{

                          MODULE 17


                Variable Reference Generation





 16.1  A Delayed Code Generation Strategy

 The analyser uses the code  generation  interface  to  signal  the
 required  program  actions as a sequence of 'post fix' operations.
 With a simple stack machine as target, these calls  can  output  a
 corresponding  sequence of stack manipulation code directly.  With
 this simple strategy, however, difficulties arise in  the  genera-
 tion of efficient code for optimised P-machines, and in the imple-
 mentation of run-time checks.

 In the Model Compiler, therefore, the interface calls made by  the
 analyser construct tree representations of each variable reference
 and expression evaluation required, delaying actual  code  genera-
 tion  until  the  context  of the reference or evaluation is esta-
 blished.

 This delayed code generation is achieved using a stack, pointed to
 by  the  variable  TopStackEntry, to simulate the evaluation-stack
 contents of a simple stack machine during execution of the  opera-
 tions  implied by the interface call sequence.  Each operand value
 or variable reference on this stack is represented by a record  of
 type StackNode.

 In the case of operand values this record is the root of a tree of
 stacknodes defining the computation required to obtain the operand
 value.  Each internal node in the tree is  of  variant  Operation,
 and   denotes  a  value-producing  operation  whose  operands  are
 represented  by  appended  subtrees.   Each   leaf   node,   which
 represents  a primary operand, is of variant Reference, denoting a
 variable access, or of variant  AConstant,  denoting  an  explicit
 constant  value.   (The  variants  Address  and Result are used to
 describe references and operands after evaluation  code  has  been
 generated.)

 The generation of stack nodes of variants Operation and  AConstant
 is  described in Chapter 17.  In this chapter the form and genera-
 tion of variable references is considered.

 16.2  Stacked References

 A stack node representing a variable reference is the  head  of  a
 list  of  such  nodes  (linked  by  the  field  AccessList),  each
 representing an access step.  The list holds the access  steps  in
 reverse  order,  i.e.  the head record represents the last step in
 the access sequence.  The  tail  record  defines  a  base  address
 within  the  run-time data stack from which all subsequent address
 calculations derive.  Each access record then implies  calculation
 from  this base address of a word or part-word address, using some
 or all of the following:

 (a)  indirection, as indicated by the field Indirect;

 (b)  indexing by a list of index expression values, pointed to  by
      the  field  Indices for word references or by the field Index
      for part-word references;

 (c)  further word address adjustment by the field Adjustment.

 Multiple access records are generated when the  necessary  address
 calculation  cannot be achieved by a single step defined as above,
 or when access checks must be applied at a particular step of  the
 address  calculation.  The access to every file variable occurring
 in a file buffer reference, to  every  dynamic  variable,  and  to
 every  record  variable  in  a tag- or variant-field reference, is
 tagged as 'vulnerable' to ensure that  a  separate  access  record
 remains  available  for  the  addition  of subsequently determined
 access checks.

 The access checks applicable to the (intermediate) address implied
 by  any  access  record,  are  represented  as a list of ancillary
 checks, pointed to by the field CheckList  of  the  record.   Each
 entry  on  the list is a record of type AncillaryRecord whose tag-
 field WhichOp defines one of the following ancillary check  opera-
 tions.

 (1)  WhichOp=CheckSelector: access to a field of a  tagged  record
      variant is checked by verifying that the SeclectorField asso-
      ciated with the variant-part holds the SelectorValue  associ-
      ated  with  the  variant.  This check is appended by the pro-
      cedure CheckTaggedVariant.

 (2)  WhichOp=SetSelector: access to a field of an untagged  record
      variant  is  accompanied  by implicit variant (re) selection.
      The TagValue associated with the variant, and the record base
      address  are  passed  as parameters to an internally compiled
      selector procedure which implements the variant  (re)  selec-
      tion.  The mechanisms invlolved in this process are discussed
      in detail in Section 26.3. This check is appended by the pro-
      cedure CheckUntaggedVariant.

 (3)  WhichOp=CheckIfActive: the 'undefined' check for a  tag-field
      is  implemented  by  checking  a 'variant-active' flag in the
      control word of the record. The field  SelectorLevel  identi-
      fies  the bit position of this flag. The control word is dis-
      cussed in detail in Section 26.3.  This check is appended  by
      the procedure UndefinedVariableCheck.

 (4)  WhichOp=SetALock: a reference must be protected to  guarentee
      its  existence  for  the duration of a with-statement body or
      procedure activation.  LockWord contains the  word-offset  of
      the  lock relative to the base-address defined by the current
      access list entry, and LockBit specifies the lock  bit  posi-
      tion  within  the lock-word. Referene protection is discussed
      in detail in Section 18.3.  This check is  appended  by  pro-
      cedure ExtendReferences.

 (5)  WhichOp=CheckIfNew: a dynamic variable used as  a  factor  is
      checked  for creation by the extended form of new. This check
      is appended by the procedure TailoredFactorCheck.

 Subsequent sections of this chapter define basic utilities for the
 creation  and  maintenance of stacked references and implement the
 interface procedures defined in Section 5.5.



 16.3  Ancillary Check List Maintenance

 The following procedures enable the creation  and  maintenance  of
 the  ancillary  check lists attached to stack nodes of form refer-
 ence:

                                                                     }

