Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-phiopt.c @ 67:f6334be47118

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 22 Mar 2011 17:18:12 +0900
parents b7f97abdc517
children 04ced10e8804
comparison
equal deleted inserted replaced
65:65488c3d617d 67:f6334be47118
1 /* Optimization of PHI nodes by converting them into straightline code. 1 /* Optimization of PHI nodes by converting them into straightline code.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Inc. 3 Free Software Foundation, Inc.
4 4
5 This file is part of GCC. 5 This file is part of GCC.
6 6
7 GCC is free software; you can redistribute it and/or modify it 7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the 8 under the terms of the GNU General Public License as published by the
26 #include "tree.h" 26 #include "tree.h"
27 #include "flags.h" 27 #include "flags.h"
28 #include "tm_p.h" 28 #include "tm_p.h"
29 #include "basic-block.h" 29 #include "basic-block.h"
30 #include "timevar.h" 30 #include "timevar.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h" 31 #include "tree-flow.h"
33 #include "tree-pass.h" 32 #include "tree-pass.h"
34 #include "tree-dump.h" 33 #include "tree-dump.h"
35 #include "langhooks.h" 34 #include "langhooks.h"
36 #include "pointer-set.h" 35 #include "pointer-set.h"
46 edge, edge, gimple, tree, tree); 45 edge, edge, gimple, tree, tree);
47 static bool abs_replacement (basic_block, basic_block, 46 static bool abs_replacement (basic_block, basic_block,
48 edge, edge, gimple, tree, tree); 47 edge, edge, gimple, tree, tree);
49 static bool cond_store_replacement (basic_block, basic_block, edge, edge, 48 static bool cond_store_replacement (basic_block, basic_block, edge, edge,
50 struct pointer_set_t *); 49 struct pointer_set_t *);
50 static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block);
51 static struct pointer_set_t * get_non_trapping (void); 51 static struct pointer_set_t * get_non_trapping (void);
52 static void replace_phi_edge_with_variable (basic_block, edge, gimple, tree); 52 static void replace_phi_edge_with_variable (basic_block, edge, gimple, tree);
53 53
54 /* This pass tries to replaces an if-then-else block with an 54 /* This pass tries to replaces an if-then-else block with an
55 assignment. We have four kinds of transformations. Some of these 55 assignment. We have four kinds of transformations. Some of these
148 blocks. In particular it replaces this: 148 blocks. In particular it replaces this:
149 149
150 bb0: 150 bb0:
151 if (cond) goto bb2; else goto bb1; 151 if (cond) goto bb2; else goto bb1;
152 bb1: 152 bb1:
153 *p = RHS 153 *p = RHS;
154 bb2: 154 bb2:
155 155
156 with 156 with
157 157
158 bb0: 158 bb0:
159 if (cond) goto bb1; else goto bb2; 159 if (cond) goto bb1; else goto bb2;
160 bb1: 160 bb1:
161 condtmp' = *p; 161 condtmp' = *p;
162 bb2: 162 bb2:
163 condtmp = PHI <RHS, condtmp'> 163 condtmp = PHI <RHS, condtmp'>
164 *p = condtmp 164 *p = condtmp;
165 165
166 This transformation can only be done under several constraints, 166 This transformation can only be done under several constraints,
167 documented below. */ 167 documented below. It also replaces:
168
169 bb0:
170 if (cond) goto bb2; else goto bb1;
171 bb1:
172 *p = RHS1;
173 goto bb3;
174 bb2:
175 *p = RHS2;
176 bb3:
177
178 with
179
180 bb0:
181 if (cond) goto bb3; else goto bb1;
182 bb1:
183 bb3:
184 condtmp = PHI <RHS1, RHS2>
185 *p = condtmp; */
168 186
169 static unsigned int 187 static unsigned int
170 tree_ssa_cs_elim (void) 188 tree_ssa_cs_elim (void)
171 { 189 {
172 return tree_ssa_phiopt_worker (true); 190 return tree_ssa_phiopt_worker (true);
247 bb1 = bb2; 265 bb1 = bb2;
248 bb2 = bb_tmp; 266 bb2 = bb_tmp;
249 e1 = e2; 267 e1 = e2;
250 e2 = e_tmp; 268 e2 = e_tmp;
251 } 269 }
270 else if (do_store_elim
271 && EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest)
272 {
273 basic_block bb3 = EDGE_SUCC (bb1, 0)->dest;
274
275 if (!single_succ_p (bb1)
276 || (EDGE_SUCC (bb1, 0)->flags & EDGE_FALLTHRU) == 0
277 || !single_succ_p (bb2)
278 || (EDGE_SUCC (bb2, 0)->flags & EDGE_FALLTHRU) == 0
279 || EDGE_COUNT (bb3->preds) != 2)
280 continue;
281 if (cond_if_else_store_replacement (bb1, bb2, bb3))
282 cfgchanged = true;
283 continue;
284 }
252 else 285 else
253 continue; 286 continue;
254 287
255 e1 = EDGE_SUCC (bb1, 0); 288 e1 = EDGE_SUCC (bb1, 0);
256 289
257 /* Make sure that bb1 is just a fall through. */ 290 /* Make sure that bb1 is just a fall through. */
258 if (!single_succ_p (bb1) 291 if (!single_succ_p (bb1)
993 return true; 1026 return true;
994 } 1027 }
995 1028
996 /* Auxiliary functions to determine the set of memory accesses which 1029 /* Auxiliary functions to determine the set of memory accesses which
997 can't trap because they are preceded by accesses to the same memory 1030 can't trap because they are preceded by accesses to the same memory
998 portion. We do that for INDIRECT_REFs, so we only need to track 1031 portion. We do that for MEM_REFs, so we only need to track
999 the SSA_NAME of the pointer indirectly referenced. The algorithm 1032 the SSA_NAME of the pointer indirectly referenced. The algorithm
1000 simply is a walk over all instructions in dominator order. When 1033 simply is a walk over all instructions in dominator order. When
1001 we see an INDIRECT_REF we determine if we've already seen a same 1034 we see an MEM_REF we determine if we've already seen a same
1002 ref anywhere up to the root of the dominator tree. If we do the 1035 ref anywhere up to the root of the dominator tree. If we do the
1003 current access can't trap. If we don't see any dominating access 1036 current access can't trap. If we don't see any dominating access
1004 the current access might trap, but might also make later accesses 1037 the current access might trap, but might also make later accesses
1005 non-trapping, so we remember it. We need to be careful with loads 1038 non-trapping, so we remember it. We need to be careful with loads
1006 or stores, for instance a load might not trap, while a store would, 1039 or stores, for instance a load might not trap, while a store would,
1010 1043
1011 ??? We currently are very conservative and assume that a load might 1044 ??? We currently are very conservative and assume that a load might
1012 trap even if a store doesn't (write-only memory). This probably is 1045 trap even if a store doesn't (write-only memory). This probably is
1013 overly conservative. */ 1046 overly conservative. */
1014 1047
1015 /* A hash-table of SSA_NAMEs, and in which basic block an INDIRECT_REF 1048 /* A hash-table of SSA_NAMEs, and in which basic block an MEM_REF
1016 through it was seen, which would constitute a no-trap region for 1049 through it was seen, which would constitute a no-trap region for
1017 same accesses. */ 1050 same accesses. */
1018 struct name_to_bb 1051 struct name_to_bb
1019 { 1052 {
1020 tree ssa_name; 1053 tree ssa_name;
1023 }; 1056 };
1024 1057
1025 /* The hash table for remembering what we've seen. */ 1058 /* The hash table for remembering what we've seen. */
1026 static htab_t seen_ssa_names; 1059 static htab_t seen_ssa_names;
1027 1060
1028 /* The set of INDIRECT_REFs which can't trap. */ 1061 /* The set of MEM_REFs which can't trap. */
1029 static struct pointer_set_t *nontrap_set; 1062 static struct pointer_set_t *nontrap_set;
1030 1063
1031 /* The hash function, based on the pointer to the pointer SSA_NAME. */ 1064 /* The hash function, based on the pointer to the pointer SSA_NAME. */
1032 static hashval_t 1065 static hashval_t
1033 name_to_bb_hash (const void *p) 1066 name_to_bb_hash (const void *p)
1046 1079
1047 return n1->ssa_name == n2->ssa_name && n1->store == n2->store; 1080 return n1->ssa_name == n2->ssa_name && n1->store == n2->store;
1048 } 1081 }
1049 1082
1050 /* We see the expression EXP in basic block BB. If it's an interesting 1083 /* We see the expression EXP in basic block BB. If it's an interesting
1051 expression (an INDIRECT_REF through an SSA_NAME) possibly insert the 1084 expression (an MEM_REF through an SSA_NAME) possibly insert the
1052 expression into the set NONTRAP or the hash table of seen expressions. 1085 expression into the set NONTRAP or the hash table of seen expressions.
1053 STORE is true if this expression is on the LHS, otherwise it's on 1086 STORE is true if this expression is on the LHS, otherwise it's on
1054 the RHS. */ 1087 the RHS. */
1055 static void 1088 static void
1056 add_or_mark_expr (basic_block bb, tree exp, 1089 add_or_mark_expr (basic_block bb, tree exp,
1057 struct pointer_set_t *nontrap, bool store) 1090 struct pointer_set_t *nontrap, bool store)
1058 { 1091 {
1059 if (INDIRECT_REF_P (exp) 1092 if (TREE_CODE (exp) == MEM_REF
1060 && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME) 1093 && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME)
1061 { 1094 {
1062 tree name = TREE_OPERAND (exp, 0); 1095 tree name = TREE_OPERAND (exp, 0);
1063 struct name_to_bb map; 1096 struct name_to_bb map;
1064 void **slot; 1097 void **slot;
1065 struct name_to_bb *n2bb; 1098 struct name_to_bb *n2bb;
1066 basic_block found_bb = 0; 1099 basic_block found_bb = 0;
1067 1100
1068 /* Try to find the last seen INDIRECT_REF through the same 1101 /* Try to find the last seen MEM_REF through the same
1069 SSA_NAME, which can trap. */ 1102 SSA_NAME, which can trap. */
1070 map.ssa_name = name; 1103 map.ssa_name = name;
1071 map.bb = 0; 1104 map.bb = 0;
1072 map.store = store; 1105 map.store = store;
1073 slot = htab_find_slot (seen_ssa_names, &map, INSERT); 1106 slot = htab_find_slot (seen_ssa_names, &map, INSERT);
1074 n2bb = (struct name_to_bb *) *slot; 1107 n2bb = (struct name_to_bb *) *slot;
1075 if (n2bb) 1108 if (n2bb)
1076 found_bb = n2bb->bb; 1109 found_bb = n2bb->bb;
1077 1110
1078 /* If we've found a trapping INDIRECT_REF, _and_ it dominates EXP 1111 /* If we've found a trapping MEM_REF, _and_ it dominates EXP
1079 (it's in a basic block on the path from us to the dominator root) 1112 (it's in a basic block on the path from us to the dominator root)
1080 then we can't trap. */ 1113 then we can't trap. */
1081 if (found_bb && found_bb->aux == (void *)1) 1114 if (found_bb && found_bb->aux == (void *)1)
1082 { 1115 {
1083 pointer_set_insert (nontrap, exp); 1116 pointer_set_insert (nontrap, exp);
1134 } 1167 }
1135 1168
1136 /* This is the entry point of gathering non trapping memory accesses. 1169 /* This is the entry point of gathering non trapping memory accesses.
1137 It will do a dominator walk over the whole function, and it will 1170 It will do a dominator walk over the whole function, and it will
1138 make use of the bb->aux pointers. It returns a set of trees 1171 make use of the bb->aux pointers. It returns a set of trees
1139 (the INDIRECT_REFs itself) which can't trap. */ 1172 (the MEM_REFs itself) which can't trap. */
1140 static struct pointer_set_t * 1173 static struct pointer_set_t *
1141 get_non_trapping (void) 1174 get_non_trapping (void)
1142 { 1175 {
1143 struct pointer_set_t *nontrap; 1176 struct pointer_set_t *nontrap;
1144 struct dom_walk_data walk_data; 1177 struct dom_walk_data walk_data;
1189 gimple assign = last_and_only_stmt (middle_bb); 1222 gimple assign = last_and_only_stmt (middle_bb);
1190 tree lhs, rhs, name; 1223 tree lhs, rhs, name;
1191 gimple newphi, new_stmt; 1224 gimple newphi, new_stmt;
1192 gimple_stmt_iterator gsi; 1225 gimple_stmt_iterator gsi;
1193 source_location locus; 1226 source_location locus;
1194 enum tree_code code;
1195 1227
1196 /* Check if middle_bb contains of only one store. */ 1228 /* Check if middle_bb contains of only one store. */
1197 if (!assign 1229 if (!assign
1198 || gimple_code (assign) != GIMPLE_ASSIGN) 1230 || !gimple_assign_single_p (assign))
1199 return false; 1231 return false;
1200 1232
1201 locus = gimple_location (assign); 1233 locus = gimple_location (assign);
1202 lhs = gimple_assign_lhs (assign); 1234 lhs = gimple_assign_lhs (assign);
1203 rhs = gimple_assign_rhs1 (assign); 1235 rhs = gimple_assign_rhs1 (assign);
1204 if (!INDIRECT_REF_P (lhs)) 1236 if (TREE_CODE (lhs) != MEM_REF
1205 return false; 1237 || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME
1206 1238 || !is_gimple_reg_type (TREE_TYPE (lhs)))
1207 /* RHS is either a single SSA_NAME or a constant. */ 1239 return false;
1208 code = gimple_assign_rhs_code (assign); 1240
1209 if (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
1210 || (code != SSA_NAME && !is_gimple_min_invariant (rhs)))
1211 return false;
1212 /* Prove that we can move the store down. We could also check 1241 /* Prove that we can move the store down. We could also check
1213 TREE_THIS_NOTRAP here, but in that case we also could move stores, 1242 TREE_THIS_NOTRAP here, but in that case we also could move stores,
1214 whose value is not available readily, which we want to avoid. */ 1243 whose value is not available readily, which we want to avoid. */
1215 if (!pointer_set_contains (nontrap, lhs)) 1244 if (!pointer_set_contains (nontrap, lhs))
1216 return false; 1245 return false;
1217 1246
1218 /* Now we've checked the constraints, so do the transformation: 1247 /* Now we've checked the constraints, so do the transformation:
1219 1) Remove the single store. */ 1248 1) Remove the single store. */
1220 mark_symbols_for_renaming (assign);
1221 gsi = gsi_for_stmt (assign); 1249 gsi = gsi_for_stmt (assign);
1250 unlink_stmt_vdef (assign);
1222 gsi_remove (&gsi, true); 1251 gsi_remove (&gsi, true);
1252 release_defs (assign);
1223 1253
1224 /* 2) Create a temporary where we can store the old content 1254 /* 2) Create a temporary where we can store the old content
1225 of the memory touched by the store, if we need to. */ 1255 of the memory touched by the store, if we need to. */
1226 if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp)) 1256 if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1227 { 1257 {
1235 lhs = unshare_expr (lhs); 1265 lhs = unshare_expr (lhs);
1236 new_stmt = gimple_build_assign (condstoretemp, lhs); 1266 new_stmt = gimple_build_assign (condstoretemp, lhs);
1237 name = make_ssa_name (condstoretemp, new_stmt); 1267 name = make_ssa_name (condstoretemp, new_stmt);
1238 gimple_assign_set_lhs (new_stmt, name); 1268 gimple_assign_set_lhs (new_stmt, name);
1239 gimple_set_location (new_stmt, locus); 1269 gimple_set_location (new_stmt, locus);
1240 mark_symbols_for_renaming (new_stmt);
1241 gsi_insert_on_edge (e1, new_stmt); 1270 gsi_insert_on_edge (e1, new_stmt);
1242 1271
1243 /* 4) Create a PHI node at the join block, with one argument 1272 /* 4) Create a PHI node at the join block, with one argument
1244 holding the old RHS, and the other holding the temporary 1273 holding the old RHS, and the other holding the temporary
1245 where we stored the old memory contents. */ 1274 where we stored the old memory contents. */
1247 add_phi_arg (newphi, rhs, e0, locus); 1276 add_phi_arg (newphi, rhs, e0, locus);
1248 add_phi_arg (newphi, name, e1, locus); 1277 add_phi_arg (newphi, name, e1, locus);
1249 1278
1250 lhs = unshare_expr (lhs); 1279 lhs = unshare_expr (lhs);
1251 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi)); 1280 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1252 mark_symbols_for_renaming (new_stmt);
1253 1281
1254 /* 5) Insert that PHI node. */ 1282 /* 5) Insert that PHI node. */
1283 gsi = gsi_after_labels (join_bb);
1284 if (gsi_end_p (gsi))
1285 {
1286 gsi = gsi_last_bb (join_bb);
1287 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
1288 }
1289 else
1290 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
1291
1292 return true;
1293 }
1294
1295 /* Do the main work of conditional store replacement. We already know
1296 that the recognized pattern looks like so:
1297
1298 split:
1299 if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
1300 THEN_BB:
1301 X = Y;
1302 goto JOIN_BB;
1303 ELSE_BB:
1304 X = Z;
1305 fallthrough (edge E0)
1306 JOIN_BB:
1307 some more
1308
1309 We check that THEN_BB and ELSE_BB contain only one store
1310 that the stores have a "simple" RHS. */
1311
1312 static bool
1313 cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
1314 basic_block join_bb)
1315 {
1316 gimple then_assign = last_and_only_stmt (then_bb);
1317 gimple else_assign = last_and_only_stmt (else_bb);
1318 tree lhs_base, lhs, then_rhs, else_rhs;
1319 source_location then_locus, else_locus;
1320 gimple_stmt_iterator gsi;
1321 gimple newphi, new_stmt;
1322
1323 /* Check if then_bb and else_bb contain only one store each. */
1324 if (then_assign == NULL
1325 || !gimple_assign_single_p (then_assign)
1326 || else_assign == NULL
1327 || !gimple_assign_single_p (else_assign))
1328 return false;
1329
1330 lhs = gimple_assign_lhs (then_assign);
1331 if (!is_gimple_reg_type (TREE_TYPE (lhs))
1332 || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
1333 return false;
1334
1335 lhs_base = get_base_address (lhs);
1336 if (lhs_base == NULL_TREE
1337 || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
1338 return false;
1339
1340 then_rhs = gimple_assign_rhs1 (then_assign);
1341 else_rhs = gimple_assign_rhs1 (else_assign);
1342 then_locus = gimple_location (then_assign);
1343 else_locus = gimple_location (else_assign);
1344
1345 /* Now we've checked the constraints, so do the transformation:
1346 1) Remove the stores. */
1347 gsi = gsi_for_stmt (then_assign);
1348 unlink_stmt_vdef (then_assign);
1349 gsi_remove (&gsi, true);
1350 release_defs (then_assign);
1351
1352 gsi = gsi_for_stmt (else_assign);
1353 unlink_stmt_vdef (else_assign);
1354 gsi_remove (&gsi, true);
1355 release_defs (else_assign);
1356
1357 /* 2) Create a temporary where we can store the old content
1358 of the memory touched by the store, if we need to. */
1359 if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
1360 {
1361 condstoretemp = create_tmp_reg (TREE_TYPE (lhs), "cstore");
1362 get_var_ann (condstoretemp);
1363 }
1364 add_referenced_var (condstoretemp);
1365
1366 /* 3) Create a PHI node at the join block, with one argument
1367 holding the old RHS, and the other holding the temporary
1368 where we stored the old memory contents. */
1369 newphi = create_phi_node (condstoretemp, join_bb);
1370 add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
1371 add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
1372
1373 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
1374
1375 /* 4) Insert that PHI node. */
1255 gsi = gsi_after_labels (join_bb); 1376 gsi = gsi_after_labels (join_bb);
1256 if (gsi_end_p (gsi)) 1377 if (gsi_end_p (gsi))
1257 { 1378 {
1258 gsi = gsi_last_bb (join_bb); 1379 gsi = gsi_last_bb (join_bb);
1259 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT); 1380 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);