[CodeMoverUtils] Improve IsControlFlowEquivalent.

Whitney Tsang · Whitney Tsang · commit 78dc64989c2f · 2020-01-28T14:18:00.000Z
Summary: Currently IsControlFlowEquivalent determine if two blocks are control flow equivalent by checking if A dominates B and B post dominates A. There exists blocks that are control flow equivalent even if they don't satisfy the A dominates B and B post dominates A condition. For example, if (cond) A if (cond) B In the PR, we determine if two blocks are control flow equivalent by also checking if the two sets of conditions A and B depends on are equivalent. Reviewer: jdoerfert, Meinersbur, dmgreen, etiotto, bmahjour, fhahn, hfinkel, kbarton Reviewed By: fhahn Subscribers: hiraditya, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D71578
diff --git a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
@@ -23,33 +23,30 @@ class Instruction;
 class PostDominatorTree;
 
 /// Return true if \p I0 and \p I1 are control flow equivalent.
-/// Two instructions are control flow equivalent if when one executes,
-/// the other is guaranteed to execute. This is determined using dominators
-/// and post-dominators: if A dominates B and B post-dominates A then A and B
-/// are control-flow equivalent.
+/// Two instructions are control flow equivalent if their basic blocks are
+/// control flow equivalent.
 bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p BB0 and \p BB1 are control flow equivalent.
 /// Two basic blocks are control flow equivalent if when one executes, the other
-/// is guaranteed to execute. This is determined using dominators and
-/// post-dominators: if A dominates B and B post-dominates A then A and B are
-/// control-flow equivalent.
+/// is guaranteed to execute.
 bool isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p I can be safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
-                        const DominatorTree &DT, const PostDominatorTree &PDT,
+                        DominatorTree &DT, const PostDominatorTree &PDT,
                         DependenceInfo &DI);
 
-/// Move instructions from \p FromBB bottom up to the beginning of \p ToBB
-/// when proven safe.
-void moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB,
-                       const DominatorTree &DT, const PostDominatorTree &PDT,
-                       DependenceInfo &DI);
+/// Move instructions, in an order-preserving manner, from \p FromBB to the
+/// beginning of \p ToBB when proven safe.
+void moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
+                                    DominatorTree &DT,
+                                    const PostDominatorTree &PDT,
+                                    DependenceInfo &DI);
 
 } // end namespace llvm
 
