instructionlist.java

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

	//ignore predicates when scheduling unless, ignorePredsNicht is true or 
	//one of the defs is a primal
	/*if(isAnOutPrimal() || GlobalOptions.doNotIgnorePreds) {
          BooleanEquation predTmp = inst.getPredicate();
	  if(predTmp != null) {
            LinkedList boolsTmp = predTmp.listBooleanOperands();
            for (Iterator itin = ((LinkedList)boolsTmp.clone()).iterator(); 
        	 itin.hasNext(); ) {
              op = (Operand)itin.next();
              _instIns.add(op);
            }
          }
	}*/
      }
      //_instIns.addAll(_cntrlIns);
      //save the flag:
      if(_instIns.size()==0)
        noIns = true;
      return _instIns;
    }
    
    /**
    this guy adds the predicate uses to the other uses and saves it to
    instInstAll.  For normal scheduling instIns is all that is necessary, but
    for adding loads and stores instInsAll is necessary
    */
    public HashSet getInstInsAll() {
      _instInsAll.addAll(getInstIns());
      
      //if(!(isAnOutPrimal() || GlobalOptions.doNotIgnorePreds)) {
        BooleanEquation predTmp = inst.getPredicate();
	if(predTmp != null) {
          LinkedList boolsTmp = predTmp.listBooleanOperands();
          for (Iterator itin = ((LinkedList)boolsTmp.clone()).iterator(); 
               itin.hasNext(); ) {
            Operand op = (Operand)itin.next();
            _instInsAll.add(op);
          }
        }
      //}
      return _instInsAll;
    }
    
    /**
    finds the set of all instruction definitions and sets the flag.  It also
    checks if any outputs are primal and sets that flag as well
    */
    public HashSet getInstOuts() {
      if(_instOuts.size()>0) 
        return _instOuts;
      else if(noOuts)
        return null;
      
      if(AStore.conforms(inst)) {
        _instOuts.add(AStore.getPrimalDestination(inst));
	_isAnOutPrimal = new Boolean(true);
      }
      else {
	_isAnOutPrimal = new Boolean(false);
	Operand op;
	int numDefs = inst.getNumberOfDefs();
	for(int i = 0; i < numDefs; i++) {
          op = inst.getOperand(i);
          if(op != null) {
            _instOuts.add(op);
            if(op.isPrimal())
              _isAnOutPrimal = new Boolean(true);
          }
	}
      }
      if(_instOuts.size()==0)
        noOuts = true;
      return _instOuts;
    }
        
    /**
    return if any outputs are primal.  if the Boolean flag == null, meaning it
    was never determined, then run getInstOuts, who will check if any are
    */
    public boolean isAnOutPrimal() {
      if(_isAnOutPrimal == null)
        getInstOuts();
      return _isAnOutPrimal.booleanValue();
    }

    /**
      return whether or not an instruction has any successors
    */
    public boolean getNoSuccs() {
      if(_noSuccs == null)
        getListOfSuccs();
      return _noSuccs.booleanValue();
    }
    
    /**
      return whether or not an instruction has any predecessors
    */
    public boolean getNoPreds() {
      if(_noPreds == null)
        getListOfPreds();
      return _noPreds.booleanValue();
    }
    
    /**
    using the dependence flow graph create a list of predecessor instructions. 
    If this is used by other schedulers it might be useful or even necessary to
    look at uses and defs instead of the dependence flow graph if the dependence
    flow graph is undefined to determine this.
    */
    public ArrayList getListOfPreds() {
      if(_listOfPreds.size()>0) {
        return _listOfPreds;
      }
      else if((_noPreds!=null)&&(_noPreds.booleanValue()))
        return null;
      
      DependenceFlowNode childNode = _dfgI.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;
	InstructionObject pObj = (InstructionObject)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 void resetSuccsList() {
      _listOfSuccs = null;
      _noSuccs=null;
      _instIns=null;
      _instInsAll=null;
      noIns = false;
      _instOuts=null;
      noOuts = false;
      _isAnOutPrimal = null;
      _listOfPreds = null;
      _noPreds = null;
      
    }
    
    public ArrayList getSuccsForDFG(){
      ArrayList listOfSuccs = new ArrayList();
      for (Iterator it1 = getInstOuts().iterator(); it1.hasNext();) {
        Operand out = (Operand)it1.next();
        for (Iterator it2 = getInstSet().iterator(); it2.hasNext();) {
	  InstructionObject cObj = (InstructionObject)it2.next();
          if((!((Getelementptr.conforms(cObj.inst))&&
        	(AStore.conforms(inst))))) {

            boolean stop = false;
	    for (Iterator it3 = cObj.getInstIns().iterator(); 
	          it3.hasNext() && !stop;) {
              Operand op = (Operand)it3.next();
	      if(op.toString().compareTo(out.toString()) == 0) {
	        stop = true;
        	listOfSuccs.add(cObj);
              }
            }
          }
        }
      }
      return listOfSuccs;
    
    }
    /**
    using the dependence flow graph create a list of successor instructions. 
    */
    public ArrayList getListOfSuccs() {
      if(_listOfSuccs.size()>0)
        return _listOfSuccs;
      else if((_noSuccs!=null)&&(_noSuccs.booleanValue()))
        return null;
      
	DependenceFlowNode parentNode = _dfgI.findNode(inst);
	for (Iterator it1 = parentNode.getOutEdges().iterator(); 
        	it1.hasNext();) {
          DependenceFlowEdge cEdge = (DependenceFlowEdge)it1.next();
          DependenceFlowNode cNode = (DependenceFlowNode)cEdge.getSink();
          Instruction cInst = cNode.getInstruction();
	  if(cInst == null) continue;
	  InstructionObject cObj = (InstructionObject)instToObjMap.get(cInst);
	  _listOfSuccs.add(cObj); 
	}
	if(_listOfSuccs.size()==0) _noSuccs = new Boolean(true);
	else _noSuccs = new Boolean(false);
	return _listOfSuccs;
      /*}
      else {
	for (Iterator it1 = getInstOuts().iterator(); it1.hasNext();) {
          Operand out = (Operand)it1.next();
	  for (Iterator it2 = getInstSet().iterator(); it2.hasNext();) {
            InstructionObject cObj = (InstructionObject)it2.next();
	    if((!((Getelementptr.conforms(cObj.inst))&&
	          (AStore.conforms(inst))))) {

	      for (Iterator it3 = cObj.getInstIns().iterator(); it3.hasNext();) {
                Operand op = (Operand)it3.next();
	        if(op.toString().compareTo(out.toString()) == 0) {
	           _listOfSuccs.add(cObj);
	        }
	      }
	    }
	  }
        }
	if(_listOfSuccs.size()==0) _noSuccs = new Boolean(true);
	else _noSuccs = new Boolean(false);
	return _listOfSuccs;
      }*/
    }

    /**
    this is a fun little method, which is mostly useful for modulo scheduling,
    but might be useful for other schedulers or even anything else.  It looks
    for chains of loads and stores through a block and deletes them all and
    changes all instructions who use any block variables defined somewhere in
    the chain so that they use the source block variable.  I wrote this, because
    the unrolled loop bodies created after modulo scheduling and used to create
    the epilog and prolog, contain long chains of loads and stores.  Not only
    are they unnecessary and wasteful uses of space, they would even cause
    incorrect execution, because these loads could use values set in the kernal
    instead of within the epilog or it could mix up values from different
    iterations (and even in the prolog and epilog there are multiple
    iterations running concurrently). 
    */
    public boolean killLSChainsRecursive(HashSet extraBlocks, 
                                         HashSet extraInsts,
                                         HashSet alreadyVisited) {    
      //if(!getNoSuccs()) {
        boolean isNotLeaf = false;
	//foreach of an instructions successors
	//for (Iterator vIt = getSuccsForDFG().iterator(); 
        //     vIt.hasNext();) {
	
        for (Iterator it2 = getInstSet().iterator(); it2.hasNext();) {
          InstructionObject childObj = (InstructionObject)it2.next();
	  if(childObj == null) continue;
          if((!((Getelementptr.conforms(childObj.inst))&&
        	(AStore.conforms(inst))))) {

            //boolean stop = false;
	    boolean isChild = false;
	    for (Iterator it1 = getInstOuts().iterator(); 
                   it1.hasNext() && !isChild;) {
              Operand out = (Operand)it1.next();
	      for (Iterator it3 = childObj.getInstIns().iterator(); 
	    	    it3.hasNext() && !isChild;) {
                Operand op = (Operand)it3.next();

	        if(op.toString().compareTo(out.toString()) == 0) {
	          isChild = true;
                }
              }
	    }
	    //InstructionObject childObj = (InstructionObject) vIt.next();
	    //to prevent getting caught in an infinite loop, we must take care not
	    //to go into an instruction again:
	    if(isChild) {
	      if(alreadyVisited.contains(childObj)) continue;
	      alreadyVisited.add(childObj);
	      //if this is a load or store:
	      if((Store.conforms(childObj.inst))||
	         (Load.conforms(childObj.inst))) {
		Operand primal = null;
		Operand opToDie = null;
		if(Store.conforms(childObj.inst)) {
		  primal = Store.getDestination(childObj.inst);
		}
		if(Load.conforms(childObj.inst)) {
		  primal = Load.getSource(childObj.inst);
		  opToDie = Load.getResult(childObj.inst);
		}

		if(primal.getFullName().indexOf("modPrim")>=0) {
		  isNotLeaf = true;
		  //save the intermidiate block variables so they can be replaced
		  //later:
		  if(opToDie != null)
	            extraBlocks.add(opToDie);
		  //if the child is a not a leaf (which killLSChainsRecursive
		  //returns) or if the child is a load, save this instruction for
		  //deletion:
		  if((childObj.killLSChainsRecursive(extraBlocks, extraInsts,
	                                            alreadyVisited))||
		     (Load.conforms(childObj.inst)))
	            extraInsts.add(childObj.inst);
		}
	      }
	    }
          }
        }
	//}
	//an instruction is a leaf if it is the final load or store in the chain
	//we don't want to delete the final store (if the final node is a store
	//and not a load), because the prolog still needs to save these values
	//for priming the kernal (and the epilog will kill any extra modPrim
	//stores later)
	return isNotLeaf;
      //}
      //return false;
    
    }
    
    /**
    this method checks to see if any of its definitions happens to be used in a
    predicate, and saves that to its list of defined predicates
    */
    public void updatePredLists() {
    
      int numDefs = inst.getNumberOfDefs();
      for(int i = 0; i < numDefs; i++) {
        Operand op = inst.getOperand(i);
	if(_usedPredOperands.contains(op))
	  listOfPredsDefnd.add(op);
      }
    }
    
    /**
    the next two methods have been retired and the two after them are used
    instead.  The problem is, if you make a copy of an object from within one
    InstructionList and save that in a second, the objects use the global
    private variables from the original, source InstructionList object instead
    of the new one.
    */
    public InstructionObject copySaveOps() {
      
      //Instruction instOld = inst;
      Instruction instCpy = inst.copySaveOps();
      InstructionObject instObjCpy = new InstructionObject(instCpy);
      instObjCpy.listOfPredsDefnd = listOfPredsDefnd;
      instObjCpy.listOfPredsUsed = listOfPredsUsed;
      BooleanEquation instBoolEQCopy = inst.getPredicate();
      instCpy.setPredicate(instBoolEQCopy);
      instObjCpy.setItPred(_iterationPred);
      
      return instObjCpy;
    
    }
  
    /**
    retired, but left in case some other use pops up...
    */
    public InstructionObject copyNewOps() {
      
      
      InstructionObject instObjCpy = copySaveOps();
      instObjCpy.newOps();
      
      return instObjCpy;
    
    }
    
    
    /**
    This method is used to create a copy of "this" instruction object.  The copy
    has the same Operands (not only the same name, but the same objects)
    */
    public void copySaveOps(InstructionObject instObj) {
      
      //Instruction instOld = inst;
      //Instruction instCpy = instObj.inst.copySaveOps();
      
      //copy instruction
      inst = instObj.inst.copySaveOps();
      
      //InstructionObject instObjCpy = new InstructionObject(instCpy);
      
      //copy pred use and def lists:
      listOfPredsDefnd = instObj.listOfPredsDefnd;
      listOfPredsUsed = instObj.listOfPredsUsed;
      
      //copy instruction predicate:
      BooleanEquation instBoolEQCopy = instObj.inst.getPredicate();
      inst.setPredicate(instBoolEQCopy);