/* ---------------------------------------------------------------------
%   Copyright (C) 2007 Association for the COINS Compiler Infrastructure
%       (Read COPYING for detailed information.)
--------------------------------------------------------------------- */
package coins.opt;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.HashSet; //##63
import java.util.Set; //##63

import coins.FlowRoot;
import coins.SymRoot;
//##63 import coins.aflow.BBlock;
import coins.flow.BBlock; //##63
//##63 import coins.aflow.DefVector;
import coins.flow.DefVector; //##63
//##63 import coins.aflow.FlowExpId;
import coins.aflow.FlowResults;
//##63 import coins.aflow.FlowUtil;
import coins.flow.FlowUtil; //##63
//##63 import coins.aflow.SetRefRepr;
import coins.flow.SetRefRepr; //##63
//##63 import coins.aflow.SetRefReprList;
import coins.flow.SetRefReprList; //##63
//##63 import coins.aflow.SubpFlow;
import coins.flow.SubpFlow; //##63
//##63 import coins.aflow.UDChain;
import coins.flow.UseDefChain; //##63
//##63 import coins.aflow.UDList;
import coins.flow.UseDefList; //##63
import coins.flow.DataFlow; //##63
import coins.flow.FlowAnalSymVector; //##63
//##63 import coins.aflow.util.CoinsIterator;
import coins.ir.IR;
import coins.ir.hir.HIR;
import coins.ir.hir.VarNode;
import coins.sym.Sym;
import coins.sym.FlowAnalSym;
import coins.sym.Type;
import coins.sym.ExpId; //##63
import java.util.List; //##63

/**
 * Constant propagation and folding basic logic class.
 * Excluded cases:
 *   Use point has multiple definition points
 *   Not included in DefIn (may be undefined)
 *   Node to which value is to be set
 *   Operand of address expression
 *   Node having no symbol
 *   Vector or structure variable
 *   Address taken variable
 *   Type of expression differs with the type of constant
 *   float/double variable
 *   Direct child of SwitchStmt (switch selector)
 *   Node generated by previous optimization (before finishHir())
 *   Node already replaced
 *   ExpId is not allocated (not an expression)
 */
public class ConstPropagationAndFolding
{
  final static int JAVA_BYTE_SIZE = 1, JAVA_CHAR_SIZE = 2, JAVA_SHORT_SIZE = 2,
    JAVA_INT_SIZE = 4, JAVA_LONG_SIZE = 8;

  //    public final OptRoot optRoot;
  public final FlowRoot flowRoot;
  public final SymRoot symRoot;
  //    public final HIR hir;
  public final Sym sym;
  FlowResults fResults;

  public final Opt opt;

  public final SubpFlow fSubpFlow; //##63
  protected UseDefList fUDList; //##63
  protected DataFlow fDataFlow; //##63
  protected final int fDbgLevel; //##67

  //    private final boolean NO_ALIAS;
  /**
   *
   * ConstPropagationAndFolding
   *
   *
   **/
  public ConstPropagationAndFolding(FlowResults pResults)
  {
    this(pResults.flowRoot);
    fResults = pResults;
  }

  /**
   *
   *
   *     ex)
   *     expression :p = (int) a;
   *     exp        := (int) [node]
   *     return     ; a [node] ;
   *
   */
  HIR SkipConv(HIR exp)
  {
    HIR Curr = exp;
    Type CurrType;
    Type expType;
    expType = exp.getType();
    while (Curr.getOperator() == HIR.OP_CONV) {
      if (Curr.getType().getTypeKind() != expType.getTypeKind()) {
        break;
      }
      Curr = (HIR)Curr.getChild1();

    }
    return Curr;
  }

  /*
   *
   *
   **/
  private ConstPropagationAndFolding(FlowRoot pFlowRoot)
  {
    flowRoot = pFlowRoot;
    symRoot = flowRoot.symRoot;
    sym = symRoot.sym;
    opt = new Opt(flowRoot);
    fSubpFlow = flowRoot.fSubpFlow; //##63
    //NO_ALIAS = flowRoot.ioRoot.getCompileSpecification().getCoinsOptions().isSet("optNa");
    fDbgLevel = flowRoot.ioRoot.dbgOpt1.getLevel(); //##67
  }

