DataFlowAnalyzer

public class DataFlowAnalyzer

Base class for data-flow analyses.

To define an actual data-flow analysis, build a derived class that overloads at least constructor DataFlowAnalyzer(CallGraph,String,TapList) and method run(TapList).

Whenever user-provided implementation uses a predefined utility methods “M” of the present class, one may need to overload recursively other utility methods as indicated in the documentation of “M”.

Fields

NOACT

protected static final int NOACT

Code for no “write” nor “read” action.

READ

protected static final int READ

Code for action “read”.

WRITE

protected static final int WRITE

Code for action “write”.

conservativeValue

protected boolean conservativeValue

The conservative info value for this analysis.

curActivity

protected ActivityPattern curActivity

The current ActivityPattern for which we analyze the current Unit.

curAnalysisName

protected String curAnalysisName

The name of the present analysis.

curArrow

protected FGArrow curArrow

The current Flow Graph arrow through which the analysis is propagating. One may assume that curArrow is available in defining the following methods (if one chooses to overload them):

curCallGraph

protected final CallGraph curCallGraph

The current CallGraph on which this analysis is currently run. One may assume that curCallGraph is available in any method of this class that one chooses to overload.

curCalledUnit

protected Unit curCalledUnit

When analyzing a call, the current called Unit. One must make sure that curCalledUnit is set to the correct value before using the utilities:

curInstruction

protected Instruction curInstruction

The current instruction on which analysis is run. One may assume that curInstruction is available in defining the following methods (if one chooses to overload them):

Also, one must make sure that curInstruction is set to the correct value before using the utilities:

inADeclaration

protected boolean inADeclaration

True when we are analyzing a tree which is inside a declaration. Useful to distinguish assignments from initializations.

nDZ

protected int nDZ

Total number of zones (i.e. Tapenade’s elementary chunks of memory) in the current Block.

topDownContexts

protected UnitStorage topDownContexts

Context for analyses that are top-down on the Call Graph.

tracedUnits

protected TapList<Unit> tracedUnits

Units for which we want to trace analysis “on the fly”.

uniqueAccessZones

protected BoolVector uniqueAccessZones

BoolVector of declared zones that have a special “unique” access in the current loop.

Constructors

DataFlowAnalyzer

protected DataFlowAnalyzer(CallGraph callGraph, String analysisName, TapList<String> traceAnalysisUnitNames)

Creation of a DataFlowAnalyzer.

Methods

accumulateValuesFromDownstream

protected boolean accumulateValuesFromDownstream()

Collects the data-flow information back from the downstream flow arrows of “curBlock”. @return true when the collecting returned a “non-empty” info, meaning that the backwards control flow really reaches this point. Special behavior for loop headers, distinguishing loop “entry”, “cycle”, and “exit”. One may overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable. If on the other hand, one decides not to overload and use the provided default, then one must consider overloading the methods:

accumulateValuesFromUpstream

protected boolean accumulateValuesFromUpstream()

Collects the data-flow information flow-wise from the incoming flow arrows of “curBlock”. Special behavior for loop headers, distinguishing loop “entry”, “cycle”, and “exit”. One may overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable. If on the other hand, one decides not to overload and use the provided default, then one must consider overloading the methods:

Returns

true when the collecting returned a “non-empty” info, meaning that the control flow really reaches this point.

analyze

protected boolean analyze()

Runs the present analysis on the curUnit. One may overload with one’s own implementation. Default implementation: analyzeForward(TapList,TapList,TapList) Overloading implementation may be or may contain analyzeForward(TapList,TapList,TapList) or analyzeBackward(TapList,TapList,TapList), in which case one must check their overloadable utilities. Globals provided: curCallGraph, curUnit.

Returns

For a bottom-up analysis, MUST return true IFF the analysis result has changed since the previous time (or if this is the first time). For a top-down analysis, this result may be anything.

analyzeBackward

public final boolean analyzeBackward(TapList<FGArrow> entryArrows, TapList<Block> insideBlocks, TapList<FGArrow> exitArrows)

Runs the present analysis, backward on the current Unit “curUnit”, or more precisely on the fraction of “curUnit” that is between “entryArrows” and “exitArrows”, which consists of the blocks “insideBlocks”. The three “entryArrows”, “insideBlocks” and “exitArrows” may be passed null, in which case the analysis is run on the full “curUnit”. As a result, this overwrites the results of this analysis on all Blocks in “insideBlock”, plus the info overwritten by initialization of the analysis on the destinations of the “exitArrows” and the info propagated as a result on the origins of the “entryArrows”. Globals required: curUnit. If this method is used, then one must consider overloading the methods:

Parameters

  • entryArrows – the Flow-Graph arrows at which the (backward) analysis will stop.

  • insideBlocks – all the Flow-Graph blocks that are on the way from entryArrows to exitArrows.

  • exitArrows – the Flow-Graph arrows from which the (backward) analysis will start.

Returns

true iff the analysis result is modified since last analysis.

analyzeForward

public final boolean analyzeForward(TapList<FGArrow> entryArrows, TapList<Block> insideBlocks, TapList<FGArrow> exitArrows)

Runs the present analysis, forward on the current Unit “curUnit”, or more precisely on the fraction of “curUnit” that is between “entryArrows” and “exitArrows”, which consists of the blocks “insideBlocks”. The three “entryArrows”, “insideBlocks” and “exitArrows” may be passed null, in which case the analysis is run on the full “curUnit”. As a result, this overwrites the results of this analysis on all Blocks in “insideBlock”, plus the info overwritten by initialization of the analysis on the origins of the “entryArrows” and the info propagated as a result on the destinations of the “exitArrows”. Globals required: curUnit. If this method is used, then one must consider overloading the methods:

Parameters

  • entryArrows – the Flow-Graph arrows from which the analysis will start.

  • insideBlocks – all the Flow-Graph blocks that are on the way from entryArrows to exitArrows.

  • exitArrows – the Flow-Graph arrows at which the analysis will stop.

