/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc

Bug Summary

File:	build/gcc/tree-ssa-loop-ivopts.cc
Warning:	line 2223, column 18 Division by zero
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 tree-ssa-loop-ivopts.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-Cb6zHM.plist -x c++ /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc
1/* Induction variable optimizations.
 Copyright (C) 2003-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 pass tries to find the optimal set of induction variables for the loop.
 It optimizes just the basic linear induction variables (although adding
 support for other types should not be too hard).  It includes the
 optimizations commonly known as strength reduction, induction variable
 coalescing and induction variable elimination.  It does it in the
 following steps:

 1) The interesting uses of induction variables are found.  This includes

    -- uses of induction variables in non-linear expressions
    -- addresses of arrays
    -- comparisons of induction variables

    Note the interesting uses are categorized and handled in group.
    Generally, address type uses are grouped together if their iv bases
    are different in constant offset.

 2) Candidates for the induction variables are found.  This includes

    -- old induction variables
    -- the variables defined by expressions derived from the "interesting
groups/uses" above

 3) The optimal (w.r. to a cost function) set of variables is chosen.  The
    cost function assigns a cost to sets of induction variables and consists
    of three parts:

    -- The group/use costs.  Each of the interesting groups/uses chooses
the best induction variable in the set and adds its cost to the sum.
The cost reflects the time spent on modifying the induction variables
value to be usable for the given purpose (adding base and offset for
arrays, etc.).
    -- The variable costs.  Each of the variables has a cost assigned that
reflects the costs associated with incrementing the value of the
variable.  The original variables are somewhat preferred.
    -- The set cost.  Depending on the size of the set, extra cost may be
added to reflect register pressure.

    All the costs are defined in a machine-specific way, using the target
    hooks and machine descriptions to determine them.

 4) The trees are transformed to use the new variables, the dead code is
    removed.

 All of this is done loop by loop.  Doing it globally is theoretically
 possible, it might give a better performance and it might enable us
 to decide costs more precisely, but getting all the interactions right
 would be complicated.

 For the targets supporting low-overhead loops, IVOPTs has to take care of
 the loops which will probably be transformed in RTL doloop optimization,
 to try to make selected IV candidate set optimal.  The process of doloop
 support includes:

 1) Analyze the current loop will be transformed to doloop or not, find and
    mark its compare type IV use as doloop use (iv_group field doloop_p), and
    set flag doloop_use_p of ivopts_data to notify subsequent processings on
    doloop.  See analyze_and_mark_doloop_use and its callees for the details.
    The target hook predict_doloop_p can be used for target specific checks.

 2) Add one doloop dedicated IV cand {(may_be_zero ? 1 : (niter + 1)), +, -1},
    set flag doloop_p of iv_cand, step cost is set as zero and no extra cost
    like biv.  For cost determination between doloop IV cand and IV use, the
    target hooks doloop_cost_for_generic and doloop_cost_for_address are
    provided to add on extra costs for generic type and address type IV use.
    Zero cost is assigned to the pair between doloop IV cand and doloop IV
    use, and bound zero is set for IV elimination.

 3) With the cost setting in step 2), the current cost model based IV
    selection algorithm will process as usual, pick up doloop dedicated IV if
    profitable.  */

92#include "config.h"
93#include "system.h"
94#include "coretypes.h"
95#include "backend.h"
96#include "rtl.h"
97#include "tree.h"
98#include "gimple.h"
99#include "cfghooks.h"
100#include "tree-pass.h"
101#include "memmodel.h"
102#include "tm_p.h"
103#include "ssa.h"
104#include "expmed.h"
105#include "insn-config.h"
106#include "emit-rtl.h"
107#include "recog.h"
108#include "cgraph.h"
109#include "gimple-pretty-print.h"
110#include "alias.h"
111#include "fold-const.h"
112#include "stor-layout.h"
113#include "tree-eh.h"
114#include "gimplify.h"
115#include "gimple-iterator.h"
116#include "gimplify-me.h"
117#include "tree-cfg.h"
118#include "tree-ssa-loop-ivopts.h"
119#include "tree-ssa-loop-manip.h"
120#include "tree-ssa-loop-niter.h"
121#include "tree-ssa-loop.h"
122#include "explow.h"
123#include "expr.h"
124#include "tree-dfa.h"
125#include "tree-ssa.h"
126#include "cfgloop.h"
127#include "tree-scalar-evolution.h"
128#include "tree-affine.h"
129#include "tree-ssa-propagate.h"
130#include "tree-ssa-address.h"
131#include "builtins.h"
132#include "tree-vectorizer.h"
133#include "dbgcnt.h"
134#include "cfganal.h"

136/* For lang_hooks.types.type_for_mode.  */
137#include "langhooks.h"

139/* FIXME: Expressions are expanded to RTL in this pass to determine the
 cost of different addressing modes.  This should be moved to a TBD
 interface between the GIMPLE and RTL worlds.  */

143/* The infinite cost.  */
144#define INFTY1000000000 1000000000

146/* Returns the expected number of loop iterations for LOOP.
 The average trip count is computed from profile data if it
 exists. */

150static inline HOST_WIDE_INTlong
151avg_loop_niter (class loop *loop)
152{
HOST_WIDE_INTlong niter = estimated_stmt_executions_int (loop);
if (niter == -1)
  {
    niter = likely_max_stmt_executions_int (loop);

    if (niter == -1 || niter > param_avg_loop_niterglobal_options.x_param_avg_loop_niter)
return param_avg_loop_niterglobal_options.x_param_avg_loop_niter;
  }

return niter;
163}

165struct iv_use;

167/* Representation of the induction variable.  */
168struct iv
169{
tree base;		/* Initial value of the iv.  */
tree base_object;	/* A memory object to that the induction variable points.  */
tree step;		/* Step of the iv (constant only).  */
tree ssa_name;	/* The ssa name with the value.  */
struct iv_use *nonlin_use;	/* The identifier in the use if it is the case.  */
bool biv_p;		/* Is it a biv?  */
bool no_overflow;	/* True if the iv doesn't overflow.  */
bool have_address_use;/* For biv, indicate if it's used in any address
	   type use.  */
179};

181/* Per-ssa version information (induction variable descriptions, etc.).  */
182struct version_info
183{
tree name;		/* The ssa name.  */
struct iv *iv;	/* Induction variable description.  */
bool has_nonlin_use;	/* For a loop-level invariant, whether it is used in
	   an expression that is not an induction variable.  */
bool preserve_biv;	/* For the original biv, whether to preserve it.  */
unsigned inv_id;	/* Id of an invariant.  */
190};

192/* Types of uses.  */
193enum use_type
194{
USE_NONLINEAR_EXPR,	/* Use in a nonlinear expression.  */
USE_REF_ADDRESS,	/* Use is an address for an explicit memory
	   reference.  */
USE_PTR_ADDRESS,	/* Use is a pointer argument to a function in
	   cases where the expansion of the function
	   will turn the argument into a normal address.  */
USE_COMPARE		/* Use is a compare.  */
202};

204/* Cost of a computation.  */
205class comp_cost
206{
207public:
comp_cost (): cost (0), complexity (0), scratch (0)
{}

comp_cost (int64_t cost, unsigned complexity, int64_t scratch = 0)
  : cost (cost), complexity (complexity), scratch (scratch)
{}

/* Returns true if COST is infinite.  */
bool infinite_cost_p ();

/* Adds costs COST1 and COST2.  */
friend comp_cost operator+ (comp_cost cost1, comp_cost cost2);

/* Adds COST to the comp_cost.  */
comp_cost operator+= (comp_cost cost);

/* Adds constant C to this comp_cost.  */
comp_cost operator+= (HOST_WIDE_INTlong c);

/* Subtracts constant C to this comp_cost.  */
comp_cost operator-= (HOST_WIDE_INTlong c);

/* Divide the comp_cost by constant C.  */
comp_cost operator/= (HOST_WIDE_INTlong c);

/* Multiply the comp_cost by constant C.  */
comp_cost operator*= (HOST_WIDE_INTlong c);

/* Subtracts costs COST1 and COST2.  */
friend comp_cost operator- (comp_cost cost1, comp_cost cost2);

/* Subtracts COST from this comp_cost.  */
comp_cost operator-= (comp_cost cost);

/* Returns true if COST1 is smaller than COST2.  */
friend bool operator< (comp_cost cost1, comp_cost cost2);

/* Returns true if COST1 and COST2 are equal.  */
friend bool operator== (comp_cost cost1, comp_cost cost2);

/* Returns true if COST1 is smaller or equal than COST2.  */
friend bool operator<= (comp_cost cost1, comp_cost cost2);

int64_t cost;		/* The runtime cost.  */
unsigned complexity;  /* The estimate of the complexity of the code for
	   the computation (in no concrete units --
	   complexity field should be larger for more
	   complex expressions and addressing modes).  */
int64_t scratch;	/* Scratch used during cost computation.  */
257};

259static const comp_cost no_cost;
260static const comp_cost infinite_cost (INFTY1000000000, 0, INFTY1000000000);

262bool
263comp_cost::infinite_cost_p ()
264{
return cost == INFTY1000000000;
266}

268comp_cost
269operator+ (comp_cost cost1, comp_cost cost2)
270{
if (cost1.infinite_cost_p () || cost2.infinite_cost_p ())
  return infinite_cost;

gcc_assert (cost1.cost + cost2.cost < infinite_cost.cost)((void)(!(cost1.cost + cost2.cost < infinite_cost.cost) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 274, __FUNCTION__), 0 : 0));
cost1.cost += cost2.cost;
cost1.complexity += cost2.complexity;

return cost1;
279}

281comp_cost
282operator- (comp_cost cost1, comp_cost cost2)
283{
if (cost1.infinite_cost_p ())
  return infinite_cost;

gcc_assert (!cost2.infinite_cost_p ())((void)(!(!cost2.infinite_cost_p ()) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 287, __FUNCTION__), 0 : 0));
gcc_assert (cost1.cost - cost2.cost < infinite_cost.cost)((void)(!(cost1.cost - cost2.cost < infinite_cost.cost) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 288, __FUNCTION__), 0 : 0));

cost1.cost -= cost2.cost;
cost1.complexity -= cost2.complexity;

return cost1;
294}

296comp_cost
297comp_cost::operator+= (comp_cost cost)
298{
*this = *this + cost;
return *this;
301}

303comp_cost
304comp_cost::operator+= (HOST_WIDE_INTlong c)
305{
if (c >= INFTY1000000000)
  this->cost = INFTY1000000000;

if (infinite_cost_p ())
  return *this;

gcc_assert (this->cost + c < infinite_cost.cost)((void)(!(this->cost + c < infinite_cost.cost) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 312, __FUNCTION__), 0 : 0));
this->cost += c;

return *this;
316}

318comp_cost
319comp_cost::operator-= (HOST_WIDE_INTlong c)
320{
if (infinite_cost_p ())
  return *this;

gcc_assert (this->cost - c < infinite_cost.cost)((void)(!(this->cost - c < infinite_cost.cost) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 324, __FUNCTION__), 0 : 0));
this->cost -= c;

return *this;
328}

330comp_cost
331comp_cost::operator/= (HOST_WIDE_INTlong c)
332{
gcc_assert (c != 0)((void)(!(c != 0) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 333, __FUNCTION__), 0 : 0));
if (infinite_cost_p ())
  return *this;

this->cost /= c;

return *this;
340}

342comp_cost
343comp_cost::operator*= (HOST_WIDE_INTlong c)
344{
if (infinite_cost_p ())
  return *this;

gcc_assert (this->cost * c < infinite_cost.cost)((void)(!(this->cost * c < infinite_cost.cost) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 348, __FUNCTION__), 0 : 0));
this->cost *= c;

return *this;
352}

354comp_cost
355comp_cost::operator-= (comp_cost cost)
356{
*this = *this - cost;
return *this;
359}

361bool
362operator< (comp_cost cost1, comp_cost cost2)
363{
if (cost1.cost == cost2.cost)
  return cost1.complexity < cost2.complexity;

return cost1.cost < cost2.cost;
368}

370bool
371operator== (comp_cost cost1, comp_cost cost2)
372{
return cost1.cost == cost2.cost
  && cost1.complexity == cost2.complexity;
375}

377bool
378operator<= (comp_cost cost1, comp_cost cost2)
379{
return cost1 < cost2 || cost1 == cost2;
381}

383struct iv_inv_expr_ent;

385/* The candidate - cost pair.  */
386class cost_pair
387{
388public:
struct iv_cand *cand;	/* The candidate.  */
comp_cost cost;	/* The cost.  */
enum tree_code comp;	/* For iv elimination, the comparison.  */
bitmap inv_vars;	/* The list of invariant ssa_vars that have to be
	   preserved when representing iv_use with iv_cand.  */
bitmap inv_exprs;	/* The list of newly created invariant expressions
	   when representing iv_use with iv_cand.  */
tree value;		/* For final value elimination, the expression for
	   the final value of the iv.  For iv elimination,
	   the new bound to compare with.  */
399};

401/* Use.  */
402struct iv_use
403{
unsigned id;		/* The id of the use.  */
unsigned group_id;	/* The group id the use belongs to.  */
enum use_type type;	/* Type of the use.  */
tree mem_type;	/* The memory type to use when testing whether an
	   address is legitimate, and what the address's
	   cost is.  */
struct iv *iv;	/* The induction variable it is based on.  */
gimple *stmt;		/* Statement in that it occurs.  */
tree *op_p;		/* The place where it occurs.  */

tree addr_base;	/* Base address with const offset stripped.  */
poly_uint64_pod addr_offset;
	/* Const offset stripped from base address.  */
417};

419/* Group of uses.  */
420struct iv_group
421{
/* The id of the group.  */
unsigned id;
/* Uses of the group are of the same type.  */
enum use_type type;
/* The set of "related" IV candidates, plus the important ones.  */
bitmap related_cands;
/* Number of IV candidates in the cost_map.  */
unsigned n_map_members;
/* The costs wrto the iv candidates.  */
class cost_pair *cost_map;
/* The selected candidate for the group.  */
struct iv_cand *selected;
/* To indicate this is a doloop use group.  */
bool doloop_p;
/* Uses in the group.  */
vec<struct iv_use *> vuses;
438};

440/* The position where the iv is computed.  */
441enum iv_position
442{
IP_NORMAL,		/* At the end, just before the exit condition.  */
IP_END,		/* At the end of the latch block.  */
IP_BEFORE_USE,	/* Immediately before a specific use.  */
IP_AFTER_USE,		/* Immediately after a specific use.  */
IP_ORIGINAL		/* The original biv.  */
448};

450/* The induction variable candidate.  */
451struct iv_cand
452{
unsigned id;		/* The number of the candidate.  */
bool important;	/* Whether this is an "important" candidate, i.e. such
	   that it should be considered by all uses.  */
bool involves_undefs; /* Whether the IV involves undefined values.  */
ENUM_BITFIELD(iv_position)enum iv_position pos : 8;	/* Where it is computed.  */
gimple *incremented_at;/* For original biv, the statement where it is
	   incremented.  */
tree var_before;	/* The variable used for it before increment.  */
tree var_after;	/* The variable used for it after increment.  */
struct iv *iv;	/* The value of the candidate.  NULL for
	   "pseudocandidate" used to indicate the possibility
	   to replace the final value of an iv by direct
	   computation of the value.  */
unsigned cost;	/* Cost of the candidate.  */
unsigned cost_step;	/* Cost of the candidate's increment operation.  */
struct iv_use *ainc_use; /* For IP_{BEFORE,AFTER}_USE candidates, the place
	      where it is incremented.  */
bitmap inv_vars;	/* The list of invariant ssa_vars used in step of the
	   iv_cand.  */
bitmap inv_exprs;	/* If step is more complicated than a single ssa_var,
	   handle it as a new invariant expression which will
	   be hoisted out of loop.  */
struct iv *orig_iv;	/* The original iv if this cand is added from biv with
	   smaller type.  */
bool doloop_p;	/* Whether this is a doloop candidate.  */
478};

480/* Hashtable entry for common candidate derived from iv uses.  */
481class iv_common_cand
482{
483public:
tree base;
tree step;
/* IV uses from which this common candidate is derived.  */
auto_vec<struct iv_use *> uses;
hashval_t hash;
489};

491/* Hashtable helpers.  */

493struct iv_common_cand_hasher : delete_ptr_hash <iv_common_cand>
494{
static inline hashval_t hash (const iv_common_cand *);
static inline bool equal (const iv_common_cand *, const iv_common_cand *);
497};

499/* Hash function for possible common candidates.  */

501inline hashval_t
502iv_common_cand_hasher::hash (const iv_common_cand *ccand)
503{
return ccand->hash;
505}

507/* Hash table equality function for common candidates.  */

509inline bool
510iv_common_cand_hasher::equal (const iv_common_cand *ccand1,
	      const iv_common_cand *ccand2)
512{
return (ccand1->hash == ccand2->hash
 && operand_equal_p (ccand1->base, ccand2->base, 0)
 && operand_equal_p (ccand1->step, ccand2->step, 0)
 && (TYPE_PRECISION (TREE_TYPE (ccand1->base))((tree_class_check ((((contains_struct_check ((ccand1->base
), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 516, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 516, __FUNCTION__))->type_common.precision)
     == TYPE_PRECISION (TREE_TYPE (ccand2->base))((tree_class_check ((((contains_struct_check ((ccand2->base
), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 517, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 517, __FUNCTION__))->type_common.precision)));
518}

520/* Loop invariant expression hashtable entry.  */

522struct iv_inv_expr_ent
523{
/* Tree expression of the entry.  */
tree expr;
/* Unique indentifier.  */
int id;
/* Hash value.  */
hashval_t hash;
530};

532/* Sort iv_inv_expr_ent pair A and B by id field.  */

534static int
535sort_iv_inv_expr_ent (const void *a, const void *b)
536{
const iv_inv_expr_ent * const *e1 = (const iv_inv_expr_ent * const *) (a);
const iv_inv_expr_ent * const *e2 = (const iv_inv_expr_ent * const *) (b);

unsigned id1 = (*e1)->id;
unsigned id2 = (*e2)->id;

if (id1 < id2)
  return -1;
else if (id1 > id2)
  return 1;
else
  return 0;
549}

551/* Hashtable helpers.  */

553struct iv_inv_expr_hasher : free_ptr_hash <iv_inv_expr_ent>
554{
static inline hashval_t hash (const iv_inv_expr_ent *);
static inline bool equal (const iv_inv_expr_ent *, const iv_inv_expr_ent *);
557};

559/* Return true if uses of type TYPE represent some form of address.  */

561inline bool
562address_p (use_type type)
563{
return type == USE_REF_ADDRESS || type == USE_PTR_ADDRESS;
565}

567/* Hash function for loop invariant expressions.  */

569inline hashval_t
570iv_inv_expr_hasher::hash (const iv_inv_expr_ent *expr)
571{
return expr->hash;
573}

575/* Hash table equality function for expressions.  */

577inline bool
578iv_inv_expr_hasher::equal (const iv_inv_expr_ent *expr1,
	   const iv_inv_expr_ent *expr2)
580{
return expr1->hash == expr2->hash
&& operand_equal_p (expr1->expr, expr2->expr, 0);
583}

585struct ivopts_data
586{
/* The currently optimized loop.  */
class loop *current_loop;
location_t loop_loc;

/* Numbers of iterations for all exits of the current loop.  */
hash_map<edge, tree_niter_desc *> *niters;

/* Number of registers used in it.  */
unsigned regs_used;

/* The size of version_info array allocated.  */
unsigned version_info_size;

/* The array of information for the ssa names.  */
struct version_info *version_info;

/* The hashtable of loop invariant expressions created
   by ivopt.  */
hash_table<iv_inv_expr_hasher> *inv_expr_tab;

/* The bitmap of indices in version_info whose value was changed.  */
bitmap relevant;

/* The uses of induction variables.  */
vec<iv_group *> vgroups;

/* The candidates.  */
vec<iv_cand *> vcands;

/* A bitmap of important candidates.  */
bitmap important_candidates;

/* Cache used by tree_to_aff_combination_expand.  */
hash_map<tree, name_expansion *> *name_expansion_cache;

/* The hashtable of common candidates derived from iv uses.  */
hash_table<iv_common_cand_hasher> *iv_common_cand_tab;

/* The common candidates.  */
vec<iv_common_cand *> iv_common_cands;

/* Hash map recording base object information of tree exp.  */
hash_map<tree, tree> *base_object_map;

/* The maximum invariant variable id.  */
unsigned max_inv_var_id;

/* The maximum invariant expression id.  */
unsigned max_inv_expr_id;

/* Number of no_overflow BIVs which are not used in memory address.  */
unsigned bivs_not_used_in_addr;

/* Obstack for iv structure.  */
struct obstack iv_obstack;

/* Whether to consider just related and important candidates when replacing a
   use.  */
bool consider_all_candidates;

/* Are we optimizing for speed?  */
bool speed;

/* Whether the loop body includes any function calls.  */
bool body_includes_call;

/* Whether the loop body can only be exited via single exit.  */
bool loop_single_exit_p;

/* Whether the loop has doloop comparison use.  */
bool doloop_use_p;
658};

660/* An assignment of iv candidates to uses.  */

662class iv_ca
663{
664public:
/* The number of uses covered by the assignment.  */
unsigned upto;

/* Number of uses that cannot be expressed by the candidates in the set.  */
unsigned bad_groups;

/* Candidate assigned to a use, together with the related costs.  */
class cost_pair **cand_for_group;

/* Number of times each candidate is used.  */
unsigned *n_cand_uses;

/* The candidates used.  */
bitmap cands;

/* The number of candidates in the set.  */
unsigned n_cands;

/* The number of invariants needed, including both invariant variants and
   invariant expressions.  */
unsigned n_invs;

/* Total cost of expressing uses.  */
comp_cost cand_use_cost;

/* Total cost of candidates.  */
int64_t cand_cost;

/* Number of times each invariant variable is used.  */
unsigned *n_inv_var_uses;

/* Number of times each invariant expression is used.  */
unsigned *n_inv_expr_uses;

/* Total cost of the assignment.  */
comp_cost cost;
701};

703/* Difference of two iv candidate assignments.  */

705struct iv_ca_delta
706{
/* Changed group.  */
struct iv_group *group;

/* An old assignment (for rollback purposes).  */
class cost_pair *old_cp;

/* A new assignment.  */
class cost_pair *new_cp;

/* Next change in the list.  */
struct iv_ca_delta *next;
718};

720/* Bound on number of candidates below that all candidates are considered.  */

722#define CONSIDER_ALL_CANDIDATES_BOUND((unsigned) global_options.x_param_iv_consider_all_candidates_bound
) \
((unsigned) param_iv_consider_all_candidates_boundglobal_options.x_param_iv_consider_all_candidates_bound)

725/* If there are more iv occurrences, we just give up (it is quite unlikely that
 optimizing such a loop would help, and it would take ages).  */

728#define MAX_CONSIDERED_GROUPS((unsigned) global_options.x_param_iv_max_considered_uses) \
((unsigned) param_iv_max_considered_usesglobal_options.x_param_iv_max_considered_uses)

731/* If there are at most this number of ivs in the set, try removing unnecessary
 ivs from the set always.  */

734#define ALWAYS_PRUNE_CAND_SET_BOUND((unsigned) global_options.x_param_iv_always_prune_cand_set_bound
) \
((unsigned) param_iv_always_prune_cand_set_boundglobal_options.x_param_iv_always_prune_cand_set_bound)

737/* The list of trees for that the decl_rtl field must be reset is stored
 here.  */

740static vec<tree> decl_rtl_to_reset;

742static comp_cost force_expr_to_var_cost (tree, bool);

744/* The single loop exit if it dominates the latch, NULL otherwise.  */

746edge
747single_dom_exit (class loop *loop)
748{
edge exit = single_exit (loop);

if (!exit)
  return NULLnullptr;

if (!just_once_each_iteration_p (loop, exit->src))
  return NULLnullptr;

return exit;
758}

760/* Dumps information about the induction variable IV to FILE.  Don't dump
 variable's name if DUMP_NAME is FALSE.  The information is dumped with
 preceding spaces indicated by INDENT_LEVEL.  */

764void
765dump_iv (FILE *file, struct iv *iv, bool dump_name, unsigned indent_level)
766{
const char *p;
const char spaces[9] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '\0'};

if (indent_level > 4)
  indent_level = 4;
p = spaces + 8 - (indent_level << 1);

fprintf (file, "%sIV struct:\n", p);
if (iv->ssa_name && dump_name)
  {
    fprintf (file, "%s  SSA_NAME:\t", p);
    print_generic_expr (file, iv->ssa_name, TDF_SLIM);
    fprintf (file, "\n");
  }

fprintf (file, "%s  Type:\t", p);
print_generic_expr (file, TREE_TYPE (iv->base)((contains_struct_check ((iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 783, __FUNCTION__))->typed.type), TDF_SLIM);
fprintf (file, "\n");

fprintf (file, "%s  Base:\t", p);
print_generic_expr (file, iv->base, TDF_SLIM);
fprintf (file, "\n");

fprintf (file, "%s  Step:\t", p);
print_generic_expr (file, iv->step, TDF_SLIM);
fprintf (file, "\n");

if (iv->base_object)
  {
    fprintf (file, "%s  Object:\t", p);
    print_generic_expr (file, iv->base_object, TDF_SLIM);
    fprintf (file, "\n");
  }

fprintf (file, "%s  Biv:\t%c\n", p, iv->biv_p ? 'Y' : 'N');

fprintf (file, "%s  Overflowness wrto loop niter:\t%s\n",
  p, iv->no_overflow ? "No-overflow" : "Overflow");
805}

807/* Dumps information about the USE to FILE.  */

809void
810dump_use (FILE *file, struct iv_use *use)
811{
fprintf (file, "  Use %d.%d:\n", use->group_id, use->id);
fprintf (file, "    At stmt:\t");
print_gimple_stmt (file, use->stmt, 0);
fprintf (file, "    At pos:\t");
if (use->op_p)
  print_generic_expr (file, *use->op_p, TDF_SLIM);
fprintf (file, "\n");
dump_iv (file, use->iv, false, 2);
820}

822/* Dumps information about the uses to FILE.  */

824void
825dump_groups (FILE *file, struct ivopts_data *data)
826{
unsigned i, j;
struct iv_group *group;

for (i = 0; i < data->vgroups.length (); i++)
  {
    group = data->vgroups[i];
    fprintf (file, "Group %d:\n", group->id);
    if (group->type == USE_NONLINEAR_EXPR)
fprintf (file, "  Type:\tGENERIC\n");
    else if (group->type == USE_REF_ADDRESS)
fprintf (file, "  Type:\tREFERENCE ADDRESS\n");
    else if (group->type == USE_PTR_ADDRESS)
fprintf (file, "  Type:\tPOINTER ARGUMENT ADDRESS\n");
    else
{
 gcc_assert (group->type == USE_COMPARE)((void)(!(group->type == USE_COMPARE) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 842, __FUNCTION__), 0 : 0));
 fprintf (file, "  Type:\tCOMPARE\n");
}
    for (j = 0; j < group->vuses.length (); j++)
dump_use (file, group->vuses[j]);
  }
848}

850/* Dumps information about induction variable candidate CAND to FILE.  */

852void
853dump_cand (FILE *file, struct iv_cand *cand)
854{
struct iv *iv = cand->iv;

fprintf (file, "Candidate %d:\n", cand->id);
if (cand->inv_vars)
  {
    fprintf (file, "  Depend on inv.vars: ");
    dump_bitmap (file, cand->inv_vars);
  }
if (cand->inv_exprs)
  {
    fprintf (file, "  Depend on inv.exprs: ");
    dump_bitmap (file, cand->inv_exprs);
  }

if (cand->var_before)
  {
    fprintf (file, "  Var befor: ");
    print_generic_expr (file, cand->var_before, TDF_SLIM);
    fprintf (file, "\n");
  }
if (cand->var_after)
  {
    fprintf (file, "  Var after: ");
    print_generic_expr (file, cand->var_after, TDF_SLIM);
    fprintf (file, "\n");
  }

switch (cand->pos)
  {
  case IP_NORMAL:
    fprintf (file, "  Incr POS: before exit test\n");
    break;

  case IP_BEFORE_USE:
    fprintf (file, "  Incr POS: before use %d\n", cand->ainc_use->id);
    break;

  case IP_AFTER_USE:
    fprintf (file, "  Incr POS: after use %d\n", cand->ainc_use->id);
    break;

  case IP_END:
    fprintf (file, "  Incr POS: at end\n");
    break;

  case IP_ORIGINAL:
    fprintf (file, "  Incr POS: orig biv\n");
    break;
  }

dump_iv (file, iv, false, 1);
906}

908/* Returns the info for ssa version VER.  */

910static inline struct version_info *
911ver_info (struct ivopts_data *data, unsigned ver)
912{
return data->version_info + ver;
914}

916/* Returns the info for ssa name NAME.  */

918static inline struct version_info *
919name_info (struct ivopts_data *data, tree name)
920{
return ver_info (data, SSA_NAME_VERSION (name)(tree_check ((name), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 921, __FUNCTION__, (SSA_NAME)))->base.u.version);
922}

924/* Returns true if STMT is after the place where the IP_NORMAL ivs will be
 emitted in LOOP.  */

927static bool
928stmt_after_ip_normal_pos (class loop *loop, gimple *stmt)
929{
basic_block bb = ip_normal_pos (loop), sbb = gimple_bb (stmt);

gcc_assert (bb)((void)(!(bb) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 932, __FUNCTION__), 0 : 0));

if (sbb == loop->latch)
  return true;

if (sbb != bb)
  return false;

return stmt == last_stmt (bb);
941}

943/* Returns true if STMT if after the place where the original induction
 variable CAND is incremented.  If TRUE_IF_EQUAL is set, we return true
 if the positions are identical.  */

947static bool
948stmt_after_inc_pos (struct iv_cand *cand, gimple *stmt, bool true_if_equal)
949{
basic_block cand_bb = gimple_bb (cand->incremented_at);
basic_block stmt_bb = gimple_bb (stmt);

if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
  return false;

if (stmt_bb != cand_bb)
  return true;

if (true_if_equal
    && gimple_uid (stmt) == gimple_uid (cand->incremented_at))
  return true;
return gimple_uid (stmt) > gimple_uid (cand->incremented_at);
963}

965/* Returns true if STMT if after the place where the induction variable
 CAND is incremented in LOOP.  */

968static bool
969stmt_after_increment (class loop *loop, struct iv_cand *cand, gimple *stmt)
970{
switch (cand->pos)
  {
  case IP_END:
    return false;

  case IP_NORMAL:
    return stmt_after_ip_normal_pos (loop, stmt);

  case IP_ORIGINAL:
  case IP_AFTER_USE:
    return stmt_after_inc_pos (cand, stmt, false);

  case IP_BEFORE_USE:
    return stmt_after_inc_pos (cand, stmt, true);

  default:
    gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 987, __FUNCTION__));
  }
989}

991/* walk_tree callback for contains_abnormal_ssa_name_p.  */

993static tree
994contains_abnormal_ssa_name_p_1 (tree *tp, int *walk_subtrees, void *)
995{
if (TREE_CODE (*tp)((enum tree_code) (*tp)->base.code) == SSA_NAME
    && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*tp)(tree_check ((*tp), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 997, __FUNCTION__, (SSA_NAME)))->base.asm_written_flag)
  return *tp;

if (!EXPR_P (*tp)((tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (*tp)->base.code))]) >= tcc_reference &&
 (tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (*tp)->base.code))]) <= tcc_expression))
  *walk_subtrees = 0;

return NULL_TREE(tree) nullptr;
1004}

1006/* Returns true if EXPR contains a ssa name that occurs in an
 abnormal phi node.  */

1009bool
1010contains_abnormal_ssa_name_p (tree expr)
1011{
return walk_tree_without_duplicateswalk_tree_without_duplicates_1 (&expr, contains_abnormal_ssa_name_p_1
, nullptr, nullptr)
  (&expr, contains_abnormal_ssa_name_p_1, NULL)walk_tree_without_duplicates_1 (&expr, contains_abnormal_ssa_name_p_1
, nullptr, nullptr) != NULL_TREE(tree) nullptr;
1014}

1016/*  Returns the structure describing number of iterations determined from
  EXIT of DATA->current_loop, or NULL if something goes wrong.  */

1019static class tree_niter_desc *
1020niter_for_exit (struct ivopts_data *data, edge exit)
1021{
class tree_niter_desc *desc;
tree_niter_desc **slot;

if (!data->niters)
  {
    data->niters = new hash_map<edge, tree_niter_desc *>;
    slot = NULLnullptr;
  }
else
  slot = data->niters->get (exit);

if (!slot)
  {
    /* Try to determine number of iterations.  We cannot safely work with ssa
names that appear in phi nodes on abnormal edges, so that we do not
create overlapping life ranges for them (PR 27283).  */
    desc = XNEW (class tree_niter_desc)((class tree_niter_desc *) xmalloc (sizeof (class tree_niter_desc
)));
    if (!number_of_iterations_exit (data->current_loop,
		      exit, desc, true)
   	  || contains_abnormal_ssa_name_p (desc->niter))
{
 XDELETE (desc)free ((void*) (desc));
 desc = NULLnullptr;
}
    data->niters->put (exit, desc);
  }
else
  desc = *slot;

return desc;
1052}

1054/* Returns the structure describing number of iterations determined from
 single dominating exit of DATA->current_loop, or NULL if something
 goes wrong.  */

1058static class tree_niter_desc *
1059niter_for_single_dom_exit (struct ivopts_data *data)
1060{
edge exit = single_dom_exit (data->current_loop);

if (!exit)
  return NULLnullptr;

return niter_for_exit (data, exit);
1067}

1069/* Initializes data structures used by the iv optimization pass, stored
 in DATA.  */

1072static void
1073tree_ssa_iv_optimize_init (struct ivopts_data *data)
1074{
data->version_info_size = 2 * num_ssa_names(vec_safe_length ((cfun + 0)->gimple_df->ssa_names));
data->version_info = XCNEWVEC (struct version_info, data->version_info_size)((struct version_info *) xcalloc ((data->version_info_size
), sizeof (struct version_info)));
data->relevant = BITMAP_ALLOCbitmap_alloc (NULLnullptr);
data->important_candidates = BITMAP_ALLOCbitmap_alloc (NULLnullptr);
data->max_inv_var_id = 0;
data->max_inv_expr_id = 0;
data->niters = NULLnullptr;
data->vgroups.create (20);
data->vcands.create (20);
data->inv_expr_tab = new hash_table<iv_inv_expr_hasher> (10);
data->name_expansion_cache = NULLnullptr;
data->base_object_map = NULLnullptr;
data->iv_common_cand_tab = new hash_table<iv_common_cand_hasher> (10);
data->iv_common_cands.create (20);
decl_rtl_to_reset.create (20);
gcc_obstack_init (&data->iv_obstack)_obstack_begin (((&data->iv_obstack)), (memory_block_pool
::block_size), (0), (mempool_obstack_chunk_alloc), (mempool_obstack_chunk_free
));
1091}

1093/* walk_tree callback for determine_base_object.  */

1095static tree
1096determine_base_object_1 (tree *tp, int *walk_subtrees, void *wdata)
1097{
tree_code code = TREE_CODE (*tp)((enum tree_code) (*tp)->base.code);
tree obj = NULL_TREE(tree) nullptr;
if (code == ADDR_EXPR)
  {
    tree base = get_base_address (TREE_OPERAND (*tp, 0)(*((const_cast<tree*> (tree_operand_check ((*tp), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1102, __FUNCTION__))))));
    if (!base)
obj = *tp;
    else if (TREE_CODE (base)((enum tree_code) (base)->base.code) != MEM_REF)
obj = fold_convert (ptr_type_node, build_fold_addr_expr (base))fold_convert_loc (((location_t) 0), global_trees[TI_PTR_TYPE]
, build_fold_addr_expr_loc (((location_t) 0), (base)));
  }
else if (code == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*tp))(((enum tree_code) (((contains_struct_check ((*tp), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1108, __FUNCTION__))->typed.type))->base.code) == POINTER_TYPE
 || ((enum tree_code) (((contains_struct_check ((*tp), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1108, __FUNCTION__))->typed.type))->base.code) == REFERENCE_TYPE
))
obj = fold_convert (ptr_type_node, *tp)fold_convert_loc (((location_t) 0), global_trees[TI_PTR_TYPE]
, *tp);

if (!obj)
  {
    if (!EXPR_P (*tp)((tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (*tp)->base.code))]) >= tcc_reference &&
 (tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (*tp)->base.code))]) <= tcc_expression))
*walk_subtrees = 0;

    return NULL_TREE(tree) nullptr;
  }
/* Record special node for multiple base objects and stop.  */
if (*static_cast<tree *> (wdata))
  {
    *static_cast<tree *> (wdata) = integer_zero_nodeglobal_trees[TI_INTEGER_ZERO];
    return integer_zero_nodeglobal_trees[TI_INTEGER_ZERO];
  }
/* Record the base object and continue looking.  */
*static_cast<tree *> (wdata) = obj;
return NULL_TREE(tree) nullptr;
1127}

1129/* Returns a memory object to that EXPR points with caching.  Return NULL if we
 are able to determine that it does not point to any such object; specially
 return integer_zero_node if EXPR contains multiple base objects.  */

1133static tree
1134determine_base_object (struct ivopts_data *data, tree expr)
1135{
tree *slot, obj = NULL_TREE(tree) nullptr;
if (data->base_object_map)
  {
    if ((slot = data->base_object_map->get(expr)) != NULLnullptr)
return *slot;
  }
else
  data->base_object_map = new hash_map<tree, tree>;

(void) walk_tree_without_duplicates (&expr, determine_base_object_1, &obj)walk_tree_without_duplicates_1 (&expr, determine_base_object_1
, &obj, nullptr);
data->base_object_map->put (expr, obj);
return obj;
1148}

1150/* Return true if address expression with non-DECL_P operand appears
 in EXPR.  */

1153static bool
1154contain_complex_addr_expr (tree expr)
1155{
bool res = false;

STRIP_NOPS (expr)(expr) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((expr)))));
switch (TREE_CODE (expr)((enum tree_code) (expr)->base.code))
  {
  case POINTER_PLUS_EXPR:
  case PLUS_EXPR:
  case MINUS_EXPR:
    res |= contain_complex_addr_expr (TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1164, __FUNCTION__))))));
    res |= contain_complex_addr_expr (TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1165, __FUNCTION__))))));
    break;

  case ADDR_EXPR:
    return (!DECL_P (TREE_OPERAND (expr, 0))(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) ((*((const_cast<tree*> (tree_operand_check ((expr), (
0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1169, __FUNCTION__))))))->base.code))] == tcc_declaration
));

  default:
    return false;
  }

return res;
1176}

1178/* Allocates an induction variable with given initial value BASE and step STEP
 for loop LOOP.  NO_OVERFLOW implies the iv doesn't overflow.  */

1181static struct iv *
1182alloc_iv (struct ivopts_data *data, tree base, tree step,
 bool no_overflow = false)
1184{
tree expr = base;
struct iv *iv = (struct iv*) obstack_alloc (&data->iv_obstack,__extension__ ({ struct obstack *__h = (&data->iv_obstack
); __extension__ ({ struct obstack *__o = (__h); size_t __len
 = ((sizeof (struct iv))); if (__extension__ ({ struct obstack
 const *__o1 = (__o); (size_t) (__o1->chunk_limit - __o1->
next_free); }) < __len) _obstack_newchunk (__o, __len); ((
void) ((__o)->next_free += (__len))); }); __extension__ ({
 struct obstack *__o1 = (__h); void *__value = (void *) __o1->
object_base; if (__o1->next_free == __value) __o1->maybe_empty_object
 = 1; __o1->next_free = (sizeof (ptrdiff_t) < sizeof (void
 *) ? ((__o1->object_base) + (((__o1->next_free) - (__o1
->object_base) + (__o1->alignment_mask)) & ~(__o1->
alignment_mask))) : (char *) (((ptrdiff_t) (__o1->next_free
) + (__o1->alignment_mask)) & ~(__o1->alignment_mask
))); if ((size_t) (__o1->next_free - (char *) __o1->chunk
) > (size_t) (__o1->chunk_limit - (char *) __o1->chunk
)) __o1->next_free = __o1->chunk_limit; __o1->object_base
 = __o1->next_free; __value; }); })
			      sizeof (struct iv))__extension__ ({ struct obstack *__h = (&data->iv_obstack
); __extension__ ({ struct obstack *__o = (__h); size_t __len
 = ((sizeof (struct iv))); if (__extension__ ({ struct obstack
 const *__o1 = (__o); (size_t) (__o1->chunk_limit - __o1->
next_free); }) < __len) _obstack_newchunk (__o, __len); ((
void) ((__o)->next_free += (__len))); }); __extension__ ({
 struct obstack *__o1 = (__h); void *__value = (void *) __o1->
object_base; if (__o1->next_free == __value) __o1->maybe_empty_object
 = 1; __o1->next_free = (sizeof (ptrdiff_t) < sizeof (void
 *) ? ((__o1->object_base) + (((__o1->next_free) - (__o1
->object_base) + (__o1->alignment_mask)) & ~(__o1->
alignment_mask))) : (char *) (((ptrdiff_t) (__o1->next_free
) + (__o1->alignment_mask)) & ~(__o1->alignment_mask
))); if ((size_t) (__o1->next_free - (char *) __o1->chunk
) > (size_t) (__o1->chunk_limit - (char *) __o1->chunk
)) __o1->next_free = __o1->chunk_limit; __o1->object_base
 = __o1->next_free; __value; }); });
gcc_assert (step != NULL_TREE)((void)(!(step != (tree) nullptr) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1188, __FUNCTION__), 0 : 0));

/* Lower address expression in base except ones with DECL_P as operand.
   By doing this:
     1) More accurate cost can be computed for address expressions;
     2) Duplicate candidates won't be created for bases in different
 forms, like &a[0] and &a.  */
STRIP_NOPS (expr)(expr) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((expr)))));
if ((TREE_CODE (expr)((enum tree_code) (expr)->base.code) == ADDR_EXPR && !DECL_P (TREE_OPERAND (expr, 0))(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) ((*((const_cast<tree*> (tree_operand_check ((expr), (
0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1196, __FUNCTION__))))))->base.code))] == tcc_declaration
))
    || contain_complex_addr_expr (expr))
  {
    aff_tree comb;
    tree_to_aff_combination (expr, TREE_TYPE (expr)((contains_struct_check ((expr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1200, __FUNCTION__))->typed.type), &comb);
    base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb))fold_convert_loc (((location_t) 0), ((contains_struct_check (
(base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1201, __FUNCTION__))->typed.type), aff_combination_to_tree
 (&comb));
  }

iv->base = base;
iv->base_object = determine_base_object (data, base);
iv->step = step;
iv->biv_p = false;
iv->nonlin_use = NULLnullptr;
iv->ssa_name = NULL_TREE(tree) nullptr;
if (!no_overflow
     && !iv_can_overflow_p (data->current_loop, TREE_TYPE (base)((contains_struct_check ((base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1211, __FUNCTION__))->typed.type),
	      base, step))
  no_overflow = true;
iv->no_overflow = no_overflow;
iv->have_address_use = false;

return iv;
1218}

1220/* Sets STEP and BASE for induction variable IV.  NO_OVERFLOW implies the IV
 doesn't overflow.  */

1223static void
1224set_iv (struct ivopts_data *data, tree iv, tree base, tree step,
bool no_overflow)
1226{
struct version_info *info = name_info (data, iv);

gcc_assert (!info->iv)((void)(!(!info->iv) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1229, __FUNCTION__), 0 : 0));

bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv)(tree_check ((iv), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1231, __FUNCTION__, (SSA_NAME)))->base.u.version);
info->iv = alloc_iv (data, base, step, no_overflow);
info->iv->ssa_name = iv;
1234}

1236/* Finds induction variable declaration for VAR.  */

1238static struct iv *
1239get_iv (struct ivopts_data *data, tree var)
1240{
basic_block bb;
tree type = TREE_TYPE (var)((contains_struct_check ((var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1242, __FUNCTION__))->typed.type);

if (!POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE)
    && !INTEGRAL_TYPE_P (type)(((enum tree_code) (type)->base.code) == ENUMERAL_TYPE || (
(enum tree_code) (type)->base.code) == BOOLEAN_TYPE || ((enum
 tree_code) (type)->base.code) == INTEGER_TYPE))
  return NULLnullptr;

if (!name_info (data, var)->iv)
  {
    bb = gimple_bb (SSA_NAME_DEF_STMT (var)(tree_check ((var), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1250, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt);

    if (!bb
 || !flow_bb_inside_loop_p (data->current_loop, bb))
{
 if (POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE))
   type = sizetypesizetype_tab[(int) stk_sizetype];
 set_iv (data, var, var, build_int_cst (type, 0), true);
}
  }

return name_info (data, var)->iv;
1262}

1264/* Return the first non-invariant ssa var found in EXPR.  */

1266static tree
1267extract_single_var_from_expr (tree expr)
1268{
int i, n;
tree tmp;
enum tree_code code;

if (!expr || is_gimple_min_invariant (expr))
  return NULLnullptr;

code = TREE_CODE (expr)((enum tree_code) (expr)->base.code);
if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))((tree_code_type_tmpl <0>::tree_code_type[(int) (code)]
) >= tcc_reference && (tree_code_type_tmpl <0>
::tree_code_type[(int) (code)]) <= tcc_expression))
  {
    n = TREE_OPERAND_LENGTH (expr)tree_operand_length (expr);
    for (i = 0; i < n; i++)
{
 tmp = extract_single_var_from_expr (TREE_OPERAND (expr, i)(*((const_cast<tree*> (tree_operand_check ((expr), (i),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1282, __FUNCTION__))))));

 if (tmp)
   return tmp;
}
  }
return (TREE_CODE (expr)((enum tree_code) (expr)->base.code) == SSA_NAME) ? expr : NULLnullptr;
1289}

1291/* Finds basic ivs.  */

1293static bool
1294find_bivs (struct ivopts_data *data)
1295{
gphi *phi;
affine_iv iv;
tree step, type, base, stop;
bool found = false;
class loop *loop = data->current_loop;
gphi_iterator psi;

for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
  {
    phi = psi.phi ();

    if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi))(tree_check ((get_def_from_ptr (gimple_phi_result_ptr (phi)))
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1307, __FUNCTION__, (SSA_NAME)))->base.asm_written_flag)
continue;

    if (virtual_operand_p (PHI_RESULT (phi)get_def_from_ptr (gimple_phi_result_ptr (phi))))
continue;

    if (!simple_iv (loop, loop, PHI_RESULT (phi)get_def_from_ptr (gimple_phi_result_ptr (phi)), &iv, true))
continue;

    if (integer_zerop (iv.step))
continue;

    step = iv.step;
    base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop))gimple_phi_arg_def (((phi)), ((loop_preheader_edge (loop))->
dest_idx));
    /* Stop expanding iv base at the first ssa var referred by iv step.
Ideally we should stop at any ssa var, because that's expensive
and unusual to happen, we just do it on the first one.

See PR64705 for the rationale.  */
    stop = extract_single_var_from_expr (step);
    base = expand_simple_operations (base, stop);
    if (contains_abnormal_ssa_name_p (base)
 || contains_abnormal_ssa_name_p (step))
continue;

    type = TREE_TYPE (PHI_RESULT (phi))((contains_struct_check ((get_def_from_ptr (gimple_phi_result_ptr
 (phi))), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1332, __FUNCTION__))->typed.type);
    base = fold_convert (type, base)fold_convert_loc (((location_t) 0), type, base);
    if (step)
{
 if (POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE))
   step = convert_to_ptrofftype (step)convert_to_ptrofftype_loc (((location_t) 0), step);
 else
   step = fold_convert (type, step)fold_convert_loc (((location_t) 0), type, step);
}

    set_iv (data, PHI_RESULT (phi)get_def_from_ptr (gimple_phi_result_ptr (phi)), base, step, iv.no_overflow);
    found = true;
  }

return found;
1347}

1349/* Marks basic ivs.  */

1351static void
1352mark_bivs (struct ivopts_data *data)
1353{
gphi *phi;
gimple *def;
tree var;
struct iv *iv, *incr_iv;
class loop *loop = data->current_loop;
basic_block incr_bb;
gphi_iterator psi;

data->bivs_not_used_in_addr = 0;
for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
  {
    phi = psi.phi ();

    iv = get_iv (data, PHI_RESULT (phi)get_def_from_ptr (gimple_phi_result_ptr (phi)));
    if (!iv)
continue;

    var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop))gimple_phi_arg_def (((phi)), ((loop_latch_edge (loop))->dest_idx
));
    def = SSA_NAME_DEF_STMT (var)(tree_check ((var), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1372, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
    /* Don't mark iv peeled from other one as biv.  */
    if (def
 && gimple_code (def) == GIMPLE_PHI
 && gimple_bb (def) == loop->header)
continue;

    incr_iv = get_iv (data, var);
    if (!incr_iv)
continue;

    /* If the increment is in the subloop, ignore it.  */
    incr_bb = gimple_bb (SSA_NAME_DEF_STMT (var)(tree_check ((var), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1384, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt);
    if (incr_bb->loop_father != data->current_loop
 || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
continue;

    iv->biv_p = true;
    incr_iv->biv_p = true;
    if (iv->no_overflow)
data->bivs_not_used_in_addr++;
    if (incr_iv->no_overflow)
data->bivs_not_used_in_addr++;
  }
1396}

1398/* Checks whether STMT defines a linear induction variable and stores its
 parameters to IV.  */

1401static bool
1402find_givs_in_stmt_scev (struct ivopts_data *data, gimple *stmt, affine_iv *iv)
1403{
tree lhs, stop;
class loop *loop = data->current_loop;

iv->base = NULL_TREE(tree) nullptr;
iv->step = NULL_TREE(tree) nullptr;

if (gimple_code (stmt) != GIMPLE_ASSIGN)
  return false;

lhs = gimple_assign_lhs (stmt);
if (TREE_CODE (lhs)((enum tree_code) (lhs)->base.code) != SSA_NAME)
  return false;

if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
  return false;

/* Stop expanding iv base at the first ssa var referred by iv step.
   Ideally we should stop at any ssa var, because that's expensive
   and unusual to happen, we just do it on the first one.

   See PR64705 for the rationale.  */
stop = extract_single_var_from_expr (iv->step);
iv->base = expand_simple_operations (iv->base, stop);
if (contains_abnormal_ssa_name_p (iv->base)
    || contains_abnormal_ssa_name_p (iv->step))
  return false;

/* If STMT could throw, then do not consider STMT as defining a GIV.
   While this will suppress optimizations, we cannot safely delete this
   GIV and associated statements, even if it appears it is not used.  */
if (stmt_could_throw_p (cfun(cfun + 0), stmt))
  return false;

return true;
1438}

1440/* Finds general ivs in statement STMT.  */

1442static void
1443find_givs_in_stmt (struct ivopts_data *data, gimple *stmt)
1444{
affine_iv iv;

if (!find_givs_in_stmt_scev (data, stmt, &iv))
  return;

set_iv (data, gimple_assign_lhs (stmt), iv.base, iv.step, iv.no_overflow);
1451}

1453/* Finds general ivs in basic block BB.  */

1455static void
1456find_givs_in_bb (struct ivopts_data *data, basic_block bb)
1457{
gimple_stmt_iterator bsi;

for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
  find_givs_in_stmt (data, gsi_stmt (bsi));
1462}

1464/* Finds general ivs.  */

1466static void
1467find_givs (struct ivopts_data *data, basic_block *body)
1468{
class loop *loop = data->current_loop;
unsigned i;

for (i = 0; i < loop->num_nodes; i++)
  find_givs_in_bb (data, body[i]);
1474}

1476/* For each ssa name defined in LOOP determines whether it is an induction
 variable and if so, its initial value and step.  */

1479static bool
1480find_induction_variables (struct ivopts_data *data, basic_block *body)
1481{
unsigned i;
bitmap_iterator bi;

if (!find_bivs (data))
  return false;

find_givs (data, body);
mark_bivs (data);

if (dump_file && (dump_flags & TDF_DETAILS))
  {
    class tree_niter_desc *niter = niter_for_single_dom_exit (data);

    if (niter)
{
 fprintf (dump_file, "  number of iterations ");
 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
 if (!integer_zerop (niter->may_be_zero))
   {
     fprintf (dump_file, "; zero if ");
     print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
   }
 fprintf (dump_file, "\n");
};

    fprintf (dump_file, "\n<Induction Vars>:\n");
    EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)for (bmp_iter_set_init (&(bi), (data->relevant), (0), &
(i)); bmp_iter_set (&(bi), &(i)); bmp_iter_next (&
(bi), &(i)))
{
 struct version_info *info = ver_info (data, i);
 if (info->iv && info->iv->step && !integer_zerop (info->iv->step))
   dump_iv (dump_file, ver_info (data, i)->iv, true, 0);
}
  }

return true;
1517}

1519/* Records a use of TYPE at *USE_P in STMT whose value is IV in GROUP.
 For address type use, ADDR_BASE is the stripped IV base, ADDR_OFFSET
 is the const offset stripped from IV base and MEM_TYPE is the type
 of the memory being addressed.  For uses of other types, ADDR_BASE
 and ADDR_OFFSET are zero by default and MEM_TYPE is NULL_TREE.  */

1525static struct iv_use *
1526record_use (struct iv_group *group, tree *use_p, struct iv *iv,
   gimple *stmt, enum use_type type, tree mem_type,
   tree addr_base, poly_uint64 addr_offset)
1529{
struct iv_use *use = XCNEW (struct iv_use)((struct iv_use *) xcalloc (1, sizeof (struct iv_use)));

use->id = group->vuses.length ();
use->group_id = group->id;
use->type = type;
use->mem_type = mem_type;
use->iv = iv;
use->stmt = stmt;
use->op_p = use_p;
use->addr_base = addr_base;
use->addr_offset = addr_offset;

group->vuses.safe_push (use);
return use;
1544}

1546/* Checks whether OP is a loop-level invariant and if so, records it.
 NONLINEAR_USE is true if the invariant is used in a way we do not
 handle specially.  */

1550static void
1551record_invariant (struct ivopts_data *data, tree op, bool nonlinear_use)
1552{
basic_block bb;
struct version_info *info;

if (TREE_CODE (op)((enum tree_code) (op)->base.code) != SSA_NAME
    || virtual_operand_p (op))
  return;

bb = gimple_bb (SSA_NAME_DEF_STMT (op)(tree_check ((op), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1560, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt);
if (bb
    && flow_bb_inside_loop_p (data->current_loop, bb))
  return;

info = name_info (data, op);
info->name = op;
info->has_nonlin_use |= nonlinear_use;
if (!info->inv_id)
  info->inv_id = ++data->max_inv_var_id;
bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op)(tree_check ((op), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1570, __FUNCTION__, (SSA_NAME)))->base.u.version);
1571}

1573/* Record a group of TYPE.  */

1575static struct iv_group *
1576record_group (struct ivopts_data *data, enum use_type type)
1577{
struct iv_group *group = XCNEW (struct iv_group)((struct iv_group *) xcalloc (1, sizeof (struct iv_group)));

group->id = data->vgroups.length ();
group->type = type;
group->related_cands = BITMAP_ALLOCbitmap_alloc (NULLnullptr);
group->vuses.create (1);
group->doloop_p = false;

data->vgroups.safe_push (group);
return group;
1588}

1590/* Record a use of TYPE at *USE_P in STMT whose value is IV in a group.
 New group will be created if there is no existing group for the use.
 MEM_TYPE is the type of memory being addressed, or NULL if this
 isn't an address reference.  */

1595static struct iv_use *
1596record_group_use (struct ivopts_data *data, tree *use_p,
  struct iv *iv, gimple *stmt, enum use_type type,
  tree mem_type)
1599{
tree addr_base = NULLnullptr;
struct iv_group *group = NULLnullptr;
poly_uint64 addr_offset = 0;

/* Record non address type use in a new group.  */
if (address_p (type))
  {
    unsigned int i;

    addr_base = strip_offset (iv->base, &addr_offset);
    for (i = 0; i < data->vgroups.length (); i++)
{
 struct iv_use *use;

 group = data->vgroups[i];
 use = group->vuses[0];
 if (!address_p (use->type))
   continue;

 /* Check if it has the same stripped base and step.  */
 if (operand_equal_p (iv->base_object, use->iv->base_object, 0)
     && operand_equal_p (iv->step, use->iv->step, 0)
     && operand_equal_p (addr_base, use->addr_base, 0))
   break;
}
    if (i == data->vgroups.length ())
group = NULLnullptr;
  }

if (!group)
  group = record_group (data, type);

return record_use (group, use_p, iv, stmt, type, mem_type,
     addr_base, addr_offset);
1634}

1636/* Checks whether the use OP is interesting and if so, records it.  */

1638static struct iv_use *
1639find_interesting_uses_op (struct ivopts_data *data, tree op)
1640{
struct iv *iv;
gimple *stmt;
struct iv_use *use;

if (TREE_CODE (op)((enum tree_code) (op)->base.code) != SSA_NAME)
  return NULLnullptr;

iv = get_iv (data, op);
if (!iv)
  return NULLnullptr;

if (iv->nonlin_use)
  {
    gcc_assert (iv->nonlin_use->type == USE_NONLINEAR_EXPR)((void)(!(iv->nonlin_use->type == USE_NONLINEAR_EXPR) ?
 fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1654, __FUNCTION__), 0 : 0));
    return iv->nonlin_use;
  }

if (integer_zerop (iv->step))
  {
    record_invariant (data, op, true);
    return NULLnullptr;
  }

stmt = SSA_NAME_DEF_STMT (op)(tree_check ((op), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1664, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
gcc_assert (gimple_code (stmt) == GIMPLE_PHI || is_gimple_assign (stmt))((void)(!(gimple_code (stmt) == GIMPLE_PHI || is_gimple_assign
 (stmt)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1665, __FUNCTION__), 0 : 0));

use = record_group_use (data, NULLnullptr, iv, stmt, USE_NONLINEAR_EXPR, NULL_TREE(tree) nullptr);
iv->nonlin_use = use;
return use;
1670}

1672/* Indicate how compare type iv_use can be handled.  */
1673enum comp_iv_rewrite
1674{
COMP_IV_NA,
/* We may rewrite compare type iv_use by expressing value of the iv_use.  */
COMP_IV_EXPR,
/* We may rewrite compare type iv_uses on both sides of comparison by
   expressing value of each iv_use.  */
COMP_IV_EXPR_2,
/* We may rewrite compare type iv_use by expressing value of the iv_use
   or by eliminating it with other iv_cand.  */
COMP_IV_ELIM
1684};

1686/* Given a condition in statement STMT, checks whether it is a compare
 of an induction variable and an invariant.  If this is the case,
 CONTROL_VAR is set to location of the iv, BOUND to the location of
 the invariant, IV_VAR and IV_BOUND are set to the corresponding
 induction variable descriptions, and true is returned.  If this is not
 the case, CONTROL_VAR and BOUND are set to the arguments of the
 condition and false is returned.  */

1694static enum comp_iv_rewrite
1695extract_cond_operands (struct ivopts_data *data, gimple *stmt,
       tree **control_var, tree **bound,
       struct iv **iv_var, struct iv **iv_bound)
1698{
/* The objects returned when COND has constant operands.  */
static struct iv const_iv;
static tree zero;
tree *op0 = &zero, *op1 = &zero;
struct iv *iv0 = &const_iv, *iv1 = &const_iv;
enum comp_iv_rewrite rewrite_type = COMP_IV_NA;

if (gimple_code (stmt) == GIMPLE_COND)
  {
    gcond *cond_stmt = as_a <gcond *> (stmt);
    op0 = gimple_cond_lhs_ptr (cond_stmt);
    op1 = gimple_cond_rhs_ptr (cond_stmt);
  }
else
  {
    op0 = gimple_assign_rhs1_ptr (stmt);
    op1 = gimple_assign_rhs2_ptr (stmt);
  }

zero = integer_zero_nodeglobal_trees[TI_INTEGER_ZERO];
const_iv.step = integer_zero_nodeglobal_trees[TI_INTEGER_ZERO];

if (TREE_CODE (*op0)((enum tree_code) (*op0)->base.code) == SSA_NAME)
  iv0 = get_iv (data, *op0);
if (TREE_CODE (*op1)((enum tree_code) (*op1)->base.code) == SSA_NAME)
  iv1 = get_iv (data, *op1);

/* If both sides of comparison are IVs.  We can express ivs on both end.  */
if (iv0 && iv1 && !integer_zerop (iv0->step) && !integer_zerop (iv1->step))
  {
    rewrite_type = COMP_IV_EXPR_2;
    goto end;
  }

/* If none side of comparison is IV.  */
if ((!iv0 || integer_zerop (iv0->step))
    && (!iv1 || integer_zerop (iv1->step)))
  goto end;

/* Control variable may be on the other side.  */
if (!iv0 || integer_zerop (iv0->step))
  {
    std::swap (op0, op1);
    std::swap (iv0, iv1);
  }
/* If one side is IV and the other side isn't loop invariant.  */
if (!iv1)
  rewrite_type = COMP_IV_EXPR;
/* If one side is IV and the other side is loop invariant.  */
else if (!integer_zerop (iv0->step) && integer_zerop (iv1->step))
  rewrite_type = COMP_IV_ELIM;

1751end:
if (control_var)
  *control_var = op0;
if (iv_var)
  *iv_var = iv0;
if (bound)
  *bound = op1;
if (iv_bound)
  *iv_bound = iv1;

return rewrite_type;
1762}

1764/* Checks whether the condition in STMT is interesting and if so,
 records it.  */

1767static void
1768find_interesting_uses_cond (struct ivopts_data *data, gimple *stmt)
1769{
tree *var_p, *bound_p;
struct iv *var_iv, *bound_iv;
enum comp_iv_rewrite ret;

ret = extract_cond_operands (data, stmt,
	       &var_p, &bound_p, &var_iv, &bound_iv);
if (ret == COMP_IV_NA)
  {
    find_interesting_uses_op (data, *var_p);
    find_interesting_uses_op (data, *bound_p);
    return;
  }

record_group_use (data, var_p, var_iv, stmt, USE_COMPARE, NULL_TREE(tree) nullptr);
/* Record compare type iv_use for iv on the other side of comparison.  */
if (ret == COMP_IV_EXPR_2)
  record_group_use (data, bound_p, bound_iv, stmt, USE_COMPARE, NULL_TREE(tree) nullptr);
1787}

1789/* Returns the outermost loop EXPR is obviously invariant in
 relative to the loop LOOP, i.e. if all its operands are defined
 outside of the returned loop.  Returns NULL if EXPR is not
 even obviously invariant in LOOP.  */

1794class loop *
1795outermost_invariant_loop_for_expr (class loop *loop, tree expr)
1796{
basic_block def_bb;
unsigned i, len;

if (is_gimple_min_invariant (expr))
  return current_loops((cfun + 0)->x_current_loops)->tree_root;

if (TREE_CODE (expr)((enum tree_code) (expr)->base.code) == SSA_NAME)
  {
    def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr)(tree_check ((expr), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1805, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt);
    if (def_bb)
{
 if (flow_bb_inside_loop_p (loop, def_bb))
   return NULLnullptr;
 return superloop_at_depth (loop,
		     loop_depth (def_bb->loop_father) + 1);
}

    return current_loops((cfun + 0)->x_current_loops)->tree_root;
  }

if (!EXPR_P (expr)((tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (expr)->base.code))]) >= tcc_reference &&
 (tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (expr)->base.code))]) <= tcc_expression))
  return NULLnullptr;

