muxtablegenerator.java

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

  public HashSet findModPrimSources(HashSet instSet) {
  
    HashSet instsToDelete = new HashSet();
    for (Iterator itin = instSet.iterator(); 
       itin.hasNext(); ) {
      Instruction inst = (Instruction)itin.next();
      if((Load.conforms(inst))&&
         (_opToElementMap.containsKey(Load.getResult(inst)))) {
	Operand op = Load.getResult(inst);
	//Element element = (Element)_opToElementMap.get(op);
	HashSet elements = (HashSet)_opToElementMap.get(op);
	PrimalOperand modPrim = (PrimalOperand)Load.getSource(inst);
        instsToDelete.add(inst);
	//save this modPrim's type:
	_modPrimToType.put(modPrim, inst.type());
	//tell the element that this iteration's output comes from this modprim:
	for (Iterator it2 = elements.iterator(); 
            it2.hasNext(); ) {
	  Element element = (Element)it2.next();
          element.modPrim = modPrim;
	}
      }
    }
    return instsToDelete;
  }
  
  /**
  This method saves all the inputs necessary for each mux tree.  It should be
  noted that MuxTableGenerator extends HashMap and its keys and values are as
  follows:
  key = operand to store to
  value = an ArrayList of all inputs to the mux tree (each item in this
          ArrayList is an Element object).
  MuxTableGenerator does not actually decide when a mux tree is necessary or
  what its inputs should be.  That is done inside of ModSched.java by its nested
  class MuxAdder.  Also, it is important to note, the epilog is created from the
  last iteration backwards to the first iteration out of the kernal, and
  therefore when MuxAdder tells MuxTableGenerator about the mux tree's inputs it
  tells it in the inverse order we want to select the earliest true iteration,
  and therefore they need to be turned around when they are saved here.
  */
  public void add(Operand primal, BooleanEquation p, Operand o) {
  
    
    if(primal.getFullName().indexOf("_predSave")==-1) {
      //since the predicates used in the stores are our control signals in the 
      //mux tree, and since the muxes need an operand rather than an
      //equation, instructions must be created to evaluate the logic 
      BEqToList eq_list = new BEqToList(p, new BooleanEquation(true));
      _logicHandleInsts.addAll(eq_list);
      //get the result of these logic equations
      BooleanOperand mux_op = eq_list.getResult();

      //get or create the ArrayList for this primal
      if(!this.containsKey(primal))
	this.put(primal, new ArrayList());
      ArrayList elementList = (ArrayList)this.get(primal);
      
      //create a new Element for this output, saving the mux control
      //operand
      Element newElement = new Element(mux_op, o);
      
      //save this to the map used by the mux tree collapsing methods
      HashSet opToElementTmp = new HashSet();
      if(_opToElementMap.containsKey(o))
        opToElementTmp = (HashSet)_opToElementMap.get(o);
      //_opToElementMap.put(o, newElement);
      _opToElementMap.put(o, opToElementTmp);
      opToElementTmp.add(newElement);
      //save the element to ArrayList for this operand:
      elementList.add(0, newElement); //note, a0 is actually the last iteration and a8
                                      //is the earliest going into the epilog
    }
  }
  
  /**
  this hashMap is used to create modPrim specific block operands
  key = modprim operand
  value = block operand for this modPrim
  */
  private HashMap _modPrimToBlockMap = new HashMap();
  /**
  This set saves all the newly created modPrim load instructions
  */
  private HashSet _modPrimLoads = new HashSet();
  /**
  This method returns a block operand specially created for each modPrim
  operand.  It saves those it creates into _modPrimToBlockMap and for future
  references to this modPrim, uses the same block operand.  It also creates the
  a new load instruction to replace all the load instructions used by every
  iteration in the epilog.
  */
  public Operand getModPrimBlock(PrimalOperand op) {
    //if a block operand already exists return it:
    if(_modPrimToBlockMap.containsKey(op))
      return (Operand)_modPrimToBlockMap.get(op);
      
    //else make a new one and save it
    Operand newOp = Operand.nextBlock(op.getFullName());
    _modPrimToBlockMap.put(op, newOp);
    
    //create a new load for this modPrim operand
    BooleanEquation trueBoolEq = new BooleanEquation(true);
    Instruction loadInst = Load.create(Operators.LOAD, 
                                       (Type)_modPrimToType.get(op),
    				       newOp, op, trueBoolEq);
    _modPrimLoads.add(loadInst);
    
    //return the new block Operand
    return newOp;
  }
    
  /**
  This is the main method from this class, and it creates the mux tree and its
  control logic.  The general algorithm used is described at the top of this
  class, so I will mostly put comments inside the method rather than repeat a
  lot here.  
  */
  public ArrayList genMuxTable() {
  
    ArrayList instList = new ArrayList();
    //foreach primal we want to store to:
    for (Iterator itin = ((Set)this.keySet()).iterator(); 
       itin.hasNext(); ) {
      Operand primal = (Operand)itin.next();
      //get the list of inputs to this tree:
      ArrayList elementList = (ArrayList)this.get(primal);

      Operand muxOut = null;
      BooleanEquation trueBoolEq = new BooleanEquation(true);
      Type type = primal.getType();
      
      //if the list has only one element, we only need to store it and no tree
      //is necessary
      if(elementList.size()==1)
        muxOut = ((Element)elementList.get(0)).op;
      else { //but otherwise let's plant ourselves a mux tree and see what we can grow
	while(elementList.size()>1) { //continue until there is only 1 element
	                              //in the list, meaning we are at the top
				      //of the tree (hmmm, a tree that gets
				      //wider as you go towards the base--must
				      //be a Christmas tree)
          //this ArrayList will be used to store the next layer in the mux tree:
	  ArrayList elementListTmpCopy = new ArrayList();
	  
	  //we want to go through the list taking off pairs of inputs and 
	  //creating muxes for them; i is used to count off the two inputs
	  int i = 0;
	  while(i < elementList.size()) {
	    //get the first element in this pair:
            Element element0 = (Element)elementList.get(i);
	    i++;
	    if(i < elementList.size()) { //if there are an odd number of 
	                                 //elements in this list, the last one
					 //will have to be passed directly to 
					 //the next level of the tree,
					 //but in the case that we can get a 
					 //pair of elements, proceed with mux
					 //creation
              //get the second element
	      Element element1 = (Element)elementList.get(i);
	      //increment i to point at the first element of the next pair
	      i++;
              
	      //make new block and boolean operands to hold the output from this
	      //mux and or:
	      muxOut = Operand.nextBlock("muxOut");
              BooleanOperand orOut = Operand.nextBoolean("orOut");
              
              //create a new element to hold it and add it to the next level's
	      //list:
	      Element newElement = new Element(orOut, muxOut);
              elementListTmpCopy.add(newElement);
	      
	      //can we collapse the tree here?  If both inputs read from the
	      //same modprim, then yes.  Save the fact that this mux is actually
	      //not a mux, but instead just a use of this modPrim:
	      if((element0.modPrim != null) &&
	         (element1.modPrim != null) &&
		 (element0.modPrim == element1.modPrim)) {
	        newElement.modPrim = element0.modPrim;
	      } 
	      else { //otherwise we can create a new mux:
		
		//get the inputs:
		Operand muxIn0 = element0.op;
		Operand muxIn1 = element1.op;
		//if either input is a use of a modPrim, use that modPrim's 
		//block operand instead of the original input:
		if(element0.modPrim != null) {
	          muxIn0 = getModPrimBlock(element0.modPrim);
		}
		if(element1.modPrim != null) {
	          muxIn1 = getModPrimBlock(element1.modPrim);
		}
		
		//create the mux!
		Instruction mux = Select.create(Operators.SELECT, type, muxOut, 
        					element0.pred, muxIn0, 
        					muxIn1, trueBoolEq);
        	//save the new mux instruction:
		instList.add(mux);
	      }
	      
	      //create an or instruction of the two predicates from both inputs
              Type orType = Type.Bool;
	      Instruction or = Binary.create(Operators.OR, orType, orOut, 
                			     element0.pred, element1.pred, 
	        			     trueBoolEq);
              //save the new or instruction:
	      instList.add(or);
            }
	    else { //if the last element cannot be paired, just copy it up to
	           //the next level of the tree:
	      elementListTmpCopy.add(element0);
	    }
	  }
	  //over write the original list, with our newly created list for the 
	  //next level of the tree:
	  elementList = new ArrayList(elementListTmpCopy);
	}
      }
      //if the entire tree just uses a modPrim, then we just need to store
      //our modPrim block operand
      if(((Element)elementList.get(0)).modPrim != null) {
        muxOut = getModPrimBlock(((Element)elementList.get(0)).modPrim);
      }

      //create a load instruction to get the kernal store predicate:
      PrimalOperand input = (PrimalOperand)_primToPred.get(primal);
      BooleanOperand output = Operand.newBoolean(primal.getFullName() + 
                                                 "_kernalPred");
      Instruction loadInst = Load.create(Operators.LOAD, Type.Bool,
          				 output, input, trueBoolEq);
      instList.add(loadInst);
      
      //make a new BooleanEquation that is the control for the final mux AND the
      //inverse of the kernal store predicate:
      BooleanEquation newPred = new BooleanEquation(((Element)elementList.get(0)).pred);
      BooleanEquation newerThanNewPred = new BooleanEquation((Bool)output);
      BooleanEquation newestPred = new BooleanEquation(newPred.and(newerThanNewPred.not()));
      BooleanEquation oldPred = (BooleanEquation)_primToOldPred.get(primal);
      
      BooleanEquation storePred = newestPred.and(oldPred);
      
      //we need one operand predicates, so create logic instructions to evaluate
      //this predicate:
      //BEqToList eq_list = new BEqToList(newestPred, new BooleanEquation(true));
      //instList.addAll(eq_list);
      
      //create a predicate from the output from these logic equations:
      //BooleanOperand predOp = eq_list.getResult();
      //BooleanEquation storePred = new BooleanEquation((Bool)predOp);
      
      //create the store the output from the mux tree (or
      //the modPrim block operand) to the primal using this predicate:
      Instruction storeInst = Store.create(Operators.STORE, type,
  					   primal, muxOut, storePred);
      //save the new instruction:
      instList.add(storeInst);
    
    }
    //save the MuxTableGenerator created modPrim loads and the logic
    //instructions used to evaluate the original epilog store predicates (see
    //comments at top on _logicHandleInsts and in add):
    instList.addAll(_modPrimLoads);
    instList.addAll(_logicHandleInsts);
    
    //return all the new instructions so they can be added to the epilog:
    return instList;
  }
}