Returns

true if the analysis result is modified since last analysis.

analyzeInBottomUp

protected boolean analyzeInBottomUp()

analyzeInTopDown

protected boolean analyzeInTopDown()

analyzeStatically

public final boolean analyzeStatically(TapList<Block> initBlocks, TapList<Block> insideBlocks)

Runs the present data-flow independent analysis on the current Unit “curUnit”. More precisely, runs only on the contents of the blocks “insideBlocks”. This means that the analysis can be run as a single sweep through each Instruction of “curUnit”, without any notion of data-flow order. For instance this can be used to propagate some data to each Unit recursively called by curUnit without modifying the data because of interpretation of curUnit.

Parameters

  • initBlocks – all the Flow-Graph blocks of curUnit for which a special initialization action must/will be made through a call to initializeFGForInitBlock()

  • insideBlocks – all the Flow-Graph blocks of curUnit that must be swept. If given null, the analysis will sweep through all Blocks of curUnit.

Returns

true iff the analysis result on curUnit is modified since last analysis call. This return value is used only in the context of a bottom-up analysis (runBottomUpAnalysis()) Otherwise this return value is ignored.

buildInfoBoolTreeOfDeclaredZones

public static TapList<?> buildInfoBoolTreeOfDeclaredZones(TapList<?> zonesTree, BoolVector info, TapIntList extraInfoZones, int whichKind, SymbolTable symbolTable)
Returns

a new (TapList) tree of Boolean’s, following the pattern of the given (TapList) tree of zones “zonesTree”, for which each TapIntList leaf becomes a Boolean which is true iff this TapIntList of extended declared zones intersects the given “info”+”extraInfoZones”.

buildInfoBoolTreeOfDeclaredZonesAll

public static TapList<?> buildInfoBoolTreeOfDeclaredZonesAll(TapList<?> zonesTree, BoolVector info, TapIntList extraInfoZones, int whichKind, SymbolTable symbolTable)

Same as buildInfoBoolTreeOfDeclaredZones, but places a True only if ALL the list of zones at this leaf are true for the given “info”+”extraInfoZones”.

buildInfoBoolTreeOfPointers

public static TapList buildInfoBoolTreeOfPointers(TapList zonesTree, SymbolTable symbolTable)
Returns

a new (TapList) tree of Boolean’s, following the pattern of the given (TapList) tree of zones “zonesTree”, in which a TapIntList leaf is true iff this zone is a pointer.

buildInfoPRZVTree

public final TapList buildInfoPRZVTree(TapList zonesTree, BoolMatrix matrix, int whichKind)
Parameters

  • zonesTree – The tree of extended declared zones for which the info is sought.

  • matrix – The matrix that contains the info.

  • whichKind – The kind that is used to number the row indices in “matrix”.

Returns

The resulting info as a tree of BoolVector’s

buildUnitPointerZoneMask

public static BoolVector buildUnitPointerZoneMask(Unit unit)

Builds a BoolVector with 1 only for the Unit’s zones of type “pointer” which point to a type which is differentiated.

changeKind

public static BoolVector changeKind(BoolVector oldInfo, int oldLength, int oldKind, int newLength, int newKind, SymbolTable symbolTable)

Convert a BoolVector containing an info on zones of kind “oldKind”. into the same info (or a subset depending on oldKind/newKind) on zones of kind “newKind”.

Returns

the converted info

collectZonesWrittenByExpression

public static void collectZonesWrittenByExpression(Tree expr, int act, BoolVector written, Instruction instr)

Accumulates into “written” the zones (possibly and/or partly) written by “expr”

commonNDZofFrontierArrows

public static int commonNDZofFrontierArrows(TapList<FGArrow> frontier, int kind)
Returns

the number of zones that flow through all arrows of the given “frontier”. It is the min of the number of zones that can flow through each arrow.

commonNDZofFrontierDestinations

public static int commonNDZofFrontierDestinations(TapList<FGArrow> frontier, int kind)
Returns

the number of common declared zones of all destinations of the given “frontier”.

commonNDZofFrontierOrigins

public static int commonNDZofFrontierOrigins(TapList<FGArrow> frontier, int kind)
Returns

the number of common declared zones of all origins of the given “frontier”.

compareChannelZoneDataDownstream

protected boolean compareChannelZoneDataDownstream(int mpZone, Block refBlock)

Compares the info for the Message-Passing channel zone “mpZone”, downstream curBlock compared with downstream “refBlock”. If curBlock’s is larger, accumulates it into refBlock’s and returns true. This default does nothing, complains, and returns false. Overload with one’s own choice.

compareChannelZoneDataUpstream

protected boolean compareChannelZoneDataUpstream(int mpZone, Block refBlock)

Compares the info for the Message-Passing channel zone “mpZone”, upstream curBlock compared with upstream “refBlock”. If curBlock’s is larger, accumulates it into refBlock’s and returns true. This default does nothing, complains, and returns false. Overload with one’s own choice.

compareDownstreamValues

protected boolean compareDownstreamValues()

Compares the current data-flow information with the info stored here (downstream current “curBlock”) upon previous sweep.

Returns

true when something has changed and therefore another Flow Graph sweep is probably necessary. Takes (should take) care of storing the new info when modified. This default does nothing and returns false. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable.

compareUpstreamChannelValuesWithInitial

protected boolean compareUpstreamChannelValuesWithInitial(TapList<Block> initBlocks)

Compares the current computed info about message-Passing channels, upstream the current Block “block” with the corresponding info upstream each Block in “initBlocks” (remember this is a backwards analysis!). If the current info is “larger”, accumulates it into the info downstream the “initBlocks” and returns true, meaning that the fixpoint iteration must restart. Otherwise returns false.

compareUpstreamValues

protected boolean compareUpstreamValues()

