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

Bug Summary

File:	build/gcc/tree-ssa-loop-im.cc
Warning:	line 1656, column 10 1st function call argument is an uninitialized value
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-suse-linux -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name tree-ssa-loop-im.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-54bjg7.plist -x c++ /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc
1/* Loop invariant motion.
 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#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "backend.h"
24#include "tree.h"
25#include "gimple.h"
26#include "cfghooks.h"
27#include "tree-pass.h"
28#include "ssa.h"
29#include "gimple-pretty-print.h"
30#include "fold-const.h"
31#include "cfganal.h"
32#include "tree-eh.h"
33#include "gimplify.h"
34#include "gimple-iterator.h"
35#include "tree-cfg.h"
36#include "tree-ssa-loop-manip.h"
37#include "tree-ssa-loop.h"
38#include "tree-into-ssa.h"
39#include "cfgloop.h"
40#include "tree-affine.h"
41#include "tree-ssa-propagate.h"
42#include "trans-mem.h"
43#include "gimple-fold.h"
44#include "tree-scalar-evolution.h"
45#include "tree-ssa-loop-niter.h"
46#include "alias.h"
47#include "builtins.h"
48#include "tree-dfa.h"
49#include "tree-ssa.h"
50#include "dbgcnt.h"

52/* TODO:  Support for predicated code motion.  I.e.

 while (1)
   {
     if (cond)
{
  a = inv;
  something;
}
   }

 Where COND and INV are invariants, but evaluating INV may trap or be
 invalid from some other reason if !COND.  This may be transformed to

 if (cond)
   a = inv;
 while (1)
   {
     if (cond)
something;
   }  */

74/* The auxiliary data kept for each statement.  */

76struct lim_aux_data
77{
class loop *max_loop;	/* The outermost loop in that the statement
		   is invariant.  */

class loop *tgt_loop;	/* The loop out of that we want to move the
		   invariant.  */

class loop *always_executed_in;
		/* The outermost loop for that we are sure
		   the statement is executed if the loop
		   is entered.  */

unsigned cost;		/* Cost of the computation performed by the
		   statement.  */

unsigned ref;			/* The simple_mem_ref in this stmt or 0.  */

vec<gimple *> depends;	/* Vector of statements that must be also
		   hoisted out of the loop when this statement
		   is hoisted; i.e. those that define the
		   operands of the statement and are inside of
		   the MAX_LOOP loop.  */
99};

101/* Maps statements to their lim_aux_data.  */

103static hash_map<gimple *, lim_aux_data *> *lim_aux_data_map;

105/* Description of a memory reference location.  */

107struct mem_ref_loc
108{
tree *ref;			/* The reference itself.  */
gimple *stmt;			/* The statement in that it occurs.  */
111};


114/* Description of a memory reference.  */

116class im_mem_ref
117{
118public:
unsigned id : 30;		/* ID assigned to the memory reference
		   (its index in memory_accesses.refs_list)  */
unsigned ref_canonical : 1;   /* Whether mem.ref was canonicalized.  */
unsigned ref_decomposed : 1;  /* Whether the ref was hashed from mem.  */
hashval_t hash;		/* Its hash value.  */

/* The memory access itself and associated caching of alias-oracle
   query meta-data.  We are using mem.ref == error_mark_node for the
   case the reference is represented by its single access stmt
   in accesses_in_loop[0].  */
ao_ref mem;

bitmap stored;		/* The set of loops in that this memory location
		   is stored to.  */
bitmap loaded;		/* The set of loops in that this memory location
		   is loaded from.  */
vec<mem_ref_loc>		accesses_in_loop;
		/* The locations of the accesses.  */

/* The following set is computed on demand.  */
bitmap_head dep_loop;		/* The set of loops in that the memory
		   reference is {in,}dependent in
		   different modes.  */
142};

144/* We use six bits per loop in the ref->dep_loop bitmap to record
 the dep_kind x dep_state combinations.  */

147enum dep_kind { lim_raw, sm_war, sm_waw };
148enum dep_state { dep_unknown, dep_independent, dep_dependent };

150/* coldest outermost loop for given loop.  */
151vec<class loop *> coldest_outermost_loop;
152/* hotter outer loop nearest to given loop.  */
153vec<class loop *> hotter_than_inner_loop;

155/* Populate the loop dependence cache of REF for LOOP, KIND with STATE.  */

157static void
158record_loop_dependence (class loop *loop, im_mem_ref *ref,
	dep_kind kind, dep_state state)
160{
gcc_assert (state != dep_unknown)((void)(!(state != dep_unknown) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 161, __FUNCTION__), 0 : 0));
unsigned bit = 6 * loop->num + kind * 2 + state == dep_dependent ? 1 : 0;
bitmap_set_bit (&ref->dep_loop, bit);
164}

166/* Query the loop dependence cache of REF for LOOP, KIND.  */

168static dep_state
169query_loop_dependence (class loop *loop, im_mem_ref *ref, dep_kind kind)
170{
unsigned first_bit = 6 * loop->num + kind * 2;
if (bitmap_bit_p (&ref->dep_loop, first_bit))
  return dep_independent;
else if (bitmap_bit_p (&ref->dep_loop, first_bit + 1))
  return dep_dependent;
return dep_unknown;
177}

179/* Mem_ref hashtable helpers.  */

181struct mem_ref_hasher : nofree_ptr_hash <im_mem_ref>
182{
typedef ao_ref *compare_type;
static inline hashval_t hash (const im_mem_ref *);
static inline bool equal (const im_mem_ref *, const ao_ref *);
186};

188/* A hash function for class im_mem_ref object OBJ.  */

190inline hashval_t
191mem_ref_hasher::hash (const im_mem_ref *mem)
192{
return mem->hash;
194}

196/* An equality function for class im_mem_ref object MEM1 with
 memory reference OBJ2.  */

199inline bool
200mem_ref_hasher::equal (const im_mem_ref *mem1, const ao_ref *obj2)
201{
if (obj2->max_size_known_p ())
  return (mem1->ref_decomposed
   && ((TREE_CODE (mem1->mem.base)((enum tree_code) (mem1->mem.base)->base.code) == MEM_REF
 && TREE_CODE (obj2->base)((enum tree_code) (obj2->base)->base.code) == MEM_REF
 && operand_equal_p (TREE_OPERAND (mem1->mem.base, 0)(*((const_cast<tree*> (tree_operand_check ((mem1->mem
.base), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 206, __FUNCTION__))))),
		     TREE_OPERAND (obj2->base, 0)(*((const_cast<tree*> (tree_operand_check ((obj2->base
), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 207, __FUNCTION__))))), 0)
 && known_eq (mem_ref_offset (mem1->mem.base) * BITS_PER_UNIT + mem1->mem.offset,(!maybe_ne (mem_ref_offset (mem1->mem.base) * (8) + mem1->
mem.offset, mem_ref_offset (obj2->base) * (8) + obj2->offset
))
	      mem_ref_offset (obj2->base) * BITS_PER_UNIT + obj2->offset)(!maybe_ne (mem_ref_offset (mem1->mem.base) * (8) + mem1->
mem.offset, mem_ref_offset (obj2->base) * (8) + obj2->offset
)))
|| (operand_equal_p (mem1->mem.base, obj2->base, 0)
    && known_eq (mem1->mem.offset, obj2->offset)(!maybe_ne (mem1->mem.offset, obj2->offset))))
   && known_eq (mem1->mem.size, obj2->size)(!maybe_ne (mem1->mem.size, obj2->size))
   && known_eq (mem1->mem.max_size, obj2->max_size)(!maybe_ne (mem1->mem.max_size, obj2->max_size))
   && mem1->mem.volatile_p == obj2->volatile_p
   && (mem1->mem.ref_alias_set == obj2->ref_alias_set
/* We are not canonicalizing alias-sets but for the
   special-case we didn't canonicalize yet and the
   incoming ref is a alias-set zero MEM we pick
   the correct one already.  */
|| (!mem1->ref_canonical
    && (TREE_CODE (obj2->ref)((enum tree_code) (obj2->ref)->base.code) == MEM_REF
	|| TREE_CODE (obj2->ref)((enum tree_code) (obj2->ref)->base.code) == TARGET_MEM_REF)
    && obj2->ref_alias_set == 0)
/* Likewise if there's a canonical ref with alias-set zero.  */
|| (mem1->ref_canonical && mem1->mem.ref_alias_set == 0))
   && types_compatible_p (TREE_TYPE (mem1->mem.ref)((contains_struct_check ((mem1->mem.ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 226, __FUNCTION__))->typed.type),
		   TREE_TYPE (obj2->ref)((contains_struct_check ((obj2->ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 227, __FUNCTION__))->typed.type)));
else
  return operand_equal_p (mem1->mem.ref, obj2->ref, 0);
230}


233/* Description of memory accesses in loops.  */

235static struct
236{
/* The hash table of memory references accessed in loops.  */
hash_table<mem_ref_hasher> *refs;

/* The list of memory references.  */
vec<im_mem_ref *> refs_list;

/* The set of memory references accessed in each loop.  */
vec<bitmap_head> refs_loaded_in_loop;

/* The set of memory references stored in each loop.  */
vec<bitmap_head> refs_stored_in_loop;

/* The set of memory references stored in each loop, including subloops .  */
vec<bitmap_head> all_refs_stored_in_loop;

/* Cache for expanding memory addresses.  */
hash_map<tree, name_expansion *> *ttae_cache;
254} memory_accesses;

256/* Obstack for the bitmaps in the above data structures.  */
257static bitmap_obstack lim_bitmap_obstack;
258static obstack mem_ref_obstack;

260static bool ref_indep_loop_p (class loop *, im_mem_ref *, dep_kind);
261static bool ref_always_accessed_p (class loop *, im_mem_ref *, bool);
262static bool refs_independent_p (im_mem_ref *, im_mem_ref *, bool = true);

264/* Minimum cost of an expensive expression.  */
265#define LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive) ((unsigned) param_lim_expensiveglobal_options.x_param_lim_expensive)

267/* The outermost loop for which execution of the header guarantees that the
 block will be executed.  */
269#define ALWAYS_EXECUTED_IN(BB)((class loop *) (BB)->aux) ((class loop *) (BB)->aux)
270#define SET_ALWAYS_EXECUTED_IN(BB, VAL)((BB)->aux = (void *) (VAL)) ((BB)->aux = (void *) (VAL))

272/* ID of the shared unanalyzable mem.  */
273#define UNANALYZABLE_MEM_ID0 0

275/* Whether the reference was analyzable.  */
276#define MEM_ANALYZABLE(REF)((REF)->id != 0) ((REF)->id != UNANALYZABLE_MEM_ID0)

278static struct lim_aux_data *
279init_lim_data (gimple *stmt)
280{
lim_aux_data *p = XCNEW (struct lim_aux_data)((struct lim_aux_data *) xcalloc (1, sizeof (struct lim_aux_data
)));
lim_aux_data_map->put (stmt, p);

return p;
285}

287static struct lim_aux_data *
288get_lim_data (gimple *stmt)
289{
lim_aux_data **p = lim_aux_data_map->get (stmt);
if (!p)
  return NULLnullptr;

return *p;
295}

297/* Releases the memory occupied by DATA.  */

299static void
300free_lim_aux_data (struct lim_aux_data *data)
301{
data->depends.release ();
free (data);
304}

306static void
307clear_lim_data (gimple *stmt)
308{
lim_aux_data **p = lim_aux_data_map->get (stmt);
if (!p)
  return;

free_lim_aux_data (*p);
*p = NULLnullptr;
315}


318/* The possibilities of statement movement.  */
319enum move_pos
{
  MOVE_IMPOSSIBLE,		/* No movement -- side effect expression.  */
  MOVE_PRESERVE_EXECUTION,	/* Must not cause the non-executed statement
		   become executed -- memory accesses, ... */
  MOVE_POSSIBLE		/* Unlimited movement.  */
};


328/* If it is possible to hoist the statement STMT unconditionally,
 returns MOVE_POSSIBLE.
 If it is possible to hoist the statement STMT, but we must avoid making
 it executed if it would not be executed in the original program (e.g.
 because it may trap), return MOVE_PRESERVE_EXECUTION.
 Otherwise return MOVE_IMPOSSIBLE.  */

335static enum move_pos
336movement_possibility_1 (gimple *stmt)
337{
tree lhs;
enum move_pos ret = MOVE_POSSIBLE;

if (flag_unswitch_loopsglobal_options.x_flag_unswitch_loops
    && gimple_code (stmt) == GIMPLE_COND)
  {
    /* If we perform unswitching, force the operands of the invariant
condition to be moved out of the loop.  */
    return MOVE_POSSIBLE;
  }

if (gimple_code (stmt) == GIMPLE_PHI
    && gimple_phi_num_args (stmt) <= 2
    && !virtual_operand_p (gimple_phi_result (stmt))
    && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt))(tree_check ((gimple_phi_result (stmt)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 352, __FUNCTION__, (SSA_NAME)))->base.asm_written_flag)
  return MOVE_POSSIBLE;

if (gimple_get_lhs (stmt) == NULL_TREE(tree) nullptr)
  return MOVE_IMPOSSIBLE;

if (gimple_vdef (stmt))
  return MOVE_IMPOSSIBLE;

if (stmt_ends_bb_p (stmt)
    || gimple_has_volatile_ops (stmt)
    || gimple_has_side_effects (stmt)
    || stmt_could_throw_p (cfun(cfun + 0), stmt))
  return MOVE_IMPOSSIBLE;

if (is_gimple_call (stmt))
  {
    /* While pure or const call is guaranteed to have no side effects, we
cannot move it arbitrarily.  Consider code like

char *s = something ();

while (1)
  {
    if (s)
      t = strlen (s);
    else
      t = 0;
  }

Here the strlen call cannot be moved out of the loop, even though
s is invariant.  In addition to possibly creating a call with
invalid arguments, moving out a function call that is not executed
may cause performance regressions in case the call is costly and
not executed at all.  */
    ret = MOVE_PRESERVE_EXECUTION;
    lhs = gimple_call_lhs (stmt);
  }
else if (is_gimple_assign (stmt))
  lhs = gimple_assign_lhs (stmt);
else
  return MOVE_IMPOSSIBLE;

if (TREE_CODE (lhs)((enum tree_code) (lhs)->base.code) == SSA_NAME
    && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)(tree_check ((lhs), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 396, __FUNCTION__, (SSA_NAME)))->base.asm_written_flag)
  return MOVE_IMPOSSIBLE;

if (TREE_CODE (lhs)((enum tree_code) (lhs)->base.code) != SSA_NAME
    || gimple_could_trap_p (stmt))
  return MOVE_PRESERVE_EXECUTION;

/* Non local loads in a transaction cannot be hoisted out.  Well,
   unless the load happens on every path out of the loop, but we
   don't take this into account yet.  */
if (flag_tmglobal_options.x_flag_tm
    && gimple_in_transaction (stmt)
    && gimple_assign_single_p (stmt))
  {
    tree rhs = gimple_assign_rhs1 (stmt);
    if (DECL_P (rhs)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (rhs)->base.code))] == tcc_declaration) && is_global_var (rhs))
{
 if (dump_file)
   {
     fprintf (dump_file, "Cannot hoist conditional load of ");
     print_generic_expr (dump_file, rhs, TDF_SLIM);
     fprintf (dump_file, " because it is in a transaction.\n");
   }
 return MOVE_IMPOSSIBLE;
}
  }

return ret;
424}

426static enum move_pos
427movement_possibility (gimple *stmt)
428{
enum move_pos pos = movement_possibility_1 (stmt);
if (pos == MOVE_POSSIBLE)
  {
    use_operand_p use_p;
    ssa_op_iter ssa_iter;
    FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, ssa_iter, SSA_OP_USE)for ((use_p) = (gimple_code (stmt) == GIMPLE_PHI ? op_iter_init_phiuse
 (&(ssa_iter), as_a <gphi *> (stmt), 0x01) : op_iter_init_use
 (&(ssa_iter), stmt, 0x01)); !op_iter_done (&(ssa_iter
)); (use_p) = op_iter_next_use (&(ssa_iter)))
if (TREE_CODE (USE_FROM_PTR (use_p))((enum tree_code) (get_use_from_ptr (use_p))->base.code) == SSA_NAME
   && ssa_name_maybe_undef_p (USE_FROM_PTR (use_p)get_use_from_ptr (use_p)))
 return MOVE_PRESERVE_EXECUTION;
  }
return pos;
440}


443/* Compare the profile count inequality of bb and loop's preheader, it is
 three-state as stated in profile-count.h, FALSE is returned if inequality
 cannot be decided.  */
446bool
447bb_colder_than_loop_preheader (basic_block bb, class loop *loop)
448{
gcc_assert (bb && loop)((void)(!(bb && loop) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 449, __FUNCTION__), 0 : 0));
return bb->count < loop_preheader_edge (loop)->src->count;
451}

453/* Check coldest loop between OUTERMOST_LOOP and LOOP by comparing profile
 count.
It does three steps check:
1) Check whether CURR_BB is cold in it's own loop_father, if it is cold, just
return NULL which means it should not be moved out at all;
2) CURR_BB is NOT cold, check if pre-computed COLDEST_LOOP is outside of
OUTERMOST_LOOP, if it is inside of OUTERMOST_LOOP, return the COLDEST_LOOP;
3) If COLDEST_LOOP is outside of OUTERMOST_LOOP, check whether there is a
hotter loop between OUTERMOST_LOOP and loop in pre-computed
HOTTER_THAN_INNER_LOOP, return it's nested inner loop, otherwise return
OUTERMOST_LOOP.
At last, the coldest_loop is inside of OUTERMOST_LOOP, just return it as
the hoist target.  */

