DiffLivenessAnalyzer¶

public final class DiffLivenessAnalyzer extends DataFlowAnalyzer ¶

Differentiated liveness analyzer. Finds out which code from the original program is useful for the derivative program. Assumes that activity analysis and plain dependence analysis are done.

The results of this analysis are:

– An annotation “RequiredInDiff” placed on subtrees of the original code whose result is necessary for the derivatives These annotations are accessed through the RequiredInDiff() and *RequiredInDiffCkp() methods.

– A UnitStorage of BlockStorage of TapList of successive diffLiveness infos between each successive instructions.

– A UnitStorage of BlockStorage of TapList of successive diffOverwrite infos between each successive instructions.

TODO: this diffOverwrite (i.e. outB) info is apparently not as good as it could be, because this analysis comes too early. If it came after TBR, then it could implement the data-flow formula from the paper:

W_bar([I;D]) = (W_bar(D) cup out(I)_{if adj-live(I)}) setminus (kill(I) cap (TBR_before(I) cup use(I’)))

whereas here, as we don’t have TBR, the “minus second part” is not done. On the other hand, TBR with recomputation now needs outB. So there is a cycle!

Feature: derives from DataFlowAnalyzer : OK
Feature: able to analyze recursive code: OK
Feature: distinguishes structure elemts: no see NOTE in diffLivenessThroughExpression()
Feature: takes  care  of  pointer dests: OK
Feature: refine on loop-local variables: OK
Feature: std method for call arguments : OK
Feature: able to analyze sub-flow-graph: OK

Methods¶

analyze¶

protected boolean analyze()¶

Analyze DiffLiveness for the “curUnit”. Algorithm: In the 1st BOTTOMUP phase, runs one backward sweep. In the 2nd TOPDOWN phase, runs up to 2 backward sweeps on curUnit’s Flow Graph. If the Context for “curUnit” is “ckp”, then run one analysis with the context’s ckpExitLiveness liveness on the ExitBlock. If the Context for “curUnit” is “nockp”, then run one analysis with the context’s nockpExitLiveness liveness on the ExitBlock. The context may be BOTH “ckp” and “nockp”. When any of the 2 runs encounters a call, then if the call is reverse-mode checkpointed, then the called routine’s Context is set to ckp=true, else either it’s a tangent diff or a non checkpointed call, and the called routine’s Context is set to nockp=true and the current DiffLiveness vector is accumulated into the called routine’s Context “nockpExitLiveness”.

Returns: true, only in the BOTTOMUP phase, if this analysis has built a different result since last time.

compareChannelZoneDataUpstream¶

protected boolean compareChannelZoneDataUpstream(int mpZone, Block refBlock)¶: Compares the info for the Message-Passing zone “mpZone”, upstream curBlock compared with upstream “refBlock”, which is one of the exit Blocks. For this analysis, “mpZone” may also be the %all_io_streams% zone. If curBlock’s is larger, accumulates it into refBlock’s and returns true.

compareDownstreamValues¶

protected boolean compareDownstreamValues()¶: Compare values downstream “curBlock” with the values found on previous sweep.

compareUpstreamChannelValuesWithInitial¶

protected boolean compareUpstreamChannelValuesWithInitial(TapList<Block> initBlocks)¶: Local redefinition of “compareUpstreamChannelValuesWithInitial” that looks at Message-Passing channels BUT ALSO AT the %all_io_streams% zone. This is a patch for the I-O problems in lauvernet-multisail with nooptim:activity, reproduced in set01/lh085 and set01/lh086. When the %all_io_streams% zone becomes live, it must become live right from the initBlocks (i.e. the exit!), to force liveness of the IO “close”. Otherwise we may get files opened twice.

compareUpstreamValues¶

protected boolean compareUpstreamValues()¶: Compare values upstream “curBlock” with the values found on previous sweep.

copyTreeRequiredInDiff¶

public static void copyTreeRequiredInDiff(ActivityPattern activity, Tree oldTree, Tree newTree)¶

If oldTree holds a “LIVENESS” annotation, copy it to newTree.

Parameters

oldTree – the old tree giving its liveness
newTree – the tree gaining it.

cumulCycleValueWithAdditional¶

protected void cumulCycleValueWithAdditional(SymbolTable commonSymbolTable)¶: Accumulate the additional(W)Info, which is cycling, into info(W)TmpCycle.

cumulValueWithAdditional¶

protected void cumulValueWithAdditional(SymbolTable commonSymbolTable)¶: Accumulate the additional(W)Info, which is not cycling, into info(W)Tmp.

getDiffLiveness¶

public BoolVector getDiffLiveness(ActivityPattern pattern)¶

Returns: the liveness info for the given Unit, as stored in entryDiffLivenessesCkp. Refines the result using unitR.

getDiffLivenessOnDiffPtr¶

public BoolVector getDiffLivenessOnDiffPtr(ActivityPattern pattern)¶

Returns: the liveness info on differentiated pointers for the given Unit, as stored in entryDiffLivenessesCkpOnDiffPtr. Refines the result using unitR.

getFrontierLiveness¶

public TapPair<BoolVector, BoolVector> getFrontierLiveness(TapList<FGArrow> frontier)¶