Compares the current data-flow information with the info stored here (upstream current “curBlock”) upon previous sweep.

Returns

true when something has changed and therefore another Flow Graph sweep is probably necessary. Takes (should take) care of storing the new info when modified. This default does nothing and returns false. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable.

compareWithStorage

protected boolean compareWithStorage(BoolVector newInfo, BoolVector newInfoCycle, int length, BlockStorage<BoolVector> storedInfos, BlockStorage<BoolVector> storedInfosCycle)

Utility that may be used in implementation of compare(Up/Down)streamValues() Compares BoolVector “newInfo” with the info stored for block in the BlockStorage<BoolVector> “storedInfos”. If there is a modification, replace the stored by the new. Does the same for the corresponding cycling infos. returns true iff either was replaced.

compareWithStorage

protected boolean compareWithStorage(BoolVector newInfo, BoolVector newInfoOnDiffPtr, BoolVector newInfoCycle, BoolVector newInfoCycleOnDiffPtr, int length, int lengthOnDiffPtr, BlockStorage<TapPair<BoolVector, BoolVector>> storedInfos, BlockStorage<TapPair<BoolVector, BoolVector>> storedInfosCycle)

Special case of compareWithStorage() for pairs of BoolVector’s, the first one for “normal” info, the second one for the info on differentiated pointers (OnDiffPtr). This primitive makes sense e.g. for DiffLiveness and TBR analyses.

Returns

true if the new info is different from the previous one. In that case, replaces the old info with the new.

containsExtendedDeclared

public static boolean containsExtendedDeclared(BoolVector info, int kind, TapIntList extendedDeclaredZones, TapIntList extraInfoZones, SymbolTable symbolTable, Unit calledUnit)
Returns

true when all zones in the given list of extended declared zones is either true in “info” or is part of the given “extraInfoZones”.

convertInfoFromUnitToUnit

public static BoolVector convertInfoFromUnitToUnit(BoolVector dataOnFromUnit, Unit fromUnit, Unit toUnit, int diffKind)

Converts a public info Boolvector, based on the external shape of fromUnit, into the equivalent public info Boolvector, but based on the external shape of toUnit.

cumulCycleValueWithAdditional

protected void cumulCycleValueWithAdditional(SymbolTable commonSymbolTable)

Accumulate the retrieved cycling data-flow value (through the cycling FGArrow curArrow) into the user-defined accumulator for cycling data-flow values. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curArrow, curBlock, curSymbolTable.

Parameters

  • commonSymbolTable – The SymbolTable which is common to the origin and the destination of curArrow.

cumulOr

protected static void cumulOr(TapList<?> boolVectorTree, BoolVector result, boolean followPointers)

Sweeps through the given “boolVectorTree”, which must be a tree of BoolVector’s. OR-accumulates all BoolVector leaves of this tree into BoolVector “result”.

Parameters

  • followPointers – when false, skips the parts of boolVectorTree that deal with pointers, i.e. that can only be accessed through a pointer deref.

cumulValueWithAdditional

protected void cumulValueWithAdditional(SymbolTable commonSymbolTable)

Accumulate the retrieved data-flow value (through the FGArrow curArrow) into the user-defined accumulator. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curArrow, curBlock, curSymbolTable.

Parameters

  • commonSymbolTable – The SymbolTable which is common to the origin and the destination of curArrow.

declaredZonesNotFromEntryToExit

public final TapIntList declaredZonesNotFromEntryToExit(HeaderBlock header, int whichKind)
Returns

the TapIntList of all declared zones of the “whichKind” kind that cannot travel directly from the entry to the exit of the cycle headed by this “header”. This is an alternative to using directEntryExitMask().

directEntryExitMask

protected final BoolVector directEntryExitMask(HeaderBlock header, int vectorLength, int whichKind)
Returns

the mask of all zones whose info must be propagated from (or to) the upstream non-cycling entry of this header to (or from) the downstream non-cycling exit of this header. This is true for all zones if the loop may cycle 0 times, else this is true for array zones that 1) have been treated as unique cells inside the loop, 2) and will not be unique cells outside the loop, 3) and are not totally accessed inside the loop. (cf bug in F77:lh05 with this refined version of activity)

eraseInfoOnTopLevel

public static void eraseInfoOnTopLevel(TapList<?> zonesTree)

Removes the info that concern parts of an argument that are passed by value.

eraseInfoOnTopLevel

public static void eraseInfoOnTopLevel(TapList zonesTree, Object replacementValue)

Removes the info that concern parts of an argument that are passed by value, and replaces the removed values with the given “replacementValue”.

filterByValue

public static BoolMatrix filterByValue(BoolMatrix publicDeps, int diffKind, Unit unit)

Returns the deps as seen by the caller side, i.e. by-value arguments are seen as unchanged.

getCalledUnit

public static Unit getCalledUnit(Tree expression, SymbolTable symbolTable)

When “expression” is a procedure or function call, returns the Unit of the called procedure.

getCalledUnits

public static TapList<Unit> getCalledUnits(Tree expression)

If called after PointerAnalyzer was run, returns the precomputed list of the Units called by “expression” (which is an op_call). There may be more than one unit e.g. in case of overloading or when using function pointers.

getValueFlowingBack

protected boolean getValueFlowingBack()

Retrieve the data-flow value that flows backwards through “curArrow”. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curArrow, curBlock, curSymbolTable.

Returns

Must return true iff the control flow may reach curArrow

getValueFlowingThrough

protected boolean getValueFlowingThrough()

Retrieve the data-flow value that flows forwards through “curArrow”. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curArrow, curBlock, curSymbolTable.

Returns

Must return true iff the control flow may reach curArrow

includePointedElementsInTree

public void includePointedElementsInTree(TapList zonesTree, ToBool total, BoolMatrix pointerDests, boolean recursive, boolean isCalled, boolean upstream)

