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/PassManager.h"
29 #include "llvm/IR/ValueHandle.h"
30 #include <deque>
31 
32 namespace llvm {
33 
34 class APInt;
35 class BasicBlock;
36 class BinaryOperator;
37 class Function;
38 class Instruction;
39 class IRBuilderBase;
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                        bool HasNUW);
107   Value *OptimizeExpression(BinaryOperator *I,
108                             SmallVectorImpl<reassociate::ValueEntry> &Ops);
109   Value *OptimizeAdd(Instruction *I,
110                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
111   Value *OptimizeXor(Instruction *I,
112                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
113   bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
114                       APInt &ConstOpnd, Value *&Res);
115   bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
116                       reassociate::XorOpnd *Opnd2, APInt &ConstOpnd,
117                       Value *&Res);
118   Value *buildMinimalMultiplyDAG(IRBuilderBase &Builder,
119                                  SmallVectorImpl<reassociate::Factor> &Factors);
120   Value *OptimizeMul(BinaryOperator *I,
121                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
122   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
123   void EraseInst(Instruction *I);
124   void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts);
125   void OptimizeInst(Instruction *I);
126   Instruction *canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op,
127                                                Value *OtherOp);
128   Instruction *canonicalizeNegFPConstants(Instruction *I);
129   void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
130 };
131 
132 } // end namespace llvm
133 
134 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
135