fdschedule.java

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

  	 
  	 
  	if(!(printOutVarName)) {
  	  float minTime = ((Float)windowMin.get(instr)).floatValue();
  	  float maxTime = ((Float)windowMax.get(instr)).floatValue();
  	  if((n_int>=minTime)&&(n_int<=maxTime))
  	    ((ArrayList)(depthInfo.get(instr))).set(1, " * |"); 
  	  else
  	    ((ArrayList)(depthInfo.get(instr))).set(1, " # |"); 
  	}
  	else {
  	  ((ArrayList)(depthInfo.get(instr))).set(1, (((ArrayList) defLists
        				   .get(instr)).toString() + " |"));
  	}
      }
    } //end foreach
    
  }
  /** This methode was written for helping to debug the force directed 
   *  scheduler.  It takes the list of instructions, @param instrlist, and 
   *  saves text representing the possible execution window for each 
   *  instruction.  This execution window is initialized with the ASAP 
   *  scheduled time as the minimum possible time for the Force-directed 
   *  scheduler to schedule an instruction, and with the ALAP as the maximum 
   *  possible.  This method goes recursively up through the instruction 
   *  hierarchy determining analyzing to know how to print.
   * 
   * @param instrlist list of instructions from hyperblock, which the 
   *	 force-directed scheduler is working on
   * @param parentInstr the starting instruction, from which this    
   *	  recursive algorithm should attempt to go down from through the    
   *	  dependence hierarchy
   * @param useLists a hashmap saving a list of all operands being   
   *	  used for a given instruction (key=instruction; value=list of used 
   *	  operands)
   * @param defLists a hashmap saving a list of all operands being   
   *	  defined by a given instruction (key=instruction; value=list of    
   *	  defined operands)
   * @param windowMax a hashmap saving the upper limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  upper limit
   * @param windowMin a hashmap saving the lower limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  lower limit
   * @param n_int time step, which for which information is currently
   *	  being printed
   * @param printOutVarName a boolean variable telling how to print  
   *	  the output operand
   * @param depthInfo a hashmap saving text representing the	     
   *	  execution windows for each instruction
   * @param depth a hashmap saving text representing the  execution  
   *	  windows for each instruction
   */
  public void printSucessorWindows(ArrayList instrlist, 
  				   Instruction parentInstr, HashMap useLists, 
        			   HashMap defLists, HashMap windowMax, 
        			   HashMap windowMin, int n_int, 
        			   boolean printOutVarName, HashMap depthInfo, 
        			   int depth) {
    for (Iterator it = ((ArrayList)instrlist).iterator(); it.hasNext(); ) {
      Instruction instr = (Instruction)it.next();   
      if((isInstrPred((ArrayList) useLists.get(instr), (ArrayList) defLists
               .get(parentInstr)))&&
          (areOutsNotPrimals((ArrayList) useLists.get(instr)))) {
  	depth++;
  	if(!(depthInfo.containsKey(instr))) {
  	  depthInfo.put(instr, new ArrayList());
  	  ((ArrayList)(depthInfo.get(instr))).add(new Integer(depth));
  	  ((ArrayList)(depthInfo.get(instr))).add("");
  	}
  	else
  	  if(depth >  ((Integer)(((ArrayList)(depthInfo.get(instr))).get(0)))
        	       .intValue())
  	    ((ArrayList)(depthInfo.get(instr))).set(0, new Integer(depth));
  	if(!(printOutVarName)) {
  	  float minTime = ((Float)windowMin.get(instr)).floatValue();
  	  float maxTime = ((Float)windowMax.get(instr)).floatValue();
  	  if((n_int>=minTime)&&(n_int<=maxTime))
  	    ((ArrayList)(depthInfo.get(instr))).set(1, " * |"); 
  	  else
  	    ((ArrayList)(depthInfo.get(instr))).set(1, " # |"); 
  	}
  	else {
  	  ((ArrayList)(depthInfo.get(instr))).set(1, (((ArrayList) 
        			   defLists.get(instr)).toString() + " |"));
  	}
  	printSucessorWindows(instrlist, instr, useLists, defLists, 
        		     windowMax, windowMin, n_int, printOutVarName, 
        		     depthInfo, depth);
  	 
  	 
      }
    } //end foreach
    
  }
  
  private class _Conns extends HashMap {
  
    private HashMap _instrToNodeMap = new HashMap();
    _Conns() {
    
    }
    
    public Boolean get(Instruction parentInstr, Instruction childInstr) {
      if(_dfg == null) return new Boolean(true);
      
      if(!this.containsKey(parentInstr))
        this.put(parentInstr, new HashMap());
      HashMap destMap = (HashMap)this.get(parentInstr);
      if(destMap.containsKey(childInstr))
        return (Boolean)destMap.get(childInstr);
      DependenceFlowNode parentNode = null;
      if(!_instrToNodeMap.containsKey(parentInstr)) {
        parentNode = _dfg.findNode(parentInstr);
	_instrToNodeMap.put(parentInstr, parentNode);
      }
      else
        parentNode = (DependenceFlowNode)_instrToNodeMap.get(parentInstr);
      DependenceFlowNode childNode = null;
      if(!_instrToNodeMap.containsKey(childInstr)) {
        childNode = _dfg.findNode(childInstr);
	_instrToNodeMap.put(childInstr, childNode);
      }
      else
        childNode = (DependenceFlowNode)_instrToNodeMap.get(childInstr);
      DependenceFlowEdge conn = (DependenceFlowEdge)_dfg.findEdge(parentNode, childNode);
      if(conn !=null && !conn.getisBackWardsPointing() && 
        (conn instanceof DependenceDataFlowEdge)) {
        destMap.put(childInstr, new Boolean(true));
	return new Boolean(true);
      }
      else
      {
	destMap.put(childInstr, new Boolean(false));
	return new Boolean(false);
      }
    }
  
  }
  
  public boolean isParentOf(Instruction parentInstr, Instruction childInstr, 
                            HashMap defLists) {
    if((_connectionCalculator.get(parentInstr, childInstr).booleanValue()) && 
       areOutsNotPrimals((ArrayList) defLists.get(parentInstr))) {
      //System.out.println("parentInstr " + parentInstr + " is parent of ");
      //System.out.println("childInstr " + childInstr);
      return true;
    }
    else
      return false;
  }
  
  //end debug methods
  //where setWindowSuccessors is
  /** This method goes down recursively through the hierarchy of instructions,
   *  resizing their execution windows by resetting their minimum execution 
   *  time.  This is performed after an instruction has been scheduled.  Its 
   *  successor instructions can now, no longer be executed any sooner than 
   *  this just scheduled instruction has completed execution.
   * 
   * @param instrlist list of instructions from hyperblock, whcih the 
   *	 force-directed scheduler is working on
   * @param parentInstr the starting instruction, from which this    
   *	  recursive algorithm should attempt to go down from through the    
   *	  dependence hierarchy
   * @param useLists a hashmap saving a list of all operands being   
   *	  used for a given instruction (key=instruction; value=list of used 
   *	  operands)
   * @param defLists a hashmap saving a list of all operands being   
   *	  defined by a given instruction (key=instruction; value=list of    
   *	  defined operands)
   * @param windowMin a hashmap saving the lower limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  lower limit
   * @param execTime a new minimum execution time for this	     
   *	  instruction.  It is determined after scheduling a predecessor
   * @param chipDef contains chip and board information such as     
   *	  where    arrays have been stored to memory and the availability of
   *	  hardware.
   */
  public boolean setWindowSuccessors(ArrayList instrlist, 
  				  Instruction parentInstr, HashMap useLists, 
        			  HashMap defLists, FDWindows windowMap, 
  				  float execTime, ChipDef chipDef) {
    //foreach sucessor
    for (Iterator it = ((ArrayList)instrlist).iterator(); it.hasNext(); ) {
      Instruction instr = (Instruction)it.next();   
      
      //if(instr predecessor of above instr && new min > this instruction's old min)
     //if((isInstrPred((ArrayList) useLists.get(instr), (ArrayList) 
     //   				      defLists.get(parentInstr)))&&
     //   				      (((areOutsNotPrimals((ArrayList) 
     //   				      useLists.get(instr)))&&
	//				      (Load.conforms(instr)))||
	//				      (!Load.conforms(instr)))) {
      /*DependenceFlowNode parentNode = _dfg.findNode(parentInstr);
      DependenceFlowNode node = _dfg.findNode(instr);
      DependenceFlowEdge conn = (DependenceFlowEdge)_dfg.findEdge(parentNode, node);
      if(conn !=null && !conn.getisBackWardsPointing() && 
         (conn instanceof DependenceDataFlowEdge) &&
	 (areOutsNotPrimals((ArrayList) useLists.get(instr)))){*/
      if(isParentOf(parentInstr, instr, defLists)) {	
        //if(n_int + instruction execution time > old min)
  	if(execTime > windowMap.getMin(instr)) {
  	  //setwindow(sucessor, n_int + instruction execution time, oldmax)
          execTime = ((float)Math.round(execTime * _schedCycleFraction))/_schedCycleFraction;
	    //throw new ScheduleException("Error: Failed to create a valid Forc" +
	    //                             "e-Directed" + " Schedule");
	    
	  if(execTime > windowMap.getMax(instr)) {
	   /* System.out.println("failed setWindowSuccessors on instr " + instr);
	    System.out.println("execTime " + execTime);
	    System.out.println("windowMap.getMax(instr) " + windowMap.getMax(instr));
	    System.out.println("windowMap.getMin(instr) " + windowMap.getMin(instr));*/
	    return false;
	  }
	  windowMap.putMin(instr, execTime);
  	  if(!setWindowSuccessors(instrlist, instr, useLists, defLists, windowMap, 
        		          execTime + getInstrRunLength(instr, chipDef) /*+
			           (1/_schedCycleFraction)*/, 
            		          chipDef))
            return false;
  	}
  	 
      }
    } //end foreach
    return true;
  }	
  //and where setWindowPredecessors is
  /** This method goes up recursively through the hierarchy of instructions, 
   *  resizing their execution windows by resetting their maximum execution 
   *  time.  This is performed after an instruction has been scheduled.  Its 
   *  predecessor instructions can now, no longer be executed any later than 
   *  this just scheduled instruction has started.
   * 
   * @param instrlist list of instructions from hyperblock, whcih the 
   *	 force-directed scheduler is working on
   * @param childInstr the starting instruction, from which this     
   *	  recursive algorithm should attempt to go up from through the      
   *	  dependence hierarchy
   * @param useLists a hashmap saving a list of all operands being   
   *	  used for a given instruction (key=instruction; value=list of used 
   *	  operands)
   * @param defLists a hashmap saving a list of all operands being   
   *	  defined by a given instruction (key=instruction; value=list of    
   *	  defined operands)
   * @param windowMax a hashmap saving the upper limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  upper limit
   * @param execTime a new minimum execution time for this	     
   *	  instruction.  It is determined after scheduling a predecessor
   * @param chipDef contains chip and board information such as     
   *	  where    arrays have been stored to memory and the availability of
   *	  hardware.
   */
  public boolean setWindowPredecessors(ArrayList instrlist, 
  				    Instruction childInstr, HashMap useLists, 
        			    HashMap defLists, FDWindows windowMap, 
  				    float execTime, ChipDef chipDef) {
    //foreach sucessor
    for (Iterator it = ((ArrayList)instrlist).iterator(); it.hasNext(); ) {
      Instruction instr = (Instruction)it.next();   
      
      
      //if((isInstrPred((ArrayList) useLists.get(childInstr), (ArrayList) 
      //  		defLists.get(instr)))&&
      //  		(areOutsNotPrimals((ArrayList) defLists.get(instr)))){
      /*DependenceFlowNode childNode = _dfg.findNode(childInstr);
      DependenceFlowNode node = _dfg.findNode(instr);
      DependenceFlowEdge conn = (DependenceFlowEdge)_dfg.findEdge(node, childNode);
      if(conn !=null && !conn.getisBackWardsPointing() && 
         (conn instanceof DependenceDataFlowEdge) &&
	 (areOutsNotPrimals((ArrayList) useLists.get(childInstr)))) {*/
      if(isParentOf(instr, childInstr, defLists)) {	
        //if(n_int + instruction execution time < old max)
	
	if(execTime < windowMap.getMax(instr) 
        			       + getInstrRunLength(instr, chipDef)) {
  	  
	    //throw new ScheduleException("Error: Failed to create a valid Forc" +
	    //                             "e-Directed" + " Schedule");
	  //setwindow(sucessor, oldmin, n_int + instruction execution time)
          float execTimeNew = execTime - getInstrRunLength(instr, chipDef) /*-
	                      (1/_schedCycleFraction)*/;
          CorrectStartTimes adjustTimes 
	    = new CorrectStartTimes(instr, chipDef, !GlobalOptions.packInstructions);

	  float correctedCycle = adjustTimes.getCorrectedStartTime(execTimeNew);
	  if(correctedCycle > execTimeNew)
	    correctedCycle--;
  	  if((execTimeNew < windowMap.getMin(instr))) {
	    /*System.out.println("failed setWindowPredecessors on instr " + instr);
	    System.out.println("execTime " + execTime);
	    System.out.println("windowMap.getMax(instr) " + windowMap.getMax(instr));
	    System.out.println("windowMap.getMin(instr) " + windowMap.getMin(instr));*/
            return false;
	  }
          correctedCycle = ((float)Math.round(correctedCycle * _schedCycleFraction))/
			    _schedCycleFraction;
	  windowMap.putMax(instr, execTimeNew);
	  //setWindowPredecessors(list, n_int + instruction execution time)
  	  if(!setWindowPredecessors(instrlist, instr, useLists, defLists, 
        			    windowMap, execTimeNew, chipDef))
	    return false;
  	}
      }
    } //end foreach
    return true;
  }
   
  /** This method calculates forces acting on an instruction if it is placed 
   *  at a given time, as a result of later instructions in the hierarchy.
   * 
   * @param dG Weights as a result of other like operations (e.g. other add 
   *	 instructions) being executed or possibly being executed in tis time
   *	  step
   * @param instrlist list of instructions from hyperblock, whcih the
   *	  force-directed scheduler is working on
   * @param childInstr the starting instruction, from which this     
   *	  recursive algorithm should attempt to go up from through the      
   *	  dependence hierarchy
   * @param useLists a hashmap saving a list of all operands being   
   *	  used for a given instruction (key=instruction; value=list of used 
   *	  operands)
   * @param defLists a hashmap saving a list of all operands being   
   *	  defined by a given instruction (key=instruction; value=list of    
   *	  defined operands)
   * @param newMax ???
   * @param windowMin a hashmap saving the lower limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  lower limit
   * @param windowMax a hashmap saving the upper limit for scheduling
   *	  a given instruction (key=instruction; value=float value of the    
   *	  upper limit
   * @param sum a sum of all forces acting in a timeslot
   * @param CanCalc keine ahnung aber bestimmt gibt's ein Grund fuer 
   *	  ihm
   * @param chipDef contains chip and board information such as     
   *	  where    arrays have been stored to memory and the availability of
   *	  hardware.
   * @return some of forces due to predecessors
   */
  public float recursivePredecessorForces(HashMap dG, ArrayList instrlist, 
  					  Instruction childInstr, 
        				  HashMap useLists, HashMap defLists, 
  					  float newMax, FDWindows windowMap, 
        				  /*HashMap sum,*/ Boolean CanCalc, 
        				  ChipDef chipDef) {
    float predecessorForce = 0;
    //float sumtmp1 = 0;
    //foreach instruction
    float force = 0;
    for (Iterator it = ((ArrayList)instrlist).iterator(); it.hasNext(); ) {
      Instruction instr = (Instruction)it.next();   
      float timeMod = 1;
      if(getInstrRunLength(instr, chipDef) < 1)
	timeMod = _schedCycleFraction * _schedCycleFractionMod;