Optimization puzzle...

Hi everyone,

I am wondering what¹s stopping the LLVM optimizer (opt -O3) from
eliminating the apparently useless « icmp sgt » instruction in the
following piece of LLVM IR.

    > ; ModuleID = 'lambda-opt.bc'
    > target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
    > target triple = "x86_64-apple-macosx10.10.0"
    >
    > ; Function Attrs: nounwind readnone ssp uwtable
    > define { <2 x float>, float } @_Z18sampleNullOperator5PointS_(i64
%pmin.coerce0, i32 %pmin.coerce1, i64 %pmax.coerce0, i32 %pmax.coerce1) #0
{
    > _ZN15SamplingClosureD1Ev.exit:
    > %0 = icmp sgt i32 %pmin.coerce1, %pmax.coerce1
    > ret { <2 x float>, float } zeroinitializer
    > }
    >
    > attributes #0 = { nounwind readnone ssp uwtable
"less-precise-fpmad"="false" "no-frame-pointer-elim"="true"
"no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false"
"no-nans-fp-math"="false" "stack-protector-buffer-size"="8"
"unsafe-fp-math"="false" "use-soft-float"="false" }
    >
    > !llvm.ident = !{!0}
    >
    > !0 = metadata !{metadata !"Apple LLVM version 6.0 (clang-600.0.57)
(based on LLVM 3.5svn)"}

The X86 code generation passes seems to eliminate it for the simple case
shown above. The generated assembly code is actually:

    > __Z18sampleNullOperator5PointS_: ## @_Z18sampleNullOperator5PointS_
    > .cfi_startproc
    > ## BB#0: ## %_ZN15SamplingClosureD1Ev.exit
    > push rbp
    > Ltmp0:
    > .cfi_def_cfa_offset 16
    > Ltmp1:
    > .cfi_offset rbp, -16
    > mov rbp, rsp
    > Ltmp2:
    > .cfi_def_cfa_register rbp
    > vxorps xmm0, xmm0, xmm0
    > vxorps xmm1, xmm1, xmm1
    > pop rbp
    > ret

I am wondering because I think that it might explain why the LLVM IR code
shown below does not get simplified to a single "ret { <2 x float>, float
} zeroinitializer" instruction. It seems to me that the nested loops have
no side-effects and are guaranteed to terminate in a finite amount of
time. Unless, the nested "icmp sgt" instructions cannot be eliminated.

