From 0a0997c699554c22f0bfb3e29d34a7de5cda3af3 Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 20 Aug 2011 00:56:31 +0000 Subject: [PATCH] bug fix on the loop termination analysis --- Robust/src/Analysis/Loops/LoopTerminate.java | 77 ++++++++++++++------ Robust/src/IR/Flat/BuildFlat.java | 5 +- Robust/src/IR/Flat/FlatCondBranch.java | 9 +++ 3 files changed, 68 insertions(+), 23 deletions(-) diff --git a/Robust/src/Analysis/Loops/LoopTerminate.java b/Robust/src/Analysis/Loops/LoopTerminate.java index f0111eb0..6344ecec 100644 --- a/Robust/src/Analysis/Loops/LoopTerminate.java +++ b/Robust/src/Analysis/Loops/LoopTerminate.java @@ -6,10 +6,12 @@ import java.util.Iterator; import java.util.Set; import Analysis.SSJava.SSJavaAnalysis; +import IR.FieldDescriptor; import IR.Operation; import IR.State; import IR.Flat.FKind; import IR.Flat.FlatCondBranch; +import IR.Flat.FlatFieldNode; import IR.Flat.FlatMethod; import IR.Flat.FlatNode; import IR.Flat.FlatOpNode; @@ -28,6 +30,9 @@ public class LoopTerminate { // induction variable TempDescriptor private HashMap derivedVar2basicInduction; + // maps a loop entrance to the result of termination analysis + private HashMap loopEntranceToTermination; + Set computed; State state; @@ -43,6 +48,7 @@ public class LoopTerminate { this.inductionVar2DefNode = new HashMap(); this.derivedVar2basicInduction = new HashMap(); this.computed = new HashSet(); + this.loopEntranceToTermination = new HashMap(); } /** @@ -61,7 +67,9 @@ public class LoopTerminate { } /** - * iterate over the current level of loops and spawn analysis for its child + * + * spawn analysis for its child and then iterate over the current level of + * loops * * @param fm * FlatMethod for loop analysis @@ -71,8 +79,8 @@ public class LoopTerminate { private void recurse(FlatMethod fm, Loops parent) { for (Iterator lpit = parent.nestedLoops().iterator(); lpit.hasNext();) { Loops child = (Loops) lpit.next(); - processLoop(fm, child); recurse(fm, child); + processLoop(fm, child); } } @@ -139,11 +147,8 @@ public class LoopTerminate { if (fnvisit.kind() == FKind.FlatCondBranch) { FlatCondBranch fcb = (FlatCondBranch) fnvisit; - if (fcb.isLoopBranch()) { - numLoop++; - } - - if (fcb.isLoopBranch() || hasLoopExitNode(fcb, true, loopEntrance, loopElements)) { + if ((fcb.isLoopBranch() && fcb.getLoopEntrance().equals(loopEntrance)) + || hasLoopExitNode(fcb, true, loopEntrance, loopElements)) { // current FlatCondBranch can introduce loop exits // in this case, guard condition of it should be composed only by loop // invariants and induction variables @@ -159,12 +164,13 @@ public class LoopTerminate { numMustTerminateGuardCondtion++; } else { if (!fcb.isLoopBranch()) { + // I DON'T THIINK WE NEED TO CARE ABOUT THIS CASE!!! // if it is if-condition and it leads us to loop exit, // corresponding guard condition should be composed by induction // and invariants - throw new Error("Loop may never terminate at " - + fm.getMethod().getClassDesc().getSourceFileName() + "::" - + loopEntrance.numLine); + // throw new Error("Loop may never terminate at " + // + fm.getMethod().getClassDesc().getSourceFileName() + "::" + // + loopEntrance.numLine); } } } @@ -182,11 +188,10 @@ public class LoopTerminate { // # of must-terminate loop condition must be equal to or larger than # of // loop - if (numMustTerminateGuardCondtion < numLoop) { + if (numMustTerminateGuardCondtion == 0) { throw new Error("Loop may never terminate at " + fm.getMethod().getClassDesc().getSourceFileName() + "::" + loopEntrance.numLine); } - } /** @@ -307,6 +312,7 @@ public class LoopTerminate { // 1) find out basic induction variable // variable i is a basic induction variable in loop if the only definitions // of i within L are of the form i=i+c where c is loop invariant + for (Iterator elit = loopElements.iterator(); elit.hasNext();) { FlatNode fn = (FlatNode) elit.next(); if (fn.kind() == FKind.FlatOpNode) { @@ -419,7 +425,7 @@ public class LoopTerminate { } // here, verify that guard operand is an induction variable - if (!hasInductionVar(fon, induction, loopElements)) { + if (!hasInductionVar(fon, induction, loopElements, new HashSet())) { return false; } @@ -427,15 +433,39 @@ public class LoopTerminate { Set guardDefSet = getDefinitionInLoop(fon, guard, loopElements); for (Iterator iterator = guardDefSet.iterator(); iterator.hasNext();) { FlatNode guardDef = (FlatNode) iterator.next(); - if (!(guardDef.kind() == FKind.FlatLiteralNode) && !loopInv.hoisted.contains(guardDef)) { + if (guardDef.kind() == FKind.FlatFieldNode) { + FlatFieldNode ffn = (FlatFieldNode) guardDef; + if ((ffn.getField().isStatic() && ffn.getField().isFinal()) + || (!hasFieldAccessInLoopElements(ffn, loopElements))) { + // if field is STATIC FINAL field or field is not appeared inside + // the current loop, allow it to be the guard + // condition + return true; + } else { + return false; + } + } else if (!(guardDef.kind() == FKind.FlatLiteralNode) + && !loopInv.hoisted.contains(guardDef)) { return false; } } } - return true; } + private boolean hasFieldAccessInLoopElements(FlatFieldNode guardNode, Set loopElements) { + for (Iterator iterator = loopElements.iterator(); iterator.hasNext();) { + FlatNode fn = (FlatNode) iterator.next(); + if (fn.kind() == FKind.FlatFieldNode) { + FlatFieldNode ffn = (FlatFieldNode) fn; + if (!ffn.equals(guardNode) && ffn.getField().equals(guardNode.getField())) { + return true; + } + } + } + return false; + } + /** * check if TempDescriptor td has at least one induction variable and is * composed only by induction vars +loop invariants @@ -448,8 +478,10 @@ public class LoopTerminate { * elements of current loop and all nested loop * @return true if 'td' is induction variable */ - private boolean hasInductionVar(FlatNode fn, TempDescriptor td, Set loopElements) { + private boolean hasInductionVar(FlatNode fn, TempDescriptor td, Set loopElements, + Set visited) { + visited.add(td); if (inductionSet.contains(td)) { return true; } else { @@ -461,15 +493,16 @@ public class LoopTerminate { int inductionVarCount = 0; TempDescriptor[] readTemps = defNode.readsTemps(); for (int i = 0; i < readTemps.length; i++) { - if (!hasInductionVar(defNode, readTemps[i], loopElements)) { - if (!isLoopInvariantVar(defNode, readTemps[i], loopElements)) { - return false; + if (!visited.contains(readTemps[i])) { + if (!hasInductionVar(defNode, readTemps[i], loopElements, visited)) { + if (!isLoopInvariantVar(defNode, readTemps[i], loopElements)) { + return false; + } + } else { + inductionVarCount++; } - } else { - inductionVarCount++; } } - // check definition of td has at least one induction var if (inductionVarCount > 0) { return true; diff --git a/Robust/src/IR/Flat/BuildFlat.java b/Robust/src/IR/Flat/BuildFlat.java index fb3b75d1..c506e7ad 100644 --- a/Robust/src/IR/Flat/BuildFlat.java +++ b/Robust/src/IR/Flat/BuildFlat.java @@ -1355,6 +1355,7 @@ public class BuildFlat { fcb.setNumLine(ln.getNumLine()); fcb.setTrueProb(State.TRUEPROB); fcb.setLoop(); + fcb.setLoopEntrance(condition.getBegin()); FlatNop nopend=new FlatNop(); FlatBackEdge backedge=new FlatBackEdge(); @@ -1393,6 +1394,7 @@ public class BuildFlat { fcb.setNumLine(ln.getNumLine()); fcb.setTrueProb(State.TRUEPROB); fcb.setLoop(); + fcb.setLoopEntrance(begin); FlatNop nopend=new FlatNop(); FlatBackEdge backedge=new FlatBackEdge(); @@ -1418,7 +1420,7 @@ public class BuildFlat { continueset=oldcs; if(ln.getLabel()!=null){ state.fn2labelMap.put(begin, ln.getLabel()); - } + } return new NodePair(begin,nopend); } else if (ln.getType()==LoopNode.DOWHILELOOP) { TempDescriptor cond_temp=TempDescriptor.tempFactory("condition", new TypeDescriptor(TypeDescriptor.BOOLEAN)); @@ -1429,6 +1431,7 @@ public class BuildFlat { fcb.setNumLine(ln.getNumLine()); fcb.setTrueProb(State.TRUEPROB); fcb.setLoop(); + fcb.setLoopEntrance(begin); FlatNop nopend=new FlatNop(); FlatBackEdge backedge=new FlatBackEdge(); diff --git a/Robust/src/IR/Flat/FlatCondBranch.java b/Robust/src/IR/Flat/FlatCondBranch.java index ed620683..bb568fe9 100644 --- a/Robust/src/IR/Flat/FlatCondBranch.java +++ b/Robust/src/IR/Flat/FlatCondBranch.java @@ -3,6 +3,7 @@ import java.util.Vector; public class FlatCondBranch extends FlatNode { TempDescriptor test_cond; + FlatNode loopEntrance; double trueprob=0.5; boolean loop=false; @@ -29,6 +30,14 @@ public class FlatCondBranch extends FlatNode { public boolean isLoopBranch() { return loop; } + + public void setLoopEntrance(FlatNode loopEntrance){ + this.loopEntrance=loopEntrance; + } + + public FlatNode getLoopEntrance(){ + return loopEntrance; + } public void setTrueProb(double p) { trueprob=p; -- 2.34.1