gcrtmethodinfo.java

Java Op Processor java vhdl processor

package com.jopdesign.build;

import java.util.*;
import java.io.PrintWriter;

import org.apache.bcel.classfile.*;
import org.apache.bcel.classfile.Method;
import org.apache.bcel.Constants;
import org.apache.bcel.generic.*;
import org.apache.bcel.verifier.exc.*;
import org.apache.bcel.verifier.structurals.*;
import org.apache.bcel.verifier.structurals.Frame;
import org.apache.bcel.verifier.structurals.UninitializedObjectType;
import org.apache.bcel.verifier.structurals.OperandStack;
import org.apache.bcel.verifier.structurals.LocalVariables;

/**
 * It is a class that are invoked two times for every non-abstract method. The
 * <code>stackWalker</code> method simulates the instructions of a given
 * method. Then this simulated context is used to extract information about the
 * incoming (ie. how the locals and the operands) frame looked for this
 * particular value of the program counter (PC). Then the information must reach
 * JOP. It is done by saving the garbage collection (GC) information below the
 * code address. We save one word that is packed with information about max.
 * number of local, max. number of operands etc. Then, if the method has ANY
 * reference for ANY value of the PC, the GC information is saved below this
 * info word. That is the case in the majority of the cases. As we need the type
 * (primitive or reference) for every local and every operand for every value of
 * the PC it can take up a lot of space. Initial experiments demonstrated an
 * overhead of 133% but now the default is an indexed approach. In this way the
 * X local bits and the Y operand bits are appended to form a pattern. These
 * patterns form a small number of unique patterns. Each PC is then mapped
 * (using just enough bits) to point to the corresponding unique pattern. The
 * unique patterns are packed at the end of bit map. When reading the file, we
 * refer to the "raw" and "indexed" approach. The raw aproach was saving the
 * aforementioned patterns for every PC. On JOP, a class called GCStkWalk is
 * responsible for identifying the references that may be among the locals and
 * the operands for the threads. A method named <code>swk</code> is
 * responsible for this scan. It walks the frames from the top and uses the
 * packes GC bit maps to determine which (if any) of the locals and operands
 * that hold references. It then returns a reference to an integer array that is
 * used in <code>GC.java</code> to push only the references onto into the
 * scanned list. Little note: The bits are written out from left to right in the
 * comments. The sum of the locals+operands cannot exceed 32. TODO: Test a
 * Gosling violation. TODO: Implement bytecode rearrangement when Gosling
 * violation detected.
 * 
 * @author rup, ms
 */
public class GCRTMethodInfo {
	static int WORDLEN = 32;

	static int totalpcwords = 0;

	static int totalcntMgciWords = 0;

	static HashMap miMap = new HashMap();

	/**
	 * Called from JOPizer->SetGCRTMethodInfo to run the stack simulation for
	 * the method.
	 * 
	 * @param mi
	 *            the method
	 */
	public static void stackWalker(MethodInfo mi) {
		((GCRTMethodInfo) miMap.get(mi)).stackWalker();
	}

	/**
	 * It runs the dump method without dumping.
	 * 
	 * @param methodbcel
	 * @return Returns the length in words that the GC bit maps will take.
	 */
	public static int gcLength(MethodInfo mi) {
		return ((GCRTMethodInfo) miMap.get(mi)).gcLength();
	}

	/**
	 * It writes out the gcpack and the bitmaps. Nice comments are dumped as
	 * well in the .jop file.
	 * 
	 * @param out
	 *            null if just the length is needed
	 * @param mi
	 *            the method
	 */
	public static void dumpMethodGcis(MethodInfo mi, PrintWriter out) {
		((GCRTMethodInfo) miMap.get(mi)).dumpMethodGcis(out);
	}
  
  public static void removePC(int pc,MethodInfo mi){
    ((GCRTMethodInfo) miMap.get(mi)).removePC(pc);
  }

	// instance
	MethodInfo mi;

	Method method;

	int length;

	// Operand map for a given PC
	int[] ogci;

	// Local variables map for a given PC
	int[] mgci;

	// Instruction count
	int instCnt;

	// instCnt
	String[] pcinfo;

