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
|
package com.seaofnodes.simple.node;
import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.codegen.CodeGen;
import com.seaofnodes.simple.type.Type;
import com.seaofnodes.simple.type.TypeMem;
import com.seaofnodes.simple.util.BAOS;
import java.util.HashMap;
import java.util.IdentityHashMap;
public class LoopNode extends RegionNode {
public LoopNode( Parser.Lexer loc, Node xctrl, Node entry ) { super(loc,xctrl,entry,null); }
public LoopNode( LoopNode loop ) { super(loop); }
@Override public Tag serialTag() { return Tag.Loop; }
public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { }
public CFGNode entry() { return cfg(1); }
public CFGNode back () { return cfg(2); }
@Override
public Type compute() {
if( inProgress() ) return Type.CONTROL;
return entry()._type;
}
// Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
@Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); }
// Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
@Override public CFGNode idom(Node dep) { return entry(); }
// If this is an unreachable loop, it may not have an exit. If it does not
// (i.e., infinite loop), force an exit to make it reachable.
public FunNode forceExit( FunNode fun, StopNode stop ) {
// Walk the backedge, then immediate dominator tree util we hit this
// Loop again. If we ever hit a CProj from an If (as opposed to
// directly on the If) we found our exit.
CFGNode x = back();
while( x != this ) {
if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) {
CFGNode other = iff.cproj(1-exit._idx);
if( other!=null && other._ltree != _ltree && nested(_ltree,other._ltree) )
return fun; // Found an exit, not an infinite loop
}
x = x.idom();
}
// Found a no-exit loop. Insert an exit
NeverNode iff = (NeverNode)new NeverNode(1.2f,back()).peephole(); // Ideal never-branch
CProjNode t = new CProjNode(iff,0,"True" ).init();
CProjNode f = new CProjNode(iff,1,"False").init();
setDef(2,t); // True continues loop, False (never) exits loop
ReturnNode ret = fun.ret();
iff._ltree = t._ltree = _ltree;
ret._ltree = f._ltree = fun._ltree;
// Now fold control into the exit. Might have 1 valid exit, or an
// XCtrl or a bunch of prior NeverNode exits.
Node top = ConstantNode.make(Type.TOP).peephole();
Node memout = new MemMergeNode();
memout.addDef(f); // placeholder for control
memout.addDef(top);
for( Node u : _outputs )
if( u instanceof PhiNode phi && phi._type.isa(TypeMem.BOT) )
memout.addDef(phi);
memout.init();
Node ctrl = ret.ctrl(), mem = ret.mem(), expr = ret.expr();
if( ctrl!=null && ctrl._type != Type.XCONTROL ) {
// Perfect aligned exit?
if( !(ctrl instanceof RegionNode r &&
mem instanceof PhiNode pmem && pmem.region()==r &&
expr instanceof PhiNode prez && prez.region()==r ) ) {
// Nope, insert an aligned exit layer
RegionNode r = new RegionNode(_loc,null,ctrl).init();
ctrl = r; r._ltree = fun._ltree;
mem = new BulkMemPhiNode(r,mem).init();
expr = new PhiNode(r,expr).init();
}
// Append new Never exit
ctrl.keep().addDef(f );
mem .keep().addDef(memout);
expr.keep().addDef(top);
} else {
ctrl = f .keep();
mem = memout.keep();
expr = top .keep();
}
ret.setDef(0,ctrl.unkeep());
ret.setDef(1,mem .unkeep());
ret.setDef(2,expr.unkeep());
// Force sane types to exit; might locally break monotonicity
ret.init();
ret.out(0).init();
stop.init();
CodeGen.CODE.add(CodeGen.CODE._start);
CodeGen.CODE.add(mem);
return fun;
}
private static boolean nested(LoopTree inner, LoopTree outer) {
for( ; inner!=null; inner = inner._par )
if( inner == outer )
return true;
return false;
}
}
|
