[LLVMdev] help with pointer-to-array conversion

[Chris Lattner]

On Thu, 28 Jul 2005, Naftali Schwartz wrote:
> I now understand that IndVarSimplify.cpp is capable of reproducing array 
> references when the pointer initialization from the array address is found 
> inside the immediately enclosing loop, such that in the following code:

Ok.

> int A[20000], B[100], Z;
> int main()
> {
>        int i, j, *a, *b;
>        for ( a = &A[0], i = 0; i != 200; i++ )
>                for ( b = &B[0], j = 0; j != 100; j++ )
>                        Z += *a++ * *b++;
> }
>
> the pointer b can be transformed into an offset from B[], but a cannot be 
> transformed into an offset from A[] because the initialization is two levels 
> up.

Hrm, that should work.

> I started poking around in IndVarSimplify.cpp and I have a patch which should 
> (at least partially) enable the transformation for a as well, but I find that 
> although the code looks OK in debug printouts, the gccas output is unchanged.

Ok

> So two questions:  1) Am I on the right track with this transformation (patch 
> enclosed) and

I haven't taken a look at the code.  Could you please give a very simple 
example showing what it is supposed to change that is currently not 
handled?  Also, can you make sure to wrap the lines to fit in 80-columns? 
Finally, please send diffs as "unified" diffs, this makes it easier to 
read.  You can get unified diffs by passing "-u" to cvs diff or normal 
diff.

> 2) why does the output not reflect my changes?

There are a couple of different possibilities.  I'm not sure exactly what 
you're trying to accomplish here, but one of the following may happen:

1. Something in the compiler is running after indvars that undoes what you
    are trying to do.
2. The input to indvars in not what you think it is, so running the pass
    in the middle of gccas is not giving you the same output as running it
    logically at the end of gccas with the opt program.

To isolate #2, it might be useful to get the full set of passes that gccas 
is doing.  gccas will dump the passes if you run it like this:

gccas /dev/null -o /dev/null -debug-pass=Arguments

That way you can use the passes with 'opt' to see exactly what code is 
given to indvars.

-Chris

> Index: lib/Transforms/Scalar/IndVarSimplify.cpp
> ===================================================================
> RCS file: /var/cvs/llvm/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp,v
> retrieving revision 1.78
> diff -r1.78 IndVarSimplify.cpp
> 310c310
> <         runOnLoop(*I);
> ---
>>         runOnLoop(LI, *I);
> 322,323c322,323
> <     void runOnLoop(Loop *L);
> <     void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader,
> ---
>>     void runOnLoop(LoopInfo *LI, Loop *L);
>>     void EliminatePointerRecurrence(LoopInfo *LI, Loop *L, PHINode *PN, 
> BasicBlock *Preheader,
> 361c361
> < void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
> ---
>> void IndVarSimplify::EliminatePointerRecurrence(LoopInfo *LI, Loop *L, 
> PHINode *PN,
> 366a367
>> Value *saved_trip_count = L->getTripCount(); // save before it's 
> clobbered
> 392c393,408
> <
> ---
>> std::cerr << "\tGEPI: " << *GEPI;
>>       if (PHINode *phi = dyn_cast<PHINode>(GEPI->getOperand(0)))
>>       {
>>               if (ConstantExpr *CE = 
> dyn_cast<ConstantExpr>(phi->getIncomingValue(0)))
>>               if (CE->getOpcode() == Instruction::GetElementPtr) // We 
> want this to become explicit...
>>               {
>> std::cerr << "Block Before: " << *GEPI->getParent();
>>                       Instruction *mul = 
> BinaryOperator::createMul(saved_trip_count,
>>                               LI->getLoopFor( phi->getIncomingBlock(1) )
>>                               ->getCanonicalInductionVariable(), "mul.", 
> GEPI);
>>                       Instruction *add = BinaryOperator::createAdd(mul, 
> NewAdd, "add.", GEPI);
>>                       GEPI->setOperand( 0, phi->getIncomingValue(0) );
>>                       GEPI->setOperand( 1, add );
>> std::cerr << "Block After: " << *GEPI->getParent();
>>               }
>>       }
> 605c621,622
> < void IndVarSimplify::runOnLoop(Loop *L) {
> ---
>> void IndVarSimplify::runOnLoop(LoopInfo *LI, Loop *L) {
>> 
> 617c634
> <       EliminatePointerRecurrence(PN, Preheader, DeadInsts);
> ---
>>       EliminatePointerRecurrence(LI, L, PN, Preheader, DeadInsts);
> 626c643
> <     runOnLoop(*I);
> ---
>>     runOnLoop(LI,*I);
> 652,653c669,670
> <         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)))
>
> Naftali
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/