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