lib/Transforms/Scalar/LoadCombine.cpp

   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/IR/Module.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/MathExtras.h"
  29 #include "llvm/Support/raw_ostream.h"
  30
  31 using namespace llvm;
  32
  33 #define DEBUG_TYPE "load-combine"
  34
  35 STATISTIC(NumLoadsAnalyzed, "Number of loads analyzed for combining");
  36 STATISTIC(NumLoadsCombined, "Number of loads combined");
  37
  38 namespace {
  39 struct PointerOffsetPair {
  40   Value *Pointer;
  41   uint64_t Offset;
  42 };
  43
  44 struct LoadPOPPair {
  45   LoadPOPPair(LoadInst *L, PointerOffsetPair P, unsigned O)
  46       : Load(L), POP(P), InsertOrder(O) {}
  47   LoadPOPPair() {}
  48   LoadInst *Load;
  49   PointerOffsetPair POP;
  50   /// \brief The new load needs to be created before the first load in IR order.
  51   unsigned InsertOrder;
  52 };
  53
  54 class LoadCombine : public BasicBlockPass {
  55   LLVMContext *C;
  56   const DataLayout *DL;
  57   AliasAnalysis *AA;
  58
  59 public:
  60   LoadCombine()
  61       : BasicBlockPass(ID),
  62         C(nullptr), DL(nullptr), AA(nullptr) {
  63     initializeSROAPass(*PassRegistry::getPassRegistry());
  64   }
  65
  66   using llvm::Pass::doInitialization;
  67   bool doInitialization(Function &) override;
  68   bool runOnBasicBlock(BasicBlock &BB) override;
  69   void getAnalysisUsage(AnalysisUsage &AU) const override;
  70
  71   const char *getPassName() const override { return "LoadCombine"; }
  72   static char ID;
  73
  74   typedef IRBuilder<true, TargetFolder> BuilderTy;
  75
  76 private:
  77   BuilderTy *Builder;
  78
  79   PointerOffsetPair getPointerOffsetPair(LoadInst &);
  80   bool combineLoads(DenseMap<const Value *, SmallVector<LoadPOPPair, 8>> &);
  81   bool aggregateLoads(SmallVectorImpl<LoadPOPPair> &);
  82   bool combineLoads(SmallVectorImpl<LoadPOPPair> &);
  83 };
  84 }
  85
  86 bool LoadCombine::doInitialization(Function &F) {
  87   DEBUG(dbgs() << "LoadCombine function: " << F.getName() << "\n");
  88   C = &F.getContext();
  89   DL = &F.getParent()->getDataLayout();
  90   if (!DL) {
  91     DEBUG(dbgs() << "  Skipping LoadCombine -- no target data!\n");
  92     return false;
  93   }
  94   return true;
  95 }
  96
  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
 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.
 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.
 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
 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
 267 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
 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