hyperblocklist.java

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

  */
  public void updateInputs(BlockNode node) {
    createHyperBlock(node);
    HashSet inEdges = new HashSet();
    HashSet prevNodes = new HashSet();
    for (Iterator inEdgIt = getInEdges(node).iterator(); inEdgIt.hasNext();){
      BlockEdge inEdge = (BlockEdge)inEdgIt.next();
      BlockNode prevNodeTmp = (BlockNode)inEdge.getSource();
      BlockNode prevNode = _node2HyperBlockMap.get(prevNodeTmp);
      if(!prevNodes.contains(prevNode)) {
        inEdges.add(inEdge);
	prevNodes.add(prevNode);
      }
    }
    saveInEdges(node, inEdges); //this overwrites what was there before
    
  }
  /**
  This is for updating the set of out edges for a hyperblock after a child hyperblock
  has been changed
  */
  public void updateOutputs(BlockNode node) {
  
    createHyperBlock(node);
    HashSet outEdges = new HashSet();
    resetChildList(node);
    HashSet nextNodes = new HashSet();
    for (Iterator outEdgIt = getOutEdges(node).iterator(); outEdgIt.hasNext();){
      BlockEdge outEdge = (BlockEdge)outEdgIt.next();
      BlockNode nxtNodeTmp = (BlockNode)outEdge.getSink();
      BlockNode nxtNode = _node2HyperBlockMap.get(nxtNodeTmp);
      if(!nextNodes.contains(nxtNode)) {
        saveNextNode(node, nxtNode);
        outEdges.add(outEdge);
	nextNodes.add(nxtNode);
      }
    }
    saveOutEdges(node, outEdges); //this overwrites what was there before
  }  
  /**
  This method lets me put together in one place all the tasks necessary to 
  save the fact that two nodes have been merged parallel.  Note: it is not
  actually merging the blocks--it is only saving the fact that they need
  to be merged parallely.
  */
  public void mergeParallel(BlockNode node1, BlockNode node2) {
  
    //make HyperBlock for node1 (if one does not already exist)
    createHyperBlock(node1);
    _node2HyperBlockMap.put(node2, node1);
    
    
    //save node2 to set of nodes in this HyperBlock
    addToSet(node1, node2);
    
    //save in edges
    HashSet inEdges = new HashSet();
    for (Iterator inEdgIt = getInEdges(node1).iterator(); inEdgIt.hasNext();){
      BlockEdge inEdge = (BlockEdge)inEdgIt.next();
      inEdges.add(inEdge);
      BlockNode inNode = _node2HyperBlockMap.get((BlockNode)inEdge.getSource());
      if(inNode == node1) continue;
      updateOutputs(inNode);
      
    }
    //we only need to save node1's in edges, because for a parallel merge to happen 
    //each node must have only one input edge and the input edge from each of them
    //must have one source.  We only want to remember the edge going from the source
    //to the new root node
    saveInEdges(node1, inEdges); //this overwrites what was there before
    
    //save out edges and next nodes:
    HashSet outEdges = new HashSet();
    resetChildList(node1);
    for (Iterator outEdgIt = getOutEdges(node1).iterator(); outEdgIt.hasNext();){
      BlockEdge outEdge = (BlockEdge)outEdgIt.next();
      outEdges.add(outEdge);
      BlockNode outNode = _node2HyperBlockMap.get((BlockNode)outEdge.getSink());
      saveNextNode(node1, outNode);
      if(outNode == node1) continue;
      updateInputs(outNode);
    }
    for (Iterator outEdgIt = getOutEdges(node2).iterator(); outEdgIt.hasNext();){
      BlockEdge outEdge = (BlockEdge)outEdgIt.next();
      BlockNode outNode = _node2HyperBlockMap.get((BlockNode)outEdge.getSink());
      if((!getChildren(node1).contains(outNode))&&
          ((!getNodeSet(node1).contains(outEdge.getSink()))||
	  (outEdge.getSink() == node1))) {
    	outEdges.add(outEdge);
	saveNextNode(node1, outNode);
        if(outNode == node1) continue;
        updateInputs(outNode);
      }
    }
    saveOutEdges(node1, outEdges); //this overwrites what was there before
    
    //if we've merged node1 with a hyperblock, we need to delete the second hyperblock
    killNode(node2); //this isn't killing the node from the graph, but rather
                     //from a list of nodes we must consider.
  }
  
  /**
      
      copied and modified from fp/passes/MergeParallelBlocks.java
  */
  //private boolean _merged;
  public void genMergeBlockGroupsParallel(BlockGraph graph) {
  
    BlockNode source = (BlockNode)graph.ENTRY;
    
    /// give a magic number a name
    //the code that used this in mergeparallelblocks was commented out!
    //boolean parent_is_decision = false;

    // merge parallel vertices
    // should we invent some "visitor style" classes and 
    // have a recursive visit ?
    recurseMergeBlocks(graph, source);

    // do this before ? or everyone always fixes them
    graph.resetMarkers(); 
    
  
  }
  
  /**
   * This method is supposed to go through all of the vertices and merge those 
   * which have the same source but different predicates.
   **/

  public BlockNode recurseMergeBlocks(BlockGraph graph, BlockNode node) {

    // base case, the node has been seen before
    
    if( node.isMarked()) {
      return node;
    }
    // mark this vertex as visited
    node.setMark();

    if (getOutDegree(node) == 2) {

      // get the out edges
      BlockEdge merged_edge = null;
      Iterator out_edge_it = getOutEdges(node).iterator();
      
      BlockEdge edge1 = (BlockEdge) out_edge_it.next();
      BlockEdge edge2 = (BlockEdge) out_edge_it.next();
      
      // merge all lower vertices
      BlockNode merged_node = null;
      BlockNode node1tmp = recurseMergeBlocks(graph, (BlockNode)edge1.getSink());
      BlockNode node1 = _node2HyperBlockMap.get(node1tmp);
      BlockNode node2tmp = recurseMergeBlocks(graph, (BlockNode)edge2.getSink());
      BlockNode node2 = _node2HyperBlockMap.get(node2tmp);

      // if both edges go to the same node (See Merge3Test) combine them
      if (node1 == node2) {
        edge1 = (BlockEdge)getOutEdges(node).iterator().next();
        // merge up
        if (isMergeable(node1)) {
	  mergeSerial(node, node1, edge1);
	  _mergeStack.push(node, node1, edge1, false);
        }
      } else if( isMergeable(node1) && isMergeable(node2) ) {
      // now merge the deeper node into the more shallow one
        //need to come back here and decide how to handle parallel when really merging
	if( node1.getDepth() < node2.getDepth() ) {
	  // I think I will change this to be graph code.
          _mergeStack.push(node2, node1, true);
	  merged_edge = edge2;
          merged_node = node2;
	  mergeParallel(node2, node1);
        } else {
          _mergeStack.push(node1, node2, true);
          merged_edge = edge1;
          merged_node = node1;
	  mergeParallel(node1, node2);
        }
	
	
	//check if new node would be mergable
        // merge up
	if(( isMergeable(merged_node))&&
	   (_node2HyperBlockMap.get(node) != 
	    _node2HyperBlockMap.get(merged_node)) ) {
	  mergeSerial(node, merged_node, merged_edge);
	  _mergeStack.push(node, merged_node, merged_edge, false);
        }

      }
    } else if (getOutDegree(node) == 1 && node != graph.ENTRY) {
      // get the out edge
      BlockEdge edge1 = (BlockEdge)getOutEdges(node).iterator().next();

      BlockNode node1tmp = recurseMergeBlocks(graph, (BlockNode)edge1.getSink());
      BlockNode node1 = _node2HyperBlockMap.get(node1tmp);
     // merge all lower vertices
      if (isMergeable(node1)) {
	mergeSerial(node, node1, edge1);
	_mergeStack.push(node, node1, edge1, false);
      }
    }
    // now go to the next vertices and check
    //for (Iterator it = getOutEdges(node).iterator(); it.hasNext();){
    for (Iterator it = getChildren(node).iterator(); it.hasNext();){
      BlockNode nodetmp = (BlockNode) it.next();
      recurseMergeBlocks(graph, nodetmp);
    }
    return node;
  }
  
  /*public void mergeNodesIntoHyperBlock(BlockNode setNode, BlockNode newNode,
                                       boolean addInstsb4) {
    HyperBlockListData hyperBlock = (HyperBlockListData)_node2HyperBlockMap.get(setNode);
    BlockNode root = hyperBlock.root;
    addToSet(root, newNode);
    
    /**
    in the parallel merge algorithm, sometimes blocks are added later than they are in the 
    graph, which messes up the instruction order.  An example of this is when one block
    is connected to two parallel blocks.  If the two parallel blocks can be merged, and if 
    the resultant block can be merged up into the top block, this algorithm would first save
    the list of instructions from each of the parallel blocks, and then from the block above,
    but the block above's instructions should be earlier in the list, since they should happen
    before.  So in these cases I add the instructions to the top of the list instead of the end.
    Another example of when this might be necessary, is if a child block was somehow reached and 
    saved to the hyperblock before one of its parents.  Its instructions will have already been 
    saved to the hyperblock instruction list.  But the parent who is being added now, needs to have
    its instructions saved above the child's.  
    
    There is one serious problem with this!  The instructions may not need to be placed at 0!  
    There may be other blocks above this parent!  But child blocks parallel to the child being
    considered at the moment may be above this child in the list, and the parent needs to be 
    above those children.  How to know how far up to put the parent instructions???
    
    if(addInstsb4) {
      addInstructions(root, newNode.getInstructions(), 0);
    }
    else
      addInstructions(root, newNode.getInstructions());
    deleteFromNextSet(root, newNode);
    _node2HyperBlockMap.put(newNode, hyperBlock);

    mergeInMultiDefHash(root, newNode.getInstructions());

    UseHash use_hash_tmp = newNode.getUseHash();
    mergeInUseHash(root, use_hash_tmp);
    for (Iterator it = newNode.getOutEdges().iterator(); it.hasNext();){
      BlockEdge out = (BlockEdge) it.next();
      BlockNode child = (BlockNode)out.getSink();
      if(!getNodeSet(root).contains(child))
        saveNextNode(root, child);
      else
        saveNextNode(root, root);
    }
  
  }
  
  public boolean mergeNodes(BlockNode node1, BlockNode node2) {
    if((!_node2HyperBlockMap.containsKey(node1))&&
       (!_node2HyperBlockMap.containsKey(node2))) {
      createHyperBlock(node1);
      _node2HyperBlockMap.put(node1, get(node1));
      mergeInMultiDefHash(node1, node1.getInstructions());

      UseHash use_hash_tmp0 = node1.getUseHash();
      putAllInUseHash(node1, use_hash_tmp0);
      
      mergeNodesIntoHyperBlock(node1, node2, false);
      
      mergeNodesIntoHyperBlock(node2, node1, true);

      
      
    }
    else if((_node2HyperBlockMap.containsKey(node1))&&
    	    (!_node2HyperBlockMap.containsKey(node2))) {
      
      mergeNodesIntoHyperBlock(node1, node2, false);

    }
    else if((!_node2HyperBlockMap.containsKey(node1))&&
    	    (_node2HyperBlockMap.containsKey(node2))) {
      
      mergeNodesIntoHyperBlock(node2, node1, true);

    }
    else if((_node2HyperBlockMap.containsKey(node1))&&
    	    (_node2HyperBlockMap.containsKey(node2))&&
	    (_node2HyperBlockMap.get(node1) != _node2HyperBlockMap.get(node2))) {
      HyperBlockListData rootHyperBlock = (HyperBlockListData)_node2HyperBlockMap.get(node1);
      BlockNode root = rootHyperBlock.root;
      HyperBlockListData childHyperBlock = (HyperBlockListData)_node2HyperBlockMap.get(node2);
      BlockNode cRoot = childHyperBlock.root;
      
      rootHyperBlock.nodeSet.addAll(childHyperBlock.nodeSet);
      for(Iterator esIt2 = childHyperBlock.nodeSet.iterator();
             esIt2.hasNext();){
        BlockNode nodeTmp = (BlockNode) esIt2.next();
        _node2HyperBlockMap.put(nodeTmp, rootHyperBlock);
      }     
      for(Iterator esIt2 = childHyperBlock.nextNodes.iterator();
             esIt2.hasNext();){
        BlockNode nextNodeTmp = (BlockNode) esIt2.next();
        if(!getNodeSet(root).contains(nextNodeTmp))
          saveNextNode(root, nextNodeTmp);
	else
	  saveNextNode(root, root);
      }     
      //rootHyperBlock.nextNodes.addAll(childHyperBlock.nextNodes);
      addInstructions(root, childHyperBlock.instructions);
      MultiDefHash def_hash_tmp = childHyperBlock.defHash;
      getCombineMultiDefHashes(root, def_hash_tmp);
      UseHash use_hash_tmp = childHyperBlock.useHash;
      mergeInUseHash(root, use_hash_tmp);
      
      remove(cRoot);
    }
    else 
      return false;
    return true;
  }*/
  
}