hyperblocklist.java

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

    def_hash_tmp.addinstructions(instructions);
  }
  

  /**
  this method initializes the usehash saved for a specific set of blocks (I keep track
  of the set, based on one root, which was the first discovered in my traversal of the tree)
  */
  public void putAllInUseHash(BlockNode root, UseHash use_hash) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    UseHash use_hash_tmp = new UseHash();
    newHyperBlock.useHash = use_hash_tmp;
    //use_hash_tmp.putAll(use_hash);
    for (Iterator opIt = ((UseHash)use_hash.clone()).keySet().iterator();
	 opIt.hasNext();){
      Operand op = (Operand) opIt.next();   
      use_hash_tmp.put(op, new ArrayList((ArrayList)use_hash.get(op)));
    }
  }
 
  /**
  this method, takes a usehash for a node, and combines its contents with those already
  in the super blocks usehash
  */
  public void mergeInUseHash(BlockNode root, UseHash use_hash) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    UseHash use_hash_tmp = newHyperBlock.useHash;
    for (Iterator opIt = ((UseHash)use_hash.clone()).keySet().iterator();
	 opIt.hasNext();){
      Operand op = (Operand) opIt.next();   
      if(use_hash_tmp.containsKey(op))
       ((ArrayList)use_hash_tmp.get(op)).addAll((ArrayList)use_hash.get(op));
      else
	use_hash_tmp.put(op, new ArrayList((ArrayList)use_hash.get(op)));
    }
    
  }

  public UseHash getUseHash(BlockNode root) {
    if(!containsKey(root))
      createHyperBlock(root);
  
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    return newHyperBlock.useHash;
  
  }
  
  public boolean containsNode(BlockNode root, BlockNode node) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    if(newHyperBlock != null)
      return newHyperBlock.nodeSet.contains(node);
    else {
      return false;
    }
  }
  
  public HashSet getNodeSet(BlockNode root) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    if(newHyperBlock != null)
      return newHyperBlock.nodeSet;
    else {
      HashSet nodeSetTmp = new HashSet();
      nodeSetTmp.add(root);
      return nodeSetTmp;
    }
  }
  
  public void addToSet(BlockNode root, BlockNode newNode) {
    addToSet(root, newNode, getNodeSet(newNode));
  }
  
  public void killNode(BlockNode root) {
    if(_node2HyperBlockMap.containsKey(root)) 
      remove(root);
  }
  
  public void addToSet(BlockNode root, BlockNode newNode, HashSet nodeSet) {
    HyperBlockListData oldHyperBlock = ((HyperBlockListData)super.get(root));
    for (Iterator nodeIt = nodeSet.iterator(); nodeIt.hasNext();){
      BlockNode nodeTmp = (BlockNode)nodeIt.next();
      _node2HyperBlockMap.put(nodeTmp, root);
      oldHyperBlock.nodeSet.add(nodeTmp);
      addInstructions(root, getInstructionList(nodeTmp));
    }
  }
  
  public void saveInEdges(BlockNode root, HashSet inEdges) {
    HyperBlockListData hyperBlock = ((HyperBlockListData)super.get(root));
    hyperBlock.inEdges = inEdges;
  }
  public HashSet getInEdges(BlockNode root) {
    HyperBlockListData hyperBlock = ((HyperBlockListData)super.get(root));
    if(hyperBlock != null)
      return hyperBlock.inEdges;
    else
      return new HashSet(root.getInEdges());
  }
  public int getInDegree(BlockNode root) {
    HyperBlockListData hyperBlock = ((HyperBlockListData)super.get(root));
    if(hyperBlock != null)
      return hyperBlock.inEdges.size();
    else
      return root.getInDegree();
  }
  public void saveOutEdges(BlockNode root, HashSet outEdges) {
    HyperBlockListData hyperBlock = ((HyperBlockListData)super.get(root));
    hyperBlock.outEdges = outEdges;
  }
  public HashSet getOutEdges(BlockNode root) {
    HyperBlockListData hyperBlock = ((HyperBlockListData)super.get(root));
    if(hyperBlock != null)
      return hyperBlock.outEdges;
    else
      return new HashSet(root.getOutEdges());
  }
  public int getOutDegree(BlockNode root) {
    HyperBlockListData hyperBlock = ((HyperBlockListData)super.get(root));
    if(hyperBlock != null)
      return hyperBlock.outEdges.size();
    else
      return root.getOutDegree();
  }
  
  public void resetChildList(BlockNode root) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    newHyperBlock.nextNodes = new HashSet();
  }
  
  public void saveNextNode(BlockNode root, BlockNode nextNode) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    newHyperBlock.nextNodes.add(nextNode);
  }
  
  public void deleteFromNextSet(BlockNode root, BlockNode nextNode) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    newHyperBlock.nextNodes.remove(nextNode);
  }
  
  public HashSet getChildren(BlockNode root) {
    HyperBlockListData newHyperBlock = ((HyperBlockListData)super.get(root));
    if(newHyperBlock != null)
      return newHyperBlock.nextNodes;
    else {
      HashSet children = new HashSet();
      for (Iterator it = getOutEdges(root).iterator(); it.hasNext();){
        BlockEdge out = (BlockEdge) it.next();
        BlockNode nodetmp = _node2HyperBlockMap.get((BlockNode)out.getSink());
        children.add(nodetmp);
      }
      return children;
    }
  }
  
  /**
  This method is similar to the isMergeable method in BlockNode, except that it
  does the same for HyperBlocks
  */
  public boolean isMergeable(BlockNode root) {
    //check if this is not the root of a hyperblock and if not use BlockNode Method:
    if(!super.containsKey(root)) 
      return root.isMergeable();
      
    String name = root.getLabel().getFullName();
    // lets not merge the entry and exit blocks
    if ("GlobalEntry".equals(name) || "GlobalExit".equals(name)) 
      return false;
    return (getInDegree(root) == 1);
  }
  
  
  /**
  This method lets me put together in one place all the tasks necessary to 
  save the fact that two nodes have been merged serially.  Note: it is not
  actually merging the blocks--it is only saving the fact that they need
  to be merged serially (or cereally if you're hungry and it's time for 
  breakfast).
  */
  public void mergeSerial(BlockNode root, BlockNode node, BlockEdge mergeEdge) {
  
    //make HyperBlock for root
    createHyperBlock(root);
    //_node2HyperBlockMap.put(node, root);
    
    //save node to set of nodes in this HyperBlock
    addToSet(root, node);
    
    //save in edges
    HashSet inEdges = new HashSet();
    for (Iterator inEdgIt = getInEdges(root).iterator(); inEdgIt.hasNext();){
      BlockEdge inEdge = (BlockEdge)inEdgIt.next();
      inEdges.add(inEdge);
      BlockNode inNode = _node2HyperBlockMap.get((BlockNode)inEdge.getSource());
      if(inNode != root)
        updateOutputs(inNode);
      
    }
    for (Iterator inEdgIt = getInEdges(node).iterator(); inEdgIt.hasNext();){
      BlockEdge inEdge = (BlockEdge)inEdgIt.next();
      if(inEdge != mergeEdge) {
    	inEdges.add(inEdge);
        BlockNode inNode = _node2HyperBlockMap.get((BlockNode)inEdge.getSource());
        updateOutputs(inNode);
      }
    }
    saveInEdges(root, inEdges); //this overwrites what was there before
    
    //save out edges and next nodes:
    HashSet outEdges = new HashSet();
    resetChildList(root);
    for (Iterator outEdgIt = getOutEdges(root).iterator(); outEdgIt.hasNext();){
      BlockEdge outEdge = (BlockEdge)outEdgIt.next();
      BlockNode outNode = _node2HyperBlockMap.get((BlockNode)outEdge.getSink());
      if((outEdge != mergeEdge)&&//this tests the same as the anded part, but can't get all cases but is faster
         ((!getNodeSet(root).contains(outNode))||
	  (outNode == root))) {
    	outEdges.add(outEdge);
	saveNextNode(root, outNode);
        if(outNode == root) continue;
        updateInputs(outNode);
      }
    }
    for (Iterator outEdgIt = getOutEdges(node).iterator(); outEdgIt.hasNext();){
      BlockEdge outEdge = (BlockEdge)outEdgIt.next();
      if(!getChildren(root).contains(outEdge.getSink())) {
    	outEdges.add(outEdge);
        BlockNode outNode = _node2HyperBlockMap.get((BlockNode)outEdge.getSink());
	saveNextNode(root, outNode);
        if(outNode == root) continue;
        updateInputs(outNode);
      }
    }
    saveOutEdges(root, outEdges); //this overwrites what was there before
    
    //if we've merged root with a hyperblock, we need to delete the second hyperblock
    killNode(node); //this isn't killing the node from the graph, but rather
                    //from a list of nodes we must consider.
  }
  
  /**
  * This method generates groups of nodes that will be merged together They
  should be treated the as one block when deciding whether to place new Loads
  and Stores in for copying block variables.
      
      copied and modified from fp/passes/MergeSerialBlocks.java
  */
  public void genMergeBlockGroupsSerial(BlockGraph graph) {
    Set replacedVertices = new HashSet();
    boolean getNext = true;
    BlockNode curr_node = null;
    BlockNode root = null;
    HashMap edgeSets = new HashMap();
    Iterator vIt = new ArrayList(graph.getAllNodes()).iterator();
    while (vIt.hasNext()) {
      if (getNext) {
        curr_node = (BlockNode)vIt.next();
      } // end of if ()
      
      if((_node2HyperBlockMap.containsKey(curr_node))&&
         (curr_node != _node2HyperBlockMap.get(curr_node)))
        continue;
      
      if (replacedVertices.contains(curr_node)) {
        continue;
      } // end of if ()
      else if(getNext){
	root = curr_node;
		
      }
      getNext = true;
      

      // do I need to keep these?
      if (curr_node == graph.EXIT) continue;

      
      // now look down all of the out edges
      for (Iterator outIt = getOutEdges(curr_node).iterator();
           outIt.hasNext();){
        BlockEdge out_edge = (BlockEdge) outIt.next();
        BlockNode next_node = _node2HyperBlockMap.get((BlockNode)out_edge.getSink());
	
	// don't remove if this is a loopback edge or a channel or a leaf
        if( next_node == curr_node 
	    || (next_node == graph.ENTRY) 
	    || (next_node == graph.EXIT) ) {
          continue;
        }
        if (curr_node == graph.ENTRY) continue;
        

        // if the in-degree is greater than one, check if same source
        if( getInDegree(next_node) > 1 ) {
          HashSet in_edges = getInEdges(next_node);
          BlockNode prev_node = null;
          boolean different_sources = false;

          for (Iterator inIt = in_edges.iterator(); inIt.hasNext();){
            BlockEdge in_edge = (BlockEdge)inIt.next();
            if( prev_node == null || 
	        prev_node == _node2HyperBlockMap.get((BlockNode)in_edge.getSource())) {
              prev_node = _node2HyperBlockMap.get((BlockNode)in_edge.getSource());
            } else {
              different_sources = true;
            }
          }
          // if there are different sources, leave this one in
          if( different_sources ) {
            continue;
          }
        }
        
	
        if (replacedVertices.contains(next_node)) {
          continue;
        } 
	_mergeStack.push(root, next_node, out_edge, false);
	
	mergeSerial(root, next_node, out_edge);
		
        replacedVertices.add(next_node);
        getNext = false;
      }
    }
  }
  
  /**
  This is for updating the set of input edges for a hyperblock after a parent hyperblock
  has been changed