Skip to content

Check Use Def Cycles

Jump to bottom
Andrei Tumbar edited this page Sep 24, 2026 · 4 revisions

This algorithm traverses the a source model and checks that there are no cycles in the use-def graph.

Input

  1. A list tul of translation units.

  2. An analysis data structure a representing the results of analysis so far. The use-def map must already be computed. The visited symbol set, use-def path set, and use-def path list must be empty.

Output

  1. The unmodified analysis a, if the check passes; otherwise an error.

Procedure

  1. Visit each translation unit in tul with input a. Return a or an error as the result.

AST Visitor Methods

Each method accepts an analysis data structure a as input and yields either a new analysis data structure a' or an error as output.

  1. Translation units: For each translation unit tu, visit each definition appearing in tu.

  2. Definitions: For each definition d that may be involved in a cycle:

    1. Let s be the unique symbol representing d. A bound parameter symbol counts as such a definition. The uses appearing in it are the uses appearing in its argument: the expression of a constant argument, the type name of a type argument, or the component instance use of a port interface instance argument.

    2. Check whether s appears in the use-def symbol set of a. If it does, then the use-def matching list of a represents a cycle. Throw a semantic error. Use the use-def matching list to construct the cycle for the error message.

    3. Otherwise if s is not in the visited symbol set of a, then

      1. Let a' be the analysis data structure that results from adding s to the use-def symbol set set of a.

      2. Visit each use appearing in d with input a'.

      3. Let a'' be the analysis data structure that results from adding s to the visited symbol set of a.

      4. Yield a'' as the result.

    4. Otherwise we have already visited s; yield a as the result.

  3. Uses: For each AST node n that represents a use:

    1. Look in the use-def map of n to get the symbol s corresponding to n. Throw an internal error if it is not there.

    2. Use n and s to construct a use-def matching m.

    3. Let a' be the analysis data structure that results from adding m to the use-def matching list of a.

    4. Visit the definition corresponding to s with input a'.

    5. Return a or an error.

Clone this wiki locally