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