	int mstack, margs, mreallocals, len;

  // word counters for indexed approach
  int pcwords = 0;
  
  String tostr;
  String signature;
  String name;  
  String cname;
  
	/**
	 * Instanciated from from <code>SetClassInfo</code>.
	 */
	public GCRTMethodInfo(MethodInfo mi, Method method) {
		this.mi = mi;
		this.method = method;

		mgci = new int[0];
		ogci = new int[0];
		instCnt = 0;
		length = 0;
		if (miMap.containsKey(mi)) {
			System.err.println("Alredy added mi.");
			System.exit(-1);
		} else {
			miMap.put(mi, this);
		}
	}

	/**
	 * It walks the stack frame at compile time. The locals and the operands are
	 * mapped to to bit maps. These bit maps are used at run time to identify an
	 * exact root set which are used in conjunction with a real-time garbage
	 * collector scheduler.
	 */
	private void stackWalker() {
		// System.out.println(".....................");
		// System.out.println("stackWalker");
		// System.out.println("Class
		// method:"+mi.cli.clazz.getClassName()+"."+mi.methodId);

		margs = mstack = mreallocals = len = instCnt = 0;

		Type at[] = method.getArgumentTypes();
		for (int i = 0; i < at.length; ++i) {
			margs += at[i].getSize();
		}

		if (!method.isStatic()) {
			margs++;
		}

		if (!method.isAbstract()) {
			mstack = method.getCode().getMaxStack();
			mreallocals = method.getCode().getMaxLocals() - margs;
      
      if ((mreallocals+margs+mstack)>31) {
        // we interprete clinit on JOP - no size restriction
        if (!method.getName().equals("<clinit>")) {
          System.err.println("wrong size: "+method.getName()+" cannot have (mreallocals+margs+mstack)>31");
          System.exit(-1);          
        }
      }

			instCnt = (method.getCode().getCode()).length;
      
			operandWalker();
		}
		// System.out.println(" ***
		// "+mi.cli.clazz.getClassName()+"."+mi.methodId+" --> mreallocals
		// ="+mreallocals+" margs ="+margs+" mstack ="+mstack);

	}

