blockgraph.java

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

/*
 *
 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.Node;
import fp.hardware.*;
import fp.parser.LlvmLexer;
import fp.parser.LlvmParser;
import fp.util.BooleanEquation;
import fp.util.BEqToList;
import fp.util.DefHash;
import fp.util.UniqueName;
import fp.util.UseHash;

import antlr.TokenStreamException;
import antlr.RecognitionException;

import java.util.*;
import java.io.*;

public class BlockGraph extends ControlFlowGraph {
  

  // Data
  private String _source;
  private String _function;
  private BlockNode _firstBlock; // the one the entry block will point to

  private UniqueName _variableNamer;

  private HashMap _variable_hash;

  //save chip info:
  //===> moved to GlobalOptions.java
  //private ChipDef _chipDef;
  private float _aveOpsPCycle;
  private float _maxOpsPCycle;
  private float _minOpsPCycle;
  private float _opsPerBlock;
  private float _cyclesPerBlock;
  private int _totOps;
  private int _cycleCount;
  private HashMap _operatorCounts;


  // this may only be for testing...
  public BlockGraph() {
    this("onTheFly", "run", false, false);
  }

  public BlockGraph(String source, String function) {
    this(source, function, true, true);
  }

  public BlockGraph(String source, String function, boolean parse, 
		    boolean connect) {
    super(source);
    _source = source;
    _function = function;
    
    _variableNamer = new UniqueName();

    _variable_hash = new HashMap();

    setDotAttribute("label", _source + ":" + _function);
    
    ((BlockNode)ENTRY).setName("GlobalEntry");
    ((BlockNode)EXIT).setName("GlobalExit");
    
    /*
      scheduler statistics for design
    */
    _aveOpsPCycle = 0;
    _maxOpsPCycle = 0;
    _minOpsPCycle = 0;
    _opsPerBlock = 0;
    _cyclesPerBlock = 0;
    _totOps = 0;
    _cycleCount = 0;
    _operatorCounts = new HashMap(); 


    /*
      All the work of building the control-flow block is to be done
      here.

    */
    if (parse) {
      //System.out.println("Parsing llv file.");
      parseFile();
      //System.out.println("Done Parsing llv file.");
    }

    if (connect)
      connectBlocks();

    //cleanUp(something);

    // addPredicates();

  }


  private void parseFile() {
    InputStream s = null;
    try {
      s = new FileInputStream(_source);
    } catch (IOException e) {
      // I should probably invent my own set of execptions.
      System.err.println("Exception occured when reading " + _source);
      e.printStackTrace();
      System.exit(-1);
    }

    LlvmLexer lLexer = new LlvmLexer(s);
    LlvmParser lParser = new LlvmParser(lLexer);
    // this is where we would pass in "this"
    try {
      lParser.module(this); 
    } catch (TokenStreamException e) {
      System.err.println("Error parsing file "+ _source);
      System.exit(-1);
    } catch (RecognitionException e) {
      System.err.println("Error parsing file "+ _source);
      System.exit(-1);
    }
  }

  public void setSource(String s) { 
    _source = s; 
    setDotLabel();
  }

  public void setFunction(String f) { 
    _function = f; 
    setDotLabel();
  }

  //scheduler stats get and set methods:
  public void setAveOpsPCycle(float i) { _aveOpsPCycle = i; }
  public float getAveOpsPCycle() { return _aveOpsPCycle; }
  public void setMaxOpsPCycle(float i) { _maxOpsPCycle = i; }
  public float getMaxOpsPCycle() { return _maxOpsPCycle; }
  public void setMinOpsPCycle(float i) { _minOpsPCycle = i; }
  public float getMinOpsPCycle() { return _minOpsPCycle; }
  public void setOpsPerBlock(float i) { _opsPerBlock = i; }
  public float getOpsPerBlock() { return _opsPerBlock; }
  public void setCyclesPerBlock(float i) { _cyclesPerBlock = i; }
  public float getCyclesPerBlock() { return _cyclesPerBlock; }
  public void setTotOps(int i) { _totOps = i; }
  public int getTotOps() { return _totOps; }
  public void setCycleCount(int i) { _cycleCount = i; }
  public int getCycleCount() { return _cycleCount; }
  public void setOperatorCounts(HashMap i) { _operatorCounts = i; }
  public HashMap getOperatorCounts() { return _operatorCounts; }


  public void setFirstBlock(BlockNode bn) {
    _firstBlock = bn;
  }

  private void setDotLabel() {
    setDotAttribute("label", _source + ":" + _function);
  }

  protected Node newNode() {
    return new BlockNode();
  }

  protected Edge newEdge() {
    return new BlockEdge();
  }

  // convenience method for clearing all block merkers.
  public void resetMarkers() {
    for(Iterator it = getAllNodes().iterator(); it.hasNext(); ) {
      ((BlockNode) it.next()).clearMark();
    }
  }

  
  // eventually this should be private 
  protected void addPredicates() {
    //do this as a pass

  }
    

  public void addVariable(Variable var) {
    _variable_hash.put(var.getOperand(), var);
  }

  public Variable getVariable(Operand op) {
    return (Variable)_variable_hash.get(op);
  }

  public boolean hasVariable(Operand op) {
    return getVariable(op) != null;
  }

  public boolean hasExternalVariable(Operand op) {
    Variable var = getVariable(op);
    if (var != null) 
      return var.isExternal();
    else
      return false;
  }

  public ArrayList getExternalOperandNames() {
    ArrayList external = new ArrayList();
    // For each variable in this blockgraph...
    for(Iterator it = _variable_hash.values().iterator(); it.hasNext(); ) {
      Variable var = (Variable) it.next();
      if(var.isExternal())
	external.add(var.getOperand().getFullName());
    }
    return external;
  }

  public HashMap getVariableHash() { return _variable_hash; }

  public void printVariables() {
    Variable var = null;
    if (!_variable_hash.isEmpty()) {
      System.out.println("*************BEGIN VARS**************************");
      for (Iterator it = _variable_hash.values().iterator(); it.hasNext();) {
	var = (Variable)it.next();
	if (var.isExternal()) {
	  System.out.print("External Variable: ");
	} else {
	  System.out.print("Global Variable: ");
	}
	System.out.println(var.toString());
      }
      System.out.println("**************END VARS*************************");
    }
  }


  // Kris's ChipInfo
  //===> moved to GlobalOptions.java
  /*public void saveChipInfo(int sliceCnt, float percentUsage) {
    _chipDef = new ChipDef(sliceCnt, percentUsage);
  }
  
  public ChipDef getChipInfo() { return _chipDef; }
  */

  /*
   *  BLOCK CODE *
   */

  private void addBlocks(Object something) {
    
  }
 
  public BlockNode findBlock(LabelOperand labelOperand) {
    BlockNode bn;
    String labelName = labelOperand.toString();
    // System.out.println("Finding target: " + labelName);
    for (Iterator it = getAllNodes().iterator(); it.hasNext(); ) {
      bn = (BlockNode) it.next();
      if (bn.getName().compareTo(labelName) == 0) {
	return bn;
      }
    }
    return null;
  }


  private void connectBlocks() {
    BlockNode bn;

    // first connect first block to ENTRY node
    if (_firstBlock == null) {
      System.err.println("Cannot find first block in block graph.");
      return;
    }
    ((ControlFlowEdge)addEdge((BlockNode)ENTRY, _firstBlock)).setLabel(Boolean.TRUE);

    // go thru all nodes and look at last instruction
    for (Iterator it = getAllNodes().iterator(); it.hasNext(); ) {
      bn = (BlockNode) it.next();
      //System.out.println("Connecting node: " + bn.getName());

      if ((bn == ENTRY) || (bn == EXIT)) {
	continue;
      }

      ArrayList iList = bn.getInstructions();

      if  (iList.size() == 0) {
	System.err.println("BlockNode has 0 instructions.");
      }

      Instruction lasti = (Instruction)iList.get(iList.size()-1);

      if (!lasti.isTerminator()) {
	System.err.println("Last instruction in block is not terminator.");
	return;
      }

      // Depending on what terminator instruction, connect block and label edge 
      BlockNode targetBlockNode = null; 
      LabelOperand target = null;

      if (lasti.isUnconditionalBranch()) {
	//System.out.println("Connecting Goto...");
	target = Goto.getTarget(lasti);

	if ((targetBlockNode=findBlock(target)) != null) {
	  ((ControlFlowEdge)addEdge(bn, targetBlockNode)).setLabel(Boolean.TRUE);
	} else System.err.println("Cannot find goto target");

      } else if (lasti.isConditionalBranch() && lasti.isVariableUses()) {
	//System.out.println("Connecting Switch...");

	// first connect default edge
        target = Switch.getDefault(lasti);
	if ((targetBlockNode=findBlock(target)) != null) {
	  ((ControlFlowEdge)addEdge(bn, targetBlockNode)).setLabel("default");
	} else System.err.println("Cannot find block for switch default target");

	// now connect each case label edge
	for (int c = 0;  Switch.hasCase(lasti, c); c++) {
	  target = Switch.getCaseLabel(lasti, c);
	  if ((targetBlockNode=findBlock(target)) != null) {
	    ConstantOperand caseValue = Switch.getCaseValue(lasti, c);
	    ((ControlFlowEdge)addEdge(bn, targetBlockNode)).setLabel(caseValue.getName());
	  } else System.err.println("Cannot find block for switch case: " + c );
	}
      } else if (lasti.isConditionalBranch()) {
	//System.out.println("Connecting Branch...");
	target = Branch.getTarget1(lasti);

	if ((targetBlockNode=findBlock(target)) != null) {
	  ((ControlFlowEdge)addEdge(bn, targetBlockNode)).setLabel(Boolean.TRUE);
	} else System.err.println("Cannot find block for branch true target");

	target = Branch.getTarget2(lasti);

	if ((targetBlockNode=findBlock(target)) != null) {
	  ((ControlFlowEdge)addEdge(bn, targetBlockNode)).setLabel(Boolean.FALSE);
	} else System.err.println("Cannot find block for branch false target");

      } else if (lasti.isReturn()) {
	//System.out.println("Connecting Return...");
	((ControlFlowEdge)addEdge(bn, (BlockNode)EXIT)).setLabel(Boolean.TRUE);
      } else System.err.println("Last instruction in block is unknown");
    }

    // if EXIT wasn't connected to anything, signal error
    if (EXIT.getInDegree() < 1) {
      System.err.println("Exit indegree is less than one.");
      return;
    }

  }


  /**
   * Node B is aborbed into Node A
   */
  public void mergeNode(BlockNode a, BlockNode b) {
    // merge the in edges of B onto A
    //System.out.println( "vertexA: " + A.toString() + " vertexB: " + 
    //          B.toString() );

    for (Iterator it = new ArrayList(b.getInEdges()).iterator();
         it.hasNext();){
      BlockEdge edge = (BlockEdge) it.next();
      edge.setSink(a);