From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id 8CFED385E823; Tue, 1 Jun 2021 01:31:54 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8CFED385E823 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Andrew Macleod To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-1135] Move Ranger cache to range-query and fur_source model. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: 1ffbfc2659e7e8fa5c5d633869870af8fca5e8ee X-Git-Newrev: 47ea02bb862d6be9a200ebccbd5d64b31a003ec2 Message-Id: <20210601013154.8CFED385E823@sourceware.org> Date: Tue, 1 Jun 2021 01:31:54 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 01 Jun 2021 01:31:54 -0000 https://gcc.gnu.org/g:47ea02bb862d6be9a200ebccbd5d64b31a003ec2 commit r12-1135-g47ea02bb862d6be9a200ebccbd5d64b31a003ec2 Author: Andrew MacLeod Date: Mon May 31 16:00:16 2021 -0400 Move Ranger cache to range-query and fur_source model. Flatten and simplify gori-computes. Tweak debug output. range-cache now provides range_of_expr and range_on_edge in the standard formats, but in a "query what you have" mode rather than "go figure out anything that is missing" mode. * gimple-range-cache.cc (ranger_cache::ranger_cache): Adjust for gori_compute being a member rather than base class. dervied call to member call. (ranger_cache::dump): No longer dump gori_map. (ranger_cache::dump_bb): New. (ranger_cache::get_non_stale_global_range): Adjust for gori_compute being a member rather than base class. (ranger_cache::set_global_range): Ditto. (ranger_cache::ssa_range_in_bb): Ditto. (ranger_cache::range_of_expr): New. (ranger_cache::range_on_edge): New. (ranger_cache::block_range): Adjust for gori_computes. Debug changes. (ranger_cache::propagate_cache): Adjust debugging output. (ranger_cache::fill_block_cache): Adjust for gori_computes. Debug output changes. * gimple-range-cache.h (class ranger_cache): Make gori_compute a member, and inherit from range_query instead. (ranger_cache::dump_bb): New. split from dump. * gimple-range-gori.cc (gori_compute::ssa_range_in_bb): Delete. (gori_compute::expr_range_at_stmt): Delete. (gori_compute::compute_name_range_op): Delete. (gori_compute::compute_operand_range_switch): Add fur_source. (gori_compute::compute_operand_range): Add fur_source param, inline old compute_name_range_op and optimize_logical_operands. (struct tf_range): Delete. (gori_compute::logical_combine): Adjust (gori_compute::optimize_logical_operands): Delete. (gori_compute::compute_logical_operands_in_chain): Delete. (gori_compute::compute_logical_operands): Adjust. (gori_compute::compute_operand1_range): Adjust to fur_source. (gori_compute::compute_operand2_range): Ditto. (gori_compute::compute_operand1_and_operand2_range): Ditto. (gori_compute::outgoing_edge_range_p): Add range_query parameter, and adjust to fur_source. * gimple-range-gori.h (class gori_compute): Simplify and adjust to range_query and fur_source. * gimple-range.cc (gimple_ranger::range_on_edge): Query range_on_edge from the ranger_cache.. (gimple_ranger::fold_range_internal): Adjust to base class change of ranger_cache. (gimple_ranger::dump_bb): Adjust dump. * gimple-range.h (gimple_ranger):export gori computes object. Diff: --- gcc/gimple-range-cache.cc | 79 ++++++---- gcc/gimple-range-cache.h | 11 +- gcc/gimple-range-gori.cc | 371 +++++++++++++++++----------------------------- gcc/gimple-range-gori.h | 47 +++--- gcc/gimple-range.cc | 10 +- gcc/gimple-range.h | 3 +- 6 files changed, 223 insertions(+), 298 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index ef3bc044891..e776bed139b 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -583,7 +583,7 @@ ranger_cache::ranger_cache (gimple_ranger &q) : query (q) { basic_block bb = BASIC_BLOCK_FOR_FN (cfun, x); if (bb) - exports (bb); + m_gori.exports (bb); } } @@ -599,22 +599,18 @@ ranger_cache::~ranger_cache () // gori map as well. void -ranger_cache::dump (FILE *f, bool gori_dump) +ranger_cache::dump (FILE *f) { m_globals.dump (f); - if (gori_dump) - { - fprintf (f, "\nDUMPING GORI MAP\n"); - gori_compute::dump (f); - } fprintf (f, "\n"); } // Dump the caches for basic block BB to file F. void -ranger_cache::dump (FILE *f, basic_block bb) +ranger_cache::dump_bb (FILE *f, basic_block bb) { + m_gori.gori_map::dump (f, bb, false); m_on_entry.dump (f, bb); } @@ -641,7 +637,8 @@ ranger_cache::get_non_stale_global_range (irange &r, tree name) { // Use this value if the range is constant or current. if (r.singleton_p () - || m_temporal->current_p (name, depend1 (name), depend2 (name))) + || m_temporal->current_p (name, m_gori.depend1 (name), + m_gori.depend2 (name))) return true; } else @@ -681,7 +678,7 @@ ranger_cache::set_global_range (tree name, const irange &r) if (r.singleton_p () || (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ())) - set_range_invariant (name); + m_gori.set_range_invariant (name); m_temporal->set_timestamp (name); } @@ -745,7 +742,7 @@ ranger_cache::ssa_range_in_bb (irange &r, tree name, basic_block bb) // If it has no entry but should, then mark this as a poor value. // Its not a poor value if it does not have *any* edge ranges, // Then global range is as good as it gets. - if (has_edge_range_p (name) && push_poor_value (bb, name)) + if (m_gori.has_edge_range_p (name) && push_poor_value (bb, name)) { if (DEBUG_RANGE_CACHE) { @@ -759,7 +756,6 @@ ranger_cache::ssa_range_in_bb (irange &r, tree name, basic_block bb) if (!m_globals.get_global_range (r, name)) r = gimple_range_global (name); } - // Check if pointers have any non-null dereferences. Non-call // exceptions mean we could throw in the middle of the block, so just // punt for now on those. @@ -768,6 +764,29 @@ ranger_cache::ssa_range_in_bb (irange &r, tree name, basic_block bb) r = range_nonzero (TREE_TYPE (name)); } +// Implement range_of_expr. + +bool +ranger_cache::range_of_expr (irange &r, tree expr, gimple *stmt) +{ + if (gimple_range_ssa_p (expr)) + ssa_range_in_bb (r, expr, gimple_bb (stmt)); + else + get_tree_range (r, expr); + return true; +} + +// Implement range_on_edge which returns true ONLY if there is a range +// calculated. + +bool +ranger_cache::range_on_edge (irange &r, edge e, tree expr) +{ + if (gimple_range_ssa_p (expr)) + return m_gori.outgoing_edge_range_p (r, e, expr, *this); + return false; +} + // Return a static range for NAME on entry to basic block BB in R. If // calc is true, fill any cache entries required between BB and the // def block for NAME. Otherwise, return false if the cache is empty. @@ -779,7 +798,7 @@ ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc) // If there are no range calculations anywhere in the IL, global range // applies everywhere, so don't bother caching it. - if (!has_edge_range_p (name)) + if (!m_gori.has_edge_range_p (name)) return false; if (calc) @@ -842,6 +861,15 @@ ranger_cache::propagate_cache (tree name) gcc_checking_assert (m_on_entry.bb_range_p (name, bb)); m_on_entry.get_bb_range (current_range, name, bb); + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "FWD visiting block %d for ", bb->index); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " starting range : "); + current_range.dump (dump_file); + fprintf (dump_file, "\n"); + } + // Calculate the "new" range on entry by unioning the pred edges. new_range.set_undefined (); FOR_EACH_EDGE (e, ei, bb->preds) @@ -849,13 +877,13 @@ ranger_cache::propagate_cache (tree name) if (DEBUG_RANGE_CACHE) fprintf (dump_file, " edge %d->%d :", e->src->index, bb->index); // Get whatever range we can for this edge. - if (!outgoing_edge_range_p (e_range, e, name)) + if (!m_gori.outgoing_edge_range_p (e_range, e, name, *this)) { ssa_range_in_bb (e_range, name, e->src); if (DEBUG_RANGE_CACHE) { fprintf (dump_file, "No outgoing edge range, picked up "); - e_range.dump(dump_file); + e_range.dump (dump_file); fprintf (dump_file, "\n"); } } @@ -864,7 +892,7 @@ ranger_cache::propagate_cache (tree name) if (DEBUG_RANGE_CACHE) { fprintf (dump_file, "outgoing range :"); - e_range.dump(dump_file); + e_range.dump (dump_file); fprintf (dump_file, "\n"); } } @@ -873,15 +901,6 @@ ranger_cache::propagate_cache (tree name) break; } - if (DEBUG_RANGE_CACHE) - { - fprintf (dump_file, "FWD visiting block %d for ", bb->index); - print_generic_expr (dump_file, name, TDF_SLIM); - fprintf (dump_file, " starting range : "); - current_range.dump (dump_file); - fprintf (dump_file, "\n"); - } - // If the range on entry has changed, update it. if (new_range != current_range) { @@ -1042,8 +1061,12 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) if (m_on_entry.get_bb_range (r, name, pred)) { if (DEBUG_RANGE_CACHE) - fprintf (dump_file, "has cache, "); - if (!r.undefined_p () || has_edge_range_p (name, e)) + { + fprintf (dump_file, "has cache, "); + r.dump (dump_file); + fprintf (dump_file, ", "); + } + if (!r.undefined_p () || m_gori.has_edge_range_p (name, e)) { add_to_update (node); if (DEBUG_RANGE_CACHE) @@ -1053,7 +1076,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) } if (DEBUG_RANGE_CACHE) - fprintf (dump_file, "pushing undefined pred block. "); + fprintf (dump_file, "pushing undefined pred block.\n"); // If the pred hasn't been visited (has no range), add it to // the list. gcc_checking_assert (!m_on_entry.bb_range_p (name, pred)); diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index fe781e0ad1b..ac50219d1dd 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -86,13 +86,15 @@ private: // them available for gori-computes to query so outgoing edges can be // properly calculated. -class ranger_cache : public gori_compute +class ranger_cache : public range_query { public: ranger_cache (class gimple_ranger &q); ~ranger_cache (); - virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb); + virtual bool range_of_expr (irange &r, tree expr, gimple *stmt); + virtual bool range_on_edge (irange &r, edge e, tree expr); + void ssa_range_in_bb (irange &r, tree name, basic_block bb); bool block_range (irange &r, basic_block bb, tree name, bool calc = true); bool get_global_range (irange &r, tree name) const; @@ -100,9 +102,10 @@ public: void set_global_range (tree name, const irange &r); non_null_ref m_non_null; + gori_compute m_gori; - void dump (FILE *f, bool dump_gori = true); - void dump (FILE *f, basic_block bb); + void dump_bb (FILE *f, basic_block bb); + virtual void dump (FILE *f) OVERRIDE; private: ssa_global_cache m_globals; block_range_cache m_on_entry; diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index c51e6ce0697..2c5360690db 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -575,68 +575,6 @@ gori_compute::gori_compute () m_bool_one = int_range<2> (boolean_true_node, boolean_true_node); } -// Provide a default of VARYING for all incoming SSA names. - -void -gori_compute::ssa_range_in_bb (irange &r, tree name, basic_block) -{ - r.set_varying (TREE_TYPE (name)); -} - -void -gori_compute::expr_range_at_stmt (irange &r, tree expr, gimple *s) -{ - if (gimple_range_ssa_p (expr)) - ssa_range_in_bb (r, expr, gimple_bb (s)); - else - get_tree_range (r, expr); -} - -// Calculate the range for NAME if the lhs of statement S has the -// range LHS. Return the result in R. Return false if no range can be -// calculated. - -bool -gori_compute::compute_name_range_op (irange &r, gimple *stmt, - const irange &lhs, tree name) -{ - int_range_max op1_range, op2_range; - - tree op1 = gimple_range_operand1 (stmt); - tree op2 = gimple_range_operand2 (stmt); - - // Operand 1 is the name being looked for, evaluate it. - if (op1 == name) - { - expr_range_at_stmt (op1_range, op1, stmt); - 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 instead of the full type. - return gimple_range_calc_op1 (r, stmt, lhs, op1_range); - } - // If we need the second operand, get a value and evaluate. - expr_range_at_stmt (op2_range, op2, stmt); - if (gimple_range_calc_op1 (r, stmt, lhs, op2_range)) - r.intersect (op1_range); - else - r = op1_range; - return true; - } - - if (op2 == name) - { - expr_range_at_stmt (op1_range, op1, stmt); - expr_range_at_stmt (r, op2, stmt); - if (gimple_range_calc_op2 (op2_range, stmt, lhs, op1_range)) - r.intersect (op2_range); - return true; - } - 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. @@ -644,7 +582,7 @@ gori_compute::compute_name_range_op (irange &r, gimple *stmt, bool gori_compute::compute_operand_range_switch (irange &r, gswitch *s, const irange &lhs, - tree name) + tree name, fur_source &src) { tree op1 = gimple_switch_index (s); @@ -659,7 +597,7 @@ gori_compute::compute_operand_range_switch (irange &r, gswitch *s, // If op1 is in the defintion chain, pass lhs back. if (gimple_range_ssa_p (op1) && in_chain_p (name, op1)) - return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name); + return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src); return false; } @@ -671,8 +609,13 @@ gori_compute::compute_operand_range_switch (irange &r, gswitch *s, bool gori_compute::compute_operand_range (irange &r, gimple *stmt, - const irange &lhs, tree name) + const irange &lhs, tree name, + fur_source &src) { + // If the lhs doesn't tell us anything, neither will unwinding further. + if (lhs.varying_p ()) + return false; + // Empty ranges are viral as they are on an unexecutable path. if (lhs.undefined_p ()) { @@ -680,35 +623,55 @@ gori_compute::compute_operand_range (irange &r, gimple *stmt, return true; } if (is_a (stmt)) - return compute_operand_range_switch (r, as_a (stmt), lhs, name); + return compute_operand_range_switch (r, as_a (stmt), lhs, name, + src); if (!gimple_range_handler (stmt)) return false; tree op1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); tree 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); - - if (is_gimple_logical_p (stmt)) - return compute_logical_operands (r, stmt, lhs, name); + // Handle end of lookup first. + if (op1 == name) + return compute_operand1_range (r, stmt, lhs, name, src); + if (op2 == name) + return compute_operand2_range (r, stmt, lhs, name, src); // NAME is not in this stmt, but one of the names in it ought to be // derived from it. bool op1_in_chain = op1 && in_chain_p (name, op1); bool op2_in_chain = op2 && 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; + + // Process logicals as they have special handling. + if (is_gimple_logical_p (stmt)) + { + int_range_max op1_trange, op1_frange; + int_range_max op2_trange, op2_frange; + compute_logical_operands (op1_trange, op1_frange, stmt, lhs, + name, src, op1, op1_in_chain); + compute_logical_operands (op2_trange, op2_frange, stmt, lhs, + name, src, op2, op2_in_chain); + return logical_combine (r, gimple_expr_code (stmt), lhs, + op1_trange, op1_frange, op2_trange, op2_frange); + } + + // Follow the appropriate operands now. if (op1_in_chain && op2_in_chain) - return compute_operand1_and_operand2_range (r, stmt, lhs, name); + return compute_operand1_and_operand2_range (r, stmt, lhs, name, src); if (op1_in_chain) - return compute_operand1_range (r, stmt, lhs, name); + return compute_operand1_range (r, stmt, lhs, name, src); if (op2_in_chain) - return compute_operand2_range (r, stmt, lhs, name); + return compute_operand2_range (r, stmt, lhs, name, src); // If neither operand is derived, this statement tells us nothing. return false; } + // Return TRUE if range R is either a true or false compatible range. static bool @@ -724,19 +687,6 @@ range_is_either_true_or_false (const irange &r) return (r.singleton_p () || !r.contains_p (build_zero_cst (type))); } -// A pair of ranges for true/false paths. - -struct tf_range -{ - tf_range () { } - tf_range (const irange &t_range, const irange &f_range) - { - true_range = t_range; - false_range = f_range; - } - int_range_max true_range, false_range; -}; - // 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. @@ -744,12 +694,11 @@ struct tf_range bool gori_compute::logical_combine (irange &r, enum tree_code code, const irange &lhs, - const tf_range &op1, const tf_range &op2) + const irange &op1_true, const irange &op1_false, + const irange &op2_true, const irange &op2_false) { - if (op1.true_range.varying_p () - && op1.false_range.varying_p () - && op2.true_range.varying_p () - && op2.false_range.varying_p ()) + if (op1_true.varying_p () && op1_false.varying_p () + && op2_true.varying_p () && op2_false.varying_p ()) return false; // This is not a simple fold of a logical expression, rather it @@ -790,8 +739,10 @@ gori_compute::logical_combine (irange &r, enum tree_code code, if (!range_is_either_true_or_false (lhs)) { int_range_max r1; - if (logical_combine (r1, code, m_bool_zero, op1, op2) - && logical_combine (r, code, m_bool_one, op1, op2)) + 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; @@ -808,18 +759,18 @@ gori_compute::logical_combine (irange &r, enum tree_code code, if (!lhs.zero_p ()) { // The TRUE side is the intersection of the the 2 true ranges. - r = op1.true_range; - r.intersect (op2.true_range); + r = op1_true; + r.intersect (op2_true); } else { // The FALSE side is the union of the other 3 cases. - int_range_max ff (op1.false_range); - ff.intersect (op2.false_range); - int_range_max tf (op1.true_range); - tf.intersect (op2.false_range); - int_range_max ft (op1.false_range); - ft.intersect (op2.true_range); + int_range_max ff (op1_false); + ff.intersect (op2_false); + int_range_max tf (op1_true); + tf.intersect (op2_false); + int_range_max ft (op1_false); + ft.intersect (op2_true); r = ff; r.union_ (tf); r.union_ (ft); @@ -834,19 +785,19 @@ gori_compute::logical_combine (irange &r, enum tree_code code, // An OR operation will only take the FALSE path if both // operands are false simlulateously, which means they should // be intersected. !(x || y) == !x && !y - r = op1.false_range; - r.intersect (op2.false_range); + r = op1_false; + r.intersect (op2_false); } else { // The TRUE side of an OR operation will be the union of // the other three combinations. - int_range_max tt (op1.true_range); - tt.intersect (op2.true_range); - int_range_max tf (op1.true_range); - tf.intersect (op2.false_range); - int_range_max ft (op1.false_range); - ft.intersect (op2.true_range); + int_range_max tt (op1_true); + tt.intersect (op2_true); + int_range_max tf (op1_true); + tf.intersect (op2_false); + int_range_max ft (op1_false); + ft.intersect (op2_true); r = tt; r.union_ (tf); r.union_ (ft); @@ -859,103 +810,54 @@ gori_compute::logical_combine (irange &r, enum tree_code code, return true; } -// Helper function for compute_logical_operands_in_chain that computes -// the range of logical statements that can be computed without -// chasing down operands. These are things like [0 = x | y] where we -// know neither operand can be non-zero, or [1 = x & y] where we know -// neither operand can be zero. - -bool -gori_compute::optimize_logical_operands (tf_range &range, - gimple *stmt, - const irange &lhs, - tree name, - tree op) -{ - enum tree_code code = gimple_expr_code (stmt); - - // Optimize [0 = x | y], since neither operand can ever be non-zero. - if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ()) - { - if (!compute_operand_range (range.false_range, SSA_NAME_DEF_STMT (op), - m_bool_zero, name)) - expr_range_at_stmt (range.false_range, name, stmt); - range.true_range = range.false_range; - return true; - } - // Optimize [1 = x & y], since neither operand can ever be zero. - if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one) - { - if (!compute_operand_range (range.true_range, SSA_NAME_DEF_STMT (op), - m_bool_one, name)) - expr_range_at_stmt (range.true_range, name, stmt); - range.false_range = range.true_range; - return true; - } - return false; -} // Given a logical STMT, calculate true and false ranges for each // potential path of NAME, assuming NAME came through the OP chain if // OP_IN_CHAIN is true. void -gori_compute::compute_logical_operands_in_chain (tf_range &range, - gimple *stmt, - const irange &lhs, - tree name, - tree op, bool op_in_chain) +gori_compute::compute_logical_operands (irange &true_range, irange &false_range, + gimple *stmt, + const irange &lhs, + tree name, fur_source &src, + tree op, bool op_in_chain) { gimple *src_stmt = gimple_range_ssa_p (op) ? SSA_NAME_DEF_STMT (op) : NULL; - if (!op_in_chain || (src_stmt != NULL - && gimple_bb (stmt) != gimple_bb (src_stmt))) + if (!op_in_chain || !src_stmt || chain_import_p (gimple_get_lhs (stmt), op)) { // If op is not in the def chain, or defined in this block, // use its known value on entry to the block. - expr_range_at_stmt (range.true_range, name, stmt); - range.false_range = range.true_range; + src.get_operand (true_range, name); + false_range = true_range; return; } - if (optimize_logical_operands (range, stmt, lhs, name, op)) - return; - // Calculate ranges for true and false on both sides, since the false - // path is not always a simple inversion of the true side. - if (!compute_operand_range (range.true_range, src_stmt, m_bool_one, name)) - expr_range_at_stmt (range.true_range, name, stmt); - if (!compute_operand_range (range.false_range, src_stmt, m_bool_zero, name)) - expr_range_at_stmt (range.false_range, name, stmt); -} - -// Given a logical STMT, calculate true and false for each potential -// path using NAME, and resolve the outcome based on the logical -// operator. - -bool -gori_compute::compute_logical_operands (irange &r, gimple *stmt, - const irange &lhs, - tree name) -{ - // Reaching this point means NAME is not in this stmt, but one of - // the names in it ought to be derived from it. - tree op1 = gimple_range_operand1 (stmt); - tree op2 = gimple_range_operand2 (stmt); - gcc_checking_assert (op1 != name && op2 != name); - - bool op1_in_chain = (gimple_range_ssa_p (op1) && in_chain_p (name, op1)); - bool op2_in_chain = (gimple_range_ssa_p (op2) && in_chain_p (name, op2)); + enum tree_code code = gimple_expr_code (stmt); + // Optimize [0 = x | y], since neither operand can ever be non-zero. + if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ()) + { + if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, + src)) + src.get_operand (false_range, name); + true_range = false_range; + return; + } - // If neither operand is derived, then this stmt tells us nothing. - if (!op1_in_chain && !op2_in_chain) - return false; + // Optimize [1 = x & y], since neither operand can ever be zero. + if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one) + { + if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src)) + src.get_operand (true_range, name); + false_range = true_range; + return; + } - tf_range op1_range, op2_range; - compute_logical_operands_in_chain (op1_range, stmt, lhs, - name, op1, op1_in_chain); - compute_logical_operands_in_chain (op2_range, stmt, lhs, - name, op2, op2_in_chain); - return logical_combine (r, gimple_expr_code (stmt), lhs, - op1_range, op2_range); + // Calculate ranges for true and false on both sides, since the false + // path is not always a simple inversion of the true side. + if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src)) + src.get_operand (true_range, name); + if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, src)) + src.get_operand (false_range, name); } // Calculate a range for NAME from the operand 1 position of STMT @@ -964,18 +866,20 @@ gori_compute::compute_logical_operands (irange &r, gimple *stmt, bool gori_compute::compute_operand1_range (irange &r, gimple *stmt, - const irange &lhs, tree name) + const irange &lhs, tree name, + fur_source &src) { int_range_max op1_range, op2_range; tree op1 = gimple_range_operand1 (stmt); tree op2 = gimple_range_operand2 (stmt); - expr_range_at_stmt (op1_range, op1, stmt); + // Fetch the known range for op1 in this block. + src.get_operand (op1_range, op1); - // Now calcuated the operand and put that result in r. + // Now range-op calcuate and put that result in r. if (op2) { - expr_range_at_stmt (op2_range, op2, stmt); + src.get_operand (op2_range, op2); if (!gimple_range_calc_op1 (r, stmt, lhs, op2_range)) return false; } @@ -988,20 +892,20 @@ gori_compute::compute_operand1_range (irange &r, gimple *stmt, return false; } - // Intersect the calculated result with the known result. + // Intersect the calculated result with the known result and return if done. + if (op1 == name) + { + r.intersect (op1_range); + return true; + } + // If the calculation continues, we're using op1_range as the new LHS. op1_range.intersect (r); gimple *src_stmt = SSA_NAME_DEF_STMT (op1); - // If def stmt is outside of this BB, then name must be an import. - if (!src_stmt || (gimple_bb (src_stmt) != gimple_bb (stmt))) - { - // If this isn't the right import statement, then abort calculation. - if (!src_stmt || gimple_get_lhs (src_stmt) != name) - return false; - return compute_name_range_op (r, src_stmt, op1_range, name); - } + gcc_checking_assert (src_stmt); + // Then feed this range back as the LHS of the defining statement. - return compute_operand_range (r, src_stmt, op1_range, name); + return compute_operand_range (r, src_stmt, op1_range, name, src); } @@ -1011,31 +915,35 @@ gori_compute::compute_operand1_range (irange &r, gimple *stmt, bool gori_compute::compute_operand2_range (irange &r, gimple *stmt, - const irange &lhs, tree name) + const irange &lhs, tree name, + fur_source &src) { int_range_max op1_range, op2_range; tree op1 = gimple_range_operand1 (stmt); tree op2 = gimple_range_operand2 (stmt); - expr_range_at_stmt (op1_range, op1, stmt); - expr_range_at_stmt (op2_range, op2, stmt); + src.get_operand (op1_range, op1); + src.get_operand (op2_range, op2); // Intersect with range for op2 based on lhs and op1. if (!gimple_range_calc_op2 (r, stmt, lhs, op1_range)) return false; - op2_range.intersect (r); - gimple *src_stmt = SSA_NAME_DEF_STMT (op2); - // If def stmt is outside of this BB, then name must be an import. - if (!src_stmt || (gimple_bb (src_stmt) != gimple_bb (stmt))) + // Intersect the calculated result with the known result and return if done. + if (op2 == name) { - // If this isn't the right src statement, then abort calculation. - if (!src_stmt || gimple_get_lhs (src_stmt) != name) - return false; - return compute_name_range_op (r, src_stmt, op2_range, name); + r.intersect (op2_range); + return true; } + // If the calculation continues, we're using op2_range as the new LHS. + op2_range.intersect (r); + + gimple *src_stmt = SSA_NAME_DEF_STMT (op2); + gcc_checking_assert (src_stmt); +// gcc_checking_assert (!is_import_p (op2, find.bb)); + // Then feed this range back as the LHS of the defining statement. - return compute_operand_range (r, src_stmt, op2_range, name); + return compute_operand_range (r, src_stmt, op2_range, name, src); } // Calculate a range for NAME from both operand positions of S @@ -1043,29 +951,27 @@ gori_compute::compute_operand2_range (irange &r, gimple *stmt, // R, or false if no range could be calculated. bool -gori_compute::compute_operand1_and_operand2_range - (irange &r, - gimple *stmt, - const irange &lhs, - tree name) +gori_compute::compute_operand1_and_operand2_range (irange &r, + gimple *stmt, + const irange &lhs, + tree name, + fur_source &src) { int_range_max 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, stmt, lhs, name)) + if (!compute_operand2_range (op_range, stmt, lhs, name, src)) return false; // Now get the range thru op1. - if (!compute_operand1_range (r, stmt, lhs, name)) + if (!compute_operand1_range (r, stmt, lhs, name, src)) 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); + // Both operands have to be simultaneously true, so perform an intersection. + r.intersect (op_range); return true; } - // Return TRUE if a range can be calcalated for NAME on edge E. bool @@ -1091,7 +997,8 @@ gori_compute::dump (FILE *f) // control edge or NAME is not defined by this edge. bool -gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name) +gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, + range_query &q) { int_range_max lhs; @@ -1101,10 +1008,12 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name) if (!stmt) return false; + fur_source src (&q, NULL, e, stmt); + // If NAME can be calculated on the edge, use that. if (is_export_p (name, e->src)) { - if (compute_operand_range (r, stmt, lhs, name)) + if (compute_operand_range (r, stmt, lhs, name, src)) { // Sometimes compatible types get interchanged. See PR97360. // Make sure we are returning the type of the thing we asked for. diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index f41dee3d8e5..06f3b791359 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -153,41 +153,30 @@ class gori_compute : public gori_map { public: gori_compute (); - bool outgoing_edge_range_p (irange &r, edge e, tree name); + bool outgoing_edge_range_p (irange &r, edge e, tree name, range_query &q); bool has_edge_range_p (tree name, edge e = NULL); void dump (FILE *f); -protected: - virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb); - bool compute_operand_range (irange &r, gimple *stmt, - const irange &lhs, tree name); - - void expr_range_at_stmt (irange &r, tree expr, gimple *s); - bool compute_logical_operands (irange &r, gimple *stmt, - const irange &lhs, - tree name); - void compute_logical_operands_in_chain (class tf_range &range, - gimple *stmt, const irange &lhs, - tree name, tree op, - bool op_in_chain); - bool optimize_logical_operands (tf_range &range, gimple *stmt, - const irange &lhs, tree name, tree op); - bool logical_combine (irange &r, enum tree_code code, const irange &lhs, - const class tf_range &op1_range, - const class tf_range &op2_range); - int_range<2> m_bool_zero; // Boolean false cached. - int_range<2> m_bool_one; // Boolean true cached. - private: - bool compute_operand_range_switch (irange &r, gswitch *stmt, - const irange &lhs, tree name); - bool compute_name_range_op (irange &r, gimple *stmt, const irange &lhs, - tree name); + bool compute_operand_range (irange &r, gimple *stmt, const irange &lhs, + tree name, class fur_source &src); + bool compute_operand_range_switch (irange &r, gswitch *s, const irange &lhs, + tree name, fur_source &src); bool compute_operand1_range (irange &r, gimple *stmt, const irange &lhs, - tree name); + tree name, fur_source &src); bool compute_operand2_range (irange &r, gimple *stmt, const irange &lhs, - tree name); + tree name, fur_source &src); bool compute_operand1_and_operand2_range (irange &r, gimple *stmt, - const irange &lhs, tree name); + const irange &lhs, tree name, + fur_source &src); + void compute_logical_operands (irange &true_range, irange &false_range, + gimple *stmt, const irange &lhs, + tree name, fur_source &src, tree op, + bool op_in_chain); + bool logical_combine (irange &r, enum tree_code code, const irange &lhs, + const irange &op1_true, const irange &op1_false, + const irange &op2_true, const irange &op2_false); + int_range<2> m_bool_zero; // Boolean false cached. + int_range<2> m_bool_one; // Boolean true cached. gimple_outgoing_range outgoing; // Edge values for COND_EXPR & SWITCH_EXPR. }; diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index b4dfaa92168..d58e151eb4e 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -1051,7 +1051,7 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name) || range_compatible_p (r.type(), TREE_TYPE (name))); // Check to see if NAME is defined on edge e. - if (m_cache.outgoing_edge_range_p (edge_range, e, name)) + if (m_cache.range_on_edge (edge_range, e, name)) r.intersect (edge_range); return true; @@ -1063,7 +1063,7 @@ bool gimple_ranger::fold_range_internal (irange &r, gimple *s, tree name) { fold_using_range f; - fur_source src (this, &m_cache, NULL, s); + fur_source src (this, &(gori ()), NULL, s); return f.fold_stmt (r, s, src, name); } @@ -1164,7 +1164,7 @@ gimple_ranger::dump_bb (FILE *f, basic_block bb) edge e; int_range_max range; fprintf (f, "\n=========== BB %d ============\n", bb->index); - m_cache.dump (f, bb); + m_cache.dump_bb (f, bb); ::dump_bb (f, bb, 4, TDF_NONE); @@ -1193,7 +1193,7 @@ gimple_ranger::dump_bb (FILE *f, basic_block bb) for (x = 1; x < num_ssa_names; x++) { tree name = gimple_range_ssa_p (ssa_name (x)); - if (name && m_cache.outgoing_edge_range_p (range, e, name)) + if (name && m_cache.range_on_edge (range, e, name)) { gimple *s = SSA_NAME_DEF_STMT (name); // Only print the range if this is the def block, or @@ -1236,7 +1236,7 @@ gimple_ranger::dump (FILE *f) FOR_EACH_BB_FN (bb, cfun) dump_bb (f, bb); - m_cache.dump (f, false); + m_cache.dump (f); } // If SCEV has any information about phi node NAME, return it as a range in R. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index ecd332a3c54..65f62e4ba9b 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -25,10 +25,10 @@ along with GCC; see the file COPYING3. If not see #include "range.h" #include "range-op.h" +#include "value-query.h" #include "gimple-range-edge.h" #include "gimple-range-gori.h" #include "gimple-range-cache.h" -#include "value-query.h" // This file is the main include point for gimple ranges. // There are two fold_range routines of interest: @@ -65,6 +65,7 @@ public: virtual void range_on_entry (irange &r, basic_block bb, tree name); virtual void range_on_exit (irange &r, basic_block bb, tree name); void export_global_ranges (); + inline gori_compute &gori () { return m_cache.m_gori; } virtual void dump (FILE *f) OVERRIDE; void dump_bb (FILE *f, basic_block bb); protected: