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.

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:

curSymbolTable

protected SymbolTable curSymbolTable

The SymbolTable of the currently analyzed Block. One may assume that curSymbolTable is available in defining the following methods (if one chooses to overload them):

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

filterByValue

public boolean filterByValue

Not very clean global flag to force propagateExitDataBwdToCallee() to skip the filtering of by-value arguments

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

number of declared-zones.

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.

addZeroIndexTEMPORARY

public static TapList[] addZeroIndexTEMPORARY(TapList[] array)

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 anlaysis 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 initializeInitBlock()

  • 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, int[] vectorMap, 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, int[] vectorMap, 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, int[] ptrVectorMap, 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.

buildInfoPRZVTreeOfExtendedDeclared

public final TapList buildInfoPRZVTreeOfExtendedDeclared(TapList zonesTree, BoolMatrix matrix, int whichKind, int[] rowMap)
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”.

  • rowMap – The map of the rows of “matrix”, i.e. the map of the row indices.

Returns

The resulting info as a tree of BoolVector’s

buildPublicPointerZoneMask

public static BoolVector buildPublicPointerZoneMask(Unit unit)

Builds a BoolVector with 1 only for public zones of type “pointer” which point to a type which is differentiated.

changeCommonDeclared

protected static int[] changeCommonDeclared(int[] map3, int newNDZ)

Builds a new map with a new number of declared zones.

changeKind

public static BoolVector changeKind(BoolVector oldInfo, int[] oldMap, int oldKind, int[] newMap, 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.

For future dataflow analysis.

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[] vectorMap, 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”.

convertPublicInfoFromUnitToUnit

public static BoolVector convertPublicInfoFromUnitToUnit(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.

dataOfParamElemOLD

public static boolean dataOfParamElemOLD(BoolVector calleeData, int paramElemIndex, int whichKind, Unit callee)

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[] vectorMap, 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)

extendedDeclaredToClass

public final int extendedDeclaredToClass(int extendedRk)
Parameters

  • extendedRk – the given extended declared zone rank

Returns

the corresponding class.

extendedDeclaredToClass

public static int extendedDeclaredToClass(int extendedRk, SymbolTable symbolTable)
Parameters

  • extendedRk – the given extended declared zone rank

  • symbolTable – The current symbolTable.

Returns

the corresponding class.

extendedDeclaredToPublicRanks

public static TapIntList extendedDeclaredToPublicRanks(TapIntList extendedRks, SymbolTable symbolTable)

Translates a list of extended declared zone ranks into the corresponding public ranks of the current unit. Correspondence is not one-to-one in general, therefore the returned TapIntList may be of different length or even empty if all given extendedRks stand for local variables inexistent at the current Unit level. TODO: this implementation is INEFFICIENT: we really miss a direct link from private zones to public zones! Static version. Needs the current SymbolTable (original, not differentiated).

For future dataflow analysis.

Parameters

  • extendedRks – the given list of extended declared zone ranks

  • symbolTable – The current symbolTable.

Returns

the list of ranks of the corresponding public zones.

extendedDeclaredToVectorIndex

public final int extendedDeclaredToVectorIndex(int extendedRk, int zoneKind, int[] vectorMap)

Translates an extended declared zone rank into the corresponding BoolVector rank, where arrangement of the BoolVector is given by its “vectorMap” and kind “zoneKind”. Globals required: curUnit, curCalledUnit, curSymbolTable

Parameters

  • extendedRk – The given extended declared zone rank.

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

  • vectorMap – The map of the BoolVector.

Returns

The corresponding BoolVector rank.

extendedDeclaredToVectorIndex

public static int extendedDeclaredToVectorIndex(int extendedRk, int zoneKind, int[] vectorMap, SymbolTable symbolTable, Unit calledUnit)

Translates an extended declared zone rank into the corresponding BoolVector rank, where the arrangement of the BoolVector is given by its “vectorMap” and the kind “zoneKind”. Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

  • extendedRk – The given extended declared zone rank.

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

  • vectorMap – The map of the BoolVector.

  • symbolTable – The current symbolTable.

  • calledUnit – When applicable, the Unit called by the present call statement.

Returns

The corresponding BoolVector rank.

extendedDeclaredToZoneInfo

public final ZoneInfo extendedDeclaredToZoneInfo(int extendedRk)

Translates an extended declared zone rank into its ZoneInfo. Globals required: curUnit, curCalledUnit, curSymbolTable

Parameters

  • extendedRk – the given extended declared zone rank

Returns

the corresponding ZoneInfo.

extendedDeclaredToZoneInfo

public static ZoneInfo extendedDeclaredToZoneInfo(int extendedRk, SymbolTable symbolTable, Unit calledUnit)

Translates an extended declared zone rank into its ZoneInfo. Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

  • extendedRk – the given extended declared zone rank

  • symbolTable – The current symbolTable.

  • calledUnit – The current called Unit, if any.

Returns

the corresponding ZoneInfo.

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.

getMapClass

public static int getMapClass(int globalRk, int[] zoneMap)
Parameters

  • globalRk – The global index in the zone map.

  • zoneMap – The given zone map.

Returns

The class of zoneMap that contains index globalRk.

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, Unit calledUnit, boolean isCalled, boolean upstream)

