[Ada] ABE checks v3.0, foundations of Elaboration order v4.0

------------------------
-- Elaboration checks --
------------------------

The dynamic ABE checks model now emits the same diagnostics as those of the
static ABE checks model.

The ABE checks mechanism has been redesigned and refactored in the face of
increasing requirements. Most of the functionality can now be toggled, thus
allowing for various combinations of behavior. The combinations are defined
as "initial states" and may be further altered.

Scenarios and targets have been distinctly separated at the higher level,
instead of directly working with nodes and entitites. Scenarios and targets
now carry a representation which removes the need to constantly recompute
relevant attributes, and offers a common interface for the various processors.

Most processing has now been refactored into "services" which perform a single
ABE-related function.

-----------------------
-- Elaboration order --
-----------------------

A new elaboration order mechanism based on the use of an invocation graph to
provide extra information about the flow of execution at elaboration time has
been introduced.

The ABE checks mechanism has been altered to encode pieces of the invocation
graph in the associated ALI files of units.

The new elaboration order mechanism reconstructs the full invocation graph at
bind time, and coupled with the library item graph, determines the elaboration
order of units.

The new elaboration order mechanism is currently inaccessible.

------------
-- Source --
------------

--  pack.ads

package Pack is
   procedure ABE_Proc;
   procedure Safe_Proc;
end Pack;

--  pack.adb

with Ada.Text_IO; use Ada.Text_IO;

package body Pack is
   function Call_Proc (ABE : Boolean) return Integer;

   procedure Safe_Proc is
   begin
      Put_Line ("safe");
   end Safe_Proc;

   function Call_Proc (ABE : Boolean) return Integer is
   begin
      if ABE then
         ABE_Proc;
      else
         Safe_Proc;
      end if;

      return 0;
   end Call_Proc;

   Elab_1 : constant Integer := Call_Proc (ABE => False);
   Elab_2 : constant Integer := Call_Proc (ABE => True);

   procedure ABE_Proc is
   begin
      Put_Line ("ABE");
   end ABE_Proc;
end Pack;

--  main.adb

with Pack;

procedure Main is begin null; end Main;

----------------------------
-- Compilation and output --
----------------------------

$ gnatmake -f -q -gnatE main.adb
$ ./main
$ gnatmake -f -q -gnatE main.adb -gnatDG -gnatwL
$ grep -c "safeE" pack.adb.dg
pack.adb:14:10: warning: cannot call "ABE_Proc" before body seen
pack.adb:14:10: warning: Program_Error may be raised at run time
pack.adb:14:10: warning:   body of unit "Pack" elaborated
pack.adb:14:10: warning:   function "Call_Proc" called at line 22
pack.adb:14:10: warning:   procedure "ABE_Proc" called at line 14
pack.adb:14:10: warning: cannot call "ABE_Proc" before body seen
pack.adb:14:10: warning: Program_Error may be raised at run time
pack.adb:14:10: warning:   body of unit "Pack" elaborated
pack.adb:14:10: warning:   function "Call_Proc" called at line 23
pack.adb:14:10: warning:   procedure "ABE_Proc" called at line 14
safe

raised PROGRAM_ERROR : pack.adb:14 access before elaboration
0

2019-07-03  Hristian Kirtchev  <kirtchev@adacore.com>

