contrib/gcc/loop-invariant.c

1 /* RTL-level loop invariant motion.
21 /* This implements the loop invariant motion pass.  It is very simple
24    eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
26    We proceed loop by loop -- it is simpler than trying to handle things
27    globally and should not lose much.  First we inspect all sets inside loop
35    Then we move the selected invariants out of the loop, creating a new
57 /* The data stored for the loop.  */
61   struct loop *outermost_exit;	/* The outermost exit of the loop.  */
62   bool has_call;		/* True if the loop contains a call.  */
97   /* If we moved the invariant out of the loop, the register that contains its
504    basic blocks that may either exit the loop, or contain the call that
505    does not have to return.  BODY is body of the loop obtained by
509 compute_always_reached (struct loop *loop, basic_block *body,
514   for (i = 0; i < loop->num_nodes; i++)
516       if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
525    exit the loop by cfg edge to HAS_EXIT and MAY_EXIT.  In MAY_EXIT
529 find_exits (struct loop *loop, basic_block *body,
535   struct loop *outermost_exit = loop, *aexit;
539   for (i = 0; i < loop->num_nodes; i++)
541       if (body[i]->loop_father == loop)
556 	      if (flow_bb_inside_loop_p (loop, e->dest))
568 	 through it.  It is sufficient to do this for header of the loop,
579       if (aexit != loop)
589   loop->aux = xcalloc (1, sizeof (struct loop_data));
590   LOOP_DATA (loop)->outermost_exit = outermost_exit;
591   LOOP_DATA (loop)->has_call = has_call;
611 find_defs (struct loop *loop, basic_block *body)
616   for (i = 0; i < loop->num_nodes; i++)
641      the loop.  Otherwise we save only cost of the computation.  */
689    loop invariants, false otherwise.  */
859 find_invariants_body (struct loop *loop, basic_block *body,
864   for (i = 0; i < loop->num_nodes; i++)
873 find_invariants (struct loop *loop)
879   basic_block *body = get_loop_body_in_dom_order (loop);
881   find_exits (loop, body, may_exit, has_exit);
882   compute_always_reached (loop, body, may_exit, always_reached);
883   compute_always_reached (loop, body, has_exit, always_executed);
885   find_defs (loop, body);
886   find_invariants_body (loop, body, always_reached, always_executed);
911    out of the loop and stores them to *COST and *REGS_NEEDED.  */
940        that forces us to add compensation code in and around the loop to
942        from the stack after the loop finishes.
947        pool are not moved out of the loop.
950        However, the primary purpose of this pass is to move loop invariant
971 	     use outside of the loop.  */
986    of registers used in the loop, N_INV_USES is the number of uses of
1010    the loop, N_INV_USES is the number of uses of invariants.  NEW_REGS
1092 	  /* This is a value that is used but not changed inside loop.  */
1130 move_invariant_reg (struct loop *loop, unsigned invno)
1135   basic_block preheader = loop_preheader_edge (loop)->src;
1154 	      if (!move_invariant_reg (loop, i))
1159       /* Move the set out of the loop.  If the set is always executed (we could
1161 	 loop, but it does not seem worth finding out) and it has no uses that
1169 	 the insn out of the loop.  Otherwise, we have to use gen_move_insn
1201       if (!move_invariant_reg (loop, repr->invno))
1236 move_invariants (struct loop *loop)
1242     move_invariant_reg (loop, i);
1293 move_single_loop_invariants (struct loop *loop)
1297   find_invariants (loop);
1299   move_invariants (loop);
1307 free_loop_data (struct loop *loop)
1309   struct loop_data *data = LOOP_DATA (loop);
1312   loop->aux = NULL;
1320   struct loop *loop;
1327   loop = loops->tree_root;
1328   while (loop->inner)
1329     loop = loop->inner;
1331   while (loop != loops->tree_root)
1333       move_single_loop_invariants (loop);
1335       if (loop->next)
1337 	  loop = loop->next;
1338 	  while (loop->inner)
1339 	    loop = loop->inner;
1342 	loop = loop->outer;