Static version of includePointedElementsInTree().

infoToString

public static String infoToString(BoolVector info, int[] infoMap, int kind, Unit unit, SymbolTable symbolTable)

Static version of infoToString().

infoToString

public final String infoToString(BoolVector info, int[] infoMap, int kind)
Returns

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

infoToStringWithDiffPtr

public static String infoToStringWithDiffPtr(BoolVector info, int[] infoMap, BoolVector infoOnDiffPtr, int[] infoMapOnDiffPtr, Unit unit, SymbolTable symbolTable)

Static version of infoToStringWithDiffPtr().

infoToStringWithDiffPtr

protected final String infoToStringWithDiffPtr(BoolVector info, int[] infoMap, BoolVector infoOnDiffPtr, int[] infoMapOnDiffPtr)
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.

infoToStringWithDiffPtrWithCycle

protected final String infoToStringWithDiffPtrWithCycle(BoolVector info, int[] infoMap, BoolVector infoOnDiffPtr, int[] infoMapOnDiffPtr, 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.

infoTreesOfRefArgs

public TapList[] infoTreesOfRefArgs(Tree[] actualParams, BoolVector info, int[] vectorMap, int whichKind)

Utility that builds the array of the trees of info for each of the given actual parameters tree. Globals required: curInstruction, curSymbolTable

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.

initializeInitBlock

protected void initializeInitBlock()

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.

initializeUnit

protected void initializeUnit()

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[] vectorMap, int kind, Tree expression, ToBool total, Instruction instruction, TapIntList extraInfoZones, SymbolTable symbolTable, Unit calledUnit)
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[] vectorMap, int kind, TapIntList extendedDeclaredZones, TapIntList extraInfoZones, SymbolTable symbolTable, Unit calledUnit)
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”.

loopRunsAtLeastOnce

public final boolean loopRunsAtLeastOnce(HeaderBlock block)

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

makeMap3

public static int[] makeMap3(int nb1, int nb2, int nb3)

Builds a map for 3 successive classes of zone indices.

Parameters

  • nb1 – the number of zones of the first class.

  • nb2 – the number of zones of the second class.

  • nb3 – the number of zones of the third class.

Returns

the map for these 3 classes.

makeMap3

public static int[] makeMap3(Unit unit, int zoneKind)

Shortcut to build the map of private zones for the calling context of “unit”.

Parameters

  • unit – The Unit of whom we want the map of the calling context.

  • zoneKind – The kind of zones for which we want to build the map.

Returns

the map of three classes.

makeMap3

public static int[] makeMap3(Unit unit, Block block, int zoneKind)

Shortcut to build the map of private zones for the given “block” of the given “unit”.

Parameters

  • unit – The Unit for whom we want the map

  • block – The Block of “unit” for whom we want the map.

  • zoneKind – The kind of zones for which we want to build the map.

makeMap3

public static int[] makeMap3(SymbolTable symbolTable, int zoneKind)

Shortcut to build the map of private zones for the given “symbolTable”.

makeMap4

public static int[] makeMap4(int nbSE, int nbNP, int nbD, int nbFP)

Builds a map for the rows or columns of a dests matrix, with four successive classes (side-effect ; null-pointers ; declared ; formal-params).

Parameters

  • nbSE – the number of side-effect zones.

  • nbNP – now useless (pass 0)

  • nbD – the number of declared zones.

  • nbFP – the number of formal parameters zones.

Returns

the map of four classes.

mapExtendedDeclaredToVectorIndex

