
    <<Pass4Xb.mesa>>
        <<Copyright © 1985 by Xerox Corporation.  All rights reserved.>>
        <<Satterthwaite, April 11, 1986 10:18:54 am PST>>
        <<Paul Rovner, September 6, 1983 11:08 pm>>
        <<Russ Atkinson (RRA) March 6, 1985 10:59:00 pm PST>>

    DIRECTORY
        Alloc: TYPE USING [Notifier],
        ComData: TYPE USING [idCARDINAL, idINT, interface, switches, typeINT, typeSTRING],
        LiteralOps: TYPE USING [MasterString, FindLocalString, StringIndex, StringReference],
        Log: TYPE USING [ErrorTree, WarningTree],
        P4: TYPE USING [
            AddrOp, All, Assignment, Attr, BiasForType, BindCase, BindType, BoolTest, BoolValue,
            both, Call, CanonicalType, CaseDriver, checked, CheckRange, CommonAttr, CommonProp,
            CommonRep, ComparableType,ConstantInterval, Construct, currentLevel, DeclItem,
            Dollar, Dot, EmptyInterval, emptyProp, Extract, FoldExpr, fullProp, Index, Interval,
            IntToReal, ListCons, LiteralRep, long, LongToShort, MakeTreeLiteral, MarkString, maxRegs, 
            MiscXfer, Narrow, New, Nil, none, NormalizeRange, other, PadRecord, Prop, RegCount, 
            Reloc, RepForType, Repr, Rhs, RowConstruct, SeqIndex, ShortToLong, signed,
            StructuredLiteral, Substx, TreeLiteral, TreeLiteralValue, TypeExp, TypeOp, Union, 
            unsigned, voidAttr, voidProp, WordsForType, ZeroP],
        Pass4: TYPE USING [implicitAttr, implicitBias, implicitType, tFALSE, tTRUE],
        Symbols: TYPE USING [Base, ISEIndex, Type, CSEIndex, lG, typeANY, seType],
        SymbolOps: TYPE USING [
            Cardinality, ConstantId, EqTypes, FindExtension, NormalType, RCType, TypeForm,
            UnderType, WordsForType, XferMode],
        SymLiteralOps: TYPE USING [AtomRef, TextRef],
        Tree: TYPE USING [Base, Index, Link, Map, NodeName, Null, treeType],
        TreeOps: TYPE USING [
            FreeNode, GetHash, GetNode, IdentityMap, ListLength, MarkShared, OpName,
            PopTree, PushNode, PushTree, SetAttr, SetInfo, Shared, UpdateList];

    Pass4Xb: PROGRAM
        IMPORTS
            Log, LiteralOps, P4, SymbolOps, SymLiteralOps, TreeOps, dataPtr: ComData, passPtr: Pass4
        EXPORTS P4 = {
        OPEN SymbolOps, P4, TreeOps;

    <<pervasive definitions from Symbols>>

        ISEIndex: TYPE = Symbols.ISEIndex;
        Type: TYPE = Symbols.Type;
        CSEIndex: TYPE = Symbols.CSEIndex;


        tb: Tree.Base;    -- tree base address (local copy)
        seb: Symbols.Base;    -- se table base address (local copy)

        ExpBNotify: PUBLIC Alloc.Notifier = {
            <<called by allocator whenever table area is repacked>>
            tb _ base[Tree.treeType]; seb _ base[Symbols.seType]};


    <<intermediate result bookkeeping>>

        ValueDescriptor: TYPE = RECORD[
            bias: INTEGER,        -- bias in representation (scalars only)
            nRegs: RegCount,    -- estimate of register requirement
            attr: Attr];        -- synthesized attributes

        VStack: TYPE = RECORD [SEQUENCE length: NAT OF ValueDescriptor];
        vStack: REF VStack _ NIL;
        vI: INTEGER;            -- index into vStack

        VPush: PUBLIC PROC[bias: INTEGER, attr: Attr, nRegs: RegCount] = {
            vI _ vI + 1;
            WHILE vI >= vStack.length DO
                newLength: NAT = vStack.length + 16;
                newStack: REF VStack = NEW[VStack[newLength]];
                FOR i: INTEGER IN [0 .. vI) DO newStack[i] _ vStack[i] ENDLOOP;
                vStack _ newStack;
                ENDLOOP;
            vStack[vI] _ [bias:bias, attr:attr, nRegs:nRegs]};

        VPop: PUBLIC PROC = {IF vI < 0 THEN ERROR; vI _ vI-1};

        VBias: PUBLIC PROC RETURNS[INTEGER] = {RETURN[vStack[vI].bias]};

        VAttr: PUBLIC PROC RETURNS[Attr] = {RETURN[vStack[vI].attr]};

        VProp: PUBLIC PROC RETURNS[Prop] = {RETURN[vStack[vI].attr.prop]};

        VRep: PUBLIC PROC RETURNS[Repr] = {RETURN[vStack[vI].attr.rep]};

        VRegs: PUBLIC PROC RETURNS[RegCount] = {RETURN[vStack[vI].nRegs]};


        ExpInit: PUBLIC PROC = {
            vStack _ NEW[VStack[32]];
            vI _ -1};

        ExpReset: PUBLIC PROC = {
            IF vStack # NIL THEN vStack _ NIL};


        OperandType: PUBLIC PROC[t: Tree.Link] RETURNS[Type] = {
            RETURN[WITH t SELECT FROM
                symbol => seb[index].idType,
                literal => IF index.litTag = string THEN dataPtr.typeSTRING ELSE dataPtr.typeINT,
                subtree => IF t = Tree.Null THEN passPtr.implicitType ELSE tb[index].info,
                ENDCASE => Symbols.typeANY]};

        ForceType: PUBLIC PROC[t: Tree.Link, type: Type] RETURNS[Tree.Link] = {
            PushTree[t];
            IF (OpName[t] # mwconst AND OpName[t] # cast) OR Shared[t] THEN PushNode[cast, 1];
            SetInfo[type];  RETURN[PopTree[]]};

        ChopType: PROC[t: Tree.Link, type: Type] RETURNS[Tree.Link] = {
            PushTree[t]; PushNode[chop, 1]; SetInfo[type]; RETURN[PopTree[]]};


    <<literals>>

        MakeStructuredLiteral: PUBLIC PROC[val: WORD, type: Type] RETURNS[t: Tree.Link] = {
            t _ MakeTreeLiteral[val];
            SELECT TypeForm[type] FROM
                $basic, $enumerated, $subrange, $mode => NULL;
                ENDCASE => t _ ForceType[t, type];
            RETURN};

        LiteralAttr: PUBLIC PROC[rep: Repr] RETURNS[Attr] = {
            RETURN[[prop: fullProp, rep: rep]]};


    <<attribute accounting>>

        BinaryAttr: PROC RETURNS[Attr] = {
            RETURN[CommonAttr[vStack[vI-1].attr, vStack[vI].attr]]};

        MergeAttr: PROC[old: Attr] RETURNS[Attr] = {
            RETURN[CommonAttr[old, vStack[vI].attr]]};


    <<register accounting>>

        RegsForType: PUBLIC PROC[type: Type] RETURNS[RegCount] = {
            sei: CSEIndex = UnderType[type];
            n: LONG CARDINAL = IF seb[sei].mark4 THEN SymbolOps.WordsForType[sei] ELSE 0;
            RETURN[IF n = 2 THEN 2 ELSE 1]};

        ComputeRegs: PROC[node: Tree.Index] RETURNS[RegCount] = {
            k: RegCount = RegsForType[tb[node].info];
            RETURN[MIN[MAX[vStack[vI-1].nRegs, vStack[vI].nRegs+k], maxRegs]]};

        ComputeIndexRegs: PUBLIC PROC[node: Tree.Index] RETURNS[RegCount] = {
            k: RegCount = RegsForType[OperandType[tb[node].son[1]]];
            t: RegCount = RegsForType[tb[node].info];
            RETURN[MIN[MAX[t, vStack[vI-1].nRegs, vStack[vI].nRegs+k], maxRegs]]};

        AdjustRegs: PROC[node: Tree.Index, commuteOp: Tree.NodeName]
              RETURNS[RegCount] = {
            n1: RegCount = vStack[vI-1].nRegs;
            n2: RegCount = vStack[vI].nRegs;
            k: RegCount = RegsForType[tb[node].info];
            n: CARDINAL;
            IF n1 >= n2 THEN n _ n2 + k
            ELSE {
                v: ValueDescriptor;
                t: Tree.Link _ tb[node].son[1];
                tb[node].son[1] _ tb[node].son[2]; tb[node].son[2] _ t;
                tb[node].name _ commuteOp;
                v _ vStack[vI]; vStack[vI] _ vStack[vI-1]; vStack[vI-1] _ v;
                n _ n1 + k};
            RETURN[MIN[MAX[n1, n2, n], maxRegs]]};


    <<constant folding>>

        Fold: PROC[node: Tree.Index, rep: Repr] RETURNS[Tree.Link] = {
            fullRep: Repr = IF tb[node].attr2 THEN long + rep ELSE rep;
            RETURN[FoldExpr[node, fullRep]]};

        FoldedAttr: PROC[val: Tree.Link, rep: Repr] RETURNS[Attr] = {
            RETURN[LiteralAttr[LiteralRep[val, rep]]]};


    <<operators>>

        UMinus: PROC[node: Tree.Index] RETURNS[val: Tree.Link] = {
            rep: Repr;
            tb[node].son[1] _ Exp[tb[node].son[1], signed];  rep _ vStack[vI].attr.rep;
            SELECT rep FROM
                both => rep _ signed;
                none => {Log.WarningTree[mixedRepresentation, val]; rep _ signed};
                ENDCASE => NULL;
            IF ~StructuredLiteral[tb[node].son[1]] THEN {
                tb[node].attr3 _ TRUE; val _ [subtree[index: node]]}
            ELSE val _ Fold[node, rep];
            IF rep = unsigned THEN rep _ signed;
            vStack[vI].attr.rep _ rep;  vStack[vI].bias _ -VBias[];
            RETURN};

        Abs: PROC[node: Tree.Index] RETURNS[val: Tree.Link] = {
            rep: Repr;
            tb[node].son[1] _ RValue[tb[node].son[1], 0, signed];
            val _ [subtree[index: node]];  rep _ vStack[vI].attr.rep;
            SELECT rep FROM
                unsigned, both => {
                    Log.WarningTree[unsignedCompare, val];
                    val _ tb[node].son[1];  tb[node].son[1] _ Tree.Null;  FreeNode[node]};
                none => {Log.WarningTree[mixedRepresentation, val]; rep _ both};
                ENDCASE => {
                    tb[node].attr3 _ TRUE;
                    IF StructuredLiteral[tb[node].son[1]] THEN val _ Fold[node, rep];
                    IF rep # other THEN rep _ both};
            vStack[vI].attr.rep _ rep;
            RETURN};


        EnumOp: PROC[node: Tree.Index, target: Repr] RETURNS[Tree.Link] = {
            t: Tree.Link;
            type: Type = tb[node].info;
            nType: CSEIndex = NormalType[type];
            long: BOOL = (TypeForm[type] = $long);
            d: INTEGER _ 0;
            DO
                d _ IF tb[node].name = pred THEN d-1 ELSE d+1;
                t _ tb[node].son[1];  tb[node].son[1] _ Tree.Null; FreeNode[node];
                SELECT OpName[t] FROM
                    pred, succ => NULL;
                    ENDCASE => EXIT;
                node _ GetNode[t];
                ENDLOOP;
            PushTree[t];  PushTree[MakeTreeLiteral[ABS[d]]];
            IF long THEN {PushNode[lengthen, 1]; SetInfo[type]};
            PushNode[IF d < 0 THEN minus ELSE plus, 2];
            SetInfo[type]; SetAttr[1, FALSE]; SetAttr[2, long];
            RETURN[IF TypeForm[nType] = $enumerated
                THEN CheckRange[
                    RValue[PopTree[], BiasForType[nType], target], Cardinality[nType], nType]
                ELSE AddOp[GetNode[PopTree[]], target]]
            };


        ArithRep: PROC[rep, target: Repr] RETURNS[Repr] = {
            RETURN[SELECT rep FROM
                both, none =>
                    SELECT target FROM both, none, other => signed, ENDCASE => target,
                ENDCASE => rep]};

        BiasedFold: PROC[node: Tree.Index, rep: Repr] RETURNS[Tree.Link] = {
            fullRep: Repr = IF tb[node].attr2 THEN long + rep ELSE rep;
            tb[node].son[1] _ AdjustBias[tb[node].son[1], -vStack[vI-1].bias];
            tb[node].son[2] _ AdjustBias[tb[node].son[2], -vStack[vI].bias];
            RETURN[FoldExpr[node, fullRep]]};

        AddOp: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            op: Tree.NodeName = tb[node].name;
            type: Type = tb[node].info;
            bias, shift: INTEGER;
            attr: Attr;
            nRegs: RegCount;
            son[1] _ Exp[son[1], target];  son[2] _ Exp[son[2], target];
            val _ [subtree[index: node]]; 
            attr _ BinaryAttr[];
            SELECT attr.rep FROM
                both => attr.rep _ ArithRep[attr.rep, target];
                none =>
                    IF target = none THEN {Log.WarningTree[mixedRepresentation, val]; attr.rep _ both}
                    ELSE attr.rep _ IF target = both THEN signed ELSE target;
                ENDCASE => NULL;
            IF StructuredLiteral[son[1]] AND StructuredLiteral[son[2]] AND ~attr1 THEN {
                val _ BiasedFold[node, attr.rep];
                attr _ FoldedAttr[val, attr.rep];  bias _ 0;  nRegs _ RegsForType[type]}
            ELSE {
                nRegs _ IF op=plus THEN AdjustRegs[node, plus] ELSE ComputeRegs[node];
                bias _ vStack[vI-1].bias;  shift _ vStack[vI].bias;
                attr3 _ attr.rep # unsigned;
                SELECT TRUE FROM
                    TreeLiteral[son[2]] => {
                        val _ son[1];  shift _ shift + TreeLiteralValue[son[2]];
                        son[1] _ Tree.Null;  FreeNode[node]};
                    (op = plus AND TreeLiteral[son[1]]) => {
                        val _ son[2];  shift _ shift + TreeLiteralValue[son[1]];
                        son[2] _ Tree.Null;  FreeNode[node]};
                    ENDCASE;
                bias _ bias + (IF op=plus THEN shift ELSE -shift)};
            VPop[];  VPop[];  VPush[bias, attr, nRegs];
            IF ~EqTypes[type, dataPtr.typeINT] AND ~EqTypes[OperandType[val], type] THEN
                val _ ForceType[val, type];
            RETURN};

        Mult: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            attr: Attr;
            const1, const2: BOOL;
            v1, v2: WORD;
            bias: INTEGER;
            nRegs: RegCount;
            t: Tree.Link;
            son[1] _ Exp[son[1], target];  son[2] _ Exp[son[2], target];
            val _ [subtree[index: node]];
            attr _ BinaryAttr[];
            SELECT attr.rep FROM
                both => attr.rep _ ArithRep[attr.rep, target];
                none =>
                    IF target = none THEN {Log.WarningTree[mixedRepresentation, val]; attr.rep _ both}
                    ELSE attr.rep _ IF target = both THEN signed ELSE target;
                ENDCASE => NULL;
            IF StructuredLiteral[son[1]] AND StructuredLiteral[son[2]] AND ~attr1 THEN {
                nRegs _ RegsForType[info];
                val _ BiasedFold[node, attr.rep];  attr _ FoldedAttr[val, attr.rep];  bias _ 0}
            ELSE {
                nRegs _ AdjustRegs[node, times];
                const1 _ TreeLiteral[son[1]];  const2 _ TreeLiteral[son[2]];
                IF const1 OR ~const2 THEN son[1] _ AdjustBias[son[1], -vStack[vI-1].bias];
                IF ~const1 OR const2 THEN son[2] _ AdjustBias[son[2], -vStack[vI].bias];
                IF const1 THEN v1 _ TreeLiteralValue[son[1]];
                IF const2 THEN v2 _ TreeLiteralValue[son[2]];
                attr3 _ attr.rep # unsigned;
                bias _ SELECT TRUE FROM
                    const1 => v1*vStack[vI].bias,
                    const2 => vStack[vI-1].bias*v2,
                    ENDCASE => 0;
                IF StructuredLiteral[son[1]] -- AND ~const2 -- THEN {
                    t _ son[2]; son[2] _ son[1]; son[1] _ t};
                IF const1 OR const2 THEN
                    SELECT (IF const1 THEN v1 ELSE v2) FROM
                        0 => {val _ son[2]; son[2] _ Tree.Null; FreeNode[node]; attr.rep _ both};
                        1 => {
                            val _ son[1];  son[1] _ Tree.Null;  FreeNode[node];
                            attr _ vStack[IF const1 THEN vI ELSE vI-1].attr};
                        -1 => {
                            PushTree[son[1]];  son[1] _ Tree.Null;  FreeNode[node];
                            PushNode[uminus, 1];  SetInfo[dataPtr.idINT];
                            SetAttr[1, FALSE]; SetAttr[2, FALSE]; SetAttr[3, TRUE];
                            val _ PopTree[]};
                        ENDCASE};
            VPop[];  VPop[];  VPush[bias, attr, nRegs];
            RETURN};

        DivMod: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            attr: Attr;
            nRegs: RegCount;
            son[1] _ RValue[son[1], 0, target];  son[2] _ RValue[son[2], 0, target];
            val _ [subtree[index: node]];  attr _ BinaryAttr[];
            SELECT attr.rep FROM
                both => NULL;    -- preserved by div and mod
                none =>
                    IF target = none THEN {Log.ErrorTree[mixedRepresentation, val]; attr.rep _ both}
                    ELSE attr.rep _ target;
                ENDCASE => NULL;
            IF StructuredLiteral[son[1]] AND StructuredLiteral[son[2]] AND ~attr1 THEN {
                nRegs _ RegsForType[info]; val _ Fold[node, attr.rep]; attr _ FoldedAttr[val, attr.rep]}
            ELSE {
                nRegs _ ComputeRegs[node];
                attr3 _ CommonRep[attr.rep, unsigned] = none;
                IF name = div AND TreeLiteral[son[2]] THEN
                    SELECT TreeLiteralValue[son[2]] FROM
                        = 1 => {val _ son[1]; son[1] _ Tree.Null; FreeNode[node]};
                        >=2 => IF attr.rep = unsigned THEN attr.rep _ both;
                        ENDCASE};
            VPop[];  VPop[];  VPush[0, attr, nRegs];  RETURN};


        RelOp: PROC[node: Tree.Index] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            attr: Attr;
            rep1, rep2: Repr;
            nRegs: RegCount;
            d1, d2: INTEGER;
            uc: BOOL;
            ZeroWarning: ARRAY Tree.NodeName [relE..relLE] OF [0..2] = [0, 0, 2, 2, 1, 1];
            CommutedOp: ARRAY Tree.NodeName [relE..relLE] OF Tree.NodeName = [
                relE, relN, relG, relLE, relL, relGE];
            son[1] _ Exp[son[1], none];  rep1 _ VRep[];  d1 _ VBias[];
            son[2] _ Exp[son[2], none];  rep2 _ VRep[];  d2 _ VBias[];
            IF ~ComparableSons[node] THEN Log.ErrorTree[sizeClash, son[2]];
            val _ [subtree[index: node]];
            attr _ BinaryAttr[];
            IF attr.rep = none THEN
                SELECT name FROM
                    relE, relN => Log.WarningTree[mixedRepresentation, val];
                    ENDCASE => Log.ErrorTree[mixedRepresentation, val];
            SELECT name FROM
                relE, relN => uc _ FALSE;
                ENDCASE => {
                    IF rep1 = unsigned OR rep2 = unsigned THEN {
                        son[1] _ AdjustBias[son[1], -d1];  d1 _ 0;
                        son[2] _ AdjustBias[son[2], -d2];  d2 _ 0};
                    uc _ CommonRep[attr.rep, unsigned] # none};
            IF d1 # d2 THEN
                IF (~uc AND TreeLiteral[son[2]]) OR (uc AND d2 > d1) THEN
                    son[2] _ AdjustBias[son[2], d1-d2]
                ELSE son[1] _ AdjustBias[son[1], d2-d1];
            IF CommonRep[attr.rep, signed+other] = none THEN {
                SELECT ZeroWarning[name] FROM
                    1 => IF TreeLiteral[son[1]] AND TreeLiteralValue[son[1]] = 0 THEN GO TO warn;
                    2 => IF TreeLiteral[son[2]] AND TreeLiteralValue[son[2]] = 0 THEN GO TO warn;
                    ENDCASE;
                EXITS
                    warn => Log.WarningTree[unsignedCompare, val]};
            IF StructuredLiteral[son[1]] AND StructuredLiteral[son[2]] AND ~attr1 THEN {
                val _ Fold[node, attr.rep];  nRegs _ 1}
            ELSE {nRegs _ AdjustRegs[node, CommutedOp[name]]; attr3 _ attr.rep # unsigned};
            VPop[];  VPop[];
            attr.rep _ both;  VPush[0, attr, nRegs];
            RETURN};

        ComparableSons: PROC[node: Tree.Index] RETURNS[BOOL] = {
            OPEN tb[node];
            <<compatibility version>>
            type1: Type = OperandType[son[1]];
            n1: CARDINAL = P4.WordsForType[type1];
            type2: Type = OperandType[son[2]];
            n2: CARDINAL = P4.WordsForType[type2];
            IF n1 = 0 OR n2 = 0 THEN RETURN[FALSE];
            SELECT TRUE FROM
                (n1 = n2) => NULL;
                (TypeForm[type1] = $record AND TypeForm[type2] = $record) =>
                    IF n1 < n2 THEN     -- account for lost discrimination
                        son[2] _ ChopType[son[2], type1]
                    ELSE son[1] _ ChopType[son[1], type2];
                ENDCASE => RETURN[FALSE];
            RETURN[ComparableType[type1] OR ComparableType[type2]]};


        In: PROC[node: Tree.Index] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            bias: INTEGER;
            attr: Attr;
            nRegs: RegCount;
            void, const: BOOL;
            subNode: Tree.Index;
            son[1] _ Exp[son[1], none];  bias _ VBias[];  attr _ VAttr[];
            <<-- IF attr.rep = unsigned  THEN>>
                {son[1] _ AdjustBias[son[1], -bias]; bias _ 0};
            void _ FALSE;  val _ [subtree[index: node]];
            son[2] _ NormalizeRange[son[2]];  subNode _ GetNode[son[2]];
            IF (const _ Interval[subNode, bias, none].const) AND ~tb[node].attr2 THEN
                [] _ ConstantInterval[subNode ! EmptyInterval => {void _ TRUE; RESUME}];
            attr _ MergeAttr[attr];
            IF attr.rep = none THEN Log.ErrorTree[mixedRepresentation, val];
            tb[subNode].attr3 _ attr3 _ (attr.rep # unsigned);
            SELECT TRUE FROM
                void AND son[1] # Tree.Null => {
                    FreeNode[node]; val _ passPtr.tFALSE; nRegs _ 1};
                const AND StructuredLiteral[son[1]] AND ~attr1 => {
                    val _ Fold[node, attr.rep]; nRegs _ 1};
                ENDCASE => nRegs _ ComputeRegs[node];
            VPop[];  VPop[];  VPush[0, attr, nRegs];  RETURN};


        BoolOp: PROC[node: Tree.Index] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            b: BOOL = (name = and);
            n1, n2, nRegs: RegCount;
            attr: Attr;
            son[1] _ BoolValue[son[1]];  n1 _ VRegs[];
            son[2] _ BoolValue[son[2]];  n2 _ VRegs[];
            IF TreeLiteral[son[1]] THEN {
                IF BoolTest[son[1]] = b THEN {
                    val _ son[2]; son[2] _ Tree.Null; attr _ vStack[vI-1].attr; nRegs _ n2}
                ELSE {
                    val _ IF b THEN passPtr.tFALSE ELSE passPtr.tTRUE;
                    attr _ LiteralAttr[both];  nRegs _ 1};
                    FreeNode[node]}
            ELSE {
                attr _ BinaryAttr[];
                IF ~TreeLiteral[son[2]] OR BoolTest[son[2]] # b THEN {
                    val _ [subtree[index: node]]; nRegs _ MAX[n1, n2]}
                ELSE {val _ son[1]; son[1] _ Tree.Null; nRegs _ n1; FreeNode[node]}};
            VPop[];  VPop[];
            attr.rep _ both;  VPush[0, attr, nRegs];
            RETURN};


        CheckAlt: PROC[t: Tree.Link, target: Type] RETURNS[Tree.Link] = {
            type: Type = OperandType[t];
            IF P4.WordsForType[type] # P4.WordsForType[target] THEN
                IF TypeForm[type] = $record AND TypeForm[target] = $record THEN
                    t _ PadRecord[t, target]
                ELSE Log.ErrorTree[sizeClash, t];
            RETURN[t]};

        IfExp: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            select: Tree.Link;
            prop: Prop;
            attr: Attr;
            nRegs: RegCount;
            type: Type = info;
            bias: INTEGER = BiasForType[type];
            son[1] _ BoolValue[son[1]];  prop _ VProp[];  nRegs _ VRegs[];  VPop[];
            IF TreeLiteral[son[1]] THEN {
                IF BoolTest[son[1]] THEN {select _ son[2]; son[2] _ Tree.Null}
                ELSE {select _ son[3]; son[3] _ Tree.Null};
                FreeNode[node];
                val _ Exp[select, target]}
            ELSE {
                son[2] _ CheckAlt[RValue[son[2], bias, target], type];
                attr _ VAttr[]; nRegs _ MAX[VRegs[], nRegs];  VPop[];
                son[3] _ CheckAlt[RValue[son[3], bias, target], type];
                val _ [subtree[index: node]];
                attr _ MergeAttr[attr];
                IF attr.rep = none  THEN
                    IF target = none THEN {Log.WarningTree[mixedRepresentation, val]; attr.rep _ both}
                    ELSE attr.rep _ target;
                vStack[vI].attr _ attr;
                val _ [subtree[index: node]]};
            vStack[vI].attr.prop _ CommonProp[VProp[], prop];
            vStack[vI].nRegs _ MAX[VRegs[], nRegs];
            RETURN};

        CaseExp: PROC[node: Tree.Index, target: Repr, caseBias: INTEGER] RETURNS[val: Tree.Link] = {
            op: Tree.NodeName = tb[node].name;
            type: Type = tb[node].info;
            bias: INTEGER = BiasForType[type];
            attr: Attr _ [prop: voidProp, rep: both+other];
            const: BOOL _ TRUE;

            Selection: Tree.Map = {
                attr.prop _ CommonProp[attr.prop, passPtr.implicitAttr.prop];
                v _ CheckAlt[RValue[t, bias, target], type];
                attr _ MergeAttr[attr];  VPop[];
                const _ const AND StructuredLiteral[v];
                RETURN};

            val _ CaseDriver[node, Selection, caseBias];
            IF OpName[val] = op THEN {PushTree[val]; SetAttr[1, const]; val _ PopTree[]};
            IF attr.rep = none THEN
                IF target = none THEN {Log.WarningTree[mixedRepresentation, val]; attr.rep _ both}
                ELSE attr.rep _ target;
            VPush[bias, attr, maxRegs];
            RETURN};

        BindCaseExp: PROC[node: Tree.Index, target: Repr] RETURNS[Tree.Link] = {
            BoundExp: PROC[t: Tree.Link, labelBias: INTEGER] RETURNS[Tree.Link] = {
                RETURN[CaseExp[GetNode[t], target, labelBias]]};
            RETURN[BindCase[node, casex, BoundExp]]};

        BindTypeExp: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            type: Type = tb[node].info;
            bias: INTEGER = BiasForType[type];
            attr: Attr _ [prop: voidProp, rep: both+other];
            const: BOOL _ TRUE;

            Selection: Tree.Map = {
                attr.prop _ CommonProp[attr.prop, passPtr.implicitAttr.prop];
                v _ CheckAlt[RValue[t, bias, target], type];
                attr _ MergeAttr[attr];  VPop[];
                const _ const AND StructuredLiteral[v];
                RETURN};

            val _ BindType[node, Selection];
            IF attr.rep = none THEN
                IF target = none THEN {Log.WarningTree[mixedRepresentation, val]; attr.rep _ both}
                ELSE attr.rep _ target;
            VPush[bias, attr, maxRegs];
            RETURN};


        MinMax: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            const: BOOL _ TRUE;
            zeroTest: BOOL _ FALSE;
            attr: Attr _ [prop: voidProp, rep: both+other];
            nRegs: RegCount _ 0;
            k: RegCount = RegsForType[info];

            Item: Tree.Map = {
                v _ RValue[t, 0, target];
                IF ~StructuredLiteral[v] THEN const _ FALSE
                ELSE IF TreeLiteral[v] AND TreeLiteralValue[v] = 0 THEN zeroTest _ TRUE;
                attr _ MergeAttr[attr];
                nRegs _ MIN[MAX[nRegs, VRegs[]+k], maxRegs];  VPop[];  RETURN};

            IF ListLength[son[1]] = 1 THEN {
                val _ Exp[son[1], target]; son[1] _ Tree.Null; FreeNode[node]}
            ELSE {
                son[1] _ UpdateList[son[1], Item];  val _ [subtree[index: node]];
                IF zeroTest AND CommonRep[attr.rep, unsigned] # none THEN
                    Log.WarningTree[unsignedCompare, val];
                SELECT attr.rep FROM
                    both => attr.rep _ IF target = none THEN both ELSE target;
                    none =>
                        IF target = none THEN {Log.ErrorTree[mixedRepresentation, val]; attr.rep _ both}
                        ELSE attr.rep _ target;  
                    ENDCASE => NULL;
                IF const AND ~attr1 THEN {
                    val _ Fold[node, attr.rep]; attr _ FoldedAttr[val, attr.rep]; nRegs _ k}
                ELSE attr3 _ attr.rep # unsigned;
                VPush[0, attr, nRegs]};
            RETURN};


        Lengthen: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            attr: Attr;
            nRegs: RegCount;
            addr: BOOL;
            son[1] _ RValue[son[1], 0, IF target=both THEN unsigned ELSE target];  
            addr _ SELECT TypeForm[CanonicalType[OperandType[son[1]]]] FROM
                $ref, $arraydesc => TRUE,
                ENDCASE => FALSE;
            IF (attr _ VAttr[]).rep = none THEN {
                Log.ErrorTree[mixedRepresentation, son[1]]; attr.rep _ both};
            attr3 _ CommonRep[attr.rep, unsigned] = none;
            nRegs _ MAX[VRegs[], RegsForType[info]];
            IF TreeLiteral[son[1]] AND (~addr OR TreeLiteralValue[son[1]] = 0--NIL--) THEN {
                val _ ShortToLong[node, attr.rep]; attr.rep _ LiteralRep[val, attr.rep]}
            ELSE IF ZeroP[son[1]] THEN {
                val _ PadRecord[son[1], info];  son[1] _ Tree.Null; FreeNode[node];
                attr.rep _ LiteralRep[val, attr.rep]}
            ELSE {attr1 _ addr; val _ [subtree[index: node]]};
            VPop[];
            IF attr.rep = unsigned AND ~addr THEN attr.rep _ both;  VPush[0, attr, nRegs];
            RETURN};

        Shorten: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            attr: Attr;
            nRegs: RegCount;
            son[1] _ RValue[son[1], 0, IF target=both THEN unsigned ELSE target];  
            nRegs _ VRegs[];  attr _ VAttr[];  VPop[];
            IF CommonRep[target, unsigned] # none THEN attr.rep _ unsigned;
            attr1 _ checked OR dataPtr.switches['b];
            IF CommonRep[attr.rep, unsigned] = none THEN attr3 _ TRUE
            ELSE {attr3 _ FALSE; info _ dataPtr.idCARDINAL};
            IF ~StructuredLiteral[son[1]] THEN val _ [subtree[index: node]]
            ELSE {val _ LongToShort[node, attr.rep]; attr.rep _ LiteralRep[val, attr.rep]};
            VPush[0, attr, nRegs];  RETURN};


        OptTypeExp: PROC[t: Tree.Link] = {IF t # Tree.Null THEN TypeExp[t]};

        Loophole: PROC[node: Tree.Index, target: Repr] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            type: Type = info;
            rep: Repr = IF tb[node].son[2] # Tree.Null OR target = none
                THEN RepForType[type]
                ELSE target;
            son[1] _ Exp[son[1], rep];
            OptTypeExp[son[2]];
            IF P4.WordsForType[OperandType[son[1]]] # P4.WordsForType[type] THEN
                Log.ErrorTree[sizeClash, son[1]];
            IF RCType[type] # none THEN val _ [subtree[index: node]]
            ELSE {
                val _ ForceType[son[1], type];
                son[1] _ Tree.Null;  FreeNode[node]};
            vStack[vI].attr.rep _ rep;  RETURN};

        Cast: PROC[node: Tree.Index] RETURNS[Tree.Link] = {
            OPEN tb[node];
            type: Type = info;
            rep: Repr = RepForType[type];
            nw: CARDINAL = P4.WordsForType[type];
            son[1] _ Exp[son[1], rep];  vStack[vI].attr.rep _ rep;
            SELECT P4.WordsForType[OperandType[son[1]]] FROM
                < nw => name _ pad;
                > nw => name _ chop;
                ENDCASE;
            RETURN[[subtree[index: node]]]};

        UnaryCast: PROC[node: Tree.Index] RETURNS[val: Tree.Link] = {
            OPEN tb[node];
            IF StructuredLiteral[son[1]] THEN {
                val _ ForceType[son[1], info]; son[1] _ Tree.Null; FreeNode[node]}
            ELSE val _ [subtree[index: node]];
            RETURN};


        AdjustBias: PUBLIC PROC[t: Tree.Link, delta: INTEGER] RETURNS[Tree.Link] = {
            op: Tree.NodeName;
            type: Type;
            IF delta = 0 THEN RETURN[t];
            IF t = Tree.Null THEN passPtr.implicitBias _ passPtr.implicitBias + delta;
            type _ OperandType[t];
            IF TreeLiteral[t] THEN RETURN[MakeStructuredLiteral[TreeLiteralValue[t]-delta, type]];
            IF delta > 0 THEN op _ minus ELSE {op _ plus; delta _ -delta};
            PushTree[t];  PushTree[MakeTreeLiteral[delta]];
            PushNode[op, 2];  SetInfo[type];  SetAttr[1, FALSE];  SetAttr[2, FALSE];
            RETURN[PopTree[]]};

        RValue: PUBLIC PROC[exp: Tree.Link, bias: INTEGER, target: Repr]
              RETURNS[val: Tree.Link] = {
            d: INTEGER;
            val _ Exp[exp, target];  d _ bias - vStack[vI].bias;
            IF d # 0 THEN {val _ AdjustBias[val, d]; vStack[vI].bias _ bias};
            RETURN};


        Exp: PUBLIC PROC[exp: Tree.Link, target: Repr] RETURNS[val: Tree.Link] = {
            attr: Attr;
            WITH expr: exp SELECT FROM

                symbol => {
                    sei: ISEIndex = expr.index;
                    type: Type;
                    IF ~seb[sei].mark4 THEN DeclItem[Tree.Link[subtree[index: seb[sei].idValue]]];
                    type _ seb[sei].idType;  attr _ [prop: fullProp, rep: RepForType[type]];
                    attr.prop.immutable _ seb[sei].immutable;
                    IF ~seb[sei].constant THEN {attr.prop.noFreeVar _ FALSE; val _ expr}
                    ELSE
                        SELECT XferMode[type] FROM
                            proc, signal, error, program =>
                                IF ConstantId[sei] AND ~seb[sei].extended THEN
                                    val _ MakeStructuredLiteral[seb[sei].idValue, type]
                                ELSE {attr.prop.noFreeVar _ FALSE; val _ expr};
                            ENDCASE =>
                                IF seb[sei].extended THEN {
                                    val _ IdentityMap[FindExtension[sei].tree];
                                    attr.prop _ emptyProp;
                                    attr.prop.noFreeVar _ attr.prop.noXfer _ TRUE;    -- checked in DeclItem
                                    attr.prop.noAssign _ attr.prop.noSelect _ TRUE;    -- implied by noFreeVar
                                    WITH val SELECT FROM
                                        subtree => {
                                            IF tb[index].name = mwconst THEN attr.prop.immutable _ TRUE;
                                            tb[index].info _ type};
                                        ENDCASE}
                                ELSE {
                                    val _ MakeStructuredLiteral[seb[sei].idValue, type];
                                    attr _ FoldedAttr[val, attr.rep]};
                    VPush[BiasForType[type], attr, RegsForType[type]]};

                literal => {
                    WITH expr.index SELECT FROM
                        word => attr _ FoldedAttr[expr, unsigned];
                        string => {
                            LiteralOps.StringReference[sti];
                            MarkString[local: sti # LiteralOps.MasterString[sti]];
                            attr _ LiteralAttr[unsigned]};
                        ENDCASE => attr _ voidAttr;
                    VPush[0, attr, 1];  val _ expr};

                subtree =>
                    IF expr = Tree.Null THEN {
                        val _ Tree.Null; VPush[passPtr.implicitBias, passPtr.implicitAttr, maxRegs]}
                    ELSE {
                        node: Tree.Index = expr.index;
                        SELECT tb[node].name FROM

                            dot => val _ Dot[node, target];
                            dollar => val _ Dollar[node];

                            cdot => {
                                val _ Exp[tb[node].son[2], target];
                                tb[node].son[2] _ Tree.Null;  FreeNode[node]};

                            uparrow => {
                                type: Type = tb[node].info;
                                attr: Attr;
                                nRegs: RegCount;
                                tb[node].son[1] _ RValue[tb[node].son[1], 0, unsigned];
                                attr _ [prop: VProp[], rep: RepForType[type]];
                                attr.prop.noSelect _ attr.prop.immutable _ attr.prop.noFreeVar _ FALSE;
                                nRegs _ MAX[RegsForType[type], VRegs[]];  VPop[];
                                VPush[BiasForType[type], attr, nRegs];
                                tb[node].attr1 _ ~tb[node].attr3 AND (checked OR dataPtr.switches['n]);
                                val _ expr};

                            callx, portcallx, signalx, errorx, startx, joinx => val _ Call[node];
                            substx => val _ Substx[node];
                            index, dindex => val _ Index[node];
                            seqindex => val _ SeqIndex[node];
                            reloc => val _ Reloc[node];
                            construct => val _ Construct[node];
                            union => val _ Union[node];
                            rowcons => val _ RowConstruct[node];
                            all => val _ All[node];
                            uminus => val _ UMinus[node];
                            abs => val _ Abs[node];
                            pred, succ => val _ EnumOp[node, target];
                            plus, minus => val _ AddOp[node, target];
                            times => val _ Mult[node, target];
                            div, mod => val _ DivMod[node, target];
                            relE, relN, relL, relGE, relG, relLE => val _ RelOp[node];
                            in, notin => val _ In[node];

                            not => {
                                tb[node].son[1] _ BoolValue[tb[node].son[1]];
                                IF ~TreeLiteral[tb[node].son[1]] THEN val _ expr
                                ELSE {
                                    val _ IF BoolTest[tb[node].son[1]] THEN passPtr.tFALSE ELSE passPtr.tTRUE;
                                    FreeNode[node];  vStack[vI].nRegs _ 1}};

                            or, and => val _ BoolOp[node];
                            ifx => val _ IfExp[node, target];
                            casex => val _ CaseExp[node, target, 0];
                            bindx => val _ IF tb[node].attr3
                                THEN BindTypeExp[node, target]
                                ELSE BindCaseExp[node, target];
                            assignx => val _ Assignment[node];
                            extractx => val _ Extract[node];
                            min, max => val _ MinMax[node, target];

                            mwconst => {
                                VPush[0, FoldedAttr[expr, RepForType[tb[node].info]], RegsForType[tb[node].info]];
                                val _ expr};

                            clit => {val _ tb[node].son[1]; FreeNode[node]; VPush[0, LiteralAttr[both], 1]};

                            llit => {
                                IF currentLevel > Symbols.lG THEN
                                    WITH e: tb[node].son[1] SELECT FROM
                                        literal =>
                                            WITH e.index SELECT FROM
                                                string => sti _ LiteralOps.FindLocalString[sti];
                                                ENDCASE;
                                        ENDCASE;
                                val _ Exp[tb[node].son[1], none];
                                vStack[vI].attr.prop.noFreeVar _ FALSE;
                                tb[node].son[1] _ Tree.Null;  FreeNode[node]};

                            textlit => {
                                nRegs: RegCount = RegsForType[tb[node].info];
                                IF dataPtr.interface THEN val _ expr
                                ELSE {
                                    val _ SymLiteralOps.TextRef[
                                        LiteralOps.StringIndex[NARROW[tb[node].son[1], Tree.Link.literal].index]];
                                    FreeNode[node]};
                                VPush[0, LiteralAttr[unsigned], nRegs]};

                            atom => {
                                IF dataPtr.interface THEN val _ expr
                                ELSE {
                                    val _ SymLiteralOps.AtomRef[GetHash[tb[node].son[1]]];
                                    FreeNode[node]};
                                VPush[0, LiteralAttr[unsigned], 2]};

                            new => val _ New[node];
                            listcons => val _ ListCons[node];
                            nil => val _ Nil[node];
                            create, fork => val _ MiscXfer[node];

                            syserrorx => {
                                VPush[0, [prop: emptyProp, rep: RepForType[tb[node].info]], maxRegs];
                                val _ expr};

                            lengthen => val _ Lengthen[node, target];
                            shorten => val _ Shorten[node, target];

                            float => {
                                tb[node].son[1] _ RValue[tb[node].son[1], 0, signed];
                                IF StructuredLiteral[tb[node].son[1]] AND vStack[vI].attr.rep # unsigned THEN
                                    val _ IntToReal[node]
                                ELSE {val _ expr; vStack[vI].nRegs _ maxRegs};
                                vStack[vI].attr.rep _ other};

                            safen, proccheck => {
                                tb[node].son[1] _ Exp[tb[node].son[1], target]; val _ expr};
                            loophole => val _ Loophole[node, target];
                            cast => val _ Cast[node];

                            ord => {
                                tb[node].son[1] _ Exp[tb[node].son[1], target];
                                val _ UnaryCast[node]};

                            val => {
                                OPEN tb[node];
                                type: Type = info;
                                rep: Repr = RepForType[type];
                                subType: Type = OperandType[son[1]];
                                son[1] _ CheckRange[
                                    RValue[son[1], BiasForType[type], rep], Cardinality[type], subType];
                                IF P4.WordsForType[subType] # P4.WordsForType[type] THEN
                                    Log.ErrorTree[sizeClash, son[1]];
                                vStack[vI].attr.rep _ rep;
                                val _ UnaryCast[node]};

                            check => {
                                type: Type = tb[node].info;
                                OptTypeExp[tb[node].son[2]];
                                val _ Rhs[tb[node].son[1], type];
                                vStack[vI].attr.rep _ RepForType[type];
                                tb[node].son[1] _ Tree.Null;  FreeNode[node]};

                            narrow => val _ Narrow[node];

                            istype => {
                                OPEN tb[node];
                                attr: Attr;
                                son[1] _ RValue[son[1], 0, RepForType[OperandType[son[1]]]];
                                attr _ [prop: VProp[], rep: both];  VPop[];
                                TypeExp[son[2]];
                                IF attr2 OR attr3 THEN {val _ expr; VPush[0, attr, maxRegs]}
                                ELSE {FreeNode[node]; val _ passPtr.tTRUE; VPush[0, attr, 1]}};

                            openx => {
                                OPEN tb[node];
                                type: Type = OperandType[son[1]];
                                prop: Prop _ voidProp;
                                IF attr1 THEN {prop.noFreeVar _ prop.immutable _ FALSE; val _ son[1]}
                                ELSE {
                                    son[1] _ RValue[son[1], 0, none]; prop _ VProp[]; VPop[];
                                    IF Shared[son[1]] THEN    -- must generate an unshared node
                                        son[1] _ ForceType[son[1], type];
                                    MarkShared[son[1], TRUE];  attr1 _ TRUE;
                                    val _ expr};
                                VPush[0, [prop: prop, rep: other], RegsForType[type]]};

                            stringinit => {
                                attr: Attr;
                                MarkString[];
                                tb[node].son[2] _ P4.Rhs[tb[node].son[2], dataPtr.idCARDINAL];  
                                attr _ [prop: VProp[], rep: unsigned];  VPop[];  attr.prop.noFreeVar _ FALSE;
                                VPush[0, attr, maxRegs];  val _ expr};

                            size, first, last, typecode => val _ TypeOp[node];
                            apply => {VPush[0, voidAttr, 0]; val _ expr};

                            ENDCASE => val _ AddrOp[node]};

                ENDCASE => ERROR;
            RETURN};

        NeutralExp: PUBLIC PROC[exp: Tree.Link] RETURNS[val: Tree.Link] = {
            val _ RValue[exp, 0, none]; VPop[]; RETURN};

        }.