contrib/gcc/tree-ssa-loop-im.c

78   struct loop *max_loop;	/* The outermost loop in that the statement
81   struct loop *tgt_loop;	/* The loop out of that we want to move the
84   struct loop *always_executed_in;
85 				/* The outermost loop for that we are sure
86 				   the statement is executed if the loop
97 				   out of the loop when this statement is
100 				   MAX_LOOP loop.  */
123 				   in the loop.  */
139 /* The outermost loop for that execution of the header guarantees that the
141 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
243 	 condition to be moved out of the loop.  */
285 	 Here the strlen call cannot be moved out of the loop, even though
296    loop to that we could move the expression using DEF if it did not have
297    other operands, i.e. the outermost loop enclosing LOOP in that the value
300 static struct loop *
301 outermost_invariant_loop (tree def, struct loop *loop)
305   struct loop *max_loop;
308     return superloop_at_depth (loop, 1);
313     return superloop_at_depth (loop, 1);
315   max_loop = find_common_loop (loop, def_bb->loop_father);
320   if (max_loop == loop)
322   max_loop = superloop_at_depth (loop, max_loop->depth + 1);
330 static struct loop *
331 outermost_invariant_loop_expr (tree expr, struct loop *loop)
335   struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
340     return outermost_invariant_loop (expr, loop);
351       aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
365    Find the outermost loop enclosing LOOP in that value of DEF is invariant
367    this loop as well (i.e. we need to hoist it out of the loop if we want
375 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
380   struct loop *max_loop;
386   max_loop = outermost_invariant_loop (def, loop);
401       && def_bb->loop_father == loop)
469 /* Determine the outermost loop to that it is possible to hoist a statement
471    the outermost loop in that the value computed by STMT is invariant.
472    If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
476    The function returns false if STMT cannot be hoisted outside of the loop it
483   struct loop *loop = bb->loop_father;
484   struct loop *level;
492     level = superloop_at_depth (loop, 1);
496     if (!add_dependency (val, lim_data, loop, true))
500     if (!add_dependency (val, lim_data, loop, false))
508 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
511    operands) is hoisted at least out of the loop LEVEL.  */
514 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
516   struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
535 /* Determines an outermost loop from that we want to hoist the statement STMT.
536    For now we chose the outermost possible loop.  TODO -- use profiling
585   struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
591     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
610 	 to be hoisted out of loop, saving expensive divide.  */
675 /* For each statement determines the outermost loop in that it is invariant,
693 /* Commits edge insertions and updates loop structures.  */
720   struct loop *level;
749       /* We do not really want to move conditionals out of the loop; we just
758 	  fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
787    out of the loop passed in DATA.  Callback for for_each_index.  */
792   struct loop *loop = data, *max_loop;
801       max_loop = outermost_invariant_loop_expr (step, loop);
805       max_loop = outermost_invariant_loop_expr (lbound, loop);
810   max_loop = outermost_invariant_loop (*index, loop);
818    moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */
821 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
832       set_level (stmt, orig_loop, loop);
844     force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
848    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
853   struct loop *loop;
854   struct loop *orig_loop;
868       force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
869       force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
879   set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
1040    of the loop, and assignments to the reference from the temporary variable
1044 schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
1057       fprintf (dump_file, " from loop %d\n", loop->num);
1063   fmt_data.loop = loop;
1064   fmt_data.orig_loop = loop;
1075   LIM_DATA (load)->max_loop = loop;
1076   LIM_DATA (load)->tgt_loop = loop;
1080   bsi_insert_on_edge (loop_latch_edge (loop), load);
1092    to a temporary variable in the loop preheader, store it back on the loop
1096    in loop.  */
1099 determine_lsm_ref (struct loop *loop, edge *exits, unsigned n_exits,
1103   struct loop *must_exec;
1117 	 of the statements in that it occurs is always executed when the loop
1119 	 reference out of the loop we will not cause the error that would not
1123 	 reference, i.e. that on each path from loop entry to loop exit at
1136 	  if (must_exec == loop
1137 	      || flow_loop_nested_p (must_exec, loop))
1145   schedule_sm (loop, exits, n_exits, ref->mem, ref->locs);
1149    of vops clobbered by call in loop or accessed by multiple memory references.
1153 hoist_memory_references (struct loop *loop, struct mem_ref *mem_refs,
1159     determine_lsm_ref (loop, exits, n_exits, clobbered_vops, ref);
1167 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits,
1206 gather_mem_refs_stmt (struct loop *loop, htab_t mem_refs,
1250   /* If we cannot move the reference out of the loop, fail.  */
1251   if (!for_each_index (mem, may_move_till, loop))
1290 gather_mem_refs (struct loop *loop, bitmap clobbered_vops)
1292   basic_block *body = get_loop_body (loop);
1298   for (i = 0; i < loop->num_nodes; i++)
1301 	gather_mem_refs_stmt (loop, mem_refs, clobbered_vops, bsi_stmt (bsi),
1365 determine_lsm_loop (struct loop *loop)
1368   edge *exits = get_loop_exit_edges (loop, &n_exits);
1372   if (!loop_suitable_for_sm (loop, exits, n_exits))
1380   mem_refs = gather_mem_refs (loop, clobbered_vops);
1386   hoist_memory_references (loop, mem_refs, clobbered_vops, exits, n_exits);
1399   struct loop *loop;
1407   loop = loops->tree_root->inner;
1410       determine_lsm_loop (loop);
1412       if (loop->inner)
1414 	  loop = loop->inner;
1417       while (!loop->next)
1419 	  loop = loop->outer;
1420 	  if (loop == loops->tree_root)
1426       loop = loop->next;
1431    for each such basic block bb records the outermost loop for that execution
1436 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1441   struct loop *inn_loop = loop;
1443   if (!loop->header->aux)
1445       bbs = get_loop_body_in_dom_order (loop);
1447       for (i = 0; i < loop->num_nodes; i++)
1452 	  if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1459 	    if (!flow_bb_inside_loop_p (loop, e->dest))
1464 	  /* A loop might be infinite (TODO use simple loop analysis
1474 	      if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1477 	      /* In a loop that is always entered we may proceed anyway.
1485 	  last->aux = loop;
1486 	  if (last == loop->header)
1494   for (loop = loop->inner; loop; loop = loop->next)
1495     fill_always_executed_in (loop, contains_call);
1498 /* Compute the global information needed by the loop invariant motion pass.
1499    LOOPS is the loop tree.  */
1506   struct loop *loop;
1522   for (loop = loops->tree_root->inner; loop; loop = loop->next)
1523     fill_always_executed_in (loop, contains_call);
1549   /* For each statement determine the outermost loop in that it is
1554      out of the loop.  Force the necessary invariants to be moved out of the