2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
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 2, or (at your option) any
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-pass.h"
40 /* This file implements the loop unswitching, i.e. transformation of loops like
53 where inv is the loop invariant, into
72 Inv is considered invariant iff the values it compares are both invariant;
73 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
76 static struct loop
*tree_unswitch_loop (struct loops
*, struct loop
*, basic_block
,
78 static bool tree_unswitch_single_loop (struct loops
*, struct loop
*, int);
79 static tree
tree_may_unswitch_on (basic_block
, struct loop
*);
81 /* Main entry point. Perform loop unswitching on all suitable LOOPS. */
84 tree_ssa_unswitch_loops (struct loops
*loops
)
90 /* Go through inner loops (only original ones). */
93 for (i
= 1; i
< num
; i
++)
96 loop
= loops
->parray
[i
];
103 changed
|= tree_unswitch_single_loop (loops
, loop
, 0);
107 return TODO_cleanup_cfg
;
111 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
112 basic blocks (for what it means see comments below). */
115 tree_may_unswitch_on (basic_block bb
, struct loop
*loop
)
117 tree stmt
, def
, cond
, use
;
121 /* BB must end in a simple conditional jump. */
122 stmt
= last_stmt (bb
);
123 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
126 /* Condition must be invariant. */
127 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
129 def
= SSA_NAME_DEF_STMT (use
);
130 def_bb
= bb_for_stmt (def
);
132 && flow_bb_inside_loop_p (loop
, def_bb
))
136 cond
= COND_EXPR_COND (stmt
);
137 /* To keep the things simple, we do not directly remove the conditions,
138 but just replace tests with 0/1. Prevent the infinite loop where we
139 would unswitch again on such a condition. */
140 if (integer_zerop (cond
) || integer_nonzerop (cond
))
146 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
147 simplish (sufficient to prevent us from duplicating loop in unswitching
151 simplify_using_entry_checks (struct loop
*loop
, tree cond
)
153 edge e
= loop_preheader_edge (loop
);
158 stmt
= last_stmt (e
->src
);
160 && TREE_CODE (stmt
) == COND_EXPR
161 && operand_equal_p (COND_EXPR_COND (stmt
), cond
, 0))
162 return (e
->flags
& EDGE_TRUE_VALUE
164 : boolean_false_node
);
166 if (!single_pred_p (e
->src
))
169 e
= single_pred_edge (e
->src
);
170 if (e
->src
== ENTRY_BLOCK_PTR
)
175 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
176 it to grow too much, it is too easy to create example on that the code would
177 grow exponentially. */
180 tree_unswitch_single_loop (struct loops
*loops
, struct loop
*loop
, int num
)
185 tree cond
= NULL_TREE
, stmt
;
186 bool changed
= false;
188 /* Do not unswitch too much. */
189 if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
191 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
192 fprintf (dump_file
, ";; Not unswitching anymore, hit max level\n");
196 /* Only unswitch innermost loops. */
199 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
200 fprintf (dump_file
, ";; Not unswitching, not innermost loop\n");
204 /* The loop should not be too large, to limit code growth. */
205 if (tree_num_loop_insns (loop
)
206 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
209 fprintf (dump_file
, ";; Not unswitching, loop too big\n");
214 bbs
= get_loop_body (loop
);
218 /* Find a bb to unswitch on. */
219 for (; i
< loop
->num_nodes
; i
++)
220 if ((cond
= tree_may_unswitch_on (bbs
[i
], loop
)))
223 if (i
== loop
->num_nodes
)
229 cond
= simplify_using_entry_checks (loop
, cond
);
230 stmt
= last_stmt (bbs
[i
]);
231 if (integer_nonzerop (cond
))
233 /* Remove false path. */
234 COND_EXPR_COND (stmt
) = boolean_true_node
;
237 else if (integer_zerop (cond
))
239 /* Remove true path. */
240 COND_EXPR_COND (stmt
) = boolean_false_node
;
250 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
251 fprintf (dump_file
, ";; Unswitching loop\n");
253 initialize_original_copy_tables ();
254 /* Unswitch the loop on this condition. */
255 nloop
= tree_unswitch_loop (loops
, loop
, bbs
[i
], cond
);
258 free_original_copy_tables ();
263 /* Update the SSA form after unswitching. */
264 update_ssa (TODO_update_ssa
);
265 free_original_copy_tables ();
267 /* Invoke itself on modified loops. */
268 tree_unswitch_single_loop (loops
, nloop
, num
+ 1);
269 tree_unswitch_single_loop (loops
, loop
, num
+ 1);
274 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
275 unswitching of innermost loops. COND is the condition determining which
276 loop is entered -- the new loop is entered if COND is true. Returns NULL
277 if impossible, new loop otherwise. */
280 tree_unswitch_loop (struct loops
*loops
, struct loop
*loop
,
281 basic_block unswitch_on
, tree cond
)
283 basic_block condition_bb
;
285 /* Some sanity checking. */
286 gcc_assert (flow_bb_inside_loop_p (loop
, unswitch_on
));
287 gcc_assert (EDGE_COUNT (unswitch_on
->succs
) == 2);
288 gcc_assert (loop
->inner
== NULL
);
290 return loop_version (loops
, loop
, unshare_expr (cond
),
291 &condition_bb
, false);