[LLVMdev] SCEV Question

Wojciech Matyjewicz wmatyjewicz at fastmail.fm
Tue Jun 10 12:30:20 PDT 2008


> 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:

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?


More information about the llvm-dev mailing list