mirror of
https://github.com/apple/swift.git
synced 2026-10-18 17:49:23 +02:00
Saleem Abdulrasool
5f090c41be
A COM existential has no directly projectable native metadata. Give its existential_metatype operation an Any.Type result so it can represent either recovered class metadata or the static interface type. QueryInterface and Release can execute foreign code. Account for those effects in memory, release, escape, and runtime-effect analysis, and prevent common-subexpression elimination from merging the queries.
948 lines
33 KiB
Swift
948 lines
33 KiB
Swift
//===--- CommonSubexpressionElimination.swift - CSE -----------------------===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2014 - 2026 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
//
|
|
// A dominator-tree DFS pass that eliminates redundant instructions by replacing
|
|
// each duplicate with the first occurrence that dominates it.
|
|
//
|
|
// It is invoked using the flag:
|
|
// "common-subexpression-elimination" — post-inlining, runs on canonical SIL
|
|
// "high-level-common-subexpression-elimination" — pre-inlining, also CSEs
|
|
// semantic array calls
|
|
//
|
|
// Lazy property getter applies are CSE-ed: two calls to the same getter on the
|
|
// same `self` value in a dominator relationship can share the first call's result.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
import SIL
|
|
|
|
// -----------------------------------------------------------------------
|
|
// Pass entry points
|
|
// -----------------------------------------------------------------------
|
|
|
|
let commonSubexpressionElimination = FunctionPass(name: "common-subexpression-elimination") {
|
|
(function: Function, context: FunctionPassContext) in
|
|
runCSE(function, context, false)
|
|
}
|
|
|
|
let highLevelCSE = FunctionPass(name: "high-level-common-subexpression-elimination") {
|
|
(function: Function, context: FunctionPassContext) in
|
|
runCSE(function, context, true)
|
|
}
|
|
|
|
func runCSE(
|
|
_ function: Function,
|
|
_ context: FunctionPassContext,
|
|
_ runsOnHighLevelSil: Bool
|
|
) {
|
|
guard let entryBlock = function.blocks.first else {
|
|
return
|
|
}
|
|
|
|
var map = ScopedHashMap()
|
|
|
|
// This will contain lazy property getter calls which can be optimized since
|
|
// they are dominated by an equivalent call, meaning the switch_enum call in
|
|
// the getter can be eliminated.
|
|
var lazyPropertyGetters: [ApplyInst] = []
|
|
|
|
processFunction(
|
|
startBlock: entryBlock,
|
|
&map,
|
|
runsOnHighLevelSil,
|
|
&lazyPropertyGetters,
|
|
context
|
|
)
|
|
processLazyPropertyGetters(lazyPropertyGetters, function, context)
|
|
if context.hasChanged(.Branches) {
|
|
_ = context.removeDeadBlocks(in: function)
|
|
}
|
|
if context.needBreakInfiniteLoops {
|
|
breakInfiniteLoops(in: function, context)
|
|
}
|
|
if context.needCompleteLifetimes {
|
|
completeLifetimes(in: function, context)
|
|
}
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// DFS over the dominator tree
|
|
// -----------------------------------------------------------------------
|
|
|
|
/// Performs an iterative depth-first traversal of the dominator tree rooted at
|
|
/// `startBlock`, processing each block's instructions for CSE opportunities.
|
|
private func processFunction(
|
|
startBlock: BasicBlock,
|
|
_ map: inout ScopedHashMap,
|
|
_ runsOnHighLevelSil: Bool = false,
|
|
_ lazyPropertyGetters: inout [ApplyInst],
|
|
_ context: FunctionPassContext
|
|
) {
|
|
// Each stack frame holds the block being visited and an iterator for
|
|
// supplying the next unprocessed dominator-tree child so we can resume after
|
|
// processing each child.
|
|
var dfsStack: [(block: BasicBlock, childIt: DomChildren.Iterator)] = []
|
|
|
|
var block = startBlock
|
|
while true {
|
|
// Process this block and push it to the stack.
|
|
guard processBlock(block, &map, runsOnHighLevelSil, &lazyPropertyGetters, context) else {
|
|
return
|
|
}
|
|
|
|
dfsStack.append((block, context.dominatorTree.getChildren(of: block).makeIterator()))
|
|
|
|
// Find the next block to visit. This will be the next child of the deepest
|
|
// stack frame that has unprocessed children.
|
|
while true {
|
|
if let child = dfsStack[dfsStack.count - 1].childIt.next() {
|
|
block = child
|
|
break
|
|
}
|
|
|
|
// All children exhausted — pop this block's entries from the map
|
|
// and remove its frame from the DFS stack.
|
|
map.pop(block: dfsStack.removeLast().block)
|
|
|
|
if dfsStack.isEmpty {
|
|
// Nothing left in the stack — we're done.
|
|
return
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// Per-block processing
|
|
// -----------------------------------------------------------------------
|
|
|
|
/// Scans `block`'s instructions for CSE candidates.
|
|
///
|
|
/// For each instruction that can be CSE-ed:
|
|
/// - If an equivalent instruction already exists in `map`, replace `inst`
|
|
/// with that earlier occurrence and erase `inst`.
|
|
/// - Otherwise, insert `inst` into `map` so dominated blocks can find it.
|
|
private func processBlock(
|
|
_ block: BasicBlock,
|
|
_ map: inout ScopedHashMap,
|
|
_ runsOnHighLevelSil: Bool = false,
|
|
_ lazyPropertyGetters: inout [ApplyInst],
|
|
_ context: FunctionPassContext
|
|
) -> Bool {
|
|
// `block.instructions` skips deleted instructions automatically, so it is
|
|
// safe to erase the current instruction while iterating.
|
|
for inst in block.instructions {
|
|
if inst.isTriviallyDead {
|
|
context.erase(instruction: inst)
|
|
continue
|
|
}
|
|
|
|
// getHash returns nil for ineligible instructions.
|
|
guard
|
|
let ref = InstructionReference(
|
|
inst: inst,
|
|
runsOnHighLevelSil: runsOnHighLevelSil,
|
|
calleeAnalysis: context.calleeAnalysis
|
|
)
|
|
else {
|
|
continue
|
|
}
|
|
// If an instruction can be handled here, then it must also be handled
|
|
// in isIdenticalTo, otherwise looking up a key in the map will fail to
|
|
// match itself.
|
|
assert(inst.isIdenticalTo(inst), "inst must match itself for map to work")
|
|
|
|
if let availInst = map.lookup(ref) {
|
|
if !context.continueWithNextSubpassRun(for: inst) {
|
|
return false
|
|
}
|
|
switch inst {
|
|
case let ai as ApplyInst where isOptimizableLazyPropertyGetter(ai):
|
|
lazyPropertyGetters.append(ai)
|
|
continue
|
|
case let openExistential as OpenExistentialRefInst:
|
|
if !processOpenExistentialRef(
|
|
openExistential, into: availInst as! OpenExistentialRefInst,
|
|
map, runsOnHighLevelSil, context
|
|
) {
|
|
map.insert(ref)
|
|
continue
|
|
}
|
|
default:
|
|
break
|
|
}
|
|
tryCSEReplace(inst: inst, with: availInst, context)
|
|
continue
|
|
}
|
|
|
|
map.insert(ref)
|
|
}
|
|
return true
|
|
}
|
|
|
|
private func hasGuaranteedSelf(_ ai: ApplyInst) -> Bool {
|
|
let conventions = ai.calleeArgumentConventions
|
|
guard let selfIdx = conventions.selfIndex else {
|
|
return false
|
|
}
|
|
return conventions[selfIdx] == .directGuaranteed
|
|
}
|
|
|
|
private func canHandleArraySemanticsCall(_ ai: ApplyInst) -> Bool {
|
|
switch ai.arraySemanticsCallKind {
|
|
case .getCount, .getCapacity, .checkIndex, .checkSubscript:
|
|
return hasGuaranteedSelf(ai)
|
|
default:
|
|
return false
|
|
}
|
|
}
|
|
|
|
private func isPureOrGlobalInit(_ ai: ApplyInst, calleeAnalysis: CalleeAnalysis?) -> Bool {
|
|
if !ai.mayReadOrWriteMemory {
|
|
return true
|
|
}
|
|
|
|
if let ca = calleeAnalysis {
|
|
let effects = ca.getSideEffects(ofApply: ai)
|
|
if effects.getMemBehavior(observeRetains: false) == .None {
|
|
return true
|
|
}
|
|
}
|
|
|
|
if let callee = ai.referencedFunction, callee.isGlobalInitFunction {
|
|
return true
|
|
}
|
|
|
|
return false
|
|
}
|
|
|
|
private func isOptimizableLazyPropertyGetter(_ ai: ApplyInst) -> Bool {
|
|
guard let callee = ai.referencedFunction,
|
|
callee.isDefinition,
|
|
callee.isLazyPropertyGetter
|
|
else {
|
|
return false
|
|
}
|
|
|
|
// We cannot inline a non-ossa function into an ossa function
|
|
if ai.parentFunction.hasOwnership && !callee.hasOwnership {
|
|
return false
|
|
}
|
|
|
|
// A getter that binds dynamic Self can only be inlined when the caller also
|
|
// binds dynamic Self and the callee is called on the self value itself.
|
|
if callee.mayBindDynamicSelf {
|
|
guard ai.parentFunction.mayBindDynamicSelf,
|
|
let calleeSelfIdx = ai.calleeArgumentConventions.selfIndex,
|
|
let callerSelf = ai.parentFunction.selfArgument,
|
|
ai.arguments[calleeSelfIdx] === callerSelf
|
|
else {
|
|
return false
|
|
}
|
|
}
|
|
|
|
// Only handle classes, but not structs.
|
|
// Lazy property getters of structs have an indirect inout self parameter.
|
|
// We don't know if the whole struct is overwritten between two getter calls.
|
|
// In such a case, the lazy property could be reset to an Optional.none.
|
|
if ai.arguments[0].type.isAddress {
|
|
return false
|
|
}
|
|
|
|
// Does the entry block check if the property has already been initialized?
|
|
// We don't handle getters of generic types, which have a switch_enum_addr.
|
|
// This will be obsolete with opaque values anyway.
|
|
guard let sei = callee.entryBlock.terminator as? SwitchEnumInst else {
|
|
return false
|
|
}
|
|
|
|
guard let someDest = sei.getUniqueSuccessor(forCaseIndex: Builder.optionalSomeCaseIndex) else {
|
|
return false
|
|
}
|
|
return someDest.arguments.count == 1
|
|
}
|
|
|
|
/// Replace lazy property getters (which are dominated by the same getter)
|
|
/// by a direct load of the value.
|
|
private func processLazyPropertyGetters(
|
|
_ lazyPropertyGetters: [ApplyInst],
|
|
_ function: Function,
|
|
_ context: FunctionPassContext
|
|
) {
|
|
for ai in lazyPropertyGetters {
|
|
guard let callee = ai.referencedFunction else {
|
|
continue
|
|
}
|
|
assert(callee.isLazyPropertyGetter)
|
|
let callBlock = ai.parentBlock
|
|
|
|
if ai.inliningCanInvalidateStackNesting {
|
|
context.notifyInvalidatedStackNesting()
|
|
}
|
|
|
|
assert(callee.isDefinition)
|
|
context.inlineFunction(apply: ai, mandatoryInline: false)
|
|
|
|
// After inlining the getter, the call block's terminator is the
|
|
// switch_enum from the getter's entry block.
|
|
guard let sei = callBlock.terminator as? SwitchEnumInst,
|
|
let someDest = sei.getUniqueSuccessor(forCaseIndex: Builder.optionalSomeCaseIndex),
|
|
someDest.arguments.count == 1
|
|
else {
|
|
continue
|
|
}
|
|
|
|
let builder = Builder(before: sei, context)
|
|
let ued = builder.createUncheckedEnumData(
|
|
enum: sei.enumOp,
|
|
caseIndex: Builder.optionalSomeCaseIndex,
|
|
resultType: someDest.arguments[0].type
|
|
)
|
|
_ = builder.createBranch(to: someDest, arguments: [ued])
|
|
context.erase(instruction: sei)
|
|
}
|
|
|
|
if context.needFixStackNesting {
|
|
context.fixStackNesting(in: function)
|
|
}
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// Replace + erase
|
|
// -----------------------------------------------------------------------
|
|
|
|
/// Replaces `inst` with the dominating equivalent `availInst` and erases it.
|
|
private func tryCSEReplace(
|
|
inst: Instruction,
|
|
with availInst: Instruction,
|
|
_ context: FunctionPassContext
|
|
) {
|
|
if let availFwd = availInst as? ForwardingInstruction,
|
|
let instFwd = inst as? ForwardingInstruction,
|
|
availFwd.forwardingOwnership != instFwd.forwardingOwnership
|
|
{
|
|
guard
|
|
availFwd.forwardingOwnership == .none
|
|
|| instFwd.forwardingOwnership == .none
|
|
else {
|
|
// This should never occur. This check is here as a precaution.
|
|
return
|
|
}
|
|
availFwd.setForwardingOwnership(to: .none, context)
|
|
}
|
|
for (result, availResult) in zip(inst.results, availInst.results) {
|
|
result.uses.replaceAll(with: availResult, context)
|
|
}
|
|
context.erase(instruction: inst)
|
|
}
|
|
|
|
/// Update SIL basic block's arguments types which refer to opened
|
|
/// archetypes. Replace such types by performing type substitutions
|
|
/// according to the provided type substitution map.
|
|
private func updateBasicBlockArgTypes(
|
|
_ block: BasicBlock,
|
|
_ cloner: Cloner<FunctionPassContext>,
|
|
_ usersToHandle: inout InstructionWorklist,
|
|
_ context: FunctionPassContext
|
|
) {
|
|
for index in 0..<block.arguments.count {
|
|
let arg = block.arguments[index]
|
|
if !arg.type.hasExistentialArchetype {
|
|
continue
|
|
}
|
|
// Try to apply the archetype remapping to this argument's type. If it
|
|
// produces a different type, use it as the argument's new type.
|
|
let oldArgType = arg.type
|
|
let newArgType = cloner.getOpType(oldArgType)
|
|
if newArgType == oldArgType {
|
|
continue
|
|
}
|
|
let newArg = block.replacePhiArgumentAndReplaceAllUses(
|
|
at: index, type: newArgType, ownership: arg.ownership, decl: arg.decl, context
|
|
)
|
|
// The old argument's borrowed-from instruction (if any) still refers to
|
|
// the stale archetype and was not carried over by the replacement above.
|
|
if newArg.ownership == .guaranteed, let phi = Phi(newArg) {
|
|
updateGuaranteedPhis(phis: [phi], context)
|
|
}
|
|
usersToHandle.pushIfNotVisited(contentsOf: newArg.users)
|
|
}
|
|
}
|
|
|
|
/// Handles CSE of guaranteed `open_existential_ref` instructions.
|
|
///
|
|
/// Returns true if uses of open_existential_ref can
|
|
/// be replaced by a dominating instruction.
|
|
private func processOpenExistentialRef(
|
|
_ openExistential: OpenExistentialRefInst,
|
|
into dominating: OpenExistentialRefInst,
|
|
_ map: ScopedHashMap,
|
|
_ runsOnHighLevelSil: Bool,
|
|
_ context: FunctionPassContext
|
|
) -> Bool {
|
|
var usersToHandle = InstructionWorklist(context)
|
|
defer { usersToHandle.deinitialize() }
|
|
|
|
// Collect all direct users that may contain opened archetypes that need to
|
|
// be replaced.
|
|
for use in openExistential.uses {
|
|
usersToHandle.pushIfNotVisited(use.instruction)
|
|
}
|
|
|
|
let oldEnv = openExistential.definedGenericEnvironment
|
|
let newEnv = dominating.definedGenericEnvironment
|
|
|
|
// Use a cloner. It makes copying the instruction and remapping of opened
|
|
// archetypes trivial.
|
|
var cloner = Cloner(in: openExistential.parentFunction, context)
|
|
defer { cloner.deinitialize() }
|
|
cloner.registerLocalArchetypeRemapping(from: oldEnv, to: newEnv)
|
|
// This cloner only remaps *types* containing local archetypes; it reuses
|
|
// SSA operands verbatim unless the operand's own defining instruction is
|
|
// itself cloned in this session. So direct (non-type-dependent) uses of
|
|
// `openExistential` must be redirected to `dominating` before any user
|
|
// gets cloned below. Otherwise a clone whose result type is derived from
|
|
// its operand's type at construction time (e.g. `copy_value`) would bake
|
|
// in the stale (old-archetype) type, and a later RAUW of the operand
|
|
// cannot retroactively fix that already-cached type.
|
|
openExistential.uses.ignoreTypeDependence.replaceAll(with: dominating, context)
|
|
|
|
// Now clone each candidate and replace the opened archetype by the
|
|
// dominating one.
|
|
while let user = usersToHandle.pop() {
|
|
if let term = user as? TermInst {
|
|
// The current use of the opened archetype is a terminator instruction.
|
|
// Check if any of the successor blocks use this opened archetype in
|
|
// the types of their arguments, and if so, replace those uses too.
|
|
for successor in term.successors where !successor.arguments.isEmpty {
|
|
updateBasicBlockArgTypes(successor, cloner, &usersToHandle, context)
|
|
}
|
|
}
|
|
|
|
// Compute if this candidate depends on the old opened archetype. It
|
|
// always does if it has a type-dependent operand on `openExistential`.
|
|
var dependsOnOldOpenedArchetype = user.operands.contains {
|
|
$0.isTypeDependent && $0.value == openExistential
|
|
}
|
|
|
|
// Look for dependencies propagated via the candidate's results.
|
|
for result in user.results where !result.uses.isEmpty && result.type.hasExistentialArchetype {
|
|
// Check if the result type depends on this specific opened existential.
|
|
if result.type.canonicalType.hasLocalArchetype(from: oldEnv) {
|
|
dependsOnOldOpenedArchetype = true
|
|
// The users of this candidate are new candidates.
|
|
usersToHandle.pushIfNotVisited(contentsOf: result.uses.users)
|
|
}
|
|
}
|
|
|
|
// No need to clone if there is no dependency on the old opened archetype.
|
|
if !dependsOnOldOpenedArchetype {
|
|
continue
|
|
}
|
|
|
|
cloner.setInsertionPoint(before: user)
|
|
let newInst = cloner.clone(instruction: user)
|
|
// Result types of this candidate's users may be using this archetype.
|
|
// Thus, we need to try to replace it there too.
|
|
for (origResult, newResult) in zip(user.results, newInst.results) {
|
|
origResult.uses.replaceAll(with: newResult, context)
|
|
}
|
|
context.erase(instruction: user)
|
|
}
|
|
return true
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// getHash — eligibility check and hash computation in one pass
|
|
// -----------------------------------------------------------------------
|
|
|
|
/// Returns the semantic hash of `inst` if it is eligible for CSE, or `nil` if
|
|
/// it must be skipped.
|
|
///
|
|
/// The hash must satisfy: if `a.isIdenticalTo(b)` then `getHash(a) == getHash(b)`.
|
|
/// It covers instruction kind, result type(s), operand SSA values, and any
|
|
/// instruction-specific attributes (field indices, literal values, etc.).
|
|
private func getHash(
|
|
of inst: Instruction,
|
|
runsOnHighLevelSil: Bool = false,
|
|
calleeAnalysis: CalleeAnalysis? = nil
|
|
) -> Int? {
|
|
// In OSSA, skip instructions that produce an owned result: replacing them
|
|
// would require inserting copies (via OwnershipRAUW or similar) to maintain
|
|
// ownership correctness. While this is possible, the inserted copies often
|
|
// cannot be optimized away, making the CSE counterproductive. Trivial (none)
|
|
// and guaranteed results are safe to replace without any fixup.
|
|
if inst.parentFunction.hasOwnership && inst.results.contains(where: { $0.ownership == .owned }) {
|
|
return nil
|
|
}
|
|
|
|
var hasher = Hasher()
|
|
|
|
// Helper: hash kind (via dynamic type) + result type + all operands.
|
|
// Used for most cast/conversion SingleValueInstructions.
|
|
func hashTypeOps(_ i: SingleValueInstruction) {
|
|
hasher.combine(ObjectIdentifier(type(of: i)))
|
|
hasher.combine(i.type)
|
|
for op in i.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
}
|
|
|
|
switch inst {
|
|
|
|
case let bi as BuiltinInst:
|
|
switch bi.id {
|
|
case .OnFastPath:
|
|
return nil // must not be moved or removed even though side-effect-free
|
|
case .Once, .OnceWithContext:
|
|
break // always eligible; fall through to hash below
|
|
default:
|
|
if bi.mayReadOrWriteMemory {
|
|
return nil
|
|
}
|
|
}
|
|
hasher.combine(ObjectIdentifier(BuiltinInst.self))
|
|
hasher.combine(bi.name._bridged.data)
|
|
hasher.combine(bi.substitutionMap.hasAnySubstitutableParams)
|
|
for op in bi.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
|
|
case let emi as ExistentialMetatypeInst:
|
|
// COM metadata queries execute foreign code, and the address form reads mutable storage.
|
|
if emi.mayHaveSideEffects || emi.operand.value.type.isAddress {
|
|
return nil
|
|
}
|
|
hasher.combine(ObjectIdentifier(ExistentialMetatypeInst.self))
|
|
hasher.combine(emi.type)
|
|
|
|
// Two `open_existential_ref`s of the same existential each define their
|
|
// own nominally-distinct opened archetype, so unlike the cases above we
|
|
// cannot hash/compare `x.type`. Merging them rewrites the type of every user
|
|
// that depends on the specific archetype, which is only attempted for
|
|
// guaranteed results.
|
|
case let x as OpenExistentialRefInst:
|
|
guard x.parentFunction.hasOwnership, x.ownership == .guaranteed else {
|
|
return nil
|
|
}
|
|
hasher.combine(ObjectIdentifier(OpenExistentialRefInst.self))
|
|
hasher.combine(x.existential.hashable)
|
|
|
|
// These instructions all use the same hash pattern: kind + result type + operands.
|
|
case let x as UpcastInst: hashTypeOps(x)
|
|
case let x as UncheckedRefCastInst: hashTypeOps(x)
|
|
case let x as UncheckedAddrCastInst: hashTypeOps(x)
|
|
case let x as UncheckedTrivialBitCastInst: hashTypeOps(x)
|
|
case let x as UncheckedBitwiseCastInst: hashTypeOps(x)
|
|
case let x as RefToRawPointerInst: hashTypeOps(x)
|
|
case let x as RawPointerToRefInst: hashTypeOps(x)
|
|
case let x as BridgeObjectToRefInst: hashTypeOps(x)
|
|
case let x as BridgeObjectToWordInst: hashTypeOps(x)
|
|
case let x as ClassifyBridgeObjectInst: hashTypeOps(x)
|
|
case let x as ValueToBridgeObjectInst: hashTypeOps(x)
|
|
case let x as RefToBridgeObjectInst: hashTypeOps(x)
|
|
case let x as ThickToObjCMetatypeInst: hashTypeOps(x)
|
|
case let x as ObjCToThickMetatypeInst: hashTypeOps(x)
|
|
case let x as ObjCMetatypeToObjectInst: hashTypeOps(x)
|
|
case let x as ObjCExistentialMetatypeToObjectInst: hashTypeOps(x)
|
|
case let x as AddressToPointerInst: hashTypeOps(x)
|
|
case let x as RefTailAddrInst: hashTypeOps(x)
|
|
case let x as ProjectBoxInst: hashTypeOps(x)
|
|
case let x as MarkDependenceInst: hashTypeOps(x)
|
|
case let x as RefToUnownedInst: hashTypeOps(x)
|
|
case let x as UnownedToRefInst: hashTypeOps(x)
|
|
case let x as RefToUnmanagedInst: hashTypeOps(x)
|
|
case let x as UnmanagedToRefInst: hashTypeOps(x)
|
|
case let x as SelectEnumInst: hashTypeOps(x)
|
|
case let x as TuplePackElementAddrInst: hashTypeOps(x)
|
|
|
|
// PointerToAddressInst also hashes isStrict to distinguish strict vs
|
|
// non-strict pointer dereferences.
|
|
case let x as PointerToAddressInst:
|
|
hasher.combine(ObjectIdentifier(PointerToAddressInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.isStrict)
|
|
for op in x.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
|
|
case let x as FunctionRefInst:
|
|
hasher.combine(ObjectIdentifier(FunctionRefInst.self))
|
|
hasher.combine(x.referencedFunction)
|
|
|
|
case let x as GlobalAddrInst:
|
|
hasher.combine(ObjectIdentifier(GlobalAddrInst.self))
|
|
hasher.combine(x.global)
|
|
|
|
// MetatypeInst has no operands; the type encodes the metatype identity.
|
|
case let x as MetatypeInst:
|
|
hasher.combine(ObjectIdentifier(MetatypeInst.self))
|
|
hasher.combine(x.type)
|
|
|
|
case let x as IntegerLiteralInst:
|
|
hasher.combine(ObjectIdentifier(IntegerLiteralInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.value) // Int? — nil for literals that don't fit in Int
|
|
|
|
// FloatLiteralInst: hash the actual bit pattern via the bridge.
|
|
// If bits is nil, we fall back to type-only, which is a safe hash collision.
|
|
case let x as FloatLiteralInst:
|
|
hasher.combine(ObjectIdentifier(FloatLiteralInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.bits)
|
|
|
|
case let x as StringLiteralInst:
|
|
hasher.combine(ObjectIdentifier(StringLiteralInst.self))
|
|
hasher.combine(x.encoding)
|
|
hasher.combine(x.value.string)
|
|
|
|
case let x as TypeValueInst:
|
|
hasher.combine(ObjectIdentifier(TypeValueInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.paramType)
|
|
|
|
// FIXME: no StructDecl so we rely on the SIL type
|
|
case let x as StructExtractInst:
|
|
hasher.combine(ObjectIdentifier(StructExtractInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.fieldIndex)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
case let x as StructElementAddrInst:
|
|
hasher.combine(ObjectIdentifier(StructElementAddrInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.fieldIndex)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
// fieldIndex + operand already uniquely identifies the projection within
|
|
// the tuple, and the operand's SSA type encodes the tuple type.
|
|
case let x as TupleExtractInst:
|
|
hasher.combine(ObjectIdentifier(TupleExtractInst.self))
|
|
hasher.combine(x.fieldIndex)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
case let x as TupleElementAddrInst:
|
|
hasher.combine(ObjectIdentifier(TupleElementAddrInst.self))
|
|
hasher.combine(x.fieldIndex)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
case let x as RefElementAddrInst:
|
|
hasher.combine(ObjectIdentifier(RefElementAddrInst.self))
|
|
hasher.combine(x.fieldIndex)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
// We use caseIndex (an Int) as the case discriminator, which encodes the
|
|
// same information as VarDecl* within a given enum type.
|
|
case let x as EnumInst:
|
|
hasher.combine(ObjectIdentifier(EnumInst.self))
|
|
hasher.combine(x.caseIndex)
|
|
if let payload = x.payload {
|
|
hasher.combine(payload.hashable)
|
|
}
|
|
|
|
// We use the result type as a proxy for the case — each case has a unique
|
|
// payload type, so the type already encodes the case.
|
|
case let x as UncheckedEnumDataInst:
|
|
hasher.combine(ObjectIdentifier(UncheckedEnumDataInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
// FIXME: no StructDecl so we rely on the SIL type
|
|
case let x as StructInst:
|
|
hasher.combine(ObjectIdentifier(StructInst.self))
|
|
hasher.combine(x.type)
|
|
for op in x.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
|
|
case let x as TupleInst:
|
|
hasher.combine(ObjectIdentifier(TupleInst.self))
|
|
hasher.combine(x.type)
|
|
for op in x.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
|
|
// CondFailInst has no result value, so we only hash the condition operand.
|
|
case let x as CondFailInst:
|
|
hasher.combine(ObjectIdentifier(CondFailInst.self))
|
|
hasher.combine(x.operand.value.hashable)
|
|
|
|
case let x as IndexAddrInst:
|
|
hasher.combine(ObjectIdentifier(IndexAddrInst.self))
|
|
hasher.combine(x.type)
|
|
for op in x.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
|
|
case let x as IndexRawPointerInst:
|
|
hasher.combine(ObjectIdentifier(IndexRawPointerInst.self))
|
|
hasher.combine(x.type)
|
|
for op in x.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
|
|
case let x as ClassMethodInst:
|
|
hasher.combine(ObjectIdentifier(ClassMethodInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
case let x as SuperMethodInst:
|
|
hasher.combine(ObjectIdentifier(SuperMethodInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
case let x as WitnessMethodInst:
|
|
hasher.combine(ObjectIdentifier(WitnessMethodInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.lookupType)
|
|
hasher.combine(x.member)
|
|
hasher.combine(x.conformance)
|
|
for op in x.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
|
|
case let x as ObjCProtocolInst:
|
|
hasher.combine(ObjectIdentifier(ObjCProtocolInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(ObjectIdentifier(x.protocolDecl))
|
|
|
|
case let x as ValueMetatypeInst:
|
|
hasher.combine(ObjectIdentifier(ValueMetatypeInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
|
|
case let x as InitExistentialMetatypeInst:
|
|
hasher.combine(ObjectIdentifier(InitExistentialMetatypeInst.self))
|
|
hasher.combine(x.type)
|
|
hasher.combine(x.operands[0].value.hashable)
|
|
for c in x.conformances {
|
|
hasher.combine(c)
|
|
}
|
|
|
|
case let x as ScalarPackIndexInst:
|
|
hasher.combine(ObjectIdentifier(ScalarPackIndexInst.self))
|
|
hasher.combine(x.componentIndex)
|
|
hasher.combine(x.indexedPackType)
|
|
|
|
case let x as DynamicPackIndexInst:
|
|
hasher.combine(ObjectIdentifier(DynamicPackIndexInst.self))
|
|
hasher.combine(x.indexedPackType)
|
|
for op in x.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
|
|
case let x as ApplyInst:
|
|
if !x.parentFunction.hasOwnership {
|
|
if x.functionConvention.resultsWithError.contains(where: { $0.convention != .unowned }) {
|
|
return nil
|
|
}
|
|
}
|
|
if isOptimizableLazyPropertyGetter(x) || (runsOnHighLevelSil && canHandleArraySemanticsCall(x))
|
|
|| (isPureOrGlobalInit(x, calleeAnalysis: calleeAnalysis))
|
|
{
|
|
hasher.combine(ObjectIdentifier(ApplyInst.self))
|
|
for op in x.operands {
|
|
hasher.combine(op.value.hashable)
|
|
}
|
|
} else {
|
|
return nil
|
|
}
|
|
|
|
default:
|
|
return nil
|
|
}
|
|
|
|
return hasher.finalize()
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// InstructionReference — Hashable wrapper with cached hash
|
|
// -----------------------------------------------------------------------
|
|
|
|
/// A `Hashable` wrapper around an `Instruction` that provides semantic equality
|
|
/// via `isIdenticalTo` and caches the pre-computed hash from `getHash(of:)`.
|
|
///
|
|
/// The failable initializer returns `nil` for instructions that are not eligible
|
|
/// for CSE. Once constructed, the hash stored in `hash` is reused for every map
|
|
/// operation, avoiding redundant computation during lookup, insertion, and pop.
|
|
struct InstructionReference: Hashable {
|
|
let inst: Instruction
|
|
let hash: Int
|
|
|
|
/// Returns `nil` if `inst` is not eligible for CSE.
|
|
init?(inst: Instruction, runsOnHighLevelSil: Bool = false, calleeAnalysis: CalleeAnalysis? = nil)
|
|
{
|
|
guard
|
|
let h = getHash(
|
|
of: inst,
|
|
runsOnHighLevelSil: runsOnHighLevelSil,
|
|
calleeAnalysis: calleeAnalysis
|
|
)
|
|
else {
|
|
return nil
|
|
}
|
|
self.inst = inst
|
|
self.hash = h
|
|
}
|
|
|
|
static func == (lhs: Self, rhs: Self) -> Bool {
|
|
if let lv = lhs.inst as? TypeValueInst, let rv = rhs.inst as? TypeValueInst {
|
|
return lv.type == rv.type && lv.paramType == rv.paramType
|
|
}
|
|
// `isIdenticalTo` requires exactly equal result types, but two
|
|
// `open_existential_ref`s of the same existential always define
|
|
// distinct opened archetypes as their result type.
|
|
// Compare the opened existential and, since the two opened archetypes are
|
|
// nominally distinct, their generic signature (conformances, superclass,
|
|
// layout constraint) — two opens of the same existential can still be
|
|
// opened to different constraint sets, and only equal signatures can be
|
|
// remapped onto one another.
|
|
if let lo = lhs.inst as? OpenExistentialRefInst, let ro = rhs.inst as? OpenExistentialRefInst {
|
|
return lo.existential === ro.existential
|
|
&& lo.definedGenericEnvironment.hasEqualGenericSignature(to: ro.definedGenericEnvironment)
|
|
}
|
|
return lhs.inst.isIdenticalTo(rhs.inst)
|
|
}
|
|
|
|
func hash(into hasher: inout Hasher) {
|
|
hasher.combine(hash)
|
|
}
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// ScopedHashMap — keyed hash table with DFS-scope push/pop
|
|
// -----------------------------------------------------------------------
|
|
|
|
/// Scoped hash table for the CSE pass.
|
|
///
|
|
/// Maps semantically-equivalent instructions (keyed by `InstructionReference`)
|
|
/// to their position in a backing stack array. The stack grows monotonically
|
|
/// during DFS of the dominator tree; `pop(block:)` unwinds it when the pass
|
|
/// leaves a basic block's scope.
|
|
///
|
|
/// Storing `InstructionReference` (rather than bare `Instruction`) in the
|
|
/// stack means `pop` can reuse the cached hash when removing map entries,
|
|
/// without re-running `getHash`.
|
|
struct ScopedHashMap {
|
|
private var map: [InstructionReference: Int] = [:]
|
|
private var stack: [InstructionReference] = []
|
|
|
|
/// Insert `ref` into the map.
|
|
///
|
|
/// If an equivalent instruction is already present, its entry is overwritten,
|
|
/// which is consistent with dominator-tree-order traversal where a closer
|
|
/// dominator should win.
|
|
mutating func insert(_ ref: InstructionReference) {
|
|
map[ref] = stack.count
|
|
stack.append(ref)
|
|
}
|
|
|
|
/// Return the previously inserted instruction that is semantically
|
|
/// equivalent to `ref.inst`, or `nil` if none exists.
|
|
func lookup(_ ref: InstructionReference) -> Instruction? {
|
|
guard let idx = map[ref] else {
|
|
return nil
|
|
}
|
|
return stack[idx].inst
|
|
}
|
|
|
|
/// Remove all instructions whose `parentBlock` is `block`.
|
|
///
|
|
/// Only removes a contiguous suffix of the stack, which is correct because
|
|
/// the pass inserts instructions in dominator-tree DFS order and calls
|
|
/// `pop(block:)` on the way back up — so all instructions from a given
|
|
/// block are always at the top of the stack when that block is popped.
|
|
mutating func pop(block: BasicBlock) {
|
|
while let ref = stack.last, ref.inst.parentBlock === block {
|
|
map.removeValue(forKey: ref)
|
|
stack.removeLast()
|
|
}
|
|
}
|
|
}
|
|
|
|
extension ScopedHashMap: CustomStringConvertible {
|
|
/// Lists each instruction in the map, one per line, in insertion order.
|
|
public var description: String {
|
|
stack.map { " \($0.inst)" }.joined(separator: "\n")
|
|
}
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// Tests
|
|
// -----------------------------------------------------------------------
|
|
|
|
/// Build a ScopedHashMap from all instructions in the first basic block
|
|
/// (duplicates are skipped via lookup), then print the map contents.
|
|
/// Used to verify that semantically identical instructions are deduplicated.
|
|
let scopedHashTableTest = FunctionTest("scoped-hash-table") {
|
|
function,
|
|
arguments,
|
|
context in
|
|
var map = ScopedHashMap()
|
|
for inst in function.blocks.first!.instructions {
|
|
guard let ref = InstructionReference(inst: inst) else {
|
|
continue
|
|
}
|
|
if map.lookup(ref) == nil {
|
|
map.insert(ref)
|
|
}
|
|
}
|
|
print(map)
|
|
}
|
|
|
|
/// Insert `inst1` and then look up `inst2`.
|
|
/// Prints "hit" if the lookup succeeds, "miss" otherwise.
|
|
let scopedHashTableInsertLookupTest = FunctionTest("scoped-hash-table-insert-lookup") {
|
|
function,
|
|
arguments,
|
|
context in
|
|
let inst1 = arguments.takeInstruction()
|
|
let inst2 = arguments.takeInstruction()
|
|
var map = ScopedHashMap()
|
|
map.insert(InstructionReference(inst: inst1)!)
|
|
print(map.lookup(InstructionReference(inst: inst2)!) != nil ? "hit" : "miss")
|
|
}
|
|
|
|
/// Takes `@instruction` (expected to be an apply), prints "true" if it is a
|
|
/// call to a lazy property getter that the CSE pass can handle, "false" otherwise.
|
|
let isOptimizableLazyPropertyGetterTest = FunctionTest("is-optimizable-lazy-property-getter") {
|
|
function,
|
|
arguments,
|
|
context in
|
|
let inst = arguments.takeInstruction()
|
|
guard let ai = inst as? ApplyInst else {
|
|
print("not an apply")
|
|
return
|
|
}
|
|
print(isOptimizableLazyPropertyGetter(ai) ? "true" : "false")
|
|
}
|
|
|
|
/// Insert `keepInst` (in a block other than `popBlock`) and `popInst` (in
|
|
/// `popBlock`), then call `pop(block: popBlock)`.
|
|
/// Prints whether each instruction remains in the map afterwards.
|
|
let scopedHashTablePopTest = FunctionTest("scoped-hash-table-pop") {
|
|
function,
|
|
arguments,
|
|
context in
|
|
let keepInst = arguments.takeInstruction()
|
|
let popInst = arguments.takeInstruction()
|
|
let popBlock = arguments.takeBlock()
|
|
let keepRef = InstructionReference(inst: keepInst)!
|
|
let popRef = InstructionReference(inst: popInst)!
|
|
var map = ScopedHashMap()
|
|
map.insert(keepRef)
|
|
map.insert(popRef)
|
|
map.pop(block: popBlock)
|
|
print(map.lookup(keepRef) != nil ? "keep: hit" : "keep: miss")
|
|
print(map.lookup(popRef) != nil ? "pop: hit" : "pop: miss")
|
|
}
|