mschedhash.java

来自「一种将c高级语言转化给VHDL的编译器」· Java 代码 · 共 1,684 行 · 第 1/5 页

/*
 *
 LA-CC 05-135 Trident 0.7.1

Copyright Notice
Copyright 2006 (c) the Regents of the University of California.

This Software was produced under a U.S. Government contract
(W-7405-ENG-36) by Los Alamos National Laboratory, which is operated
by the University of California for the U.S. Department of Energy. The
U.S. Government is licensed to use, reproduce, and distribute this
Software. Permission is granted to the public to copy and use this
Software without charge, provided that this Notice and any statement
of authorship are reproduced on all copies. Neither the Government nor
the University makes any warranty, express or implied, or assumes any
liability or responsibility for the user of this Software.


 */


package fp.flowgraph;

import java.util.*;
import fp.util.*;
import java.io.*;
import java.lang.Math;

import fp.hardware.*;
import fp.graph.*;
import fp.passes.*;
import fp.*;


/** This class contains most of the guts of the modulo scheduler.  The 
 *  comments in here are mostly on the parts that are designed by me to do
 *  edits or something.  To learn more about modulo scheduling itself,
 *  please read Rau's papers.  This guy works with ModSched.java and 
 *  extends InstructionList.  InstructionList extends HashMap and contains
 *  many methods useful for editing a scheduled list of instructions.  It
 *  also saves the schedule itself, in that the key is the schedule time
 *  and the values are HashSets of all the instructions at that time.  
 *  MSchedHash extends InstructionList and contains Modulo Scheduling 
 *  specific methods.  InstructionList contains a nested class called
 *  InstructionObject, which saves instructions, some stuff for them, and
 *  useful methods for dealing with individual instructions.  MSchedHash
 *  uses MSchedInstObjects, which extend InstructionObjects, and contain
 *  Modulo Scheduling specific instruction editing methods as well as some
 *  implementations for part of the modulo scheduling algorithm.
 * 
 * @author Kris Peterson
 */
public class MSchedHash extends InstructionList
{

  /**
  * This nested class saves instruction data, and modulo scheduling
  * methods for editing individual instructions
  */
  public class MSchedInstObject extends InstructionObject {
  
    
    //public Instruction inst;
    /**
    schedule time
    */
    public float startTime = -1;
    /**
    previous schedule time
    */
    public float oldStartTime = -1;      
    //private ArrayList _listOfSuccs = new ArrayList();
    //private Boolean _noSuccs = null;
    //private ArrayList _listOfPreds = new ArrayList();
    //private Boolean _noPreds = null;
    /**
    number of iterations separating two instructions (0 means they are in
    the same iteration and 1 means that one is executed one iteration later)
    */
    private HashMap _distances = new HashMap();
    /**
    the earliest legal start time for an instruction as determined based on
    the scheduled times for its immediate scheduled predecessors
    */
    private float _estart = -1;
    /**
    the execution time if the loop were unrolled
    */
    public float unrollSt = -1;
    /**
    the earliest possible number of iterations of the modulo scheduled block
    before the loop would reach this instruction (this corresponds to estart
    and not the actual schedule time)
    */
    private int _eIICnt = -1;
    /**
    the number iterations of the modulo scheduled block
    before the loop would reach this instruction
    */
    private int _iiCnt = -1;
    //public float pStTime = 999;
    //private float _unrollEstart = -1;
    //private HashSet _cntrlIns = new HashSet();
    //public HashSet badParents = new HashSet();
    /**
    when a legal schedule slot has not been found, choose one randomly, but
    not in places that have already been tried.  This HashSet saves those
    who have been tried
    */
    private HashSet _triedTimes = new HashSet();
    
    /**
    constructor--this one is never used
    */
    public MSchedInstObject() {
      super();
    }
    
    /**
    constructor--saves the instructions associated with this object.  
    */
    public MSchedInstObject(Instruction i) {
      //save instruction to an InstructionObject variable
      super(i);
    }
    
    /*public boolean getNoSuccs() {
      if(_noSuccs == null)
        getListOfSuccs();
      return _noSuccs.booleanValue();
    }
    
    public boolean getNoPreds() {
      if(_noPreds == null)
        getListOfPreds();
      return _noPreds.booleanValue();
    }*/
    
    
    
