/* GIMPLE range GORI functions. Copyright (C) 2017-2019 Free Software Foundation, Inc. Contributed by Andrew MacLeod . This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ #include "config.h" #include "system.h" #include "coretypes.h" #include "backend.h" #include "tree.h" #include "gimple.h" #include "ssa.h" #include "gimple-pretty-print.h" #include "diagnostic-core.h" #include "wide-int.h" #include "gimple-range.h" #include "gimple-range-gori.h" #include "fold-const.h" // Construct a range_def_chain range_def_chain::range_def_chain () { m_def_chain.create (0); m_def_chain.safe_grow_cleared (num_ssa_names); m_terminal.create (0); m_terminal.safe_grow_cleared (num_ssa_names); } // Destruct a range_def_chain range_def_chain::~range_def_chain () { unsigned x; for (x = 0; x < m_def_chain.length (); ++x) if (m_def_chain[x]) BITMAP_FREE (m_def_chain[x]); m_def_chain.release (); m_terminal.release (); } // Return true if NAME is in the def chain of DEF. If BB is provided, // only return true if the defining statement of DEF is in BB. bool range_def_chain::in_chain_p (tree name, tree def) { gcc_checking_assert (gimple_range_ssa_p (def)); gcc_checking_assert (gimple_range_ssa_p (name)); // Get the defintion chain for DEF bitmap chain = get_def_chain (def); if (chain == NULL) return false; return bitmap_bit_p (chain, SSA_NAME_VERSION (name)); } // If NAME has a definition chain, and the chain has a single import // into the block, return the name of that import. tree range_def_chain::terminal_name (tree name) { // Ensure the def chain has been calculated. get_def_chain (name); return m_terminal[SSA_NAME_VERSION (name)]; } // Given up to 3 ssa names, return the common name or NULL_TREE. // NULL_TREE's passed in can be ignored, but all specified ssa-names // must be the same name. static inline tree pick_import (tree ssa1, tree ssa2, tree ssa3) { if (ssa1) { if (ssa2 && ssa1 != ssa2) return NULL_TREE; // No match. // Either ssa2 is NULL, or it is the same as ssa1. if (!ssa3 || ssa1 == ssa3) return ssa1; // ssa1 is the import. return NULL_TREE; } if (ssa2) { // If there is no ssa3 or ssa3 is the same as ssa2, thats the import. if (!ssa3 || ssa2 == ssa3) return ssa2; // They must both be different, so no import. return NULL_TREE; } return ssa3; } // Build def_chains for NAME if it is in BB.. copy the def chain into // RESULT. Return the import for name, or NAME if it is an import. tree range_def_chain::build_def_chain (tree name, bitmap result, basic_block bb) { bitmap b; gimple *def_stmt = SSA_NAME_DEF_STMT (name); // Add this operand into the result. bitmap_set_bit (result, SSA_NAME_VERSION (name)); if (gimple_bb (def_stmt) == bb && !is_a(def_stmt)) { // Get the def chain for the operand b = get_def_chain (name); // If there was one, copy it into result and retuirn the terminal name. if (b) { bitmap_ior_into (result, b); return m_terminal [SSA_NAME_VERSION (name)]; } // If there is no def chain, this terminal is within the same BB. } return name; // This is an import. } // Return TRUE if NAME has been processed for a def_chain. inline bool range_def_chain::has_def_chain (tree name) { unsigned v = SSA_NAME_VERSION (name); if (v >= m_def_chain.length ()) { m_def_chain.safe_grow_cleared (num_ssa_names + 1); m_terminal.safe_grow_cleared (num_ssa_names + 1); } return (m_def_chain[v] != NULL); } // Calculate the def chain for NAME and all of its dependent // operands. Only using names in the same BB. Return the bitmap of // all names in the m_def_chain. This only works for supported range // statements. bitmap range_def_chain::get_def_chain (tree name) { tree ssa1, ssa2, ssa3; unsigned v = SSA_NAME_VERSION (name); // If it has already been processed, just return the cached value. if (has_def_chain (name)) return m_def_chain[v]; // No definition chain for default defs. if (SSA_NAME_IS_DEFAULT_DEF (name)) return NULL; gimple *s = SSA_NAME_DEF_STMT (name); if (gimple_range_handler (s)) { ssa1 = gimple_range_ssa_p (gimple_range_operand1 (s)); ssa2 = gimple_range_ssa_p (gimple_range_operand2 (s)); ssa3 = NULL_TREE; } else if (is_a (s) && gimple_assign_rhs_code (s) == COND_EXPR) { gassign *st = as_a (s); ssa1 = gimple_range_ssa_p (gimple_assign_rhs1 (st)); ssa2 = gimple_range_ssa_p (gimple_assign_rhs2 (st)); ssa3 = gimple_range_ssa_p (gimple_assign_rhs3 (st)); } else return NULL; basic_block bb = gimple_bb (s); // Allocate a new bitmap and initialize it. m_def_chain[v] = BITMAP_ALLOC (NULL); // build_def_chain returns the terminal name. If we have more than // one unique terminal name, then this statement will have no // terminal. bool has_term = true; m_terminal[v] = NULL_TREE; if (ssa1) { ssa1 = build_def_chain (ssa1, m_def_chain[v], bb); // if this chain has no terminal, root cannot either. if (!ssa1) has_term = false; } if (ssa2) { ssa2 = build_def_chain (ssa2, m_def_chain[v], bb); if (!ssa2) has_term = false; } if (ssa3) { ssa3 = build_def_chain (ssa3, m_def_chain[v], bb); if (!ssa3) has_term = false; } if (has_term) m_terminal[v] = pick_import (ssa1, ssa2, ssa3); else m_terminal[v] = NULL_TREE; // If we run into pathological cases where the defintion chains are // huge (I'm thinking fppp for instance.. huge basic block fully // unrolled) we might be able to limit this by deciding here that if // there is no import AND 2 or more ssa names, we change the // def_chain back to be just the ssa-names. that should prevent a_2 // = b_6 + a_8 from creating a pathological case yet allow us to // still handle it when b_6 and a_8 are derived from the same base // name. thoughts? return m_def_chain[v]; } // Initialize a gori-map structure. gori_map::gori_map () { m_outgoing.create (0); m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); m_incoming.create (0); m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun)); } // Free any memory the GORI map allocated. gori_map::~gori_map () { unsigned bb; for (bb = 0; bb < m_outgoing.length (); ++bb) if (m_outgoing[bb]) BITMAP_FREE (m_outgoing[bb]); m_outgoing.release (); for (bb = 0; bb < m_incoming.length (); ++bb) if (m_incoming[bb]) BITMAP_FREE (m_incoming[bb]); m_incoming.release (); } // Return the bitmap vector of all imports to BB. Calculate if necessary. bitmap gori_map::imports (basic_block bb) { if (!m_incoming[bb->index]) calculate_gori (bb); return m_incoming[bb->index]; } // Return true if NAME is an import to basic block BB bool gori_map::is_import_p (tree name, basic_block bb) { return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name)); } // Return the bitmap vector of all export from BB. Calculate if necessary. bitmap gori_map::exports (basic_block bb) { if (!m_outgoing[bb->index]) calculate_gori (bb); return m_outgoing[bb->index]; } // Return true if NAME is can have ranges generated for it from basic // block BB. bool gori_map::is_export_p (tree name, basic_block bb) { return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name)); } // Return true if any element in the def chain of NAME is in the // export list for BB. bool gori_map::def_chain_in_export_p (tree name, basic_block bb) { bitmap a = exports (bb); bitmap b = get_def_chain (name); if (a && b) return bitmap_intersect_p (a, b); return false; } // If NAME is non-NULL and defined in block BB, calculate the def // chain and add it to m_outgoing, and any imports to m_incoming. void gori_map::maybe_add_gori (tree name, basic_block bb) { if (name) { bitmap r = get_def_chain (name); if (r) { bitmap_copy (m_outgoing[bb->index], r); tree im = terminal_name (name); if (im) bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (im)); } else { // If there is no def chain, and name originates outside // this block then this name is also an import. if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb) bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name)); } // Def chain doesn't include itself, and even if there isn't a // def chain, this name should be added to exports. bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name)); } } // Calculate all the required information for BB. void gori_map::calculate_gori (basic_block bb) { tree name; gcc_assert (m_outgoing[bb->index] == NULL); m_outgoing[bb->index] = BITMAP_ALLOC (NULL); m_incoming[bb->index] = BITMAP_ALLOC (NULL); // If this block's last statement may generate range informaiton, go // calculate it. gimple *s = gimple_outgoing_range_stmt_p (bb); if (!s) return; if (is_a (s)) { gcond *gc = as_a(s); name = gimple_range_ssa_p (gimple_cond_lhs (gc)); maybe_add_gori (name, gimple_bb (s)); name = gimple_range_ssa_p (gimple_cond_rhs (gc)); maybe_add_gori (name, gimple_bb (s)); } else { gswitch *gs = as_a(s); name = gimple_range_ssa_p (gimple_switch_index (gs)); maybe_add_gori (name, gimple_bb (s)); } } // Dump the table information for BB to file F. void gori_map::dump(FILE *f, basic_block bb) { tree t; bool header = false; const char *header_string = "bb%-4d "; const char *header2 = " "; bool printed_something = false;; unsigned x, y; bitmap_iterator bi; if (!m_outgoing[bb->index]) { fprintf (f, "bb%d was not processed.\n", bb->index); return; } // Dump the def chain for each SSA_NAME defined in BB. for (x = 1; x < num_ssa_names; x++) { tree name = ssa_name (x); if (!name) continue; gimple *stmt = SSA_NAME_DEF_STMT (name); bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL); if (stmt && gimple_bb (stmt) == bb && chain && !bitmap_empty_p (chain)) { fprintf (f, header_string, bb->index); header_string = header2; header = true; print_generic_expr (f, name, TDF_SLIM); if ((t = terminal_name (name))) { fprintf (f, " : (terminal "); print_generic_expr (f, t, TDF_SLIM); fprintf (f, ")"); } fprintf (f, " : "); EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi) { print_generic_expr (f, ssa_name (y), TDF_SLIM); fprintf (f, " "); } fprintf (f, "\n"); } } printed_something |= header; // Now dump the incoming vector. header = false; EXECUTE_IF_SET_IN_BITMAP (m_incoming[bb->index], 0, y, bi) { if (!header) { fprintf (f, header_string, bb->index); fprintf (f, "imports: "); header_string = header2; header = true; } print_generic_expr (f, ssa_name (y), TDF_SLIM); fprintf (f, " "); } if (header) fputc ('\n', f); // Now dump the export vector. printed_something |= header; header = false; EXECUTE_IF_SET_IN_BITMAP (m_outgoing[bb->index], 0, y, bi) { if (!header) { fprintf (f, header_string, bb->index); fprintf (f, "exports: "); header_string = header2; header = true; } print_generic_expr (f, ssa_name (y), TDF_SLIM); fprintf (f, " "); } if (header) fputc ('\n', f); printed_something |= header; if (printed_something) fprintf (f, "\n"); } // Dump the entire GORI map structure to file F. // void gori_map::dump(FILE *f) { basic_block bb; FOR_EACH_BB_FN (bb, cfun) { dump (f, bb); fprintf (f, "\n"); } } DEBUG_FUNCTION void debug (gori_map &g) { g.dump (stderr); } // Return the legacy global known value for NAME in R. void gori_compute::range_of_ssa_name (value_range_base &r, tree name, gimple *s ATTRIBUTE_UNUSED) { r = gimple_range_global (name); } // This function returns a range for a tree node. If optional // statement S is present, then the range would be if it were to // appear as a use on S. Return false if ranges are not supported for // the type of EXPR. bool gori_compute::range_of_expr (value_range_base &r, tree expr, gimple *s) { tree type; if (TYPE_P (expr)) type = expr; else type = TREE_TYPE (expr); // Return false if the type isn't suported. if (!value_range_base::supports_type_p (type)) return false; switch (TREE_CODE (expr)) { case INTEGER_CST: // If we encounter an overflow, simply punt and drop to varying // since we have no idea how it will be used. if (!TREE_OVERFLOW_P (expr)) { r = value_range_base (expr, expr); return true; } break; case SSA_NAME: range_of_ssa_name (r, expr, s); return true; case ADDR_EXPR: { // Handle &var which can show up in phi arguments. bool ov; if (tree_single_nonzero_warnv_p (expr, &ov)) { r = range_nonzero (type); return true; } break; } default: break; } r = value_range_base (type); return true; } // Same as range_of_expr, but no statement option, and perform // substitution of NAME with RANGE_OF_NAME if expr happens to match // it. Since there is no statement, this enforces that ranges for // ssa-names invoked wont go off and calculate a range in derived // bases. value_range_base gori_compute::get_tree_range (tree expr, tree name, const value_range_base *range_of_name) { value_range_base r; if (expr == name && range_of_name) return *range_of_name; gcc_assert (range_of_expr (r, expr)); return r; } // Calculate the range for NAME if the lhs of statement S has the // range LHS. If present, NAME_RANGE is any known range for NAME // coming into this stmt. Return the result in R. Return false if no // range can be calculated. bool gori_compute::compute_name_range_op (value_range_base &r, gimple *s, const value_range_base &lhs, tree name, const value_range_base *name_range) { value_range_base op1_range, op2_range; tree op1 = gimple_range_operand1 (s); tree op2 = gimple_range_operand2 (s); // Operand 1 is the name being looked for, evaluate it. if (op1 == name) { if (!op2) { // The second parameter to a unary operation is the range // for the type of operand1, but if it can be reduced // further, the results will be better. Start with what we // know of the range of OP1. op1_range = get_tree_range (op1, name, name_range); return gimple_range_calc_op1 (s, r, lhs, op1_range); } // If we need the second operand, get a value and evaluate. op2_range = get_tree_range (op2, name, name_range); if (gimple_range_calc_op1 (s, r, lhs, op2_range)) { // If op1 also has a range, intersect the 2 ranges. if (name_range) r.intersect (*name_range); return true; } return false; } if (op2 == name) { op1_range = get_tree_range (op1, name, name_range); if (gimple_range_calc_op2 (s, r, lhs, op1_range)) { // If op2 also has a range, intersect the 2 ranges. if (name_range) r.intersect (*name_range); return true; } } return false; } // Construct a gori_compute object. gori_compute::gori_compute () { // Create a boolean_type true and false range. m_bool_zero = value_range_base (boolean_false_node, boolean_false_node); m_bool_one = value_range_base (boolean_true_node, boolean_true_node); } // Destruct a gori_compute_object gori_compute::~gori_compute () { } // Given the statement S, return an evaluation in R for NAME when the // lhs evaluates to LHS. Returning false means the name being looked // for was not resolvable. If present, NAME_RANGE is any known range // for NAME coming into S. bool gori_compute::compute_operand_range (value_range_base &r, gimple *s, const value_range_base &lhs, tree name, const value_range_base *name_range) { if (gimple_range_handler (s)) return compute_operand_range_op (r, s, lhs, name, name_range); if (is_a (s)) return compute_operand_range_switch (r, as_a (s), lhs, name, name_range); return false; } // Given the switch S, return an evaluation in R for NAME when the lhs // evaluates to LHS. Returning false means the name being looked for // was not resolvable. If present, NAME_RANGE is any known range for // NAME coming into S. bool gori_compute::compute_operand_range_switch (value_range_base &r, gswitch *s, const value_range_base &lhs, tree name, const value_range_base *name_range) { tree op1 = gimple_switch_index (s); // If name matches, the range is simply the range from the edge. // Empty ranges are viral as they are on a path which isn't // executable. if (op1 == name || lhs.undefined_p ()) { r = lhs; // If this is also the terminal if (name && name_range) r.intersect (*name_range); return true; } // If op1 is in the defintion chain, pass lhs back. if (gimple_range_ssa_p (op1) && m_gori_map.in_chain_p (name, op1)) return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, name_range); return false; } // Return TRUE if GS is a logical && or || expression. static inline bool is_gimple_logical_p (const gimple *gs) { /* Look for boolean and/or condition. */ if (gimple_code (gs) == GIMPLE_ASSIGN) switch (gimple_expr_code (gs)) { case TRUTH_AND_EXPR: case TRUTH_OR_EXPR: return true; case BIT_AND_EXPR: case BIT_IOR_EXPR: // Bitwise operations on single bits are logical too. if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)), boolean_type_node)) return true; break; default: break; } return false; } // Given the range_op S, return an evaluation in R for NAME when the // lhs evaluates to LHS. Returning false means the name being looked // for was not resolvable. If present, NAME_RANGE is any known range // for NAME coming into S. bool gori_compute::compute_operand_range_op (value_range_base &r, gimple *stmt, const value_range_base &lhs, tree name, const value_range_base *name_range) { tree op1, op2; bool op1_in_chain, op2_in_chain; // Empty ranges are viral as they are on a path which isn't executable. if (lhs.undefined_p ()) { r.set_undefined (); return true; } op1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); op2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); // The base ranger handles NAME on this statement. if (op1 == name || op2 == name) return compute_name_range_op (r, stmt, lhs, name, name_range); // Check for logical combination cases which require developing // ranges and combining the results based on the operation. if (is_gimple_logical_p (stmt)) return compute_logical_operands (r, stmt, lhs, name, name_range); // Reaching this point means NAME is not in this stmt, but one of // the names in it ought to be derived from it. op1_in_chain = op1 && m_gori_map.in_chain_p (name, op1); op2_in_chain = op2 && m_gori_map.in_chain_p (name, op2); if (op2_in_chain) { if (op1_in_chain) return compute_operand1_and_operand2_range (r, stmt, lhs, name, name_range); else return compute_operand2_range (r, stmt, lhs, name, name_range); } else if (op1_in_chain) return compute_operand1_range (r, stmt, lhs, name, name_range); // If neither operand is derived, then this stmt tells us nothing. return false; } // Evaluate a binary logical expression by combining the true and // false ranges for each of the operands based on the result value in // the LHS. bool gori_compute::logical_combine (value_range_base &r, enum tree_code code, const value_range_base &lhs, const value_range_base &op1_true, const value_range_base &op1_false, const value_range_base &op2_true, const value_range_base &op2_false) { // This is not a simple fold of a logical expression, rather it // determines ranges which flow through the logical expression. // // Assuming x_8 is an unsigned char, and relational statements: // b_1 = x_8 < 20 // b_2 = x_8 > 5 // consider the logical expression and branch: // c_2 = b_1 && b_2 // if (c_2) // // To determine the range of x_8 on either edge of the branch, one // must first determine what the range of x_8 is when the boolean // values of b_1 and b_2 are both true and false. // b_1 TRUE x_8 = [0, 19] // b_1 FALSE x_8 = [20, 255] // b_2 TRUE x_8 = [6, 255] // b_2 FALSE x_8 = [0,5]. // // These ranges are then combined based on the expected outcome of // the branch The range on the TRUE side of the branch must satisfy // b_1 == true && b_2 == true // in terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255] // must be true. The range of x_8 on the true side must be the // intersection of both ranges since both must be true. Thus the // range of x_8 on the true side is [6, 19] // // To determine the ranges on the FALSE side, all 3 combinations of // failing ranges must be considered, and combined as any of them // can cause the false result. // If the LHS can be TRUE OR FALSE, then evaluate both a TRUE and // FALSE results and combine them. If we fell back to VARYING any // range restrictions that have been discovered up to this point // would be lost. */ if (!lhs.singleton_p ()) { value_range_base r1; if (logical_combine (r1, code, m_bool_zero, op1_true, op1_false, op2_true, op2_false) && logical_combine (r, code, m_bool_one, op1_true, op1_false, op2_true, op2_false)) { r.union_ (r1); return true; } return false; } switch (code) { // A logical AND combines ranges from 2 boolean conditions. // c_2 = b_1 && b_2 case TRUTH_AND_EXPR: case BIT_AND_EXPR: if (!lhs.zero_p ()) // The TRUE side is the intersection of the the 2 true ranges. r = range_intersect (op1_true, op2_true); else { // The FALSE side is the union of the other 3 cases. value_range_base ff = range_intersect (op1_false, op2_false); value_range_base tf = range_intersect (op1_true, op2_false); value_range_base ft = range_intersect (op1_false, op2_true); r = range_union (ff, tf); r.union_ (ft); } break; // A logical OR combines ranges from 2 boolean conditons. // c_2 = b_1 || b_2 case TRUTH_OR_EXPR: case BIT_IOR_EXPR: if (lhs.zero_p ()) // An OR operation will only take the FALSE path if both // operands are false. so [20, 255] intersect [0, 5] is the // union: [0,5][20,255]. */ r = range_intersect (op1_false, op2_false); else { // The TRUE side of an OR operation will be the union of // the other three combinations. value_range_base tt = range_intersect (op1_true, op2_true); value_range_base tf = range_intersect (op1_true, op2_false); value_range_base ft = range_intersect (op1_false, op2_true); r = range_union (tt, tf); r.union_ (ft); } break; default: gcc_unreachable (); } return true; } // Given a logical STMT, calculate true and false for each potential // path using NAME and resolve the outcome based on the logical // operator. If present, NAME_RANGE is any known range for NAME // coming into S. bool gori_compute::compute_logical_operands (value_range_base &r, gimple *s, const value_range_base &lhs, tree name, const value_range_base *name_range) { value_range_base op1_range, op2_range; tree op1, op2; bool op1_in_chain, op2_in_chain; bool ret = true; const unsigned depth_limit = 6; // Max depth of logical recursion. static unsigned depth = 0; // Current depth of recursion. value_range_base op1_true, op1_false, op2_true, op2_false; // Reaching this point means NAME is not in this stmt, but one of // the names in it ought to be derived from it. */ op1 = gimple_range_operand1 (s); op2 = gimple_range_operand2 (s); gcc_checking_assert (op1 != name && op2 != name); op1_in_chain = (gimple_range_ssa_p (op1) && m_gori_map.in_chain_p (name, op1)); op2_in_chain = (gimple_range_ssa_p (op2) && m_gori_map.in_chain_p (name, op2)); // If neither operand is derived, then this stmt tells us nothing. if (!op1_in_chain && !op2_in_chain) return false; // Long chains of nested logical expressions rarely produce good // ranges but can take exponential times to compute since we are // recursively evaluating them for the true and false result. If // the depth is too great simply terminate the calculation. See gcc // testcase rvrp-logic-1.c. if (depth > depth_limit) { r.set_varying (TREE_TYPE (name)); return true; } depth++; // The false path is not always a simple inversion of the true side. // Calulate ranges for true and false on both sides. if (op1_in_chain) { ret = compute_operand_range (op1_true, SSA_NAME_DEF_STMT (op1), m_bool_one, name, name_range); ret &= compute_operand_range (op1_false, SSA_NAME_DEF_STMT (op1), m_bool_zero, name, name_range); } else { // Otherwise just get the value for name in operand 1 position op1_true = get_tree_range (name, name, name_range); op1_false = op1_true; } // If operand1 evaluated OK, move on to operand 2. if (ret) { if (op2_in_chain) { ret &= compute_operand_range (op2_true, SSA_NAME_DEF_STMT (op2), m_bool_one, name, name_range); ret &= compute_operand_range (op2_false, SSA_NAME_DEF_STMT (op2), m_bool_zero, name, name_range); } else { // Otherwise just get the value for name in operand 2 // position. op2_true = get_tree_range (name, name, name_range); op2_false = op2_true; } } if (!ret || !logical_combine (r, gimple_expr_code (s), lhs, op1_true, op1_false, op2_true, op2_false)) r.set_varying (TREE_TYPE (name)); depth--; return true; } // Calculate a range for NAME from the operand 1 position of S // assuming the result of the statement is LHS. Return the range in // R, or false if no range could be calculated. If present, // NAME_RANGE is any known range for NAME coming into S. bool gori_compute::compute_operand1_range (value_range_base &r, gimple *s, const value_range_base &lhs, tree name, const value_range_base *name_range) { value_range_base op1_range, op2_range; tree op1 = gimple_range_operand1 (s); tree op2 = gimple_range_operand2 (s); // Determine a known range for operand1 (). op1_range = get_tree_range (op1, name, name_range); // Now calcuated the operand and put that result in r. if (!op2) { // we pass op1_range to the unary operation. Nomally it's a // hidden range_for_type parameter, but sometimes having the // actual range can result in better information. if (!gimple_range_calc_op1 (s, r, lhs, op1_range)) return false; } else { op2_range = get_tree_range (op2, name, name_range); if (!gimple_range_calc_op1 (s, r, lhs, op2_range)) return false; } // Intersect the calculated result with the known result. op1_range.intersect (r); // Then feed this range back as the LHS of the defining statement. return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), op1_range, name, name_range); } // Calculate a range for NAME from the operand 2 position of S // assuming the result of the statement is LHS. Return the range in // R, or false if no range could be calculated. If present, // NAME_RANGE is any known range for NAME coming into S. bool gori_compute::compute_operand2_range (value_range_base &r, gimple *s, const value_range_base &lhs, tree name, const value_range_base *name_range) { value_range_base op1_range, op2_range; tree op1 = gimple_range_operand1 (s); tree op2 = gimple_range_operand2 (s); // Get a range for op1. op1_range = get_tree_range (op1, name, name_range); // calculate the range for op2 based on lhs and op1. if (!gimple_range_calc_op2 (s, op2_range, lhs, op1_range)) return false; // Also pick up what is known about op2's range at this point r = get_tree_range (op2, name, name_range); // And intersect it with the calculated result. op2_range.intersect (r); // Then feed this range back as the LHS of the defining statement. return compute_operand_range (r, SSA_NAME_DEF_STMT (op2), op2_range, name, name_range); } // Calculate a range for NAME from both operand positions of S // assuming the result of the statement is LHS. Return the range in // R, or false if no range could be calculated. If present, // NAME_RANGE is any known range for NAME coming into S. bool gori_compute::compute_operand1_and_operand2_range (value_range_base &r, gimple *s, const value_range_base &lhs, tree name, const value_range_base *name_range) { value_range_base op_range; // Calculate a good a range for op2. Since op1 == op2, this will // have already included whatever the actual range of name is. if (!compute_operand2_range (op_range, s, lhs, name, name_range)) return false; // Now get the range thru op1... if (!compute_operand1_range (r, s, lhs, name, name_range)) return false; // Whichever range is the most permissive is the one we need to // use. (?) OR is that true? Maybe this should be intersection? r.union_ (op_range); return true; } bool gori_compute::has_edge_range_p (edge e, tree name) { return (m_gori_map.is_export_p (name, e->src) || m_gori_map.def_chain_in_export_p (name, e->src)); } // Calculate a range on edge E and return it in R. Try to evaluate a // range for NAME on this edge. Return FALSE if this is either not a // control edge or NAME is not defined by this edge. bool gori_compute::outgoing_edge_range_p (value_range_base &r, edge e, tree name, const value_range_base *name_range) { value_range_base lhs; gcc_checking_assert (gimple_range_ssa_p (name)); // Determine if there is an outgoing edge. gimple *s = gimple_outgoing_edge_range_p (lhs, e); if (!s) return false; // If NAME can be calculated on the edge, use that. if (m_gori_map.is_export_p (name, e->src)) return compute_operand_range (r, s, lhs, name, name_range); // Otherwise see if NAME is derived from something that can be // calculated. This performs no dynamic lookups whatsover, so it is // low cost. return false; }