467static class loop *
468get_coldest_out_loop (class loop *outermost_loop, class loop *loop,
      basic_block curr_bb)
470{
gcc_assert (outermost_loop == loop((void)(!(outermost_loop == loop || flow_loop_nested_p (outermost_loop
, loop)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 472, __FUNCTION__), 0 : 0))
     || flow_loop_nested_p (outermost_loop, loop))((void)(!(outermost_loop == loop || flow_loop_nested_p (outermost_loop
, loop)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 472, __FUNCTION__), 0 : 0));

/* If bb_colder_than_loop_preheader returns false due to three-state
  comparision, OUTERMOST_LOOP is returned finally to preserve the behavior.
  Otherwise, return the coldest loop between OUTERMOST_LOOP and LOOP.  */
if (curr_bb && bb_colder_than_loop_preheader (curr_bb, loop))
  return NULLnullptr;

class loop *coldest_loop = coldest_outermost_loop[loop->num];
if (loop_depth (coldest_loop) < loop_depth (outermost_loop))
  {
    class loop *hotter_loop = hotter_than_inner_loop[loop->num];
    if (!hotter_loop
 || loop_depth (hotter_loop) < loop_depth (outermost_loop))
return outermost_loop;

    /*  hotter_loop is between OUTERMOST_LOOP and LOOP like:
[loop tree root, ..., coldest_loop, ..., outermost_loop, ...,
hotter_loop, second_coldest_loop, ..., loop]
return second_coldest_loop to be the hoist target.  */
    class loop *aloop;
    for (aloop = hotter_loop->inner; aloop; aloop = aloop->next)
if (aloop == loop || flow_loop_nested_p (aloop, loop))
 return aloop;
  }
return coldest_loop;
498}

500/* Suppose that operand DEF is used inside the LOOP.  Returns the outermost
 loop to that we could move the expression using DEF if it did not have
 other operands, i.e. the outermost loop enclosing LOOP in that the value
 of DEF is invariant.  */

505static class loop *
506outermost_invariant_loop (tree def, class loop *loop)
507{
gimple *def_stmt;
basic_block def_bb;
class loop *max_loop;
struct lim_aux_data *lim_data;

if (!def)
  return superloop_at_depth (loop, 1);

if (TREE_CODE (def)((enum tree_code) (def)->base.code) != SSA_NAME)
  {
    gcc_assert (is_gimple_min_invariant (def))((void)(!(is_gimple_min_invariant (def)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 518, __FUNCTION__), 0 : 0));
    return superloop_at_depth (loop, 1);
  }

def_stmt = SSA_NAME_DEF_STMT (def)(tree_check ((def), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 522, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
def_bb = gimple_bb (def_stmt);
if (!def_bb)
  return superloop_at_depth (loop, 1);

max_loop = find_common_loop (loop, def_bb->loop_father);

lim_data = get_lim_data (def_stmt);
if (lim_data != NULLnullptr && lim_data->max_loop != NULLnullptr)
  max_loop = find_common_loop (max_loop,
		 loop_outer (lim_data->max_loop));
if (max_loop == loop)
  return NULLnullptr;
max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);

return max_loop;
538}

540/* DATA is a structure containing information associated with a statement
 inside LOOP.  DEF is one of the operands of this statement.

 Find the outermost loop enclosing LOOP in that value of DEF is invariant
 and record this in DATA->max_loop field.  If DEF itself is defined inside
 this loop as well (i.e. we need to hoist it out of the loop if we want
 to hoist the statement represented by DATA), record the statement in that
 DEF is defined to the DATA->depends list.  Additionally if ADD_COST is true,
 add the cost of the computation of DEF to the DATA->cost.

 If DEF is not invariant in LOOP, return false.  Otherwise return TRUE.  */

552static bool
553add_dependency (tree def, struct lim_aux_data *data, class loop *loop,
bool add_cost)
555{
gimple *def_stmt = SSA_NAME_DEF_STMT (def)(tree_check ((def), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 556, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
basic_block def_bb = gimple_bb (def_stmt);
class loop *max_loop;
struct lim_aux_data *def_data;

if (!def_bb)
  return true;

max_loop = outermost_invariant_loop (def, loop);
if (!max_loop)
  return false;

if (flow_loop_nested_p (data->max_loop, max_loop))
  data->max_loop = max_loop;

def_data = get_lim_data (def_stmt);
if (!def_data)
  return true;

if (add_cost
    /* Only add the cost if the statement defining DEF is inside LOOP,
i.e. if it is likely that by moving the invariants dependent
on it, we will be able to avoid creating a new register for
it (since it will be only used in these dependent invariants).  */
    && def_bb->loop_father == loop)
  data->cost += def_data->cost;

data->depends.safe_push (def_stmt);

return true;
586}

588/* Returns an estimate for a cost of statement STMT.  The values here
 are just ad-hoc constants, similar to costs for inlining.  */

591static unsigned
592stmt_cost (gimple *stmt)
593{
/* Always try to create possibilities for unswitching.  */
if (gimple_code (stmt) == GIMPLE_COND
    || gimple_code (stmt) == GIMPLE_PHI)
  return LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive);

/* We should be hoisting calls if possible.  */
if (is_gimple_call (stmt))
  {
    tree fndecl;

    /* Unless the call is a builtin_constant_p; this always folds to a
constant, so moving it is useless.  */
    fndecl = gimple_call_fndecl (stmt);
    if (fndecl && fndecl_built_in_p (fndecl, BUILT_IN_CONSTANT_P))
return 0;

    return LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive);
  }

/* Hoisting memory references out should almost surely be a win.  */
if (gimple_references_memory_p (stmt))
  return LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive);

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

switch (gimple_assign_rhs_code (stmt))
  {
  case MULT_EXPR:
  case WIDEN_MULT_EXPR:
  case WIDEN_MULT_PLUS_EXPR:
  case WIDEN_MULT_MINUS_EXPR:
  case DOT_PROD_EXPR:
  case TRUNC_DIV_EXPR:
  case CEIL_DIV_EXPR:
  case FLOOR_DIV_EXPR:
  case ROUND_DIV_EXPR:
  case EXACT_DIV_EXPR:
  case CEIL_MOD_EXPR:
  case FLOOR_MOD_EXPR:
  case ROUND_MOD_EXPR:
  case TRUNC_MOD_EXPR:
  case RDIV_EXPR:
    /* Division and multiplication are usually expensive.  */
    return LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive);

  case LSHIFT_EXPR:
  case RSHIFT_EXPR:
  case WIDEN_LSHIFT_EXPR:
  case LROTATE_EXPR:
  case RROTATE_EXPR:
    /* Shifts and rotates are usually expensive.  */
    return LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive);

  case CONSTRUCTOR:
    /* Make vector construction cost proportional to the number
       of elements.  */
    return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt))(vec_safe_length (((tree_check ((gimple_assign_rhs1 (stmt)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 651, __FUNCTION__, (CONSTRUCTOR)))->constructor.elts)));

  case SSA_NAME:
  case PAREN_EXPR:
    /* Whether or not something is wrapped inside a PAREN_EXPR
       should not change move cost.  Nor should an intermediate
unpropagated SSA name copy.  */
    return 0;

  default:
    return 1;
  }
663}

665/* Finds the outermost loop between OUTER and LOOP in that the memory reference
 REF is independent.  If REF is not independent in LOOP, NULL is returned
 instead.  */

669static class loop *
670outermost_indep_loop (class loop *outer, class loop *loop, im_mem_ref *ref)
671{
class loop *aloop;

if (ref->stored && bitmap_bit_p (ref->stored, loop->num))
  return NULLnullptr;

for (aloop = outer;
     aloop != loop;
     aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
  if ((!ref->stored || !bitmap_bit_p (ref->stored, aloop->num))
&& ref_indep_loop_p (aloop, ref, lim_raw))
    return aloop;

if (ref_indep_loop_p (loop, ref, lim_raw))
  return loop;
else
  return NULLnullptr;
688}

690/* If there is a simple load or store to a memory reference in STMT, returns
 the location of the memory reference, and sets IS_STORE according to whether
 it is a store or load.  Otherwise, returns NULL.  */

694static tree *
695simple_mem_ref_in_stmt (gimple *stmt, bool *is_store)
696{
tree *lhs, *rhs;

/* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns.  */
if (!gimple_assign_single_p (stmt))
19
←
Assuming the condition is false→
20
←
Taking false branch→
  return NULLnullptr;

lhs = gimple_assign_lhs_ptr (stmt);
rhs = gimple_assign_rhs1_ptr (stmt);

if (TREE_CODE (*lhs)((enum tree_code) (*lhs)->base.code) == SSA_NAME && gimple_vuse (stmt))
21
←
Assuming pointer value is null→
22
←
Assuming field 'code' is not equal to SSA_NAME→
  {
    *is_store = false;
    return rhs;
  }
else if (gimple_vdef (stmt)
23
←
Assuming the condition is true→
  && (TREE_CODE (*rhs)((enum tree_code) (*rhs)->base.code) == SSA_NAME || is_gimple_min_invariant (*rhs)))
24
←
Assuming field 'code' is equal to SSA_NAME→
  {
    *is_store = true;
    return lhs;
25
←
Returning pointer (loaded from 'lhs'), which participates in a condition later→
  }
else
  return NULLnullptr;
719}

721/* From a controlling predicate in DOM determine the arguments from
 the PHI node PHI that are chosen if the predicate evaluates to
 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
 they are non-NULL.  Returns true if the arguments can be determined,
 else return false.  */

727static bool
728extract_true_false_args_from_phi (basic_block dom, gphi *phi,
		  tree *true_arg_p, tree *false_arg_p)
730{
edge te, fe;
if (! extract_true_false_controlled_edges (dom, gimple_bb (phi),
			     &te, &fe))
  return false;

if (true_arg_p)
  *true_arg_p = PHI_ARG_DEF (phi, te->dest_idx)gimple_phi_arg_def ((phi), (te->dest_idx));
if (false_arg_p)
  *false_arg_p = PHI_ARG_DEF (phi, fe->dest_idx)gimple_phi_arg_def ((phi), (fe->dest_idx));

return true;
742}

744/* Determine the outermost loop to that it is possible to hoist a statement
 STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
 the outermost loop in that the value computed by STMT is invariant.
 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
 we preserve the fact whether STMT is executed.  It also fills other related
 information to LIM_DATA (STMT).

 The function returns false if STMT cannot be hoisted outside of the loop it
 is defined in, and true otherwise.  */

754static bool
755determine_max_movement (gimple *stmt, bool must_preserve_exec)
756{
basic_block bb = gimple_bb (stmt);
class loop *loop = bb->loop_father;
class loop *level;
struct lim_aux_data *lim_data = get_lim_data (stmt);
tree val;
ssa_op_iter iter;

if (must_preserve_exec)
  level = ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux);
else
  level = superloop_at_depth (loop, 1);
lim_data->max_loop = get_coldest_out_loop (level, loop, bb);
if (!lim_data->max_loop)
  return false;

if (gphi *phi = dyn_cast <gphi *> (stmt))
  {
    use_operand_p use_p;
    unsigned min_cost = UINT_MAX(2147483647 *2U +1U);
    unsigned total_cost = 0;
    struct lim_aux_data *def_data;

    /* We will end up promoting dependencies to be unconditionally
evaluated.  For this reason the PHI cost (and thus the
cost we remove from the loop by doing the invariant motion)
is that of the cheapest PHI argument dependency chain.  */
    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)))
{
 val = USE_FROM_PTR (use_p)get_use_from_ptr (use_p);

 if (TREE_CODE (val)((enum tree_code) (val)->base.code) != SSA_NAME)
   {
     /* Assign const 1 to constants.  */
     min_cost = MIN (min_cost, 1)((min_cost) < (1) ? (min_cost) : (1));
     total_cost += 1;
     continue;
   }
 if (!add_dependency (val, lim_data, loop, false))
   return false;

 gimple *def_stmt = SSA_NAME_DEF_STMT (val)(tree_check ((val), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 797, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
 if (gimple_bb (def_stmt)
     && gimple_bb (def_stmt)->loop_father == loop)
   {
     def_data = get_lim_data (def_stmt);
     if (def_data)
{
  min_cost = MIN (min_cost, def_data->cost)((min_cost) < (def_data->cost) ? (min_cost) : (def_data
->cost));
  total_cost += def_data->cost;
}
   }
}

    min_cost = MIN (min_cost, total_cost)((min_cost) < (total_cost) ? (min_cost) : (total_cost));
    lim_data->cost += min_cost;

    if (gimple_phi_num_args (phi) > 1)
{
 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
 gimple *cond;
 if (gsi_end_p (gsi_last_bb (dom)))
   return false;
 cond = gsi_stmt (gsi_last_bb (dom));
 if (gimple_code (cond) != GIMPLE_COND)
   return false;
 /* Verify that this is an extended form of a diamond and
    the PHI arguments are completely controlled by the
    predicate in DOM.  */
 if (!extract_true_false_args_from_phi (dom, phi, NULLnullptr, NULLnullptr))
   return false;

 /* Fold in dependencies and cost of the condition.  */
 FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)for (val = op_iter_init_tree (&(iter), cond, 0x01); !op_iter_done
 (&(iter)); (void) (val = op_iter_next_tree (&(iter))
))
   {
     if (!add_dependency (val, lim_data, loop, false))
return false;
     def_data = get_lim_data (SSA_NAME_DEF_STMT (val)(tree_check ((val), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 833, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt);
     if (def_data)
lim_data->cost += def_data->cost;
   }

 /* We want to avoid unconditionally executing very expensive
    operations.  As costs for our dependencies cannot be
    negative just claim we are not invariand for this case.
    We also are not sure whether the control-flow inside the
    loop will vanish.  */
 if (total_cost - min_cost >= 2 * LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive)
     && !(min_cost != 0
   && total_cost / min_cost <= 2))
   return false;

 /* Assume that the control-flow in the loop will vanish.
    ???  We should verify this and not artificially increase
    the cost if that is not the case.  */
 lim_data->cost += stmt_cost (stmt);
}

    return true;
  }

/* A stmt that receives abnormal edges cannot be hoisted.  */
if (is_a <gcall *> (stmt)
    && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE(1 << 7)))
  return false;

FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)for (val = op_iter_init_tree (&(iter), stmt, 0x01); !op_iter_done
 (&(iter)); (void) (val = op_iter_next_tree (&(iter))
))
  if (!add_dependency (val, lim_data, loop, true))
    return false;

if (gimple_vuse (stmt))
  {
    im_mem_ref *ref
= lim_data ? memory_accesses.refs_list[lim_data->ref] : NULLnullptr;
    if (ref
 && MEM_ANALYZABLE (ref)((ref)->id != 0))
{
 lim_data->max_loop = outermost_indep_loop (lim_data->max_loop,
				     loop, ref);
 if (!lim_data->max_loop)
   return false;
}
    else if (! add_dependency (gimple_vuse (stmt), lim_data, loop, false))
return false;
  }

lim_data->cost += stmt_cost (stmt);

return true;
885}

887/* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
 and that one of the operands of this statement is computed by STMT.
 Ensure that STMT (together with all the statements that define its
 operands) is hoisted at least out of the loop LEVEL.  */

892static void
893set_level (gimple *stmt, class loop *orig_loop, class loop *level)
894{
class loop *stmt_loop = gimple_bb (stmt)->loop_father;
struct lim_aux_data *lim_data;
gimple *dep_stmt;
unsigned i;

stmt_loop = find_common_loop (orig_loop, stmt_loop);
lim_data = get_lim_data (stmt);
if (lim_data != NULLnullptr && lim_data->tgt_loop != NULLnullptr)
  stmt_loop = find_common_loop (stmt_loop,
		  loop_outer (lim_data->tgt_loop));
if (flow_loop_nested_p (stmt_loop, level))
  return;

gcc_assert (level == lim_data->max_loop((void)(!(level == lim_data->max_loop || flow_loop_nested_p
 (lim_data->max_loop, level)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 909, __FUNCTION__), 0 : 0))
     || flow_loop_nested_p (lim_data->max_loop, level))((void)(!(level == lim_data->max_loop || flow_loop_nested_p
 (lim_data->max_loop, level)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 909, __FUNCTION__), 0 : 0));

lim_data->tgt_loop = level;
FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt)for (i = 0; (lim_data->depends).iterate ((i), &(dep_stmt
)); ++(i))
  set_level (dep_stmt, orig_loop, level);
914}

916/* Determines an outermost loop from that we want to hoist the statement STMT.
 For now we chose the outermost possible loop.  TODO -- use profiling
 information to set it more sanely.  */

920static void
921set_profitable_level (gimple *stmt)
922{
set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
924}

926/* Returns true if STMT is a call that has side effects.  */

928static bool
929nonpure_call_p (gimple *stmt)
930{
if (gimple_code (stmt) != GIMPLE_CALL)
  return false;

return gimple_has_side_effects (stmt);
935}

937/* Rewrite a/b to a*(1/b).  Return the invariant stmt to process.  */

