dfa

Data flow analysis for Nim. We transform the AST into a linear list of instructions first to make this easier to handle: There are only 2 different branching instructions: 'goto X' is an unconditional goto, 'fork X' is a conditional goto (either the next instruction or 'X' can be taken). Exhaustive case statements are translated so that the last branch is transformed into an 'else' branch. return and break are all covered by 'goto'.

Control flow through exception handling: Contrary to popular belief, exception handling doesn't cause many problems for this DFA representation, raise is a statement that goes to the outer finally or except if there is one, otherwise it is the same as return. Every call is treated as a call that can potentially raise. However, without a surrounding try we don't emit these fork ReturnLabel instructions in order to speed up the dataflow analysis passes.

The data structures and algorithms used here are inspired by "A Graph–Free Approach to Data–Flow Analysis" by Markus Mohnen. https://link.springer.com/content/pdf/10.1007/3-540-45937-5_6.pdf

Imports

ast, types, lineinfos, renderer, asciitables, patterns

Types

InstrKind = enum
  goto, fork, def, use

Source Edit

Instr = object
  n*: PNode
  case kind*: InstrKind
  of goto, fork:
    dest*: int
  else:
    nil

Source Edit

ControlFlowGraph = seq[Instr]

Source Edit

InstrTargetKind = enum
  None, Full, Partial

Source Edit

Procs

proc echoCfg(c: ControlFlowGraph; start = 0; last = -1) {...}{.deprecated,
    raises: [Exception], tags: [RootEffect].}

Deprecated

echos the ControlFlowGraph for debugging purposes. Source Edit

proc skipConvDfa(n: PNode): PNode {...}{.raises: [], tags: [].}

Source Edit

proc aliases(obj, field: PNode): bool {...}{.raises: [Exception], tags: [RootEffect].}

Source Edit

proc instrTargets(insloc, loc: PNode): InstrTargetKind {...}{.raises: [Exception],
    tags: [RootEffect].}

Source Edit

proc isAnalysableFieldAccess(orig: PNode; owner: PSym): bool {...}{.raises: [],
    tags: [].}

Source Edit

proc constructCfg(s: PSym; body: PNode): ControlFlowGraph {...}{.raises: [Exception],
    tags: [RootEffect].}

constructs a control flow graph for body. Source Edit