[Beignet] [PATCH 7/7] Backend: Refine instruction schedule pre reg alloction
Xiuli Pan
xiuli.pan at intel.com
Mon Nov 14 08:20:08 UTC 2016
From: Pan Xiuli <xiuli.pan at intel.com>
Fix the pre schedule, now it will work with the origin algorithm. We add
more dependency for instruction to keep the schedule result not random
and keep the origin order.
Contributor: Ruiling Song <ruiling.song at intel.com>
Signed-off-by: Pan Xiuli <xiuli.pan at intel.com>
---
backend/src/backend/gen_insn_scheduling.cpp | 113 +++++++++++++++++++---------
1 file changed, 77 insertions(+), 36 deletions(-)
diff --git a/backend/src/backend/gen_insn_scheduling.cpp b/backend/src/backend/gen_insn_scheduling.cpp
index 245d17a..de21301 100644
--- a/backend/src/backend/gen_insn_scheduling.cpp
+++ b/backend/src/backend/gen_insn_scheduling.cpp
@@ -102,7 +102,8 @@ namespace gbe
WRITE_AFTER_WRITE,
WRITE_AFTER_READ,
READ_AFTER_WRITE,
- READ_AFTER_WRITE_MEMORY
+ READ_AFTER_WRITE_MEMORY,
+ SYNCHRONIZATION
} DepMode;
/*! We need to chain together the node we point */
@@ -113,11 +114,17 @@ namespace gbe
DepMode depMode;
};
+ struct ScheduleDAGWrapper
+ {
+ INLINE ScheduleDAGWrapper(ScheduleDAGNode *node, DepMode m = READ_AFTER_WRITE) : node(node), depMode(m) {}
+ ScheduleDAGNode *node;
+ DepMode depMode;
+ };
/*! Node of the DAG */
struct ScheduleDAGNode
{
INLINE ScheduleDAGNode(SelectionInstruction &insn) :
- insn(insn), refNum(0), depNum(0), retiredCycle(0), preRetired(false), readDistance(0x7fffffff) {}
+ insn(insn), refNum(0), depNum(0), regNum(0), retiredCycle(0), preRetired(false), readDistance(0x7fffffff) {}
bool dependsOn(ScheduleDAGNode *node) const {
GBE_ASSERT(node != NULL);
for (auto child : node->children)
@@ -206,7 +213,7 @@ namespace gbe
/*! Stores the last node that wrote to a register / memory ... */
vector<ScheduleDAGNode*> nodes;
/*! store nodes each node depends on */
- map<ScheduleDAGNode *, vector<ScheduleDAGNode*>> deps;
+ map<ScheduleDAGNode *, vector<ScheduleDAGWrapper>> deps;
/*! Stores the nodes per instruction */
vector<ScheduleDAGNode*> insnNodes;
/*! Number of virtual register in the selection */
@@ -283,20 +290,22 @@ namespace gbe
void DependencyTracker::addDependency(ScheduleDAGNode *node0, ScheduleDAGNode *node1, DepMode depMode) {
if (node0 != NULL && node1 != NULL && node0 != node1 && node0->dependsOn(node1) == false) {
- if (node1->insn.isRead())
- depMode = depMode == READ_AFTER_WRITE ? READ_AFTER_WRITE_MEMORY : depMode;
ScheduleListNode *dep = scheduler.newScheduleListNode(node0, depMode);
node0->refNum++;
node1->children.push_back(dep);
node1->depNum++;
auto it = deps.find(node0);
if (it != deps.end()) {
- it->second.push_back(node1);
+ it->second.push_back(ScheduleDAGWrapper(node1, depMode));
} else {
- vector<ScheduleDAGNode*> vn;
- vn.push_back(node1);
+ vector<ScheduleDAGWrapper> vn;
+ vn.push_back(ScheduleDAGWrapper(node1, depMode));
deps.insert(std::make_pair(node0, vn));
}
+ } else {
+ if (node0 != NULL && node1 == NULL && depMode == READ_AFTER_WRITE) {
+ node0->regNum += 1;
+ }
}
}
@@ -474,8 +483,8 @@ namespace gbe
auto it = tracker.deps.find(node);
if (it != tracker.deps.end()) {
for (auto &depNode : it->second) {
- if (depNode && !depNode->insn.isRead())
- traverseReadNode(depNode, degree + 1);
+ if (depNode.node && !depNode.node->insn.isRead())
+ traverseReadNode(depNode.node, degree + 1);
}
}
}
@@ -504,12 +513,12 @@ namespace gbe
// read-after-write in memory
if (insn.isRead()) {
const uint32_t index = tracker.getMemoryIndex();
- tracker.addDependency(node, index, READ_AFTER_WRITE);
+ tracker.addDependency(node, index, READ_AFTER_WRITE_MEMORY);
}
//read-after-write of scratch memory
if (insn.opcode == SEL_OP_UNSPILL_REG) {
const uint32_t index = tracker.getMemoryIndex();
- tracker.addDependency(node, index, READ_AFTER_WRITE);
+ tracker.addDependency(node, index, READ_AFTER_WRITE_MEMORY);
}
// Consider barriers and wait are reading memory (local and global)
@@ -518,7 +527,7 @@ namespace gbe
insn.opcode == SEL_OP_WAIT ||
insn.opcode == SEL_OP_WORKGROUP_OP) {
const uint32_t memIndex = tracker.getMemoryIndex();
- tracker.addDependency(node, memIndex, READ_AFTER_WRITE);
+ tracker.addDependency(node, memIndex, READ_AFTER_WRITE_MEMORY);
}
// write-after-write in registers
@@ -630,6 +639,9 @@ namespace gbe
inline bool cmp(const ScheduleDAGNode *v0, const ScheduleDAGNode *v1) {
return v0->regNum < v1->regNum;
}
+ inline bool cmpID(const ScheduleDAGNode *v0, const ScheduleDAGNode *v1) {
+ return v0->insn.ID < v1->insn.ID;
+ }
/* Recursively compute heuristic Sethi-Ullman number for each node. */
void SelectionScheduler::computeRegPressure(ScheduleDAGNode *node,
@@ -639,24 +651,30 @@ namespace gbe
return;
}
if (node->refNum == 0) {
- node->regNum = 0;
- regPressureMap.insert(std::make_pair(node, 0));
+ regPressureMap.insert(std::make_pair(node, node->regNum));
return;
}
- auto &children = tracker.deps.find(node)->second;
- for (auto child : children) {
- computeRegPressure(child, regPressureMap);
+ auto &childrenOld = tracker.deps.find(node)->second;
+ for (auto child : childrenOld) {
+ computeRegPressure(child.node, regPressureMap);
+ }
+ // we only care true data dependency here.
+ vector<ScheduleDAGNode *> children;
+
+ for (auto &x : childrenOld) {
+ if (x.depMode == READ_AFTER_WRITE)
+ children.push_back(x.node);
}
std::sort(children.begin(), children.end(), cmp);
uint32_t maxRegNum = 0;
- int32_t i = 0;
+ int32_t i = 1;
for (auto &child : children) {
if (child->regNum + children.size() - i > maxRegNum)
- maxRegNum = child->regNum + node->children.size() - i;
+ maxRegNum = child->regNum + children.size() - i;
++i;
}
- node->regNum = maxRegNum;
- regPressureMap.insert(std::make_pair(node, maxRegNum));
+ node->regNum += maxRegNum;
+ regPressureMap.insert(std::make_pair(node, node->regNum));
return;
}
@@ -673,7 +691,7 @@ namespace gbe
computeRegPressure(node, regPressureMap);
parentIndexMap.insert(std::make_pair(node, INT_MAX));
}
- set<ScheduleDAGNode *> readySet(rootNodes.begin(), rootNodes.end());
+ vector<ScheduleDAGNode *> readySet(rootNodes.begin(), rootNodes.end());
set<ScheduleDAGNode *> scheduledSet;
int32_t j = insnNum;
@@ -682,36 +700,59 @@ namespace gbe
// as the best node to schedule.
while(readySet.size()) {
ScheduleDAGNode * bestNode = NULL;
+ vector<ScheduleDAGNode *>::iterator bestNodeitr;
int32_t minRegNum = INT_MAX;
int32_t minParentIndex = INT_MAX;
- for(auto node : readySet) {
+ uint32_t nowinsnID = 0;
+ std::sort(readySet.begin(), readySet.end(), cmp);
+ for(auto itr = readySet.begin(); itr != readySet.end(); ++itr) {
+ ScheduleDAGNode * node = *itr;
GBE_ASSERT(scheduledSet.contains(node) == false);
if (parentIndexMap.find(node)->second < minParentIndex) {
bestNode = node;
+ bestNodeitr = itr;
minParentIndex = parentIndexMap.find(node)->second;
minRegNum = regPressureMap.find(node)->second;
}
else if (parentIndexMap.find(node)->second == minParentIndex) {
if (regPressureMap.find(node)->second < minRegNum) {
+ bestNodeitr = itr;
bestNode = node;
minRegNum = regPressureMap.find(node)->second;
}
+ else if (regPressureMap.find(node)->second == minRegNum) {
+ if (nowinsnID < node->insn.ID) {
+ bestNode = node;
+ bestNodeitr = itr;
+ nowinsnID = node->insn.ID;
+ }
+ }
}
}
- for( auto node : tracker.deps.find(bestNode)->second ) {
- if (node == NULL)
- continue;
- node->depNum--;
- if (parentIndexMap.find(node) != parentIndexMap.end())
- parentIndexMap.find(node)->second = j;
- else
- parentIndexMap.insert(std::make_pair(node, j));
- if (node->depNum == 0 && scheduledSet.contains(node) == false)
- readySet.insert(node);
- }
bb.prepend(&bestNode->insn);
- readySet.erase(bestNode);
+ readySet.erase(bestNodeitr);
scheduledSet.insert(bestNode);
+ auto itt = tracker.deps.find(bestNode);
+ if (itt != tracker.deps.end()) {
+ for( auto node : itt->second ) {
+ if (node.node == NULL)
+ continue;
+ node.node->depNum--;
+ if (parentIndexMap.find(node.node) != parentIndexMap.end())
+ parentIndexMap.find(node.node)->second = j;
+ else
+ parentIndexMap.insert(std::make_pair(node.node, j));
+ for(auto noderd : readySet) {
+ if (noderd->dependsOn(node.node) && node.depMode != 2)
+ {
+ parentIndexMap.find(noderd)->second = j - 1;
+ }
+ }
+ }
+ for( auto node : itt->second )
+ if (node.node->depNum == 0 && scheduledSet.contains(node.node) == false)
+ readySet.push_back(node.node);
+ }
--j;
}
GBE_ASSERT(insnNum == (int32_t)bb.insnList.size());
--
2.7.4
More information about the Beignet
mailing list