[LLVMdev] SCCP

[Nick Lewycky]

Chris Lattner wrote:
> 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. :)

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

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

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: llvm-dev.c
Type: text/x-csrc
Size: 120 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20060510/85372206/attachment.c>