program VariableRef;

#include "globals.x"
#include "expeval.pf"
#include "semantics.pf

procedure StartAncillaries(var List: AncillaryList);
visible;

  begin
{    List.FirstEntry := nil;
    List.LastEntry := nil		}
  end { startancillaries };

procedure AppendEntry(var List: AncillaryList;
                      NewEntry: AncillaryEntry);
visible;

  begin
{    with List do
      begin
        if FirstEntry = nil
        then FirstEntry := NewEntry else LastEntry^.Next := NewEntry;
        LastEntry := NewEntry
      end								}
  end { appendentry };

function CheckCount(List: AncillaryList): Scalar;
visible;

  var { Entry: AncillaryEntry;		}
      Count: Scalar;


  begin
    Count := 0;
{    Entry := List.FirstEntry;
    while Entry <> nil do
    begin
      Count := Count + 1;
      Entry := Entry^.Next
    end;				}
    CheckCount := Count
  end { checkcount };

{

 16.4  Evaluation Stack Maintenance

 The following procedures enable creation and  maintenance  of  the
 evaluation stack itself:

                                                                     }

procedure GetEntry(var Entry: StackEntry);
visible;

  begin
    new(Entry);
    with Entry^ do
      begin
        NextNode := nil;
        RunError := 0;
        Vulnerable := false;
        StartAncillaries(CheckList);
        DataRep := DefaultRepresentation;
        DataBytes := 0
      end
  end { getentry };

procedure FreeEntry(Entry: StackEntry);
visible;

  var NextWord, ThisWord: WordEntry;

  begin
    with Entry^ do
      if Kind = AConstant
      then
        with TheConst do
          if Kind in [SetValue, StringValue]
          then
            begin
              if Kind = SetValue
              then NextWord := Setval else NextWord := Stringval;
              while NextWord <> nil do
                begin
                  ThisWord := NextWord;
                  NextWord := ThisWord^.Next;
                  dispose(ThisWord)
                end
            end;
    dispose(Entry)
  end { freeentry };

procedure Push(Entry: StackEntry);
visible;

  begin
    Entry^.NextNode := TopStackEntry;
    TopStackEntry := Entry
  end { push };

procedure Pop(var Entry: StackEntry);
visible;

  begin
    Entry := TopStackEntry;
    TopStackEntry := Entry^.NextNode
  end { pop };

procedure InitStack;
visible;

  begin TopStackEntry := nil end;

{

 16.5  Reference Creation and Manipulation

 The following utility procedures simplify creation of  maintenance
 of (access lists of) reference records.

                                                                     }

procedure GetReference(var NewEntry: StackEntry);
visible;

  begin
    GetEntry(NewEntry);
    with NewEntry^ do
      begin
        Kind := Reference;
        BaseAddress := DftAddress;
        Adjustment := 0;
        Level := 0;
        Indirect := false;
        AccessList := nil;
        Class := VarRef;
        PartOfWord := false;
        Indexed := false
      end
  end { getreference };

procedure ReferencePartWord(var Entry: StackEntry);

  begin
    with Entry^ do
      begin
        PartOfWord := true;
        BitOffset := 0;
        BitSize := 0;
        OnByteBoundary := false;
        IndexedPartWord := false
      end
  end { refpartword };

procedure PushNewAccess(var Entry: StackEntry; ForAPartWord: Boolean);
visible;

  var NewEntry: StackEntry;

  begin
    GetReference(NewEntry);
    with NewEntry^ do
      begin
        AccessList := Entry;
        if ForAPartWord then ReferencePartWord(NewEntry)
      end;
    Entry := NewEntry
  end { pushnewaccess };

