1 //===- LoadCombine.cpp - Combine Adjacent Loads ---------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 /// This transformation combines adjacent loads.
11 ///
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Transforms/Scalar.h"
15
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Analysis/AliasAnalysis.h"
19 #include "llvm/Analysis/AliasSetTracker.h"
20 #include "llvm/Analysis/TargetFolder.h"
21 #include "llvm/Pass.h"
22 #include "llvm/IR/DataLayout.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/MathExtras.h"
28 #include "llvm/Support/raw_ostream.h"
29
30 using namespace llvm;
31
32 #define DEBUG_TYPE "load-combine"
33
34 STATISTIC(NumLoadsAnalyzed, "Number of loads analyzed for combining");
35 STATISTIC(NumLoadsCombined, "Number of loads combined");
36
37 namespace {
38 struct PointerOffsetPair {
39 Value *Pointer;
40 uint64_t Offset;
41 };
42
43 struct LoadPOPPair {
LoadPOPPair__anon66f3801b0111::LoadPOPPair44 LoadPOPPair(LoadInst *L, PointerOffsetPair P, unsigned O)
45 : Load(L), POP(P), InsertOrder(O) {}
LoadPOPPair__anon66f3801b0111::LoadPOPPair46 LoadPOPPair() {}
47 LoadInst *Load;
48 PointerOffsetPair POP;
49 /// \brief The new load needs to be created before the first load in IR order.
50 unsigned InsertOrder;
51 };
52
53 class LoadCombine : public BasicBlockPass {
54 LLVMContext *C;
55 const DataLayout *DL;
56 AliasAnalysis *AA;
57
58 public:
LoadCombine()59 LoadCombine()
60 : BasicBlockPass(ID),
61 C(nullptr), DL(nullptr), AA(nullptr) {
62 initializeSROAPass(*PassRegistry::getPassRegistry());
63 }
64
65 using llvm::Pass::doInitialization;
66 bool doInitialization(Function &) override;
67 bool runOnBasicBlock(BasicBlock &BB) override;
68 void getAnalysisUsage(AnalysisUsage &AU) const override;
69
getPassName() const70 const char *getPassName() const override { return "LoadCombine"; }
71 static char ID;
72
73 typedef IRBuilder<true, TargetFolder> BuilderTy;
74
75 private:
76 BuilderTy *Builder;
77
78 PointerOffsetPair getPointerOffsetPair(LoadInst &);
79 bool combineLoads(DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &);
80 bool aggregateLoads(SmallVectorImpl<LoadPOPPair> &);
81 bool combineLoads(SmallVectorImpl<LoadPOPPair> &);
82 };
83 }
84
doInitialization(Function & F)85 bool LoadCombine::doInitialization(Function &F) {
86 DEBUG(dbgs() << "LoadCombine function: " << F.getName() << "\n");
87 C = &F.getContext();
88 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
89 if (!DLP) {
90 DEBUG(dbgs() << " Skipping LoadCombine -- no target data!\n");
91 return false;
92 }
93 DL = &DLP->getDataLayout();
94 return true;
95 }
96
getPointerOffsetPair(LoadInst & LI)97 PointerOffsetPair LoadCombine::getPointerOffsetPair(LoadInst &LI) {
98 PointerOffsetPair POP;
99 POP.Pointer = LI.getPointerOperand();
100 POP.Offset = 0;
101 while (isa<BitCastInst>(POP.Pointer) || isa<GetElementPtrInst>(POP.Pointer)) {
102 if (auto *GEP = dyn_cast<GetElementPtrInst>(POP.Pointer)) {
103 unsigned BitWidth = DL->getPointerTypeSizeInBits(GEP->getType());
104 APInt Offset(BitWidth, 0);
105 if (GEP->accumulateConstantOffset(*DL, Offset))
106 POP.Offset += Offset.getZExtValue();
107 else
108 // Can't handle GEPs with variable indices.
109 return POP;
110 POP.Pointer = GEP->getPointerOperand();
111 } else if (auto *BC = dyn_cast<BitCastInst>(POP.Pointer))
112 POP.Pointer = BC->getOperand(0);
113 }
114 return POP;
115 }
116
combineLoads(DenseMap<const Value *,SmallVector<LoadPOPPair,8>> & LoadMap)117 bool LoadCombine::combineLoads(
118 DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &LoadMap) {
119 bool Combined = false;
120 for (auto &Loads : LoadMap) {
121 if (Loads.second.size() < 2)
122 continue;
123 std::sort(Loads.second.begin(), Loads.second.end(),
124 [](const LoadPOPPair &A, const LoadPOPPair &B) {
125 return A.POP.Offset < B.POP.Offset;
126 });
127 if (aggregateLoads(Loads.second))
128 Combined = true;
129 }
130 return Combined;
131 }
132
133 /// \brief Try to aggregate loads from a sorted list of loads to be combined.
134 ///
135 /// It is guaranteed that no writes occur between any of the loads. All loads
136 /// have the same base pointer. There are at least two loads.
aggregateLoads(SmallVectorImpl<LoadPOPPair> & Loads)137 bool LoadCombine::aggregateLoads(SmallVectorImpl<LoadPOPPair> &Loads) {
138 assert(Loads.size() >= 2 && "Insufficient loads!");
139 LoadInst *BaseLoad = nullptr;
140 SmallVector<LoadPOPPair, 8> AggregateLoads;
141 bool Combined = false;
142 uint64_t PrevOffset = -1ull;
143 uint64_t PrevSize = 0;
144 for (auto &L : Loads) {
145 if (PrevOffset == -1ull) {
146 BaseLoad = L.Load;
147 PrevOffset = L.POP.Offset;
148 PrevSize = DL->getTypeStoreSize(L.Load->getType());
149 AggregateLoads.push_back(L);
150 continue;
151 }
152 if (L.Load->getAlignment() > BaseLoad->getAlignment())
153 continue;
154 if (L.POP.Offset > PrevOffset + PrevSize) {
155 // No other load will be combinable
156 if (combineLoads(AggregateLoads))
157 Combined = true;
158 AggregateLoads.clear();
159 PrevOffset = -1;
160 continue;
161 }
162 if (L.POP.Offset != PrevOffset + PrevSize)
163 // This load is offset less than the size of the last load.
164 // FIXME: We may want to handle this case.
165 continue;
166 PrevOffset = L.POP.Offset;
167 PrevSize = DL->getTypeStoreSize(L.Load->getType());
168 AggregateLoads.push_back(L);
169 }
170 if (combineLoads(AggregateLoads))
171 Combined = true;
172 return Combined;
173 }
174
175 /// \brief Given a list of combinable load. Combine the maximum number of them.
combineLoads(SmallVectorImpl<LoadPOPPair> & Loads)176 bool LoadCombine::combineLoads(SmallVectorImpl<LoadPOPPair> &Loads) {
177 // Remove loads from the end while the size is not a power of 2.
178 unsigned TotalSize = 0;
179 for (const auto &L : Loads)
180 TotalSize += L.Load->getType()->getPrimitiveSizeInBits();
181 while (TotalSize != 0 && !isPowerOf2_32(TotalSize))
182 TotalSize -= Loads.pop_back_val().Load->getType()->getPrimitiveSizeInBits();
183 if (Loads.size() < 2)
184 return false;
185
186 DEBUG({
187 dbgs() << "***** Combining Loads ******\n";
188 for (const auto &L : Loads) {
189 dbgs() << L.POP.Offset << ": " << *L.Load << "\n";
190 }
191 });
192
193 // Find first load. This is where we put the new load.
194 LoadPOPPair FirstLP;
195 FirstLP.InsertOrder = -1u;
196 for (const auto &L : Loads)
197 if (L.InsertOrder < FirstLP.InsertOrder)
198 FirstLP = L;
199
200 unsigned AddressSpace =
201 FirstLP.POP.Pointer->getType()->getPointerAddressSpace();
202
203 Builder->SetInsertPoint(FirstLP.Load);
204 Value *Ptr = Builder->CreateConstGEP1_64(
205 Builder->CreatePointerCast(Loads[0].POP.Pointer,
206 Builder->getInt8PtrTy(AddressSpace)),
207 Loads[0].POP.Offset);
208 LoadInst *NewLoad = new LoadInst(
209 Builder->CreatePointerCast(
210 Ptr, PointerType::get(IntegerType::get(Ptr->getContext(), TotalSize),
211 Ptr->getType()->getPointerAddressSpace())),
212 Twine(Loads[0].Load->getName()) + ".combined", false,
213 Loads[0].Load->getAlignment(), FirstLP.Load);
214
215 for (const auto &L : Loads) {
216 Builder->SetInsertPoint(L.Load);
217 Value *V = Builder->CreateExtractInteger(
218 *DL, NewLoad, cast<IntegerType>(L.Load->getType()),
219 L.POP.Offset - Loads[0].POP.Offset, "combine.extract");
220 L.Load->replaceAllUsesWith(V);
221 }
222
223 NumLoadsCombined = NumLoadsCombined + Loads.size();
224 return true;
225 }
226
runOnBasicBlock(BasicBlock & BB)227 bool LoadCombine::runOnBasicBlock(BasicBlock &BB) {
228 if (skipOptnoneFunction(BB) || !DL)
229 return false;
230
231 AA = &getAnalysis<AliasAnalysis>();
232
233 IRBuilder<true, TargetFolder>
234 TheBuilder(BB.getContext(), TargetFolder(DL));
235 Builder = &TheBuilder;
236
237 DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> LoadMap;
238 AliasSetTracker AST(*AA);
239
240 bool Combined = false;
241 unsigned Index = 0;
242 for (auto &I : BB) {
243 if (I.mayThrow() || (I.mayWriteToMemory() && AST.containsUnknown(&I))) {
244 if (combineLoads(LoadMap))
245 Combined = true;
246 LoadMap.clear();
247 AST.clear();
248 continue;
249 }
250 LoadInst *LI = dyn_cast<LoadInst>(&I);
251 if (!LI)
252 continue;
253 ++NumLoadsAnalyzed;
254 if (!LI->isSimple() || !LI->getType()->isIntegerTy())
255 continue;
256 auto POP = getPointerOffsetPair(*LI);
257 if (!POP.Pointer)
258 continue;
259 LoadMap[POP.Pointer].push_back(LoadPOPPair(LI, POP, Index++));
260 AST.add(LI);
261 }
262 if (combineLoads(LoadMap))
263 Combined = true;
264 return Combined;
265 }
266
getAnalysisUsage(AnalysisUsage & AU) const267 void LoadCombine::getAnalysisUsage(AnalysisUsage &AU) const {
268 AU.setPreservesCFG();
269
270 AU.addRequired<AliasAnalysis>();
271 AU.addPreserved<AliasAnalysis>();
272 }
273
274 char LoadCombine::ID = 0;
275
createLoadCombinePass()276 BasicBlockPass *llvm::createLoadCombinePass() {
277 return new LoadCombine();
278 }
279
280 INITIALIZE_PASS_BEGIN(LoadCombine, "load-combine", "Combine Adjacent Loads",
281 false, false)
282 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
283 INITIALIZE_PASS_END(LoadCombine, "load-combine", "Combine Adjacent Loads",
284 false, false)
285
286