case FKind.FlatFlagActionNode:
case FKind.FlatCheckNode:
case FKind.FlatBackEdge:
+ case FKind.FlatExit:
case FKind.FlatTagDeclaration:
case FKind.FlatMethod:
case FKind.FlatAtomicEnterNode:
if (!useful.contains(fn)) {
//We have a useless node
FlatNode fnnext=fn.getNext(0);
+
for(int i=0;i<fn.numPrev();i++) {
FlatNode nprev=fn.getPrev(i);
+
for(int j=0;j<nprev.numNext();j++) {
if (nprev.getNext(j)==fn) {
nprev.setnext(j, fnnext);
public void analyze(FlatMethod fm, boolean postdominator) {
domtable=new Hashtable<FlatNode, FlatNode>();
+ childtree=new Hashtable<FlatNode, Set<FlatNode>>();
if (postdominator) {
Set<FlatNode> fnodes=fm.getNodeSet();
Vector<FlatNode> v=new Vector<FlatNode>();
for(Iterator<FlatNode> fit=fnodes.iterator();fit.hasNext();) {
FlatNode fn=fit.next();
- if (fn.numNext()==0)
+ if (fn.numNext()==0) {
v.add(fn);
+ }
}
FlatNode[] fnarray=new FlatNode[v.size()];
for(int i=0;i<v.size();i++) {
FlatNode fn=vec.elementAt(i);
FlatNode dom=null;
for(int j=0;j<(postdominator?fn.numNext():fn.numPrev());j++) {
- FlatNode ndom=domtable.get(postdominator?fn.getNext(i):fn.getPrev(i));
- dom=intersect(dom,ndom);
+ FlatNode np=postdominator?fn.getNext(j):fn.getPrev(j);
+ FlatNode ndom=domtable.get(np);
+ if (ndom!=null) {
+ if (dom==null)
+ dom=np;
+ else
+ dom=intersect(dom,np);
+ }
}
if (!domtable.containsKey(fn)||
!domtable.get(fn).equals(dom)) {
* <code>LoopFinder</code> implements Dominator Tree Loop detection.
*
* @author Brian Demsky <bdemsky@mit.edu>
- * @version $Id: LoopFinder.java,v 1.2 2009/03/27 09:02:25 bdemsky Exp $
+ * @version $Id: LoopFinder.java,v 1.3 2009/04/03 09:06:12 bdemsky Exp $
*/
public class LoopFinder implements Loops {
//nested loop tree
setofloops=new HashSet();
+
//Find loops
findloopheaders(hc);
root.entries.add(current_node);
//See if those we dominate are backedges
- stk.addAll(dominator.children(current_node));
+ Set<FlatNode> children=dominator.children(current_node);
+
+ if (children!=null) {
+ for(Iterator<FlatNode> it=children.iterator();it.hasNext();) {
+ FlatNode fn=it.next();
+ if (fn!=current_node)
+ stk.push(fn);
+ }
+ }
}
}
}
LoopFinder loops;
DomTree posttree;
- Hashtable<Loops, Vector<FlatNode>> table;
+ Hashtable<FlatNode, Vector<FlatNode>> table;
Set<FlatNode> hoisted;
UseDef usedef;
TypeUtil typeutil;
Set tounroll;
+ Loops root;
public void analyze(FlatMethod fm) {
loops=new LoopFinder(fm);
- Loops root=loops.getRootloop(fm);
- table=new Hashtable<Loops, Vector<FlatNode>>();
+ root=loops.getRootloop(fm);
+ table=new Hashtable<FlatNode, Vector<FlatNode>>();
hoisted=new HashSet<FlatNode>();
usedef=new UseDef(fm);
posttree=new DomTree(fm,true);
}
public void recurse(Loops parent) {
- processLoop(parent, parent.nestedLoops().size()==0);
for(Iterator lpit=parent.nestedLoops().iterator();lpit.hasNext();) {
Loops child=(Loops)lpit.next();
+ processLoop(child, child.nestedLoops().size()==0);
recurse(child);
}
}
Set elements=l.loopIncElements();
Set toprocess=l.loopIncElements();
toprocess.removeAll(hoisted);
+ Set entrances=l.loopEntrances();
+ assert entrances.size()==1;
+ FlatNode entrance=(FlatNode)entrances.iterator().next();
HashSet<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
HashSet<TypeDescriptor> types=new HashSet<TypeDescriptor>();
HashSet dominatorset=unsafe?null:computeAlways(l);
/* Compute loop invariants */
- table.put(l, new Vector<FlatNode>());
+ table.put(entrance, new Vector<FlatNode>());
while(changed) {
changed=false;
nextfn:
break;
case FKind.FlatElementNode:
- if (unsafe||!dominatorset.contains(fn)||
+ if (unsafe||dominatorset==null||
+ !dominatorset.contains(fn)||
checkNode(fn,elements))
continue nextfn;
TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
break;
case FKind.FlatFieldNode:
- if (unsafe||!dominatorset.contains(fn)||
+ if (unsafe||dominatorset==null||
+ !dominatorset.contains(fn)||
fields.contains(((FlatFieldNode)fn).getField())||
checkNode(fn,elements)) {
continue nextfn;
}
//mark to hoist
hoisted.add(fn);
- table.get(l).add(fn);
+ table.get(entrance).add(fn);
}
}
}
dooptimize(fm);
}
private void dooptimize(FlatMethod fm) {
- Loops root=loopinv.loops.getRootloop(fm);
+ Loops root=loopinv.root;
recurse(root);
}
private void recurse(Loops parent) {
- processLoop(parent);
for(Iterator lpit=parent.nestedLoops().iterator();lpit.hasNext();) {
Loops child=(Loops)lpit.next();
+ processLoop(child);
recurse(child);
}
}
}
}
public void hoistOps(Loops l) {
- Vector<FlatNode> tohoist=loopinv.table.get(l);
+ Set entrances=l.loopEntrances();
+ assert entrances.size()==1;
+ FlatNode entrance=(FlatNode)entrances.iterator().next();
+ Vector<FlatNode> tohoist=loopinv.table.get(entrance);
Set lelements=l.loopIncElements();
TempMap t=new TempMap();
+ TempMap tnone=new TempMap();
FlatNode first=null;
FlatNode last=null;
+ if (tohoist.size()==0)
+ return;
+
for(int i=0;i<tohoist.size();i++) {
FlatNode fn=tohoist.elementAt(i);
TempDescriptor[] writes=fn.writesTemps();
+ FlatNode fnnew=fn.clone(tnone);
+
+ fnnew.rewriteUse(t);
+
for(int j=0;j<writes.length;j++) {
- if (writes[j]!=null&&!t.maps(writes[j])) {
+ if (writes[j]!=null) {
TempDescriptor cp=writes[j].createNew();
t.addPair(writes[j],cp);
}
}
- FlatNode fnnew=fn.clone(t);
+ fnnew.rewriteDef(t);
+
if (first==null)
first=fnnew;
else
last=fnnew;
/* Splice out old node */
if (writes.length==1) {
- FlatOpNode fon=new FlatOpNode(t.tempMap(writes[0]),writes[0], null, new Operation(Operation.ASSIGN));
+ FlatOpNode fon=new FlatOpNode(writes[0], t.tempMap(writes[0]), null, new Operation(Operation.ASSIGN));
fn.replace(fon);
+ if (fn==entrance)
+ entrance=fon;
} else if (writes.length>1) {
throw new Error();
}
}
/* The chain is built at this point. */
- assert l.loopEntrances().size()==1;
- FlatNode entrance=(FlatNode)l.loopEntrances().iterator().next();
+ FlatNode[] prevarray=new FlatNode[entrance.numPrev()];
for(int i=0;i<entrance.numPrev();i++) {
- FlatNode prev=entrance.getPrev(i);
+ prevarray[i]=entrance.getPrev(i);
+ }
+ for(int i=0;i<prevarray.length;i++) {
+ FlatNode prev=prevarray[i];
+
if (!lelements.contains(prev)) {
//need to fix this edge
for(int j=0;j<prev.numNext();j++) {
public void kill(Hashtable<LocalExpression, Group> tab, TempDescriptor t) {
LocalExpression e=new LocalExpression(t);
Group g=tab.get(e);
- tab.remove(e);
- g.set.remove(e);
+ if (g!=null) {
+ tab.remove(e);
+ g.set.remove(e);
+ }
}
}
class LocalExpression {
Operation op;
- Object o;
+ Object obj;
Group a;
Group b;
TempDescriptor t;
this.t=t;
}
LocalExpression(Object o) {
- this.o=o;
+ this.obj=o;
}
LocalExpression(Group a, Group b, Operation op) {
this.a=a;
h^=t.hashCode();
if (a!=null)
h^=a.hashCode();
- if (o!=null)
- h^=o.hashCode();
if (op!=null)
h^=op.getOp();
if (b!=null)
h^=b.hashCode();
if (f!=null)
h^=f.hashCode();
+ if (obj!=null)
+ h^=obj.hashCode();
return h;
}
+ public static boolean equiv(Object a, Object b) {
+ if (a!=null)
+ return a.equals(b);
+ else
+ return b==null;
+ }
+
public boolean equals(Object o) {
LocalExpression e=(LocalExpression)o;
- if (a!=e.a||f!=e.f||b!=e.b)
+ if (!(equiv(a,e.a)&&equiv(f,e.f)&&equiv(b,e.b)&&
+ equiv(td,e.td)&&equiv(this.obj,e.obj)))
return false;
- if (td!=null) {
- if (!td.equals(e.td))
- return false;
- }
- if (o!=null) {
- if (e.o==null)
- return false;
- return o.equals(e.o);
- } else if (op!=null)
+ if (op!=null)
return op.getOp()==e.op.getOp();
+ else if (e.op!=null)
+ return false;
return true;
}
}
\ No newline at end of file
projects / IRC.git / commitdiff