llvm dev - Sep 2014 - [LLVMdev] Loops Prevent Function Pointer Inlining?

I've CC'ed Chad Rosier as I think this behaviour is a side-effect of
his revert of IndVarSimplify.cpp (git
c6b1a7e577a0b9e9cff9f9b7ac35a2cde7c448d8, SVN 217962). The change
basically makes the IndVar pass change:

; <label>:4                                       ; preds = %6, %0
  %i.0 = phi i32 [ 0, %0 ], [ %11, %6 ]
  %5 = icmp eq i32 %i.0, 0
  br i1 %5, label %6, label %17

To:

; <label>:4                                       ; preds = %7, %0
  %indvars.iv = phi i64 [ %indvars.iv.next, %7 ], [ 0, %0 ]
  %5 = trunc i64 %indvars.iv to i32
  %6 = icmp eq i32 %5, 0
  br i1 %6, label %7, label %15

Whereas before the patch it would be:

; <label>:4                                       ; preds = %7, %0
  %indvars.iv = phi i64 [ %indvars.iv.next, %7 ], [ 0, %0 ]
  %5 = icmp eq i64 %indvars.iv, 0
  br i1 %5, label %6, label %15

This has a knock-on effect on the GVN pass; in the basic block that is
the body of the loop it only knows that "trunc i64 %indvars.iv to i32"
is zero, not that "%indvars.iv" is zero, so it can't convert the
"add
i64 %indvars.iv, 1" to a constant 1, and so doesn't realise the body
of the loop is only ever executed once.

I'll keep digging...

Thanks,

Nick

On 25 September 2014 00:11, Nicholas White <n.j.white at gmail.com>
wrote:
> ; <label>:4                                       ; preds = %7, %0
>   %indvars.iv = phi i64 [ %indvars.iv.next, %7 ], [ 0, %0 ]
>   %5 = trunc i64 %indvars.iv to i32
>   %6 = icmp eq i32 %5, 0
>   br i1 %6, label %7, label %15
Oh, I remember similar effects of truncate in the vectorizer. We
discussed a bit about that for other cases, maybe you can find it in
the list (probably end of last year, beginning of this year). I don't
remember the outcome, though. :(

--renato

Nick,
The work done in r217953 was to widen the loop compare to eliminate the
trunc from in between the induction variable and the compare.  The result
is that this enables LSR to consider more cases (i.e., LSR doesn't play
nice with the trunc).

So the code prior to r217953 looked like this:

  %indvars.iv = phi i64 [ %indvars.iv.next, %7 ], [ 0, %0 ]
  %5 = trunc i64 %indvars.iv to i32
  %6 = icmp eq i32 %5, 0
  br i1 %6, label %7, label %15

After my commit the compare was widened:

  %indvars.iv = phi i64 [ %indvars.iv.next, %7 ], [ 0, %0 ]
  %5 = icmp eq i64 %indvars.iv, 0
  br i1 %5, label %6, label %15

but then I realized the unsigned comparison wasn't handled correctly, so I
made a partial revert in r217962.

I'm currently working on the unsigned solution.  As I pointed out in a
previous email, I'm pretty sure this is safe if the induction variable
steps by unit 1.  Hopefully, I'll have to committed shortly.

I still don't follow your point (I'm not a GVN expert by any means), but
I
do hope this helps.  If you have any more questions, please let me know.

 Chad
> I've CC'ed Chad Rosier as I think this behaviour is a side-effect
of
> his revert of IndVarSimplify.cpp (git
> c6b1a7e577a0b9e9cff9f9b7ac35a2cde7c448d8, SVN 217962).
> The change basically makes the IndVar pass change:
>
> ; <label>:4                                       ; preds = %6, %0
>   %i.0 = phi i32 [ 0, %0 ], [ %11, %6 ]
>   %5 = icmp eq i32 %i.0, 0
>   br i1 %5, label %6, label %17
>
> To:
>
> ; <label>:4                                       ; preds = %7, %0
>   %indvars.iv = phi i64 [ %indvars.iv.next, %7 ], [ 0, %0 ]
>   %5 = trunc i64 %indvars.iv to i32
>   %6 = icmp eq i32 %5, 0
>   br i1 %6, label %7, label %15
>
> Whereas before the patch it would be:
>
> ; <label>:4                                       ; preds = %7, %0
>   %indvars.iv = phi i64 [ %indvars.iv.next, %7 ], [ 0, %0 ]
>   %5 = icmp eq i64 %indvars.iv, 0
>   br i1 %5, label %6, label %15
>
> This has a knock-on effect on the GVN pass; in the basic block that is
> the body of the loop it only knows that "trunc i64 %indvars.iv to
i32"
> is zero, not that "%indvars.iv" is zero, so it can't convert
the "add
> i64 %indvars.iv, 1" to a constant 1, and so doesn't realise the
body
> of the loop is only ever executed once.
>
> I'll keep digging...
>
> Thanks,
>
> Nick
>

Thanks - that does help. I didn't realise the earlier code put the
`trunc` in too - that's what's preventing the GVN pass from removing
the loop entirely. I'm looking forward to your unsigned patch - then
the generated IR for my example will be much better :)