Gabe Black has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/38386 )
Change subject: cpu: Factor MaxInst(SrcDest)Regs out of the trace CPU.
......................................................................
cpu: Factor MaxInst(SrcDest)Regs out of the trace CPU.
Manage register and ROB dependencies using lists instead of arrays to
better support random removals, and avoid having to know the global
maximum number of registers in an instruction.
Change-Id: Ie9f30c61bac52ad31745a1011f62c95622908d2f
---
M src/cpu/trace/trace_cpu.cc
M src/cpu/trace/trace_cpu.hh
2 files changed, 45 insertions(+), 101 deletions(-)
diff --git a/src/cpu/trace/trace_cpu.cc b/src/cpu/trace/trace_cpu.cc
index c9b9944..2daa0cf 100644
--- a/src/cpu/trace/trace_cpu.cc
+++ b/src/cpu/trace/trace_cpu.cc
@@ -308,15 +308,15 @@
}
// Annotate the ROB dependencies of the new node onto the parent
nodes.
- addDepsOnParent(new_node, new_node->robDep, new_node->numRobDep);
+ addDepsOnParent(new_node, new_node->robDep);
// Annotate the register dependencies of the new node onto the
parent
// nodes.
- addDepsOnParent(new_node, new_node->regDep, new_node->numRegDep);
+ addDepsOnParent(new_node, new_node->regDep);
num_read++;
// Add to map
depGraph[new_node->seqNum] = new_node;
- if (new_node->numRobDep == 0 && new_node->numRegDep == 0) {
+ if (new_node->robDep.empty() && new_node->regDep.empty()) {
// Source dependencies are already complete, check if resources
// are available and issue. The execution time is approximated
// to current time plus the computational delay.
@@ -331,18 +331,12 @@
template<typename T>
void
-TraceCPU::ElasticDataGen::addDepsOnParent(GraphNode *new_node,
- T& dep_array, uint8_t& num_dep)
+TraceCPU::ElasticDataGen::addDepsOnParent(GraphNode *new_node, T& dep_list)
{
- for (auto& a_dep : dep_array) {
- // The convention is to set the dependencies starting with the
first
- // index in the ROB and register dependency arrays. Thus, when we
reach
- // a dependency equal to the initialisation value of zero, we know
have
- // iterated over all dependencies and can break.
- if (a_dep == 0)
- break;
+ auto dep_it = dep_list.begin();
+ while (dep_it != dep_list.end()) {
// We look up the valid dependency, i.e. the parent of this node
- auto parent_itr = depGraph.find(a_dep);
+ auto parent_itr = depGraph.find(*dep_it);
if (parent_itr != depGraph.end()) {
// If the parent is found, it is yet to be executed. Append a
// pointer to the new node to the dependents list of the parent
@@ -351,12 +345,12 @@
auto num_depts = parent_itr->second->dependents.size();
elasticStats.maxDependents = std::max<double>(num_depts,
elasticStats.maxDependents.value());
+ dep_it++;
} else {
// The dependency is not found in the graph. So consider
// the execution of the parent is complete, i.e. remove this
// dependency.
- a_dep = 0;
- num_dep--;
+ dep_it = dep_list.erase(dep_it);
}
}
}
@@ -449,8 +443,8 @@
(*child_itr)->removeRobDep(node_ptr->seqNum)) {
// Check if the child node has become dependency free
- if ((*child_itr)->numRobDep == 0 &&
- (*child_itr)->numRegDep == 0) {
+ if ((*child_itr)->robDep.empty() == 0 &&
+ (*child_itr)->regDep.empty() == 0) {
// Source dependencies are complete, check if
// resources are available and issue
@@ -637,7 +631,7 @@
TraceCPU::ElasticDataGen::checkAndIssue(const GraphNode* node_ptr, bool
first)
{
// Assert the node is dependency-free
- assert(node_ptr->numRobDep == 0 && node_ptr->numRegDep == 0);
+ assert(node_ptr->robDep.empty() && node_ptr->regDep.empty());
// If this is the first attempt, print a debug message to indicate
this.
if (first) {
@@ -1219,28 +1213,23 @@
element->compDelay = pkt_msg.comp_delay() * timeMultiplier;
// Repeated field robDepList
- element->clearRobDep();
- assert((pkt_msg.rob_dep()).size() <= element->maxRobDep);
+ element->robDep.clear();
for (int i = 0; i < (pkt_msg.rob_dep()).size(); i++) {
- element->robDep[element->numRobDep] = pkt_msg.rob_dep(i);
- element->numRobDep += 1;
+ element->robDep.push_back(pkt_msg.rob_dep(i));
}
// Repeated field
- element->clearRegDep();
- assert((pkt_msg.reg_dep()).size() <= TheISA::MaxInstSrcRegs);
+ element->regDep.clear();
for (int i = 0; i < (pkt_msg.reg_dep()).size(); i++) {
// There is a possibility that an instruction has both, a
register
// and order dependency on an instruction. In such a case, the
// register dependency is omitted
bool duplicate = false;
- for (int j = 0; j < element->numRobDep; j++) {
- duplicate |= (pkt_msg.reg_dep(i) == element->robDep[j]);
+ for (auto &dep: element->robDep) {
+ duplicate |= (pkt_msg.reg_dep(i) == dep);
}
- if (!duplicate) {
- element->regDep[element->numRegDep] = pkt_msg.reg_dep(i);
- element->numRegDep += 1;
- }
+ if (!duplicate)
+ element->regDep.push_back(pkt_msg.reg_dep(i));
}
// Optional fields
@@ -1285,14 +1274,13 @@
bool
TraceCPU::ElasticDataGen::GraphNode::removeRegDep(NodeSeqNum reg_dep)
{
- for (auto& own_reg_dep : regDep) {
- if (own_reg_dep == reg_dep) {
- // If register dependency is found, make it zero and return
true
- own_reg_dep = 0;
- assert(numRegDep > 0);
- --numRegDep;
- DPRINTFR(TraceCPUData, "\tFor %lli: Marking register
dependency "
- "%lli done.\n", seqNum, reg_dep);
+ for (auto it = regDep.begin(); it != regDep.end(); it++) {
+ if (*it == reg_dep) {
+ // If register dependency is found, erase it.
+ regDep.erase(it);
+ DPRINTFR(TraceCPUData,
+ "\tFor %lli: Marking register dependency %lli done.\n",
+ seqNum, reg_dep);
return true;
}
}
@@ -1304,12 +1292,10 @@
bool
TraceCPU::ElasticDataGen::GraphNode::removeRobDep(NodeSeqNum rob_dep)
{
- for (auto& own_rob_dep : robDep) {
- if (own_rob_dep == rob_dep) {
- // If the rob dependency is found, make it zero and return true
- own_rob_dep = 0;
- assert(numRobDep > 0);
- --numRobDep;
+ for (auto it = robDep.begin(); it != robDep.end(); it++) {
+ if (*it == rob_dep) {
+ // If the rob dependency is found, erase it.
+ robDep.erase(it);
DPRINTFR(TraceCPUData,
"\tFor %lli: Marking ROB dependency %lli done.\n",
seqNum, rob_dep);
@@ -1319,24 +1305,6 @@
return false;
}
-void
-TraceCPU::ElasticDataGen::GraphNode::clearRegDep()
-{
- for (auto& own_reg_dep : regDep) {
- own_reg_dep = 0;
- }
- numRegDep = 0;
-}
-
-void
-TraceCPU::ElasticDataGen::GraphNode::clearRobDep()
-{
- for (auto& own_rob_dep : robDep) {
- own_rob_dep = 0;
- }
- numRobDep = 0;
-}
-
bool
TraceCPU::ElasticDataGen::GraphNode::removeDepOnInst(NodeSeqNum
done_seq_num)
{
@@ -1349,7 +1317,7 @@
assert(regdep_found);
}
// Return true if the node is dependency free
- return (numRobDep == 0 && numRegDep == 0);
+ return robDep.empty() && regDep.empty();
}
void
@@ -1363,17 +1331,13 @@
DPRINTFR(TraceCPUData, ",%i", flags);
}
DPRINTFR(TraceCPUData, ",%lli", compDelay);
- int i = 0;
DPRINTFR(TraceCPUData, "robDep:");
- while (robDep[i] != 0) {
- DPRINTFR(TraceCPUData, ",%lli", robDep[i]);
- i++;
+ for (auto &dep: robDep) {
+ DPRINTFR(TraceCPUData, ",%lli", dep);
}
- i = 0;
DPRINTFR(TraceCPUData, "regDep:");
- while (regDep[i] != 0) {
- DPRINTFR(TraceCPUData, ",%lli", regDep[i]);
- i++;
+ for (auto &dep: regDep) {
+ DPRINTFR(TraceCPUData, ",%lli", dep);
}
auto child_itr = dependents.begin();
DPRINTFR(TraceCPUData, "dependents:");
diff --git a/src/cpu/trace/trace_cpu.hh b/src/cpu/trace/trace_cpu.hh
index d0f0e47..11a6bb2 100644
--- a/src/cpu/trace/trace_cpu.hh
+++ b/src/cpu/trace/trace_cpu.hh
@@ -38,8 +38,8 @@
#ifndef __CPU_TRACE_TRACE_CPU_HH__
#define __CPU_TRACE_TRACE_CPU_HH__
-#include <array>
#include <cstdint>
+#include <list>
#include <queue>
#include <set>
#include <unordered_map>
@@ -555,18 +555,11 @@
class GraphNode
{
public:
- /**
- * The maximum no. of ROB dependencies. There can be at most 2
- * order dependencies which could exist for a store. For a load
- * and comp node there can be at most one order dependency.
- */
- static const uint8_t maxRobDep = 2;
+ /** Typedef for the list containing the ROB dependencies */
+ typedef std::list<NodeSeqNum> RobDepList;
- /** Typedef for the array containing the ROB dependencies */
- typedef std::array<NodeSeqNum, maxRobDep> RobDepArray;
-
- /** Typedef for the array containing the register dependencies
*/
- typedef std::array<NodeSeqNum, TheISA::MaxInstSrcRegs>
RegDepArray;
+ /** Typedef for the list containing the register dependencies
*/
+ typedef std::list<NodeSeqNum> RegDepList;
/** Instruction sequence number */
NodeSeqNum seqNum;
@@ -595,23 +588,17 @@
/** Instruction PC */
Addr pc;
- /** Array of order dependencies. */
- RobDepArray robDep;
-
- /** Number of order dependencies */
- uint8_t numRobDep;
+ /** List of order dependencies. */
+ RobDepList robDep;
/** Computational delay */
uint64_t compDelay;
/**
- * Array of register dependencies (incoming) if any. Maximum
number
+ * List of register dependencies (incoming) if any. Maximum
number
* of source registers used to set maximum size of the array
*/
- RegDepArray regDep;
-
- /** Number of register dependencies */
- uint8_t numRegDep;
+ RegDepList regDep;
/**
* A vector of nodes dependent (outgoing) on this node. A
@@ -629,12 +616,6 @@
/** Is the node a compute (non load/store) node */
bool isComp() const { return (type == Record::COMP); }
- /** Initialize register dependency array to all zeroes */
- void clearRegDep();
-
- /** Initialize register dependency array to all zeroes */
- void clearRobDep();
-
/** Remove completed instruction from register dependency
array */
bool removeRegDep(NodeSeqNum reg_dep);
@@ -897,8 +878,7 @@
* which may get modified during iteration
*/
template<typename T>
- void addDepsOnParent(GraphNode *new_node, T& dep_array,
- uint8_t& num_dep);
+ void addDepsOnParent(GraphNode *new_node, T& dep_array);
/**
* This is the main execute function which consumes nodes from the
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/38386
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: Ie9f30c61bac52ad31745a1011f62c95622908d2f
Gerrit-Change-Number: 38386
Gerrit-PatchSet: 1
Gerrit-Owner: Gabe Black <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