procedure PreserveAccess(var Entry: StackEntry);

  begin PushNewAccess(Entry, Entry^.PartOfWord) end;

procedure PartWordReference(var Entry: StackEntry);

  begin
    with Entry^ do
      if Kind <> Reference
      then PushNewAccess(Entry, true)
      else
        if PartOfWord
        then
          begin
            OnByteBoundary := false;
            if IndexedPartWord then PushNewAccess(Entry, true)
          end
        else
          if Indexed
          then PushNewAccess(Entry, true)
          else ReferencePartWord(Entry)
  end { partwordreference };

{

 16.6  Simple References
 The interface procedure StackReference,  which  creates  the  base
 reference  from  which  more  complex  access  lists are built, is
 trivially implemented using the preceding utilities:

                                                                     }

procedure StackReference (Indirct : Boolean ;
                          Location : RuntimeAddress);
visible;

  var NewEntry: StackEntry;

  begin
    if CodeIsToBeGenerated
    then
      begin
        GetReference(NewEntry);
        with NewEntry^ do
          begin
            BaseAddress := Location;
            Indirect := Indirct
          end;
        Push(NewEntry)
      end
  end { stackreference };

{

 16.7  Indexed References

 The IndexedReference operation, for  indexing  normal  arrays,  is
 carried out as follows:

 (a)  the index value is checked for range,  using  the  CheckRange
      procedure defined in Chapter 17.

 (b)  if the index value is constant a  direct  adjustment  of  the
      array reference is made to address the element required, oth-
      erwise the index value is appended to the  appropriate  index
      list for delayed index code generation.

 The IndexedCAPReference operation for indexing  conformant  arrays
 is  simpler  in  that  no special treatment of constant indices is
 possible and the nature of the existing array reference is  known.
 A  corresponding  procedure CheckCAPRange defined in Chapter 17 is
 used to check the index value range in this case.

                                                                     }

{procedure CheckRange(Min, Max: MCIntegerForm; CheckNumber: Scalar);
  forward;
}

procedure InxReference (PackedArray: Boolean;
                            LowBound, HighBound: ObjectValue;
                            Element: TypeRepresentation);
visible;

  var Entry, ArrayIndex: StackEntry;
      ConstIndex, PackedElement: Boolean;
      ThisIndex: IndexEntry;
      NormalisedIndex: MCIntegerForm;
      ElsPerWord: 2..MCBitsPerWord;

  begin
    if CodeIsToBeGenerated
    then
      begin
        CheckRange(LowBound.Ival, HighBound.Ival, 1);
        Pop(ArrayIndex);
        if ArrayIndex^.Kind = AConstant
        then
          begin
            ConstIndex := true;
            NormalisedIndex :=
              ArrayIndex^.TheConst.Ival - LowBound.Ival;
            FreeEntry(ArrayIndex)
          end
        else
          begin
            ConstIndex := false;
            new(ThisIndex);
            with ThisIndex^ do
              begin
                TheIndex := ArrayIndex;
                Next := nil;
                CAPIndex := false;
                Lower := LowBound.Ival;
                Upper := HighBound.Ival
              end
          end;
        Pop(Entry);
        if Entry^.Vulnerable then PreserveAccess(Entry);
        with Element do
          if WordSize > 1
          then PackedElement := false
          else
            PackedElement :=
              PackedArray and (BitSize <= MCBitsPerWord div 2);
        if PackedElement then PartWordReference(Entry);
        with Entry^ do
          if PackedElement
          then
            begin
              ElsPerWord := MCBitsPerWord div Element.BitSize;
              BitSize := MCBitsPerWord div ElsPerWord;
              if ConstIndex
              then
                begin
                  Adjustment :=
                    Adjustment + NormalisedIndex div ElsPerWord;
                  BitOffset :=
                    BitOffset +
                    (NormalisedIndex mod ElsPerWord) * BitSize
                end
              else
                begin
                  IndexedPartWord := true;
                  OnByteBoundary := (ElsPerWord = MCBytesPerWord);
                  ThisIndex^.Factor := ElsPerWord;
                  Index := ThisIndex
                end
            end
          else
            begin
              if ConstIndex
              then
                Adjustment :=
                  Adjustment + NormalisedIndex * Element.WordSize
              else
                begin
                  Adjustment :=
                    Adjustment - LowBound.Ival * Element.WordSize;
                  ThisIndex^.Factor := Element.WordSize;
                  if Indexed
                  then ThisIndex^.Next := Indices
                  else Indexed := true;
                  Indices := ThisIndex
                end
            end;
        Entry^.DataRep := Element;
        Push(Entry)
      end
  end { indexedreference };

