18f2214f4892acb994d13531d555196bd8f242dadIan Romanick/* 28f2214f4892acb994d13531d555196bd8f242dadIan Romanick * Copyright © 2010 Intel Corporation 38f2214f4892acb994d13531d555196bd8f242dadIan Romanick * 48f2214f4892acb994d13531d555196bd8f242dadIan Romanick * Permission is hereby granted, free of charge, to any person obtaining a 58f2214f4892acb994d13531d555196bd8f242dadIan Romanick * copy of this software and associated documentation files (the "Software"), 68f2214f4892acb994d13531d555196bd8f242dadIan Romanick * to deal in the Software without restriction, including without limitation 78f2214f4892acb994d13531d555196bd8f242dadIan Romanick * the rights to use, copy, modify, merge, publish, distribute, sublicense, 88f2214f4892acb994d13531d555196bd8f242dadIan Romanick * and/or sell copies of the Software, and to permit persons to whom the 98f2214f4892acb994d13531d555196bd8f242dadIan Romanick * Software is furnished to do so, subject to the following conditions: 108f2214f4892acb994d13531d555196bd8f242dadIan Romanick * 118f2214f4892acb994d13531d555196bd8f242dadIan Romanick * The above copyright notice and this permission notice (including the next 128f2214f4892acb994d13531d555196bd8f242dadIan Romanick * paragraph) shall be included in all copies or substantial portions of the 138f2214f4892acb994d13531d555196bd8f242dadIan Romanick * Software. 148f2214f4892acb994d13531d555196bd8f242dadIan Romanick * 158f2214f4892acb994d13531d555196bd8f242dadIan Romanick * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 168f2214f4892acb994d13531d555196bd8f242dadIan Romanick * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 178f2214f4892acb994d13531d555196bd8f242dadIan Romanick * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 188f2214f4892acb994d13531d555196bd8f242dadIan Romanick * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 198f2214f4892acb994d13531d555196bd8f242dadIan Romanick * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 208f2214f4892acb994d13531d555196bd8f242dadIan Romanick * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 218f2214f4892acb994d13531d555196bd8f242dadIan Romanick * DEALINGS IN THE SOFTWARE. 228f2214f4892acb994d13531d555196bd8f242dadIan Romanick */ 238f2214f4892acb994d13531d555196bd8f242dadIan Romanick 248f2214f4892acb994d13531d555196bd8f242dadIan Romanick/** 258f2214f4892acb994d13531d555196bd8f242dadIan Romanick * \file opt_redundant_jumps.cpp 268f2214f4892acb994d13531d555196bd8f242dadIan Romanick * Remove certain types of redundant jumps 278f2214f4892acb994d13531d555196bd8f242dadIan Romanick */ 288f2214f4892acb994d13531d555196bd8f242dadIan Romanick 298f2214f4892acb994d13531d555196bd8f242dadIan Romanick#include "ir.h" 308f2214f4892acb994d13531d555196bd8f242dadIan Romanick 31337d9c955b070224f7278524af54ddacd8bb0f17Eric Anholtnamespace { 32337d9c955b070224f7278524af54ddacd8bb0f17Eric Anholt 338f2214f4892acb994d13531d555196bd8f242dadIan Romanickclass redundant_jumps_visitor : public ir_hierarchical_visitor { 348f2214f4892acb994d13531d555196bd8f242dadIan Romanickpublic: 358f2214f4892acb994d13531d555196bd8f242dadIan Romanick redundant_jumps_visitor() 368f2214f4892acb994d13531d555196bd8f242dadIan Romanick { 378f2214f4892acb994d13531d555196bd8f242dadIan Romanick this->progress = false; 388f2214f4892acb994d13531d555196bd8f242dadIan Romanick } 398f2214f4892acb994d13531d555196bd8f242dadIan Romanick 408f2214f4892acb994d13531d555196bd8f242dadIan Romanick virtual ir_visitor_status visit_leave(ir_if *); 418f2214f4892acb994d13531d555196bd8f242dadIan Romanick virtual ir_visitor_status visit_leave(ir_loop *); 42d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholt virtual ir_visitor_status visit_enter(ir_assignment *); 438f2214f4892acb994d13531d555196bd8f242dadIan Romanick 448f2214f4892acb994d13531d555196bd8f242dadIan Romanick bool progress; 458f2214f4892acb994d13531d555196bd8f242dadIan Romanick}; 468f2214f4892acb994d13531d555196bd8f242dadIan Romanick 47337d9c955b070224f7278524af54ddacd8bb0f17Eric Anholt} /* unnamed namespace */ 48337d9c955b070224f7278524af54ddacd8bb0f17Eric Anholt 49d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholt/* We only care about the top level instructions, so don't descend 50d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholt * into expressions. 51d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholt */ 52d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholtir_visitor_status 53d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholtredundant_jumps_visitor::visit_enter(ir_assignment *ir) 54d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholt{ 55d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholt return visit_continue_with_parent; 56d3a444af2d4c42a23e9ec78dbef4c3ee45e1e50cEric Anholt} 578f2214f4892acb994d13531d555196bd8f242dadIan Romanick 588f2214f4892acb994d13531d555196bd8f242dadIan Romanickir_visitor_status 598f2214f4892acb994d13531d555196bd8f242dadIan Romanickredundant_jumps_visitor::visit_leave(ir_if *ir) 608f2214f4892acb994d13531d555196bd8f242dadIan Romanick{ 618f2214f4892acb994d13531d555196bd8f242dadIan Romanick /* If the last instruction in both branches is a 'break' or a 'continue', 628f2214f4892acb994d13531d555196bd8f242dadIan Romanick * pull it out of the branches and insert it after the if-statment. Note 638f2214f4892acb994d13531d555196bd8f242dadIan Romanick * that both must be the same type (either 'break' or 'continue'). 648f2214f4892acb994d13531d555196bd8f242dadIan Romanick */ 658f2214f4892acb994d13531d555196bd8f242dadIan Romanick ir_instruction *const last_then = 668f2214f4892acb994d13531d555196bd8f242dadIan Romanick (ir_instruction *) ir->then_instructions.get_tail(); 678f2214f4892acb994d13531d555196bd8f242dadIan Romanick ir_instruction *const last_else = 688f2214f4892acb994d13531d555196bd8f242dadIan Romanick (ir_instruction *) ir->else_instructions.get_tail(); 698f2214f4892acb994d13531d555196bd8f242dadIan Romanick 708f2214f4892acb994d13531d555196bd8f242dadIan Romanick if ((last_then == NULL) || (last_else == NULL)) 718f2214f4892acb994d13531d555196bd8f242dadIan Romanick return visit_continue; 728f2214f4892acb994d13531d555196bd8f242dadIan Romanick 738f2214f4892acb994d13531d555196bd8f242dadIan Romanick if ((last_then->ir_type != ir_type_loop_jump) 748f2214f4892acb994d13531d555196bd8f242dadIan Romanick || (last_else->ir_type != ir_type_loop_jump)) 758f2214f4892acb994d13531d555196bd8f242dadIan Romanick return visit_continue; 768f2214f4892acb994d13531d555196bd8f242dadIan Romanick 778f2214f4892acb994d13531d555196bd8f242dadIan Romanick ir_loop_jump *const then_jump = (ir_loop_jump *) last_then; 788f2214f4892acb994d13531d555196bd8f242dadIan Romanick ir_loop_jump *const else_jump = (ir_loop_jump *) last_else; 798f2214f4892acb994d13531d555196bd8f242dadIan Romanick 808f2214f4892acb994d13531d555196bd8f242dadIan Romanick if (then_jump->mode != else_jump->mode) 818f2214f4892acb994d13531d555196bd8f242dadIan Romanick return visit_continue; 828f2214f4892acb994d13531d555196bd8f242dadIan Romanick 838f2214f4892acb994d13531d555196bd8f242dadIan Romanick then_jump->remove(); 848f2214f4892acb994d13531d555196bd8f242dadIan Romanick else_jump->remove(); 858f2214f4892acb994d13531d555196bd8f242dadIan Romanick this->progress = true; 868f2214f4892acb994d13531d555196bd8f242dadIan Romanick 878f2214f4892acb994d13531d555196bd8f242dadIan Romanick ir->insert_after(then_jump); 888f2214f4892acb994d13531d555196bd8f242dadIan Romanick 898f2214f4892acb994d13531d555196bd8f242dadIan Romanick /* If both branchs of the if-statement are now empty, remove the 908f2214f4892acb994d13531d555196bd8f242dadIan Romanick * if-statement. 918f2214f4892acb994d13531d555196bd8f242dadIan Romanick */ 928f2214f4892acb994d13531d555196bd8f242dadIan Romanick if (ir->then_instructions.is_empty() && ir->else_instructions.is_empty()) 938f2214f4892acb994d13531d555196bd8f242dadIan Romanick ir->remove(); 948f2214f4892acb994d13531d555196bd8f242dadIan Romanick 958f2214f4892acb994d13531d555196bd8f242dadIan Romanick return visit_continue; 968f2214f4892acb994d13531d555196bd8f242dadIan Romanick} 978f2214f4892acb994d13531d555196bd8f242dadIan Romanick 988f2214f4892acb994d13531d555196bd8f242dadIan Romanick 998f2214f4892acb994d13531d555196bd8f242dadIan Romanickir_visitor_status 1008f2214f4892acb994d13531d555196bd8f242dadIan Romanickredundant_jumps_visitor::visit_leave(ir_loop *ir) 1018f2214f4892acb994d13531d555196bd8f242dadIan Romanick{ 1028f2214f4892acb994d13531d555196bd8f242dadIan Romanick /* If the last instruction of a loop body is a 'continue', remove it. 1038f2214f4892acb994d13531d555196bd8f242dadIan Romanick */ 1048f2214f4892acb994d13531d555196bd8f242dadIan Romanick ir_instruction *const last = 1058f2214f4892acb994d13531d555196bd8f242dadIan Romanick (ir_instruction *) ir->body_instructions.get_tail(); 1068f2214f4892acb994d13531d555196bd8f242dadIan Romanick 1078f2214f4892acb994d13531d555196bd8f242dadIan Romanick if (last && (last->ir_type == ir_type_loop_jump) 1088f2214f4892acb994d13531d555196bd8f242dadIan Romanick && (((ir_loop_jump *) last)->mode == ir_loop_jump::jump_continue)) { 1098f2214f4892acb994d13531d555196bd8f242dadIan Romanick last->remove(); 1108f2214f4892acb994d13531d555196bd8f242dadIan Romanick this->progress = true; 1118f2214f4892acb994d13531d555196bd8f242dadIan Romanick } 1128f2214f4892acb994d13531d555196bd8f242dadIan Romanick 1138f2214f4892acb994d13531d555196bd8f242dadIan Romanick return visit_continue; 1148f2214f4892acb994d13531d555196bd8f242dadIan Romanick} 1158f2214f4892acb994d13531d555196bd8f242dadIan Romanick 1168f2214f4892acb994d13531d555196bd8f242dadIan Romanick 1178f2214f4892acb994d13531d555196bd8f242dadIan Romanickbool 1188f2214f4892acb994d13531d555196bd8f242dadIan Romanickoptimize_redundant_jumps(exec_list *instructions) 1198f2214f4892acb994d13531d555196bd8f242dadIan Romanick{ 1208f2214f4892acb994d13531d555196bd8f242dadIan Romanick redundant_jumps_visitor v; 1218f2214f4892acb994d13531d555196bd8f242dadIan Romanick 1228f2214f4892acb994d13531d555196bd8f242dadIan Romanick v.run(instructions); 1238f2214f4892acb994d13531d555196bd8f242dadIan Romanick return v.progress; 1248f2214f4892acb994d13531d555196bd8f242dadIan Romanick} 125