939static gimple *
940rewrite_reciprocal (gimple_stmt_iterator *bsi)
941{
gassign *stmt, *stmt1, *stmt2;
tree name, lhs, type;
tree real_one;
gimple_stmt_iterator gsi;

stmt = as_a <gassign *> (gsi_stmt (*bsi));
lhs = gimple_assign_lhs (stmt);
type = TREE_TYPE (lhs)((contains_struct_check ((lhs), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 949, __FUNCTION__))->typed.type);

real_one = build_one_cst (type);

name = make_temp_ssa_name (type, NULLnullptr, "reciptmp");
stmt1 = gimple_build_assign (name, RDIV_EXPR, real_one,
	       gimple_assign_rhs2 (stmt));
stmt2 = gimple_build_assign (lhs, MULT_EXPR, name,
	       gimple_assign_rhs1 (stmt));

/* Replace division stmt with reciprocal and multiply stmts.
   The multiply stmt is not invariant, so update iterator
   and avoid rescanning.  */
gsi = *bsi;
gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
gsi_replace (&gsi, stmt2, true);

/* Continue processing with invariant reciprocal statement.  */
return stmt1;
968}

970/* Check if the pattern at *BSI is a bittest of the form
 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0.  */

973static gimple *
974rewrite_bittest (gimple_stmt_iterator *bsi)
975{
gassign *stmt;
gimple *stmt1;
gassign *stmt2;
gimple *use_stmt;
gcond *cond_stmt;
tree lhs, name, t, a, b;
use_operand_p use;

stmt = as_a <gassign *> (gsi_stmt (*bsi));
lhs = gimple_assign_lhs (stmt);

/* Verify that the single use of lhs is a comparison against zero.  */
if (TREE_CODE (lhs)((enum tree_code) (lhs)->base.code) != SSA_NAME
    || !single_imm_use (lhs, &use, &use_stmt))
  return stmt;
cond_stmt = dyn_cast <gcond *> (use_stmt);
if (!cond_stmt)
  return stmt;
if (gimple_cond_lhs (cond_stmt) != lhs
    || (gimple_cond_code (cond_stmt) != NE_EXPR
 && gimple_cond_code (cond_stmt) != EQ_EXPR)
    || !integer_zerop (gimple_cond_rhs (cond_stmt)))
  return stmt;

/* Get at the operands of the shift.  The rhs is TMP1 & 1.  */
stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt))(tree_check ((gimple_assign_rhs1 (stmt)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1001, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
if (gimple_code (stmt1) != GIMPLE_ASSIGN)
  return stmt;

/* There is a conversion in between possibly inserted by fold.  */
if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1))((gimple_assign_rhs_code (stmt1)) == NOP_EXPR || (gimple_assign_rhs_code
 (stmt1)) == CONVERT_EXPR))
  {
    t = gimple_assign_rhs1 (stmt1);
    if (TREE_CODE (t)((enum tree_code) (t)->base.code) != SSA_NAME
 || !has_single_use (t))
return stmt;
    stmt1 = SSA_NAME_DEF_STMT (t)(tree_check ((t), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1012, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
    if (gimple_code (stmt1) != GIMPLE_ASSIGN)
return stmt;
  }

/* Verify that B is loop invariant but A is not.  Verify that with
   all the stmt walking we are still in the same loop.  */
if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
    || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
  return stmt;

a = gimple_assign_rhs1 (stmt1);
b = gimple_assign_rhs2 (stmt1);

if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULLnullptr
    && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULLnullptr)
  {
    gimple_stmt_iterator rsi;

    /* 1 << B */
    t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),fold_build2_loc (((location_t) 0), LSHIFT_EXPR, ((contains_struct_check
 ((a), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1032, __FUNCTION__))->typed.type), build_int_cst (((contains_struct_check
 ((a), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1033, __FUNCTION__))->typed.type), 1), b )
       build_int_cst (TREE_TYPE (a), 1), b)fold_build2_loc (((location_t) 0), LSHIFT_EXPR, ((contains_struct_check
 ((a), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1032, __FUNCTION__))->typed.type), build_int_cst (((contains_struct_check
 ((a), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1033, __FUNCTION__))->typed.type), 1), b );
    name = make_temp_ssa_name (TREE_TYPE (a)((contains_struct_check ((a), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1034, __FUNCTION__))->typed.type), NULLnullptr, "shifttmp");
    stmt1 = gimple_build_assign (name, t);

    /* A & (1 << B) */
    t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name)fold_build2_loc (((location_t) 0), BIT_AND_EXPR, ((contains_struct_check
 ((a), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1038, __FUNCTION__))->typed.type), a, name );
    name = make_temp_ssa_name (TREE_TYPE (a)((contains_struct_check ((a), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1039, __FUNCTION__))->typed.type), NULLnullptr, "shifttmp");
    stmt2 = gimple_build_assign (name, t);

    /* Replace the SSA_NAME we compare against zero.  Adjust
the type of zero accordingly.  */
    SET_USE (use, name)set_ssa_use_from_ptr (use, name);
    gimple_cond_set_rhs (cond_stmt,
	   build_int_cst_type (TREE_TYPE (name)((contains_struct_check ((name), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1046, __FUNCTION__))->typed.type),
			       0));

    /* Don't use gsi_replace here, none of the new assignments sets
the variable originally set in stmt.  Move bsi to stmt1, and
then remove the original stmt, so that we get a chance to
retain debug info for it.  */
    rsi = *bsi;
    gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
    gsi_insert_before (&rsi, stmt2, GSI_SAME_STMT);
    gimple *to_release = gsi_stmt (rsi);
    gsi_remove (&rsi, true);
    release_defs (to_release);

    return stmt1;
  }

return stmt;
1064}

1066/* Determine the outermost loops in that statements in basic block BB are
 invariant, and record them to the LIM_DATA associated with the
 statements.  */

1070static void
1071compute_invariantness (basic_block bb)
1072{
enum move_pos pos;
gimple_stmt_iterator bsi;
gimple *stmt;
bool maybe_never = ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux) == NULLnullptr;
class loop *outermost = ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux);
struct lim_aux_data *lim_data;

if (!loop_outer (bb->loop_father))
  return;

if (dump_file && (dump_flags & TDF_DETAILS))
  fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
    bb->index, bb->loop_father->num, loop_depth (bb->loop_father));

/* Look at PHI nodes, but only if there is at most two.
   ???  We could relax this further by post-processing the inserted
   code and transforming adjacent cond-exprs with the same predicate
   to control flow again.  */
bsi = gsi_start_phis (bb);
if (!gsi_end_p (bsi)
    && ((gsi_next (&bsi), gsi_end_p (bsi))
 || (gsi_next (&bsi), gsi_end_p (bsi))))
  for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
    {
stmt = gsi_stmt (bsi);

pos = movement_possibility (stmt);
if (pos == MOVE_IMPOSSIBLE)
 continue;

lim_data = get_lim_data (stmt);
if (! lim_data)
 lim_data = init_lim_data (stmt);
lim_data->always_executed_in = outermost;

if (!determine_max_movement (stmt, false))
 {
   lim_data->max_loop = NULLnullptr;
   continue;
 }

if (dump_file && (dump_flags & TDF_DETAILS))
 {
   print_gimple_stmt (dump_file, stmt, 2);
   fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
     loop_depth (lim_data->max_loop),
     lim_data->cost);
 }

if (lim_data->cost >= LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive))
 set_profitable_level (stmt);
    }

for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
  {
    stmt = gsi_stmt (bsi);

    pos = movement_possibility (stmt);
    if (pos == MOVE_IMPOSSIBLE)
{
 if (nonpure_call_p (stmt))
   {
     maybe_never = true;
     outermost = NULLnullptr;
   }
 /* Make sure to note always_executed_in for stores to make
    store-motion work.  */
 else if (stmt_makes_single_store (stmt))
   {
     struct lim_aux_data *lim_data = get_lim_data (stmt);
     if (! lim_data)
lim_data = init_lim_data (stmt);
     lim_data->always_executed_in = outermost;
   }
 continue;
}

    if (is_gimple_assign (stmt)
 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
     == GIMPLE_BINARY_RHS))
{
 tree op0 = gimple_assign_rhs1 (stmt);
 tree op1 = gimple_assign_rhs2 (stmt);
 class loop *ol1 = outermost_invariant_loop (op1,
			loop_containing_stmt (stmt));

 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
    to be hoisted out of loop, saving expensive divide.  */
 if (pos == MOVE_POSSIBLE
     && gimple_assign_rhs_code (stmt) == RDIV_EXPR
     && flag_unsafe_math_optimizationsglobal_options.x_flag_unsafe_math_optimizations
     && !flag_trapping_mathglobal_options.x_flag_trapping_math
     && ol1 != NULLnullptr
     && outermost_invariant_loop (op0, ol1) == NULLnullptr)
   stmt = rewrite_reciprocal (&bsi);

 /* If the shift count is invariant, convert (A >> B) & 1 to
    A & (1 << B) allowing the bit mask to be hoisted out of the loop
    saving an expensive shift.  */
 if (pos == MOVE_POSSIBLE
     && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
     && integer_onep (op1)
     && TREE_CODE (op0)((enum tree_code) (op0)->base.code) == SSA_NAME
     && has_single_use (op0))
   stmt = rewrite_bittest (&bsi);
}

    lim_data = get_lim_data (stmt);
    if (! lim_data)
lim_data = init_lim_data (stmt);
    lim_data->always_executed_in = outermost;

    if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
continue;

    if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
{
 lim_data->max_loop = NULLnullptr;
 continue;
}

    if (dump_file && (dump_flags & TDF_DETAILS))
{
 print_gimple_stmt (dump_file, stmt, 2);
 fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
   loop_depth (lim_data->max_loop),
   lim_data->cost);
}

    if (lim_data->cost >= LIM_EXPENSIVE((unsigned) global_options.x_param_lim_expensive))
set_profitable_level (stmt);
  }
1205}

1207/* Hoist the statements in basic block BB out of the loops prescribed by
 data stored in LIM_DATA structures associated with each statement.  Callback
 for walk_dominator_tree.  */

1211unsigned int
1212move_computations_worker (basic_block bb)
1213{
class loop *level;
unsigned cost = 0;
struct lim_aux_data *lim_data;
unsigned int todo = 0;

if (!loop_outer (bb->loop_father))
  return todo;

for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
  {
    gassign *new_stmt;
    gphi *stmt = bsi.phi ();

    lim_data = get_lim_data (stmt);
    if (lim_data == NULLnullptr)
{
 gsi_next (&bsi);
 continue;
}

    cost = lim_data->cost;
    level = lim_data->tgt_loop;
    clear_lim_data (stmt);

    if (!level)
{
 gsi_next (&bsi);
 continue;
}

    if (dump_file && (dump_flags & TDF_DETAILS))
{
 fprintf (dump_file, "Moving PHI node\n");
 print_gimple_stmt (dump_file, stmt, 0);
 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
   cost, level->num);
}

    if (gimple_phi_num_args (stmt) == 1)
{
 tree arg = PHI_ARG_DEF (stmt, 0)gimple_phi_arg_def ((stmt), (0));
 new_stmt = gimple_build_assign (gimple_phi_result (stmt),
			  TREE_CODE (arg)((enum tree_code) (arg)->base.code), arg);
}
    else
{
 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
 gimple *cond = gsi_stmt (gsi_last_bb (dom));
 tree arg0 = NULL_TREE(tree) nullptr, arg1 = NULL_TREE(tree) nullptr, t;
 /* Get the PHI arguments corresponding to the true and false
    edges of COND.  */
 extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
 gcc_assert (arg0 && arg1)((void)(!(arg0 && arg1) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1266, __FUNCTION__), 0 : 0));
 t = make_ssa_name (boolean_type_nodeglobal_trees[TI_BOOLEAN_TYPE]);
 new_stmt = gimple_build_assign (t, gimple_cond_code (cond),
			  gimple_cond_lhs (cond),
			  gimple_cond_rhs (cond));
 gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
 new_stmt = gimple_build_assign (gimple_phi_result (stmt),
			  COND_EXPR, t, arg0, arg1);
 todo |= TODO_cleanup_cfg(1 << 5);
}
    if (!ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux)
 || (ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux) != level
     && !flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux), level)))
reset_flow_sensitive_info (gimple_assign_lhs (new_stmt));
    gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
    remove_phi_node (&bsi, false);
  }

for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
  {
    edge e;

    gimple *stmt = gsi_stmt (bsi);

    lim_data = get_lim_data (stmt);
    if (lim_data == NULLnullptr)
{
 gsi_next (&bsi);
 continue;
}

    cost = lim_data->cost;
    level = lim_data->tgt_loop;
    clear_lim_data (stmt);

    if (!level)
{
 gsi_next (&bsi);
 continue;
}

    /* We do not really want to move conditionals out of the loop; we just
placed it here to force its operands to be moved if necessary.  */
    if (gimple_code (stmt) == GIMPLE_COND)
{
 gsi_next (&bsi);
 continue;
}

    if (dump_file && (dump_flags & TDF_DETAILS))
{
 fprintf (dump_file, "Moving statement\n");
 print_gimple_stmt (dump_file, stmt, 0);
 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
   cost, level->num);
}

    e = loop_preheader_edge (level);
    gcc_assert (!gimple_vdef (stmt))((void)(!(!gimple_vdef (stmt)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1324, __FUNCTION__), 0 : 0));
    if (gimple_vuse (stmt))
{
 /* The new VUSE is the one from the virtual PHI in the loop
    header or the one already present.  */
 gphi_iterator gsi2;
 for (gsi2 = gsi_start_phis (e->dest);
      !gsi_end_p (gsi2); gsi_next (&gsi2))
   {
     gphi *phi = gsi2.phi ();
     if (virtual_operand_p (gimple_phi_result (phi)))
{
  SET_USE (gimple_vuse_op (stmt),set_ssa_use_from_ptr (gimple_vuse_op (stmt), gimple_phi_arg_def
 (((phi)), ((e)->dest_idx)))
	   PHI_ARG_DEF_FROM_EDGE (phi, e))set_ssa_use_from_ptr (gimple_vuse_op (stmt), gimple_phi_arg_def
 (((phi)), ((e)->dest_idx)));
  break;
}
   }
}
    gsi_remove (&bsi, false);
    if (gimple_has_lhs (stmt)
 && TREE_CODE (gimple_get_lhs (stmt))((enum tree_code) (gimple_get_lhs (stmt))->base.code) == SSA_NAME
 && (!ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux)
     || !(ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux) == level
   || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux), level))))
reset_flow_sensitive_info (gimple_get_lhs (stmt));
    /* In case this is a stmt that is not unconditionally executed
       when the target loop header is executed and the stmt may
invoke undefined integer or pointer overflow rewrite it to
unsigned arithmetic.  */
    if (is_gimple_assign (stmt)
 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))(((enum tree_code) (((contains_struct_check ((gimple_assign_lhs
 (stmt)), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1354, __FUNCTION__))->typed.type))->base.code) == ENUMERAL_TYPE
 || ((enum tree_code) (((contains_struct_check ((gimple_assign_lhs
 (stmt)), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1354, __FUNCTION__))->typed.type))->base.code) == BOOLEAN_TYPE
 || ((enum tree_code) (((contains_struct_check ((gimple_assign_lhs
 (stmt)), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1354, __FUNCTION__))->typed.type))->base.code) == INTEGER_TYPE
)
 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt)))((((enum tree_code) (((contains_struct_check ((gimple_assign_lhs
 (stmt)), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1355, __FUNCTION__))->typed.type))->base.code) == POINTER_TYPE
 || ((enum tree_code) (((contains_struct_check ((gimple_assign_lhs
 (stmt)), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1355, __FUNCTION__))->typed.type))->base.code) == REFERENCE_TYPE
) ? !global_options.x_flag_wrapv_pointer : (!(any_integral_type_check
 ((((contains_struct_check ((gimple_assign_lhs (stmt)), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1355, __FUNCTION__))->typed.type)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1355, __FUNCTION__))->base.u.bits.unsigned_flag &&
 !global_options.x_flag_wrapv && !global_options.x_flag_trapv
))
 && arith_code_with_undefined_signed_overflow
      (gimple_assign_rhs_code (stmt))
 && (!ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux)
     || !(ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux) == level
   || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb)((class loop *) (bb)->aux), level))))
gsi_insert_seq_on_edge (e, rewrite_to_defined_overflow (stmt));
    else
gsi_insert_on_edge (e, stmt);
  }

return todo;
1367}

1369/* Checks whether the statement defining variable *INDEX can be hoisted
 out of the loop passed in DATA.  Callback for for_each_index.  */

1372static bool
1373may_move_till (tree ref, tree *index, void *data)
1374{
class loop *loop = (class loop *) data, *max_loop;

/* If REF is an array reference, check also that the step and the lower
   bound is invariant in LOOP.  */
if (TREE_CODE (ref)((enum tree_code) (ref)->base.code) == ARRAY_REF)
  {
    tree step = TREE_OPERAND (ref, 3)(*((const_cast<tree*> (tree_operand_check ((ref), (3), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1381, __FUNCTION__)))));
    tree lbound = TREE_OPERAND (ref, 2)(*((const_cast<tree*> (tree_operand_check ((ref), (2), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1382, __FUNCTION__)))));

    max_loop = outermost_invariant_loop (step, loop);
    if (!max_loop)
return false;

    max_loop = outermost_invariant_loop (lbound, loop);
    if (!max_loop)
return false;
  }

max_loop = outermost_invariant_loop (*index, loop);
if (!max_loop)
  return false;

return true;
1398}

1400/* If OP is SSA NAME, force the statement that defines it to be
 moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */

