[Indigo]<Cedar>Compiler>Pass4Xb.Mesa!7

file Pass4Xb.mesa

last written by Satterthwaite, July 8, 1983 1:57 pm

last written by Paul Rovner, September 6, 1983 11:08 pm

DIRECTORY

Alloc: TYPE USING [Notifier],

ComData: TYPE USING [interface, switches, typeCARDINAL, typeINT, typeSTRING],

LiteralOps: TYPE USING [MasterString, FindLocalString, StringIndex, StringReference],

Log: TYPE USING [ErrorTree, WarningTree],

P4: TYPE USING [

Attr, voidAttr, Prop, emptyProp, fullProp, voidProp,

Repr, none, signed, unsigned, both, long, other, RegCount, maxRegs,

checked, currentLevel,

AddrOp, All, Assignment, BiasForType, BindCase, BindType, BoolTest, BoolValue,

Call, CanonicalType, CaseDriver, CheckRange, CommonAttr, CommonProp,

CommonRep, ComparableType,ConstantInterval, Construct, DeclItem, Dollar, Dot,

EmptyInterval, Extract, FoldExpr, Index, Interval, IntToReal, LiteralRep,

LongToShort, MakeTreeLiteral, MarkString, MiscXfer, Narrow, New, Nil,

NormalizeRange, PadRecord, Reloc, RepForType, Rhs, RowConstruct, SeqIndex,

ShortToLong, StructuredLiteral, Substx, TreeLiteral, TreeLiteralValue,

TypeExp, TypeOp, Union, WordsForType, ZeroP],

Pass4: TYPE USING [implicitAttr, implicitBias, implicitType, tFALSE, tTRUE],

Symbols: TYPE USING [Base, ISEIndex, CSEIndex, lG, typeANY, seType],

SymbolOps: TYPE USING [

Cardinality, ConstantId, 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;

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 [CSEIndex] = {

RETURN [WITH t SELECT FROM

symbol => UnderType[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: CSEIndex] 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: CSEIndex] RETURNS [Tree.Link] = {

PushTree[t]; PushNode[chop, 1]; SetInfo[type]; RETURN [PopTree[]]};

literals

MakeStructuredLiteral: PUBLIC PROC [val: WORD, type: CSEIndex]

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: CSEIndex] RETURNS [RegCount] = {

n: LONG CARDINAL = IF seb[type].mark4 THEN SymbolOps.WordsForType[type] 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.ErrorTree[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: CSEIndex = tb[node].info;

nType: CSEIndex = NormalType[type];

long: BOOL = (TypeForm[type] = long);

d: INTEGER ← 0;

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: CSEIndex = 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 type # dataPtr.typeINT AND 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.typeINT];

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: CSEIndex = OperandType[son[1]];

n1: CARDINAL = P4.WordsForType[type1];

type2: CSEIndex = 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: CSEIndex] RETURNS [Tree.Link] = {

type: CSEIndex = 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;

bias: INTEGER = BiasForType[info];

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], info];

attr ← VAttr[]; nRegs ← MAX[VRegs[], nRegs]; VPop[];

son[3] ← CheckAlt[RValue[son[3], bias, target], info];

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: CSEIndex = 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: CSEIndex = 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.typeCARDINAL};

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: CSEIndex = 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];

rep: Repr = RepForType[info];

nw: CARDINAL = P4.WordsForType[info];

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: CSEIndex;

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: CSEIndex;

IF ~seb[sei].mark4 THEN DeclItem[Tree.Link[subtree[index: seb[sei].idValue]]];

type ← UnderType[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 => {

OPEN tb[node];

attr: Attr;

nRegs: RegCount;

son[1] ← RValue[son[1], 0, unsigned];

attr ← [prop: VProp[], rep: RepForType[info]];

attr.prop.noSelect ← attr.prop.immutable ← FALSE;

nRegs ← MAX[RegsForType[info], VRegs[]]; VPop[];

VPush[BiasForType[info], attr, nRegs];

attr1 ← ~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;

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];

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];

rep: Repr = RepForType[info];

subType: CSEIndex = OperandType[son[1]];

son[1] ← CheckRange[

RValue[son[1], BiasForType[info], rep], Cardinality[info], subType];

IF P4.WordsForType[subType] # P4.WordsForType[info] THEN

Log.ErrorTree[sizeClash, son[1]];

vStack[vI].attr.rep ← rep;

val ← UnaryCast[node]};

check => {

OptTypeExp[tb[node].son[2]];

val ← Rhs[tb[node].son[1], tb[node].info];

vStack[vI].attr.rep ← RepForType[tb[node].info];

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: CSEIndex = 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.typeCARDINAL];

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};