190075Sobrien/* Basic block reordering routines for the 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 "tree.h" 2690075Sobrien#include "rtl.h" 2790075Sobrien#include "hard-reg-set.h" 28169689Skan#include "obstack.h" 2990075Sobrien#include "basic-block.h" 3090075Sobrien#include "insn-config.h" 3190075Sobrien#include "output.h" 3290075Sobrien#include "function.h" 3390075Sobrien#include "cfglayout.h" 34132718Skan#include "cfgloop.h" 35132718Skan#include "target.h" 36132718Skan#include "ggc.h" 37132718Skan#include "alloc-pool.h" 38169689Skan#include "flags.h" 39169689Skan#include "tree-pass.h" 40169689Skan#include "vecprim.h" 4190075Sobrien 4290075Sobrien/* Holds the interesting trailing notes for the function. */ 43132718Skanrtx cfg_layout_function_footer, cfg_layout_function_header; 4490075Sobrien 45132718Skanstatic rtx skip_insns_after_block (basic_block); 46132718Skanstatic void record_effective_endpoints (void); 47132718Skanstatic rtx label_for_bb (basic_block); 48132718Skanstatic void fixup_reorder_chain (void); 4990075Sobrien 50132718Skanstatic void set_block_levels (tree, int); 51132718Skanstatic void change_scope (rtx, tree, tree); 5290075Sobrien 53132718Skanvoid verify_insn_chain (void); 54132718Skanstatic void fixup_fallthru_exit_predecessor (void); 55132718Skanstatic tree insn_scope (rtx); 56117395Skan 57132718Skanrtx 58132718Skanunlink_insn_chain (rtx first, rtx last) 59117395Skan{ 60117395Skan rtx prevfirst = PREV_INSN (first); 61117395Skan rtx nextlast = NEXT_INSN (last); 6290075Sobrien 63117395Skan PREV_INSN (first) = NULL; 64117395Skan NEXT_INSN (last) = NULL; 65117395Skan if (prevfirst) 66117395Skan NEXT_INSN (prevfirst) = nextlast; 67117395Skan if (nextlast) 68117395Skan PREV_INSN (nextlast) = prevfirst; 69117395Skan else 70117395Skan set_last_insn (prevfirst); 71117395Skan if (!prevfirst) 72117395Skan set_first_insn (nextlast); 73117395Skan return first; 74117395Skan} 7590075Sobrien 7690075Sobrien/* Skip over inter-block insns occurring after BB which are typically 7790075Sobrien associated with BB (e.g., barriers). If there are any such insns, 7890075Sobrien we return the last one. Otherwise, we return the end of BB. */ 7990075Sobrien 8090075Sobrienstatic rtx 81132718Skanskip_insns_after_block (basic_block bb) 8290075Sobrien{ 8390075Sobrien rtx insn, last_insn, next_head, prev; 8490075Sobrien 8590075Sobrien next_head = NULL_RTX; 86117395Skan if (bb->next_bb != EXIT_BLOCK_PTR) 87132718Skan next_head = BB_HEAD (bb->next_bb); 8890075Sobrien 89132718Skan for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; ) 9090075Sobrien { 9190075Sobrien if (insn == next_head) 9290075Sobrien break; 9390075Sobrien 9490075Sobrien switch (GET_CODE (insn)) 9590075Sobrien { 9690075Sobrien case BARRIER: 9790075Sobrien last_insn = insn; 9890075Sobrien continue; 9990075Sobrien 10090075Sobrien case NOTE: 10190075Sobrien switch (NOTE_LINE_NUMBER (insn)) 10290075Sobrien { 10390075Sobrien case NOTE_INSN_BLOCK_END: 10490075Sobrien last_insn = insn; 10590075Sobrien continue; 10690075Sobrien case NOTE_INSN_DELETED: 10790075Sobrien case NOTE_INSN_DELETED_LABEL: 10890075Sobrien continue; 10990075Sobrien 11090075Sobrien default: 11190075Sobrien continue; 11290075Sobrien break; 11390075Sobrien } 11490075Sobrien break; 11590075Sobrien 11690075Sobrien case CODE_LABEL: 11790075Sobrien if (NEXT_INSN (insn) 118169689Skan && JUMP_P (NEXT_INSN (insn)) 11990075Sobrien && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC 120169689Skan || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC)) 12190075Sobrien { 12290075Sobrien insn = NEXT_INSN (insn); 12390075Sobrien last_insn = insn; 12490075Sobrien continue; 12590075Sobrien } 126117395Skan break; 12790075Sobrien 12890075Sobrien default: 12990075Sobrien break; 13090075Sobrien } 13190075Sobrien 13290075Sobrien break; 13390075Sobrien } 13490075Sobrien 13590075Sobrien /* It is possible to hit contradictory sequence. For instance: 136117395Skan 13790075Sobrien jump_insn 138169689Skan NOTE_INSN_BLOCK_BEG 13990075Sobrien barrier 14090075Sobrien 14190075Sobrien Where barrier belongs to jump_insn, but the note does not. This can be 14290075Sobrien created by removing the basic block originally following 143169689Skan NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */ 14490075Sobrien 145132718Skan for (insn = last_insn; insn != BB_END (bb); insn = prev) 14690075Sobrien { 14790075Sobrien prev = PREV_INSN (insn); 148169689Skan if (NOTE_P (insn)) 14990075Sobrien switch (NOTE_LINE_NUMBER (insn)) 15090075Sobrien { 151117395Skan case NOTE_INSN_BLOCK_END: 152117395Skan case NOTE_INSN_DELETED: 153117395Skan case NOTE_INSN_DELETED_LABEL: 15490075Sobrien continue; 155117395Skan default: 15690075Sobrien reorder_insns (insn, insn, last_insn); 157117395Skan } 15890075Sobrien } 15990075Sobrien 16090075Sobrien return last_insn; 16190075Sobrien} 16290075Sobrien 16390075Sobrien/* Locate or create a label for a given basic block. */ 16490075Sobrien 16590075Sobrienstatic rtx 166132718Skanlabel_for_bb (basic_block bb) 16790075Sobrien{ 168132718Skan rtx label = BB_HEAD (bb); 16990075Sobrien 170169689Skan if (!LABEL_P (label)) 17190075Sobrien { 172169689Skan if (dump_file) 173169689Skan fprintf (dump_file, "Emitting label for block %d\n", bb->index); 17490075Sobrien 17590075Sobrien label = block_label (bb); 17690075Sobrien } 17790075Sobrien 17890075Sobrien return label; 17990075Sobrien} 18090075Sobrien 18190075Sobrien/* Locate the effective beginning and end of the insn chain for each 18290075Sobrien block, as defined by skip_insns_after_block above. */ 18390075Sobrien 18490075Sobrienstatic void 185132718Skanrecord_effective_endpoints (void) 18690075Sobrien{ 187132718Skan rtx next_insn; 188117395Skan basic_block bb; 189132718Skan rtx insn; 190117395Skan 191132718Skan for (insn = get_insns (); 192132718Skan insn 193169689Skan && NOTE_P (insn) 194132718Skan && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK; 195132718Skan insn = NEXT_INSN (insn)) 196132718Skan continue; 197169689Skan /* No basic blocks at all? */ 198169689Skan gcc_assert (insn); 199169689Skan 200132718Skan if (PREV_INSN (insn)) 201132718Skan cfg_layout_function_header = 202132718Skan unlink_insn_chain (get_insns (), PREV_INSN (insn)); 203132718Skan else 204132718Skan cfg_layout_function_header = NULL_RTX; 205132718Skan 206132718Skan next_insn = get_insns (); 207117395Skan FOR_EACH_BB (bb) 20890075Sobrien { 20990075Sobrien rtx end; 21090075Sobrien 211132718Skan if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb)) 212169689Skan bb->il.rtl->header = unlink_insn_chain (next_insn, 213132718Skan PREV_INSN (BB_HEAD (bb))); 21490075Sobrien end = skip_insns_after_block (bb); 215132718Skan if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end) 216169689Skan bb->il.rtl->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end); 217132718Skan next_insn = NEXT_INSN (BB_END (bb)); 21890075Sobrien } 21990075Sobrien 220132718Skan cfg_layout_function_footer = next_insn; 221132718Skan if (cfg_layout_function_footer) 222132718Skan cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ()); 22390075Sobrien} 22490075Sobrien 225132718Skan/* Data structures representing mapping of INSN_LOCATOR into scope blocks, line 226132718Skan numbers and files. In order to be GGC friendly we need to use separate 227132718Skan varrays. This also slightly improve the memory locality in binary search. 228132718Skan The _locs array contains locators where the given property change. The 229132718Skan block_locators_blocks contains the scope block that is used for all insn 230132718Skan locator greater than corresponding block_locators_locs value and smaller 231132718Skan than the following one. Similarly for the other properties. */ 232169689Skanstatic VEC(int,heap) *block_locators_locs; 233169689Skanstatic GTY(()) VEC(tree,gc) *block_locators_blocks; 234169689Skanstatic VEC(int,heap) *line_locators_locs; 235169689Skanstatic VEC(int,heap) *line_locators_lines; 236169689Skanstatic VEC(int,heap) *file_locators_locs; 237132718Skanstatic GTY(()) varray_type file_locators_files; 238132718Skanint prologue_locator; 239132718Skanint epilogue_locator; 24090075Sobrien 241132718Skan/* During the RTL expansion the lexical blocks and line numbers are 242132718Skan represented via INSN_NOTEs. Replace them by representation using 243132718Skan INSN_LOCATORs. */ 244132718Skan 245169689Skanunsigned int 246132718Skaninsn_locators_initialize (void) 24790075Sobrien{ 24890075Sobrien tree block = NULL; 249132718Skan tree last_block = NULL; 25090075Sobrien rtx insn, next; 251132718Skan int loc = 0; 252132718Skan int line_number = 0, last_line_number = 0; 253169689Skan const char *file_name = NULL, *last_file_name = NULL; 25490075Sobrien 255132718Skan prologue_locator = epilogue_locator = 0; 256132718Skan 257169689Skan block_locators_locs = VEC_alloc (int, heap, 32); 258169689Skan block_locators_blocks = VEC_alloc (tree, gc, 32); 259169689Skan line_locators_locs = VEC_alloc (int, heap, 32); 260169689Skan line_locators_lines = VEC_alloc (int, heap, 32); 261169689Skan file_locators_locs = VEC_alloc (int, heap, 32); 262132718Skan VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files"); 263132718Skan 26490075Sobrien for (insn = get_insns (); insn; insn = next) 26590075Sobrien { 266169689Skan int active = 0; 267169689Skan 26890075Sobrien next = NEXT_INSN (insn); 26990075Sobrien 270169689Skan if (NOTE_P (insn)) 271169689Skan { 272169689Skan gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_BEG 273169689Skan && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END); 274169689Skan if (NOTE_LINE_NUMBER (insn) > 0) 275169689Skan { 276169689Skan expanded_location xloc; 277169689Skan NOTE_EXPANDED_LOCATION (xloc, insn); 278169689Skan line_number = xloc.line; 279169689Skan file_name = xloc.file; 280169689Skan } 281169689Skan } 282169689Skan else 283169689Skan active = (active_insn_p (insn) 284169689Skan && GET_CODE (PATTERN (insn)) != ADDR_VEC 285169689Skan && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); 286169689Skan 287169689Skan check_block_change (insn, &block); 288169689Skan 289169689Skan if (active 290169689Skan || !next 291132718Skan || (!prologue_locator && file_name)) 292132718Skan { 293132718Skan if (last_block != block) 294132718Skan { 295132718Skan loc++; 296169689Skan VEC_safe_push (int, heap, block_locators_locs, loc); 297169689Skan VEC_safe_push (tree, gc, block_locators_blocks, block); 298132718Skan last_block = block; 299132718Skan } 300132718Skan if (last_line_number != line_number) 301132718Skan { 302132718Skan loc++; 303169689Skan VEC_safe_push (int, heap, line_locators_locs, loc); 304169689Skan VEC_safe_push (int, heap, line_locators_lines, line_number); 305132718Skan last_line_number = line_number; 306132718Skan } 307132718Skan if (last_file_name != file_name) 308132718Skan { 309132718Skan loc++; 310169689Skan VEC_safe_push (int, heap, file_locators_locs, loc); 311169689Skan VARRAY_PUSH_CHAR_PTR (file_locators_files, (char *) file_name); 312132718Skan last_file_name = file_name; 313132718Skan } 314169689Skan if (!prologue_locator && file_name) 315169689Skan prologue_locator = loc; 316169689Skan if (!next) 317169689Skan epilogue_locator = loc; 318169689Skan if (active) 319169689Skan INSN_LOCATOR (insn) = loc; 320132718Skan } 32190075Sobrien } 322117395Skan 323117395Skan /* Tag the blocks with a depth number so that change_scope can find 324117395Skan the common parent easily. */ 325117395Skan set_block_levels (DECL_INITIAL (cfun->decl), 0); 326169689Skan 327169689Skan free_block_changes (); 328169689Skan return 0; 32990075Sobrien} 33090075Sobrien 331169689Skanstruct tree_opt_pass pass_insn_locators_initialize = 332169689Skan{ 333169689Skan "locators", /* name */ 334169689Skan NULL, /* gate */ 335169689Skan insn_locators_initialize, /* execute */ 336169689Skan NULL, /* sub */ 337169689Skan NULL, /* next */ 338169689Skan 0, /* static_pass_number */ 339169689Skan 0, /* tv_id */ 340169689Skan 0, /* properties_required */ 341169689Skan 0, /* properties_provided */ 342169689Skan 0, /* properties_destroyed */ 343169689Skan 0, /* todo_flags_start */ 344169689Skan TODO_dump_func, /* todo_flags_finish */ 345169689Skan 0 /* letter */ 346169689Skan}; 347169689Skan 348169689Skan 34990075Sobrien/* For each lexical block, set BLOCK_NUMBER to the depth at which it is 35090075Sobrien found in the block tree. */ 35190075Sobrien 35290075Sobrienstatic void 353132718Skanset_block_levels (tree block, int level) 35490075Sobrien{ 35590075Sobrien while (block) 35690075Sobrien { 35790075Sobrien BLOCK_NUMBER (block) = level; 35890075Sobrien set_block_levels (BLOCK_SUBBLOCKS (block), level + 1); 35990075Sobrien block = BLOCK_CHAIN (block); 36090075Sobrien } 36190075Sobrien} 362117395Skan 363117395Skan/* Return sope resulting from combination of S1 and S2. */ 364169689Skanstatic tree 365132718Skanchoose_inner_scope (tree s1, tree s2) 366117395Skan{ 367117395Skan if (!s1) 368117395Skan return s2; 369117395Skan if (!s2) 370117395Skan return s1; 371117395Skan if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2)) 372117395Skan return s1; 373117395Skan return s2; 374117395Skan} 375117395Skan 37690075Sobrien/* Emit lexical block notes needed to change scope from S1 to S2. */ 37790075Sobrien 37890075Sobrienstatic void 379132718Skanchange_scope (rtx orig_insn, tree s1, tree s2) 38090075Sobrien{ 38190075Sobrien rtx insn = orig_insn; 38290075Sobrien tree com = NULL_TREE; 38390075Sobrien tree ts1 = s1, ts2 = s2; 38490075Sobrien tree s; 38590075Sobrien 38690075Sobrien while (ts1 != ts2) 38790075Sobrien { 388169689Skan gcc_assert (ts1 && ts2); 38990075Sobrien if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2)) 39090075Sobrien ts1 = BLOCK_SUPERCONTEXT (ts1); 39190075Sobrien else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2)) 39290075Sobrien ts2 = BLOCK_SUPERCONTEXT (ts2); 39390075Sobrien else 39490075Sobrien { 39590075Sobrien ts1 = BLOCK_SUPERCONTEXT (ts1); 39690075Sobrien ts2 = BLOCK_SUPERCONTEXT (ts2); 39790075Sobrien } 39890075Sobrien } 39990075Sobrien com = ts1; 40090075Sobrien 40190075Sobrien /* Close scopes. */ 40290075Sobrien s = s1; 40390075Sobrien while (s != com) 40490075Sobrien { 40590075Sobrien rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn); 40690075Sobrien NOTE_BLOCK (note) = s; 40790075Sobrien s = BLOCK_SUPERCONTEXT (s); 40890075Sobrien } 40990075Sobrien 41090075Sobrien /* Open scopes. */ 41190075Sobrien s = s2; 41290075Sobrien while (s != com) 41390075Sobrien { 41490075Sobrien insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn); 41590075Sobrien NOTE_BLOCK (insn) = s; 41690075Sobrien s = BLOCK_SUPERCONTEXT (s); 41790075Sobrien } 41890075Sobrien} 41990075Sobrien 420132718Skan/* Return lexical scope block insn belong to. */ 421132718Skanstatic tree 422132718Skaninsn_scope (rtx insn) 423132718Skan{ 424169689Skan int max = VEC_length (int, block_locators_locs); 425132718Skan int min = 0; 426132718Skan int loc = INSN_LOCATOR (insn); 427132718Skan 428132718Skan /* When block_locators_locs was initialized, the pro- and epilogue 429132718Skan insns didn't exist yet and can therefore not be found this way. 430132718Skan But we know that they belong to the outer most block of the 431132718Skan current function. 432132718Skan Without this test, the prologue would be put inside the block of 433132718Skan the first valid instruction in the function and when that first 434132718Skan insn is part of an inlined function then the low_pc of that 435132718Skan inlined function is messed up. Likewise for the epilogue and 436132718Skan the last valid instruction. */ 437132718Skan if (loc == prologue_locator || loc == epilogue_locator) 438132718Skan return DECL_INITIAL (cfun->decl); 439132718Skan 440132718Skan if (!max || !loc) 441132718Skan return NULL; 442132718Skan while (1) 443132718Skan { 444132718Skan int pos = (min + max) / 2; 445169689Skan int tmp = VEC_index (int, block_locators_locs, pos); 446132718Skan 447132718Skan if (tmp <= loc && min != pos) 448132718Skan min = pos; 449132718Skan else if (tmp > loc && max != pos) 450132718Skan max = pos; 451132718Skan else 452132718Skan { 453132718Skan min = pos; 454132718Skan break; 455132718Skan } 456132718Skan } 457169689Skan return VEC_index (tree, block_locators_blocks, min); 458132718Skan} 459132718Skan 460132718Skan/* Return line number of the statement specified by the locator. */ 461132718Skanint 462132718Skanlocator_line (int loc) 463132718Skan{ 464169689Skan int max = VEC_length (int, line_locators_locs); 465132718Skan int min = 0; 466132718Skan 467132718Skan if (!max || !loc) 468132718Skan return 0; 469132718Skan while (1) 470132718Skan { 471132718Skan int pos = (min + max) / 2; 472169689Skan int tmp = VEC_index (int, line_locators_locs, pos); 473132718Skan 474132718Skan if (tmp <= loc && min != pos) 475132718Skan min = pos; 476132718Skan else if (tmp > loc && max != pos) 477132718Skan max = pos; 478132718Skan else 479132718Skan { 480132718Skan min = pos; 481132718Skan break; 482132718Skan } 483132718Skan } 484169689Skan return VEC_index (int, line_locators_lines, min); 485132718Skan} 486132718Skan 487132718Skan/* Return line number of the statement that produced this insn. */ 488132718Skanint 489132718Skaninsn_line (rtx insn) 490132718Skan{ 491132718Skan return locator_line (INSN_LOCATOR (insn)); 492132718Skan} 493132718Skan 494132718Skan/* Return source file of the statement specified by LOC. */ 495132718Skanconst char * 496132718Skanlocator_file (int loc) 497132718Skan{ 498169689Skan int max = VEC_length (int, file_locators_locs); 499132718Skan int min = 0; 500132718Skan 501132718Skan if (!max || !loc) 502132718Skan return NULL; 503132718Skan while (1) 504132718Skan { 505132718Skan int pos = (min + max) / 2; 506169689Skan int tmp = VEC_index (int, file_locators_locs, pos); 507132718Skan 508132718Skan if (tmp <= loc && min != pos) 509132718Skan min = pos; 510132718Skan else if (tmp > loc && max != pos) 511132718Skan max = pos; 512132718Skan else 513132718Skan { 514132718Skan min = pos; 515132718Skan break; 516132718Skan } 517132718Skan } 518132718Skan return VARRAY_CHAR_PTR (file_locators_files, min); 519132718Skan} 520132718Skan 521132718Skan/* Return source file of the statement that produced this insn. */ 522132718Skanconst char * 523132718Skaninsn_file (rtx insn) 524132718Skan{ 525132718Skan return locator_file (INSN_LOCATOR (insn)); 526132718Skan} 527132718Skan 52890075Sobrien/* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based 52990075Sobrien on the scope tree and the newly reordered instructions. */ 53090075Sobrien 53190075Sobrienvoid 532132718Skanreemit_insn_block_notes (void) 53390075Sobrien{ 53490075Sobrien tree cur_block = DECL_INITIAL (cfun->decl); 53590075Sobrien rtx insn, note; 53690075Sobrien 537117395Skan insn = get_insns (); 538117395Skan if (!active_insn_p (insn)) 539117395Skan insn = next_active_insn (insn); 540117395Skan for (; insn; insn = next_active_insn (insn)) 54190075Sobrien { 54290075Sobrien tree this_block; 54390075Sobrien 544169689Skan /* Avoid putting scope notes between jump table and its label. */ 545169689Skan if (JUMP_P (insn) 546169689Skan && (GET_CODE (PATTERN (insn)) == ADDR_VEC 547169689Skan || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) 548169689Skan continue; 549169689Skan 550132718Skan this_block = insn_scope (insn); 551117395Skan /* For sequences compute scope resulting from merging all scopes 552169689Skan of instructions nested inside. */ 553117395Skan if (GET_CODE (PATTERN (insn)) == SEQUENCE) 554117395Skan { 555117395Skan int i; 556117395Skan rtx body = PATTERN (insn); 557117395Skan 558117395Skan this_block = NULL; 559117395Skan for (i = 0; i < XVECLEN (body, 0); i++) 560117395Skan this_block = choose_inner_scope (this_block, 561132718Skan insn_scope (XVECEXP (body, 0, i))); 562117395Skan } 56390075Sobrien if (! this_block) 56490075Sobrien continue; 56590075Sobrien 56690075Sobrien if (this_block != cur_block) 56790075Sobrien { 56890075Sobrien change_scope (insn, cur_block, this_block); 56990075Sobrien cur_block = this_block; 57090075Sobrien } 57190075Sobrien } 57290075Sobrien 57390075Sobrien /* change_scope emits before the insn, not after. */ 574132718Skan note = emit_note (NOTE_INSN_DELETED); 57590075Sobrien change_scope (note, cur_block, DECL_INITIAL (cfun->decl)); 57690075Sobrien delete_insn (note); 57790075Sobrien 57890075Sobrien reorder_blocks (); 57990075Sobrien} 58090075Sobrien 58190075Sobrien/* Given a reorder chain, rearrange the code to match. */ 58290075Sobrien 58390075Sobrienstatic void 584132718Skanfixup_reorder_chain (void) 58590075Sobrien{ 586117395Skan basic_block bb, prev_bb; 58790075Sobrien int index; 588117395Skan rtx insn = NULL; 58990075Sobrien 590132718Skan if (cfg_layout_function_header) 591132718Skan { 592132718Skan set_first_insn (cfg_layout_function_header); 593132718Skan insn = cfg_layout_function_header; 594132718Skan while (NEXT_INSN (insn)) 595132718Skan insn = NEXT_INSN (insn); 596132718Skan } 597132718Skan 59890075Sobrien /* First do the bulk reordering -- rechain the blocks without regard to 59990075Sobrien the needed changes to jumps and labels. */ 60090075Sobrien 601169689Skan for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS; 60290075Sobrien bb != 0; 603169689Skan bb = bb->aux, index++) 60490075Sobrien { 605169689Skan if (bb->il.rtl->header) 606117395Skan { 607117395Skan if (insn) 608169689Skan NEXT_INSN (insn) = bb->il.rtl->header; 609117395Skan else 610169689Skan set_first_insn (bb->il.rtl->header); 611169689Skan PREV_INSN (bb->il.rtl->header) = insn; 612169689Skan insn = bb->il.rtl->header; 613117395Skan while (NEXT_INSN (insn)) 614117395Skan insn = NEXT_INSN (insn); 615117395Skan } 616117395Skan if (insn) 617132718Skan NEXT_INSN (insn) = BB_HEAD (bb); 618117395Skan else 619132718Skan set_first_insn (BB_HEAD (bb)); 620132718Skan PREV_INSN (BB_HEAD (bb)) = insn; 621132718Skan insn = BB_END (bb); 622169689Skan if (bb->il.rtl->footer) 623117395Skan { 624169689Skan NEXT_INSN (insn) = bb->il.rtl->footer; 625169689Skan PREV_INSN (bb->il.rtl->footer) = insn; 626117395Skan while (NEXT_INSN (insn)) 627117395Skan insn = NEXT_INSN (insn); 628117395Skan } 62990075Sobrien } 63090075Sobrien 631169689Skan gcc_assert (index == n_basic_blocks); 63290075Sobrien 633132718Skan NEXT_INSN (insn) = cfg_layout_function_footer; 634132718Skan if (cfg_layout_function_footer) 635132718Skan PREV_INSN (cfg_layout_function_footer) = insn; 63690075Sobrien 63790075Sobrien while (NEXT_INSN (insn)) 63890075Sobrien insn = NEXT_INSN (insn); 63990075Sobrien 64090075Sobrien set_last_insn (insn); 64190075Sobrien#ifdef ENABLE_CHECKING 64290075Sobrien verify_insn_chain (); 64390075Sobrien#endif 644132718Skan delete_dead_jumptables (); 64590075Sobrien 64690075Sobrien /* Now add jumps and labels as needed to match the blocks new 64790075Sobrien outgoing edges. */ 64890075Sobrien 649169689Skan for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->aux) 65090075Sobrien { 65190075Sobrien edge e_fall, e_taken, e; 65290075Sobrien rtx bb_end_insn; 65390075Sobrien basic_block nb; 654169689Skan edge_iterator ei; 65590075Sobrien 656169689Skan if (EDGE_COUNT (bb->succs) == 0) 65790075Sobrien continue; 65890075Sobrien 65990075Sobrien /* Find the old fallthru edge, and another non-EH edge for 66090075Sobrien a taken jump. */ 66190075Sobrien e_taken = e_fall = NULL; 662169689Skan 663169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 66490075Sobrien if (e->flags & EDGE_FALLTHRU) 66590075Sobrien e_fall = e; 66690075Sobrien else if (! (e->flags & EDGE_EH)) 66790075Sobrien e_taken = e; 66890075Sobrien 669132718Skan bb_end_insn = BB_END (bb); 670169689Skan if (JUMP_P (bb_end_insn)) 67190075Sobrien { 67290075Sobrien if (any_condjump_p (bb_end_insn)) 67390075Sobrien { 67490075Sobrien /* If the old fallthru is still next, nothing to do. */ 675169689Skan if (bb->aux == e_fall->dest 676169689Skan || e_fall->dest == EXIT_BLOCK_PTR) 67790075Sobrien continue; 67890075Sobrien 679117395Skan /* The degenerated case of conditional jump jumping to the next 680169689Skan instruction can happen for jumps with side effects. We need 681169689Skan to construct a forwarder block and this will be done just 682169689Skan fine by force_nonfallthru below. */ 683117395Skan if (!e_taken) 684169689Skan ; 685117395Skan 686169689Skan /* There is another special case: if *neither* block is next, 68790075Sobrien such as happens at the very end of a function, then we'll 68890075Sobrien need to add a new unconditional jump. Choose the taken 68990075Sobrien edge based on known or assumed probability. */ 690169689Skan else if (bb->aux != e_taken->dest) 69190075Sobrien { 69290075Sobrien rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0); 69390075Sobrien 69490075Sobrien if (note 69590075Sobrien && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2 69690075Sobrien && invert_jump (bb_end_insn, 697169689Skan (e_fall->dest == EXIT_BLOCK_PTR 698169689Skan ? NULL_RTX 699169689Skan : label_for_bb (e_fall->dest)), 0)) 70090075Sobrien { 70190075Sobrien e_fall->flags &= ~EDGE_FALLTHRU; 702169689Skan#ifdef ENABLE_CHECKING 703169689Skan gcc_assert (could_fall_through 704169689Skan (e_taken->src, e_taken->dest)); 705169689Skan#endif 70690075Sobrien e_taken->flags |= EDGE_FALLTHRU; 70790075Sobrien update_br_prob_note (bb); 70890075Sobrien e = e_fall, e_fall = e_taken, e_taken = e; 70990075Sobrien } 71090075Sobrien } 71190075Sobrien 712169689Skan /* If the "jumping" edge is a crossing edge, and the fall 713169689Skan through edge is non-crossing, leave things as they are. */ 714169689Skan else if ((e_taken->flags & EDGE_CROSSING) 715169689Skan && !(e_fall->flags & EDGE_CROSSING)) 716169689Skan continue; 717169689Skan 718117395Skan /* Otherwise we can try to invert the jump. This will 71990075Sobrien basically never fail, however, keep up the pretense. */ 72090075Sobrien else if (invert_jump (bb_end_insn, 721169689Skan (e_fall->dest == EXIT_BLOCK_PTR 722169689Skan ? NULL_RTX 723169689Skan : label_for_bb (e_fall->dest)), 0)) 72490075Sobrien { 72590075Sobrien e_fall->flags &= ~EDGE_FALLTHRU; 726169689Skan#ifdef ENABLE_CHECKING 727169689Skan gcc_assert (could_fall_through 728169689Skan (e_taken->src, e_taken->dest)); 729169689Skan#endif 73090075Sobrien e_taken->flags |= EDGE_FALLTHRU; 73190075Sobrien update_br_prob_note (bb); 73290075Sobrien continue; 73390075Sobrien } 73490075Sobrien } 73590075Sobrien else 73690075Sobrien { 737169689Skan /* Otherwise we have some return, switch or computed 738169689Skan jump. In the 99% case, there should not have been a 739169689Skan fallthru edge. */ 740169689Skan gcc_assert (returnjump_p (bb_end_insn) || !e_fall); 741169689Skan continue; 74290075Sobrien } 74390075Sobrien } 74490075Sobrien else 74590075Sobrien { 74690075Sobrien /* No fallthru implies a noreturn function with EH edges, or 74790075Sobrien something similarly bizarre. In any case, we don't need to 74890075Sobrien do anything. */ 74990075Sobrien if (! e_fall) 75090075Sobrien continue; 75190075Sobrien 75290075Sobrien /* If the fallthru block is still next, nothing to do. */ 753169689Skan if (bb->aux == e_fall->dest) 75490075Sobrien continue; 75590075Sobrien 75690075Sobrien /* A fallthru to exit block. */ 757169689Skan if (e_fall->dest == EXIT_BLOCK_PTR) 75890075Sobrien continue; 75990075Sobrien } 76090075Sobrien 76190075Sobrien /* We got here if we need to add a new jump insn. */ 76290075Sobrien nb = force_nonfallthru (e_fall); 76390075Sobrien if (nb) 76490075Sobrien { 765169689Skan nb->il.rtl->visited = 1; 766169689Skan nb->aux = bb->aux; 767169689Skan bb->aux = nb; 76890075Sobrien /* Don't process this new block. */ 76990075Sobrien bb = nb; 770169689Skan 771169689Skan /* Make sure new bb is tagged for correct section (same as 772169689Skan fall-thru source, since you cannot fall-throu across 773169689Skan section boundaries). */ 774169689Skan BB_COPY_PARTITION (e_fall->src, single_pred (bb)); 775169689Skan if (flag_reorder_blocks_and_partition 776169689Skan && targetm.have_named_sections 777169689Skan && JUMP_P (BB_END (bb)) 778169689Skan && !any_condjump_p (BB_END (bb)) 779169689Skan && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING)) 780169689Skan REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST 781169689Skan (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb))); 78290075Sobrien } 78390075Sobrien } 78490075Sobrien 78590075Sobrien /* Put basic_block_info in the new order. */ 78690075Sobrien 787169689Skan if (dump_file) 788117395Skan { 789169689Skan fprintf (dump_file, "Reordered sequence:\n"); 790169689Skan for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS; 791169689Skan bb; 792169689Skan bb = bb->aux, index++) 793117395Skan { 794169689Skan fprintf (dump_file, " %i ", index); 795169689Skan if (get_bb_original (bb)) 796169689Skan fprintf (dump_file, "duplicate of %i ", 797169689Skan get_bb_original (bb)->index); 798169689Skan else if (forwarder_block_p (bb) 799169689Skan && !LABEL_P (BB_HEAD (bb))) 800169689Skan fprintf (dump_file, "compensation "); 801117395Skan else 802169689Skan fprintf (dump_file, "bb %i ", bb->index); 803169689Skan fprintf (dump_file, " [%i]\n", bb->frequency); 804117395Skan } 805117395Skan } 80690075Sobrien 807117395Skan prev_bb = ENTRY_BLOCK_PTR; 808117395Skan bb = ENTRY_BLOCK_PTR->next_bb; 809169689Skan index = NUM_FIXED_BLOCKS; 810117395Skan 811169689Skan for (; bb; prev_bb = bb, bb = bb->aux, index ++) 81290075Sobrien { 81390075Sobrien bb->index = index; 814169689Skan SET_BASIC_BLOCK (index, bb); 815117395Skan 816117395Skan bb->prev_bb = prev_bb; 817117395Skan prev_bb->next_bb = bb; 81890075Sobrien } 819117395Skan prev_bb->next_bb = EXIT_BLOCK_PTR; 820117395Skan EXIT_BLOCK_PTR->prev_bb = prev_bb; 821132718Skan 822132718Skan /* Annoying special case - jump around dead jumptables left in the code. */ 823132718Skan FOR_EACH_BB (bb) 824132718Skan { 825132718Skan edge e; 826169689Skan edge_iterator ei; 827169689Skan 828169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 829169689Skan if (e->flags & EDGE_FALLTHRU) 830169689Skan break; 831169689Skan 832132718Skan if (e && !can_fallthru (e->src, e->dest)) 833132718Skan force_nonfallthru (e); 834132718Skan } 83590075Sobrien} 83690075Sobrien 83790075Sobrien/* Perform sanity checks on the insn chain. 83890075Sobrien 1. Check that next/prev pointers are consistent in both the forward and 83990075Sobrien reverse direction. 84090075Sobrien 2. Count insns in chain, going both directions, and check if equal. 84190075Sobrien 3. Check that get_last_insn () returns the actual end of chain. */ 84290075Sobrien 84390075Sobrienvoid 844132718Skanverify_insn_chain (void) 84590075Sobrien{ 84690075Sobrien rtx x, prevx, nextx; 84790075Sobrien int insn_cnt1, insn_cnt2; 84890075Sobrien 84990075Sobrien for (prevx = NULL, insn_cnt1 = 1, x = get_insns (); 85090075Sobrien x != 0; 85190075Sobrien prevx = x, insn_cnt1++, x = NEXT_INSN (x)) 852169689Skan gcc_assert (PREV_INSN (x) == prevx); 85390075Sobrien 854169689Skan gcc_assert (prevx == get_last_insn ()); 85590075Sobrien 85690075Sobrien for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn (); 85790075Sobrien x != 0; 85890075Sobrien nextx = x, insn_cnt2++, x = PREV_INSN (x)) 859169689Skan gcc_assert (NEXT_INSN (x) == nextx); 86090075Sobrien 861169689Skan gcc_assert (insn_cnt1 == insn_cnt2); 86290075Sobrien} 863117395Skan 864169689Skan/* If we have assembler epilogues, the block falling through to exit must 865169689Skan be the last one in the reordered chain when we reach final. Ensure 866169689Skan that this condition is met. */ 86790075Sobrienstatic void 868132718Skanfixup_fallthru_exit_predecessor (void) 86990075Sobrien{ 87090075Sobrien edge e; 871169689Skan edge_iterator ei; 87290075Sobrien basic_block bb = NULL; 87390075Sobrien 874169689Skan /* This transformation is not valid before reload, because we might 875169689Skan separate a call from the instruction that copies the return 876169689Skan value. */ 877169689Skan gcc_assert (reload_completed); 878169689Skan 879169689Skan FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 88090075Sobrien if (e->flags & EDGE_FALLTHRU) 88190075Sobrien bb = e->src; 88290075Sobrien 883169689Skan if (bb && bb->aux) 88490075Sobrien { 885117395Skan basic_block c = ENTRY_BLOCK_PTR->next_bb; 88690075Sobrien 887146895Skan /* If the very first block is the one with the fall-through exit 888146895Skan edge, we have to split that block. */ 889146895Skan if (c == bb) 890146895Skan { 891146895Skan bb = split_block (bb, NULL)->dest; 892169689Skan bb->aux = c->aux; 893169689Skan c->aux = bb; 894169689Skan bb->il.rtl->footer = c->il.rtl->footer; 895169689Skan c->il.rtl->footer = NULL; 896146895Skan } 897146895Skan 898169689Skan while (c->aux != bb) 899169689Skan c = c->aux; 90090075Sobrien 901169689Skan c->aux = bb->aux; 902169689Skan while (c->aux) 903169689Skan c = c->aux; 90490075Sobrien 905169689Skan c->aux = bb; 906169689Skan bb->aux = NULL; 90790075Sobrien } 90890075Sobrien} 90990075Sobrien 910117395Skan/* Return true in case it is possible to duplicate the basic block BB. */ 91190075Sobrien 912169689Skan/* We do not want to declare the function in a header file, since it should 913169689Skan only be used through the cfghooks interface, and we do not want to move 914169689Skan it to cfgrtl.c since it would require also moving quite a lot of related 915169689Skan code. */ 916169689Skanextern bool cfg_layout_can_duplicate_bb_p (basic_block); 917169689Skan 918117395Skanbool 919132718Skancfg_layout_can_duplicate_bb_p (basic_block bb) 920117395Skan{ 921117395Skan /* Do not attempt to duplicate tablejumps, as we need to unshare 922132718Skan the dispatch table. This is difficult to do, as the instructions 923117395Skan computing jump destination may be hoisted outside the basic block. */ 924132718Skan if (tablejump_p (BB_END (bb), NULL, NULL)) 925117395Skan return false; 926132718Skan 927132718Skan /* Do not duplicate blocks containing insns that can't be copied. */ 928132718Skan if (targetm.cannot_copy_insn_p) 929132718Skan { 930132718Skan rtx insn = BB_HEAD (bb); 931132718Skan while (1) 932132718Skan { 933169689Skan if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn)) 934132718Skan return false; 935132718Skan if (insn == BB_END (bb)) 936132718Skan break; 937132718Skan insn = NEXT_INSN (insn); 938132718Skan } 939132718Skan } 940132718Skan 941117395Skan return true; 942117395Skan} 943117395Skan 944169689Skanrtx 945132718Skanduplicate_insn_chain (rtx from, rtx to) 946117395Skan{ 947117395Skan rtx insn, last; 948117395Skan 949117395Skan /* Avoid updating of boundaries of previous basic block. The 950117395Skan note will get removed from insn stream in fixup. */ 951132718Skan last = emit_note (NOTE_INSN_DELETED); 952117395Skan 953117395Skan /* Create copy at the end of INSN chain. The chain will 954117395Skan be reordered later. */ 955117395Skan for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn)) 956117395Skan { 957117395Skan switch (GET_CODE (insn)) 958117395Skan { 959117395Skan case INSN: 960117395Skan case CALL_INSN: 961117395Skan case JUMP_INSN: 962117395Skan /* Avoid copying of dispatch tables. We never duplicate 963117395Skan tablejumps, so this can hit only in case the table got 964117395Skan moved far from original jump. */ 965117395Skan if (GET_CODE (PATTERN (insn)) == ADDR_VEC 966117395Skan || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) 967117395Skan break; 968132718Skan emit_copy_of_insn_after (insn, get_last_insn ()); 969117395Skan break; 970117395Skan 971117395Skan case CODE_LABEL: 972117395Skan break; 973117395Skan 974117395Skan case BARRIER: 975117395Skan emit_barrier (); 976117395Skan break; 977117395Skan 978117395Skan case NOTE: 979117395Skan switch (NOTE_LINE_NUMBER (insn)) 980117395Skan { 981117395Skan /* In case prologue is empty and function contain label 982169689Skan in first BB, we may want to copy the block. */ 983117395Skan case NOTE_INSN_PROLOGUE_END: 984117395Skan 985117395Skan case NOTE_INSN_DELETED: 986117395Skan case NOTE_INSN_DELETED_LABEL: 987117395Skan /* No problem to strip these. */ 988117395Skan case NOTE_INSN_EPILOGUE_BEG: 989117395Skan case NOTE_INSN_FUNCTION_END: 990117395Skan /* Debug code expect these notes to exist just once. 991169689Skan Keep them in the master copy. 992169689Skan ??? It probably makes more sense to duplicate them for each 993169689Skan epilogue copy. */ 994117395Skan case NOTE_INSN_FUNCTION_BEG: 995117395Skan /* There is always just single entry to function. */ 996117395Skan case NOTE_INSN_BASIC_BLOCK: 997117395Skan break; 998117395Skan 999117395Skan case NOTE_INSN_REPEATED_LINE_NUMBER: 1000169689Skan case NOTE_INSN_SWITCH_TEXT_SECTIONS: 1001132718Skan emit_note_copy (insn); 1002117395Skan break; 1003117395Skan 1004117395Skan default: 1005169689Skan /* All other notes should have already been eliminated. 1006169689Skan */ 1007169689Skan gcc_assert (NOTE_LINE_NUMBER (insn) >= 0); 1008169689Skan 1009117395Skan /* It is possible that no_line_number is set and the note 1010169689Skan won't be emitted. */ 1011132718Skan emit_note_copy (insn); 1012117395Skan } 1013117395Skan break; 1014117395Skan default: 1015169689Skan gcc_unreachable (); 1016117395Skan } 1017117395Skan } 1018117395Skan insn = NEXT_INSN (last); 1019117395Skan delete_insn (last); 1020117395Skan return insn; 1021117395Skan} 1022169689Skan/* Create a duplicate of the basic block BB. */ 1023117395Skan 1024169689Skan/* We do not want to declare the function in a header file, since it should 1025169689Skan only be used through the cfghooks interface, and we do not want to move 1026169689Skan it to cfgrtl.c since it would require also moving quite a lot of related 1027169689Skan code. */ 1028169689Skanextern basic_block cfg_layout_duplicate_bb (basic_block); 1029169689Skan 1030117395Skanbasic_block 1031169689Skancfg_layout_duplicate_bb (basic_block bb) 1032117395Skan{ 1033117395Skan rtx insn; 1034117395Skan basic_block new_bb; 1035117395Skan 1036132718Skan insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb)); 1037117395Skan new_bb = create_basic_block (insn, 1038117395Skan insn ? get_last_insn () : NULL, 1039117395Skan EXIT_BLOCK_PTR->prev_bb); 1040117395Skan 1041169689Skan BB_COPY_PARTITION (new_bb, bb); 1042169689Skan if (bb->il.rtl->header) 1043117395Skan { 1044169689Skan insn = bb->il.rtl->header; 1045117395Skan while (NEXT_INSN (insn)) 1046117395Skan insn = NEXT_INSN (insn); 1047169689Skan insn = duplicate_insn_chain (bb->il.rtl->header, insn); 1048117395Skan if (insn) 1049169689Skan new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ()); 1050117395Skan } 1051117395Skan 1052169689Skan if (bb->il.rtl->footer) 1053117395Skan { 1054169689Skan insn = bb->il.rtl->footer; 1055117395Skan while (NEXT_INSN (insn)) 1056117395Skan insn = NEXT_INSN (insn); 1057169689Skan insn = duplicate_insn_chain (bb->il.rtl->footer, insn); 1058117395Skan if (insn) 1059169689Skan new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ()); 1060117395Skan } 1061117395Skan 1062169689Skan if (bb->il.rtl->global_live_at_start) 1063117395Skan { 1064169689Skan new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 1065169689Skan new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 1066169689Skan COPY_REG_SET (new_bb->il.rtl->global_live_at_start, 1067169689Skan bb->il.rtl->global_live_at_start); 1068169689Skan COPY_REG_SET (new_bb->il.rtl->global_live_at_end, 1069169689Skan bb->il.rtl->global_live_at_end); 1070117395Skan } 1071117395Skan 1072117395Skan return new_bb; 1073117395Skan} 1074117395Skan 1075117395Skan/* Main entry point to this module - initialize the datastructures for 1076132718Skan CFG layout changes. It keeps LOOPS up-to-date if not null. 1077117395Skan 1078132718Skan FLAGS is a set of additional flags to pass to cleanup_cfg(). It should 1079132718Skan include CLEANUP_UPDATE_LIFE if liveness information must be kept up 1080132718Skan to date. */ 1081132718Skan 1082117395Skanvoid 1083132718Skancfg_layout_initialize (unsigned int flags) 108490075Sobrien{ 1085169689Skan initialize_original_copy_tables (); 1086132718Skan 1087132718Skan cfg_layout_rtl_register_cfg_hooks (); 108890075Sobrien 108990075Sobrien record_effective_endpoints (); 1090132718Skan 1091132718Skan cleanup_cfg (CLEANUP_CFGLAYOUT | flags); 109290075Sobrien} 109390075Sobrien 1094132718Skan/* Splits superblocks. */ 1095169689Skanvoid 1096132718Skanbreak_superblocks (void) 1097132718Skan{ 1098132718Skan sbitmap superblocks; 1099169689Skan bool need = false; 1100169689Skan basic_block bb; 1101132718Skan 1102169689Skan superblocks = sbitmap_alloc (last_basic_block); 1103132718Skan sbitmap_zero (superblocks); 1104132718Skan 1105169689Skan FOR_EACH_BB (bb) 1106169689Skan if (bb->flags & BB_SUPERBLOCK) 1107132718Skan { 1108169689Skan bb->flags &= ~BB_SUPERBLOCK; 1109169689Skan SET_BIT (superblocks, bb->index); 1110169689Skan need = true; 1111132718Skan } 1112132718Skan 1113132718Skan if (need) 1114132718Skan { 1115132718Skan rebuild_jump_labels (get_insns ()); 1116132718Skan find_many_sub_basic_blocks (superblocks); 1117132718Skan } 1118132718Skan 1119132718Skan free (superblocks); 1120132718Skan} 1121132718Skan 1122169689Skan/* Finalize the changes: reorder insn list according to the sequence specified 1123169689Skan by aux pointers, enter compensation code, rebuild scope forest. */ 112490075Sobrien 112590075Sobrienvoid 1126132718Skancfg_layout_finalize (void) 112790075Sobrien{ 1128132718Skan basic_block bb; 1129132718Skan 1130132718Skan#ifdef ENABLE_CHECKING 1131132718Skan verify_flow_info (); 1132132718Skan#endif 1133132718Skan rtl_register_cfg_hooks (); 1134169689Skan if (reload_completed 1135169689Skan#ifdef HAVE_epilogue 1136169689Skan && !HAVE_epilogue 1137169689Skan#endif 1138169689Skan ) 1139169689Skan fixup_fallthru_exit_predecessor (); 114090075Sobrien fixup_reorder_chain (); 114190075Sobrien 114290075Sobrien#ifdef ENABLE_CHECKING 114390075Sobrien verify_insn_chain (); 114490075Sobrien#endif 1145132718Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1146169689Skan { 1147169689Skan bb->il.rtl->header = bb->il.rtl->footer = NULL; 1148169689Skan bb->aux = NULL; 1149169689Skan bb->il.rtl->visited = 0; 1150169689Skan } 115190075Sobrien 1152132718Skan break_superblocks (); 1153132718Skan 115490075Sobrien#ifdef ENABLE_CHECKING 115590075Sobrien verify_flow_info (); 115690075Sobrien#endif 1157169689Skan 1158169689Skan free_original_copy_tables (); 115990075Sobrien} 1160132718Skan 1161132718Skan/* Checks whether all N blocks in BBS array can be copied. */ 1162132718Skanbool 1163132718Skancan_copy_bbs_p (basic_block *bbs, unsigned n) 1164132718Skan{ 1165132718Skan unsigned i; 1166132718Skan edge e; 1167132718Skan int ret = true; 1168132718Skan 1169132718Skan for (i = 0; i < n; i++) 1170169689Skan bbs[i]->flags |= BB_DUPLICATED; 1171132718Skan 1172132718Skan for (i = 0; i < n; i++) 1173132718Skan { 1174132718Skan /* In case we should redirect abnormal edge during duplication, fail. */ 1175169689Skan edge_iterator ei; 1176169689Skan FOR_EACH_EDGE (e, ei, bbs[i]->succs) 1177132718Skan if ((e->flags & EDGE_ABNORMAL) 1178169689Skan && (e->dest->flags & BB_DUPLICATED)) 1179132718Skan { 1180132718Skan ret = false; 1181132718Skan goto end; 1182132718Skan } 1183132718Skan 1184169689Skan if (!can_duplicate_block_p (bbs[i])) 1185132718Skan { 1186132718Skan ret = false; 1187132718Skan break; 1188132718Skan } 1189132718Skan } 1190132718Skan 1191132718Skanend: 1192132718Skan for (i = 0; i < n; i++) 1193169689Skan bbs[i]->flags &= ~BB_DUPLICATED; 1194132718Skan 1195132718Skan return ret; 1196132718Skan} 1197132718Skan 1198132718Skan/* Duplicates N basic blocks stored in array BBS. Newly created basic blocks 1199132718Skan are placed into array NEW_BBS in the same order. Edges from basic blocks 1200132718Skan in BBS are also duplicated and copies of those of them 1201132718Skan that lead into BBS are redirected to appropriate newly created block. The 1202132718Skan function assigns bbs into loops (copy of basic block bb is assigned to 1203132718Skan bb->loop_father->copy loop, so this must be set up correctly in advance) 1204132718Skan and updates dominators locally (LOOPS structure that contains the information 1205132718Skan about dominators is passed to enable this). 1206132718Skan 1207132718Skan BASE is the superloop to that basic block belongs; if its header or latch 1208132718Skan is copied, we do not set the new blocks as header or latch. 1209132718Skan 1210132718Skan Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES, 1211169689Skan also in the same order. 1212132718Skan 1213169689Skan Newly created basic blocks are put after the basic block AFTER in the 1214169689Skan instruction stream, and the order of the blocks in BBS array is preserved. */ 1215169689Skan 1216132718Skanvoid 1217132718Skancopy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, 1218169689Skan edge *edges, unsigned num_edges, edge *new_edges, 1219169689Skan struct loop *base, basic_block after) 1220132718Skan{ 1221132718Skan unsigned i, j; 1222132718Skan basic_block bb, new_bb, dom_bb; 1223132718Skan edge e; 1224132718Skan 1225132718Skan /* Duplicate bbs, update dominators, assign bbs to loops. */ 1226132718Skan for (i = 0; i < n; i++) 1227132718Skan { 1228132718Skan /* Duplicate. */ 1229132718Skan bb = bbs[i]; 1230169689Skan new_bb = new_bbs[i] = duplicate_block (bb, NULL, after); 1231169689Skan after = new_bb; 1232169689Skan bb->flags |= BB_DUPLICATED; 1233132718Skan /* Add to loop. */ 1234132718Skan add_bb_to_loop (new_bb, bb->loop_father->copy); 1235132718Skan /* Possibly set header. */ 1236132718Skan if (bb->loop_father->header == bb && bb->loop_father != base) 1237132718Skan new_bb->loop_father->header = new_bb; 1238132718Skan /* Or latch. */ 1239132718Skan if (bb->loop_father->latch == bb && bb->loop_father != base) 1240132718Skan new_bb->loop_father->latch = new_bb; 1241132718Skan } 1242132718Skan 1243132718Skan /* Set dominators. */ 1244132718Skan for (i = 0; i < n; i++) 1245132718Skan { 1246132718Skan bb = bbs[i]; 1247132718Skan new_bb = new_bbs[i]; 1248132718Skan 1249132718Skan dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); 1250169689Skan if (dom_bb->flags & BB_DUPLICATED) 1251132718Skan { 1252169689Skan dom_bb = get_bb_copy (dom_bb); 1253132718Skan set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb); 1254132718Skan } 1255132718Skan } 1256132718Skan 1257132718Skan /* Redirect edges. */ 1258169689Skan for (j = 0; j < num_edges; j++) 1259132718Skan new_edges[j] = NULL; 1260132718Skan for (i = 0; i < n; i++) 1261132718Skan { 1262169689Skan edge_iterator ei; 1263132718Skan new_bb = new_bbs[i]; 1264132718Skan bb = bbs[i]; 1265132718Skan 1266169689Skan FOR_EACH_EDGE (e, ei, new_bb->succs) 1267132718Skan { 1268169689Skan for (j = 0; j < num_edges; j++) 1269132718Skan if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest) 1270132718Skan new_edges[j] = e; 1271132718Skan 1272169689Skan if (!(e->dest->flags & BB_DUPLICATED)) 1273132718Skan continue; 1274169689Skan redirect_edge_and_branch_force (e, get_bb_copy (e->dest)); 1275132718Skan } 1276132718Skan } 1277132718Skan 1278132718Skan /* Clear information about duplicates. */ 1279132718Skan for (i = 0; i < n; i++) 1280169689Skan bbs[i]->flags &= ~BB_DUPLICATED; 1281132718Skan} 1282132718Skan 1283132718Skan#include "gt-cfglayout.h" 1284