1169689Skan/* Loop unswitching. 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify it 7169689Skanunder the terms of the GNU General Public License as published by the 8169689SkanFree Software Foundation; either version 2, or (at your option) any 9169689Skanlater version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 12169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14169689Skanfor more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "rtl.h" 27169689Skan#include "tm_p.h" 28169689Skan#include "hard-reg-set.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "output.h" 31169689Skan#include "diagnostic.h" 32169689Skan#include "tree-flow.h" 33169689Skan#include "tree-dump.h" 34169689Skan#include "timevar.h" 35169689Skan#include "cfgloop.h" 36169689Skan#include "domwalk.h" 37169689Skan#include "params.h" 38169689Skan#include "tree-pass.h" 39169689Skan 40169689Skan/* This file implements the loop unswitching, i.e. transformation of loops like 41169689Skan 42169689Skan while (A) 43169689Skan { 44169689Skan if (inv) 45169689Skan B; 46169689Skan 47169689Skan X; 48169689Skan 49169689Skan if (!inv) 50169689Skan C; 51169689Skan } 52169689Skan 53169689Skan where inv is the loop invariant, into 54169689Skan 55169689Skan if (inv) 56169689Skan { 57169689Skan while (A) 58169689Skan { 59169689Skan B; 60169689Skan X; 61169689Skan } 62169689Skan } 63169689Skan else 64169689Skan { 65169689Skan while (A) 66169689Skan { 67169689Skan X; 68169689Skan C; 69169689Skan } 70169689Skan } 71169689Skan 72169689Skan Inv is considered invariant iff the values it compares are both invariant; 73169689Skan tree-ssa-loop-im.c ensures that all the suitable conditions are in this 74169689Skan shape. */ 75169689Skan 76169689Skanstatic struct loop *tree_unswitch_loop (struct loops *, struct loop *, basic_block, 77169689Skan tree); 78169689Skanstatic bool tree_unswitch_single_loop (struct loops *, struct loop *, int); 79169689Skanstatic tree tree_may_unswitch_on (basic_block, struct loop *); 80169689Skan 81169689Skan/* Main entry point. Perform loop unswitching on all suitable LOOPS. */ 82169689Skan 83169689Skanunsigned int 84169689Skantree_ssa_unswitch_loops (struct loops *loops) 85169689Skan{ 86169689Skan int i, num; 87169689Skan struct loop *loop; 88169689Skan bool changed = false; 89169689Skan 90169689Skan /* Go through inner loops (only original ones). */ 91169689Skan num = loops->num; 92169689Skan 93169689Skan for (i = 1; i < num; i++) 94169689Skan { 95169689Skan /* Removed loop? */ 96169689Skan loop = loops->parray[i]; 97169689Skan if (!loop) 98169689Skan continue; 99169689Skan 100169689Skan if (loop->inner) 101169689Skan continue; 102169689Skan 103169689Skan changed |= tree_unswitch_single_loop (loops, loop, 0); 104169689Skan } 105169689Skan 106169689Skan if (changed) 107169689Skan return TODO_cleanup_cfg; 108169689Skan return 0; 109169689Skan} 110169689Skan 111169689Skan/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its 112169689Skan basic blocks (for what it means see comments below). */ 113169689Skan 114169689Skanstatic tree 115169689Skantree_may_unswitch_on (basic_block bb, struct loop *loop) 116169689Skan{ 117169689Skan tree stmt, def, cond, use; 118169689Skan basic_block def_bb; 119169689Skan ssa_op_iter iter; 120169689Skan 121169689Skan /* BB must end in a simple conditional jump. */ 122169689Skan stmt = last_stmt (bb); 123169689Skan if (!stmt || TREE_CODE (stmt) != COND_EXPR) 124169689Skan return NULL_TREE; 125169689Skan 126169689Skan /* Condition must be invariant. */ 127169689Skan FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 128169689Skan { 129169689Skan def = SSA_NAME_DEF_STMT (use); 130169689Skan def_bb = bb_for_stmt (def); 131169689Skan if (def_bb 132169689Skan && flow_bb_inside_loop_p (loop, def_bb)) 133169689Skan return NULL_TREE; 134169689Skan } 135169689Skan 136169689Skan cond = COND_EXPR_COND (stmt); 137169689Skan /* To keep the things simple, we do not directly remove the conditions, 138169689Skan but just replace tests with 0/1. Prevent the infinite loop where we 139169689Skan would unswitch again on such a condition. */ 140169689Skan if (integer_zerop (cond) || integer_nonzerop (cond)) 141169689Skan return NULL_TREE; 142169689Skan 143169689Skan return cond; 144169689Skan} 145169689Skan 146169689Skan/* Simplifies COND using checks in front of the entry of the LOOP. Just very 147169689Skan simplish (sufficient to prevent us from duplicating loop in unswitching 148169689Skan unnecessarily). */ 149169689Skan 150169689Skanstatic tree 151169689Skansimplify_using_entry_checks (struct loop *loop, tree cond) 152169689Skan{ 153169689Skan edge e = loop_preheader_edge (loop); 154169689Skan tree stmt; 155169689Skan 156169689Skan while (1) 157169689Skan { 158169689Skan stmt = last_stmt (e->src); 159169689Skan if (stmt 160169689Skan && TREE_CODE (stmt) == COND_EXPR 161169689Skan && operand_equal_p (COND_EXPR_COND (stmt), cond, 0)) 162169689Skan return (e->flags & EDGE_TRUE_VALUE 163169689Skan ? boolean_true_node 164169689Skan : boolean_false_node); 165169689Skan 166169689Skan if (!single_pred_p (e->src)) 167169689Skan return cond; 168169689Skan 169169689Skan e = single_pred_edge (e->src); 170169689Skan if (e->src == ENTRY_BLOCK_PTR) 171169689Skan return cond; 172169689Skan } 173169689Skan} 174169689Skan 175169689Skan/* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow 176169689Skan it to grow too much, it is too easy to create example on that the code would 177169689Skan grow exponentially. */ 178169689Skan 179169689Skanstatic bool 180169689Skantree_unswitch_single_loop (struct loops *loops, struct loop *loop, int num) 181169689Skan{ 182169689Skan basic_block *bbs; 183169689Skan struct loop *nloop; 184169689Skan unsigned i; 185169689Skan tree cond = NULL_TREE, stmt; 186169689Skan bool changed = false; 187169689Skan 188169689Skan /* Do not unswitch too much. */ 189169689Skan if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) 190169689Skan { 191169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 192169689Skan fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); 193169689Skan return false; 194169689Skan } 195169689Skan 196169689Skan /* Only unswitch innermost loops. */ 197169689Skan if (loop->inner) 198169689Skan { 199169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 200169689Skan fprintf (dump_file, ";; Not unswitching, not innermost loop\n"); 201169689Skan return false; 202169689Skan } 203169689Skan 204169689Skan /* The loop should not be too large, to limit code growth. */ 205169689Skan if (tree_num_loop_insns (loop) 206169689Skan > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) 207169689Skan { 208169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 209169689Skan fprintf (dump_file, ";; Not unswitching, loop too big\n"); 210169689Skan return false; 211169689Skan } 212169689Skan 213169689Skan i = 0; 214169689Skan bbs = get_loop_body (loop); 215169689Skan 216169689Skan while (1) 217169689Skan { 218169689Skan /* Find a bb to unswitch on. */ 219169689Skan for (; i < loop->num_nodes; i++) 220169689Skan if ((cond = tree_may_unswitch_on (bbs[i], loop))) 221169689Skan break; 222169689Skan 223169689Skan if (i == loop->num_nodes) 224169689Skan { 225169689Skan free (bbs); 226169689Skan return changed; 227169689Skan } 228169689Skan 229169689Skan cond = simplify_using_entry_checks (loop, cond); 230169689Skan stmt = last_stmt (bbs[i]); 231169689Skan if (integer_nonzerop (cond)) 232169689Skan { 233169689Skan /* Remove false path. */ 234169689Skan COND_EXPR_COND (stmt) = boolean_true_node; 235169689Skan changed = true; 236169689Skan } 237169689Skan else if (integer_zerop (cond)) 238169689Skan { 239169689Skan /* Remove true path. */ 240169689Skan COND_EXPR_COND (stmt) = boolean_false_node; 241169689Skan changed = true; 242169689Skan } 243169689Skan else 244169689Skan break; 245169689Skan 246169689Skan update_stmt (stmt); 247169689Skan i++; 248169689Skan } 249169689Skan 250169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 251169689Skan fprintf (dump_file, ";; Unswitching loop\n"); 252169689Skan 253169689Skan initialize_original_copy_tables (); 254169689Skan /* Unswitch the loop on this condition. */ 255169689Skan nloop = tree_unswitch_loop (loops, loop, bbs[i], cond); 256169689Skan if (!nloop) 257169689Skan { 258169689Skan free_original_copy_tables (); 259169689Skan free (bbs); 260169689Skan return changed; 261169689Skan } 262169689Skan 263169689Skan /* Update the SSA form after unswitching. */ 264169689Skan update_ssa (TODO_update_ssa); 265169689Skan free_original_copy_tables (); 266169689Skan 267169689Skan /* Invoke itself on modified loops. */ 268169689Skan tree_unswitch_single_loop (loops, nloop, num + 1); 269169689Skan tree_unswitch_single_loop (loops, loop, num + 1); 270169689Skan free (bbs); 271169689Skan return true; 272169689Skan} 273169689Skan 274169689Skan/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support 275169689Skan unswitching of innermost loops. COND is the condition determining which 276169689Skan loop is entered -- the new loop is entered if COND is true. Returns NULL 277169689Skan if impossible, new loop otherwise. */ 278169689Skan 279169689Skanstatic struct loop * 280169689Skantree_unswitch_loop (struct loops *loops, struct loop *loop, 281169689Skan basic_block unswitch_on, tree cond) 282169689Skan{ 283169689Skan basic_block condition_bb; 284169689Skan 285169689Skan /* Some sanity checking. */ 286169689Skan gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); 287169689Skan gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); 288169689Skan gcc_assert (loop->inner == NULL); 289169689Skan 290169689Skan return loop_version (loops, loop, unshare_expr (cond), 291169689Skan &condition_bb, false); 292169689Skan} 293