Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-loop-unswitch.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 24 May 2010 12:47:05 +0900 |
| parents | 77e2b8dfacca |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* Loop unswitching. |
| 2 Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 |
| 0 | 4 This file is part of GCC. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
5 |
| 0 | 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. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
10 |
| 0 | 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. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
15 |
| 0 | 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 "tm.h" | |
| 24 #include "tree.h" | |
| 25 #include "tm_p.h" | |
| 26 #include "basic-block.h" | |
| 27 #include "output.h" | |
| 28 #include "diagnostic.h" | |
| 29 #include "tree-flow.h" | |
| 30 #include "tree-dump.h" | |
| 31 #include "timevar.h" | |
| 32 #include "cfgloop.h" | |
| 33 #include "params.h" | |
| 34 #include "tree-pass.h" | |
| 35 #include "tree-inline.h" | |
| 36 | |
| 37 /* This file implements the loop unswitching, i.e. transformation of loops like | |
| 38 | |
| 39 while (A) | |
| 40 { | |
| 41 if (inv) | |
| 42 B; | |
| 43 | |
| 44 X; | |
| 45 | |
| 46 if (!inv) | |
| 47 C; | |
| 48 } | |
| 49 | |
| 50 where inv is the loop invariant, into | |
| 51 | |
| 52 if (inv) | |
| 53 { | |
| 54 while (A) | |
| 55 { | |
| 56 B; | |
| 57 X; | |
| 58 } | |
| 59 } | |
| 60 else | |
| 61 { | |
| 62 while (A) | |
| 63 { | |
| 64 X; | |
| 65 C; | |
| 66 } | |
| 67 } | |
| 68 | |
| 69 Inv is considered invariant iff the values it compares are both invariant; | |
| 70 tree-ssa-loop-im.c ensures that all the suitable conditions are in this | |
| 71 shape. */ | |
| 72 | |
| 73 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree); | |
| 74 static bool tree_unswitch_single_loop (struct loop *, int); | |
| 75 static tree tree_may_unswitch_on (basic_block, struct loop *); | |
| 76 | |
| 77 /* Main entry point. Perform loop unswitching on all suitable loops. */ | |
| 78 | |
| 79 unsigned int | |
| 80 tree_ssa_unswitch_loops (void) | |
| 81 { | |
| 82 loop_iterator li; | |
| 83 struct loop *loop; | |
| 84 bool changed = false; | |
| 85 | |
| 86 /* Go through inner loops (only original ones). */ | |
| 87 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) | |
| 88 { | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
89 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
90 fprintf (dump_file, ";; Considering loop %d\n", loop->num); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
91 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
92 /* Do not unswitch in cold regions. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
93 if (optimize_loop_for_size_p (loop)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
94 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
95 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
96 fprintf (dump_file, ";; Not unswitching cold loops\n"); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
97 continue; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
98 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
99 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
100 /* The loop should not be too large, to limit code growth. */ |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
101 if (tree_num_loop_insns (loop, &eni_size_weights) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
102 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
103 { |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
104 if (dump_file && (dump_flags & TDF_DETAILS)) |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
105 fprintf (dump_file, ";; Not unswitching, loop too big\n"); |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
106 continue; |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
107 } |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
108 |
| 0 | 109 changed |= tree_unswitch_single_loop (loop, 0); |
| 110 } | |
| 111 | |
| 112 if (changed) | |
| 113 return TODO_cleanup_cfg; | |
| 114 return 0; | |
| 115 } | |
| 116 | |
| 117 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its | |
| 118 basic blocks (for what it means see comments below). */ | |
| 119 | |
| 120 static tree | |
| 121 tree_may_unswitch_on (basic_block bb, struct loop *loop) | |
| 122 { | |
| 123 gimple stmt, def; | |
| 124 tree cond, use; | |
| 125 basic_block def_bb; | |
| 126 ssa_op_iter iter; | |
| 127 | |
| 128 /* BB must end in a simple conditional jump. */ | |
| 129 stmt = last_stmt (bb); | |
| 130 if (!stmt || gimple_code (stmt) != GIMPLE_COND) | |
| 131 return NULL_TREE; | |
| 132 | |
| 133 /* Condition must be invariant. */ | |
| 134 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) | |
| 135 { | |
| 136 def = SSA_NAME_DEF_STMT (use); | |
| 137 def_bb = gimple_bb (def); | |
| 138 if (def_bb | |
| 139 && flow_bb_inside_loop_p (loop, def_bb)) | |
| 140 return NULL_TREE; | |
| 141 } | |
| 142 | |
| 143 cond = build2 (gimple_cond_code (stmt), boolean_type_node, | |
| 144 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); | |
| 145 | |
| 146 /* To keep the things simple, we do not directly remove the conditions, | |
| 147 but just replace tests with 0/1. Prevent the infinite loop where we | |
| 148 would unswitch again on such a condition. */ | |
| 149 if (integer_zerop (cond) || integer_nonzerop (cond)) | |
| 150 return NULL_TREE; | |
| 151 | |
| 152 return cond; | |
| 153 } | |
| 154 | |
| 155 /* Simplifies COND using checks in front of the entry of the LOOP. Just very | |
| 156 simplish (sufficient to prevent us from duplicating loop in unswitching | |
| 157 unnecessarily). */ | |
| 158 | |
| 159 static tree | |
| 160 simplify_using_entry_checks (struct loop *loop, tree cond) | |
| 161 { | |
| 162 edge e = loop_preheader_edge (loop); | |
| 163 gimple stmt; | |
| 164 | |
| 165 while (1) | |
| 166 { | |
| 167 stmt = last_stmt (e->src); | |
| 168 if (stmt | |
| 169 && gimple_code (stmt) == GIMPLE_COND | |
| 170 && gimple_cond_code (stmt) == TREE_CODE (cond) | |
| 171 && operand_equal_p (gimple_cond_lhs (stmt), | |
| 172 TREE_OPERAND (cond, 0), 0) | |
| 173 && operand_equal_p (gimple_cond_rhs (stmt), | |
| 174 TREE_OPERAND (cond, 1), 0)) | |
| 175 return (e->flags & EDGE_TRUE_VALUE | |
| 176 ? boolean_true_node | |
| 177 : boolean_false_node); | |
| 178 | |
| 179 if (!single_pred_p (e->src)) | |
| 180 return cond; | |
| 181 | |
| 182 e = single_pred_edge (e->src); | |
| 183 if (e->src == ENTRY_BLOCK_PTR) | |
| 184 return cond; | |
| 185 } | |
| 186 } | |
| 187 | |
| 188 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow | |
| 189 it to grow too much, it is too easy to create example on that the code would | |
| 190 grow exponentially. */ | |
| 191 | |
| 192 static bool | |
| 193 tree_unswitch_single_loop (struct loop *loop, int num) | |
| 194 { | |
| 195 basic_block *bbs; | |
| 196 struct loop *nloop; | |
| 197 unsigned i; | |
| 198 tree cond = NULL_TREE; | |
| 199 gimple stmt; | |
| 200 bool changed = false; | |
| 201 | |
| 202 /* Do not unswitch too much. */ | |
| 203 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) | |
| 204 { | |
| 205 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 206 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); | |
| 207 return false; | |
| 208 } | |
| 209 | |
| 210 i = 0; | |
| 211 bbs = get_loop_body (loop); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
212 |
| 0 | 213 while (1) |
| 214 { | |
| 215 /* Find a bb to unswitch on. */ | |
| 216 for (; i < loop->num_nodes; i++) | |
| 217 if ((cond = tree_may_unswitch_on (bbs[i], loop))) | |
| 218 break; | |
| 219 | |
| 220 if (i == loop->num_nodes) | |
| 221 { | |
| 222 free (bbs); | |
| 223 return changed; | |
| 224 } | |
| 225 | |
| 226 cond = simplify_using_entry_checks (loop, cond); | |
| 227 stmt = last_stmt (bbs[i]); | |
| 228 if (integer_nonzerop (cond)) | |
| 229 { | |
| 230 /* Remove false path. */ | |
| 231 gimple_cond_set_condition_from_tree (stmt, boolean_true_node); | |
| 232 changed = true; | |
| 233 } | |
| 234 else if (integer_zerop (cond)) | |
| 235 { | |
| 236 /* Remove true path. */ | |
| 237 gimple_cond_set_condition_from_tree (stmt, boolean_false_node); | |
| 238 changed = true; | |
| 239 } | |
| 240 else | |
| 241 break; | |
| 242 | |
| 243 update_stmt (stmt); | |
| 244 i++; | |
| 245 } | |
| 246 | |
| 247 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 248 fprintf (dump_file, ";; Unswitching loop\n"); | |
| 249 | |
| 250 initialize_original_copy_tables (); | |
| 251 /* Unswitch the loop on this condition. */ | |
| 252 nloop = tree_unswitch_loop (loop, bbs[i], cond); | |
| 253 if (!nloop) | |
| 254 { | |
| 255 free_original_copy_tables (); | |
| 256 free (bbs); | |
| 257 return changed; | |
| 258 } | |
| 259 | |
| 260 /* Update the SSA form after unswitching. */ | |
| 261 update_ssa (TODO_update_ssa); | |
| 262 free_original_copy_tables (); | |
| 263 | |
| 264 /* Invoke itself on modified loops. */ | |
| 265 tree_unswitch_single_loop (nloop, num + 1); | |
| 266 tree_unswitch_single_loop (loop, num + 1); | |
| 267 free (bbs); | |
| 268 return true; | |
| 269 } | |
| 270 | |
| 271 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support | |
| 272 unswitching of innermost loops. COND is the condition determining which | |
| 273 loop is entered -- the new loop is entered if COND is true. Returns NULL | |
| 274 if impossible, new loop otherwise. */ | |
| 275 | |
| 276 static struct loop * | |
| 277 tree_unswitch_loop (struct loop *loop, | |
| 278 basic_block unswitch_on, tree cond) | |
| 279 { | |
| 280 unsigned prob_true; | |
| 281 edge edge_true, edge_false; | |
| 282 | |
| 283 /* Some sanity checking. */ | |
| 284 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); | |
| 285 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); | |
| 286 gcc_assert (loop->inner == NULL); | |
| 287 | |
| 288 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); | |
| 289 prob_true = edge_true->probability; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
290 return loop_version (loop, unshare_expr (cond), |
| 0 | 291 NULL, prob_true, prob_true, |
| 292 REG_BR_PROB_BASE - prob_true, false); | |
| 293 } |