loop_analysis.h revision 3bcfafcf0320ee5407716ff67062e80d162760d4
19434a0749f26c640305f68ef85d17a31063a5705Ian Romanick/* -*- c++ -*- */ 29434a0749f26c640305f68ef85d17a31063a5705Ian Romanick/* 39434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Copyright © 2010 Intel Corporation 49434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 59434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Permission is hereby granted, free of charge, to any person obtaining a 69434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * copy of this software and associated documentation files (the "Software"), 79434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * to deal in the Software without restriction, including without limitation 89434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * the rights to use, copy, modify, merge, publish, distribute, sublicense, 99434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * and/or sell copies of the Software, and to permit persons to whom the 109434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Software is furnished to do so, subject to the following conditions: 119434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 129434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * The above copyright notice and this permission notice (including the next 139434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * paragraph) shall be included in all copies or substantial portions of the 149434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Software. 159434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 169434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 179434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 189434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 199434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 209434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 219434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 229434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * DEALINGS IN THE SOFTWARE. 239434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 249434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 259434a0749f26c640305f68ef85d17a31063a5705Ian Romanick#pragma once 269434a0749f26c640305f68ef85d17a31063a5705Ian Romanick#ifndef LOOP_ANALYSIS_H 279434a0749f26c640305f68ef85d17a31063a5705Ian Romanick#define LOOP_ANALYSIS_H 289434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 299434a0749f26c640305f68ef85d17a31063a5705Ian Romanick#include "ir.h" 309434a0749f26c640305f68ef85d17a31063a5705Ian Romanick#include "program/hash_table.h" 319434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 329434a0749f26c640305f68ef85d17a31063a5705Ian Romanick/** 339434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Analyze and classify all variables used in all loops in the instruction list 349434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 359434a0749f26c640305f68ef85d17a31063a5705Ian Romanickextern class loop_state * 369434a0749f26c640305f68ef85d17a31063a5705Ian Romanickanalyze_loop_variables(exec_list *instructions); 379434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 389434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 399434a0749f26c640305f68ef85d17a31063a5705Ian Romanick/** 40bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * Fill in loop control fields 41bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * 42bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * Based on analysis of loop variables, this function tries to remove sequences 43bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * in the loop of the form 44bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * 45bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * (if (expression bool ...) (break)) 46bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * 47bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * and fill in the \c ir_loop::from, \c ir_loop::to, and \c ir_loop::counter 48bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * fields of the \c ir_loop. 49bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * 50bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * In this process, some conditional break-statements may be eliminated 51bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * altogether. For example, if it is provable that one loop exit condition will 52bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * always be satisfied before another, the unnecessary exit condition will be 53bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick * removed. 54bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick */ 55bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanickextern bool 56bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanickset_loop_controls(exec_list *instructions, loop_state *ls); 57bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick 58bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick 59bfe3fbb38e0a3ae7c1efb74282628c2cc5abc3e0Ian Romanick/** 609434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Tracking for all variables used in a loop 619434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 629434a0749f26c640305f68ef85d17a31063a5705Ian Romanickclass loop_variable_state : public exec_node { 639434a0749f26c640305f68ef85d17a31063a5705Ian Romanickpublic: 649434a0749f26c640305f68ef85d17a31063a5705Ian Romanick class loop_variable *get(const ir_variable *); 659434a0749f26c640305f68ef85d17a31063a5705Ian Romanick class loop_variable *insert(ir_variable *); 669434a0749f26c640305f68ef85d17a31063a5705Ian Romanick class loop_terminator *insert(ir_if *); 679434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 689434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 699434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 709434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Loop whose variable state is being tracked by this structure 719434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 729434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ir_loop *loop; 739434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 749434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 759434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Variables that have not yet been classified 769434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 779434a0749f26c640305f68ef85d17a31063a5705Ian Romanick exec_list variables; 789434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 799434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 809434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Variables whose values are constant within the body of the loop 819434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 829434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * This list contains \c loop_variable objects. 839434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 849434a0749f26c640305f68ef85d17a31063a5705Ian Romanick exec_list constants; 859434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 869434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 879434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Induction variables for this loop 889434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 899434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * This list contains \c loop_variable objects. 909434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 919434a0749f26c640305f68ef85d17a31063a5705Ian Romanick exec_list induction_variables; 929434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 939434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 949434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Simple if-statements that lead to the termination of the loop 959434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 969434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * This list contains \c loop_terminator objects. 979434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 989434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * \sa is_loop_terminator 999434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 1009434a0749f26c640305f68ef85d17a31063a5705Ian Romanick exec_list terminators; 1019434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1029434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 1039434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Hash table containing all variables accessed in this loop 1049434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 1059434a0749f26c640305f68ef85d17a31063a5705Ian Romanick hash_table *var_hash; 1069434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1073bcfafcf0320ee5407716ff67062e80d162760d4Ian Romanick /** 1083bcfafcf0320ee5407716ff67062e80d162760d4Ian Romanick * Number of ir_loop_jump instructions that operate on this loop 1093bcfafcf0320ee5407716ff67062e80d162760d4Ian Romanick */ 1103bcfafcf0320ee5407716ff67062e80d162760d4Ian Romanick unsigned num_loop_jumps; 1113bcfafcf0320ee5407716ff67062e80d162760d4Ian Romanick 1129434a0749f26c640305f68ef85d17a31063a5705Ian Romanick loop_variable_state() 1139434a0749f26c640305f68ef85d17a31063a5705Ian Romanick { 1143bcfafcf0320ee5407716ff67062e80d162760d4Ian Romanick this->num_loop_jumps = 0; 1159434a0749f26c640305f68ef85d17a31063a5705Ian Romanick this->var_hash = hash_table_ctor(0, hash_table_pointer_hash, 1169434a0749f26c640305f68ef85d17a31063a5705Ian Romanick hash_table_pointer_compare); 1179434a0749f26c640305f68ef85d17a31063a5705Ian Romanick } 1189434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1199434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ~loop_variable_state() 1209434a0749f26c640305f68ef85d17a31063a5705Ian Romanick { 1219434a0749f26c640305f68ef85d17a31063a5705Ian Romanick hash_table_dtor(this->var_hash); 1229434a0749f26c640305f68ef85d17a31063a5705Ian Romanick } 1239434a0749f26c640305f68ef85d17a31063a5705Ian Romanick}; 1249434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1259434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1269434a0749f26c640305f68ef85d17a31063a5705Ian Romanickclass loop_variable : public exec_node { 1279434a0749f26c640305f68ef85d17a31063a5705Ian Romanickpublic: 1289434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** The variable in question. */ 1299434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ir_variable *var; 1309434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1319434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** Is the variable read in the loop before it is written? */ 1329434a0749f26c640305f68ef85d17a31063a5705Ian Romanick bool read_before_write; 1339434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1349434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** Are all variables in the RHS of the assignment loop constants? */ 1359434a0749f26c640305f68ef85d17a31063a5705Ian Romanick bool rhs_clean; 1369434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1379434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** Is there an assignment to the variable that is conditional? */ 1389434a0749f26c640305f68ef85d17a31063a5705Ian Romanick bool conditional_assignment; 1399434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1409434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** Reference to the first assignment to the variable in the loop body. */ 1419434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ir_assignment *first_assignment; 1429434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1439434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** Number of assignments to the variable in the loop body. */ 1449434a0749f26c640305f68ef85d17a31063a5705Ian Romanick unsigned num_assignments; 1459434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1469434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 1479434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Increment values for loop induction variables 1489434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 1499434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Loop induction variables have a single increment of the form 1509434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * \c b * \c biv + \c c, where \c b and \c c are loop constants and \c i 1519434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * is a basic loop induction variable. 1529434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * 1539434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * If \c iv_scale is \c NULL, 1 is used. If \c biv is the same as \c var, 1549434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * then \c var is a basic loop induction variable. 1559434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 1569434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /*@{*/ 1579434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ir_rvalue *iv_scale; 1589434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ir_variable *biv; 1599434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ir_rvalue *increment; 1609434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /*@}*/ 1619434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1629434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1639434a0749f26c640305f68ef85d17a31063a5705Ian Romanick inline bool is_loop_constant() const 1649434a0749f26c640305f68ef85d17a31063a5705Ian Romanick { 1659434a0749f26c640305f68ef85d17a31063a5705Ian Romanick const bool is_const = (this->num_assignments == 0) 1669434a0749f26c640305f68ef85d17a31063a5705Ian Romanick || ((this->num_assignments == 1) 1679434a0749f26c640305f68ef85d17a31063a5705Ian Romanick && !this->conditional_assignment 1689434a0749f26c640305f68ef85d17a31063a5705Ian Romanick && !this->read_before_write 1699434a0749f26c640305f68ef85d17a31063a5705Ian Romanick && this->rhs_clean); 1709434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1719434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /* If the RHS of *the* assignment is clean, then there must be exactly 1729434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * one assignment of the variable. 1739434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 1749434a0749f26c640305f68ef85d17a31063a5705Ian Romanick assert((this->rhs_clean && (this->num_assignments == 1)) 1759434a0749f26c640305f68ef85d17a31063a5705Ian Romanick || !this->rhs_clean); 1769434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1779434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /* Variables that are marked read-only *MUST* be loop constant. 1789434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 1799434a0749f26c640305f68ef85d17a31063a5705Ian Romanick assert(!this->var->read_only || (this->var->read_only && is_const)); 1809434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1819434a0749f26c640305f68ef85d17a31063a5705Ian Romanick return is_const; 1829434a0749f26c640305f68ef85d17a31063a5705Ian Romanick } 1839434a0749f26c640305f68ef85d17a31063a5705Ian Romanick}; 1849434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1859434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1869434a0749f26c640305f68ef85d17a31063a5705Ian Romanickclass loop_terminator : public exec_node { 1879434a0749f26c640305f68ef85d17a31063a5705Ian Romanickpublic: 1889434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ir_if *ir; 1899434a0749f26c640305f68ef85d17a31063a5705Ian Romanick}; 1909434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1919434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1929434a0749f26c640305f68ef85d17a31063a5705Ian Romanickclass loop_state { 1939434a0749f26c640305f68ef85d17a31063a5705Ian Romanickpublic: 1949434a0749f26c640305f68ef85d17a31063a5705Ian Romanick ~loop_state(); 1959434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 1969434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 1979434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Get the loop variable state data for a particular loop 1989434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 1999434a0749f26c640305f68ef85d17a31063a5705Ian Romanick loop_variable_state *get(const ir_loop *); 2009434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 2019434a0749f26c640305f68ef85d17a31063a5705Ian Romanick loop_variable_state *insert(ir_loop *ir); 2029434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 2039434a0749f26c640305f68ef85d17a31063a5705Ian Romanickprivate: 2049434a0749f26c640305f68ef85d17a31063a5705Ian Romanick loop_state(); 2059434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 2069434a0749f26c640305f68ef85d17a31063a5705Ian Romanick /** 2079434a0749f26c640305f68ef85d17a31063a5705Ian Romanick * Hash table containing all loops that have been analyzed. 2089434a0749f26c640305f68ef85d17a31063a5705Ian Romanick */ 2099434a0749f26c640305f68ef85d17a31063a5705Ian Romanick hash_table *ht; 2109434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 2119434a0749f26c640305f68ef85d17a31063a5705Ian Romanick void *mem_ctx; 2129434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 2139434a0749f26c640305f68ef85d17a31063a5705Ian Romanick friend class loop_analysis; 2149434a0749f26c640305f68ef85d17a31063a5705Ian Romanick}; 2159434a0749f26c640305f68ef85d17a31063a5705Ian Romanick 2169434a0749f26c640305f68ef85d17a31063a5705Ian Romanick#endif /* LOOP_ANALYSIS_H */ 217