| ------------------------------------------------------------------------------ |
| -- -- |
| -- GNAT COMPILER COMPONENTS -- |
| -- -- |
| -- B I N D O -- |
| -- -- |
| -- B o d y -- |
| -- -- |
| -- Copyright (C) 2019-2022, Free Software Foundation, Inc. -- |
| -- -- |
| -- GNAT is free software; you can redistribute it and/or modify it under -- |
| -- terms of the GNU General Public License as published by the Free Soft- -- |
| -- ware Foundation; either version 3, or (at your option) any later ver- -- |
| -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- |
| -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- |
| -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -- |
| -- for more details. You should have received a copy of the GNU General -- |
| -- Public License distributed with GNAT; see file COPYING3. If not, go to -- |
| -- http://www.gnu.org/licenses for a complete copy of the license. -- |
| -- -- |
| -- GNAT was originally developed by the GNAT team at New York University. -- |
| -- Extensive contributions were provided by Ada Core Technologies Inc. -- |
| -- -- |
| ------------------------------------------------------------------------------ |
| |
| with Binde; |
| with Opt; use Opt; |
| |
| with Bindo.Elaborators; |
| use Bindo.Elaborators; |
| |
| package body Bindo is |
| |
| --------------------------------- |
| -- Elaboration-order mechanism -- |
| --------------------------------- |
| |
| -- The elaboration-order (EO) mechanism implemented in this unit and its |
| -- children has the following objectives: |
| -- |
| -- * Find an ordering of all library items (historically referred to as |
| -- "units") in the bind which require elaboration, taking into account: |
| -- |
| -- - The dependencies between units expressed in the form of with |
| -- clauses. |
| -- |
| -- - Pragmas Elaborate, Elaborate_All, Elaborate_Body, Preelaborable, |
| -- and Pure. |
| -- |
| -- - The flow of execution at elaboration time. |
| -- |
| -- - Additional dependencies between units supplied to the binder by |
| -- means of a forced-elaboration-order file. |
| -- |
| -- The high-level idea empoyed by the EO mechanism is to construct two |
| -- graphs and use the information they represent to find an ordering of |
| -- all units. |
| -- |
| -- The invocation graph represents the flow of execution at elaboration |
| -- time. |
| -- |
| -- The library graph captures the dependencies between units expressed |
| -- by with clause and elaboration-related pragmas. The library graph is |
| -- further augmented with additional information from the invocation |
| -- graph by exploring the execution paths from a unit with elaboration |
| -- code to other external units. |
| -- |
| -- The strongly connected components of the library graph are computed. |
| -- |
| -- The order is obtained using a topological sort-like algorithm which |
| -- traverses the library graph and its strongly connected components in |
| -- an attempt to order available units while enabling other units to be |
| -- ordered. |
| -- |
| -- * Diagnose elaboration circularities between units |
| -- |
| -- An elaboration circularity arises when either |
| -- |
| -- - At least one unit cannot be ordered, or |
| -- |
| -- - All units can be ordered, but an edge with an Elaborate_All |
| -- pragma links two vertices within the same component of the |
| -- library graph. |
| -- |
| -- The library graph is traversed to discover, collect, and sort all |
| -- cycles that hinder the elaboration order. |
| -- |
| -- The most important cycle is diagnosed by describing its effects on |
| -- the elaboration order and listing all units comprising the circuit. |
| -- Various suggestions on how to break the cycle are offered. |
| |
| ----------------- |
| -- Terminology -- |
| ----------------- |
| |
| -- * Component - A strongly connected component of a graph. |
| -- |
| -- * Elaborable component - A component that is not waiting on other |
| -- components to be elaborated. |
| -- |
| -- * Elaborable vertex - A vertex that is not waiting on strong and weak |
| -- predecessors, and whose component is elaborable. |
| -- |
| -- * Elaboration circularity - A cycle involving units from the bind. |
| -- |
| -- * Elaboration root - A special invocation construct which denotes the |
| -- elaboration procedure of a unit. |
| -- |
| -- * Invocation - The act of activating a task, calling a subprogram, or |
| -- instantiating a generic. |
| -- |
| -- * Invocation construct - An entry declaration, [single] protected type, |
| -- subprogram declaration, subprogram instantiation, or a [single] task |
| -- type declared in the visible, private, or body declarations of some |
| -- unit. The construct is encoded in the ALI file of the related unit. |
| -- |
| -- * Invocation graph - A directed graph which models the flow of execution |
| -- at elaboration time. |
| -- |
| -- - Vertices - Invocation constructs plus extra information. Certain |
| -- vertices act as elaboration roots. |
| -- |
| -- - Edges - Invocation relations plus extra information. |
| -- |
| -- * Invocation relation - A flow link between two invocation constructs. |
| -- This link is encoded in the ALI file of unit that houses the invoker. |
| -- |
| -- * Invocation signature - A set of attributes that uniquely identify an |
| -- invocation construct within the namespace of all ALI files. |
| -- |
| -- * Invoker - The source construct of an invocation relation (the caller, |
| -- instantiator, or task activator). |
| -- |
| -- * Library graph - A directed graph which captures with clause and pragma |
| -- dependencies between units. |
| -- |
| -- - Vertices - Units plus extra information. |
| -- |
| -- - Edges - With clause, pragma, and additional dependencies between |
| -- units. |
| -- |
| -- * Pending predecessor - A vertex that must be elaborated before another |
| -- vertex can be elaborated. |
| -- |
| -- * Strong edge - A non-invocation library graph edge. Strong edges |
| -- represent the language-defined relations between units. |
| -- |
| -- * Strong predecessor - A library graph vertex reachable via a strong |
| -- edge. |
| -- |
| -- * Target - The destination construct of an invocation relation (the |
| -- generic, subprogram, or task type). |
| -- |
| -- * Weak edge - An invocation library graph edge. Weak edges represent |
| -- the speculative flow of execution at elaboration time, which may or |
| -- may not take place. |
| -- |
| -- * Weak predecessor - A library graph vertex reachable via a weak edge. |
| -- |
| -- * Weakly elaborable vertex - A vertex that is waiting solely on weak |
| -- predecessors to be elaborated, and whose component is elaborable. |
| |
| ------------------ |
| -- Architecture -- |
| ------------------ |
| |
| -- Find_Elaboration_Order |
| -- | |
| -- +--> Collect_Elaborable_Units |
| -- +--> Write_ALI_Tables |
| -- +--> Elaborate_Units |
| -- | |
| -- +------ | -------------- Construction phase ------------------------+ |
| -- | | | |
| -- | +--> Build_Library_Graph | |
| -- | +--> Validate_Library_Graph | |
| -- | +--> Write_Library_Graph | |
| -- | | | |
| -- | +--> Build_Invocation_Graph | |
| -- | +--> Validate_Invocation_Graph | |
| -- | +--> Write_Invocation_Graph | |
| -- | | | |
| -- +------ | ----------------------------------------------------------+ |
| -- | |
| -- +------ | -------------- Augmentation phase ------------------------+ |
| -- | | | |
| -- | +--> Augment_Library_Graph | |
| -- | | | |
| -- +------ | ----------------------------------------------------------+ |
| -- | |
| -- +------ | -------------- Ordering phase ----------------------------+ |
| -- | | | |
| -- | +--> Find_Components | |
| -- | | | |
| -- | +--> Elaborate_Library_Graph | |
| -- | +--> Validate_Elaboration_Order | |
| -- | +--> Write_Elaboration_Order | |
| -- | | | |
| -- | +--> Write_Unit_Closure | |
| -- | | | |
| -- +------ | ----------------------------------------------------------+ |
| -- | |
| -- +------ | -------------- Diagnostics phase -------------------------+ |
| -- | | | |
| -- | +--> Find_Cycles | |
| -- | +--> Validate_Cycles | |
| -- | +--> Write_Cycles | |
| -- | | | |
| -- | +--> Diagnose_Cycle / Diagnose_All_Cycles | |
| -- | | |
| -- +-------------------------------------------------------------------+ |
| |
| ------------------------ |
| -- Construction phase -- |
| ------------------------ |
| |
| -- The Construction phase has the following objectives: |
| -- |
| -- * Build the library graph by inspecting the ALI file of each unit that |
| -- requires elaboration. |
| -- |
| -- * Validate the consistency of the library graph, only when switch -d_V |
| -- is in effect. |
| -- |
| -- * Write the contents of the invocation graph in human-readable form to |
| -- standard output when switch -d_L is in effect. |
| -- |
| -- * Build the invocation graph by inspecting invocation constructs and |
| -- relations in the ALI file of each unit that requires elaboration. |
| -- |
| -- * Validate the consistency of the invocation graph, only when switch |
| -- -d_V is in effect. |
| -- |
| -- * Write the contents of the invocation graph in human-readable form to |
| -- standard output when switch -d_I is in effect. |
| |
| ------------------------ |
| -- Augmentation phase -- |
| ------------------------ |
| |
| -- The Augmentation phase has the following objectives: |
| -- |
| -- * Discover transitions of the elaboration flow from a unit with an |
| -- elaboration root to other units. Augment the library graph with |
| -- extra edges for each such transition. |
| |
| -------------------- |
| -- Ordering phase -- |
| -------------------- |
| |
| -- The Ordering phase has the following objectives: |
| -- |
| -- * Discover all components of the library graph by treating specs and |
| -- bodies as single vertices. |
| -- |
| -- * Try to order as many vertices of the library graph as possible by |
| -- performing a topological sort based on the pending predecessors of |
| -- vertices across all components and within a single component. |
| -- |
| -- * Validate the consistency of the order, only when switch -d_V is in |
| -- effect. |
| -- |
| -- * Write the contents of the order in human-readable form to standard |
| -- output when switch -d_O is in effect. |
| -- |
| -- * Write the sources of the order closure when switch -R is in effect. |
| |
| ----------------------- |
| -- Diagnostics phase -- |
| ----------------------- |
| |
| -- The Diagnostics phase has the following objectives: |
| -- |
| -- * Discover, save, and sort all cycles in the library graph. The cycles |
| -- are sorted based on the following heuristics: |
| -- |
| -- - A cycle with higher precedence is preferred. |
| -- |
| -- - A cycle with fewer invocation edges is preferred. |
| -- |
| -- - A cycle with a shorter length is preferred. |
| -- |
| -- * Validate the consistency of cycles, only when switch -d_V is in |
| -- effect. |
| -- |
| -- * Write the contents of all cycles in human-readable form to standard |
| -- output when switch -d_O is in effect. |
| -- |
| -- * Diagnose the most important cycle, or all cycles when switch -d_C is |
| -- in effect. The diagnostic consists of: |
| -- |
| -- - The reason for the existence of the cycle, along with the unit |
| -- whose elaboration cannot be guaranteed. |
| -- |
| -- - A detailed traceback of the cycle, showcasing the transition |
| -- between units, along with any other elaboration-order-related |
| -- information. |
| -- |
| -- - A set of suggestions on how to break the cycle considering the |
| -- the edges comprising the circuit, the elaboration model used to |
| -- compile the units, the availability of invocation information, |
| -- and the state of various relevant switches. |
| |
| -------------- |
| -- Switches -- |
| -------------- |
| |
| -- -d_a Ignore the effects of pragma Elaborate_All |
| -- |
| -- GNATbind creates a regular with edge instead of an Elaborate_All |
| -- edge in the library graph, thus eliminating the effects of the |
| -- pragma. |
| -- |
| -- -d_b Ignore the effects of pragma Elaborate_Body |
| -- |
| -- GNATbind treats a spec and body pair as decoupled. |
| -- |
| -- -d_e Ignore the effects of pragma Elaborate |
| -- |
| -- GNATbind creates a regular with edge instead of an Elaborate edge |
| -- in the library graph, thus eliminating the effects of the pragma. |
| -- In addition, GNATbind does not create an edge to the body of the |
| -- pragma argument. |
| -- |
| -- -d_t Output cycle-detection trace information |
| -- |
| -- GNATbind outputs trace information on cycle-detection activities |
| -- to standard output. |
| -- |
| -- -d_A Output ALI invocation tables |
| -- |
| -- GNATbind outputs the contents of ALI table Invocation_Constructs |
| -- and Invocation_Edges in textual format to standard output. |
| -- |
| -- -d_C Diagnose all cycles |
| -- |
| -- GNATbind outputs diagnostics for all unique cycles in the bind, |
| -- rather than just the most important one. |
| -- |
| -- -d_I Output invocation graph |
| -- |
| -- GNATbind outputs the invocation graph in text format to standard |
| -- output. |
| -- |
| -- -d_L Output library graph |
| -- |
| -- GNATbind outputs the library graph in textual format to standard |
| -- output. |
| -- |
| -- -d_P Output cycle paths |
| -- |
| -- GNATbind outputs the cycle paths in text format to standard output |
| -- |
| -- -d_S Output elaboration-order status information |
| -- |
| -- GNATbind outputs trace information concerning the status of its |
| -- various phases to standard output. |
| -- |
| -- -d_T Output elaboration-order trace information |
| -- |
| -- GNATbind outputs trace information on elaboration-order detection |
| -- activities to standard output. |
| -- |
| -- -d_V Validate bindo cycles, graphs, and order |
| -- |
| -- GNATbind validates the invocation graph, library graph along with |
| -- its cycles, and elaboration order by detecting inconsistencies and |
| -- producing error reports. |
| -- |
| -- -e Output complete list of elaboration-order dependencies |
| -- |
| -- GNATbind outputs the dependencies between units to standard |
| -- output. |
| -- |
| -- -f Force elaboration order from given file |
| -- |
| -- GNATbind applies an additional set of edges to the library graph. |
| -- The edges are read from a file specified by the argument of the |
| -- flag. |
| -- |
| -- -H Legacy elaboration-order model enabled |
| -- |
| -- GNATbind uses the library-graph and heuristics-based elaboration- |
| -- order model. |
| -- |
| -- -l Output chosen elaboration order |
| -- |
| -- GNATbind outputs the elaboration order in text format to standard |
| -- output. |
| -- |
| -- -p Pessimistic (worst-case) elaboration order |
| -- |
| -- This switch is not used in Bindo and its children. |
| |
| ---------------------------------------- |
| -- Debugging elaboration-order issues -- |
| ---------------------------------------- |
| |
| -- Prior to debugging elaboration-order-related issues, enable all relevant |
| -- debug flags to collect as much information as possible. Depending on the |
| -- number of files in the bind, Bindo may emit anywhere between several MBs |
| -- to several hundred MBs of data to standard output. The switches are: |
| -- |
| -- -d_A -d_C -d_I -d_L -d_P -d_t -d_T -d_V |
| -- |
| -- Bindo offers several debugging routines that can be invoked from gdb. |
| -- Those are defined in the body of Bindo.Writers, in sections denoted by |
| -- header Debug. For quick reference, the routines are: |
| -- |
| -- palgc -- print all library-graph cycles |
| -- pau -- print all units |
| -- pc -- print component |
| -- pige -- print invocation-graph edge |
| -- pigv -- print invocation-graph vertex |
| -- plgc -- print library-graph cycle |
| -- plge -- print library-graph edge |
| -- plgv -- print library-graph vertex |
| -- pu -- print units |
| -- |
| -- * Apparent infinite loop |
| -- |
| -- The elaboration order mechanism appears to be stuck in an infinite |
| -- loop. Use switch -d_S to output the status of each elaboration phase. |
| -- |
| -- * Invalid elaboration order |
| -- |
| -- The elaboration order is invalid when: |
| -- |
| -- - A unit that requires elaboration is missing from the order |
| -- - A unit that does not require elaboration is present in the order |
| -- |
| -- Examine the output of the elaboration algorithm available via switch |
| -- -d_T to determine how the related units were included in or excluded |
| -- from the order. Determine whether the library graph contains all the |
| -- relevant edges for those units. |
| -- |
| -- Units and routines of interest: |
| -- Bindo.Elaborators |
| -- Elaborate_Library_Graph |
| -- Elaborate_Units |
| -- |
| -- * Invalid invocation graph |
| -- |
| -- The invocation graph is invalid when: |
| -- |
| -- - An edge lacks an attribute |
| -- - A vertex lacks an attribute |
| -- |
| -- Find the malformed edge or vertex and determine which attribute is |
| -- missing. Examine the contents of the invocation-related ALI tables |
| -- available via switch -d_A. If the invocation construct or relation |
| -- is missing, verify the ALI file. If the ALI lacks all the relevant |
| -- information, then Sem_Elab most likely failed to discover a valid |
| -- elaboration path. |
| -- |
| -- Units and routines of interest: |
| -- Bindo.Builders |
| -- Bindo.Graphs |
| -- Add_Edge |
| -- Add_Vertex |
| -- Build_Invocation_Graph |
| -- |
| -- * Invalid library graph |
| -- |
| -- The library graph is invalid when: |
| -- |
| -- - An edge lacks an attribute |
| -- - A vertex lacks an attribute |
| -- |
| -- Find the malformed edge or vertex and determine which attribute is |
| -- missing. |
| -- |
| -- Units and routines of interest: |
| -- Bindo.Builders |
| -- Bindo.Graphs |
| -- Add_Edge |
| -- Add_Vertex |
| -- Build_Library_Graph |
| -- |
| -- * Invalid library-graph cycle |
| -- |
| -- A library-graph cycle is invalid when: |
| -- |
| -- - It lacks enough edges to form a circuit |
| -- - At least one edge in the circuit is repeated |
| -- |
| -- Find the malformed cycle and determine which attribute is missing. |
| -- |
| -- Units and routines of interest: |
| -- Bindo.Graphs |
| -- Find_Cycles |
| |
| ---------------------------- |
| -- Find_Elaboration_Order -- |
| ---------------------------- |
| |
| procedure Find_Elaboration_Order |
| (Order : out Unit_Id_Table; |
| Main_Lib_File : File_Name_Type) |
| is |
| begin |
| -- Use the library graph and heuristic-based elaboration order when |
| -- switch -H (legacy elaboration-order mode enabled). |
| |
| if Legacy_Elaboration_Order then |
| Binde.Find_Elab_Order (Order, Main_Lib_File); |
| |
| -- Otherwise use the invocation and library-graph-based elaboration |
| -- order. |
| |
| else |
| Invocation_And_Library_Graph_Elaborators.Elaborate_Units |
| (Order => Order, |
| Main_Lib_File => Main_Lib_File); |
| end if; |
| end Find_Elaboration_Order; |
| |
| end Bindo; |