gcc/ada/

	* ali.adb: Add with and use clauses for GNAT,
	GNAT.Dynamic_HTables, and Snames.  Add a map from invocation
	signature records to invocation signature ids.  Add various
	encodings of invocation-related attributes.  Sort and update
	table Known_ALI_Lines.
	(Add_Invocation_Construct, Add_Invocation_Relation,
	Body_Placement_Kind_To_Code, Code_To_Body_Placement_Kind,
	Code_To_Invocation_Construct_Kind, Code_To_Invocation_Kind,
	Code_To_Invocation_Graph_Line_Kind, Destroy, Hash): New
	routines.
	(Initialize_ALI): Sort the initialization sequence. Add
	initialization for all invocation-related tables.
	(Invocation_Construct_Kind_To_Code,
	Invocation_Graph_Line_Kind_To_Code, Invocation_Kind_To_Code,
	Invocation_Signature_Of, Present): New routines.
	(Scan_ALI): Add the default values for invocation-related ids.
	Scan invocation graph lines.
	(Scan_Invocation_Graph_Line): New routine.
	* ali.ads: Add with clause for GNAT.Dynamic_Tables.  Add types
	for invocation constructs, relations, and signatures.  Add
	tables for invocation constructs, relations, and signatures.
	Update Unit_Record to capture invocation-related ids.  Relocate
	table Unit_Id_Tables and subtypes Unit_Id_Table, Unit_Id_Array
	from Binde.
	(Add_Invocation_Construct, Add_Invocation_Relation,
	Body_Placement_Kind_To_Code, Code_To_Body_Placement_Kind,
	Code_To_Invocation_Construct_Kind, Code_To_Invocation_Kind,
	Code_To_Invocation_Graph_Line_Kind,
	Invocation_Construct_Kind_To_Code,
	Invocation_Graph_Line_Kind_To_Code, Invocation_Kind_To_Code,
	Invocation_Signature_Of, Present): New routines.
	* binde.adb: Add with and use clause for Types.  Add use clause
	for ALI.Unit_Id_Tables;
	* binde.ads: Relocate table Unit_Id_Tables and subtypes
	Unit_Id_Table, Unit_Id_Array to ALI.
	* bindgen.adb: Remove with and use clause for ALI.
	* bindgen.ads: Remove with and use clause for Binde.  Add with
	and use clause for ALI.
	* bindo.adb,  bindo.ads, bindo-augmentors.adb,
	bindo-augmentors.ads, bindo-builders.adb, bindo-builders.ads,
	bindo-diagnostics.adb, bindo-diagnostics.ads,
	bindo-elaborators.adb, bindo-elaborators.ads, bindo-graphs.adb,
	bindo-graphs.ads, bindo-units.adb, bindo-units.ads,
	bindo-validators.adb, bindo-validators.ads, bindo-writers.adb,
	bindo-writers.ads: New units.
	* debug.adb: Use and describe GNAT debug switches -gnatd_F and
	-gnatd_G.  Add GNATbind debug switches in the ranges dA .. dZ,
	d.a .. d.z, d.A .. d.Z, d.1 .. d.9, d_a .. d_z, d_A .. d_Z, and
	d_1 .. d_9.  Use and describe GNATbind debug switches -d_A,
	-d_I, -d_L, -d_N, -d_O, -d_T, and -d_V.
	* exp_util.adb, exp_util.ads (Exceptions_OK): Relocate to
	Sem_Util.
	* gnatbind.adb: Add with and use clause for Bindo.  Use the new
	Bindo elaboration order only when -d_N is in effect.
	* lib-writ.adb
	(Column, Extra, Invoker, Kind, Line, Locations, Name, Placement,
	Scope, Signature, Target): New routines.
	(Write_ALI): Output all invocation-related data.
	(Write_Invocation_Graph): New routine.
	* lib-writ.ads: Document the invocation graph ALI line.
	* namet.adb, namet.ads (Present): New routines.
	* sem_ch8.adb (Find_Direct_Name): Capture the status of
	elaboration checks and warnings of an identifier.
	(Find_Expanded_Name): Capture the status of elaboration checks
	and warnings of an expanded name.
	* sem_ch12.adb (Analyze_Generic_Package_Declaration): Ensure
	that invocation graph-related data within the body of the main
	unit is encoded in the ALI file.
	(Analyze_Generic_Subprogram_Declaration): Ensure that invocation
	graph-related data within the body of the main unit is encoded
	in the ALI file.
	(Analyze_Package_Instantiation): Perform minimal decoration of
	the instance entity.
	(Analyze_Subprogram_Instantiation): Perform minimal decoration
	of the instance entity.
	* sem_elab.adb: Perform heavy refactoring of all code. The unit
	is now split into "services" which specialize in one area of ABE
	checks.  Add processing in order to capture invocation-graph
	related attributes of the main unit, and encode them in the ALI
	file.  The Processing phase can now operate in multiple modes,
	all described by type Processing_Kind.  Scenarios and targets
	are now distinct at the higher level, and carry their own
	representations. This eliminates the need to constantly
	recompute their attributes, and offers the various processors a
	uniform interface.  The various initial states of the Processing
	phase are now encoded using type Processing_In_State, and
	xxx_State constants.
	* sem_elab.ads: Update the literals of type
	Enclosing_Level_Kind.  Add Inline pragmas on several routines.
	* sem_prag.adb (Process_Inline): Ensure that invocation
	graph-related data within the body of the main unit is encoded
	in the ALI file.
	* sem_util.adb (Enclosing_Generic_Body, Enclosing_Generic_Unit):
	Code clean up.
	(Exceptions_OK): Relocated from Sem_Util.
	(Mark_Save_Invocation_Graph_Of_Body): New routine.
	* sem_util.ads (Exceptions_OK): Relocated from Sem_Util.
	(Mark_Save_Invocation_Graph_Of_Body): New routine.
	* sinfo.adb (Is_Elaboration_Checks_OK_Node): Now applicable to
	N_Variable_Reference_Marker.
	(Is_Elaboration_Warnings_OK_Node): Now applicable to
	N_Expanded_Name, N_Identifier, N_Variable_Reference_Marker.
	(Is_Read): Use Flag4.
	(Is_SPARK_Mode_On_Node): New applicable to
	N_Variable_Reference_Marker.
	(Is_Write): Use Flag5.
	(Save_Invocation_Graph_Of_Body): New routine.
	(Set_Is_Elaboration_Checks_OK_Node): Now applicable to
	N_Variable_Reference_Marker.
	(Set_Is_Elaboration_Warnings_OK_Node): Now applicable to
	N_Expanded_Name, N_Identifier, N_Variable_Reference_Marker.
	(Set_Is_SPARK_Mode_On_Node): New applicable to
	N_Variable_Reference_Marker.
	(Set_Save_Invocation_Graph_Of_Body): New routine.
	* sinfo.ads: Update the documentation of attributes
	Is_Elaboration_Checks_OK_Node, Is_Elaboration_Warnings_OK_Node,
	Is_SPARK_Mode_On_Node.  Update the flag usage of attributes
	Is_Read, Is_Write.  Add attribute Save_Invocation_Graph_Of_Body
	and update its occurrence in nodes.
	(Save_Invocation_Graph_Of_Body): New routine along with pragma
	Inline.
	(Set_Save_Invocation_Graph_Of_Body): New routine along with
	pragma Inline.
	* switch-b.adb (Scan_Binder_Switches): Refactor the scanning of
	debug switches.
	(Scan_Debug_Switches): New routine.
	* libgnat/g-dynhta.adb, libgnat/g-dynhta.ads (Contains): New routine.
	* libgnat/g-graphs.adb (Associate_Vertices): Update the use of
	Component_Vertex_Iterator.
	(Contains_Component, Contains_Edge, Contains_Vertex, Has_Next):
	Reimplemented.
	(Iterate_Component_Vertices): New routine.
	(Iterate_Vertices): Removed.
	(Next): Update the parameter profile.
	(Number_Of_Component_Vertices, Number_Of_Outgoing_Edges): New
	routines.
	* libgnat/g-graphs.ads: Update the initialization of
	No_Component.  Add type Component_Vertex_Iterator.  Remove type
	Vertex_Iterator.
	(Has_Next): Add new versions and remove old ones.
	(Iterate_Component_Vertices): New routine.
	(Iterate_Vertices): Removed.
	(Next): Add new versions and remove old ones.
	(Number_Of_Component_Vertices, Number_Of_Outgoing_Edges): New
	routines.
	* libgnat/g-sets.adb (Contains): Reimplemented.
	* gcc-interface/Make-lang.in (GNATBIND_OBJS): Add
	GNAT.Dynamic_HTables, GNAT.Graphs and Bindo units.
	* rtsfind.ads: Remove extra space.

