PM: Port Reassociate to the new pass manager

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@267631 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 101 insertions, 139 deletions

diff --git a/lib/Transforms/Scalar/Reassociate.cpp b/lib/Transforms/Scalar/Reassociate.cpp
index 417546b0839..6b761c5bec7 100644
--- a/lib/Transforms/Scalar/Reassociate.cpp
+++ b/lib/Transforms/Scalar/Reassociate.cpp
@@ -20,7 +20,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
@@ -39,9 +39,11 @@
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 using namespace llvm;
+using namespace reassociate;
 
 #define DEBUG_TYPE "reassociate"
 
@@ -49,17 +51,6 @@ STATISTIC(NumChanged, "Number of insts reassociated");
 STATISTIC(NumAnnihil, "Number of expr tree annihilated");
 STATISTIC(NumFactor , "Number of multiplies factored");
 
-namespace {
-  struct ValueEntry {
-    unsigned Rank;
-    Value *Op;
-    ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
-  };
-  inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
-    return LHS.Rank > RHS.Rank;   // Sort so that highest rank goes to start.
-  }
-}
-
 #ifndef NDEBUG
 /// Print out the expression identified in the Ops list.
 ///
@@ -75,92 +66,35 @@ static void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) {
 }
 #endif
 
-namespace {
-  /// \brief Utility class representing a base and exponent pair which form one
-  /// factor of some product.
-  struct Factor {
-    Value *Base;
-    unsigned Power;
-    Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {}
-  };
-  
-  /// Utility class representing a non-constant Xor-operand. We classify
-  /// non-constant Xor-Operands into two categories:
-  ///  C1) The operand is in the form "X & C", where C is a constant and C != ~0
-  ///  C2)
-  ///    C2.1) The operand is in the form of "X | C", where C is a non-zero
-  ///          constant.
-  ///    C2.2) Any operand E which doesn't fall into C1 and C2.1, we view this
-  ///          operand as "E | 0"
-  class XorOpnd {
-  public:
-    XorOpnd(Value *V);
-
-    bool isInvalid() const { return SymbolicPart == nullptr; }
-    bool isOrExpr() const { return isOr; }
-    Value *getValue() const { return OrigVal; }
-    Value *getSymbolicPart() const { return SymbolicPart; }
-    unsigned getSymbolicRank() const { return SymbolicRank; }
-    const APInt &getConstPart() const { return ConstPart; }
-
-    void Invalidate() { SymbolicPart = OrigVal = nullptr; }
-    void setSymbolicRank(unsigned R) { SymbolicRank = R; }
-
-  private:
-    Value *OrigVal;
-    Value *SymbolicPart;
-    APInt ConstPart;
-    unsigned SymbolicRank;
-    bool isOr;
-  };
-}
-
-namespace {
-  class Reassociate : public FunctionPass {
-    DenseMap<BasicBlock*, unsigned> RankMap;
-    DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
-    SetVector<AssertingVH<Instruction> > RedoInsts;
-    bool MadeChange;
-  public:
-    static char ID; // Pass identification, replacement for typeid
-    Reassociate() : FunctionPass(ID) {
-      initializeReassociatePass(*PassRegistry::getPassRegistry());
-    }
-
-    bool runOnFunction(Function &F) override;
-
-    void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.setPreservesCFG();
-      AU.addPreserved<GlobalsAAWrapperPass>();
-    }
-  private:
-    void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
-
-    unsigned getRank(Value *V);
-    void canonicalizeOperands(Instruction *I);
-    void ReassociateExpression(BinaryOperator *I);
-    void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
-    Value *OptimizeExpression(BinaryOperator *I,
-                              SmallVectorImpl<ValueEntry> &Ops);
-    Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops);
-    Value *OptimizeXor(Instruction *I, SmallVectorImpl<ValueEntry> &Ops);
-    bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, APInt &ConstOpnd,
-                        Value *&Res);
-    bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2,
-                        APInt &ConstOpnd, Value *&Res);
-    bool collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops,
-                                SmallVectorImpl<Factor> &Factors);
-    Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
-                                   SmallVectorImpl<Factor> &Factors);
-    Value *OptimizeMul(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
-    Value *RemoveFactorFromExpression(Value *V, Value *Factor);
-    void EraseInst(Instruction *I);
-    void RecursivelyEraseDeadInsts(Instruction *I,
-                                   SetVector<AssertingVH<Instruction>> &Insts);
-    void OptimizeInst(Instruction *I);
-    Instruction *canonicalizeNegConstExpr(Instruction *I);
-  };
-}
+/// Utility class representing a non-constant Xor-operand. We classify
+/// non-constant Xor-Operands into two categories:
+///  C1) The operand is in the form "X & C", where C is a constant and C != ~0
+///  C2)
+///    C2.1) The operand is in the form of "X | C", where C is a non-zero
+///          constant.
+///    C2.2) Any operand E which doesn't fall into C1 and C2.1, we view this
+///          operand as "E | 0"
+class llvm::reassociate::XorOpnd {
+public:
+  XorOpnd(Value *V);
+
+  bool isInvalid() const { return SymbolicPart == nullptr; }
+  bool isOrExpr() const { return isOr; }
+  Value *getValue() const { return OrigVal; }
+  Value *getSymbolicPart() const { return SymbolicPart; }
+  unsigned getSymbolicRank() const { return SymbolicRank; }
+  const APInt &getConstPart() const { return ConstPart; }
+
+  void Invalidate() { SymbolicPart = OrigVal = nullptr; }
+  void setSymbolicRank(unsigned R) { SymbolicRank = R; }
+
+private:
+  Value *OrigVal;
+  Value *SymbolicPart;
+  APInt ConstPart;
+  unsigned SymbolicRank;
+  bool isOr;
+};
 
 XorOpnd::XorOpnd(Value *V) {
   assert(!isa<ConstantInt>(V) && "No ConstantInt");
@@ -189,13 +123,6 @@ XorOpnd::XorOpnd(Value *V) {
   isOr = true;
 }
 
-char Reassociate::ID = 0;
-INITIALIZE_PASS(Reassociate, "reassociate",
-                "Reassociate expressions", false, false)
-
-// Public interface to the Reassociate pass
-FunctionPass *llvm::createReassociatePass() { return new Reassociate(); }
-
 /// Return true if V is an instruction of the specified opcode and if it
 /// only has one use.
 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) {
@@ -218,8 +145,8 @@ static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode1,
   return nullptr;
 }
 
