1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/* 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright © 2010 Intel Corporation 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * copy of this software and associated documentation files (the "Software"), 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * to deal in the Software without restriction, including without limitation 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software is furnished to do so, subject to the following conditions: 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The above copyright notice and this permission notice (including the next 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * paragraph) shall be included in all copies or substantial portions of the 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software. 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * DEALINGS IN THE SOFTWARE. 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "glsl_types.h" 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "loop_analysis.h" 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "ir_hierarchical_visitor.h" 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic bool is_loop_terminator(ir_if *ir); 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic bool all_expression_operands_are_loop_constant(ir_rvalue *, 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org hash_table *); 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic ir_rvalue *get_basic_induction_increment(ir_assignment *, hash_table *); 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_state::loop_state() 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->ht = hash_table_ctor(0, hash_table_pointer_hash, 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org hash_table_pointer_compare); 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->mem_ctx = ralloc_context(NULL); 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->loop_found = false; 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_state::~loop_state() 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org hash_table_dtor(this->ht); 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ralloc_free(this->mem_ctx); 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_variable_state * 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_state::insert(ir_loop *ir) 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable_state *ls = new(this->mem_ctx) loop_variable_state; 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org hash_table_insert(this->ht, ls, ir); 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->loop_found = true; 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return ls; 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_variable_state * 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_state::get(const ir_loop *ir) 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return (loop_variable_state *) hash_table_find(this->ht, ir); 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_variable * 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_variable_state::get(const ir_variable *ir) 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return (loop_variable *) hash_table_find(this->var_hash, ir); 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_variable * 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_variable_state::insert(ir_variable *var) 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *mem_ctx = ralloc_parent(this); 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable *lv = rzalloc(mem_ctx, loop_variable); 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->var = var; 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org hash_table_insert(this->var_hash, lv, lv->var); 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->variables.push_tail(lv); 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return lv; 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_terminator * 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_variable_state::insert(ir_if *if_stmt) 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *mem_ctx = ralloc_parent(this); 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_terminator *t = rzalloc(mem_ctx, loop_terminator); 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t->ir = if_stmt; 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->terminators.push_tail(t); 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return t; 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass loop_analysis : public ir_hierarchical_visitor { 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_analysis(); 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit(ir_loop_jump *); 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit(ir_dereference_variable *); 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit_enter(ir_call *); 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit_enter(ir_loop *); 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit_leave(ir_loop *); 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit_enter(ir_assignment *); 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit_leave(ir_assignment *); 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit_enter(ir_if *); 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit_leave(ir_if *); 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_state *loops; 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int if_statement_depth; 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_assignment *current_assignment; 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org exec_list state; 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::loop_analysis() 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->loops = new loop_state; 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->if_statement_depth = 0; 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->current_assignment = NULL; 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit(ir_loop_jump *ir) 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (void) ir; 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!this->state.is_empty()); 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable_state *const ls = 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (loop_variable_state *) this->state.get_head(); 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ls->num_loop_jumps++; 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit_enter(ir_call *ir) 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* If we're not somewhere inside a loop, there's nothing to do. */ 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (this->state.is_empty()) 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable_state *const ls = 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (loop_variable_state *) this->state.get_head(); 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ls->contains_calls = true; 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue_with_parent; 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit(ir_dereference_variable *ir) 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* If we're not somewhere inside a loop, there's nothing to do. 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (this->state.is_empty()) 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable_state *const ls = 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (loop_variable_state *) this->state.get_head(); 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_variable *var = ir->variable_referenced(); 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable *lv = ls->get(var); 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (lv == NULL) { 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv = ls->insert(var); 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->read_before_write = !this->in_assignee; 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (this->in_assignee) { 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(this->current_assignment != NULL); 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->conditional_assignment = (this->if_statement_depth > 0) 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org || (this->current_assignment->condition != NULL); 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (lv->first_assignment == NULL) { 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(lv->num_assignments == 0); 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->first_assignment = this->current_assignment; 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->num_assignments++; 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else if (lv->first_assignment == this->current_assignment) { 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* This catches the case where the variable is used in the RHS of an 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * assignment where it is also in the LHS. 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->read_before_write = true; 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 211f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 212f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 213f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 214f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 215f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit_enter(ir_loop *ir) 216f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 217f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable_state *ls = this->loops->insert(ir); 218f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->state.push_head(ls); 219f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 220f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 221f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 222f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 223f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 224f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit_leave(ir_loop *ir) 225f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 226f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable_state *const ls = 227f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (loop_variable_state *) this->state.pop_head(); 228f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 229f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* Function calls may contain side effects. These could alter any of our 230f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * variables in ways that cannot be known, and may even terminate shader 231f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * execution (say, calling discard in the fragment shader). So we can't 232f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * rely on any of our analysis about assignments to variables. 233f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 234f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * We could perform some conservative analysis (prove there's no statically 235f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * possible assignment, etc.) but it isn't worth it for now; function 236f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * inlining will allow us to unroll loops anyway. 237f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 238f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (ls->contains_calls) 239f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 240f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 241f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org foreach_list(node, &ir->body_instructions) { 242f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* Skip over declarations at the start of a loop. 243f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 244f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (((ir_instruction *) node)->as_variable()) 245f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 246f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 247f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_if *if_stmt = ((ir_instruction *) node)->as_if(); 248f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 249f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ((if_stmt != NULL) && is_loop_terminator(if_stmt)) 250f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ls->insert(if_stmt); 251f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 252f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 253f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 254f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 255f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 256f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org foreach_list_safe(node, &ls->variables) { 257f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable *lv = (loop_variable *) node; 258f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 259f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* Move variables that are already marked as being loop constant to 260f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * a separate list. These trivially don't need to be tested. 261f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 262f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (lv->is_loop_constant()) { 263f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->remove(); 264f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ls->constants.push_tail(lv); 265f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 266f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 267f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 268f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* Each variable assigned in the loop that isn't already marked as being loop 269f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * constant might still be loop constant. The requirements at this point 270f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * are: 271f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 272f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * - Variable is written before it is read. 273f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 274f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * - Only one assignment to the variable. 275f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 276f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * - All operands on the RHS of the assignment are also loop constants. 277f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 278f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The last requirement is the reason for the progress loop. A variable 279f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * marked as a loop constant on one pass may allow other variables to be 280f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * marked as loop constant on following passes. 281f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 282f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool progress; 283f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org do { 284f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org progress = false; 285f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 286f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org foreach_list_safe(node, &ls->variables) { 287f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable *lv = (loop_variable *) node; 288f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 289f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (lv->conditional_assignment || (lv->num_assignments > 1)) 290f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 291f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 292f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* Process the RHS of the assignment. If all of the variables 293f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * accessed there are loop constants, then add this 294f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 295f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_rvalue *const rhs = lv->first_assignment->rhs; 296f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (all_expression_operands_are_loop_constant(rhs, ls->var_hash)) { 297f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->rhs_clean = true; 298f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 299f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (lv->is_loop_constant()) { 300f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org progress = true; 301f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 302f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->remove(); 303f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ls->constants.push_tail(lv); 304f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 305f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 306f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 307f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } while (progress); 308f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 309f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* The remaining variables that are not loop invariant might be loop 310f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * induction variables. 311f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 312f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org foreach_list_safe(node, &ls->variables) { 313f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable *lv = (loop_variable *) node; 314f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 315f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* If there is more than one assignment to a variable, it cannot be a 316f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * loop induction variable. This isn't strictly true, but this is a 317f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * very simple induction variable detector, and it can't handle more 318f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * complex cases. 319f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 320f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (lv->num_assignments > 1) 321f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 322f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 323f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* All of the variables with zero assignments in the loop are loop 324f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * invariant, and they should have already been filtered out. 325f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 326f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(lv->num_assignments == 1); 327f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(lv->first_assignment != NULL); 328f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 329f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* The assignmnet to the variable in the loop must be unconditional. 330f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 331f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (lv->conditional_assignment) 332f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 333f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 334f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* Basic loop induction variables have a single assignment in the loop 335f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * that has the form 'VAR = VAR + i' or 'VAR = VAR - i' where i is a 336f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * loop invariant. 337f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 338f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_rvalue *const inc = 339f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get_basic_induction_increment(lv->first_assignment, ls->var_hash); 340f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (inc != NULL) { 341f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->iv_scale = NULL; 342f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->biv = lv->var; 343f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->increment = inc; 344f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 345f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org lv->remove(); 346f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ls->induction_variables.push_tail(lv); 347f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 348f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 349f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 350f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 351f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 352f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 353f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 354f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit_enter(ir_if *ir) 355f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 356f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (void) ir; 357f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 358f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!this->state.is_empty()) 359f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->if_statement_depth++; 360f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 361f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 362f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 363f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 364f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 365f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit_leave(ir_if *ir) 366f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 367f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (void) ir; 368f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 369f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!this->state.is_empty()) 370f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->if_statement_depth--; 371f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 372f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 373f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 374f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 375f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 376f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit_enter(ir_assignment *ir) 377f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 378f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* If we're not somewhere inside a loop, there's nothing to do. 379f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 380f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (this->state.is_empty()) 381f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue_with_parent; 382f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 383f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->current_assignment = ir; 384f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 385f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 386f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 387f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 388f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_visitor_status 389f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_analysis::visit_leave(ir_assignment *ir) 390f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 391f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* Since the visit_enter exits with visit_continue_with_parent for this 392f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * case, the loop state stack should never be empty here. 393f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 394f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!this->state.is_empty()); 395f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 396f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(this->current_assignment == ir); 397f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->current_assignment = NULL; 398f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 399f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 400f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 401f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 402f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 403f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgclass examine_rhs : public ir_hierarchical_visitor { 404f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgpublic: 405f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org examine_rhs(hash_table *loop_variables) 406f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 407f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->only_uses_loop_constants = true; 408f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->loop_variables = loop_variables; 409f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 410f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 411f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual ir_visitor_status visit(ir_dereference_variable *ir) 412f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 413f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable *lv = 414f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (loop_variable *) hash_table_find(this->loop_variables, ir->var); 415f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 416f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(lv != NULL); 417f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 418f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (lv->is_loop_constant()) { 419f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_continue; 420f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 421f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->only_uses_loop_constants = false; 422f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return visit_stop; 423f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 424f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 425f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 426f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org hash_table *loop_variables; 427f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool only_uses_loop_constants; 428f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 429f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 430f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 431f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 432f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgall_expression_operands_are_loop_constant(ir_rvalue *ir, hash_table *variables) 433f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 434f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org examine_rhs v(variables); 435f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 436f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir->accept(&v); 437f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 438f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return v.only_uses_loop_constants; 439f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 440f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 441f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 442f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgir_rvalue * 443f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgget_basic_induction_increment(ir_assignment *ir, hash_table *var_hash) 444f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 445f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* The RHS must be a binary expression. 446f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 447f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_expression *const rhs = ir->rhs->as_expression(); 448f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ((rhs == NULL) 449f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org || ((rhs->operation != ir_binop_add) 450f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org && (rhs->operation != ir_binop_sub))) 451f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return NULL; 452f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 453f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* One of the of operands of the expression must be the variable assigned. 454f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * If the operation is subtraction, the variable in question must be the 455f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * "left" operand. 456f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 457f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_variable *const var = ir->lhs->variable_referenced(); 458f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 459f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_variable *const op0 = rhs->operands[0]->variable_referenced(); 460f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_variable *const op1 = rhs->operands[1]->variable_referenced(); 461f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 462f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (((op0 != var) && (op1 != var)) 463f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org || ((op1 == var) && (rhs->operation == ir_binop_sub))) 464f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return NULL; 465f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 466f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_rvalue *inc = (op0 == var) ? rhs->operands[1] : rhs->operands[0]; 467f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 468f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (inc->as_constant() == NULL) { 469f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_variable *const inc_var = inc->variable_referenced(); 470f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (inc_var != NULL) { 471f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_variable *lv = 472f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (loop_variable *) hash_table_find(var_hash, inc_var); 473f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 474f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!lv->is_loop_constant()) 475f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inc = NULL; 476f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else 477f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inc = NULL; 478f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 479f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 480f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ((inc != NULL) && (rhs->operation == ir_binop_sub)) { 481f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *mem_ctx = ralloc_parent(ir); 482f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 483f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inc = new(mem_ctx) ir_expression(ir_unop_neg, 484f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inc->type, 485f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org inc->clone(mem_ctx, NULL), 486f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org NULL); 487f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 488f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 489f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return inc; 490f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 491f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 492f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 493f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 494f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Detect whether an if-statement is a loop terminating condition 495f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 496f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Detects if-statements of the form 497f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 498f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * (if (expression bool ...) (break)) 499f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 500f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 501f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgis_loop_terminator(ir_if *ir) 502f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 503f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!ir->else_instructions.is_empty()) 504f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 505f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 506f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_instruction *const inst = 507f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (ir_instruction *) ir->then_instructions.get_head(); 508f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(inst != NULL); 509f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 510f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (inst->ir_type != ir_type_loop_jump) 511f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 512f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 513f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ir_loop_jump *const jump = (ir_loop_jump *) inst; 514f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (jump->mode != ir_loop_jump::jump_break) 515f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 516f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 517f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 518f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 519f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 520f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 521f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgloop_state * 522f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.organalyze_loop_variables(exec_list *instructions) 523f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 524f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org loop_analysis v; 525f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 526f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org v.run(instructions); 527f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return v.loops; 528f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 529