Extends a given tree of zones with the destination of pointers. Globals required: curInstruction, curSymbolTable, curCalledUnit

Parameters

  • zonesTree – The tree of zones to be extended.

  • total – When passed a non-null ToBool, it is set to false if some pointed zone was included.

  • pointerDests – The pointer dests matrix. It is unnecessary after PointerAnalyzer has run, because the needed info is then stored at the level of the curBlock and curInstruction.

  • recursive – if true, recursively call across pointers.

  • isCalled – is true when we are on a function call and therefore the zonesTree may contain zones of rank greater than the last declared zone and these extra zones represent the formal parameters of the current call. If isCalled is false, then the extra zones represent split variables.

  • upstream – when true, the pointer destination info is retrieved upstream of the curInstruction, otherwise the info downstream is used.

includePointedElementsInTree

public static void includePointedElementsInTree(TapList zonesTree, ToBool total, BoolMatrix pointerDests, boolean recursive, SymbolTable symbolTable, Instruction instruction, boolean isCalled, boolean upstream)

Static version of includePointedElementsInTree().

infoToString

public final String infoToString(BoolVector info, int infoLen, int kind)
Returns

a String that shows the given data-flow info, given its length and kind, and prefixing it with the key to the meaning of the zone numbers in the dump file.

infoToString

public static String infoToString(BoolVector info, int infoLen, int kind, Unit unit, SymbolTable symbolTable)

Static version of infoToString().

infoToStringWithDiffPtr

protected final String infoToStringWithDiffPtr(BoolVector info, int infoLen, BoolVector infoOnDiffPtr, int infoLenOnDiffPtr)
Returns

a string that shows the given data-flow info, which is made of two parts, one on the original (ALLKIND) zones, the other on the future derivatives of pointer (PTRKIND) zones.

infoToStringWithDiffPtr

public static String infoToStringWithDiffPtr(BoolVector info, int infoLen, BoolVector infoOnDiffPtr, int infoLenOnDiffPtr, Unit unit, SymbolTable symbolTable)

Static version of infoToStringWithDiffPtr().

infoToStringWithDiffPtrWithCycle

protected final String infoToStringWithDiffPtrWithCycle(BoolVector info, int infoLen, BoolVector infoOnDiffPtr, int infoLenOnDiffPtr, BoolVector infoCycle, BoolVector infoCycleOnDiffPtr)
Returns

a string that shows the given data-flow info, which is made of four parts: the first on the original (ALLKIND) zones, the second on the future derivatives of pointer (PTRKIND) zones, and the third and fourth are the same for the “cycling” info i.e. the special, more accurate, info that is propagated through the cycles of an enclosing clean DO-loop.

initializeCGForRootUnit

protected void initializeCGForRootUnit()

If necessary, implement here whatever must be done for initialization of the analysis’ root Unit “rootUnit” after initialization of all units but before the analysis starts. This is needed only for a top-down analysis. This default does nothing. Overload with one’s own choice.

initializeCGForUnit

protected Object initializeCGForUnit()

Initializations before the sweeps on the Call Graph. This must make all initializations related to “unit”. For a top-down analysis, this MUST return an Object, which will be used as the initial value of the top-down context. For a bottom-up analysis, this method must return something but nobody cares for its value, so please return null! This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit.

initializeCumulValue

protected void initializeCumulValue()

Create an empty info to propagate it upwards. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable.

initializeFGForBlock

protected void initializeFGForBlock()

If necessary, initializations for “curBlock” done just before the analysis of the “curUnit” (which contains “curBlock”). This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable.

initializeFGForInitBlock

protected void initializeFGForInitBlock()

Initializations on the “curBlock”, which is an initial entry block, before the sweeps on curUnit. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable.

initializeFGForUnit

protected void initializeFGForUnit()

Initializations before the sweeps on the Flow Graph of “unit”. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit.

intersectsExtendedDeclared

public static boolean intersectsExtendedDeclared(BoolVector info, int kind, Tree expression, ToBool total, Instruction instruction, TapIntList extraInfoZones, SymbolTable symbolTable)
Returns

true when one of the zones of the value of “expression” is either an extra “tmp” zone, that appears in the given list of “extraInfoZones” that are assumed to have the property, or it is of the required “kind” and there is a 1 in BoolVector “info” at the index that corresponds to this zone. Fills “total” when provided non null.

intersectsExtendedDeclared

public static boolean intersectsExtendedDeclared(BoolVector info, int kind, TapIntList extendedDeclaredZones, TapIntList extraInfoZones, SymbolTable symbolTable)
Returns

true when “info” contains true for at least one zone in the given TapIntList of extended declared zones or for an extra tmp zone that is in “extraInfoZones”.

intersectsKindZoneRks

public static boolean intersectsKindZoneRks(BoolVector info, int infoKind, TapIntList zoneRks, TapIntList extraInfoZones, SymbolTable symbolTable)

intersectsZoneRks

public static boolean intersectsZoneRks(BoolVector info, TapIntList zoneRks, TapIntList extraInfoZones)

kindZoneRkToZoneRk

public static final int kindZoneRkToZoneRk(int zoneRk, int zoneKind, SymbolTable symbolTable)

Translates a zone rank “zoneRk” of kind “zoneKind”, into an ALLKIND zone rank.

Parameters

  • zoneRk – The given zone index.

  • zoneKind – The kind of the given zone, in {ALLKIND, REALKIND, PTRKIND}.

  • symbolTable – The current symbolTable.

Returns

the corresponding extended declared zone rank.

loopRunsAtLeastOnce

public final boolean loopRunsAtLeastOnce(HeaderBlock block)

True if this loop is guaranteed to run at least once.

mapZoneRkToKindZoneRk

public final TapIntList mapZoneRkToKindZoneRk(TapIntList extendedRks, int zoneKind)

