1169689Skan/* Loop header copying on trees. 2169689Skan Copyright (C) 2004, 2005, 2006, 2007 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 "tree-pass.h" 35169689Skan#include "timevar.h" 36169689Skan#include "cfgloop.h" 37169689Skan#include "tree-inline.h" 38169689Skan#include "flags.h" 39169689Skan#include "tree-inline.h" 40169689Skan 41169689Skan/* Duplicates headers of loops if they are small enough, so that the statements 42169689Skan in the loop body are always executed when the loop is entered. This 43169689Skan increases effectiveness of code motion optimizations, and reduces the need 44169689Skan for loop preconditioning. */ 45169689Skan 46169689Skan/* Check whether we should duplicate HEADER of LOOP. At most *LIMIT 47169689Skan instructions should be duplicated, limit is decreased by the actual 48169689Skan amount. */ 49169689Skan 50169689Skanstatic bool 51169689Skanshould_duplicate_loop_header_p (basic_block header, struct loop *loop, 52169689Skan int *limit) 53169689Skan{ 54169689Skan block_stmt_iterator bsi; 55169689Skan tree last; 56169689Skan 57169689Skan /* Do not copy one block more than once (we do not really want to do 58169689Skan loop peeling here). */ 59169689Skan if (header->aux) 60169689Skan return false; 61169689Skan 62169689Skan gcc_assert (EDGE_COUNT (header->succs) > 0); 63169689Skan if (single_succ_p (header)) 64169689Skan return false; 65169689Skan if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest) 66169689Skan && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest)) 67169689Skan return false; 68169689Skan 69169689Skan /* If this is not the original loop header, we want it to have just 70169689Skan one predecessor in order to match the && pattern. */ 71169689Skan if (header != loop->header && !single_pred_p (header)) 72169689Skan return false; 73169689Skan 74169689Skan last = last_stmt (header); 75169689Skan if (TREE_CODE (last) != COND_EXPR) 76169689Skan return false; 77169689Skan 78169689Skan /* Approximately copy the conditions that used to be used in jump.c -- 79169689Skan at most 20 insns and no calls. */ 80169689Skan for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi)) 81169689Skan { 82169689Skan last = bsi_stmt (bsi); 83169689Skan 84169689Skan if (TREE_CODE (last) == LABEL_EXPR) 85169689Skan continue; 86169689Skan 87169689Skan if (get_call_expr_in (last)) 88169689Skan return false; 89169689Skan 90169689Skan *limit -= estimate_num_insns (last); 91169689Skan if (*limit < 0) 92169689Skan return false; 93169689Skan } 94169689Skan 95169689Skan return true; 96169689Skan} 97169689Skan 98169689Skan/* Checks whether LOOP is a do-while style loop. */ 99169689Skan 100169689Skanstatic bool 101169689Skando_while_loop_p (struct loop *loop) 102169689Skan{ 103169689Skan tree stmt = last_stmt (loop->latch); 104169689Skan 105169689Skan /* If the latch of the loop is not empty, it is not a do-while loop. */ 106169689Skan if (stmt 107169689Skan && TREE_CODE (stmt) != LABEL_EXPR) 108169689Skan return false; 109169689Skan 110169689Skan /* If the header contains just a condition, it is not a do-while loop. */ 111169689Skan stmt = last_and_only_stmt (loop->header); 112169689Skan if (stmt 113169689Skan && TREE_CODE (stmt) == COND_EXPR) 114169689Skan return false; 115169689Skan 116169689Skan return true; 117169689Skan} 118169689Skan 119169689Skan/* For all loops, copy the condition at the end of the loop body in front 120169689Skan of the loop. This is beneficial since it increases efficiency of 121169689Skan code motion optimizations. It also saves one jump on entry to the loop. */ 122169689Skan 123169689Skanstatic unsigned int 124169689Skancopy_loop_headers (void) 125169689Skan{ 126169689Skan struct loops *loops; 127169689Skan unsigned i; 128169689Skan struct loop *loop; 129169689Skan basic_block header; 130169689Skan edge exit, entry; 131169689Skan basic_block *bbs, *copied_bbs; 132169689Skan unsigned n_bbs; 133169689Skan unsigned bbs_size; 134169689Skan 135169689Skan loops = loop_optimizer_init (LOOPS_HAVE_PREHEADERS 136169689Skan | LOOPS_HAVE_SIMPLE_LATCHES); 137169689Skan if (!loops) 138169689Skan return 0; 139169689Skan 140169689Skan#ifdef ENABLE_CHECKING 141169689Skan verify_loop_structure (loops); 142169689Skan#endif 143169689Skan 144169689Skan bbs = XNEWVEC (basic_block, n_basic_blocks); 145169689Skan copied_bbs = XNEWVEC (basic_block, n_basic_blocks); 146169689Skan bbs_size = n_basic_blocks; 147169689Skan 148169689Skan for (i = 1; i < loops->num; i++) 149169689Skan { 150169689Skan /* Copy at most 20 insns. */ 151169689Skan int limit = 20; 152169689Skan 153169689Skan loop = loops->parray[i]; 154169689Skan if (!loop) 155169689Skan continue; 156169689Skan header = loop->header; 157169689Skan 158169689Skan /* If the loop is already a do-while style one (either because it was 159169689Skan written as such, or because jump threading transformed it into one), 160169689Skan we might be in fact peeling the first iteration of the loop. This 161169689Skan in general is not a good idea. */ 162169689Skan if (do_while_loop_p (loop)) 163169689Skan continue; 164169689Skan 165169689Skan /* Iterate the header copying up to limit; this takes care of the cases 166169689Skan like while (a && b) {...}, where we want to have both of the conditions 167169689Skan copied. TODO -- handle while (a || b) - like cases, by not requiring 168169689Skan the header to have just a single successor and copying up to 169169689Skan postdominator. */ 170169689Skan 171169689Skan exit = NULL; 172169689Skan n_bbs = 0; 173169689Skan while (should_duplicate_loop_header_p (header, loop, &limit)) 174169689Skan { 175169689Skan /* Find a successor of header that is inside a loop; i.e. the new 176169689Skan header after the condition is copied. */ 177169689Skan if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)) 178169689Skan exit = EDGE_SUCC (header, 0); 179169689Skan else 180169689Skan exit = EDGE_SUCC (header, 1); 181169689Skan bbs[n_bbs++] = header; 182169689Skan gcc_assert (bbs_size > n_bbs); 183169689Skan header = exit->dest; 184169689Skan } 185169689Skan 186169689Skan if (!exit) 187169689Skan continue; 188169689Skan 189169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 190169689Skan fprintf (dump_file, 191169689Skan "Duplicating header of the loop %d up to edge %d->%d.\n", 192169689Skan loop->num, exit->src->index, exit->dest->index); 193169689Skan 194169689Skan /* Ensure that the header will have just the latch as a predecessor 195169689Skan inside the loop. */ 196169689Skan if (!single_pred_p (exit->dest)) 197169689Skan exit = single_pred_edge (loop_split_edge_with (exit, NULL)); 198169689Skan 199169689Skan entry = loop_preheader_edge (loop); 200169689Skan 201169689Skan if (!tree_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs)) 202169689Skan { 203169689Skan fprintf (dump_file, "Duplication failed.\n"); 204169689Skan continue; 205169689Skan } 206169689Skan 207169689Skan /* If the loop has the form "for (i = j; i < j + 10; i++)" then 208169689Skan this copying can introduce a case where we rely on undefined 209169689Skan signed overflow to eliminate the preheader condition, because 210169689Skan we assume that "j < j + 10" is true. We don't want to warn 211169689Skan about that case for -Wstrict-overflow, because in general we 212169689Skan don't warn about overflow involving loops. Prevent the 213169689Skan warning by setting TREE_NO_WARNING. */ 214169689Skan if (warn_strict_overflow > 0) 215169689Skan { 216169689Skan unsigned int i; 217169689Skan 218169689Skan for (i = 0; i < n_bbs; ++i) 219169689Skan { 220169689Skan tree last; 221169689Skan 222169689Skan last = last_stmt (copied_bbs[i]); 223169689Skan if (TREE_CODE (last) == COND_EXPR) 224169689Skan TREE_NO_WARNING (last) = 1; 225169689Skan } 226169689Skan } 227169689Skan 228169689Skan /* Ensure that the latch and the preheader is simple (we know that they 229169689Skan are not now, since there was the loop exit condition. */ 230169689Skan loop_split_edge_with (loop_preheader_edge (loop), NULL); 231169689Skan loop_split_edge_with (loop_latch_edge (loop), NULL); 232169689Skan } 233169689Skan 234169689Skan free (bbs); 235169689Skan free (copied_bbs); 236169689Skan 237169689Skan loop_optimizer_finalize (loops); 238169689Skan return 0; 239169689Skan} 240169689Skan 241169689Skanstatic bool 242169689Skangate_ch (void) 243169689Skan{ 244169689Skan return flag_tree_ch != 0; 245169689Skan} 246169689Skan 247169689Skanstruct tree_opt_pass pass_ch = 248169689Skan{ 249169689Skan "ch", /* name */ 250169689Skan gate_ch, /* gate */ 251169689Skan copy_loop_headers, /* execute */ 252169689Skan NULL, /* sub */ 253169689Skan NULL, /* next */ 254169689Skan 0, /* static_pass_number */ 255169689Skan TV_TREE_CH, /* tv_id */ 256169689Skan PROP_cfg | PROP_ssa, /* properties_required */ 257169689Skan 0, /* properties_provided */ 258169689Skan 0, /* properties_destroyed */ 259169689Skan 0, /* todo_flags_start */ 260169689Skan TODO_cleanup_cfg | TODO_dump_func 261169689Skan | TODO_verify_ssa, /* todo_flags_finish */ 262169689Skan 0 /* letter */ 263169689Skan}; 264