1403static void
1404force_move_till_op (tree op, class loop *orig_loop, class loop *loop)
1405{
gimple *stmt;

if (!op
    || is_gimple_min_invariant (op))
  return;

gcc_assert (TREE_CODE (op) == SSA_NAME)((void)(!(((enum tree_code) (op)->base.code) == SSA_NAME) ?
 fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1412, __FUNCTION__), 0 : 0));

stmt = SSA_NAME_DEF_STMT (op)(tree_check ((op), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1414, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
if (gimple_nop_p (stmt))
  return;

set_level (stmt, orig_loop, loop);
1419}

1421/* Forces statement defining invariants in REF (and *INDEX) to be moved out of
 the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
 for_each_index.  */

1425struct fmt_data
1426{
class loop *loop;
class loop *orig_loop;
1429};

1431static bool
1432force_move_till (tree ref, tree *index, void *data)
1433{
struct fmt_data *fmt_data = (struct fmt_data *) data;

if (TREE_CODE (ref)((enum tree_code) (ref)->base.code) == ARRAY_REF)
  {
    tree step = TREE_OPERAND (ref, 3)(*((const_cast<tree*> (tree_operand_check ((ref), (3), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1438, __FUNCTION__)))));
    tree lbound = TREE_OPERAND (ref, 2)(*((const_cast<tree*> (tree_operand_check ((ref), (2), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1439, __FUNCTION__)))));

    force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
    force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
  }

force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);

return true;
1448}

1450/* A function to free the mem_ref object OBJ.  */

1452static void
1453memref_free (class im_mem_ref *mem)
1454{
mem->accesses_in_loop.release ();
1456}

1458/* Allocates and returns a memory reference description for MEM whose hash
 value is HASH and id is ID.  */

1461static im_mem_ref *
1462mem_ref_alloc (ao_ref *mem, unsigned hash, unsigned id)
1463{
im_mem_ref *ref = XOBNEW (&mem_ref_obstack, class im_mem_ref)((class im_mem_ref *) __extension__ ({ struct obstack *__h = (
(&mem_ref_obstack)); __extension__ ({ struct obstack *__o
 = (__h); size_t __len = ((sizeof (class im_mem_ref))); 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; }); }));
if (mem)
  ref->mem = *mem;
else
  ao_ref_init (&ref->mem, error_mark_nodeglobal_trees[TI_ERROR_MARK]);
ref->id = id;
ref->ref_canonical = false;
ref->ref_decomposed = false;
ref->hash = hash;
ref->stored = NULLnullptr;
ref->loaded = NULLnullptr;
bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack);
ref->accesses_in_loop.create (1);

return ref;
1479}

1481/* Records memory reference location *LOC in LOOP to the memory reference
 description REF.  The reference occurs in statement STMT.  */

1484static void
1485record_mem_ref_loc (im_mem_ref *ref, gimple *stmt, tree *loc)
1486{
mem_ref_loc aref;
aref.stmt = stmt;
aref.ref = loc;
ref->accesses_in_loop.safe_push (aref);
1491}

1493/* Set the LOOP bit in REF stored bitmap and allocate that if
 necessary.  Return whether a bit was changed.  */

1496static bool
1497set_ref_stored_in_loop (im_mem_ref *ref, class loop *loop)
1498{
if (!ref->stored)
  ref->stored = BITMAP_ALLOCbitmap_alloc (&lim_bitmap_obstack);
return bitmap_set_bit (ref->stored, loop->num);
1502}

1504/* Marks reference REF as stored in LOOP.  */

1506static void
1507mark_ref_stored (im_mem_ref *ref, class loop *loop)
1508{
while (loop != current_loops((cfun + 0)->x_current_loops)->tree_root
&& set_ref_stored_in_loop (ref, loop))
  loop = loop_outer (loop);
1512}

1514/* Set the LOOP bit in REF loaded bitmap and allocate that if
 necessary.  Return whether a bit was changed.  */

1517static bool
1518set_ref_loaded_in_loop (im_mem_ref *ref, class loop *loop)
1519{
if (!ref->loaded)
  ref->loaded = BITMAP_ALLOCbitmap_alloc (&lim_bitmap_obstack);
return bitmap_set_bit (ref->loaded, loop->num);
1523}

1525/* Marks reference REF as loaded in LOOP.  */

1527static void
1528mark_ref_loaded (im_mem_ref *ref, class loop *loop)
1529{
while (loop != current_loops((cfun + 0)->x_current_loops)->tree_root
&& set_ref_loaded_in_loop (ref, loop))
  loop = loop_outer (loop);
1533}

1535/* Gathers memory references in statement STMT in LOOP, storing the
 information about them in the memory_accesses structure.  Marks
 the vops accessed through unrecognized statements there as
 well.  */

