From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id 34DDA3857C6D; Tue, 6 Oct 2020 16:49:31 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 34DDA3857C6D Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Andrew Macleod To: gcc-cvs@gcc.gnu.org Subject: [gcc r11-3684] Ranger classes. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: 1644d7f4c1c4f99231d7de5e35fa7ce2d2e2c4c6 X-Git-Newrev: 90e88fd376bb9ad6223a1f5ccd803d1bd9539b05 Message-Id: <20201006164931.34DDA3857C6D@sourceware.org> Date: Tue, 6 Oct 2020 16:49:31 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 06 Oct 2020 16:49:31 -0000 https://gcc.gnu.org/g:90e88fd376bb9ad6223a1f5ccd803d1bd9539b05 commit r11-3684-g90e88fd376bb9ad6223a1f5ccd803d1bd9539b05 Author: Andrew MacLeod Date: Tue Oct 6 12:12:53 2020 -0400 Ranger classes. Add the 8 ranger files and the Makefile changes to build it. 2020-10-06 Andrew MacLeod * Makefile.in (OBJS): Add gimple-range*.o. * gimple-range.h: New file. * gimple-range.cc: New file. * gimple-range-cache.h: New file. * gimple-range-cache.cc: New file. * gimple-range-edge.h: New file. * gimple-range-edge.cc: New file. * gimple-range-gori.h: New file. * gimple-range-gori.cc: New file. Diff: --- gcc/Makefile.in | 4 + gcc/gimple-range-cache.cc | 877 ++++++++++++++++++++++++++++++ gcc/gimple-range-cache.h | 120 ++++ gcc/gimple-range-edge.cc | 197 +++++++ gcc/gimple-range-edge.h | 55 ++ gcc/gimple-range-gori.cc | 1321 +++++++++++++++++++++++++++++++++++++++++++++ gcc/gimple-range-gori.h | 138 +++++ gcc/gimple-range.cc | 1284 +++++++++++++++++++++++++++++++++++++++++++ gcc/gimple-range.h | 170 ++++++ 9 files changed, 4166 insertions(+) diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 50d6c83eb76..5a8fb0d7612 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1369,6 +1369,10 @@ OBJS = \ gimple-loop-versioning.o \ gimple-low.o \ gimple-pretty-print.o \ + gimple-range.o \ + gimple-range-cache.o \ + gimple-range-edge.o \ + gimple-range-gori.o \ gimple-ssa-backprop.o \ gimple-ssa-evrp.o \ gimple-ssa-evrp-analyze.o \ diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc new file mode 100644 index 00000000000..13b9933cc01 --- /dev/null +++ b/gcc/gimple-range-cache.cc @@ -0,0 +1,877 @@ +/* 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.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); + bitmap_obstack_initialize (&m_bitmaps); +} + +// Free any bitmaps which were allocated,a swell as the vector itself. + +non_null_ref::~non_null_ref () +{ + bitmap_obstack_release (&m_bitmaps); + m_nn.release (); +} + +// 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 (&m_bitmaps); + + // 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 doesn't 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, irange_allocator *allocator); + ~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 *m_type_range; + tree m_type; + irange_allocator *m_irange_allocator; +}; + + +// Initialize a block cache for an ssa_name of type T. + +ssa_block_ranges::ssa_block_ranges (tree t, irange_allocator *allocator) +{ + gcc_checking_assert (TYPE_P (t)); + m_type = t; + m_irange_allocator = allocator; + + m_tab.create (0); + m_tab.safe_grow_cleared (last_basic_block_for_fn (cfun)); + + // Create the cached type range. + m_type_range = m_irange_allocator->allocate (2); + m_type_range->set_varying (t); + + 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 *m = m_irange_allocator->allocate (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 *m = m_tab[bb->index]; + if (m) + { + r = *m; + return true; + } + return false; +} + +// Return 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; + int_range_max 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); + m_irange_allocator = new irange_allocator; +} + +// 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]; + } + delete m_irange_allocator; + // 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), m_irange_allocator); + + 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) +{ + 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) +{ + return get_block_ranges (name).set_bb_varying (bb); +} + +// Return the range for NAME on entry to BB in R. Return true if there +// is one. + +bool +block_range_cache::get_bb_range (irange &r, tree name, const basic_block bb) +{ + 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) +{ + 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; + int_range_max 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); + m_irange_allocator = new irange_allocator; +} + +// Deconstruct a global cache. + +ssa_global_cache::~ssa_global_cache () +{ + m_tab.release (); + delete m_irange_allocator; +} + +// 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 *stow = m_tab[v]; + if (!stow) + return false; + r = *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 *m = m_tab[v]; + if (m && m->fits_p (r)) + *m = r; + else + m_tab[v] = m_irange_allocator->allocate (r); +} + +// 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 *)); +} + +// Dump the contents of the global cache to F. + +void +ssa_global_cache::dump (FILE *f) +{ + unsigned x; + int_range_max 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); +} + +// -------------------------------------------------------------------------- + +ranger_cache::ranger_cache (range_query &q) : query (q) +{ + 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); + m_poor_value_list.create (0); + m_poor_value_list.safe_grow_cleared (20); + m_poor_value_list.truncate (0); +} + +ranger_cache::~ranger_cache () +{ + m_poor_value_list.release (); + m_workback.release (); + m_update_list.release (); +} + +// Push a request for a new lookup in block BB of name. Return true if +// the request is actually made (ie, isn't a duplicate). + +bool +ranger_cache::push_poor_value (basic_block bb, tree name) +{ + if (m_poor_value_list.length ()) + { + // Don't push anything else to the same block. If there are multiple + // things required, another request will come during a later evaluation + // and this prevents oscillation building uneccessary depth. + if ((m_poor_value_list.last ()).bb == bb) + return false; + } + + struct update_record rec; + rec.bb = bb; + rec.calc = name; + m_poor_value_list.safe_push (rec); + return true; +} + +// Provide lookup for the gori-computes class to access the best known range +// of an ssa_name in any given basic block. Note, this does no additonal +// lookups, just accesses the data that is already known. + +void +ranger_cache::ssa_range_in_bb (irange &r, tree name, basic_block bb) +{ + gimple *s = SSA_NAME_DEF_STMT (name); + basic_block def_bb = ((s && gimple_bb (s)) ? gimple_bb (s) : + ENTRY_BLOCK_PTR_FOR_FN (cfun)); + if (bb == def_bb) + { + // NAME is defined in this block, so request its current value + if (!m_globals.get_global_range (r, name)) + { + // If it doesn't have a value calculated, it means it's a + // "poor" value being used in some calculation. Queue it up + // as a poor value to be improved later. + r = gimple_range_global (name); + if (push_poor_value (bb, name)) + { + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, + "*CACHE* no global def in bb %d for ", bb->index); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " depth : %d\n", + m_poor_value_list.length ()); + } + } + } + } + // Look for the on-entry value of name in BB from the cache. + else if (!m_on_entry.get_bb_range (r, name, bb)) + { + // If it has no entry then mark this as a poor value. + if (push_poor_value (bb, name)) + { + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, + "*CACHE* no on entry range in bb %d for ", bb->index); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " depth : %d\n", m_poor_value_list.length ()); + } + } + // Try to pick up any known global value as a best guess for now. + if (!m_globals.get_global_range (r, name)) + r = gimple_range_global (name); + } + + // Check if pointers have any non-null dereferences. Non-call + // exceptions mean we could throw in the middle of the block, so just + // punt for now on those. + if (r.varying_p () && m_non_null.non_null_deref_p (name, bb) && + !cfun->can_throw_non_call_exceptions) + r = range_nonzero (TREE_TYPE (name)); +} + +// Return a static range for NAME on entry to basic block BB in R. If +// calc is true, fill any cache entries required between BB and the +// def block for NAME. Otherwise, return false if the cache is empty. + +bool +ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc) +{ + gcc_checking_assert (gimple_range_ssa_p (name)); + + if (calc) + { + gimple *def_stmt = SSA_NAME_DEF_STMT (name); + basic_block def_bb = NULL; + if (def_stmt) + def_bb = gimple_bb (def_stmt);; + if (!def_bb) + { + // If we get to the entry block, this better be a default def + // or range_on_entry was called for a block not dominated by + // the def. + 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 definition 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); +} + +// Add BB to the list of blocks to update, unless it's already in the list. + +void +ranger_cache::add_to_update (basic_block bb) +{ + if (!m_update_list.contains (bb)) + m_update_list.quick_push (bb); +} + +// If there is anything in the iterative update_list, continue +// processing NAME until the list of blocks is empty. + +void +ranger_cache::iterative_cache_update (tree name) +{ + basic_block bb; + edge_iterator ei; + edge e; + int_range_max new_range; + int_range_max current_range; + int_range_max e_range; + + // Process each block by seeing if its calculated range on entry is + // the same as its 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 (); + gcc_checking_assert (m_on_entry.bb_range_p (name, bb)); + 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) + { + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, " edge %d->%d :", e->src->index, bb->index); + // Get whatever range we can for this edge. + if (!outgoing_edge_range_p (e_range, e, name)) + { + ssa_range_in_bb (e_range, name, e->src); + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "No outgoing edge range, picked up "); + e_range.dump(dump_file); + fprintf (dump_file, "\n"); + } + } + else + { + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "outgoing range :"); + e_range.dump(dump_file); + fprintf (dump_file, "\n"); + } + } + new_range.union_ (e_range); + if (new_range.varying_p ()) + break; + } + + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "FWD visiting block %d for ", bb->index); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " starting range : "); + current_range.dump (dump_file); + fprintf (dump_file, "\n"); + } + + // If the range on entry has changed, update it. + if (new_range != current_range) + { + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, " Updating range to "); + new_range.dump (dump_file); + fprintf (dump_file, "\n Updating blocks :"); + } + m_on_entry.set_bb_range (name, bb, new_range); + // Mark each successor that has a range to re-check its range + FOR_EACH_EDGE (e, ei, bb->succs) + if (m_on_entry.bb_range_p (name, e->dest)) + { + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, " bb%d",e->dest->index); + add_to_update (e->dest); + } + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "\n"); + } + } + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "DONE visiting blocks for "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, "\n"); + } +} + +// Make sure that the range-on-entry cache for NAME is set for block BB. +// Work back through the CFG to DEF_BB ensuring the range is calculated +// on the block/edges leading back to that point. + +void +ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) +{ + edge_iterator ei; + edge e; + int_range_max block_result; + int_range_max undefined; + unsigned poor_list_start = m_poor_value_list.length (); + + // At this point we shouldn't 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_RANGE_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_RANGE_CACHE) + { + fprintf (dump_file, "BACK visiting block %d for ", node->index); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, "\n"); + } + + FOR_EACH_EDGE (e, ei, node->preds) + { + basic_block pred = e->src; + int_range_max r; + + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, " %d->%d ",e->src->index, e->dest->index); + + // 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)) + { + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "entry: bail."); + continue; + } + + // Regardless of whether 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)) + { + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "nonnull: update "); + 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 (DEBUG_RANGE_CACHE) + fprintf (dump_file, "has cache, "); + if (!r.undefined_p () || has_edge_range_p (e, name)) + { + add_to_update (node); + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "update. "); + } + continue; + } + + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "pushing undefined pred block. "); + // 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); + } + } + + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "\n"); + + // Now fill in the marked blocks with values. + iterative_cache_update (name); + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, " iterative update done.\n"); + + // Now that the cache has been updated, check to see if there were any + // SSA_NAMES used in filling the cache which were "poor values". + // We can evaluate them, and inject any new values into the iteration + // list, and see if it improves any on-entry values. + if (poor_list_start != m_poor_value_list.length ()) + { + gcc_checking_assert (poor_list_start < m_poor_value_list.length ()); + while (poor_list_start < m_poor_value_list.length ()) + { + // Find a range for this unresolved value. + // Note, this may spawn new cache filling cycles, but by the time it + // is finished, the work vectors will all be back to the same state + // as before the call. The update record vector will always be + // returned to the current state upon return. + struct update_record rec = m_poor_value_list.pop (); + basic_block calc_bb = rec.bb; + int_range_max tmp; + + // The update work list should be empty at this point. + gcc_checking_assert (m_update_list.length () == 0); + + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "(%d:%d)Calculating ", + m_poor_value_list.length () + 1, poor_list_start); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " used poor value for "); + print_generic_expr (dump_file, rec.calc, TDF_SLIM); + fprintf (dump_file, " in bb%d, trying to improve:\n", + calc_bb->index); + } + + // It must have at least one edge, pick edge 0. we just want to + // calculate a range at the exit from the block so the caches feeding + // this block will be filled up. + gcc_checking_assert (EDGE_SUCC (calc_bb, 0)); + query.range_on_edge (tmp, EDGE_SUCC (calc_bb, 0), rec.calc); + + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, " Checking successors of bb%d :", + calc_bb->index); + + // Try recalculating any successor blocks with the new value. + // Note that even if this value is refined from the initial value, + // it may not affect the calculation, but the iterative update + // will resolve that efficently. + FOR_EACH_EDGE (e, ei, calc_bb->succs) + { + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "bb%d: ", e->dest->index); + // Only update active cache entries. + if (m_on_entry.bb_range_p (name, e->dest)) + { + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "update "); + add_to_update (e->dest); + } + } + if (DEBUG_RANGE_CACHE) + fprintf (dump_file, "\n"); + // Now see if there is a new value. + iterative_cache_update (name); + } + } + +} diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h new file mode 100644 index 00000000000..29ab01e2a98 --- /dev/null +++ b/gcc/gimple-range-cache.h @@ -0,0 +1,120 @@ +/* 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 + +#include "gimple-range-gori.h" + +// 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 in that 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); + bitmap_obstack m_bitmaps; +}; + +// This class manages a vector of pointers to ssa_block ranges. It +// provides the basis for the "range on entry" cache for all +// SSA names. + +class block_range_cache +{ +public: + block_range_cache (); + ~block_range_cache (); + + 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); + irange_allocator *m_irange_allocator; +}; + +// 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. + +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 irange_allocator *m_irange_allocator; +}; + +// This class provides all the caches a global ranger may need, and makes +// them available for gori-computes to query so outgoing edges can be +// properly calculated. + +class ranger_cache : public gori_compute_cache +{ +public: + ranger_cache (class range_query &q); + ~ranger_cache (); + + virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb); + bool block_range (irange &r, basic_block bb, tree name, bool calc = true); + + ssa_global_cache m_globals; + block_range_cache m_on_entry; + non_null_ref m_non_null; +private: + void add_to_update (basic_block bb); + void fill_block_cache (tree name, basic_block bb, basic_block def_bb); + void iterative_cache_update (tree name); + + vec m_workback; + vec m_update_list; + + // Iterative "poor value" calculations. + struct update_record + { + basic_block bb; // Block which value needs to be calculated in. + tree calc; // SSA_NAME which needs its value calculated. + }; + bool push_poor_value (basic_block bb, tree name); + vec m_poor_value_list; + class range_query &query; +}; + +#endif // GCC_SSA_RANGE_CACHE_H diff --git a/gcc/gimple-range-edge.cc b/gcc/gimple-range-edge.cc new file mode 100644 index 00000000000..c5ee54fec51 --- /dev/null +++ b/gcc/gimple-range-edge.cc @@ -0,0 +1,197 @@ +/* Gimple range edge functionaluity. + Copyright (C) 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 "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "gimple-range.h" + +// If there is a range control statment at the end of block BB, return it. +// Otherwise return NULL. + +gimple * +gimple_outgoing_range_stmt_p (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) && gimple_range_handler (s)) + return gsi_stmt (gsi); + gswitch *sw = dyn_cast (s); + if (sw && irange::supports_type_p (TREE_TYPE (gimple_switch_index (sw)))) + return gsi_stmt (gsi); + } + return NULL; +} + + +outgoing_range::outgoing_range () +{ + m_edge_table = NULL; +} + +outgoing_range::~outgoing_range () +{ + if (m_edge_table) + delete m_edge_table; +} + + +// Get a range for a switch edge E from statement S and return it in R. +// Use a cached value if it exists, or calculate it if not. + +bool +outgoing_range::get_edge_range (irange &r, gimple *s, edge e) +{ + gcc_checking_assert (is_a (s)); + gswitch *sw = as_a (s); + + // ADA currently has 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 switches where the labels dont match the argument. + if (gimple_switch_num_labels (sw) > 1 && + TYPE_PRECISION (TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)))) != + TYPE_PRECISION (TREE_TYPE (gimple_switch_index (sw)))) + return false; + + if (!m_edge_table) + m_edge_table = new hash_map (n_edges_for_fn (cfun)); + + irange **val = m_edge_table->get (e); + if (!val) + { + calc_switch_ranges (sw); + val = m_edge_table->get (e); + gcc_checking_assert (val); + } + r = **val; + return true; +} + + +// Calculate all switch edges from SW and cache them in the hash table. + +void +outgoing_range::calc_switch_ranges (gswitch *sw) +{ + bool existed; + unsigned x, lim; + lim = gimple_switch_num_labels (sw); + tree type = TREE_TYPE (gimple_switch_index (sw)); + + edge default_edge = gimple_switch_default_edge (cfun, sw); + irange *&default_slot = m_edge_table->get_or_insert (default_edge, &existed); + + // This should be the first call into this switch. For the default + // range case, start with varying and intersect each other case from + // it. + + gcc_checking_assert (!existed); + + // Allocate an int_range_max for default case. + default_slot = m_range_allocator.allocate (255); + default_slot->set_varying (type); + + for (x = 1; x < lim; x++) + { + edge e = gimple_switch_edge (cfun, sw, x); + + // If this edge is the same as the default edge, do nothing else. + if (e == default_edge) + continue; + + tree low = CASE_LOW (gimple_switch_label (sw, x)); + tree high = CASE_HIGH (gimple_switch_label (sw, x)); + if (!high) + high = low; + + // Remove the case range from the default case. + int_range_max def_range (low, high); + range_cast (def_range, type); + def_range.invert (); + default_slot->intersect (def_range); + + // Create/union this case with anything on else on the edge. + int_range_max case_range (low, high); + range_cast (case_range, type); + irange *&slot = m_edge_table->get_or_insert (e, &existed); + if (existed) + { + case_range.union_ (*slot); + if (slot->fits_p (case_range)) + { + *slot = case_range; + continue; + } + } + // If there was an existing range and it doesn't fit, we lose the memory. + // It'll get reclaimed when the obstack is freed. This seems less + // intrusive than allocating max ranges for each case. + slot = m_range_allocator.allocate (case_range); + } +} + + +// 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 * +outgoing_range::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<2> (boolean_true_node, boolean_true_node); + else if (e->flags & EDGE_FALSE_VALUE) + r = int_range<2> (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; + + if (get_edge_range (r, sw, e)) + return s; + + return NULL; +} diff --git a/gcc/gimple-range-edge.h b/gcc/gimple-range-edge.h new file mode 100644 index 00000000000..400c814ac7e --- /dev/null +++ b/gcc/gimple-range-edge.h @@ -0,0 +1,55 @@ +/* Gimple range edge header file. + Copyright (C) 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 GIMPLE_RANGE_EDGE_H +#define GIMPLE_RANGE_EDGE_H + +// This class is used to query ranges on constant edges in GIMPLE. +// +// For a COND_EXPR, the TRUE edge will return [1,1] and the false edge a [0,0]. +// +// For SWITCH_EXPR, it is awkward to calculate ranges. When a request +// is made, the entire switch is evalauted and the results cached. +// Any future requests to that switch will use the cached value, providing +// dramatic decrease in computation time. +// +// The API is simple, just ask for the range on the edge. +// The return value is NULL for no range, or the branch statement which the +// edge gets the range from, along with the range. + +class outgoing_range +{ +public: + outgoing_range (); + ~outgoing_range (); + gimple *edge_range_p (irange &r, edge e); +private: + void calc_switch_ranges (gswitch *sw); + bool get_edge_range (irange &r, gimple *s, edge e); + + hash_map *m_edge_table; + irange_allocator m_range_allocator; +}; + +// If there is a range control statment at the end of block BB, return it. +gimple *gimple_outgoing_range_stmt_p (basic_block bb); + +#endif // GIMPLE_RANGE_EDGE_H diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc new file mode 100644 index 00000000000..eaf1a445c25 --- /dev/null +++ b/gcc/gimple-range-gori.cc @@ -0,0 +1,1321 @@ +/* Gimple range GORI functions. + 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 "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "gimple-range.h" + + +/* RANGE_DEF_CHAIN is used to determine what SSA names in a block can + have range information calculated for them, and what the + dependencies on each other are. + + Information for a basic block is calculated once and stored. It is + only calculated the first time a query is made, so if no queries + are made, there is little overhead. + + The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set + within this bitmap to indicate SSA names that are defined in the + SAME block and used to calculate this SSA name. + + + : + _1 = x_4(D) + -2; + _2 = _1 * 4; + j_7 = foo (); + q_5 = _2 + 3; + if (q_5 <= 13) + + _1 : x_4(D) + _2 : 1 x_4(D) + q_5 : _1 _2 x_4(D) + + This dump indicates the bits set in the def_chain vector. + as well as demonstrates the def_chain bits for the related ssa_names. + + Checking the chain for _2 indicates that _1 and x_4 are used in + its evaluation. + + Def chains also only include statements which are valid gimple + so a def chain will only span statements for which the range + engine implements operations for. */ + + +class range_def_chain +{ +public: + range_def_chain (); + ~range_def_chain (); + bool has_def_chain (tree name); + bitmap get_def_chain (tree name); + bool in_chain_p (tree name, tree def); +private: + vec m_def_chain; // SSA_NAME : def chain components. + void build_def_chain (tree name, bitmap result, basic_block bb); +}; + + +// Construct a range_def_chain. + +range_def_chain::range_def_chain () +{ + m_def_chain.create (0); + m_def_chain.safe_grow_cleared (num_ssa_names); +} + +// Destruct a range_def_chain. + +range_def_chain::~range_def_chain () +{ + unsigned x; + for (x = 0; x < m_def_chain.length (); ++x) + if (m_def_chain[x]) + BITMAP_FREE (m_def_chain[x]); + m_def_chain.release (); +} + +// Return true if NAME is in the def chain of DEF. If BB is provided, +// only return true if the defining statement of DEF is in BB. + +bool +range_def_chain::in_chain_p (tree name, tree def) +{ + gcc_checking_assert (gimple_range_ssa_p (def)); + gcc_checking_assert (gimple_range_ssa_p (name)); + + // Get the defintion chain for DEF. + bitmap chain = get_def_chain (def); + + if (chain == NULL) + return false; + return bitmap_bit_p (chain, SSA_NAME_VERSION (name)); +} + +// Build def_chains for NAME if it is in BB. Copy the def chain into RESULT. + +void +range_def_chain::build_def_chain (tree name, bitmap result, basic_block bb) +{ + bitmap b; + gimple *def_stmt = SSA_NAME_DEF_STMT (name); + // Add this operand into the result. + bitmap_set_bit (result, SSA_NAME_VERSION (name)); + + if (gimple_bb (def_stmt) == bb && !is_a(def_stmt)) + { + // Get the def chain for the operand. + b = get_def_chain (name); + // If there was one, copy it into result. + if (b) + bitmap_ior_into (result, b); + } +} + +// Return TRUE if NAME has been processed for a def_chain. + +inline bool +range_def_chain::has_def_chain (tree name) +{ + // Ensure there is an entry in the internal vector. + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_def_chain.length ()) + m_def_chain.safe_grow_cleared (num_ssa_names + 1); + return (m_def_chain[v] != NULL); +} + +// Calculate the def chain for NAME and all of its dependent +// operands. Only using names in the same BB. Return the bitmap of +// all names in the m_def_chain. This only works for supported range +// statements. + +bitmap +range_def_chain::get_def_chain (tree name) +{ + tree ssa1, ssa2, ssa3; + unsigned v = SSA_NAME_VERSION (name); + + // If it has already been processed, just return the cached value. + if (has_def_chain (name)) + return m_def_chain[v]; + + // No definition chain for default defs. + if (SSA_NAME_IS_DEFAULT_DEF (name)) + return NULL; + + gimple *stmt = SSA_NAME_DEF_STMT (name); + if (gimple_range_handler (stmt)) + { + ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); + ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); + ssa3 = NULL_TREE; + } + else if (is_a (stmt) + && gimple_assign_rhs_code (stmt) == COND_EXPR) + { + gassign *st = as_a (stmt); + ssa1 = gimple_range_ssa_p (gimple_assign_rhs1 (st)); + ssa2 = gimple_range_ssa_p (gimple_assign_rhs2 (st)); + ssa3 = gimple_range_ssa_p (gimple_assign_rhs3 (st)); + } + else + return NULL; + + basic_block bb = gimple_bb (stmt); + + m_def_chain[v] = BITMAP_ALLOC (NULL); + + if (ssa1) + build_def_chain (ssa1, m_def_chain[v], bb); + if (ssa2) + build_def_chain (ssa2, m_def_chain[v], bb); + if (ssa3) + build_def_chain (ssa3, m_def_chain[v], bb); + + // If we run into pathological cases where the defintion chains are + // huge (ie huge basic block fully unrolled) we might be able to limit + // this by deciding here that if some criteria is satisfied, we change the + // def_chain back to be just the ssa-names. That will help prevent chains + // of a_2 = b_6 + a_8 from creating a pathological case. + return m_def_chain[v]; +} + +// ------------------------------------------------------------------- + +/* GORI_MAP is used to accumulate what SSA names in a block can + generate range information, and provides tools for the block ranger + to enable it to efficiently calculate these ranges. + + GORI stands for "Generates Outgoing Range Information." + + It utilizes the range_def_chain class to contruct def_chains. + Information for a basic block is calculated once and stored. It is + only calculated the first time a query is made. If no queries are + made, there is little overhead. + + one bitmap is maintained for each basic block: + m_outgoing : a set bit indicates a range can be generated for a name. + + Generally speaking, the m_outgoing vector is the union of the + entire def_chain of all SSA names used in the last statement of the + block which generate ranges. */ + +class gori_map : public range_def_chain +{ +public: + gori_map (); + ~gori_map (); + + bool is_export_p (tree name, basic_block bb); + bool def_chain_in_export_p (tree name, basic_block bb); + + void dump (FILE *f); + void dump (FILE *f, basic_block bb); +private: + bitmap_obstack m_bitmaps; + vec m_outgoing; // BB: Outgoing ranges calculatable on edges + void maybe_add_gori (tree name, basic_block bb); + void calculate_gori (basic_block bb); + bitmap exports (basic_block bb); +}; + + +// Initialize a gori-map structure. + +gori_map::gori_map () +{ + m_outgoing.create (0); + m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); + bitmap_obstack_initialize (&m_bitmaps); +} + +// Free any memory the GORI map allocated. + +gori_map::~gori_map () +{ + bitmap_obstack_release (&m_bitmaps); + m_outgoing.release (); +} + +// Return the bitmap vector of all export from BB. Calculate if necessary. + +bitmap +gori_map::exports (basic_block bb) +{ + if (!m_outgoing[bb->index]) + calculate_gori (bb); + return m_outgoing[bb->index]; +} + +// Return true if NAME is can have ranges generated for it from basic +// block BB. + +bool +gori_map::is_export_p (tree name, basic_block bb) +{ + return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name)); +} + +// Return true if any element in the def chain of NAME is in the +// export list for BB. + +bool +gori_map::def_chain_in_export_p (tree name, basic_block bb) +{ + bitmap a = exports (bb); + bitmap b = get_def_chain (name); + if (a && b) + return bitmap_intersect_p (a, b); + return false; +} + +// If NAME is non-NULL and defined in block BB, calculate the def +// chain and add it to m_outgoing. + +void +gori_map::maybe_add_gori (tree name, basic_block bb) +{ + if (name) + { + gimple *s = SSA_NAME_DEF_STMT (name); + bitmap r = get_def_chain (name); + // Check if there is a def chain, and it is in this block. + if (r && gimple_bb (s) == bb) + bitmap_copy (m_outgoing[bb->index], r); + // Def chain doesn't include itself, and even if there isn't a + // def chain, this name should be added to exports. + bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name)); + } +} + +// Calculate all the required information for BB. + +void +gori_map::calculate_gori (basic_block bb) +{ + tree name; + if (bb->index >= (signed int)m_outgoing.length ()) + m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); + gcc_checking_assert (m_outgoing[bb->index] == NULL); + m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps); + + // If this block's last statement may generate range informaiton, go + // calculate it. + gimple *stmt = gimple_outgoing_range_stmt_p (bb); + if (!stmt) + return; + if (is_a (stmt)) + { + gcond *gc = as_a(stmt); + name = gimple_range_ssa_p (gimple_cond_lhs (gc)); + maybe_add_gori (name, gimple_bb (stmt)); + + name = gimple_range_ssa_p (gimple_cond_rhs (gc)); + maybe_add_gori (name, gimple_bb (stmt)); + } + else + { + gswitch *gs = as_a(stmt); + name = gimple_range_ssa_p (gimple_switch_index (gs)); + maybe_add_gori (name, gimple_bb (stmt)); + } +} + +// Dump the table information for BB to file F. + +void +gori_map::dump (FILE *f, basic_block bb) +{ + bool header = false; + const char *header_string = "bb%-4d "; + const char *header2 = " "; + bool printed_something = false;; + unsigned x, y; + bitmap_iterator bi; + + // BB was not processed. + if (!m_outgoing[bb->index]) + return; + + // Dump the def chain for each SSA_NAME defined in BB. + for (x = 1; x < num_ssa_names; x++) + { + tree name = ssa_name (x); + if (!name) + continue; + gimple *stmt = SSA_NAME_DEF_STMT (name); + bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL); + if (stmt && gimple_bb (stmt) == bb && chain && !bitmap_empty_p (chain)) + { + fprintf (f, header_string, bb->index); + header_string = header2; + header = true; + print_generic_expr (f, name, TDF_SLIM); + fprintf (f, " : "); + EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi) + { + print_generic_expr (f, ssa_name (y), TDF_SLIM); + fprintf (f, " "); + } + fprintf (f, "\n"); + } + } + + printed_something |= header; + + // Now dump the export vector. + header = false; + EXECUTE_IF_SET_IN_BITMAP (m_outgoing[bb->index], 0, y, bi) + { + if (!header) + { + fprintf (f, header_string, bb->index); + fprintf (f, "exports: "); + header_string = header2; + header = true; + } + print_generic_expr (f, ssa_name (y), TDF_SLIM); + fprintf (f, " "); + } + if (header) + fputc ('\n', f); + + printed_something |= header; + if (printed_something) + fprintf (f, "\n"); +} + +// Dump the entire GORI map structure to file F. + +void +gori_map::dump (FILE *f) +{ + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + dump (f, bb); + if (m_outgoing[bb->index]) + fprintf (f, "\n"); + } +} + +DEBUG_FUNCTION void +debug (gori_map &g) +{ + g.dump (stderr); +} + +// ------------------------------------------------------------------- + +// Construct a gori_compute object. + +gori_compute::gori_compute () +{ + // Create a boolean_type true and false range. + m_bool_zero = int_range<2> (boolean_false_node, boolean_false_node); + m_bool_one = int_range<2> (boolean_true_node, boolean_true_node); + m_gori_map = new gori_map; +} + +// Destruct a gori_compute_object. + +gori_compute::~gori_compute () +{ + delete m_gori_map; +} + +// Provide a default of VARYING for all incoming SSA names. + +void +gori_compute::ssa_range_in_bb (irange &r, tree name, basic_block) +{ + r.set_varying (TREE_TYPE (name)); +} + +void +gori_compute::expr_range_in_bb (irange &r, tree expr, basic_block bb) +{ + if (gimple_range_ssa_p (expr)) + ssa_range_in_bb (r, expr, bb); + else + get_tree_range (r, expr); +} + +// Calculate the range for NAME if the lhs of statement S has the +// range LHS. Return the result in R. Return false if no range can be +// calculated. + +bool +gori_compute::compute_name_range_op (irange &r, gimple *stmt, + const irange &lhs, tree name) +{ + int_range_max op1_range, op2_range; + + tree op1 = gimple_range_operand1 (stmt); + tree op2 = gimple_range_operand2 (stmt); + + // Operand 1 is the name being looked for, evaluate it. + if (op1 == name) + { + expr_range_in_bb (op1_range, op1, gimple_bb (stmt)); + if (!op2) + { + // The second parameter to a unary operation is the range + // for the type of operand1, but if it can be reduced + // further, the results will be better. Start with what we + // know of the range of OP1 instead of the full type. + return gimple_range_calc_op1 (r, stmt, lhs, op1_range); + } + // If we need the second operand, get a value and evaluate. + expr_range_in_bb (op2_range, op2, gimple_bb (stmt)); + if (gimple_range_calc_op1 (r, stmt, lhs, op2_range)) + r.intersect (op1_range); + else + r = op1_range; + return true; + } + + if (op2 == name) + { + expr_range_in_bb (op1_range, op1, gimple_bb (stmt)); + expr_range_in_bb (r, op2, gimple_bb (stmt)); + if (gimple_range_calc_op2 (op2_range, stmt, lhs, op1_range)) + r.intersect (op2_range); + return true; + } + return false; +} + +// Given the switch S, return an evaluation in R for NAME when the lhs +// evaluates to LHS. Returning false means the name being looked for +// was not resolvable. + +bool +gori_compute::compute_operand_range_switch (irange &r, gswitch *s, + const irange &lhs, + tree name) +{ + tree op1 = gimple_switch_index (s); + + // If name matches, the range is simply the range from the edge. + // Empty ranges are viral as they are on a path which isn't + // executable. + if (op1 == name || lhs.undefined_p ()) + { + r = lhs; + return true; + } + + // If op1 is in the defintion chain, pass lhs back. + if (gimple_range_ssa_p (op1) && m_gori_map->in_chain_p (name, op1)) + return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name); + + return false; +} + +// Return TRUE if GS is a logical && or || expression. + +static inline bool +is_gimple_logical_p (const gimple *gs) +{ + // Look for boolean and/or condition. + if (gimple_code (gs) == GIMPLE_ASSIGN) + switch (gimple_expr_code (gs)) + { + case TRUTH_AND_EXPR: + case TRUTH_OR_EXPR: + return true; + + case BIT_AND_EXPR: + case BIT_IOR_EXPR: + // Bitwise operations on single bits are logical too. + if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)), + boolean_type_node)) + return true; + break; + + default: + break; + } + return false; +} + +// Return an evaluation for NAME as it would appear in STMT when the +// statement's lhs evaluates to LHS. If successful, return TRUE and +// store the evaluation in R, otherwise return FALSE. + +bool +gori_compute::compute_operand_range (irange &r, gimple *stmt, + const irange &lhs, tree name) +{ + // Empty ranges are viral as they are on an unexecutable path. + if (lhs.undefined_p ()) + { + r.set_undefined (); + return true; + } + if (is_a (stmt)) + return compute_operand_range_switch (r, as_a (stmt), lhs, name); + if (!gimple_range_handler (stmt)) + return false; + + tree op1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); + tree op2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); + + // The base ranger handles NAME on this statement. + if (op1 == name || op2 == name) + return compute_name_range_op (r, stmt, lhs, name); + + if (is_gimple_logical_p (stmt)) + return compute_logical_operands (r, stmt, lhs, name); + + // NAME is not in this stmt, but one of the names in it ought to be + // derived from it. + bool op1_in_chain = op1 && m_gori_map->in_chain_p (name, op1); + bool op2_in_chain = op2 && m_gori_map->in_chain_p (name, op2); + if (op1_in_chain && op2_in_chain) + return compute_operand1_and_operand2_range (r, stmt, lhs, name); + if (op1_in_chain) + return compute_operand1_range (r, stmt, lhs, name); + if (op2_in_chain) + return compute_operand2_range (r, stmt, lhs, name); + + // If neither operand is derived, this statement tells us nothing. + return false; +} + +// Return TRUE if range R is either a true or false compatible range. + +static bool +range_is_either_true_or_false (const irange &r) +{ + if (r.undefined_p ()) + return false; + + // This is complicated by the fact that Ada has multi-bit booleans, + // so true can be ~[0, 0] (i.e. [1,MAX]). + tree type = r.type (); + gcc_checking_assert (types_compatible_p (type, boolean_type_node)); + return (r.singleton_p () || !r.contains_p (build_zero_cst (type))); +} + +// A pair of ranges for true/false paths. + +struct tf_range +{ + tf_range () { } + tf_range (const irange &t_range, const irange &f_range) + { + true_range = t_range; + false_range = f_range; + } + int_range_max true_range, false_range; +}; + +// Evaluate a binary logical expression by combining the true and +// false ranges for each of the operands based on the result value in +// the LHS. + +bool +gori_compute::logical_combine (irange &r, enum tree_code code, + const irange &lhs, + const tf_range &op1, const tf_range &op2) +{ + if (op1.true_range.varying_p () + && op1.false_range.varying_p () + && op2.true_range.varying_p () + && op2.false_range.varying_p ()) + return false; + + // This is not a simple fold of a logical expression, rather it + // determines ranges which flow through the logical expression. + // + // Assuming x_8 is an unsigned char, and relational statements: + // b_1 = x_8 < 20 + // b_2 = x_8 > 5 + // consider the logical expression and branch: + // c_2 = b_1 && b_2 + // if (c_2) + // + // To determine the range of x_8 on either edge of the branch, one + // must first determine what the range of x_8 is when the boolean + // values of b_1 and b_2 are both true and false. + // b_1 TRUE x_8 = [0, 19] + // b_1 FALSE x_8 = [20, 255] + // b_2 TRUE x_8 = [6, 255] + // b_2 FALSE x_8 = [0,5]. + // + // These ranges are then combined based on the expected outcome of + // the branch. The range on the TRUE side of the branch must satisfy + // b_1 == true && b_2 == true + // + // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255] + // must be true. The range of x_8 on the true side must be the + // intersection of both ranges since both must be true. Thus the + // range of x_8 on the true side is [6, 19]. + // + // To determine the ranges on the FALSE side, all 3 combinations of + // failing ranges must be considered, and combined as any of them + // can cause the false result. + // + // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and + // FALSE results and combine them. If we fell back to VARYING any + // range restrictions that have been discovered up to this point + // would be lost. + if (!range_is_either_true_or_false (lhs)) + { + int_range_max r1; + if (logical_combine (r1, code, m_bool_zero, op1, op2) + && logical_combine (r, code, m_bool_one, op1, op2)) + { + r.union_ (r1); + return true; + } + return false; + } + + switch (code) + { + // A logical AND combines ranges from 2 boolean conditions. + // c_2 = b_1 && b_2 + case TRUTH_AND_EXPR: + case BIT_AND_EXPR: + if (!lhs.zero_p ()) + { + // The TRUE side is the intersection of the the 2 true ranges. + r = op1.true_range; + r.intersect (op2.true_range); + } + else + { + // The FALSE side is the union of the other 3 cases. + int_range_max ff (op1.false_range); + ff.intersect (op2.false_range); + int_range_max tf (op1.true_range); + tf.intersect (op2.false_range); + int_range_max ft (op1.false_range); + ft.intersect (op2.true_range); + r = ff; + r.union_ (tf); + r.union_ (ft); + } + break; + // A logical OR combines ranges from 2 boolean conditons. + // c_2 = b_1 || b_2 + case TRUTH_OR_EXPR: + case BIT_IOR_EXPR: + if (lhs.zero_p ()) + { + // An OR operation will only take the FALSE path if both + // operands are false, so [20, 255] intersect [0, 5] is the + // union: [0,5][20,255]. + r = op1.false_range; + r.intersect (op2.false_range); + } + else + { + // The TRUE side of an OR operation will be the union of + // the other three combinations. + int_range_max tt (op1.true_range); + tt.intersect (op2.true_range); + int_range_max tf (op1.true_range); + tf.intersect (op2.false_range); + int_range_max ft (op1.false_range); + ft.intersect (op2.true_range); + r = tt; + r.union_ (tf); + r.union_ (ft); + } + break; + default: + gcc_unreachable (); + } + + return true; +} + +// Helper function for compute_logical_operands_in_chain that computes +// the range of logical statements that can be computed without +// chasing down operands. These are things like [0 = x | y] where we +// know neither operand can be non-zero, or [1 = x & y] where we know +// neither operand can be zero. + +bool +gori_compute::optimize_logical_operands (tf_range &range, + gimple *stmt, + const irange &lhs, + tree name, + tree op) +{ + enum tree_code code = gimple_expr_code (stmt); + + // Optimize [0 = x | y], since neither operand can ever be non-zero. + if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ()) + { + if (!compute_operand_range (range.false_range, SSA_NAME_DEF_STMT (op), + m_bool_zero, name)) + expr_range_in_bb (range.false_range, name, gimple_bb (stmt)); + range.true_range = range.false_range; + return true; + } + // Optimize [1 = x & y], since neither operand can ever be zero. + if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one) + { + if (!compute_operand_range (range.true_range, SSA_NAME_DEF_STMT (op), + m_bool_one, name)) + expr_range_in_bb (range.true_range, name, gimple_bb (stmt)); + range.false_range = range.true_range; + return true; + } + return false; +} + +// Given a logical STMT, calculate true and false ranges for each +// potential path of NAME, assuming NAME came through the OP chain if +// OP_IN_CHAIN is true. + +void +gori_compute::compute_logical_operands_in_chain (tf_range &range, + gimple *stmt, + const irange &lhs, + tree name, + tree op, bool op_in_chain) +{ + if (!op_in_chain) + { + // If op is not in chain, use its known value. + expr_range_in_bb (range.true_range, name, gimple_bb (stmt)); + range.false_range = range.true_range; + return; + } + if (optimize_logical_operands (range, stmt, lhs, name, op)) + return; + + // Calulate ranges for true and false on both sides, since the false + // path is not always a simple inversion of the true side. + if (!compute_operand_range (range.true_range, SSA_NAME_DEF_STMT (op), + m_bool_one, name)) + expr_range_in_bb (range.true_range, name, gimple_bb (stmt)); + if (!compute_operand_range (range.false_range, SSA_NAME_DEF_STMT (op), + m_bool_zero, name)) + expr_range_in_bb (range.false_range, name, gimple_bb (stmt)); +} + +// Given a logical STMT, calculate true and false for each potential +// path using NAME, and resolve the outcome based on the logical +// operator. + +bool +gori_compute::compute_logical_operands (irange &r, gimple *stmt, + const irange &lhs, + tree name) +{ + // Reaching this point means NAME is not in this stmt, but one of + // the names in it ought to be derived from it. + tree op1 = gimple_range_operand1 (stmt); + tree op2 = gimple_range_operand2 (stmt); + gcc_checking_assert (op1 != name && op2 != name); + + bool op1_in_chain = (gimple_range_ssa_p (op1) + && m_gori_map->in_chain_p (name, op1)); + bool op2_in_chain = (gimple_range_ssa_p (op2) + && m_gori_map->in_chain_p (name, op2)); + + // If neither operand is derived, then this stmt tells us nothing. + if (!op1_in_chain && !op2_in_chain) + return false; + + tf_range op1_range, op2_range; + compute_logical_operands_in_chain (op1_range, stmt, lhs, + name, op1, op1_in_chain); + compute_logical_operands_in_chain (op2_range, stmt, lhs, + name, op2, op2_in_chain); + return logical_combine (r, gimple_expr_code (stmt), lhs, + op1_range, op2_range); +} + +// Calculate a range for NAME from the operand 1 position of STMT +// assuming the result of the statement is LHS. Return the range in +// R, or false if no range could be calculated. + +bool +gori_compute::compute_operand1_range (irange &r, gimple *stmt, + const irange &lhs, tree name) +{ + int_range_max op1_range, op2_range; + tree op1 = gimple_range_operand1 (stmt); + tree op2 = gimple_range_operand2 (stmt); + + expr_range_in_bb (op1_range, op1, gimple_bb (stmt)); + + // Now calcuated the operand and put that result in r. + if (op2) + { + expr_range_in_bb (op2_range, op2, gimple_bb (stmt)); + if (!gimple_range_calc_op1 (r, stmt, lhs, op2_range)) + return false; + } + else + { + // We pass op1_range to the unary operation. Nomally it's a + // hidden range_for_type parameter, but sometimes having the + // actual range can result in better information. + if (!gimple_range_calc_op1 (r, stmt, lhs, op1_range)) + return false; + } + + // Intersect the calculated result with the known result. + op1_range.intersect (r); + + gimple *src_stmt = SSA_NAME_DEF_STMT (op1); + // If def stmt is outside of this BB, then name must be an import. + if (!src_stmt || (gimple_bb (src_stmt) != gimple_bb (stmt))) + { + // If this isn't the right import statement, then abort calculation. + if (!src_stmt || gimple_get_lhs (src_stmt) != name) + return false; + return compute_name_range_op (r, src_stmt, op1_range, name); + } + // Then feed this range back as the LHS of the defining statement. + return compute_operand_range (r, src_stmt, op1_range, name); +} + + +// Calculate a range for NAME from the operand 2 position of S +// assuming the result of the statement is LHS. Return the range in +// R, or false if no range could be calculated. + +bool +gori_compute::compute_operand2_range (irange &r, gimple *stmt, + const irange &lhs, tree name) +{ + int_range_max op1_range, op2_range; + tree op1 = gimple_range_operand1 (stmt); + tree op2 = gimple_range_operand2 (stmt); + + expr_range_in_bb (op1_range, op1, gimple_bb (stmt)); + expr_range_in_bb (op2_range, op2, gimple_bb (stmt)); + + // Intersect with range for op2 based on lhs and op1. + if (gimple_range_calc_op2 (r, stmt, lhs, op1_range)) + op2_range.intersect (r); + + gimple *src_stmt = SSA_NAME_DEF_STMT (op2); + // If def stmt is outside of this BB, then name must be an import. + if (!src_stmt || (gimple_bb (src_stmt) != gimple_bb (stmt))) + { + // If this isn't the right src statement, then abort calculation. + if (!src_stmt || gimple_get_lhs (src_stmt) != name) + return false; + return compute_name_range_op (r, src_stmt, op2_range, name); + } + // Then feed this range back as the LHS of the defining statement. + return compute_operand_range (r, src_stmt, op2_range, name); +} + +// Calculate a range for NAME from both operand positions of S +// assuming the result of the statement is LHS. Return the range in +// R, or false if no range could be calculated. + +bool +gori_compute::compute_operand1_and_operand2_range + (irange &r, + gimple *stmt, + const irange &lhs, + tree name) +{ + int_range_max op_range; + + // Calculate a good a range for op2. Since op1 == op2, this will + // have already included whatever the actual range of name is. + if (!compute_operand2_range (op_range, stmt, lhs, name)) + return false; + + // Now get the range thru op1. + if (!compute_operand1_range (r, stmt, lhs, name)) + return false; + + // Whichever range is the most permissive is the one we need to + // use. (?) OR is that true? Maybe this should be intersection? + r.union_ (op_range); + return true; +} + +// Return TRUE if a range can be calcalated for NAME on edge E. + +bool +gori_compute::has_edge_range_p (edge e, tree name) +{ + return (m_gori_map->is_export_p (name, e->src) + || m_gori_map->def_chain_in_export_p (name, e->src)); +} + +// Dump what is known to GORI computes to listing file F. + +void +gori_compute::dump (FILE *f) +{ + m_gori_map->dump (f); +} + +// Calculate a range on edge E and return it in R. Try to evaluate a +// range for NAME on this edge. Return FALSE if this is either not a +// control edge or NAME is not defined by this edge. + +bool +gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name) +{ + int_range_max lhs; + + gcc_checking_assert (gimple_range_ssa_p (name)); + // Determine if there is an outgoing edge. + gimple *stmt = outgoing.edge_range_p (lhs, e); + if (!stmt) + return false; + + // If NAME can be calculated on the edge, use that. + if (m_gori_map->is_export_p (name, e->src)) + return compute_operand_range (r, stmt, lhs, name); + + // Otherwise see if NAME is derived from something that can be + // calculated. This performs no dynamic lookups whatsover, so it is + // low cost. + return false; +} + +// -------------------------------------------------------------------------- + +// Cache for SSAs that appear on the RHS of a boolean assignment. +// +// Boolean assignments of logical expressions (i.e. LHS = j_5 > 999) +// have SSA operands whose range depend on the LHS of the assigment. +// That is, the range of j_5 when LHS is true is different than when +// LHS is false. +// +// This class caches the TRUE/FALSE ranges of such SSAs to avoid +// recomputing. + +class logical_stmt_cache +{ +public: + logical_stmt_cache (); + ~logical_stmt_cache (); + void set_range (tree lhs, tree name, const tf_range &); + bool get_range (tf_range &r, tree lhs, tree name) const; + bool cacheable_p (gimple *, const irange *lhs_range = NULL) const; + void dump (FILE *, gimple *stmt) const; + tree same_cached_name (tree lhs1, tree lh2) const; +private: + tree cached_name (tree lhs) const; + void slot_diagnostics (tree lhs, const tf_range &range) const; + struct cache_entry + { + cache_entry (tree name, const irange &t_range, const irange &f_range); + void dump (FILE *out) const; + tree name; + tf_range range; + }; + vec m_ssa_cache; +}; + +logical_stmt_cache::cache_entry::cache_entry (tree name, + const irange &t_range, + const irange &f_range) + : name (name), range (t_range, f_range) +{ +} + +logical_stmt_cache::logical_stmt_cache () +{ + m_ssa_cache.create (num_ssa_names + num_ssa_names / 10); + m_ssa_cache.safe_grow_cleared (num_ssa_names); +} + +logical_stmt_cache::~logical_stmt_cache () +{ + for (unsigned i = 0; i < m_ssa_cache.length (); ++i) + if (m_ssa_cache[i]) + delete m_ssa_cache[i]; + m_ssa_cache.release (); +} + +// Dump cache_entry to OUT. + +void +logical_stmt_cache::cache_entry::dump (FILE *out) const +{ + fprintf (out, "name="); + print_generic_expr (out, name, TDF_SLIM); + fprintf (out, " "); + range.true_range.dump (out); + fprintf (out, ", "); + range.false_range.dump (out); + fprintf (out, "\n"); +} + +// Update range for cache entry of NAME as it appears in the defining +// statement of LHS. + +void +logical_stmt_cache::set_range (tree lhs, tree name, const tf_range &range) +{ + unsigned version = SSA_NAME_VERSION (lhs); + if (version >= m_ssa_cache.length ()) + m_ssa_cache.safe_grow_cleared (num_ssa_names + num_ssa_names / 10); + + cache_entry *slot = m_ssa_cache[version]; + slot_diagnostics (lhs, range); + if (slot) + { + // The IL must have changed. Update the carried SSA name for + // consistency. Testcase is libgomp.fortran/doacross1.f90. + if (slot->name != name) + slot->name = name; + return; + } + m_ssa_cache[version] + = new cache_entry (name, range.true_range, range.false_range); +} + +// If there is a cached entry of NAME, set it in R and return TRUE, +// otherwise return FALSE. LHS is the defining statement where NAME +// appeared. + +bool +logical_stmt_cache::get_range (tf_range &r, tree lhs, tree name) const +{ + gcc_checking_assert (cacheable_p (SSA_NAME_DEF_STMT (lhs))); + if (cached_name (lhs) == name) + { + unsigned version = SSA_NAME_VERSION (lhs); + if (m_ssa_cache[version]) + { + r = m_ssa_cache[version]->range; + return true; + } + } + return false; +} + +// If the defining statement of LHS is in the cache, return the SSA +// operand being cached. That is, return SSA for LHS = SSA .RELOP. OP2. + +tree +logical_stmt_cache::cached_name (tree lhs) const +{ + unsigned version = SSA_NAME_VERSION (lhs); + + if (version >= m_ssa_cache.length ()) + return NULL; + + if (m_ssa_cache[version]) + return m_ssa_cache[version]->name; + return NULL; +} + +// Return TRUE if the cached name for LHS1 is the same as the +// cached name for LHS2. + +tree +logical_stmt_cache::same_cached_name (tree lhs1, tree lhs2) const +{ + tree name = cached_name (lhs1); + if (name && name == cached_name (lhs2)) + return name; + return NULL; +} + +// Return TRUE if STMT is a statement we are interested in caching. +// LHS_RANGE is any known range for the LHS of STMT. + +bool +logical_stmt_cache::cacheable_p (gimple *stmt, const irange *lhs_range) const +{ + if (gimple_code (stmt) == GIMPLE_ASSIGN + && types_compatible_p (TREE_TYPE (gimple_assign_lhs (stmt)), + boolean_type_node) + && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) + { + switch (gimple_expr_code (stmt)) + { + case LT_EXPR: + case LE_EXPR: + case GT_EXPR: + case GE_EXPR: + case EQ_EXPR: + case NE_EXPR: + case TRUTH_AND_EXPR: + case BIT_AND_EXPR: + case TRUTH_OR_EXPR: + case BIT_IOR_EXPR: + return !lhs_range || range_is_either_true_or_false (*lhs_range); + default: + return false; + } + } + return false; +} + +// Output debugging diagnostics for the cache entry for LHS. RANGE is +// the new range that is being cached. + +void +logical_stmt_cache::slot_diagnostics (tree lhs, const tf_range &range) const +{ + gimple *stmt = SSA_NAME_DEF_STMT (lhs); + unsigned version = SSA_NAME_VERSION (lhs); + cache_entry *slot = m_ssa_cache[version]; + + if (!slot) + { + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file ? dump_file : stderr, "registering range for: "); + dump (dump_file ? dump_file : stderr, stmt); + } + return; + } + if (DEBUG_RANGE_CACHE) + fprintf (dump_file ? dump_file : stderr, + "reusing range for SSA #%d\n", version); + if (CHECKING_P && (slot->range.true_range != range.true_range + || slot->range.false_range != range.false_range)) + { + fprintf (stderr, "FATAL: range altered for cached: "); + dump (stderr, stmt); + fprintf (stderr, "Attempt to change to:\n"); + fprintf (stderr, "TRUE="); + range.true_range.dump (stderr); + fprintf (stderr, ", FALSE="); + range.false_range.dump (stderr); + fprintf (stderr, "\n"); + gcc_unreachable (); + } +} + +// Dump the cache information for STMT. + +void +logical_stmt_cache::dump (FILE *out, gimple *stmt) const +{ + tree lhs = gimple_assign_lhs (stmt); + cache_entry *entry = m_ssa_cache[SSA_NAME_VERSION (lhs)]; + + print_gimple_stmt (out, stmt, 0, TDF_SLIM); + if (entry) + { + fprintf (out, "\tname = "); + print_generic_expr (out, entry->name); + fprintf (out, " lhs(%d)= ", SSA_NAME_VERSION (lhs)); + print_generic_expr (out, lhs); + fprintf (out, "\n\tTRUE="); + entry->range.true_range.dump (out); + fprintf (out, ", FALSE="); + entry->range.false_range.dump (out); + fprintf (out, "\n"); + } + else + fprintf (out, "[EMPTY]\n"); +} + +gori_compute_cache::gori_compute_cache () +{ + m_cache = new logical_stmt_cache; +} + +gori_compute_cache::~gori_compute_cache () +{ + delete m_cache; +} + +// Caching version of compute_operand_range. If NAME, as it appears +// in STMT, has already been cached return it from the cache, +// otherwise compute the operand range as normal and cache it. + +bool +gori_compute_cache::compute_operand_range (irange &r, gimple *stmt, + const irange &lhs_range, tree name) +{ + bool cacheable = m_cache->cacheable_p (stmt, &lhs_range); + if (cacheable) + { + tree lhs = gimple_assign_lhs (stmt); + tf_range range; + if (m_cache->get_range (range, lhs, name)) + { + if (lhs_range.zero_p ()) + r = range.false_range; + else + r = range.true_range; + return true; + } + } + if (super::compute_operand_range (r, stmt, lhs_range, name)) + { + if (cacheable) + cache_stmt (stmt); + return true; + } + return false; +} + +// Cache STMT if possible. + +void +gori_compute_cache::cache_stmt (gimple *stmt) +{ + gcc_checking_assert (m_cache->cacheable_p (stmt)); + enum tree_code code = gimple_expr_code (stmt); + tree lhs = gimple_assign_lhs (stmt); + tree op1 = gimple_range_operand1 (stmt); + tree op2 = gimple_range_operand2 (stmt); + int_range_max r_true_side, r_false_side; + + // LHS = s_5 > 999. + if (TREE_CODE (op2) == INTEGER_CST) + { + range_operator *handler = range_op_handler (code, TREE_TYPE (lhs)); + int_range_max op2_range; + expr_range_in_bb (op2_range, op2, gimple_bb (stmt)); + tree type = TREE_TYPE (op1); + handler->op1_range (r_true_side, type, m_bool_one, op2_range); + handler->op1_range (r_false_side, type, m_bool_zero, op2_range); + m_cache->set_range (lhs, op1, tf_range (r_true_side, r_false_side)); + } + // LHS = s_5 > b_8. + else if (tree cached_name = m_cache->same_cached_name (op1, op2)) + { + tf_range op1_range, op2_range; + gcc_assert (m_cache->get_range (op1_range, op1, cached_name)); + gcc_assert (m_cache->get_range (op2_range, op2, cached_name)); + gcc_assert (logical_combine (r_true_side, code, m_bool_one, + op1_range, op2_range)); + gcc_assert (logical_combine (r_false_side, code, m_bool_zero, + op1_range, op2_range)); + m_cache->set_range (lhs, cached_name, + tf_range (r_true_side, r_false_side)); + } +} diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h new file mode 100644 index 00000000000..8ef452bf433 --- /dev/null +++ b/gcc/gimple-range-gori.h @@ -0,0 +1,138 @@ +/* Header file for gimple range GORI structures. + 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_RANGE_GORI_H +#define GCC_GIMPLE_RANGE_GORI_H + + +// This class is used to determine which SSA_NAMES can have ranges +// calculated for them on outgoing edges from basic blocks. This represents +// ONLY the effect of the basic block edge->src on a range. +// +// There are 2 primary entry points: +// +// has_edge_range_p (edge e, tree name) +// returns true if the outgoing edge *may* be able to produce range +// information for ssa_name NAME on edge E. +// FALSE is returned if this edge does not affect the range of NAME. +// +// outgoing_edge_range_p (irange &range, edge e, tree name) +// Actually does the calculation of RANGE for name on E +// This represents application of whatever static range effect edge E +// may have on NAME, not any cumulative effect. + +// There are also some internal APIs +// +// ssa_range_in_bb () is an internal routine which is used to start any +// calculation chain using SSA_NAMES which come from outside the block. ie +// a_2 = b_4 - 8 +// if (a_2 < 30) +// on the true edge, a_2 is known to be [0, 29] +// b_4 can be calculated as [8, 37] +// during this calculation, b_4 is considered an "import" and ssa_range_in_bb +// is queried for a starting range which is used in the calculation. +// A default value of VARYING provides the raw static info for the edge. +// +// If there is any known range for b_4 coming into this block, it can refine +// the results. This allows for cascading results to be propogated. +// if b_4 is [100, 200] on entry to the block, feeds into the calculation +// of a_2 = [92, 192], and finally on the true edge the range would be +// an empty range [] because it is not possible for the true edge to be taken. +// +// expr_range_in_bb is simply a wrapper which calls ssa_range_in_bb for +// SSA_NAMES and otherwise simply calculates the range of the expression. +// +// The remaining routines are internal use only. + +class gori_compute +{ +public: + gori_compute (); + ~gori_compute (); + bool outgoing_edge_range_p (irange &r, edge e, tree name); + bool has_edge_range_p (edge e, tree name); + void dump (FILE *f); +protected: + virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb); + virtual bool compute_operand_range (irange &r, gimple *stmt, + const irange &lhs, tree name); + + void expr_range_in_bb (irange &r, tree expr, basic_block bb); + bool compute_logical_operands (irange &r, gimple *stmt, + const irange &lhs, + tree name); + void compute_logical_operands_in_chain (class tf_range &range, + gimple *stmt, const irange &lhs, + tree name, tree op, + bool op_in_chain); + bool optimize_logical_operands (tf_range &range, gimple *stmt, + const irange &lhs, tree name, tree op); + bool logical_combine (irange &r, enum tree_code code, const irange &lhs, + const class tf_range &op1_range, + const class tf_range &op2_range); + int_range<2> m_bool_zero; // Boolean false cached. + int_range<2> m_bool_one; // Boolean true cached. + +private: + bool compute_operand_range_switch (irange &r, gswitch *stmt, + const irange &lhs, tree name); + bool compute_name_range_op (irange &r, gimple *stmt, const irange &lhs, + tree name); + bool compute_operand1_range (irange &r, gimple *stmt, const irange &lhs, + tree name); + bool compute_operand2_range (irange &r, gimple *stmt, const irange &lhs, + tree name); + bool compute_operand1_and_operand2_range (irange &r, gimple *stmt, + const irange &lhs, tree name); + + class gori_map *m_gori_map; + outgoing_range outgoing; // Edge values for COND_EXPR & SWITCH_EXPR. +}; + + +// This class adds a cache to gori_computes for logical expressions. +// bool result = x && y +// requires calcuation of both X and Y for both true and false results. +// There are 4 combinations [0,0][0,0] [0,0][1,1] [1,1][0,0] and [1,1][1,1]. +// Note that each pair of possible results for X and Y are used twice, and +// the calcuation of those results are the same each time. +// +// The cache simply checks if a stmt is cachable, and if so, saves both the +// true and false results for the next time the query is made. +// +// This is used to speed up long chains of logical operations which +// quickly become exponential. + +class gori_compute_cache : public gori_compute +{ +public: + gori_compute_cache (); + ~gori_compute_cache (); +protected: + virtual bool compute_operand_range (irange &r, gimple *stmt, + const irange &lhs, tree name); +private: + void cache_stmt (gimple *); + typedef gori_compute super; + class logical_stmt_cache *m_cache; +}; + +#endif // GCC_GIMPLE_RANGE_GORI_H diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc new file mode 100644 index 00000000000..75c03d6610b --- /dev/null +++ b/gcc/gimple-range.cc @@ -0,0 +1,1284 @@ +/* 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-pretty-print.h" +#include "gimple-iterator.h" +#include "optabs-tree.h" +#include "gimple-fold.h" +#include "tree-cfg.h" +#include "fold-const.h" +#include "tree-cfg.h" +#include "wide-int.h" +#include "fold-const.h" +#include "case-cfn-macros.h" +#include "omp-general.h" +#include "cfgloop.h" +#include "tree-ssa-loop.h" +#include "tree-scalar-evolution.h" +#include "dbgcnt.h" +#include "alloc-pool.h" +#include "vr-values.h" +#include "gimple-range.h" + + +// Adjust the range for a pointer difference where the operands came +// from a memchr. +// +// This notices the following sequence: +// +// def = __builtin_memchr (arg, 0, sz) +// n = def - arg +// +// The range for N can be narrowed to [0, PTRDIFF_MAX - 1]. + +static void +adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt) +{ + tree op0 = gimple_assign_rhs1 (diff_stmt); + tree op1 = gimple_assign_rhs2 (diff_stmt); + tree op0_ptype = TREE_TYPE (TREE_TYPE (op0)); + tree op1_ptype = TREE_TYPE (TREE_TYPE (op1)); + gimple *call; + + if (TREE_CODE (op0) == SSA_NAME + && TREE_CODE (op1) == SSA_NAME + && (call = SSA_NAME_DEF_STMT (op0)) + && is_gimple_call (call) + && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) + && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node) + && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node) + && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node) + && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node) + && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) + && vrp_operand_equal_p (op1, gimple_call_arg (call, 0)) + && integer_zerop (gimple_call_arg (call, 1))) + { + tree max = vrp_val_max (ptrdiff_type_node); + wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); + tree expr_type = gimple_expr_type (diff_stmt); + tree range_min = build_zero_cst (expr_type); + tree range_max = wide_int_to_tree (expr_type, wmax - 1); + int_range<2> r (range_min, range_max); + res.intersect (r); + } +} + +// This function looks for situations when walking the use/def chains +// may provide additonal contextual range information not exposed on +// this statement. Like knowing the IMAGPART return value from a +// builtin function is a boolean result. + +// We should rework how we're called, as we have an op_unknown entry +// for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this +// function gets called. + +static void +gimple_range_adjustment (irange &res, const gimple *stmt) +{ + switch (gimple_expr_code (stmt)) + { + case POINTER_DIFF_EXPR: + adjust_pointer_diff_expr (res, stmt); + return; + + case IMAGPART_EXPR: + { + tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); + if (TREE_CODE (name) == SSA_NAME) + { + gimple *def_stmt = SSA_NAME_DEF_STMT (name); + if (def_stmt && is_gimple_call (def_stmt) + && gimple_call_internal_p (def_stmt)) + { + switch (gimple_call_internal_fn (def_stmt)) + { + case IFN_ADD_OVERFLOW: + case IFN_SUB_OVERFLOW: + case IFN_MUL_OVERFLOW: + case IFN_ATOMIC_COMPARE_EXCHANGE: + { + int_range<2> r; + r.set_varying (boolean_type_node); + tree type = TREE_TYPE (gimple_assign_lhs (stmt)); + range_cast (r, type); + res.intersect (r); + } + default: + break; + } + } + } + break; + } + + default: + break; + } +} + +// Return a range in R for the tree EXPR. Return true if a range is +// representable. + +bool +get_tree_range (irange &r, tree expr) +{ + tree type; + if (TYPE_P (expr)) + type = expr; + else + type = TREE_TYPE (expr); + + // Return false if the type isn't suported. + if (!irange::supports_type_p (type)) + return false; + + switch (TREE_CODE (expr)) + { + case INTEGER_CST: + r.set (expr, expr); + return true; + + case SSA_NAME: + r = gimple_range_global (expr); + return true; + + case ADDR_EXPR: + { + // Handle &var which can show up in phi arguments. + bool ov; + if (tree_single_nonzero_warnv_p (expr, &ov)) + { + r = range_nonzero (type); + return true; + } + break; + } + + default: + break; + } + r.set_varying (type); + return true; +} + +// Fold this unary statement using R1 as operand1's range, returning +// the result in RES. Return false if the operation fails. + +bool +gimple_range_fold (irange &res, const gimple *stmt, const irange &r1) +{ + gcc_checking_assert (gimple_range_handler (stmt)); + + tree type = gimple_expr_type (stmt); + // Unary SSA operations require the LHS type as the second range. + int_range<2> r2 (type); + + return gimple_range_fold (res, stmt, r1, r2); +} + +// Fold this binary statement using R1 and R2 as the operands ranges, +// returning the result in RES. Return false if the operation fails. + +bool +gimple_range_fold (irange &res, const gimple *stmt, + const irange &r1, const irange &r2) +{ + gcc_checking_assert (gimple_range_handler (stmt)); + + gimple_range_handler (stmt)->fold_range (res, gimple_expr_type (stmt), + r1, r2); + + // If there are any gimple lookups, do those now. + gimple_range_adjustment (res, stmt); + return true; +} + +// Return the base of the RHS of an assignment. + +tree +gimple_range_base_of_assignment (const gimple *stmt) +{ + gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); + tree op1 = gimple_assign_rhs1 (stmt); + if (gimple_assign_rhs_code (stmt) == ADDR_EXPR) + return get_base_address (TREE_OPERAND (op1, 0)); + return op1; +} + +// Return the first operand of this statement if it is a valid operand +// supported by ranges, otherwise return NULL_TREE. Special case is +// &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr. + +tree +gimple_range_operand1 (const gimple *stmt) +{ + gcc_checking_assert (gimple_range_handler (stmt)); + + switch (gimple_code (stmt)) + { + case GIMPLE_COND: + return gimple_cond_lhs (stmt); + case GIMPLE_ASSIGN: + { + tree base = gimple_range_base_of_assignment (stmt); + if (base && TREE_CODE (base) == MEM_REF) + { + // If the base address is an SSA_NAME, we return it + // here. This allows processing of the range of that + // name, while the rest of the expression is simply + // ignored. The code in range_ops will see the + // ADDR_EXPR and do the right thing. + tree ssa = TREE_OPERAND (base, 0); + if (TREE_CODE (ssa) == SSA_NAME) + return ssa; + } + return base; + } + default: + break; + } + return NULL; +} + +// Return the second operand of statement STMT, otherwise return NULL_TREE. + +tree +gimple_range_operand2 (const gimple *stmt) +{ + gcc_checking_assert (gimple_range_handler (stmt)); + + switch (gimple_code (stmt)) + { + case GIMPLE_COND: + return gimple_cond_rhs (stmt); + case GIMPLE_ASSIGN: + if (gimple_num_ops (stmt) >= 3) + return gimple_assign_rhs2 (stmt); + default: + break; + } + return NULL_TREE; +} + +// Calculate what we can determine of the range of this unary +// statement's operand if the lhs of the expression has the range +// LHS_RANGE. Return false if nothing can be determined. + +bool +gimple_range_calc_op1 (irange &r, const gimple *stmt, const irange &lhs_range) +{ + gcc_checking_assert (gimple_num_ops (stmt) < 3); + + // An empty range is viral. + 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<2> type_range (type); + return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, + type_range); +} + +// Calculate what we can determine of the range of this statement's +// first operand if the lhs of the expression has the range LHS_RANGE +// and the second operand has the range OP2_RANGE. Return false if +// nothing can be determined. + +bool +gimple_range_calc_op1 (irange &r, const gimple *stmt, + const irange &lhs_range, const irange &op2_range) +{ + // Unary operation are allowed to pass a range in for second operand + // as there are often additional restrictions beyond the type which + // can be imposed. See operator_cast::op1_range(). + tree type = TREE_TYPE (gimple_range_operand1 (stmt)); + // An empty range is viral. + if (op2_range.undefined_p () || lhs_range.undefined_p ()) + { + r.set_undefined (); + return true; + } + return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, + op2_range); +} + +// Calculate what we can determine of the range of this statement's +// second operand if the lhs of the expression has the range LHS_RANGE +// and the first operand has the range OP1_RANGE. Return false if +// nothing can be determined. + +bool +gimple_range_calc_op2 (irange &r, const gimple *stmt, + const irange &lhs_range, const irange &op1_range) +{ + tree type = TREE_TYPE (gimple_range_operand2 (stmt)); + // An empty range is viral. + if (op1_range.undefined_p () || lhs_range.undefined_p ()) + { + r.set_undefined (); + return true; + } + return gimple_range_handler (stmt)->op2_range (r, type, lhs_range, + op1_range); +} + +// Calculate a range for statement S and return it in R. If NAME is provided it +// represents the SSA_NAME on the LHS of the statement. It is only required +// if there is more than one lhs/output. If a range cannot +// be calculated, return false. + +bool +gimple_ranger::calc_stmt (irange &r, gimple *s, tree name) +{ + bool res = false; + // If name is specified, make sure it is an 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 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) +{ + int_range_max range1, range2; + tree type = gimple_expr_type (s); + gcc_checking_assert (irange::supports_type_p (type)); + + tree op1 = gimple_range_operand1 (s); + tree op2 = gimple_range_operand2 (s); + + if (range_of_non_trivial_assignment (r, s)) + return true; + + if (range_of_expr (range1, op1, s)) + { + if (!op2) + return gimple_range_fold (r, s, range1); + + if (range_of_expr (range2, op2, s)) + return gimple_range_fold (r, s, range1, range2); + } + r.set_varying (type); + return true; +} + +// Calculate the range of a non-trivial assignment. That is, is one +// inolving arithmetic on an SSA name (for example, an ADDR_EXPR). +// Return the range in R. +// +// If a range cannot be calculated, return false. + +bool +gimple_ranger::range_of_non_trivial_assignment (irange &r, gimple *stmt) +{ + if (gimple_code (stmt) != GIMPLE_ASSIGN) + return false; + + tree base = gimple_range_base_of_assignment (stmt); + if (base && TREE_CODE (base) == MEM_REF + && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) + { + int_range_max range1; + tree ssa = TREE_OPERAND (base, 0); + if (range_of_expr (range1, ssa, stmt)) + { + tree type = TREE_TYPE (ssa); + range_operator *op = range_op_handler (POINTER_PLUS_EXPR, type); + int_range<2> offset (TREE_OPERAND (base, 1), TREE_OPERAND (base, 1)); + op->fold_range (r, type, range1, offset); + return true; + } + } + return false; +} + +// Calculate a range for phi statement S and return it in R. +// If a range cannot be calculated, return false. + +bool +gimple_ranger::range_of_phi (irange &r, gphi *phi) +{ + tree phi_def = gimple_phi_result (phi); + tree type = TREE_TYPE (phi_def); + int_range_max arg_range; + unsigned x; + + if (!irange::supports_type_p (type)) + return false; + + // Start with an empty range, unioning in each argument's range. + r.set_undefined (); + for (x = 0; x < gimple_phi_num_args (phi); x++) + { + 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; + } + + // If SCEV is available, query if this PHI has any knonwn values. + if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) + { + value_range loop_range; + class loop *l = loop_containing_stmt (phi); + if (l) + { + range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi); + if (!loop_range.varying_p ()) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Loops range found for "); + print_generic_expr (dump_file, phi_def, TDF_SLIM); + fprintf (dump_file, ": "); + loop_range.dump (dump_file); + fprintf (dump_file, " and calculated range :"); + r.dump (dump_file); + fprintf (dump_file, "\n"); + } + r.intersect (loop_range); + } + } + } + + return true; +} + +// Calculate a range for call statement S and return it in R. +// If a range cannot be calculated, return false. + +bool +gimple_ranger::range_of_call (irange &r, gcall *call) +{ + tree type = gimple_call_return_type (call); + tree lhs = gimple_call_lhs (call); + bool strict_overflow_p; + + if (!irange::supports_type_p (type)) + return false; + + if (range_of_builtin_call (r, call)) + ; + else if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p)) + r.set (build_int_cst (type, 0), TYPE_MAX_VALUE (type)); + else if (gimple_call_nonnull_result_p (call) + || gimple_call_nonnull_arg (call)) + r = range_nonzero (type); + else + r.set_varying (type); + + // If there is an LHS, intersect that with what is known. + if (lhs) + { + value_range def; + def = gimple_range_global (lhs); + r.intersect (def); + } + return true; +} + + +void +gimple_ranger::range_of_builtin_ubsan_call (irange &r, gcall *call, + tree_code code) +{ + gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR + || code == MULT_EXPR); + tree type = gimple_call_return_type (call); + range_operator *op = range_op_handler (code, type); + gcc_checking_assert (op); + int_range_max 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 arithmetic is wrapping. If there is any overflow, + // we'll complain, but will actually do wrapping operation. + flag_wrapv = 1; + op->fold_range (r, type, ir0, ir1); + flag_wrapv = saved_flag_wrapv; + + // If for both arguments vrp_valueize returned non-NULL, this should + // have been already folded and if not, it wasn't folded because of + // overflow. Avoid removing the UBSAN_CHECK_* calls in that case. + if (r.singleton_p ()) + r.set_varying (type); +} + + +bool +gimple_ranger::range_of_builtin_call (irange &r, gcall *call) +{ + combined_fn func = gimple_call_combined_fn (call); + if (func == CFN_LAST) + return false; + + tree type = gimple_call_return_type (call); + tree arg; + int mini, maxi, zerov, prec; + scalar_int_mode mode; + + switch (func) + { + case CFN_BUILT_IN_CONSTANT_P: + if (cfun->after_inlining) + { + r.set_zero (type); + // r.equiv_clear (); + return true; + } + arg = gimple_call_arg (call, 0); + if (range_of_expr (r, arg, call) && r.singleton_p ()) + { + r.set (build_one_cst (type), build_one_cst (type)); + return true; + } + break; + + CASE_CFN_FFS: + CASE_CFN_POPCOUNT: + // __builtin_ffs* and __builtin_popcount* return [0, prec]. + arg = gimple_call_arg (call, 0); + prec = TYPE_PRECISION (TREE_TYPE (arg)); + mini = 0; + maxi = prec; + gcc_assert (range_of_expr (r, arg, call)); + // If arg is non-zero, then ffs or popcount are non-zero. + if (!range_includes_zero_p (&r)) + mini = 1; + // If some high bits are known to be zero, decrease the maximum. + if (!r.undefined_p ()) + { + wide_int max = r.upper_bound (); + maxi = wi::floor_log2 (max) + 1; + } + r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); + return true; + + CASE_CFN_PARITY: + r.set (build_zero_cst (type), build_one_cst (type)); + return true; + + CASE_CFN_CLZ: + // __builtin_c[lt]z* return [0, prec-1], except when the + // argument is 0, but that is undefined behavior. + // + // On many targets where the CLZ RTL or optab value is defined + // for 0, the value is prec, so include that in the range by + // default. + arg = gimple_call_arg (call, 0); + prec = TYPE_PRECISION (TREE_TYPE (arg)); + mini = 0; + maxi = prec; + mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); + if (optab_handler (clz_optab, mode) != CODE_FOR_nothing + && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) + // Only handle the single common value. + && zerov != prec) + // Magic value to give up, unless we can prove arg is non-zero. + mini = -2; + + gcc_assert (range_of_expr (r, arg, call)); + // From clz of minimum we can compute result maximum. + if (r.constant_p ()) + { + maxi = prec - 1 - wi::floor_log2 (r.lower_bound ()); + if (maxi != prec) + mini = 0; + } + else if (!range_includes_zero_p (&r)) + { + maxi = prec - 1; + mini = 0; + } + if (mini == -2) + break; + // From clz of maximum we can compute result minimum. + if (r.constant_p ()) + { + mini = prec - 1 - wi::floor_log2 (r.upper_bound ()); + if (mini == prec) + break; + } + if (mini == -2) + break; + r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); + return true; + + CASE_CFN_CTZ: + // __builtin_ctz* return [0, prec-1], except for when the + // argument is 0, but that is undefined behavior. + // + // If there is a ctz optab for this mode and + // CTZ_DEFINED_VALUE_AT_ZERO, include that in the range, + // otherwise just assume 0 won't be seen. + arg = gimple_call_arg (call, 0); + prec = TYPE_PRECISION (TREE_TYPE (arg)); + mini = 0; + maxi = prec - 1; + mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); + if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing + && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov)) + { + // Handle only the two common values. + if (zerov == -1) + mini = -1; + else if (zerov == prec) + maxi = prec; + else + // Magic value to give up, unless we can prove arg is non-zero. + mini = -2; + } + gcc_assert (range_of_expr (r, arg, call)); + if (!r.undefined_p ()) + { + if (r.lower_bound () != 0) + { + mini = 0; + maxi = prec - 1; + } + // If some high bits are known to be zero, we can decrease + // the maximum. + wide_int max = r.upper_bound (); + if (max == 0) + break; + maxi = wi::floor_log2 (max); + } + if (mini == -2) + break; + r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); + return true; + + CASE_CFN_CLRSB: + arg = gimple_call_arg (call, 0); + prec = TYPE_PRECISION (TREE_TYPE (arg)); + r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1)); + return true; + case CFN_UBSAN_CHECK_ADD: + range_of_builtin_ubsan_call (r, call, PLUS_EXPR); + return true; + case CFN_UBSAN_CHECK_SUB: + range_of_builtin_ubsan_call (r, call, MINUS_EXPR); + return true; + case CFN_UBSAN_CHECK_MUL: + range_of_builtin_ubsan_call (r, call, MULT_EXPR); + return true; + + case CFN_GOACC_DIM_SIZE: + case CFN_GOACC_DIM_POS: + // Optimizing these two internal functions helps the loop + // optimizer eliminate outer comparisons. Size is [1,N] + // and pos is [0,N-1]. + { + bool is_pos = func == CFN_GOACC_DIM_POS; + int axis = oacc_get_ifn_dim_arg (call); + int size = oacc_get_fn_dim_size (current_function_decl, axis); + if (!size) + // If it's dynamic, the backend might know a hardware limitation. + size = targetm.goacc.dim_limit (axis); + + r.set (build_int_cst (type, is_pos ? 0 : 1), + size + ? build_int_cst (type, size - is_pos) : vrp_val_max (type)); + return true; + } + + case CFN_BUILT_IN_STRLEN: + if (tree lhs = gimple_call_lhs (call)) + if (ptrdiff_type_node + && (TYPE_PRECISION (ptrdiff_type_node) + == TYPE_PRECISION (TREE_TYPE (lhs)))) + { + tree type = TREE_TYPE (lhs); + tree max = vrp_val_max (ptrdiff_type_node); + wide_int wmax + = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); + tree range_min = build_zero_cst (type); + // To account for the terminating NULL, the maximum length + // is one less than the maximum array size, which in turn + // is one less than PTRDIFF_MAX (or SIZE_MAX where it's + // smaller than the former type). + // FIXME: Use max_object_size() - 1 here. + tree range_max = wide_int_to_tree (type, wmax - 2); + r.set (range_min, range_max); + return true; + } + break; + default: + break; + } + return false; +} + + + +// Calculate a range for COND_EXPR statement S and return it in R. +// If a range cannot be calculated, return false. + +bool +gimple_ranger::range_of_cond_expr (irange &r, gassign *s) +{ + int_range_max cond_range, range1, range2; + tree cond = gimple_assign_rhs1 (s); + tree op1 = gimple_assign_rhs2 (s); + tree op2 = gimple_assign_rhs3 (s); + + gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR); + gcc_checking_assert (useless_type_conversion_p (TREE_TYPE (op1), + TREE_TYPE (op2))); + if (!irange::supports_type_p (TREE_TYPE (op1))) + return false; + + gcc_assert (range_of_expr (cond_range, cond, s)); + gcc_assert (range_of_expr (range1, op1, s)); + gcc_assert (range_of_expr (range2, op2, s)); + + // If the condition is known, choose the appropriate expression. + if (cond_range.singleton_p ()) + { + // False, pick second operand. + if (cond_range.zero_p ()) + r = range2; + else + r = range1; + } + else + { + r = range1; + r.union_ (range2); + } + return true; +} + +bool +gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) +{ + if (!gimple_range_ssa_p (expr)) + return get_tree_range (r, expr); + + // If there is no statement, just get the global value. + if (!stmt) + { + if (!m_cache.m_globals.get_global_range (r, expr)) + r = gimple_range_global (expr); + return true; + } + + basic_block bb = gimple_bb (stmt); + gimple *def_stmt = SSA_NAME_DEF_STMT (expr); + + // If name is defined in this block, try to get an range from S. + if (def_stmt && gimple_bb (def_stmt) == bb) + gcc_assert (range_of_stmt (r, def_stmt, expr)); + else + // Otherwise OP comes from outside this block, use range on entry. + range_on_entry (r, bb, expr); + + // No range yet, see if there is a dereference in the block. + // We don't care if it's between the def and a use within a block + // because the entire block must be executed anyway. + // FIXME:?? For non-call exceptions we could have a statement throw + // which causes an early block exit. + // in which case we may need to walk from S back to the def/top of block + // to make sure the deref happens between S and there before claiming + // there is a deref. Punt for now. + if (!cfun->can_throw_non_call_exceptions && r.varying_p () && + m_cache.m_non_null.non_null_deref_p (expr, bb)) + r = range_nonzero (TREE_TYPE (expr)); + + return true; +} + +// Return the range of NAME on entry to block BB in R. + +void +gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name) +{ + int_range_max entry_range; + gcc_checking_assert (gimple_range_ssa_p (name)); + + // Start with any known range + gcc_assert (range_of_stmt (r, SSA_NAME_DEF_STMT (name), name)); + + // Now see if there is any on_entry value which may refine it. + if (m_cache.block_range (entry_range, bb, name)) + r.intersect (entry_range); +} + +// Calculate the range for NAME at the end of block BB and return it in R. +// Return false if no range can be calculated. + +void +gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name) +{ + // on-exit from the exit block? + gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); + + gimple *s = last_stmt (bb); + // If there is no statement in the block and this isn't the entry + // block, go get the range_on_entry for this block. For the entry + // block, a NULL stmt will return the global value for NAME. + if (!s && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)) + range_on_entry (r, bb, name); + else + gcc_assert (range_of_expr (r, name, s)); + gcc_checking_assert (r.undefined_p () + || types_compatible_p (r.type(), TREE_TYPE (name))); +} + +// Calculate a range for NAME on edge E and return it in R. + +bool +gimple_ranger::range_on_edge (irange &r, edge e, tree name) +{ + int_range_max 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 true; + } + + range_on_exit (r, e->src, name); + gcc_checking_assert (r.undefined_p () + || types_compatible_p (r.type(), TREE_TYPE (name))); + + // Check to see if NAME is defined on edge e. + if (m_cache.outgoing_edge_range_p (edge_range, e, name)) + r.intersect (edge_range); + + return true; +} + +// Calculate a range for statement S and return it in R. If NAME is +// provided it represents the SSA_NAME on the LHS of the statement. +// It is only required if there is more than one lhs/output. Check +// the global cache for NAME first to see if the evaluation can be +// avoided. If a range cannot be calculated, return false. + +bool +gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) +{ + // If no name, simply call the base routine. + if (!name) + name = gimple_get_lhs (s); + + if (!name) + return calc_stmt (r, s, NULL_TREE); + + gcc_checking_assert (TREE_CODE (name) == SSA_NAME && + irange::supports_type_p (TREE_TYPE (name))); + + // If this STMT has already been processed, return that value. + if (m_cache.m_globals.get_global_range (r, name)) + return true; + // Avoid infinite recursion by initializing global cache + int_range_max tmp = gimple_range_global (name); + m_cache.m_globals.set_global_range (name, tmp); + + gcc_assert (calc_stmt (r, s, name)); + + if (is_a (s)) + r.intersect (tmp); + m_cache.m_globals.set_global_range (name, r); + return true; +} + +// This routine will export whatever global ranges are known to GCC +// SSA_RANGE_NAME_INFO fields. + +void +gimple_ranger::export_global_ranges () +{ + unsigned x; + int_range_max r; + if (dump_file) + { + fprintf (dump_file, "Exported global range table\n"); + fprintf (dump_file, "===========================\n"); + } + + for ( x = 1; x < num_ssa_names; x++) + { + tree name = ssa_name (x); + if (name && !SSA_NAME_IN_FREE_LIST (name) + && gimple_range_ssa_p (name) + && m_cache.m_globals.get_global_range (r, name) + && !r.varying_p()) + { + // Make sure the new range is a subset of the old range. + int_range_max old_range; + old_range = gimple_range_global (name); + old_range.intersect (r); + /* Disable this while we fix tree-ssa/pr61743-2.c. */ + //gcc_checking_assert (old_range == r); + + // WTF? Can't write non-null pointer ranges?? stupid set_range_info! + if (!POINTER_TYPE_P (TREE_TYPE (name)) && !r.undefined_p ()) + { + value_range vr = r; + set_range_info (name, vr); + if (dump_file) + { + print_generic_expr (dump_file, name , TDF_SLIM); + fprintf (dump_file, " --> "); + vr.dump (dump_file); + fprintf (dump_file, "\n"); + fprintf (dump_file, " irange : "); + r.dump (dump_file); + fprintf (dump_file, "\n"); + } + } + } + } +} + +// Print the known table values to file F. + +void +gimple_ranger::dump (FILE *f) +{ + basic_block bb; + + FOR_EACH_BB_FN (bb, cfun) + { + unsigned x; + edge_iterator ei; + edge e; + int_range_max range; + fprintf (f, "\n=========== BB %d ============\n", bb->index); + m_cache.m_on_entry.dump (f, bb); + + dump_bb (f, bb, 4, TDF_NONE); + + // Now find any globals defined in this block. + for (x = 1; x < num_ssa_names; x++) + { + tree name = ssa_name (x); + if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) && + gimple_bb (SSA_NAME_DEF_STMT (name)) == bb && + m_cache.m_globals.get_global_range (range, name)) + { + if (!range.varying_p ()) + { + print_generic_expr (f, name, TDF_SLIM); + fprintf (f, " : "); + range.dump (f); + fprintf (f, "\n"); + } + + } + } + + // And now outgoing edges, if they define anything. + FOR_EACH_EDGE (e, ei, bb->succs) + { + for (x = 1; x < num_ssa_names; x++) + { + tree name = gimple_range_ssa_p (ssa_name (x)); + if (name && m_cache.outgoing_edge_range_p (range, e, name)) + { + gimple *s = SSA_NAME_DEF_STMT (name); + // Only print the range if this is the def block, or + // the on entry cache for either end of the edge is + // set. + if ((s && bb == gimple_bb (s)) || + m_cache.block_range (range, bb, name, false) || + m_cache.block_range (range, e->dest, name, false)) + { + range_on_edge (range, e, name); + if (!range.varying_p ()) + { + fprintf (f, "%d->%d ", e->src->index, + e->dest->index); + char c = ' '; + if (e->flags & EDGE_TRUE_VALUE) + fprintf (f, " (T)%c", c); + else if (e->flags & EDGE_FALSE_VALUE) + fprintf (f, " (F)%c", c); + else + fprintf (f, " "); + print_generic_expr (f, name, TDF_SLIM); + fprintf(f, " : \t"); + range.dump(f); + fprintf (f, "\n"); + } + } + } + } + } + } + + m_cache.m_globals.dump (dump_file); + fprintf (f, "\n"); + + if (dump_flags & TDF_DETAILS) + { + fprintf (f, "\nDUMPING GORI MAP\n"); + m_cache.dump (f); + fprintf (f, "\n"); + } +} + +// If SCEV has any information about phi node NAME, return it as a range in R. + +void +gimple_ranger::range_of_ssa_name_with_loop_info (irange &r, tree name, + class loop *l, gphi *phi) +{ + gcc_checking_assert (TREE_CODE (name) == SSA_NAME); + tree min, max, type = TREE_TYPE (name); + if (bounds_of_var_in_loop (&min, &max, this, l, phi, name)) + { + // ?? We could do better here. Since MIN/MAX can only be an + // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call + // the ranger and solve anything not an integer. + if (TREE_CODE (min) != INTEGER_CST) + min = vrp_val_min (type); + if (TREE_CODE (max) != INTEGER_CST) + max = vrp_val_max (type); + r.set (min, max); + } + else + r.set_varying (type); +} + +// -------------------------------------------------------------------------- +// trace_ranger implementation. + + +trace_ranger::trace_ranger () +{ + indent = 0; + trace_count = 0; +} + +// If dumping, return true and print the prefix for the next output line. + +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) +{ + if (dumping (counter, true)) + { + indent -= bump; + fputs(result ? "TRUE : " : "FALSE : ", dump_file); + fprintf (dump_file, "(%u) ", counter); + fputs (caller, dump_file); + fputs (" (",dump_file); + if (name) + print_generic_expr (dump_file, name, TDF_SLIM); + fputs (") ",dump_file); + if (result) + { + r.dump (dump_file); + fputc('\n', dump_file); + } + else + fputc('\n', dump_file); + // Marks the end of a request. + if (indent == 0) + fputc('\n', dump_file); + } + return result; +} + +// Tracing version of range_on_edge. Call it with printing wrappers. + +bool +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; + } + + bool res = gimple_ranger::range_on_edge (r, e, name); + trailer (idx, "range_on_edge", true, name, r); + return res; +} + +// 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; + } + + gimple_ranger::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; + } + + gimple_ranger::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 = gimple_ranger::range_of_stmt (r, s, name); + + return trailer (idx, "range_of_stmt", res, name, r); +} + +// Tracing version of range_of_expr. Call it with printing wrappers. + +bool +trace_ranger::range_of_expr (irange &r, tree name, gimple *s) +{ + bool res; + unsigned idx = ++trace_count; + if (dumping (idx)) + { + fprintf (dump_file, "range_of_expr("); + print_generic_expr (dump_file, name, TDF_SLIM); + fputs (")", dump_file); + if (s) + { + fputs (" at stmt ", dump_file); + print_gimple_stmt (dump_file, s, 0, TDF_SLIM); + } + else + fputs ("\n", dump_file); + indent += bump; + } + + res = gimple_ranger::range_of_expr (r, name, s); + + return trailer (idx, "range_of_expr", res, name, r); +} diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h new file mode 100644 index 00000000000..4d35e72795f --- /dev/null +++ b/gcc/gimple-range.h @@ -0,0 +1,170 @@ +/* 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" +#include "gimple-range-edge.h" +#include "gimple-range-gori.h" +#include "gimple-range-cache.h" +#include "value-query.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 range_query +{ +public: + gimple_ranger () : m_cache (*this) { } + virtual bool range_of_stmt (irange &r, gimple *, tree name = NULL) OVERRIDE; + virtual bool range_of_expr (irange &r, tree name, gimple * = NULL) OVERRIDE; + virtual bool range_on_edge (irange &r, edge e, tree name) OVERRIDE; + virtual void range_on_entry (irange &r, basic_block bb, tree name); + virtual void range_on_exit (irange &r, basic_block bb, tree name); + void export_global_ranges (); + void dump (FILE *f); +protected: + bool calc_stmt (irange &r, gimple *s, tree name = NULL_TREE); + bool range_of_range_op (irange &r, gimple *s); + bool range_of_call (irange &r, gcall *call); + bool range_of_cond_expr (irange &r, gassign* cond); + ranger_cache m_cache; +private: + bool range_of_phi (irange &r, gphi *phi); + bool range_of_non_trivial_assignment (irange &r, gimple *s); + bool range_of_builtin_call (irange &r, gcall *call); + void range_of_builtin_ubsan_call (irange &r, gcall *call, tree_code code); + bool range_with_loop_info (irange &r, tree name); + void range_of_ssa_name_with_loop_info (irange &, tree, class loop *, + gphi *); +}; + +// Calculate a basic range for a tree expression. +extern bool get_tree_range (irange &r, tree expr); + +// These routines provide a GIMPLE interface to the range-ops code. +extern tree gimple_range_operand1 (const gimple *s); +extern tree gimple_range_operand2 (const gimple *s); +extern tree gimple_range_base_of_assignment (const gimple *s); +extern bool gimple_range_fold (irange &res, const gimple *s, + const irange &r1); +extern bool gimple_range_fold (irange &res, const gimple *s, + const irange &r1, + const irange &r2); +extern bool gimple_range_calc_op1 (irange &r, const gimple *s, + const irange &lhs_range); +extern bool gimple_range_calc_op1 (irange &r, const gimple *s, + const irange &lhs_range, + const irange &op2_range); +extern bool gimple_range_calc_op2 (irange &r, const gimple *s, + const irange &lhs_range, + const irange &op1_range); + + +// Return the range_operator pointer for this statement. This routine +// can also be used to gate whether a routine is range-ops enabled. + +static inline range_operator * +gimple_range_handler (const gimple *s) +{ + if ((gimple_code (s) == GIMPLE_ASSIGN) || (gimple_code (s) == GIMPLE_COND)) + return range_op_handler (gimple_expr_code (s), gimple_expr_type (s)); + return NULL; +} + +// Return EXP if it is an SSA_NAME with a type supported by gimple ranges. + +static inline tree +gimple_range_ssa_p (tree exp) +{ + if (exp && TREE_CODE (exp) == SSA_NAME && + !SSA_NAME_IS_VIRTUAL_OPERAND (exp) && + irange::supports_type_p (TREE_TYPE (exp))) + return exp; + return NULL_TREE; +} + +// Return the legacy GCC global range for NAME if it has one, otherwise +// return VARYING. + +static inline value_range +gimple_range_global (tree name) +{ + gcc_checking_assert (gimple_range_ssa_p (name)); + tree type = TREE_TYPE (name); +#if 0 + // Reenable picking up global ranges when we are OK failing tests that look + // for builtin_unreachable in the code, like + // RUNTESTFLAGS=dg.exp=pr61034.C check-g++ + // pre-optimizations (inlining) set a global range which causes the ranger + // to remove the condition which leads to builtin_unreachable. + 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); + } +#endif + // Otherwise return range for the type. + return value_range (type); +} + + +// This class overloads the ranger routines to provide tracing facilties +// Entry and exit values to each of the APIs is placed in the dumpfile. + +class trace_ranger : public gimple_ranger +{ +public: + trace_ranger (); + virtual bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE); + virtual bool range_of_expr (irange &r, tree name, gimple *s = NULL); + virtual bool 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); +private: + 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); +}; + +// Flag to enable debugging the various internal Caches. +#define DEBUG_RANGE_CACHE (dump_file && (flag_evrp_mode & EVRP_MODE_DEBUG)) + +#endif // GCC_GIMPLE_RANGE_STMT_H