[Beignet] [PATCH] GBE: considering loop depth when do spilling.
Zhigang Gong
zhigang.gong at intel.com
Tue Apr 22 18:26:41 PDT 2014
The key value is dominated by the loop depth. The value has larger loop depth
will always get a smaller key, no mather the interval value.
Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
---
backend/src/backend/gen_context.hpp | 4 ++++
backend/src/backend/gen_reg_allocation.cpp | 30 ++++++++++++++++++++----------
backend/src/ir/function.cpp | 5 +++--
backend/src/ir/function.hpp | 7 ++++---
backend/src/ir/liveness.cpp | 2 ++
backend/src/ir/liveness.hpp | 6 ++++++
backend/src/llvm/llvm_gen_backend.cpp | 2 +-
7 files changed, 40 insertions(+), 16 deletions(-)
diff --git a/backend/src/backend/gen_context.hpp b/backend/src/backend/gen_context.hpp
index 1154796..70abc8d 100644
--- a/backend/src/backend/gen_context.hpp
+++ b/backend/src/backend/gen_context.hpp
@@ -84,6 +84,10 @@ namespace gbe
INLINE const ir::Liveness::UEVar &getLiveIn(const ir::BasicBlock *bb) const {
return this->liveness->getLiveIn(bb);
}
+ /*! Get the innerest loop depth of the given block */
+ INLINE const uint32_t getLoopDepth(const ir::BasicBlock *bb) const {
+ return this->liveness->getLoopDepth(bb);
+ }
void collectShifter(GenRegister dest, GenRegister src);
void loadTopHalf(GenRegister dest, GenRegister src);
diff --git a/backend/src/backend/gen_reg_allocation.cpp b/backend/src/backend/gen_reg_allocation.cpp
index 6ae2dc7..9908ab8 100644
--- a/backend/src/backend/gen_reg_allocation.cpp
+++ b/backend/src/backend/gen_reg_allocation.cpp
@@ -48,14 +48,17 @@ namespace gbe
*/
struct GenRegInterval {
INLINE GenRegInterval(ir::Register reg) :
- reg(reg), minID(INT_MAX), maxID(-INT_MAX) {}
+ reg(reg), minID(INT_MAX), maxID(-INT_MAX), loopDepth(0){}
ir::Register reg; //!< (virtual) register of the interval
int32_t minID, maxID; //!< Starting and ending points
+ uint32_t loopDepth;
};
+ /* The key value is dominated by the loop depth. The value has larger loop depth
+ will always get a smaller key, no mather the interval value.*/
typedef struct GenRegIntervalKey {
- GenRegIntervalKey(uint16_t reg, int32_t maxID) {
- key = ((uint64_t)maxID << 16) | reg;
+ GenRegIntervalKey(uint16_t reg, int32_t maxID, uint32_t loopDepth) {
+ key = (((uint64_t)maxID << 16) | reg ) - ((uint64_t)loopDepth << 48);
}
const ir::Register getReg() const {
return (ir::Register)(key & 0xFFFF);
@@ -63,7 +66,7 @@ namespace gbe
const int32_t getMaxID() const {
return key >> 16;
}
- uint64_t key;
+ int64_t key;
} GenRegIntervalKey;
struct spillCmp {
@@ -77,15 +80,15 @@ namespace gbe
{
public:
std::set<GenRegIntervalKey, spillCmp>::iterator find(GenRegInterval interval) {
- GenRegIntervalKey key(interval.reg, interval.maxID);
+ GenRegIntervalKey key(interval.reg, interval.maxID, interval.loopDepth);
return SpillSet::find(key);
}
void insert(GenRegInterval interval) {
- GenRegIntervalKey key(interval.reg, interval.maxID);
+ GenRegIntervalKey key(interval.reg, interval.maxID, interval.loopDepth);
SpillSet::insert(key);
}
void erase(GenRegInterval interval) {
- GenRegIntervalKey key(interval.reg, interval.maxID);
+ GenRegIntervalKey key(interval.reg, interval.maxID, interval.loopDepth);
SpillSet::erase(key);
}
};
@@ -920,6 +923,8 @@ namespace gbe
for (auto &block : *selection.blockList) {
int32_t lastID = insnID;
int32_t firstID = insnID;
+ const ir::BasicBlock *bb = block.bb;
+ const uint32_t loopDepth = ctx.getLoopDepth(bb);
// Update the intervals of each used register. Note that we do not
// register allocate R0, so we skip all sub-registers in r0
RegIntervalMap *boolsMap = new RegIntervalMap;
@@ -937,6 +942,7 @@ namespace gbe
continue;
this->intervals[reg].minID = std::min(this->intervals[reg].minID, insnID);
this->intervals[reg].maxID = std::max(this->intervals[reg].maxID, insnID);
+ this->intervals[reg].loopDepth = std::max(this->intervals[reg].loopDepth, loopDepth);
}
for (uint32_t dstID = 0; dstID < dstNum; ++dstID) {
const GenRegister &selReg = insn.dst(dstID);
@@ -949,6 +955,7 @@ namespace gbe
continue;
this->intervals[reg].minID = std::min(this->intervals[reg].minID, insnID);
this->intervals[reg].maxID = std::max(this->intervals[reg].maxID, insnID);
+ this->intervals[reg].loopDepth = std::max(this->intervals[reg].loopDepth, loopDepth);
}
// OK, a flag is used as a predicate or a conditional modifier
@@ -984,14 +991,17 @@ namespace gbe
}
// All registers alive at the begining of the block must update their intervals.
- const ir::BasicBlock *bb = block.bb;
- for (auto reg : ctx.getLiveIn(bb))
+ for (auto reg : ctx.getLiveIn(bb)) {
this->intervals[reg].minID = std::min(this->intervals[reg].minID, firstID);
+ this->intervals[reg].loopDepth = std::max(this->intervals[reg].loopDepth, loopDepth);
+ }
// All registers alive at the end of the block must have their intervals
// updated as well
- for (auto reg : ctx.getLiveOut(bb))
+ for (auto reg : ctx.getLiveOut(bb)) {
this->intervals[reg].maxID = std::max(this->intervals[reg].maxID, lastID);
+ this->intervals[reg].loopDepth = std::max(this->intervals[reg].loopDepth, loopDepth);
+ }
if (boolsMap->size() > 0)
boolIntervalsMap.insert(std::make_pair(&block, boolsMap));
diff --git a/backend/src/ir/function.cpp b/backend/src/ir/function.cpp
index b0df412..c4b8b26 100644
--- a/backend/src/ir/function.cpp
+++ b/backend/src/ir/function.cpp
@@ -60,8 +60,8 @@ namespace ir {
return unit.getPointerFamily();
}
- void Function::addLoop(const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits) {
- loops.push_back(GBE_NEW(Loop, bbs, exits));
+ void Function::addLoop(const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits, uint32_t depth) {
+ loops.push_back(GBE_NEW(Loop, bbs, exits, depth));
}
void Function::checkEmptyLabels(void) {
@@ -342,6 +342,7 @@ namespace ir {
return label->getLabelIndex();
}
+
} /* namespace ir */
} /* namespace gbe */
diff --git a/backend/src/ir/function.hpp b/backend/src/ir/function.hpp
index abefa54..39644ad 100644
--- a/backend/src/ir/function.hpp
+++ b/backend/src/ir/function.hpp
@@ -138,10 +138,11 @@ namespace ir {
struct Loop : public NonCopyable
{
public:
- Loop(const vector<LabelIndex> &in, const vector<std::pair<LabelIndex, LabelIndex>> &exit) :
- bbs(in), exits(exit) {}
+ Loop(const vector<LabelIndex> &in, const vector<std::pair<LabelIndex, LabelIndex>> &exit, uint32_t depth) :
+ bbs(in), exits(exit), depth(depth) {}
vector<LabelIndex> bbs;
vector<std::pair<LabelIndex, LabelIndex>> exits;
+ uint32_t depth;
GBE_STRUCT(Loop);
};
@@ -332,7 +333,7 @@ namespace ir {
/*! Push stack size. */
INLINE void pushStackSize(uint32_t step) { this->stackSize += step; }
/*! add the loop info for later liveness analysis */
- void addLoop(const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits);
+ void addLoop(const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits, uint32_t depth);
INLINE const vector<Loop * > &getLoops() { return loops; }
private:
friend class Context; //!< Can freely modify a function
diff --git a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp
index 9be539f..3477110 100644
--- a/backend/src/ir/liveness.cpp
+++ b/backend/src/ir/liveness.cpp
@@ -150,6 +150,8 @@ namespace ir {
for (auto bb : l->bbs) {
BlockInfo * bI = liveness[&fn.getBlock(bb)];
+ if (bI->loopDepth < l->depth)
+ bI->loopDepth = l->depth;
for(auto r : toExtend) {
if(!bI->upwardUsed.contains(r))
bI->upwardUsed.insert(r);
diff --git a/backend/src/ir/liveness.hpp b/backend/src/ir/liveness.hpp
index 11f1fdc..4c32929 100644
--- a/backend/src/ir/liveness.hpp
+++ b/backend/src/ir/liveness.hpp
@@ -72,6 +72,7 @@ namespace ir {
UEVar upwardUsed;
LiveOut liveOut;
VarKill varKill;
+ uint32_t loopDepth;
};
/*! Gives for each block the variables alive at entry / exit */
typedef map<const BasicBlock*, BlockInfo*> Info;
@@ -93,6 +94,11 @@ namespace ir {
const BlockInfo &info = this->getBlockInfo(bb);
return info.upwardUsed;
}
+ /*! Get the innerest loop depth of the specified BB. */
+ const uint32_t getLoopDepth(const BasicBlock *bb) const {
+ const BlockInfo &info = this->getBlockInfo(bb);
+ return info.loopDepth;
+ }
/*! Return the function the liveness was computed on */
INLINE const Function &getFunction(void) const { return fn; }
diff --git a/backend/src/llvm/llvm_gen_backend.cpp b/backend/src/llvm/llvm_gen_backend.cpp
index 6c2b45d..a4e7f24 100644
--- a/backend/src/llvm/llvm_gen_backend.cpp
+++ b/backend/src/llvm/llvm_gen_backend.cpp
@@ -1517,7 +1517,7 @@ namespace gbe
GBE_ASSERT(labelMap.find(b.second) != labelMap.end());
loopExits.push_back(std::make_pair(labelMap[b.first], labelMap[b.second]));
}
- fn.addLoop(loopBBs, loopExits);
+ fn.addLoop(loopBBs, loopExits, loop.first->getLoopDepth());
}
}
--
1.8.3.2
More information about the Beignet
mailing list