From e2fd8e5b61ae4ff81d2a38efe270bcff34d6a6af Mon Sep 17 00:00:00 2001 From: Benjamin Segovia Date: Mon, 8 Oct 2012 19:14:21 +0000 Subject: [PATCH] Used intrusive_list for SelectionInstruction --- backend/src/backend/gen_insn_scheduling.cpp | 4 +- backend/src/backend/gen_insn_selection.cpp | 82 ++++++++--------------------- backend/src/backend/gen_insn_selection.hpp | 24 +++++---- 3 files changed, 38 insertions(+), 72 deletions(-) diff --git a/backend/src/backend/gen_insn_scheduling.cpp b/backend/src/backend/gen_insn_scheduling.cpp index 2fa6873..580cb03 100644 --- a/backend/src/backend/gen_insn_scheduling.cpp +++ b/backend/src/backend/gen_insn_scheduling.cpp @@ -428,7 +428,6 @@ namespace gbe this->ready.erase(toSchedule); this->active.push_back(toSchedule.node()); toSchedule->node->retiredCycle = cycle + getLatencyGen7(toSchedule->node->insn); - toSchedule->node->insn.next = toSchedule->node->insn.prev = NULL; bb.append(&toSchedule->node->insn); insnNum--; } else @@ -443,7 +442,8 @@ namespace gbe SelectionScheduler scheduler(ctx, selection); selection.foreach([&](SelectionBlock &bb) { const int32_t insnNum = scheduler.buildDAG(bb); - bb.insnHead = bb.insnTail = NULL; + bb.insnList.clear(); + // bb.insnHead = bb.insnTail = NULL; scheduler.scheduleDAG(bb, insnNum); }); } diff --git a/backend/src/backend/gen_insn_selection.cpp b/backend/src/backend/gen_insn_selection.cpp index 90aa275..3570b27 100644 --- a/backend/src/backend/gen_insn_selection.cpp +++ b/backend/src/backend/gen_insn_selection.cpp @@ -38,35 +38,17 @@ namespace gbe /////////////////////////////////////////////////////////////////////////// SelectionInstruction::SelectionInstruction(SelectionOpcode op, uint32_t dst, uint32_t src) : - parent(NULL), prev(NULL), next(NULL), opcode(op), dstNum(dst), srcNum(src) + parent(NULL), opcode(op), dstNum(dst), srcNum(src) {} void SelectionInstruction::prepend(SelectionInstruction &other) { - SelectionInstruction *before = this->prev; - this->prev = &other; - other.next = this; + gbe::prepend(&other, this); other.parent = this->parent; - if (before) { - other.prev = before; - before->next = &other; - } else { - GBE_ASSERT(this == this->parent->insnHead); - this->parent->insnHead = &other; - } } void SelectionInstruction::append(SelectionInstruction &other) { - SelectionInstruction *after = this->next; - this->next = &other; - other.prev = this; + gbe::append(&other, this); other.parent = this->parent; - if (after) { - other.next = after; - after->prev = &other; - } else { - GBE_ASSERT(this == this->parent->insnTail); - this->parent->insnTail = &other; - } } bool SelectionInstruction::isRead(void) const { @@ -102,30 +84,18 @@ namespace gbe /////////////////////////////////////////////////////////////////////////// SelectionBlock::SelectionBlock(const ir::BasicBlock *bb) : - insnHead(NULL), insnTail(NULL), vector(NULL), next(NULL), bb(bb) + vector(NULL), next(NULL), bb(bb) {} void SelectionBlock::append(ir::Register reg) { tmp.push_back(reg); } void SelectionBlock::append(SelectionInstruction *insn) { - if (this->insnTail != NULL) { - this->insnTail->next = insn; - insn->prev = this->insnTail; - } - if (this->insnHead == NULL) - this->insnHead = insn; - this->insnTail = insn; + this->insnList.push_back(insn); insn->parent = this; } void SelectionBlock::prepend(SelectionInstruction *insn) { - if (this->insnHead != NULL) { - this->insnHead->prev = insn; - insn->next = this->insnHead; - } - if (this->insnTail == NULL) - this->insnTail = insn; - this->insnHead = insn; + this->insnList.push_front(insn); insn->parent = this; } @@ -313,7 +283,7 @@ namespace gbe /*! Owns this structure */ GenContext &ctx; /*! Tail of the code fragment for backward code generation */ - SelectionInstruction *bwdTail; + intrusive_list bwdList; /*! List of emitted blocks */ SelectionBlock *blockHead, *blockTail; /*! Currently processed block */ @@ -412,7 +382,7 @@ namespace gbe }; Selection::Opaque::Opaque(GenContext &ctx) : - ctx(ctx), bwdTail(NULL), blockHead(NULL), blockTail(NULL), block(NULL), + ctx(ctx), blockHead(NULL), blockTail(NULL), block(NULL), curr(ctx.getSimdWidth()), file(ctx.getFunction().getRegisterFile()), maxInsnNum(ctx.getFunction().getLargestBlockSize()), dagPool(maxInsnNum), stateNum(0), vectorNum(0), bwdCodeGeneration(false) @@ -450,16 +420,13 @@ namespace gbe } void Selection::Opaque::endBackwardGeneration(void) { - // Attach the code fragment to the basic block - if (this->bwdTail) { - GBE_ASSERT(this->block != NULL); - // Prepend the code from last to first - while (this->bwdTail) { - this->block->prepend(this->bwdTail); - this->bwdTail = this->bwdTail->prev; - } + for (auto it = bwdList.rbegin(); it != bwdList.rend();) { + SelectionInstruction &insn = *it; + auto toRemoveIt = it--; + bwdList.erase(toRemoveIt); + this->block->prepend(&insn); } - this->bwdTail = NULL; + this->bwdCodeGeneration = false; } @@ -488,13 +455,9 @@ namespace gbe { GBE_ASSERT(this->block != NULL); SelectionInstruction *insn = this->create(opcode, dstNum, srcNum); - if (this->bwdCodeGeneration) { - if (this->bwdTail) { - this->bwdTail->next = insn; - insn->prev = this->bwdTail; - } - this->bwdTail = insn; - } else + if (this->bwdCodeGeneration) + this->bwdList.push_back(insn); + else this->block->append(insn); insn->state = this->curr; return insn; @@ -504,13 +467,10 @@ namespace gbe GBE_ASSERT(this->block != NULL); SelectionVector *vector = this->newSelectionVector(); - if (this->bwdCodeGeneration) { - GBE_ASSERT(this->bwdTail != NULL); - vector->insn = this->bwdTail; - } else { - GBE_ASSERT(this->block->insnTail != NULL); - vector->insn = this->block->insnTail; - } + if (this->bwdCodeGeneration) + vector->insn = this->bwdList.back(); + else + vector->insn = this->block->insnList.back(); this->block->append(vector); this->vectorNum++; return vector; diff --git a/backend/src/backend/gen_insn_selection.hpp b/backend/src/backend/gen_insn_selection.hpp index 12d1567..d3dc32b 100644 --- a/backend/src/backend/gen_insn_selection.hpp +++ b/backend/src/backend/gen_insn_selection.hpp @@ -31,6 +31,7 @@ #include "backend/gen_encoder.hpp" #include "backend/gen_context.hpp" #include "sys/vector.hpp" +#include "sys/intrusive_list.hpp" namespace gbe { @@ -82,13 +83,11 @@ namespace gbe /*! A selection instruction is also almost a Gen instruction but *before* the * register allocation */ - class SelectionInstruction : public NonCopyable + class SelectionInstruction : public NonCopyable, public intrusive_list_node { public: /*! Owns the instruction */ SelectionBlock *parent; - /*! Instruction are chained in the block */ - SelectionInstruction *prev, *next; /*! Append an instruction before this one */ void prepend(SelectionInstruction &insn); /*! Append an instruction after this one */ @@ -178,7 +177,7 @@ namespace gbe public: SelectionBlock(const ir::BasicBlock *bb); /*! All the emitted instructions in the block */ - SelectionInstruction *insnHead, *insnTail; + intrusive_list insnList; /*! The vectors that may be required by some instructions of the block */ SelectionVector *vector; /*! Extra registers needed by the block (only live in the block) */ @@ -198,11 +197,18 @@ namespace gbe /*! Apply the given functor on all the instructions */ template INLINE void foreach(const T &functor) const { - SelectionInstruction *curr = insnHead; - while (curr) { - SelectionInstruction *succ = curr->next; - functor(*curr); - curr = succ; + for (auto it = insnList.begin(); it != insnList.end();) { + const SelectionInstruction &curr = *it; + ++it; + functor(curr); + } + } + template + INLINE void foreach(const T &functor) { + for (auto it = insnList.begin(); it != insnList.end();) { + SelectionInstruction &curr = *it; + ++it; + functor(curr); } } }; -- 2.7.4