isl_ast_build_ast_from_schedule: also add stride guard in generic case
[platform/upstream/isl.git] / isl_tarjan.c
1 /*
2  * Copyright 2010-2011 INRIA Saclay
3  * Copyright 2012      Ecole Normale Superieure
4  *
5  * Use of this software is governed by the MIT license
6  *
7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9  * 91893 Orsay, France
10  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11  */
12
13 #include <stdlib.h>
14 #include <isl/ctx.h>
15 #include <isl_tarjan.h>
16
17 void isl_tarjan_graph_free(struct isl_tarjan_graph *g)
18 {
19         if (!g)
20                 return;
21         free(g->node);
22         free(g->stack);
23         free(g->order);
24         free(g);
25 }
26
27 static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
28 {
29         struct isl_tarjan_graph *g;
30         int i;
31
32         g = isl_calloc_type(ctx, struct isl_tarjan_graph);
33         if (!g)
34                 return NULL;
35         g->len = len;
36         g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
37         if (!g->node)
38                 goto error;
39         for (i = 0; i < len; ++i)
40                 g->node[i].index = -1;
41         g->stack = isl_alloc_array(ctx, int, len);
42         if (!g->stack)
43                 goto error;
44         g->order = isl_alloc_array(ctx, int, 2 * len);
45         if (!g->order)
46                 goto error;
47
48         g->sp = 0;
49         g->index = 0;
50         g->op = 0;
51
52         return g;
53 error:
54         isl_tarjan_graph_free(g);
55         return NULL;
56 }
57
58 /* Perform Tarjan's algorithm for computing the strongly connected components
59  * in the graph with g->len nodes and with edges defined by "follows".
60  */
61 static int isl_tarjan_components(struct isl_tarjan_graph *g, int i,
62         int (*follows)(int i, int j, void *user), void *user)
63 {
64         int j;
65
66         g->node[i].index = g->index;
67         g->node[i].min_index = g->index;
68         g->node[i].on_stack = 1;
69         g->index++;
70         g->stack[g->sp++] = i;
71
72         for (j = g->len - 1; j >= 0; --j) {
73                 int f;
74
75                 if (j == i)
76                         continue;
77                 if (g->node[j].index >= 0 &&
78                         (!g->node[j].on_stack ||
79                          g->node[j].index > g->node[i].min_index))
80                         continue;
81
82                 f = follows(i, j, user);
83                 if (f < 0)
84                         return -1;
85                 if (!f)
86                         continue;
87
88                 if (g->node[j].index < 0) {
89                         isl_tarjan_components(g, j, follows, user);
90                         if (g->node[j].min_index < g->node[i].min_index)
91                                 g->node[i].min_index = g->node[j].min_index;
92                 } else if (g->node[j].index < g->node[i].min_index)
93                         g->node[i].min_index = g->node[j].index;
94         }
95
96         if (g->node[i].index != g->node[i].min_index)
97                 return 0;
98
99         do {
100                 j = g->stack[--g->sp];
101                 g->node[j].on_stack = 0;
102                 g->order[g->op++] = j;
103         } while (j != i);
104         g->order[g->op++] = -1;
105
106         return 0;
107 }
108
109 /* Decompose the graph with "len" nodes and edges defined by "follows"
110  * into strongly connected components (SCCs).
111  * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
112  * It should return -1 on error.
113  *
114  * If SCC a contains a node i that follows a node j in another SCC b
115  * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b
116  * in the result.
117  */
118 struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
119         int (*follows)(int i, int j, void *user), void *user)
120 {
121         int i;
122         struct isl_tarjan_graph *g = NULL;
123
124         g = isl_tarjan_graph_alloc(ctx, len);
125         if (!g)
126                 return NULL;
127         for (i = len - 1; i >= 0; --i) {
128                 if (g->node[i].index >= 0)
129                         continue;
130                 if (isl_tarjan_components(g, i, follows, user) < 0)
131                         goto error;
132         }
133
134         return g;
135 error:
136         isl_tarjan_graph_free(g);
137         return NULL;
138 }