dependenceflowgraph.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 fp.graph.Edge;
import fp.graph.Graph;
import fp.graph.Node;
import fp.util.*;
import fp.hardware.*;

import java.util.*;

/** 
 * A data-flow graph for a basic block in a procedure/method/function
 * 
 * @author Nathan Kitchen
 * copied and modified by Kris Peterson
 */
public class DependenceFlowGraph extends Graph {
  static private int count = 0;
  /** 
   * The nodes with no incoming edges
   */
  private HashSet _topSources;
  
  /** 
   * The nodes with no outgoing edges
   */
  private HashSet _bottomSinks;
   
  //saving top and bottom of graph:
  private DependenceFlowNode _sTART;
  private DependenceFlowNode _sTOP;
  
  /**
  these both map instructions to Nodes, but the second one creates a new node if
  no mapping is found.
  */
  private HashMap _inst2NodeMap;
  private InstToNodeMap _inst2NodeGenAndMapper;
  
  private ALoadNAStoreHandler _loadStoreHandler;
  
  /** 
   * Constructs a new unnamed data flow graph
   */
  public DependenceFlowGraph() {
    this(null);
  }
   
  /** 
   * Constructs a new named data flow graph
   * 
   * @param name 
   */
  public DependenceFlowGraph(String name) {
    super(name);
    _topSources = new HashSet();
    _bottomSinks = new HashSet();
    _sTART = new DependenceFlowNode(null);
    _sTOP = new DependenceFlowNode(null);
    _sTART.setPrimaryDotLabel("sTART");
    _sTOP.setPrimaryDotLabel("sTOP");
    this.addNode(_sTART);
    this.addNode(_sTOP);
    _inst2NodeMap = new HashMap();
    _inst2NodeGenAndMapper = new InstToNodeMap();
    _loadStoreHandler  = new ALoadNAStoreHandler();
  }
  
  /** return the start node
   * 
   * @return return the start node
   */
  public DependenceFlowNode sTART(){return _sTART;}
  /** return the stop node
   * 
   * @return return the stop node
   */
  public DependenceFlowNode sTOP(){return _sTOP;}
  /** save the start node
   * 
   * @param s_DependenceFlowNode 
   */
  public void saveSTART(DependenceFlowNode s){_sTART = s;}
  /** save the stop node
   * 
   * @param s_DependenceFlowNode 
   */
  public void saveSTOP(DependenceFlowNode s){_sTOP = s;}
  
  
  /** 
   * Returns the nodes that have no incoming edges.  If all the edges are
   * drawn to point down, these nodes are at the top of the graph.  NOTE:
   * This set is not just a copy.  If you alter it, you will alter the
   * graph itself.
   */
  public Set getTopSources() {
    return _topSources;
  }

  public DependenceFlowNode findNode(Instruction i) {
    
    if(_inst2NodeMap.containsKey(i))
      return (DependenceFlowNode)_inst2NodeMap.get(i);
    for (Iterator it = getAllNodes().iterator(); it.hasNext(); ) {
      DependenceFlowNode node = (DependenceFlowNode)it.next();
      if(node.getInstruction() == null) continue;   
      if(node.getInstruction().toString().equals(i.toString())) {
        _inst2NodeMap.put(i, node);
	return node;
      }
    }
    
    return null;
  }

  private class InstToNodeMap extends HashMap {
  
    public InstToNodeMap(){super();}
    
    public DependenceFlowNode get(InstructionList.InstructionObject instObj) {
      if(containsKey(instObj))
        return (DependenceFlowNode)super.get(instObj);
      else {
        
	Instruction inst = instObj.inst;
	DependenceFlowNode dfn = dfn = new DependenceFlowNode(inst.getClass(), 
	                                                      inst);
        dfn.setPrimaryDotLabel(inst.toDotLabel());
        dfn.setInstruction(inst);
        dfn.setInstructionObj(instObj);
        addNode(dfn);
        DependenceCntrlFlowEdge dcfe = new DependenceCntrlFlowEdge(_sTART, dfn, 
	                                                           "");
        addEdge(dcfe);
        dcfe.setLabel("Entry Edge");
        dcfe = new DependenceCntrlFlowEdge(dfn, _sTOP, "");
        addEdge(dcfe);
        dcfe.setLabel("Exit Edge");
        
	put(instObj, dfn);
	_inst2NodeMap.put(inst, dfn);
	return dfn;
      
      }
    }
  
  }
  
  private class ALoadNAStoreHandler extends HashSet{
    private class ALoadAStorePair {
      public Instruction aloadInst;
      public Instruction astoreInst;
      public ALoadAStorePair() {}
      public ALoadAStorePair(Instruction aloadI, Instruction astoreI) {
        this();
	aloadInst = aloadI;
	astoreInst = astoreI;
      }
    }
    
    public ALoadNAStoreHandler() {
      super();
    }
    
    public void add(Instruction aloadI, Instruction astoreI) {
    
      ALoadAStorePair newPair = new ALoadAStorePair(aloadI, astoreI);
      super.add(newPair);
    
    }
    