Translates a list of extended declared zone ranks into a list of corresponding BoolVector ranks, where the BoolVector is of kind “zoneKind”. Preserves the order. Globals required: curCallGraph, curSymbolTable

Parameters

  • extendedRks – The given list of extended declared zone ranks.

  • zoneKind – The kind (in {ALLKIND, REALKIND, PTRKIND}) used in the BoolVector.

Returns

The corresponding list of BoolVector ranks.

mapZoneRkToKindZoneRk

public static final TapIntList mapZoneRkToKindZoneRk(TapIntList extendedRks, int zoneKind, SymbolTable symbolTable)

Translates a list of extended declared zone ranks into a list of corresponding BoolVector ranks, where the BoolVector is of kind “zoneKind”. Preserves the order. Static version.

Parameters

  • extendedRks – The given list of extended declared zone ranks.

  • zoneKind – The kind (in {ALLKIND, REALKIND, PTRKIND}) used in the BoolVector.

  • symbolTable – The current symbolTable.

Returns

The corresponding list of BoolVector ranks.

mapZoneRkToZoneInfo

public static TapList<ZoneInfo> mapZoneRkToZoneInfo(TapIntList extendedRks, SymbolTable symbolTable)

Translates a list of extended declared zone ranks into a list of corresponding ZoneInfo’s,

Parameters

  • extendedRks – the given list of extended declared zone ranks

  • symbolTable – The current symbolTable.

Returns

the corresponding list of ZoneInfo’s.

mayPointToRelocated

public static boolean mayPointToRelocated(Tree expression, boolean onDiff, Instruction instruction, SymbolTable symbolTable, boolean inJointDiffCode)
Returns

true when one of the possible destinations of the given pointer “expression” may have been reallocated to a different memory address between the forward and backward sweep of this expression’s location.

modifyAccessTreeForUniqueAccess

public static Tree modifyAccessTreeForUniqueAccess(int declaredIndex, Tree accessTree, Block block)

When this index “declaredIndex” in this block “block” has been detected as a “unique-access” zone, i.e. a zone which is accessed always for the same unique single cell during the enclosing loop, then the typical accessTree must be the access tree for this cell only (cf F77:lh09).

Returns

this new typical accessTree. Otherwise returns the old “accessTree”.

namesOfZones

public static String namesOfZones(BoolVector selectedZones, int whichKind, Unit unit)
Returns

a String with the names of all variables for which “selectedZones” is true.

oneZoneIsMultiple

public boolean oneZoneIsMultiple(TapIntList zonesList)
Returns

true if one of the zones in “zonesList” (TapIntList list of extended declared ranks) is actually labelled as multiple → in that case, an access to these zones can’t be total.

orInfoPRZVTrees

public static void orInfoPRZVTrees(BoolVector info, TapList<?> infoTree)

OR-Accumulates the given BoolVector “info” into each BoolVector leaf of “infoTree”.

propagateCallSiteDataToActualArgs

public static TapList[] propagateCallSiteDataToActualArgs(BoolVector privateData, Tree actualResultTree, Tree[] actualParamTreeS, TapList actualResultData, int nbDiffZ, TapIntList tmpZones, Instruction instruction, CallArrow arrow, boolean valuesCarryInfo, int whichKind)

Propagates a private info on the caller’s side onto the actual parameters of the call. The given private info “privateData” is propagated into the data trees for the call actual arguments. Info totally propagated onto an actual argument is removed from the “privateData”, which is therefore modified ! Similarly, info concerning the “actualResultTree” is propagated into the data tree for the result “actualResultData”, and removed from “privateData” when total.

Parameters

  • privateData – The given private info in the caller, nearby the call.

  • actualResultTree – The expression Tree that receives the actual call result, if any. null otherwise.

  • actualParamTreeS – The expression trees of the actual arguments of the call.

  • actualResultData – The tree of Boolean of the info on the actual result (output). Must be given non-null if actualResultTree is non-null.

  • nbDiffZ – The number of diffKind Zones

  • tmpZones – the list of extra zones introduced by splitting. Their info is considered True.

  • instruction – The Instruction of the current procedure call.

  • arrow – The current CallArrow from the current Instruction to the called Unit (useless?).

  • valuesCarryInfo – Not sure if necessary ?

  • whichKind – The kind of the info as stored in the privateData.

Returns

The tree of Boolean of the info on each actual argument (output).

propagateValuesBackwardThroughBlock

protected boolean propagateValuesBackwardThroughBlock()

Propagates the data-flow information backwards through “curBlock”. This default does propagation through each instruction. One may overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable. If on the other hand, one decides not to overload and use the provided default, then one must consider overloading the method:

Returns

false when the control flow cannot go through (e.g. exit()).

propagateValuesBackwardThroughExpression

protected boolean propagateValuesBackwardThroughExpression()

Propagates the data-flow information backwards through expression “tree”. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable, curInstruction.

Returns

false when the control flow cannot go through (e.g. exit()).

propagateValuesForwardThroughBlock

protected boolean propagateValuesForwardThroughBlock()

Propagates the data-flow information forwards through “curBlock”. This default does propagation through each instruction. One may overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable. If on the other hand, one decides not to overload and use the provided default, then one must consider overloading the method:

Returns

false when the control flow cannot go through (e.g. exit()).

propagateValuesForwardThroughExpression

protected boolean propagateValuesForwardThroughExpression()

Propagates the data-flow information forwards through the tree inside the curInstruction. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable, curInstruction.

Returns

false when the control flow cannot go through (e.g. exit()).

propagateValuesStaticallyThroughBlock

protected void propagateValuesStaticallyThroughBlock()

Propagates the data-flow information statically through “curBlock”.

propagateValuesStaticallyThroughExpression

protected void propagateValuesStaticallyThroughExpression()

Propagates the data-flow information statically to the tree inside the curInstruction. Default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable, curInstruction.

referenceIsTotal

