1f34f39330bb41fb0a86930908de10353193a841dMatt Turner/* 2f34f39330bb41fb0a86930908de10353193a841dMatt Turner * Copyright © 2014 Intel Corporation 3f34f39330bb41fb0a86930908de10353193a841dMatt Turner * 4f34f39330bb41fb0a86930908de10353193a841dMatt Turner * Permission is hereby granted, free of charge, to any person obtaining a 5f34f39330bb41fb0a86930908de10353193a841dMatt Turner * copy of this software and associated documentation files (the "Software"), 6f34f39330bb41fb0a86930908de10353193a841dMatt Turner * to deal in the Software without restriction, including without limitation 7f34f39330bb41fb0a86930908de10353193a841dMatt Turner * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8f34f39330bb41fb0a86930908de10353193a841dMatt Turner * and/or sell copies of the Software, and to permit persons to whom the 9f34f39330bb41fb0a86930908de10353193a841dMatt Turner * Software is furnished to do so, subject to the following conditions: 10f34f39330bb41fb0a86930908de10353193a841dMatt Turner * 11f34f39330bb41fb0a86930908de10353193a841dMatt Turner * The above copyright notice and this permission notice (including the next 12f34f39330bb41fb0a86930908de10353193a841dMatt Turner * paragraph) shall be included in all copies or substantial portions of the 13f34f39330bb41fb0a86930908de10353193a841dMatt Turner * Software. 14f34f39330bb41fb0a86930908de10353193a841dMatt Turner * 15f34f39330bb41fb0a86930908de10353193a841dMatt Turner * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16f34f39330bb41fb0a86930908de10353193a841dMatt Turner * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17f34f39330bb41fb0a86930908de10353193a841dMatt Turner * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18f34f39330bb41fb0a86930908de10353193a841dMatt Turner * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19f34f39330bb41fb0a86930908de10353193a841dMatt Turner * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20f34f39330bb41fb0a86930908de10353193a841dMatt Turner * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21f34f39330bb41fb0a86930908de10353193a841dMatt Turner * IN THE SOFTWARE. 22f34f39330bb41fb0a86930908de10353193a841dMatt Turner */ 23f34f39330bb41fb0a86930908de10353193a841dMatt Turner 24f34f39330bb41fb0a86930908de10353193a841dMatt Turner#include "brw_fs.h" 25f34f39330bb41fb0a86930908de10353193a841dMatt Turner#include "brw_fs_live_variables.h" 26f34f39330bb41fb0a86930908de10353193a841dMatt Turner#include "brw_cfg.h" 27f34f39330bb41fb0a86930908de10353193a841dMatt Turner 28f34f39330bb41fb0a86930908de10353193a841dMatt Turner/** @file brw_fs_dead_code_eliminate.cpp 29f34f39330bb41fb0a86930908de10353193a841dMatt Turner * 30f34f39330bb41fb0a86930908de10353193a841dMatt Turner * Dataflow-aware dead code elimination. 31f34f39330bb41fb0a86930908de10353193a841dMatt Turner * 32f34f39330bb41fb0a86930908de10353193a841dMatt Turner * Walks the instruction list from the bottom, removing instructions that 33f34f39330bb41fb0a86930908de10353193a841dMatt Turner * have results that both aren't used in later blocks and haven't been read 34f34f39330bb41fb0a86930908de10353193a841dMatt Turner * yet in the tail end of this block. 35f34f39330bb41fb0a86930908de10353193a841dMatt Turner */ 36f34f39330bb41fb0a86930908de10353193a841dMatt Turner 379919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke/** 389919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke * Is it safe to eliminate the instruction? 399919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke */ 409919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunkestatic bool 419919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunkecan_eliminate(const fs_inst *inst, BITSET_WORD *flag_live) 429919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke{ 439919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke return !inst->is_control_flow() && 449919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke !inst->has_side_effects() && 459919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke !(flag_live[0] & inst->flags_written()) && 469919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke !inst->writes_accumulator; 479919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke} 489919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke 499919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke/** 509919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke * Is it safe to omit the write, making the destination ARF null? 519919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke */ 529919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunkestatic bool 539919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunkecan_omit_write(const fs_inst *inst) 549919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke{ 559919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke switch (inst->opcode) { 569919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke case SHADER_OPCODE_UNTYPED_ATOMIC: 579919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke case SHADER_OPCODE_UNTYPED_ATOMIC_LOGICAL: 589919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke case SHADER_OPCODE_TYPED_ATOMIC: 599919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke case SHADER_OPCODE_TYPED_ATOMIC_LOGICAL: 609919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke return true; 619919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke default: 629919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke /* We can eliminate the destination write for ordinary instructions, 639919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke * but not most SENDs. 649919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke */ 659919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke if (inst->opcode < 128 && inst->mlen == 0) 669919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke return true; 679919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke 689919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke /* It might not be safe for other virtual opcodes. */ 699919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke return false; 709919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke } 719919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke} 729919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke 73f34f39330bb41fb0a86930908de10353193a841dMatt Turnerbool 74f34f39330bb41fb0a86930908de10353193a841dMatt Turnerfs_visitor::dead_code_eliminate() 75f34f39330bb41fb0a86930908de10353193a841dMatt Turner{ 76f34f39330bb41fb0a86930908de10353193a841dMatt Turner bool progress = false; 77f34f39330bb41fb0a86930908de10353193a841dMatt Turner 78680fe0acb3e6569f7b9aab1913e9181d5a7eee2fMatt Turner calculate_live_intervals(); 79f34f39330bb41fb0a86930908de10353193a841dMatt Turner 80f34f39330bb41fb0a86930908de10353193a841dMatt Turner int num_vars = live_intervals->num_vars; 814d4335c81a3f7d8434d9983881a63abcbc29dd5cJuha-Pekka Heikkila BITSET_WORD *live = rzalloc_array(NULL, BITSET_WORD, BITSET_WORDS(num_vars)); 824d4335c81a3f7d8434d9983881a63abcbc29dd5cJuha-Pekka Heikkila BITSET_WORD *flag_live = rzalloc_array(NULL, BITSET_WORD, 1); 83f34f39330bb41fb0a86930908de10353193a841dMatt Turner 847e6a6f3e619e7dfed244043a95082f2168a5c953Matt Turner foreach_block_reverse_safe(block, cfg) { 8513f660158573846d6b1bc30ed4c61d97405bea58Matt Turner memcpy(live, live_intervals->block_data[block->num].liveout, 86f34f39330bb41fb0a86930908de10353193a841dMatt Turner sizeof(BITSET_WORD) * BITSET_WORDS(num_vars)); 8760d507c3c5c7caed57119df0ab4d824ad1ea85dcMatt Turner memcpy(flag_live, live_intervals->block_data[block->num].flag_liveout, 8860d507c3c5c7caed57119df0ab4d824ad1ea85dcMatt Turner sizeof(BITSET_WORD)); 89f34f39330bb41fb0a86930908de10353193a841dMatt Turner 907e6a6f3e619e7dfed244043a95082f2168a5c953Matt Turner foreach_inst_in_block_reverse_safe(fs_inst, inst, block) { 919919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke if (inst->dst.file == VGRF) { 920bc46cc9619b8ae43e7a7c96bfe91f19371d301dFrancisco Jerez const unsigned var = live_intervals->var_from_reg(inst->dst); 93f34f39330bb41fb0a86930908de10353193a841dMatt Turner bool result_live = false; 94f34f39330bb41fb0a86930908de10353193a841dMatt Turner 950bc46cc9619b8ae43e7a7c96bfe91f19371d301dFrancisco Jerez for (unsigned i = 0; i < regs_written(inst); i++) 960bc46cc9619b8ae43e7a7c96bfe91f19371d301dFrancisco Jerez result_live |= BITSET_TEST(live, var + i); 97f34f39330bb41fb0a86930908de10353193a841dMatt Turner 989919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke if (!result_live && 999919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke (can_omit_write(inst) || can_eliminate(inst, flag_live))) { 1009919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke inst->dst = fs_reg(retype(brw_null_reg(), inst->dst.type)); 101f34f39330bb41fb0a86930908de10353193a841dMatt Turner progress = true; 102f34f39330bb41fb0a86930908de10353193a841dMatt Turner } 103f34f39330bb41fb0a86930908de10353193a841dMatt Turner } 104f34f39330bb41fb0a86930908de10353193a841dMatt Turner 1059919542f1cfff70524bc6117d19bf88e59159caaKenneth Graunke if (inst->dst.is_null() && can_eliminate(inst, flag_live)) { 1063759a89ad358139ef981bd5d46261ee115762b94Matt Turner inst->opcode = BRW_OPCODE_NOP; 1073759a89ad358139ef981bd5d46261ee115762b94Matt Turner progress = true; 1083759a89ad358139ef981bd5d46261ee115762b94Matt Turner } 1093759a89ad358139ef981bd5d46261ee115762b94Matt Turner 110b163aa01487ab5f9b22c48b7badc5d65999c4985Matt Turner if (inst->dst.file == VGRF) { 11118d12336b964cad54bbc0780380c3dcf625abb3dMatt Turner if (!inst->is_partial_write()) { 112b37273b92431a2d986235774f04a9fba2aa1bf74Matt Turner int var = live_intervals->var_from_reg(inst->dst); 113c458eeb94620fbce0a37474fc292545002d67f76Francisco Jerez for (unsigned i = 0; i < regs_written(inst); i++) { 114ab7234c8520499fcfeed153e0aefeb6b43758d1fJason Ekstrand BITSET_CLEAR(live, var + i); 11518d12336b964cad54bbc0780380c3dcf625abb3dMatt Turner } 11618d12336b964cad54bbc0780380c3dcf625abb3dMatt Turner } 11718d12336b964cad54bbc0780380c3dcf625abb3dMatt Turner } 11818d12336b964cad54bbc0780380c3dcf625abb3dMatt Turner 1190fec265373f269d116f6d4de900b208fffabe2a1Francisco Jerez if (!inst->predicate && inst->exec_size >= 8) 1200fec265373f269d116f6d4de900b208fffabe2a1Francisco Jerez flag_live[0] &= ~inst->flags_written(); 12160d507c3c5c7caed57119df0ab4d824ad1ea85dcMatt Turner 1227e6a6f3e619e7dfed244043a95082f2168a5c953Matt Turner if (inst->opcode == BRW_OPCODE_NOP) { 1237e6a6f3e619e7dfed244043a95082f2168a5c953Matt Turner inst->remove(block); 12448b4e88d3d2cfa2ccd912184cfdcbe559cd36ff0Matt Turner continue; 1257e6a6f3e619e7dfed244043a95082f2168a5c953Matt Turner } 12648b4e88d3d2cfa2ccd912184cfdcbe559cd36ff0Matt Turner 127b1dcdcde2e323f960833f5c7da65d5c2c20113c9Matt Turner for (int i = 0; i < inst->sources; i++) { 128b163aa01487ab5f9b22c48b7badc5d65999c4985Matt Turner if (inst->src[i].file == VGRF) { 129b37273b92431a2d986235774f04a9fba2aa1bf74Matt Turner int var = live_intervals->var_from_reg(inst->src[i]); 130f34f39330bb41fb0a86930908de10353193a841dMatt Turner 131c458eeb94620fbce0a37474fc292545002d67f76Francisco Jerez for (unsigned j = 0; j < regs_read(inst, i); j++) { 132ab7234c8520499fcfeed153e0aefeb6b43758d1fJason Ekstrand BITSET_SET(live, var + j); 133f34f39330bb41fb0a86930908de10353193a841dMatt Turner } 134f34f39330bb41fb0a86930908de10353193a841dMatt Turner } 135f34f39330bb41fb0a86930908de10353193a841dMatt Turner } 13660d507c3c5c7caed57119df0ab4d824ad1ea85dcMatt Turner 1370fec265373f269d116f6d4de900b208fffabe2a1Francisco Jerez flag_live[0] |= inst->flags_read(devinfo); 138f34f39330bb41fb0a86930908de10353193a841dMatt Turner } 139f34f39330bb41fb0a86930908de10353193a841dMatt Turner } 140f34f39330bb41fb0a86930908de10353193a841dMatt Turner 141f34f39330bb41fb0a86930908de10353193a841dMatt Turner ralloc_free(live); 14260d507c3c5c7caed57119df0ab4d824ad1ea85dcMatt Turner ralloc_free(flag_live); 143f34f39330bb41fb0a86930908de10353193a841dMatt Turner 1447e6a6f3e619e7dfed244043a95082f2168a5c953Matt Turner if (progress) 145072ea414d04f1b9a7bf06a00b9011e8ad521c878Matt Turner invalidate_live_intervals(); 146f34f39330bb41fb0a86930908de10353193a841dMatt Turner 147f34f39330bb41fb0a86930908de10353193a841dMatt Turner return progress; 148f34f39330bb41fb0a86930908de10353193a841dMatt Turner} 149