blockgraph.java

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

    } // end of for (Iterator  = .iterator(); .hasNext();)
    for (Iterator it = new ArrayList(b.getOutEdges()).iterator();
         it.hasNext();){
      BlockEdge edge = (BlockEdge) it.next();
      edge.setSource(a);
    } // end of for (Iterator  = .iterator(); .hasNext();)
    removeNode(b);
    mergeEdges( (BlockNode)a);
  }


  // mergeSerial
   /**
   * These methods do the subsumption
   **/
  public void mergeSerial( BlockNode nodeA, BlockEdge edge, BlockNode nodeB) {
    //System.out.println("BlockGraph::mergeSerial()");

    //System.out.println(" nodeA\n "+nodeA.getDefHash()+"\n"+nodeA.getUseHash());
    //System.out.println(" nodeB\n "+nodeB.getDefHash()+"\n"+nodeB.getUseHash());

    // remove the edge between nodeA -> nodeB
    removeEdge( edge );

    /*
      This function takes the outputs of the this vertex and tests
      them agains the inputs of THE vertex.  If there is correspondance,
      then a new operand is created to move the value of a given variable
      q from the old block to the new block.  This does not try to optimize
      the aliasing that is going on.
     */

    mergeSerialCrossCancel(nodeA, nodeB);

    /*
      This probably can happen but it is not a big deal.
      It says that for a given input q, this vertex reads
      q and old vertex reads q.  It is not a problem, but 
      we would like them to both read from the same variable.
      They should not be reading different values since that should
      have been cleared up in the previous check.
    */ 
    mergeSerialOutputs(nodeA, nodeB);

    mergeInstructions(nodeA, nodeB);
    
    //System.out.println(" nodeA\n"+nodeA.getDefHash()+"\n"+nodeA.getUseHash());

  }
  
  
  private void mergeInstructions(BlockNode a, BlockNode b) {
    ArrayList a_instructions = a.getInstructions();
    for(ListIterator iter = b.getInstructions().listIterator(); 
	iter.hasNext(); ) {
      Instruction temp = (Instruction)iter.next();
      if (!temp.isNOP()) 
	a.addInstruction(temp);
    }
  }


  /*
    This takes two nodes that are connected via an edge in a serial fashion and
    fixes the nodeA -> outputs collisions with inputs -> nodeB.
  */
  private void mergeSerialCrossCancel(BlockNode nodeA, BlockNode nodeB) {
    
    //System.out.println("BlockGraph::serialCrossCancel()");
    DefHash def_hash = nodeA.getDefHash();
    UseHash merging_use_hash = nodeB.getUseHash();
    for (Iterator it = ((DefHash)def_hash.clone()).keySet().iterator(); 
	 it.hasNext(); ) {

      Operand this_out = (Operand)it.next();
      // unnecessary to examine constants
      if (this_out.isConstant()) continue;
      if (!this_out.isPrimal()) continue;

      ArrayList collisions = (ArrayList)merging_use_hash.get(this_out);
      // no collisions, no work. -- this_out must be primal, right?
      if (collisions == null) continue;
      collisions = (ArrayList)collisions.clone();

      Instruction source = (Instruction)def_hash.get(this_out);
      // find collisions for now ...
      // print them ?
      
      //System.out.println("SerialCrossCancel collisions:");
      //System.out.println(collisions);

      // this may not be optimal, if we are adding selects for lots of collisions.
      for(ListIterator collision_iter = collisions.listIterator(); 
	  collision_iter.hasNext(); ) {
	Instruction collision = (Instruction)collision_iter.next();

	Operand new_op = this_out.getNextNonPrime();
	Instruction mine = source, his = collision;
	BooleanEquation his_pred = his.getPredicate();
	// I don't need to remove mine.
	nodeB.removeInstruction(his);

	
	//PrimalOperand primal_op = (PrimalOperand)this_out;
      
	BooleanEquation mux_eq = new BooleanEquation(mine.getPredicate());
      
	BEqToList eq_list = new BEqToList(mux_eq, new BooleanEquation(true));
	for(Iterator eq_iter = eq_list.iterator(); eq_iter.hasNext(); ) {
	  nodeA.addInstruction((Instruction)eq_iter.next());
	}
	
	BooleanOperand mux_op = eq_list.getResult();

	Instruction mux = Select.create(Operators.SELECT, mine.type(),
					Load.getResult(his), mux_op, 
					Store.getValue(mine), new_op);

	BooleanEquation mux_pred = new BooleanEquation(his_pred);
	mux.setPredicate(mux_pred);

	Load.setResult(his, new_op);

	// little strange to add these to nodeB.
	nodeB.addInstruction(mux);
	nodeB.addInstruction(his);
      }

    }
  }

  
  void mergeSerialOutputs(BlockNode nodeA, BlockNode nodeB) {
    //System.out.println("BlockGraph::mergeSerialOutputs()");
    DefHash def_hash = nodeA.getDefHash();
    DefHash merging_def_hash = nodeB.getDefHash();
    for(Iterator it = ((HashMap)def_hash.clone()).keySet().iterator(); 
	it.hasNext(); ) {
      Operand this_out = (Operand)it.next();
      if (this_out.isConstant()) continue;

      Instruction collision = (Instruction)merging_def_hash.get(this_out);
      if (collision == null) continue;

      Instruction source = (Instruction)def_hash.get(this_out);
      
      // print them ?
      	    //System.err.println("Output collision : "+collision);
            //System.err.println("Output source	 : "+source);
      Operand new_op = this_out.getNextNonPrime();
      BooleanEquation new_pred = new BooleanEquation();
      Instruction mine = source, his = collision;
      
      BooleanEquation his_pred = his.getPredicate();
      BooleanEquation mine_pred = mine.getPredicate();
      
      PrimalOperand primal_op = (PrimalOperand)this_out;
      
      Instruction store = Store.create(Operators.STORE, mine.type(), 
				       primal_op, new_op);
      
      BooleanEquation mux_eq = new BooleanEquation(his_pred);
      
      BEqToList eq_list = new BEqToList(mux_eq, new BooleanEquation(true));
      for(Iterator eq_iter = eq_list.iterator(); eq_iter.hasNext(); ) {
	nodeA.addInstruction((Instruction)eq_iter.next());
      }

      BooleanOperand mux_op = eq_list.getResult();

      Instruction mux = Select.create(Operators.SELECT, mine.type(),
				      new_op, mux_op, 
				      Store.getValue(his),				      
				      Store.getValue(mine));

      BooleanEquation mux_pred = new BooleanEquation(his_pred);
      BooleanEquation store_pred = new BooleanEquation(mine_pred);
      store_pred.or(mux_pred);
      mux_pred.or(store_pred);

      store.setPredicate(store_pred);
      mux.setPredicate(mux_pred);

      nodeA.removeInstruction(mine);
      nodeB.removeInstruction(his);

      nodeA.addInstruction(store);
      nodeA.addInstruction(mux);

    }
  }


  // mergeParallel
  public void mergeParallel(BlockNode a, BlockNode b) {
    mergeParallelOutputs(a, b);
    
    mergeInstructions(a, b);
  }
  

  void mergeParallelOutputs(BlockNode a, BlockNode b) {
    DefHash def_hash = a.getDefHash();
    DefHash merging_def_hash = b.getDefHash();

    for(Iterator it = ((DefHash)def_hash.clone()).keySet().iterator(); it.hasNext(); ) {
      Operand this_out = (Operand)it.next();
      // constants, although primal are not interesting.
      if (this_out.isConstant()) continue;
      
      Instruction collision = (Instruction)merging_def_hash.get(this_out);
      // nothing to see, move along.
      if (collision == null) continue;
     
      Instruction source = (Instruction)def_hash.get(this_out);
      
      //System.out.println(" Mine "+source);
      //System.out.println(" his  "+collision);

      Operand new_op = this_out.getNextNonPrime();
      
      BooleanEquation new_pred = new BooleanEquation();
      Instruction mine = source, his = collision;
      
      BooleanEquation his_pred = his.getPredicate();
      BooleanEquation mine_pred = mine.getPredicate();

      //System.err.println("collision "  + collision);
      //System.err.println("source "  + source);
      //System.err.println(" bad var  "+this_out);
      PrimalOperand primal_op = (PrimalOperand)this_out;

      // Now since we have found a collision -- we will search through
      // all of the instructions to find where this thing was used.
          
      Instruction store = Store.create(Operators.STORE, mine.type(), 
                                       (Operand)primal_op, new_op);
      
      BooleanEquation mux_eq = new BooleanEquation(his_pred);

      BEqToList eq_list = new BEqToList(mux_eq, new BooleanEquation(true));
      for(Iterator eq_iter = eq_list.iterator(); eq_iter.hasNext(); ) {
        a.addInstruction((Instruction)eq_iter.next());
      }
      
      BooleanOperand mux_op = eq_list.getResult();

      Instruction mux = Select.create(Operators.SELECT, mine.type(),
				      new_op, mux_op,
				      Store.getValue(his),
				      Store.getValue(mine));
      
      BooleanEquation mux_pred = new BooleanEquation(his_pred);
      BooleanEquation store_pred = new BooleanEquation(mine_pred);
      store_pred.or(mux_pred);
      mux_pred.or(store_pred);

      store.setPredicate(store_pred);
      mux.setPredicate(mux_pred);

      a.removeInstruction(mine);
      b.removeInstruction(his);

      a.addInstruction(store);
      a.addInstruction(mux);
    }
  }

	
  private void cleanUp(Object something) {

  }

  // this assumes basic block structure.
  // will not work on merged structures.
  // This also assumes no predicates.
  public void splitBlock(BlockNode node, Instruction inst) {
    // create new node
    // move out edges from old node to new node
    // make out edge from old to new
    // remove all instructions from old node
    // add partial list to old node
    // add the rest to new node

    ArrayList old_list = (ArrayList)node.getInstructions().clone();
    // if this is goofy, we should throw an exception or something.
    int index = old_list.indexOf(inst);
    int size = old_list.size();

    // how does this fit into keeping track of loop stuff?
    BlockNode new_node = (BlockNode)addNode();
    new_node.setName("split_"+node.getLabel().getFullName());
    Set out_edges = new HashSet();
    out_edges.addAll(node.getOutEdges());

    for(Iterator sIt = out_edges.iterator(); sIt.hasNext(); ) {
      BlockEdge edge = (BlockEdge)sIt.next();
      edge.setSource(new_node);
    }
    out_edges.clear();
    BlockEdge edge = (BlockEdge)addEdge(node, new_node);
    edge.setPredicate(new BooleanEquation(true));
    
    List node_list = old_list.subList(0, index);
    List new_list = old_list.subList(index, size);

    node.removeAllInstructions();
    node.addInstructions(node_list);
    new_node.addInstructions(new_list);

  }


  /*
   *  EDGE CODE *
   */

  /**
   * This method takes two edges that should have the same source and sink,
   * ORs their predicates and then replaces them with the new ORed edge
   **/
    
  public void mergeEdges(BlockNode node) { 
    // combine edges going in that have the same source
    mergeEdges(node.getInEdges(), true);
    // combine edges going out that have the same sink
    mergeEdges(node.getOutEdges(), false);
  }
  
  /**
   * @param lookForSameSource true if edges should be merged when they have
   * the same source, false if edges should be merged when they have the same
   * sink
   */
  private void mergeEdges( Set edgeSet, boolean lookForSameSource ) {
    // Map sources to lists of edges that have predicates
    Map endPointsToEdges = new HashMap() {
        public Object get(Object key) {
          Object value = super.get(key);
          if (value == null) {
            value = new ArrayList();
            super.put(key, value);
          } // end of if ()
          return value;
        }
	
        public Object put(Object key, Object value) {
          List l = (List) get(key);
          l.add(value);
          return l;
        }
      };
    for (Iterator in_edges = edgeSet.iterator(); in_edges.hasNext();) {
      BlockEdge edge = (BlockEdge)in_edges.next();
      if (edge.getPredicate() != null) {
        String key = null;
        // look for edges with the same source going to the same sink port
        if (lookForSameSource) {
          key = edge.getSource() + ":" + edge.getDotSinkPort();
        } else {
	  // look for edges with the same sink coming from the same source port
          key = edge.getSink() + ":" + edge.getDotSourcePort();
        }
        endPointsToEdges.put(key, edge);
      } // end of if ()
    }
    for (Iterator mit = endPointsToEdges.values().iterator();
         mit.hasNext();){
      List edges = (List) mit.next();
      if (edges.size() > 1) {
        // Multiple edges have the same source
        BlockEdge edge1 = (BlockEdge) edges.get(0);
        BooleanEquation edge1pred = edge1.getPredicate();
        for (Iterator lit = edges.listIterator(1); lit.hasNext();){ 
          BlockEdge edge2 = (BlockEdge) lit.next();
          edge1pred.or( edge2.getPredicate() );
	  // jt: I don't think this is required.
          //edge1.combineIfStatements(edge2);

          removeEdge( edge2 );
        } 
      } // end of if ()
    } // end of for (Iterator  = .iterator(); .hasNext();)
  }



}