//===--- AliasAnalysis.swift - the alias analysis -------------------------===// // // This source file is part of the Swift.org open source project // // Copyright (c) 2014 - 2024 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 // //===----------------------------------------------------------------------===// import OptimizerBridging import SIL extension FunctionPassContext { var aliasAnalysis: AliasAnalysis { let bridgedAA = _bridged.getAliasAnalysis() return AliasAnalysis(bridged: bridgedAA, context: self) } } extension Instruction { func mayRead(fromAddress: Value, _ aliasAnalysis: AliasAnalysis) -> Bool { aliasAnalysis.getMemoryEffect(of: self, on: fromAddress).read } func mayWrite(toAddress: Value, _ aliasAnalysis: AliasAnalysis) -> Bool { if toAddress.isImmutableAddress { // Take a shortcut for indirect-in arguments. return false } return aliasAnalysis.getMemoryEffect(of: self, on: toAddress).write } func mayReadOrWrite(address: Value, _ aliasAnalysis: AliasAnalysis) -> Bool { let effect = aliasAnalysis.getMemoryEffect(of: self, on: address) if address.isImmutableAddress { return effect.read } return effect.read || effect.write } } /// Alias analysis. /// /// It's mainly used to check if an instruction may read or write from/to a specific address. /// struct AliasAnalysis { fileprivate let bridged: BridgedAliasAnalysis fileprivate let context: FunctionPassContext //===--------------------------------------------------------------------===// // Public interface //===--------------------------------------------------------------------===// /// Returns the effects of `inst`'s memory behavior on the memory pointed to by the `address`. func getMemoryEffect(of inst: Instruction, on address: Value) -> SideEffects.Memory { precondition(address.type.isAddress, "getMemoryEffects requires address value") var result = computeMemoryEffect(of: inst, on: MemoryLocation.memoryAddress(address)) if result.write && isImmutable(instruction: inst, inScopeOf: address) { result.write = false } // In the past we cached the result per instruction-address pair. But it turned out that the hit-miss rate was // pretty high (~ 1:7) and the cache lookup took as long as recomputing. return result } /// Returns true if `v1` and `v2` do or may alias. /// /// Usually `v1` and `v2` are addresses and in this case the return value is true if both addresses /// do or may point to the same memory location. /// /// If `v1` or `v2` is not an address, the function checks if any "interior" pointer of the value may alias /// with the other value or address. /// If a value is a class, "interior" pointer means: an address of any stored property of the class instance. /// If a value is a struct or another value type, "interior" pointers refer to any stored propery addresses of any /// class references in the struct or value type. For example: /// /// class C { var x: Int; var y: Int } /// struct S { var c1: C; var c2: C } /// /// `mayAlias(s, someAddress)` checks if someAddress aliases with `s.c1.x`, `s.c1.y`, `s.c2.x` or `s.c2.y` /// func mayAlias(_ v1: Value, _ v2: Value) -> Bool { if v1.type.isAddress && v2.type.isAddress { // The projection-path based check and TBAA can only be done if both values are really addresses. // This is the common case. let accessPath1 = v1.accessPath let accessPath2 = v2.accessPath if accessPath1.isDistinct(from: accessPath2) { return false } // Type-based alias analysis is only of minor importance. It's only needed if unsafe pointers are in play. // There are some critical functions in the stdlib which use unsafe pointers. Therefore we cannot omit TBAA. if isTypeDistinct(v1, v2, accessPath1.base, accessPath2.base) { return false } } // Finaly use escape info to check if one address "escapes" to the other address. return v1.allContainedAddresss.canAddressAlias(with: v2.allContainedAddresss, context) } static func register() { BridgedAliasAnalysis.registerAnalysis( // initFn { (bridgedAliasAnalysis: BridgedAliasAnalysis, size: Int) in assert(MemoryLayout.size <= size, "wrong AliasAnalysis.cache size") bridgedAliasAnalysis.mutableCachePointer.initializeMemory(as: Cache.self, repeating: Cache(), count: 1) }, // destroyFn { (bridgedAliasAnalysis: BridgedAliasAnalysis) in bridgedAliasAnalysis.mutableCachePointer.assumingMemoryBound(to: Cache.self).deinitialize(count: 1) }, // getMemEffectsFn { (bridgedCtxt: BridgedPassContext, bridgedAliasAnalysis: BridgedAliasAnalysis, bridgedAddr: BridgedValue, bridgedInst: BridgedInstruction) -> BridgedMemoryBehavior in let aa = AliasAnalysis(bridged: bridgedAliasAnalysis, context: FunctionPassContext(_bridged: bridgedCtxt)) return aa.getMemoryEffect(of: bridgedInst.instruction, on: bridgedAddr.value).bridged }, // isObjReleasedFn { (bridgedCtxt: BridgedPassContext, bridgedAliasAnalysis: BridgedAliasAnalysis, bridgedObj: BridgedValue, bridgedInst: BridgedInstruction) -> Bool in let context = FunctionPassContext(_bridged: bridgedCtxt) let aa = AliasAnalysis(bridged: bridgedAliasAnalysis, context: context) let inst = bridgedInst.instruction let obj = bridgedObj.value let path = SmallProjectionPath(.anyValueFields) let budget = aa.getComplexityBudget(for: inst.parentFunction) if let apply = inst as? FullApplySite { // Workaround for quadratic complexity in ARCSequenceOpts. // We need to use an ever lower budget to not get into noticeable compile time troubles. let effect = aa.getOwnershipEffect(of: apply, for: obj, path: path, complexityBudget: budget / 10) return effect.destroy } return obj.at(path).isEscaping(using: EscapesToInstructionVisitor(target: inst, isAddress: false), complexityBudget: budget, context) }, // isAddrVisibleFromObj { (bridgedCtxt: BridgedPassContext, bridgedAliasAnalysis: BridgedAliasAnalysis, bridgedAddr: BridgedValue, bridgedObj: BridgedValue) -> Bool in let context = FunctionPassContext(_bridged: bridgedCtxt) let aa = AliasAnalysis(bridged: bridgedAliasAnalysis, context: context) let addr = bridgedAddr.value.allContainedAddresss // This is similar to `canReferenceSameFieldFn`, except that all addresses of all objects are // considered which are transitively visible from `bridgedObj`. let anythingReachableFromObj = bridgedObj.value.at(SmallProjectionPath(.anything)) return addr.canAddressAlias(with: anythingReachableFromObj, complexityBudget: aa.getComplexityBudget(for: bridgedObj.value.parentFunction), context) }, // mayAliasFn { (bridgedCtxt: BridgedPassContext, bridgedAliasAnalysis: BridgedAliasAnalysis, bridgedLhs: BridgedValue, bridgedRhs: BridgedValue) -> Bool in let context = FunctionPassContext(_bridged: bridgedCtxt) let aa = AliasAnalysis(bridged: bridgedAliasAnalysis, context: context) return aa.mayAlias(bridgedLhs.value, bridgedRhs.value) } ) } //===--------------------------------------------------------------------===// // Internals //===--------------------------------------------------------------------===// private var cache: Cache { unsafeAddress { bridged.cachePointer.assumingMemoryBound(to: Cache.self) } nonmutating unsafeMutableAddress { bridged.mutableCachePointer.assumingMemoryBound(to: Cache.self) } } // The actual logic to compute the memory effect of an instruction. private func computeMemoryEffect(of inst: Instruction, on memLoc: MemoryLocation) -> SideEffects.Memory { switch inst { case let beginAccess as BeginAccessInst: // begin_access does not physically read or write memory. But we model it as a memory read and/or write // to prevent optimizations to move other aliased loads/stores across begin_access into the access scope. return getAccessScopeEffect(of: beginAccess, on: memLoc) case let endAccess as EndAccessInst: // Similar to begin_access, we model it as a memory read and/or write to prevent optimizations to move // other aliased loads/stores into the access scope. return getAccessScopeEffect(of: endAccess.beginAccess, on: memLoc) case is InjectEnumAddrInst, is UncheckedTakeEnumDataAddrInst, is InitExistentialAddrInst, is DeinitExistentialAddrInst, is FixLifetimeInst, is ClassifyBridgeObjectInst, is ValueToBridgeObjectInst, is DeallocStackInst: if memLoc.mayAlias(with: (inst as! UnaryInstruction).operand.value, self) { return inst.memoryEffects } return .noEffects case is CondFailInst, is StrongRetainInst, is UnownedRetainInst, is StrongRetainUnownedInst, is RetainValueInst, is UnmanagedRetainValueInst, is CopyValueInst, is StrongCopyUnownedValueInst, is StrongCopyUnmanagedValueInst, is StrongCopyWeakValueInst, is BeginBorrowInst, is BeginCOWMutationInst: return .noEffects case let load as LoadInst: if memLoc.mayAlias(with: load.address, self) { switch load.loadOwnership { case .unqualified, .copy, .trivial: return .init(read: true) case .take: // "take" is conceptually a write to the memory location. return .worstEffects } } else { return .noEffects } case let store as StoreInst: if memLoc.isLetValue && store.destination.accessBase != memLoc.address.accessBase { return .noEffects } if memLoc.mayAlias(with: store.destination, self) { return inst.memoryEffects } else { switch store.storeOwnership { case .unqualified, .initialize, .trivial: return .noEffects case .assign: // Consider side effects of the destructor return defaultEffects(of: store, on: memLoc) } } case let storeBorrow as StoreBorrowInst: return memLoc.mayAlias(with: storeBorrow.destination, self) ? .init(write: true) : .noEffects case let copy as SourceDestAddrInstruction: let mayRead = memLoc.mayAlias(with: copy.source, self) let mayWrite = memLoc.mayAlias(with: copy.destination, self) var effects = SideEffects.Memory(read: mayRead, write: mayWrite || (mayRead && copy.isTakeOfSrc)) if !copy.isInitializationOfDest { effects.merge(with: defaultEffects(of: copy, on: memLoc)) } return effects case let apply as FullApplySite: return getApplyEffect(of: apply, on: memLoc) case let partialApply as PartialApplyInst: return getPartialApplyEffect(of: partialApply, on: memLoc) case let endApply as EndApplyInst: return getApplyEffect(of: endApply.beginApply, on: memLoc) case let abortApply as AbortApplyInst: return getApplyEffect(of: abortApply.beginApply, on: memLoc) case let builtin as BuiltinInst: return getBuiltinEffect(of: builtin, on: memLoc) case let endBorrow as EndBorrowInst: switch endBorrow.borrow { case let storeBorrow as StoreBorrowInst: precondition(endBorrow.borrow.type.isAddress) return memLoc.mayAlias(with: storeBorrow, self) ? .worstEffects : .noEffects case let beginBorrow as BeginBorrowInst where !beginBorrow.hasPointerEscape: return getBorrowEffects(of: endBorrow, on: memLoc) case let loadBorrow as LoadBorrowInst: let borrowEffects = getBorrowEffects(of: endBorrow, on: memLoc) // In addition to the "regular" borrow effects, a load_borrow also has effects on the memory location // from where it loads the value. This includes "write" to prevent any optimization to change the // memory location after the load_borrow. if borrowEffects != .worstEffects && memLoc.mayAlias(with: loadBorrow.address, self) { return .worstEffects } return borrowEffects default: break } return defaultEffects(of: endBorrow, on: memLoc) case let debugValue as DebugValueInst: if debugValue.operand.value.type.isAddress && memLoc.mayAlias(with: debugValue.operand.value, self) { return .init(read: true) } else { return .noEffects } case let destroy as DestroyValueInst: if destroy.destroyedValue.type.isNoEscapeFunction { return .noEffects } if destroy.isDeadEnd { // We don't have to take deinit effects into acount for a `destroy_value [dead_end]`. // Such destroys are lowered to no-ops and will not call any deinit. return .noEffects } return defaultEffects(of: destroy, on: memLoc) default: let effects = inst.memoryEffects if effects == .noEffects { return effects } return defaultEffects(of: inst, on: memLoc) } } /// Returns the memory effects which protect the interior pointers of a borrowed value. /// For example, an `end_borrow` of a class reference must alias with all field addresses (= the interior /// pointers) of the class instance. private func getBorrowEffects(of endBorrow: EndBorrowInst, on memLoc: MemoryLocation) -> SideEffects.Memory { let accessPath = memLoc.address.accessPath switch accessPath.base { case .stack, .global, .argument, .storeBorrow: // Those access bases cannot be interior pointers of a borrowed value return .noEffects case .pointer, .index, .unidentified, .yield: // We don't know anything about this address -> get the conservative effects return defaultEffects(of: endBorrow, on: memLoc) case .box, .class, .tail: // Check if the memLoc is "derived" from the begin_borrow, i.e. is an interior pointer. var walker = FindBeginBorrowWalker(beginBorrow: endBorrow.borrow as! BorrowIntroducingInstruction) return walker.visitAccessStorageRoots(of: accessPath) ? .noEffects : .worstEffects } } private func getAccessScopeEffect(of beginAccess: BeginAccessInst, on memLoc: MemoryLocation) -> SideEffects.Memory { if !memLoc.mayAlias(with: beginAccess.address, self) { return .noEffects } switch beginAccess.accessKind { case .`init`: return .init(read: false, write: true) case .read: return .init(read: true, write: false) case .modify: return memLoc.isLetValue ? .noEffects : .worstEffects case .deinit: // For the same reason we treat a `load [take]` or a `destroy_addr` // as a memory write, we do that for a `begin_access [deinit]` as well. return .worstEffects } } private func getApplyEffect(of apply: FullApplySite, on memLoc: MemoryLocation) -> SideEffects.Memory { let calleeAnalysis = context.calleeAnalysis let visitor = FullApplyEffectsVisitor(apply: apply, calleeAnalysis: calleeAnalysis, isAddress: true) let memoryEffects: SideEffects.Memory // First try to figure out to which argument(s) the address "escapes" to. if let result = memLoc.addressWithPath.visit(using: visitor, initialWalkingDirection: memLoc.walkingDirection, context) { // The resulting effects are the argument effects to which `address` escapes to. memoryEffects = result.memory } else { // The address has unknown escapes. So we have to take the global effects of the called function(s). memoryEffects = calleeAnalysis.getSideEffects(ofApply: apply).memory } return memoryEffects } private func getPartialApplyEffect(of partialApply: PartialApplyInst, on memLoc: MemoryLocation) -> SideEffects.Memory { let visitor = PartialApplyEffectsVisitor(partialApply: partialApply) // Figure out to which argument(s) the address "escapes" to. if let result = memLoc.addressWithPath.visit(using: visitor, initialWalkingDirection: memLoc.walkingDirection, context) { // The resulting effects are the argument effects to which the address escapes to. return result } return .worstEffects } private func getBuiltinEffect(of builtin: BuiltinInst, on memLoc: MemoryLocation) -> SideEffects.Memory { switch builtin.id { case .Once, .OnceWithContext: if !memLoc.addressWithPath.isEscaping(using: AddressVisibleByBuiltinOnceVisitor(), initialWalkingDirection: memLoc.walkingDirection, context) { return .noEffects } let callee = builtin.operands[1].value return context.calleeAnalysis.getSideEffects(ofCallee: callee).memory default: return defaultEffects(of: builtin, on: memLoc) } } private func getOwnershipEffect(of apply: FullApplySite, for value: Value, path: SmallProjectionPath, complexityBudget: Int) -> SideEffects.Ownership { let visitor = FullApplyEffectsVisitor(apply: apply, calleeAnalysis: context.calleeAnalysis, isAddress: false) if let result = value.at(path).visit(using: visitor, complexityBudget: complexityBudget, context) { // The resulting effects are the argument effects to which `value` escapes to. return result.ownership } else { // `value` has unknown escapes. So we have to take the global effects of the called function(s). return visitor.calleeAnalysis.getSideEffects(ofApply: apply).ownership } } /// Gets the default effects of an instruction. /// It just checks if `memLoc` can somehow be visible by `inst` at all. private func defaultEffects(of inst: Instruction, on memLoc: MemoryLocation) -> SideEffects.Memory { if memLoc.addressWithPath.isEscaping(using: EscapesToInstructionVisitor(target: inst, isAddress: true), initialWalkingDirection: memLoc.walkingDirection, complexityBudget: getComplexityBudget(for: inst.parentFunction), context) { return inst.memoryEffects } return .noEffects } // To avoid quadratic complexity for large functions, we limit the amount of work that the EscapeUtils are // allowed to to. This keeps the complexity linear. // // This arbitrary limit is good enough for almost all functions. It lets // the EscapeUtils do several hundred up/down walks which is much more than needed in most cases. private func getComplexityBudget(for function: Function) -> Int { if cache.estimatedFunctionSize == nil { var numInsts = 0 for _ in function.instructions { numInsts += 1 } cache.estimatedFunctionSize = numInsts } return 1000000 / cache.estimatedFunctionSize! } /// Returns true if the `instruction` (which in general writes to memory) is immutable in a certain scope, /// defined by `address`. /// /// That means that even if we don't know anything about `instruction`, we can be sure /// that `instruction` cannot write to `address`, if it's inside the addresse's scope. /// An immutable scope is for example a read-only `begin_access`/`end_access` scope. /// Another example is a borrow scope of an immutable copy-on-write buffer. private func isImmutable(instruction: Instruction, inScopeOf address: Value) -> Bool { guard let immutableScope = ImmutableScope(for: address, context) else { return false } if case .wholeFunction = immutableScope { // No need to check if the instruction is inside the scope if the scope is the whole function. return true } if !isImmutableCacheComputed(for: immutableScope) { computeImmutableCache(for: immutableScope) } let key = Cache.ScopeKey(beginScope: immutableScope.beginScopeInstruction, instInScope: instruction) return cache.immutableInstructionsInScopes.contains(key) } private func isImmutableCacheComputed(for immutableScope: ImmutableScope) -> Bool { let beginScopeInst = immutableScope.beginScopeInstruction // The special key of (beginScopeInst, beginScopeInst) is used as a marker to check if the immutable scope // is already computed at all. let key = Cache.ScopeKey(beginScope: beginScopeInst, instInScope: beginScopeInst) return !cache.immutableInstructionsInScopes.insert(key).inserted } private func computeImmutableCache(for immutableScope: ImmutableScope) { let beginScopeInst = immutableScope.beginScopeInstruction var worklist = InstructionWorklist(context) defer { worklist.deinitialize() } immutableScope.pushEndScopeInstructions(to: &worklist) while let inst = worklist.pop() { if inst.mayWriteToMemory { if case .modifyAccess(let beginAccessInst) = immutableScope, computeMemoryEffect(of: inst, on: .modifyAccessScope(beginAccessInst)).write { } else { cache.immutableInstructionsInScopes.insert(Cache.ScopeKey(beginScope: beginScopeInst, instInScope: inst)) } } worklist.pushPredecessors(of: inst, ignoring: beginScopeInst) } } } //===--------------------------------------------------------------------===// // Internal data structures //===--------------------------------------------------------------------===// private struct Cache { struct ScopeKey: Hashable { let beginScope: Instruction let instInScope: Instruction } // Caches immutable instructions inside specific scopes. var immutableInstructionsInScopes = Set() // Used to limit complexity. The size is computed lazily. var estimatedFunctionSize: Int? = nil } // A simple abstraction for the kind of address the memory effect is computed. private enum MemoryLocation { // The usual case: an arbitrary address case memoryAddress(Value) // The address of an modify-access, within the access scope. // The difference to an arbitrary address is that we know that there are no other reads or writes to the // access-address within the access scope. // This is used when computing the immutable-scope of a `begin_access [modify]` case modifyAccessScope(BeginAccessInst) var addressWithPath: ProjectedValue { let addrValue = self.address return addrValue.at(SmallProjectionPath(.anyValueFields)) } var address: Value { switch self { case .memoryAddress(let value): precondition(value.type.isAddress, "expected address value") return value case .modifyAccessScope(let beginAccess): return beginAccess } } var walkingDirection: EscapeUtilityTypes.WalkingDirection { switch self { case .memoryAddress: // We need to consider where the address comes from return .up case .modifyAccessScope: // We don't care where the access-address comes from because we know that all accesses to the address // (in the access scope) must be derived from the `begin_access`. return .down } } var isLetValue: Bool { switch self { case .memoryAddress(let addr): return addr.accessBase.isLet case .modifyAccessScope: return false } } func mayAlias(with otherAddr: Value, _ aliasAnalysis: AliasAnalysis) -> Bool { return aliasAnalysis.mayAlias(address, otherAddr) } } /// A scope in which certain instructions can be assumed to be immutable, /// i.e. don't write to the scope's based address. private enum ImmutableScope { // If the based address is or is derived from an indirect-in or guaranteed function argument. // The scope spans over the whole function and we don't need to do any scope computation. case wholeFunction // If the based address is or is derived from a begin_access with access kind "read". case readAccess(BeginAccessInst) // If the based address is or is derived from a begin_access with access kind "modify". case modifyAccess(BeginAccessInst) // If the based address is an interior pointer (e.g. the address of a class field) of a borrowed object. case borrow(BeginBorrowValue) init?(for basedAddress: Value, _ context: FunctionPassContext) { switch basedAddress.enclosingAccessScope { case .access(let beginAccess): if beginAccess.isUnsafe { return nil } switch beginAccess.accessKind { case .read: self = .readAccess(beginAccess) case .modify: self = .modifyAccess(beginAccess) case .`init`, .deinit: return nil } case .base(let accessBase): let object: Value switch accessBase { case .class(let elementAddr): if !elementAddr.isImmutable { return nil } object = elementAddr.instance case .tail(let tailAddr): if !tailAddr.isImmutable { return nil } object = tailAddr.instance case .global(let global): if global.isLet && !basedAddress.parentFunction.canInitializeGlobal { self = .wholeFunction return } return nil default: return nil } if !object.parentFunction.hasOwnership { // Special handling for non-OSSA: we can only reason about guaranteed function arguments. var walker = IsGuaranteedFunctionArgumentWalker() if walker.walkUp(value: object, path: SmallProjectionPath()) != .continueWalk { return nil } self = .wholeFunction } else { guard let singleBorrowIntroducer = object.getBorrowIntroducers(context).singleElement else { return nil } switch singleBorrowIntroducer { case .beginBorrow, .loadBorrow, .reborrow: self = .borrow(singleBorrowIntroducer) case .functionArgument: self = .wholeFunction case .beginApply, .uncheckOwnershipConversion: return nil } } case .dependence(let markDep): // ignore mark_dependence for the purpose of alias analysis. self.init(for: markDep.value, context) } } var beginScopeInstruction: SingleValueInstruction { switch self { case .wholeFunction: fatalError("should not request the beginScopeInstruction of a whole function") case .readAccess(let beginAccess), .modifyAccess(let beginAccess): return beginAccess case .borrow(let beginBorrowValue): switch beginBorrowValue { case .beginBorrow(let bbi): return bbi case .loadBorrow(let lbi): return lbi case .reborrow(let phi): return phi.borrowedFrom! default: fatalError("unsupported BeginBorrowValue") } } } func pushEndScopeInstructions(to worklist: inout InstructionWorklist) { switch self { case .wholeFunction: fatalError("should not pushEndScopeInstructions of a whole function") case .readAccess(let beginAccess), .modifyAccess(let beginAccess): for endAccess in beginAccess.endAccessInstructions { worklist.pushPredecessors(of: endAccess, ignoring: beginAccess) } case .borrow(let beginBorrowValue): let beginScopeInst = beginScopeInstruction for endBorrowOp in beginBorrowValue.scopeEndingOperands { worklist.pushPredecessors(of: endBorrowOp.instruction, ignoring: beginScopeInst) } } } } private struct FindBeginBorrowWalker : ValueUseDefWalker { let beginBorrow: BorrowIntroducingInstruction var walkUpCache = WalkerCache() mutating func walkUp(value: Value, path: SmallProjectionPath) -> WalkResult { if value == beginBorrow { return .abortWalk } if value.ownership != .guaranteed { // If value is owned then it cannot be the borrowed value. return .continueWalk } return walkUpDefault(value: value, path: path) } mutating func rootDef(value: Value, path: SmallProjectionPath) -> WalkResult { switch value { case is FunctionArgument, // Loading a value from memory cannot be the borrowed value. // Note that we exclude the "regular" `load` by checking for guaranteed ownership in `walkUp`. is LoadBorrowInst: return .continueWalk default: return .abortWalk } } } private struct IsGuaranteedFunctionArgumentWalker : ValueUseDefWalker { var walkUpCache = WalkerCache() mutating func rootDef(value: Value, path: SmallProjectionPath) -> WalkResult { if let funcArg = value as? FunctionArgument, funcArg.convention.isGuaranteed { return .continueWalk } return .abortWalk } } // Computes the effects which a called function (potentially) has on an address. private struct FullApplyEffectsVisitor : EscapeVisitorWithResult { let apply: FullApplySite let calleeAnalysis: CalleeAnalysis let isAddress: Bool var result = SideEffects.GlobalEffects() mutating func visitUse(operand: Operand, path: EscapePath) -> UseResult { let user = operand.instruction if user is ReturnInst { // Anything which is returned cannot escape to an instruction inside the function. return .ignore } if user == apply { if apply.isCallee(operand: operand) { // If the address "escapes" to the callee of the apply it means that the address was captured // by an inout_aliasable operand of an partial_apply. // Therefore assume that the called function will both, read and write, to the address. return .abort } let e = calleeAnalysis.getSideEffects(of: apply, operand: operand, path: path.projectionPath) result.merge(with: e) } return .continueWalk } var followTrivialTypes: Bool { isAddress } var followLoads: Bool { !isAddress } } // In contrast to a full apply, the effects of a partial_apply don't depend on the callee // (a partial_apply doesn't call anything, it just creates a thick function pointer). // The only effects come from capturing the arguments (either consuming or guaranteeed). private struct PartialApplyEffectsVisitor : EscapeVisitorWithResult { let partialApply: PartialApplyInst var result = SideEffects.Memory.noEffects mutating func visitUse(operand: Operand, path: EscapePath) -> UseResult { let user = operand.instruction if user is ReturnInst { // Anything which is returned cannot escape to an instruction inside the function. return .ignore } if user == partialApply, let convention = partialApply.convention(of: operand) { switch convention { case .indirectIn, .indirectInGuaranteed: result.read = true if !partialApply.isOnStack { result.write = true } case .indirectInout, .indirectInoutAliasable, .packInout: break case .directOwned, .directUnowned, .directGuaranteed, .packOwned, .packGuaranteed: break case .indirectOut, .packOut, .indirectInCXX: fatalError("invalid convention for partial_apply") } } return .continueWalk } var followTrivialTypes: Bool { true } var followLoads: Bool { false } } private struct AddressVisibleByBuiltinOnceVisitor : EscapeVisitor { var followTrivialTypes: Bool { true } var followLoads: Bool { false } } /// Checks if a value is "escaping" to the `target` instruction. private struct EscapesToInstructionVisitor : EscapeVisitor { let target: Instruction let isAddress: Bool mutating func visitUse(operand: Operand, path: EscapePath) -> UseResult { let user = operand.instruction if user == target { return .abort } if user is ReturnInst { // Anything which is returned cannot escape to an instruction inside the function. return .ignore } return .continueWalk } var followTrivialTypes: Bool { isAddress } var followLoads: Bool { !isAddress } } private extension Value { var isImmutableAddress: Bool { switch accessBase { case .argument(let arg): return arg.convention == .indirectInGuaranteed default: return false } } } //===--------------------------------------------------------------------===// // Type-based alias analysis (TBAA) //===--------------------------------------------------------------------===// /// Perform type-based alias analysis (TBAA). private func isTypeDistinct(_ address1: Value, _ address2: Value, _ accessBase1: AccessBase, _ accessBase2: AccessBase ) -> Bool { let type1 = address1.type let type2 = address2.type if type1 == type2 { return false } if !accessBase1.isEligibleForTBAA || !accessBase2.isEligibleForTBAA { return false } if !type1.isEligibleForTBAA || !type2.isEligibleForTBAA { return false } let function = address1.parentFunction // Even if the types are different, one type can contain the other type, e.g. // // struct S { var i: Int } // isTypeDistinct(addressOfS, addressOfInt) -> false // if type1.aggregateIsOrContains(type2, in: function) || type2.aggregateIsOrContains(type1, in: function) { return false } if type1.isClass && type2.isClass { return false } return true } private extension AccessBase { func isIndirectResult(of apply: FullApplySite) -> Bool { return apply.indirectResultOperands.contains { $0.value.accessBase == self } } var isEligibleForTBAA: Bool { // Only access bases which cannot be the result of an not-strict pointer conversion are eligible. switch self { case .box, .class, .tail, .global: return true case .pointer(let pointerToAddress): return pointerToAddress.isStrict default: return false } } } private extension Type { var isEligibleForTBAA: Bool { if hasArchetype { // Two distinct types which contain archetypes can be actually the same, e.g.: // SomeGenericStruct // T is a type parameter, which can potentially also be Int // SomeGenericStruct return false } if isClass || isStruct || isEnum || isTuple { return true } // Only support the most important builtin types to be on the safe side. // Historically we assumed that Builtin.RawPointer can alias everything (but why?). if isBuiltinInteger || isBuiltinFloat { return true } return false } } private extension Function { var canInitializeGlobal: Bool { return isGlobalInitOnceFunction || // In non -parse-as-library mode globals are initialized in the `main` function. name == "main" } } //===--------------------------------------------------------------------===// // Bridging //===--------------------------------------------------------------------===// private extension SideEffects.Memory { var bridged: BridgedMemoryBehavior { switch (read, write) { case (false, false): return .None case (true, false): return .MayRead case (false, true): return .MayWrite case (true, true): return .MayReadWrite } } } private extension BridgedAliasAnalysis { var cachePointer: UnsafeRawPointer { UnsafeRawPointer(aa) } var mutableCachePointer: UnsafeMutableRawPointer { UnsafeMutableRawPointer(aa) } }