Fix invalid test in Guard Widening

[mkazantsev]

Summary

One of Guard Widening tests is not checking what it is supposed to check and
is based on flaky logic. Guard widening algorithm relies on PDT. The outer loop
is infinite, therefore no post-domination tree exists. According to the algorithm,
we should only widen if there is post-domination between two guards. This test is
based on two flaky facts regarding the PDT:

• PDT must choose the furthest block as its non-trivial root for infinite loops;
• PDT must know nothing about implicit control flow of guards.

When the guards are turned into equivalent form of widenable branches, both these
facts break and widening becomes illegal. So it makes sense to fix the test to make
it more robust.

This patch alters the test so that it checks what it is supposed to check. Now it
has 2 loops and checks the widening scenario described in the comment.

[reames]

I disagree w/your analysis of what the test does and is supposed to do. Please review the existing check lines, they're inconsistent with your claims.

[mkazantsev]

Sorry, I do not understand your objection's meaning. The test's comment states that

; With guards in loops, we're okay hoisting out the guard into the
; containing loop.

The checks actually check that we widen a guard from block outer (which is a latch of outer loop) into inner loop inner.

In GenericDomTreeConstruction.h, there is a comment:

// Find the furthest away we can get by following successors, then
// follow them in reverse.  This gives us some reasonable answer about
// the post-dom tree inside any infinite loop. In particular, it
// guarantees we get to the farthest away point along *some*
// path. This also matches the GCC's behavior.
// If we really wanted a totally complete picture of dominance inside
// this infinite loop, we could do it with SCC-like algorithms to find
// the lowest and highest points in the infinite loop.  In theory, it
// would be nice to give the canonical backedge for the loop, but it's
// expensive and does not always lead to a minimal set of roots.

So when we are trying to construct PDT for infinite loop, we choose *some* block
as its non-trivial root. No guarantee is given that this block is going to be block outer.
I don't remember what was this situation, but there was a case where inner was chosen
a root, and therefore no post-dominance between them was inserted.

Could you please elaborate what exactly are you disagree with?

[mkazantsev]

I don't remember what was this situation, but there was a case where inner was chosen a root

I've refreshed it in my mind now. The current algorithm of choise of non-trivial root will choose outer as the furthermost block. And therefore the 2nd guard will post-dominate the 1st one. If we turn the guards into a form of widenable branches, it will look like:

inner:
  br guaded1, deopt1
guarded1:
  br inner, outer
outer:
  br guarded2, deopt2
guarded2: 
  br inner

This graph has a trivial root deopt2. Now block outer does not post-dominate block inner because inner has a branch to deopt1. So we can no longer widen.

So in fact, this test is only checking fact that PDT *happens* to choose furthest block as its non-trivial root and *happens* to ignore the implicit control flow of guards. Both these facts may in theory change. So maybe UB was a too harsh word here, but the fact that we can do widening here stands on two highly fragile facts.

[mkazantsev]

I agree that my initial assessment that it was a single loops with 2 latches was wrong. We can interpret it as 2 loops, where inner is an inner loop, outer is an outer loop and outer loop's header is created after loop canonicalization. However, even in this case, checks check that we widen the condition of guard from outer loop *into* inner loop, while the comment claims opposite.

[reames]

Max and I ended up discussing this offline. Our conclusion:

1. There's a cornercase around PDT and infinite loops which needs tested.
2. The existing test is named as if it was intended to cover that case, but instead covers a separate interesting case.
3. Max is going to rename this test, and add another one to cover the PDT cornercase.

Max, provided your change only adds the new test case, you can consider that LGTM. If there are any changes to existing test cases (beyond the function rename) or code, please post for review. Please make sure to include a comment in the new test about the infinite loop cornercase and why it arises.

test/Transforms/GuardWidening/basic.ll

; CHECK:  ret void
   ret void
 }
 
 ; With guards in loops, we're okay hoisting out the guard into the
 ; containing loop.
 define void @f_11(i32 %a, i1 %cond_0, i1 %cond_1) {
 ; CHECK-LABEL: @f_11(
 entry:
-  br label %inner
+  br label %outer_header
 
-inner:
-; CHECK: inner:
-; CHECK:  %wide.chk = and i1 %cond_0, %cond_1
-; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
-; CHECK:  br i1 undef, label %inner, label %outer
+outer_header:
+; CHECK:      outer_header:
+; CHECK-NEXT:   %wide.chk = and i1 %cond_0, %cond_1
+; CHECK-NEXT:   call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
 
   call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
-  br i1 undef, label %inner, label %outer
+  br label %inner
 
-outer:
+inner:
   call void(i1, ...) @llvm.experimental.guard(i1 %cond_1) [ "deopt"() ]
-  br label %inner
+  br i1 undef, label %inner, label %outer_latch
+
+outer_latch:
+  br i1 undef, label %outer_header, label %exit
+
+exit:
+  ret void
 }
 
 ; Checks that we are adequately guarded against exponential-time
 ; behavior when hoisting code.
 define void @f_12(i32 %a0) {
 ; CHECK-LABEL: @f_12
 
 ; Eliding the earlier 29 multiplications for brevity