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));
}
}