public final TapIntList mapExtendedDeclaredToVectorIndex(TapIntList extendedRks, int zoneKind, int[] vectorMap)

Translates a list of extended declared zone ranks into a list of corresponding BoolVector ranks, where the arrangement of the BoolVector is given by its “vectorMap” and the kind “zoneKind”. Preserves the order. Globals required: curUnit, curCalledUnit, curSymbolTable

Parameters

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

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

  • vectorMap – The map of the BoolVector.

Returns

The corresponding list of BoolVector ranks.

mapExtendedDeclaredToVectorIndex

public static TapIntList mapExtendedDeclaredToVectorIndex(TapIntList extendedRks, int zoneKind, int[] vectorMap, SymbolTable symbolTable, Unit calledUnit)

Translates a list of extended declared zone ranks into a list of corresponding BoolVector ranks, where the arrangement of the BoolVector is given by its “vectorMap” and the kind “zoneKind”. Preserves the order. Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

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

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

  • vectorMap – The map of the BoolVector.

  • symbolTable – The current symbolTable.

  • calledUnit – When applicable, the Unit called by the present call statement.

Returns

The corresponding list of BoolVector ranks.

mapExtendedDeclaredToZoneInfo

public static TapList<ZoneInfo> mapExtendedDeclaredToZoneInfo(TapIntList extendedRks, SymbolTable symbolTable, Unit calledUnit)

Translates a list of extended declared zone ranks into a list of corresponding ZoneInfo’s, Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

  • extendedRks – the given list of extended declared zone ranks

  • symbolTable – The current symbolTable.

  • calledUnit – The current called Unit, if any.

Returns

the corresponding list of ZoneInfo’s.

mapSize

public static int mapSize(int[] map)
Parameters

  • map – the given map.

Returns

the number of zones in the given map.

mapZoneRkToPublicRk

public static TapIntList mapZoneRkToPublicRk(TapIntList zoneRks, int zoneKind, Unit calledUnit)

Translates a list of zone ranks “zoneRks”, of kind “zoneKind” into the list of corresponding public zone ranks, i.e. ranks in the external shape of their Unit “calledUnit”.

Parameters

  • zoneRks – The given list of zone indices.

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

  • calledUnit – The unit of which zoneRks are visible zones.

Returns

The public ranks for “zoneRks” in calledUnit.

mapZoneRkToVectorIndex

public final TapIntList mapZoneRkToVectorIndex(TapIntList zoneRks, int zoneClass, int zoneKind, int[] vectorMap)

Translates a list of zone rank “zoneRks”, all of kind “zoneKind” and class “zoneClass”, into the corresponding indices in a targetted ZoneVector or BoolMatrix, which must be of the same kind “zoneKind” and whose map is given in “vectorMap”. Preserves the order. Globals required: curCalledUnit

Parameters

  • zoneRks – The given list of zone ranks.

  • zoneClass – The class of the given zone, in {D_CLASS, FP_CLASS}.

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

  • vectorMap – The map of the classes used in the targetted vector.

Returns

The corresponding list of indices in the targetted ZoneVector or BoolMatrix row or column.

mapZoneRkToVectorIndex

public static TapIntList mapZoneRkToVectorIndex(TapIntList zoneRks, int zoneClass, int zoneKind, int[] vectorMap, Unit calledUnit)

Translates a list of zone rank “zoneRks”, all of kind “zoneKind” and class “zoneClass”, into the corresponding indices in a targetted ZoneVector or BoolMatrix, which must be of the same kind “zoneKind” and whose map is given in “vectorMap”. Preserves the order. Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

  • zoneRks – The given list of zone ranks.

  • zoneClass – The class of the given zone, in {D_CLASS, FP_CLASS}.

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

  • vectorMap – The map of the classes used in the targetted vector.

  • calledUnit – The current called Unit, if any.

Returns

The corresponding list of indices in the targetted ZoneVector or BoolMatrix row or column.

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).

For future dataflow analysis.

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, int[] vectorMap, Tree actualResultTree, Tree[] actualParamTreeS, TapList actualResultData, 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.

  • vectorMap – The map of “privateData”.

  • 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.

  • 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).

