[SimplifyCFG] Simplify based on a dominating condition (looking past hammocks and diamonds).

[mcrosier]

Summary

This patch extends the support for simplifying the CFG based on a dominating condition. The search threshold is increased from 1 to 3. In turn, a new function is added to IR BasicBlock, getIDom(), that looks past hammocks and diamonds. I suspect this new function might be useful in other scenarios.

No correctness issues or compile-time regressions above noise for llvmts, SPEC2000, SPEC2006, SPEC2017. This results in a small code size reduction in some cases and hits about 1/3 of the SPEC benchmarks and a few tests from the llvmts.

Chad

[efriedma]

We already have a couple other passes which can do optimize your testcase (JumpThreading and GVN); what do we gain from doing this analysis here specifically?

[• dberlin]

EarlyCSE should be able to do this as well, and PredicateInfo will build a form that makes this trivial for anything to do it, in linear time, without any limits necessary.
(By numbers, predicateinfo was the fastest analysis we had that walked the IR at the time it was committed, so ...)

[mcrosier]

Eli and Danny have (rightfully) convinced me this has little/no merit. However, this is a derivative of some other work I've been doing with the inline cost model and I think both of your inputs would be very valuable. Please see: http://lists.llvm.org/pipermail/llvm-dev/2017-August/116183.html

[mcrosier]

In D36287#831132, @efriedma wrote:

We already have a couple other passes which can do optimize your testcase (JumpThreading and GVN); what do we gain from doing this analysis here specifically?

Just to follow up on your question, Eli. I suspect the fact that SimplifyCFG runs more frequently than JT and GVN result in a few additional cases being captured (perhaps cases exposed after JT/GVN). However, I honestly haven't done the full investigation to get a definitive answer. Again, this is just derivative work and I'm not particularly set on getting this committed.

include/llvm/Analysis/ValueTracking.h

matchSelectPattern(const Value *V, const Value *&LHS, const Value *&RHS,
     Value *L = const_cast<Value*>(LHS);
     Value *R = const_cast<Value*>(RHS);
     auto Result = matchSelectPattern(const_cast<Value*>(V), L, R);
     LHS = L;
     RHS = R;
     return Result;
   }
 
+  /// Find all of the conditions that dominate BB up to a max search depth of \p
+  /// Limit.
+  bool
+  findDominatingConditions(const BasicBlock *BB,
+                           SmallVectorImpl<std::pair<Value *, bool>> &DomConds,
+                           unsigned Limit = 1);
+
   /// Return true if RHS is known to be implied true by LHS.  Return false if
   /// RHS is known to be implied false by LHS.  Otherwise, return None if no
   /// implication can be made.
   /// A & B must be i1 (boolean) values or a vector of such values. Note that
   /// the truth table for implication is the same as <=u on i1 values (but not
   /// <=s!).  The truth table for both is:
   ///    | T | F (B)
   ///  T | T | F
   ///  F | T | T
   /// (A)
   Optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
                                     const DataLayout &DL, bool LHSIsTrue = true,
                                     unsigned Depth = 0);
 } // end namespace llvm
 
 #endif

include/llvm/IR/BasicBlock.h

public:
   /// multiple edges from the unique predecessor to this block (for example a
   /// switch statement with multiple cases having the same destination).
   const BasicBlock *getUniquePredecessor() const;
   BasicBlock *getUniquePredecessor() {
     return const_cast<BasicBlock *>(
                  static_cast<const BasicBlock *>(this)->getUniquePredecessor());
   }
 
+  /// \brief Return the immediate dominator of this block.  Otherwise return a
+  /// null pointer.  Unlike getSinglePredecessor this function is able to walk
+  /// past if-then (hammocks) and if-then-else (diamond) statements.
+  const BasicBlock *getIDom() const;
+  BasicBlock *getIDom() {
+    return const_cast<BasicBlock *>(
+        static_cast<const BasicBlock *>(this)->getIDom());
+  }
+
   /// \brief Return the successor of this block if it has a single successor.
   /// Otherwise return a null pointer.
   ///
   /// This method is analogous to getSinglePredecessor above.
   const BasicBlock *getSingleSuccessor() const;
   BasicBlock *getSingleSuccessor() {
     return const_cast<BasicBlock *>(
                    static_cast<const BasicBlock *>(this)->getSingleSuccessor());

lib/Analysis/ValueTracking.cpp

if (Value *C = lookThroughCast(CmpI, FalseVal, TrueVal, CastOp))
       return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
                                   C, cast<CastInst>(FalseVal)->getOperand(0),
                                   LHS, RHS);
   }
   return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS, TrueVal, FalseVal,
                               LHS, RHS);
 }
 
