hyperblocklist.java

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

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


public class HyperBlockList extends HashMap {

  private class HyperBlockListData {
    public BlockNode root;
    public HashSet nodeSet = new HashSet();
    public UseHash useHash = new UseHash();
    public MultiDefHash defHash = new MultiDefHash();
    public HashSet inEdges = new HashSet();
    public HashSet outEdges = new HashSet();
    public HashSet nextNodes = new HashSet();
    public ArrayList instructions = new ArrayList();
    public HashMap inst2NodeMap = new HashMap();
  }
  
  private class MergeObject {
    public BlockNode node1;
    public BlockNode node2;
    public BlockEdge mergeEdge; //needed for merge serial
    public boolean isParallelMerge = false;
  }
  
  private class MergeStack extends ArrayList {
  
    public MergeStack() {super();}
    public void push(BlockNode node1, BlockNode node2, BlockEdge mergeEdge, 
                    boolean isParallelMerge) {
      MergeObject saveMergeInfo = new MergeObject();
      saveMergeInfo.node1 = node1;
      saveMergeInfo.node2 = node2;
      saveMergeInfo.mergeEdge = mergeEdge;
      saveMergeInfo.isParallelMerge = isParallelMerge;
      add(saveMergeInfo);
    }
    public void push(BlockNode node1, BlockNode node2, 
                    boolean isParallelMerge) {
      MergeObject saveMergeInfo = new MergeObject();
      saveMergeInfo.node1 = node1;
      saveMergeInfo.node2 = node2;
      saveMergeInfo.isParallelMerge = isParallelMerge;
      add(saveMergeInfo);
    }
    /**
    These pushes and pop methods are actually misnamed because this is actually 
    a FIFO and not a stack..I just don't know what the names are for the 
    equivalent instructions in a FIFO.
    */
    public boolean pop(BlockGraph graph) {
      if(size() == 0) //when all merges have been performed return false
        return false;
      MergeObject saveMergeInfo = (MergeObject)get(0);
      remove(0);
      BlockNode node1 = saveMergeInfo.node1;
      BlockNode node2 = saveMergeInfo.node2;
      BlockEdge mergeEdge = saveMergeInfo.mergeEdge;
      boolean isParallelMerge = saveMergeInfo.isParallelMerge;
      
      
      if(saveMergeInfo.isParallelMerge) { //parallel merge
        //graph.mergeEdges(node1);
	graph.mergeParallel(node1, node2);
	graph.mergeNode(node1, node2);
      }
      else { //serial merge
        graph.mergeEdges(node1); //or remove edge??
	graph.mergeSerial(node1, mergeEdge, node2);
	graph.mergeNode(node1, node2);
      }
      return true; //a merge was performed
    }
  
  }
  
  private MergeStack _mergeStack = new MergeStack();
  
  private class Node2HPBlockMap extends HashMap {
    private Node2HPBlockMap() {super();}
    public BlockNode get(BlockNode n) {
      if(containsKey(n))
        return (BlockNode)super.get(n);
      else
        return n;
    }
  }
  
  private Node2HPBlockMap _node2HyperBlockMap = new Node2HPBlockMap();
  
  public HyperBlockList() {super();}
  
  public void createHyperBlock(BlockNode root) {
    if(super.containsKey(root))  
      return;
    HyperBlockListData newHyperBlock = new HyperBlockListData();
    newHyperBlock.root = root;
    _node2HyperBlockMap.put(root, root);
    super.put(root, newHyperBlock);
    
    
    //need to do this by hand because the methods will skip over the data
    newHyperBlock.nodeSet.add(root);
    addInstructions(root, root.getInstructions());
    HashSet prevNodes = new HashSet();
    for (Iterator inEdgIt = root.getInEdges().iterator(); inEdgIt.hasNext();){
      BlockEdge inEdge = (BlockEdge)inEdgIt.next();
      BlockNode prevNodeTmp = (BlockNode)inEdge.getSource();
      BlockNode prevNode = _node2HyperBlockMap.get(prevNodeTmp);
      if(!prevNodes.contains(prevNode)) {
        newHyperBlock.inEdges.add(inEdge);
	prevNodes.add(prevNode);
      }
    }
    HashSet nextNodes = new HashSet();
    for (Iterator outEdgIt = root.getOutEdges().iterator(); outEdgIt.hasNext();){
      BlockEdge outEdge = (BlockEdge)outEdgIt.next();
      BlockNode nxtNodeTmp = (BlockNode)outEdge.getSink();
      BlockNode nxtNode = _node2HyperBlockMap.get(nxtNodeTmp);
      
      if(!nextNodes.contains(nxtNode)) {
        saveNextNode(root, nxtNode);
        newHyperBlock.outEdges.add(outEdge);
	nextNodes.add(nxtNode);
      }
    }
    
  }
    
  public BlockNode findNode(Instruction inst, BlockNode root) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    if(newHyperBlock.inst2NodeMap.containsKey(inst))
      return (BlockNode)newHyperBlock.inst2NodeMap.get(inst);
    
    for (Iterator blockIt = newHyperBlock.nodeSet.iterator(); 
	 blockIt.hasNext();) {
      BlockNode node = (BlockNode) blockIt.next();
      if(node.getInstructions().contains(inst)) {
        newHyperBlock.inst2NodeMap.put(inst, node);
	return node;
      }
    }
    