propagateCallSiteDataToCallee

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

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.

  • callSiteMap – the map of zones existing at the call site. May be passed null if passing null as actualResultTree and actualParamTreeS

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

  • propagateEvenByValue – when true, forces propagation of info upon call exit on top level of parameters, even in the call-by-value case. Most often passed “false”. Typically passed “true” for a backwards analysis (Usefulness, AvlX…) across call exit.

Returns

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

propagateCallSiteDataToCallee

public static BoolMatrix propagateCallSiteDataToCallee(BoolMatrix callSiteData, TapList[] callSiteParamDataS, Tree actualResultTree, Tree[] actualParamTreeS, boolean onEntry, Tree callTree, Instruction callInstruction, CallArrow callArrow, int[] callSiteMap, int whichKind, boolean propagateEvenByValue)
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.

propagateCalleeDataToCallSite

public static TapList[] propagateCalleeDataToCallSite(BoolVector calleeData, BoolVector callSiteData, Tree actualResultTree, Tree[] actualParamTreeS, boolean onEntry, Tree callTree, Instruction instruction, CallArrow arrow, int[] callSiteMap, 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 some 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.

  • arrow – the call arrow for this call site.

  • callSiteMap – the map of zones existing at the call site. May be passed null if passing null as actualResultTree and actualParamTreeS

  • 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.

propagateCalleeDataToCallSite

public static TapList[] propagateCalleeDataToCallSite(BoolMatrix calleeData, BoolMatrix callSiteData, Tree actualResultTree, Tree[] actualParamTreeS, boolean onEntry, Tree callTree, Instruction instruction, CallArrow arrow, int[] callSiteMap, 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?.

propagateDataToCallSite

public static BoolVector propagateDataToCallSite(BoolVector publicData, Tree actualResultTree, Tree[] actualParamTreeS, int[] vectorMap, Instruction instruction, CallArrow arrow, boolean cumulOr, boolean valuesCarryInfo, int whichKind)

Variant of propagateDataToCaller() (now renamed as propagateCalleeDataToCallSite()), for which the given publicData of the called routine is translated as private data at the caller site. The difference is about pointers and aliases: If the actual parameter (or indeed also a passed global) is a deref of a pointer p, then the info on the formal parameter is translated as an info on the caller’s zone for the “initial” *p. In other words whatever the call site *p actually points to, (e.g. to variable x, or to variables {x or y}) this translation doesn’t care, doesn’t attach the data on the zones of e.g. x or y, but instead it attaches the data on the zone for *p, i.e. the zone provided as default/initial destination of p. actualResultTree and actualParamTreeS must be given non-null.

propagateEntryDataFwdToCallee

public BoolVector propagateEntryDataFwdToCallee(BoolVector privateDataInTransit, int[] vectorMap, TapList[] actualParamDataS, BoolVector publicTouched, CallArrow arrow, Tree[] actualParamTreeS, int whichKind, boolean transit)

Same as propagateEntryDataFwdToCallee, for zone vectors instead of zone matrices. On one hand, returns the translation of the “privateDataInTransit” in the public zones of the called Unit. On the other hand, when “transit” is true, modifies “privateDataInTransit” so that it contains in the end only the part of its original value that may travel unmodified across this call. This is useful for a following “propagateExitDataFwdToCaller”. When “transit” is false, argument “privateDataInTransit” is not modified, and in this special case, arguments “publicTouched” and “actualParamTreeS” are not used and may be null. Globals required: curInstruction, curSymbolTable, curUnit, curCalledUnit.

propagateExitDataBwdToCallee

public BoolVector propagateExitDataBwdToCallee(BoolVector privateDataInTransit, int[] vectorMap, TapList resultData, TapIntList moreTrueZones, CallArrow arrow, Tree[] actualParamTreeS, int whichKind, boolean transit, BoolVector publicTouched, boolean diffMaybePassedByRef, boolean resetValue)

Propagates any data-flow info BoolVector “privateDataInTransit” which applies just downstream a call, plus the info “resultData” on the result, upstream the call boundary. On one hand, this returns the public data-flow info at the exit of the called unit, which is in the returned BoolVector. On the other hand, and only when “transit” is true, this modifies the given “privateDataInTransit” so that it contains only the part of it that may be propagated untouched backwards to the entry end of the call, because the corresponding variables are not passed or only partially passed to the called unit. If “transit” is true, this returned “privateDataInTransit” must be kept untouched until it is passed as the 2nd argument of the corresponding propagateEntryDataBwdToCaller(). Optional argument “moreTrueZones” contains zone numbers that are above the number of declared zones, and which are considered having the data-flow info “true”. When “diffMaybePassedByRef” is true, considers that parameters that are not overwritten as if they were passed by reference (cf comment below). When “transit” is true, argument “publicTouched” is used to further reduce the returned public data-flow info at the exit of the called unit. When “transit” is false, argument “privateDataInTransit” is not modified, and in this special case, argument “publicTouched” is not used and may be null. Globals required: curInstruction, curSymbolTable, curUnit.

Parameters

  • publicTouched – Only when “transit” is true, restricts the public zones of the called unit that may be modified by the call. If given null, defaults to “all true”.

  • resetValue – the “empty” value that must be set into “privateDataInTransit” for the variables that are not propagated untouched. Generally false, true for e.g. N in InOut.

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”.

removeInfoOnTopLevel

public static void removeInfoOnTopLevel(TapList<?> zonesTree)

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

removeInfoOnTopLevel

public static void removeInfoOnTopLevel(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”.

removeZeroIndexTEMPORARY

public static TapList[] removeZeroIndexTEMPORARY(TapList[] array)

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.

setExtendedDeclared

public static void setExtendedDeclared(BoolVector info, int[] vectorMap, int kind, TapIntList extendedDeclaredZones, boolean value, SymbolTable symbolTable)

Static version of setExtendedDeclared().

setExtendedDeclared

public static void setExtendedDeclared(BoolVector info, int[] vectorMap, int kind, int extendedDeclaredZone, boolean value, SymbolTable symbolTable)

Static version of setExtendedDeclared().

setExtendedDeclared

public final void setExtendedDeclared(BoolVector info, int[] vectorMap, int kind, TapIntList extendedDeclaredZones, boolean value)

Sets the booleans of “info” to “value” for the given TapIntList of extended declared zones.

setExtendedDeclared

public final void setExtendedDeclared(BoolVector info, int[] vectorMap, int kind, int extendedDeclaredZone, boolean value)

Sets the booleans of “info” to “value” for the given extended declared zone of kind “kind”.

setInfoBoolMatrixAtRowsColumns

public final void setInfoBoolMatrixAtRowsColumns(BoolMatrix matrix, TapList rowZonesTree, int rowOffset, TapList columnZonesTree, int columnOffset)

Sets elements of the given “matrix”, as prescribed by the given “rowZonesTree” and “columnZonesTree”. “rowZonesTree” and “columnZonesTree” are in general assumed to be organized with the same tree structure. For each pair of corresponding TapIntList leaves of “rowZonesTree” and “columnZonesTree”, all cells with row and column belonging to the TapIntList’s are set to true.

setInfoBoolTreeToExtendedDeclaredZones

public final void setInfoBoolTreeToExtendedDeclaredZones(BoolVector infos, int[] vectorMap, 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, int[] vectorMap, 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

setInfoPRZVTreeToExtendedDeclaredZones

public final void setInfoPRZVTreeToExtendedDeclaredZones(BoolMatrix matrix, int[] vectorMap, 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, the vectorMap and the “totalSet”.

Parameters

  • vectorMap – The map of each row of “matrix”, i.e. the map of the column indices.

setRefValue

public void setRefValue(Tree refTree, int kind, BoolVector info, int[] infoMap, 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”.

showMap

public static String showMap(int[] map)
Parameters

  • map – the given map.

Returns

the string that shows the given map.

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.

terminateTermBlock

protected void terminateTermBlock()

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.

terminateUnit

protected boolean terminateUnit()

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 final void traceDisplayPrivateZones(Unit unit, int[] map, int kind)

Displays into the trace the list of all the private zones of Unit “unit”, following the given “map” which is of kind “kind”. Globals required: curSymbolTable

vectorIndexToExtendedDeclared

public final int vectorIndexToExtendedDeclared(int index, int indexClass, int zoneKind, int[] vectorMap)

Translates a BoolVector index into its extended declared zone rank. Globals required: curUnit, curCalledUnit, curSymbolTable

For future dataflow analysis.

Parameters

  • index – The index in a BoolVector.

  • indexClass – The class of the index, i.e. its containing class in “vectorMap”. if unknown, this class can be found by getMapClass(index, vectorMap).

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

  • vectorMap – The map of the BoolVector.

Returns

the corresponding ZoneInfo.

vectorIndexToExtendedDeclared

public static int vectorIndexToExtendedDeclared(int index, int indexClass, int zoneKind, int[] vectorMap, SymbolTable symbolTable)

Translates a BoolVector index into its extended declared zone rank. Static version. Does not work for FP_CLASS.

Parameters

  • index – The index in a BoolVector.

  • indexClass – The class of the index, i.e. its containing class in “vectorMap”. if unknown, this class can be found by getMapClass(index, vectorMap).

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

  • vectorMap – The map of the BoolVector.

  • symbolTable – The current symbolTable.

Returns

the corresponding ZoneInfo.

vectorIndexToZoneInfo

public final ZoneInfo vectorIndexToZoneInfo(int index, int indexClass, int zoneKind, int[] vectorMap)

Translates a BoolVector index into the corresponding ZoneInfo. Globals required: curUnit, curCalledUnit, curSymbolTable

Parameters

  • index – The index in a BoolVector.

  • indexClass – The class of the index, i.e. its containing class in “vectorMap”. if unknown, this class can be found by getMapClass(index, vectorMap).

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

  • vectorMap – The map of the BoolVector.

Returns

the corresponding ZoneInfo.

vectorIndexToZoneInfo

public static ZoneInfo vectorIndexToZoneInfo(int index, int indexClass, int zoneKind, int[] vectorMap, SymbolTable symbolTable)

Translates a BoolVector index into the corresponding ZoneInfo. Static version. Does not work for FP_CLASS.

Parameters

  • index – The index in a BoolVector.

  • indexClass – The class of the index, i.e. its containing class in “vectorMap”. if unknown, this class can be found by getMapClass(index, vectorMap).

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

  • vectorMap – The map of the BoolVector.

  • symbolTable – The current symbolTable.

Returns

the corresponding ZoneInfo.

zoneInfoToExtendedDeclared

public final int zoneInfoToExtendedDeclared(ZoneInfo zoneInfo, int zoneClass)

Translates a ZoneInfo into its extended declared zone rank. Globals required: curUnit, curCalledUnit, curSymbolTable

Parameters

  • zoneInfo – The given ZoneInfo.

  • zoneClass – The class of “zoneInfo”, in {D_CLASS, FP_CLASS}.

Returns

The corresponding extended declared zone rank.

zoneInfoToExtendedDeclared

public static int zoneInfoToExtendedDeclared(ZoneInfo zoneInfo, int zoneClass, SymbolTable symbolTable, Unit calledUnit)

Translates a ZoneInfo into its extended declared zone rank. Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

  • zoneInfo – The given ZoneInfo.

  • zoneClass – The class of “zoneInfo”, in {D_CLASS, FP_CLASS}.

  • symbolTable – The current symbolTable.

  • calledUnit – The current called Unit, if any.

Returns

The corresponding extended declared zone rank.

zoneInfoToVectorIndex

public final int zoneInfoToVectorIndex(ZoneInfo zoneInfo, int zoneClass, int zoneKind, int[] vectorMap)

Translates a Zoneinfo, of class “zoneClass”, into its corresponding index in a targetted ZoneVector or BoolMatrix row or column, of kind “zoneKind” and whose map is given in “vectorMap”. Globals required: curCalledUnit

Parameters

  • zoneInfo – The given ZoneInfo.

  • zoneClass – The class of the given zoneInfo, in {D_CLASS, FP_CLASS}.

  • zoneKind – The kind of the targetted vector, in {ALLKIND, REALKIND, PTRKIND}.

  • vectorMap – The map of the classes used in the targetted vector.

Returns

The corresponding index in the targetted ZoneVector or BoolMatrix row or column.

zoneInfoToVectorIndex

public static int zoneInfoToVectorIndex(ZoneInfo zoneInfo, int zoneClass, int zoneKind, int[] vectorMap, Unit calledUnit)

Translates a Zoneinfo, of class “zoneClass”, into its corresponding index Static version. Needs the “calledUnit” if using FP_CLASS. in a targetted ZoneVector or BoolMatrix row or column, of kind “zoneKind” and whose map is given in “vectorMap”.

Parameters

  • zoneInfo – The given ZoneInfo.

  • zoneClass – The class of the given zoneInfo, in {D_CLASS, FP_CLASS}.

  • zoneKind – The kind of the targetted vector, in {ALLKIND, REALKIND, PTRKIND}.

  • vectorMap – The map of the classes used in the targetted vector.

  • calledUnit – The current called Unit, if any.

Returns

The corresponding index in the targetted ZoneVector or BoolMatrix row or column.

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.

zoneRkToExtendedDeclared

public final int zoneRkToExtendedDeclared(int zoneRk, int zoneClass, int zoneKind)

Translates a zone rank “zoneRk”, of kind “zoneKind” and class “zoneClass”, into its extended declared zone rank. Globals required: curCalledUnit

Parameters

  • zoneRk – The given zone index.

  • zoneClass – The class of the given zone index, in {D_CLASS, FP_CLASS}.

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

Returns

the corresponding extended declared zone rank.

zoneRkToExtendedDeclared

public static int zoneRkToExtendedDeclared(int zoneRk, int zoneClass, int zoneKind, SymbolTable symbolTable, Unit calledUnit)

Translates a zone rank “zoneRk”, of kind “zoneKind” and class “zoneClass”, into its extended declared zone rank. Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

  • zoneRk – The given zone index.

  • zoneClass – The class of the given zone index, in {D_CLASS, FP_CLASS}.

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

  • symbolTable – The current symbolTable.

  • calledUnit – The current called Unit, if any.

Returns

the corresponding extended declared zone rank.

zoneRkToPublicRk

public static int zoneRkToPublicRk(int zoneRk, int zoneKind, Unit calledUnit)

Translates a zone rank “zoneRk”, of kind “zoneKind” into its corresponding public zone rank, i.e. rank in the external shape of its Unit “calledUnit”.

Parameters

  • zoneRk – The given zone index.

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

  • calledUnit – The unit of which zoneRk is a visible zone.

Returns

The public rank of “zoneRk” in calledUnit.

zoneRkToVectorIndex

public final int zoneRkToVectorIndex(int zoneRk, int zoneClass, int zoneKind, int[] vectorMap)

Translates a zone rank “zoneRk”, of kind “zoneKind” and class “zoneClass”, into its corresponding index in a targetted ZoneVector or BoolMatrix, which must be of the same kind “zoneKind” and whose map is given in “vectorMap”. Globals required: curCalledUnit

Parameters

  • zoneRk – The given zone rank.

  • zoneClass – The class of the given zone, in {D_CLASS, FP_CLASS}.

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

  • vectorMap – The map of the classes used in the targetted vector.

Returns

The corresponding index in the targetted ZoneVector or BoolMatrix row or column.

zoneRkToVectorIndex

public static int zoneRkToVectorIndex(int zoneRk, int zoneClass, int zoneKind, int[] vectorMap, Unit calledUnit)

Translates a zone rank “zoneRk”, of kind “zoneKind” and class “zoneClass”, into its corresponding index in a targetted ZoneVector or BoolMatrix, which must be of the same kind “zoneKind” and whose map is given in “vectorMap”. Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

  • zoneRk – The given zone rank.

  • zoneClass – The class of the given zone, in {D_CLASS, FP_CLASS}.

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

  • vectorMap – The map of the classes used in the targetted vector.

  • calledUnit – The current called Unit, if any.

Returns

The corresponding index in the targetted ZoneVector or BoolMatrix row or column.

zoneRkToZoneInfo

public final ZoneInfo zoneRkToZoneInfo(int zoneRk, int zoneClass, int zoneKind)

Translates a zone rank “zoneRk”, of kind “zoneKind” and class “zoneClass”, into its ZoneInfo. Globals required: curUnit, curCalledUnit, curSymbolTable

Parameters

  • zoneRk – The given zone index.

  • zoneClass – The class of the given zone index, in {D_CLASS, FP_CLASS}.

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

Returns

the corresponding ZoneInfo.

zoneRkToZoneInfo

public static ZoneInfo zoneRkToZoneInfo(int zoneRk, int zoneClass, int zoneKind, SymbolTable symbolTable, Unit calledUnit)

Translates a zone rank “zoneRk”, of kind “zoneKind” and class “zoneClass”, into its ZoneInfo. Static version. Needs the “calledUnit” if using FP_CLASS.

Parameters

  • zoneRk – The given zone index.

  • zoneClass – The class of the given zone index, in {D_CLASS, FP_CLASS}.

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

  • symbolTable – The current symbolTable.

  • calledUnit – The current called Unit, if any.

Returns

the corresponding ZoneInfo.