unsigned maxdepth = 0;
len = TREE_OPERAND_LENGTH (expr)tree_operand_length (expr);
for (i = 0; i < len; i++)
  {
    class loop *ivloop;
    if (!TREE_OPERAND (expr, i)(*((const_cast<tree*> (tree_operand_check ((expr), (i),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1825, __FUNCTION__))))))
continue;

    ivloop = outermost_invariant_loop_for_expr (loop, TREE_OPERAND (expr, i)(*((const_cast<tree*> (tree_operand_check ((expr), (i),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1828, __FUNCTION__))))));
    if (!ivloop)
return NULLnullptr;
    maxdepth = MAX (maxdepth, loop_depth (ivloop))((maxdepth) > (loop_depth (ivloop)) ? (maxdepth) : (loop_depth
 (ivloop)));
  }

return superloop_at_depth (loop, maxdepth);
1835}

1837/* Returns true if expression EXPR is obviously invariant in LOOP,
 i.e. if all its operands are defined outside of the LOOP.  LOOP
 should not be the function body.  */

1841bool
1842expr_invariant_in_loop_p (class loop *loop, tree expr)
1843{
basic_block def_bb;
unsigned i, len;

gcc_assert (loop_depth (loop) > 0)((void)(!(loop_depth (loop) > 0) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1847, __FUNCTION__), 0 : 0));

if (is_gimple_min_invariant (expr))
  return true;

if (TREE_CODE (expr)((enum tree_code) (expr)->base.code) == SSA_NAME)
  {
    def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr)(tree_check ((expr), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1854, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt);
    if (def_bb
 && flow_bb_inside_loop_p (loop, def_bb))
return false;

    return true;
  }

if (!EXPR_P (expr)((tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (expr)->base.code))]) >= tcc_reference &&
 (tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (expr)->base.code))]) <= tcc_expression))
  return false;

len = TREE_OPERAND_LENGTH (expr)tree_operand_length (expr);
for (i = 0; i < len; i++)
  if (TREE_OPERAND (expr, i)(*((const_cast<tree*> (tree_operand_check ((expr), (i),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1867, __FUNCTION__)))))
&& !expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i)(*((const_cast<tree*> (tree_operand_check ((expr), (i),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1868, __FUNCTION__)))))))
    return false;

return true;
1872}

1874/* Given expression EXPR which computes inductive values with respect
 to loop recorded in DATA, this function returns biv from which EXPR
 is derived by tracing definition chains of ssa variables in EXPR.  */

1878static struct iv*
1879find_deriving_biv_for_expr (struct ivopts_data *data, tree expr)
1880{
struct iv *iv;
unsigned i, n;
tree e2, e1;
enum tree_code code;
gimple *stmt;

if (expr == NULL_TREE(tree) nullptr)
  return NULLnullptr;

if (is_gimple_min_invariant (expr))
  return NULLnullptr;

code = TREE_CODE (expr)((enum tree_code) (expr)->base.code);
if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))((tree_code_type_tmpl <0>::tree_code_type[(int) (code)]
) >= tcc_reference && (tree_code_type_tmpl <0>
::tree_code_type[(int) (code)]) <= tcc_expression))
  {
    n = TREE_OPERAND_LENGTH (expr)tree_operand_length (expr);
    for (i = 0; i < n; i++)
{
 iv = find_deriving_biv_for_expr (data, TREE_OPERAND (expr, i)(*((const_cast<tree*> (tree_operand_check ((expr), (i),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1899, __FUNCTION__))))));
 if (iv)
   return iv;
}
  }

/* Stop if it's not ssa name.  */
if (code != SSA_NAME)
  return NULLnullptr;

iv = get_iv (data, expr);
if (!iv || integer_zerop (iv->step))
  return NULLnullptr;
else if (iv->biv_p)
  return iv;

stmt = SSA_NAME_DEF_STMT (expr)(tree_check ((expr), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1915, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
if (gphi *phi = dyn_cast <gphi *> (stmt))
  {
    ssa_op_iter iter;
    use_operand_p use_p;
    basic_block phi_bb = gimple_bb (phi);

    /* Skip loop header PHI that doesn't define biv.  */
    if (phi_bb->loop_father == data->current_loop)
return NULLnullptr;

    if (virtual_operand_p (gimple_phi_result (phi)))
return NULLnullptr;

    FOR_EACH_PHI_ARG (use_p, phi, iter, SSA_OP_USE)for ((use_p) = op_iter_init_phiuse (&(iter), phi, 0x01); !
op_iter_done (&(iter)); (use_p) = op_iter_next_use (&
(iter)))
{
 tree use = USE_FROM_PTR (use_p)get_use_from_ptr (use_p);
 iv = find_deriving_biv_for_expr (data, use);
 if (iv)
   return iv;
}
    return NULLnullptr;
  }
if (gimple_code (stmt) != GIMPLE_ASSIGN)
  return NULLnullptr;

e1 = gimple_assign_rhs1 (stmt);
code = gimple_assign_rhs_code (stmt);
if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
  return find_deriving_biv_for_expr (data, e1);

switch (code)
  {
  case MULT_EXPR:
  case PLUS_EXPR:
  case MINUS_EXPR:
  case POINTER_PLUS_EXPR:
    /* Increments, decrements and multiplications by a constant
are simple.  */
    e2 = gimple_assign_rhs2 (stmt);
    iv = find_deriving_biv_for_expr (data, e2);
    if (iv)
return iv;
    gcc_fallthrough ();

  CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
    /* Casts are simple.  */
    return find_deriving_biv_for_expr (data, e1);

  default:
    break;
  }

return NULLnullptr;
1969}

1971/* Record BIV, its predecessor and successor that they are used in
 address type uses.  */

1974static void
1975record_biv_for_address_use (struct ivopts_data *data, struct iv *biv)
1976{
unsigned i;
tree type, base_1, base_2;
bitmap_iterator bi;

if (!biv || !biv->biv_p || integer_zerop (biv->step)
    || biv->have_address_use || !biv->no_overflow)
  return;

type = TREE_TYPE (biv->base)((contains_struct_check ((biv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 1985, __FUNCTION__))->typed.type);
if (!INTEGRAL_TYPE_P (type)(((enum tree_code) (type)->base.code) == ENUMERAL_TYPE || (
(enum tree_code) (type)->base.code) == BOOLEAN_TYPE || ((enum
 tree_code) (type)->base.code) == INTEGER_TYPE))
  return;

biv->have_address_use = true;
data->bivs_not_used_in_addr--;
base_1 = fold_build2 (PLUS_EXPR, type, biv->base, biv->step)fold_build2_loc (((location_t) 0), PLUS_EXPR, type, biv->base
, biv->step );
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)for (bmp_iter_set_init (&(bi), (data->relevant), (0), &
(i)); bmp_iter_set (&(bi), &(i)); bmp_iter_next (&
(bi), &(i)))
  {
    struct iv *iv = ver_info (data, i)->iv;

    if (!iv || !iv->biv_p || integer_zerop (iv->step)
 || iv->have_address_use || !iv->no_overflow)
continue;

    if (type != TREE_TYPE (iv->base)((contains_struct_check ((iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2000, __FUNCTION__))->typed.type)
 || !INTEGRAL_TYPE_P (TREE_TYPE (iv->base))(((enum tree_code) (((contains_struct_check ((iv->base), (
TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2001, __FUNCTION__))->typed.type))->base.code) == ENUMERAL_TYPE
 || ((enum tree_code) (((contains_struct_check ((iv->base)
, (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2001, __FUNCTION__))->typed.type))->base.code) == BOOLEAN_TYPE
 || ((enum tree_code) (((contains_struct_check ((iv->base)
, (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2001, __FUNCTION__))->typed.type))->base.code) == INTEGER_TYPE
))
continue;

    if (!operand_equal_p (biv->step, iv->step, 0))
continue;

    base_2 = fold_build2 (PLUS_EXPR, type, iv->base, iv->step)fold_build2_loc (((location_t) 0), PLUS_EXPR, type, iv->base
, iv->step );
    if (operand_equal_p (base_1, iv->base, 0)
 || operand_equal_p (base_2, biv->base, 0))
{
 iv->have_address_use = true;
 data->bivs_not_used_in_addr--;
}
  }
2015}

2017/* Cumulates the steps of indices into DATA and replaces their values with the
 initial ones.  Returns false when the value of the index cannot be determined.
 Callback for for_each_index.  */

2021struct ifs_ivopts_data
2022{
struct ivopts_data *ivopts_data;
gimple *stmt;
tree step;
2026};

2028static bool
2029idx_find_step (tree base, tree *idx, void *data)
2030{
struct ifs_ivopts_data *dta = (struct ifs_ivopts_data *) data;
struct iv *iv;
bool use_overflow_semantics = false;
tree step, iv_base, iv_step, lbound, off;
class loop *loop = dta->ivopts_data->current_loop;

/* If base is a component ref, require that the offset of the reference
   be invariant.  */
if (TREE_CODE (base)((enum tree_code) (base)->base.code) == COMPONENT_REF)
  {
    off = component_ref_field_offset (base);
    return expr_invariant_in_loop_p (loop, off);
  }

/* If base is array, first check whether we will be able to move the
   reference out of the loop (in order to take its address in strength
   reduction).  In order for this to work we need both lower bound
   and step to be loop invariants.  */
if (TREE_CODE (base)((enum tree_code) (base)->base.code) == ARRAY_REF || TREE_CODE (base)((enum tree_code) (base)->base.code) == ARRAY_RANGE_REF)
  {
    /* Moreover, for a range, the size needs to be invariant as well.  */
    if (TREE_CODE (base)((enum tree_code) (base)->base.code) == ARRAY_RANGE_REF
 && !expr_invariant_in_loop_p (loop, TYPE_SIZE (TREE_TYPE (base))((tree_class_check ((((contains_struct_check ((base), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2053, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2053, __FUNCTION__))->type_common.size)))
return false;

    step = array_ref_element_size (base);
    lbound = array_ref_low_bound (base);

    if (!expr_invariant_in_loop_p (loop, step)
 || !expr_invariant_in_loop_p (loop, lbound))
return false;
  }

if (TREE_CODE (*idx)((enum tree_code) (*idx)->base.code) != SSA_NAME)
  return true;

iv = get_iv (dta->ivopts_data, *idx);
if (!iv)
  return false;

/* XXX  We produce for a base of *D42 with iv->base being &x[0]
 *&x[0], which is not folded and does not trigger the
 ARRAY_REF path below.  */
*idx = iv->base;

if (integer_zerop (iv->step))
  return true;

if (TREE_CODE (base)((enum tree_code) (base)->base.code) == ARRAY_REF || TREE_CODE (base)((enum tree_code) (base)->base.code) == ARRAY_RANGE_REF)
  {
    step = array_ref_element_size (base);

    /* We only handle addresses whose step is an integer constant.  */
    if (TREE_CODE (step)((enum tree_code) (step)->base.code) != INTEGER_CST)
return false;
  }
else
  /* The step for pointer arithmetics already is 1 byte.  */
  step = size_one_nodeglobal_trees[TI_SIZE_ONE];

iv_base = iv->base;
iv_step = iv->step;
if (iv->no_overflow && nowrap_type_p (TREE_TYPE (iv_step)((contains_struct_check ((iv_step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2093, __FUNCTION__))->typed.type)))
  use_overflow_semantics = true;

if (!convert_affine_scev (dta->ivopts_data->current_loop,
	    sizetypesizetype_tab[(int) stk_sizetype], &iv_base, &iv_step, dta->stmt,
	    use_overflow_semantics))
  {
    /* The index might wrap.  */
    return false;
  }

step = fold_build2 (MULT_EXPR, sizetype, step, iv_step)fold_build2_loc (((location_t) 0), MULT_EXPR, sizetype_tab[(int
) stk_sizetype], step, iv_step );
dta->step = fold_build2 (PLUS_EXPR, sizetype, dta->step, step)fold_build2_loc (((location_t) 0), PLUS_EXPR, sizetype_tab[(int
) stk_sizetype], dta->step, step );

if (dta->ivopts_data->bivs_not_used_in_addr)
  {
    if (!iv->biv_p)
iv = find_deriving_biv_for_expr (dta->ivopts_data, iv->ssa_name);

    record_biv_for_address_use (dta->ivopts_data, iv);
  }
return true;
2115}

2117/* Records use in index IDX.  Callback for for_each_index.  Ivopts data
 object is passed to it in DATA.  */

2120static bool
2121idx_record_use (tree base, tree *idx,
void *vdata)
2123{
struct ivopts_data *data = (struct ivopts_data *) vdata;
find_interesting_uses_op (data, *idx);
if (TREE_CODE (base)((enum tree_code) (base)->base.code) == ARRAY_REF || TREE_CODE (base)((enum tree_code) (base)->base.code) == ARRAY_RANGE_REF)
  {
    if (TREE_OPERAND (base, 2)(*((const_cast<tree*> (tree_operand_check ((base), (2),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2128, __FUNCTION__))))))
find_interesting_uses_op (data, TREE_OPERAND (base, 2)(*((const_cast<tree*> (tree_operand_check ((base), (2),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2129, __FUNCTION__))))));
    if (TREE_OPERAND (base, 3)(*((const_cast<tree*> (tree_operand_check ((base), (3),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2130, __FUNCTION__))))))
find_interesting_uses_op (data, TREE_OPERAND (base, 3)(*((const_cast<tree*> (tree_operand_check ((base), (3),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2131, __FUNCTION__))))));
  }
return true;
2134}

2136/* If we can prove that TOP = cst * BOT for some constant cst,
 store cst to MUL and return true.  Otherwise return false.
 The returned value is always sign-extended, regardless of the
 signedness of TOP and BOT.  */

2141static bool
2142constant_multiple_of (tree top, tree bot, widest_int *mul)
2143{
tree mby;
enum tree_code code;
unsigned precision = TYPE_PRECISION (TREE_TYPE (top))((tree_class_check ((((contains_struct_check ((top), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2146, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2146, __FUNCTION__))->type_common.precision);
widest_int res, p0, p1;

STRIP_NOPS (top)(top) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((top)))));
STRIP_NOPS (bot)(bot) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((bot)))));

if (operand_equal_p (top, bot, 0))
  {
    *mul = 1;
    return true;
  }

code = TREE_CODE (top)((enum tree_code) (top)->base.code);
switch (code)
  {
  case MULT_EXPR:
    mby = TREE_OPERAND (top, 1)(*((const_cast<tree*> (tree_operand_check ((top), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2162, __FUNCTION__)))));
    if (TREE_CODE (mby)((enum tree_code) (mby)->base.code) != INTEGER_CST)
return false;

    if (!constant_multiple_of (TREE_OPERAND (top, 0)(*((const_cast<tree*> (tree_operand_check ((top), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2166, __FUNCTION__))))), bot, &res))
return false;

    *mul = wi::sext (res * wi::to_widest (mby), precision);
    return true;

  case PLUS_EXPR:
  case MINUS_EXPR:
    if (!constant_multiple_of (TREE_OPERAND (top, 0)(*((const_cast<tree*> (tree_operand_check ((top), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2174, __FUNCTION__))))), bot, &p0)
 || !constant_multiple_of (TREE_OPERAND (top, 1)(*((const_cast<tree*> (tree_operand_check ((top), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2175, __FUNCTION__))))), bot, &p1))
return false;

    if (code == MINUS_EXPR)
p1 = -p1;
    *mul = wi::sext (p0 + p1, precision);
    return true;

  case INTEGER_CST:
    if (TREE_CODE (bot)((enum tree_code) (bot)->base.code) != INTEGER_CST)
return false;

    p0 = widest_int::from (wi::to_wide (top), SIGNED);
    p1 = widest_int::from (wi::to_wide (bot), SIGNED);
    if (p1 == 0)
return false;
    *mul = wi::sext (wi::divmod_trunc (p0, p1, SIGNED, &res), precision);
    return res == 0;

  default:
    if (POLY_INT_CST_P (top)(1 > 1 && ((enum tree_code) (top)->base.code) ==
 POLY_INT_CST)
 && POLY_INT_CST_P (bot)(1 > 1 && ((enum tree_code) (bot)->base.code) ==
 POLY_INT_CST)
 && constant_multiple_p (wi::to_poly_widest (top),
		  wi::to_poly_widest (bot), mul))
return true;

    return false;
  }
2203}

2205/* Return true if memory reference REF with step STEP may be unaligned.  */

2207static bool
2208may_be_unaligned_p (tree ref, tree step)
2209{
/* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
   thus they are not misaligned.  */
if (TREE_CODE (ref)((enum tree_code) (ref)->base.code) == TARGET_MEM_REF)
1
Assuming field 'code' is not equal to TARGET_MEM_REF→
  return false;

unsigned int align = TYPE_ALIGN (TREE_TYPE (ref))(((tree_class_check ((((contains_struct_check ((ref), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2215, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2215, __FUNCTION__))->type_common.align) ? ((unsigned)1)
 << (((tree_class_check ((((contains_struct_check ((ref
), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2215, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2215, __FUNCTION__))->type_common.align) - 1) : 0);
2
←
Taking false branch→
3
←
Assuming field 'align' is 0→
4
←
'?' condition is false→
5
←
'align' initialized to 0→
if (GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref)))get_mode_alignment (((((enum tree_code) ((tree_class_check ((
((contains_struct_check ((ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2216, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2216, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (((contains_struct_check ((ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2216, __FUNCTION__))->typed.type)) : (((contains_struct_check
 ((ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2216, __FUNCTION__))->typed.type))->type_common.mode)
) > align)
6
←
Assuming field 'code' is not equal to VECTOR_TYPE→
7
←
'?' condition is false→
8
←
Assuming the condition is false→
9
←
Taking false branch→
  align = GET_MODE_ALIGNMENT (TYPE_MODE (TREE_TYPE (ref)))get_mode_alignment (((((enum tree_code) ((tree_class_check ((
((contains_struct_check ((ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2217, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2217, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (((contains_struct_check ((ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2217, __FUNCTION__))->typed.type)) : (((contains_struct_check
 ((ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2217, __FUNCTION__))->typed.type))->type_common.mode)
);

unsigned HOST_WIDE_INTlong bitpos;
unsigned int ref_align;
get_object_alignment_1 (ref, &ref_align, &bitpos);
if (ref_align < align
10
←
Assuming 'ref_align' is >= 'align'→
    || (bitpos % align) != 0
11
←
Division by zero
    || (bitpos % BITS_PER_UNIT(8)) != 0)
  return true;

unsigned int trailing_zeros = tree_ctz (step);
if (trailing_zeros < HOST_BITS_PER_INT(8 * 4)
    && (1U << trailing_zeros) * BITS_PER_UNIT(8) < align)
  return true;

return false;
2233}

2235/* Return true if EXPR may be non-addressable.   */

2237bool
2238may_be_nonaddressable_p (tree expr)
2239{
switch (TREE_CODE (expr)((enum tree_code) (expr)->base.code))
  {
  case VAR_DECL:
    /* Check if it's a register variable.  */
    return DECL_HARD_REGISTER (expr)((tree_check ((expr), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2244, __FUNCTION__, (VAR_DECL)))->decl_with_vis.hard_register
);

  case TARGET_MEM_REF:
    /* TARGET_MEM_REFs are translated directly to valid MEMs on the
target, thus they are always addressable.  */
    return false;

  case MEM_REF:
    /* Likewise for MEM_REFs, modulo the storage order.  */
    return REF_REVERSE_STORAGE_ORDER (expr)((tree_check2 ((expr), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2253, __FUNCTION__, (BIT_FIELD_REF), (MEM_REF)))->base.default_def_flag
);

  case BIT_FIELD_REF:
    if (REF_REVERSE_STORAGE_ORDER (expr)((tree_check2 ((expr), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2256, __FUNCTION__, (BIT_FIELD_REF), (MEM_REF)))->base.default_def_flag
))
return true;
    return may_be_nonaddressable_p (TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2258, __FUNCTION__))))));

  case COMPONENT_REF:
    if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr, 0)))((tree_check4 ((((contains_struct_check (((*((const_cast<tree
*> (tree_operand_check ((expr), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2261, __FUNCTION__)))))), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2261, __FUNCTION__))->typed.type)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2261, __FUNCTION__, (RECORD_TYPE), (UNION_TYPE), (QUAL_UNION_TYPE
), (ARRAY_TYPE)))->base.u.bits.saturating_flag))
return true;
    return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))((tree_check (((*((const_cast<tree*> (tree_operand_check
 ((expr), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2263, __FUNCTION__)))))), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2263, __FUNCTION__, (FIELD_DECL)))->decl_common.decl_flag_2
)
    || may_be_nonaddressable_p (TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2264, __FUNCTION__))))));

  case ARRAY_REF:
  case ARRAY_RANGE_REF:
    if (TYPE_REVERSE_STORAGE_ORDER (TREE_TYPE (TREE_OPERAND (expr, 0)))((tree_check4 ((((contains_struct_check (((*((const_cast<tree
*> (tree_operand_check ((expr), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2268, __FUNCTION__)))))), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2268, __FUNCTION__))->typed.type)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2268, __FUNCTION__, (RECORD_TYPE), (UNION_TYPE), (QUAL_UNION_TYPE
), (ARRAY_TYPE)))->base.u.bits.saturating_flag))
return true;
    return may_be_nonaddressable_p (TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2270, __FUNCTION__))))));

  case VIEW_CONVERT_EXPR:
    /* This kind of view-conversions may wrap non-addressable objects
and make them look addressable.  After some processing the
non-addressability may be uncovered again, causing ADDR_EXPRs
of inappropriate objects to be built.  */
    if (is_gimple_reg (TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2277, __FUNCTION__))))))
 || !is_gimple_addressable (TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2278, __FUNCTION__)))))))
return true;
    return may_be_nonaddressable_p (TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2280, __FUNCTION__))))));

  CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
    return true;

  default:
    break;
  }

return false;
2290}

2292/* Finds addresses in *OP_P inside STMT.  */

2294static void
2295find_interesting_uses_address (struct ivopts_data *data, gimple *stmt,
	       tree *op_p)
2297{
tree base = *op_p, step = size_zero_nodeglobal_trees[TI_SIZE_ZERO];
struct iv *civ;
struct ifs_ivopts_data ifs_ivopts_data;

/* Do not play with volatile memory references.  A bit too conservative,
   perhaps, but safe.  */
if (gimple_has_volatile_ops (stmt))
  goto fail;

/* Ignore bitfields for now.  Not really something terribly complicated
   to handle.  TODO.  */
if (TREE_CODE (base)((enum tree_code) (base)->base.code) == BIT_FIELD_REF)
  goto fail;

base = unshare_expr (base);

if (TREE_CODE (base)((enum tree_code) (base)->base.code) == TARGET_MEM_REF)
  {
    tree type = build_pointer_type (TREE_TYPE (base)((contains_struct_check ((base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2316, __FUNCTION__))->typed.type));
    tree astep;

    if (TMR_BASE (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2319, __FUNCTION__, (TARGET_MEM_REF)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2319, __FUNCTION__))))))
 && TREE_CODE (TMR_BASE (base))((enum tree_code) (((*((const_cast<tree*> (tree_operand_check
 (((tree_check ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2320, __FUNCTION__, (TARGET_MEM_REF)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2320, __FUNCTION__)))))))->base.code) == SSA_NAME)
{
 civ = get_iv (data, TMR_BASE (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2322, __FUNCTION__, (TARGET_MEM_REF)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2322, __FUNCTION__)))))));
 if (!civ)
   goto fail;

 TMR_BASE (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2326, __FUNCTION__, (TARGET_MEM_REF)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2326, __FUNCTION__)))))) = civ->base;
 step = civ->step;
}
    if (TMR_INDEX2 (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2329, __FUNCTION__, (TARGET_MEM_REF)))), (4), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2329, __FUNCTION__))))))
 && TREE_CODE (TMR_INDEX2 (base))((enum tree_code) (((*((const_cast<tree*> (tree_operand_check
 (((tree_check ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2330, __FUNCTION__, (TARGET_MEM_REF)))), (4), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2330, __FUNCTION__)))))))->base.code) == SSA_NAME)
{
 civ = get_iv (data, TMR_INDEX2 (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2332, __FUNCTION__, (TARGET_MEM_REF)))), (4), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2332, __FUNCTION__)))))));
 if (!civ)
   goto fail;

 TMR_INDEX2 (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2336, __FUNCTION__, (TARGET_MEM_REF)))), (4), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2336, __FUNCTION__)))))) = civ->base;
 step = civ->step;
}
    if (TMR_INDEX (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2339, __FUNCTION__, (TARGET_MEM_REF)))), (2), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2339, __FUNCTION__))))))
 && TREE_CODE (TMR_INDEX (base))((enum tree_code) (((*((const_cast<tree*> (tree_operand_check
 (((tree_check ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2340, __FUNCTION__, (TARGET_MEM_REF)))), (2), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2340, __FUNCTION__)))))))->base.code) == SSA_NAME)
{
 civ = get_iv (data, TMR_INDEX (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2342, __FUNCTION__, (TARGET_MEM_REF)))), (2), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2342, __FUNCTION__)))))));
 if (!civ)
   goto fail;

 TMR_INDEX (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2346, __FUNCTION__, (TARGET_MEM_REF)))), (2), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2346, __FUNCTION__)))))) = civ->base;
 astep = civ->step;

 if (astep)
   {
     if (TMR_STEP (base)((*((const_cast<tree*> (tree_operand_check (((tree_check
 ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2351, __FUNCTION__, (TARGET_MEM_REF)))), (3), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2351, __FUNCTION__)))))))
astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep)fold_build2_loc (((location_t) 0), MULT_EXPR, type, ((*((const_cast
<tree*> (tree_operand_check (((tree_check ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2352, __FUNCTION__, (TARGET_MEM_REF)))), (3), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2352, __FUNCTION__)))))), astep );

     step = fold_build2 (PLUS_EXPR, type, step, astep)fold_build2_loc (((location_t) 0), PLUS_EXPR, type, step, astep
 );
   }
}

    if (integer_zerop (step))
goto fail;
    base = tree_mem_ref_addr (type, base);
  }
else
  {
    ifs_ivopts_data.ivopts_data = data;
    ifs_ivopts_data.stmt = stmt;
    ifs_ivopts_data.step = size_zero_nodeglobal_trees[TI_SIZE_ZERO];
    if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data)
 || integer_zerop (ifs_ivopts_data.step))
goto fail;
    step = ifs_ivopts_data.step;

    /* Check that the base expression is addressable.  This needs
to be done after substituting bases of IVs into it.  */
    if (may_be_nonaddressable_p (base))
goto fail;

    /* Moreover, on strict alignment platforms, check that it is
sufficiently aligned.  */
    if (STRICT_ALIGNMENT0 && may_be_unaligned_p (base, step))
goto fail;

    base = build_fold_addr_expr (base)build_fold_addr_expr_loc (((location_t) 0), (base));

    /* Substituting bases of IVs into the base expression might
have caused folding opportunities.  */
    if (TREE_CODE (base)((enum tree_code) (base)->base.code) == ADDR_EXPR)
{
 tree *ref = &TREE_OPERAND (base, 0)(*((const_cast<tree*> (tree_operand_check ((base), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2388, __FUNCTION__)))));
 while (handled_component_p (*ref))
   ref = &TREE_OPERAND (*ref, 0)(*((const_cast<tree*> (tree_operand_check ((*ref), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2390, __FUNCTION__)))));
 if (TREE_CODE (*ref)((enum tree_code) (*ref)->base.code) == MEM_REF)
   {
     tree tem = fold_binary (MEM_REF, TREE_TYPE (*ref),fold_binary_loc (((location_t) 0), MEM_REF, ((contains_struct_check
 ((*ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2393, __FUNCTION__))->typed.type), (*((const_cast<tree
*> (tree_operand_check ((*ref), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2394, __FUNCTION__))))), (*((const_cast<tree*> (tree_operand_check
 ((*ref), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2395, __FUNCTION__))))))
		      TREE_OPERAND (*ref, 0),fold_binary_loc (((location_t) 0), MEM_REF, ((contains_struct_check
 ((*ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2393, __FUNCTION__))->typed.type), (*((const_cast<tree
*> (tree_operand_check ((*ref), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2394, __FUNCTION__))))), (*((const_cast<tree*> (tree_operand_check
 ((*ref), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2395, __FUNCTION__))))))
		      TREE_OPERAND (*ref, 1))fold_binary_loc (((location_t) 0), MEM_REF, ((contains_struct_check
 ((*ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2393, __FUNCTION__))->typed.type), (*((const_cast<tree
*> (tree_operand_check ((*ref), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2394, __FUNCTION__))))), (*((const_cast<tree*> (tree_operand_check
 ((*ref), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2395, __FUNCTION__))))));
     if (tem)
*ref = tem;
   }
}
  }

civ = alloc_iv (data, base, step);
/* Fail if base object of this memory reference is unknown.  */
if (civ->base_object == NULL_TREE(tree) nullptr)
  goto fail;

record_group_use (data, op_p, civ, stmt, USE_REF_ADDRESS, TREE_TYPE (*op_p)((contains_struct_check ((*op_p), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2407, __FUNCTION__))->typed.type));
return;

2410fail:
for_each_index (op_p, idx_record_use, data);
2412}

2414/* Finds and records invariants used in STMT.  */

2416static void
2417find_invariants_stmt (struct ivopts_data *data, gimple *stmt)
2418{
ssa_op_iter iter;
use_operand_p use_p;
tree op;

FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)for ((use_p) = (gimple_code (stmt) == GIMPLE_PHI ? op_iter_init_phiuse
 (&(iter), as_a <gphi *> (stmt), 0x01) : op_iter_init_use
 (&(iter), stmt, 0x01)); !op_iter_done (&(iter)); (use_p
) = op_iter_next_use (&(iter)))
  {
    op = USE_FROM_PTR (use_p)get_use_from_ptr (use_p);
    record_invariant (data, op, false);
  }
2428}

2430/* CALL calls an internal function.  If operand *OP_P will become an
 address when the call is expanded, return the type of the memory
 being addressed, otherwise return null.  */

2434static tree
2435get_mem_type_for_internal_fn (gcall *call, tree *op_p)
2436{
switch (gimple_call_internal_fn (call))
  {
  case IFN_MASK_LOAD:
  case IFN_MASK_LOAD_LANES:
  case IFN_LEN_LOAD:
    if (op_p == gimple_call_arg_ptr (call, 0))
return TREE_TYPE (gimple_call_lhs (call))((contains_struct_check ((gimple_call_lhs (call)), (TS_TYPED)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2443, __FUNCTION__))->typed.type);
    return NULL_TREE(tree) nullptr;

  case IFN_MASK_STORE:
  case IFN_MASK_STORE_LANES:
  case IFN_LEN_STORE:
    if (op_p == gimple_call_arg_ptr (call, 0))
return TREE_TYPE (gimple_call_arg (call, 3))((contains_struct_check ((gimple_call_arg (call, 3)), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2450, __FUNCTION__))->typed.type);
    return NULL_TREE(tree) nullptr;

  default:
    return NULL_TREE(tree) nullptr;
  }
2456}

2458/* IV is a (non-address) iv that describes operand *OP_P of STMT.
 Return true if the operand will become an address when STMT
 is expanded and record the associated address use if so.  */

2462static bool
2463find_address_like_use (struct ivopts_data *data, gimple *stmt, tree *op_p,
       struct iv *iv)
2465{
/* Fail if base object of this memory reference is unknown.  */
if (iv->base_object == NULL_TREE(tree) nullptr)
  return false;

tree mem_type = NULL_TREE(tree) nullptr;
if (gcall *call = dyn_cast <gcall *> (stmt))
  if (gimple_call_internal_p (call))
    mem_type = get_mem_type_for_internal_fn (call, op_p);
if (mem_type)
  {
    iv = alloc_iv (data, iv->base, iv->step);
    record_group_use (data, op_p, iv, stmt, USE_PTR_ADDRESS, mem_type);
    return true;
  }
return false;
2481}

2483/* Finds interesting uses of induction variables in the statement STMT.  */

2485static void
2486find_interesting_uses_stmt (struct ivopts_data *data, gimple *stmt)
2487{
struct iv *iv;
tree op, *lhs, *rhs;
ssa_op_iter iter;
use_operand_p use_p;
enum tree_code code;

find_invariants_stmt (data, stmt);

if (gimple_code (stmt) == GIMPLE_COND)
  {
    find_interesting_uses_cond (data, stmt);
    return;
  }

if (is_gimple_assign (stmt))
  {
    lhs = gimple_assign_lhs_ptr (stmt);
    rhs = gimple_assign_rhs1_ptr (stmt);

    if (TREE_CODE (*lhs)((enum tree_code) (*lhs)->base.code) == SSA_NAME)
{
 /* If the statement defines an induction variable, the uses are not
    interesting by themselves.  */

 iv = get_iv (data, *lhs);

 if (iv && !integer_zerop (iv->step))
   return;
}

    code = gimple_assign_rhs_code (stmt);
    if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
 && (REFERENCE_CLASS_P (*rhs)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (*rhs)->base.code))] == tcc_reference)
     || is_gimple_val (*rhs)))
{
 if (REFERENCE_CLASS_P (*rhs)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (*rhs)->base.code))] == tcc_reference))
   find_interesting_uses_address (data, stmt, rhs);
 else
   find_interesting_uses_op (data, *rhs);

 if (REFERENCE_CLASS_P (*lhs)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (*lhs)->base.code))] == tcc_reference))
   find_interesting_uses_address (data, stmt, lhs);
 return;
}
    else if (TREE_CODE_CLASS (code)tree_code_type_tmpl <0>::tree_code_type[(int) (code)] == tcc_comparison)
{
 find_interesting_uses_cond (data, stmt);
 return;
}

    /* TODO -- we should also handle address uses of type

memory = call (whatever);

and

call (memory).  */
  }

if (gimple_code (stmt) == GIMPLE_PHI
    && gimple_bb (stmt) == data->current_loop->header)
  {
    iv = get_iv (data, PHI_RESULT (stmt)get_def_from_ptr (gimple_phi_result_ptr (stmt)));

    if (iv && !integer_zerop (iv->step))
return;
  }

FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)for ((use_p) = (gimple_code (stmt) == GIMPLE_PHI ? op_iter_init_phiuse
 (&(iter), as_a <gphi *> (stmt), 0x01) : op_iter_init_use
 (&(iter), stmt, 0x01)); !op_iter_done (&(iter)); (use_p
) = op_iter_next_use (&(iter)))
  {
    op = USE_FROM_PTR (use_p)get_use_from_ptr (use_p);

    if (TREE_CODE (op)((enum tree_code) (op)->base.code) != SSA_NAME)
continue;

    iv = get_iv (data, op);
    if (!iv)
continue;

    if (!find_address_like_use (data, stmt, use_p->use, iv))
find_interesting_uses_op (data, op);
  }
2570}

2572/* Finds interesting uses of induction variables outside of loops
 on loop exit edge EXIT.  */

2575static void
2576find_interesting_uses_outside (struct ivopts_data *data, edge exit)
2577{
gphi *phi;
gphi_iterator psi;
tree def;

for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
  {
    phi = psi.phi ();
    def = PHI_ARG_DEF_FROM_EDGE (phi, exit)gimple_phi_arg_def (((phi)), ((exit)->dest_idx));
    if (!virtual_operand_p (def))
find_interesting_uses_op (data, def);
  }
2589}

2591/* Return TRUE if OFFSET is within the range of [base + offset] addressing
 mode for memory reference represented by USE.  */

2594static GTY (()) vec<rtx, va_gc> *addr_list;

2596static bool
2597addr_offset_valid_p (struct iv_use *use, poly_int64 offset)
2598{
rtx reg, addr;
unsigned list_index;
addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (use->iv->base))((tree_class_check ((((contains_struct_check ((use->iv->
base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2601, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2601, __FUNCTION__))->base.u.bits.address_space);
machine_mode addr_mode, mem_mode = TYPE_MODE (use->mem_type)((((enum tree_code) ((tree_class_check ((use->mem_type), (
tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2602, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (use->mem_type) : (use->mem_type)->type_common.mode
);

list_index = (unsigned) as * MAX_MACHINE_MODE + (unsigned) mem_mode;
if (list_index >= vec_safe_length (addr_list))
  vec_safe_grow_cleared (addr_list, list_index + MAX_MACHINE_MODE, true);

addr = (*addr_list)[list_index];
if (!addr)
  {
    addr_mode = targetm.addr_space.address_mode (as);
    reg = gen_raw_REG (addr_mode, LAST_VIRTUAL_REGISTER(((76)) + 5) + 1);
    addr = gen_rtx_fmt_ee (PLUS, addr_mode, reg, NULL_RTX)gen_rtx_fmt_ee_stat ((PLUS), (addr_mode), (reg), ((rtx) 0) );
    (*addr_list)[list_index] = addr;
  }
else
  addr_mode = GET_MODE (addr)((machine_mode) (addr)->mode);

XEXP (addr, 1)(((addr)->u.fld[1]).rt_rtx) = gen_int_mode (offset, addr_mode);
return (memory_address_addr_space_p (mem_mode, addr, as));
2621}

2623/* Comparison function to sort group in ascending order of addr_offset.  */

2625static int
2626group_compare_offset (const void *a, const void *b)
2627{
const struct iv_use *const *u1 = (const struct iv_use *const *) a;
const struct iv_use *const *u2 = (const struct iv_use *const *) b;

return compare_sizes_for_sort ((*u1)->addr_offset, (*u2)->addr_offset);
2632}

2634/* Check if small groups should be split.  Return true if no group
 contains more than two uses with distinct addr_offsets.  Return
 false otherwise.  We want to split such groups because:

   1) Small groups don't have much benefit and may interfer with
general candidate selection.
   2) Size for problem with only small groups is usually small and
general algorithm can handle it well.

 TODO -- Above claim may not hold when we want to merge memory
 accesses with conseuctive addresses.  */

2646static bool
2647split_small_address_groups_p (struct ivopts_data *data)
2648{
unsigned int i, j, distinct = 1;
struct iv_use *pre;
struct iv_group *group;

for (i = 0; i < data->vgroups.length (); i++)
  {
    group = data->vgroups[i];
    if (group->vuses.length () == 1)
continue;

    gcc_assert (address_p (group->type))((void)(!(address_p (group->type)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2659, __FUNCTION__), 0 : 0));
    if (group->vuses.length () == 2)
{
 if (compare_sizes_for_sort (group->vuses[0]->addr_offset,
		      group->vuses[1]->addr_offset) > 0)
   std::swap (group->vuses[0], group->vuses[1]);
}
    else
group->vuses.qsort (group_compare_offset)qsort (group_compare_offset);

    if (distinct > 2)
continue;

    distinct = 1;
    for (pre = group->vuses[0], j = 1; j < group->vuses.length (); j++)
{
 if (maybe_ne (group->vuses[j]->addr_offset, pre->addr_offset))
   {
     pre = group->vuses[j];
     distinct++;
   }

 if (distinct > 2)
   break;
}
  }

return (distinct <= 2);
2687}

2689/* For each group of address type uses, this function further groups
 these uses according to the maximum offset supported by target's
 [base + offset] addressing mode.  */

2693static void
2694split_address_groups (struct ivopts_data *data)
2695{
unsigned int i, j;
/* Always split group.  */
bool split_p = split_small_address_groups_p (data);

for (i = 0; i < data->vgroups.length (); i++)
  {
    struct iv_group *new_group = NULLnullptr;
    struct iv_group *group = data->vgroups[i];
    struct iv_use *use = group->vuses[0];

    use->id = 0;
    use->group_id = group->id;
    if (group->vuses.length () == 1)
continue;

    gcc_assert (address_p (use->type))((void)(!(address_p (use->type)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2711, __FUNCTION__), 0 : 0));

    for (j = 1; j < group->vuses.length ();)
{
 struct iv_use *next = group->vuses[j];
 poly_int64 offset = next->addr_offset - use->addr_offset;

 /* Split group if aksed to, or the offset against the first
    use can't fit in offset part of addressing mode.  IV uses
    having the same offset are still kept in one group.  */
 if (maybe_ne (offset, 0)
     && (split_p || !addr_offset_valid_p (use, offset)))
   {
     if (!new_group)
new_group = record_group (data, group->type);
     group->vuses.ordered_remove (j);
     new_group->vuses.safe_push (next);
     continue;
   }

 next->id = j;
 next->group_id = group->id;
 j++;
}
  }
2736}

2738/* Finds uses of the induction variables that are interesting.  */

2740static void
2741find_interesting_uses (struct ivopts_data *data, basic_block *body)
2742{
basic_block bb;
gimple_stmt_iterator bsi;
unsigned i;
edge e;

for (i = 0; i < data->current_loop->num_nodes; i++)
  {
    edge_iterator ei;
    bb = body[i];

    FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_exit_block_ptr)
   && !flow_bb_inside_loop_p (data->current_loop, e->dest))
 find_interesting_uses_outside (data, e);

    for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
find_interesting_uses_stmt (data, gsi_stmt (bsi));
    for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
if (!is_gimple_debug (gsi_stmt (bsi)))
 find_interesting_uses_stmt (data, gsi_stmt (bsi));
  }

split_address_groups (data);

if (dump_file && (dump_flags & TDF_DETAILS))
  {
    fprintf (dump_file, "\n<IV Groups>:\n");
    dump_groups (dump_file, data);
    fprintf (dump_file, "\n");
  }
2773}

2775/* Strips constant offsets from EXPR and stores them to OFFSET.  If INSIDE_ADDR
 is true, assume we are inside an address.  If TOP_COMPREF is true, assume
 we are at the top-level of the processed address.  */

2779static tree
2780strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
poly_int64 *offset)
2782{
tree op0 = NULL_TREE(tree) nullptr, op1 = NULL_TREE(tree) nullptr, tmp, step;
enum tree_code code;
tree type, orig_type = TREE_TYPE (expr)((contains_struct_check ((expr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2785, __FUNCTION__))->typed.type);
poly_int64 off0, off1;
HOST_WIDE_INTlong st;
tree orig_expr = expr;

STRIP_NOPS (expr)(expr) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((expr)))));

type = TREE_TYPE (expr)((contains_struct_check ((expr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2792, __FUNCTION__))->typed.type);
code = TREE_CODE (expr)((enum tree_code) (expr)->base.code);
*offset = 0;

switch (code)
  {
  case POINTER_PLUS_EXPR:
  case PLUS_EXPR:
  case MINUS_EXPR:
    op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2801, __FUNCTION__)))));
    op1 = TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2802, __FUNCTION__)))));

    op0 = strip_offset_1 (op0, false, false, &off0);
    op1 = strip_offset_1 (op1, false, false, &off1);

    *offset = (code == MINUS_EXPR ? off0 - off1 : off0 + off1);
    if (op0 == TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2808, __FUNCTION__)))))
 && op1 == TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2809, __FUNCTION__))))))
return orig_expr;

    if (integer_zerop (op1))
expr = op0;
    else if (integer_zerop (op0))
{
 if (code == MINUS_EXPR)
   expr = fold_build1 (NEGATE_EXPR, type, op1)fold_build1_loc (((location_t) 0), NEGATE_EXPR, type, op1 );
 else
   expr = op1;
}
    else
expr = fold_build2 (code, type, op0, op1)fold_build2_loc (((location_t) 0), code, type, op0, op1 );

    return fold_convert (orig_type, expr)fold_convert_loc (((location_t) 0), orig_type, expr);

  case MULT_EXPR:
    op1 = TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2827, __FUNCTION__)))));
    if (!cst_and_fits_in_hwi (op1))
return orig_expr;

    op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2831, __FUNCTION__)))));
    op0 = strip_offset_1 (op0, false, false, &off0);
    if (op0 == TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2833, __FUNCTION__))))))
return orig_expr;

    *offset = off0 * int_cst_value (op1);
    if (integer_zerop (op0))
expr = op0;
    else
expr = fold_build2 (MULT_EXPR, type, op0, op1)fold_build2_loc (((location_t) 0), MULT_EXPR, type, op0, op1 );

    return fold_convert (orig_type, expr)fold_convert_loc (((location_t) 0), orig_type, expr);

  case ARRAY_REF:
  case ARRAY_RANGE_REF:
    if (!inside_addr)
return orig_expr;

    step = array_ref_element_size (expr);
    if (!cst_and_fits_in_hwi (step))
break;

    st = int_cst_value (step);
    op1 = TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2854, __FUNCTION__)))));
    op1 = strip_offset_1 (op1, false, false, &off1);
    *offset = off1 * st;

    if (top_compref
 && integer_zerop (op1))
{
 /* Strip the component reference completely.  */
 op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2862, __FUNCTION__)))));
 op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
 *offset += off0;
 return op0;
}
    break;

  case COMPONENT_REF:
    {
tree field;

if (!inside_addr)
 return orig_expr;

tmp = component_ref_field_offset (expr);
field = TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2877, __FUNCTION__)))));
if (top_compref
   && cst_and_fits_in_hwi (tmp)
   && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field)((tree_check ((field), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2880, __FUNCTION__, (FIELD_DECL)))->field_decl.bit_offset
)))
 {
   HOST_WIDE_INTlong boffset, abs_off;

   /* Strip the component reference completely.  */
   op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2885, __FUNCTION__)))));
   op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
   boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field)((tree_check ((field), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2887, __FUNCTION__, (FIELD_DECL)))->field_decl.bit_offset
));
   abs_off = abs_hwi (boffset) / BITS_PER_UNIT(8);
   if (boffset < 0)
     abs_off = -abs_off;

   *offset = off0 + int_cst_value (tmp) + abs_off;
   return op0;
 }
    }
    break;

  case ADDR_EXPR:
    op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2899, __FUNCTION__)))));
    op0 = strip_offset_1 (op0, true, true, &off0);
    *offset += off0;

    if (op0 == TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2903, __FUNCTION__))))))
return orig_expr;

    expr = build_fold_addr_expr (op0)build_fold_addr_expr_loc (((location_t) 0), (op0));
    return fold_convert (orig_type, expr)fold_convert_loc (((location_t) 0), orig_type, expr);

  case MEM_REF:
    /* ???  Offset operand?  */
    inside_addr = false;
    break;

  default:
    if (ptrdiff_tree_p (expr, offset) && maybe_ne (*offset, 0))
return build_int_cst (orig_type, 0);
    return orig_expr;
  }

/* Default handling of expressions for that we want to recurse into
   the first operand.  */
op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2922, __FUNCTION__)))));
op0 = strip_offset_1 (op0, inside_addr, false, &off0);
*offset += off0;

if (op0 == TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2926, __FUNCTION__)))))
    && (!op1 || op1 == TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2927, __FUNCTION__)))))))
  return orig_expr;

expr = copy_node (expr);
TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2931, __FUNCTION__))))) = op0;
if (op1)
  TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2933, __FUNCTION__))))) = op1;

/* Inside address, we might strip the top level component references,
   thus changing type of the expression.  Handling of ADDR_EXPR
   will fix that.  */
expr = fold_convert (orig_type, expr)fold_convert_loc (((location_t) 0), orig_type, expr);

return expr;
2941}

2943/* Strips constant offsets from EXPR and stores them to OFFSET.  */

2945tree
2946strip_offset (tree expr, poly_uint64_pod *offset)
2947{
poly_int64 off;
tree core = strip_offset_1 (expr, false, false, &off);
*offset = off;
return core;
2952}

2954/* Returns variant of TYPE that can be used as base for different uses.
 We return unsigned type with the same precision, which avoids problems
 with overflows.  */

2958static tree
2959generic_type_for (tree type)
2960{
if (POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE))
  return unsigned_type_for (type);

if (TYPE_UNSIGNED (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2964, __FUNCTION__))->base.u.bits.unsigned_flag))
  return type;

return unsigned_type_for (type);
2968}

2970/* Private data for walk_tree.  */

2972struct walk_tree_data
2973{
bitmap *inv_vars;
struct ivopts_data *idata;
2976};

2978/* Callback function for walk_tree, it records invariants and symbol
 reference in *EXPR_P.  DATA is the structure storing result info.  */

2981static tree
2982find_inv_vars_cb (tree *expr_p, int *ws ATTRIBUTE_UNUSED__attribute__ ((__unused__)), void *data)
2983{
tree op = *expr_p;
struct version_info *info;
struct walk_tree_data *wdata = (struct walk_tree_data*) data;

if (TREE_CODE (op)((enum tree_code) (op)->base.code) != SSA_NAME)
  return NULL_TREE(tree) nullptr;

info = name_info (wdata->idata, op);
/* Because we expand simple operations when finding IVs, loop invariant
   variable that isn't referred by the original loop could be used now.
   Record such invariant variables here.  */
if (!info->iv)
  {
    struct ivopts_data *idata = wdata->idata;
    basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (op)(tree_check ((op), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 2998, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt);

    if (!bb || !flow_bb_inside_loop_p (idata->current_loop, bb))
{
 tree steptype = TREE_TYPE (op)((contains_struct_check ((op), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3002, __FUNCTION__))->typed.type);
 if (POINTER_TYPE_P (steptype)(((enum tree_code) (steptype)->base.code) == POINTER_TYPE ||
 ((enum tree_code) (steptype)->base.code) == REFERENCE_TYPE
))
   steptype = sizetypesizetype_tab[(int) stk_sizetype];
 set_iv (idata, op, op, build_int_cst (steptype, 0), true);
 record_invariant (idata, op, false);
}
  }
if (!info->inv_id || info->has_nonlin_use)
  return NULL_TREE(tree) nullptr;

if (!*wdata->inv_vars)
  *wdata->inv_vars = BITMAP_ALLOCbitmap_alloc (NULLnullptr);
bitmap_set_bit (*wdata->inv_vars, info->inv_id);

return NULL_TREE(tree) nullptr;
3017}

3019/* Records invariants in *EXPR_P.  INV_VARS is the bitmap to that we should
 store it.  */

3022static inline void
3023find_inv_vars (struct ivopts_data *data, tree *expr_p, bitmap *inv_vars)
3024{
struct walk_tree_data wdata;

if (!inv_vars)
  return;

wdata.idata = data;
wdata.inv_vars = inv_vars;
walk_tree (expr_p, find_inv_vars_cb, &wdata, NULL)walk_tree_1 (expr_p, find_inv_vars_cb, &wdata, nullptr, nullptr
);
3033}

3035/* Get entry from invariant expr hash table for INV_EXPR.  New entry
 will be recorded if it doesn't exist yet.  Given below two exprs:
   inv_expr + cst1, inv_expr + cst2
 It's hard to make decision whether constant part should be stripped
 or not.  We choose to not strip based on below facts:
   1) We need to count ADD cost for constant part if it's stripped,
which isn't always trivial where this functions is called.
   2) Stripping constant away may be conflict with following loop
invariant hoisting pass.
   3) Not stripping constant away results in more invariant exprs,
which usually leads to decision preferring lower reg pressure.  */

3047static iv_inv_expr_ent *
3048get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
3049{
STRIP_NOPS (inv_expr)(inv_expr) = tree_strip_nop_conversions ((const_cast<union
 tree_node *> (((inv_expr)))));

if (poly_int_tree_p (inv_expr)
    || TREE_CODE (inv_expr)((enum tree_code) (inv_expr)->base.code) == SSA_NAME)
  return NULLnullptr;

/* Don't strip constant part away as we used to.  */

/* Stores EXPR in DATA->inv_expr_tab, return pointer to iv_inv_expr_ent.  */
struct iv_inv_expr_ent ent;
ent.expr = inv_expr;
ent.hash = iterative_hash_expr (inv_expr, 0);
struct iv_inv_expr_ent **slot = data->inv_expr_tab->find_slot (&ent, INSERT);

if (!*slot)
  {
    *slot = XNEW (struct iv_inv_expr_ent)((struct iv_inv_expr_ent *) xmalloc (sizeof (struct iv_inv_expr_ent
)));
    (*slot)->expr = inv_expr;
    (*slot)->hash = ent.hash;
    (*slot)->id = ++data->max_inv_expr_id;
  }

return *slot;
3073}


3076/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as
 unsuitable as ivopts candidates for potentially involving undefined
 behavior.  */

3080static tree
3081find_ssa_undef (tree *tp, int *walk_subtrees, void *bb_)
3082{
basic_block bb = (basic_block) bb_;
if (TREE_CODE (*tp)((enum tree_code) (*tp)->base.code) == SSA_NAME
    && ssa_name_maybe_undef_p (*tp)
    && !ssa_name_any_use_dominates_bb_p (*tp, bb))
  return *tp;
if (!EXPR_P (*tp)((tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (*tp)->base.code))]) >= tcc_reference &&
 (tree_code_type_tmpl <0>::tree_code_type[(int) (((enum
 tree_code) (*tp)->base.code))]) <= tcc_expression))
  *walk_subtrees = 0;
return NULLnullptr;
3091}

3093/* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
 position to POS.  If USE is not NULL, the candidate is set as related to
 it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
 replacement of the final value of the iv by a direct computation.  */

3098static struct iv_cand *
3099add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
 enum iv_position pos, struct iv_use *use,
 gimple *incremented_at, struct iv *orig_iv = NULLnullptr,
 bool doloop = false)
3103{
unsigned i;
struct iv_cand *cand = NULLnullptr;
tree type, orig_type;

gcc_assert (base && step)((void)(!(base && step) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3108, __FUNCTION__), 0 : 0));

/* -fkeep-gc-roots-live means that we have to keep a real pointer
   live, but the ivopts code may replace a real pointer with one
   pointing before or after the memory block that is then adjusted
   into the memory block during the loop.  FIXME: It would likely be
   better to actually force the pointer live and still use ivopts;
   for example, it would be enough to write the pointer into memory
   and keep it there until after the loop.  */
if (flag_keep_gc_roots_liveglobal_options.x_flag_keep_gc_roots_live && POINTER_TYPE_P (TREE_TYPE (base))(((enum tree_code) (((contains_struct_check ((base), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3117, __FUNCTION__))->typed.type))->base.code) == POINTER_TYPE
 || ((enum tree_code) (((contains_struct_check ((base), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3117, __FUNCTION__))->typed.type))->base.code) == REFERENCE_TYPE
))
  return NULLnullptr;

/* If BASE contains undefined SSA names make sure we only record
   the original IV.  */