    /*public ArrayList getListOfPreds() {
      if(_listOfPreds.size()>0)
        return _listOfPreds;
      else if((_noPreds!=null)&&(_noPreds.booleanValue()))
        return null;
      
      DependenceFlowNode childNode = _dfg.findNode(inst);
      for (Iterator it1 = ((Set)(childNode.getInEdges())).iterator(); 
              it1.hasNext();) {
        DependenceFlowEdge pEdge = (DependenceFlowEdge)it1.next();
        DependenceFlowNode pNode = (DependenceFlowNode)pEdge.getSource();
        Instruction pInst = pNode.getInstruction();
	if(pInst == null)  continue;
	MSchedInstObject pObj = (MSchedInstObject)instToObjMap.get(pInst);
	//if(pEdge instanceof DependenceCntrlFlowEdge)
	//  _cntrlIns.addAll(pObj.getInstOuts());
	_listOfPreds.add(pObj); 
      }
      if(_listOfPreds.size()==0) _noPreds = new Boolean(true);
      else _noPreds = new Boolean(false);
      return _listOfPreds;
    }
  
    public ArrayList getListOfSuccs() {
      if(_listOfSuccs.size()>0)
        return _listOfSuccs;
      else if((_noSuccs!=null)&&(_noSuccs.booleanValue()))
        return null;
      
      DependenceFlowNode parentNode = _dfg.findNode(inst);
      for (Iterator it1 = parentNode.getOutEdges().iterator(); 
              it1.hasNext();) {
        DependenceFlowEdge cEdge = (DependenceFlowEdge)it1.next();
        DependenceFlowNode cNode = (DependenceFlowNode)cEdge.getSink();
        Instruction cInst = cNode.getInstruction();
	MSchedInstObject cObj = (MSchedInstObject)instToObjMap.get(cInst);
	if(cInst == null) continue;
	//if(!((cEdge.getisBackWardsPointing())&&
	//     (cEdge instanceof DependenceCntrlFlowEdge)))
	if(!cEdge.getisBackWardsPointing())
	  _distances.put(cInst, new Integer(0));
	else if((_distances.get(cInst) == null)||
	       (((Integer)_distances.get(cInst)).intValue() != 0)) 
	  _distances.put(cInst, new Integer(1));
	_listOfSuccs.add(cObj); 
      }
      if(_listOfSuccs.size()==0) _noSuccs = new Boolean(true);
      else _noSuccs = new Boolean(false);
      return _listOfSuccs;
    }*/
    
    /**
    this method determines the "distance" or number of iterations separating
    this instruction and its child instruction.  
    */
    public int getDistance(Instruction childInst) {
    
      //check if it has already been determined
      if(!_distances.containsKey(childInst)) {
	//if not, find both instructions in the dependence flow graph
	DependenceFlowNode parentNode = _dfg.findNode(inst);
	DependenceFlowNode childNode = _dfg.findNode(childInst);
	//for each out edge from the parent:
	for (Iterator it1 = parentNode.getOutEdges().iterator(); 
        	it1.hasNext();) {
          DependenceFlowEdge cEdge = (DependenceFlowEdge)it1.next();
          DependenceFlowNode cNode = (DependenceFlowNode)cEdge.getSink();
	  if(childNode != cNode) continue;
          //if the edge connects the two instructions
	  Instruction cInst = cNode.getInstruction();
	  if(cInst == null) continue;
	  //if at least one connecting edge is not recursive set the 
	  //distance to 0, and otherwise to 1 and save in the hashmap
	  //"_disntances"
	  if(!cEdge.getisBackWardsPointing())
	    _distances.put(cInst, new Integer(0));
	  else if((_distances.get(cInst) == null)||
		 (((Integer)_distances.get(cInst)).intValue() != 0)) 
	    _distances.put(cInst, new Integer(1));
	}
      }
      //return the distance
      return  ((Integer)_distances.get(childInst)).intValue();
    
    }
    
    /**
    see Rau's papers for more.  The effective delay is equal to the
    real delay (i.e. the latency of an instruction) - the distance between
    parent and child times ii.  
    */
    public float getEffectiveDelay(Instruction childInst, int ii) {
      float effDelay = getRunLength() - getDistance(childInst) * ii;
      return effDelay;
    }
    
