<div dir="ltr">So, the first gets deleted with -dce because it's trivially dead.<div><br></div><div>The second, nothing gets deleted because no DCE we have does DCE using control dependence, so it marks Terminators as live. This makes everything executable in your case.</div><div><br></div><div>SCCP and most other passes don't delete it because they are forward passes, and start by assuming the entryblock is executable and go from there. If you make this assumption (which is not fixable for forward passes), everything here is executable.</div><div><br></div><div>DCE is normally the backwards pass that fixes this.<br></div><div><br></div><div>You can make ADCE fix this particular case, even without control dependence, with a small change:<br><br></div><div>Right now it marks all terminators as alive.</div><div><br></div><div>It should mark all return's as alive.</div><div>Other terminators, It should only mark terminators as live once it reaches a block with an alive operation in it (IE the first time it gets into that block).</div><div><br></div><div><br></div><div>That would make it mark the return as useful, then discover no other block has useful operations, and delete them all.</div><div><br></div><div>I've attached a mostly untested patch to do this.</div><div>It does what you want (It removes everything but the return)</div><div>It should work in all cases.</div><div>I ripped the erasure code from SCCP</div><div>It will crash because it doesn't know what to do when it needs to redirect the entry block</div><div>SCCP doesn't have this problem because it is only redirecting, not erasing, so the entry block always has a terminator to redirect.</div><div>(before, it crashed because it wanted to remove the entry block) </div><div><br></div><div><br></div><div>So this needs to be fixed.</div><div>I marked it with a TODO.</div><div>If you want to do this, maybe refactor out the code for deleting dead blocks from SCCP/DCE, and then submit the patch, it would be great.</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Mar 25, 2015 at 10:47 AM, Benoit Belley <span dir="ltr"><<a href="mailto:Benoit.Belley@autodesk.com" target="_blank">Benoit.Belley@autodesk.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi everyone,<br>
<br>
<br>
I am wondering what¹s stopping the LLVM optimizer (opt -O3) from<br>
eliminating the apparently useless « icmp sgt » instruction in the<br>
following piece of LLVM IR.<br>
<br>
> ; ModuleID = 'lambda-opt.bc'<br>
> target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"<br>
> target triple = "x86_64-apple-macosx10.10.0"<br>
><br>
> ; Function Attrs: nounwind readnone ssp uwtable<br>
> define { <2 x float>, float } @_Z18sampleNullOperator5PointS_(i64<br>
%pmin.coerce0, i32 %pmin.coerce1, i64 %pmax.coerce0, i32 %pmax.coerce1) #0<br>
{<br>
> _ZN15SamplingClosureD1Ev.exit:<br>
> %0 = icmp sgt i32 %pmin.coerce1, %pmax.coerce1<br>
> ret { <2 x float>, float } zeroinitializer<br>
> }<br>
><br>
> attributes #0 = { nounwind readnone ssp uwtable<br>
"less-precise-fpmad"="false" "no-frame-pointer-elim"="true"<br>
"no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false"<br>
"no-nans-fp-math"="false" "stack-protector-buffer-size"="8"<br>
"unsafe-fp-math"="false" "use-soft-float"="false" }<br>
><br>
> !llvm.ident = !{!0}<br>
><br>
> !0 = metadata !{metadata !"Apple LLVM version 6.0 (clang-600.0.57)<br>
(based on LLVM 3.5svn)"}<br>
<br>
<br>
The X86 code generation passes seems to eliminate it for the simple case<br>
shown above. The generated assembly code is actually:<br>
<br>
<br>
> __Z18sampleNullOperator5PointS_: ## @_Z18sampleNullOperator5PointS_<br>
> .cfi_startproc<br>
> ## BB#0: ## %_ZN15SamplingClosureD1Ev.exit<br>
> push rbp<br>
> Ltmp0:<br>
> .cfi_def_cfa_offset 16<br>
> Ltmp1:<br>
> .cfi_offset rbp, -16<br>
> mov rbp, rsp<br>
> Ltmp2:<br>
> .cfi_def_cfa_register rbp<br>
> vxorps xmm0, xmm0, xmm0<br>
> vxorps xmm1, xmm1, xmm1<br>
> pop rbp<br>
> ret<br>
<br>
<br>
I am wondering because I think that it might explain why the LLVM IR code<br>
shown below does not get simplified to a single "ret { <2 x float>, float<br>
} zeroinitializer" instruction. It seems to me that the nested loops have<br>
no side-effects and are guaranteed to terminate in a finite amount of<br>
time. Unless, the nested "icmp sgt" instructions cannot be eliminated.<br>
<br>
Of course, in that case, the X86 code generation passes can no longer do<br>
their magic...<br>
<br>
<br>
> ; ModuleID = 'lambda-opt.bc'<br>
> target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"<br>
> target triple = "x86_64-apple-macosx10.10.0"<br>
><br>
> ; Function Attrs: ssp uwtable<br>
> define { <2 x float>, float } @_Z18sampleNullOperator5PointS_(i64<br>
> %pmin.coerce0, i32 %pmin.coerce1, i64 %pmax.coerce0, i32<br>
%pmax.coerce1) #0<br>
> {<br>
> %1 = icmp slt i32 %pmin.coerce1, %pmax.coerce1<br>
> br i1 %1, label %.lr.ph35.i, label %_ZN15SamplingClosureD1Ev.exit<br>
><br>
> .lr.ph35.i: ; preds = %0<br>
> %2 = lshr i64 %pmin.coerce0, 32<br>
> %3 = trunc i64 %2 to i32<br>
> %4 = lshr i64 %pmax.coerce0, 32<br>
> %5 = trunc i64 %4 to i32<br>
> %6 = icmp slt i32 %3, %5<br>
> %7 = trunc i64 %pmin.coerce0 to i32<br>
> %8 = trunc i64 %pmax.coerce0 to i32<br>
> %9 = icmp slt i32 %7, %8<br>
> br i1 %6, label %.lr.ph23.us.i.preheader, label<br>
> %_ZN15SamplingClosureD1Ev.exit<br>
><br>
> .lr.ph23.us.i.preheader: ; preds =<br>
%.lr.ph35.i<br>
> %10 = trunc i64 %pmax.coerce0 to i32<br>
> %11 = trunc i64 %pmin.coerce0 to i32<br>
> %12 = sub i32 %10, %11<br>
> br label %.lr.ph23.us.i<br>
><br>
> ._crit_edge24.us-lcssa.us57.i: ; preds = %14,<br>
> %.lr.ph23.us.i<br>
> %13 = add nsw i32 %z.028.us.i, 1<br>
> %exitcond66.i = icmp eq i32 %13, %pmax.coerce1<br>
> br i1 %exitcond66.i, label %_ZN15SamplingClosureD1Ev.exit, label<br>
> %.lr.ph23.us.i<br>
><br>
> .lr.ph23.us.i: ; preds =<br>
> %._crit_edge24.us-lcssa.us57.i, %.lr.ph23.us.i.preheader<br>
> %z.028.us.i = phi i32 [ %13, %._crit_edge24.us-lcssa.us57.i ], [<br>
> %pmin.coerce1, %.lr.ph23.us.i.preheader ]<br>
> br i1 %9, label %.lr.ph.us.us.i, label<br>
%._crit_edge24.us-lcssa.us57.i<br>
><br>
> ; <label>:14 ; preds = %.noexc,<br>
> %middle.block<br>
> %15 = add nsw i32 %y.018.us.us.i, 1<br>
> %exitcond65.i = icmp eq i32 %15, %5<br>
> br i1 %exitcond65.i, label %._crit_edge24.us-lcssa.us57.i, label<br>
> %.lr.ph.us.us.i<br>
><br>
> .lr.ph.us.us.i: ; preds = %14,<br>
> %.lr.ph23.us.i<br>
> %y.018.us.us.i = phi i32 [ %15, %14 ], [ %3, %.lr.ph23.us.i ]<br>
> %end.idx = add i32 %12, %7<br>
> %n.vec = and i32 %12, -128<br>
> %end.idx.rnd.down = add i32 %n.vec, %7<br>
> %cmp.zero = icmp eq i32 %n.vec, 0<br>
> br i1 %cmp.zero, label %middle.block, label %vector.body<br>
><br>
> vector.body: ; preds =<br>
%vector.body,<br>
> %.lr.ph.us.us.i<br>
> %index = phi i32 [ %index.next, %vector.body ], [ %7,<br>
%.lr.ph.us.us.i ]<br>
> %index.next = add i32 %index, 128<br>
> %16 = icmp eq i32 %index.next, %end.idx.rnd.down<br>
> br i1 %16, label %middle.block, label %vector.body, !llvm.loop !1<br>
><br>
> middle.block: ; preds =<br>
%vector.body,<br>
> %.lr.ph.us.us.i<br>
> %resume.val = phi i32 [ %7, %.lr.ph.us.us.i ], [ %end.idx.rnd.down,<br>
> %vector.body ]<br>
> %cmp.n = icmp eq i32 %end.idx, %resume.val<br>
> br i1 %cmp.n, label %14, label %.noexc<br>
><br>
> .noexc: ; preds = %.noexc,<br>
> %middle.block<br>
> %x.012.us.us.i = phi i32 [ %17, %.noexc ], [ %resume.val,<br>
%middle.block ]<br>
> %17 = add nsw i32 %x.012.us.us.i, 1<br>
> %exitcond64.i = icmp eq i32 %17, %8<br>
> br i1 %exitcond64.i, label %14, label %.noexc, !llvm.loop !4<br>
><br>
> _ZN15SamplingClosureD1Ev.exit: ; preds =<br>
> %._crit_edge24.us-lcssa.us57.i, %.lr.ph35.i, %0<br>
> ret { <2 x float>, float } zeroinitializer<br>
> }<br>
><br>
> attributes #0 = { ssp uwtable "less-precise-fpmad"="false"<br>
> "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf"<br>
> "no-infs-fp-math"="false" "no-nans-fp-math"="false"<br>
> "stack-protector-buffer-size"="8" "unsafe-fp-math"="false"<br>
> "use-soft-float"="false" }<br>
><br>
> !llvm.ident = !{!0}<br>
><br>
> !0 = metadata !{metadata !"Apple LLVM version 6.0 (clang-600.0.57)<br>
(based<br>
> on LLVM 3.5svn)"}<br>
> !1 = metadata !{metadata !1, metadata !2, metadata !3}<br>
> !2 = metadata !{metadata !"llvm.vectorizer.width", i32 1}<br>
> !3 = metadata !{metadata !"llvm.vectorizer.unroll", i32 1}<br>
> !4 = metadata !{metadata !4, metadata !2, metadata !3}<br>
<br>
<br>
Thanks for you help,<br>
Benoit<br>
<br>
Benoit Belley<br>
Sr Principal Developer<br>
M&E-Product Development Group<br>
MAIN +1 514 393 1616<br>
DIRECT +1 438 448 6304<br>
FAX +1 514 393 0110<br>
Twitter <<a href="http://twitter.com/autodesk" target="_blank">http://twitter.com/autodesk</a>><br>
Facebook <<a href="https://www.facebook.com/Autodesk" target="_blank">https://www.facebook.com/Autodesk</a>><br>
Autodesk, Inc.<br>
10 Duke Street<br>
Montreal, Quebec, Canada H3C 2L7<br>
<a href="http://www.autodesk.com" target="_blank">www.autodesk.com</a> <<a href="http://www.autodesk.com/" target="_blank">http://www.autodesk.com/</a>><br>
<br>
<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div><br></div>