[LLVMdev] SCEV Question

[David Greene]

On Tuesday 10 June 2008 14:30, Wojciech Matyjewicz wrote:
> Hi,
>
> > Is there a document describing the guts of SCEV anywhere?
>
> If you're looking for theoretical background of SCEV (chains of
> recurrences algebra), you may take a look at this article:
> http://citeseer.ist.psu.edu/vanengelen00symbolic.html

Yep, I have this one.

> I'm not aware of any LLVM-specific document describing SCEV.

Ok.

> > I have a simple question.  When looking at a linear SCEVAddRecExpr
> > with a constant step recurrence (that is, getStepRecurrence returns
> > SCEVConstant), is the constant in terms of bytes or in terms of "index,"
> > in that the byte offset is calculated by taking the step and multiplying
> > it by the data size of any memory operation its used in.
>
> SCEV expressions are orthogonal to memory operations. They just describe
> (in a finite way) what consecutive values will an LLVM-register defined
> in a (possibly infinite) loop have. They apply only to integer
> registers. I believe an inttoptr or getelementptr instruction has to be
> used with such an integer register as an operand before performing a
> memory operation. And it is the selection of one of these instruction
> that decides how to interpret a SCEV with regard to a memory operation.

Right.  That's what I figured.

> For example, suppose that a i32 register named %i defined in a loop has
> SCEV {1, 2} and:
>   %ptr = getelementptr i32* %base, i32 %i
> Then %ptr in succesive iterations will be defined as:
>   %base + 4 bytes   // %i = 1
>   %base + 12 bytes  // %i = 3
>   %base + 20 bytes  // %i = 5
>
> > In this case, I have a load address and I call SE.getSCEV(Addr).  That
> > returns the linear recurrence.
>
> Hmm... Don't you use one of the instruction mentioned above on Addr
> before it hits the load?

I'll have to double-check, but I imagine so.

Thanks.

                                                  -Dave