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