	/**
	 * Collect type information on the operands for the stack frame. The code is
	 * and then the execution context of each instructions is used to map the
	 * type info of each entry on the stack. We map a reference entry with a 1
	 * and a non-reference entry with a 0.
	 * 
	 * The simulation part is based of the BCEL Pass3bVerifer.
	 */
	private void operandWalker() {
		// System.out.println("operandWalker");

		JavaClass jc = mi.cli.clazz;

		ConstantPoolGen cpg = new ConstantPoolGen(jc.getConstantPool());

		// Some methods overridden (see bottom of this file)
		InstConstraintVisitor icv = new AnInstConstraintVisitor();

		icv.setConstantPoolGen(cpg);

		ExecutionVisitor ev = new ExecutionVisitor();
		ev.setConstantPoolGen(cpg);

		MethodGen mg = new MethodGen(method, jc.getClassName(), cpg);
		// To later get the PC positions of the instructions
		mg.getInstructionList().setPositions(true);
		tostr = mg.toString();
		signature = mg.getSignature();
		name = mg.getName();
		cname = mg.getClassName();
    if(method.getName().equalsIgnoreCase("trace")){
      boolean stop =true;
    }
		icv.setMethodGen(mg);

		if (!(mg.isAbstract() || mg.isNative())) { // IF mg HAS CODE (See pass
			// 2)

			ControlFlowGraph cfg = new ControlFlowGraph(mg);

			// InstructionContext as key for inFrame
			HashMap inFrames = new HashMap();
			HashMap outFrames = new HashMap();

//			// ArrayList array (size is length of bytecode)
//			// holds ArrayList objects with clones of OperandStack objects for
//			// each PC
//			ArrayList osa[] = new ArrayList[method.getCode().getCode().length]; // +1
//			// because
//			// incoming
//			// frame
//			// to
//			// method
//			// is
//			// included
//			// ArrayList array (size is length of bytecode)
//			// holds ArrayList objects with clones of LocalVariables objects for
//			// each PC
//			ArrayList lva[] = new ArrayList[method.getCode().getCode().length];
//			for (int i = 0; i < lva.length; i++) {
//				lva[i] = new ArrayList();
//				osa[i] = new ArrayList();
//			}

			// Build the initial frame situation for this method.
			FrameFrame fStart = new FrameFrame(mg.getMaxLocals(), mg
					.getMaxStack());
			if (!mg.isStatic()) {
				if (mg.getName().equals(Constants.CONSTRUCTOR_NAME)) {
					fStart.setThis(new UninitializedObjectType(new ObjectType(
							jc.getClassName())));
					fStart.getLocals().set(0, fStart.getThis());
				} else {
					fStart.setThis(null);
					fStart.getLocals()
							.set(0, new ObjectType(jc.getClassName()));
				}
			}
			Type[] argtypes = mg.getArgumentTypes();
			int twoslotoffset = 0;
			for (int j = 0; j < argtypes.length; j++) {
				if (argtypes[j] == Type.SHORT || argtypes[j] == Type.BYTE
						|| argtypes[j] == Type.CHAR
						|| argtypes[j] == Type.BOOLEAN) {
					argtypes[j] = Type.INT;
				}
				fStart.getLocals().set(
						twoslotoffset + j + (mg.isStatic() ? 0 : 1),
						argtypes[j]);
				if (argtypes[j].getSize() == 2) {
					twoslotoffset++;
					fStart.getLocals().set(
							twoslotoffset + j + (mg.isStatic() ? 0 : 1),
							Type.UNKNOWN);
				}
			}

			InstructionContext start = cfg.contextOf(mg.getInstructionList()
					.getStart());
			// don't need to compare for first frame
			inFrames.put(start, fStart);

			boolean fbool = start.execute(fStart, new ArrayList(), icv, ev);
			Frame fout = start.getOutFrame(new ArrayList());
			outFrames.put(start,fout);
			start.setTag(start.getTag() + 1);
			// int posnow = start.getInstruction().getPosition();

//			osa[start.getInstruction().getPosition()].add(fStart.getStack()
//					.getClone());
//			lva[start.getInstruction().getPosition()].add(fStart.getLocals()
//					.getClone());

			Vector ics = new Vector(); // Type: InstructionContext
			Vector ecs = new Vector(); // Type: ArrayList (of
			// InstructionContext)

			ics.add(start);
			ecs.add(new ArrayList());
			int loopcnt = 1;
			// LOOP!
			while (!ics.isEmpty()) {
				loopcnt++;
				InstructionContext u;
				ArrayList ec;
				u = (InstructionContext) ics.get(0);
				//System.out.println(u.toString());
				ec = (ArrayList) ecs.get(0);
				ics.remove(0);
				ecs.remove(0);
				ArrayList oldchain = (ArrayList) (ec.clone());
				ArrayList newchain = (ArrayList) (ec.clone());
				newchain.add(u);

				if ((u.getInstruction().getInstruction()) instanceof RET) {
					// We can only follow _one_ successor, the one after the
					// JSR that was recently executed.
					RET ret = (RET) (u.getInstruction().getInstruction());
					ReturnaddressType t = (ReturnaddressType) u.getOutFrame(
							oldchain).getLocals().get(ret.getIndex());
					InstructionContext theSuccessor = cfg.contextOf(t
							.getTarget());

					// Sanity check
					InstructionContext lastJSR = null;
					int skip_jsr = 0;
					for (int ss = oldchain.size() - 1; ss >= 0; ss--) {
						if (skip_jsr < 0) {
							throw new AssertionViolatedException(
									"More RET than JSR in execution chain?!");
						}
						if (((InstructionContext) oldchain.get(ss))
								.getInstruction().getInstruction() instanceof JsrInstruction) {
							if (skip_jsr == 0) {
								lastJSR = (InstructionContext) oldchain.get(ss);
								break;
							} else {
								skip_jsr--;
							}
						}
						if (((InstructionContext) oldchain.get(ss))
								.getInstruction().getInstruction() instanceof RET) {
							skip_jsr++;
						}
					}
					if (lastJSR == null) {
						throw new AssertionViolatedException(
								"RET without a JSR before in ExecutionChain?! EC: '"
										+ oldchain + "'.");
					}
					JsrInstruction jsr = (JsrInstruction) (lastJSR
							.getInstruction().getInstruction());
					if (theSuccessor != (cfg.contextOf(jsr.physicalSuccessor()))) {
						throw new AssertionViolatedException("RET '"
								+ u.getInstruction()
								+ "' info inconsistent: jump back to '"
								+ theSuccessor + "' or '"
								+ cfg.contextOf(jsr.physicalSuccessor()) + "'?");
					}

					if (theSuccessor.execute(u.getOutFrame(oldchain), newchain,
							icv, ev)) {
						ics.add(theSuccessor);
						ecs.add((ArrayList) newchain.clone());
					}
					//inFrames.put(theSuccessor,u.getOutFrame(oldchain));
					theSuccessor.setTag(theSuccessor.getTag() + 1);
//					osa[theSuccessor.getInstruction().getPosition()].add(fStart
//							.getStack().getClone());
//					lva[theSuccessor.getInstruction().getPosition()].add(fStart
//							.getLocals().getClone());
					Frame prevf = (Frame)inFrames.put(theSuccessor,u.getOutFrame(oldchain));
					Frame newf = theSuccessor.getOutFrame(newchain);
					Frame prevof = (Frame)outFrames.put(theSuccessor,newf);
					if (prevof != null && !frmComp(prevof,newf,theSuccessor)){
						System.out.println("A: Gosling violation:"
								+ prevf.toString()+newf.toString());
						System.exit(-1);
					}

				} else {// "not a ret"
					// Normal successors. Add them to the queue of successors.
					// TODO: Does u get executed?
					InstructionContext[] succs = u.getSuccessors();
					
//					System.out.println("suss#:" + succs.length);
					for (int s = 0; s < succs.length; s++) {
						InstructionContext v = succs[s];
						//System.out.println(v.toString());
                        if (v.execute(u.getOutFrame(oldchain), newchain, icv,
								ev)) {
							ics.add(v);
							ecs.add((ArrayList) newchain.clone());
						}
						v.setTag(v.getTag() + 1);
//						osa[v.getInstruction().getPosition()].add(fStart
//								.getStack().getClone());
//						lva[v.getInstruction().getPosition()].add(fStart
//								.getLocals().getClone());
						Frame prevf = (Frame)inFrames.put(v,u.getOutFrame(oldchain));
						Frame newf = v.getOutFrame(newchain);
						Frame prevof = (Frame)outFrames.put(v,newf);
						if (prevof != null && !frmComp(prevof,newf,v)){
							System.out.println("B: Gosling violation:"
									+ fStart.toString());
							System.exit(-1);
						}
					}
				}// end "not a ret"

				// Exception Handlers. Add them to the queue of successors.
				// [subroutines are never protected; mandated by JustIce]
				ExceptionHandler[] exc_hds = u.getExceptionHandlers();
				for (int s = 0; s < exc_hds.length; s++) {
					InstructionContext v = cfg.contextOf(exc_hds[s]
							.getHandlerStart());
					Frame f = new Frame(
							u.getOutFrame(oldchain).getLocals(),
							new OperandStack(
									u.getOutFrame(oldchain).getStack()
											.maxStack(),
									(exc_hds[s].getExceptionType() == null ? Type.THROWABLE
											: exc_hds[s].getExceptionType())));

					if (v.execute(f, new ArrayList(), icv, ev)) {
						ics.add(v);
						ecs.add(new ArrayList());
					}
					v.setTag(v.getTag() + 1);
//					osa[v.getInstruction().getPosition()].add(fStart.getStack()
//							.getClone());
//					lva[v.getInstruction().getPosition()].add(fStart
//							.getLocals().getClone());
					Frame prevf = (Frame)inFrames.put(v,f);
					Frame newf = v.getOutFrame(new ArrayList());
					Frame prevof = (Frame)outFrames.put(v,newf);
					if (prevof != null && !frmComp(prevof,newf,v)){							
						System.err.println("C: Gosling violation:"
								+ prevf.toString()+newf.toString());
						System.exit(-1);
					}