-- file Pass4S.mesa
-- last modified by Satterthwaite, September 7, 1982 2:49 pm
-- last modified by Sweet, January 21, 1981  10:50 PM
-- last modified by Donahue, 10-Dec-81  9:14:17

DIRECTORY
  Alloc: TYPE USING [Notifier],
  ComData: TYPE USING [
    bodyIndex, definitionsOnly, globalFrameSize, monitored, stopping, switches, textIndex,
    typeBOOL, typeINT, typeLOCK],
  Log: TYPE USING [Error, ErrorSei, ErrorTree],
  LiteralOps: TYPE USING [Find, ResetLocalStrings],
  P4: TYPE USING [
    Repr, none, unsigned, both, other,
    AdjustBias, Assignment, BiasForType, BoolValue, Call, CheckBlock,
    CommonRep, ConstantInterval, Cover, DeclItem, DeclUpdate, Exp, Extract,
    Interval, LayoutBlock, LayoutGlobals, LayoutInterface, LayoutLocals,
    MakeArgRecord, MakeTreeLiteral, NeutralExp, NormalizeRange,
    OperandType, ProcessSymLiterals, RelTest, RepForType, Rhs, RValue,
    TreeLiteral, TreeLiteralValue, VBias, VPop, VRep, WordsForType,
    EmptyInterval],
  Pass4: TYPE USING [
    implicitBias, implicitRep, implicitType, lockNode, resident,
    resumeRecord, returnRecord, tFALSE, tTRUE],
  PrincOps: TYPE USING [StateVector, EPRange, localbase],
  Symbols: TYPE USING [
    Base, ISEIndex, CSEIndex, RecordSEIndex, CTXIndex, BTIndex, CBTIndex, ContextLevel,
    SENull, RecordSENull, CTXNull, RootBti, BTNull, lG, lL, typeANY, WordLength,
    seType, ctxType, bodyType],
  SymbolOps: TYPE USING [
    ArgRecord, Cardinality, ContextVariant, DelinkBti, NormalType, TransferTypes,
    TypeLink, UnderType],
  SymLiteralOps: TYPE USING [DescribeRefLits, DescribeTypes],
  Tree: TYPE USING [
    Base, Index, Link, Map, NodeName, Scan, Null, NullIndex, treeType],
  TreeOps: TYPE USING [
    FreeNode, FreeTree, GetNode, GetSe, ListHead, ListLength, MakeList, MakeNode,
    NthSon, OpName, PopTree, PushProperList, PushList, PushLit, PushNode, PushTree,
    ReverseScanList, ReverseUpdateList, ScanList, SetAttr, SetInfo, SetShared,
    UpdateList];

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

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

  StmtNotify: PUBLIC Alloc.Notifier = {
    -- called by allocator whenever table area is repacked
    tb ← base[Tree.treeType];
    seb ← base[seType];  ctxb ← base[ctxType];  bb ← base[bodyType]};

  Repr: TYPE = P4.Repr;
    none: Repr = P4.none;


 -- bodies and blocks

  currentLevel: PUBLIC ContextLevel;
  currentBody: BTIndex;
  checked: PUBLIC BOOLEAN;

  BodyList: PROC [firstBti: BTIndex] = {
    nextBti: BTIndex;
    FOR bti: BTIndex ← firstBti, nextBti UNTIL bti = BTNull DO
      nextBti ← IF bb[bti].link.which = parent THEN BTNull ELSE bb[bti].link.index;
      WITH bb[bti] SELECT FROM
	Callable =>
	  IF ~inline OR (dataPtr.definitionsOnly AND LocalBody[LOOPHOLE[bti]]) THEN
	    Body[LOOPHOLE[bti, CBTIndex]]
	  ELSE DelinkBti[bti];
	ENDCASE => BodyList[bb[bti].firstSon];
      ENDLOOP};

  LocalBody: PROC [bti: CBTIndex] RETURNS [BOOLEAN] = INLINE {
    sei: ISEIndex = bb[bti].id;
    RETURN [sei = SENull OR ctxb[seb[sei].idCtx].ctxType = simple]};


  Body: PUBLIC PROC [bti: CBTIndex] = {
    oldBodyIndex: CBTIndex = dataPtr.bodyIndex;
    oldLevel: ContextLevel = currentLevel;
    saveChecked: BOOLEAN = checked;
    saveIndex: CARDINAL = dataPtr.textIndex;
    saveCatchScope: BOOLEAN = catchScope;
    saveRecord: RecordSEIndex = passPtr.returnRecord;
    node: Tree.Index = WITH bb[bti].info SELECT FROM
	Internal => bodyTree,
	ENDCASE => ERROR;
    sei: CSEIndex = bb[bti].ioType;
    base, bound: CARDINAL;
    initTree: Tree.Link;
    catchScope ← FALSE;
    dataPtr.bodyIndex ← currentBody ← bti;  dataPtr.textIndex ← bb[bti].sourceIndex;
    currentLevel ← IF bti = RootBti THEN lG ELSE bb[bti].level;
    checked ← tb[node].attr1;
    IF dataPtr.definitionsOnly AND bb[bti].level > lL
      THEN Log.ErrorSei[nonDefinition, bb[bti].id];
    passPtr.returnRecord ← TransferTypes[bb[bti].ioType].typeOut;
    [] ← LiteralOps.ResetLocalStrings[];
    bb[bti].hints.noStrings ← TRUE;	-- see MarkString, below
    IF tb[node].son[4] # Tree.Null THEN {
      tb[node].son[4] ← Exp[tb[node].son[4], none]; VPop[]};
    tb[node].son[1] ← UpdateList[tb[node].son[1], OpenItem];
    [init: initTree, decls: tb[node].son[2]] ← ScanDecls[tb[node].son[2]];
    IF bti = RootBti THEN {
      fragments: BOOLEAN ←
        (SymLiteralOps.DescribeTypes[].length + SymLiteralOps.DescribeRefLits[].length) # 0;
      dataPtr.globalFrameSize ←
        (LayoutGlobals[bti, dataPtr.stopping, fragments] + (WordLength-1))/WordLength;
      IF bb[bti].type # RecordSENull THEN
        seb[bb[bti].type].length ← dataPtr.globalFrameSize*WordLength;
      ProcessSymLiterals[];
      base ← PrincOps.localbase*WordLength;
      IF dataPtr.monitored AND tb[passPtr.lockNode].attr1 THEN {
	PushTree[tb[passPtr.lockNode].son[2]];
	PushLit[LiteralOps.Find[100000b]];  PushNode[cast, 1];
	SetInfo[dataPtr.typeLOCK];
	PushNode[assign, 2];  SetAttr[1, TRUE];
	initTree ← Prefix[PopTree[], initTree]}}
    ELSE {
      base ← LayoutLocals[bti];
      IF bb[bti].type # RecordSENull THEN seb[bb[bti].type].length ← base;
      IF bb[bti].firstSon # BTNull THEN
        initTree ← Prefix[BodyInitList[bb[bti].firstSon], initTree]};
    IF bb[bti].type # RecordSENull THEN seb[bb[bti].type].mark4 ← TRUE;
    tb[node].son[3] ← UpdateList[tb[node].son[3], Stmt];
    bound ← AssignSubBlocks[bti, base];
    WITH bb[bti].info SELECT FROM
      Internal => {
	frameSize ← (bound + (WordLength-1))/WordLength;
	thread ← LiteralOps.ResetLocalStrings[]};
      ENDCASE;
    bb[bti].resident ← passPtr.resident;
    IF bb[bti].firstSon # BTNull THEN BodyList[bb[bti].firstSon];
    tb[node].son[1] ← ReverseUpdateList[tb[node].son[1], CloseItem];
    tb[node].son[2] ← Prefix[initTree, UpdateList[tb[node].son[2], DeclUpdate]];
    IF dataPtr.definitionsOnly AND bti = RootBti THEN {
      n: CARDINAL = LayoutInterface[bti];
      WITH t: seb[bb[bti].ioType] SELECT FROM
	definition => t.nGfi ← IF n=0 THEN 1 ELSE (n-1)/PrincOps.EPRange + 1;
	ENDCASE};
    catchScope ← saveCatchScope;
    currentBody ← dataPtr.bodyIndex ← oldBodyIndex;
    currentLevel ← oldLevel;  checked ← saveChecked;
    dataPtr.textIndex ← saveIndex;  passPtr.returnRecord ← saveRecord};

  MarkString: PUBLIC PROC [local: BOOLEAN] = {
    bb[IF local THEN dataPtr.bodyIndex ELSE RootBti].hints.noStrings ← FALSE};
     
     
  ScanDecls: PROC [t: Tree.Link] RETURNS [init, decls: Tree.Link] = {
    IF OpName[t] = initlist THEN {
      node: Tree.Index = GetNode[t];
      init ← UpdateList[tb[node].son[1], Stmt];  tb[node].son[1] ← Tree.Null;
      decls ← tb[node].son[2];  tb[node].son[2] ← Tree.Null;
      FreeNode[node]}
    ELSE {init ← Tree.Null; decls ← t};
    ScanList[decls, DeclItem]; RETURN};

  Prefix: PROC [first, rest: Tree.Link] RETURNS [Tree.Link] = {
    SELECT TRUE FROM
      (first = Tree.Null) => RETURN [rest];
      (rest = Tree.Null) => RETURN [first];
      ENDCASE => {PushTree[first]; PushTree[rest]; RETURN [MakeList[2]]}};

  BodyInitList: PROC [firstBti: BTIndex] RETURNS [Tree.Link] = {
    bti: BTIndex ← firstBti;
    n: CARDINAL ← 0;
    IF bti # BTNull THEN
      DO
	WITH body: bb[bti] SELECT FROM
	  Callable =>
	    IF ~body.inline THEN {PushNode[procinit, 0]; SetInfo[bti]; n ← n+1};
	  ENDCASE => NULL;
	IF bb[bti].link.which = parent THEN EXIT;
	bti ← bb[bti].link.index;
	ENDLOOP;
    RETURN [MakeList[n]]};

  AssignSubBlocks: PROC [rootBti: BTIndex, base: CARDINAL] RETURNS [bound: CARDINAL] = {
    level: ContextLevel = bb[rootBti].level;
    bti: BTIndex;
    bound ← base;
    IF (bti ← bb[rootBti].firstSon) # BTNull THEN
      DO
	SELECT bb[bti].kind FROM
	  Other =>
	    IF bb[bti].level = level THEN {
	      length: CARDINAL = AssignBlock[bti, base];
	      bound ← MAX[length, bound]};
	  ENDCASE => NULL;
	IF bb[bti].link.which = parent THEN EXIT;
	bti ← bb[bti].link.index;
	ENDLOOP;
    RETURN};


  Subst: PUBLIC PROC [node: Tree.Index] RETURNS [Tree.Link] = {
    OPEN tb[node];
    saveRecord: RecordSEIndex = passPtr.returnRecord;
    saveChecked: BOOLEAN = checked;
    son[1] ← NeutralExp[son[1]];
    passPtr.returnRecord ← TransferTypes[OperandType[son[1]]].typeOut;
    IF ~attr3 THEN checked ← attr1;
    son[2] ← UpdateList[son[2], Stmt];
    checked ← saveChecked;  passPtr.returnRecord ← saveRecord;
    RETURN [[subtree[index: node]]]};


  Scope: PROC [node: Tree.Index, item: Tree.Map] RETURNS [Tree.Link] = {
    OPEN tb[node];
    bti: BTIndex = info;
    saveIndex: CARDINAL = dataPtr.textIndex;
    oldBodyIndex: BTIndex = currentBody;
    oldLevel: ContextLevel = currentLevel;
    initTree: Tree.Link;
    dataPtr.textIndex ← bb[bti].sourceIndex;
    currentBody ← bti;  currentLevel ← bb[bti].level;
    [init: initTree, decls: son[1]] ← ScanDecls[son[1]];
    IF bb[bti].type # RecordSENull THEN seb[bb[bti].type].mark4 ← TRUE;
    CheckBlock[bti];
    son[2] ← UpdateList[son[2], item];
    son[1] ← Prefix[initTree, UpdateList[son[1], DeclUpdate]];
    IF catchScope THEN catchBound ← MAX[AssignBlock[bti, catchBase], catchBound];
    currentBody ← oldBodyIndex;  currentLevel ← oldLevel;
    dataPtr.textIndex ← saveIndex;
    RETURN [[subtree[index: node]]]};

  AssignBlock: PROC [bti: BTIndex, base: CARDINAL] RETURNS [bound: CARDINAL] = {
    node: Tree.Index;
    newBase: CARDINAL = LayoutBlock[bti, base];
    initTree: Tree.Link = IF bb[bti].firstSon # BTNull
	THEN BodyInitList[bb[bti].firstSon]
	ELSE Tree.Null;
    IF bb[bti].type # RecordSENull THEN seb[bb[bti].type].length ← newBase;
    bound ← AssignSubBlocks[bti, newBase];
    WITH bb[bti].info SELECT FROM
      Internal => {frameSize ← (bound + (WordLength-1))/WordLength; node ← bodyTree};
      ENDCASE => NULL;
    IF initTree # Tree.Null THEN tb[node].son[1] ← Prefix[initTree, tb[node].son[1]];
    RETURN};


 -- main dispatch

  Stmt: PROC [stmt: Tree.Link] RETURNS [val: Tree.Link] = {
    node: Tree.Index;
    saveIndex: CARDINAL = dataPtr.textIndex;
    val ← stmt;		-- the default case
    WITH stmt SELECT FROM
      subtree => {
	node ← index;
	IF node # Tree.NullIndex THEN {
	  OPEN tb[node];
	  dataPtr.textIndex ← info;
	  SELECT name FROM

	    assign => {val ← Assignment[node]; VPop[]};
	    extract => val ← ExtractStmt[node];

	    call, portcall, signal, error, xerror, start, join => {val ← Call[node]; VPop[]};
	    subst => val ← Subst[node];

	    block => {
	      saveChecked: BOOLEAN = checked;
	      checked ← tb[node].attr1;  val ← Scope[node, Stmt];
	      checked ← saveChecked};

	    if => val ← IfStmt[node];
	    case => val ← CaseDriver[node, Stmt, 0];
	    bind =>
	      val ← IF attr3 THEN BindType[node, Stmt] ELSE BindCase[node, case, BindStmt];

	    do => val ← DoStmt[node];

	    return, result => Return[node, passPtr.returnRecord];
	    resume => Return[node, passPtr.resumeRecord];

	    label => {son[1] ← Stmt[son[1]]; son[2] ← UpdateList[son[2], Stmt]};

	    open => {
	      son[1] ← UpdateList[son[1], OpenItem];
	      son[2] ← UpdateList[son[2], Stmt];
	      son[1] ← ReverseUpdateList[son[1], CloseItem]};

	    checked => {
	      saveChecked: BOOLEAN = checked;
	      checked ← attr1;  son[1] ← Stmt[son[1]];
	      checked ← saveChecked};

	    enable => {CatchPhrase[son[1]]; son[2] ← Stmt[son[2]]};
	    catchmark => son[1] ← Stmt[son[1]];

	    lock => {son[1] ← UpdateList[son[1], Stmt]; son[2] ← Exp[son[2], none]; VPop[]};
	    notify, broadcast, unlock => {son[1] ← Exp[son[1], none]; VPop[]};
	    wait => {
	      son[1] ← Exp[son[1], none];  VPop[];
	      son[2] ← Exp[son[2], none];  VPop[];
	      IF nSons > 2 THEN CatchNest[son[3]]};

	    restart => {son[1] ← NeutralExp[son[1]]; IF nSons > 2 THEN CatchNest[son[3]]};

	    dst, lst, lstf => {
	      son[1] ← Exp[son[1], none];
	      IF WordsForType[OperandType[son[1]]] < SIZE[PrincOps.StateVector] THEN
	        Log.ErrorTree[sizeClash, son[1]];
	      VPop[]};

	    goto, exit, loop, syserror, reject, continue, retry, stop, null => NULL;
	    free => val ← Free[node];

	    apply => NULL;
	    item => son[2] ← Stmt[son[2]];
	    list => val ← UpdateList[stmt, Stmt];

	    ENDCASE => Log.Error[unimplemented]}};
      ENDCASE => ERROR;
    dataPtr.textIndex ← saveIndex;  RETURN};


 -- extraction

  ExtractStmt: PROC [node: Tree.Index] RETURNS [val: Tree.Link] = {
    subNode: Tree.Index = GetNode[tb[node].son[1]];
    rType: RecordSEIndex = tb[subNode].info;
    IF rType # Symbols.RecordSENull THEN {val ← Extract[node]; VPop[]}
    ELSE {
      val ← Stmt[tb[node].son[2]];  tb[node].son[2] ← Tree.Null;
      WITH val SELECT FROM subtree => tb[index].info ← tb[node].info ENDCASE;
      FreeNode[node]};
    RETURN};


 -- return
 
  Return: PROC [node: Tree.Index, type: RecordSEIndex] = {
    IF tb[node].attr3 AND type # RecordSENull THEN {
      tb[node].son[1] ← Rhs[tb[node].son[1], type]; VPop[]}
    ELSE tb[node].son[1] ← MakeArgRecord[type, tb[node].son[1]]};
      

 -- conditionals

  IfStmt: PROC [node: Tree.Index] RETURNS [val: Tree.Link] = {
    OPEN tb[node];
    son[1] ← BoolValue[son[1]];  VPop[];
    son[2] ← Stmt[son[2]];  son[3] ← Stmt[son[3]];
    IF ~TreeLiteral[son[1]] THEN val ← Tree.Link[subtree[index: node]]
    ELSE {
      IF son[1] # passPtr.tFALSE THEN {val ← son[2]; son[2] ← Tree.Null}
      ELSE {val ← son[3]; son[3] ← Tree.Null};
      FreeNode[node]};
    RETURN};

 
  BindStmt: PROC [t: Tree.Link, labelBias: INTEGER] RETURNS [Tree.Link] = {
    node: Tree.Index = GetNode[t];
    RETURN [CaseDriver[GetNode[t], Stmt, labelBias]]};


  -- drivers for processing selections

  BindType: PUBLIC PROC [node: Tree.Index, eval: Tree.Map] RETURNS [Tree.Link] = {
    OPEN tb[node];
    saveType: CSEIndex = passPtr.implicitType;
    saveBias: INTEGER = passPtr.implicitBias;
    saveRep: Repr = passPtr.implicitRep;

    Item: Tree.Map = {RETURN [Scope[GetNode[t], eval]]};

    subNode: Tree.Index ← GetNode[son[1]];
    type: CSEIndex = OperandType[tb[subNode].son[2]];
    PushTree[RValue[tb[subNode].son[2], BiasForType[type], RepForType[type]]];
    passPtr.implicitType ← type;
    passPtr.implicitRep ← VRep[];  passPtr.implicitBias ← VBias[];  VPop[];
    tb[subNode].son[2] ← Tree.Null;
    PushTree[UpdateList[son[3], Item]];  son[3] ← Tree.Null;
    PushTree[eval[son[4]]];  son[4] ← Tree.Null;
    PushNode[name, 3];  SetInfo[info];  SetAttr[1, attr1];  SetAttr[2, attr2];
    FreeNode[node];
    passPtr.implicitRep ← saveRep;  passPtr.implicitBias ← saveBias;
    passPtr.implicitType ← saveType;
    RETURN [PopTree[]]};

  BindCase: PUBLIC PROC [
	node: Tree.Index,
	op: Tree.NodeName,
	eval: PROC [Tree.Link, INTEGER] RETURNS [Tree.Link]]
      RETURNS [val: Tree.Link] = {
    OPEN tb[node];
    labelBias: INTEGER = TagBias[BoundType[son[1]], TestCtx[ListHead[son[3]]]];
    subNode: Tree.Index;
    PushTree[son[2]];  son[2] ← Tree.Null;
    PushTree[son[3]];  son[3] ← Tree.Null;
    PushTree[son[4]];  son[4] ← Tree.Null;
    PushTree[OpenItem[son[1]]];  son[1] ← Tree.Null;
    PushNode[op, 4];  SetInfo[info];  SetAttr[1, FALSE];  SetAttr[3, attr3];
    val ← eval[PopTree[], labelBias];  subNode ← GetNode[val];
    tb[subNode].son[4] ← CloseItem[tb[subNode].son[4]];
    FreeNode[node];
    RETURN};


  BoundType: PROC [base: Tree.Link] RETURNS [CSEIndex] = INLINE {
    RETURN [DerefType[OperandType[NthSon[base, 2]]]]};

  TestCtx: PROC [item: Tree.Link] RETURNS [CTXIndex] = INLINE {
    RETURN [IF item = Tree.Null
      THEN CTXNull
      ELSE seb[GetSe[NthSon[ListHead[NthSon[item, 1]], 2]]].idCtx]};
    
  TagBias: PROC [rType: CSEIndex, testCtx: CTXIndex] RETURNS [INTEGER] = {
    FOR subType: CSEIndex ← rType, UnderType[TypeLink[subType]]
     WHILE subType # SENull DO
      WITH t: seb[subType] SELECT FROM
        record =>
	  IF t.hints.variant THEN {
	    sei: ISEIndex = ContextVariant[t.fieldCtx];
	    uType: CSEIndex = UnderType[seb[sei].idType];
	    WITH u: seb[uType] SELECT FROM
	      union =>
		IF u.caseCtx = testCtx OR testCtx = CTXNull THEN
		  RETURN [BiasForType[UnderType[seb[u.tagSei].idType]]];
	      ENDCASE};
	ENDCASE => EXIT;
      ENDLOOP;
    ERROR};


  CaseDriver: PUBLIC PROC [node: Tree.Index, selection: Tree.Map, labelBias: INTEGER]
      RETURNS [val: Tree.Link] = {
    OPEN tb[node];
    type: CSEIndex = OperandType[son[1]];
    son[1] ← Exp[son[1], none];
    IF type = dataPtr.typeBOOL AND attr1 AND TreeLiteral[son[1]] THEN {

      CaseItem: Tree.Scan = {
	subNode: Tree.Index = GetNode[t];
	started: BOOLEAN;

	PushTest: Tree.Scan = {
	  tNode: Tree.Index = GetNode[t];
	  PushTree[tb[tNode].son[2]];  tb[tNode].son[2] ← Tree.Null;
	  IF son[1] = passPtr.tFALSE THEN PushNode[not, 1];
	  IF started THEN PushNode[or, 2];
	  started ← TRUE;  RETURN};

	PushTree[tb[subNode].son[2]];  tb[subNode].son[2] ← Tree.Null;
	started ← FALSE;  ScanList[tb[subNode].son[1], PushTest];
	IF selection = Stmt THEN {PushNode[if, -3]; SetInfo[tb[subNode].info]}
	ELSE {PushNode[ifx, -3]; SetInfo[tb[node].info]};
	RETURN};

      son[1] ← AdjustBias[son[1], -VBias[]];  VPop[];
      PushTree[son[3]];  son[3] ← Tree.Null;
      ReverseScanList[son[2], CaseItem];
      FreeNode[node];
      val ← selection[PopTree[]]}
    ELSE {
      nSons: CARDINAL = ListLength[son[2]];
      i, j, first, last, next, newSons: CARDINAL;
      min, max: INTEGER;
      minTree, maxTree: Tree.Link;
      rep: Repr;
      subNode, listNode: Tree.Index;
      switchable, copying: BOOLEAN;
      multiword: BOOLEAN = WordsForType[type] # 1;
      count: CARDINAL;

      SwitchValue: Tree.Map = {
	val: Tree.Link;
	tNode: Tree.Index = GetNode[t];
	val ← tb[tNode].son[2] ← RValue[tb[tNode].son[2], passPtr.implicitBias, rep];
	VPop[];
	IF count = 0 THEN {first ← i; minTree ← maxTree ← val}
	ELSE {
	  subRep: Repr = (SELECT rep FROM other, none => unsigned, ENDCASE => rep);
	  IF RelTest[val, minTree, relL, subRep] THEN minTree ← val;
	  IF RelTest[val, maxTree, relG, subRep] THEN maxTree ← val};
	count ← count + 1;
	RETURN [t]};

      saveType: CSEIndex = passPtr.implicitType;
      saveBias: INTEGER = passPtr.implicitBias;
      saveRep: Repr = passPtr.implicitRep;
      passPtr.implicitType ← type;
      passPtr.implicitBias ← VBias[] - labelBias;
      passPtr.implicitRep ← rep ← VRep[];  VPop[];
      newSons ← nSons;
      i ← next ← 1;  copying ← FALSE;  listNode ← GetNode[son[2]];
      UNTIL i > nSons DO
	WHILE i <= nSons DO
	  subNode ← GetNode[tb[listNode].son[i]];
	  IF tb[subNode].attr1 AND ~multiword THEN EXIT;
	  tb[subNode].son[1] ← UpdateList[tb[subNode].son[1], NeutralExp];
	  tb[subNode].son[2] ← selection[tb[subNode].son[2]];
	  i ← i+1;
	  ENDLOOP;
	switchable ← FALSE;  count ← 0;
	WHILE i <= nSons DO  -- N.B. implicitbias is never changed by this loop
	  subNode ← GetNode[tb[listNode].son[i]];
	  IF ~tb[subNode].attr1 OR multiword THEN EXIT;
	  tb[subNode].son[1] ← UpdateList[tb[subNode].son[1], SwitchValue];
	  tb[subNode].son[2] ← selection[tb[subNode].son[2]];
	  switchable ← TRUE;  last ← i;  i ← i+1;
	  ENDLOOP;
	IF switchable
	 AND SwitchWorthy[count,
	      (max←TreeLiteralValue[maxTree])-(min←TreeLiteralValue[minTree])] THEN {
	  copying ← TRUE;
	  FOR j IN [next .. first) DO PushTree[tb[listNode].son[j]] ENDLOOP;
	  PushTree[AdjustBias[Tree.Null, min]];
	  PushTree[MakeTreeLiteral[max-min+1]];
	  FOR j IN [first .. last] DO PushTree[SwitchTree[tb[listNode].son[j], min]] ENDLOOP;
	  PushProperList[last-first+1];
	  PushNode[caseswitch, 3];
	   next ← last+1;  newSons ← newSons - (last-first)};
	ENDLOOP;
      IF copying THEN {
	FOR j IN [next .. nSons] DO PushTree[tb[listNode].son[j]] ENDLOOP;
	PushProperList[newSons];  son[2] ← PopTree[]};
      son[3] ← selection[son[3]];
      val ← Tree.Link[subtree[index: node]];
      passPtr.implicitRep ← saveRep;  passPtr.implicitBias ← saveBias;
      passPtr.implicitType ← saveType};
    RETURN};

  -- auxiliary routines for CaseDriver

    SwitchWorthy: PROC [entries, delta: CARDINAL] RETURNS [BOOLEAN] = {
      -- the decision function for using a switch
      RETURN [delta < 77777b AND delta+6 < 3*entries]};

    SwitchTree: PROC [t: Tree.Link, offset: INTEGER] RETURNS [Tree.Link] = {
      node: Tree.Index = GetNode[t];
      count: CARDINAL;

      PushSwitchEntry: Tree.Scan = {
	subNode: Tree.Index = GetNode[t];
	count ← count+1;
	PushTree[MakeTreeLiteral[TreeLiteralValue[tb[subNode].son[2]]-offset]]};

      count ← 0;  ScanList[tb[node].son[1], PushSwitchEntry];
      PushList[count];  PushTree[tb[node].son[2]];
      tb[node].son[2] ← Tree.Null;  FreeNode[node];
      RETURN [MakeNode[casetest, 2]]};


 -- iterative statements

  DoStmt: PROC [node: Tree.Index] RETURNS [val: Tree.Link] = {
    OPEN tb[node];
    void: BOOLEAN ← FALSE;
    bti: BTIndex ← BTNull;
    IF son[1] # Tree.Null THEN [bti, void] ← ForClause[GetNode[son[1]]];
    IF son[2] # Tree.Null THEN {
      son[2] ← BoolValue[son[2]];  VPop[];
      SELECT son[2] FROM
	passPtr.tTRUE => son[2] ← FreeTree[son[2]];
	passPtr.tFALSE => void ← TRUE;
	ENDCASE};
    son[3] ← UpdateList[son[3], OpenItem];
    son[4] ← UpdateList[son[4], Stmt];
    son[5] ← UpdateList[son[5], Stmt];
    son[6] ← UpdateList[son[6], Stmt];
    son[3] ← ReverseUpdateList[son[3], CloseItem];
    IF catchScope AND bti # BTNull THEN
      catchBound ← MAX[AssignBlock[bti, catchBase], catchBound];
    IF ~void THEN val ← [subtree[index: node]]
    ELSE {val ← son[6]; son[6] ← Tree.Null; FreeNode[node]};
    RETURN};

  ForClause: PROC [node: Tree.Index] RETURNS [bti: BTIndex, void: BOOLEAN] = {
    idBias: INTEGER;
    idRep, rep: Repr;
    idType, type1, type2: CSEIndex;
    iNode: Tree.Index;
    range: CARDINAL;
    void ← FALSE;  bti ← tb[node].info;
    IF tb[node].son[1] = Tree.Null THEN {
      idType ← dataPtr.typeINT; idBias ← 0; idRep ← both}
    ELSE {
      IF OpName[tb[node].son[1]] = decl THEN {
	subNode: Tree.Index ← GetNode[tb[node].son[1]];
	ScanList[tb[node].son[1], DeclItem];
	tb[node].son[1] ← tb[subNode].son[1];
	tb[subNode].son[1] ← Tree.Null;  FreeNode[subNode]};
      idType ← OperandType[tb[node].son[1]];
      tb[node].son[1] ← Exp[tb[node].son[1], none];
      idBias ← VBias[];  idRep ← VRep[]; VPop[]};
    SELECT tb[node].name FROM
      forseq => {
	tb[node].son[2] ← Rhs[tb[node].son[2], idType];  VPop[];
	tb[node].son[3] ← Rhs[tb[node].son[3], idType];  VPop[]};
      upthru, downthru => {
	tb[node].son[2] ← NormalizeRange[tb[node].son[2]];
	iNode ← GetNode[tb[node].son[2]];
	type1 ← OperandType[tb[iNode].son[1]];
	type2 ← OperandType[tb[iNode].son[2]];
	tb[node].attr1 ← Interval[iNode, idBias, idRep].const AND seb[idType].typeTag # long;
	IF tb[node].attr1 AND ~tb[iNode].attr2 THEN
	  [] ← ConstantInterval[iNode ! EmptyInterval => {void ← TRUE; RESUME}];
	rep ← CommonRep[VRep[], idRep];
	tb[iNode].attr3 ← rep # unsigned;  VPop[];
	IF rep = none OR (rep = unsigned AND idBias > 0) THEN
	  Log.ErrorTree[mixedRepresentation, tb[node].son[2]];
	SELECT TRUE FROM
	  void => NULL;
	  (WordsForType[idType] = 0) => Log.ErrorTree[sizeClash, tb[node].son[1]];
	  (idType # dataPtr.typeINT) AND (idType # typeANY) => {
	    OPEN tb[iNode];
	    range ← Cardinality[idType];
	    IF (checked OR dataPtr.switches['b]) AND range # 0 THEN
	      IF (Cover[idType, idRep, type1, rep] # full AND RangeTest[son[1], range] # in)
	       OR
		 (Cover[idType, idRep, type2, rep] # full AND RangeTest[son[2], range] # in) THEN
		tb[node].son[3] ← MakeTreeLiteral[range];
	    IF name = intCC AND type2 # dataPtr.typeINT THEN
	      IF TreeLiteral[son[1]] AND
	       INTEGER[TreeLiteralValue[son[1]]]+idBias <= BiasForType[type2] THEN
	        tb[node].attr1 ← TRUE;
	    IF tb[node].attr1 AND range # 0 THEN {	-- nonvoid interval
	      IF (name=intCC OR name=intCO) AND RangeTest[son[1], range] = out THEN
	        Log.ErrorTree[boundsFault, son[1]];
	      IF (name=intCC OR name=intOC) AND RangeTest[son[2], range] = out THEN
	        Log.ErrorTree[boundsFault, son[2]]}};
	  ENDCASE};
      ENDCASE => ERROR;
    RETURN};

  RangeTest: PROC [t: Tree.Link, range: CARDINAL] RETURNS [{in, out, unknown}] = {
    RETURN [IF TreeLiteral[t]
	THEN IF TreeLiteralValue[t] < range THEN in ELSE out
	ELSE unknown]};


 -- free

  Free: PROC [node: Tree.Index] RETURNS [Tree.Link] = {
    OPEN tb[node];
    vType, pType: CSEIndex;
    IF son[1] # Tree.Null THEN {son[1] ← Exp[son[1], none]; VPop[]};
    son[2] ← NeutralExp[son[2]];
    vType ← OperandType[son[2]];  pType ← DerefType[vType];
    IF OpName[son[2]] = addr THEN {
      subNode: Tree.Index = GetNode[son[2]];
      son[2] ← tb[subNode].son[1];  tb[subNode].son[1] ← Tree.Null;  FreeNode[subNode]}
    ELSE {
      PushTree[son[2]];  PushNode[uparrow, 1];  SetInfo[pType];
      SetAttr[1, checked OR dataPtr.switches['n]];
      SetAttr[2, seb[vType].typeTag = long];
      son[2] ← PopTree[]};
    tb[node].son[3] ← MakeTreeLiteral[WordsForType[DerefType[pType]]];
    IF nSons > 3 THEN CatchNest[son[4]];
    RETURN [[subtree[index: node]]]};


 -- basing

  DerefType: PROC [type: CSEIndex] RETURNS [CSEIndex] = {
    subType: CSEIndex = NormalType[type];
    RETURN [WITH seb[subType] SELECT FROM
      ref => UnderType[refType],
      ENDCASE => type]};

  OpenItem: Tree.Map = {
    node: Tree.Index = GetNode[t];
    IF OpName[tb[node].son[2]] # openx THEN v ← Tree.Null
    ELSE {v ← NeutralExp[tb[node].son[2]]; tb[node].son[2] ← Tree.Null};
    FreeNode[node];
    RETURN};

  CloseItem: Tree.Map = {
    node: Tree.Index;
    IF bb[currentBody].firstSon # BTNull OR OpName[t] # openx THEN v ← t
    ELSE {
      SetShared[t, FALSE];  node ← GetNode[t];
      v ← tb[node].son[1];  tb[node].son[1] ← Tree.Null;  FreeNode[node]};
    RETURN};


 -- catch phrases

  CatchFrameBase: CARDINAL = (PrincOps.localbase+1)*WordLength;
  catchScope: BOOLEAN;
  catchBase: CARDINAL;
  catchBound: CARDINAL;

  CatchNest: PUBLIC PROC [t: Tree.Link] = {
    IF t # Tree.Null THEN CatchPhrase[t]};

  CatchPhrase: PROC [t: Tree.Link] = {
    node: Tree.Index = GetNode[t];
    saveCatchScope: BOOLEAN = catchScope;
    saveCatchBase: CARDINAL = catchBase;
    saveCatchBound: CARDINAL = catchBound;
    bound: CARDINAL;

    CatchTest: Tree.Map = {
      PushTree[Tree.Null];  PushTree[Exp[t, none]];  VPop[];
      PushNode[relE, 2];  SetInfo[dataPtr.typeBOOL];
      RETURN [PopTree[]]};

    CatchItem: Tree.Scan = {
      node: Tree.Index = GetNode[t];
      type: CSEIndex = tb[node].info;
      saveRecord: RecordSEIndex = passPtr.resumeRecord;
      tb[node].son[1] ← UpdateList[tb[node].son[1], CatchTest];
      catchBase ← CatchFrameBase;
      IF type = SENull THEN passPtr.resumeRecord ← RecordSENull
      ELSE
	WITH t: seb[type] SELECT FROM
	  transfer => {
	    passPtr.resumeRecord ← ArgRecord[t.typeOut];
	    catchBase ← catchBase +
	      ArgLength[ArgRecord[t.typeIn]] + ArgLength[passPtr.resumeRecord]};
	  ENDCASE => ERROR;
      catchBound ← catchBase;
      tb[node].son[2] ← Stmt[tb[node].son[2]];
      bound ← MAX[bound, catchBound];
      passPtr.resumeRecord ← saveRecord};

    catchScope ← TRUE;  currentLevel ← currentLevel + 1;
    bound ← CatchFrameBase + WordLength;
    ScanList[tb[node].son[1], CatchItem];
    IF tb[node].nSons > 1 THEN {
      catchBound ← catchBase ← CatchFrameBase;
      tb[node].son[2] ← Stmt[tb[node].son[2]];
      bound ← MAX[bound, catchBound]};
    tb[node].info ← (bound + (WordLength-1))/WordLength;
    catchBase ← saveCatchBase;  catchBound ← saveCatchBound;
    currentLevel ← currentLevel - 1;  catchScope ← saveCatchScope};

  ArgLength: PROC [rSei: RecordSEIndex] RETURNS [CARDINAL] = {
    RETURN [IF rSei = SENull THEN 0 ELSE seb[rSei].length]};

  }.