    /**
    Please read Rau's paper for more on this.  This is one of the main
    methods from modulo scheduling.  Its purpose is to determine the
    earliest possible start time for an instruction based on the finish
    times of all its immidiate, scheduled predecessors.  This is legal
    because the immidiate predecessors should have been scheduled correctly
    based on their predecessors, because problems with successors will be
    handled later, and because if any problems occur later with other non
    scheduled predecessors, this instruction will be unscheduled and
    rescheduled at the time that predecessor is scheduled (that is, when I
    say "the time..." I don't mean the cycle that the other instruction was
    scheduled at, but rather the moment in Trident's runtime that it
    considers the other instruction it will also see this guy and unschedule
    him).  
    */
    public void estart(int ii) {

      float estartTmp = -9999;
      float unrollEstartTmp = -9999;
      //int unrollEII = -9999;
      //for each immidiate predecessor:
      if(getListOfPreds()==null) _eIICnt=0;
      else {
	for (Iterator it1 = getListOfPreds().iterator(); 
        	  it1.hasNext();) {
	  MSchedInstObject pObj = (MSchedInstObject)it1.next();

	  float execTime = 0;
	  float unrollExecTime = 0;
	  //float unrollII = 0;

	  //if the parent is scheduled, find the effective end time for that
	  //instruction, which is its start time plus its effective delay:
	  if(pObj.startTime >= 0)
	    execTime = Math.max(0, pObj.startTime +
	                           pObj.getEffectiveDelay(this.inst, ii));
	  //save the max from all parents:
	  estartTmp = Math.max(estartTmp, execTime);
	  //get the unroll start time, similarly, except use the parent's
	  //unrolled start time plus its full latency if the distance is 0
	  //and 0 if the distance is 1 (if they are in different iterations
	  //we don't care where they are with respect to each other in the 
	  //unrolled schedule since the parent should be near the end of the 
	  //unrolled loop body and the child near the beginning
	  if(pObj.unrollSt >= 0) {
	    if(pObj.getDistance(inst)==0)
	      unrollExecTime = Math.max(0, pObj.getRunLength() + pObj.unrollSt);
	    else {
	      unrollExecTime = 0;
	      //pStTime = Math.min(pStTime, pObj.startTime);
	      //badParents.add(pObj);
	    }
          }
	  //save the max unroll time:
	  unrollEstartTmp = Math.max(unrollEstartTmp, unrollExecTime);
	}

	//save the max parent stop time, to this instruction's _estart private
	//variable
	_estart = estartTmp;
	//set the earliest number of iterations of the modulo scheduled block
	//before this executes to the unrolled time divided by ii-1 
	//(remember, the modulo scheduled block contains different parts of
	//the unrolled loop body and for data to travel through from the start
	//to this instruction, it must pass through the number of iterations
	//of the modulo scheduled body that would execute in the time it 
	//would take for the data to get to this instruction in the unrolled 
	//loop):
	_eIICnt = (int)(unrollEstartTmp/(ii));
      }
    }

    /**
    Please also refer ro Rau's paper for more on this. Once an estart has 
    been found, a schedule time must be found.  This time depends on several
    factors.  The factor Rau mentions is hardware conflichts.  But in
    Trident there are a few other factors that must be considered when
    finding a legal schedule time.  One is that, pipelined instructions must
    always start on even clock edges, and non-piplined instructions cannot
    run over a clock boundary.  The second Trident-specific issue is that
    for data to pass between different iterations of the modulo scheduled
    block, it must be saved and read from a register, and time for these
    loads and stores must be inserted into the block.
    */
    public float findTimeSlot(int ii) {
      //this class is for correcting start times for instructions so that
      //pipelined instructions start on even clock edges and non-pipelined
      //instructions don't run over a boundary:
      CorrectStartTimes adjustTimes = new CorrectStartTimes(inst, _chipdef,
							    !GlobalOptions.packInstructions);
    
      //Loads and store instructions must be handled differently.  The
      //problem is that if a store to a register occurs in the same cycle
      //as a read from that same register, the synthesis part of Trident
      //will try to optimize things by connecting instructions using the
      //load to the same wire that was used in the store and will remove 
      //the load instruction. This causes timing problems because
      //instructions will use values, which would have been stored 
      //in the register and read one iteration later, too early--one 
      //iteration  the modulo scheduled block too early.  This means that, 
      //for example, if you had the c code: