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