[SCEV] By more careful when traversing phis in isImpliedViaMerge.

[fhahn]

Summary

I think currently isImpliedViaMerge can incorrectly return true for phis
in a loop/cycle, if the found condition involves the previous value of

Consider the case in exit_cond_depends_on_inner_loop.

At some point, we call (modulo simplifications)
isImpliedViaMerge(<=, %x.lcssa, -1, %call, -1).

The existing code tries to prove IncV <= -1 for all incoming values
InvV using the found condition (%call <= -1). At the moment this succeeds,
but only because it does not compare the same runtime value. The found
condition checks the value of the last iteration, but the incoming value
is from the *previous* iteration.

Hence we incorrectly determine that the *previous* value was <= -1,
which may not be true.

I think we need to be more careful when looking at the incoming values
here. In particular, we need to rule out that a found condition refers to
any value that may refer to one of the previous iterations. I'm not sure
there's a reliable way to do so (that also works of irreducible control
flow).

So for now this patch adds an additional requirement that the incoming
value must properly dominate the phi block. This should ensure the
values do not change in a cycle. I am not entirely sure if will catch
all cases and I appreciate a through second look in that regard.

Alternatively we could also unconditionally bail out in this case,
instead of checking the incoming values

[reames]

I'm confused.

On this example:
inner:

%x = phi i32 [ -1, %outer.header ], [ %call, %inner ]
%call = call i32 @match()
%inner.cond = icmp sgt i32 %call, -1
br i1 %inner.cond, label %inner, label %outer.exiting.1

outer.exiting.1:

%x.lcssa = phi i32 [ %x, %inner ]

The value of %x *is* always signed less than or equal to -1. On the last iteration, %call might not be, but the value used in the x.lcssa is the value of the phi, not of the call. Thus, concluding that %x.lcssa <=s -1 seems entirely correct?

[fhahn]

In D101829#2739843, @reames wrote:

I'm confused.

On this example:
inner:

%x = phi i32 [ -1, %outer.header ], [ %call, %inner ]
%call = call i32 @match()
%inner.cond = icmp sgt i32 %call, -1
br i1 %inner.cond, label %inner, label %outer.exiting.1

outer.exiting.1:

%x.lcssa = phi i32 [ %x, %inner ]

The value of %x *is* always signed less than or equal to -1. On the last iteration, %call might not be, but the value used in the x.lcssa is the value of the phi, not of the call. Thus, concluding that %x.lcssa <=s -1 seems entirely correct?

I might be glancing over something, but aren't we continuing the loop if %call >s -1 and exit if `call <=s -1?

So in the iteration before we exit, %call >s -1, hence %x >s -1 in the last iteration. In the last iteration, %call <=s -1, but %x still has the value from the previous iteration.

[reames]

In D101829#2739961, @fhahn wrote:

In D101829#2739843, @reames wrote:

I might be glancing over something, but aren't we continuing the loop if %call >s -1 and exit if `call <=s -1?

No, you're entirely correct. I'd swapped the branch order in my head when reading.

So in the iteration before we exit, %call >s -1, hence %x >s -1 in the last iteration. In the last iteration, %call <=s -1, but %x still has the value from the previous iteration.

There are two sub-cases here:

1. Exit on the first iteration - %x will be -1 (e.g. value on entry).
2. Exit on second or further iteration - %x will be >s -1. (e.g. value on backedge, last iteration value of call)

We can correctly conclude that x >=s -1, but not x >s -1. Which I think was your original point right? Sorry for the confusion.

[fhahn]

In D101829#2740003, @reames wrote:

In D101829#2739961, @fhahn wrote:

In D101829#2739843, @reames wrote:

I might be glancing over something, but aren't we continuing the loop if %call >s -1 and exit if `call <=s -1?

No, you're entirely correct. I'd swapped the branch order in my head when reading.

So in the iteration before we exit, %call >s -1, hence %x >s -1 in the last iteration. In the last iteration, %call <=s -1, but %x still has the value from the previous iteration.

There are two sub-cases here:

1. Exit on the first iteration - %x will be -1 (e.g. value on entry).
2. Exit on second or further iteration - %x will be >s -1. (e.g. value on backedge, last iteration value of call)

We can correctly conclude that x >=s -1, but not x >s -1. Which I think was your original point right? Sorry for the confusion.

Yes I think that matches my understanding of the issue. Plus we cannot conclude that x >s -1 is always false, which happens for the test case IIUC.

[nikic]

