| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| /** |
| * @author Sergey L. Ivashin |
| */ |
| |
| #include "Ia32IRManager.h" |
| #include "Ia32RegAllocCheck.h" |
| #include "XTimer.h" |
| #include "Counter.h" |
| #include "Stl.h" |
| #ifdef PLATFORM_POSIX |
| #include <limits.h> |
| #endif |
| |
| #ifdef _DEBUG_SPILLGEN |
| #include "Ia32SpillGenDbg.h" |
| #endif //#ifdef _DEBUG_SPILLGEN |
| |
| |
| namespace Jitrino |
| { |
| namespace Ia32 |
| { |
| |
| static const char* help = |
| " regs=ALL\n" |
| " regs=<comma-separated list of available registers, e.g EAX,ECX,XMM0,>\n" |
| ; |
| |
| |
| struct SpillGen : public SessionAction |
| { |
| |
| // Inter-blocks data |
| // ----------------- |
| |
| typedef U_32 RegMask; |
| typedef StlVector<Opnd*> Opnds; |
| |
| MemoryManager mm; // this is private MemoryManager, not irm.getMemoryManager() |
| |
| // Table of all available registers sets. |
| // Each set (GPReg, FPReg, XMMReg and so on) is represented by the corresponding |
| // Constraint object. |
| struct Registers : public StlVector<Constraint> |
| { |
| Registers (MemoryManager& mm) :StlVector<Constraint>(mm) {} |
| |
| void parse (const char*); |
| |
| // clear mask fields in all elements of the table |
| void clearMasks (); |
| |
| void merge (const Registers&); |
| |
| // register the new constraint (register) in the table. |
| // if table doesn't contain constraint of the specified kind, it will be ignored |
| // (add = false) or new table entry for the constraint will be created (add = true). |
| int merge (const Constraint&, bool add = false); |
| |
| // returns table index of the constraint of the specified kind or -1 |
| int getIndex (const Constraint&) const; |
| |
| // returns pointer to the table element of the specified kind |
| Constraint* contains (const Constraint&); |
| |
| int indexes[IRMaxRegKinds]; |
| }; |
| Registers registers; |
| |
| size_t opndcount; // initial count of operands |
| size_t emitted; // extra instructions count |
| size_t fails; // if != 0, then SpillGen should be aborted |
| |
| // mapping operand -> its memory location |
| // every operand that was splitted to memory is registered in this table |
| typedef ::std::pair<const Opnd*, Opnd*> TwoOpnds; |
| typedef StlVector<TwoOpnds> MemOpnds; |
| MemOpnds memopnds; |
| |
| |
| // Block-specific data |
| // ------------------- |
| |
| enum |
| { |
| RoleDef = 1, |
| RoleUse = 2, |
| RoleCond = 4, // if (RoleCond == true) RoleUse = true; |
| RoleEnd = 8 |
| }; |
| typedef char OpRole; |
| |
| // extension of 'Inst' structure with some specific data |
| struct Instx |
| { |
| Instx () : nbopnds(0), evicts(0) {} |
| |
| Inst* inst; // pointer to the corresponding instruction |
| size_t nbopnds; // max number of operands in instruction |
| OpRole* oproles; // array of nbopnds size |
| Opnds* evicts; // can be null, can contain null pointers |
| RegMask regusage[IRMaxRegKinds];// masks of all registers that are busy at this instruction |
| RegMask regpress[IRMaxRegKinds]; |
| }; |
| |
| typedef StlVector<Instx> Instxs; |
| Instxs instxs; |
| |
| // created for all problem (needed to be allocated) operands |
| |
| struct Op |
| { |
| Instx* instx; |
| OpRole oprole; |
| }; |
| |
| |
| struct Opline |
| { |
| Opline () : ops(0) {} |
| |
| void clear (MemoryManager&); |
| void addOp (Instx*, OpRole); |
| |
| // iterator methods, work with the current instruction only |
| void start (); |
| void forw (); |
| void back (const Instx*); |
| bool go () const {return op != 0;} |
| bool isDef () const {return op->instx == instx && (op->oprole & RoleDef) != 0;} |
| bool isUse () const {return op->instx == instx && (op->oprole & RoleUse) != 0;} |
| bool isEnd () const {return op->instx == instx && (op->oprole & RoleEnd) != 0;} |
| bool isProc() const {return op->instx == instx;} |
| |
| // work with the specified instruction |
| bool isDef (const Inst*) const; |
| bool isUse (const Inst*) const; |
| |
| |
| bool at_start, // 'true' if this operand lives at the BB entry |
| at_exit, // 'true' if this operand lives at the BB exit |
| catched; // 'true' if this operand lives at entry to dispatch node |
| int idx; // -1 or index of the corresponding constraint in 'registers' array |
| Opnd* opnd; // original form of operand |
| Opnd* opnd_mem; // 0 or memory form of the operand (cached copy of the value from 'memopnds' array) |
| Instx* save_instx; // 0 or point where instruction to save operand should be inserted |
| bool save_before; // true if save must be before instruction (false is the default) |
| Opnd* save_opnd; // which operand should be saved |
| RegMask save_regmsk; |
| int save_regidx; |
| bool save_changed; |
| |
| typedef StlVector<Op> Ops; |
| Ops* ops; // array of all instructions that change/use value of the operand |
| |
| // current instruction |
| Op* op; |
| Instx* instx; |
| |
| static bool smaller (const Opline& x, const Opline& y) {return x.weight < y.weight;} |
| |
| Constraint initial; |
| int weight; |
| }; |
| |
| |
| typedef StlVector<Opline> Oplines; |
| Oplines actives; |
| StlVector<Opline*> actsmap; |
| |
| struct Evict; |
| typedef StlVector<Evict> Evicts; |
| |
| // current context |
| Node* bblock; // the basic block being processed |
| BitSet* lives_start, // liveness info for start and end of the block |
| * lives_exit; // |
| BitSet* lives_catch; // 0 or mask of operands live at the corresponding dispatch node |
| |
| bool evicts_known; |
| |
| // Methods |
| // ------- |
| |
| |
| SpillGen () : mm("SpillGen") |
| , registers(mm), memopnds(mm) |
| , instxs(mm), actives(mm), actsmap(mm) |
| , lives_start(0), lives_exit(0) |
| {} |
| |
| U_32 getNeedInfo () const {return NeedInfo_LivenessInfo;} |
| U_32 getSideEffects () const {return SideEffect_InvalidatesLivenessInfo;} |
| |
| void runImpl(); |
| bool verify(bool force=false); |
| |
| size_t pass0 (); |
| size_t pass1 (); |
| RegMask lookPreffered (Opline&); |
| bool tryRegister (Opline&, Constraint, RegMask); |
| bool tryMemory (Opline&, Constraint); |
| bool tryEvict (Opline&, Constraint); |
| bool tryRepair (Opline&, Constraint); |
| bool simplify (Inst*, Opnd*); |
| RegMask usedRegs (const Instx*, int idx, bool isuse) const; |
| RegMask callRegs (const Instx*, int idx) const; |
| int update (const Inst*, const Opnd*, Constraint&) const; |
| void assignReg (Opline&, Instx* begx, Instx* endx, RegName); |
| void assignMem (Opline&, Instx* begx, Instx* endx); |
| void saveOpnd (Opline&, Instx*, Opnd*); |
| void saveOpnd (Opline&, Instx*, Opnd*, RegMask, int, bool); |
| bool loadOpnd (Opline&, Instx*, Opnd*); |
| void loadOpndMem (Opline&); |
| Opnd* opndMem (Opline&); |
| Opnd* opndMem (const Opnd*); |
| Opnd* opndReg (const Opnd*, RegName) const; |
| void emitPushPop (bool before, Inst*, Opnd* opnd, bool push); |
| Inst* emitMove (bool before, Inst*, Opnd* dst, Opnd* src); |
| RegName findFree (RegMask usable, int idx, Instx* begx); |
| RegName findEvict (RegMask usable, int idx, Instx* begx, Instx*& endx); |
| void setupEvicts (); |
| Evict* pickEvict (Evicts&); |
| bool isEvict (const Opnd*, const Instx*) const; |
| void killEvict (const Opnd*, Instx*) const; |
| RegMask getRegMaskConstr (const Opnd*, Constraint) const; |
| |
| }; |
| |
| |
| static ActionFactory<SpillGen> _spillgen("spillgen", help); |
| |
| |
| |
| #ifdef _DEBUG_SPILLGEN |
| #ifdef _MSC_VER |
| #pragma warning(disable : 4505) //unreferenced local function has been removed |
| #else |
| #endif //#ifdef _MSC_VER |
| #include "Ia32SpillGenDbgHead.h" |
| #else |
| #define DBGOUT(s) |
| #endif //#ifdef _DEBUG_SPILLGEN |
| |
| |
| |
| |
| // Utility class for (zero-terminated) strings parsing |
| // |
| class Tokens |
| { |
| public: |
| |
| Tokens (const char* s) :src(s) {;} |
| |
| void init (const char* s) {src = s;} |
| bool scan (); |
| bool isWord () const {return isw;} |
| const char* lex () const {return buff;} |
| |
| protected: |
| |
| const char* src; |
| char* dst; |
| char buff[64]; |
| bool isw; |
| }; |
| |
| |
| // Return 'false' if end of parsing string is reached and 'true' otherwise. |
| // isWord() will specify was it word or separator (one character). |
| // lex() will return zero-terminated lexem string scanned (for word or separator). |
| // |
| bool Tokens::scan () |
| { |
| while (isspace(*src)) |
| src++; |
| |
| if (*src == 0) |
| return false; |
| |
| dst = buff; |
| isw = isalnum(*src) != 0; |
| if (!isw) |
| *dst++ = *src++; |
| else |
| while (isalnum(*src)) |
| { |
| assert(dst != &buff[sizeof(buff)-1]); |
| *dst++ = *src++; |
| } |
| |
| *dst = 0; |
| return true; |
| } |
| |
| |
| const int MAXREGS = IRMaxRegNamesSameKind*IRMaxRegKinds; |
| |
| |
| // Temporary structure to describe operand that can be evicted. |
| // Used to choose the best operand to evict. |
| // |
| struct SpillGen::Evict |
| { |
| Opnd* opnd; |
| Instx* begx, * endx; |
| int weight; |
| |
| bool operator < (const Evict& x) const {return weight < x.weight;} |
| }; |
| |
| |
| //// Misc helpers |
| ///// ---------------------- |
| |
| |
| static size_t bitCount (SpillGen::RegMask mk) |
| { |
| size_t count = 0; |
| while (mk != 0) |
| { |
| if ((mk & 1) != 0) |
| ++count; |
| mk >>= 1; |
| } |
| return count; |
| } |
| |
| |
| static void merge (Constraint& c, SpillGen::RegMask mk) |
| { |
| c.setMask(c.getMask() | mk); |
| } |
| |
| |
| // Parse input parameters (registers available) and build table of the regsiters |
| // available for allocalion ('registers'). |
| // |
| void SpillGen::Registers::parse (const char* params) |
| { |
| if (params == 0 || strcmp(params, "ALL") == 0) |
| { |
| |
| #ifdef HYX86_64 |
| push_back(Constraint(RegName_R8) |
| |Constraint(RegName_RAX) |
| |Constraint(RegName_RCX) |
| |Constraint(RegName_RBX) |
| |Constraint(RegName_RDX) |
| |Constraint(RegName_RSI) |
| |Constraint(RegName_RDI) |
| |Constraint(RegName_R9) |
| |Constraint(RegName_R10) |
| |Constraint(RegName_R11) |
| |Constraint(RegName_R12)); |
| #else |
| push_back(Constraint(RegName_EAX) |
| |Constraint(RegName_ECX) |
| |Constraint(RegName_EDX) |
| |Constraint(RegName_EBX) |
| |Constraint(RegName_ESI) |
| |Constraint(RegName_EDI) |
| |Constraint(RegName_EBP)); |
| #endif |
| |
| push_back(Constraint(RegName_XMM1) |
| |Constraint(RegName_XMM0) |
| |Constraint(RegName_XMM2) |
| |Constraint(RegName_XMM3) |
| |Constraint(RegName_XMM4) |
| |Constraint(RegName_XMM5) |
| |Constraint(RegName_XMM6) |
| |Constraint(RegName_XMM7)); |
| |
| push_back(Constraint(RegName_FP0)); |
| } |
| else |
| { |
| Constraint c; |
| for (Tokens t(params); t.scan(); ) |
| if (t.isWord()) |
| { |
| RegName r = getRegName(t.lex()); |
| if (r != RegName_Null) |
| c = Constraint(r); |
| |
| merge(c, true); |
| } |
| } |
| |
| assert(!empty()); |
| |
| for (size_t i = 0; i != IRMaxRegKinds; ++i) |
| indexes[i] = -1; |
| |
| for (size_t i = 0; i != size(); ++i) |
| indexes[operator[](i).getKind()] = (int)i; |
| } |
| |
| |
| void SpillGen::Registers::clearMasks () |
| { |
| for (size_t i = 0; i != size(); ++i) |
| operator[](i).setMask(0); |
| } |
| |
| |
| void SpillGen::Registers::merge (const SpillGen::Registers& x) |
| { |
| for (size_t i = 0; i != size(); ++i) |
| { |
| Constraint& r = operator[](i); |
| r.setMask(r.getMask() | x[i].getMask()); |
| } |
| } |
| |
| |
| int SpillGen::Registers::merge (const Constraint& c, bool add) |
| { |
| if (c.getMask() != 0) |
| { |
| for (size_t i = 0; i != size(); ++i) |
| { |
| Constraint& r = operator[](i); |
| if (r.getKind() == c.getKind()) |
| { |
| r.setMask(r.getMask() | c.getMask()); |
| return (int)i; |
| } |
| } |
| |
| if (add) |
| push_back(c); |
| } |
| |
| return -1; |
| } |
| |
| |
| int SpillGen::Registers::getIndex (const Constraint& c) const |
| { |
| return indexes[c.getKind() & OpndKind_Reg]; |
| } |
| |
| |
| Constraint* SpillGen::Registers::contains (const Constraint& c) |
| { |
| for (size_t i = 0; i != size(); ++i) |
| { |
| Constraint& r = operator[](i); |
| if (r.getKind() == c.getKind() && (r.getMask() & c.getMask()) != 0) |
| return &r; |
| } |
| |
| return 0; |
| } |
| |
| |
| void SpillGen::Opline::clear (MemoryManager& mm) |
| { |
| if (ops == 0) |
| ops = new (mm) Ops(mm); |
| else |
| ops->clear(); |
| |
| opnd_mem = 0; |
| save_instx = 0; |
| } |
| |
| |
| void SpillGen::Opline::addOp (Instx* instx, OpRole oprole) |
| { |
| if (ops->empty() || ops->back().instx != instx) |
| { |
| Op tmp; |
| tmp.instx = instx; |
| tmp.oprole = oprole; |
| ops->push_back(tmp); |
| } |
| else |
| { |
| ops->back().oprole |= oprole; |
| } |
| |
| op = 0; |
| } |
| |
| |
| void SpillGen::Opline::start () |
| { |
| assert(!ops->empty()); |
| op = &ops->back(); |
| instx = op->instx; |
| } |
| |
| |
| void SpillGen::Opline::forw () |
| { |
| assert(op != 0); |
| assert(!ops->empty()); |
| if (op == &ops->front()) |
| { |
| op = 0; |
| return; |
| } |
| |
| assert(instx != ops->front().instx); |
| ++instx; |
| |
| Op* opx = op - 1; |
| if (opx->instx == instx) |
| op = opx; |
| } |
| |
| |
| void SpillGen::Opline::back (const Instx* x) |
| { |
| if (op == 0) |
| { |
| assert(!ops->empty()); |
| op = &ops->front(); |
| instx = op->instx; |
| } |
| |
| while (instx != x) |
| { |
| assert(instx != ops->back().instx); |
| if (op->instx == instx) |
| ++op; |
| |
| --instx; |
| } |
| } |
| |
| |
| static bool operator == (const SpillGen::Op& op, const Inst* i) |
| { |
| return op.instx->inst == i; |
| } |
| |
| |
| bool SpillGen::Opline::isDef (const Inst* i) const |
| { |
| Ops::iterator end, ptr = find(ops->begin(), end = ops->end(), i); |
| return ptr != end && (ptr->oprole & RoleDef) != 0; |
| } |
| |
| |
| bool SpillGen::Opline::isUse (const Inst* i) const |
| { |
| Ops::iterator end, ptr = find(ops->begin(), end = ops->end(), i); |
| return ptr != end && (ptr->oprole & RoleUse) != 0; |
| } |
| |
| |
| ///// SpillGen |
| ///// ---------------------- |
| |
| |
| void SpillGen::runImpl() |
| { |
| #ifdef _DEBUG_SPILLGEN |
| onConstruct(*this); |
| #endif |
| |
| const bool* spill_flag = static_cast<const bool*>(getIRManager().getInfo("SpillGen")); |
| if (spill_flag != 0 && !*spill_flag) |
| { |
| DBGOUT("SpillGen skipped" << endl;); |
| return; |
| } |
| |
| registers.parse(getArg("regs")); |
| DBGOUT("parameters: " << registers << endl;) |
| irManager->resetOpndConstraints(); |
| |
| fails = 0; |
| emitted = 0; |
| |
| opndcount = irManager->getOpndCount(); |
| lives_exit = new (mm) BitSet(mm, (U_32)opndcount); |
| |
| actsmap.resize(opndcount); |
| for (size_t i = 0; i < opndcount; ++i) |
| actsmap[i] = 0; |
| |
| const Nodes& nodes = irManager->getFlowGraph()->getNodes(); |
| for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) { |
| Node* node = *it; |
| if (node->isBlockNode()) |
| { |
| bblock = node; |
| if (bblock->isEmpty()) { |
| continue; |
| } |
| |
| lives_start = irManager->getLiveAtEntry(bblock); |
| lives_exit->resize((U_32)opndcount); |
| irManager->getLiveAtExit(bblock, *lives_exit); |
| |
| size_t bfails = 0; |
| |
| for (;;) |
| { |
| if (pass0() == 0) |
| break; |
| |
| #ifdef _DEBUG_SPILLGEN |
| if (Log::isEnabled()) |
| outInstxs(Log::out(), *this); |
| #endif |
| |
| size_t x; |
| if ((x = pass1()) == 0 || x == bfails) |
| { |
| bfails = x; |
| |
| if (x != 0 && Log::isEnabled()) |
| Log::out() << "SpillGen cannot assign operand(s)" << std::endl; |
| |
| break; |
| } |
| bfails = x; |
| |
| DBGOUT(endl << "reiterating BB#"<< bblock->getId() << endl;) |
| |
| if (opndcount != irManager->getOpndCount()) |
| { |
| size_t oldcount = opndcount; |
| opndcount = irManager->getOpndCount(); |
| lives_exit->resize((U_32)opndcount); |
| irManager->fixLivenessInfo(); |
| |
| actsmap.resize(opndcount); |
| for (; oldcount < opndcount; ++oldcount) |
| actsmap[oldcount] = 0; |
| } |
| } |
| |
| fails += bfails; |
| } |
| } |
| |
| static Counter<size_t> count_emits("ia32:spillgen:emits", 0); |
| count_emits += emitted; |
| |
| #ifdef _DEBUG_SPILLGEN |
| DBGOUT(endl << "Emitted movs :" << emitted << endl); |
| |
| if (fails) |
| DBGOUT(endl << "FAILS: " << fails << endl); |
| #endif |
| |
| assert(fails == 0); |
| |
| if (fails != 0) |
| Jitrino::crash("SpillGen failed"); |
| |
| #ifdef _DEBUG_SPILLGEN |
| onDestruct(*this); |
| #endif |
| } |
| |
| |
| bool SpillGen::verify (bool force) |
| { |
| bool failed = false; |
| |
| if (force || getVerificationLevel() >= 1) |
| { |
| irManager->packOpnds(); |
| irManager->updateLivenessInfo(); |
| |
| if (!RegAllocCheck(*irManager).run(true)) |
| failed = true; |
| |
| if (!SessionAction::verify(true)) |
| failed = true; |
| } |
| |
| return !failed; |
| } |
| |
| |
| // Preprocessing phase. |
| // Scans all instructions in the basic block and create 'Instx' extension structure for |
| // every instruction with required information. |
| // Identifies all operands that needed to be allocated (problem operands) and fill 'Opline' |
| // structure for each. |
| // |
| size_t SpillGen::pass0 () |
| { |
| static CountTime pass0Timer("ia32::spillgen:pass0"); |
| AutoTimer tm(pass0Timer); |
| |
| actives.resize(0); |
| |
| evicts_known = false; |
| |
| const size_t regkinds = registers.size(); |
| assert(regkinds <= IRMaxRegKinds); |
| |
| instxs.resize(bblock->getInstCount() + 1); |
| |
| instxs[0].inst = 0; |
| if (instxs[0].evicts == 0) |
| instxs[0].evicts = new (mm) Opnds(mm); |
| else |
| instxs[0].evicts->resize(0); |
| |
| Instxs::iterator instxp = instxs.end() - 1; |
| |
| for (size_t i = 0; i < regkinds; ++i) |
| instxp->regusage [i] = 0; |
| |
| #ifdef _DEBUG_SPILLGEN |
| DBGOUT(endl << "BB#"<< bblock->getId()); |
| if (!instxs.empty()) |
| DBGOUT (" [" << *(Inst*)bblock->getFirstInst() << " - " << *(Inst*)bblock->getLastInst() << "] "); |
| DBGOUT(instxs.size() - 1 << endl); |
| #endif |
| |
| // calculate registers used at the block exit |
| |
| BitSet lives_next = *lives_exit; |
| BitSet::IterB ib(*lives_exit); |
| for (int i = ib.getNext(); i != -1; i = ib.getNext()) |
| { |
| Constraint loc = irManager->getOpnd(i)->getConstraint(Opnd::ConstraintKind_Location, OpndSize_Default); |
| int idx = registers.getIndex(loc); |
| if (!loc.isNull() && idx != -1) |
| {// this operand is already assigned to some location/register |
| instxp->regusage[idx] |= loc.getMask(); |
| } |
| } |
| |
| // iterate over instructions towards the top of the block |
| |
| for (Inst* inst = (Inst*)bblock->getLastInst(); inst != 0; inst = inst->getPrevInst()) |
| { |
| // Prepare processing of the next instruction |
| |
| Instxs::iterator instxq = instxp - 1; |
| for (size_t i = 0; i < regkinds; ++i) |
| instxq->regusage [i] = instxp->regusage[i]; |
| |
| // Process current instruction |
| |
| instxp->inst = inst; |
| |
| size_t nbopnds = inst->getOpndCount(Inst::OpndRole_All); |
| if (instxp->nbopnds < nbopnds) |
| instxp->oproles = new (mm) OpRole[instxp->nbopnds = (nbopnds + 8) & ~7]; |
| |
| for (size_t i = 0; i < regkinds; ++i) |
| instxp->regpress[i] = 0; |
| |
| Opnd* opnd; |
| size_t itx = 0; |
| Inst::Opnds opnds(inst, Inst::OpndRole_All); |
| for (Inst::Opnds::iterator it = opnds.begin(); it != opnds.end(); it = opnds.next(it), ++itx) |
| { |
| opnd = inst->getOpnd(it); |
| |
| U_32 roles = inst->getOpndRoles(it); |
| |
| OpRole oprole = 0; |
| |
| if ((roles & Inst::OpndRole_Def) != 0) |
| oprole |= RoleDef; |
| |
| if ((roles & Inst::OpndRole_Use) != 0 || (inst->getProperties() & Inst::Properties_Conditional) != 0) |
| oprole |= RoleUse; |
| |
| if ((inst->getProperties() & Inst::Properties_Conditional) != 0) |
| oprole |= RoleCond; |
| |
| if (!lives_next.getBit(opnd->getId())) |
| oprole |= RoleEnd; |
| |
| assert(itx < instxp->nbopnds); |
| instxp->oproles[itx] = oprole; |
| |
| Constraint loc = opnd->getConstraint(Opnd::ConstraintKind_Location, OpndSize_Default); |
| if (!loc.isNull()) |
| {// this operand is already assigned to some location/register |
| int idx; |
| if ((idx = registers.getIndex(loc)) != -1) |
| { |
| RegMask msk = loc.getMask(); |
| assert(msk != 0); |
| RegMask was = instxp->regusage[idx]; |
| instxq->regusage [idx] |= msk; |
| if ((oprole & RoleUse) != 0) |
| { |
| } |
| else if ((oprole & (RoleDef | RoleCond)) == RoleDef) |
| { |
| instxq->regusage[idx] &= ~msk; |
| if ((was & msk) == 0) |
| { |
| DBGOUT("dead def " << *inst << " " << *opnd << endl;) |
| instxp->regusage [idx] |= msk; |
| } |
| } |
| } |
| } |
| else |
| {// this operand is not allocated yet |
| unsigned mask = (1<<inst->getOpndCount())-1; |
| loc = ((Inst*)inst)->getConstraint(it, mask, OpndSize_Default); |
| int idx = registers.getIndex(loc); |
| Opline* opline = actsmap[opnd->getId()]; |
| if (opline == 0) |
| {// Is this is a problem operand? |
| if (!(loc & Constraint(OpndKind_Memory)).isNull() || idx != -1) |
| {// operand can be assigned to memory or register |
| actives.resize(actives.size() + 1); |
| opline = &actives.back(); |
| actsmap[opnd->getId()] = opline; |
| |
| opline->clear(mm); |
| opline->opnd = opnd; |
| opline->at_start = lives_start->getBit(opnd->getId()); |
| opline->at_exit = lives_exit->getBit(opnd->getId()); |
| opline->initial = loc; |
| } |
| else |
| { |
| DBGOUT("Cannot assign " << *opnd << " @ " << *opline->instx->inst << endl;) |
| } |
| } |
| else |
| { |
| opline->initial.intersectWith(loc); |
| } |
| |
| // this operand is tracked |
| if (opline != 0) |
| { |
| opline->addOp(&*instxp, oprole); |
| |
| if ((loc & Constraint(OpndKind_Memory)).isNull()) |
| {// Operand cannot assigned to memory |
| assert(idx != -1); |
| if (bitCount(loc.getMask()) == 1) |
| instxp->regpress[idx] |= loc.getMask(); |
| } |
| } |
| } |
| |
| if (inst->isLiveRangeEnd(it)) |
| lives_next.setBit(opnd->getId(), false); |
| else if (inst->isLiveRangeStart(it)) |
| lives_next.setBit(opnd->getId(), true); |
| } |
| |
| instxp = instxq; |
| } |
| |
| assert(instxp == instxs.begin()); |
| return actives.size(); |
| } |
| |
| |
| |
| // Allocation phase. |
| // Allocate all problem operands for the current block. |
| // |
| size_t SpillGen::pass1 () |
| { |
| static CountTime pass1Timer("ia32::spillgen:pass1"); |
| AutoTimer tm(pass1Timer); |
| |
| size_t fails = 0; |
| |
| if (actives.size() > 1) |
| { |
| for (Oplines::iterator it = actives.begin(); it != actives.end(); ++it) |
| { |
| Opline& opline = *it; |
| opline.weight = (int)bitCount(opline.initial.getMask()); |
| } |
| sort(actives.begin(), actives.end(), Opline::smaller); |
| } |
| |
| lives_catch = 0; |
| Node* node = bblock->getExceptionEdgeTarget(); |
| if (node != NULL) |
| if ((lives_catch = irManager->getLiveAtEntry(node))->isEmpty()) |
| lives_catch = 0; |
| |
| for (Oplines::reverse_iterator it = actives.rbegin(); it != actives.rend(); ++it) |
| { |
| Opline& opline = *it; |
| if (actsmap[opline.opnd->getId()] == 0) |
| continue; |
| |
| actsmap[opline.opnd->getId()] = 0; |
| |
| #ifdef _DEBUG_SPILLGEN |
| opruns.incr(opline.ops->size()); |
| #endif |
| opline.opnd_mem = 0; |
| opline.save_instx = 0; |
| opline.save_changed = false; |
| opline.start(); |
| |
| // Is this operand lives at the corresponding Dispatch node entry ? |
| opline.catched = (lives_catch == 0) ? false : lives_catch->getBit(opline.opnd->getId()); |
| |
| DBGOUT(opline;) |
| |
| // Begin-block processing |
| |
| RegMask prefreg = 0; |
| |
| // Is this operand lives at entry of this node ? |
| if (opline.at_start) |
| saveOpnd(opline, opline.instx, opndMem(opline)); |
| else |
| prefreg = lookPreffered(opline); |
| |
| // Process instructions that are using the operand |
| |
| while (opline.go()) |
| if (opline.isProc()) |
| { |
| Constraint c(opline.opnd->getConstraint(Opnd::ConstraintKind_Initial)); |
| update(opline.instx->inst, opline.opnd, c); |
| opline.idx = registers.getIndex(c); |
| |
| if (!tryRegister(opline, c, prefreg)) |
| if (!tryMemory(opline, c)) |
| if (!tryEvict(opline, c)) |
| if (!tryRepair(opline, c)) |
| {// Cannot assign operand, so let it remains in the original form |
| DBGOUT("Cannot assign " << opline.opnd << " @ " << *opline.instx->inst << endl;) |
| ++fails; |
| |
| if (simplify(opline.instx->inst, opline.opnd)) |
| { |
| loadOpndMem(opline); |
| break; |
| } |
| |
| loadOpnd(opline, opline.instx, opline.opnd); |
| |
| if (opline.isDef()) |
| opline.save_changed = true; |
| |
| saveOpnd(opline, opline.instx, opline.opnd); |
| |
| opline.forw(); |
| } |
| } |
| else |
| { |
| opline.forw(); |
| } |
| |
| // End-block processing |
| |
| //assert(opline.instx == opline.ops->front().instx); |
| if (opline.at_exit) |
| loadOpndMem(opline); |
| } |
| return fails; |
| } |
| |
| |
| SpillGen::RegMask SpillGen::lookPreffered (Opline& opline) |
| { |
| Inst* inst = opline.instx->inst; |
| if (inst->getMnemonic() != Mnemonic_MOV || inst->getOpnd(0) != opline.opnd) |
| return 0; |
| |
| if ((opline.instx->oproles[1] & RoleEnd) == 0) |
| return 0; |
| |
| Opnd* opnd1 = inst->getOpnd(1); |
| |
| RegMask msk; |
| Constraint loc = opnd1->getConstraint(Opnd::ConstraintKind_Location, OpndSize_Default); |
| if (!loc.isNull() && registers.getIndex(loc) != -1) |
| msk = loc.getMask(); |
| else |
| return 0; |
| |
| DBGOUT("COALESCE at " << *inst << " " << *opnd1 << endl;) |
| return msk; |
| } |
| |
| |
| // Attempt to allocate a register for the operand. |
| // |
| bool SpillGen::tryRegister (Opline& opline, Constraint c, RegMask prefreg) |
| { |
| if (opline.idx == -1) |
| return false; |
| |
| Constraint cx = c.getAliasConstraint(OpndSize_Default) & registers[opline.idx]; |
| Constraint cr((OpndKind)cx.getKind(), c.getSize(), cx.getMask()); |
| |
| // handle first instruction of the interval |
| |
| RegMask mk = cr.getMask() & ~usedRegs(opline.instx, opline.idx, opline.isUse()); |
| if (mk == 0) |
| { |
| DBGOUT(" -No reg [" << *opline.instx->inst << "]" << c << endl;) |
| return false; |
| } |
| |
| RegMask mkpost = ~(RegMask)0; |
| if (!opline.isDef()) |
| mkpost = callRegs(opline.instx, opline.idx); |
| |
| // handle second and all others instructions |
| |
| Instx* begx = opline.instx; |
| Instx* endx = begx; |
| int count = 0; |
| for (opline.forw(); opline.go(); opline.forw()) |
| { |
| RegMask tmp = mk & mkpost; |
| if (opline.isEnd()) |
| tmp &= ~opline.instx->regusage[opline.idx-1]; |
| else |
| tmp &= ~opline.instx->regusage[opline.idx]; |
| |
| if (tmp == 0) |
| break; |
| |
| int cnt = 0; |
| if (opline.isProc()) |
| { |
| if (opline.isDef() && !opline.isUse()) |
| break; |
| |
| if ((cnt = update(opline.instx->inst, opline.opnd, cr)) != 0) |
| { |
| tmp &= cr.getMask(); |
| if (tmp == 0) |
| break; |
| endx = opline.instx; |
| } |
| } |
| |
| mk = tmp; |
| mkpost = callRegs(opline.instx, opline.idx); |
| count += cnt; |
| } |
| |
| DBGOUT(" -reg [" << *begx->inst << " - " << *endx->inst |
| << "] avail:" << RegMasks(cx, mk) << " count:" << count << endl;) |
| |
| if (count == 0) |
| { |
| assert(begx == endx); |
| Constraint cm = c & OpndKind_Memory; |
| if (!cm.isNull()) |
| { |
| DBGOUT(" -mem [" << *begx->inst << "]" << endl;) |
| assignMem(opline, begx, begx); |
| return true; |
| } |
| } |
| |
| if ((mk & prefreg) != 0) |
| { |
| mk &= prefreg; |
| static Counter<size_t> count_preffer("ia32:spillgen:preffered", 0); |
| count_preffer++; |
| } |
| RegName rn = findFree(mk, opline.idx, begx); |
| assignReg(opline, begx, endx, rn); |
| return true; |
| } |
| |
| |
| // Attempt to assign operand to memory. |
| // |
| bool SpillGen::tryMemory (Opline& opline, Constraint c) |
| { |
| c.intersectWith(OpndKind_Memory); |
| if (c.isNull()) |
| { |
| DBGOUT(" -No mem [" << *opline.instx->inst << "]" << endl;) |
| return false; |
| } |
| |
| DBGOUT(" -mem [" << *opline.instx->inst << "]" << endl;) |
| assignMem(opline, opline.instx, opline.instx); |
| opline.forw(); |
| return true; |
| } |
| |
| |
| // Attempt to find other operand that can be temporary saved to memory and use it's register |
| // for the operand processed. |
| // |
| bool SpillGen::tryEvict (Opline& opline, Constraint c) |
| { |
| if (opline.idx == -1) |
| return false; |
| |
| Constraint cx = c.getAliasConstraint(OpndSize_Default) & registers[opline.idx]; |
| Constraint cr((OpndKind)cx.getKind(), c.getSize(), cx.getMask()); |
| |
| Instx* begx = opline.instx; |
| Instx* endx = begx; |
| |
| for (opline.forw(); opline.go(); opline.forw()) |
| { |
| Constraint cx = cr; |
| if (update(opline.instx->inst, opline.opnd, cx)) |
| if (cx.getMask() == 0) |
| break; |
| |
| cr = cx; |
| endx = opline.instx; |
| } |
| |
| RegName rn = findEvict(cr.getMask(), opline.idx, begx, endx); |
| if (rn == RegName_Null) |
| { |
| DBGOUT(" -No evict [" << *begx->inst << " - " << *endx->inst << "]" << endl;) |
| opline.back(begx); |
| return false; |
| } |
| |
| DBGOUT(" -evict [" << *begx->inst << " - " << *endx->inst |
| << "] " << getRegNameString(rn) << endl;) |
| |
| static Counter<size_t> count_evicts("ia32:spillgen:evicts", 0); |
| count_evicts++; |
| |
| assignReg(opline, begx, endx, rn); |
| |
| opline.back(endx); |
| opline.forw(); |
| return true; |
| } |
| |
| |
| // Attempt to change allocation that was previously made, i.e. reassign register that |
| // already used in the instruction for other operand because the processed operand |
| // requires already assigned register. |
| // |
| bool SpillGen::tryRepair (Opline& opline, Constraint c) |
| { |
| if (opline.idx == -1) |
| return false; |
| |
| Constraint ca = c.getAliasConstraint(OpndSize_Default) & registers[opline.idx]; |
| Constraint cr((OpndKind)ca.getKind(), c.getSize(), ca.getMask()); |
| |
| Inst* inst = opline.instx->inst; |
| |
| RegMask mk = cr.getMask(); |
| |
| Opnd* ox = 0, *ox_out = 0; |
| RegName rx = RegName_Null; |
| bool need_load = false, |
| need_save = false; |
| |
| size_t itx = 0; |
| Inst::Opnds opnds(inst, Inst::OpndRole_All); |
| for (Inst::Opnds::iterator it = opnds.begin(); it != opnds.end(); it = opnds.next(it), ++itx) |
| { |
| ox = inst->getOpnd(it); |
| RegMask oxMask = ox->getConstraint(Opnd::ConstraintKind_Initial).getMask(); |
| |
| RegMask rm = getRegMaskConstr(ox, cr); |
| if ((mk & rm) != 0) |
| { |
| OpRole oprole = opline.instx->oproles[itx]; |
| need_load = (oprole & RoleUse) != 0; |
| need_save = (oprole & RoleEnd) == 0; |
| |
| unsigned mask = (1<<inst->getOpndCount())-1; |
| Constraint cx = ((Inst*)inst)->getConstraint(it, mask, OpndSize_Default); |
| RegMask used = usedRegs(opline.instx, opline.idx, need_load); |
| RegMask usable = (cx & registers[opline.idx]).getMask() & ~mk & oxMask; |
| if ((usable & ~used) != 0) |
| { |
| rx = findFree(usable & ~used, opline.idx, opline.instx); |
| ox_out = opndReg(ox, rx); |
| break; |
| } |
| else if (!(cx & OpndKind_Memory).isNull()) |
| { |
| ox_out = opndMem(ox); |
| break; |
| } |
| else |
| { |
| rx = findEvict(usable, opline.idx, opline.instx, opline.instx); |
| if (rx != RegName_Null) |
| { |
| ox_out = opndReg(ox, rx); |
| break; |
| } |
| } |
| } |
| } |
| |
| if (ox_out == 0) |
| return false; |
| |
| // relocate operand 'ox' to new register 'rx' |
| |
| DBGOUT(" -repair [" << *inst << "] " << *opline.opnd |
| << " " << *ox << " " << *ox_out << endl;) |
| |
| static Counter<size_t> count_repairs("ia32:spillgen:repairs", 0); |
| count_repairs++; |
| |
| if (need_load) |
| emitMove(true, inst, ox_out, ox); |
| if (need_save) |
| emitMove(false, inst, ox, ox_out); |
| |
| inst->replaceOpnd(ox, ox_out); |
| if (rx != RegName_Null /*&& need_save*/) |
| opline.instx->regusage[opline.idx] |= getRegMask(rx); |
| |
| // assign the requsted operand to the register which was previosly assigned to ox |
| |
| assignReg(opline, opline.instx, opline.instx, ox->getRegName()); |
| opline.forw(); |
| return true; |
| } |
| |
| |
| bool SpillGen::simplify (Inst* inst, Opnd* opnd) |
| { |
| Opnd* opndm; |
| if (inst->hasKind(Inst::Kind_LocalControlTransferInst) && inst->getOpndCount() == 1) |
| { |
| opndm = inst->getOpnd(0); |
| Opnd* opndx = irManager->newMemOpnd(opndm->getType(), |
| MemOpndKind_StackAutoLayout, |
| irManager->getRegOpnd(STACK_REG), |
| 0); |
| DBGOUT("simplify jump " << *opndm << " -> mem " << *opndx << endl;); |
| emitMove(true, inst,opndx, opndm); |
| inst->replaceOpnd(opndm, opndx); |
| |
| for (int so = 0; so != MemOpndSubOpndKind_Count; ++so) |
| { |
| Opnd* sub = opndm->getMemOpndSubOpnd(static_cast<MemOpndSubOpndKind>(so)); |
| if (sub != 0) |
| actsmap[sub->getId()] = 0; |
| } |
| return true; |
| } |
| |
| else if (inst->hasKind(Inst::Kind_CallInst) && (opndm = inst->getOpnd(0)) == opnd) |
| { |
| Opnd* opndx = irManager->newMemOpnd(opndm->getType(), |
| MemOpndKind_StackAutoLayout, |
| irManager->getRegOpnd(STACK_REG), |
| 0); |
| DBGOUT("simplify call " << *opndm << " -> mem " << *opndx << endl;); |
| emitMove(true, inst,opndx, opndm); |
| inst->replaceOpnd(opndm, opndx); |
| |
| for (int so = 0; so != MemOpndSubOpndKind_Count; ++so) |
| { |
| Opnd* sub = opndm->getMemOpndSubOpnd(static_cast<MemOpndSubOpndKind>(so)); |
| if (sub != 0) |
| actsmap[sub->getId()] = 0; |
| } |
| return true; |
| } |
| |
| return false; |
| } |
| |
| |
| // Return mask of all free registers at the instruction specified. |
| // If register will define value, set isuse=false. |
| // If regsiter will load value defined in some other instruction, set isuse=true |
| // |
| SpillGen::RegMask SpillGen::usedRegs (const Instx* instx, int idx, bool isuse) const |
| { |
| RegMask used = instx->regusage[idx]; |
| if (isuse) |
| used |= (used ^ (instx-1)->regusage[idx]); |
| |
| return used; |
| } |
| |
| |
| SpillGen::RegMask SpillGen::callRegs (const Instx* instx, int idx) const |
| { |
| if (instx->inst->getMnemonic() == Mnemonic_CALL) |
| { |
| OpndKind k = static_cast<OpndKind>(registers[idx].getKind()); |
| Constraint ci = static_cast<CallInst*>(instx->inst)->getCalleeSaveRegs(k); |
| return ci.getMask(); |
| } |
| |
| return ~(RegMask)0; |
| } |
| |
| |
| // If currently handled operand is referenced by current instruction, then evaluate |
| // constraint of the operand imposed by this instruction and return 'true'. |
| // Otherwise, do nothing and return false. |
| // |
| int SpillGen::update (const Inst* inst, const Opnd* opnd, Constraint& constr) const |
| { |
| int count = 0; |
| Inst::Opnds opnds(inst, Inst::OpndRole_All); |
| for (Inst::Opnds::iterator it = opnds.begin(); it != opnds.end(); it = opnds.next(it)) |
| if ( inst->getOpnd(it) == opnd) |
| { |
| // if operand occures more than once then conservatively take |
| // the strong constraint for the operand |
| Constraint c; |
| c = ((Inst*)inst)->getConstraint(it, count?0xFFFFFFFF:0x7FFFFFFF, constr.getSize()); |
| if (constr.isNull()) |
| constr = c; |
| else |
| constr.intersectWith(c); |
| |
| count++; |
| } |
| return count; |
| } |
| |
| |
| // Split operand and assign register 'rn' to it in the interval specified |
| // ('begx' - 'endx', inclusive) |
| // |
| void SpillGen::assignReg (Opline& opline, Instx* begx, Instx* endx, RegName rn) |
| { |
| assert(rn != RegName_Null); |
| RegMask mk = getRegMask(rn); |
| Opnd* opnd_reg = opndReg(opline.opnd, rn); |
| |
| int reguses = 0; |
| |
| DBGOUT("assignReg " << *opline.opnd << " [" << *begx->inst |
| << " - " << *endx->inst << "] to " << *opnd_reg << endl;) |
| |
| if (loadOpnd(opline, begx, opnd_reg)) |
| (begx-1)->regusage[opline.idx] |= mk; |
| |
| bool has_def = false; |
| Instx* savex = endx; |
| |
| for (Instx* ptrx = begx; ptrx <= endx; ++ptrx) |
| { |
| if (opline.save_changed && opline.catched && ptrx->inst->hasKind(Inst::Kind_CallInst)) |
| { |
| emitMove(true, ptrx->inst, opndMem(opline), opnd_reg); |
| opline.save_changed = false; |
| } |
| |
| if (ptrx->inst->replaceOpnd(opline.opnd, opnd_reg)) |
| {// the operand is used in the instruction |
| ++reguses; |
| if (opline.isDef(ptrx->inst)) |
| { |
| has_def = true; |
| opline.save_changed = true; |
| savex = ptrx; |
| } |
| } |
| else |
| {// the operand is not used in the instruction, so it can be evicted |
| if (ptrx->evicts != 0) |
| ptrx->evicts->push_back(opnd_reg); |
| } |
| |
| // special processing for dead-definition (begx == endx && has_def) |
| if (ptrx != endx || (begx == endx && has_def)) |
| ptrx->regusage[opline.idx] |= mk; |
| } |
| |
| bool before = false; |
| if (savex->inst->getMnemonic() == Mnemonic_CALL && !opline.isDef(savex->inst)) |
| { |
| Constraint ci = static_cast<CallInst*>(savex->inst)->getCalleeSaveRegs(getRegKind(rn)); |
| before = (ci.getMask() & mk) == 0; |
| } |
| saveOpnd(opline, savex, opnd_reg, before ? 0 : mk, opline.idx, before); |
| |
| #ifdef _DEBUG_SPILLGEN |
| assigns.incr(reguses); |
| #endif |
| } |
| |
| |
| // Split operand and assign memory location to it in the interval specified |
| // ('begx' - 'endx', inclusive) |
| // |
| void SpillGen::assignMem (Opline& opline, Instx* begx, Instx* endx) |
| { |
| opndMem(opline); |
| |
| DBGOUT("assignMem " << *opline.opnd << " [" << *begx->inst |
| << " - " << *endx->inst << "] to " << *opline.opnd_mem << endl;) |
| |
| loadOpnd(opline, begx, opline.opnd_mem); |
| |
| if (opline.opnd != opline.opnd_mem) |
| for (; begx <= endx; ++begx) |
| { |
| begx->inst->replaceOpnd(opline.opnd, opline.opnd_mem); |
| } |
| |
| saveOpnd(opline, endx, opline.opnd_mem); |
| opline.save_changed = false; |
| } |
| |
| |
| // Lazy save 'opnd' to memory at the point 'instx' |
| // |
| void SpillGen::saveOpnd (Opline& opline, Instx* instx, Opnd* opnd) |
| { |
| opline.save_instx = instx; |
| opline.save_before = false; |
| opline.save_opnd = opnd; |
| opline.save_regmsk = 0; |
| opline.save_regidx = -1; |
| } |
| |
| |
| void SpillGen::saveOpnd (Opline& opline, Instx* instx, Opnd* opnd, RegMask regmsk, int regidx, bool before) |
| { |
| opline.save_instx = instx; |
| opline.save_before = before; |
| opline.save_opnd = opnd; |
| opline.save_regmsk = regmsk; |
| opline.save_regidx = regidx; |
| } |
| |
| |
| // Load operand from memory to 'opnd' at the poinr 'instx' |
| // |
| bool SpillGen::loadOpnd (Opline& opline, Instx* instx, Opnd* opnd) |
| { |
| if (opline.save_instx == 0 || !opline.isUse(instx->inst)) |
| return false; |
| |
| if (opline.save_opnd->hasAssignedPhysicalLocation()) |
| { |
| opndMem(opline); |
| if (opline.save_changed) |
| { |
| emitMove(opline.save_before, |
| opline.save_instx->inst, |
| opline.opnd_mem, |
| opline.save_opnd); |
| if (opline.save_regmsk != 0) |
| opline.save_instx->regusage[opline.save_regidx] |= opline.save_regmsk; |
| opline.save_changed = false; |
| } |
| emitMove(true, instx->inst, opnd, opline.opnd_mem); |
| } |
| else |
| { |
| if (opnd->hasAssignedPhysicalLocation()) |
| {// Assigned <- UnAssigned |
| emitMove(true, instx->inst, opnd, opline.save_opnd); |
| } |
| else |
| {// UnAssigned <- UnAssigned |
| assert(opnd == opline.save_opnd); |
| opline.save_opnd = opnd; |
| opline.save_instx = instx; |
| } |
| } |
| return true; |
| } |
| |
| |
| // Save operand to memory |
| // |
| void SpillGen::loadOpndMem (Opline& opline) |
| { |
| if (opline.save_instx == 0) |
| return; |
| |
| if (opline.save_opnd->hasAssignedPhysicalLocation()) |
| { |
| if (opline.save_changed) |
| { |
| emitMove(opline.save_before, |
| opline.save_instx->inst, |
| opndMem(opline), |
| opline.save_opnd); |
| if (opline.save_regmsk != 0) |
| opline.save_instx->regusage[opline.save_regidx] |= opline.save_regmsk; |
| opline.save_changed = false; |
| } |
| } |
| } |
| |
| |
| Opnd* SpillGen::opndMem (Opline& opline) |
| { |
| if (opline.opnd_mem == 0) |
| opline.opnd_mem = opndMem(opline.opnd); |
| |
| return opline.opnd_mem; |
| } |
| |
| |
| static bool operator == (const SpillGen::TwoOpnds& p, const Opnd* o) |
| { |
| return p.first == o; |
| } |
| |
| |
| Opnd* SpillGen::opndMem (const Opnd* opnd) |
| { |
| Opnd* opnd_mem; |
| |
| MemOpnds::iterator ptr, end; |
| if ((ptr = find(memopnds.begin(), end = memopnds.end(), opnd)) == end) |
| { |
| opnd_mem = irManager->newMemOpnd(opnd->getType(), |
| MemOpndKind_StackAutoLayout, |
| irManager->getRegOpnd(STACK_REG), |
| 0); |
| memopnds.push_back(TwoOpnds(opnd, opnd_mem)); |
| #ifdef _DEBUG_SPILLGEN |
| DBGOUT("split " << *opnd << " -> mem " << *opnd_mem << endl;) |
| //if (dbgraw != 0) |
| // dbgraw->split(opnd, opnd_mem); |
| #endif |
| } |
| else |
| { |
| opnd_mem = ptr->second; |
| } |
| |
| return opnd_mem; |
| } |
| |
| |
| Opnd* SpillGen::opndReg (const Opnd* opnd, RegName rn) const |
| { |
| Opnd* opnd_reg = irManager->newRegOpnd(opnd->getType(), getRegName(getRegKind(rn), opnd->getSize(), getRegIndex(rn))); |
| #ifdef _DEBUG_SPILLGEN |
| DBGOUT("split " << *opnd << " -> reg " << *opnd_reg << endl;) |
| //if (dbgraw != 0) |
| // dbgraw->split(opnd, opnd_reg); |
| #endif |
| return opnd_reg; |
| } |
| |
| |
| void SpillGen::emitPushPop (bool before, Inst* inst, Opnd* opnd, bool push) |
| { |
| if (push) |
| emitMove(before, inst, opndMem(opnd), opnd); |
| else |
| emitMove(before, inst, opnd, opndMem(opnd)); |
| } |
| |
| |
| // Emit 'mov' instruction before/after the instruction specified |
| // |
| Inst* SpillGen::emitMove (bool before, Inst* inst, Opnd* dst, Opnd* src) |
| { |
| if (dst == src) |
| return 0; |
| |
| Inst* mov = irManager->newCopyPseudoInst(Mnemonic_MOV, dst, src); |
| if (before) { |
| mov->insertBefore(inst); |
| } else |
| { |
| // ensure we don't append after any branch instructions |
| // for example, after the last instruction in basic block |
| assert(!inst->hasKind(Inst::Kind_LocalControlTransferInst)); |
| mov->insertAfter(inst); |
| } |
| |
| DBGOUT((before?"before":" after") << " " << *inst << " " |
| << *mov << " MOV " << *dst << " " << *src << endl;) |
| emitted++; |
| |
| return mov; |
| } |
| |
| RegName SpillGen::findFree (RegMask usable, int idx, Instx* instx) |
| { |
| Constraint c = registers[idx]; |
| usable &= c.getMask(); // search only from available registers |
| |
| Instx* begx = instxs.empty()? (Instx*)NULL:&*instxs.begin(); |
| Instx* endx = begx + instxs.size() ; |
| ++begx; |
| Instx* ptrx; |
| size_t xbest = INT_MAX, |
| xbest_free = INT_MAX, |
| xlgth_free = 0, |
| xbest_press = INT_MAX, |
| xlgth_press = 0; |
| |
| size_t x, found; |
| RegMask msk; |
| for (x = 0, found = 0, msk = 1; usable != 0; ++x, msk <<= 1) { |
| if ((usable & msk) != 0) |
| { |
| usable ^= msk, ++found; |
| if (usable == 0 && found == 1) |
| {// this is the only register available - no need to choose the best |
| xbest = x; |
| break; |
| } |
| |
| size_t lgth = 0; |
| bool press = (instx->regpress[idx] & msk) != 0; |
| |
| for (ptrx = instx-1; ptrx >= begx && (ptrx->regusage[idx] & msk) == 0; --ptrx) |
| { |
| ++lgth; |
| press |= (ptrx->regpress[idx] & msk) != 0; |
| } |
| for (ptrx = instx+1; ptrx < endx && (ptrx->regusage[idx] & msk) == 0; ++ptrx) |
| { |
| ++lgth; |
| press |= (ptrx->regpress[idx] & msk) != 0; |
| } |
| if (press) |
| { |
| if (xbest_press == INT_MAX || xlgth_press >= lgth) |
| xbest_press = x, |
| xlgth_press = lgth; |
| } |
| else |
| { |
| if (xbest_free == INT_MAX || xlgth_free >= lgth) |
| xbest_free = x, |
| xlgth_free = lgth; |
| } |
| } |
| } |
| if (xbest == INT_MAX) { |
| xbest = xbest_free != INT_MAX ? xbest_free : xbest_press; |
| } |
| |
| return xbest == INT_MAX ? |
| RegName_Null : |
| getRegName(static_cast<OpndKind>(c.getKind()), c.getSize(), (int)xbest); |
| } |
| |
| |
| RegName SpillGen::findEvict (RegMask usable, int idx, Instx* begx, Instx*& endx) |
| { |
| Constraint c = registers[idx]; |
| Inst* inst = begx->inst; |
| Opnd* opnd; |
| |
| RegMask used = 0; |
| Inst::Opnds opnds(inst, Inst::OpndRole_All); |
| for (Inst::Opnds::iterator it = opnds.begin(); it != opnds.end(); it = opnds.next(it)) |
| used |= getRegMaskConstr(inst->getOpnd(it), c); |
| |
| usable &= ~used; |
| if (usable == 0) |
| return RegName_Null; |
| |
| if (!evicts_known) |
| setupEvicts(); |
| |
| Evicts evicts(mm); |
| |
| for (Opnds::iterator it = begx->evicts->begin(); it != begx->evicts->end(); ++it) |
| if ((opnd = *it) != 0 && (usable & getRegMaskConstr(opnd, c)) != 0) |
| { |
| Evict tmp; |
| tmp.opnd = opnd; |
| tmp.begx = begx; |
| tmp.endx = begx; |
| evicts.push_back(tmp); |
| } |
| |
| if (evicts.empty()) |
| return RegName_Null; |
| |
| Evict* evict = pickEvict(evicts); |
| if (evict == 0) |
| return RegName_Null; |
| |
| if (evict->endx->inst->hasKind(Inst::Kind_LocalControlTransferInst)) { |
| --(evict->endx); |
| if ((evict->endx < evict->begx) || (evict->endx < endx)) |
| return RegName_Null; |
| } |
| |
| if (endx > evict->endx) |
| endx = evict->endx; |
| |
| // now evict the operand found |
| |
| emitPushPop(true, evict->begx->inst, evict->opnd, true); |
| emitPushPop(false, evict->endx->inst, evict->opnd, false); |
| |
| // update the 'instxs' table |
| |
| RegName rn = evict->opnd->getRegName(); |
| RegMask mk = getRegMask(rn); |
| assert((usable & mk)); |
| |
| Instx* ptrx; |
| for (ptrx = evict->begx; ptrx <= evict->endx; ++ptrx) |
| { |
| // mark register assigned to the operand as free |
| if (ptrx != evict->endx) |
| ptrx->regusage[idx] &= ~mk; |
| |
| // clear the operand as a candidate to evict |
| killEvict(evict->opnd, ptrx); |
| } |
| |
| return rn; |
| } |
| |
| |
| void SpillGen::setupEvicts () |
| { |
| Opnd* opnd; |
| Constraint loc; |
| RegMask msk; |
| int idx; |
| |
| // will be used to calculate all registers used in an instruction |
| Registers used(mm); |
| used = registers; |
| |
| Registers* catched = 0; |
| |
| BitSet ls = *lives_exit; |
| ls.resize(irManager->getOpndCount()); |
| BitSet lsnext = ls; |
| |
| Instxs::iterator instxp = instxs.end() - 1; |
| for (Inst* inst = (Inst*)bblock->getLastInst(); inst != 0; inst = inst->getPrevInst()) |
| { |
| used.clearMasks(); // mask of all registers used in the current instruction |
| |
| Inst::Opnds opnds(inst, Inst::OpndRole_All); |
| for (Inst::Opnds::iterator it = opnds.begin(); it != opnds.end(); it = opnds.next(it)) |
| { |
| opnd = inst->getOpnd(it); |
| loc = opnd->getConstraint(Opnd::ConstraintKind_Location, OpndSize_Default); |
| if ((msk = loc.getMask()) != 0 && (idx = registers.getIndex(loc)) != -1) |
| {// this operand is already assigned to some location/register |
| if (inst->isLiveRangeEnd(it)) |
| lsnext.setBit(opnd->getId(), false); |
| else if (inst->isLiveRangeStart(it)) |
| lsnext.setBit(opnd->getId(), true); |
| |
| merge(used[idx], msk); |
| } |
| } |
| if (inst->hasKind(Inst::Kind_CallInst) && lives_catch != 0) |
| { |
| if (catched == 0) |
| {// construct the catched operand list - once per block |
| catched = new (mm) Registers(mm); |
| *catched = registers; |
| catched->clearMasks(); |
| |
| BitSet::IterB lives(*lives_catch); |
| for (int i = lives.getNext(); i != -1; i = lives.getNext()) |
| { |
| opnd = irManager->getOpnd(i); |
| loc = opnd->getConstraint(Opnd::ConstraintKind_Location, OpndSize_Default); |
| if ((msk = loc.getMask()) != 0 && (idx = registers.getIndex(loc)) != -1) |
| merge((*catched)[idx], msk); |
| } |
| } |
| used.merge(*catched); |
| } |
| if (inst == instxp->inst) |
| { |
| if (instxp->evicts == 0) |
| instxp->evicts = new (mm) Opnds(mm); |
| else |
| instxp->evicts->resize(0); |
| |
| BitSet::IterB lives(ls); |
| for (int i = lives.getNext(); i != -1; i = lives.getNext()) |
| { |
| opnd = irManager->getOpnd(i); |
| loc = opnd->getConstraint(Opnd::ConstraintKind_Location, OpndSize_Default); |
| if (loc.getMask() != 0 && registers.contains(loc) && !used.contains(loc)) |
| instxp->evicts->push_back(opnd); |
| } |
| |
| --instxp; |
| } |
| |
| ls = lsnext; |
| } |
| |
| evicts_known = true; |
| } |
| |
| |
| SpillGen::Evict* SpillGen::pickEvict (Evicts& evicts) |
| { |
| Instx* begx = instxs.empty()? (Instx*)NULL:&*instxs.begin(); |
| Instx* endx = begx + instxs.size(); |
| ++begx; |
| Instx* ptrx; |
| |
| DBGOUT("Evicts" << endl;) |
| for (Evicts::iterator it = evicts.begin(); it != evicts.end(); ++it) |
| { |
| Evict& evict = *it; |
| |
| for (ptrx = evict.begx-1; ptrx >= begx && isEvict(evict.opnd, ptrx); --ptrx) |
| evict.begx = ptrx; |
| |
| for (ptrx = evict.endx+1; ptrx < endx && isEvict(evict.opnd, ptrx); ++ptrx) |
| evict.endx = ptrx; |
| |
| evict.weight = int(evict.endx - evict.begx); |
| |
| DBGOUT(" evict " << *evict.opnd << " [" << *evict.begx->inst |
| << " - " << *evict.endx->inst << "] w:" << evict.weight << endl;) |
| } |
| assert(!evicts.empty()); |
| return &*max_element(evicts.begin(), evicts.end()); |
| } |
| |
| |
| bool SpillGen::isEvict (const Opnd* opnd, const Instx* ptrx) const |
| { |
| Opnds::iterator endx = ptrx->evicts->end(); |
| return find(ptrx->evicts->begin(), endx, opnd) != endx; |
| } |
| |
| |
| void SpillGen:: killEvict (const Opnd* opnd, Instx* instx) const |
| { |
| Opnds::iterator end = instx->evicts->end(); |
| Opnds::iterator it = find(instx->evicts->begin(), end, opnd); |
| if (it != end) |
| *it = 0; |
| } |
| |
| |
| SpillGen::RegMask SpillGen::getRegMaskConstr (const Opnd* opnd, Constraint c) const |
| { |
| return opnd->isPlacedIn(c.getAliasConstraint(OpndSize_Default)) ? |
| getRegMask(opnd->getRegName()) : 0; |
| } |
| |
| |
| #ifdef _DEBUG_SPILLGEN |
| #include "Ia32SpillGenDbgTail.h" |
| #endif |
| |
| |
| } //namespace Ia32 |
| |
| } //namespace Jitrino |
| |
| |
| |
| |
| |
