From a9287272f2cb7b3d28f8ddbdeaa35f3c3b349c8e Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 3 Apr 2009 09:06:12 +0000 Subject: [PATCH] lots of bugs --- Robust/src/Analysis/Loops/DeadCode.java | 3 ++ Robust/src/Analysis/Loops/DomTree.java | 14 ++++++-- Robust/src/Analysis/Loops/LoopFinder.java | 13 +++++-- Robust/src/Analysis/Loops/LoopInvariant.java | 22 +++++++----- Robust/src/Analysis/Loops/LoopOptimize.java | 35 ++++++++++++++----- Robust/src/Analysis/Loops/localCSE.java | 36 +++++++++++--------- 6 files changed, 85 insertions(+), 38 deletions(-) diff --git a/Robust/src/Analysis/Loops/DeadCode.java b/Robust/src/Analysis/Loops/DeadCode.java index ebbba254..4df9eb48 100644 --- a/Robust/src/Analysis/Loops/DeadCode.java +++ b/Robust/src/Analysis/Loops/DeadCode.java @@ -29,6 +29,7 @@ public class DeadCode { case FKind.FlatFlagActionNode: case FKind.FlatCheckNode: case FKind.FlatBackEdge: + case FKind.FlatExit: case FKind.FlatTagDeclaration: case FKind.FlatMethod: case FKind.FlatAtomicEnterNode: @@ -74,8 +75,10 @@ public class DeadCode { if (!useful.contains(fn)) { //We have a useless node FlatNode fnnext=fn.getNext(0); + for(int i=0;i(); + childtree=new Hashtable>(); if (postdominator) { Set fnodes=fm.getNodeSet(); Vector v=new Vector(); for(Iterator 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;iLoopFinder implements Dominator Tree Loop detection. * * @author Brian Demsky - * @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 { @@ -154,6 +154,7 @@ public class LoopFinder implements Loops { //nested loop tree setofloops=new HashSet(); + //Find loops findloopheaders(hc); @@ -266,7 +267,15 @@ public class LoopFinder implements Loops { root.entries.add(current_node); //See if those we dominate are backedges - stk.addAll(dominator.children(current_node)); + Set children=dominator.children(current_node); + + if (children!=null) { + for(Iterator it=children.iterator();it.hasNext();) { + FlatNode fn=it.next(); + if (fn!=current_node) + stk.push(fn); + } + } } } diff --git a/Robust/src/Analysis/Loops/LoopInvariant.java b/Robust/src/Analysis/Loops/LoopInvariant.java index 0e007e1f..2afbc5b2 100644 --- a/Robust/src/Analysis/Loops/LoopInvariant.java +++ b/Robust/src/Analysis/Loops/LoopInvariant.java @@ -17,16 +17,17 @@ public class LoopInvariant { } LoopFinder loops; DomTree posttree; - Hashtable> table; + Hashtable> table; Set 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>(); + root=loops.getRootloop(fm); + table=new Hashtable>(); hoisted=new HashSet(); usedef=new UseDef(fm); posttree=new DomTree(fm,true); @@ -35,9 +36,9 @@ public class LoopInvariant { } 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); } } @@ -48,6 +49,9 @@ public class LoopInvariant { 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 fields=new HashSet(); HashSet types=new HashSet(); @@ -76,7 +80,7 @@ public class LoopInvariant { HashSet dominatorset=unsafe?null:computeAlways(l); /* Compute loop invariants */ - table.put(l, new Vector()); + table.put(entrance, new Vector()); while(changed) { changed=false; nextfn: @@ -98,7 +102,8 @@ public class LoopInvariant { 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(); @@ -114,7 +119,8 @@ public class LoopInvariant { 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; @@ -128,7 +134,7 @@ public class LoopInvariant { } //mark to hoist hoisted.add(fn); - table.get(l).add(fn); + table.get(entrance).add(fn); } } } diff --git a/Robust/src/Analysis/Loops/LoopOptimize.java b/Robust/src/Analysis/Loops/LoopOptimize.java index 2e584506..e8759189 100644 --- a/Robust/src/Analysis/Loops/LoopOptimize.java +++ b/Robust/src/Analysis/Loops/LoopOptimize.java @@ -18,13 +18,13 @@ public class LoopOptimize { 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); } } @@ -36,21 +36,33 @@ public class LoopOptimize { } } public void hoistOps(Loops l) { - Vector tohoist=loopinv.table.get(l); + Set entrances=l.loopEntrances(); + assert entrances.size()==1; + FlatNode entrance=(FlatNode)entrances.iterator().next(); + Vector 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;i1) { 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 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); + } } } @@ -220,7 +222,7 @@ class Group { class LocalExpression { Operation op; - Object o; + Object obj; Group a; Group b; TempDescriptor t; @@ -230,7 +232,7 @@ class LocalExpression { this.t=t; } LocalExpression(Object o) { - this.o=o; + this.obj=o; } LocalExpression(Group a, Group b, Operation op) { this.a=a; @@ -254,30 +256,32 @@ class LocalExpression { 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 -- 2.34.1