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
14#include "llvm/MCA/HardwareUnits/LSUnit.h"
15#include "llvm/MCA/Instruction.h"
16#include "llvm/Support/Debug.h"
17#include "llvm/Support/raw_ostream.h"
18
19#define DEBUG_TYPE "llvm-mca"
20
21namespace llvm {
22namespace mca {
23
24LSUnitBase::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()) {
29    const MCExtraProcessorInfo &EPI = SM.getExtraProcessorInfo();
30    if (!LQSize && EPI.LoadQueueID) {
31      const MCProcResourceDesc &LdQDesc = *SM.getProcResource(EPI.LoadQueueID);
32      LQSize = std::max(0, LdQDesc.BufferSize);
33    }
34
35    if (!SQSize && EPI.StoreQueueID) {
36      const MCProcResourceDesc &StQDesc = *SM.getProcResource(EPI.StoreQueueID);
37      SQSize = std::max(0, StQDesc.BufferSize);
38    }
39  }
40}
41
42LSUnitBase::~LSUnitBase() = default;
43
44void LSUnitBase::cycleEvent() {
45  for (const std::pair<unsigned, std::unique_ptr<MemoryGroup>> &G : Groups)
46    G.second->cycleEvent();
47}
48
49#ifndef NDEBUG
50void 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
69unsigned LSUnit::dispatch(const InstRef &IR) {
70  const Instruction &IS = *IR.getInstruction();
71  bool IsStoreBarrier = IS.isAStoreBarrier();
72  bool IsLoadBarrier = IS.isALoadBarrier();
73  assert((IS.getMayLoad() || IS.getMayStore()) && "Not a memory operation!");
74
75  if (IS.getMayLoad())
76    acquireLQSlot();
77  if (IS.getMayStore())
78    acquireSQSlot();
79
80  if (IS.getMayStore()) {
81    unsigned NewGID = createMemoryGroup();
82    MemoryGroup &NewGroup = getGroup(NewGID);
83    NewGroup.addInstruction();
84
85    // A store may not pass a previous load or load barrier.
86    unsigned ImmediateLoadDominator =
87        std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
88    if (ImmediateLoadDominator) {
89      MemoryGroup &IDom = getGroup(ImmediateLoadDominator);
90      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
91                        << ") --> (" << NewGID << ")\n");
92      IDom.addSuccessor(&NewGroup, !assumeNoAlias());
93    }
94
95    // A store may not pass a previous store barrier.
96    if (CurrentStoreBarrierGroupID) {
97      MemoryGroup &StoreGroup = getGroup(CurrentStoreBarrierGroupID);
98      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
99                        << CurrentStoreBarrierGroupID
100                        << ") --> (" << NewGID << ")\n");
101      StoreGroup.addSuccessor(&NewGroup, true);
102    }
103
104    // A store may not pass a previous store.
105    if (CurrentStoreGroupID &&
106        (CurrentStoreGroupID != CurrentStoreBarrierGroupID)) {
107      MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
108      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
109                        << ") --> (" << NewGID << ")\n");
110      StoreGroup.addSuccessor(&NewGroup, !assumeNoAlias());
111    }
112
113
114    CurrentStoreGroupID = NewGID;
115    if (IsStoreBarrier)
116      CurrentStoreBarrierGroupID = NewGID;
117
118    if (IS.getMayLoad()) {
119      CurrentLoadGroupID = NewGID;
120      if (IsLoadBarrier)
121        CurrentLoadBarrierGroupID = NewGID;
122    }
123
124    return NewGID;
125  }
126
127  assert(IS.getMayLoad() && "Expected a load!");
128
129  unsigned ImmediateLoadDominator =
130      std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
131
132  // A new load group is created if we are in one of the following situations:
133  // 1) This is a load barrier (by construction, a load barrier is always
134  //    assigned to a different memory group).
135  // 2) There is no load in flight (by construction we always keep loads and
136  //    stores into separate memory groups).
137  // 3) There is a load barrier in flight. This load depends on it.
138  // 4) There is an intervening store between the last load dispatched to the
139  //    LSU and this load. We always create a new group even if this load
140  //    does not alias the last dispatched store.
141  // 5) There is no intervening store and there is an active load group.
142  //    However that group has already started execution, so we cannot add
143  //    this load to it.
144  bool ShouldCreateANewGroup =
145      IsLoadBarrier || !ImmediateLoadDominator ||
146      CurrentLoadBarrierGroupID == ImmediateLoadDominator ||
147      ImmediateLoadDominator <= CurrentStoreGroupID ||
148      getGroup(ImmediateLoadDominator).isExecuting();
149
150  if (ShouldCreateANewGroup) {
151    unsigned NewGID = createMemoryGroup();
152    MemoryGroup &NewGroup = getGroup(NewGID);
153    NewGroup.addInstruction();
154
155    // A load may not pass a previous store or store barrier
156    // unless flag 'NoAlias' is set.
157    if (!assumeNoAlias() && CurrentStoreGroupID) {
158      MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
159      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
160                        << ") --> (" << NewGID << ")\n");
161      StoreGroup.addSuccessor(&NewGroup, true);
162    }
163
164    // A load barrier may not pass a previous load or load barrier.
165    if (IsLoadBarrier) {
166      if (ImmediateLoadDominator) {
167        MemoryGroup &LoadGroup = getGroup(ImmediateLoadDominator);
168        LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
169                          << ImmediateLoadDominator
170                          << ") --> (" << NewGID << ")\n");
171        LoadGroup.addSuccessor(&NewGroup, true);
172      }
173    } else {
174      // A younger load cannot pass a older load barrier.
175      if (CurrentLoadBarrierGroupID) {
176        MemoryGroup &LoadGroup = getGroup(CurrentLoadBarrierGroupID);
177        LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
178                          << CurrentLoadBarrierGroupID
179                          << ") --> (" << NewGID << ")\n");
180        LoadGroup.addSuccessor(&NewGroup, true);
181      }
182    }
183
184    CurrentLoadGroupID = NewGID;
185    if (IsLoadBarrier)
186      CurrentLoadBarrierGroupID = NewGID;
187    return NewGID;
188  }
189
190  // A load may pass a previous load.
191  MemoryGroup &Group = getGroup(CurrentLoadGroupID);
192  Group.addInstruction();
193  return CurrentLoadGroupID;
194}
195
196LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
197  const Instruction &IS = *IR.getInstruction();
198  if (IS.getMayLoad() && isLQFull())
199    return LSUnit::LSU_LQUEUE_FULL;
200  if (IS.getMayStore() && isSQFull())
201    return LSUnit::LSU_SQUEUE_FULL;
202  return LSUnit::LSU_AVAILABLE;
203}
204
205void LSUnitBase::onInstructionExecuted(const InstRef &IR) {
206  unsigned GroupID = IR.getInstruction()->getLSUTokenID();
207  auto It = Groups.find(GroupID);
208  assert(It != Groups.end() && "Instruction not dispatched to the LS unit");
209  It->second->onInstructionExecuted(IR);
210  if (It->second->isExecuted())
211    Groups.erase(It);
212}
213
214void LSUnitBase::onInstructionRetired(const InstRef &IR) {
215  const Instruction &IS = *IR.getInstruction();
216  bool IsALoad = IS.getMayLoad();
217  bool IsAStore = IS.getMayStore();
218  assert((IsALoad || IsAStore) && "Expected a memory operation!");
219
220  if (IsALoad) {
221    releaseLQSlot();
222    LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
223                      << " has been removed from the load queue.\n");
224  }
225
226  if (IsAStore) {
227    releaseSQSlot();
228    LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
229                      << " has been removed from the store queue.\n");
230  }
231}
232
233void LSUnit::onInstructionExecuted(const InstRef &IR) {
234  const Instruction &IS = *IR.getInstruction();
235  if (!IS.isMemOp())
236    return;
237
238  LSUnitBase::onInstructionExecuted(IR);
239  unsigned GroupID = IS.getLSUTokenID();
240  if (!isValidGroupID(GroupID)) {
241    if (GroupID == CurrentLoadGroupID)
242      CurrentLoadGroupID = 0;
243    if (GroupID == CurrentStoreGroupID)
244      CurrentStoreGroupID = 0;
245    if (GroupID == CurrentLoadBarrierGroupID)
246      CurrentLoadBarrierGroupID = 0;
247    if (GroupID == CurrentStoreBarrierGroupID)
248      CurrentStoreBarrierGroupID = 0;
249  }
250}
251
252} // namespace mca
253} // namespace llvm
254