LLVM  10.0.0svn
Reassociate.h
Go to the documentation of this file.
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"
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;
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 {
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:
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 {
89  unsigned Score;
90  bool isValid() const { return Value1 && Value2; }
91  };
93 
94  bool MadeChange;
95 
96 public:
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,
106  Value *OptimizeExpression(BinaryOperator *I,
108  Value *OptimizeAdd(Instruction *I,
110  Value *OptimizeXor(Instruction *I,
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,
119  Value *OptimizeMul(BinaryOperator *I,
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
DenseMap< AssertingVH< Value >, unsigned > ValueRankMap
Definition: Reassociate.h:78
Utility class representing a non-constant Xor-operand.
Definition: Reassociate.cpp:95
nary reassociate
Utility class representing a base and exponent pair which form one factor of some product...
Definition: Reassociate.h:59
F(f)
Reassociate commutative expressions.
Definition: Reassociate.h:71
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
bool operator<(const ValueEntry &LHS, const ValueEntry &RHS)
Definition: Reassociate.h:53
A nullable Value handle that is nullable.
Definition: ValueHandle.h:140
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
SetVector< AssertingVH< Instruction >, std::deque< AssertingVH< Instruction > >> OrderedSet
Definition: Reassociate.h:74
ValueEntry(unsigned R, Value *O)
Definition: Reassociate.h:50
OrderedSet RedoInsts
Definition: Reassociate.h:79
DenseMap< BasicBlock *, unsigned > RankMap
Definition: Reassociate.h:77
Factor(Value *Base, unsigned Power)
Definition: Reassociate.h:63
Class for arbitrary precision integers.
Definition: APInt.h:69
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM Value Representation.
Definition: Value.h:73
A vector that has set insertion semantics.
Definition: SetVector.h:40
This header defines various interfaces for pass management in LLVM.