1 //===- LoadCombine.cpp - Combine Adjacent Loads ---------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This transformation combines adjacent loads.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Scalar.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Analysis/TargetFolder.h"
19 #include "llvm/Pass.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/IRBuilder.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/MathExtras.h"
26 #include "llvm/Support/raw_ostream.h"
30 #define DEBUG_TYPE "load-combine"
32 STATISTIC(NumLoadsAnalyzed, "Number of loads analyzed for combining");
33 STATISTIC(NumLoadsCombined, "Number of loads combined");
36 struct PointerOffsetPair {
42 LoadPOPPair(LoadInst *L, PointerOffsetPair P, unsigned O)
43 : Load(L), POP(P), InsertOrder(O) {}
46 PointerOffsetPair POP;
47 /// \brief The new load needs to be created before the first load in IR order.
51 class LoadCombine : public BasicBlockPass {
58 C(nullptr), DL(nullptr) {
59 initializeSROAPass(*PassRegistry::getPassRegistry());
62 using llvm::Pass::doInitialization;
63 bool doInitialization(Function &) override;
64 bool runOnBasicBlock(BasicBlock &BB) override;
65 void getAnalysisUsage(AnalysisUsage &AU) const override;
67 const char *getPassName() const override { return "LoadCombine"; }
70 typedef IRBuilder<true, TargetFolder> BuilderTy;
75 PointerOffsetPair getPointerOffsetPair(LoadInst &);
76 bool combineLoads(DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &);
77 bool aggregateLoads(SmallVectorImpl<LoadPOPPair> &);
78 bool combineLoads(SmallVectorImpl<LoadPOPPair> &);
82 bool LoadCombine::doInitialization(Function &F) {
83 DEBUG(dbgs() << "LoadCombine function: " << F.getName() << "\n");
85 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
87 DEBUG(dbgs() << " Skipping LoadCombine -- no target data!\n");
90 DL = &DLP->getDataLayout();
94 PointerOffsetPair LoadCombine::getPointerOffsetPair(LoadInst &LI) {
95 PointerOffsetPair POP;
96 POP.Pointer = LI.getPointerOperand();
98 while (isa<BitCastInst>(POP.Pointer) || isa<GetElementPtrInst>(POP.Pointer)) {
99 if (auto *GEP = dyn_cast<GetElementPtrInst>(POP.Pointer)) {
100 unsigned BitWidth = DL->getPointerTypeSizeInBits(GEP->getType());
101 APInt Offset(BitWidth, 0);
102 if (GEP->accumulateConstantOffset(*DL, Offset))
103 POP.Offset += Offset.getZExtValue();
105 // Can't handle GEPs with variable indices.
107 POP.Pointer = GEP->getPointerOperand();
108 } else if (auto *BC = dyn_cast<BitCastInst>(POP.Pointer))
109 POP.Pointer = BC->getOperand(0);
114 bool LoadCombine::combineLoads(
115 DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &LoadMap) {
116 bool Combined = false;
117 for (auto &Loads : LoadMap) {
118 if (Loads.second.size() < 2)
120 std::sort(Loads.second.begin(), Loads.second.end(),
121 [](const LoadPOPPair &A, const LoadPOPPair &B) {
122 return A.POP.Offset < B.POP.Offset;
124 if (aggregateLoads(Loads.second))
130 /// \brief Try to aggregate loads from a sorted list of loads to be combined.
132 /// It is guaranteed that no writes occur between any of the loads. All loads
133 /// have the same base pointer. There are at least two loads.
134 bool LoadCombine::aggregateLoads(SmallVectorImpl<LoadPOPPair> &Loads) {
135 assert(Loads.size() >= 2 && "Insufficient loads!");
136 LoadInst *BaseLoad = nullptr;
137 SmallVector<LoadPOPPair, 8> AggregateLoads;
138 bool Combined = false;
139 uint64_t PrevOffset = -1ull;
140 uint64_t PrevSize = 0;
141 for (auto &L : Loads) {
142 if (PrevOffset == -1ull) {
144 PrevOffset = L.POP.Offset;
145 PrevSize = DL->getTypeStoreSize(L.Load->getType());
146 AggregateLoads.push_back(L);
149 if (L.Load->getAlignment() > BaseLoad->getAlignment())
151 if (L.POP.Offset > PrevOffset + PrevSize) {
152 // No other load will be combinable
153 if (combineLoads(AggregateLoads))
155 AggregateLoads.clear();
159 if (L.POP.Offset != PrevOffset + PrevSize)
160 // This load is offset less than the size of the last load.
161 // FIXME: We may want to handle this case.
163 PrevOffset = L.POP.Offset;
164 PrevSize = DL->getTypeStoreSize(L.Load->getType());
165 AggregateLoads.push_back(L);
167 if (combineLoads(AggregateLoads))
172 /// \brief Given a list of combinable load. Combine the maximum number of them.
173 bool LoadCombine::combineLoads(SmallVectorImpl<LoadPOPPair> &Loads) {
174 // Remove loads from the end while the size is not a power of 2.
175 unsigned TotalSize = 0;
176 for (const auto &L : Loads)
177 TotalSize += L.Load->getType()->getPrimitiveSizeInBits();
178 while (TotalSize != 0 && !isPowerOf2_32(TotalSize))
179 TotalSize -= Loads.pop_back_val().Load->getType()->getPrimitiveSizeInBits();
180 if (Loads.size() < 2)
184 dbgs() << "***** Combining Loads ******\n";
185 for (const auto &L : Loads) {
186 dbgs() << L.POP.Offset << ": " << *L.Load << "\n";
190 // Find first load. This is where we put the new load.
192 FirstLP.InsertOrder = -1u;
193 for (const auto &L : Loads)
194 if (L.InsertOrder < FirstLP.InsertOrder)
197 unsigned AddressSpace =
198 FirstLP.POP.Pointer->getType()->getPointerAddressSpace();
200 Builder->SetInsertPoint(FirstLP.Load);
201 Value *Ptr = Builder->CreateConstGEP1_64(
202 Builder->CreatePointerCast(Loads[0].POP.Pointer,
203 Builder->getInt8PtrTy(AddressSpace)),
204 Loads[0].POP.Offset);
205 LoadInst *NewLoad = new LoadInst(
206 Builder->CreatePointerCast(
207 Ptr, PointerType::get(IntegerType::get(Ptr->getContext(), TotalSize),
208 Ptr->getType()->getPointerAddressSpace())),
209 Twine(Loads[0].Load->getName()) + ".combined", false,
210 Loads[0].Load->getAlignment(), FirstLP.Load);
212 for (const auto &L : Loads) {
213 Builder->SetInsertPoint(L.Load);
214 Value *V = Builder->CreateExtractInteger(
215 *DL, NewLoad, cast<IntegerType>(L.Load->getType()),
216 L.POP.Offset - Loads[0].POP.Offset, "combine.extract");
217 L.Load->replaceAllUsesWith(V);
220 NumLoadsCombined = NumLoadsCombined + Loads.size();
224 bool LoadCombine::runOnBasicBlock(BasicBlock &BB) {
225 if (skipOptnoneFunction(BB) || !DL)
228 IRBuilder<true, TargetFolder>
229 TheBuilder(BB.getContext(), TargetFolder(DL));
230 Builder = &TheBuilder;
232 DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> LoadMap;
234 bool Combined = false;
237 if (I.mayWriteToMemory() || I.mayThrow()) {
238 if (combineLoads(LoadMap))
243 LoadInst *LI = dyn_cast<LoadInst>(&I);
247 if (!LI->isSimple() || !LI->getType()->isIntegerTy())
249 auto POP = getPointerOffsetPair(*LI);
252 LoadMap[POP.Pointer].push_back(LoadPOPPair(LI, POP, Index++));
254 if (combineLoads(LoadMap))
259 void LoadCombine::getAnalysisUsage(AnalysisUsage &AU) const {
260 AU.setPreservesCFG();
263 char LoadCombine::ID = 0;
265 BasicBlockPass *llvm::createLoadCombinePass() {
266 return new LoadCombine();
269 INITIALIZE_PASS(LoadCombine, "load-combine", "Combine Adjacent Loads", false,