2 Copyright (C) 2002 Free Software Foundation, Inc.
4 This file is part of Bison, the GNU Compiler Compiler.
6 Bison is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 Bison is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with Bison; see the file COPYING. If not, write to
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
29 relation_print (relation r
, size_t size
, FILE *out
)
33 for (i
= 0; i
< size
; ++i
)
35 fprintf (out
, "%3d: ", i
);
37 for (j
= 0; r
[i
][j
] != -1; ++j
)
38 fprintf (out
, "%3d ", r
[i
][j
]);
45 /*---------------------------------------------------------------.
46 | digraph & traverse. |
48 | The following variables are used as common storage between the |
50 `---------------------------------------------------------------*/
53 static relation_nodes INDEX
;
54 static relation_nodes VERTICES
;
66 INDEX
[i
] = height
= top
;
69 for (j
= 0; R
[i
][j
] >= 0; ++j
)
71 if (INDEX
[R
[i
][j
]] == 0)
74 if (INDEX
[i
] > INDEX
[R
[i
][j
]])
75 INDEX
[i
] = INDEX
[R
[i
][j
]];
77 bitset_or (F
[i
], F
[i
], F
[R
[i
][j
]]);
80 if (INDEX
[i
] == height
)
89 bitset_copy (F
[j
], F
[i
]);
95 relation_digraph (relation r
, size_t size
, bitsetv
*function
)
100 CALLOC (INDEX
, size
+ 1);
101 CALLOC (VERTICES
, size
+ 1);
107 for (i
= 0; i
< size
; i
++)
110 for (i
= 0; i
< size
; i
++)
111 if (INDEX
[i
] == 0 && R
[i
])
121 /*-------------------------------------------.
122 | Destructively transpose R_ARG, of size N. |
123 `-------------------------------------------*/
126 relation_transpose (relation
*R_arg
, int n
)
129 relation new_R
= CALLOC (new_R
, n
);
130 /* END_R[I] -- next entry of NEW_R[I]. */
131 relation end_R
= CALLOC (end_R
, n
);
132 /* NEDGES[I] -- total size of NEW_R[I]. */
133 int *nedges
= CALLOC (nedges
, n
);
136 if (trace_flag
& trace_sets
)
138 fputs ("relation_transpose: input\n", stderr
);
139 relation_print (*R_arg
, n
, stderr
);
143 for (i
= 0; i
< n
; i
++)
145 for (j
= 0; (*R_arg
)[i
][j
] >= 0; ++j
)
146 ++nedges
[(*R_arg
)[i
][j
]];
149 for (i
= 0; i
< n
; i
++)
152 relation_node
*sp
= CALLOC (sp
, nedges
[i
] + 1);
159 for (i
= 0; i
< n
; i
++)
161 for (j
= 0; (*R_arg
)[i
][j
] >= 0; ++j
)
163 *end_R
[(*R_arg
)[i
][j
]] = i
;
164 ++end_R
[(*R_arg
)[i
][j
]];
170 /* Free the input: it is replaced with the result. */
171 for (i
= 0; i
< n
; i
++)
175 if (trace_flag
& trace_sets
)
177 fputs ("relation_transpose: output\n", stderr
);
178 relation_print (new_R
, n
, stderr
);