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 148