    return null;
    
  }
  
  public boolean popMerge(BlockGraph graph) {
    return _mergeStack.pop(graph);
  }
  
  /**
  This method checks to see if an operand is defined before it is used.  It does this
  by checking how deep in the ArrayList of instructions for this hyperblock, the 
  operand is defined and compares this with the earliest instruction that uses 
  the operand.  Please see comments for the method makeHyperBlockInstructionList
  for a discussion on the order that the instuctions are placed in the instruction list.
  */
  public boolean isDefinedBeforeUsed(Operand op, BlockNode root) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    ArrayList instList = newHyperBlock.instructions;
    MultiDefHash defHash = newHyperBlock.defHash;
    UseHash useHash = newHyperBlock.useHash;
   
    //Instruction defInst = (Instruction)defHash.get(op);
    int minDefRank = 9999;
    for(Iterator defIt = ((ArrayList)defHash.get(op)).iterator();
	 defIt.hasNext();) {
      Instruction defInst = (Instruction) defIt.next();
      if(instList.indexOf(defInst) < minDefRank)
        minDefRank = instList.indexOf(defInst);
    }
    
    int useMinRank = 9999;
    for(Iterator useIt = ((ArrayList)useHash.get(op)).iterator();
	 useIt.hasNext();) {
      Instruction useInst = (Instruction) useIt.next();
      if(instList.indexOf(useInst) < useMinRank)
        useMinRank = instList.indexOf(useInst);
    }
    
    if(minDefRank < useMinRank)
      return true;
    else
      return false;
  }
  
  public ArrayList getInstructionList(BlockNode root) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    if(newHyperBlock != null)
      return newHyperBlock.instructions;
    else
      return root.getInstructions();
  }
  
  public void addInstructions(BlockNode root, ArrayList iList) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    addInstructions(root, iList, newHyperBlock.instructions.size());
  }
  
  public void addInstructions(BlockNode root, ArrayList iList, int rank) {
    mergeInMultiDefHash(root, iList);
    saveToUseHash(root, iList);
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    newHyperBlock.instructions.addAll(rank, iList);
  }
  
  public void saveToUseHash(BlockNode root, Collection instructions) {
  
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    UseHash use_hash_tmp = newHyperBlock.useHash;
    use_hash_tmp.addinstructions(instructions);
  }
  
  public void removeInst(BlockNode root, Instruction inst) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    for (Iterator blockIt = newHyperBlock.nodeSet.iterator(); 
	 blockIt.hasNext();) {
      BlockNode node = (BlockNode) blockIt.next();
      node.removeInstruction(inst);
    }
    newHyperBlock.instructions.remove(inst);
    newHyperBlock.useHash.remove(inst);
    newHyperBlock.defHash.remove(inst);
  }
  
  public void clearUseHash(BlockNode root) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    //MultiDefHash def_hash_tmp = newHyperBlock.defHash;
    //def_hash_tmp.clear();
    UseHash use_hash_tmp = newHyperBlock.useHash;
    use_hash_tmp.clear();
  }
  
  public void addToUseHash(BlockNode root, Instruction i) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    //MultiDefHash def_hash_tmp = newHyperBlock.defHash;
    //def_hash_tmp.add(i);
    UseHash use_hash_tmp = newHyperBlock.useHash;
    use_hash_tmp.add(i);
  }
  
  /**
  initializes a def hash for a given node
  */
  public void putAllInMultiDefHash(BlockNode root, MultiDefHash def_hash) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    MultiDefHash def_hash_tmp = new MultiDefHash();
    newHyperBlock.defHash = def_hash_tmp;
    def_hash_tmp.putAll(def_hash);
    for (Iterator vIt2 = def_hash.keySet().iterator(); 
	vIt2.hasNext();) {
      Operand def = (Operand) vIt2.next();
      Instruction i = (Instruction)def_hash.get(def);
      def.setType(i.type());
    }
  }
  
  /**
  puts an instruction into the defhash that defines operand op and is in the HyperBlock
  associated with root node root
  */
  public void putInMultiDefHash(BlockNode root, Operand op, Instruction i) {
  
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    MultiDefHash def_hash_tmp = newHyperBlock.defHash;
    def_hash_tmp.put(op, i);
    op.setType(i.type());
  
  }

  public MultiDefHash getMultiDefHash(BlockNode root) {
  
    //this will make an empty hyperblock.  It is only necessary for GlobalEntry, because my pass never comes here
    if(!containsKey(root))
      createHyperBlock(root);
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    return newHyperBlock.defHash;
  
  }

  public void saveMultiDefHash(BlockNode root, MultiDefHash defHash) {
  
    putAllInMultiDefHash(root, defHash);
    //HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    //newHyperBlock.defHash = defHash;
  
  }
  
  public void getCombineMultiDefHashes(BlockNode root, MultiDefHash defHash) {
  
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    MultiDefHash def_hash_tmp = newHyperBlock.defHash;
    for(Iterator instListsIt2 = defHash.values().iterator();
	   instListsIt2.hasNext();){
      ArrayList instLists = (ArrayList) instListsIt2.next();
      def_hash_tmp.addinstructions(instLists);
    }
  }
  
  public void mergeInMultiDefHash(BlockNode root, Collection instructions) {
  
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    MultiDefHash def_hash_tmp = newHyperBlock.defHash;