    public boolean makeConns(boolean isLoop) {
      boolean isBlockRecursive = false;
      for (Iterator it = this.iterator(); it.hasNext(); ) {
        ALoadAStorePair pair = (ALoadAStorePair)it.next();
	if(keinRecCon(pair)) {
          DependenceDataFlowEdge ddfe = new DependenceDataFlowEdge(
	  	       (DependenceFlowNode)_inst2NodeMap.get(pair.astoreInst), 
	               (DependenceFlowNode)_inst2NodeMap.get(pair.aloadInst),"");
          addEdge(ddfe);
          ddfe.setBackWardsPointing();
          if(isLoop)
            isBlockRecursive = true;
          //ddfe.setLabel("Data Dependency Flow Edge: backwards pointing");
	  
	}
      }
      return isBlockRecursive;
    }
    
    private boolean keinRecCon(ALoadAStorePair pair) {
      DependenceFlowNode store = 
                         (DependenceFlowNode)_inst2NodeMap.get(pair.astoreInst);
      DependenceFlowNode load = 
                         (DependenceFlowNode)_inst2NodeMap.get(pair.aloadInst);
      ArrayList backEdgeToLoopEnd = new ArrayList();
      ArrayList loopEndToLoad = new ArrayList();
      ArrayList loopEndToStore = new ArrayList();
      
      if(!(store.findPathsForRecursiveArrayCheck(load, backEdgeToLoopEnd, 
        					 loopEndToLoad, loopEndToStore)))
      //if(true)
        return true;
      
      //System.out.println("backEdgeToLoopEnd " + backEdgeToLoopEnd);
      //System.out.println("loopEndToLoad " + loopEndToLoad);
      //System.out.println("loopEndToStore " + loopEndToStore);
      
      float start0 = 0;
      float loopEnd0 = start0;
      for (Iterator it2 = backEdgeToLoopEnd.iterator(); it2.hasNext();) {
        DependenceFlowNode nodeTmp = (DependenceFlowNode)it2.next();
	Instruction inst = nodeTmp.getInstruction();
        if(inst == null) continue;
        //System.out.println("inst " + inst); 
         
        if((Cast.conforms(inst))||
           (Store.conforms(inst))||
           (Load.conforms(inst))||
	   (Getelementptr.conforms(inst)))
          continue;
        else if(Binary.conforms(inst)) {
          String opName = inst.operator().toString();
          Operand firstOp = Binary.getVal1(inst);
          Operand secndOp = Binary.getVal2(inst);
          Float fstOp = null; 
          Float scndOp = null; 
	  
	  if(firstOp.isFloatConstant())
	    fstOp = new Float(((FloatConstantOperand)firstOp).getValue());
	  else if(firstOp.isDoubleConstant())
	    fstOp = new Float(((DoubleConstantOperand)firstOp).getValue());
	  else if(firstOp.isIntConstant())
	    fstOp = new Float(((IntConstantOperand)firstOp).getValue());
	  else if(firstOp.isLongConstant())
	    fstOp = new Float(((LongConstantOperand)firstOp).getValue());
	  
	  if(secndOp.isFloatConstant())
	    scndOp = new Float(((FloatConstantOperand)secndOp).getValue());
	  else if(secndOp.isDoubleConstant())
	    scndOp = new Float(((DoubleConstantOperand)secndOp).getValue());
	  else if(secndOp.isIntConstant())
	    scndOp = new Float(((IntConstantOperand)secndOp).getValue());
	  else if(secndOp.isLongConstant())
	    scndOp = new Float(((LongConstantOperand)secndOp).getValue());
	  
	  float value;
	  if(fstOp == null && scndOp == null) {
	    /*System.out.println("fst and 2nd ops null " +  inst);
	    System.out.println("fst ops " +  firstOp);
	    System.out.println("fst ops " +  fstOp);
	    System.out.println("2nd ops " +  scndOp);
	    System.out.println("2nd ops " +  secndOp);*/
	    return true;
	  }
	  value = fstOp == null ? scndOp.floatValue() : fstOp.floatValue();
	  
          if(opName.matches(".*[aA][dD][dD].*")) {
            loopEnd0 += value;
          }
          else if(opName.matches(".*[sS][uU][bB].*")) {
            loopEnd0 = fstOp == null ? loopEnd0-value : value-loopEnd0;
	    //loopEnd0 -= value;
          }
          else if(opName.matches(".*[mM][uU][lL].*")) {
	    loopEnd0 *= value;
          }
          else if(opName.matches(".*[dD][iI][vV].*")) {
            loopEnd0 = fstOp == null ? loopEnd0/value : value/loopEnd0;
	    //loopEnd0 /= value;
          }
          else if(opName.matches(".*[sS][hH][lL].*")) {
	    loopEnd0 *= Math.pow(2, value);
          }
          else if(opName.matches(".*[sS][hH][rR].*")) {
	    loopEnd0 *= Math.pow(1/2, value);
          }
           
           
        }
        else {
          return true;
	  //System.out.println("else " + inst);
	}
      }
      System.out.println("start0 " + start0 + " loopEnd0 " + loopEnd0);
      
      float aload0 = loopEnd0;
      for (Iterator it2 = loopEndToLoad.iterator(); it2.hasNext();) {
        DependenceFlowNode nodeTmp = (DependenceFlowNode)it2.next();
	Instruction inst = nodeTmp.getInstruction();
        if(inst == null) continue;
        //System.out.println("inst " + inst); 
        if((Cast.conforms(inst))||
           (Store.conforms(inst))||
           (Load.conforms(inst))||
	   (Getelementptr.conforms(inst)))
          continue;
        else if(Binary.conforms(inst)) {
          String opName = inst.operator().toString();
          Operand firstOp = Binary.getVal1(inst);
          Operand secndOp = Binary.getVal2(inst);