[LLVMdev] 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));
      }
    }