1540static void
1541gather_mem_refs_stmt (class loop *loop, gimple *stmt)
1542{
tree *mem = NULLnullptr;
hashval_t hash;
im_mem_ref **slot;
im_mem_ref *ref;
bool is_stored;
unsigned id;

if (!gimple_vuse (stmt))
16
←
Assuming the condition is false→
17
←
Taking false branch→
  return;

mem = simple_mem_ref_in_stmt (stmt, &is_stored);
18
←
Calling 'simple_mem_ref_in_stmt'→
26
←
Returning from 'simple_mem_ref_in_stmt'→
if (!mem26.1
'mem' is non-null
 && is_gimple_assign (stmt))
  {
    /* For aggregate copies record distinct references but use them
only for disambiguation purposes.  */
    id = memory_accesses.refs_list.length ();
    ref = mem_ref_alloc (NULLnullptr, 0, id);
    memory_accesses.refs_list.safe_push (ref);
    if (dump_file && (dump_flags & TDF_DETAILS))
{
 fprintf (dump_file, "Unhandled memory reference %u: ", id);
 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
    record_mem_ref_loc (ref, stmt, mem);
    is_stored = gimple_vdef (stmt);
  }
else if (!mem26.2
'mem' is non-null
)
27
←
Taking false branch→
  {
    /* We use the shared mem_ref for all unanalyzable refs.  */
    id = UNANALYZABLE_MEM_ID0;
    ref = memory_accesses.refs_list[id];
    if (dump_file && (dump_flags & TDF_DETAILS))
{
 fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
    is_stored = gimple_vdef (stmt);
  }
else
  {
    /* We are looking for equal refs that might differ in structure
       such as a.b vs. MEM[&a + 4].  So we key off the ao_ref but
make sure we can canonicalize the ref in the hashtable if
non-operand_equal_p refs are found.  For the lookup we mark
the case we want strict equality with aor.max_size == -1.  */
    ao_ref aor;
    ao_ref_init (&aor, *mem);
    ao_ref_base (&aor);
    ao_ref_alias_set (&aor);
    HOST_WIDE_INTlong offset, size, max_size;
    poly_int64 saved_maxsize = aor.max_size, mem_off;
    tree mem_base;
28
←
'mem_base' declared without an initial value→
    bool ref_decomposed;
    if (aor.max_size_known_p ()
29
←
Taking false branch→
 && aor.offset.is_constant (&offset)
 && aor.size.is_constant (&size)
 && aor.max_size.is_constant (&max_size)
 && size == max_size
 && (size % BITS_PER_UNIT(8)) == 0
 /* We're canonicalizing to a MEM where TYPE_SIZE specifies the
    size.  Make sure this is consistent with the extraction.  */
 && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (*mem))((tree_class_check ((((contains_struct_check ((*mem), (TS_TYPED
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1604, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1604, __FUNCTION__))->type_common.size))
 && known_eq (wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (*mem))),(!maybe_ne (wi::to_poly_offset (((tree_class_check ((((contains_struct_check
 ((*mem), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1605, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1605, __FUNCTION__))->type_common.size)), aor.size))
       aor.size)(!maybe_ne (wi::to_poly_offset (((tree_class_check ((((contains_struct_check
 ((*mem), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1605, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1605, __FUNCTION__))->type_common.size)), aor.size))
 && (mem_base = get_addr_base_and_unit_offset (aor.ref, &mem_off)))
{
 ref_decomposed = true;
 tree base = ao_ref_base (&aor);
 poly_int64 moffset;
 HOST_WIDE_INTlong mcoffset;
 if (TREE_CODE (base)((enum tree_code) (base)->base.code) == MEM_REF
     && (mem_ref_offset (base) * BITS_PER_UNIT(8) + offset).to_shwi (&moffset)
     && moffset.is_constant (&mcoffset))
   {
     hash = iterative_hash_expr (TREE_OPERAND (base, 0)(*((const_cast<tree*> (tree_operand_check ((base), (0),
 "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1617, __FUNCTION__))))), 0);
     hash = iterative_hash_host_wide_int (mcoffset, hash);
   }
 else
   {
     hash = iterative_hash_expr (base, 0);
     hash = iterative_hash_host_wide_int (offset, hash);
   }
 hash = iterative_hash_host_wide_int (size, hash);
}
    else
{
 ref_decomposed = false;
 hash = iterative_hash_expr (aor.ref, 0);
 aor.max_size = -1;
}
    slot = memory_accesses.refs->find_slot_with_hash (&aor, hash, INSERT);
    aor.max_size = saved_maxsize;
    if (*slot)
30
←
Assuming the condition is true→
{
 if (!(*slot)->ref_canonical 
31
←
Assuming field 'ref_canonical' is 0→
     && !operand_equal_p (*mem, (*slot)->mem.ref, 0))
32
←
Assuming the condition is true→
   {
     /* If we didn't yet canonicalize the hashtable ref (which
        we'll end up using for code insertion) and hit a second
 equal ref that is not structurally equivalent create
 a canonical ref which is a bare MEM_REF.  */
     if (TREE_CODE (*mem)((enum tree_code) (*mem)->base.code) == MEM_REF
33
←
Taking true branch→
34
←
Assuming field 'code' is not equal to MEM_REF→
36
←
Taking false branch→
  || TREE_CODE (*mem)((enum tree_code) (*mem)->base.code) == TARGET_MEM_REF)
35
←
Assuming field 'code' is not equal to TARGET_MEM_REF→
{
  (*slot)->mem.ref = *mem;
  (*slot)->mem.base_alias_set = ao_ref_base_alias_set (&aor);
}
     else
{
  tree ref_alias_type = reference_alias_ptr_type (*mem);
  unsigned int ref_align = get_object_alignment (*mem);
  tree ref_type = TREE_TYPE (*mem)((contains_struct_check ((*mem), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1654, __FUNCTION__))->typed.type);
  tree tmp = build1 (ADDR_EXPR, ptr_type_nodeglobal_trees[TI_PTR_TYPE],
		     unshare_expr (mem_base));
37
←
1st function call argument is an uninitialized value
  if (TYPE_ALIGN (ref_type)(((tree_class_check ((ref_type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1657, __FUNCTION__))->type_common.align) ? ((unsigned)1)
 << (((tree_class_check ((ref_type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1657, __FUNCTION__))->type_common.align) - 1) : 0) != ref_align)
    ref_type = build_aligned_type (ref_type, ref_align);
  (*slot)->mem.ref
    = fold_build2 (MEM_REF, ref_type, tmp,fold_build2_loc (((location_t) 0), MEM_REF, ref_type, tmp, build_int_cst
 (ref_alias_type, mem_off) )
		   build_int_cst (ref_alias_type, mem_off))fold_build2_loc (((location_t) 0), MEM_REF, ref_type, tmp, build_int_cst
 (ref_alias_type, mem_off) );
  if ((*slot)->mem.volatile_p)
    TREE_THIS_VOLATILE ((*slot)->mem.ref)(((*slot)->mem.ref)->base.volatile_flag) = 1;
  gcc_checking_assert (TREE_CODE ((*slot)->mem.ref) == MEM_REF((void)(!(((enum tree_code) ((*slot)->mem.ref)->base.code
) == MEM_REF && is_gimple_mem_ref_addr ((*((const_cast
<tree*> (tree_operand_check (((*slot)->mem.ref), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1667, __FUNCTION__))))))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1667, __FUNCTION__), 0 : 0))
		       && is_gimple_mem_ref_addr((void)(!(((enum tree_code) ((*slot)->mem.ref)->base.code
) == MEM_REF && is_gimple_mem_ref_addr ((*((const_cast
<tree*> (tree_operand_check (((*slot)->mem.ref), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1667, __FUNCTION__))))))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1667, __FUNCTION__), 0 : 0))
		            (TREE_OPERAND ((*slot)->mem.ref,((void)(!(((enum tree_code) ((*slot)->mem.ref)->base.code
) == MEM_REF && is_gimple_mem_ref_addr ((*((const_cast
<tree*> (tree_operand_check (((*slot)->mem.ref), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1667, __FUNCTION__))))))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1667, __FUNCTION__), 0 : 0))
					   0)))((void)(!(((enum tree_code) ((*slot)->mem.ref)->base.code
) == MEM_REF && is_gimple_mem_ref_addr ((*((const_cast
<tree*> (tree_operand_check (((*slot)->mem.ref), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1667, __FUNCTION__))))))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1667, __FUNCTION__), 0 : 0));
  (*slot)->mem.base_alias_set = (*slot)->mem.ref_alias_set;
}
     (*slot)->ref_canonical = true;
   }
 ref = *slot;
 id = ref->id;
}
    else
{
 id = memory_accesses.refs_list.length ();
 ref = mem_ref_alloc (&aor, hash, id);
 ref->ref_decomposed = ref_decomposed;
 memory_accesses.refs_list.safe_push (ref);
 *slot = ref;

 if (dump_file && (dump_flags & TDF_DETAILS))
   {
     fprintf (dump_file, "Memory reference %u: ", id);
     print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
     fprintf (dump_file, "\n");
   }
}

    record_mem_ref_loc (ref, stmt, mem);
  }
if (is_stored)
  {
    bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
    mark_ref_stored (ref, loop);
  }
/* A not simple memory op is also a read when it is a write.  */
if (!is_stored || id == UNANALYZABLE_MEM_ID0
    || ref->mem.ref == error_mark_nodeglobal_trees[TI_ERROR_MARK])
  {
    bitmap_set_bit (&memory_accesses.refs_loaded_in_loop[loop->num], ref->id);
    mark_ref_loaded (ref, loop);
  }
init_lim_data (stmt)->ref = ref->id;
return;
1707}

1709static unsigned *bb_loop_postorder;

1711/* qsort sort function to sort blocks after their loop fathers postorder.  */

1713static int
1714sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_,
		void *bb_loop_postorder_)
1716{
unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
basic_block bb1 = *(const basic_block *)bb1_;
basic_block bb2 = *(const basic_block *)bb2_;
class loop *loop1 = bb1->loop_father;
class loop *loop2 = bb2->loop_father;
if (loop1->num == loop2->num)
  return bb1->index - bb2->index;
return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1725}

1727/* qsort sort function to sort ref locs after their loop fathers postorder.  */

1729static int
1730sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_,
		 void *bb_loop_postorder_)
1732{
unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
const mem_ref_loc *loc1 = (const mem_ref_loc *)loc1_;
const mem_ref_loc *loc2 = (const mem_ref_loc *)loc2_;
class loop *loop1 = gimple_bb (loc1->stmt)->loop_father;
class loop *loop2 = gimple_bb (loc2->stmt)->loop_father;
if (loop1->num == loop2->num)
  return 0;
return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1741}

1743/* Gathers memory references in loops.  */

1745static void
1746analyze_memory_references (bool store_motion)
1747{
gimple_stmt_iterator bsi;
basic_block bb, *bbs;
class loop *outer;
unsigned i, n;

/* Collect all basic-blocks in loops and sort them after their
   loops postorder.  */
i = 0;
bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)((basic_block *) xmalloc (sizeof (basic_block) * ((((cfun + 0
))->cfg->x_n_basic_blocks) - (2))));
FOR_EACH_BB_FN (bb, cfun)for (bb = ((cfun + 0))->cfg->x_entry_block_ptr->next_bb
; bb != ((cfun + 0))->cfg->x_exit_block_ptr; bb = bb->
next_bb)
7
←
Assuming 'bb' is not equal to field 'x_exit_block_ptr'→
8
←
Loop condition is true.  Entering loop body→
11
←
Assuming 'bb' is equal to field 'x_exit_block_ptr'→
12
←
Loop condition is false. Execution continues on line 1760→
  if (bb->loop_father != current_loops((cfun + 0)->x_current_loops)->tree_root)
9
←
Assuming field 'loop_father' is not equal to field 'tree_root'→
10
←
Taking true branch→
    bbs[i++] = bb;
n = i;
gcc_sort_r (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp,
     bb_loop_postorder);

/* Visit blocks in loop postorder and assign mem-ref IDs in that order.
   That results in better locality for all the bitmaps.  It also
   automatically sorts the location list of gathered memory references
   after their loop postorder number allowing to binary-search it.  */
for (i = 0; i < n; ++i)
13
←
Loop condition is true.  Entering loop body→
  {
    basic_block bb = bbs[i];
    for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
14
←
Loop condition is true.  Entering loop body→
      gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
15
←
Calling 'gather_mem_refs_stmt'→
  }

/* Verify the list of gathered memory references is sorted after their
   loop postorder number.  */
if (flag_checkingglobal_options.x_flag_checking)
  {
    im_mem_ref *ref;
    FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)for (i = 0; (memory_accesses.refs_list).iterate ((i), &(ref
)); ++(i))
for (unsigned j = 1; j < ref->accesses_in_loop.length (); ++j)
 gcc_assert (sort_locs_in_loop_postorder_cmp((void)(!(sort_locs_in_loop_postorder_cmp (&ref->accesses_in_loop
[j-1], &ref->accesses_in_loop[j], bb_loop_postorder) <=
 0) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1784, __FUNCTION__), 0 : 0))
	(&ref->accesses_in_loop[j-1], &ref->accesses_in_loop[j],((void)(!(sort_locs_in_loop_postorder_cmp (&ref->accesses_in_loop
[j-1], &ref->accesses_in_loop[j], bb_loop_postorder) <=
 0) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1784, __FUNCTION__), 0 : 0))
	 bb_loop_postorder) <= 0)((void)(!(sort_locs_in_loop_postorder_cmp (&ref->accesses_in_loop
[j-1], &ref->accesses_in_loop[j], bb_loop_postorder) <=
 0) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1784, __FUNCTION__), 0 : 0));
  }

free (bbs);

if (!store_motion)
  return;

/* Propagate the information about accessed memory references up
   the loop hierarchy.  */
for (auto loop : loops_list (cfun(cfun + 0), LI_FROM_INNERMOST))
  {
    /* Finalize the overall touched references (including subloops).  */
    bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num],
       &memory_accesses.refs_stored_in_loop[loop->num]);

    /* Propagate the information about accessed memory references up
the loop hierarchy.  */
    outer = loop_outer (loop);
    if (outer == current_loops((cfun + 0)->x_current_loops)->tree_root)
continue;

    bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
       &memory_accesses.all_refs_stored_in_loop[loop->num]);
  }
1809}

1811/* Returns true if MEM1 and MEM2 may alias.  TTAE_CACHE is used as a cache in
 tree_to_aff_combination_expand.  */

1814static bool
1815mem_refs_may_alias_p (im_mem_ref *mem1, im_mem_ref *mem2,
      hash_map<tree, name_expansion *> **ttae_cache,
      bool tbaa_p)
1818{
gcc_checking_assert (mem1->mem.ref != error_mark_node((void)(!(mem1->mem.ref != global_trees[TI_ERROR_MARK] &&
 mem2->mem.ref != global_trees[TI_ERROR_MARK]) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1820, __FUNCTION__), 0 : 0))
       && mem2->mem.ref != error_mark_node)((void)(!(mem1->mem.ref != global_trees[TI_ERROR_MARK] &&
 mem2->mem.ref != global_trees[TI_ERROR_MARK]) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 1820, __FUNCTION__), 0 : 0));

/* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
   object and their offset differ in such a way that the locations cannot
   overlap, then they cannot alias.  */
poly_widest_int size1, size2;
aff_tree off1, off2;

/* Perform basic offset and type-based disambiguation.  */
if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, tbaa_p))
  return false;

/* The expansion of addresses may be a bit expensive, thus we only do
   the check at -O2 and higher optimization levels.  */
if (optimizeglobal_options.x_optimize < 2)
  return true;

get_inner_reference_aff (mem1->mem.ref, &off1, &size1);
get_inner_reference_aff (mem2->mem.ref, &off2, &size2);
aff_combination_expand (&off1, ttae_cache);
aff_combination_expand (&off2, ttae_cache);
aff_combination_scale (&off1, -1);
aff_combination_add (&off2, &off1);

if (aff_comb_cannot_overlap_p (&off2, size1, size2))
  return false;

return true;
1848}

1850/* Compare function for bsearch searching for reference locations
 in a loop.  */

1853static int
1854find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_,
	  void *bb_loop_postorder_)
1856{
unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
class loop *loop = (class loop *)const_cast<void *>(loop_);
mem_ref_loc *loc = (mem_ref_loc *)const_cast<void *>(loc_);
class loop *loc_loop = gimple_bb (loc->stmt)->loop_father;
if (loop->num  == loc_loop->num
    || flow_loop_nested_p (loop, loc_loop))
  return 0;
return (bb_loop_postorder[loop->num] < bb_loop_postorder[loc_loop->num]
 ? -1 : 1);
1866}

1868/* Iterates over all locations of REF in LOOP and its subloops calling
 fn.operator() with the location as argument.  When that operator
 returns true the iteration is stopped and true is returned.
 Otherwise false is returned.  */

1873template <typename FN>
1874static bool
1875for_all_locs_in_loop (class loop *loop, im_mem_ref *ref, FN fn)
1876{
unsigned i;
mem_ref_loc *loc;

/* Search for the cluster of locs in the accesses_in_loop vector
   which is sorted after postorder index of the loop father.  */
loc = ref->accesses_in_loop.bsearch (loop, find_ref_loc_in_loop_cmp,
		       bb_loop_postorder);
if (!loc)
  return false;

/* We have found one location inside loop or its sub-loops.  Iterate
   both forward and backward to cover the whole cluster.  */
i = loc - ref->accesses_in_loop.address ();
while (i > 0)
  {
    --i;
    mem_ref_loc *l = &ref->accesses_in_loop[i];
    if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
break;
    if (fn (l))
return true;
  }
for (i = loc - ref->accesses_in_loop.address ();
     i < ref->accesses_in_loop.length (); ++i)
  {
    mem_ref_loc *l = &ref->accesses_in_loop[i];
    if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
break;
    if (fn (l))
return true;
  }

return false;
1910}

1912/* Rewrites location LOC by TMP_VAR.  */

1914class rewrite_mem_ref_loc
1915{
1916public:
rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
bool operator () (mem_ref_loc *loc);
tree tmp_var;
1920};

1922bool
1923rewrite_mem_ref_loc::operator () (mem_ref_loc *loc)
1924{
*loc->ref = tmp_var;
update_stmt (loc->stmt);
return false;
1928}

1930/* Rewrites all references to REF in LOOP by variable TMP_VAR.  */

1932static void
1933rewrite_mem_refs (class loop *loop, im_mem_ref *ref, tree tmp_var)
1934{
for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
1936}

1938/* Stores the first reference location in LOCP.  */

1940class first_mem_ref_loc_1
1941{
1942public:
first_mem_ref_loc_1 (mem_ref_loc **locp_) : locp (locp_) {}
bool operator () (mem_ref_loc *loc);
mem_ref_loc **locp;
1946};

1948bool
1949first_mem_ref_loc_1::operator () (mem_ref_loc *loc)
1950{
*locp = loc;
return true;
1953}

1955/* Returns the first reference location to REF in LOOP.  */

1957static mem_ref_loc *
1958first_mem_ref_loc (class loop *loop, im_mem_ref *ref)
1959{
mem_ref_loc *locp = NULLnullptr;
for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
return locp;
1963}

1965/* Helper function for execute_sm.  Emit code to store TMP_VAR into
 MEM along edge EX.

 The store is only done if MEM has changed.  We do this so no
 changes to MEM occur on code paths that did not originally store
 into it.

 The common case for execute_sm will transform:

   for (...) {
     if (foo)
       stuff;
     else
       MEM = TMP_VAR;
   }

 into:

   lsm = MEM;
   for (...) {
     if (foo)
       stuff;
     else
       lsm = TMP_VAR;
   }
   MEM = lsm;

This function will generate:

   lsm = MEM;

   lsm_flag = false;
   ...
   for (...) {
     if (foo)
       stuff;
     else {
       lsm = TMP_VAR;
       lsm_flag = true;
     }
   }
   if (lsm_flag)	<--
     MEM = lsm;	<-- (X)

In case MEM and TMP_VAR are NULL the function will return the then
block so the caller can insert (X) and other related stmts. 
2011*/

2013static basic_block
2014execute_sm_if_changed (edge ex, tree mem, tree tmp_var, tree flag,
       edge preheader, hash_set <basic_block> *flag_bbs,
       edge &append_cond_position, edge &last_cond_fallthru)
2017{
basic_block new_bb, then_bb, old_dest;
bool loop_has_only_one_exit;
edge then_old_edge;
gimple_stmt_iterator gsi;
gimple *stmt;
bool irr = ex->flags & EDGE_IRREDUCIBLE_LOOP;

profile_count count_sum = profile_count::zero ();
int nbbs = 0, ncount = 0;
profile_probability flag_probability = profile_probability::uninitialized ();

/* Flag is set in FLAG_BBS. Determine probability that flag will be true
   at loop exit.

   This code may look fancy, but it cannot update profile very realistically
   because we do not know the probability that flag will be true at given
   loop exit.

   We look for two interesting extremes
     - when exit is dominated by block setting the flag, we know it will
       always be true.  This is a common case.
     - when all blocks setting the flag have very low frequency we know
       it will likely be false.
   In all other cases we default to 2/3 for flag being true.  */

for (hash_set<basic_block>::iterator it = flag_bbs->begin ();
     it != flag_bbs->end (); ++it)
  {
     if ((*it)->count.initialized_p ())
       count_sum += (*it)->count, ncount ++;
     if (dominated_by_p (CDI_DOMINATORS, ex->src, *it))
flag_probability = profile_probability::always ();
     nbbs++;
  }

profile_probability cap = profile_probability::always ().apply_scale (2, 3);

if (flag_probability.initialized_p ())
  ;
else if (ncount == nbbs
  && preheader->count () >= count_sum && preheader->count ().nonzero_p ())
  {
    flag_probability = count_sum.probability_in (preheader->count ());
    if (flag_probability > cap)
flag_probability = cap;
  }

if (!flag_probability.initialized_p ())
  flag_probability = cap;

/* ?? Insert store after previous store if applicable.  See note
   below.  */
if (append_cond_position)
  ex = append_cond_position;

loop_has_only_one_exit = single_pred_p (ex->dest);

if (loop_has_only_one_exit)
  ex = split_block_after_labels (ex->dest);
else
  {
    for (gphi_iterator gpi = gsi_start_phis (ex->dest);
  !gsi_end_p (gpi); gsi_next (&gpi))
{
 gphi *phi = gpi.phi ();
 if (virtual_operand_p (gimple_phi_result (phi)))
   continue;

 /* When the destination has a non-virtual PHI node with multiple
    predecessors make sure we preserve the PHI structure by
    forcing a forwarder block so that hoisting of that PHI will
    still work.  */
 split_edge (ex);
 break;
}
  }

old_dest = ex->dest;
new_bb = split_edge (ex);
then_bb = create_empty_bb (new_bb);
then_bb->count = new_bb->count.apply_probability (flag_probability);
if (irr)
  then_bb->flags = BB_IRREDUCIBLE_LOOP;
add_bb_to_loop (then_bb, new_bb->loop_father);

gsi = gsi_start_bb (new_bb);
stmt = gimple_build_cond (NE_EXPR, flag, boolean_false_nodeglobal_trees[TI_BOOLEAN_FALSE],
	    NULL_TREE(tree) nullptr, NULL_TREE(tree) nullptr);
gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);

/* Insert actual store.  */
if (mem)
  {
    gsi = gsi_start_bb (then_bb);
    stmt = gimple_build_assign (unshare_expr (mem), tmp_var);
    gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
  }

edge e1 = single_succ_edge (new_bb);
edge e2 = make_edge (new_bb, then_bb,
              EDGE_TRUE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
e2->probability = flag_probability;

e1->flags |= EDGE_FALSE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0);
e1->flags &= ~EDGE_FALLTHRU;

e1->probability = flag_probability.invert ();

then_old_edge = make_single_succ_edge (then_bb, old_dest,
	     EDGE_FALLTHRU | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));

set_immediate_dominator (CDI_DOMINATORS, then_bb, new_bb);

if (append_cond_position)
  {
    basic_block prevbb = last_cond_fallthru->src;
    redirect_edge_succ (last_cond_fallthru, new_bb);
    set_immediate_dominator (CDI_DOMINATORS, new_bb, prevbb);
    set_immediate_dominator (CDI_DOMINATORS, old_dest,
	       recompute_dominator (CDI_DOMINATORS, old_dest));
  }

/* ?? Because stores may alias, they must happen in the exact
   sequence they originally happened.  Save the position right after
   the (_lsm) store we just created so we can continue appending after
   it and maintain the original order.  */
append_cond_position = then_old_edge;
last_cond_fallthru = find_edge (new_bb, old_dest);

if (!loop_has_only_one_exit)
  for (gphi_iterator gpi = gsi_start_phis (old_dest);
!gsi_end_p (gpi); gsi_next (&gpi))
    {
gphi *phi = gpi.phi ();
unsigned i;

for (i = 0; i < gimple_phi_num_args (phi); i++)
 if (gimple_phi_arg_edge (phi, i)->src == new_bb)
   {
     tree arg = gimple_phi_arg_def (phi, i);
     add_phi_arg (phi, arg, then_old_edge, UNKNOWN_LOCATION((location_t) 0));
     update_stmt (phi);
   }
    }

return then_bb;
2164}

2166/* When REF is set on the location, set flag indicating the store.  */

2168class sm_set_flag_if_changed
2169{
2170public:
sm_set_flag_if_changed (tree flag_, hash_set <basic_block> *bbs_)
: flag (flag_), bbs (bbs_) {}
bool operator () (mem_ref_loc *loc);
tree flag;
hash_set <basic_block> *bbs;
2176};

2178bool
2179sm_set_flag_if_changed::operator () (mem_ref_loc *loc)
2180{
/* Only set the flag for writes.  */
if (is_gimple_assign (loc->stmt)
    && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
  {
    gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
    gimple *stmt = gimple_build_assign (flag, boolean_true_nodeglobal_trees[TI_BOOLEAN_TRUE]);
    gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
    bbs->add (gimple_bb (stmt));
  }
return false;
2191}

2193/* Helper function for execute_sm.  On every location where REF is
 set, set an appropriate flag indicating the store.  */

2196static tree
2197execute_sm_if_changed_flag_set (class loop *loop, im_mem_ref *ref,
		hash_set <basic_block> *bbs)
2199{
tree flag;
char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag");
flag = create_tmp_reg (boolean_type_nodeglobal_trees[TI_BOOLEAN_TYPE], str);
for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag, bbs));
return flag;
2205}

2207struct sm_aux
2208{
tree tmp_var;
tree store_flag;
hash_set <basic_block> flag_bbs;
2212};

2214/* Executes store motion of memory reference REF from LOOP.
 Exits from the LOOP are stored in EXITS.  The initialization of the
 temporary variable is put to the preheader of the loop, and assignments
 to the reference from the temporary variable are emitted to exits.  */

2219static void
2220execute_sm (class loop *loop, im_mem_ref *ref,
   hash_map<im_mem_ref *, sm_aux *> &aux_map, bool maybe_mt,
   bool use_other_flag_var)
2223{
gassign *load;
struct fmt_data fmt_data;
struct lim_aux_data *lim_data;
bool multi_threaded_model_p = false;
gimple_stmt_iterator gsi;
sm_aux *aux = new sm_aux;

if (dump_file && (dump_flags & TDF_DETAILS))
  {
    fprintf (dump_file, "Executing store motion of ");
    print_generic_expr (dump_file, ref->mem.ref);
    fprintf (dump_file, " from loop %d\n", loop->num);
  }

aux->tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref)((contains_struct_check ((ref->mem.ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2238, __FUNCTION__))->typed.type),
		 get_lsm_tmp_name (ref->mem.ref, ~0));

fmt_data.loop = loop;
fmt_data.orig_loop = loop;
for_each_index (&ref->mem.ref, force_move_till, &fmt_data);

bool always_stored = ref_always_accessed_p (loop, ref, true);
if (maybe_mt
    && (bb_in_transaction (loop_preheader_edge (loop)->src)
 || (! flag_store_data_racesglobal_options.x_flag_store_data_races && ! always_stored)))
  multi_threaded_model_p = true;

if (multi_threaded_model_p && !use_other_flag_var)
  aux->store_flag
    = execute_sm_if_changed_flag_set (loop, ref, &aux->flag_bbs);
else
  aux->store_flag = NULL_TREE(tree) nullptr;

/* Remember variable setup.  */
aux_map.put (ref, aux);

rewrite_mem_refs (loop, ref, aux->tmp_var);

/* Emit the load code on a random exit edge or into the latch if
   the loop does not exit, so that we are sure it will be processed
   by move_computations after all dependencies.  */
gsi = gsi_for_stmt (first_mem_ref_loc (loop, ref)->stmt);

/* Avoid doing a load if there was no load of the ref in the loop.
   Esp. when the ref is not always stored we cannot optimize it
   away later.  But when it is not always stored we must use a conditional
   store then.  */
if ((!always_stored && !multi_threaded_model_p)
    || (ref->loaded && bitmap_bit_p (ref->loaded, loop->num)))
  load = gimple_build_assign (aux->tmp_var, unshare_expr (ref->mem.ref));
else
  {
    /* If not emitting a load mark the uninitialized state on the
loop entry as not to be warned for.  */
    tree uninit = create_tmp_reg (TREE_TYPE (aux->tmp_var)((contains_struct_check ((aux->tmp_var), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2278, __FUNCTION__))->typed.type));
    suppress_warning (uninit, OPT_Wuninitialized);
    load = gimple_build_assign (aux->tmp_var, uninit);
  }
lim_data = init_lim_data (load);
lim_data->max_loop = loop;
lim_data->tgt_loop = loop;
gsi_insert_before (&gsi, load, GSI_SAME_STMT);

if (aux->store_flag)
  {
    load = gimple_build_assign (aux->store_flag, boolean_false_nodeglobal_trees[TI_BOOLEAN_FALSE]);
    lim_data = init_lim_data (load);
    lim_data->max_loop = loop;
    lim_data->tgt_loop = loop;
    gsi_insert_before (&gsi, load, GSI_SAME_STMT);
  }
2295}

2297/* sm_ord is used for ordinary stores we can retain order with respect
     to other stores
 sm_unord is used for conditional executed stores which need to be
     able to execute in arbitrary order with respect to other stores
 sm_other is used for stores we do not try to apply store motion to.  */
