1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
package com.seaofnodes.simple;
import com.seaofnodes.simple.node.LoopNode;
import com.seaofnodes.simple.node.Node;
import com.seaofnodes.simple.node.ProjNode;
import java.util.ArrayList;
import java.util.BitSet;
public class IRPrinter {
// Print a node on 1 line, columnar aligned, as:
// NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE
// 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt
public static void _printLine( Node n, StringBuilder sb ) {
sb.append("%4d %-7.7s ".formatted(n._nid,n.label()));
if( n._inputs==null ) {
sb.append("DEAD\n");
return;
}
for( Node def : n._inputs )
sb.append(def==null ? "____ " : "%4d ".formatted(def._nid));
for( int i = n._inputs.size(); i<3; i++ )
sb.append(" ");
sb.append(" [[ ");
for( Node use : n._outputs )
sb.append(use==null ? "____ " : "%4d ".formatted(use._nid));
int lim = 5 - Math.max(n._inputs.size(),3);
for( int i = n._outputs.size(); i<lim; i++ )
sb.append(" ");
sb.append(" ]] ");
if( n._type!= null ) sb.append(n._type.str());
sb.append("\n");
}
private static StringBuilder nodeId(StringBuilder sb, Node n) {
sb.append("%%%d".formatted(n._nid));
if (n instanceof ProjNode proj) {
sb.append(".").append(proj._idx);
}
return sb;
}
// Print a node on 1 line, format is inspired by LLVM
// %id: TYPE = NODE(inputs ....)
// Nodes as referred to as %id
public static void _printLineLlvmFormat( Node n, StringBuilder sb ) {
nodeId(sb, n).append(": ");
if( n._inputs==null ) {
sb.append("DEAD\n");
return;
}
if( n._type!= null ) n._type.typeName(sb);
sb.append(" = ").append( n.label() ).append( "(" );
for( int i = 0; i < n._inputs.size(); i++ ) {
Node def = n.in(i);
if (i > 0)
sb.append(", ");
if (def == null) sb.append("_");
else nodeId(sb, def);
}
sb.append(")").append("\n");
}
public static void printLine( Node n, StringBuilder sb, boolean llvmFormat ) {
if (llvmFormat) _printLineLlvmFormat( n, sb );
else _printLine ( n, sb );
}
public static String prettyPrint(Node node, int depth) {
return prettyPrint( node, depth, false );
}
// Another bulk pretty-printer. Makes more effort at basic-block grouping.
public static String prettyPrint( Node node, int depth, boolean llvmFormat ) {
// First, a Breadth First Search at a fixed depth.
BFS bfs = new BFS(node,depth);
// Convert just that set to a post-order
ArrayList<Node> rpos = new ArrayList<>();
BitSet visit = new BitSet();
for( int i=bfs._lim; i< bfs._bfs.size(); i++ )
postOrd( bfs._bfs.get(i), rpos, visit, bfs._bs);
// Reverse the post-order walk
StringBuilder sb = new StringBuilder();
boolean gap=false;
for( int i=rpos.size()-1; i>=0; i-- ) {
Node n = rpos.get(i);
if( n.isCFG() || n.isMultiHead() ) {
if( !gap ) sb.append("\n"); // Blank before multihead
printLine( n, sb, llvmFormat ); // Print head
while( --i >= 0 ) {
Node t = rpos.get(i);
if( !t.isMultiTail() ) { i++; break; }
printLine( t, sb, llvmFormat );
}
sb.append("\n"); // Blank after multitail
gap = true;
} else {
printLine( n, sb, llvmFormat );
gap = false;
}
}
return sb.toString();
}
private static void postOrd(Node n, ArrayList<Node> rpos, BitSet visit, BitSet bfs) {
if( !bfs.get(n._nid) )
return; // Not in the BFS visit
if( visit.get(n._nid) ) return; // Already post-order walked
visit.set(n._nid);
// First walk the CFG, then everything
if( n.isCFG() ) {
for( Node use : n._outputs )
if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) )
postOrd(use, rpos,visit,bfs);
for( Node use : n._outputs )
if( use!=null && use.isCFG() )
postOrd(use,rpos,visit,bfs);
}
for( Node use : n._outputs )
if( use != null )
postOrd(use, rpos,visit,bfs);
// Post-order
rpos.add(n);
}
// Breadth-first search, broken out in a class to keep in more independent.
// Maintains a root-set of Nodes at the limit (or past by 1 if MultiHead).
public static class BFS {
// A breadth first search, plus MultiHeads for any MultiTails
public final ArrayList<Node> _bfs;
public final BitSet _bs; // Visited members by node id
public final int _depth; // Depth limit
public final int _lim; // From here to _bfs._len can be roots for a reverse search
public BFS( Node base, int d ) {
_depth = d;
_bfs = new ArrayList<>();
_bs = new BitSet();
add(base); // Prime the pump
int idx=0, lim=1; // Limit is where depth counter changes
while( idx < _bfs.size() ) { // Ran out of nodes below depth
Node n = _bfs.get(idx++);
for( Node def : n._inputs )
if( def!=null && !_bs.get(def._nid) )
add(def);
if( idx==lim ) { // Depth counter changes at limit
if( --d < 0 )
break; // Ran out of depth
lim = _bfs.size(); // New depth limit
}
}
// Toss things past the limit except multi-heads
while( idx < _bfs.size() ) {
Node n = _bfs.get(idx);
if( n.isMultiHead() ) idx++;
else del(idx);
}
// Root set is any node with no inputs in the visited set
lim = _bfs.size();
for( int i=_bfs.size()-1; i>=0; i-- )
if( !any_visited(_bfs.get(i)) )
swap( i,--lim);
_lim = lim;
}
void swap( int x, int y ) {
if( x==y ) return;
Node tx = _bfs.get(x);
Node ty = _bfs.get(y);
_bfs.set(x,ty);
_bfs.set(y,tx);
}
void add(Node n) {
_bfs.add(n);
_bs.set(n._nid);
}
void del(int idx) {
Node n = Utils.del(_bfs, idx);
_bs.clear(n._nid);
}
boolean any_visited( Node n ) {
for( Node def : n._inputs )
if( def!=null && _bs.get(def._nid) )
return true;
return false;
}
}
}
|
