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, 59 Temple Place - Suite 330, 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 cleanup_tree_cfg_loop ();
110 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
111 basic blocks (for what it means see comments below). */
114 tree_may_unswitch_on (basic_block bb
, struct loop
*loop
)
116 tree stmt
, def
, cond
;
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 uses
= STMT_USE_OPS (stmt
);
128 for (i
= 0; i
< NUM_USES (uses
); i
++)
130 def
= SSA_NAME_DEF_STMT (USE_OP (uses
, i
));
131 def_bb
= bb_for_stmt (def
);
133 && flow_bb_inside_loop_p (loop
, def_bb
))
137 cond
= COND_EXPR_COND (stmt
);
138 /* To keep the things simple, we do not directly remove the conditions,
139 but just replace tests with 0/1. Prevent the infinite loop where we
140 would unswitch again on such a condition. */
141 if (integer_zerop (cond
) || integer_nonzerop (cond
))
147 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
148 simplish (sufficient to prevent us from duplicating loop in unswitching
152 simplify_using_entry_checks (struct loop
*loop
, tree cond
)
154 edge e
= loop_preheader_edge (loop
);
159 stmt
= last_stmt (e
->src
);
161 && TREE_CODE (stmt
) == COND_EXPR
162 && operand_equal_p (COND_EXPR_COND (stmt
), cond
, 0))
163 return (e
->flags
& EDGE_TRUE_VALUE
165 : boolean_false_node
);
167 if (!single_pred_p (e
->src
))
170 e
= single_pred_edge (e
->src
);
171 if (e
->src
== ENTRY_BLOCK_PTR
)
176 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
177 it to grow too much, it is too easy to create example on that the code would
178 grow exponentially. */
181 tree_unswitch_single_loop (struct loops
*loops
, struct loop
*loop
, int num
)
186 tree cond
= NULL_TREE
, stmt
;
187 bool changed
= false;
189 /* Do not unswitch too much. */
190 if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
192 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
193 fprintf (dump_file
, ";; Not unswitching anymore, hit max level\n");
197 /* Only unswitch innermost loops. */
200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
201 fprintf (dump_file
, ";; Not unswitching, not innermost loop\n");
205 /* The loop should not be too large, to limit code growth. */
206 if (tree_num_loop_insns (loop
)
207 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
210 fprintf (dump_file
, ";; Not unswitching, loop too big\n");
215 bbs
= get_loop_body (loop
);
219 /* Find a bb to unswitch on. */
220 for (; i
< loop
->num_nodes
; i
++)
221 if ((cond
= tree_may_unswitch_on (bbs
[i
], loop
)))
224 if (i
== loop
->num_nodes
)
230 cond
= simplify_using_entry_checks (loop
, cond
);
231 stmt
= last_stmt (bbs
[i
]);
232 if (integer_nonzerop (cond
))
234 /* Remove false path. */
235 COND_EXPR_COND (stmt
) = boolean_true_node
;
238 else if (integer_zerop (cond
))
240 /* Remove true path. */
241 COND_EXPR_COND (stmt
) = boolean_false_node
;
251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
252 fprintf (dump_file
, ";; Unswitching loop\n");
254 /* Unswitch the loop on this condition. */
255 nloop
= tree_unswitch_loop (loops
, loop
, bbs
[i
], cond
);
259 /* Update the SSA form after unswitching. */
260 update_ssa (TODO_update_ssa
);
262 /* Invoke itself on modified loops. */
263 tree_unswitch_single_loop (loops
, nloop
, num
+ 1);
264 tree_unswitch_single_loop (loops
, loop
, num
+ 1);
268 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
269 unswitching of innermost loops. COND is the condition determining which
270 loop is entered -- the new loop is entered if COND is true. Returns NULL
271 if impossible, new loop otherwise. */
274 tree_unswitch_loop (struct loops
*loops
, struct loop
*loop
,
275 basic_block unswitch_on
, tree cond
)
277 basic_block condition_bb
;
279 /* Some sanity checking. */
280 gcc_assert (flow_bb_inside_loop_p (loop
, unswitch_on
));
281 gcc_assert (EDGE_COUNT (unswitch_on
->succs
) == 2);
282 gcc_assert (loop
->inner
== NULL
);
284 return loop_version (loops
, loop
, unshare_expr (cond
),