2302enum sm_kind { sm_ord, sm_unord, sm_other };
2303struct seq_entry
2304{
seq_entry () {}
seq_entry (unsigned f, sm_kind k, tree fr = NULLnullptr)
  : first (f), second (k), from (fr) {}
unsigned first;
sm_kind second;
tree from;
2311};

2313static void
2314execute_sm_exit (class loop *loop, edge ex, vec<seq_entry> &seq,
 hash_map<im_mem_ref *, sm_aux *> &aux_map, sm_kind kind,
 edge &append_cond_position, edge &last_cond_fallthru)
2317{
/* Sink the stores to exit from the loop.  */
for (unsigned i = seq.length (); i > 0; --i)
  {
    im_mem_ref *ref = memory_accesses.refs_list[seq[i-1].first];
    if (seq[i-1].second == sm_other)
{
 gcc_assert (kind == sm_ord && seq[i-1].from != NULL_TREE)((void)(!(kind == sm_ord && seq[i-1].from != (tree) nullptr
) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2324, __FUNCTION__), 0 : 0));
 if (dump_file && (dump_flags & TDF_DETAILS))
   {
     fprintf (dump_file, "Re-issueing dependent store of ");
     print_generic_expr (dump_file, ref->mem.ref);
     fprintf (dump_file, " from loop %d on exit %d -> %d\n",
       loop->num, ex->src->index, ex->dest->index);
   }
 gassign *store = gimple_build_assign (unshare_expr (ref->mem.ref),
				seq[i-1].from);
 gsi_insert_on_edge (ex, store);
}
    else
{
 sm_aux *aux = *aux_map.get (ref);
 if (!aux->store_flag || kind == sm_ord)
   {
     gassign *store;
     store = gimple_build_assign (unshare_expr (ref->mem.ref),
			   aux->tmp_var);
     gsi_insert_on_edge (ex, store);
   }
 else
   execute_sm_if_changed (ex, ref->mem.ref, aux->tmp_var,
		   aux->store_flag,
		   loop_preheader_edge (loop), &aux->flag_bbs,
		   append_cond_position, last_cond_fallthru);
}
  }
2353}

2355/* Push the SM candidate at index PTR in the sequence SEQ down until
 we hit the next SM candidate.  Return true if that went OK and
 false if we could not disambiguate agains another unrelated ref.
 Update *AT to the index where the candidate now resides.  */

2360static bool
2361sm_seq_push_down (vec<seq_entry> &seq, unsigned ptr, unsigned *at)
2362{
*at = ptr;
for (; ptr > 0; --ptr)
  {
    seq_entry &new_cand = seq[ptr];
    seq_entry &against = seq[ptr-1];
    if (against.second == sm_ord
 || (against.second == sm_other && against.from != NULL_TREE(tree) nullptr))
/* Found the tail of the sequence.  */
break;
    /* We may not ignore self-dependences here.  */
    if (new_cand.first == against.first
 || !refs_independent_p (memory_accesses.refs_list[new_cand.first],
		  memory_accesses.refs_list[against.first],
		  false))
/* ???  Prune new_cand from the list of refs to apply SM to.  */
return false;
    std::swap (new_cand, against);
    *at = ptr - 1;
  }
return true;
2383}

2385/* Computes the sequence of stores from candidates in REFS_NOT_IN_SEQ to SEQ
 walking backwards from VDEF (or the end of BB if VDEF is NULL).  */

2388static int
2389sm_seq_valid_bb (class loop *loop, basic_block bb, tree vdef,
 vec<seq_entry> &seq, bitmap refs_not_in_seq,
 bitmap refs_not_supported, bool forked,
 bitmap fully_visited)
2393{
if (!vdef)
  for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
gsi_prev (&gsi))
    {
vdef = gimple_vdef (gsi_stmt (gsi));
if (vdef)
 break;
    }
if (!vdef)
  {
    gphi *vphi = get_virtual_phi (bb);
    if (vphi)
vdef = gimple_phi_result (vphi);
  }
if (!vdef)
  {
    if (single_pred_p (bb))
/* This handles the perfect nest case.  */
return sm_seq_valid_bb (loop, single_pred (bb), vdef,
		seq, refs_not_in_seq, refs_not_supported,
		forked, fully_visited);
    return 0;
  }
do
  {
    gimple *def = SSA_NAME_DEF_STMT (vdef)(tree_check ((vdef), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2419, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
    if (gimple_bb (def) != bb)
{
 /* If we forked by processing a PHI do not allow our walk to
    merge again until we handle that robustly.  */
 if (forked)
   {
     /* Mark refs_not_in_seq as unsupported.  */
     bitmap_ior_into (refs_not_supported, refs_not_in_seq);
     return 1;
   }
 /* Otherwise it doesn't really matter if we end up in different
    BBs.  */
 bb = gimple_bb (def);
}
    if (gphi *phi = dyn_cast <gphi *> (def))
{
 /* Handle CFG merges.  Until we handle forks (gimple_bb (def) != bb)
    this is still linear.
    Eventually we want to cache intermediate results per BB
    (but we can't easily cache for different exits?).  */
 /* Stop at PHIs with possible backedges.  */
 if (bb == bb->loop_father->header
     || bb->flags & BB_IRREDUCIBLE_LOOP)
   {
     /* Mark refs_not_in_seq as unsupported.  */
     bitmap_ior_into (refs_not_supported, refs_not_in_seq);
     return 1;
   }
 if (gimple_phi_num_args (phi) == 1)
   return sm_seq_valid_bb (loop, gimple_phi_arg_edge (phi, 0)->src,
		    gimple_phi_arg_def (phi, 0), seq,
		    refs_not_in_seq, refs_not_supported,
		    false, fully_visited);
 if (bitmap_bit_p (fully_visited,
	    SSA_NAME_VERSION (gimple_phi_result (phi))(tree_check ((gimple_phi_result (phi)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2454, __FUNCTION__, (SSA_NAME)))->base.u.version))
   return 1;
 auto_vec<seq_entry> first_edge_seq;
 auto_bitmap tem_refs_not_in_seq (&lim_bitmap_obstack);
 int eret;
 bitmap_copy (tem_refs_not_in_seq, refs_not_in_seq);
 eret = sm_seq_valid_bb (loop, gimple_phi_arg_edge (phi, 0)->src,
		  gimple_phi_arg_def (phi, 0),
		  first_edge_seq,
		  tem_refs_not_in_seq, refs_not_supported,
		  true, fully_visited);
 if (eret != 1)
   return -1;
 /* Simplify our lives by pruning the sequence of !sm_ord.  */
 while (!first_edge_seq.is_empty ()
 && first_edge_seq.last ().second != sm_ord)
   first_edge_seq.pop ();
 for (unsigned int i = 1; i < gimple_phi_num_args (phi); ++i)
   {
     tree vuse = gimple_phi_arg_def (phi, i);
     edge e = gimple_phi_arg_edge (phi, i);
     auto_vec<seq_entry> edge_seq;
     bitmap_and_compl (tem_refs_not_in_seq,
		refs_not_in_seq, refs_not_supported);
     /* If we've marked all refs we search for as unsupported
 we can stop processing and use the sequence as before
 the PHI.  */
     if (bitmap_empty_p (tem_refs_not_in_seq))
return 1;
     eret = sm_seq_valid_bb (loop, e->src, vuse, edge_seq,
		      tem_refs_not_in_seq, refs_not_supported,
		      true, fully_visited);
     if (eret != 1)
return -1;
     /* Simplify our lives by pruning the sequence of !sm_ord.  */
     while (!edge_seq.is_empty ()
     && edge_seq.last ().second != sm_ord)
edge_seq.pop ();
     unsigned min_len = MIN(first_edge_seq.length (),((first_edge_seq.length ()) < (edge_seq.length ()) ? (first_edge_seq
.length ()) : (edge_seq.length ()))
		     edge_seq.length ())((first_edge_seq.length ()) < (edge_seq.length ()) ? (first_edge_seq
.length ()) : (edge_seq.length ()));
     /* Incrementally merge seqs into first_edge_seq.  */
     int first_uneq = -1;
     auto_vec<seq_entry, 2> extra_refs;
     for (unsigned int i = 0; i < min_len; ++i)
{
  /* ???  We can more intelligently merge when we face different
     order by additional sinking operations in one sequence.
     For now we simply mark them as to be processed by the
     not order-preserving SM code.  */
  if (first_edge_seq[i].first != edge_seq[i].first)
    {
      if (first_edge_seq[i].second == sm_ord)
	bitmap_set_bit (refs_not_supported,
			first_edge_seq[i].first);
      if (edge_seq[i].second == sm_ord)
	bitmap_set_bit (refs_not_supported, edge_seq[i].first);
      first_edge_seq[i].second = sm_other;
      first_edge_seq[i].from = NULL_TREE(tree) nullptr;
      /* Record the dropped refs for later processing.  */
      if (first_uneq == -1)
	first_uneq = i;
      extra_refs.safe_push (seq_entry (edge_seq[i].first,
				       sm_other, NULL_TREE(tree) nullptr));
    }
  /* sm_other prevails.  */
  else if (first_edge_seq[i].second != edge_seq[i].second)
    {
      /* Make sure the ref is marked as not supported.  */
      bitmap_set_bit (refs_not_supported,
		      first_edge_seq[i].first);
      first_edge_seq[i].second = sm_other;
      first_edge_seq[i].from = NULL_TREE(tree) nullptr;
    }
  else if (first_edge_seq[i].second == sm_other
	   && first_edge_seq[i].from != NULL_TREE(tree) nullptr
	   && (edge_seq[i].from == NULL_TREE(tree) nullptr
	       || !operand_equal_p (first_edge_seq[i].from,
				    edge_seq[i].from, 0)))
    first_edge_seq[i].from = NULL_TREE(tree) nullptr;
}
     /* Any excess elements become sm_other since they are now
 coonditionally executed.  */
     if (first_edge_seq.length () > edge_seq.length ())
{
  for (unsigned i = edge_seq.length ();
       i < first_edge_seq.length (); ++i)
    {
      if (first_edge_seq[i].second == sm_ord)
	bitmap_set_bit (refs_not_supported,
			first_edge_seq[i].first);
      first_edge_seq[i].second = sm_other;
    }
}
     else if (edge_seq.length () > first_edge_seq.length ())
{
  if (first_uneq == -1)
    first_uneq = first_edge_seq.length ();
  for (unsigned i = first_edge_seq.length ();
       i < edge_seq.length (); ++i)
    {
      if (edge_seq[i].second == sm_ord)
	bitmap_set_bit (refs_not_supported, edge_seq[i].first);
      extra_refs.safe_push (seq_entry (edge_seq[i].first,
				       sm_other, NULL_TREE(tree) nullptr));
    }
}
     /* Put unmerged refs at first_uneq to force dependence checking
 on them.  */
     if (first_uneq != -1)
{
  /* Missing ordered_splice_at.  */
  if ((unsigned)first_uneq == first_edge_seq.length ())
    first_edge_seq.safe_splice (extra_refs);
  else
    {
      unsigned fes_length = first_edge_seq.length ();
      first_edge_seq.safe_grow (fes_length
				+ extra_refs.length ());
      memmove (&first_edge_seq[first_uneq + extra_refs.length ()],
	       &first_edge_seq[first_uneq],
	       (fes_length - first_uneq) * sizeof (seq_entry));
      memcpy (&first_edge_seq[first_uneq],
	      extra_refs.address (),
	      extra_refs.length () * sizeof (seq_entry));
    }
}
   }
 /* Use the sequence from the first edge and push SMs down.  */
 for (unsigned i = 0; i < first_edge_seq.length (); ++i)
   {
     unsigned id = first_edge_seq[i].first;
     seq.safe_push (first_edge_seq[i]);
     unsigned new_idx;
     if ((first_edge_seq[i].second == sm_ord
   || (first_edge_seq[i].second == sm_other
       && first_edge_seq[i].from != NULL_TREE(tree) nullptr))
  && !sm_seq_push_down (seq, seq.length () - 1, &new_idx))
{
  if (first_edge_seq[i].second == sm_ord)
    bitmap_set_bit (refs_not_supported, id);
  /* Mark it sm_other.  */
  seq[new_idx].second = sm_other;
  seq[new_idx].from = NULL_TREE(tree) nullptr;
}
   }
 bitmap_set_bit (fully_visited,
	  SSA_NAME_VERSION (gimple_phi_result (phi))(tree_check ((gimple_phi_result (phi)), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2600, __FUNCTION__, (SSA_NAME)))->base.u.version);
 return 1;
}
    lim_aux_data *data = get_lim_data (def);
    gcc_assert (data)((void)(!(data) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2604, __FUNCTION__), 0 : 0));
    if (data->ref == UNANALYZABLE_MEM_ID0)
return -1;
    /* Stop at memory references which we can't move.  */
    else if (memory_accesses.refs_list[data->ref]->mem.ref == error_mark_nodeglobal_trees[TI_ERROR_MARK]
      || TREE_THIS_VOLATILE((memory_accesses.refs_list[data->ref]->mem.ref)->base
.volatile_flag)
    (memory_accesses.refs_list[data->ref]->mem.ref)((memory_accesses.refs_list[data->ref]->mem.ref)->base
.volatile_flag))
{
 /* Mark refs_not_in_seq as unsupported.  */
 bitmap_ior_into (refs_not_supported, refs_not_in_seq);
 return 1;
}
    /* One of the stores we want to apply SM to and we've not yet seen.  */
    else if (bitmap_clear_bit (refs_not_in_seq, data->ref))
{
 seq.safe_push (seq_entry (data->ref, sm_ord));

 /* 1) push it down the queue until a SMed
    and not ignored ref is reached, skipping all not SMed refs
    and ignored refs via non-TBAA disambiguation.  */
 unsigned new_idx;
 if (!sm_seq_push_down (seq, seq.length () - 1, &new_idx)
     /* If that fails but we did not fork yet continue, we'll see
 to re-materialize all of the stores in the sequence then.
 Further stores will only be pushed up to this one.  */
     && forked)
   {
     bitmap_set_bit (refs_not_supported, data->ref);
     /* Mark it sm_other.  */
     seq[new_idx].second = sm_other;
   }

 /* 2) check whether we've seen all refs we want to SM and if so
    declare success for the active exit  */
 if (bitmap_empty_p (refs_not_in_seq))
   return 1;
}
    else
/* Another store not part of the final sequence.  Simply push it.  */
seq.safe_push (seq_entry (data->ref, sm_other,
		  gimple_assign_rhs1 (def)));

    vdef = gimple_vuse (def);
  }
while (1);
2649}

2651/* Hoists memory references MEM_REFS out of LOOP.  EXITS is the list of exit
 edges of the LOOP.  */

2654static void
2655hoist_memory_references (class loop *loop, bitmap mem_refs,
	 const vec<edge> &exits)
2657{
im_mem_ref *ref;
unsigned  i;
bitmap_iterator bi;

/* There's a special case we can use ordered re-materialization for
   conditionally excuted stores which is when all stores in the loop
   happen in the same basic-block.  In that case we know we'll reach
   all stores and thus can simply process that BB and emit a single
   conditional block of ordered materializations.  See PR102436.  */
basic_block single_store_bb = NULLnullptr;
EXECUTE_IF_SET_IN_BITMAP (&memory_accesses.all_refs_stored_in_loop[loop->num],for (bmp_iter_set_init (&(bi), (&memory_accesses.all_refs_stored_in_loop
[loop->num]), (0), &(i)); bmp_iter_set (&(bi), &
(i)); bmp_iter_next (&(bi), &(i)))
	    0, i, bi)for (bmp_iter_set_init (&(bi), (&memory_accesses.all_refs_stored_in_loop
[loop->num]), (0), &(i)); bmp_iter_set (&(bi), &
(i)); bmp_iter_next (&(bi), &(i)))
  {
    bool fail = false;
    ref = memory_accesses.refs_list[i];
    for (auto loc : ref->accesses_in_loop)
if (!gimple_vdef (loc.stmt))
 ;
else if (!single_store_bb)
 {
   single_store_bb = gimple_bb (loc.stmt);
   bool conditional = false;
   for (edge e : exits)
     if (!dominated_by_p (CDI_DOMINATORS, e->src, single_store_bb))
{
  /* Conditional as seen from e.  */
  conditional = true;
  break;
}
   if (!conditional)
     {
fail = true;
break;
     }
 }
else if (single_store_bb != gimple_bb (loc.stmt))
 {
   fail = true;
   break;
 }
    if (fail)
{
 single_store_bb = NULLnullptr;
 break;
}
  }
if (single_store_bb)
  {
    /* Analyze the single block with stores.  */
    auto_bitmap fully_visited;
    auto_bitmap refs_not_supported;
    auto_bitmap refs_not_in_seq;
    auto_vec<seq_entry> seq;
    bitmap_copy (refs_not_in_seq, mem_refs);
    int res = sm_seq_valid_bb (loop, single_store_bb, NULL_TREE(tree) nullptr,
		 seq, refs_not_in_seq, refs_not_supported,
		 false, fully_visited);
    if (res != 1)
{
 /* Unhandled refs can still fail this.  */
 bitmap_clear (mem_refs);
 return;
}

    /* We cannot handle sm_other since we neither remember the
stored location nor the value at the point we execute them.  */
    for (unsigned i = 0; i < seq.length (); ++i)
{
 unsigned new_i;
 if (seq[i].second == sm_other
     && seq[i].from != NULL_TREE(tree) nullptr)
   seq[i].from = NULL_TREE(tree) nullptr;
 else if ((seq[i].second == sm_ord
    || (seq[i].second == sm_other
	&& seq[i].from != NULL_TREE(tree) nullptr))
   && !sm_seq_push_down (seq, i, &new_i))
   {
     bitmap_set_bit (refs_not_supported, seq[new_i].first);
     seq[new_i].second = sm_other;
     seq[new_i].from = NULL_TREE(tree) nullptr;
   }
}
    bitmap_and_compl_into (mem_refs, refs_not_supported);
    if (bitmap_empty_p (mem_refs))
return;

    /* Prune seq.  */
    while (seq.last ().second == sm_other
    && seq.last ().from == NULL_TREE(tree) nullptr)
seq.pop ();

    hash_map<im_mem_ref *, sm_aux *> aux_map;

    /* Execute SM but delay the store materialization for ordered
sequences on exit.  */
    bool first_p = true;
    EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)for (bmp_iter_set_init (&(bi), (mem_refs), (0), &(i))
; bmp_iter_set (&(bi), &(i)); bmp_iter_next (&(bi
), &(i)))
{
 ref = memory_accesses.refs_list[i];
 execute_sm (loop, ref, aux_map, true, !first_p);
 first_p = false;
}

    /* Get at the single flag variable we eventually produced.  */
    im_mem_ref *ref
= memory_accesses.refs_list[bitmap_first_set_bit (mem_refs)];
    sm_aux *aux = *aux_map.get (ref);

    /* Materialize ordered store sequences on exits.  */
    edge e;
    FOR_EACH_VEC_ELT (exits, i, e)for (i = 0; (exits).iterate ((i), &(e)); ++(i))
{
 edge append_cond_position = NULLnullptr;
 edge last_cond_fallthru = NULLnullptr;
 edge insert_e = e;
 /* Construct the single flag variable control flow and insert
    the ordered seq of stores in the then block.  With
    -fstore-data-races we can do the stores unconditionally.  */
 if (aux->store_flag)
   insert_e
     = single_pred_edge
  (execute_sm_if_changed (e, NULL_TREE(tree) nullptr, NULL_TREE(tree) nullptr,
			  aux->store_flag,
			  loop_preheader_edge (loop),
			  &aux->flag_bbs, append_cond_position,
			  last_cond_fallthru));
 execute_sm_exit (loop, insert_e, seq, aux_map, sm_ord,
	   append_cond_position, last_cond_fallthru);
 gsi_commit_one_edge_insert (insert_e, NULLnullptr);
}

    for (hash_map<im_mem_ref *, sm_aux *>::iterator iter = aux_map.begin ();
  iter != aux_map.end (); ++iter)
delete (*iter).second;

    return;
  }

/* To address PR57359 before actually applying store-motion check
   the candidates found for validity with regards to reordering
   relative to other stores which we until here disambiguated using
   TBAA which isn't valid.
   What matters is the order of the last stores to the mem_refs
   with respect to the other stores of the loop at the point of the
   loop exits.  */

/* For each exit compute the store order, pruning from mem_refs
   on the fly.  */
/* The complexity of this is at least
   O(number of exits * number of SM refs) but more approaching
   O(number of exits * number of SM refs * number of stores).  */
/* ???  Somehow do this in a single sweep over the loop body.  */
auto_vec<std::pair<edge, vec<seq_entry> > > sms;
auto_bitmap refs_not_supported (&lim_bitmap_obstack);
edge e;
FOR_EACH_VEC_ELT (exits, i, e)for (i = 0; (exits).iterate ((i), &(e)); ++(i))
  {
    vec<seq_entry> seq;
    seq.create (4);
    auto_bitmap refs_not_in_seq (&lim_bitmap_obstack);
    bitmap_and_compl (refs_not_in_seq, mem_refs, refs_not_supported);
    if (bitmap_empty_p (refs_not_in_seq))
{
 seq.release ();
 break;
}
    auto_bitmap fully_visited;
    int res = sm_seq_valid_bb (loop, e->src, NULL_TREE(tree) nullptr,
		 seq, refs_not_in_seq,
		 refs_not_supported, false,
		 fully_visited);
    if (res != 1)
{
 bitmap_copy (refs_not_supported, mem_refs);
 seq.release ();
 break;
}
    sms.safe_push (std::make_pair (e, seq));
  }

/* Prune pruned mem_refs from earlier processed exits.  */
bool changed = !bitmap_empty_p (refs_not_supported);
while (changed)
  {
    changed = false;
    std::pair<edge, vec<seq_entry> > *seq;
    FOR_EACH_VEC_ELT (sms, i, seq)for (i = 0; (sms).iterate ((i), &(seq)); ++(i))
{
 bool need_to_push = false;
 for (unsigned i = 0; i < seq->second.length (); ++i)
   {
     sm_kind kind = seq->second[i].second;
     if (kind == sm_other && seq->second[i].from == NULL_TREE(tree) nullptr)
break;
     unsigned id = seq->second[i].first;
     unsigned new_idx;
     if (kind == sm_ord
  && bitmap_bit_p (refs_not_supported, id))
{
  seq->second[i].second = sm_other;
  gcc_assert (seq->second[i].from == NULL_TREE)((void)(!(seq->second[i].from == (tree) nullptr) ? fancy_abort
 ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2858, __FUNCTION__), 0 : 0));
  need_to_push = true;
}
     else if (need_to_push
       && !sm_seq_push_down (seq->second, i, &new_idx))
{
  /* We need to push down both sm_ord and sm_other
     but for the latter we need to disqualify all
     following refs.  */
  if (kind == sm_ord)
    {
      if (bitmap_set_bit (refs_not_supported, id))
	changed = true;
      seq->second[new_idx].second = sm_other;
    }
  else
    {
      for (unsigned j = seq->second.length () - 1;
	   j > new_idx; --j)
	if (seq->second[j].second == sm_ord
	    && bitmap_set_bit (refs_not_supported,
			       seq->second[j].first))
	  changed = true;
      seq->second.truncate (new_idx);
      break;
    }
}
   }
}
  }
