/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc

Bug Summary

File:	build/gcc/loop-iv.cc
Warning:	line 589, column 18 The left operand of '==' is a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-suse-linux -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name loop-iv.cc -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model static -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -resource-dir /usr/lib64/clang/15.0.7 -D IN_GCC -D HAVE_CONFIG_H -I . -I . -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/. -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../include -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcpp/include -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcody -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber/bid -I ../libdecnumber -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libbacktrace -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/13/../../../../include/c++/13 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/13/../../../../include/c++/13/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/13/../../../../include/c++/13/backward -internal-isystem /usr/lib64/clang/15.0.7/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/13/../../../../x86_64-suse-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-narrowing -Wwrite-strings -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fdeprecated-macro -fdebug-compilation-dir=/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=plist-html -analyzer-config silence-checkers=core.NullDereference -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2023-03-27-141847-20772-1/report-XW2GA9.plist -x c++ /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc

1/* Rtl-level induction variable analysis.
 Copyright (C) 2004-2023 Free Software Foundation, Inc.

4This file is part of GCC.

6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.

11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.

16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */

20/* This is a simple analysis of induction variables of the loop.  The major use
 is for determining the number of iterations of a loop for loop unrolling,
 doloop optimization and branch prediction.  The iv information is computed
 on demand.

 Induction variables are analyzed by walking the use-def chains.  When
 a basic induction variable (biv) is found, it is cached in the bivs
 hash table.  When register is proved to be a biv, its description
 is stored to DF_REF_DATA of the def reference.

 The analysis works always with one loop -- you must call
 iv_analysis_loop_init (loop) for it.  All the other functions then work with
 this loop.   When you need to work with another loop, just call
 iv_analysis_loop_init for it.  When you no longer need iv analysis, call
 iv_analysis_done () to clean up the memory.

 The available functions are:

 iv_analyze (insn, mode, reg, iv): Stores the description of the induction
   variable corresponding to the use of register REG in INSN to IV, given
   that REG has mode MODE.  Returns true if REG is an induction variable
   in INSN. false otherwise.  If a use of REG is not found in INSN,
   the following insns are scanned (so that we may call this function
   on insns returned by get_condition).
 iv_analyze_result (insn, def, iv):  Stores to IV the description of the iv
   corresponding to DEF, which is a register defined in INSN.
 iv_analyze_expr (insn, mode, expr, iv):  Stores to IV the description of iv
   corresponding to expression EXPR evaluated at INSN.  All registers used by
   EXPR must also be used in INSN.  MODE is the mode of EXPR.
49*/

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"

68/* Possible return values of iv_get_reaching_def.  */

70enum iv_grd_result
71{
/* More than one reaching def, or reaching def that does not
   dominate the use.  */
GRD_INVALID,

/* The use is trivial invariant of the loop, i.e. is not changed
   inside the loop.  */
GRD_INVARIANT,

/* The use is reached by initial value and a value from the
   previous iteration.  */
GRD_MAYBE_BIV,

/* The use has single dominating def.  */
GRD_SINGLE_DOM
86};

88/* Information about a biv.  */

90class biv_entry
91{
92public:
unsigned regno;	/* The register of the biv.  */
class rtx_iv iv;	/* Value of the biv.  */
95};

97static bool clean_slate = true;

99static unsigned int iv_ref_table_size = 0;

101/* Table of rtx_ivs indexed by the df_ref uid field.  */
102static class rtx_iv ** iv_ref_table;

104/* Induction variable stored at the reference.  */
105#define DF_REF_IV(REF)iv_ref_table[((REF)->base.id)] iv_ref_table[DF_REF_ID (REF)((REF)->base.id)]
106#define DF_REF_IV_SET(REF, IV)iv_ref_table[((REF)->base.id)] = (IV) iv_ref_table[DF_REF_ID (REF)((REF)->base.id)] = (IV)

108/* The current loop.  */

110static class loop *current_loop;

112/* Hashtable helper.  */

114struct biv_entry_hasher : free_ptr_hash <biv_entry>
115{
typedef rtx_def *compare_type;
static inline hashval_t hash (const biv_entry *);
static inline bool equal (const biv_entry *, const rtx_def *);
119};

121/* Returns hash value for biv B.  */

123inline hashval_t
124biv_entry_hasher::hash (const biv_entry *b)
125{
return b->regno;
127}

129/* Compares biv B and register R.  */

131inline bool
132biv_entry_hasher::equal (const biv_entry *b, const rtx_def *r)
133{
return b->regno == REGNO (r)(rhs_regno(r));
135}

137/* Bivs of the current loop.  */

139static hash_table<biv_entry_hasher> *bivs;

141static bool iv_analyze_op (rtx_insn *, scalar_int_mode, rtx, class rtx_iv *);

143/* Return the RTX code corresponding to the IV extend code EXTEND.  */
144static inline enum rtx_code
145iv_extend_to_rtx_code (enum iv_extend_code extend)
146{
switch (extend)
  {
  case IV_SIGN_EXTEND:
    return SIGN_EXTEND;
  case IV_ZERO_EXTEND:
    return ZERO_EXTEND;
  case IV_UNKNOWN_EXTEND:
    return UNKNOWN;
  }
gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 156, __FUNCTION__));
157}

159/* Dumps information about IV to FILE.  */

161extern void dump_iv_info (FILE *, class rtx_iv *);
162void
163dump_iv_info (FILE *file, class rtx_iv *iv)
164{
if (!iv->base)
  {
    fprintf (file, "not simple");
    return;
  }

if (iv->step == const0_rtx(const_int_rtx[64])
    && !iv->first_special)
  fprintf (file, "invariant ");

print_rtl (file, iv->base);
if (iv->step != const0_rtx(const_int_rtx[64]))
  {
    fprintf (file, " + ");
    print_rtl (file, iv->step);
    fprintf (file, " * iteration");
  }
fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode)mode_name[iv->mode]);

if (iv->mode != iv->extend_mode)
  fprintf (file, " %s to %s",
    rtx_name[iv_extend_to_rtx_code (iv->extend)],
    GET_MODE_NAME (iv->extend_mode)mode_name[iv->extend_mode]);

if (iv->mult != const1_rtx(const_int_rtx[64 +1]))
  {
    fprintf (file, " * ");
    print_rtl (file, iv->mult);
  }
if (iv->delta != const0_rtx(const_int_rtx[64]))
  {
    fprintf (file, " + ");
    print_rtl (file, iv->delta);
  }
if (iv->first_special)
  fprintf (file, " (first special)");
201}

203static void
204check_iv_ref_table_size (void)
205{
if (iv_ref_table_size < DF_DEFS_TABLE_SIZE ()(df->def_info.table_size))
  {
    unsigned int new_size = DF_DEFS_TABLE_SIZE ()(df->def_info.table_size) + (DF_DEFS_TABLE_SIZE ()(df->def_info.table_size) / 4);
    iv_ref_table = XRESIZEVEC (class rtx_iv *, iv_ref_table, new_size)((class rtx_iv * *) xrealloc ((void *) (iv_ref_table), sizeof
 (class rtx_iv *) * (new_size)));
    memset (&iv_ref_table[iv_ref_table_size], 0,
     (new_size - iv_ref_table_size) * sizeof (class rtx_iv *));
    iv_ref_table_size = new_size;
  }
214}


217/* Checks whether REG is a well-behaved register.  */

219static bool
220simple_reg_p (rtx reg)
221{
unsigned r;

if (GET_CODE (reg)((enum rtx_code) (reg)->code) == SUBREG)
  {
    if (!subreg_lowpart_p (reg))
return false;
    reg = SUBREG_REG (reg)(((reg)->u.fld[0]).rt_rtx);
  }

if (!REG_P (reg)(((enum rtx_code) (reg)->code) == REG))
  return false;

r = REGNO (reg)(rhs_regno(reg));
if (HARD_REGISTER_NUM_P (r)((r) < 76))
  return false;

if (GET_MODE_CLASS (GET_MODE (reg))((enum mode_class) mode_class[((machine_mode) (reg)->mode)
]) != MODE_INT)
  return false;

return true;
242}

244/* Clears the information about ivs stored in df.  */

246static void
247clear_iv_info (void)
248{
unsigned i, n_defs = DF_DEFS_TABLE_SIZE ()(df->def_info.table_size);
class rtx_iv *iv;

check_iv_ref_table_size ();
for (i = 0; i < n_defs; i++)
  {
    iv = iv_ref_table[i];
    if (iv)
{
 free (iv);
 iv_ref_table[i] = NULL__null;
}
  }

bivs->empty ();
264}


267/* Prepare the data for an induction variable analysis of a LOOP.  */

269void
270iv_analysis_loop_init (class loop *loop)
271{
current_loop = loop;

/* Clear the information from the analysis of the previous loop.  */
if (clean_slate)
  {
    df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
    bivs = new hash_table<biv_entry_hasher> (10);
    clean_slate = false;
  }
else
  clear_iv_info ();

/* Get rid of the ud chains before processing the rescans.  Then add
   the problem back.  */
df_remove_problem (df_chain(df->problems_by_index[DF_CHAIN]));
df_process_deferred_rescans ();
df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
df_chain_add_problem (DF_UD_CHAIN);
df_note_add_problem ();
df_analyze_loop (loop);
if (dump_file)
  df_dump_region (dump_file);

check_iv_ref_table_size ();
296}

298/* Finds the definition of REG that dominates loop latch and stores
 it to DEF.  Returns false if there is not a single definition
 dominating the latch.  If REG has no definition in loop, DEF
 is set to NULL and true is returned.  */

303static bool
304latch_dominating_def (rtx reg, df_ref *def)
305{
df_ref single_rd = NULL__null, adef;
unsigned regno = REGNO (reg)(rhs_regno(reg));
class df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch)(df_rd_get_bb_info ((current_loop->latch)->index));

for (adef = DF_REG_DEF_CHAIN (regno)(df->def_regs[(regno)]->reg_chain); adef; adef = DF_REF_NEXT_REG (adef)((adef)->base.next_reg))
  {
    if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef)(((((adef)->base.cl) == DF_REF_ARTIFICIAL) ? (adef)->artificial_ref
.bb : BLOCK_FOR_INSN (((adef)->base.insn_info->insn)))->
index))
 || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)((adef)->base.id)))
continue;

    /* More than one reaching definition.  */
    if (single_rd)
return false;

    if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)((((adef)->base.cl) == DF_REF_ARTIFICIAL) ? (adef)->artificial_ref
.bb : BLOCK_FOR_INSN (((adef)->base.insn_info->insn)))))
return false;

    single_rd = adef;
  }

*def = single_rd;
return true;
328}

330/* Gets definition of REG reaching its use in INSN and stores it to DEF.  */

332static enum iv_grd_result
333iv_get_reaching_def (rtx_insn *insn, rtx reg, df_ref *def)
334{
df_ref use, adef;
basic_block def_bb, use_bb;
rtx_insn *def_insn;
bool dom_p;

*def = NULL__null;
if (!simple_reg_p (reg))
  return GRD_INVALID;
if (GET_CODE (reg)((enum rtx_code) (reg)->code) == SUBREG)
  reg = SUBREG_REG (reg)(((reg)->u.fld[0]).rt_rtx);
gcc_assert (REG_P (reg))((void)(!((((enum rtx_code) (reg)->code) == REG)) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 345, __FUNCTION__), 0 : 0));

use = df_find_use (insn, reg);
gcc_assert (use != NULL)((void)(!(use != __null) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 348, __FUNCTION__), 0 : 0));

if (!DF_REF_CHAIN (use)((use)->base.chain))
  return GRD_INVARIANT;

/* More than one reaching def.  */
if (DF_REF_CHAIN (use)((use)->base.chain)->next)
  return GRD_INVALID;

adef = DF_REF_CHAIN (use)((use)->base.chain)->ref;

/* We do not handle setting only part of the register.  */
if (DF_REF_FLAGS (adef)((adef)->base.flags) & DF_REF_READ_WRITE)
  return GRD_INVALID;

def_insn = DF_REF_INSN (adef)((adef)->base.insn_info->insn);
def_bb = DF_REF_BB (adef)((((adef)->base.cl) == DF_REF_ARTIFICIAL) ? (adef)->artificial_ref
.bb : BLOCK_FOR_INSN (((adef)->base.insn_info->insn)));
use_bb = BLOCK_FOR_INSN (insn);

if (use_bb == def_bb)
  dom_p = (DF_INSN_LUID (def_insn)((((df->insns[(INSN_UID (def_insn))]))->luid)) < DF_INSN_LUID (insn)((((df->insns[(INSN_UID (insn))]))->luid)));
else
  dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);

if (dom_p)
  {
    *def = adef;
    return GRD_SINGLE_DOM;
  }

/* The definition does not dominate the use.  This is still OK if
   this may be a use of a biv, i.e. if the def_bb dominates loop
   latch.  */
if (just_once_each_iteration_p (current_loop, def_bb))
  return GRD_MAYBE_BIV;

return GRD_INVALID;
385}

387/* Sets IV to invariant CST in MODE.  Always returns true (just for
 consistency with other iv manipulation functions that may fail).  */

390static bool
391iv_constant (class rtx_iv *iv, scalar_int_mode mode, rtx cst)
392{
iv->mode = mode;
iv->base = cst;
iv->step = const0_rtx(const_int_rtx[64]);
iv->first_special = false;
iv->extend = IV_UNKNOWN_EXTEND;
iv->extend_mode = iv->mode;
iv->delta = const0_rtx(const_int_rtx[64]);
iv->mult = const1_rtx(const_int_rtx[64 +1]);

return true;
403}

405/* Evaluates application of subreg to MODE on IV.  */

407static bool
408iv_subreg (class rtx_iv *iv, scalar_int_mode mode)
409{
/* If iv is invariant, just calculate the new value.  */
if (iv->step == const0_rtx(const_int_rtx[64])
    && !iv->first_special)
  {
    rtx val = get_iv_value (iv, const0_rtx(const_int_rtx[64]));
    val = lowpart_subreg (mode, val,
	    iv->extend == IV_UNKNOWN_EXTEND
	    ? iv->mode : iv->extend_mode);

    iv->base = val;
    iv->extend = IV_UNKNOWN_EXTEND;
    iv->mode = iv->extend_mode = mode;
    iv->delta = const0_rtx(const_int_rtx[64]);
    iv->mult = const1_rtx(const_int_rtx[64 +1]);
    return true;
  }

if (iv->extend_mode == mode)
  return true;

if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
  return false;

iv->extend = IV_UNKNOWN_EXTEND;
iv->mode = mode;

iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
		  simplify_gen_binary (MULT, iv->extend_mode,
				       iv->base, iv->mult));
iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
iv->mult = const1_rtx(const_int_rtx[64 +1]);
iv->delta = const0_rtx(const_int_rtx[64]);
iv->first_special = false;

return true;
445}

447/* Evaluates application of EXTEND to MODE on IV.  */

449static bool
450iv_extend (class rtx_iv *iv, enum iv_extend_code extend, scalar_int_mode mode)
451{
/* If iv is invariant, just calculate the new value.  */
if (iv->step == const0_rtx(const_int_rtx[64])
    && !iv->first_special)
  {
    rtx val = get_iv_value (iv, const0_rtx(const_int_rtx[64]));
    if (iv->extend_mode != iv->mode
 && iv->extend != IV_UNKNOWN_EXTEND
 && iv->extend != extend)
val = lowpart_subreg (iv->mode, val, iv->extend_mode);
    val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
		val,
		iv->extend == extend
		? iv->extend_mode : iv->mode);
    iv->base = val;
    iv->extend = IV_UNKNOWN_EXTEND;
    iv->mode = iv->extend_mode = mode;
    iv->delta = const0_rtx(const_int_rtx[64]);
    iv->mult = const1_rtx(const_int_rtx[64 +1]);
    return true;
  }

if (mode != iv->extend_mode)
  return false;

if (iv->extend != IV_UNKNOWN_EXTEND
    && iv->extend != extend)
  return false;

iv->extend = extend;

return true;
483}

485/* Evaluates negation of IV.  */

487static bool
488iv_neg (class rtx_iv *iv)
489{
if (iv->extend == IV_UNKNOWN_EXTEND)
  {
    iv->base = simplify_gen_unary (NEG, iv->extend_mode,
		     iv->base, iv->extend_mode);
    iv->step = simplify_gen_unary (NEG, iv->extend_mode,
		     iv->step, iv->extend_mode);
  }
else
  {
    iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
		      iv->delta, iv->extend_mode);
    iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
		     iv->mult, iv->extend_mode);
  }

return true;
506}

508/* Evaluates addition or subtraction (according to OP) of IV1 to IV0.  */

510static bool
511iv_add (class rtx_iv *iv0, class rtx_iv *iv1, enum rtx_code op)
512{
scalar_int_mode mode;
rtx arg;

/* Extend the constant to extend_mode of the other operand if necessary.  */
if (iv0->extend == IV_UNKNOWN_EXTEND
    && iv0->mode == iv0->extend_mode
    && iv0->step == const0_rtx(const_int_rtx[64])
    && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
  {
    iv0->extend_mode = iv1->extend_mode;
    iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
		      iv0->base, iv0->mode);
  }
if (iv1->extend == IV_UNKNOWN_EXTEND
    && iv1->mode == iv1->extend_mode
    && iv1->step == const0_rtx(const_int_rtx[64])
    && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
  {
    iv1->extend_mode = iv0->extend_mode;
    iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
		      iv1->base, iv1->mode);
  }

mode = iv0->extend_mode;
if (mode != iv1->extend_mode)
  return false;

if (iv0->extend == IV_UNKNOWN_EXTEND
    && iv1->extend == IV_UNKNOWN_EXTEND)
  {
    if (iv0->mode != iv1->mode)
return false;

    iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
    iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);

    return true;
  }

/* Handle addition of constant.  */
if (iv1->extend == IV_UNKNOWN_EXTEND
    && iv1->mode == mode
    && iv1->step == const0_rtx(const_int_rtx[64]))
  {
    iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
    return true;
  }

if (iv0->extend == IV_UNKNOWN_EXTEND
    && iv0->mode == mode
    && iv0->step == const0_rtx(const_int_rtx[64]))
  {
    arg = iv0->base;
    *iv0 = *iv1;
    if (op == MINUS
 && !iv_neg (iv0))
return false;

    iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
    return true;
  }

return false;
576}

578/* Evaluates multiplication of IV by constant CST.  */

580static bool
581iv_mult (class rtx_iv *iv, rtx mby)
582{
scalar_int_mode mode = iv->extend_mode;

if (GET_MODE (mby)((machine_mode) (mby)->mode) != VOIDmode((void) 0, E_VOIDmode)
33
←
Assuming the condition is false→
    && GET_MODE (mby)((machine_mode) (mby)->mode) != mode)
  return false;

if (iv->extend == IV_UNKNOWN_EXTEND)
34
←
The left operand of '==' is a garbage value
  {
    iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
    iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
  }
else
  {
    iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
    iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
  }

return true;
601}

603/* Evaluates shift of IV by constant CST.  */

605static bool
606iv_shift (class rtx_iv *iv, rtx mby)
607{
scalar_int_mode mode = iv->extend_mode;

if (GET_MODE (mby)((machine_mode) (mby)->mode) != VOIDmode((void) 0, E_VOIDmode)
    && GET_MODE (mby)((machine_mode) (mby)->mode) != mode)
  return false;

if (iv->extend == IV_UNKNOWN_EXTEND)
  {
    iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
    iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
  }
else
  {
    iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
    iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
  }

return true;
626}

628/* The recursive part of get_biv_step.  Gets the value of the single value
 defined by DEF wrto initial value of REG inside loop, in shape described
 at get_biv_step.  */

632static bool
633get_biv_step_1 (df_ref def, scalar_int_mode outer_mode, rtx reg,
rtx *inner_step, scalar_int_mode *inner_mode,
enum iv_extend_code *extend,
rtx *outer_step)
637{
rtx set, rhs, op0 = NULL_RTX(rtx) 0, op1 = NULL_RTX(rtx) 0;
rtx next, nextr;
enum rtx_code code;
rtx_insn *insn = DF_REF_INSN (def)((def)->base.insn_info->insn);
df_ref next_def;
enum iv_grd_result res;

set = single_set (insn);
if (!set)
  return false;

rhs = find_reg_equal_equiv_note (insn);
if (rhs)
  rhs = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
else
  rhs = SET_SRC (set)(((set)->u.fld[1]).rt_rtx);

code = GET_CODE (rhs)((enum rtx_code) (rhs)->code);
switch (code)
  {
  case SUBREG:
  case REG:
    next = rhs;
    break;

  case PLUS:
  case MINUS:
    op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
    op1 = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);

    if (code == PLUS && CONSTANT_P (op0)((rtx_class[(int) (((enum rtx_code) (op0)->code))]) == RTX_CONST_OBJ
))
std::swap (op0, op1);

    if (!simple_reg_p (op0)
 || !CONSTANT_P (op1)((rtx_class[(int) (((enum rtx_code) (op1)->code))]) == RTX_CONST_OBJ
))
return false;

    if (GET_MODE (rhs)((machine_mode) (rhs)->mode) != outer_mode)
{
 /* ppc64 uses expressions like

    (set x:SI (plus:SI (subreg:SI y:DI) 1)).

    this is equivalent to

    (set x':DI (plus:DI y:DI 1))
    (set x:SI (subreg:SI (x':DI)).  */
 if (GET_CODE (op0)((enum rtx_code) (op0)->code) != SUBREG)
   return false;
 if (GET_MODE (SUBREG_REG (op0))((machine_mode) ((((op0)->u.fld[0]).rt_rtx))->mode) != outer_mode)
   return false;
}

    next = op0;
    break;

  case SIGN_EXTEND:
  case ZERO_EXTEND:
    if (GET_MODE (rhs)((machine_mode) (rhs)->mode) != outer_mode)
return false;

    op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
    if (!simple_reg_p (op0))
return false;

    next = op0;
    break;

  default:
    return false;
  }

if (GET_CODE (next)((enum rtx_code) (next)->code) == SUBREG)
  {
    if (!subreg_lowpart_p (next))
return false;

    nextr = SUBREG_REG (next)(((next)->u.fld[0]).rt_rtx);
    if (GET_MODE (nextr)((machine_mode) (nextr)->mode) != outer_mode)
return false;
  }
else
  nextr = next;

res = iv_get_reaching_def (insn, nextr, &next_def);

if (res == GRD_INVALID || res == GRD_INVARIANT)
  return false;

if (res == GRD_MAYBE_BIV)
  {
    if (!rtx_equal_p (nextr, reg))
return false;

    *inner_step = const0_rtx(const_int_rtx[64]);
    *extend = IV_UNKNOWN_EXTEND;
    *inner_mode = outer_mode;
    *outer_step = const0_rtx(const_int_rtx[64]);
  }
else if (!get_biv_step_1 (next_def, outer_mode, reg,
	    inner_step, inner_mode, extend,
	    outer_step))
  return false;

if (GET_CODE (next)((enum rtx_code) (next)->code) == SUBREG)
  {
    scalar_int_mode amode;
    if (!is_a <scalar_int_mode> (GET_MODE (next)((machine_mode) (next)->mode), &amode)
 || GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
return false;

    *inner_mode = amode;
    *inner_step = simplify_gen_binary (PLUS, outer_mode,
			 *inner_step, *outer_step);
    *outer_step = const0_rtx(const_int_rtx[64]);
    *extend = IV_UNKNOWN_EXTEND;
  }

switch (code)
  {
  case REG:
  case SUBREG:
    break;

  case PLUS:
  case MINUS:
    if (*inner_mode == outer_mode
 /* See comment in previous switch.  */
 || GET_MODE (rhs)((machine_mode) (rhs)->mode) != outer_mode)
*inner_step = simplify_gen_binary (code, outer_mode,
			   *inner_step, op1);
    else
*outer_step = simplify_gen_binary (code, outer_mode,
			   *outer_step, op1);
    break;

  case SIGN_EXTEND:
  case ZERO_EXTEND:
    gcc_assert (GET_MODE (op0) == *inner_mode((void)(!(((machine_mode) (op0)->mode) == *inner_mode &&
 *extend == IV_UNKNOWN_EXTEND && *outer_step == (const_int_rtx
[64])) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 778, __FUNCTION__), 0 : 0))
  && *extend == IV_UNKNOWN_EXTEND((void)(!(((machine_mode) (op0)->mode) == *inner_mode &&
 *extend == IV_UNKNOWN_EXTEND && *outer_step == (const_int_rtx
[64])) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 778, __FUNCTION__), 0 : 0))
  && *outer_step == const0_rtx)((void)(!(((machine_mode) (op0)->mode) == *inner_mode &&
 *extend == IV_UNKNOWN_EXTEND && *outer_step == (const_int_rtx
[64])) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 778, __FUNCTION__), 0 : 0));

    *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
    break;

  default:
    return false;
  }

return true;
788}

790/* Gets the operation on register REG inside loop, in shape

 OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))

 If the operation cannot be described in this shape, return false.
 LAST_DEF is the definition of REG that dominates loop latch.  */

797static bool
798get_biv_step (df_ref last_def, scalar_int_mode outer_mode, rtx reg,
     rtx *inner_step, scalar_int_mode *inner_mode,
     enum iv_extend_code *extend, rtx *outer_step)
801{
if (!get_biv_step_1 (last_def, outer_mode, reg,
       inner_step, inner_mode, extend,
       outer_step))
  return false;

gcc_assert ((*inner_mode == outer_mode) != (*extend != IV_UNKNOWN_EXTEND))((void)(!((*inner_mode == outer_mode) != (*extend != IV_UNKNOWN_EXTEND
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 807, __FUNCTION__), 0 : 0));
gcc_assert (*inner_mode != outer_mode || *outer_step == const0_rtx)((void)(!(*inner_mode != outer_mode || *outer_step == (const_int_rtx
[64])) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 808, __FUNCTION__), 0 : 0));

return true;
811}

813/* Records information that DEF is induction variable IV.  */

815static void
816record_iv (df_ref def, class rtx_iv *iv)
817{
class rtx_iv *recorded_iv = XNEW (class rtx_iv)((class rtx_iv *) xmalloc (sizeof (class rtx_iv)));

*recorded_iv = *iv;
check_iv_ref_table_size ();
DF_REF_IV_SET (def, recorded_iv)iv_ref_table[((def)->base.id)] = (recorded_iv);
823}

825/* If DEF was already analyzed for bivness, store the description of the biv to
 IV and return true.  Otherwise return false.  */

828static bool
829analyzed_for_bivness_p (rtx def, class rtx_iv *iv)
830{
class biv_entry *biv = bivs->find_with_hash (def, REGNO (def)(rhs_regno(def)));

if (!biv)
  return false;

*iv = biv->iv;
return true;
838}

840static void
841record_biv (rtx def, class rtx_iv *iv)
842{
class biv_entry *biv = XNEW (class biv_entry)((class biv_entry *) xmalloc (sizeof (class biv_entry)));
biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def)(rhs_regno(def)), INSERT);

biv->regno = REGNO (def)(rhs_regno(def));
biv->iv = *iv;
gcc_assert (!*slot)((void)(!(!*slot) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 848, __FUNCTION__), 0 : 0));
*slot = biv;
850}

852/* Determines whether DEF is a biv and if so, stores its description
 to *IV.  OUTER_MODE is the mode of DEF.  */

855static bool
856iv_analyze_biv (scalar_int_mode outer_mode, rtx def, class rtx_iv *iv)
857{
rtx inner_step, outer_step;
scalar_int_mode inner_mode;
enum iv_extend_code extend;
df_ref last_def;

if (dump_file)
  {
    fprintf (dump_file, "Analyzing ");
    print_rtl (dump_file, def);
    fprintf (dump_file, " for bivness.\n");
  }

if (!REG_P (def)(((enum rtx_code) (def)->code) == REG))
  {
    if (!CONSTANT_P (def)((rtx_class[(int) (((enum rtx_code) (def)->code))]) == RTX_CONST_OBJ
))
return false;

    return iv_constant (iv, outer_mode, def);
  }

if (!latch_dominating_def (def, &last_def))
  {
    if (dump_file)
fprintf (dump_file, "  not simple.\n");
    return false;
  }

if (!last_def)
  return iv_constant (iv, outer_mode, def);

if (analyzed_for_bivness_p (def, iv))
  {
    if (dump_file)
fprintf (dump_file, "  already analysed.\n");
    return iv->base != NULL_RTX(rtx) 0;
  }

if (!get_biv_step (last_def, outer_mode, def, &inner_step, &inner_mode,
     &extend, &outer_step))
  {
    iv->base = NULL_RTX(rtx) 0;
    goto end;
  }

/* Loop transforms base to es (base + inner_step) + outer_step,
   where es means extend of subreg between inner_mode and outer_mode.
   The corresponding induction variable is

   es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step  */

iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
iv->mode = inner_mode;
iv->extend_mode = outer_mode;
iv->extend = extend;
iv->mult = const1_rtx(const_int_rtx[64 +1]);
iv->delta = outer_step;
iv->first_special = inner_mode != outer_mode;

end:
if (dump_file)
  {
    fprintf (dump_file, "  ");
    dump_iv_info (dump_file, iv);
    fprintf (dump_file, "\n");
  }

record_biv (def, iv);
return iv->base != NULL_RTX(rtx) 0;
927}

