.. java:import:: fr.inria.tapenade.utils BoolMatrix .. java:import:: fr.inria.tapenade.utils BoolVector .. java:import:: fr.inria.tapenade.utils ILLang .. java:import:: fr.inria.tapenade.utils TapIntList .. java:import:: fr.inria.tapenade.utils TapPair .. java:import:: fr.inria.tapenade.utils ToBool .. java:import:: fr.inria.tapenade.utils ToInt .. java:import:: fr.inria.tapenade.utils Tree DiffLivenessAnalyzer ==================== .. java:package:: fr.inria.tapenade.analysis :noindex: .. java:type:: 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! .. parsed-literal:: 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 ^^^^^^^ .. java:method:: @Override protected boolean analyze() :outertype: DiffLivenessAnalyzer 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". :return: true, only in the BOTTOMUP phase, if this analysis has built a different result since last time. compareChannelZoneDataUpstream ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean compareChannelZoneDataUpstream(int mpZone, Block refBlock) :outertype: DiffLivenessAnalyzer 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 ^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean compareDownstreamValues() :outertype: DiffLivenessAnalyzer Compare values downstream "curBlock" with the values found on previous sweep. compareUpstreamChannelValuesWithInitial ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean compareUpstreamChannelValuesWithInitial(TapList initBlocks) :outertype: DiffLivenessAnalyzer 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 ^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean compareUpstreamValues() :outertype: DiffLivenessAnalyzer Compare values upstream "curBlock" with the values found on previous sweep. copyTreeRequiredInDiff ^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public static void copyTreeRequiredInDiff(ActivityPattern activity, Tree oldTree, Tree newTree) :outertype: DiffLivenessAnalyzer If oldTree holds a "LIVENESS" annotation, copy it to newTree. :param oldTree: the old tree giving its liveness :param newTree: the tree gaining it. cumulCycleValueWithAdditional ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void cumulCycleValueWithAdditional(SymbolTable commonSymbolTable) :outertype: DiffLivenessAnalyzer Accumulate the additional(W)Info, which is cycling, into info(W)TmpCycle. cumulValueWithAdditional ^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void cumulValueWithAdditional(SymbolTable commonSymbolTable) :outertype: DiffLivenessAnalyzer Accumulate the additional(W)Info, which is not cycling, into info(W)Tmp. getDiffLiveness ^^^^^^^^^^^^^^^ .. java:method:: public BoolVector getDiffLiveness(ActivityPattern pattern) :outertype: DiffLivenessAnalyzer :return: the liveness info for the given Unit, as stored in entryDiffLivenessesCkp. Refines the result using unitR. getDiffLivenessOnDiffPtr ^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public BoolVector getDiffLivenessOnDiffPtr(ActivityPattern pattern) :outertype: DiffLivenessAnalyzer :return: the liveness info on differentiated pointers for the given Unit, as stored in entryDiffLivenessesCkpOnDiffPtr. Refines the result using unitR. getFrontierLiveness ^^^^^^^^^^^^^^^^^^^ .. java:method:: public TapPair getFrontierLiveness(TapList frontier) :outertype: DiffLivenessAnalyzer :return: 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 ^^^^^^^^^^^^^^^^^^^^ .. java:method:: public TapPair getFrontierOverwrite(TapList frontier) :outertype: DiffLivenessAnalyzer :return: 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 ^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean getValueFlowingBack() :outertype: DiffLivenessAnalyzer Get the DiffLiveness info that flows back through the curArrow. initializeCGForRootUnit ^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void initializeCGForRootUnit() :outertype: DiffLivenessAnalyzer Only in the TOPDOWN_NOCKP phase, cleans up and initializes the context of the root Unit "curUnit". initializeCGForUnit ^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected Object initializeCGForUnit() :outertype: DiffLivenessAnalyzer Initializes the context of current Unit "curUnit" for this analysis. initializeCumulValue ^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void initializeCumulValue() :outertype: DiffLivenessAnalyzer initializeInitBlock ^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void initializeInitBlock() :outertype: DiffLivenessAnalyzer initializeUnit ^^^^^^^^^^^^^^ .. java:method:: @Override protected void initializeUnit() :outertype: DiffLivenessAnalyzer 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 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public static boolean isTreeOrSubtreeRequiredInDiff(ActivityPattern activity, Tree tree, boolean checkpoint) :outertype: DiffLivenessAnalyzer :return: true if tree, or any subtree inside, is annotated as required because it computes a value that is required by the differentiated computations. isTreeRequiredInDiff ^^^^^^^^^^^^^^^^^^^^ .. java:method:: public static boolean isTreeRequiredInDiff(ActivityPattern activity, Tree tree, boolean checkpoint, boolean onDiffPtr) :outertype: DiffLivenessAnalyzer :return: true if tree is annotated as required because it computes a value that is required by the differentiated computations. propagateValuesBackwardThroughBlock ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean propagateValuesBackwardThroughBlock() :outertype: DiffLivenessAnalyzer Propagate the DiffLiveness info through "CurBlock". resetLivenessInfo ^^^^^^^^^^^^^^^^^ .. java:method:: public void resetLivenessInfo(TapList blocks) :outertype: DiffLivenessAnalyzer Wipes off all diff liveness annotations inside the given blocks. run ^^^ .. java:method:: @Override protected void run(TapList rootUnits) :outertype: DiffLivenessAnalyzer Runs DiffLiveness analysis bottom-up then top-down from the given Unit's "rootUnits". runAnalysis ^^^^^^^^^^^ .. java:method:: public static void runAnalysis(CallGraph callGraph, TapList rootUnits) :outertype: DiffLivenessAnalyzer Main entry point. Builds a DiffLivenessAnalyzer, stores it and runs it. setCurBlockEtc ^^^^^^^^^^^^^^ .. java:method:: @Override protected void setCurBlockEtc(Block block) :outertype: DiffLivenessAnalyzer In addition to super.setCurBlockEtc(), sets nDPZ and vectorMap's. setCurUnitActivitiesLivenessesAndOverwrites ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public void setCurUnitActivitiesLivenessesAndOverwrites(ActivityPattern activity, boolean isJointMode) :outertype: DiffLivenessAnalyzer setCurUnitActivity ^^^^^^^^^^^^^^^^^^ .. java:method:: public void setCurUnitActivity(ActivityPattern activity) :outertype: DiffLivenessAnalyzer setCurUnitEtc ^^^^^^^^^^^^^ .. java:method:: @Override public void setCurUnitEtc(Unit unit) :outertype: DiffLivenessAnalyzer In addition to super.setCurUnitEtc(), sets nDPZ. setDiffPtrRequiredInDiff ^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public static void setDiffPtrRequiredInDiff(ActivityPattern activity, Tree tree) :outertype: DiffLivenessAnalyzer 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 ^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void setEmptyCumulAndCycleValues() :outertype: DiffLivenessAnalyzer Empty the info(W)Tmp and info(W)TmpCycle that are used to propagate diff-liveness and diff-overwrite upwards. setPhaseSubGraph ^^^^^^^^^^^^^^^^ .. java:method:: public void setPhaseSubGraph() :outertype: DiffLivenessAnalyzer Forces the next diff-liveness runs to analyze only a sub-flow-graph of the current Unit. setRequiredInDiff ^^^^^^^^^^^^^^^^^ .. java:method:: public static void setRequiredInDiff(ActivityPattern activity, Tree tree) :outertype: DiffLivenessAnalyzer 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 ^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public static void setTreeRequiredInDiff(ActivityPattern activity, Tree tree, boolean checkpoint, boolean onDiffPtr) :outertype: DiffLivenessAnalyzer 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 ^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void terminateFGForBlock() :outertype: DiffLivenessAnalyzer 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 ^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void terminateTermBlock() :outertype: DiffLivenessAnalyzer terminateUnit ^^^^^^^^^^^^^ .. java:method:: @Override protected boolean terminateUnit() :outertype: DiffLivenessAnalyzer Terminates analysis on the given curUnit. Always returns false, but anyway this result is not used by top-down data-flow analyses.