LLVM  10.0.0svn
LSUnit.cpp
Go to the documentation of this file.
1 //===----------------------- LSUnit.cpp --------------------------*- C++-*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
10 /// A Load-Store Unit for the llvm-mca tool.
11 ///
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/MCA/Instruction.h"
16 #include "llvm/Support/Debug.h"
18 
19 #define DEBUG_TYPE "llvm-mca"
20 
21 namespace llvm {
22 namespace mca {
23 
24 LSUnitBase::LSUnitBase(const MCSchedModel &SM, unsigned LQ, unsigned SQ,
25  bool AssumeNoAlias)
26  : LQSize(LQ), SQSize(SQ), UsedLQEntries(0), UsedSQEntries(0),
27  NoAlias(AssumeNoAlias), NextGroupID(1) {
28  if (SM.hasExtraProcessorInfo()) {
30  if (!LQSize && EPI.LoadQueueID) {
31  const MCProcResourceDesc &LdQDesc = *SM.getProcResource(EPI.LoadQueueID);
32  LQSize = LdQDesc.BufferSize;
33  }
34 
35  if (!SQSize && EPI.StoreQueueID) {
36  const MCProcResourceDesc &StQDesc = *SM.getProcResource(EPI.StoreQueueID);
37  SQSize = StQDesc.BufferSize;
38  }
39  }
40 }
41 
43 
45  for (const std::pair<unsigned, std::unique_ptr<MemoryGroup>> &G : Groups)
46  G.second->cycleEvent();
47 }
48 
49 #ifndef NDEBUG
50 void LSUnitBase::dump() const {
51  dbgs() << "[LSUnit] LQ_Size = " << getLoadQueueSize() << '\n';
52  dbgs() << "[LSUnit] SQ_Size = " << getStoreQueueSize() << '\n';
53  dbgs() << "[LSUnit] NextLQSlotIdx = " << getUsedLQEntries() << '\n';
54  dbgs() << "[LSUnit] NextSQSlotIdx = " << getUsedSQEntries() << '\n';
55  dbgs() << "\n";
56  for (const auto &GroupIt : Groups) {
57  const MemoryGroup &Group = *GroupIt.second;
58  dbgs() << "[LSUnit] Group (" << GroupIt.first << "): "
59  << "[ #Preds = " << Group.getNumPredecessors()
60  << ", #GIssued = " << Group.getNumExecutingPredecessors()
61  << ", #GExecuted = " << Group.getNumExecutedPredecessors()
62  << ", #Inst = " << Group.getNumInstructions()
63  << ", #IIssued = " << Group.getNumExecuting()
64  << ", #IExecuted = " << Group.getNumExecuted() << '\n';
65  }
66 }
67 #endif
68 
69 unsigned LSUnit::dispatch(const InstRef &IR) {
70  const InstrDesc &Desc = IR.getInstruction()->getDesc();
71  unsigned IsMemBarrier = Desc.HasSideEffects;
72  assert((Desc.MayLoad || Desc.MayStore) && "Not a memory operation!");
73 
74  if (Desc.MayLoad)
75  assignLQSlot();
76  if (Desc.MayStore)
77  assignSQSlot();
78 
79  if (Desc.MayStore) {
80  // Always create a new group for store operations.
81 
82  // A store may not pass a previous store or store barrier.
83  unsigned NewGID = createMemoryGroup();
84  MemoryGroup &NewGroup = getGroup(NewGID);
85  NewGroup.addInstruction();
86 
87  // A store may not pass a previous load or load barrier.
88  unsigned ImmediateLoadDominator =
89  std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
90  if (ImmediateLoadDominator) {
91  MemoryGroup &IDom = getGroup(ImmediateLoadDominator);
92  LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
93  << ") --> (" << NewGID << ")\n");
94  IDom.addSuccessor(&NewGroup);
95  }
96  if (CurrentStoreGroupID) {
97  MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
98  LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
99  << ") --> (" << NewGID << ")\n");
100  StoreGroup.addSuccessor(&NewGroup);
101  }
102 
103  CurrentStoreGroupID = NewGID;
104  if (Desc.MayLoad) {
105  CurrentLoadGroupID = NewGID;
106  if (IsMemBarrier)
107  CurrentLoadBarrierGroupID = NewGID;
108  }
109 
110  return NewGID;
111  }
112 
113  assert(Desc.MayLoad && "Expected a load!");
114 
115  // Always create a new memory group if this is the first load of the sequence.
116 
117  // A load may not pass a previous store unless flag 'NoAlias' is set.
118  // A load may pass a previous load.
119  // A younger load cannot pass a older load barrier.
120  // A load barrier cannot pass a older load.
121  bool ShouldCreateANewGroup = !CurrentLoadGroupID || IsMemBarrier ||
122  CurrentLoadGroupID <= CurrentStoreGroupID ||
123  CurrentLoadGroupID <= CurrentLoadBarrierGroupID;
124  if (ShouldCreateANewGroup) {
125  unsigned NewGID = createMemoryGroup();
126  MemoryGroup &NewGroup = getGroup(NewGID);
127  NewGroup.addInstruction();
128 
129  if (!assumeNoAlias() && CurrentStoreGroupID) {
130  MemoryGroup &StGroup = getGroup(CurrentStoreGroupID);
131  LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
132  << ") --> (" << NewGID << ")\n");
133  StGroup.addSuccessor(&NewGroup);
134  }
135  if (CurrentLoadBarrierGroupID) {
136  MemoryGroup &LdGroup = getGroup(CurrentLoadBarrierGroupID);
137  LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentLoadBarrierGroupID
138  << ") --> (" << NewGID << ")\n");
139  LdGroup.addSuccessor(&NewGroup);
140  }
141 
142  CurrentLoadGroupID = NewGID;
143  if (IsMemBarrier)
144  CurrentLoadBarrierGroupID = NewGID;
145  return NewGID;
146  }
147 
148  MemoryGroup &Group = getGroup(CurrentLoadGroupID);
149  Group.addInstruction();
150  return CurrentLoadGroupID;
151 }
152 
154  const InstrDesc &Desc = IR.getInstruction()->getDesc();
155  if (Desc.MayLoad && isLQFull())
157  if (Desc.MayStore && isSQFull())
159  return LSUnit::LSU_AVAILABLE;
160 }
161 
163  const InstrDesc &Desc = IR.getInstruction()->getDesc();
164  bool IsALoad = Desc.MayLoad;
165  bool IsAStore = Desc.MayStore;
166  assert((IsALoad || IsAStore) && "Expected a memory operation!");
167 
168  unsigned GroupID = IR.getInstruction()->getLSUTokenID();
169  auto It = Groups.find(GroupID);
170  It->second->onInstructionExecuted();
171  if (It->second->isExecuted()) {
172  Groups.erase(It);
173  }
174 
175  if (IsALoad) {
176  UsedLQEntries--;
177  LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
178  << " has been removed from the load queue.\n");
179  }
180 
181  if (IsAStore) {
182  UsedSQEntries--;
183  LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
184  << " has been removed from the store queue.\n");
185  }
186 }
187 
189  const Instruction &IS = *IR.getInstruction();
190  if (!IS.isMemOp())
191  return;
192 
194  unsigned GroupID = IS.getLSUTokenID();
195  if (!isValidGroupID(GroupID)) {
196  if (GroupID == CurrentLoadGroupID)
197  CurrentLoadGroupID = 0;
198  if (GroupID == CurrentStoreGroupID)
199  CurrentStoreGroupID = 0;
200  if (GroupID == CurrentLoadBarrierGroupID)
201  CurrentLoadBarrierGroupID = 0;
202  }
203 }
204 
205 } // namespace mca
206 } // namespace llvm
Instruction * getInstruction()
Definition: Instruction.h:575
LSUnitBase(const MCSchedModel &SM, unsigned LoadQueueSize, unsigned StoreQueueSize, bool AssumeNoAlias)
Definition: LSUnit.cpp:24
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:444
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
unsigned assignLQSlot()
Definition: LSUnit.h:212
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isValidGroupID(unsigned Index) const
Definition: LSUnit.h:243
unsigned getLoadQueueSize() const
Returns the total number of entries in the load queue.
Definition: LSUnit.h:205
unsigned getNumInstructions() const
Definition: LSUnit.h:69
const MCProcResourceDesc * getProcResource(unsigned ProcResourceIdx) const
Definition: MCSchedule.h:339
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:561
A node of a memory dependency graph.
Definition: LSUnit.h:37
A Load/Store unit class that models load/store queues and that implements a simple weak memory consis...
virtual ~LSUnitBase()
Definition: LSUnit.cpp:42
virtual void cycleEvent()
Definition: LSUnit.cpp:44
unsigned getSourceIndex() const
Definition: Instruction.h:574
bool isSQFull() const
Definition: LSUnit.h:240
virtual void onInstructionExecuted(const InstRef &IR)
Definition: LSUnit.cpp:162
unsigned createMemoryGroup()
Definition: LSUnit.h:286
bool isLQFull() const
Definition: LSUnit.h:241
unsigned dispatch(const InstRef &IR) override
Allocates LS resources for instruction IR.
Definition: LSUnit.cpp:69
unsigned getUsedLQEntries() const
Definition: LSUnit.h:210
Provide extra details about the machine processor.
Definition: MCSchedule.h:177
unsigned getLSUTokenID() const
Definition: Instruction.h:498
bool assumeNoAlias() const
Definition: LSUnit.h:215
void onInstructionExecuted(const InstRef &IR) override
Definition: LSUnit.cpp:188
unsigned getNumExecuted() const
Definition: LSUnit.h:71
unsigned assignSQSlot()
Definition: LSUnit.h:213
const InstrDesc & getDesc() const
Definition: Instruction.h:417
unsigned getNumExecutingPredecessors() const
Definition: LSUnit.h:63
bool hasExtraProcessorInfo() const
Definition: MCSchedule.h:315
Status isAvailable(const InstRef &IR) const override
Returns LSU_AVAILABLE if there are enough load/store queue entries to accomodate instruction IR...
Definition: LSUnit.cpp:153
unsigned getNumExecutedPredecessors() const
Definition: LSUnit.h:66
void dump() const
Definition: LSUnit.cpp:50
unsigned getUsedSQEntries() const
Definition: LSUnit.h:211
Define a kind of processor resource that will be modeled by the scheduler.
Definition: MCSchedule.h:32
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
void addSuccessor(MemoryGroup *Group)
Definition: LSUnit.h:80
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned getNumExecuting() const
Definition: LSUnit.h:70
unsigned getNumPredecessors() const
Definition: LSUnit.h:62
unsigned getStoreQueueSize() const
Returns the total number of entries in the store queue.
Definition: LSUnit.h:208
An instruction descriptor.
Definition: Instruction.h:347
This file defines abstractions used by the Pipeline to model register reads, register writes and inst...
const MCExtraProcessorInfo & getExtraProcessorInfo() const
Definition: MCSchedule.h:322
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:244
Statically lint checks LLVM IR
Definition: Lint.cpp:192
const MemoryGroup & getGroup(unsigned Index) const
Definition: LSUnit.h:276