LCOV - code coverage report
Current view: top level - gcc - loop-iv.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1229 1403 87.6 %
Date: 2020-04-04 11:58:09 Functions: 48 51 94.1 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Rtl-level induction variable analysis.
       2                 :            :    Copyright (C) 2004-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify it
       7                 :            : under the terms of the GNU General Public License as published by the
       8                 :            : Free Software Foundation; either version 3, or (at your option) any
       9                 :            : later version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT
      12                 :            : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : /* This is a simple analysis of induction variables of the loop.  The major use
      21                 :            :    is for determining the number of iterations of a loop for loop unrolling,
      22                 :            :    doloop optimization and branch prediction.  The iv information is computed
      23                 :            :    on demand.
      24                 :            : 
      25                 :            :    Induction variables are analyzed by walking the use-def chains.  When
      26                 :            :    a basic induction variable (biv) is found, it is cached in the bivs
      27                 :            :    hash table.  When register is proved to be a biv, its description
      28                 :            :    is stored to DF_REF_DATA of the def reference.
      29                 :            : 
      30                 :            :    The analysis works always with one loop -- you must call
      31                 :            :    iv_analysis_loop_init (loop) for it.  All the other functions then work with
      32                 :            :    this loop.   When you need to work with another loop, just call
      33                 :            :    iv_analysis_loop_init for it.  When you no longer need iv analysis, call
      34                 :            :    iv_analysis_done () to clean up the memory.
      35                 :            : 
      36                 :            :    The available functions are:
      37                 :            : 
      38                 :            :    iv_analyze (insn, mode, reg, iv): Stores the description of the induction
      39                 :            :      variable corresponding to the use of register REG in INSN to IV, given
      40                 :            :      that REG has mode MODE.  Returns true if REG is an induction variable
      41                 :            :      in INSN. false otherwise.  If a use of REG is not found in INSN,
      42                 :            :      the following insns are scanned (so that we may call this function
      43                 :            :      on insns returned by get_condition).
      44                 :            :    iv_analyze_result (insn, def, iv):  Stores to IV the description of the iv
      45                 :            :      corresponding to DEF, which is a register defined in INSN.
      46                 :            :    iv_analyze_expr (insn, mode, expr, iv):  Stores to IV the description of iv
      47                 :            :      corresponding to expression EXPR evaluated at INSN.  All registers used bu
      48                 :            :      EXPR must also be used in INSN.  MODE is the mode of EXPR.
      49                 :            : */
      50                 :            : 
      51                 :            : #include "config.h"
      52                 :            : #include "system.h"
      53                 :            : #include "coretypes.h"
      54                 :            : #include "backend.h"
      55                 :            : #include "rtl.h"
      56                 :            : #include "df.h"
      57                 :            : #include "memmodel.h"
      58                 :            : #include "emit-rtl.h"
      59                 :            : #include "diagnostic-core.h"
      60                 :            : #include "cfgloop.h"
      61                 :            : #include "intl.h"
      62                 :            : #include "dumpfile.h"
      63                 :            : #include "rtl-iter.h"
      64                 :            : #include "tree-ssa-loop-niter.h"
      65                 :            : #include "regs.h"
      66                 :            : #include "function-abi.h"
      67                 :            : 
      68                 :            : /* Possible return values of iv_get_reaching_def.  */
      69                 :            : 
      70                 :            : enum iv_grd_result
      71                 :            : {
      72                 :            :   /* More than one reaching def, or reaching def that does not
      73                 :            :      dominate the use.  */
      74                 :            :   GRD_INVALID,
      75                 :            : 
      76                 :            :   /* The use is trivial invariant of the loop, i.e. is not changed
      77                 :            :      inside the loop.  */
      78                 :            :   GRD_INVARIANT,
      79                 :            : 
      80                 :            :   /* The use is reached by initial value and a value from the
      81                 :            :      previous iteration.  */
      82                 :            :   GRD_MAYBE_BIV,
      83                 :            : 
      84                 :            :   /* The use has single dominating def.  */
      85                 :            :   GRD_SINGLE_DOM
      86                 :            : };
      87                 :            : 
      88                 :            : /* Information about a biv.  */
      89                 :            : 
      90                 :            : class biv_entry
      91                 :            : {
      92                 :            : public:
      93                 :            :   unsigned regno;       /* The register of the biv.  */
      94                 :            :   class rtx_iv iv;      /* Value of the biv.  */
      95                 :            : };
      96                 :            : 
      97                 :            : static bool clean_slate = true;
      98                 :            : 
      99                 :            : static unsigned int iv_ref_table_size = 0;
     100                 :            : 
     101                 :            : /* Table of rtx_ivs indexed by the df_ref uid field.  */
     102                 :            : static class rtx_iv ** iv_ref_table;
     103                 :            : 
     104                 :            : /* Induction variable stored at the reference.  */
     105                 :            : #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID (REF)]
     106                 :            : #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID (REF)] = (IV)
     107                 :            : 
     108                 :            : /* The current loop.  */
     109                 :            : 
     110                 :            : static class loop *current_loop;
     111                 :            : 
     112                 :            : /* Hashtable helper.  */
     113                 :            : 
     114                 :            : struct biv_entry_hasher : free_ptr_hash <biv_entry>
     115                 :            : {
     116                 :            :   typedef rtx_def *compare_type;
     117                 :            :   static inline hashval_t hash (const biv_entry *);
     118                 :            :   static inline bool equal (const biv_entry *, const rtx_def *);
     119                 :            : };
     120                 :            : 
     121                 :            : /* Returns hash value for biv B.  */
     122                 :            : 
     123                 :            : inline hashval_t
     124                 :       9121 : biv_entry_hasher::hash (const biv_entry *b)
     125                 :            : {
     126                 :       9121 :   return b->regno;
     127                 :            : }
     128                 :            : 
     129                 :            : /* Compares biv B and register R.  */
     130                 :            : 
     131                 :            : inline bool
     132                 :      20872 : biv_entry_hasher::equal (const biv_entry *b, const rtx_def *r)
     133                 :            : {
     134                 :      20872 :   return b->regno == REGNO (r);
     135                 :            : }
     136                 :            : 
     137                 :            : /* Bivs of the current loop.  */
     138                 :            : 
     139                 :            : static hash_table<biv_entry_hasher> *bivs;
     140                 :            : 
     141                 :            : static bool iv_analyze_op (rtx_insn *, scalar_int_mode, rtx, class rtx_iv *);
     142                 :            : 
     143                 :            : /* Return the RTX code corresponding to the IV extend code EXTEND.  */
     144                 :            : static inline enum rtx_code
     145                 :          0 : iv_extend_to_rtx_code (enum iv_extend_code extend)
     146                 :            : {
     147                 :          0 :   switch (extend)
     148                 :            :     {
     149                 :            :     case IV_SIGN_EXTEND:
     150                 :            :       return SIGN_EXTEND;
     151                 :            :     case IV_ZERO_EXTEND:
     152                 :            :       return ZERO_EXTEND;
     153                 :            :     case IV_UNKNOWN_EXTEND:
     154                 :            :       return UNKNOWN;
     155                 :            :     }
     156                 :          0 :   gcc_unreachable ();
     157                 :            : }
     158                 :            : 
     159                 :            : /* Dumps information about IV to FILE.  */
     160                 :            : 
     161                 :            : extern void dump_iv_info (FILE *, class rtx_iv *);
     162                 :            : void
     163                 :        598 : dump_iv_info (FILE *file, class rtx_iv *iv)
     164                 :            : {
     165                 :        598 :   if (!iv->base)
     166                 :            :     {
     167                 :         71 :       fprintf (file, "not simple");
     168                 :         71 :       return;
     169                 :            :     }
     170                 :            : 
     171                 :        527 :   if (iv->step == const0_rtx
     172                 :        223 :       && !iv->first_special)
     173                 :        223 :     fprintf (file, "invariant ");
     174                 :            : 
     175                 :        527 :   print_rtl (file, iv->base);
     176                 :        527 :   if (iv->step != const0_rtx)
     177                 :            :     {
     178                 :        304 :       fprintf (file, " + ");
     179                 :        304 :       print_rtl (file, iv->step);
     180                 :        304 :       fprintf (file, " * iteration");
     181                 :            :     }
     182                 :        527 :   fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
     183                 :            : 
     184                 :        527 :   if (iv->mode != iv->extend_mode)
     185                 :          0 :     fprintf (file, " %s to %s",
     186                 :          0 :              rtx_name[iv_extend_to_rtx_code (iv->extend)],
     187                 :          0 :              GET_MODE_NAME (iv->extend_mode));
     188                 :            : 
     189                 :        527 :   if (iv->mult != const1_rtx)
     190                 :            :     {
     191                 :          0 :       fprintf (file, " * ");
     192                 :          0 :       print_rtl (file, iv->mult);
     193                 :            :     }
     194                 :        527 :   if (iv->delta != const0_rtx)
     195                 :            :     {
     196                 :          0 :       fprintf (file, " + ");
     197                 :          0 :       print_rtl (file, iv->delta);
     198                 :            :     }
     199                 :        527 :   if (iv->first_special)
     200                 :          0 :     fprintf (file, " (first special)");
     201                 :            : }
     202                 :            : 
     203                 :            : static void
     204                 :     127058 : check_iv_ref_table_size (void)
     205                 :            : {
     206                 :     127058 :   if (iv_ref_table_size < DF_DEFS_TABLE_SIZE ())
     207                 :            :     {
     208                 :       8540 :       unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
     209                 :       8540 :       iv_ref_table = XRESIZEVEC (class rtx_iv *, iv_ref_table, new_size);
     210                 :       8540 :       memset (&iv_ref_table[iv_ref_table_size], 0,
     211                 :       8540 :               (new_size - iv_ref_table_size) * sizeof (class rtx_iv *));
     212                 :       8540 :       iv_ref_table_size = new_size;
     213                 :            :     }
     214                 :     127058 : }
     215                 :            : 
     216                 :            : 
     217                 :            : /* Checks whether REG is a well-behaved register.  */
     218                 :            : 
     219                 :            : static bool
     220                 :     208682 : simple_reg_p (rtx reg)
     221                 :            : {
     222                 :     208682 :   unsigned r;
     223                 :            : 
     224                 :     208682 :   if (GET_CODE (reg) == SUBREG)
     225                 :            :     {
     226                 :        230 :       if (!subreg_lowpart_p (reg))
     227                 :            :         return false;
     228                 :        230 :       reg = SUBREG_REG (reg);
     229                 :            :     }
     230                 :            : 
     231                 :     208682 :   if (!REG_P (reg))
     232                 :            :     return false;
     233                 :            : 
     234                 :     200444 :   r = REGNO (reg);
     235                 :     200444 :   if (HARD_REGISTER_NUM_P (r))
     236                 :            :     return false;
     237                 :            : 
     238                 :     197201 :   if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
     239                 :          0 :     return false;
     240                 :            : 
     241                 :            :   return true;
     242                 :            : }
     243                 :            : 
     244                 :            : /* Clears the information about ivs stored in df.  */
     245                 :            : 
     246                 :            : static void
     247                 :      31916 : clear_iv_info (void)
     248                 :            : {
     249                 :      31916 :   unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
     250                 :      31916 :   class rtx_iv *iv;
     251                 :            : 
     252                 :      31916 :   check_iv_ref_table_size ();
     253                 :    6282030 :   for (i = 0; i < n_defs; i++)
     254                 :            :     {
     255                 :    6250120 :       iv = iv_ref_table[i];
     256                 :    6250120 :       if (iv)
     257                 :            :         {
     258                 :      31586 :           free (iv);
     259                 :      31586 :           iv_ref_table[i] = NULL;
     260                 :            :         }
     261                 :            :     }
     262                 :            : 
     263                 :      31916 :   bivs->empty ();
     264                 :      31916 : }
     265                 :            : 
     266                 :            : 
     267                 :            : /* Prepare the data for an induction variable analysis of a LOOP.  */
     268                 :            : 
     269                 :            : void
     270                 :      31916 : iv_analysis_loop_init (class loop *loop)
     271                 :            : {
     272                 :      31916 :   current_loop = loop;
     273                 :            : 
     274                 :            :   /* Clear the information from the analysis of the previous loop.  */
     275                 :      31916 :   if (clean_slate)
     276                 :            :     {
     277                 :       4707 :       df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
     278                 :       4707 :       bivs = new hash_table<biv_entry_hasher> (10);
     279                 :       4707 :       clean_slate = false;
     280                 :            :     }
     281                 :            :   else
     282                 :      27209 :     clear_iv_info ();
     283                 :            : 
     284                 :            :   /* Get rid of the ud chains before processing the rescans.  Then add
     285                 :            :      the problem back.  */
     286                 :      31916 :   df_remove_problem (df_chain);
     287                 :      31916 :   df_process_deferred_rescans ();
     288                 :      31916 :   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
     289                 :      31916 :   df_chain_add_problem (DF_UD_CHAIN);
     290                 :      31916 :   df_note_add_problem ();
     291                 :      31916 :   df_analyze_loop (loop);
     292                 :      31916 :   if (dump_file)
     293                 :        187 :     df_dump_region (dump_file);
     294                 :            : 
     295                 :      31916 :   check_iv_ref_table_size ();
     296                 :      31916 : }
     297                 :            : 
     298                 :            : /* Finds the definition of REG that dominates loop latch and stores
     299                 :            :    it to DEF.  Returns false if there is not a single definition
     300                 :            :    dominating the latch.  If REG has no definition in loop, DEF
     301                 :            :    is set to NULL and true is returned.  */
     302                 :            : 
     303                 :            : static bool
     304                 :      73807 : latch_dominating_def (rtx reg, df_ref *def)
     305                 :            : {
     306                 :      73807 :   df_ref single_rd = NULL, adef;
     307                 :      73807 :   unsigned regno = REGNO (reg);
     308                 :      73807 :   class df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
     309                 :            : 
     310                 :     224268 :   for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
     311                 :            :     {
     312                 :     150507 :       if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
     313                 :     150507 :           || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)))
     314                 :      89358 :         continue;
     315                 :            : 
     316                 :            :       /* More than one reaching definition.  */
     317                 :      61149 :       if (single_rd)
     318                 :            :         return false;
     319                 :            : 
     320                 :      61147 :       if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
     321                 :            :         return false;
     322                 :            : 
     323                 :            :       single_rd = adef;
     324                 :            :     }
     325                 :            : 
     326                 :      73761 :   *def = single_rd;
     327                 :      73761 :   return true;
     328                 :            : }
     329                 :            : 
     330                 :            : /* Gets definition of REG reaching its use in INSN and stores it to DEF.  */
     331                 :            : 
     332                 :            : static enum iv_grd_result
     333                 :     100409 : iv_get_reaching_def (rtx_insn *insn, rtx reg, df_ref *def)
     334                 :            : {
     335                 :     100409 :   df_ref use, adef;
     336                 :     100409 :   basic_block def_bb, use_bb;
     337                 :     100409 :   rtx_insn *def_insn;
     338                 :     100409 :   bool dom_p;
     339                 :            : 
     340                 :     100409 :   *def = NULL;
     341                 :     100409 :   if (!simple_reg_p (reg))
     342                 :            :     return GRD_INVALID;
     343                 :      97428 :   if (GET_CODE (reg) == SUBREG)
     344                 :          0 :     reg = SUBREG_REG (reg);
     345                 :      97428 :   gcc_assert (REG_P (reg));
     346                 :            : 
     347                 :      97428 :   use = df_find_use (insn, reg);
     348                 :      97428 :   gcc_assert (use != NULL);
     349                 :            : 
     350                 :      97428 :   if (!DF_REF_CHAIN (use))
     351                 :            :     return GRD_INVARIANT;
     352                 :            : 
     353                 :            :   /* More than one reaching def.  */
     354                 :      81459 :   if (DF_REF_CHAIN (use)->next)
     355                 :            :     return GRD_INVALID;
     356                 :            : 
     357                 :      81303 :   adef = DF_REF_CHAIN (use)->ref;
     358                 :            : 
     359                 :            :   /* We do not handle setting only part of the register.  */
     360                 :      81303 :   if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
     361                 :            :     return GRD_INVALID;
     362                 :            : 
     363                 :      81303 :   def_insn = DF_REF_INSN (adef);
     364                 :      81303 :   def_bb = DF_REF_BB (adef);
     365                 :      81303 :   use_bb = BLOCK_FOR_INSN (insn);
     366                 :            : 
     367                 :      81303 :   if (use_bb == def_bb)
     368                 :      76865 :     dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
     369                 :            :   else
     370                 :       4438 :     dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
     371                 :            : 
     372                 :      81303 :   if (dom_p)
     373                 :            :     {
     374                 :      22770 :       *def = adef;
     375                 :      22770 :       return GRD_SINGLE_DOM;
     376                 :            :     }
     377                 :            : 
     378                 :            :   /* The definition does not dominate the use.  This is still OK if
     379                 :            :      this may be a use of a biv, i.e. if the def_bb dominates loop
     380                 :            :      latch.  */
     381                 :      58533 :   if (just_once_each_iteration_p (current_loop, def_bb))
     382                 :      58499 :     return GRD_MAYBE_BIV;
     383                 :            : 
     384                 :            :   return GRD_INVALID;
     385                 :            : }
     386                 :            : 
     387                 :            : /* Sets IV to invariant CST in MODE.  Always returns true (just for
     388                 :            :    consistency with other iv manipulation functions that may fail).  */
     389                 :            : 
     390                 :            : static bool
     391                 :      47275 : iv_constant (class rtx_iv *iv, scalar_int_mode mode, rtx cst)
     392                 :            : {
     393                 :      47275 :   iv->mode = mode;
     394                 :      47275 :   iv->base = cst;
     395                 :      47275 :   iv->step = const0_rtx;
     396                 :      47275 :   iv->first_special = false;
     397                 :      47275 :   iv->extend = IV_UNKNOWN_EXTEND;
     398                 :      47275 :   iv->extend_mode = iv->mode;
     399                 :      47275 :   iv->delta = const0_rtx;
     400                 :      47275 :   iv->mult = const1_rtx;
     401                 :            : 
     402                 :      47275 :   return true;
     403                 :            : }
     404                 :            : 
     405                 :            : /* Evaluates application of subreg to MODE on IV.  */
     406                 :            : 
     407                 :            : static bool
     408                 :        218 : iv_subreg (class rtx_iv *iv, scalar_int_mode mode)
     409                 :            : {
     410                 :            :   /* If iv is invariant, just calculate the new value.  */
     411                 :        218 :   if (iv->step == const0_rtx
     412                 :          9 :       && !iv->first_special)
     413                 :            :     {
     414                 :          9 :       rtx val = get_iv_value (iv, const0_rtx);
     415                 :          9 :       val = lowpart_subreg (mode, val,
     416                 :          9 :                             iv->extend == IV_UNKNOWN_EXTEND
     417                 :            :                             ? iv->mode : iv->extend_mode);
     418                 :            : 
     419                 :          9 :       iv->base = val;
     420                 :          9 :       iv->extend = IV_UNKNOWN_EXTEND;
     421                 :          9 :       iv->mode = iv->extend_mode = mode;
     422                 :          9 :       iv->delta = const0_rtx;
     423                 :          9 :       iv->mult = const1_rtx;
     424                 :          9 :       return true;
     425                 :            :     }
     426                 :            : 
     427                 :        209 :   if (iv->extend_mode == mode)
     428                 :            :     return true;
     429                 :            : 
     430                 :        627 :   if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
     431                 :            :     return false;
     432                 :            : 
     433                 :        209 :   iv->extend = IV_UNKNOWN_EXTEND;
     434                 :        209 :   iv->mode = mode;
     435                 :            : 
     436                 :        209 :   iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
     437                 :            :                                   simplify_gen_binary (MULT, iv->extend_mode,
     438                 :            :                                                        iv->base, iv->mult));
     439                 :        209 :   iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
     440                 :        209 :   iv->mult = const1_rtx;
     441                 :        209 :   iv->delta = const0_rtx;
     442                 :        209 :   iv->first_special = false;
     443                 :            : 
     444                 :        209 :   return true;
     445                 :            : }
     446                 :            : 
     447                 :            : /* Evaluates application of EXTEND to MODE on IV.  */
     448                 :            : 
     449                 :            : static bool
     450                 :          5 : iv_extend (class rtx_iv *iv, enum iv_extend_code extend, scalar_int_mode mode)
     451                 :            : {
     452                 :            :   /* If iv is invariant, just calculate the new value.  */
     453                 :          5 :   if (iv->step == const0_rtx
     454                 :          0 :       && !iv->first_special)
     455                 :            :     {
     456                 :          0 :       rtx val = get_iv_value (iv, const0_rtx);
     457                 :          0 :       if (iv->extend_mode != iv->mode
     458                 :          0 :           && iv->extend != IV_UNKNOWN_EXTEND
     459                 :          0 :           && iv->extend != extend)
     460                 :          0 :         val = lowpart_subreg (iv->mode, val, iv->extend_mode);
     461                 :          0 :       val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
     462                 :            :                                 val,
     463                 :          0 :                                 iv->extend == extend
     464                 :            :                                 ? iv->extend_mode : iv->mode);
     465                 :          0 :       iv->base = val;
     466                 :          0 :       iv->extend = IV_UNKNOWN_EXTEND;
     467                 :          0 :       iv->mode = iv->extend_mode = mode;
     468                 :          0 :       iv->delta = const0_rtx;
     469                 :          0 :       iv->mult = const1_rtx;
     470                 :          0 :       return true;
     471                 :            :     }
     472                 :            : 
     473                 :          5 :   if (mode != iv->extend_mode)
     474                 :            :     return false;
     475                 :            : 
     476                 :          2 :   if (iv->extend != IV_UNKNOWN_EXTEND
     477                 :          0 :       && iv->extend != extend)
     478                 :            :     return false;
     479                 :            : 
     480                 :          2 :   iv->extend = extend;
     481                 :            : 
     482                 :          2 :   return true;
     483                 :            : }
     484                 :            : 
     485                 :            : /* Evaluates negation of IV.  */
     486                 :            : 
     487                 :            : static bool
     488                 :          8 : iv_neg (class rtx_iv *iv)
     489                 :            : {
     490                 :          8 :   if (iv->extend == IV_UNKNOWN_EXTEND)
     491                 :            :     {
     492                 :          8 :       iv->base = simplify_gen_unary (NEG, iv->extend_mode,
     493                 :            :                                      iv->base, iv->extend_mode);
     494                 :          8 :       iv->step = simplify_gen_unary (NEG, iv->extend_mode,
     495                 :            :                                      iv->step, iv->extend_mode);
     496                 :            :     }
     497                 :            :   else
     498                 :            :     {
     499                 :          0 :       iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
     500                 :            :                                       iv->delta, iv->extend_mode);
     501                 :          0 :       iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
     502                 :            :                                      iv->mult, iv->extend_mode);
     503                 :            :     }
     504                 :            : 
     505                 :          8 :   return true;
     506                 :            : }
     507                 :            : 
     508                 :            : /* Evaluates addition or subtraction (according to OP) of IV1 to IV0.  */
     509                 :            : 
     510                 :            : static bool
     511                 :      28103 : iv_add (class rtx_iv *iv0, class rtx_iv *iv1, enum rtx_code op)
     512                 :            : {
     513                 :      28103 :   scalar_int_mode mode;
     514                 :      28103 :   rtx arg;
     515                 :            : 
     516                 :            :   /* Extend the constant to extend_mode of the other operand if necessary.  */
     517                 :      28103 :   if (iv0->extend == IV_UNKNOWN_EXTEND
     518                 :      28102 :       && iv0->mode == iv0->extend_mode
     519                 :      28073 :       && iv0->step == const0_rtx
     520                 :      28178 :       && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
     521                 :            :     {
     522                 :          4 :       iv0->extend_mode = iv1->extend_mode;
     523                 :          4 :       iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
     524                 :            :                                       iv0->base, iv0->mode);
     525                 :            :     }
     526                 :      28103 :   if (iv1->extend == IV_UNKNOWN_EXTEND
     527                 :      28103 :       && iv1->mode == iv1->extend_mode
     528                 :      28099 :       && iv1->step == const0_rtx
     529                 :     112340 :       && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
     530                 :            :     {
     531                 :         29 :       iv1->extend_mode = iv0->extend_mode;
     532                 :         29 :       iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
     533                 :            :                                       iv1->base, iv1->mode);
     534                 :            :     }
     535                 :            : 
     536                 :      28103 :   mode = iv0->extend_mode;
     537                 :      28103 :   if (mode != iv1->extend_mode)
     538                 :            :     return false;
     539                 :            : 
     540                 :      28103 :   if (iv0->extend == IV_UNKNOWN_EXTEND
     541                 :      28102 :       && iv1->extend == IV_UNKNOWN_EXTEND)
     542                 :            :     {
     543                 :      28102 :       if (iv0->mode != iv1->mode)
     544                 :            :         return false;
     545                 :            : 
     546                 :      28102 :       iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
     547                 :      28102 :       iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
     548                 :            : 
     549                 :      28102 :       return true;
     550                 :            :     }
     551                 :            : 
     552                 :            :   /* Handle addition of constant.  */
     553                 :          1 :   if (iv1->extend == IV_UNKNOWN_EXTEND
     554                 :          1 :       && iv1->mode == mode
     555                 :          2 :       && iv1->step == const0_rtx)
     556                 :            :     {
     557                 :          1 :       iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
     558                 :          1 :       return true;
     559                 :            :     }
     560                 :            : 
     561                 :          0 :   if (iv0->extend == IV_UNKNOWN_EXTEND
     562                 :          0 :       && iv0->mode == mode
     563                 :          0 :       && iv0->step == const0_rtx)
     564                 :            :     {
     565                 :          0 :       arg = iv0->base;
     566                 :          0 :       *iv0 = *iv1;
     567                 :          0 :       if (op == MINUS
     568                 :          0 :           && !iv_neg (iv0))
     569                 :            :         return false;
     570                 :            : 
     571                 :          0 :       iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
     572                 :          0 :       return true;
     573                 :            :     }
     574                 :            : 
     575                 :            :   return false;
     576                 :            : }
     577                 :            : 
     578                 :            : /* Evaluates multiplication of IV by constant CST.  */
     579                 :            : 
     580                 :            : static bool
     581                 :          2 : iv_mult (class rtx_iv *iv, rtx mby)
     582                 :            : {
     583                 :          2 :   scalar_int_mode mode = iv->extend_mode;
     584                 :            : 
     585                 :          2 :   if (GET_MODE (mby) != VOIDmode
     586                 :          2 :       && GET_MODE (mby) != mode)
     587                 :            :     return false;
     588                 :            : 
     589                 :          2 :   if (iv->extend == IV_UNKNOWN_EXTEND)
     590                 :            :     {
     591                 :          2 :       iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
     592                 :          2 :       iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
     593                 :            :     }
     594                 :            :   else
     595                 :            :     {
     596                 :          0 :       iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
     597                 :          0 :       iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
     598                 :            :     }
     599                 :            : 
     600                 :            :   return true;
     601                 :            : }
     602                 :            : 
     603                 :            : /* Evaluates shift of IV by constant CST.  */
     604                 :            : 
     605                 :            : static bool
     606                 :          3 : iv_shift (class rtx_iv *iv, rtx mby)
     607                 :            : {
     608                 :          3 :   scalar_int_mode mode = iv->extend_mode;
     609                 :            : 
     610                 :          3 :   if (GET_MODE (mby) != VOIDmode
     611                 :          3 :       && GET_MODE (mby) != mode)
     612                 :            :     return false;
     613                 :            : 
     614                 :          3 :   if (iv->extend == IV_UNKNOWN_EXTEND)
     615                 :            :     {
     616                 :          3 :       iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
     617                 :          3 :       iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
     618                 :            :     }
     619                 :            :   else
     620                 :            :     {
     621                 :          0 :       iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
     622                 :          0 :       iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
     623                 :            :     }
     624                 :            : 
     625                 :            :   return true;
     626                 :            : }
     627                 :            : 
     628                 :            : /* The recursive part of get_biv_step.  Gets the value of the single value
     629                 :            :    defined by DEF wrto initial value of REG inside loop, in shape described
     630                 :            :    at get_biv_step.  */
     631                 :            : 
     632                 :            : static bool
     633                 :      36322 : get_biv_step_1 (df_ref def, scalar_int_mode outer_mode, rtx reg,
     634                 :            :                 rtx *inner_step, scalar_int_mode *inner_mode,
     635                 :            :                 enum iv_extend_code *extend,
     636                 :            :                 rtx *outer_step)
     637                 :            : {
     638                 :      36322 :   rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
     639                 :      36322 :   rtx next, nextr;
     640                 :      36322 :   enum rtx_code code;
     641                 :      36322 :   rtx_insn *insn = DF_REF_INSN (def);
     642                 :      36322 :   df_ref next_def;
     643                 :      36322 :   enum iv_grd_result res;
     644                 :            : 
     645                 :      36322 :   set = single_set (insn);
     646                 :      36322 :   if (!set)
     647                 :            :     return false;
     648                 :            : 
     649                 :      36230 :   rhs = find_reg_equal_equiv_note (insn);
     650                 :      36230 :   if (rhs)
     651                 :         32 :     rhs = XEXP (rhs, 0);
     652                 :            :   else
     653                 :      36198 :     rhs = SET_SRC (set);
     654                 :            : 
     655                 :      36230 :   code = GET_CODE (rhs);
     656                 :      36230 :   switch (code)
     657                 :            :     {
     658                 :            :     case SUBREG:
     659                 :            :     case REG:
     660                 :            :       next = rhs;
     661                 :            :       break;
     662                 :            : 
     663                 :      33738 :     case PLUS:
     664                 :      33738 :     case MINUS:
     665                 :      33738 :       op0 = XEXP (rhs, 0);
     666                 :      33738 :       op1 = XEXP (rhs, 1);
     667                 :            : 
     668                 :      33738 :       if (code == PLUS && CONSTANT_P (op0))
     669                 :          0 :         std::swap (op0, op1);
     670                 :            : 
     671                 :      33738 :       if (!simple_reg_p (op0)
     672                 :      33738 :           || !CONSTANT_P (op1))
     673                 :            :         return false;
     674                 :            : 
     675                 :      29030 :       if (GET_MODE (rhs) != outer_mode)
     676                 :            :         {
     677                 :            :           /* ppc64 uses expressions like
     678                 :            : 
     679                 :            :              (set x:SI (plus:SI (subreg:SI y:DI) 1)).
     680                 :            : 
     681                 :            :              this is equivalent to
     682                 :            : 
     683                 :            :              (set x':DI (plus:DI y:DI 1))
     684                 :            :              (set x:SI (subreg:SI (x':DI)).  */
     685                 :          1 :           if (GET_CODE (op0) != SUBREG)
     686                 :            :             return false;
     687                 :          1 :           if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
     688                 :            :             return false;
     689                 :            :         }
     690                 :            : 
     691                 :            :       next = op0;
     692                 :            :       break;
     693                 :            : 
     694                 :         12 :     case SIGN_EXTEND:
     695                 :         12 :     case ZERO_EXTEND:
     696                 :         12 :       if (GET_MODE (rhs) != outer_mode)
     697                 :            :         return false;
     698                 :            : 
     699                 :         12 :       op0 = XEXP (rhs, 0);
     700                 :         12 :       if (!simple_reg_p (op0))
     701                 :            :         return false;
     702                 :            : 
     703                 :            :       next = op0;
     704                 :            :       break;
     705                 :            : 
     706                 :            :     default:
     707                 :            :       return false;
     708                 :            :     }
     709                 :            : 
     710                 :      30781 :   if (GET_CODE (next) == SUBREG)
     711                 :            :     {
     712                 :         14 :       if (!subreg_lowpart_p (next))
     713                 :            :         return false;
     714                 :            : 
     715                 :         14 :       nextr = SUBREG_REG (next);
     716                 :         14 :       if (GET_MODE (nextr) != outer_mode)
     717                 :            :         return false;
     718                 :            :     }
     719                 :            :   else
     720                 :            :     nextr = next;
     721                 :            : 
     722                 :      30774 :   res = iv_get_reaching_def (insn, nextr, &next_def);
     723                 :            : 
     724                 :      30774 :   if (res == GRD_INVALID || res == GRD_INVARIANT)
     725                 :            :     return false;
     726                 :            : 
     727                 :      30661 :   if (res == GRD_MAYBE_BIV)
     728                 :            :     {
     729                 :      29009 :       if (!rtx_equal_p (nextr, reg))
     730                 :            :         return false;
     731                 :            : 
     732                 :      28991 :       *inner_step = const0_rtx;
     733                 :      28991 :       *extend = IV_UNKNOWN_EXTEND;
     734                 :      28991 :       *inner_mode = outer_mode;
     735                 :      28991 :       *outer_step = const0_rtx;
     736                 :            :     }
     737                 :       1652 :   else if (!get_biv_step_1 (next_def, outer_mode, reg,
     738                 :            :                             inner_step, inner_mode, extend,
     739                 :            :                             outer_step))
     740                 :            :     return false;
     741                 :            : 
     742                 :      30054 :   if (GET_CODE (next) == SUBREG)
     743                 :            :     {
     744                 :          3 :       scalar_int_mode amode;
     745                 :          3 :       if (!is_a <scalar_int_mode> (GET_MODE (next), &amode)
     746                 :          6 :           || GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
     747                 :          0 :         return false;
     748                 :            : 
     749                 :          3 :       *inner_mode = amode;
     750                 :          3 :       *inner_step = simplify_gen_binary (PLUS, outer_mode,
     751                 :            :                                          *inner_step, *outer_step);
     752                 :          3 :       *outer_step = const0_rtx;
     753                 :          3 :       *extend = IV_UNKNOWN_EXTEND;
     754                 :            :     }
     755                 :            : 
     756                 :      30054 :   switch (code)
     757                 :            :     {
     758                 :            :     case REG:
     759                 :            :     case SUBREG:
     760                 :            :       break;
     761                 :            : 
     762                 :      28990 :     case PLUS:
     763                 :      28990 :     case MINUS:
     764                 :      28990 :       if (*inner_mode == outer_mode
     765                 :            :           /* See comment in previous switch.  */
     766                 :      28990 :           || GET_MODE (rhs) != outer_mode)
     767                 :      28989 :         *inner_step = simplify_gen_binary (code, outer_mode,
     768                 :            :                                            *inner_step, op1);
     769                 :            :       else
     770                 :          1 :         *outer_step = simplify_gen_binary (code, outer_mode,
     771                 :            :                                            *outer_step, op1);
     772                 :            :       break;
     773                 :            : 
     774                 :          3 :     case SIGN_EXTEND:
     775                 :          3 :     case ZERO_EXTEND:
     776                 :          3 :       gcc_assert (GET_MODE (op0) == *inner_mode
     777                 :            :                   && *extend == IV_UNKNOWN_EXTEND
     778                 :            :                   && *outer_step == const0_rtx);
     779                 :            : 
     780                 :          3 :       *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
     781                 :          3 :       break;
     782                 :            : 
     783                 :            :     default:
     784                 :            :       return false;
     785                 :            :     }
     786                 :            : 
     787                 :            :   return true;
     788                 :            : }
     789                 :            : 
     790                 :            : /* Gets the operation on register REG inside loop, in shape
     791                 :            : 
     792                 :            :    OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
     793                 :            : 
     794                 :            :    If the operation cannot be described in this shape, return false.
     795                 :            :    LAST_DEF is the definition of REG that dominates loop latch.  */
     796                 :            : 
     797                 :            : static bool
     798                 :      34670 : get_biv_step (df_ref last_def, scalar_int_mode outer_mode, rtx reg,
     799                 :            :               rtx *inner_step, scalar_int_mode *inner_mode,
     800                 :            :               enum iv_extend_code *extend, rtx *outer_step)
     801                 :            : {
     802                 :      34670 :   if (!get_biv_step_1 (last_def, outer_mode, reg,
     803                 :            :                        inner_step, inner_mode, extend,
     804                 :            :                        outer_step))
     805                 :            :     return false;
     806                 :            : 
     807                 :      28991 :   gcc_assert ((*inner_mode == outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
     808                 :      28991 :   gcc_assert (*inner_mode != outer_mode || *outer_step == const0_rtx);
     809                 :            : 
     810                 :            :   return true;
     811                 :            : }
     812                 :            : 
     813                 :            : /* Records information that DEF is induction variable IV.  */
     814                 :            : 
     815                 :            : static void
     816                 :      31586 : record_iv (df_ref def, class rtx_iv *iv)
     817                 :            : {
     818                 :      31586 :   class rtx_iv *recorded_iv = XNEW (class rtx_iv);
     819                 :            : 
     820                 :      31586 :   *recorded_iv = *iv;
     821                 :      31586 :   check_iv_ref_table_size ();
     822                 :      31586 :   DF_REF_IV_SET (def, recorded_iv);
     823                 :      31586 : }
     824                 :            : 
     825                 :            : /* If DEF was already analyzed for bivness, store the description of the biv to
     826                 :            :    IV and return true.  Otherwise return false.  */
     827                 :            : 
     828                 :            : static bool
     829                 :      45289 : analyzed_for_bivness_p (rtx def, class rtx_iv *iv)
     830                 :            : {
     831                 :      45289 :   class biv_entry *biv = bivs->find_with_hash (def, REGNO (def));
     832                 :            : 
     833                 :      45289 :   if (!biv)
     834                 :            :     return false;
     835                 :            : 
     836                 :      10619 :   *iv = biv->iv;
     837                 :      10619 :   return true;
     838                 :            : }
     839                 :            : 
     840                 :            : static void
     841                 :      34670 : record_biv (rtx def, class rtx_iv *iv)
     842                 :            : {
     843                 :      34670 :   class biv_entry *biv = XNEW (class biv_entry);
     844                 :      34670 :   biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def), INSERT);
     845                 :            : 
     846                 :      34670 :   biv->regno = REGNO (def);
     847                 :      34670 :   biv->iv = *iv;
     848                 :      34670 :   gcc_assert (!*slot);
     849                 :      34670 :   *slot = biv;
     850                 :      34670 : }
     851                 :            : 
     852                 :            : /* Determines whether DEF is a biv and if so, stores its description
     853                 :            :    to *IV.  OUTER_MODE is the mode of DEF.  */
     854                 :            : 
     855                 :            : static bool
     856                 :      45289 : iv_analyze_biv (scalar_int_mode outer_mode, rtx def, class rtx_iv *iv)
     857                 :            : {
     858                 :      45289 :   rtx inner_step, outer_step;
     859                 :      45289 :   scalar_int_mode inner_mode;
     860                 :      45289 :   enum iv_extend_code extend;
     861                 :      45289 :   df_ref last_def;
     862                 :            : 
     863                 :      45289 :   if (dump_file)
     864                 :            :     {
     865                 :        233 :       fprintf (dump_file, "Analyzing ");
     866                 :        233 :       print_rtl (dump_file, def);
     867                 :        233 :       fprintf (dump_file, " for bivness.\n");
     868                 :            :     }
     869                 :            : 
     870                 :      45289 :   if (!REG_P (def))
     871                 :            :     {
     872                 :          0 :       if (!CONSTANT_P (def))
     873                 :            :         return false;
     874                 :            : 
     875                 :          0 :       return iv_constant (iv, outer_mode, def);
     876                 :            :     }
     877                 :            : 
     878                 :      45289 :   if (!latch_dominating_def (def, &last_def))
     879                 :            :     {
     880                 :          0 :       if (dump_file)
     881                 :          0 :         fprintf (dump_file, "  not simple.\n");
     882                 :          0 :       return false;
     883                 :            :     }
     884                 :            : 
     885                 :      45289 :   if (!last_def)
     886                 :          0 :     return iv_constant (iv, outer_mode, def);
     887                 :            : 
     888                 :      45289 :   if (analyzed_for_bivness_p (def, iv))
     889                 :            :     {
     890                 :      10619 :       if (dump_file)
     891                 :         81 :         fprintf (dump_file, "  already analysed.\n");
     892                 :      10619 :       return iv->base != NULL_RTX;
     893                 :            :     }
     894                 :            : 
     895                 :      34670 :   if (!get_biv_step (last_def, outer_mode, def, &inner_step, &inner_mode,
     896                 :            :                      &extend, &outer_step))
     897                 :            :     {
     898                 :       5679 :       iv->base = NULL_RTX;
     899                 :       5679 :       goto end;
     900                 :            :     }
     901                 :            : 
     902                 :            :   /* Loop transforms base to es (base + inner_step) + outer_step,
     903                 :            :      where es means extend of subreg between inner_mode and outer_mode.
     904                 :            :      The corresponding induction variable is
     905                 :            : 
     906                 :            :      es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step  */
     907                 :            : 
     908                 :      28991 :   iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
     909                 :      28991 :   iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
     910                 :      28991 :   iv->mode = inner_mode;
     911                 :      28991 :   iv->extend_mode = outer_mode;
     912                 :      28991 :   iv->extend = extend;
     913                 :      28991 :   iv->mult = const1_rtx;
     914                 :      28991 :   iv->delta = outer_step;
     915                 :      28991 :   iv->first_special = inner_mode != outer_mode;
     916                 :            : 
     917                 :      34670 :  end:
     918                 :      34670 :   if (dump_file)
     919                 :            :     {
     920                 :        152 :       fprintf (dump_file, "  ");
     921                 :        152 :       dump_iv_info (dump_file, iv);
     922                 :        152 :       fprintf (dump_file, "\n");
     923                 :            :     }
     924                 :            : 
     925                 :      34670 :   record_biv (def, iv);
     926                 :      34670 :   return iv->base != NULL_RTX;
     927                 :            : }
     928                 :            : 
     929                 :            : /* Analyzes expression RHS used at INSN and stores the result to *IV.
     930                 :            :    The mode of the induction variable is MODE.  */
     931                 :            : 
     932                 :            : bool
     933                 :      88648 : iv_analyze_expr (rtx_insn *insn, scalar_int_mode mode, rtx rhs,
     934                 :            :                  class rtx_iv *iv)
     935                 :            : {
     936                 :      88648 :   rtx mby = NULL_RTX;
     937                 :      88648 :   rtx op0 = NULL_RTX, op1 = NULL_RTX;
     938                 :      88648 :   class rtx_iv iv0, iv1;
     939                 :      88648 :   enum rtx_code code = GET_CODE (rhs);
     940                 :      88648 :   scalar_int_mode omode = mode;
     941                 :            : 
     942                 :      88648 :   iv->base = NULL_RTX;
     943                 :      88648 :   iv->step = NULL_RTX;
     944                 :            : 
     945                 :      88648 :   gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
     946                 :            : 
     947                 :      88648 :   if (CONSTANT_P (rhs)
     948                 :      60570 :       || REG_P (rhs)
     949                 :      30977 :       || code == SUBREG)
     950                 :      57722 :     return iv_analyze_op (insn, mode, rhs, iv);
     951                 :            : 
     952                 :      30926 :   switch (code)
     953                 :            :     {
     954                 :            :     case REG:
     955                 :            :       op0 = rhs;
     956                 :            :       break;
     957                 :            : 
     958                 :        469 :     case SIGN_EXTEND:
     959                 :        469 :     case ZERO_EXTEND:
     960                 :        469 :     case NEG:
     961                 :        469 :       op0 = XEXP (rhs, 0);
     962                 :            :       /* We don't know how many bits there are in a sign-extended constant.  */
     963                 :        469 :       if (!is_a <scalar_int_mode> (GET_MODE (op0), &omode))
     964                 :            :         return false;
     965                 :            :       break;
     966                 :            : 
     967                 :      28457 :     case PLUS:
     968                 :      28457 :     case MINUS:
     969                 :      28457 :       op0 = XEXP (rhs, 0);
     970                 :      28457 :       op1 = XEXP (rhs, 1);
     971                 :      28457 :       break;
     972                 :            : 
     973                 :          4 :     case MULT:
     974                 :          4 :       op0 = XEXP (rhs, 0);
     975                 :          4 :       mby = XEXP (rhs, 1);
     976                 :          4 :       if (!CONSTANT_P (mby))
     977                 :          1 :         std::swap (op0, mby);
     978                 :          4 :       if (!CONSTANT_P (mby))
     979                 :            :         return false;
     980                 :            :       break;
     981                 :            : 
     982                 :         19 :     case ASHIFT:
     983                 :         19 :       op0 = XEXP (rhs, 0);
     984                 :         19 :       mby = XEXP (rhs, 1);
     985                 :         19 :       if (!CONSTANT_P (mby))
     986                 :            :         return false;
     987                 :            :       break;
     988                 :            : 
     989                 :            :     default:
     990                 :            :       return false;
     991                 :            :     }
     992                 :            : 
     993                 :      28942 :   if (op0
     994                 :      28942 :       && !iv_analyze_expr (insn, omode, op0, &iv0))
     995                 :            :     return false;
     996                 :            : 
     997                 :      28138 :   if (op1
     998                 :      28138 :       && !iv_analyze_expr (insn, omode, op1, &iv1))
     999                 :            :     return false;
    1000                 :            : 
    1001                 :      28121 :   switch (code)
    1002                 :            :     {
    1003                 :          4 :     case SIGN_EXTEND:
    1004                 :          4 :       if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode))
    1005                 :            :         return false;
    1006                 :            :       break;
    1007                 :            : 
    1008                 :          1 :     case ZERO_EXTEND:
    1009                 :          1 :       if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode))
    1010                 :            :         return false;
    1011                 :            :       break;
    1012                 :            : 
    1013                 :          8 :     case NEG:
    1014                 :          8 :       if (!iv_neg (&iv0))
    1015                 :            :         return false;
    1016                 :            :       break;
    1017                 :            : 
    1018                 :      28103 :     case PLUS:
    1019                 :      28103 :     case MINUS:
    1020                 :      28103 :       if (!iv_add (&iv0, &iv1, code))
    1021                 :            :         return false;
    1022                 :            :       break;
    1023                 :            : 
    1024                 :          2 :     case MULT:
    1025                 :          2 :       if (!iv_mult (&iv0, mby))
    1026                 :            :         return false;
    1027                 :            :       break;
    1028                 :            : 
    1029                 :          3 :     case ASHIFT:
    1030                 :          3 :       if (!iv_shift (&iv0, mby))
    1031                 :            :         return false;
    1032                 :            :       break;
    1033                 :            : 
    1034                 :            :     default:
    1035                 :            :       break;
    1036                 :            :     }
    1037                 :            : 
    1038                 :      28118 :   *iv = iv0;
    1039                 :      28118 :   return iv->base != NULL_RTX;
    1040                 :            : }
    1041                 :            : 
    1042                 :            : /* Analyzes iv DEF and stores the result to *IV.  */
    1043                 :            : 
    1044                 :            : static bool
    1045                 :      31640 : iv_analyze_def (df_ref def, class rtx_iv *iv)
    1046                 :            : {
    1047                 :      31640 :   rtx_insn *insn = DF_REF_INSN (def);
    1048                 :      31640 :   rtx reg = DF_REF_REG (def);
    1049                 :      31640 :   rtx set, rhs;
    1050                 :            : 
    1051                 :      31640 :   if (dump_file)
    1052                 :            :     {
    1053                 :        223 :       fprintf (dump_file, "Analyzing def of ");
    1054                 :        223 :       print_rtl (dump_file, reg);
    1055                 :        223 :       fprintf (dump_file, " in insn ");
    1056                 :        223 :       print_rtl_single (dump_file, insn);
    1057                 :            :     }
    1058                 :            : 
    1059                 :      31640 :   check_iv_ref_table_size ();
    1060                 :      31640 :   if (DF_REF_IV (def))
    1061                 :            :     {
    1062                 :         51 :       if (dump_file)
    1063                 :          0 :         fprintf (dump_file, "  already analysed.\n");
    1064                 :         51 :       *iv = *DF_REF_IV (def);
    1065                 :         51 :       return iv->base != NULL_RTX;
    1066                 :            :     }
    1067                 :            : 
    1068                 :      31589 :   iv->base = NULL_RTX;
    1069                 :      31589 :   iv->step = NULL_RTX;
    1070                 :            : 
    1071                 :      31589 :   scalar_int_mode mode;
    1072                 :      31589 :   if (!REG_P (reg) || !is_a <scalar_int_mode> (GET_MODE (reg), &mode))
    1073                 :            :     return false;
    1074                 :            : 
    1075                 :      31587 :   set = single_set (insn);
    1076                 :      31587 :   if (!set)
    1077                 :            :     return false;
    1078                 :            : 
    1079                 :      31586 :   if (!REG_P (SET_DEST (set)))
    1080                 :            :     return false;
    1081                 :            : 
    1082                 :      31586 :   gcc_assert (SET_DEST (set) == reg);
    1083                 :      31586 :   rhs = find_reg_equal_equiv_note (insn);
    1084                 :      31586 :   if (rhs)
    1085                 :        299 :     rhs = XEXP (rhs, 0);
    1086                 :            :   else
    1087                 :      31287 :     rhs = SET_SRC (set);
    1088                 :            : 
    1089                 :      31586 :   iv_analyze_expr (insn, mode, rhs, iv);
    1090                 :      31586 :   record_iv (def, iv);
    1091                 :            : 
    1092                 :      31586 :   if (dump_file)
    1093                 :            :     {
    1094                 :        223 :       print_rtl (dump_file, reg);
    1095                 :        223 :       fprintf (dump_file, " in insn ");
    1096                 :        223 :       print_rtl_single (dump_file, insn);
    1097                 :        223 :       fprintf (dump_file, "  is ");
    1098                 :        223 :       dump_iv_info (dump_file, iv);
    1099                 :        223 :       fprintf (dump_file, "\n");
    1100                 :            :     }
    1101                 :            : 
    1102                 :      31586 :   return iv->base != NULL_RTX;
    1103                 :            : }
    1104                 :            : 
    1105                 :            : /* Analyzes operand OP of INSN and stores the result to *IV.  MODE is the
    1106                 :            :    mode of OP.  */
    1107                 :            : 
    1108                 :            : static bool
    1109                 :     101302 : iv_analyze_op (rtx_insn *insn, scalar_int_mode mode, rtx op, class rtx_iv *iv)
    1110                 :            : {
    1111                 :     101302 :   df_ref def = NULL;
    1112                 :     101302 :   enum iv_grd_result res;
    1113                 :            : 
    1114                 :     101302 :   if (dump_file)
    1115                 :            :     {
    1116                 :        522 :       fprintf (dump_file, "Analyzing operand ");
    1117                 :        522 :       print_rtl (dump_file, op);
    1118                 :        522 :       fprintf (dump_file, " of insn ");
    1119                 :        522 :       print_rtl_single (dump_file, insn);
    1120                 :            :     }
    1121                 :            : 
    1122                 :     101302 :   if (function_invariant_p (op))
    1123                 :            :     res = GRD_INVARIANT;
    1124                 :      69910 :   else if (GET_CODE (op) == SUBREG)
    1125                 :            :     {
    1126                 :        275 :       scalar_int_mode inner_mode;
    1127                 :        275 :       if (!subreg_lowpart_p (op)
    1128                 :        549 :           || !is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (op)), &inner_mode))
    1129                 :            :         return false;
    1130                 :            : 
    1131                 :        274 :       if (!iv_analyze_op (insn, inner_mode, SUBREG_REG (op), iv))
    1132                 :            :         return false;
    1133                 :            : 
    1134                 :        218 :       return iv_subreg (iv, mode);
    1135                 :            :     }
    1136                 :            :   else
    1137                 :            :     {
    1138                 :      69635 :       res = iv_get_reaching_def (insn, op, &def);
    1139                 :      69635 :       if (res == GRD_INVALID)
    1140                 :            :         {
    1141                 :       3144 :           if (dump_file)
    1142                 :          3 :             fprintf (dump_file, "  not simple.\n");
    1143                 :       3144 :           return false;
    1144                 :            :         }
    1145                 :            :     }
    1146                 :            : 
    1147                 :      66491 :   if (res == GRD_INVARIANT)
    1148                 :            :     {
    1149                 :      47275 :       iv_constant (iv, mode, op);
    1150                 :            : 
    1151                 :      47275 :       if (dump_file)
    1152                 :            :         {
    1153                 :        223 :           fprintf (dump_file, "  ");
    1154                 :        223 :           dump_iv_info (dump_file, iv);
    1155                 :        223 :           fprintf (dump_file, "\n");
    1156                 :            :         }
    1157                 :      47275 :       return true;
    1158                 :            :     }
    1159                 :            : 
    1160                 :      50608 :   if (res == GRD_MAYBE_BIV)
    1161                 :      29490 :     return iv_analyze_biv (mode, op, iv);
    1162                 :            : 
    1163                 :      21118 :   return iv_analyze_def (def, iv);
    1164                 :            : }
    1165                 :            : 
    1166                 :            : /* Analyzes value VAL at INSN and stores the result to *IV.  MODE is the
    1167                 :            :    mode of VAL.  */
    1168                 :            : 
    1169                 :            : bool
    1170                 :      43306 : iv_analyze (rtx_insn *insn, scalar_int_mode mode, rtx val, class rtx_iv *iv)
    1171                 :            : {
    1172                 :      43306 :   rtx reg;
    1173                 :            : 
    1174                 :            :   /* We must find the insn in that val is used, so that we get to UD chains.
    1175                 :            :      Since the function is sometimes called on result of get_condition,
    1176                 :            :      this does not necessarily have to be directly INSN; scan also the
    1177                 :            :      following insns.  */
    1178                 :      43306 :   if (simple_reg_p (val))
    1179                 :            :     {
    1180                 :      37556 :       if (GET_CODE (val) == SUBREG)
    1181                 :        224 :         reg = SUBREG_REG (val);
    1182                 :            :       else
    1183                 :      37556 :         reg = val;
    1184                 :            : 
    1185                 :      37556 :       while (!df_find_use (insn, reg))
    1186                 :          0 :         insn = NEXT_INSN (insn);
    1187                 :            :     }
    1188                 :            : 
    1189                 :      43306 :   return iv_analyze_op (insn, mode, val, iv);
    1190                 :            : }
    1191                 :            : 
    1192                 :            : /* Analyzes definition of DEF in INSN and stores the result to IV.  */
    1193                 :            : 
    1194                 :            : bool
    1195                 :      10522 : iv_analyze_result (rtx_insn *insn, rtx def, class rtx_iv *iv)
    1196                 :            : {
    1197                 :      10522 :   df_ref adef;
    1198                 :            : 
    1199                 :      10522 :   adef = df_find_def (insn, def);
    1200                 :      10522 :   if (!adef)
    1201                 :            :     return false;
    1202                 :            : 
    1203                 :      10522 :   return iv_analyze_def (adef, iv);
    1204                 :            : }
    1205                 :            : 
    1206                 :            : /* Checks whether definition of register REG in INSN is a basic induction
    1207                 :            :    variable.  MODE is the mode of REG.
    1208                 :            : 
    1209                 :            :    IV analysis must have been initialized (via a call to
    1210                 :            :    iv_analysis_loop_init) for this function to produce a result.  */
    1211                 :            : 
    1212                 :            : bool
    1213                 :      31217 : biv_p (rtx_insn *insn, scalar_int_mode mode, rtx reg)
    1214                 :            : {
    1215                 :      31217 :   class rtx_iv iv;
    1216                 :      31217 :   df_ref def, last_def;
    1217                 :            : 
    1218                 :      31217 :   if (!simple_reg_p (reg))
    1219                 :            :     return false;
    1220                 :            : 
    1221                 :      28518 :   def = df_find_def (insn, reg);
    1222                 :      28518 :   gcc_assert (def != NULL);
    1223                 :      28518 :   if (!latch_dominating_def (reg, &last_def))
    1224                 :            :     return false;
    1225                 :      28472 :   if (last_def != def)
    1226                 :            :     return false;
    1227                 :            : 
    1228                 :      15799 :   if (!iv_analyze_biv (mode, reg, &iv))
    1229                 :            :     return false;
    1230                 :            : 
    1231                 :      10523 :   return iv.step != const0_rtx;
    1232                 :            : }
    1233                 :            : 
    1234                 :            : /* Calculates value of IV at ITERATION-th iteration.  */
    1235                 :            : 
    1236                 :            : rtx
    1237                 :          9 : get_iv_value (class rtx_iv *iv, rtx iteration)
    1238                 :            : {
    1239                 :          9 :   rtx val;
    1240                 :            : 
    1241                 :            :   /* We would need to generate some if_then_else patterns, and so far
    1242                 :            :      it is not needed anywhere.  */
    1243                 :          9 :   gcc_assert (!iv->first_special);
    1244                 :            : 
    1245                 :          9 :   if (iv->step != const0_rtx && iteration != const0_rtx)
    1246                 :          0 :     val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
    1247                 :            :                                simplify_gen_binary (MULT, iv->extend_mode,
    1248                 :            :                                                     iv->step, iteration));
    1249                 :            :   else
    1250                 :          9 :     val = iv->base;
    1251                 :            : 
    1252                 :          9 :   if (iv->extend_mode == iv->mode)
    1253                 :            :     return val;
    1254                 :            : 
    1255                 :          0 :   val = lowpart_subreg (iv->mode, val, iv->extend_mode);
    1256                 :            : 
    1257                 :          0 :   if (iv->extend == IV_UNKNOWN_EXTEND)
    1258                 :            :     return val;
    1259                 :            : 
    1260                 :          0 :   val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend),
    1261                 :            :                             iv->extend_mode, val, iv->mode);
    1262                 :          0 :   val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
    1263                 :            :                              simplify_gen_binary (MULT, iv->extend_mode,
    1264                 :            :                                                   iv->mult, val));
    1265                 :            : 
    1266                 :          0 :   return val;
    1267                 :            : }
    1268                 :            : 
    1269                 :            : /* Free the data for an induction variable analysis.  */
    1270                 :            : 
    1271                 :            : void
    1272                 :       7108 : iv_analysis_done (void)
    1273                 :            : {
    1274                 :       7108 :   if (!clean_slate)
    1275                 :            :     {
    1276                 :       4707 :       clear_iv_info ();
    1277                 :       4707 :       clean_slate = true;
    1278                 :       4707 :       df_finish_pass (true);
    1279                 :       4707 :       delete bivs;
    1280                 :       4707 :       bivs = NULL;
    1281                 :       4707 :       free (iv_ref_table);
    1282                 :       4707 :       iv_ref_table = NULL;
    1283                 :       4707 :       iv_ref_table_size = 0;
    1284                 :            :     }
    1285                 :       7108 : }
    1286                 :            : 
    1287                 :            : /* Computes inverse to X modulo (1 << MOD).  */
    1288                 :            : 
    1289                 :            : static uint64_t
    1290                 :      17028 : inverse (uint64_t x, int mod)
    1291                 :            : {
    1292                 :      17028 :   uint64_t mask =
    1293                 :      17028 :           ((uint64_t) 1 << (mod - 1) << 1) - 1;
    1294                 :      17028 :   uint64_t rslt = 1;
    1295                 :      17028 :   int i;
    1296                 :            : 
    1297                 :     868237 :   for (i = 0; i < mod - 1; i++)
    1298                 :            :     {
    1299                 :     851209 :       rslt = (rslt * x) & mask;
    1300                 :     851209 :       x = (x * x) & mask;
    1301                 :            :     }
    1302                 :            : 
    1303                 :      17028 :   return rslt;
    1304                 :            : }
    1305                 :            : 
    1306                 :            : /* Checks whether any register in X is in set ALT.  */
    1307                 :            : 
    1308                 :            : static bool
    1309                 :    4253250 : altered_reg_used (const_rtx x, bitmap alt)
    1310                 :            : {
    1311                 :    4253250 :   subrtx_iterator::array_type array;
    1312                 :   23726500 :   FOR_EACH_SUBRTX (iter, array, x, NONCONST)
    1313                 :            :     {
    1314                 :   19494100 :       const_rtx x = *iter;
    1315                 :   19494100 :       if (REG_P (x) && REGNO_REG_SET_P (alt, REGNO (x)))
    1316                 :      20878 :         return true;
    1317                 :            :     }
    1318                 :    4232370 :   return false;
    1319                 :            : }
    1320                 :            : 
    1321                 :            : /* Marks registers altered by EXPR in set ALT.  */
    1322                 :            : 
    1323                 :            : static void
    1324                 :    1587360 : mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
    1325                 :            : {
    1326                 :    1587360 :   if (GET_CODE (expr) == SUBREG)
    1327                 :          0 :     expr = SUBREG_REG (expr);
    1328                 :    1587360 :   if (!REG_P (expr))
    1329                 :            :     return;
    1330                 :            : 
    1331                 :    1458320 :   SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
    1332                 :            : }
    1333                 :            : 
    1334                 :            : /* Checks whether RHS is simple enough to process.  */
    1335                 :            : 
    1336                 :            : static bool
    1337                 :     990621 : simple_rhs_p (rtx rhs)
    1338                 :            : {
    1339                 :     990621 :   rtx op0, op1;
    1340                 :            : 
    1341                 :     990621 :   if (function_invariant_p (rhs)
    1342                 :     990621 :       || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
    1343                 :            :     return true;
    1344                 :            : 
    1345                 :     725653 :   switch (GET_CODE (rhs))
    1346                 :            :     {
    1347                 :     299551 :     case PLUS:
    1348                 :     299551 :     case MINUS:
    1349                 :     299551 :     case AND:
    1350                 :     299551 :       op0 = XEXP (rhs, 0);
    1351                 :     299551 :       op1 = XEXP (rhs, 1);
    1352                 :            :       /* Allow reg OP const and reg OP reg.  */
    1353                 :     293027 :       if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
    1354                 :     302298 :           && !function_invariant_p (op0))
    1355                 :            :         return false;
    1356                 :     197329 :       if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
    1357                 :     293312 :           && !function_invariant_p (op1))
    1358                 :       1484 :         return false;
    1359                 :            : 
    1360                 :            :       return true;
    1361                 :            : 
    1362                 :     161986 :     case ASHIFT:
    1363                 :     161986 :     case ASHIFTRT:
    1364                 :     161986 :     case LSHIFTRT:
    1365                 :     161986 :     case MULT:
    1366                 :     161986 :       op0 = XEXP (rhs, 0);
    1367                 :     161986 :       op1 = XEXP (rhs, 1);
    1368                 :            :       /* Allow reg OP const.  */
    1369                 :     161986 :       if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
    1370                 :            :         return false;
    1371                 :     161431 :       if (!function_invariant_p (op1))
    1372                 :      12935 :         return false;
    1373                 :            : 
    1374                 :            :       return true;
    1375                 :            : 
    1376                 :            :     default:
    1377                 :            :       return false;
    1378                 :            :     }
    1379                 :            : }
    1380                 :            : 
    1381                 :            : /* If REGNO has a single definition, return its known value, otherwise return
    1382                 :            :    null.  */
    1383                 :            : 
    1384                 :            : static rtx
    1385                 :     240669 : find_single_def_src (unsigned int regno)
    1386                 :            : {
    1387                 :     240669 :   rtx src = NULL_RTX;
    1388                 :            : 
    1389                 :            :   /* Don't look through unbounded number of single definition REG copies,
    1390                 :            :      there might be loops for sources with uninitialized variables.  */
    1391                 :     246352 :   for (int cnt = 0; cnt < 128; cnt++)
    1392                 :            :     {
    1393                 :     246344 :       df_ref adef = DF_REG_DEF_CHAIN (regno);
    1394                 :     246344 :       if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
    1395                 :     103184 :           || DF_REF_IS_ARTIFICIAL (adef))
    1396                 :            :         return NULL_RTX;
    1397                 :            : 
    1398                 :     100852 :       rtx set = single_set (DF_REF_INSN (adef));
    1399                 :     100845 :       if (set == NULL || !REG_P (SET_DEST (set))
    1400                 :     201697 :           || REGNO (SET_DEST (set)) != regno)
    1401                 :            :         return NULL_RTX;
    1402                 :            : 
    1403                 :     100845 :       rtx note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
    1404                 :     100845 :       if (note && function_invariant_p (XEXP (note, 0)))
    1405                 :            :         {
    1406                 :         40 :           src = XEXP (note, 0);
    1407                 :         40 :           break;
    1408                 :            :         }
    1409                 :     100805 :       src = SET_SRC (set);
    1410                 :            : 
    1411                 :     100805 :       if (REG_P (src))
    1412                 :            :         {
    1413                 :       5683 :           regno = REGNO (src);
    1414                 :       5683 :           continue;
    1415                 :            :         }
    1416                 :            :       break;
    1417                 :            :     }
    1418                 :      95170 :   if (!function_invariant_p (src))
    1419                 :      94024 :     return NULL_RTX;
    1420                 :            : 
    1421                 :            :   return src;
    1422                 :            : }
    1423                 :            : 
    1424                 :            : /* If any registers in *EXPR that have a single definition, try to replace
    1425                 :            :    them with the known-equivalent values.  */
    1426                 :            : 
    1427                 :            : static void
    1428                 :     133149 : replace_single_def_regs (rtx *expr)
    1429                 :            : {
    1430                 :     133149 :   subrtx_var_iterator::array_type array;
    1431                 :     134295 :  repeat:
    1432                 :     935498 :   FOR_EACH_SUBRTX_VAR (iter, array, *expr, NONCONST)
    1433                 :            :     {
    1434                 :     802349 :       rtx x = *iter;
    1435                 :     802349 :       if (REG_P (x))
    1436                 :     240669 :         if (rtx new_x = find_single_def_src (REGNO (x)))
    1437                 :            :           {
    1438                 :       1146 :             *expr = simplify_replace_rtx (*expr, x, new_x);
    1439                 :       1146 :             goto repeat;
    1440                 :            :           }
    1441                 :            :     }
    1442                 :     133149 : }
    1443                 :            : 
    1444                 :            : /* A subroutine of simplify_using_initial_values, this function examines INSN
    1445                 :            :    to see if it contains a suitable set that we can use to make a replacement.
    1446                 :            :    If it is suitable, return true and set DEST and SRC to the lhs and rhs of
    1447                 :            :    the set; return false otherwise.  */
    1448                 :            : 
    1449                 :            : static bool
    1450                 :    1506850 : suitable_set_for_replacement (rtx_insn *insn, rtx *dest, rtx *src)
    1451                 :            : {
    1452                 :    1506850 :   rtx set = single_set (insn);
    1453                 :    1506850 :   rtx lhs = NULL_RTX, rhs;
    1454                 :            : 
    1455                 :    1506850 :   if (!set)
    1456                 :            :     return false;
    1457                 :            : 
    1458                 :    1121440 :   lhs = SET_DEST (set);
    1459                 :    1121440 :   if (!REG_P (lhs))
    1460                 :            :     return false;
    1461                 :            : 
    1462                 :     990621 :   rhs = find_reg_equal_equiv_note (insn);
    1463                 :     990621 :   if (rhs)
    1464                 :      38115 :     rhs = XEXP (rhs, 0);
    1465                 :            :   else
    1466                 :     952506 :     rhs = SET_SRC (set);
    1467                 :            : 
    1468                 :     990621 :   if (!simple_rhs_p (rhs))
    1469                 :            :     return false;
    1470                 :            : 
    1471                 :     705288 :   *dest = lhs;
    1472                 :     705288 :   *src = rhs;
    1473                 :     705288 :   return true;
    1474                 :            : }
    1475                 :            : 
    1476                 :            : /* Using the data returned by suitable_set_for_replacement, replace DEST
    1477                 :            :    with SRC in *EXPR and return the new expression.  Also call
    1478                 :            :    replace_single_def_regs if the replacement changed something.  */
    1479                 :            : static void
    1480                 :     949053 : replace_in_expr (rtx *expr, rtx dest, rtx src)
    1481                 :            : {
    1482                 :     949053 :   rtx old = *expr;
    1483                 :     949053 :   *expr = simplify_replace_rtx (*expr, dest, src);
    1484                 :     949053 :   if (old == *expr)
    1485                 :            :     return;
    1486                 :      67662 :   replace_single_def_regs (expr);
    1487                 :            : }
    1488                 :            : 
    1489                 :            : /* Checks whether A implies B.  */
    1490                 :            : 
    1491                 :            : static bool
    1492                 :     176771 : implies_p (rtx a, rtx b)
    1493                 :            : {
    1494                 :     176771 :   rtx op0, op1, opb0, opb1;
    1495                 :     176771 :   machine_mode mode;
    1496                 :            : 
    1497                 :     176771 :   if (rtx_equal_p (a, b))
    1498                 :            :     return true;
    1499                 :            : 
    1500                 :     176632 :   if (GET_CODE (a) == EQ)
    1501                 :            :     {
    1502                 :      20405 :       op0 = XEXP (a, 0);
    1503                 :      20405 :       op1 = XEXP (a, 1);
    1504                 :            : 
    1505                 :      20405 :       if (REG_P (op0)
    1506                 :      16318 :           || (GET_CODE (op0) == SUBREG
    1507                 :       1148 :               && REG_P (SUBREG_REG (op0))))
    1508                 :            :         {
    1509                 :       5191 :           rtx r = simplify_replace_rtx (b, op0, op1);
    1510                 :       5191 :           if (r == const_true_rtx)
    1511                 :            :             return true;
    1512                 :            :         }
    1513                 :            : 
    1514                 :      20286 :       if (REG_P (op1)
    1515                 :      18141 :           || (GET_CODE (op1) == SUBREG
    1516                 :        156 :               && REG_P (SUBREG_REG (op1))))
    1517                 :            :         {
    1518                 :       2301 :           rtx r = simplify_replace_rtx (b, op1, op0);
    1519                 :       2301 :           if (r == const_true_rtx)
    1520                 :            :             return true;
    1521                 :            :         }
    1522                 :            :     }
    1523                 :            : 
    1524                 :     176513 :   if (b == const_true_rtx)
    1525                 :            :     return true;
    1526                 :            : 
    1527                 :     176513 :   if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
    1528                 :            :        && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
    1529                 :     175056 :       || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
    1530                 :            :           && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
    1531                 :            :     return false;
    1532                 :            : 
    1533                 :     173398 :   op0 = XEXP (a, 0);
    1534                 :     173398 :   op1 = XEXP (a, 1);
    1535                 :     173398 :   opb0 = XEXP (b, 0);
    1536                 :     173398 :   opb1 = XEXP (b, 1);
    1537                 :            : 
    1538                 :     173398 :   mode = GET_MODE (op0);
    1539                 :     173398 :   if (mode != GET_MODE (opb0))
    1540                 :            :     mode = VOIDmode;
    1541                 :     161420 :   else if (mode == VOIDmode)
    1542                 :            :     {
    1543                 :          0 :       mode = GET_MODE (op1);
    1544                 :          0 :       if (mode != GET_MODE (opb1))
    1545                 :          0 :         mode = VOIDmode;
    1546                 :            :     }
    1547                 :            : 
    1548                 :            :   /* A < B implies A + 1 <= B.  */
    1549                 :     173398 :   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
    1550                 :      72639 :       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
    1551                 :            :     {
    1552                 :            : 
    1553                 :       2511 :       if (GET_CODE (a) == GT)
    1554                 :       1544 :         std::swap (op0, op1);
    1555                 :            : 
    1556                 :       2511 :       if (GET_CODE (b) == GE)
    1557                 :        808 :         std::swap (opb0, opb1);
    1558                 :            : 
    1559                 :       2511 :       if (SCALAR_INT_MODE_P (mode)
    1560                 :       2505 :           && rtx_equal_p (op1, opb1)
    1561                 :       2958 :           && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
    1562                 :            :         return true;
    1563                 :       2511 :       return false;
    1564                 :            :     }
    1565                 :            : 
    1566                 :            :   /* A < B or A > B imply A != B.  TODO: Likewise
    1567                 :            :      A + n < B implies A != B + n if neither wraps.  */
    1568                 :     170887 :   if (GET_CODE (b) == NE
    1569                 :      23412 :       && (GET_CODE (a) == GT || GET_CODE (a) == GTU
    1570                 :      11274 :           || GET_CODE (a) == LT || GET_CODE (a) == LTU))
    1571                 :            :     {
    1572                 :      14632 :       if (rtx_equal_p (op0, opb0)
    1573                 :      14632 :           && rtx_equal_p (op1, opb1))
    1574                 :            :         return true;
    1575                 :            :     }
    1576                 :            : 
    1577                 :            :   /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1.  */
    1578                 :     167034 :   if (GET_CODE (a) == NE
    1579                 :      46389 :       && op1 == const0_rtx)
    1580                 :            :     {
    1581                 :      16704 :       if ((GET_CODE (b) == GTU
    1582                 :        469 :            && opb1 == const0_rtx)
    1583                 :      16704 :           || (GET_CODE (b) == GEU
    1584                 :         22 :               && opb1 == const1_rtx))
    1585                 :          0 :         return rtx_equal_p (op0, opb0);
    1586                 :            :     }
    1587                 :            : 
    1588                 :            :   /* A != N is equivalent to A - (N + 1) <u -1.  */
    1589                 :     167034 :   if (GET_CODE (a) == NE
    1590                 :      46389 :       && CONST_INT_P (op1)
    1591                 :      45965 :       && GET_CODE (b) == LTU
    1592                 :       3532 :       && opb1 == constm1_rtx
    1593                 :        369 :       && GET_CODE (opb0) == PLUS
    1594                 :         75 :       && CONST_INT_P (XEXP (opb0, 1))
    1595                 :            :       /* Avoid overflows.  */
    1596                 :         19 :       && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
    1597                 :            :           != ((unsigned HOST_WIDE_INT)1
    1598                 :            :               << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
    1599                 :         19 :       && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
    1600                 :         13 :     return rtx_equal_p (op0, XEXP (opb0, 0));
    1601                 :            : 
    1602                 :            :   /* Likewise, A != N implies A - N > 0.  */
    1603                 :     167021 :   if (GET_CODE (a) == NE
    1604                 :      46376 :       && CONST_INT_P (op1))
    1605                 :            :     {
    1606                 :      45952 :       if (GET_CODE (b) == GTU
    1607                 :        661 :           && GET_CODE (opb0) == PLUS
    1608                 :        191 :           && opb1 == const0_rtx
    1609                 :          0 :           && CONST_INT_P (XEXP (opb0, 1))
    1610                 :            :           /* Avoid overflows.  */
    1611                 :          0 :           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
    1612                 :            :               != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1)))
    1613                 :      45952 :           && rtx_equal_p (XEXP (opb0, 0), op0))
    1614                 :          0 :         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
    1615                 :      45952 :       if (GET_CODE (b) == GEU
    1616                 :         22 :           && GET_CODE (opb0) == PLUS
    1617                 :          1 :           && opb1 == const1_rtx
    1618                 :          0 :           && CONST_INT_P (XEXP (opb0, 1))
    1619                 :            :           /* Avoid overflows.  */
    1620                 :          0 :           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
    1621                 :            :               != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1)))
    1622                 :      45952 :           && rtx_equal_p (XEXP (opb0, 0), op0))
    1623                 :          0 :         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
    1624                 :            :     }
    1625                 :            : 
    1626                 :            :   /* A >s X, where X is positive, implies A <u Y, if Y is negative.  */
    1627                 :     167021 :   if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
    1628                 :      45865 :       && CONST_INT_P (op1)
    1629                 :      35670 :       && ((GET_CODE (a) == GT && op1 == constm1_rtx)
    1630                 :      33480 :           || INTVAL (op1) >= 0)
    1631                 :      35660 :       && GET_CODE (b) == LTU
    1632                 :        891 :       && CONST_INT_P (opb1)
    1633                 :     167912 :       && rtx_equal_p (op0, opb0))
    1634                 :         69 :     return INTVAL (opb1) < 0;
    1635                 :            : 
    1636                 :            :   return false;
    1637                 :            : }
    1638                 :            : 
    1639                 :            : /* Canonicalizes COND so that
    1640                 :            : 
    1641                 :            :    (1) Ensure that operands are ordered according to
    1642                 :            :        swap_commutative_operands_p.
    1643                 :            :    (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
    1644                 :            :        for GE, GEU, and LEU.  */
    1645                 :            : 
    1646                 :            : rtx
    1647                 :     184774 : canon_condition (rtx cond)
    1648                 :            : {
    1649                 :     184774 :   rtx op0, op1;
    1650                 :     184774 :   enum rtx_code code;
    1651                 :     184774 :   machine_mode mode;
    1652                 :            : 
    1653                 :     184774 :   code = GET_CODE (cond);
    1654                 :     184774 :   op0 = XEXP (cond, 0);
    1655                 :     184774 :   op1 = XEXP (cond, 1);
    1656                 :            : 
    1657                 :     184774 :   if (swap_commutative_operands_p (op0, op1))
    1658                 :            :     {
    1659                 :      19954 :       code = swap_condition (code);
    1660                 :      19954 :       std::swap (op0, op1);
    1661                 :            :     }
    1662                 :            : 
    1663                 :     184774 :   mode = GET_MODE (op0);
    1664                 :     184774 :   if (mode == VOIDmode)
    1665                 :          0 :     mode = GET_MODE (op1);
    1666                 :     184774 :   gcc_assert (mode != VOIDmode);
    1667                 :            : 
    1668                 :     184774 :   if (CONST_SCALAR_INT_P (op1) && GET_MODE_CLASS (mode) != MODE_CC)
    1669                 :            :     {
    1670                 :     154988 :       rtx_mode_t const_val (op1, mode);
    1671                 :            : 
    1672                 :     154988 :       switch (code)
    1673                 :            :         {
    1674                 :      15146 :         case LE:
    1675                 :      15146 :           if (wi::ne_p (const_val, wi::max_value (mode, SIGNED)))
    1676                 :            :             {
    1677                 :      15146 :               code = LT;
    1678                 :      15146 :               op1 = immed_wide_int_const (wi::add (const_val, 1),  mode);
    1679                 :            :             }
    1680                 :            :           break;
    1681                 :            : 
    1682                 :      18191 :         case GE:
    1683                 :      18191 :           if (wi::ne_p (const_val, wi::min_value (mode, SIGNED)))
    1684                 :            :             {
    1685                 :      18191 :               code = GT;
    1686                 :      18191 :               op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
    1687                 :            :             }
    1688                 :            :           break;
    1689                 :            : 
    1690                 :        496 :         case LEU:
    1691                 :        496 :           if (wi::ne_p (const_val, -1))
    1692                 :            :             {
    1693                 :        496 :               code = LTU;
    1694                 :        496 :               op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
    1695                 :            :             }
    1696                 :            :           break;
    1697                 :            : 
    1698                 :       7965 :         case GEU:
    1699                 :       7965 :           if (wi::ne_p (const_val, 0))
    1700                 :            :             {
    1701                 :       7965 :               code = GTU;
    1702                 :       7965 :               op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
    1703                 :            :             }
    1704                 :            :           break;
    1705                 :            : 
    1706                 :            :         default:
    1707                 :            :           break;
    1708                 :            :         }
    1709                 :            :     }
    1710                 :            : 
    1711                 :     184774 :   if (op0 != XEXP (cond, 0)
    1712                 :     164820 :       || op1 != XEXP (cond, 1)
    1713                 :     131867 :       || code != GET_CODE (cond)
    1714                 :     131867 :       || GET_MODE (cond) != SImode)
    1715                 :     147406 :     cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
    1716                 :            : 
    1717                 :     184774 :   return cond;
    1718                 :            : }
    1719                 :            : 
    1720                 :            : /* Reverses CONDition; returns NULL if we cannot.  */
    1721                 :            : 
    1722                 :            : static rtx
    1723                 :     167456 : reversed_condition (rtx cond)
    1724                 :            : {
    1725                 :     167456 :   enum rtx_code reversed;
    1726                 :     167456 :   reversed = reversed_comparison_code (cond, NULL);
    1727                 :     167456 :   if (reversed == UNKNOWN)
    1728                 :            :     return NULL_RTX;
    1729                 :            :   else
    1730                 :     165816 :     return gen_rtx_fmt_ee (reversed,
    1731                 :            :                            GET_MODE (cond), XEXP (cond, 0),
    1732                 :            :                            XEXP (cond, 1));
    1733                 :            : }
    1734                 :            : 
    1735                 :            : /* Tries to use the fact that COND holds to simplify EXPR.  ALTERED is the
    1736                 :            :    set of altered regs.  */
    1737                 :            : 
    1738                 :            : void
    1739                 :     110854 : simplify_using_condition (rtx cond, rtx *expr, regset altered)
    1740                 :            : {
    1741                 :     110854 :   rtx rev, reve, exp = *expr;
    1742                 :            : 
    1743                 :            :   /* If some register gets altered later, we do not really speak about its
    1744                 :            :      value at the time of comparison.  */
    1745                 :     110854 :   if (altered && altered_reg_used (cond, altered))
    1746                 :            :     return;
    1747                 :            : 
    1748                 :     110471 :   if (GET_CODE (cond) == EQ
    1749                 :      15206 :       && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
    1750                 :            :     {
    1751                 :       8728 :       *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
    1752                 :       8728 :       return;
    1753                 :            :     }
    1754                 :            : 
    1755                 :     101743 :   if (!COMPARISON_P (exp))
    1756                 :            :     return;
    1757                 :            : 
    1758                 :      46200 :   rev = reversed_condition (cond);
    1759                 :      46200 :   reve = reversed_condition (exp);
    1760                 :            : 
    1761                 :      46200 :   cond = canon_condition (cond);
    1762                 :      46200 :   exp = canon_condition (exp);
    1763                 :      46200 :   if (rev)
    1764                 :      46174 :     rev = canon_condition (rev);
    1765                 :      46200 :   if (reve)
    1766                 :      46200 :     reve = canon_condition (reve);
    1767                 :            : 
    1768                 :      46200 :   if (rtx_equal_p (exp, cond))
    1769                 :            :     {
    1770                 :        160 :       *expr = const_true_rtx;
    1771                 :        160 :       return;
    1772                 :            :     }
    1773                 :            : 
    1774                 :      46040 :   if (rev && rtx_equal_p (exp, rev))
    1775                 :            :     {
    1776                 :         29 :       *expr = const0_rtx;
    1777                 :         29 :       return;
    1778                 :            :     }
    1779                 :            : 
    1780                 :      46011 :   if (implies_p (cond, exp))
    1781                 :            :     {
    1782                 :       3934 :       *expr = const_true_rtx;
    1783                 :       3934 :       return;
    1784                 :            :     }
    1785                 :            : 
    1786                 :      42077 :   if (reve && implies_p (cond, reve))
    1787                 :            :     {
    1788                 :          1 :       *expr = const0_rtx;
    1789                 :          1 :       return;
    1790                 :            :     }
    1791                 :            : 
    1792                 :            :   /* A proof by contradiction.  If *EXPR implies (not cond), *EXPR must
    1793                 :            :      be false.  */
    1794                 :      42076 :   if (rev && implies_p (exp, rev))
    1795                 :            :     {
    1796                 :         29 :       *expr = const0_rtx;
    1797                 :         29 :       return;
    1798                 :            :     }
    1799                 :            : 
    1800                 :            :   /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true.  */
    1801                 :      42047 :   if (rev && reve && implies_p (reve, rev))
    1802                 :            :     {
    1803                 :         27 :       *expr = const_true_rtx;
    1804                 :         27 :       return;
    1805                 :            :     }
    1806                 :            : 
    1807                 :            :   /* We would like to have some other tests here.  TODO.  */
    1808                 :            : 
    1809                 :            :   return;
    1810                 :            : }
    1811                 :            : 
    1812                 :            : /* Use relationship between A and *B to eventually eliminate *B.
    1813                 :            :    OP is the operation we consider.  */
    1814                 :            : 
    1815                 :            : static void
    1816                 :       4612 : eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
    1817                 :            : {
    1818                 :       4612 :   switch (op)
    1819                 :            :     {
    1820                 :          0 :     case AND:
    1821                 :            :       /* If A implies *B, we may replace *B by true.  */
    1822                 :          0 :       if (implies_p (a, *b))
    1823                 :          0 :         *b = const_true_rtx;
    1824                 :            :       break;
    1825                 :            : 
    1826                 :       4612 :     case IOR:
    1827                 :            :       /* If *B implies A, we may replace *B by false.  */
    1828                 :       4612 :       if (implies_p (*b, a))
    1829                 :        201 :         *b = const0_rtx;
    1830                 :            :       break;
    1831                 :            : 
    1832                 :          0 :     default:
    1833                 :          0 :       gcc_unreachable ();
    1834                 :            :     }
    1835                 :       4612 : }
    1836                 :            : 
    1837                 :            : /* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
    1838                 :            :    operation we consider.  */
    1839                 :            : 
    1840                 :            : static void
    1841                 :      33997 : eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
    1842                 :            : {
    1843                 :      33997 :   rtx elt;
    1844                 :            : 
    1845                 :      36303 :   for (elt = tail; elt; elt = XEXP (elt, 1))
    1846                 :       2306 :     eliminate_implied_condition (op, *head, &XEXP (elt, 0));
    1847                 :      36303 :   for (elt = tail; elt; elt = XEXP (elt, 1))
    1848                 :       2306 :     eliminate_implied_condition (op, XEXP (elt, 0), head);
    1849                 :      33997 : }
    1850                 :            : 
    1851                 :            : /* Simplifies *EXPR using initial values at the start of the LOOP.  If *EXPR
    1852                 :            :    is a list, its elements are assumed to be combined using OP.  */
    1853                 :            : 
    1854                 :            : static void
    1855                 :     231019 : simplify_using_initial_values (class loop *loop, enum rtx_code op, rtx *expr)
    1856                 :            : {
    1857                 :     231019 :   bool expression_valid;
    1858                 :     231019 :   rtx head, tail, last_valid_expr;
    1859                 :     231019 :   rtx_expr_list *cond_list;
    1860                 :     231019 :   rtx_insn *insn;
    1861                 :     231019 :   rtx neutral, aggr;
    1862                 :     231019 :   regset altered, this_altered;
    1863                 :     231019 :   edge e;
    1864                 :            : 
    1865                 :     231019 :   if (!*expr)
    1866                 :     165532 :     return;
    1867                 :            : 
    1868                 :     120103 :   if (CONSTANT_P (*expr))
    1869                 :            :     return;
    1870                 :            : 
    1871                 :      99484 :   if (GET_CODE (*expr) == EXPR_LIST)
    1872                 :            :     {
    1873                 :      33997 :       head = XEXP (*expr, 0);
    1874                 :      33997 :       tail = XEXP (*expr, 1);
    1875                 :            : 
    1876                 :      33997 :       eliminate_implied_conditions (op, &head, tail);
    1877                 :            : 
    1878                 :      33997 :       switch (op)
    1879                 :            :         {
    1880                 :          7 :         case AND:
    1881                 :          7 :           neutral = const_true_rtx;
    1882                 :          7 :           aggr = const0_rtx;
    1883                 :          7 :           break;
    1884                 :            : 
    1885                 :      33990 :         case IOR:
    1886                 :      33990 :           neutral = const0_rtx;
    1887                 :      33990 :           aggr = const_true_rtx;
    1888                 :      33990 :           break;
    1889                 :            : 
    1890                 :          0 :         default:
    1891                 :          0 :           gcc_unreachable ();
    1892                 :            :         }
    1893                 :            : 
    1894                 :      33997 :       simplify_using_initial_values (loop, UNKNOWN, &head);
    1895                 :      33997 :       if (head == aggr)
    1896                 :            :         {
    1897                 :          0 :           XEXP (*expr, 0) = aggr;
    1898                 :          0 :           XEXP (*expr, 1) = NULL_RTX;
    1899                 :          0 :           return;
    1900                 :            :         }
    1901                 :      33997 :       else if (head == neutral)
    1902                 :            :         {
    1903                 :      13578 :           *expr = tail;
    1904                 :      13578 :           simplify_using_initial_values (loop, op, expr);
    1905                 :      13578 :           return;
    1906                 :            :         }
    1907                 :      20419 :       simplify_using_initial_values (loop, op, &tail);
    1908                 :            : 
    1909                 :      20419 :       if (tail && XEXP (tail, 0) == aggr)
    1910                 :            :         {
    1911                 :          0 :           *expr = tail;
    1912                 :          0 :           return;
    1913                 :            :         }
    1914                 :            : 
    1915                 :      20419 :       XEXP (*expr, 0) = head;
    1916                 :      20419 :       XEXP (*expr, 1) = tail;
    1917                 :      20419 :       return;
    1918                 :            :     }
    1919                 :            : 
    1920                 :      65487 :   gcc_assert (op == UNKNOWN);
    1921                 :            : 
    1922                 :      65487 :   replace_single_def_regs (expr);
    1923                 :      65487 :   if (CONSTANT_P (*expr))
    1924                 :            :     return;
    1925                 :            : 
    1926                 :      65487 :   e = loop_preheader_edge (loop);
    1927                 :      65487 :   if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1928                 :            :     return;
    1929                 :            : 
    1930                 :      65487 :   altered = ALLOC_REG_SET (&reg_obstack);
    1931                 :      65487 :   this_altered = ALLOC_REG_SET (&reg_obstack);
    1932                 :            : 
    1933                 :      65487 :   expression_valid = true;
    1934                 :      65487 :   last_valid_expr = *expr;
    1935                 :      65487 :   cond_list = NULL;
    1936                 :     165306 :   while (1)
    1937                 :            :     {
    1938                 :     165306 :       insn = BB_END (e->src);
    1939                 :     165306 :       if (any_condjump_p (insn))
    1940                 :            :         {
    1941                 :      99783 :           rtx cond = get_condition (BB_END (e->src), NULL, false, true);
    1942                 :            : 
    1943                 :      99783 :           if (cond && (e->flags & EDGE_FALLTHRU))
    1944                 :      67200 :             cond = reversed_condition (cond);
    1945                 :      99783 :           if (cond)
    1946                 :            :             {
    1947                 :      98445 :               rtx old = *expr;
    1948                 :      98445 :               simplify_using_condition (cond, expr, altered);
    1949                 :      98445 :               if (old != *expr)
    1950                 :            :                 {
    1951                 :       3572 :                   rtx note;
    1952                 :       3572 :                   if (CONSTANT_P (*expr))
    1953                 :       3565 :                     goto out;
    1954                 :          7 :                   for (note = cond_list; note; note = XEXP (note, 1))
    1955                 :            :                     {
    1956                 :          0 :                       simplify_using_condition (XEXP (note, 0), expr, altered);
    1957                 :          0 :                       if (CONSTANT_P (*expr))
    1958                 :          0 :                         goto out;
    1959                 :            :                     }
    1960                 :            :                 }
    1961                 :      94880 :               cond_list = alloc_EXPR_LIST (0, cond, cond_list);
    1962                 :            :             }
    1963                 :            :         }
    1964                 :            : 
    1965                 :    3588280 :       FOR_BB_INSNS_REVERSE (e->src, insn)
    1966                 :            :         {
    1967                 :    1730080 :           rtx src, dest;
    1968                 :    1730080 :           rtx old = *expr;
    1969                 :            : 
    1970                 :    1730080 :           if (!INSN_P (insn))
    1971                 :     223228 :             continue;
    1972                 :            : 
    1973                 :    1506850 :           CLEAR_REG_SET (this_altered);
    1974                 :    1506850 :           note_stores (insn, mark_altered, this_altered);
    1975                 :    1506850 :           if (CALL_P (insn))
    1976                 :            :             {
    1977                 :            :               /* Kill all registers that might be clobbered by the call.
    1978                 :            :                  We don't track modes of hard registers, so we need to be
    1979                 :            :                  conservative and assume that partial kills are full kills.  */
    1980                 :       7261 :               function_abi callee_abi = insn_callee_abi (insn);
    1981                 :      14522 :               IOR_REG_SET_HRS (this_altered,
    1982                 :            :                                callee_abi.full_and_partial_reg_clobbers ());
    1983                 :            :             }
    1984                 :            : 
    1985                 :    1506850 :           if (suitable_set_for_replacement (insn, &dest, &src))
    1986                 :            :             {
    1987                 :     705288 :               rtx_expr_list **pnote, **pnote_next;
    1988                 :            : 
    1989                 :     705288 :               replace_in_expr (expr, dest, src);
    1990                 :     705288 :               if (CONSTANT_P (*expr))
    1991                 :      16809 :                 goto out;
    1992                 :            : 
    1993                 :     942814 :               for (pnote = &cond_list; *pnote; pnote = pnote_next)
    1994                 :            :                 {
    1995                 :     243765 :                   rtx_expr_list *note = *pnote;
    1996                 :     243765 :                   rtx old_cond = XEXP (note, 0);
    1997                 :            : 
    1998                 :     243765 :                   pnote_next = (rtx_expr_list **)&XEXP (note, 1);
    1999                 :     243765 :                   replace_in_expr (&XEXP (note, 0), dest, src);
    2000                 :            : 
    2001                 :            :                   /* We can no longer use a condition that has been simplified
    2002                 :            :                      to a constant, and simplify_using_condition will abort if
    2003                 :            :                      we try.  */
    2004                 :     243765 :                   if (CONSTANT_P (XEXP (note, 0)))
    2005                 :            :                     {
    2006                 :          0 :                       *pnote = *pnote_next;
    2007                 :          0 :                       pnote_next = pnote;
    2008                 :          0 :                       free_EXPR_LIST_node (note);
    2009                 :            :                     }
    2010                 :            :                   /* Retry simplifications with this condition if either the
    2011                 :            :                      expression or the condition changed.  */
    2012                 :     243765 :                   else if (old_cond != XEXP (note, 0) || old != *expr)
    2013                 :      12409 :                     simplify_using_condition (XEXP (note, 0), expr, altered);
    2014                 :            :                 }
    2015                 :            :             }
    2016                 :            :           else
    2017                 :            :             {
    2018                 :     801562 :               rtx_expr_list **pnote, **pnote_next;
    2019                 :            : 
    2020                 :            :               /* If we did not use this insn to make a replacement, any overlap
    2021                 :            :                  between stores in this insn and our expression will cause the
    2022                 :            :                  expression to become invalid.  */
    2023                 :     801562 :               if (altered_reg_used (*expr, this_altered))
    2024                 :       9935 :                 goto out;
    2025                 :            : 
    2026                 :            :               /* Likewise for the conditions.  */
    2027                 :    2642420 :               for (pnote = &cond_list; *pnote; pnote = pnote_next)
    2028                 :            :                 {
    2029                 :    1850790 :                   rtx_expr_list *note = *pnote;
    2030                 :    1850790 :                   rtx old_cond = XEXP (note, 0);
    2031                 :            : 
    2032                 :    1850790 :                   pnote_next = (rtx_expr_list **)&XEXP (note, 1);
    2033                 :    1850790 :                   if (altered_reg_used (old_cond, this_altered))
    2034                 :            :                     {
    2035                 :       9397 :                       *pnote = *pnote_next;
    2036                 :       9397 :                       pnote_next = pnote;
    2037                 :       9397 :                       free_EXPR_LIST_node (note);
    2038                 :            :                     }
    2039                 :            :                 }
    2040                 :            :             }
    2041                 :            : 
    2042                 :    1490680 :           if (CONSTANT_P (*expr))
    2043                 :        635 :             goto out;
    2044                 :            : 
    2045                 :    1490040 :           IOR_REG_SET (altered, this_altered);
    2046                 :            : 
    2047                 :            :           /* If the expression now contains regs that have been altered, we
    2048                 :            :              can't return it to the caller.  However, it is still valid for
    2049                 :            :              further simplification, so keep searching to see if we can
    2050                 :            :              eventually turn it into a constant.  */
    2051                 :    1490040 :           if (altered_reg_used (*expr, altered))
    2052                 :            :             expression_valid = false;
    2053                 :    1488880 :           if (expression_valid)
    2054                 :    1488610 :             last_valid_expr = *expr;
    2055                 :            :         }
    2056                 :            : 
    2057                 :     144932 :       if (!single_pred_p (e->src)
    2058                 :     144932 :           || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    2059                 :            :         break;
    2060                 :            :       e = single_pred_edge (e->src);
    2061                 :            :     }
    2062                 :            : 
    2063                 :      65487 :  out:
    2064                 :      65487 :   free_EXPR_LIST_list (&cond_list);
    2065                 :      65487 :   if (!CONSTANT_P (*expr))
    2066                 :      55048 :     *expr = last_valid_expr;
    2067                 :      65487 :   FREE_REG_SET (altered);
    2068                 :      65487 :   FREE_REG_SET (this_altered);
    2069                 :            : }
    2070                 :            : 
    2071                 :            : /* Transforms invariant IV into MODE.  Adds assumptions based on the fact
    2072                 :            :    that IV occurs as left operands of comparison COND and its signedness
    2073                 :            :    is SIGNED_P to DESC.  */
    2074                 :            : 
    2075                 :            : static void
    2076                 :          0 : shorten_into_mode (class rtx_iv *iv, scalar_int_mode mode,
    2077                 :            :                    enum rtx_code cond, bool signed_p, class niter_desc *desc)
    2078                 :            : {
    2079                 :          0 :   rtx mmin, mmax, cond_over, cond_under;
    2080                 :            : 
    2081                 :          0 :   get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
    2082                 :          0 :   cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
    2083                 :            :                                         iv->base, mmin);
    2084                 :          0 :   cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
    2085                 :            :                                        iv->base, mmax);
    2086                 :            : 
    2087                 :          0 :   switch (cond)
    2088                 :            :     {
    2089                 :          0 :       case LE:
    2090                 :          0 :       case LT:
    2091                 :          0 :       case LEU:
    2092                 :          0 :       case LTU:
    2093                 :          0 :         if (cond_under != const0_rtx)
    2094                 :          0 :           desc->infinite =
    2095                 :          0 :                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
    2096                 :          0 :         if (cond_over != const0_rtx)
    2097                 :          0 :           desc->noloop_assumptions =
    2098                 :          0 :                   alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
    2099                 :            :         break;
    2100                 :            : 
    2101                 :          0 :       case GE:
    2102                 :          0 :       case GT:
    2103                 :          0 :       case GEU:
    2104                 :          0 :       case GTU:
    2105                 :          0 :         if (cond_over != const0_rtx)
    2106                 :          0 :           desc->infinite =
    2107                 :          0 :                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
    2108                 :          0 :         if (cond_under != const0_rtx)
    2109                 :          0 :           desc->noloop_assumptions =
    2110                 :          0 :                   alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
    2111                 :            :         break;
    2112                 :            : 
    2113                 :          0 :       case NE:
    2114                 :          0 :         if (cond_over != const0_rtx)
    2115                 :          0 :           desc->infinite =
    2116                 :          0 :                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
    2117                 :          0 :         if (cond_under != const0_rtx)
    2118                 :          0 :           desc->infinite =
    2119                 :          0 :                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
    2120                 :            :         break;
    2121                 :            : 
    2122                 :          0 :       default:
    2123                 :          0 :         gcc_unreachable ();
    2124                 :            :     }
    2125                 :            : 
    2126                 :          0 :   iv->mode = mode;
    2127                 :          0 :   iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
    2128                 :          0 : }
    2129                 :            : 
    2130                 :            : /* Transforms IV0 and IV1 compared by COND so that they are both compared as
    2131                 :            :    subregs of the same mode if possible (sometimes it is necessary to add
    2132                 :            :    some assumptions to DESC).  */
    2133                 :            : 
    2134                 :            : static bool
    2135                 :      18655 : canonicalize_iv_subregs (class rtx_iv *iv0, class rtx_iv *iv1,
    2136                 :            :                          enum rtx_code cond, class niter_desc *desc)
    2137                 :            : {
    2138                 :      18655 :   scalar_int_mode comp_mode;
    2139                 :      18655 :   bool signed_p;
    2140                 :            : 
    2141                 :            :   /* If the ivs behave specially in the first iteration, or are
    2142                 :            :      added/multiplied after extending, we ignore them.  */
    2143                 :      18655 :   if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
    2144                 :            :     return false;
    2145                 :      18655 :   if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
    2146                 :            :     return false;
    2147                 :            : 
    2148                 :            :   /* If there is some extend, it must match signedness of the comparison.  */
    2149                 :      18655 :   switch (cond)
    2150                 :            :     {
    2151                 :       3021 :       case LE:
    2152                 :       3021 :       case LT:
    2153                 :       3021 :         if (iv0->extend == IV_ZERO_EXTEND
    2154                 :       3021 :             || iv1->extend == IV_ZERO_EXTEND)
    2155                 :            :           return false;
    2156                 :            :         signed_p = true;
    2157                 :            :         break;
    2158                 :            : 
    2159                 :        351 :       case LEU:
    2160                 :        351 :       case LTU:
    2161                 :        351 :         if (iv0->extend == IV_SIGN_EXTEND
    2162                 :        351 :             || iv1->extend == IV_SIGN_EXTEND)
    2163                 :            :           return false;
    2164                 :            :         signed_p = false;
    2165                 :            :         break;
    2166                 :            : 
    2167                 :      15283 :       case NE:
    2168                 :      15283 :         if (iv0->extend != IV_UNKNOWN_EXTEND
    2169                 :          0 :             && iv1->extend != IV_UNKNOWN_EXTEND
    2170                 :          0 :             && iv0->extend != iv1->extend)
    2171                 :            :           return false;
    2172                 :            : 
    2173                 :      15283 :         signed_p = false;
    2174                 :      15283 :         if (iv0->extend != IV_UNKNOWN_EXTEND)
    2175                 :          0 :           signed_p = iv0->extend == IV_SIGN_EXTEND;
    2176                 :      15283 :         if (iv1->extend != IV_UNKNOWN_EXTEND)
    2177                 :          0 :           signed_p = iv1->extend == IV_SIGN_EXTEND;
    2178                 :            :         break;
    2179                 :            : 
    2180                 :          0 :       default:
    2181                 :          0 :         gcc_unreachable ();
    2182                 :            :     }
    2183                 :            : 
    2184                 :            :   /* Values of both variables should be computed in the same mode.  These
    2185                 :            :      might indeed be different, if we have comparison like
    2186                 :            : 
    2187                 :            :      (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
    2188                 :            : 
    2189                 :            :      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
    2190                 :            :      in different modes.  This does not seem impossible to handle, but
    2191                 :            :      it hardly ever occurs in practice.
    2192                 :            : 
    2193                 :            :      The only exception is the case when one of operands is invariant.
    2194                 :            :      For example pentium 3 generates comparisons like
    2195                 :            :      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
    2196                 :            :      definitely do not want this prevent the optimization.  */
    2197                 :      18655 :   comp_mode = iv0->extend_mode;
    2198                 :      55965 :   if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
    2199                 :         10 :     comp_mode = iv1->extend_mode;
    2200                 :            : 
    2201                 :      18655 :   if (iv0->extend_mode != comp_mode)
    2202                 :            :     {
    2203                 :         10 :       if (iv0->mode != iv0->extend_mode
    2204                 :         10 :           || iv0->step != const0_rtx)
    2205                 :            :         return false;
    2206                 :            : 
    2207                 :         12 :       iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
    2208                 :            :                                       comp_mode, iv0->base, iv0->mode);
    2209                 :         10 :       iv0->extend_mode = comp_mode;
    2210                 :            :     }
    2211                 :            : 
    2212                 :      18655 :   if (iv1->extend_mode != comp_mode)
    2213                 :            :     {
    2214                 :        195 :       if (iv1->mode != iv1->extend_mode
    2215                 :        195 :           || iv1->step != const0_rtx)
    2216                 :            :         return false;
    2217                 :            : 
    2218                 :        206 :       iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
    2219                 :            :                                       comp_mode, iv1->base, iv1->mode);
    2220                 :        194 :       iv1->extend_mode = comp_mode;
    2221                 :            :     }
    2222                 :            : 
    2223                 :            :   /* Check that both ivs belong to a range of a single mode.  If one of the
    2224                 :            :      operands is an invariant, we may need to shorten it into the common
    2225                 :            :      mode.  */
    2226                 :      18654 :   if (iv0->mode == iv0->extend_mode
    2227                 :      18450 :       && iv0->step == const0_rtx
    2228                 :      26032 :       && iv0->mode != iv1->mode)
    2229                 :          0 :     shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
    2230                 :            : 
    2231                 :      18654 :   if (iv1->mode == iv1->extend_mode
    2232                 :      18450 :       && iv1->step == const0_rtx
    2233                 :      29890 :       && iv0->mode != iv1->mode)
    2234                 :          0 :     shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
    2235                 :            : 
    2236                 :      18654 :   if (iv0->mode != iv1->mode)
    2237                 :            :     return false;
    2238                 :            : 
    2239                 :      18654 :   desc->mode = iv0->mode;
    2240                 :      18654 :   desc->signed_p = signed_p;
    2241                 :            : 
    2242                 :      18654 :   return true;
    2243                 :            : }
    2244                 :            : 
    2245                 :            : /* Tries to estimate the maximum number of iterations in LOOP, and return the
    2246                 :            :    result.  This function is called from iv_number_of_iterations with
    2247                 :            :    a number of fields in DESC already filled in.  OLD_NITER is the original
    2248                 :            :    expression for the number of iterations, before we tried to simplify it.  */
    2249                 :            : 
    2250                 :            : static uint64_t
    2251                 :      15137 : determine_max_iter (class loop *loop, class niter_desc *desc, rtx old_niter)
    2252                 :            : {
    2253                 :      15137 :   rtx niter = desc->niter_expr;
    2254                 :      15137 :   rtx mmin, mmax, cmp;
    2255                 :      15137 :   uint64_t nmax, inc;
    2256                 :      15137 :   uint64_t andmax = 0;
    2257                 :            : 
    2258                 :            :   /* We used to look for constant operand 0 of AND,
    2259                 :            :      but canonicalization should always make this impossible.  */
    2260                 :      15137 :   gcc_checking_assert (GET_CODE (niter) != AND
    2261                 :            :                        || !CONST_INT_P (XEXP (niter, 0)));
    2262                 :            : 
    2263                 :      15137 :   if (GET_CODE (niter) == AND
    2264                 :        368 :       && CONST_INT_P (XEXP (niter, 1)))
    2265                 :            :     {
    2266                 :        368 :       andmax = UINTVAL (XEXP (niter, 1));
    2267                 :        368 :       niter = XEXP (niter, 0);
    2268                 :            :     }
    2269                 :            : 
    2270                 :      15137 :   get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
    2271                 :      15137 :   nmax = UINTVAL (mmax) - UINTVAL (mmin);
    2272                 :            : 
    2273                 :      15137 :   if (GET_CODE (niter) == UDIV)
    2274                 :            :     {
    2275                 :          6 :       if (!CONST_INT_P (XEXP (niter, 1)))
    2276                 :            :         return nmax;
    2277                 :          6 :       inc = INTVAL (XEXP (niter, 1));
    2278                 :          6 :       niter = XEXP (niter, 0);
    2279                 :            :     }
    2280                 :            :   else
    2281                 :            :     inc = 1;
    2282                 :            : 
    2283                 :            :   /* We could use a binary search here, but for now improving the upper
    2284                 :            :      bound by just one eliminates one important corner case.  */
    2285                 :      27342 :   cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
    2286                 :            :                                  desc->mode, old_niter, mmax);
    2287                 :      15137 :   simplify_using_initial_values (loop, UNKNOWN, &cmp);
    2288                 :      15137 :   if (cmp == const_true_rtx)
    2289                 :            :     {
    2290                 :      10782 :       nmax--;
    2291                 :            : 
    2292                 :      10782 :       if (dump_file)
    2293                 :         14 :         fprintf (dump_file, ";; improved upper bound by one.\n");
    2294                 :            :     }
    2295                 :      15137 :   nmax /= inc;
    2296                 :      15137 :   if (andmax)
    2297                 :        368 :     nmax = MIN (nmax, andmax);
    2298                 :      15137 :   if (dump_file)
    2299                 :         17 :     fprintf (dump_file, ";; Determined upper bound %" PRId64".\n",
    2300                 :            :              nmax);
    2301                 :            :   return nmax;
    2302                 :            : }
    2303                 :            : 
    2304                 :            : /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
    2305                 :            :    the result into DESC.  Very similar to determine_number_of_iterations
    2306                 :            :    (basically its rtl version), complicated by things like subregs.  */
    2307                 :            : 
    2308                 :            : static void
    2309                 :      25163 : iv_number_of_iterations (class loop *loop, rtx_insn *insn, rtx condition,
    2310                 :            :                          class niter_desc *desc)
    2311                 :            : {
    2312                 :      25163 :   rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
    2313                 :      25163 :   class rtx_iv iv0, iv1;
    2314                 :      25163 :   rtx assumption, may_not_xform;
    2315                 :      25163 :   enum rtx_code cond;
    2316                 :      25163 :   machine_mode nonvoid_mode;
    2317                 :      25163 :   scalar_int_mode comp_mode;
    2318                 :      25163 :   rtx mmin, mmax, mode_mmin, mode_mmax;
    2319                 :      25163 :   uint64_t s, size, d, inv, max, up, down;
    2320                 :      25163 :   int64_t inc, step_val;
    2321                 :      25163 :   int was_sharp = false;
    2322                 :      25163 :   rtx old_niter;
    2323                 :      25163 :   bool step_is_pow2;
    2324                 :            : 
    2325                 :            :   /* The meaning of these assumptions is this:
    2326                 :            :      if !assumptions
    2327                 :            :        then the rest of information does not have to be valid
    2328                 :            :      if noloop_assumptions then the loop does not roll
    2329                 :            :      if infinite then this exit is never used */
    2330                 :            : 
    2331                 :      25163 :   desc->assumptions = NULL_RTX;
    2332                 :      25163 :   desc->noloop_assumptions = NULL_RTX;
    2333                 :      25163 :   desc->infinite = NULL_RTX;
    2334                 :      25163 :   desc->simple_p = true;
    2335                 :            : 
    2336                 :      25163 :   desc->const_iter = false;
    2337                 :      25163 :   desc->niter_expr = NULL_RTX;
    2338                 :            : 
    2339                 :      25163 :   cond = GET_CODE (condition);
    2340                 :      25163 :   gcc_assert (COMPARISON_P (condition));
    2341                 :            : 
    2342                 :      25163 :   nonvoid_mode = GET_MODE (XEXP (condition, 0));
    2343                 :      25163 :   if (nonvoid_mode == VOIDmode)
    2344                 :          0 :     nonvoid_mode = GET_MODE (XEXP (condition, 1));
    2345                 :            :   /* The constant comparisons should be folded.  */
    2346                 :      25163 :   gcc_assert (nonvoid_mode != VOIDmode);
    2347                 :            : 
    2348                 :            :   /* We only handle integers or pointers.  */
    2349                 :      25163 :   scalar_int_mode mode;
    2350                 :      25163 :   if (!is_a <scalar_int_mode> (nonvoid_mode, &mode))
    2351                 :        808 :     goto fail;
    2352                 :            : 
    2353                 :      24355 :   op0 = XEXP (condition, 0);
    2354                 :      24355 :   if (!iv_analyze (insn, mode, op0, &iv0))
    2355                 :       5404 :     goto fail;
    2356                 :            : 
    2357                 :      18951 :   op1 = XEXP (condition, 1);
    2358                 :      18951 :   if (!iv_analyze (insn, mode, op1, &iv1))
    2359                 :        169 :     goto fail;
    2360                 :            : 
    2361                 :      18782 :   if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
    2362                 :      37564 :       || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
    2363                 :          0 :     goto fail;
    2364                 :            : 
    2365                 :            :   /* Check condition and normalize it.  */
    2366                 :            : 
    2367                 :      18782 :   switch (cond)
    2368                 :            :     {
    2369                 :       2328 :       case GE:
    2370                 :       2328 :       case GT:
    2371                 :       2328 :       case GEU:
    2372                 :       2328 :       case GTU:
    2373                 :       2328 :         std::swap (iv0, iv1);
    2374                 :       2328 :         cond = swap_condition (cond);
    2375                 :       2328 :         break;
    2376                 :            :       case NE:
    2377                 :            :       case LE:
    2378                 :            :       case LEU:
    2379                 :            :       case LT:
    2380                 :            :       case LTU:
    2381                 :            :         break;
    2382                 :        127 :       default:
    2383                 :        127 :         goto fail;
    2384                 :            :     }
    2385                 :            : 
    2386                 :            :   /* Handle extends.  This is relatively nontrivial, so we only try in some
    2387                 :            :      easy cases, when we can canonicalize the ivs (possibly by adding some
    2388                 :            :      assumptions) to shape subreg (base + i * step).  This function also fills
    2389                 :            :      in desc->mode and desc->signed_p.  */
    2390                 :            : 
    2391                 :      18655 :   if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
    2392                 :          1 :     goto fail;
    2393                 :            : 
    2394                 :      18654 :   comp_mode = iv0.extend_mode;
    2395                 :      18654 :   mode = iv0.mode;
    2396                 :      18654 :   size = GET_MODE_PRECISION (mode);
    2397                 :      18654 :   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
    2398                 :      18654 :   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
    2399                 :      18654 :   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
    2400                 :            : 
    2401                 :      18654 :   if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
    2402                 :          0 :     goto fail;
    2403                 :            : 
    2404                 :            :   /* We can take care of the case of two induction variables chasing each other
    2405                 :            :      if the test is NE. I have never seen a loop using it, but still it is
    2406                 :            :      cool.  */
    2407                 :      18654 :   if (iv0.step != const0_rtx && iv1.step != const0_rtx)
    2408                 :            :     {
    2409                 :          0 :       if (cond != NE)
    2410                 :          0 :         goto fail;
    2411                 :            : 
    2412                 :          0 :       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
    2413                 :          0 :       iv1.step = const0_rtx;
    2414                 :            :     }
    2415                 :            : 
    2416                 :      18654 :   iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
    2417                 :      18654 :   iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
    2418                 :            : 
    2419                 :            :   /* This is either infinite loop or the one that ends immediately, depending
    2420                 :            :      on initial values.  Unswitching should remove this kind of conditions.  */
    2421                 :      18654 :   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
    2422                 :        164 :     goto fail;
    2423                 :            : 
    2424                 :      18490 :   if (cond != NE)
    2425                 :            :     {
    2426                 :       3304 :       if (iv0.step == const0_rtx)
    2427                 :         24 :         step_val = -INTVAL (iv1.step);
    2428                 :            :       else
    2429                 :       3280 :         step_val = INTVAL (iv0.step);
    2430                 :            : 
    2431                 :            :       /* Ignore loops of while (i-- < 10) type.  */
    2432                 :       3304 :       if (step_val < 0)
    2433                 :          4 :         goto fail;
    2434                 :            : 
    2435                 :       3300 :       step_is_pow2 = !(step_val & (step_val - 1));
    2436                 :            :     }
    2437                 :            :   else
    2438                 :            :     {
    2439                 :            :       /* We do not care about whether the step is power of two in this
    2440                 :            :          case.  */
    2441                 :            :       step_is_pow2 = false;
    2442                 :      18486 :       step_val = 0;
    2443                 :            :     }
    2444                 :            : 
    2445                 :            :   /* Some more condition normalization.  We must record some assumptions
    2446                 :            :      due to overflows.  */
    2447                 :      18486 :   switch (cond)
    2448                 :            :     {
    2449                 :        515 :       case LT:
    2450                 :        515 :       case LTU:
    2451                 :            :         /* We want to take care only of non-sharp relationals; this is easy,
    2452                 :            :            as in cases the overflow would make the transformation unsafe
    2453                 :            :            the loop does not roll.  Seemingly it would make more sense to want
    2454                 :            :            to take care of sharp relationals instead, as NE is more similar to
    2455                 :            :            them, but the problem is that here the transformation would be more
    2456                 :            :            difficult due to possibly infinite loops.  */
    2457                 :        515 :         if (iv0.step == const0_rtx)
    2458                 :            :           {
    2459                 :         12 :             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
    2460                 :         12 :             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
    2461                 :            :                                                   mode_mmax);
    2462                 :         12 :             if (assumption == const_true_rtx)
    2463                 :          0 :               goto zero_iter_simplify;
    2464                 :         12 :             iv0.base = simplify_gen_binary (PLUS, comp_mode,
    2465                 :            :                                             iv0.base, const1_rtx);
    2466                 :            :           }
    2467                 :            :         else
    2468                 :            :           {
    2469                 :        503 :             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
    2470                 :        503 :             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
    2471                 :            :                                                   mode_mmin);
    2472                 :        503 :             if (assumption == const_true_rtx)
    2473                 :          0 :               goto zero_iter_simplify;
    2474                 :        503 :             iv1.base = simplify_gen_binary (PLUS, comp_mode,
    2475                 :            :                                             iv1.base, constm1_rtx);
    2476                 :            :           }
    2477                 :            : 
    2478                 :        515 :         if (assumption != const0_rtx)
    2479                 :        444 :           desc->noloop_assumptions =
    2480                 :        444 :                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
    2481                 :        515 :         cond = (cond == LT) ? LE : LEU;
    2482                 :            : 
    2483                 :            :         /* It will be useful to be able to tell the difference once more in
    2484                 :            :            LE -> NE reduction.  */
    2485                 :            :         was_sharp = true;
    2486                 :            :         break;
    2487                 :      18486 :       default: ;
    2488                 :            :     }
    2489                 :            : 
    2490                 :            :   /* Take care of trivially infinite loops.  */
    2491                 :      18486 :   if (cond != NE)
    2492                 :            :     {
    2493                 :       3300 :       if (iv0.step == const0_rtx)
    2494                 :            :         {
    2495                 :         21 :           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
    2496                 :         21 :           if (rtx_equal_p (tmp, mode_mmin))
    2497                 :            :             {
    2498                 :          0 :               desc->infinite =
    2499                 :          0 :                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
    2500                 :            :               /* Fill in the remaining fields somehow.  */
    2501                 :          0 :               goto zero_iter_simplify;
    2502                 :            :             }
    2503                 :            :         }
    2504                 :            :       else
    2505                 :            :         {
    2506                 :       3279 :           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
    2507                 :       3279 :           if (rtx_equal_p (tmp, mode_mmax))
    2508                 :            :             {
    2509                 :          0 :               desc->infinite =
    2510                 :          0 :                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
    2511                 :            :               /* Fill in the remaining fields somehow.  */
    2512                 :          0 :               goto zero_iter_simplify;
    2513                 :            :             }
    2514                 :            :         }
    2515                 :            :     }
    2516                 :            : 
    2517                 :            :   /* If we can we want to take care of NE conditions instead of size
    2518                 :            :      comparisons, as they are much more friendly (most importantly
    2519                 :            :      this takes care of special handling of loops with step 1).  We can
    2520                 :            :      do it if we first check that upper bound is greater or equal to
    2521                 :            :      lower bound, their difference is constant c modulo step and that
    2522                 :            :      there is not an overflow.  */
    2523                 :      18486 :   if (cond != NE)
    2524                 :            :     {
    2525                 :       3300 :       if (iv0.step == const0_rtx)
    2526                 :         21 :         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
    2527                 :            :       else
    2528                 :            :         step = iv0.step;
    2529                 :       3300 :       step = lowpart_subreg (mode, step, comp_mode);
    2530                 :       3300 :       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
    2531                 :       3300 :       delta = lowpart_subreg (mode, delta, comp_mode);
    2532                 :       3300 :       delta = simplify_gen_binary (UMOD, mode, delta, step);
    2533                 :       3300 :       may_xform = const0_rtx;
    2534                 :       3300 :       may_not_xform = const_true_rtx;
    2535                 :            : 
    2536                 :       3300 :       if (CONST_INT_P (delta))
    2537                 :            :         {
    2538                 :       1842 :           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
    2539                 :            :             {
    2540                 :            :               /* A special case.  We have transformed condition of type
    2541                 :            :                  for (i = 0; i < 4; i += 4)
    2542                 :            :                  into
    2543                 :            :                  for (i = 0; i <= 3; i += 4)
    2544                 :            :                  obviously if the test for overflow during that transformation
    2545                 :            :                  passed, we cannot overflow here.  Most importantly any
    2546                 :            :                  loop with sharp end condition and step 1 falls into this
    2547                 :            :                  category, so handling this case specially is definitely
    2548                 :            :                  worth the troubles.  */
    2549                 :            :               may_xform = const_true_rtx;
    2550                 :            :             }
    2551                 :       1468 :           else if (iv0.step == const0_rtx)
    2552                 :            :             {
    2553                 :          5 :               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
    2554                 :          5 :               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
    2555                 :          5 :               bound = lowpart_subreg (mode, bound, comp_mode);
    2556                 :          5 :               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
    2557                 :          5 :               may_xform = simplify_gen_relational (cond, SImode, mode,
    2558                 :            :                                                    bound, tmp);
    2559                 :          5 :               may_not_xform = simplify_gen_relational (reverse_condition (cond),
    2560                 :            :                                                        SImode, mode,
    2561                 :            :                                                        bound, tmp);
    2562                 :            :             }
    2563                 :            :           else
    2564                 :            :             {
    2565                 :       1463 :               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
    2566                 :       1463 :               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
    2567                 :       1463 :               bound = lowpart_subreg (mode, bound, comp_mode);
    2568                 :       1463 :               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
    2569                 :       1463 :               may_xform = simplify_gen_relational (cond, SImode, mode,
    2570                 :            :                                                    tmp, bound);
    2571                 :       1463 :               may_not_xform = simplify_gen_relational (reverse_condition (cond),
    2572                 :            :                                                        SImode, mode,
    2573                 :            :                                                        tmp, bound);
    2574                 :            :             }
    2575                 :            :         }
    2576                 :            : 
    2577                 :       3300 :       if (may_xform != const0_rtx)
    2578                 :            :         {
    2579                 :            :           /* We perform the transformation always provided that it is not
    2580                 :            :              completely senseless.  This is OK, as we would need this assumption
    2581                 :            :              to determine the number of iterations anyway.  */
    2582                 :       1842 :           if (may_xform != const_true_rtx)
    2583                 :            :             {
    2584                 :            :               /* If the step is a power of two and the final value we have
    2585                 :            :                  computed overflows, the cycle is infinite.  Otherwise it
    2586                 :            :                  is nontrivial to compute the number of iterations.  */
    2587                 :       1457 :               if (step_is_pow2)
    2588                 :       1457 :                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
    2589                 :            :                                                   desc->infinite);
    2590                 :            :               else
    2591                 :          0 :                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
    2592                 :            :                                                      desc->assumptions);
    2593                 :            :             }
    2594                 :            : 
    2595                 :            :           /* We are going to lose some information about upper bound on
    2596                 :            :              number of iterations in this step, so record the information
    2597                 :            :              here.  */
    2598                 :       1842 :           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
    2599                 :       1842 :           if (CONST_INT_P (iv1.base))
    2600                 :         49 :             up = INTVAL (iv1.base);
    2601                 :            :           else
    2602                 :       1793 :             up = INTVAL (mode_mmax) - inc;
    2603                 :       1842 :           down = INTVAL (CONST_INT_P (iv0.base)
    2604                 :            :                          ? iv0.base
    2605                 :            :                          : mode_mmin);
    2606                 :       1842 :           max = (up - down) / inc + 1;
    2607                 :       1842 :           if (!desc->infinite
    2608                 :        385 :               && !desc->assumptions)
    2609                 :        770 :             record_niter_bound (loop, max, false, true);
    2610                 :            : 
    2611                 :       1842 :           if (iv0.step == const0_rtx)
    2612                 :            :             {
    2613                 :         15 :               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
    2614                 :         15 :               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
    2615                 :            :             }
    2616                 :            :           else
    2617                 :            :             {
    2618                 :       1827 :               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
    2619                 :       1827 :               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
    2620                 :            :             }
    2621                 :            : 
    2622                 :       1842 :           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
    2623                 :       1842 :           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
    2624                 :       1842 :           assumption = simplify_gen_relational (reverse_condition (cond),
    2625                 :            :                                                 SImode, mode, tmp0, tmp1);
    2626                 :       1842 :           if (assumption == const_true_rtx)
    2627                 :          0 :             goto zero_iter_simplify;
    2628                 :       1842 :           else if (assumption != const0_rtx)
    2629                 :       1842 :             desc->noloop_assumptions =
    2630                 :       1842 :                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
    2631                 :            :           cond = NE;
    2632                 :            :         }
    2633                 :            :     }
    2634                 :            : 
    2635                 :            :   /* Count the number of iterations.  */
    2636                 :      16644 :   if (cond == NE)
    2637                 :            :     {
    2638                 :            :       /* Everything we do here is just arithmetics modulo size of mode.  This
    2639                 :            :          makes us able to do more involved computations of number of iterations
    2640                 :            :          than in other cases.  First transform the condition into shape
    2641                 :            :          s * i <> c, with s positive.  */
    2642                 :      17028 :       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
    2643                 :      17028 :       iv0.base = const0_rtx;
    2644                 :      17028 :       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
    2645                 :      17028 :       iv1.step = const0_rtx;
    2646                 :      17028 :       if (INTVAL (iv0.step) < 0)
    2647                 :            :         {
    2648                 :       7943 :           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, comp_mode);
    2649                 :       7943 :           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, comp_mode);
    2650                 :            :         }
    2651                 :      17028 :       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
    2652                 :            : 
    2653                 :            :       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
    2654                 :            :          is infinite.  Otherwise, the number of iterations is
    2655                 :            :          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
    2656                 :      17028 :       s = INTVAL (iv0.step); d = 1;
    2657                 :      42239 :       while (s % 2 != 1)
    2658                 :            :         {
    2659                 :      25211 :           s /= 2;
    2660                 :      25211 :           d *= 2;
    2661                 :      25211 :           size--;
    2662                 :            :         }
    2663                 :      17028 :       bound = GEN_INT (((uint64_t) 1 << (size - 1 ) << 1) - 1);
    2664                 :            : 
    2665                 :      17028 :       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
    2666                 :      17028 :       tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
    2667                 :      17028 :       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
    2668                 :      17028 :       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
    2669                 :            : 
    2670                 :      17028 :       tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode));
    2671                 :      17028 :       inv = inverse (s, size);
    2672                 :      17028 :       tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
    2673                 :      17028 :       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
    2674                 :            :     }
    2675                 :            :   else
    2676                 :            :     {
    2677                 :       1458 :       if (iv1.step == const0_rtx)
    2678                 :            :         /* Condition in shape a + s * i <= b
    2679                 :            :            We must know that b + s does not overflow and a <= b + s and then we
    2680                 :            :            can compute number of iterations as (b + s - a) / s.  (It might
    2681                 :            :            seem that we in fact could be more clever about testing the b + s
    2682                 :            :            overflow condition using some information about b - a mod s,
    2683                 :            :            but it was already taken into account during LE -> NE transform).  */
    2684                 :            :         {
    2685                 :       1452 :           step = iv0.step;
    2686                 :       1452 :           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
    2687                 :       1452 :           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
    2688                 :            : 
    2689                 :       1452 :           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
    2690                 :            :                                        lowpart_subreg (mode, step,
    2691                 :            :                                                        comp_mode));
    2692                 :       1452 :           if (step_is_pow2)
    2693                 :            :             {
    2694                 :       1449 :               rtx t0, t1;
    2695                 :            : 
    2696                 :            :               /* If s is power of 2, we know that the loop is infinite if
    2697                 :            :                  a % s <= b % s and b + s overflows.  */
    2698                 :       1449 :               assumption = simplify_gen_relational (reverse_condition (cond),
    2699                 :            :                                                     SImode, mode,
    2700                 :            :                                                     tmp1, bound);
    2701                 :            : 
    2702                 :       1449 :               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
    2703                 :       1449 :               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
    2704                 :       1449 :               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
    2705                 :       1449 :               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
    2706                 :       1449 :               desc->infinite =
    2707                 :       1449 :                       alloc_EXPR_LIST (0, assumption, desc->infinite);
    2708                 :            :             }
    2709                 :            :           else
    2710                 :            :             {
    2711                 :          3 :               assumption = simplify_gen_relational (cond, SImode, mode,
    2712                 :            :                                                     tmp1, bound);
    2713                 :          3 :               desc->assumptions =
    2714                 :          3 :                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
    2715                 :            :             }
    2716                 :            : 
    2717                 :       1452 :           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
    2718                 :       1452 :           tmp = lowpart_subreg (mode, tmp, comp_mode);
    2719                 :       1452 :           assumption = simplify_gen_relational (reverse_condition (cond),
    2720                 :            :                                                 SImode, mode, tmp0, tmp);
    2721                 :            : 
    2722                 :       1452 :           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
    2723                 :       1452 :           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
    2724                 :            :         }
    2725                 :            :       else
    2726                 :            :         {
    2727                 :            :           /* Condition in shape a <= b - s * i
    2728                 :            :              We must know that a - s does not overflow and a - s <= b and then
    2729                 :            :              we can again compute number of iterations as (b - (a - s)) / s.  */
    2730                 :          6 :           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
    2731                 :          6 :           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
    2732                 :          6 :           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
    2733                 :            : 
    2734                 :          6 :           bound = simplify_gen_binary (PLUS, mode, mode_mmin,
    2735                 :            :                                        lowpart_subreg (mode, step, comp_mode));
    2736                 :          6 :           if (step_is_pow2)
    2737                 :            :             {
    2738                 :          3 :               rtx t0, t1;
    2739                 :            : 
    2740                 :            :               /* If s is power of 2, we know that the loop is infinite if
    2741                 :            :                  a % s <= b % s and a - s overflows.  */
    2742                 :          3 :               assumption = simplify_gen_relational (reverse_condition (cond),
    2743                 :            :                                                     SImode, mode,
    2744                 :            :                                                     bound, tmp0);
    2745                 :            : 
    2746                 :          3 :               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
    2747                 :          3 :               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
    2748                 :          3 :               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
    2749                 :          3 :               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
    2750                 :          3 :               desc->infinite =
    2751                 :          3 :                       alloc_EXPR_LIST (0, assumption, desc->infinite);
    2752                 :            :             }
    2753                 :            :           else
    2754                 :            :             {
    2755                 :          3 :               assumption = simplify_gen_relational (cond, SImode, mode,
    2756                 :            :                                                     bound, tmp0);
    2757                 :          3 :               desc->assumptions =
    2758                 :          3 :                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
    2759                 :            :             }
    2760                 :            : 
    2761                 :          6 :           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
    2762                 :          6 :           tmp = lowpart_subreg (mode, tmp, comp_mode);
    2763                 :          6 :           assumption = simplify_gen_relational (reverse_condition (cond),
    2764                 :            :                                                 SImode, mode,
    2765                 :            :                                                 tmp, tmp1);
    2766                 :          6 :           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
    2767                 :          6 :           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
    2768                 :            :         }
    2769                 :       1458 :       if (assumption == const_true_rtx)
    2770                 :          0 :         goto zero_iter_simplify;
    2771                 :       1458 :       else if (assumption != const0_rtx)
    2772                 :       1458 :         desc->noloop_assumptions =
    2773                 :       1458 :                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
    2774                 :       1458 :       delta = simplify_gen_binary (UDIV, mode, delta, step);
    2775                 :       1458 :       desc->niter_expr = delta;
    2776                 :            :     }
    2777                 :            : 
    2778                 :      18486 :   old_niter = desc->niter_expr;
    2779                 :            : 
    2780                 :      18486 :   simplify_using_initial_values (loop, AND, &desc->assumptions);
    2781                 :      18486 :   if (desc->assumptions
    2782                 :          1 :       && XEXP (desc->assumptions, 0) == const0_rtx)
    2783                 :          0 :     goto fail;
    2784                 :      18486 :   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
    2785                 :      18486 :   simplify_using_initial_values (loop, IOR, &desc->infinite);
    2786                 :      18486 :   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
    2787                 :            : 
    2788                 :            :   /* Rerun the simplification.  Consider code (created by copying loop headers)
    2789                 :            : 
    2790                 :            :      i = 0;
    2791                 :            : 
    2792                 :            :      if (0 < n)
    2793                 :            :        {
    2794                 :            :          do
    2795                 :            :            {
    2796                 :            :              i++;
    2797                 :            :            } while (i < n);
    2798                 :            :        }
    2799                 :            : 
    2800                 :            :     The first pass determines that i = 0, the second pass uses it to eliminate
    2801                 :            :     noloop assumption.  */
    2802                 :            : 
    2803                 :      18486 :   simplify_using_initial_values (loop, AND, &desc->assumptions);
    2804                 :      18486 :   if (desc->assumptions
    2805                 :          1 :       && XEXP (desc->assumptions, 0) == const0_rtx)
    2806                 :          0 :     goto fail;
    2807                 :      18486 :   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
    2808                 :      18486 :   simplify_using_initial_values (loop, IOR, &desc->infinite);
    2809                 :      18486 :   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
    2810                 :            : 
    2811                 :      18486 :   if (desc->noloop_assumptions
    2812                 :       3221 :       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
    2813                 :          0 :     goto zero_iter;
    2814                 :            : 
    2815                 :      18486 :   if (CONST_INT_P (desc->niter_expr))
    2816                 :            :     {
    2817                 :       3349 :       uint64_t val = INTVAL (desc->niter_expr);
    2818                 :            : 
    2819                 :       3349 :       desc->const_iter = true;
    2820                 :       3349 :       desc->niter = val & GET_MODE_MASK (desc->mode);
    2821                 :       3349 :       if (!desc->infinite
    2822                 :       3348 :           && !desc->assumptions)
    2823                 :       6696 :         record_niter_bound (loop, desc->niter, false, true);
    2824                 :            :     }
    2825                 :            :   else
    2826                 :            :     {
    2827                 :      15137 :       max = determine_max_iter (loop, desc, old_niter);
    2828                 :      15137 :       if (!max)
    2829                 :          0 :         goto zero_iter_simplify;
    2830                 :      15137 :       if (!desc->infinite
    2831                 :       8455 :           && !desc->assumptions)
    2832                 :      16908 :         record_niter_bound (loop, max, false, true);
    2833                 :            : 
    2834                 :            :       /* simplify_using_initial_values does a copy propagation on the registers
    2835                 :            :          in the expression for the number of iterations.  This prolongs life
    2836                 :            :          ranges of registers and increases register pressure, and usually
    2837                 :            :          brings no gain (and if it happens to do, the cse pass will take care
    2838                 :            :          of it anyway).  So prevent this behavior, unless it enabled us to
    2839                 :            :          derive that the number of iterations is a constant.  */
    2840                 :      15137 :       desc->niter_expr = old_niter;
    2841                 :            :     }
    2842                 :            : 
    2843                 :            :   return;
    2844                 :            : 
    2845                 :          0 : zero_iter_simplify:
    2846                 :            :   /* Simplify the assumptions.  */
    2847                 :          0 :   simplify_using_initial_values (loop, AND, &desc->assumptions);
    2848                 :          0 :   if (desc->assumptions
    2849                 :          0 :       && XEXP (desc->assumptions, 0) == const0_rtx)
    2850                 :          0 :     goto fail;
    2851                 :          0 :   simplify_using_initial_values (loop, IOR, &desc->infinite);
    2852                 :            : 
    2853                 :            :   /* Fallthru.  */
    2854                 :          0 : zero_iter:
    2855                 :          0 :   desc->const_iter = true;
    2856                 :          0 :   desc->niter = 0;
    2857                 :          0 :   record_niter_bound (loop, 0, true, true);
    2858                 :          0 :   desc->noloop_assumptions = NULL_RTX;
    2859                 :          0 :   desc->niter_expr = const0_rtx;
    2860                 :          0 :   return;
    2861                 :            : 
    2862                 :       6677 : fail:
    2863                 :       6677 :   desc->simple_p = false;
    2864                 :       6677 :   return;
    2865                 :            : }
    2866                 :            : 
    2867                 :            : /* Checks whether E is a simple exit from LOOP and stores its description
    2868                 :            :    into DESC.  */
    2869                 :            : 
    2870                 :            : static void
    2871                 :      34530 : check_simple_exit (class loop *loop, edge e, class niter_desc *desc)
    2872                 :            : {
    2873                 :      34530 :   basic_block exit_bb;
    2874                 :      34530 :   rtx condition;
    2875                 :      34530 :   rtx_insn *at;
    2876                 :      34530 :   edge ein;
    2877                 :            : 
    2878                 :      34530 :   exit_bb = e->src;
    2879                 :      34530 :   desc->simple_p = false;
    2880                 :            : 
    2881                 :            :   /* It must belong directly to the loop.  */
    2882                 :      34530 :   if (exit_bb->loop_father != loop)
    2883                 :       9367 :     return;
    2884                 :            : 
    2885                 :            :   /* It must be tested (at least) once during any iteration.  */
    2886                 :      32437 :   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
    2887                 :            :     return;
    2888                 :            : 
    2889                 :            :   /* It must end in a simple conditional jump.  */
    2890                 :      27119 :   if (!any_condjump_p (BB_END (exit_bb)))
    2891                 :            :     return;
    2892                 :            : 
    2893                 :      27061 :   ein = EDGE_SUCC (exit_bb, 0);
    2894                 :      27061 :   if (ein == e)
    2895                 :      12580 :     ein = EDGE_SUCC (exit_bb, 1);
    2896                 :            : 
    2897                 :      27061 :   desc->out_edge = e;
    2898                 :      27061 :   desc->in_edge = ein;
    2899                 :            : 
    2900                 :            :   /* Test whether the condition is suitable.  */
    2901                 :      27061 :   if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
    2902                 :            :     return;
    2903                 :            : 
    2904                 :      25598 :   if (ein->flags & EDGE_FALLTHRU)
    2905                 :            :     {
    2906                 :       7856 :       condition = reversed_condition (condition);
    2907                 :       7856 :       if (!condition)
    2908                 :            :         return;
    2909                 :            :     }
    2910                 :            : 
    2911                 :            :   /* Check that we are able to determine number of iterations and fill
    2912                 :            :      in information about it.  */
    2913                 :      25163 :   iv_number_of_iterations (loop, at, condition, desc);
    2914                 :            : }
    2915                 :            : 
    2916                 :            : /* Finds a simple exit of LOOP and stores its description into DESC.  */
    2917                 :            : 
    2918                 :            : static void
    2919                 :      23195 : find_simple_exit (class loop *loop, class niter_desc *desc)
    2920                 :            : {
    2921                 :      23195 :   unsigned i;
    2922                 :      23195 :   basic_block *body;
    2923                 :      23195 :   edge e;
    2924                 :      23195 :   class niter_desc act;
    2925                 :      23195 :   bool any = false;
    2926                 :      23195 :   edge_iterator ei;
    2927                 :            : 
    2928                 :      23195 :   desc->simple_p = false;
    2929                 :      23195 :   body = get_loop_body (loop);
    2930                 :            : 
    2931                 :     253839 :   for (i = 0; i < loop->num_nodes; i++)
    2932                 :            :     {
    2933                 :     590121 :       FOR_EACH_EDGE (e, ei, body[i]->succs)
    2934                 :            :         {
    2935                 :     359477 :           if (flow_bb_inside_loop_p (loop, e->dest))
    2936                 :     324947 :             continue;
    2937                 :            : 
    2938                 :      34530 :           check_simple_exit (loop, e, &act);
    2939                 :      34530 :           if (!act.simple_p)
    2940                 :      16044 :             continue;
    2941                 :            : 
    2942                 :      18486 :           if (!any)
    2943                 :            :             any = true;
    2944                 :            :           else
    2945                 :            :             {
    2946                 :            :               /* Prefer constant iterations; the less the better.  */
    2947                 :         80 :               if (!act.const_iter
    2948                 :          6 :                   || (desc->const_iter && act.niter >= desc->niter))
    2949                 :         77 :                 continue;
    2950                 :            : 
    2951                 :            :               /* Also if the actual exit may be infinite, while the old one
    2952                 :            :                  not, prefer the old one.  */
    2953                 :          3 :               if (act.infinite && !desc->infinite)
    2954                 :          0 :                 continue;
    2955                 :            :             }
    2956                 :            : 
    2957                 :      18409 :           *desc = act;
    2958                 :            :         }
    2959                 :            :     }
    2960                 :            : 
    2961                 :      23195 :   if (dump_file)
    2962                 :            :     {
    2963                 :        106 :       if (desc->simple_p)
    2964                 :            :         {
    2965                 :         71 :           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
    2966                 :         71 :           fprintf (dump_file, "  simple exit %d -> %d\n",
    2967                 :         71 :                    desc->out_edge->src->index,
    2968                 :         71 :                    desc->out_edge->dest->index);
    2969                 :         71 :           if (desc->assumptions)
    2970                 :            :             {
    2971                 :          0 :               fprintf (dump_file, "  assumptions: ");
    2972                 :          0 :               print_rtl (dump_file, desc->assumptions);
    2973                 :          0 :               fprintf (dump_file, "\n");
    2974                 :            :             }
    2975                 :         71 :           if (desc->noloop_assumptions)
    2976                 :            :             {
    2977                 :          2 :               fprintf (dump_file, "  does not roll if: ");
    2978                 :          2 :               print_rtl (dump_file, desc->noloop_assumptions);
    2979                 :          2 :               fprintf (dump_file, "\n");
    2980                 :            :             }
    2981                 :         71 :           if (desc->infinite)
    2982                 :            :             {
    2983                 :         13 :               fprintf (dump_file, "  infinite if: ");
    2984                 :         13 :               print_rtl (dump_file, desc->infinite);
    2985                 :         13 :               fprintf (dump_file, "\n");
    2986                 :            :             }
    2987                 :            : 
    2988                 :         71 :           fprintf (dump_file, "  number of iterations: ");
    2989                 :         71 :           print_rtl (dump_file, desc->niter_expr);
    2990                 :         71 :           fprintf (dump_file, "\n");
    2991                 :            : 
    2992                 :         71 :           fprintf (dump_file, "  upper bound: %li\n",
    2993                 :            :                    (long)get_max_loop_iterations_int (loop));
    2994                 :         71 :           fprintf (dump_file, "  likely upper bound: %li\n",
    2995                 :            :                    (long)get_likely_max_loop_iterations_int (loop));
    2996                 :         71 :           fprintf (dump_file, "  realistic bound: %li\n",
    2997                 :            :                    (long)get_estimated_loop_iterations_int (loop));
    2998                 :            :         }
    2999                 :            :       else
    3000                 :         35 :         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
    3001                 :            :     }
    3002                 :            : 
    3003                 :            :   /* Fix up the finiteness if possible.  We can only do it for single exit,
    3004                 :            :      since the loop is finite, but it's possible that we predicate one loop
    3005                 :            :      exit to be finite which can not be determined as finite in middle-end as
    3006                 :            :      well.  It results in incorrect predicate information on the exit condition
    3007                 :            :      expression.  For example, if says [(int) _1 + -8, + , -8] != 0 finite,
    3008                 :            :      it means _1 can exactly divide -8.  */
    3009                 :      23195 :   if (desc->infinite && single_exit (loop) && finite_loop_p (loop))
    3010                 :            :     {
    3011                 :       5796 :       desc->infinite = NULL_RTX;
    3012                 :       5796 :       if (dump_file)
    3013                 :         13 :         fprintf (dump_file, "  infinite updated to finite.\n");
    3014                 :            :     }
    3015                 :            : 
    3016                 :      23195 :   free (body);
    3017                 :      23195 : }
    3018                 :            : 
    3019                 :            : /* Creates a simple loop description of LOOP if it was not computed
    3020                 :            :    already.  */
    3021                 :            : 
    3022                 :            : class niter_desc *
    3023                 :      83089 : get_simple_loop_desc (class loop *loop)
    3024                 :            : {
    3025                 :      83089 :   class niter_desc *desc = simple_loop_desc (loop);
    3026                 :            : 
    3027                 :      83089 :   if (desc)
    3028                 :            :     return desc;
    3029                 :            : 
    3030                 :            :   /* At least desc->infinite is not always initialized by
    3031                 :            :      find_simple_loop_exit.  */
    3032                 :      23195 :   desc = ggc_cleared_alloc<niter_desc> ();
    3033                 :      23195 :   iv_analysis_loop_init (loop);
    3034                 :      23195 :   find_simple_exit (loop, desc);
    3035                 :      23195 :   loop->simple_loop_desc = desc;
    3036                 :      23195 :   return desc;
    3037                 :            : }
    3038                 :            : 
    3039                 :            : /* Releases simple loop description for LOOP.  */
    3040                 :            : 
    3041                 :            : void
    3042                 :    2851260 : free_simple_loop_desc (class loop *loop)
    3043                 :            : {
    3044                 :    2851260 :   class niter_desc *desc = simple_loop_desc (loop);
    3045                 :            : 
    3046                 :    2851260 :   if (!desc)
    3047                 :            :     return;
    3048                 :            : 
    3049                 :      23195 :   ggc_free (desc);
    3050                 :      23195 :   loop->simple_loop_desc = NULL;
    3051                 :            : }

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.