From fa8f67d081065db1b5692f5fc037139fb0d713a3 Mon Sep 17 00:00:00 2001 From: Aldy Hernandez Date: Thu, 2 Apr 2020 19:54:58 +0200 Subject: Shuffle all the ranger code around into various files: gimple-range-cache.* gimple-range-stmt.* gimple-range-gori.* gimple-range-cfg.* gimple-ranger.* --- gcc/Makefile.in | 7 +- gcc/gimple-range-cache.cc | 468 ++++++++++++++ gcc/gimple-range-cache.h | 84 +++ gcc/gimple-range-cfg.cc | 459 ++++++++++++++ gcc/gimple-range-cfg.h | 41 ++ gcc/gimple-range-gori.cc | 8 +- gcc/gimple-range-gori.h | 4 +- gcc/gimple-range-stmt.cc | 367 +++++++++++ gcc/gimple-range-stmt.h | 98 +++ gcc/gimple-range.cc | 381 ------------ gcc/gimple-range.h | 97 --- gcc/gimple-ranger.cc | 945 ++++++++++++++++++++++++++++ gcc/gimple-ranger.h | 139 +++++ gcc/gimple-ssa-evrp-analyze.c | 4 +- gcc/ssa-range-cache.cc | 485 --------------- gcc/ssa-range-cache.h | 84 --- gcc/ssa-range.cc | 1382 ----------------------------------------- gcc/ssa-range.h | 155 ----- gcc/vr-values.c | 2 +- 19 files changed, 2613 insertions(+), 2597 deletions(-) create mode 100644 gcc/gimple-range-cache.cc create mode 100644 gcc/gimple-range-cache.h create mode 100644 gcc/gimple-range-cfg.cc create mode 100644 gcc/gimple-range-cfg.h create mode 100644 gcc/gimple-range-stmt.cc create mode 100644 gcc/gimple-range-stmt.h delete mode 100644 gcc/gimple-range.cc delete mode 100644 gcc/gimple-range.h create mode 100644 gcc/gimple-ranger.cc create mode 100644 gcc/gimple-ranger.h delete mode 100644 gcc/ssa-range-cache.cc delete mode 100644 gcc/ssa-range-cache.h delete mode 100644 gcc/ssa-range.cc delete mode 100644 gcc/ssa-range.h (limited to 'gcc') diff --git a/gcc/Makefile.in b/gcc/Makefile.in index d66e6da..52ba209 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1327,7 +1327,10 @@ OBJS = \ gimple-loop-versioning.o \ gimple-low.o \ gimple-pretty-print.o \ - gimple-range.o \ + gimple-ranger.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 \ @@ -1497,8 +1500,6 @@ OBJS = \ spellcheck.o \ spellcheck-tree.o \ sreal.o \ - ssa-range.o \ - ssa-range-cache.o \ stack-ptr-mod.o \ statistics.o \ stmt.o \ diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc new file mode 100644 index 0000000..bfcc890 --- /dev/null +++ b/gcc/gimple-range-cache.cc @@ -0,0 +1,468 @@ +/* Gimple ranger SSA cache implementation. + Copyright (C) 2017-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "insn-codes.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "gimple-range-stmt.h" +#include "gimple-range-cache.h" + +// During contructor, Allocate the vector of ssa_names. + +non_null_ref::non_null_ref () +{ + m_nn.create (0); + m_nn.safe_grow_cleared (num_ssa_names); +} + +// Free any bitmaps which were allocated,a swell as the vector itself. + +non_null_ref::~non_null_ref () +{ + unsigned x; + for (x = 0; x< m_nn.length (); x++) + if (m_nn[x]) + BITMAP_FREE (m_nn[x]); +} + +// Return true if NAME has a non-null dereference in block bb. If this is the +// first query for NAME, calculate the summary first. + +bool +non_null_ref::non_null_deref_p (tree name, basic_block bb) +{ + if (!POINTER_TYPE_P (TREE_TYPE (name))) + return false; + + unsigned v = SSA_NAME_VERSION (name); + if (!m_nn[v]) + process_name (name); + + return bitmap_bit_p (m_nn[v], bb->index); +} + +// Allocate an populate the bitmap for NAME. An ON bit for a block index +// indicates there is a non-null reference in that block. +// In order to populate the bitmap, a quick run of all the immediate uses +// are made and the statement checked to see if a non-null dereference is made +// on that statement. + +void +non_null_ref::process_name (tree name) +{ + unsigned v = SSA_NAME_VERSION (name); + use_operand_p use_p; + imm_use_iterator iter; + bitmap b; + + // Only tracked for pointers. + if (!POINTER_TYPE_P (TREE_TYPE (name))) + return; + + // Already processed if a bitmap has been allocated. + if (m_nn[v]) + return; + + b = BITMAP_ALLOC (NULL); + + // Loop over each immediate use and see if it implies a non-null value. + FOR_EACH_IMM_USE_FAST (use_p, iter, name) + { + gimple *s = USE_STMT (use_p); + unsigned index = gimple_bb (s)->index; + tree value; + enum tree_code comp_code; + + // If bit is already set for this block, dont bother looking again. + if (bitmap_bit_p (b, index)) + continue; + + // If we can infer a != 0 range, then set the bit for this BB + if (infer_value_range (s, name, &comp_code, &value)) + { + if (comp_code == NE_EXPR && integer_zerop (value)) + bitmap_set_bit (b, index); + } + } + + m_nn[v] = b; +} + +// This class implements a cache of ranges indexed by basic block. +// It represents all that is known about an SSA_NAME on entry to each block +// It caches a range-for-type varying range so it doesnt need to be reformed all +// the time. If a range is ever always associated with a type, we can use that +// instead,. +// Whenever varying is being set for a block, the cache simply points +// to this cached one rather than create a new one each time. + +class ssa_block_ranges +{ +public: + ssa_block_ranges (tree t); + ~ssa_block_ranges (); + + void set_bb_range (const basic_block bb, const irange &r); + void set_bb_varying (const basic_block bb); + bool get_bb_range (irange &r, const basic_block bb); + bool bb_range_p (const basic_block bb); + + void dump(FILE *f); +private: + vec m_tab; + irange_storage *m_type_range; + tree m_type; +}; + + +// Initialize a block cache for an ssa_name of type T + +ssa_block_ranges::ssa_block_ranges (tree t) +{ + irange_storage tr; + gcc_assert (TYPE_P (t)); + m_type = t; + + m_tab.create (0); + m_tab.safe_grow_cleared (last_basic_block_for_fn (cfun)); + + // Create the cached type range. + tr.set_varying (t); + m_type_range = new irange_storage (tr); + + m_tab[ENTRY_BLOCK_PTR_FOR_FN (cfun)->index] = m_type_range; +} + +// Destruct block range. + +ssa_block_ranges::~ssa_block_ranges () +{ + m_tab.release (); +} + +// Set the range for block BB to be R. + +void +ssa_block_ranges::set_bb_range (const basic_block bb, const irange &r) +{ + irange_storage *m = m_tab[bb->index]; + +// If there is already range memory for this block, kill it. +// Look into reuse. +// +// right now we're losing memory. +// +// if (m && m != m_type_range) +// delete m; + + m = new irange_storage (r); + m_tab[bb->index] = m; +} + +// Set the range for block BB to the range for the type. + +void +ssa_block_ranges::set_bb_varying (const basic_block bb) +{ + m_tab[bb->index] = m_type_range; +} + +// Return the range associated with block BB in R. Return false if there is no +// range, + +bool +ssa_block_ranges::get_bb_range (irange &r, const basic_block bb) +{ + irange_storage *m = m_tab[bb->index]; + if (m) + { + r = irange_storage (*m); + return true; + } + return false; +} + +// Returns true if a range is present + +bool +ssa_block_ranges::bb_range_p (const basic_block bb) +{ + return m_tab[bb->index] != NULL; +} + + +// Print the list of known ranges for file F in a nice format. + +void +ssa_block_ranges::dump (FILE *f) +{ + basic_block bb; + widest_irange r; + + FOR_EACH_BB_FN (bb, cfun) + if (get_bb_range (r, bb)) + { + fprintf (f, "BB%d -> ", bb->index); + r.dump (f); + fprintf (f, "\n"); + } +} + +// ------------------------------------------------------------------------- + +// Initialize the block cache. + +block_range_cache::block_range_cache () +{ + m_ssa_ranges.create (0); + m_ssa_ranges.safe_grow_cleared (num_ssa_names); +} + +// Remove any m_block_caches which have been created. + +block_range_cache::~block_range_cache () +{ + unsigned x; + for (x = 0; x < m_ssa_ranges.length (); ++x) + { + if (m_ssa_ranges[x]) + delete m_ssa_ranges[x]; + } + // Release the vector itself. + m_ssa_ranges.release (); +} + +// Return a reference to the m_block_cache for NAME. If it has not been +// accessed yet, allocate it. + +ssa_block_ranges & +block_range_cache::get_block_ranges (tree name) +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_ssa_ranges.length ()) + m_ssa_ranges.safe_grow_cleared (num_ssa_names + 1); + + if (!m_ssa_ranges[v]) + m_ssa_ranges[v] = new ssa_block_ranges (TREE_TYPE (name)); + + return *(m_ssa_ranges[v]); +} + +// Set the range for NAME on entry to block BB to R. + +void +block_range_cache::set_bb_range (tree name, const basic_block bb, + const irange &r) +{ + gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); + return get_block_ranges (name).set_bb_range (bb, r); +} + +// Set the range for NAME on entry to block BB to varying.. + +void +block_range_cache::set_bb_varying (tree name, const basic_block bb) +{ + gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); + return get_block_ranges (name).set_bb_varying (bb); +} + +// Return the range for NAME on entry to BB in R. Return true if here is one. + +bool +block_range_cache::get_bb_range (irange &r, tree name, const basic_block bb) +{ + gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); + return get_block_ranges (name).get_bb_range (r, bb); +} + +// Return true if NAME has a range set in block BB. + +bool +block_range_cache::bb_range_p (tree name, const basic_block bb) +{ + gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); + return get_block_ranges (name).bb_range_p (bb); +} + +// Print all known block caches to file F. +void +block_range_cache::dump (FILE *f) +{ + unsigned x; + for (x = 0; x < m_ssa_ranges.length (); ++x) + { + if (m_ssa_ranges[x]) + { + fprintf (f, " Ranges for "); + print_generic_expr (f, ssa_name (x), TDF_NONE); + fprintf (f, ":\n"); + m_ssa_ranges[x]->dump (f); + fprintf (f, "\n"); + } + } +} + +// Print all known ranges on entry to blobk BB to file F. +void +block_range_cache::dump (FILE *f, basic_block bb, bool print_varying) +{ + unsigned x; + widest_irange r; + bool summarize_varying = false; + for (x = 1; x < m_ssa_ranges.length (); ++x) + { + if (!gimple_range_ssa_p (ssa_name (x))) + continue; + if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb)) + { + if (!print_varying && r.varying_p ()) + { + summarize_varying = true; + continue; + } + print_generic_expr (f, ssa_name (x), TDF_NONE); + fprintf (f, "\t"); + r.dump(f); + fprintf (f, "\n"); + } + } + // If there were any varying entries, lump them all together. + if (summarize_varying) + { + fprintf (f, "VARYING_P on entry : "); + for (x = 1; x < num_ssa_names; ++x) + { + if (!gimple_range_ssa_p (ssa_name (x))) + continue; + if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb)) + { + if (r.varying_p ()) + { + print_generic_expr (f, ssa_name (x), TDF_NONE); + fprintf (f, " "); + } + } + } + fprintf (f, "\n"); + } +} +// ------------------------------------------------------------------------- + +// Initialize a global cache. + +ssa_global_cache::ssa_global_cache () +{ + m_tab.create (0); + m_tab.safe_grow_cleared (num_ssa_names); +} + +// Deconstruct a global cache. + +ssa_global_cache::~ssa_global_cache () +{ + m_tab.release (); +} + +// Retrieve the global range of NAME from cache memory if it exists. +// Return the value in R. + +bool +ssa_global_cache::get_global_range (irange &r, tree name) const +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_tab.length ()) + return false; + + irange_storage *stow = m_tab[v]; + if (!stow) + return false; + r = irange_storage (*stow); + return true; +} + +// Set the range for NAME to R in the global cache. + +void +ssa_global_cache::set_global_range (tree name, const irange &r) +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_tab.length ()) + m_tab.safe_grow_cleared (num_ssa_names + 1); + irange_storage *m = m_tab[v]; + + // Ficme update in place it if fits. +// if (m && m->update (r, TREE_TYPE (name))) +// ; +// else + { +// m = irange_storage::alloc (r, TREE_TYPE (name)); + m = new irange_storage (r); + m_tab[SSA_NAME_VERSION (name)] = m; + } +} + +// Set the range for NAME to R in the glonbal cache. + +void +ssa_global_cache::clear_global_range (tree name) +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_tab.length ()) + m_tab.safe_grow_cleared (num_ssa_names + 1); + m_tab[v] = NULL; +} + +// Clear the global cache. + +void +ssa_global_cache::clear () +{ + memset (m_tab.address(), 0, m_tab.length () * sizeof (irange_storage *)); +} + +// Dump the contents of the global cache to F. + +void +ssa_global_cache::dump (FILE *f) +{ + unsigned x; + widest_irange r; + fprintf (f, "Non-varying global ranges:\n"); + fprintf (f, "=========================:\n"); + for ( x = 1; x < num_ssa_names; x++) + if (gimple_range_ssa_p (ssa_name (x)) && + get_global_range (r, ssa_name (x)) && !r.varying_p ()) + { + print_generic_expr (f, ssa_name (x), TDF_NONE); + fprintf (f, " : "); + r.dump (f); + fprintf (f, "\n"); + } + fputc ('\n', f); +} + + diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h new file mode 100644 index 0000000..b841ce2 --- /dev/null +++ b/gcc/gimple-range-cache.h @@ -0,0 +1,84 @@ +/* Header file for gimple ranger SSA cache. + Copyright (C) 2017-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_SSA_RANGE_CACHE_H +#define GCC_SSA_RANGE_CACHE_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. + +typedef int_range<3> irange_storage; + +class ssa_global_cache +{ +public: + ssa_global_cache (); + ~ssa_global_cache (); + bool get_global_range (irange& r, tree name) const; + void set_global_range (tree name, const irange&r); + void clear_global_range (tree name); + void clear (); + void dump (FILE *f = stderr); +private: + vec m_tab; +}; + +// Class used to track non-null references of an ssa-name +// A vector of bitmaps indexed by ssa-name is maintained. When indexed by +// Basic Block, an on-bit indicates there is a non-null dereference for +// that ssa_name in that basic block. + +class non_null_ref +{ +public: + non_null_ref (); + ~non_null_ref (); + bool non_null_deref_p (tree name, basic_block bb); +private: + vec m_nn; + void process_name (tree name); +}; + +// This class manages a vector of pointers to ssa_block ranges. +// THis provides the basis for the "range on entry" cache for +// all ssa-names. + +class block_range_cache +{ +public: + block_range_cache (); + ~block_range_cache (); + + // Hide the details of the block cache with these wrappers + void set_bb_range (tree name, const basic_block bb, const irange &r); + void set_bb_varying (tree name, const basic_block bb); + bool get_bb_range (irange &r, tree name, const basic_block bb); + bool bb_range_p (tree name, const basic_block bb); + + void dump (FILE *f); + void dump (FILE *f, basic_block bb, bool print_varying = true); +private: + vec m_ssa_ranges; + ssa_block_ranges &get_block_ranges (tree name); +}; + + +#endif // GCC_SSA_RANGE_CACHE_H diff --git a/gcc/gimple-range-cfg.cc b/gcc/gimple-range-cfg.cc new file mode 100644 index 0000000..a2ac0c4 --- /dev/null +++ b/gcc/gimple-range-cfg.cc @@ -0,0 +1,459 @@ +/* Implementation of the gimple_ranger class. + Copyright (C) 2017-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "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(s)) + res = range_of_phi (r, as_a (s)); + else if (is_a(s)) + res = range_of_call (r, as_a (s)); + else if (is_a (s) && gimple_assign_rhs_code (s) == COND_EXPR) + res = range_of_cond_expr (r, as_a (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. +// Return false if no range can be determined. + +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_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 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; +} + + +void +gimple_ranger::range_of_ubsan_call (irange &r, gcall *call, tree_code code) +{ + 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); +} + + +// 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); + tree arg; + int mini, maxi, zerov, prec; + scalar_int_mode mode; + + if (!irange::supports_type_p (type)) + return false; + + combined_fn func = gimple_call_combined_fn (call); + switch (func) + { + case CFN_BUILT_IN_CONSTANT_P: + if (cfun->after_inlining) + { + r.set_zero (type); + // r.equiv_clean (); + } + break; + /* __builtin_ffs* and __builtin_popcount* return [0, prec]. */ + CASE_CFN_FFS: + CASE_CFN_POPCOUNT: + arg = gimple_call_arg (call, 0); + prec = TYPE_PRECISION (TREE_TYPE (arg)); + mini = 0; + maxi = prec; + if (TREE_CODE (arg) == SSA_NAME) + { + widest_irange vr0; + gcc_assert (range_of_expr (vr0, arg, call)); + /* If arg is non-zero, then ffs or popcount are non-zero. */ + if (range_includes_zero_p (&vr0) == 0) + mini = 1; + /* If some high bits are known to be zero, we can decrease + the maximum. */ + if (vr0.kind () == VR_RANGE + && TREE_CODE (vr0.max ()) == INTEGER_CST + && !operand_less_p (vr0.min (), + build_zero_cst (TREE_TYPE (vr0.min ())))) + maxi = tree_floor_log2 (vr0.max ()) + 1; + } + r.set (build_int_cst (type, mini), + build_int_cst (type, maxi)); + break; + /* __builtin_parity* returns [0, 1]. */ + CASE_CFN_PARITY: + r.set (build_int_cst (type, 0), + build_int_cst (type, 1)); + break; + /* __builtin_c[lt]z* return [0, prec-1], except for + 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. */ + CASE_CFN_CLZ: + 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) + /* Handle only the single common value. */ + && zerov != prec) + /* Magic value to give up, unless vr0 proves + arg is non-zero. */ + mini = -2; + if (TREE_CODE (arg) == SSA_NAME) + { + widest_irange vr0; + gcc_assert (range_of_expr (vr0, arg, call)); + /* From clz of VR_RANGE minimum we can compute + result maximum. */ + if (vr0.kind () == VR_RANGE + && TREE_CODE (vr0.min ()) == INTEGER_CST) + { + maxi = prec - 1 - tree_floor_log2 (vr0.min ()); + if (maxi != prec) + mini = 0; + } + else if (!range_includes_zero_p (&vr0)) + { + maxi = prec - 1; + mini = 0; + } + if (mini == -2) + break; + /* From clz of VR_RANGE maximum we can compute + result minimum. */ + if (vr0.kind () == VR_RANGE + && TREE_CODE (vr0.max ()) == INTEGER_CST) + { + mini = prec - 1 - tree_floor_log2 (vr0.max ()); + if (mini == prec) + break; + } + } + if (mini == -2) + break; + r.set (build_int_cst (type, mini), + build_int_cst (type, maxi)); + break; + /* __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. */ + CASE_CFN_CTZ: + 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 vr0 proves + arg is non-zero. */ + mini = -2; + } + if (TREE_CODE (arg) == SSA_NAME) + { + widest_irange vr0; + gcc_assert (range_of_expr (vr0, arg, call)); + /* If arg is non-zero, then use [0, prec - 1]. */ + if (vr0.kind () == VR_RANGE + && integer_nonzerop (vr0.min ())) + { + mini = 0; + maxi = prec - 1; + } + /* If some high bits are known to be zero, + we can decrease the result maximum. */ + if (vr0.kind () == VR_RANGE + && TREE_CODE (vr0.max ()) == INTEGER_CST) + { + maxi = tree_floor_log2 (vr0.max ()); + /* For vr0 [0, 0] give up. */ + if (maxi == -1) + break; + } + } + if (mini == -2) + break; + r.set (build_int_cst (type, mini), + build_int_cst (type, maxi)); + break; + /* __builtin_clrsb* returns [0, prec-1]. */ + 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)); + break; + case CFN_UBSAN_CHECK_ADD: + range_of_ubsan_call (r, call, PLUS_EXPR); + break; + case CFN_UBSAN_CHECK_SUB: + range_of_ubsan_call (r, call, MINUS_EXPR); + break; + case CFN_UBSAN_CHECK_MUL: + range_of_ubsan_call (r, call, MULT_EXPR); + break; + 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); + + tree type = TREE_TYPE (gimple_call_lhs (call)); + r.set (build_int_cst (type, is_pos ? 0 : 1), + size + ? build_int_cst (type, size - is_pos) : vrp_val_max (type)); + } + break; + 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); + break; + } + break; + default: + { + bool ignore; + if (gimple_stmt_nonnegative_warnv_p (call, &ignore)) + 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); + break; + } + } + + // 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; +} diff --git a/gcc/gimple-range-cfg.h b/gcc/gimple-range-cfg.h new file mode 100644 index 0000000..d7e7883 --- /dev/null +++ b/gcc/gimple-range-cfg.h @@ -0,0 +1,41 @@ +/* Header file for the gimple_ranger class. + Copyright (C) 2017-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_GIMPLE_RANGE_CFG_H +#define GCC_GIMPLE_RANGE_CFG_H + +class gimple_ranger : public gori_compute +{ +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_phi (irange &r, gphi *phi); + bool range_of_call (irange &r, gcall *call); + bool range_of_cond_expr (irange &r, gassign* cond); +private: + void range_of_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 f44a6b2..e3535c9 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1,5 +1,5 @@ -/* GIMPLE range GORI functions. - Copyright (C) 2017-2019 Free Software Foundation, Inc. +/* Gimple range GORI functions. + Copyright (C) 2017-2020 Free Software Foundation, Inc. Contributed by Andrew MacLeod . This file is part of GCC. @@ -26,9 +26,7 @@ along with GCC; see the file COPYING3. If not see #include "gimple.h" #include "ssa.h" #include "gimple-pretty-print.h" -#include "diagnostic-core.h" -#include "wide-int.h" -#include "gimple-range.h" +#include "gimple-range-stmt.h" #include "gimple-range-gori.h" #include "fold-const.h" diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index 45aaa24..a393f47 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -1,5 +1,5 @@ -/* Header file for GIMPLE range GORI structures. - Copyright (C) 2017-2019 Free Software Foundation, Inc. +/* Header file for gimple range GORI structures. + Copyright (C) 2017-2020 Free Software Foundation, Inc. Contributed by Andrew MacLeod . This file is part of GCC. diff --git a/gcc/gimple-range-stmt.cc b/gcc/gimple-range-stmt.cc new file mode 100644 index 0000000..4e48477 --- /dev/null +++ b/gcc/gimple-range-stmt.cc @@ -0,0 +1,367 @@ +/* Code for GIMPLE range related routines. + Copyright (C) 2019-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod + and Aldy Hernandez . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "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" + +// 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. + +static void +gimple_range_adjustment (const gimple *stmt, irange &res) +{ + switch (gimple_expr_code (stmt)) + { + case IMAGPART_EXPR: + { + tree name; + tree type = TREE_TYPE (gimple_assign_lhs (stmt)); + + 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); + 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_single_range (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; + + if (e != gimple_switch_default_edge (cfun, sw)) + { + r.set_undefined (); + // Loop through all the switches edges, ignoring the default edge. + // unioning the ranges together. + 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. + // intersecting the ranges not covered by the case. + for (x = 1; x < lim; x++) + { + 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 (s) || is_a (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 (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 (s)); + gswitch *sw = as_a (s); + tree type = TREE_TYPE (gimple_switch_index (sw)); + + if (!irange::supports_type_p (type)) + return NULL; + + return calc_single_range (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 (stmt, res); + return true; +} + + +// 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 expr = gimple_assign_rhs1 (stmt); + if (gimple_assign_rhs_code (stmt) == ADDR_EXPR) + { + // 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 base = get_base_address (TREE_OPERAND (expr, 0)); + if (base != NULL_TREE && TREE_CODE (base) == MEM_REF) + { + // If the base address is an SSA_NAME, return it. + tree b = TREE_OPERAND (base, 0); + if (TREE_CODE (b) == SSA_NAME) + return b; + } + } + return expr; + } + 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 new file mode 100644 index 0000000..ddc6872 --- /dev/null +++ b/gcc/gimple-range-stmt.h @@ -0,0 +1,98 @@ +/* Header file for the GIMPLE range interface. + Copyright (C) 2019-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod + and Aldy Hernandez . + +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 +. */ + +#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 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-range.cc b/gcc/gimple-range.cc deleted file mode 100644 index 2bed7da..0000000 --- a/gcc/gimple-range.cc +++ /dev/null @@ -1,381 +0,0 @@ -/* Code for GIMPLE range related routines. - Copyright (C) 2019 Free Software Foundation, Inc. - Contributed by Andrew MacLeod - and Aldy Hernandez . - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 3, or (at your option) -any later version. - -GCC is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "backend.h" -#include "insn-codes.h" -#include "rtl.h" -#include "tree.h" -#include "gimple.h" -#include "cfghooks.h" -#include "tree-pass.h" -#include "ssa.h" -#include "optabs-tree.h" -#include "gimple-pretty-print.h" -#include "diagnostic-core.h" -#include "flags.h" -#include "fold-const.h" -#include "stor-layout.h" -#include "calls.h" -#include "cfganal.h" -#include "gimple-fold.h" -#include "tree-eh.h" -#include "gimple-iterator.h" -#include "gimple-walk.h" -#include "tree-cfg.h" -#include "wide-int.h" -#include "gimple-range.h" - -// 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. - -static void -gimple_range_adjustment (const gimple *stmt, irange &res) -{ - switch (gimple_expr_code (stmt)) - { - case IMAGPART_EXPR: - { - tree name; - tree type = TREE_TYPE (gimple_assign_lhs (stmt)); - - 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); - 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_single_range (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; - - if (e != gimple_switch_default_edge (cfun, sw)) - { - r.set_undefined (); - // Loop through all the switches edges, ignoring the default edge. - // unioning the ranges together. - 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. - // intersecting the ranges not covered by the case. - for (x = 1; x < lim; x++) - { - 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 (s) || is_a (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 (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 (s)); - gswitch *sw = as_a (s); - tree type = TREE_TYPE (gimple_switch_index (sw)); - - if (!irange::supports_type_p (type)) - return NULL; - - return calc_single_range (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 (stmt, res); - return true; -} - - -// 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 expr = gimple_assign_rhs1 (stmt); - if (gimple_assign_rhs_code (stmt) == ADDR_EXPR) - { - // 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 base = get_base_address (TREE_OPERAND (expr, 0)); - if (base != NULL_TREE && TREE_CODE (base) == MEM_REF) - { - // If the base address is an SSA_NAME, return it. - tree b = TREE_OPERAND (base, 0); - if (TREE_CODE (b) == SSA_NAME) - return b; - } - } - return expr; - } - 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.h b/gcc/gimple-range.h deleted file mode 100644 index 641522b..0000000 --- a/gcc/gimple-range.h +++ /dev/null @@ -1,97 +0,0 @@ -/* Header file for the GIMPLE range interface. - Copyright (C) 2019 Free Software Foundation, Inc. - Contributed by Andrew MacLeod . - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it under -the terms of the GNU General Public License as published by the Free -Software Foundation; either version 3, or (at your option) any later -version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -. */ - -#ifndef GCC_GIMPLE_RANGE_H -#define GCC_GIMPLE_RANGE_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 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_H diff --git a/gcc/gimple-ranger.cc b/gcc/gimple-ranger.cc new file mode 100644 index 0000000..1d3e872 --- /dev/null +++ b/gcc/gimple-ranger.cc @@ -0,0 +1,945 @@ +/* Main entry point for the gimple ranger. + Copyright (C) 2017-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod + and Aldy Hernandez . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "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 isnt 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 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 (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) +{ + + gimple *def_stmt = SSA_NAME_DEF_STMT (name); + basic_block def_bb = NULL; + + gcc_checking_assert (gimple_range_ssa_p (name)); + + if (calc) + { + 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 fo 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::loop_ranger () +{ + m_vr_values = new vr_values_tester; +} + +loop_ranger::~loop_ranger () +{ + delete m_vr_values; +} + +// Adjust a PHI result with loop information. + +void +loop_ranger::adjust_phi_with_loop_info (irange &r, gphi *phi) +{ + struct loop *l = loop_containing_stmt (phi); + if (l && l->header == gimple_bb (phi)) + { + tree phi_result = PHI_RESULT (phi); + value_range vl = r; + value_range_equiv vr = vl; + m_vr_values->adjust_range_with_scev (&vr, l, phi, phi_result); + if (vr.constant_p ()) + { + widest_irange old = r; + r = vr; + if (old != r + && dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "LOOP_RANGER refined this PHI result: "); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); + fprintf (dump_file, " from this range: "); + old.dump (dump_file); + fprintf (dump_file, "\n"); + fprintf (dump_file, " into this range: "); + r.dump (dump_file); + fprintf (dump_file, "\n"); + } + } + } +} + +// Virtual override of global_ranger::range_of_phi() that adjusts the +// result with loop information if available. + +bool +loop_ranger::range_of_stmt (irange &r, gimple *s, tree name) +{ + bool result = global_ranger::range_of_stmt (r, s, name); + if (result && is_a (s) && scev_initialized_p ()) + adjust_phi_with_loop_info (r, as_a (s)); + return result; +} + +// Constructor for trace_ranger. + +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_DETAILS)) + { + // 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) +{ + 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); + } + 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 new file mode 100644 index 0000000..f2b31ed --- /dev/null +++ b/gcc/gimple-ranger.h @@ -0,0 +1,139 @@ +/* Header file for the gimple ranger. + Copyright (C) 2017-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod + and Aldy Hernandez . + +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 +. */ + +#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); + + 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); +private: + 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); + + ssa_global_cache m_globals; + block_range_cache m_on_entry; + non_null_ref m_non_null; + vec m_workback; + vec 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 bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE); +private: + void adjust_phi_with_loop_info (irange &r, gphi *phi); + + 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 global_ranger super; // Inherited from class for easy changing. + 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/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c index 43daa72..7a3f22f 100644 --- a/gcc/gimple-ssa-evrp-analyze.c +++ b/gcc/gimple-ssa-evrp-analyze.c @@ -42,8 +42,8 @@ along with GCC; see the file COPYING3. If not see #include "vr-values.h" #include "gimple-ssa-evrp-analyze.h" #include "dbgcnt.h" -#include "gimple-range.h" -#include "ssa-range.h" +#include "gimple-range-stmt.h" +#include "gimple-ranger.h" class vr_gori_interface : public trace_gori_compute { diff --git a/gcc/ssa-range-cache.cc b/gcc/ssa-range-cache.cc deleted file mode 100644 index b8011a5..0000000 --- a/gcc/ssa-range-cache.cc +++ /dev/null @@ -1,485 +0,0 @@ -/* SSA range cache related functionalilty. - Copyright (C) 2017-2018 Free Software Foundation, Inc. - Contributed by Andrew MacLeod . - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 3, or (at your option) -any later version. - -GCC is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "backend.h" -#include "insn-codes.h" -#include "rtl.h" -#include "tree.h" -#include "gimple.h" -#include "cfghooks.h" -#include "tree-pass.h" -#include "ssa.h" -#include "optabs-tree.h" -#include "gimple-pretty-print.h" -#include "diagnostic-core.h" -#include "flags.h" -#include "fold-const.h" -#include "stor-layout.h" -#include "calls.h" -#include "cfganal.h" -#include "gimple-fold.h" -#include "tree-eh.h" -#include "gimple-iterator.h" -#include "gimple-walk.h" -#include "tree-cfg.h" -#include "wide-int.h" -#include "ssa-range.h" -#include "fold-const.h" -#include "dbgcnt.h" - -// During contructor, Allocate the vector of ssa_names. - -non_null_ref::non_null_ref () -{ - m_nn.create (0); - m_nn.safe_grow_cleared (num_ssa_names); -} - -// Free any bitmaps which were allocated,a swell as the vector itself. - -non_null_ref::~non_null_ref () -{ - unsigned x; - for (x = 0; x< m_nn.length (); x++) - if (m_nn[x]) - BITMAP_FREE (m_nn[x]); -} - -// Return true if NAME has a non-null dereference in block bb. If this is the -// first query for NAME, calculate the summary first. - -bool -non_null_ref::non_null_deref_p (tree name, basic_block bb) -{ - if (!POINTER_TYPE_P (TREE_TYPE (name))) - return false; - - unsigned v = SSA_NAME_VERSION (name); - if (!m_nn[v]) - process_name (name); - - return bitmap_bit_p (m_nn[v], bb->index); -} - -// Allocate an populate the bitmap for NAME. An ON bit for a block index -// indicates there is a non-null reference in that block. -// In order to populate the bitmap, a quick run of all the immediate uses -// are made and the statement checked to see if a non-null dereference is made -// on that statement. - -void -non_null_ref::process_name (tree name) -{ - unsigned v = SSA_NAME_VERSION (name); - use_operand_p use_p; - imm_use_iterator iter; - bitmap b; - - // Only tracked for pointers. - if (!POINTER_TYPE_P (TREE_TYPE (name))) - return; - - // Already processed if a bitmap has been allocated. - if (m_nn[v]) - return; - - b = BITMAP_ALLOC (NULL); - - // Loop over each immediate use and see if it implies a non-null value. - FOR_EACH_IMM_USE_FAST (use_p, iter, name) - { - gimple *s = USE_STMT (use_p); - unsigned index = gimple_bb (s)->index; - tree value; - enum tree_code comp_code; - - // If bit is already set for this block, dont bother looking again. - if (bitmap_bit_p (b, index)) - continue; - - // If we can infer a != 0 range, then set the bit for this BB - if (infer_value_range (s, name, &comp_code, &value)) - { - if (comp_code == NE_EXPR && integer_zerop (value)) - bitmap_set_bit (b, index); - } - } - - m_nn[v] = b; -} - -// This class implements a cache of ranges indexed by basic block. -// It represents all that is known about an SSA_NAME on entry to each block -// It caches a range-for-type varying range so it doesnt need to be reformed all -// the time. If a range is ever always associated with a type, we can use that -// instead,. -// Whenever varying is being set for a block, the cache simply points -// to this cached one rather than create a new one each time. - -class ssa_block_ranges -{ -public: - ssa_block_ranges (tree t); - ~ssa_block_ranges (); - - void set_bb_range (const basic_block bb, const irange &r); - void set_bb_varying (const basic_block bb); - bool get_bb_range (irange &r, const basic_block bb); - bool bb_range_p (const basic_block bb); - - void dump(FILE *f); -private: - vec m_tab; - irange_storage *m_type_range; - tree m_type; -}; - - -// Initialize a block cache for an ssa_name of type T - -ssa_block_ranges::ssa_block_ranges (tree t) -{ - irange_storage tr; - gcc_assert (TYPE_P (t)); - m_type = t; - - m_tab.create (0); - m_tab.safe_grow_cleared (last_basic_block_for_fn (cfun)); - - // Create the cached type range. - tr.set_varying (t); - m_type_range = new irange_storage (tr); - - m_tab[ENTRY_BLOCK_PTR_FOR_FN (cfun)->index] = m_type_range; -} - -// Destruct block range. - -ssa_block_ranges::~ssa_block_ranges () -{ - m_tab.release (); -} - -// Set the range for block BB to be R. - -void -ssa_block_ranges::set_bb_range (const basic_block bb, const irange &r) -{ - irange_storage *m = m_tab[bb->index]; - -// If there is already range memory for this block, kill it. -// Look into reuse. -// -// right now we're losing memory. -// -// if (m && m != m_type_range) -// delete m; - - m = new irange_storage (r); - m_tab[bb->index] = m; -} - -// Set the range for block BB to the range for the type. - -void -ssa_block_ranges::set_bb_varying (const basic_block bb) -{ - m_tab[bb->index] = m_type_range; -} - -// Return the range associated with block BB in R. Return false if there is no -// range, - -bool -ssa_block_ranges::get_bb_range (irange &r, const basic_block bb) -{ - irange_storage *m = m_tab[bb->index]; - if (m) - { - r = irange_storage (*m); - return true; - } - return false; -} - -// Returns true if a range is present - -bool -ssa_block_ranges::bb_range_p (const basic_block bb) -{ - return m_tab[bb->index] != NULL; -} - - -// Print the list of known ranges for file F in a nice format. - -void -ssa_block_ranges::dump (FILE *f) -{ - basic_block bb; - widest_irange r; - - FOR_EACH_BB_FN (bb, cfun) - if (get_bb_range (r, bb)) - { - fprintf (f, "BB%d -> ", bb->index); - r.dump (f); - fprintf (f, "\n"); - } -} - -// ------------------------------------------------------------------------- - -// Initialize the block cache. - -block_range_cache::block_range_cache () -{ - m_ssa_ranges.create (0); - m_ssa_ranges.safe_grow_cleared (num_ssa_names); -} - -// Remove any m_block_caches which have been created. - -block_range_cache::~block_range_cache () -{ - unsigned x; - for (x = 0; x < m_ssa_ranges.length (); ++x) - { - if (m_ssa_ranges[x]) - delete m_ssa_ranges[x]; - } - // Release the vector itself. - m_ssa_ranges.release (); -} - -// Return a reference to the m_block_cache for NAME. If it has not been -// accessed yet, allocate it. - -ssa_block_ranges & -block_range_cache::get_block_ranges (tree name) -{ - unsigned v = SSA_NAME_VERSION (name); - if (v >= m_ssa_ranges.length ()) - m_ssa_ranges.safe_grow_cleared (num_ssa_names + 1); - - if (!m_ssa_ranges[v]) - m_ssa_ranges[v] = new ssa_block_ranges (TREE_TYPE (name)); - - return *(m_ssa_ranges[v]); -} - -// Set the range for NAME on entry to block BB to R. - -void -block_range_cache::set_bb_range (tree name, const basic_block bb, - const irange &r) -{ - gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); - return get_block_ranges (name).set_bb_range (bb, r); -} - -// Set the range for NAME on entry to block BB to varying.. - -void -block_range_cache::set_bb_varying (tree name, const basic_block bb) -{ - gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); - return get_block_ranges (name).set_bb_varying (bb); -} - -// Return the range for NAME on entry to BB in R. Return true if here is one. - -bool -block_range_cache::get_bb_range (irange &r, tree name, const basic_block bb) -{ - gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); - return get_block_ranges (name).get_bb_range (r, bb); -} - -// Return true if NAME has a range set in block BB. - -bool -block_range_cache::bb_range_p (tree name, const basic_block bb) -{ - gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); - return get_block_ranges (name).bb_range_p (bb); -} - -// Print all known block caches to file F. -void -block_range_cache::dump (FILE *f) -{ - unsigned x; - for (x = 0; x < m_ssa_ranges.length (); ++x) - { - if (m_ssa_ranges[x]) - { - fprintf (f, " Ranges for "); - print_generic_expr (f, ssa_name (x), TDF_NONE); - fprintf (f, ":\n"); - m_ssa_ranges[x]->dump (f); - fprintf (f, "\n"); - } - } -} - -// Print all known ranges on entry to blobk BB to file F. -void -block_range_cache::dump (FILE *f, basic_block bb, bool print_varying) -{ - unsigned x; - widest_irange r; - bool summarize_varying = false; - for (x = 1; x < m_ssa_ranges.length (); ++x) - { - if (!gimple_range_ssa_p (ssa_name (x))) - continue; - if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb)) - { - if (!print_varying && r.varying_p ()) - { - summarize_varying = true; - continue; - } - print_generic_expr (f, ssa_name (x), TDF_NONE); - fprintf (f, "\t"); - r.dump(f); - fprintf (f, "\n"); - } - } - // If there were any varying entries, lump them all together. - if (summarize_varying) - { - fprintf (f, "VARYING_P on entry : "); - for (x = 1; x < num_ssa_names; ++x) - { - if (!gimple_range_ssa_p (ssa_name (x))) - continue; - if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb)) - { - if (r.varying_p ()) - { - print_generic_expr (f, ssa_name (x), TDF_NONE); - fprintf (f, " "); - } - } - } - fprintf (f, "\n"); - } -} -// ------------------------------------------------------------------------- - -// Initialize a global cache. - -ssa_global_cache::ssa_global_cache () -{ - m_tab.create (0); - m_tab.safe_grow_cleared (num_ssa_names); -} - -// Deconstruct a global cache. - -ssa_global_cache::~ssa_global_cache () -{ - m_tab.release (); -} - -// Retrieve the global range of NAME from cache memory if it exists. -// Return the value in R. - -bool -ssa_global_cache::get_global_range (irange &r, tree name) const -{ - unsigned v = SSA_NAME_VERSION (name); - if (v >= m_tab.length ()) - return false; - - irange_storage *stow = m_tab[v]; - if (!stow) - return false; - r = irange_storage (*stow); - return true; -} - -// Set the range for NAME to R in the global cache. - -void -ssa_global_cache::set_global_range (tree name, const irange &r) -{ - unsigned v = SSA_NAME_VERSION (name); - if (v >= m_tab.length ()) - m_tab.safe_grow_cleared (num_ssa_names + 1); - irange_storage *m = m_tab[v]; - - // Ficme update in place it if fits. -// if (m && m->update (r, TREE_TYPE (name))) -// ; -// else - { -// m = irange_storage::alloc (r, TREE_TYPE (name)); - m = new irange_storage (r); - m_tab[SSA_NAME_VERSION (name)] = m; - } -} - -// Set the range for NAME to R in the glonbal cache. - -void -ssa_global_cache::clear_global_range (tree name) -{ - unsigned v = SSA_NAME_VERSION (name); - if (v >= m_tab.length ()) - m_tab.safe_grow_cleared (num_ssa_names + 1); - m_tab[v] = NULL; -} - -// Clear the global cache. - -void -ssa_global_cache::clear () -{ - memset (m_tab.address(), 0, m_tab.length () * sizeof (irange_storage *)); -} - -// Dump the contents of the global cache to F. - -void -ssa_global_cache::dump (FILE *f) -{ - unsigned x; - widest_irange r; - fprintf (f, "Non-varying global ranges:\n"); - fprintf (f, "=========================:\n"); - for ( x = 1; x < num_ssa_names; x++) - if (gimple_range_ssa_p (ssa_name (x)) && - get_global_range (r, ssa_name (x)) && !r.varying_p ()) - { - print_generic_expr (f, ssa_name (x), TDF_NONE); - fprintf (f, " : "); - r.dump (f); - fprintf (f, "\n"); - } - fputc ('\n', f); -} - - diff --git a/gcc/ssa-range-cache.h b/gcc/ssa-range-cache.h deleted file mode 100644 index 79827df..0000000 --- a/gcc/ssa-range-cache.h +++ /dev/null @@ -1,84 +0,0 @@ -/* Header file for SSA range cache classes. - Copyright (C) 2017-2018 Free Software Foundation, Inc. - Contributed by Andrew MacLeod . - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it under -the terms of the GNU General Public License as published by the Free -Software Foundation; either version 3, or (at your option) any later -version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -. */ - -#ifndef GCC_SSA_RANGE_CACHE_H -#define GCC_SSA_RANGE_CACHE_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. - -typedef int_range<3> irange_storage; - -class ssa_global_cache -{ -public: - ssa_global_cache (); - ~ssa_global_cache (); - bool get_global_range (irange& r, tree name) const; - void set_global_range (tree name, const irange&r); - void clear_global_range (tree name); - void clear (); - void dump (FILE *f = stderr); -private: - vec m_tab; -}; - -// Class used to track non-null references of an ssa-name -// A vector of bitmaps indexed by ssa-name is maintained. When indexed by -// Basic Block, an on-bit indicates there is a non-null dereference for -// that ssa_name in that basic block. - -class non_null_ref -{ -public: - non_null_ref (); - ~non_null_ref (); - bool non_null_deref_p (tree name, basic_block bb); -private: - vec m_nn; - void process_name (tree name); -}; - -// This class manages a vector of pointers to ssa_block ranges. -// THis provides the basis for the "range on entry" cache for -// all ssa-names. - -class block_range_cache -{ -public: - block_range_cache (); - ~block_range_cache (); - - // Hide the details of the block cache with these wrappers - void set_bb_range (tree name, const basic_block bb, const irange &r); - void set_bb_varying (tree name, const basic_block bb); - bool get_bb_range (irange &r, tree name, const basic_block bb); - bool bb_range_p (tree name, const basic_block bb); - - void dump (FILE *f); - void dump (FILE *f, basic_block bb, bool print_varying = true); -private: - vec m_ssa_ranges; - ssa_block_ranges &get_block_ranges (tree name); -}; - - -#endif // GCC_SSA_RANGE_CACHE_H diff --git a/gcc/ssa-range.cc b/gcc/ssa-range.cc deleted file mode 100644 index 1d3f644..0000000 --- a/gcc/ssa-range.cc +++ /dev/null @@ -1,1382 +0,0 @@ -/* SSA range support functions. - Copyright (C) 2017-2018 Free Software Foundation, Inc. - Contributed by Andrew MacLeod . - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 3, or (at your option) -any later version. - -GCC is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "backend.h" -#include "insn-codes.h" -#include "rtl.h" -#include "tree.h" -#include "gimple.h" -#include "cfghooks.h" -#include "tree-pass.h" -#include "ssa.h" -#include "optabs-tree.h" -#include "gimple-pretty-print.h" -#include "diagnostic-core.h" -#include "flags.h" -#include "fold-const.h" -#include "stor-layout.h" -#include "calls.h" -#include "cfganal.h" -#include "gimple-fold.h" -#include "tree-eh.h" -#include "gimple-iterator.h" -#include "gimple-walk.h" -#include "tree-cfg.h" -#include "wide-int.h" -#include "ssa-range.h" -#include "fold-const.h" -#include "cfgloop.h" -#include "tree-scalar-evolution.h" -#include "tree-ssa-loop.h" -#include "alloc-pool.h" -#include "vr-values.h" -#include "dbgcnt.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(s)) - res = range_of_phi (r, as_a (s)); - else if (is_a(s)) - res = range_of_call (r, as_a (s)); - else if (is_a (s) && gimple_assign_rhs_code (s) == COND_EXPR) - res = range_of_cond_expr (r, as_a (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. -// Return false if no range can be determined. - -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_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 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; -} - - -void -gimple_ranger::range_of_ubsan_call (irange &r, gcall *call, tree_code code) -{ - 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); -} - - -// 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); - tree arg; - int mini, maxi, zerov, prec; - scalar_int_mode mode; - - if (!irange::supports_type_p (type)) - return false; - - combined_fn func = gimple_call_combined_fn (call); - switch (func) - { - case CFN_BUILT_IN_CONSTANT_P: - if (cfun->after_inlining) - { - r.set_zero (type); - // r.equiv_clean (); - } - break; - /* __builtin_ffs* and __builtin_popcount* return [0, prec]. */ - CASE_CFN_FFS: - CASE_CFN_POPCOUNT: - arg = gimple_call_arg (call, 0); - prec = TYPE_PRECISION (TREE_TYPE (arg)); - mini = 0; - maxi = prec; - if (TREE_CODE (arg) == SSA_NAME) - { - widest_irange vr0; - gcc_assert (range_of_expr (vr0, arg, call)); - /* If arg is non-zero, then ffs or popcount are non-zero. */ - if (range_includes_zero_p (&vr0) == 0) - mini = 1; - /* If some high bits are known to be zero, we can decrease - the maximum. */ - if (vr0.kind () == VR_RANGE - && TREE_CODE (vr0.max ()) == INTEGER_CST - && !operand_less_p (vr0.min (), - build_zero_cst (TREE_TYPE (vr0.min ())))) - maxi = tree_floor_log2 (vr0.max ()) + 1; - } - r.set (build_int_cst (type, mini), - build_int_cst (type, maxi)); - break; - /* __builtin_parity* returns [0, 1]. */ - CASE_CFN_PARITY: - r.set (build_int_cst (type, 0), - build_int_cst (type, 1)); - break; - /* __builtin_c[lt]z* return [0, prec-1], except for - 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. */ - CASE_CFN_CLZ: - 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) - /* Handle only the single common value. */ - && zerov != prec) - /* Magic value to give up, unless vr0 proves - arg is non-zero. */ - mini = -2; - if (TREE_CODE (arg) == SSA_NAME) - { - widest_irange vr0; - gcc_assert (range_of_expr (vr0, arg, call)); - /* From clz of VR_RANGE minimum we can compute - result maximum. */ - if (vr0.kind () == VR_RANGE - && TREE_CODE (vr0.min ()) == INTEGER_CST) - { - maxi = prec - 1 - tree_floor_log2 (vr0.min ()); - if (maxi != prec) - mini = 0; - } - else if (!range_includes_zero_p (&vr0)) - { - maxi = prec - 1; - mini = 0; - } - if (mini == -2) - break; - /* From clz of VR_RANGE maximum we can compute - result minimum. */ - if (vr0.kind () == VR_RANGE - && TREE_CODE (vr0.max ()) == INTEGER_CST) - { - mini = prec - 1 - tree_floor_log2 (vr0.max ()); - if (mini == prec) - break; - } - } - if (mini == -2) - break; - r.set (build_int_cst (type, mini), - build_int_cst (type, maxi)); - break; - /* __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. */ - CASE_CFN_CTZ: - 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 vr0 proves - arg is non-zero. */ - mini = -2; - } - if (TREE_CODE (arg) == SSA_NAME) - { - widest_irange vr0; - gcc_assert (range_of_expr (vr0, arg, call)); - /* If arg is non-zero, then use [0, prec - 1]. */ - if (vr0.kind () == VR_RANGE - && integer_nonzerop (vr0.min ())) - { - mini = 0; - maxi = prec - 1; - } - /* If some high bits are known to be zero, - we can decrease the result maximum. */ - if (vr0.kind () == VR_RANGE - && TREE_CODE (vr0.max ()) == INTEGER_CST) - { - maxi = tree_floor_log2 (vr0.max ()); - /* For vr0 [0, 0] give up. */ - if (maxi == -1) - break; - } - } - if (mini == -2) - break; - r.set (build_int_cst (type, mini), - build_int_cst (type, maxi)); - break; - /* __builtin_clrsb* returns [0, prec-1]. */ - 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)); - break; - case CFN_UBSAN_CHECK_ADD: - range_of_ubsan_call (r, call, PLUS_EXPR); - break; - case CFN_UBSAN_CHECK_SUB: - range_of_ubsan_call (r, call, MINUS_EXPR); - break; - case CFN_UBSAN_CHECK_MUL: - range_of_ubsan_call (r, call, MULT_EXPR); - break; - 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); - - tree type = TREE_TYPE (gimple_call_lhs (call)); - r.set (build_int_cst (type, is_pos ? 0 : 1), - size - ? build_int_cst (type, size - is_pos) : vrp_val_max (type)); - } - break; - 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); - break; - } - break; - default: - { - bool ignore; - if (gimple_stmt_nonnegative_warnv_p (call, &ignore)) - 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); - break; - } - } - - // 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; -} - - -// 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 isnt 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 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 (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) -{ - - gimple *def_stmt = SSA_NAME_DEF_STMT (name); - basic_block def_bb = NULL; - - gcc_checking_assert (gimple_range_ssa_p (name)); - - if (calc) - { - 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 fo 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::loop_ranger () -{ - m_vr_values = new vr_values_tester; -} - -loop_ranger::~loop_ranger () -{ - delete m_vr_values; -} - -// Adjust a PHI result with loop information. - -void -loop_ranger::adjust_phi_with_loop_info (irange &r, gphi *phi) -{ - struct loop *l = loop_containing_stmt (phi); - if (l && l->header == gimple_bb (phi)) - { - tree phi_result = PHI_RESULT (phi); - value_range vl = r; - value_range_equiv vr = vl; - m_vr_values->adjust_range_with_scev (&vr, l, phi, phi_result); - if (vr.constant_p ()) - { - widest_irange old = r; - r = vr; - if (old != r - && dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "LOOP_RANGER refined this PHI result: "); - print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); - fprintf (dump_file, " from this range: "); - old.dump (dump_file); - fprintf (dump_file, "\n"); - fprintf (dump_file, " into this range: "); - r.dump (dump_file); - fprintf (dump_file, "\n"); - } - } - } -} - -// Virtual override of global_ranger::range_of_phi() that adjusts the -// result with loop information if available. - -bool -loop_ranger::range_of_stmt (irange &r, gimple *s, tree name) -{ - bool result = global_ranger::range_of_stmt (r, s, name); - if (result && is_a (s) && scev_initialized_p ()) - adjust_phi_with_loop_info (r, as_a (s)); - return result; -} - -// Constructor for trace_ranger. - -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_DETAILS)) - { - // 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) -{ - 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); - } - 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/ssa-range.h b/gcc/ssa-range.h deleted file mode 100644 index 87acc95..0000000 --- a/gcc/ssa-range.h +++ /dev/null @@ -1,155 +0,0 @@ -/* Header file for SSA range interface. - Copyright (C) 2017-2018 Free Software Foundation, Inc. - Contributed by Andrew MacLeod . - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it under -the terms of the GNU General Public License as published by the Free -Software Foundation; either version 3, or (at your option) any later -version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -. */ - -#ifndef GCC_SSA_RANGE_H -#define GCC_SSA_RANGE_H - -#include "gimple-range.h" -#include "gimple-range-gori.h" -#include "ssa-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 gori_compute -{ -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_phi (irange &r, gphi *phi); - bool range_of_call (irange &r, gcall *call); - bool range_of_cond_expr (irange &r, gassign* cond); -private: - void range_of_ubsan_call (irange &r, gcall *call, tree_code code); -}; - - -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); - - 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); -private: - 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); - - ssa_global_cache m_globals; - block_range_cache m_on_entry; - non_null_ref m_non_null; - vec m_workback; - vec 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 bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE); -private: - void adjust_phi_with_loop_info (irange &r, gphi *phi); - - 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 global_ranger super; // Inherited from class for easy changing. - 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_SSA_RANGE_H diff --git a/gcc/vr-values.c b/gcc/vr-values.c index f001aa4..eab4cb4 100644 --- a/gcc/vr-values.c +++ b/gcc/vr-values.c @@ -50,7 +50,7 @@ along with GCC; see the file COPYING3. If not see #include "vr-values.h" #include "cfghooks.h" #include "range-op.h" -#include "gimple-range.h" +#include "gimple-range-stmt.h" /* Set value range VR to a non-negative range of type TYPE. */ -- cgit v1.1