bool involves_undefs = false;
if (walk_tree (&base, find_ssa_undef, data->current_loop->header, NULL)walk_tree_1 (&base, find_ssa_undef, data->current_loop
->header, nullptr, nullptr))
  {
    if (pos != IP_ORIGINAL)
return NULLnullptr;
    important = false;
    involves_undefs = true;
  }

/* For non-original variables, make sure their values are computed in a type
   that does not invoke undefined behavior on overflows (since in general,
   we cannot prove that these induction variables are non-wrapping).  */
if (pos != IP_ORIGINAL)
  {
    orig_type = TREE_TYPE (base)((contains_struct_check ((base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3136, __FUNCTION__))->typed.type);
    type = generic_type_for (orig_type);
    if (type != orig_type)
{
 base = fold_convert (type, base)fold_convert_loc (((location_t) 0), type, base);
 step = fold_convert (type, step)fold_convert_loc (((location_t) 0), type, step);
}
  }

for (i = 0; i < data->vcands.length (); i++)
  {
    cand = data->vcands[i];

    if (cand->pos != pos)
continue;

    if (cand->incremented_at != incremented_at
 || ((pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
     && cand->ainc_use != use))
continue;

    if (operand_equal_p (base, cand->iv->base, 0)
 && operand_equal_p (step, cand->iv->step, 0)
 && (TYPE_PRECISION (TREE_TYPE (base))((tree_class_check ((((contains_struct_check ((base), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3159, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3159, __FUNCTION__))->type_common.precision)
     == TYPE_PRECISION (TREE_TYPE (cand->iv->base))((tree_class_check ((((contains_struct_check ((cand->iv->
base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3160, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3160, __FUNCTION__))->type_common.precision)))
break;
  }

if (i == data->vcands.length ())
  {
    cand = XCNEW (struct iv_cand)((struct iv_cand *) xcalloc (1, sizeof (struct iv_cand)));
    cand->id = i;
    cand->iv = alloc_iv (data, base, step);
    cand->pos = pos;
    if (pos != IP_ORIGINAL)
{
 if (doloop)
   cand->var_before = create_tmp_var_raw (TREE_TYPE (base)((contains_struct_check ((base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3173, __FUNCTION__))->typed.type), "doloop");
 else
   cand->var_before = create_tmp_var_raw (TREE_TYPE (base)((contains_struct_check ((base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3175, __FUNCTION__))->typed.type), "ivtmp");
 cand->var_after = cand->var_before;
}
    cand->important = important;
    cand->involves_undefs = involves_undefs;
    cand->incremented_at = incremented_at;
    cand->doloop_p = doloop;
    data->vcands.safe_push (cand);

    if (!poly_int_tree_p (step))
{
 find_inv_vars (data, &step, &cand->inv_vars);

 iv_inv_expr_ent *inv_expr = get_loop_invariant_expr (data, step);
 /* Share bitmap between inv_vars and inv_exprs for cand.  */
 if (inv_expr != NULLnullptr)
   {
     cand->inv_exprs = cand->inv_vars;
     cand->inv_vars = NULLnullptr;
     if (cand->inv_exprs)
bitmap_clear (cand->inv_exprs);
     else
cand->inv_exprs = BITMAP_ALLOCbitmap_alloc (NULLnullptr);

     bitmap_set_bit (cand->inv_exprs, inv_expr->id);
   }
}

    if (pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
cand->ainc_use = use;
    else
cand->ainc_use = NULLnullptr;

    cand->orig_iv = orig_iv;
    if (dump_file && (dump_flags & TDF_DETAILS))
dump_cand (dump_file, cand);
  }

cand->important |= important;
cand->doloop_p |= doloop;

/* Relate candidate to the group for which it is added.  */
if (use)
  bitmap_set_bit (data->vgroups[use->group_id]->related_cands, i);

return cand;
3221}

3223/* Returns true if incrementing the induction variable at the end of the LOOP
 is allowed.

 The purpose is to avoid splitting latch edge with a biv increment, thus
 creating a jump, possibly confusing other optimization passes and leaving
 less freedom to scheduler.  So we allow IP_END only if IP_NORMAL is not
 available (so we do not have a better alternative), or if the latch edge
 is already nonempty.  */

3232static bool
3233allow_ip_end_pos_p (class loop *loop)
3234{
if (!ip_normal_pos (loop))
  return true;

if (!empty_block_p (ip_end_pos (loop)))
  return true;

return false;
3242}

3244/* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
 Important field is set to IMPORTANT.  */

3247static void
3248add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
	bool important, struct iv_use *use)
3250{
basic_block use_bb = gimple_bb (use->stmt);
machine_mode mem_mode;
unsigned HOST_WIDE_INTlong cstepi;

/* If we insert the increment in any position other than the standard
   ones, we must ensure that it is incremented once per iteration.
   It must not be in an inner nested loop, or one side of an if
   statement.  */
if (use_bb->loop_father != data->current_loop
    || !dominated_by_p (CDI_DOMINATORS, data->current_loop->latch, use_bb)
    || stmt_can_throw_internal (cfun(cfun + 0), use->stmt)
    || !cst_and_fits_in_hwi (step))
  return;

cstepi = int_cst_value (step);

mem_mode = TYPE_MODE (use->mem_type)((((enum tree_code) ((tree_class_check ((use->mem_type), (
tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3267, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (use->mem_type) : (use->mem_type)->type_common.mode
);
if (((USE_LOAD_PRE_INCREMENT (mem_mode)0
|| USE_STORE_PRE_INCREMENT (mem_mode)0)
     && known_eq (GET_MODE_SIZE (mem_mode), cstepi)(!maybe_ne (GET_MODE_SIZE (mem_mode), cstepi)))
    || ((USE_LOAD_PRE_DECREMENT (mem_mode)0
  || USE_STORE_PRE_DECREMENT (mem_mode)0)
 && known_eq (GET_MODE_SIZE (mem_mode), -cstepi)(!maybe_ne (GET_MODE_SIZE (mem_mode), -cstepi))))
  {
    enum tree_code code = MINUS_EXPR;
    tree new_base;
    tree new_step = step;

    if (POINTER_TYPE_P (TREE_TYPE (base))(((enum tree_code) (((contains_struct_check ((base), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3279, __FUNCTION__))->typed.type))->base.code) == POINTER_TYPE
 || ((enum tree_code) (((contains_struct_check ((base), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3279, __FUNCTION__))->typed.type))->base.code) == REFERENCE_TYPE
))
{
 new_step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step)fold_build1_loc (((location_t) 0), NEGATE_EXPR, ((contains_struct_check
 ((step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3281, __FUNCTION__))->typed.type), step );
 code = POINTER_PLUS_EXPR;
}
    else
new_step = fold_convert (TREE_TYPE (base), new_step)fold_convert_loc (((location_t) 0), ((contains_struct_check (
(base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3285, __FUNCTION__))->typed.type), new_step);
    new_base = fold_build2 (code, TREE_TYPE (base), base, new_step)fold_build2_loc (((location_t) 0), code, ((contains_struct_check
 ((base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3286, __FUNCTION__))->typed.type), base, new_step );
    add_candidate_1 (data, new_base, step, important, IP_BEFORE_USE, use,
       use->stmt);
  }
if (((USE_LOAD_POST_INCREMENT (mem_mode)0
|| USE_STORE_POST_INCREMENT (mem_mode)0)
     && known_eq (GET_MODE_SIZE (mem_mode), cstepi)(!maybe_ne (GET_MODE_SIZE (mem_mode), cstepi)))
    || ((USE_LOAD_POST_DECREMENT (mem_mode)0
  || USE_STORE_POST_DECREMENT (mem_mode)0)
 && known_eq (GET_MODE_SIZE (mem_mode), -cstepi)(!maybe_ne (GET_MODE_SIZE (mem_mode), -cstepi))))
  {
    add_candidate_1 (data, base, step, important, IP_AFTER_USE, use,
       use->stmt);
  }
3300}

3302/* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
 position to POS.  If USE is not NULL, the candidate is set as related to
 it.  The candidate computation is scheduled before exit condition and at
 the end of loop.  */

3307static void
3308add_candidate (struct ivopts_data *data, tree base, tree step, bool important,
      struct iv_use *use, struct iv *orig_iv = NULLnullptr,
      bool doloop = false)
3311{
if (ip_normal_pos (data->current_loop))
  add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULLnullptr, orig_iv,
     doloop);
/* Exclude doloop candidate here since it requires decrement then comparison
   and jump, the IP_END position doesn't match.  */
if (!doloop && ip_end_pos (data->current_loop)
    && allow_ip_end_pos_p (data->current_loop))
  add_candidate_1 (data, base, step, important, IP_END, use, NULLnullptr, orig_iv);
3320}

3322/* Adds standard iv candidates.  */

3324static void
3325add_standard_iv_candidates (struct ivopts_data *data)
3326{
add_candidate (data, integer_zero_nodeglobal_trees[TI_INTEGER_ZERO], integer_one_nodeglobal_trees[TI_INTEGER_ONE], true, NULLnullptr);

/* The same for a double-integer type if it is still fast enough.  */
if (TYPE_PRECISION((tree_class_check ((integer_types[itk_long]), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3331, __FUNCTION__))->type_common.precision)
(long_integer_type_node)((tree_class_check ((integer_types[itk_long]), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3331, __FUNCTION__))->type_common.precision) > TYPE_PRECISION (integer_type_node)((tree_class_check ((integer_types[itk_int]), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3331, __FUNCTION__))->type_common.precision)
    && TYPE_PRECISION (long_integer_type_node)((tree_class_check ((integer_types[itk_long]), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3332, __FUNCTION__))->type_common.precision) <= BITS_PER_WORD((8) * (((global_options.x_ix86_isa_flags & (1UL <<
 1)) != 0) ? 8 : 4)))
  add_candidate (data, build_int_cst (long_integer_type_nodeinteger_types[itk_long], 0),
   build_int_cst (long_integer_type_nodeinteger_types[itk_long], 1), true, NULLnullptr);

/* The same for a double-integer type if it is still fast enough.  */
if (TYPE_PRECISION((tree_class_check ((integer_types[itk_long_long]), (tcc_type
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3338, __FUNCTION__))->type_common.precision)
(long_long_integer_type_node)((tree_class_check ((integer_types[itk_long_long]), (tcc_type
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3338, __FUNCTION__))->type_common.precision) > TYPE_PRECISION (long_integer_type_node)((tree_class_check ((integer_types[itk_long]), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3338, __FUNCTION__))->type_common.precision)
    && TYPE_PRECISION (long_long_integer_type_node)((tree_class_check ((integer_types[itk_long_long]), (tcc_type
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3339, __FUNCTION__))->type_common.precision) <= BITS_PER_WORD((8) * (((global_options.x_ix86_isa_flags & (1UL <<
 1)) != 0) ? 8 : 4)))
  add_candidate (data, build_int_cst (long_long_integer_type_nodeinteger_types[itk_long_long], 0),
   build_int_cst (long_long_integer_type_nodeinteger_types[itk_long_long], 1), true, NULLnullptr);
3342}


3345/* Adds candidates bases on the old induction variable IV.  */

3347static void
3348add_iv_candidate_for_biv (struct ivopts_data *data, struct iv *iv)
3349{
gimple *phi;
tree def;
struct iv_cand *cand;

/* Check if this biv is used in address type use.  */
if (iv->no_overflow  && iv->have_address_use
    && INTEGRAL_TYPE_P (TREE_TYPE (iv->base))(((enum tree_code) (((contains_struct_check ((iv->base), (
TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3356, __FUNCTION__))->typed.type))->base.code) == ENUMERAL_TYPE
 || ((enum tree_code) (((contains_struct_check ((iv->base)
, (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3356, __FUNCTION__))->typed.type))->base.code) == BOOLEAN_TYPE
 || ((enum tree_code) (((contains_struct_check ((iv->base)
, (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3356, __FUNCTION__))->typed.type))->base.code) == INTEGER_TYPE
)
    && TYPE_PRECISION (TREE_TYPE (iv->base))((tree_class_check ((((contains_struct_check ((iv->base), (
TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3357, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3357, __FUNCTION__))->type_common.precision) < TYPE_PRECISION (sizetype)((tree_class_check ((sizetype_tab[(int) stk_sizetype]), (tcc_type
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3357, __FUNCTION__))->type_common.precision))
  {
    tree base = fold_convert (sizetype, iv->base)fold_convert_loc (((location_t) 0), sizetype_tab[(int) stk_sizetype
], iv->base);
    tree step = fold_convert (sizetype, iv->step)fold_convert_loc (((location_t) 0), sizetype_tab[(int) stk_sizetype
], iv->step);

    /* Add iv cand of same precision as index part in TARGET_MEM_REF.  */
    add_candidate (data, base, step, true, NULLnullptr, iv);
    /* Add iv cand of the original type only if it has nonlinear use.  */
    if (iv->nonlin_use)
add_candidate (data, iv->base, iv->step, true, NULLnullptr);
  }
else
  add_candidate (data, iv->base, iv->step, true, NULLnullptr);

/* The same, but with initial value zero.  */
if (POINTER_TYPE_P (TREE_TYPE (iv->base))(((enum tree_code) (((contains_struct_check ((iv->base), (
TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3372, __FUNCTION__))->typed.type))->base.code) == POINTER_TYPE
 || ((enum tree_code) (((contains_struct_check ((iv->base)
, (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3372, __FUNCTION__))->typed.type))->base.code) == REFERENCE_TYPE
))
  add_candidate (data, size_int (0)size_int_kind (0, stk_sizetype), iv->step, true, NULLnullptr);
else
  add_candidate (data, build_int_cst (TREE_TYPE (iv->base)((contains_struct_check ((iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3375, __FUNCTION__))->typed.type), 0),
   iv->step, true, NULLnullptr);

phi = SSA_NAME_DEF_STMT (iv->ssa_name)(tree_check ((iv->ssa_name), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3378, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
if (gimple_code (phi) == GIMPLE_PHI)
  {
    /* Additionally record the possibility of leaving the original iv
untouched.  */
    def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop))gimple_phi_arg_def (((phi)), ((loop_latch_edge (data->current_loop
))->dest_idx));
    /* Don't add candidate if it's from another PHI node because
it's an affine iv appearing in the form of PEELED_CHREC.  */
    phi = SSA_NAME_DEF_STMT (def)(tree_check ((def), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3386, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
    if (gimple_code (phi) != GIMPLE_PHI)
{
 cand = add_candidate_1 (data,
		  iv->base, iv->step, true, IP_ORIGINAL, NULLnullptr,
		  SSA_NAME_DEF_STMT (def)(tree_check ((def), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3391, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt);
 if (cand)
   {
     cand->var_before = iv->ssa_name;
     cand->var_after = def;
   }
}
    else
gcc_assert (gimple_bb (phi) == data->current_loop->header)((void)(!(gimple_bb (phi) == data->current_loop->header
) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3399, __FUNCTION__), 0 : 0));
  }
3401}

3403/* Adds candidates based on the old induction variables.  */

3405static void
3406add_iv_candidate_for_bivs (struct ivopts_data *data)
3407{
unsigned i;
struct iv *iv;
bitmap_iterator bi;

EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)for (bmp_iter_set_init (&(bi), (data->relevant), (0), &
(i)); bmp_iter_set (&(bi), &(i)); bmp_iter_next (&
(bi), &(i)))
  {
    iv = ver_info (data, i)->iv;
    if (iv && iv->biv_p && !integer_zerop (iv->step))
add_iv_candidate_for_biv (data, iv);
  }
3418}

3420/* Record common candidate {BASE, STEP} derived from USE in hashtable.  */

3422static void
3423record_common_cand (struct ivopts_data *data, tree base,
    tree step, struct iv_use *use)
3425{
class iv_common_cand ent;
class iv_common_cand **slot;

ent.base = base;
ent.step = step;
ent.hash = iterative_hash_expr (base, 0);
ent.hash = iterative_hash_expr (step, ent.hash);

slot = data->iv_common_cand_tab->find_slot (&ent, INSERT);
if (*slot == NULLnullptr)
  {
    *slot = new iv_common_cand ();
    (*slot)->base = base;
    (*slot)->step = step;
    (*slot)->uses.create (8);
    (*slot)->hash = ent.hash;
    data->iv_common_cands.safe_push ((*slot));
  }

gcc_assert (use != NULL)((void)(!(use != nullptr) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3445, __FUNCTION__), 0 : 0));
(*slot)->uses.safe_push (use);
return;
3448}

3450/* Comparison function used to sort common candidates.  */

3452static int
3453common_cand_cmp (const void *p1, const void *p2)
3454{
unsigned n1, n2;
const class iv_common_cand *const *const ccand1
  = (const class iv_common_cand *const *)p1;
const class iv_common_cand *const *const ccand2
  = (const class iv_common_cand *const *)p2;

n1 = (*ccand1)->uses.length ();
n2 = (*ccand2)->uses.length ();
return n2 - n1;
3464}

3466/* Adds IV candidates based on common candidated recorded.  */

3468static void
3469add_iv_candidate_derived_from_uses (struct ivopts_data *data)
3470{
unsigned i, j;
struct iv_cand *cand_1, *cand_2;

data->iv_common_cands.qsort (common_cand_cmp)qsort (common_cand_cmp);
for (i = 0; i < data->iv_common_cands.length (); i++)
  {
    class iv_common_cand *ptr = data->iv_common_cands[i];

    /* Only add IV candidate if it's derived from multiple uses.  */
    if (ptr->uses.length () <= 1)
break;

    cand_1 = NULLnullptr;
    cand_2 = NULLnullptr;
    if (ip_normal_pos (data->current_loop))
cand_1 = add_candidate_1 (data, ptr->base, ptr->step,
		  false, IP_NORMAL, NULLnullptr, NULLnullptr);

    if (ip_end_pos (data->current_loop)
 && allow_ip_end_pos_p (data->current_loop))
cand_2 = add_candidate_1 (data, ptr->base, ptr->step,
		  false, IP_END, NULLnullptr, NULLnullptr);

    /* Bind deriving uses and the new candidates.  */
    for (j = 0; j < ptr->uses.length (); j++)
{
 struct iv_group *group = data->vgroups[ptr->uses[j]->group_id];
 if (cand_1)
   bitmap_set_bit (group->related_cands, cand_1->id);
 if (cand_2)
   bitmap_set_bit (group->related_cands, cand_2->id);
}
  }

/* Release data since it is useless from this point.  */
data->iv_common_cand_tab->empty ();
data->iv_common_cands.truncate (0);
3508}

3510/* Adds candidates based on the value of USE's iv.  */

3512static void
3513add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use)
3514{
poly_uint64 offset;
tree base;
struct iv *iv = use->iv;
tree basetype = TREE_TYPE (iv->base)((contains_struct_check ((iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3518, __FUNCTION__))->typed.type);

/* Don't add candidate for iv_use with non integer, pointer or non-mode
   precision types, instead, add candidate for the corresponding scev in
   unsigned type with the same precision.  See PR93674 for more info.  */
if ((TREE_CODE (basetype)((enum tree_code) (basetype)->base.code) != INTEGER_TYPE && !POINTER_TYPE_P (basetype)(((enum tree_code) (basetype)->base.code) == POINTER_TYPE ||
 ((enum tree_code) (basetype)->base.code) == REFERENCE_TYPE
))
    || !type_has_mode_precision_p (basetype))
  {
    basetype = lang_hooks.types.type_for_mode (TYPE_MODE (basetype)((((enum tree_code) ((tree_class_check ((basetype), (tcc_type
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3526, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (basetype) : (basetype)->type_common.mode),
				 TYPE_UNSIGNED (basetype)((tree_class_check ((basetype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3527, __FUNCTION__))->base.u.bits.unsigned_flag));
    add_candidate (data, fold_convert (basetype, iv->base)fold_convert_loc (((location_t) 0), basetype, iv->base),
     fold_convert (basetype, iv->step)fold_convert_loc (((location_t) 0), basetype, iv->step), false, NULLnullptr);
    return;
  }

add_candidate (data, iv->base, iv->step, false, use);

/* Record common candidate for use in case it can be shared by others.  */
record_common_cand (data, iv->base, iv->step, use);

/* Record common candidate with initial value zero.  */
basetype = TREE_TYPE (iv->base)((contains_struct_check ((iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3539, __FUNCTION__))->typed.type);
if (POINTER_TYPE_P (basetype)(((enum tree_code) (basetype)->base.code) == POINTER_TYPE ||
 ((enum tree_code) (basetype)->base.code) == REFERENCE_TYPE
))
  basetype = sizetypesizetype_tab[(int) stk_sizetype];
record_common_cand (data, build_int_cst (basetype, 0), iv->step, use);

/* Compare the cost of an address with an unscaled index with the cost of
  an address with a scaled index and add candidate if useful.  */
poly_int64 step;
if (use != NULLnullptr
    && poly_int_tree_p (iv->step, &step)
    && address_p (use->type))
  {
    poly_int64 new_step;
    unsigned int fact = preferred_mem_scale_factor
(use->iv->base,
TYPE_MODE (use->mem_type)((((enum tree_code) ((tree_class_check ((use->mem_type), (
tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3554, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (use->mem_type) : (use->mem_type)->type_common.mode
),
optimize_loop_for_speed_p (data->current_loop));

    if (fact != 1
 && multiple_p (step, fact, &new_step))
add_candidate (data, size_int (0)size_int_kind (0, stk_sizetype),
       wide_int_to_tree (sizetypesizetype_tab[(int) stk_sizetype], new_step),
       true, NULLnullptr);
  }

/* Record common candidate with constant offset stripped in base.
   Like the use itself, we also add candidate directly for it.  */
base = strip_offset (iv->base, &offset);
if (maybe_ne (offset, 0U) || base != iv->base)
  {
    record_common_cand (data, base, iv->step, use);
    add_candidate (data, base, iv->step, false, use);
  }

/* Record common candidate with base_object removed in base.  */
base = iv->base;
STRIP_NOPS (base)(base) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((base)))));
if (iv->base_object != NULLnullptr && TREE_CODE (base)((enum tree_code) (base)->base.code) == POINTER_PLUS_EXPR)
  {
    tree step = iv->step;

    STRIP_NOPS (step)(step) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((step)))));
    base = TREE_OPERAND (base, 1)(*((const_cast<tree*> (tree_operand_check ((base), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3581, __FUNCTION__)))));
    step = fold_convert (sizetype, step)fold_convert_loc (((location_t) 0), sizetype_tab[(int) stk_sizetype
], step);
    record_common_cand (data, base, step, use);
    /* Also record common candidate with offset stripped.  */
    base = strip_offset (base, &offset);
    if (maybe_ne (offset, 0U))
record_common_cand (data, base, step, use);
  }

/* At last, add auto-incremental candidates.  Make such variables
   important since other iv uses with same base object may be based
   on it.  */
if (use != NULLnullptr && address_p (use->type))
  add_autoinc_candidates (data, iv->base, iv->step, true, use);
3595}

3597/* Adds candidates based on the uses.  */

3599static void
3600add_iv_candidate_for_groups (struct ivopts_data *data)
3601{
unsigned i;

/* Only add candidate for the first use in group.  */
for (i = 0; i < data->vgroups.length (); i++)
  {
    struct iv_group *group = data->vgroups[i];

    gcc_assert (group->vuses[0] != NULL)((void)(!(group->vuses[0] != nullptr) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3609, __FUNCTION__), 0 : 0));
    add_iv_candidate_for_use (data, group->vuses[0]);
  }
add_iv_candidate_derived_from_uses (data);
3613}

3615/* Record important candidates and add them to related_cands bitmaps.  */

3617static void
3618record_important_candidates (struct ivopts_data *data)
3619{
unsigned i;
struct iv_group *group;

for (i = 0; i < data->vcands.length (); i++)
  {
    struct iv_cand *cand = data->vcands[i];

    if (cand->important)
bitmap_set_bit (data->important_candidates, i);
  }

data->consider_all_candidates = (data->vcands.length ()
		   <= CONSIDER_ALL_CANDIDATES_BOUND((unsigned) global_options.x_param_iv_consider_all_candidates_bound
));

/* Add important candidates to groups' related_cands bitmaps.  */
for (i = 0; i < data->vgroups.length (); i++)
  {
    group = data->vgroups[i];
    bitmap_ior_into (group->related_cands, data->important_candidates);
  }
3640}

3642/* Allocates the data structure mapping the (use, candidate) pairs to costs.
 If consider_all_candidates is true, we use a two-dimensional array, otherwise
 we allocate a simple list to every use.  */

3646static void
3647alloc_use_cost_map (struct ivopts_data *data)
3648{
unsigned i, size, s;

for (i = 0; i < data->vgroups.length (); i++)
  {
    struct iv_group *group = data->vgroups[i];

    if (data->consider_all_candidates)
size = data->vcands.length ();
    else
{
 s = bitmap_count_bits (group->related_cands);

 /* Round up to the power of two, so that moduling by it is fast.  */
 size = s ? (1 << ceil_log2 (s)) : 1;
}

    group->n_map_members = size;
    group->cost_map = XCNEWVEC (class cost_pair, size)((class cost_pair *) xcalloc ((size), sizeof (class cost_pair
)));
  }
3668}

3670/* Sets cost of (GROUP, CAND) pair to COST and record that it depends
 on invariants INV_VARS and that the value used in expressing it is
 VALUE, and in case of iv elimination the comparison operator is COMP.  */

3674static void
3675set_group_iv_cost (struct ivopts_data *data,
   struct iv_group *group, struct iv_cand *cand,
   comp_cost cost, bitmap inv_vars, tree value,
   enum tree_code comp, bitmap inv_exprs)
3679{
unsigned i, s;

if (cost.infinite_cost_p ())
  {
    BITMAP_FREE (inv_vars)((void) (bitmap_obstack_free ((bitmap) inv_vars), (inv_vars) =
 (bitmap) nullptr));
    BITMAP_FREE (inv_exprs)((void) (bitmap_obstack_free ((bitmap) inv_exprs), (inv_exprs
) = (bitmap) nullptr));
    return;
  }

if (data->consider_all_candidates)
  {
    group->cost_map[cand->id].cand = cand;
    group->cost_map[cand->id].cost = cost;
    group->cost_map[cand->id].inv_vars = inv_vars;
    group->cost_map[cand->id].inv_exprs = inv_exprs;
    group->cost_map[cand->id].value = value;
    group->cost_map[cand->id].comp = comp;
    return;
  }

/* n_map_members is a power of two, so this computes modulo.  */
s = cand->id & (group->n_map_members - 1);
for (i = s; i < group->n_map_members; i++)
  if (!group->cost_map[i].cand)
    goto found;
for (i = 0; i < s; i++)
  if (!group->cost_map[i].cand)
    goto found;

gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3709, __FUNCTION__));

3711found:
group->cost_map[i].cand = cand;
group->cost_map[i].cost = cost;
group->cost_map[i].inv_vars = inv_vars;
group->cost_map[i].inv_exprs = inv_exprs;
group->cost_map[i].value = value;
group->cost_map[i].comp = comp;
3718}

3720/* Gets cost of (GROUP, CAND) pair.  */

3722static class cost_pair *
3723get_group_iv_cost (struct ivopts_data *data, struct iv_group *group,
   struct iv_cand *cand)
3725{
unsigned i, s;
class cost_pair *ret;

if (!cand)
  return NULLnullptr;

if (data->consider_all_candidates)
  {
    ret = group->cost_map + cand->id;
    if (!ret->cand)
return NULLnullptr;

    return ret;
  }

/* n_map_members is a power of two, so this computes modulo.  */
s = cand->id & (group->n_map_members - 1);
for (i = s; i < group->n_map_members; i++)
  if (group->cost_map[i].cand == cand)
    return group->cost_map + i;
  else if (group->cost_map[i].cand == NULLnullptr)
    return NULLnullptr;
for (i = 0; i < s; i++)
  if (group->cost_map[i].cand == cand)
    return group->cost_map + i;
  else if (group->cost_map[i].cand == NULLnullptr)
    return NULLnullptr;

return NULLnullptr;
3755}

3757/* Produce DECL_RTL for object obj so it looks like it is stored in memory.  */
3758static rtx
3759produce_memory_decl_rtl (tree obj, int *regno)
3760{
addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (obj))((tree_class_check ((((contains_struct_check ((obj), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3761, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3761, __FUNCTION__))->base.u.bits.address_space);
machine_mode address_mode = targetm.addr_space.address_mode (as);
rtx x;

gcc_assert (obj)((void)(!(obj) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3765, __FUNCTION__), 0 : 0));
if (TREE_STATIC (obj)((obj)->base.static_flag) || DECL_EXTERNAL (obj)((contains_struct_check ((obj), (TS_DECL_COMMON), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3766, __FUNCTION__))->decl_common.decl_flag_1))
  {
    const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj))((const char *) (tree_check ((decl_assembler_name (obj)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3768, __FUNCTION__, (IDENTIFIER_NODE)))->identifier.id.str
);
    x = gen_rtx_SYMBOL_REF (address_mode, name)gen_rtx_fmt_s0_stat ((SYMBOL_REF), ((address_mode)), ((name))
 );
    SET_SYMBOL_REF_DECL (x, obj)(((void)(!(!(__extension__ ({ __typeof ((x)) const _rtx = ((x
)); if (((enum rtx_code) (_rtx)->code) != SYMBOL_REF) rtl_check_failed_flag
 ("CONSTANT_POOL_ADDRESS_P", _rtx, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3770, __FUNCTION__); _rtx; })->unchanging)) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3770, __FUNCTION__), 0 : 0)), ((((x))->u.fld[1]).rt_tree
) = (obj));
    x = gen_rtx_MEM (DECL_MODE (obj)((contains_struct_check ((obj), (TS_DECL_COMMON), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3771, __FUNCTION__))->decl_common.mode), x);
    set_mem_addr_space (x, as);
    targetm.encode_section_info (obj, x, true);
  }
else
  {
    x = gen_raw_REG (address_mode, (*regno)++);
    x = gen_rtx_MEM (DECL_MODE (obj)((contains_struct_check ((obj), (TS_DECL_COMMON), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3778, __FUNCTION__))->decl_common.mode), x);
    set_mem_addr_space (x, as);
  }

return x;
3783}

3785/* Prepares decl_rtl for variables referred in *EXPR_P.  Callback for
 walk_tree.  DATA contains the actual fake register number.  */

3788static tree
3789prepare_decl_rtl (tree *expr_p, int *ws, void *data)
3790{
tree obj = NULL_TREE(tree) nullptr;
rtx x = NULL_RTX(rtx) 0;
int *regno = (int *) data;

switch (TREE_CODE (*expr_p)((enum tree_code) (*expr_p)->base.code))
  {
  case ADDR_EXPR:
    for (expr_p = &TREE_OPERAND (*expr_p, 0)(*((const_cast<tree*> (tree_operand_check ((*expr_p), (
0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3798, __FUNCTION__)))));
  handled_component_p (*expr_p);
  expr_p = &TREE_OPERAND (*expr_p, 0)(*((const_cast<tree*> (tree_operand_check ((*expr_p), (
0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3800, __FUNCTION__))))))
continue;
    obj = *expr_p;
    if (DECL_P (obj)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (obj)->base.code))] == tcc_declaration) && HAS_RTL_P (obj)((tree_contains_struct[(((enum tree_code) (obj)->base.code
))][(TS_DECL_WRTL)])) && !DECL_RTL_SET_P (obj)(((tree_contains_struct[(((enum tree_code) (obj)->base.code
))][(TS_DECL_WRTL)])) && (contains_struct_check ((obj
), (TS_DECL_WRTL), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3803, __FUNCTION__))->decl_with_rtl.rtl != nullptr))
x = produce_memory_decl_rtl (obj, regno);
    break;

  case SSA_NAME:
    *ws = 0;
    obj = SSA_NAME_VAR (*expr_p)((tree_check ((*expr_p), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3809, __FUNCTION__, (SSA_NAME)))->ssa_name.var == (tree)
 nullptr || ((enum tree_code) ((*expr_p)->ssa_name.var)->
base.code) == IDENTIFIER_NODE ? (tree) nullptr : (*expr_p)->
ssa_name.var);
    /* Defer handling of anonymous SSA_NAMEs to the expander.  */
    if (!obj)
return NULL_TREE(tree) nullptr;
    if (!DECL_RTL_SET_P (obj)(((tree_contains_struct[(((enum tree_code) (obj)->base.code
))][(TS_DECL_WRTL)])) && (contains_struct_check ((obj
), (TS_DECL_WRTL), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3813, __FUNCTION__))->decl_with_rtl.rtl != nullptr))
x = gen_raw_REG (DECL_MODE (obj)((contains_struct_check ((obj), (TS_DECL_COMMON), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3814, __FUNCTION__))->decl_common.mode), (*regno)++);
    break;

  case VAR_DECL:
  case PARM_DECL:
  case RESULT_DECL:
    *ws = 0;
    obj = *expr_p;

    if (DECL_RTL_SET_P (obj)(((tree_contains_struct[(((enum tree_code) (obj)->base.code
))][(TS_DECL_WRTL)])) && (contains_struct_check ((obj
), (TS_DECL_WRTL), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3823, __FUNCTION__))->decl_with_rtl.rtl != nullptr))
break;

    if (DECL_MODE (obj)((contains_struct_check ((obj), (TS_DECL_COMMON), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3826, __FUNCTION__))->decl_common.mode) == BLKmode((void) 0, E_BLKmode))
x = produce_memory_decl_rtl (obj, regno);
    else
x = gen_raw_REG (DECL_MODE (obj)((contains_struct_check ((obj), (TS_DECL_COMMON), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3829, __FUNCTION__))->decl_common.mode), (*regno)++);

    break;

  default:
    break;
  }

if (x)
  {
    decl_rtl_to_reset.safe_push (obj);
    SET_DECL_RTL (obj, x)set_decl_rtl (obj, x);
  }

return NULL_TREE(tree) nullptr;
3844}

3846/* Predict whether the given loop will be transformed in the RTL
 doloop_optimize pass.  Attempt to duplicate some doloop_optimize checks.
 This is only for target independent checks, see targetm.predict_doloop_p
 for the target dependent ones.

 Note that according to some initial investigation, some checks like costly
 niter check and invalid stmt scanning don't have much gains among general
 cases, so keep this as simple as possible first.

 Some RTL specific checks seems unable to be checked in gimple, if any new
 checks or easy checks _are_ missing here, please add them.  */

3858static bool
3859generic_predict_doloop_p (struct ivopts_data *data)
3860{
class loop *loop = data->current_loop;

/* Call target hook for target dependent checks.  */
if (!targetm.predict_doloop_p (loop))
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Predict doloop failure due to"
	    " target specific checks.\n");
    return false;
  }

/* Similar to doloop_optimize, check iteration description to know it's
   suitable or not.  Keep it as simple as possible, feel free to extend it
   if you find any multiple exits cases matter.  */
edge exit = single_dom_exit (loop);
class tree_niter_desc *niter_desc;
if (!exit || !(niter_desc = niter_for_exit (data, exit)))
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Predict doloop failure due to"
	    " unexpected niters.\n");
    return false;
  }

/* Similar to doloop_optimize, check whether iteration count too small
   and not profitable.  */
HOST_WIDE_INTlong est_niter = get_estimated_loop_iterations_int (loop);
if (est_niter == -1)
  est_niter = get_likely_max_loop_iterations_int (loop);
if (est_niter >= 0 && est_niter < 3)
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
 "Predict doloop failure due to"
 " too few iterations (%u).\n",
 (unsigned int) est_niter);
    return false;
  }

return true;
3901}

3903/* Determines cost of the computation of EXPR.  */

3905static unsigned
3906computation_cost (tree expr, bool speed)
3907{
rtx_insn *seq;
rtx rslt;
tree type = TREE_TYPE (expr)((contains_struct_check ((expr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3910, __FUNCTION__))->typed.type);
unsigned cost;
/* Avoid using hard regs in ways which may be unsupported.  */
int regno = LAST_VIRTUAL_REGISTER(((76)) + 5) + 1;
struct cgraph_node *node = cgraph_node::get (current_function_decl);
enum node_frequency real_frequency = node->frequency;

node->frequency = NODE_FREQUENCY_NORMAL;
crtl(&x_rtl)->maybe_hot_insn_p = speed;
walk_tree (&expr, prepare_decl_rtl, &regno, NULL)walk_tree_1 (&expr, prepare_decl_rtl, &regno, nullptr
, nullptr);
start_sequence ();
rslt = expand_expr (expr, NULL_RTX(rtx) 0, TYPE_MODE (type)((((enum tree_code) ((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3921, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (type) : (type)->type_common.mode), EXPAND_NORMAL);
seq = get_insns ();
end_sequence ();
default_rtl_profile ();
node->frequency = real_frequency;

cost = seq_cost (seq, speed);
if (MEM_P (rslt)(((enum rtx_code) (rslt)->code) == MEM))
  cost += address_cost (XEXP (rslt, 0)(((rslt)->u.fld[0]).rt_rtx), TYPE_MODE (type)((((enum tree_code) ((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3929, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (type) : (type)->type_common.mode),
	  TYPE_ADDR_SPACE (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3930, __FUNCTION__))->base.u.bits.address_space), speed);
else if (!REG_P (rslt)(((enum rtx_code) (rslt)->code) == REG))
  cost += set_src_cost (rslt, TYPE_MODE (type)((((enum tree_code) ((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3932, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (type) : (type)->type_common.mode), speed);

return cost;
3935}

3937/* Returns variable containing the value of candidate CAND at statement AT.  */

3939static tree
3940var_at_stmt (class loop *loop, struct iv_cand *cand, gimple *stmt)
3941{
if (stmt_after_increment (loop, cand, stmt))
  return cand->var_after;
else
  return cand->var_before;
3946}

3948/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
 same precision that is at least as wide as the precision of TYPE, stores
 BA to A and BB to B, and returns the type of BA.  Otherwise, returns the
 type of A and B.  */

3953static tree
3954determine_common_wider_type (tree *a, tree *b)
3955{
tree wider_type = NULLnullptr;
tree suba, subb;
tree atype = TREE_TYPE (*a)((contains_struct_check ((*a), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3958, __FUNCTION__))->typed.type);

if (CONVERT_EXPR_P (*a)((((enum tree_code) (*a)->base.code)) == NOP_EXPR || (((enum
 tree_code) (*a)->base.code)) == CONVERT_EXPR))
  {
    suba = TREE_OPERAND (*a, 0)(*((const_cast<tree*> (tree_operand_check ((*a), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3962, __FUNCTION__)))));
    wider_type = TREE_TYPE (suba)((contains_struct_check ((suba), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3963, __FUNCTION__))->typed.type);
    if (TYPE_PRECISION (wider_type)((tree_class_check ((wider_type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3964, __FUNCTION__))->type_common.precision) < TYPE_PRECISION (atype)((tree_class_check ((atype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3964, __FUNCTION__))->type_common.precision))
return atype;
  }
else
  return atype;

if (CONVERT_EXPR_P (*b)((((enum tree_code) (*b)->base.code)) == NOP_EXPR || (((enum
 tree_code) (*b)->base.code)) == CONVERT_EXPR))
  {
    subb = TREE_OPERAND (*b, 0)(*((const_cast<tree*> (tree_operand_check ((*b), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3972, __FUNCTION__)))));
    if (TYPE_PRECISION (wider_type)((tree_class_check ((wider_type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3973, __FUNCTION__))->type_common.precision) != TYPE_PRECISION (TREE_TYPE (subb))((tree_class_check ((((contains_struct_check ((subb), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3973, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3973, __FUNCTION__))->type_common.precision))
return atype;
  }
else
  return atype;

*a = suba;
*b = subb;
return wider_type;
3982}

3984/* Determines the expression by that USE is expressed from induction variable
 CAND at statement AT in LOOP.  The expression is stored in two parts in a
 decomposed form.  The invariant part is stored in AFF_INV; while variant
 part in AFF_VAR.  Store ratio of CAND.step over USE.step in PRAT if it's
 non-null.  Returns false if USE cannot be expressed using CAND.  */

3990static bool
3991get_computation_aff_1 (class loop *loop, gimple *at, struct iv_use *use,
       struct iv_cand *cand, class aff_tree *aff_inv,
       class aff_tree *aff_var, widest_int *prat = NULLnullptr)
3994{
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase = cand->iv->base, cstep = cand->iv->step;
tree common_type, uutype, var, cstep_common;
tree utype = TREE_TYPE (ubase)((contains_struct_check ((ubase), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3998, __FUNCTION__))->typed.type), ctype = TREE_TYPE (cbase)((contains_struct_check ((cbase), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 3998, __FUNCTION__))->typed.type);
aff_tree aff_cbase;
widest_int rat;

/* We must have a precision to express the values of use.  */
if (TYPE_PRECISION (utype)((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4003, __FUNCTION__))->type_common.precision) > TYPE_PRECISION (ctype)((tree_class_check ((ctype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4003, __FUNCTION__))->type_common.precision))
  return false;

var = var_at_stmt (loop, cand, at);
uutype = unsigned_type_for (utype);

/* If the conversion is not noop, perform it.  */
if (TYPE_PRECISION (utype)((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4010, __FUNCTION__))->type_common.precision) < TYPE_PRECISION (ctype)((tree_class_check ((ctype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4010, __FUNCTION__))->type_common.precision))
  {
    if (cand->orig_iv != NULLnullptr && CONVERT_EXPR_P (cbase)((((enum tree_code) (cbase)->base.code)) == NOP_EXPR || ((
(enum tree_code) (cbase)->base.code)) == CONVERT_EXPR)
 && (CONVERT_EXPR_P (cstep)((((enum tree_code) (cstep)->base.code)) == NOP_EXPR || ((
(enum tree_code) (cstep)->base.code)) == CONVERT_EXPR) || poly_int_tree_p (cstep)))
{
 tree inner_base, inner_step, inner_type;
 inner_base = TREE_OPERAND (cbase, 0)(*((const_cast<tree*> (tree_operand_check ((cbase), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4016, __FUNCTION__)))));
 if (CONVERT_EXPR_P (cstep)((((enum tree_code) (cstep)->base.code)) == NOP_EXPR || ((
(enum tree_code) (cstep)->base.code)) == CONVERT_EXPR))
   inner_step = TREE_OPERAND (cstep, 0)(*((const_cast<tree*> (tree_operand_check ((cstep), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4018, __FUNCTION__)))));
 else
   inner_step = cstep;

 inner_type = TREE_TYPE (inner_base)((contains_struct_check ((inner_base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4022, __FUNCTION__))->typed.type);
 /* If candidate is added from a biv whose type is smaller than
    ctype, we know both candidate and the biv won't overflow.
    In this case, it's safe to skip the convertion in candidate.
    As an example, (unsigned short)((unsigned long)A) equals to
    (unsigned short)A, if A has a type no larger than short.  */
 if (TYPE_PRECISION (inner_type)((tree_class_check ((inner_type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4028, __FUNCTION__))->type_common.precision) <= TYPE_PRECISION (uutype)((tree_class_check ((uutype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4028, __FUNCTION__))->type_common.precision))
   {
     cbase = inner_base;
     cstep = inner_step;
   }
}
    cbase = fold_convert (uutype, cbase)fold_convert_loc (((location_t) 0), uutype, cbase);
    cstep = fold_convert (uutype, cstep)fold_convert_loc (((location_t) 0), uutype, cstep);
    var = fold_convert (uutype, var)fold_convert_loc (((location_t) 0), uutype, var);
  }

/* Ratio is 1 when computing the value of biv cand by itself.
   We can't rely on constant_multiple_of in this case because the
   use is created after the original biv is selected.  The call
   could fail because of inconsistent fold behavior.  See PR68021
   for more information.  */
if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
  {
    gcc_assert (is_gimple_assign (use->stmt))((void)(!(is_gimple_assign (use->stmt)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4046, __FUNCTION__), 0 : 0));
    gcc_assert (use->iv->ssa_name == cand->var_after)((void)(!(use->iv->ssa_name == cand->var_after) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4047, __FUNCTION__), 0 : 0));
    gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after)((void)(!(gimple_assign_lhs (use->stmt) == cand->var_after
) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4048, __FUNCTION__), 0 : 0));
    rat = 1;
  }
else if (!constant_multiple_of (ustep, cstep, &rat))
  return false;

if (prat)
  *prat = rat;

/* In case both UBASE and CBASE are shortened to UUTYPE from some common
   type, we achieve better folding by computing their difference in this
   wider type, and cast the result to UUTYPE.  We do not need to worry about
   overflows, as all the arithmetics will in the end be performed in UUTYPE
   anyway.  */
common_type = determine_common_wider_type (&ubase, &cbase);

/* use = ubase - ratio * cbase + ratio * var.  */
tree_to_aff_combination (ubase, common_type, aff_inv);
tree_to_aff_combination (cbase, common_type, &aff_cbase);
tree_to_aff_combination (var, uutype, aff_var);

/* We need to shift the value if we are after the increment.  */
if (stmt_after_increment (loop, cand, at))
  {
    aff_tree cstep_aff;

    if (common_type != uutype)
cstep_common = fold_convert (common_type, cstep)fold_convert_loc (((location_t) 0), common_type, cstep);
    else
cstep_common = cstep;

    tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
    aff_combination_add (&aff_cbase, &cstep_aff);
  }

aff_combination_scale (&aff_cbase, -rat);
aff_combination_add (aff_inv, &aff_cbase);
if (common_type != uutype)
  aff_combination_convert (aff_inv, uutype);

aff_combination_scale (aff_var, rat);
return true;
4090}

4092/* Determines the expression by that USE is expressed from induction variable
 CAND at statement AT in LOOP.  The expression is stored in a decomposed
 form into AFF.  Returns false if USE cannot be expressed using CAND.  */

4096static bool
4097get_computation_aff (class loop *loop, gimple *at, struct iv_use *use,
     struct iv_cand *cand, class aff_tree *aff)
4099{
aff_tree aff_var;

if (!get_computation_aff_1 (loop, at, use, cand, aff, &aff_var))
  return false;

aff_combination_add (aff, &aff_var);
return true;
4107}

4109/* Return the type of USE.  */

4111static tree
4112get_use_type (struct iv_use *use)
4113{
tree base_type = TREE_TYPE (use->iv->base)((contains_struct_check ((use->iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4114, __FUNCTION__))->typed.type);
tree type;

if (use->type == USE_REF_ADDRESS)
  {
    /* The base_type may be a void pointer.  Create a pointer type based on
the mem_ref instead.  */
    type = build_pointer_type (TREE_TYPE (*use->op_p)((contains_struct_check ((*use->op_p), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4121, __FUNCTION__))->typed.type));
    gcc_assert (TYPE_ADDR_SPACE (TREE_TYPE (type))((void)(!(((tree_class_check ((((contains_struct_check ((type
), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4122, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4122, __FUNCTION__))->base.u.bits.address_space) == ((tree_class_check
 ((((contains_struct_check ((base_type), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4123, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4123, __FUNCTION__))->base.u.bits.address_space)) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4123, __FUNCTION__), 0 : 0))
  == TYPE_ADDR_SPACE (TREE_TYPE (base_type)))((void)(!(((tree_class_check ((((contains_struct_check ((type
), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4122, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4122, __FUNCTION__))->base.u.bits.address_space) == ((tree_class_check
 ((((contains_struct_check ((base_type), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4123, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4123, __FUNCTION__))->base.u.bits.address_space)) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4123, __FUNCTION__), 0 : 0));
  }
else
  type = base_type;

return type;
4129}

4131/* Determines the expression by that USE is expressed from induction variable
 CAND at statement AT in LOOP.  The computation is unshared.  */

4134static tree
4135get_computation_at (class loop *loop, gimple *at,
    struct iv_use *use, struct iv_cand *cand)
4137{
aff_tree aff;
tree type = get_use_type (use);

if (!get_computation_aff (loop, at, use, cand, &aff))
  return NULL_TREE(tree) nullptr;
unshare_aff_combination (&aff);
return fold_convert (type, aff_combination_to_tree (&aff))fold_convert_loc (((location_t) 0), type, aff_combination_to_tree
 (&aff));
4145}

4147/* Like get_computation_at, but try harder, even if the computation
 is more expensive.  Intended for debug stmts.  */

4150static tree
4151get_debug_computation_at (class loop *loop, gimple *at,
	  struct iv_use *use, struct iv_cand *cand)
4153{
if (tree ret = get_computation_at (loop, at, use, cand))
  return ret;

tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase = cand->iv->base, cstep = cand->iv->step;
tree var;
tree utype = TREE_TYPE (ubase)((contains_struct_check ((ubase), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4160, __FUNCTION__))->typed.type), ctype = TREE_TYPE (cbase)((contains_struct_check ((cbase), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4160, __FUNCTION__))->typed.type);
widest_int rat;

/* We must have a precision to express the values of use.  */
if (TYPE_PRECISION (utype)((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4164, __FUNCTION__))->type_common.precision) >= TYPE_PRECISION (ctype)((tree_class_check ((ctype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4164, __FUNCTION__))->type_common.precision))
  return NULL_TREE(tree) nullptr;

/* Try to handle the case that get_computation_at doesn't,
   try to express
   use = ubase + (var - cbase) / ratio.  */
if (!constant_multiple_of (cstep, fold_convert (TREE_TYPE (cstep), ustep)fold_convert_loc (((location_t) 0), ((contains_struct_check (
(cstep), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4170, __FUNCTION__))->typed.type), ustep),
	     &rat))
  return NULL_TREE(tree) nullptr;

bool neg_p = false;
if (wi::neg_p (rat))
  {
    if (TYPE_UNSIGNED (ctype)((tree_class_check ((ctype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4177, __FUNCTION__))->base.u.bits.unsigned_flag))
return NULL_TREE(tree) nullptr;
    neg_p = true;
    rat = wi::neg (rat);
  }

/* If both IVs can wrap around and CAND doesn't have a power of two step,
   it is unsafe.  Consider uint16_t CAND with step 9, when wrapping around,
   the values will be ... 0xfff0, 0xfff9, 2, 11 ... and when use is say
   uint8_t with step 3, those values divided by 3 cast to uint8_t will be
   ... 0x50, 0x53, 0, 3 ... rather than expected 0x50, 0x53, 0x56, 0x59.  */
if (!use->iv->no_overflow
    && !cand->iv->no_overflow
    && !integer_pow2p (cstep))
  return NULL_TREE(tree) nullptr;

int bits = wi::exact_log2 (rat);
if (bits == -1)
  bits = wi::floor_log2 (rat) + 1;
if (!cand->iv->no_overflow
    && TYPE_PRECISION (utype)((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4197, __FUNCTION__))->type_common.precision) + bits > TYPE_PRECISION (ctype)((tree_class_check ((ctype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4197, __FUNCTION__))->type_common.precision))
  return NULL_TREE(tree) nullptr;

var = var_at_stmt (loop, cand, at);

if (POINTER_TYPE_P (ctype)(((enum tree_code) (ctype)->base.code) == POINTER_TYPE || (
(enum tree_code) (ctype)->base.code) == REFERENCE_TYPE))
  {
    ctype = unsigned_type_for (ctype);
    cbase = fold_convert (ctype, cbase)fold_convert_loc (((location_t) 0), ctype, cbase);
    cstep = fold_convert (ctype, cstep)fold_convert_loc (((location_t) 0), ctype, cstep);
    var = fold_convert (ctype, var)fold_convert_loc (((location_t) 0), ctype, var);
  }

if (stmt_after_increment (loop, cand, at))
  var = fold_build2 (MINUS_EXPR, TREE_TYPE (var), var,fold_build2_loc (((location_t) 0), MINUS_EXPR, ((contains_struct_check
 ((var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4211, __FUNCTION__))->typed.type), var, unshare_expr (cstep
) )
       unshare_expr (cstep))fold_build2_loc (((location_t) 0), MINUS_EXPR, ((contains_struct_check
 ((var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4211, __FUNCTION__))->typed.type), var, unshare_expr (cstep
) );

var = fold_build2 (MINUS_EXPR, TREE_TYPE (var), var, cbase)fold_build2_loc (((location_t) 0), MINUS_EXPR, ((contains_struct_check
 ((var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4214, __FUNCTION__))->typed.type), var, cbase );
var = fold_build2 (EXACT_DIV_EXPR, TREE_TYPE (var), var,fold_build2_loc (((location_t) 0), EXACT_DIV_EXPR, ((contains_struct_check
 ((var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4215, __FUNCTION__))->typed.type), var, wide_int_to_tree
 (((contains_struct_check ((var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4216, __FUNCTION__))->typed.type), rat) )
     wide_int_to_tree (TREE_TYPE (var), rat))fold_build2_loc (((location_t) 0), EXACT_DIV_EXPR, ((contains_struct_check
 ((var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4215, __FUNCTION__))->typed.type), var, wide_int_to_tree
 (((contains_struct_check ((var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4216, __FUNCTION__))->typed.type), rat) );
if (POINTER_TYPE_P (utype)(((enum tree_code) (utype)->base.code) == POINTER_TYPE || (
(enum tree_code) (utype)->base.code) == REFERENCE_TYPE))
  {
    var = fold_convert (sizetype, var)fold_convert_loc (((location_t) 0), sizetype_tab[(int) stk_sizetype
], var);
    if (neg_p)
var = fold_build1 (NEGATE_EXPR, sizetype, var)fold_build1_loc (((location_t) 0), NEGATE_EXPR, sizetype_tab[
(int) stk_sizetype], var );
    var = fold_build2 (POINTER_PLUS_EXPR, utype, ubase, var)fold_build2_loc (((location_t) 0), POINTER_PLUS_EXPR, utype, ubase
, var );
  }
else
  {
    var = fold_convert (utype, var)fold_convert_loc (((location_t) 0), utype, var);
    var = fold_build2 (neg_p ? MINUS_EXPR : PLUS_EXPR, utype,fold_build2_loc (((location_t) 0), neg_p ? MINUS_EXPR : PLUS_EXPR
, utype, ubase, var )
	 ubase, var)fold_build2_loc (((location_t) 0), neg_p ? MINUS_EXPR : PLUS_EXPR
, utype, ubase, var );
  }
return var;
4231}

4233/* Adjust the cost COST for being in loop setup rather than loop body.
 If we're optimizing for space, the loop setup overhead is constant;
 if we're optimizing for speed, amortize it over the per-iteration cost.
 If ROUND_UP_P is true, the result is round up rather than to zero when
 optimizing for speed.  */
4238static int64_t
4239adjust_setup_cost (struct ivopts_data *data, int64_t cost,
   bool round_up_p = false)
4241{
if (cost == INFTY1000000000)
  return cost;
else if (optimize_loop_for_speed_p (data->current_loop))
  {
    int64_t niters = (int64_t) avg_loop_niter (data->current_loop);
    return (cost + (round_up_p ? niters - 1 : 0)) / niters;
  }
else
  return cost;
4251}

4253/* Calculate the SPEED or size cost of shiftadd EXPR in MODE.  MULT is the
 EXPR operand holding the shift.  COST0 and COST1 are the costs for
 calculating the operands of EXPR.  Returns true if successful, and returns
 the cost in COST.  */

4258static bool
4259get_shiftadd_cost (tree expr, scalar_int_mode mode, comp_cost cost0,
   comp_cost cost1, tree mult, bool speed, comp_cost *cost)
4261{
comp_cost res;
tree op1 = TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4263, __FUNCTION__)))));
tree cst = TREE_OPERAND (mult, 1)(*((const_cast<tree*> (tree_operand_check ((mult), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4264, __FUNCTION__)))));
tree multop = TREE_OPERAND (mult, 0)(*((const_cast<tree*> (tree_operand_check ((mult), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4265, __FUNCTION__)))));
int m = exact_log2 (int_cst_value (cst));
int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode))((((8) * (((global_options.x_ix86_isa_flags & (1UL <<
 1)) != 0) ? 8 : 4))) < (GET_MODE_BITSIZE (mode)) ? (((8) *
 (((global_options.x_ix86_isa_flags & (1UL << 1)) !=
 0) ? 8 : 4))) : (GET_MODE_BITSIZE (mode)));
int as_cost, sa_cost;
bool mult_in_op1;

if (!(m >= 0 && m < maxm))
  return false;

STRIP_NOPS (op1)(op1) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op1)))));
mult_in_op1 = operand_equal_p (op1, mult, 0);

as_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);

/* If the target has a cheap shift-and-add or shift-and-sub instruction,
   use that in preference to a shift insn followed by an add insn.  */
sa_cost = (TREE_CODE (expr)((enum tree_code) (expr)->base.code) != MINUS_EXPR
    ? shiftadd_cost (speed, mode, m)
    : (mult_in_op1
? shiftsub1_cost (speed, mode, m)
: shiftsub0_cost (speed, mode, m)));

res = comp_cost (MIN (as_cost, sa_cost)((as_cost) < (sa_cost) ? (as_cost) : (sa_cost)), 0);
res += (mult_in_op1 ? cost0 : cost1);

STRIP_NOPS (multop)(multop) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((multop)))));
if (!is_gimple_val (multop))
  res += force_expr_to_var_cost (multop, speed);

*cost = res;
return true;
4296}

4298/* Estimates cost of forcing expression EXPR into a variable.  */

4300static comp_cost
4301force_expr_to_var_cost (tree expr, bool speed)
4302{
static bool costs_initialized = false;
static unsigned integer_cost [2];
static unsigned symbol_cost [2];
static unsigned address_cost [2];
tree op0, op1;
comp_cost cost0, cost1, cost;
machine_mode mode;
scalar_int_mode int_mode;

if (!costs_initialized)
  {
    tree type = build_pointer_type (integer_type_nodeinteger_types[itk_int]);
    tree var, addr;
    rtx x;
    int i;

    var = create_tmp_var_raw (integer_type_nodeinteger_types[itk_int], "test_var");
    TREE_STATIC (var)((var)->base.static_flag) = 1;
    x = produce_memory_decl_rtl (var, NULLnullptr);
    SET_DECL_RTL (var, x)set_decl_rtl (var, x);

    addr = build1 (ADDR_EXPR, type, var);


    for (i = 0; i < 2; i++)
{
 integer_cost[i] = computation_cost (build_int_cst (integer_type_nodeinteger_types[itk_int],
					     2000), i);

 symbol_cost[i] = computation_cost (addr, i) + 1;

 address_cost[i]
   = computation_cost (fold_build_pointer_plus_hwi (addr, 2000)fold_build_pointer_plus_hwi_loc (((location_t) 0), addr, 2000
), i) + 1;
 if (dump_file && (dump_flags & TDF_DETAILS))
   {
     fprintf (dump_file, "force_expr_to_var_cost %s costs:\n", i ? "speed" : "size");
     fprintf (dump_file, "  integer %d\n", (int) integer_cost[i]);
     fprintf (dump_file, "  symbol %d\n", (int) symbol_cost[i]);
     fprintf (dump_file, "  address %d\n", (int) address_cost[i]);
     fprintf (dump_file, "  other %d\n", (int) target_spill_cost(this_target_cfgloop->x_target_spill_cost)[i]);
     fprintf (dump_file, "\n");
   }
}

    costs_initialized = true;
  }

STRIP_NOPS (expr)(expr) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((expr)))));

if (SSA_VAR_P (expr)(((enum tree_code) (expr)->base.code) == VAR_DECL || ((enum
 tree_code) (expr)->base.code) == PARM_DECL || ((enum tree_code
) (expr)->base.code) == RESULT_DECL || ((enum tree_code) (
expr)->base.code) == SSA_NAME))
  return no_cost;

if (is_gimple_min_invariant (expr))
  {
    if (poly_int_tree_p (expr))
return comp_cost (integer_cost [speed], 0);

    if (TREE_CODE (expr)((enum tree_code) (expr)->base.code) == ADDR_EXPR)
{
 tree obj = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4362, __FUNCTION__)))));

 if (VAR_P (obj)(((enum tree_code) (obj)->base.code) == VAR_DECL)
     || TREE_CODE (obj)((enum tree_code) (obj)->base.code) == PARM_DECL
     || TREE_CODE (obj)((enum tree_code) (obj)->base.code) == RESULT_DECL)
   return comp_cost (symbol_cost [speed], 0);
}

    return comp_cost (address_cost [speed], 0);
  }

switch (TREE_CODE (expr)((enum tree_code) (expr)->base.code))
  {
  case POINTER_PLUS_EXPR:
  case PLUS_EXPR:
  case MINUS_EXPR:
  case MULT_EXPR:
  case TRUNC_DIV_EXPR:
  case BIT_AND_EXPR:
  case BIT_IOR_EXPR:
  case LSHIFT_EXPR:
  case RSHIFT_EXPR:
    op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4384, __FUNCTION__)))));
    op1 = TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4385, __FUNCTION__)))));
    STRIP_NOPS (op0)(op0) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op0)))));
    STRIP_NOPS (op1)(op1) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op1)))));
    break;

  CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
  case NEGATE_EXPR:
  case BIT_NOT_EXPR:
    op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4393, __FUNCTION__)))));
    STRIP_NOPS (op0)(op0) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op0)))));
    op1 = NULL_TREE(tree) nullptr;
    break;
  /* See add_iv_candidate_for_doloop, for doloop may_be_zero case, we
     introduce COND_EXPR for IV base, need to support better cost estimation
     for this COND_EXPR and tcc_comparison.  */
  case COND_EXPR:
    op0 = TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4401, __FUNCTION__)))));
    STRIP_NOPS (op0)(op0) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op0)))));
    op1 = TREE_OPERAND (expr, 2)(*((const_cast<tree*> (tree_operand_check ((expr), (2),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4403, __FUNCTION__)))));
    STRIP_NOPS (op1)(op1) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op1)))));
    break;
  case LT_EXPR:
  case LE_EXPR:
  case GT_EXPR:
  case GE_EXPR:
  case EQ_EXPR:
  case NE_EXPR:
  case UNORDERED_EXPR:
  case ORDERED_EXPR:
  case UNLT_EXPR:
  case UNLE_EXPR:
  case UNGT_EXPR:
  case UNGE_EXPR:
  case UNEQ_EXPR:
  case LTGT_EXPR:
  case MAX_EXPR:
  case MIN_EXPR:
    op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4422, __FUNCTION__)))));
    STRIP_NOPS (op0)(op0) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op0)))));
    op1 = TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4424, __FUNCTION__)))));
    STRIP_NOPS (op1)(op1) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op1)))));
    break;

  default:
    /* Just an arbitrary value, FIXME.  */
    return comp_cost (target_spill_cost(this_target_cfgloop->x_target_spill_cost)[speed], 0);
  }

