nv50_ir_ra.cpp revision 57594065c30feec9376be9b2132659f7d87362ee
157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include "nv50_ir.h" 357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include "nv50_ir_target.h" 457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include "nv50/nv50_debug.h" 657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillernamespace nv50_ir { 857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define MAX_REGISTER_FILE_SIZE 256 1057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass RegisterSet 1257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 1357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 1457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegisterSet(); 1557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegisterSet(const Target *); 1657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void init(const Target *); 1857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void reset(); // reset allocation status, but not max assigned regs 1957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void periodicMask(DataFile f, uint32_t lock, uint32_t unlock); 2157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void intersect(DataFile f, const RegisterSet *); 2257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool assign(Value **, int nr); 2457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void release(const Value *); 2557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void occupy(const Value *); 2657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int getMaxAssigned(DataFile f) const { return fill[f]; } 2857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void print() const; 3057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 3257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t bits[FILE_ADDRESS + 1][(MAX_REGISTER_FILE_SIZE + 31) / 32]; 3357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int unit[FILE_ADDRESS + 1]; // log2 of allocation granularity 3557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int last[FILE_ADDRESS + 1]; 3757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int fill[FILE_ADDRESS + 1]; 3857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 3957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 4157594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::reset() 4257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 4357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller memset(bits, 0, sizeof(bits)); 4457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 4557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4657594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::RegisterSet() 4757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 4857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller reset(); 4957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 5057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 5157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 5257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::init(const Target *targ) 5357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 5457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int rf = 0; rf <= FILE_ADDRESS; ++rf) { 5557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DataFile f = static_cast<DataFile>(rf); 5657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller last[rf] = targ->getFileSize(f) - 1; 5757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unit[rf] = targ->getFileUnit(f); 5857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fill[rf] = -1; 5957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(last[rf] < MAX_REGISTER_FILE_SIZE); 6057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 6157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 6257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 6357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::RegisterSet(const Target *targ) 6457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 6557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller reset(); 6657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller init(targ); 6757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 6857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 6957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 7057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::periodicMask(DataFile f, uint32_t lock, uint32_t unlock) 7157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 7257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int i = 0; i < (last[f] + 31) / 32; ++i) 7357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bits[f][i] = (bits[f][i] | lock) & ~unlock; 7457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 7557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 7657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 7757594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::intersect(DataFile f, const RegisterSet *set) 7857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 7957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int i = 0; i < (last[f] + 31) / 32; ++i) 8057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bits[f][i] |= set->bits[f][i]; 8157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 8257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 8457594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::print() const 8557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 8657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("GPR:"); 8757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int i = 0; i < (last[FILE_GPR] + 31) / 32; ++i) 8857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO(" %08x", bits[FILE_GPR][i]); 8957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("\n"); 9057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 9157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 9257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 9357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::assign(Value **def, int nr) 9457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 9557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DataFile f = def[0]->reg.file; 9657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int n = nr; 9757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (n == 3) 9857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller n = 4; 9957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int s = (n * def[0]->reg.size) >> unit[f]; 10057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t m = (1 << s) - 1; 10157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 10257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int id = last[f] + 1; 10357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int i; 10457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 10557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (i = 0; (i * 32) < last[f]; ++i) { 10657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bits[f][i] == 0xffffffff) 10757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 10857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 10957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (id = 0; id < 32; id += s) 11057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(bits[f][i] & (m << id))) 11157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 11257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (id < 32) 11357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 11457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 11557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller id += i * 32; 11657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (id > last[f]) 11757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 11857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 11957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bits[f][id / 32] |= m << (id % 32); 12057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 12157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (id + (s - 1) > fill[f]) 12257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fill[f] = id + (s - 1); 12357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 12457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (i = 0; i < nr; ++i, ++id) 12557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!def[i]->livei.isEmpty()) // XXX: really increased id if empty ? 12657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller def[i]->reg.data.id = id; 12757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 12857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 12957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 13057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 13157594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::occupy(const Value *val) 13257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 13357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int id = val->reg.data.id; 13457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (id < 0) 13557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return; 13657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int f = val->reg.file; 13757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 13857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t m = (1 << (val->reg.size >> unit[f])) - 1; 13957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(0, REG_ALLOC, "reg occupy: %u[%i] %x\n", f, id, m); 14157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bits[f][id / 32] |= m << (id % 32); 14357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (fill[f] < id) 14557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fill[f] = id; 14657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 14757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 14957594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::release(const Value *val) 15057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 15157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int id = val->reg.data.id; 15257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (id < 0) 15357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return; 15457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int f = val->reg.file; 15557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t m = (1 << (val->reg.size >> unit[f])) - 1; 15757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(0, REG_ALLOC, "reg release: %u[%i] %x\n", f, id, m); 15957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bits[f][id / 32] &= ~(m << (id % 32)); 16157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 16257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define JOIN_MASK_PHI (1 << 0) 16457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define JOIN_MASK_UNION (1 << 1) 16557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define JOIN_MASK_MOV (1 << 2) 16657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define JOIN_MASK_TEX (1 << 3) 16757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define JOIN_MASK_CONSTRAINT (1 << 4) 16857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass RegAlloc 17057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 17157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 17257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegAlloc(Program *program) : prog(program), sequence(0) { } 17357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool exec(); 17557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool execFunc(); 17657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 17857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool coalesceValues(unsigned int mask); 17957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool linearScan(); 18057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool allocateConstrainedValues(); 18157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 18357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class PhiMovesPass : public Pass { 18457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 18557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool visit(BasicBlock *); 18657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool needNewElseBlock(BasicBlock *b, BasicBlock *p); 18757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 18857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class BuildIntervalsPass : public Pass { 19057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 19157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool visit(BasicBlock *); 19257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void collectLiveValues(BasicBlock *); 19357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void addLiveRange(Value *, const BasicBlock *, int end); 19457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 19557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class InsertConstraintsPass : public Pass { 19757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 19857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool exec(Function *func); 19957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 20057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool visit(BasicBlock *); 20157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool insertConstraintMoves(); 20357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void addHazard(Instruction *i, const ValueRef *src); 20557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void textureMask(TexInstruction *); 20657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void addConstraint(Instruction *, int s, int n); 20757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool detectConflict(Instruction *, int s); 20857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLList constrList; 21057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 21157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool buildLiveSets(BasicBlock *); 21357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void collectLValues(DLList&, bool assignedOnly); 21457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void insertOrderedTail(DLList&, Value *); 21657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline Instruction *insnBySerial(int); 21757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 21957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Program *prog; 22057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Function *func; 22157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // instructions in control flow / chronological order 22357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ArrayList insns; 22457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int sequence; // for manual passes through CFG 22657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 22757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerInstruction * 22957594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::insnBySerial(int serial) 23057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 23157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return reinterpret_cast<Instruction *>(insns.get(serial)); 23257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 23357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 23457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 23557594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::BuildIntervalsPass::addLiveRange(Value *val, 23657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const BasicBlock *bb, 23757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int end) 23857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 23957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *insn = val->getUniqueInsn(); 24057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!insn) 24257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return; 24357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(bb->getFirst()->serial <= bb->getExit()->serial); 24457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(bb->getExit()->serial + 1 >= end); 24557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int begin = insn->serial; 24757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (begin < bb->getEntry()->serial || begin > bb->getExit()->serial) 24857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller begin = bb->getEntry()->serial; 24957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "%%%i <- live range [%i(%i), %i)\n", 25157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller val->id, begin, insn->serial, end); 25257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (begin != end) // empty ranges are only added as hazards for fixed regs 25457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller val->livei.extend(begin, end); 25557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 25657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 25857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::PhiMovesPass::needNewElseBlock(BasicBlock *b, BasicBlock *p) 25957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 26057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (b->cfg.incidentCount() <= 1) 26157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 26257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 26357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int n = 0; 26457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = p->cfg.outgoing(); !ei.end(); ei.next()) 26557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.getType() == Graph::Edge::TREE || 26657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ei.getType() == Graph::Edge::FORWARD) 26757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++n; 26857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return (n == 2); 26957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 27057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// For each operand of each PHI in b, generate a new value by inserting a MOV 27257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// at the end of the block it is coming from and replace the operand with its 27357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// result. This eliminates liveness conflicts and enables us to let values be 27457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// copied to the right register if such a conflict exists nonetheless. 27557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// 27657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// These MOVs are also crucial in making sure the live intervals of phi srces 27757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// are extended until the end of the loop, since they are not included in the 27857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// live-in sets. 27957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 28057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::PhiMovesPass::visit(BasicBlock *bb) 28157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 28257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *phi, *mov; 28357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *pb, *pn; 28457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) { 28657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb = pn = BasicBlock::get(ei.getNode()); 28757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(pb); 28857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (needNewElseBlock(bb, pb)) { 29057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pn = new BasicBlock(func); 29157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // deletes an edge, iterator is invalid after this: 29357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb->cfg.detach(&bb->cfg); 29457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb->cfg.attach(&pn->cfg, Graph::Edge::TREE); 29557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pn->cfg.attach(&bb->cfg, Graph::Edge::FORWARD); // XXX: check order ! 29657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(pb->getExit()->op != OP_CALL); 29857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (pb->getExit()->asFlow()->target.bb == bb) 29957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb->getExit()->asFlow()->target.bb = pn; 30057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 30157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 30257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 30357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 30457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // insert MOVs (phi->src[j] should stem from j-th in-BB) 30557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int j = 0; 30657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) { 30757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb = BasicBlock::get(ei.getNode()); 30857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!pb->isTerminated()) 30957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb->insertTail(new_FlowInstruction(func, OP_BRA, bb)); 31057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (phi = bb->getPhi(); phi && phi->op == OP_PHI; phi = phi->next) { 31257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mov = new_Instruction(func, OP_MOV, TYPE_U32); 31357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mov->setSrc(0, phi->getSrc(j)); 31557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mov->setDef(0, new_LValue(func, phi->getDef(0)->asLValue())); 31657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller phi->setSrc(j, mov->getDef(0)); 31757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb->insertBefore(pb->getExit(), mov); 31957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 32057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++j; 32157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 32257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 32357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 32457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 32557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 32657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Build the set of live-in variables of bb. 32757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 32857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::buildLiveSets(BasicBlock *bb) 32957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 33057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *bn; 33157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *i; 33257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int s, d; 33357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "buildLiveSets(BB:%i)\n", bb->getId()); 33557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.allocate(func->allLValues.getSize(), false); 33757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int n = 0; 33957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 34057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bn = BasicBlock::get(ei.getNode()); 34157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bn == bb) 34257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 34357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bn->cfg.visit(sequence)) 34457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!buildLiveSets(bn)) 34557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 34657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (n++ == 0) 34757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet = bn->liveSet; 34857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller else 34957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet |= bn->liveSet; 35057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 35157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!n && !bb->liveSet.marker) 35257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.fill(0); 35357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.marker = true; 35457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) { 35657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("BB:%i live set of out blocks:\n", bb->getId()); 35757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.print(); 35857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 35957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // if (!bb->getEntry()) 36157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // return true; 36257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (i = bb->getExit(); i && i != bb->getEntry()->prev; i = i->prev) { 36457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0; i->defExists(d); ++d) 36557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getDef(d)->id); 36657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (s = 0; i->srcExists(s); ++s) 36757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->getSrc(s)->asLValue()) 36857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.set(i->getSrc(s)->id); 36957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 37057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (i = bb->getPhi(); i && i->op == OP_PHI; i = i->next) 37157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getDef(0)->id); 37257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) { 37457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("BB:%i live set after propagation:\n", bb->getId()); 37557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.print(); 37657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 37757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 37957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 38057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 38257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::BuildIntervalsPass::collectLiveValues(BasicBlock *bb) 38357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 38457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *bbA = NULL, *bbB = NULL; 38557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(bb->cfg.incidentCount() || bb->liveSet.popCount() == 0); 38757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb->cfg.outgoingCount()) { 38957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // trickery to save a loop of OR'ing liveSets 39057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // aliasing works fine with BitSet::setOr 39157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 39257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.getType() == Graph::Edge::DUMMY) 39357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 39457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bbA) { 39557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.setOr(&bbA->liveSet, &bbB->liveSet); 39657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbA = bb; 39757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 39857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbA = bbB; 39957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 40057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbB = BasicBlock::get(ei.getNode()); 40157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 40257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.setOr(&bbB->liveSet, bbA ? &bbA->liveSet : NULL); 40357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 40457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb->cfg.incidentCount()) { 40557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.fill(0); 40657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 40757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 40857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 40957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 41057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::BuildIntervalsPass::visit(BasicBlock *bb) 41157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 41257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller collectLiveValues(bb); 41357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 41457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "BuildIntervals(BB:%i)\n", bb->getId()); 41557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 41657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // go through out blocks and delete phi sources that do not originate from 41757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // the current block from the live set 41857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 41957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *out = BasicBlock::get(ei.getNode()); 42057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 42157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Instruction *i = out->getPhi(); i && i->op == OP_PHI; i = i->next) { 42257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getDef(0)->id); 42357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 42457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int s = 0; s < NV50_IR_MAX_SRCS && i->src[s].exists(); ++s) { 42557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i->src[s].getInsn()); 42657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->getSrc(s)->getUniqueInsn()->bb == bb) // XXX: reachableBy ? 42757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.set(i->getSrc(s)->id); 42857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller else 42957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getSrc(s)->id); 43057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 43157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 43257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 43357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 43457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // remaining live-outs are live until end 43557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb->getExit()) { 43657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int j = 0; j < bb->liveSet.getSize(); ++j) 43757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb->liveSet.test(j)) 43857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller addLiveRange(func->getLValue(j), bb, bb->getExit()->serial + 1); 43957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 44057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 44157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Instruction *i = bb->getExit(); i && i->op != OP_PHI; i = i->prev) { 44257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int d = 0; i->defExists(d); ++d) { 44357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getDef(d)->id); 44457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->getDef(d)->reg.data.id >= 0) // add hazard for fixed regs 44557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->getDef(d)->livei.extend(i->serial, i->serial); 44657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 44757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 44857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int s = 0; i->srcExists(s); ++s) { 44957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!i->getSrc(s)->asLValue()) 45057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 45157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!bb->liveSet.test(i->getSrc(s)->id)) { 45257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.set(i->getSrc(s)->id); 45357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller addLiveRange(i->getSrc(s), bb, i->serial); 45457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 45557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 45657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 45757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 45857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 45957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 46057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 46157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 46257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::coalesceValues(unsigned int mask) 46357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 46457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int c, n; 46557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 46657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (n = 0; n < insns.getSize(); ++n) { 46757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *i; 46857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *insn = insnBySerial(n); 46957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 47057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller switch (insn->op) { 47157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_PHI: 47257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_PHI)) 47357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 47457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; insn->srcExists(c); ++c) 47557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!insn->getDef(0)->coalesce(insn->getSrc(c), false)) { 47657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ERROR("failed to coalesce phi operands\n"); 47757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 47857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 47957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 48057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_UNION: 48157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_UNION)) 48257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 48357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; insn->srcExists(c); ++c) 48457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->getDef(0)->coalesce(insn->getSrc(c), true); 48557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 48657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_CONSTRAINT: 48757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_CONSTRAINT)) 48857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 48957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; c < 4 && insn->srcExists(c); ++c) 49057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->getDef(c)->coalesce(insn->getSrc(c), true); 49157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 49257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_MOV: 49357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_MOV)) 49457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 49557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i = insn->getSrc(0)->getUniqueInsn(); 49657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i && !i->constrainedDefs()) 49757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->getDef(0)->coalesce(insn->getSrc(0), false); 49857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 49957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TEX: 50057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXB: 50157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXL: 50257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXF: 50357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXQ: 50457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXD: 50557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXG: 50657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TEXCSAA: 50757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_TEX)) 50857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 50957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; c < 4 && insn->srcExists(c); ++c) 51057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insn->getDef(c)->coalesce(insn->getSrc(c), true); 51157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 51257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller default: 51357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 51457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 51557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 51657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 51757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 51857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 51957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 52057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::insertOrderedTail(DLList &list, Value *val) 52157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 52257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // we insert the live intervals in order, so this should be short 52357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLList::Iterator iter = list.revIterator(); 52457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const int begin = val->livei.begin(); 52557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (; !iter.end(); iter.next()) { 52657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (reinterpret_cast<Value *>(iter.get())->livei.begin() <= begin) 52757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 52857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 52957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller iter.insert(val); 53057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 53157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 53257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerstatic void 53357594065c30feec9376be9b2132659f7d87362eeChristoph BumillercheckList(DLList &list) 53457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 53557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Value *prev = NULL; 53657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Value *next = NULL; 53757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 53857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator iter = list.iterator(); !iter.end(); iter.next()) { 53957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = Value::get(iter); 54057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(next); 54157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (prev) { 54257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(prev->livei.begin() <= next->livei.begin()); 54357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 54457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(next->join == next); 54557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prev = next; 54657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 54757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 54857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 55057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::collectLValues(DLList &list, bool assignedOnly) 55157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 55257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int n = 0; n < insns.getSize(); ++n) { 55357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *i = insnBySerial(n); 55457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 55557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int d = 0; i->defExists(d); ++d) 55657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!i->getDef(d)->livei.isEmpty()) 55757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!assignedOnly || i->getDef(d)->reg.data.id >= 0) 55857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insertOrderedTail(list, i->getDef(d)); 55957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 56057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller checkList(list); 56157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 56257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 56357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 56457594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::allocateConstrainedValues() 56557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 56657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Value *defs[4]; 56757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegisterSet regSet[4]; 56857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLList regVals; 56957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 57057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "RA: allocating constrained values\n"); 57157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 57257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller collectLValues(regVals, true); 57357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 57457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int c = 0; c < 4; ++c) 57557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller regSet[c].init(prog->getTarget()); 57657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 57757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int n = 0; n < insns.getSize(); ++n) { 57857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *i = insnBySerial(n); 57957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 58057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const int vecSize = i->defCount(0xf); 58157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (vecSize < 2) 58257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 58357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(vecSize <= 4); 58457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 58557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int c = 0; c < vecSize; ++c) 58657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller defs[c] = i->def[c].rep(); 58757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 58857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (defs[0]->reg.data.id >= 0) { 58957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int c = 1; c < vecSize; ++c) { 59057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(defs[c]->reg.data.id >= 0); 59157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 59257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 59357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 59457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 59557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int c = 0; c < vecSize; ++c) { 59657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t mask; 59757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller regSet[c].reset(); 59857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 59957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator it = regVals.iterator(); !it.end(); it.next()) { 60057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Value *rVal = Value::get(it); 60157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (rVal->reg.data.id >= 0 && rVal->livei.overlaps(defs[c]->livei)) 60257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller regSet[c].occupy(rVal); 60357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 60457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mask = 0x11111111; 60557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (vecSize == 2) // granularity is 2 instead of 4 60657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mask |= 0x11111111 << 2; 60757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller regSet[c].periodicMask(defs[0]->reg.file, 0, ~(mask << c)); 60857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 60957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!defs[c]->livei.isEmpty()) 61057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller insertOrderedTail(regVals, defs[c]); 61157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 61257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int c = 1; c < vecSize; ++c) 61357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller regSet[0].intersect(defs[0]->reg.file, ®Set[c]); 61457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 61557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!regSet[0].assign(&defs[0], vecSize)) // TODO: spilling 61657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 61757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 61857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int c = 0; c < 4; c += 2) 61957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (regSet[c].getMaxAssigned(FILE_GPR) > prog->maxGPR) 62057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prog->maxGPR = regSet[c].getMaxAssigned(FILE_GPR); 62157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 62257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 62357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 62457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 62557594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::linearScan() 62657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 62757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Value *cur, *val; 62857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLList unhandled, active, inactive; 62957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegisterSet f(prog->getTarget()), free(prog->getTarget()); 63057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 63157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "RA: linear scan\n"); 63257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 63357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller collectLValues(unhandled, false); 63457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 63557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator cI = unhandled.iterator(); !cI.end();) { 63657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cur = Value::get(cI); 63757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cI.erase(); 63857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 63957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator aI = active.iterator(); !aI.end();) { 64057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller val = Value::get(aI); 64157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (val->livei.end() <= cur->livei.begin()) { 64257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller free.release(val); 64357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller aI.erase(); 64457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 64557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!val->livei.contains(cur->livei.begin())) { 64657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller free.release(val); 64757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller aI.moveToList(inactive); 64857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 64957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller aI.next(); 65057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 65157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 65257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 65357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator iI = inactive.iterator(); !iI.end();) { 65457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller val = Value::get(iI); 65557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (val->livei.end() <= cur->livei.begin()) { 65657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller iI.erase(); 65757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 65857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (val->livei.contains(cur->livei.begin())) { 65957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller free.occupy(val); 66057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller iI.moveToList(active); 66157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 66257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller iI.next(); 66357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 66457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 66557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller f = free; 66657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 66757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator iI = inactive.iterator(); !iI.end(); iI.next()) { 66857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller val = Value::get(iI); 66957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (val->livei.overlaps(cur->livei)) 67057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller f.occupy(val); 67157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 67257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 67357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator uI = unhandled.iterator(); !uI.end(); uI.next()) { 67457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller val = Value::get(uI); 67557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (val->reg.data.id >= 0 && val->livei.overlaps(cur->livei)) 67657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller f.occupy(val); 67757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 67857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 67957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (cur->reg.data.id < 0) { 68057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool spill = !f.assign(&cur, 1); 68157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (spill) { 68257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ERROR("out of registers of file %u\n", cur->reg.file); 68357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller abort(); 68457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 68557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 68657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller free.occupy(cur); 68757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller active.insert(cur); 68857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 68957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 69057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (f.getMaxAssigned(FILE_GPR) > prog->maxGPR) 69157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prog->maxGPR = f.getMaxAssigned(FILE_GPR); 69257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (free.getMaxAssigned(FILE_GPR) > prog->maxGPR) 69357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller prog->maxGPR = free.getMaxAssigned(FILE_GPR); 69457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 69557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 69657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 69757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 69857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::exec() 69957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 70057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (ArrayList::Iterator fi = prog->allFuncs.iterator(); 70157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller !fi.end(); fi.next()) { 70257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller func = reinterpret_cast<Function *>(fi.get()); 70357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!execFunc()) 70457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 70557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 70657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 70757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 70857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 70957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 71057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::execFunc() 71157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 71257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller InsertConstraintsPass insertConstr; 71357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller PhiMovesPass insertMoves; 71457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BuildIntervalsPass buildIntervals; 71557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 71657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int i; 71757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool ret; 71857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 71957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = insertConstr.exec(func); 72057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 72157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 72257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 72357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = insertMoves.run(func); 72457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 72557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 72657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 72757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (sequence = func->cfg.nextSequence(), i = 0; 72857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret && i <= func->loopNestingBound; 72957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller sequence = func->cfg.nextSequence(), ++i) 73057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = buildLiveSets(BasicBlock::get(func->cfg.getRoot())); 73157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 73257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 73357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 73457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller func->orderInstructions(this->insns); 73557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 73657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = buildIntervals.run(func); 73757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 73857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 73957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 74057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = coalesceValues(JOIN_MASK_PHI); 74157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 74257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 74357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller switch (prog->getTarget()->getChipset() & 0xf0) { 74457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case 0x50: 74557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = coalesceValues(JOIN_MASK_UNION | JOIN_MASK_TEX); 74657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 74757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case 0xc0: 74857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = coalesceValues(JOIN_MASK_UNION | JOIN_MASK_CONSTRAINT); 74957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 75057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller default: 75157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 75257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 75357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 75457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 75557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = coalesceValues(JOIN_MASK_MOV); 75657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 75757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 75857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 75957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) { 76057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller func->print(); 76157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller func->printLiveIntervals(); 76257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 76357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 76457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = allocateConstrainedValues() && linearScan(); 76557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 76657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 76757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 76857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerout: 76957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // TODO: should probably call destructor on LValues later instead 77057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (ArrayList::Iterator it = func->allLValues.iterator(); 77157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller !it.end(); it.next()) 77257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller reinterpret_cast<LValue *>(it.get())->livei.clear(); 77357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 77457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ret; 77557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 77657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 77757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool Program::registerAllocation() 77857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 77957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegAlloc ra(this); 78057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ra.exec(); 78157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 78257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 78357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 78457594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::exec(Function *ir) 78557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 78657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller constrList.clear(); 78757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 78857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool ret = run(ir, true, true); 78957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ret) 79057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = insertConstraintMoves(); 79157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ret; 79257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 79357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 79457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// TODO: make part of texture insn 79557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 79657594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::textureMask(TexInstruction *tex) 79757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 79857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Value *def[4]; 79957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int c, k, d; 80057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint8_t mask = 0; 80157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 80257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0, k = 0, c = 0; c < 4; ++c) { 80357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(tex->tex.mask & (1 << c))) 80457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 80557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (tex->getDef(k)->refCount()) { 80657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mask |= 1 << c; 80757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller def[d++] = tex->getDef(k); 80857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 80957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++k; 81057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 81157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller tex->tex.mask = mask; 81257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 81357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#if 0 // reorder or set the unused ones NULL ? 81457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; c < 4; ++c) 81557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(tex->tex.mask & (1 << c))) 81657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller def[d++] = tex->getDef(c); 81757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#endif 81857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; c < d; ++c) 81957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller tex->setDef(c, def[c]); 82057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#if 1 82157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (; c < 4; ++c) 82257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller tex->setDef(c, NULL); 82357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#endif 82457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 82557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 82657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 82757594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::detectConflict(Instruction *cst, int s) 82857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 82957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // current register allocation can't handle it if a value participates in 83057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // multiple constraints 83157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (ValueRef::Iterator it = cst->src[s].iterator(); !it.end(); it.next()) { 83257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *insn = it.get()->getInsn(); 83357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (insn != cst) 83457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 83557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 83657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 83757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // can start at s + 1 because detectConflict is called on all sources 83857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int c = s + 1; cst->srcExists(c); ++c) 83957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (cst->getSrc(c) == cst->getSrc(s)) 84057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 84157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 84257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *defi = cst->getSrc(s)->getInsn(); 84357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 84457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return (!defi || defi->constrainedDefs()); 84557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 84657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 84757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 84857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::addConstraint(Instruction *i, int s, int n) 84957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 85057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *cst; 85157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int d; 85257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 85357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // first, look for an existing identical constraint op 85457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator it = constrList.iterator(); !it.end(); it.next()) { 85557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst = reinterpret_cast<Instruction *>(it.get()); 85657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!i->bb->dominatedBy(cst->bb)) 85757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 85857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0; d < n; ++d) 85957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (cst->getSrc(d) != i->getSrc(d + s)) 86057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 86157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (d >= n) { 86257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0; d < n; ++d, ++s) 86357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->setSrc(s, cst->getDef(d)); 86457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return; 86557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 86657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 86757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst = new_Instruction(func, OP_CONSTRAINT, i->dType); 86857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 86957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0; d < n; ++s, ++d) { 87057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst->setDef(d, new_LValue(func, FILE_GPR)); 87157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst->setSrc(d, i->getSrc(s)); 87257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->setSrc(s, cst->getDef(d)); 87357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 87457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->bb->insertBefore(i, cst); 87557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 87657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller constrList.insert(cst); 87757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 87857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 87957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Add a dummy use of the pointer source of >= 8 byte loads after the load 88057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// to prevent it from being assigned a register which overlapping the load's 88157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// destination, which would produce random corruptions. 88257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 88357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::addHazard(Instruction *i, const ValueRef *src) 88457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 88557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *hzd = new_Instruction(func, OP_NOP, TYPE_NONE); 88657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller hzd->setSrc(0, src->get()); 88757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->bb->insertAfter(i, hzd); 88857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 88957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 89057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 89157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Insert constraint markers for instructions whose multiple sources must be 89257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// located in consecutive registers. 89357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 89457594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::visit(BasicBlock *bb) 89557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 89657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller TexInstruction *tex; 89757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *next; 89857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int s, n, size; 89957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 90057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Instruction *i = bb->getEntry(); i; i = next) { 90157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = i->next; 90257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 90357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if ((tex = i->asTex())) { 90457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller textureMask(tex); 90557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 90657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // FIXME: this is target specific 90757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (tex->op == OP_TXQ) { 90857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller s = tex->srcCount(0xff); 90957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller n = 0; 91057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 91157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller s = tex->tex.target.getArgCount(); 91257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!tex->tex.target.isArray() && 91357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (tex->tex.rIndirectSrc >= 0 || tex->tex.sIndirectSrc >= 0)) 91457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++s; 91557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller n = tex->srcCount(0xff) - s; 91657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(n <= 4); 91757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 91857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 91957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (s > 1) 92057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller addConstraint(i, 0, s); 92157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (n > 1) 92257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller addConstraint(i, s, n); 92357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 92457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->op == OP_EXPORT || i->op == OP_STORE) { 92557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (size = typeSizeof(i->dType), s = 1; size > 0; ++s) { 92657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i->srcExists(s)); 92757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size -= i->getSrc(s)->reg.size; 92857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 92957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if ((s - 1) > 1) 93057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller addConstraint(i, 1, s - 1); 93157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 93257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->op == OP_LOAD) { 93357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->src[0].isIndirect(0) && typeSizeof(i->dType) >= 8) 93457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller addHazard(i, i->src[0].getIndirect(0)); 93557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 93657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 93757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 93857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 93957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 94057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Insert extra moves so that, if multiple register constraints on a value are 94157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// in conflict, these conflicts can be resolved. 94257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 94357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::insertConstraintMoves() 94457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 94557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator it = constrList.iterator(); !it.end(); it.next()) { 94657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *cst = reinterpret_cast<Instruction *>(it.get()); 94757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 94857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int s = 0; cst->srcExists(s); ++s) { 94957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!detectConflict(cst, s)) 95057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 95157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *mov = new_Instruction(func, OP_MOV, 95257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller typeOfSize(cst->src[s].getSize())); 95357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mov->setSrc(0, cst->getSrc(s)); 95457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mov->setDef(0, new_LValue(func, FILE_GPR)); 95557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst->setSrc(s, mov->getDef(0)); 95657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 95757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst->bb->insertBefore(cst, mov); 95857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 95957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 96057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 96157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 96257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 96357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} // namespace nv50_ir 964