LCOV - code coverage report
Current view: top level - gcc - tree-ssa-loop-manip.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 97.3 % 673 655
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 31 31
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* High-level loop manipulation functions.
       2              :    Copyright (C) 2004-2026 Free Software Foundation, Inc.
       3              : 
       4              : This file is part of GCC.
       5              : 
       6              : GCC is free software; you can redistribute it and/or modify it
       7              : under the terms of the GNU General Public License as published by the
       8              : Free Software Foundation; either version 3, or (at your option) any
       9              : later version.
      10              : 
      11              : GCC is distributed in the hope that it will be useful, but WITHOUT
      12              : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14              : for more details.
      15              : 
      16              : You should have received a copy of the GNU General Public License
      17              : along with GCC; see the file COPYING3.  If not see
      18              : <http://www.gnu.org/licenses/>.  */
      19              : 
      20              : #include "config.h"
      21              : #include "system.h"
      22              : #include "coretypes.h"
      23              : #include "backend.h"
      24              : #include "tree.h"
      25              : #include "gimple.h"
      26              : #include "cfghooks.h"
      27              : #include "tree-pass.h"        /* ??? for TODO_update_ssa but this isn't a pass.  */
      28              : #include "ssa.h"
      29              : #include "gimple-pretty-print.h"
      30              : #include "fold-const.h"
      31              : #include "cfganal.h"
      32              : #include "gimplify.h"
      33              : #include "gimple-iterator.h"
      34              : #include "gimplify-me.h"
      35              : #include "tree-cfg.h"
      36              : #include "tree-ssa-loop-ivopts.h"
      37              : #include "tree-ssa-loop-manip.h"
      38              : #include "tree-ssa-loop-niter.h"
      39              : #include "tree-ssa-loop.h"
      40              : #include "tree-into-ssa.h"
      41              : #include "tree-ssa.h"
      42              : #include "cfgloop.h"
      43              : #include "tree-scalar-evolution.h"
      44              : #include "tree-inline.h"
      45              : 
      46              : /* All bitmaps for rewriting into loop-closed SSA go on this obstack,
      47              :    so that we can free them all at once.  */
      48              : static bitmap_obstack loop_renamer_obstack;
      49              : 
      50              : /* Reset debug binds outside LOOP that use values defined in the NUM_NODES
      51              :    basic blocks in BBS.  */
      52              : 
      53              : void
      54        34597 : reset_debug_uses_outside_loop (class loop *loop, basic_block *bbs,
      55              :                                unsigned num_nodes)
      56              : {
      57       106115 :   for (unsigned i = 0; i < num_nodes; ++i)
      58              :     {
      59        71518 :       basic_block bb = bbs[i];
      60        71518 :       imm_use_iterator ui;
      61        71518 :       gimple *use_stmt;
      62       169589 :       for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
      63        98071 :            gsi_next (&gpi))
      64              :         {
      65       310710 :           FOR_EACH_IMM_USE_STMT (use_stmt, ui,
      66              :                                  gimple_phi_result (gpi.phi ()))
      67       234455 :             if (gimple_debug_bind_p (use_stmt)
      68        21816 :                 && loop != gimple_bb (use_stmt)->loop_father
      69        21832 :                 && !flow_loop_nested_p (loop,
      70           16 :                                         gimple_bb (use_stmt)->loop_father))
      71              :               {
      72            2 :                 gimple_debug_bind_reset_value (use_stmt);
      73            2 :                 update_stmt (use_stmt);
      74        98071 :               }
      75              :         }
      76       657759 :       for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
      77       514723 :            gsi_next (&gsi))
      78              :         {
      79       514723 :           ssa_op_iter op_iter;
      80       514723 :           def_operand_p def_p;
      81       833072 :           FOR_EACH_SSA_DEF_OPERAND (def_p, gsi_stmt (gsi), op_iter, SSA_OP_DEF)
      82       794102 :             FOR_EACH_IMM_USE_STMT (use_stmt, ui, DEF_FROM_PTR (def_p))
      83       512834 :               if (gimple_debug_bind_p (use_stmt)
      84        37081 :                   && loop != gimple_bb (use_stmt)->loop_father
      85        37109 :                   && !flow_loop_nested_p (loop,
      86           28 :                                           gimple_bb (use_stmt)->loop_father))
      87              :                 {
      88            1 :                   gimple_debug_bind_reset_value (use_stmt);
      89            1 :                   update_stmt (use_stmt);
      90       318349 :                 }
      91              :         }
      92              :     }
      93        34597 : }
      94              : 
      95              : /* Insert IV increment statements STMTS before or after INCR_POS;
      96              :    AFTER selects which.  INCR_POS and AFTER can be computed using
      97              :    standard_iv_increment_position.  */
      98              : 
      99              : void
     100      1056994 : insert_iv_increment (gimple_stmt_iterator *incr_pos, bool after,
     101              :                      gimple_seq stmts)
     102              : {
     103              :   /* Prevent the increment from inheriting a bogus location if it is not put
     104              :      immediately after a statement whose location is known.  */
     105      1056994 :   if (after)
     106              :     {
     107        12353 :       gimple_stmt_iterator gsi = *incr_pos;
     108        12353 :       if (!gsi_end_p (gsi))
     109        10856 :         gsi_next_nondebug (&gsi);
     110        12353 :       if (gsi_end_p (gsi))
     111              :         {
     112        12353 :           edge e = single_succ_edge (gsi_bb (*incr_pos));
     113        12353 :           gimple_seq_set_location (stmts, e->goto_locus);
     114              :         }
     115        12353 :       gsi_insert_seq_after (incr_pos, stmts, GSI_NEW_STMT);
     116              :     }
     117              :   else
     118              :     {
     119      1044641 :       gimple_stmt_iterator gsi = *incr_pos;
     120      1044641 :       if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
     121            0 :         gsi_next_nondebug (&gsi);
     122      1044641 :       if (!gsi_end_p (gsi))
     123      1044137 :         gimple_seq_set_location (stmts, gimple_location (gsi_stmt (gsi)));
     124      1044641 :       gsi_insert_seq_before (incr_pos, stmts, GSI_NEW_STMT);
     125              :     }
     126      1056994 : }
     127              : 
     128              : /* Creates an induction variable with value BASE (+/-) STEP * iteration in LOOP.
     129              :    If INCR_OP is PLUS_EXPR, the induction variable is BASE + STEP * iteration.
     130              :    If INCR_OP is MINUS_EXPR, the induction variable is BASE - STEP * iteration.
     131              :    It is expected that neither BASE nor STEP are shared with other expressions
     132              :    (unless the sharing rules allow this).  Use VAR as a base var_decl for it
     133              :    (if NULL, a new temporary will be created).  The increment will occur at
     134              :    INCR_POS (after it if AFTER is true, before it otherwise).  INCR_POS and
     135              :    AFTER can be computed using standard_iv_increment_position.  The ssa versions
     136              :    of the variable before and after increment will be stored in VAR_BEFORE and
     137              :    VAR_AFTER (unless they are NULL).  If LOOP_INVARIANT is true then the
     138              :    calculation step will be added to the pre-header.  Otherwise, the step
     139              :    calculation is added to incr_pos.  */
     140              : 
     141              : void
     142      1040327 : create_iv (tree base, tree_code incr_op, tree step, tree var, class loop *loop,
     143              :            gimple_stmt_iterator *incr_pos, bool after, tree *var_before,
     144              :            tree *var_after, bool loop_invariant)
     145              : {
     146      1040327 :   gphi *phi;
     147      1040327 :   tree initial, step1;
     148      1040327 :   gimple_seq stmts;
     149      1040327 :   tree vb, va;
     150      1040327 :   gcc_assert (incr_op == PLUS_EXPR || incr_op == MINUS_EXPR);
     151      1040327 :   edge pe = loop_preheader_edge (loop);
     152              : 
     153      1040327 :   if (var != NULL_TREE)
     154              :     {
     155       641547 :       vb = make_ssa_name (var);
     156       641547 :       va = make_ssa_name (var);
     157              :     }
     158              :   else
     159              :     {
     160       398780 :       vb = make_temp_ssa_name (TREE_TYPE (base), NULL, "ivtmp");
     161       398780 :       va = make_temp_ssa_name (TREE_TYPE (base), NULL, "ivtmp");
     162              :     }
     163      1040327 :   if (var_before)
     164       715033 :     *var_before = vb;
     165      1040327 :   if (var_after)
     166      1032731 :     *var_after = va;
     167              : 
     168              :   /* For easier readability of the created code, produce MINUS_EXPRs
     169              :      when suitable.  */
     170      1040327 :   if (TREE_CODE (step) == INTEGER_CST)
     171              :     {
     172       976828 :       if (TYPE_UNSIGNED (TREE_TYPE (step)))
     173              :         {
     174       974796 :           step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
     175       974796 :           if (tree_int_cst_lt (step1, step))
     176              :             {
     177       341800 :               incr_op = (incr_op == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR);
     178              :               step = step1;
     179              :             }
     180              :         }
     181              :       else
     182              :         {
     183         2032 :           if (!tree_expr_nonnegative_p (step)
     184         2032 :               && may_negate_without_overflow_p (step))
     185              :             {
     186           21 :               incr_op = (incr_op == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR);
     187           21 :               step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
     188              :             }
     189              :         }
     190              :     }
     191      1040327 :   if (POINTER_TYPE_P (TREE_TYPE (base)))
     192              :     {
     193       140505 :       if (TREE_CODE (base) == ADDR_EXPR)
     194        50631 :         mark_addressable (TREE_OPERAND (base, 0));
     195       140505 :       step = convert_to_ptrofftype (step);
     196       140505 :       if (incr_op == MINUS_EXPR)
     197         3028 :         step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
     198              :       incr_op = POINTER_PLUS_EXPR;
     199              :     }
     200              : 
     201      1040327 :   gimple_seq incr_stmts = nullptr;
     202              :   /* Gimplify the step if necessary.  */
     203      1040327 :   if (loop_invariant)
     204              :     {
     205      1040327 :       step = force_gimple_operand (step, &stmts, true, NULL_TREE);
     206      1040327 :       if (stmts)
     207            0 :         gsi_insert_seq_on_edge_immediate (pe, stmts);
     208              :     }
     209              :   else
     210            0 :     step = force_gimple_operand (step, &incr_stmts, true, NULL_TREE);
     211              : 
     212      1040327 :   gimple_seq_add_stmt (&incr_stmts,
     213      1040327 :                        gimple_build_assign (va, incr_op, vb, step));
     214      1040327 :   insert_iv_increment (incr_pos, after, incr_stmts);
     215              : 
     216      1040327 :   initial = force_gimple_operand (base, &stmts, true, var);
     217      1040327 :   if (stmts)
     218       280512 :     gsi_insert_seq_on_edge_immediate (pe, stmts);
     219              : 
     220      1040327 :   phi = create_phi_node (vb, loop->header);
     221      1040327 :   add_phi_arg (phi, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION);
     222      1040327 :   add_phi_arg (phi, va, loop_latch_edge (loop), UNKNOWN_LOCATION);
     223      1040327 : }
     224              : 
     225              : /* Return the innermost superloop LOOP of USE_LOOP that is a superloop of
     226              :    both DEF_LOOP and USE_LOOP.  */
     227              : 
     228              : static inline class loop *
     229       148222 : find_sibling_superloop (class loop *use_loop, class loop *def_loop)
     230              : {
     231       148222 :   unsigned ud = loop_depth (use_loop);
     232       148222 :   unsigned dd = loop_depth (def_loop);
     233       148222 :   gcc_assert (ud > 0 && dd > 0);
     234       148222 :   if (ud > dd)
     235        18852 :     use_loop = superloop_at_depth (use_loop, dd);
     236       148222 :   if (ud < dd)
     237        27742 :     def_loop = superloop_at_depth (def_loop, ud);
     238       150993 :   while (loop_outer (use_loop) != loop_outer (def_loop))
     239              :     {
     240         2771 :       use_loop = loop_outer (use_loop);
     241         2771 :       def_loop = loop_outer (def_loop);
     242         2771 :       gcc_assert (use_loop && def_loop);
     243              :     }
     244       148222 :   return use_loop;
     245              : }
     246              : 
     247              : /* DEF_BB is a basic block containing a DEF that needs rewriting into
     248              :    loop-closed SSA form.  USE_BLOCKS is the set of basic blocks containing
     249              :    uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in
     250              :    USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_BB).
     251              :    ALL_EXITS[I] is the set of all basic blocks that exit loop I.
     252              :    DEF_LOOP_EXITS is a bitmap of loop exit blocks that exit the loop
     253              :    containing DEF_BB or its outer loops.
     254              : 
     255              :    Compute the subset of loop exit destinations that exit the loop
     256              :    containing DEF_BB or one of its loop fathers, in which DEF is live.
     257              :    This set is returned in the bitmap LIVE_EXITS.
     258              : 
     259              :    Instead of computing the complete livein set of the def, we use the loop
     260              :    nesting tree as a form of poor man's structure analysis.  This greatly
     261              :    speeds up the analysis, which is important because this function may be
     262              :    called on all SSA names that need rewriting, one at a time.  */
     263              : 
     264              : static void
     265      3247368 : compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
     266              :                          basic_block def_bb, bitmap def_loop_exits)
     267              : {
     268      3247368 :   unsigned i;
     269      3247368 :   bitmap_iterator bi;
     270      3247368 :   class loop *def_loop = def_bb->loop_father;
     271      3247368 :   unsigned def_loop_depth = loop_depth (def_loop);
     272              : 
     273              :   /* Normally the work list size is bounded by the number of basic
     274              :      blocks in the largest loop.  We don't know this number, but we
     275              :      can be fairly sure that it will be relatively small.  */
     276      3247368 :   auto_vec<basic_block, 8> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
     277              : 
     278      7818044 :   EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi)
     279              :     {
     280      4570676 :       basic_block use_bb = BASIC_BLOCK_FOR_FN (cfun, i);
     281      4570676 :       class loop *use_loop = use_bb->loop_father;
     282      4570676 :       gcc_checking_assert (def_loop != use_loop
     283              :                            && ! flow_loop_nested_p (def_loop, use_loop));
     284      4570676 :       if (! flow_loop_nested_p (use_loop, def_loop))
     285       124190 :         use_bb = find_sibling_superloop (use_loop, def_loop)->header;
     286      4570676 :       if (bitmap_set_bit (live_exits, use_bb->index))
     287      4527023 :         worklist.safe_push (use_bb);
     288              :     }
     289              : 
     290              :   /* Iterate until the worklist is empty.  */
     291     10037496 :   while (! worklist.is_empty ())
     292              :     {
     293      6790128 :       edge e;
     294      6790128 :       edge_iterator ei;
     295              : 
     296              :       /* Pull a block off the worklist.  */
     297      6790128 :       basic_block bb = worklist.pop ();
     298              : 
     299              :       /* Make sure we have at least enough room in the work list
     300              :          for all predecessors of this block.  */
     301      6790128 :       worklist.reserve (EDGE_COUNT (bb->preds));
     302              : 
     303              :       /* For each predecessor block.  */
     304     14653035 :       FOR_EACH_EDGE (e, ei, bb->preds)
     305              :         {
     306      7862907 :           basic_block pred = e->src;
     307      7862907 :           class loop *pred_loop = pred->loop_father;
     308      7862907 :           unsigned pred_loop_depth = loop_depth (pred_loop);
     309      7862907 :           bool pred_visited;
     310              : 
     311              :           /* We should have met DEF_BB along the way.  */
     312      7862907 :           gcc_assert (pred != ENTRY_BLOCK_PTR_FOR_FN (cfun));
     313              : 
     314      7862907 :           if (pred_loop_depth >= def_loop_depth)
     315              :             {
     316      4785444 :               if (pred_loop_depth > def_loop_depth)
     317       155485 :                 pred_loop = superloop_at_depth (pred_loop, def_loop_depth);
     318              :               /* If we've reached DEF_LOOP, our train ends here.  */
     319      4785444 :               if (pred_loop == def_loop)
     320      5599802 :                 continue;
     321              :             }
     322      3077463 :           else if (! flow_loop_nested_p (pred_loop, def_loop))
     323        24032 :             pred = find_sibling_superloop (pred_loop, def_loop)->header;
     324              : 
     325              :           /* Add PRED to the LIVEIN set.  PRED_VISITED is true if
     326              :              we had already added PRED to LIVEIN before.  */
     327      3929434 :           pred_visited = !bitmap_set_bit (live_exits, pred->index);
     328              : 
     329              :           /* If we have visited PRED before, don't add it to the worklist.
     330              :              If BB dominates PRED, then we're probably looking at a loop.
     331              :              We're only interested in looking up in the dominance tree
     332              :              because DEF_BB dominates all the uses.  */
     333      3929434 :           if (pred_visited || dominated_by_p (CDI_DOMINATORS, pred, bb))
     334      1666329 :             continue;
     335              : 
     336      2263105 :           worklist.quick_push (pred);
     337              :         }
     338              :     }
     339              : 
     340      3247368 :   bitmap_and_into (live_exits, def_loop_exits);
     341      3247368 : }
     342              : 
     343              : /* Add a loop-closing PHI for VAR in basic block EXIT.  */
     344              : 
     345              : static void
     346      3850817 : add_exit_phi (basic_block exit, tree var)
     347              : {
     348      3850817 :   gphi *phi;
     349      3850817 :   edge e;
     350      3850817 :   edge_iterator ei;
     351              : 
     352              :   /* Check that at least one of the edges entering the EXIT block exits
     353              :      the loop, or a superloop of that loop, that VAR is defined in.  */
     354      3850817 :   if (flag_checking)
     355              :     {
     356      3850715 :       gimple *def_stmt = SSA_NAME_DEF_STMT (var);
     357      3850715 :       basic_block def_bb = gimple_bb (def_stmt);
     358      3860272 :       FOR_EACH_EDGE (e, ei, exit->preds)
     359              :         {
     360      7720544 :           class loop *aloop = find_common_loop (def_bb->loop_father,
     361      3860272 :                                                  e->src->loop_father);
     362      3860272 :           if (!flow_bb_inside_loop_p (aloop, e->dest))
     363              :             break;
     364              :         }
     365      3850715 :       gcc_assert (e);
     366              :     }
     367              : 
     368      3850817 :   phi = create_phi_node (NULL_TREE, exit);
     369      3850817 :   create_new_def_for (var, phi, gimple_phi_result_ptr (phi));
     370      7907925 :   FOR_EACH_EDGE (e, ei, exit->preds)
     371      4057108 :     add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
     372              : 
     373      3850817 :   if (dump_file && (dump_flags & TDF_DETAILS))
     374              :     {
     375         1854 :       fprintf (dump_file, ";; Created LCSSA PHI: ");
     376         1854 :       print_gimple_stmt (dump_file, phi, 0, dump_flags);
     377              :     }
     378      3850817 : }
     379              : 
     380              : /* Add exit phis for VAR that is used in LIVEIN.
     381              :    Exits of the loops are stored in LOOP_EXITS.  Returns the number
     382              :    of PHIs added for VAR.  */
     383              : 
     384              : static unsigned
     385      3247368 : add_exit_phis_var (tree var, bitmap use_blocks, bitmap def_loop_exits)
     386              : {
     387      3247368 :   unsigned index;
     388      3247368 :   bitmap_iterator bi;
     389      3247368 :   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
     390              : 
     391      3247368 :   gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
     392              : 
     393      3247368 :   auto_bitmap live_exits (&loop_renamer_obstack);
     394      3247368 :   compute_live_loop_exits (live_exits, use_blocks, def_bb, def_loop_exits);
     395              : 
     396      3247368 :   unsigned cnt = 0;
     397      7098185 :   EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi)
     398              :     {
     399      3850817 :       add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var);
     400      3850817 :       cnt++;
     401              :     }
     402      3247368 :   return cnt;
     403      3247368 : }
     404              : 
     405              : static int
     406     48311587 : loop_name_cmp (const void *p1, const void *p2)
     407              : {
     408     48311587 :   auto l1 = (const std::pair<int, int> *)p1;
     409     48311587 :   auto l2 = (const std::pair<int, int> *)p2;
     410     48311587 :   if (l1->first < l2->first)
     411              :     return -1;
     412     29060024 :   else if (l1->first > l2->first)
     413     18106701 :     return 1;
     414              :   return 0;
     415              : }
     416              : 
     417              : /* Add exit phis for the names marked in NAMES_TO_RENAME.
     418              :    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
     419              :    names are used are stored in USE_BLOCKS.  Returns whether any name
     420              :    required multiple LC PHI nodes.  */
     421              : 
     422              : static bool
     423       748240 : add_exit_phis (bitmap names_to_rename, bitmap *use_blocks)
     424              : {
     425       748240 :   unsigned i;
     426       748240 :   bitmap_iterator bi;
     427       748240 :   bool multiple_p = false;
     428              : 
     429              :   /* Sort names_to_rename after definition loop so we can avoid re-computing
     430              :      def_loop_exits.  */
     431       748240 :   auto_vec<std::pair<int, int> > names (bitmap_count_bits (names_to_rename));
     432      3995608 :   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
     433              :     {
     434      3247368 :       tree name = ssa_name (i);
     435      3247368 :       loop_p def_loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
     436      3247368 :       names.quick_push (std::make_pair (def_loop->num, i));
     437              :     }
     438       748240 :   names.qsort (loop_name_cmp);
     439              : 
     440       748240 :   auto_bitmap def_loop_exits (&loop_renamer_obstack);
     441       748240 :   loop_p last_def_loop = NULL;
     442      5492088 :   for (auto p : names)
     443              :     {
     444      3247368 :       loop_p def_loop = get_loop (cfun, p.first);
     445      3247368 :       if (def_loop != last_def_loop)
     446              :         {
     447      1794756 :           bitmap_clear (def_loop_exits);
     448      1794756 :           last_def_loop = def_loop;
     449      6004107 :           for (class loop *loop = def_loop; loop != current_loops->tree_root;
     450      2414595 :                loop = loop_outer (loop))
     451      8824378 :             for (auto exit = loop->exits->next; exit->e; exit = exit->next)
     452      6409783 :               bitmap_set_bit (def_loop_exits, exit->e->dest->index);
     453              :         }
     454      3247368 :       if (add_exit_phis_var (ssa_name (p.second), use_blocks[p.second],
     455              :                              def_loop_exits) > 1)
     456       359472 :         multiple_p = true;
     457              :     }
     458              : 
     459       748240 :   return multiple_p;
     460       748240 : }
     461              : 
     462              : /* For USE in BB, if it is used outside of the loop it is defined in,
     463              :    mark it for rewrite.  Record basic block BB where it is used
     464              :    to USE_BLOCKS.  Record the ssa name index to NEED_PHIS bitmap.
     465              :    Note that for USEs in phis, BB should be the src of the edge corresponding to
     466              :    the use, rather than the bb containing the phi.  */
     467              : 
     468              : static void
     469    166658040 : find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
     470              :                          bitmap need_phis)
     471              : {
     472    166658040 :   unsigned ver;
     473    166658040 :   basic_block def_bb;
     474    166658040 :   class loop *def_loop;
     475              : 
     476    166658040 :   if (TREE_CODE (use) != SSA_NAME)
     477              :     return;
     478              : 
     479    160672202 :   ver = SSA_NAME_VERSION (use);
     480    160672202 :   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
     481    160672202 :   if (!def_bb)
     482              :     return;
     483    149114334 :   def_loop = def_bb->loop_father;
     484              : 
     485              :   /* If the definition is not inside a loop, it is not interesting.  */
     486    149114334 :   if (!loop_outer (def_loop))
     487              :     return;
     488              : 
     489              :   /* If the use is not outside of the loop it is defined in, it is not
     490              :      interesting.  */
     491     78081678 :   if (flow_bb_inside_loop_p (def_loop, bb))
     492              :     return;
     493              : 
     494              :   /* If we're seeing VER for the first time, we still have to allocate
     495              :      a bitmap for its uses.  */
     496      5224565 :   if (bitmap_set_bit (need_phis, ver))
     497      3247368 :     use_blocks[ver] = BITMAP_ALLOC (&loop_renamer_obstack);
     498      5224565 :   bitmap_set_bit (use_blocks[ver], bb->index);
     499              : }
     500              : 
     501              : /* For uses matching USE_FLAGS in STMT, mark names that are used outside of the
     502              :    loop they are defined to rewrite.  Record the set of blocks in which the ssa
     503              :    names are used to USE_BLOCKS, and the ssa names themselves to NEED_PHIS.  */
     504              : 
     505              : static void
     506    222550250 : find_uses_to_rename_stmt (gimple *stmt, bitmap *use_blocks, bitmap need_phis,
     507              :                           int use_flags)
     508              : {
     509    222550250 :   ssa_op_iter iter;
     510    222550250 :   tree var;
     511    222550250 :   basic_block bb = gimple_bb (stmt);
     512              : 
     513    222550250 :   if (is_gimple_debug (stmt))
     514    131397526 :     return;
     515              : 
     516              :   /* FOR_EACH_SSA_TREE_OPERAND iterator does not allows SSA_OP_VIRTUAL_USES
     517              :      only.  */
     518     91152724 :   if (use_flags == SSA_OP_VIRTUAL_USES)
     519              :     {
     520     91152724 :       tree vuse = gimple_vuse (stmt);
     521            0 :       if (vuse != NULL_TREE)
     522            0 :         find_uses_to_rename_use (bb, gimple_vuse (stmt), use_blocks, need_phis);
     523              :     }
     524              :   else
     525    220030620 :     FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, use_flags)
     526    128877896 :       find_uses_to_rename_use (bb, var, use_blocks, need_phis);
     527              : }
     528              : 
     529              : /* Marks names matching USE_FLAGS that are used in BB and outside of the loop
     530              :    they are defined in for rewrite.  Records the set of blocks in which the ssa
     531              :    names are used to USE_BLOCKS.  Record the SSA names that will
     532              :    need exit PHIs in NEED_PHIS.  */
     533              : 
     534              : static void
     535     30919104 : find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis,
     536              :                         int use_flags)
     537              : {
     538     30919104 :   edge e;
     539     30919104 :   edge_iterator ei;
     540     30919104 :   bool do_virtuals = (use_flags & SSA_OP_VIRTUAL_USES) != 0;
     541     30919104 :   bool do_nonvirtuals = (use_flags & SSA_OP_USE) != 0;
     542              : 
     543     74925578 :   FOR_EACH_EDGE (e, ei, bb->succs)
     544     81786618 :     for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
     545     37780144 :          gsi_next (&bsi))
     546              :       {
     547     37780144 :         gphi *phi = bsi.phi ();
     548     37780144 :         bool virtual_p = virtual_operand_p (gimple_phi_result (phi));
     549     37780144 :         if ((virtual_p && do_virtuals)
     550     22480295 :             || (!virtual_p && do_nonvirtuals))
     551     37780144 :           find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
     552              :                                    use_blocks, need_phis);
     553              :       }
     554              : 
     555    284388458 :   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
     556    222550250 :        gsi_next (&bsi))
     557    222550250 :     find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis,
     558              :                               use_flags);
     559     30919104 : }
     560              : 
     561              : /* Marks names matching USE_FLAGS that are used outside of the loop they are
     562              :    defined in for rewrite.  Records the set of blocks in which the ssa names are
     563              :    used to USE_BLOCKS.  Record the SSA names that will need exit PHIs in
     564              :    NEED_PHIS.  If CHANGED_BBS is not NULL, scan only blocks in this set.  */
     565              : 
     566              : static void
     567      1070301 : find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis,
     568              :                      int use_flags)
     569              : {
     570      1070301 :   basic_block bb;
     571      1070301 :   unsigned index;
     572      1070301 :   bitmap_iterator bi;
     573              : 
     574      1070301 :   if (changed_bbs)
     575        29418 :     EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
     576              :       {
     577        21561 :         bb = BASIC_BLOCK_FOR_FN (cfun, index);
     578        21561 :         if (bb)
     579        21561 :           find_uses_to_rename_bb (bb, use_blocks, need_phis, use_flags);
     580              :       }
     581              :   else
     582     31959987 :     FOR_EACH_BB_FN (bb, cfun)
     583     30897543 :       find_uses_to_rename_bb (bb, use_blocks, need_phis, use_flags);
     584      1070301 : }
     585              : 
     586              : /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
     587              :    phi nodes to ensure that no variable is used outside the loop it is
     588              :    defined in.
     589              : 
     590              :    This strengthening of the basic ssa form has several advantages:
     591              : 
     592              :    1) Updating it during unrolling/peeling/versioning is trivial, since
     593              :       we do not need to care about the uses outside of the loop.
     594              :       The same applies to virtual operands which are also rewritten into
     595              :       loop closed SSA form.  Note that virtual operands are always live
     596              :       until function exit.
     597              :    2) The behavior of all uses of an induction variable is the same.
     598              :       Without this, you need to distinguish the case when the variable
     599              :       is used outside of the loop it is defined in, for example
     600              : 
     601              :       for (i = 0; i < 100; i++)
     602              :         {
     603              :           for (j = 0; j < 100; j++)
     604              :             {
     605              :               k = i + j;
     606              :               use1 (k);
     607              :             }
     608              :           use2 (k);
     609              :         }
     610              : 
     611              :       Looking from the outer loop with the normal SSA form, the first use of k
     612              :       is not well-behaved, while the second one is an induction variable with
     613              :       base 99 and step 1.
     614              : 
     615              :       If CHANGED_BBS is not NULL, we look for uses outside loops only in the
     616              :       basic blocks in this set.
     617              : 
     618              :       USE_FLAGS allows us to specify whether we want virtual, non-virtual or
     619              :       both variables rewritten.
     620              : 
     621              :       UPDATE_FLAG is used in the call to update_ssa.  See
     622              :       TODO_update_ssa* for documentation.  */
     623              : 
     624              : static void
     625      4724951 : rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
     626              :                                 int use_flags)
     627              : {
     628      4724951 :   bitmap *use_blocks;
     629      4724951 :   bitmap names_to_rename;
     630              : 
     631      4724951 :   loops_state_set (LOOP_CLOSED_SSA);
     632      4724951 :   if (number_of_loops (cfun) <= 1)
     633              :     return;
     634              : 
     635              :   /* If the pass has caused the SSA form to be out-of-date, update it
     636              :      now.  */
     637      1070301 :   if (update_flag != 0)
     638      1069915 :     update_ssa (update_flag);
     639          386 :   else if (flag_checking)
     640          386 :     verify_ssa (true, true);
     641              : 
     642      1070301 :   bitmap_obstack_initialize (&loop_renamer_obstack);
     643              : 
     644      1070301 :   names_to_rename = BITMAP_ALLOC (&loop_renamer_obstack);
     645              : 
     646              :   /* Uses of names to rename.  We don't have to initialize this array,
     647              :      because we know that we will only have entries for the SSA names
     648              :      in NAMES_TO_RENAME.  */
     649      2140602 :   use_blocks = XNEWVEC (bitmap, num_ssa_names);
     650      1070301 :   find_uses_to_rename (changed_bbs, use_blocks, names_to_rename, use_flags);
     651              : 
     652      1070301 :   if (!bitmap_empty_p (names_to_rename))
     653              :     {
     654       748240 :       bool release_recorded_exits_p = false;
     655       748240 :       if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
     656              :         {
     657              :           /* Doing one scan over the whole function is cheaper than
     658              :              traversing the loop tree and gathering BBs of each loop.  */
     659            0 :           record_loop_exits ();
     660            0 :           release_recorded_exits_p = true;
     661              :         }
     662              : 
     663              :       /* Add the PHI nodes on exits of the loops for the names we need to
     664              :          rewrite.  When no variable required multiple LC PHI nodes to be
     665              :          inserted then we know that all uses outside of the loop are
     666              :          dominated by the single LC SSA definition and no further PHI
     667              :          node insertions are required.  */
     668       748240 :       bool need_phis_p = add_exit_phis (names_to_rename, use_blocks);
     669              : 
     670       748240 :       if (release_recorded_exits_p)
     671            0 :         release_recorded_exits (cfun);
     672              : 
     673              :       /* Fix up all the names found to be used outside their original
     674              :          loops.  */
     675      1348641 :       update_ssa (need_phis_p ? TODO_update_ssa : TODO_update_ssa_no_phi);
     676              :     }
     677              : 
     678      1070301 :   bitmap_obstack_release (&loop_renamer_obstack);
     679      1070301 :   free (use_blocks);
     680              : }
     681              : 
     682              : /* Rewrites the defs and uses into a loop closed ssa form.
     683              :    If CHANGED_BBS is not NULL, we look for uses outside loops only in the basic
     684              :    blocks in this set.  UPDATE_FLAG is used in the call to update_ssa.  See
     685              :    TODO_update_ssa* for documentation.  */
     686              : 
     687              : void
     688      4724951 : rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
     689              : {
     690      4724951 :   rewrite_into_loop_closed_ssa_1 (changed_bbs, update_flag, SSA_OP_ALL_USES);
     691      4724951 : }
     692              : 
     693              : /* Check invariants of the loop closed ssa form for the def in DEF_BB.  */
     694              : 
     695              : static void
     696    180761557 : check_loop_closed_ssa_def (basic_block def_bb, tree def)
     697              : {
     698    180761557 :   use_operand_p use_p;
     699    180761557 :   imm_use_iterator iterator;
     700    532068347 :   FOR_EACH_IMM_USE_FAST (use_p, iterator, def)
     701              :     {
     702    351306790 :       if (is_gimple_debug (USE_STMT (use_p)))
     703     46243799 :         continue;
     704              : 
     705    305062991 :       basic_block use_bb = gimple_bb (USE_STMT (use_p));
     706    305062991 :       if (is_a <gphi *> (USE_STMT (use_p)))
     707     81746300 :         use_bb = EDGE_PRED (use_bb, PHI_ARG_INDEX_FROM_USE (use_p))->src;
     708              : 
     709    305062991 :       gcc_assert (flow_bb_inside_loop_p (def_bb->loop_father, use_bb));
     710    180761557 :     }
     711    180761557 : }
     712              : 
     713              : /* Checks invariants of loop closed ssa form in BB.  */
     714              : 
     715              : static void
     716     52639795 : check_loop_closed_ssa_bb (basic_block bb)
     717              : {
     718     95839691 :   for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
     719     43199896 :        gsi_next (&bsi))
     720              :     {
     721     43199896 :       gphi *phi = bsi.phi ();
     722              : 
     723     43199896 :       check_loop_closed_ssa_def (bb, PHI_RESULT (phi));
     724              :     }
     725              : 
     726    215012058 :   for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (bb); !gsi_end_p (bsi);
     727    162372263 :        gsi_next_nondebug (&bsi))
     728              :     {
     729    162372263 :       ssa_op_iter iter;
     730    162372263 :       tree var;
     731    162372263 :       gimple *stmt = gsi_stmt (bsi);
     732              : 
     733    299933924 :       FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_DEFS)
     734    137561661 :         check_loop_closed_ssa_def (bb, var);
     735              :     }
     736     52639795 : }
     737              : 
     738              : /* Checks that invariants of the loop closed ssa form are preserved.
     739              :    Call verify_ssa when VERIFY_SSA_P is true.  Note all loops are checked
     740              :    if LOOP is NULL, otherwise, only LOOP is checked.  */
     741              : 
     742              : DEBUG_FUNCTION void
     743      4018499 : verify_loop_closed_ssa (bool verify_ssa_p, class loop *loop)
     744              : {
     745      8036998 :   if (number_of_loops (cfun) <= 1)
     746              :     return;
     747              : 
     748      4018499 :   timevar_push (TV_VERIFY_LOOP_CLOSED);
     749              : 
     750      4018499 :   if (loop == NULL)
     751              :     {
     752      4016754 :       basic_block bb;
     753              : 
     754      4016754 :       if (verify_ssa_p)
     755        35309 :         verify_ssa (false, true);
     756              : 
     757    132845697 :       FOR_EACH_BB_FN (bb, cfun)
     758    128828943 :         if (bb->loop_father && bb->loop_father->num > 0)
     759     52631476 :           check_loop_closed_ssa_bb (bb);
     760              :     }
     761              :   else
     762              :     {
     763         1745 :       basic_block *bbs = get_loop_body (loop);
     764              : 
     765              :       /* We do not have loop-local SSA verification so just
     766              :          check there's no update queued.  */
     767         1745 :       if (verify_ssa_p)
     768         1745 :         gcc_assert (!need_ssa_update_p (cfun));
     769              : 
     770        10064 :       for (unsigned i = 0; i < loop->num_nodes; ++i)
     771         8319 :         check_loop_closed_ssa_bb (bbs[i]);
     772              : 
     773         1745 :       free (bbs);
     774              :     }
     775              : 
     776      4018499 :   timevar_pop (TV_VERIFY_LOOP_CLOSED);
     777              : }
     778              : 
     779              : /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
     780              :    preserve the loop closed ssa form.  If COPY_CONSTANTS_P is true then
     781              :    forwarder PHIs are also created for constant arguments.
     782              :    The newly created block is returned.  */
     783              : 
     784              : basic_block
     785        66523 : split_loop_exit_edge (edge exit, bool copy_constants_p)
     786              : {
     787        66523 :   basic_block dest = exit->dest;
     788        66523 :   basic_block bb = split_edge (exit);
     789        66523 :   gphi *phi, *new_phi;
     790        66523 :   tree new_name, name;
     791        66523 :   use_operand_p op_p;
     792        66523 :   gphi_iterator psi;
     793        66523 :   location_t locus;
     794              : 
     795       157911 :   for (psi = gsi_start_phis (dest); !gsi_end_p (psi); gsi_next (&psi))
     796              :     {
     797        91388 :       phi = psi.phi ();
     798        91388 :       op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
     799        91388 :       locus = gimple_phi_arg_location_from_edge (phi, single_succ_edge (bb));
     800              : 
     801        91388 :       name = USE_FROM_PTR (op_p);
     802              : 
     803              :       /* If the argument of the PHI node is a constant, we do not need
     804              :          to keep it inside loop.  */
     805        91388 :       if (TREE_CODE (name) != SSA_NAME
     806         2621 :           && !copy_constants_p)
     807         2507 :         continue;
     808              : 
     809              :       /* Otherwise create an auxiliary phi node that will copy the value
     810              :          of the SSA name out of the loop.  */
     811        88881 :       new_name = duplicate_ssa_name (PHI_RESULT (phi), NULL);
     812        88881 :       new_phi = create_phi_node (new_name, bb);
     813        88881 :       add_phi_arg (new_phi, name, exit, locus);
     814        88881 :       SET_USE (op_p, new_name);
     815              :     }
     816              : 
     817        66523 :   return bb;
     818              : }
     819              : 
     820              : /* Returns the basic block in that statements should be emitted for induction
     821              :    variables incremented at the end of the LOOP.  */
     822              : 
     823              : basic_block
     824     24492720 : ip_end_pos (class loop *loop)
     825              : {
     826     24492720 :   return loop->latch;
     827              : }
     828              : 
     829              : /* Returns the basic block in that statements should be emitted for induction
     830              :    variables incremented just before exit condition of a LOOP.  */
     831              : 
     832              : basic_block
     833     50497410 : ip_normal_pos (class loop *loop)
     834              : {
     835     50497410 :   basic_block bb;
     836     50497410 :   edge exit;
     837              : 
     838     50497410 :   if (!single_pred_p (loop->latch))
     839              :     return NULL;
     840              : 
     841     50345448 :   bb = single_pred (loop->latch);
     842    100690896 :   if (!safe_is_a <gcond *> (*gsi_last_bb (bb)))
     843              :     return NULL;
     844              : 
     845     50332632 :   exit = EDGE_SUCC (bb, 0);
     846     50332632 :   if (exit->dest == loop->latch)
     847     38022451 :     exit = EDGE_SUCC (bb, 1);
     848              : 
     849     50332632 :   if (flow_bb_inside_loop_p (loop, exit->dest))
     850        58616 :     return NULL;
     851              : 
     852              :   return bb;
     853              : }
     854              : 
     855              : /* Stores the standard position for induction variable increment in LOOP
     856              :    (just before the exit condition if it is available and latch block is empty,
     857              :    end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
     858              :    the increment should be inserted after *BSI.  */
     859              : 
     860              : void
     861       222261 : standard_iv_increment_position (class loop *loop, gimple_stmt_iterator *bsi,
     862              :                                 bool *insert_after)
     863              : {
     864       222261 :   basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
     865       222261 :   gimple *last = last_nondebug_stmt (latch);
     866              : 
     867       222261 :   if (!bb
     868       222261 :       || (last && gimple_code (last) != GIMPLE_LABEL))
     869              :     {
     870          117 :       *bsi = gsi_last_bb (latch);
     871          117 :       *insert_after = true;
     872              :     }
     873              :   else
     874              :     {
     875       222144 :       *bsi = gsi_last_bb (bb);
     876       222144 :       *insert_after = false;
     877              :     }
     878       222261 : }
     879              : 
     880              : /* Copies phi node arguments for duplicated blocks.  The index of the first
     881              :    duplicated block is FIRST_NEW_BLOCK.  */
     882              : 
     883              : static void
     884       153903 : copy_phi_node_args (unsigned first_new_block)
     885              : {
     886       153903 :   unsigned i;
     887              : 
     888      1382216 :   for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
     889      1228313 :     BASIC_BLOCK_FOR_FN (cfun, i)->flags |= BB_DUPLICATED;
     890              : 
     891      1382216 :   for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
     892      1228313 :     add_phi_args_after_copy_bb (BASIC_BLOCK_FOR_FN (cfun, i));
     893              : 
     894      1382216 :   for (i = first_new_block; i < (unsigned) last_basic_block_for_fn (cfun); i++)
     895      1228313 :     BASIC_BLOCK_FOR_FN (cfun, i)->flags &= ~BB_DUPLICATED;
     896       153903 : }
     897              : 
     898              : 
     899              : /* The same as cfgloopmanip.cc:duplicate_loop_body_to_header_edge, but also
     900              :    updates the PHI nodes at start of the copied region.  In order to
     901              :    achieve this, only loops whose exits all lead to the same location
     902              :    are handled.
     903              : 
     904              :    Notice that we do not completely update the SSA web after
     905              :    duplication.  The caller is responsible for calling update_ssa
     906              :    after the loop has been duplicated.  */
     907              : 
     908              : bool
     909       153920 : gimple_duplicate_loop_body_to_header_edge (class loop *loop, edge e,
     910              :                                            unsigned int ndupl,
     911              :                                            sbitmap wont_exit, edge orig,
     912              :                                            vec<edge> *to_remove, int flags)
     913              : {
     914       153920 :   unsigned first_new_block;
     915              : 
     916       153920 :   if (!loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
     917              :     return false;
     918       153920 :   if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
     919              :     return false;
     920              : 
     921       153920 :   first_new_block = last_basic_block_for_fn (cfun);
     922       153920 :   if (!duplicate_loop_body_to_header_edge (loop, e, ndupl, wont_exit, orig,
     923              :                                            to_remove, flags))
     924              :     return false;
     925              : 
     926              :   /* Readd the removed phi args for e.  */
     927       153903 :   flush_pending_stmts (e);
     928              : 
     929              :   /* Copy the phi node arguments.  */
     930       153903 :   copy_phi_node_args (first_new_block);
     931              : 
     932       153903 :   scev_reset ();
     933              : 
     934       153903 :   return true;
     935              : }
     936              : 
     937              : /* Returns true if we can unroll LOOP FACTOR times.  Number
     938              :    of iterations of the loop is returned in NITER.  */
     939              : 
     940              : bool
     941          930 : can_unroll_loop_p (class loop *loop, unsigned factor,
     942              :                    class tree_niter_desc *niter)
     943              : {
     944          930 :   edge exit;
     945              : 
     946              :   /* Check whether unrolling is possible.  We only want to unroll loops
     947              :      for that we are able to determine number of iterations.  We also
     948              :      want to split the extra iterations of the loop from its end,
     949              :      therefore we require that the loop has precisely one
     950              :      exit.  */
     951              : 
     952          930 :   exit = single_dom_exit (loop);
     953          930 :   if (!exit)
     954              :     return false;
     955              : 
     956          909 :   if (!number_of_iterations_exit (loop, exit, niter, false)
     957          908 :       || niter->cmp == ERROR_MARK
     958              :       /* Scalar evolutions analysis might have copy propagated
     959              :          the abnormal ssa names into these expressions, hence
     960              :          emitting the computations based on them during loop
     961              :          unrolling might create overlapping life ranges for
     962              :          them, and failures in out-of-ssa.  */
     963          906 :       || contains_abnormal_ssa_name_p (niter->may_be_zero)
     964          906 :       || contains_abnormal_ssa_name_p (niter->control.base)
     965          906 :       || contains_abnormal_ssa_name_p (niter->control.step)
     966         1815 :       || contains_abnormal_ssa_name_p (niter->bound))
     967              :     return false;
     968              : 
     969              :   /* And of course, we must be able to duplicate the loop.  */
     970          906 :   if (!can_duplicate_loop_p (loop))
     971              :     return false;
     972              : 
     973              :   /* The final loop should be small enough.  */
     974          906 :   if (tree_num_loop_insns (loop, &eni_size_weights) * factor
     975          906 :       > (unsigned) param_max_unrolled_insns)
     976            6 :     return false;
     977              : 
     978              :   return true;
     979              : }
     980              : 
     981              : /* Determines the conditions that control execution of LOOP unrolled FACTOR
     982              :    times.  DESC is number of iterations of LOOP.  ENTER_COND is set to
     983              :    condition that must be true if the main loop can be entered.
     984              :    If the loop does not always iterate an exact multiple of FACTOR times,
     985              :    EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
     986              :    how the exit from the unrolled loop should be controlled.  Otherwise,
     987              :    the trees are set to null and EXIT_CMP is set to ERROR_MARK.  */
     988              : 
     989              : static void
     990          889 : determine_exit_conditions (class loop *loop, class tree_niter_desc *desc,
     991              :                            unsigned factor, tree *enter_cond,
     992              :                            tree *exit_base, tree *exit_step,
     993              :                            enum tree_code *exit_cmp, tree *exit_bound)
     994              : {
     995          889 :   gimple_seq stmts;
     996          889 :   tree base = desc->control.base;
     997          889 :   tree step = desc->control.step;
     998          889 :   tree bound = desc->bound;
     999          889 :   tree type = TREE_TYPE (step);
    1000          889 :   tree bigstep, delta;
    1001          889 :   tree min = lower_bound_in_type (type, type);
    1002          889 :   tree max = upper_bound_in_type (type, type);
    1003          889 :   enum tree_code cmp = desc->cmp;
    1004          889 :   tree cond = boolean_true_node, assum;
    1005              : 
    1006              :   /* For pointers, do the arithmetics in the type of step.  */
    1007          889 :   base = fold_convert (type, base);
    1008          889 :   bound = fold_convert (type, bound);
    1009              : 
    1010          889 :   *enter_cond = boolean_false_node;
    1011          889 :   *exit_base = NULL_TREE;
    1012          889 :   *exit_step = NULL_TREE;
    1013          889 :   *exit_cmp = ERROR_MARK;
    1014          889 :   *exit_bound = NULL_TREE;
    1015          889 :   gcc_assert (cmp != ERROR_MARK);
    1016              : 
    1017              :   /* We only need to be correct when we answer question
    1018              :      "Do at least FACTOR more iterations remain?" in the unrolled loop.
    1019              :      Thus, transforming BASE + STEP * i <> BOUND to
    1020              :      BASE + STEP * i < BOUND is ok.  */
    1021          889 :   if (cmp == NE_EXPR)
    1022              :     {
    1023           89 :       if (tree_int_cst_sign_bit (step))
    1024              :         cmp = GT_EXPR;
    1025              :       else
    1026          889 :         cmp = LT_EXPR;
    1027              :     }
    1028          800 :   else if (cmp == LT_EXPR)
    1029              :     {
    1030          798 :       gcc_assert (!tree_int_cst_sign_bit (step));
    1031              :     }
    1032            2 :   else if (cmp == GT_EXPR)
    1033              :     {
    1034            2 :       gcc_assert (tree_int_cst_sign_bit (step));
    1035              :     }
    1036              :   else
    1037            0 :     gcc_unreachable ();
    1038              : 
    1039              :   /* The main body of the loop may be entered iff:
    1040              : 
    1041              :      1) desc->may_be_zero is false.
    1042              :      2) it is possible to check that there are at least FACTOR iterations
    1043              :         of the loop, i.e., BOUND - step * FACTOR does not overflow.
    1044              :      3) # of iterations is at least FACTOR  */
    1045              : 
    1046          889 :   if (!integer_zerop (desc->may_be_zero))
    1047            5 :     cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
    1048              :                         invert_truthvalue (desc->may_be_zero),
    1049              :                         cond);
    1050              : 
    1051          889 :   bigstep = fold_build2 (MULT_EXPR, type, step,
    1052              :                          build_int_cst_type (type, factor));
    1053          889 :   delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
    1054          889 :   if (cmp == LT_EXPR)
    1055          835 :     assum = fold_build2 (GE_EXPR, boolean_type_node,
    1056              :                          bound,
    1057              :                          fold_build2 (PLUS_EXPR, type, min, delta));
    1058              :   else
    1059           54 :     assum = fold_build2 (LE_EXPR, boolean_type_node,
    1060              :                          bound,
    1061              :                          fold_build2 (PLUS_EXPR, type, max, delta));
    1062          889 :   cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
    1063              : 
    1064          889 :   bound = fold_build2 (MINUS_EXPR, type, bound, delta);
    1065          889 :   assum = fold_build2 (cmp, boolean_type_node, base, bound);
    1066          889 :   cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
    1067              : 
    1068          889 :   if (integer_nonzerop (cond)
    1069          889 :       && integer_zerop (desc->may_be_zero))
    1070              :     {
    1071              :       /* When the iteration count is an exact multiple of factor we're done.  */
    1072          164 :       if (TREE_CODE (desc->niter) == INTEGER_CST
    1073          164 :           && wi::multiple_of_p (wi::to_widest (desc->niter) + 1,
    1074              :                                 factor, UNSIGNED))
    1075           33 :         return;
    1076              :     }
    1077              : 
    1078          856 :   cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
    1079          856 :   if (stmts)
    1080           19 :     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
    1081              :   /* cond now may be a gimple comparison, which would be OK, but also any
    1082              :      other gimple rhs (say a && b).  In this case we need to force it to
    1083              :      operand.  */
    1084          856 :   if (!is_gimple_condexpr_for_cond (cond))
    1085              :     {
    1086           14 :       cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
    1087           14 :       if (stmts)
    1088           14 :         gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
    1089              :     }
    1090          856 :   *enter_cond = cond;
    1091              : 
    1092          856 :   base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
    1093          856 :   if (stmts)
    1094           30 :     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
    1095          856 :   bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
    1096          856 :   if (stmts)
    1097          774 :     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
    1098              : 
    1099          856 :   *exit_base = base;
    1100          856 :   *exit_step = bigstep;
    1101          856 :   *exit_cmp = cmp;
    1102          856 :   *exit_bound = bound;
    1103              : }
    1104              : 
    1105              : /* Unroll LOOP FACTOR times.  LOOP is known to have a single exit edge
    1106              :    whose source block dominates the latch.  DESC describes the number of
    1107              :    iterations of LOOP.
    1108              : 
    1109              :    If N is number of iterations of the loop and MAY_BE_ZERO is the condition
    1110              :    under that loop exits in the first iteration even if N != 0,
    1111              : 
    1112              :    while (1)
    1113              :      {
    1114              :        x = phi (init, next);
    1115              : 
    1116              :        pre;
    1117              :        if (st)
    1118              :          break;
    1119              :        post;
    1120              :      }
    1121              : 
    1122              :    becomes (with possibly the exit conditions formulated a bit differently,
    1123              :    avoiding the need to create a new iv):
    1124              : 
    1125              :    if (MAY_BE_ZERO || N < FACTOR)
    1126              :      goto rest;
    1127              : 
    1128              :    do
    1129              :      {
    1130              :        x = phi (init, next);
    1131              : 
    1132              :        pre;
    1133              :        post;
    1134              :        pre;
    1135              :        post;
    1136              :        ...
    1137              :        pre;
    1138              :        post;
    1139              :        N -= FACTOR;
    1140              : 
    1141              :      } while (N >= FACTOR);
    1142              : 
    1143              :    rest:
    1144              :      init' = phi (init, x);
    1145              : 
    1146              :    while (1)
    1147              :      {
    1148              :        x = phi (init', next);
    1149              : 
    1150              :        pre;
    1151              :        if (st)
    1152              :          break;
    1153              :        post;
    1154              :      }
    1155              : 
    1156              :    Before the loop is unrolled, TRANSFORM is called for it (only for the
    1157              :    unrolled loop, but not for its versioned copy).  DATA is passed to
    1158              :    TRANSFORM.  */
    1159              : 
    1160              : /* Probability in % that the unrolled loop is entered.  Just a guess.  */
    1161              : #define PROB_UNROLLED_LOOP_ENTERED 90
    1162              : 
    1163              : void
    1164          889 : tree_transform_and_unroll_loop (class loop *loop, unsigned factor,
    1165              :                                 class tree_niter_desc *desc,
    1166              :                                 transform_callback transform,
    1167              :                                 void *data)
    1168              : {
    1169          889 :   unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
    1170              : 
    1171          889 :   enum tree_code exit_cmp;
    1172          889 :   tree enter_main_cond, exit_base, exit_step, exit_bound;
    1173          889 :   bool flat = maybe_flat_loop_profile (loop);
    1174          889 :   determine_exit_conditions (loop, desc, factor,
    1175              :                              &enter_main_cond, &exit_base, &exit_step,
    1176              :                              &exit_cmp, &exit_bound);
    1177          889 :   bool single_loop_p = !exit_base;
    1178              : 
    1179          889 :   gcond *exit_if = nullptr;
    1180          889 :   class loop *new_loop = nullptr;
    1181          889 :   edge new_exit;
    1182          889 :   if (!single_loop_p)
    1183              :     {
    1184          856 :       profile_count entry_count = loop_preheader_edge (loop)->src->count;
    1185              :       /* Let us assume that the unrolled loop is quite likely to be entered.  */
    1186          856 :       profile_probability prob_entry;
    1187          856 :       if (integer_nonzerop (enter_main_cond))
    1188           49 :         prob_entry = profile_probability::always ();
    1189              :       else
    1190          807 :         prob_entry = profile_probability::guessed_always ()
    1191          807 :                             .apply_scale (PROB_UNROLLED_LOOP_ENTERED, 100);
    1192              : 
    1193              : 
    1194              :       /* The values for scales should keep profile consistent, and somewhat
    1195              :          close to correct.  */
    1196          856 :       new_loop = loop_version (loop, enter_main_cond, NULL, prob_entry,
    1197              :                                prob_entry.invert (),
    1198              :                                prob_entry,
    1199              :                                /* We will later redirect exit from vectorized
    1200              :                                   loop to new_loop.  */
    1201              :                                profile_probability::always (),
    1202              :                                true);
    1203          856 :       gcc_assert (new_loop != NULL);
    1204          856 :       update_ssa (TODO_update_ssa_no_phi);
    1205              : 
    1206              :       /* Prepare the cfg and update the phi nodes.  Move the loop exit to the
    1207              :          loop latch (and make its condition dummy, for the moment).  */
    1208          856 :       basic_block rest = loop_preheader_edge (new_loop)->src;
    1209          856 :       edge precond_edge = single_pred_edge (rest);
    1210          856 :       split_edge (loop_latch_edge (loop));
    1211          856 :       basic_block exit_bb = single_pred (loop->latch);
    1212          856 :       edge exit = single_dom_exit (loop);
    1213              : 
    1214              :       /* Since the exit edge will be removed, the frequency of all the blocks
    1215              :          in the loop that are dominated by it must be scaled.  */
    1216          856 :       if (exit->probability.initialized_p ())
    1217          856 :         scale_dominated_blocks_in_loop (loop, exit->src,
    1218              :                                         /* We are scaling up here so
    1219              :                                            probability does not fit.  */
    1220          856 :                                         exit->src->count,
    1221         1712 :                                         exit->src->count - exit->count ());
    1222              : 
    1223          856 :       gimple_stmt_iterator bsi = gsi_last_bb (exit_bb);
    1224          856 :       exit_if = gimple_build_cond (EQ_EXPR, integer_zero_node,
    1225              :                                    integer_zero_node,
    1226              :                                    NULL_TREE, NULL_TREE);
    1227              : 
    1228          856 :       gsi_insert_after (&bsi, exit_if, GSI_NEW_STMT);
    1229          856 :       new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
    1230          856 :       rescan_loop_exit (new_exit, true, false);
    1231              : 
    1232              :       /* Set the probability of new exit to the same of the old one.  Fix
    1233              :          the count of the latch block.  */
    1234          856 :       new_exit->probability = exit->probability;
    1235          856 :       edge new_nonexit = single_pred_edge (loop->latch);
    1236          856 :       new_nonexit->probability = exit->probability.invert ();
    1237          856 :       new_nonexit->flags = EDGE_TRUE_VALUE;
    1238          856 :       set_edge_probability_and_rescale_others
    1239          856 :               (exit, profile_probability::never ());
    1240          856 :       loop->latch->count = new_nonexit->count ();
    1241              : 
    1242          856 :       edge old_entry = loop_preheader_edge (loop);
    1243          856 :       edge new_entry = loop_preheader_edge (new_loop);
    1244          856 :       edge old_latch = loop_latch_edge (loop);
    1245          856 :       for (gphi_iterator psi_old_loop = gsi_start_phis (loop->header),
    1246          856 :              psi_new_loop = gsi_start_phis (new_loop->header);
    1247         2677 :            !gsi_end_p (psi_old_loop);
    1248         1821 :            gsi_next (&psi_old_loop), gsi_next (&psi_new_loop))
    1249              :         {
    1250         1821 :           gphi *phi_old_loop = psi_old_loop.phi ();
    1251         1821 :           gphi *phi_new_loop = psi_new_loop.phi ();
    1252              : 
    1253         1821 :           tree init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
    1254         1821 :           use_operand_p op
    1255         1821 :             = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
    1256         1821 :           gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
    1257         1821 :           tree next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
    1258              : 
    1259              :           /* Prefer using original variable as a base for the new ssa name.
    1260              :              This is necessary for virtual ops, and useful in order to avoid
    1261              :              losing debug info for real ops.  */
    1262         1821 :           tree new_init;
    1263         1821 :           if (TREE_CODE (next) == SSA_NAME
    1264         3642 :               && useless_type_conversion_p (TREE_TYPE (next),
    1265         1821 :                                             TREE_TYPE (init)))
    1266         1821 :             new_init = copy_ssa_name (next);
    1267            0 :           else if (TREE_CODE (init) == SSA_NAME
    1268            0 :                    && useless_type_conversion_p (TREE_TYPE (init),
    1269            0 :                                                  TREE_TYPE (next)))
    1270            0 :             new_init = copy_ssa_name (init);
    1271            0 :           else if (useless_type_conversion_p (TREE_TYPE (next),
    1272            0 :                                               TREE_TYPE (init)))
    1273            0 :             new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
    1274              :                                            "unrinittmp");
    1275              :           else
    1276            0 :             new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
    1277              :                                            "unrinittmp");
    1278              : 
    1279         1821 :           gphi *phi_rest = create_phi_node (new_init, rest);
    1280         1821 :           add_phi_arg (phi_rest, init, precond_edge, UNKNOWN_LOCATION);
    1281         1821 :           add_phi_arg (phi_rest, next, new_exit, UNKNOWN_LOCATION);
    1282         1821 :           SET_USE (op, new_init);
    1283              :         }
    1284              : 
    1285          856 :       remove_path (exit);
    1286              :       /* We will later redirect exit from vectorized loop to new_loop.  */
    1287          856 :       loop_preheader_edge (new_loop)->src->count = entry_count;
    1288              : 
    1289              :       /* The epilog loop latch executes at most factor - 1 times.
    1290              :          Since the epilog is entered unconditionally it will need to handle
    1291              :          up to factor executions of its body.
    1292              : 
    1293              :          That however relies on ENTER_MAIN_COND being false implying that
    1294              :          less than factor iterations are left.  determine_exit_conditions
    1295              :          derives ENTER_MAIN_COND from a LT_EXPR/GT_EXPR comparison of the
    1296              :          control IV, which for a NE_EXPR exit test is only valid if that IV
    1297              :          does not wrap.  When it may wrap the main loop can be skipped (the
    1298              :          condition may even be constant false) while the epilog still runs
    1299              :          all iterations of the original loop, so keep the bound we inherited
    1300              :          from it.  */
    1301          856 :       if (desc->cmp != NE_EXPR || desc->control.no_overflow)
    1302              :         {
    1303          854 :           new_loop->any_upper_bound = true;
    1304          854 :           new_loop->nb_iterations_upper_bound = factor - 1;
    1305              :           /* We do not really know estimate on number of iterations, since we
    1306              :              do not track any estimates modulo unroll factor.
    1307              :              Scale loop profile.  It may be more realistic to scale loop
    1308              :              profile to factor / 2 - 1, but vectorizer also uses factor - 1.  */
    1309          854 :           scale_loop_profile (new_loop, profile_probability::always (),
    1310              :                               factor - 1);
    1311              :         }
    1312              :       /* Drop estimate from loop_info, see above.  */
    1313          856 :       new_loop->any_estimate = false;
    1314              :     }
    1315              :   else
    1316           33 :     new_exit = single_dom_exit (loop);
    1317              : 
    1318              :   /* Transform the loop.  */
    1319          889 :   if (transform)
    1320          795 :     (*transform) (loop, data);
    1321              : 
    1322              :   /* Unroll the loop and remove the exits in all iterations except for the
    1323              :      last one.  */
    1324          889 :   auto_sbitmap wont_exit (factor);
    1325          889 :   bitmap_ones (wont_exit);
    1326          889 :   bitmap_clear_bit (wont_exit, factor - 1);
    1327              : 
    1328          889 :   auto_vec<edge> to_remove;
    1329          889 :   bool ok
    1330              :     = gimple_duplicate_loop_body_to_header_edge
    1331          963 :             (loop, loop_latch_edge (loop), factor - 1, wont_exit,
    1332              :              new_exit, &to_remove,
    1333              :              DLTHE_FLAG_UPDATE_FREQ | (flat ? DLTHE_FLAG_FLAT_PROFILE : 0));
    1334          889 :   gcc_assert (ok);
    1335              : 
    1336         3828 :   for (edge e : to_remove)
    1337              :     {
    1338         1161 :       ok = remove_path (e);
    1339         1161 :       gcc_assert (ok);
    1340              :     }
    1341          889 :   update_ssa (TODO_update_ssa);
    1342              : 
    1343          889 :   new_exit = single_dom_exit (loop);
    1344              :   /* gimple_duplicate_loop_body_to_header_edge depending on
    1345              :      DLTHE_FLAG_UPDATE_FREQ either keeps original frequency of the loop header
    1346              :      or scales it down accordingly.
    1347              :      However exit edge probability is kept as original.  Fix it if needed
    1348              :      and compensate.  */
    1349          889 :   update_loop_exit_probability_scale_dom_bbs (loop, new_exit);
    1350          889 :   if (!single_loop_p)
    1351              :     {
    1352              :       /* Finally create the new counter for number of iterations and add
    1353              :          the new exit instruction.  */
    1354          856 :       tree ctr_before, ctr_after;
    1355          856 :       gimple_stmt_iterator bsi = gsi_last_nondebug_bb (new_exit->src);
    1356          856 :       exit_if = as_a <gcond *> (gsi_stmt (bsi));
    1357          856 :       create_iv (exit_base, PLUS_EXPR, exit_step, NULL_TREE, loop,
    1358              :                  &bsi, false, &ctr_before, &ctr_after);
    1359          856 :       gimple_cond_set_code (exit_if, exit_cmp);
    1360          856 :       gimple_cond_set_lhs (exit_if, ctr_after);
    1361          856 :       gimple_cond_set_rhs (exit_if, exit_bound);
    1362          856 :       update_stmt (exit_if);
    1363              :     }
    1364          889 :   if (loop->any_upper_bound)
    1365         1756 :     loop->nb_iterations_upper_bound = wi::udiv_floor
    1366          878 :                 (loop->nb_iterations_upper_bound + 1, factor) - 1;
    1367          889 :   if (loop->any_likely_upper_bound)
    1368         1756 :     loop->nb_iterations_likely_upper_bound = wi::udiv_floor
    1369          878 :                 (loop->nb_iterations_likely_upper_bound + 1, factor) - 1;
    1370          889 :   if (loop->any_estimate)
    1371          182 :     loop->nb_iterations_estimate = wi::udiv_floor
    1372           91 :                 (loop->nb_iterations_estimate + 1, factor) - 1;
    1373              : 
    1374          889 :   checking_verify_flow_info ();
    1375          889 :   checking_verify_loop_structure ();
    1376          889 :   checking_verify_loop_closed_ssa (true, loop);
    1377          889 :   if (new_loop)
    1378         1745 :     checking_verify_loop_closed_ssa (true, new_loop);
    1379          889 : }
    1380              : 
    1381              : /* Wrapper over tree_transform_and_unroll_loop for case we do not
    1382              :    want to transform the loop before unrolling.  The meaning
    1383              :    of the arguments is the same as for tree_transform_and_unroll_loop.  */
    1384              : 
    1385              : void
    1386           94 : tree_unroll_loop (class loop *loop, unsigned factor,
    1387              :                   class tree_niter_desc *desc)
    1388              : {
    1389           94 :   tree_transform_and_unroll_loop (loop, factor, desc, NULL, NULL);
    1390           94 : }
    1391              : 
    1392              : /* Rewrite the phi node at position PSI in function of the main
    1393              :    induction variable MAIN_IV and insert the generated code at GSI.  */
    1394              : 
    1395              : static void
    1396         2025 : rewrite_phi_with_iv (loop_p loop,
    1397              :                      gphi_iterator *psi,
    1398              :                      gimple_stmt_iterator *gsi,
    1399              :                      tree main_iv)
    1400              : {
    1401         2025 :   affine_iv iv;
    1402         2025 :   gassign *stmt;
    1403         2025 :   gphi *phi = psi->phi ();
    1404         2025 :   tree atype, mtype, val, res = PHI_RESULT (phi);
    1405              : 
    1406         4050 :   if (virtual_operand_p (res) || res == main_iv)
    1407              :     {
    1408         1155 :       gsi_next (psi);
    1409         1237 :       return;
    1410              :     }
    1411              : 
    1412          870 :   if (!simple_iv (loop, loop, res, &iv, true))
    1413              :     {
    1414           82 :       gsi_next (psi);
    1415           82 :       return;
    1416              :     }
    1417              : 
    1418          788 :   remove_phi_node (psi, false);
    1419              : 
    1420          788 :   atype = TREE_TYPE (res);
    1421          788 :   mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
    1422          788 :   val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
    1423              :                      fold_convert (mtype, main_iv));
    1424         1574 :   val = fold_build2 (POINTER_TYPE_P (atype)
    1425              :                      ? POINTER_PLUS_EXPR : PLUS_EXPR,
    1426              :                      atype, unshare_expr (iv.base), val);
    1427          788 :   val = force_gimple_operand_gsi (gsi, val, false, NULL_TREE, true,
    1428              :                                   GSI_SAME_STMT);
    1429          788 :   stmt = gimple_build_assign (res, val);
    1430          788 :   gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
    1431              : }
    1432              : 
    1433              : /* Rewrite all the phi nodes of LOOP in function of the main induction
    1434              :    variable MAIN_IV.  */
    1435              : 
    1436              : static void
    1437          580 : rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv)
    1438              : {
    1439          580 :   unsigned i;
    1440          580 :   basic_block *bbs = get_loop_body_in_dom_order (loop);
    1441          580 :   gphi_iterator psi;
    1442              : 
    1443         2634 :   for (i = 0; i < loop->num_nodes; i++)
    1444              :     {
    1445         1474 :       basic_block bb = bbs[i];
    1446         1474 :       gimple_stmt_iterator gsi = gsi_after_labels (bb);
    1447              : 
    1448         1474 :       if (bb->loop_father != loop)
    1449           97 :         continue;
    1450              : 
    1451         3402 :       for (psi = gsi_start_phis (bb); !gsi_end_p (psi); )
    1452         2025 :         rewrite_phi_with_iv (loop, &psi, &gsi, main_iv);
    1453              :     }
    1454              : 
    1455          580 :   free (bbs);
    1456          580 : }
    1457              : 
    1458              : /* Bases all the induction variables in LOOP on a single induction variable
    1459              :    (with base 0 and step 1), whose final value is compared with *NIT.  When the
    1460              :    IV type precision has to be larger than *NIT type precision, *NIT is
    1461              :    converted to the larger type, the conversion code is inserted before the
    1462              :    loop, and *NIT is updated to the new definition.  When BUMP_IN_LATCH is true,
    1463              :    the induction variable is incremented in the loop latch, otherwise it is
    1464              :    incremented in the loop header.  Return the induction variable that was
    1465              :    created.  */
    1466              : 
    1467              : tree
    1468          580 : canonicalize_loop_ivs (class loop *loop, tree *nit, bool bump_in_latch)
    1469              : {
    1470          580 :   unsigned precision = TYPE_PRECISION (TREE_TYPE (*nit));
    1471          580 :   unsigned original_precision = precision;
    1472          580 :   tree type, var_before;
    1473          580 :   gimple_stmt_iterator gsi;
    1474          580 :   gphi_iterator psi;
    1475          580 :   gcond *stmt;
    1476          580 :   edge exit = single_dom_exit (loop);
    1477          580 :   gimple_seq stmts;
    1478          580 :   bool unsigned_p = false;
    1479              : 
    1480          580 :   for (psi = gsi_start_phis (loop->header);
    1481         1925 :        !gsi_end_p (psi); gsi_next (&psi))
    1482              :     {
    1483         1345 :       gphi *phi = psi.phi ();
    1484         1345 :       tree res = PHI_RESULT (phi);
    1485         1345 :       bool uns;
    1486              : 
    1487         1345 :       type = TREE_TYPE (res);
    1488         1345 :       if (virtual_operand_p (res)
    1489          853 :           || (!INTEGRAL_TYPE_P (type)
    1490           21 :               && !POINTER_TYPE_P (type))
    1491         2183 :           || TYPE_PRECISION (type) < precision)
    1492          529 :         continue;
    1493              : 
    1494          816 :       uns = POINTER_TYPE_P (type) | TYPE_UNSIGNED (type);
    1495              : 
    1496          816 :       if (TYPE_PRECISION (type) > precision)
    1497              :         unsigned_p = uns;
    1498              :       else
    1499          812 :         unsigned_p |= uns;
    1500              : 
    1501          816 :       precision = TYPE_PRECISION (type);
    1502              :     }
    1503              : 
    1504          580 :   scalar_int_mode mode = smallest_int_mode_for_size (precision).require ();
    1505          580 :   precision = GET_MODE_PRECISION (mode);
    1506          580 :   type = build_nonstandard_integer_type (precision, unsigned_p);
    1507              : 
    1508          580 :   if (original_precision != precision
    1509          580 :       || TYPE_UNSIGNED (TREE_TYPE (*nit)) != unsigned_p)
    1510              :     {
    1511          298 :       *nit = fold_convert (type, *nit);
    1512          298 :       *nit = force_gimple_operand (*nit, &stmts, true, NULL_TREE);
    1513          298 :       if (stmts)
    1514          112 :         gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
    1515              :     }
    1516              : 
    1517          580 :   if (bump_in_latch)
    1518         1160 :     gsi = gsi_last_bb (loop->latch);
    1519              :   else
    1520            0 :     gsi = gsi_last_nondebug_bb (loop->header);
    1521          580 :   create_iv (build_int_cst_type (type, 0), PLUS_EXPR, build_int_cst (type, 1),
    1522              :              NULL_TREE, loop, &gsi, bump_in_latch, &var_before, NULL);
    1523              : 
    1524          580 :   rewrite_all_phi_nodes_with_iv (loop, var_before);
    1525              : 
    1526         1160 :   stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
    1527              :   /* Make the loop exit if the control condition is not satisfied.  */
    1528          580 :   if (exit->flags & EDGE_TRUE_VALUE)
    1529              :     {
    1530          100 :       edge te, fe;
    1531              : 
    1532          100 :       extract_true_false_edges_from_block (exit->src, &te, &fe);
    1533          100 :       te->flags = EDGE_FALSE_VALUE;
    1534          100 :       fe->flags = EDGE_TRUE_VALUE;
    1535              :     }
    1536          580 :   gimple_cond_set_code (stmt, LT_EXPR);
    1537          580 :   gimple_cond_set_lhs (stmt, var_before);
    1538          580 :   gimple_cond_set_rhs (stmt, *nit);
    1539          580 :   update_stmt (stmt);
    1540              : 
    1541          580 :   return var_before;
    1542              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.