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