public boolean referenceIsTotal(boolean totalRef, TapList zonesTree)
Parameters

  • totalRef – true when the Tree of the reference is actually total, i.e. is not an array index

  • zonesTree – the tree of zones of the reference. Globals required: curInstruction, uniqueAccessZones

Returns

true when the reference that has the given “totalRef” and the given “zonesList” may be considered total in the current data-flow analysis. The answer depends of the “curInstruction“‘s where mask and of the current “uniqueAccessZones”.

resetSweeps

public void resetSweeps()

run

protected void run(TapList<Unit> rootUnits)

Runs the present analysis, possibly limited to the part of the CallGraph which is under the given “rootUnits”, or on the whole CallGraph if “rootUnits” is null. One may overload with one’s own implementation. Default implementation: runBottomUpAnalysis(TapList) Overloading implementation may be or may contain runTopDownAnalysis(TapList) or runBottomUpAnalysis(TapList), in which case one must check their overloadable utilities. Globals provided: curCallGraph.

Parameters

  • rootUnits – The list of all Units recursively under the differentiation root, ordered top-down.

runBottomUpAnalysis

protected final void runBottomUpAnalysis(TapList<Unit> rootUnits)

Runs the present analysis, bottom-up on the current CallGraph, up to and including the root Units in “rootUnits”, or up to the top of the CallGraph if “rootUnits” is null. If this method is used, then one must consider overloading the methods:

Parameters

  • rootUnits – The list of all Units recursively under the differentiation root, ordered top-down.

runBottomUpTopDownAnalysis

protected final void runBottomUpTopDownAnalysis(TapList<Unit> rootUnits)

Runs the present analysis, mixing bottom-up and top-down. After each time a Unit is analyzed, it may decide that the callers and/or the callees of this Unit must be (re-)analyzed. Priority is given to re-analysis of callers, i.e. to the bottom-up sweep.

runSpecialCycleAnalysis

public static boolean runSpecialCycleAnalysis(Block block)

True if one may run the analysis in a special way that is able to detect full access to arrays, instead of considering all properties on arrays as undecidable.

runStatically

protected final void runStatically()

runTopDownAnalysis

protected final void runTopDownAnalysis(TapList<Unit> rootUnits)

Runs the present analysis, top-down on the current CallGraph, starting at and including the root Units in “rootUnits”, or at the top Units of the CallGraph if “rootUnits” is null. If this method is used, then one must consider overloading the methods:

Parameters

  • rootUnits – The list of all Units recursively under the differentiation root, ordered top-down.

setCurBlockEtc

protected void setCurBlockEtc(Block block)

Set curBlock, curSymbolTable, nDZ. One may overload with one’s own choice, but it must call super.setCurBlockEtc(block). Globals provided: curCallGraph, curUnit.

Parameters

  • block – The new current Block.

setCurUnitEtc

public void setCurUnitEtc(Unit unit)

Set curUnit. Also set the relatedUnit in tapEnv (but [llh 8/8/14 TODO] doesn’t reset it to null!! ). One may overload with one’s own choice, but it must call super.setCurUnitEtc(unit). Globals provided: curCallGraph.

Parameters

  • unit – The new current Unit.

setEmptyCumulAndCycleValues

protected void setEmptyCumulAndCycleValues()

Reinitialize the user-defined accumulators in which cumulValueWithAdditional() and cumulCycleValueWithAdditional() will accumulate the data-flow values before analyzing a Block. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable.

setInfoBoolTreeToExtendedDeclaredZones

public final void setInfoBoolTreeToExtendedDeclaredZones(BoolVector infos, TapList zonesTree, boolean newVal, TapList mask, boolean totalSet, int whichKind)

Updates the BoolVector “infos”, which holds some information on private “whichKind” zones, by setting to “newVal” the info of the zones in “zonesTree” that pass through the “mask”. When non-null, “mask” indicates the parts of zonesTree that must be considered. At each leaf in “zonesTree” that passes through the “mask”, the setting to “newVal” is done according to the boolean “totalSet” and to the global “conservativeValue” for the current data-flow analysis, as defined in method conservativeSetExtendedDeclared(). Globals required: curSymbolTable

setInfoBoolTreeToExtendedDeclaredZones

public final void setInfoBoolTreeToExtendedDeclaredZones(BoolVector infos, TapList zonesTree, TapList boolsTree, TapList mask, boolean totalSet, int whichKind)

Updates the BoolVector “infos”, which holds some information on private “whichKind” zones, with the additional tree of infos given in “boolsTree”. The tree “boolsTree” is the tree of infos for a given expression, for which the corresponding tree of declared zones is the given “zonesTree”. When non-null, “mask” indicates the parts of zonesTree/boolsTree that must be considered. This method recursively traverses “zonesTree”, “mask”, and “boolsTree” in parallel, and when it reaches leaves and the mask allows for it, it sets into “infos” at the current zones (“zonesTree”) the boolean info found in “boolsTree”. This setting varies according to the boolean “totalSet” and to the global “conservativeValue” for the current data-flow analysis, as defined in method conservativeSetExtendedDeclared(). Globals required: curSymbolTable

setInfoPRZVTree

public final void setInfoPRZVTree(BoolMatrix matrix, TapList zonesTree, TapList przvsTree, TapList mask, boolean totalSet, int whichKind)

Adds into “matrix” that “zonesTree” receives info “przvsTree”, i.e. schematically that ” zonesTree := przvsTree ; ” Assumes that zonesTree and przvsTree are two matching trees (if they don’t match, does some union-merge of subtrees, to make the two trees match anyway) For each pair of corresponding leaves of the two trees, one leaf is a TapIntList of extended declared zones designating rows in the “matrix”, the other leaf is a BoolVector. Sets these rows in “matrix” to this BoolVector, observing the whichKind.

setKindZoneRk

public final void setKindZoneRk(BoolVector info, int infoKind, int zoneRk, boolean value)