std::pair<edge, vec<seq_entry> > *seq;
FOR_EACH_VEC_ELT (sms, i, seq)for (i = 0; (sms).iterate ((i), &(seq)); ++(i))
  {
    /* Prune sm_other from the end.  */
    while (!seq->second.is_empty ()
    && seq->second.last ().second == sm_other)
seq->second.pop ();
    /* Prune duplicates from the start.  */
    auto_bitmap seen (&lim_bitmap_obstack);
    unsigned j, k;
    for (j = k = 0; j < seq->second.length (); ++j)
if (bitmap_set_bit (seen, seq->second[j].first))
 {
   if (k != j)
     seq->second[k] = seq->second[j];
   ++k;
 }
    seq->second.truncate (k);
    /* And verify.  */
    seq_entry *e;
    FOR_EACH_VEC_ELT (seq->second, j, e)for (j = 0; (seq->second).iterate ((j), &(e)); ++(j))
gcc_assert (e->second == sm_ord((void)(!(e->second == sm_ord || (e->second == sm_other
 && e->from != (tree) nullptr)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2910, __FUNCTION__), 0 : 0))
    || (e->second == sm_other && e->from != NULL_TREE))((void)(!(e->second == sm_ord || (e->second == sm_other
 && e->from != (tree) nullptr)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2910, __FUNCTION__), 0 : 0));
  }

/* Verify dependence for refs we cannot handle with the order preserving
   code (refs_not_supported) or prune them from mem_refs.  */
auto_vec<seq_entry> unord_refs;
EXECUTE_IF_SET_IN_BITMAP (refs_not_supported, 0, i, bi)for (bmp_iter_set_init (&(bi), (refs_not_supported), (0),
 &(i)); bmp_iter_set (&(bi), &(i)); bmp_iter_next
 (&(bi), &(i)))
  {
    ref = memory_accesses.refs_list[i];
    if (!ref_indep_loop_p (loop, ref, sm_waw))
bitmap_clear_bit (mem_refs, i);
    /* We've now verified store order for ref with respect to all other
stores in the loop does not matter.  */
    else
unord_refs.safe_push (seq_entry (i, sm_unord));
  }

hash_map<im_mem_ref *, sm_aux *> aux_map;

/* Execute SM but delay the store materialization for ordered
   sequences on exit.  */
EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)for (bmp_iter_set_init (&(bi), (mem_refs), (0), &(i))
; bmp_iter_set (&(bi), &(i)); bmp_iter_next (&(bi
), &(i)))
  {
    ref = memory_accesses.refs_list[i];
    execute_sm (loop, ref, aux_map, bitmap_bit_p (refs_not_supported, i),
  false);
  }

/* Materialize ordered store sequences on exits.  */
FOR_EACH_VEC_ELT (exits, i, e)for (i = 0; (exits).iterate ((i), &(e)); ++(i))
  {
    edge append_cond_position = NULLnullptr;
    edge last_cond_fallthru = NULLnullptr;
    if (i < sms.length ())
{
 gcc_assert (sms[i].first == e)((void)(!(sms[i].first == e) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 2945, __FUNCTION__), 0 : 0));
 execute_sm_exit (loop, e, sms[i].second, aux_map, sm_ord,
	   append_cond_position, last_cond_fallthru);
 sms[i].second.release ();
}
    if (!unord_refs.is_empty ())
execute_sm_exit (loop, e, unord_refs, aux_map, sm_unord,
	 append_cond_position, last_cond_fallthru);
    /* Commit edge inserts here to preserve the order of stores
when an exit exits multiple loops.  */
    gsi_commit_one_edge_insert (e, NULLnullptr);
  }

for (hash_map<im_mem_ref *, sm_aux *>::iterator iter = aux_map.begin ();
     iter != aux_map.end (); ++iter)
  delete (*iter).second;
2961}

2963class ref_always_accessed
2964{
2965public:
ref_always_accessed (class loop *loop_, bool stored_p_)
    : loop (loop_), stored_p (stored_p_) {}
bool operator () (mem_ref_loc *loc);
class loop *loop;
bool stored_p;
2971};

2973bool
2974ref_always_accessed::operator () (mem_ref_loc *loc)
2975{
class loop *must_exec;

struct lim_aux_data *lim_data = get_lim_data (loc->stmt);
if (!lim_data)
  return false;

/* If we require an always executed store make sure the statement
   is a store.  */
if (stored_p)
  {
    tree lhs = gimple_get_lhs (loc->stmt);
    if (!lhs
 || !(DECL_P (lhs)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (lhs)->base.code))] == tcc_declaration) || REFERENCE_CLASS_P (lhs)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (lhs)->base.code))] == tcc_reference)))
return false;
  }

must_exec = lim_data->always_executed_in;
if (!must_exec)
  return false;

if (must_exec == loop
    || flow_loop_nested_p (must_exec, loop))
  return true;

return false;
3001}

3003/* Returns true if REF is always accessed in LOOP.  If STORED_P is true
 make sure REF is always stored to in LOOP.  */

3006static bool
3007ref_always_accessed_p (class loop *loop, im_mem_ref *ref, bool stored_p)
3008{
return for_all_locs_in_loop (loop, ref,
	       ref_always_accessed (loop, stored_p));
3011}

3013/* Returns true if REF1 and REF2 are independent.  */

3015static bool
3016refs_independent_p (im_mem_ref *ref1, im_mem_ref *ref2, bool tbaa_p)
3017{
if (ref1 == ref2)
  return true;

if (dump_file && (dump_flags & TDF_DETAILS))
  fprintf (dump_file, "Querying dependency of refs %u and %u: ",
    ref1->id, ref2->id);

if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache, tbaa_p))
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "dependent.\n");
    return false;
  }
else
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "independent.\n");
    return true;
  }
3037}

3039/* Returns true if REF is independent on all other accessess in LOOP.
 KIND specifies the kind of dependence to consider.
   lim_raw assumes REF is not stored in LOOP and disambiguates RAW
    dependences so if true REF can be hoisted out of LOOP
   sm_war disambiguates a store REF against all other loads to see
   whether the store can be sunk across loads out of LOOP
   sm_waw disambiguates a store REF against all other stores to see
   whether the store can be sunk across stores out of LOOP.  */

3048static bool
3049ref_indep_loop_p (class loop *loop, im_mem_ref *ref, dep_kind kind)
3050{
bool indep_p = true;
bitmap refs_to_check;

if (kind == sm_war)
  refs_to_check = &memory_accesses.refs_loaded_in_loop[loop->num];
else
  refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];

if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID0)
    || ref->mem.ref == error_mark_nodeglobal_trees[TI_ERROR_MARK])
  indep_p = false;
else
  {
    /* tri-state, { unknown, independent, dependent }  */
    dep_state state = query_loop_dependence (loop, ref, kind);
    if (state != dep_unknown)
return state == dep_independent ? true : false;

    class loop *inner = loop->inner;
    while (inner)
{
 if (!ref_indep_loop_p (inner, ref, kind))
   {
     indep_p = false;
     break;
   }
 inner = inner->next;
}

    if (indep_p)
{
 unsigned i;
 bitmap_iterator bi;
 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)for (bmp_iter_set_init (&(bi), (refs_to_check), (0), &
(i)); bmp_iter_set (&(bi), &(i)); bmp_iter_next (&
(bi), &(i)))
   {
     im_mem_ref *aref = memory_accesses.refs_list[i];
     if (aref->mem.ref == error_mark_nodeglobal_trees[TI_ERROR_MARK])
{
  gimple *stmt = aref->accesses_in_loop[0].stmt;
  if ((kind == sm_war
       && ref_maybe_used_by_stmt_p (stmt, &ref->mem,
				    kind != sm_waw))
      || stmt_may_clobber_ref_p_1 (stmt, &ref->mem,
				   kind != sm_waw))
    {
      indep_p = false;
      break;
    }
}
     else if (!refs_independent_p (ref, aref, kind != sm_waw))
{
  indep_p = false;
  break;
}
   }
}
  }

if (dump_file && (dump_flags & TDF_DETAILS))
  fprintf (dump_file, "Querying %s dependencies of ref %u in loop %d: %s\n",
    kind == lim_raw ? "RAW" : (kind == sm_war ? "SM WAR" : "SM WAW"),
    ref->id, loop->num, indep_p ? "independent" : "dependent");

/* Record the computed result in the cache.  */
record_loop_dependence (loop, ref, kind,
	  indep_p ? dep_independent : dep_dependent);

return indep_p;
3119}

3121class ref_in_loop_hot_body
3122{
3123public:
ref_in_loop_hot_body (class loop *loop_) : l (loop_) {}
bool operator () (mem_ref_loc *loc);
class loop *l;
3127};

3129/* Check the coldest loop between loop L and innermost loop.  If there is one
 cold loop between L and INNER_LOOP, store motion can be performed, otherwise
 no cold loop means no store motion.  get_coldest_out_loop also handles cases
 when l is inner_loop.  */
3133bool
3134ref_in_loop_hot_body::operator () (mem_ref_loc *loc)
3135{
basic_block curr_bb = gimple_bb (loc->stmt);
class loop *inner_loop = curr_bb->loop_father;
return get_coldest_out_loop (l, inner_loop, curr_bb);
3139}


3142/* Returns true if we can perform store motion of REF from LOOP.  */

3144static bool
3145can_sm_ref_p (class loop *loop, im_mem_ref *ref)
3146{
tree base;

/* Can't hoist unanalyzable refs.  */
if (!MEM_ANALYZABLE (ref)((ref)->id != 0))
  return false;

/* Can't hoist/sink aggregate copies.  */
if (ref->mem.ref == error_mark_nodeglobal_trees[TI_ERROR_MARK])
  return false;

/* It should be movable.  */
if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref)((contains_struct_check ((ref->mem.ref), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 3158, __FUNCTION__))->typed.type))
    || TREE_THIS_VOLATILE (ref->mem.ref)((ref->mem.ref)->base.volatile_flag)
    || !for_each_index (&ref->mem.ref, may_move_till, loop))
  return false;

/* If it can throw fail, we do not properly update EH info.  */
if (tree_could_throw_p (ref->mem.ref))
  return false;

/* If it can trap, it must be always executed in LOOP.
   Readonly memory locations may trap when storing to them, but
   tree_could_trap_p is a predicate for rvalues, so check that
   explicitly.  */
base = get_base_address (ref->mem.ref);
if ((tree_could_trap_p (ref->mem.ref)
     || (DECL_P (base)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (base)->base.code))] == tcc_declaration) && TREE_READONLY (base)((non_type_check ((base), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-ssa-loop-im.cc"
, 3173, __FUNCTION__))->base.readonly_flag)))
    /* ???  We can at least use false here, allowing loads?  We
are forcing conditional stores if the ref is not always
stored to later anyway.  So this would only guard
the load we need to emit.  Thus when the ref is not
loaded we can elide this completely?  */
    && !ref_always_accessed_p (loop, ref, true))
  return false;

/* Verify all loads of ref can be hoisted.  */
if (ref->loaded
    && bitmap_bit_p (ref->loaded, loop->num)
    && !ref_indep_loop_p (loop, ref, lim_raw))
  return false;

/* Verify the candidate can be disambiguated against all loads,
   that is, we can elide all in-loop stores.  Disambiguation
   against stores is done later when we cannot guarantee preserving
   the order of stores.  */
if (!ref_indep_loop_p (loop, ref, sm_war))
  return false;

/* Verify whether the candidate is hot for LOOP.  Only do store motion if the
  candidate's profile count is hot.  Statement in cold BB shouldn't be moved
  out of it's loop_father.  */
if (!for_all_locs_in_loop (loop, ref, ref_in_loop_hot_body (loop)))
  return false;

