loop-unswitch.c revision 132718
181477Smarkm/* Loop unswitching for GNU compiler. 2109069Snectar Copyright (C) 2002, 2003 Free Software Foundation, Inc. 3109069Snectar 4109069SnectarThis file is part of GCC. 5109069Snectar 6109069SnectarGCC is free software; you can redistribute it and/or modify it under 7109069Snectarthe terms of the GNU General Public License as published by the Free 8109069SnectarSoftware Foundation; either version 2, or (at your option) any later 9140667Srwatsonversion. 10109069Snectar 1194564SdesGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1293984SdesWARRANTY; without even the implied warranty of MERCHANTABILITY or 1393984SdesFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1493984Sdesfor more details. 1593984Sdes 16110274SdesYou should have received a copy of the GNU General Public License 1781477Smarkmalong with GCC; see the file COPYING. If not, write to the Free 1881477SmarkmSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 1981477Smarkm02111-1307, USA. */ 2081477Smarkm 21109069Snectar#include "config.h" 2281477Smarkm#include "system.h" 2381477Smarkm#include "coretypes.h" 2481477Smarkm#include "tm.h" 2581477Smarkm#include "rtl.h" 2681477Smarkm#include "hard-reg-set.h" 2781477Smarkm#include "basic-block.h" 2881477Smarkm#include "cfgloop.h" 29110274Sdes#include "cfglayout.h" 3081477Smarkm#include "params.h" 3181477Smarkm#include "output.h" 3281477Smarkm#include "expr.h" 3381477Smarkm 3481477Smarkm/* This pass moves constant conditions out of loops, duplicating the loop 35110274Sdes in progress, i.e. this code: 3681477Smarkm 3781477Smarkm while (loop_cond) 3881477Smarkm { 3981477Smarkm A; 4081477Smarkm if (cond) 4181477Smarkm branch1; 4281477Smarkm else 4381477Smarkm branch2; 4481477Smarkm B; 4581477Smarkm if (cond) 4681477Smarkm branch3; 4794564Sdes C; 4881477Smarkm } 4981477Smarkm where nothing inside the loop alters cond is transformed 5084218Sdillon into 5184218Sdillon 5284218Sdillon if (cond) 5381477Smarkm { 5481477Smarkm while (loop_cond) 5581477Smarkm { 5681477Smarkm A; 5781477Smarkm branch1; 5881477Smarkm B; 5981477Smarkm branch3; 6093984Sdes C; 6181477Smarkm } 6281477Smarkm } 6381477Smarkm else 6481477Smarkm { 6581477Smarkm while (loop_cond) 6681477Smarkm { 6781477Smarkm A; 6881477Smarkm branch2; 6981477Smarkm B; 7081477Smarkm C; 7181477Smarkm } 7281477Smarkm } 7390229Sdes 74115465Sdes Duplicating the loop might lead to code growth exponential in number of 7581477Smarkm branches inside loop, so we limit the number of unswitchings performed 7681477Smarkm in a single loop to PARAM_MAX_UNSWITCH_LEVEL. We only perform the 7781477Smarkm transformation on innermost loops, as the benefit of doing it on loops 7881477Smarkm containing subloops would not be very large compared to complications 7981477Smarkm with handling this case. */ 8081477Smarkm 8181477Smarkmstatic struct loop *unswitch_loop (struct loops *, struct loop *, 8281477Smarkm basic_block); 8381477Smarkmstatic void unswitch_single_loop (struct loops *, struct loop *, rtx, int); 8481477Smarkmstatic bool may_unswitch_on_p (basic_block, struct loop *, 8585485Ssobomax basic_block *); 8685485Ssobomaxstatic rtx reversed_condition (rtx); 8781477Smarkm 88115465Sdes/* Main entry point. Perform loop unswitching on all suitable LOOPS. */ 89140667Srwatsonvoid 90115465Sdesunswitch_loops (struct loops *loops) 91115465Sdes{ 92207553Smm int i, num; 93115465Sdes struct loop *loop; 94239062Sdfr 9581477Smarkm /* Go through inner loops (only original ones). */ 96233406Sstas num = loops->num; 97233406Sstas 98233406Sstas for (i = 1; i < num; i++) 99233406Sstas { 100233406Sstas /* Removed loop? */ 101233406Sstas loop = loops->parray[i]; 102233406Sstas if (!loop) 10381477Smarkm continue; 10481477Smarkm 10581477Smarkm if (loop->inner) 10681477Smarkm continue; 10794564Sdes 108115465Sdes unswitch_single_loop (loops, loop, NULL_RTX, 0); 10981477Smarkm#ifdef ENABLE_CHECKING 11081477Smarkm verify_dominators (CDI_DOMINATORS); 11181477Smarkm verify_loop_structure (loops); 11281477Smarkm#endif 11381477Smarkm } 114106864Snectar} 115233406Sstas 11681477Smarkm/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its 11781477Smarkm basic blocks (for what it means see comments below). List of basic blocks 118174837Sdes inside LOOP is provided in BODY to save time. */ 119123454Sdesstatic bool 120125650Sdesmay_unswitch_on_p (basic_block bb, struct loop *loop, basic_block *body) 121106864Snectar{ 12281477Smarkm rtx test; 12381477Smarkm unsigned i; 12481477Smarkm 12594564Sdes /* BB must end in a simple conditional jump. */ 12681477Smarkm if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next) 12781477Smarkm return false; 12881477Smarkm if (!any_condjump_p (BB_END (bb))) 129123454Sdes return false; 13081477Smarkm 13194564Sdes /* With branches inside loop. */ 13281477Smarkm if (!flow_bb_inside_loop_p (loop, bb->succ->dest) 133123454Sdes || !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest)) 13481477Smarkm return false; 13581477Smarkm 136123454Sdes /* It must be executed just once each iteration (because otherwise we 13781477Smarkm are unable to update dominator/irreducible loop information correctly). */ 13881477Smarkm if (!just_once_each_iteration_p (loop, bb)) 13981477Smarkm return false; 140123454Sdes 14181477Smarkm /* Condition must be invariant. We use just a stupid test of invariantness 14281477Smarkm of the condition: all used regs must not be modified inside loop body. */ 14381477Smarkm test = get_condition (BB_END (bb), NULL, true); 14481477Smarkm if (!test) 14594564Sdes return false; 14681477Smarkm 14781477Smarkm for (i = 0; i < loop->num_nodes; i++) 14881477Smarkm if (modified_between_p (test, BB_HEAD (body[i]), NEXT_INSN (BB_END (body[i])))) 14981477Smarkm return false; 15081477Smarkm 15181477Smarkm return true; 15281477Smarkm} 15381477Smarkm 15481477Smarkm/* Reverses CONDition; returns NULL if we cannot. */ 15581477Smarkmstatic rtx 15681477Smarkmreversed_condition (rtx cond) 15781477Smarkm{ 15881477Smarkm enum rtx_code reversed; 15981477Smarkm reversed = reversed_comparison_code (cond, NULL); 160115465Sdes if (reversed == UNKNOWN) 161123454Sdes return NULL_RTX; 16281477Smarkm else 16381477Smarkm return gen_rtx_fmt_ee (reversed, 16481477Smarkm GET_MODE (cond), XEXP (cond, 0), 16581477Smarkm XEXP (cond, 1)); 16681477Smarkm} 16781477Smarkm 16881477Smarkm/* Unswitch single LOOP. COND_CHECKED holds list of conditions we already 16981477Smarkm unswitched on and are therefore known to be true in this LOOP. NUM is 170233406Sstas number of unswitchings done; do not allow it to grow too much, it is too 17181477Smarkm easy to create example on that the code would grow exponentially. */ 17281477Smarkmstatic void 17381477Smarkmunswitch_single_loop (struct loops *loops, struct loop *loop, 17481477Smarkm rtx cond_checked, int num) 17581477Smarkm{ 17681477Smarkm basic_block *bbs, bb; 17781477Smarkm struct loop *nloop; 17881477Smarkm unsigned i; 17981477Smarkm int true_first; 18081477Smarkm rtx cond, rcond, conds, rconds, acond, split_before; 18181477Smarkm int always_true; 182233406Sstas int always_false; 183233406Sstas int repeat; 18481477Smarkm edge e; 18581477Smarkm 18681477Smarkm /* Do not unswitch too much. */ 18781477Smarkm if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) 18881477Smarkm { 18981477Smarkm if (rtl_dump_file) 19081477Smarkm fprintf (rtl_dump_file, ";; Not unswitching anymore, hit max level\n"); 19181477Smarkm return; 19293984Sdes } 19381477Smarkm 19481477Smarkm /* Only unswitch innermost loops. */ 19581477Smarkm if (loop->inner) 19681477Smarkm { 19781477Smarkm if (rtl_dump_file) 198207553Smm fprintf (rtl_dump_file, ";; Not unswitching, not innermost loop\n"); 199207553Smm return; 200207553Smm } 201207553Smm 202207555Smm /* We must be able to duplicate loop body. */ 203207555Smm if (!can_duplicate_loop_p (loop)) 204207555Smm { 205207555Smm if (rtl_dump_file) 206207555Smm fprintf (rtl_dump_file, ";; Not unswitching, can't duplicate loop\n"); 207207555Smm return; 208207555Smm } 209233406Sstas 210233406Sstas /* The loop should not be too large, to limit code growth. */ 211207555Smm if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) 212207555Smm { 213207555Smm if (rtl_dump_file) 214207555Smm fprintf (rtl_dump_file, ";; Not unswitching, loop too big\n"); 215207555Smm return; 216207555Smm } 217207555Smm 218207555Smm /* Do not unswitch in cold areas. */ 219207555Smm if (!maybe_hot_bb_p (loop->header)) 220207555Smm { 221207555Smm if (rtl_dump_file) 222239062Sdfr fprintf (rtl_dump_file, ";; Not unswitching, not hot area\n"); 223239062Sdfr return; 224239062Sdfr } 225239062Sdfr 226239062Sdfr /* Nor if the loop usually does not roll. */ 227239062Sdfr if (expected_loop_iterations (loop) < 1) 22881477Smarkm { 22981477Smarkm if (rtl_dump_file) 230207555Smm fprintf (rtl_dump_file, ";; Not unswitching, loop iterations < 1\n"); 23181477Smarkm return; 23281477Smarkm } 233233406Sstas 234233406Sstas do 235233406Sstas { 236233406Sstas repeat = 0; 237233406Sstas 238233406Sstas /* Find a bb to unswitch on. */ 239233406Sstas bbs = get_loop_body (loop); 240233406Sstas for (i = 0; i < loop->num_nodes; i++) 241233406Sstas if (may_unswitch_on_p (bbs[i], loop, bbs)) 242233406Sstas break; 243233406Sstas 244233406Sstas if (i == loop->num_nodes) 245233406Sstas { 246233406Sstas free (bbs); 247233406Sstas return; 24881477Smarkm } 24981477Smarkm 25081477Smarkm if (!(cond = get_condition (BB_END (bbs[i]), &split_before, true))) 251233406Sstas abort (); 252233406Sstas rcond = reversed_condition (cond); 25381477Smarkm 25481477Smarkm /* Check whether the result can be predicted. */ 255233406Sstas always_true = 0; 256233406Sstas always_false = 0; 25781477Smarkm for (acond = cond_checked; acond; acond = XEXP (acond, 1)) 25881477Smarkm { 25981477Smarkm if (rtx_equal_p (cond, XEXP (acond, 0))) 26081477Smarkm { 26181477Smarkm always_true = 1; 26281477Smarkm break; 263106864Snectar } 264233406Sstas if (rtx_equal_p (rcond, XEXP (acond, 0))) 26581477Smarkm { 26681477Smarkm always_false = 1; 267233406Sstas break; 268233406Sstas } 26981477Smarkm } 27081477Smarkm 27181477Smarkm if (always_true) 27281477Smarkm { 27381477Smarkm /* Remove false path. */ 27481477Smarkm for (e = bbs[i]->succ; !(e->flags & EDGE_FALLTHRU); e = e->succ_next); 275233406Sstas remove_path (loops, e); 276233406Sstas free (bbs); 27781477Smarkm repeat = 1; 27881477Smarkm } 27981477Smarkm else if (always_false) 28081477Smarkm { 28181477Smarkm /* Remove true path. */ 28281477Smarkm for (e = bbs[i]->succ; e->flags & EDGE_FALLTHRU; e = e->succ_next); 283233406Sstas remove_path (loops, e); 284233406Sstas free (bbs); 28581477Smarkm repeat = 1; 28681477Smarkm } 28781477Smarkm } while (repeat); 28881477Smarkm 28981477Smarkm /* We found the condition we can unswitch on. */ 29081477Smarkm conds = alloc_EXPR_LIST (0, cond, cond_checked); 29181477Smarkm if (rcond) 29281477Smarkm rconds = alloc_EXPR_LIST (0, rcond, cond_checked); 29393984Sdes else 29493984Sdes rconds = cond_checked; 29593984Sdes 29693984Sdes /* Separate condition in a single basic block. */ 29793984Sdes bb = split_loop_bb (bbs[i], PREV_INSN (split_before))->dest; 298140667Srwatson free (bbs); 29993984Sdes true_first = !(bb->succ->flags & EDGE_FALLTHRU); 30093984Sdes if (rtl_dump_file) 30181477Smarkm fprintf (rtl_dump_file, ";; Unswitching loop\n"); 30281477Smarkm 30381477Smarkm /* Unswitch the loop on this condition. */ 30481477Smarkm nloop = unswitch_loop (loops, loop, bb); 30581477Smarkm if (!nloop) 30681477Smarkm abort (); 30781477Smarkm 30881477Smarkm /* Invoke itself on modified loops. */ 309125650Sdes unswitch_single_loop (loops, nloop, true_first ? conds : rconds, num + 1); 31081477Smarkm unswitch_single_loop (loops, loop, true_first ? rconds : conds, num + 1); 31181477Smarkm 31281477Smarkm free_EXPR_LIST_node (conds); 31381477Smarkm if (rcond) 31481477Smarkm free_EXPR_LIST_node (rconds); 31581477Smarkm} 31681477Smarkm 31781477Smarkm/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support 31881477Smarkm unswitching of innermost loops. UNSWITCH_ON must be executed in every 319106864Snectar iteration, i.e. it must dominate LOOP latch, and should only contain code 320106864Snectar for the condition we unswitch on. Returns NULL if impossible, new 321106864Snectar loop otherwise. */ 322106864Snectarstatic struct loop * 323106864Snectarunswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on) 324106864Snectar{ 325106864Snectar edge entry, latch_edge; 326106864Snectar basic_block switch_bb, unswitch_on_alt, src; 32781477Smarkm struct loop *nloop; 32881477Smarkm sbitmap zero_bitmap; 32981477Smarkm int irred_flag; 33081477Smarkm 33181477Smarkm /* Some sanity checking. */ 33281477Smarkm if (!flow_bb_inside_loop_p (loop, unswitch_on)) 33381477Smarkm abort (); 33481477Smarkm if (!unswitch_on->succ || !unswitch_on->succ->succ_next || 33581477Smarkm unswitch_on->succ->succ_next->succ_next) 33681477Smarkm abort (); 33781477Smarkm if (!just_once_each_iteration_p (loop, unswitch_on)) 33881477Smarkm abort (); 33981477Smarkm if (loop->inner) 34081477Smarkm abort (); 34181477Smarkm if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->dest)) 34281477Smarkm abort (); 343239099Sdim if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->succ_next->dest)) 34481477Smarkm abort (); 345239099Sdim 34681477Smarkm /* Will we be able to perform redirection? */ 34781477Smarkm if (!any_condjump_p (BB_END (unswitch_on))) 34881477Smarkm return NULL; 34981477Smarkm if (!cfg_layout_can_duplicate_bb_p (unswitch_on)) 35081477Smarkm return NULL; 35181477Smarkm 35281477Smarkm entry = loop_preheader_edge (loop); 35394564Sdes 35481477Smarkm /* Make a copy. */ 35581477Smarkm src = entry->src; 35681477Smarkm irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; 35794564Sdes entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; 358115465Sdes zero_bitmap = sbitmap_alloc (2); 35981477Smarkm sbitmap_zero (zero_bitmap); 360147810Skensmith if (!duplicate_loop_to_header_edge (loop, entry, loops, 1, 361147810Skensmith zero_bitmap, NULL, NULL, NULL, 0)) 362147810Skensmith return NULL; 36381477Smarkm free (zero_bitmap); 36481477Smarkm entry->flags |= irred_flag; 36581477Smarkm 36681477Smarkm /* Record the block with condition we unswitch on. */ 36781477Smarkm unswitch_on_alt = unswitch_on->rbi->copy; 36881477Smarkm 36981477Smarkm /* Make a copy of the block containing the condition; we will use 37081477Smarkm it as switch to decide which loop we want to use. */ 37181477Smarkm switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL); 372123454Sdes if (irred_flag) 373125650Sdes { 374174837Sdes switch_bb->flags |= BB_IRREDUCIBLE_LOOP; 375115465Sdes switch_bb->succ->flags |= EDGE_IRREDUCIBLE_LOOP; 37681477Smarkm switch_bb->succ->succ_next->flags |= EDGE_IRREDUCIBLE_LOOP; 37781477Smarkm } 37881477Smarkm else 37981477Smarkm { 38081477Smarkm switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP; 38194564Sdes switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP; 38281477Smarkm switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP; 38381477Smarkm } 38494564Sdes add_to_dominance_info (CDI_DOMINATORS, switch_bb); 38581477Smarkm unswitch_on->rbi->copy = unswitch_on_alt; 38681477Smarkm 38794564Sdes /* Loopify from the copy of LOOP body, constructing the new loop. */ 38881477Smarkm for (latch_edge = loop->latch->rbi->copy->succ; 38981477Smarkm latch_edge->dest != loop->header; 39094564Sdes latch_edge = latch_edge->succ_next); 39181477Smarkm nloop = loopify (loops, latch_edge, 392140747Srwatson loop->header->rbi->copy->pred, switch_bb); 393207553Smm 394207553Smm /* Remove branches that are now unreachable in new loops. We rely on the 395140747Srwatson fact that cfg_layout_duplicate_bb reverses list of edges. */ 396140747Srwatson remove_path (loops, unswitch_on->succ); 39781477Smarkm remove_path (loops, unswitch_on_alt->succ); 39881477Smarkm 39981477Smarkm /* One of created loops do not have to be subloop of the outer loop now, 400123454Sdes so fix its placement in loop data structure. */ 40181477Smarkm fix_loop_placement (loop); 40294564Sdes fix_loop_placement (nloop); 40381477Smarkm 404123454Sdes /* Preserve the simple loop preheaders. */ 40581477Smarkm loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX); 40681477Smarkm loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX); 40781477Smarkm 408106862Snectar return nloop; 40994564Sdes} 41081477Smarkm