setKindZoneRk

public static final void setKindZoneRk(BoolVector info, int infoKind, int zoneRk, boolean value, SymbolTable symbolTable)

setKindZoneRks

public void setKindZoneRks(BoolVector info, int infoKind, TapIntList zoneRks, boolean value)

setKindZoneRks

public static void setKindZoneRks(BoolVector info, int infoKind, TapIntList zoneRks, boolean value, SymbolTable symbolTable)

setRefValue

public void setRefValue(Tree refTree, int kind, BoolVector info, boolean value, boolean followPointers)

Sets the info to “value” for all “kind” zones of reference expression “refTree”. When followPointers is true, does it also for the zones pointed by the pointers in refTree. Globals required: curInstruction, curSymbolTable

setTopDownContext

protected void setTopDownContext(Unit unit, Object context)

Set context for analyses that are top-down on the Call Graph.

Parameters

  • unit – current Unit.

  • context – context Object.

setUniqueAccessZones

public void setUniqueAccessZones(Block block)

Fills the global BoolVector “uniqueAccessZones” with the zones that are accessed during the enclosing loop iteration as unique cells: these accesses will be temporarily marked “total”.

setZoneRks

public static void setZoneRks(BoolVector info, TapIntList zoneRks, boolean value)

sweeps

public int sweeps()

terminateCGForUnit

protected void terminateCGForUnit()

If necessary, runs some concluding analysis on Unit “unit” after the present analysis is completed on the Call Graph. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit.

terminateFGForBlock

protected void terminateFGForBlock()

If necessary, termination operations on an inside block “curBlock” after the sweeps on a unit. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable.

terminateFGForTermBlock

protected void terminateFGForTermBlock()

If necessary, termination operations on a termination block “curBlock” after the sweeps on a unit. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit, curBlock, curSymbolTable.

terminateFGForUnit

protected boolean terminateFGForUnit()

Termination operations at the end of the Flow Graph analysis of the given Unit “curUnit”. In the case of a bottom-up analysis, must build the analysis result on the current “curUnit”, which is deduced from the values stored at the entry of the exit Block, depending on the direction. For a bottom-up analysis, this method MUST return true IFF the analysis result has changed since the previous time (or if this is the first time). For a top-down analysis, this method must return a boolean value but nobody cares for it. This default does nothing. Overload with one’s own choice. Globals provided: curCallGraph, curUnit

topDownContext

protected Object topDownContext(Unit unit)

Context for analyses that are top-down on the Call Graph.

Parameters

  • unit – current Unit.

Returns

context for analyses that are top-down on the Call Graph.

traceDisplayPrivateZones

protected static final void traceDisplayPrivateZones(Unit unit, int nZ, int kind)

Displays into the trace the list of the “nZ” zones of kind “kind” in “unit”.

translateCallSiteDataToCallee

public static BoolVector translateCallSiteDataToCallee(BoolVector callSiteData, TapList[] callSiteParamDataS, Tree actualResultTree, Tree[] actualParamTreeS, boolean onEntry, Tree callTree, Instruction callInstruction, CallArrow callArrow, int whichKind)

Propagates a boolean data-flow info callSiteData, which applies in some calling procedure immediately before/after a call site (i.e. a call to some callee procedure), to the same info translated to apply at the entry/exit of the callee. In order to deal with the call arguments, either param callSiteParamDataS is passed non-null and it is assumed to contain the TapList-tree of the data-flow info for each actual argument (and for the actual result at index 0) before/after the call site, or callSiteParamDataS is passed null (or some element of it is null for some index) and then params actualResultTree and actualParamTreeS must be passed non-null, and are used to retrieve the part of the data-flow that concerns the formal parameters by looking up in callSiteData for what concerns the actual arguments.

Parameters

  • callSiteData – the given data-flow info, expressed in terms of the zones that exist at the call site. This method does not modify it.

  • callSiteParamDataS – the given data-flow info about the actual parameters of the call. If passed null or some index is null, then the corresponding actualResultTree or element of actualParamTreeS should be passed non-null. Value at index 0 is about the actual result of the call, and it is used only when onEntry==false, otherwise may be null

  • actualResultTree – The tree of the (actual) result. Needed only for a function and when callSiteParamDataS is null or null at index 0. TODO: argument should disappear when precomputed actualResultTree is stored on the callTree.

  • actualParamTreeS – The trees of the actual arguments. Needed only when callSiteParamDataS is null or null at the corresponding index. TODO: argument should disappear when precomputed actualParamTreeS are stored on the callTree.

  • onEntry – if true, propagate the info from before the call, to the callee entry, else propagate the info from after the call, back to the callee exit.

  • callTree – the call tree (operator op_call)

  • callInstruction – the call instruction

  • callArrow – the call arrow from the calling procedure to the callee.

  • whichKind – the kind of zones on which the data-flow info is focused.

Returns

the corresponding data-flow info at the entry/exit, expressed in terms of the zones that exist at the root of the callee.

translateCallSiteDataToCallee

public static BoolVector translateCallSiteDataToCallee(BoolVector callSiteData, TapList[] callSiteParamDataS, Tree actualResultTree, Tree[] actualParamTreeS, boolean onEntry, Tree callTree, Instruction callInstruction, CallArrow callArrow, int whichKind, boolean propagateEvenByValue)

translateCallSiteDataToCallee

public static BoolMatrix translateCallSiteDataToCallee(BoolMatrix callSiteData, TapList[] callSiteParamDataS, Tree actualResultTree, Tree[] actualParamTreeS, boolean onEntry, Tree callTree, Instruction callInstruction, CallArrow callArrow, int whichKind)
Parameters

  • callSiteData – the call site data matrix. This method does not modify it, but some of its rows may be shared as rows of the result callee data matrix.

  • callSiteParamDataS – an array (for each argument, index 0 for result, i for argument i) of a tree of BoolVector’s containing the call site data for the result or arguments.

