1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
|
------------------------------------------------------------------------------
-- --
-- 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;
|
