Skip to content

SROA

SROA is implemented in two phases: an interprocedural optimization and an intraprocedural optimization.

Interprocedural SROA: The goal of this pass is just to update the types of all functions to break up product parameter (into multiple parameters, eliminating parameters of unit type) and simplifying return types (by eliminating unit types and singleton products). To do this, we make as few changes to the function as possible by re-constructing the original parameter products and constructing the new return value from the original return value by reading fields out of it and writing it into the new return type.

This also requires updating call sites; again to make as few changes as possible we read fields out of the original arguments to construct the new arguments and take the new return value and reconstruct the old return value from it.

Intraprocedural SROA: This is an iterative process where each iteration removes one level of products and we repeat until no changes are made. Each iteration proceeds as follows:

  1. Find the nodes that interact with products (constants and parameters of product types, phi over products, reads and writes over products, and call nodes returning products)
  2. Construct a map from each pair of non-read node ID and field index to new node ID which will correspond to only that field of that original node. We allocate these new node IDs ahead of time using a worklist initialized in reverse post-order. For phi nodes, parameters, and constants we create new nodes for each field. For write nodes any non-written fields are just mapped to the field of the input product while the written field is mapped to the value being written into the product. Because of this we need the product value of the write to have been visited already.
  3. Finally with the map, we update the code; for each node that interacts with products, we create new nodes for constants (into separate constants for each field), parameters (generate a read for each field), and phis (a phi for each field), and replace all uses of reads based on the map (replace with the value from the map for the product it reads at the field it reads).
  4. Delete old phis, reads, and writes.