instructionlist.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 java.util.*;
import fp.util.*;
import java.io.*;
import java.lang.Math;

import fp.hardware.*;
import fp.graph.*;
import fp.passes.*;
import fp.*;


/** This class stores the list of instructions for use by the scheduling
 * routines.  It has some useful methods and a nested class for storing data for
 * an instruction.  I wrote this for modulo scheduling, but with the
 * hope that the other schedulers would be slowly migrated over to using this.
 *
 * The class extends hashmap and
 * keys = scheduled time of execution for instructions
 * values = HashSets of InstructionObjects to be executed at this time
 *
 * MSchedHash extends this class and contains modulo scheduling specific methods
 * and data 
 *
 * @author Kris Peterson
 */
public class InstructionList extends HashMap
{

  /** This nested class saves an instruction and some associated information,
   *  which my methods will use.  MSchedInstObject extends this class and
   *  contains modulo scheduling specific methods and data.
   */
  public class InstructionObject {
  
    /**
    * This nested class within MSchedInstObject is for finding and saving
    * the nets connecting different instructions
    */
    private class ConnectingOperands {
    
      /**
      key is a successor instruction
      value is HashSet of all nets connecting this instruction with its
            successor ignoring predicates
      */
      private HashMap _succConns = new HashMap();
      /**
      key is a predecessor instruction
      value is HashSet of all nets connecting this instruction with its
            predecessor ignoring predicates
      */
      private HashMap _predConns = new HashMap();
      /**
      key is a successor instruction
      value is HashSet of all nets connecting this instruction with its
            successor including predicates
      */
      private HashMap _succConnsAll = new HashMap();
      /**
      key is a predecessor instruction
      value is HashSet of all nets connecting this instruction with its
            predecessor including predicates
      */
      private HashMap _predConnsAll = new HashMap();
      
      /**
      constructor
      */
      public ConnectingOperands() {
      }
      
      /**
      find the connecting nets between two instructions, excluding
      predicates.  If they are 
      known, return that, but if not, find them.
      */
      public HashSet getPredConns(Instruction i) {
        //check if the connecting nets are saved
	if(!_predConns.containsKey(i)) {
	  //if not, then foreach input to this instruction, if parent
	  //instruction i defines that net, save it
	  HashSet operandList = new HashSet();
	  for (Iterator vIt = getInstIns().iterator(); vIt.hasNext();) {
            Operand op = (Operand) vIt.next();
	    InstructionObject pObj = (InstructionObject)instToObjMap.get(i);
	    if(pObj.getInstOuts().contains(op))
	      operandList.add(op);
	  }
	  //save and return the set of connecting nets
	  _predConns.put(i, operandList);
	  return operandList;
	}
	//if it was saved, return
        return (HashSet)_predConns.get(i);
      }
    
      /**
      find the connecting nets between two instructions, including
      predicates.  If they are 
      known, return that, but if not, find them.
      See comments within the method above for understand how this works
      */
      public HashSet getPredConnsAll(Instruction i) {
        if(!_predConns.containsKey(i)) {
	  HashSet operandList = new HashSet();
	  //notice getInstInsAll() is called instead of getInstIns()
	  //like above
	  for (Iterator vIt = getInstInsAll().iterator(); vIt.hasNext();) {
            Operand op = (Operand) vIt.next();
	    InstructionObject pObj = (InstructionObject)instToObjMap.get(i);
	    if(contains(pObj.getInstOuts(), op))
	      operandList.add(op);
	  }
	  _predConns.put(i, operandList);
	  return operandList;
	}
        return (HashSet)_predConns.get(i);
      }
      
      private boolean contains(HashSet savedOuts, Operand op) {
        for (Iterator vIt = savedOuts.iterator(); vIt.hasNext();) {
          Operand opTmp = (Operand) vIt.next();
          if(opTmp.toString().compareTo(op.toString())==0)
      	    return true;
        }
        return false;
      }
    
      /**
      find the connecting nets between an instruction and one of its
      successors, excluding
      predicates.  If they are 
      known, return that, but if not, find them.
      */
      public HashSet getSuccConns(Instruction i) {
        if(!_succConns.containsKey(i)) {
	  HashSet operandList = new HashSet();
	  //notice getInstOuts() is called this time
	  for (Iterator vIt = getInstOuts().iterator(); vIt.hasNext();) {
            Operand op = (Operand) vIt.next();
	    InstructionObject cObj = (InstructionObject)instToObjMap.get(i);
	    //here getInstIns() is called instead of getInstOuts() like
	    //above
	    if(cObj.getInstIns().contains(op))
	      operandList.add(op);
	  }
	  _succConns.put(i, operandList);
	  return operandList;
	}
        return (HashSet)_succConns.get(i);
      }
    
      /**
      find the connecting nets between an instruction and one of its
      successors, including predicates.  If they are 
      known, return that, but if not, find them.
      */
      public HashSet getSuccConnsAll(Instruction i) {
        if(!_succConns.containsKey(i)) {
	  HashSet operandList = new HashSet();
	  for (Iterator vIt = getInstOuts().iterator(); vIt.hasNext();) {
            Operand op = (Operand) vIt.next();
	    InstructionObject cObj = (InstructionObject)instToObjMap.get(i);
	    //notice getInstInsAll()
	    if(cObj.getInstInsAll().contains(op))
	      operandList.add(op);
	  }
	  _succConns.put(i, operandList);
	  return operandList;
	}
        return (HashSet)_succConns.get(i);
      }
    
    }//end nested class ConnectingOperands