if (op0 == NULL_TREE(tree) nullptr
    || TREE_CODE (op0)((enum tree_code) (op0)->base.code) == SSA_NAME || CONSTANT_CLASS_P (op0)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (op0)->base.code))] == tcc_constant))
  cost0 = no_cost;
else
  cost0 = force_expr_to_var_cost (op0, speed);

if (op1 == NULL_TREE(tree) nullptr
    || TREE_CODE (op1)((enum tree_code) (op1)->base.code) == SSA_NAME || CONSTANT_CLASS_P (op1)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (op1)->base.code))] == tcc_constant))
  cost1 = no_cost;
else
  cost1 = force_expr_to_var_cost (op1, speed);

mode = TYPE_MODE (TREE_TYPE (expr))((((enum tree_code) ((tree_class_check ((((contains_struct_check
 ((expr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4445, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4445, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (((contains_struct_check ((expr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4445, __FUNCTION__))->typed.type)) : (((contains_struct_check
 ((expr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4445, __FUNCTION__))->typed.type))->type_common.mode);
switch (TREE_CODE (expr)((enum tree_code) (expr)->base.code))
  {
  case POINTER_PLUS_EXPR:
  case PLUS_EXPR:
  case MINUS_EXPR:
  case NEGATE_EXPR:
    cost = comp_cost (add_cost (speed, mode), 0);
    if (TREE_CODE (expr)((enum tree_code) (expr)->base.code) != NEGATE_EXPR)
{
 tree mult = NULL_TREE(tree) nullptr;
 comp_cost sa_cost;
 if (TREE_CODE (op1)((enum tree_code) (op1)->base.code) == MULT_EXPR)
   mult = op1;
 else if (TREE_CODE (op0)((enum tree_code) (op0)->base.code) == MULT_EXPR)
   mult = op0;

 if (mult != NULL_TREE(tree) nullptr
     && is_a <scalar_int_mode> (mode, &int_mode)
     && cst_and_fits_in_hwi (TREE_OPERAND (mult, 1)(*((const_cast<tree*> (tree_operand_check ((mult), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4464, __FUNCTION__))))))
     && get_shiftadd_cost (expr, int_mode, cost0, cost1, mult,
		    speed, &sa_cost))
   return sa_cost;
}
    break;

  CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
    {
tree inner_mode, outer_mode;
outer_mode = TREE_TYPE (expr)((contains_struct_check ((expr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4474, __FUNCTION__))->typed.type);
inner_mode = TREE_TYPE (op0)((contains_struct_check ((op0), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4475, __FUNCTION__))->typed.type);
cost = comp_cost (convert_cost (TYPE_MODE (outer_mode)((((enum tree_code) ((tree_class_check ((outer_mode), (tcc_type
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4476, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (outer_mode) : (outer_mode)->type_common.mode),
		       TYPE_MODE (inner_mode)((((enum tree_code) ((tree_class_check ((inner_mode), (tcc_type
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4477, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (inner_mode) : (inner_mode)->type_common.mode), speed), 0);
    }
    break;

  case MULT_EXPR:
    if (cst_and_fits_in_hwi (op0))
cost = comp_cost (mult_by_coeff_cost (int_cst_value (op0),
			     mode, speed), 0);
    else if (cst_and_fits_in_hwi (op1))
cost = comp_cost (mult_by_coeff_cost (int_cst_value (op1),
			     mode, speed), 0);
    else
return comp_cost (target_spill_cost(this_target_cfgloop->x_target_spill_cost) [speed], 0);
    break;

  case TRUNC_DIV_EXPR:
    /* Division by power of two is usually cheap, so we allow it.  Forbid
anything else.  */
    if (integer_pow2p (TREE_OPERAND (expr, 1)(*((const_cast<tree*> (tree_operand_check ((expr), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4495, __FUNCTION__)))))))
cost = comp_cost (add_cost (speed, mode), 0);
    else
cost = comp_cost (target_spill_cost(this_target_cfgloop->x_target_spill_cost)[speed], 0);
    break;

  case BIT_AND_EXPR:
  case BIT_IOR_EXPR:
  case BIT_NOT_EXPR:
  case LSHIFT_EXPR:
  case RSHIFT_EXPR:
    cost = comp_cost (add_cost (speed, mode), 0);
    break;
  case COND_EXPR:
    op0 = TREE_OPERAND (expr, 0)(*((const_cast<tree*> (tree_operand_check ((expr), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4509, __FUNCTION__)))));
    STRIP_NOPS (op0)(op0) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((op0)))));
    if (op0 == NULL_TREE(tree) nullptr || TREE_CODE (op0)((enum tree_code) (op0)->base.code) == SSA_NAME
 || CONSTANT_CLASS_P (op0)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (op0)->base.code))] == tcc_constant))
cost = no_cost;
    else
cost = force_expr_to_var_cost (op0, speed);
    break;
  case LT_EXPR:
  case LE_EXPR:
  case GT_EXPR:
  case GE_EXPR:
  case EQ_EXPR:
  case NE_EXPR:
  case UNORDERED_EXPR:
  case ORDERED_EXPR:
  case UNLT_EXPR:
  case UNLE_EXPR:
  case UNGT_EXPR:
  case UNGE_EXPR:
  case UNEQ_EXPR:
  case LTGT_EXPR:
  case MAX_EXPR:
  case MIN_EXPR:
    /* Simply use add cost for now, FIXME if there is some more accurate cost
evaluation way.  */
    cost = comp_cost (add_cost (speed, mode), 0);
    break;

  default:
    gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4539, __FUNCTION__));
  }

cost += cost0;
cost += cost1;
return cost;
4545}

4547/* Estimates cost of forcing EXPR into a variable.  INV_VARS is a set of the
 invariants the computation depends on.  */

4550static comp_cost
4551force_var_cost (struct ivopts_data *data, tree expr, bitmap *inv_vars)
4552{
if (!expr)
  return no_cost;

find_inv_vars (data, &expr, inv_vars);
return force_expr_to_var_cost (expr, data->speed);
4558}

4560/* Returns cost of auto-modifying address expression in shape base + offset.
 AINC_STEP is step size of the address IV.  AINC_OFFSET is offset of the
 address expression.  The address expression has ADDR_MODE in addr space
 AS.  The memory access has MEM_MODE.  SPEED means we are optimizing for
 speed or size.  */

4566enum ainc_type
4567{
AINC_PRE_INC,		/* Pre increment.  */
AINC_PRE_DEC,		/* Pre decrement.  */
AINC_POST_INC,	/* Post increment.  */
AINC_POST_DEC,	/* Post decrement.  */
AINC_NONE		/* Also the number of auto increment types.  */
4573};

4575struct ainc_cost_data
4576{
int64_t costs[AINC_NONE];
4578};

4580static comp_cost
4581get_address_cost_ainc (poly_int64 ainc_step, poly_int64 ainc_offset,
       machine_mode addr_mode, machine_mode mem_mode,
       addr_space_t as, bool speed)
4584{
if (!USE_LOAD_PRE_DECREMENT (mem_mode)0
    && !USE_STORE_PRE_DECREMENT (mem_mode)0
    && !USE_LOAD_POST_DECREMENT (mem_mode)0
    && !USE_STORE_POST_DECREMENT (mem_mode)0
    && !USE_LOAD_PRE_INCREMENT (mem_mode)0
    && !USE_STORE_PRE_INCREMENT (mem_mode)0
    && !USE_LOAD_POST_INCREMENT (mem_mode)0
    && !USE_STORE_POST_INCREMENT (mem_mode)0)
  return infinite_cost;

static vec<ainc_cost_data *> ainc_cost_data_list;
unsigned idx = (unsigned) as * MAX_MACHINE_MODE + (unsigned) mem_mode;
if (idx >= ainc_cost_data_list.length ())
  {
    unsigned nsize = ((unsigned) as + 1) *MAX_MACHINE_MODE;

    gcc_assert (nsize > idx)((void)(!(nsize > idx) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4601, __FUNCTION__), 0 : 0));
    ainc_cost_data_list.safe_grow_cleared (nsize, true);
  }

ainc_cost_data *data = ainc_cost_data_list[idx];
if (data == NULLnullptr)
  {
    rtx reg = gen_raw_REG (addr_mode, LAST_VIRTUAL_REGISTER(((76)) + 5) + 1);

    data = (ainc_cost_data *) xcalloc (1, sizeof (*data));
    data->costs[AINC_PRE_DEC] = INFTY1000000000;
    data->costs[AINC_POST_DEC] = INFTY1000000000;
    data->costs[AINC_PRE_INC] = INFTY1000000000;
    data->costs[AINC_POST_INC] = INFTY1000000000;
    if (USE_LOAD_PRE_DECREMENT (mem_mode)0
 || USE_STORE_PRE_DECREMENT (mem_mode)0)
{
 rtx addr = gen_rtx_PRE_DEC (addr_mode, reg)gen_rtx_fmt_e_stat ((PRE_DEC), ((addr_mode)), ((reg)) );

 if (memory_address_addr_space_p (mem_mode, addr, as))
   data->costs[AINC_PRE_DEC]
     = address_cost (addr, mem_mode, as, speed);
}
    if (USE_LOAD_POST_DECREMENT (mem_mode)0
 || USE_STORE_POST_DECREMENT (mem_mode)0)
{
 rtx addr = gen_rtx_POST_DEC (addr_mode, reg)gen_rtx_fmt_e_stat ((POST_DEC), ((addr_mode)), ((reg)) );

 if (memory_address_addr_space_p (mem_mode, addr, as))
   data->costs[AINC_POST_DEC]
     = address_cost (addr, mem_mode, as, speed);
}
    if (USE_LOAD_PRE_INCREMENT (mem_mode)0
 || USE_STORE_PRE_INCREMENT (mem_mode)0)
{
 rtx addr = gen_rtx_PRE_INC (addr_mode, reg)gen_rtx_fmt_e_stat ((PRE_INC), ((addr_mode)), ((reg)) );

 if (memory_address_addr_space_p (mem_mode, addr, as))
   data->costs[AINC_PRE_INC]
     = address_cost (addr, mem_mode, as, speed);
}
    if (USE_LOAD_POST_INCREMENT (mem_mode)0
 || USE_STORE_POST_INCREMENT (mem_mode)0)
{
 rtx addr = gen_rtx_POST_INC (addr_mode, reg)gen_rtx_fmt_e_stat ((POST_INC), ((addr_mode)), ((reg)) );

 if (memory_address_addr_space_p (mem_mode, addr, as))
   data->costs[AINC_POST_INC]
     = address_cost (addr, mem_mode, as, speed);
}
    ainc_cost_data_list[idx] = data;
  }

poly_int64 msize = GET_MODE_SIZE (mem_mode);
if (known_eq (ainc_offset, 0)(!maybe_ne (ainc_offset, 0)) && known_eq (msize, ainc_step)(!maybe_ne (msize, ainc_step)))
  return comp_cost (data->costs[AINC_POST_INC], 0);
if (known_eq (ainc_offset, 0)(!maybe_ne (ainc_offset, 0)) && known_eq (msize, -ainc_step)(!maybe_ne (msize, -ainc_step)))
  return comp_cost (data->costs[AINC_POST_DEC], 0);
if (known_eq (ainc_offset, msize)(!maybe_ne (ainc_offset, msize)) && known_eq (msize, ainc_step)(!maybe_ne (msize, ainc_step)))
  return comp_cost (data->costs[AINC_PRE_INC], 0);
if (known_eq (ainc_offset, -msize)(!maybe_ne (ainc_offset, -msize)) && known_eq (msize, -ainc_step)(!maybe_ne (msize, -ainc_step)))
  return comp_cost (data->costs[AINC_PRE_DEC], 0);

return infinite_cost;
4665}

4667/* Return cost of computing USE's address expression by using CAND.
 AFF_INV and AFF_VAR represent invariant and variant parts of the
 address expression, respectively.  If AFF_INV is simple, store
 the loop invariant variables which are depended by it in INV_VARS;
 if AFF_INV is complicated, handle it as a new invariant expression
 and record it in INV_EXPR.  RATIO indicates multiple times between
 steps of USE and CAND.  If CAN_AUTOINC is nonNULL, store boolean
 value to it indicating if this is an auto-increment address.  */

4676static comp_cost
4677get_address_cost (struct ivopts_data *data, struct iv_use *use,
  struct iv_cand *cand, aff_tree *aff_inv,
  aff_tree *aff_var, HOST_WIDE_INTlong ratio,
  bitmap *inv_vars, iv_inv_expr_ent **inv_expr,
  bool *can_autoinc, bool speed)
4682{
rtx addr;
bool simple_inv = true;
tree comp_inv = NULL_TREE(tree) nullptr, type = aff_var->type;
comp_cost var_cost = no_cost, cost = no_cost;
struct mem_address parts = {NULL_TREE(tree) nullptr, integer_one_nodeglobal_trees[TI_INTEGER_ONE],
	      NULL_TREE(tree) nullptr, NULL_TREE(tree) nullptr, NULL_TREE(tree) nullptr};
machine_mode addr_mode = TYPE_MODE (type)((((enum tree_code) ((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4689, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (type) : (type)->type_common.mode);
machine_mode mem_mode = TYPE_MODE (use->mem_type)((((enum tree_code) ((tree_class_check ((use->mem_type), (
tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4690, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (use->mem_type) : (use->mem_type)->type_common.mode
);
addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (use->iv->base))((tree_class_check ((((contains_struct_check ((use->iv->
base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4691, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4691, __FUNCTION__))->base.u.bits.address_space);
/* Only true if ratio != 1.  */
bool ok_with_ratio_p = false;
bool ok_without_ratio_p = false;

if (!aff_combination_const_p (aff_inv))
  {
    parts.index = integer_one_nodeglobal_trees[TI_INTEGER_ONE];
    /* Addressing mode "base + index".  */
    ok_without_ratio_p = valid_mem_ref_p (mem_mode, as, &parts);
    if (ratio != 1)
{
 parts.step = wide_int_to_tree (type, ratio);
 /* Addressing mode "base + index << scale".  */
 ok_with_ratio_p = valid_mem_ref_p (mem_mode, as, &parts);
 if (!ok_with_ratio_p)
   parts.step = NULL_TREE(tree) nullptr;
}
    if (ok_with_ratio_p || ok_without_ratio_p)
{
 if (maybe_ne (aff_inv->offset, 0))
   {
     parts.offset = wide_int_to_tree (sizetypesizetype_tab[(int) stk_sizetype], aff_inv->offset);
     /* Addressing mode "base + index [<< scale] + offset".  */
     if (!valid_mem_ref_p (mem_mode, as, &parts))
parts.offset = NULL_TREE(tree) nullptr;
     else
aff_inv->offset = 0;
   }

 move_fixed_address_to_symbol (&parts, aff_inv);
 /* Base is fixed address and is moved to symbol part.  */
 if (parts.symbol != NULL_TREE(tree) nullptr && aff_combination_zero_p (aff_inv))
   parts.base = NULL_TREE(tree) nullptr;

 /* Addressing mode "symbol + base + index [<< scale] [+ offset]".  */
 if (parts.symbol != NULL_TREE(tree) nullptr
     && !valid_mem_ref_p (mem_mode, as, &parts))
   {
     aff_combination_add_elt (aff_inv, parts.symbol, 1);
     parts.symbol = NULL_TREE(tree) nullptr;
     /* Reset SIMPLE_INV since symbol address needs to be computed
 outside of address expression in this case.  */
     simple_inv = false;
     /* Symbol part is moved back to base part, it can't be NULL.  */
     parts.base = integer_one_nodeglobal_trees[TI_INTEGER_ONE];
   }
}
    else
parts.index = NULL_TREE(tree) nullptr;
  }
else
  {
    poly_int64 ainc_step;
    if (can_autoinc
 && ratio == 1
 && ptrdiff_tree_p (cand->iv->step, &ainc_step))
{
 poly_int64 ainc_offset = (aff_inv->offset).force_shwi ();

 if (stmt_after_increment (data->current_loop, cand, use->stmt))
   ainc_offset += ainc_step;
 cost = get_address_cost_ainc (ainc_step, ainc_offset,
			addr_mode, mem_mode, as, speed);
 if (!cost.infinite_cost_p ())
   {
     *can_autoinc = true;
     return cost;
   }
 cost = no_cost;
}
    if (!aff_combination_zero_p (aff_inv))
{
 parts.offset = wide_int_to_tree (sizetypesizetype_tab[(int) stk_sizetype], aff_inv->offset);
 /* Addressing mode "base + offset".  */
 if (!valid_mem_ref_p (mem_mode, as, &parts))
   parts.offset = NULL_TREE(tree) nullptr;
 else
   aff_inv->offset = 0;
}
  }

if (simple_inv)
  simple_inv = (aff_inv == NULLnullptr
  || aff_combination_const_p (aff_inv)
  || aff_combination_singleton_var_p (aff_inv));
if (!aff_combination_zero_p (aff_inv))
  comp_inv = aff_combination_to_tree (aff_inv);
if (comp_inv != NULL_TREE(tree) nullptr)
  cost = force_var_cost (data, comp_inv, inv_vars);
if (ratio != 1 && parts.step == NULL_TREE(tree) nullptr)
  var_cost += mult_by_coeff_cost (ratio, addr_mode, speed);
if (comp_inv != NULL_TREE(tree) nullptr && parts.index == NULL_TREE(tree) nullptr)
  var_cost += add_cost (speed, addr_mode);

if (comp_inv && inv_expr && !simple_inv)
  {
    *inv_expr = get_loop_invariant_expr (data, comp_inv);
    /* Clear depends on.  */
    if (*inv_expr != NULLnullptr && inv_vars && *inv_vars)
bitmap_clear (*inv_vars);

    /* Cost of small invariant expression adjusted against loop niters
is usually zero, which makes it difficult to be differentiated
from candidate based on loop invariant variables.  Secondly, the
generated invariant expression may not be hoisted out of loop by
following pass.  We penalize the cost by rounding up in order to
neutralize such effects.  */
    cost.cost = adjust_setup_cost (data, cost.cost, true);
    cost.scratch = cost.cost;
  }

cost += var_cost;
addr = addr_for_mem_ref (&parts, as, false);
gcc_assert (memory_address_addr_space_p (mem_mode, addr, as))((void)(!(memory_address_addr_space_p (mem_mode, addr, as)) ?
 fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4805, __FUNCTION__), 0 : 0));
cost += address_cost (addr, mem_mode, as, speed);

if (parts.symbol != NULL_TREE(tree) nullptr)
  cost.complexity += 1;
/* Don't increase the complexity of adding a scaled index if it's
   the only kind of index that the target allows.  */
if (parts.step != NULL_TREE(tree) nullptr && ok_without_ratio_p)
  cost.complexity += 1;
if (parts.base != NULL_TREE(tree) nullptr && parts.index != NULL_TREE(tree) nullptr)
  cost.complexity += 1;
if (parts.offset != NULL_TREE(tree) nullptr && !integer_zerop (parts.offset))
  cost.complexity += 1;

return cost;
4820}

4822/* Scale (multiply) the computed COST (except scratch part that should be
 hoisted out a loop) by header->frequency / AT->frequency, which makes
 expected cost more accurate.  */

4826static comp_cost
4827get_scaled_computation_cost_at (ivopts_data *data, gimple *at, comp_cost cost)
4828{
if (data->speed
    && data->current_loop->header->count.to_frequency (cfun(cfun + 0)) > 0)
  {
    basic_block bb = gimple_bb (at);
    gcc_assert (cost.scratch <= cost.cost)((void)(!(cost.scratch <= cost.cost) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4833, __FUNCTION__), 0 : 0));
    int scale_factor = (int)(intptr_t) bb->aux;
    if (scale_factor == 1)
return cost;

    int64_t scaled_cost
= cost.scratch + (cost.cost - cost.scratch) * scale_factor;

    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Scaling cost based on bb prob by %2.2f: "
 "%" PRId64"l" "d" " (scratch: %" PRId64"l" "d" ") -> %" PRId64"l" "d" "\n",
 1.0f * scale_factor, cost.cost, cost.scratch, scaled_cost);

    cost.cost = scaled_cost;
  }

return cost;
4850}

4852/* Determines the cost of the computation by that USE is expressed
 from induction variable CAND.  If ADDRESS_P is true, we just need
 to create an address from it, otherwise we want to get it into
 register.  A set of invariants we depend on is stored in INV_VARS.
 If CAN_AUTOINC is nonnull, use it to record whether autoinc
 addressing is likely.  If INV_EXPR is nonnull, record invariant
 expr entry in it.  */

4860static comp_cost
4861get_computation_cost (struct ivopts_data *data, struct iv_use *use,
      struct iv_cand *cand, bool address_p, bitmap *inv_vars,
      bool *can_autoinc, iv_inv_expr_ent **inv_expr)
4864{
gimple *at = use->stmt;
tree ubase = use->iv->base, cbase = cand->iv->base;
tree utype = TREE_TYPE (ubase)((contains_struct_check ((ubase), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4867, __FUNCTION__))->typed.type), ctype = TREE_TYPE (cbase)((contains_struct_check ((cbase), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4867, __FUNCTION__))->typed.type);
tree comp_inv = NULL_TREE(tree) nullptr;
HOST_WIDE_INTlong ratio, aratio;
comp_cost cost;
widest_int rat;
aff_tree aff_inv, aff_var;
bool speed = optimize_bb_for_speed_p (gimple_bb (at));

if (inv_vars)
  *inv_vars = NULLnullptr;
if (can_autoinc)
  *can_autoinc = false;
if (inv_expr)
  *inv_expr = NULLnullptr;

/* Check if we have enough precision to express the values of use.  */
if (TYPE_PRECISION (utype)((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4883, __FUNCTION__))->type_common.precision) > TYPE_PRECISION (ctype)((tree_class_check ((ctype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4883, __FUNCTION__))->type_common.precision))
  return infinite_cost;

if (address_p
    || (use->iv->base_object
 && cand->iv->base_object
 && POINTER_TYPE_P (TREE_TYPE (use->iv->base_object))(((enum tree_code) (((contains_struct_check ((use->iv->
base_object), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4889, __FUNCTION__))->typed.type))->base.code) == POINTER_TYPE
 || ((enum tree_code) (((contains_struct_check ((use->iv->
base_object), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4889, __FUNCTION__))->typed.type))->base.code) == REFERENCE_TYPE
)
 && POINTER_TYPE_P (TREE_TYPE (cand->iv->base_object))(((enum tree_code) (((contains_struct_check ((cand->iv->
base_object), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4890, __FUNCTION__))->typed.type))->base.code) == POINTER_TYPE
 || ((enum tree_code) (((contains_struct_check ((cand->iv->
base_object), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4890, __FUNCTION__))->typed.type))->base.code) == REFERENCE_TYPE
)))
  {
    /* Do not try to express address of an object with computation based
on address of a different object.  This may cause problems in rtl
level alias analysis (that does not expect this to be happening,
as this is illegal in C), and would be unlikely to be useful
anyway.  */
    if (use->iv->base_object
 && cand->iv->base_object
 && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
return infinite_cost;
  }

if (!get_computation_aff_1 (data->current_loop, at, use,
	      cand, &aff_inv, &aff_var, &rat)
    || !wi::fits_shwi_p (rat))
  return infinite_cost;

ratio = rat.to_shwi ();
if (address_p)
  {
    cost = get_address_cost (data, use, cand, &aff_inv, &aff_var, ratio,
	       inv_vars, inv_expr, can_autoinc, speed);
    cost = get_scaled_computation_cost_at (data, at, cost);
    /* For doloop IV cand, add on the extra cost.  */
    cost += cand->doloop_p ? targetm.doloop_cost_for_address : 0;
    return cost;
  }

bool simple_inv = (aff_combination_const_p (&aff_inv)
     || aff_combination_singleton_var_p (&aff_inv));
tree signed_type = signed_type_for (aff_combination_type (&aff_inv));
aff_combination_convert (&aff_inv, signed_type);
if (!aff_combination_zero_p (&aff_inv))
  comp_inv = aff_combination_to_tree (&aff_inv);

cost = force_var_cost (data, comp_inv, inv_vars);
if (comp_inv && inv_expr && !simple_inv)
  {
    *inv_expr = get_loop_invariant_expr (data, comp_inv);
    /* Clear depends on.  */
    if (*inv_expr != NULLnullptr && inv_vars && *inv_vars)
bitmap_clear (*inv_vars);

    cost.cost = adjust_setup_cost (data, cost.cost);
    /* Record setup cost in scratch field.  */
    cost.scratch = cost.cost;
  }
/* Cost of constant integer can be covered when adding invariant part to
   variant part.  */
else if (comp_inv && CONSTANT_CLASS_P (comp_inv)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (comp_inv)->base.code))] == tcc_constant))
  cost = no_cost;

/* Need type narrowing to represent use with cand.  */
if (TYPE_PRECISION (utype)((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4944, __FUNCTION__))->type_common.precision) < TYPE_PRECISION (ctype)((tree_class_check ((ctype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4944, __FUNCTION__))->type_common.precision))
  {
    machine_mode outer_mode = TYPE_MODE (utype)((((enum tree_code) ((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4946, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (utype) : (utype)->type_common.mode);
    machine_mode inner_mode = TYPE_MODE (ctype)((((enum tree_code) ((tree_class_check ((ctype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4947, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (ctype) : (ctype)->type_common.mode);
    cost += comp_cost (convert_cost (outer_mode, inner_mode, speed), 0);
  }

/* Turn a + i * (-c) into a - i * c.  */
if (ratio < 0 && comp_inv && !integer_zerop (comp_inv))
  aratio = -ratio;
else
  aratio = ratio;

if (ratio != 1)
  cost += mult_by_coeff_cost (aratio, TYPE_MODE (utype)((((enum tree_code) ((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4958, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (utype) : (utype)->type_common.mode), speed);

/* TODO: We may also need to check if we can compute  a + i * 4 in one
   instruction.  */
/* Need to add up the invariant and variant parts.  */
if (comp_inv && !integer_zerop (comp_inv))
  cost += add_cost (speed, TYPE_MODE (utype)((((enum tree_code) ((tree_class_check ((utype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 4964, __FUNCTION__)))->base.code) == VECTOR_TYPE) ? vector_type_mode
 (utype) : (utype)->type_common.mode));

cost = get_scaled_computation_cost_at (data, at, cost);

/* For doloop IV cand, add on the extra cost.  */
if (cand->doloop_p && use->type == USE_NONLINEAR_EXPR)
  cost += targetm.doloop_cost_for_generic;

return cost;
4973}

4975/* Determines cost of computing the use in GROUP with CAND in a generic
 expression.  */

4978static bool
4979determine_group_iv_cost_generic (struct ivopts_data *data,
		 struct iv_group *group, struct iv_cand *cand)
4981{
comp_cost cost;
iv_inv_expr_ent *inv_expr = NULLnullptr;
bitmap inv_vars = NULLnullptr, inv_exprs = NULLnullptr;
struct iv_use *use = group->vuses[0];

/* The simple case first -- if we need to express value of the preserved
   original biv, the cost is 0.  This also prevents us from counting the
   cost of increment twice -- once at this use and once in the cost of
   the candidate.  */
if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
  cost = no_cost;
/* If the IV candidate involves undefined SSA values and is not the
   same IV as on the USE avoid using that candidate here.  */
else if (cand->involves_undefs
  && (!use->iv || !operand_equal_p (cand->iv->base, use->iv->base, 0)))
  return false;
else
  cost = get_computation_cost (data, use, cand, false,
		 &inv_vars, NULLnullptr, &inv_expr);

if (inv_expr)
  {
    inv_exprs = BITMAP_ALLOCbitmap_alloc (NULLnullptr);
    bitmap_set_bit (inv_exprs, inv_expr->id);
  }
set_group_iv_cost (data, group, cand, cost, inv_vars,
     NULL_TREE(tree) nullptr, ERROR_MARK, inv_exprs);
return !cost.infinite_cost_p ();
5010}

5012/* Determines cost of computing uses in GROUP with CAND in addresses.  */

5014static bool
5015determine_group_iv_cost_address (struct ivopts_data *data,
		 struct iv_group *group, struct iv_cand *cand)
5017{
unsigned i;
bitmap inv_vars = NULLnullptr, inv_exprs = NULLnullptr;
bool can_autoinc;
iv_inv_expr_ent *inv_expr = NULLnullptr;
struct iv_use *use = group->vuses[0];
comp_cost sum_cost = no_cost, cost;

cost = get_computation_cost (data, use, cand, true,
	       &inv_vars, &can_autoinc, &inv_expr);

if (inv_expr)
  {
    inv_exprs = BITMAP_ALLOCbitmap_alloc (NULLnullptr);
    bitmap_set_bit (inv_exprs, inv_expr->id);
  }
sum_cost = cost;
if (!sum_cost.infinite_cost_p () && cand->ainc_use == use)
  {
    if (can_autoinc)
sum_cost -= cand->cost_step;
    /* If we generated the candidate solely for exploiting autoincrement
opportunities, and it turns out it can't be used, set the cost to
infinity to make sure we ignore it.  */
    else if (cand->pos == IP_AFTER_USE || cand->pos == IP_BEFORE_USE)
sum_cost = infinite_cost;
  }

/* Uses in a group can share setup code, so only add setup cost once.  */
cost -= cost.scratch;
/* Compute and add costs for rest uses of this group.  */
for (i = 1; i < group->vuses.length () && !sum_cost.infinite_cost_p (); i++)
  {
    struct iv_use *next = group->vuses[i];

    /* TODO: We could skip computing cost for sub iv_use when it has the
same cost as the first iv_use, but the cost really depends on the
offset and where the iv_use is.  */
cost = get_computation_cost (data, next, cand, true,
		     NULLnullptr, &can_autoinc, &inv_expr);
if (inv_expr)
 {
   if (!inv_exprs)
     inv_exprs = BITMAP_ALLOCbitmap_alloc (NULLnullptr);

   bitmap_set_bit (inv_exprs, inv_expr->id);
 }
    sum_cost += cost;
  }
set_group_iv_cost (data, group, cand, sum_cost, inv_vars,
     NULL_TREE(tree) nullptr, ERROR_MARK, inv_exprs);

return !sum_cost.infinite_cost_p ();
5070}

5072/* Computes value of candidate CAND at position AT in iteration DESC->NITER,
 and stores it to VAL.  */

5075static void
5076cand_value_at (class loop *loop, struct iv_cand *cand, gimple *at,
      class tree_niter_desc *desc, aff_tree *val)
5078{
aff_tree step, delta, nit;
struct iv *iv = cand->iv;
tree type = TREE_TYPE (iv->base)((contains_struct_check ((iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5081, __FUNCTION__))->typed.type);
tree niter = desc->niter;
bool after_adjust = stmt_after_increment (loop, cand, at);
tree steptype;

if (POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE))
  steptype = sizetypesizetype_tab[(int) stk_sizetype];
else
  steptype = unsigned_type_for (type);

/* If AFTER_ADJUST is required, the code below generates the equivalent
   of BASE + NITER * STEP + STEP, when ideally we'd prefer the expression
   BASE + (NITER + 1) * STEP, especially when NITER is often of the form
   SSA_NAME - 1.  Unfortunately, guaranteeing that adding 1 to NITER
   doesn't overflow is tricky, so we peek inside the TREE_NITER_DESC
   class for common idioms that we know are safe.  */
if (after_adjust
    && desc->control.no_overflow
    && integer_onep (desc->control.step)
    && (desc->cmp == LT_EXPR
 || desc->cmp == NE_EXPR)
    && TREE_CODE (desc->bound)((enum tree_code) (desc->bound)->base.code) == SSA_NAME)
  {
    if (integer_onep (desc->control.base))
{
 niter = desc->bound;
 after_adjust = false;
}
    else if (TREE_CODE (niter)((enum tree_code) (niter)->base.code) == MINUS_EXPR
      && integer_onep (TREE_OPERAND (niter, 1)(*((const_cast<tree*> (tree_operand_check ((niter), (1)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5110, __FUNCTION__)))))))
{
 niter = TREE_OPERAND (niter, 0)(*((const_cast<tree*> (tree_operand_check ((niter), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5112, __FUNCTION__)))));
 after_adjust = false;
}
  }

tree_to_aff_combination (iv->step, TREE_TYPE (iv->step)((contains_struct_check ((iv->step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5117, __FUNCTION__))->typed.type), &step);
aff_combination_convert (&step, steptype);
tree_to_aff_combination (niter, TREE_TYPE (niter)((contains_struct_check ((niter), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5119, __FUNCTION__))->typed.type), &nit);
aff_combination_convert (&nit, steptype);
aff_combination_mult (&nit, &step, &delta);
if (after_adjust)
  aff_combination_add (&delta, &step);

tree_to_aff_combination (iv->base, type, val);
if (!POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE))
  aff_combination_convert (val, steptype);
aff_combination_add (val, &delta);
5129}

5131/* Returns period of induction variable iv.  */

5133static tree
5134iv_period (struct iv *iv)
5135{
tree step = iv->step, period, type;
tree pow2div;

gcc_assert (step && TREE_CODE (step) == INTEGER_CST)((void)(!(step && ((enum tree_code) (step)->base.code
) == INTEGER_CST) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5139, __FUNCTION__), 0 : 0));

type = unsigned_type_for (TREE_TYPE (step)((contains_struct_check ((step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5141, __FUNCTION__))->typed.type));
/* Period of the iv is lcm (step, type_range)/step -1,
   i.e., N*type_range/step - 1. Since type range is power
   of two, N == (step >> num_of_ending_zeros_binary (step),
   so the final result is

     (type_range >> num_of_ending_zeros_binary (step)) - 1

*/
pow2div = num_ending_zeros (step);

period = build_low_bits_mask (type,
		(TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5153, __FUNCTION__))->type_common.precision)
		 - tree_to_uhwi (pow2div)));

return period;
5157}

5159/* Returns the comparison operator used when eliminating the iv USE.  */

5161static enum tree_code
5162iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
5163{
class loop *loop = data->current_loop;
basic_block ex_bb;
edge exit;

ex_bb = gimple_bb (use->stmt);
exit = EDGE_SUCC (ex_bb, 0)(*(ex_bb)->succs)[(0)];
if (flow_bb_inside_loop_p (loop, exit->dest))
  exit = EDGE_SUCC (ex_bb, 1)(*(ex_bb)->succs)[(1)];

return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
5174}

5176/* Returns true if we can prove that BASE - OFFSET does not overflow.  For now,
 we only detect the situation that BASE = SOMETHING + OFFSET, where the
 calculation is performed in non-wrapping type.

 TODO: More generally, we could test for the situation that
BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
This would require knowing the sign of OFFSET.  */

5184static bool
5185difference_cannot_overflow_p (struct ivopts_data *data, tree base, tree offset)
5186{
enum tree_code code;
tree e1, e2;
aff_tree aff_e1, aff_e2, aff_offset;

if (!nowrap_type_p (TREE_TYPE (base)((contains_struct_check ((base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5191, __FUNCTION__))->typed.type)))
  return false;

base = expand_simple_operations (base);

if (TREE_CODE (base)((enum tree_code) (base)->base.code) == SSA_NAME)
  {
    gimple *stmt = SSA_NAME_DEF_STMT (base)(tree_check ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5198, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;

    if (gimple_code (stmt) != GIMPLE_ASSIGN)
return false;

    code = gimple_assign_rhs_code (stmt);
    if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
return false;

    e1 = gimple_assign_rhs1 (stmt);
    e2 = gimple_assign_rhs2 (stmt);
  }
else
  {
    code = TREE_CODE (base)((enum tree_code) (base)->base.code);
    if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS)
return false;
    e1 = TREE_OPERAND (base, 0)(*((const_cast<tree*> (tree_operand_check ((base), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5215, __FUNCTION__)))));
    e2 = TREE_OPERAND (base, 1)(*((const_cast<tree*> (tree_operand_check ((base), (1),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5216, __FUNCTION__)))));
  }

/* Use affine expansion as deeper inspection to prove the equality.  */
tree_to_aff_combination_expand (e2, TREE_TYPE (e2)((contains_struct_check ((e2), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5220, __FUNCTION__))->typed.type),
		  &aff_e2, &data->name_expansion_cache);
tree_to_aff_combination_expand (offset, TREE_TYPE (offset)((contains_struct_check ((offset), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5222, __FUNCTION__))->typed.type),
		  &aff_offset, &data->name_expansion_cache);
aff_combination_scale (&aff_offset, -1);
switch (code)
  {
  case PLUS_EXPR:
    aff_combination_add (&aff_e2, &aff_offset);
    if (aff_combination_zero_p (&aff_e2))
return true;

    tree_to_aff_combination_expand (e1, TREE_TYPE (e1)((contains_struct_check ((e1), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5232, __FUNCTION__))->typed.type),
		      &aff_e1, &data->name_expansion_cache);
    aff_combination_add (&aff_e1, &aff_offset);
    return aff_combination_zero_p (&aff_e1);

  case POINTER_PLUS_EXPR:
    aff_combination_add (&aff_e2, &aff_offset);
    return aff_combination_zero_p (&aff_e2);

  default:
    return false;
  }
5244}

5246/* Tries to replace loop exit by one formulated in terms of a LT_EXPR
 comparison with CAND.  NITER describes the number of iterations of
 the loops.  If successful, the comparison in COMP_P is altered accordingly.

 We aim to handle the following situation:

 sometype *base, *p;
 int a, b, i;

 i = a;
 p = p_0 = base + a;

 do
   {
     bla (*p);
     p++;
     i++;
   }
 while (i < b);

 Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
 We aim to optimize this to

 p = p_0 = base + a;
 do
   {
     bla (*p);
     p++;
   }
 while (p < p_0 - a + b);

 This preserves the correctness, since the pointer arithmetics does not
 overflow.  More precisely:

 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
    overflow in computing it or the values of p.
 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
    overflow.  To prove this, we use the fact that p_0 = base + a.  */

5285static bool
5286iv_elimination_compare_lt (struct ivopts_data *data,
	   struct iv_cand *cand, enum tree_code *comp_p,
	   class tree_niter_desc *niter)
5289{
tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter)((contains_struct_check ((niter->niter), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5290, __FUNCTION__))->typed.type), offset;
class aff_tree nit, tmpa, tmpb;
enum tree_code comp;
HOST_WIDE_INTlong step;

/* We need to know that the candidate induction variable does not overflow.
   While more complex analysis may be used to prove this, for now just
   check that the variable appears in the original program and that it
   is computed in a type that guarantees no overflows.  */
cand_type = TREE_TYPE (cand->iv->base)((contains_struct_check ((cand->iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5299, __FUNCTION__))->typed.type);
if (cand->pos != IP_ORIGINAL || !nowrap_type_p (cand_type))
  return false;

/* Make sure that the loop iterates till the loop bound is hit, as otherwise
   the calculation of the BOUND could overflow, making the comparison
   invalid.  */
if (!data->loop_single_exit_p)
  return false;

/* We need to be able to decide whether candidate is increasing or decreasing
   in order to choose the right comparison operator.  */
if (!cst_and_fits_in_hwi (cand->iv->step))
  return false;
step = int_cst_value (cand->iv->step);

/* Check that the number of iterations matches the expected pattern:
   a + 1 > b ? 0 : b - a - 1.  */
mbz = niter->may_be_zero;
if (TREE_CODE (mbz)((enum tree_code) (mbz)->base.code) == GT_EXPR)
  {
    /* Handle a + 1 > b.  */
    tree op0 = TREE_OPERAND (mbz, 0)(*((const_cast<tree*> (tree_operand_check ((mbz), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5321, __FUNCTION__)))));
    if (TREE_CODE (op0)((enum tree_code) (op0)->base.code) == PLUS_EXPR && integer_onep (TREE_OPERAND (op0, 1)(*((const_cast<tree*> (tree_operand_check ((op0), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5322, __FUNCTION__)))))))
{
 a = TREE_OPERAND (op0, 0)(*((const_cast<tree*> (tree_operand_check ((op0), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5324, __FUNCTION__)))));
 b = TREE_OPERAND (mbz, 1)(*((const_cast<tree*> (tree_operand_check ((mbz), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5325, __FUNCTION__)))));
}
    else
return false;
  }
else if (TREE_CODE (mbz)((enum tree_code) (mbz)->base.code) == LT_EXPR)
  {
    tree op1 = TREE_OPERAND (mbz, 1)(*((const_cast<tree*> (tree_operand_check ((mbz), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5332, __FUNCTION__)))));

    /* Handle b < a + 1.  */
    if (TREE_CODE (op1)((enum tree_code) (op1)->base.code) == PLUS_EXPR && integer_onep (TREE_OPERAND (op1, 1)(*((const_cast<tree*> (tree_operand_check ((op1), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5335, __FUNCTION__)))))))
{
 a = TREE_OPERAND (op1, 0)(*((const_cast<tree*> (tree_operand_check ((op1), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5337, __FUNCTION__)))));
 b = TREE_OPERAND (mbz, 0)(*((const_cast<tree*> (tree_operand_check ((mbz), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5338, __FUNCTION__)))));
}
    else
return false;
  }
else
  return false;

/* Expected number of iterations is B - A - 1.  Check that it matches
   the actual number, i.e., that B - A - NITER = 1.  */
tree_to_aff_combination (niter->niter, nit_type, &nit);
tree_to_aff_combination (fold_convert (nit_type, a)fold_convert_loc (((location_t) 0), nit_type, a), nit_type, &tmpa);
tree_to_aff_combination (fold_convert (nit_type, b)fold_convert_loc (((location_t) 0), nit_type, b), nit_type, &tmpb);
aff_combination_scale (&nit, -1);
aff_combination_scale (&tmpa, -1);
aff_combination_add (&tmpb, &tmpa);
aff_combination_add (&tmpb, &nit);
if (tmpb.n != 0 || maybe_ne (tmpb.offset, 1))
  return false;

/* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
   overflow.  */
offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),fold_build2_loc (((location_t) 0), MULT_EXPR, ((contains_struct_check
 ((cand->iv->step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5360, __FUNCTION__))->typed.type), cand->iv->step,
 fold_convert_loc (((location_t) 0), ((contains_struct_check (
(cand->iv->step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5362, __FUNCTION__))->typed.type), a) )
	cand->iv->step,fold_build2_loc (((location_t) 0), MULT_EXPR, ((contains_struct_check
 ((cand->iv->step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5360, __FUNCTION__))->typed.type), cand->iv->step,
 fold_convert_loc (((location_t) 0), ((contains_struct_check (
(cand->iv->step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5362, __FUNCTION__))->typed.type), a) )
	fold_convert (TREE_TYPE (cand->iv->step), a))fold_build2_loc (((location_t) 0), MULT_EXPR, ((contains_struct_check
 ((cand->iv->step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5360, __FUNCTION__))->typed.type), cand->iv->step,
 fold_convert_loc (((location_t) 0), ((contains_struct_check (
(cand->iv->step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5362, __FUNCTION__))->typed.type), a) );
if (!difference_cannot_overflow_p (data, cand->iv->base, offset))
  return false;

/* Determine the new comparison operator.  */
comp = step < 0 ? GT_EXPR : LT_EXPR;
if (*comp_p == NE_EXPR)
  *comp_p = comp;
else if (*comp_p == EQ_EXPR)
  *comp_p = invert_tree_comparison (comp, false);
else
  gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5373, __FUNCTION__));

return true;
5376}

5378/* Check whether it is possible to express the condition in USE by comparison
 of candidate CAND.  If so, store the value compared with to BOUND, and the
 comparison operator to COMP.  */

5382static bool
5383may_eliminate_iv (struct ivopts_data *data,
  struct iv_use *use, struct iv_cand *cand, tree *bound,
  enum tree_code *comp)
5386{
basic_block ex_bb;
edge exit;
tree period;
class loop *loop = data->current_loop;
aff_tree bnd;
class tree_niter_desc *desc = NULLnullptr;

if (TREE_CODE (cand->iv->step)((enum tree_code) (cand->iv->step)->base.code) != INTEGER_CST)
  return false;

/* For now works only for exits that dominate the loop latch.
   TODO: extend to other conditions inside loop body.  */
ex_bb = gimple_bb (use->stmt);
if (use->stmt != last_stmt (ex_bb)
    || gimple_code (use->stmt) != GIMPLE_COND
    || !dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
  return false;

exit = EDGE_SUCC (ex_bb, 0)(*(ex_bb)->succs)[(0)];
if (flow_bb_inside_loop_p (loop, exit->dest))
  exit = EDGE_SUCC (ex_bb, 1)(*(ex_bb)->succs)[(1)];
if (flow_bb_inside_loop_p (loop, exit->dest))
  return false;

desc = niter_for_exit (data, exit);
if (!desc)
  return false;

/* Determine whether we can use the variable to test the exit condition.
   This is the case iff the period of the induction variable is greater
   than the number of iterations for which the exit condition is true.  */
period = iv_period (cand->iv);

/* If the number of iterations is constant, compare against it directly.  */
if (TREE_CODE (desc->niter)((enum tree_code) (desc->niter)->base.code) == INTEGER_CST)
  {
    /* See cand_value_at.  */
    if (stmt_after_increment (loop, cand, use->stmt))
{
 if (!tree_int_cst_lt (desc->niter, period))
   return false;
}
    else
{
 if (tree_int_cst_lt (period, desc->niter))
   return false;
}
  }

/* If not, and if this is the only possible exit of the loop, see whether
   we can get a conservative estimate on the number of iterations of the
   entire loop and compare against that instead.  */
else
  {
    widest_int period_value, max_niter;

    max_niter = desc->max;
    if (stmt_after_increment (loop, cand, use->stmt))
max_niter += 1;
    period_value = wi::to_widest (period);
    if (wi::gtu_p (max_niter, period_value))
{
 /* See if we can take advantage of inferred loop bound
    information.  */
 if (data->loop_single_exit_p)
   {
     if (!max_loop_iterations (loop, &max_niter))
return false;
     /* The loop bound is already adjusted by adding 1.  */
     if (wi::gtu_p (max_niter, period_value))
return false;
   }
 else
   return false;
}
  }

/* For doloop IV cand, the bound would be zero.  It's safe whether
   may_be_zero set or not.  */
if (cand->doloop_p)
  {
    *bound = build_int_cst (TREE_TYPE (cand->iv->base)((contains_struct_check ((cand->iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5468, __FUNCTION__))->typed.type), 0);
    *comp = iv_elimination_compare (data, use);
    return true;
  }

cand_value_at (loop, cand, use->stmt, desc, &bnd);

*bound = fold_convert (TREE_TYPE (cand->iv->base),fold_convert_loc (((location_t) 0), ((contains_struct_check (
(cand->iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5475, __FUNCTION__))->typed.type), aff_combination_to_tree
 (&bnd))
	 aff_combination_to_tree (&bnd))fold_convert_loc (((location_t) 0), ((contains_struct_check (
(cand->iv->base), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5475, __FUNCTION__))->typed.type), aff_combination_to_tree
 (&bnd));
*comp = iv_elimination_compare (data, use);

/* It is unlikely that computing the number of iterations using division
   would be more profitable than keeping the original induction variable.  */
if (expression_expensive_p (*bound))
  return false;

/* Sometimes, it is possible to handle the situation that the number of
   iterations may be zero unless additional assumptions by using <
   instead of != in the exit condition.

   TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
  base the exit condition on it.  However, that is often too
  expensive.  */
if (!integer_zerop (desc->may_be_zero))
  return iv_elimination_compare_lt (data, cand, comp, desc);

return true;
5495}

/* Calculates the cost of BOUND, if it is a PARM_DECL.  A PARM_DECL must
  be copied, if it is used in the loop body and DATA->body_includes_call.  */

5500static int
5501parm_decl_cost (struct ivopts_data *data, tree bound)
5502{
tree sbound = bound;
STRIP_NOPS (sbound)(sbound) = tree_strip_nop_conversions ((const_cast<union tree_node
 *> (((sbound)))));

if (TREE_CODE (sbound)((enum tree_code) (sbound)->base.code) == SSA_NAME
    && SSA_NAME_IS_DEFAULT_DEF (sbound)(tree_check ((sbound), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5507, __FUNCTION__, (SSA_NAME)))->base.default_def_flag
    && TREE_CODE (SSA_NAME_VAR (sbound))((enum tree_code) (((tree_check ((sbound), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5508, __FUNCTION__, (SSA_NAME)))->ssa_name.var == (tree)
 nullptr || ((enum tree_code) ((sbound)->ssa_name.var)->
base.code) == IDENTIFIER_NODE ? (tree) nullptr : (sbound)->
ssa_name.var))->base.code) == PARM_DECL
    && data->body_includes_call)
  return COSTS_N_INSNS (1)((1) * 4);

return 0;
5513}

5515/* Determines cost of computing the use in GROUP with CAND in a condition.  */

5517static bool
5518determine_group_iv_cost_cond (struct ivopts_data *data,
	      struct iv_group *group, struct iv_cand *cand)
5520{
tree bound = NULL_TREE(tree) nullptr;
struct iv *cmp_iv;
bitmap inv_exprs = NULLnullptr;
bitmap inv_vars_elim = NULLnullptr, inv_vars_express = NULLnullptr, inv_vars;
comp_cost elim_cost = infinite_cost, express_cost, cost, bound_cost;
enum comp_iv_rewrite rewrite_type;
iv_inv_expr_ent *inv_expr_elim = NULLnullptr, *inv_expr_express = NULLnullptr, *inv_expr;
tree *control_var, *bound_cst;
enum tree_code comp = ERROR_MARK;
struct iv_use *use = group->vuses[0];

/* Extract condition operands.  */
rewrite_type = extract_cond_operands (data, use->stmt, &control_var,
			&bound_cst, NULLnullptr, &cmp_iv);
gcc_assert (rewrite_type != COMP_IV_NA)((void)(!(rewrite_type != COMP_IV_NA) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5535, __FUNCTION__), 0 : 0));

/* Try iv elimination.  */
if (rewrite_type == COMP_IV_ELIM
    && may_eliminate_iv (data, use, cand, &bound, &comp))
  {
    elim_cost = force_var_cost (data, bound, &inv_vars_elim);
    if (elim_cost.cost == 0)
elim_cost.cost = parm_decl_cost (data, bound);
    else if (TREE_CODE (bound)((enum tree_code) (bound)->base.code) == INTEGER_CST)
elim_cost.cost = 0;
    /* If we replace a loop condition 'i < n' with 'p < base + n',
inv_vars_elim will have 'base' and 'n' set, which implies that both
'base' and 'n' will be live during the loop.	 More likely,
'base + n' will be loop invariant, resulting in only one live value
during the loop.  So in that case we clear inv_vars_elim and set
inv_expr_elim instead.  */
    if (inv_vars_elim && bitmap_count_bits (inv_vars_elim) > 1)
{
 inv_expr_elim = get_loop_invariant_expr (data, bound);
 bitmap_clear (inv_vars_elim);
}
    /* The bound is a loop invariant, so it will be only computed
once.  */
    elim_cost.cost = adjust_setup_cost (data, elim_cost.cost);
  }

/* When the condition is a comparison of the candidate IV against
   zero, prefer this IV.

   TODO: The constant that we're subtracting from the cost should
   be target-dependent.  This information should be added to the
   target costs for each backend.  */
if (!elim_cost.infinite_cost_p () /* Do not try to decrease infinite! */
    && integer_zerop (*bound_cst)
    && (operand_equal_p (*control_var, cand->var_after, 0)
 || operand_equal_p (*control_var, cand->var_before, 0)))
  elim_cost -= 1;

express_cost = get_computation_cost (data, use, cand, false,
		       &inv_vars_express, NULLnullptr,
		       &inv_expr_express);
if (cmp_iv != NULLnullptr)
  find_inv_vars (data, &cmp_iv->base, &inv_vars_express);

/* Count the cost of the original bound as well.  */
bound_cost = force_var_cost (data, *bound_cst, NULLnullptr);
if (bound_cost.cost == 0)
  bound_cost.cost = parm_decl_cost (data, *bound_cst);
else if (TREE_CODE (*bound_cst)((enum tree_code) (*bound_cst)->base.code) == INTEGER_CST)
  bound_cost.cost = 0;
express_cost += bound_cost;

/* Choose the better approach, preferring the eliminated IV. */
if (elim_cost <= express_cost)
  {
    cost = elim_cost;
    inv_vars = inv_vars_elim;
    inv_vars_elim = NULLnullptr;
    inv_expr = inv_expr_elim;
    /* For doloop candidate/use pair, adjust to zero cost.  */
    if (group->doloop_p && cand->doloop_p && elim_cost.cost > no_cost.cost)
cost = no_cost;
  }
else
  {
    cost = express_cost;
    inv_vars = inv_vars_express;
    inv_vars_express = NULLnullptr;
    bound = NULL_TREE(tree) nullptr;
    comp = ERROR_MARK;
    inv_expr = inv_expr_express;
  }

if (inv_expr)
  {
    inv_exprs = BITMAP_ALLOCbitmap_alloc (NULLnullptr);
    bitmap_set_bit (inv_exprs, inv_expr->id);
  }
set_group_iv_cost (data, group, cand, cost,
     inv_vars, bound, comp, inv_exprs);

if (inv_vars_elim)
  BITMAP_FREE (inv_vars_elim)((void) (bitmap_obstack_free ((bitmap) inv_vars_elim), (inv_vars_elim
) = (bitmap) nullptr));
if (inv_vars_express)
  BITMAP_FREE (inv_vars_express)((void) (bitmap_obstack_free ((bitmap) inv_vars_express), (inv_vars_express
) = (bitmap) nullptr));

return !cost.infinite_cost_p ();
5623}

5625/* Determines cost of computing uses in GROUP with CAND.  Returns false
 if USE cannot be represented with CAND.  */

5628static bool
5629determine_group_iv_cost (struct ivopts_data *data,
	 struct iv_group *group, struct iv_cand *cand)
5631{
switch (group->type)
  {
  case USE_NONLINEAR_EXPR:
    return determine_group_iv_cost_generic (data, group, cand);

  case USE_REF_ADDRESS:
  case USE_PTR_ADDRESS:
    return determine_group_iv_cost_address (data, group, cand);

  case USE_COMPARE:
    return determine_group_iv_cost_cond (data, group, cand);

  default:
    gcc_unreachable ()(fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-ivopts.cc"
, 5645, __FUNCTION__));
  }
5647}

5649/* Return true if get_computation_cost indicates that autoincrement is
 a possibility for the pair of USE and CAND, false otherwise.  */

5652static bool
5653autoinc_possible_for_pair (struct ivopts_data *data, struct iv_use *use,
	   struct iv_cand *cand)
5655{
if (!address_p (use->type))
  return false;

bool can_autoinc = false;
get_computation_cost (data, use, cand, true, NULLnullptr, &can_autoinc, NULLnullptr);
return can_autoinc;
5662}

5664/* Examine IP_ORIGINAL candidates to see if they are incremented next to a
 use that allows autoincrement, and set their AINC_USE if possible.  */

5667static void
5668set_autoinc_for_original_candidates (struct ivopts_data *data)
5669{
unsigned i, j;

for (i = 0; i < data->vcands.length (); i++)
  {
    struct iv_cand *cand = data->vcands[i];
    struct iv_use *closest_before = NULLnullptr;
    struct iv_use *closest_after = NULLnullptr;
    if (cand->pos != IP_ORIGINAL)
continue;

    for (j = 0; j < data->vgroups.length (); j++)
{
 struct iv_group *group = data->vgroups