instructionlist.java

一种将c高级语言转化给VHDL的编译器

    InstructionList copy = new InstructionList(_chipdef, _maxRunTime);
    
    for (Iterator vIt = this.keySet().iterator(); vIt.hasNext();) {
      Float time = (Float) vIt.next();
      float timefl = time.floatValue();
      
      //for all schedule times with the range from start to finish
      if((start <= timefl)&&(timefl <= finish)) {
        HashSet iList = getAllAtTime(timefl);
	for (Iterator vIt2 = iList.iterator(); vIt2.hasNext();) {
          InstructionObject instObj = (InstructionObject) vIt2.next();
	  //InstructionObject instObjCpy = new InstructionObject(instObj.copySaveOps());
	  
	  //copy the InstructionObject to the other list.  The other list has to
	  //do the job of actually creating the new InstructionObject, however
	  //because otherwise, the new object will still point to THIS's private
	  //variables instead of copy's
	  copy.copy(timefl, instObj);
	}
      }
    }
    
    return copy;
  
  }
  
  /**
  This does exactly the same as above, except that when copying
  InstructionObjects, the InstructionObject, function copyNewOps is used, to
  create copies of the instructions with new operands
  */
  public InstructionList partialListCopyNewBlocks(float start, float finish) {
  
    InstructionList copy = new InstructionList(_chipdef, _maxRunTime);
    _oldToNew = new HashMap();
    for (Iterator vIt = this.keySet().iterator(); vIt.hasNext();) {
      Float time = (Float) vIt.next();
      float timefl = time.floatValue();
      
      if((start <= timefl)&&(timefl <= finish)) {
        HashSet iList = getAllAtTime(timefl);
	for (Iterator vIt2 = iList.iterator(); vIt2.hasNext();) {
          InstructionObject instObj = (InstructionObject) vIt2.next();
	  //InstructionObject instObjCpy = instObj.copyNewOps();
	  copy.copyNewOps(timefl, instObj);
	}
      }
    }
    
    return copy;
  
  }
  
  /**
  create a new InstructionObject, and call copySaveOps to copy instObj to the
  newly created object
  */
  public void copy(float time, InstructionObject instObj) {
    InstructionObject instObjCpy = new InstructionObject();
    instObjCpy.copySaveOps(instObj);
    add(time, instObjCpy);
  }
  
  /**
  do the same as above except make the copy with new Operands 
  */
  public void copyNewOps(float time, InstructionObject instObj) {
    InstructionObject instObjCpy = new InstructionObject();
    instObjCpy.copyNewOps(instObj);
    add(time, instObjCpy);
  }
  
  /**
  if a string of instructions only result in the definition of a block variable, 
  they should be killed as they are useless since the block variable has no life 
  after this hyperblock.  This works, by first finding all instructions who
  define primals.  All the predecessors of these instructions must also be ok,
  so the inputs to these instructions are saved.  Then another search is
  performed for all instructions defining the inputs to the primal defining
  instructions.  This is repeated to find their predecessors until the ultimate
  predecessors of the primal defining circuits have been found.  Any instruction
  not in these circuits must define only block variables ultimately.
  */
  public void killBlockDefiningCircuits() {
    HashSet savedOuts = new HashSet();
    HashSet goodInsts = new HashSet();
    
    boolean change = false;
    do {
      change = false;
      //foreach instruction:
      for (Iterator vIt = _allInstsSet.iterator(); vIt.hasNext();) {
	InstructionObject instObj = (InstructionObject) vIt.next();
	Instruction inst = instObj.inst;
	Operand out = inst.getOperand(0);
	//if the output from this instruction is known to be ok because it is 
	//part of a circuit that defines a primal, or if the output is itself a 
	//primal, then ...
	if(((out.isPrimal())||(contains(savedOuts, out)))&&
	   (!goodInsts.contains(inst))) {
	  
	  //save the fact that this instruction is ok
	  goodInsts.add(inst);
	  
	  change = true;
	  
	  //save the inputs from this instruction, since this instruction's 
	  //predecessors must also be ok, if this guy is ok. 
	  Operand op;
	  int numDefs = inst.getNumberOfDefs();
	  int total = inst.getNumberOfOperands();
	  for(int i = numDefs; i < total; i++) {
            op = inst.getOperand(i);
            if(op != null)
              savedOuts.add(op);
	  }

          //save any predicate inputs
	  BooleanEquation predTmp = inst.getPredicate();
	  if(predTmp != null) {
            LinkedList BoolsTmp = predTmp.listBooleanOperands();
            for (Iterator itin = ((LinkedList)BoolsTmp.clone()).iterator(); 
          	 itin.hasNext(); ) {
              op = (Operand)itin.next();
              savedOuts.add(op);
            }
          }
	  
	}
      } 
    //continue until all primal defining circuits have been traced back to their
    //ultimate sources
    }while(change);
    
    //foreach instruction
    for (Iterator vIt = ((HashSet)_allInstsSet.clone()).iterator(); 
             vIt.hasNext();) {
      InstructionObject instObj = (InstructionObject) vIt.next();
      Instruction inst = instObj.inst;
      
      //if it's not one of the saved ones, kill it
      if(!goodInsts.contains(inst))
        remove(instObj);
    }
    
  }
  
  public boolean contains(HashSet savedOuts, Operand op) {
    for (Iterator vIt = savedOuts.iterator(); vIt.hasNext();) {
      Operand opTmp = (Operand) vIt.next();
      if(opTmp.toString().compareTo(op.toString())==0)
        return true;
    }
    return false;
  }
  
  /**
  This gets rid of aliasing in the form of block or boolean variables being
  loaded or stored into another block or boolean variable instead of a primal. 
  These load and store instructions can be deleted and the resultant operand can
  be replaced by the source operand whereever it is used.  But actually this
  replaces a special case created by modulo scheduling, where this aliased block
  is then used again in another load or store, which defines yet another block
  or boolean.  This looks for both loads and stores, kills them both and
  replaces all uses of their defined block or boolean operands with the source
  operand.  
  */
  public void killEmBlockToBlockCopies() {
    HashMap replacements = new HashMap();
    ArrayList times = new ArrayList(this.keySet());
    sort(times);
    //for all times
    for (Iterator vIt = times.iterator(); vIt.hasNext();) {
      Float time = (Float) vIt.next();
      float timefl = time.floatValue();
      HashSet list = getAllAtTime(timefl);
      //for each instruction at this time
      for (Iterator vIt2 = ((HashSet)list.clone()).iterator(); 
              vIt2.hasNext();) {
	InstructionObject instObj = (InstructionObject) vIt2.next();
	Instruction inst = instObj.inst;
	//if this instruction is a load or store
	if((Store.conforms(inst))||(Load.conforms(inst))){
	  Operand in = null;
	  Operand out1 = null;

	  if(Store.conforms(inst)) {
            in = Store.getValue(inst);
            out1 = Store.getDestination(inst);
	  }
	  if(Load.conforms(inst)) {
            in = Load.getSource(inst);
            out1 = Load.getResult(inst);
	  }
	  
	  
	  //if both this instruction's input and output are block or boolean 
	  //operands:
	  if(((in.isBlock())||(in.isBoolean()))&&
	     ((out1.isBlock())||(out1.isBoolean()))) {
	    boolean replaced = false;
	    //foreach instruction (place for speedup!!! now that getSuccs is  
	    //defined in here instead of MSchedHash, only the successors can be
	    //searched instead of all instructions)
	    for (Iterator it1 = ((HashSet)_allInstsSet.clone()).iterator(); 
        	      it1.hasNext();) {
	      InstructionObject cObj = (InstructionObject)it1.next();
	      Instruction cInst = cObj.inst;
	      //if the instruction is a child:
	      if((Store.conforms(cInst))||(Load.conforms(cInst))){
		Operand out2 = null;
		Operand in2 = null;
		if(Store.conforms(cInst)) {
	          in2 = Store.getValue(cInst);
        	  out2 = Store.getDestination(cInst);
		}
		if(Load.conforms(cInst)) {
	          in2 = Load.getSource(cInst);
        	  out2 = Load.getResult(cInst);
		}
		//if in2==out, which means this is a successor, and the out is a
		//block or boolean operand, delete the object and save that its
		//output needs to be replaced whereever it's used
		if((in2 == out1)&&((out2.isBlock())||(out2.isBoolean()))){
		  replacements.put(out2, in);
		  remove(cObj);
        	  replaced = true;
		}
	      }
	    }
	    //delete the first load or store, and save that its output needs to
	    //be replaced as well
	    if(replaced) {
	      replacements.put(out1, in);
	      remove(instObj);
	    }
	  }
	}

      }
    }
    
    //foreach instruction
    for (Iterator vIt = _allInstsSet.iterator(); 
         vIt.hasNext();) {
      InstructionObject instObj = (InstructionObject) vIt.next();
      //Instruction inst = instObj.inst;
      
      //for each key of the replacements hashMap, where:
      //key = alias, which should be removed
      //value = source operand, that should replace the alias
      for (Iterator vIte = replacements.keySet().iterator(); 
           vIte.hasNext();) {
        Operand op = (Operand) vIte.next();
        //get the source operand:
	Operand opTmp = (Operand) replacements.get(op);
	//replace the alias with the source:
	instObj.replaceOperand(op, opTmp);
      }
    }
  
  }

  /**
  I don't think this is used by modulo scheduling anymore, but it is still here
  in case I found later that it was useful.  It just replaces all operands in
  all instructions with new ones (but leaving wires connecting, i.e. replacing
  same operands with the same new operand)
  */
  public void newOpsForInsts() {
    _oldToNew = new HashMap();
    for (Iterator vIt = _allInstsSet.iterator(); 
         vIt.hasNext();) {
      InstructionObject instObj = (InstructionObject) vIt.next();
      instObj.newOps();
    }
  
  }
  
  /**
  if we have chains of loads and stores (that is where a value is stored into a
  primal, that primal is loaded (and perhaps used), and stored again, and
  perhaps loaded, all these instructions can be deleted, and all the extra
  operands can be replaced with the original source operand.  This was written
  specifically for modulo scheduling, but was placed in InstructionList, because
  it might be useful for other schedulers if they ever do use InstructionList. 
  Modulo scheduling creates chains of loads and stores to transfer data over the
  edges of the modulo scheduled block, but in the epilog and prolog, these
  chains cause confusion and are unnecessary extra space and slow down.
  */
  public void killLSChains() {
    HashSet allToDieSet = new HashSet();
    HashMap replacementMap = new HashMap();
    HashSet extraInsts = new HashSet();
    //foreach instruction
    for (Iterator vIt = ((HashSet)_allInstsSet.clone()).iterator(); 
         vIt.hasNext();) {
      InstructionObject instObj = (InstructionObject) vIt.next();
      //if it is a store to a modPrim primal operand
      if((Store.conforms(instObj.inst))&&
         (Store.getDestination(instObj.inst).getFullName().indexOf("modPrim")>=0)) {
      
        Operand in = Store.getValue(instObj.inst);
	if(allToDieSet.contains(in)) continue; //we don't need to consider
	                                       //instructions that killLSChainsRecursive
					       //has already determined should
                                               //die
	HashSet extraBlocks = new HashSet();
	//call killLSChainsRecursive to go down the chain, finding instructions
	//to die.  It returns whether the instruction was the end of the chain, 
	//which I want to keep alive, since the prolog needs this instruction to
	//transfer data to the loop kernal
	if(instObj.killLSChainsRecursive(extraBlocks, extraInsts, 
	                                 new HashSet()))
	  extraInsts.add(instObj.inst);
	//removeInsts(extraInsts);
	
	//save a set of operands to replace with the input of this instruction
	replacementMap.put(in, extraBlocks);
	allToDieSet.addAll(extraBlocks);
	//replaceOps(in, extraBlocks);
      
      }
    }
    //delete the instructions:
    removeInsts(extraInsts);
    //replace all the operands with the source:
    replaceOps(replacementMap, allToDieSet);
  
  }
  
  /**
  This was written to support killLSChains.  it replaces all the operands in a
  set with one operand, which killLSChains has determined is the source operand
  in a chain of loads and stores.
  */
  public void replaceOps(HashMap replacementMap, HashSet allToDieSet) {
    //for replacementMap
    //key = source operand
    //value = set of alias that should be replaced by key

    
    for (Iterator vIt = replacementMap.keySet().iterator(); 
         vIt.hasNext();) {
      Operand keeper = (Operand) vIt.next();
      //because of the way killLSChains goes through the list, it will sometimes
      //start in the middle of a chain of loads and stores and will not know
      //that the source it found when starting here is not the ultimate source.
      //That means that it will want to do extra replacements, where it will try
      //to replace operands with the operand used in the middle.  allToDieSet 
      //knows all the operands that will be replaced, however, and so by
      //checking if it contains an operand, we can know if this operand was from
      //the middle of the chain and not bother with the replacement.
      if(allToDieSet.contains(keeper)) continue;
      
      //foreach instruction, and foreach operand in the set of operands to 
      //replace, replace the operand with the source operand
      for (Iterator vIt2 = _allInstsSet.iterator(); 
           vIt2.hasNext();) {
	InstructionObject instObj = (InstructionObject) vIt2.next();
	for (Iterator vIt3 = ((HashSet)replacementMap.get(keeper)).iterator(); 
            vIt3.hasNext();) {
          Operand looser = (Operand) vIt3.next();
	  instObj.replaceOperand(looser, keeper);
	}
      }
    }
  }
  
  /**
  This method is no longer used.  It was written to do the same job as
  killLSChains, but didn't do it as well.  It also tried to kill the loads and
  stores to modPrim primal operands used in modulo scheduling.  I think it
  doesn't even work anymore at all, because from looking at it, it looks like I
  may have been in the middle of some change to it, when I had the idea to write
  killLSChains and didn't finish whatever that change was.  Anyway, if you feel
  inspired to play with it, here it is:
  */
  public void removeUnwantedPs() {
  
    HashMap replacements = new Has