commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kohs...@apache.org
Subject svn commit: r359613 - /jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java
Date Wed, 28 Dec 2005 19:55:45 GMT
Author: kohsuke
Date: Wed Dec 28 11:55:43 2005
New Revision: 359613

URL: http://svn.apache.org/viewcvs?rev=359613&view=rev
Log:
DFS can use ArrayList better than BFS.

Modified:
    jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java

Modified: jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java?rev=359613&r1=359612&r2=359613&view=diff
==============================================================================
--- jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java
(original)
+++ jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/Subroutines.java
Wed Dec 28 11:55:43 2005
@@ -86,25 +86,25 @@
 
 		/** The instructions that belong to this subroutine. */
 		private Set instructions;
-		
+
 		/*
 		 * Refer to the Subroutine interface for documentation.
 		 */
 		public boolean contains(InstructionHandle inst){
 			return instructions.contains(inst);
 		}
-		
+
 		/**
 		 * The JSR or JSR_W instructions that define this
 		 * subroutine by targeting it.
 		 */
 		private HashSet theJSRs = new HashSet();
-		
+
 		/**
 		 * The RET instruction that leaves this subroutine.
 		 */
 		private InstructionHandle theRET;
-		
+
 		/**
 		 * Returns a String representation of this object, merely
 		 * for debugging purposes.
@@ -114,7 +114,7 @@
 		 */
 		public String toString(){
 			String ret = "Subroutine: Local variable is '"+localVariable+"', JSRs are '"+theJSRs+"',
RET is '"+theRET+"', Instructions: '"+instructions.toString()+"'.";
-			
+
 			ret += " Accessed local variable slots: '";
 			int[] alv = getAccessedLocalsIndices();
 			for (int i=0; i<alv.length; i++){
@@ -131,7 +131,7 @@
 
 			return ret;
 		}
-		
+
 		/**
 		 * Sets the leaving RET instruction. Must be invoked after all instructions are added.
 		 * Must not be invoked for top-level 'subroutine'.
@@ -161,7 +161,7 @@
 			}
 			theRET = ret;
 		}
-				
+
 		/*
 		 * Refer to the Subroutine interface for documentation.
 		 */
@@ -172,7 +172,7 @@
 			InstructionHandle[] jsrs = new InstructionHandle[theJSRs.size()];
 			return (InstructionHandle[]) (theJSRs.toArray(jsrs));
 		}
-	
+
 		/**
 		 * Adds a new JSR or JSR_W that has this subroutine as its target.
 		 */
@@ -203,7 +203,7 @@
 			}
 			return theRET;
 		}
-		
+
 		/*
 		 * Refer to the Subroutine interface for documentation.
 		 */
@@ -211,7 +211,7 @@
 			InstructionHandle[] ret = new InstructionHandle[instructions.size()];
 			return (InstructionHandle[]) instructions.toArray(ret);
 		}
-		
+
 		/* Satisfies Subroutine.getRecursivelyAccessedLocalsIndices(). */
 		public int[] getRecursivelyAccessedLocalsIndices(){
 			HashSet s = new HashSet();
@@ -276,7 +276,7 @@
 					}
 				}
 			}
-			
+
 			int[] ret = new int[acc.size()];
 			i = acc.iterator();
 			int j=-1;
@@ -304,7 +304,7 @@
 			Subroutine[] ret = new Subroutine[h.size()];
 			return (Subroutine[]) h.toArray(ret);
 		}
-		
+
 		/*
 		 * Sets the local variable slot the ASTORE that is targeted
 		 * by the JsrInstructions of this subroutine operates on.
@@ -319,7 +319,7 @@
 				localVariable = i;
 			}
 		}
-		
+
 		/**
 		 * The default constructor.
 		 */
@@ -352,7 +352,7 @@
 	 * create the Subroutine objects of.
 	 */
 	public Subroutines(MethodGen mg){
-	
+
 		InstructionHandle[] all = mg.getInstructionList().getInstructionHandles();
 		CodeExceptionGen[] handlers = mg.getExceptionHandlers();
 
@@ -367,7 +367,7 @@
 				sub_leaders.add(((JsrInstruction) inst).getTarget());
 			}
 		}
