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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
//==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass identifies expensive constants to hoist and coalesces them to
// better prepare it for SelectionDAG-based code generation. This works around
// the limitations of the basic-block-at-a-time approach.
//
// First it scans all instructions for integer constants and calculates its
// cost. If the constant can be folded into the instruction (the cost is
// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
// consider it expensive and leave it alone. This is the default behavior and
// the default implementation of getIntImmCost will always return TCC_Free.
//
// If the cost is more than TCC_BASIC, then the integer constant can't be folded
// into the instruction and it might be beneficial to hoist the constant.
// Similar constants are coalesced to reduce register pressure and
// materialization code.
//
// When a constant is hoisted, it is also hidden behind a bitcast to force it to
// be live-out of the basic block. Otherwise the constant would be just
// duplicated and each basic block would have its own copy in the SelectionDAG.
// The SelectionDAG recognizes such constants as opaque and doesn't perform
// certain transformations on them, which would create a new expensive constant.
//
// This optimization is only applied to integer constants in instructions and
// simple (this means not nested) constant cast expressions. For example:
// %0 = load i64* inttoptr (i64 big_constant to i64*)
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
#define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/PassManager.h"
#include <algorithm>
#include <vector>
namespace llvm {
class BasicBlock;
class BlockFrequencyInfo;
class Constant;
class ConstantInt;
class DominatorTree;
class Function;
class Instruction;
class TargetTransformInfo;
/// A private "module" namespace for types and utilities used by
/// ConstantHoisting. These are implementation details and should not be used by
/// clients.
namespace consthoist {
/// Keeps track of the user of a constant and the operand index where the
/// constant is used.
struct ConstantUser {
Instruction *Inst;
unsigned OpndIdx;
ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
};
using ConstantUseListType = SmallVector<ConstantUser, 8>;
/// Keeps track of a constant candidate and its uses.
struct ConstantCandidate {
ConstantUseListType Uses;
ConstantInt *ConstInt;
unsigned CumulativeCost = 0;
ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {}
/// Add the user to the use list and update the cost.
void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
CumulativeCost += Cost;
Uses.push_back(ConstantUser(Inst, Idx));
}
};
/// This represents a constant that has been rebased with respect to a
/// base constant. The difference to the base constant is recorded in Offset.
struct RebasedConstantInfo {
ConstantUseListType Uses;
Constant *Offset;
RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
: Uses(std::move(Uses)), Offset(Offset) {}
};
using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
/// A base constant and all its rebased constants.
struct ConstantInfo {
ConstantInt *BaseConstant;
RebasedConstantListType RebasedConstants;
};
} // end namespace consthoist
class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
public:
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
// Glue for old PM.
bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
BlockFrequencyInfo *BFI, BasicBlock &Entry);
void releaseMemory() {
ConstantVec.clear();
ClonedCastMap.clear();
ConstCandVec.clear();
}
private:
using ConstCandMapType = DenseMap<ConstantInt *, unsigned>;
using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
const TargetTransformInfo *TTI;
DominatorTree *DT;
BlockFrequencyInfo *BFI;
BasicBlock *Entry;
/// Keeps track of constant candidates found in the function.
ConstCandVecType ConstCandVec;
/// Keep track of cast instructions we already cloned.
SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
/// These are the final constants we decided to hoist.
SmallVector<consthoist::ConstantInfo, 8> ConstantVec;
Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
SmallPtrSet<Instruction *, 8>
findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
void collectConstantCandidates(ConstCandMapType &ConstCandMap,
Instruction *Inst, unsigned Idx,
ConstantInt *ConstInt);
void collectConstantCandidates(ConstCandMapType &ConstCandMap,
Instruction *Inst, unsigned Idx);
void collectConstantCandidates(ConstCandMapType &ConstCandMap,
Instruction *Inst);
void collectConstantCandidates(Function &Fn);
void findAndMakeBaseConstant(ConstCandVecType::iterator S,
ConstCandVecType::iterator E);
unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
ConstCandVecType::iterator E,
ConstCandVecType::iterator &MaxCostItr);
void findBaseConstants();
void emitBaseConstants(Instruction *Base, Constant *Offset,
const consthoist::ConstantUser &ConstUser);
bool emitBaseConstants();
void deleteDeadCastInst() const;
bool optimizeConstants(Function &Fn);
};
} // end namespace llvm
#endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
|
