ADActivityAnalyzer¶

public final class ADActivityAnalyzer extends DataFlowAnalyzer ¶

Analyzer in charge of activity analysis on a CallGraph. This is useful for Automatic Differentiation. The results of this analysis are:

An annotation “ActiveExpr” placed on subtrees of the original code whose value is active. These annotations are accessed through the AnnotatedActive() methods.
A UnitStorage “activities” of BlockStorage of TapList of successive activity infos between each successive instructions.
A UnitStorage “usefulnesses”, same for usefulnesses.
A UnitStorage “callActivities” of activity at the entry point of each unit.
A UnitStorage “exitActivities” of activity at the exit point of each unit.
A UnitStorage “varFunctionADActivities” of callActivity and exitUsefulness for each “function name” argument of each unit.

Feature: derives from DataFlowAnalyzer : OK
Feature: able to analyze recursive code: OK
Feature: distinguishes structure elemts: OK
Feature: takes  care  of  pointer dests: ?? for BOTTOMUP_1, OK for TOPDOWN_2
Feature: refine on loop-local variables: not for BOTTOMUP_1, disconnected for TOPDOWN_2 cf [pbLoopArrays]
Feature: std method for call arguments : OK
Feature: able to analyze sub-flow-graph: OK
Feature: specialized wrt each activity : OK obviously only for TOPDOWN_2

Constructors¶

ADActivityAnalyzer¶

ADActivityAnalyzer(CallGraph cg, TapList<DiffRoot> diffRoots, int diffKind)¶: Creates an ADActivityAnalyzer, given the CallGraph “cg” on which it will work.

Methods¶

accumulateValuesFromUpstream¶

protected boolean accumulateValuesFromUpstream()¶

Collects the data-flow information from the incoming flow arrows.

Returns: true when the control flow effectively reaches this point.

analyze¶

protected boolean analyze()¶: Analyze activities for the “curUnit”. For the BOTTOMUP_1 phase, returns true when the resulting dependencies for “curUnit” were modified, false otherwise. For the TOPDOWN_2 phase, always returns false, but anyway this result is not used by top-down data-flow analyses.

buildDefaultIntrinsicCallActivity¶

protected static BoolVector buildDefaultIntrinsicCallActivity(Unit intrinsicUnit, int diffKind)¶

compareChannelZoneDataDownstream¶

protected boolean compareChannelZoneDataDownstream(int mpZone, Block refBlock)¶

compareChannelZoneDataUpstream¶

protected boolean compareChannelZoneDataUpstream(int mpZone, Block refBlock)¶

compareDownstreamValues¶

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

compareUpstreamValues¶

protected boolean compareUpstreamValues()¶

Compare data-flow value upstream “curBlock”, with the value on previous sweep.

Returns: true when something has changed and therefore another Flow Graph sweep is probably necessary.

cumulCycleValueWithAdditional¶

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

cumulValueWithAdditional¶

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

formalArgsActivity¶

public static boolean[] formalArgsActivity(ActivityPattern pattern)¶

For a given activity pattern, finds whether each formal argument of the concerned Unit has a derivative or not.

Parameters

pattern – the given activity pattern

Returns

an array of booleans, one for each formal argument plus a last one for the function’s result, where the boolean of rank k (0 to nbArgs) is true iff the (1+k)’th argument has a derivative argument, either because an input derivative is expected, or an output derivative will be returned, or both. Here, a variable’s derivative is expected either if the variable is an “active” value or if it is a ReqX or AvlX pointer Special case for the function’s result, which is never expected as an input.

functionDiffFormalRequired¶

public static BoolVector functionDiffFormalRequired(ActivityPattern pattern, boolean withPointers)¶

Returns the info whether the arguments of a Unit require a differentiated counterpart, for the given activity pattern of this Unit. The info is expressed in terms of each elementary argument of the Unit, i.e. as a BoolVector following the Unit’s public shape. An elementary argument “arg” requires a differentiated counterpart when either this arg is active upon entry or exit of this unit, or because (a) (it is relatively hard to declare locally (e.g. dynamic sizes in Fortran) OR its derivative is already available at (one of) the call sites) AND (b) (it becomes active somewhere inside unit, OR the memory location of its differentiated counterpart will be needed by a (to-be-active) pointer somewhere inside unit).

Parameters

pattern – an activity pattern of this unit
withPointers – if true, count also zones that have a diff because of ReqX analysis.

Returns

the unit’s zones (of kind ALLKIND) that require a differentiated counterpart,

getDiffDeps¶

public BoolMatrix getDiffDeps(Unit unit)¶