- 
+
 		// Build up the database.
 		Iterator iter = sub_leaders.iterator();
 		while (iter.hasNext()){
@@ -393,8 +393,8 @@
 				((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(all[i]);
 			}
 		}
-		
-		// Now do a BFS from every subroutine leader to find all the
+
+		// Now do a closure computation from every subroutine leader to find all the
 		// instructions that belong to a subroutine.
 		HashSet instructions_assigned = new HashSet(); // we don't want to assign an instruction
to two or more Subroutine objects.
 
@@ -407,7 +407,7 @@
             InstructionHandle actual = (InstructionHandle) (iter.next());
 			// Init Queue
 			ArrayList Q = new ArrayList();
-			Q.add(actual); // add(Obj) adds to the end, remove(0) removes from the start.
+			Q.add(actual);
 
             /* BFS ALGORITHM MODIFICATION: Start out with multiple "root" nodes, as exception
handlers are starting points of top-level code, too. [why top-level? TODO: Refer to the special
JustIce notion of subroutines.]*/
 			if (actual == all[0]){
@@ -416,9 +416,9 @@
 				}
 			}
 			/* CONTINUE NORMAL BFS ALGORITHM */
-			
+
 			while (!Q.isEmpty()){
-				InstructionHandle u = (InstructionHandle) Q.remove(0);
+				InstructionHandle u = (InstructionHandle) Q.remove(Q.size()-1);
                 if(closure.add(u)) {
                     InstructionHandle[] successors = getSuccessors(u);
                     for (int i=0; i<successors.length; i++){
@@ -435,12 +435,12 @@
                     throw new StructuralCodeConstraintException("Instruction '"+h+"' is part
of more than one subroutine (or of the top level and a subroutine).");
                 }
             }
-            
+
             if (actual != all[0]){// If we don't deal with the top-level 'subroutine'
 				((SubroutineImpl) getSubroutine(actual)).setLeavingRET();
 			}
 		}
-		
+
 		// Now make sure no instruction of a Subroutine is protected by exception handling code
 		// as is mandated by JustIces notion of subroutines.
 		/*for (int i=0; i<handlers.length; i++){
@@ -458,7 +458,7 @@
 				_protected = _protected.getNext();
 			}
 		}*/
-		
+
 		// Now make sure no subroutine is calling a subroutine
 		// that uses the same local variable for the RET as themselves
 		// (recursively).
@@ -485,7 +485,7 @@
 
 		for (int i=0; i<subs.length; i++){
 			int index = ((RET) (subs[i].getLeavingRET().getInstruction())).getIndex();
-			
+
 			if (!set.add(new Integer(index))){
 				// Don't use toString() here because of possibly infinite recursive subSubs() calls then.
 				SubroutineImpl si = (SubroutineImpl) subs[i];
@@ -493,11 +493,11 @@
 			}
 
 			noRecursiveCalls(subs[i], set);
-			
+
 			set.remove(new Integer(index));
 		}
-	} 
-	
+	}
+
 	/**
 	 * Returns the Subroutine object associated with the given
 	 * leader (that is, the first instruction of the subroutine).
@@ -508,7 +508,7 @@
 	 */
 	public Subroutine getSubroutine(InstructionHandle leader){
 		Subroutine ret = (Subroutine) subroutines.get(leader);
-		
+
 		if (ret == null){
 			throw new AssertionViolatedException("Subroutine requested for an InstructionHandle that
is not a leader of a subroutine.");
 		}
@@ -516,7 +516,7 @@
 		if (ret == TOPLEVEL){
 			throw new AssertionViolatedException("TOPLEVEL special subroutine requested; use getTopLevel().");
 		}
-		
+
 		return ret;
 	}
 
@@ -565,24 +565,24 @@
 		final InstructionHandle[] empty = new InstructionHandle[0];
 		final InstructionHandle[] single = new InstructionHandle[1];
 		final InstructionHandle[] pair = new InstructionHandle[2];
-		
+
 		Instruction inst = instruction.getInstruction();
-		
+
 		if (inst instanceof RET){
 			return empty;
 		}
-		
+
 		// Terminates method normally.
 		if (inst instanceof ReturnInstruction){
 			return empty;
 		}
-		
+
 		// Terminates method abnormally, because JustIce mandates
 		// subroutines not to be protected by exception handlers.
 		if (inst instanceof ATHROW){
 			return empty;
 		}
-		
+
 		// See method comment.
 		if (inst instanceof JsrInstruction){
 			single[0] = instruction.getNext();
@@ -611,7 +611,7 @@
 			}
 		}
 
-		// default case: Fall through.		
+		// default case: Fall through.
 		single[0] = instruction.getNext();
 		return single;
 	}



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message