mirror of
https://forge.sourceware.org/marek/gcc.git
synced 2026-02-22 03:47:02 -05:00
519 lines
21 KiB
Ada
519 lines
21 KiB
Ada
------------------------------------------------------------------------------
|
|
-- --
|
|
-- GNAT COMPILER COMPONENTS --
|
|
-- --
|
|
-- B I N D O --
|
|
-- --
|
|
-- B o d y --
|
|
-- --
|
|
-- Copyright (C) 2019-2026, 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;
|