  /**
   *
   * doSubp
   *
   *
   **/
  public boolean doSubp(SubpFlow pSubpFlow)
  {
    boolean lChanged, lChangedAtLeastOnce = false;
    BBlock lBBlock;
    fUDList = fSubpFlow.getUseDefList(); //##63
    fDataFlow = flowRoot.flow.dataFlow(); //##63
    fDataFlow.findUseDef(); //##63
    fDataFlow.findExposed(); //##63
    fDataFlow.findDefInDefOut(); //##63
    Set lReplacedNodes = new HashSet(); //##63
    do {
      lChanged = false;
      //##63 for (Iterator lIt = pSubpFlow.getBBlocksFromEntry().iterator();
      for (Iterator lIt = pSubpFlow.getListOfBBlocksFromEntry().iterator(); //##63
           lIt.hasNext(); ) {
        lBBlock = (BBlock)lIt.next();
        lChanged = doBBlock(lBBlock, lReplacedNodes) || lChanged;
      }
      lChangedAtLeastOnce |= lChanged;
    }
    while (lChanged);

    return lChangedAtLeastOnce;
  }

  /**
   *
   * doBBlock
   *
   *
   **/
  //##63 public boolean doBBlock(BBlock pBBlock)
  protected boolean doBBlock(BBlock pBBlock, Set pReplacedNodes) //##63
  {
    if ((pBBlock == null)||(pBBlock.getBBlockNumber() == 0))
      return false; //##63
    //##66 SetRefReprList lSetRefReprs = (SetRefReprList)fResults.get(
    //##66   "BBlockSetRefReprs", pBBlock);
    SetRefReprList lSetRefReprs = fSubpFlow.getSetRefReprList(pBBlock); //##66
    if (fDbgLevel >= 2) {
      flowRoot.ioRoot.dbgOpt1.print(2, "ConstPropagationAndFolding.doBBlock",
        "B" + pBBlock.getBBlockNumber()); //##63
      flowRoot.ioRoot.dbgOpt1.print(4, "lSetRefReprs",
        lSetRefReprs.toString()); //##63
    }
    SetRefRepr lSetRefRepr;
    Map lDefs = new HashMap();
    SubpFlow lSubpFlow = pBBlock.getSubpFlow();
    //##63 UDChain lUDChain, lUDChain0;
    UseDefChain lUDChain, lUDChain0; //##63
    IR lExp;
    IR lConstNode;
    IR lFoldedNode;
    IR lParent;
    Sym lSym;
    IR lBrotherNode;
    IR lCallNode = null;
    boolean lReplaced = false;
    //##63 FlowExpId lFlowExpId;
    ExpId lExpId; //##63
    DefVector lDReach, lPReach;

    //##63 for (CoinsIterator lIt = lSetRefReprs.coinsIterator();
    for (Iterator lIt = lSetRefReprs.iterator(); //##63
         lIt.hasNext(); ) {
      lSetRefRepr = (SetRefRepr)lIt.next();
      Iterator lExpIt = lSetRefRepr.expListIterator();

      for (; lExpIt.hasNext(); ) {
        lExp = (IR)lExpIt.next();
        if (pReplacedNodes.contains(lExp)) //##63
          continue; // This expression is already replaced by constant. //##63
        if (!FlowUtil.isLvalue(lExp) || FlowUtil.notDereferenced(lExp)) {
          continue;
        }
        // I.Fukuda
        HIR p = (HIR)((IR)lExp).getParent();
        if (p != null) {
          if (p.getOperator() == HIR.OP_SWITCH) {
            continue;
          }
        }

        try {
          int lTypeKind = lExp.getSym().getSymType().getTypeKind();
          // Substitution of vector variable causes problem in the backend.
          // LIR's structure variable shouldn't be replaced with the value of
          // its first member.
          if (lTypeKind == Type.KIND_VECTOR ||
              lTypeKind == Type.KIND_STRUCT) {
            continue;
          }
        }
        catch (NullPointerException e) {
        }

        if (lSetRefRepr.sets()) {
          if (lExp == lSetRefRepr.defNode()) {
            continue;
          }
        }
        //##63 lFlowExpId = fResults.getFlowExpIdForNode(lExp);
        lExpId = fSubpFlow.getExpId(lExp); //##63
        //##63 if (lFlowExpId != null) {
        if (lExpId != null) { //##63

          // 2005.02.11 I.Fukuda
          Sym sSym = ((HIR)lExp).getSym(); // Symbol used by the expression.
          if (sSym == null) {
            continue;
          }
          if (!(sSym instanceof FlowAnalSym)) {
            continue;
          }
          //##65 BEGIN
          if (lSubpFlow.setOfAddressTakenVariables().contains(sSym))
            continue;
          if ((lSubpFlow.setOfGlobalVariables().contains(sSym))&&
              lSubpFlow.hasCall())
            continue;
          //##65 END
          //##63 if (lSubpFlow.getSymIndexTable().contains(sSym) == false)
          if (lSubpFlow.getIndexedSym(((FlowAnalSym)sSym).getIndex()) == null) { //##63
            continue;
          }
          //Type Etype =lExp.getType();
          int llTypeKind = lExp.getSym().getSymType().getTypeKind();
          if (llTypeKind > Type.KIND_INT_UPPER_LIM) {
            continue;
          }
          if (fDbgLevel > 3) //##67
            opt.dbg(5, "Used var=", ((VarNode)lExp).getVar().toString());
          //##63 UDList lUDList = (UDList)fResults.get("UDList", ((VarNode)lExp).getVar(),lSubpFlow);
          //##63 if (lUDList == null) continue;
          //##63 lUDChain = lUDList.getUDChain(lExp);
          lUDChain = fUDList.getUseDefChain(lExp); //##63
          if (lUDChain == null) {
            continue; //##63
          }
          //
          //lUDChain = ((UDList)fResults.get("UDList0",
          //                           lFlowExpId,lSubpFlow)).getUDChain(lExp);
          if (fDbgLevel > 3) //##67
            opt.dbg(5, "lUDChain", lUDChain);
          if (lUDChain.getDefList().size() == 1) {
            // There is only one defining node.
            IR lDefNode = (IR)lUDChain.getDefList().get(0);
            //
            // comment : 2004.08.10 I.Fukuda
            //  int x,y;
            //   x=1;    (lDefNode -> assign)
            //   y=x+2;
            //
            //System.out.println("Constant propagation");
            // System.out.println("lDefNode="+lDefNode.toString());

            // Checks whether the node really defines (instead of modifies)
            // the symbol.
            ////////////////////////////////////////////////////////////////////
            // I.Fukuda (2005.02.11)
            //if (lDefNode != UDChain.UNINITIALIZED &&
            //    lDefNode != UDChain.PARAM &&
            //     fResults.getFlowExpIdForNode((HIR)SkipConv((HIR)FlowUtil.getChild1(lDefNode)))
            //     == lFlowExpId) {
            //##63 if (lDefNode == UDChain.UNINITIALIZED  ||
            //##63     lDefNode == UDChain.PARAM )
            //##63      continue;
            // Above should be REFINED. //##63
            //##63 BEGIN
            if ((lDefNode == null)||
                (lDefNode == fSubpFlow.getFlowAdapter().dummyUninitialization)||
                (lDefNode == fSubpFlow.getFlowAdapter().dummySettingByParam))//##63
              continue;
            //##63 END
            Sym dSym = ((HIR)lDefNode.getChild1()).getSym();
            // dSym is the symbol defined by lDefNode.
            if (dSym == null) {
              if (!(dSym instanceof FlowAnalSym)) {
                continue;
              }
            }
            if (sSym != dSym) {
              continue;
            }
            //##63 BEGIN
            FlowAnalSymVector lExposed = pBBlock.getExposed();
            FlowAnalSymVector lDefIn = pBBlock.getDefIn();
            if (lExposed.contains((FlowAnalSym)sSym)) {
              if (! lDefIn.contains((FlowAnalSym)sSym)) {
                // The symbol may be undefined.
                continue;
              }
            }
            //##63 END
            HIR Child2 = SkipConv((HIR)FlowUtil.getChild2(lDefNode));
            if (FlowUtil.isConstNode(Child2)) {
              if (Child2.getType() != ((HIR)lExp).getType()) //##65
                continue; // Type differs. //##65
              //##63  lConstNode = OptUtil.createConstNodeFromConstNode( Child2, flowRoot);
              lConstNode = Child2.copyWithOperands(); //##63
              //if (FlowUtil.isConstNode(FlowUtil.getChild2(lDefNode))) {
              //    lConstNode = OptUtil.createConstNodeFromConstNode(
              //                               FlowUtil.getChild2(lDefNode), flowRoot);
              ////////////////////////////////////////////////////////////////////

              //
              // comment : 2004.08.10 I.Fukuda
              //  int x,y;
              //   x=1;    (lConstNode -> '1')
              //   y=x+2;  (lExp ->x)
              //
              //System.out.println("lConstNode="+lConstNode.toString());
              //System.out.println("lExp="+lExp.toString());

              int pTypeKind = lConstNode.getSym().getSymType().getTypeKind();

              //
              // comment : 2004.08.10 I.Fukuda
              // replace:
              // y=x+1 --> y= 1+2;
              //
              lReplaced = true;
              pReplacedNodes.add(lExp); //##63
              OptUtil.replaceNode(lExp, lConstNode);

              lFoldedNode = lConstNode;
              do {
                lParent = lFoldedNode.getParent();
                if (lParent == null) {
                  break;
                }

                //
                // comment : 2004.08.10 I.Fukuda
                //
                // y= 1+2; (lParent --> '+')
                //

                lFoldedNode = OptUtil.fold(lParent, flowRoot);
              }
              while (lFoldedNode != lParent
                && FlowUtil.isConstNode(lFoldedNode));
            }
          }
        }
      }
    }
    return lReplaced;
  }

} // ConstPropagationAndFolding
