coins.opt
クラス NormalizeHir

java.lang.Object
  |
  +--coins.opt.NormalizeHir

public class NormalizeHir
extends java.lang.Object

 NormalizeHir
   normalizes HIR to prepare for PRE.

   Remove critical edge (an edge from a basic block with multiple
   successor to a basic block with multiple predecessor) by inserting
   an empty basic block in the critical edge.

 if (condition) then goto joinLabel
  ==> unnecessary to change.
  (can be inserted ahead of goto-statement in thenBBlock.)

 if (condition) then thenBBlock else elseBBlock;
  ==> unnecessary to change.

 if (condition1) { // if (condition1 && condition2) ...
  if (condition2) {
  thenLabel2:
  thenPart1; goto endIfLabel;
  }else
  elseLabel2:
  goto elsLabel1;
 }else {
  elseLabel1:
   elsePart;
 endIfLabel:
   ==>
   if (condition1) {
  if (condition2) {
  thenLabel2:
    thenPart1; goto endIfLabel;
  }else
  elseLabel2:
    goto elsLabel1-2;
   }else { (block
  elseLabel1:
  elseLabel1-2:
   elsePart;
   ) // block end
   endIfLabel:

 if (condition1) { // if (condition1 || condition2) ...
  thenLabel1:
  thenPart; goto endIfLabel;
 }else {
  elseLabel1:
  if (condition2) {
  thenLabel2:
  goto thenLabel1;
  }else
  elseLabel2:
  elsePart;
  }
 endIfLabel:
   ==>
   if (condition1) {
  thenLabel1: (block
    thenLabel1-2:
    thenPart; goto endIfLabel;
  ) // block end
   }else {
  elseLabel1:
  if (condition2) {
  thenLabel2:
    goto thenLabel1-2;
  }else
  elseLabel2:
    elsePart;
  }
   endIfLabel:

 if (condition) then thenBBlock; (null elseBBlock)
  ==> if (condition) then thenBBlock else emptyBBlock;

 if (condition) else elseBBlock; (null thenBBlock)
  ==> if (condition) then emptyBBlock else elseBBlock;

 swith (exp) { case I1: statement1; break;
     case I2; statement2; break;
     ... default: defaultBBlock; }
  ==> unnecessary to change.

 swith (exp) { case I1: case I2; statement2; break;
     ...
     default: defaultBBlock; }
  ==>
   swith (exp) { case (I1-I2): // case label I1, I2 are
     // attached to one statement.
     statement2; goto swithcEndLabel;
     ... default: defaultBBlock; }

 swith (exp) { case I1: statement1;
     case I2: statement2; break;
     ...
     case In: statementn;
     default: defaultBBlock; }
  ==>
   swith (exp) { case I1: statement1; goto L2;
     case I2; goto L2;
    L2: statement2; goto swithcEndLabel;
     case In: statementn; goto Ln;
     ...
     default:
    Ln: defaultBBlock; }

 (loop
   loopInitPart
   loopBackLabel:
   startCondition (if (! startCondition) goto loopEndLabel)
   loopBodyLabel:
   loopBody  (without break;)
   loopStepLabel:null
   // endCondition is null
   loopStepPart (goto loopBackLabel)
   loopEndLabel:
   loopEndPart
  )
  ==>  unnecessary to change.

 (loop
   loopInitPart
   loopBackLabel:
   // startCondition is null
   loopBodyLabel:
   loopBody  (without break;)
   loopStepLabel:null
   endCondition (if (! endCondition) goto loopEndLabel)
   loopStepPart (goto loopBackLabel)
   loopEndLabel:
   loopEndPart
  )
  ==>
 (loop
   loopInitPart
   (jump loopBodyLabel) -- insert
   loopBackLabel:
   // startCondition is null
   loopBodyLabel:
   loopBody  (without break;)
   loopStepLabel:null
   endCondition (if (! endCondition) goto loopEndLabel)
   loopStepPart (goto loopBackLabel)
   loopEndLabel:
   loopEndPart
  )

 (loop
   loopInitPart
   loopBackLabel:
   startCondition (if (! startCondition) goto loopEndLabel)
   loopBodyLabel:
   loopBody with break
     (if (breakCondition) goto loopEndLabel)
   rest of loopBody
   loopStepLabel: // loopEndCondition is not null.
     if (! loopEndCondition) goto loopEndLabel;
   loopStepPart (goto loopBackLabel)
   loopEndLabel:
   loopEndPart
  )
  ==>
  (block
  (loop
     loopInitPart
     loopBackLabel:
   startCondition (if (! startCondition) goto loopEndLabel)
     loopBodyLabel:
   loopBody with break
   (if (breakCondition) goto loopExitLabel)
   rest of loopBody
   loopStepLabel:  // loopEndCondition is not null.
   if (! loopEndCondition) goto loopExitLabel;
     loopStepPart (goto loopBackLabel)
     loopEndLabel: // set loopEndPart as null)
   ) // loop end
   loopExitLabel:
     loopEndPart
   ) // block end

 (loop // Most general loop.
   loopInitPart;
   if (startCondition) {
   statements added by addToconditionalInitPart
   goto loopBodyLabel;
   }else goto looEndLabel;
   loopBackLabel:
   startConditionPart(if (! startCondition) goto loopEndLabel;)
   loopBodyLabel:
   loopBody;
   if (breakCondition) goto loopEndLabel;
   ...
   if (continueCondition) goto loopStepLabel;
   ...
   loopStepLabel:
   endCondition (if (! endCondition) goto loopEndLabel)
   loopStepPart (goto loopBackLabel;)
   loopEndLabel:
   loopEndPart;
 )
  ==>
 (block
  (loop
     loopInitPart;
     if (startCondition) {
   statements added by addToconditionalInitPart
   goto conditionalInitLabel;
     }else goto loopExitLabel;
     loopBackLabel:
   startConditionPart(if (! startCondition) goto loopEndLabel)
     loopBodyLabel: null
     conditionalInitLabel:
   loopBody;
   if (breakCondition) goto loopExitLabel;
   ...
   if (continueCondition) goto loopStepLabel;
   ...
   loopStepLabel:null
     endCondition (if (! endCondition) goto loopEndLabel)
     loopStepPart (goto loopBackLabel)
     loopEndLabel: null
   ) // loop end
   loopExitlabel:
  loopEndPart;
   ) // block end

  Rules for loop conversion:
  If break or conditionalInit are contained in the loop,
  add loopExitlabel after loopEndLabel and attach loopEndPart
  to loopExitLabel, and then change loopEndLabel of jump
  statements in conditionalInit and break to loopExitLabel.
  Also change loopBodyLabel of conditionalInit to
  conditionalInitLabel attached after loopBodyLabel.
 


フィールドの概要
protected  java.util.List fCriticalEdgeTargetLabels
          fCriticalEdgeTargetLabels is the set of labels of critical edge target statements.
protected  int fCriticalStmtIndex
          fStmtWithCriticalEdge[fCriticalStmtIndex] is the statement under processing by eliminateCriticalEdge.
protected  int fDbgLevel
          fJumpListt is the list of jump statements in thte current subprogram.
(パッケージプライベート)  Flow flow
           
(パッケージプライベート)  FlowRoot flowRoot
           
protected  java.util.List fStmtWithCriticalEdge
          fStmtWithCriticalEdge lists control statements having critical edges.
(パッケージプライベート)  SubpDefinition fSubpDef
           
(パッケージプライベート)  SubpFlow fSubpFlow
           
protected  boolean fTransformed
          fTransformed is set to true if HIR is changed by normalization, else it is set to false.
(パッケージプライベート)  HIR hir
           
(パッケージプライベート)  IoRoot ioRoot
           
(パッケージプライベート)  SymRoot symRoot
           
 
コンストラクタの概要
NormalizeHir(FlowRoot pFlowRoot, SubpDefinition pSubpDef)
          Constructor to normalize HIR.
 
メソッドの概要
protected  void adjustHirPositionOfLabels1(Stmt pStmt)
           
protected  void adjustLinkages(Stmt pOldStmt, Stmt pNewStmt)
           
 boolean checkCriticalEdges(SubpFlow pSubpFlow, SubpDefinition pSubpDef)
           
protected  Stmt containingControlStmt(HIR pHir)
          Get the control statement containing pHir.
protected  Stmt containingControlStmtInBBlock(HIR pHir, BBlock pFromBBlock)
          Get control statement that either contains pHir or compound control statement in pFromBBlock.
protected  Stmt containingStmt(Stmt pHir1, Stmt pHir2)
          If pHir1 contains pHir2 then return pHir1; else if pHir2 contains pHir1 then return pHir2; else return null;
 void dbg(int level, java.lang.Object pObject)
           
 void dbg(int level, java.lang.String pHeader, java.lang.Object pObject)
           
protected  void eliminateCriticalEdge()
           
protected  void eliminateCriticalEdgeOfCompoundStmt(Stmt pStmt)
           
protected  Stmt getCompoundControlStmtOfBBlock(BBlock pBBlock)
          Get the compound control statement in pBBlock.
protected  Stmt getPreviousStmtOfCaseStmt(Stmt pCaseStmt, SwitchStmt pSwitchStmt, int pCaseIndex)
           
protected  boolean isCompoundControlStmt(HIR pHir)
           
static boolean isEmptyStmt(Stmt pStmt)
           
protected  boolean labelListContainsLabelOfStmt(java.util.List pLabelList, LabeledStmt pLabeledStmt)
           
protected  void mergeLabelsOfStmt1ToStmt2(LabeledStmt pStmt1, LabeledStmt pStmt2)
           
protected  boolean processCriticalEdge()
           
protected  void processIfStmt(IfStmt pIfStmt)
          processIfStmt Remove critical edge of if-statement.
protected  void processLoopStmt(LoopStmt pLoopStmt)
          processLoopStmt removes critical edges from the given loop statement.
protected  void processSwitchStmt(SwitchStmt pSwitchStmt)
          processSwitchStmt removes critical edges from the given switch statement.
protected  void separateJumpTarget(JumpStmt pJumpStmt, LabeledStmt pLabeledStmt)
           
 
クラス java.lang.Object から継承したメソッド
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

フィールドの詳細

ioRoot

IoRoot ioRoot

symRoot

SymRoot symRoot

flowRoot

FlowRoot flowRoot

flow

Flow flow

fSubpFlow

SubpFlow fSubpFlow

hir

HIR hir

fSubpDef

SubpDefinition fSubpDef

fTransformed

protected boolean fTransformed
fTransformed is set to true if HIR is changed by normalization, else it is set to false.


fStmtWithCriticalEdge

protected java.util.List fStmtWithCriticalEdge
fStmtWithCriticalEdge lists control statements having critical edges. The listed statements may be IfStmt, LoopStmt, SwitchStmt. This should be maintained (by adjustLinkages) when statements are copied/deleted.


fCriticalStmtIndex

protected int fCriticalStmtIndex
fStmtWithCriticalEdge[fCriticalStmtIndex] is the statement under processing by eliminateCriticalEdge.


fCriticalEdgeTargetLabels

protected java.util.List fCriticalEdgeTargetLabels
fCriticalEdgeTargetLabels is the set of labels of critical edge target statements.


fDbgLevel

protected int fDbgLevel
fJumpListt is the list of jump statements in thte current subprogram. If the current subprogram has no critical edge, it is empty. This is used at the first statge of eliminateCritical edges and after that, it is not necessary to maintain.

コンストラクタの詳細

NormalizeHir

public NormalizeHir(FlowRoot pFlowRoot,
                    SubpDefinition pSubpDef)
Constructor to normalize HIR.

パラメータ:
pFlowRoot -
メソッドの詳細

processCriticalEdge

protected boolean processCriticalEdge()

containingStmt

protected Stmt containingStmt(Stmt pHir1,
                              Stmt pHir2)
If pHir1 contains pHir2 then return pHir1; else if pHir2 contains pHir1 then return pHir2; else return null;

パラメータ:
pHir1 - statement.
pHir2 - statement.
戻り値:
containing statement.

containingControlStmtInBBlock

protected Stmt containingControlStmtInBBlock(HIR pHir,
                                             BBlock pFromBBlock)
Get control statement that either contains pHir or compound control statement in pFromBBlock.

パラメータ:
pHir -
pFromBBlock - starting BBlock of critical edge.
戻り値:
the control statement

containingControlStmt

protected Stmt containingControlStmt(HIR pHir)
Get the control statement containing pHir. If there is no control statement containing pHir, then return null.

パラメータ:
pHir -
戻り値:
the control statement containing pHir.

getCompoundControlStmtOfBBlock

protected Stmt getCompoundControlStmtOfBBlock(BBlock pBBlock)
Get the compound control statement in pBBlock. If not found, return null. The conpound control statement is found, then it is the last statement in pBBlock.

パラメータ:
pBBlock - within which compound control statement is to be found.
戻り値:
the compound control statement or null.

isCompoundControlStmt

protected boolean isCompoundControlStmt(HIR pHir)

isEmptyStmt

public static boolean isEmptyStmt(Stmt pStmt)

eliminateCriticalEdge

protected void eliminateCriticalEdge()

eliminateCriticalEdgeOfCompoundStmt

protected void eliminateCriticalEdgeOfCompoundStmt(Stmt pStmt)

separateJumpTarget

protected void separateJumpTarget(JumpStmt pJumpStmt,
                                  LabeledStmt pLabeledStmt)

processIfStmt

protected void processIfStmt(IfStmt pIfStmt)
processIfStmt Remove critical edge of if-statement.


processLoopStmt

protected void processLoopStmt(LoopStmt pLoopStmt)
processLoopStmt removes critical edges from the given loop statement.

パラメータ:
pLoopStmt - loop statement.

processSwitchStmt

protected void processSwitchStmt(SwitchStmt pSwitchStmt)
processSwitchStmt removes critical edges from the given switch statement.

パラメータ:
pSwitchStmt - switch statement.

getPreviousStmtOfCaseStmt

protected Stmt getPreviousStmtOfCaseStmt(Stmt pCaseStmt,
                                         SwitchStmt pSwitchStmt,
                                         int pCaseIndex)

labelListContainsLabelOfStmt

protected boolean labelListContainsLabelOfStmt(java.util.List pLabelList,
                                               LabeledStmt pLabeledStmt)

mergeLabelsOfStmt1ToStmt2

protected void mergeLabelsOfStmt1ToStmt2(LabeledStmt pStmt1,
                                         LabeledStmt pStmt2)

adjustLinkages

protected void adjustLinkages(Stmt pOldStmt,
                              Stmt pNewStmt)

adjustHirPositionOfLabels1

protected void adjustHirPositionOfLabels1(Stmt pStmt)

checkCriticalEdges

public boolean checkCriticalEdges(SubpFlow pSubpFlow,
                                  SubpDefinition pSubpDef)

dbg

public void dbg(int level,
                java.lang.String pHeader,
                java.lang.Object pObject)

dbg

public void dbg(int level,
                java.lang.Object pObject)