dependenceflowgraph.java

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

	  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].*")) {
            astore1 += value;
          }
          else if(opName.matches(".*[sS][uU][bB].*")) {
            astore1 = fstOp == null ? astore1-value : value-astore1;
	    //astore1 -= value;
          }
          else if(opName.matches(".*[mM][uU][lL].*")) {
	    astore1 *= value;
          }
          else if(opName.matches(".*[dD][iI][vV].*")) {
            astore1 = fstOp == null ? astore1/value : value/astore1;
	    //astore1 /= value;
          }
          else if(opName.matches(".*[sS][hH][lL].*")) {
	    astore1 *= Math.pow(2, value);
          }
          else if(opName.matches(".*[sS][hH][rR].*")) {
	    astore1 *= Math.pow(1/2, value);
          }
           
           
        }
        else {
          return true;
	  //System.out.println("else " + inst);
	}
      }
      System.out.println("astore1 " + astore1 + " loopEnd1 " + loopEnd1);
      if(aload1>astore1)
        return false;
      //System.exit(1);
      
      return true;
    }
  }
  
  /** perhaps, this is bad programming style, but all t`he main guts of the pass 
   *  are here.  It follows 7 steps:
   * 
   * 1) create STOP and START pseudo nodes (which Rau's algorithm uses)
   * 2) create node for all instructions and add input connection from START and 
   *    output to STOP
   * 3) add data dependency edges (same as data flow) and control dependency 
   *    edges for predicates
   * 4) check for edges going over loop edge and label them as recursive 
   *    connections
   * 5) add data dependency edges for arrays
   * 6) add control edges for loop control
   * 7) write the graph to a dotty file
   * 
   * @param blockGraph 
   */
  public boolean generateGraph(BlockNode bn, InstructionList iList) {
    
    //step 0: checks if the block node is a loop
    boolean isLoop = checkIfBlockNodeIsLoop(bn);
    
    //steps 1-3, create dependence flow nodes and connect them with control and data
    //flow edges
    makeAndConnectNodes(bn, iList);
        //System.out.println("after make and connect  ");
	//printEdges();
    
    //step 4: see which edges should be labeled as recursive (that is is part of a 
    //interloop dependency)
    boolean isBlockRecursive = setRecursiveEdges(isLoop);
        //System.out.println("after set recursive this.getAllEdges() ");
	//printEdges();
    
    //step 4b: look for extra data dependency loop edges that were hidden
    //because there was no load and store to a primal
    isBlockRecursive |= findOtherRecursiveDataEdges(bn, isLoop, iList);
    
    //step 5: add recursive edges from AStores to ALoads if necessary 
    isBlockRecursive = isBlockRecursive | 
                       _loadStoreHandler.makeConns(isLoop);
         //System.out.println("after load store handling this.getAllEdges() ");
	//printEdges();
   bn.setIsRecursive(isBlockRecursive);
    
    //step 6: add control edges (if the Block is a loop, edges from where the loop
    //exit predicate is calculated to every node in the DFG need to be added):
    addCntrlEdges(bn, iList.getInstructions());
         //System.out.println("after add control edges this.getAllEdges() ");
	//printEdges();
    return true;
  }
  
  public boolean findOtherRecursiveDataEdges(BlockNode node, boolean isLoop, 
                                             InstructionList iList) {
  
    if(findOtherRecDataEdgesRec(node, _sTART, new HashSet(), iList) && isLoop)
      return true;
    return false;
  }
  
  public boolean findOtherRecDataEdgesRec(BlockNode node, 
                                          DependenceFlowNode pdfn, 
					  HashSet alreadyVisited,
					  InstructionList iList) {
  
    boolean isRec = false;
    alreadyVisited.add(pdfn);
    HashSet outEdges = new HashSet(pdfn.getOutEdges());
    for (Iterator it5 = outEdges.iterator(); it5.hasNext();) {
      DependenceFlowEdge edge = (DependenceFlowEdge)it5.next();
      if(!edge.getIsDataEdge() && pdfn != _sTART) continue;
      if(edge.getisBackWardsPointing()) continue;
      DependenceFlowNode cdfn = (DependenceFlowNode)edge.getSink();
      
      if((alreadyVisited.contains(cdfn))&&
         (pdfn != _sTART)) {
        removeEdge(edge);
        insertLoadStore(node, pdfn, cdfn, iList);
	isRec = true;
      }
      else if(!alreadyVisited.contains(cdfn)) {
        HashSet alreadyVisitedCopy = new HashSet();
	alreadyVisitedCopy.addAll(alreadyVisited);
	isRec = findOtherRecDataEdgesRec(node, cdfn, alreadyVisitedCopy, iList);
      }
      
    }
    return isRec;
  }
  
  private int _lkwCntr = 0;
  public void insertLoadStore(BlockNode node, DependenceFlowNode pdfn, 
                              DependenceFlowNode cdfn, InstructionList iList) {
    Instruction pInst = pdfn.getInstruction();
    Instruction cInst = cdfn.getInstruction();
    InstructionList.InstructionObject pObj = iList.findInstObj(pInst);
    InstructionList.InstructionObject cObj = iList.findInstObj(cInst);
    
    
    HashSet connectingOps = pObj.getSuccConns(cInst);
    
    for (Iterator it1 = connectingOps.iterator(); it1.hasNext();) {
      Operand op = (Operand)it1.next();
      if(op.isPrimal()) continue;  //if an operand is primal it does not
	                           //need to be loaded and stored
      
      Operand newOp = op.getNextNonPrime();
      node.removeFromHashes(cInst);
      cObj.replaceOperand(op, newOp);
      node.updateHashes(cInst);
      String name = "lkw_dpf" + _lkwCntr;
      _lkwCntr++;
      PrimalOperand newVar = Operand.newPrimal(name);
      Type type = pInst.type();
      BooleanEquation eq = pInst.getPredicate();
      
      Instruction lInst = Load.create(Operators.LOAD, type, newOp, newVar, eq);
      node.addInstruction(lInst);
      InstructionList.InstructionObject load_Obj = iList.newInstructionObject(lInst);
      DependenceFlowNode load_dfn = _inst2NodeGenAndMapper.get(load_Obj);
      iList.add((float)-1.0, load_Obj);
      DependenceDataFlowEdge ddfe = new DependenceDataFlowEdge(load_dfn, cdfn, "");
      this.addEdge(ddfe);
      
      BooleanEquation instPred = load_Obj.inst.getPredicate();
      if(instPred != null) {
        LinkedList BoolsTmp = instPred.listBooleanOperands();
       for(Iterator it3 = BoolsTmp.iterator(); it3.hasNext();) {
          Operand pred = (Operand)it3.next();
	  DefHash defs = node.getDefHash();
	  Instruction parentInst = (Instruction)defs.get(pred);
	  if(parentInst == null) continue;
	  DependenceFlowNode cfnd =
	               _inst2NodeGenAndMapper.get(iList.instToObjMap.get(parentInst));
          DependenceCntrlFlowEdge dcfe = new DependenceCntrlFlowEdge(cfnd, 
								     load_dfn,"");
          this.addEdge(dcfe);
        }
      }
      
      Instruction sInst = Store.create(Operators.STORE, type, newVar, op, 
                                       eq);
      node.addInstruction(sInst);
      InstructionList.InstructionObject store_Obj = iList.newInstructionObject(sInst);
      DependenceFlowNode store_dfn = _inst2NodeGenAndMapper.get(store_Obj);
      iList.add((float)-1.0, store_Obj);
      DependenceDataFlowEdge ddfe2 = new DependenceDataFlowEdge(pdfn, store_dfn, "");
      this.addEdge(ddfe2);
      
      
      DependenceDataFlowEdge ddfe3 = new DependenceDataFlowEdge(store_dfn, 
                                                                load_dfn, "");
      this.addEdge(ddfe3);
      ddfe3.setBackWardsPointing();
      
      instPred = store_Obj.inst.getPredicate();
      if(instPred != null) {
        LinkedList BoolsTmp = instPred.listBooleanOperands();
       for(Iterator it3 = BoolsTmp.iterator(); it3.hasNext();) {
          Operand pred = (Operand)it3.next();
	  DefHash defs = node.getDefHash();
	  Instruction parentInst = (Instruction)defs.get(pred);
	  if(parentInst == null) continue;
	  DependenceFlowNode cfnd =
	               _inst2NodeGenAndMapper.get(iList.instToObjMap.get(parentInst));
          DependenceCntrlFlowEdge dcfe = new DependenceCntrlFlowEdge(cfnd, 
								     store_dfn,"");
          this.addEdge(dcfe);
        }
      }
   
    }
  }
  
  public void printEdges() {
    for (Iterator it = getAllEdges().iterator(); it.hasNext();) {
      DependenceFlowEdge edge = (DependenceFlowEdge)it.next();
      System.out.println("edge from " + edge.getSource() + " to " + edge.getSink());
    }
  
  }
  
  public boolean checkIfBlockNodeIsLoop(BlockNode bn) {
    for (Iterator it = bn.getOutEdges().iterator(); it.hasNext();) {
      BlockEdge outEdge = (BlockEdge)it.next();
      //if(outEdge.isBackwardEdge()) 
      if(outEdge.getSource() == outEdge.getSink()) 
        return true;
    }
    return false;
  }
  
  public void makeAndConnectNodes(BlockNode bn, InstructionList iList) {
    for (Iterator it = iList.getInstSet().iterator(); it.hasNext(); ) {
      InstructionList.InstructionObject instObj = 
                                   (InstructionList.InstructionObject)it.next();
      
      
      DependenceFlowNode pdfn = _inst2NodeGenAndMapper.get(instObj);
      //if(instObj.getNoSuccs()) continue;
      for (Iterator it2 = instObj.getSuccsForDFG().iterator(); it2.hasNext(); ) {
        InstructionList.InstructionObject childObj = 
	                          (InstructionList.InstructionObject)it2.next();
	if(ALoad.conforms(childObj.inst) && AStore.conforms(instObj.inst)) {
          _loadStoreHandler.add(childObj.inst, instObj.inst);
	  continue;
        }
	//System.out.println("making node for " +  childObj);
	//System.out.println("with parent  " +  instObj);
	DependenceFlowNode cdfn = _inst2NodeGenAndMapper.get(childObj);
	//System.out.println("cdfn  " + cdfn);
        DependenceDataFlowEdge ddfe = new DependenceDataFlowEdge(pdfn, cdfn,"");
	if(Load.conforms(childObj.inst) && Store.conforms(instObj.inst)) {
          ddfe.setBackWardsPointing();
        }
        //System.out.println("add data conn between " + pdfn + " and " + cdfn);
        //System.out.println("ddfe " + ddfe);
	this.addEdge(ddfe);
        //System.out.println("all edges ");
	//printEdges();
      }
        //System.out.println("after all adds ");
	//printEdges();
      
      /*for (Iterator it3 = instObj.listOfPredsDefnd.iterator(); it3.hasNext(); ) {
        Operand pred = (Operand)it3.next();
	for (Iterator it4 = iList.getInstSet().iterator(); it4.hasNext(); ) {
          InstructionList.InstructionObject childObj = 
	                          (InstructionList.InstructionObject)it4.next();
	  if(childObj.listOfPredsUsed.contains(pred)) {
	    DependenceFlowNode pdfn = _inst2NodeGenAndMapper.get(instObj.inst);
	    DependenceFlowNode cdfn = _inst2NodeGenAndMapper.get(childObj.inst);
            DependenceCntrlFlowEdge dcfe = new DependenceCntrlFlowEdge(pdfn, 
	                                                               cdfn,"");
            this.addEdge(dcfe);
	  
	  }
	}
      }*/
      BooleanEquation instPred = instObj.inst.getPredicate();
      if(instPred != null) {
        LinkedList BoolsTmp = instPred.listBooleanOperands();
       for(Iterator it3 = BoolsTmp.iterator(); it3.hasNext();) {
      //for (Iterator it3 = instObj.listOfPredsUsed.iterator(); it3.hasNext(); ) {
          Operand pred = (Operand)it3.next();
	  DefHash defs = bn.getDefHash();
	  Instruction parentInst = (Instruction)defs.get(pred);
	  if(parentInst == null) continue;
	  //for (Iterator it4 = iList.getInstSet().iterator(); it4.hasNext(); ) {
          //  InstructionList.InstructionObject childObj = 
	  //                          (InstructionList.InstructionObject)it4.next();
	  //  if(childObj.listOfPredsUsed.contains(pred)) {
	  //DependenceFlowNode pdfn = _inst2NodeGenAndMapper.get(instObj.inst);
	  DependenceFlowNode cdfn =
	               _inst2NodeGenAndMapper.get(iList.instToObjMap.get(parentInst));
          DependenceCntrlFlowEdge dcfe = new DependenceCntrlFlowEdge(cdfn, 
								     pdfn,"");
          this.addEdge(dcfe);
	  
	//  }
	//}
        }
      }
    }
  }
  
  public boolean setRecursiveEdges(boolean isLoop) {
    boolean isBlockRecursive = false;
    for (Iterator it5 = this.getAllEdges().iterator(); it5.hasNext();) {