{procedure CheckCAPRange(LowBoundAddress, HighBoundAddress:
                          RuntimeAddress);
  forward;
}

procedure InxCAPReference ( PackedSchema: Boolean;
                                LowBound,HighBound: CAPBound;
                                BoundPairRepresentation,
                                Component: TypeRepresentation );
visible;

  var Entry, ArrayIndex: StackEntry;
      ThisIndex: IndexEntry;
      PackedComponent: Boolean;
      ElsPerWord: 2..MCBitsPerWord;

  begin
    if CodeIsToBeGenerated
    then
      begin
        if Checks in Requested
        then CheckCAPRange(LowBound.Address, HighBound.Address);
        Pop(ArrayIndex);
        new(ThisIndex);
        with ThisIndex^ do
          begin
            TheIndex := ArrayIndex;
            Next := nil;
            CAPIndex := true;
            BpAddress := LowBound.Address
          end;
        Pop(Entry);
        with Component do
          if WordSize > 1
          then PackedComponent := false
          else
            PackedComponent :=
              PackedSchema and (BitSize <= MCBitsPerWord div 2);
        if PackedComponent then PartWordReference(Entry);
        with Entry^ do
          if PackedComponent
          then
            begin
              ElsPerWord := MCBitsPerWord div Component.BitSize;
              OnByteBoundary := (ElsPerWord = MCBytesPerWord);
              BitSize := MCBitsPerWord div ElsPerWord;
              IndexedPartWord := true;
              ThisIndex^.Factor := ElsPerWord;
              Index := ThisIndex
            end
          else
            begin
              if Indexed
              then ThisIndex^.Next := Indices else Indexed := true;
              Indices := ThisIndex
            end;
        Push(Entry)
      end
  end { indexedcapreference };

{

 16.8  Field References

 A field reference involves adjustment of the record address by the
 word  or  part-word offset of the field.  In practice this is com-
 plicated by the following:

 (a)  if the field is a tagfield, the record access  is  vulnerable
      to a check arising from a subsequent tagfield assignment;

 (b)  if the field is a variant field a cascade of  variant  checks
      may have been generated by a preceding call to VariantChecks.

 VariantChecks generates this cascade by  recursive  identification
 of  the variant in which the field lies from the outermost variant
 level.  At each level the action required is either to check or to
 reset  the  corresponding selector value, depending on whether the
 variant part has or has not an explicit tag  field.   Accordingly,
 the  procedures CheckUntaggedVariant and CheckTaggedVariant append
 appropriate entries  on  the  CheckList  for  the  record-variable
 reference.


                                                                     }

procedure CheckUntaggedVariant(SelectorRep: TypeRepresentation;
                               VariantValue: ObjectValue);

{  var CheckEntry: AncillaryEntry;
      RecordEntry: StackEntry;
}
  begin
{    if CodeIsToBeGenerated and
       (SelectorRep.CheckCode.EntryOffset <> 0)
    then
      begin
        Pop(RecordEntry);
        new(CheckEntry);
        with CheckEntry^ do
          begin
            Next := nil;
            WhichOp := SetSelector;
            Selector := SelectorRep.CheckCode;
            TagValue := VariantValue.Ival
          end;
        AppendEntry(RecordEntry^.CheckList, CheckEntry);
        Push(RecordEntry)
      end							}
  end { checkuntaggedvariant };

procedure CheckTaggedVariant(SelectorRep, VariantRep:
                               TypeRepresentation);

{  var CheckEntry: AncillaryEntry;
      RecordEntry: StackEntry;
}
  begin
{    if CodeIsToBeGenerated and (Checks in Requested)
    then
      begin
        Pop(RecordEntry);
        new(CheckEntry);
        with CheckEntry^ do
          begin
            Next := nil;
            WhichOp := CheckSelector;
            SelectorField := SelectorRep.Selector;
            SelectorValue := VariantRep.CheckValue.Magnitude
          end;
        AppendEntry(RecordEntry^.CheckList, CheckEntry);
        Push(RecordEntry)
      end								}
  end { checktaggedvariant };