+bool llvm::findDominatingConditions(
+    const BasicBlock *BB, SmallVectorImpl<std::pair<Value *, bool>> &DomConds,
+    unsigned Limit) {
+  assert(DomConds.empty() && "Expected an empty vector!");
+
+  unsigned Iter = 0;
+  const BasicBlock *CurrentBB = BB;
+  const BasicBlock *CurrentIDom = BB->getIDom();
+  while (CurrentIDom && Iter++ < Limit) {
+    if (CurrentIDom == CurrentBB->getSinglePredecessor()) {
+      auto *DomBI = dyn_cast<BranchInst>(CurrentIDom->getTerminator());
+      if (DomBI && DomBI->isConditional()) {
+        assert((DomBI->getSuccessor(0) == CurrentBB ||
+                DomBI->getSuccessor(1) == CurrentBB) &&
+               "Unexpected CFG!");
+        Value *Condition = DomBI->getCondition();
+        bool TrueDest = DomBI->getSuccessor(0) == CurrentBB;
+        DomConds.push_back(std::make_pair(Condition, TrueDest));
+      }
+    }
+    CurrentBB = CurrentIDom;
+    CurrentIDom = CurrentBB->getIDom();
+  }
+  return !DomConds.empty();
+}
+
 /// Return true if "icmp Pred LHS RHS" is always true.
 static bool isTruePredicate(CmpInst::Predicate Pred, const Value *LHS,
                             const Value *RHS, const DataLayout &DL,
                             unsigned Depth) {
   assert(!LHS->getType()->isVectorTy() && "TODO: extend to handle vectors!");
   if (ICmpInst::isTrueWhenEqual(Pred) && LHS == RHS)
     return true;
 

lib/IR/BasicBlock.cpp

for (;PI != E; ++PI) {
     if (*PI != PredBB)
       return nullptr;
     // The same predecessor appears multiple times in the predecessor list.
     // This is OK.
   }
   return PredBB;
 }
 
+const BasicBlock *BasicBlock::getIDom() const {
+  const BasicBlock *CurrentPred = this->getSinglePredecessor();
+  if (CurrentPred)
+    return CurrentPred;
+
+  const_pred_iterator PII = pred_begin(this);
+  const_pred_iterator E = pred_end(this);
+  // No predecessors.
+  if (PII == E)
+    return nullptr;
+
+  unsigned NumPreds = std::distance(PII, E);
+  if (NumPreds != 2)
+    return nullptr;
+
+  const BasicBlock *PredA = *PII++;
+  const BasicBlock *PredB = *PII;
+  const BasicBlock *PredADom = PredA->getSinglePredecessor();
+  const BasicBlock *PredBDom = PredB->getSinglePredecessor();
+  // Look through hammocks.
+  if (PredADom && PredADom == PredB)
+    return PredB;
+  if (PredBDom && PredBDom == PredA)
+    return PredA;
+  // Look through diamonds.
+  if (PredADom && PredADom == PredBDom)
+    return PredADom;
+  return nullptr;
+}
+
 const BasicBlock *BasicBlock::getSingleSuccessor() const {
   succ_const_iterator SI = succ_begin(this), E = succ_end(this);
   if (SI == E) return nullptr; // no successors
   const BasicBlock *TheSucc = *SI;
   ++SI;
   return (SI == E) ? TheSucc : nullptr /* multiple successors */;
 }
 

lib/Transforms/Utils/SimplifyCFG.cpp

static cl::opt<bool> SpeculateOneExpensiveInst(
     cl::desc("Allow exactly one expensive instruction to be speculatively "
              "executed"));
 
 static cl::opt<unsigned> MaxSpeculationDepth(
     "max-speculation-depth", cl::Hidden, cl::init(10),
     cl::desc("Limit maximum recursion depth when calculating costs of "
              "speculatively executed instructions"));
 
+static cl::opt<unsigned> ImplicationSearchThreshold(
+    "simplifycfg-implication-search-threshold",
+    cl::desc("The number of predecessors to search for a stronger condition "
+             "used to simplify a weaker condition"),
+    cl::init(3), cl::Hidden);
+
 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
 STATISTIC(NumLinearMaps,
           "Number of switch instructions turned into linear mapping");
 STATISTIC(NumLookupTables,
           "Number of switch instructions turned into lookup tables");
 STATISTIC(
     NumLookupTablesHoles,
     "Number of switch instructions turned into lookup tables (holes checked)");