From-SVN: r272976

1 files changed, 287 insertions, 0 deletions

diff --git a/gcc/ada/bindo.adb b/gcc/ada/bindo.adb
new file mode 100644
index 0000000..7d26476
--- /dev/null
+++ b/gcc/ada/bindo.adb
@@ -0,0 +1,287 @@
+------------------------------------------------------------------------------
+--                                                                          --
+--                         GNAT COMPILER COMPONENTS                         --
+--                                                                          --
+--                                B I N D O                                 --
+--                                                                          --
+--                                 B o d y                                  --
+--                                                                          --
+--             Copyright (C) 2019, 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 Bindo.Elaborators;
+use  Bindo.Elaborators.Invocation_And_Library_Graph_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 file.
+   --
+   --      The high-level idea is to construct two graphs:
+   --
+   --        - Invocation graph - Models the flow of execution at elaboration
+   --          time.
+   --
+   --        - Library graph - Represents with clause and pragma dependencies
+   --          between units.
+   --
+   --      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. All strongly
+   --      connected components of the library graph are discovered. Finally,
+   --      the order is obtained via a topological sort-like algorithm which
+   --      attempts to order available units while enabling other units to be
+   --      ordered.
+   --
+   --    * Diagnose elaboration circularities between units
+   --
+   --      The library graph may contain at least one cycle, in which case no
+   --      ordering is possible.
+   --
+   --      ??? more on this later
+
+   -----------------
+   -- Terminology --
+   -----------------
+
+   --  * Component - A strongly connected component of a graph.
+   --
+   --  * 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.
+   --
+   --  * Target - The destination construct of an invocation relation (the
+   --    generic, subprogram, or task type).
+
+   ------------------
+   -- 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 -------------------------+
+   --  |       |                                                           |
+   --  |       +--> ??? more on this later                                 |
+   --  |                                                                   |
+   --  +-------------------------------------------------------------------+
+
+   ------------------------
+   -- 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
+   --      peforming 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 --
+   -----------------------
+
+   --  ??? more on this later
+
+   --------------
+   -- Switches --
+   --------------
+
+   --  -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_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_N  New bindo order
+   --
+   --        GNATbind utilizes the new bindo elaboration order
+   --
+   --  -d_O  Output elaboration order
+   --
+   --        GNATbind outputs the elaboration order in text format to standard
+   --        output.
+   --
+   --  -d_T  Output elaboration order trace information
+   --
+   --        GNATbind outputs trace information on elaboration order activities
+   --        to standard output.
+   --
+   --  -d_V  Validate bindo graphs and order
+   --
+   --        GNATbind validates the invocation graph, library graph, SCC graph
+   --        and elaboration order by detecting inconsistencies and producing
+   --        error reports.
+
+   ----------------------------------------
+   -- Debugging elaboration order issues --
+   ----------------------------------------
+
+   --  ??? more on this later
+
+   ----------------------------
+   -- Find_Elaboration_Order --
+   ----------------------------
+
+   procedure Find_Elaboration_Order
+     (Order         : out Unit_Id_Table;
+      Main_Lib_File : File_Name_Type)
+   is
+   begin
+      Elaborate_Units (Order, Main_Lib_File);
+   end Find_Elaboration_Order;
+
+end Bindo;