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/BasicBlock.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 IRBuilderBase;
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 struct OverflowTracking {
68   bool HasNUW;
69   bool HasNSW;
70   bool AllKnownNonNegative;
71   bool AllKnownNonZero;
72   // Note: AllKnownNonNegative can be true in a case where one of the operands
73   // is negative, but one the operators is not NSW. AllKnownNonNegative should
74   // not be used independently of HasNSW
OverflowTrackingOverflowTracking75   OverflowTracking()
76       : HasNUW(true), HasNSW(true), AllKnownNonNegative(true),
77         AllKnownNonZero(true) {}
78 };
79 
80 class XorOpnd;
81 
82 } // end namespace reassociate
83 
84 /// Reassociate commutative expressions.
85 class ReassociatePass : public PassInfoMixin<ReassociatePass> {
86 public:
87   using OrderedSet =
88       SetVector<AssertingVH<Instruction>, std::deque<AssertingVH<Instruction>>>;
89 
90 protected:
91   DenseMap<BasicBlock *, unsigned> RankMap;
92   DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
93   OrderedSet RedoInsts;
94 
95   // Arbitrary, but prevents quadratic behavior.
96   static const unsigned GlobalReassociateLimit = 10;
97   static const unsigned NumBinaryOps =
98       Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin;
99 
100   struct PairMapValue {
101     WeakVH Value1;
102     WeakVH Value2;
103     unsigned Score;
isValidPairMapValue104     bool isValid() const { return Value1 && Value2; }
105   };
106   DenseMap<std::pair<Value *, Value *>, PairMapValue> PairMap[NumBinaryOps];
107 
108   bool MadeChange;
109 
110 public:
111   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
112 
113 private:
114   void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
115   unsigned getRank(Value *V);
116   void canonicalizeOperands(Instruction *I);
117   void ReassociateExpression(BinaryOperator *I);
118   void RewriteExprTree(BinaryOperator *I,
119                        SmallVectorImpl<reassociate::ValueEntry> &Ops,
120                        reassociate::OverflowTracking Flags);
121   Value *OptimizeExpression(BinaryOperator *I,
122                             SmallVectorImpl<reassociate::ValueEntry> &Ops);
123   Value *OptimizeAdd(Instruction *I,
124                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
125   Value *OptimizeXor(Instruction *I,
126                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
127   bool CombineXorOpnd(BasicBlock::iterator It, reassociate::XorOpnd *Opnd1,
128                       APInt &ConstOpnd, Value *&Res);
129   bool CombineXorOpnd(BasicBlock::iterator It, reassociate::XorOpnd *Opnd1,
130                       reassociate::XorOpnd *Opnd2, APInt &ConstOpnd,
131                       Value *&Res);
132   Value *buildMinimalMultiplyDAG(IRBuilderBase &Builder,
133                                  SmallVectorImpl<reassociate::Factor> &Factors);
134   Value *OptimizeMul(BinaryOperator *I,
135                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
136   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
137   void EraseInst(Instruction *I);
138   void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts);
139   void OptimizeInst(Instruction *I);
140   Instruction *canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op,
141                                                Value *OtherOp);
142   Instruction *canonicalizeNegFPConstants(Instruction *I);
143   void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
144 };
145 
146 } // end namespace llvm
147 
148 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
149