wcetanalyser.java

Java Op Processor java vhdl processor

    WCETBasicBlock b = S;
    ArrayList al = new ArrayList(); // not finished paths
    
    // [l.length-1] : last element (T node)
    //  Integer.MIN_VALUE terminates a method sequence
    // first element is unique int id of method: mmap->midmap
    int[] l = new int[200]; 
    int MAXLINK = 1000;  // 
    
    l[0] = b.bid;
//System.out.println("l[0]:"+b.id);    
    l[1] = Integer.MIN_VALUE;
    al.add(l);
    int len = 0;    
    while(al.size()>0){
      if((l = (int[])al.get(0)) != l){
        len = 0;
        for (int i=0;true;i++){
          if(l[i]!=Integer.MIN_VALUE)
            len++;
          else{
  //System.out.println("l[len-1] "+l[len-1]);          
            b = bba[l[len-1]];
            break;
          }
        }
      }
//System.out.println("len:"+len);   
//for (int i=0;i<len;i++){
//  System.out.println(l[i]);
//}
      
      if(l.length<=len+1){ // make room for invokes
        int newl[] = new int[l.length+10];
        System.arraycopy(l,0,newl,0,len);
        l = newl;
      }
      
      if(l.length>MAXLINK){
        System.out.println("MAXLINK in "+b.wcmb.name+": probably UNBOUNDED and need a @WCA loop annotation");
        al.remove(l);
        break;
      }
  
      int hit = 0;
      int chit = 0;
      boolean svio = false;
      if(b.sucbb != null){
        if(b.sc != -1){  // constraint on sucbb
          for (int i=1;i<len;i++){
            if(l[i-1] == b.bid && l[i] == b.sucbb.bid)
              hit++;
            if(l[i-1] == b.scsid && l[i] == b.sctid)
              chit++;
          }
          if(hit>chit*b.sc)
            svio = true;
        }
      }
      
      hit = 0;
      chit = 0;
      boolean tvio = false;
      if(b.tarbb != null){
        if(b.tc != -1){
          for (int i=0;i<len;i++){
            if(l[i-1] == b.bid && l[i] == b.tarbb.bid)
              hit++;
            if(l[i-1] == b.tcsid && l[i] == b.tctid)
              chit++;
          }
          if(hit>chit*b.tc)
            tvio = true;
        }
      }
      
      // both paths advancing
      if((b.sucbb != null && !svio) && (b.tarbb != null && !tvio)){
        int newl[] = new int[l.length];
        System.arraycopy(l,0,newl,0,l.length);
        newl[len] = b.tarbb.bid;
        newl[len+1] = Integer.MIN_VALUE;
        if(b.tarbb.nodetype == WCETBasicBlock.TNODE)
          bbl.add(newl);
        else
          al.add(newl);
        
        l[len] = b.sucbb.bid;
        l[len+1] = Integer.MIN_VALUE;
        if(b.sucbb.nodetype == WCETBasicBlock.TNODE)
          bbl.add(al.remove(0));
      } else if(b.sucbb != null && !svio){
        l[len] = b.sucbb.bid;
        l[len+1] = Integer.MIN_VALUE;
        if(b.sucbb.nodetype == WCETBasicBlock.TNODE)
          bbl.add(al.remove(0));
      } else if(b.tarbb != null && !tvio){
        l[len] = b.tarbb.bid;
        l[len+1] = Integer.MIN_VALUE;
        if(b.tarbb.nodetype == WCETBasicBlock.TNODE)
          bbl.add(al.remove(0));
      } else
        al.remove(l);
    }
    
    // append methodid to invoking blocks as -id