Returns: the published or built result, for “unit”, of the AD dependencies analysis, i.e. the dependencies signature, of type BoolMatrix , of the Unit.

getUpdateModifiedZones¶

public static BoolVector getUpdateModifiedZones(BoolMatrix deps, BoolVector variedOnCall, Unit unit)¶

Variant of getModifiedZones special for the initial update through the Unit’s deps.

Returns: a vector with true at index i if diff of zone i will be modified by the tangent of the routine whose dependencies are “deps”, and called with the given varied→useful context. Diff of zone i is NOT modified when both input and output diffs are 0.0, or also when the row i of “deps” is “implicit-identity”. Assumes the matrix is not “implicit-zero”. Not very well understood yet why this must be different from getFinalModifiedZones(): TODO.

getUpdateModifiedZonesT¶

public static BoolVector getUpdateModifiedZonesT(BoolMatrix deps, BoolVector usefulOnExit)¶

Variant of getModifiedZonesT special for the initial update through the Unit’s deps.

Returns: a vector with true at index i if diff of zone i will be modified by the adjoint (in the “variedOnCall”→”usefulOnExit” calling context) of the routine whose dependencies are “deps”. This is a sort of transposed equivalent of getUpdateModifiedZones(). Assumes the matrix is not “implicit-zero”. Diff of zone i is NOT modified when both input and output diffs are 0.0, or also when the column i of “deps” is identity, i.e. all-zero except for “implicit-identity” on the diagonal. Not very well understood yet why this must be different from getFinalModifiedZonesT() : TODO .

getValueFlowingBack¶

protected boolean getValueFlowingBack()¶

Returns: the (usefulness) value that flows back through curArrow.

getValueFlowingThrough¶

protected boolean getValueFlowingThrough()¶

Returns: the (variedness) value that flows down through curArrow.

hasOneAnnotatedActive¶

protected static boolean hasOneAnnotatedActive(ActivityPattern curActivity, Tree ioArg, SymbolTable symbolTable)¶

haveDifferentiatedVariable¶

public static boolean haveDifferentiatedVariable(TapList<ZoneInfo> zones)¶

Parameters

zones – the list of ZoneInfo’s to look from.

Returns

true iff one of the “zones” is known to have a differentiated variable, i.e. is active at some time.

initializeCGForRootUnit¶

protected void initializeCGForRootUnit()¶: Cleans up and initializes the context of curUnit, which is a root Unit.

initializeCGForUnit¶

protected Object initializeCGForUnit()¶: Initializes the context of Unit “unit” for this analysis on the Call-Graph.

initializeCumulValue¶

protected void initializeCumulValue()¶

initializeFGForBlock¶

protected void initializeFGForBlock()¶

initializeInitBlock¶

protected void initializeInitBlock()¶

initializeUnit¶

protected void initializeUnit()¶: Initialization routine before fixpoint propagation on the given “curUnit”.

isActiveArg¶

public static boolean isActiveArg(int zoneRk, BoolVector activeZones, WrapperTypeSpec argType)¶

Tells whether a zone is active with respect to a given activity and therefore must have a derivative. Both zoneRk and activeZones nust use the same “kind” i.e. ALLKIND or diffKind When activeZones is not given, an approximate answer is built by checking that the given argType of this zone is “differentiable”.

Parameters

zoneRk – The rank of the considered zone.
activeZones – The considered activity.
argType – The type of the considered zone.

isActiveUnit¶

public boolean isActiveUnit(Unit unit)¶

Returns: true iff the given “unit” is active, which means it must have a differentiated counterpart.

isActiveUnit¶

public boolean isActiveUnit(ActivityPattern pattern)¶

isAnnotatedActive¶

public static boolean isAnnotatedActive(ActivityPattern pattern, Tree tree, SymbolTable symbolTable)¶

Returns: true if the annotation “ActiveExpr” is present, which means that this “tree” returns or sets an active value.

oneSymbolDeclIsActive¶

public static boolean oneSymbolDeclIsActive(TapList<SymbolDecl> symbolDecls)¶

propagateValuesBackwardThroughBlock¶

protected boolean propagateValuesBackwardThroughBlock()¶: Propagate the (usefulness) info through “curBlock”.

propagateValuesForwardThroughBlock¶

protected boolean propagateValuesForwardThroughBlock()¶: Propagate the (ad-deps or variedness) info through “curBlock”.

propagateValuesStaticallyThroughExpression¶

protected void propagateValuesStaticallyThroughExpression()¶

putBackSharingZones¶

