Lines Matching refs:loop
34 static void duplicate_subloops (struct loops *, struct loop *, struct loop *);
35 static void copy_loops_to (struct loops *, struct loop **, int,
36 struct loop *);
43 static void add_loop (struct loops *, struct loop *);
44 static void fix_loop_placements (struct loops *, struct loop *, bool *);
47 static void place_new_loop (struct loops *, struct loop *);
48 static void scale_loop_frequencies (struct loop *, int, int);
49 static basic_block create_preheader (struct loop *, int);
50 static void unloop (struct loops *, struct loop *, bool *);
61 /* Remove basic blocks BBS from loop structure and dominance info,
92 /* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
93 Let L be a loop to that BB belongs. Then every successor of BB must either
94 1) belong to some superloop of loop L, or
95 2) be a header of loop K such that K->outer is superloop of L
96 Returns true if we had to move BB into other loop to enforce this condition,
104 struct loop *loop = loops->tree_root, *act;
115 if (flow_loop_nested_p (loop, act))
116 loop = act;
119 if (loop == bb->loop_father)
123 add_bb_to_loop (bb, loop);
128 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
146 struct loop *base_loop;
150 of their successors moved to outer loop. It may be necessary to
152 the basic block up the loop structure. The whole story is a bit
183 /* Subloop header, maybe move the loop upward. */
204 struct loop *nca;
213 the path up the loop tree from base_loop do not contain
242 and update loop structure stored in LOOPS and dominators. Return true if
259 irreducible region, or if the set of basic blocks that belong to a loop
260 that is inside an irreducible region is changed, or if such a loop is
274 normally. We may assume that e->dest is not a header of any loop,
348 loops in the loop tree. */
367 corresponding loop and add it to LOOPS tree. */
369 add_loop (struct loops *loops, struct loop *loop)
374 /* Add it to loop structure. */
375 place_new_loop (loops, loop);
376 loop->level = 1;
380 n = dfs_enumerate_from (loop->latch, 1, alp_enum_p,
381 bbs, n_basic_blocks, loop->header);
384 add_bb_to_loop (bbs[i], loop);
385 add_bb_to_loop (loop->header, loop);
392 scale_loop_frequencies (struct loop *loop, int num, int den)
396 bbs = get_loop_body (loop);
397 scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);
401 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
402 latch to header and update loop tree stored in LOOPS and dominators
408 Returns newly created loop. */
410 struct loop *
420 struct loop *loop = XCNEW (struct loop);
421 struct loop *outer = succ_bb->loop_father->outer;
427 loop->header = header_edge->dest;
428 loop->latch = latch_edge->src;
438 loop_redirect_edge (latch_edge, loop->header);
441 /* During loop versioning, one of the switch_bb edge is already properly
446 loop_redirect_edge (false_edge, loop->header);
450 set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
455 /* Compute new loop. */
456 add_loop (loops, loop);
457 flow_loop_tree_node_add (outer, loop);
459 /* Add switch_bb to appropriate loop. */
467 scale_loop_frequencies (loop, prob, tot_prob);
475 body = get_loop_body (loop);
477 for (i = 0; i < loop->num_nodes; i++)
480 for (i = 0; i < loop->num_nodes; i++)
500 return loop;
504 the LOOP was removed. After this function, original loop latch will
511 unloop (struct loops *loops, struct loop *loop, bool *irred_invalidated)
514 struct loop *ploop;
516 basic_block latch = loop->latch;
519 if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
523 loop header dominates loop latch, so the only thing we have to care of
524 is the placement of loops and basic blocks inside the loop tree. We
525 move them all to the loop->outer, and then let fix_bb_placements do
528 body = get_loop_body (loop);
529 n = loop->num_nodes;
531 if (body[i]->loop_father == loop)
534 add_bb_to_loop (body[i], loop->outer);
538 while (loop->inner)
540 ploop = loop->inner;
542 flow_loop_tree_node_add (loop->outer, ploop);
545 /* Remove the loop and free its data. */
546 flow_loop_tree_node_remove (loop);
547 loops->parray[loop->num] = NULL;
548 flow_loop_free (loop);
553 there is an irreducible region inside the cancelled loop, the flags will
558 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
560 FATHER, and set it as outer loop of LOOP. Return true if placement of
564 fix_loop_placement (struct loop *loop)
570 struct loop *father = loop->pred[0], *act;
572 body = get_loop_body (loop);
573 for (i = 0; i < loop->num_nodes; i++)
575 if (!flow_bb_inside_loop_p (loop, e->dest))
577 act = find_common_loop (loop, e->dest->loop_father);
583 if (father != loop->outer)
585 for (act = loop->outer; act != father; act = act->outer)
586 act->num_nodes -= loop->num_nodes;
587 flow_loop_tree_node_remove (loop);
588 flow_loop_tree_node_add (father, loop);
594 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
597 may cause the right placement of LOOP inside loop tree to change.
599 IRRED_INVALIDATED is set to true if a change in the loop structures might
603 fix_loop_placements (struct loops *loops, struct loop *loop,
606 struct loop *outer;
608 while (loop->outer)
610 outer = loop->outer;
611 if (!fix_loop_placement (loop))
614 /* Changing the placement of a loop in the loop tree may alter the
617 to the loop. So call fix_bb_placements to fix up the placement
619 fix_bb_placements (loops, loop_preheader_edge (loop)->src,
621 loop = outer;
627 place_new_loop (struct loops *loops, struct loop *loop)
630 xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *));
631 loops->parray[loops->num] = loop;
633 loop->num = loops->num++;
636 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
637 created loop into LOOPS structure. */
638 struct loop *
639 duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)
641 struct loop *cloop;
642 cloop = XCNEW (struct loop);
645 /* Initialize copied loop. */
646 cloop->level = loop->level;
648 /* Set it as copy of loop. */
649 loop->copy = cloop;
657 /* Copies structure of subloops of LOOP into TARGET loop, placing
658 newly created loops into loop tree stored in LOOPS. */
660 duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target)
662 struct loop *aloop, *cloop;
664 for (aloop = loop->inner; aloop; aloop = aloop->next)
672 into TARGET loop, placing newly created loops into loop tree LOOPS. */
674 copy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target)
676 struct loop *aloop;
737 can_duplicate_loop_p (struct loop *loop)
740 basic_block *bbs = get_loop_body (loop);
742 ret = can_copy_bbs_p (bbs, loop->num_nodes);
753 struct loop *loop)
760 for (; loop->outer; loop = loop->outer)
762 if (!loop->single_exit)
765 if (loop->single_exit->src->flags & BB_DUPLICATED)
766 loop->single_exit = NULL;
775 this to work, i.e. it must be entry or latch edge of this loop; these are
777 correctly (in case E is latch, the function unrolls the loop, if E is entry
778 edge, it peels the loop). Store edges created by copying ORIG edge from
784 duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
789 struct loop *target, *aloop;
790 struct loop **orig_loops;
792 basic_block header = loop->header, latch = loop->latch;
807 gcc_assert (e->dest == loop->header);
812 /* Orig must be edge out of the loop. */
813 gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
814 gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
817 n = loop->num_nodes;
818 bbs = get_loop_body_in_dom_order (loop);
819 gcc_assert (bbs[0] == loop->header);
820 gcc_assert (bbs[n - 1] == loop->latch);
823 if (!can_copy_bbs_p (bbs, loop->num_nodes))
828 new_bbs = XNEWVEC (basic_block, loop->num_nodes);
830 /* In case we are doing loop peeling and the loop is in the middle of
836 latch_edge = loop_latch_edge (loop);
841 of duplicated loop bodies. */
874 should've managed the flags so all except for original loop
916 for (aloop = loop->inner; aloop; aloop = aloop->next)
918 orig_loops = XCNEWVEC (struct loop *, n_orig_loops);
919 for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
922 loop->copy = target;
935 /* Record exit edge in original loop body. */
949 copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
960 /* Note whether the blocks and edges belong to an irreducible loop. */
987 loop->header);
989 latch = loop->latch = new_bbs[n - 1];
995 loop->header);
1006 the original loop (i.e. in case of peeling). */
1023 /* Update the original loop. */
1045 if (flow_bb_inside_loop_p (loop, dominated))
1078 struct loop *loop = single_succ (jump)->loop_father;
1082 add_bb_to_loop (jump, loop);
1083 loop->latch = jump;
1092 create_preheader (struct loop *loop, int flags)
1096 struct loop *cloop, *ploop;
1103 cloop = loop->outer;
1105 FOR_EACH_EDGE (e, ei, loop->header->preds)
1107 if (e->src == loop->latch)
1117 /* Get an edge that is different from the one from loop->latch
1118 to loop->header. */
1119 e = EDGE_PRED (loop->header,
1120 EDGE_PRED (loop->header, 0)->src == loop->latch);
1126 mfb_kj_edge = loop_latch_edge (loop);
1128 fallthru = make_forwarder_block (loop->header, mfb_keep_just,
1131 loop->header = fallthru->dest;
1135 for (ploop = loop; ploop; ploop = ploop->outer)
1157 loop->header->loop_father = loop;
1167 fprintf (dump_file, "Created preheader block for loop %i\n",
1168 loop->num);
1173 /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
1184 /* Forces all loop latches of loops from loop tree LOOPS to have only single
1190 struct loop *loop;
1195 loop = loops->parray[i];
1196 if (loop->latch != loop->header && single_succ_p (loop->latch))
1199 e = find_edge (loop->latch, loop->header);
1214 struct loop *loop_c;
1237 of the loop we want to version, adds the versioning condition, and
1238 adjust the edges to the two versions of the loop appropriately.
1275 /* Adjust loop header phi nodes. */
1283 This transformation given a condition and a loop, creates
1285 where loop_copy1 is the loop transformed in one way, and loop_copy2
1286 is the loop transformed in another way (or unchanged). 'condition'
1290 If PLACE_AFTER is true, we place the new loop after LOOP in the
1293 struct loop *
1294 loop_version (struct loops *loops, struct loop * loop,
1301 struct loop *nloop;
1304 /* CHECKME: Loop versioning does not handle nested loop at this point. */
1305 if (loop->inner)
1308 /* Record entry and latch edges for the loop */
1309 entry = loop_preheader_edge (loop);
1313 /* Note down head of loop as first_head. */
1316 /* Duplicate loop. */
1317 if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, loops, 1,
1321 /* After duplication entry edge now points to new loop head block.
1325 /* Split loop entry edge and insert new block with cond expr. */
1337 latch_edge = single_succ_edge (get_bb_copy (loop->latch));
1342 single_pred_edge (get_bb_copy (loop->header)),
1346 exit = loop->single_exit;
1360 loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1370 after = loop->latch;
1380 /* At this point condition_bb is loop predheader with two successors,
1381 first_head and second_head. Make sure that loop predheader has only
1383 loop_split_edge_with (loop_preheader_edge (loop), NULL);
1390 (and their headers and latches were set to NULL), loop exists might get
1391 removed (thus the loop nesting may be wrong), and some blocks and edges
1392 were changed (so the information about bb --> loop mapping does not have
1397 If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
1404 struct loop *loop, *ploop;
1407 /* Remove the old bb -> loop mapping. */
1418 loop = loops->parray[i];
1419 if (!loop)
1422 loop->num_nodes = 0;
1423 if (loop->header)
1426 while (loop->inner)
1428 ploop = loop->inner;
1430 flow_loop_tree_node_add (loop->outer, ploop);
1433 /* Remove the loop and free its data. */
1434 flow_loop_tree_node_remove (loop);
1435 loops->parray[loop->num] = NULL;
1436 flow_loop_free (loop);
1440 loop = loops->tree_root;
1443 if (loop->inner)
1444 loop = loop->inner;
1447 while (!loop->next
1448 && loop != loops->tree_root)
1449 loop = loop->outer;
1450 if (loop == loops->tree_root)
1453 loop = loop->next;
1456 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
1459 /* Now fix the loop nesting. */
1462 loop = loops->parray[i];
1463 if (!loop)
1466 bb = loop_preheader_edge (loop)->src;
1467 if (bb->loop_father != loop->outer)
1469 flow_loop_tree_node_remove (loop);
1470 flow_loop_tree_node_add (bb->loop_father, loop);
1474 /* Mark the blocks whose loop has changed. */