929/* Analyzes expression RHS used at INSN and stores the result to *IV.
 The mode of the induction variable is MODE.  */

932bool
933iv_analyze_expr (rtx_insn *insn, scalar_int_mode mode, rtx rhs,
 class rtx_iv *iv)
935{
rtx mby = NULL_RTX(rtx) 0;
rtx op0 = NULL_RTX(rtx) 0, op1 = NULL_RTX(rtx) 0;
class rtx_iv iv0, iv1;
enum rtx_code code = GET_CODE (rhs)((enum rtx_code) (rhs)->code);
scalar_int_mode omode = mode;

iv->base = NULL_RTX(rtx) 0;
iv->step = NULL_RTX(rtx) 0;

gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode)((void)(!(((machine_mode) (rhs)->mode) == mode || ((machine_mode
) (rhs)->mode) == ((void) 0, E_VOIDmode)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 945, __FUNCTION__), 0 : 0));
19
←
Assuming the condition is true→
20
←
'?' condition is false→

if (CONSTANT_P (rhs)((rtx_class[(int) (((enum rtx_code) (rhs)->code))]) == RTX_CONST_OBJ
)
21
←
Assuming the condition is false→
24
←
Taking false branch→
    || REG_P (rhs)(((enum rtx_code) (rhs)->code) == REG)
22
←
Assuming field 'code' is not equal to REG→
    || code == SUBREG)
23
←
Assuming 'code' is not equal to SUBREG→
  return iv_analyze_op (insn, mode, rhs, iv);

switch (code)
25
←
Control jumps to 'case MULT:'  at line 973→
  {
  case REG:
    op0 = rhs;
    break;

  case SIGN_EXTEND:
  case ZERO_EXTEND:
  case NEG:
    op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
    /* We don't know how many bits there are in a sign-extended constant.  */
    if (!is_a <scalar_int_mode> (GET_MODE (op0)((machine_mode) (op0)->mode), &omode))
return false;
    break;

  case PLUS:
  case MINUS:
    op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
    op1 = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
    break;

  case MULT:
    op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
    mby = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
    if (!CONSTANT_P (mby)((rtx_class[(int) (((enum rtx_code) (mby)->code))]) == RTX_CONST_OBJ
))
26
←
Assuming the condition is false→
27
←
Taking false branch→
std::swap (op0, mby);
    if (!CONSTANT_P (mby)((rtx_class[(int) (((enum rtx_code) (mby)->code))]) == RTX_CONST_OBJ
))
28
←
Assuming the condition is false→
29
←
Taking false branch→
return false;
    break;

  case ASHIFT:
    op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
    mby = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
    if (!CONSTANT_P (mby)((rtx_class[(int) (((enum rtx_code) (mby)->code))]) == RTX_CONST_OBJ
))
return false;
    break;

  default:
    return false;
  }

if (op0
30
←
Assuming 'op0' is null→
    && !iv_analyze_expr (insn, omode, op0, &iv0))
  return false;

if (op1

30.1	'op1' is null

998 && !iv_analyze_expr (insn, omode, op1, &iv1)) 999 return false; 1000 1001 switch (code)

←

Control jumps to 'case MULT:' at line 1024

→

1002 { 1003 case SIGN_EXTEND: 1004 if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode)) 1005 return false; 1006 break; 1007 1008 case ZERO_EXTEND: 1009 if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode)) 1010 return false; 1011 break; 1012 1013 case NEG: 1014 if (!iv_neg (&iv0)) 1015 return false; 1016 break; 1017 1018 case PLUS: 1019 case MINUS: 1020 if (!iv_add (&iv0, &iv1, code)) 1021 return false; 1022 break; 1023 1024 case MULT: 1025 if (!iv_mult (&iv0, mby))

←

Calling 'iv_mult'

→

