ranger restructuring
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 19f6ceb..b7e643b 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1364,12 +1364,10 @@
gimple-loop-versioning.o \
gimple-low.o \
gimple-pretty-print.o \
- gimple-ranger.o \
- gimple-ranger-vrp.o \
+ gimple-range.o \
+ gimple-range-vrp.o \
misc.o \
gimple-range-cache.o \
- gimple-range-cfg.o \
- gimple-range-stmt.o \
gimple-range-gori.o \
gimple-ssa-backprop.o \
gimple-ssa-evrp.o \
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 3220133..f6ea338 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -27,8 +27,7 @@
#include "gimple.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
-#include "gimple-range-stmt.h"
-#include "gimple-range-cache.h"
+#include "gimple-range.h"
// During contructor, allocate the vector of ssa_names.
@@ -462,4 +461,222 @@
fputc ('\n', f);
}
+// --------------------------------------------------------------------------
+
+ranger_cache::ranger_cache ()
+{
+ m_workback.create (0);
+ m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
+ m_update_list.create (0);
+ m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun));
+ m_update_list.truncate (0);
+}
+
+ranger_cache::~ranger_cache ()
+{
+ m_workback.release ();
+ m_update_list.release ();
+}
+
+
+// Provide lookup for the gori-computes class to access the best known range
+// of an ssa_name in any given basic block. NOte this does no additonal
+// lookups, just accesses the data that is already known.
+
+void
+ranger_cache::ssa_range_in_bb (irange &r, tree name, basic_block bb)
+{
+ gimple *s = SSA_NAME_DEF_STMT (name);
+ basic_block def_bb = ((s && gimple_bb (s)) ? gimple_bb (s) :
+ ENTRY_BLOCK_PTR_FOR_FN (cfun));
+ if (bb == def_bb || !m_on_entry.get_bb_range (r, name, bb))
+ {
+ // Try to pick up any known value first.
+ 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 he block, so just
+ // punt for now on those.
+ if (r.varying_p () && m_non_null.non_null_deref_p (name, bb) &&
+ !cfun->can_throw_non_call_exceptions)
+ r = range_nonzero (TREE_TYPE (name));
+}
+
+
+// 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.
+
+bool
+ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc)
+{
+ gcc_checking_assert (gimple_range_ssa_p (name));
+
+ if (calc)
+ {
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+ basic_block def_bb = NULL;
+ if (def_stmt)
+ def_bb = gimple_bb (def_stmt);;
+ if (!def_bb)
+ {
+ // If we get to the entry block, this better be a default def
+ // or range_on_entry was called for a block not dominated by
+ // the def. This would be a bug.
+ gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name));
+ def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+ }
+
+ // There is no range on entry for the defintion block.
+ if (def_bb == bb)
+ return false;
+
+ // Otherwise, go figure out what is known in predecessor blocks.
+ fill_block_cache (name, bb, def_bb);
+ gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
+ }
+ return m_on_entry.get_bb_range (r, name, bb);
+}
+
+
+void
+ranger_cache::add_to_update (basic_block bb)
+{
+ if (!m_update_list.contains (bb))
+ m_update_list.quick_push (bb);
+}
+
+#define DEBUG_CACHE (0 && dump_file)
+
+// If there is anything in the iterative update_list, continue
+// processing NAME until the list of blocks is empty.
+
+void
+ranger_cache::iterative_cache_update (tree name)
+{
+ basic_block bb;
+ edge_iterator ei;
+ edge e;
+ widest_irange new_range;
+ widest_irange current_range;
+ widest_irange e_range;
+
+ // Process each block by seeing if it's calculated range on entry is
+ // the same as it's cached value. IF there is a difference, update
+ // the cache to reflect the new value, and check to see if any
+ // successors have cache entries which may need to be checked for
+ // updates.
+
+ while (m_update_list.length () > 0)
+ {
+ bb = m_update_list.pop ();
+if (DEBUG_CACHE) fprintf (dump_file, "FWD visiting block %d\n", bb->index);
+
+ gcc_assert (m_on_entry.get_bb_range (current_range, name, bb));
+ // Calculate the "new" range on entry by unioning the pred edges..
+ new_range.set_undefined ();
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ // Get whatever range we can for this edge
+ if (!outgoing_edge_range_p (e_range, e, name))
+ ssa_range_in_bb (e_range, name, e->src);
+ new_range.union_ (e_range);
+ if (new_range.varying_p ())
+ break;
+ }
+ // If the range on entry has changed, update it.
+ if (new_range != current_range)
+ {
+if (DEBUG_CACHE) { fprintf (dump_file, "updating range from/to "); current_range.dump (dump_file); new_range.dump (dump_file); }
+ m_on_entry.set_bb_range (name, bb, new_range);
+ // Mark each successor that has a range to re-check it's range
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (m_on_entry.bb_range_p (name, e->dest))
+ add_to_update (e->dest);
+ }
+ }
+if (DEBUG_CACHE) fprintf (dump_file, "DONE visiting blocks \n\n");
+}
+
+// Make sure that the range-on-entry cache for NAME is set for block BB.
+// Work back thourgh the CFG to DEF_BB ensuring the range is calculated
+// on the block/edges leading back to that point.
+
+void
+ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
+{
+ edge_iterator ei;
+ edge e;
+ widest_irange block_result;
+ widest_irange undefined;
+
+ // At this point we shouldnt be looking at the def, entry or exit block.
+ gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
+ bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
+
+ // If the block cache is set, then we've already visited this block.
+ if (m_on_entry.bb_range_p (name, bb))
+ return;
+
+ // Visit each block back to the DEF. Initialize each one to UNDEFINED.
+ // m_visited at the end will contain all the blocks that we needed to set
+ // the range_on_entry cache for.
+ m_workback.truncate (0);
+ m_workback.quick_push (bb);
+ undefined.set_undefined ();
+ m_on_entry.set_bb_range (name, bb, undefined);
+ gcc_checking_assert (m_update_list.length () == 0);
+
+if (DEBUG_CACHE) { fprintf (dump_file, "\n"); print_generic_expr (dump_file, name, TDF_SLIM); fprintf (dump_file, " : "); }
+
+ while (m_workback.length () > 0)
+ {
+ basic_block node = m_workback.pop ();
+if (DEBUG_CACHE) fprintf (dump_file, "BACK visiting block %d\n", node->index);
+
+ FOR_EACH_EDGE (e, ei, node->preds)
+ {
+ basic_block pred = e->src;
+ widest_irange r;
+ // If the pred block is the def block add this BB to update list.
+ if (pred == def_bb)
+ {
+ add_to_update (node);
+ continue;
+ }
+
+ // If the pred is entry but NOT def, then it is used before
+ // defined, it'll get set to []. and no need to update it.
+ if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ continue;
+
+ // Regardless of whther we have visited pred or not, if the pred has
+ // a non-null reference, revisit this block.
+ if (m_non_null.non_null_deref_p (name, pred))
+ add_to_update (node);
+
+ // If the pred block already has a range, or if it can contribute
+ // something new. Ie, the edge generates a range of some sort.
+ if (m_on_entry.get_bb_range (r, name, pred))
+ {
+ if (!r.undefined_p () || has_edge_range_p (e, name))
+ add_to_update (node);
+ continue;
+ }
+
+ // 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));
+ m_on_entry.set_bb_range (name, pred, undefined);
+ m_workback.quick_push (pred);
+ }
+ }
+
+ iterative_cache_update (name);
+}
+
+
+
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index 7dfaf8f..39c7a99 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -21,6 +21,8 @@
#ifndef GCC_SSA_RANGE_CACHE_H
#define GCC_SSA_RANGE_CACHE_H
+#include "gimple-range-gori.h"
+
// This global cache is used with the range engine as markers for what
// has been visited during this incarnation. Once the ranger evaluates
// a name, it is typically not re-evaluated again.
@@ -79,4 +81,30 @@
void process_name (tree name);
};
+// THis class provides all the caches a global ranger may needs, and makes
+// them available for gori-computes to query so outgoing edges can be
+// properly calculated.
+//
+class ranger_cache : public gori_compute_cache
+{
+public:
+ ranger_cache ();
+ ~ranger_cache ();
+
+ virtual 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);
+
+ ssa_global_cache m_globals;
+ block_range_cache m_on_entry;
+ non_null_ref m_non_null;
+private:
+ void add_to_update (basic_block bb);
+ void fill_block_cache (tree name, basic_block bb, basic_block def_bb);
+ void iterative_cache_update (tree name);
+
+ vec<basic_block> m_workback;
+ vec<basic_block> m_update_list;
+
+};
+
#endif // GCC_SSA_RANGE_CACHE_H
diff --git a/gcc/gimple-range-cfg.cc b/gcc/gimple-range-cfg.cc
deleted file mode 100644
index f513fd8..0000000
--- a/gcc/gimple-range-cfg.cc
+++ /dev/null
@@ -1,495 +0,0 @@
-/* Implementation of the gimple_ranger class.
- Copyright (C) 2017-2020 Free Software Foundation, Inc.
- Contributed by Andrew MacLeod <amacleod@redhat.com>
- and Aldy Hernandez <aldyh@redhat.com>.
-
-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
-<http://www.gnu.org/licenses/>. */
-
-#include "config.h"
-#include "system.h"
-#include "coretypes.h"
-#include "backend.h"
-#include "insn-codes.h"
-#include "tree.h"
-#include "gimple.h"
-#include "ssa.h"
-#include "optabs-tree.h"
-#include "gimple-fold.h"
-#include "tree-cfg.h"
-#include "wide-int.h"
-#include "gimple-range-stmt.h"
-#include "gimple-range-gori.h"
-#include "gimple-range-cfg.h"
-#include "fold-const.h"
-#include "case-cfn-macros.h"
-#include "omp-general.h"
-
-// Calculate a range for statement S and return it in R. If NAME is provided it
-// represents the SSA_NAME on the LHS of the statement. It is only required
-// if there is more than one lhs/output. If a range cannot
-// be calculated, return false.
-
-bool
-gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
-{
- bool res = false;
- // If name is specified, make sure it is a LHS of S.
- gcc_checking_assert (name ? SSA_NAME_DEF_STMT (name) == s : true);
-
- if (gimple_range_handler (s))
- res = range_of_range_op (r, s);
- else if (is_a<gphi *>(s))
- res = range_of_phi (r, as_a<gphi *> (s));
- else if (is_a<gcall *>(s))
- res = range_of_call (r, as_a<gcall *> (s));
- else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
- res = range_of_cond_expr (r, as_a<gassign *> (s));
- else
- {
- // If no name is specified, try the expression kind.
- if (!name)
- {
- tree t = gimple_expr_type (s);
- if (!irange::supports_type_p (t))
- return false;
- r.set_varying (t);
- return true;
- }
- // We don't understand the stmt, so return the global range.
- r = gimple_range_global (name);
- return true;
- }
- if (res)
- {
- if (r.undefined_p ())
- return true;
- if (name && TREE_TYPE (name) != r.type ())
- range_cast (r, TREE_TYPE (name));
- return true;
- }
- return false;
-}
-
-
-// Calculate a range for NAME on edge E and return it in R.
-
-void
-gimple_ranger::range_on_edge (irange &r, edge e, tree name)
-{
- widest_irange edge_range;
- gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));
-
- // PHI arguments can be constants, catch these here.
- if (!gimple_range_ssa_p (name))
- {
- gcc_assert (range_of_expr (r, name));
- return;
- }
-
- range_on_exit (r, e->src, name);
- gcc_checking_assert (r.undefined_p ()
- || types_compatible_p (r.type(), TREE_TYPE (name)));
-
- // Check to see if NAME is defined on edge e.
- if (outgoing_edge_range_p (edge_range, e, name, &r))
- r = edge_range;
-}
-
-// Return the range for NAME on entry to block BB in R.
-// At the statement level, this amounts to whatever the global value is.
-
-void
-gimple_ranger::range_on_entry (irange &r, basic_block bb ATTRIBUTE_UNUSED,
- tree name)
-{
- range_of_ssa_name (r, name);
-}
-
-
-// Return the range for NAME on exit from block BB in R.
-// At the statement level, this amounts to whatever the global value is.
-
-void
-gimple_ranger::range_on_exit (irange &r, basic_block bb ATTRIBUTE_UNUSED,
- tree name)
-{
- range_of_ssa_name (r, name);
-}
-
-
-// Calculate a range for range_op statement S and return it in R. If any
-// If a range cannot be calculated, return false.
-
-bool
-gimple_ranger::range_of_range_op (irange &r, gimple *s)
-{
- widest_irange range1, range2;
- tree type = gimple_expr_type (s);
- gcc_checking_assert (irange::supports_type_p (type));
-
- tree op1 = gimple_range_operand1 (s);
- tree op2 = gimple_range_operand2 (s);
-
- if (range_of_non_trivial_assignment (r, s))
- return true;
-
- if (range_of_expr (range1, op1, s))
- {
- if (!op2)
- return gimple_range_fold (s, r, range1);
-
- if (range_of_expr (range2, op2, s))
- return gimple_range_fold (s, r, range1, range2);
- }
- r.set_varying (type);
- return true;
-}
-
-
-// Calculate the range of a non-trivial assignment. That is, is one
-// inolving arithmetic on an SSA name (for example, an ADDR_EXPR).
-// Return the range in R.
-//
-// If a range cannot be calculated, return false.
-
-bool
-gimple_ranger::range_of_non_trivial_assignment (irange &r, gimple *stmt)
-{
- if (gimple_code (stmt) != GIMPLE_ASSIGN)
- return false;
-
- tree base = gimple_range_base_of_assignment (stmt);
- if (base && TREE_CODE (base) == MEM_REF
- && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
- {
- widest_irange range1;
- tree ssa = TREE_OPERAND (base, 0);
- if (range_of_expr (range1, ssa, stmt))
- {
- tree type = TREE_TYPE (ssa);
- range_operator *op = range_op_handler (POINTER_PLUS_EXPR, type);
- int_range<1> offset (TREE_OPERAND (base, 1), TREE_OPERAND (base, 1));
- op->fold_range (r, type, range1, offset);
- return true;
- }
- }
- return false;
-}
-
-
-// Calculate a range for phi statement S and return it in R.
-// If a range cannot be calculated, return false.
-
-bool
-gimple_ranger::range_of_phi (irange &r, gphi *phi)
-{
- tree phi_def = gimple_phi_result (phi);
- tree type = TREE_TYPE (phi_def);
- widest_irange phi_range;
- unsigned x;
-
- if (!irange::supports_type_p (type))
- return false;
-
- // And start with an empty range, unioning in each argument's range.
- r.set_undefined ();
- for (x = 0; x < gimple_phi_num_args (phi); x++)
- {
- widest_irange arg_range;
- tree arg = gimple_phi_arg_def (phi, x);
- edge e = gimple_phi_arg_edge (phi, x);
-
- range_on_edge (arg_range, e, arg);
- r.union_ (arg_range);
- // Once the value reaches varying, stop looking.
- if (r.varying_p ())
- break;
- }
-
- return true;
-}
-
-
-// Calculate a range for call statement S and return it in R.
-// If a range cannot be calculated, return false.
-
-bool
-gimple_ranger::range_of_call (irange &r, gcall *call)
-{
- tree type = gimple_call_return_type (call);
- tree lhs = gimple_call_lhs (call);
- bool strict_overflow_p;
-
- if (!irange::supports_type_p (type))
- return false;
-
- if (range_of_builtin_call (r, call))
- ;
- else if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p))
- r.set (build_int_cst (type, 0), TYPE_MAX_VALUE (type));
- else if (gimple_call_nonnull_result_p (call)
- || gimple_call_nonnull_arg (call))
- r = range_nonzero (type);
- else
- r.set_varying (type);
-
- // If there is a lHS, intersect that with what is known.
- if (lhs)
- {
- value_range def;
- def = gimple_range_global (lhs);
- r.intersect (def);
- }
- return true;
-}
-
-
-void
-gimple_ranger::range_of_builtin_ubsan_call (irange &r, gcall *call,
- tree_code code)
-{
- gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR
- || code == MULT_EXPR);
- tree type = gimple_call_return_type (call);
- range_operator *op = range_op_handler (code, type);
- gcc_checking_assert (op);
- widest_irange ir0, ir1;
- tree arg0 = gimple_call_arg (call, 0);
- tree arg1 = gimple_call_arg (call, 1);
- gcc_assert (range_of_expr (ir0, arg0, call));
- gcc_assert (range_of_expr (ir1, arg1, call));
-
- bool saved_flag_wrapv = flag_wrapv;
- /* Pretend the arithmetics is wrapping. If there is
- any overflow, we'll complain, but will actually do
- wrapping operation. */
- flag_wrapv = 1;
- op->fold_range (r, type, ir0, ir1);
- flag_wrapv = saved_flag_wrapv;
-
- /* If for both arguments vrp_valueize returned non-NULL,
- this should have been already folded and if not, it
- wasn't folded because of overflow. Avoid removing the
- UBSAN_CHECK_* calls in that case. */
- if (r.singleton_p ())
- r.set_varying (type);
-}
-
-
-bool
-gimple_ranger::range_of_builtin_call (irange &r, gcall *call)
-{
- combined_fn func = gimple_call_combined_fn (call);
- if (func == CFN_LAST)
- return false;
-
- tree type = gimple_call_return_type (call);
- tree arg;
- int mini, maxi, zerov, prec;
- scalar_int_mode mode;
-
- switch (func)
- {
- case CFN_BUILT_IN_CONSTANT_P:
- if (cfun->after_inlining)
- {
- r.set_zero (type);
- // r.equiv_clear ();
- return true;
- }
- arg = gimple_call_arg (call, 0);
- if (range_of_expr (r, arg, call) && r.singleton_p ())
- {
- r.set (build_one_cst (type), build_one_cst (type));
- return true;
- }
- break;
-
- CASE_CFN_FFS:
- CASE_CFN_POPCOUNT:
- // __builtin_ffs* and __builtin_popcount* return [0, prec].
- arg = gimple_call_arg (call, 0);
- prec = TYPE_PRECISION (TREE_TYPE (arg));
- mini = 0;
- maxi = prec;
- gcc_assert (range_of_expr (r, arg, call));
- // If arg is non-zero, then ffs or popcount are non-zero.
- if (!range_includes_zero_p (&r))
- mini = 1;
- // If some high bits are known to be zero, decrease the maximum.
- if (!r.undefined_p ())
- {
- wide_int max = r.upper_bound ();
- maxi = wi::floor_log2 (max) + 1;
- }
- r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
- return true;
-
- CASE_CFN_PARITY:
- r.set (build_zero_cst (type), build_one_cst (type));
- return true;
-
- CASE_CFN_CLZ:
- // __builtin_c[lt]z* return [0, prec-1], except when the
- // argument is 0, but that is undefined behavior.
- //
- // On many targets where the CLZ RTL or optab value is defined
- // for 0, the value is prec, so include that in the range by
- // default.
- arg = gimple_call_arg (call, 0);
- prec = TYPE_PRECISION (TREE_TYPE (arg));
- mini = 0;
- maxi = prec;
- mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
- if (optab_handler (clz_optab, mode) != CODE_FOR_nothing
- && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov)
- // Only handle the single common value.
- && zerov != prec)
- // Magic value to give up, unless we can prove arg is non-zero.
- mini = -2;
-
- gcc_assert (range_of_expr (r, arg, call));
- // From clz of minimum we can compute result maximum.
- if (r.constant_p ())
- {
- maxi = prec - 1 - wi::floor_log2 (r.lower_bound ());
- if (maxi != prec)
- mini = 0;
- }
- else if (!range_includes_zero_p (&r))
- {
- maxi = prec - 1;
- mini = 0;
- }
- if (mini == -2)
- break;
- // From clz of maximum we can compute result minimum.
- if (r.constant_p ())
- {
- mini = prec - 1 - wi::floor_log2 (r.upper_bound ());
- if (mini == prec)
- break;
- }
- if (mini == -2)
- break;
- r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
- return true;
-
- CASE_CFN_CTZ:
- // __builtin_ctz* return [0, prec-1], except for when the
- // argument is 0, but that is undefined behavior.
- //
- // If there is a ctz optab for this mode and
- // CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
- // otherwise just assume 0 won't be seen.
- arg = gimple_call_arg (call, 0);
- prec = TYPE_PRECISION (TREE_TYPE (arg));
- mini = 0;
- maxi = prec - 1;
- mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
- if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing
- && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov))
- {
- // Handle only the two common values.
- if (zerov == -1)
- mini = -1;
- else if (zerov == prec)
- maxi = prec;
- else
- // Magic value to give up, unless we can prove arg is non-zero.
- mini = -2;
- }
- gcc_assert (range_of_expr (r, arg, call));
- if (!r.undefined_p ())
- {
- if (r.lower_bound () != 0)
- {
- mini = 0;
- maxi = prec - 1;
- }
- // If some high bits are known to be zero, we can decrease
- // the maximum.
- wide_int max = r.upper_bound ();
- if (max == 0)
- break;
- maxi = wi::floor_log2 (max);
- }
- if (mini == -2)
- break;
- r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
- return true;
-
- CASE_CFN_CLRSB:
- arg = gimple_call_arg (call, 0);
- prec = TYPE_PRECISION (TREE_TYPE (arg));
- r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1));
- return true;
- case CFN_UBSAN_CHECK_ADD:
- range_of_builtin_ubsan_call (r, call, PLUS_EXPR);
- return true;
- case CFN_UBSAN_CHECK_SUB:
- range_of_builtin_ubsan_call (r, call, MINUS_EXPR);
- return true;
- case CFN_UBSAN_CHECK_MUL:
- range_of_builtin_ubsan_call (r, call, MULT_EXPR);
- return true;
-
- case CFN_GOACC_DIM_SIZE:
- case CFN_GOACC_DIM_POS:
- // Optimizing these two internal functions helps the loop
- // optimizer eliminate outer comparisons. Size is [1,N]
- // and pos is [0,N-1].
- {
- bool is_pos = func == CFN_GOACC_DIM_POS;
- int axis = oacc_get_ifn_dim_arg (call);
- int size = oacc_get_fn_dim_size (current_function_decl, axis);
- if (!size)
- // If it's dynamic, the backend might know a hardware limitation.
- size = targetm.goacc.dim_limit (axis);
-
- r.set (build_int_cst (type, is_pos ? 0 : 1),
- size
- ? build_int_cst (type, size - is_pos) : vrp_val_max (type));
- return true;
- }
-
- case CFN_BUILT_IN_STRLEN:
- if (tree lhs = gimple_call_lhs (call))
- if (ptrdiff_type_node
- && (TYPE_PRECISION (ptrdiff_type_node)
- == TYPE_PRECISION (TREE_TYPE (lhs))))
- {
- tree type = TREE_TYPE (lhs);
- tree max = vrp_val_max (ptrdiff_type_node);
- wide_int wmax
- = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
- tree range_min = build_zero_cst (type);
- // To account for the terminating NULL, the maximum length
- // is one less than the maximum array size, which in turn
- // is one less than PTRDIFF_MAX (or SIZE_MAX where it's
- // smaller than the former type).
- // FIXME: Use max_object_size() - 1 here.
- tree range_max = wide_int_to_tree (type, wmax - 2);
- r.set (range_min, range_max);
- return true;
- }
- break;
- default:
- break;
- }
- return false;
-}
diff --git a/gcc/gimple-range-cfg.h b/gcc/gimple-range-cfg.h
deleted file mode 100644
index e5e7676..0000000
--- a/gcc/gimple-range-cfg.h
+++ /dev/null
@@ -1,44 +0,0 @@
-/* Header file for the gimple_ranger class.
- Copyright (C) 2017-2020 Free Software Foundation, Inc.
- Contributed by Andrew MacLeod <amacleod@redhat.com>
- and Aldy Hernandez <aldyh@redhat.com>.
-
-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
-<http://www.gnu.org/licenses/>. */
-
-#ifndef GCC_GIMPLE_RANGE_CFG_H
-#define GCC_GIMPLE_RANGE_CFG_H
-
-class gimple_ranger : public gori_compute_cache
-{
-public:
- virtual bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE);
- virtual void range_on_edge (irange &r, edge e, tree name);
-
- virtual void range_on_entry (irange &r, basic_block bb, tree name);
- virtual void range_on_exit (irange &r, basic_block bb, tree name);
-protected:
- bool range_of_range_op (irange &r, gimple *s);
- bool range_of_call (irange &r, gcall *call);
- bool range_of_cond_expr (irange &r, gassign* cond);
-private:
- bool range_of_phi (irange &r, gphi *phi);
- bool range_of_non_trivial_assignment (irange &r, gimple *s);
- bool range_of_builtin_call (irange &r, gcall *call);
- void range_of_builtin_ubsan_call (irange &r, gcall *call, tree_code code);
-};
-
-#endif // GCC_GIMPLE_RANGE_CFG_H
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 8d90ae7..2a59f0a 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -29,9 +29,74 @@
#include "gimple.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
-#include "gimple-range-stmt.h"
-#include "gimple-range-gori.h"
-#include "fold-const.h"
+#include "gimple-range.h"
+
+
+/* RANGE_DEF_CHAIN is used to determine what SSA names in a block can
+ have range information calculated for them, and what the
+ dependencies on each other are.
+
+ Information for a basic block is calculated once and stored. It is
+ only calculated the first time a query is made, so if no queries
+ are made, there is little overhead.
+
+ The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
+ within this bitmap to indicate SSA names that are defined in the
+ SAME block and used to calculate this SSA name.
+
+ One import is maintained per def-chain. An IMPORT is defined as an
+ SSA name in the def chain which occurs outside the basic block. A
+ change in the value of this SSA name can change the value of any
+ name in the chain.
+
+ If there is more than one import, or an ssa_name originates WITHIN
+ the same basic block, but is defined by a statement that the range
+ engine does not know how to calculate, then there is no import for
+ the entire chain.
+
+ <bb 2> :
+ _1 = x_4(D) + -2;
+ _2 = _1 * 4;
+ j_7 = foo ();
+ q_5 = _2 + 3;
+ if (q_5 <= 13)
+
+ _1 : (import : x_4(D)) :x_4(D)
+ _2 : (import : x_4(D)) :_1 x_4(D)
+ q_5 : (import : x_4(D)) :_1 _2 x_4(D)
+
+ This dump indicates the bits set in the def_chain vector and their
+ import, as well as demonstrates the def_chain bits for the related
+ ssa_names.
+
+ Checking the chain for _2 indicates that _1 and x_4 are used in
+ its evaluation, and with x_4 being an import.
+
+ For the purpose of defining an import, PHI node defintions are
+ considered imports as they don't really reside in the block, but
+ are accumulators of values from incoming edges.
+
+ Def chains also only include statements which are valid gimple
+ so a def chain will only span statements for which the range
+ engine implements operations for. */
+
+
+class range_def_chain
+{
+public:
+ range_def_chain ();
+ ~range_def_chain ();
+ tree terminal_name (tree name);
+ bool has_def_chain (tree name);
+ bitmap get_def_chain (tree name);
+ bool in_chain_p (tree name, tree def);
+private:
+ vec<bitmap> m_def_chain; // SSA_NAME : def chain components.
+ vec<tree> m_terminal; // SSA_NAME : chain terminal name.
+ tree build_def_chain (tree name, bitmap result, basic_block bb);
+};
+
+
// Construct a range_def_chain
@@ -233,6 +298,54 @@
return m_def_chain[v];
}
+// -------------------------------------------------------------------
+
+/* GORI_MAP is used to accumulate what SSA names in a block can
+ generate range information, and provides tools for the block ranger
+ to enable it to efficiently calculate these ranges.
+
+ GORI stands for "Generates Outgoing Range Information."
+
+ It utilizes the range_def_chain class to contruct def_chains.
+ Information for a basic block is calculated once and stored. It is
+ only calculated the first time a query is made. If no queries are
+ made, there is little overhead.
+
+ 2 bitmaps are maintained for each basic block:
+
+ m_outgoing : a set bit indicates a range can be generated for a name.
+ m_incoming : a set bit means a this name come from outside the
+ block and is used in the calculation of some outgoing
+ range.
+
+ Generally speaking, the m_outgoing vector is the union of the
+ entire def_chain of all SSA names used in the last statement of the
+ block which generate ranges. The m_incoming vector is the union of
+ all the terminal names of those def chains. They act as a one-stop
+ summary for the block. */
+
+class gori_map : public range_def_chain
+{
+public:
+ gori_map ();
+ ~gori_map ();
+
+ bool is_export_p (tree name, basic_block bb);
+ bool def_chain_in_export_p (tree name, basic_block bb);
+ bool is_import_p (tree name, basic_block bb);
+
+ void dump (FILE *f);
+ void dump (FILE *f, basic_block bb);
+private:
+ bitmap_obstack m_bitmaps;
+ vec<bitmap> m_outgoing; // BB: Outgoing ranges calculatable on edges
+ vec<bitmap> m_incoming; // BB: block imports
+ void maybe_add_gori (tree name, basic_block bb);
+ void calculate_gori (basic_block bb);
+ bitmap imports (basic_block bb);
+ bitmap exports (basic_block bb);
+};
+
// Initialize a gori-map structure.
@@ -312,8 +425,10 @@
{
if (name)
{
+ gimple *s = SSA_NAME_DEF_STMT (name);
bitmap r = get_def_chain (name);
- if (r)
+ // Check if there is a def chain, and it is in this block.
+ if (r && gimple_bb (s) == bb)
{
bitmap_copy (m_outgoing[bb->index], r);
tree im = terminal_name (name);
@@ -324,7 +439,7 @@
{
// 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)
+ if (!s || gimple_bb (s) != 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
@@ -479,90 +594,18 @@
g.dump (stderr);
}
-const value_range_equiv *
-range_store::get_value_range (const_tree expr ATTRIBUTE_UNUSED,
- gimple *stmt ATTRIBUTE_UNUSED)
-{
- gcc_unreachable ();
- return NULL;
-}
+// -------------------------------------------------------------------
-// Return the legacy global known value for NAME in R.
void
-gori_compute::range_of_ssa_name (irange &r, tree name,
- gimple *stmt ATTRIBUTE_UNUSED)
+gori_compute::expr_range_in_bb (irange &r, tree expr, basic_block bb)
{
- r = gimple_range_global (name);
-}
-
-
-// This function returns a range for a tree node. If optional
-// statement STMT is present, then the range would be if it were to
-// appear as a use on STMT. Return false if ranges are not supported for
-// the type of EXPR.
-
-bool
-gori_compute::range_of_expr (irange &r, tree expr, gimple *stmt)
-{
- tree type;
- if (TYPE_P (expr))
- type = expr;
+ if (gimple_range_ssa_p (expr))
+ ssa_range_in_bb (r, expr, bb);
else
- type = TREE_TYPE (expr);
-
- // Return false if the type isn't suported.
- if (!irange::supports_type_p (type))
- return false;
-
- switch (TREE_CODE (expr))
- {
- case INTEGER_CST:
- r.set (expr, expr);
- return true;
-
- case SSA_NAME:
- range_of_ssa_name (r, expr, stmt);
- 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.set_varying (type);
- return true;
+ get_tree_range (r, expr);
}
-// 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 won't go off and calculate a range in derived
-// bases.
-
-void
-gori_compute::get_tree_range (irange &r, tree expr, tree name,
- const irange *range_of_name)
-{
- if (expr == name && range_of_name)
- {
- r = *range_of_name;
- return;
- }
- gcc_assert (range_of_expr (r, expr));
-}
-
-
// 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
@@ -570,9 +613,7 @@
bool
gori_compute::compute_name_range_op (irange &r, gimple *stmt,
- const irange &lhs,
- tree name,
- const irange *name_range)
+ const irange &lhs, tree name)
{
widest_irange op1_range, op2_range;
@@ -582,37 +623,31 @@
// Operand 1 is the name being looked for, evaluate it.
if (op1 == name)
{
+ expr_range_in_bb (op1_range, op1, gimple_bb (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.
- get_tree_range (op1_range, op1, name, name_range);
- return gimple_range_calc_op1 (stmt, r, lhs, op1_range);
+ // 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.
- get_tree_range (op2_range, op2, name, name_range);
- if (gimple_range_calc_op1 (stmt, 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;
+ expr_range_in_bb (op2_range, op2, gimple_bb (stmt));
+ if (gimple_range_calc_op1 (r, stmt, lhs, op2_range))
+ r.intersect (op1_range);
+ else
+ r = op1_range;
+ return true;
}
if (op2 == name)
{
- get_tree_range (op1_range, op1, name, name_range);
- if (gimple_range_calc_op2 (stmt, r, lhs, op1_range))
- {
- // If op2 also has a range, intersect the 2 ranges.
- if (name_range)
- r.intersect (*name_range);
- return true;
- }
+ expr_range_in_bb (op1_range, op1, gimple_bb (stmt));
+ expr_range_in_bb (r, op2, gimple_bb (stmt));
+ if (gimple_range_calc_op2 (op2_range, stmt, lhs, op1_range))
+ r.intersect (op2_range);
+ return true;
}
return false;
}
@@ -626,12 +661,14 @@
// Create a boolean_type true and false range.
m_bool_zero = int_range<1> (boolean_false_node, boolean_false_node);
m_bool_one = int_range<1> (boolean_true_node, boolean_true_node);
+ m_gori_map = new gori_map;
}
// Destruct a gori_compute_object
gori_compute::~gori_compute ()
{
+ delete m_gori_map;
}
// Given the switch S, return an evaluation in R for NAME when the lhs
@@ -642,8 +679,7 @@
bool
gori_compute::compute_operand_range_switch (irange &r, gswitch *s,
const irange &lhs,
- tree name,
- const irange *name_range)
+ tree name)
{
tree op1 = gimple_switch_index (s);
@@ -653,16 +689,12 @@
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);
+ 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);
return false;
}
@@ -702,9 +734,7 @@
bool
gori_compute::compute_operand_range (irange &r, gimple *stmt,
- const irange &lhs,
- tree name,
- const irange *name_range)
+ const irange &lhs, tree name)
{
// Empty ranges are viral as they are on an unexecutable path.
if (lhs.undefined_p ())
@@ -713,8 +743,7 @@
return true;
}
if (is_a<gswitch *> (stmt))
- return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs,
- name, name_range);
+ return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs, name);
if (!gimple_range_handler (stmt))
return false;
@@ -723,21 +752,21 @@
// The base ranger handles NAME on this statement.
if (op1 == name || op2 == name)
- return compute_name_range_op (r, stmt, lhs, name, name_range);
+ return compute_name_range_op (r, stmt, lhs, name);
if (is_gimple_logical_p (stmt))
- return compute_logical_operands (r, stmt, lhs, name, name_range);
+ return compute_logical_operands (r, stmt, lhs, name);
// NAME is not in this stmt, but one of the names in it ought to be
// derived from it.
- bool op1_in_chain = op1 && m_gori_map.in_chain_p (name, op1);
- bool op2_in_chain = op2 && m_gori_map.in_chain_p (name, op2);
+ bool op1_in_chain = op1 && m_gori_map->in_chain_p (name, op1);
+ bool op2_in_chain = op2 && m_gori_map->in_chain_p (name, op2);
if (op1_in_chain && op2_in_chain)
- return compute_operand1_and_operand2_range (r, stmt, lhs, name, name_range);
+ return compute_operand1_and_operand2_range (r, stmt, lhs, name);
if (op1_in_chain)
- return compute_operand1_range (r, stmt, lhs, name, name_range);
+ return compute_operand1_range (r, stmt, lhs, name);
if (op2_in_chain)
- return compute_operand2_range (r, stmt, lhs, name, name_range);
+ return compute_operand2_range (r, stmt, lhs, name);
// If neither operand is derived, this statement tells us nothing.
return false;
@@ -891,7 +920,6 @@
gimple *stmt,
const irange &lhs,
tree name,
- const irange *name_range,
tree op)
{
enum tree_code code = gimple_expr_code (stmt);
@@ -900,8 +928,8 @@
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, name_range))
- get_tree_range (range.false_range, name, name, name_range);
+ m_bool_zero, name))
+ expr_range_in_bb (range.false_range, name, gimple_bb (stmt));
range.true_range = range.false_range;
return true;
}
@@ -909,8 +937,8 @@
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, name_range))
- get_tree_range (range.true_range, name, name, name_range);
+ m_bool_one, name))
+ expr_range_in_bb (range.true_range, name, gimple_bb (stmt));
range.false_range = range.true_range;
return true;
}
@@ -927,27 +955,26 @@
gimple *stmt,
const irange &lhs,
tree name,
- const irange *name_range,
tree op, bool op_in_chain)
{
if (!op_in_chain)
{
// If op is not in chain, use its known value.
- get_tree_range (range.true_range, name, name, name_range);
+ expr_range_in_bb (range.true_range, name, gimple_bb (stmt));
range.false_range = range.true_range;
return;
}
- if (optimize_logical_operands (range, stmt, lhs, name, name_range, op))
+ if (optimize_logical_operands (range, stmt, lhs, name, op))
return;
// Calulate 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, SSA_NAME_DEF_STMT (op),
- m_bool_one, name, name_range))
- get_tree_range (range.true_range, name, name, name_range);
+ m_bool_one, name))
+ expr_range_in_bb (range.true_range, name, gimple_bb (stmt));
if (!compute_operand_range (range.false_range, SSA_NAME_DEF_STMT (op),
- m_bool_zero, name, name_range))
- get_tree_range (range.false_range, name, name, name_range);
+ m_bool_zero, name))
+ expr_range_in_bb (range.false_range, name, gimple_bb (stmt));
}
// Given a logical STMT, calculate true and false for each potential
@@ -958,8 +985,7 @@
bool
gori_compute::compute_logical_operands (irange &r, gimple *stmt,
const irange &lhs,
- tree name,
- const irange *name_range)
+ 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. */
@@ -968,9 +994,9 @@
gcc_checking_assert (op1 != name && op2 != name);
bool op1_in_chain = (gimple_range_ssa_p (op1)
- && m_gori_map.in_chain_p (name, op1));
+ && m_gori_map->in_chain_p (name, op1));
bool op2_in_chain = (gimple_range_ssa_p (op2)
- && m_gori_map.in_chain_p (name, 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)
@@ -978,9 +1004,9 @@
tf_range op1_range, op2_range;
compute_logical_operands_in_chain (op1_range, stmt, lhs,
- name, name_range, op1, op1_in_chain);
+ name, op1, op1_in_chain);
compute_logical_operands_in_chain (op2_range, stmt, lhs,
- name, name_range, op2, op2_in_chain);
+ name, op2, op2_in_chain);
return logical_combine (r, gimple_expr_code (stmt), lhs,
op1_range, op2_range);
}
@@ -992,20 +1018,19 @@
bool
gori_compute::compute_operand1_range (irange &r, gimple *stmt,
- const irange &lhs, tree name,
- const irange *name_range)
+ const irange &lhs, tree name)
{
widest_irange op1_range, op2_range;
tree op1 = gimple_range_operand1 (stmt);
tree op2 = gimple_range_operand2 (stmt);
- get_tree_range (op1_range, op1, name, name_range);
+ expr_range_in_bb (op1_range, op1, gimple_bb (stmt));
// Now calcuated the operand and put that result in r.
if (op2)
{
- get_tree_range (op2_range, op2, name, name_range);
- if (!gimple_range_calc_op1 (stmt, r, lhs, op2_range))
+ expr_range_in_bb (op2_range, op2, gimple_bb (stmt));
+ if (!gimple_range_calc_op1 (r, stmt, lhs, op2_range))
return false;
}
else
@@ -1013,16 +1038,25 @@
// 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 (stmt, r, lhs, op1_range))
+ if (!gimple_range_calc_op1 (r, stmt, lhs, op1_range))
return false;
}
// Intersect the calculated result with the known result.
op1_range.intersect (r);
+ gimple *src_stmt = SSA_NAME_DEF_STMT (op1);
+ // If defstmt 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);
+ }
+ else
// 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);
+ return compute_operand_range (r, src_stmt, op1_range, name);
}
@@ -1033,32 +1067,31 @@
bool
gori_compute::compute_operand2_range (irange &r, gimple *stmt,
- const irange &lhs, tree name,
- const irange *name_range)
+ const irange &lhs, tree name)
{
widest_irange op1_range, op2_range;
tree op1 = gimple_range_operand1 (stmt);
tree op2 = gimple_range_operand2 (stmt);
- get_tree_range (op1_range, op1, name, name_range);
+ expr_range_in_bb (op1_range, op1, gimple_bb (stmt));
+ expr_range_in_bb (op2_range, op2, gimple_bb (stmt));
- // Calculate the range for op2 based on lhs and op1.
- if (!gimple_range_calc_op2 (stmt, op2_range, lhs, op1_range))
+ // INtersect with range for op2 based on lhs and op1.
+ if (gimple_range_calc_op2 (r, stmt, lhs, op1_range))
+ op2_range.intersect (r);
+
+ gimple *src_stmt = SSA_NAME_DEF_STMT (op2);
+ // If defstmt is outside of this BB, then name must be an import.
+ if (!src_stmt || (gimple_bb (src_stmt) != gimple_bb (stmt)))
{
- get_tree_range (op2_range, op2, name, name_range);
- if (op2_range.varying_p ())
- return false;
+ // 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);
}
-
- // Also pick up what is known about op2's range at this point
- get_tree_range (r, op2, name, name_range);
-
- // And intersect it with the calculated result.
- op2_range.intersect (r);
-
+ else
// 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);
+ return compute_operand_range (r, src_stmt, op2_range, name);
}
// Calculate a range for NAME from both operand positions of S
@@ -1071,18 +1104,17 @@
(irange &r,
gimple *stmt,
const irange &lhs,
- tree name,
- const irange *name_range)
+ tree name)
{
widest_irange 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, name_range))
+ if (!compute_operand2_range (op_range, stmt, lhs, name))
return false;
// Now get the range thru op1...
- if (!compute_operand1_range (r, stmt, lhs, name, name_range))
+ if (!compute_operand1_range (r, stmt, lhs, name))
return false;
// Whichever range is the most permissive is the one we need to
@@ -1094,8 +1126,15 @@
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));
+ return (m_gori_map->is_export_p (name, e->src)
+ || m_gori_map->def_chain_in_export_p (name, e->src));
+}
+
+
+void
+gori_compute::dump (FILE *f)
+{
+ m_gori_map->dump (f);
}
@@ -1104,8 +1143,7 @@
// control edge or NAME is not defined by this edge.
bool
-gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name,
- const irange *name_range)
+gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name)
{
widest_irange lhs;
@@ -1116,8 +1154,8 @@
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, stmt, lhs, name, name_range);
+ if (m_gori_map->is_export_p (name, e->src))
+ return compute_operand_range (r, stmt, lhs, name);
// Otherwise see if NAME is derived from something that can be
// calculated. This performs no dynamic lookups whatsover, so it is
@@ -1125,177 +1163,8 @@
return false;
}
-// Tracing wrapper implementation for gori_compute.
-trace_gori_compute::trace_gori_compute ()
-{
- indent = 0;
- trace_count = 0;
-}
-// If dumping, return true and print the prefix for the next output line.
-
-bool
-trace_gori_compute::dumping (unsigned counter, bool trailing)
-{
- if (dump_file && (dump_flags & TDF_GORI))
- {
- // Print counter index as well as INDENT spaces.
- if (!trailing)
- fprintf (dump_file, " %-7u ", counter);
- else
- fprintf (dump_file, " ");
- for (unsigned x = 0; x < indent; x++)
- fputc (' ', dump_file);
- return true;
- }
- return false;
-}
-
-// After calling a routine, if dumping, print the CALLER, NAME, and RESULT,
-// returning RESULT.
-
-bool
-trace_gori_compute::trailer (unsigned counter, const char *caller, bool result,
- tree name, const irange &r)
-{
- indent -= bump;
- if (dumping (counter, true))
- {
- fputs(result ? "TRUE : " : "FALSE : ", dump_file);
- fprintf (dump_file, "(%u) ", counter);
- fputs (caller, dump_file);
- fputs (" (", dump_file);
- if (name)
- print_generic_expr (dump_file, name, TDF_SLIM);
- fputs (") ", dump_file);
- if (result)
- r.dump (dump_file);
- fputc('\n', dump_file);
- }
- // Marks the end of a request.
- if (indent == 0)
- fputc ('\n', dump_file);
- return result;
-}
-
-void
-trace_gori_compute::range_of_ssa_name (irange &r, tree name, gimple *stmt)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "range_of_ssa_name (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") at stmt ");
- if (stmt)
- print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- else
- fprintf (dump_file, " NULL\n");
- indent += bump;
- }
- super::range_of_ssa_name (r, name, stmt);
- trailer (idx, "range_of_ssa_name", true, name, r);
-}
-
-bool
-trace_gori_compute::range_of_expr (irange &r, tree name, gimple *stmt)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "range_of_expr (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") at stmt ");
- if (stmt)
- print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- else
- fprintf (dump_file, " NULL\n");
- indent += bump;
- }
- bool res = super::range_of_expr (r, name, stmt);
- return trailer (idx, "range_of_expr", res, name, r);
-}
-
-bool
-trace_gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name,
- const irange *name_range)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "outgoing_edge_range_p (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") on edge %d->%d, with range ", e->src->index,
- e->dest->index);
- if (name_range)
- {
- name_range->dump (dump_file);
- fprintf (dump_file, "\n");
- }
- else
- fputs ("NULL\n", dump_file);
- indent += bump;
- }
- bool res = super::outgoing_edge_range_p (r, e, name, name_range);
- return trailer (idx, "outgoing_edge_range_p", res, name, r);
-}
-
-bool
-trace_gori_compute::compute_operand_range (irange &r, gimple *stmt,
- const irange &lhs,
- tree name,
- const irange *name_range)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "compute_operand_range (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") with range ");
- if (name_range)
- name_range->dump (dump_file);
- else
- fputs ("NULL", dump_file);
- fprintf (dump_file, " at stmt:\n");
- dumping (idx, true);
- fputs (" ", dump_file);
- lhs.dump (dump_file);
- fprintf (dump_file, " <==> ");
- print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- indent += bump;
- }
- bool res = super::compute_operand_range (r, stmt, lhs, name, name_range);
- return trailer (idx, "compute_operand_range", res, name, r);
-}
-
-bool
-trace_gori_compute::compute_logical_operands (irange &r, gimple *stmt,
- const irange &lhs,
- tree name,
- const irange *name_range)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "compute_logical_operands (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") with range ");
- if (name_range)
- name_range->dump (dump_file);
- else
- fputs ("NULL", dump_file);
- fprintf (dump_file, " at stmt:\n");
- dumping (idx, true);
- fputs (" ", dump_file);
- lhs.dump (dump_file);
- fprintf (dump_file, " <==> ");
- print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- indent += bump;
- }
- bool res = super::compute_logical_operands (r, stmt, lhs, name, name_range);
- return trailer (idx, "compute_logical_operands", res, name, r);
-}
class logical_stmt_cache
{
@@ -1511,8 +1380,7 @@
bool
gori_compute_cache::compute_operand_range (irange &r, gimple *stmt,
const irange &lhs,
- tree name,
- const irange *name_range)
+ tree name)
{
bool cacheable = m_cache->cacheable_p (stmt, &lhs);
if (cacheable)
@@ -1525,12 +1393,10 @@
r = range.false_range;
else
r = range.true_range;
- if (name_range)
- r.intersect (*name_range);
return true;
}
}
- if (super::compute_operand_range (r, stmt, lhs, name, name_range))
+ if (super::compute_operand_range (r, stmt, lhs, name))
{
if (cacheable)
cache_comparison (stmt);
@@ -1563,7 +1429,7 @@
tree lhs = gimple_assign_lhs (stmt);
range_operator *handler = range_op_handler (code, TREE_TYPE (lhs));
widest_irange op2_range;
- gcc_assert (range_of_expr (op2_range, op2));
+ expr_range_in_bb (op2_range, op2, gimple_bb (stmt));
tree type = TREE_TYPE (op1);
handler->op1_range (r_true_side, type, m_bool_one, op2_range);
handler->op1_range (r_false_side, type, m_bool_zero, op2_range);
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 4724b68..5fc4080 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -22,192 +22,53 @@
#ifndef GCC_GIMPLE_RANGE_GORI_H
#define GCC_GIMPLE_RANGE_GORI_H
-/* RANGE_DEF_CHAIN is used to determine what SSA names in a block can
- have range information calculated for them, and what the
- dependencies on each other are.
-
- Information for a basic block is calculated once and stored. It is
- only calculated the first time a query is made, so if no queries
- are made, there is little overhead.
-
- The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
- within this bitmap to indicate SSA names that are defined in the
- SAME block and used to calculate this SSA name.
-
- One import is maintained per def-chain. An IMPORT is defined as an
- SSA name in the def chain which occurs outside the basic block. A
- change in the value of this SSA name can change the value of any
- name in the chain.
-
- If there is more than one import, or an ssa_name originates WITHIN
- the same basic block, but is defined by a statement that the range
- engine does not know how to calculate, then there is no import for
- the entire chain.
-
- <bb 2> :
- _1 = x_4(D) + -2;
- _2 = _1 * 4;
- j_7 = foo ();
- q_5 = _2 + 3;
- if (q_5 <= 13)
-
- _1 : (import : x_4(D)) :x_4(D)
- _2 : (import : x_4(D)) :_1 x_4(D)
- q_5 : (import : x_4(D)) :_1 _2 x_4(D)
-
- This dump indicates the bits set in the def_chain vector and their
- import, as well as demonstrates the def_chain bits for the related
- ssa_names.
-
- Checking the chain for _2 indicates that _1 and x_4 are used in
- its evaluation, and with x_4 being an import.
-
- For the purpose of defining an import, PHI node defintions are
- considered imports as they don't really reside in the block, but
- are accumulators of values from incoming edges.
-
- Def chains also only include statements which are valid gimple
- so a def chain will only span statements for which the range
- engine implements operations for. */
-
-
-class range_def_chain
-{
-public:
- range_def_chain ();
- ~range_def_chain ();
- tree terminal_name (tree name);
- bool has_def_chain (tree name);
- bitmap get_def_chain (tree name);
- bool in_chain_p (tree name, tree def);
-private:
- vec<bitmap> m_def_chain; // SSA_NAME : def chain components.
- vec<tree> m_terminal; // SSA_NAME : chain terminal name.
- tree build_def_chain (tree name, bitmap result, basic_block bb);
-};
-
-
-/* GORI_MAP is used to accumulate what SSA names in a block can
- generate range information, and provides tools for the block ranger
- to enable it to efficiently calculate these ranges.
-
- GORI stands for "Generates Outgoing Range Information."
-
- It utilizes the range_def_chain class to contruct def_chains.
- Information for a basic block is calculated once and stored. It is
- only calculated the first time a query is made. If no queries are
- made, there is little overhead.
-
- 2 bitmaps are maintained for each basic block:
-
- m_outgoing : a set bit indicates a range can be generated for a name.
- m_incoming : a set bit means a this name come from outside the
- block and is used in the calculation of some outgoing
- range.
-
- Generally speaking, the m_outgoing vector is the union of the
- entire def_chain of all SSA names used in the last statement of the
- block which generate ranges. The m_incoming vector is the union of
- all the terminal names of those def chains. They act as a one-stop
- summary for the block. */
-
-class gori_map : public range_def_chain
-{
-public:
- gori_map ();
- ~gori_map ();
-
- bool is_export_p (tree name, basic_block bb);
- bool def_chain_in_export_p (tree name, basic_block bb);
- bool is_import_p (tree name, basic_block bb);
-
- void dump (FILE *f);
- void dump (FILE *f, basic_block bb);
-private:
- bitmap_obstack m_bitmaps;
- vec<bitmap> m_outgoing; // BB: Outgoing ranges calculatable on edges
- vec<bitmap> m_incoming; // BB: block imports
- void maybe_add_gori (tree name, basic_block bb);
- void calculate_gori (basic_block bb);
- bitmap imports (basic_block bb);
-public:
- // FIXME: Temporarily set as public.
- bitmap exports (basic_block bb);
-};
-
-// Generic object to return a range for an SSA.
-class range_store
-{
-public:
- virtual bool range_of_expr (irange &r, tree expr, gimple *stmt = NULL) = 0;
- virtual const class value_range_equiv *get_value_range (const_tree expr,
- gimple *stmt = NULL);
-};
// This class utilizes a GORI map to determine which SSA_NAMES can
// have ranges calculated for them on outgoing edges from basic
// blocks.
-class gori_compute : public range_store
+class gori_compute
{
public:
gori_compute ();
- /* Destructor is virtual to silence:
-
- warning: deleting object of polymorphic class type ‘vr_values’
- which has non-virtual destructor might cause undefined
- behavior. */
- virtual ~gori_compute ();
- virtual bool range_of_expr (irange &r, tree expr, gimple *stmt = NULL);
- virtual bool outgoing_edge_range_p (irange &r, edge e, tree name,
- const irange *name_range = NULL);
-protected:
- virtual void range_of_ssa_name (irange &r, tree name, gimple *stmt = NULL);
- virtual bool compute_operand_range (irange &r, gimple *stmt,
- const irange &lhs,
- tree name,
- const irange *name_range = NULL);
+ ~gori_compute ();
+ bool outgoing_edge_range_p (irange &r, edge e, tree name);
bool has_edge_range_p (edge e, tree name);
- virtual bool compute_logical_operands (irange &r, gimple *stmt,
- const irange &lhs,
- tree name, const irange *name_range);
+ void dump (FILE *f);
+protected:
+ virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb) = 0;
+ virtual bool compute_operand_range (irange &r, gimple *stmt,
+ const irange &lhs, tree name);
+
+ void expr_range_in_bb (irange &r, tree expr, basic_block bb);
+ 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,
- const irange *name_range,
- tree op, bool op_in_chain);
- bool optimize_logical_operands (tf_range &range,
- gimple *stmt, const irange &lhs,
- tree name, const irange *name_range,
- tree op);
+ 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,
+ 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<1> m_bool_zero; // Boolean false cached.
int_range<1> m_bool_one; // Boolean true cached.
- gori_map m_gori_map;
private:
- void get_tree_range (irange &, tree expr, tree name,
- const irange *range_of_name);
bool compute_operand_range_switch (irange &r, gswitch *stmt,
- const irange &lhs,
- tree name, const irange *name_range);
- bool compute_name_range_op (irange &r, gimple *stmt,
- const irange &lhs,
- tree name, const irange *name_range);
- bool compute_operand1_range (irange &r, gimple *stmt,
- const irange &lhs,
- tree name, const irange *name_range);
- bool compute_operand2_range (irange &r, gimple *stmt,
- const irange &lhs,
- tree name, const irange *name_range);
- bool compute_operand1_and_operand2_range
- (irange &r, gimple *stmt,
- const irange &lhs,
- tree name, const irange *name_range);
+ const irange &lhs, tree name);
+ bool compute_name_range_op (irange &r, gimple *stmt, const irange &lhs,
+ tree name);
+ bool compute_operand1_range (irange &r, gimple *stmt, const irange &lhs,
+ tree name);
+ bool compute_operand2_range (irange &r, gimple *stmt, const irange &lhs,
+ tree name);
+ bool compute_operand1_and_operand2_range (irange &r, gimple *stmt,
+ const irange &lhs, tree name);
+
+ class gori_map *m_gori_map;
};
class gori_compute_cache : public gori_compute
@@ -217,9 +78,7 @@
~gori_compute_cache ();
protected:
virtual bool compute_operand_range (irange &r, gimple *stmt,
- const irange &lhs,
- tree name,
- const irange *name_range = NULL);
+ const irange &lhs, tree name);
private:
void cache_comparison (gimple *);
void cache_comparison_with_int (gimple *, enum tree_code,
@@ -230,32 +89,4 @@
class logical_stmt_cache *m_cache;
};
-class trace_gori_compute : public gori_compute_cache
-{
-public:
- trace_gori_compute ();
- virtual bool range_of_expr (irange &r, tree expr, gimple *stmt = NULL);
- virtual bool outgoing_edge_range_p (irange &r, edge e, tree name,
- const irange *name_range = NULL);
-protected:
- virtual void range_of_ssa_name (irange &r, tree name, gimple *stmt = NULL);
- virtual bool compute_operand_range (irange &r, gimple *stmt,
- const irange &lhs,
- tree name,
- const irange *name_range = NULL);
- virtual bool compute_logical_operands (irange &r, gimple *stmt,
- const irange &lhs,
- tree name, const irange *name_range);
-private:
- typedef gori_compute_cache super;
-protected:
- static const unsigned bump = 2;
- unsigned indent;
- unsigned trace_count; // Current trace index count.
-
- bool dumping (unsigned counter, bool trailing = false);
- bool trailer (unsigned counter, const char *caller, bool result, tree name,
- const irange &r);
-};
-
#endif // GCC_GIMPLE_RANGE_GORI_H
diff --git a/gcc/gimple-range-stmt.cc b/gcc/gimple-range-stmt.cc
deleted file mode 100644
index 81f2bb5..0000000
--- a/gcc/gimple-range-stmt.cc
+++ /dev/null
@@ -1,426 +0,0 @@
-/* Code for GIMPLE range related routines.
- Copyright (C) 2019-2020 Free Software Foundation, Inc.
- Contributed by Andrew MacLeod <amacleod@redhat.com>
- and Aldy Hernandez <aldyh@redhat.com>.
-
-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
-<http://www.gnu.org/licenses/>. */
-
-#include "config.h"
-#include "system.h"
-#include "coretypes.h"
-#include "backend.h"
-#include "insn-codes.h"
-#include "rtl.h"
-#include "tree.h"
-#include "gimple.h"
-#include "ssa.h"
-#include "gimple-iterator.h"
-#include "tree-cfg.h"
-#include "gimple-range-stmt.h"
-
-// Adjust the range for a pointer difference where the operands came
-// from a memchr.
-//
-// This notices the following sequence:
-//
-// def = __builtin_memchr (arg, 0, sz)
-// n = def - arg
-//
-// The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
-
-static void
-adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt)
-{
- tree op0 = gimple_assign_rhs1 (diff_stmt);
- tree op1 = gimple_assign_rhs2 (diff_stmt);
- tree op0_ptype = TREE_TYPE (TREE_TYPE (op0));
- tree op1_ptype = TREE_TYPE (TREE_TYPE (op1));
- gimple *call;
-
- if (TREE_CODE (op0) == SSA_NAME
- && TREE_CODE (op1) == SSA_NAME
- && (call = SSA_NAME_DEF_STMT (op0))
- && is_gimple_call (call)
- && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
- && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node)
- && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node)
- && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node)
- && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node)
- && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
- && vrp_operand_equal_p (op1, gimple_call_arg (call, 0))
- && integer_zerop (gimple_call_arg (call, 1)))
- {
- tree max = vrp_val_max (ptrdiff_type_node);
- wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
- tree expr_type = gimple_expr_type (diff_stmt);
- tree range_min = build_zero_cst (expr_type);
- tree range_max = wide_int_to_tree (expr_type, wmax - 1);
- int_range<1> r (range_min, range_max);
- res.intersect (r);
- }
-}
-
-// This function looks for situations when walking the use/def chains
-// may provide additonal contextual range information not exposed on
-// this statement. Like knowing the IMAGPART return value from a
-// builtin function is a boolean result.
-
-// We should rework how we're called, as we have an op_unknown entry
-// for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this
-// function gets called.
-
-static void
-gimple_range_adjustment (irange &res, const gimple *stmt)
-{
- switch (gimple_expr_code (stmt))
- {
- case POINTER_DIFF_EXPR:
- adjust_pointer_diff_expr (res, stmt);
- return;
-
- case IMAGPART_EXPR:
- {
- tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
- if (TREE_CODE (name) == SSA_NAME)
- {
- gimple *def_stmt = SSA_NAME_DEF_STMT (name);
- if (def_stmt && is_gimple_call (def_stmt)
- && gimple_call_internal_p (def_stmt))
- {
- switch (gimple_call_internal_fn (def_stmt))
- {
- case IFN_ADD_OVERFLOW:
- case IFN_SUB_OVERFLOW:
- case IFN_MUL_OVERFLOW:
- case IFN_ATOMIC_COMPARE_EXCHANGE:
- {
- int_range<1> r;
- r.set_varying (boolean_type_node);
- tree type = TREE_TYPE (gimple_assign_lhs (stmt));
- range_cast (r, type);
- res.intersect (r);
- }
- default:
- break;
- }
- }
- }
- break;
- }
-
- default:
- break;
- }
-}
-
-// ------------------------------------------------------------------------
-
-// This function will calculate the "constant" range on edge E from
-// switch SW returning it in R, and return the switch statement
-// itself. This is currently not very efficent as the way we
-// represent switches in GIMPLE does not map well to this calculation.
-
-static gimple *
-calc_range_for_switch_on_edge (irange &r, gswitch *sw, edge e)
-{
- unsigned x, lim;
- lim = gimple_switch_num_labels (sw);
- tree type = TREE_TYPE (gimple_switch_index (sw));
-
- // ADA and FORTRAN currently have cases where the index is 64 bits
- // and the case arguments are 32 bit, causing a trap when we create
- // a case_range. Until this is resolved
- // (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798) punt on
- // these switches. Furthermore, cfamily fails during a bootstrap
- // due to a signed index and unsigned cases. So punting unless
- // types_compatible_p () for now.
- tree case_type = TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)));
- if (lim > 1 && !types_compatible_p (type, case_type))
- return NULL;
-
- edge default_edge = gimple_switch_default_edge (cfun, sw);
- if (e != default_edge)
- {
- r.set_undefined ();
- // Union all the ranges for each switch edge, ignoring the
- // default edge.
- for (x = 1; x < lim; x++)
- {
- if (gimple_switch_edge (cfun, sw, x) != e)
- continue;
- tree low = CASE_LOW (gimple_switch_label (sw, x));
- tree high = CASE_HIGH (gimple_switch_label (sw, x));
- if (!high)
- high = low;
- int_range<1> case_range (low, high);
- r.union_ (case_range);
- }
- }
- else
- {
- r.set_varying (type);
- // Loop through all the switches edges, ignoring the default
- // edge, while intersecting the ranges not covered by the case.
- for (x = 1; x < lim; x++)
- {
- // Some other edge could still point to the default edge
- // destination. Ignore it.
- if (gimple_switch_edge (cfun, sw, x) == default_edge)
- continue;
- tree low = CASE_LOW (gimple_switch_label (sw, x));
- tree high = CASE_HIGH (gimple_switch_label (sw, x));
- if (!high)
- high = low;
- int_range<1> case_range (low, high, VR_ANTI_RANGE);
- r.intersect (case_range);
- }
- }
- return sw;
-}
-
-
-// If there is a range control statment at the end of block BB, return it.
-
-gimple_stmt_iterator
-gsi_outgoing_range_stmt (basic_block bb)
-{
- gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
- if (!gsi_end_p (gsi))
- {
- gimple *s = gsi_stmt (gsi);
- if (is_a<gcond *> (s) || is_a<gswitch *> (s))
- return gsi;
- }
- return gsi_none ();
-}
-
-
-// If there is a range control statment at the end of block BB, return it.
-
-gimple *
-gimple_outgoing_range_stmt_p (basic_block bb)
-{
- // This will return NULL if there is not a branch statement.
- return gsi_stmt (gsi_outgoing_range_stmt (bb));
-}
-
-
-// Calculate the range forced on on edge E by control flow, return it
-// in R. Return the statment which defines the range, otherwise
-// return NULL
-
-gimple *
-gimple_outgoing_edge_range_p (irange &r, edge e)
-{
- // Determine if there is an outgoing edge.
- gimple *s = gimple_outgoing_range_stmt_p (e->src);
- if (!s)
- return NULL;
-
- if (is_a<gcond *> (s))
- {
- if (e->flags & EDGE_TRUE_VALUE)
- r = int_range<1> (boolean_true_node, boolean_true_node);
- else if (e->flags & EDGE_FALSE_VALUE)
- r = int_range<1> (boolean_false_node, boolean_false_node);
- else
- gcc_unreachable ();
- return s;
- }
-
- gcc_checking_assert (is_a<gswitch *> (s));
- gswitch *sw = as_a<gswitch *> (s);
- tree type = TREE_TYPE (gimple_switch_index (sw));
-
- if (!irange::supports_type_p (type))
- return NULL;
-
- return calc_range_for_switch_on_edge (r, sw, e);
-}
-
-
-
-// Fold this unary statement using R1 as operand1's range, returning
-// the result in RES. Return false if the operation fails.
-
-bool
-gimple_range_fold (const gimple *stmt, irange &res, const irange &r1)
-{
- gcc_checking_assert (gimple_range_handler (stmt));
-
- tree type = gimple_expr_type (stmt);
- // Unary SSA operations require the LHS type as the second range.
- int_range<1> r2 (type);
-
- return gimple_range_fold (stmt, res, r1, r2);
-}
-
-
-// Fold this binary statement using R1 and R2 as the operands ranges,
-// returning the result in RES. Return false if the operation fails.
-
-bool
-gimple_range_fold (const gimple *stmt, irange &res,
- const irange &r1, const irange &r2)
-{
- gcc_checking_assert (gimple_range_handler (stmt));
-
- gimple_range_handler (stmt)->fold_range (res, gimple_expr_type (stmt),
- r1, r2);
-
- // If there are any gimple lookups, do those now.
- gimple_range_adjustment (res, stmt);
- return true;
-}
-
-// Return the base of the RHS of an assignment.
-
-tree
-gimple_range_base_of_assignment (const gimple *stmt)
-{
- gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
- tree op1 = gimple_assign_rhs1 (stmt);
- if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
- return get_base_address (TREE_OPERAND (op1, 0));
- return op1;
-}
-
-// Return the first operand of this statement if it is a valid operand
-// supported by ranges, otherwise return NULL_TREE. Special case is
-// &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr.
-
-tree
-gimple_range_operand1 (const gimple *stmt)
-{
- gcc_checking_assert (gimple_range_handler (stmt));
-
- switch (gimple_code (stmt))
- {
- case GIMPLE_COND:
- return gimple_cond_lhs (stmt);
- case GIMPLE_ASSIGN:
- {
- tree base = gimple_range_base_of_assignment (stmt);
- if (base && TREE_CODE (base) == MEM_REF)
- {
- // If the base address is an SSA_NAME, we return it
- // here. This allows processing of the range of that
- // name, while the rest of the expression is simply
- // ignored. The code in range_ops will see the
- // ADDR_EXPR and do the right thing.
- tree ssa = TREE_OPERAND (base, 0);
- if (TREE_CODE (ssa) == SSA_NAME)
- return ssa;
- }
- return base;
- }
- default:
- break;
- }
- return NULL;
-}
-
-
-// Return the second operand of statement STMT, otherwise return NULL_TREE.
-
-tree
-gimple_range_operand2 (const gimple *stmt)
-{
- gcc_checking_assert (gimple_range_handler (stmt));
-
- switch (gimple_code (stmt))
- {
- case GIMPLE_COND:
- return gimple_cond_rhs (stmt);
- case GIMPLE_ASSIGN:
- if (gimple_num_ops (stmt) >= 3)
- return gimple_assign_rhs2 (stmt);
- default:
- break;
- }
- return NULL_TREE;
-}
-
-
-
-// Calculate what we can determine of the range of this unary
-// statement's operand if the lhs of the expression has the range
-// LHS_RANGE. Return false if nothing can be determined.
-
-bool
-gimple_range_calc_op1 (const gimple *stmt, irange &r, const irange &lhs_range)
-{
- gcc_checking_assert (gimple_num_ops (stmt) < 3);
- // An empty range is viral, so return an empty range.
-
- tree type = TREE_TYPE (gimple_range_operand1 (stmt));
- if (lhs_range.undefined_p ())
- {
- r.set_undefined ();
- return true;
- }
- // Unary operations require the type of the first operand in the
- // second range position.
- int_range<1> type_range (type);
- return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
- type_range);
-}
-
-
-// Calculate what we can determine of the range of this statement's
-// first operand if the lhs of the expression has the range LHS_RANGE
-// and the second operand has the range OP2_RANGE. Return false if
-// nothing can be determined.
-
-bool
-gimple_range_calc_op1 (const gimple *stmt, irange &r,
- const irange &lhs_range, const irange &op2_range)
-{
- // Unary operation are allowed to pass a range in for second operand
- // as there are often additional restrictions beyond the type which
- // can be imposed. See operator_cast::op1_range.()
- tree type = TREE_TYPE (gimple_range_operand1 (stmt));
- // An empty range is viral, so return an empty range.
- if (op2_range.undefined_p () || lhs_range.undefined_p ())
- {
- r.set_undefined ();
- return true;
- }
- return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
- op2_range);
-}
-
-
-// Calculate what we can determine of the range of this statement's
-// second operand if the lhs of the expression has the range LHS_RANGE
-// and the first operand has the range OP1_RANGE. Return false if
-// nothing can be determined.
-
-bool
-gimple_range_calc_op2 (const gimple *stmt, irange &r,
- const irange &lhs_range, const irange &op1_range)
-{
- tree type = TREE_TYPE (gimple_range_operand2 (stmt));
- // An empty range is viral, so return an empty range.
- if (op1_range.undefined_p () || lhs_range.undefined_p ())
- {
- r.set_undefined ();
- return true;
- }
- return gimple_range_handler (stmt)->op2_range (r, type, lhs_range,
- op1_range);
-}
diff --git a/gcc/gimple-range-stmt.h b/gcc/gimple-range-stmt.h
deleted file mode 100644
index c27f15d..0000000
--- a/gcc/gimple-range-stmt.h
+++ /dev/null
@@ -1,99 +0,0 @@
-/* Header file for the GIMPLE range interface.
- Copyright (C) 2019-2020 Free Software Foundation, Inc.
- Contributed by Andrew MacLeod <amacleod@redhat.com>
- and Aldy Hernandez <aldyh@redhat.com>.
-
-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
-<http://www.gnu.org/licenses/>. */
-
-#ifndef GCC_GIMPLE_RANGE_STMT_H
-#define GCC_GIMPLE_RANGE_STMT_H
-
-
-#include "range.h"
-#include "range-op.h"
-
-// If BB ends with a range generating stmt, return its GSI.
-extern gimple_stmt_iterator gsi_outgoing_range_stmt (basic_block bb);
-// If BB ends with a range generating stmt, return that stmt.
-extern gimple *gimple_outgoing_range_stmt_p (basic_block bb);
-// If edge E has a constant range, return it and the range generating
-// statement. for conditonals its TRUE/FALSE, for switches its the
-// possible cases.
-extern gimple *gimple_outgoing_edge_range_p (irange &r, edge e);
-
-// These routines provide a GIMPLE interface to the range-ops code.
-extern tree gimple_range_operand1 (const gimple *s);
-extern tree gimple_range_operand2 (const gimple *s);
-extern tree gimple_range_base_of_assignment (const gimple *s);
-extern bool gimple_range_fold (const gimple *s, irange &res,
- const irange &r1);
-extern bool gimple_range_fold (const gimple *s, irange &res,
- const irange &r1,
- const irange &r2);
-extern bool gimple_range_calc_op1 (const gimple *s, irange &r,
- const irange &lhs_range);
-extern bool gimple_range_calc_op1 (const gimple *s, irange &r,
- const irange &lhs_range,
- const irange &op2_range);
-extern bool gimple_range_calc_op2 (const gimple *s, irange &r,
- const irange &lhs_range,
- const irange &op1_range);
-
-
-// Return the range_operator pointer for this statement. This routine
-// can also be used to gate whether a routine is range-ops enabled.
-
-static inline range_operator *
-gimple_range_handler (const gimple *s)
-{
- if ((gimple_code (s) == GIMPLE_ASSIGN) || (gimple_code (s) == GIMPLE_COND))
- return range_op_handler (gimple_expr_code (s), gimple_expr_type (s));
- return NULL;
-}
-
-// Return EXP if it is an SSA_NAME with a type supported by gimple ranges.
-
-static inline tree
-gimple_range_ssa_p (tree exp)
-{
- if (exp && TREE_CODE (exp) == SSA_NAME &&
- !SSA_NAME_IS_VIRTUAL_OPERAND (exp) &&
- irange::supports_type_p (TREE_TYPE (exp)))
- return exp;
- return NULL_TREE;
-}
-
-// Return the legacy GCC global range for NAME if it has one, otherwise
-// return VARYING.
-
-static inline value_range
-gimple_range_global (tree name)
-{
- gcc_checking_assert (gimple_range_ssa_p (name));
- tree type = TREE_TYPE (name);
- if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
- {
- // Return a range from an SSA_NAME's available range.
- wide_int min, max;
- enum value_range_kind kind = get_range_info (name, &min, &max);
- return value_range (type, min, max, kind);
- }
- // Otherwise return range for the type.
- return value_range (type);
-}
-
-#endif // GCC_GIMPLE_RANGE_STMT_H
diff --git a/gcc/gimple-ranger-vrp.cc b/gcc/gimple-range-vrp.cc
similarity index 89%
rename from gcc/gimple-ranger-vrp.cc
rename to gcc/gimple-range-vrp.cc
index 02bb1a3..4956813 100644
--- a/gcc/gimple-ranger-vrp.cc
+++ b/gcc/gimple-range-vrp.cc
@@ -42,12 +42,12 @@
#include "tree-cfgcleanup.h"
#include "vr-values.h"
#include "gimple-ssa-evrp-analyze.h"
-#include "gimple-ranger.h"
+#include "gimple-range.h"
-class rvrp_ranger : public trace_ranger
+class rvrp_ranger : public range_store
{
public:
- rvrp_ranger () : trace_ranger (), range_pool ("rvrp value range pool") { }
+ rvrp_ranger () : range_pool ("rvrp value range pool") { }
~rvrp_ranger ()
{
range_pool.release ();
@@ -58,10 +58,15 @@
gimple *stmt) OVERRIDE
{
widest_irange r;
- if (range_of_expr (r, const_cast<tree> (expr), stmt))
+ if (ranger.range_of_expr (r, const_cast<tree> (expr), stmt))
return new (range_pool.allocate ()) value_range_equiv (r);
return new (range_pool.allocate ()) value_range_equiv (TREE_TYPE (expr));
}
+ virtual bool range_of_expr (irange &r, tree expr, gimple *stmt = NULL)
+ {
+ return ranger.range_of_expr (r, expr, stmt);
+ }
+ gimple_ranger ranger;
private:
object_allocator<value_range_equiv> range_pool;
};
@@ -76,7 +81,7 @@
{
widest_irange r;
tree singleton;
- if (ranger.range_of_expr (r, op, stmt) && r.singleton_p (&singleton)
+ if (ranger.ranger.range_of_expr (r, op, stmt) && r.singleton_p (&singleton)
&& allow_il_changes)
return singleton;
return NULL;
@@ -88,7 +93,7 @@
return false;
widest_irange r;
- if (ranger.range_of_stmt (r, cond) && r.singleton_p ())
+ if (ranger.ranger.range_of_stmt (r, cond) && r.singleton_p ())
{
if (allow_il_changes)
{
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
new file mode 100644
index 0000000..e6cbb3a
--- /dev/null
+++ b/gcc/gimple-range.cc
@@ -0,0 +1,1309 @@
+/* Code for GIMPLE range related routines.
+ Copyright (C) 2019-2020 Free Software Foundation, Inc.
+ Contributed by Andrew MacLeod <amacleod@redhat.com>
+ and Aldy Hernandez <aldyh@redhat.com>.
+
+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
+<http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "insn-codes.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "gimple-iterator.h"
+#include "optabs-tree.h"
+#include "gimple-fold.h"
+#include "tree-cfg.h"
+#include "fold-const.h"
+#include "tree-cfg.h"
+#include "wide-int.h"
+#include "fold-const.h"
+#include "case-cfn-macros.h"
+#include "omp-general.h"
+#include "cfgloop.h"
+#include "tree-ssa-loop.h"
+#include "tree-scalar-evolution.h"
+#include "dbgcnt.h"
+#include "alloc-pool.h"
+#include "vr-values.h"
+#include "gimple-range.h"
+
+
+// Adjust the range for a pointer difference where the operands came
+// from a memchr.
+//
+// This notices the following sequence:
+//
+// def = __builtin_memchr (arg, 0, sz)
+// n = def - arg
+//
+// The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
+
+static void
+adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt)
+{
+ tree op0 = gimple_assign_rhs1 (diff_stmt);
+ tree op1 = gimple_assign_rhs2 (diff_stmt);
+ tree op0_ptype = TREE_TYPE (TREE_TYPE (op0));
+ tree op1_ptype = TREE_TYPE (TREE_TYPE (op1));
+ gimple *call;
+
+ if (TREE_CODE (op0) == SSA_NAME
+ && TREE_CODE (op1) == SSA_NAME
+ && (call = SSA_NAME_DEF_STMT (op0))
+ && is_gimple_call (call)
+ && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
+ && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node)
+ && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node)
+ && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node)
+ && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node)
+ && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
+ && vrp_operand_equal_p (op1, gimple_call_arg (call, 0))
+ && integer_zerop (gimple_call_arg (call, 1)))
+ {
+ tree max = vrp_val_max (ptrdiff_type_node);
+ wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
+ tree expr_type = gimple_expr_type (diff_stmt);
+ tree range_min = build_zero_cst (expr_type);
+ tree range_max = wide_int_to_tree (expr_type, wmax - 1);
+ int_range<1> r (range_min, range_max);
+ res.intersect (r);
+ }
+}
+
+// This function looks for situations when walking the use/def chains
+// may provide additonal contextual range information not exposed on
+// this statement. Like knowing the IMAGPART return value from a
+// builtin function is a boolean result.
+
+// We should rework how we're called, as we have an op_unknown entry
+// for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this
+// function gets called.
+
+static void
+gimple_range_adjustment (irange &res, const gimple *stmt)
+{
+ switch (gimple_expr_code (stmt))
+ {
+ case POINTER_DIFF_EXPR:
+ adjust_pointer_diff_expr (res, stmt);
+ return;
+
+ case IMAGPART_EXPR:
+ {
+ tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
+ if (TREE_CODE (name) == SSA_NAME)
+ {
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+ if (def_stmt && is_gimple_call (def_stmt)
+ && gimple_call_internal_p (def_stmt))
+ {
+ switch (gimple_call_internal_fn (def_stmt))
+ {
+ case IFN_ADD_OVERFLOW:
+ case IFN_SUB_OVERFLOW:
+ case IFN_MUL_OVERFLOW:
+ case IFN_ATOMIC_COMPARE_EXCHANGE:
+ {
+ int_range<1> r;
+ r.set_varying (boolean_type_node);
+ tree type = TREE_TYPE (gimple_assign_lhs (stmt));
+ range_cast (r, type);
+ res.intersect (r);
+ }
+ default:
+ break;
+ }
+ }
+ }
+ break;
+ }
+
+ default:
+ break;
+ }
+}
+
+// ------------------------------------------------------------------------
+
+// This function will calculate the "constant" range on edge E from
+// switch SW returning it in R, and return the switch statement
+// itself. This is currently not very efficent as the way we
+// represent switches in GIMPLE does not map well to this calculation.
+
+static gimple *
+calc_range_for_switch_on_edge (irange &r, gswitch *sw, edge e)
+{
+ unsigned x, lim;
+ lim = gimple_switch_num_labels (sw);
+ tree type = TREE_TYPE (gimple_switch_index (sw));
+
+ // ADA and FORTRAN currently have cases where the index is 64 bits
+ // and the case arguments are 32 bit, causing a trap when we create
+ // a case_range. Until this is resolved
+ // (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798) punt on
+ // these switches. Furthermore, cfamily fails during a bootstrap
+ // due to a signed index and unsigned cases. So punting unless
+ // types_compatible_p () for now.
+ tree case_type = TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)));
+ if (lim > 1 && !types_compatible_p (type, case_type))
+ return NULL;
+
+ edge default_edge = gimple_switch_default_edge (cfun, sw);
+ if (e != default_edge)
+ {
+ r.set_undefined ();
+ // Union all the ranges for each switch edge, ignoring the
+ // default edge.
+ for (x = 1; x < lim; x++)
+ {
+ if (gimple_switch_edge (cfun, sw, x) != e)
+ continue;
+ tree low = CASE_LOW (gimple_switch_label (sw, x));
+ tree high = CASE_HIGH (gimple_switch_label (sw, x));
+ if (!high)
+ high = low;
+ int_range<1> case_range (low, high);
+ r.union_ (case_range);
+ }
+ }
+ else
+ {
+ r.set_varying (type);
+ // Loop through all the switches edges, ignoring the default
+ // edge, while intersecting the ranges not covered by the case.
+ for (x = 1; x < lim; x++)
+ {
+ // Some other edge could still point to the default edge
+ // destination. Ignore it.
+ if (gimple_switch_edge (cfun, sw, x) == default_edge)
+ continue;
+ tree low = CASE_LOW (gimple_switch_label (sw, x));
+ tree high = CASE_HIGH (gimple_switch_label (sw, x));
+ if (!high)
+ high = low;
+ int_range<1> case_range (low, high, VR_ANTI_RANGE);
+ r.intersect (case_range);
+ }
+ }
+ return sw;
+}
+
+
+// If there is a range control statment at the end of block BB, return it.
+
+gimple_stmt_iterator
+gsi_outgoing_range_stmt (basic_block bb)
+{
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+ if (!gsi_end_p (gsi))
+ {
+ gimple *s = gsi_stmt (gsi);
+ if (is_a<gcond *> (s) || is_a<gswitch *> (s))
+ return gsi;
+ }
+ return gsi_none ();
+}
+
+
+// If there is a range control statment at the end of block BB, return it.
+
+gimple *
+gimple_outgoing_range_stmt_p (basic_block bb)
+{
+ // This will return NULL if there is not a branch statement.
+ return gsi_stmt (gsi_outgoing_range_stmt (bb));
+}
+
+
+// Calculate the range forced on on edge E by control flow, return it
+// in R. Return the statment which defines the range, otherwise
+// return NULL
+
+gimple *
+gimple_outgoing_edge_range_p (irange &r, edge e)
+{
+ // Determine if there is an outgoing edge.
+ gimple *s = gimple_outgoing_range_stmt_p (e->src);
+ if (!s)
+ return NULL;
+
+ if (is_a<gcond *> (s))
+ {
+ if (e->flags & EDGE_TRUE_VALUE)
+ r = int_range<1> (boolean_true_node, boolean_true_node);
+ else if (e->flags & EDGE_FALSE_VALUE)
+ r = int_range<1> (boolean_false_node, boolean_false_node);
+ else
+ gcc_unreachable ();
+ return s;
+ }
+
+ gcc_checking_assert (is_a<gswitch *> (s));
+ gswitch *sw = as_a<gswitch *> (s);
+ tree type = TREE_TYPE (gimple_switch_index (sw));
+
+ if (!irange::supports_type_p (type))
+ return NULL;
+
+ return calc_range_for_switch_on_edge (r, sw, e);
+}
+
+
+// Return a range in R for the tree EXPR. Return true if a range is
+// representable.
+
+bool
+get_tree_range (irange &r, tree expr)
+{
+ tree type;
+ if (TYPE_P (expr))
+ type = expr;
+ else
+ type = TREE_TYPE (expr);
+
+ // Return false if the type isn't suported.
+ if (!irange::supports_type_p (type))
+ return false;
+
+ switch (TREE_CODE (expr))
+ {
+ case INTEGER_CST:
+ r.set (expr, expr);
+ return true;
+
+ case SSA_NAME:
+ r = gimple_range_global (expr);
+ 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.set_varying (type);
+ return true;
+}
+
+// Fold this unary statement using R1 as operand1's range, returning
+// the result in RES. Return false if the operation fails.
+
+bool
+gimple_range_fold (irange &res, const gimple *stmt, const irange &r1)
+{
+ gcc_checking_assert (gimple_range_handler (stmt));
+
+ tree type = gimple_expr_type (stmt);
+ // Unary SSA operations require the LHS type as the second range.
+ int_range<1> r2 (type);
+
+ return gimple_range_fold (res, stmt, r1, r2);
+}
+
+
+// Fold this binary statement using R1 and R2 as the operands ranges,
+// returning the result in RES. Return false if the operation fails.
+
+bool
+gimple_range_fold (irange &res, const gimple *stmt,
+ const irange &r1, const irange &r2)
+{
+ gcc_checking_assert (gimple_range_handler (stmt));
+
+ gimple_range_handler (stmt)->fold_range (res, gimple_expr_type (stmt),
+ r1, r2);
+
+ // If there are any gimple lookups, do those now.
+ gimple_range_adjustment (res, stmt);
+ return true;
+}
+
+// Return the base of the RHS of an assignment.
+
+tree
+gimple_range_base_of_assignment (const gimple *stmt)
+{
+ gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
+ tree op1 = gimple_assign_rhs1 (stmt);
+ if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
+ return get_base_address (TREE_OPERAND (op1, 0));
+ return op1;
+}
+
+// Return the first operand of this statement if it is a valid operand
+// supported by ranges, otherwise return NULL_TREE. Special case is
+// &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr.
+
+tree
+gimple_range_operand1 (const gimple *stmt)
+{
+ gcc_checking_assert (gimple_range_handler (stmt));
+
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_COND:
+ return gimple_cond_lhs (stmt);
+ case GIMPLE_ASSIGN:
+ {
+ tree base = gimple_range_base_of_assignment (stmt);
+ if (base && TREE_CODE (base) == MEM_REF)
+ {
+ // If the base address is an SSA_NAME, we return it
+ // here. This allows processing of the range of that
+ // name, while the rest of the expression is simply
+ // ignored. The code in range_ops will see the
+ // ADDR_EXPR and do the right thing.
+ tree ssa = TREE_OPERAND (base, 0);
+ if (TREE_CODE (ssa) == SSA_NAME)
+ return ssa;
+ }
+ return base;
+ }
+ default:
+ break;
+ }
+ return NULL;
+}
+
+
+// Return the second operand of statement STMT, otherwise return NULL_TREE.
+
+tree
+gimple_range_operand2 (const gimple *stmt)
+{
+ gcc_checking_assert (gimple_range_handler (stmt));
+
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_COND:
+ return gimple_cond_rhs (stmt);
+ case GIMPLE_ASSIGN:
+ if (gimple_num_ops (stmt) >= 3)
+ return gimple_assign_rhs2 (stmt);
+ default:
+ break;
+ }
+ return NULL_TREE;
+}
+
+
+
+// Calculate what we can determine of the range of this unary
+// statement's operand if the lhs of the expression has the range
+// LHS_RANGE. Return false if nothing can be determined.
+
+bool
+gimple_range_calc_op1 (irange &r, const gimple *stmt, const irange &lhs_range)
+{
+ gcc_checking_assert (gimple_num_ops (stmt) < 3);
+ // An empty range is viral, so return an empty range.
+
+ tree type = TREE_TYPE (gimple_range_operand1 (stmt));
+ if (lhs_range.undefined_p ())
+ {
+ r.set_undefined ();
+ return true;
+ }
+ // Unary operations require the type of the first operand in the
+ // second range position.
+ int_range<1> type_range (type);
+ return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
+ type_range);
+}
+
+
+// Calculate what we can determine of the range of this statement's
+// first operand if the lhs of the expression has the range LHS_RANGE
+// and the second operand has the range OP2_RANGE. Return false if
+// nothing can be determined.
+
+bool
+gimple_range_calc_op1 (irange &r, const gimple *stmt,
+ const irange &lhs_range, const irange &op2_range)
+{
+ // Unary operation are allowed to pass a range in for second operand
+ // as there are often additional restrictions beyond the type which
+ // can be imposed. See operator_cast::op1_range.()
+ tree type = TREE_TYPE (gimple_range_operand1 (stmt));
+ // An empty range is viral, so return an empty range.
+ if (op2_range.undefined_p () || lhs_range.undefined_p ())
+ {
+ r.set_undefined ();
+ return true;
+ }
+ return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
+ op2_range);
+}
+
+
+// Calculate what we can determine of the range of this statement's
+// second operand if the lhs of the expression has the range LHS_RANGE
+// and the first operand has the range OP1_RANGE. Return false if
+// nothing can be determined.
+
+bool
+gimple_range_calc_op2 (irange &r, const gimple *stmt,
+ const irange &lhs_range, const irange &op1_range)
+{
+ tree type = TREE_TYPE (gimple_range_operand2 (stmt));
+ // An empty range is viral, so return an empty range.
+ if (op1_range.undefined_p () || lhs_range.undefined_p ())
+ {
+ r.set_undefined ();
+ return true;
+ }
+ return gimple_range_handler (stmt)->op2_range (r, type, lhs_range,
+ op1_range);
+}
+
+
+// Calculate a range for statement S and return it in R. If NAME is provided it
+// represents the SSA_NAME on the LHS of the statement. It is only required
+// if there is more than one lhs/output. If a range cannot
+// be calculated, return false.
+
+bool
+gimple_ranger::calc_stmt (irange &r, gimple *s, tree name)
+{
+ bool res = false;
+ // If name is specified, make sure it is a LHS of S.
+ gcc_checking_assert (name ? SSA_NAME_DEF_STMT (name) == s : true);
+
+ if (gimple_range_handler (s))
+ res = range_of_range_op (r, s);
+ else if (is_a<gphi *>(s))
+ res = range_of_phi (r, as_a<gphi *> (s));
+ else if (is_a<gcall *>(s))
+ res = range_of_call (r, as_a<gcall *> (s));
+ else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
+ res = range_of_cond_expr (r, as_a<gassign *> (s));
+ else
+ {
+ // If no name is specified, try the expression kind.
+ if (!name)
+ {
+ tree t = gimple_expr_type (s);
+ if (!irange::supports_type_p (t))
+ return false;
+ r.set_varying (t);
+ return true;
+ }
+ // We don't understand the stmt, so return the global range.
+ r = gimple_range_global (name);
+ return true;
+ }
+ if (res)
+ {
+ if (r.undefined_p ())
+ return true;
+ if (name && TREE_TYPE (name) != r.type ())
+ range_cast (r, TREE_TYPE (name));
+ return true;
+ }
+ return false;
+}
+
+// Calculate a range for range_op statement S and return it in R. If any
+// If a range cannot be calculated, return false.
+
+bool
+gimple_ranger::range_of_range_op (irange &r, gimple *s)
+{
+ widest_irange range1, range2;
+ tree type = gimple_expr_type (s);
+ gcc_checking_assert (irange::supports_type_p (type));
+
+ tree op1 = gimple_range_operand1 (s);
+ tree op2 = gimple_range_operand2 (s);
+
+ if (range_of_non_trivial_assignment (r, s))
+ return true;
+
+ if (range_of_expr (range1, op1, s))
+ {
+ if (!op2)
+ return gimple_range_fold (r, s, range1);
+
+ if (range_of_expr (range2, op2, s))
+ return gimple_range_fold (r, s, range1, range2);
+ }
+ r.set_varying (type);
+ return true;
+}
+
+
+// Calculate the range of a non-trivial assignment. That is, is one
+// inolving arithmetic on an SSA name (for example, an ADDR_EXPR).
+// Return the range in R.
+//
+// If a range cannot be calculated, return false.
+
+bool
+gimple_ranger::range_of_non_trivial_assignment (irange &r, gimple *stmt)
+{
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return false;
+
+ tree base = gimple_range_base_of_assignment (stmt);
+ if (base && TREE_CODE (base) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
+ {
+ widest_irange range1;
+ tree ssa = TREE_OPERAND (base, 0);
+ if (range_of_expr (range1, ssa, stmt))
+ {
+ tree type = TREE_TYPE (ssa);
+ range_operator *op = range_op_handler (POINTER_PLUS_EXPR, type);
+ int_range<1> offset (TREE_OPERAND (base, 1), TREE_OPERAND (base, 1));
+ op->fold_range (r, type, range1, offset);
+ return true;
+ }
+ }
+ return false;
+}
+
+
+// Calculate a range for phi statement S and return it in R.
+// If a range cannot be calculated, return false.
+
+bool
+gimple_ranger::range_of_phi (irange &r, gphi *phi)
+{
+ tree phi_def = gimple_phi_result (phi);
+ tree type = TREE_TYPE (phi_def);
+ widest_irange phi_range;
+ unsigned x;
+
+ if (!irange::supports_type_p (type))
+ return false;
+
+ // And start with an empty range, unioning in each argument's range.
+ r.set_undefined ();
+ for (x = 0; x < gimple_phi_num_args (phi); x++)
+ {
+ widest_irange arg_range;
+ tree arg = gimple_phi_arg_def (phi, x);
+ edge e = gimple_phi_arg_edge (phi, x);
+
+ range_on_edge (arg_range, e, arg);
+ r.union_ (arg_range);
+ // Once the value reaches varying, stop looking.
+ if (r.varying_p ())
+ break;
+ }
+
+ return true;
+}
+
+
+// Calculate a range for call statement S and return it in R.
+// If a range cannot be calculated, return false.
+
+bool
+gimple_ranger::range_of_call (irange &r, gcall *call)
+{
+ tree type = gimple_call_return_type (call);
+ tree lhs = gimple_call_lhs (call);
+ bool strict_overflow_p;
+
+ if (!irange::supports_type_p (type))
+ return false;
+
+ if (range_of_builtin_call (r, call))
+ ;
+ else if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p))
+ r.set (build_int_cst (type, 0), TYPE_MAX_VALUE (type));
+ else if (gimple_call_nonnull_result_p (call)
+ || gimple_call_nonnull_arg (call))
+ r = range_nonzero (type);
+ else
+ r.set_varying (type);
+
+ // If there is a lHS, intersect that with what is known.
+ if (lhs)
+ {
+ value_range def;
+ def = gimple_range_global (lhs);
+ r.intersect (def);
+ }
+ return true;
+}
+
+
+void
+gimple_ranger::range_of_builtin_ubsan_call (irange &r, gcall *call,
+ tree_code code)
+{
+ gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR
+ || code == MULT_EXPR);
+ tree type = gimple_call_return_type (call);
+ range_operator *op = range_op_handler (code, type);
+ gcc_checking_assert (op);
+ widest_irange ir0, ir1;
+ tree arg0 = gimple_call_arg (call, 0);
+ tree arg1 = gimple_call_arg (call, 1);
+ gcc_assert (range_of_expr (ir0, arg0, call));
+ gcc_assert (range_of_expr (ir1, arg1, call));
+
+ bool saved_flag_wrapv = flag_wrapv;
+ /* Pretend the arithmetics is wrapping. If there is
+ any overflow, we'll complain, but will actually do
+ wrapping operation. */
+ flag_wrapv = 1;
+ op->fold_range (r, type, ir0, ir1);
+ flag_wrapv = saved_flag_wrapv;
+
+ /* If for both arguments vrp_valueize returned non-NULL,
+ this should have been already folded and if not, it
+ wasn't folded because of overflow. Avoid removing the
+ UBSAN_CHECK_* calls in that case. */
+ if (r.singleton_p ())
+ r.set_varying (type);
+}
+
+
+bool
+gimple_ranger::range_of_builtin_call (irange &r, gcall *call)
+{
+ combined_fn func = gimple_call_combined_fn (call);
+ if (func == CFN_LAST)
+ return false;
+
+ tree type = gimple_call_return_type (call);
+ tree arg;
+ int mini, maxi, zerov, prec;
+ scalar_int_mode mode;
+
+ switch (func)
+ {
+ case CFN_BUILT_IN_CONSTANT_P:
+ if (cfun->after_inlining)
+ {
+ r.set_zero (type);
+ // r.equiv_clear ();
+ return true;
+ }
+ arg = gimple_call_arg (call, 0);
+ if (range_of_expr (r, arg, call) && r.singleton_p ())
+ {
+ r.set (build_one_cst (type), build_one_cst (type));
+ return true;
+ }
+ break;
+
+ CASE_CFN_FFS:
+ CASE_CFN_POPCOUNT:
+ // __builtin_ffs* and __builtin_popcount* return [0, prec].
+ arg = gimple_call_arg (call, 0);
+ prec = TYPE_PRECISION (TREE_TYPE (arg));
+ mini = 0;
+ maxi = prec;
+ gcc_assert (range_of_expr (r, arg, call));
+ // If arg is non-zero, then ffs or popcount are non-zero.
+ if (!range_includes_zero_p (&r))
+ mini = 1;
+ // If some high bits are known to be zero, decrease the maximum.
+ if (!r.undefined_p ())
+ {
+ wide_int max = r.upper_bound ();
+ maxi = wi::floor_log2 (max) + 1;
+ }
+ r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
+ return true;
+
+ CASE_CFN_PARITY:
+ r.set (build_zero_cst (type), build_one_cst (type));
+ return true;
+
+ CASE_CFN_CLZ:
+ // __builtin_c[lt]z* return [0, prec-1], except when the
+ // argument is 0, but that is undefined behavior.
+ //
+ // On many targets where the CLZ RTL or optab value is defined
+ // for 0, the value is prec, so include that in the range by
+ // default.
+ arg = gimple_call_arg (call, 0);
+ prec = TYPE_PRECISION (TREE_TYPE (arg));
+ mini = 0;
+ maxi = prec;
+ mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
+ if (optab_handler (clz_optab, mode) != CODE_FOR_nothing
+ && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov)
+ // Only handle the single common value.
+ && zerov != prec)
+ // Magic value to give up, unless we can prove arg is non-zero.
+ mini = -2;
+
+ gcc_assert (range_of_expr (r, arg, call));
+ // From clz of minimum we can compute result maximum.
+ if (r.constant_p ())
+ {
+ maxi = prec - 1 - wi::floor_log2 (r.lower_bound ());
+ if (maxi != prec)
+ mini = 0;
+ }
+ else if (!range_includes_zero_p (&r))
+ {
+ maxi = prec - 1;
+ mini = 0;
+ }
+ if (mini == -2)
+ break;
+ // From clz of maximum we can compute result minimum.
+ if (r.constant_p ())
+ {
+ mini = prec - 1 - wi::floor_log2 (r.upper_bound ());
+ if (mini == prec)
+ break;
+ }
+ if (mini == -2)
+ break;
+ r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
+ return true;
+
+ CASE_CFN_CTZ:
+ // __builtin_ctz* return [0, prec-1], except for when the
+ // argument is 0, but that is undefined behavior.
+ //
+ // If there is a ctz optab for this mode and
+ // CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
+ // otherwise just assume 0 won't be seen.
+ arg = gimple_call_arg (call, 0);
+ prec = TYPE_PRECISION (TREE_TYPE (arg));
+ mini = 0;
+ maxi = prec - 1;
+ mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
+ if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing
+ && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov))
+ {
+ // Handle only the two common values.
+ if (zerov == -1)
+ mini = -1;
+ else if (zerov == prec)
+ maxi = prec;
+ else
+ // Magic value to give up, unless we can prove arg is non-zero.
+ mini = -2;
+ }
+ gcc_assert (range_of_expr (r, arg, call));
+ if (!r.undefined_p ())
+ {
+ if (r.lower_bound () != 0)
+ {
+ mini = 0;
+ maxi = prec - 1;
+ }
+ // If some high bits are known to be zero, we can decrease
+ // the maximum.
+ wide_int max = r.upper_bound ();
+ if (max == 0)
+ break;
+ maxi = wi::floor_log2 (max);
+ }
+ if (mini == -2)
+ break;
+ r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
+ return true;
+
+ CASE_CFN_CLRSB:
+ arg = gimple_call_arg (call, 0);
+ prec = TYPE_PRECISION (TREE_TYPE (arg));
+ r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1));
+ return true;
+ case CFN_UBSAN_CHECK_ADD:
+ range_of_builtin_ubsan_call (r, call, PLUS_EXPR);
+ return true;
+ case CFN_UBSAN_CHECK_SUB:
+ range_of_builtin_ubsan_call (r, call, MINUS_EXPR);
+ return true;
+ case CFN_UBSAN_CHECK_MUL:
+ range_of_builtin_ubsan_call (r, call, MULT_EXPR);
+ return true;
+
+ case CFN_GOACC_DIM_SIZE:
+ case CFN_GOACC_DIM_POS:
+ // Optimizing these two internal functions helps the loop
+ // optimizer eliminate outer comparisons. Size is [1,N]
+ // and pos is [0,N-1].
+ {
+ bool is_pos = func == CFN_GOACC_DIM_POS;
+ int axis = oacc_get_ifn_dim_arg (call);
+ int size = oacc_get_fn_dim_size (current_function_decl, axis);
+ if (!size)
+ // If it's dynamic, the backend might know a hardware limitation.
+ size = targetm.goacc.dim_limit (axis);
+
+ r.set (build_int_cst (type, is_pos ? 0 : 1),
+ size
+ ? build_int_cst (type, size - is_pos) : vrp_val_max (type));
+ return true;
+ }
+
+ case CFN_BUILT_IN_STRLEN:
+ if (tree lhs = gimple_call_lhs (call))
+ if (ptrdiff_type_node
+ && (TYPE_PRECISION (ptrdiff_type_node)
+ == TYPE_PRECISION (TREE_TYPE (lhs))))
+ {
+ tree type = TREE_TYPE (lhs);
+ tree max = vrp_val_max (ptrdiff_type_node);
+ wide_int wmax
+ = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
+ tree range_min = build_zero_cst (type);
+ // To account for the terminating NULL, the maximum length
+ // is one less than the maximum array size, which in turn
+ // is one less than PTRDIFF_MAX (or SIZE_MAX where it's
+ // smaller than the former type).
+ // FIXME: Use max_object_size() - 1 here.
+ tree range_max = wide_int_to_tree (type, wmax - 2);
+ r.set (range_min, range_max);
+ return true;
+ }
+ break;
+ default:
+ break;
+ }
+ return false;
+}
+
+
+
+
+// Calculate a range for COND_EXPR statement S and return it in R.
+// If a range cannot be calculated, return false.
+
+bool
+gimple_ranger::range_of_cond_expr (irange &r, gassign *s)
+{
+ widest_irange cond_range, range1, range2;
+ tree cond = gimple_assign_rhs1 (s);
+ tree op1 = gimple_assign_rhs2 (s);
+ tree op2 = gimple_assign_rhs3 (s);
+
+ gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR);
+ gcc_checking_assert (useless_type_conversion_p (TREE_TYPE (op1),
+ TREE_TYPE (op2)));
+ if (!irange::supports_type_p (TREE_TYPE (op1)))
+ return false;
+
+ gcc_assert (range_of_expr (cond_range, cond, s));
+ gcc_assert (range_of_expr (range1, op1, s));
+ gcc_assert (range_of_expr (range2, op2, s));
+
+ // If the condition is known, choose the appropriate expression.
+ if (cond_range.singleton_p ())
+ {
+ // False, pick second operand
+ if (cond_range.zero_p ())
+ r = range2;
+ else
+ r = range1;
+ }
+ else
+ {
+ r = range1;
+ r.union_ (range2);
+ }
+ return true;
+}
+
+
+
+bool
+gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
+{
+ if (!gimple_range_ssa_p (expr))
+ return get_tree_range (r, expr);
+
+ // If there is no statement, just get the global value.
+ if (!stmt)
+ {
+ if (!m_cache.m_globals.get_global_range (r, expr))
+ r = gimple_range_global (expr);
+ return true;
+ }
+
+ basic_block bb = gimple_bb (stmt);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
+
+ // If name is defined in this block, try to get an range from S.
+ if (def_stmt && gimple_bb (def_stmt) == bb)
+ gcc_assert (range_of_stmt (r, def_stmt, expr));
+ else
+ // Otherwise OP comes from outside this block, use range on entry.
+ range_on_entry (r, bb, expr);
+
+ // No range yet, see if there is a dereference in the block.
+ // We don't care if it's between the def and a use within a block
+ // because the entire block must be executed anyway.
+ // FIXME:?? For non-call exceptions we could have a statement throw
+ // which causes an early block exit.
+ // in which case we may need to walk from S back to the def/top of block
+ // to make sure the deref happens between S and there before claiming
+ // there is a deref. Punt for now.
+ if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
+ m_cache.m_non_null.non_null_deref_p (expr, bb))
+ r = range_nonzero (TREE_TYPE (expr));
+
+ return true;
+}
+
+
+// Return the range of NAME on entry to block BB in R.
+
+void
+gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
+{
+ widest_irange entry_range;
+ gcc_checking_assert (gimple_range_ssa_p (name));
+
+ // Start with any known range
+ gcc_assert (range_of_stmt (r, SSA_NAME_DEF_STMT (name), name));
+
+ // Now see if there is any on_entry value which may refine it.
+ if (m_cache.block_range (entry_range, bb, name))
+ r.intersect (entry_range);
+}
+
+
+// Calculate the range for NAME at the end of block BB and return it in R.
+// Return false if no range can be calculated.
+
+void
+gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name)
+{
+ // on-exit from the exit block?
+ gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
+
+ gimple *s = last_stmt (bb);
+ // If there is no statement in the block and this isn't the entry
+ // block, go get the range_on_entry for this block. For the entry
+ // block, a NULL stmt will return the global value for NAME.
+ if (!s && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ range_on_entry (r, bb, name);
+ else
+ gcc_assert (range_of_expr (r, name, s));
+ gcc_checking_assert (r.undefined_p ()
+ || types_compatible_p (r.type(), TREE_TYPE (name)));
+}
+
+// Calculate a range for NAME on edge E and return it in R.
+
+void
+gimple_ranger::range_on_edge (irange &r, edge e, tree name)
+{
+ widest_irange edge_range;
+ gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));
+
+ // PHI arguments can be constants, catch these here.
+ if (!gimple_range_ssa_p (name))
+ {
+ gcc_assert (range_of_expr (r, name));
+ return;
+ }
+
+ range_on_exit (r, e->src, name);
+ gcc_checking_assert (r.undefined_p ()
+ || types_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))
+ r.intersect (edge_range);
+}
+
+// Calculate a range for statement S and return it in R. If NAME is
+// provided it represents the SSA_NAME on the LHS of the statement.
+// It is only required if there is more than one lhs/output. Check
+// the global cache for NAME first to see if the evaluation can be
+// avoided. If a range cannot be calculated, return false.
+
+bool
+gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
+{
+ // If no name, simply call the base routine.
+ if (!name)
+ name = gimple_get_lhs (s);
+
+ if (!name)
+ return calc_stmt (r, s, NULL_TREE);
+
+ gcc_checking_assert (TREE_CODE (name) == SSA_NAME &&
+ irange::supports_type_p (TREE_TYPE (name)));
+
+ // If this STMT has already been processed, return that value.
+ if (m_cache.m_globals.get_global_range (r, name))
+ return true;
+
+ // Avoid infinite recursion by initializing global cache
+ widest_irange tmp = gimple_range_global (name);
+ m_cache.m_globals.set_global_range (name, tmp);
+
+ gcc_assert (calc_stmt (r, s, name));
+
+ if (is_a<gphi *> (s))
+ r.intersect (tmp);
+ m_cache.m_globals.set_global_range (name, r);
+ return true;
+}
+
+
+// This routine will export whatever global ranges are known to GCC
+// SSA_RANGE_NAME_INFO fields.
+
+void
+gimple_ranger::export_global_ranges ()
+{
+ unsigned x;
+ widest_irange r;
+ if (dump_file)
+ {
+ fprintf (dump_file, "Exported global range table\n");
+ fprintf (dump_file, "===========================\n");
+ }
+
+ for ( x = 1; x < num_ssa_names; x++)
+ {
+ tree name = ssa_name (x);
+ if (name && !SSA_NAME_IN_FREE_LIST (name)
+ && gimple_range_ssa_p (name)
+ && m_cache.m_globals.get_global_range (r, name)
+ && !r.varying_p())
+ {
+ // Make sure the new range is a subset of the old range.
+ widest_irange old_range;
+ old_range = gimple_range_global (name);
+ old_range.intersect (r);
+ /* Disable this while we fix tree-ssa/pr61743-2.c. */
+ //gcc_checking_assert (old_range == r);
+
+ // WTF? Can't write non-null pointer ranges?? stupid set_range_info!
+ if (!POINTER_TYPE_P (TREE_TYPE (name)) && !r.undefined_p ())
+ {
+ value_range vr = r;
+ set_range_info (name, vr);
+ if (dump_file)
+ {
+ print_generic_expr (dump_file, name , TDF_SLIM);
+ fprintf (dump_file, " --> ");
+ vr.dump (dump_file);
+ fprintf (dump_file, "\n");
+ fprintf (dump_file, " irange : ");
+ r.dump (dump_file);
+ fprintf (dump_file, "\n");
+ }
+ }
+ }
+ }
+}
+
+
+// Print the known table values to file F.
+
+void
+gimple_ranger::dump (FILE *f)
+{
+ basic_block bb;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ unsigned x;
+ edge_iterator ei;
+ edge e;
+ widest_irange range;
+ fprintf (f, "\n=========== BB %d ============\n", bb->index);
+ m_cache.m_on_entry.dump (f, bb);
+
+ dump_bb (f, bb, 4, TDF_NONE);
+
+ // Now find any globals defined in this block
+ for (x = 1; x < num_ssa_names; x++)
+ {
+ tree name = ssa_name (x);
+ if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) &&
+ gimple_bb (SSA_NAME_DEF_STMT (name)) == bb &&
+ m_cache.m_globals.get_global_range (range, name))
+ {
+ if (!range.varying_p ())
+ {
+ print_generic_expr (f, name, TDF_SLIM);
+ fprintf (f, " : ");
+ range.dump (f);
+ fprintf (f, "\n");
+ }
+
+ }
+ }
+
+ // And now outgoing edges, if they define anything.
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ 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))
+ {
+ gimple *s = SSA_NAME_DEF_STMT (name);
+ // Only print the range if this is the def block, or
+ // the on entry cache for either end of the edge is
+ // set.
+ if ((s && bb == gimple_bb (s)) ||
+ m_cache.block_range (range, bb, name, false) ||
+ m_cache.block_range (range, e->dest, name, false))
+ {
+ range_on_edge (range, e, name);
+ if (!range.varying_p ())
+ {
+ fprintf (f, "%d->%d ", e->src->index,
+ e->dest->index);
+ char c = ' ';
+ if (e->flags & EDGE_TRUE_VALUE)
+ fprintf (f, " (T)%c", c);
+ else if (e->flags & EDGE_FALSE_VALUE)
+ fprintf (f, " (F)%c", c);
+ else
+ fprintf (f, " ");
+ print_generic_expr (f, name, TDF_SLIM);
+ fprintf(f, " : \t");
+ range.dump(f);
+ fprintf (f, "\n");
+ }
+ }
+ }
+ }
+ }
+ }
+
+ m_cache.m_globals.dump (dump_file);
+ fprintf (f, "\n");
+
+ if (dump_flags & TDF_DETAILS)
+ {
+ fprintf (f, "\nDUMPING GORI MAP\n");
+ m_cache.dump (f);
+ fprintf (f, "\n");
+ }
+}
+
+
+// loop_ranger implementation.
+
+loop_ranger::loop_ranger ()
+{
+ m_vr_values = new vr_values;
+}
+
+loop_ranger::~loop_ranger ()
+{
+ delete m_vr_values;
+}
+
+void
+loop_ranger::range_of_ssa_name_with_loop_info (irange &r, tree name,
+ class loop *l, gphi *phi)
+{
+ gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
+ value_range_equiv vr;
+ vr.set_varying (TREE_TYPE (name));
+ m_vr_values->adjust_range_with_scev (&vr, l, phi, name);
+ vr.normalize_symbolics ();
+ r = vr;
+}
+
+// If NAME is either a PHI result or a PHI argument, see if we can
+// determine range information by querying loop info. If so, return
+// TRUE and set the range in R.
+
+bool
+loop_ranger::range_with_loop_info (irange &r, tree name)
+{
+ if (!scev_initialized_p ())
+ return false;
+
+ gimple *def = SSA_NAME_DEF_STMT (name);
+ class loop *l = loop_containing_stmt (def);
+ if (!l)
+ return false;
+
+ basic_block header = l->header;
+ for (gphi_iterator iter = gsi_start_phis (header);
+ !gsi_end_p (iter); gsi_next (&iter))
+ {
+ gphi *phi = iter.phi ();
+ if (PHI_RESULT (phi) == name)
+ {
+ range_of_ssa_name_with_loop_info (r, name, l, phi);
+ return true;
+ }
+ for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
+ if (PHI_ARG_DEF (phi, i) == name)
+ {
+ range_of_ssa_name_with_loop_info (r, name, l, phi);
+ return true;
+ }
+ }
+ return false;
+}
+
+bool
+loop_ranger::range_of_stmt (irange &r, gimple *stmt, tree name)
+{
+ // If there is no global range for a PHI, start the party with
+ // whatever information SCEV may have.
+ if (gphi *phi = dyn_cast<gphi *> (stmt))
+ {
+ tree phi_result = PHI_RESULT (phi);
+ if (!POINTER_TYPE_P (TREE_TYPE (phi_result))
+ && !m_cache.m_globals.get_global_range (r, phi_result)
+ && range_with_loop_info (r, phi_result))
+ {
+ value_range loop_range;
+ get_range_info (phi_result, loop_range);
+ r.intersect (loop_range);
+ if (!r.varying_p ())
+ set_range_info (phi_result, r);
+ }
+ }
+ return super::range_of_stmt (r, stmt, name);
+}
+
+void
+loop_ranger::range_on_edge (irange &r, edge e, tree name)
+{
+ super::range_on_edge (r, e, name);
+
+ if (TREE_CODE (name) == SSA_NAME)
+ {
+ value_range loop_range;
+ if (range_with_loop_info (loop_range, name))
+ r.intersect (loop_range);
+ }
+}
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
new file mode 100644
index 0000000..23c904c
--- /dev/null
+++ b/gcc/gimple-range.h
@@ -0,0 +1,160 @@
+/* Header file for the GIMPLE range interface.
+ Copyright (C) 2019-2020 Free Software Foundation, Inc.
+ Contributed by Andrew MacLeod <amacleod@redhat.com>
+ and Aldy Hernandez <aldyh@redhat.com>.
+
+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
+<http://www.gnu.org/licenses/>. */
+
+#ifndef GCC_GIMPLE_RANGE_STMT_H
+#define GCC_GIMPLE_RANGE_STMT_H
+
+
+#include "range.h"
+#include "range-op.h"
+#include "gimple-range-gori.h"
+#include "gimple-range-cache.h"
+
+// This is the basic range generator interface.
+//
+// This base class provides all the API entry points, but only provides
+// functionality at the statement level. Ie, it can calculate ranges on
+// statements, but does no additonal lookup.
+//
+// All the range_of_* methods will return a range if the types is
+// supported by the range engine. It may be the full range for the
+// type, AKA varying_p or it may be a refined range. If the range
+// type is not supported, then false is returned. Non-statement
+// related methods return whatever the current global value is.
+
+
+class gimple_ranger
+{
+public:
+ virtual bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE);
+ virtual bool range_of_expr (irange &r, tree name, gimple *stmt = NULL);
+ virtual void range_on_edge (irange &r, edge e, tree name);
+ 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 ();
+ void dump (FILE *f);
+protected:
+ bool calc_stmt (irange &r, gimple *s, tree name = NULL_TREE);
+ bool range_of_range_op (irange &r, gimple *s);
+ bool range_of_call (irange &r, gcall *call);
+ bool range_of_cond_expr (irange &r, gassign* cond);
+ ranger_cache m_cache;
+private:
+ bool range_of_phi (irange &r, gphi *phi);
+ bool range_of_non_trivial_assignment (irange &r, gimple *s);
+ bool range_of_builtin_call (irange &r, gcall *call);
+ void range_of_builtin_ubsan_call (irange &r, gcall *call, tree_code code);
+};
+
+
+// A global ranger that uses SCEV/loop (if available) to refine PHI results.
+
+class loop_ranger : public gimple_ranger
+{
+public:
+ loop_ranger ();
+ ~loop_ranger ();
+ virtual void range_on_edge (irange &r, edge e, tree name);
+ virtual bool range_of_stmt (irange &r, gimple *stmt, tree name = NULL_TREE);
+
+private:
+ typedef gimple_ranger super;
+ bool range_with_loop_info (irange &r, tree name);
+ void range_of_ssa_name_with_loop_info (irange &, tree, class loop *,
+ gphi *);
+
+ class vr_values *m_vr_values;
+};
+
+// Calculate a basic range for a tree expression.
+extern bool get_tree_range (irange &r, tree expr);
+
+// If BB ends with a range generating stmt, return its GSI.
+extern gimple_stmt_iterator gsi_outgoing_range_stmt (basic_block bb);
+// If BB ends with a range generating stmt, return that stmt.
+extern gimple *gimple_outgoing_range_stmt_p (basic_block bb);
+// If edge E has a constant range, return it and the range generating
+// statement. for conditonals its TRUE/FALSE, for switches its the
+// possible cases.
+extern gimple *gimple_outgoing_edge_range_p (irange &r, edge e);
+
+// These routines provide a GIMPLE interface to the range-ops code.
+extern tree gimple_range_operand1 (const gimple *s);
+extern tree gimple_range_operand2 (const gimple *s);
+extern tree gimple_range_base_of_assignment (const gimple *s);
+extern bool gimple_range_fold (irange &res, const gimple *s,
+ const irange &r1);
+extern bool gimple_range_fold (irange &res, const gimple *s,
+ const irange &r1,
+ const irange &r2);
+extern bool gimple_range_calc_op1 (irange &r, const gimple *s,
+ const irange &lhs_range);
+extern bool gimple_range_calc_op1 (irange &r, const gimple *s,
+ const irange &lhs_range,
+ const irange &op2_range);
+extern bool gimple_range_calc_op2 (irange &r, const gimple *s,
+ const irange &lhs_range,
+ const irange &op1_range);
+
+
+// Return the range_operator pointer for this statement. This routine
+// can also be used to gate whether a routine is range-ops enabled.
+
+static inline range_operator *
+gimple_range_handler (const gimple *s)
+{
+ if ((gimple_code (s) == GIMPLE_ASSIGN) || (gimple_code (s) == GIMPLE_COND))
+ return range_op_handler (gimple_expr_code (s), gimple_expr_type (s));
+ return NULL;
+}
+
+// Return EXP if it is an SSA_NAME with a type supported by gimple ranges.
+
+static inline tree
+gimple_range_ssa_p (tree exp)
+{
+ if (exp && TREE_CODE (exp) == SSA_NAME &&
+ !SSA_NAME_IS_VIRTUAL_OPERAND (exp) &&
+ irange::supports_type_p (TREE_TYPE (exp)))
+ return exp;
+ return NULL_TREE;
+}
+
+// Return the legacy GCC global range for NAME if it has one, otherwise
+// return VARYING.
+
+static inline value_range
+gimple_range_global (tree name)
+{
+ gcc_checking_assert (gimple_range_ssa_p (name));
+ tree type = TREE_TYPE (name);
+ if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
+ {
+ // Return a range from an SSA_NAME's available range.
+ wide_int min, max;
+ enum value_range_kind kind = get_range_info (name, &min, &max);
+ return value_range (type, min, max, kind);
+ }
+ // Otherwise return range for the type.
+ return value_range (type);
+}
+
+#endif // GCC_GIMPLE_RANGE_STMT_H
diff --git a/gcc/gimple-ranger.cc b/gcc/gimple-ranger.cc
deleted file mode 100644
index dc51ff1..0000000
--- a/gcc/gimple-ranger.cc
+++ /dev/null
@@ -1,1001 +0,0 @@
-/* Main entry point for the gimple ranger.
- Copyright (C) 2017-2020 Free Software Foundation, Inc.
- Contributed by Andrew MacLeod <amacleod@redhat.com>
- and Aldy Hernandez <aldyh@redhat.com>.
-
-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
-<http://www.gnu.org/licenses/>. */
-
-#include "config.h"
-#include "system.h"
-#include "coretypes.h"
-#include "backend.h"
-#include "insn-codes.h"
-#include "rtl.h"
-#include "tree.h"
-#include "gimple.h"
-#include "ssa.h"
-#include "gimple-pretty-print.h"
-#include "gimple-iterator.h"
-#include "tree-cfg.h"
-#include "gimple-ranger.h"
-#include "cfgloop.h"
-#include "tree-ssa-loop.h"
-#include "tree-scalar-evolution.h"
-#include "dbgcnt.h"
-#include "alloc-pool.h"
-#include "vr-values.h"
-
-// Calculate a range for COND_EXPR statement S and return it in R.
-// If a range cannot be calculated, return false.
-
-bool
-gimple_ranger::range_of_cond_expr (irange &r, gassign *s)
-{
- widest_irange cond_range, range1, range2;
- tree cond = gimple_assign_rhs1 (s);
- tree op1 = gimple_assign_rhs2 (s);
- tree op2 = gimple_assign_rhs3 (s);
-
- gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR);
- gcc_checking_assert (useless_type_conversion_p (TREE_TYPE (op1),
- TREE_TYPE (op2)));
- if (!irange::supports_type_p (TREE_TYPE (op1)))
- return false;
-
- gcc_assert (range_of_expr (cond_range, cond, s));
- gcc_assert (range_of_expr (range1, op1, s));
- gcc_assert (range_of_expr (range2, op2, s));
-
- // If the condition is known, choose the appropriate expression.
- if (cond_range.singleton_p ())
- {
- // False, pick second operand
- if (cond_range.zero_p ())
- r = range2;
- else
- r = range1;
- }
- else
- {
- r = range1;
- r.union_ (range2);
- }
- return true;
-}
-
-
-// ------------------------------------------------------------------------
-
-
-// Construct a global_ranger object.
-
-global_ranger::global_ranger ()
-{
- m_workback.create (0);
- m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
- m_update_list.create (0);
- m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun));
- m_update_list.truncate (0);
-}
-
-// Destruct a global_ranger object.
-
-global_ranger::~global_ranger ()
-{
- m_workback.release ();
- m_update_list.release ();
-}
-
-// Return true if NAME has a non-null dereference in block BB.
-
-bool
-global_ranger::non_null_deref_p (tree name, basic_block bb)
-{
- return m_non_null.non_null_deref_p (name, bb);
-}
-
-void
-global_ranger::dump_block (FILE *f, basic_block bb)
-{
- m_on_entry.dump (f, bb);
-}
-
-
-// Return the range of NAME on entry to block BB in R.
-
-void
-global_ranger::range_on_entry (irange &r, basic_block bb, tree name)
-{
- widest_irange entry_range;
- gcc_checking_assert (gimple_range_ssa_p (name));
-
- // Start with any known range
- gcc_assert (range_of_stmt (r, SSA_NAME_DEF_STMT (name), name));
-
- // Now see if there is any on_entry value which may refine it.
- if (block_range (entry_range, bb, name))
- r.intersect (entry_range);
-}
-
-
-// Calculate the range for NAME at the end of block BB and return it in R.
-// Return false if no range can be calculated.
-
-void
-global_ranger::range_on_exit (irange &r, basic_block bb, tree name)
-{
- // on-exit from the exit block?
- gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
-
- gimple *s = last_stmt (bb);
- // If there is no statement in the block and this isn't the entry
- // block, go get the range_on_entry for this block. For the entry
- // block, a NULL stmt will return the global value for NAME.
- if (!s && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
- range_on_entry (r, bb, name);
- else
- gcc_assert (range_of_expr (r, name, s));
- gcc_checking_assert (r.undefined_p ()
- || types_compatible_p (r.type(), TREE_TYPE (name)));
-}
-
-// Calculate a range for NAME on edge E and return it in R.
-
-void
-global_ranger::range_on_edge (irange &r, edge e, tree name)
-{
- super::range_on_edge (r, e, name);
-
- if (TREE_CODE (name) == SSA_NAME)
- {
- widest_irange range_for_name;
- range_of_ssa_name (range_for_name, name);
- r.intersect (range_for_name);
- }
-}
-
-// Calculate a range for statement S and return it in R. If NAME is
-// provided it represents the SSA_NAME on the LHS of the statement.
-// It is only required if there is more than one lhs/output. Check
-// the global cache for NAME first to see if the evaluation can be
-// avoided. If a range cannot be calculated, return false.
-
-bool
-global_ranger::range_of_stmt (irange &r, gimple *s, tree name)
-{
- // If no name, simply call the base routine.
- if (!name)
- {
- // first check to see if the stmt has a name.
- name = gimple_get_lhs (s);
- if (!name)
- return gimple_ranger::range_of_stmt (r, s, name);
- }
-
- gcc_checking_assert (TREE_CODE (name) == SSA_NAME &&
- irange::supports_type_p (TREE_TYPE (name)));
-
- // If this STMT has already been processed, return that value.
- if (m_globals.get_global_range (r, name))
- return true;
-
- // Avoid infinite recursion by initializing global cache
- widest_irange tmp = gimple_range_global (name);
- m_globals.set_global_range (name, tmp);
-
- gcc_assert (gimple_ranger::range_of_stmt (r, s, name));
-
- if (is_a<gphi *> (s))
- r.intersect (tmp);
- m_globals.set_global_range (name, r);
- return true;
-}
-
-
-// Determine a range for OP on stmt S, returning the result in R. If
-// OP is not defined in BB, find the range on entry to this block.
-
-void
-global_ranger::range_of_ssa_name (irange &r, tree name, gimple *s)
-{
- // If there is no statement, just get the global value.
- if (!s)
- {
- gimple_ranger::range_of_ssa_name (r, name);
- return;
- }
-
- basic_block bb = gimple_bb (s);
- gimple *def_stmt = SSA_NAME_DEF_STMT (name);
-
- // If name is defined in this block, try to get an range from S.
- if (def_stmt && gimple_bb (def_stmt) == bb)
- gcc_assert (range_of_stmt (r, def_stmt, name));
- else
- // Otherwise OP comes from outside this block, use range on entry.
- range_on_entry (r, bb, name);
-
- // No range yet, see if there is a dereference in the block.
- // We don't care if it's between the def and a use within a block
- // because the entire block must be executed anyway.
- // FIXME:?? For non-call exceptions we could have a statement throw
- // which causes an early block exit.
- // in which case we may need to walk from S back to the def/top of block
- // to make sure the deref happens between S and there before claiming
- // there is a deref. Punt for now.
- if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
- non_null_deref_p (name, bb))
- r = range_nonzero (TREE_TYPE (name));
-}
-
-
-
-bool
-global_ranger::range_from_import (irange &r, tree name, irange &import_range)
-{
- widest_irange r1, r2;
- bool res = true;
- tree import = m_gori_map.terminal_name (name);
-
- // This probably means the IL has changed underneath... just return
- // false until we have a more comprehensive solution.
- if (!import || (import_range.undefined_p () ||
- useless_type_conversion_p (TREE_TYPE (import),
- import_range.type ())))
- return false;
-
- // Only handling range_ops until we find a cond-expr that matters.
- // We process this specially so we can handle self-referencing chains. ie:
- // b_3 = b_1 + 10
- // b_4 = b_3 + b_1 // b_4 = b_1 * 2 + 10 really
- // if (b_4 < 20)
- //
- // import b_1 = [0,0]
- // we want to make sure b_4 evaluates both b_3 and b_1 with this import value
- // Due to the nature of def chains, there can only be one import in the chain.
- // its possible 2 different chains occur in one stmt, ie:
- // if (b_4 < d_6), but there is no DEF for this stmt, so it can't happen.
- // f_5 = b_4 + d_6 would have no import since there are 2 symbolics.
-
- gimple *s = SSA_NAME_DEF_STMT (name);
- if (!s || !gimple_range_handler (s))
- return false;
-
- tree op1 = gimple_range_operand1 (s);
- tree op2 = gimple_range_operand2 (s);
-
- // Evaluate op1
- if (gimple_range_ssa_p (op1))
- {
- if (op1 == import)
- r1 = import_range;
- else
- res = range_from_import (r1, op1, import_range);
- }
- else
- gcc_assert (range_of_expr (r1, op1));
-
- if (!res)
- return false;
- if (!op2)
- return gimple_range_fold (s, r, r1);
-
- // Now evaluate op2.
- if (gimple_range_ssa_p (op2))
- {
- if (op2 == import)
- r2 = import_range;
- else
- res = range_from_import (r2, op2, import_range);
- }
- else
- gcc_assert (range_of_expr (r2, op2));
-
- if (res)
- return gimple_range_fold (s, r, r1, r2);
-
- return false;
-}
-
-
-
-// This routine will export whatever global ranges are known to GCC
-// SSA_RANGE_NAME_INFO fields.
-
-void
-global_ranger::export_global_ranges ()
-{
- unsigned x;
- widest_irange r;
- if (dump_file)
- {
- fprintf (dump_file, "Exported global range table\n");
- fprintf (dump_file, "===========================\n");
- }
-
- for ( x = 1; x < num_ssa_names; x++)
- {
- tree name = ssa_name (x);
- if (name && !SSA_NAME_IN_FREE_LIST (name)
- && gimple_range_ssa_p (name)
- && m_globals.get_global_range (r, name)
- && !r.varying_p())
- {
- // Make sure the new range is a subset of the old range.
- widest_irange old_range;
- old_range = gimple_range_global (name);
- old_range.intersect (r);
- /* Disable this while we fix tree-ssa/pr61743-2.c. */
- //gcc_checking_assert (old_range == r);
-
- // WTF? Can't write non-null pointer ranges?? stupid set_range_info!
- if (!POINTER_TYPE_P (TREE_TYPE (name)) && !r.undefined_p ())
- {
- if (!dbg_cnt (ranger_export_count))
- return;
-
- value_range vr = r;
- set_range_info (name, vr);
- if (dump_file)
- {
- print_generic_expr (dump_file, name , TDF_SLIM);
- fprintf (dump_file, " --> ");
- vr.dump (dump_file);
- fprintf (dump_file, "\n");
- fprintf (dump_file, " irange : ");
- r.dump (dump_file);
- fprintf (dump_file, "\n");
- }
- }
- }
- }
-}
-
-
-// Print the known table values to file F.
-
-void
-global_ranger::dump (FILE *f)
-{
- basic_block bb;
-
- FOR_EACH_BB_FN (bb, cfun)
- {
- unsigned x;
- edge_iterator ei;
- edge e;
- widest_irange range;
- fprintf (f, "\n=========== BB %d ============\n", bb->index);
- dump_block (f, bb);
-
- dump_bb (f, bb, 4, TDF_NONE);
-
- // Now find any globals defined in this block
- for (x = 1; x < num_ssa_names; x++)
- {
- tree name = ssa_name (x);
- if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) &&
- gimple_bb (SSA_NAME_DEF_STMT (name)) == bb &&
- m_globals.get_global_range (range, name))
- {
- if (!range.varying_p ())
- {
- print_generic_expr (f, name, TDF_SLIM);
- fprintf (f, " : ");
- range.dump (f);
- fprintf (f, "\n");
- }
-
- }
- }
-
- // And now outgoing edges, if they define anything.
- FOR_EACH_EDGE (e, ei, bb->succs)
- {
- for (x = 1; x < num_ssa_names; x++)
- {
- tree name = gimple_range_ssa_p (ssa_name (x));
- if (name && outgoing_edge_range_p (range, e, name))
- {
- gimple *s = SSA_NAME_DEF_STMT (name);
- // Only print the range if this is the def block, or
- // the on entry cache for either end of the edge is
- // set.
- if ((s && bb == gimple_bb (s)) ||
- block_range (range, bb, name, false) ||
- block_range (range, e->dest, name, false))
- {
- range_on_edge (range, e, name);
- if (!range.varying_p ())
- {
- fprintf (f, "%d->%d ", e->src->index,
- e->dest->index);
- char c = (m_gori_map.is_export_p (name, bb) ? ' ' : '*');
- if (e->flags & EDGE_TRUE_VALUE)
- fprintf (f, " (T)%c", c);
- else if (e->flags & EDGE_FALSE_VALUE)
- fprintf (f, " (F)%c", c);
- else
- fprintf (f, " ");
- print_generic_expr (f, name, TDF_SLIM);
- fprintf(f, " : \t");
- range.dump(f);
- fprintf (f, "\n");
- }
- }
- }
- }
- }
- }
-
- m_globals.dump (dump_file);
- fprintf (f, "\n");
-
- if (dump_flags & TDF_DETAILS)
- {
- fprintf (f, "\nDUMPING GORI MAP\n");
- m_gori_map.dump (f);
- fprintf (f, "\n");
- }
-}
-
-// Calculate all ranges by visiting every block and asking for the range of
-// each ssa_name on each statement, and then dump those ranges to OUTPUT.
-
-void
-global_ranger::calculate_and_dump (FILE *output)
-{
- basic_block bb;
- widest_irange r;
-
- // Walk every statement asking for a range.
- FOR_EACH_BB_FN (bb, cfun)
- {
- for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
- gsi_next (&gpi))
- {
- gphi *phi = gpi.phi ();
- tree phi_def = gimple_phi_result (phi);
- if (gimple_range_ssa_p (phi_def))
- gcc_assert (range_of_stmt (r, phi));
- }
-
- for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
- gsi_next (&gsi))
- {
- gimple *stmt = gsi_stmt (gsi);
- ssa_op_iter iter;
- use_operand_p use_p;
-
- // Calculate a range for the LHS if there is one.
- if (gimple_range_ssa_p (gimple_get_lhs (stmt)))
- range_of_stmt (r, stmt);
- // and make sure to query every operand.
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
- {
- tree use = gimple_range_ssa_p (USE_FROM_PTR (use_p));
- if (use)
- range_of_expr (r, use, stmt);
- }
- }
- }
- // The dump it.
- dump (output);
- fprintf (output, "\n");
-}
-
-// 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.
-
-bool
-global_ranger::block_range (irange &r, basic_block bb, tree name, bool calc)
-{
- gcc_checking_assert (gimple_range_ssa_p (name));
-
- if (calc)
- {
- gimple *def_stmt = SSA_NAME_DEF_STMT (name);
- basic_block def_bb = NULL;
- if (def_stmt)
- def_bb = gimple_bb (def_stmt);;
- if (!def_bb)
- {
- // If we get to the entry block, this better be a default def
- // or range_on_entry was called for a block not dominated by
- // the def. This would be a bug.
- gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name));
- def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
- }
-
- // There is no range on entry for the defintion block.
- if (def_bb == bb)
- return false;
-
- // Otherwise, go figure out what is known in predecessor blocks.
- fill_block_cache (name, bb, def_bb);
- gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
- }
- return m_on_entry.get_bb_range (r, name, bb);
-}
-
-
-// Return the static range for NAME on edge E in R. If there is no
-// range-on-entry cache for E->src, then return false. If this is the
-// def block, then see if the DEF can be evaluated with them import
-// name, otherwise use varying as the range. If there is any outgoing
-// range information on edge E, incorporate it into the results.
-
-bool
-global_ranger::edge_range (irange &r, edge e, tree name)
-{
- basic_block src = e->src;
- widest_irange er, tmp;
- gimple *s = SSA_NAME_DEF_STMT (name);
- basic_block def_bb = ((s && gimple_bb (s)) ? gimple_bb (s) :
- ENTRY_BLOCK_PTR_FOR_FN (cfun));
-
- if (src == def_bb)
- {
- // Check to see if the import has a cache_entry, and if it does
- // use that in an evaluation to get a static starting value.
- // The import should have a range if the global range is
- // requested before any other lookups.
- tree term = (has_edge_range_p (e, name) ? m_gori_map.terminal_name (name)
- : NULL_TREE);
- if (!term || !(m_on_entry.get_bb_range (tmp, term, src) &&
- range_from_import (r, name, tmp)))
- {
- // Try to pick up any known value first.
- if (!m_globals.get_global_range (r, name))
- r = gimple_range_global (name);
- }
- }
- else if (!m_on_entry.get_bb_range (r, name, src))
- return false;
-
- // Check if pointers have any non-null dereferences. Non-call
- // exceptions mean we could throw in the middle of he block, so just
- // punt for now on those.
- if (r.varying_p () && m_non_null.non_null_deref_p (name, src) &&
- !cfun->can_throw_non_call_exceptions)
- r = range_nonzero (TREE_TYPE (name));
-
- if (outgoing_edge_range_p (er, e, name, &r))
- r = er;
- return true;
-}
-
-void
-global_ranger::add_to_update (basic_block bb)
-{
- if (!m_update_list.contains (bb))
- m_update_list.quick_push (bb);
-}
-
-#define DEBUG_CACHE (0 && dump_file)
-
-// If there is anything in the iterative update_list, continue
-// processing NAME until the list of blocks is empty.
-
-void
-global_ranger::iterative_cache_update (tree name)
-{
- basic_block bb;
- edge_iterator ei;
- edge e;
- widest_irange new_range;
- widest_irange current_range;
- widest_irange e_range;
-
- // Process each block by seeing if it's calculated range on entry is
- // the same as it's cached value. IF there is a difference, update
- // the cache to reflect the new value, and check to see if any
- // successors have cache entries which may need to be checked for
- // updates.
-
- while (m_update_list.length () > 0)
- {
- bb = m_update_list.pop ();
-if (DEBUG_CACHE) fprintf (dump_file, "FWD visiting block %d\n", bb->index);
-
- gcc_assert (m_on_entry.get_bb_range (current_range, name, bb));
- // Calculate the "new" range on entry by unioning the pred edges..
- new_range.set_undefined ();
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- gcc_assert (edge_range (e_range, e, name));
- new_range.union_ (e_range);
- if (new_range.varying_p ())
- break;
- }
- // If the range on entry has changed, update it.
- if (new_range != current_range)
- {
-if (DEBUG_CACHE) { fprintf (dump_file, "updating range from/to "); current_range.dump (dump_file); new_range.dump (dump_file); }
- m_on_entry.set_bb_range (name, bb, new_range);
- // Mark each successor that has a range to re-check it's range
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (m_on_entry.bb_range_p (name, e->dest))
- add_to_update (e->dest);
- }
- }
-if (DEBUG_CACHE) fprintf (dump_file, "DONE visiting blocks \n\n");
-}
-
-// Make sure that the range-on-entry cache for NAME is set for block BB.
-// Work back thourgh the CFG to DEF_BB ensuring the range is calculated
-// on the block/edges leading back to that point.
-
-void
-global_ranger::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
-{
- edge_iterator ei;
- edge e;
- widest_irange block_result;
- widest_irange undefined;
-
- // At this point we shouldnt be looking at the def, entry or exit block.
- gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
- bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
-
- // If the block cache is set, then we've already visited this block.
- if (m_on_entry.bb_range_p (name, bb))
- return;
-
- // Visit each block back to the DEF. Initialize each one to UNDEFINED.
- // m_visited at the end will contain all the blocks that we needed to set
- // the range_on_entry cache for.
- m_workback.truncate (0);
- m_workback.quick_push (bb);
- undefined.set_undefined ();
- m_on_entry.set_bb_range (name, bb, undefined);
- gcc_checking_assert (m_update_list.length () == 0);
-
-if (DEBUG_CACHE) { fprintf (dump_file, "\n"); print_generic_expr (dump_file, name, TDF_SLIM); fprintf (dump_file, " : "); }
-
- while (m_workback.length () > 0)
- {
- basic_block node = m_workback.pop ();
-if (DEBUG_CACHE) fprintf (dump_file, "BACK visiting block %d\n", node->index);
-
- FOR_EACH_EDGE (e, ei, node->preds)
- {
- basic_block pred = e->src;
- widest_irange r;
- // If the pred block is the def block add this BB to update list.
- if (pred == def_bb)
- {
- add_to_update (node);
- continue;
- }
-
- // If the pred is entry but NOT def, then it is used before
- // defined, it'll get set to []. and no need to update it.
- if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
- continue;
-
- // Regardless of whther we have visited pred or not, if the pred has
- // a non-null reference, revisit this block.
- if (m_non_null.non_null_deref_p (name, pred))
- add_to_update (node);
-
- // If the pred block already has a range, or if it can contribute
- // something new. Ie, the edge generates a range of some sort.
- if (m_on_entry.get_bb_range (r, name, pred))
- {
- if (!r.undefined_p () || has_edge_range_p (e, name))
- add_to_update (node);
- continue;
- }
-
- // 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));
- m_on_entry.set_bb_range (name, pred, undefined);
- m_workback.quick_push (pred);
- }
- }
-
- iterative_cache_update (name);
-}
-
-
-// loop_ranger implementation.
-
-loop_ranger::loop_ranger ()
-{
- m_vr_values = new vr_values;
-}
-
-loop_ranger::~loop_ranger ()
-{
- delete m_vr_values;
-}
-
-void
-loop_ranger::range_of_ssa_name_with_loop_info (irange &r, tree name,
- class loop *l, gphi *phi)
-{
- gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
- value_range_equiv vr;
- vr.set_varying (TREE_TYPE (name));
- m_vr_values->adjust_range_with_scev (&vr, l, phi, name);
- vr.normalize_symbolics ();
- r = vr;
-}
-
-// If NAME is either a PHI result or a PHI argument, see if we can
-// determine range information by querying loop info. If so, return
-// TRUE and set the range in R.
-
-bool
-loop_ranger::range_with_loop_info (irange &r, tree name)
-{
- if (!scev_initialized_p ())
- return false;
-
- gimple *def = SSA_NAME_DEF_STMT (name);
- class loop *l = loop_containing_stmt (def);
- if (!l)
- return false;
-
- basic_block header = l->header;
- for (gphi_iterator iter = gsi_start_phis (header);
- !gsi_end_p (iter); gsi_next (&iter))
- {
- gphi *phi = iter.phi ();
- if (PHI_RESULT (phi) == name)
- {
- range_of_ssa_name_with_loop_info (r, name, l, phi);
- return true;
- }
- for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
- if (PHI_ARG_DEF (phi, i) == name)
- {
- range_of_ssa_name_with_loop_info (r, name, l, phi);
- return true;
- }
- }
- return false;
-}
-
-bool
-loop_ranger::range_of_stmt (irange &r, gimple *stmt, tree name)
-{
- // If there is no global range for a PHI, start the party with
- // whatever information SCEV may have.
- if (gphi *phi = dyn_cast<gphi *> (stmt))
- {
- tree phi_result = PHI_RESULT (phi);
- if (!POINTER_TYPE_P (TREE_TYPE (phi_result))
- && !m_globals.get_global_range (r, phi_result)
- && range_with_loop_info (r, phi_result))
- {
- value_range loop_range;
- get_range_info (phi_result, loop_range);
- r.intersect (loop_range);
- if (!r.varying_p ())
- set_range_info (phi_result, r);
- }
- }
- return super::range_of_stmt (r, stmt, name);
-}
-
-void
-loop_ranger::range_on_edge (irange &r, edge e, tree name)
-{
- super::range_on_edge (r, e, name);
-
- if (TREE_CODE (name) == SSA_NAME)
- {
- value_range loop_range;
- if (range_with_loop_info (loop_range, name))
- r.intersect (loop_range);
- }
-}
-
-
-// trace_ranger implementation.
-
-trace_ranger::trace_ranger ()
-{
- indent = 0;
- trace_count = 0;
-}
-
-// If dumping, return true and print the prefix for the next output line.
-
-inline bool
-trace_ranger::dumping (unsigned counter, bool trailing)
-{
- if (dump_file && (dump_flags & TDF_GORI))
- {
- // Print counter index as well as INDENT spaces.
- if (!trailing)
- fprintf (dump_file, " %-7u ", counter);
- else
- fprintf (dump_file, " ");
- unsigned x;
- for (x = 0; x< indent; x++)
- fputc (' ', dump_file);
- return true;
- }
- return false;
-}
-
-// After calling a routine, if dumping, print the CALLER, NAME, and RESULT,
-// returning RESULT.
-
-bool
-trace_ranger::trailer (unsigned counter, const char *caller, bool result,
- tree name, const irange &r)
-{
- if (dumping (counter, true))
- {
- indent -= bump;
- fputs(result ? "TRUE : " : "FALSE : ", dump_file);
- fprintf (dump_file, "(%u) ", counter);
- fputs (caller, dump_file);
- fputs (" (",dump_file);
- if (name)
- print_generic_expr (dump_file, name, TDF_SLIM);
- fputs (") ",dump_file);
- if (result)
- {
- r.dump (dump_file);
- fputc('\n', dump_file);
- }
- else
- fputc('\n', dump_file);
- // Marks the end of a request.
- if (indent == 0)
- fputc('\n', dump_file);
- }
- return result;
-}
-
-// Tracing version of range_of_expr. Call it with printing wrappers.
-
-void
-trace_ranger::range_of_ssa_name (irange &r, tree name, gimple *s)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "range_of_ssa_name (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") at stmt ");
- if (s)
- print_gimple_stmt (dump_file, s , 0, TDF_SLIM);
- else
- fprintf (dump_file, " NULL\n");
- indent += bump;
- }
-
- super::range_of_ssa_name (r, name, s);
-
- trailer (idx, "range_of_ssa_name", true, name, r);
-}
-
-// Tracing version of range_on_edge. Call it with printing wrappers.
-
-void
-trace_ranger::range_on_edge (irange &r, edge e, tree name)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "range_on_edge (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
- indent += bump;
- }
-
- super::range_on_edge (r, e, name);
-
- trailer (idx, "range_on_edge", true, name, r);
-}
-
-// Tracing version of range_on_entry. Call it with printing wrappers.
-
-void
-trace_ranger::range_on_entry (irange &r, basic_block bb, tree name)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "range_on_entry (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") to BB %d\n", bb->index);
- indent += bump;
- }
-
- super::range_on_entry (r, bb, name);
-
- trailer (idx, "range_on_entry", true, name, r);
-}
-
-// Tracing version of range_on_exit. Call it with printing wrappers.
-
-void
-trace_ranger::range_on_exit (irange &r, basic_block bb, tree name)
-{
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "range_on_exit (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") from BB %d\n", bb->index);
- indent += bump;
- }
-
- super::range_on_exit (r, bb, name);
-
- trailer (idx, "range_on_exit", true, name, r);
-}
-
-// Tracing version of range_of_stmt. Call it with printing wrappers.
-
-bool
-trace_ranger::range_of_stmt (irange &r, gimple *s, tree name)
-{
- bool res;
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "range_of_stmt (");
- if (name)
- print_generic_expr (dump_file, name, TDF_SLIM);
- fputs (") at stmt ", dump_file);
- print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
- indent += bump;
- }
-
- res = super::range_of_stmt (r, s, name);
-
- return trailer (idx, "range_of_stmt", res, name, r);
-}
-
-// Tracing version of outgoing_edge_range_p. Call it with printing wrappers.
-
-bool
-trace_ranger::outgoing_edge_range_p (irange &r, edge e, tree name,
- const irange *name_range)
-{
- bool res;
- unsigned idx = ++trace_count;
- if (dumping (idx))
- {
- fprintf (dump_file, "outgoing_edge_range_p (");
- print_generic_expr (dump_file, name, TDF_SLIM);
- fprintf (dump_file, ") on edge %d->%d, with range ", e->src->index,
- e->dest->index);
- if (name_range)
- {
- name_range->dump (dump_file);
- fprintf (dump_file, "\n");
- }
- else
- fputs ("NULL\n", dump_file);
- indent += bump;
- }
-
- res = super::outgoing_edge_range_p (r, e, name, name_range);
-
- return trailer (idx, "outgoing_edge_range_p", res, name, r);
-}
diff --git a/gcc/gimple-ranger.h b/gcc/gimple-ranger.h
deleted file mode 100644
index e192356..0000000
--- a/gcc/gimple-ranger.h
+++ /dev/null
@@ -1,146 +0,0 @@
-/* Header file for the gimple ranger.
- Copyright (C) 2017-2020 Free Software Foundation, Inc.
- Contributed by Andrew MacLeod <amacleod@redhat.com>
- and Aldy Hernandez <aldyh@redhat.com>.
-
-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
-<http://www.gnu.org/licenses/>. */
-
-#ifndef GCC_GIMPLE_RANGER_H
-#define GCC_GIMPLE_RANGER_H
-
-#include "gimple-range-stmt.h"
-#include "gimple-range-gori.h"
-#include "gimple-range-cfg.h"
-#include "gimple-range-cache.h"
-
-
-// This is the basic range generator interface.
-//
-// This base class provides all the API entry points, but only provides
-// functionality at the statement level. Ie, it can calculate ranges on
-// statements, but does no additonal lookup.
-//
-// All the range_of_* methods will return a range if the types is
-// supported by the range engine. It may be the full range for the
-// type, AKA varying_p or it may be a refined range. If the range
-// type is not supported, then false is returned. Non-statement
-// related methods return whatever the current global value is.
-
-class global_ranger : public gimple_ranger
-{
-public:
- global_ranger ();
- ~global_ranger ();
- virtual void range_on_entry (irange &r, basic_block bb, tree name);
- virtual void range_on_exit (irange &r, basic_block bb, tree name);
- virtual bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE);
- virtual void range_on_edge (irange &r, edge e, tree name);
-
- void export_global_ranges ();
-
- void dump (FILE *f);
- void calculate_and_dump (FILE *f);
-protected:
- virtual void range_of_ssa_name (irange &r, tree name, gimple *s = NULL);
- bool range_from_import (irange &r, tree name, irange &import_range);
- ssa_global_cache m_globals;
-private:
- typedef gimple_ranger super;
- bool non_null_deref_p (tree name, basic_block bb);
- bool block_range (irange &r, basic_block bb, tree name, bool calc = true);
- void dump_block (FILE *f, basic_block bb);
-
- void add_to_update (basic_block bb);
- bool edge_range (irange &r, edge e, tree name);
- void fill_block_cache (tree name, basic_block bb, basic_block def_bb);
- void iterative_cache_update (tree name);
-
- block_range_cache m_on_entry;
- non_null_ref m_non_null;
- vec<basic_block> m_workback;
- vec<basic_block> m_update_list;
-};
-
-
-// A global ranger that uses SCEV/loop (if available) to refine PHI results.
-
-class loop_ranger : public global_ranger
-{
-public:
- loop_ranger ();
- ~loop_ranger ();
- virtual void range_on_edge (irange &r, edge e, tree name);
- virtual bool range_of_stmt (irange &r, gimple *stmt, tree name);
-
-private:
- typedef global_ranger super;
- bool range_with_loop_info (irange &r, tree name);
- void range_of_ssa_name_with_loop_info (irange &, tree, class loop *,
- gphi *);
-
- class vr_values *m_vr_values;
-};
-
-class trace_ranger : public loop_ranger
-{
-public:
- trace_ranger();
-
- virtual bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE);
- virtual void range_on_edge (irange &r, edge e, tree name);
- virtual void range_on_entry (irange &r, basic_block bb, tree name);
- virtual void range_on_exit (irange &r, basic_block bb, tree name);
-
- // Calculate a range on edge E only if it is defined by E.
- virtual bool outgoing_edge_range_p (irange &r, edge e, tree name,
- const irange *name_range = NULL);
-protected:
- virtual void range_of_ssa_name (irange &r, tree name, gimple *s = NULL);
-private:
- typedef loop_ranger super;
- static const unsigned bump = 2;
- unsigned indent;
- unsigned trace_count; // Current trace index count.
-
- bool dumping (unsigned counter, bool trailing = false);
- bool trailer (unsigned counter, const char *caller, bool result, tree name,
- const irange &r);
-};
-
-
-
-// Like global_ranger::range_of_expr (), but make an on-the-fly
-// ranger. If SSA, as seen from STMT, has a known range, set it in R
-// and return TRUE.
-//
-// NOTE: There is overhead involved with this function, so it should
-// only be used for lightweight queries. It is mostly meant for range
-// queries that don't need caching in subsequent calls.
-
-static inline bool
-on_demand_get_range_on_stmt (irange &r, tree ssa, gimple *stmt)
-{
- if (!cfun->cfg)
- return false;
- loop_ranger ranger;
- bool ret;
- ret = ranger.range_of_expr (r, ssa, stmt);
- if (ret && r.varying_p ())
- return false;
- return ret;
-}
-#endif // GCC_GIMPLE_RANGER_H
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index d86d30f..d5b4e0a 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -50,7 +50,6 @@
#include "vr-values.h"
#include "cfghooks.h"
#include "range-op.h"
-#include "gimple-range-stmt.h"
#include "misc.h"
/* Set value range VR to a non-negative range of type TYPE. */
diff --git a/gcc/vr-values.h b/gcc/vr-values.h
index 17e71b7..ab8849a 100644
--- a/gcc/vr-values.h
+++ b/gcc/vr-values.h
@@ -21,7 +21,16 @@
#define GCC_VR_VALUES_H
#include "value-range-equiv.h"
-#include "gimple-range-gori.h"
+#include "gimple-range.h"
+
+// Generic object to return a range for an SSA.
+class range_store
+{
+public:
+ virtual bool range_of_expr (irange &r, tree expr, gimple *stmt = NULL) = 0;
+ virtual const class value_range_equiv *get_value_range (const_tree expr,
+ gimple *stmt = NULL) = 0;
+};
class simplify_using_ranges
{
