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