[LLVMdev] SCCP

[Chris Lattner]

On Wed, 10 May 2006, Nick Lewycky 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. :)

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

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/