procedure DoVariantChecks (VarPart: TypEntry; FieldId: IdEntry);
visible;

{  var LocalVariant: TypEntry;
}
  begin
{    if VarPart^.TagField <> FieldId
    then
      begin
        LocalVariant := VarPart^.FirstVariant;
        while not VariantField(LocalVariant, FieldId) do
          LocalVariant := LocalVariant^.NextVariant;
        with VarPart^ do
          if TagField = nil
          then
            CheckUntaggedVariant
              (Representation, LocalVariant^.VariantValue1)
          else
            CheckTaggedVariant
              (Representation, LocalVariant^.Representation);
        with LocalVariant^ do
          if SubVarPart <> nil
          then
            if VariantField(SubVarPart, FieldId)
            then DoVariantChecks(SubVarPart, FieldId)
      end							}
  end { variantchecks };

procedure FieldReference ( Field: FieldOffset; TagField: Boolean );
visible;

  var Entry: StackEntry;

  begin
    if CodeIsToBeGenerated
    then
      begin
        Pop(Entry);
        if TagField or (Entry^.CheckList.FirstEntry <> nil)
        then Entry^.Vulnerable := true;
        if Entry^.Vulnerable or (Entry^.Kind = Address)
        then PreserveAccess(Entry);
        if Field.PartWord then PartWordReference(Entry);
        with Entry^ do
          begin
            if Field.PartWord
            then
              begin
                BitSize := Field.BitSize;
                BitOffset := BitOffset + Field.BitOffset
              end;
            Adjustment := Adjustment + Field.WordOffset;
            Level := Field.Level
          end;
        if TagField then Entry^.Class := TagRef;
        Push(Entry)
      end
  end { fieldreference };

{

 16.9  Pointer and File Buffer References

 Pointer and file buffer references, except those  to  text  files,
 both  involve indirection.  The procedure IndirectReference imple-
 ments those aspects of indirection  common  to  pointer  and  file
 references.

 In the case of file buffer references the  indirection  is  via  a
 buffer  pointer embedded within the file record, which points to a
 sliding  buffer  window  within  the  associated  transfer  buffer
 itself.

 In the case of text files the file buffer is maintained as a char-
 acter  field  of  the  file record itself, so a BufferReference is
 equivalent to a FieldReference.

 The access created by a pointer reference,  and  the  file  record
 access  involved  in  a  buffer reference are always vulnerable to
 subsequent access checks.

                                                                     }

procedure IndirectReference(APointer: Boolean);
visible;

  var Entry: StackEntry;

  begin
    if CodeIsToBeGenerated
    then
      begin
        Pop(Entry);
        with Entry^ do
          begin
            if not (Vulnerable or Indirect or PartOfWord or Indexed
                    or (AccessList <> nil))
            then
              with BaseAddress do
                WordOffset := WordOffset + Adjustment
            else PreserveAccess(Entry)
          end;
        with Entry^ do
          begin
            Adjustment := 0;
            Indirect := true;
            if APointer
            then
              begin
                Class := PnterRef;
                if Checks in Requested then Vulnerable := true
              end
          end;
        Push(Entry)
      end
  end { indirectreference };

procedure PnterReference;
visible;

  begin
    if CodeIsToBeGenerated then IndirectReference(true)
  end { pnterreference };

procedure BufferReference ( PackedFile, TextFile: Boolean;
                            Element: TypeRepresentation );
visible;

  var Entry: StackEntry;

  begin
    if CodeIsToBeGenerated
    then
      begin
        if Checks in Requested
        then
          begin
            Pop(Entry);
            if Entry^.Vulnerable then PreserveAccess(Entry);
            Entry^.Class := FileRef;
            Entry^.Vulnerable := true;
            Push(Entry)
          end;
        FieldReference(BufferOffset, false);
        if not TextFile then IndirectReference(false)
      end
  end { bufferreference };

{

 16.10 Reference Testing

 The following function enables subsequent chapters to test whether
 a  reference  is simple, i.e. is a word access involving no index-
 ing, pointer chasing, or access checking code.

                                                                     }

function SimpleReference(Entry: StackEntry): Boolean;
visible;

  begin
    with Entry^ do
      if Kind <> Reference
      then SimpleReference := false
      else
        SimpleReference :=
          (AccessList = nil) and not PartOfWord and not Indexed and
          not (Indirect and (Class = PnterRef))
  end { simplereference };

begin
{ module ends here}
end.