tools/llvm-mca/LSUnit.cpp

   1 //===----------------------- LSUnit.cpp --------------------------*- C++-*-===//
   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 ///
  11 /// A Load-Store Unit for the llvm-mca tool.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "LSUnit.h"
  16 #include "Instruction.h"
  17 #include "llvm/Support/Debug.h"
  18 #include "llvm/Support/raw_ostream.h"
  19
  20 using namespace llvm;
  21
  22 #define DEBUG_TYPE "llvm-mca"
  23
  24 namespace mca {
  25
  26 #ifndef NDEBUG
  27 void LSUnit::dump() const {
  28   dbgs() << "[LSUnit] LQ_Size = " << LQ_Size << '\n';
  29   dbgs() << "[LSUnit] SQ_Size = " << SQ_Size << '\n';
  30   dbgs() << "[LSUnit] NextLQSlotIdx = " << LoadQueue.size() << '\n';
  31   dbgs() << "[LSUnit] NextSQSlotIdx = " << StoreQueue.size() << '\n';
  32 }
  33 #endif
  34
  35 void LSUnit::assignLQSlot(unsigned Index) {
  36   assert(!isLQFull());
  37   assert(LoadQueue.count(Index) == 0);
  38
  39   LLVM_DEBUG(dbgs() << "[LSUnit] - AssignLQSlot <Idx=" << Index
  40                     << ",slot=" << LoadQueue.size() << ">\n");
  41   LoadQueue.insert(Index);
  42 }
  43
  44 void LSUnit::assignSQSlot(unsigned Index) {
  45   assert(!isSQFull());
  46   assert(StoreQueue.count(Index) == 0);
  47
  48   LLVM_DEBUG(dbgs() << "[LSUnit] - AssignSQSlot <Idx=" << Index
  49                     << ",slot=" << StoreQueue.size() << ">\n");
  50   StoreQueue.insert(Index);
  51 }
  52
  53 bool LSUnit::reserve(const InstRef &IR) {
  54   const InstrDesc Desc = IR.getInstruction()->getDesc();
  55   unsigned MayLoad = Desc.MayLoad;
  56   unsigned MayStore = Desc.MayStore;
  57   unsigned IsMemBarrier = Desc.HasSideEffects;
  58   if (!MayLoad && !MayStore)
  59     return false;
  60
  61   const unsigned Index = IR.getSourceIndex();
  62   if (MayLoad) {
  63     if (IsMemBarrier)
  64       LoadBarriers.insert(Index);
  65     assignLQSlot(Index);
  66   }
  67   if (MayStore) {
  68     if (IsMemBarrier)
  69       StoreBarriers.insert(Index);
  70     assignSQSlot(Index);
  71   }
  72   return true;
  73 }
  74
  75 bool LSUnit::isReady(const InstRef &IR) const {
  76   const unsigned Index = IR.getSourceIndex();
  77   bool IsALoad = LoadQueue.count(Index) != 0;
  78   bool IsAStore = StoreQueue.count(Index) != 0;
  79   assert((IsALoad || IsAStore) && "Instruction is not in queue!");
  80
  81   unsigned LoadBarrierIndex = LoadBarriers.empty() ? 0 : *LoadBarriers.begin();
  82   unsigned StoreBarrierIndex =
  83       StoreBarriers.empty() ? 0 : *StoreBarriers.begin();
  84
  85   if (IsALoad && LoadBarrierIndex) {
  86     if (Index > LoadBarrierIndex)
  87       return false;
  88     if (Index == LoadBarrierIndex && Index != *LoadQueue.begin())
  89       return false;
  90   }
  91
  92   if (IsAStore && StoreBarrierIndex) {
  93     if (Index > StoreBarrierIndex)
  94       return false;
  95     if (Index == StoreBarrierIndex && Index != *StoreQueue.begin())
  96       return false;
  97   }
  98
  99   if (NoAlias && IsALoad)
 100     return true;
 101
 102   if (StoreQueue.size()) {
 103     // Check if this memory operation is younger than the older store.
 104     if (Index > *StoreQueue.begin())
 105       return false;
 106   }
 107
 108   // Okay, we are older than the oldest store in the queue.
 109   // If there are no pending loads, then we can say for sure that this
 110   // instruction is ready.
 111   if (isLQEmpty())
 112     return true;
 113
 114   // Check if there are no older loads.
 115   if (Index <= *LoadQueue.begin())
 116     return true;
 117
 118   // There is at least one younger load.
 119   return !IsAStore;
 120 }
 121
 122 void LSUnit::onInstructionExecuted(const InstRef &IR) {
 123   const unsigned Index = IR.getSourceIndex();
 124   std::set<unsigned>::iterator it = LoadQueue.find(Index);
 125   if (it != LoadQueue.end()) {
 126     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
 127                       << " has been removed from the load queue.\n");
 128     LoadQueue.erase(it);
 129   }
 130
 131   it = StoreQueue.find(Index);
 132   if (it != StoreQueue.end()) {
 133     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
 134                       << " has been removed from the store queue.\n");
 135     StoreQueue.erase(it);
 136   }
 137
 138   if (!StoreBarriers.empty() && Index == *StoreBarriers.begin())
 139     StoreBarriers.erase(StoreBarriers.begin());
 140   if (!LoadBarriers.empty() && Index == *LoadBarriers.begin())
 141     LoadBarriers.erase(LoadBarriers.begin());
 142 }
 143 } // namespace mca