contrib/llvm/tools/llvm-mca/LSUnit.h

   1 //===------------------------- LSUnit.h --------------------------*- 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 class that models load/store queues and that implements
  12 /// a simple weak memory consistency model.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_TOOLS_LLVM_MCA_LSUNIT_H
  17 #define LLVM_TOOLS_LLVM_MCA_LSUNIT_H
  18
  19 #include <set>
  20
  21 namespace mca {
  22
  23 class InstRef;
  24 struct InstrDesc;
  25
  26 /// A Load/Store Unit implementing a load and store queues.
  27 ///
  28 /// This class implements a load queue and a store queue to emulate the
  29 /// out-of-order execution of memory operations.
  30 /// Each load (or store) consumes an entry in the load (or store) queue.
  31 ///
  32 /// Rules are:
  33 /// 1) A younger load is allowed to pass an older load only if there are no
  34 ///    stores nor barriers in between the two loads.
  35 /// 2) An younger store is not allowed to pass an older store.
  36 /// 3) A younger store is not allowed to pass an older load.
  37 /// 4) A younger load is allowed to pass an older store only if the load does
  38 ///    not alias with the store.
  39 ///
  40 /// This class optimistically assumes that loads don't alias store operations.
  41 /// Under this assumption, younger loads are always allowed to pass older
  42 /// stores (this would only affects rule 4).
  43 /// Essentially, this LSUnit doesn't attempt to run any sort alias analysis to
  44 /// predict when loads and stores don't alias with eachother.
  45 ///
  46 /// To enforce aliasing between loads and stores, flag `AssumeNoAlias` must be
  47 /// set to `false` by the constructor of LSUnit.
  48 ///
  49 /// In the case of write-combining memory, rule 2. could be relaxed to allow
  50 /// reordering of non-aliasing store operations. At the moment, this is not
  51 /// allowed.
  52 /// To put it in another way, there is no option to specify a different memory
  53 /// type for memory operations (example: write-through, write-combining, etc.).
  54 /// Also, there is no way to weaken the memory model, and this unit currently
  55 /// doesn't support write-combining behavior.
  56 ///
  57 /// No assumptions are made on the size of the store buffer.
  58 /// As mentioned before, this class doesn't perform alias analysis.
  59 /// Consequently,  LSUnit doesn't know how to identify cases where
  60 /// store-to-load forwarding may occur.
  61 ///
  62 /// LSUnit doesn't attempt to predict whether a load or store hits or misses
  63 /// the L1 cache. To be more specific, LSUnit doesn't know anything about
  64 /// the cache hierarchy and memory types.
  65 /// It only knows if an instruction "mayLoad" and/or "mayStore". For loads, the
  66 /// scheduling model provides an "optimistic" load-to-use latency (which usually
  67 /// matches the load-to-use latency for when there is a hit in the L1D).
  68 ///
  69 /// Class MCInstrDesc in LLVM doesn't know about serializing operations, nor
  70 /// memory-barrier like instructions.
  71 /// LSUnit conservatively assumes that an instruction which `mayLoad` and has
  72 /// `unmodeled side effects` behave like a "soft" load-barrier. That means, it
  73 /// serializes loads without forcing a flush of the load queue.
  74 /// Similarly, instructions that both `mayStore` and have `unmodeled side
  75 /// effects` are treated like store barriers. A full memory
  76 /// barrier is a 'mayLoad' and 'mayStore' instruction with unmodeled side
  77 /// effects. This is obviously inaccurate, but this is the best that we can do
  78 /// at the moment.
  79 ///
  80 /// Each load/store barrier consumes one entry in the load/store queue. A
  81 /// load/store barrier enforces ordering of loads/stores:
  82 ///  - A younger load cannot pass a load barrier.
  83 ///  - A younger store cannot pass a store barrier.
  84 ///
  85 /// A younger load has to wait for the memory load barrier to execute.
  86 /// A load/store barrier is "executed" when it becomes the oldest entry in
  87 /// the load/store queue(s). That also means, all the older loads/stores have
  88 /// already been executed.
  89 class LSUnit {
  90   // Load queue size.
  91   // LQ_Size == 0 means that there are infinite slots in the load queue.
  92   unsigned LQ_Size;
  93
  94   // Store queue size.
  95   // SQ_Size == 0 means that there are infinite slots in the store queue.
  96   unsigned SQ_Size;
  97
  98   // If true, loads will never alias with stores. This is the default.
  99   bool NoAlias;
 100
 101   std::set<unsigned> LoadQueue;
 102   std::set<unsigned> StoreQueue;
 103
 104   void assignLQSlot(unsigned Index);
 105   void assignSQSlot(unsigned Index);
 106   bool isReadyNoAlias(unsigned Index) const;
 107
 108   // An instruction that both 'mayStore' and 'HasUnmodeledSideEffects' is
 109   // conservatively treated as a store barrier. It forces older store to be
 110   // executed before newer stores are issued.
 111   std::set<unsigned> StoreBarriers;
 112
 113   // An instruction that both 'MayLoad' and 'HasUnmodeledSideEffects' is
 114   // conservatively treated as a load barrier. It forces older loads to execute
 115   // before newer loads are issued.
 116   std::set<unsigned> LoadBarriers;
 117
 118 public:
 119   LSUnit(unsigned LQ = 0, unsigned SQ = 0, bool AssumeNoAlias = false)
 120       : LQ_Size(LQ), SQ_Size(SQ), NoAlias(AssumeNoAlias) {}
 121
 122 #ifndef NDEBUG
 123   void dump() const;
 124 #endif
 125
 126   bool isSQEmpty() const { return StoreQueue.empty(); }
 127   bool isLQEmpty() const { return LoadQueue.empty(); }
 128   bool isSQFull() const { return SQ_Size != 0 && StoreQueue.size() == SQ_Size; }
 129   bool isLQFull() const { return LQ_Size != 0 && LoadQueue.size() == LQ_Size; }
 130
 131   // Returns true if this instruction has been successfully enqueued.
 132   bool reserve(const InstRef &IR);
 133
 134   // The rules are:
 135   // 1. A store may not pass a previous store.
 136   // 2. A load may not pass a previous store unless flag 'NoAlias' is set.
 137   // 3. A load may pass a previous load.
 138   // 4. A store may not pass a previous load (regardless of flag 'NoAlias').
 139   // 5. A load has to wait until an older load barrier is fully executed.
 140   // 6. A store has to wait until an older store barrier is fully executed.
 141   bool isReady(const InstRef &IR) const;
 142   void onInstructionExecuted(const InstRef &IR);
 143 };
 144
 145 } // namespace mca
 146
 147 #endif