public void putBackSharingZones(BoolVector variedOnCall, BoolVector usefulOnExit, Unit unit)¶: Put back zones that share a variable with another zone which is varied or useful: (cf lh91).

reMergeAndAnnotate¶

public void reMergeAndAnnotate(TapList<Block> portionBlocks, ActivityPattern activity)¶

After a local recomputation of ADActivity on a sub-flow-graph of the current Unit, does again the merging of Usefulness into Variedness to obtain activity, and also recomputes the Activity annotations. Does this on all the Blocks inside the sub-flow-graph.

Parameters

portionBlocks – The list of all Blocks inside the sub-flow-graph.
activity – The current ActivityPattern for which we have been recomputing this Unit’s activity.

run¶

protected void run(TapList<Unit> rootUnits)¶

Runs activity analysis from the given Unit’s “rootUnits”. First, a bottom-up sweep builds the differentiable dependency matrices, Second, a top-down sweep detects activity everywhere under rootUnits.

Parameters

rootUnits – The list of topmost Units that must be analyzed.

runAnalysis¶

public static void runAnalysis(CallGraph callGraph, TapList<DiffRoot> diffRoots, int diffKind)¶: Main trigger method. Runs activity analysis analysis under the rootUnits.

saveFrontierActivity¶

public static TapPair<TapList<BoolVector>, TapList<BoolVector>> saveFrontierActivity(TapList<FGArrow> entryArrows, TapList<FGArrow> exitArrows, ActivityPattern curActivity)¶

Returns: the activity info on the entry arrows plus the usefulness info on the exit arrows.

setAnnotatedActive¶

public static void setAnnotatedActive(ActivityPattern pattern, Tree tree)¶: Sets the annotation that tells that this subtree is active.

setCurBlockEtc¶

protected void setCurBlockEtc(Block block)¶: Set curBlock, curSymbolTable, nDZ. In addition, sets nDRZ and the 3rd size of curBlockMap.

setCurUnitEtc¶

public void setCurUnitEtc(Unit unit)¶: Set curUnit. In addition, sets nDRZ, and the contents of curBlockMap.

setEmptyCumulAndCycleValues¶

protected void setEmptyCumulAndCycleValues()¶: Empty the infoTmp and infoTmpCycle that are used to propagate variedness upwards and usefulness downwards.

setOnceActiveZonesAndAnnotateDiffDeclsAndTypes¶

protected static void setOnceActiveZonesAndAnnotateDiffDeclsAndTypes(BoolVector activeZones, SymbolTable symbolTable, int kind, int thisKindNDZ)¶: For every zone for which the info in “activeZones” is true, (knowing that “activeZones” is a vector on zone ranks of kind “kind”), marks this zone as “active” (i.e. active at least once). Also finds the VariableDecl that corresponds to this zone and annotates it as “differentiated” (i.e. there will be a diff VariableDecl). Also, if this VariableDecl uses a structured type, declares the corresponding parts of this type as “differentiated” too, which is necessary to build the correct final differentiated type.

setPhaseUseful¶

public void setPhaseUseful(BoolVector usefulExits, BlockStorage<TapList<BoolVector>> curUnitUsefulnesses)¶: Prepares for the next analyzeBackward() to run only a “USEFUL” analysis and only on a sub-flow-graph of the current Unit.

setPhaseVaried¶

public void setPhaseVaried(BoolVector variedEntries, BlockStorage<TapList<BoolVector>> curUnitVariednesses)¶: Prepares for the next analyzeForward() to run only a “VARIED” analysis and only on a sub-flow-graph of the current Unit.

terminateCGForUnit¶

protected void terminateCGForUnit()¶: Set the activity annotations on the trees of Unit “curUnit”. This is done after all sweeps on the call graph are completed, therefore this is done only once.

terminateFGForBlock¶

protected void terminateFGForBlock()¶: Refines the propagated info (VARIED of USEFUL) for every interval between successive Instruction’s in curBlock. The result is built and stored into the global “curUnitInfos”, which is a BlockStorage of TapList’s of infos, with N+1 infos if curBlock has N Instruction’s.

terminateTermBlock¶

protected void terminateTermBlock()¶

terminateUnit¶

protected boolean terminateUnit()¶: Terminates analysis on the given curUnit. For the BOTTOMUP_1 phase, MUST return true iff the result has changed since previous time. For the TOPDOWN_2 phase, always returns false, but anyway this result is not used by top-down data-flow analyses.

unitIsContext¶

public boolean unitIsContext(ActivityPattern pattern)¶

Returns: true when the given Unit is in the outside “context” of the differentiated region.