Coverage Report

Created: 2017-08-18 19:41

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_tarjan.c
Line
Count
Source (jump to first uncovered line)
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
struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g)
18
612
{
19
612
  if (!g)
20
0
    return NULL;
21
612
  free(g->node);
22
612
  free(g->stack);
23
612
  free(g->order);
24
612
  free(g);
25
612
  return NULL;
26
612
}
27
28
static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
29
612
{
30
612
  struct isl_tarjan_graph *g;
31
612
  int i;
32
612
33
612
  g = isl_calloc_type(ctx, struct isl_tarjan_graph);
34
612
  if (!g)
35
0
    return NULL;
36
612
  g->len = len;
37
612
  g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
38
612
  if (
len && 612
!g->node612
)
39
0
    goto error;
40
1.82k
  
for (i = 0; 612
i < len1.82k
;
++i1.21k
)
41
1.21k
    g->node[i].index = -1;
42
612
  g->stack = isl_alloc_array(ctx, int, len);
43
612
  if (
len && 612
!g->stack612
)
44
0
    goto error;
45
612
  
g->order = 612
isl_alloc_array612
(ctx, int, 2 * len);
46
612
  if (
len && 612
!g->order612
)
47
0
    goto error;
48
612
49
612
  g->sp = 0;
50
612
  g->index = 0;
51
612
  g->op = 0;
52
612
53
612
  return g;
54
612
error:
55
0
  isl_tarjan_graph_free(g);
56
612
  return NULL;
57
612
}
58
59
/* Perform Tarjan's algorithm for computing the strongly connected components
60
 * in the graph with g->len nodes and with edges defined by "follows".
61
 */
62
static isl_stat isl_tarjan_components(struct isl_tarjan_graph *g, int i,
63
  isl_bool (*follows)(int i, int j, void *user), void *user)
64
1.21k
{
65
1.21k
  int j;
66
1.21k
67
1.21k
  g->node[i].index = g->index;
68
1.21k
  g->node[i].min_index = g->index;
69
1.21k
  g->node[i].on_stack = 1;
70
1.21k
  g->index++;
71
1.21k
  g->stack[g->sp++] = i;
72
1.21k
73
4.77k
  for (j = g->len - 1; 
j >= 04.77k
;
--j3.56k
)
{3.56k
74
3.56k
    isl_bool f;
75
3.56k
76
3.56k
    if (j == i)
77
1.21k
      continue;
78
2.35k
    
if (2.35k
g->node[j].index >= 0 &&2.35k
79
2.35k
      (!g->node[j].on_stack ||
80
1.27k
       g->node[j].index > g->node[i].min_index))
81
797
      continue;
82
2.35k
83
2.35k
    f = follows(i, j, user);
84
1.55k
    if (f < 0)
85
0
      return isl_stat_error;
86
1.55k
    
if (1.55k
!f1.55k
)
87
774
      continue;
88
1.55k
89
781
    
if (781
g->node[j].index < 0781
)
{435
90
435
      isl_tarjan_components(g, j, follows, user);
91
435
      if (g->node[j].min_index < g->node[i].min_index)
92
2
        g->node[i].min_index = g->node[j].min_index;
93
781
    } else 
if (346
g->node[j].index < g->node[i].min_index346
)
94
346
      g->node[i].min_index = g->node[j].index;
95
1.21k
  }
96
1.21k
97
1.21k
  
if (1.21k
g->node[i].index != g->node[i].min_index1.21k
)
98
348
    return isl_stat_ok;
99
1.21k
100
862
  
do 862
{1.21k
101
1.21k
    j = g->stack[--g->sp];
102
1.21k
    g->node[j].on_stack = 0;
103
1.21k
    g->order[g->op++] = j;
104
1.21k
  } while (j != i);
105
862
  g->order[g->op++] = -1;
106
862
107
1.21k
  return isl_stat_ok;
108
1.21k
}
109
110
/* Decompose the graph with "len" nodes and edges defined by "follows"
111
 * into strongly connected components (SCCs).
112
 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
113
 * It should return -1 on error.
114
 *
115
 * If SCC a contains a node i that follows a node j in another SCC b
116
 * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b
117
 * in the result.
118
 */
119
struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
120
  isl_bool (*follows)(int i, int j, void *user), void *user)
121
589
{
122
589
  int i;
123
589
  struct isl_tarjan_graph *g = NULL;
124
589
125
589
  g = isl_tarjan_graph_alloc(ctx, len);
126
589
  if (!g)
127
0
    return NULL;
128
1.73k
  
for (i = len - 1; 589
i >= 01.73k
;
--i1.15k
)
{1.15k
129
1.15k
    if (g->node[i].index >= 0)
130
398
      continue;
131
752
    
if (752
isl_tarjan_components(g, i, follows, user) < 0752
)
132
0
      return isl_tarjan_graph_free(g);
133
752
  }
134
589
135
589
  return g;
136
589
}
137
138
/* Decompose the graph with "len" nodes and edges defined by "follows"
139
 * into the strongly connected component (SCC) that contains "node"
140
 * as well as all SCCs that are followed by this SCC.
141
 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
142
 * It should return -1 on error.
143
 *
144
 * The SCC containing "node" will appear as the last component
145
 * in g->order.
146
 */
147
struct isl_tarjan_graph *isl_tarjan_graph_component(isl_ctx *ctx, int len,
148
  int node, isl_bool (*follows)(int i, int j, void *user), void *user)
149
23
{
150
23
  struct isl_tarjan_graph *g;
151
23
152
23
  g = isl_tarjan_graph_alloc(ctx, len);
153
23
  if (!g)
154
0
    return NULL;
155
23
  
if (23
isl_tarjan_components(g, node, follows, user) < 023
)
156
0
    return isl_tarjan_graph_free(g);
157
23
158
23
  return g;
159
23
}