include/llvm/Transforms/Scalar/Reassociate.h

   1 //===- Reassociate.h - Reassociate binary expressions -----------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This pass reassociates commutative expressions in an order that is designed
  10 // to promote better constant propagation, GCSE, LICM, PRE, etc.
  11 //
  12 // For example: 4 + (x + 5) -> x + (4 + 5)
  13 //
  14 // In the implementation of this algorithm, constants are assigned rank = 0,
  15 // function arguments are rank = 1, and other values are assigned ranks
  16 // corresponding to the reverse post order traversal of current function
  17 // (starting at 2), which effectively gives values in deep loops higher rank
  18 // than values not in loops.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
  23 #define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
  24
  25 #include "llvm/ADT/DenseMap.h"
  26 #include "llvm/ADT/PostOrderIterator.h"
  27 #include "llvm/ADT/SetVector.h"
  28 #include "llvm/IR/IRBuilder.h"
  29 #include "llvm/IR/PassManager.h"
  30 #include "llvm/IR/ValueHandle.h"
  31 #include <deque>
  32
  33 namespace llvm {
  34
  35 class APInt;
  36 class BasicBlock;
  37 class BinaryOperator;
  38 class Function;
  39 class Instruction;
  40 class Value;
  41
  42 /// A private "module" namespace for types and utilities used by Reassociate.
  43 /// These are implementation details and should not be used by clients.
  44 namespace reassociate {
  45
  46 struct ValueEntry {
  47   unsigned Rank;
  48   Value *Op;
  49
  50   ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
  51 };
  52
  53 inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
  54   return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start.
  55 }
  56
  57 /// Utility class representing a base and exponent pair which form one
  58 /// factor of some product.
  59 struct Factor {
  60   Value *Base;
  61   unsigned Power;
  62
  63   Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {}
  64 };
  65
  66 class XorOpnd;
  67
  68 } // end namespace reassociate
  69
  70 /// Reassociate commutative expressions.
  71 class ReassociatePass : public PassInfoMixin<ReassociatePass> {
  72 public:
  73   using OrderedSet =
  74       SetVector<AssertingVH<Instruction>, std::deque<AssertingVH<Instruction>>>;
  75
  76 protected:
  77   DenseMap<BasicBlock *, unsigned> RankMap;
  78   DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
  79   OrderedSet RedoInsts;
  80
  81   // Arbitrary, but prevents quadratic behavior.
  82   static const unsigned GlobalReassociateLimit = 10;
  83   static const unsigned NumBinaryOps =
  84       Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin;
  85
  86   struct PairMapValue {
  87     WeakVH Value1;
  88     WeakVH Value2;
  89     unsigned Score;
  90     bool isValid() const { return Value1 && Value2; }
  91   };
  92   DenseMap<std::pair<Value *, Value *>, PairMapValue> PairMap[NumBinaryOps];
  93
  94   bool MadeChange;
  95
  96 public:
  97   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
  98
  99 private:
 100   void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
 101   unsigned getRank(Value *V);
 102   void canonicalizeOperands(Instruction *I);
 103   void ReassociateExpression(BinaryOperator *I);
 104   void RewriteExprTree(BinaryOperator *I,
 105                        SmallVectorImpl<reassociate::ValueEntry> &Ops);
 106   Value *OptimizeExpression(BinaryOperator *I,
 107                             SmallVectorImpl<reassociate::ValueEntry> &Ops);
 108   Value *OptimizeAdd(Instruction *I,
 109                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
 110   Value *OptimizeXor(Instruction *I,
 111                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
 112   bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
 113                       APInt &ConstOpnd, Value *&Res);
 114   bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
 115                       reassociate::XorOpnd *Opnd2, APInt &ConstOpnd,
 116                       Value *&Res);
 117   Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
 118                                  SmallVectorImpl<reassociate::Factor> &Factors);
 119   Value *OptimizeMul(BinaryOperator *I,
 120                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
 121   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
 122   void EraseInst(Instruction *I);
 123   void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts);
 124   void OptimizeInst(Instruction *I);
 125   Instruction *canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op,
 126                                                Value *OtherOp);
 127   Instruction *canonicalizeNegFPConstants(Instruction *I);
 128   void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
 129 };
 130
 131 } // end namespace llvm
 132
 133 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H