LCOV - code coverage report
Current view: top level - gcc - gimple-range-gori.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 83.3 % 762 635
Test Date: 2026-11-14 16:39:50 Functions: 90.6 % 53 48
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Gimple range GORI functions.
       2              :    Copyright (C) 2017-2026 Free Software Foundation, Inc.
       3              :    Contributed by Andrew MacLeod <amacleod@redhat.com>
       4              :    and Aldy Hernandez <aldyh@redhat.com>.
       5              : 
       6              : This file is part of GCC.
       7              : 
       8              : GCC is free software; you can redistribute it and/or modify
       9              : it under the terms of the GNU General Public License as published by
      10              : the Free Software Foundation; either version 3, or (at your option)
      11              : any later version.
      12              : 
      13              : GCC is distributed in the hope that it will be useful,
      14              : but WITHOUT ANY WARRANTY; without even the implied warranty of
      15              : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      16              : GNU General Public License for more details.
      17              : 
      18              : You should have received a copy of the GNU General Public License
      19              : along with GCC; see the file COPYING3.  If not see
      20              : <http://www.gnu.org/licenses/>.  */
      21              : 
      22              : #include "config.h"
      23              : #include "system.h"
      24              : #include "coretypes.h"
      25              : #include "backend.h"
      26              : #include "tree.h"
      27              : #include "gimple.h"
      28              : #include "ssa.h"
      29              : #include "gimple-pretty-print.h"
      30              : #include "gimple-range.h"
      31              : 
      32              : // Return TRUE if GS is a logical && or || expression.
      33              : 
      34              : static inline bool
      35     88800475 : is_gimple_logical_p (const gimple *gs)
      36              : {
      37              :   // Look for boolean and/or condition.
      38     88800475 :   if (is_gimple_assign (gs))
      39     34674329 :     switch (gimple_expr_code (gs))
      40              :       {
      41            0 :         case TRUTH_AND_EXPR:
      42            0 :         case TRUTH_OR_EXPR:
      43            0 :           return true;
      44              : 
      45      7394985 :         case BIT_AND_EXPR:
      46      7394985 :         case BIT_IOR_EXPR:
      47              :           // Bitwise operations on single bits are logical too.
      48      7394985 :           if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)),
      49              :                                   boolean_type_node))
      50              :             return true;
      51              :           break;
      52              : 
      53              :         default:
      54              :           break;
      55              :       }
      56              :   return false;
      57              : }
      58              : 
      59              : /* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
      60              :    have range information calculated for them, and what the
      61              :    dependencies on each other are.
      62              : 
      63              :    Information for a basic block is calculated once and stored.  It is
      64              :    only calculated the first time a query is made, so if no queries
      65              :    are made, there is little overhead.
      66              : 
      67              :    The def_chain bitmap is indexed by SSA_NAME_VERSION.  Bits are set
      68              :    within this bitmap to indicate SSA names that are defined in the
      69              :    SAME block and used to calculate this SSA name.
      70              : 
      71              : 
      72              :     <bb 2> :
      73              :       _1 = x_4(D) + -2;
      74              :       _2 = _1 * 4;
      75              :       j_7 = foo ();
      76              :       q_5 = _2 + 3;
      77              :       if (q_5 <= 13)
      78              : 
      79              :     _1  : x_4(D)
      80              :     _2  : 1  x_4(D)
      81              :     q_5  : _1  _2  x_4(D)
      82              : 
      83              :     This dump indicates the bits set in the def_chain vector.
      84              :     as well as demonstrates the def_chain bits for the related ssa_names.
      85              : 
      86              :     Checking the chain for _2 indicates that _1 and x_4 are used in
      87              :     its evaluation.
      88              : 
      89              :     Def chains also only include statements which are valid gimple
      90              :     so a def chain will only span statements for which the range
      91              :     engine implements operations for.  */
      92              : 
      93              : 
      94              : // Construct a range_def_chain.
      95              : 
      96     29644007 : range_def_chain::range_def_chain ()
      97              : {
      98     29644007 :   bitmap_obstack_initialize (&m_bitmaps);
      99     29644007 :   m_def_chain.create (0);
     100     59288014 :   m_def_chain.safe_grow_cleared (num_ssa_names);
     101     29644007 :   m_logical_depth = 0;
     102     29644007 : }
     103              : 
     104              : // Destruct a range_def_chain.
     105              : 
     106     29644007 : range_def_chain::~range_def_chain ()
     107              : {
     108     29644007 :   m_def_chain.release ();
     109     29644007 :   bitmap_obstack_release (&m_bitmaps);
     110     29644007 : }
     111              : 
     112              : // Return true if NAME is in the def chain of DEF.  If BB is provided,
     113              : // only return true if the defining statement of DEF is in BB.
     114              : 
     115              : bool
     116    239519448 : range_def_chain::in_chain_p (tree name, tree def)
     117              : {
     118    239519448 :   gcc_checking_assert (gimple_range_ssa_p (def));
     119    239519448 :   gcc_checking_assert (gimple_range_ssa_p (name));
     120              : 
     121              :   // Get the definition chain for DEF.
     122    239519448 :   bitmap chain = get_def_chain (def);
     123              : 
     124    239519448 :   if (chain == NULL)
     125              :     return false;
     126    180903523 :   return bitmap_bit_p (chain, SSA_NAME_VERSION (name));
     127              : }
     128              : 
     129              : // Add either IMP or the import list B to the import set of DATA.
     130              : 
     131              : void
     132    351013353 : range_def_chain::set_import (struct rdc &data, tree imp, bitmap b)
     133              : {
     134              :   // If there are no imports, just return
     135    351013353 :   if (imp == NULL_TREE && !b)
     136              :     return;
     137    350842024 :   if (!data.m_import)
     138    156276993 :     data.m_import = BITMAP_ALLOC (&m_bitmaps);
     139    350842024 :   if (imp != NULL_TREE)
     140    305871324 :     bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp));
     141              :   else
     142     44970700 :     bitmap_ior_into (data.m_import, b);
     143              : }
     144              : 
     145              : // Return the import list for NAME.
     146              : 
     147              : bitmap
     148    183787293 : range_def_chain::get_imports (tree name)
     149              : {
     150    183787293 :   if (!has_def_chain (name))
     151    107902761 :     get_def_chain (name);
     152    183787293 :   bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import;
     153    183787293 :   return i;
     154              : }
     155              : 
     156              : // Return true if IMPORT is an import to NAMEs def chain.
     157              : 
     158              : bool
     159      7324834 : range_def_chain::chain_import_p (tree name, tree import)
     160              : {
     161      7324834 :   bitmap b = get_imports (name);
     162      7324834 :   if (b)
     163      7315423 :     return bitmap_bit_p (b, SSA_NAME_VERSION (import));
     164              :   return false;
     165              : }
     166              : 
     167              : // Build def_chains for NAME if it is in BB.  Copy the def chain into RESULT.
     168              : 
     169              : void
     170    260423298 : range_def_chain::register_dependency (tree name, tree dep, basic_block bb)
     171              : {
     172    260423298 :   if (!gimple_range_ssa_p (dep))
     173              :     return;
     174              : 
     175    221452859 :   unsigned v = SSA_NAME_VERSION (name);
     176    221452859 :   if (v >= m_def_chain.length ())
     177        14074 :     m_def_chain.safe_grow_cleared (num_ssa_names + 1);
     178    221452859 :   struct rdc &src = m_def_chain[v];
     179    221452859 :   gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
     180    221452859 :   unsigned dep_v = SSA_NAME_VERSION (dep);
     181    221452859 :   bitmap b;
     182              : 
     183              :   // Set the direct dependency cache entries.
     184    221452859 :   if (!src.ssa1)
     185    121791464 :     src.ssa1 = SSA_NAME_VERSION (dep);
     186     99661395 :   else if (!src.ssa2 && src.ssa1 != SSA_NAME_VERSION (dep))
     187     35484777 :     src.ssa2 = SSA_NAME_VERSION (dep);
     188              : 
     189              :   // Don't calculate imports or export/dep chains if BB is not provided.
     190              :   // This is usually the case for when the temporal cache wants the direct
     191              :   // dependencies of a stmt.
     192    221452859 :   if (!bb)
     193              :     return;
     194              : 
     195     76496074 :   if (!src.bm)
     196     61422364 :     src.bm = BITMAP_ALLOC (&m_bitmaps);
     197              : 
     198              :   // Add this operand into the result.
     199     76496074 :   bitmap_set_bit (src.bm, dep_v);
     200              : 
     201     76496074 :   if (gimple_bb (def_stmt) == bb && !is_a<gphi *>(def_stmt))
     202              :     {
     203              :       // Get the def chain for the operand.
     204     45142029 :       b = get_def_chain (dep);
     205              :       // If there was one, copy it into result.  Access def_chain directly
     206              :       // as the get_def_chain request above could reallocate the vector.
     207     45142029 :       if (b)
     208     27183838 :         bitmap_ior_into (m_def_chain[v].bm, b);
     209              :       // And copy the import list.
     210     45142029 :       set_import (m_def_chain[v], NULL_TREE, get_imports (dep));
     211              :     }
     212              :   else
     213              :     // Originated outside the block, so it is an import.
     214     31354045 :     set_import (src, dep, NULL);
     215              : }
     216              : 
     217              : bool
     218            0 : range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b)
     219              : {
     220            0 :   bitmap a = get_def_chain (name);
     221            0 :   if (a && b)
     222            0 :     return bitmap_intersect_p (a, b);
     223              :   return false;
     224              : }
     225              : 
     226              : void
     227    131320298 : range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name)
     228              : {
     229    131320298 :   bitmap r = get_def_chain (name);
     230    131320298 :   if (r)
     231     41375297 :     bitmap_ior_into (b, r);
     232    131320298 : }
     233              : 
     234              : 
     235              : // Return TRUE if NAME has been processed for a def_chain.
     236              : 
     237              : inline bool
     238    708024055 : range_def_chain::has_def_chain (tree name)
     239              : {
     240              :   // Ensure there is an entry in the internal vector.
     241    708024055 :   unsigned v = SSA_NAME_VERSION (name);
     242    708024055 :   if (v >= m_def_chain.length ())
     243          614 :     m_def_chain.safe_grow_cleared (num_ssa_names + 1);
     244    708024055 :   return (m_def_chain[v].ssa1 != 0);
     245              : }
     246              : 
     247              : 
     248              : 
     249              : // Calculate the def chain for NAME and all of its dependent
     250              : // operands. Only using names in the same BB.  Return the bitmap of
     251              : // all names in the m_def_chain.  This only works for supported range
     252              : // statements.
     253              : 
     254              : bitmap
     255    524236507 : range_def_chain::get_def_chain (tree name)
     256              : {
     257    524236507 :   tree ssa[3];
     258    524236507 :   unsigned v = SSA_NAME_VERSION (name);
     259              : 
     260              :   // If it has already been processed, just return the cached value.
     261    524236507 :   if (has_def_chain (name) && m_def_chain[v].bm)
     262              :     return m_def_chain[v].bm;
     263              : 
     264              :   // No definition chain for default defs.
     265    336121606 :   if (SSA_NAME_IS_DEFAULT_DEF (name))
     266              :     {
     267              :       // A Default def is always an import.
     268     17767862 :       set_import (m_def_chain[v], name, NULL);
     269     17767862 :       return NULL;
     270              :     }
     271              : 
     272    318353744 :   gimple *stmt = SSA_NAME_DEF_STMT (name);
     273    318353744 :   unsigned count = gimple_range_ssa_names (ssa, 3, stmt);
     274    318353744 :   if (count == 0)
     275              :     {
     276              :       // Stmts not understood or with no operands are always imports.
     277    256749417 :       set_import (m_def_chain[v], name, NULL);
     278    256749417 :       return NULL;
     279              :     }
     280              : 
     281              :   // Terminate the def chains if we see too many cascading stmts.
     282     61604327 :   if (m_logical_depth == param_ranger_logical_depth)
     283              :     return NULL;
     284              : 
     285              :   // Increase the depth if we have a pair of ssa-names.
     286     61422366 :   if (count > 1)
     287     15042991 :     m_logical_depth++;
     288              : 
     289    137918442 :   for (unsigned x = 0; x < count; x++)
     290     76496076 :     register_dependency (name, ssa[x], gimple_bb (stmt));
     291              : 
     292     61422366 :   if (count > 1)
     293     15042991 :     m_logical_depth--;
     294              : 
     295     61422366 :   return m_def_chain[v].bm;
     296              : }
     297              : 
     298              : // Clear def chain info for NAME.
     299              : 
     300              : void
     301       268535 : range_def_chain::clear (tree name)
     302              : {
     303       268535 :   unsigned v = SSA_NAME_VERSION (name);
     304       268535 :   if (v >= m_def_chain.length ())
     305              :     return;
     306              : 
     307       207322 :   m_def_chain[v].ssa1 = 0;
     308       207322 :   m_def_chain[v].ssa2 = 0;
     309       207322 :   m_def_chain[v].bm = NULL;
     310       207322 :   m_def_chain[v].m_import = NULL;
     311              : }
     312              : 
     313              : // Dump what we know for basic block BB to file F.
     314              : 
     315              : void
     316          118 : range_def_chain::dump (FILE *f, basic_block bb, const char *prefix)
     317              : {
     318          118 :   unsigned x, y;
     319          118 :   bitmap_iterator bi;
     320              : 
     321              :   // Dump the def chain for each SSA_NAME defined in BB.
     322         8213 :   for (x = 1; x < num_ssa_names; x++)
     323              :     {
     324         8095 :       tree name = ssa_name (x);
     325         8095 :       if (!name)
     326         3578 :         continue;
     327         4517 :       gimple *stmt = SSA_NAME_DEF_STMT (name);
     328         4517 :       if (!stmt || (bb && gimple_bb (stmt) != bb))
     329         4262 :         continue;
     330          255 :       bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL);
     331          150 :       if (chain && !bitmap_empty_p (chain))
     332              :         {
     333          132 :           fprintf (f, prefix);
     334          132 :           print_generic_expr (f, name, TDF_SLIM);
     335          132 :           fprintf (f, " : ");
     336              : 
     337          132 :           bitmap imports = get_imports (name);
     338          465 :           EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi)
     339              :             {
     340          333 :               print_generic_expr (f, ssa_name (y), TDF_SLIM);
     341          333 :               if (imports && bitmap_bit_p (imports, y))
     342          164 :                 fprintf (f, "(I)");
     343          333 :               fprintf (f, "  ");
     344              :             }
     345          132 :           fprintf (f, "\n");
     346              :         }
     347              :     }
     348          118 : }
     349              : 
     350              : 
     351              : // -------------------------------------------------------------------
     352              : 
     353              : /* GORI_MAP is used to accumulate what SSA names in a block can
     354              :    generate range information, and provides tools for the block ranger
     355              :    to enable it to efficiently calculate these ranges.
     356              : 
     357              :    GORI stands for "Generates Outgoing Range Information."
     358              : 
     359              :    It utilizes the range_def_chain class to construct def_chains.
     360              :    Information for a basic block is calculated once and stored.  It is
     361              :    only calculated the first time a query is made.  If no queries are
     362              :    made, there is little overhead.
     363              : 
     364              :    one bitmap is maintained for each basic block:
     365              :    m_outgoing  : a set bit indicates a range can be generated for a name.
     366              : 
     367              :    Generally speaking, the m_outgoing vector is the union of the
     368              :    entire def_chain of all SSA names used in the last statement of the
     369              :    block which generate ranges.  */
     370              : 
     371              : 
     372              : // Initialize a gori-map structure.
     373              : 
     374     29644007 : gori_map::gori_map ()
     375              : {
     376     29644007 :   m_outgoing.create (0);
     377     29644007 :   m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
     378     29644007 :   m_incoming.create (0);
     379     29644007 :   m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
     380     29644007 :   m_maybe_variant = BITMAP_ALLOC (&m_bitmaps);
     381     29644007 : }
     382              : 
     383              : // Free any memory the GORI map allocated.
     384              : 
     385     29644007 : gori_map::~gori_map ()
     386              : {
     387     29644007 :   m_incoming.release ();
     388     29644007 :   m_outgoing.release ();
     389     29644007 : }
     390              : 
     391              : // Return the bitmap vector of all export from BB.  Calculate if necessary.
     392              : 
     393              : bitmap
     394   1659628574 : gori_map::exports (basic_block bb)
     395              : {
     396   3319257148 :   if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
     397    339106448 :     calculate_gori (bb);
     398   1659628574 :   return m_outgoing[bb->index];
     399              : }
     400              : 
     401              : // Return the bitmap vector of all exports AND their dependencies from BB
     402              : // in TMPBIT.  Calculate if necessary.  Return TMPBIT.
     403              : 
     404              : bitmap
     405       232666 : gori_map::exports_and_deps (basic_block bb, bitmap tmpbit)
     406              : {
     407       465332 :   if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
     408            0 :     calculate_gori (bb);
     409       232666 :   bitmap_copy (tmpbit, m_outgoing[bb->index]);
     410       232666 :   if (!bitmap_empty_p (tmpbit))
     411              :     {
     412       232666 :       tree name;
     413       584487 :       FOR_EACH_GORI_EXPORT_NAME (this, bb, name)
     414              :         {
     415       351821 :           bitmap dep = get_def_chain (name);
     416       351821 :           if (dep)
     417        74475 :             bitmap_ior_into (tmpbit, dep);
     418              :         }
     419              :     }
     420       232666 :   return tmpbit;
     421              : }
     422              : 
     423              : // Return the bitmap vector of all imports to BB.  Calculate if necessary.
     424              : 
     425              : bitmap
     426      9563741 : gori_map::imports (basic_block bb)
     427              : {
     428     19127482 :   if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
     429            0 :     calculate_gori (bb);
     430      9563741 :   return m_incoming[bb->index];
     431              : }
     432              : 
     433              : // Return true if NAME is can have ranges generated for it from basic
     434              : // block BB.
     435              : 
     436              : bool
     437   2085663509 : gori_map::is_export_p (tree name, basic_block bb)
     438              : {
     439              :   // If no BB is specified, test if it is exported anywhere in the IL.
     440   2085663509 :   if (!bb)
     441    911617576 :     return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name));
     442   1174045933 :   return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
     443              : }
     444              : 
     445              : // Set or clear the m_maybe_variant bit to determine if ranges will be tracked
     446              : // for NAME.  A clear bit means they will NOT be tracked.
     447              : 
     448              : void
     449      4979905 : gori_map::set_range_invariant (tree name, bool invariant)
     450              : {
     451      4979905 :   if (invariant)
     452      1351599 :     bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
     453              :   else
     454      3628306 :     bitmap_set_bit (m_maybe_variant, SSA_NAME_VERSION (name));
     455      4979905 : }
     456              : 
     457              : // Return true if NAME is an import to block BB.
     458              : 
     459              : bool
     460            0 : gori_map::is_import_p (tree name, basic_block bb)
     461              : {
     462              :   // If no BB is specified, test if it is exported anywhere in the IL.
     463            0 :   return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name));
     464              : }
     465              : 
     466              : // If NAME is non-NULL and defined in block BB, calculate the def
     467              : // chain and add it to m_outgoing.
     468              : 
     469              : void
     470    213410904 : gori_map::maybe_add_gori (tree name, basic_block bb)
     471              : {
     472    213410904 :   if (name)
     473              :     {
     474              :       // Check if there is a def chain, regardless of the block.
     475    131320298 :       add_def_chain_to_bitmap (m_outgoing[bb->index], name);
     476              :       // Check for any imports.
     477    131320298 :       bitmap imp = get_imports (name);
     478              :       // If there were imports, add them so we can recompute
     479    131320298 :       if (imp)
     480    131319000 :         bitmap_ior_into (m_incoming[bb->index], imp);
     481              :       // This name is always an import.
     482    131320298 :       if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb)
     483     33930871 :         bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name));
     484              : 
     485              :       // Def chain doesn't include itself, and even if there isn't a
     486              :       // def chain, this name should be added to exports.
     487    131320298 :       bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name));
     488              :     }
     489    213410904 : }
     490              : 
     491              : // Calculate all the required information for BB.
     492              : 
     493              : void
     494    339106448 : gori_map::calculate_gori (basic_block bb)
     495              : {
     496    339106448 :   tree name;
     497    678212896 :   if (bb->index >= (signed int)m_outgoing.length ())
     498              :     {
     499         1329 :       m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
     500         1329 :       m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
     501              :     }
     502    339106448 :   gcc_checking_assert (m_outgoing[bb->index] == NULL);
     503    339106448 :   m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps);
     504    339106448 :   m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps);
     505              : 
     506    339106448 :   if (single_succ_p (bb))
     507              :     return;
     508              : 
     509              :   // If this block's last statement may generate range information, go
     510              :   // calculate it.
     511    175959458 :   gimple *stmt = gimple_outgoing_range_stmt_p (bb);
     512    175959458 :   if (!stmt)
     513              :     return;
     514    106954055 :   if (is_a<gcond *> (stmt))
     515              :     {
     516    106458254 :       gcond *gc = as_a<gcond *>(stmt);
     517    106458254 :       name = gimple_range_ssa_p (gimple_cond_lhs (gc));
     518    106458254 :       maybe_add_gori (name, gimple_bb (stmt));
     519              : 
     520    106458254 :       name = gimple_range_ssa_p (gimple_cond_rhs (gc));
     521    106458254 :       maybe_add_gori (name, gimple_bb (stmt));
     522              :     }
     523              :   else
     524              :     {
     525              :       // Do not process switches if they are too large.
     526       495801 :       if (EDGE_COUNT (bb->succs) > (unsigned)param_vrp_switch_limit)
     527              :         return;
     528       494396 :       gswitch *gs = as_a<gswitch *>(stmt);
     529       494396 :       name = gimple_range_ssa_p (gimple_switch_index (gs));
     530       494396 :       maybe_add_gori (name, gimple_bb (stmt));
     531              :     }
     532              :   // Add this bitmap to the aggregate list of all outgoing names.
     533    106952650 :   bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]);
     534              : }
     535              : 
     536              : // Dump the table information for BB to file F.
     537              : 
     538              : void
     539          257 : gori_map::dump (FILE *f, basic_block bb, bool verbose)
     540              : {
     541              :   // BB was not processed.
     542          257 :   if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index]))
     543              :     return;
     544              : 
     545          118 :   tree name;
     546              : 
     547          118 :   bitmap imp = imports (bb);
     548          118 :   if (!bitmap_empty_p (imp))
     549              :     {
     550          118 :       if (verbose)
     551            0 :         fprintf (f, "bb<%u> Imports: ",bb->index);
     552              :       else
     553          118 :         fprintf (f, "Imports: ");
     554          283 :       FOR_EACH_GORI_IMPORT_NAME (this, bb, name)
     555              :         {
     556          165 :           print_generic_expr (f, name, TDF_SLIM);
     557          165 :           fprintf (f, "  ");
     558              :         }
     559          118 :       fputc ('\n', f);
     560              :     }
     561              : 
     562          118 :   if (verbose)
     563            0 :     fprintf (f, "bb<%u> Exports: ",bb->index);
     564              :   else
     565          118 :     fprintf (f, "Exports: ");
     566              :   // Dump the export vector.
     567          394 :   FOR_EACH_GORI_EXPORT_NAME (this, bb, name)
     568              :     {
     569          276 :       print_generic_expr (f, name, TDF_SLIM);
     570          276 :       fprintf (f, "  ");
     571              :     }
     572          118 :   fputc ('\n', f);
     573              : 
     574          118 :   range_def_chain::dump (f, bb, "         ");
     575              : }
     576              : 
     577              : // Dump the entire GORI map structure to file F.
     578              : 
     579              : void
     580            0 : gori_map::dump (FILE *f)
     581              : {
     582            0 :   basic_block bb;
     583            0 :   FOR_EACH_BB_FN (bb, cfun)
     584            0 :     dump (f, bb);
     585            0 : }
     586              : 
     587              : DEBUG_FUNCTION void
     588            0 : debug (gori_map &g)
     589              : {
     590            0 :   g.dump (stderr);
     591            0 : }
     592              : 
     593              : // -------------------------------------------------------------------
     594              : 
     595              : // Construct a gori_compute object.
     596              : 
     597     29644007 : gori_compute::gori_compute (gori_map &map, int not_executable_flag,
     598              :                             int sw_max_edges)
     599     29644007 :   : gimple_outgoing_range (sw_max_edges), m_map (map), tracer ("GORI ")
     600              : {
     601     29644007 :   m_not_executable_flag = not_executable_flag;
     602              :   // Create a boolean_type true and false range.
     603     29644007 :   m_bool_zero = range_false ();
     604     29644007 :   m_bool_one = range_true ();
     605     29644007 :   if (dump_file && (param_ranger_debug & RANGER_DEBUG_GORI))
     606            0 :     tracer.enable_trace ();
     607              : 
     608              :   // Reduce maximum recompute depth based on the size of the CFG to avoid
     609              :   // excessive compuations in large CFGs.
     610     29644007 :   m_recompute_depth = (int) param_ranger_recompute_depth
     611     29644007 :                       - (int) last_basic_block_for_fn (cfun) / 4096;
     612     29644007 :   if (m_recompute_depth < 1)
     613            3 :     m_recompute_depth = 1;
     614     29644007 : }
     615              : 
     616     59288014 : gori_compute::~gori_compute ()
     617              : {
     618     59288014 : }
     619              : 
     620              : // Given the switch S, return an evaluation in R for NAME when the lhs
     621              : // evaluates to LHS.  Returning false means the name being looked for
     622              : // was not resolvable.
     623              : 
     624              : bool
     625       158964 : gori_compute::compute_operand_range_switch (vrange &r, gswitch *s,
     626              :                                             const vrange &lhs,
     627              :                                             tree name, fur_source &src)
     628              : {
     629       158964 :   tree op1 = gimple_switch_index (s);
     630              : 
     631              :   // If name matches, the range is simply the range from the edge.
     632              :   // Empty ranges are viral as they are on a path which isn't
     633              :   // executable.
     634       158964 :   if (op1 == name || lhs.undefined_p ())
     635              :     {
     636       115810 :       r = lhs;
     637       115810 :       return true;
     638              :     }
     639              : 
     640              :   // If op1 is in the definition chain, pass lhs back.
     641        43154 :   if (gimple_range_ssa_p (op1) && m_map.in_chain_p (name, op1))
     642        42645 :     return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src);
     643              : 
     644              :   return false;
     645              : }
     646              : 
     647              : 
     648              : // Return an evaluation for NAME as it would appear in STMT when the
     649              : // statement's lhs evaluates to LHS.  If successful, return TRUE and
     650              : // store the evaluation in R, otherwise return FALSE.
     651              : 
     652              : bool
     653    201670689 : gori_compute::compute_operand_range (vrange &r, gimple *stmt,
     654              :                                      const vrange &lhs, tree name,
     655              :                                      fur_source &src, value_relation *rel)
     656              : {
     657    201670689 :   value_relation vrel;
     658    201670689 :   value_relation *vrel_ptr = rel;
     659              :   // Empty ranges are viral as they are on an unexecutable path.
     660    201670689 :   if (lhs.undefined_p ())
     661              :     {
     662       136229 :       r.set_undefined ();
     663       136229 :       return true;
     664              :     }
     665    201534460 :   if (is_a<gswitch *> (stmt))
     666       158964 :     return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs, name,
     667       158964 :                                          src);
     668    201375496 :   gimple_range_op_handler handler (stmt);
     669    201375496 :   if (!handler)
     670              :     return false;
     671              : 
     672    201053994 :   tree op1 = gimple_range_ssa_p (handler.operand1 ());
     673    201053994 :   tree op2 = gimple_range_ssa_p (handler.operand2 ());
     674              : 
     675              :   // If there is a relation between op1 and op2, use it instead as it is
     676              :   // likely to be more applicable.
     677    201053994 :   if (op1 && op2)
     678              :     {
     679     95775969 :       value_range r1, r2;
     680     95775969 :       r1.set_varying (TREE_TYPE (op1));
     681     95775969 :       r2.set_varying (TREE_TYPE (op2));
     682     95775969 :       relation_kind k = handler.op1_op2_relation (lhs, r1, r2);
     683     95775969 :       if (k != VREL_VARYING)
     684              :         {
     685     59700590 :           vrel.set_relation (k, op1, op2);
     686     59700590 :           vrel_ptr = &vrel;
     687              :         }
     688     95775969 :     }
     689              : 
     690              :   // Handle end of lookup first.
     691    201053994 :   if (op1 == name)
     692     79904291 :     return compute_operand1_range (r, handler, lhs, src, vrel_ptr);
     693    121149703 :   if (op2 == name)
     694     28740772 :     return compute_operand2_range (r, handler, lhs, src, vrel_ptr);
     695              : 
     696              :   // NAME is not in this stmt, but one of the names in it ought to be
     697              :   // derived from it.
     698     92408931 :   bool op1_in_chain = op1 && m_map.in_chain_p (name, op1);
     699     92408931 :   bool op2_in_chain = op2 && m_map.in_chain_p (name, op2);
     700              : 
     701              :   // If neither operand is derived, then this stmt tells us nothing.
     702     70929492 :   if (!op1_in_chain && !op2_in_chain)
     703              :     return false;
     704              : 
     705              :   // If either operand is in the def chain of the other (or they are equal), it
     706              :   // will be evaluated twice and can result in an exponential time calculation.
     707              :   // Instead just evaluate the one operand.
     708     91097553 :   if (op1_in_chain && op2_in_chain)
     709              :     {
     710      4197577 :       if (m_map.in_chain_p (op1, op2) || op1 == op2)
     711              :         op1_in_chain = false;
     712      3161394 :       else if (m_map.in_chain_p (op2, op1))
     713       180642 :         op2_in_chain = false;
     714              :     }
     715              : 
     716     91097553 :   bool res = false;
     717              :   // If the lhs doesn't tell us anything only a relation can possibly enhance
     718              :   // the result.
     719     91097553 :   if (lhs.varying_p ())
     720              :     {
     721      2540924 :       if (!vrel_ptr)
     722              :         return false;
     723              :       // If there is a relation (ie: x != y) , it can only be relevant if
     724              :       // a) both elements are in the defchain
     725              :       //    c = x > y   // (x and y are in c's defchain)
     726      2139052 :       if (op1_in_chain)
     727      1428942 :         res = m_map.in_chain_p (vrel_ptr->op1 (), op1)
     728      1428942 :               && m_map.in_chain_p (vrel_ptr->op2 (), op1);
     729      2139052 :       if (!res && op2_in_chain)
     730       810472 :         res = m_map.in_chain_p (vrel_ptr->op1 (), op2)
     731       810472 :               || m_map.in_chain_p (vrel_ptr->op2 (), op2);
     732      1328580 :       if (!res)
     733              :         {
     734              :           // or b) one relation element is in the defchain of the other and the
     735              :           //       other is the LHS of this stmt.
     736              :           //  x = y + 2
     737      2113443 :           if (vrel_ptr->op1 () == handler.lhs ()
     738      2113443 :               && (vrel_ptr->op2 () == op1 || vrel_ptr->op2 () == op2))
     739              :             res = true;
     740      2024190 :           else if (vrel_ptr->op2 () == handler.lhs ()
     741      2024190 :                    && (vrel_ptr->op1 () == op1 || vrel_ptr->op1 () == op2))
     742              :             res = true;
     743              :         }
     744              :       if (!res)
     745              :         return false;
     746              :     }
     747              : 
     748              :   // Process logicals as they have special handling.
     749     88799017 :   if (is_gimple_logical_p (stmt))
     750              :     {
     751              :       // If the lhs doesn't tell us anything, neither will combining operands.
     752      5429660 :       if (lhs.varying_p ())
     753              :         return false;
     754              : 
     755      5429660 :       unsigned idx;
     756      5429660 :       if ((idx = tracer.header ("compute_operand ")))
     757              :         {
     758            0 :           print_generic_expr (dump_file, name, TDF_SLIM);
     759            0 :           fprintf (dump_file, " with LHS = ");
     760            0 :           lhs.dump (dump_file);
     761            0 :           fprintf (dump_file, " at stmt ");
     762            0 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
     763              :         }
     764              : 
     765      5429660 :       tree type = TREE_TYPE (name);
     766      5429660 :       value_range op1_trange (type), op1_frange (type);
     767      5429660 :       value_range op2_trange (type), op2_frange (type);
     768      5429660 :       compute_logical_operands (op1_trange, op1_frange, handler,
     769              :                                 as_a <irange> (lhs),
     770              :                                 name, src, op1, op1_in_chain);
     771      5429660 :       compute_logical_operands (op2_trange, op2_frange, handler,
     772              :                                 as_a <irange> (lhs),
     773              :                                 name, src, op2, op2_in_chain);
     774      5429660 :       res = logical_combine (r,
     775              :                              gimple_expr_code (stmt),
     776              :                              as_a <irange> (lhs),
     777      5429660 :                              op1_trange, op1_frange, op2_trange, op2_frange);
     778      5429660 :       if (idx)
     779            0 :         tracer.trailer (idx, "compute_operand", res, name, r);
     780      5429660 :       return res;
     781      5429660 :     }
     782              :   // Follow the appropriate operands now.
     783     83369357 :   if (op1_in_chain && op2_in_chain)
     784       981663 :     return compute_operand1_and_operand2_range (r, handler, lhs, name, src,
     785       981663 :                                                 vrel_ptr);
     786     82387694 :   value_range vr;
     787     82387694 :   gimple *src_stmt;
     788     82387694 :   if (op1_in_chain)
     789              :     {
     790     66695464 :       vr.set_range_class (TREE_TYPE (op1));
     791     66695464 :       if (!compute_operand1_range (vr, handler, lhs, src, vrel_ptr))
     792              :         return false;
     793     64953982 :       src_stmt = SSA_NAME_DEF_STMT (op1);
     794              :     }
     795              :   else
     796              :     {
     797     15692230 :       gcc_checking_assert (op2_in_chain);
     798     15692230 :       vr.set_range_class (TREE_TYPE (op2));
     799     15692230 :       if (!compute_operand2_range (vr, handler, lhs, src, vrel_ptr))
     800              :         return false;
     801     15089579 :       src_stmt = SSA_NAME_DEF_STMT (op2);
     802              :     }
     803              : 
     804     80043561 :   gcc_checking_assert (src_stmt);
     805              :   // Then feed this range back as the LHS of the defining statement.
     806     80043561 :   return compute_operand_range (r, src_stmt, vr, name, src, vrel_ptr);
     807              :   // If neither operand is derived, this statement tells us nothing.
     808     82387694 : }
     809              : 
     810              : 
     811              : // Return TRUE if range R is either a true or false compatible range.
     812              : 
     813              : static bool
     814      4446991 : range_is_either_true_or_false (const irange &r)
     815              : {
     816      4446991 :   if (r.undefined_p ())
     817              :     return false;
     818              : 
     819              :   // This is complicated by the fact that Ada has multi-bit booleans,
     820              :   // so true can be ~[0, 0] (i.e. [1,MAX]).
     821      4446991 :   tree type = r.type ();
     822      4446991 :   gcc_checking_assert (range_compatible_p (type, boolean_type_node));
     823      4446991 :   return (r.singleton_p ()
     824      4446991 :           || !r.contains_p (wi::zero (TYPE_PRECISION (type))));
     825              : }
     826              : 
     827              : // Evaluate a binary logical expression by combining the true and
     828              : // false ranges for each of the operands based on the result value in
     829              : // the LHS.
     830              : 
     831              : bool
     832      5429660 : gori_compute::logical_combine (vrange &r, enum tree_code code,
     833              :                                const irange &lhs,
     834              :                                const vrange &op1_true, const vrange &op1_false,
     835              :                                const vrange &op2_true, const vrange &op2_false)
     836              : {
     837      5429660 :   if (op1_true.varying_p () && op1_false.varying_p ()
     838      7163737 :       && op2_true.varying_p () && op2_false.varying_p ())
     839              :     return false;
     840              : 
     841      4446991 :   unsigned idx;
     842      4446991 :   if ((idx = tracer.header ("logical_combine")))
     843              :     {
     844            0 :       switch (code)
     845              :         {
     846            0 :           case TRUTH_OR_EXPR:
     847            0 :           case BIT_IOR_EXPR:
     848            0 :             fprintf (dump_file, " || ");
     849            0 :             break;
     850            0 :           case TRUTH_AND_EXPR:
     851            0 :           case BIT_AND_EXPR:
     852            0 :             fprintf (dump_file, " && ");
     853            0 :             break;
     854              :           default:
     855              :             break;
     856              :         }
     857            0 :       fprintf (dump_file, " with LHS = ");
     858            0 :       lhs.dump (dump_file);
     859            0 :       fputc ('\n', dump_file);
     860              : 
     861            0 :       tracer.print (idx, "op1_true = ");
     862            0 :       op1_true.dump (dump_file);
     863            0 :       fprintf (dump_file, "  op1_false = ");
     864            0 :       op1_false.dump (dump_file);
     865            0 :       fputc ('\n', dump_file);
     866            0 :       tracer.print (idx, "op2_true = ");
     867            0 :       op2_true.dump (dump_file);
     868            0 :       fprintf (dump_file, "  op2_false = ");
     869            0 :       op2_false.dump (dump_file);
     870            0 :       fputc ('\n', dump_file);
     871              :     }
     872              : 
     873              :   // This is not a simple fold of a logical expression, rather it
     874              :   // determines ranges which flow through the logical expression.
     875              :   //
     876              :   // Assuming x_8 is an unsigned char, and relational statements:
     877              :   //          b_1 = x_8 < 20
     878              :   //          b_2 = x_8 > 5
     879              :   // consider the logical expression and branch:
     880              :   //          c_2 = b_1 && b_2
     881              :   //          if (c_2)
     882              :   //
     883              :   // To determine the range of x_8 on either edge of the branch, one
     884              :   // must first determine what the range of x_8 is when the boolean
     885              :   // values of b_1 and b_2 are both true and false.
     886              :   //    b_1 TRUE      x_8 = [0, 19]
     887              :   //    b_1 FALSE     x_8 = [20, 255]
     888              :   //    b_2 TRUE      x_8 = [6, 255]
     889              :   //    b_2 FALSE     x_8 = [0,5].
     890              :   //
     891              :   // These ranges are then combined based on the expected outcome of
     892              :   // the branch.  The range on the TRUE side of the branch must satisfy
     893              :   //     b_1 == true && b_2 == true
     894              :   //
     895              :   // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
     896              :   // must be true.  The range of x_8 on the true side must be the
     897              :   // intersection of both ranges since both must be true.  Thus the
     898              :   // range of x_8 on the true side is [6, 19].
     899              :   //
     900              :   // To determine the ranges on the FALSE side, all 3 combinations of
     901              :   // failing ranges must be considered, and combined as any of them
     902              :   // can cause the false result.
     903              :   //
     904              :   // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
     905              :   // FALSE results and combine them.  If we fell back to VARYING any
     906              :   // range restrictions that have been discovered up to this point
     907              :   // would be lost.
     908      4446991 :   if (!range_is_either_true_or_false (lhs))
     909              :     {
     910            0 :       bool res;
     911            0 :       value_range r1 (r);
     912            0 :       if (logical_combine (r1, code, m_bool_zero, op1_true, op1_false,
     913              :                            op2_true, op2_false)
     914            0 :           && logical_combine (r, code, m_bool_one, op1_true, op1_false,
     915              :                               op2_true, op2_false))
     916              :         {
     917            0 :           r.union_ (r1);
     918            0 :           res = true;
     919              :         }
     920              :       else
     921              :         res = false;
     922            0 :       if (idx && res)
     923              :         {
     924            0 :           tracer.print (idx, "logical_combine produced ");
     925            0 :           r.dump (dump_file);
     926            0 :           fputc ('\n', dump_file);
     927              :         }
     928            0 :       return res;
     929            0 :     }
     930              : 
     931      4446991 :   switch (code)
     932              :     {
     933              :       //  A logical AND combines ranges from 2 boolean conditions.
     934              :       //       c_2 = b_1 && b_2
     935      2967025 :       case TRUTH_AND_EXPR:
     936      2967025 :       case BIT_AND_EXPR:
     937      2967025 :         if (!lhs.zero_p ())
     938              :           {
     939              :             // The TRUE side is the intersection of the 2 true ranges.
     940      1894199 :             r = op1_true;
     941      1894199 :             r.intersect (op2_true);
     942              :           }
     943              :         else
     944              :           {
     945              :             // The FALSE side is the union of the other 3 cases.
     946      1072826 :             value_range ff (op1_false);
     947      1072826 :             ff.intersect (op2_false);
     948      1072826 :             value_range tf (op1_true);
     949      1072826 :             tf.intersect (op2_false);
     950      1072826 :             value_range ft (op1_false);
     951      1072826 :             ft.intersect (op2_true);
     952      1072826 :             r = ff;
     953      1072826 :             r.union_ (tf);
     954      1072826 :             r.union_ (ft);
     955      1072826 :           }
     956              :         break;
     957              :       //  A logical OR combines ranges from 2 boolean conditions.
     958              :       //        c_2 = b_1 || b_2
     959      1479966 :       case TRUTH_OR_EXPR:
     960      1479966 :       case BIT_IOR_EXPR:
     961      1479966 :         if (lhs.zero_p ())
     962              :           {
     963              :             // An OR operation will only take the FALSE path if both
     964              :             // operands are false simultaneously, which means they should
     965              :             // be intersected.  !(x || y) == !x && !y
     966      1043348 :             r = op1_false;
     967      1043348 :             r.intersect (op2_false);
     968              :           }
     969              :         else
     970              :           {
     971              :             // The TRUE side of an OR operation will be the union of
     972              :             // the other three combinations.
     973       436618 :             value_range tt (op1_true);
     974       436618 :             tt.intersect (op2_true);
     975       436618 :             value_range tf (op1_true);
     976       436618 :             tf.intersect (op2_false);
     977       436618 :             value_range ft (op1_false);
     978       436618 :             ft.intersect (op2_true);
     979       436618 :             r = tt;
     980       436618 :             r.union_ (tf);
     981       436618 :             r.union_ (ft);
     982       436618 :           }
     983              :         break;
     984            0 :       default:
     985            0 :         gcc_unreachable ();
     986              :     }
     987              : 
     988      4446991 :   if (idx)
     989            0 :     tracer.trailer (idx, "logical_combine", true, NULL_TREE, r);
     990              :   return true;
     991              : }
     992              : 
     993              : 
     994              : // Given a logical STMT, calculate true and false ranges for each
     995              : // potential path of NAME, assuming NAME came through the OP chain if
     996              : // OP_IN_CHAIN is true.
     997              : 
     998              : void
     999     10859320 : gori_compute::compute_logical_operands (vrange &true_range, vrange &false_range,
    1000              :                                         gimple_range_op_handler &handler,
    1001              :                                         const irange &lhs,
    1002              :                                         tree name, fur_source &src,
    1003              :                                         tree op, bool op_in_chain)
    1004              : {
    1005     10859320 :   gimple *stmt = handler.stmt ();
    1006     21718640 :   gimple *src_stmt = gimple_range_ssa_p (op) ? SSA_NAME_DEF_STMT (op) : NULL;
    1007     10859320 :   if (!op_in_chain || !src_stmt || m_map.chain_import_p (handler.lhs (), op))
    1008              :     {
    1009              :       // If op is not in the def chain, or defined in this block,
    1010              :       // use its known value on entry to the block.
    1011      3579642 :       src.get_operand (true_range, name);
    1012      3579642 :       false_range = true_range;
    1013      3579642 :       unsigned idx;
    1014      3579642 :       if ((idx = tracer.header ("logical_operand")))
    1015              :         {
    1016            0 :           print_generic_expr (dump_file, op, TDF_SLIM);
    1017            0 :           fprintf (dump_file, " not in computation chain. Queried.\n");
    1018            0 :           tracer.trailer (idx, "logical_operand", true, NULL_TREE, true_range);
    1019              :         }
    1020              :       return;
    1021              :     }
    1022              : 
    1023      7279678 :   enum tree_code code = gimple_expr_code (stmt);
    1024              :   // Optimize [0 = x | y], since neither operand can ever be non-zero.
    1025      7279678 :   if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ())
    1026              :     {
    1027      1692494 :       if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name,
    1028              :                                   src))
    1029       148416 :         src.get_operand (false_range, name);
    1030      1692494 :       true_range = false_range;
    1031      1692494 :       return;
    1032              :     }
    1033              : 
    1034              :   // Optimize [1 = x & y], since neither operand can ever be zero.
    1035      5587184 :   if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one)
    1036              :     {
    1037      3448904 :       if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
    1038       230090 :         src.get_operand (true_range, name);
    1039      3448904 :       false_range = true_range;
    1040      3448904 :       return;
    1041              :     }
    1042              : 
    1043              :   // Calculate ranges for true and false on both sides, since the false
    1044              :   // path is not always a simple inversion of the true side.
    1045      2138280 :   if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src))
    1046       152079 :     src.get_operand (true_range, name);
    1047      2138280 :   if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, src))
    1048       153142 :     src.get_operand (false_range, name);
    1049              : }
    1050              : 
    1051              : 
    1052              : // This routine will try to refine the ranges of OP1 and OP2 given a relation
    1053              : // K between them.  In order to perform this refinement, one of the operands
    1054              : // must be in the definition chain of the other.  The use is refined using
    1055              : // op1/op2_range on the statement, and the definition is then recalculated
    1056              : // using the relation.
    1057              : 
    1058              : bool
    1059     59687204 : gori_compute::refine_using_relation (tree op1, vrange &op1_range,
    1060              :                                tree op2, vrange &op2_range,
    1061              :                                fur_source &src, relation_kind k)
    1062              : {
    1063     59687204 :   gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
    1064     59687204 :   gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
    1065              : 
    1066     59687204 :   if (k == VREL_VARYING || k == VREL_EQ || k == VREL_UNDEFINED)
    1067              :     return false;
    1068              : 
    1069     50280996 :   bool change = false;
    1070     50280996 :   bool op1_def_p = m_map.in_chain_p (op2, op1);
    1071     50280996 :   if (!op1_def_p)
    1072     48907988 :     if (!m_map.in_chain_p (op1, op2))
    1073              :       return false;
    1074              : 
    1075      3320789 :   tree def_op = op1_def_p ? op1 : op2;
    1076              :   tree use_op = op1_def_p ? op2 : op1;
    1077              : 
    1078      3320789 :   if (!op1_def_p)
    1079      3320789 :     k = relation_swap (k);
    1080              : 
    1081              :   // op1_def is true if we want to look up op1, otherwise we want op2.
    1082              :   // if neither is the case, we returned in the above check.
    1083              : 
    1084      4693797 :   gimple *def_stmt = SSA_NAME_DEF_STMT (def_op);
    1085      4693797 :   gimple_range_op_handler op_handler (def_stmt);
    1086      4693797 :   if (!op_handler)
    1087              :     return false;
    1088      4690667 :   tree def_op1 = op_handler.operand1 ();
    1089      4690667 :   tree def_op2 = op_handler.operand2 ();
    1090              :   // if the def isn't binary, the relation will not be useful.
    1091      4690667 :   if (!def_op2)
    1092              :     return false;
    1093              : 
    1094              :   // Determine if op2 is directly referenced as an operand.
    1095      4611638 :   if (def_op1 == use_op)
    1096              :     {
    1097              :       // def_stmt has op1 in the 1st operand position.
    1098      1395365 :       value_range other_op (TREE_TYPE (def_op2));
    1099      1395365 :       src.get_operand (other_op, def_op2);
    1100              : 
    1101              :       // Using op1_range as the LHS, and relation REL, evaluate op2.
    1102      1395365 :       tree type = TREE_TYPE (def_op1);
    1103      1395365 :       value_range new_result (type);
    1104      2439419 :       if (!op_handler.op1_range (new_result, type,
    1105              :                                  op1_def_p ? op1_range : op2_range,
    1106      1395365 :                                  other_op, relation_trio::lhs_op1 (k)))
    1107        94266 :         return false;
    1108              :       // Note: K arrives as an op1/op2 relation, and because of
    1109              :       // the definition chain requirement here, it is also an LHS relation on the
    1110              :       // defining statement, which is how it is passed to the range operators below.
    1111      1301099 :       if (op1_def_p)
    1112              :         {
    1113       321497 :           change |= op2_range.intersect (new_result);
    1114              :           // Recalculate the LHS passing the lhs-op1 relation so that
    1115              :           // operator_plus::fold_range can tighten the no-overflow range.
    1116       321497 :           if (op_handler.fold_range (new_result, type, op2_range, other_op,
    1117              :                                      relation_trio::lhs_op1 (k)))
    1118              :             {
    1119       321497 :               change |= op1_range.intersect (new_result);
    1120              :             }
    1121              :         }
    1122              :       else
    1123              :         {
    1124       979602 :           change |= op1_range.intersect (new_result);
    1125              :           // Recalculate the LHS passing the lhs-op1 relation.
    1126       979602 :           if (op_handler.fold_range (new_result, type, op1_range, other_op,
    1127              :                                      relation_trio::lhs_op1 (k)))
    1128              :             {
    1129       979602 :               change |= op2_range.intersect (new_result);
    1130              :             }
    1131              :         }
    1132      1395365 :     }
    1133      3216273 :   else if (def_op2 == use_op)
    1134              :     {
    1135              :       // def_stmt has op1 in the 1st operand position.
    1136      2128829 :       value_range other_op (TREE_TYPE (def_op1));
    1137      2128829 :       src.get_operand (other_op, def_op1);
    1138              : 
    1139              :       // Using op1_range as the LHS, and relation REL, evaluate op2.
    1140      2128829 :       tree type = TREE_TYPE (def_op2);
    1141      2128829 :       value_range new_result (type);
    1142      3961153 :       if (!op_handler.op2_range (new_result, type,
    1143              :                                  op1_def_p ? op1_range : op2_range,
    1144      2128829 :                                  other_op, relation_trio::lhs_op2 (k)))
    1145        97951 :         return false;
    1146              :       // Note: K arrives as an op1/op2 relation, and because of
    1147              :       // the definition chain requirement here, it is also an LHS relation on the
    1148              :       // defining statement, which is how it is passed to the range operators below.
    1149      2030878 :       if (op1_def_p)
    1150              :         {
    1151       290321 :           change |= op2_range.intersect (new_result);
    1152              :           // Recalculate the LHS passing the lhs-op2 relation.
    1153       290321 :           if (op_handler.fold_range (new_result, type, other_op, op2_range,
    1154              :                                      relation_trio::lhs_op2 (k)))
    1155              :             {
    1156       290321 :               change |= op1_range.intersect (new_result);
    1157              :             }
    1158              :         }
    1159              :       else
    1160              :         {
    1161      1740557 :           change |= op1_range.intersect (new_result);
    1162              :           // Recalculate the LHS passing the lhs-op2 relation.
    1163      1740557 :           if (op_handler.fold_range (new_result, type, other_op, op1_range,
    1164              :                                      relation_trio::lhs_op2 (k)))
    1165              :             {
    1166      1740557 :               change |= op2_range.intersect (new_result);
    1167              :             }
    1168              :         }
    1169      2128829 :     }
    1170              :   return change;
    1171              : }
    1172              : 
    1173              : // Calculate a range for NAME from the operand 1 position of STMT
    1174              : // assuming the result of the statement is LHS.  Return the range in
    1175              : // R, or false if no range could be calculated.
    1176              : 
    1177              : bool
    1178    147008443 : gori_compute::compute_operand1_range (vrange &r,
    1179              :                                       gimple_range_op_handler &handler,
    1180              :                                       const vrange &lhs,
    1181              :                                       fur_source &src, value_relation *rel)
    1182              : {
    1183    147008443 :   gimple *stmt = handler.stmt ();
    1184    147008443 :   tree op1 = handler.operand1 ();
    1185    147008443 :   tree op2 = handler.operand2 ();
    1186    147008443 :   tree lhs_name = gimple_get_lhs (stmt);
    1187              : 
    1188    147008443 :   relation_trio trio;
    1189    147008443 :   if (rel)
    1190     53008393 :     trio = rel->create_trio (lhs_name, op1, op2);
    1191              : 
    1192    147008443 :   value_range op1_range (TREE_TYPE (op1));
    1193    147008443 :   value_range op2_range (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1));
    1194              : 
    1195              :   // Fetch the known range for op1 in this block.
    1196    147008443 :   src.get_operand (op1_range, op1);
    1197              : 
    1198              :   // Now range-op calculate and put that result in r.
    1199    147008443 :   if (op2)
    1200              :     {
    1201    128584725 :       src.get_operand (op2_range, op2);
    1202              : 
    1203    128584725 :       relation_kind op_op = trio.op1_op2 ();
    1204    128584725 :       if (op_op != VREL_VARYING)
    1205     30075017 :         refine_using_relation (op1, op1_range, op2, op2_range, src, op_op);
    1206              : 
    1207              :       // If op1 == op2, create a new trio for just this call.
    1208    128584725 :       if (op1 == op2 && gimple_range_ssa_p (op1))
    1209       137697 :         trio = relation_trio (trio.lhs_op1 (), trio.lhs_op2 (), VREL_EQ);
    1210    128584725 :       if (!handler.calc_op1 (r, lhs, op2_range, trio))
    1211              :         return false;
    1212              :     }
    1213              :   else
    1214              :     {
    1215              :       // We pass op1_range to the unary operation.  Normally it's a
    1216              :       // hidden range_for_type parameter, but sometimes having the
    1217              :       // actual range can result in better information.
    1218     18423718 :       if (!handler.calc_op1 (r, lhs, op1_range, trio))
    1219              :         return false;
    1220              :     }
    1221              : 
    1222    140428235 :   unsigned idx;
    1223    140428235 :   if ((idx = tracer.header ("compute op 1 (")))
    1224              :     {
    1225            0 :       print_generic_expr (dump_file, op1, TDF_SLIM);
    1226            0 :       fprintf (dump_file, ") at ");
    1227            0 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1228            0 :       tracer.print (idx, "LHS =");
    1229            0 :       lhs.dump (dump_file);
    1230            0 :       if (op2 && TREE_CODE (op2) == SSA_NAME)
    1231              :         {
    1232            0 :           fprintf (dump_file, ", ");
    1233            0 :           print_generic_expr (dump_file, op2, TDF_SLIM);
    1234            0 :           fprintf (dump_file, " = ");
    1235            0 :           op2_range.dump (dump_file);
    1236              :         }
    1237            0 :       fprintf (dump_file, "\n");
    1238            0 :       tracer.print (idx, "Computes ");
    1239            0 :       print_generic_expr (dump_file, op1, TDF_SLIM);
    1240            0 :       fprintf (dump_file, " = ");
    1241            0 :       r.dump (dump_file);
    1242            0 :       fprintf (dump_file, " intersect Known range : ");
    1243            0 :       op1_range.dump (dump_file);
    1244            0 :       fputc ('\n', dump_file);
    1245              :     }
    1246              : 
    1247    140428235 :   r.intersect (op1_range);
    1248    140428235 :   if (idx)
    1249            0 :     tracer.trailer (idx, "produces ", true, op1, r);
    1250              :   return true;
    1251    147008443 : }
    1252              : 
    1253              : 
    1254              : // Calculate a range for NAME from the operand 2 position of S
    1255              : // assuming the result of the statement is LHS.  Return the range in
    1256              : // R, or false if no range could be calculated.
    1257              : 
    1258              : bool
    1259     45414665 : gori_compute::compute_operand2_range (vrange &r,
    1260              :                                       gimple_range_op_handler &handler,
    1261              :                                       const vrange &lhs,
    1262              :                                       fur_source &src, value_relation *rel)
    1263              : {
    1264     45414665 :   gimple *stmt = handler.stmt ();
    1265     45414665 :   tree op1 = handler.operand1 ();
    1266     45414665 :   tree op2 = handler.operand2 ();
    1267     45414665 :   tree lhs_name = gimple_get_lhs (stmt);
    1268              : 
    1269     45414665 :   value_range op1_range (TREE_TYPE (op1));
    1270     45414665 :   value_range op2_range (TREE_TYPE (op2));
    1271              : 
    1272     45414665 :   src.get_operand (op1_range, op1);
    1273     45414665 :   src.get_operand (op2_range, op2);
    1274              : 
    1275     45414665 :   relation_trio trio;
    1276     45414665 :   if (rel)
    1277     36696855 :     trio = rel->create_trio (lhs_name, op1, op2);
    1278     45414665 :   relation_kind op_op = trio.op1_op2 ();
    1279              : 
    1280     45414665 :   if (op_op != VREL_VARYING)
    1281     29612187 :     refine_using_relation (op1, op1_range, op2, op2_range, src, op_op);
    1282              : 
    1283              :   // If op1 == op2, create a new trio for this stmt.
    1284     45414665 :   if (op1 == op2 && gimple_range_ssa_p (op1))
    1285        36422 :     trio = relation_trio (trio.lhs_op1 (), trio.lhs_op2 (), VREL_EQ);
    1286              :   // Intersect with range for op2 based on lhs and op1.
    1287     45414665 :   if (!handler.calc_op2 (r, lhs, op1_range, trio))
    1288              :     return false;
    1289              : 
    1290     40371708 :   unsigned idx;
    1291     40371708 :   if ((idx = tracer.header ("compute op 2 (")))
    1292              :     {
    1293            0 :       print_generic_expr (dump_file, op2, TDF_SLIM);
    1294            0 :       fprintf (dump_file, ") at ");
    1295            0 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1296            0 :       tracer.print (idx, "LHS = ");
    1297            0 :       lhs.dump (dump_file);
    1298            0 :       if (TREE_CODE (op1) == SSA_NAME)
    1299              :         {
    1300            0 :           fprintf (dump_file, ", ");
    1301            0 :           print_generic_expr (dump_file, op1, TDF_SLIM);
    1302            0 :           fprintf (dump_file, " = ");
    1303            0 :           op1_range.dump (dump_file);
    1304              :         }
    1305            0 :       fprintf (dump_file, "\n");
    1306            0 :       tracer.print (idx, "Computes ");
    1307            0 :       print_generic_expr (dump_file, op2, TDF_SLIM);
    1308            0 :       fprintf (dump_file, " = ");
    1309            0 :       r.dump (dump_file);
    1310            0 :       fprintf (dump_file, " intersect Known range : ");
    1311            0 :       op2_range.dump (dump_file);
    1312            0 :       fputc ('\n', dump_file);
    1313              :     }
    1314              :   // Intersect the calculated result with the known result and return if done.
    1315     40371708 :   r.intersect (op2_range);
    1316     40371708 :   if (idx)
    1317            0 :     tracer.trailer (idx, " produces ", true, op2, r);
    1318              :   return true;
    1319     45414665 : }
    1320              : 
    1321              : // Calculate a range for NAME from both operand positions of S
    1322              : // assuming the result of the statement is LHS.  Return the range in
    1323              : // R, or false if no range could be calculated.
    1324              : 
    1325              : bool
    1326       981663 : gori_compute::compute_operand1_and_operand2_range (vrange &r,
    1327              :                                                    gimple_range_op_handler
    1328              :                                                                      &handler,
    1329              :                                                    const vrange &lhs,
    1330              :                                                    tree name,
    1331              :                                                    fur_source &src,
    1332              :                                                    value_relation *rel)
    1333              : {
    1334       981663 :   value_range op_range (TREE_TYPE (name));
    1335              : 
    1336       981663 :   value_range vr (TREE_TYPE (handler.operand2 ()));
    1337              :   // Calculate a good a range through op2.
    1338       981663 :   if (!compute_operand2_range (vr, handler, lhs, src, rel))
    1339              :     return false;
    1340       957810 :   gimple *src_stmt = SSA_NAME_DEF_STMT (handler.operand2 ());
    1341       957810 :   gcc_checking_assert (src_stmt);
    1342              :   // Then feed this range back as the LHS of the defining statement.
    1343       957810 :   if (!compute_operand_range (r, src_stmt, vr, name, src, rel))
    1344              :     return false;
    1345              : 
    1346              :   // Now get the range thru op1.
    1347       408688 :   vr.set_range_class (TREE_TYPE (handler.operand1 ()));
    1348       408688 :   if (!compute_operand1_range (vr, handler, lhs, src, rel))
    1349              :     return false;
    1350       405793 :   src_stmt = SSA_NAME_DEF_STMT (handler.operand1 ());
    1351       405793 :   gcc_checking_assert (src_stmt);
    1352              :   // Then feed this range back as the LHS of the defining statement.
    1353       405793 :   if (!compute_operand_range (op_range, src_stmt, vr, name, src, rel))
    1354              :     return false;
    1355              : 
    1356              :   // Both operands have to be simultaneously true, so perform an intersection.
    1357       284216 :   r.intersect (op_range);
    1358       284216 :   return true;
    1359       981663 : }
    1360              : 
    1361              : // Return TRUE if NAME can be recomputed on any edge exiting BB.  If any
    1362              : // direct dependent is exported, it may also change the computed value of NAME.
    1363              : 
    1364              : bool
    1365   1303858989 : gori_compute::may_recompute_p (tree name, basic_block bb, int depth)
    1366              : {
    1367   1303858989 :   tree dep1 = m_map.depend1 (name);
    1368   1303858989 :   tree dep2 = m_map.depend2 (name);
    1369              : 
    1370              :   // If the first dependency is not set, there is no recomputation.
    1371              :   // Dependencies reflect original IL, not current state.   Check if the
    1372              :   // SSA_NAME is still valid as well.
    1373   1303858989 :   if (!dep1)
    1374              :     return false;
    1375              : 
    1376              :   // Only recalculate range-op statements that are recomputable.
    1377   1016321149 :   gimple *s = SSA_NAME_DEF_STMT (name);
    1378   1016321149 :   gimple_range_op_handler handler (s);
    1379   1016321149 :   if (!handler || !handler.recomputable_p ())
    1380              :     return false;
    1381              : 
    1382    595355790 :   if (!dep2)
    1383              :     {
    1384              :       // -1 indicates a default param, convert it to the real default.
    1385    524976312 :       if (depth == -1)
    1386    455693013 :         depth = m_recompute_depth;
    1387              : 
    1388    524976312 :       bool res = m_map.is_export_p (dep1, bb);
    1389    524976312 :       if (res || depth <= 1)
    1390              :         return res;
    1391              :       // Check another level of recomputation.
    1392    471554974 :       return may_recompute_p (dep1, bb, --depth);
    1393              :     }
    1394              :   // Two dependencies terminate the depth of the search.
    1395     70379478 :   return m_map.is_export_p (dep1, bb) || m_map.is_export_p (dep2, bb);
    1396              : }
    1397              : 
    1398              : // Return TRUE if NAME can be recomputed on edge E.  If any direct dependent
    1399              : // is exported on edge E, it may change the computed value of NAME.
    1400              : 
    1401              : bool
    1402     38000308 : gori_compute::may_recompute_p (tree name, edge e, int depth)
    1403              : {
    1404     38000308 :   gcc_checking_assert (e);
    1405     38000308 :   return may_recompute_p (name, e->src, depth);
    1406              : }
    1407              : 
    1408              : 
    1409              : // Return TRUE if a range can be calculated or recomputed for NAME on any
    1410              : // edge exiting BB.
    1411              : 
    1412              : bool
    1413   1246719012 : gori_compute::has_edge_range_p (tree name, basic_block bb)
    1414              : {
    1415              :   // Check if NAME is an export or can be recomputed.
    1416   1246719012 :   if (bb)
    1417    573106200 :     return m_map.is_export_p (name, bb) || may_recompute_p (name, bb);
    1418              : 
    1419              :   // If no block is specified, check for anywhere in the IL.
    1420    673612812 :   return m_map.is_export_p (name) || may_recompute_p (name);
    1421              : }
    1422              : 
    1423              : // Return TRUE if a range can be calculated or recomputed for NAME on edge E.
    1424              : 
    1425              : bool
    1426      1814164 : gori_compute::has_edge_range_p (tree name, edge e)
    1427              : {
    1428      1814164 :   gcc_checking_assert (e);
    1429      1814164 :   return has_edge_range_p (name, e->src);
    1430              : }
    1431              : 
    1432              : // Calculate a range on edge E and return it in R.  Try to evaluate a
    1433              : // range for NAME on this edge.  Return FALSE if this is either not a
    1434              : // control edge or NAME is not defined by this edge.
    1435              : 
    1436              : bool
    1437    202403370 : gori_compute::edge_range_p (vrange &r, edge e, tree name, range_query &q)
    1438              : {
    1439    202403370 :   unsigned idx;
    1440              : 
    1441    202403370 :   if ((e->flags & m_not_executable_flag))
    1442              :     {
    1443        45223 :       r.set_undefined ();
    1444        45223 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1445           24 :           fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n",
    1446           24 :                    e->src->index, e->dest->index);
    1447              :       return true;
    1448              :     }
    1449              : 
    1450    202358147 :   gcc_checking_assert (gimple_range_ssa_p (name));
    1451    202358147 :   int_range_max lhs;
    1452              :   // Determine if there is an outgoing edge.
    1453    202358147 :   gimple *stmt = gimple_outgoing_range::edge_range_p (lhs, e);
    1454    202358147 :   if (!stmt)
    1455              :     return false;
    1456              : 
    1457    148800802 :   fur_stmt src (stmt, &q);
    1458              :   // If NAME can be calculated on the edge, use that.
    1459    148800802 :   if (m_map.is_export_p (name, e->src))
    1460              :     {
    1461    110800494 :       bool res;
    1462    110800494 :       if ((idx = tracer.header ("outgoing_edge")))
    1463              :         {
    1464            0 :           fprintf (dump_file, " for ");
    1465            0 :           print_generic_expr (dump_file, name, TDF_SLIM);
    1466            0 :           fprintf (dump_file, " on edge %d->%d\n",
    1467            0 :                    e->src->index, e->dest->index);
    1468              :         }
    1469    110800494 :       if ((res = compute_operand_range (r, stmt, lhs, name, src)))
    1470              :         {
    1471              :           // Sometimes compatible types get interchanged. See PR97360.
    1472              :           // Make sure we are returning the type of the thing we asked for.
    1473     94947084 :           if (!r.undefined_p () && r.type () != TREE_TYPE (name))
    1474              :             {
    1475      5151678 :               gcc_checking_assert (range_compatible_p (r.type (),
    1476              :                                                        TREE_TYPE (name)));
    1477      5151678 :               range_cast (r, TREE_TYPE (name));
    1478              :             }
    1479              :         }
    1480    110800494 :       if (idx)
    1481            0 :         tracer.trailer (idx, "outgoing_edge", res, name, r);
    1482              :       return res;
    1483              :     }
    1484              :   // If NAME isn't exported, check if it can be recomputed.
    1485     38000308 :   else if (may_recompute_p (name, e))
    1486              :     {
    1487      9562396 :       gimple *def_stmt = SSA_NAME_DEF_STMT (name);
    1488              : 
    1489      9562396 :       if ((idx = tracer.header ("recomputation")))
    1490              :         {
    1491            0 :           fprintf (dump_file, " attempt on edge %d->%d for ",
    1492            0 :                    e->src->index, e->dest->index);
    1493            0 :           print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
    1494              :         }
    1495              :       // Simply calculate DEF_STMT on edge E using the range query Q.
    1496      9562396 :       fold_range (r, def_stmt, e, &q);
    1497      9562396 :       if (idx)
    1498            0 :         tracer.trailer (idx, "recomputation", true, name, r);
    1499              :       return true;
    1500              :     }
    1501              :   return false;
    1502    202358147 : }
    1503              : 
    1504              : // Dump what is known to GORI computes to listing file F.
    1505              : 
    1506              : void
    1507            0 : gori_compute::dump (FILE *f)
    1508              : {
    1509            0 :   m_map.gori_map::dump (f);
    1510            0 : }
    1511              : 
    1512              : // ------------------------------------------------------------------------
    1513              : //  GORI iterator.  Although we have bitmap iterators, don't expose that it
    1514              : //  is currently a bitmap.  Use an export iterator to hide future changes.
    1515              : 
    1516              : // Construct a basic iterator over an export bitmap.
    1517              : 
    1518     81087811 : gori_export_iterator::gori_export_iterator (bitmap b)
    1519              : {
    1520     81087811 :   bm = b;
    1521     81087811 :   if (b)
    1522     81087811 :     bmp_iter_set_init (&bi, b, 1, &y);
    1523     81087811 : }
    1524              : 
    1525              : 
    1526              : // Move to the next export bitmap spot.
    1527              : 
    1528              : void
    1529    170536824 : gori_export_iterator::next ()
    1530              : {
    1531    170536824 :   bmp_iter_next (&bi, &y);
    1532    170536824 : }
    1533              : 
    1534              : 
    1535              : // Fetch the name of the next export in the export list.  Return NULL if
    1536              : // iteration is done.
    1537              : 
    1538              : tree
    1539    251624446 : gori_export_iterator::get_name ()
    1540              : {
    1541    251624446 :   if (!bm)
    1542              :     return NULL_TREE;
    1543              : 
    1544    251624635 :   while (bmp_iter_set (&bi, &y))
    1545              :     {
    1546    170767807 :       tree t = ssa_name (y);
    1547    170767807 :       if (t)
    1548              :         return t;
    1549          189 :       next ();
    1550              :     }
    1551              :   return NULL_TREE;
    1552              : }
    1553              : 
    1554              : // This is a helper class to set up STMT with a known LHS for further GORI
    1555              : // processing.
    1556              : 
    1557         1466 : class gori_stmt_info : public gimple_range_op_handler
    1558              : {
    1559              : public:
    1560              :   gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q);
    1561              :   value_range op1_range;
    1562              :   value_range op2_range;
    1563              :   tree ssa1;
    1564              :   tree ssa2;
    1565              : };
    1566              : 
    1567              : 
    1568              : // Uses query Q to get the known ranges on STMT with a LHS range
    1569              : // for op1_range and op2_range and set ssa1 and ssa2 if either or both of
    1570              : // those operands are SSA_NAMES.
    1571              : 
    1572         1466 : gori_stmt_info::gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q)
    1573         1466 :   : gimple_range_op_handler (stmt)
    1574              : {
    1575         1466 :   ssa1 = NULL;
    1576         1466 :   ssa2 = NULL;
    1577              :   // Don't handle switches as yet for vector processing.
    1578         1466 :   if (is_a<gswitch *> (stmt))
    1579              :     return;
    1580              : 
    1581              :   // No frther processing for VARYING or undefined.
    1582         1466 :   if (lhs.undefined_p () || lhs.varying_p ())
    1583              :     return;
    1584              : 
    1585              :   // If there is no range-op handler, we are also done.
    1586         1466 :   if (!*this)
    1587              :     return;
    1588              : 
    1589              :   // Only evaluate logical cases if both operands must be the same as the LHS.
    1590              :   // Otherwise its becomes exponential in time, as well as more complicated.
    1591         1458 :   if (is_gimple_logical_p (stmt))
    1592              :     {
    1593            0 :       gcc_checking_assert (range_compatible_p (lhs.type (), boolean_type_node));
    1594            0 :       enum tree_code code = gimple_expr_code (stmt);
    1595            0 :       if (code == TRUTH_OR_EXPR ||  code == BIT_IOR_EXPR)
    1596              :         {
    1597              :           // [0, 0] = x || y  means both x and y must be zero.
    1598            0 :           if (!lhs.singleton_p () || !lhs.zero_p ())
    1599              :             return;
    1600              :         }
    1601            0 :       else if (code == TRUTH_AND_EXPR ||  code == BIT_AND_EXPR)
    1602              :         {
    1603              :           // [1, 1] = x && y  means both x and y must be one.
    1604            0 :           if (!lhs.singleton_p () || lhs.zero_p ())
    1605              :             return;
    1606              :         }
    1607              :     }
    1608              : 
    1609         1458 :   tree op1 = operand1 ();
    1610         1458 :   tree op2 = operand2 ();
    1611         1458 :   ssa1 = gimple_range_ssa_p (op1);
    1612         1458 :   ssa2 = gimple_range_ssa_p (op2);
    1613              :   // If both operands are the same, only process one of them.
    1614         1458 :   if (ssa1 && ssa1 == ssa2)
    1615            0 :     ssa2 = NULL_TREE;
    1616              : 
    1617              :   // Extract current ranges for the operands.
    1618         1458 :   fur_stmt src (stmt, q);
    1619         1458 :   if (op1)
    1620              :     {
    1621         1458 :       op1_range.set_range_class (TREE_TYPE (op1));
    1622         1458 :       src.get_operand (op1_range, op1);
    1623              :     }
    1624              : 
    1625              :   // And satisfy the second operand for single op statements.
    1626         1458 :   if (op2)
    1627              :     {
    1628         1444 :       op2_range.set_range_class (TREE_TYPE (op2));
    1629         1444 :       src.get_operand (op2_range, op2);
    1630              :     }
    1631           14 :   else if (op1)
    1632           14 :     op2_range = op1_range;
    1633              :   return;
    1634              : }
    1635              : 
    1636              : 
    1637              : // Process STMT using LHS as the range of the LHS. Invoke GORI processing
    1638              : // to resolve ranges for all SSA_NAMES feeding STMT which may be altered
    1639              : // based on LHS.  Fill R with the results, and resolve all incoming
    1640              : // ranges using range-query Q.
    1641              : 
    1642              : static void
    1643          295 : gori_calc_operands (vrange &lhs, gimple *stmt, ssa_cache &r, range_query *q)
    1644              : {
    1645          295 :   struct gori_stmt_info si(lhs, stmt, q);
    1646          295 :   if (!si)
    1647            5 :     return;
    1648              : 
    1649          290 :   value_range tmp;
    1650              :   // Now evaluate operand ranges, and set them in the edge cache.
    1651              :   // If there was already a range, leave it and do no further evaluation.
    1652          290 :   if (si.ssa1 && !r.has_range (si.ssa1))
    1653              :     {
    1654          224 :       tmp.set_range_class (TREE_TYPE (si.ssa1));
    1655          224 :       if (si.calc_op1 (tmp, lhs, si.op2_range))
    1656          158 :         si.op1_range.intersect (tmp);
    1657          224 :       if (!si.op1_range.varying_p ())
    1658              :         {
    1659          216 :           r.set_range (si.ssa1, si.op1_range);
    1660          216 :           gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
    1661              :           // If definition is in the same basic block, evaluate it.
    1662          216 :           if (src && gimple_bb (src) == gimple_bb (stmt))
    1663          213 :             gori_calc_operands (si.op1_range, src, r, q);
    1664              :         }
    1665              :     }
    1666              : 
    1667          290 :   if (si.ssa2 && !r.has_range (si.ssa2))
    1668              :     {
    1669           71 :       tmp.set_range_class (TREE_TYPE (si.ssa2));
    1670           71 :       if (si.calc_op2 (tmp, lhs, si.op1_range))
    1671            5 :         si.op2_range.intersect (tmp);
    1672           71 :       if (!si.op2_range.varying_p ())
    1673              :         {
    1674           71 :           r.set_range (si.ssa2, si.op2_range);
    1675           71 :           gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
    1676           71 :           if (src && gimple_bb (src) == gimple_bb (stmt))
    1677           71 :             gori_calc_operands (si.op2_range, src, r, q);
    1678              :         }
    1679              :     }
    1680          585 : }
    1681              : 
    1682              : // Use ssa_cache R as a repository for all outgoing ranges on edge E that
    1683              : // can be calculated.  Use Q to establish starting edge ranges and to resolve
    1684              : // operand values.  If Q is NULL use the current range
    1685              : // query available to the system.
    1686              : 
    1687              : bool
    1688           20 : gori_on_edge (ssa_cache &r, edge e, range_query *q)
    1689              : {
    1690           20 :   if (!q)
    1691            0 :     q = get_range_query (cfun);
    1692              :   // Start with an empty vector
    1693           20 :   r.clear ();
    1694           20 :   int_range_max lhs;
    1695              :   // Determine if there is an outgoing edge.
    1696           20 :   gimple *stmt = q->gori ().edge_range_p (lhs, e);
    1697           20 :   if (!stmt)
    1698              :     return false;
    1699           11 :   gori_calc_operands (lhs, stmt, r, q);
    1700           11 :   return true;
    1701           20 : }
    1702              : 
    1703              : // Helper for GORI_NAME_ON_EDGE which uses query Q to determine if STMT
    1704              : // provides a range for NAME, and returns it in R if so. If it does not,
    1705              : // continue processing feeding statements until we run out of statements
    1706              : // or fine a range for NAME.
    1707              : 
    1708              : bool
    1709         1171 : gori_name_helper (vrange &r, tree name, vrange &lhs, gimple *stmt,
    1710              :                   range_query *q, int depth = 0)
    1711              : {
    1712         1171 :   struct gori_stmt_info si(lhs, stmt, q);
    1713         1171 :   if (!si)
    1714              :     return false;
    1715              : 
    1716         1168 :   if (si.ssa1 == name)
    1717            4 :     return si.calc_op1 (r, lhs, si.op2_range);
    1718         1164 :   if (si.ssa2 == name)
    1719            0 :     return si.calc_op2 (r, lhs, si.op1_range);
    1720              : 
    1721              :   // Limit the exponential growth via the logical depth limit.
    1722         1164 :   if (si.ssa1 && si.ssa2)
    1723          573 :     if (++depth >= param_ranger_logical_depth)
    1724              :       return false;
    1725              : 
    1726          876 :   value_range tmp;
    1727              :   // Now evaluate operand ranges, and set them in the edge cache.
    1728              :   // If there was already a range, leave it and do no further evaluation.
    1729          876 :   if (si.ssa1)
    1730              :     {
    1731          875 :       tmp.set_range_class (TREE_TYPE (si.ssa1));
    1732          875 :       if (si.calc_op1 (tmp, lhs, si.op2_range))
    1733          776 :         si.op1_range.intersect (tmp);
    1734          875 :       gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
    1735              :       // If definition is in the same basic block, evaluate it.
    1736          875 :       if (src && gimple_bb (src) == gimple_bb (stmt))
    1737          862 :         if (gori_name_helper (r, name, si.op1_range, src, q, depth))
    1738              :           return true;
    1739              :     }
    1740              : 
    1741          875 :   if (si.ssa2)
    1742              :     {
    1743          285 :       tmp.set_range_class (TREE_TYPE (si.ssa2));
    1744          285 :       if (si.calc_op2 (tmp, lhs, si.op1_range))
    1745          186 :         si.op2_range.intersect (tmp);
    1746          285 :       gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
    1747          285 :       if (src && gimple_bb (src) == gimple_bb (stmt))
    1748          285 :         if (gori_name_helper (r, name, si.op2_range, src, q, depth))
    1749              :           return true;
    1750              :     }
    1751              :   return false;
    1752          876 : }
    1753              : 
    1754              : // Check if NAME has an outgoing range on edge E.  Use query Q to evaluate
    1755              : // the operands.  Return TRUE and the range in R if there is an outgoing range.
    1756              : // This is like gori_on_edge except it only looks for the single name and
    1757              : // does not require an ssa_cache.
    1758              : 
    1759              : bool
    1760           39 : gori_name_on_edge (vrange &r, tree name, edge e, range_query *q)
    1761              : {
    1762           39 :   int_range_max lhs;
    1763           39 :   gimple *stmt = gimple_outgoing_range_stmt_p (e->src);
    1764           39 :   if (!stmt || !is_a<gcond *> (stmt))
    1765              :     return false;
    1766           24 :   gcond_edge_range (lhs, e);
    1767           24 :   return gori_name_helper (r, name, lhs, stmt, q);
    1768           39 : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.