translateCalleeDataToCallSite

public static TapList<?> translateCalleeDataToCallSite(TapList<?> zonesTree, Unit calledUnit, TapList[] paramZones)

Propagates some data-flow information tree of zones, which applies at the exit of some callee procedure, to the place immediately after some call site to this procedure. Returns basically a copy of the given “zonesTree”, in which all leaves, which are TapIntList’s of declared zones ranks in the callee procedure, are replaced with TapIntList’s of declared zones ranks in the calling procedure context.

translateCalleeDataToCallSite

public static TapList[] translateCalleeDataToCallSite(BoolVector calleeData, BoolVector callSiteData, Tree actualResultTree, Tree[] actualParamTreeS, boolean onEntry, Tree callTree, Instruction instruction, CallArrow callArrow, int whichKind, BoolVector passesThroughCall, BoolVector passesAroundCall, boolean valuesCarryInfo, boolean onlyWhenTotal)

Propagates some data-flow information calleeData, which applies at the entry (resp. exit) of some called procedure (entry iff onEntry==true, otherwise exit), to the place immediately before (resp. after) some call site that calls this procedure, by accumulating this info into the given callSiteData. If actualResultTree is given non-null, then the info on the result’s zones is integrated into callSiteData. Similarly if actualParamTreeS is given non-null and actualParamTreeS[N-1] is non-null, the info on parameter N is integrated into callSiteData. Otherwise, the info on the result and formal params is returned (for the non-given actual result and actual params) into the returned array of TapList.

Parameters

  • calleeData – the given data, expressed in terms of the zones of the callee.

  • callSiteData – the data, shaped after the call site, that will accumulate the translation of the calleeData. It may be passed null in which case only arguments and result data are translated. Very often, it contains the data at the other end of the call site, e.g. before the call if onEntry==false.

  • actualResultTree – the variable receiving the call’s result at the call site. May be not given, i.e. null.

  • actualParamTreeS – the call site actual arguments. May be not given, i.e. null. Some elements may be not given, i.e. null.

  • onEntry – true when propagation goes from called unit entry back to immediately before the call site. Otherwise, it means that propagation goes from called unit exit forward to immediately after the call site.

  • callTree – the call tree at the call site.

  • instruction – the instruction which contains the call site. It is used to obtain the call site’s SymbolTable and pointer destination info.

  • arrow – the call arrow for this call site.

  • whichKind – the kind of zones on which the data-flow info is focused.

  • passesThroughCall – When given, the mask of zones of the call site whose data in callSiteData may be modified by this call. TODO: improve this code so that this mask is given following the zones of the callee

  • passesAroundCall – When given, the mask of zones of the call site whose data in callSiteData may pass untouched by this call. TODO: improve this code so that this mask is given following the zones of the callee

  • valuesCarryInfo – when false and parameters are passed by value, info on the parameter is not propagated (except through pointers).

  • onlyWhenTotal – when true, propagation is done through an argument only when this access to the actual argument is total. For instance onlyWhenTotal should be true when propagating a “killed” info, since a non-total actual argument will not be fully killed.

Returns

the list (indexed on [0,nbArgs]) of the data on the call’s actual arguments (with index 0 representing the function result), except when actualResultTree is given and all actualParamTreeS are given, in which case returns null.

translateCalleeDataToCallSite

public static TapList[] translateCalleeDataToCallSite(BoolMatrix calleeData, BoolMatrix callSiteData, Tree actualResultTree, Tree[] actualParamTreeS, boolean onEntry, Tree callTree, Instruction instruction, CallArrow callArrow, int whichKind, BoolVector passesThroughCall, BoolVector passesAroundCall, boolean valuesCarryInfo, BoolVector calleeMask)
Parameters

  • calleeMask – a mask on the zones of the callee. All info outside this mask is not propagated. Used in ReqExplicit. TODO: rationalize this with passesThroughCall, which may be the same info expressed on the call site zones?.

translateCalleeDataToCallSite2

public static TapIntList translateCalleeDataToCallSite2(TapIntList calleeZones, Unit calledUnit, TapList[] paramZones)

Propagates some list of extended declared ranks that refer to the exit context of some procedure, into a list of corresponding extended declared ranks, in the context immediately after some call site to this procedure.

zoneIsPointer

public static boolean zoneIsPointer(int zoneRk, SymbolTable symbolTable, Unit calledUnit)

zoneIsPointer

public final boolean zoneIsPointer(int zoneRk)
Parameters

  • zoneRk – the given extended declared ALLKIND zone rank.

Returns

true if “zoneRk” is for a pointer.

zoneIsScalar

public final boolean zoneIsScalar(int zoneRk)
Parameters

  • zoneRk – the given extended declared ALLKIND zone rank.

Returns

true if “zoneRk” is for a scalar variable.

zoneRkToKindZoneRk

public final int zoneRkToKindZoneRk(int extendedRk, int zoneKind)

Translates an extended declared zone rank into the corresponding BoolVector rank, where the BoolVector is of kind “zoneKind”. Globals required: curCallGraph, curSymbolTable

Parameters

  • extendedRk – The given extended declared zone rank.

  • zoneKind – The kind (in {ALLKIND, REALKIND, PTRKIND}) used in the BoolVector.

Returns

The corresponding BoolVector rank.

zoneRkToKindZoneRk

public static final int zoneRkToKindZoneRk(int extendedRk, int zoneKind, SymbolTable symbolTable)

Translates an extended declared zone rank into the corresponding BoolVector rank, where the BoolVector is of kind “zoneKind”. Static version.

Parameters

  • extendedRk – The given extended declared zone rank.

  • zoneKind – The kind (in {ALLKIND, REALKIND, PTRKIND}) used in the BoolVector.

  • symbolTable – The current symbolTable.

Returns

The corresponding BoolVector rank.