Returns: the “useBar” info for the code from the given frontier to the end of the enclosing Checkpoint. ATTENTION: takes away the bits about test zones ! Requires that “curUnitInfos” is set beforehand to the correct diffLivenessesCkp or diffLivenesses of curUnit.

getFrontierOverwrite¶

public TapPair<BoolVector, BoolVector> getFrontierOverwrite(TapList<FGArrow> frontier)¶

Returns: the “outBar” info for the code from the given frontier to the end of the enclosing Checkpoint. Requires that “curUnitInfosW” is set beforehand to the correct diffOverwritesCkp or diffOverwrites of curUnit.

getValueFlowingBack¶

protected boolean getValueFlowingBack()¶: Get the DiffLiveness info that flows back through the curArrow.

initializeCGForRootUnit¶

protected void initializeCGForRootUnit()¶: Only in the TOPDOWN_NOCKP phase, cleans up and initializes the context of the root Unit “curUnit”.

initializeCGForUnit¶

protected Object initializeCGForUnit()¶: Initializes the context of current Unit “curUnit” for this analysis.

initializeCumulValue¶

protected void initializeCumulValue()¶

initializeInitBlock¶

protected void initializeInitBlock()¶

initializeUnit¶

protected void initializeUnit()¶: Initialization routine before DiffLiveness analysis on “curUnit”. Called once at the beginning of each analyzeBackward(). Sets the DiffLiveness on the ExitBlock to the vector found in the Context, which has been stored in “unitExitLiveness”.

isTreeOrSubtreeRequiredInDiff¶

public static boolean isTreeOrSubtreeRequiredInDiff(ActivityPattern activity, Tree tree, boolean checkpoint)¶

Returns: true if tree, or any subtree inside, is annotated as required because it computes a value that is required by the differentiated computations.

isTreeRequiredInDiff¶

public static boolean isTreeRequiredInDiff(ActivityPattern activity, Tree tree, boolean checkpoint, boolean onDiffPtr)¶

Returns: true if tree is annotated as required because it computes a value that is required by the differentiated computations.

propagateValuesBackwardThroughBlock¶

protected boolean propagateValuesBackwardThroughBlock()¶: Propagate the DiffLiveness info through “CurBlock”.

resetLivenessInfo¶

public void resetLivenessInfo(TapList<Block> blocks)¶: Wipes off all diff liveness annotations inside the given blocks.

run¶

protected void run(TapList<Unit> rootUnits)¶: Runs DiffLiveness analysis bottom-up then top-down from the given Unit’s “rootUnits”.

runAnalysis¶

public static void runAnalysis(CallGraph callGraph, TapList<Unit> rootUnits)¶: Main entry point. Builds a DiffLivenessAnalyzer, stores it and runs it.

setCurBlockEtc¶

protected void setCurBlockEtc(Block block)¶: In addition to super.setCurBlockEtc(), sets nDPZ and vectorMap’s.

setCurUnitActivitiesLivenessesAndOverwrites¶

public void setCurUnitActivitiesLivenessesAndOverwrites(ActivityPattern activity, boolean isJointMode)¶

setCurUnitActivity¶

public void setCurUnitActivity(ActivityPattern activity)¶

setCurUnitEtc¶

public void setCurUnitEtc(Unit unit)¶: In addition to super.setCurUnitEtc(), sets nDPZ.

setDiffPtrRequiredInDiff¶

public static void setDiffPtrRequiredInDiff(ActivityPattern activity, Tree tree)¶: Sets the annotation that tells that the diff pointer of this tree computes a value that is required by the differentiated computations in all cases (CKP or NOPCKP).

setEmptyCumulAndCycleValues¶

protected void setEmptyCumulAndCycleValues()¶: Empty the info(W)Tmp and info(W)TmpCycle that are used to propagate diff-liveness and diff-overwrite upwards.

setPhaseSubGraph¶

public void setPhaseSubGraph()¶: Forces the next diff-liveness runs to analyze only a sub-flow-graph of the current Unit.

setRequiredInDiff¶

public static void setRequiredInDiff(ActivityPattern activity, Tree tree)¶: Sets the annotation that tells that this tree computes a value that is required by the differentiated computations in all cases (CKP or NOPCKP).

setTreeRequiredInDiff¶

public static void setTreeRequiredInDiff(ActivityPattern activity, Tree tree, boolean checkpoint, boolean onDiffPtr)¶: Sets the annotation, at the right place, that tells that this tree computes a value that is required by the differentiated computations. When “checkpoint” is false, the annotation means that this tree is required only in split mode (more vars required). When “onDiffPtr” is true, the annotation is about the diff pointer of this tree (and this tree is necessarily a pointer).

terminateFGForBlock¶

protected void terminateFGForBlock()¶: Build and store the TapList of the propagated DiffLiveness info between successive Instruction’s of this curBlock. This TapList has N+1 infos if curBlock has N Instruction’s, and it is stored into the global “curUnitInfos”.

terminateTermBlock¶

protected void terminateTermBlock()¶

terminateUnit¶

protected boolean terminateUnit()¶: Terminates analysis on the given curUnit. Always returns false, but anyway this result is not used by top-down data-flow analyses.