llvm dev - Jun 2008 - [LLVMdev] SCEV Question

Is there a document describing the guts of SCEV anywhere?

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.

In this case, I have a load address and I call SE.getSCEV(Addr).  That
returns the linear recurrence.

                                          -Dave

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

I'm not aware of any LLVM-specific document describing SCEV.
> 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.

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?

-Wojtek

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