llvm dev - May 2008 - [LLVMdev] Troubling promotion of return value to Integer ...

On Fri, 2008-05-16 at 11:42 -0700, Chris Lattner wrote:
> This would get compiled (by the front-end to something like this:
> 
> 
> define i32 @bar() {
>   ; call
>   %tmp = call i32 @foo()
>   %x = trunc i32 %tmp to i8
> 
> 
>   ; return
>   %tmp2 = sext i8 to i32
>   ret i32 %tmp2
> }
> 
> 
> The problem with this is that we now have a trunc+sext instruction
> that cannot be eliminated...
Chris:

In an attempt to avoid adding distraction, I withheld the following
thought earlier. It may be equivalent to your annotation idea, but I
want to throw it out in case it provokes something useful.

Extension and promotion is a peculiar case. If an

   %x = sext i8 %y to i32

has already been performed, then there is no harm (in the sense that no
value is changed) by executing it redundantly on the low field of the
result register, as in:

   %z = sext i8 %x to i32

I'm giving an input %x that is known to be an i32 here intentionally.

This prompts me to the following thought, which may not be helpful.
Perhaps we might introduce something like the following two
pseudo-instructions in the IR:

   resext   sign extend on a quantity that the front end asserts has
            already been sign extended.

   rezext   zero extend on a quantity that the front end asserts has
            already been zero extended.

These instructions serve to advise the caller-side optimizer that the
required extend has been done, which tells us what we need to know for
optimizations. If they inadvertently make it to the back end, they
peephole away as a NO-OP.

Since we are already trusting the front end to introduce the correct
extension in the callee, I don't see any harm in trusting it to advise
us that it did so at the caller return site. The outcome is certainly no
worse than a front end that simply generates IR that is wrong, and
omission of the advisory instruction merely results in loss of an
optimization opportunity rather than any error of computational
semantics.

Like I say, not sure if this is helpful.


shap

On May 16, 2008, at 12:19 PM, Jonathan S. Shapiro wrote:
> In an attempt to avoid adding distraction, I withheld the following
> thought earlier. It may be equivalent to your annotation idea, but I
> want to throw it out in case it provokes something useful.
No problem, ideas are welcome.
> I'm giving an input %x that is known to be an i32 here intentionally.
>
> This prompts me to the following thought, which may not be helpful.
> Perhaps we might introduce something like the following two
> pseudo-instructions in the IR:
>
>   resext   sign extend on a quantity that the front end asserts has
>            already been sign extended.
>
>   rezext   zero extend on a quantity that the front end asserts has
>            already been zero extended.
>
> These instructions serve to advise the caller-side optimizer that the
> required extend has been done, which tells us what we need to know for
> optimizations. If they inadvertently make it to the back end, they
> peephole away as a NO-OP.
Ok, so these are basically "copies with assertions".  There are a  
couple of similar proposals for things like this (for example, with  
pointers you might want to make some assertion w.r.t. aliasing).

The downside of this sort of approach (vs attributes) is that it  
increases the size of the every caller of the function.  The advantage  
is that it is more explicit, potentially more general, and doesn't  
require new attributes for each size.  OTOH, some of these advantages  
go away if this gets extended for other properties: we end up having a  
copy with attributes on it :)
> Since we are already trusting the front end to introduce the correct
> extension in the callee, I don't see any harm in trusting it to advise
> us that it did so at the caller return site.
Right.  If it's part of the ABI, it is fair (and important!) for the  
optimizer to be able to use this.
> The outcome is certainly no
> worse than a front end that simply generates IR that is wrong, and
> omission of the advisory instruction merely results in loss of an
> optimization opportunity rather than any error of computational
> semantics.
Yep.

-Chris

On Fri, 2008-05-16 at 13:00 -0700, Chris Lattner wrote:
> Ok, so these are basically "copies with assertions".  There are a
> couple of similar proposals for things like this (for example, with  
> pointers you might want to make some assertion w.r.t. aliasing).
> 
> The downside of this sort of approach (vs attributes) is that it  
> increases the size of the every caller of the function.  The advantage  
> is that it is more explicit, potentially more general, and doesn't  
> require new attributes for each size.  OTOH, some of these advantages  
> go away if this gets extended for other properties: we end up having a  
> copy with attributes on it :)
Agreed, with one caveat:

I don't understand how attributes work at this point, but if the
use-case is specific to each caller, the attribute will need to be
attached separately to each call point, and the difference in space for
such cases vs "copies with assertions" may not turn out to be very
big.



A general observation I would make -- this is coming from other systems
that I have worked on and does not reflect any understanding of LLVM
internals -- is that annotation schemes are often a source of error in
programs. Perhaps I have gotten them wrong when I have attempted them,
but what I have found in the past is that I end up with a lot of code
where I have a primary switch-like construct on the main object type (in
this case I imagine a switch on IR instruction), followed by a bunch of
special cases that look for applicable annotations within each case.

What I have observed to happen when code is structured this way is that
two types of coding failures become common:

  1. Failures of case analysis, where some annotation is applicable in
     several places or states, but is missing in some subset of these.
     These can be hard to locate.

  2. Failures of update, of the form "I caught 4 of the 5 places that
     needed this update."

  3. What one really ends up with, in effect, is a situation where the
     *real* instruction (from a semantic perspective) was the alleged
     instruction plus the semantically important annotation, but the
     representational encoding of the real instruction has been made
     awkward to deal with by splitting it into multiple substructures.

That is: they are "robust to error", in the sense that with high
likelihood errors will be introduced by maintenance over time.

Because of this, I have come to feel in my own code that
operation-specific annotations are often better dealt with by new
operations that can be inserted directly into the primary switch. I can
always run multiple cases into the same switch block, and the compiler
will help me notice which ones I forgot.  I try to reserve use of
annotations and attributes for situations where:

  1. The annotation/attribute is advisory or non-semantic, or

  2. The annotation/attribute is almost universally applicable, and is
     therefore not likely to need independent consideration at
     multiple points in a long switch-like construct. Instead
     it gets dealt with at one place, either at top or bottom of
     the switch.

It's a trade-off, and I see no hard and fast rule that can be extracted
here, but my personal bias is to err in favor of robustness under
maintenance rather than in favor of reduced memory consumption.


shap