[LoopDeletion] Exploit undef Phi inputs when symbolically executing 1st iteration

[mkazantsev]

Summary

Follow-up on Roman's idea expressed in D103959.

• If a Phi has undefined inputs from live blocks:
  • and no other inputs, assume it is undef itself;
  • and exactly one non-undef input, we can assume that all undefs are equal to this input.

[mkazantsev]

Actually the 2nd part isn't true. Need rework.

[mkazantsev]

Fixed 2nd item

[mkazantsev]

Urgh, I double-checked with lang ref and my initial version was fine:

Branching on an undefined value is undefined behavior.

Rolling back to initial version.

[lebedev.ri]

Looks good to me, thank you.

In D104618#2829759, @mkazantsev wrote:

Urgh, I double-checked with lang ref and my initial version was fine:

Branching on an undefined value is undefined behavior.

Rolling back to initial version.

It is correct as per langref, but i'm not confident we currently
don't restrain ourselves about it in other places.

[aqjune]

Hi,
I'm afraid that fixes on br i1 undef are still ongoing. I have one GSoC student who will work on fixing them.
Currently the list of buggy transformations are tracked at https://llvm.org/pr46144 .
Would it be a good idea to mark only one of edges live (line 344) and leave comment at pr46144 about this?

[reames]

I would suggest splitting this into two patches. The "ignore undef input in phi" is safe, and commonly done across the optimizer. The "branch on undef" is tricky. Just from a risk management perspective, I think it makes sense to split them into separate changes.

If you want to split, you can consider this an LGTM for the "ignore undef input in phi" part, and then continue this review for the "branch on undef" part.

[mkazantsev]

I'm fine with splitting this in two parts, especially if br i1 undef is broken.

[mkazantsev]

Split out 1st part only.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

262

nit: they are equal

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll

744

It would be good to replace these br i1 undef by br i1 %c1 where %c1 is an arg, to avoid making the code UB.

[mkazantsev]

As yesterday, wings-down to give some time to underlying patch to fail. :)

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

262

Will fix

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll

744

Good point!

[lebedev.ri]

LGTM, thank you.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

for (auto *Succ : successors(BB))
       MarkLiveEdge(BB, Succ);
   };
 
   // Check if there is only one value coming from all live predecessor blocks.
   // Note that because we iterate in RPOT, we have already visited all its
   // (non-latch) predecessors.
   auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
     BasicBlock *BB = PN.getParent();
+    bool HasLivePreds = false;
+    (void)HasLivePreds;
     if (BB == Header)
       return PN.getIncomingValueForBlock(L->getLoopPredecessor());
     Value *OnlyInput = nullptr;
     for (auto *Pred : predecessors(BB))
       if (LiveEdges.count({ Pred, BB })) {
+        HasLivePreds = true;
         Value *Incoming = PN.getIncomingValueForBlock(Pred);
+        // Skip undefs. If they are present, we can assume they equal to the
+        // non-undef input.
+        if (isa<UndefValue>(Incoming))
+          continue;
         // Two inputs.
         if (OnlyInput && OnlyInput != Incoming)
           return nullptr;
         OnlyInput = Incoming;
       }
 
-    assert(OnlyInput && "No live predecessors?");
-    return OnlyInput;
+    assert(HasLivePreds && "No live predecessors?");
+    // If all incoming live value were undefs, return undef.
+    return OnlyInput ? OnlyInput : UndefValue::get(PN.getType());
   };
   DenseMap<Value *, Value *> FirstIterValue;
 
   // Use the following algorithm to prove we never take the latch on the 1st
   // iteration:
   // 1. Traverse in topological order, so that whenever we visit a block, all
   //    its predecessors are already visited.
   // 2. If we can prove that the block may have only 1 predecessor on the 1st
for (auto *BB : RPOT) {
     if (!LHS->getType()->isIntegerTy()) {
       MarkAllSuccessorsLive(BB);
       continue;
     }
 
     // Can we prove constant true or false for this condition?
     LHS = getValueOnFirstIteration(LHS, FirstIterValue, SQ);
     RHS = getValueOnFirstIteration(RHS, FirstIterValue, SQ);
-    auto *KnownCondition =
-        dyn_cast_or_null<ConstantInt>(SimplifyICmpInst(Pred, LHS, RHS, SQ));
+    auto *KnownCondition = SimplifyICmpInst(Pred, LHS, RHS, SQ);
     if (!KnownCondition) {
+      // Failed to simplify.
+      MarkAllSuccessorsLive(BB);
+      continue;
+    }
+    if (isa<UndefValue>(KnownCondition)) {
+      // If there is a non-loop successor, always assume this branch leaves the
+      // loop. Otherwise, arbitrarily take IfTrue.
+      if (L->contains(IfTrue) && L->contains(IfFalse))
+        MarkLiveEdge(BB, IfTrue);
+      continue;
+    }
+    auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
+    if (!ConstCondition) {
+      // Non-constant condition, cannot analyze any further.
       MarkAllSuccessorsLive(BB);
       continue;
     }
-    if (KnownCondition->isAllOnesValue())
+    if (ConstCondition->isAllOnesValue())
       MarkLiveEdge(BB, IfTrue);
     else
       MarkLiveEdge(BB, IfFalse);
   }
 
   // We can break the latch if it wasn't live.
   return !LiveEdges.count({ Latch, Header });
 }

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll

 done:                                             ; preds = %backedge
   %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
   ret i32 %sum.next.lcssa
 
 failure:
   unreachable
 }
 
-; TODO: We can break the backedge here by assuming that undef = sub.
 define i32 @test_multiple_pred_undef_1() {
 ; CHECK-LABEL: @test_multiple_pred_undef_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
 ; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
 ; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br i1 undef, label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
 ; CHECK:       if.true.1:
-; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br i1 undef, label [[IF_FALSE_1:%.*]], label [[IF_FALSE_2:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ [[SUB]], [[IF_TRUE_1]] ], [ undef, [[IF_TRUE_2]] ]
-; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
+; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
+; CHECK:       backedge.loop_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       done:
 ; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %loop

 done:                                             ; preds = %backedge
   %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
   ret i32 %sum.next.lcssa
 
 failure:
   unreachable
 }
 
-; TODO: We can break the backedge here by assuming that undef = sub.
 define i32 @test_multiple_pred_undef_2() {
 ; CHECK-LABEL: @test_multiple_pred_undef_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
 ; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
 ; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br i1 undef, label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
 ; CHECK:       if.true.1:
-; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br i1 undef, label [[IF_FALSE_1:%.*]], label [[IF_FALSE_2:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ undef, [[IF_TRUE_1]] ], [ [[SUB]], [[IF_TRUE_2]] ]
-; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
+; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
+; CHECK:       backedge.loop_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       done:
 ; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %loop

 done:                                             ; preds = %backedge
   %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
   ret i32 %sum.next.lcssa
 
 failure:
   unreachable
 }
 
-; TODO: We can break the backedge here by exploiting undef.
 define i32 @test_multiple_pred_undef_3() {
 ; CHECK-LABEL: @test_multiple_pred_undef_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
 ; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
 ; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br i1 undef, label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
 ; CHECK:       if.true.1:
-; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br i1 undef, label [[IF_FALSE_1:%.*]], label [[IF_FALSE_2:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ undef, [[IF_TRUE_1]] ], [ undef, [[IF_TRUE_2]] ]
-; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
+; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
+; CHECK:       backedge.loop_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       done:
 ; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %loop