contrib/gcc/cfgloop.c

1 /* Natural loop discovery code for GNU compiler.
37    considered to belong to inner loop with same header.  */
44 static int flow_loop_level_compute (struct loop *);
46 static void establish_preds (struct loop *);
51 /* Dump loop related CFG information.  */
97 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
99   return (loop->depth > outer->depth
100 	 && loop->pred[outer->depth] == outer);
103 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
106 struct loop *
107 superloop_at_depth (struct loop *loop, unsigned depth)
109   gcc_assert (depth <= (unsigned) loop->depth);
111   if (depth == (unsigned) loop->depth)
112     return loop;
114   return loop->pred[depth];
117 /* Dump the loop information specified by LOOP to the stream FILE
121 flow_loop_dump (const struct loop *loop, FILE *file,
122 		void (*loop_dump_aux) (const struct loop *, FILE *, int),
128   if (! loop || ! loop->header)
131   fprintf (file, ";;\n;; Loop %d\n", loop->num);
134 	   loop->header->index, loop->latch->index);
136 	   loop->depth, loop->level,
137 	   (long) (loop->outer ? loop->outer->num : -1));
140   bbs = get_loop_body (loop);
141   for (i = 0; i < loop->num_nodes; i++)
147     loop_dump_aux (loop, file, verbose);
150 /* Dump the loop information specified by LOOPS to the stream FILE,
154 flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
167       struct loop *loop = loops->parray[i];
169       if (!loop)
172       flow_loop_dump (loop, file, loop_dump_aux, verbose);
181 flow_loop_free (struct loop *loop)
183   if (loop->pred)
184     free (loop->pred);
185   free (loop);
199       /* Free the loop descriptors.  */
202 	  struct loop *loop = loops->parray[i];
204 	  if (!loop)
207 	  flow_loop_free (loop);
222    Return the number of nodes within the loop.  */
225 flow_loop_nodes_find (basic_block header, struct loop *loop)
231   header->loop_father = loop;
232   header->loop_depth = loop->depth;
234   if (loop->latch->loop_father != loop)
239       stack[sp++] = loop->latch;
240       loop->latch->loop_father = loop;
241       loop->latch->loop_depth = loop->depth;
256 		  && ancestor->loop_father != loop)
258 		  ancestor->loop_father = loop;
259 		  ancestor->loop_depth = loop->depth;
270 /* For each loop in the lOOPS tree that has just a single exit
278   struct loop *loop;
283       loop = loops->parray[i];
284       if (loop)
285 	loop->single_exit = NULL;
301 	  for (loop = bb->loop_father;
302 	       loop != e->dest->loop_father;
303 	       loop = loop->outer)
307 	      if (loop->single_exit)
308 		loop->single_exit = single_succ_edge (ENTRY_BLOCK_PTR);
310 		loop->single_exit = e;
317       loop = loops->parray[i];
318       if (!loop)
321       if (loop->single_exit == single_succ_edge (ENTRY_BLOCK_PTR))
322 	loop->single_exit = NULL;
329 establish_preds (struct loop *loop)
331   struct loop *ploop, *father = loop->outer;
333   loop->depth = father->depth + 1;
335   /* Remember the current loop depth if it is the largest seen so far.  */
336   cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
338   if (loop->pred)
339     free (loop->pred);
340   loop->pred = XNEWVEC (struct loop *, loop->depth);
341   memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
342   loop->pred[father->depth] = father;
344   for (ploop = loop->inner; ploop; ploop = ploop->next)
348 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
349    added loop.  If LOOP has some children, take care of that their
353 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
355   loop->next = father->inner;
356   father->inner = loop;
357   loop->outer = father;
359   establish_preds (loop);
362 /* Remove LOOP from the loop hierarchy tree.  */
365 flow_loop_tree_node_remove (struct loop *loop)
367   struct loop *prev, *father;
369   father = loop->outer;
370   loop->outer = NULL;
372   /* Remove loop from the list of sons.  */
373   if (father->inner == loop)
374     father->inner = loop->next;
377       for (prev = father->inner; prev->next != loop; prev = prev->next);
378       prev->next = loop->next;
381   loop->depth = -1;
382   free (loop->pred);
383   loop->pred = NULL;
386 /* Helper function to compute loop nesting depth and enclosed loop level
387    for the natural loop specified by LOOP.  Returns the loop level.  */
390 flow_loop_level_compute (struct loop *loop)
392   struct loop *inner;
395   if (! loop)
398   /* Traverse loop tree assigning depth and computing level as the
399      maximum level of all the inner loops of this loop.  The loop
400      level is equivalent to the height of the loop in the loop tree
401      and corresponds to the number of enclosed loop levels (including
403   for (inner = loop->inner; inner; inner = inner->next)
411   loop->level = level;
415 /* Compute the loop nesting depth and enclosed loop level for the loop
416    hierarchy tree specified by LOOPS.  Return the maximum enclosed loop
470   /* Split blocks so that each loop has only single latch.  */
543 	  /* Split out the heavy edge, and create inner loop for it.  */
584       struct loop *loop = loops->parray[i];
585       loop->parallel_p = true;
607   /* We are going to recount the maximum loop depth,
625   /* Count the number of loop headers.  This should be the
639 	 loop (not worth the problems).  */
653 	     by this block.  A natural loop has a single entry
655 	     loop.  It also has single back edge to the header
669   /* Allocate loop structures.  */
670   loops->parray = XCNEWVEC (struct loop *, num_loops + 1);
672   /* Dummy loop containing whole function.  */
673   loops->parray[0] = XCNEW (struct loop);
709 	  struct loop *loop;
719 	  loop = loops->parray[num_loops] = XCNEW (struct loop);
721 	  loop->header = header;
722 	  loop->num = num_loops;
733 		  loop->latch = latch;
738 	  flow_loop_tree_node_add (header->loop_father, loop);
739 	  loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
742       /* Assign the loop nesting depth and enclosed loop level for each
743 	 loop.  */
763 flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
765   struct loop *source_loop;
771   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
785 get_loop_body (const struct loop *loop)
790   gcc_assert (loop->num_nodes);
792   tovisit = XCNEWVEC (basic_block, loop->num_nodes);
793   tovisit[tv++] = loop->header;
795   if (loop->latch == EXIT_BLOCK_PTR)
798       gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
803   else if (loop->latch != loop->header)
805       tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
806 			       tovisit + 1, loop->num_nodes - 1,
807 			       loop->header) + 1;
810   gcc_assert (tv == loop->num_nodes);
818 fill_sons_in_loop (const struct loop *loop, basic_block bb,
828       if (!flow_bb_inside_loop_p (loop, son))
831       if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
836       fill_sons_in_loop (loop, son, tovisit, tv);
840     fill_sons_in_loop (loop, postpone, tovisit, tv);
843 /* Gets body of a LOOP (that must be different from the outermost loop)
848 get_loop_body_in_dom_order (const struct loop *loop)
853   gcc_assert (loop->num_nodes);
855   tovisit = XCNEWVEC (basic_block, loop->num_nodes);
857   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
860   fill_sons_in_loop (loop, loop->header, tovisit, &tv);
862   gcc_assert (tv == (int) loop->num_nodes);
870 get_loop_body_in_bfs_order (const struct loop *loop)
878   gcc_assert (loop->num_nodes);
879   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
881   blocks = XCNEWVEC (basic_block, loop->num_nodes);
884   bb = loop->header;
885   while (i < loop->num_nodes)
899 	  if (flow_bb_inside_loop_p (loop, e->dest))
920 get_loop_exit_edges (const struct loop *loop, unsigned int *num_edges)
927   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
929   body = get_loop_body (loop);
931   for (i = 0; i < loop->num_nodes; i++)
933       if (!flow_bb_inside_loop_p (loop, e->dest))
938   for (i = 0; i < loop->num_nodes; i++)
940       if (!flow_bb_inside_loop_p (loop, e->dest))
950 num_loop_branches (const struct loop *loop)
955   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
957   body = get_loop_body (loop);
959   for (i = 0; i < loop->num_nodes; i++)
969 add_bb_to_loop (basic_block bb, struct loop *loop)
973    bb->loop_father = loop;
974    bb->loop_depth = loop->depth;
975    loop->num_nodes++;
976    for (i = 0; i < loop->depth; i++)
977      loop->pred[i]->num_nodes++;
985    struct loop *loop = bb->loop_father;
987    loop->num_nodes--;
988    for (i = 0; i < loop->depth; i++)
989      loop->pred[i]->num_nodes--;
994 /* Finds nearest common ancestor in loop tree for given loops.  */
995 struct loop *
996 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1017 cancel_loop (struct loops *loops, struct loop *loop)
1022   gcc_assert (!loop->inner);
1025   bbs = get_loop_body (loop);
1026   for (i = 0; i < loop->num_nodes; i++)
1027     bbs[i]->loop_father = loop->outer;
1029   /* Remove the loop from structure.  */
1030   flow_loop_tree_node_remove (loop);
1032   /* Remove loop from loops array.  */
1033   loops->parray[loop->num] = NULL;
1035   /* Free loop data.  */
1036   flow_loop_free (loop);
1041 cancel_loop_tree (struct loops *loops, struct loop *loop)
1043   while (loop->inner)
1044     cancel_loop_tree (loops, loop->inner);
1045   cancel_loop (loops, loop);
1050      -- results of get_loop_body really belong to the loop
1051      -- loop header have just single entry edge and single latch edge
1052      -- loop latches have only single successor that is header of their loop
1061   struct loop *loop;
1070     for (loop = bb->loop_father; loop; loop = loop->outer)
1071       sizes[loop->num]++;
1080 	  error ("size of loop %d should be %d, not %d",
1089       loop = loops->parray[i];
1090       if (!loop)
1092       bbs = get_loop_body (loop);
1094       for (j = 0; j < loop->num_nodes; j++)
1095 	if (!flow_bb_inside_loop_p (loop, bbs[j]))
1097 	    error ("bb %d do not belong to loop %d",
1107       loop = loops->parray[i];
1108       if (!loop)
1112 	  && EDGE_COUNT (loop->header->preds) != 2)
1114 	  error ("loop %d's header does not have exactly 2 entries", i);
1119 	  if (!single_succ_p (loop->latch))
1121 	      error ("loop %d's latch does not have exactly 1 successor", i);
1124 	  if (single_succ (loop->latch) != loop->header)
1126 	      error ("loop %d's latch does not have header as successor", i);
1129 	  if (loop->latch->loop_father != loop)
1131 	      error ("loop %d's latch does not belong directly to it", i);
1135       if (loop->header->loop_father != loop)
1137 	  error ("loop %d's header does not belong directly to it", i);
1141 	  && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1143 	  error ("loop %d's latch is marked as part of irreducible region", i);
1224 	      for (loop = bb->loop_father;
1225 		   loop != e->dest->loop_father;
1226 		   loop = loop->outer)
1228 		  sizes[loop->num]++;
1229 		  if (loop->single_exit
1230 		      && loop->single_exit != e)
1232 		      error ("wrong single exit %d->%d recorded for loop %d",
1233 			     loop->single_exit->src->index,
1234 			     loop->single_exit->dest->index,
1235 			     loop->num);
1246 	  loop = loops->parray[i];
1247 	  if (!loop)
1251 	      && !loop->single_exit)
1253 	      error ("single exit not recorded for loop %d", loop->num);
1258 	      && loop->single_exit)
1260 	      error ("loop %d should not have single exit (%d -> %d)",
1261 		     loop->num,
1262 		     loop->single_exit->src->index,
1263 		     loop->single_exit->dest->index);
1276 loop_latch_edge (const struct loop *loop)
1278   return find_edge (loop->latch, loop->header);
1283 loop_preheader_edge (const struct loop *loop)
1288   FOR_EACH_EDGE (e, ei, loop->header->preds)
1289     if (e->src != loop->latch)
1298 loop_exit_edge_p (const struct loop *loop, edge e)
1300   return (flow_bb_inside_loop_p (loop, e->src)
1301 	  && !flow_bb_inside_loop_p (loop, e->dest));