Of course, in that case, the X86 code generation passes can no longer do
their magic...

    > ; ModuleID = 'lambda-opt.bc'
    > target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
    > target triple = "x86_64-apple-macosx10.10.0"
    >
    > ; Function Attrs: ssp uwtable
    > define { <2 x float>, float } @_Z18sampleNullOperator5PointS_(i64
    > %pmin.coerce0, i32 %pmin.coerce1, i64 %pmax.coerce0, i32
%pmax.coerce1) #0
    > {
    > %1 = icmp slt i32 %pmin.coerce1, %pmax.coerce1
    > br i1 %1, label %.lr.ph35.i, label %_ZN15SamplingClosureD1Ev.exit
    >
    > .lr.ph35.i: ; preds = %0
    > %2 = lshr i64 %pmin.coerce0, 32
    > %3 = trunc i64 %2 to i32
    > %4 = lshr i64 %pmax.coerce0, 32
    > %5 = trunc i64 %4 to i32
    > %6 = icmp slt i32 %3, %5
    > %7 = trunc i64 %pmin.coerce0 to i32
    > %8 = trunc i64 %pmax.coerce0 to i32
    > %9 = icmp slt i32 %7, %8
    > br i1 %6, label %.lr.ph23.us.i.preheader, label
    > %_ZN15SamplingClosureD1Ev.exit
    >
    > .lr.ph23.us.i.preheader: ; preds =
%.lr.ph35.i
    > %10 = trunc i64 %pmax.coerce0 to i32
    > %11 = trunc i64 %pmin.coerce0 to i32
    > %12 = sub i32 %10, %11
    > br label %.lr.ph23.us.i
    >
    > ._crit_edge24.us-lcssa.us57.i: ; preds = %14,
    > %.lr.ph23.us.i
    > %13 = add nsw i32 %z.028.us.i, 1
    > %exitcond66.i = icmp eq i32 %13, %pmax.coerce1
    > br i1 %exitcond66.i, label %_ZN15SamplingClosureD1Ev.exit, label
    > %.lr.ph23.us.i
    >
    > .lr.ph23.us.i: ; preds =
    > %._crit_edge24.us-lcssa.us57.i, %.lr.ph23.us.i.preheader
    > %z.028.us.i = phi i32 [ %13, %._crit_edge24.us-lcssa.us57.i ], [
    > %pmin.coerce1, %.lr.ph23.us.i.preheader ]
    > br i1 %9, label %.lr.ph.us.us.i, label
%._crit_edge24.us-lcssa.us57.i
    >
    > ; <label>:14 ; preds = %.noexc,
    > %middle.block
    > %15 = add nsw i32 %y.018.us.us.i, 1
    > %exitcond65.i = icmp eq i32 %15, %5
    > br i1 %exitcond65.i, label %._crit_edge24.us-lcssa.us57.i, label
    > %.lr.ph.us.us.i
    >
    > .lr.ph.us.us.i: ; preds = %14,
    > %.lr.ph23.us.i
    > %y.018.us.us.i = phi i32 [ %15, %14 ], [ %3, %.lr.ph23.us.i ]
    > %end.idx = add i32 %12, %7
    > %n.vec = and i32 %12, -128
    > %end.idx.rnd.down = add i32 %n.vec, %7
    > %cmp.zero = icmp eq i32 %n.vec, 0
    > br i1 %cmp.zero, label %middle.block, label %vector.body
    >
    > vector.body: ; preds =
%vector.body,
    > %.lr.ph.us.us.i
    > %index = phi i32 [ %index.next, %vector.body ], [ %7,
%.lr.ph.us.us.i ]
    > %index.next = add i32 %index, 128
    > %16 = icmp eq i32 %index.next, %end.idx.rnd.down
    > br i1 %16, label %middle.block, label %vector.body, !llvm.loop !1
    >
    > middle.block: ; preds =
%vector.body,
    > %.lr.ph.us.us.i
    > %resume.val = phi i32 [ %7, %.lr.ph.us.us.i ], [ %end.idx.rnd.down,
    > %vector.body ]
    > %cmp.n = icmp eq i32 %end.idx, %resume.val
    > br i1 %cmp.n, label %14, label %.noexc
    >
    > .noexc: ; preds = %.noexc,
    > %middle.block
    > %x.012.us.us.i = phi i32 [ %17, %.noexc ], [ %resume.val,
%middle.block ]
    > %17 = add nsw i32 %x.012.us.us.i, 1
    > %exitcond64.i = icmp eq i32 %17, %8
    > br i1 %exitcond64.i, label %14, label %.noexc, !llvm.loop !4
    >
    > _ZN15SamplingClosureD1Ev.exit: ; preds =
    > %._crit_edge24.us-lcssa.us57.i, %.lr.ph35.i, %0
    > ret { <2 x float>, float } zeroinitializer
    > }
    >
    > attributes #0 = { ssp uwtable "less-precise-fpmad"="false"
    > "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf"
    > "no-infs-fp-math"="false" "no-nans-fp-math"="false"
    > "stack-protector-buffer-size"="8" "unsafe-fp-math"="false"
    > "use-soft-float"="false" }
    >
    > !llvm.ident = !{!0}
    >
    > !0 = metadata !{metadata !"Apple LLVM version 6.0 (clang-600.0.57)
(based
    > on LLVM 3.5svn)"}
    > !1 = metadata !{metadata !1, metadata !2, metadata !3}
    > !2 = metadata !{metadata !"llvm.vectorizer.width", i32 1}
    > !3 = metadata !{metadata !"llvm.vectorizer.unroll", i32 1}
    > !4 = metadata !{metadata !4, metadata !2, metadata !3}

Thanks for you help,
Benoit

Benoit Belley
Sr Principal Developer
M&E-Product Development Group
MAIN +1 514 393 1616
DIRECT +1 438 448 6304
FAX +1 514 393 0110
Twitter <http://twitter.com/autodesk>
Facebook <https://www.facebook.com/Autodesk>
Autodesk, Inc.
10 Duke Street
Montreal, Quebec, Canada H3C 2L7
www.autodesk.com <http://www.autodesk.com/>

So, the first gets deleted with -dce because it’s trivially dead.

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.

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.

DCE is normally the backwards pass that fixes this.

You can make ADCE fix this particular case, even without control dependence, with a small change:

Right now it marks all terminators as alive.

It should mark all return’s as alive.
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).

That would make it mark the return as useful, then discover no other block has useful operations, and delete them all.

I’ve attached a mostly untested patch to do this.
It does what you want (It removes everything but the return)
It should work in all cases.
I ripped the erasure code from SCCP
It will crash because it doesn’t know what to do when it needs to redirect the entry block
SCCP doesn’t have this problem because it is only redirecting, not erasing, so the entry block always has a terminator to redirect.
(before, it crashed because it wanted to remove the entry block)

So this needs to be fixed.
I marked it with a TODO.
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.

adce.patch (5.04 KB)

Here’s a version that doesn’t try to do block deletion on it’s own. If you use -adce then -simplifycfg, you get what you want.
It passes all tests except one, which is that we delete an invoke of a pure function, IE Transforms/ADCE/dce_pure_invoke.ll -
I’m not sure why that’s bad.

The reason we delete it is because it returns false to I.mayHaveSideEffects(), and in particular, mayThrow returns false as well!

That seems really wrong if we expect it to stay around, so i’m actually okay with failing this case unless someone tells me why we shouldn’t.

(and why the right thing isn’t to make it return true to mayThrow)

adce2.patch (4.02 KB)

Note: this version is likely broken in other ways, because it replaces the unconditional terminators with unreachable, which may leave the function with no returns at all if it does it to the entry block.

I.E:

it will produce

; Function Attrs: readnone
declare i32 @strlen(i8*) #0

define i32 @test() {
unreachable

Cont: ; No predecessors!
ret i32 0

Other: ; No predecessors!
%exn = landingpad { i8*, i32 } personality i32 (…)* @__gxx_personality_v0
cleanup
ret i32 1
}

So i don’t know which is better to go with.

No, it’s some loop specific pass working backwards.
It’s probably still worth fixing ADCE though, since the fix is simple.

I’ve updated the change to work with invokes (after talking with nick, we don’t consider the control flow change to be a side effect).
I’ll test and submit it

350F40DB-4457-4455-A632-0DF05738AF15[6].png

Excellent!
Benoit

350F40DB-4457-4455-A632-0DF05738AF15[6].png