primalpromotion.java

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

/*
 *
 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.*;

/** This class contains the methods for performing primal promotion.  Originally
 *  all this code was in ConvInterBlockNonPrimToPrimal.java, but I moved it here,
 *  so that the methods would be available to ModuloSchedule.java.  This is a 
 *  brand new version of this class.  I rewrote it because I couldn't understand
 *  the old one anymore, and I wanted to rewrite it to make it more readable and 
 *  simple.  I hope I didn't add some errors.  
 * 
 * @author Kris Peterson
 */
public class PrimalPromotion 
{
  
  private class ChildNodeFinder {
  
    private LabelOperand _c1, _c2;
    
    public ChildNodeFinder() { _c1 = null; _c2 = null; }
    
    public BooleanOperand findBrBool(BlockNode node, HashSet nodeSet) {
      for (Iterator instIt = node.getInstructions().iterator(); 
           instIt.hasNext();) {
        Instruction i = (Instruction) instIt.next();
	if(Goto.conforms(i)) {
	  _c1 = Goto.getTarget(i);
	  return null;
	}
	if(Branch.conforms(i)) {
	  _c1 = Branch.getTarget1(i);
	  _c2 = Branch.getTarget2(i);
	  return Branch.getBoolean(i);
	}
      }
      if(node.getOutEdges().size()==1) {
        Iterator cNodeIt = node.getOutEdges().iterator();
        BlockNode cNode = (BlockNode)((BlockEdge)cNodeIt.next()).getSink();
	if(nodeSet.contains(cNode))
	  _c1 = cNode.getLabel();
      }
      return null;
    }
    
    public BlockNode getC1(BlockNode pNode, HashSet nodeSet) {
    
      for (Iterator cNodeIt = pNode.getOutEdges().iterator(); 
           cNodeIt.hasNext();) {
        BlockEdge outEdge = (BlockEdge) cNodeIt.next();
	BlockNode possibleCNode = (BlockNode)outEdge.getSink();
	if(possibleCNode == pNode) continue;
	if(!nodeSet.contains(possibleCNode)) continue;
	if(possibleCNode.getLabel() == _c1)
	  return possibleCNode;
      } 
      return null;
    }
  
    public BlockNode getC2(BlockNode pNode, HashSet nodeSet) {
    
      for (Iterator cNodeIt = pNode.getOutEdges().iterator(); 
           cNodeIt.hasNext();) {
        BlockEdge outEdge = (BlockEdge) cNodeIt.next();
	BlockNode possibleCNode = (BlockNode)outEdge.getSink();
	if(possibleCNode == pNode) continue;
	if(!nodeSet.contains(possibleCNode)) continue;
	if(possibleCNode.getLabel() == _c2)
	  return possibleCNode;
      } 
      return null;
    }
  
  }
  
  /**
  This nested class was written to help create load and store instructions
  and to generate the new primal operands and new block operands
  */
  private class OperandCreator {
  
    private int _lkwCntr;
    private HashMap _def2PrimMap;
    private HashMap _def2NonPrimMap;
    private HashMap _newInsts;
    
    public OperandCreator() {
      _lkwCntr = 0;
      _def2PrimMap = new HashMap();
      _def2NonPrimMap = new HashMap();
      _newInsts = new HashMap();
    }
    
    private class InstRank {
    
      public Instruction i;
      public int rank;
      public InstRank() {}
    }
    
    /**
    I don't add the load and store instructions until the end, and so they
    need to be saved until ready to be added.  This method saves them to a
    private variable hashset called _newInsts, which saves a list of 
    instructions to add to which node.
    */
    public void addNewInst(BlockNode pBlock, Instruction inst, int rank) {
      if(!(_newInsts.containsKey(pBlock)))
        _newInsts.put(pBlock, new HashSet());
      
      InstRank i = new InstRank();
      i.i = inst;
      i.rank = rank;
      ((HashSet)_newInsts.get(pBlock)).add(i);
    }
    
    
    public PrimalOperand makePrimal(Operand op, Type type) {
      if(_def2PrimMap.containsKey(op)) { 
	PrimalOperand newVar = (PrimalOperand)_def2PrimMap.get(op);
        return newVar;
      }
      String name = "lkw" + _lkwCntr;
      _lkwCntr++;
      PrimalOperand newVar = Operand.newPrimal(name);
      /*Variable v = new Variable(newVar, type, true);
      _graph.addVariable(v);*/
      _def2PrimMap.put(op, newVar);
      return newVar;
    
    }
    
    /**
    This method helps me to create a new primal for a given operand that I wish 
    to pass between blocks, unless a primal already exists for that operand.
    */
    //public void addStore(Operand def, Operand otherOp, BlockNode pBlock, Type type, 
    public void addStore(Operand def, Instruction dInst, Operand otherOp, 
                         BlockNode pBlock, Type type, BooleanEquation eq, 
			 HyperBlockList hyperBlockGroups) {
      /**
      make the new primal and its store
      */
      ArrayList nodeInstList = pBlock.getInstructions();
      if(nodeInstList.contains(dInst)) {
        int defRank = nodeInstList.indexOf(dInst) + 1;
        PrimalOperand newVar = makePrimal(def, type);
        //Operand otherOp = makeNonPrim(def);
        Instruction sInst = Store.create(Operators.STORE, type, newVar, otherOp/*, eq*/);
        addNewInst(pBlock, sInst, defRank);
        //return otherOp;
      }
    }
    