diff --git a/llvm/lib/Transforms/Scalar/LoopFuse.cpp b/llvm/lib/Transforms/Scalar/LoopFuse.cpp
@@ -1123,7 +1123,7 @@ struct LoopFuser {
   /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
   /// successor, then merge FC0.Latch with its unique successor.
   void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
-    moveInstsBottomUp(*FC0.Latch, *FC1.Latch, DT, PDT, DI);
+    moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI);
     if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) {
       MergeBlockIntoPredecessor(Succ, &DTU, &LI);
       DTU.flush();
diff --git a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
@@ -12,8 +12,10 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/OrderedInstructions.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Dominators.h"
@@ -30,6 +32,189 @@ STATISTIC(NotControlFlowEquivalent,
 STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
 STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
 
+namespace {
+/// Represent a control condition. A control condition is a condition of a
+/// terminator to decide which successors to execute. The pointer field
+/// represents the address of the condition of the terminator. The integer field
+/// is a bool, it is true when the basic block is executed when V is true. For
+/// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
+/// integer field equals to true, while %cond is a control condition of bb1 with
+/// the integer field equals to false.
+using ControlCondition = PointerIntPair<Value *, 1, bool>;
+#ifndef NDEBUG
+raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
+  OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
+     << "]";
+  return OS;
+}
+#endif
+
+/// Represent a set of control conditions required to execute ToBB from FromBB.
+class ControlConditions {
+  using ConditionVectorTy = SmallVector<ControlCondition, 6>;
+
+  /// A SmallVector of control conditions.
+  ConditionVectorTy Conditions;
+
+public:
+  /// Return a ControlConditions which stores all conditions required to execute
+  /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the
+  /// number of conditions to collect. Return None if not all conditions are
+  /// collected successfully, or we hit the limit.
+  static Optional<const ControlConditions>
+  collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,
+                           const DominatorTree &DT,
+                           const PostDominatorTree &PDT,
+                           unsigned MaxLookup = 6);
+
+  /// Return true if there exists no control conditions required to execute ToBB
+  /// from FromBB.
+  bool isUnconditional() const { return Conditions.empty(); }
+
+  /// Return a constant reference of Conditions.
+  const ConditionVectorTy &getControlConditions() const { return Conditions; }
+
+  /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition
+  /// equals to \p True. Return true if inserted successfully.
+  bool addControlCondition(ControlCondition C);
+
+  /// Return true if for all control conditions in Conditions, there exists an
+  /// equivalent control condition in \p Other.Conditions.
+  bool isEquivalent(const ControlConditions &Other) const;
+
+  /// Return true if \p C1 and \p C2 are equivalent.
+  static bool isEquivalent(const ControlCondition &C1,
+                           const ControlCondition &C2);
+
+private:
+  ControlConditions() = default;
+
+  static bool isEquivalent(const Value &V1, const Value &V2);
+  static bool isInverse(const Value &V1, const Value &V2);
+};
+} // namespace
+
+Optional<const ControlConditions> ControlConditions::collectControlConditions(
+    const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT,
+    const PostDominatorTree &PDT, unsigned MaxLookup) {
+  assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
+
+  ControlConditions Conditions;
+  unsigned NumConditions = 0;
+
+  // BB is executed unconditional from itself.
+  if (&Dominator == &BB)
+    return Conditions;
+
+  const BasicBlock *CurBlock = &BB;
+  // Walk up the dominator tree from the associated DT node for BB to the
+  // associated DT node for Dominator.
+  do {
+    assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
+    BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();
+    assert(DT.dominates(&Dominator, IDom) &&
+           "Expecting Dominator to dominate IDom");
+
+    // Limitation: can only handle branch instruction currently.
+    const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
+    if (!BI)
+      return None;
+
+    bool Inserted = false;
+    if (PDT.dominates(CurBlock, IDom)) {
+      LLVM_DEBUG(dbgs() << CurBlock->getName()
+                        << " is executed unconditionally from "
+                        << IDom->getName() << "\n");
+    } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {
+      LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
+                        << *BI->getCondition() << "\" is true from "
+                        << IDom->getName() << "\n");
+      Inserted = Conditions.addControlCondition(
+          ControlCondition(BI->getCondition(), true));
+    } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {
+      LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
+                        << *BI->getCondition() << "\" is false from "
+                        << IDom->getName() << "\n");
+      Inserted = Conditions.addControlCondition(
+          ControlCondition(BI->getCondition(), false));
+    } else
+      return None;
+
+    if (Inserted)
+      ++NumConditions;
+
+    if (MaxLookup != 0 && NumConditions > MaxLookup)
+      return None;
+
+    CurBlock = IDom;
+  } while (CurBlock != &Dominator);
+
+  return Conditions;
+}
+
+bool ControlConditions::addControlCondition(ControlCondition C) {
+  bool Inserted = false;
+  if (none_of(Conditions, [&C](ControlCondition &Exists) {
+        return ControlConditions::isEquivalent(C, Exists);
+      })) {
+    Conditions.push_back(C);
+    Inserted = true;
+  }
+
+  LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");
+  return Inserted;
+}
+
+bool ControlConditions::isEquivalent(const ControlConditions &Other) const {
+  if (Conditions.empty() && Other.Conditions.empty())
+    return true;
+
+  if (Conditions.size() != Other.Conditions.size())
+    return false;
+
+  return all_of(Conditions, [&Other](const ControlCondition &C) {
+    return any_of(Other.Conditions, [&C](const ControlCondition &OtherC) {
+      return ControlConditions::isEquivalent(C, OtherC);
+    });
+  });
+}
+
+bool ControlConditions::isEquivalent(const ControlCondition &C1,
+                                     const ControlCondition &C2) {
+  if (C1.getInt() == C2.getInt()) {
+    if (isEquivalent(*C1.getPointer(), *C2.getPointer()))
+      return true;
+  } else if (isInverse(*C1.getPointer(), *C2.getPointer()))
+    return true;
+
+  return false;
+}
+
+// FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
+// Values.
+// Currently, isEquivalent rely on other passes to ensure equivalent conditions
+// have the same value, e.g. GVN.
+bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {
+  return &V1 == &V2;
+}
+
+bool ControlConditions::isInverse(const Value &V1, const Value &V2) {
+  if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1))
+    if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {
+      if (Cmp1->getPredicate() == Cmp2->getInversePredicate() &&
+          Cmp1->getOperand(0) == Cmp2->getOperand(0) &&
+          Cmp1->getOperand(1) == Cmp2->getOperand(1))
+        return true;
+
+      if (Cmp1->getPredicate() ==
+              CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
+          Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
+          Cmp1->getOperand(1) == Cmp2->getOperand(0))
+        return true;
+    }
+  return false;
+}
+
 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                                    const DominatorTree &DT,
                                    const PostDominatorTree &PDT) {
@@ -42,8 +227,30 @@ bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
   if (&BB0 == &BB1)
     return true;
 
-  return ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
-          (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)));
+  if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
+      (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
+    return true;
+
+  // If the set of conditions required to execute BB0 and BB1 from their common
+  // dominator are the same, then BB0 and BB1 are control flow equivalent.
+  const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);
+  LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
+                    << " and " << BB1.getName() << " is "
+                    << CommonDominator->getName() << "\n");
+
+  Optional<const ControlConditions> BB0Conditions =
+      ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
+                                                  PDT);
+  if (BB0Conditions == None)
+    return false;
+
+  Optional<const ControlConditions> BB1Conditions =
+      ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,
+                                                  PDT);
+  if (BB1Conditions == None)
+    return false;
+
+  return BB0Conditions->isEquivalent(*BB1Conditions);
 }
 
 static bool reportInvalidCandidate(const Instruction &I,
@@ -90,8 +297,7 @@ collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
 }
 
 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
