tree-ssa-loop-ivcanon.c revision 225736
1204076Spjd/* Induction variable canonicalization. 2204076Spjd Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3211877Spjd 4204076SpjdThis file is part of GCC. 5204076Spjd 6204076SpjdGCC is free software; you can redistribute it and/or modify it 7204076Spjdunder the terms of the GNU General Public License as published by the 8204076SpjdFree Software Foundation; either version 2, or (at your option) any 9204076Spjdlater version. 10204076Spjd 11204076SpjdGCC is distributed in the hope that it will be useful, but WITHOUT 12204076SpjdANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13204076SpjdFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14204076Spjdfor more details. 15204076Spjd 16204076SpjdYou should have received a copy of the GNU General Public License 17204076Spjdalong with GCC; see the file COPYING. If not, write to the Free 18204076SpjdSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19204076Spjd02110-1301, USA. */ 20204076Spjd 21204076Spjd/* This pass detects the loops that iterate a constant number of times, 22204076Spjd adds a canonical induction variable (step -1, tested against 0) 23204076Spjd and replaces the exit test. This enables the less powerful rtl 24204076Spjd level analysis to use this information. 25204076Spjd 26204076Spjd This might spoil the code in some cases (by increasing register pressure). 27204076Spjd Note that in the case the new variable is not needed, ivopts will get rid 28204076Spjd of it, so it might only be a problem when there are no other linear induction 29204076Spjd variables. In that case the created optimization possibilities are likely 30204076Spjd to pay up. 31204076Spjd 32204076Spjd Additionally in case we detect that it is beneficial to unroll the 33204076Spjd loop completely, we do it right here to expose the optimization 34204076Spjd possibilities to the following passes. */ 35204076Spjd 36204076Spjd#include "config.h" 37204076Spjd#include "system.h" 38204076Spjd#include "coretypes.h" 39204076Spjd#include "tm.h" 40204076Spjd#include "tree.h" 41204076Spjd#include "rtl.h" 42204076Spjd#include "tm_p.h" 43204076Spjd#include "hard-reg-set.h" 44204076Spjd#include "basic-block.h" 45213009Spjd#include "output.h" 46204076Spjd#include "diagnostic.h" 47204076Spjd#include "tree-flow.h" 48204076Spjd#include "tree-dump.h" 49204076Spjd#include "cfgloop.h" 50204076Spjd#include "tree-pass.h" 51204076Spjd#include "ggc.h" 52204076Spjd#include "tree-chrec.h" 53204076Spjd#include "tree-scalar-evolution.h" 54204076Spjd#include "params.h" 55204076Spjd#include "flags.h" 56204076Spjd#include "tree-inline.h" 57212038Spjd 58204076Spjd/* Specifies types of loops that may be unrolled. */ 59204076Spjd 60204076Spjdenum unroll_level 61211977Spjd{ 62204076Spjd UL_SINGLE_ITER, /* Only loops that exit immediately in the first 63204076Spjd iteration. */ 64204076Spjd UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase 65204076Spjd of code size. */ 66204076Spjd UL_ALL /* All suitable loops. */ 67204076Spjd}; 68219864Spjd 69219864Spjd/* Adds a canonical induction variable to LOOP iterating NITER times. EXIT 70204076Spjd is the exit edge whose condition is replaced. */ 71204076Spjd 72204076Spjdstatic void 73204076Spjdcreate_canonical_iv (struct loop *loop, edge exit, tree niter) 74204076Spjd{ 75204076Spjd edge in; 76204076Spjd tree cond, type, var; 77204076Spjd block_stmt_iterator incr_at; 78211984Spjd enum tree_code cmp; 79211984Spjd 80204076Spjd if (dump_file && (dump_flags & TDF_DETAILS)) 81204076Spjd { 82204076Spjd fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num); 83204076Spjd print_generic_expr (dump_file, niter, TDF_SLIM); 84204076Spjd fprintf (dump_file, " iterations.\n"); 85204076Spjd } 86204076Spjd 87204076Spjd cond = last_stmt (exit->src); 88204076Spjd in = EDGE_SUCC (exit->src, 0); 89204076Spjd if (in == exit) 90204076Spjd in = EDGE_SUCC (exit->src, 1); 91204076Spjd 92204076Spjd /* Note that we do not need to worry about overflows, since 93204076Spjd type of niter is always unsigned and all comparisons are 94204076Spjd just for equality/nonequality -- i.e. everything works 95204076Spjd with a modulo arithmetics. */ 96204076Spjd 97204076Spjd type = TREE_TYPE (niter); 98204076Spjd niter = fold_build2 (PLUS_EXPR, type, 99204076Spjd niter, 100204076Spjd build_int_cst (type, 1)); 101204076Spjd incr_at = bsi_last (in->src); 102204076Spjd create_iv (niter, 103204076Spjd build_int_cst (type, -1), 104204076Spjd NULL_TREE, loop, 105204076Spjd &incr_at, false, NULL, &var); 106204076Spjd 107204076Spjd cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR; 108204076Spjd COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node, 109204076Spjd var, 110211877Spjd build_int_cst (type, 0)); 111211877Spjd update_stmt (cond); 112211877Spjd} 113211877Spjd 114211877Spjd/* Computes an estimated number of insns in LOOP. */ 115211877Spjd 116211877Spjdunsigned 117211877Spjdtree_num_loop_insns (struct loop *loop) 118211877Spjd{ 119211877Spjd basic_block *body = get_loop_body (loop); 120211877Spjd block_stmt_iterator bsi; 121211877Spjd unsigned size = 1, i; 122211877Spjd 123211877Spjd for (i = 0; i < loop->num_nodes; i++) 124211877Spjd for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) 125211877Spjd size += estimate_num_insns (bsi_stmt (bsi)); 126211877Spjd free (body); 127211877Spjd 128211877Spjd return size; 129211877Spjd} 130204076Spjd 131204076Spjd/* Estimate number of insns of completely unrolled loop. We assume 132204076Spjd that the size of the unrolled loop is decreased in the 133204076Spjd following way (the numbers of insns are based on what 134204076Spjd estimate_num_insns returns for appropriate statements): 135204076Spjd 136204076Spjd 1) exit condition gets removed (2 insns) 137204076Spjd 2) increment of the control variable gets removed (2 insns) 138204076Spjd 3) All remaining statements are likely to get simplified 139204076Spjd due to constant propagation. Hard to estimate; just 140204076Spjd as a heuristics we decrease the rest by 1/3. 141204076Spjd 142204076Spjd NINSNS is the number of insns in the loop before unrolling. 143204076Spjd NUNROLL is the number of times the loop is unrolled. */ 144204076Spjd 145204076Spjdstatic unsigned HOST_WIDE_INT 146204076Spjdestimated_unrolled_size (unsigned HOST_WIDE_INT ninsns, 147204076Spjd unsigned HOST_WIDE_INT nunroll) 148204076Spjd{ 149204076Spjd HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3; 150204076Spjd if (unr_insns <= 0) 151204076Spjd unr_insns = 1; 152204076Spjd unr_insns *= (nunroll + 1); 153204076Spjd 154204076Spjd return unr_insns; 155210879Spjd} 156210879Spjd 157210879Spjd/* Tries to unroll LOOP completely, i.e. NITER times. LOOPS is the 158204076Spjd loop tree. UL determines which loops we are allowed to unroll. 159204076Spjd EXIT is the exit of the loop that should be eliminated. */ 160204076Spjd 161204076Spjdstatic bool 162210879Spjdtry_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED, 163210879Spjd struct loop *loop, 164210879Spjd edge exit, tree niter, 165204076Spjd enum unroll_level ul) 166204076Spjd{ 167204076Spjd unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; 168204076Spjd tree old_cond, cond, dont_exit, do_exit; 169204076Spjd 170204076Spjd if (loop->inner) 171204076Spjd return false; 172204076Spjd 173204076Spjd if (!host_integerp (niter, 1)) 174204076Spjd return false; 175204076Spjd n_unroll = tree_low_cst (niter, 1); 176204076Spjd 177204076Spjd max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES); 178204076Spjd if (n_unroll > max_unroll) 179204076Spjd return false; 180204076Spjd 181204076Spjd if (n_unroll) 182204076Spjd { 183204076Spjd if (ul == UL_SINGLE_ITER) 184204076Spjd return false; 185204076Spjd 186223181Strociny ninsns = tree_num_loop_insns (loop); 187220271Spjd 188220271Spjd if (n_unroll * ninsns 189220271Spjd > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)) 190223181Strociny return false; 191220271Spjd 192204076Spjd if (ul == UL_NO_GROWTH) 193204076Spjd { 194204076Spjd unr_insns = estimated_unrolled_size (ninsns, n_unroll); 195204076Spjd 196204076Spjd if (dump_file && (dump_flags & TDF_DETAILS)) 197204076Spjd { 198204076Spjd fprintf (dump_file, " Loop size: %d\n", (int) ninsns); 199204076Spjd fprintf (dump_file, " Estimated size after unrolling: %d\n", 200204076Spjd (int) unr_insns); 201204076Spjd } 202204076Spjd 203204076Spjd if (unr_insns > ninsns) 204204076Spjd { 205204076Spjd if (dump_file && (dump_flags & TDF_DETAILS)) 206204076Spjd fprintf (dump_file, "Not unrolling loop %d:\n", loop->num); 207204076Spjd return false; 208204076Spjd } 209204076Spjd } 210204076Spjd } 211204076Spjd 212204076Spjd if (exit->flags & EDGE_TRUE_VALUE) 213204076Spjd { 214204076Spjd dont_exit = boolean_false_node; 215204076Spjd do_exit = boolean_true_node; 216204076Spjd } 217204076Spjd else 218204076Spjd { 219204076Spjd dont_exit = boolean_true_node; 220204076Spjd do_exit = boolean_false_node; 221204076Spjd } 222204076Spjd cond = last_stmt (exit->src); 223204076Spjd 224204076Spjd if (n_unroll) 225204076Spjd { 226204076Spjd sbitmap wont_exit; 227204076Spjd edge *edges_to_remove = XNEWVEC (edge, n_unroll); 228204076Spjd unsigned int n_to_remove = 0; 229204076Spjd 230204076Spjd old_cond = COND_EXPR_COND (cond); 231204076Spjd COND_EXPR_COND (cond) = dont_exit; 232204076Spjd update_stmt (cond); 233204076Spjd initialize_original_copy_tables (); 234204076Spjd 235204076Spjd wont_exit = sbitmap_alloc (n_unroll + 1); 236204076Spjd sbitmap_ones (wont_exit); 237204076Spjd RESET_BIT (wont_exit, 0); 238204076Spjd 239204076Spjd if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), 240204076Spjd loops, n_unroll, wont_exit, 241204076Spjd exit, edges_to_remove, 242204076Spjd &n_to_remove, 243204076Spjd DLTHE_FLAG_UPDATE_FREQ 244204076Spjd | DLTHE_FLAG_COMPLETTE_PEEL)) 245204076Spjd { 246204076Spjd COND_EXPR_COND (cond) = old_cond; 247204076Spjd update_stmt (cond); 248204076Spjd free_original_copy_tables (); 249204076Spjd free (wont_exit); 250214284Spjd free (edges_to_remove); 251214284Spjd return false; 252214284Spjd } 253214284Spjd free (wont_exit); 254204076Spjd free (edges_to_remove); 255218138Spjd free_original_copy_tables (); 256204076Spjd } 257204076Spjd 258204076Spjd COND_EXPR_COND (cond) = do_exit; 259214284Spjd update_stmt (cond); 260214284Spjd 261214284Spjd update_ssa (TODO_update_ssa); 262214284Spjd 263214284Spjd if (dump_file && (dump_flags & TDF_DETAILS)) 264214284Spjd fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num); 265214284Spjd 266220865Spjd return true; 267204076Spjd} 268219830Spjd 269219830Spjd/* Adds a canonical induction variable to LOOP if suitable. LOOPS is the loops 270219830Spjd tree. CREATE_IV is true if we may create a new iv. UL determines 271219830Spjd which loops we are allowed to completely unroll. If TRY_EVAL is true, we try 272219830Spjd to determine the number of iterations of a loop by direct evaluation. 273219830Spjd Returns true if cfg is changed. */ 274219830Spjd 275219830Spjdstatic bool 276219830Spjdcanonicalize_loop_induction_variables (struct loops *loops, struct loop *loop, 277219830Spjd bool create_iv, enum unroll_level ul, 278219830Spjd bool try_eval) 279219830Spjd{ 280219831Spjd edge exit = NULL; 281219830Spjd tree niter; 282204076Spjd 283204076Spjd niter = number_of_iterations_in_loop (loop); 284204076Spjd if (TREE_CODE (niter) == INTEGER_CST) 285204076Spjd { 286219843Spjd exit = loop->single_exit; 287204076Spjd if (!just_once_each_iteration_p (loop, exit->src)) 288204076Spjd return false; 289204076Spjd 290204076Spjd /* The result of number_of_iterations_in_loop is by one higher than 291204076Spjd we expect (i.e. it returns number of executions of the exit 292204076Spjd condition, not of the loop latch edge). */ 293204076Spjd niter = fold_build2 (MINUS_EXPR, TREE_TYPE (niter), niter, 294204076Spjd build_int_cst (TREE_TYPE (niter), 1)); 295204076Spjd } 296204076Spjd else 297204076Spjd { 298204076Spjd /* If the loop has more than one exit, try checking all of them 299204076Spjd for # of iterations determinable through scev. */ 300204076Spjd if (!loop->single_exit) 301204076Spjd niter = find_loop_niter (loop, &exit); 302204076Spjd 303204076Spjd /* Finally if everything else fails, try brute force evaluation. */ 304204076Spjd if (try_eval 305204076Spjd && (chrec_contains_undetermined (niter) 306204076Spjd || TREE_CODE (niter) != INTEGER_CST)) 307204076Spjd niter = find_loop_niter_by_eval (loop, &exit); 308204076Spjd 309204076Spjd if (chrec_contains_undetermined (niter) 310204076Spjd || TREE_CODE (niter) != INTEGER_CST) 311204076Spjd return false; 312204076Spjd } 313204076Spjd 314204076Spjd if (dump_file && (dump_flags & TDF_DETAILS)) 315204076Spjd { 316204076Spjd fprintf (dump_file, "Loop %d iterates ", loop->num); 317204076Spjd print_generic_expr (dump_file, niter, TDF_SLIM); 318204076Spjd fprintf (dump_file, " times.\n"); 319204076Spjd } 320204076Spjd 321204076Spjd if (try_unroll_loop_completely (loops, loop, exit, niter, ul)) 322204076Spjd return true; 323204076Spjd 324204076Spjd if (create_iv) 325204076Spjd create_canonical_iv (loop, exit, niter); 326204076Spjd 327204076Spjd return false; 328204076Spjd} 329218138Spjd 330204076Spjd/* The main entry point of the pass. Adds canonical induction variables 331204076Spjd to the suitable LOOPS. */ 332204076Spjd 333204076Spjdunsigned int 334204076Spjdcanonicalize_induction_variables (struct loops *loops) 335204076Spjd{ 336204076Spjd unsigned i; 337204076Spjd struct loop *loop; 338204076Spjd bool changed = false; 339204076Spjd 340204076Spjd for (i = 1; i < loops->num; i++) 341204076Spjd { 342204076Spjd loop = loops->parray[i]; 343204076Spjd 344204076Spjd if (loop) 345204076Spjd changed |= canonicalize_loop_induction_variables (loops, loop, 346204076Spjd true, UL_SINGLE_ITER, 347204076Spjd true); 348220007Spjd } 349204076Spjd 350214276Spjd /* Clean up the information about numbers of iterations, since brute force 351204076Spjd evaluation could reveal new information. */ 352204076Spjd scev_reset (); 353214275Spjd 354214275Spjd if (changed) 355209182Spjd return TODO_cleanup_cfg; 356223181Strociny return 0; 357220271Spjd} 358220271Spjd 359220271Spjd/* Unroll LOOPS completely if they iterate just few times. Unless 360223181Strociny MAY_INCREASE_SIZE is true, perform the unrolling only if the 361204076Spjd size of the code does not increase. */ 362204076Spjd 363204076Spjdunsigned int 364212038Spjdtree_unroll_loops_completely (struct loops *loops, bool may_increase_size) 365204076Spjd{ 366204076Spjd unsigned i; 367204076Spjd struct loop *loop; 368204076Spjd bool changed = false; 369204076Spjd enum unroll_level ul; 370204076Spjd 371204076Spjd for (i = 1; i < loops->num; i++) 372213009Spjd { 373204076Spjd loop = loops->parray[i]; 374204076Spjd 375219482Strociny if (!loop) 376204076Spjd continue; 377204076Spjd 378204076Spjd if (may_increase_size && maybe_hot_bb_p (loop->header)) 379204076Spjd ul = UL_ALL; 380219818Spjd else 381204076Spjd ul = UL_NO_GROWTH; 382204076Spjd changed |= canonicalize_loop_induction_variables (loops, loop, 383204076Spjd false, ul, 384204076Spjd !flag_tree_loop_ivcanon); 385212038Spjd } 386212038Spjd 387212038Spjd /* Clean up the information about numbers of iterations, since complete 388219818Spjd unrolling might have invalidated it. */ 389212038Spjd scev_reset (); 390212038Spjd 391212038Spjd if (changed) 392212038Spjd return TODO_cleanup_cfg; 393204076Spjd return 0; 394204076Spjd} 395204076Spjd 396204076Spjd/* Checks whether LOOP is empty. */ 397204076Spjd 398204076Spjdstatic bool 399204076Spjdempty_loop_p (struct loop *loop) 400204076Spjd{ 401204076Spjd edge exit; 402204076Spjd struct tree_niter_desc niter; 403204076Spjd tree phi, def; 404204076Spjd basic_block *body; 405204076Spjd block_stmt_iterator bsi; 406212038Spjd unsigned i; 407212038Spjd tree stmt; 408218043Spjd 409218043Spjd /* If the loop has multiple exits, it is too hard for us to handle. 410204076Spjd Similarly, if the exit is not dominating, we cannot determine 411204076Spjd whether the loop is not infinite. */ 412204076Spjd exit = single_dom_exit (loop); 413211977Spjd if (!exit) 414211984Spjd return false; 415218043Spjd 416219482Strociny /* The loop must be finite. */ 417211984Spjd if (!number_of_iterations_exit (loop, exit, &niter, false)) 418218043Spjd return false; 419218043Spjd 420218043Spjd /* Values of all loop exit phi nodes must be invariants. */ 421218043Spjd for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) 422218043Spjd { 423204076Spjd if (!is_gimple_reg (PHI_RESULT (phi))) 424218045Spjd continue; 425218045Spjd 426218043Spjd def = PHI_ARG_DEF_FROM_EDGE (phi, exit); 427219482Strociny 428218043Spjd if (!expr_invariant_in_loop_p (loop, def)) 429220005Spjd return false; 430204076Spjd } 431213009Spjd 432213009Spjd /* And there should be no memory modifying or from other reasons 433210880Spjd unremovable statements. */ 434207371Spjd body = get_loop_body (loop); 435219721Strociny for (i = 0; i < loop->num_nodes; i++) 436207371Spjd { 437207371Spjd /* Irreducible region might be infinite. */ 438207371Spjd if (body[i]->flags & BB_IRREDUCIBLE_LOOP) 439207371Spjd { 440204076Spjd free (body); 441213007Spjd return false; 442213007Spjd } 443221899Spjd 444218049Spjd for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) 445218214Spjd { 446218049Spjd stmt = bsi_stmt (bsi); 447213007Spjd if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS) 448213007Spjd || stmt_ann (stmt)->has_volatile_ops) 449213007Spjd { 450213007Spjd free (body); 451213007Spjd return false; 452213007Spjd } 453213007Spjd 454213007Spjd /* Also, asm statements and calls may have side effects and we 455213007Spjd cannot change the number of times they are executed. */ 456218138Spjd switch (TREE_CODE (stmt)) 457213007Spjd { 458204076Spjd case RETURN_EXPR: 459212038Spjd case MODIFY_EXPR: 460204076Spjd stmt = get_call_expr_in (stmt); 461204076Spjd if (!stmt) 462218138Spjd break; 463204076Spjd 464218138Spjd case CALL_EXPR: 465213007Spjd if (TREE_SIDE_EFFECTS (stmt)) 466204076Spjd { 467204076Spjd free (body); 468204076Spjd return false; 469204076Spjd } 470204076Spjd break; 471204076Spjd 472204076Spjd case ASM_EXPR: 473204076Spjd /* We cannot remove volatile assembler. */ 474204076Spjd if (ASM_VOLATILE_P (stmt)) 475204076Spjd { 476204076Spjd free (body); 477204076Spjd return false; 478204076Spjd } 479204076Spjd break; 480204076Spjd 481204076Spjd default: 482204076Spjd break; 483204076Spjd } 484204076Spjd } 485204076Spjd } 486204076Spjd free (body); 487204076Spjd 488204076Spjd return true; 489204076Spjd} 490204076Spjd 491204076Spjd/* Remove LOOP by making it exit in the first iteration. */ 492204076Spjd 493204076Spjdstatic void 494204076Spjdremove_empty_loop (struct loop *loop) 495204076Spjd{ 496204076Spjd edge exit = single_dom_exit (loop), non_exit; 497204076Spjd tree cond_stmt = last_stmt (exit->src); 498211882Spjd tree do_exit; 499211882Spjd basic_block *body; 500211882Spjd unsigned n_before, freq_in, freq_h; 501204076Spjd gcov_type exit_count = exit->count; 502204076Spjd 503204076Spjd non_exit = EDGE_SUCC (exit->src, 0); 504204076Spjd if (non_exit == exit) 505204076Spjd non_exit = EDGE_SUCC (exit->src, 1); 506204076Spjd 507204076Spjd if (exit->flags & EDGE_TRUE_VALUE) 508204076Spjd do_exit = boolean_true_node; 509204076Spjd else 510204076Spjd do_exit = boolean_false_node; 511204076Spjd 512204076Spjd COND_EXPR_COND (cond_stmt) = do_exit; 513204076Spjd update_stmt (cond_stmt); 514204076Spjd 515204076Spjd /* Let us set the probabilities of the edges coming from the exit block. */ 516204076Spjd exit->probability = REG_BR_PROB_BASE; 517204076Spjd non_exit->probability = 0; 518204076Spjd non_exit->count = 0; 519204076Spjd 520204076Spjd /* Update frequencies and counts. Everything before 521222164Spjd the exit needs to be scaled FREQ_IN/FREQ_H times, 522211882Spjd where FREQ_IN is the frequency of the entry edge 523211882Spjd and FREQ_H is the frequency of the loop header. 524204076Spjd Everything after the exit has zero frequency. */ 525204076Spjd freq_h = loop->header->frequency; 526204076Spjd freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop)); 527204076Spjd if (freq_h != 0) 528204076Spjd { 529204076Spjd body = get_loop_body_in_dom_order (loop); 530204076Spjd for (n_before = 1; n_before <= loop->num_nodes; n_before++) 531204076Spjd if (body[n_before - 1] == exit->src) 532204076Spjd break; 533204076Spjd scale_bbs_frequencies_int (body, n_before, freq_in, freq_h); 534204076Spjd scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before, 535204076Spjd 0, 1); 536204076Spjd free (body); 537204076Spjd } 538204076Spjd 539204076Spjd /* Number of executions of exit is not changed, thus we need to restore 540204076Spjd the original value. */ 541204076Spjd exit->count = exit_count; 542204076Spjd} 543204076Spjd 544204076Spjd/* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED 545204076Spjd is set to true if LOOP or any of its subloops is removed. */ 546204076Spjd 547204076Spjdstatic bool 548204076Spjdtry_remove_empty_loop (struct loop *loop, bool *changed) 549204076Spjd{ 550204076Spjd bool nonempty_subloop = false; 551204076Spjd struct loop *sub; 552204076Spjd 553204076Spjd /* First, all subloops must be removed. */ 554204076Spjd for (sub = loop->inner; sub; sub = sub->next) 555204076Spjd nonempty_subloop |= !try_remove_empty_loop (sub, changed); 556204076Spjd 557204076Spjd if (nonempty_subloop || !empty_loop_p (loop)) 558204076Spjd return false; 559204076Spjd 560204076Spjd remove_empty_loop (loop); 561204076Spjd *changed = true; 562204076Spjd return true; 563204076Spjd} 564204076Spjd 565204076Spjd/* Remove the empty LOOPS. */ 566204076Spjd 567204076Spjdunsigned int 568204076Spjdremove_empty_loops (struct loops *loops) 569204076Spjd{ 570204076Spjd bool changed = false; 571204076Spjd struct loop *loop; 572204076Spjd 573204076Spjd for (loop = loops->tree_root->inner; loop; loop = loop->next) 574204076Spjd try_remove_empty_loop (loop, &changed); 575204076Spjd 576204076Spjd if (changed) 577204076Spjd { 578204076Spjd scev_reset (); 579204076Spjd return TODO_cleanup_cfg; 580204076Spjd } 581204076Spjd return 0; 582212899Spjd} 583211984Spjd