Index: gcc/gcc/tree-ssa-loop-unswitch.c |
diff --git a/gcc/gcc/tree-ssa-loop-unswitch.c b/gcc/gcc/tree-ssa-loop-unswitch.c |
index b42c70d81528c187168130d18997533b2f2a58e6..e12f2950deea3509703c3e31b505ba2d041d7ec7 100644 |
--- a/gcc/gcc/tree-ssa-loop-unswitch.c |
+++ b/gcc/gcc/tree-ssa-loop-unswitch.c |
@@ -1,18 +1,18 @@ |
/* Loop unswitching. |
- Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc. |
- |
+ Copyright (C) 2004, 2005, 2007, 2008, 2010 Free Software Foundation, Inc. |
+ |
This file is part of GCC. |
- |
+ |
GCC is free software; you can redistribute it and/or modify it |
under the terms of the GNU General Public License as published by the |
Free Software Foundation; either version 3, or (at your option) any |
later version. |
- |
+ |
GCC is distributed in the hope that it will be useful, but WITHOUT |
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
for more details. |
- |
+ |
You should have received a copy of the GNU General Public License |
along with GCC; see the file COPYING3. If not see |
<http://www.gnu.org/licenses/>. */ |
@@ -32,7 +32,6 @@ along with GCC; see the file COPYING3. If not see |
#include "tree-dump.h" |
#include "timevar.h" |
#include "cfgloop.h" |
-#include "domwalk.h" |
#include "params.h" |
#include "tree-pass.h" |
#include "tree-inline.h" |
@@ -113,6 +112,12 @@ tree_may_unswitch_on (basic_block bb, struct loop *loop) |
if (!stmt || gimple_code (stmt) != GIMPLE_COND) |
return NULL_TREE; |
+ /* To keep the things simple, we do not directly remove the conditions, |
+ but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite |
+ loop where we would unswitch again on such a condition. */ |
+ if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) |
+ return NULL_TREE; |
+ |
/* Condition must be invariant. */ |
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) |
{ |
@@ -126,12 +131,6 @@ tree_may_unswitch_on (basic_block bb, struct loop *loop) |
cond = build2 (gimple_cond_code (stmt), boolean_type_node, |
gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); |
- /* To keep the things simple, we do not directly remove the conditions, |
- but just replace tests with 0/1. Prevent the infinite loop where we |
- would unswitch again on such a condition. */ |
- if (integer_zerop (cond) || integer_nonzerop (cond)) |
- return NULL_TREE; |
- |
return cond; |
} |
@@ -177,19 +176,11 @@ tree_unswitch_single_loop (struct loop *loop, int num) |
{ |
basic_block *bbs; |
struct loop *nloop; |
- unsigned i; |
+ unsigned i, found; |
tree cond = NULL_TREE; |
gimple stmt; |
bool changed = false; |
- /* Do not unswitch too much. */ |
- if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) |
- { |
- if (dump_file && (dump_flags & TDF_DETAILS)) |
- fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); |
- return false; |
- } |
- |
/* Only unswitch innermost loops. */ |
if (loop->inner) |
{ |
@@ -217,7 +208,8 @@ tree_unswitch_single_loop (struct loop *loop, int num) |
i = 0; |
bbs = get_loop_body (loop); |
- |
+ found = loop->num_nodes; |
+ |
while (1) |
{ |
/* Find a bb to unswitch on. */ |
@@ -227,8 +219,17 @@ tree_unswitch_single_loop (struct loop *loop, int num) |
if (i == loop->num_nodes) |
{ |
- free (bbs); |
- return changed; |
+ if (dump_file |
+ && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL) |
+ && (dump_flags & TDF_DETAILS)) |
+ fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); |
+ |
+ if (found == loop->num_nodes) |
+ { |
+ free (bbs); |
+ return changed; |
+ } |
+ break; |
} |
cond = simplify_using_entry_checks (loop, cond); |
@@ -245,19 +246,107 @@ tree_unswitch_single_loop (struct loop *loop, int num) |
gimple_cond_set_condition_from_tree (stmt, boolean_false_node); |
changed = true; |
} |
+ /* Do not unswitch too much. */ |
+ else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) |
+ { |
+ i++; |
+ continue; |
+ } |
+ /* In nested tree_unswitch_single_loop first optimize all conditions |
+ using entry checks, then discover still reachable blocks in the |
+ loop and find the condition only among those still reachable bbs. */ |
+ else if (num != 0) |
+ { |
+ if (found == loop->num_nodes) |
+ found = i; |
+ i++; |
+ continue; |
+ } |
else |
- break; |
+ { |
+ found = i; |
+ break; |
+ } |
update_stmt (stmt); |
i++; |
} |
+ if (num != 0) |
+ { |
+ basic_block *tos, *worklist; |
+ |
+ /* When called recursively, first do a quick discovery |
+ of reachable bbs after the above changes and only |
+ consider conditions in still reachable bbs. */ |
+ tos = worklist = XNEWVEC (basic_block, loop->num_nodes); |
+ |
+ for (i = 0; i < loop->num_nodes; i++) |
+ bbs[i]->flags &= ~BB_REACHABLE; |
+ |
+ /* Start with marking header. */ |
+ *tos++ = bbs[0]; |
+ bbs[0]->flags |= BB_REACHABLE; |
+ |
+ /* Iterate: find everything reachable from what we've already seen |
+ within the same innermost loop. Don't look through false edges |
+ if condition is always true or true edges if condition is |
+ always false. */ |
+ while (tos != worklist) |
+ { |
+ basic_block b = *--tos; |
+ edge e; |
+ edge_iterator ei; |
+ int flags = 0; |
+ |
+ if (EDGE_COUNT (b->succs) == 2) |
+ { |
+ gimple stmt = last_stmt (b); |
+ if (stmt |
+ && gimple_code (stmt) == GIMPLE_COND) |
+ { |
+ if (gimple_cond_true_p (stmt)) |
+ flags = EDGE_FALSE_VALUE; |
+ else if (gimple_cond_false_p (stmt)) |
+ flags = EDGE_TRUE_VALUE; |
+ } |
+ } |
+ |
+ FOR_EACH_EDGE (e, ei, b->succs) |
+ { |
+ basic_block dest = e->dest; |
+ |
+ if (dest->loop_father == loop |
+ && !(dest->flags & BB_REACHABLE) |
+ && !(e->flags & flags)) |
+ { |
+ *tos++ = dest; |
+ dest->flags |= BB_REACHABLE; |
+ } |
+ } |
+ } |
+ |
+ free (worklist); |
+ |
+ /* Find a bb to unswitch on. */ |
+ for (; found < loop->num_nodes; found++) |
+ if ((bbs[found]->flags & BB_REACHABLE) |
+ && (cond = tree_may_unswitch_on (bbs[found], loop))) |
+ break; |
+ |
+ if (found == loop->num_nodes) |
+ { |
+ free (bbs); |
+ return changed; |
+ } |
+ } |
+ |
if (dump_file && (dump_flags & TDF_DETAILS)) |
fprintf (dump_file, ";; Unswitching loop\n"); |
initialize_original_copy_tables (); |
/* Unswitch the loop on this condition. */ |
- nloop = tree_unswitch_loop (loop, bbs[i], cond); |
+ nloop = tree_unswitch_loop (loop, bbs[found], cond); |
if (!nloop) |
{ |
free_original_copy_tables (); |
@@ -295,7 +384,7 @@ tree_unswitch_loop (struct loop *loop, |
extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); |
prob_true = edge_true->probability; |
- return loop_version (loop, unshare_expr (cond), |
+ return loop_version (loop, unshare_expr (cond), |
NULL, prob_true, prob_true, |
REG_BR_PROB_BASE - prob_true, false); |
} |