Return to twigb.t CVS log

Up to [Research Unix] / researchv10no / cmd / twig / doc / manual

Annotation of researchv10no/cmd/twig/doc/manual/twigb.t, revision 1.1

1.1     ! root        1: .EQ
        !             2: delim ##
        !             3: .EN
        !             4: .DS C
        !             5: \f3 Twig: A Brief Description\f1
        !             6: .DE
        !             7: .sp 2 ex
        !             8: .PP
        !             9: Twig is a language for processing trees based on the
        !            10: algorithms described above.  A twig program consists of a set
        !            11: of pattern-action rules together with associated declarations.  Patterns
        !            12: describe trees to be matched.  Actions calculate costs, perform tree
        !            13: manipulations and other functions such as emitting code.
        !            14: A twig program is translated by the twig
        !            15: preprocessor into subroutines and tables in the host language which is C.
        !            16: .PP
        !            17: There are many ways to represent trees and costs.  To give the user more
        !            18: choice in representation, twig treats them as abstract data
        !            19: types (ADT).  Its manipulation of trees and costs are strictly performed
        !            20: through calls to subroutines provided by the user.
        !            21: .sp 1ex
        !            22: .SH
        !            23: Rules
        !            24: .PP
        !            25: The fundamental unit of a twig program is a rule.
        !            26: .sp 1ex
        !            27: .ti 1.5in
        !            28: \f2label \f3: \f2tree_pattern \f3[ \f2cost \f3] [ = \f2action \f3]\f1
        !            29: .sp 1ex
        !            30: .PP
        !            31: Intuitively, the pattern is used to match a subtree.  The \f2cost\f1 code
        !            32: fragment is then evaluated.  The resulting cost is recorded by
        !            33: the matcher for use in dynamic programming.  The \f2action\f1 is executed
        !            34: if the rule is part of the least cost cover of the tree.
        !            35: .PP
        !            36: If the \f2cost\f1 part is missing, Twig will insert default code
        !            37: that returns the special value, DEFAULT_COST.
        !            38: A missing \f2action\f1 part indicates that no action will be taken when a
        !            39: match is found.
        !            40: .SH
        !            41: Tree Patterns
        !            42: .PP
        !            43: Tree patterns are specified
        !            44: in prefix parenthesized form and can be described by the
        !            45: following BNF:
        !            46: .DS
        !            47: .na
        !            48: .nf
        !            49: \f2tree_pattern \(-> node_id | label_id
        !            50: tree_pattern \(-> node_id (tree_list)
        !            51: tree_list \(-> tree,tree_list | tree
        !            52: .DE
        !            53: .ad
        !            54: .fi
        !            55: For example, the tree,
        !            56: .DS
        !            57: .sp 1in
        !            58: .DE
        !            59: will be written in twig as
        !            60: .sp 1ex
        !            61: .DS
        !            62: .na
        !            63: .nf
        !            64: \f3oper(leftOp,rightOp)\f1
        !            65: .DE
        !            66: .ad
        !            67: .fi
        !            68: .PP
        !            69: There are two types of symbols: \f2node_id\f1s and \f2label_id\f1s.
        !            70: \f2Node_id\f1s are used to denote internal nodes and leaves.
        !            71: \f2Label_id\f1s label tree patterns and are analogous to
        !            72: non-terminals in context free grammars.
        !            73: For example, the following twig rules without their action parts describe
        !            74: simple expression trees with the \f3plus\f1 operator.
        !            75: .DS
        !            76: \f3
        !            77: .na
        !            78: .nf
        !            79: expr: plus(expr, expr)
        !            80: expr: identifier
        !            81: expr: constant
        !            82: .DE
        !            83: .ad
        !            84: .fi
        !            85: \f3Identifier\f1 and \f3constant\f1 are \f2node_id\f1s
        !            86: representing leaves, and
        !            87: \f2plus\f1 is a \f2node_id\f1s representing an internal node whereas
        !            88: \f3expr\f1 is a
        !            89: \f2label_id\f1.  Leaves of patterns that are \f2label_id\f1s are called
        !            90: \f2labelled leaves\f1.
        !            91: In the first rule, both leaves of the pattern are labelled.
        !            92: .PP
        !            93: Twig assigns an integer to each node symbol and label symbol.  These
        !            94: integers are used by the twig pattern matcher as encodings for the
        !            95: symbols.
        !            96: As the matcher traverses the
        !            97: tree, a user supplied subroutine is called to provide an integer
        !            98: corresponding to each node.
        !            99: .SH
        !           100: Costs
        !           101: .PP
        !           102: To increase the flexibility of representing costs, the tree matcher
        !           103: views costs as an ADT.
        !           104: For example, costs may be represented as an integer or
        !           105: as a vector of integers with each element representing the cost of a specific
        !           106: resource.
        !           107: A cost ADT suitable for Twig must have the following four definitions:
        !           108: .IP
        !           109: \(bu \f3COST\f1 is a C type.
        !           110: Although the proper functioning of the tree matcher
        !           111: does not depend on the details of the \f3COST\f1 type, it must have
        !           112: the type information for storage allocation purposes.
        !           113: .IP
        !           114: \(bu
        !           115: \f3INFINITY\f1 is the maximum attainable cost value.  The matcher uses
        !           116: \f3INFINITY\f1 to initialize its data structures.
        !           117: .IP
        !           118: \(bu
        !           119: \f3DEFAULT_COST\f1 is the cost
        !           120: value returned by rules without a cost part.
        !           121: .IP
        !           122: \(bu
        !           123: \f3COSTLESS\f1 is a function of
        !           124: two cost values.  It must return true if and only if the first argument is
        !           125: less than the second.
        !           126: .sp 2ex
        !           127: .SH
        !           128: Trees
        !           129: .PP
        !           130: As with costs, Twig treats trees as an ADT.  Here, using an ADT is
        !           131: even more important because trees come in a variety of shapes and
        !           132: representations.
        !           133: Twig would be overly complicated if it had to
        !           134: know any more than the fundamental properties of trees.  Thus,
        !           135: twig treats trees as an acyclic directed
        !           136: graph of almost featureless nodes with one
        !           137: distinguished node, the root.  Each node has only one feature and that
        !           138: is an integer corresponding to the \f2node_id\f1s discussed above.
        !           139: To provide this
        !           140: view to Twig, the user must provide the following definitions and
        !           141: subroutines.
        !           142: .IP
        !           143: \(bu \f3NODE\f1 is the type of a node.  The actual
        !           144: details of
        !           145: the NODE are irrelevant and Twig uses this definition only for storage
        !           146: allocation and declaration purposes.
        !           147: .IP
        !           148: \(bu \f3NONODE\f1 is a constant of type \f3NODE\f1.  It is a distinguished
        !           149: value returned by the routines defined below to represent a null value.
        !           150: .IP
        !           151: \(bu
        !           152: \f3mtGetNodes#(r,n)# returns the #n#th child of \f2r\f1 where \f2r\f1
        !           153: is a \f3NODE\f1.  The
        !           154: leftmost child is \f3mtGetNodes\f2(r,1)\f1.  If #n>degree(r)#
        !           155: then the function should return \f3NONODE\f1.  Twig expects the
        !           156: expression \f3mtGetNodes\f2(\f3NONODE\f2, 0)\f1
        !           157: to denote the root node of
        !           158: the subject tree.
        !           159: .IP
        !           160: \(bu
        !           161: \f3mtValue\f2(r)\f1 returns the integer associated with \f2r\f1.
        !           162: .IP
        !           163: \(bu
        !           164: \f3mtSetNodes\f2(r,n,c)\f1 replaces the \f2n\f1th child of \f2r\f1 with
        !           165: \f2c\f1.  This routine may be used to replace whole subtrees with others.
        !           166: .sp 2ex
        !           167: .SH
        !           168: Pattern Matcher Operation
        !           169: .PP
        !           170: The pattern matcher operates in two phases: the costing phase and the
        !           171: execution phase.
        !           172: .PP
        !           173: In the costing phase, the matcher performs a preorder traversal of
        !           174: a subject tree and discovers matches from the bottom up.  At the same time, it
        !           175: builds a skeleton tree that is structurally isomorphic to the subject tree.
        !           176: When a match is discovered the cost clause of the pattern is invoked to
        !           177: calculate the cost.  Many patterns with different labels could match at any
        !           178: given node but only the lowest cost pattern for each label is recorded in
        !           179: the skeleton.
        !           180: .PP
        !           181: When a pattern is matched, its label is then used as input to the pattern
        !           182: matcher so that matching of patterns with labelled leaves can begin.
        !           183: This
        !           184: process
        !           185: is analogous to a reduce action in
        !           186: bottom up parsers.  In twig, multiple reductions are
        !           187: tracked.
        !           188: .PP
        !           189: The cost part of a rule can also assign a \f2mode\f1 to a match.  The
        !           190: \f2mode\f1 controls how action parts are to be executed.
        !           191: Actions parts of \f2defer\f1 mode matches are not executed until the
        !           192: execution phase.  \f2Rewrite\f1 mode matches cause the action part to
        !           193: be executed immediately during the costing phase to transform the
        !           194: matched subtree.  Once the rewrite mode action is executed, the costing
        !           195: phase continues by purging all information in the skeleton for the old
        !           196: subtree and then scanning the newly transformed subtree.
        !           197: \f2Rewrite\f1 actions are similar
        !           198: to actions that are invoked on a reduction in
        !           199: LR parsing.
        !           200: .PP
        !           201: In the case where multiple rewrite actions are possible the one with
        !           202: the lowest cost will be executed.  Furthermore, a rewrite action is
        !           203: considered only if its cost is lower than all the defer mode actions.
        !           204: Rewrite mode actions that are not executed are treated in the same
        !           205: manner as defer mode actions in the execution phase.
        !           206: .PP
        !           207: When the root of the subject tree is reached in the preorder
        !           208: traversal, the execution phase begins.  The lowest cost match is then
        !           209: chosen at the root and executed.  In this context, execution involves
        !           210: executing the actions of the labelled leaves before invoking the code
        !           211: in the current action.
        !           212: .SH
        !           213: Lexical Issues and Conventions
        !           214: .PP
        !           215: Currently the
        !           216: following are keywords of twig in no particular order:
        !           217: .DS
        !           218: .TS
        !           219: center;
        !           220: l l l.
        !           221: label  node    cost
        !           222: action prologue        insert
        !           223: .TE
        !           224: .DE
        !           225: They have special meanings and may not be used as
        !           226: identifiers.
        !           227: ;:(),= are special characters.  All blanks, tabs, formfeeds and
        !           228: newlines are ignored by twig but they may not appear inside
        !           229: identifiers and numbers.  Identifiers are nonempty strings
        !           230: made of letters, digits or underscores and starting with a letter.
        !           231: Numbers are nonempty string of digits.  Code fragments or action parts
        !           232: are enclosed in braces.  Inside code fragments, C lexical rules must
        !           233: be obeyed except that strings of the form $...$ that are not inside C
        !           234: strings are interpreted by twig.  In the following sections, $id$
        !           235: denotes an identifier; \f2int1\f1, \f2int2\f1 denotes numbers; \f2ccode\f1
        !           236: denotes C code fragments; ... indicates repetition of the previous
        !           237: item; [...] indicates that ... is optional.
        !           238: .PP
        !           239: The input to the Twig program will be referred to as the subject tree.
        !           240: .sp 2ex
        !           241: .SH
        !           242: Prologue and Inserts
        !           243: \f1
        !           244: .DS
        !           245: \f3prologue \f2ccode\f1;
        !           246: .DE
        !           247: signals to twig that \f2ccode\f1 should be inserted at the
        !           248: beginning of the output source file.  \f2Ccode\f1 should contain
        !           249: definitions relevant to the C code in
        !           250: rules that are defined later in the twig source file.
        !           251: .DS
        !           252: \f3insert \f2ccode\f1;
        !           253: .DE
        !           254: should cause \f2ccode\f1 to be placed into the source file.
        !           255: There can be multiple inserts and they will be placed into the source
        !           256: file
        !           257: in the order that they appear.
        !           258: .SH
        !           259: Declarations
        !           260: .PP
        !           261: All twig identifiers are declared before they are used.
        !           262: .DS
        !           263: \f3node\f1 \f2id\f1[(\f2int1\f1)] [= \f2int2\f1] ...;
        !           264: .DE
        !           265: A node declaration declares one or more identifier to be
        !           266: associated with nodes of the subject tree.  The identifiers are
        !           267: assigned numbers by twig but the user can overide the assigned number
        !           268: by specifying \f2int2\f1.  The degree of the node identifer, i.e. the
        !           269: number of children, is assumed to be fixed.  Normally, twig will
        !           270: deduce the degree when \f2id\f1 is used in a rule.  However, the user may
        !           271: explicitly give the degree by specifying \f2int1\f1.
        !           272: .DS
        !           273: \f3label\f2 id\f1 ...;
        !           274: .DE
        !           275: A label declaration indicates that the following $id$'s are to be used
        !           276: as labels of rules.
        !           277: .sp 2ex
        !           278: .SH
        !           279: Costs and Action code
        !           280: .PP
        !           281: Code fragments such as the \f2cost\f1 and \f2action\f1 clauses of a rule are
        !           282: specfied by enclosing C code in braces.  All legal C constructs are
        !           283: permitted in code fragments.  In addition, the following are provided
        !           284: for convenient access to the subject tree and internal data
        !           285: structures of the matcher.
        !           286: .sp 1ex
        !           287: .IP
        !           288: \(bu $%\f2n\f1$ denotes a pointer value to the matcher data
        !           289: structure for the $n$th labelled leaf.  Thus to access the cost value
        !           290: associated with that leaf, the notation $%\f2n\f1$\(->cost may be used.
        !           291: .IP
        !           292: \(bu
        !           293: $$ denotes a pointer value to the root of the subject
        !           294: tree.
        !           295: .IP
        !           296: \(bu
        !           297: $#{n sub 1}.{n sub 2}.{n sub 3}...{n sub {k-1}}.{n sub k}#$ denotes
        !           298: a pointer value to the ${n sub k}$th child of the $#{n sub {k-1}}#th$
        !           299: child of the
        !           300: $#{n sub {k-2}}#$th child of ... of the $#{n sub 1 }#$th child of the root of
        !           301: the subject tree.  Each $#{n sub i}#$ is a positive non-zero integer.
        !           302: .PP
        !           303: Some special constructs are available to code fragments in the cost
        !           304: part of the specification.  The
        !           305: statement "\f3ABORT;\f1" when encountered during the execution of
        !           306: the cost code, signals to the matcher that this pattern is to be
        !           307: rejected.  When a "\f3REWRITE;\f1" statement is encountered, control
        !           308: is returned to the matcher and the rule will become a \f2rewrite\f1
        !           309: mode match.  When the end of the cost code fragment is reached,
        !           310: control is returned to the matcher and the rule becomes a \f2defer\f1
        !           311: mode match.  Cost values are returned to the matcher by assigning to
        !           312: a variable named
        !           313: "\f3cost\f1" in the cost clause.  If no assignment is
        !           314: made to \f3cost\f1 then the returned cost will be
        !           315: \f3DEFAULT_COST\f1.
        !           316: .PP
        !           317: Action clauses are expected to return a new tree which will replace
        !           318: the subject tree.  This is done by returning using the standard C
        !           319: "\f3return\f2(new_tree);\f1" statement
        !           320: where \f2new_tree\f1 is of type
        !           321: \f3NODEPTR\f1.  When the end of the action clause is encountered, the
        !           322: matcher resumes execution and the subject tree is not replaced.
        !           323: .bp
        !           324: .SH
        !           325: An Example
        !           326: .PP
        !           327: The following are examples of twig rules that generate VAX code for
        !           328: the subtract instruction:
        !           329: .DS
        !           330: .na
        !           331: .nf
        !           332: prologue {
        !           333:        NODE gettermp();
        !           334: };
        !           335: node   long constant sub;
        !           336: label  operand temp;
        !           337: 
        !           338: operand: long;                 /* rule 1 */
        !           339: operand: constant;             /* rule 2 */
        !           340: operand: temp;                 /* rule 3 */
        !           341: temp:   operand;               /* rule 4 */
        !           342:        { cost = TEMP_COST+$%1$\(->cost; }
        !           343:        = {
        !           344:                NODE t = gettemp();
        !           345:                emit("mov", $$, t, 0);
        !           346:                return(t);
        !           347:        };
        !           348: 
        !           349: operand: sub(operand,opernad)  /* rule 5 */
        !           350:        { cost = $%1$\(->cost-$%2$\(->cost+SUB_COST; }
        !           351:        = {
        !           352:                NODE t = gettemp();
        !           353:                emit("sub", $1$, $2$, t, 0);
        !           354:                return(t);
        !           355:        };
        !           356: 
        !           357: temp:  sub(temp,constant)      /* rule 6 $*/
        !           358:        {
        !           359:                if(value($2$)==1)
        !           360:                        cost = $%1$\(->cost+DEC_COST;
        !           361:                else ABORT;
        !           362:        } = {
        !           363:                emit("dec", $1$, 0);
        !           364:                return($1$);
        !           365:        };
        !           366: .DE
        !           367: .IP
        !           368: \(bu
        !           369: Rules 3 and 4 form a loop.
        !           370: The potential loop: temp\(->operand\(->temp\(->operand... is
        !           371: broken
        !           372: by the matcher recognizing that the cost of the second match of temp
        !           373: does not cost less than the first match of temp.
        !           374: .IP
        !           375: \(bu In the cost clause of rule 5, the cost is the sum of the
        !           376: leaves plus the cost of the subtract instruction.
        !           377: The action clause emits code to add the two operands
        !           378: and leave the result in a temporary location.  The temporary is
        !           379: returned as a substitution for the subject tree.
        !           380: .IP
        !           381: \(bu Rule 6 handles a special case where the left operand is
        !           382: already in a temporary and the constant is one.  In this case, the
        !           383: temporary is directly decremented and returned as the new tree.
        !           384: .bp
        !           385: .DS C
        !           386: \f3Experimental Results\f1
        !           387: .DE
        !           388: .sp 2ex
        !           389: .PP
        !           390: A code generator for the VAX has been build using Twig and incorporated
        !           391: into the pcc2 compiler.  The following table summarizes the results
        !           392: for three benchmark programs.
        !           393: The compiler using the Twig code generator is abbreviated \f2tcc\f1.
        !           394: The times were obtained on a VAX-11/780
        !           395: running 4.2bsd UNIX.
        !           396: The first number is the time spent in the compiler.
        !           397: The parenthesized number is the time spent in the operating system.
        !           398: .TS
        !           399: center;
        !           400: c c c c c
        !           401: l n n n n.
        !           402:        lines   tcc     pcc2    improvement
        !           403: _
        !           404: grep.c 458     9.9(1.4)        11.4(0.9)       13%
        !           405: pmach.c        610     13.2(1.5)       13.5(0.6)       2%
        !           406: reader.c       1005    23.3(1.6)       31.2(0.9)       25%
        !           407: .TE
        !           408: .PP
        !           409: The running time for tcc is slightly
        !           410: faster than that of pcc2.
        !           411: However, The higher system times of tcc indicates that tcc place
        !           412: higher demands on the operating system.
        !           413: In the case of pmach.c, the total CPU time is actually more than that
        !           414: of pcc2's.
        !           415: .PP
        !           416: Twig requires more dynamic storage than pcc2.  For a tree, the dynamic
        !           417: storage requirement on the average is  number of nodes * 200
        !           418: bytes
        !           419: while the worst case is about number of nodes * 1000 bytes.
        !           420: However this storage is reclaimed and reused for every new tree.
        !           421: The larger system time
        !           422: is caused by calls to the runtime system for dynamic storage.
        !           423: .PP
        !           424: Writing and modifying tcc was quick.
        !           425: The basic
        !           426: VAX without indexed addressing mode can be described in about two weeks.
        !           427: This was done concurrently with debugging much of the table
        !           428: walker.  Adding indexed modes took
        !           429: only several hours once we were confident that the rest of the
        !           430: description was correct.
        !           431: .PP
        !           432: One reason for the ease of modifcation is that rules can be added
        !           433: independent of the other rules.  Looping can be completely ignored since
        !           434: dynamic programming eliminates that possiblity.
        !           435: Table generation was extremely fast or about 4.2 seconds for the
        !           436: VAX description.  Thus testing the description could be done quickly.
        !           437: .PP
        !           438: The tables were very small.  For the VAX, there were only 109 rules.
        !           439: This required 7.5K bytes of table space.
        !           440: The whole code generator is another 40K
        !           441: bytes.
        !           442: .SH
        !           443: Code Quality
        !           444: .PP
        !           445: The code generated by the Twig for the test programs were of the
        !           446: same quality as code generated by pcc2.
        !           447: However, Twig does better targeting.
        !           448: .DS
        !           449: tcc:
        !           450: .ti +4em
        !           451: addl3  -4(fp),-8(fp),-12(fp)
        !           452: .sp 1ex
        !           453: pcc2:
        !           454: .ti +4em
        !           455: addl3  -4(fp),-8(fp),r0
        !           456: .ti +4em
        !           457: movl   r0,-12(fp)
        !           458: .DE
        !           459: On the other hand, pcc2 handled temporary registers better
        !           460: and for an equivalent sequence of code, Twig may use
        !           461: more temporary registers.
        !           462: .DS
        !           463: tcc:
        !           464: .ti +4em
        !           465:        cvtbl   (r0),r1
        !           466: pcc2:
        !           467: .ti +4em
        !           468:        cvtbl   (r0),r0
        !           469: .DE
        !           470: This is actually a symptom of how temporary registers are allocated in tcc.
        !           471: Registers are allocated before code is emitted and thus any registers freed
        !           472: during code emissions will not be reused until the next code sequence.
        !           473: .SH
        !           474: Room for improvement
        !           475: .PP
        !           476: Currently Twig is slow compared to other table-driven systems such as
        !           477: [Henry] and [Ganapathi].  However, we have had less than one year of
        !           478: experience with Twig and we believe that its performance can be
        !           479: improved because
        !           480: .IP
        !           481: \(bu Unit productions such as
        !           482: .DS
        !           483: operand: temp
        !           484: .DE
        !           485: in the above example increases the running time of Twig
        !           486: since the closure operation for unit production is done at run-time.
        !           487: .IP
        !           488: \(bu Machine representations.  The current compact
        !           489: representation of the machine require linear searching except at the
        !           490: start state where the large branching factor compelled us to use an
        !           491: array scheme.  Using another representation would speed up the
        !           492: matcher.  For example, implementing the VAX description as an array is
        !           493: estimated to use about 50K bytes but would provide a significant
        !           494: performance improvement.
        !           495: .IP
        !           496: \(bu Twig performs many more procedure calls than pcc2.
        !           497: Every machine step requires at least one procedure call.  Contrast
        !           498: this to YACC where a machine step is performed in line.  Procedure
        !           499: calls on the VAX are expensive.

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.