patch for pointer-to-array conversion

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

patch for pointer-to-array conversion

Naftali Schwartz
The enlosed patch for IndVarSimplify.cpp works even when the pointer
increment is deeply nested wrt pointer initialization, but note that it
needs to have loop structures preserved, as in the following:

int A[3000000], B[20000], C[100], Z;
volatile int I, J, K;
int main()
{
         int i, j, k, *a, *b, *c;
         for ( a = &A[0], i = 0; i != 300; i++ )
         {
                 I++;
                 for ( b = &B[0], j = 0; j != 200; j++ )
                 {
                         J++;
                         for ( c = &C[0], k = 0; k != 100; k++ )
                         {
                                 K++;
                                 Z += *a++ * *b++ * *c++;
                         }
                 }
         }
}

but unlike the collapsing which would happen in, e.g., the following:

int A[3000000], B[20000], C[100], Z;
int main()
{
         int i, j, k, *a, *b, *c;
         for ( a = &A[0], i = 0; i != 300; i++ )
                 for ( b = &B[0], j = 0; j != 200; j++ )
                         for ( c = &C[0], k = 0; k != 100; k++ )
                                 Z += *a++ * *b++ * *c++;
}

Here's the patch with diff -u, limited to 80 columns:
Does it look reasonable?

Thanks,
Naftali

Index: lib/Transforms/Scalar/IndVarSimplify.cpp
===================================================================
RCS file: /var/cvs/llvm/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp,v
retrieving revision 1.78
diff -u -r1.78 IndVarSimplify.cpp
--- lib/Transforms/Scalar/IndVarSimplify.cpp    15 Jun 2005 21:29:31 -0000
1.78
+++ lib/Transforms/Scalar/IndVarSimplify.cpp    29 Jul 2005 15:17:19 -0000
@@ -49,6 +49,7 @@
  #include "llvm/Transforms/Utils/Local.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
  using namespace llvm;

  namespace {
@@ -300,6 +301,7 @@
      ScalarEvolution *SE;
      bool Changed;
    public:
+
      virtual bool runOnFunction(Function &) {
        LI = &getAnalysis<LoopInfo>();
        SE = &getAnalysis<ScalarEvolution>();
@@ -354,21 +356,11 @@
    }
  }

-
-/// EliminatePointerRecurrence - Check to see if this is a trivial GEP
pointer
-/// recurrence.  If so, change it into an integer recurrence, permitting
-/// analysis by the SCEV routines.
-void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
-                                                BasicBlock *Preheader,
-                                            std::set<Instruction*>
&DeadInsts) {
-  assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!");
-  unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader);
-  unsigned BackedgeIdx = PreheaderIdx^1;
-  if (GetElementPtrInst *GEPI =
-      dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx)))
-    if (GEPI->getOperand(0) == PN) {
-      assert(GEPI->getNumOperands() == 2 && "GEP types must mismatch!");
-
+static std::pair<Value*,Value*> transformPointerRecurrence(
+               GetElementPtrInst *GEPI, PHINode *PN, BasicBlock
*Preheader )
+{
+      unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader);
+      unsigned BackedgeIdx = PreheaderIdx^1;
        // Okay, we found a pointer recurrence.  Transform this pointer
        // recurrence into an integer recurrence.  Compute the value that
gets
        // added to the pointer at every iteration.
@@ -390,6 +382,35 @@
        // Update the GEP to use the new recurrence we just inserted.
        GEPI->setOperand(1, NewAdd);

+      // Nesting is deep...
+      if ( PHINode *PN = dyn_cast<PHINode>( GEPI->getOperand(0) ) )
+           return transformPointerRecurrence( GEPI, PN,
PN->getIncomingBlock(0) );
+      return std::make_pair(NewAdd,NewPhi);
+}
+
+/// EliminatePointerRecurrence - Check to see if this is a trivial GEP
pointer
+/// recurrence.  If so, change it into an integer recurrence, permitting
+/// analysis by the SCEV routines.
+void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
+                                                BasicBlock *Preheader,
+                                            std::set<Instruction*>
&DeadInsts) {
+  assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!");
+  unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader);
+  unsigned BackedgeIdx = PreheaderIdx^1;
+  if (GetElementPtrInst *GEPI =
+      dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx)))
+    if (GEPI->getOperand(0) == PN) {
+      std::vector<Instruction*> Updates;
+      for (Value::use_iterator UI = PN->use_begin(),
+               E = PN->use_end(); UI != E; ++UI)
+        if ( *UI != GEPI && *UI->use_begin() != PN )
+           Updates.push_back( dyn_cast<Instruction>( *UI ) );
+      assert(GEPI->getNumOperands() == 2 && "GEP types must mismatch!");
+      Value *NewAdd, *NewPhi;
+       tie(NewAdd,NewPhi) = transformPointerRecurrence( GEPI, PN,
Preheader );
+       for ( std::vector<Instruction*>::iterator i = Updates.begin();
+                       i != Updates.end(); i++ )
+               (*i)->replaceAllUsesWith( GEPI );
        // If the incoming value is a constant expr GEP, try peeling out
the array
        // 0 index if possible to make things simpler.
        if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEPI->getOperand(0)))
@@ -603,6 +624,7 @@


  void IndVarSimplify::runOnLoop(Loop *L) {
+
    // First step.  Check to see if there are any trivial GEP pointer
recurrences.
    // If there are, change them into integer recurrences, permitting
analysis by
    // the SCEV routines.
@@ -649,8 +671,8 @@
          // variable.  Doing so will put expensive multiply instructions
inside
          // of the loop.  For now just disable indvar subst on anything
more
          // complex than a linear addrec.
-        if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV))
-          if (AR->getNumOperands() == 2 &&
isa<SCEVConstant>(AR->getOperand(1)))
+        if (1)//SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV))
+          if (1)//AR->getNumOperands() == 2 &&
isa<SCEVConstant>(AR->getOperand(1)))
              IndVars.push_back(std::make_pair(PN, SCEV));
      }
    }

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev