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 26e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#include <stack> 27e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#include <limits> 2857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillernamespace nv50_ir { 3057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define MAX_REGISTER_FILE_SIZE 256 3257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass RegisterSet 3457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 3557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 3657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegisterSet(const Target *); 3757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void init(const Target *); 39e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void reset(DataFile, bool resetMax = false); 4057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void periodicMask(DataFile f, uint32_t lock, uint32_t unlock); 4257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void intersect(DataFile f, const RegisterSet *); 4357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 44e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool assign(int32_t& reg, DataFile f, unsigned int size); 45e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void release(DataFile f, int32_t reg, unsigned int size); 46e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool occupy(DataFile f, int32_t reg, unsigned int size); 47ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez bool occupy(const Value *); 48e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void occupyMask(DataFile f, int32_t reg, uint8_t mask); 4957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 50e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline int getMaxAssigned(DataFile f) const { return fill[f]; } 51e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 52e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline unsigned int getFileSize(DataFile f, uint8_t regSize) const 53e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 54e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (restrictedGPR16Range && f == FILE_GPR && regSize == 2) 55e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return (last[f] + 1) / 2; 56e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return last[f] + 1; 57e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 58e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 59e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline unsigned int units(DataFile f, unsigned int size) const 60e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 61e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return size >> unit[f]; 62e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 63e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // for regs of size >= 4, id is counted in 4-byte words (like nv50/c0 binary) 64e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline unsigned int idToBytes(Value *v) const 65e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 66e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return v->reg.data.id * MIN2(v->reg.size, 4); 67e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 68e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline unsigned int idToUnits(Value *v) const 69e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 70e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return units(v->reg.file, idToBytes(v)); 71e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 72e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline int bytesToId(Value *v, unsigned int bytes) const 73e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 74e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (v->reg.size < 4) 75e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return units(v->reg.file, bytes); 76e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return bytes / 4; 77e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 78e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline int unitsToId(DataFile f, int u, uint8_t size) const 79e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 80e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (u < 0) 81e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return -1; 82e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return (size < 4) ? u : ((u << unit[f]) / 4); 83e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 8457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void print() const; 8657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 88e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller BitSet bits[LAST_REGISTER_FILE + 1]; 89e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 90e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int unit[LAST_REGISTER_FILE + 1]; // log2 of allocation granularity 9157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 92e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int last[LAST_REGISTER_FILE + 1]; 93e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int fill[LAST_REGISTER_FILE + 1]; 9457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 95e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const bool restrictedGPR16Range; 9657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 9757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 9857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 99e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegisterSet::reset(DataFile f, bool resetMax) 10057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 101e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bits[f].fill(0); 102e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (resetMax) 103e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller fill[f] = -1; 10457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 10557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 10657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 10757594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::init(const Target *targ) 10857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 10957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int rf = 0; rf <= FILE_ADDRESS; ++rf) { 11057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DataFile f = static_cast<DataFile>(rf); 11157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller last[rf] = targ->getFileSize(f) - 1; 11257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unit[rf] = targ->getFileUnit(f); 11357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller fill[rf] = -1; 11457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(last[rf] < MAX_REGISTER_FILE_SIZE); 115e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bits[rf].allocate(last[rf] + 1, true); 11657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 11757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 11857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 11957594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::RegisterSet(const Target *targ) 120e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller : restrictedGPR16Range(targ->getChipset() < 0xc0) 12157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 12257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller init(targ); 123e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (unsigned int i = 0; i <= LAST_REGISTER_FILE; ++i) 124e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller reset(static_cast<DataFile>(i)); 12557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 12657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 12757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 12857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::periodicMask(DataFile f, uint32_t lock, uint32_t unlock) 12957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 130e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bits[f].periodicMask32(lock, unlock); 13157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 13257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 13357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 13457594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::intersect(DataFile f, const RegisterSet *set) 13557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 136e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bits[f] |= set->bits[f]; 13757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 13857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 13957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 14057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegisterSet::print() const 14157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 14257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("GPR:"); 143e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bits[FILE_GPR].print(); 14457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("\n"); 14557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 14657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 148e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegisterSet::assign(int32_t& reg, DataFile f, unsigned int size) 14957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 150e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller reg = bits[f].findFreeRange(size); 151e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (reg < 0) 15257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 153e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller fill[f] = MAX2(fill[f], (int32_t)(reg + size - 1)); 15457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 15557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 15657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 157ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerezbool 158e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegisterSet::occupy(const Value *v) 15957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 160e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return occupy(v->reg.file, v->reg.data.id, v->reg.size >> unit[v->reg.file]); 161e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 16257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 163e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 164e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegisterSet::occupyMask(DataFile f, int32_t reg, uint8_t mask) 165e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 166e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bits[f].setMask(reg & ~31, static_cast<uint32_t>(mask) << (reg % 32)); 167e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 16857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 169e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerbool 170e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegisterSet::occupy(DataFile f, int32_t reg, unsigned int size) 171e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 172e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (bits[f].testRange(reg, size)) 173ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez return false; 174ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 175e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bits[f].setRange(reg, size); 17657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 177e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(0, REG_ALLOC, "reg occupy: %u[%i] %u\n", f, reg, size); 17857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 179e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller fill[f] = MAX2(fill[f], (int32_t)(reg + size - 1)); 180ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 181ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez return true; 18257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 18357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 185e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegisterSet::release(DataFile f, int32_t reg, unsigned int size) 18657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 187e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bits[f].clrRange(reg, size); 18857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 189e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(0, REG_ALLOC, "reg release: %u[%i] %u\n", f, reg, size); 19057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 19157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass RegAlloc 19357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 19457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 19557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegAlloc(Program *program) : prog(program), sequence(0) { } 19657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool exec(); 19857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool execFunc(); 19957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 20157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class PhiMovesPass : public Pass { 20257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 20357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool visit(BasicBlock *); 20457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool needNewElseBlock(BasicBlock *b, BasicBlock *p); 20557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 20657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 207ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez class ArgumentMovesPass : public Pass { 208ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez private: 209ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez virtual bool visit(BasicBlock *); 210ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez }; 211ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 21257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class BuildIntervalsPass : public Pass { 21357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 21457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool visit(BasicBlock *); 21557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void collectLiveValues(BasicBlock *); 21657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void addLiveRange(Value *, const BasicBlock *, int end); 21757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 21857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class InsertConstraintsPass : public Pass { 22057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 22157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool exec(Function *func); 22257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 22357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool visit(BasicBlock *); 22457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool insertConstraintMoves(); 22657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 227e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void condenseDefs(Instruction *); 228e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void condenseSrcs(Instruction *, const int first, const int last); 229e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 23057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void addHazard(Instruction *i, const ValueRef *src); 23157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void textureMask(TexInstruction *); 23257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void addConstraint(Instruction *, int s, int n); 23357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool detectConflict(Instruction *, int s); 23457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 235e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // target specific functions, TODO: put in subclass or Target 236e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void texConstraintNV50(TexInstruction *); 237e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void texConstraintNVC0(TexInstruction *); 238e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void texConstraintNVE0(TexInstruction *); 239e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 240e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<Instruction *> constrList; 241e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 242e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const Target *targ; 24357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 24457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool buildLiveSets(BasicBlock *); 24657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 24857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Program *prog; 24957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Function *func; 25057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // instructions in control flow / chronological order 25257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ArrayList insns; 25357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int sequence; // for manual passes through CFG 25557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 25657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 257e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillertypedef std::pair<Value *, Value *> ValuePair; 258e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 259e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerclass SpillCodeInserter 26057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 261e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerpublic: 262e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller SpillCodeInserter(Function *fn) : func(fn), stackSize(0), stackBase(0) { } 263e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 264e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool run(const std::list<ValuePair>&); 265e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 266e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Symbol *assignSlot(const Interval&, unsigned int size); 267e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline int32_t getStackSize() const { return stackSize; } 268e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 269e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerprivate: 270e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Function *func; 271e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 272e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller struct SpillSlot 273e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 274e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Interval occup; 275e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<Value *> residents; // needed to recalculate occup 276e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Symbol *sym; 277e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int32_t offset; 278e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline uint8_t size() const { return sym->reg.size; } 279e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller }; 280e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<SpillSlot> slots; 281e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int32_t stackSize; 282e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int32_t stackBase; 283e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 284e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *unspill(Instruction *usei, LValue *, Value *slot); 285e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void spill(Instruction *defi, Value *slot, LValue *); 286e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller}; 28757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 28957594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::BuildIntervalsPass::addLiveRange(Value *val, 29057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const BasicBlock *bb, 29157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int end) 29257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 29357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *insn = val->getUniqueInsn(); 29457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!insn) 296530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez insn = bb->getFirst(); 297530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez 29857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(bb->getFirst()->serial <= bb->getExit()->serial); 29957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(bb->getExit()->serial + 1 >= end); 30057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 30157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int begin = insn->serial; 30257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (begin < bb->getEntry()->serial || begin > bb->getExit()->serial) 30357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller begin = bb->getEntry()->serial; 30457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 30557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "%%%i <- live range [%i(%i), %i)\n", 30657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller val->id, begin, insn->serial, end); 30757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 30857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (begin != end) // empty ranges are only added as hazards for fixed regs 30957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller val->livei.extend(begin, end); 31057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 31157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 31357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::PhiMovesPass::needNewElseBlock(BasicBlock *b, BasicBlock *p) 31457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 31557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (b->cfg.incidentCount() <= 1) 31657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 31757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int n = 0; 31957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = p->cfg.outgoing(); !ei.end(); ei.next()) 32057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.getType() == Graph::Edge::TREE || 32157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ei.getType() == Graph::Edge::FORWARD) 32257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++n; 32357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return (n == 2); 32457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 32557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 32657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// For each operand of each PHI in b, generate a new value by inserting a MOV 32757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// at the end of the block it is coming from and replace the operand with its 32857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// result. This eliminates liveness conflicts and enables us to let values be 32957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// copied to the right register if such a conflict exists nonetheless. 33057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// 33157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// These MOVs are also crucial in making sure the live intervals of phi srces 33257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// are extended until the end of the loop, since they are not included in the 33357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// live-in sets. 33457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 33557594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::PhiMovesPass::visit(BasicBlock *bb) 33657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 33757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *phi, *mov; 33857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *pb, *pn; 33957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 340e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::stack<BasicBlock *> stack; 341e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 34257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) { 343e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pb = BasicBlock::get(ei.getNode()); 34457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(pb); 345e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (needNewElseBlock(bb, pb)) 346e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller stack.push(pb); 347e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 348e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller while (!stack.empty()) { 349e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pb = stack.top(); 350e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pn = new BasicBlock(func); 351e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller stack.pop(); 352e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 353e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pb->cfg.detach(&bb->cfg); 354e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pb->cfg.attach(&pn->cfg, Graph::Edge::TREE); 355e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pn->cfg.attach(&bb->cfg, Graph::Edge::FORWARD); 356e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 357e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(pb->getExit()->op != OP_CALL); 358e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (pb->getExit()->asFlow()->target.bb == bb) 359e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pb->getExit()->asFlow()->target.bb = pn; 36057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 36157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3629362d4bc0a03860ec386156cf499e855a9c2d2a5Christoph Bumiller // insert MOVs (phi->src(j) should stem from j-th in-BB) 36357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int j = 0; 36457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) { 36557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb = BasicBlock::get(ei.getNode()); 36657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!pb->isTerminated()) 36757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb->insertTail(new_FlowInstruction(func, OP_BRA, bb)); 36857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (phi = bb->getPhi(); phi && phi->op == OP_PHI; phi = phi->next) { 37057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mov = new_Instruction(func, OP_MOV, TYPE_U32); 37157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mov->setSrc(0, phi->getSrc(j)); 37357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mov->setDef(0, new_LValue(func, phi->getDef(0)->asLValue())); 37457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller phi->setSrc(j, mov->getDef(0)); 37557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pb->insertBefore(pb->getExit(), mov); 37757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 37857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++j; 37957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 38057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 38257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 38357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 384ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerezbool 385ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco JerezRegAlloc::ArgumentMovesPass::visit(BasicBlock *bb) 386ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez{ 387ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez // Bind function call inputs/outputs to the same physical register 388ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez // the callee uses, inserting moves as appropriate for the case a 389ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez // conflict arises. 390ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez for (Instruction *i = bb->getEntry(); i; i = i->next) { 391ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez FlowInstruction *cal = i->asFlow(); 392ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez if (!cal || cal->op != OP_CALL || cal->builtin) 393ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez continue; 394ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez RegisterSet clobberSet(prog->getTarget()); 395ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 396ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez // Bind input values. 397ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez for (int s = 0; cal->srcExists(s); ++s) { 398ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez LValue *tmp = new_LValue(func, cal->getSrc(s)->asLValue()); 399ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez tmp->reg.data.id = cal->target.fn->ins[s].rep()->reg.data.id; 400ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 401ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez Instruction *mov = 402ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez new_Instruction(func, OP_MOV, typeOfSize(tmp->reg.size)); 403ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez mov->setDef(0, tmp); 404ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez mov->setSrc(0, cal->getSrc(s)); 405ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez cal->setSrc(s, tmp); 406ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 407ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez bb->insertBefore(cal, mov); 408ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez } 409ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 410ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez // Bind output values. 411ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez for (int d = 0; cal->defExists(d); ++d) { 412ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez LValue *tmp = new_LValue(func, cal->getDef(d)->asLValue()); 413ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez tmp->reg.data.id = cal->target.fn->outs[d].rep()->reg.data.id; 414ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 415ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez Instruction *mov = 416ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez new_Instruction(func, OP_MOV, typeOfSize(tmp->reg.size)); 417ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez mov->setSrc(0, tmp); 418ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez mov->setDef(0, cal->getDef(d)); 419ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez cal->setDef(d, tmp); 420ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 421ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez bb->insertAfter(cal, mov); 422ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez clobberSet.occupy(tmp); 423ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez } 424ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 425ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez // Bind clobbered values. 426ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez for (std::deque<Value *>::iterator it = cal->target.fn->clobbers.begin(); 427ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez it != cal->target.fn->clobbers.end(); 428ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez ++it) { 429ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez if (clobberSet.occupy(*it)) { 430ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez Value *tmp = new_LValue(func, (*it)->asLValue()); 431ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez tmp->reg.data.id = (*it)->reg.data.id; 432ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez cal->setDef(cal->defCount(), tmp); 433ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez } 434ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez } 435ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez } 436ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 437ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez // Update the clobber set of the function. 438ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez if (BasicBlock::get(func->cfgExit) == bb) { 439ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez func->buildDefSets(); 440ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez for (unsigned int i = 0; i < bb->defSet.getSize(); ++i) 441ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez if (bb->defSet.test(i)) 442ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez func->clobbers.push_back(func->getLValue(i)); 443ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez } 444ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 445ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez return true; 446ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez} 447ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 44857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Build the set of live-in variables of bb. 44957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 45057594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::buildLiveSets(BasicBlock *bb) 45157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 452530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez Function *f = bb->getFunction(); 45357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *bn; 45457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *i; 45557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int s, d; 45657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 45757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "buildLiveSets(BB:%i)\n", bb->getId()); 45857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 45957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.allocate(func->allLValues.getSize(), false); 46057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 46157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int n = 0; 46257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 46357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bn = BasicBlock::get(ei.getNode()); 46457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bn == bb) 46557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 46657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bn->cfg.visit(sequence)) 46757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!buildLiveSets(bn)) 46857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 469f4dbdcbfcf7370deeb5dcccec2e8d1c471d66517Francisco Jerez if (n++ || bb->liveSet.marker) 47057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet |= bn->liveSet; 471f4dbdcbfcf7370deeb5dcccec2e8d1c471d66517Francisco Jerez else 472f4dbdcbfcf7370deeb5dcccec2e8d1c471d66517Francisco Jerez bb->liveSet = bn->liveSet; 47357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 47457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!n && !bb->liveSet.marker) 47557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.fill(0); 47657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.marker = true; 47757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 47857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) { 47957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("BB:%i live set of out blocks:\n", bb->getId()); 48057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.print(); 48157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 48257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 48357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // if (!bb->getEntry()) 48457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // return true; 48557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 486530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez if (bb == BasicBlock::get(f->cfgExit)) { 487530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez for (std::deque<ValueRef>::iterator it = f->outs.begin(); 488530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez it != f->outs.end(); ++it) { 489530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez assert(it->get()->asLValue()); 490530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez bb->liveSet.set(it->get()->id); 491530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez } 492530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez } 493530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez 49457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (i = bb->getExit(); i && i != bb->getEntry()->prev; i = i->prev) { 49557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0; i->defExists(d); ++d) 49657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getDef(d)->id); 49757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (s = 0; i->srcExists(s); ++s) 49857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->getSrc(s)->asLValue()) 49957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.set(i->getSrc(s)->id); 50057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 50157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (i = bb->getPhi(); i && i->op == OP_PHI; i = i->next) 50257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getDef(0)->id); 50357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 50457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) { 50557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("BB:%i live set after propagation:\n", bb->getId()); 50657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.print(); 50757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 50857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 50957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 51057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 51157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 51257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 51357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::BuildIntervalsPass::collectLiveValues(BasicBlock *bb) 51457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 51557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *bbA = NULL, *bbB = NULL; 51657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 51757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb->cfg.outgoingCount()) { 51857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // trickery to save a loop of OR'ing liveSets 51957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // aliasing works fine with BitSet::setOr 52057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 52157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ei.getType() == Graph::Edge::DUMMY) 52257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 52357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bbA) { 52457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.setOr(&bbA->liveSet, &bbB->liveSet); 52557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbA = bb; 52657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 52757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbA = bbB; 52857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 52957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bbB = BasicBlock::get(ei.getNode()); 53057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 53157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.setOr(&bbB->liveSet, bbA ? &bbA->liveSet : NULL); 53257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 53357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb->cfg.incidentCount()) { 53457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.fill(0); 53557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 53657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 53757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 53857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 53957594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::BuildIntervalsPass::visit(BasicBlock *bb) 54057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 54157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller collectLiveValues(bb); 54257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "BuildIntervals(BB:%i)\n", bb->getId()); 54457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // go through out blocks and delete phi sources that do not originate from 54657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // the current block from the live set 54757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 54857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BasicBlock *out = BasicBlock::get(ei.getNode()); 54957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 55057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Instruction *i = out->getPhi(); i && i->op == OP_PHI; i = i->next) { 55157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getDef(0)->id); 55257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 5538cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez for (int s = 0; i->srcExists(s); ++s) { 5549362d4bc0a03860ec386156cf499e855a9c2d2a5Christoph Bumiller assert(i->src(s).getInsn()); 55557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->getSrc(s)->getUniqueInsn()->bb == bb) // XXX: reachableBy ? 55657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.set(i->getSrc(s)->id); 55757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller else 55857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getSrc(s)->id); 55957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 56057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 56157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 56257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 56357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // remaining live-outs are live until end 56457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb->getExit()) { 56557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int j = 0; j < bb->liveSet.getSize(); ++j) 56657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (bb->liveSet.test(j)) 56757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller addLiveRange(func->getLValue(j), bb, bb->getExit()->serial + 1); 56857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 56957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 57057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Instruction *i = bb->getExit(); i && i->op != OP_PHI; i = i->prev) { 57157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int d = 0; i->defExists(d); ++d) { 57257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.clr(i->getDef(d)->id); 57357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->getDef(d)->reg.data.id >= 0) // add hazard for fixed regs 57457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->getDef(d)->livei.extend(i->serial, i->serial); 57557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 57657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 57757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int s = 0; i->srcExists(s); ++s) { 57857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!i->getSrc(s)->asLValue()) 57957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 58057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!bb->liveSet.test(i->getSrc(s)->id)) { 58157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bb->liveSet.set(i->getSrc(s)->id); 58257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller addLiveRange(i->getSrc(s), bb, i->serial); 58357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 58457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 58557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 58657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 587530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez if (bb == BasicBlock::get(func->cfg.getRoot())) { 588530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez for (std::deque<ValueDef>::iterator it = func->ins.begin(); 589530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez it != func->ins.end(); ++it) { 590530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez if (it->get()->reg.data.id >= 0) // add hazard for fixed regs 591530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez it->get()->livei.extend(0, 1); 592530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez } 593530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez } 594530ff61ba77f940f6f4093956b99221ab62ab430Francisco Jerez 59557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 59657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 59757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 598e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 599e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#define JOIN_MASK_PHI (1 << 0) 600e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#define JOIN_MASK_UNION (1 << 1) 601e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#define JOIN_MASK_MOV (1 << 2) 602e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#define JOIN_MASK_TEX (1 << 3) 603e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 604e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerclass GCRA 605e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 606e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerpublic: 607e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller GCRA(Function *, SpillCodeInserter&); 608e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ~GCRA(); 609e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 610e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool allocateRegisters(ArrayList& insns); 611e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 612e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void printNodeInfo() const; 613e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 614e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerprivate: 615e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller class RIG_Node : public Graph::Node 616e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 617e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller public: 618e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node(); 619e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 620e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void init(const RegisterSet&, LValue *); 621e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 622e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void addInterference(RIG_Node *); 623e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void addRegPreference(RIG_Node *); 624e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 625e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline LValue *getValue() const 626e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 627e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return reinterpret_cast<LValue *>(data); 628e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 629e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline void setValue(LValue *lval) { data = lval; } 630e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 631e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline uint8_t getCompMask() const 632e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 633e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return ((1 << colors) - 1) << (reg & 7); 634e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 635e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 636e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller static inline RIG_Node *get(const Graph::EdgeIterator& ei) 637e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 638e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return static_cast<RIG_Node *>(ei.getNode()); 639e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 640e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 641e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller public: 642e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint32_t degree; 643e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint16_t degreeLimit; // if deg < degLimit, node is trivially colourable 644e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint16_t colors; 645e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 646e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller DataFile f; 647e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int32_t reg; 648e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 649e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller float weight; 650e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 651e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // list pointers for simplify() phase 652e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *next; 653e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *prev; 654e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 655e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // union of the live intervals of all coalesced values (we want to retain 656e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // the separate intervals for testing interference of compound values) 657e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Interval livei; 658e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 659e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<RIG_Node *> prefRegs; 660e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller }; 661e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 662e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerprivate: 663e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline RIG_Node *getNode(const LValue *v) const { return &nodes[v->id]; } 664e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 665e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void buildRIG(ArrayList&); 666e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool coalesce(ArrayList&); 667e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool doCoalesce(ArrayList&, unsigned int mask); 668e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void calculateSpillWeights(); 669e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void simplify(); 670e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool selectRegisters(); 671e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void cleanup(const bool success); 672e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 673e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void simplifyEdge(RIG_Node *, RIG_Node *); 674e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void simplifyNode(RIG_Node *); 675e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 676e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool coalesceValues(Value *, Value *, bool force); 677e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void resolveSplitsAndMerges(); 678e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void makeCompound(Instruction *, bool isSplit); 679e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 680e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline void checkInterference(const RIG_Node *, Graph::EdgeIterator&); 681e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 682e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline void insertOrderedTail(std::list<RIG_Node *>&, RIG_Node *); 683e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void checkList(std::list<RIG_Node *>&); 684e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 685e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerprivate: 686e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::stack<uint32_t> stack; 687e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 688e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // list headers for simplify() phase 689e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node lo[2]; 690e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node hi; 691e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 692e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Graph RIG; 693e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *nodes; 694e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller unsigned int nodeCount; 695e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 696e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Function *func; 697e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Program *prog; 698e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 699e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller static uint8_t relDegree[17][17]; 700e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 701e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RegisterSet regs; 702e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 703e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // need to fixup register id for participants of OP_MERGE/SPLIT 704e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<Instruction *> merges; 705e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<Instruction *> splits; 706e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 707e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller SpillCodeInserter& spill; 708e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<ValuePair> mustSpill; 709e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller}; 710e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 711e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumilleruint8_t GCRA::relDegree[17][17]; 712e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 713e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::RIG_Node::RIG_Node() : Node(NULL), next(this), prev(this) 714e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 715e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller colors = 0; 716e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 717e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 718e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 719e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::printNodeInfo() const 720e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 721e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (unsigned int i = 0; i < nodeCount; ++i) { 722e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!nodes[i].colors) 723e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 724e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO("RIG_Node[%%%i]($[%u]%i): %u colors, weight %f, deg %u/%u\n X", 725e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller i, 726e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nodes[i].f,nodes[i].reg,nodes[i].colors, 727e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nodes[i].weight, 728e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nodes[i].degree, nodes[i].degreeLimit); 729e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 730e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Graph::EdgeIterator ei = nodes[i].outgoing(); !ei.end(); ei.next()) 731e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO(" %%%i", RIG_Node::get(ei)->getValue()->id); 732e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Graph::EdgeIterator ei = nodes[i].incident(); !ei.end(); ei.next()) 733e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO(" %%%i", RIG_Node::get(ei)->getValue()->id); 734e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO("\n"); 735e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 736e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 737e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 738e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 739e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::RIG_Node::init(const RegisterSet& regs, LValue *lval) 740e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 741e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller setValue(lval); 742e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (lval->reg.data.id >= 0) 743e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->noSpill = lval->fixedReg = 1; 744e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 745e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller colors = regs.units(lval->reg.file, lval->reg.size); 746e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller f = lval->reg.file; 747e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller reg = -1; 748e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (lval->reg.data.id >= 0) 749e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller reg = regs.idToUnits(lval); 750e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 751e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller weight = std::numeric_limits<float>::infinity(); 752e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller degree = 0; 753e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller degreeLimit = regs.getFileSize(f, lval->reg.size); 754e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 755e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller livei.insert(lval->livei); 756e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 757e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 758e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerbool 759e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::coalesceValues(Value *dst, Value *src, bool force) 760e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 761e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *rep = dst->join->asLValue(); 762e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *val = src->join->asLValue(); 763e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 764e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!force && val->reg.data.id >= 0) { 765e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller rep = src->join->asLValue(); 766e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller val = dst->join->asLValue(); 767e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 768e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *nRep = &nodes[rep->id]; 769e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *nVal = &nodes[val->id]; 770e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 771e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (src->reg.file != dst->reg.file) { 772e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!force) 773e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 774e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller WARN("forced coalescing of values in different files !\n"); 775e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 776e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!force && dst->reg.size != src->reg.size) 777e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 778e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 779e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if ((rep->reg.data.id >= 0) && (rep->reg.data.id != val->reg.data.id)) { 780e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (force) { 781e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (val->reg.data.id >= 0) 782e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller WARN("forced coalescing of values in different fixed regs !\n"); 783e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 784e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (val->reg.data.id >= 0) 785e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 786e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // make sure that there is no overlap with the fixed register of rep 787e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (ArrayList::Iterator it = func->allLValues.iterator(); 788e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller !it.end(); it.next()) { 789e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Value *reg = reinterpret_cast<Value *>(it.get())->asLValue(); 790e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(reg); 791e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (reg->interfers(rep) && reg->livei.overlaps(nVal->livei)) 792e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 793e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 794e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 795e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 796e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 797e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!force && nRep->livei.overlaps(nVal->livei)) 798e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 799e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 800e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "joining %%%i($%i) <- %%%i\n", 801e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller rep->id, rep->reg.data.id, val->id); 802e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 803e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // set join pointer of all values joined with val 804e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Value::DefIterator def = val->defs.begin(); def != val->defs.end(); 805e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++def) 806e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller (*def)->get()->join = rep; 807e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(rep->join == rep && val->join == rep); 808e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 809e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // add val's definitions to rep and extend the live interval of its RIG node 810e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller rep->defs.insert(rep->defs.end(), val->defs.begin(), val->defs.end()); 811e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nRep->livei.unify(nVal->livei); 812e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return true; 813e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 814e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 815e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerbool 816e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::coalesce(ArrayList& insns) 817e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 818e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool ret = doCoalesce(insns, JOIN_MASK_PHI); 819e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!ret) 820e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 821e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller switch (func->getProgram()->getTarget()->getChipset() & ~0xf) { 822e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0x50: 823e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0x80: 824e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0x90: 825e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0xa0: 826e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = doCoalesce(insns, JOIN_MASK_UNION | JOIN_MASK_TEX); 827e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 828e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0xc0: 829e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0xd0: 830e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0xe0: 831e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = doCoalesce(insns, JOIN_MASK_UNION); 832e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 833e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller default: 834e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 835e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 836e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!ret) 837e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 838e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return doCoalesce(insns, JOIN_MASK_MOV); 839e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 840e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 841e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerstatic inline uint8_t makeCompMask(int compSize, int base, int size) 842e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 843e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint8_t m = ((1 << size) - 1) << base; 844e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 845e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller switch (compSize) { 846e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 1: 847e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return 0xff; 848e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 2: 849e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller m |= (m << 2); 850e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return (m << 4) | m; 851e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 3: 852e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 4: 853e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return (m << 4) | m; 854e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller default: 855e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(compSize <= 8); 856e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return m; 857e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 858e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 859e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 860e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerstatic inline void copyCompound(Value *dst, Value *src) 861e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 862e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *ldst = dst->asLValue(); 863e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lsrc = src->asLValue(); 864e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 865e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ldst->compound = lsrc->compound; 866e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ldst->compMask = lsrc->compMask; 867e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 868e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 869e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 870e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::makeCompound(Instruction *insn, bool split) 871e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 872e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *rep = (split ? insn->getSrc(0) : insn->getDef(0))->asLValue(); 873e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 874e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) { 875e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO("makeCompound(split = %i): ", split); 876e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->print(); 877e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 878e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 879e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const unsigned int size = getNode(rep)->colors; 880e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller unsigned int base = 0; 881e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 882e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!rep->compound) 883e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller rep->compMask = 0xff; 884e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller rep->compound = 1; 885e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 886e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int c = 0; split ? insn->defExists(c) : insn->srcExists(c); ++c) { 887e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *val = (split ? insn->getDef(c) : insn->getSrc(c))->asLValue(); 888e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 889e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller val->compound = 1; 890e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!val->compMask) 891e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller val->compMask = 0xff; 892e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller val->compMask &= makeCompMask(size, base, getNode(val)->colors); 893e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(val->compMask); 894e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 895e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "compound: %%%i:%02x <- %%%i:%02x\n", 896e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller rep->id, rep->compMask, val->id, val->compMask); 897e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 898e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller base += getNode(val)->colors; 899e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 900e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(base == size); 901e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 902e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 90357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 904e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::doCoalesce(ArrayList& insns, unsigned int mask) 90557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 90657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int c, n; 90757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 90857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (n = 0; n < insns.getSize(); ++n) { 90957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *i; 910e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *insn = reinterpret_cast<Instruction *>(insns.get(n)); 91157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 91257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller switch (insn->op) { 91357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_PHI: 91457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_PHI)) 91557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 91657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; insn->srcExists(c); ++c) 917e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!coalesceValues(insn->getDef(0), insn->getSrc(c), false)) { 918e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // this is bad 91957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ERROR("failed to coalesce phi operands\n"); 92057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 92157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 92257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 92357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_UNION: 924e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case OP_MERGE: 92557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_UNION)) 92657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 92757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; insn->srcExists(c); ++c) 928e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller coalesceValues(insn->getDef(0), insn->getSrc(c), true); 929e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (insn->op == OP_MERGE) { 930e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller merges.push_back(insn); 931e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (insn->srcExists(1)) 932e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller makeCompound(insn, false); 933e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 93457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 935e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case OP_SPLIT: 936e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!(mask & JOIN_MASK_UNION)) 93757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 938e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller splits.push_back(insn); 939e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (c = 0; insn->defExists(c); ++c) 940e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller coalesceValues(insn->getSrc(0), insn->getDef(c), true); 941e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller makeCompound(insn, true); 94257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 94357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_MOV: 94457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_MOV)) 94557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 9468cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez i = NULL; 9478cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez if (!insn->getDef(0)->uses.empty()) 9488cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez i = insn->getDef(0)->uses.front()->getInsn(); 9494021979182d3a6eb2bed1e9d784e218eb88bfa28Christoph Bumiller // if this is a contraint-move there will only be a single use 950e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (i && i->op == OP_MERGE) // do we really still need this ? 9514021979182d3a6eb2bed1e9d784e218eb88bfa28Christoph Bumiller break; 95257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i = insn->getSrc(0)->getUniqueInsn(); 953e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (i && !i->constrainedDefs()) { 954e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (coalesceValues(insn->getDef(0), insn->getSrc(0), false)) 955e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller copyCompound(insn->getSrc(0), insn->getDef(0)); 956e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 95757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 95857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TEX: 95957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXB: 96057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXL: 96157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXF: 96257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXQ: 96357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXD: 96457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TXG: 96557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller case OP_TEXCSAA: 96657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(mask & JOIN_MASK_TEX)) 96757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 968e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (c = 0; insn->srcExists(c) && c != insn->predSrc; ++c) 969e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller coalesceValues(insn->getDef(c), insn->getSrc(c), true); 97057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 97157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller default: 97257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 97357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 97457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 97557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 97657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 97757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 97857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 979e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::RIG_Node::addInterference(RIG_Node *node) 980e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 981e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller this->degree += relDegree[node->colors][colors]; 982e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller node->degree += relDegree[colors][node->colors]; 983e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 984e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller this->attach(node, Graph::Edge::CROSS); 985e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 986e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 987e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 988e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::RIG_Node::addRegPreference(RIG_Node *node) 989e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 990e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller prefRegs.push_back(node); 991e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 992e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 993e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::GCRA(Function *fn, SpillCodeInserter& spill) : 994e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller func(fn), 995e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs(fn->getProgram()->getTarget()), 996e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller spill(spill) 99757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 998e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller prog = func->getProgram(); 999e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1000e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // initialize relative degrees array - i takes away from j 1001e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int i = 1; i <= 16; ++i) 1002e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int j = 1; j <= 16; ++j) 1003e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller relDegree[i][j] = j * ((i + j - 1) / j); 1004e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1005e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1006e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::~GCRA() 1007e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1008e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (nodes) 1009e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller delete[] nodes; 1010e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1011e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1012e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1013e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::checkList(std::list<RIG_Node *>& lst) 1014e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1015e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller GCRA::RIG_Node *prev = NULL; 1016e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1017e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::list<RIG_Node *>::iterator it = lst.begin(); 1018e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != lst.end(); 1019e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) { 1020e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert((*it)->getValue()->join == (*it)->getValue()); 1021e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (prev) 1022e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(prev->livei.begin() <= (*it)->livei.begin()); 1023e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller prev = *it; 1024e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1025e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1026e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1027e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1028e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::insertOrderedTail(std::list<RIG_Node *>& list, RIG_Node *node) 1029e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1030e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (node->livei.isEmpty()) 1031e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return; 1032e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // only the intervals of joined values don't necessarily arrive in order 1033e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<RIG_Node *>::iterator prev, it; 1034e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (it = list.end(); it != list.begin(); it = prev) { 1035e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller prev = it; 1036e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller --prev; 1037e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if ((*prev)->livei.begin() <= node->livei.begin()) 103857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 103957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1040e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller list.insert(it, node); 104157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 104257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1043e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1044e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::buildRIG(ArrayList& insns) 104557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 1046e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<RIG_Node *> values, active; 1047e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1048e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::deque<ValueDef>::iterator it = func->ins.begin(); 1049e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != func->ins.end(); ++it) 1050e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insertOrderedTail(values, getNode(it->get()->asLValue())); 1051e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1052e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int i = 0; i < insns.getSize(); ++i) { 1053e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *insn = reinterpret_cast<Instruction *>(insns.get(i)); 1054e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int d = 0; insn->defExists(d); ++d) 1055e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (insn->getDef(d)->rep() == insn->getDef(d)) 1056e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insertOrderedTail(values, getNode(insn->getDef(d)->asLValue())); 1057e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1058e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller checkList(values); 105957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1060e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller while (!values.empty()) { 1061e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *cur = values.front(); 1062e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1063e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::list<RIG_Node *>::iterator it = active.begin(); 1064e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != active.end(); 1065e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) { 1066e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *node = *it; 1067e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1068e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (node->livei.end() <= cur->livei.begin()) { 1069e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it = active.erase(it); 1070e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller --it; 1071e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 1072e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (node->f == cur->f && node->livei.overlaps(cur->livei)) { 1073e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cur->addInterference(node); 1074e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 107557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1076e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller values.pop_front(); 1077e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller active.push_back(cur); 107857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 107957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 108057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 108157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 1082e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::calculateSpillWeights() 108357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 1084e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (unsigned int i = 0; i < nodeCount; ++i) { 1085e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *const n = &nodes[i]; 1086e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!nodes[i].colors || nodes[i].livei.isEmpty()) 1087e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 1088e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (nodes[i].reg >= 0) { 1089e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // update max reg 1090e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs.occupy(n->f, n->reg, n->colors); 1091e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 1092e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1093e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *val = nodes[i].getValue(); 1094a5397851870d3a9969b2b864c849ba209ef9b0f7Francisco Jerez 1095e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!val->noSpill) { 1096e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int rc = 0; 1097e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Value::DefIterator it = val->defs.begin(); 1098e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != val->defs.end(); 1099e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) 1100e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller rc += (*it)->get()->refCount(); 110157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1102e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nodes[i].weight = 1103e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller (float)rc * (float)rc / (float)nodes[i].livei.extent(); 1104e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1105e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1106e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (nodes[i].degree < nodes[i].degreeLimit) { 1107e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int l = 0; 1108e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (val->reg.size > 4) 1109e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller l = 1; 1110e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller DLLIST_ADDHEAD(&lo[l], &nodes[i]); 1111e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1112e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller DLLIST_ADDHEAD(&hi, &nodes[i]); 1113e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 111457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1115e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) 1116e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller printNodeInfo(); 111757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 111857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1119e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1120e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::simplifyEdge(RIG_Node *a, RIG_Node *b) 112157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 1122e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool move = b->degree >= b->degreeLimit; 112357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1124e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, 1125e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller "edge: (%%%i, deg %u/%u) >-< (%%%i, deg %u/%u)\n", 1126e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller a->getValue()->id, a->degree, a->degreeLimit, 1127e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller b->getValue()->id, b->degree, b->degreeLimit); 112857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1129e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller b->degree -= relDegree[a->colors][b->colors]; 113057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1131e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller move = move && b->degree < b->degreeLimit; 1132e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (move && !DLLIST_EMPTY(b)) { 1133e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int l = (b->getValue()->reg.size > 4) ? 1 : 0; 1134e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller DLLIST_DEL(b); 1135e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller DLLIST_ADDTAIL(&lo[l], b); 1136e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1137e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 113857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1139e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1140e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::simplifyNode(RIG_Node *node) 1141e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1142e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) 1143e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller simplifyEdge(node, RIG_Node::get(ei)); 114457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1145e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Graph::EdgeIterator ei = node->incident(); !ei.end(); ei.next()) 1146e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller simplifyEdge(node, RIG_Node::get(ei)); 114757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1148e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller DLLIST_DEL(node); 1149e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller stack.push(node->getValue()->id); 115057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1151e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "SIMPLIFY: pushed %%%i%s\n", 1152e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller node->getValue()->id, 1153e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller (node->degree < node->degreeLimit) ? "" : "(spill)"); 1154e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1155e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1156e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1157e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::simplify() 1158e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1159e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (;;) { 1160e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!DLLIST_EMPTY(&lo[0])) { 1161e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller do { 1162e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller simplifyNode(lo[0].next); 1163e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } while (!DLLIST_EMPTY(&lo[0])); 1164e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 1165e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!DLLIST_EMPTY(&lo[1])) { 1166e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller simplifyNode(lo[1].next); 1167e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 1168e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!DLLIST_EMPTY(&hi)) { 1169e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *best = hi.next; 1170e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller float bestScore = best->weight / (float)best->degree; 1171e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // spill candidate 1172e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (RIG_Node *it = best->next; it != &hi; it = it->next) { 1173e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller float score = it->weight / (float)it->degree; 1174e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (score < bestScore) { 1175e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller best = it; 1176e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bestScore = score; 1177e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 117857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1179e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (isinf(bestScore)) { 1180e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ERROR("no viable spill candidates left\n"); 1181e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1182e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1183e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller simplifyNode(best); 1184e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1185e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 118657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1187e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1188e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1189e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1190e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1191e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::checkInterference(const RIG_Node *node, Graph::EdgeIterator& ei) 1192e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1193e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const RIG_Node *intf = RIG_Node::get(ei); 1194e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1195e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (intf->reg < 0) 1196e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return; 1197e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const LValue *vA = node->getValue(); 1198e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const LValue *vB = intf->getValue(); 119957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1200e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const uint8_t intfMask = ((1 << intf->colors) - 1) << (intf->reg & 7); 120157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1202e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (vA->compound | vB->compound) { 1203e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // NOTE: this only works for >aligned< register tuples ! 1204e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Value::DefCIterator D = vA->defs.begin(); D != vA->defs.end(); ++D) { 1205e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Value::DefCIterator d = vB->defs.begin(); d != vB->defs.end(); ++d) { 1206e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const LValue *vD = (*D)->get()->asLValue(); 1207e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const LValue *vd = (*d)->get()->asLValue(); 1208e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1209e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!vD->livei.overlaps(vd->livei)) { 1210e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "(%%%i) X (%%%i): no overlap\n", 1211e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller vD->id, vd->id); 1212e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 121357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 121457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1215e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint8_t mask = vD->compound ? vD->compMask : ~0; 1216e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (vd->compound) { 1217e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(vB->compound); 1218e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mask &= vd->compMask & vB->compMask; 1219e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1220e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mask &= intfMask; 1221e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1222e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1223e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, 1224e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller "(%%%i)%02x X (%%%i)%02x & %02x: $r%i.%02x\n", 1225e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller vD->id, 1226e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller vD->compound ? vD->compMask : 0xff, 1227e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller vd->id, 1228e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller vd->compound ? vd->compMask : intfMask, 1229e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller vB->compMask, intf->reg & ~7, mask); 1230e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (mask) 1231e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs.occupyMask(node->f, intf->reg & ~7, mask); 123257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1233e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1234e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1235e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, 1236e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller "(%%%i) X (%%%i): $r%i + %u\n", 1237e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller vA->id, vB->id, intf->reg, intf->colors); 1238e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs.occupy(node->f, intf->reg, intf->colors); 1239e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1240e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 124157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1242e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerbool 1243e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::selectRegisters() 1244e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1245e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "\nSELECT phase\n"); 1246e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1247e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller while (!stack.empty()) { 1248e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG_Node *node = &nodes[stack.top()]; 1249e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller stack.pop(); 1250e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1251e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs.reset(node->f); 1252e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1253e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "\nNODE[%%%i, %u colors]\n", 1254e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller node->getValue()->id, node->colors); 1255e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1256e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) 1257e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller checkInterference(node, ei); 1258e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Graph::EdgeIterator ei = node->incident(); !ei.end(); ei.next()) 1259e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller checkInterference(node, ei); 1260e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1261e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!node->prefRegs.empty()) { 1262e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::list<RIG_Node *>::const_iterator it = node->prefRegs.begin(); 1263e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != node->prefRegs.end(); 1264e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) { 1265e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if ((*it)->reg >= 0 && 1266e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs.occupy(node->f, (*it)->reg, node->colors)) { 1267e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller node->reg = (*it)->reg; 1268e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1269e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1270e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1271e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1272e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (node->reg >= 0) 1273e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 1274e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = node->getValue(); 1275e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) 1276e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs.print(); 1277e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool ret = regs.assign(node->reg, node->f, node->colors); 1278e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (ret) { 1279e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "assigned reg %i\n", node->reg); 1280e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->compMask = node->getCompMask(); 1281e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1282e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "must spill: %%%i (size %u)\n", 1283e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->id, lval->reg.size); 1284e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Symbol *slot = NULL; 1285e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (lval->reg.file == FILE_GPR) 1286e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slot = spill.assignSlot(node->livei, lval->reg.size); 1287e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mustSpill.push_back(ValuePair(lval, slot)); 1288e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1289e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1290e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!mustSpill.empty()) 1291e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 1292e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (unsigned int i = 0; i < nodeCount; ++i) { 1293e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = nodes[i].getValue(); 1294e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (nodes[i].reg >= 0 && nodes[i].colors > 0) 1295e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->reg.data.id = 1296e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs.unitsToId(nodes[i].f, nodes[i].reg, lval->reg.size); 129757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 129857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 129957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 130057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 130157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 1302e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::allocateRegisters(ArrayList& insns) 130357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 1304e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool ret; 1305e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1306e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, 1307e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller "allocateRegisters to %u instructions\n", insns.getSize()); 130857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1309e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nodeCount = func->allLValues.getSize(); 1310e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nodes = new RIG_Node[nodeCount]; 1311e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!nodes) 1312e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 1313e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (unsigned int i = 0; i < nodeCount; ++i) { 1314e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = reinterpret_cast<LValue *>(func->allLValues.get(i)); 1315e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (lval) { 1316e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nodes[i].init(regs, lval); 1317e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller RIG.insert(&nodes[i]); 1318e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1319e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 132057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1321e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // coalesce first, we use only 1 RIG node for a group of joined values 1322e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = coalesce(insns); 1323e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!ret) 1324e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller goto out; 132557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1326e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (func->getProgram()->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) 1327e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller func->printLiveIntervals(); 132857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1329e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller buildRIG(insns); 1330e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller calculateSpillWeights(); 1331e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller simplify(); 1332e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1333e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = selectRegisters(); 1334e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!ret) { 1335e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, 1336e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller "selectRegisters failed, inserting spill code ...\n"); 1337e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller regs.reset(FILE_GPR, true); 1338e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller spill.run(mustSpill); 1339e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) 1340e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller func->print(); 1341e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1342e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller prog->maxGPR = regs.getMaxAssigned(FILE_GPR); 1343e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1344e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1345e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerout: 1346e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cleanup(ret); 1347e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return ret; 1348e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1349e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1350e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1351e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::cleanup(const bool success) 1352e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1353e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mustSpill.clear(); 1354e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1355e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (ArrayList::Iterator it = func->allLValues.iterator(); 1356e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller !it.end(); it.next()) { 1357e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = reinterpret_cast<LValue *>(it.get()); 1358e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1359e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->livei.clear(); 1360e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1361e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->compound = 0; 1362e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->compMask = 0; 1363e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1364e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (lval->join == lval) 1365e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 1366e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1367e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (success) { 1368e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->reg.data.id = lval->join->reg.data.id; 1369e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1370e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end(); 1371e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++d) 1372e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->join->defs.remove(*d); 1373e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->join = lval; 137457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1375e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 137657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1377e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (success) 1378e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller resolveSplitsAndMerges(); 1379e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller splits.clear(); // avoid duplicate entries on next coalesce pass 1380e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller merges.clear(); 1381e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1382e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller delete[] nodes; 1383e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller nodes = NULL; 1384e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1385e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1386e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerSymbol * 1387e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerSpillCodeInserter::assignSlot(const Interval &livei, unsigned int size) 1388e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1389e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller SpillSlot slot; 1390e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int32_t offsetBase = stackSize; 1391e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int32_t offset; 1392e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<SpillSlot>::iterator pos = slots.end(), it = slots.begin(); 1393e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1394e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (offsetBase % size) 1395e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller offsetBase += size - (offsetBase % size); 1396e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1397e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slot.sym = NULL; 1398e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1399e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (offset = offsetBase; offset < stackSize; offset += size) { 1400e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller while (it != slots.end() && it->offset < offset) 1401e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it; 1402e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (it == slots.end()) // no slots left 1403e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1404e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller std::list<SpillSlot>::iterator bgn = it; 1405e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1406e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller while (it != slots.end() && it->offset < (offset + size)) { 1407e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it->occup.print(); 1408e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (it->occup.overlaps(livei)) 1409e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1410e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it; 1411e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1412e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (it == slots.end() || it->offset >= (offset + size)) { 1413e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // fits 1414e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (; bgn != slots.end() && bgn->offset < (offset + size); ++bgn) { 1415e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bgn->occup.insert(livei); 1416e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (bgn->size() == size) 1417e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slot.sym = bgn->sym; 141857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1419e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 142057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1421e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1422e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!slot.sym) { 1423e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller stackSize = offset + size; 1424e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slot.offset = offset; 1425e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slot.sym = new_Symbol(func->getProgram(), FILE_MEMORY_LOCAL); 1426e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!func->stackPtr) 1427e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller offset += func->tlsBase; 1428e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slot.sym->setAddress(NULL, offset); 1429e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slot.sym->reg.size = size; 1430e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slots.insert(pos, slot)->occup.insert(livei); 1431e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1432e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return slot.sym; 1433e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 143457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1435e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1436e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerSpillCodeInserter::spill(Instruction *defi, Value *slot, LValue *lval) 1437e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1438e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const DataType ty = typeOfSize(slot->reg.size); 1439e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1440e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *st; 1441e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (slot->reg.file == FILE_MEMORY_LOCAL) { 1442e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller st = new_Instruction(func, OP_STORE, ty); 1443e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller st->setSrc(0, slot); 1444e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller st->setSrc(1, lval); 1445e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->noSpill = 1; 1446e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1447e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller st = new_Instruction(func, OP_CVT, ty); 1448e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller st->setDef(0, slot); 1449e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller st->setSrc(0, lval); 1450e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1451e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller defi->bb->insertAfter(defi, st); 1452e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 145357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1454e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerLValue * 1455e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerSpillCodeInserter::unspill(Instruction *usei, LValue *lval, Value *slot) 1456e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1457e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const DataType ty = typeOfSize(slot->reg.size); 1458e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1459e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval = cloneShallow(func, lval); 146057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1461e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *ld; 1462e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (slot->reg.file == FILE_MEMORY_LOCAL) { 1463e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->noSpill = 1; 1464e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ld = new_Instruction(func, OP_LOAD, ty); 1465e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1466e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ld = new_Instruction(func, OP_CVT, ty); 1467e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1468e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ld->setDef(0, lval); 1469e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ld->setSrc(0, slot); 1470e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1471e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller usei->bb->insertBefore(usei, ld); 1472e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return lval; 1473e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1474e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1475e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerbool 1476e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerSpillCodeInserter::run(const std::list<ValuePair>& lst) 1477e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1478e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::list<ValuePair>::const_iterator it = lst.begin(); it != lst.end(); 1479e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) { 1480e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = it->first->asLValue(); 1481e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Symbol *mem = it->second ? it->second->asSym() : NULL; 1482e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1483e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end(); 1484e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++d) { 1485e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Value *slot = mem ? 1486e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller static_cast<Value *>(mem) : new_LValue(func, FILE_GPR); 1487e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Value *tmp = NULL; 1488e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *last = NULL; 1489e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1490e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *dval = (*d)->get()->asLValue(); 1491e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *defi = (*d)->getInsn(); 1492e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1493e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // handle uses first or they'll contain the spill stores 1494e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller while (!dval->uses.empty()) { 1495e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ValueRef *u = dval->uses.front(); 1496e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *usei = u->getInsn(); 1497e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(usei); 1498e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (usei->op == OP_PHI) { 1499e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller tmp = (slot->reg.file == FILE_MEMORY_LOCAL) ? NULL : slot; 1500e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller last = NULL; 1501e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 1502e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!last || usei != last->next) { // TODO: sort uses 1503e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller tmp = unspill(usei, dval, slot); 1504e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller last = usei; 1505e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1506e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller u->set(tmp); 1507e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1508e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1509e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(defi); 1510e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (defi->op == OP_PHI) { 1511e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller d = lval->defs.erase(d); 1512e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller --d; 1513e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (slot->reg.file == FILE_MEMORY_LOCAL) 1514e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller delete_Instruction(func->getProgram(), defi); 1515e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller else 1516e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller defi->setDef(0, slot); 1517e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1518e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller spill(defi, slot, dval); 151957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 152057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1521e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 152257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 152357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1524e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // TODO: We're not trying to reuse old slots in a potential next iteration. 1525e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // We have to update the slots' livei intervals to be able to do that. 1526e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller stackBase = stackSize; 1527e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller slots.clear(); 152857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 152957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 153057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 153157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 153257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::exec() 153357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 1534d32ebb8c304725fa6bb7ec2d3d40ce828c713917Francisco Jerez for (IteratorRef it = prog->calls.iteratorDFS(false); 1535d32ebb8c304725fa6bb7ec2d3d40ce828c713917Francisco Jerez !it->end(); it->next()) { 1536d32ebb8c304725fa6bb7ec2d3d40ce828c713917Francisco Jerez func = Function::get(reinterpret_cast<Graph::Node *>(it->get())); 1537e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1538e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller func->tlsBase = prog->tlsSize; 153957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!execFunc()) 154057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 1541e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller prog->tlsSize += func->tlsSize; 154257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 154357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 154457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 154557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 154657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 154757594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::execFunc() 154857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 154957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller InsertConstraintsPass insertConstr; 1550ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez PhiMovesPass insertPhiMoves; 1551ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez ArgumentMovesPass insertArgMoves; 155257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BuildIntervalsPass buildIntervals; 1553e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller SpillCodeInserter insertSpills(func); 1554e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1555e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller GCRA gcra(func, insertSpills); 155657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1557e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller unsigned int i, retries; 155857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool ret; 155957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 156057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = insertConstr.exec(func); 156157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 156257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 156357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1564ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez ret = insertPhiMoves.run(func); 1565ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez if (!ret) 1566ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez goto out; 1567ed255dbae2ada50cbdb71f6b03f4e42d3ed7ebc6Francisco Jerez 1568e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = insertArgMoves.run(func); 156957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!ret) 157057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller goto out; 157157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1572e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // TODO: need to fix up spill slot usage ranges to support > 1 retry 1573e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (retries = 0; retries < 3; ++retries) { 1574e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (retries && (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)) 1575e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO("Retry: %i\n", retries); 1576e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) 1577e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller func->print(); 1578e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1579e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // spilling to registers may add live ranges, need to rebuild everything 1580e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = true; 1581e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (sequence = func->cfg.nextSequence(), i = 0; 1582e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret && i <= func->loopNestingBound; 1583e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller sequence = func->cfg.nextSequence(), ++i) 1584e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = buildLiveSets(BasicBlock::get(func->cfg.getRoot())); 1585e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!ret) 1586e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1587e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller func->orderInstructions(this->insns); 158857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1589e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = buildIntervals.run(func); 1590e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!ret) 1591e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1592e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ret = gcra.allocateRegisters(insns); 1593e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (ret) 1594e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; // success 159557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1596e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller INFO_DBG(prog->dbgFlags, REG_ALLOC, "RegAlloc done: %i\n", ret); 159757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1598e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller func->tlsSize = insertSpills.getStackSize(); 159957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerout: 160057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ret; 160157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 160257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1603e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller// TODO: check if modifying Instruction::join here breaks anything 1604e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1605e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerGCRA::resolveSplitsAndMerges() 1606e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1607e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::list<Instruction *>::iterator it = splits.begin(); 1608e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != splits.end(); 1609e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) { 1610e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *split = *it; 1611e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller unsigned int reg = regs.idToBytes(split->getSrc(0)); 1612e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int d = 0; split->defExists(d); ++d) { 1613e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Value *v = split->getDef(d); 1614e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller v->reg.data.id = regs.bytesToId(v, reg); 1615e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller v->join = v; 1616e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller reg += v->reg.size; 1617e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1618e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1619e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller splits.clear(); 1620e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1621e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::list<Instruction *>::iterator it = merges.begin(); 1622e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != merges.end(); 1623e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) { 1624e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *merge = *it; 1625e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller unsigned int reg = regs.idToBytes(merge->getDef(0)); 1626e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int s = 0; merge->srcExists(s); ++s) { 1627e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Value *v = merge->getSrc(s); 1628e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller v->reg.data.id = regs.bytesToId(v, reg); 1629e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller v->join = v; 1630e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller reg += v->reg.size; 1631e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1632e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1633e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller merges.clear(); 1634e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1635e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 163657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool Program::registerAllocation() 163757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 163857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller RegAlloc ra(this); 163957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ra.exec(); 164057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 164157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 164257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 164357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::exec(Function *ir) 164457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 164557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller constrList.clear(); 164657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 164757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool ret = run(ir, true, true); 164857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (ret) 164957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = insertConstraintMoves(); 165057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ret; 165157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 165257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 165357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// TODO: make part of texture insn 165457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 165557594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::textureMask(TexInstruction *tex) 165657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 165757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Value *def[4]; 165857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int c, k, d; 165957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint8_t mask = 0; 166057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 166157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0, k = 0, c = 0; c < 4; ++c) { 166257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(tex->tex.mask & (1 << c))) 166357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 166457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (tex->getDef(k)->refCount()) { 166557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller mask |= 1 << c; 166657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller def[d++] = tex->getDef(k); 166757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 166857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++k; 166957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 167057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller tex->tex.mask = mask; 167157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 167257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (c = 0; c < d; ++c) 167357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller tex->setDef(c, def[c]); 167457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (; c < 4; ++c) 167557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller tex->setDef(c, NULL); 167657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 167757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 167857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 167957594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::detectConflict(Instruction *cst, int s) 168057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 16818cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez Value *v = cst->getSrc(s); 16828cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez 168357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // current register allocation can't handle it if a value participates in 168457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // multiple constraints 16858cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez for (Value::UseIterator it = v->uses.begin(); it != v->uses.end(); ++it) { 16868cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez if (cst != (*it)->getInsn()) 168757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 168857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 168957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 169057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // can start at s + 1 because detectConflict is called on all sources 169157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (int c = s + 1; cst->srcExists(c); ++c) 16928cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez if (v == cst->getSrc(c)) 169357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 169457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16958cc2eca5df0116aa7fb8233a9ab6ad1c9e4203cdFrancisco Jerez Instruction *defi = v->getInsn(); 169657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 169757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return (!defi || defi->constrainedDefs()); 169857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 169957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 170057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 170157594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::addConstraint(Instruction *i, int s, int n) 170257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 170357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *cst; 170457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int d; 170557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 170657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // first, look for an existing identical constraint op 1707e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::list<Instruction *>::iterator it = constrList.begin(); 1708e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != constrList.end(); 1709e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) { 1710e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cst = (*it); 171157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!i->bb->dominatedBy(cst->bb)) 171257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 171357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0; d < n; ++d) 171457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (cst->getSrc(d) != i->getSrc(d + s)) 171557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; 171657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (d >= n) { 171757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0; d < n; ++d, ++s) 171857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->setSrc(s, cst->getDef(d)); 171957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return; 172057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 172157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 172257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst = new_Instruction(func, OP_CONSTRAINT, i->dType); 172357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 172457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (d = 0; d < n; ++s, ++d) { 172557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst->setDef(d, new_LValue(func, FILE_GPR)); 172657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller cst->setSrc(d, i->getSrc(s)); 172757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->setSrc(s, cst->getDef(d)); 172857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 172957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->bb->insertBefore(i, cst); 173057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1731e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller constrList.push_back(cst); 173257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 173357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 173457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Add a dummy use of the pointer source of >= 8 byte loads after the load 173557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// to prevent it from being assigned a register which overlapping the load's 173657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// destination, which would produce random corruptions. 173757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 173857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::addHazard(Instruction *i, const ValueRef *src) 173957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 174057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *hzd = new_Instruction(func, OP_NOP, TYPE_NONE); 174157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller hzd->setSrc(0, src->get()); 174257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller i->bb->insertAfter(i, hzd); 174357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 174457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 174557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1746e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller// b32 { %r0 %r1 %r2 %r3 } -> b128 %r0q 1747e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1748e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegAlloc::InsertConstraintsPass::condenseDefs(Instruction *insn) 1749e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1750e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint8_t size = 0; 1751e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int n; 1752e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (n = 0; insn->defExists(n) && insn->def(n).getFile() == FILE_GPR; ++n) 1753e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller size += insn->getDef(n)->reg.size; 1754e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (n < 2) 1755e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return; 1756e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = new_LValue(func, FILE_GPR); 1757e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->reg.size = size; 1758e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1759e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *split = new_Instruction(func, OP_SPLIT, typeOfSize(size)); 1760e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller split->setSrc(0, lval); 1761e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int d = 0; d < n; ++d) { 1762e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller split->setDef(d, insn->getDef(d)); 1763e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->setDef(d, NULL); 1764e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1765e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->setDef(0, lval); 1766e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1767e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int k = 1, d = n; insn->defExists(d); ++d, ++k) { 1768e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->setDef(k, insn->getDef(d)); 1769e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->setDef(d, NULL); 1770e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1771e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // carry over predicate if any (mainly for OP_UNION uses) 1772e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller split->setPredicate(insn->cc, insn->getPredicate()); 1773e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1774e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->bb->insertAfter(insn, split); 1775e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller constrList.push_back(split); 1776e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1777e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1778e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegAlloc::InsertConstraintsPass::condenseSrcs(Instruction *insn, 1779e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const int a, const int b) 1780e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1781e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint8_t size = 0; 1782e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (a >= b) 1783e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return; 1784e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int s = a; s <= b; ++s) 1785e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller size += insn->getSrc(s)->reg.size; 1786e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!size) 1787e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return; 1788e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = new_LValue(func, FILE_GPR); 1789e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->reg.size = size; 1790e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1791e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Value *save[3]; 1792e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->takeExtraSources(0, save); 1793e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1794e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *merge = new_Instruction(func, OP_MERGE, typeOfSize(size)); 1795e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller merge->setDef(0, lval); 1796e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int s = a, i = 0; s <= b; ++s, ++i) { 1797e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller merge->setSrc(i, insn->getSrc(s)); 1798e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->setSrc(s, NULL); 1799e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1800e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->setSrc(a, lval); 1801e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1802e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int k = a + 1, s = b + 1; insn->srcExists(s); ++s, ++k) { 1803e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->setSrc(k, insn->getSrc(s)); 1804e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->setSrc(s, NULL); 1805e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1806e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->bb->insertBefore(insn, merge); 1807e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1808e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller insn->putExtraSources(0, save); 1809e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1810e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller constrList.push_back(merge); 1811e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1812e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1813e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1814e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegAlloc::InsertConstraintsPass::texConstraintNVE0(TexInstruction *tex) 1815e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1816e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller textureMask(tex); 1817e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseDefs(tex); 1818e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1819e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int n = tex->srcCount(0xff, true); 1820e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (n > 4) { 1821e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseSrcs(tex, 0, 3); 182238a20281fcc2ed244aea0aaa268035533f48a183Christoph Bumiller if (n > 5) // NOTE: first call modified positions already 182338a20281fcc2ed244aea0aaa268035533f48a183Christoph Bumiller condenseSrcs(tex, 4 - (4 - 1), n - 1 - (4 - 1)); 1824e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 1825e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (n > 1) { 1826e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseSrcs(tex, 0, n - 1); 1827e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1828e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1829e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1830e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1831e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegAlloc::InsertConstraintsPass::texConstraintNVC0(TexInstruction *tex) 1832e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1833e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int n, s; 1834e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1835e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller textureMask(tex); 1836e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1837e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (tex->op == OP_TXQ) { 1838e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller s = tex->srcCount(0xff); 1839e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller n = 0; 1840e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 1841e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller s = tex->tex.target.getArgCount(); 1842e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!tex->tex.target.isArray() && 1843e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller (tex->tex.rIndirectSrc >= 0 || tex->tex.sIndirectSrc >= 0)) 1844e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++s; 1845e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (tex->op == OP_TXD && tex->tex.useOffsets) 1846e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++s; 1847e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller n = tex->srcCount(0xff) - s; 1848e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(n <= 4); 1849e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1850e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1851e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (s > 1) 1852e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseSrcs(tex, 0, s - 1); 185338a20281fcc2ed244aea0aaa268035533f48a183Christoph Bumiller if (n > 1) // NOTE: first call modified positions already 185438a20281fcc2ed244aea0aaa268035533f48a183Christoph Bumiller condenseSrcs(tex, 1, n); 1855e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1856e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseDefs(tex); 1857e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1858e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1859e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid 1860e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerRegAlloc::InsertConstraintsPass::texConstraintNV50(TexInstruction *tex) 1861e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 1862e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Value *pred = tex->getPredicate(); 1863e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (pred) 1864e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller tex->setPredicate(tex->cc, NULL); 1865e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1866e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller textureMask(tex); 1867e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1868e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(tex->defExists(0) && tex->srcExists(0)); 1869e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // make src and def count match 1870e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int c; 1871e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (c = 0; tex->srcExists(c) || tex->defExists(c); ++c) { 1872e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!tex->srcExists(c)) 1873e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller tex->setSrc(c, new_LValue(func, tex->getSrc(0)->asLValue())); 1874e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!tex->defExists(c)) 1875e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller tex->setDef(c, new_LValue(func, tex->getDef(0)->asLValue())); 1876e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1877e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (pred) 1878e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller tex->setPredicate(tex->cc, pred); 1879e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseDefs(tex); 1880e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseSrcs(tex, 0, c - 1); 1881e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 1882e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 188357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Insert constraint markers for instructions whose multiple sources must be 188457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// located in consecutive registers. 188557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 188657594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::visit(BasicBlock *bb) 188757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 188857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller TexInstruction *tex; 188957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Instruction *next; 1890e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int s, size; 1891e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1892e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller targ = bb->getProgram()->getTarget(); 189357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 189457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Instruction *i = bb->getEntry(); i; i = next) { 189557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = i->next; 189657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 189757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if ((tex = i->asTex())) { 1898e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller switch (targ->getChipset() & ~0xf) { 1899e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0x50: 1900e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0x80: 1901e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0x90: 1902e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0xa0: 1903e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller texConstraintNV50(tex); 1904e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1905e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0xc0: 1906e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0xd0: 1907e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller texConstraintNVC0(tex); 1908e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1909e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller case 0xe0: 1910e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller texConstraintNVE0(tex); 1911e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 1912e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller default: 1913e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 191457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 191557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 191657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i->op == OP_EXPORT || i->op == OP_STORE) { 191757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (size = typeSizeof(i->dType), s = 1; size > 0; ++s) { 191857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i->srcExists(s)); 191957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size -= i->getSrc(s)->reg.size; 192057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1921e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseSrcs(i, 1, s - 1); 192257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else 1923e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (i->op == OP_LOAD || i->op == OP_VFETCH) { 1924e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller condenseDefs(i); 19259362d4bc0a03860ec386156cf499e855a9c2d2a5Christoph Bumiller if (i->src(0).isIndirect(0) && typeSizeof(i->dType) >= 8) 19269362d4bc0a03860ec386156cf499e855a9c2d2a5Christoph Bumiller addHazard(i, i->src(0).getIndirect(0)); 1927e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 1928e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (i->op == OP_UNION) { 1929e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller constrList.push_back(i); 193057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 193157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 193257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 193357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 193457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 193557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// Insert extra moves so that, if multiple register constraints on a value are 193657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// in conflict, these conflicts can be resolved. 193757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 193857594065c30feec9376be9b2132659f7d87362eeChristoph BumillerRegAlloc::InsertConstraintsPass::insertConstraintMoves() 193957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 1940e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (std::list<Instruction *>::iterator it = constrList.begin(); 1941e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller it != constrList.end(); 1942e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller ++it) { 1943e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *cst = *it; 1944e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *mov; 1945e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1946e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (cst->op == OP_SPLIT && 0) { 1947e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // spilling splits is annoying, just make sure they're separate 1948e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int d = 0; cst->defExists(d); ++d) { 1949e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!cst->getDef(d)->refCount()) 1950e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 1951e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = new_LValue(func, cst->def(d).getFile()); 1952e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const uint8_t size = cst->def(d).getSize(); 1953e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->reg.size = size; 1954e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1955e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov = new_Instruction(func, OP_MOV, typeOfSize(size)); 1956e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov->setSrc(0, lval); 1957e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov->setDef(0, cst->getDef(d)); 1958e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cst->setDef(d, mov->getSrc(0)); 1959e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cst->bb->insertAfter(cst, mov); 1960e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1961e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cst->getSrc(0)->asLValue()->noSpill = 1; 1962e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov->getSrc(0)->asLValue()->noSpill = 1; 1963e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1964e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 1965e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (cst->op == OP_MERGE || cst->op == OP_UNION) { 1966e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (int s = 0; cst->srcExists(s); ++s) { 1967e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const uint8_t size = cst->src(s).getSize(); 1968e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1969e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!cst->getSrc(s)->defs.size()) { 1970e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov = new_Instruction(func, OP_NOP, typeOfSize(size)); 1971e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov->setDef(0, cst->getSrc(s)); 1972e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cst->bb->insertBefore(cst, mov); 1973e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 1974e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 1975e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(cst->getSrc(s)->defs.size() == 1); // still SSA 1976e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1977e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Instruction *defi = cst->getSrc(s)->defs.front()->getInsn(); 1978e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // catch some cases where don't really need MOVs 1979e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (cst->getSrc(s)->refCount() == 1 && !defi->constrainedDefs()) 1980e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller continue; 1981e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1982e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller LValue *lval = new_LValue(func, cst->src(s).getFile()); 1983e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller lval->reg.size = size; 198457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1985e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov = new_Instruction(func, OP_MOV, typeOfSize(size)); 1986e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov->setDef(0, lval); 1987e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov->setSrc(0, cst->getSrc(s)); 1988e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cst->setSrc(s, mov->getDef(0)); 1989e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cst->bb->insertBefore(cst, mov); 199057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 1991e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller cst->getDef(0)->asLValue()->noSpill = 1; // doesn't help 1992e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 1993e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (cst->op == OP_UNION) 1994e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller mov->setPredicate(defi->cc, defi->getPredicate()); 1995e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 199657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 199757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 1998e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 199957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 200057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 200157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 200257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} // namespace nv50_ir 2003