[SImplifyCFG] Preserve knowledge about guarding condition by adding assume

[dbakunevich]

Summary

This improvement aims to add "assume" after removing "undefined behavior" from "phinode" to improve optimization.

This code that I changed initially just removed the edge from the parent block that came in phinode with undefined behavior. Since the code simply removed the edge, there was no information left in the parent block under what condition the transition from the previous block to the current one was made.

pred:
  x = ...
  cond = x > 10
  br cond, bb, other.succ

bb:
  phi [nullptr, pred], ... // other possible preds
  load(phi) // UB if we came from pred

other.succ:
  // here we know that x <= 10, but this knowledge is lost
  // after the branch is turned to unconditional unless we
  // preserve it with assume.

[mkazantsev]

Please make the description more informative.

For patch name, I'd suggest something like "[SImplifyCFG] Preserve knowledge about guarding condition by adding assume".

The description is also confusing. I think what you are aiming would be

pred:
  x = ...
  cond = x > 10
  br cond, bb, other.succ

bb:
  phi [nullptr, pred], ... // other possible preds
  load(phi) // UB if we came from pred

other.succ:
  // here we know that x <= 10, but this knowledge is lost
  // after the branch is turned to unconditional unless we
  // preserve it with assume.

[mkazantsev]

I'm OK with the code change, but please add some informative description on what this patch is about.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6602

You can also add a comment on why is that made.

[mkazantsev]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6601–6608

Do you mean "guarding condition", "assume" instea of "protection state" and "guess"?

[mkazantsev]

LGTM with a nit. Let's hold it for couple more days in case if someone has comments on it.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6604

Move the comment here; I'd simply say "Preserve knowledge about guarding condition by adding an assume because it might not be inferrable anymore".

[lebedev.ri]

In general, i wonder if we should always be doing such a thing in situations like this.
There's potential the increase in block sizes will result in some other optimizations starting to fail.

[xbolva00]

In D109054#2986001, @lebedev.ri wrote:

In general, i wonder if we should always be doing such a thing in situations like this.
There's potential the increase in block sizes will result in some other optimizations starting to fail.

They should ignore such assumes anyway.

[mkazantsev]

In D109054#2986001, @lebedev.ri wrote:

In general, i wonder if we should always be doing such a thing in situations like this.
There's potential the increase in block sizes will result in some other optimizations starting to fail.

If the removed condition is implied by another dominating condition, then we should theoretically still have all facts even after removal. It does not mean every pass *will* be able to infer it, but they *could*. But in this case, the removed condition might not be inferrable, because it is deleted based on something which is not (directly) related to it. So it makes sense to leave the assume in place.

As for the size -- assumed conditions should hopefully be ignored by costs models. If not, it's a bug in those cost models.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i)
         Instruction *T = Predecessor->getTerminator();
         IRBuilder<> Builder(T);
         if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
           BB->removePredecessor(Predecessor);
           // Turn uncoditional branches into unreachables and remove the dead
           // destination from conditional branches.
           if (BI->isUnconditional())
             Builder.CreateUnreachable();
+          else {
+            // Preserve guarding condition in assume, because it might not be
+            // inferrable from any dominating condition.
+            Value *Cond = BI->getCondition();
+            if (BI->getSuccessor(0) == BB)
+              Builder.CreateAssumption(Builder.CreateNot(Cond));
             else
+              Builder.CreateAssumption(Cond);
             Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1)
                                                        : BI->getSuccessor(0));
+          }
           BI->eraseFromParent();
           if (DTU)
             DTU->applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
           return true;
         }
         // TODO: SwitchInst.
       }
 

llvm/test/Transforms/SimplifyCFG/tautological-conditional-branch.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
 
 %0 = type { %1*, %2* }
 %1 = type { %0* }
 %2 = type { %0*, %2* }
 
 define void @eggs(i1 %arg, i1 %arg16, %0* %arg17, %0* %arg18, %0* %arg19) {
 ; CHECK-LABEL: @eggs(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br i1 [[ARG:%.*]], label [[BB20:%.*]], label [[BB21:%.*]]
 ; CHECK:       bb20:
 ; CHECK-NEXT:    call void @wombat()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb21:
 ; CHECK-NEXT:    [[I:%.*]] = icmp eq %0* [[ARG17:%.*]], null
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[I]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    call void @hoge()
-; CHECK-NEXT:    [[I27:%.*]] = getelementptr inbounds [[TMP0:%.*]], %0* [[ARG19:%.*]], i64 0, i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[ARG16:%.*]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP1]])
+; CHECK-NEXT:    [[I27:%.*]] = getelementptr inbounds [[TMP0]], %0* [[ARG19:%.*]], i64 0, i32 0
 ; CHECK-NEXT:    [[I28:%.*]] = load %1*, %1** [[I27]], align 8
 ; CHECK-NEXT:    call void @pluto.1(%1* [[I28]])
 ; CHECK-NEXT:    call void @pluto()
 ; CHECK-NEXT:    ret void
 ;
 bb:
   br i1 %arg, label %bb20, label %bb21