-                              const DominatorTree &DT,
-                              const PostDominatorTree &PDT,
+                              DominatorTree &DT, const PostDominatorTree &PDT,
                               DependenceInfo &DI) {
   // Cannot move itself before itself.
   if (&I == &InsertPoint)
@@ -111,9 +317,9 @@ bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
   if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
     return reportInvalidCandidate(I, NotControlFlowEquivalent);
 
-  // As I and InsertPoint are control flow equivalent, if I dominates
-  // InsertPoint, then I comes before InsertPoint.
-  const bool MoveForward = DT.dominates(&I, &InsertPoint);
+  OrderedInstructions OI(&DT);
+  DT.updateDFSNumbers();
+  const bool MoveForward = OI.dfsBefore(&I, &InsertPoint);
   if (MoveForward) {
     // When I is being moved forward, we need to make sure the InsertPoint
     // dominates every users. Or else, a user may be using an undefined I.
@@ -126,7 +332,7 @@ bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
     // dominates the InsertPoint. Or else, an operand may be undefined for I.
     for (const Value *Op : I.operands())
       if (auto *OpInst = dyn_cast<Instruction>(Op))
-        if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
+        if (&InsertPoint == OpInst || !OI.dominates(OpInst, &InsertPoint))
           return false;
   }
 
@@ -174,9 +380,10 @@ bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
   return true;
 }
 
-void llvm::moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB,
-                             const DominatorTree &DT,
-                             const PostDominatorTree &PDT, DependenceInfo &DI) {
+void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
+                                          DominatorTree &DT,
+                                          const PostDominatorTree &PDT,
+                                          DependenceInfo &DI) {
   for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
     Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
     Instruction &I = *It;
diff --git a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
