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

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