SCCP

For an analysis pass, I'm interested in reading the lattice values
calculated by SCCP. Should I split the current SCCP optimization into an
analysis piece and the optimization that depends on it, so that I can
use its analysis results?

Nick Lewycky

SCCP is already split into an SCCPSolver class that is used by the SCCP and IPSCCP classes. You should just be able to use SCCPSolver. Note that it is not a pass, just a class you can use.

-Chris

Chris Lattner wrote:

You could do that, but SCCPSolver isn't really useful to mainline LLVM for anything other than SCCP and IPSCCP, so we don't need it in a public header. Out of curiosity, what are you looking to use the latice values for? Why not just run SCCP and then look at the transformed code?

-Chris

Chris Lattner wrote:

For an analysis pass, I'm interested in reading the lattice values
calculated by SCCP. Should I split the current SCCP optimization
into an
analysis piece and the optimization that depends on it, so that I can
use its analysis results?

SCCP is already split into an SCCPSolver class that is used by the SCCP
and IPSCCP classes. You should just be able to use SCCPSolver. Note
that it is not a pass, just a class you can use.

Thanks. I thought SCCPSolver was just a helper. I suppose then I should
just move its class declaration into a header so it can be seen from
outside SCCP.cpp. Would creating a new include/llvm/Transforms/SCCP.h be
the right idea?

You could do that, but SCCPSolver isn't really useful to mainline LLVM
for anything other than SCCP and IPSCCP, so we don't need it in a public
header. Out of curiosity, what are you looking to use the latice values
for? Why not just run SCCP and then look at the transformed code?

I was planning to write an analysis pass that checks the expression at
every conditional statement to see whether the value is underdefined or
not. This would be after SCCP and other optimizations have already been
run, so conditional statements with constant expressions would already
be eliminated. (Am I being silly? There isn't a pass to eliminate
conditionals on underdefined variables is there?)

It would be fine for my purposes to just copy the class declaration into
my own code.

Nick

You could do that, but SCCPSolver isn't really useful to mainline LLVM
for anything other than SCCP and IPSCCP, so we don't need it in a public
header. Out of curiosity, what are you looking to use the latice values
for? Why not just run SCCP and then look at the transformed code?

I was planning to write an analysis pass that checks the expression at
every conditional statement to see whether the value is underdefined or
not.

Then just run the SCCP pass, and check to see if any operands satisfy the predicate "isa<UndefValue>(V)". LLVM explicitly represents undefined values.

This would be after SCCP and other optimizations have already been
run, so conditional statements with constant expressions would already
be eliminated.

Right, conditionals like "cst1 < cst2" will certainly be folded to true or false. Also "undef < X" will be folded to undef by the SCCP pass.

-Chris

Chris Lattner wrote:

You could do that, but SCCPSolver isn't really useful to mainline LLVM
for anything other than SCCP and IPSCCP, so we don't need it in a public
header. Out of curiosity, what are you looking to use the latice values
for? Why not just run SCCP and then look at the transformed code?

I was planning to write an analysis pass that checks the expression at
every conditional statement to see whether the value is underdefined or
not.

Then just run the SCCP pass, and check to see if any operands satisfy
the predicate "isa<UndefValue>(V)". LLVM explicitly represents
undefined values.

I have a case where it doesn't, but perhaps the SCCP pass isn't to blame:

  extern void write_char(int);

  const char foo[4] = "foo";

  write_char(foo[0]);
  write_char(foo[5]);

The write_char(foo[0]) correctly becomes write_char('f'), but the
write_char(foo[5]) doesn't become undefined, instead staying as a
GetElementPtrInst. I thought this might be because the optimizer is
being conservative about correctness, but that the lattice must still
show it as underdefined -- but obviously as I haven't looked at the
lattice directly, I haven't verified that yet.

Maybe it becomes overdefined as the constant can't be resolved, and I
should just fix the SCCP pass?

Nick

Then just run the SCCP pass, and check to see if any operands satisfy
the predicate "isa<UndefValue>(V)". LLVM explicitly represents
undefined values.

I have a case where it doesn't, but perhaps the SCCP pass isn't to blame:

extern void write_char(int);

const char foo[4] = "foo";

write_char(foo[0]);
write_char(foo[5]);

The write_char(foo[0]) correctly becomes write_char('f'), but the
write_char(foo[5]) doesn't become undefined, instead staying as a
GetElementPtrInst.

Well, sort of. Without a compilable function to tell for sure, I can't make absolute statements, but here are some comments. :slight_smile:

1. The SCCP pass only does really simple propagation of loads: in
    particular, a load will only be "constant folded" if it is a load from
    a constant global. This isn't, so SCCP won't touch it.
2. SCCP isn't propagating foo[0], -load-vn -gcse does. In particular,
    GCSE sees a store to a memory location, followed by a load from the
    same location (without an intervening, potentially aliasing, store).
    It forward propagates the stored value to the load (in this case, the
    constant), eliminating the load.
3. It would be straight-forward to teach the instcombine pass to turn a
    load from an invalid location (in this case, off the end of the array)
    into an undef value. If you wanted to tackle this, it should be
    straight-forward and would be a worthwhile addition to the LLVM
    optimizer.

