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 *);
104   struct loop *loop = loops->tree_root, *act;  in fix_bb_placement()  local
115       if (flow_loop_nested_p (loop, act))  in fix_bb_placement()
116 	loop = act;  in fix_bb_placement()
119   if (loop == bb->loop_father)  in fix_bb_placement()
123   add_bb_to_loop (bb, loop);  in fix_bb_placement()
146   struct loop *base_loop;  in fix_bb_placements()
204 	  struct loop *nca;  in fix_bb_placements()
369 add_loop (struct loops *loops, struct loop *loop)  in add_loop()  argument
375   place_new_loop (loops, loop);  in add_loop()
376   loop->level = 1;  in add_loop()
380   n = dfs_enumerate_from (loop->latch, 1, alp_enum_p,  in add_loop()
381 			  bbs, n_basic_blocks, loop->header);  in add_loop()
384     add_bb_to_loop (bbs[i], loop);  in add_loop()
385   add_bb_to_loop (loop->header, loop);  in add_loop()
392 scale_loop_frequencies (struct loop *loop, int num, int den)  in scale_loop_frequencies()  argument
396   bbs = get_loop_body (loop);  in scale_loop_frequencies()
397   scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);  in scale_loop_frequencies()
410 struct loop *
420   struct loop *loop = XCNEW (struct loop);  in loopify()  local
421   struct loop *outer = succ_bb->loop_father->outer;  in loopify()
427   loop->header = header_edge->dest;  in loopify()
428   loop->latch = latch_edge->src;  in loopify()
438   loop_redirect_edge (latch_edge, loop->header);  in loopify()
446       loop_redirect_edge (false_edge, loop->header);  in loopify()
450       set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);  in loopify()
456   add_loop (loops, loop);  in loopify()
457   flow_loop_tree_node_add (outer, loop);  in loopify()
467   scale_loop_frequencies (loop, prob, tot_prob);  in loopify()
475   body = get_loop_body (loop);  in loopify()
477   for (i = 0; i < loop->num_nodes; i++)  in loopify()
480   for (i = 0; i < loop->num_nodes; i++)  in loopify()
500   return loop;  in loopify()
511 unloop (struct loops *loops, struct loop *loop, bool *irred_invalidated)  in unloop()  argument
514   struct loop *ploop;  in unloop()
516   basic_block latch = loop->latch;  in unloop()
519   if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)  in unloop()
528   body = get_loop_body (loop);  in unloop()
529   n = loop->num_nodes;  in unloop()
531     if (body[i]->loop_father == loop)  in unloop()
534 	add_bb_to_loop (body[i], loop->outer);  in unloop()
538   while (loop->inner)  in unloop()
540       ploop = loop->inner;  in unloop()
542       flow_loop_tree_node_add (loop->outer, ploop);  in unloop()
546   flow_loop_tree_node_remove (loop);  in unloop()
547   loops->parray[loop->num] = NULL;  in unloop()
548   flow_loop_free (loop);  in unloop()
564 fix_loop_placement (struct loop *loop)  in fix_loop_placement()  argument
570   struct loop *father = loop->pred[0], *act;  in fix_loop_placement()
572   body = get_loop_body (loop);  in fix_loop_placement()
573   for (i = 0; i < loop->num_nodes; i++)  in fix_loop_placement()
575       if (!flow_bb_inside_loop_p (loop, e->dest))  in fix_loop_placement()
577 	  act = find_common_loop (loop, e->dest->loop_father);  in fix_loop_placement()
583   if (father != loop->outer)  in fix_loop_placement()
585       for (act = loop->outer; act != father; act = act->outer)  in fix_loop_placement()
586 	act->num_nodes -= loop->num_nodes;  in fix_loop_placement()
587       flow_loop_tree_node_remove (loop);  in fix_loop_placement()
588       flow_loop_tree_node_add (father, loop);  in fix_loop_placement()
603 fix_loop_placements (struct loops *loops, struct loop *loop,  in fix_loop_placements()  argument
606   struct loop *outer;  in fix_loop_placements()
608   while (loop->outer)  in fix_loop_placements()
610       outer = loop->outer;  in fix_loop_placements()
611       if (!fix_loop_placement (loop))  in fix_loop_placements()
619       fix_bb_placements (loops, loop_preheader_edge (loop)->src,  in fix_loop_placements()
621       loop = outer;  in fix_loop_placements()
627 place_new_loop (struct loops *loops, struct loop *loop)  in place_new_loop()  argument
630     xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *));  in place_new_loop()
631   loops->parray[loops->num] = loop;  in place_new_loop()
633   loop->num = loops->num++;  in place_new_loop()
638 struct loop *
639 duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)  in duplicate_loop()  argument
641   struct loop *cloop;  in duplicate_loop()
642   cloop = XCNEW (struct loop);  in duplicate_loop()
646   cloop->level = loop->level;  in duplicate_loop()
649   loop->copy = cloop;  in duplicate_loop()
660 duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target)  in duplicate_subloops()  argument
662   struct loop *aloop, *cloop;  in duplicate_subloops()
664   for (aloop = loop->inner; aloop; aloop = aloop->next)  in duplicate_subloops()
674 copy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target)  in copy_loops_to()
676   struct loop *aloop;  in copy_loops_to()
737 can_duplicate_loop_p (struct loop *loop)  in can_duplicate_loop_p()  argument
740   basic_block *bbs = get_loop_body (loop);  in can_duplicate_loop_p()
742   ret = can_copy_bbs_p (bbs, loop->num_nodes);  in can_duplicate_loop_p()
753 				       struct loop *loop)  in update_single_exits_after_duplication()  argument
760   for (; loop->outer; loop = loop->outer)  in update_single_exits_after_duplication()
762       if (!loop->single_exit)  in update_single_exits_after_duplication()
765       if (loop->single_exit->src->flags & BB_DUPLICATED)  in update_single_exits_after_duplication()
766 	loop->single_exit = NULL;  in update_single_exits_after_duplication()
784 duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,  in duplicate_loop_to_header_edge()  argument
789   struct loop *target, *aloop;  in duplicate_loop_to_header_edge()
790   struct loop **orig_loops;  in duplicate_loop_to_header_edge()
792   basic_block header = loop->header, latch = loop->latch;  in duplicate_loop_to_header_edge()
807   gcc_assert (e->dest == loop->header);  in duplicate_loop_to_header_edge()
813       gcc_assert (flow_bb_inside_loop_p (loop, orig->src));  in duplicate_loop_to_header_edge()
814       gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));  in duplicate_loop_to_header_edge()
817   n = loop->num_nodes;  in duplicate_loop_to_header_edge()
818   bbs = get_loop_body_in_dom_order (loop);  in duplicate_loop_to_header_edge()
819   gcc_assert (bbs[0] == loop->header);  in duplicate_loop_to_header_edge()
820   gcc_assert (bbs[n  - 1] == loop->latch);  in duplicate_loop_to_header_edge()
823   if (!can_copy_bbs_p (bbs, loop->num_nodes))  in duplicate_loop_to_header_edge()
828   new_bbs = XNEWVEC (basic_block, loop->num_nodes);  in duplicate_loop_to_header_edge()
836   latch_edge = loop_latch_edge (loop);  in duplicate_loop_to_header_edge()
916   for (aloop = loop->inner; aloop; aloop = aloop->next)  in duplicate_loop_to_header_edge()
918   orig_loops = XCNEWVEC (struct loop *, n_orig_loops);  in duplicate_loop_to_header_edge()
919   for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)  in duplicate_loop_to_header_edge()
922   loop->copy = target;  in duplicate_loop_to_header_edge()
949       copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,  in duplicate_loop_to_header_edge()
987 					  loop->header);  in duplicate_loop_to_header_edge()
989 	  latch = loop->latch = new_bbs[n - 1];  in duplicate_loop_to_header_edge()
995 					  loop->header);  in duplicate_loop_to_header_edge()
1045 	  if (flow_bb_inside_loop_p (loop, dominated))  in duplicate_loop_to_header_edge()
1078   struct loop *loop = single_succ (jump)->loop_father;  in mfb_update_loops()  local
1082   add_bb_to_loop (jump, loop);  in mfb_update_loops()
1083   loop->latch = jump;  in mfb_update_loops()
1092 create_preheader (struct loop *loop, int flags)  in create_preheader()  argument
1096   struct loop *cloop, *ploop;  in create_preheader()
1103   cloop = loop->outer;  in create_preheader()
1105   FOR_EACH_EDGE (e, ei, loop->header->preds)  in create_preheader()
1107       if (e->src == loop->latch)  in create_preheader()
1119       e = EDGE_PRED (loop->header,  in create_preheader()
1120 		     EDGE_PRED (loop->header, 0)->src == loop->latch);  in create_preheader()
1126   mfb_kj_edge = loop_latch_edge (loop);  in create_preheader()
1128   fallthru = make_forwarder_block (loop->header, mfb_keep_just,  in create_preheader()
1131   loop->header = fallthru->dest;  in create_preheader()
1135   for (ploop = loop; ploop; ploop = ploop->outer)  in create_preheader()
1157   loop->header->loop_father = loop;  in create_preheader()
1168 	     loop->num);  in create_preheader()
1190   struct loop *loop;  in force_single_succ_latches()  local
1195       loop = loops->parray[i];  in force_single_succ_latches()
1196       if (loop->latch != loop->header && single_succ_p (loop->latch))  in force_single_succ_latches()
1199       e = find_edge (loop->latch, loop->header);  in force_single_succ_latches()
1214   struct loop *loop_c;  in loop_split_edge_with()
1293 struct loop *
1294 loop_version (struct loops *loops, struct loop * loop,  in loop_version()  argument
1301   struct loop *nloop;  in loop_version()
1305   if (loop->inner)  in loop_version()
1309   entry = loop_preheader_edge (loop);  in loop_version()
1317   if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, loops, 1,  in loop_version()
1337   latch_edge = single_succ_edge (get_bb_copy (loop->latch));  in loop_version()
1342 		   single_pred_edge (get_bb_copy (loop->header)),  in loop_version()
1346   exit = loop->single_exit;  in loop_version()
1360       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;  in loop_version()
1370       after = loop->latch;  in loop_version()
1383   loop_split_edge_with (loop_preheader_edge (loop), NULL);  in loop_version()
1404   struct loop *loop, *ploop;  in fix_loop_structure()  local
1418       loop = loops->parray[i];  in fix_loop_structure()
1419       if (!loop)  in fix_loop_structure()
1422       loop->num_nodes = 0;  in fix_loop_structure()
1423       if (loop->header)  in fix_loop_structure()
1426       while (loop->inner)  in fix_loop_structure()
1428 	  ploop = loop->inner;  in fix_loop_structure()
1430 	  flow_loop_tree_node_add (loop->outer, ploop);  in fix_loop_structure()
1434       flow_loop_tree_node_remove (loop);  in fix_loop_structure()
1435       loops->parray[loop->num] = NULL;  in fix_loop_structure()
1436       flow_loop_free (loop);  in fix_loop_structure()
1440   loop = loops->tree_root;  in fix_loop_structure()
1443       if (loop->inner)  in fix_loop_structure()
1444 	loop = loop->inner;  in fix_loop_structure()
1447 	  while (!loop->next  in fix_loop_structure()
1448 		 && loop != loops->tree_root)  in fix_loop_structure()
1449 	    loop = loop->outer;  in fix_loop_structure()
1450 	  if (loop == loops->tree_root)  in fix_loop_structure()
1453 	  loop = loop->next;  in fix_loop_structure()
1456       loop->num_nodes = flow_loop_nodes_find (loop->header, loop);  in fix_loop_structure()
1462       loop = loops->parray[i];  in fix_loop_structure()
1463       if (!loop)  in fix_loop_structure()
1466       bb = loop_preheader_edge (loop)->src;  in fix_loop_structure()
1467       if (bb->loop_father != loop->outer)  in fix_loop_structure()
1469 	  flow_loop_tree_node_remove (loop);  in fix_loop_structure()
1470 	  flow_loop_tree_node_add (bb->loop_father, loop);  in fix_loop_structure()