-void Reassociate::BuildRankMap(Function &F,
-                               ReversePostOrderTraversal<Function *> &RPOT) {
+void ReassociatePass::BuildRankMap(
+    Function &F, ReversePostOrderTraversal<Function *> &RPOT) {
   unsigned i = 2;
 
   // Assign distinct ranks to function arguments.
@@ -242,7 +169,7 @@ void Reassociate::BuildRankMap(Function &F,
   }
 }
 
-unsigned Reassociate::getRank(Value *V) {
+unsigned ReassociatePass::getRank(Value *V) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) {
     if (isa<Argument>(V)) return ValueRankMap[V];   // Function argument.
@@ -273,7 +200,7 @@ unsigned Reassociate::getRank(Value *V) {
 }
 
 // Canonicalize constants to RHS.  Otherwise, sort the operands by rank.
-void Reassociate::canonicalizeOperands(Instruction *I) {
+void ReassociatePass::canonicalizeOperands(Instruction *I) {
   assert(isa<BinaryOperator>(I) && "Expected binary operator.");
   assert(I->isCommutative() && "Expected commutative operator.");
 
@@ -683,8 +610,8 @@ static bool LinearizeExprTree(BinaryOperator *I,
 
 /// Now that the operands for this expression tree are
 /// linearized and optimized, emit them in-order.
-void Reassociate::RewriteExprTree(BinaryOperator *I,
-                                  SmallVectorImpl<ValueEntry> &Ops) {
+void ReassociatePass::RewriteExprTree(BinaryOperator *I,
+                                      SmallVectorImpl<ValueEntry> &Ops) {
   assert(Ops.size() > 1 && "Single values should be used directly!");
 
   // Since our optimizations should never increase the number of operations, the
@@ -1067,7 +994,7 @@ static Value *EmitAddTreeOfValues(Instruction *I,
 /// If V is an expression tree that is a multiplication sequence,
 /// and if this sequence contains a multiply by Factor,
 /// remove Factor from the tree and return the new tree.
-Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) {
+Value *ReassociatePass::RemoveFactorFromExpression(Value *V, Value *Factor) {
   BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul);
   if (!BO)
     return nullptr;
@@ -1230,9 +1157,9 @@ static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd,
 // If it was successful, true is returned, and the "R" and "C" is returned
 // via "Res" and "ConstOpnd", respectively; otherwise, false is returned,
 // and both "Res" and "ConstOpnd" remain unchanged.
-//  
-bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
-                                 APInt &ConstOpnd, Value *&Res) {
+//
+bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
+                                     APInt &ConstOpnd, Value *&Res) {
   // Xor-Rule 1: (x | c1) ^ c2 = (x | c1) ^ (c1 ^ c1) ^ c2 
   //                       = ((x | c1) ^ c1) ^ (c1 ^ c2)
   //                       = (x & ~c1) ^ (c1 ^ c2)
@@ -1266,8 +1193,9 @@ bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
 // via "Res" and "ConstOpnd", respectively (If the entire expression is
 // evaluated to a constant, the Res is set to NULL); otherwise, false is
 // returned, and both "Res" and "ConstOpnd" remain unchanged.
-bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2,
-                                 APInt &ConstOpnd, Value *&Res) {
+bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
+                                     XorOpnd *Opnd2, APInt &ConstOpnd,
+                                     Value *&Res) {
   Value *X = Opnd1->getSymbolicPart();
   if (X != Opnd2->getSymbolicPart())
     return false;
@@ -1341,8 +1269,8 @@ bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2,
 /// Optimize a series of operands to an 'xor' instruction. If it can be reduced
 /// to a single Value, it is returned, otherwise the Ops list is mutated as
 /// necessary.
-Value *Reassociate::OptimizeXor(Instruction *I,
-                                SmallVectorImpl<ValueEntry> &Ops) {
+Value *ReassociatePass::OptimizeXor(Instruction *I,
+                                    SmallVectorImpl<ValueEntry> &Ops) {
   if (Value *V = OptimizeAndOrXor(Instruction::Xor, Ops))
     return V;
       
@@ -1462,8 +1390,8 @@ Value *Reassociate::OptimizeXor(Instruction *I,
 /// Optimize a series of operands to an 'add' instruction.  This
 /// optimizes based on identities.  If it can be reduced to a single Value, it
 /// is returned, otherwise the Ops list is mutated as necessary.
-Value *Reassociate::OptimizeAdd(Instruction *I,
-                                SmallVectorImpl<ValueEntry> &Ops) {
+Value *ReassociatePass::OptimizeAdd(Instruction *I,
+                                    SmallVectorImpl<ValueEntry> &Ops) {
   // Scan the operand lists looking for X and -X pairs.  If we find any, we
   // can simplify expressions like X+-X == 0 and X+~X ==-1.  While we're at it,
   // scan for any
@@ -1700,8 +1628,8 @@ Value *Reassociate::OptimizeAdd(Instruction *I,
 ///   ((((x*y)*x)*y)*x) -> [(x, 3), (y, 2)]
 ///
 /// \returns Whether any factors have a power greater than one.
-bool Reassociate::collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops,
-                                         SmallVectorImpl<Factor> &Factors) {
+bool ReassociatePass::collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops,
+                                             SmallVectorImpl<Factor> &Factors) {
   // FIXME: Have Ops be (ValueEntry, Multiplicity) pairs, simplifying this.
   // Compute the sum of powers of simplifiable factors.
   unsigned FactorPowerSum = 0;
@@ -1777,8 +1705,9 @@ static Value *buildMultiplyTree(IRBuilder<> &Builder,
 /// equal and the powers are sorted in decreasing order, compute the minimal
 /// DAG of multiplies to compute the final product, and return that product
 /// value.
-Value *Reassociate::buildMinimalMultiplyDAG(IRBuilder<> &Builder,
-                                            SmallVectorImpl<Factor> &Factors) {
+Value *
+ReassociatePass::buildMinimalMultiplyDAG(IRBuilder<> &Builder,
+                                         SmallVectorImpl<Factor> &Factors) {
   assert(Factors[0].Power);
   SmallVector<Value *, 4> OuterProduct;
   for (unsigned LastIdx = 0, Idx = 1, Size = Factors.size();
@@ -1834,8 +1763,8 @@ Value *Reassociate::buildMinimalMultiplyDAG(IRBuilder<> &Builder,
   return V;
 }
 
-Value *Reassociate::OptimizeMul(BinaryOperator *I,
-                                SmallVectorImpl<ValueEntry> &Ops) {
+Value *ReassociatePass::OptimizeMul(BinaryOperator *I,
+                                    SmallVectorImpl<ValueEntry> &Ops) {
   // We can only optimize the multiplies when there is a chain of more than
   // three, such that a balanced tree might require fewer total multiplies.
   if (Ops.size() < 4)
@@ -1858,8 +1787,8 @@ Value *Reassociate::OptimizeMul(BinaryOperator *I,
   return nullptr;
 }
 
-Value *Reassociate::OptimizeExpression(BinaryOperator *I,
-                                       SmallVectorImpl<ValueEntry> &Ops) {
+Value *ReassociatePass::OptimizeExpression(BinaryOperator *I,
+                                           SmallVectorImpl<ValueEntry> &Ops) {
   // Now that we have the linearized expression tree, try to optimize it.
   // Start by folding any constants that we found.
   Constant *Cst = nullptr;
@@ -1919,7 +1848,7 @@ Value *Reassociate::OptimizeExpression(BinaryOperator *I,
 
 // Remove dead instructions and if any operands are trivially dead add them to
 // Insts so they will be removed as well.
-void Reassociate::RecursivelyEraseDeadInsts(
+void ReassociatePass::RecursivelyEraseDeadInsts(
     Instruction *I, SetVector<AssertingVH<Instruction>> &Insts) {
   assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
   SmallVector<Value *, 4> Ops(I->op_begin(), I->op_end());
@@ -1934,7 +1863,7 @@ void Reassociate::RecursivelyEraseDeadInsts(
 }
 
 /// Zap the given instruction, adding interesting operands to the work list.
-void Reassociate::EraseInst(Instruction *I) {
+void ReassociatePass::EraseInst(Instruction *I) {
   assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
   SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
   // Erase the dead instruction.
@@ -1958,7 +1887,7 @@ void Reassociate::EraseInst(Instruction *I) {
 // Canonicalize expressions of the following form:
 //  x + (-Constant * y) -> x - (Constant * y)
 //  x - (-Constant * y) -> x + (Constant * y)
-Instruction *Reassociate::canonicalizeNegConstExpr(Instruction *I) {
+Instruction *ReassociatePass::canonicalizeNegConstExpr(Instruction *I) {
   if (!I->hasOneUse() || I->getType()->isVectorTy())
     return nullptr;
 
@@ -2035,7 +1964,7 @@ Instruction *Reassociate::canonicalizeNegConstExpr(Instruction *I) {
 
 /// Inspect and optimize the given instruction. Note that erasing
 /// instructions is not allowed.
-void Reassociate::OptimizeInst(Instruction *I) {
+void ReassociatePass::OptimizeInst(Instruction *I) {
   // Only consider operations that we understand.
   if (!isa<BinaryOperator>(I))
     return;
@@ -2162,7 +2091,7 @@ void Reassociate::OptimizeInst(Instruction *I) {
   ReassociateExpression(BO);
 }
 
-void Reassociate::ReassociateExpression(BinaryOperator *I) {
+void ReassociatePass::ReassociateExpression(BinaryOperator *I) {
   // First, walk the expression tree, linearizing the tree, collecting the
   // operand information.
   SmallVector<RepeatedValue, 8> Tree;
@@ -2244,10 +2173,7 @@ void Reassociate::ReassociateExpression(BinaryOperator *I) {
   RewriteExprTree(I, Ops);
 }
 
-bool Reassociate::runOnFunction(Function &F) {
-  if (skipFunction(F))
-    return false;
-
+PreservedAnalyses ReassociatePass::run(Function &F) {
   // Reassociate needs for each instruction to have its operands already
   // processed, so we first perform a RPOT of the basic blocks so that
   // when we process a basic block, all its dominators have been processed
@@ -2301,5 +2227,41 @@ bool Reassociate::runOnFunction(Function &F) {
   RankMap.clear();
   ValueRankMap.clear();
 
-  return MadeChange;
+  if (MadeChange)
+    return PreservedAnalyses::none();
+
+  return PreservedAnalyses::all();
+}
+
+namespace {
+  class ReassociateLegacyPass : public FunctionPass {
+    ReassociatePass Impl;
+  public:
+    static char ID; // Pass identification, replacement for typeid
+    ReassociateLegacyPass() : FunctionPass(ID) {
+      initializeReassociateLegacyPassPass(*PassRegistry::getPassRegistry());
+    }
+
+    bool runOnFunction(Function &F) override {
+      if (skipFunction(F))
+        return false;
+
+      auto PA = Impl.run(F);
+      return !PA.areAllPreserved();
+    }
+
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.setPreservesCFG();
+      AU.addPreserved<GlobalsAAWrapperPass>();
+    }
+  };
+}
+
+char ReassociateLegacyPass::ID = 0;
+INITIALIZE_PASS(ReassociateLegacyPass, "reassociate",
+                "Reassociate expressions", false, false)
+
+// Public interface to the Reassociate pass
+FunctionPass *llvm::createReassociatePass() {
+  return new ReassociateLegacyPass();
 }