Left: | ||
Right: |
OLD | NEW |
---|---|
1 /* Branch prediction routines for the GNU compiler. | 1 /* Branch prediction routines for the GNU compiler. |
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010 | 2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010 |
3 Free Software Foundation, 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 under | 7 GCC is free software; you can redistribute it and/or modify it under |
8 the terms of the GNU General Public License as published by the Free | 8 the terms of the GNU General Public License as published by the Free |
9 Software Foundation; either version 3, or (at your option) any later | 9 Software Foundation; either version 3, or (at your option) any later |
10 version. | 10 version. |
(...skipping 928 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
939 } | 939 } |
940 clear_bb_predictions (bb); | 940 clear_bb_predictions (bb); |
941 | 941 |
942 if (!bb->count) | 942 if (!bb->count) |
943 { | 943 { |
944 first->probability = combined_probability; | 944 first->probability = combined_probability; |
945 second->probability = REG_BR_PROB_BASE - combined_probability; | 945 second->probability = REG_BR_PROB_BASE - combined_probability; |
946 } | 946 } |
947 } | 947 } |
948 | 948 |
949 /* Check if T1 and T2 satisfy the IV_COMPARE condition. | |
950 Return the SSA_NAME if the condition satisfies, NULL otherwise. | |
951 | |
952 T1 and T2 should be one of the following cases: | |
953 1. T1 is SSA_NAME, T2 is NULL | |
954 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4] | |
955 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */ | |
956 | |
957 static tree | |
958 find_qualified_ssa_name (tree t1, tree t2) | |
davidxl
2012/01/31 01:25:42
Better change the name into 'strips_small_constant
| |
959 { | |
960 tree ret = NULL; | |
961 int value = 0; | |
962 | |
963 if (!t1) | |
964 return NULL; | |
965 else if (TREE_CODE (t1) == SSA_NAME) | |
966 ret = t1; | |
967 else if (TREE_CODE (t1) == INTEGER_CST) | |
968 value = TREE_INT_CST_LOW (t1); | |
969 else | |
970 return NULL; | |
971 | |
972 if (!t2) | |
973 return ret; | |
974 else if (TREE_CODE (t2) == INTEGER_CST) | |
975 value = TREE_INT_CST_LOW (t2); | |
976 else if (TREE_CODE (t2) == SSA_NAME) | |
977 { | |
978 if (ret) | |
979 return NULL; | |
980 else | |
981 ret = t2; | |
982 } | |
983 | |
984 if (value <= 4 && value >= -4) | |
985 return ret; | |
986 else | |
987 return NULL; | |
988 } | |
989 | |
990 /* Return the SSA_NAME in T or T's operands. | |
991 Return NULL if T does not satisfy IV_COMPARE condition. */ | |
davidxl
2012/01/31 01:25:42
Fix comment -- there is no IV_COMPARE used here.
| |
992 | |
993 static tree | |
994 find_ssa_name_in_expr (tree t) | |
995 { | |
davidxl
2012/01/31 01:25:42
Better change the name into 'get_base_value (tree
| |
996 if (TREE_CODE (t) == SSA_NAME) | |
997 return t; | |
998 | |
999 if (!BINARY_CLASS_P (t)) | |
1000 return NULL; | |
1001 | |
1002 switch (TREE_OPERAND_LENGTH (t)) | |
1003 { | |
1004 case 1: | |
1005 return find_qualified_ssa_name (TREE_OPERAND (t, 0), NULL); | |
1006 case 2: | |
1007 return find_qualified_ssa_name (TREE_OPERAND (t, 0), | |
1008 TREE_OPERAND (t, 1)); | |
1009 default: | |
1010 return NULL; | |
1011 } | |
1012 } | |
1013 | |
1014 /* Return the SSA_NAME in the rhs of assignment STMT. | |
1015 Return NULL if STMT does not satisfy IV_COMPARE condition. */ | |
1016 | |
1017 static tree | |
1018 find_ssa_name_in_assign_stmt (gimple stmt) | |
1019 { | |
1020 gcc_assert (is_gimple_assign (stmt)); | |
1021 | |
1022 if (gimple_assign_rhs3 (stmt) != NULL) | |
1023 return NULL; | |
1024 | |
1025 return find_qualified_ssa_name (gimple_assign_rhs1 (stmt), | |
1026 gimple_assign_rhs2 (stmt)); | |
1027 } | |
1028 | |
1029 /* Check the compare STMT in LOOP. If it compares an induction | |
1030 variable to a loop invariant, return true, and save | |
1031 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP. | |
1032 Otherwise return false and set LOOP_INVAIANT to NULL. */ | |
1033 | |
1034 static bool | |
1035 is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop, | |
1036 tree *loop_invariant, | |
1037 enum tree_code *compare_code, | |
1038 int *loop_step) | |
1039 { | |
1040 tree op0, op1, bound; | |
1041 affine_iv iv0, iv1; | |
1042 enum tree_code code; | |
1043 int step; | |
1044 | |
1045 code = gimple_cond_code (stmt); | |
1046 *loop_invariant = NULL; | |
1047 | |
1048 switch (code) | |
1049 { | |
1050 case GT_EXPR: | |
1051 case GE_EXPR: | |
1052 case NE_EXPR: | |
1053 case LT_EXPR: | |
1054 case LE_EXPR: | |
1055 case EQ_EXPR: | |
1056 break; | |
1057 | |
1058 default: | |
1059 return false; | |
1060 } | |
1061 | |
1062 op0 = gimple_cond_lhs (stmt); | |
1063 op1 = gimple_cond_rhs (stmt); | |
1064 | |
1065 if (TREE_CODE (op0) != SSA_NAME || TREE_CODE (op1) != SSA_NAME) | |
1066 return false; | |
1067 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true)) | |
1068 return false; | |
1069 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true)) | |
1070 return false; | |
1071 if (TREE_CODE (iv0.step) != INTEGER_CST | |
1072 || TREE_CODE (iv1.step) != INTEGER_CST) | |
1073 return false; | |
1074 if ((integer_zerop (iv0.step) && integer_zerop (iv1.step)) | |
1075 || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step))) | |
1076 return false; | |
1077 | |
1078 if (integer_zerop (iv0.step)) | |
1079 { | |
1080 if (code != NE_EXPR && code != EQ_EXPR) | |
1081 code = invert_tree_comparison (code, false); | |
1082 bound = iv0.base; | |
1083 step = TREE_INT_CST_LOW (iv1.step); | |
1084 } | |
1085 else | |
1086 { | |
1087 bound = iv1.base; | |
1088 step = TREE_INT_CST_LOW (iv0.step); | |
1089 } | |
1090 | |
1091 bound = find_ssa_name_in_expr (bound); | |
1092 if (!bound) | |
1093 return false; | |
1094 | |
1095 *loop_invariant = bound; | |
1096 *compare_code = code; | |
1097 *loop_step = step; | |
1098 return true; | |
1099 } | |
1100 | |
1101 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 reference | |
1102 a similar variable. */ | |
davidxl
2012/01/31 01:25:42
Fix the comments. Returns true if T1 and T2 are va
| |
1103 | |
1104 static bool | |
1105 is_bound_expr_similar (tree t1, tree t2) | |
1106 { | |
davidxl
2012/01/31 01:25:42
May be changing the name to
expr_coherent_p (tre
| |
1107 gimple stmt; | |
1108 tree ssa_name_1 = NULL; | |
1109 tree ssa_name_2 = NULL; | |
1110 | |
1111 gcc_assert (TREE_CODE (t1) == SSA_NAME); | |
1112 gcc_assert (TREE_CODE (t2) == SSA_NAME); | |
1113 | |
1114 if (t1 == t2) | |
1115 return true; | |
1116 | |
1117 /* Check to see if t1 is expressed/defined with t2. */ | |
1118 stmt = SSA_NAME_DEF_STMT (t1); | |
1119 gcc_assert (stmt != NULL); | |
1120 if (is_gimple_assign (stmt)) | |
1121 { | |
1122 ssa_name_1 = find_ssa_name_in_assign_stmt (stmt); | |
1123 if (ssa_name_1 && ssa_name_1 == t2) | |
1124 return true; | |
1125 } | |
1126 | |
1127 /* Check to see if t2 is expressed/defined with t1. */ | |
1128 stmt = SSA_NAME_DEF_STMT (t2); | |
1129 gcc_assert (stmt != NULL); | |
1130 if (is_gimple_assign (stmt)) | |
1131 { | |
1132 ssa_name_2 = find_ssa_name_in_assign_stmt (stmt); | |
1133 if (ssa_name_2 && ssa_name_2 == t1) | |
1134 return true; | |
1135 } | |
1136 | |
1137 /* Compare if t1 and t2's def_stmts are identical. */ | |
1138 if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2) | |
1139 return true; | |
1140 else | |
1141 return false; | |
1142 } | |
1143 | |
1144 /* Predict branch probability of BB when BB contains a branch that compares | |
1145 an induction variable in LOOP to LOOP_BOUND_VAR. The loop exit is | |
1146 compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP. | |
1147 | |
1148 E.g. | |
1149 for (int i = 0; i < bound; i++) { | |
1150 if (i < bound - 2) | |
1151 computation_1(); | |
1152 else | |
1153 computation_2(); | |
1154 } | |
1155 | |
1156 In this loop, we will predict the branch inside the loop to be taken. */ | |
1157 | |
1158 static void | |
1159 predict_iv_comparison (struct loop *loop, basic_block bb, | |
1160 tree loop_bound_var, | |
1161 enum tree_code loop_bound_code, | |
1162 int loop_bound_step) | |
1163 { | |
1164 gimple stmt; | |
1165 tree compare_var; | |
1166 enum tree_code compare_code; | |
1167 int compare_step; | |
1168 edge then_edge; | |
1169 edge_iterator ei; | |
1170 | |
1171 if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED) | |
1172 || predicted_by_p (bb, PRED_LOOP_ITERATIONS) | |
1173 || predicted_by_p (bb, PRED_LOOP_EXIT)) | |
1174 return; | |
1175 | |
1176 stmt = last_stmt (bb); | |
1177 if (!stmt || gimple_code (stmt) != GIMPLE_COND) | |
1178 return; | |
1179 if (!is_comparison_with_loop_invariant_p (stmt, loop, &compare_var, | |
1180 &compare_code, | |
1181 &compare_step)) | |
1182 return; | |
1183 | |
1184 /* Find the taken edge. */ | |
1185 FOR_EACH_EDGE (then_edge, ei, bb->succs) | |
1186 if (then_edge->flags & EDGE_TRUE_VALUE) | |
1187 break; | |
1188 | |
1189 /* When comparing an IV to a loop invariant, NE is more likely to be | |
1190 taken while EQ is more likely to be not-taken. */ | |
1191 if (compare_code == NE_EXPR) | |
1192 { | |
1193 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); | |
1194 return; | |
1195 } | |
1196 else if (compare_code == EQ_EXPR) | |
1197 { | |
1198 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); | |
1199 return; | |
1200 } | |
1201 | |
1202 if (!is_bound_expr_similar (loop_bound_var, compare_var)) | |
1203 return; | |
1204 | |
1205 if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR) | |
1206 && (compare_code == LT_EXPR || compare_code == LE_EXPR)) | |
davidxl
2012/01/31 01:25:42
Fix indentation.
| |
1207 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); | |
1208 else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR) | |
1209 && (compare_code == GT_EXPR || compare_code == GE_EXPR)) | |
1210 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); | |
1211 else if (loop_bound_code == NE_EXPR) | |
1212 { | |
1213 /* If the loop backedge condition is "(i != bound)", we do | |
1214 the comparison based on the step of IV: | |
1215 * step < 0 : backedge condition is like (i > bound) | |
1216 * step > 0 : backedge condition is like (i < bound) */ | |
1217 gcc_assert (loop_bound_step != 0); | |
1218 if (loop_bound_step > 0 | |
1219 && (compare_code == LT_EXPR | |
1220 || compare_code == LE_EXPR)) | |
1221 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); | |
1222 else if (loop_bound_step < 0 | |
1223 && (compare_code == GT_EXPR | |
1224 || compare_code == GE_EXPR)) | |
1225 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); | |
1226 else | |
1227 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); | |
1228 } | |
1229 else | |
1230 /* The branch is predicted not-taken if loop_bound_code is | |
1231 opposite with compare_code. */ | |
1232 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); | |
1233 } | |
1234 · | |
949 /* Predict edge probabilities by exploiting loop structure. */ | 1235 /* Predict edge probabilities by exploiting loop structure. */ |
950 | 1236 |
951 static void | 1237 static void |
952 predict_loops (void) | 1238 predict_loops (void) |
953 { | 1239 { |
954 loop_iterator li; | 1240 loop_iterator li; |
955 struct loop *loop; | 1241 struct loop *loop; |
956 | 1242 |
957 /* Try to predict out blocks in a loop that are not part of a | 1243 /* Try to predict out blocks in a loop that are not part of a |
958 natural loop. */ | 1244 natural loop. */ |
959 FOR_EACH_LOOP (li, loop, 0) | 1245 FOR_EACH_LOOP (li, loop, 0) |
960 { | 1246 { |
961 basic_block bb, *bbs; | 1247 basic_block bb, *bbs; |
962 unsigned j, n_exits; | 1248 unsigned j, n_exits; |
963 VEC (edge, heap) *exits; | 1249 VEC (edge, heap) *exits; |
964 struct tree_niter_desc niter_desc; | 1250 struct tree_niter_desc niter_desc; |
965 edge ex; | 1251 edge ex; |
1252 struct nb_iter_bound *nb_iter; | |
1253 enum tree_code loop_bound_code = ERROR_MARK; | |
1254 int loop_bound_step = 0; | |
1255 tree loop_bound_var = NULL; | |
1256 gimple stmt = NULL; | |
966 | 1257 |
967 exits = get_loop_exit_edges (loop); | 1258 exits = get_loop_exit_edges (loop); |
968 n_exits = VEC_length (edge, exits); | 1259 n_exits = VEC_length (edge, exits); |
969 | 1260 |
970 FOR_EACH_VEC_ELT (edge, exits, j, ex) | 1261 FOR_EACH_VEC_ELT (edge, exits, j, ex) |
971 { | 1262 { |
972 tree niter = NULL; | 1263 tree niter = NULL; |
973 HOST_WIDE_INT nitercst; | 1264 HOST_WIDE_INT nitercst; |
974 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS); | 1265 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS); |
975 int probability; | 1266 int probability; |
(...skipping 27 matching lines...) Expand all Loading... | |
1003 predictor = PRED_LOOP_ITERATIONS_GUESSED; | 1294 predictor = PRED_LOOP_ITERATIONS_GUESSED; |
1004 } | 1295 } |
1005 else | 1296 else |
1006 continue; | 1297 continue; |
1007 | 1298 |
1008 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst); | 1299 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst); |
1009 predict_edge (ex, predictor, probability); | 1300 predict_edge (ex, predictor, probability); |
1010 } | 1301 } |
1011 VEC_free (edge, heap, exits); | 1302 VEC_free (edge, heap, exits); |
1012 | 1303 |
1304 /* Find information about loop bound variables. */ | |
1305 for (nb_iter = loop->bounds; nb_iter; | |
1306 nb_iter = nb_iter->next) | |
1307 if (nb_iter->stmt | |
1308 && gimple_code (nb_iter->stmt) == GIMPLE_COND) | |
1309 { | |
1310 stmt = nb_iter->stmt; | |
1311 break; | |
1312 } | |
1313 if (!stmt && last_stmt (loop->header) | |
1314 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND) | |
1315 stmt = last_stmt (loop->header); | |
1316 if (stmt) | |
1317 is_comparison_with_loop_invariant_p (stmt, loop, | |
1318 &loop_bound_var, | |
1319 &loop_bound_code, | |
1320 &loop_bound_step); | |
1321 | |
1013 bbs = get_loop_body (loop); | 1322 bbs = get_loop_body (loop); |
1014 | 1323 |
1015 for (j = 0; j < loop->num_nodes; j++) | 1324 for (j = 0; j < loop->num_nodes; j++) |
1016 { | 1325 { |
1017 int header_found = 0; | 1326 int header_found = 0; |
1018 edge e; | 1327 edge e; |
1019 edge_iterator ei; | 1328 edge_iterator ei; |
1020 | 1329 |
1021 bb = bbs[j]; | 1330 bb = bbs[j]; |
1022 | 1331 |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1064 int probability = ((REG_BR_PROB_BASE | 1373 int probability = ((REG_BR_PROB_BASE |
1065 - predictor_info [(int) PRED_LOOP_EXIT].hitrat e) | 1374 - predictor_info [(int) PRED_LOOP_EXIT].hitrat e) |
1066 / n_exits); | 1375 / n_exits); |
1067 if (probability < HITRATE (2)) | 1376 if (probability < HITRATE (2)) |
1068 probability = HITRATE (2); | 1377 probability = HITRATE (2); |
1069 FOR_EACH_EDGE (e, ei, bb->succs) | 1378 FOR_EACH_EDGE (e, ei, bb->succs) |
1070 if (e->dest->index < NUM_FIXED_BLOCKS | 1379 if (e->dest->index < NUM_FIXED_BLOCKS |
1071 || !flow_bb_inside_loop_p (loop, e->dest)) | 1380 || !flow_bb_inside_loop_p (loop, e->dest)) |
1072 predict_edge (e, PRED_LOOP_EXIT, probability); | 1381 predict_edge (e, PRED_LOOP_EXIT, probability); |
1073 } | 1382 } |
1383 if (loop_bound_var) | |
1384 predict_iv_comparison (loop, bb, loop_bound_var, | |
1385 loop_bound_code, | |
1386 loop_bound_step); | |
1074 } | 1387 } |
1075 | 1388 |
1076 /* Free basic blocks from get_loop_body. */ | 1389 /* Free basic blocks from get_loop_body. */ |
1077 free (bbs); | 1390 free (bbs); |
1078 } | 1391 } |
1079 } | 1392 } |
1080 | 1393 |
1081 /* Attempt to predict probabilities of BB outgoing edges using local | 1394 /* Attempt to predict probabilities of BB outgoing edges using local |
1082 properties. */ | 1395 properties. */ |
1083 static void | 1396 static void |
(...skipping 1299 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
2383 estimate_bb_frequencies (); | 2696 estimate_bb_frequencies (); |
2384 remove_fake_exit_edges (); | 2697 remove_fake_exit_edges (); |
2385 loop_optimizer_finalize (); | 2698 loop_optimizer_finalize (); |
2386 } | 2699 } |
2387 else if (profile_status == PROFILE_READ) | 2700 else if (profile_status == PROFILE_READ) |
2388 counts_to_freqs (); | 2701 counts_to_freqs (); |
2389 else | 2702 else |
2390 gcc_unreachable (); | 2703 gcc_unreachable (); |
2391 timevar_pop (TV_REBUILD_FREQUENCIES); | 2704 timevar_pop (TV_REBUILD_FREQUENCIES); |
2392 } | 2705 } |
OLD | NEW |