    /**
    using the philosophy that using more memory to reduce calculations increases
    speed, the latency for an instruction is saved here.  That way, it only
    needs to be calculated once and all other times, this value will be
    returned.
    */
    private float _runlength = -1;
    /**
    the instruction associated with this object.
    */
    public Instruction inst;
    /**
    a list of operands used in predicates that are defined by this instruction.
    */
    public ArrayList listOfPredsDefnd = new ArrayList();
    /**
    a list of operands used in predicates that are used by this instruction.
    */
    public ArrayList listOfPredsUsed = new ArrayList();
    /**
    not used at this time, but may be used later if other schedulers use this.
    */
    public float execTimeTemp = -1;
    /**
    a set of uses by this instruction not including predicates unless this
    instruction is a store to a primal.
    */
    private HashSet _instIns = new HashSet();
    /**
    a set of all uses by this instruction including predicates 
    */
    private HashSet _instInsAll = new HashSet();
    /**
    a flag telling if this instruction has any inputs 
    */
    public boolean noIns = false;
    /**
    a set of definitions by this instruction
    */
    private HashSet _instOuts = new HashSet();
    /**
    a flag telling if this instruction has any outputs 
    */
    public boolean noOuts = false;
    /**
    a flag telling if this instruction has any primal outputs 
    */
    public Boolean _isAnOutPrimal = null;
    /**
    an arraylist of successor instructions (I can't remember why I used
    ArrayList instead of HashSet).
    */
    private ArrayList _listOfSuccs = new ArrayList();
    /**
    a boolean telling whether there are successors or not.  It is of type
    Boolean instead of boolean, because that gave me a third possible value
    (null), which I could use to know if it has already been determined if there
    are any successors.  If it is null, it will first try to create the list of
    successors before returning a value for this variable (the it I'm referring
    to is a method below which returns whether there are successors or not).
    */
    private Boolean _noSuccs = null;
    /**
    an arraylist of predecessor instructions
    */
    private ArrayList _listOfPreds = new ArrayList();
    /**
    a boolean telling whether there are successors or not.  
    */
    private Boolean _noPreds = null;
    
    private Operand _iterationPred = null;

    /**
    see nested class "ConnectingOperands".  This is an instantiation
    of that class and is used to save this instruction's connecting nets
    with other instructions
    */
    private ConnectingOperands _connOps = new ConnectingOperands();


    public InstructionObject() {
      _iterationPred = null;
    }
  
    public InstructionObject(Instruction i) {
      inst = i;
      updatePredLists();
      _iterationPred = null;
    }
    
    /**
    to make it easier to debug, I added this so that I can print these objects
    and know which object I'm refering to, without having to reference the
    instruction itself in the print statement (which may be difficult if I'm
    trying to print a collection of objects, since otherwise I'd have to put in
    a loop to go through each object and print its instruction)
    */
    public String toString() {
      return inst.toString();
    }
    

    /**
    get the list of connecting nets between this instruction and parent
    instruction i, excluding predicates.  
    */
    public HashSet getPredConns(Instruction i) {
      return _connOps.getPredConns(i);
    }
    
    /**
    get the list of connecting nets between this instruction and parent
    instruction i, including predicates.  
    */
    public HashSet getPredConnsAll(Instruction i) {
      return _connOps.getPredConnsAll(i);
    }
    
    /**
    get the list of connecting nets between this instruction and child
    instruction i, excluding predicates.  
    */
    public HashSet getSuccConns(Instruction i) {
      return _connOps.getSuccConns(i);
    }
    
    /**
    get the list of connecting nets between this instruction and child
    instruction i, including predicates.  
    */
    public HashSet getSuccConnsAll(Instruction i) {
      return _connOps.getSuccConnsAll(i);
    }

    //use carefully!
    public void addIn(Operand inputOp) {
      getInstIns();
      _instIns.add(inputOp);
      _iterationPred = inputOp;
    }
    
    public void addOut(Operand outputOp) {
      getInstOuts();
      _instOuts.add(outputOp);
      //_iterationSucc = outputOp;
    }
    
    public void changeItPred(Operand op1, Operand op2) {
      if((_iterationPred != null) && (_iterationPred == op1))
        _iterationPred = op2;
    }
    
    public BooleanOperand getItPred() { return (BooleanOperand)_iterationPred; }
    public void setItPred(Operand itPredOp) { _iterationPred = itPredOp; }
    
    /**
    this guy finds all the uses for an instruction
    */
    public HashSet getInstIns() {
      //if they've already been found or if there are none, than return the set
      //or null
      if(_instIns.size()>0) 
        return _instIns;
      else if(noIns)
        return null;
	
      if(AStore.conforms(inst)) {
        _instIns.add(AStore.getAddrDestination(inst));
        _instIns.add(AStore.getValue(inst));
      }
      else {
      
	//otherwise get them all and save them to the set
	Operand op;
	int numDefs = inst.getNumberOfDefs();
	int total = inst.getNumberOfOperands();
	for(int i = numDefs; i < total; i++) {
          op = inst.getOperand(i);
          if(op != null)
            _instIns.add(op);
	}