wcetanalyser.java

Java Op Processor java vhdl processor

            if(wcbblast.sucbb != null){
              wcbbnext = wcbblast.sucbb;             
            }else if(wcbblast.tarbb != null){
              wcbbnext = wcbblast.tarbb;
            }else{ // T node
System.out.println("T:"+ WU.printChain(link));              
              pl.remove(0);
            }
System.out.println("b:"+ WU.printChain(link));  
System.out.println("wcbbnext:"+wcbbnext.getIDS());
System.out.println("wcbbinvo:"+wcbbinvo.getIDS());
            if(wcbbnext != null){
              if(wcbbnext == wcbbinvo){ 
System.out.println("removing  pl(0). pll.size:"+pl.size());                
                okl.add(pl.remove(0)); // the max 1 candidate chain saved
System.out.println("removed  pl(0). pll.size:"+pl.size());
if(pl.size()>0)
  System.out.println("pl(0):"+WU.printChain((ArrayList)pl.get(0)));
              } 
              else if(link.contains(wcbbnext)){
                pl.remove(0);
              }
              else
                link.add(wcbbnext);
              
//              else if(wcbbnext.loopcontroller){ // check that it is the first loopcontroller
//                  boolean onlylc = true;
//                  for (int i=1;i<link.size();i++){
//                    if(((WCETBasicBlock)link.get(i)).loopcontroller){
//                      onlylc = false;
//                      break;
//                    }
//                  }
//                  if(onlylc){
//                    link.add(wcbbnext);
//                    wcbbinvo.innerlc = wcbbnext.bid;
//                  }
//                  else
//                    pl.remove(0);
//              } else if(wcbbnext.nodetype == WCETBasicBlock.INODE){
//                if(wcbbnext.invowcmb == wcbbinvo.invowcmb) 
//                  link.add(wcbbnext); // ok to invoke the same method (one cache miss is false, however)
//                else
//                  pl.remove(0);
//              }
//              else{
//                link.add(wcbbnext);
//              }         
            }
          }
          
          System.out.println("#ok chains:"+okl.size());
          for (int i=0;i<okl.size();i++){
            link = (ArrayList)okl.get(i);
            System.out.println(WU.printChain(link));
          }
          
          while(okl.size()>0){
            // conservative: require that it is the only invo block for all loops
            // ok to have it multiple times (just a more conservative estimate)
            link = (ArrayList)okl.get(0);
            WCETBasicBlock wcbbinvo = (WCETBasicBlock)link.get(0);
            wcbbinvo.innerinode = true;
            for (int i=1;i<link.size()-1;i++){
              WCETBasicBlock wcbbtest = (WCETBasicBlock)link.get(i);
              if(wcbbtest.nodetype == WCETBasicBlock.INODE && wcbbtest != wcbbinvo)
                wcbbinvo.innerinode = false;
            }           
          }
        } else{
          wcbb.innerinode = false; 
        }
      }
    }
    */
  }

  public ControlFlowGraph getControlFlowGraph() {
    return cfg;
  }

  public MethodGen getMethodGen() {
    return mg;
  }
  
  /**
   * Find a local variable based on an entry in the LocalVariableTable attribute.
   * @see http://java.sun.com/docs/books/vmspec/2nd-edition/html/ClassFile.doc.html#5956
   * @param index
   * @param pc
   * @return local variable type and name or "NA"
   */
  public String getLocalVarName(int index, int pc){
//System.out.println("getLocalVarName: index:"+index+" pc:"+pc+" info:"+mg.getClassName()+"."+mg.getName());
    LocalVariableTable lvt = methodbcel.getLocalVariableTable();
    String lvName = "";
    boolean match = false;
    if(lvt!=null){
      LocalVariable[] lva = lvt.getLocalVariableTable(); 

//System.out.println("lva.length:"+lva.length);   
     for(int i=0;i<lva.length;i++){
       LocalVariable lv = lva[i]; 
//System.out.println("lv["+i+"]: index:"+lv.getIndex()+" name:"+lv.getName()+" pcstart:"+pc+" length:"+lv.getLength());     
       if(lv.getIndex()==index){
//System.out.println("index match");       
         if(pc>=lv.getStartPC()){
//System.out.println("startpc match");
           if(pc<=lv.getStartPC()+lv.getLength()){
//System.out.println("endpc match");            
             lvName = lv.getSignature() +":"+lv.getName();
             if(match){
               System.out.println("Only one match pr. local variable table is possible");
               System.exit(-1);
             }
             match = true;
             //break; //safety check when commented out, but slower
           }
         }
       }
    }
    }
    return lvName;
  }

  /**
   * Get the bb that currently covers the bytecode at the position. The design
   * is such that some bb will always cover a bytecode. It may the the same bb
   * that is returned if the branch points back (direct loop).
   * 
   * @param pos
   * @return covering bb
   */
  public WCETBasicBlock getCoveringBB(InstructionHandle ih) {
    // if cov bb starts on pos then done otherwise run throug all keys
    WCETBasicBlock covbb = (WCETBasicBlock) bbs.get(new Integer(ih
        .getPosition()));
    if (covbb == null) {
      Iterator it = bbs.keySet().iterator();
      // find the cov. bb
      int bbpos = 0;
      while (it.hasNext()) {
        int apos = ((Integer) it.next()).intValue();
        if (apos < ih.getPosition() && apos > bbpos) {
          bbpos = apos;
        }
      }
      covbb = (WCETBasicBlock) bbs.get(new Integer(bbpos));
    }
    return covbb;
  }

  /**
   * Create a new wcbb if none of the existing wcbbs are starting on that
   * position. Call this method twice when you encounter a branch type byte
   * code.
   * 
   * @param start
   *          the position to check for
   * @return true if a wcbb was created
   */
  public boolean createBasicBlock(InstructionHandle stih) {
    boolean res;
    // get the covering bb
    WCETBasicBlock covwcbb = getCoveringBB(stih);
    if (covwcbb.getStart() == stih.getPosition()) {
      // already a bb on start pos
      res = false;
    } else // create one by splitting the covering bb
    {
      WCETBasicBlock wcbb = covwcbb.split(stih);
      if((stih.getInstruction() instanceof InvokeInstruction) &&
          !(((InvokeInstruction)stih.getInstruction()).getClassName(getCpg())).equals(wca.nativeClass)){
//System.out.println("inode:"+((InvokeInstruction)stih.getInstruction()).getClassName(getCpg()));       
        wcbb.nodetype = WCETBasicBlock.INODE; 
        leaf = false;
      }
      // save the new bb in the hash map
      if (bbs.put(new Integer(stih.getPosition()), wcbb) != null) {
        System.err.println("The starting pos should be unique.");
        System.exit(-1);
      }
      res = true;
    }
    return res;
  }
  
  public void createBasicBlock(int type){
    if(type == WCETBasicBlock.SNODE){
      S = new WCETBasicBlock(this,WCETBasicBlock.SNODE);  
      bbs.put(new Integer(Integer.MIN_VALUE), S);
    }
    if(type == WCETBasicBlock.TNODE){
      T = new WCETBasicBlock(this,WCETBasicBlock.TNODE);
      bbs.put(new Integer(Integer.MAX_VALUE), T);
    }
  }

  /**
   * It sorts the basic blocks and creates the directed graph.
   */
  public void directedGraph() {
    // now create the directed graph
    dg = new int[bbs.size()][bbs.size()];
    WCETBasicBlock.bba = new WCETBasicBlock[bbs.size()+2];//TODO
    LineNumberTable lnt = methodbcel.getLineNumberTable();
    WCETBasicBlock pbb = null;
    for (Iterator iter = bbs.keySet().iterator(); iter.hasNext();) {
      Integer keyInt = (Integer) iter.next();
      WCETBasicBlock wcbb = (WCETBasicBlock) bbs.get(keyInt);
      if(pbb!=null)
        wcbb.prevbb = pbb;
      pbb = wcbb;
      if(wcbb.nodetype!=WCETBasicBlock.SNODE && wcbb.nodetype!=WCETBasicBlock.TNODE)
        wcbb.line = lnt.getSourceLine(wcbb.endih.getPosition());
      else 
        wcbb.line = -1;
      WCETBasicBlock tarwcbb = wcbb.getTarbb();
      int bid = wcbb.getBid();
//System.out.println(bid + ":"+WCETBasicBlock.bba.length);      
      WCETBasicBlock.bba[bid] = wcbb;
      if (tarwcbb != null) {
        int tarbbid = tarwcbb.getBid();
        tarwcbb.addTargeter(wcbb);
        dg[bid][tarbbid]++;
      }
      WCETBasicBlock sucbb = wcbb.getSucbb();
      if (sucbb != null){// && sucbb.nodetype != WCETBasicBlock.TNODE) {
        int sucid = sucbb.getBid();
        sucbb.addTargeter(wcbb);
        dg[bid][sucid]++;
      }
    }
    
    HashSet lines = new HashSet();
    // find loopdrivers/loopcontrollers
//System.out.println("\nmethod:"+method.getClass().getName()+"."+method.getName());    
//    System.out.println("METHOD:"+name);
    for (Iterator iter = bbs.keySet().iterator(); iter.hasNext();) {
      
      Integer keyInt = (Integer) iter.next();
      WCETBasicBlock wcbb = (WCETBasicBlock) bbs.get(keyInt);
      
//System.out.println("wcbb:"+wcbb.getIDS());    
//if(wcbb.line >=0)
//  System.out.println("codeline:"+codeLines[wcbb.line-1]);
//System.out.println("outer loop wcbb.id:"+wcbb.id);      
      // identify loop controller candidate
      HashMap wcaA = null;
      if(wcbb.line >=0)
        wcaA = WU.wcaA(codeLines[wcbb.line-1]);
      if(wcaA != null){
        if(wcaA.get("loop") != null){ // wcbb is now loopdriver

      if(((wcbb.sucbb != null || wcbb.tarbb != null)
          && (!wcbb.loopdriver || !wcbb.loopcontroller))
          && !lines.contains(new Integer(wcbb.line))){
        
//System.out.println("loopdriver id:"+wcbb.id);           
//System.out.println("LOOPDRIVER:"+wcbb.getIDS());            
            // find loopcontroller
            boolean set = false;
            WCETBasicBlock wcbbhit = wcbb;
            for (Iterator lciter = bbs.keySet().iterator(); lciter.hasNext();) {
              Integer lckeyInt = (Integer) lciter.next();
              WCETBasicBlock lcwcbb = (WCETBasicBlock) bbs.get(lckeyInt);
              if(set){
                if(lcwcbb.sucbb != null && lcwcbb.tarbb != null){
                  if(lcwcbb.line == wcbbhit.line){
//System.out.println("hit candidate:"+lcwcbb.id);                    
                    wcbbhit = lcwcbb;
                  } 
                }
              }
              
              if(lcwcbb==wcbb){
//System.out.println("set on id:"+lcwcbb.id);                
                set = true;
              }                
            }
//System.out.println("loop controller hit:"+wcbbhit.id);            
            wcbb.loopdriver = true;
            wcbb.loopcontroller = false;
            wcbb.loop = Integer.parseInt((String)wcaA.get("loop"));
            wcbbhit.loopcontroller = true;
            String wcastr = (codeLines[wcbb.line-1].substring(codeLines[wcbb.line-1].indexOf("@WCA")));
            if(wcastr.indexOf("<=")!=-1)
              wcbbhit.leq = true;
            wcbbhit.loopdriver = false;
            wcbbhit.loopid = wcbb.bid;
            wcbbhit.loop = Integer.parseInt((String)wcaA.get("loop"));
            wcbbhit.loopdriverwcbb = wcbb;
            lines.add(new Integer(wcbbhit.line));
//            if(wcaA.get("innerloop") != null){
//              if(((String)wcaA.get("innerloop")).equals("true")){
//System.out.println(wcbb.getIDS() +" is an inner loop controller");                
//                wcbb.innerloop = true;
//              }
//            }
          }
        }
      }
          
//      if(wcbb.loopcontroller){
//        HashMap tinbbs = wcbb.getInbbs();
//        if(wcbb.bid > 0 && tinbbs.size()!=2){
////          System.out.println("error in loopcontrol:"+wcbb.id);
////          System.out.println("tinbbs.size:"+tinbbs.size());
////          System.exit(-1);
//        }
//      }
    }
  }

  /**
   * Converts the WCETMethodBasicBlock to a String.
   * 
   * @return string representation of the MehtodBasicBlock
   */
  public String toString() {
    StringBuffer sb = new StringBuffer();
     
    sb.append("******************************************************************************\n");
        sb.append("WCET info for:"+jc.getClassName() + "." + methodbcel.getName()
        + methodbcel.getSignature()+"\n\n");

    // directed graph
    sb.append("Directed graph of basic blocks(row->column):\n");
    StringBuffer top = new StringBuffer();
    top.append(WU.prepad("",4));

    for (int i = 0; i < dg.length; i++) {
      if(i<dg.length-1)
        top.append(WU.postpad(getBbs(i).getIDS(),4));
      else
        top.append(WU.postpad(getBbs(i).getIDS(),4));
    }
    top.append("\n");

    for (int i = 0; i < top.length() - 3; i++) {
      sb.append("=");
    }
    sb.append("\n" + top.toString());

    for (int i = 0; i < dg.length; i++) {
      sb.append(WU.postpad(getBbs(i).getIDS(),3));

      for (int j = 0; j < dg.length; j++) {
        if (dg[i][j] == 0)
          sb.append(" ."); // a space does not clutter it as much as a zero
        else
          sb.append(" " + dg[i][j]);

        if(j<dg.length-1)
          sb.append(WU.postpad("",2));
        else
          sb.append(WU.postpad("",2));
      }
      sb.append("\n");
    }
    sb.append(WU.repeat("=",top.length() - 3));
    sb.append("\n");
    

    // bytecode listing
    sb.append("\nTable of basic blocks' and instructions\n");
    sb.append("=========================================================================\n");
    sb.append("Block Addr.  Bytecode                Cycles    Cache miss     Misc. info\n");
    sb.append("             [opcode]                        invoke  return\n");
    sb.append("-------------------------------------------------------------------------\n");
    for (Iterator iter = bbs.keySet().iterator(); iter.hasNext();) {
      Integer keyInt = (Integer) iter.next();
      WCETBasicBlock wcbb = (WCETBasicBlock) bbs.get(keyInt);
      sb.append(wcbb.toCodeString());
    }
    sb.append("=========================================================================\n");
    sb.append("Info: n="+n+" b="+WCETInstruction.calculateB(n)+" a="+WCETInstruction.a+" r="+WCETInstruction.r+" w="+WCETInstruction.w+"\n");
    sb.append("\n"); 
//    if(wca.ls){
//      sb.append(toLS(true, true, ""));
//      WCETBasicBlock.linkbb(WCETBasicBlock.bba[0]);
//      WCETBasicBlock.bbe();
//      sb.append("\n"+toLinkBBS());
//    }
    sb.append(toLS(false,true, null));
    
    sb.append(toDot(false));
   
    return sb.toString();
  }

  public String toDot(boolean global) {
    // global if true then dot is appwide   
    StringBuffer sb = new StringBuffer();
    // dot graph
    // use: dot -Tps graph.dot -o graph.ps
    boolean labels = true;