GNAT: The GNU Ada Compiler June, 2004 Copyright (C) Javier Miranda and Edmond Schonberg [email protected], [email protected] Applied Microelectronics Research Institute University of Las Palmas de Gran Canaria Canary Islands Spain Computer Science Department New York University U.S.A. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any latter published by the Free Software Foundation; with the Invariant Sections being (cid:147)GNU General Public Documentation License(cid:148), the Front-Cover text being (cid:147)GNAT: The GNU Ada Compiler(cid:148), and the Back-Cover text being (cid:147)Copies published by the Free Software Foundation raise funds for GNU development.(cid:148) ii Contents I First Part: Introduction 7 1 The GNATProject 9 1.1 GCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 TheGNATCompiler . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 CompilationModel . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 TraditionalCompilationModel . . . . . . . . . . . . . . 13 1.3.2 GNATCompilationModel . . . . . . . . . . . . . . . . . 13 1.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 OverviewoftheFront-end Architecture 19 2.1 TheScanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 TheParser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.1 TheAbstractSyntaxTree . . . . . . . . . . . . . . . . . 22 2.3 TheSemanticAnalyzer . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 TheExpander . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3 Error Recovery 31 3.1 ScannerError Recovery . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.1 UseoftheCasingofIdenti(cid:2)ers . . . . . . . . . . . . . . 32 iii iv CONTENTS 3.2 Parser ErrorRecovery . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 TheParserScope-Stack . . . . . . . . . . . . . . . . . . 33 3.2.2 Example1: Useofindentation . . . . . . . . . . . . . . . 34 3.2.3 Example2: HandlingSemicolonUsedinPlace of’is’ . . 34 3.2.4 Example3: Handling’is’UsedinPlace ofSemicolon . . 36 3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 II Second Part: Semantic Analysis 39 4 Scopes andVisibility 41 4.1 FlagsandDataStructures . . . . . . . . . . . . . . . . . . . . . . 41 4.2 AnalysisofRecords,TasksandProtectedTypes.. . . . . . . . . . 45 4.3 AnalysisofPackages . . . . . . . . . . . . . . . . . . . . . . . . 46 4.4 AnalysisofPrivateTypes . . . . . . . . . . . . . . . . . . . . . . 47 4.4.1 PrivateEntitiesVisibility . . . . . . . . . . . . . . . . . . 48 4.4.2 PrivateTypeDeclarations . . . . . . . . . . . . . . . . . 49 4.4.3 Deferred ConstantsandIncompleteTypes . . . . . . . . . 51 4.4.4 LimitedTypes . . . . . . . . . . . . . . . . . . . . . . . 51 4.4.5 AnalysisofChildUnits . . . . . . . . . . . . . . . . . . . 51 4.4.6 AnalysisofSubunits . . . . . . . . . . . . . . . . . . . . 52 4.5 NameResolution . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5 OverloadResolution 55 5.1 ResolutionAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . 56 5.1.1 AdditionalDetailsfortheBottom-UpPass . . . . . . . . 57 CONTENTS v 5.1.2 DataStructures . . . . . . . . . . . . . . . . . . . . . . . 59 5.1.3 AdditionalDetailsfortheTop-DownPass . . . . . . . . . 60 5.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6 AnalysisofDiscriminants 63 6.1 AnalysisofDiscriminants. . . . . . . . . . . . . . . . . . . . . . 64 6.2 AnalysisofDiscriminantsinDerivedTypes . . . . . . . . . . . . 67 6.3 Discriminals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7 Generic Units 71 7.1 GenericUnits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.1.1 AnalysisofGenericUnits . . . . . . . . . . . . . . . . . 72 7.1.2 InstantiationofGeneric Units . . . . . . . . . . . . . . . 75 7.1.3 Parameter Matching . . . . . . . . . . . . . . . . . . . . 75 7.1.4 PrivateTypes . . . . . . . . . . . . . . . . . . . . . . . . 80 7.2 NestedGenericUnits . . . . . . . . . . . . . . . . . . . . . . . . 80 7.2.1 AnalysisofNestedGeneric Units . . . . . . . . . . . . . 80 7.2.2 InstantiationofNestedGenericUnits . . . . . . . . . . . 81 7.3 GenericChildUnits . . . . . . . . . . . . . . . . . . . . . . . . . 84 7.3.1 AnalysisofGenericChildUnits . . . . . . . . . . . . . . 84 7.3.2 InstantiationofChildGenericUnits . . . . . . . . . . . . 85 7.4 DelayedInstantiationofBodies . . . . . . . . . . . . . . . . . . . 89 7.5 DetectionofInstantiationCircularities . . . . . . . . . . . . . . . 90 7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 8 Freezing Analysis 93 vi CONTENTS 8.1 Freezing TypesandSubtypes . . . . . . . . . . . . . . . . . . . . 94 8.2 Freezing Expressions . . . . . . . . . . . . . . . . . . . . . . . . 95 8.3 Freezing Objects . . . . . . . . . . . . . . . . . . . . . . . . . . 96 8.4 Freezing Subprograms . . . . . . . . . . . . . . . . . . . . . . . 96 8.5 Freezing Packages . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.6 Freezing GenericUnits . . . . . . . . . . . . . . . . . . . . . . . 97 8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 III Third Part: Expansion 99 9 Expansion ofTasks 101 9.1 TaskCreation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 9.2 TaskTermination . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.3 TaskAbortion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.4 ExpansionofTaskTypeDeclarations. . . . . . . . . . . . . . . . 104 9.5 TaskBodyExpansion . . . . . . . . . . . . . . . . . . . . . . . . 105 9.6 ExampleofTaskExpansion . . . . . . . . . . . . . . . . . . . . 106 9.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 10 Expansion ofRendezvous andrelated Constructs 109 10.1 EntryIdenti(cid:2)cation . . . . . . . . . . . . . . . . . . . . . . . . . 110 10.2 Entry-CallExpansion . . . . . . . . . . . . . . . . . . . . . . . . 110 10.2.1 ExpansionofSimpleEntry-Calls . . . . . . . . . . . . . 112 10.2.2 ExpansionofConditionalandTimedEntry-Calls . . . . . 112 10.3 AsynchronousTransferofControl . . . . . . . . . . . . . . . . . 113 10.3.1 ATCImplementationModels . . . . . . . . . . . . . . . . 114 CONTENTS vii 10.3.2 ExpansionofATC . . . . . . . . . . . . . . . . . . . . . 116 10.4 ExpansionofAcceptStatements . . . . . . . . . . . . . . . . . . 117 10.4.1 SimpleAcceptExpansion . . . . . . . . . . . . . . . . . 117 10.4.2 TimedandSelectiveAccept . . . . . . . . . . . . . . . . 118 10.4.3 CountAttributeExpansion . . . . . . . . . . . . . . . . . 120 10.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 11 Expansion ofProtected Objects 121 11.1 TheProxyModel . . . . . . . . . . . . . . . . . . . . . . . . . . 123 11.1.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . 124 11.2 ExpansionofProtectedTypes. . . . . . . . . . . . . . . . . . . . 125 11.2.1 ExpansionofProtected-TypeSpeci(cid:2)cation . . . . . . . . 125 11.2.2 ExpansionofProtectedSubprograms . . . . . . . . . . . 127 11.2.3 ExpansionofEntryBarriers . . . . . . . . . . . . . . . . 129 11.2.4 ExpansionofEntrybodies . . . . . . . . . . . . . . . . . 129 11.2.5 TabletoBarriersandEntry-Bodies . . . . . . . . . . . . . 130 11.2.6 ExpansionofEntryFamilies . . . . . . . . . . . . . . . . 130 11.3 Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 12 Expansion ofControlled-Types 133 12.1 ImplementationOverview . . . . . . . . . . . . . . . . . . . . . 134 12.1.1 ExceptionalBlockExit . . . . . . . . . . . . . . . . . . . 135 12.1.2 FinalizationofAnonymousObjects . . . . . . . . . . . . 136 12.1.3 FinalizationofDynamicallyAllocatedObjects . . . . . . 136 12.1.4 ProblemsRelatedtoMutableObjects . . . . . . . . . . . 137 12.1.5 ControlledClass-WideObjects . . . . . . . . . . . . . . . 137 viii CONTENTS 12.2 ExpansionActivitiesforControlled-Types . . . . . . . . . . . . . 138 12.2.1 ExpansionofAssignment . . . . . . . . . . . . . . . . . 139 12.2.2 ExpansionofAnonymousControlledObjects . . . . . . . 140 12.2.3 ObjectswithControlledComponents . . . . . . . . . . . 141 12.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 13 Expansion ofTagged-Types 145 13.1 TaggedandPolymorphicObjects . . . . . . . . . . . . . . . . . . 146 13.2 TheDispatchTable . . . . . . . . . . . . . . . . . . . . . . . . . 147 13.3 PrimitiveOperations . . . . . . . . . . . . . . . . . . . . . . . . 149 13.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 IV Fourth Part: Run-Time 155 14 Tasking 157 14.1 TheAdaTaskControlBlock . . . . . . . . . . . . . . . . . . . . 157 14.2 TaskStates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 14.3 TaskCreationandTermination . . . . . . . . . . . . . . . . . . . 159 14.4 Run-TimeSubprogramsfor TaskCreationandTermination . . . . 163 14.4.1 GNARL.Enter Master . . . . . . . . . . . . . . . . . . . 165 14.4.2 GNARL.Create Task . . . . . . . . . . . . . . . . . . . . 165 14.4.3 GNARL.Activate Tasks . . . . . . . . . . . . . . . . . . 166 14.4.4 GNARL.Tasks Wrapper . . . . . . . . . . . . . . . . . . 168 14.4.5 GNARL.Complete Activation . . . . . . . . . . . . . . . 168 14.4.6 GNARL.Complete Task . . . . . . . . . . . . . . . . . . 169 14.4.7 GNARL.Complete Master . . . . . . . . . . . . . . . . . 169 CONTENTS ix 14.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 15 The Rendezvous 171 15.1 TheEntry-CallRecord . . . . . . . . . . . . . . . . . . . . . . . 172 15.2 EntriesandQueues . . . . . . . . . . . . . . . . . . . . . . . . . 173 15.3 Accepted-CallsStack . . . . . . . . . . . . . . . . . . . . . . . . 174 15.4 SelectiveAccept . . . . . . . . . . . . . . . . . . . . . . . . . . 174 15.5 Run-TimeRendezvousSubprograms . . . . . . . . . . . . . . . . 176 15.5.1 GNARL.Call Simple . . . . . . . . . . . . . . . . . . . . 176 15.5.2 GNARL.Call Synchronous . . . . . . . . . . . . . . . . . 176 15.5.3 GNARL.Task Do Or Queue . . . . . . . . . . . . . . . . 177 15.5.4 GNARL.Task Entry Call . . . . . . . . . . . . . . . . . . 177 15.5.5 GNARL.Accept Trivial . . . . . . . . . . . . . . . . . . 177 15.5.6 GNARL.Accept Call . . . . . . . . . . . . . . . . . . . . 178 15.5.7 GNARL.Complete Rendezvous . . . . . . . . . . . . . . 178 15.5.8 GNARL.Exceptional Complete Rendezvous . . . . . . . 178 15.5.9 GNARL.Selective Wait . . . . . . . . . . . . . . . . . . 179 15.5.10GNARL.Task Count . . . . . . . . . . . . . . . . . . . . 180 15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 16 Protected Objects 181 16.1 TheLock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 16.2 Run-TimeSubprograms . . . . . . . . . . . . . . . . . . . . . . . 182 16.2.1 GNARL.Protected Entry Call . . . . . . . . . . . . . . . 182 16.2.2 GNARL.PO Do Or Queue . . . . . . . . . . . . . . . . . 183 16.2.3 GNARL.Service Entries . . . . . . . . . . . . . . . . . . 184 16.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 x CONTENTS 17 Time andClocks 187 17.1 DelayandDelayUntilStatements . . . . . . . . . . . . . . . . . 187 17.2 TimedEntryCall . . . . . . . . . . . . . . . . . . . . . . . . . . 189 17.3 TimedSelectiveAccept . . . . . . . . . . . . . . . . . . . . . . . 190 17.4 Run-TimeSubprograms . . . . . . . . . . . . . . . . . . . . . . . 190 17.4.1 GNARL.Timed Delay . . . . . . . . . . . . . . . . . . . 190 17.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 18 Exceptions 193 18.1 DataStructures . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 18.1.1 Exception Id . . . . . . . . . . . . . . . . . . . . . . . . 193 18.1.2 TheExceptionsTable . . . . . . . . . . . . . . . . . . . . 194 18.2 Run-TimeSubprograms . . . . . . . . . . . . . . . . . . . . . . . 195 18.2.1 GNARL.Raise . . . . . . . . . . . . . . . . . . . . . . . 195 18.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 19 Interrupts 197 19.1 POSIX Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 19.1.1 ReservedSignals . . . . . . . . . . . . . . . . . . . . . . 199 19.2 DataStructures . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 19.2.1 InterruptsManager: BasicApproach . . . . . . . . . . . . 202 19.2.2 Server Tasks: BasicApproach . . . . . . . . . . . . . . . 203 19.2.3 Interrupt-ManagerandServer-TasksIntegration . . . . . . 203 19.3 Run-TimeSubprograms . . . . . . . . . . . . . . . . . . . . . . . 207 19.3.1 GNARL.Install Handlers . . . . . . . . . . . . . . . . . . 207 19.3.2 GNARL.Attach Handlers . . . . . . . . . . . . . . . . . 207 19.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208