    /**
    create or get a new copy of the non primal operand
    */
    public void addLoad(Operand def, BlockNode cBlock, 
                        HyperBlockList hyperBlockGroups, Instruction lInst
			 /*BooleanEquation eq, boolean makeLoad*/) {
    
      //Operand newVar = makeNonPrim(def);
      //get the primal, so that it can be used in the load instruction
      ArrayList instList = hyperBlockGroups.getInstructionList(cBlock);
      UseHash hBlockUseHash = hyperBlockGroups.getUseHash(cBlock);
      int useMinRank = 9999;
      Instruction fstUse = null;
      for(Iterator useIt = ((ArrayList)hBlockUseHash.get(def)).iterator();
           useIt.hasNext();) {
        Instruction useInst = (Instruction) useIt.next();
        if((instList.indexOf(useInst) < useMinRank)&&
	   (useInst != lInst)) {
          useMinRank = instList.indexOf(useInst);
	  fstUse = useInst;
        }
      }
      for(Iterator esIt = hyperBlockGroups.getNodeSet(cBlock).iterator();
    	     esIt.hasNext();){
	BlockNode cNode = (BlockNode) esIt.next();
        UseHash useHash = cNode.getUseHash();
	ArrayList nodeInstList = cNode.getInstructions();

	if(nodeInstList.contains(fstUse)) {
	  int useRank = nodeInstList.indexOf(fstUse);
	  addNewInst(cNode, lInst, useRank);
	}
      }
    }
    
    public void addLoad(Operand def, Operand newVar, BlockNode cBlock, Type type, 
                        HyperBlockList hyperBlockGroups) {
      PrimalOperand lkwVar = makePrimal(def, type);
      BooleanEquation trueBoolEq = new BooleanEquation(true);
      Instruction lInst = Load.create(Operators.LOAD, type, newVar, lkwVar/*, trueBoolEq*/);
      addLoad(def, cBlock, hyperBlockGroups, lInst);
    }
    /**
    add all the instructions to their respective blocks
    */
    public void addInstructs() {
    
      
      for (Iterator opIt = _newInsts.keySet().iterator();
           opIt.hasNext();){
        BlockNode node = (BlockNode) opIt.next();
	ArrayList instList = new ArrayList(((HashSet)_newInsts.get(node)));
	sort(instList);
	int cnt = 0;
	for (Iterator instIt = instList.iterator();
           instIt.hasNext();){
          InstRank i = (InstRank) instIt.next();
	  Instruction inst = i.i;
	  int rank = i.rank + cnt++;
	  node.addInstruction(inst, rank);
	}
      }
      _newInsts = new HashMap();
    }
  
    private void sort(ArrayList o_list) {
      class InstRankCompare implements Comparator {      
	public int compare(Object o1, Object o2) {	
  	  if (o1 instanceof InstRank		  
  	  && o2 instanceof InstRank) { 	 
  	    InstRank p1 = (InstRank)o1;	     
  	    InstRank p2 = (InstRank)o2;	     
  	    if( p1.rank > p2.rank ){  	  
  	      return 1;	       
  	      } else if( p1.rank < p2.rank ){ 	   
  	      return -1;         
  	      } else {		
  	      return 0;	       
  	    }	   
  	    } else {	    
  	    throw new ClassCastException("Not Instruction");	  
  	  }      
	}    
      }	     
      Collections.sort(o_list, new InstRankCompare());  
    }

  }
  

  private OperandCreator _operandCreator;
  private BlockGraph _graph;
  public PrimalPromotion(BlockGraph graph) {
    _operandCreator = new OperandCreator();
    _graph = graph;
  }
  
  /**
  recursive analysis of graph, for primal promotion.  It descends the graph 
  searching for non primals that are defined by a ancestor of some descentent
  block and adds a load and store to a primal, to carry the value between blocks
  and renames the non primal.
  
  */
  private HashMap saveChildUses = new HashMap();
  private HashMap saveParentDefs = new HashMap();
  public void primalPromotion(HyperBlockList mergeBlockGroups) {
    
    primalPromotionRec((BlockNode)_graph.ENTRY, mergeBlockGroups,
		       new HashSet(), new HashSet()/*, saveChildUses, 
		       saveParentDefs*/);
    for(Iterator esIt = saveChildUses.keySet().iterator();
    	   esIt.hasNext();){
      BlockNode node = (BlockNode) esIt.next();
      MultiDefHash def_hash = mergeBlockGroups.getMultiDefHash(node);
      UseHash use_hash = mergeBlockGroups.getUseHash(node);
      HashSet usedByChildren = (HashSet)saveChildUses.get(node);
      //usedByChildren.addAll(use_hash.keySet());
      HashSet savedDefsTmp = (HashSet)saveParentDefs.get(node);
      //savedDefsTmp.addAll(def_hash.keySet());
      HashSet allTransferVars = new HashSet();
      allTransferVars.addAll(savedDefsTmp);
      allTransferVars.addAll(usedByChildren);
      for(Iterator opIt = allTransferVars.iterator();
    	     opIt.hasNext();){