primalpromotion.java

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

	Operand op = (Operand) opIt.next();
	if((!op.isPrimal())&&(!op.isConstant()))
          addLoadsAndStores(def_hash, use_hash, op, savedDefsTmp, usedByChildren,
        		    node, mergeBlockGroups);
      } 
      
    }
    _operandCreator.addInstructs();
  }
      
  public HashSet primalPromotionRec(BlockNode currentHyperBlock,
                                    HyperBlockList mergeBlockGroups,
				    HashSet alreadyVisited,
				    HashSet savedDefs/*,
				    HashMap saveChildUses,
				    HashMap saveParentDefs*/) {
  
    alreadyVisited.add(currentHyperBlock);
    MultiDefHash def_hash = mergeBlockGroups.getMultiDefHash(currentHyperBlock);
    HashSet savedDefsTmp = new HashSet(savedDefs);
    HashSet savedDefsNew = new HashSet(savedDefs);
    savedDefsNew.addAll(def_hash.keySet());
    HashSet usedByChildren = new HashSet();
    for(Iterator esIt = mergeBlockGroups.getChildren(currentHyperBlock).iterator();
    	   esIt.hasNext();){
      BlockNode cNode = (BlockNode) esIt.next();
      if(!alreadyVisited.contains(cNode)) {
	HashSet usedByChildrenTmp = null;
	usedByChildrenTmp = primalPromotionRec(cNode, mergeBlockGroups, 
	                                       alreadyVisited, savedDefsNew/*,
					       saveChildUses, saveParentDefs*/);
        usedByChildren.addAll(usedByChildrenTmp);
      }
      else if((currentHyperBlock != cNode)&&(cNode != _graph.EXIT)) {
	if(saveChildUses.containsKey(cNode)) {
	  usedByChildren.addAll((HashSet)saveChildUses.get(cNode));
        }
	/*else {
          usedByChildren.addAll(mergeBlockGroups.getUseHash(currentHyperBlock).keySet());
	}*/
        HashSet cNodeDefs = new HashSet();
	if(saveParentDefs.containsKey(cNode))
	  cNodeDefs = (HashSet)saveParentDefs.get(cNode);
	cNodeDefs.addAll(def_hash.keySet());
	saveParentDefs.put(cNode, cNodeDefs);
      }
      else if((currentHyperBlock == cNode)&&(cNode != _graph.EXIT)) {
	//HashSet boundryXingOps = new HashSet();
        //boundryXingOps.addAll(getRealLoopUses(mergeBlockGroups, cNode));
	//usedByChildren.addAll(boundryXingOps);
	//savedDefsTmp.addAll(boundryXingOps);
	savedDefsTmp.addAll(def_hash.keySet());
      }
    }
    //usedByChildren.addAll(mergeBlockGroups.getUseHash(currentHyperBlock).keySet());
    //if((currentHyperBlock!=_graph.EXIT)&&(currentHyperBlock!=_graph.ENTRY)) {
      usedByChildren.addAll(mergeBlockGroups.getUseHash(currentHyperBlock).keySet());
      saveChildUses.put(currentHyperBlock, usedByChildren);
      if(saveParentDefs.containsKey(currentHyperBlock)) {
        HashSet cNodeDefs = (HashSet)saveParentDefs.get(currentHyperBlock);
        //cNodeDefs.addAll(def_hash.keySet());
	savedDefsTmp.addAll(cNodeDefs);
      }
      saveParentDefs.put(currentHyperBlock, savedDefsTmp);
    //}
    return usedByChildren;
  
  }
  
  
  /**
  This method analyzes a hyperblock to decide how to add loads and stores for primal promotion
  and how to replace the existing nonprimal operands so that no aliases are created and taking
  into account whether the lifetime of an operand crosses over a loop boundary, etc.
  
  There are several cases that need to be considered.  
  
  1) an operand is only used by a hyperblock and not defined and is defined by an earlier hyperblock
  in the graph.  It is important to note, that to test for this, we need to check not only that it is
  in the usehash and not in the defhash, but also that it was defined by an earlier block.  However,
  primalPromotionRec does the actual checking to see that it is defined by an earlier block and that it
  is used by this block before calling this method.  In this simple case, we need to add a load to load
  the primal version of this operand into a newly named local copy of the nonprimal.  Additionally, all 
  uses of the original nonprimal, need to be changed to use the new local copy of the nonprimal instead
  of the original nonprimal.  Any aliases existing or created are not removed.
  
  2) an operand is only defined by a hyperblock and not used. Again, primalPromotionRec checks to make
  sure that this operand is in this hyperblock's defhash and is used by a child node.  The only check
  performed here is that it is only defined.  For this case, a store instruction must be added, and a 
  new local nonprimal copy of the original nonprimal must be created and each definition of the
  old nonprimal must be replaced by the new nonprimal.  
  
  3)  if an operand is used and defined within a hyperblock, there are 2 different sub cases.
  
  A)  If an operand is used and defined within a hyperblock and is defined before it is used.  This
  case is very simple, because it overwrites any earlier definitions of the operand and so no load 
  is necessary. There are two sub cases of this subcase:
  
  i) This operand is not used by any of the hyperblock's descendants.  In this case, no loads or stores
  are necessary, and the only thing to do is to rename the nonprimal so it doesn't conflict with other
  versions in the graph. Only one new name should be generated and it should be used for both the uses
  and defs of this operand.
  
  ii) This operand is used by at least one of the hyperblock's descendants.  In this case, a store must be
  added to save the result of this non primal to a primal, which can transfer its value down to the 
  descendant node.  Additionally, the nonprimals should be renamed in the hyperblock, using the same
  name for both all uses and all defs.
  
  B)  If an operand is used and defined within a hyperblock and it is used before it is defined.  This 
  case is slightly more complicated.  For this to be the case, there must be a definition in an 
  ancestor hyperblock, to give that first use its original value.  Because of that, a load will always
  be necessary, although just to be careful, I will first check that it was defined by an ancestor.  If
  this operand is used by a descendant (which could be the next iteration of a loop hyperblock) a store
  instruction must be added.  In this case, two new nonprimal versions of the original nonprimal must be
  created--one for the uses, and as the result of the load, and the other for the defs and for the source
  for the store instruction.  
  
  For cases 2 and 3, if there are multiple definitions of a non prim, they each need to get a different
  new non prim operand, but be saved to the same new primal.  This may create aliases, but the remove 
  alias path will take care of that, and the multiple stores to the same primal can be optimized to one
  store and select statements, but this will be done by the merge blocks pass.
  
  ==================================================================================================
  Note:
  Only 1 load or store is added per hyperblock!!! (I don't know why I used exclamation marks, or 
  even more, why I used 3, but evidently I found this statement highly significant at the time.
  Also this is no longer true.  Multiple stores may be added.)
  ==================================================================================================
  
  
  */
  public void addLoadsAndStores(MultiDefHash defHash, UseHash useHash, Operand op, 
                                HashSet definedByParents, HashSet usedByChildren, 
				BlockNode hyperBlockRoot, 
				HyperBlockList hyperBlockGroups) {
    BooleanEquation trueEq = new BooleanEquation(true);
    //case 1:
    if((useHash.containsKey(op))&&(!defHash.containsKey(op))&&
       (definedByParents.contains(op))) { //check if used but not defined
      Operand newNonPrimOp = op.getNextNonPrime();
      Instruction inst = (Instruction)(((ArrayList)useHash.get(op)).get(0)); //assuming 1st def
        								     //has same type as 
        								     //others
      if(replaceUses(op, newNonPrimOp, useHash, hyperBlockRoot, hyperBlockGroups))
        _operandCreator.addLoad(op, newNonPrimOp, hyperBlockRoot, inst.type(),
	                        hyperBlockGroups);
    }
    //case 2:
    else if((!useHash.containsKey(op))&&(defHash.containsKey(op))&&
            (usedByChildren.contains(op))) { //check if defined but not used
      
      for(Iterator defInstIt = ((ArrayList)defHash.get(op)).iterator(); 
             defInstIt.hasNext();) {
        Instruction inst = (Instruction) defInstIt.next();
        _operandCreator.addStore(op, inst, op, hyperBlockGroups.findNode(inst, hyperBlockRoot), 
	                         inst.type(), trueEq, hyperBlockGroups);
      }
    }
    //case 3:
    else if((useHash.containsKey(op))&&(defHash.containsKey(op))) { //check if used and defined
      //case 3A:
      if(hyperBlockGroups.isDefinedBeforeUsed(op, hyperBlockRoot)) {
	
	//case 3A i:
	if(!usedByChildren.contains(op)) {
	  Operand newNonPrimOp = op.getNextNonPrime();
	  replaceOp(op, newNonPrimOp, useHash, defHash, hyperBlockRoot, hyperBlockGroups); 
	}
	//case 3A ii:
	else {
          for(Iterator defInstIt = ((ArrayList)defHash.get(op)).iterator(); 
    	         defInstIt.hasNext();) {
            Instruction inst = (Instruction) defInstIt.next();
	    _operandCreator.addStore(op, inst, op, hyperBlockGroups.findNode(inst, hyperBlockRoot), inst.type(), 
	                             trueEq, hyperBlockGroups);
	  }
	}
      }
      //case 3B:
      else {
	Operand newNonPrimOp = op.getNextNonPrime();
	//if((definedByParents.contains(op))&&(replaceUses(op, newNonPrimOp, useHash, 
	//  					       hyperBlockRoot, hyperBlockGroups))) {
	if(replaceUses(op, newNonPrimOp, useHash, hyperBlockRoot, hyperBlockGroups)) {
	//if((definedByParents.contains(op))&&
	//   (replaceUses(op, newNonPrimOp, useHash, hyperBlockRoot, hyperBlockGroups))) {
          Instruction inst = (Instruction)(((ArrayList)useHash.get(op)).get(0)); //assuming 1st use
        									 //has same type as 
        									 //others
          _operandCreator.addLoad(op, newNonPrimOp, hyperBlockRoot, inst.type(),
        			  hyperBlockGroups);
	}



	for(Iterator defInstIt = ((ArrayList)defHash.get(op)).iterator(); 
               defInstIt.hasNext();) {
          Instruction inst = (Instruction) defInstIt.next();
          Operand newNonPrimDef = op.getNextNonPrime();
          //_operandCreator.addStore(op, newNonPrimDef, hyperBlockRoot, inst.type(), trueEq,
          _operandCreator.addStore(op, inst, newNonPrimDef, hyperBlockGroups.findNode(inst, hyperBlockRoot), 
	                           inst.type(), trueEq, hyperBlockGroups);
          inst.replaceOperand(op, newNonPrimDef);
	}
       
      }
    }
  }
  
  
  /**
  This method replaces uses of an operand that is being primal promoted, with the new local copy of this
  operand.  If it finds that it will create an alias (i.e. the old nonprimal is loaded or stored into 
  another nonprimal), it replaces the source of the load or store with the new local copy of the nonprim
  and converts any stores into loads.
  */
  public boolean replaceUses(Operand oldUse, Operand newUse, UseHash useHash, 
                             BlockNode cBlock, HyperBlockList hyperBlockGroups) {
      
    //if at least one def is from an alias there will already be a store inst
    boolean addLoad = true;
    Operand newOp = newUse;
    for (Iterator useInstIt = ((ArrayList)((ArrayList)((UseHash)useHash.clone()).get(oldUse)).clone()).iterator(); 
    	 useInstIt.hasNext();) {
      Instruction inst = (Instruction) useInstIt.next();
      //useHash.remove(inst);
      inst.replaceOperand(oldUse, newOp);
      //useHash.add(inst);
    }
    return addLoad;
      
  }
  
  
  /**
  This method replaces defs of an operand that is being primal promoted, with the new local copy of this
  operand.  If it finds that it will create an alias (i.e. the old nonprimal is loaded or stored into 
  another nonprimal), it replaces the destination of the load or store with the new local copy of the 
  nonprim and converts any loads into stores.
  */
  public boolean replaceDefs(Operand oldDef, Operand newDef, MultiDefHash defHash) {
      
    
    boolean addStore = true;
    
    for (Iterator defInstIt = ((ArrayList)defHash.get(oldDef)).iterator(); 
    	 defInstIt.hasNext();) {
      Instruction inst = (Instruction) defInstIt.next();
      inst.replaceOperand(oldDef, newDef);
    }
    return addStore;
      
  }
  
  /**
  This method replaces the old nonprim with a new one.  It replaces both the defs and uses of the 
  nonprim.  If it finds that it would create an alias (i.e. the evil loads and stores to another 
  nonprim), this time, it deletes the load/store instruction and replaces the alias everywhere with
  the new nonprim by calling replaceOp again with the alias operand as an input.  
  */
  public void replaceOp(Operand oldOp, Operand newOp, UseHash useHash, MultiDefHash defHash,
                        BlockNode hyperBlockRoot, HyperBlockList hyperBlockGroups ) {
      
    for (Iterator opInstIt = ((ArrayList)((ArrayList)useHash.get(oldOp)).clone()).iterator(); 
    	 opInstIt.hasNext();) {
      Instruction inst = (Instruction) opInstIt.next();
      inst.replaceOperand(oldOp, newOp);
    }
    
    for (Iterator opInstIt = ((ArrayList)((ArrayList)defHash.get(oldOp)).clone()).iterator(); 
    	 opInstIt.hasNext();) {
      Instruction inst = (Instruction) opInstIt.next();
      inst.replaceOperand(oldOp, newOp);
    }
      
  }
  
  
  /**
  This method looks for which operands have lifetimes over the loop boundary and are used by the next 
  iteration of the loop.  It determines this by checking if the operand was used before being defined.
  */
  public HashSet getRealLoopUses(HyperBlockList hyperBlockGroups, BlockNode hyperblockRootNode) {
    MultiDefHash defHash = hyperBlockGroups.getMultiDefHash(hyperblockRootNode);
    UseHash useHash = hyperBlockGroups.getUseHash(hyperblockRootNode);
    HashSet realUses = new HashSet();
    for(Iterator defIt = defHash.keySet().iterator();
    	   defIt.hasNext();){
      Operand def = (Operand) defIt.next();
      if(useHash.containsKey(def)) {
        if(!hyperBlockGroups.isDefinedBeforeUsed(def, hyperblockRootNode)) {
	  realUses.add(def);
        }
      }
    }
    return realUses; 
  }


}