//    for (int i=0;i<bbl.size();i++){
//      l = (int[])bbl.get(i);
//      int j = 0;
//      for (;j<l.length;j++){
//        if(l[j]==Integer.MIN_VALUE){
//          break;
//        }
//        else{
//          int inv = bba[l[j]].bbinvo.size();
//          int[] newl = new int[l.length+inv];
//          System.arraycopy(l,0,newl,0,j);
//          System.arraycopy(l,j,newl,j+inv,l.length-j);
//          for(int m = 0;m<inv;m++){
//            String mids = (String)bba[l[j]].bbinvo.get(m);
//            int mid = ((Integer)wcmb.wca.midmap.get(mids)).intValue();
//            newl[j+m] = -mid;
//          }
//        }
//      }
//    }
//
//    
//    
//    if(true){
//      for (int i=0;i<bbl.size();i++){
//        l = (int[])bbl.get(i);
//        int j = 0;
//        for (;j<l.length;j++){
//          if(l[j]==-1)
//            break;
//        }
//        System.out.println("bbl["+i+"]"+b.wcmb.cname+":"+j);
//      }
//    }
  }
  
  public static void bbe(){
    bbe = new int[bbl.size()];
//System.out.println("bbe size:"+bbe.length);
//System.out.println("bba[l[j]]:"+bba.length);
//for (int i=0;i<bba.length;i++){
//  System.out.println("bba["+i+"].id"+bba[i].id);
//  
//}
    int wcetmax = Integer.MIN_VALUE;
    int bcetmin = Integer.MAX_VALUE;
    for (int i=0;i<bbl.size();i++){
      int[] l = (int[])bbl.get(i);
//System.out.println("bbl["+i+"]"+"l.length="+l.length);      
      for (int j=0;j<l.length;j++){
        if(l[j]==Integer.MIN_VALUE)
          break;
//System.out.println("i = "+i);
//System.out.println("j = "+j);
//System.out.println("l[j] = "+l[j]);
        if(l[j]<0){ // another method w. neg. entry
//          int mid = -m;
//          String mids = (String)bba[l[j]].bbinvo.get(mid);
//          int mid = ((Integer)wcmb.wca.midmap.get(mids)).intValue();
//          newl[j+m] = -mid;
//        } else if(bba.length>l[j] && bba[l[j]]!=null){//TODO
          bbe[i] += bba[l[j]].getBlockCycles();
        } 
          
//System.out.println("bba[l["+i+"]].getBlockCycles()"+bba[l[i]].getBlockCycles());        
//System.out.println("bbe["+i+"]="+bbe[i]);        
        if(bbe[i]>wcetmax){
          wcetid = i;
          wcetmax = bbe[i];
        }
        if(bbe[i]<bcetmin){
          bcetid = i;
          bcetmin = bbe[i];
        }
      }
    }
//System.out.println("wcetid:"+wcetid);

//System.out.println("wcetmax:"+wcetmax);
//System.out.println("bcetid:"+bcetid);
//System.out.println("bcetmax:"+bcetmin);
//System.exit(-1);
    
  }


  /**
   * Add wbb that points to this wbb.
   * 
   * @param wbbtargeter
   *          a wbb that points to this wbb.
   * @return true if it was already added
   */
  boolean addTargeter(WCETBasicBlock wbbtargeter) {
    WCETBasicBlock wbbold = (WCETBasicBlock) inbbs.put(wbbtargeter.getKey(),
        wbbtargeter);
    if (wbbold == null) {
      return true;
    } else {
      return false;
    }
  }

  /**
   * Will create a new BB by splitting the old.
   * 
   * @param stih
   *          the first instruction of the new block
   * @return the new BB
   */
  WCETBasicBlock split(InstructionHandle newstih) {
    WCETBasicBlock spbb = new WCETBasicBlock(newstih, endih, wcmb, WCETBasicBlock.BNODE);
    end = newstih.getPrev().getPosition();
    endih = newstih.getPrev();
    return spbb;
  }

  /**
   * <code>loopchains</code> now contains the chains the define the loop. 
   */
  public void createLoopChains(){
//    System.out.println("entering createloopchains for:"+getIDS()+","+wcmb.cname+"."+wcmb.name);
    if(!loopcontroller){
      System.out.println("not a loop controler");
      System.exit(-1);
    }
    else{
//      System.out.println("loopcontroller:"+getIDS());
//      System.out.println("loopdriver:"+loopdriverwcbb.getIDS());
    }
    
    innerloop = true;
    loopchains = new ArrayList();

//if(innerloop)
//  return;
    ArrayList chains = new ArrayList();
    ArrayList chain = new ArrayList();
    chains.add(chain);
    chain.add(this);
    chain.add(sucbb);
    // loop until exausted all possibilities
    while(chains.size()>0){
      chain = (ArrayList)chains.get(0);
      WCETBasicBlock wcbblast = (WCETBasicBlock)chain.get(chain.size()-1);
      if(wcbblast.loopcontroller)
        innerloop = false;
      if(wcbblast.sucbb != null){
        if(wcbblast.sucbb == this){
          loopchains.add(chain);
        }
        else if(!wcbblast.loopcontroller){
          ArrayList newchain = (ArrayList)chain.clone();
          newchain.add(wcbblast.sucbb);
          chains.add(newchain);
        }         
      }
      if(wcbblast.tarbb != null){
        if(wcbblast.tarbb == this)
          loopchains.add(chain);
        else {
          ArrayList newchain = (ArrayList)chain.clone();
          newchain.add(wcbblast.tarbb);
          chains.add(newchain);
        }    
      }
      chains.remove(0);
    }
    // mark invocation blocks as innerloop
    if(innerloop){
//System.out.println("if innerloop");      
//System.out.println("loopchains:\n"+WU.printChains(loopchains));
      HashSet invowcmb = new HashSet();
      ArrayList invoblocks = new ArrayList();
      // loop all chains
      for (int i=0;i<loopchains.size();i++){
        chain = (ArrayList)loopchains.get(i);
        for (int j=0;j<chain.size();j++){
          WCETBasicBlock wcbb = (WCETBasicBlock)chain.get(j);
          if(wcbb.nodetype == WCETBasicBlock.INODE){
            invowcmb.add(wcbb.invowcmb);
            invoblocks.add(wcbb);
          }
        }
      }
//System.out.println("invowcmb.size():"+invowcmb.size());      
      if(invowcmb.size()==1){
//System.out.println("invoblocks.size():"+invoblocks.size());        
        for (int i=0;i<invoblocks.size();i++){
          WCETBasicBlock invowcbb = (WCETBasicBlock)invoblocks.get(i);
          invowcbb.innerloop = true;
          invowcbb.loopdriverwcbb = loopdriverwcbb;
          invowcbb.loop = loop;
        }
      }
    }
  }
  
  /**
   * Returns the cycle count for cache hit. Remember to check validWcet() for validity.
   * 
   * @return wcet count
   */
  public int getWcetHit() {
    return wcetHit;
  }

  /**
   * Calculte wcetHit and wcetMiss for the Basic block.
   */
  public void calculateWcet() {
    InstructionHandle ih = stih;
    wcetHit = 0;
    wcetMiss = 0;
    valid = true;
    if(nodetype != WCETBasicBlock.SNODE && nodetype != WCETBasicBlock.TNODE){
      do {
        int wcetHitTmp = WCETInstruction.getCyclesFromHandle(ih, false, wcmb.getN());
        int wcetMissTmp = WCETInstruction.getCyclesFromHandle(ih, true, wcmb.getN());
        if (wcetHitTmp != WCETInstruction.WCETNOTAVAILABLE) {
          wcetHit += wcetHitTmp;
          wcetMiss += wcetMissTmp;
        } else {
          valid = false;
        }
      } while (ih != endih && (ih = ih.getNext()) != null); // null will never
                                                            // happen, but need
                                                            // the getNext
    }
  }

  /**
   * True if the
   * 
   * @return
   */
  public boolean getValid() {
    return valid;
  }
  
  // convert to block name: in flow = out flow, S & T default = 1
  public String toLSFlow(){
    StringBuffer ls = new StringBuffer();
    if(nodetype == WCETBasicBlock.SNODE)
      ls.append(getIDS()+": 1 = f"+getIDS()+"_"+sucbb.getIDS()+"; // S flow\n");
    else if(nodetype == WCETBasicBlock.BNODE || nodetype == WCETBasicBlock.INODE){
      HashMap tinbbs = getInbbs();
      
      ls.append(getIDS()+": ");
      for (Iterator titer = tinbbs.keySet().iterator(); titer.hasNext();) {
        Integer tkeyInt = (Integer) titer.next();
        WCETBasicBlock w = (WCETBasicBlock) tinbbs.get(tkeyInt);
        ls.append("f"+w.getIDS()+"_"+getIDS());
        
        if(titer.hasNext())
          ls.append(" + ");
      } 
      ls.append(" = ");
      if(sucbb != null){
        //if(wcbb.sucbb.nodetype != WCETBasicBlock.TNODE){  
          ls.append("f"+getIDS()+"_"+sucbb.getIDS());
        //}
      }
      // same target can happen if there is an empty branch; if(true);
      boolean sametarget = ((sucbb != null && tarbb!=null)&&(sucbb == tarbb));
      if((sucbb != null && tarbb!=null)&&!sametarget)
        ls.append(" + ");
      if(tarbb!=null && !sametarget)
        ls.append("f"+getIDS()+"_"+tarbb.getIDS());
      
      ls.append(";\n");
      }
    else if(nodetype == WCETBasicBlock.TNODE){
      HashMap tinbbs = getInbbs();
      
      ls.append(getIDS()+": ");
      for (Iterator titer = tinbbs.keySet().iterator(); titer.hasNext();) {
        Integer tkeyInt = (Integer) titer.next();
        WCETBasicBlock w = (WCETBasicBlock) tinbbs.get(tkeyInt);
        ls.append("f"+w.getIDS()+"_"+getIDS());
        
        if(titer.hasNext())
          ls.append(" + ");
      } 
      ls.append(" = 1");
    }
    else{
      System.out.println("Unknown nodetype");
      System.exit(-1