gcc-pr26435-pr20256.patch

   1 Index: tree-loop-linear.c
   2 ===================================================================
   3 *** tree-loop-linear.c  (revision 113884)
   4 --- tree-loop-linear.c  (working copy)
   5 ***************
   6 *** 1,5 ****
   7   /* Linear Loop transforms
   8 !    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
   9      Contributed by Daniel Berlin <dberlin@dberlin.org>.
  10
  11   This file is part of GCC.
  12 --- 1,5 ----
  13   /* Linear Loop transforms
  14 !    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
  15      Contributed by Daniel Berlin <dberlin@dberlin.org>.
  16
  17   This file is part of GCC.
  18 *************** try_interchange_loops (lambda_trans_matr
  19 *** 243,248 ****
  20 --- 243,249 ----
  21   void
  22   linear_transform_loops (struct loops *loops)
  23   {
  24 +   bool modified = false;
  25     unsigned int i;
  26     VEC(tree,heap) *oldivs = NULL;
  27     VEC(tree,heap) *invariants = NULL;
  28 *************** linear_transform_loops (struct loops *lo
  29 *** 257,263 ****
  30         lambda_loopnest before, after;
  31         lambda_trans_matrix trans;
  32         bool problem = false;
  33 -       bool need_perfect_nest = false;
  34         /* If it's not a loop nest, we don't want it.
  35            We also don't handle sibling loops properly,
  36            which are loops of the following form:
  37 --- 258,263 ----
  38 *************** linear_transform_loops (struct loops *lo
  39 *** 334,345 ****
  40             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
  41           continue;
  42         }
  43 !       if (!perfect_nest_p (loop_nest))
  44 !       need_perfect_nest = true;
  45 !       before = gcc_loopnest_to_lambda_loopnest (loops,
  46 !                                               loop_nest, &oldivs,
  47 !                                               &invariants,
  48 !                                               need_perfect_nest);
  49         if (!before)
  50         continue;
  51
  52 --- 334,342 ----
  53             fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
  54           continue;
  55         }
  56 !
  57 !       before = gcc_loopnest_to_lambda_loopnest (loops, loop_nest, &oldivs,
  58 !                                               &invariants);
  59         if (!before)
  60         continue;
  61
  62 *************** linear_transform_loops (struct loops *lo
  63 *** 357,362 ****
  64 --- 354,361 ----
  65         }
  66         lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
  67                                        after, trans);
  68 +       modified = true;
  69 +
  70         if (dump_file)
  71         fprintf (dump_file, "Successfully transformed loop.\n");
  72         free_dependence_relations (dependence_relations);
  73 *************** linear_transform_loops (struct loops *lo
  74 *** 365,369 ****
  75     VEC_free (tree, heap, oldivs);
  76     VEC_free (tree, heap, invariants);
  77     scev_reset ();
  78 !   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
  79   }
  80 --- 364,370 ----
  81     VEC_free (tree, heap, oldivs);
  82     VEC_free (tree, heap, invariants);
  83     scev_reset ();
  84 !
  85 !   if (modified)
  86 !     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi);
  87   }
  88 Index: lambda.h
  89 ===================================================================
  90 *** lambda.h    (revision 113884)
  91 --- lambda.h    (working copy)
  92 ***************
  93 *** 1,5 ****
  94   /* Lambda matrix and vector interface.
  95 !    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
  96      Contributed by Daniel Berlin <dberlin@dberlin.org>
  97
  98   This file is part of GCC.
  99 --- 1,5 ----
 100   /* Lambda matrix and vector interface.
 101 !    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
 102      Contributed by Daniel Berlin <dberlin@dberlin.org>
 103
 104   This file is part of GCC.
 105 *************** void print_lambda_body_vector (FILE *, l
 106 *** 200,207 ****
 107   lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *,
 108                                                  struct loop *,
 109                                                  VEC(tree,heap) **,
 110 !                                                VEC(tree,heap) **,
 111 !                                                bool);
 112   void lambda_loopnest_to_gcc_loopnest (struct loop *,
 113                                       VEC(tree,heap) *, VEC(tree,heap) *,
 114                                       lambda_loopnest, lambda_trans_matrix);
 115 --- 200,206 ----
 116   lambda_loopnest gcc_loopnest_to_lambda_loopnest (struct loops *,
 117                                                  struct loop *,
 118                                                  VEC(tree,heap) **,
 119 !                                                VEC(tree,heap) **);
 120   void lambda_loopnest_to_gcc_loopnest (struct loop *,
 121                                       VEC(tree,heap) *, VEC(tree,heap) *,
 122                                       lambda_loopnest, lambda_trans_matrix);
 123 Index: lambda-code.c
 124 ===================================================================
 125 *** lambda-code.c       (revision 113884)
 126 --- lambda-code.c       (working copy)
 127 ***************
 128 *** 1,5 ****
 129   /*  Loop transformation code generation
 130 !     Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
 131       Contributed by Daniel Berlin <dberlin@dberlin.org>
 132
 133       This file is part of GCC.
 134 --- 1,5 ----
 135   /*  Loop transformation code generation
 136 !     Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
 137       Contributed by Daniel Berlin <dberlin@dberlin.org>
 138
 139       This file is part of GCC.
 140 *************** static lambda_lattice lambda_lattice_new
 141 *** 149,154 ****
 142 --- 149,155 ----
 143   static lambda_lattice lambda_lattice_compute_base (lambda_loopnest);
 144
 145   static tree find_induction_var_from_exit_cond (struct loop *);
 146 + static bool can_convert_to_perfect_nest (struct loop *);
 147
 148   /* Create a new lambda body vector.  */
 149
 150 *************** DEF_VEC_ALLOC_P(lambda_loop,heap);
 151 *** 1498,1511 ****
 152
 153   lambda_loopnest
 154   gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
 155 !                                struct loop * loop_nest,
 156                                  VEC(tree,heap) **inductionvars,
 157 !                                VEC(tree,heap) **invariants,
 158 !                                bool need_perfect_nest)
 159   {
 160     lambda_loopnest ret = NULL;
 161 !   struct loop *temp;
 162 !   int depth = 0;
 163     size_t i;
 164     VEC(lambda_loop,heap) *loops = NULL;
 165     VEC(tree,heap) *uboundvars = NULL;
 166 --- 1499,1511 ----
 167
 168   lambda_loopnest
 169   gcc_loopnest_to_lambda_loopnest (struct loops *currloops,
 170 !                                struct loop *loop_nest,
 171                                  VEC(tree,heap) **inductionvars,
 172 !                                VEC(tree,heap) **invariants)
 173   {
 174     lambda_loopnest ret = NULL;
 175 !   struct loop *temp = loop_nest;
 176 !   int depth = depth_of_nest (loop_nest);
 177     size_t i;
 178     VEC(lambda_loop,heap) *loops = NULL;
 179     VEC(tree,heap) *uboundvars = NULL;
 180 *************** gcc_loopnest_to_lambda_loopnest (struct
 181 *** 1513,1521 ****
 182     VEC(int,heap) *steps = NULL;
 183     lambda_loop newloop;
 184     tree inductionvar = NULL;
 185 !
 186 !   depth = depth_of_nest (loop_nest);
 187 !   temp = loop_nest;
 188     while (temp)
 189       {
 190         newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
 191 --- 1513,1523 ----
 192     VEC(int,heap) *steps = NULL;
 193     lambda_loop newloop;
 194     tree inductionvar = NULL;
 195 !   bool perfect_nest = perfect_nest_p (loop_nest);
 196 !
 197 !   if (!perfect_nest && !can_convert_to_perfect_nest (loop_nest))
 198 !     goto fail;
 199 !
 200     while (temp)
 201       {
 202         newloop = gcc_loop_to_lambda_loop (temp, depth, invariants,
 203 *************** gcc_loopnest_to_lambda_loopnest (struct
 204 *** 1523,1534 ****
 205                                          &lboundvars, &uboundvars,
 206                                          &steps);
 207         if (!newloop)
 208 !       return NULL;
 209         VEC_safe_push (tree, heap, *inductionvars, inductionvar);
 210         VEC_safe_push (lambda_loop, heap, loops, newloop);
 211         temp = temp->inner;
 212       }
 213 !   if (need_perfect_nest)
 214       {
 215         if (!perfect_nestify (currloops, loop_nest,
 216                             lboundvars, uboundvars, steps, *inductionvars))
 217 --- 1525,1538 ----
 218                                          &lboundvars, &uboundvars,
 219                                          &steps);
 220         if (!newloop)
 221 !       goto fail;
 222 !
 223         VEC_safe_push (tree, heap, *inductionvars, inductionvar);
 224         VEC_safe_push (lambda_loop, heap, loops, newloop);
 225         temp = temp->inner;
 226       }
 227 !
 228 !   if (!perfect_nest)
 229       {
 230         if (!perfect_nestify (currloops, loop_nest,
 231                             lboundvars, uboundvars, steps, *inductionvars))
 232 *************** gcc_loopnest_to_lambda_loopnest (struct
 233 *** 1542,1550 ****
 234 --- 1546,1557 ----
 235         fprintf (dump_file,
 236                  "Successfully converted loop nest to perfect loop nest.\n");
 237       }
 238 +
 239     ret = lambda_loopnest_new (depth, 2 * depth);
 240 +
 241     for (i = 0; VEC_iterate (lambda_loop, loops, i, newloop); i++)
 242       LN_LOOPS (ret)[i] = newloop;
 243 +
 244    fail:
 245     VEC_free (lambda_loop, heap, loops);
 246     VEC_free (tree, heap, uboundvars);
 247 *************** replace_uses_equiv_to_x_with_y (struct l
 248 *** 2156,2168 ****
 249       {
 250         tree use = USE_FROM_PTR (use_p);
 251         tree step = NULL_TREE;
 252 !       tree access_fn = NULL_TREE;
 253 !
 254 !
 255 !       access_fn = instantiate_parameters
 256 !       (loop, analyze_scalar_evolution (loop, use));
 257 !       if (access_fn != NULL_TREE && access_fn != chrec_dont_know)
 258 !       step = evolution_part_in_loop_num (access_fn, loop->num);
 259         if ((step && step != chrec_dont_know
 260            && TREE_CODE (step) == INTEGER_CST
 261            && int_cst_value (step) == xstep)
 262 --- 2163,2174 ----
 263       {
 264         tree use = USE_FROM_PTR (use_p);
 265         tree step = NULL_TREE;
 266 !       tree scev = instantiate_parameters (loop,
 267 !                                         analyze_scalar_evolution (loop, use));
 268 !
 269 !       if (scev != NULL_TREE && scev != chrec_dont_know)
 270 !       step = evolution_part_in_loop_num (scev, loop->num);
 271 !
 272         if ((step && step != chrec_dont_know
 273            && TREE_CODE (step) == INTEGER_CST
 274            && int_cst_value (step) == xstep)
 275 *************** replace_uses_equiv_to_x_with_y (struct l
 276 *** 2171,2192 ****
 277       }
 278   }
 279
 280 - /* Return TRUE if STMT uses tree OP in it's uses.  */
 281 -
 282 - static bool
 283 - stmt_uses_op (tree stmt, tree op)
 284 - {
 285 -   ssa_op_iter iter;
 286 -   tree use;
 287 -
 288 -   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 289 -     {
 290 -       if (use == op)
 291 -       return true;
 292 -     }
 293 -   return false;
 294 - }
 295 -
 296   /* Return true if STMT is an exit PHI for LOOP */
 297
 298   static bool
 299 --- 2177,2182 ----
 300 *************** can_put_in_inner_loop (struct loop *inne
 301 *** 2236,2250 ****
 302
 303   }
 304
 305
 306 ! /* Return TRUE if LOOP is an imperfect nest that we can convert to a perfect
 307 !    one.  LOOPIVS is a vector of induction variables, one per loop.
 308 !    ATM, we only handle imperfect nests of depth 2, where all of the statements
 309 !    occur after the inner loop.  */
 310
 311   static bool
 312 ! can_convert_to_perfect_nest (struct loop *loop,
 313 !                            VEC(tree,heap) *loopivs)
 314   {
 315     basic_block *bbs;
 316     tree exit_condition, phi;
 317 --- 2226,2264 ----
 318
 319   }
 320
 321 + /* Return true if STMT can be put *after* the inner loop of LOOP.  */
 322 +
 323 + static bool
 324 + can_put_after_inner_loop (struct loop *loop, tree stmt)
 325 + {
 326 +   imm_use_iterator imm_iter;
 327 +   use_operand_p use_p;
 328 +
 329 +   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
 330 +     return false;
 331 +
 332 +   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, TREE_OPERAND (stmt, 0))
 333 +     {
 334 +       if (!exit_phi_for_loop_p (loop, USE_STMT (use_p)))
 335 +       {
 336 +         basic_block immbb = bb_for_stmt (USE_STMT (use_p));
 337 +
 338 +         if (!dominated_by_p (CDI_DOMINATORS,
 339 +                              immbb,
 340 +                              loop->inner->header)
 341 +             && !can_put_in_inner_loop (loop->inner, stmt))
 342 +           return false;
 343 +       }
 344 +     }
 345 +   return true;
 346 + }
 347
 348 ! /* Return TRUE if LOOP is an imperfect nest that we can convert to a
 349 !    perfect one.  At the moment, we only handle imperfect nests of
 350 !    depth 2, where all of the statements occur after the inner loop.  */
 351
 352   static bool
 353 ! can_convert_to_perfect_nest (struct loop *loop)
 354   {
 355     basic_block *bbs;
 356     tree exit_condition, phi;
 357 *************** can_convert_to_perfect_nest (struct loop
 358 *** 2264,2282 ****
 359         {
 360           for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 361             {
 362 -             size_t j;
 363               tree stmt = bsi_stmt (bsi);
 364 !             tree iv;
 365 !
 366               if (stmt == exit_condition
 367                   || not_interesting_stmt (stmt)
 368                   || stmt_is_bumper_for_loop (loop, stmt))
 369                 continue;
 370 !             /* If the statement uses inner loop ivs, we == screwed.  */
 371 !             for (j = 1; VEC_iterate (tree, loopivs, j, iv); j++)
 372 !               if (stmt_uses_op (stmt, iv))
 373 !                 goto fail;
 374 !
 375               /* If this is a simple operation like a cast that is invariant
 376                  in the inner loop, only used there, and we can place it
 377                  there, then it's not going to hurt us.
 378 --- 2278,2290 ----
 379         {
 380           for (bsi = bsi_start (bbs[i]); !bsi_end_p (bsi); bsi_next (&bsi))
 381             {
 382               tree stmt = bsi_stmt (bsi);
 383 !
 384               if (stmt == exit_condition
 385                   || not_interesting_stmt (stmt)
 386                   || stmt_is_bumper_for_loop (loop, stmt))
 387                 continue;
 388 !
 389               /* If this is a simple operation like a cast that is invariant
 390                  in the inner loop, only used there, and we can place it
 391                  there, then it's not going to hurt us.
 392 *************** can_convert_to_perfect_nest (struct loop
 393 *** 2286,2295 ****
 394                  theory that we are going to gain a lot more by interchanging
 395                  the loop than we are by leaving some invariant code there for
 396                  some other pass to clean up.  */
 397 !             if (TREE_CODE (stmt) == MODIFY_EXPR
 398 !                 && is_gimple_cast (TREE_OPERAND (stmt, 1))
 399 !                 && can_put_in_inner_loop (loop->inner, stmt))
 400 !               continue;
 401
 402               /* Otherwise, if the bb of a statement we care about isn't
 403                  dominated by the header of the inner loop, then we can't
 404 --- 2294,2358 ----
 405                  theory that we are going to gain a lot more by interchanging
 406                  the loop than we are by leaving some invariant code there for
 407                  some other pass to clean up.  */
 408 !             if (TREE_CODE (stmt) == MODIFY_EXPR)
 409 !               {
 410 !                 use_operand_p use_a, use_b;
 411 !                 imm_use_iterator imm_iter;
 412 !                 ssa_op_iter op_iter, op_iter1;
 413 !                 tree op0 = TREE_OPERAND (stmt, 0);
 414 !                 tree scev = instantiate_parameters
 415 !                   (loop, analyze_scalar_evolution (loop, op0));
 416 !
 417 !                 /* If the IV is simple, it can be duplicated.  */
 418 !                 if (!automatically_generated_chrec_p (scev))
 419 !                   {
 420 !                     tree step = evolution_part_in_loop_num (scev, loop->num);
 421 !                     if (step && step != chrec_dont_know
 422 !                         && TREE_CODE (step) == INTEGER_CST)
 423 !                       continue;
 424 !                   }
 425 !
 426 !                 /* The statement should not define a variable used
 427 !                    in the inner loop.  */
 428 !                 if (TREE_CODE (op0) == SSA_NAME)
 429 !                   FOR_EACH_IMM_USE_FAST (use_a, imm_iter, op0)
 430 !                     if (bb_for_stmt (USE_STMT (use_a))->loop_father
 431 !                         == loop->inner)
 432 !                       goto fail;
 433 !
 434 !                 FOR_EACH_SSA_USE_OPERAND (use_a, stmt, op_iter, SSA_OP_USE)
 435 !                   {
 436 !                     tree node, op = USE_FROM_PTR (use_a);
 437 !
 438 !                     /* The variables should not be used in both loops.  */
 439 !                     FOR_EACH_IMM_USE_FAST (use_b, imm_iter, op)
 440 !                     if (bb_for_stmt (USE_STMT (use_b))->loop_father
 441 !                         == loop->inner)
 442 !                       goto fail;
 443 !
 444 !                     /* The statement should not use the value of a
 445 !                        scalar that was modified in the loop.  */
 446 !                     node = SSA_NAME_DEF_STMT (op);
 447 !                     if (TREE_CODE (node) == PHI_NODE)
 448 !                       FOR_EACH_PHI_ARG (use_b, node, op_iter1, SSA_OP_USE)
 449 !                         {
 450 !                           tree arg = USE_FROM_PTR (use_b);
 451 !
 452 !                           if (TREE_CODE (arg) == SSA_NAME)
 453 !                             {
 454 !                               tree arg_stmt = SSA_NAME_DEF_STMT (arg);
 455 !
 456 !                               if (bb_for_stmt (arg_stmt)->loop_father
 457 !                                   == loop->inner)
 458 !                                 goto fail;
 459 !                             }
 460 !                         }
 461 !                   }
 462 !
 463 !                 if (can_put_in_inner_loop (loop->inner, stmt)
 464 !                     || can_put_after_inner_loop (loop, stmt))
 465 !                   continue;
 466 !               }
 467
 468               /* Otherwise, if the bb of a statement we care about isn't
 469                  dominated by the header of the inner loop, then we can't
 470 *************** perfect_nestify (struct loops *loops,
 471 *** 2379,2392 ****
 472     tree stmt;
 473     tree oldivvar, ivvar, ivvarinced;
 474     VEC(tree,heap) *phis = NULL;
 475 !
 476 !   if (!can_convert_to_perfect_nest (loop, loopivs))
 477 !     return false;
 478 !
 479 !   /* Create the new loop */
 480 !
 481     olddest = loop->single_exit->dest;
 482 !   preheaderbb =  loop_split_edge_with (loop->single_exit, NULL);
 483     headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
 484
 485     /* Push the exit phi nodes that we are moving.  */
 486 --- 2442,2451 ----
 487     tree stmt;
 488     tree oldivvar, ivvar, ivvarinced;
 489     VEC(tree,heap) *phis = NULL;
 490 !
 491 !   /* Create the new loop.  */
 492     olddest = loop->single_exit->dest;
 493 !   preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
 494     headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
 495
 496     /* Push the exit phi nodes that we are moving.  */
 497 *************** perfect_nestify (struct loops *loops,
 498 *** 2552,2561 ****
 499                       continue;
 500                     }
 501
 502 !                 replace_uses_equiv_to_x_with_y (loop, stmt,
 503 !                                                 oldivvar,
 504 !                                                 VEC_index (int, steps, 0),
 505 !                                                 ivvar);
 506                   bsi_move_before (&bsi, &tobsi);
 507
 508                   /* If the statement has any virtual operands, they may
 509 --- 2611,2619 ----
 510                       continue;
 511                     }
 512
 513 !                 replace_uses_equiv_to_x_with_y
 514 !                   (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar);
 515 !
 516                   bsi_move_before (&bsi, &tobsi);
 517
 518                   /* If the statement has any virtual operands, they may
 519