ADTBRAnalyzer¶

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¶

protected boolean analyze()¶: 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¶

protected boolean analyzeInBottomUp()¶

analyzeInTopDown¶

protected boolean analyzeInTopDown()¶

compareChannelZoneDataDownstream¶

protected boolean compareChannelZoneDataDownstream(int mpZone, Block refBlock)¶

compareChannelZoneDataUpstream¶

protected boolean compareChannelZoneDataUpstream(int mpZone, Block refBlock)¶

compareDownstreamValues¶

protected boolean compareDownstreamValues()¶: 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¶

protected boolean compareUpstreamValues()¶: 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¶

public static void copyAnnotation(ActivityPattern curActivity, Tree fromTree, Tree toTree)¶: If there is an annotation about “TBR” on “fromTree” for activity “curActivity”, copies it onto “toTree”.

cumulCycleValueWithAdditional¶

protected void cumulCycleValueWithAdditional(SymbolTable commonSymbolTable)¶: Same as cumulValueWithAdditional(), but for “cycle-related” info. Must initialize the tbrTmpCycle variable if it is is null.

cumulValueWithAdditional¶

protected void cumulValueWithAdditional(SymbolTable commonSymbolTable)¶: 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¶

public TapPair<BoolVector, BoolVector> getFrontierTBR(TapList<FGArrow> frontier)¶: 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¶

protected boolean getValueFlowingThrough()¶: 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¶

protected void initializeCGForRootUnit()¶: 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¶

protected Object initializeCGForUnit()¶: 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¶

protected void initializeFGForBlock()¶: 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¶

protected void initializeInitBlock()¶

initializeUnit¶

protected void initializeUnit()¶: Initializations before each TBR analysis of “curUnit”. For a top-down analysis, retrieves and uses the call context from the global “topDownContexts”.

isTBR¶

public static boolean isTBR(ActivityPattern curActivity, Tree tree)¶

Returns: true if the given tree is marked “To Be Recorded”.

isTBROnDiffPtr¶

public static boolean isTBROnDiffPtr(ActivityPattern curActivity, Tree tree)¶

Returns: true if the diff of the given tree (which is a pointer) is marked “To Be Recorded”.

isTBRindex¶

public static boolean isTBRindex(ActivityPattern curActivity, Tree indexTree)¶

Returns: 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¶

public static boolean isTBRindexOnLoopCycle(ActivityPattern curActivity, Tree indexTree)¶

Returns: true if the given tree, which is a DO-loop index, is marked “To Be Recorded” upon loop cycle.

isTBRindexOnLoopEntry¶

public static boolean isTBRindexOnLoopEntry(ActivityPattern curActivity, Tree indexTree)¶

Returns: true if the given tree, which is a DO-loop index, is marked “To Be Recorded” upon loop entry.

prepareStorageForUnit¶

public void prepareStorageForUnit(Unit unit)¶: Creates the storage locations for the results of TBR analysis for the given Unit, if they are not already created.

propagateValuesForwardThroughBlock¶

protected boolean propagateValuesForwardThroughBlock()¶: 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¶

public void restoreInsideInfo(TapList<Block> blocksInside, Object savedInfo, BlockStorage<TapList<TapPair<BoolVector, BoolVector>>> unitTBRs)¶

run¶

protected void run(TapList<Unit> rootUnits)¶: 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¶

public static void runAnalysis(CallGraph callgraph, TapList<Unit> rootUnits)¶: Run TBR analysis on the given Call Graph, under the given root Units.

saveInsideInfo¶

public Object saveInsideInfo(TapList<Block> blocksInside, BlockStorage<TapList<TapPair<BoolVector, BoolVector>>> unitTBRs)¶

selectAvailableRecomputations¶

TapPair<TapList<Instruction>, TapList<Instruction>> selectAvailableRecomputations(TapPair<BoolVector, BoolVector> diffOverwrites, TapPair<BoolVector, BoolVector> diffLivenesses, TapPair<BoolVector, BoolVector> lastChanceZones)¶

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.

Returns: the list of recomputation instructions that will be placed “here”.

setCurBlockEtc¶

protected void setCurBlockEtc(Block block)¶

Set curBlock, curSymbolTable, nDZ, vectorMap’s.

Parameters

block – The new current Block.

setCurUnitActivity¶

public void setCurUnitActivity(ActivityPattern activity)¶

setCurUnitEtc¶

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

setEmptyCumulAndCycleValues¶

protected void setEmptyCumulAndCycleValues()¶: Empty the global variables tbrTmp and tbrTmpCycle that are used to accumulate the TBR info that arrive from FGArrows.

setPhaseSubGraph¶

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

summarizeMustTBR¶

public static void summarizeMustTBR(CallGraph cg)¶

terminateFGForBlock¶

protected void terminateFGForBlock()¶

terminateTermBlock¶

protected void terminateTermBlock()¶

terminateUnit¶

protected boolean terminateUnit()¶

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.

Returns: true if the result propagated up (unitLocalTBR + unitLocalTBROnDiffPtr) has changed since last sweep.