10d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt/* 20d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * Copyright © 2012 Intel Corporation 30d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 40d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * Permission is hereby granted, free of charge, to any person obtaining a 50d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * copy of this software and associated documentation files (the "Software"), 60d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * to deal in the Software without restriction, including without limitation 70d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * the rights to use, copy, modify, merge, publish, distribute, sublicense, 80d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * and/or sell copies of the Software, and to permit persons to whom the 90d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * Software is furnished to do so, subject to the following conditions: 100d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 110d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * The above copyright notice and this permission notice (including the next 120d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * paragraph) shall be included in all copies or substantial portions of the 130d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * Software. 140d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 150d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 160d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 170d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 180d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 190d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 200d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 210d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * IN THE SOFTWARE. 220d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 230d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * Authors: 240d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * Eric Anholt <eric@anholt.net> 250d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 260d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt */ 270d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 285ed57d9543df1875d843638212a1f650fc0b17ecEric Anholt#include "brw_cfg.h" 290d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt#include "brw_fs_live_variables.h" 300d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 310d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholtusing namespace brw; 320d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 33398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt#define MAX_INSTRUCTION (1 << 30) 34398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt 350d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt/** @file brw_fs_live_variables.cpp 360d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 3745ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * Support for calculating liveness information about virtual GRFs. 3845ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * 3945ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * This produces a live interval for each whole virtual GRF. We could 4045ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * choose to expose per-component live intervals for VGRFs of size > 1, 4145ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * but we currently do not. It is easier for the consumers of this 4245ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * information to work with whole VGRFs. 4345ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * 44eb746a80e5e99bafd3957a1cb2d9db8548a1a6beFrancisco Jerez * However, we internally track use/def information at the per-GRF level for 45eb746a80e5e99bafd3957a1cb2d9db8548a1a6beFrancisco Jerez * greater accuracy. Large VGRFs may be accessed piecemeal over many 46eb746a80e5e99bafd3957a1cb2d9db8548a1a6beFrancisco Jerez * (possibly non-adjacent) instructions. In this case, examining a single 47eb746a80e5e99bafd3957a1cb2d9db8548a1a6beFrancisco Jerez * instruction is insufficient to decide whether a whole VGRF is ultimately 48eb746a80e5e99bafd3957a1cb2d9db8548a1a6beFrancisco Jerez * used or defined. Tracking individual components allows us to easily 49eb746a80e5e99bafd3957a1cb2d9db8548a1a6beFrancisco Jerez * assemble this information. 500d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 51503fe278b070285b75a4000408873973d8d5f2b1Matt Turner * See Muchnick's Advanced Compiler Design and Implementation, section 520d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 14.1 (p444). 530d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt */ 540d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 55097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholtvoid 5613f660158573846d6b1bc30ed4c61d97405bea58Matt Turnerfs_live_variables::setup_one_read(struct block_data *bd, fs_inst *inst, 57b37273b92431a2d986235774f04a9fba2aa1bf74Matt Turner int ip, const fs_reg ®) 58097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt{ 59b37273b92431a2d986235774f04a9fba2aa1bf74Matt Turner int var = var_from_reg(reg); 6078fa6172e11159a32fc5bb222965fd53eb39976eMatt Turner assert(var < num_vars); 61097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt 62398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt start[var] = MIN2(start[var], ip); 6383dedb6354d0e9b04e8ccad77e86bdb7bad44bddKenneth Graunke end[var] = MAX2(end[var], ip); 64398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt 65097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt /* The use[] bitset marks when the block makes use of a variable (VGRF 66097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt * channel) without having completely defined that variable within the 67097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt * block. 68097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt */ 6913f660158573846d6b1bc30ed4c61d97405bea58Matt Turner if (!BITSET_TEST(bd->def, var)) 7013f660158573846d6b1bc30ed4c61d97405bea58Matt Turner BITSET_SET(bd->use, var); 71097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt} 72097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt 73097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholtvoid 7413f660158573846d6b1bc30ed4c61d97405bea58Matt Turnerfs_live_variables::setup_one_write(struct block_data *bd, fs_inst *inst, 75b37273b92431a2d986235774f04a9fba2aa1bf74Matt Turner int ip, const fs_reg ®) 76097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt{ 77b37273b92431a2d986235774f04a9fba2aa1bf74Matt Turner int var = var_from_reg(reg); 7878fa6172e11159a32fc5bb222965fd53eb39976eMatt Turner assert(var < num_vars); 79097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt 80398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt start[var] = MIN2(start[var], ip); 81398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt end[var] = MAX2(end[var], ip); 82398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt 83097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt /* The def[] bitset marks when an initialization in a block completely 84097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt * screens off previous updates of that variable (VGRF channel). 85097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt */ 86b163aa01487ab5f9b22c48b7badc5d65999c4985Matt Turner if (inst->dst.file == VGRF && !inst->is_partial_write()) { 8713f660158573846d6b1bc30ed4c61d97405bea58Matt Turner if (!BITSET_TEST(bd->use, var)) 8813f660158573846d6b1bc30ed4c61d97405bea58Matt Turner BITSET_SET(bd->def, var); 89097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt } 90097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt} 91097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt 920d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt/** 93f179f419d1d0a03fad36c2b0a58e8b853bae6118Eric Anholt * Sets up the use[] and def[] bitsets. 940d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * 950d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * The basic-block-level live variable analysis needs to know which 960d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * variables get used before they're completely defined, and which 970d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * variables are completely defined before they're used. 9845ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * 9945ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * These are tracked at the per-component level, rather than whole VGRFs. 1000d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt */ 1010d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholtvoid 1020d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholtfs_live_variables::setup_def_use() 1030d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt{ 1040d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt int ip = 0; 1050d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 106596990d91e2a4c4a3a303c6c2da623bf1840771bMatt Turner foreach_block (block, cfg) { 1070d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt assert(ip == block->start_ip); 108596990d91e2a4c4a3a303c6c2da623bf1840771bMatt Turner if (block->num > 0) 109596990d91e2a4c4a3a303c6c2da623bf1840771bMatt Turner assert(cfg->blocks[block->num - 1]->end_ip == ip - 1); 1100d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 11113f660158573846d6b1bc30ed4c61d97405bea58Matt Turner struct block_data *bd = &block_data[block->num]; 11213f660158573846d6b1bc30ed4c61d97405bea58Matt Turner 113bc2fbbafd216676ccc7c3abd794ecb7dd1fa631fMatt Turner foreach_inst_in_block(fs_inst, inst, block) { 1140d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt /* Set use[] for this instruction */ 115b1dcdcde2e323f960833f5c7da65d5c2c20113c9Matt Turner for (unsigned int i = 0; i < inst->sources; i++) { 116097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt fs_reg reg = inst->src[i]; 117097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt 118b163aa01487ab5f9b22c48b7badc5d65999c4985Matt Turner if (reg.file != VGRF) 119701e9af15f9cedd8c1dbad417d195ee2a46e07bfKenneth Graunke continue; 1200d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 121c458eeb94620fbce0a37474fc292545002d67f76Francisco Jerez for (unsigned j = 0; j < regs_read(inst, i); j++) { 12213f660158573846d6b1bc30ed4c61d97405bea58Matt Turner setup_one_read(bd, inst, ip, reg); 12386944e063ad40cac0860bfd85a3cc4e9a9805aa3Francisco Jerez reg.offset += REG_SIZE; 12445ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt } 1250d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 1260fec265373f269d116f6d4de900b208fffabe2a1Francisco Jerez 1270fec265373f269d116f6d4de900b208fffabe2a1Francisco Jerez bd->flag_use[0] |= inst->flags_read(v->devinfo) & ~bd->flag_def[0]; 1280d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 129097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt /* Set def[] for this instruction */ 130b163aa01487ab5f9b22c48b7badc5d65999c4985Matt Turner if (inst->dst.file == VGRF) { 131097bf101c33ee14e4e163523dc4e4e0fbca9f051Eric Anholt fs_reg reg = inst->dst; 132c458eeb94620fbce0a37474fc292545002d67f76Francisco Jerez for (unsigned j = 0; j < regs_written(inst); j++) { 13313f660158573846d6b1bc30ed4c61d97405bea58Matt Turner setup_one_write(bd, inst, ip, reg); 13486944e063ad40cac0860bfd85a3cc4e9a9805aa3Francisco Jerez reg.offset += REG_SIZE; 13545ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt } 1360d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 1370fec265373f269d116f6d4de900b208fffabe2a1Francisco Jerez 1380fec265373f269d116f6d4de900b208fffabe2a1Francisco Jerez if (!inst->predicate && inst->exec_size >= 8) 1390fec265373f269d116f6d4de900b208fffabe2a1Francisco Jerez bd->flag_def[0] |= inst->flags_written() & ~bd->flag_use[0]; 1400d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 1410d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt ip++; 1420d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 1430d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 1440d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt} 1450d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 1460d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt/** 1470d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * The algorithm incrementally sets bits in liveout and livein, 1480d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * propagating it through control flow. It will eventually terminate 1490d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * because it only ever adds bits, and stops when no bits are added in 1500d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt * a pass. 1510d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt */ 1520d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholtvoid 1530d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholtfs_live_variables::compute_live_variables() 1540d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt{ 1550d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt bool cont = true; 1560d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 1570d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt while (cont) { 1580d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt cont = false; 1590d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 160b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand foreach_block_reverse (block, cfg) { 16113f660158573846d6b1bc30ed4c61d97405bea58Matt Turner struct block_data *bd = &block_data[block->num]; 16213f660158573846d6b1bc30ed4c61d97405bea58Matt Turner 1630d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt /* Update liveout */ 164596990d91e2a4c4a3a303c6c2da623bf1840771bMatt Turner foreach_list_typed(bblock_link, child_link, link, &block->children) { 16513f660158573846d6b1bc30ed4c61d97405bea58Matt Turner struct block_data *child_bd = &block_data[child_link->block->num]; 1660d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 167f179f419d1d0a03fad36c2b0a58e8b853bae6118Eric Anholt for (int i = 0; i < bitset_words; i++) { 16813f660158573846d6b1bc30ed4c61d97405bea58Matt Turner BITSET_WORD new_liveout = (child_bd->livein[i] & 16913f660158573846d6b1bc30ed4c61d97405bea58Matt Turner ~bd->liveout[i]); 170f179f419d1d0a03fad36c2b0a58e8b853bae6118Eric Anholt if (new_liveout) { 17113f660158573846d6b1bc30ed4c61d97405bea58Matt Turner bd->liveout[i] |= new_liveout; 172f179f419d1d0a03fad36c2b0a58e8b853bae6118Eric Anholt cont = true; 173f179f419d1d0a03fad36c2b0a58e8b853bae6118Eric Anholt } 1740d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 175bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner BITSET_WORD new_liveout = (child_bd->flag_livein[0] & 176bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner ~bd->flag_liveout[0]); 177bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner if (new_liveout) { 178bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner bd->flag_liveout[0] |= new_liveout; 179bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner cont = true; 180bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner } 1810d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 182b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand 183b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand /* Update livein */ 184b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand for (int i = 0; i < bitset_words; i++) { 185b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand BITSET_WORD new_livein = (bd->use[i] | 186b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand (bd->liveout[i] & 187b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand ~bd->def[i])); 188b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand if (new_livein & ~bd->livein[i]) { 189b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand bd->livein[i] |= new_livein; 190b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand cont = true; 191b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand } 192b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand } 193b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand BITSET_WORD new_livein = (bd->flag_use[0] | 194b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand (bd->flag_liveout[0] & 195b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand ~bd->flag_def[0])); 196b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand if (new_livein & ~bd->flag_livein[0]) { 197b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand bd->flag_livein[0] |= new_livein; 198b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand cont = true; 199b2c6ba0c4b21391dc35018e1c8c4f7f7d8952beaJason Ekstrand } 2000d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 2010d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 2020d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt} 2030d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 204398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt/** 205398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt * Extend the start/end ranges for each variable to account for the 206398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt * new information calculated from control flow. 207398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt */ 208398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholtvoid 209398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholtfs_live_variables::compute_start_end() 210398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt{ 211596990d91e2a4c4a3a303c6c2da623bf1840771bMatt Turner foreach_block (block, cfg) { 21213f660158573846d6b1bc30ed4c61d97405bea58Matt Turner struct block_data *bd = &block_data[block->num]; 21313f660158573846d6b1bc30ed4c61d97405bea58Matt Turner 214398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt for (int i = 0; i < num_vars; i++) { 2159d2bbca98d2712f7bafe66cb3bc08859ff14133eIago Toral Quiroga if (BITSET_TEST(bd->livein, i)) { 2169d2bbca98d2712f7bafe66cb3bc08859ff14133eIago Toral Quiroga start[i] = MIN2(start[i], block->start_ip); 2179d2bbca98d2712f7bafe66cb3bc08859ff14133eIago Toral Quiroga end[i] = MAX2(end[i], block->start_ip); 2189d2bbca98d2712f7bafe66cb3bc08859ff14133eIago Toral Quiroga } 219398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt 2209d2bbca98d2712f7bafe66cb3bc08859ff14133eIago Toral Quiroga if (BITSET_TEST(bd->liveout, i)) { 2219d2bbca98d2712f7bafe66cb3bc08859ff14133eIago Toral Quiroga start[i] = MIN2(start[i], block->end_ip); 2229d2bbca98d2712f7bafe66cb3bc08859ff14133eIago Toral Quiroga end[i] = MAX2(end[i], block->end_ip); 2239d2bbca98d2712f7bafe66cb3bc08859ff14133eIago Toral Quiroga } 224398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt } 225398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt } 226398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt} 227398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt 2282e90d1fb62a6ef53c15eff76e242c510145178a9Matt Turnerfs_live_variables::fs_live_variables(fs_visitor *v, const cfg_t *cfg) 2290d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt : v(v), cfg(cfg) 2300d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt{ 231db47074ac02e2b822dd118f4837b32732941b78bFrancisco Jerez mem_ctx = ralloc_context(NULL); 2320d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 233447879eb88b8df41ad32cf4406cc636b112b72d9Francisco Jerez num_vgrfs = v->alloc.count; 23445ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt num_vars = 0; 23545ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt var_from_vgrf = rzalloc_array(mem_ctx, int, num_vgrfs); 23645ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt for (int i = 0; i < num_vgrfs; i++) { 23745ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt var_from_vgrf[i] = num_vars; 238447879eb88b8df41ad32cf4406cc636b112b72d9Francisco Jerez num_vars += v->alloc.sizes[i]; 23945ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt } 24045ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt 24145ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt vgrf_from_var = rzalloc_array(mem_ctx, int, num_vars); 24245ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt for (int i = 0; i < num_vgrfs; i++) { 243447879eb88b8df41ad32cf4406cc636b112b72d9Francisco Jerez for (unsigned j = 0; j < v->alloc.sizes[i]; j++) { 24445ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt vgrf_from_var[var_from_vgrf[i] + j] = i; 24545ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt } 24645ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt } 24745ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt 248398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt start = ralloc_array(mem_ctx, int, num_vars); 249398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt end = rzalloc_array(mem_ctx, int, num_vars); 250398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt for (int i = 0; i < num_vars; i++) { 251398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt start[i] = MAX_INSTRUCTION; 252398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt end[i] = -1; 253398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt } 254398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt 25513f660158573846d6b1bc30ed4c61d97405bea58Matt Turner block_data= rzalloc_array(mem_ctx, struct block_data, cfg->num_blocks); 2560d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 25745ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt bitset_words = BITSET_WORDS(num_vars); 2580d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt for (int i = 0; i < cfg->num_blocks; i++) { 25913f660158573846d6b1bc30ed4c61d97405bea58Matt Turner block_data[i].def = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words); 26013f660158573846d6b1bc30ed4c61d97405bea58Matt Turner block_data[i].use = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words); 26113f660158573846d6b1bc30ed4c61d97405bea58Matt Turner block_data[i].livein = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words); 26213f660158573846d6b1bc30ed4c61d97405bea58Matt Turner block_data[i].liveout = rzalloc_array(mem_ctx, BITSET_WORD, bitset_words); 263bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner 264bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner block_data[i].flag_def[0] = 0; 265bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner block_data[i].flag_use[0] = 0; 266bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner block_data[i].flag_livein[0] = 0; 267bf8deb55146696b2332d9ea29f6242d236e1b46aMatt Turner block_data[i].flag_liveout[0] = 0; 2680d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt } 2690d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 2700d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt setup_def_use(); 2710d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt compute_live_variables(); 272398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt compute_start_end(); 2730d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt} 2740d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt 2750d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholtfs_live_variables::~fs_live_variables() 2760d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt{ 2770d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt ralloc_free(mem_ctx); 2780d6c96a5c34de3ffdd6167282d7520dfd3c863cbEric Anholt} 27934b17ee598e855e1090a455c2dac31ed8104954bEric Anholt 2804b821a97b5fcdc4c530d5455c43196be09830322Kenneth Graunkevoid 281072ea414d04f1b9a7bf06a00b9011e8ad521c878Matt Turnerfs_visitor::invalidate_live_intervals() 2824b821a97b5fcdc4c530d5455c43196be09830322Kenneth Graunke{ 283b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt ralloc_free(live_intervals); 284b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt live_intervals = NULL; 2854b821a97b5fcdc4c530d5455c43196be09830322Kenneth Graunke} 2864b821a97b5fcdc4c530d5455c43196be09830322Kenneth Graunke 28745ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt/** 28845ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * Compute the live intervals for each virtual GRF. 28945ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * 29045ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * This uses the per-component use/def data, but combines it to produce 29145ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt * information about whole VGRFs. 29245ffaeccaf412f322605a7c7488c6ab0d85fc4b6Eric Anholt */ 29334b17ee598e855e1090a455c2dac31ed8104954bEric Anholtvoid 294680fe0acb3e6569f7b9aab1913e9181d5a7eee2fMatt Turnerfs_visitor::calculate_live_intervals() 29534b17ee598e855e1090a455c2dac31ed8104954bEric Anholt{ 296b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt if (this->live_intervals) 29734b17ee598e855e1090a455c2dac31ed8104954bEric Anholt return; 29834b17ee598e855e1090a455c2dac31ed8104954bEric Anholt 299447879eb88b8df41ad32cf4406cc636b112b72d9Francisco Jerez int num_vgrfs = this->alloc.count; 300e290372542d0475e612e4d10a27b22eae3158ecdEric Anholt ralloc_free(this->virtual_grf_start); 301e290372542d0475e612e4d10a27b22eae3158ecdEric Anholt ralloc_free(this->virtual_grf_end); 302939b0f2c2ff41869fce8c99986607f5daf67b63aKenneth Graunke virtual_grf_start = ralloc_array(mem_ctx, int, num_vgrfs); 303939b0f2c2ff41869fce8c99986607f5daf67b63aKenneth Graunke virtual_grf_end = ralloc_array(mem_ctx, int, num_vgrfs); 304f7a71e2570053205eb603aa04b8c52d4f54d8e4cEric Anholt 3055af8388110595f6324d697f0b468047c779f1079Kenneth Graunke for (int i = 0; i < num_vgrfs; i++) { 306939b0f2c2ff41869fce8c99986607f5daf67b63aKenneth Graunke virtual_grf_start[i] = MAX_INSTRUCTION; 307939b0f2c2ff41869fce8c99986607f5daf67b63aKenneth Graunke virtual_grf_end[i] = -1; 30834b17ee598e855e1090a455c2dac31ed8104954bEric Anholt } 30934b17ee598e855e1090a455c2dac31ed8104954bEric Anholt 310680fe0acb3e6569f7b9aab1913e9181d5a7eee2fMatt Turner this->live_intervals = new(mem_ctx) fs_live_variables(this, cfg); 311137c5ece7d22bcbb017e52f00273b42a191f496dEric Anholt 312398656d97e8e554623f43eca31dc6a0cbf22979dEric Anholt /* Merge the per-component live ranges to whole VGRF live ranges. */ 313b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt for (int i = 0; i < live_intervals->num_vars; i++) { 314b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt int vgrf = live_intervals->vgrf_from_var[i]; 315b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt virtual_grf_start[vgrf] = MIN2(virtual_grf_start[vgrf], 316b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt live_intervals->start[i]); 317b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt virtual_grf_end[vgrf] = MAX2(virtual_grf_end[vgrf], 318b4d676d71006e5e85893d7b44740860b1b2c3425Eric Anholt live_intervals->end[i]); 319137c5ece7d22bcbb017e52f00273b42a191f496dEric Anholt } 32034b17ee598e855e1090a455c2dac31ed8104954bEric Anholt} 32134b17ee598e855e1090a455c2dac31ed8104954bEric Anholt 32234b17ee598e855e1090a455c2dac31ed8104954bEric Anholtbool 323b6af650a095034eaa2de93bf6cf2985d7fdfce89Eric Anholtfs_live_variables::vars_interfere(int a, int b) 324b6af650a095034eaa2de93bf6cf2985d7fdfce89Eric Anholt{ 325b6af650a095034eaa2de93bf6cf2985d7fdfce89Eric Anholt return !(end[b] <= start[a] || 326b6af650a095034eaa2de93bf6cf2985d7fdfce89Eric Anholt end[a] <= start[b]); 327b6af650a095034eaa2de93bf6cf2985d7fdfce89Eric Anholt} 328b6af650a095034eaa2de93bf6cf2985d7fdfce89Eric Anholt 329b6af650a095034eaa2de93bf6cf2985d7fdfce89Eric Anholtbool 33034b17ee598e855e1090a455c2dac31ed8104954bEric Anholtfs_visitor::virtual_grf_interferes(int a, int b) 33134b17ee598e855e1090a455c2dac31ed8104954bEric Anholt{ 332e290372542d0475e612e4d10a27b22eae3158ecdEric Anholt return !(virtual_grf_end[a] <= virtual_grf_start[b] || 333e290372542d0475e612e4d10a27b22eae3158ecdEric Anholt virtual_grf_end[b] <= virtual_grf_start[a]); 33434b17ee598e855e1090a455c2dac31ed8104954bEric Anholt} 335