instructionlist.java

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

      //return instObjCpy;
      
      _iterationPred = instObj.getItPred();
    
    }
  
    /**
    copy "this" instruction object, but replace all the block operands with new
    ones.  This is used by the epilog because it has multiple iterations of the
    loop running it, all starting at different points (not starting at their
    beginning at different offsets of time, but starting at truly different 
    locations).  These different iterations need to use different block operands
    to prevent confusions and data transfer between interations that shouldn't
    occur.
    */
    public void copyNewOps(InstructionObject instObj) {
      
      
      copySaveOps(instObj);
      //System.err.println("b4 " + this);
      newOps();
      //System.err.println("this " + this);
      
      //return instObjCpy;
    
    }
    
    /**
    replaces operands with new ones.  But the new operands are saved so that
    when another instruction is found that uses the same operand, it will use
    the same newly created operand, instead of creating yet another and
    disconnecting them.
    */
    public void newOps() {
      
      Operand op;
      int total = inst.getNumberOfOperands();
      Operand newOp = null;
      for(int i = 0; i < total; i++) {
        op = inst.getOperand(i);
	
	//if an instruction has two operands of the same name they'll end up
	//getting replaced twice.  For example if we have the instruction:
	//%tmp_1 = aaa_mul %tmp_2 %tmp_2
	//during the first pass through it will see the first tmp_2 and make a
	//operand for it called tmp2_0, probably and then it will replace both
	//operands.  The instruction will now look like this:
	//%tmp_1 = aaa_mul %tmp_2_0 %tmp_2_0
	//but the loop will continue and it will look at the second tmp_2
	//variable, which now has the name tmp2_0.  It will think this is a new
	//operand and create yet another, probably called tmp_2_0_0 and replace
	//both again giving us this:
	//%tmp_1 = aaa_mul %tmp_2_0_0 %tmp_2_0_0
	//all other instructions using or defining tmp_2 will be using tmp_2_0
	//and this one will be unconnected.  To prevent this, I check if I've
	//already created this operand and if so skip to the next operand:
	if(_oldToNew.containsValue(op)) continue;
	newOp = null;
        /*if((op != null) && 
	  ((op.isBlock())||
	   ((op.isBoolean())&&(!_usedPredOperands.contains(op))))&&
	  (newOp != op)) {*/
        
	if(op != null) {
	  //if we've already created a new operand for this guy, use that
	  if(_oldToNew.containsKey(op))
	    newOp = (Operand)_oldToNew.get(op);
	  else {//otherwise create a new block or boolean as appropriate:
	    if(op.isBlock())
	      newOp = Operand.nextBlock(op.getFullName());
	    else if(op.isBoolean())
	      newOp = Operand.nextBoolean(op.getFullName());
	   _oldToNew.put(op, newOp);
	  }
	  if(newOp != null) //replace the operand (and since we only gave newOp
	                    //a value if op was a block or boolean, all other
			    //types of operands such as primals will not be 
			    //changed)
	    replaceOperand(op, newOp);
	}
      }
      //do the same in the predicate:
      newOp = null;
      BooleanEquation predTmp = inst.getPredicate();
      if(predTmp != null) {
        LinkedList boolsTmp = predTmp.listBooleanOperands();
        for (Iterator itin = ((LinkedList)boolsTmp.clone()).iterator(); 
             itin.hasNext(); ) {
          op = (Operand)itin.next();
          if(op != null) {
	    if(_oldToNew.containsKey(op))
	      newOp = (BooleanOperand)_oldToNew.get(op);
	    else {
	      newOp = Operand.nextBoolean(op.getFullName());
	     _oldToNew.put(op, newOp);
	    }
	    replaceOperand(op, newOp);
	  }
        }
      }
      if((_iterationPred != null)) {
	if(_oldToNew.containsKey(_iterationPred))
	  newOp = (Operand)_oldToNew.get(_iterationPred);
	else {//otherwise create a new block or boolean as appropriate:
	 newOp = Operand.nextBoolean(_iterationPred.getFullName());
	 _oldToNew.put(_iterationPred, newOp);
	}
        _iterationPred = newOp;
      }
    }
  
    /**
    replace an operand in an instruction, both within the instruction and its
    predicate.  This was written so that the listOfPredsUsed and defined could
    be edited.
    */
    public void replaceOperand(Operand oldOp, Operand newOp) {
      inst.replaceOperand(oldOp, newOp);
      if((oldOp.isBoolean())&&(newOp.isBoolean())) {
	BooleanEquation predTmp = (BooleanEquation)inst.getPredicate().clone();
	BooleanEquation neweq = new BooleanEquation(predTmp);
	neweq = predTmp.replaceBool((Bool)oldOp, (Bool)newOp);
	inst.setPredicate(neweq); 
	//_usedPredOperands.remove(oldOp);
	_usedPredOperands.add(newOp);
	listOfPredsUsed.remove(oldOp);
	listOfPredsUsed.add(newOp);
	changeItPred(oldOp, newOp);
      }
      updatePredLists();
      /*listOfPredsDefnd.remove(oldOp);
      listOfPredsUsed.remove(oldOp);
      listOfPredsDefnd.add(newOp);
      listOfPredsUsed.add(newOp);*/
      
    }

    /**
    return the latency of an instruction.  Once the latency has been found, it
    is saved to the private variable _runlength and in the future its value will
    be returned instead of recalculating the latency.  If the latency is an
    ALoad or AStore, the latency is found by checking in the chipdef hardware
    information class and otherwise it is found on the instruction itself
    */
    public float getRunLength() {
      if(_runlength != -1)
        return _runlength;
      
      float latency = 0;
      /*if((ALoad.conforms(inst))&&(_chipdef != null)) {
        Operand primSource = ALoad.getPrimalSource(inst);
        latency = _chipdef.getMemInitReadLat(primSource);
      }
      else if((AStore.conforms(inst))&&(_chipdef != null)) {
        Operand primDest = AStore.getPrimalDestination(inst);
        latency = _chipdef.getMemInitWriteLat(primDest);
      }
      else*/
        latency = inst.getRunLength();
	
      if(!GlobalOptions.packInstructions && latency < 1) latency=1;
      
      _runlength = latency;
      
      return latency;
      
      
    }
  
  }//end class InstructionObject
  
  /** Often I know the instruction I am interested in, but not its associated
  instruction object.  This nested class was written to help me find objects.  
  It extends HashMap where 
  keys = instruction
  values = instruction object
  */
  public class InstToObjMap extends HashMap {
  
    public InstToObjMap() {
      super();
    }
    
    /**
    Given an instruction i, this method returns the associated
    InstructionObject.  After searching through all InstructionObjects to find
    that one that is associated with i, it saves the relationship in THIS (since
    THIS is a hashmap) and in the future if the same instruction i is requested,
    the value in THIS is returned and another search is unnecessary.
    */
    public InstructionObject get(Instruction i) {
      //if instruction i is known, return its InstructionObject
      if(this.containsKey(i))
        return (InstructionObject)super.get(i);
      //else search through all Instruction objects for i, save i and return
      //that object
      for (Iterator vIt2 = _allInstsSet.iterator(); vIt2.hasNext();) {
        InstructionObject instObj = (InstructionObject) vIt2.next();
        Instruction inst = instObj.inst;
	this.put(inst, instObj);
	if(inst == i)
	  return instObj;
      }
      //hopefully it will never get to this statement:
      return (InstructionObject)super.get(i);
    }
    
  
  } //end class InstToObjMap
    
  /** This class was written, to deal with the problem with floating point
  numbers that 8.095 can become corrupted and become 8.0949999999.  Since I save
  my instructions in sets in a hashmap (InstructionList extends HashMap), where
  the key is the time and the value is the set of instructions in that time, if
  these corruptions are allowed we could have a instruction at 8.09499999, and
  one at 8.095, and one at 8.0950001, when we would want them all to be saved in
  the same time slot.  This method rounds all times to within 1/100th.
  */
  public class RoundTimeOff {
  
    
    public RoundTimeOff() {
    
    }
    
    public float roundTime(float t) {
      return ((float)Math.round(t*100))/100;
    }
  
  } //end RoundTimeOff
  
  /**
  This is an instantian of the instruction to InstructionObject mapper
  */
  public InstToObjMap instToObjMap = new InstToObjMap();
  /**
  To make it easier to access all InstructionObjects and to find individual
  objects, I created this private Set to contain copies of them all.  As I said,
  they are stored in InstructionList in sets associated with certain times, but
  to make it unnecessary to search through every set at every time, there is one
  set with them all.
  */
  private HashSet _allInstsSet = new HashSet();
  /**
  instatiation of the time rounding class
  */
  private RoundTimeOff _roundTimes = new RoundTimeOff();
  /**
  This is the lowest execution time of an insruction.  It is used by the 
  InstructionList copy functions
  */
  private float _minTime = 99999;
  /**
  This is the highest execution time of an insruction.  It is used by the 
  InstructionList copy functions
  */
  private float _maxTime = -99999;
  /**
  This set was created to help during creation of InstructionObjects to know
  what predicate operands are being used.  Knowing this list of all predicates
  used in the schedule, when one of these operands is defined in an
  InstructionObject, it can be noted that that definition is the definition of a
  predicate.
  */
  private HashSet _usedPredOperands = new HashSet();
  /**
  When using the InstructionObject "copyNewOps" method, to ensure that only one
  new operand is created for any existing operand and that all instances of the
  existing operand are all replaced with the same new operand, this hashmap was
  created to save which old operands are associated with which new operands.
  */
  static private HashMap _oldToNew = null;
  /**
  ASAP, ALAP, and modulo scheduling can get stuck in an infinite loop, trying to
  create longer and longer schedules, when in reality no schedule is possible. 
  To know when it is stuck in a loop, we just need to know the longest possible
  schedule, which would be when every instruction ran serially.  The time
  necessary for such a schedule is the sum of all latencies for all instructions
  in the list.  _maxRunTime saves this value after it is created when
  instructions are added to the list.
  */
  private float _maxRunTime = 0;

  /**
  this points the hardware description class instatiation
  */
  private ChipDef _chipdef = null;
  /**
  this points to a dependence flow graph for the hyperblock that is being
  scheduled
  */
  private DependenceFlowGraph _dfgI = null;
  /**
  this points to the hyperblock being scheduled
  */
  public BlockNode _node = null;
  //static private HashSet _usedPreds = new HashSet();
  
  public InstructionList() {
    super();
    _dfgI = null;
  }

  public InstructionList(ChipDef chipdef, float maxRunTime) {
    this();
    _chipdef = chipdef;
    _maxRunTime = maxRunTime;
  }

  public InstructionList(BlockNode bNode, ChipDef chipdef) {
    this();
    _chipdef = chipdef;
    _node = bNode;
    //read in instructions from a node:
    readInList(bNode);
  }
  
  public InstructionList(ChipDef chipdef, DependenceFlowGraph dfg) {
    this();
    _chipdef = chipdef;
    _dfgI = dfg;
  }
  
  /**
  if the dependence flow graph was unknown at the time when the InstructionList
  was instantiated, save it now
  */
  public void saveDFG(DependenceFlowGraph dfg) {
    _dfgI = dfg;
  
  }
  
  /**
  Instructions save their exection time.  If instructions have already been
  scheduled, this method can be called to place them in the correct time slots
  in InstructionList for their given execution times.
  */
  public void scheduleToExecTime() {
    ArrayList times = new ArrayList(this.keySet());
    sort(times);
    for (Iterator vIt = times.iterator(); vIt.hasNext();) {
      Float execTimeFl = (Float) vIt.next();
      float execTime = execTimeFl.floatValue();
      HashSet iList = getAllAtTime(execTime);
      for (Iterator vIt2 = ((HashSet)iList.clone()).iterator(); 
             vIt2.hasNext();) {
	InstructionObject instObj = (InstructionObject) vIt2.next();
	Instruction inst = instObj.inst;
	float newTime = inst.getExecTime();
	remove(execTime, instObj);
	put(newTime, instObj);
      }
    }
  }
  
  /**
  returns the certain maximum possible schedule length, which has been saved in
  _maxRunTime, after being calculated when the schedule was read in.
  */
  public float getMaxRunTime() { return _maxRunTime; }

  /**
  Since InstructionList extends HashMap, the easiest way to determine the number 
  of instructions in the InstructionList is to call "size" on the private
  hashset of all instructions
  */
  public int size() {
    return _allInstsSet.size();
  }
  
  /**
  this was written to adjust the min and max execution times given a certain
  execution time for an instruction
  */
  private void checkMinMaxTimes(float time) {
    _maxTime = Math.max(_maxTime, time); 
    _minTime = Math.min(_minTime, time); 
  }
  
   /**
  if the min or max time is unknown, go through the schedule and find it, save