llvm dev - May 2006 - [LLVMdev] SCCP

Chris Lattner wrote:
> On Tue, 9 May 2006, Nick Lewycky 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

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/

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>