dependenceflowgraph.java

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

      DependenceFlowEdge edge = (DependenceFlowEdge)it5.next();
      DependenceFlowNode pdfn = (DependenceFlowNode)edge.getSource();
      if(pdfn.getInstruction() == null) continue;
      InstructionList.InstructionObject pObj = pdfn.getInstructionObj();
      DependenceFlowNode cdfn = (DependenceFlowNode)edge.getSink();
      if(cdfn.getInstruction() == null) continue;
      //System.out.println("is conn between " + pdfn + " and " + cdfn + " recursive?");
      if(((pObj.isAnOutPrimal())||(isStoredToPrimal(pdfn)))&&
          (isSCCAndOneNotBackPointing((Node)pdfn, (Node)cdfn))) {
        edge.setBackWardsPointing();
        //dcfeTmp.setLabel("Control Dependency Flow Edge: backwards pointing");
         //System.out.println("makeing  " + pdfn + " to " + cdfn + " backpointing");
        if(isLoop)
          isBlockRecursive = true;
      }
      
    }
    return isBlockRecursive;
  }
  
  public void addCntrlEdges(BlockNode bn, HashSet iList) {
  
      BooleanEquation edgepred = null;
      Set out_edges = new HashSet();
      out_edges.addAll(bn.getOutEdges());
      BooleanEquation edgePredicate = null;
      for (Iterator it = out_edges.iterator(); it.hasNext();) {
        BlockEdge outEdge = (BlockEdge)it.next();
        if(outEdge.isBackwardEdge()) 
          edgepred = new BooleanEquation(outEdge.getPredicate());
      }
      
      //block is recursive and so control edges are interesting
      if(edgepred != null) {
        LinkedList BoolsTmp = edgepred.listBooleanOperands();
        DefHash defHash2 = bn.getDefHash();
        for(Iterator it1 = BoolsTmp.iterator(); it1.hasNext();) {
          Operand op_Operand = (Operand)it1.next();
          if(defHash2.containsKey(op_Operand)) {
            Instruction sourceInst = (Instruction)defHash2.get(op_Operand);
	    for(Iterator it3 = iList.iterator(); it3.hasNext();) {
              Instruction sinkInst = (Instruction)it3.next();
              DependenceCntrlFlowEdge dcfe = new DependenceCntrlFlowEdge(
	               (DependenceFlowNode)_inst2NodeMap.get(sourceInst),
		       (DependenceFlowNode)_inst2NodeMap.get(sinkInst), 
		       "");
	      this.addEdge(dcfe);
              dcfe.setBackWardsPointing();
         //System.out.println("adding backpointing cntrl edge between  " + sourceInst + " and " + sinkInst);
              //dcfe.setLabel("Control Dependency Edge: backwards pointing");
            }
          }
        }
        
      }
  
  
  }
   
   
  /** check if the output is stored to primal by the next instruction
   * 
   * @param node DependenceFlowNode to check
   * @return true if the output from this is stored to a primal in the next 
   *         instruction
   */
  public boolean isStoredToPrimal(DependenceFlowNode node) {
    if(doesLaterNodeDefPrimal(node, node, new ArrayList()))
      return false;
    for (Iterator nodeIt = node.getOutEdges().iterator(); 
    	 nodeIt.hasNext(); ) {
      DependenceFlowEdge edge = (DependenceFlowEdge)nodeIt.next();
      if(((DependenceFlowNode)edge.getSink()).getInstruction() == null) continue;
      
      
      if((((DependenceFlowNode)edge.getSink()).getInstruction().isStore())&&
         (((DependenceFlowNode)edge.getSink()).getInstruction()
	                                         .getOperand(0).isPrimal()))
        return true;
    }
    return false;
  }
   
   /** this method checks to make sure that there is not a pimal defined within this
   *   loop; it's better to make that primal def instruction the back edge.
   * 
   * @param startNode  
   * @param currentNode 
   * @return whether such a connection exists
   */
  private boolean doesLaterNodeDefPrimal(DependenceFlowNode startNode, 
                                        DependenceFlowNode currentNode,
                                        ArrayList alreadyVisited) {
    Set outEdges = currentNode.getOutEdges();
    boolean flag = false;
    if(outEdges.size()>0){
      for (Iterator it2 = outEdges.iterator(); it2.hasNext() && 
           flag == false;) {
        DependenceFlowEdge outEdge = (DependenceFlowEdge)it2.next();
        if(!startNode.isInSameSCC(outEdge.getSink()))
	  continue;
	if(isOutputPrimal((DependenceFlowNode)outEdge.getSink())) 
          return true;
        //if(outEdge.getSink()==startNode) 
        //  return false;
        
	//else 
	if(!alreadyVisited.contains(outEdge.getSink())){
          alreadyVisited.add(outEdge.getSink());
          flag = doesLaterNodeDefPrimal(startNode, (DependenceFlowNode)outEdge.getSink(), 
	                                alreadyVisited);
        }
      }
    }
    return flag;
     
  }

 /** check if at least one defined operand is primal
   * 
   * @param node_DependenceFlowNode 
   * @return true if at least one def is primal
   */
  public boolean isOutputPrimal(DependenceFlowNode node_DependenceFlowNode) {
    for(int n_int=0;n_int<node_DependenceFlowNode
                                 .getInstruction().getNumberOfDefs(); 
            n_int++) {
      if(node_DependenceFlowNode.getInstruction().getOperand(n_int).isPrimal()){
        return true;
	}
    }
    return false;
  }
   
   
   
  //copied from Graph.java with addition of checking to see if edge is backpointing
  /** this method was copied from Graph.java, but slightly edited.  It checks to 
   *  see if there is a connection between two nodes that does not pass through 
   *  a recursive edge.
   * 
   * @param startNode_Node 
   * @param currentNode 
   * @param alreadyVisited 
   * @return whether such a connection exists
   */
  //private HashSet _setOfSCCs = new HashSet();
  //private HashSet _alreadyFoundInSCC = new HashSet();
  private HashSet _notInSCC = new HashSet();
  private HashSet _alreadyCheckedIfNotInSCC = new HashSet();
  public boolean isSCCAndOneNotBackPointing(Node startNode, 
                                            Node currentNode) {
  
    //if this is true either they are in separate SCCs or if they are in the same
    //since it was already found, an edge must have been backwardspointing already
    //(this is only safe, because I first check if we're looking at the place where
    //I will set an edge to be backwardspointing.)
    //if((_alreadyFoundInSCC.contains(startNode))&&
    //   (_alreadyFoundInSCC.contains(currentNode)))			    
   //   return false;
    
    //if one of them is not in an scc no checking is necessary
    if((_notInSCC.contains(startNode))||
       (_notInSCC.contains(currentNode)))
      return false;
    
    if(!_alreadyCheckedIfNotInSCC.contains(startNode)) {
       _alreadyCheckedIfNotInSCC.add(startNode);
       if(!startNode.isSCC())
         _notInSCC.add(startNode);
    }
    boolean flag = isSCCAndOneNotBackPointingRec(startNode, currentNode, 
                                                 new ArrayList());
   // if(flag)
    //  	_alreadyFoundInSCC.add(startNode);			    
    return flag;
  }
  
  public boolean isSCCAndOneNotBackPointingRec(Node startNode, 
                                               Node currentNode,
                                               ArrayList alreadyVisited) {
    Set outEdges = currentNode.getOutEdges();
    boolean flag = false;
    if(outEdges.size()>0){
      for (Iterator it2 = outEdges.iterator(); it2.hasNext() && 
            flag == false;) {
        DependenceFlowEdge outEdge = (DependenceFlowEdge)it2.next();
        if(((DependenceFlowNode)outEdge.getSink()).getInstruction() == null) 
	  continue;
        if(outEdge.getisBackWardsPointing()) continue;
	if(_notInSCC.contains(currentNode)) continue;
	if(!_alreadyCheckedIfNotInSCC.contains(currentNode)) {
	   _alreadyCheckedIfNotInSCC.add(currentNode);
	   if(!currentNode.isSCC()) {
             _notInSCC.add(currentNode);
	     continue;
	   }
	}
	if(outEdge.getSink() == startNode) {
          return true;
        }
        else if(!alreadyVisited.contains(outEdge.getSink())){
          alreadyVisited.add(outEdge.getSink());
          flag = isSCCAndOneNotBackPointingRec(startNode, outEdge.getSink(), 
	                                       alreadyVisited);
          //if(flag)
	  //  _alreadyFoundInSCC.add(outEdge.getSink());
	}
      }
    }
    return flag;
     
  }
  
  
  
  /** 
   * Returns the nodes that have no outgoing edges.  If all the edges are
   * drawn to point down, these nodes are at the bottom of the graph.  NOTE:
   * This set is not just a copy.  If you alter it, you will alter the
   * graph itself.
   */
  public Set getBottomSinks() {
    return _bottomSinks;
  }
  
  /** 
   * Returns the name of <code>cls</code>, which is simple except for arrays
   * 
   * @param cls 
   */
  private String getName(Class cls) {
    if (cls == null) {
      return "null";
    } // end of if ()
    else if (cls.isArray()) {
      return getName(cls.getComponentType()) + "[]";
    } // end of else if ()
    else {
      return cls.getName();
    } // end of else
  }
  
  /** 
   * Instantiates a DependenceFlowNode
   */
  protected Node newNode() {
    return new DependenceFlowNode(null, null);
  }
  
  /** 
   * Instantiates a DependenceFlowEdge
   */
  protected Edge newEdge() {
    return new DependenceFlowEdge();
  }
  
  /** 
   * Also replaces <code>oldNode</code> in the set of top sources and bottom
   * sinks
   * 
   * @param oldNode 
   * @param newNode 
   */
  public void replaceNode(Node oldNode, Node newNode) {
    super.replaceNode(oldNode, newNode);
    Set topSources = getTopSources();
    if (topSources.contains(oldNode)) {
      topSources.remove(oldNode);
      topSources.add(newNode);
    } // end of if ()
    Set bottomSinks = getBottomSinks();
    if (bottomSinks.contains(oldNode)) {
      bottomSinks.remove(oldNode);
      bottomSinks.add(newNode);
    } // end of if ()
  }
  
   
  /** 
   * Appends the type of each node to its label before calling
   * <code>super.toDot()</code>
   */
  public String toDot() {
    Iterator iter = getAllNodes().iterator();
    StringBuffer sb = new StringBuffer();
    while (iter.hasNext()) {
      DependenceFlowNode node = (DependenceFlowNode) iter.next();
      sb.delete(0, sb.length());
      sb.append(node.getPrimaryDotLabel()).append('\n');
      Class type = node.getType();
      sb.append(getName(type));
      int line = node.getSourceLine();
      if (line != DependenceFlowNode.UNKNOWN_LINE) {
        sb.append('\n').append("line: ").append(line);
      } // end of if ()
      node.setDotAttribute("label", sb.toString());
    }
    String dotString = super.toDot();
    String dotStringMinSubStr = new String();
    String dotStringMaxSubStr = new String();
    dotStringMinSubStr = "{rank = minrank; ";
    dotStringMaxSubStr = "{rank = maxrank; ";
    int lastIndex = dotString.lastIndexOf("}");
    dotString = dotString.substring(0, lastIndex-1);
    dotString = dotString + "{rank = source; " + _sTART.getDotName() + "}\n";
    for (Iterator it = getAllNodes().iterator(); it.hasNext();) {
      DependenceFlowNode node = (DependenceFlowNode) it.next();
      if((node != _sTART)&&(node != _sTART)) {
    	dotStringMinSubStr = dotStringMinSubStr + node.getDotName() + "; ";
    	dotStringMaxSubStr = dotStringMaxSubStr + node.getDotName() + "; ";
      }
       
    }  
    dotStringMinSubStr = dotStringMinSubStr + "}\n";
    dotStringMaxSubStr = dotStringMaxSubStr + "}\n";
    dotString = dotString + dotStringMinSubStr;
    dotString = dotString + dotStringMaxSubStr;
    dotString = dotString + "{rank = source; " + _sTOP.getDotName() + "}\n";
    dotString = dotString + "}\n";
    return dotString;
  }
}