I thought this might be because the optimizer is being conservative about correctness, but that the lattice must still show it as underdefined -- but obviously as I haven't looked at the lattice directly, I haven't verified that yet.

Yup, if there is a load from a memory location on the stack, SCCP won't touch it: it will assume it is overdefined.

Maybe it becomes overdefined as the constant can't be resolved, and I
should just fix the SCCP pass?

I'd suggest fixing this in the instcombine pass. This isn't something that the 'conditionalness' of SCCP adds value for, so doing it in a simpler place is better. If you have any questions about extending instcombine (or anything else), please ask. :slight_smile:

-Chris

Chris Lattner wrote:

Then just run the SCCP pass, and check to see if any operands satisfy
the predicate "isa<UndefValue>(V)". LLVM explicitly represents
undefined values.

I have a case where it doesn't, but perhaps the SCCP pass isn't to blame:

extern void write_char(int);

const char foo[4] = "foo";

write_char(foo[0]);
write_char(foo[5]);

The write_char(foo[0]) correctly becomes write_char('f'), but the
write_char(foo[5]) doesn't become undefined, instead staying as a
GetElementPtrInst.

Well, sort of. Without a compilable function to tell for sure, I can't
make absolute statements, but here are some comments. :slight_smile:

Wrap the two write_char calls in "void f(){ ... }" . I've attached the
full .c file this time.

1. The SCCP pass only does really simple propagation of loads: in
   particular, a load will only be "constant folded" if it is a load from
   a constant global. This isn't, so SCCP won't touch it.
2. SCCP isn't propagating foo[0], -load-vn -gcse does. In particular,
   GCSE sees a store to a memory location, followed by a load from the
   same location (without an intervening, potentially aliasing, store).
   It forward propagates the stored value to the load (in this case, the
   constant), eliminating the load.

I tested it with "opt -sccp". I should've included a properly runnable
example the first time. Sorry. At least, running "opt -load-vn -gcse"
does not convert foo[0] into "102".

I'm not even sure whether foo[4] is a ConstantArray or a GlobalValue,
but either way it's Constant.

3. It would be straight-forward to teach the instcombine pass to turn a
   load from an invalid location (in this case, off the end of the array)
   into an undef value. If you wanted to tackle this, it should be
   straight-forward and would be a worthwhile addition to the LLVM
   optimizer.

In SCCPSolver::visitGetElementPtrInst, it would fall through to the
final markConstant call at the end of the function. Someone should be
doing a check with indexValid to see if instead it should be marking as
undefined.

I can try to produce such a patch.

I thought this might be because the optimizer is being conservative
about correctness, but that the lattice must still show it as
underdefined -- but obviously as I haven't looked at the lattice
directly, I haven't verified that yet.

Yup, if there is a load from a memory location on the stack, SCCP won't
touch it: it will assume it is overdefined.

Maybe it becomes overdefined as the constant can't be resolved, and I
should just fix the SCCP pass?

I'd suggest fixing this in the instcombine pass. This isn't something
that the 'conditionalness' of SCCP adds value for, so doing it in a
simpler place is better. If you have any questions about extending
instcombine (or anything else), please ask. :slight_smile:

I don't think it needs to be in the SCCP, but I'd have to familiarize
myself with the instcombine code. Just so long as you're still sure,
after noting that it's not the GCSE pass! :slight_smile:

Actually, I have been wondering how LLVM handles something nasty, like a
GetElementPtrInst with a base pointer to foo, and an index of bar-foo
(where foo and bar are both global arrays). This would look like an
invalid access of foo[bar-foo], but actually be a valid access of
bar[0]. Specifically, I wouldn't want to break such cases with this
optimization.

Nick

llvm-dev.c (120 Bytes)

Nick Lewycky wrote:

I tested it with "opt -sccp". I should've included a properly runnable
example the first time. Sorry. At least, running "opt -load-vn -gcse"
does not convert foo[0] into "102".

Further testing shows that the SCCP optimization will do handle it, and
so will the instruction combiner.

Chris Lattner wrote:

I'd suggest fixing this in the instcombine pass. This isn't something
that the 'conditionalness' of SCCP adds value for, so doing it in a
simpler place is better. If you have any questions about extending
instcombine (or anything else), please ask. :slight_smile:

I've patched the instruction combiner to return UndefValue when the
index is constant and known to be out of range for either an ArrayType
or PackedType.

Patch attached.

Nick Lewycky

invalidindexundef.patch (1.74 KB)

Nick Lewycky wrote:

Hi Nick,

Sorry for the delay. :frowning:

Chris Lattner wrote:

I'd suggest fixing this in the instcombine pass. This isn't something
that the 'conditionalness' of SCCP adds value for, so doing it in a
simpler place is better. If you have any questions about extending
instcombine (or anything else), please ask. :slight_smile:

I've patched the instruction combiner to return UndefValue when the
index is constant and known to be out of range for either an ArrayType
or PackedType.

Patch attached.

Very nice, and it includes a testcase, perfect! I've applied your patch:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060522/035049.html
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060522/035050.html

Thanks, and sorry again for the delay :frowning:

-Chris