ADTBRAnalyzer ============= .. java:package:: fr.inria.tapenade.analysis :noindex: .. java:type:: public final class ADTBRAnalyzer extends DataFlowAnalyzer "To Be Recorded" (TBR) analyzer. A Variable is TBR at some program location if its value has been used by an instruction upstream, and this usage is such that the value will be used by the derivative adjoint instructions too. Therefore, if a variable is TBR at some location, and is overwritten later, then it must be saved (e.g. PUSH'ed) just before this overwrite. Methods ------- analyze ^^^^^^^ .. java:method:: @Override protected boolean analyze() :outertype: ADTBRAnalyzer Run TBR analysis on the curUnit, forward. Run one analysis for each ActivityPattern of curUnit. Propagates up the result of analyzeForward(), which is "true" if the analysis up-result is modified since previous run. analyzeInBottomUp ^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean analyzeInBottomUp() :outertype: ADTBRAnalyzer analyzeInTopDown ^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean analyzeInTopDown() :outertype: ADTBRAnalyzer compareChannelZoneDataDownstream ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean compareChannelZoneDataDownstream(int mpZone, Block refBlock) :outertype: ADTBRAnalyzer compareChannelZoneDataUpstream ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean compareChannelZoneDataUpstream(int mpZone, Block refBlock) :outertype: ADTBRAnalyzer compareDownstreamValues ^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean compareDownstreamValues() :outertype: ADTBRAnalyzer Compares tbrTmp info arriving to the exit of this curBlock with same info stored here at the previous sweep, found in tbrsDown.retrieve(curBlock). If new info not null and old info is null or different, must update the stored info with (possibly a copy of) the arriving info, and must return "true" for "modified". If "curBlock" is a loop header and we have a special treatment for cycles, i.e. if runSpecialCycleAnalysis(curBlock) is "true", comparison is done also on the tbrTmpCycle value, compared with the stored tbrsCycleDown.retrieve(curBlock). compareUpstreamValues ^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean compareUpstreamValues() :outertype: ADTBRAnalyzer Compares tbrTmp info arriving to the entry of this curBlock with same info stored here at the previous sweep, found in tbrsUp.retrieve(curBlock). If new info not null and old info is null or different, must update the stored info with (possibly a copy of) the arriving info, and must return "true" for "modified". If "curBlock" is a loop header and we have a special treatment for cycles, i.e. if runSpecialCycleAnalysis(curBlock) is "true", comparison is done also on the tbrTmpCycle value, compared with the stored tbrsCycleUp.retrieve(curBlock). copyAnnotation ^^^^^^^^^^^^^^ .. java:method:: public static void copyAnnotation(ActivityPattern curActivity, Tree fromTree, Tree toTree) :outertype: ADTBRAnalyzer If there is an annotation about "TBR" on "fromTree" for activity "curActivity", copies it onto "toTree". cumulCycleValueWithAdditional ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void cumulCycleValueWithAdditional(SymbolTable commonSymbolTable) :outertype: ADTBRAnalyzer Same as cumulValueWithAdditional(), but for "cycle-related" info. Must initialize the tbrTmpCycle variable if it is is null. cumulValueWithAdditional ^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void cumulValueWithAdditional(SymbolTable commonSymbolTable) :outertype: ADTBRAnalyzer Accumulates the TBR info present in the "additionalTBR" global variable into the global variable "tbrTmp", which contains the non-cycle-related TBR info. The "commonSymbolTable" determines which zones are common between the origin block and the destination Block. For the other zones, the info must vanish. Must initialize the tbrTmp and recompTmp global variables if either is null, meaning "additionalXXX" is the first accumulated info. getFrontierTBR ^^^^^^^^^^^^^^ .. java:method:: public TapPair getFrontierTBR(TapList frontier) :outertype: ADTBRAnalyzer When "frontier" is a list of converging flow arrows that define the entry into a fragment of the current Unit, returns the vector of the zones that are "To Be Recorded" upon entry into this fragment, by collecting the info coming from the frontier's origins. getValueFlowingThrough ^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean getValueFlowingThrough() :outertype: ADTBRAnalyzer Get the TBR info that arrives down-flow through the curArrow. Must return false iff no value arrives, i.e. the control hasn't reached to this point yet. If curArrow cycles from a loop header to its next iteration, returns the special cycles-related TBR info downstream from the loop header. Stores the info into the global additionalTBR, plus when appropriate additionalRecomp. initializeCGForRootUnit ^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void initializeCGForRootUnit() :outertype: ADTBRAnalyzer Only for the degenerate case where we don't want to run full TBR analysis, AND we neither want to restrict TBR saving to used variables, we must set the initial tbr true for all variables, provided they have been initialized. initializeCGForUnit ^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected Object initializeCGForUnit() :outertype: ADTBRAnalyzer Initializes the context of Unit "unit" for TBR analysis, before the sweeps on the CallGraph. Before a BOTTOMUP_1 phase, does nothing and returns null. Before a TOPDOWN_2 phase, places into each ActivityPattern's of curUnit, an initial, empty, top-down context, which is a TBR BoolVector. initializeFGForBlock ^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void initializeFGForBlock() :outertype: ADTBRAnalyzer Precomputes and stores into "cleanLoopIndexZones" the TapIntList of the loop index zones of the clean do-loops around the given "curBlock". Also initializes the boolean attached to each Instruction that tells that this Instruction must remain in the FWD sweep even if recomputed in the BWD sweep. initializeInitBlock ^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void initializeInitBlock() :outertype: ADTBRAnalyzer initializeUnit ^^^^^^^^^^^^^^ .. java:method:: @Override protected void initializeUnit() :outertype: ADTBRAnalyzer Initializations before each TBR analysis of "curUnit". For a top-down analysis, retrieves and uses the call context from the global "topDownContexts". isTBR ^^^^^ .. java:method:: public static boolean isTBR(ActivityPattern curActivity, Tree tree) :outertype: ADTBRAnalyzer :return: true if the given tree is marked "To Be Recorded". isTBROnDiffPtr ^^^^^^^^^^^^^^ .. java:method:: public static boolean isTBROnDiffPtr(ActivityPattern curActivity, Tree tree) :outertype: ADTBRAnalyzer :return: true if the diff of the given tree (which is a pointer) is marked "To Be Recorded". isTBRindex ^^^^^^^^^^ .. java:method:: public static boolean isTBRindex(ActivityPattern curActivity, Tree indexTree) :outertype: ADTBRAnalyzer :return: true if the given tree, which is a DO-loop index, is marked "To Be Recorded", either upon loop entry or upon loop cycle. isTBRindexOnLoopCycle ^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public static boolean isTBRindexOnLoopCycle(ActivityPattern curActivity, Tree indexTree) :outertype: ADTBRAnalyzer :return: true if the given tree, which is a DO-loop index, is marked "To Be Recorded" upon loop cycle. isTBRindexOnLoopEntry ^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public static boolean isTBRindexOnLoopEntry(ActivityPattern curActivity, Tree indexTree) :outertype: ADTBRAnalyzer :return: true if the given tree, which is a DO-loop index, is marked "To Be Recorded" upon loop entry. prepareStorageForUnit ^^^^^^^^^^^^^^^^^^^^^ .. java:method:: public void prepareStorageForUnit(Unit unit) :outertype: ADTBRAnalyzer Creates the storage locations for the results of TBR analysis for the given Unit, if they are not already created. propagateValuesForwardThroughBlock ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected boolean propagateValuesForwardThroughBlock() :outertype: ADTBRAnalyzer Propagates the TBR info tbrTmp forward through "curBlock", upstream. Must return "false" iff the control doesn't reach the curBlock exit (e.g. because of a "stop"). If "curBlock" is a loop header and we have a special treatment for cycles, i.e. if runSpecialCycleAnalysis(curBlock) is "true", propagation must also propagate the tbrTmpCycle value. The propagation can modify tbrTmp and tbrTmpCycle if needed, it is not necessary to copy them. restoreInsideInfo ^^^^^^^^^^^^^^^^^ .. java:method:: public void restoreInsideInfo(TapList blocksInside, Object savedInfo, BlockStorage>> unitTBRs) :outertype: ADTBRAnalyzer run ^^^ .. java:method:: @Override protected void run(TapList rootUnits) :outertype: ADTBRAnalyzer Run TBR analysis on a CallGraph. Bottom-Up and Top-Down are mixed because Top-Down needs the summaries of called procedures provided by Bottom-Up, and conversely PUSH/POP decided during Top-Down may require Bottom-Up to run again. Bottom-Up sweeps compute the TBR info upon exit from each Unit, restricted to TBR due to uses from inside the Unit (in papers: Use(\overleftarrow{Unit})). Top-Down sweeps compute the full interprocedural TBR, using the result of Bottom-Up. runAnalysis ^^^^^^^^^^^ .. java:method:: public static void runAnalysis(CallGraph callgraph, TapList rootUnits) :outertype: ADTBRAnalyzer Run TBR analysis on the given Call Graph, under the given root Units. saveInsideInfo ^^^^^^^^^^^^^^ .. java:method:: public Object saveInsideInfo(TapList blocksInside, BlockStorage>> unitTBRs) :outertype: ADTBRAnalyzer selectAvailableRecomputations ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: TapPair, TapList> selectAvailableRecomputations(TapPair diffOverwrites, TapPair diffLivenesses, TapPair lastChanceZones) :outertype: ADTBRAnalyzer Final placement decision for available recomputations. Looks into recompTmp to select the available recomputations that must be placed at the current location, because they compute a TBR value for which there is a recomputation available and this is the last chance to use this recomputation instruction before it becomes obsolete. When an available recomputation is selected. it is added to the returned list of instructions and removed from recompTmp. tbrTmp and tbrTmpOnDiffPtr may be modified accordingly. :return: the list of recomputation instructions that will be placed "here". setCurBlockEtc ^^^^^^^^^^^^^^ .. java:method:: @Override protected void setCurBlockEtc(Block block) :outertype: ADTBRAnalyzer Set curBlock, curSymbolTable, nDZ, vectorMap's. :param block: The new current Block. setCurUnitActivity ^^^^^^^^^^^^^^^^^^ .. java:method:: public void setCurUnitActivity(ActivityPattern activity) :outertype: ADTBRAnalyzer setCurUnitEtc ^^^^^^^^^^^^^ .. java:method:: @Override public void setCurUnitEtc(Unit unit) :outertype: ADTBRAnalyzer In addition to super.setCurUnitEtc(), sets nDPZ. setEmptyCumulAndCycleValues ^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void setEmptyCumulAndCycleValues() :outertype: ADTBRAnalyzer Empty the global variables tbrTmp and tbrTmpCycle that are used to accumulate the TBR info that arrive from FGArrows. setPhaseSubGraph ^^^^^^^^^^^^^^^^ .. java:method:: public void setPhaseSubGraph() :outertype: ADTBRAnalyzer Forces the next TBR runs to analyze only a sub-flow-graph of the current Unit. summarizeMustTBR ^^^^^^^^^^^^^^^^ .. java:method:: public static void summarizeMustTBR(CallGraph cg) :outertype: ADTBRAnalyzer terminateFGForBlock ^^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void terminateFGForBlock() :outertype: ADTBRAnalyzer terminateTermBlock ^^^^^^^^^^^^^^^^^^ .. java:method:: @Override protected void terminateTermBlock() :outertype: ADTBRAnalyzer terminateUnit ^^^^^^^^^^^^^ .. java:method:: @Override protected boolean terminateUnit() :outertype: ADTBRAnalyzer Terminates TBR analysis on "curUnit". Done after each analysis of "curUnit", i.e. more than once if recursion. For a TOPDOWN_2 phase, builds the final result that contains the TBR status between each pair of successive Instruction's. :return: true if the result propagated up (unitLocalTBR + unitLocalTBROnDiffPtr) has changed since last sweep.