-- file Pass4Xb.mesa
-- last written by Satterthwaite, February 24, 1983 3:32 pm
DIRECTORY
Alloc: TYPE USING [Notifier],
ComData: TYPE USING [interface, switches, typeCARDINAL, typeINTEGER, 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, BoolValue, Call,
CanonicalType, CaseDriver, CheckRange, CommonAttr, CommonProp,
CommonRep, ComparableType,ConstantInterval, Construct, DeclItem, Dollar,
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)
zone: UNCOUNTED ZONE ← NIL;
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: LONG POINTER TO 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: LONG POINTER TO VStack = zone.NEW[VStack[newLength]];
FOR i: INTEGER IN [0 .. vI) DO newStack[i] ← vStack[i] ENDLOOP;
zone.FREE[@vStack];
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 [scratchZone: UNCOUNTED ZONE] = {
zone ← scratchZone;
vStack ← zone.NEW[VStack[32]];
vI ← -1};
ExpReset: PUBLIC PROC = {
IF vStack # NIL THEN zone.FREE[@vStack];
zone ← 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.typeINTEGER,
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] = {
n1: RegCount = vStack[vI-1].nRegs;
n2: RegCount = vStack[vI].nRegs;
k: RegCount = RegsForType[tb[node].info];
RETURN [MIN[MAX[n1, n2+k], maxRegs]]};
ComputeIndexRegs: PUBLIC PROC [node: Tree.Index] RETURNS [RegCount] = {
n1: RegCount = vStack[vI-1].nRegs;
n2: RegCount = vStack[vI].nRegs;
k: RegCount = RegsForType[OperandType[tb[node].son[1]]];
RETURN [MIN[MAX[RegsForType[tb[node].info], n1, n2+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;
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: 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.typeINTEGER 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.typeINTEGER];
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: Tree.Link = IF (name = and) THEN passPtr.tTRUE ELSE passPtr.tFALSE;
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 son[1] = b THEN {
val ← son[2]; son[2] ← Tree.Null; attr ← vStack[vI-1].attr; nRegs ← n2}
ELSE {
val ← IF (name = and) THEN passPtr.tFALSE ELSE passPtr.tTRUE;
attr ← LiteralAttr[both]; nRegs ← 1};
FreeNode[node]}
ELSE {
attr ← BinaryAttr[];
IF 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 son[1] # passPtr.tFALSE 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};
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];
WITH val SELECT FROM
subtree => tb[index].info ← type;
ENDCASE;
val ← Exp[val, target]; attr ← VAttr[]; VPop[]}
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 => {
OPEN tb[node];
prop: Prop;
nRegs: RegCount;
son[1] ← RValue[son[1], 0, unsigned];
prop ← VProp[]; prop.noSelect ← FALSE;
nRegs ← MAX[RegsForType[info], VRegs[]]; VPop[];
son[2] ← Exp[son[2], target];
vStack[vI].nRegs ← nRegs;
vStack[vI].attr.prop ← CommonProp[vStack[vI].attr.prop, prop];
attr1 ← ~attr3 AND (checked OR dataPtr.switches['n]);
val ← expr};
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 tb[node].son[1] # passPtr.tFALSE
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];
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 => {
OPEN tb[node];
rep: Repr = RepForType[info];
son[1] ← Exp[son[1], rep]; vStack[vI].attr.rep ← rep;
IF P4.WordsForType[OperandType[son[1]]] # P4.WordsForType[info] THEN
name ← chop;
val ← expr};
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};
}.