What BasicAA does for this case is a CFG reachability check from the phi to the value. If it's reachable, you have some kind of cycle. I think what you're doing here is fine though, as this doesn't seem like a terribly important optimization to me, and the nature of SCEV makes those properlyDominates() checks likely to succeed for common cases (as non-SCEVUnknown expressions are effectively hoisted).

[fhahn]

In D101829#2740317, @nikic wrote:

What BasicAA does for this case is a CFG reachability check from the phi to the value. If it's reachable, you have some kind of cycle. I think what you're doing here is fine though, as this doesn't seem like a terribly important optimization to me, and the nature of SCEV makes those properlyDominates() checks likely to succeed for common cases (as non-SCEVUnknown expressions are effectively hoisted).

I think we should start out with a relatively simple/safe fix and go from there. The impact of the code seems relatively small, e.g. if unconditionally bail out in this case, ~2 benchmarks out of SPEC2000/SPEC2006/MultiSource have minor binary changes.

[nikic]

I agree, so this LGTM.

[reames]

LGTM to me too for the record.

llvm/lib/Analysis/ScalarEvolution.cpp

if (RPhi && RPhi->getParent() == LBB) {
     // the predicate is true for (LHS, RHS) if it is true for all such pairs.
     // At this point RHS is either a non-Phi, or it is a Phi from some block
     // different from LBB.
     for (const BasicBlock *IncBB : predecessors(LBB)) {
       // Check that RHS is available in this block.
       if (!dominates(RHS, IncBB))
         return false;
       const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
+      // Make sure L does not refer to a value from a potentially previous
+      // iteration of a loop.
+      if (!properlyDominates(L, IncBB))
+        return false;
       if (!ProvedEasily(L, RHS))
         return false;
     }
   }
   return true;
 }
 
 bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,

llvm/test/Transforms/IRCE/decrementing-loop.ll

 
 out.of.bounds:
   ret void
 
 exit:
   ret void
 }
 
+; TODO: we need to be more careful when trying to look through phi nodes in
+; cycles, because the condition to prove may reference the previous value of
+; the phi. So we currently fail to optimize this case.
 ; Check that we can figure out that IV is non-negative via implication through
 ; two Phi nodes, one being AddRec.
 define void @test_05(i32* %a, i32* %a_len_ptr, i1 %cond) {
 
 ; CHECK-LABEL: test_05
-; CHECK:       mainloop:
-; CHECK-NEXT:    br label %loop
-; CHECK:       loop:
-; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
-; CHECK:       loop.preloop:
+; CHECK: entry:
+; CHECK:   br label %merge
+; CHECK-NOT: mainloop
 
  entry:
   %len.a = load i32, i32* %a_len_ptr, !range !0
   %len.minus.one = sub nsw i32 %len.a, 1
   %len.plus.one = add nsw i32 %len.a, 1
   %len.minus.two = sub nsw i32 %len.a, 2
   br label %merge
 

llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll

 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[X:%.*]] = phi i32 [ -1, [[OUTER_HEADER]] ], [ [[CALL:%.*]], [[INNER]] ]
 ; CHECK-NEXT:    [[CALL]] = call i32 @match()
 ; CHECK-NEXT:    [[INNER_COND:%.*]] = icmp sgt i32 [[CALL]], -1
 ; CHECK-NEXT:    br i1 [[INNER_COND]], label [[INNER]], label [[OUTER_EXITING_1:%.*]]
 ; CHECK:       outer.exiting.1:
 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X]], [[INNER]] ]
-; CHECK-NEXT:    br i1 false, label [[EXIT:%.*]], label [[OUTER_LATCH]]
+; CHECK-NEXT:    [[OUTER_COND_1:%.*]] = icmp sgt i32 [[X_LCSSA]], -1
+; CHECK-NEXT:    br i1 [[OUTER_COND_1]], label [[EXIT:%.*]], label [[OUTER_LATCH]]
 ; CHECK:       outer.latch:
 ; CHECK-NEXT:    [[IV_OUTER_NEXT]] = add nuw nsw i32 [[IV_OUTER]], 1
 ; CHECK-NEXT:    [[OUTER_COND_2:%.*]] = icmp ult i32 [[IV_OUTER]], 100
 ; CHECK-NEXT:    br i1 [[OUTER_COND_2]], label [[OUTER_HEADER]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[X_RES:%.*]] = phi i32 [ [[X_LCSSA]], [[OUTER_EXITING_1]] ], [ -1, [[OUTER_LATCH]] ]
 ; CHECK-NEXT:    ret i32 [[X_RES]]
 ;