Storage Allocation Algorithm

Data area is contiguous region of storage specified by its base address and size.
Two kinds of data are are arrays and records.

Allocation of Data in Records

Allocation of storage is done as an offset to a base address, which is associated with a block of storage. Assignment of storage locations is done sequentially by a simple algorithm:

• next = 0

offset = next;
next = next + n;
return offset;

• Finally, next gives the total size of the block.

Word Alignment and Padding

storage alignment: Certain items must be allocated at restricted locations.
In such cases, next is advanced to next available boundary if needed, and the intervening(사이에 오는) storage is wasted; this is called padding

wordaddress(next, m) = ( (next + m - 1) / m) *m

Variant Records

A record declaration has a form such as : record $field_1$, …, $field_n$ : $type_1$ ; .. end *
Such a declaration is processed as follows :

• Initialize offset within the record to be 0.
• For each entry group,
  • find the symbol table entry for the type
  • allocate storage within the record using the storage allocation algorithm and size of type
  • make a symbol table entry for each field, filling in its print name, type, offset in the record, and size.
  • link the entries for the field to an entry for the record
• The size of the record is the total size given by the storage allocation algorithm, rounded up to whole words.
• Variant records simply restart the storage allocation at the place where the variant part begins. Total size is the maximum size of the variants.

Citation:

• Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools
• UT Austin CS375: Compilers by G.Novak.