return true;
3202}

3204/* Marks the references in LOOP for that store motion should be performed
 in REFS_TO_SM.  SM_EXECUTED is the set of references for that store
 motion was performed in one of the outer loops.  */

3208static void
3209find_refs_for_sm (class loop *loop, bitmap sm_executed, bitmap refs_to_sm)
3210{
bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
unsigned i;
bitmap_iterator bi;
im_mem_ref *ref;

EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)for (bmp_iter_and_compl_init (&(bi), (refs), (sm_executed
), (0), &(i)); bmp_iter_and_compl (&(bi), &(i)); bmp_iter_next
 (&(bi), &(i)))
  {
    ref = memory_accesses.refs_list[i];
    if (can_sm_ref_p (loop, ref) && dbg_cnt (lim))
bitmap_set_bit (refs_to_sm, i);
  }
3222}

3224/* Checks whether LOOP (with exits stored in EXITS array) is suitable
 for a store motion optimization (i.e. whether we can insert statement
 on its exits).  */

3228static bool
3229loop_suitable_for_sm (class loop *loop ATTRIBUTE_UNUSED__attribute__ ((__unused__)),
      const vec<edge> &exits)
3231{
unsigned i;
edge ex;

FOR_EACH_VEC_ELT (exits, i, ex)for (i = 0; (exits).iterate ((i), &(ex)); ++(i))
  if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
    return false;

return true;
3240}

3242/* Try to perform store motion for all memory references modified inside
 LOOP.  SM_EXECUTED is the bitmap of the memory references for that
 store motion was executed in one of the outer loops.  */

3246static void
3247store_motion_loop (class loop *loop, bitmap sm_executed)
3248{
auto_vec<edge> exits = get_loop_exit_edges (loop);
class loop *subloop;
bitmap sm_in_loop = BITMAP_ALLOCbitmap_alloc (&lim_bitmap_obstack);

if (loop_suitable_for_sm (loop, exits))
  {
    find_refs_for_sm (loop, sm_executed, sm_in_loop);
    if (!bitmap_empty_p (sm_in_loop))
hoist_memory_references (loop, sm_in_loop, exits);
  }

bitmap_ior_into (sm_executed, sm_in_loop);
for (subloop = loop->inner; subloop != NULLnullptr; subloop = subloop->next)
  store_motion_loop (subloop, sm_executed);
bitmap_and_compl_into (sm_executed, sm_in_loop);
BITMAP_FREE (sm_in_loop)((void) (bitmap_obstack_free ((bitmap) sm_in_loop), (sm_in_loop
) = (bitmap) nullptr));
3265}

3267/* Try to perform store motion for all memory references modified inside
 loops.  */

3270static void
3271do_store_motion (void)
3272{
class loop *loop;
bitmap sm_executed = BITMAP_ALLOCbitmap_alloc (&lim_bitmap_obstack);

for (loop = current_loops((cfun + 0)->x_current_loops)->tree_root->inner; loop != NULLnullptr; loop = loop->next)
  store_motion_loop (loop, sm_executed);

BITMAP_FREE (sm_executed)((void) (bitmap_obstack_free ((bitmap) sm_executed), (sm_executed
) = (bitmap) nullptr));
3280}

3282/* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
 for each such basic block bb records the outermost loop for that execution
 of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
 blocks that contain a nonpure call.  */

3287static void
3288fill_always_executed_in_1 (class loop *loop, sbitmap contains_call)
3289{
basic_block bb = NULLnullptr, last = NULLnullptr;
edge e;
class loop *inn_loop = loop;

if (ALWAYS_EXECUTED_IN (loop->header)((class loop *) (loop->header)->aux) == NULLnullptr)
  {
    auto_vec<basic_block, 64> worklist;
    worklist.reserve_exact (loop->num_nodes);
    worklist.quick_push (loop->header);
    do
{
 edge_iterator ei;
 bb = worklist.pop ();

 if (!flow_bb_inside_loop_p (inn_loop, bb))
   {
     /* When we are leaving a possibly infinite inner loop
 we have to stop processing.  */
     if (!finite_loop_p (inn_loop))
break;
     /* If the loop was finite we can continue with processing
 the loop we exited to.  */
     inn_loop = bb->loop_father;
   }

 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
   last = bb;

 if (bitmap_bit_p (contains_call, bb->index))
   break;

 /* If LOOP exits from this BB stop processing.  */
 FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
   if (!flow_bb_inside_loop_p (loop, e->dest))
     break;
 if (e)
   break;

 /* A loop might be infinite (TODO use simple loop analysis
    to disprove this if possible).  */
 if (bb->flags & BB_IRREDUCIBLE_LOOP)
   break;

 if (bb->loop_father->header == bb)
   /* Record that we enter into a subloop since it might not
      be finite.  */
   /* ???  Entering into a not always executed subloop makes
      fill_always_executed_in quadratic in loop depth since
      we walk those loops N times.  This is not a problem
      in practice though, see PR102253 for a worst-case testcase.  */
   inn_loop = bb->loop_father;

 /* Walk the body of LOOP sorted by dominance relation.  Additionally,
    if a basic block S dominates the latch, then only blocks dominated
    by S are after it.
    This is get_loop_body_in_dom_order using a worklist algorithm and
    stopping once we are no longer interested in visiting further
    blocks.  */
 unsigned old_len = worklist.length ();
 unsigned postpone = 0;
 for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
      son;
      son = next_dom_son (CDI_DOMINATORS, son))
   {
     if (!flow_bb_inside_loop_p (loop, son))
continue;
     if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
postpone = worklist.length ();
     worklist.quick_push (son);
   }
 if (postpone)
   /* Postponing the block that dominates the latch means
      processing it last and thus putting it earliest in the
      worklist.  */
   std::swap (worklist[old_len], worklist[postpone]);
}
    while (!worklist.is_empty ());

    while (1)
{
 if (dump_enabled_p ())
   dump_printf (MSG_NOTE, "BB %d is always executed in loop %d\n",
	 last->index, loop->num);
 SET_ALWAYS_EXECUTED_IN (last, loop)((last)->aux = (void *) (loop));
 if (last == loop->header)
   break;
 last = get_immediate_dominator (CDI_DOMINATORS, last);
}
  }

for (loop = loop->inner; loop; loop = loop->next)
  fill_always_executed_in_1 (loop, contains_call);
3382}

3384/* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
 for each such basic block bb records the outermost loop for that execution
 of its header implies execution of bb.  */

3388static void
3389fill_always_executed_in (void)
3390{
basic_block bb;
class loop *loop;

auto_sbitmap contains_call (last_basic_block_for_fn (cfun)(((cfun + 0))->cfg->x_last_basic_block));
bitmap_clear (contains_call);
FOR_EACH_BB_FN (bb, cfun)for (bb = ((cfun + 0))->cfg->x_entry_block_ptr->next_bb
; bb != ((cfun + 0))->cfg->x_exit_block_ptr; bb = bb->
next_bb)
  {
    gimple_stmt_iterator gsi;
    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
 if (nonpure_call_p (gsi_stmt (gsi)))
   break;
}

    if (!gsi_end_p (gsi))
bitmap_set_bit (contains_call, bb->index);
  }

for (loop = current_loops((cfun + 0)->x_current_loops)->tree_root->inner; loop; loop = loop->next)
  fill_always_executed_in_1 (loop, contains_call);
3411}

3413/* Find the coldest loop preheader for LOOP, also find the nearest hotter loop
 to LOOP.  Then recursively iterate each inner loop.  */

3416void
3417fill_coldest_and_hotter_out_loop (class loop *coldest_loop,
		  class loop *hotter_loop, class loop *loop)
3419{
if (bb_colder_than_loop_preheader (loop_preheader_edge (loop)->src,
		     coldest_loop))
  coldest_loop = loop;

coldest_outermost_loop[loop->num] = coldest_loop;

hotter_than_inner_loop[loop->num] = NULLnullptr;
class loop *outer_loop = loop_outer (loop);
if (hotter_loop
    && bb_colder_than_loop_preheader (loop_preheader_edge (loop)->src,
			hotter_loop))
  hotter_than_inner_loop[loop->num] = hotter_loop;

if (outer_loop && outer_loop != current_loops((cfun + 0)->x_current_loops)->tree_root
    && bb_colder_than_loop_preheader (loop_preheader_edge (loop)->src,
			outer_loop))
  hotter_than_inner_loop[loop->num] = outer_loop;

if (dump_enabled_p ())
  {
    dump_printf (MSG_NOTE, "loop %d's coldest_outermost_loop is %d, ",
   loop->num, coldest_loop->num);
    if (hotter_than_inner_loop[loop->num])
dump_printf (MSG_NOTE, "hotter_than_inner_loop is %d\n",
     hotter_than_inner_loop[loop->num]->num);
    else
dump_printf (MSG_NOTE, "hotter_than_inner_loop is NULL\n");
  }

class loop *inner_loop;
for (inner_loop = loop->inner; inner_loop; inner_loop = inner_loop->next)
  fill_coldest_and_hotter_out_loop (coldest_loop,
		      hotter_than_inner_loop[loop->num],
		      inner_loop);
3454}

3456/* Compute the global information needed by the loop invariant motion pass.  */

3458static void
3459tree_ssa_lim_initialize (bool store_motion)
3460{
unsigned i;

bitmap_obstack_initialize (&lim_bitmap_obstack);
gcc_obstack_init (&mem_ref_obstack)_obstack_begin (((&mem_ref_obstack)), (memory_block_pool::
block_size), (0), (mempool_obstack_chunk_alloc), (mempool_obstack_chunk_free
));
lim_aux_data_map = new hash_map<gimple *, lim_aux_data *>;

if (flag_tmglobal_options.x_flag_tm)
  compute_transaction_bits ();

memory_accesses.refs = new hash_table<mem_ref_hasher> (100);
memory_accesses.refs_list.create (100);
/* Allocate a special, unanalyzable mem-ref with ID zero.  */
memory_accesses.refs_list.quick_push
  (mem_ref_alloc (NULLnullptr, 0, UNANALYZABLE_MEM_ID0));

memory_accesses.refs_loaded_in_loop.create (number_of_loops (cfun(cfun + 0)));
memory_accesses.refs_loaded_in_loop.quick_grow (number_of_loops (cfun(cfun + 0)));
memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun(cfun + 0)));
memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops (cfun(cfun + 0)));
if (store_motion)
  {
    memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun(cfun + 0)));
    memory_accesses.all_refs_stored_in_loop.quick_grow
				      (number_of_loops (cfun(cfun + 0)));
  }

for (i = 0; i < number_of_loops (cfun(cfun + 0)); i++)
  {
    bitmap_initialize (&memory_accesses.refs_loaded_in_loop[i],
	 &lim_bitmap_obstack);
    bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
	 &lim_bitmap_obstack);
    if (store_motion)
bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
	   &lim_bitmap_obstack);
  }

memory_accesses.ttae_cache = NULLnullptr;

/* Initialize bb_loop_postorder with a mapping from loop->num to
   its postorder index.  */
i = 0;
bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun))((unsigned *) xmalloc (sizeof (unsigned) * (number_of_loops (
(cfun + 0)))));
for (auto loop : loops_list (cfun(cfun + 0), LI_FROM_INNERMOST))
  bb_loop_postorder[loop->num] = i++;
3506}

3508/* Cleans up after the invariant motion pass.  */

3510static void
3511tree_ssa_lim_finalize (void)
3512{
basic_block bb;
unsigned i;
im_mem_ref *ref;

FOR_EACH_BB_FN (bb, cfun)for (bb = ((cfun + 0))->cfg->x_entry_block_ptr->next_bb
; bb != ((cfun + 0))->cfg->x_exit_block_ptr; bb = bb->
next_bb)
  SET_ALWAYS_EXECUTED_IN (bb, NULL)((bb)->aux = (void *) (nullptr));

bitmap_obstack_release (&lim_bitmap_obstack);
delete lim_aux_data_map;

delete memory_accesses.refs;
memory_accesses.refs = NULLnullptr;

FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)for (i = 0; (memory_accesses.refs_list).iterate ((i), &(ref
)); ++(i))
  memref_free (ref);
memory_accesses.refs_list.release ();
obstack_free (&mem_ref_obstack, NULL)__extension__ ({ struct obstack *__o = (&mem_ref_obstack)
; void *__obj = (void *) (nullptr); if (__obj > (void *) __o
->chunk && __obj < (void *) __o->chunk_limit
) __o->next_free = __o->object_base = (char *) __obj; else
 _obstack_free (__o, __obj); });

memory_accesses.refs_loaded_in_loop.release ();
memory_accesses.refs_stored_in_loop.release ();
memory_accesses.all_refs_stored_in_loop.release ();

if (memory_accesses.ttae_cache)
  free_affine_expand_cache (&memory_accesses.ttae_cache);

free (bb_loop_postorder);

coldest_outermost_loop.release ();
hotter_than_inner_loop.release ();
3542}

3544/* Moves invariants from loops.  Only "expensive" invariants are moved out --
 i.e. those that are likely to be win regardless of the register pressure.
 Only perform store motion if STORE_MOTION is true.  */

3548unsigned int
3549loop_invariant_motion_in_fun (function *fun, bool store_motion)
3550{
unsigned int todo = 0;

tree_ssa_lim_initialize (store_motion);

mark_ssa_maybe_undefs ();

/* Gathers information about memory accesses in the loops.  */
analyze_memory_references (store_motion);
6
←
Calling 'analyze_memory_references'→

/* Fills ALWAYS_EXECUTED_IN information for basic blocks.  */
fill_always_executed_in ();

/* Pre-compute coldest outermost loop and nearest hotter loop of each loop.
 */
class loop *loop;
coldest_outermost_loop.create (number_of_loops (cfun(cfun + 0)));
coldest_outermost_loop.safe_grow_cleared (number_of_loops (cfun(cfun + 0)));
hotter_than_inner_loop.create (number_of_loops (cfun(cfun + 0)));
hotter_than_inner_loop.safe_grow_cleared (number_of_loops (cfun(cfun + 0)));
for (loop = current_loops((cfun + 0)->x_current_loops)->tree_root->inner; loop != NULLnullptr; loop = loop->next)
  fill_coldest_and_hotter_out_loop (loop, NULLnullptr, loop);

int *rpo = XNEWVEC (int, last_basic_block_for_fn (fun))((int *) xmalloc (sizeof (int) * (((fun)->cfg->x_last_basic_block
))));
int n = pre_and_rev_post_order_compute_fn (fun, NULLnullptr, rpo, false);

/* For each statement determine the outermost loop in that it is
   invariant and cost for computing the invariant.  */
for (int i = 0; i < n; ++i)
  compute_invariantness (BASIC_BLOCK_FOR_FN (fun, rpo[i])((*((fun)->cfg->x_basic_block_info))[(rpo[i])]));

/* Execute store motion.  Force the necessary invariants to be moved
   out of the loops as well.  */
if (store_motion)
  do_store_motion ();

free (rpo);
rpo = XNEWVEC (int, last_basic_block_for_fn (fun))((int *) xmalloc (sizeof (int) * (((fun)->cfg->x_last_basic_block
))));
n = pre_and_rev_post_order_compute_fn (fun, NULLnullptr, rpo, false);

/* Move the expressions that are expensive enough.  */
for (int i = 0; i < n; ++i)
  todo |= move_computations_worker (BASIC_BLOCK_FOR_FN (fun, rpo[i])((*((fun)->cfg->x_basic_block_info))[(rpo[i])]));

free (rpo);

gsi_commit_edge_inserts ();
if (need_ssa_update_p (fun))
  rewrite_into_loop_closed_ssa (NULLnullptr, TODO_update_ssa(1 << 11));

tree_ssa_lim_finalize ();

return todo;
3603}

3605/* Loop invariant motion pass.  */

3607namespace {

3609const pass_data pass_data_lim =
3610{
GIMPLE_PASS, /* type */
"lim", /* name */
OPTGROUP_LOOP, /* optinfo_flags */
TV_LIM, /* tv_id */
PROP_cfg(1 << 3), /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
0, /* todo_flags_finish */
3620};

3622class pass_lim : public gimple_opt_pass
3623{
3624public:
pass_lim (gcc::context *ctxt)
  : gimple_opt_pass (pass_data_lim, ctxt)
{}

/* opt_pass methods: */
opt_pass * clone () final override { return new pass_lim (m_ctxt); }
bool gate (function *) final override { return flag_tree_loop_imglobal_options.x_flag_tree_loop_im != 0; }
unsigned int execute (function *) final override;

3634}; // class pass_lim

3636unsigned int
3637pass_lim::execute (function *fun)
3638{
bool in_loop_pipeline = scev_initialized_p ();
if (!in_loop_pipeline)
1
Assuming 'in_loop_pipeline' is true→
2
←
Taking false branch→
  loop_optimizer_init (LOOPS_NORMAL(LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
) | LOOPS_HAVE_RECORDED_EXITS);

if (number_of_loops (fun) <= 1)
3
←
Assuming the condition is false→
4
←
Taking false branch→
  return 0;
unsigned int todo = loop_invariant_motion_in_fun (fun, flag_move_loop_storesglobal_options.x_flag_move_loop_stores);
5
←
Calling 'loop_invariant_motion_in_fun'→

if (!in_loop_pipeline)
  loop_optimizer_finalize ();
else
  scev_reset ();
return todo;
3652}

3654} // anon namespace

3656gimple_opt_pass *
3657make_pass_lim (gcc::context *ctxt)
3658{
return new pass_lim (ctxt);
3660}

