Mercurial > hg > CbC > CbC_gcc
annotate gcc/ddg.c @ 158:494b0b89df80 default tip
...
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 25 May 2020 18:13:55 +0900 |
| parents | 1830386684a0 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* DDG - Data Dependence Graph implementation. |
| 145 | 2 Copyright (C) 2004-2020 Free Software Foundation, Inc. |
| 0 | 3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com> |
| 4 | |
| 5 This file is part of GCC. | |
| 6 | |
| 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 | |
| 9 Software Foundation; either version 3, or (at your option) any later | |
| 10 version. | |
| 11 | |
| 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
| 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 15 for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 | |
| 22 #include "config.h" | |
| 23 #include "system.h" | |
| 24 #include "coretypes.h" | |
| 111 | 25 #include "backend.h" |
| 0 | 26 #include "rtl.h" |
| 111 | 27 #include "df.h" |
| 0 | 28 #include "insn-attr.h" |
| 29 #include "sched-int.h" | |
| 30 #include "ddg.h" | |
| 111 | 31 #include "rtl-iter.h" |
| 0 | 32 |
| 33 #ifdef INSN_SCHEDULING | |
| 34 | |
| 35 /* Forward declarations. */ | |
| 36 static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr); | |
| 37 static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr); | |
| 38 static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr); | |
| 39 static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr, | |
| 40 ddg_node_ptr, dep_t); | |
| 41 static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr, | |
| 42 dep_type, dep_data_type, int); | |
| 43 static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type, | |
| 44 dep_data_type, int, int); | |
| 45 static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr); | |
| 46 | |
| 47 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */ | |
| 48 static bool mem_ref_p; | |
| 49 | |
| 50 /* Auxiliary function for mem_read_insn_p. */ | |
| 111 | 51 static void |
| 52 mark_mem_use (rtx *x, void *) | |
| 0 | 53 { |
| 111 | 54 subrtx_iterator::array_type array; |
| 55 FOR_EACH_SUBRTX (iter, array, *x, NONCONST) | |
| 56 if (MEM_P (*iter)) | |
| 57 { | |
| 58 mem_ref_p = true; | |
| 59 break; | |
| 60 } | |
| 0 | 61 } |
| 62 | |
| 63 /* Returns nonzero if INSN reads from memory. */ | |
| 64 static bool | |
| 111 | 65 mem_read_insn_p (rtx_insn *insn) |
| 0 | 66 { |
| 67 mem_ref_p = false; | |
| 111 | 68 note_uses (&PATTERN (insn), mark_mem_use, NULL); |
| 0 | 69 return mem_ref_p; |
| 70 } | |
| 71 | |
| 72 static void | |
| 73 mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) | |
| 74 { | |
| 75 if (MEM_P (loc)) | |
| 76 mem_ref_p = true; | |
| 77 } | |
| 78 | |
| 79 /* Returns nonzero if INSN writes to memory. */ | |
| 80 static bool | |
| 111 | 81 mem_write_insn_p (rtx_insn *insn) |
| 0 | 82 { |
| 83 mem_ref_p = false; | |
| 145 | 84 note_stores (insn, mark_mem_store, NULL); |
| 0 | 85 return mem_ref_p; |
| 86 } | |
| 87 | |
| 88 /* Returns nonzero if X has access to memory. */ | |
| 89 static bool | |
| 90 rtx_mem_access_p (rtx x) | |
| 91 { | |
| 92 int i, j; | |
| 93 const char *fmt; | |
| 94 enum rtx_code code; | |
| 95 | |
| 96 if (x == 0) | |
| 97 return false; | |
| 98 | |
| 99 if (MEM_P (x)) | |
| 100 return true; | |
| 101 | |
| 102 code = GET_CODE (x); | |
| 103 fmt = GET_RTX_FORMAT (code); | |
| 104 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
| 105 { | |
| 106 if (fmt[i] == 'e') | |
| 107 { | |
| 108 if (rtx_mem_access_p (XEXP (x, i))) | |
| 109 return true; | |
| 110 } | |
| 111 else if (fmt[i] == 'E') | |
| 112 for (j = 0; j < XVECLEN (x, i); j++) | |
| 113 { | |
| 114 if (rtx_mem_access_p (XVECEXP (x, i, j))) | |
| 115 return true; | |
| 116 } | |
| 117 } | |
| 118 return false; | |
| 119 } | |
| 120 | |
| 121 /* Returns nonzero if INSN reads to or writes from memory. */ | |
| 122 static bool | |
| 111 | 123 mem_access_insn_p (rtx_insn *insn) |
| 0 | 124 { |
| 125 return rtx_mem_access_p (PATTERN (insn)); | |
| 126 } | |
| 127 | |
| 111 | 128 /* Return true if DEF_INSN contains address being auto-inc or auto-dec |
| 129 which is used in USE_INSN. Otherwise return false. The result is | |
| 130 being used to decide whether to remove the edge between def_insn and | |
| 131 use_insn when -fmodulo-sched-allow-regmoves is set. This function | |
| 132 doesn't need to consider the specific address register; no reg_moves | |
| 133 will be allowed for any life range defined by def_insn and used | |
| 134 by use_insn, if use_insn uses an address register auto-inc'ed by | |
| 135 def_insn. */ | |
| 136 bool | |
| 137 autoinc_var_is_used_p (rtx_insn *def_insn, rtx_insn *use_insn) | |
| 138 { | |
| 139 rtx note; | |
| 140 | |
| 141 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1)) | |
| 142 if (REG_NOTE_KIND (note) == REG_INC | |
| 143 && reg_referenced_p (XEXP (note, 0), PATTERN (use_insn))) | |
| 144 return true; | |
| 145 | |
| 146 return false; | |
| 147 } | |
| 148 | |
| 149 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise | |
| 150 return false. */ | |
| 151 static bool | |
| 152 def_has_ccmode_p (rtx_insn *insn) | |
| 153 { | |
| 154 df_ref def; | |
| 155 | |
| 156 FOR_EACH_INSN_DEF (def, insn) | |
| 157 { | |
| 158 machine_mode mode = GET_MODE (DF_REF_REG (def)); | |
| 159 | |
| 160 if (GET_MODE_CLASS (mode) == MODE_CC) | |
| 161 return true; | |
| 162 } | |
| 163 | |
| 164 return false; | |
| 165 } | |
| 166 | |
| 0 | 167 /* Computes the dependence parameters (latency, distance etc.), creates |
| 168 a ddg_edge and adds it to the given DDG. */ | |
| 169 static void | |
| 170 create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node, | |
| 171 ddg_node_ptr dest_node, dep_t link) | |
| 172 { | |
| 173 ddg_edge_ptr e; | |
| 174 int latency, distance = 0; | |
| 175 dep_type t = TRUE_DEP; | |
| 176 dep_data_type dt = (mem_access_insn_p (src_node->insn) | |
| 177 && mem_access_insn_p (dest_node->insn) ? MEM_DEP | |
| 178 : REG_DEP); | |
| 179 gcc_assert (src_node->cuid < dest_node->cuid); | |
| 180 gcc_assert (link); | |
| 181 | |
| 182 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */ | |
| 183 if (DEP_TYPE (link) == REG_DEP_ANTI) | |
| 184 t = ANTI_DEP; | |
| 185 else if (DEP_TYPE (link) == REG_DEP_OUTPUT) | |
| 186 t = OUTPUT_DEP; | |
| 187 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
188 gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
189 gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
190 |
| 0 | 191 /* We currently choose not to create certain anti-deps edges and |
| 192 compensate for that by generating reg-moves based on the life-range | |
| 193 analysis. The anti-deps that will be deleted are the ones which | |
| 194 have true-deps edges in the opposite direction (in other words | |
| 111 | 195 the kernel has only one def of the relevant register). |
| 196 If the address that is being auto-inc or auto-dec in DEST_NODE | |
| 197 is used in SRC_NODE then do not remove the edge to make sure | |
| 198 reg-moves will not be created for this address. | |
| 199 TODO: support the removal of all anti-deps edges, i.e. including those | |
| 0 | 200 whose register has multiple defs in the loop. */ |
| 111 | 201 if (flag_modulo_sched_allow_regmoves |
| 202 && (t == ANTI_DEP && dt == REG_DEP) | |
| 203 && !def_has_ccmode_p (dest_node->insn) | |
| 204 && !autoinc_var_is_used_p (dest_node->insn, src_node->insn)) | |
| 0 | 205 { |
| 206 rtx set; | |
| 207 | |
| 208 set = single_set (dest_node->insn); | |
| 209 /* TODO: Handle registers that REG_P is not true for them, i.e. | |
| 210 subregs and special registers. */ | |
| 211 if (set && REG_P (SET_DEST (set))) | |
| 212 { | |
| 213 int regno = REGNO (SET_DEST (set)); | |
| 214 df_ref first_def; | |
| 145 | 215 class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); |
| 0 | 216 |
| 217 first_def = df_bb_regno_first_def_find (g->bb, regno); | |
| 218 gcc_assert (first_def); | |
| 219 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
220 if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))) |
| 0 | 221 return; |
| 222 } | |
| 223 } | |
| 224 | |
| 225 latency = dep_cost (link); | |
| 226 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance); | |
| 227 add_edge_to_ddg (g, e); | |
| 228 } | |
| 229 | |
| 230 /* The same as the above function, but it doesn't require a link parameter. */ | |
| 231 static void | |
| 232 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, | |
| 233 dep_type d_t, dep_data_type d_dt, int distance) | |
| 234 { | |
| 235 ddg_edge_ptr e; | |
| 236 int l; | |
| 237 enum reg_note dep_kind; | |
| 238 struct _dep _dep, *dep = &_dep; | |
| 239 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
240 gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
241 gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
242 |
| 0 | 243 if (d_t == ANTI_DEP) |
| 244 dep_kind = REG_DEP_ANTI; | |
| 245 else if (d_t == OUTPUT_DEP) | |
| 246 dep_kind = REG_DEP_OUTPUT; | |
| 247 else | |
| 248 { | |
| 249 gcc_assert (d_t == TRUE_DEP); | |
| 250 | |
| 251 dep_kind = REG_DEP_TRUE; | |
| 252 } | |
| 253 | |
| 254 init_dep (dep, from->insn, to->insn, dep_kind); | |
| 255 | |
| 256 l = dep_cost (dep); | |
| 257 | |
| 258 e = create_ddg_edge (from, to, d_t, d_dt, l, distance); | |
| 259 if (distance > 0) | |
| 260 add_backarc_to_ddg (g, e); | |
| 261 else | |
| 262 add_edge_to_ddg (g, e); | |
| 263 } | |
| 264 | |
| 265 | |
| 266 /* Given a downwards exposed register def LAST_DEF (which is the last | |
| 267 definition of that register in the bb), add inter-loop true dependences | |
| 268 to all its uses in the next iteration, an output dependence to the | |
| 269 first def of the same register (possibly itself) in the next iteration | |
| 270 and anti-dependences from its uses in the current iteration to the | |
| 271 first definition in the next iteration. */ | |
| 272 static void | |
| 273 add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def) | |
| 274 { | |
| 275 int regno = DF_REF_REGNO (last_def); | |
| 276 struct df_link *r_use; | |
| 277 int has_use_in_bb_p = false; | |
| 111 | 278 rtx_insn *def_insn = DF_REF_INSN (last_def); |
| 0 | 279 ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn); |
| 280 ddg_node_ptr use_node; | |
| 281 df_ref first_def = df_bb_regno_first_def_find (g->bb, regno); | |
| 282 | |
| 283 gcc_assert (last_def_node); | |
| 284 gcc_assert (first_def); | |
| 285 | |
| 111 | 286 if (flag_checking && DF_REF_ID (last_def) != DF_REF_ID (first_def)) |
| 287 { | |
| 145 | 288 class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb); |
| 111 | 289 gcc_assert (!bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def))); |
| 290 } | |
| 0 | 291 |
| 292 /* Create inter-loop true dependences and anti dependences. */ | |
| 293 for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next) | |
| 294 { | |
| 131 | 295 if (DF_REF_BB (r_use->ref) != g->bb) |
| 296 continue; | |
| 0 | 297 |
| 131 | 298 gcc_assert (!DF_REF_IS_ARTIFICIAL (r_use->ref) |
| 299 && DF_REF_INSN_INFO (r_use->ref) != NULL); | |
| 300 | |
| 301 rtx_insn *use_insn = DF_REF_INSN (r_use->ref); | |
| 0 | 302 |
| 303 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */ | |
| 304 use_node = get_node_of_insn (g, use_insn); | |
| 305 gcc_assert (use_node); | |
| 306 has_use_in_bb_p = true; | |
| 307 if (use_node->cuid <= last_def_node->cuid) | |
| 308 { | |
| 309 /* Add true deps from last_def to it's uses in the next | |
| 310 iteration. Any such upwards exposed use appears before | |
| 311 the last_def def. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
312 create_ddg_dep_no_link (g, last_def_node, use_node, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
313 DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP, |
| 0 | 314 REG_DEP, 1); |
| 315 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
316 else if (!DEBUG_INSN_P (use_insn)) |
| 0 | 317 { |
| 318 /* Add anti deps from last_def's uses in the current iteration | |
| 319 to the first def in the next iteration. We do not add ANTI | |
| 320 dep when there is an intra-loop TRUE dep in the opposite | |
| 321 direction, but use regmoves to fix such disregarded ANTI | |
| 322 deps when broken. If the first_def reaches the USE then | |
| 323 there is such a dep. */ | |
| 324 ddg_node_ptr first_def_node = get_node_of_insn (g, | |
| 325 DF_REF_INSN (first_def)); | |
| 326 | |
| 327 gcc_assert (first_def_node); | |
| 328 | |
| 111 | 329 /* Always create the edge if the use node is a branch in |
| 330 order to prevent the creation of reg-moves. | |
| 331 If the address that is being auto-inc or auto-dec in LAST_DEF | |
| 332 is used in USE_INSN then do not remove the edge to make sure | |
| 333 reg-moves will not be created for that address. */ | |
| 0 | 334 if (DF_REF_ID (last_def) != DF_REF_ID (first_def) |
| 111 | 335 || !flag_modulo_sched_allow_regmoves |
| 336 || JUMP_P (use_node->insn) | |
| 337 || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn) | |
| 338 || def_has_ccmode_p (DF_REF_INSN (last_def))) | |
| 0 | 339 create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP, |
| 340 REG_DEP, 1); | |
| 341 | |
| 342 } | |
| 343 } | |
| 344 /* Create an inter-loop output dependence between LAST_DEF (which is the | |
| 345 last def in its block, being downwards exposed) and the first def in | |
| 346 its block. Avoid creating a self output dependence. Avoid creating | |
| 347 an output dependence if there is a dependence path between the two | |
| 348 defs starting with a true dependence to a use which can be in the | |
| 349 next iteration; followed by an anti dependence of that use to the | |
| 350 first def (i.e. if there is a use between the two defs.) */ | |
| 351 if (!has_use_in_bb_p) | |
| 352 { | |
| 353 ddg_node_ptr dest_node; | |
| 354 | |
| 355 if (DF_REF_ID (last_def) == DF_REF_ID (first_def)) | |
| 356 return; | |
| 357 | |
| 358 dest_node = get_node_of_insn (g, DF_REF_INSN (first_def)); | |
| 359 gcc_assert (dest_node); | |
| 360 create_ddg_dep_no_link (g, last_def_node, dest_node, | |
| 361 OUTPUT_DEP, REG_DEP, 1); | |
| 362 } | |
| 363 } | |
| 364 /* Build inter-loop dependencies, by looking at DF analysis backwards. */ | |
| 365 static void | |
| 366 build_inter_loop_deps (ddg_ptr g) | |
| 367 { | |
| 368 unsigned rd_num; | |
| 145 | 369 class df_rd_bb_info *rd_bb_info; |
| 0 | 370 bitmap_iterator bi; |
| 371 | |
| 372 rd_bb_info = DF_RD_BB_INFO (g->bb); | |
| 373 | |
| 374 /* Find inter-loop register output, true and anti deps. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
375 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi) |
| 0 | 376 { |
| 377 df_ref rd = DF_DEFS_GET (rd_num); | |
| 378 | |
| 379 add_cross_iteration_register_deps (g, rd); | |
| 380 } | |
| 381 } | |
| 382 | |
| 383 | |
| 111 | 384 /* Return true if two specified instructions have mem expr with conflict |
| 385 alias sets. */ | |
| 386 static bool | |
| 387 insns_may_alias_p (rtx_insn *insn1, rtx_insn *insn2) | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
388 { |
| 111 | 389 subrtx_iterator::array_type array1; |
| 390 subrtx_iterator::array_type array2; | |
| 391 FOR_EACH_SUBRTX (iter1, array1, PATTERN (insn1), NONCONST) | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
392 { |
| 111 | 393 const_rtx x1 = *iter1; |
| 394 if (MEM_P (x1)) | |
| 395 FOR_EACH_SUBRTX (iter2, array2, PATTERN (insn2), NONCONST) | |
| 396 { | |
| 397 const_rtx x2 = *iter2; | |
| 398 if (MEM_P (x2) && may_alias_p (x2, x1)) | |
| 399 return true; | |
| 400 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
401 } |
| 111 | 402 return false; |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
403 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
404 |
| 111 | 405 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps |
| 406 to ddg G. */ | |
| 407 static void | |
| 408 add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
409 { |
| 111 | 410 |
| 411 if ((from->cuid == to->cuid) | |
| 412 || !insns_may_alias_p (from->insn, to->insn)) | |
| 413 /* Do not create edge if memory references have disjoint alias sets | |
| 414 or 'to' and 'from' are the same instruction. */ | |
| 415 return; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
416 |
| 111 | 417 if (mem_write_insn_p (from->insn)) |
| 418 { | |
| 419 if (mem_read_insn_p (to->insn)) | |
| 420 create_ddg_dep_no_link (g, from, to, | |
| 421 DEBUG_INSN_P (to->insn) | |
| 422 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 0); | |
| 423 else | |
| 424 create_ddg_dep_no_link (g, from, to, | |
| 425 DEBUG_INSN_P (to->insn) | |
| 426 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 0); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
427 } |
| 111 | 428 else if (!mem_read_insn_p (to->insn)) |
| 429 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
430 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
431 |
| 0 | 432 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps |
| 433 to ddg G. */ | |
| 434 static void | |
| 435 add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) | |
| 436 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
437 if (!insns_may_alias_p (from->insn, to->insn)) |
| 0 | 438 /* Do not create edge if memory references have disjoint alias sets. */ |
| 439 return; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
440 |
| 0 | 441 if (mem_write_insn_p (from->insn)) |
| 442 { | |
| 443 if (mem_read_insn_p (to->insn)) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
444 create_ddg_dep_no_link (g, from, to, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
445 DEBUG_INSN_P (to->insn) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
446 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1); |
| 0 | 447 else if (from->cuid != to->cuid) |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
448 create_ddg_dep_no_link (g, from, to, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
449 DEBUG_INSN_P (to->insn) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
450 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1); |
| 0 | 451 } |
| 452 else | |
| 453 { | |
| 454 if (mem_read_insn_p (to->insn)) | |
| 455 return; | |
| 456 else if (from->cuid != to->cuid) | |
| 457 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
458 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
459 if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
460 create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
461 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
462 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1); |
| 0 | 463 } |
| 464 } | |
| 465 | |
| 466 } | |
| 467 | |
| 468 /* Perform intra-block Data Dependency analysis and connect the nodes in | |
| 469 the DDG. We assume the loop has a single basic block. */ | |
| 470 static void | |
| 471 build_intra_loop_deps (ddg_ptr g) | |
| 472 { | |
| 473 int i; | |
| 474 /* Hold the dependency analysis state during dependency calculations. */ | |
| 145 | 475 class deps_desc tmp_deps; |
| 111 | 476 rtx_insn *head, *tail; |
| 0 | 477 |
| 478 /* Build the dependence information, using the sched_analyze function. */ | |
| 479 init_deps_global (); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
480 init_deps (&tmp_deps, false); |
| 0 | 481 |
| 482 /* Do the intra-block data dependence analysis for the given block. */ | |
| 483 get_ebb_head_tail (g->bb, g->bb, &head, &tail); | |
| 484 sched_analyze (&tmp_deps, head, tail); | |
| 485 | |
| 486 /* Build intra-loop data dependencies using the scheduler dependency | |
| 487 analysis. */ | |
| 488 for (i = 0; i < g->num_nodes; i++) | |
| 489 { | |
| 490 ddg_node_ptr dest_node = &g->nodes[i]; | |
| 491 sd_iterator_def sd_it; | |
| 492 dep_t dep; | |
| 493 | |
| 494 if (! INSN_P (dest_node->insn)) | |
| 495 continue; | |
| 496 | |
| 497 FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep) | |
| 498 { | |
| 111 | 499 rtx_insn *src_insn = DEP_PRO (dep); |
| 500 ddg_node_ptr src_node; | |
| 501 | |
| 502 /* Don't add dependencies on debug insns to non-debug insns | |
| 503 to avoid codegen differences between -g and -g0. */ | |
| 504 if (DEBUG_INSN_P (src_insn) && !DEBUG_INSN_P (dest_node->insn)) | |
| 505 continue; | |
| 506 | |
| 507 src_node = get_node_of_insn (g, src_insn); | |
| 0 | 508 |
| 509 if (!src_node) | |
| 510 continue; | |
| 511 | |
| 512 create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep); | |
| 513 } | |
| 514 | |
| 515 /* If this insn modifies memory, add an edge to all insns that access | |
| 516 memory. */ | |
| 517 if (mem_access_insn_p (dest_node->insn)) | |
| 518 { | |
| 519 int j; | |
| 520 | |
| 521 for (j = 0; j <= i; j++) | |
| 522 { | |
| 523 ddg_node_ptr j_node = &g->nodes[j]; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
524 if (DEBUG_INSN_P (j_node->insn)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
525 continue; |
| 0 | 526 if (mem_access_insn_p (j_node->insn)) |
| 111 | 527 { |
| 528 /* Don't bother calculating inter-loop dep if an intra-loop dep | |
| 529 already exists. */ | |
| 530 if (! bitmap_bit_p (dest_node->successors, j)) | |
| 0 | 531 add_inter_loop_mem_dep (g, dest_node, j_node); |
| 111 | 532 /* If -fmodulo-sched-allow-regmoves |
| 533 is set certain anti-dep edges are not created. | |
| 534 It might be that these anti-dep edges are on the | |
| 535 path from one memory instruction to another such that | |
| 536 removing these edges could cause a violation of the | |
| 537 memory dependencies. Thus we add intra edges between | |
| 538 every two memory instructions in this case. */ | |
| 539 if (flag_modulo_sched_allow_regmoves | |
| 540 && !bitmap_bit_p (dest_node->predecessors, j)) | |
| 541 add_intra_loop_mem_dep (g, j_node, dest_node); | |
| 542 } | |
| 0 | 543 } |
| 544 } | |
| 545 } | |
| 546 | |
| 547 /* Free the INSN_LISTs. */ | |
| 548 finish_deps_global (); | |
| 549 free_deps (&tmp_deps); | |
| 550 | |
| 551 /* Free dependencies. */ | |
| 552 sched_free_deps (head, tail, false); | |
| 553 } | |
| 554 | |
| 555 | |
| 556 /* Given a basic block, create its DDG and return a pointer to a variable | |
| 557 of ddg type that represents it. | |
| 558 Initialize the ddg structure fields to the appropriate values. */ | |
| 559 ddg_ptr | |
| 560 create_ddg (basic_block bb, int closing_branch_deps) | |
| 561 { | |
| 562 ddg_ptr g; | |
| 111 | 563 rtx_insn *insn, *first_note; |
| 145 | 564 int i, j; |
| 0 | 565 int num_nodes = 0; |
| 566 | |
| 567 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg)); | |
| 568 | |
| 569 g->bb = bb; | |
| 570 g->closing_branch_deps = closing_branch_deps; | |
| 571 | |
| 572 /* Count the number of insns in the BB. */ | |
| 573 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); | |
| 574 insn = NEXT_INSN (insn)) | |
| 575 { | |
| 576 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE) | |
| 577 continue; | |
| 578 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
579 if (DEBUG_INSN_P (insn)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
580 g->num_debug++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
581 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
582 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
583 if (mem_read_insn_p (insn)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
584 g->num_loads++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
585 if (mem_write_insn_p (insn)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
586 g->num_stores++; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
587 } |
| 0 | 588 num_nodes++; |
| 589 } | |
| 590 | |
| 591 /* There is nothing to do for this BB. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
592 if ((num_nodes - g->num_debug) <= 1) |
| 0 | 593 { |
| 594 free (g); | |
| 595 return NULL; | |
| 596 } | |
| 597 | |
| 598 /* Allocate the nodes array, and initialize the nodes. */ | |
| 599 g->num_nodes = num_nodes; | |
| 600 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node)); | |
| 601 g->closing_branch = NULL; | |
| 602 i = 0; | |
| 111 | 603 first_note = NULL; |
| 0 | 604 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); |
| 605 insn = NEXT_INSN (insn)) | |
| 606 { | |
| 607 if (! INSN_P (insn)) | |
| 608 { | |
| 609 if (! first_note && NOTE_P (insn) | |
| 610 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK) | |
| 611 first_note = insn; | |
| 612 continue; | |
| 613 } | |
| 614 if (JUMP_P (insn)) | |
| 615 { | |
| 616 gcc_assert (!g->closing_branch); | |
| 617 g->closing_branch = &g->nodes[i]; | |
| 618 } | |
| 619 else if (GET_CODE (PATTERN (insn)) == USE) | |
| 620 { | |
| 621 if (! first_note) | |
| 622 first_note = insn; | |
| 623 continue; | |
| 624 } | |
| 625 | |
| 626 g->nodes[i].cuid = i; | |
| 627 g->nodes[i].successors = sbitmap_alloc (num_nodes); | |
| 111 | 628 bitmap_clear (g->nodes[i].successors); |
| 0 | 629 g->nodes[i].predecessors = sbitmap_alloc (num_nodes); |
| 111 | 630 bitmap_clear (g->nodes[i].predecessors); |
| 0 | 631 g->nodes[i].first_note = (first_note ? first_note : insn); |
| 145 | 632 |
| 633 g->nodes[i].aux.count = -1; | |
| 634 g->nodes[i].max_dist = XCNEWVEC (int, num_nodes); | |
| 635 for (j = 0; j < num_nodes; j++) | |
| 636 g->nodes[i].max_dist[j] = -1; | |
| 637 | |
| 0 | 638 g->nodes[i++].insn = insn; |
| 111 | 639 first_note = NULL; |
| 0 | 640 } |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
641 |
| 0 | 642 /* We must have found a branch in DDG. */ |
| 643 gcc_assert (g->closing_branch); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
644 |
| 0 | 645 |
| 646 /* Build the data dependency graph. */ | |
| 647 build_intra_loop_deps (g); | |
| 648 build_inter_loop_deps (g); | |
| 649 return g; | |
| 650 } | |
| 651 | |
| 652 /* Free all the memory allocated for the DDG. */ | |
| 653 void | |
| 654 free_ddg (ddg_ptr g) | |
| 655 { | |
| 656 int i; | |
| 657 | |
| 658 if (!g) | |
| 659 return; | |
| 660 | |
| 661 for (i = 0; i < g->num_nodes; i++) | |
| 662 { | |
| 663 ddg_edge_ptr e = g->nodes[i].out; | |
| 664 | |
| 665 while (e) | |
| 666 { | |
| 667 ddg_edge_ptr next = e->next_out; | |
| 668 | |
| 669 free (e); | |
| 670 e = next; | |
| 671 } | |
| 672 sbitmap_free (g->nodes[i].successors); | |
| 673 sbitmap_free (g->nodes[i].predecessors); | |
| 145 | 674 free (g->nodes[i].max_dist); |
| 0 | 675 } |
| 676 if (g->num_backarcs > 0) | |
| 677 free (g->backarcs); | |
| 678 free (g->nodes); | |
| 679 free (g); | |
| 680 } | |
| 681 | |
| 682 void | |
| 683 print_ddg_edge (FILE *file, ddg_edge_ptr e) | |
| 684 { | |
| 685 char dep_c; | |
| 686 | |
| 687 switch (e->type) | |
| 688 { | |
| 689 case OUTPUT_DEP : | |
| 690 dep_c = 'O'; | |
| 691 break; | |
| 692 case ANTI_DEP : | |
| 693 dep_c = 'A'; | |
| 694 break; | |
| 695 default: | |
| 696 dep_c = 'T'; | |
| 697 } | |
| 698 | |
| 699 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), | |
| 700 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn)); | |
| 701 } | |
| 702 | |
| 703 /* Print the DDG nodes with there in/out edges to the dump file. */ | |
| 704 void | |
| 705 print_ddg (FILE *file, ddg_ptr g) | |
| 706 { | |
| 707 int i; | |
| 708 | |
| 709 for (i = 0; i < g->num_nodes; i++) | |
| 710 { | |
| 711 ddg_edge_ptr e; | |
| 712 | |
| 713 fprintf (file, "Node num: %d\n", g->nodes[i].cuid); | |
| 714 print_rtl_single (file, g->nodes[i].insn); | |
| 715 fprintf (file, "OUT ARCS: "); | |
| 716 for (e = g->nodes[i].out; e; e = e->next_out) | |
| 717 print_ddg_edge (file, e); | |
| 718 | |
| 719 fprintf (file, "\nIN ARCS: "); | |
| 720 for (e = g->nodes[i].in; e; e = e->next_in) | |
| 721 print_ddg_edge (file, e); | |
| 722 | |
| 723 fprintf (file, "\n"); | |
| 724 } | |
| 725 } | |
| 726 | |
| 727 /* Print the given DDG in VCG format. */ | |
| 111 | 728 DEBUG_FUNCTION void |
| 0 | 729 vcg_print_ddg (FILE *file, ddg_ptr g) |
| 730 { | |
| 731 int src_cuid; | |
| 732 | |
| 733 fprintf (file, "graph: {\n"); | |
| 734 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++) | |
| 735 { | |
| 736 ddg_edge_ptr e; | |
| 737 int src_uid = INSN_UID (g->nodes[src_cuid].insn); | |
| 738 | |
| 739 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid); | |
| 740 print_rtl_single (file, g->nodes[src_cuid].insn); | |
| 741 fprintf (file, "\"}\n"); | |
| 742 for (e = g->nodes[src_cuid].out; e; e = e->next_out) | |
| 743 { | |
| 744 int dst_uid = INSN_UID (e->dest->insn); | |
| 745 int dst_cuid = e->dest->cuid; | |
| 746 | |
| 747 /* Give the backarcs a different color. */ | |
| 748 if (e->distance > 0) | |
| 749 fprintf (file, "backedge: {color: red "); | |
| 750 else | |
| 751 fprintf (file, "edge: { "); | |
| 752 | |
| 753 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid); | |
| 754 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid); | |
| 755 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance); | |
| 756 } | |
| 757 } | |
| 758 fprintf (file, "}\n"); | |
| 759 } | |
| 760 | |
| 761 /* Dump the sccs in SCCS. */ | |
| 762 void | |
| 763 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g) | |
| 764 { | |
| 765 unsigned int u = 0; | |
| 766 sbitmap_iterator sbi; | |
| 767 int i; | |
| 768 | |
| 769 if (!file) | |
| 770 return; | |
| 771 | |
| 772 fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs); | |
| 773 for (i = 0; i < sccs->num_sccs; i++) | |
| 774 { | |
| 775 fprintf (file, "SCC number: %d\n", i); | |
| 111 | 776 EXECUTE_IF_SET_IN_BITMAP (sccs->sccs[i]->nodes, 0, u, sbi) |
| 0 | 777 { |
| 778 fprintf (file, "insn num %d\n", u); | |
| 779 print_rtl_single (file, g->nodes[u].insn); | |
| 780 } | |
| 781 } | |
| 782 fprintf (file, "\n"); | |
| 783 } | |
| 784 | |
| 785 /* Create an edge and initialize it with given values. */ | |
| 786 static ddg_edge_ptr | |
| 787 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, | |
| 788 dep_type t, dep_data_type dt, int l, int d) | |
| 789 { | |
| 790 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge)); | |
| 791 | |
| 792 e->src = src; | |
| 793 e->dest = dest; | |
| 794 e->type = t; | |
| 795 e->data_type = dt; | |
| 796 e->latency = l; | |
| 797 e->distance = d; | |
| 798 e->next_in = e->next_out = NULL; | |
| 145 | 799 e->in_scc = false; |
| 0 | 800 return e; |
| 801 } | |
| 802 | |
| 803 /* Add the given edge to the in/out linked lists of the DDG nodes. */ | |
| 804 static void | |
| 805 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e) | |
| 806 { | |
| 807 ddg_node_ptr src = e->src; | |
| 808 ddg_node_ptr dest = e->dest; | |
| 809 | |
| 810 /* Should have allocated the sbitmaps. */ | |
| 811 gcc_assert (src->successors && dest->predecessors); | |
| 812 | |
| 111 | 813 bitmap_set_bit (src->successors, dest->cuid); |
| 814 bitmap_set_bit (dest->predecessors, src->cuid); | |
| 0 | 815 e->next_in = dest->in; |
| 816 dest->in = e; | |
| 817 e->next_out = src->out; | |
| 818 src->out = e; | |
| 819 } | |
| 820 | |
| 821 | |
| 822 | |
| 823 /* Algorithm for computing the recurrence_length of an scc. We assume at | |
| 824 for now that cycles in the data dependence graph contain a single backarc. | |
| 825 This simplifies the algorithm, and can be generalized later. */ | |
| 826 static void | |
| 145 | 827 set_recurrence_length (ddg_scc_ptr scc) |
| 0 | 828 { |
| 829 int j; | |
| 830 int result = -1; | |
| 831 | |
| 832 for (j = 0; j < scc->num_backarcs; j++) | |
| 833 { | |
| 834 ddg_edge_ptr backarc = scc->backarcs[j]; | |
| 835 int distance = backarc->distance; | |
| 836 ddg_node_ptr src = backarc->dest; | |
| 837 ddg_node_ptr dest = backarc->src; | |
| 145 | 838 int length = src->max_dist[dest->cuid]; |
| 0 | 839 |
| 145 | 840 if (length < 0) |
| 841 continue; | |
| 842 | |
| 0 | 843 length += backarc->latency; |
| 844 result = MAX (result, (length / distance)); | |
| 845 } | |
| 846 scc->recurrence_length = result; | |
| 847 } | |
| 848 | |
| 849 /* Create a new SCC given the set of its nodes. Compute its recurrence_length | |
| 145 | 850 and mark edges that belong to this scc. */ |
| 0 | 851 static ddg_scc_ptr |
| 145 | 852 create_scc (ddg_ptr g, sbitmap nodes, int id) |
| 0 | 853 { |
| 854 ddg_scc_ptr scc; | |
| 855 unsigned int u = 0; | |
| 856 sbitmap_iterator sbi; | |
| 857 | |
| 858 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc)); | |
| 859 scc->backarcs = NULL; | |
| 860 scc->num_backarcs = 0; | |
| 861 scc->nodes = sbitmap_alloc (g->num_nodes); | |
| 111 | 862 bitmap_copy (scc->nodes, nodes); |
| 0 | 863 |
| 864 /* Mark the backarcs that belong to this SCC. */ | |
| 111 | 865 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi) |
| 0 | 866 { |
| 867 ddg_edge_ptr e; | |
| 868 ddg_node_ptr n = &g->nodes[u]; | |
| 869 | |
| 145 | 870 gcc_assert (n->aux.count == -1); |
| 871 n->aux.count = id; | |
| 872 | |
| 0 | 873 for (e = n->out; e; e = e->next_out) |
| 111 | 874 if (bitmap_bit_p (nodes, e->dest->cuid)) |
| 0 | 875 { |
| 145 | 876 e->in_scc = true; |
| 0 | 877 if (e->distance > 0) |
| 878 add_backarc_to_scc (scc, e); | |
| 879 } | |
| 880 } | |
| 881 | |
| 882 return scc; | |
| 883 } | |
| 884 | |
| 885 /* Cleans the memory allocation of a given SCC. */ | |
| 886 static void | |
| 887 free_scc (ddg_scc_ptr scc) | |
| 888 { | |
| 889 if (!scc) | |
| 890 return; | |
| 891 | |
| 892 sbitmap_free (scc->nodes); | |
| 893 if (scc->num_backarcs > 0) | |
| 894 free (scc->backarcs); | |
| 895 free (scc); | |
| 896 } | |
| 897 | |
| 898 | |
| 899 /* Add a given edge known to be a backarc to the given DDG. */ | |
| 900 static void | |
| 901 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e) | |
| 902 { | |
| 903 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr); | |
| 904 | |
| 905 add_edge_to_ddg (g, e); | |
| 906 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size); | |
| 907 g->backarcs[g->num_backarcs++] = e; | |
| 908 } | |
| 909 | |
| 910 /* Add backarc to an SCC. */ | |
| 911 static void | |
| 912 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e) | |
| 913 { | |
| 914 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr); | |
| 915 | |
| 916 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size); | |
| 917 scc->backarcs[scc->num_backarcs++] = e; | |
| 918 } | |
| 919 | |
| 920 /* Add the given SCC to the DDG. */ | |
| 921 static void | |
| 922 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc) | |
| 923 { | |
| 924 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr); | |
| 925 | |
| 926 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size); | |
| 927 g->sccs[g->num_sccs++] = scc; | |
| 928 } | |
| 929 | |
| 930 /* Given the instruction INSN return the node that represents it. */ | |
| 931 ddg_node_ptr | |
| 111 | 932 get_node_of_insn (ddg_ptr g, rtx_insn *insn) |
| 0 | 933 { |
| 934 int i; | |
| 935 | |
| 936 for (i = 0; i < g->num_nodes; i++) | |
| 937 if (insn == g->nodes[i].insn) | |
| 938 return &g->nodes[i]; | |
| 939 return NULL; | |
| 940 } | |
| 941 | |
| 942 /* Given a set OPS of nodes in the DDG, find the set of their successors | |
| 943 which are not in OPS, and set their bits in SUCC. Bits corresponding to | |
| 944 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */ | |
| 945 void | |
| 946 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops) | |
| 947 { | |
| 948 unsigned int i = 0; | |
| 949 sbitmap_iterator sbi; | |
| 950 | |
| 111 | 951 EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi) |
| 0 | 952 { |
| 953 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]); | |
| 111 | 954 bitmap_ior (succ, succ, node_succ); |
| 0 | 955 }; |
| 956 | |
| 957 /* We want those that are not in ops. */ | |
| 111 | 958 bitmap_and_compl (succ, succ, ops); |
| 0 | 959 } |
| 960 | |
| 961 /* Given a set OPS of nodes in the DDG, find the set of their predecessors | |
| 962 which are not in OPS, and set their bits in PREDS. Bits corresponding to | |
| 963 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */ | |
| 964 void | |
| 965 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops) | |
| 966 { | |
| 967 unsigned int i = 0; | |
| 968 sbitmap_iterator sbi; | |
| 969 | |
| 111 | 970 EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi) |
| 0 | 971 { |
| 972 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]); | |
| 111 | 973 bitmap_ior (preds, preds, node_preds); |
| 0 | 974 }; |
| 975 | |
| 976 /* We want those that are not in ops. */ | |
| 111 | 977 bitmap_and_compl (preds, preds, ops); |
| 0 | 978 } |
| 979 | |
| 980 | |
| 981 /* Compare function to be passed to qsort to order the backarcs in descending | |
| 982 recMII order. */ | |
| 983 static int | |
| 984 compare_sccs (const void *s1, const void *s2) | |
| 985 { | |
| 986 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
987 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length; |
| 0 | 988 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1)); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
989 |
| 0 | 990 } |
| 991 | |
| 992 /* Order the backarcs in descending recMII order using compare_sccs. */ | |
| 993 static void | |
| 994 order_sccs (ddg_all_sccs_ptr g) | |
| 995 { | |
| 996 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr), | |
| 997 (int (*) (const void *, const void *)) compare_sccs); | |
| 998 } | |
| 999 | |
| 1000 /* Check that every node in SCCS belongs to exactly one strongly connected | |
| 1001 component and that no element of SCCS is empty. */ | |
| 1002 static void | |
| 1003 check_sccs (ddg_all_sccs_ptr sccs, int num_nodes) | |
| 1004 { | |
| 1005 int i = 0; | |
| 111 | 1006 auto_sbitmap tmp (num_nodes); |
| 0 | 1007 |
| 111 | 1008 bitmap_clear (tmp); |
| 0 | 1009 for (i = 0; i < sccs->num_sccs; i++) |
| 1010 { | |
| 111 | 1011 gcc_assert (!bitmap_empty_p (sccs->sccs[i]->nodes)); |
| 0 | 1012 /* Verify that every node in sccs is in exactly one strongly |
| 1013 connected component. */ | |
| 111 | 1014 gcc_assert (!bitmap_intersect_p (tmp, sccs->sccs[i]->nodes)); |
| 1015 bitmap_ior (tmp, tmp, sccs->sccs[i]->nodes); | |
| 0 | 1016 } |
| 1017 } | |
| 1018 | |
| 1019 /* Perform the Strongly Connected Components decomposing algorithm on the | |
| 1020 DDG and return DDG_ALL_SCCS structure that contains them. */ | |
| 1021 ddg_all_sccs_ptr | |
| 1022 create_ddg_all_sccs (ddg_ptr g) | |
| 1023 { | |
| 145 | 1024 int i, j, k, scc, way; |
| 0 | 1025 int num_nodes = g->num_nodes; |
| 111 | 1026 auto_sbitmap from (num_nodes); |
| 1027 auto_sbitmap to (num_nodes); | |
| 1028 auto_sbitmap scc_nodes (num_nodes); | |
| 0 | 1029 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr) |
| 1030 xmalloc (sizeof (struct ddg_all_sccs)); | |
| 1031 | |
| 1032 sccs->ddg = g; | |
| 1033 sccs->sccs = NULL; | |
| 1034 sccs->num_sccs = 0; | |
| 1035 | |
| 1036 for (i = 0; i < g->num_backarcs; i++) | |
| 1037 { | |
| 1038 ddg_scc_ptr scc; | |
| 1039 ddg_edge_ptr backarc = g->backarcs[i]; | |
| 1040 ddg_node_ptr src = backarc->src; | |
| 1041 ddg_node_ptr dest = backarc->dest; | |
| 1042 | |
| 1043 /* If the backarc already belongs to an SCC, continue. */ | |
| 145 | 1044 if (backarc->in_scc) |
| 0 | 1045 continue; |
| 1046 | |
| 111 | 1047 bitmap_clear (scc_nodes); |
| 1048 bitmap_clear (from); | |
| 1049 bitmap_clear (to); | |
| 1050 bitmap_set_bit (from, dest->cuid); | |
| 1051 bitmap_set_bit (to, src->cuid); | |
| 0 | 1052 |
| 1053 if (find_nodes_on_paths (scc_nodes, g, from, to)) | |
| 1054 { | |
| 145 | 1055 scc = create_scc (g, scc_nodes, sccs->num_sccs); |
| 0 | 1056 add_scc_to_ddg (sccs, scc); |
| 1057 } | |
| 1058 } | |
| 145 | 1059 |
| 1060 /* Init max_dist arrays for Floyd–Warshall-like | |
| 1061 longest patch calculation algorithm. */ | |
| 1062 for (k = 0; k < num_nodes; k++) | |
| 1063 { | |
| 1064 ddg_edge_ptr e; | |
| 1065 ddg_node_ptr n = &g->nodes[k]; | |
| 1066 | |
| 1067 if (n->aux.count == -1) | |
| 1068 continue; | |
| 1069 | |
| 1070 n->max_dist[k] = 0; | |
| 1071 for (e = n->out; e; e = e->next_out) | |
| 1072 if (e->distance == 0 && g->nodes[e->dest->cuid].aux.count == n->aux.count) | |
| 1073 n->max_dist[e->dest->cuid] = e->latency; | |
| 1074 } | |
| 1075 | |
| 1076 /* Run main Floid-Warshall loop. We use only non-backarc edges | |
| 1077 inside each scc. */ | |
| 1078 for (k = 0; k < num_nodes; k++) | |
| 1079 { | |
| 1080 scc = g->nodes[k].aux.count; | |
| 1081 if (scc != -1) | |
| 1082 { | |
| 1083 for (i = 0; i < num_nodes; i++) | |
| 1084 if (g->nodes[i].aux.count == scc) | |
| 1085 for (j = 0; j < num_nodes; j++) | |
| 1086 if (g->nodes[j].aux.count == scc | |
| 1087 && g->nodes[i].max_dist[k] >= 0 | |
| 1088 && g->nodes[k].max_dist[j] >= 0) | |
| 1089 { | |
| 1090 way = g->nodes[i].max_dist[k] + g->nodes[k].max_dist[j]; | |
| 1091 if (g->nodes[i].max_dist[j] < way) | |
| 1092 g->nodes[i].max_dist[j] = way; | |
| 1093 } | |
| 1094 } | |
| 1095 } | |
| 1096 | |
| 1097 /* Calculate recurrence_length using max_dist info. */ | |
| 1098 for (i = 0; i < sccs->num_sccs; i++) | |
| 1099 set_recurrence_length (sccs->sccs[i]); | |
| 1100 | |
| 0 | 1101 order_sccs (sccs); |
| 111 | 1102 |
| 1103 if (flag_checking) | |
| 1104 check_sccs (sccs, num_nodes); | |
| 1105 | |
| 0 | 1106 return sccs; |
| 1107 } | |
| 1108 | |
| 1109 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */ | |
| 1110 void | |
| 1111 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) | |
| 1112 { | |
| 1113 int i; | |
| 1114 | |
| 1115 if (!all_sccs) | |
| 1116 return; | |
| 1117 | |
| 1118 for (i = 0; i < all_sccs->num_sccs; i++) | |
| 1119 free_scc (all_sccs->sccs[i]); | |
| 1120 | |
| 111 | 1121 free (all_sccs->sccs); |
| 0 | 1122 free (all_sccs); |
| 1123 } | |
| 1124 | |
| 1125 | |
| 1126 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination | |
| 1127 nodes - find all nodes that lie on paths from FROM to TO (not excluding | |
| 1128 nodes from FROM and TO). Return nonzero if nodes exist. */ | |
| 1129 int | |
| 1130 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) | |
| 1131 { | |
| 1132 int change; | |
| 1133 unsigned int u = 0; | |
| 1134 int num_nodes = g->num_nodes; | |
| 1135 sbitmap_iterator sbi; | |
| 1136 | |
| 111 | 1137 auto_sbitmap workset (num_nodes); |
| 1138 auto_sbitmap reachable_from (num_nodes); | |
| 1139 auto_sbitmap reach_to (num_nodes); | |
| 1140 auto_sbitmap tmp (num_nodes); | |
| 0 | 1141 |
| 111 | 1142 bitmap_copy (reachable_from, from); |
| 1143 bitmap_copy (tmp, from); | |
| 0 | 1144 |
| 1145 change = 1; | |
| 1146 while (change) | |
| 1147 { | |
| 1148 change = 0; | |
| 111 | 1149 bitmap_copy (workset, tmp); |
| 1150 bitmap_clear (tmp); | |
| 1151 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) | |
| 0 | 1152 { |
| 1153 ddg_edge_ptr e; | |
| 1154 ddg_node_ptr u_node = &g->nodes[u]; | |
| 1155 | |
| 1156 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out) | |
| 1157 { | |
| 1158 ddg_node_ptr v_node = e->dest; | |
| 1159 int v = v_node->cuid; | |
| 1160 | |
| 111 | 1161 if (!bitmap_bit_p (reachable_from, v)) |
| 0 | 1162 { |
| 111 | 1163 bitmap_set_bit (reachable_from, v); |
| 1164 bitmap_set_bit (tmp, v); | |
| 0 | 1165 change = 1; |
| 1166 } | |
| 1167 } | |
| 1168 } | |
| 1169 } | |
| 1170 | |
| 111 | 1171 bitmap_copy (reach_to, to); |
| 1172 bitmap_copy (tmp, to); | |
| 0 | 1173 |
| 1174 change = 1; | |
| 1175 while (change) | |
| 1176 { | |
| 1177 change = 0; | |
| 111 | 1178 bitmap_copy (workset, tmp); |
| 1179 bitmap_clear (tmp); | |
| 1180 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi) | |
| 0 | 1181 { |
| 1182 ddg_edge_ptr e; | |
| 1183 ddg_node_ptr u_node = &g->nodes[u]; | |
| 1184 | |
| 1185 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in) | |
| 1186 { | |
| 1187 ddg_node_ptr v_node = e->src; | |
| 1188 int v = v_node->cuid; | |
| 1189 | |
| 111 | 1190 if (!bitmap_bit_p (reach_to, v)) |
| 0 | 1191 { |
| 111 | 1192 bitmap_set_bit (reach_to, v); |
| 1193 bitmap_set_bit (tmp, v); | |
| 0 | 1194 change = 1; |
| 1195 } | |
| 1196 } | |
| 1197 } | |
| 1198 } | |
| 1199 | |
| 111 | 1200 return bitmap_and (result, reachable_from, reach_to); |
| 0 | 1201 } |
| 1202 | |
| 1203 #endif /* INSN_SCHEDULING */ |