if (&*I == BI) {
         return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
     }
   }
 
   // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction.
   if (SimplifyBranchOnICmpChain(BI, Builder, DL))
     return true;
 
-  // If this basic block has a single dominating predecessor block and the
-  // dominating block's condition implies BI's condition, we know the direction
-  // of the BI branch.
-  if (BasicBlock *Dom = BB->getSinglePredecessor()) {
-    auto *PBI = dyn_cast_or_null<BranchInst>(Dom->getTerminator());
-    if (PBI && PBI->isConditional() &&
-        PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
-      assert(PBI->getSuccessor(0) == BB || PBI->getSuccessor(1) == BB);
-      bool CondIsTrue = PBI->getSuccessor(0) == BB;
-      Optional<bool> Implication = isImpliedCondition(
-          PBI->getCondition(), BI->getCondition(), DL, CondIsTrue);
+  // If this basic block has a dominating condition that implies BI's condition,
+  // we know the direction of the BI branch.
+  unsigned Limit = ImplicationSearchThreshold;
+  SmallVector<std::pair<Value *, bool>, 3> DomConds;
+  if (findDominatingConditions(BB, DomConds, Limit)) {
+    Value *Cond = BI->getCondition();
+    auto &DL = BB->getModule()->getDataLayout();
+    for (unsigned i = 0, e = DomConds.size(); i != e; ++i) {
+      Optional<bool> Implication =
+        isImpliedCondition(DomConds[i].first, Cond, DL, DomConds[i].second);
       if (Implication) {
         // Turn this into a branch on constant.
-        auto *OldCond = BI->getCondition();
         ConstantInt *CI = *Implication
-                              ? ConstantInt::getTrue(BB->getContext())
-                              : ConstantInt::getFalse(BB->getContext());
         BI->setCondition(CI);
-        RecursivelyDeleteTriviallyDeadInstructions(OldCond);
+        RecursivelyDeleteTriviallyDeadInstructions(Cond);
         return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
       }
     }
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.

test/CodeGen/AArch64/addsub.ll

 }
 
 define void @testing() {
 ; CHECK-LABEL: testing:
   %val = load i32, i32* @var_i32
   %val2 = load i32, i32* @var2_i32
 
 ; CHECK: cmp {{w[0-9]+}}, #4095
-; CHECK: b.ne [[RET:.?LBB[0-9]+_[0-9]+]]
-  %cmp_pos_small = icmp ne i32 %val, 4095
+; CHECK: b.eq [[RET:.?LBB[0-9]+_[0-9]+]]
+  %cmp_pos_small = icmp eq i32 %val, 4095
   br i1 %cmp_pos_small, label %ret, label %test2
 
 test2:
 ; CHECK: cmp {{w[0-9]+}}, {{#3567, lsl #12|#14610432}}
 ; CHECK: b.lo [[RET]]
   %newval2 = add i32 %val, 1
   store i32 %newval2, i32* @var_i32
   %cmp_pos_big = icmp ult i32 %val2, 14610432

test/CodeGen/AArch64/arm64-andCmpBrToTBZ.ll

 
 if.then3:                                         ; preds = %_ZNK7WebCore4Node10hasTagNameERKNS_13QualifiedNameE.exit, %land.rhs.i
   %tmp11 = load i8, i8* %str14, align 8
   %tmp12 = and i8 %tmp11, 2
   %tmp13 = icmp ne i8 %tmp12, 0
   br label %return
 
 if.end5:                                          ; preds = %_ZNK7WebCore4Node10hasTagNameERKNS_13QualifiedNameE.exit, %lor.rhs.i.i.i
-; CHECK: %if.end5
-; CHECK: tbz
   br i1 %tobool.i.i.i, label %if.end12, label %land.rhs.i19, !prof !1
 
+; The above conditional branch gets simplified based on the dominating condition in if.end
+; CHECK-NOT: tbz
+; CHECK: %land.rhs.i19
+
 land.rhs.i19:                                     ; preds = %if.end5
   %cmp.i.i.i18 = icmp eq i8* %str6, %str7
   br i1 %cmp.i.i.i18, label %if.then7, label %lor.rhs.i.i.i23
 
 lor.rhs.i.i.i23:                                  ; preds = %land.rhs.i19
   %cmp.i13.i.i.i22 = icmp eq i8* %str3, %str4
   br i1 %cmp.i13.i.i.i22, label %_ZNK7WebCore4Node10hasTagNameERKNS_13QualifiedNameE.exit28, label %if.end12
 

test/Transforms/SimplifyCFG/implied-cond-hammock-diamond.ll

+; RUN: opt %s -S -simplifycfg | FileCheck %s
+
+; Check that we can simplify a condition in if.then3 based on the branch
+; condition of entry.  This check to make sure we can traverse past the if.then
+; block.
+; CHECK-LABEL: @test1(
+define void @test1(i32 %a, i32 %b, i32 %c, i32* %arr) {
+entry:
+  %tobool = icmp ne i32 %a, 0
+  %tobool1 = icmp ne i32 %b, 0
+  %cond = and i1 %tobool, %tobool1
+  br i1 %cond, label %if.then, label %if.end9
+
+if.then:
+  store i32 %a, i32* %arr, align 4
+  %tobool2 = icmp eq i32 %c, 0
+  br i1 %tobool2, label %if.end9, label %if.then3
+
+if.then3:
+  %arrayidx2 = getelementptr inbounds i32, i32* %arr, i64 2
+  store i32 %c, i32* %arrayidx2, align 4
+  br i1 %tobool1, label %if.then6, label %if.end9 ; <-- Simplifies to br label %if.then6
+
+; CHECK: if.then3:
+; CHECK: br label %if.end9
+; CHECK-NOT: if.then6:
+
+if.then6:
+  %arrayidx1 = getelementptr inbounds i32, i32* %arr, i64 1
+  store i32 %b, i32* %arrayidx1, align 4
+  br label %if.end9
+
+if.end9:
+  ret void
+}
+
+; Check to make sure we can look through an if-then (hammock).
+; CHECK-LABEL: @test2(
+define void @test2(i32 %a, i32 %b, i32 %c, i32* %arr) {
+entry:
+  %tobool = icmp ne i32 %a, 0
+  %tobool1 = icmp ne i32 %b, 0
+  %or.cond = and i1 %tobool, %tobool1
+  br i1 %or.cond, label %if.then, label %if.end9
+
+if.then:
+  store i32 %a, i32* %arr, align 4
+  %tobool2 = icmp eq i32 %c, 0
+  br i1 %tobool2, label %if.end, label %if.then3
+  
+; CHECK: if.then:
+; CHECK: br i1 %tobool2, label %if.then6, label %if.then3
+
+if.then3:
+  %arrayidx4 = getelementptr inbounds i32, i32* %arr, i64 2
+  store i32 %c, i32* %arrayidx4, align 4
+  br label %if.end
+
+; CHECK: if.then3:
+; CHECK: br label %if.then6
+
+if.end:
+  br i1 %tobool1, label %if.then6, label %if.end9 ; <- Simplifies to br label %if.then6
+
+; CHECK-NOT: if.end:
+; CHECK-NOT: br i1 %tobool1, label %if.then6, label %if.end9
+
+if.then6:
+  %arrayidx7 = getelementptr inbounds i32, i32* %arr, i64 1
+  store i32 %b, i32* %arrayidx7, align 4
+  br label %if.end9
+
+if.end9:                                          ; preds = %if.end, %if.then6, %entry
+  ret void
+}
+
+; Check to make sure we can look through an if-then-else (diamond).
+; CHECK-LABEL: @test3(
+define void @test3(i32 %a, i32 %b, i32 %c, i32* %arr) local_unnamed_addr #0 {
+entry:
+  %tobool = icmp ne i32 %a, 0
+  %tobool1 = icmp ne i32 %b, 0
+  %or.cond = and i1 %tobool, %tobool1
+  br i1 %or.cond, label %if.then, label %if.end7
+
+if.then:
+  %tobool2 = icmp eq i32 %c, 0
+  br i1 %tobool2, label %if.else, label %if.then3
+
+if.then3:
+  call void @foo() #2
+  br label %if.end
+
+; CHECK: if.then3:
+; CHECK: br label %if.then5
+
+if.else:
+  call void @bar() #2
+  br label %if.end
+
+; CHECK: if.else:
+; CHECK: br label %if.then5
+
+if.end:
+  br i1 %tobool1, label %if.then5, label %if.end7
+
+; CHECK-NOT: if.end:
+; CHECK-NOT: br i1 %tobool1, label %if.then5, label %if.end7
+
+if.then5:
+  %arrayidx = getelementptr inbounds i32, i32* %arr, i64 1
+  store i32 %b, i32* %arrayidx, align 4
+  br label %if.end7
+
+if.end7:
+  ret void
+}
+
+declare void @foo()
+declare void @bar()