190075Sobrien/* Natural loop discovery code for GNU compiler. 2169689Skan Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. 390075Sobrien 490075SobrienThis file is part of GCC. 590075Sobrien 690075SobrienGCC is free software; you can redistribute it and/or modify it under 790075Sobrienthe terms of the GNU General Public License as published by the Free 890075SobrienSoftware Foundation; either version 2, or (at your option) any later 990075Sobrienversion. 1090075Sobrien 1190075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1290075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1390075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1490075Sobrienfor more details. 1590075Sobrien 1690075SobrienYou should have received a copy of the GNU General Public License 1790075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 2090075Sobrien 2190075Sobrien#include "config.h" 2290075Sobrien#include "system.h" 23132718Skan#include "coretypes.h" 24132718Skan#include "tm.h" 2590075Sobrien#include "rtl.h" 2690075Sobrien#include "hard-reg-set.h" 27169689Skan#include "obstack.h" 28169689Skan#include "function.h" 2990075Sobrien#include "basic-block.h" 30117395Skan#include "toplev.h" 31132718Skan#include "cfgloop.h" 32132718Skan#include "flags.h" 33169689Skan#include "tree.h" 34169689Skan#include "tree-flow.h" 3590075Sobrien 36117395Skan/* Ratio of frequencies of edges so that one of more latch edges is 37117395Skan considered to belong to inner loop with same header. */ 38117395Skan#define HEAVY_EDGE_RATIO 8 39117395Skan 40169689Skan#define HEADER_BLOCK(B) (* (int *) (B)->aux) 41169689Skan#define LATCH_EDGE(E) (*(int *) (E)->aux) 42169689Skan 43132718Skanstatic void flow_loops_cfg_dump (const struct loops *, FILE *); 44132718Skanstatic int flow_loop_level_compute (struct loop *); 45169689Skanstatic void flow_loops_level_compute (struct loops *); 46132718Skanstatic void establish_preds (struct loop *); 47132718Skanstatic void canonicalize_loop_headers (void); 48132718Skanstatic bool glb_enum_p (basic_block, void *); 4990075Sobrien 5090075Sobrien/* Dump loop related CFG information. */ 5190075Sobrien 5290075Sobrienstatic void 53132718Skanflow_loops_cfg_dump (const struct loops *loops, FILE *file) 5490075Sobrien{ 5590075Sobrien int i; 56117395Skan basic_block bb; 5790075Sobrien 58132718Skan if (! loops->num || ! file) 5990075Sobrien return; 6090075Sobrien 61117395Skan FOR_EACH_BB (bb) 6290075Sobrien { 6390075Sobrien edge succ; 64169689Skan edge_iterator ei; 6590075Sobrien 66117395Skan fprintf (file, ";; %d succs { ", bb->index); 67169689Skan FOR_EACH_EDGE (succ, ei, bb->succs) 6890075Sobrien fprintf (file, "%d ", succ->dest->index); 69117395Skan fprintf (file, "}\n"); 7090075Sobrien } 7190075Sobrien 7290075Sobrien /* Dump the DFS node order. */ 7390075Sobrien if (loops->cfg.dfs_order) 7490075Sobrien { 7590075Sobrien fputs (";; DFS order: ", file); 76169689Skan for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) 7790075Sobrien fprintf (file, "%d ", loops->cfg.dfs_order[i]); 7890075Sobrien 7990075Sobrien fputs ("\n", file); 8090075Sobrien } 8190075Sobrien 8290075Sobrien /* Dump the reverse completion node order. */ 8390075Sobrien if (loops->cfg.rc_order) 8490075Sobrien { 8590075Sobrien fputs (";; RC order: ", file); 86169689Skan for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) 8790075Sobrien fprintf (file, "%d ", loops->cfg.rc_order[i]); 8890075Sobrien 8990075Sobrien fputs ("\n", file); 9090075Sobrien } 9190075Sobrien} 9290075Sobrien 93117395Skan/* Return nonzero if the nodes of LOOP are a subset of OUTER. */ 9490075Sobrien 95117395Skanbool 96132718Skanflow_loop_nested_p (const struct loop *outer, const struct loop *loop) 9790075Sobrien{ 98169689Skan return (loop->depth > outer->depth 99169689Skan && loop->pred[outer->depth] == outer); 10090075Sobrien} 10190075Sobrien 102169689Skan/* Returns the loop such that LOOP is nested DEPTH (indexed from zero) 103169689Skan loops within LOOP. */ 104169689Skan 105169689Skanstruct loop * 106169689Skansuperloop_at_depth (struct loop *loop, unsigned depth) 107169689Skan{ 108169689Skan gcc_assert (depth <= (unsigned) loop->depth); 109169689Skan 110169689Skan if (depth == (unsigned) loop->depth) 111169689Skan return loop; 112169689Skan 113169689Skan return loop->pred[depth]; 114169689Skan} 115169689Skan 11690075Sobrien/* Dump the loop information specified by LOOP to the stream FILE 11790075Sobrien using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ 11890075Sobrien 11990075Sobrienvoid 120132718Skanflow_loop_dump (const struct loop *loop, FILE *file, 121132718Skan void (*loop_dump_aux) (const struct loop *, FILE *, int), 122132718Skan int verbose) 12390075Sobrien{ 124117395Skan basic_block *bbs; 125132718Skan unsigned i; 126117395Skan 12790075Sobrien if (! loop || ! loop->header) 12890075Sobrien return; 12990075Sobrien 130169689Skan fprintf (file, ";;\n;; Loop %d\n", loop->num); 13190075Sobrien 132169689Skan fprintf (file, ";; header %d, latch %d\n", 133169689Skan loop->header->index, loop->latch->index); 13490075Sobrien fprintf (file, ";; depth %d, level %d, outer %ld\n", 13590075Sobrien loop->depth, loop->level, 13690075Sobrien (long) (loop->outer ? loop->outer->num : -1)); 13790075Sobrien 138117395Skan fprintf (file, ";; nodes:"); 139117395Skan bbs = get_loop_body (loop); 140117395Skan for (i = 0; i < loop->num_nodes; i++) 141117395Skan fprintf (file, " %d", bbs[i]->index); 142117395Skan free (bbs); 143117395Skan fprintf (file, "\n"); 14490075Sobrien 14590075Sobrien if (loop_dump_aux) 14690075Sobrien loop_dump_aux (loop, file, verbose); 14790075Sobrien} 14890075Sobrien 14990075Sobrien/* Dump the loop information specified by LOOPS to the stream FILE, 15090075Sobrien using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ 15190075Sobrien 15290075Sobrienvoid 153132718Skanflow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) 15490075Sobrien{ 155117395Skan int i; 15690075Sobrien int num_loops; 15790075Sobrien 15890075Sobrien num_loops = loops->num; 15990075Sobrien if (! num_loops || ! file) 16090075Sobrien return; 16190075Sobrien 162169689Skan fprintf (file, ";; %d loops found\n", num_loops); 163117395Skan 16490075Sobrien for (i = 0; i < num_loops; i++) 16590075Sobrien { 166117395Skan struct loop *loop = loops->parray[i]; 16790075Sobrien 168117395Skan if (!loop) 169117395Skan continue; 170117395Skan 17190075Sobrien flow_loop_dump (loop, file, loop_dump_aux, verbose); 17290075Sobrien } 17390075Sobrien 17490075Sobrien if (verbose) 17590075Sobrien flow_loops_cfg_dump (loops, file); 17690075Sobrien} 17790075Sobrien 178117395Skan/* Free data allocated for LOOP. */ 179132718Skanvoid 180132718Skanflow_loop_free (struct loop *loop) 181117395Skan{ 182117395Skan if (loop->pred) 183117395Skan free (loop->pred); 184117395Skan free (loop); 185117395Skan} 186117395Skan 18790075Sobrien/* Free all the memory allocated for LOOPS. */ 18890075Sobrien 18990075Sobrienvoid 190132718Skanflow_loops_free (struct loops *loops) 19190075Sobrien{ 192117395Skan if (loops->parray) 19390075Sobrien { 194132718Skan unsigned i; 19590075Sobrien 196169689Skan gcc_assert (loops->num); 19790075Sobrien 19890075Sobrien /* Free the loop descriptors. */ 19990075Sobrien for (i = 0; i < loops->num; i++) 20090075Sobrien { 201117395Skan struct loop *loop = loops->parray[i]; 20290075Sobrien 203117395Skan if (!loop) 204117395Skan continue; 205117395Skan 206117395Skan flow_loop_free (loop); 20790075Sobrien } 20890075Sobrien 209117395Skan free (loops->parray); 210117395Skan loops->parray = NULL; 21190075Sobrien 21290075Sobrien if (loops->cfg.dfs_order) 21390075Sobrien free (loops->cfg.dfs_order); 214117395Skan if (loops->cfg.rc_order) 215117395Skan free (loops->cfg.rc_order); 21690075Sobrien 21790075Sobrien } 21890075Sobrien} 21990075Sobrien 220117395Skan/* Find the nodes contained within the LOOP with header HEADER. 221117395Skan Return the number of nodes within the loop. */ 22290075Sobrien 223169689Skanint 224132718Skanflow_loop_nodes_find (basic_block header, struct loop *loop) 22590075Sobrien{ 22690075Sobrien basic_block *stack; 22790075Sobrien int sp; 228117395Skan int num_nodes = 1; 22990075Sobrien 230117395Skan header->loop_father = loop; 231117395Skan header->loop_depth = loop->depth; 23290075Sobrien 233117395Skan if (loop->latch->loop_father != loop) 23490075Sobrien { 235169689Skan stack = XNEWVEC (basic_block, n_basic_blocks); 236117395Skan sp = 0; 23790075Sobrien num_nodes++; 238117395Skan stack[sp++] = loop->latch; 239117395Skan loop->latch->loop_father = loop; 240117395Skan loop->latch->loop_depth = loop->depth; 241132718Skan 242117395Skan while (sp) 24390075Sobrien { 244117395Skan basic_block node; 245117395Skan edge e; 246169689Skan edge_iterator ei; 24790075Sobrien 248117395Skan node = stack[--sp]; 249132718Skan 250169689Skan FOR_EACH_EDGE (e, ei, node->preds) 25190075Sobrien { 252117395Skan basic_block ancestor = e->src; 253117395Skan 254117395Skan if (ancestor != ENTRY_BLOCK_PTR 255117395Skan && ancestor->loop_father != loop) 256117395Skan { 257117395Skan ancestor->loop_father = loop; 258117395Skan ancestor->loop_depth = loop->depth; 259117395Skan num_nodes++; 260117395Skan stack[sp++] = ancestor; 261117395Skan } 26290075Sobrien } 26390075Sobrien } 264117395Skan free (stack); 26590075Sobrien } 26690075Sobrien return num_nodes; 26790075Sobrien} 26890075Sobrien 269169689Skan/* For each loop in the lOOPS tree that has just a single exit 270169689Skan record the exit edge. */ 27190075Sobrien 272169689Skanvoid 273169689Skanmark_single_exit_loops (struct loops *loops) 27490075Sobrien{ 275169689Skan basic_block bb; 27690075Sobrien edge e; 277169689Skan struct loop *loop; 278169689Skan unsigned i; 27990075Sobrien 280169689Skan for (i = 1; i < loops->num; i++) 281169689Skan { 282169689Skan loop = loops->parray[i]; 283169689Skan if (loop) 284169689Skan loop->single_exit = NULL; 285169689Skan } 28690075Sobrien 287169689Skan FOR_EACH_BB (bb) 288169689Skan { 289169689Skan edge_iterator ei; 290169689Skan if (bb->loop_father == loops->tree_root) 291169689Skan continue; 292169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 293169689Skan { 294169689Skan if (e->dest == EXIT_BLOCK_PTR) 295169689Skan continue; 29690075Sobrien 297169689Skan if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) 298169689Skan continue; 29990075Sobrien 300169689Skan for (loop = bb->loop_father; 301169689Skan loop != e->dest->loop_father; 302169689Skan loop = loop->outer) 30390075Sobrien { 304169689Skan /* If we have already seen an exit, mark this by the edge that 305169689Skan surely does not occur as any exit. */ 306169689Skan if (loop->single_exit) 307169689Skan loop->single_exit = single_succ_edge (ENTRY_BLOCK_PTR); 308169689Skan else 309169689Skan loop->single_exit = e; 31090075Sobrien } 31190075Sobrien } 31290075Sobrien } 31390075Sobrien 314169689Skan for (i = 1; i < loops->num; i++) 315169689Skan { 316169689Skan loop = loops->parray[i]; 317169689Skan if (!loop) 318169689Skan continue; 319169689Skan 320169689Skan if (loop->single_exit == single_succ_edge (ENTRY_BLOCK_PTR)) 321169689Skan loop->single_exit = NULL; 322169689Skan } 323169689Skan 324169689Skan loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS; 32590075Sobrien} 32690075Sobrien 327132718Skanstatic void 328132718Skanestablish_preds (struct loop *loop) 329132718Skan{ 330132718Skan struct loop *ploop, *father = loop->outer; 331132718Skan 332132718Skan loop->depth = father->depth + 1; 333169689Skan 334169689Skan /* Remember the current loop depth if it is the largest seen so far. */ 335169689Skan cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth); 336169689Skan 337132718Skan if (loop->pred) 338132718Skan free (loop->pred); 339169689Skan loop->pred = XNEWVEC (struct loop *, loop->depth); 340132718Skan memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth); 341132718Skan loop->pred[father->depth] = father; 342132718Skan 343132718Skan for (ploop = loop->inner; ploop; ploop = ploop->next) 344132718Skan establish_preds (ploop); 345132718Skan} 346132718Skan 347117395Skan/* Add LOOP to the loop hierarchy tree where FATHER is father of the 348132718Skan added loop. If LOOP has some children, take care of that their 349132718Skan pred field will be initialized correctly. */ 35090075Sobrien 351117395Skanvoid 352132718Skanflow_loop_tree_node_add (struct loop *father, struct loop *loop) 35390075Sobrien{ 354117395Skan loop->next = father->inner; 355117395Skan father->inner = loop; 356117395Skan loop->outer = father; 35790075Sobrien 358132718Skan establish_preds (loop); 35990075Sobrien} 36090075Sobrien 361117395Skan/* Remove LOOP from the loop hierarchy tree. */ 36290075Sobrien 363117395Skanvoid 364132718Skanflow_loop_tree_node_remove (struct loop *loop) 36590075Sobrien{ 366117395Skan struct loop *prev, *father; 36790075Sobrien 368117395Skan father = loop->outer; 369117395Skan loop->outer = NULL; 37090075Sobrien 371117395Skan /* Remove loop from the list of sons. */ 372117395Skan if (father->inner == loop) 373117395Skan father->inner = loop->next; 374117395Skan else 375117395Skan { 376117395Skan for (prev = father->inner; prev->next != loop; prev = prev->next); 377117395Skan prev->next = loop->next; 378117395Skan } 37990075Sobrien 380117395Skan loop->depth = -1; 381117395Skan free (loop->pred); 382117395Skan loop->pred = NULL; 38390075Sobrien} 38490075Sobrien 38590075Sobrien/* Helper function to compute loop nesting depth and enclosed loop level 386117395Skan for the natural loop specified by LOOP. Returns the loop level. */ 38790075Sobrien 38890075Sobrienstatic int 389132718Skanflow_loop_level_compute (struct loop *loop) 39090075Sobrien{ 39190075Sobrien struct loop *inner; 39290075Sobrien int level = 1; 39390075Sobrien 39490075Sobrien if (! loop) 39590075Sobrien return 0; 39690075Sobrien 39790075Sobrien /* Traverse loop tree assigning depth and computing level as the 39890075Sobrien maximum level of all the inner loops of this loop. The loop 39990075Sobrien level is equivalent to the height of the loop in the loop tree 40090075Sobrien and corresponds to the number of enclosed loop levels (including 40190075Sobrien itself). */ 40290075Sobrien for (inner = loop->inner; inner; inner = inner->next) 40390075Sobrien { 404117395Skan int ilevel = flow_loop_level_compute (inner) + 1; 40590075Sobrien 406117395Skan if (ilevel > level) 407117395Skan level = ilevel; 40890075Sobrien } 40990075Sobrien 41090075Sobrien loop->level = level; 41190075Sobrien return level; 41290075Sobrien} 41390075Sobrien 41490075Sobrien/* Compute the loop nesting depth and enclosed loop level for the loop 41590075Sobrien hierarchy tree specified by LOOPS. Return the maximum enclosed loop 41690075Sobrien level. */ 41790075Sobrien 418169689Skanstatic void 419132718Skanflow_loops_level_compute (struct loops *loops) 42090075Sobrien{ 421169689Skan flow_loop_level_compute (loops->tree_root); 42290075Sobrien} 42390075Sobrien 424169689Skan/* A callback to update latch and header info for basic block JUMP created 425169689Skan by redirecting an edge. */ 42690075Sobrien 427169689Skanstatic void 428169689Skanupdate_latch_info (basic_block jump) 42990075Sobrien{ 430169689Skan alloc_aux_for_block (jump, sizeof (int)); 431169689Skan HEADER_BLOCK (jump) = 0; 432169689Skan alloc_aux_for_edge (single_pred_edge (jump), sizeof (int)); 433169689Skan LATCH_EDGE (single_pred_edge (jump)) = 0; 434169689Skan set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump)); 43590075Sobrien} 43690075Sobrien 437169689Skan/* A callback for make_forwarder block, to redirect all edges except for 438169689Skan MFB_KJ_EDGE to the entry part. E is the edge for that we should decide 439169689Skan whether to redirect it. */ 440117395Skan 441169689Skanstatic edge mfb_kj_edge; 442169689Skanstatic bool 443169689Skanmfb_keep_just (edge e) 444117395Skan{ 445169689Skan return e != mfb_kj_edge; 446117395Skan} 447117395Skan 448169689Skan/* A callback for make_forwarder block, to redirect the latch edges into an 449169689Skan entry part. E is the edge for that we should decide whether to redirect 450169689Skan it. */ 451117395Skan 452169689Skanstatic bool 453169689Skanmfb_keep_nonlatch (edge e) 454117395Skan{ 455169689Skan return LATCH_EDGE (e); 456117395Skan} 457117395Skan 458117395Skan/* Takes care of merging natural loops with shared headers. */ 459169689Skan 460117395Skanstatic void 461132718Skancanonicalize_loop_headers (void) 462117395Skan{ 463117395Skan basic_block header; 464117395Skan edge e; 465132718Skan 466117395Skan alloc_aux_for_blocks (sizeof (int)); 467117395Skan alloc_aux_for_edges (sizeof (int)); 468117395Skan 469117395Skan /* Split blocks so that each loop has only single latch. */ 470117395Skan FOR_EACH_BB (header) 471117395Skan { 472169689Skan edge_iterator ei; 473117395Skan int num_latches = 0; 474117395Skan int have_abnormal_edge = 0; 475117395Skan 476169689Skan FOR_EACH_EDGE (e, ei, header->preds) 477117395Skan { 478117395Skan basic_block latch = e->src; 479117395Skan 480117395Skan if (e->flags & EDGE_ABNORMAL) 481117395Skan have_abnormal_edge = 1; 482117395Skan 483117395Skan if (latch != ENTRY_BLOCK_PTR 484132718Skan && dominated_by_p (CDI_DOMINATORS, latch, header)) 485117395Skan { 486117395Skan num_latches++; 487117395Skan LATCH_EDGE (e) = 1; 488117395Skan } 489117395Skan } 490117395Skan if (have_abnormal_edge) 491117395Skan HEADER_BLOCK (header) = 0; 492117395Skan else 493117395Skan HEADER_BLOCK (header) = num_latches; 494117395Skan } 495117395Skan 496169689Skan if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR))) 497117395Skan { 498117395Skan basic_block bb; 499117395Skan 500117395Skan /* We could not redirect edges freely here. On the other hand, 501117395Skan we can simply split the edge from entry block. */ 502169689Skan bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); 503132718Skan 504169689Skan alloc_aux_for_edge (single_succ_edge (bb), sizeof (int)); 505169689Skan LATCH_EDGE (single_succ_edge (bb)) = 0; 506117395Skan alloc_aux_for_block (bb, sizeof (int)); 507117395Skan HEADER_BLOCK (bb) = 0; 508117395Skan } 509117395Skan 510117395Skan FOR_EACH_BB (header) 511117395Skan { 512117395Skan int max_freq, is_heavy; 513169689Skan edge heavy, tmp_edge; 514169689Skan edge_iterator ei; 515117395Skan 516169689Skan if (HEADER_BLOCK (header) <= 1) 517117395Skan continue; 518117395Skan 519117395Skan /* Find a heavy edge. */ 520117395Skan is_heavy = 1; 521117395Skan heavy = NULL; 522117395Skan max_freq = 0; 523169689Skan FOR_EACH_EDGE (e, ei, header->preds) 524117395Skan if (LATCH_EDGE (e) && 525117395Skan EDGE_FREQUENCY (e) > max_freq) 526117395Skan max_freq = EDGE_FREQUENCY (e); 527169689Skan FOR_EACH_EDGE (e, ei, header->preds) 528117395Skan if (LATCH_EDGE (e) && 529117395Skan EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO) 530117395Skan { 531117395Skan if (heavy) 532117395Skan { 533117395Skan is_heavy = 0; 534117395Skan break; 535117395Skan } 536117395Skan else 537117395Skan heavy = e; 538117395Skan } 539117395Skan 540117395Skan if (is_heavy) 541117395Skan { 542169689Skan /* Split out the heavy edge, and create inner loop for it. */ 543169689Skan mfb_kj_edge = heavy; 544169689Skan tmp_edge = make_forwarder_block (header, mfb_keep_just, 545169689Skan update_latch_info); 546169689Skan alloc_aux_for_block (tmp_edge->dest, sizeof (int)); 547169689Skan HEADER_BLOCK (tmp_edge->dest) = 1; 548169689Skan alloc_aux_for_edge (tmp_edge, sizeof (int)); 549169689Skan LATCH_EDGE (tmp_edge) = 0; 550169689Skan HEADER_BLOCK (header)--; 551117395Skan } 552169689Skan 553169689Skan if (HEADER_BLOCK (header) > 1) 554169689Skan { 555169689Skan /* Create a new latch block. */ 556169689Skan tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch, 557169689Skan update_latch_info); 558169689Skan alloc_aux_for_block (tmp_edge->dest, sizeof (int)); 559169689Skan HEADER_BLOCK (tmp_edge->src) = 0; 560169689Skan HEADER_BLOCK (tmp_edge->dest) = 1; 561169689Skan alloc_aux_for_edge (tmp_edge, sizeof (int)); 562169689Skan LATCH_EDGE (tmp_edge) = 1; 563169689Skan } 564117395Skan } 565117395Skan 566117395Skan free_aux_for_blocks (); 567117395Skan free_aux_for_edges (); 568169689Skan 569169689Skan#ifdef ENABLE_CHECKING 570169689Skan verify_dominators (CDI_DOMINATORS); 571169689Skan#endif 572117395Skan} 573117395Skan 574169689Skan/* Initialize all the parallel_p fields of the loops structure to true. */ 575169689Skan 576169689Skanstatic void 577169689Skaninitialize_loops_parallel_p (struct loops *loops) 578169689Skan{ 579169689Skan unsigned int i; 580169689Skan 581169689Skan for (i = 0; i < loops->num; i++) 582169689Skan { 583169689Skan struct loop *loop = loops->parray[i]; 584169689Skan loop->parallel_p = true; 585169689Skan } 586169689Skan} 587169689Skan 58890075Sobrien/* Find all the natural loops in the function and save in LOOPS structure and 589169689Skan recalculate loop_depth information in basic block structures. 590169689Skan Return the number of natural loops found. */ 59190075Sobrien 59290075Sobrienint 593169689Skanflow_loops_find (struct loops *loops) 59490075Sobrien{ 59590075Sobrien int b; 59690075Sobrien int num_loops; 59790075Sobrien edge e; 59890075Sobrien sbitmap headers; 59990075Sobrien int *dfs_order; 60090075Sobrien int *rc_order; 601117395Skan basic_block header; 602117395Skan basic_block bb; 60390075Sobrien 60490075Sobrien memset (loops, 0, sizeof *loops); 60590075Sobrien 606169689Skan /* We are going to recount the maximum loop depth, 607169689Skan so throw away the last count. */ 608169689Skan cfun->max_loop_depth = 0; 609169689Skan 61090075Sobrien /* Taking care of this degenerate case makes the rest of 61190075Sobrien this code simpler. */ 612169689Skan if (n_basic_blocks == NUM_FIXED_BLOCKS) 61390075Sobrien return 0; 61490075Sobrien 61590075Sobrien dfs_order = NULL; 61690075Sobrien rc_order = NULL; 61790075Sobrien 618169689Skan /* Ensure that the dominators are computed. */ 619169689Skan calculate_dominance_info (CDI_DOMINATORS); 620169689Skan 621117395Skan /* Join loops with shared headers. */ 622117395Skan canonicalize_loop_headers (); 623117395Skan 624117395Skan /* Count the number of loop headers. This should be the 62590075Sobrien same as the number of natural loops. */ 626117395Skan headers = sbitmap_alloc (last_basic_block); 627117395Skan sbitmap_zero (headers); 628117395Skan 62990075Sobrien num_loops = 0; 630117395Skan FOR_EACH_BB (header) 63190075Sobrien { 632169689Skan edge_iterator ei; 633117395Skan int more_latches = 0; 634132718Skan 63590075Sobrien header->loop_depth = 0; 63690075Sobrien 637122180Skan /* If we have an abnormal predecessor, do not consider the 638122180Skan loop (not worth the problems). */ 639169689Skan FOR_EACH_EDGE (e, ei, header->preds) 640122180Skan if (e->flags & EDGE_ABNORMAL) 641122180Skan break; 642122180Skan if (e) 643122180Skan continue; 644122180Skan 645169689Skan FOR_EACH_EDGE (e, ei, header->preds) 64690075Sobrien { 64790075Sobrien basic_block latch = e->src; 64890075Sobrien 649169689Skan gcc_assert (!(e->flags & EDGE_ABNORMAL)); 650117395Skan 65190075Sobrien /* Look for back edges where a predecessor is dominated 65290075Sobrien by this block. A natural loop has a single entry 65390075Sobrien node (header) that dominates all the nodes in the 65490075Sobrien loop. It also has single back edge to the header 655117395Skan from a latch node. */ 656132718Skan if (latch != ENTRY_BLOCK_PTR 657132718Skan && dominated_by_p (CDI_DOMINATORS, latch, header)) 658117395Skan { 659117395Skan /* Shared headers should be eliminated by now. */ 660169689Skan gcc_assert (!more_latches); 661117395Skan more_latches = 1; 662117395Skan SET_BIT (headers, header->index); 663117395Skan num_loops++; 664117395Skan } 66590075Sobrien } 66690075Sobrien } 66790075Sobrien 668117395Skan /* Allocate loop structures. */ 669169689Skan loops->parray = XCNEWVEC (struct loop *, num_loops + 1); 670117395Skan 671117395Skan /* Dummy loop containing whole function. */ 672169689Skan loops->parray[0] = XCNEW (struct loop); 673117395Skan loops->parray[0]->next = NULL; 674117395Skan loops->parray[0]->inner = NULL; 675117395Skan loops->parray[0]->outer = NULL; 676117395Skan loops->parray[0]->depth = 0; 677117395Skan loops->parray[0]->pred = NULL; 678169689Skan loops->parray[0]->num_nodes = n_basic_blocks; 679117395Skan loops->parray[0]->latch = EXIT_BLOCK_PTR; 680117395Skan loops->parray[0]->header = ENTRY_BLOCK_PTR; 681117395Skan ENTRY_BLOCK_PTR->loop_father = loops->parray[0]; 682117395Skan EXIT_BLOCK_PTR->loop_father = loops->parray[0]; 683117395Skan 684117395Skan loops->tree_root = loops->parray[0]; 685117395Skan 686117395Skan /* Find and record information about all the natural loops 687117395Skan in the CFG. */ 688117395Skan loops->num = 1; 689117395Skan FOR_EACH_BB (bb) 690117395Skan bb->loop_father = loops->tree_root; 691117395Skan 69290075Sobrien if (num_loops) 69390075Sobrien { 69490075Sobrien /* Compute depth first search order of the CFG so that outer 69590075Sobrien natural loops will be found before inner natural loops. */ 696169689Skan dfs_order = XNEWVEC (int, n_basic_blocks); 697169689Skan rc_order = XNEWVEC (int, n_basic_blocks); 698169689Skan pre_and_rev_post_order_compute (dfs_order, rc_order, false); 69990075Sobrien 70090075Sobrien /* Save CFG derived information to avoid recomputing it. */ 70190075Sobrien loops->cfg.dfs_order = dfs_order; 70290075Sobrien loops->cfg.rc_order = rc_order; 70390075Sobrien 704117395Skan num_loops = 1; 70590075Sobrien 706169689Skan for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++) 70790075Sobrien { 708117395Skan struct loop *loop; 709169689Skan edge_iterator ei; 71090075Sobrien 71190075Sobrien /* Search the nodes of the CFG in reverse completion order 71290075Sobrien so that we can find outer loops first. */ 713117395Skan if (!TEST_BIT (headers, rc_order[b])) 714117395Skan continue; 71590075Sobrien 716117395Skan header = BASIC_BLOCK (rc_order[b]); 717132718Skan 718169689Skan loop = loops->parray[num_loops] = XCNEW (struct loop); 719117395Skan 720117395Skan loop->header = header; 721117395Skan loop->num = num_loops; 722117395Skan num_loops++; 723117395Skan 724117395Skan /* Look for the latch for this header block. */ 725169689Skan FOR_EACH_EDGE (e, ei, header->preds) 72690075Sobrien { 727117395Skan basic_block latch = e->src; 72890075Sobrien 729117395Skan if (latch != ENTRY_BLOCK_PTR 730132718Skan && dominated_by_p (CDI_DOMINATORS, latch, header)) 73190075Sobrien { 73290075Sobrien loop->latch = latch; 733117395Skan break; 73490075Sobrien } 73590075Sobrien } 736117395Skan 737117395Skan flow_loop_tree_node_add (header->loop_father, loop); 738117395Skan loop->num_nodes = flow_loop_nodes_find (loop->header, loop); 73990075Sobrien } 74090075Sobrien 741117395Skan /* Assign the loop nesting depth and enclosed loop level for each 742117395Skan loop. */ 743169689Skan flow_loops_level_compute (loops); 74490075Sobrien 745117395Skan loops->num = num_loops; 746169689Skan initialize_loops_parallel_p (loops); 74790075Sobrien } 748132718Skan 749132718Skan sbitmap_free (headers); 750132718Skan 751132718Skan loops->state = 0; 752117395Skan#ifdef ENABLE_CHECKING 753117395Skan verify_flow_info (); 754132718Skan verify_loop_structure (loops); 755117395Skan#endif 75690075Sobrien 757117395Skan return loops->num; 75890075Sobrien} 75990075Sobrien 760117395Skan/* Return nonzero if basic block BB belongs to LOOP. */ 761117395Skanbool 762132718Skanflow_bb_inside_loop_p (const struct loop *loop, const basic_block bb) 763117395Skan{ 764117395Skan struct loop *source_loop; 76590075Sobrien 766117395Skan if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) 767117395Skan return 0; 768117395Skan 769117395Skan source_loop = bb->loop_father; 770117395Skan return loop == source_loop || flow_loop_nested_p (loop, source_loop); 771117395Skan} 772117395Skan 773117395Skan/* Enumeration predicate for get_loop_body. */ 774117395Skanstatic bool 775132718Skanglb_enum_p (basic_block bb, void *glb_header) 776117395Skan{ 777117395Skan return bb != (basic_block) glb_header; 77890075Sobrien} 779117395Skan 780132718Skan/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs 781132718Skan order against direction of edges from latch. Specially, if 782132718Skan header != latch, latch is the 1-st block. */ 783117395Skanbasic_block * 784132718Skanget_loop_body (const struct loop *loop) 785117395Skan{ 786117395Skan basic_block *tovisit, bb; 787132718Skan unsigned tv = 0; 788117395Skan 789169689Skan gcc_assert (loop->num_nodes); 790117395Skan 791169689Skan tovisit = XCNEWVEC (basic_block, loop->num_nodes); 792117395Skan tovisit[tv++] = loop->header; 793117395Skan 794117395Skan if (loop->latch == EXIT_BLOCK_PTR) 795117395Skan { 796117395Skan /* There may be blocks unreachable from EXIT_BLOCK. */ 797169689Skan gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks); 798117395Skan FOR_EACH_BB (bb) 799117395Skan tovisit[tv++] = bb; 800117395Skan tovisit[tv++] = EXIT_BLOCK_PTR; 801117395Skan } 802117395Skan else if (loop->latch != loop->header) 803117395Skan { 804117395Skan tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p, 805117395Skan tovisit + 1, loop->num_nodes - 1, 806117395Skan loop->header) + 1; 807117395Skan } 808117395Skan 809169689Skan gcc_assert (tv == loop->num_nodes); 810117395Skan return tovisit; 811117395Skan} 812117395Skan 813169689Skan/* Fills dominance descendants inside LOOP of the basic block BB into 814169689Skan array TOVISIT from index *TV. */ 815169689Skan 816169689Skanstatic void 817169689Skanfill_sons_in_loop (const struct loop *loop, basic_block bb, 818169689Skan basic_block *tovisit, int *tv) 819169689Skan{ 820169689Skan basic_block son, postpone = NULL; 821169689Skan 822169689Skan tovisit[(*tv)++] = bb; 823169689Skan for (son = first_dom_son (CDI_DOMINATORS, bb); 824169689Skan son; 825169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 826169689Skan { 827169689Skan if (!flow_bb_inside_loop_p (loop, son)) 828169689Skan continue; 829169689Skan 830169689Skan if (dominated_by_p (CDI_DOMINATORS, loop->latch, son)) 831169689Skan { 832169689Skan postpone = son; 833169689Skan continue; 834169689Skan } 835169689Skan fill_sons_in_loop (loop, son, tovisit, tv); 836169689Skan } 837169689Skan 838169689Skan if (postpone) 839169689Skan fill_sons_in_loop (loop, postpone, tovisit, tv); 840169689Skan} 841169689Skan 842169689Skan/* Gets body of a LOOP (that must be different from the outermost loop) 843169689Skan sorted by dominance relation. Additionally, if a basic block s dominates 844169689Skan the latch, then only blocks dominated by s are be after it. */ 845169689Skan 846169689Skanbasic_block * 847169689Skanget_loop_body_in_dom_order (const struct loop *loop) 848169689Skan{ 849169689Skan basic_block *tovisit; 850169689Skan int tv; 851169689Skan 852169689Skan gcc_assert (loop->num_nodes); 853169689Skan 854169689Skan tovisit = XCNEWVEC (basic_block, loop->num_nodes); 855169689Skan 856169689Skan gcc_assert (loop->latch != EXIT_BLOCK_PTR); 857169689Skan 858169689Skan tv = 0; 859169689Skan fill_sons_in_loop (loop, loop->header, tovisit, &tv); 860169689Skan 861169689Skan gcc_assert (tv == (int) loop->num_nodes); 862169689Skan 863169689Skan return tovisit; 864169689Skan} 865169689Skan 866169689Skan/* Get body of a LOOP in breadth first sort order. */ 867169689Skan 868169689Skanbasic_block * 869169689Skanget_loop_body_in_bfs_order (const struct loop *loop) 870169689Skan{ 871169689Skan basic_block *blocks; 872169689Skan basic_block bb; 873169689Skan bitmap visited; 874169689Skan unsigned int i = 0; 875169689Skan unsigned int vc = 1; 876169689Skan 877169689Skan gcc_assert (loop->num_nodes); 878169689Skan gcc_assert (loop->latch != EXIT_BLOCK_PTR); 879169689Skan 880169689Skan blocks = XCNEWVEC (basic_block, loop->num_nodes); 881169689Skan visited = BITMAP_ALLOC (NULL); 882169689Skan 883169689Skan bb = loop->header; 884169689Skan while (i < loop->num_nodes) 885169689Skan { 886169689Skan edge e; 887169689Skan edge_iterator ei; 888169689Skan 889169689Skan if (!bitmap_bit_p (visited, bb->index)) 890169689Skan { 891169689Skan /* This basic block is now visited */ 892169689Skan bitmap_set_bit (visited, bb->index); 893169689Skan blocks[i++] = bb; 894169689Skan } 895169689Skan 896169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 897169689Skan { 898169689Skan if (flow_bb_inside_loop_p (loop, e->dest)) 899169689Skan { 900169689Skan if (!bitmap_bit_p (visited, e->dest->index)) 901169689Skan { 902169689Skan bitmap_set_bit (visited, e->dest->index); 903169689Skan blocks[i++] = e->dest; 904169689Skan } 905169689Skan } 906169689Skan } 907169689Skan 908169689Skan gcc_assert (i >= vc); 909169689Skan 910169689Skan bb = blocks[vc++]; 911169689Skan } 912169689Skan 913169689Skan BITMAP_FREE (visited); 914169689Skan return blocks; 915169689Skan} 916169689Skan 917132718Skan/* Gets exit edges of a LOOP, returning their number in N_EDGES. */ 918132718Skanedge * 919169689Skanget_loop_exit_edges (const struct loop *loop, unsigned int *num_edges) 920132718Skan{ 921132718Skan edge *edges, e; 922132718Skan unsigned i, n; 923132718Skan basic_block * body; 924169689Skan edge_iterator ei; 925132718Skan 926169689Skan gcc_assert (loop->latch != EXIT_BLOCK_PTR); 927132718Skan 928132718Skan body = get_loop_body (loop); 929132718Skan n = 0; 930132718Skan for (i = 0; i < loop->num_nodes; i++) 931169689Skan FOR_EACH_EDGE (e, ei, body[i]->succs) 932132718Skan if (!flow_bb_inside_loop_p (loop, e->dest)) 933132718Skan n++; 934169689Skan edges = XNEWVEC (edge, n); 935169689Skan *num_edges = n; 936132718Skan n = 0; 937132718Skan for (i = 0; i < loop->num_nodes; i++) 938169689Skan FOR_EACH_EDGE (e, ei, body[i]->succs) 939132718Skan if (!flow_bb_inside_loop_p (loop, e->dest)) 940132718Skan edges[n++] = e; 941132718Skan free (body); 942132718Skan 943132718Skan return edges; 944132718Skan} 945132718Skan 946169689Skan/* Counts the number of conditional branches inside LOOP. */ 947169689Skan 948169689Skanunsigned 949169689Skannum_loop_branches (const struct loop *loop) 950169689Skan{ 951169689Skan unsigned i, n; 952169689Skan basic_block * body; 953169689Skan 954169689Skan gcc_assert (loop->latch != EXIT_BLOCK_PTR); 955169689Skan 956169689Skan body = get_loop_body (loop); 957169689Skan n = 0; 958169689Skan for (i = 0; i < loop->num_nodes; i++) 959169689Skan if (EDGE_COUNT (body[i]->succs) >= 2) 960169689Skan n++; 961169689Skan free (body); 962169689Skan 963169689Skan return n; 964169689Skan} 965169689Skan 966117395Skan/* Adds basic block BB to LOOP. */ 967117395Skanvoid 968132718Skanadd_bb_to_loop (basic_block bb, struct loop *loop) 969132718Skan{ 970117395Skan int i; 971132718Skan 972117395Skan bb->loop_father = loop; 973117395Skan bb->loop_depth = loop->depth; 974117395Skan loop->num_nodes++; 975117395Skan for (i = 0; i < loop->depth; i++) 976117395Skan loop->pred[i]->num_nodes++; 977117395Skan } 978117395Skan 979117395Skan/* Remove basic block BB from loops. */ 980117395Skanvoid 981132718Skanremove_bb_from_loops (basic_block bb) 982132718Skan{ 983117395Skan int i; 984117395Skan struct loop *loop = bb->loop_father; 985117395Skan 986117395Skan loop->num_nodes--; 987117395Skan for (i = 0; i < loop->depth; i++) 988117395Skan loop->pred[i]->num_nodes--; 989117395Skan bb->loop_father = NULL; 990117395Skan bb->loop_depth = 0; 991169689Skan} 992117395Skan 993117395Skan/* Finds nearest common ancestor in loop tree for given loops. */ 994117395Skanstruct loop * 995132718Skanfind_common_loop (struct loop *loop_s, struct loop *loop_d) 996117395Skan{ 997117395Skan if (!loop_s) return loop_d; 998117395Skan if (!loop_d) return loop_s; 999132718Skan 1000117395Skan if (loop_s->depth < loop_d->depth) 1001117395Skan loop_d = loop_d->pred[loop_s->depth]; 1002117395Skan else if (loop_s->depth > loop_d->depth) 1003117395Skan loop_s = loop_s->pred[loop_d->depth]; 1004117395Skan 1005117395Skan while (loop_s != loop_d) 1006117395Skan { 1007117395Skan loop_s = loop_s->outer; 1008117395Skan loop_d = loop_d->outer; 1009117395Skan } 1010117395Skan return loop_s; 1011117395Skan} 1012117395Skan 1013132718Skan/* Cancels the LOOP; it must be innermost one. */ 1014169689Skan 1015169689Skanstatic void 1016132718Skancancel_loop (struct loops *loops, struct loop *loop) 1017132718Skan{ 1018132718Skan basic_block *bbs; 1019132718Skan unsigned i; 1020132718Skan 1021169689Skan gcc_assert (!loop->inner); 1022132718Skan 1023132718Skan /* Move blocks up one level (they should be removed as soon as possible). */ 1024132718Skan bbs = get_loop_body (loop); 1025132718Skan for (i = 0; i < loop->num_nodes; i++) 1026132718Skan bbs[i]->loop_father = loop->outer; 1027132718Skan 1028132718Skan /* Remove the loop from structure. */ 1029132718Skan flow_loop_tree_node_remove (loop); 1030132718Skan 1031132718Skan /* Remove loop from loops array. */ 1032132718Skan loops->parray[loop->num] = NULL; 1033132718Skan 1034132718Skan /* Free loop data. */ 1035132718Skan flow_loop_free (loop); 1036132718Skan} 1037132718Skan 1038132718Skan/* Cancels LOOP and all its subloops. */ 1039132718Skanvoid 1040132718Skancancel_loop_tree (struct loops *loops, struct loop *loop) 1041132718Skan{ 1042132718Skan while (loop->inner) 1043132718Skan cancel_loop_tree (loops, loop->inner); 1044132718Skan cancel_loop (loops, loop); 1045132718Skan} 1046132718Skan 1047132718Skan/* Checks that LOOPS are all right: 1048132718Skan -- sizes of loops are all right 1049117395Skan -- results of get_loop_body really belong to the loop 1050117395Skan -- loop header have just single entry edge and single latch edge 1051117395Skan -- loop latches have only single successor that is header of their loop 1052132718Skan -- irreducible loops are correctly marked 1053117395Skan */ 1054117395Skanvoid 1055132718Skanverify_loop_structure (struct loops *loops) 1056117395Skan{ 1057132718Skan unsigned *sizes, i, j; 1058132718Skan sbitmap irreds; 1059117395Skan basic_block *bbs, bb; 1060117395Skan struct loop *loop; 1061117395Skan int err = 0; 1062132718Skan edge e; 1063117395Skan 1064117395Skan /* Check sizes. */ 1065169689Skan sizes = XCNEWVEC (unsigned, loops->num); 1066117395Skan sizes[0] = 2; 1067117395Skan 1068117395Skan FOR_EACH_BB (bb) 1069117395Skan for (loop = bb->loop_father; loop; loop = loop->outer) 1070117395Skan sizes[loop->num]++; 1071117395Skan 1072117395Skan for (i = 0; i < loops->num; i++) 1073117395Skan { 1074117395Skan if (!loops->parray[i]) 1075169689Skan continue; 1076117395Skan 1077117395Skan if (loops->parray[i]->num_nodes != sizes[i]) 1078117395Skan { 1079169689Skan error ("size of loop %d should be %d, not %d", 1080117395Skan i, sizes[i], loops->parray[i]->num_nodes); 1081117395Skan err = 1; 1082117395Skan } 1083117395Skan } 1084117395Skan 1085117395Skan /* Check get_loop_body. */ 1086117395Skan for (i = 1; i < loops->num; i++) 1087117395Skan { 1088117395Skan loop = loops->parray[i]; 1089117395Skan if (!loop) 1090117395Skan continue; 1091117395Skan bbs = get_loop_body (loop); 1092117395Skan 1093117395Skan for (j = 0; j < loop->num_nodes; j++) 1094117395Skan if (!flow_bb_inside_loop_p (loop, bbs[j])) 1095117395Skan { 1096169689Skan error ("bb %d do not belong to loop %d", 1097117395Skan bbs[j]->index, i); 1098117395Skan err = 1; 1099117395Skan } 1100117395Skan free (bbs); 1101117395Skan } 1102117395Skan 1103117395Skan /* Check headers and latches. */ 1104117395Skan for (i = 1; i < loops->num; i++) 1105117395Skan { 1106117395Skan loop = loops->parray[i]; 1107117395Skan if (!loop) 1108117395Skan continue; 1109117395Skan 1110132718Skan if ((loops->state & LOOPS_HAVE_PREHEADERS) 1111169689Skan && EDGE_COUNT (loop->header->preds) != 2) 1112117395Skan { 1113169689Skan error ("loop %d's header does not have exactly 2 entries", i); 1114117395Skan err = 1; 1115117395Skan } 1116132718Skan if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES) 1117117395Skan { 1118169689Skan if (!single_succ_p (loop->latch)) 1119117395Skan { 1120169689Skan error ("loop %d's latch does not have exactly 1 successor", i); 1121117395Skan err = 1; 1122117395Skan } 1123169689Skan if (single_succ (loop->latch) != loop->header) 1124117395Skan { 1125169689Skan error ("loop %d's latch does not have header as successor", i); 1126117395Skan err = 1; 1127117395Skan } 1128117395Skan if (loop->latch->loop_father != loop) 1129117395Skan { 1130169689Skan error ("loop %d's latch does not belong directly to it", i); 1131117395Skan err = 1; 1132117395Skan } 1133117395Skan } 1134117395Skan if (loop->header->loop_father != loop) 1135117395Skan { 1136169689Skan error ("loop %d's header does not belong directly to it", i); 1137117395Skan err = 1; 1138117395Skan } 1139132718Skan if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 1140132718Skan && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) 1141132718Skan { 1142169689Skan error ("loop %d's latch is marked as part of irreducible region", i); 1143132718Skan err = 1; 1144132718Skan } 1145117395Skan } 1146117395Skan 1147132718Skan /* Check irreducible loops. */ 1148132718Skan if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 1149132718Skan { 1150132718Skan /* Record old info. */ 1151132718Skan irreds = sbitmap_alloc (last_basic_block); 1152132718Skan FOR_EACH_BB (bb) 1153132718Skan { 1154169689Skan edge_iterator ei; 1155132718Skan if (bb->flags & BB_IRREDUCIBLE_LOOP) 1156132718Skan SET_BIT (irreds, bb->index); 1157132718Skan else 1158132718Skan RESET_BIT (irreds, bb->index); 1159169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1160132718Skan if (e->flags & EDGE_IRREDUCIBLE_LOOP) 1161132718Skan e->flags |= EDGE_ALL_FLAGS + 1; 1162132718Skan } 1163132718Skan 1164132718Skan /* Recount it. */ 1165132718Skan mark_irreducible_loops (loops); 1166132718Skan 1167132718Skan /* Compare. */ 1168132718Skan FOR_EACH_BB (bb) 1169132718Skan { 1170169689Skan edge_iterator ei; 1171169689Skan 1172132718Skan if ((bb->flags & BB_IRREDUCIBLE_LOOP) 1173132718Skan && !TEST_BIT (irreds, bb->index)) 1174132718Skan { 1175169689Skan error ("basic block %d should be marked irreducible", bb->index); 1176132718Skan err = 1; 1177132718Skan } 1178132718Skan else if (!(bb->flags & BB_IRREDUCIBLE_LOOP) 1179132718Skan && TEST_BIT (irreds, bb->index)) 1180132718Skan { 1181169689Skan error ("basic block %d should not be marked irreducible", bb->index); 1182132718Skan err = 1; 1183132718Skan } 1184169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1185132718Skan { 1186132718Skan if ((e->flags & EDGE_IRREDUCIBLE_LOOP) 1187132718Skan && !(e->flags & (EDGE_ALL_FLAGS + 1))) 1188132718Skan { 1189169689Skan error ("edge from %d to %d should be marked irreducible", 1190132718Skan e->src->index, e->dest->index); 1191132718Skan err = 1; 1192132718Skan } 1193132718Skan else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) 1194132718Skan && (e->flags & (EDGE_ALL_FLAGS + 1))) 1195132718Skan { 1196169689Skan error ("edge from %d to %d should not be marked irreducible", 1197132718Skan e->src->index, e->dest->index); 1198132718Skan err = 1; 1199132718Skan } 1200132718Skan e->flags &= ~(EDGE_ALL_FLAGS + 1); 1201132718Skan } 1202132718Skan } 1203132718Skan free (irreds); 1204132718Skan } 1205132718Skan 1206169689Skan /* Check the single_exit. */ 1207169689Skan if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) 1208169689Skan { 1209169689Skan memset (sizes, 0, sizeof (unsigned) * loops->num); 1210169689Skan FOR_EACH_BB (bb) 1211169689Skan { 1212169689Skan edge_iterator ei; 1213169689Skan if (bb->loop_father == loops->tree_root) 1214169689Skan continue; 1215169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1216169689Skan { 1217169689Skan if (e->dest == EXIT_BLOCK_PTR) 1218169689Skan continue; 1219169689Skan 1220169689Skan if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) 1221169689Skan continue; 1222169689Skan 1223169689Skan for (loop = bb->loop_father; 1224169689Skan loop != e->dest->loop_father; 1225169689Skan loop = loop->outer) 1226169689Skan { 1227169689Skan sizes[loop->num]++; 1228169689Skan if (loop->single_exit 1229169689Skan && loop->single_exit != e) 1230169689Skan { 1231169689Skan error ("wrong single exit %d->%d recorded for loop %d", 1232169689Skan loop->single_exit->src->index, 1233169689Skan loop->single_exit->dest->index, 1234169689Skan loop->num); 1235169689Skan error ("right exit is %d->%d", 1236169689Skan e->src->index, e->dest->index); 1237169689Skan err = 1; 1238169689Skan } 1239169689Skan } 1240169689Skan } 1241169689Skan } 1242169689Skan 1243169689Skan for (i = 1; i < loops->num; i++) 1244169689Skan { 1245169689Skan loop = loops->parray[i]; 1246169689Skan if (!loop) 1247169689Skan continue; 1248169689Skan 1249169689Skan if (sizes[i] == 1 1250169689Skan && !loop->single_exit) 1251169689Skan { 1252169689Skan error ("single exit not recorded for loop %d", loop->num); 1253169689Skan err = 1; 1254169689Skan } 1255169689Skan 1256169689Skan if (sizes[i] != 1 1257169689Skan && loop->single_exit) 1258169689Skan { 1259169689Skan error ("loop %d should not have single exit (%d -> %d)", 1260169689Skan loop->num, 1261169689Skan loop->single_exit->src->index, 1262169689Skan loop->single_exit->dest->index); 1263169689Skan err = 1; 1264169689Skan } 1265169689Skan } 1266169689Skan } 1267169689Skan 1268169689Skan gcc_assert (!err); 1269169689Skan 1270169689Skan free (sizes); 1271117395Skan} 1272117395Skan 1273117395Skan/* Returns latch edge of LOOP. */ 1274117395Skanedge 1275132718Skanloop_latch_edge (const struct loop *loop) 1276117395Skan{ 1277169689Skan return find_edge (loop->latch, loop->header); 1278117395Skan} 1279117395Skan 1280117395Skan/* Returns preheader edge of LOOP. */ 1281117395Skanedge 1282132718Skanloop_preheader_edge (const struct loop *loop) 1283117395Skan{ 1284117395Skan edge e; 1285169689Skan edge_iterator ei; 1286117395Skan 1287169689Skan FOR_EACH_EDGE (e, ei, loop->header->preds) 1288169689Skan if (e->src != loop->latch) 1289169689Skan break; 1290117395Skan 1291117395Skan return e; 1292117395Skan} 1293169689Skan 1294169689Skan/* Returns true if E is an exit of LOOP. */ 1295169689Skan 1296169689Skanbool 1297169689Skanloop_exit_edge_p (const struct loop *loop, edge e) 1298169689Skan{ 1299169689Skan return (flow_bb_inside_loop_p (loop, e->src) 1300169689Skan && !flow_bb_inside_loop_p (loop, e->dest)); 1301169689Skan} 1302