swift-mirror/docs/SIL/SIL-Utilities.md

Utilities for SIL optimizer passes

This document lists a set of SIL utilities to be used by the Swift implementation of the SIL optimizer.

Some of the utilities presented in this document are still in the design phase and are not implemented yet (see Status).

Goals for utilities

We want to avoid a situation like we have in the C++ SIL optimizer, where a huge amount of (partly) redundant utilities exist. Many of those utilities have overlapping functionality, are difficult to discover and are poorly designed. We want to do better in the Swift SIL optimizer.

Basic Data-Structures

Stack

An allocation-free, array like data structure. To be used instead of Swift.Array wherever random-access is not needed.

Related C++ utilities: llvm::SmallVector, Stack Status: done

BasicBlockSet

An extremely efficient implementation of a set of basic blocks.

Related C++ utilities: BasicBlockSet Status: done

ValueSet

An extremely efficient implementation of a set of values.

Related C++ utilities: ValueSet Status: done

InstructionSet

An extremely efficient implementation of a set of instructions.

Related C++ utilities: InstructionSet Status: done

BasicBlockWorklist

To be used for all kind of basic-block work-list algorithms.

Uses: Stack, BasicBlockSet
Related C++ utilities: BasicBlockWorklist Status: done

SIL data structures

SmallProjectionPath

Describes a path of projections.

Related C++ utilities: AccessPath, ProjectionPath
Status: done

ProjectedValue

A projected value is defined by the original value and a projection path.

Related C++ utilities: AccessPath Status: done

SingleInlineArray

An array with the first element stored inline. Useful for analyses that produces results that are typically a 1-to-1 map, but rarely a 1-to-N map.

Building SIL

static Builder.insert(after:, insertFunc: (Builder) -> ())

Useful to insert instructions after a (potential) terminator instruction.

Related C++ utilities: SILBuilderWithScope::insertAfter() Status: done

SSA Traversal Utilities

Walk Utils

This consists of four protocols, which can be implemented to walk up or down the SSA graph:

• ValueDefUseWalker
• AddressDefUseWalker
• ValueUseDefWalker
• AddressUseDefWalker

Uses: instruction classifications
Related C++ utilities: AccessPath, RCIdentityAnalysis, various def-use/use-def walkers in optimization passes.
Status: done

Escape Utilities

Escape analysis, which is used e.g. in stack promotion or alias analysis. Escape analysis is usable through the following methods of ProjectedValue and Value:

• isEscaping()
• isAddressEscaping()
• visit()
• visitAddress()

Uses: Walk Utilities, ProjectedValue Related C++ utilities: EscapeAnalysis, various def-use walkers in optimization passes.
Status: done

Access Utils

A set of utilities for analyzing memory accesses. It defines the following concepts:

• AccessBase: represents the base address of a memory access.
• AccessPath: a pair of an AccessBase and SmallProjectionPath with the path describing the specific address (in terms of projections) of the access.
• Access storage path (which is of type ProjectedValue): identifies the reference - or a value which contains a reference - an address originates from.

Uses: Walk utils Related C++ utilities: AccessPath and other access utilities. Status: done

Address Utils

• AddressUseVisitor: classify address uses. This can be used by def-use walkers to ensure complete handling of all legal SIL patterns.

Related Swift Utilities AddressDefUseWalker

Related C++ Utilities Projection::isAddressProjection isAccessStorageCast transitiveAddressWalker

TODO: Refactor AddressDefUseWalker to implement AddressUseVisitor.

Ownership Utils

BorrowUtils.swift has utilities for traversing borrow scopes:

• BorrowingInstruction: find borrow scopes during def-use walks
• BeginBorrowValue: find borrow scopes during use-def walks
• gatherBorrowIntroducers: use-def walk finds the current scopes
• gatherEnclosingValues: use-def walk finds the outer lifetimes that enclose the current scope

OwnershipUtils.swift has utilities for traversing OSSA lifetimes:

