<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Mar 26, 2015 at 2:54 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I've run into cases where, because not all of LLVM's optimizations<br>
understand the semantics of the `llvm.$op.with.overflow` intrinsics,<br>
canonicalizing compares to `llvm.$op.with.overflow` ends up preventing<br>
optimization.<br>
<br>
For instance, running the following snippet through `opt -indvars`<br>
optimizes `%to.optimize` to `true`, but running it through<br>
`opt -instcombine -indvars` does not.<br>
<br>
```<br>
declare void @side_effect(i1)<br>
<br>
define void @foo(i8 %x, i8 %y) {<br>
entry:<br>
%sum = add i8 %x, %y<br>
%e = icmp ugt i8 %x, %sum<br>
br i1 %e, label %exit, label %loop<br>
<br>
loop:<br>
%idx = phi i8 [ %x, %entry ], [ %idx.inc, %loop ]<br>
%idx.inc = add i8 %idx, 1<br>
%to.optimize = icmp ule i8 %idx, %sum<br>
call void @side_effect(i1 %to.optimize)<br>
%c = icmp ule i8 %idx.inc, %sum<br>
br i1 %c, label %loop, label %exit<br>
<br>
exit:<br>
ret void<br>
}<br>
```<br>
<br>
This happens because `-instcombine` does the following tranform:<br>
<br>
```<br>
entry:<br>
%uadd = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 %x, i8 %y)<br>
%0 = extractvalue { i8, i1 } %uadd, 0<br>
%e = extractvalue { i8, i1 } %uadd, 1<br>
br i1 %e, label %exit, label %loop.preheader<br>
```<br>
<br>
and ScalarEvolution can no longer see through the `extractvalue` of<br>
the call to `llvm.uadd.with.overflow.i8`.<br>
<br>
The right way to fix this depends on the intended purpose of the<br>
`llvm.$op.with.overflow` intrinsics. Three solutions I can think of:<br>
<br>
* if they're a convenience useful only for better codegen, can the<br>
transform that instcombine is doing currently (transforming<br>
compares to `extractvalue` of a `.with.overflow` intrinsic) be<br>
moved to CodeGenPrep?<br></blockquote><div><br></div><div>Unfortunately, they are not a mere convenience. I've personally spent effort trying to optimize away overflow checks in InstCombine, it does this in its InstCombineCalls visitor.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
* if they're something more fundamental, then maybe they should to be<br>
promoted to an instruction? They've been around since at least<br>
llvm 2.6 as far as I can tell. Personally, I seriously doubt this<br>
is a good idea, given that the semantics of these intrinsics can be<br>
completely described by a DAG composed of existing instructions.<br></blockquote><div><br></div><div>I think promoting them would be quite disruptive. Most passes don't care about these operations and can't do much with them.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
* add rules to ScalarEvolution to have it understand these intrinsics<br>
(or maybe even expand them before `-indvars` -- I think<br>
`-liv-reduce` tries to do this in some cases), but I'd vote for<br>
keeping this complexity out of ScalarEvolution unless there are<br>
good reasons why the `.with.overflow` calls need to be introduced<br>
before codegenprep.<br></blockquote><div><br></div><div>If we don't care about trying to optimize out overflow checks in InstCombine, I'd go with moving the complexity to CGP. However, I think InstCombine is doing the right thing here by forming these. I think there are two choices that keep our optimizations:</div><div>- Teach SCEV, one way or another, about *_with_overflow.</div><div>- Don't form overflow intrinsics in InstCombine but instead teach ProcessUGT_ADDCST_ADD, et al. to use WillNotOverflowUnsignedAdd, et al. to optimize away the compare.</div><div><br></div><div>The second approach sounds much easier but I don't know what we lose by doing it.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
What do you think?<br>
<span class="HOEnZb"><font color="#888888"><br>
-- Sanjoy<br>
</font></span></blockquote></div><br></div></div>