LLVM  14.0.0git
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/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;
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(IRBuilderBase &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
llvm::reassociate::ValueEntry::Rank
unsigned Rank
Definition: Reassociate.h:47
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::reassociate::ValueEntry
Definition: Reassociate.h:46
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
llvm::ReassociatePass
Reassociate commutative expressions.
Definition: Reassociate.h:71
llvm::ReassociatePass::PairMapValue::Value2
WeakVH Value2
Definition: Reassociate.h:88
llvm::ReassociatePass::RankMap
DenseMap< BasicBlock *, unsigned > RankMap
Definition: Reassociate.h:77
llvm::ReassociatePass::PairMapValue::isValid
bool isValid() const
Definition: Reassociate.h:90
llvm::WeakVH
A nullable Value handle that is nullable.
Definition: ValueHandle.h:144
DenseMap.h
llvm::ReassociatePass::RedoInsts
OrderedSet RedoInsts
Definition: Reassociate.h:79
llvm::ReassociatePass::NumBinaryOps
static const unsigned NumBinaryOps
Definition: Reassociate.h:83
llvm::reassociate::operator<
bool operator<(const ValueEntry &LHS, const ValueEntry &RHS)
Definition: Reassociate.h:53
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::reassociate::XorOpnd
Utility class representing a non-constant Xor-operand.
Definition: Reassociate.cpp:97
llvm::Instruction
Definition: Instruction.h:45
llvm::ReassociatePass::MadeChange
bool MadeChange
Definition: Reassociate.h:94
llvm::ReassociatePass::PairMapValue
Definition: Reassociate.h:86
llvm::reassociate::Factor::Base
Value * Base
Definition: Reassociate.h:60
llvm::ReassociatePass::OrderedSet
SetVector< AssertingVH< Instruction >, std::deque< AssertingVH< Instruction > >> OrderedSet
Definition: Reassociate.h:74
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:192
llvm::ReassociatePass::PairMap
DenseMap< std::pair< Value *, Value * >, PairMapValue > PairMap[NumBinaryOps]
Definition: Reassociate.h:92
llvm::reassociate::ValueEntry::Op
Value * Op
Definition: Reassociate.h:48
llvm::DenseMap< BasicBlock *, unsigned >
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::reassociate::ValueEntry::ValueEntry
ValueEntry(unsigned R, Value *O)
Definition: Reassociate.h:50
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::reassociate::Factor::Power
unsigned Power
Definition: Reassociate.h:61
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::BinaryOperator
Definition: InstrTypes.h:189
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:95
ValueHandle.h
llvm::ReassociatePass::PairMapValue::Value1
WeakVH Value1
Definition: Reassociate.h:87
llvm::ReassociatePass::GlobalReassociateLimit
static const unsigned GlobalReassociateLimit
Definition: Reassociate.h:82
llvm::ReassociatePass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
Definition: Reassociate.cpp:2499
llvm::ReassociatePass::ValueRankMap
DenseMap< AssertingVH< Value >, unsigned > ValueRankMap
Definition: Reassociate.h:78
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::reassociate::Factor::Factor
Factor(Value *Base, unsigned Power)
Definition: Reassociate.h:63
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
llvm::ReassociatePass::PairMapValue::Score
unsigned Score
Definition: Reassociate.h:89
PostOrderIterator.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::reassociate::Factor
Utility class representing a base and exponent pair which form one factor of some product.
Definition: Reassociate.h:59
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
reassociate
nary reassociate
Definition: NaryReassociate.cpp:162
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h