From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12450 invoked by alias); 10 Dec 2003 16:17:23 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 12433 invoked from network); 10 Dec 2003 16:17:18 -0000 Received: from unknown (HELO mtagate2.de.ibm.com) (195.212.29.151) by sources.redhat.com with SMTP; 10 Dec 2003 16:17:18 -0000 Received: from d12relay01.megacenter.de.ibm.com (d12relay01.megacenter.de.ibm.com [9.149.165.180] (may be forged)) by mtagate2.de.ibm.com (8.12.10/8.12.10) with ESMTP id hBAGHHHf127160; Wed, 10 Dec 2003 16:17:17 GMT Received: from d10ml001.telaviv.ibm.com (d12av02.megacenter.de.ibm.com [9.149.165.228]) by d12relay01.megacenter.de.ibm.com (8.12.9/NCO/VER6.6) with ESMTP id hBAGHDAd265712; Wed, 10 Dec 2003 17:17:14 +0100 Subject: DDG - Implementing Swing Modulo Scheduling in GCC (cont.) To: gcc@gcc.gnu.org Cc: Ayal Zaks , David Edelsohn , Vladimir Makarov , canqun@yahoo.com.cn Message-ID: From: Mostafa Hagog Date: Wed, 10 Dec 2003 17:03:00 -0000 MIME-Version: 1.0 Content-type: text/plain; charset=ISO-8859-1 Content-transfer-encoding: quoted-printable X-SW-Source: 2003-12/txt/msg00632.txt.bz2 Following http://gcc.gnu.org/ml/gcc/2003-09/msg00954.html: ... >Infrastructure requirements for implementing SMS in GCC >------------------------------------------------------- [snip] >2. Building a dependance graph (for loops) with loop carried dependancies; > intra-loop dependancies could be based on the standard > LOG_LINKS/INSN_DEPEND structures. Loop carried dependancies > calculations must be added, with their associated distances (from > dependence.c?). > The following functionality must be implemented: > 1. Identifying cycles (strongly connected components) in the > dependance graph. > 2. Find the set of all predecessor [all successor] nodes for a given > set of nodes in the dependance graph. > 3. Find all nodes that lie on some directed path between two strongly > connected subgraphs. ... Here are the interfaces and implementation of the Data Dependence Graph required above. Data dependence information is collected in gcc during the scheduling passes, and we plan to invoke SMS as part of the first scheduling pass. Therefore, the dependence information collected for the scheduler can serve SMS. However, SMS requires additional information, some of which must be kept on the dependence edges. This requires a fundamental change in the rtl LOG_LINKS. Our solution is to build a new and different representation of the data dependence information. The attached ddg.h and ddg.c files define and implement this representation. It is based on a general graph of nodes and edge structures, with basic information such as dependence distance and latency of edges, as well as allowing algorithm-specific information in the "data" union. The graph is built from the current LOG_LINKS dependency information (ddg.c/build_deps()), although it can be easily built from other representations if/when needed. In addition the DDG calculates loop carried dependencies, strongly-connected components and their maximum recurrence length (e.g. to compute recMII). We tried to make the DDG as generic as possible for potential use by other algorithms or optimizations. Comments are welcome. Ayal & Mostafa. ddg.h: ------ /* DDG - Data Dependence Graph - interface. */ typedef struct ddg_node *ddg_node_ptr; typedef struct ddg_edge *ddg_edge_ptr; typedef struct ddg *ddg_ptr; typedef struct ddg_scc *ddg_scc_ptr; typedef struct ddg_all_sccs *ddg_all_sccs_ptr; typedef enum {TRUE_DEP, OUTPUT_DEP, ANTI_DEP} dep_type; typedef enum {REG_OR_MEM_DEP, REG_DEP, MEM_DEP, REG_AND_MEM_DEP} dep_data_type; #define NODE_SUCCESSORS(x) ((x)->successors) #define NODE_PREDECESSORS(x) ((x)->predecessors) /* A structure that represents a node in the DDG. */ struct ddg_node { /* Each node has a number which is the order of the insn in the BB that this node represents. */ int num; /* The insn represented by the node. */ rtx insn; /* Incoming/Outgoing dependency edges. */ ddg_edge_ptr in; ddg_edge_ptr out; /* Each bit is set if the node is a successor/predecessor according to the node number. */ sbitmap successors; sbitmap predecessors; /* For general use by algorithms manipulating the ddg. */ union { int count; void *info; } data; }; /* A structure that represents an edge in the DDG. */ struct ddg_edge { /* The source and destination nodes of the dependency edge. */ ddg_node_ptr src; ddg_node_ptr dest; /* Dependency type. */ dep_type type; /* REG or MEM dependency. ??? Not implemented yet. */ dep_data_type data_type; /* Latency of the depedency. */ int latency; /* The distance: number of loop iterations the dependency crosses. */ int distance; /* The following two fields are used to form a linked list of the in/out going edges to/from each node. */ ddg_edge_ptr next_in; ddg_edge_ptr next_out; /* For general use by algorithms manipulating the ddg. */ union { int count; void *info; } data; }; /* This structure holds the Data Dependence Graph for a basic block. */ struct ddg { /* The basic block for which this DDG is built. */ basic_block bb; /* Allow speculative movements when set. */ int speculative; /* Number of instructions in the basic block. */ int num_nodes; /* This array holds the nodes in the graph; it is indexed by the node number, which follows the order of the instructions in the BB. */ ddg_node_ptr nodes; /* The size of the allocated array for holding nodes. Can be different from num_nodes because we pre-allocate memory for the virtual nodes created when unrolling the loop. */ int node_arr_size; /* Array and number of back-arcs in the DDG. */ ddg_edge_ptr *backarcs; int num_backarcs; }; /* Holds information on an SCC (Strongly Connected Component) of the DDG. = */ struct ddg_scc { /* A bitmap that represents the nodes of the DDG that are in the SCC. */ sbitmap nodes; /* The backarc edges in the SCC, and their number. */ ddg_edge_ptr *backarcs; int num_backarcs; /* The maximum of (total_latency/total_distance) over all cycles in the S= CC. */ int recurrence_length; }; /* This structure holds the SCCs of the DDG. */ struct ddg_all_sccs { /* Array that holds the SCCs in the DDG, and their number. */ ddg_scc_ptr *sccs; int num_sccs; ddg_ptr ddg; }; ddg_ptr create_ddg (basic_block, int allow_speculative_moves); void free_ddg (ddg_ptr); void print_ddg (FILE *, ddg_ptr); ddg_node_ptr get_node_number_by_insn (ddg_ptr, rtx); ddg_edge_ptr create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, dep_type, dep_data_type, int latency, int distance); void add_edge_to_ddg (ddg_ptr, ddg_edge_ptr); void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr); void print_ddg_edge (FILE *, ddg_edge_ptr); void find_successors (sbitmap result, ddg_ptr, sbitmap); void find_predecessors (sbitmap result, ddg_ptr, sbitmap); ddg_all_sccs_ptr create_ddg_all_sccs (ddg_ptr); void free_ddg_all_sccs (ddg_all_sccs_ptr); int find_nodes_on_paths (sbitmap result, ddg_ptr, sbitmap from, sbitmap to); int longest_simple_path (ddg_ptr, int from, int to, sbitmap via); ddg.c: ------ /* DDG - Data Dependence Graph implementation. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" #include "toplev.h" #include "rtl.h" #include "tm_p.h" #include "hard-reg-set.h" #include "basic-block.h" #include "regs.h" #include "function.h" #include "flags.h" #include "insn-config.h" #include "insn-attr.h" #include "except.h" #include "toplev.h" #include "recog.h" #include "sched-int.h" #include "target.h" #include "cfglayout.h" #include "cfgloop.h" #include "sbitmap.h" #include "ddg.h" #define IS_ARTIFICIAL(x) ((x)->data.info ? 1 : 0) #define ART2ORIG(x) ((x)->data.info) enum edge_flag {NOT_IN_SCC, IN_SCC}; /* Forward declarations. */ static ddg_node_ptr add_artificial_node_to_ddg (ddg_ptr, rtx, ddg_node_ptr); static void add_backarc_edge_to_ddg (ddg_ptr, ddg_edge_ptr); static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr); /* The following three functions are copied from the current scheduler code in order to use sched_analyze() for computing the dependecies. They are used when initializing the sched_info structure. */ static const char * ddg_print_insn (rtx insn, int aligned) { static char tmp[80]; sprintf (tmp, "i%4d", INSN_UID (insn)); return tmp; } static int contributes_to_priority (rtx next, rtx insn) { return BLOCK_NUM (next) =3D=3D BLOCK_NUM (insn); } static void compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED, regset cond_exec ATTRIBUTE_UNUSED, regset used ATTRIBUTE_UNUSED, regset set ATTRIBUTE_UNUSED) { } static struct sched_info ddg_sched_info =3D { NULL, NULL, NULL, NULL, NULL, ddg_print_insn, contributes_to_priority, compute_jump_reg_dependencies, NULL, NULL, NULL, NULL, 0, 0, 0 }; /* The following three functions build the data dependence graph including loop-carried dependences, by first creating an artificial copy of the loop (by unrolling), then calculating intra-(extended)-block dependences, and finally generating ddg_edges for such dependneces and removing the artificial copy. */ /* Unroll the loop, assuming it contains a single basic block, and add the insns of the new iteration as artificial nodes to the ddg. */ static void add_artificial_loop_copy_to_ddg (ddg_ptr g) { int i, num_orig_nodes =3D g->num_nodes; rtx art_insn, first_art_insn, last_art_insn; /* The last insn before the jump out of the loop. */ rtx last_orig_insn =3D prev_nonnote_insn (g->bb->end); rtx next_last_orig_insn =3D NEXT_INSN (last_orig_insn); /* Prev_first_art_insn is the last insn in the original instruction chain; duplicated insns will start after this insn. */ rtx prev_first_art_insn; /* Unroll the single basic block loop, by duplicating the instructions (except for the latch jump) and chaining them after the last instruction of the loop. */ /* Avoid updating the boundaries of previous basic block. The note is later deleted. */ prev_first_art_insn =3D emit_note (NOTE_INSN_DELETED); last_art_insn =3D get_last_insn (); /* I.e., prev_first_art_insn. */ /* Create copy at the end of INSN chain. The chain will be repositioned later. */ for (i =3D 0; i < num_orig_nodes; i++) { ddg_node_ptr node =3D &g->nodes[i]; if (GET_CODE (node->insn) =3D=3D JUMP_INSN) /* This is the end of the basic block. */ break; duplicate_insn (node->insn); art_insn =3D get_last_insn (); if (art_insn =3D=3D last_art_insn) continue; add_artificial_node_to_ddg (g, art_insn, node); last_art_insn =3D art_insn; } first_art_insn =3D NEXT_INSN (prev_first_art_insn); delete_insn (prev_first_art_insn); if (! first_art_insn) return; /* Connect the virutal unroll chain to the original BB insn chain. */ NEXT_INSN (PREV_INSN (first_art_insn)) =3D NEXT_INSN (last_art_insn); if (NEXT_INSN (last_art_insn) !=3D NULL_RTX) PREV_INSN (NEXT_INSN (last_art_insn)) =3D PREV_INSN (first_art_insn); /* Our last_insn moved so update the global last_insn to what it was. */ set_last_insn (PREV_INSN (first_art_insn)); NEXT_INSN (last_orig_insn) =3D first_art_insn; PREV_INSN (first_art_insn) =3D last_orig_insn; NEXT_INSN (last_art_insn) =3D next_last_orig_insn; PREV_INSN (next_last_orig_insn) =3D last_art_insn; } /* Delete the instructions of the artificial loop copy. We assume that the artificial nodes are concentrated at the end of g->nodes array. */ static void remove_artificial_loop_copy_from_ddg (ddg_ptr g) { int i; for (i =3D g->num_nodes - 1; i >=3D 0; i--) { ddg_node_ptr node =3D &g->nodes[i]; if (! node->data.info) break; /* This is node is artificial. */ if (! INSN_DELETED_P (node->insn)) delete_insn (node->insn); } g->num_nodes =3D i + 1; } /* Do Data Dependency analysis and connect the nodes in the DDG. We assume the loop has a single basic block, and unroll it once to compute loop carried dependecies. */ static void build_deps (ddg_ptr g) { int i; /* Hold the dependency analysis state during the dependency calculations.= */ struct deps tmp_deps; rtx head, tail, link; /* Unroll the loop to expose cross iteration dependecies. */ add_artificial_loop_copy_to_ddg (g); /* Initilize the scheduler. */ current_sched_info =3D &ddg_sched_info; sched_init (NULL); /* Build the dependence information, using the sched_analyze function. */ init_deps_global (); init_deps (&tmp_deps); /* Do the data dependence analysis for the given block. */ get_block_head_tail (g->bb->index, &head, &tail); sched_analyze (&tmp_deps, head, tail); /* Add dependences so that branches are scheduled to run last in their block. */ /* add_branch_dependences (head, tail); ??? static in sched-rgn.c */ /* Create DDG edges according to LOG_LINKS. */ for (i =3D 0; i < g->num_nodes; i++) { ddg_node_ptr dest_node =3D &g->nodes[i]; int dest_is_art; if (! INSN_P (dest_node->insn)) continue; dest_is_art =3D IS_ARTIFICIAL (dest_node); for (link =3D LOG_LINKS (dest_node->insn); link; link =3D XEXP (link,= 1)) { ddg_edge_ptr e; int latency; ddg_node_ptr src_node =3D get_node_number_by_insn (g, XEXP (link, 0)); dep_type t =3D TRUE_DEP; /* We consider only orig--->art and art--->art dependencies. */ if (!src_node || IS_ARTIFICIAL (src_node)) continue; add_forward_dependence (XEXP (link, 0), dest_node->insn, REG_NOTE_KIND (link)); latency =3D insn_cost (dest_node->insn, link, XEXP (link, 0)); if (REG_NOTE_KIND (link) =3D=3D REG_DEP_ANTI) t =3D ANTI_DEP; else if (REG_NOTE_KIND (link) =3D=3D REG_DEP_OUTPUT) t =3D OUTPUT_DEP; /* If dest is an artificial node, then the dependency crosses a backarc. Otherwise it is a regular (intra-loop) dependency. */ if (dest_is_art) { ddg_node_ptr orig_dest_node =3D ART2ORIG (dest_node); /* Every insn is output dependent on itself; ignore such deps. = */ if (src_node !=3D orig_dest_node || t !=3D OUTPUT_DEP) { e =3D create_ddg_edge (src_node, orig_dest_node, t, REG_OR_MEM_DEP, latency, 1); add_backarc_edge_to_ddg (g, e); } } else { e =3D create_ddg_edge (src_node, dest_node, t, REG_OR_MEM_DEP, latency, 0); add_edge_to_ddg (g, e); } } } remove_artificial_loop_copy_from_ddg (g); /* Free the INSN_LISTs. */ free_deps (&tmp_deps); /* Release scheduler data. */ sched_finish (); } /* Given a basic block, create its DDG and return a pointer to a variable of ddg type that represents it. Initialize the ddg structure fields to the appropriate values. */ ddg_ptr create_ddg (basic_block bb, int allow_speculative_moves) { ddg_ptr g; rtx insn; int i; int num_nodes =3D 0; g =3D (ddg_ptr) xmalloc (sizeof (struct ddg)); memset (g, 0, sizeof (struct ddg)); g->bb =3D bb; g->speculative =3D allow_speculative_moves; /* Count the number of insns in the BB. */ for (insn =3D bb->head; insn !=3D NEXT_INSN (bb->end); insn =3D NEXT_INSN= (insn)) num_nodes++; g->num_nodes =3D num_nodes; /* Allocate the nodes array, and initialize the nodes. */ g->node_arr_size =3D num_nodes * 2; /* Twice to hold artificial copies. = */ g->nodes =3D (ddg_node_ptr) xmalloc (sizeof (struct ddg_node) * g->node_arr_size); /* The "upper" num_nodes nodes are zeroed lazily. */ memset (g->nodes, 0, sizeof (struct ddg_node) * num_nodes); i =3D 0; for (insn =3D bb->head; insn !=3D NEXT_INSN (bb->end); insn =3D NEXT_INSN= (insn)) { g->nodes[i].num =3D i; g->nodes[i].successors =3D sbitmap_alloc (num_nodes); sbitmap_zero (g->nodes[i].successors); g->nodes[i].predecessors =3D sbitmap_alloc (num_nodes); sbitmap_zero (g->nodes[i].predecessors); g->nodes[i++].insn =3D insn; } /* Build the data dependecy graph. */ build_deps (g); return g; } /* Free all the memory allocated for the DDG. */ void free_ddg (ddg_ptr g) { int i; for (i =3D 0; i < g->num_nodes; i++) { ddg_edge_ptr e =3D g->nodes[i].out; while (e) { ddg_edge_ptr next =3D e->next_out; free (e); e =3D next; } } free (g->nodes); free (g); } void print_ddg_edge (FILE *dump_file, ddg_edge_ptr e) { char dep_c; switch (e->type) { case OUTPUT_DEP : dep_c =3D 'O'; break; case ANTI_DEP : dep_c =3D 'A'; break; default: dep_c =3D 'T'; } fprintf (dump_file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn), dep_c, e->latency, e->distance, INSN_UID (e->dest->insn)); } void print_ddg (FILE *dump_file, ddg_ptr g) { int i; for (i =3D 0; i < g->num_nodes; i++) { ddg_edge_ptr e; print_rtl_single (dump_file, g->nodes[i].insn); fprintf (dump_file, "OUT ARCS: "); for (e =3D g->nodes[i].out; e; e =3D e->next_out) print_ddg_edge (dump_file, e); fprintf (dump_file, "\nIN ARCS: "); for (e =3D g->nodes[i].in; e; e =3D e->next_in) print_ddg_edge (dump_file, e); fprintf (dump_file, "\n"); } } /* Create an edge and initialize it with given values. */ ddg_edge_ptr create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, dep_type t, dep_data_type dt, int l, int d) { ddg_edge_ptr e =3D (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge)); e->src =3D src; e->dest =3D dest; e->type =3D t; e->data_type =3D dt; e->latency =3D l; e->distance =3D d; e->next_in =3D e->next_out =3D NULL; e->data.info =3D 0; return e; } /* Add the given edge to the in/out linked lists of the DDG nodes. */ void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr e) { ddg_node_ptr src =3D e->src; ddg_node_ptr dest =3D e->dest; SET_BIT (src->successors, dest->num); SET_BIT (dest->predecessors, src->num); e->next_in =3D g->nodes[dest->num].in; g->nodes[dest->num].in =3D e; e->next_out =3D g->nodes[src->num].out; g->nodes[src->num].out =3D e; } /* Algorithm for computing the recurrence_length of an scc. We assume at fi= rst that cycles in the data dependence graph contain a single backarc. This simpl= ifies the algorithm, and can be generalized later. */ static void set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g) { int j; int result =3D -1; for (j =3D 0; j < scc->num_backarcs; j++) { ddg_edge_ptr backarc =3D scc->backarcs[j]; int length; int distance =3D backarc->distance; ddg_node_ptr src =3D backarc->dest; ddg_node_ptr dest =3D backarc->src; length =3D longest_simple_path (g, src->num, dest->num, scc->nodes); if (length < 0 ) { fprintf (stderr, "Found backarc not on simple cycle in SCC.\n"); continue; } length +=3D backarc->latency; result =3D MAX (result, (length / distance)); } scc->recurrence_length =3D result; } /* Create a new SCC given the set of its nodes. Compute its recurrence_len= gth, and mark edges that belong to this scc as IN_SCC. */ static ddg_scc_ptr create_scc (ddg_ptr g, sbitmap nodes) { ddg_scc_ptr scc; int u; scc =3D (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc)); scc->backarcs =3D NULL; scc->num_backarcs =3D 0; scc->nodes =3D sbitmap_alloc (g->num_nodes); sbitmap_copy (scc->nodes, nodes); /* Mark the backarcs that belong to this SCC. */ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, { ddg_edge_ptr e; ddg_node_ptr n =3D &g->nodes[u]; for (e =3D n->out; e; e =3D e->next_out) if (TEST_BIT (nodes, e->dest->num)) { e->data.count =3D IN_SCC; if (e->distance > 0) add_backarc_to_scc (scc, e); } }); set_recurrence_length (scc, g); return scc; } /* Cleans the memory allocation of a given SCC. */ static void free_scc (ddg_scc_ptr scc) { if (!scc) return; sbitmap_free (scc->nodes); if (scc->num_backarcs > 0) free (scc->backarcs); free (scc); } /* Add a given edge known to be a backarc to the given DDG. */ void add_backarc_edge_to_ddg (ddg_ptr g, ddg_edge_ptr e) { add_edge_to_ddg (g, e); if (g->num_backarcs =3D=3D 0) g->backarcs =3D (ddg_edge_ptr *) xmalloc (sizeof (ddg_edge_ptr)); else g->backarcs =3D (ddg_edge_ptr *) xrealloc (g->backarcs, (g->num_backarcs + 1) * sizeof (ddg_edge_ptr)); g->backarcs[g->num_backarcs++] =3D e; } /* Add backarc to an SCC. */ void add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e) { if (scc->num_backarcs =3D=3D 0) scc->backarcs =3D (ddg_edge_ptr *) xmalloc (sizeof (ddg_edge_ptr)); else scc->backarcs =3D (ddg_edge_ptr *) xrealloc (scc->backarcs, (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr)); scc->backarcs[scc->num_backarcs++] =3D e; } /* Add the given SCC to the DDG. */ static void add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc) { if (g->num_sccs =3D=3D 0) g->sccs =3D (ddg_scc_ptr *) xmalloc (sizeof (ddg_scc_ptr)); else g->sccs =3D (ddg_scc_ptr *) xrealloc (g->sccs, (g->num_sccs +1) * sizeof (ddg_scc_ptr)); g->sccs[g->num_sccs++] =3D scc; } /* Create an artificial node and add it as the last node of the DDG. */ ddg_node_ptr add_artificial_node_to_ddg (ddg_ptr g, rtx art_insn, ddg_node_ptr orig_node) { ddg_node_ptr new_art_node; if (g->num_nodes =3D=3D 0) return NULL; if (g->num_nodes =3D=3D g->node_arr_size) abort (); new_art_node =3D &g->nodes[g->num_nodes]; memset (new_art_node, 0, sizeof (struct ddg_node)); new_art_node->num =3D g->num_nodes++; new_art_node->insn =3D art_insn; new_art_node->data.info =3D orig_node; return new_art_node; } /* Given the instruction INSN return the node number that represents it. */ ddg_node_ptr get_node_number_by_insn (ddg_ptr g, rtx insn) { int i; for (i =3D 0; i < g->num_nodes; i++) if (insn =3D=3D g->nodes[i].insn) return &g->nodes[i]; return NULL; } /* Given a set OPS of nodes in the DDG, find the set of their successors which are not in OPS, and set their bits in SUCC. Leaves the other bits in SUCC unchanged. */ void find_successors (sbitmap succ, ddg_ptr g, sbitmap ops) { int i; EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, { sbitmap node_succ =3D NODE_SUCCESSORS (&g->nodes[i]); sbitmap_a_or_b (succ, succ, node_succ); }); /* We want those that are not in ops. */ sbitmap_difference (succ, succ, ops); } /* Given a set OPS of nodes in the DDG, find the set of their predecessors which are not in OPS, and set their bits in PREDS. Leaves the other bits in PREDS unchanged. */ void find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops) { int i; EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, { const sbitmap node_preds =3D NODE_PREDECESSORS (&g->nodes[i]); sbitmap_a_or_b (preds, preds, node_preds); }); /* We want those that are not in ops. */ sbitmap_difference (preds, preds, ops); } /* Compare function to be passed to qsort to order the backarcs in descending recMII order. */ static int compare_sccs (ddg_scc_ptr s1, ddg_scc_ptr s2) { return (s2->recurrence_length - s1->recurrence_length); } /* Order the backarcs in descending recMII order using compare_sccs. */ static void order_sccs (ddg_all_sccs_ptr g) { qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr), (int (*) (const void *, const void *)) compare_sccs); } /* Perform the Strongly Connected Components decomposing algorithm on the DDG and return DDG_ALL_SCCS structure that contains them. */ ddg_all_sccs_ptr create_ddg_all_sccs (ddg_ptr g) { int i; int num_nodes =3D g->num_nodes; sbitmap from =3D sbitmap_alloc (num_nodes); sbitmap to =3D sbitmap_alloc (num_nodes); sbitmap scc_nodes =3D sbitmap_alloc (num_nodes); ddg_all_sccs_ptr sccs =3D (ddg_all_sccs_ptr) xmalloc (sizeof (struct ddg_all_sccs)); for (i =3D 0; i < g->num_backarcs; i++) { ddg_scc_ptr scc; ddg_edge_ptr backarc =3D g->backarcs[i]; ddg_node_ptr src =3D backarc->src; ddg_node_ptr dest =3D backarc->dest; /* If the backarc already belongs to an SCC, continue. */ if (backarc->data.count =3D=3D IN_SCC) continue; sbitmap_zero (from); sbitmap_zero (to); SET_BIT (from, dest->num); SET_BIT (to, src->num); if (find_nodes_on_paths (scc_nodes, g, from, to)) { scc =3D create_scc (g, scc_nodes); add_scc_to_ddg (sccs, scc); } } order_sccs (sccs); return sccs; } /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. = */ void free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) { int i; for (i =3D 0; i < all_sccs->num_sccs; i++) free_scc (all_sccs->sccs[i]); free (all_sccs); } /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination nodes - find all nodes that lie on paths from FROM to TO (not excluding nodes from FROM and TO). Return non zero if nodes exist. */ int find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) { int change, u; int num_nodes =3D g->num_nodes; sbitmap workset =3D sbitmap_alloc (num_nodes); sbitmap reachable_from =3D sbitmap_alloc (num_nodes); sbitmap reach_to =3D sbitmap_alloc (num_nodes); sbitmap tmp =3D sbitmap_alloc (num_nodes); sbitmap_copy (reachable_from, from); sbitmap_copy (tmp, from); change =3D 1; while (change) { change =3D 0; sbitmap_copy (workset, tmp); sbitmap_zero (tmp); EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, { ddg_edge_ptr e; ddg_node_ptr u_node =3D &g->nodes[u]; for (e =3D u_node->out; e !=3D (ddg_edge_ptr) 0; e =3D e->next_out) { ddg_node_ptr v_node =3D e->dest; int v =3D v_node->num; if (!TEST_BIT (reachable_from, v)) { SET_BIT (reachable_from, v); SET_BIT (tmp, v); change =3D 1; } } }); } sbitmap_copy (reach_to, to); sbitmap_copy (tmp, to); change =3D 1; while (change) { change =3D 0; sbitmap_copy (workset, tmp); sbitmap_zero (tmp); EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, { ddg_edge_ptr e; ddg_node_ptr u_node =3D &g->nodes[u]; for (e =3D u_node->in; e !=3D (ddg_edge_ptr) 0; e =3D e->next_in) { ddg_node_ptr v_node =3D e->src; int v =3D v_node->num; if (!TEST_BIT (reach_to, v)) { SET_BIT (reach_to, v); SET_BIT (tmp, v); change =3D 1; } } }); } return sbitmap_a_and_b_cg (result, reachable_from, reach_to); } /* Find the length of a longest path from SRC to DEST in G, going only through NODES, and disregarding backarcs. */ int longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes) { int i; int v, u; struct ddg_edge * e; int change =3D 1; int result; int num_nodes =3D g->num_nodes; sbitmap workset =3D sbitmap_alloc (num_nodes); sbitmap tmp =3D sbitmap_alloc (num_nodes); /* Data will hold the distance of the longest path found so far from src to each node. Initialize to less than minimum (-1). */ for (i=3D0; inum_nodes; i++) g->nodes[i].data.count =3D -1; g->nodes[src].data.count =3D 0; sbitmap_zero (tmp); SET_BIT (tmp, src); while (change) { change =3D 0; sbitmap_copy (workset, tmp); sbitmap_zero (tmp); EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, { ddg_node_ptr u_node =3D &g->nodes[u]; for (e =3D u_node->out; e; e =3D e->next_out) { ddg_node_ptr v_node =3D e->dest; v =3D v_node->num; if (TEST_BIT (nodes, v) && (e->distance =3D=3D 0) && (v_node->data.count < u_node->data.count + e->latency)) { v_node->data.count =3D u_node->data.count + e->latency; SET_BIT (tmp, v); change =3D 1; } } }); } result =3D g->nodes[dest].data.count; return result; }