• computeLinearLiveness: compute an InstructionRange from the immediate lifetime ending uses.
• computeInteriorLiveness: complete def-use walk to compute an InstructionRange from all transitive use points that must be within an OSSA lifetime.
• InteriorUseWalker: def-use walker for all transitive use points that must be within an OSSA lifetime.
• OwnershipUseVistor: categorize all uses of an owned or guaranteed use by ownership effect. Use this within a recursive def-use walker to decide how to follow each use.

InteriorUseWalker, like AddressDefUseWalker, walks def-use address projections. The difference is that it visits and classifies all uses regardless of whether they are projections, it has callbacks for handling inner scopes, and it automatically handles the lifetime effect of inner scopes and dependent values.

ForwardingUtils.swift has utilities for traversing forward-extended lifetimes:

Forward-extended lifetimes may include multiple OSSA lifetimes joined by ForwardingInstructions. Querying certain information about OSSA lifetimes, such as whether it has a lexical lifetime or a pointer escape, requires finding the introducer of the forward-extended lifetime. Forwarding walkers traverse the SSA graph of ForwardingInstructions:

• ForwardingUseDefWalker: Find the introducer of a forward-extended lifetime
• ForwardingDefUseWalker: Find all OSSA lifetimes within a forward-extended lifetime.

LifetimeDependence

Model lifetime dependencies in SIL, as required be ~Escapable types.

Control- and Dataflow

DeadEndBlocks

A utility for finding dead-end blocks. Dead-end blocks are blocks from which there is no path to the function exit (return, throw or unwind). These are blocks which end with an unreachable instruction and blocks from which all paths end in "unreachable" blocks.

Uses: BasicBlockWorklist
Related C++ utilities: DeadEndBlocks
Status: done

BasicBlockRange

Defines a range from a dominating "begin" block to one or more "end" blocks. To be used for all kind of backward block reachability analysis.

Uses: Stack, BasicBlockSet, BasicBlockWorklist
Related C++ utilities: PrunedLiveBlocks, findJointPostDominatingSet()
Status: done

InstructionRange

Like BasicBlockRange, but at the granularity of instructions.

Uses: BasicBlockRange
Related C++ utilities: PrunedLiveness, ValueLifetimeAnalysis
Status: done

Utilities for Inter-procedural Analysis

FunctionUses

Provides a list of instructions, which reference a function. This utility performs an analysis of all functions in the module and collects instructions which reference other functions. It can be used to do inter-procedural caller-analysis.

Related C++ utilities: CallerAnalysis Status: done

OSSA Utilities

Value.makeAvailable() and Value.copy(at:)

To be used where a value is copied in one block and used in another block.

Uses: BasicBlockRange
Related C++ utilities: makeValueAvailable(), OwnershipLifetimeExtender
Status: done

Instruction classifications

We want to classify certain instructions into common groups so that passes can deal deal with the group instead of individual instruction opcodes. Optimization passes then don't need to be updated if new instructions are added to a group.

In Swift we can easily do this by introducing protocols to which instruction classes can conform to.

ApplySite

Related C++ utilities: ApplySite Status: exists; to-do: complete member variables/functions

CastInstruction

Details need to be decided.

Conforming instructions: UpcastInst, UncheckedRefCastInst, etc.
Members: ownership behavior, e.g. forwarding, etc.
Status: to-do

AddressProjectionInstruction

Details need to be decided.

Conforming instructions: StructElementAddrInst, TupleElementAddrInst
Members: var fieldIndex: Int
Related C++ utilities: skipAddrProjections
Status: to-do

AggregateInstruction

Details need to be decided.

Conforming instructions: StructInst, TupleInst
Status: to-do

ExtractInstruction

Details need to be decided.

Conforming instructions: StructExtractInst, TupleExtractInst
Status: to-do

BorrowScope

Details need to be decided. Maybe it's better to not do this as a protocol but just add an extension function Value.introducesBorrowScope. Reason: an Argument can be guaranteed or owned.

Conforming instructions: BeginBorrowInst, Argument with guaranteed ownership (however will do that), LoadBorrowInst
Status: to-do