1026 return false; 1027 break; 1028 1029 case ASHIFT: 1030 if (!iv_shift (&iv0, mby)) 1031 return false; 1032 break; 1033 1034 default: 1035 break; 1036 } 1037 1038 *iv = iv0; 1039 return iv->base != NULL_RTX(rtx) 0; 1040} 1041 1042/* Analyzes iv DEF and stores the result to *IV. */ 1043 1044static bool 1045iv_analyze_def (df_ref def, class rtx_iv *iv) 1046{ 1047 rtx_insn *insn = DF_REF_INSN (def)((def)->base.insn_info->insn); 1048 rtx reg = DF_REF_REG (def)((def)->base.reg); 1049 rtx set, rhs; 1050 1051 if (dump_file)

←

Assuming 'dump_file' is null

→

←

Taking false branch

→

1052 { 1053 fprintf (dump_file, "Analyzing def of "); 1054 print_rtl (dump_file, reg); 1055 fprintf (dump_file, " in insn "); 1056 print_rtl_single (dump_file, insn); 1057 } 1058 1059 check_iv_ref_table_size (); 1060 if (DF_REF_IV (def)iv_ref_table[((def)->base.id)])

←

Assuming the condition is false

→

←

Taking false branch

→

1061 { 1062 if (dump_file) 1063 fprintf (dump_file, " already analysed.\n"); 1064 *iv = *DF_REF_IV (def)iv_ref_table[((def)->base.id)]; 1065 return iv->base != NULL_RTX(rtx) 0; 1066 } 1067 1068 iv->base = NULL_RTX(rtx) 0; 1069 iv->step = NULL_RTX(rtx) 0; 1070 1071 scalar_int_mode mode; 1072 if (!REG_P (reg)(((enum rtx_code) (reg)->code) == REG) || !is_a <scalar_int_mode> (GET_MODE (reg)((machine_mode) (reg)->mode), &mode))

←

Assuming field 'code' is equal to REG

→

←

Taking false branch

→

1073 return false; 1074 1075 set = single_set (insn); 1076 if (!set)

←

Assuming 'set' is non-null

→

←

Taking false branch

→

1077 return false; 1078 1079 if (!REG_P (SET_DEST (set))(((enum rtx_code) ((((set)->u.fld[0]).rt_rtx))->code) ==
REG))

←

Assuming field 'code' is equal to REG

→

←

Taking false branch

→

1080 return false; 1081 1082 gcc_assert (SET_DEST (set) == reg)((void)(!((((set)->u.fld[0]).rt_rtx) == reg) ? fancy_abort
("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 1082, __FUNCTION__), 0 : 0));

←

Assuming 'reg' is equal to field 'rt_rtx'

→

←

'?' condition is false

→

1083 rhs = find_reg_equal_equiv_note (insn); 1084 if (rhs)

←

Assuming 'rhs' is null

→

←

Taking false branch

→

1085 rhs = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx); 1086 else 1087 rhs = SET_SRC (set)(((set)->u.fld[1]).rt_rtx); 1088 1089 iv_analyze_expr (insn, mode, rhs, iv);

←

Calling 'iv_analyze_expr'

→

1090 record_iv (def, iv); 1091 1092 if (dump_file) 1093 { 1094 print_rtl (dump_file, reg); 1095 fprintf (dump_file, " in insn "); 1096 print_rtl_single (dump_file, insn); 1097 fprintf (dump_file, " is "); 1098 dump_iv_info (dump_file, iv); 1099 fprintf (dump_file, "\n"); 1100 } 1101 1102 return iv->base != NULL_RTX(rtx) 0; 1103} 1104 1105/* Analyzes operand OP of INSN and stores the result to *IV. MODE is the 1106 mode of OP. */ 1107 1108static bool 1109iv_analyze_op (rtx_insn *insn, scalar_int_mode mode, rtx op, class rtx_iv *iv) 1110{ 1111 df_ref def = NULL__null; 1112 enum iv_grd_result res; 1113 1114 if (dump_file) 1115 { 1116 fprintf (dump_file, "Analyzing operand "); 1117 print_rtl (dump_file, op); 1118 fprintf (dump_file, " of insn "); 1119 print_rtl_single (dump_file, insn); 1120 } 1121 1122 if (function_invariant_p (op)) 1123 res = GRD_INVARIANT; 1124 else if (GET_CODE (op)((enum rtx_code) (op)->code) == SUBREG) 1125 { 1126 scalar_int_mode inner_mode; 1127 if (!subreg_lowpart_p (op) 1128 || !is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (op))((machine_mode) ((((op)->u.fld[0]).rt_rtx))->mode), &inner_mode)) 1129 return false; 1130 1131 if (!iv_analyze_op (insn, inner_mode, SUBREG_REG (op)(((op)->u.fld[0]).rt_rtx), iv)) 1132 return false; 1133 1134 return iv_subreg (iv, mode); 1135 } 1136 else 1137 { 1138 res = iv_get_reaching_def (insn, op, &def); 1139 if (res == GRD_INVALID) 1140 { 1141 if (dump_file) 1142 fprintf (dump_file, " not simple.\n"); 1143 return false; 1144 } 1145 } 1146 1147 if (res == GRD_INVARIANT) 1148 { 1149 iv_constant (iv, mode, op); 1150 1151 if (dump_file) 1152 { 1153 fprintf (dump_file, " "); 1154 dump_iv_info (dump_file, iv); 1155 fprintf (dump_file, "\n"); 1156 } 1157 return true; 1158 } 1159 1160 if (res == GRD_MAYBE_BIV) 1161 return iv_analyze_biv (mode, op, iv); 1162 1163 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 1169bool 1170iv_analyze (rtx_insn *insn, scalar_int_mode mode, rtx val, class rtx_iv *iv) 1171{ 1172 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 if (simple_reg_p (val)) 1179 { 1180 if (GET_CODE (val)((enum rtx_code) (val)->code) == SUBREG) 1181 reg = SUBREG_REG (val)(((val)->u.fld[0]).rt_rtx); 1182 else 1183 reg = val; 1184 1185 while (!df_find_use (insn, reg)) 1186 insn = NEXT_INSN (insn); 1187 } 1188 1189 return iv_analyze_op (insn, mode, val, iv); 1190} 1191 1192/* Analyzes definition of DEF in INSN and stores the result to IV. */ 1193 1194bool 1195iv_analyze_result (rtx_insn *insn, rtx def, class rtx_iv *iv) 1196{ 1197 df_ref adef; 1198 1199 adef = df_find_def (insn, def); 1200 if (!adef)

Assuming 'adef' is non-null

→

←

Taking false branch

→

1201 return false; 1202 1203 return iv_analyze_def (adef, iv);

←

Calling 'iv_analyze_def'

→

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 1212bool 1213biv_p (rtx_insn *insn, scalar_int_mode mode, rtx reg) 1214{ 1215 class rtx_iv iv; 1216 df_ref def, last_def; 1217 1218 if (!simple_reg_p (reg)) 1219 return false; 1220 1221 def = df_find_def (insn, reg); 1222 gcc_assert (def != NULL)((void)(!(def != __null) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 1222, __FUNCTION__), 0 : 0)); 1223 if (!latch_dominating_def (reg, &last_def)) 1224 return false; 1225 if (last_def != def) 1226 return false; 1227 1228 if (!iv_analyze_biv (mode, reg, &iv)) 1229 return false; 1230 1231 return iv.step != const0_rtx(const_int_rtx[64]); 1232} 1233 1234/* Calculates value of IV at ITERATION-th iteration. */ 1235 1236rtx 1237get_iv_value (class rtx_iv *iv, rtx iteration) 1238{ 1239 rtx val; 1240 1241 /* We would need to generate some if_then_else patterns, and so far 1242 it is not needed anywhere. */ 1243 gcc_assert (!iv->first_special)((void)(!(!iv->first_special) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 1243, __FUNCTION__), 0 : 0)); 1244 1245 if (iv->step != const0_rtx(const_int_rtx[64]) && iteration != const0_rtx(const_int_rtx[64])) 1246 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 val = iv->base; 1251 1252 if (iv->extend_mode == iv->mode) 1253 return val; 1254 1255 val = lowpart_subreg (iv->mode, val, iv->extend_mode); 1256 1257 if (iv->extend == IV_UNKNOWN_EXTEND) 1258 return val; 1259 1260 val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend), 1261 iv->extend_mode, val, iv->mode); 1262 val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta, 1263 simplify_gen_binary (MULT, iv->extend_mode, 1264 iv->mult, val)); 1265 1266 return val; 1267} 1268 1269/* Free the data for an induction variable analysis. */ 1270 1271void 1272iv_analysis_done (void) 1273{ 1274 if (!clean_slate) 1275 { 1276 clear_iv_info (); 1277 clean_slate = true; 1278 df_finish_pass (true); 1279 delete bivs; 1280 bivs = NULL__null; 1281 free (iv_ref_table); 1282 iv_ref_table = NULL__null; 1283 iv_ref_table_size = 0; 1284 } 1285} 1286 1287/* Computes inverse to X modulo (1 << MOD). */ 1288 1289static uint64_t 1290inverse (uint64_t x, int mod) 1291{ 1292 uint64_t mask = 1293 ((uint64_t) 1 << (mod - 1) << 1) - 1; 1294 uint64_t rslt = 1; 1295 int i; 1296 1297 for (i = 0; i < mod - 1; i++) 1298 { 1299 rslt = (rslt * x) & mask; 1300 x = (x * x) & mask; 1301 } 1302 1303 return rslt; 1304} 1305 1306/* Checks whether any register in X is in set ALT. */ 1307 1308static bool 1309altered_reg_used (const_rtx x, bitmap alt) 1310{ 1311 subrtx_iterator::array_type array; 1312 FOR_EACH_SUBRTX (iter, array, x, NONCONST)for (subrtx_iterator iter (array, x, rtx_nonconst_subrtx_bounds
); !iter.at_end (); iter.next ()) 1313 { 1314 const_rtx x = *iter; 1315 if (REG_P (x)(((enum rtx_code) (x)->code) == REG) && REGNO_REG_SET_P (alt, REGNO (x))bitmap_bit_p (alt, (rhs_regno(x)))) 1316 return true; 1317 } 1318 return false; 1319} 1320 1321/* Marks registers altered by EXPR in set ALT. */ 1322 1323static void 1324mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED__attribute__ ((__unused__)), void *alt) 1325{ 1326 if (GET_CODE (expr)((enum rtx_code) (expr)->code) == SUBREG) 1327 expr = SUBREG_REG (expr)(((expr)->u.fld[0]).rt_rtx); 1328 if (!REG_P (expr)(((enum rtx_code) (expr)->code) == REG)) 1329 return; 1330 1331 SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr))bitmap_set_bit ((bitmap) alt, (rhs_regno(expr))); 1332} 1333 1334/* Checks whether RHS is simple enough to process. */ 1335 1336static bool 1337simple_rhs_p (rtx rhs) 1338{ 1339 rtx op0, op1; 1340 1341 if (function_invariant_p (rhs) 1342 || (REG_P (rhs)(((enum rtx_code) (rhs)->code) == REG) && !HARD_REGISTER_P (rhs)((((rhs_regno(rhs))) < 76)))) 1343 return true; 1344 1345 switch (GET_CODE (rhs)((enum rtx_code) (rhs)->code)) 1346 { 1347 case PLUS: 1348 case MINUS: 1349 case AND: 1350 op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx); 1351 op1 = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx); 1352 /* Allow reg OP const and reg OP reg. */ 1353 if (!(REG_P (op0)(((enum rtx_code) (op0)->code) == REG) && !HARD_REGISTER_P (op0)((((rhs_regno(op0))) < 76))) 1354 && !function_invariant_p (op0)) 1355 return false; 1356 if (!(REG_P (op1)(((enum rtx_code) (op1)->code) == REG) && !HARD_REGISTER_P (op1)((((rhs_regno(op1))) < 76))) 1357 && !function_invariant_p (op1)) 1358 return false; 1359 1360 return true; 1361 1362 case ASHIFT: 1363 case ASHIFTRT: 1364 case LSHIFTRT: 1365 case MULT: 1366 op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx); 1367 op1 = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx); 1368 /* Allow reg OP const. */ 1369 if (!(REG_P (op0)(((enum rtx_code) (op0)->code) == REG) && !HARD_REGISTER_P (op0)((((rhs_regno(op0))) < 76)))) 1370 return false; 1371 if (!function_invariant_p (op1)) 1372 return false; 1373 1374 return true; 1375 1376 default: 1377 return false; 1378 } 1379} 1380 1381/* If any registers in *EXPR that have a single definition, try to replace 1382 them with the known-equivalent values. */ 1383 1384static void 1385replace_single_def_regs (rtx *expr) 1386{ 1387 subrtx_var_iterator::array_type array; 1388 repeat: 1389 FOR_EACH_SUBRTX_VAR (iter, array, *expr, NONCONST)for (subrtx_var_iterator iter (array, *expr, rtx_nonconst_subrtx_bounds
); !iter.at_end (); iter.next ()) 1390 { 1391 rtx x = *iter; 1392 if (REG_P (x)(((enum rtx_code) (x)->code) == REG)) 1393 if (rtx new_x = df_find_single_def_src (x)) 1394 { 1395 *expr = simplify_replace_rtx (*expr, x, new_x); 1396 goto repeat; 1397 } 1398 } 1399} 1400 1401/* A subroutine of simplify_using_initial_values, this function examines INSN 1402 to see if it contains a suitable set that we can use to make a replacement. 1403 If it is suitable, return true and set DEST and SRC to the lhs and rhs of 1404 the set; return false otherwise. */ 1405 1406static bool 1407suitable_set_for_replacement (rtx_insn *insn, rtx *dest, rtx *src) 1408{ 1409 rtx set = single_set (insn); 1410 rtx lhs = NULL_RTX(rtx) 0, rhs; 1411 1412 if (!set) 1413 return false; 1414 1415 lhs = SET_DEST (set)(((set)->u.fld[0]).rt_rtx); 1416 if (!REG_P (lhs)(((enum rtx_code) (lhs)->code) == REG)) 1417 return false; 1418 1419 rhs = find_reg_equal_equiv_note (insn); 1420 if (rhs) 1421 rhs = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx); 1422 else 1423 rhs = SET_SRC (set)(((set)->u.fld[1]).rt_rtx); 1424 1425 if (!simple_rhs_p (rhs)) 1426 return false; 1427 1428 *dest = lhs; 1429 *src = rhs; 1430 return true; 1431} 1432 1433/* Using the data returned by suitable_set_for_replacement, replace DEST 1434 with SRC in *EXPR and return the new expression. Also call 1435 replace_single_def_regs if the replacement changed something. */ 1436static void 1437replace_in_expr (rtx *expr, rtx dest, rtx src) 1438{ 1439 rtx old = *expr; 1440 *expr = simplify_replace_rtx (*expr, dest, src); 1441 if (old == *expr) 1442 return; 1443 replace_single_def_regs (expr); 1444} 1445 1446/* Checks whether A implies B. */ 1447 1448static bool 1449implies_p (rtx a, rtx b) 1450{ 1451 rtx op0, op1, opb0, opb1; 1452 machine_mode mode; 1453 1454 if (rtx_equal_p (a, b)) 1455 return true; 1456 1457 if (GET_CODE (a)((enum rtx_code) (a)->code) == EQ) 1458 { 1459 op0 = XEXP (a, 0)(((a)->u.fld[0]).rt_rtx); 1460 op1 = XEXP (a, 1)(((a)->u.fld[1]).rt_rtx); 1461 1462 if (REG_P (op0)(((enum rtx_code) (op0)->code) == REG) 1463 || (GET_CODE (op0)((enum rtx_code) (op0)->code) == SUBREG 1464 && REG_P (SUBREG_REG (op0))(((enum rtx_code) ((((op0)->u.fld[0]).rt_rtx))->code) ==
REG))) 1465 { 1466 rtx r = simplify_replace_rtx (b, op0, op1); 1467 if (r == const_true_rtx) 1468 return true; 1469 } 1470 1471 if (REG_P (op1)(((enum rtx_code) (op1)->code) == REG) 1472 || (GET_CODE (op1)((enum rtx_code) (op1)->code) == SUBREG 1473 && REG_P (SUBREG_REG (op1))(((enum rtx_code) ((((op1)->u.fld[0]).rt_rtx))->code) ==
REG))) 1474 { 1475 rtx r = simplify_replace_rtx (b, op1, op0); 1476 if (r == const_true_rtx) 1477 return true; 1478 } 1479 } 1480 1481 if (b == const_true_rtx) 1482 return true; 1483 1484 if ((GET_RTX_CLASS (GET_CODE (a))(rtx_class[(int) (((enum rtx_code) (a)->code))]) != RTX_COMM_COMPARE 1485 && GET_RTX_CLASS (GET_CODE (a))(rtx_class[(int) (((enum rtx_code) (a)->code))]) != RTX_COMPARE) 1486 || (GET_RTX_CLASS (GET_CODE (b))(rtx_class[(int) (((enum rtx_code) (b)->code))]) != RTX_COMM_COMPARE 1487 && GET_RTX_CLASS (GET_CODE (b))(rtx_class[(int) (((enum rtx_code) (b)->code))]) != RTX_COMPARE)) 1488 return false; 1489 1490 op0 = XEXP (a, 0)(((a)->u.fld[0]).rt_rtx); 1491 op1 = XEXP (a, 1)(((a)->u.fld[1]).rt_rtx); 1492 opb0 = XEXP (b, 0)(((b)->u.fld[0]).rt_rtx); 1493 opb1 = XEXP (b, 1)(((b)->u.fld[1]).rt_rtx); 1494 1495 mode = GET_MODE (op0)((machine_mode) (op0)->mode); 1496 if (mode != GET_MODE (opb0)((machine_mode) (opb0)->mode)) 1497 mode = VOIDmode((void) 0, E_VOIDmode); 1498 else if (mode == VOIDmode((void) 0, E_VOIDmode)) 1499 { 1500 mode = GET_MODE (op1)((machine_mode) (op1)->mode); 1501 if (mode != GET_MODE (opb1)((machine_mode) (opb1)->mode)) 1502 mode = VOIDmode((void) 0, E_VOIDmode); 1503 } 1504 1505 /* A code) == GT || GET_CODE (a)((enum rtx_code) (a)->code) == LT) 1507 && (GET_CODE (b)((enum rtx_code) (b)->code) == GE || GET_CODE (b)((enum rtx_code) (b)->code) == LE)) 1508 { 1509 1510 if (GET_CODE (a)((enum rtx_code) (a)->code) == GT) 1511 std::swap (op0, op1); 1512 1513 if (GET_CODE (b)((enum rtx_code) (b)->code) == GE) 1514 std::swap (opb0, opb1); 1515 1516 if (SCALAR_INT_MODE_P (mode)(((enum mode_class) mode_class[mode]) == MODE_INT || ((enum mode_class
) mode_class[mode]) == MODE_PARTIAL_INT) 1517 && rtx_equal_p (op1, opb1) 1518 && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx(const_int_rtx[64 +1])) 1519 return true; 1520 return false; 1521 } 1522 1523 /* A B imply A != B. TODO: Likewise 1524 A + n code) == NE 1526 && (GET_CODE (a)((enum rtx_code) (a)->code) == GT || GET_CODE (a)((enum rtx_code) (a)->code) == GTU 1527 || GET_CODE (a)((enum rtx_code) (a)->code) == LT || GET_CODE (a)((enum rtx_code) (a)->code) == LTU)) 1528 { 1529 if (rtx_equal_p (op0, opb0) 1530 && rtx_equal_p (op1, opb1)) 1531 return true; 1532 } 1533 1534 /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */ 1535 if (GET_CODE (a)((enum rtx_code) (a)->code) == NE 1536 && op1 == const0_rtx(const_int_rtx[64])) 1537 { 1538 if ((GET_CODE (b)((enum rtx_code) (b)->code) == GTU 1539 && opb1 == const0_rtx(const_int_rtx[64])) 1540 || (GET_CODE (b)((enum rtx_code) (b)->code) == GEU 1541 && opb1 == const1_rtx(const_int_rtx[64 +1]))) 1542 return rtx_equal_p (op0, opb0); 1543 } 1544 1545 /* A != N is equivalent to A - (N + 1) code) == NE 1547 && CONST_INT_P (op1)(((enum rtx_code) (op1)->code) == CONST_INT) 1548 && GET_CODE (b)((enum rtx_code) (b)->code) == LTU 1549 && opb1 == constm1_rtx(const_int_rtx[64 -1]) 1550 && GET_CODE (opb0)((enum rtx_code) (opb0)->code) == PLUS 1551 && CONST_INT_P (XEXP (opb0, 1))(((enum rtx_code) ((((opb0)->u.fld[1]).rt_rtx))->code) ==
CONST_INT) 1552 /* Avoid overflows. */ 1553 && ((unsigned HOST_WIDE_INTlong) INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]) 1554 != ((unsigned HOST_WIDE_INTlong)1 1555 << (HOST_BITS_PER_WIDE_INT64 - 1)) - 1) 1556 && INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]) + 1 == -INTVAL (op1)((op1)->u.hwint[0])) 1557 return rtx_equal_p (op0, XEXP (opb0, 0)(((opb0)->u.fld[0]).rt_rtx)); 1558 1559 /* Likewise, A != N implies A - N > 0. */ 1560 if (GET_CODE (a)((enum rtx_code) (a)->code) == NE 1561 && CONST_INT_P (op1)(((enum rtx_code) (op1)->code) == CONST_INT)) 1562 { 1563 if (GET_CODE (b)((enum rtx_code) (b)->code) == GTU 1564 && GET_CODE (opb0)((enum rtx_code) (opb0)->code) == PLUS 1565 && opb1 == const0_rtx(const_int_rtx[64]) 1566 && CONST_INT_P (XEXP (opb0, 1))(((enum rtx_code) ((((opb0)->u.fld[1]).rt_rtx))->code) ==
CONST_INT) 1567 /* Avoid overflows. */ 1568 && ((unsigned HOST_WIDE_INTlong) INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]) 1569 != (HOST_WIDE_INT_1U1UL << (HOST_BITS_PER_WIDE_INT64 - 1))) 1570 && rtx_equal_p (XEXP (opb0, 0)(((opb0)->u.fld[0]).rt_rtx), op0)) 1571 return INTVAL (op1)((op1)->u.hwint[0]) == -INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]); 1572 if (GET_CODE (b)((enum rtx_code) (b)->code) == GEU 1573 && GET_CODE (opb0)((enum rtx_code) (opb0)->code) == PLUS 1574 && opb1 == const1_rtx(const_int_rtx[64 +1]) 1575 && CONST_INT_P (XEXP (opb0, 1))(((enum rtx_code) ((((opb0)->u.fld[1]).rt_rtx))->code) ==
CONST_INT) 1576 /* Avoid overflows. */ 1577 && ((unsigned HOST_WIDE_INTlong) INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]) 1578 != (HOST_WIDE_INT_1U1UL << (HOST_BITS_PER_WIDE_INT64 - 1))) 1579 && rtx_equal_p (XEXP (opb0, 0)(((opb0)->u.fld[0]).rt_rtx), op0)) 1580 return INTVAL (op1)((op1)->u.hwint[0]) == -INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]); 1581 } 1582 1583 /* A >s X, where X is positive, implies A code) == GT || GET_CODE (a)((enum rtx_code) (a)->code) == GE) 1585 && CONST_INT_P (op1)(((enum rtx_code) (op1)->code) == CONST_INT) 1586 && ((GET_CODE (a)((enum rtx_code) (a)->code) == GT && op1 == constm1_rtx(const_int_rtx[64 -1])) 1587 || INTVAL (op1)((op1)->u.hwint[0]) >= 0) 1588 && GET_CODE (b)((enum rtx_code) (b)->code) == LTU 1589 && CONST_INT_P (opb1)(((enum rtx_code) (opb1)->code) == CONST_INT) 1590 && rtx_equal_p (op0, opb0)) 1591 return INTVAL (opb1)((opb1)->u.hwint[0]) < 0; 1592 1593 return false; 1594} 1595 1596/* Canonicalizes COND so that 1597 1598 (1) Ensure that operands are ordered according to 1599 swap_commutative_operands_p. 1600 (2) (LE x const) will be replaced with (LT x <const+1>) and similarly 1601 for GE, GEU, and LEU. */ 1602 1603rtx 1604canon_condition (rtx cond) 1605{ 1606 rtx op0, op1; 1607 enum rtx_code code; 1608 machine_mode mode; 1609 1610 code = GET_CODE (cond)((enum rtx_code) (cond)->code); 1611 op0 = XEXP (cond, 0)(((cond)->u.fld[0]).rt_rtx); 1612 op1 = XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx); 1613 1614 if (swap_commutative_operands_p (op0, op1)) 1615 { 1616 code = swap_condition (code); 1617 std::swap (op0, op1); 1618 } 1619 1620 mode = GET_MODE (op0)((machine_mode) (op0)->mode); 1621 if (mode == VOIDmode((void) 0, E_VOIDmode)) 1622 mode = GET_MODE (op1)((machine_mode) (op1)->mode); 1623 gcc_assert (mode != VOIDmode)((void)(!(mode != ((void) 0, E_VOIDmode)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 1623, __FUNCTION__), 0 : 0)); 1624 1625 if (CONST_SCALAR_INT_P (op1)((((enum rtx_code) (op1)->code) == CONST_INT) || (((enum rtx_code
) (op1)->code) == CONST_WIDE_INT)) && GET_MODE_CLASS (mode)((enum mode_class) mode_class[mode]) != MODE_CC) 1626 { 1627 rtx_mode_t const_val (op1, mode); 1628 1629 switch (code) 1630 { 1631 case LE: 1632 if (wi::ne_p (const_val, wi::max_value (mode, SIGNED))) 1633 { 1634 code = LT; 1635 op1 = immed_wide_int_const (wi::add (const_val, 1), mode); 1636 } 1637 break; 1638 1639 case GE: 1640 if (wi::ne_p (const_val, wi::min_value (mode, SIGNED))) 1641 { 1642 code = GT; 1643 op1 = immed_wide_int_const (wi::sub (const_val, 1), mode); 1644 } 1645 break; 1646 1647 case LEU: 1648 if (wi::ne_p (const_val, -1)) 1649 { 1650 code = LTU; 1651 op1 = immed_wide_int_const (wi::add (const_val, 1), mode); 1652 } 1653 break; 1654 1655 case GEU: 1656 if (wi::ne_p (const_val, 0)) 1657 { 1658 code = GTU; 1659 op1 = immed_wide_int_const (wi::sub (const_val, 1), mode); 1660 } 1661 break; 1662 1663 default: 1664 break; 1665 } 1666 } 1667 1668 if (op0 != XEXP (cond, 0)(((cond)->u.fld[0]).rt_rtx) 1669 || op1 != XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx) 1670 || code != GET_CODE (cond)((enum rtx_code) (cond)->code) 1671 || GET_MODE (cond)((machine_mode) (cond)->mode) != SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode))) 1672 cond = gen_rtx_fmt_ee (code, SImode, op0, op1)gen_rtx_fmt_ee_stat ((code), ((scalar_int_mode ((scalar_int_mode
::from_int) E_SImode))), (op0), (op1) ); 1673 1674 return cond; 1675} 1676 1677/* Reverses CONDition; returns NULL if we cannot. */ 1678 1679static rtx 1680reversed_condition (rtx cond) 1681{ 1682 enum rtx_code reversed; 1683 reversed = reversed_comparison_code (cond, NULL__null); 1684 if (reversed == UNKNOWN) 1685 return NULL_RTX(rtx) 0; 1686 else 1687 return gen_rtx_fmt_ee (reversed,gen_rtx_fmt_ee_stat ((reversed), (((machine_mode) (cond)->
mode)), ((((cond)->u.fld[0]).rt_rtx)), ((((cond)->u.fld
[1]).rt_rtx)) ) 1688 GET_MODE (cond), XEXP (cond, 0),gen_rtx_fmt_ee_stat ((reversed), (((machine_mode) (cond)->
mode)), ((((cond)->u.fld[0]).rt_rtx)), ((((cond)->u.fld
[1]).rt_rtx)) ) 1689 XEXP (cond, 1))gen_rtx_fmt_ee_stat ((reversed), (((machine_mode) (cond)->
mode)), ((((cond)->u.fld[0]).rt_rtx)), ((((cond)->u.fld
[1]).rt_rtx)) ); 1690} 1691 1692/* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the 1693 set of altered regs. */ 1694 1695void 1696simplify_using_condition (rtx cond, rtx *expr, regset altered) 1697{ 1698 rtx rev, reve, exp = *expr; 1699 1700 /* If some register gets altered later, we do not really speak about its 1701 value at the time of comparison. */ 1702 if (altered && altered_reg_used (cond, altered)) 1703 return; 1704 1705 if (GET_CODE (cond)((enum rtx_code) (cond)->code) == EQ 1706 && REG_P (XEXP (cond, 0))(((enum rtx_code) ((((cond)->u.fld[0]).rt_rtx))->code) ==
REG) && CONSTANT_P (XEXP (cond, 1))((rtx_class[(int) (((enum rtx_code) ((((cond)->u.fld[1]).rt_rtx
))->code))]) == RTX_CONST_OBJ)) 1707 { 1708 *expr = simplify_replace_rtx (*expr, XEXP (cond, 0)(((cond)->u.fld[0]).rt_rtx), XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx)); 1709 return; 1710 } 1711 1712 if (!COMPARISON_P (exp)(((rtx_class[(int) (((enum rtx_code) (exp)->code))]) &
(~1)) == (RTX_COMPARE & (~1)))) 1713 return; 1714 1715 rev = reversed_condition (cond); 1716 reve = reversed_condition (exp); 1717 1718 cond = canon_condition (cond); 1719 exp = canon_condition (exp); 1720 if (rev) 1721 rev = canon_condition (rev); 1722 if (reve) 1723 reve = canon_condition (reve); 1724 1725 if (rtx_equal_p (exp, cond)) 1726 { 1727 *expr = const_true_rtx; 1728 return; 1729 } 1730 1731 if (rev && rtx_equal_p (exp, rev)) 1732 { 1733 *expr = const0_rtx(const_int_rtx[64]); 1734 return; 1735 } 1736 1737 if (implies_p (cond, exp)) 1738 { 1739 *expr = const_true_rtx; 1740 return; 1741 } 1742 1743 if (reve && implies_p (cond, reve)) 1744 { 1745 *expr = const0_rtx(const_int_rtx[64]); 1746 return; 1747 } 1748 1749 /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must 1750 be false. */ 1751 if (rev && implies_p (exp, rev)) 1752 { 1753 *expr = const0_rtx(const_int_rtx[64]); 1754 return; 1755 } 1756 1757 /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */ 1758 if (rev && reve && implies_p (reve, rev)) 1759 { 1760 *expr = const_true_rtx; 1761 return; 1762 } 1763 1764 /* We would like to have some other tests here. TODO. */ 1765 1766 return; 1767} 1768 1769/* Use relationship between A and *B to eventually eliminate *B. 1770 OP is the operation we consider. */ 1771 1772static void 1773eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b) 1774{ 1775 switch (op) 1776 { 1777 case AND: 1778 /* If A implies *B, we may replace *B by true. */ 1779 if (implies_p (a, *b)) 1780 *b = const_true_rtx; 1781 break; 1782 1783 case IOR: 1784 /* If *B implies A, we may replace *B by false. */ 1785 if (implies_p (*b, a)) 1786 *b = const0_rtx(const_int_rtx[64]); 1787 break; 1788 1789 default: 1790 gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 1790, __FUNCTION__)); 1791 } 1792} 1793 1794/* Eliminates the conditions in TAIL that are implied by HEAD. OP is the 1795 operation we consider. */ 1796 1797static void 1798eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail) 1799{ 1800 rtx elt; 1801 1802 for (elt = tail; elt; elt = XEXP (elt, 1)(((elt)->u.fld[1]).rt_rtx)) 1803 eliminate_implied_condition (op, *head, &XEXP (elt, 0)(((elt)->u.fld[0]).rt_rtx)); 1804 for (elt = tail; elt; elt = XEXP (elt, 1)(((elt)->u.fld[1]).rt_rtx)) 1805 eliminate_implied_condition (op, XEXP (elt, 0)(((elt)->u.fld[0]).rt_rtx), head); 1806} 1807 1808/* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR 1809 is a list, its elements are assumed to be combined using OP. */ 1810 1811static void 1812simplify_using_initial_values (class loop *loop, enum rtx_code op, rtx *expr) 1813{ 1814 bool expression_valid; 1815 rtx head, tail, last_valid_expr; 1816 rtx_expr_list *cond_list; 1817 rtx_insn *insn; 1818 rtx neutral, aggr; 1819 regset altered, this_altered; 1820 edge e; 1821 1822 if (!*expr) 1823 return; 1824 1825 if (CONSTANT_P (*expr)((rtx_class[(int) (((enum rtx_code) (*expr)->code))]) == RTX_CONST_OBJ
)) 1826 return; 1827 1828 if (GET_CODE (*expr)((enum rtx_code) (*expr)->code) == EXPR_LIST) 1829 { 1830 head = XEXP (*expr, 0)(((*expr)->u.fld[0]).rt_rtx); 1831 tail = XEXP (*expr, 1)(((*expr)->u.fld[1]).rt_rtx); 1832 1833 eliminate_implied_conditions (op, &head, tail); 1834 1835 switch (op) 1836 { 1837 case AND: 1838 neutral = const_true_rtx; 1839 aggr = const0_rtx(const_int_rtx[64]); 1840 break; 1841 1842 case IOR: 1843 neutral = const0_rtx(const_int_rtx[64]); 1844 aggr = const_true_rtx; 1845 break; 1846 1847 default: 1848 gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 1848, __FUNCTION__)); 1849 } 1850 1851 simplify_using_initial_values (loop, UNKNOWN, &head); 1852 if (head == aggr) 1853 { 1854 XEXP (*expr, 0)(((*expr)->u.fld[0]).rt_rtx) = aggr; 1855 XEXP (*expr, 1)(((*expr)->u.fld[1]).rt_rtx) = NULL_RTX(rtx) 0; 1856 return; 1857 } 1858 else if (head == neutral) 1859 { 1860 *expr = tail; 1861 simplify_using_initial_values (loop, op, expr); 1862 return; 1863 } 1864 simplify_using_initial_values (loop, op, &tail); 1865 1866 if (tail && XEXP (tail, 0)(((tail)->u.fld[0]).rt_rtx) == aggr) 1867 { 1868 *expr = tail; 1869 return; 1870 } 1871 1872 XEXP (*expr, 0)(((*expr)->u.fld[0]).rt_rtx) = head; 1873 XEXP (*expr, 1)(((*expr)->u.fld[1]).rt_rtx) = tail; 1874 return; 1875 } 1876 1877 gcc_assert (op == UNKNOWN)((void)(!(op == UNKNOWN) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 1877, __FUNCTION__), 0 : 0)); 1878 1879 replace_single_def_regs (expr); 1880 if (CONSTANT_P (*expr)((rtx_class[(int) (((enum rtx_code) (*expr)->code))]) == RTX_CONST_OBJ
)) 1881 return; 1882 1883 e = loop_preheader_edge (loop); 1884 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)) 1885 return; 1886 1887 altered = ALLOC_REG_SET (&reg_obstack)bitmap_alloc (&reg_obstack); 1888 this_altered = ALLOC_REG_SET (&reg_obstack)bitmap_alloc (&reg_obstack); 1889 1890 expression_valid = true; 1891 last_valid_expr = *expr; 1892 cond_list = NULL__null; 1893 while (1) 1894 { 1895 insn = BB_END (e->src)(e->src)->il.x.rtl->end_; 1896 if (any_condjump_p (insn) && onlyjump_p (insn)) 1897 { 1898 rtx cond = get_condition (BB_END (e->src)(e->src)->il.x.rtl->end_, NULL__null, false, true); 1899 1900 if (cond && (e->flags & EDGE_FALLTHRU)) 1901 cond = reversed_condition (cond); 1902 if (cond) 1903 { 1904 rtx old = *expr; 1905 simplify_using_condition (cond, expr, altered); 1906 if (old != *expr) 1907 { 1908 rtx note; 1909 if (CONSTANT_P (*expr)((rtx_class[(int) (((enum rtx_code) (*expr)->code))]) == RTX_CONST_OBJ
)) 1910 goto out; 1911 for (note = cond_list; note; note = XEXP (note, 1)(((note)->u.fld[1]).rt_rtx)) 1912 { 1913 simplify_using_condition (XEXP (note, 0)(((note)->u.fld[0]).rt_rtx), expr, altered); 1914 if (CONSTANT_P (*expr)((rtx_class[(int) (((enum rtx_code) (*expr)->code))]) == RTX_CONST_OBJ
)) 1915 goto out; 1916 } 1917 } 1918 cond_list = alloc_EXPR_LIST (0, cond, cond_list); 1919 } 1920 } 1921 1922 FOR_BB_INSNS_REVERSE (e->src, insn)for ((insn) = (e->src)->il.x.rtl->end_; (insn) &&
(insn) != PREV_INSN ((e->src)->il.x.head_); (insn) = PREV_INSN
(insn)) 1923 { 1924 rtx src, dest; 1925 rtx old = *expr; 1926 1927 if (!INSN_P (insn)(((((enum rtx_code) (insn)->code) == INSN) || (((enum rtx_code
) (insn)->code) == JUMP_INSN) || (((enum rtx_code) (insn)->
code) == CALL_INSN)) || (((enum rtx_code) (insn)->code) ==
DEBUG_INSN))) 1928 continue; 1929 1930 CLEAR_REG_SET (this_altered)bitmap_clear (this_altered); 1931 note_stores (insn, mark_altered, this_altered); 1932 if (CALL_P (insn)(((enum rtx_code) (insn)->code) == CALL_INSN)) 1933 { 1934 /* Kill all registers that might be clobbered by the call. 1935 We don't track modes of hard registers, so we need to be 1936 conservative and assume that partial kills are full kills. */ 1937 function_abi callee_abi = insn_callee_abi (insn); 1938 IOR_REG_SET_HRS (this_altered,bitmap_ior_into (this_altered, bitmap_view<HARD_REG_SET>
(callee_abi.full_and_partial_reg_clobbers ())) 1939 callee_abi.full_and_partial_reg_clobbers ())bitmap_ior_into (this_altered, bitmap_view<HARD_REG_SET>
(callee_abi.full_and_partial_reg_clobbers ())); 1940 } 1941 1942 if (suitable_set_for_replacement (insn, &dest, &src)) 1943 { 1944 rtx_expr_list **pnote, **pnote_next; 1945 1946 replace_in_expr (expr, dest, src); 1947 if (CONSTANT_P (*expr)((rtx_class[(int) (((enum rtx_code) (*expr)->code))]) == RTX_CONST_OBJ
)) 1948 goto out; 1949 1950 for (pnote = &cond_list; *pnote; pnote = pnote_next) 1951 { 1952 rtx_expr_list *note = *pnote; 1953 rtx old_cond = XEXP (note, 0)(((note)->u.fld[0]).rt_rtx); 1954 1955 pnote_next = (rtx_expr_list **)&XEXP (note, 1)(((note)->u.fld[1]).rt_rtx); 1956 replace_in_expr (&XEXP (note, 0)(((note)->u.fld[0]).rt_rtx), dest, src); 1957 1958 /* We can no longer use a condition that has been simplified 1959 to a constant, and simplify_using_condition will abort if 1960 we try. */ 1961 if (CONSTANT_P (XEXP (note, 0))((rtx_class[(int) (((enum rtx_code) ((((note)->u.fld[0]).rt_rtx
))->code))]) == RTX_CONST_OBJ)) 1962 { 1963 *pnote = *pnote_next; 1964 pnote_next = pnote; 1965 free_EXPR_LIST_node (note); 1966 } 1967 /* Retry simplifications with this condition if either the 1968 expression or the condition changed. */ 1969 else if (old_cond != XEXP (note, 0)(((note)->u.fld[0]).rt_rtx) || old != *expr) 1970 simplify_using_condition (XEXP (note, 0)(((note)->u.fld[0]).rt_rtx), expr, altered); 1971 } 1972 } 1973 else 1974 { 1975 rtx_expr_list **pnote, **pnote_next; 1976 1977 /* If we did not use this insn to make a replacement, any overlap 1978 between stores in this insn and our expression will cause the 1979 expression to become invalid. */ 1980 if (altered_reg_used (*expr, this_altered)) 1981 goto out; 1982 1983 /* Likewise for the conditions. */ 1984 for (pnote = &cond_list; *pnote; pnote = pnote_next) 1985 { 1986 rtx_expr_list *note = *pnote; 1987 rtx old_cond = XEXP (note, 0)(((note)->u.fld[0]).rt_rtx); 1988 1989 pnote_next = (rtx_expr_list **)&XEXP (note, 1)(((note)->u.fld[1]).rt_rtx); 1990 if (altered_reg_used (old_cond, this_altered)) 1991 { 1992 *pnote = *pnote_next; 1993 pnote_next = pnote; 1994 free_EXPR_LIST_node (note); 1995 } 1996 } 1997 } 1998 1999 if (CONSTANT_P (*expr)((rtx_class[(int) (((enum rtx_code) (*expr)->code))]) == RTX_CONST_OBJ
)) 2000 goto out; 2001 2002 IOR_REG_SET (altered, this_altered)bitmap_ior_into (altered, this_altered); 2003 2004 /* If the expression now contains regs that have been altered, we 2005 can't return it to the caller. However, it is still valid for 2006 further simplification, so keep searching to see if we can 2007 eventually turn it into a constant. */ 2008 if (altered_reg_used (*expr, altered)) 2009 expression_valid = false; 2010 if (expression_valid) 2011 last_valid_expr = *expr; 2012 } 2013 2014 if (!single_pred_p (e->src) 2015 || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)) 2016 break; 2017 e = single_pred_edge (e->src); 2018 } 2019 2020 out: 2021 free_EXPR_LIST_list (&cond_list); 2022 if (!CONSTANT_P (*expr)((rtx_class[(int) (((enum rtx_code) (*expr)->code))]) == RTX_CONST_OBJ
)) 2023 *expr = last_valid_expr; 2024 FREE_REG_SET (altered)((void) (bitmap_obstack_free ((bitmap) altered), (altered) = (
bitmap) __null)); 2025 FREE_REG_SET (this_altered)((void) (bitmap_obstack_free ((bitmap) this_altered), (this_altered
) = (bitmap) __null)); 2026} 2027 2028/* Transforms invariant IV into MODE. Adds assumptions based on the fact 2029 that IV occurs as left operands of comparison COND and its signedness 2030 is SIGNED_P to DESC. */ 2031 2032static void 2033shorten_into_mode (class rtx_iv *iv, scalar_int_mode mode, 2034 enum rtx_code cond, bool signed_p, class niter_desc *desc) 2035{ 2036 rtx mmin, mmax, cond_over, cond_under; 2037 2038 get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax); 2039 cond_under = simplify_gen_relational (LT, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), iv->extend_mode, 2040 iv->base, mmin); 2041 cond_over = simplify_gen_relational (GT, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), iv->extend_mode, 2042 iv->base, mmax); 2043 2044 switch (cond) 2045 { 2046 case LE: 2047 case LT: 2048 case LEU: 2049 case LTU: 2050 if (cond_under != const0_rtx(const_int_rtx[64])) 2051 desc->infinite = 2052 alloc_EXPR_LIST (0, cond_under, desc->infinite); 2053 if (cond_over != const0_rtx(const_int_rtx[64])) 2054 desc->noloop_assumptions = 2055 alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions); 2056 break; 2057 2058 case GE: 2059 case GT: 2060 case GEU: 2061 case GTU: 2062 if (cond_over != const0_rtx(const_int_rtx[64])) 2063 desc->infinite = 2064 alloc_EXPR_LIST (0, cond_over, desc->infinite); 2065 if (cond_under != const0_rtx(const_int_rtx[64])) 2066 desc->noloop_assumptions = 2067 alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions); 2068 break; 2069 2070 case NE: 2071 if (cond_over != const0_rtx(const_int_rtx[64])) 2072 desc->infinite = 2073 alloc_EXPR_LIST (0, cond_over, desc->infinite); 2074 if (cond_under != const0_rtx(const_int_rtx[64])) 2075 desc->infinite = 2076 alloc_EXPR_LIST (0, cond_under, desc->infinite); 2077 break; 2078 2079 default: 2080 gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 2080, __FUNCTION__)); 2081 } 2082 2083 iv->mode = mode; 2084 iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND; 2085} 2086 2087/* Transforms IV0 and IV1 compared by COND so that they are both compared as 2088 subregs of the same mode if possible (sometimes it is necessary to add 2089 some assumptions to DESC). */ 2090 2091static bool 2092canonicalize_iv_subregs (class rtx_iv *iv0, class rtx_iv *iv1, 2093 enum rtx_code cond, class niter_desc *desc) 2094{ 2095 scalar_int_mode comp_mode; 2096 bool signed_p; 2097 2098 /* If the ivs behave specially in the first iteration, or are 2099 added/multiplied after extending, we ignore them. */ 2100 if (iv0->first_special || iv0->mult != const1_rtx(const_int_rtx[64 +1]) || iv0->delta != const0_rtx(const_int_rtx[64])) 2101 return false; 2102 if (iv1->first_special || iv1->mult != const1_rtx(const_int_rtx[64 +1]) || iv1->delta != const0_rtx(const_int_rtx[64])) 2103 return false; 2104 2105 /* If there is some extend, it must match signedness of the comparison. */ 2106 switch (cond) 2107 { 2108 case LE: 2109 case LT: 2110 if (iv0->extend == IV_ZERO_EXTEND 2111 || iv1->extend == IV_ZERO_EXTEND) 2112 return false; 2113 signed_p = true; 2114 break; 2115 2116 case LEU: 2117 case LTU: 2118 if (iv0->extend == IV_SIGN_EXTEND 2119 || iv1->extend == IV_SIGN_EXTEND) 2120 return false; 2121 signed_p = false; 2122 break; 2123 2124 case NE: 2125 if (iv0->extend != IV_UNKNOWN_EXTEND 2126 && iv1->extend != IV_UNKNOWN_EXTEND 2127 && iv0->extend != iv1->extend) 2128 return false; 2129 2130 signed_p = false; 2131 if (iv0->extend != IV_UNKNOWN_EXTEND) 2132 signed_p = iv0->extend == IV_SIGN_EXTEND; 2133 if (iv1->extend != IV_UNKNOWN_EXTEND) 2134 signed_p = iv1->extend == IV_SIGN_EXTEND; 2135 break; 2136 2137 default: 2138 gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 2138, __FUNCTION__)); 2139 } 2140 2141 /* Values of both variables should be computed in the same mode. These 2142 might indeed be different, if we have comparison like 2143 2144 (compare (subreg:SI (iv0)) (subreg:SI (iv1))) 2145 2146 and iv0 and iv1 are both ivs iterating in SI mode, but calculated 2147 in different modes. This does not seem impossible to handle, but 2148 it hardly ever occurs in practice. 2149 2150 The only exception is the case when one of operands is invariant. 2151 For example pentium 3 generates comparisons like 2152 (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we 2153 definitely do not want this prevent the optimization. */ 2154 comp_mode = iv0->extend_mode; 2155 if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode)) 2156 comp_mode = iv1->extend_mode; 2157 2158 if (iv0->extend_mode != comp_mode) 2159 { 2160 if (iv0->mode != iv0->extend_mode 2161 || iv0->step != const0_rtx(const_int_rtx[64])) 2162 return false; 2163 2164 iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND, 2165 comp_mode, iv0->base, iv0->mode); 2166 iv0->extend_mode = comp_mode; 2167 } 2168 2169 if (iv1->extend_mode != comp_mode) 2170 { 2171 if (iv1->mode != iv1->extend_mode 2172 || iv1->step != const0_rtx(const_int_rtx[64])) 2173 return false; 2174 2175 iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND, 2176 comp_mode, iv1->base, iv1->mode); 2177 iv1->extend_mode = comp_mode; 2178 } 2179 2180 /* Check that both ivs belong to a range of a single mode. If one of the 2181 operands is an invariant, we may need to shorten it into the common 2182 mode. */ 2183 if (iv0->mode == iv0->extend_mode 2184 && iv0->step == const0_rtx(const_int_rtx[64]) 2185 && iv0->mode != iv1->mode) 2186 shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc); 2187 2188 if (iv1->mode == iv1->extend_mode 2189 && iv1->step == const0_rtx(const_int_rtx[64]) 2190 && iv0->mode != iv1->mode) 2191 shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc); 2192 2193 if (iv0->mode != iv1->mode) 2194 return false; 2195 2196 desc->mode = iv0->mode; 2197 desc->signed_p = signed_p; 2198 2199 return true; 2200} 2201 2202/* Tries to estimate the maximum number of iterations in LOOP, and return the 2203 result. This function is called from iv_number_of_iterations with 2204 a number of fields in DESC already filled in. OLD_NITER is the original 2205 expression for the number of iterations, before we tried to simplify it. */ 2206 2207static uint64_t 2208determine_max_iter (class loop *loop, class niter_desc *desc, rtx old_niter) 2209{ 2210 rtx niter = desc->niter_expr; 2211 rtx mmin, mmax, cmp; 2212 uint64_t nmax, inc; 2213 uint64_t andmax = 0; 2214 2215 /* We used to look for constant operand 0 of AND, 2216 but canonicalization should always make this impossible. */ 2217 gcc_checking_assert (GET_CODE (niter) != AND((void)(!(((enum rtx_code) (niter)->code) != AND || !(((enum
rtx_code) ((((niter)->u.fld[0]).rt_rtx))->code) == CONST_INT
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 2218, __FUNCTION__), 0 : 0)) 2218 || !CONST_INT_P (XEXP (niter, 0)))((void)(!(((enum rtx_code) (niter)->code) != AND || !(((enum
rtx_code) ((((niter)->u.fld[0]).rt_rtx))->code) == CONST_INT
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 2218, __FUNCTION__), 0 : 0)); 2219 2220 if (GET_CODE (niter)((enum rtx_code) (niter)->code) == AND 2221 && CONST_INT_P (XEXP (niter, 1))(((enum rtx_code) ((((niter)->u.fld[1]).rt_rtx))->code)
== CONST_INT)) 2222 { 2223 andmax = UINTVAL (XEXP (niter, 1))((unsigned long) (((((niter)->u.fld[1]).rt_rtx))->u.hwint
[0])); 2224 niter = XEXP (niter, 0)(((niter)->u.fld[0]).rt_rtx); 2225 } 2226 2227 get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax); 2228 nmax = UINTVAL (mmax)((unsigned long) ((mmax)->u.hwint[0])) - UINTVAL (mmin)((unsigned long) ((mmin)->u.hwint[0])); 2229 2230 if (GET_CODE (niter)((enum rtx_code) (niter)->code) == UDIV) 2231 { 2232 if (!CONST_INT_P (XEXP (niter, 1))(((enum rtx_code) ((((niter)->u.fld[1]).rt_rtx))->code)
== CONST_INT)) 2233 return nmax; 2234 inc = INTVAL (XEXP (niter, 1))(((((niter)->u.fld[1]).rt_rtx))->u.hwint[0]); 2235 niter = XEXP (niter, 0)(((niter)->u.fld[0]).rt_rtx); 2236 } 2237 else 2238 inc = 1; 2239 2240 /* We could use a binary search here, but for now improving the upper 2241 bound by just one eliminates one important corner case. */ 2242 cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode((void) 0, E_VOIDmode), 2243 desc->mode, old_niter, mmax); 2244 simplify_using_initial_values (loop, UNKNOWN, &cmp); 2245 if (cmp == const_true_rtx) 2246 { 2247 nmax--; 2248 2249 if (dump_file) 2250 fprintf (dump_file, ";; improved upper bound by one.\n"); 2251 } 2252 nmax /= inc; 2253 if (andmax) 2254 nmax = MIN (nmax, andmax)((nmax) < (andmax) ? (nmax) : (andmax)); 2255 if (dump_file) 2256 fprintf (dump_file, ";; Determined upper bound %" PRId64"l" "d"".\n", 2257 nmax); 2258 return nmax; 2259} 2260 2261/* Computes number of iterations of the CONDITION in INSN in LOOP and stores 2262 the result into DESC. Very similar to determine_number_of_iterations 2263 (basically its rtl version), complicated by things like subregs. */ 2264 2265static void 2266iv_number_of_iterations (class loop *loop, rtx_insn *insn, rtx condition, 2267 class niter_desc *desc) 2268{ 2269 rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1; 2270 class rtx_iv iv0, iv1; 2271 rtx assumption, may_not_xform; 2272 enum rtx_code cond; 2273 machine_mode nonvoid_mode; 2274 scalar_int_mode comp_mode; 2275 rtx mmin, mmax, mode_mmin, mode_mmax; 2276 uint64_t s, size, d, inv, max, up, down; 2277 int64_t inc, step_val; 2278 int was_sharp = false; 2279 rtx old_niter; 2280 bool step_is_pow2; 2281 2282 /* The meaning of these assumptions is this: 2283 if !assumptions 2284 then the rest of information does not have to be valid 2285 if noloop_assumptions then the loop does not roll 2286 if infinite then this exit is never used */ 2287 2288 desc->assumptions = NULL_RTX(rtx) 0; 2289 desc->noloop_assumptions = NULL_RTX(rtx) 0; 2290 desc->infinite = NULL_RTX(rtx) 0; 2291 desc->simple_p = true; 2292 2293 desc->const_iter = false; 2294 desc->niter_expr = NULL_RTX(rtx) 0; 2295 2296 cond = GET_CODE (condition)((enum rtx_code) (condition)->code); 2297 gcc_assert (COMPARISON_P (condition))((void)(!((((rtx_class[(int) (((enum rtx_code) (condition)->
code))]) & (~1)) == (RTX_COMPARE & (~1)))) ? fancy_abort
("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 2297, __FUNCTION__), 0 : 0)); 2298 2299 nonvoid_mode = GET_MODE (XEXP (condition, 0))((machine_mode) ((((condition)->u.fld[0]).rt_rtx))->mode
); 2300 if (nonvoid_mode == VOIDmode((void) 0, E_VOIDmode)) 2301 nonvoid_mode = GET_MODE (XEXP (condition, 1))((machine_mode) ((((condition)->u.fld[1]).rt_rtx))->mode
); 2302 /* The constant comparisons should be folded. */ 2303 gcc_assert (nonvoid_mode != VOIDmode)((void)(!(nonvoid_mode != ((void) 0, E_VOIDmode)) ? fancy_abort
("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.cc"
, 2303, __FUNCTION__), 0 : 0)); 2304 2305 /* We only handle integers or pointers. */ 2306 scalar_int_mode mode; 2307 if (!is_a <scalar_int_mode> (nonvoid_mode, &mode)) 2308 goto fail; 2309 2310 op0 = XEXP (condition, 0)(((condition)->u.fld[0]).rt_rtx); 2311 if (!iv_analyze (insn, mode, op0, &iv0)) 2312 goto fail; 2313 2314 op1 = XEXP (condition, 1)(((condition)->u.fld[1]).rt_rtx); 2315 if (!iv_analyze (insn, mode, op1, &iv1)) 2316 goto fail; 2317 2318 if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT64 2319 || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT64) 2320 goto fail; 2321 2322 /* Check condition and normalize it. */ 2323 2324 switch (cond) 2325 { 2326 case GE: 2327 case GT: 2328 case GEU: 2329 case GTU: 2330 std::swap (iv0, iv1); 2331 cond = swap_condition (cond); 2332 break; 2333 case NE: 2334 case LE: 2335 case LEU: 2336 case LT: 2337 case LTU: 2338 break; 2339 default: 2340 goto fail; 2341 } 2342 2343 /* Handle extends. This is relatively nontrivial, so we only try in some 2344 easy cases, when we can canonicalize the ivs (possibly by adding some 2345 assumptions) to shape subreg (base + i * step). This function also fills 2346 in desc->mode and desc->signed_p. */ 2347 2348 if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc)) 2349 goto fail; 2350 2351 comp_mode = iv0.extend_mode; 2352 mode = iv0.mode; 2353 size = GET_MODE_PRECISION (mode); 2354 get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax); 2355 mode_mmin = lowpart_subreg (mode, mmin, comp_mode); 2356 mode_mmax = lowpart_subreg (mode, mmax, comp_mode); 2357 2358 if (!CONST_INT_P (iv0.step)(((enum rtx_code) (iv0.step)->code) == CONST_INT) || !CONST_INT_P (iv1.step)(((enum rtx_code) (iv1.step)->code) == CONST_INT)) 2359 goto fail; 2360 2361 /* We can take care of the case of two induction variables chasing each other 2362 if the test is NE. I have never seen a loop using it, but still it is 2363 cool. */ 2364 if (iv0.step != const0_rtx(const_int_rtx[64]) && iv1.step != const0_rtx(const_int_rtx[64])) 2365 { 2366 if (cond != NE) 2367 goto fail; 2368 2369 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step); 2370 iv1.step = const0_rtx(const_int_rtx[64]); 2371 } 2372 2373 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode); 2374 iv1.step = lowpart_subreg (mode, iv1.step, comp_mode); 2375 2376 /* This is either infinite loop or the one that ends immediately, depending 2377 on initial values. Unswitching should remove this kind of conditions. */ 2378 if (iv0.step == const0_rtx(const_int_rtx[64]) && iv1.step == const0_rtx(const_int_rtx[64])) 2379 goto fail; 2380 2381 if (cond != NE) 2382 { 2383 if (iv0.step == const0_rtx(const_int_rtx[64])) 2384 step_val = -INTVAL (iv1.step)((iv1.step)->u.hwint[0]); 2385 else 2386 step_val = INTVAL (iv0.step)((iv0.step)->u.hwint[0]); 2387 2388 /* Ignore loops of while (i-- < 10) type. */ 2389 if (step_val < 0) 2390 goto fail; 2391 2392 step_is_pow2 = !(step_val & (step_val - 1)); 2393 } 2394 else 2395 { 2396 /* We do not care about whether the step is power of two in this 2397 case. */ 2398 step_is_pow2 = false; 2399 step_val = 0; 2400 } 2401 2402 /* Some more condition normalization. We must record some assumptions 2403 due to overflows. */ 2404 switch (cond) 2405 { 2406 case LT: 2407 case LTU: 2408 /* We want to take care only of non-sharp relationals; this is easy, 2409 as in cases the overflow would make the transformation unsafe 2410 the loop does not roll. Seemingly it would make more sense to want 2411 to take care of sharp relationals instead, as NE is more similar to 2412 them, but the problem is that here the transformation would be more 2413 difficult due to possibly infinite loops. */ 2414 if (iv0.step == const0_rtx(const_int_rtx[64])) 2415 { 2416 tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2417 assumption = simplify_gen_relational (EQ, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp, 2418 mode_mmax); 2419 if (assumption == const_true_rtx) 2420 goto zero_iter_simplify; 2421 iv0.base = simplify_gen_binary (PLUS, comp_mode, 2422 iv0.base, const1_rtx(const_int_rtx[64 +1])); 2423 } 2424 else 2425 { 2426 tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2427 assumption = simplify_gen_relational (EQ, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp, 2428 mode_mmin); 2429 if (assumption == const_true_rtx) 2430 goto zero_iter_simplify; 2431 iv1.base = simplify_gen_binary (PLUS, comp_mode, 2432 iv1.base, constm1_rtx(const_int_rtx[64 -1])); 2433 } 2434 2435 if (assumption != const0_rtx(const_int_rtx[64])) 2436 desc->noloop_assumptions = 2437 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2438 cond = (cond == LT) ? LE : LEU; 2439 2440 /* It will be useful to be able to tell the difference once more in 2441 LE -> NE reduction. */ 2442 was_sharp = true; 2443 break; 2444 default: ; 2445 } 2446 2447 /* Take care of trivially infinite loops. */ 2448 if (cond != NE) 2449 { 2450 if (iv0.step == const0_rtx(const_int_rtx[64])) 2451 { 2452 tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2453 if (rtx_equal_p (tmp, mode_mmin)) 2454 { 2455 desc->infinite = 2456 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX(rtx) 0); 2457 /* Fill in the remaining fields somehow. */ 2458 goto zero_iter_simplify; 2459 } 2460 } 2461 else 2462 { 2463 tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2464 if (rtx_equal_p (tmp, mode_mmax)) 2465 { 2466 desc->infinite = 2467 alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX(rtx) 0); 2468 /* Fill in the remaining fields somehow. */ 2469 goto zero_iter_simplify; 2470 } 2471 } 2472 } 2473 2474 /* If we can we want to take care of NE conditions instead of size 2475 comparisons, as they are much more friendly (most importantly 2476 this takes care of special handling of loops with step 1). We can 2477 do it if we first check that upper bound is greater or equal to 2478 lower bound, their difference is constant c modulo step and that 2479 there is not an overflow. */ 2480 if (cond != NE) 2481 { 2482 if (iv0.step == const0_rtx(const_int_rtx[64])) 2483 step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode); 2484 else 2485 step = iv0.step; 2486 step = lowpart_subreg (mode, step, comp_mode); 2487 delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base); 2488 delta = lowpart_subreg (mode, delta, comp_mode); 2489 delta = simplify_gen_binary (UMOD, mode, delta, step); 2490 may_xform = const0_rtx(const_int_rtx[64]); 2491 may_not_xform = const_true_rtx; 2492 2493 if (CONST_INT_P (delta)(((enum rtx_code) (delta)->code) == CONST_INT)) 2494 { 2495 if (was_sharp && INTVAL (delta)((delta)->u.hwint[0]) == INTVAL (step)((step)->u.hwint[0]) - 1) 2496 { 2497 /* A special case. We have transformed condition of type 2498 for (i = 0; i < 4; i += 4) 2499 into 2500 for (i = 0; i <= 3; i += 4) 2501 obviously if the test for overflow during that transformation 2502 passed, we cannot overflow here. Most importantly any 2503 loop with sharp end condition and step 1 falls into this 2504 category, so handling this case specially is definitely 2505 worth the troubles. */ 2506 may_xform = const_true_rtx; 2507 } 2508 else if (iv0.step == const0_rtx(const_int_rtx[64])) 2509 { 2510 bound = simplify_gen_binary (PLUS, comp_mode, mmin, step); 2511 bound = simplify_gen_binary (MINUS, comp_mode, bound, delta); 2512 bound = lowpart_subreg (mode, bound, comp_mode); 2513 tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2514 may_xform = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2515 bound, tmp); 2516 may_not_xform = simplify_gen_relational (reverse_condition (cond), 2517 SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2518 bound, tmp); 2519 } 2520 else 2521 { 2522 bound = simplify_gen_binary (MINUS, comp_mode, mmax, step); 2523 bound = simplify_gen_binary (PLUS, comp_mode, bound, delta); 2524 bound = lowpart_subreg (mode, bound, comp_mode); 2525 tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2526 may_xform = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2527 tmp, bound); 2528 may_not_xform = simplify_gen_relational (reverse_condition (cond), 2529 SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2530 tmp, bound); 2531 } 2532 } 2533 2534 if (may_xform != const0_rtx(const_int_rtx[64])) 2535 { 2536 /* We perform the transformation always provided that it is not 2537 completely senseless. This is OK, as we would need this assumption 2538 to determine the number of iterations anyway. */ 2539 if (may_xform != const_true_rtx) 2540 { 2541 /* If the step is a power of two and the final value we have 2542 computed overflows, the cycle is infinite. Otherwise it 2543 is nontrivial to compute the number of iterations. */ 2544 if (step_is_pow2) 2545 desc->infinite = alloc_EXPR_LIST (0, may_not_xform, 2546 desc->infinite); 2547 else 2548 desc->assumptions = alloc_EXPR_LIST (0, may_xform, 2549 desc->assumptions); 2550 } 2551 2552 /* We are going to lose some information about upper bound on 2553 number of iterations in this step, so record the information 2554 here. */ 2555 inc = INTVAL (iv0.step)((iv0.step)->u.hwint[0]) - INTVAL (iv1.step)((iv1.step)->u.hwint[0]); 2556 if (CONST_INT_P (iv1.base)(((enum rtx_code) (iv1.base)->code) == CONST_INT)) 2557 up = INTVAL (iv1.base)((iv1.base)->u.hwint[0]); 2558 else 2559 up = INTVAL (mode_mmax)((mode_mmax)->u.hwint[0]) - inc; 2560 down = INTVAL (CONST_INT_P (iv0.base)(((((enum rtx_code) (iv0.base)->code) == CONST_INT) ? iv0.
base : mode_mmin)->u.hwint[0]) 2561 ? iv0.base(((((enum rtx_code) (iv0.base)->code) == CONST_INT) ? iv0.
base : mode_mmin)->u.hwint[0]) 2562 : mode_mmin)(((((enum rtx_code) (iv0.base)->code) == CONST_INT) ? iv0.
base : mode_mmin)->u.hwint[0]); 2563 max = (up - down) / inc + 1; 2564 if (!desc->infinite 2565 && !desc->assumptions) 2566 record_niter_bound (loop, max, false, true); 2567 2568 if (iv0.step == const0_rtx(const_int_rtx[64])) 2569 { 2570 iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta); 2571 iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step); 2572 } 2573 else 2574 { 2575 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta); 2576 iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step); 2577 } 2578 2579 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2580 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2581 assumption = simplify_gen_relational (reverse_condition (cond), 2582 SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp0, tmp1); 2583 if (assumption == const_true_rtx) 2584 goto zero_iter_simplify; 2585 else if (assumption != const0_rtx(const_int_rtx[64])) 2586 desc->noloop_assumptions = 2587 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2588 cond = NE; 2589 } 2590 } 2591 2592 /* Count the number of iterations. */ 2593 if (cond == NE) 2594 { 2595 /* Everything we do here is just arithmetics modulo size of mode. This 2596 makes us able to do more involved computations of number of iterations 2597 than in other cases. First transform the condition into shape 2598 s * i <> c, with s positive. */ 2599 iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base); 2600 iv0.base = const0_rtx(const_int_rtx[64]); 2601 iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step); 2602 iv1.step = const0_rtx(const_int_rtx[64]); 2603 if (INTVAL (iv0.step)((iv0.step)->u.hwint[0]) < 0) 2604 { 2605 iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, comp_mode); 2606 iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, comp_mode); 2607 } 2608 iv0.step = lowpart_subreg (mode, iv0.step, comp_mode); 2609 2610 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop 2611 is infinite. Otherwise, the number of iterations is 2612 (inverse(s/d) * (c/d)) mod (size of mode/d). */ 2613 s = INTVAL (iv0.step)((iv0.step)->u.hwint[0]); d = 1; 2614 while (s % 2 != 1) 2615 { 2616 s /= 2; 2617 d *= 2; 2618 size--; 2619 } 2620 bound = GEN_INT (((uint64_t) 1 << (size - 1 ) << 1) - 1)gen_rtx_CONST_INT (((void) 0, E_VOIDmode), (((uint64_t) 1 <<
(size - 1 ) << 1) - 1)); 2621 2622 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2623 tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode)); 2624 assumption = simplify_gen_relational (NE, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp, const0_rtx(const_int_rtx[64])); 2625 desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite); 2626 2627 tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode)); 2628 inv = inverse (s, size); 2629 tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode)); 2630 desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound); 2631 } 2632 else 2633 { 2634 if (iv1.step == const0_rtx(const_int_rtx[64])) 2635 /* Condition in shape a + s * i <= b 2636 We must know that b + s does not overflow and a <= b + s and then we 2637 can compute number of iterations as (b + s - a) / s. (It might 2638 seem that we in fact could be more clever about testing the b + s 2639 overflow condition using some information about b - a mod s, 2640 but it was already taken into account during LE -> NE transform). */ 2641 { 2642 step = iv0.step; 2643 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2644 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2645 2646 bound = simplify_gen_binary (MINUS, mode, mode_mmax, 2647 lowpart_subreg (mode, step, 2648 comp_mode)); 2649 if (step_is_pow2) 2650 { 2651 rtx t0, t1; 2652 2653 /* If s is power of 2, we know that the loop is infinite if 2654 a % s <= b % s and b + s overflows. */ 2655 assumption = simplify_gen_relational (reverse_condition (cond), 2656 SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2657 tmp1, bound); 2658 2659 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step); 2660 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step); 2661 tmp = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, t0, t1); 2662 assumption = simplify_gen_binary (AND, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), assumption, tmp); 2663 desc->infinite = 2664 alloc_EXPR_LIST (0, assumption, desc->infinite); 2665 } 2666 else 2667 { 2668 assumption = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2669 tmp1, bound); 2670 desc->assumptions = 2671 alloc_EXPR_LIST (0, assumption, desc->assumptions); 2672 } 2673 2674 tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step); 2675 tmp = lowpart_subreg (mode, tmp, comp_mode); 2676 assumption = simplify_gen_relational (reverse_condition (cond), 2677 SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp0, tmp); 2678 2679 delta = simplify_gen_binary (PLUS, mode, tmp1, step); 2680 delta = simplify_gen_binary (MINUS, mode, delta, tmp0); 2681 } 2682 else 2683 { 2684 /* Condition in shape a <= b - s * i 2685 We must know that a - s does not overflow and a - s <= b and then 2686 we can again compute number of iterations as (b - (a - s)) / s. */ 2687 step = simplify_gen_unary (NEG, mode, iv1.step, mode); 2688 tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2689 tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2690 2691 bound = simplify_gen_binary (PLUS, mode, mode_mmin, 2692 lowpart_subreg (mode, step, comp_mode)); 2693 if (step_is_pow2) 2694 { 2695 rtx t0, t1; 2696 2697 /* If s is power of 2, we know that the loop is infinite if 2698 a % s <= b % s and a - s overflows. */ 2699 assumption = simplify_gen_relational (reverse_condition (cond), 2700 SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2701 bound, tmp0); 2702 2703 t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step); 2704 t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step); 2705 tmp = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, t0, t1); 2706 assumption = simplify_gen_binary (AND, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), assumption, tmp); 2707 desc->infinite = 2708 alloc_EXPR_LIST (0, assumption, desc->infinite); 2709 } 2710 else 2711 { 2712 assumption = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2713 bound, tmp0); 2714 desc->assumptions = 2715 alloc_EXPR_LIST (0, assumption, desc->assumptions); 2716 } 2717 2718 tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step); 2719 tmp = lowpart_subreg (mode, tmp, comp_mode); 2720 assumption = simplify_gen_relational (reverse_condition (cond), 2721 SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, 2722 tmp, tmp1); 2723 delta = simplify_gen_binary (MINUS, mode, tmp0, step); 2724 delta = simplify_gen_binary (MINUS, mode, tmp1, delta); 2725 } 2726 if (assumption == const_true_rtx) 2727 goto zero_iter_simplify; 2728 else if (assumption != const0_rtx(const_int_rtx[64])) 2729 desc->noloop_assumptions = 2730 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2731 delta = simplify_gen_binary (UDIV, mode, delta, step); 2732 desc->niter_expr = delta; 2733 } 2734 2735 old_niter = desc->niter_expr; 2736 2737 simplify_using_initial_values (loop, AND, &desc->assumptions); 2738 if (desc->assumptions 2739 && XEXP (desc->assumptions, 0)(((desc->assumptions)->u.fld[0]).rt_rtx) == const0_rtx(const_int_rtx[64])) 2740 goto fail; 2741 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions); 2742 simplify_using_initial_values (loop, IOR, &desc->infinite); 2743 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr); 2744 2745 /* Rerun the simplification. Consider code (created by copying loop headers) 2746 2747 i = 0; 2748 2749 if (0 < n) 2750 { 2751 do 2752 { 2753 i++; 2754 } while (i < n); 2755 } 2756 2757 The first pass determines that i = 0, the second pass uses it to eliminate 2758 noloop assumption. */ 2759 2760 simplify_using_initial_values (loop, AND, &desc->assumptions); 2761 if (desc->assumptions 2762 && XEXP (desc->assumptions, 0)(((desc->assumptions)->u.fld[0]).rt_rtx) == const0_rtx(const_int_rtx[64])) 2763 goto fail; 2764 simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions); 2765 simplify_using_initial_values (loop, IOR, &desc->infinite); 2766 simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr); 2767 2768 if (desc->noloop_assumptions 2769 && XEXP (desc->noloop_assumptions, 0)(((desc->noloop_assumptions)->u.fld[0]).rt_rtx) == const_true_rtx) 2770 goto zero_iter; 2771 2772 if (CONST_INT_P (desc->niter_expr)(((enum rtx_code) (desc->niter_expr)->code) == CONST_INT
)) 2773 { 2774 uint64_t val = INTVAL (desc->niter_expr)((desc->niter_expr)->u.hwint[0]); 2775 2776 desc->const_iter = true; 2777 desc->niter = val & GET_MODE_MASK (desc->mode)mode_mask_array[desc->mode]; 2778 if (!desc->infinite 2779 && !desc->assumptions) 2780 record_niter_bound (loop, desc->niter, false, true); 2781 } 2782 else 2783 { 2784 max = determine_max_iter (loop, desc, old_niter); 2785 if (!max) 2786 goto zero_iter_simplify; 2787 if (!desc->infinite 2788 && !desc->assumptions) 2789 record_niter_bound (loop, max, false, true); 2790 2791 /* simplify_using_initial_values does a copy propagation on the registers 2792 in the expression for the number of iterations. This prolongs life 2793 ranges of registers and increases register pressure, and usually 2794 brings no gain (and if it happens to do, the cse pass will take care 2795 of it anyway). So prevent this behavior, unless it enabled us to 2796 derive that the number of iterations is a constant. */ 2797 desc->niter_expr = old_niter; 2798 } 2799 2800 return; 2801 2802zero_iter_simplify: 2803 /* Simplify the assumptions. */ 2804 simplify_using_initial_values (loop, AND, &desc->assumptions); 2805 if (desc->assumptions 2806 && XEXP (desc->assumptions, 0)(((desc->assumptions)->u.fld[0]).rt_rtx) == const0_rtx(const_int_rtx[64])) 2807 goto fail; 2808 simplify_using_initial_values (loop, IOR, &desc->infinite); 2809 2810 /* Fallthru. */ 2811zero_iter: 2812 desc->const_iter = true; 2813 desc->niter = 0; 2814 record_niter_bound (loop, 0, true, true); 2815 desc->noloop_assumptions = NULL_RTX(rtx) 0; 2816 desc->niter_expr = const0_rtx(const_int_rtx[64]); 2817 return; 2818 2819fail: 2820 desc->simple_p = false; 2821 return; 2822} 2823 2824/* Checks whether E is a simple exit from LOOP and stores its description 2825 into DESC. */ 2826 2827static void 2828check_simple_exit (class loop *loop, edge e, class niter_desc *desc) 2829{ 2830 basic_block exit_bb; 2831 rtx condition; 2832 rtx_insn *at; 2833 edge ein; 2834 2835 exit_bb = e->src; 2836 desc->simple_p = false; 2837 2838 /* It must belong directly to the loop. */ 2839 if (exit_bb->loop_father != loop) 2840 return; 2841 2842 /* It must be tested (at least) once during any iteration. */ 2843 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb)) 2844 return; 2845 2846 /* It must end in a simple conditional jump. */ 2847 if (!any_condjump_p (BB_END (exit_bb)(exit_bb)->il.x.rtl->end_) || !onlyjump_p (BB_END (exit_bb)(exit_bb)->il.x.rtl->end_)) 2848 return; 2849 2850 ein = EDGE_SUCC (exit_bb, 0)(*(exit_bb)->succs)[(0)]; 2851 if (ein == e) 2852 ein = EDGE_SUCC (exit_bb, 1)(*(exit_bb)->succs)[(1)]; 2853 2854 desc->out_edge = e; 2855 desc->in_edge = ein; 2856 2857 /* Test whether the condition is suitable. */ 2858 if (!(condition = get_condition (BB_END (ein->src)(ein->src)->il.x.rtl->end_, &at, false, false))) 2859 return; 2860 2861 if (ein->flags & EDGE_FALLTHRU) 2862 { 2863 condition = reversed_condition (condition); 2864 if (!condition) 2865 return; 2866 } 2867 2868 /* Check that we are able to determine number of iterations and fill 2869 in information about it. */ 2870 iv_number_of_iterations (loop, at, condition, desc); 2871} 2872 2873/* Finds a simple exit of LOOP and stores its description into DESC. */ 2874 2875static void 2876find_simple_exit (class loop *loop, class niter_desc *desc) 2877{ 2878 unsigned i; 2879 basic_block *body; 2880 edge e; 2881 class niter_desc act; 2882 bool any = false; 2883 edge_iterator ei; 2884 2885 desc->simple_p = false; 2886 body = get_loop_body (loop); 2887 2888 for (i = 0; i < loop->num_nodes; i++) 2889 { 2890 FOR_EACH_EDGE (e, ei, body[i]->succs)for ((ei) = ei_start_1 (&((body[i]->succs))); ei_cond (
(ei), &(e)); ei_next (&(ei))) 2891 { 2892 if (flow_bb_inside_loop_p (loop, e->dest)) 2893 continue; 2894 2895 check_simple_exit (loop, e, &act); 2896 if (!act.simple_p) 2897 continue; 2898 2899 if (!any) 2900 any = true; 2901 else 2902 { 2903 /* Prefer constant iterations; the less the better. */ 2904 if (!act.const_iter 2905 || (desc->const_iter && act.niter >= desc->niter)) 2906 continue; 2907 2908 /* Also if the actual exit may be infinite, while the old one 2909 not, prefer the old one. */ 2910 if (act.infinite && !desc->infinite) 2911 continue; 2912 } 2913 2914 *desc = act; 2915 } 2916 } 2917 2918 if (dump_file) 2919 { 2920 if (desc->simple_p) 2921 { 2922 fprintf (dump_file, "Loop %d is simple:\n", loop->num); 2923 fprintf (dump_file, " simple exit %d -> %d\n", 2924 desc->out_edge->src->index, 2925 desc->out_edge->dest->index); 2926 if (desc->assumptions) 2927 { 2928 fprintf (dump_file, " assumptions: "); 2929 print_rtl (dump_file, desc->assumptions); 2930 fprintf (dump_file, "\n"); 2931 } 2932 if (desc->noloop_assumptions) 2933 { 2934 fprintf (dump_file, " does not roll if: "); 2935 print_rtl (dump_file, desc->noloop_assumptions); 2936 fprintf (dump_file, "\n"); 2937 } 2938 if (desc->infinite) 2939 { 2940 fprintf (dump_file, " infinite if: "); 2941 print_rtl (dump_file, desc->infinite); 2942 fprintf (dump_file, "\n"); 2943 } 2944 2945 fprintf (dump_file, " number of iterations: "); 2946 print_rtl (dump_file, desc->niter_expr); 2947 fprintf (dump_file, "\n"); 2948 2949 fprintf (dump_file, " upper bound: %li\n", 2950 (long)get_max_loop_iterations_int (loop)); 2951 fprintf (dump_file, " likely upper bound: %li\n", 2952 (long)get_likely_max_loop_iterations_int (loop)); 2953 fprintf (dump_file, " realistic bound: %li\n", 2954 (long)get_estimated_loop_iterations_int (loop)); 2955 } 2956 else 2957 fprintf (dump_file, "Loop %d is not simple.\n", loop->num); 2958 } 2959 2960 /* Fix up the finiteness if possible. We can only do it for single exit, 2961 since the loop is finite, but it's possible that we predicate one loop 2962 exit to be finite which can not be determined as finite in middle-end as 2963 well. It results in incorrect predicate information on the exit condition 2964 expression. For example, if says [(int) _1 + -8, + , -8] != 0 finite, 2965 it means _1 can exactly divide -8. */ 2966 if (desc->infinite && single_exit (loop) && finite_loop_p (loop)) 2967 { 2968 desc->infinite = NULL_RTX(rtx) 0; 2969 if (dump_file) 2970 fprintf (dump_file, " infinite updated to finite.\n"); 2971 } 2972 2973 free (body); 2974} 2975 2976/* Creates a simple loop description of LOOP if it was not computed 2977 already. */ 2978 2979class niter_desc * 2980get_simple_loop_desc (class loop *loop) 2981{ 2982 class niter_desc *desc = simple_loop_desc (loop); 2983 2984 if (desc) 2985 return desc; 2986 2987 /* At least desc->infinite is not always initialized by 2988 find_simple_loop_exit. */ 2989 desc = ggc_cleared_alloc<niter_desc> (); 2990 iv_analysis_loop_init (loop); 2991 find_simple_exit (loop, desc); 2992 loop->simple_loop_desc = desc; 2993 return desc; 2994} 2995 2996/* Releases simple loop description for LOOP. */ 2997 2998void 2999free_simple_loop_desc (class loop *loop) 3000{ 3001 class niter_desc *desc = simple_loop_desc (loop); 3002 3003 if (!desc) 3004 return; 3005 3006 ggc_free (desc); 3007 loop->simple_loop_desc = NULL__null; 3008}