MIMOSA INTERNAL DOCUMENTATION FOR INTERNAL XEROX USE ONLY Mimosa Internals Russ Atkinson c Copyright 1987 Xerox Corporation. All rights reserved. Abstract: This document describes the internal structure used by the Mimosa compiler. Created by: Russ Atkinson Maintained by: Russ Keywords: Mimosa, Cedar, Mesa, Dragon XEROX Xerox Corporation Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, California 94304 For Internal Xerox Use Only Introduction Mimosa compilation phases Mimosa is primarily based on the Cedar 6.0 & Cedar 7.0 releases of the Cedar/Mesa compiler. Its pass structure, algorithms, and internal structure are inherited, rather than created, which leads to some confusion at times. There has also been substantial revision, which creates a different variety of confusion. Pass 1 - Scanning & Parsing Definitions: MimP1 Exports: CompilerUtil, ScannerExtras Implementations: MimScanner Pass1 MimParserImpl Pass1T Pass2 The scanner is an ad hoc program that accepts an input stream and produces a stream of tokens. The implementation is in MimScanner.mesa. The scanner is meant to be compatible with the scanner accessible through the Cedar system (see IOScanImpl.mesa). Unfortunately, the scanners are not identical, and can give different results, although this is regarded as erroneous. The parser is a table-driven LALR(1) parser with tables produced by a separate program (PGS - Parser Generation System). Essentially the parser accepts a stream of tokens and produces an abstract syntax tree. The productions and associated actions used by PGS to produce the tables are contained in the file Pass1T.pgs. PGS also produces the file Pass1T.mesa, which is a renumbered version of Pass1T.pgs. The mesa code in Pass1T.pgs (copied to Pass1T.mesa) specifies the actions at each production, and specialized comments specify the productions. There is a current limitation of 256 (maybe 255) productions imposed by PGS. There is some indication that the PGS code was meant to handle more, but it has not been made to work. [RRA] Pass 2 - Semantic table building Definitions: none Exports: CompilerUtil Implementations: Pass2 This pass (implemented by Pass2) scans the tree, producing some simplifications, and constructs semantic entries for all type constructors, body table and context entries for all observed bodies, and other housekeeping. Pass 3 - Type checking Definitions: MimP3 MimP3S Pass3Attributes Pass3 Exports: CompilerUtil, MimosaCopier Implementations: MimosaCopierImpl, Pass3AttributesImpl Pass3B Pass3D Pass3I Pass3M Pass3S Pass3V Pass3Xa Pass3Xb Pass3Xc Pass3P Pass3 performs most of the work in the compiler not related to actual code generation: type checking, definitions reading, and symbol copying. Much of the work comes from making sense out of generic operations like generic arithmetic. Type checking is carried out up to but not including range checking, so subranges are considered to be equivalent to base types. MimosaCopierImpl - symbol copying MimosaCopierImpl copies symbols (and trees) from symbols files into the current symbol table within the compiler. Pass3B - DIRECTORY processing Pass3D - declaration processing Pass3I - identifier processing Pass3I performs most declaration and scope processing for identifiers. Pass3I also performs RC map completion and REF literal processing. Pass3M - miscellaneous processing Pass3M handles type checking for a variety of statements and expressions. Pass3M.MiscStmt handles the following nodes: signal, error, start, join, wait, xerror, resume, reject, continue, retry, restart, stop, notify, broadcast, free, and enable. Pass3M.MiscStmt even handles some obsolete forms (dst, lst, lste, lstf). Pass3M.New handles new (New), cons (Cons) and listcons (ListCons) nodes (all called by Pass3XB). Unusual control transfers are handled by Pass3M.MiscXfer (signalx, errorx, fork, joinx, create, startx). Catch phrases are handled by Pass3M.CatchPhrase. Pass3S - statement processing general statement processing Pass3V - variant processing variant record processing Pass3Xa, Pass3Xb, Pass3Xc - expression processing general expression processing Pass3P - INLINE expansion Pass3P performs most of the inline expansion, transforming calls on inline procedures into subst nodes (for calls that are statements) and substx nodes (for calls that are expressions). In many ways this module is a completely separate pass. There is a funny problem with inline expansion due to the fact that trees are saved at the end of Pass4 processing, while they are expanded before Pass4 processing. Someday this crock should be fixed! [RRA] Pass 4 - Range checking & constant folding Pass 4 performs the range checking part of type checking, which requires that constant folding be performed as well. During Pass 4 the sizes of all types and variables are determined, as well as the layout of records (the bit positions of all fields). The constant folding is still a bit of a mess since there are still implicit assumptions about the big-endian nature of the target, yet we eventually want to target little-endian machines. For now most constant-fodling is disabled for record and array constructors. This problem is partly relieved by constant expression collection and evaluation during global frame initialization. However, this area still needs work. [RRA] Pass4B - Binary file processing Pass4B deals with Pass 4 initialization and with object files. Pass4B assigns links to imported items in AssignImports. Pass4B determines exported type mismatches in ExportId. Pass4L - Layout Pass4L lays out records, frames, interfaces, and so forth. Ideally all decisions would be determined by parameters, but this still needs some work. Pass4L has facilities (currently not used) for performing naive local variable allocation using static frequency. Unfortunately, on some machines (like Dragon), variables have penalties for being placed in arbitrary locations, and register assignment is better left to machine dependent modules anyway. Pass4L puts out the LinkFrag part of the mob file (indicating which items are imported). Pass 5 - Intermediate code generation Definitions: MimCode MimGenRC MimP5 MimP5S MimP5U Exports: ?? Implementations: MimCalls MimP5UImpl MimCons MimExpr MimFlow MimSelect MimStmt MimStore MimDriver ?? MimP5UImpl - utility routines MimCalls - generation of procedure calls MimCons - constructors MimExpr - expressions general expression generation: binary & unary arithmetic MimFlow - flow of control relational expressions, IF, labels, EXIT, LOOP, GO TO, arithmetic conversions MimSelect - selectors SELECT, WITH ... SELECT ISTYPE, NARROW type & tag predicates MimStmt - statements general statements MimStore - storing of values assignment, extraction, indexing of arrays MimDriver - module level generation modules, procedures, returns, monitors locks, proc descriptors Int Code - Intermediate code transformations Definitions: ?? Exports: IntCodeTarget, IntCodeTwig, IntCodeUtils, ParseIntCode, TargetConversions Implementations: IntCodeTargetImpl, IntCodeTwigImpl, IntCodeUtilsImpl, ParseIntCodeImpl, TargetConversionsImpl IntCodeTwigImpl - intermediate code transformations IntCodeTwigImpl handles transformations on the intermediate code. Most of these transformations have to do with the procedure model. It is this module that handles argument record and return record limits, nested procedures, and many others. See IntCodeTwigDoc for more information. Utilities Definitions: ?? Exports: ?? Implementations: SymbolCacheImpl, SymbolOpsImpl, TreeOpsImpl, LiteralOpsImpl, SymLiteralOpsImpl, TypesImpl, MimFilesImpl, BcdOutput, MesaTab, ConstArithImpl, MimSysOpsImpl Control & Data Definitions: ?? Exports: ?? Implementations: DebugTab, ErrorTab, FileParmsImpl, MimCommandUtilImpl, MimData, MimosaDebug, MimosaInterface, MimosaLogImpl, MimosaSequencer Other Definitions: MimosaType2CType Exports: MimosaType2CType Implementations: MimosaType2CTypeImpl MimosaType2CTypeImpl - C type hacking MimosaType2CTypeImpl turns a Mimosa type description into a C type description. This translation is only partial, and has not been verified. Commentary Pass4D.PushTrimDecls Pass4D.PushDecl used to trim off all declarations without initializations. This apparantly assumed that no declaration preocessing would happen in Pass5 (code generation). This assumption is, of course, completely bogus for Mimosa. Therefore, this trimming now passes through all declarations, even if there is no initialization. Internal debugging variables This documents interesting little variables in the Mimosa compiler that can be set to assist debugging, or just to alter the behavior in interesting ways. The types and defaults are given as Mesa declarations. AllocImpl.neverFree: BOOL _ FALSE Can be set to TRUE to inhibit retail level freeing of chunks from tables. Recent (Dec. '87) measurements indicate that only about 25-30% of chunks allocated are ever freed at the retail level (they are, of course, freed at the wholesale level). MimDriver.enableNamesFile: BOOL _ TRUE Enables the output of the variable names file (*.names). MimDriver.enableTypesFile: BOOL _ TRUE Enables the output of the C types file (*.cTypes). MimDriver.enableStreamOutput: BOOL _ TRUE Enables a simple text file of the icd output. MimDriver.enableTiogaOutput: BOOL _ FALSE Enables a node-structured file of the icd output. MimDriver.enableViewerOutput: BOOL _ FALSE Special case to inhibit freeing of just Tree nodes. MimosaLogImpl.debug: BOOL _ FALSE When set, will cause the signal MimosaLogImpl.EnterSignal to be raised when MimosaLogImpl.Enter is called, as it is for every error or warning message written on the compiler log. MimStmt.sourceBreak: SourceMap.Loc _ SourceMap.nullLoc When set, will cause the signal MimStmt.SourceSeen to be raised when MimStmt.StatementTree is started on a node with the specified source index. Pass2.recordPainted: BOOL _ TRUE If TRUE, then records default to being painted (but not argument records). Pass2.enumPainted: BOOL _ TRUE If TRUE, then enumerations default to being painted. Pass2.recordPacked: BOOL _ TRUE If TRUE, then records default to being packed (but not argument records). Pass3S.sourceBreak: SourceMap.Loc _ SourceMap.nullLoc When set, will cause the signal Pass3S.SourceSeen to be raised when Pass3S.Stmt is started on a node with the specified source index. Pass4S.sourceBreak: SourceMap.Loc _ SourceMap.nullLoc When set, will cause the signal Pass4S.SourceSeen to be raised when Pass4S.Stmt is started on a node with the specified source index. TreeOpsImpl.neverFree: BOOL _ FALSE Special case to inhibit freeing of just Tree nodes. R MimosaInternalDoc.tioga Russ Atkinson (RRA) March 9, 1988 2:04:11 pm PST ÊZ•NewlineDelimiter –(cedardoc) style™•Mark LastEditedšœ™Icode– LastEdited™0—J– LastEdited™Iunleaded– centerHeaderšÐlsÏsžž ˜L– centerFooteršž˜Ititle˜Iauthorsšœ ˜ IabstractšÐmsž8˜9OšÏb œL˜UOš  œ˜Oš œ˜!Oš  œ˜%O˜I boilerplateš ÏqœÏoœ¢œ¢œ¢ Ñbox˜Žheadšœ ˜ ˜Iblock˜º ˜Iitemšœ˜Sšœ$˜$Sšœ<˜—— ˜,Sšœ˜SšœR˜RSšœn˜n šœ3˜3Qšœ˜—— ˜ Sšœ˜Sšœ ˜ Sšœ«˜«— ˜Sšœ˜Sšœ ˜ Sšœ˜— ˜Sšœ˜Sšœ˜Sšœ%˜% šœ%˜%Qšœ˜———— ˜ šœ˜RšœÌ˜Ì—— ˜R˜Ò šœ¤œ¤˜!Ršœ¤œã˜õ— šœ¤œ¤˜&R˜8— šœ¤œ¤˜&R˜2— šœ¤œ¤˜)R˜-— šœ¤œ¤˜)R˜1— šœ¤œ¤˜*R˜3— šœ¤œ¤˜!Ršœ³˜³— šœ6˜6Ršœ˜— šœ¤œ¤˜ Ršœ¤œC˜J— šœ¤œ¤˜Ršœ¤œ-˜4— šœ¤œ¤˜Ršœ¤œB˜I— šœ5˜5Ršœ…˜…— šœ5˜5Ršœ…˜…— šœ¤œ¤˜#R˜3———…—)ä/