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