diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/ObjCARC')
19 files changed, 2429 insertions, 1917 deletions
diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ARCInstKind.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ARCInstKind.cpp new file mode 100644 index 0000000..afb873a --- /dev/null +++ b/contrib/llvm/lib/Transforms/ObjCARC/ARCInstKind.cpp @@ -0,0 +1,673 @@ +//===- ARCInstKind.cpp - ObjC ARC Optimization ----------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file defines several utility functions used by various ARC +/// optimizations which are IMHO too big to be in a header file. +/// +/// WARNING: This file knows about certain library functions. It recognizes them +/// by name, and hardwires knowledge of their semantics. +/// +/// WARNING: This file knows about how certain Objective-C library functions are +/// used. Naive LLVM IR transformations which would otherwise be +/// behavior-preserving may break these assumptions. +/// +//===----------------------------------------------------------------------===// + +#include "ObjCARC.h" +#include "llvm/IR/Intrinsics.h" + +using namespace llvm; +using namespace llvm::objcarc; + +raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, + const ARCInstKind Class) { + switch (Class) { + case ARCInstKind::Retain: + return OS << "ARCInstKind::Retain"; + case ARCInstKind::RetainRV: + return OS << "ARCInstKind::RetainRV"; + case ARCInstKind::RetainBlock: + return OS << "ARCInstKind::RetainBlock"; + case ARCInstKind::Release: + return OS << "ARCInstKind::Release"; + case ARCInstKind::Autorelease: + return OS << "ARCInstKind::Autorelease"; + case ARCInstKind::AutoreleaseRV: + return OS << "ARCInstKind::AutoreleaseRV"; + case ARCInstKind::AutoreleasepoolPush: + return OS << "ARCInstKind::AutoreleasepoolPush"; + case ARCInstKind::AutoreleasepoolPop: + return OS << "ARCInstKind::AutoreleasepoolPop"; + case ARCInstKind::NoopCast: + return OS << "ARCInstKind::NoopCast"; + case ARCInstKind::FusedRetainAutorelease: + return OS << "ARCInstKind::FusedRetainAutorelease"; + case ARCInstKind::FusedRetainAutoreleaseRV: + return OS << "ARCInstKind::FusedRetainAutoreleaseRV"; + case ARCInstKind::LoadWeakRetained: + return OS << "ARCInstKind::LoadWeakRetained"; + case ARCInstKind::StoreWeak: + return OS << "ARCInstKind::StoreWeak"; + case ARCInstKind::InitWeak: + return OS << "ARCInstKind::InitWeak"; + case ARCInstKind::LoadWeak: + return OS << "ARCInstKind::LoadWeak"; + case ARCInstKind::MoveWeak: + return OS << "ARCInstKind::MoveWeak"; + case ARCInstKind::CopyWeak: + return OS << "ARCInstKind::CopyWeak"; + case ARCInstKind::DestroyWeak: + return OS << "ARCInstKind::DestroyWeak"; + case ARCInstKind::StoreStrong: + return OS << "ARCInstKind::StoreStrong"; + case ARCInstKind::CallOrUser: + return OS << "ARCInstKind::CallOrUser"; + case ARCInstKind::Call: + return OS << "ARCInstKind::Call"; + case ARCInstKind::User: + return OS << "ARCInstKind::User"; + case ARCInstKind::IntrinsicUser: + return OS << "ARCInstKind::IntrinsicUser"; + case ARCInstKind::None: + return OS << "ARCInstKind::None"; + } + llvm_unreachable("Unknown instruction class!"); +} + +ARCInstKind llvm::objcarc::GetFunctionClass(const Function *F) { + Function::const_arg_iterator AI = F->arg_begin(), AE = F->arg_end(); + + // No (mandatory) arguments. + if (AI == AE) + return StringSwitch<ARCInstKind>(F->getName()) + .Case("objc_autoreleasePoolPush", ARCInstKind::AutoreleasepoolPush) + .Case("clang.arc.use", ARCInstKind::IntrinsicUser) + .Default(ARCInstKind::CallOrUser); + + // One argument. + const Argument *A0 = AI++; + if (AI == AE) + // Argument is a pointer. + if (PointerType *PTy = dyn_cast<PointerType>(A0->getType())) { + Type *ETy = PTy->getElementType(); + // Argument is i8*. + if (ETy->isIntegerTy(8)) + return StringSwitch<ARCInstKind>(F->getName()) + .Case("objc_retain", ARCInstKind::Retain) + .Case("objc_retainAutoreleasedReturnValue", ARCInstKind::RetainRV) + .Case("objc_retainBlock", ARCInstKind::RetainBlock) + .Case("objc_release", ARCInstKind::Release) + .Case("objc_autorelease", ARCInstKind::Autorelease) + .Case("objc_autoreleaseReturnValue", ARCInstKind::AutoreleaseRV) + .Case("objc_autoreleasePoolPop", ARCInstKind::AutoreleasepoolPop) + .Case("objc_retainedObject", ARCInstKind::NoopCast) + .Case("objc_unretainedObject", ARCInstKind::NoopCast) + .Case("objc_unretainedPointer", ARCInstKind::NoopCast) + .Case("objc_retain_autorelease", + ARCInstKind::FusedRetainAutorelease) + .Case("objc_retainAutorelease", ARCInstKind::FusedRetainAutorelease) + .Case("objc_retainAutoreleaseReturnValue", + ARCInstKind::FusedRetainAutoreleaseRV) + .Case("objc_sync_enter", ARCInstKind::User) + .Case("objc_sync_exit", ARCInstKind::User) + .Default(ARCInstKind::CallOrUser); + + // Argument is i8** + if (PointerType *Pte = dyn_cast<PointerType>(ETy)) + if (Pte->getElementType()->isIntegerTy(8)) + return StringSwitch<ARCInstKind>(F->getName()) + .Case("objc_loadWeakRetained", ARCInstKind::LoadWeakRetained) + .Case("objc_loadWeak", ARCInstKind::LoadWeak) + .Case("objc_destroyWeak", ARCInstKind::DestroyWeak) + .Default(ARCInstKind::CallOrUser); + } + + // Two arguments, first is i8**. + const Argument *A1 = AI++; + if (AI == AE) + if (PointerType *PTy = dyn_cast<PointerType>(A0->getType())) + if (PointerType *Pte = dyn_cast<PointerType>(PTy->getElementType())) + if (Pte->getElementType()->isIntegerTy(8)) + if (PointerType *PTy1 = dyn_cast<PointerType>(A1->getType())) { + Type *ETy1 = PTy1->getElementType(); + // Second argument is i8* + if (ETy1->isIntegerTy(8)) + return StringSwitch<ARCInstKind>(F->getName()) + .Case("objc_storeWeak", ARCInstKind::StoreWeak) + .Case("objc_initWeak", ARCInstKind::InitWeak) + .Case("objc_storeStrong", ARCInstKind::StoreStrong) + .Default(ARCInstKind::CallOrUser); + // Second argument is i8**. + if (PointerType *Pte1 = dyn_cast<PointerType>(ETy1)) + if (Pte1->getElementType()->isIntegerTy(8)) + return StringSwitch<ARCInstKind>(F->getName()) + .Case("objc_moveWeak", ARCInstKind::MoveWeak) + .Case("objc_copyWeak", ARCInstKind::CopyWeak) + // Ignore annotation calls. This is important to stop the + // optimizer from treating annotations as uses which would + // make the state of the pointers they are attempting to + // elucidate to be incorrect. + .Case("llvm.arc.annotation.topdown.bbstart", + ARCInstKind::None) + .Case("llvm.arc.annotation.topdown.bbend", + ARCInstKind::None) + .Case("llvm.arc.annotation.bottomup.bbstart", + ARCInstKind::None) + .Case("llvm.arc.annotation.bottomup.bbend", + ARCInstKind::None) + .Default(ARCInstKind::CallOrUser); + } + + // Anything else. + return ARCInstKind::CallOrUser; +} + +// A whitelist of intrinsics that we know do not use objc pointers or decrement +// ref counts. +static bool isInertIntrinsic(unsigned ID) { + // TODO: Make this into a covered switch. + switch (ID) { + case Intrinsic::returnaddress: + case Intrinsic::frameaddress: + case Intrinsic::stacksave: + case Intrinsic::stackrestore: + case Intrinsic::vastart: + case Intrinsic::vacopy: + case Intrinsic::vaend: + case Intrinsic::objectsize: + case Intrinsic::prefetch: + case Intrinsic::stackprotector: + case Intrinsic::eh_return_i32: + case Intrinsic::eh_return_i64: + case Intrinsic::eh_typeid_for: + case Intrinsic::eh_dwarf_cfa: + case Intrinsic::eh_sjlj_lsda: + case Intrinsic::eh_sjlj_functioncontext: + case Intrinsic::init_trampoline: + case Intrinsic::adjust_trampoline: + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + case Intrinsic::invariant_start: + case Intrinsic::invariant_end: + // Don't let dbg info affect our results. + case Intrinsic::dbg_declare: + case Intrinsic::dbg_value: + // Short cut: Some intrinsics obviously don't use ObjC pointers. + return true; + default: + return false; + } +} + +// A whitelist of intrinsics that we know do not use objc pointers or decrement +// ref counts. +static bool isUseOnlyIntrinsic(unsigned ID) { + // We are conservative and even though intrinsics are unlikely to touch + // reference counts, we white list them for safety. + // + // TODO: Expand this into a covered switch. There is a lot more here. + switch (ID) { + case Intrinsic::memcpy: + case Intrinsic::memmove: + case Intrinsic::memset: + return true; + default: + return false; + } +} + +/// \brief Determine what kind of construct V is. +ARCInstKind llvm::objcarc::GetARCInstKind(const Value *V) { + if (const Instruction *I = dyn_cast<Instruction>(V)) { + // Any instruction other than bitcast and gep with a pointer operand have a + // use of an objc pointer. Bitcasts, GEPs, Selects, PHIs transfer a pointer + // to a subsequent use, rather than using it themselves, in this sense. + // As a short cut, several other opcodes are known to have no pointer + // operands of interest. And ret is never followed by a release, so it's + // not interesting to examine. + switch (I->getOpcode()) { + case Instruction::Call: { + const CallInst *CI = cast<CallInst>(I); + // See if we have a function that we know something about. + if (const Function *F = CI->getCalledFunction()) { + ARCInstKind Class = GetFunctionClass(F); + if (Class != ARCInstKind::CallOrUser) + return Class; + Intrinsic::ID ID = F->getIntrinsicID(); + if (isInertIntrinsic(ID)) + return ARCInstKind::None; + if (isUseOnlyIntrinsic(ID)) + return ARCInstKind::User; + } + + // Otherwise, be conservative. + return GetCallSiteClass(CI); + } + case Instruction::Invoke: + // Otherwise, be conservative. + return GetCallSiteClass(cast<InvokeInst>(I)); + case Instruction::BitCast: + case Instruction::GetElementPtr: + case Instruction::Select: + case Instruction::PHI: + case Instruction::Ret: + case Instruction::Br: + case Instruction::Switch: + case Instruction::IndirectBr: + case Instruction::Alloca: + case Instruction::VAArg: + case Instruction::Add: + case Instruction::FAdd: + case Instruction::Sub: + case Instruction::FSub: + case Instruction::Mul: + case Instruction::FMul: + case Instruction::SDiv: + case Instruction::UDiv: + case Instruction::FDiv: + case Instruction::SRem: + case Instruction::URem: + case Instruction::FRem: + case Instruction::Shl: + case Instruction::LShr: + case Instruction::AShr: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + case Instruction::SExt: + case Instruction::ZExt: + case Instruction::Trunc: + case Instruction::IntToPtr: + case Instruction::FCmp: + case Instruction::FPTrunc: + case Instruction::FPExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::UIToFP: + case Instruction::SIToFP: + case Instruction::InsertElement: + case Instruction::ExtractElement: + case Instruction::ShuffleVector: + case Instruction::ExtractValue: + break; + case Instruction::ICmp: + // Comparing a pointer with null, or any other constant, isn't an + // interesting use, because we don't care what the pointer points to, or + // about the values of any other dynamic reference-counted pointers. + if (IsPotentialRetainableObjPtr(I->getOperand(1))) + return ARCInstKind::User; + break; + default: + // For anything else, check all the operands. + // Note that this includes both operands of a Store: while the first + // operand isn't actually being dereferenced, it is being stored to + // memory where we can no longer track who might read it and dereference + // it, so we have to consider it potentially used. + for (User::const_op_iterator OI = I->op_begin(), OE = I->op_end(); + OI != OE; ++OI) + if (IsPotentialRetainableObjPtr(*OI)) + return ARCInstKind::User; + } + } + + // Otherwise, it's totally inert for ARC purposes. + return ARCInstKind::None; +} + +/// \brief Test if the given class is a kind of user. +bool llvm::objcarc::IsUser(ARCInstKind Class) { + switch (Class) { + case ARCInstKind::User: + case ARCInstKind::CallOrUser: + case ARCInstKind::IntrinsicUser: + return true; + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::RetainBlock: + case ARCInstKind::Release: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::NoopCast: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::Call: + case ARCInstKind::None: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +/// \brief Test if the given class is objc_retain or equivalent. +bool llvm::objcarc::IsRetain(ARCInstKind Class) { + switch (Class) { + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + return true; + // I believe we treat retain block as not a retain since it can copy its + // block. + case ARCInstKind::RetainBlock: + case ARCInstKind::Release: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::NoopCast: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + case ARCInstKind::User: + case ARCInstKind::None: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +/// \brief Test if the given class is objc_autorelease or equivalent. +bool llvm::objcarc::IsAutorelease(ARCInstKind Class) { + switch (Class) { + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + return true; + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::RetainBlock: + case ARCInstKind::Release: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::NoopCast: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + case ARCInstKind::User: + case ARCInstKind::None: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +/// \brief Test if the given class represents instructions which return their +/// argument verbatim. +bool llvm::objcarc::IsForwarding(ARCInstKind Class) { + switch (Class) { + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::NoopCast: + return true; + case ARCInstKind::RetainBlock: + case ARCInstKind::Release: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + case ARCInstKind::User: + case ARCInstKind::None: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +/// \brief Test if the given class represents instructions which do nothing if +/// passed a null pointer. +bool llvm::objcarc::IsNoopOnNull(ARCInstKind Class) { + switch (Class) { + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::Release: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::RetainBlock: + return true; + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + case ARCInstKind::User: + case ARCInstKind::None: + case ARCInstKind::NoopCast: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +/// \brief Test if the given class represents instructions which are always safe +/// to mark with the "tail" keyword. +bool llvm::objcarc::IsAlwaysTail(ARCInstKind Class) { + // ARCInstKind::RetainBlock may be given a stack argument. + switch (Class) { + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::AutoreleaseRV: + return true; + case ARCInstKind::Release: + case ARCInstKind::Autorelease: + case ARCInstKind::RetainBlock: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + case ARCInstKind::User: + case ARCInstKind::None: + case ARCInstKind::NoopCast: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +/// \brief Test if the given class represents instructions which are never safe +/// to mark with the "tail" keyword. +bool llvm::objcarc::IsNeverTail(ARCInstKind Class) { + /// It is never safe to tail call objc_autorelease since by tail calling + /// objc_autorelease: fast autoreleasing causing our object to be potentially + /// reclaimed from the autorelease pool which violates the semantics of + /// __autoreleasing types in ARC. + switch (Class) { + case ARCInstKind::Autorelease: + return true; + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::Release: + case ARCInstKind::RetainBlock: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + case ARCInstKind::User: + case ARCInstKind::None: + case ARCInstKind::NoopCast: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +/// \brief Test if the given class represents instructions which are always safe +/// to mark with the nounwind attribute. +bool llvm::objcarc::IsNoThrow(ARCInstKind Class) { + // objc_retainBlock is not nounwind because it calls user copy constructors + // which could theoretically throw. + switch (Class) { + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::Release: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + return true; + case ARCInstKind::RetainBlock: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + case ARCInstKind::User: + case ARCInstKind::None: + case ARCInstKind::NoopCast: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +/// Test whether the given instruction can autorelease any pointer or cause an +/// autoreleasepool pop. +/// +/// This means that it *could* interrupt the RV optimization. +bool llvm::objcarc::CanInterruptRV(ARCInstKind Class) { + switch (Class) { + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + return true; + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::Release: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::RetainBlock: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::User: + case ARCInstKind::None: + case ARCInstKind::NoopCast: + return false; + } + llvm_unreachable("covered switch isn't covered?"); +} + +bool llvm::objcarc::CanDecrementRefCount(ARCInstKind Kind) { + switch (Kind) { + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::NoopCast: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::User: + case ARCInstKind::None: + return false; + + // The cases below are conservative. + + // RetainBlock can result in user defined copy constructors being called + // implying releases may occur. + case ARCInstKind::RetainBlock: + case ARCInstKind::Release: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: + case ARCInstKind::DestroyWeak: + case ARCInstKind::StoreStrong: + case ARCInstKind::CallOrUser: + case ARCInstKind::Call: + return true; + } + + llvm_unreachable("covered switch isn't covered?"); +} diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ARCInstKind.h b/contrib/llvm/lib/Transforms/ObjCARC/ARCInstKind.h new file mode 100644 index 0000000..636c65c --- /dev/null +++ b/contrib/llvm/lib/Transforms/ObjCARC/ARCInstKind.h @@ -0,0 +1,123 @@ +//===--- ARCInstKind.h - ARC instruction equivalence classes -*- C++ -*----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_TRANSFORMS_OBJCARC_ARCINSTKIND_H +#define LLVM_LIB_TRANSFORMS_OBJCARC_ARCINSTKIND_H + +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Function.h" + +namespace llvm { +namespace objcarc { + +/// \enum ARCInstKind +/// +/// \brief Equivalence classes of instructions in the ARC Model. +/// +/// Since we do not have "instructions" to represent ARC concepts in LLVM IR, +/// we instead operate on equivalence classes of instructions. +/// +/// TODO: This should be split into two enums: a runtime entry point enum +/// (possibly united with the ARCRuntimeEntrypoint class) and an enum that deals +/// with effects of instructions in the ARC model (which would handle the notion +/// of a User or CallOrUser). +enum class ARCInstKind { + Retain, ///< objc_retain + RetainRV, ///< objc_retainAutoreleasedReturnValue + RetainBlock, ///< objc_retainBlock + Release, ///< objc_release + Autorelease, ///< objc_autorelease + AutoreleaseRV, ///< objc_autoreleaseReturnValue + AutoreleasepoolPush, ///< objc_autoreleasePoolPush + AutoreleasepoolPop, ///< objc_autoreleasePoolPop + NoopCast, ///< objc_retainedObject, etc. + FusedRetainAutorelease, ///< objc_retainAutorelease + FusedRetainAutoreleaseRV, ///< objc_retainAutoreleaseReturnValue + LoadWeakRetained, ///< objc_loadWeakRetained (primitive) + StoreWeak, ///< objc_storeWeak (primitive) + InitWeak, ///< objc_initWeak (derived) + LoadWeak, ///< objc_loadWeak (derived) + MoveWeak, ///< objc_moveWeak (derived) + CopyWeak, ///< objc_copyWeak (derived) + DestroyWeak, ///< objc_destroyWeak (derived) + StoreStrong, ///< objc_storeStrong (derived) + IntrinsicUser, ///< clang.arc.use + CallOrUser, ///< could call objc_release and/or "use" pointers + Call, ///< could call objc_release + User, ///< could "use" a pointer + None ///< anything that is inert from an ARC perspective. +}; + +raw_ostream &operator<<(raw_ostream &OS, const ARCInstKind Class); + +/// \brief Test if the given class is a kind of user. +bool IsUser(ARCInstKind Class); + +/// \brief Test if the given class is objc_retain or equivalent. +bool IsRetain(ARCInstKind Class); + +/// \brief Test if the given class is objc_autorelease or equivalent. +bool IsAutorelease(ARCInstKind Class); + +/// \brief Test if the given class represents instructions which return their +/// argument verbatim. +bool IsForwarding(ARCInstKind Class); + +/// \brief Test if the given class represents instructions which do nothing if +/// passed a null pointer. +bool IsNoopOnNull(ARCInstKind Class); + +/// \brief Test if the given class represents instructions which are always safe +/// to mark with the "tail" keyword. +bool IsAlwaysTail(ARCInstKind Class); + +/// \brief Test if the given class represents instructions which are never safe +/// to mark with the "tail" keyword. +bool IsNeverTail(ARCInstKind Class); + +/// \brief Test if the given class represents instructions which are always safe +/// to mark with the nounwind attribute. +bool IsNoThrow(ARCInstKind Class); + +/// Test whether the given instruction can autorelease any pointer or cause an +/// autoreleasepool pop. +bool CanInterruptRV(ARCInstKind Class); + +/// \brief Determine if F is one of the special known Functions. If it isn't, +/// return ARCInstKind::CallOrUser. +ARCInstKind GetFunctionClass(const Function *F); + +/// \brief Determine which objc runtime call instruction class V belongs to. +/// +/// This is similar to GetARCInstKind except that it only detects objc +/// runtime calls. This allows it to be faster. +/// +static inline ARCInstKind GetBasicARCInstKind(const Value *V) { + if (const CallInst *CI = dyn_cast<CallInst>(V)) { + if (const Function *F = CI->getCalledFunction()) + return GetFunctionClass(F); + // Otherwise, be conservative. + return ARCInstKind::CallOrUser; + } + + // Otherwise, be conservative. + return isa<InvokeInst>(V) ? ARCInstKind::CallOrUser : ARCInstKind::User; +} + +/// Map V to its ARCInstKind equivalence class. +ARCInstKind GetARCInstKind(const Value *V); + +/// Returns false if conservatively we can prove that any instruction mapped to +/// this kind can not decrement ref counts. Returns true otherwise. +bool CanDecrementRefCount(ARCInstKind Kind); + +} // end namespace objcarc +} // end namespace llvm + +#endif diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ARCRuntimeEntryPoints.h b/contrib/llvm/lib/Transforms/ObjCARC/ARCRuntimeEntryPoints.h index e286dbc..d4fef10 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ARCRuntimeEntryPoints.h +++ b/contrib/llvm/lib/Transforms/ObjCARC/ARCRuntimeEntryPoints.h @@ -27,22 +27,22 @@ namespace llvm { namespace objcarc { +enum class ARCRuntimeEntryPointKind { + AutoreleaseRV, + Release, + Retain, + RetainBlock, + Autorelease, + StoreStrong, + RetainRV, + RetainAutorelease, + RetainAutoreleaseRV, +}; + /// Declarations for ObjC runtime functions and constants. These are initialized /// lazily to avoid cluttering up the Module with unused declarations. class ARCRuntimeEntryPoints { public: - enum EntryPointType { - EPT_AutoreleaseRV, - EPT_Release, - EPT_Retain, - EPT_RetainBlock, - EPT_Autorelease, - EPT_StoreStrong, - EPT_RetainRV, - EPT_RetainAutorelease, - EPT_RetainAutoreleaseRV - }; - ARCRuntimeEntryPoints() : TheModule(nullptr), AutoreleaseRV(nullptr), Release(nullptr), @@ -54,9 +54,7 @@ public: RetainAutorelease(nullptr), RetainAutoreleaseRV(nullptr) { } - ~ARCRuntimeEntryPoints() { } - - void Initialize(Module *M) { + void init(Module *M) { TheModule = M; AutoreleaseRV = nullptr; Release = nullptr; @@ -69,30 +67,30 @@ public: RetainAutoreleaseRV = nullptr; } - Constant *get(const EntryPointType entry) { + Constant *get(ARCRuntimeEntryPointKind kind) { assert(TheModule != nullptr && "Not initialized."); - switch (entry) { - case EPT_AutoreleaseRV: + switch (kind) { + case ARCRuntimeEntryPointKind::AutoreleaseRV: return getI8XRetI8XEntryPoint(AutoreleaseRV, "objc_autoreleaseReturnValue", true); - case EPT_Release: + case ARCRuntimeEntryPointKind::Release: return getVoidRetI8XEntryPoint(Release, "objc_release"); - case EPT_Retain: + case ARCRuntimeEntryPointKind::Retain: return getI8XRetI8XEntryPoint(Retain, "objc_retain", true); - case EPT_RetainBlock: + case ARCRuntimeEntryPointKind::RetainBlock: return getI8XRetI8XEntryPoint(RetainBlock, "objc_retainBlock", false); - case EPT_Autorelease: + case ARCRuntimeEntryPointKind::Autorelease: return getI8XRetI8XEntryPoint(Autorelease, "objc_autorelease", true); - case EPT_StoreStrong: + case ARCRuntimeEntryPointKind::StoreStrong: return getI8XRetI8XXI8XEntryPoint(StoreStrong, "objc_storeStrong"); - case EPT_RetainRV: + case ARCRuntimeEntryPointKind::RetainRV: return getI8XRetI8XEntryPoint(RetainRV, "objc_retainAutoreleasedReturnValue", true); - case EPT_RetainAutorelease: + case ARCRuntimeEntryPointKind::RetainAutorelease: return getI8XRetI8XEntryPoint(RetainAutorelease, "objc_retainAutorelease", true); - case EPT_RetainAutoreleaseRV: + case ARCRuntimeEntryPointKind::RetainAutoreleaseRV: return getI8XRetI8XEntryPoint(RetainAutoreleaseRV, "objc_retainAutoreleaseReturnValue", true); } diff --git a/contrib/llvm/lib/Transforms/ObjCARC/BlotMapVector.h b/contrib/llvm/lib/Transforms/ObjCARC/BlotMapVector.h new file mode 100644 index 0000000..d6439b6 --- /dev/null +++ b/contrib/llvm/lib/Transforms/ObjCARC/BlotMapVector.h @@ -0,0 +1,108 @@ +//===- BlotMapVector.h - A MapVector with the blot operation -*- C++ -*----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/DenseMap.h" +#include <vector> +#include <algorithm> + +namespace llvm { +/// \brief An associative container with fast insertion-order (deterministic) +/// iteration over its elements. Plus the special blot operation. +template <class KeyT, class ValueT> class BlotMapVector { + /// Map keys to indices in Vector. + typedef DenseMap<KeyT, size_t> MapTy; + MapTy Map; + + typedef std::vector<std::pair<KeyT, ValueT>> VectorTy; + /// Keys and values. + VectorTy Vector; + +public: + typedef typename VectorTy::iterator iterator; + typedef typename VectorTy::const_iterator const_iterator; + iterator begin() { return Vector.begin(); } + iterator end() { return Vector.end(); } + const_iterator begin() const { return Vector.begin(); } + const_iterator end() const { return Vector.end(); } + +#ifdef XDEBUG + ~BlotMapVector() { + assert(Vector.size() >= Map.size()); // May differ due to blotting. + for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); I != E; + ++I) { + assert(I->second < Vector.size()); + assert(Vector[I->second].first == I->first); + } + for (typename VectorTy::const_iterator I = Vector.begin(), E = Vector.end(); + I != E; ++I) + assert(!I->first || (Map.count(I->first) && + Map[I->first] == size_t(I - Vector.begin()))); + } +#endif + + ValueT &operator[](const KeyT &Arg) { + std::pair<typename MapTy::iterator, bool> Pair = + Map.insert(std::make_pair(Arg, size_t(0))); + if (Pair.second) { + size_t Num = Vector.size(); + Pair.first->second = Num; + Vector.push_back(std::make_pair(Arg, ValueT())); + return Vector[Num].second; + } + return Vector[Pair.first->second].second; + } + + std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &InsertPair) { + std::pair<typename MapTy::iterator, bool> Pair = + Map.insert(std::make_pair(InsertPair.first, size_t(0))); + if (Pair.second) { + size_t Num = Vector.size(); + Pair.first->second = Num; + Vector.push_back(InsertPair); + return std::make_pair(Vector.begin() + Num, true); + } + return std::make_pair(Vector.begin() + Pair.first->second, false); + } + + iterator find(const KeyT &Key) { + typename MapTy::iterator It = Map.find(Key); + if (It == Map.end()) + return Vector.end(); + return Vector.begin() + It->second; + } + + const_iterator find(const KeyT &Key) const { + typename MapTy::const_iterator It = Map.find(Key); + if (It == Map.end()) + return Vector.end(); + return Vector.begin() + It->second; + } + + /// This is similar to erase, but instead of removing the element from the + /// vector, it just zeros out the key in the vector. This leaves iterators + /// intact, but clients must be prepared for zeroed-out keys when iterating. + void blot(const KeyT &Key) { + typename MapTy::iterator It = Map.find(Key); + if (It == Map.end()) + return; + Vector[It->second].first = KeyT(); + Map.erase(It); + } + + void clear() { + Map.clear(); + Vector.clear(); + } + + bool empty() const { + assert(Map.empty() == Vector.empty()); + return Map.empty(); + } +}; +} // diff --git a/contrib/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.cpp b/contrib/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.cpp index f6c236c..4edd029 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.cpp +++ b/contrib/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.cpp @@ -32,21 +32,20 @@ using namespace llvm::objcarc; /// Test whether the given instruction can result in a reference count /// modification (positive or negative) for the pointer's object. -bool -llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr, - ProvenanceAnalysis &PA, - InstructionClass Class) { +bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, + ARCInstKind Class) { switch (Class) { - case IC_Autorelease: - case IC_AutoreleaseRV: - case IC_IntrinsicUser: - case IC_User: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::User: // These operations never directly modify a reference count. return false; default: break; } - ImmutableCallSite CS = static_cast<const Value *>(Inst); + ImmutableCallSite CS(Inst); assert(CS && "Only calls can alter reference counts!"); // See if AliasAnalysis can help us with the call. @@ -54,10 +53,12 @@ llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr, if (AliasAnalysis::onlyReadsMemory(MRB)) return false; if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { + const DataLayout &DL = Inst->getModule()->getDataLayout(); for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) { const Value *Op = *I; - if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) + if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && + PA.related(Ptr, Op, DL)) return true; } return false; @@ -67,15 +68,29 @@ llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr, return true; } +bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst, + const Value *Ptr, + ProvenanceAnalysis &PA, + ARCInstKind Class) { + // First perform a quick check if Class can not touch ref counts. + if (!CanDecrementRefCount(Class)) + return false; + + // Otherwise, just use CanAlterRefCount for now. + return CanAlterRefCount(Inst, Ptr, PA, Class); +} + /// Test whether the given instruction can "use" the given pointer's object in a /// way that requires the reference count to be positive. -bool -llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr, - ProvenanceAnalysis &PA, InstructionClass Class) { - // IC_Call operations (as opposed to IC_CallOrUser) never "use" objc pointers. - if (Class == IC_Call) +bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, ARCInstKind Class) { + // ARCInstKind::Call operations (as opposed to + // ARCInstKind::CallOrUser) never "use" objc pointers. + if (Class == ARCInstKind::Call) return false; + const DataLayout &DL = Inst->getModule()->getDataLayout(); + // Consider various instructions which may have pointer arguments which are // not "uses". if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) { @@ -84,29 +99,31 @@ llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr, // of any other dynamic reference-counted pointers. if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA())) return false; - } else if (ImmutableCallSite CS = static_cast<const Value *>(Inst)) { + } else if (auto CS = ImmutableCallSite(Inst)) { // For calls, just check the arguments (and not the callee operand). for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(), OE = CS.arg_end(); OI != OE; ++OI) { const Value *Op = *OI; - if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) + if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && + PA.related(Ptr, Op, DL)) return true; } return false; } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { // Special-case stores, because we don't care about the stored value, just // the store address. - const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand()); + const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL); // If we can't tell what the underlying object was, assume there is a // dependence. - return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Op, Ptr); + return IsPotentialRetainableObjPtr(Op, *PA.getAA()) && + PA.related(Op, Ptr, DL); } // Check each operand for a match. for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end(); OI != OE; ++OI) { const Value *Op = *OI; - if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op)) + if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL)) return true; } return false; @@ -123,11 +140,11 @@ llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, switch (Flavor) { case NeedsPositiveRetainCount: { - InstructionClass Class = GetInstructionClass(Inst); + ARCInstKind Class = GetARCInstKind(Inst); switch (Class) { - case IC_AutoreleasepoolPop: - case IC_AutoreleasepoolPush: - case IC_None: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::None: return false; default: return CanUse(Inst, Arg, PA, Class); @@ -135,10 +152,10 @@ llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, } case AutoreleasePoolBoundary: { - InstructionClass Class = GetInstructionClass(Inst); + ARCInstKind Class = GetARCInstKind(Inst); switch (Class) { - case IC_AutoreleasepoolPop: - case IC_AutoreleasepoolPush: + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::AutoreleasepoolPush: // These mark the end and begin of an autorelease pool scope. return true; default: @@ -148,13 +165,13 @@ llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, } case CanChangeRetainCount: { - InstructionClass Class = GetInstructionClass(Inst); + ARCInstKind Class = GetARCInstKind(Inst); switch (Class) { - case IC_AutoreleasepoolPop: + case ARCInstKind::AutoreleasepoolPop: // Conservatively assume this can decrement any count. return true; - case IC_AutoreleasepoolPush: - case IC_None: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::None: return false; default: return CanAlterRefCount(Inst, Arg, PA, Class); @@ -162,28 +179,28 @@ llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, } case RetainAutoreleaseDep: - switch (GetBasicInstructionClass(Inst)) { - case IC_AutoreleasepoolPop: - case IC_AutoreleasepoolPush: + switch (GetBasicARCInstKind(Inst)) { + case ARCInstKind::AutoreleasepoolPop: + case ARCInstKind::AutoreleasepoolPush: // Don't merge an objc_autorelease with an objc_retain inside a different // autoreleasepool scope. return true; - case IC_Retain: - case IC_RetainRV: + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: // Check for a retain of the same pointer for merging. - return GetObjCArg(Inst) == Arg; + return GetArgRCIdentityRoot(Inst) == Arg; default: // Nothing else matters for objc_retainAutorelease formation. return false; } case RetainAutoreleaseRVDep: { - InstructionClass Class = GetBasicInstructionClass(Inst); + ARCInstKind Class = GetBasicARCInstKind(Inst); switch (Class) { - case IC_Retain: - case IC_RetainRV: + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: // Check for a retain of the same pointer for merging. - return GetObjCArg(Inst) == Arg; + return GetArgRCIdentityRoot(Inst) == Arg; default: // Anything that can autorelease interrupts // retainAutoreleaseReturnValue formation. @@ -192,7 +209,7 @@ llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst, } case RetainRVDep: - return CanInterruptRV(GetBasicInstructionClass(Inst)); + return CanInterruptRV(GetBasicARCInstKind(Inst)); } llvm_unreachable("Invalid dependence flavor"); diff --git a/contrib/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.h b/contrib/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.h index 7b5601a..8e042d4 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.h +++ b/contrib/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.h @@ -63,15 +63,24 @@ Depends(DependenceKind Flavor, Instruction *Inst, const Value *Arg, /// Test whether the given instruction can "use" the given pointer's object in a /// way that requires the reference count to be positive. -bool -CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, - InstructionClass Class); +bool CanUse(const Instruction *Inst, const Value *Ptr, ProvenanceAnalysis &PA, + ARCInstKind Class); /// Test whether the given instruction can result in a reference count /// modification (positive or negative) for the pointer's object. -bool -CanAlterRefCount(const Instruction *Inst, const Value *Ptr, - ProvenanceAnalysis &PA, InstructionClass Class); +bool CanAlterRefCount(const Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, ARCInstKind Class); + +/// Returns true if we can not conservatively prove that Inst can not decrement +/// the reference count of Ptr. Returns false if we can. +bool CanDecrementRefCount(const Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, ARCInstKind Class); + +static inline bool CanDecrementRefCount(const Instruction *Inst, + const Value *Ptr, + ProvenanceAnalysis &PA) { + return CanDecrementRefCount(Inst, Ptr, PA, GetARCInstKind(Inst)); +} } // namespace objcarc } // namespace llvm diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARC.h b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARC.h index 7a7eae8..7595e2d 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARC.h +++ b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARC.h @@ -24,6 +24,7 @@ #define LLVM_LIB_TRANSFORMS_OBJCARC_OBJCARC_H #include "llvm/ADT/StringSwitch.h" +#include "llvm/ADT/Optional.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ValueTracking.h" @@ -33,6 +34,7 @@ #include "llvm/Pass.h" #include "llvm/Transforms/ObjCARC.h" #include "llvm/Transforms/Utils/Local.h" +#include "ARCInstKind.h" namespace llvm { class raw_ostream; @@ -68,160 +70,14 @@ static inline bool ModuleHasARC(const Module &M) { M.getNamedValue("clang.arc.use"); } -/// \enum InstructionClass -/// \brief A simple classification for instructions. -enum InstructionClass { - IC_Retain, ///< objc_retain - IC_RetainRV, ///< objc_retainAutoreleasedReturnValue - IC_RetainBlock, ///< objc_retainBlock - IC_Release, ///< objc_release - IC_Autorelease, ///< objc_autorelease - IC_AutoreleaseRV, ///< objc_autoreleaseReturnValue - IC_AutoreleasepoolPush, ///< objc_autoreleasePoolPush - IC_AutoreleasepoolPop, ///< objc_autoreleasePoolPop - IC_NoopCast, ///< objc_retainedObject, etc. - IC_FusedRetainAutorelease, ///< objc_retainAutorelease - IC_FusedRetainAutoreleaseRV, ///< objc_retainAutoreleaseReturnValue - IC_LoadWeakRetained, ///< objc_loadWeakRetained (primitive) - IC_StoreWeak, ///< objc_storeWeak (primitive) - IC_InitWeak, ///< objc_initWeak (derived) - IC_LoadWeak, ///< objc_loadWeak (derived) - IC_MoveWeak, ///< objc_moveWeak (derived) - IC_CopyWeak, ///< objc_copyWeak (derived) - IC_DestroyWeak, ///< objc_destroyWeak (derived) - IC_StoreStrong, ///< objc_storeStrong (derived) - IC_IntrinsicUser, ///< clang.arc.use - IC_CallOrUser, ///< could call objc_release and/or "use" pointers - IC_Call, ///< could call objc_release - IC_User, ///< could "use" a pointer - IC_None ///< anything else -}; - -raw_ostream &operator<<(raw_ostream &OS, const InstructionClass Class); - -/// \brief Test if the given class is a kind of user. -inline static bool IsUser(InstructionClass Class) { - return Class == IC_User || - Class == IC_CallOrUser || - Class == IC_IntrinsicUser; -} - -/// \brief Test if the given class is objc_retain or equivalent. -static inline bool IsRetain(InstructionClass Class) { - return Class == IC_Retain || - Class == IC_RetainRV; -} - -/// \brief Test if the given class is objc_autorelease or equivalent. -static inline bool IsAutorelease(InstructionClass Class) { - return Class == IC_Autorelease || - Class == IC_AutoreleaseRV; -} - -/// \brief Test if the given class represents instructions which return their -/// argument verbatim. -static inline bool IsForwarding(InstructionClass Class) { - return Class == IC_Retain || - Class == IC_RetainRV || - Class == IC_Autorelease || - Class == IC_AutoreleaseRV || - Class == IC_NoopCast; -} - -/// \brief Test if the given class represents instructions which do nothing if -/// passed a null pointer. -static inline bool IsNoopOnNull(InstructionClass Class) { - return Class == IC_Retain || - Class == IC_RetainRV || - Class == IC_Release || - Class == IC_Autorelease || - Class == IC_AutoreleaseRV || - Class == IC_RetainBlock; -} - -/// \brief Test if the given class represents instructions which are always safe -/// to mark with the "tail" keyword. -static inline bool IsAlwaysTail(InstructionClass Class) { - // IC_RetainBlock may be given a stack argument. - return Class == IC_Retain || - Class == IC_RetainRV || - Class == IC_AutoreleaseRV; -} - -/// \brief Test if the given class represents instructions which are never safe -/// to mark with the "tail" keyword. -static inline bool IsNeverTail(InstructionClass Class) { - /// It is never safe to tail call objc_autorelease since by tail calling - /// objc_autorelease, we also tail call -[NSObject autorelease] which supports - /// fast autoreleasing causing our object to be potentially reclaimed from the - /// autorelease pool which violates the semantics of __autoreleasing types in - /// ARC. - return Class == IC_Autorelease; -} - -/// \brief Test if the given class represents instructions which are always safe -/// to mark with the nounwind attribute. -static inline bool IsNoThrow(InstructionClass Class) { - // objc_retainBlock is not nounwind because it calls user copy constructors - // which could theoretically throw. - return Class == IC_Retain || - Class == IC_RetainRV || - Class == IC_Release || - Class == IC_Autorelease || - Class == IC_AutoreleaseRV || - Class == IC_AutoreleasepoolPush || - Class == IC_AutoreleasepoolPop; -} - -/// Test whether the given instruction can autorelease any pointer or cause an -/// autoreleasepool pop. -static inline bool -CanInterruptRV(InstructionClass Class) { - switch (Class) { - case IC_AutoreleasepoolPop: - case IC_CallOrUser: - case IC_Call: - case IC_Autorelease: - case IC_AutoreleaseRV: - case IC_FusedRetainAutorelease: - case IC_FusedRetainAutoreleaseRV: - return true; - default: - return false; - } -} - -/// \brief Determine if F is one of the special known Functions. If it isn't, -/// return IC_CallOrUser. -InstructionClass GetFunctionClass(const Function *F); - -/// \brief Determine which objc runtime call instruction class V belongs to. -/// -/// This is similar to GetInstructionClass except that it only detects objc -/// runtime calls. This allows it to be faster. -/// -static inline InstructionClass GetBasicInstructionClass(const Value *V) { - if (const CallInst *CI = dyn_cast<CallInst>(V)) { - if (const Function *F = CI->getCalledFunction()) - return GetFunctionClass(F); - // Otherwise, be conservative. - return IC_CallOrUser; - } - - // Otherwise, be conservative. - return isa<InvokeInst>(V) ? IC_CallOrUser : IC_User; -} - -/// \brief Determine what kind of construct V is. -InstructionClass GetInstructionClass(const Value *V); - /// \brief This is a wrapper around getUnderlyingObject which also knows how to /// look through objc_retain and objc_autorelease calls, which we know to return /// their argument verbatim. -static inline const Value *GetUnderlyingObjCPtr(const Value *V) { +static inline const Value *GetUnderlyingObjCPtr(const Value *V, + const DataLayout &DL) { for (;;) { - V = GetUnderlyingObject(V); - if (!IsForwarding(GetBasicInstructionClass(V))) + V = GetUnderlyingObject(V, DL); + if (!IsForwarding(GetBasicARCInstKind(V))) break; V = cast<CallInst>(V)->getArgOperand(0); } @@ -229,37 +85,44 @@ static inline const Value *GetUnderlyingObjCPtr(const Value *V) { return V; } -/// \brief This is a wrapper around Value::stripPointerCasts which also knows -/// how to look through objc_retain and objc_autorelease calls, which we know to -/// return their argument verbatim. -static inline const Value *StripPointerCastsAndObjCCalls(const Value *V) { +/// The RCIdentity root of a value \p V is a dominating value U for which +/// retaining or releasing U is equivalent to retaining or releasing V. In other +/// words, ARC operations on \p V are equivalent to ARC operations on \p U. +/// +/// We use this in the ARC optimizer to make it easier to match up ARC +/// operations by always mapping ARC operations to RCIdentityRoots instead of +/// pointers themselves. +/// +/// The two ways that we see RCIdentical values in ObjC are via: +/// +/// 1. PointerCasts +/// 2. Forwarding Calls that return their argument verbatim. +/// +/// Thus this function strips off pointer casts and forwarding calls. *NOTE* +/// This implies that two RCIdentical values must alias. +static inline const Value *GetRCIdentityRoot(const Value *V) { for (;;) { V = V->stripPointerCasts(); - if (!IsForwarding(GetBasicInstructionClass(V))) + if (!IsForwarding(GetBasicARCInstKind(V))) break; V = cast<CallInst>(V)->getArgOperand(0); } return V; } -/// \brief This is a wrapper around Value::stripPointerCasts which also knows -/// how to look through objc_retain and objc_autorelease calls, which we know to -/// return their argument verbatim. -static inline Value *StripPointerCastsAndObjCCalls(Value *V) { - for (;;) { - V = V->stripPointerCasts(); - if (!IsForwarding(GetBasicInstructionClass(V))) - break; - V = cast<CallInst>(V)->getArgOperand(0); - } - return V; +/// Helper which calls const Value *GetRCIdentityRoot(const Value *V) and just +/// casts away the const of the result. For documentation about what an +/// RCIdentityRoot (and by extension GetRCIdentityRoot is) look at that +/// function. +static inline Value *GetRCIdentityRoot(Value *V) { + return const_cast<Value *>(GetRCIdentityRoot((const Value *)V)); } /// \brief Assuming the given instruction is one of the special calls such as -/// objc_retain or objc_release, return the argument value, stripped of no-op -/// casts and forwarding calls. -static inline Value *GetObjCArg(Value *Inst) { - return StripPointerCastsAndObjCCalls(cast<CallInst>(Inst)->getArgOperand(0)); +/// objc_retain or objc_release, return the RCIdentity root of the argument of +/// the call. +static inline Value *GetArgRCIdentityRoot(Value *Inst) { + return GetRCIdentityRoot(cast<CallInst>(Inst)->getArgOperand(0)); } static inline bool IsNullOrUndef(const Value *V) { @@ -286,8 +149,8 @@ static inline void EraseInstruction(Instruction *CI) { if (!Unused) { // Replace the return value with the argument. - assert((IsForwarding(GetBasicInstructionClass(CI)) || - (IsNoopOnNull(GetBasicInstructionClass(CI)) && + assert((IsForwarding(GetBasicARCInstKind(CI)) || + (IsNoopOnNull(GetBasicARCInstKind(CI)) && isa<ConstantPointerNull>(OldArg))) && "Can't delete non-forwarding instruction with users!"); CI->replaceAllUsesWith(OldArg); @@ -344,15 +207,15 @@ static inline bool IsPotentialRetainableObjPtr(const Value *Op, return true; } -/// \brief Helper for GetInstructionClass. Determines what kind of construct CS +/// \brief Helper for GetARCInstKind. Determines what kind of construct CS /// is. -static inline InstructionClass GetCallSiteClass(ImmutableCallSite CS) { +static inline ARCInstKind GetCallSiteClass(ImmutableCallSite CS) { for (ImmutableCallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) if (IsPotentialRetainableObjPtr(*I)) - return CS.onlyReadsMemory() ? IC_User : IC_CallOrUser; + return CS.onlyReadsMemory() ? ARCInstKind::User : ARCInstKind::CallOrUser; - return CS.onlyReadsMemory() ? IC_None : IC_Call; + return CS.onlyReadsMemory() ? ARCInstKind::None : ARCInstKind::Call; } /// \brief Return true if this value refers to a distinct and identifiable @@ -371,7 +234,7 @@ static inline bool IsObjCIdentifiedObject(const Value *V) { if (const LoadInst *LI = dyn_cast<LoadInst>(V)) { const Value *Pointer = - StripPointerCastsAndObjCCalls(LI->getPointerOperand()); + GetRCIdentityRoot(LI->getPointerOperand()); if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Pointer)) { // A constant pointer can't be pointing to an object on the heap. It may // be reference-counted, but it won't be deleted. @@ -396,6 +259,55 @@ static inline bool IsObjCIdentifiedObject(const Value *V) { return false; } +enum class ARCMDKindID { + ImpreciseRelease, + CopyOnEscape, + NoObjCARCExceptions, +}; + +/// A cache of MDKinds used by various ARC optimizations. +class ARCMDKindCache { + Module *M; + + /// The Metadata Kind for clang.imprecise_release metadata. + llvm::Optional<unsigned> ImpreciseReleaseMDKind; + + /// The Metadata Kind for clang.arc.copy_on_escape metadata. + llvm::Optional<unsigned> CopyOnEscapeMDKind; + + /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata. + llvm::Optional<unsigned> NoObjCARCExceptionsMDKind; + +public: + void init(Module *Mod) { + M = Mod; + ImpreciseReleaseMDKind = NoneType::None; + CopyOnEscapeMDKind = NoneType::None; + NoObjCARCExceptionsMDKind = NoneType::None; + } + + unsigned get(ARCMDKindID ID) { + switch (ID) { + case ARCMDKindID::ImpreciseRelease: + if (!ImpreciseReleaseMDKind) + ImpreciseReleaseMDKind = + M->getContext().getMDKindID("clang.imprecise_release"); + return *ImpreciseReleaseMDKind; + case ARCMDKindID::CopyOnEscape: + if (!CopyOnEscapeMDKind) + CopyOnEscapeMDKind = + M->getContext().getMDKindID("clang.arc.copy_on_escape"); + return *CopyOnEscapeMDKind; + case ARCMDKindID::NoObjCARCExceptions: + if (!NoObjCARCExceptionsMDKind) + NoObjCARCExceptionsMDKind = + M->getContext().getMDKindID("clang.arc.no_objc_arc_exceptions"); + return *NoObjCARCExceptionsMDKind; + } + llvm_unreachable("Covered switch isn't covered?!"); + } +}; + } // end namespace objcarc } // end namespace llvm diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp index 1a25391..d318643 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp +++ b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp @@ -97,11 +97,11 @@ bool ObjCARCAPElim::OptimizeBB(BasicBlock *BB) { Instruction *Push = nullptr; for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { Instruction *Inst = I++; - switch (GetBasicInstructionClass(Inst)) { - case IC_AutoreleasepoolPush: + switch (GetBasicARCInstKind(Inst)) { + case ARCInstKind::AutoreleasepoolPush: Push = Inst; break; - case IC_AutoreleasepoolPop: + case ARCInstKind::AutoreleasepoolPop: // If this pop matches a push and nothing in between can autorelease, // zap the pair. if (Push && cast<CallInst>(Inst)->getArgOperand(0) == Push) { @@ -115,7 +115,7 @@ bool ObjCARCAPElim::OptimizeBB(BasicBlock *BB) { } Push = nullptr; break; - case IC_CallOrUser: + case ARCInstKind::CallOrUser: if (MayAutorelease(ImmutableCallSite(Inst))) Push = nullptr; break; diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAliasAnalysis.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAliasAnalysis.cpp index c61b6b0..b1515e3 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAliasAnalysis.cpp +++ b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAliasAnalysis.cpp @@ -46,6 +46,11 @@ ImmutablePass *llvm::createObjCARCAliasAnalysisPass() { return new ObjCARCAliasAnalysis(); } +bool ObjCARCAliasAnalysis::doInitialization(Module &M) { + InitializeAliasAnalysis(this, &M.getDataLayout()); + return true; +} + void ObjCARCAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); @@ -59,8 +64,8 @@ ObjCARCAliasAnalysis::alias(const Location &LocA, const Location &LocB) { // First, strip off no-ops, including ObjC-specific no-ops, and try making a // precise alias query. - const Value *SA = StripPointerCastsAndObjCCalls(LocA.Ptr); - const Value *SB = StripPointerCastsAndObjCCalls(LocB.Ptr); + const Value *SA = GetRCIdentityRoot(LocA.Ptr); + const Value *SB = GetRCIdentityRoot(LocB.Ptr); AliasResult Result = AliasAnalysis::alias(Location(SA, LocA.Size, LocA.AATags), Location(SB, LocB.Size, LocB.AATags)); @@ -69,8 +74,8 @@ ObjCARCAliasAnalysis::alias(const Location &LocA, const Location &LocB) { // If that failed, climb to the underlying object, including climbing through // ObjC-specific no-ops, and try making an imprecise alias query. - const Value *UA = GetUnderlyingObjCPtr(SA); - const Value *UB = GetUnderlyingObjCPtr(SB); + const Value *UA = GetUnderlyingObjCPtr(SA, *DL); + const Value *UB = GetUnderlyingObjCPtr(SB, *DL); if (UA != SA || UB != SB) { Result = AliasAnalysis::alias(Location(UA), Location(UB)); // We can't use MustAlias or PartialAlias results here because @@ -92,14 +97,14 @@ ObjCARCAliasAnalysis::pointsToConstantMemory(const Location &Loc, // First, strip off no-ops, including ObjC-specific no-ops, and try making // a precise alias query. - const Value *S = StripPointerCastsAndObjCCalls(Loc.Ptr); + const Value *S = GetRCIdentityRoot(Loc.Ptr); if (AliasAnalysis::pointsToConstantMemory(Location(S, Loc.Size, Loc.AATags), OrLocal)) return true; // If that failed, climb to the underlying object, including climbing through // ObjC-specific no-ops, and try making an imprecise alias query. - const Value *U = GetUnderlyingObjCPtr(S); + const Value *U = GetUnderlyingObjCPtr(S, *DL); if (U != S) return AliasAnalysis::pointsToConstantMemory(Location(U), OrLocal); @@ -120,7 +125,7 @@ ObjCARCAliasAnalysis::getModRefBehavior(const Function *F) { return AliasAnalysis::getModRefBehavior(F); switch (GetFunctionClass(F)) { - case IC_NoopCast: + case ARCInstKind::NoopCast: return DoesNotAccessMemory; default: break; @@ -134,15 +139,15 @@ ObjCARCAliasAnalysis::getModRefInfo(ImmutableCallSite CS, const Location &Loc) { if (!EnableARCOpts) return AliasAnalysis::getModRefInfo(CS, Loc); - switch (GetBasicInstructionClass(CS.getInstruction())) { - case IC_Retain: - case IC_RetainRV: - case IC_Autorelease: - case IC_AutoreleaseRV: - case IC_NoopCast: - case IC_AutoreleasepoolPush: - case IC_FusedRetainAutorelease: - case IC_FusedRetainAutoreleaseRV: + switch (GetBasicARCInstKind(CS.getInstruction())) { + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::NoopCast: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: // These functions don't access any memory visible to the compiler. // Note that this doesn't include objc_retainBlock, because it updates // pointers when it copies block data. diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAliasAnalysis.h b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAliasAnalysis.h index 3fcea4e..3c5a021 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAliasAnalysis.h +++ b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCAliasAnalysis.h @@ -44,9 +44,7 @@ namespace objcarc { } private: - void initializePass() override { - InitializeAliasAnalysis(this); - } + bool doInitialization(Module &M) override; /// This method is used when a pass implements an analysis interface through /// multiple inheritance. If needed, it should override this to adjust the diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp index eb325eb..e7731ad 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp +++ b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp @@ -35,6 +35,7 @@ #include "llvm/IR/InlineAsm.h" #include "llvm/IR/Operator.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; using namespace llvm::objcarc; @@ -44,6 +45,10 @@ using namespace llvm::objcarc; STATISTIC(NumPeeps, "Number of calls peephole-optimized"); STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed"); +//===----------------------------------------------------------------------===// +// Declarations +//===----------------------------------------------------------------------===// + namespace { /// \brief Late ARC optimizations /// @@ -68,17 +73,23 @@ namespace { /// "tail". SmallPtrSet<CallInst *, 8> StoreStrongCalls; - bool OptimizeRetainCall(Function &F, Instruction *Retain); + /// Returns true if we eliminated Inst. + bool tryToPeepholeInstruction(Function &F, Instruction *Inst, + inst_iterator &Iter, + SmallPtrSetImpl<Instruction *> &DepInsts, + SmallPtrSetImpl<const BasicBlock *> &Visited, + bool &TailOkForStoreStrong); - bool ContractAutorelease(Function &F, Instruction *Autorelease, - InstructionClass Class, - SmallPtrSetImpl<Instruction *> - &DependingInstructions, - SmallPtrSetImpl<const BasicBlock *> - &Visited); + bool optimizeRetainCall(Function &F, Instruction *Retain); - void ContractRelease(Instruction *Release, - inst_iterator &Iter); + bool + contractAutorelease(Function &F, Instruction *Autorelease, + ARCInstKind Class, + SmallPtrSetImpl<Instruction *> &DependingInstructions, + SmallPtrSetImpl<const BasicBlock *> &Visited); + + void tryToContractReleaseIntoStoreStrong(Instruction *Release, + inst_iterator &Iter); void getAnalysisUsage(AnalysisUsage &AU) const override; bool doInitialization(Module &M) override; @@ -92,30 +103,15 @@ namespace { }; } -char ObjCARCContract::ID = 0; -INITIALIZE_PASS_BEGIN(ObjCARCContract, - "objc-arc-contract", "ObjC ARC contraction", false, false) -INITIALIZE_AG_DEPENDENCY(AliasAnalysis) -INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_END(ObjCARCContract, - "objc-arc-contract", "ObjC ARC contraction", false, false) - -Pass *llvm::createObjCARCContractPass() { - return new ObjCARCContract(); -} - -void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<AliasAnalysis>(); - AU.addRequired<DominatorTreeWrapperPass>(); - AU.setPreservesCFG(); -} +//===----------------------------------------------------------------------===// +// Implementation +//===----------------------------------------------------------------------===// /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a /// return value. We do this late so we do not disrupt the dataflow analysis in /// ObjCARCOpt. -bool -ObjCARCContract::OptimizeRetainCall(Function &F, Instruction *Retain) { - ImmutableCallSite CS(GetObjCArg(Retain)); +bool ObjCARCContract::optimizeRetainCall(Function &F, Instruction *Retain) { + ImmutableCallSite CS(GetArgRCIdentityRoot(Retain)); const Instruction *Call = CS.getInstruction(); if (!Call) return false; @@ -139,7 +135,7 @@ ObjCARCContract::OptimizeRetainCall(Function &F, Instruction *Retain) { // We do not have to worry about tail calls/does not throw since // retain/retainRV have the same properties. - Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_RetainRV); + Constant *Decl = EP.get(ARCRuntimeEntryPointKind::RetainRV); cast<CallInst>(Retain)->setCalledFunction(Decl); DEBUG(dbgs() << "New: " << *Retain << "\n"); @@ -147,19 +143,16 @@ ObjCARCContract::OptimizeRetainCall(Function &F, Instruction *Retain) { } /// Merge an autorelease with a retain into a fused call. -bool -ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease, - InstructionClass Class, - SmallPtrSetImpl<Instruction *> - &DependingInstructions, - SmallPtrSetImpl<const BasicBlock *> - &Visited) { - const Value *Arg = GetObjCArg(Autorelease); +bool ObjCARCContract::contractAutorelease( + Function &F, Instruction *Autorelease, ARCInstKind Class, + SmallPtrSetImpl<Instruction *> &DependingInstructions, + SmallPtrSetImpl<const BasicBlock *> &Visited) { + const Value *Arg = GetArgRCIdentityRoot(Autorelease); // Check that there are no instructions between the retain and the autorelease // (such as an autorelease_pop) which may change the count. CallInst *Retain = nullptr; - if (Class == IC_AutoreleaseRV) + if (Class == ARCInstKind::AutoreleaseRV) FindDependencies(RetainAutoreleaseRVDep, Arg, Autorelease->getParent(), Autorelease, DependingInstructions, Visited, PA); @@ -177,94 +170,208 @@ ObjCARCContract::ContractAutorelease(Function &F, Instruction *Autorelease, Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin()); DependingInstructions.clear(); - if (!Retain || - GetBasicInstructionClass(Retain) != IC_Retain || - GetObjCArg(Retain) != Arg) + if (!Retain || GetBasicARCInstKind(Retain) != ARCInstKind::Retain || + GetArgRCIdentityRoot(Retain) != Arg) return false; Changed = true; ++NumPeeps; - DEBUG(dbgs() << "ObjCARCContract::ContractAutorelease: Fusing " - "retain/autorelease. Erasing: " << *Autorelease << "\n" - " Old Retain: " - << *Retain << "\n"); + DEBUG(dbgs() << " Fusing retain/autorelease!\n" + " Autorelease:" << *Autorelease << "\n" + " Retain: " << *Retain << "\n"); - Constant *Decl = EP.get(Class == IC_AutoreleaseRV ? - ARCRuntimeEntryPoints::EPT_RetainAutoreleaseRV : - ARCRuntimeEntryPoints::EPT_RetainAutorelease); + Constant *Decl = EP.get(Class == ARCInstKind::AutoreleaseRV + ? ARCRuntimeEntryPointKind::RetainAutoreleaseRV + : ARCRuntimeEntryPointKind::RetainAutorelease); Retain->setCalledFunction(Decl); - DEBUG(dbgs() << " New Retain: " - << *Retain << "\n"); + DEBUG(dbgs() << " New RetainAutorelease: " << *Retain << "\n"); EraseInstruction(Autorelease); return true; } -/// Attempt to merge an objc_release with a store, load, and objc_retain to form -/// an objc_storeStrong. This can be a little tricky because the instructions -/// don't always appear in order, and there may be unrelated intervening -/// instructions. -void ObjCARCContract::ContractRelease(Instruction *Release, - inst_iterator &Iter) { - LoadInst *Load = dyn_cast<LoadInst>(GetObjCArg(Release)); - if (!Load || !Load->isSimple()) return; +static StoreInst *findSafeStoreForStoreStrongContraction(LoadInst *Load, + Instruction *Release, + ProvenanceAnalysis &PA, + AliasAnalysis *AA) { + StoreInst *Store = nullptr; + bool SawRelease = false; - // For now, require everything to be in one basic block. - BasicBlock *BB = Release->getParent(); - if (Load->getParent() != BB) return; + // Get the location associated with Load. + AliasAnalysis::Location Loc = MemoryLocation::get(Load); // Walk down to find the store and the release, which may be in either order. - BasicBlock::iterator I = Load, End = BB->end(); - ++I; - AliasAnalysis::Location Loc = AA->getLocation(Load); - StoreInst *Store = nullptr; - bool SawRelease = false; - for (; !Store || !SawRelease; ++I) { - if (I == End) - return; + for (auto I = std::next(BasicBlock::iterator(Load)), + E = Load->getParent()->end(); + I != E; ++I) { + // If we found the store we were looking for and saw the release, + // break. There is no more work to be done. + if (Store && SawRelease) + break; - Instruction *Inst = I; + // Now we know that we have not seen either the store or the release. If I + // is the the release, mark that we saw the release and continue. + Instruction *Inst = &*I; if (Inst == Release) { SawRelease = true; continue; } - InstructionClass Class = GetBasicInstructionClass(Inst); + // Otherwise, we check if Inst is a "good" store. Grab the instruction class + // of Inst. + ARCInstKind Class = GetBasicARCInstKind(Inst); - // Unrelated retains are harmless. + // If Inst is an unrelated retain, we don't care about it. + // + // TODO: This is one area where the optimization could be made more + // aggressive. if (IsRetain(Class)) continue; + // If we have seen the store, but not the release... if (Store) { - // The store is the point where we're going to put the objc_storeStrong, - // so make sure there are no uses after it. - if (CanUse(Inst, Load, PA, Class)) - return; - } else if (AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod) { - // We are moving the load down to the store, so check for anything - // else which writes to the memory between the load and the store. - Store = dyn_cast<StoreInst>(Inst); - if (!Store || !Store->isSimple()) return; - if (Store->getPointerOperand() != Loc.Ptr) return; + // We need to make sure that it is safe to move the release from its + // current position to the store. This implies proving that any + // instruction in between Store and the Release conservatively can not use + // the RCIdentityRoot of Release. If we can prove we can ignore Inst, so + // continue... + if (!CanUse(Inst, Load, PA, Class)) { + continue; + } + + // Otherwise, be conservative and return nullptr. + return nullptr; } + + // Ok, now we know we have not seen a store yet. See if Inst can write to + // our load location, if it can not, just ignore the instruction. + if (!(AA->getModRefInfo(Inst, Loc) & AliasAnalysis::Mod)) + continue; + + Store = dyn_cast<StoreInst>(Inst); + + // If Inst can, then check if Inst is a simple store. If Inst is not a + // store or a store that is not simple, then we have some we do not + // understand writing to this memory implying we can not move the load + // over the write to any subsequent store that we may find. + if (!Store || !Store->isSimple()) + return nullptr; + + // Then make sure that the pointer we are storing to is Ptr. If so, we + // found our Store! + if (Store->getPointerOperand() == Loc.Ptr) + continue; + + // Otherwise, we have an unknown store to some other ptr that clobbers + // Loc.Ptr. Bail! + return nullptr; } - Value *New = StripPointerCastsAndObjCCalls(Store->getValueOperand()); + // If we did not find the store or did not see the release, fail. + if (!Store || !SawRelease) + return nullptr; - // Walk up to find the retain. - I = Store; - BasicBlock::iterator Begin = BB->begin(); - while (I != Begin && GetBasicInstructionClass(I) != IC_Retain) + // We succeeded! + return Store; +} + +static Instruction * +findRetainForStoreStrongContraction(Value *New, StoreInst *Store, + Instruction *Release, + ProvenanceAnalysis &PA) { + // Walk up from the Store to find the retain. + BasicBlock::iterator I = Store; + BasicBlock::iterator Begin = Store->getParent()->begin(); + while (I != Begin && GetBasicARCInstKind(I) != ARCInstKind::Retain) { + Instruction *Inst = &*I; + + // It is only safe to move the retain to the store if we can prove + // conservatively that nothing besides the release can decrement reference + // counts in between the retain and the store. + if (CanDecrementRefCount(Inst, New, PA) && Inst != Release) + return nullptr; --I; + } Instruction *Retain = I; - if (GetBasicInstructionClass(Retain) != IC_Retain) return; - if (GetObjCArg(Retain) != New) return; + if (GetBasicARCInstKind(Retain) != ARCInstKind::Retain) + return nullptr; + if (GetArgRCIdentityRoot(Retain) != New) + return nullptr; + return Retain; +} + +/// Attempt to merge an objc_release with a store, load, and objc_retain to form +/// an objc_storeStrong. An objc_storeStrong: +/// +/// objc_storeStrong(i8** %old_ptr, i8* new_value) +/// +/// is equivalent to the following IR sequence: +/// +/// ; Load old value. +/// %old_value = load i8** %old_ptr (1) +/// +/// ; Increment the new value and then release the old value. This must occur +/// ; in order in case old_value releases new_value in its destructor causing +/// ; us to potentially have a dangling ptr. +/// tail call i8* @objc_retain(i8* %new_value) (2) +/// tail call void @objc_release(i8* %old_value) (3) +/// +/// ; Store the new_value into old_ptr +/// store i8* %new_value, i8** %old_ptr (4) +/// +/// The safety of this optimization is based around the following +/// considerations: +/// +/// 1. We are forming the store strong at the store. Thus to perform this +/// optimization it must be safe to move the retain, load, and release to +/// (4). +/// 2. We need to make sure that any re-orderings of (1), (2), (3), (4) are +/// safe. +void ObjCARCContract::tryToContractReleaseIntoStoreStrong(Instruction *Release, + inst_iterator &Iter) { + // See if we are releasing something that we just loaded. + auto *Load = dyn_cast<LoadInst>(GetArgRCIdentityRoot(Release)); + if (!Load || !Load->isSimple()) + return; + + // For now, require everything to be in one basic block. + BasicBlock *BB = Release->getParent(); + if (Load->getParent() != BB) + return; + + // First scan down the BB from Load, looking for a store of the RCIdentityRoot + // of Load's + StoreInst *Store = + findSafeStoreForStoreStrongContraction(Load, Release, PA, AA); + // If we fail, bail. + if (!Store) + return; + + // Then find what new_value's RCIdentity Root is. + Value *New = GetRCIdentityRoot(Store->getValueOperand()); + + // Then walk up the BB and look for a retain on New without any intervening + // instructions which conservatively might decrement ref counts. + Instruction *Retain = + findRetainForStoreStrongContraction(New, Store, Release, PA); + + // If we fail, bail. + if (!Retain) + return; Changed = true; ++NumStoreStrongs; + DEBUG( + llvm::dbgs() << " Contracting retain, release into objc_storeStrong.\n" + << " Old:\n" + << " Store: " << *Store << "\n" + << " Release: " << *Release << "\n" + << " Retain: " << *Retain << "\n" + << " Load: " << *Load << "\n"); + LLVMContext &C = Release->getContext(); Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); Type *I8XX = PointerType::getUnqual(I8X); @@ -274,7 +381,7 @@ void ObjCARCContract::ContractRelease(Instruction *Release, Args[0] = new BitCastInst(Args[0], I8XX, "", Store); if (Args[1]->getType() != I8X) Args[1] = new BitCastInst(Args[1], I8X, "", Store); - Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_StoreStrong); + Constant *Decl = EP.get(ARCRuntimeEntryPointKind::StoreStrong); CallInst *StoreStrong = CallInst::Create(Decl, Args, "", Store); StoreStrong->setDoesNotThrow(); StoreStrong->setDebugLoc(Store->getDebugLoc()); @@ -284,6 +391,8 @@ void ObjCARCContract::ContractRelease(Instruction *Release, // we can set the tail flag once we know it's safe. StoreStrongCalls.insert(StoreStrong); + DEBUG(llvm::dbgs() << " New Store Strong: " << *StoreStrong << "\n"); + if (&*Iter == Store) ++Iter; Store->eraseFromParent(); Release->eraseFromParent(); @@ -292,85 +401,34 @@ void ObjCARCContract::ContractRelease(Instruction *Release, Load->eraseFromParent(); } -bool ObjCARCContract::doInitialization(Module &M) { - // If nothing in the Module uses ARC, don't do anything. - Run = ModuleHasARC(M); - if (!Run) - return false; - - EP.Initialize(&M); - - // Initialize RetainRVMarker. - RetainRVMarker = nullptr; - if (NamedMDNode *NMD = - M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker")) - if (NMD->getNumOperands() == 1) { - const MDNode *N = NMD->getOperand(0); - if (N->getNumOperands() == 1) - if (const MDString *S = dyn_cast<MDString>(N->getOperand(0))) - RetainRVMarker = S; - } - - return false; -} - -bool ObjCARCContract::runOnFunction(Function &F) { - if (!EnableARCOpts) - return false; - - // If nothing in the Module uses ARC, don't do anything. - if (!Run) - return false; - - Changed = false; - AA = &getAnalysis<AliasAnalysis>(); - DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); - - PA.setAA(&getAnalysis<AliasAnalysis>()); - - // Track whether it's ok to mark objc_storeStrong calls with the "tail" - // keyword. Be conservative if the function has variadic arguments. - // It seems that functions which "return twice" are also unsafe for the - // "tail" argument, because they are setjmp, which could need to - // return to an earlier stack state. - bool TailOkForStoreStrongs = !F.isVarArg() && - !F.callsFunctionThatReturnsTwice(); - - // For ObjC library calls which return their argument, replace uses of the - // argument with uses of the call return value, if it dominates the use. This - // reduces register pressure. - SmallPtrSet<Instruction *, 4> DependingInstructions; - SmallPtrSet<const BasicBlock *, 4> Visited; - for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { - Instruction *Inst = &*I++; - - DEBUG(dbgs() << "ObjCARCContract: Visiting: " << *Inst << "\n"); - +bool ObjCARCContract::tryToPeepholeInstruction( + Function &F, Instruction *Inst, inst_iterator &Iter, + SmallPtrSetImpl<Instruction *> &DependingInsts, + SmallPtrSetImpl<const BasicBlock *> &Visited, + bool &TailOkForStoreStrongs) { // Only these library routines return their argument. In particular, // objc_retainBlock does not necessarily return its argument. - InstructionClass Class = GetBasicInstructionClass(Inst); + ARCInstKind Class = GetBasicARCInstKind(Inst); switch (Class) { - case IC_FusedRetainAutorelease: - case IC_FusedRetainAutoreleaseRV: - break; - case IC_Autorelease: - case IC_AutoreleaseRV: - if (ContractAutorelease(F, Inst, Class, DependingInstructions, Visited)) - continue; - break; - case IC_Retain: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: + return false; + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + return contractAutorelease(F, Inst, Class, DependingInsts, Visited); + case ARCInstKind::Retain: // Attempt to convert retains to retainrvs if they are next to function // calls. - if (!OptimizeRetainCall(F, Inst)) - break; + if (!optimizeRetainCall(F, Inst)) + return false; // If we succeed in our optimization, fall through. // FALLTHROUGH - case IC_RetainRV: { + case ARCInstKind::RetainRV: { // If we're compiling for a target which needs a special inline-asm // marker to do the retainAutoreleasedReturnValue optimization, // insert it now. if (!RetainRVMarker) - break; + return false; BasicBlock::iterator BBI = Inst; BasicBlock *InstParent = Inst->getParent(); @@ -388,8 +446,8 @@ bool ObjCARCContract::runOnFunction(Function &F) { --BBI; } while (IsNoopInstruction(BBI)); - if (&*BBI == GetObjCArg(Inst)) { - DEBUG(dbgs() << "ObjCARCContract: Adding inline asm marker for " + if (&*BBI == GetArgRCIdentityRoot(Inst)) { + DEBUG(dbgs() << "Adding inline asm marker for " "retainAutoreleasedReturnValue optimization.\n"); Changed = true; InlineAsm *IA = @@ -400,9 +458,9 @@ bool ObjCARCContract::runOnFunction(Function &F) { CallInst::Create(IA, "", Inst); } decline_rv_optimization: - break; + return false; } - case IC_InitWeak: { + case ARCInstKind::InitWeak: { // objc_initWeak(p, null) => *p = null CallInst *CI = cast<CallInst>(Inst); if (IsNullOrUndef(CI->getArgOperand(1))) { @@ -417,31 +475,80 @@ bool ObjCARCContract::runOnFunction(Function &F) { CI->replaceAllUsesWith(Null); CI->eraseFromParent(); } - continue; + return true; } - case IC_Release: - ContractRelease(Inst, I); - continue; - case IC_User: + case ARCInstKind::Release: + // Try to form an objc store strong from our release. If we fail, there is + // nothing further to do below, so continue. + tryToContractReleaseIntoStoreStrong(Inst, Iter); + return true; + case ARCInstKind::User: // Be conservative if the function has any alloca instructions. // Technically we only care about escaping alloca instructions, // but this is sufficient to handle some interesting cases. if (isa<AllocaInst>(Inst)) TailOkForStoreStrongs = false; - continue; - case IC_IntrinsicUser: + return true; + case ARCInstKind::IntrinsicUser: // Remove calls to @clang.arc.use(...). Inst->eraseFromParent(); - continue; + return true; default: - continue; + return true; } +} - DEBUG(dbgs() << "ObjCARCContract: Finished List.\n\n"); +//===----------------------------------------------------------------------===// +// Top Level Driver +//===----------------------------------------------------------------------===// + +bool ObjCARCContract::runOnFunction(Function &F) { + if (!EnableARCOpts) + return false; + + // If nothing in the Module uses ARC, don't do anything. + if (!Run) + return false; + + Changed = false; + AA = &getAnalysis<AliasAnalysis>(); + DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); + + PA.setAA(&getAnalysis<AliasAnalysis>()); + + DEBUG(llvm::dbgs() << "**** ObjCARC Contract ****\n"); + + // Track whether it's ok to mark objc_storeStrong calls with the "tail" + // keyword. Be conservative if the function has variadic arguments. + // It seems that functions which "return twice" are also unsafe for the + // "tail" argument, because they are setjmp, which could need to + // return to an earlier stack state. + bool TailOkForStoreStrongs = + !F.isVarArg() && !F.callsFunctionThatReturnsTwice(); - // Don't use GetObjCArg because we don't want to look through bitcasts + // For ObjC library calls which return their argument, replace uses of the + // argument with uses of the call return value, if it dominates the use. This + // reduces register pressure. + SmallPtrSet<Instruction *, 4> DependingInstructions; + SmallPtrSet<const BasicBlock *, 4> Visited; + for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E;) { + Instruction *Inst = &*I++; + + DEBUG(dbgs() << "Visiting: " << *Inst << "\n"); + + // First try to peephole Inst. If there is nothing further we can do in + // terms of undoing objc-arc-expand, process the next inst. + if (tryToPeepholeInstruction(F, Inst, I, DependingInstructions, Visited, + TailOkForStoreStrongs)) + continue; + + // Otherwise, try to undo objc-arc-expand. + + // Don't use GetArgRCIdentityRoot because we don't want to look through bitcasts // and such; to do the replacement, the argument must have type i8*. Value *Arg = cast<CallInst>(Inst)->getArgOperand(0); + + // TODO: Change this to a do-while. for (;;) { // If we're compiling bugpointed code, don't get in trouble. if (!isa<Instruction>(Arg) && !isa<Argument>(Arg)) @@ -458,7 +565,7 @@ bool ObjCARCContract::runOnFunction(Function &F) { // reachability here because an unreachable call is considered to // trivially dominate itself, which would lead us to rewriting its // argument in terms of its return value, which would lead to - // infinite loops in GetObjCArg. + // infinite loops in GetArgRCIdentityRoot. if (DT->isReachableFromEntry(U) && DT->dominates(Inst, U)) { Changed = true; Instruction *Replacement = Inst; @@ -514,3 +621,45 @@ bool ObjCARCContract::runOnFunction(Function &F) { return Changed; } + +//===----------------------------------------------------------------------===// +// Misc Pass Manager +//===----------------------------------------------------------------------===// + +char ObjCARCContract::ID = 0; +INITIALIZE_PASS_BEGIN(ObjCARCContract, "objc-arc-contract", + "ObjC ARC contraction", false, false) +INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_END(ObjCARCContract, "objc-arc-contract", + "ObjC ARC contraction", false, false) + +void ObjCARCContract::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired<AliasAnalysis>(); + AU.addRequired<DominatorTreeWrapperPass>(); + AU.setPreservesCFG(); +} + +Pass *llvm::createObjCARCContractPass() { return new ObjCARCContract(); } + +bool ObjCARCContract::doInitialization(Module &M) { + // If nothing in the Module uses ARC, don't do anything. + Run = ModuleHasARC(M); + if (!Run) + return false; + + EP.init(&M); + + // Initialize RetainRVMarker. + RetainRVMarker = nullptr; + if (NamedMDNode *NMD = + M.getNamedMetadata("clang.arc.retainAutoreleasedReturnValueMarker")) + if (NMD->getNumOperands() == 1) { + const MDNode *N = NMD->getOperand(0); + if (N->getNumOperands() == 1) + if (const MDString *S = dyn_cast<MDString>(N->getOperand(0))) + RetainRVMarker = S; + } + + return false; +} diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCExpand.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCExpand.cpp index bf9fcbb..53c19c3 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCExpand.cpp +++ b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCExpand.cpp @@ -99,13 +99,13 @@ bool ObjCARCExpand::runOnFunction(Function &F) { DEBUG(dbgs() << "ObjCARCExpand: Visiting: " << *Inst << "\n"); - switch (GetBasicInstructionClass(Inst)) { - case IC_Retain: - case IC_RetainRV: - case IC_Autorelease: - case IC_AutoreleaseRV: - case IC_FusedRetainAutorelease: - case IC_FusedRetainAutoreleaseRV: { + switch (GetBasicARCInstKind(Inst)) { + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: + case ARCInstKind::Autorelease: + case ARCInstKind::AutoreleaseRV: + case ARCInstKind::FusedRetainAutorelease: + case ARCInstKind::FusedRetainAutoreleaseRV: { // These calls return their argument verbatim, as a low-level // optimization. However, this makes high-level optimizations // harder. Undo any uses of this optimization that the front-end diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCOpts.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCOpts.cpp index 76932e6..dca3f1b 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCOpts.cpp +++ b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCOpts.cpp @@ -26,9 +26,11 @@ #include "ObjCARC.h" #include "ARCRuntimeEntryPoints.h" +#include "BlotMapVector.h" #include "DependencyAnalysis.h" #include "ObjCARCAliasAnalysis.h" #include "ProvenanceAnalysis.h" +#include "PtrState.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" @@ -45,106 +47,10 @@ using namespace llvm::objcarc; #define DEBUG_TYPE "objc-arc-opts" -/// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific. -/// @{ - -namespace { - /// \brief An associative container with fast insertion-order (deterministic) - /// iteration over its elements. Plus the special blot operation. - template<class KeyT, class ValueT> - class MapVector { - /// Map keys to indices in Vector. - typedef DenseMap<KeyT, size_t> MapTy; - MapTy Map; - - typedef std::vector<std::pair<KeyT, ValueT> > VectorTy; - /// Keys and values. - VectorTy Vector; - - public: - typedef typename VectorTy::iterator iterator; - typedef typename VectorTy::const_iterator const_iterator; - iterator begin() { return Vector.begin(); } - iterator end() { return Vector.end(); } - const_iterator begin() const { return Vector.begin(); } - const_iterator end() const { return Vector.end(); } - -#ifdef XDEBUG - ~MapVector() { - assert(Vector.size() >= Map.size()); // May differ due to blotting. - for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); - I != E; ++I) { - assert(I->second < Vector.size()); - assert(Vector[I->second].first == I->first); - } - for (typename VectorTy::const_iterator I = Vector.begin(), - E = Vector.end(); I != E; ++I) - assert(!I->first || - (Map.count(I->first) && - Map[I->first] == size_t(I - Vector.begin()))); - } -#endif - - ValueT &operator[](const KeyT &Arg) { - std::pair<typename MapTy::iterator, bool> Pair = - Map.insert(std::make_pair(Arg, size_t(0))); - if (Pair.second) { - size_t Num = Vector.size(); - Pair.first->second = Num; - Vector.push_back(std::make_pair(Arg, ValueT())); - return Vector[Num].second; - } - return Vector[Pair.first->second].second; - } - - std::pair<iterator, bool> - insert(const std::pair<KeyT, ValueT> &InsertPair) { - std::pair<typename MapTy::iterator, bool> Pair = - Map.insert(std::make_pair(InsertPair.first, size_t(0))); - if (Pair.second) { - size_t Num = Vector.size(); - Pair.first->second = Num; - Vector.push_back(InsertPair); - return std::make_pair(Vector.begin() + Num, true); - } - return std::make_pair(Vector.begin() + Pair.first->second, false); - } - - iterator find(const KeyT &Key) { - typename MapTy::iterator It = Map.find(Key); - if (It == Map.end()) return Vector.end(); - return Vector.begin() + It->second; - } - - const_iterator find(const KeyT &Key) const { - typename MapTy::const_iterator It = Map.find(Key); - if (It == Map.end()) return Vector.end(); - return Vector.begin() + It->second; - } - - /// This is similar to erase, but instead of removing the element from the - /// vector, it just zeros out the key in the vector. This leaves iterators - /// intact, but clients must be prepared for zeroed-out keys when iterating. - void blot(const KeyT &Key) { - typename MapTy::iterator It = Map.find(Key); - if (It == Map.end()) return; - Vector[It->second].first = KeyT(); - Map.erase(It); - } - - void clear() { - Map.clear(); - Vector.clear(); - } - }; -} - -/// @} -/// /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC. /// @{ -/// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon +/// \brief This is similar to GetRCIdentityRoot but it stops as soon /// as it finds a value with multiple uses. static const Value *FindSingleUseIdentifiedObject(const Value *Arg) { if (Arg->hasOneUse()) { @@ -153,7 +59,7 @@ static const Value *FindSingleUseIdentifiedObject(const Value *Arg) { if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg)) if (GEP->hasAllZeroIndices()) return FindSingleUseIdentifiedObject(GEP->getPointerOperand()); - if (IsForwarding(GetBasicInstructionClass(Arg))) + if (IsForwarding(GetBasicARCInstKind(Arg))) return FindSingleUseIdentifiedObject( cast<CallInst>(Arg)->getArgOperand(0)); if (!IsObjCIdentifiedObject(Arg)) @@ -165,7 +71,7 @@ static const Value *FindSingleUseIdentifiedObject(const Value *Arg) { // trivial uses, we can still consider this to be a single-use value. if (IsObjCIdentifiedObject(Arg)) { for (const User *U : Arg->users()) - if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg) + if (!U->use_empty() || GetRCIdentityRoot(U) != Arg) return nullptr; return Arg; @@ -177,13 +83,14 @@ static const Value *FindSingleUseIdentifiedObject(const Value *Arg) { /// This is a wrapper around getUnderlyingObjCPtr along the lines of /// GetUnderlyingObjects except that it returns early when it sees the first /// alloca. -static inline bool AreAnyUnderlyingObjectsAnAlloca(const Value *V) { +static inline bool AreAnyUnderlyingObjectsAnAlloca(const Value *V, + const DataLayout &DL) { SmallPtrSet<const Value *, 4> Visited; SmallVector<const Value *, 4> Worklist; Worklist.push_back(V); do { const Value *P = Worklist.pop_back_val(); - P = GetUnderlyingObjCPtr(P); + P = GetUnderlyingObjCPtr(P, DL); if (isa<AllocaInst>(P)) return true; @@ -198,8 +105,8 @@ static inline bool AreAnyUnderlyingObjectsAnAlloca(const Value *V) { } if (const PHINode *PN = dyn_cast<const PHINode>(P)) { - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - Worklist.push_back(PN->getIncomingValue(i)); + for (Value *IncValue : PN->incoming_values()) + Worklist.push_back(IncValue); continue; } } while (!Worklist.empty()); @@ -270,293 +177,6 @@ STATISTIC(NumReleasesAfterOpt, #endif namespace { - /// \enum Sequence - /// - /// \brief A sequence of states that a pointer may go through in which an - /// objc_retain and objc_release are actually needed. - enum Sequence { - S_None, - S_Retain, ///< objc_retain(x). - S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement. - S_Use, ///< any use of x. - S_Stop, ///< like S_Release, but code motion is stopped. - S_Release, ///< objc_release(x). - S_MovableRelease ///< objc_release(x), !clang.imprecise_release. - }; - - raw_ostream &operator<<(raw_ostream &OS, const Sequence S) - LLVM_ATTRIBUTE_UNUSED; - raw_ostream &operator<<(raw_ostream &OS, const Sequence S) { - switch (S) { - case S_None: - return OS << "S_None"; - case S_Retain: - return OS << "S_Retain"; - case S_CanRelease: - return OS << "S_CanRelease"; - case S_Use: - return OS << "S_Use"; - case S_Release: - return OS << "S_Release"; - case S_MovableRelease: - return OS << "S_MovableRelease"; - case S_Stop: - return OS << "S_Stop"; - } - llvm_unreachable("Unknown sequence type."); - } -} - -static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) { - // The easy cases. - if (A == B) - return A; - if (A == S_None || B == S_None) - return S_None; - - if (A > B) std::swap(A, B); - if (TopDown) { - // Choose the side which is further along in the sequence. - if ((A == S_Retain || A == S_CanRelease) && - (B == S_CanRelease || B == S_Use)) - return B; - } else { - // Choose the side which is further along in the sequence. - if ((A == S_Use || A == S_CanRelease) && - (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease)) - return A; - // If both sides are releases, choose the more conservative one. - if (A == S_Stop && (B == S_Release || B == S_MovableRelease)) - return A; - if (A == S_Release && B == S_MovableRelease) - return A; - } - - return S_None; -} - -namespace { - /// \brief Unidirectional information about either a - /// retain-decrement-use-release sequence or release-use-decrement-retain - /// reverse sequence. - struct RRInfo { - /// After an objc_retain, the reference count of the referenced - /// object is known to be positive. Similarly, before an objc_release, the - /// reference count of the referenced object is known to be positive. If - /// there are retain-release pairs in code regions where the retain count - /// is known to be positive, they can be eliminated, regardless of any side - /// effects between them. - /// - /// Also, a retain+release pair nested within another retain+release - /// pair all on the known same pointer value can be eliminated, regardless - /// of any intervening side effects. - /// - /// KnownSafe is true when either of these conditions is satisfied. - bool KnownSafe; - - /// True of the objc_release calls are all marked with the "tail" keyword. - bool IsTailCallRelease; - - /// If the Calls are objc_release calls and they all have a - /// clang.imprecise_release tag, this is the metadata tag. - MDNode *ReleaseMetadata; - - /// For a top-down sequence, the set of objc_retains or - /// objc_retainBlocks. For bottom-up, the set of objc_releases. - SmallPtrSet<Instruction *, 2> Calls; - - /// The set of optimal insert positions for moving calls in the opposite - /// sequence. - SmallPtrSet<Instruction *, 2> ReverseInsertPts; - - /// If this is true, we cannot perform code motion but can still remove - /// retain/release pairs. - bool CFGHazardAfflicted; - - RRInfo() : - KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(nullptr), - CFGHazardAfflicted(false) {} - - void clear(); - - /// Conservatively merge the two RRInfo. Returns true if a partial merge has - /// occurred, false otherwise. - bool Merge(const RRInfo &Other); - - }; -} - -void RRInfo::clear() { - KnownSafe = false; - IsTailCallRelease = false; - ReleaseMetadata = nullptr; - Calls.clear(); - ReverseInsertPts.clear(); - CFGHazardAfflicted = false; -} - -bool RRInfo::Merge(const RRInfo &Other) { - // Conservatively merge the ReleaseMetadata information. - if (ReleaseMetadata != Other.ReleaseMetadata) - ReleaseMetadata = nullptr; - - // Conservatively merge the boolean state. - KnownSafe &= Other.KnownSafe; - IsTailCallRelease &= Other.IsTailCallRelease; - CFGHazardAfflicted |= Other.CFGHazardAfflicted; - - // Merge the call sets. - Calls.insert(Other.Calls.begin(), Other.Calls.end()); - - // Merge the insert point sets. If there are any differences, - // that makes this a partial merge. - bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size(); - for (Instruction *Inst : Other.ReverseInsertPts) - Partial |= ReverseInsertPts.insert(Inst).second; - return Partial; -} - -namespace { - /// \brief This class summarizes several per-pointer runtime properties which - /// are propogated through the flow graph. - class PtrState { - /// True if the reference count is known to be incremented. - bool KnownPositiveRefCount; - - /// True if we've seen an opportunity for partial RR elimination, such as - /// pushing calls into a CFG triangle or into one side of a CFG diamond. - bool Partial; - - /// The current position in the sequence. - unsigned char Seq : 8; - - /// Unidirectional information about the current sequence. - RRInfo RRI; - - public: - PtrState() : KnownPositiveRefCount(false), Partial(false), - Seq(S_None) {} - - - bool IsKnownSafe() const { - return RRI.KnownSafe; - } - - void SetKnownSafe(const bool NewValue) { - RRI.KnownSafe = NewValue; - } - - bool IsTailCallRelease() const { - return RRI.IsTailCallRelease; - } - - void SetTailCallRelease(const bool NewValue) { - RRI.IsTailCallRelease = NewValue; - } - - bool IsTrackingImpreciseReleases() const { - return RRI.ReleaseMetadata != nullptr; - } - - const MDNode *GetReleaseMetadata() const { - return RRI.ReleaseMetadata; - } - - void SetReleaseMetadata(MDNode *NewValue) { - RRI.ReleaseMetadata = NewValue; - } - - bool IsCFGHazardAfflicted() const { - return RRI.CFGHazardAfflicted; - } - - void SetCFGHazardAfflicted(const bool NewValue) { - RRI.CFGHazardAfflicted = NewValue; - } - - void SetKnownPositiveRefCount() { - DEBUG(dbgs() << "Setting Known Positive.\n"); - KnownPositiveRefCount = true; - } - - void ClearKnownPositiveRefCount() { - DEBUG(dbgs() << "Clearing Known Positive.\n"); - KnownPositiveRefCount = false; - } - - bool HasKnownPositiveRefCount() const { - return KnownPositiveRefCount; - } - - void SetSeq(Sequence NewSeq) { - DEBUG(dbgs() << "Old: " << Seq << "; New: " << NewSeq << "\n"); - Seq = NewSeq; - } - - Sequence GetSeq() const { - return static_cast<Sequence>(Seq); - } - - void ClearSequenceProgress() { - ResetSequenceProgress(S_None); - } - - void ResetSequenceProgress(Sequence NewSeq) { - DEBUG(dbgs() << "Resetting sequence progress.\n"); - SetSeq(NewSeq); - Partial = false; - RRI.clear(); - } - - void Merge(const PtrState &Other, bool TopDown); - - void InsertCall(Instruction *I) { - RRI.Calls.insert(I); - } - - void InsertReverseInsertPt(Instruction *I) { - RRI.ReverseInsertPts.insert(I); - } - - void ClearReverseInsertPts() { - RRI.ReverseInsertPts.clear(); - } - - bool HasReverseInsertPts() const { - return !RRI.ReverseInsertPts.empty(); - } - - const RRInfo &GetRRInfo() const { - return RRI; - } - }; -} - -void -PtrState::Merge(const PtrState &Other, bool TopDown) { - Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown); - KnownPositiveRefCount &= Other.KnownPositiveRefCount; - - // If we're not in a sequence (anymore), drop all associated state. - if (Seq == S_None) { - Partial = false; - RRI.clear(); - } else if (Partial || Other.Partial) { - // If we're doing a merge on a path that's previously seen a partial - // merge, conservatively drop the sequence, to avoid doing partial - // RR elimination. If the branch predicates for the two merge differ, - // mixing them is unsafe. - ClearSequenceProgress(); - } else { - // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this - // point, we know that currently we are not partial. Stash whether or not - // the merge operation caused us to undergo a partial merging of reverse - // insertion points. - Partial = RRI.Merge(Other.RRI); - } -} - -namespace { /// \brief Per-BasicBlock state. class BBState { /// The number of unique control paths from the entry which can reach this @@ -566,20 +186,18 @@ namespace { /// The number of unique control paths to exits from this block. unsigned BottomUpPathCount; - /// A type for PerPtrTopDown and PerPtrBottomUp. - typedef MapVector<const Value *, PtrState> MapTy; - /// The top-down traversal uses this to record information known about a /// pointer at the bottom of each block. - MapTy PerPtrTopDown; + BlotMapVector<const Value *, TopDownPtrState> PerPtrTopDown; /// The bottom-up traversal uses this to record information known about a /// pointer at the top of each block. - MapTy PerPtrBottomUp; + BlotMapVector<const Value *, BottomUpPtrState> PerPtrBottomUp; /// Effective predecessors of the current block ignoring ignorable edges and /// ignored backedges. SmallVector<BasicBlock *, 2> Preds; + /// Effective successors of the current block ignoring ignorable edges and /// ignored backedges. SmallVector<BasicBlock *, 2> Succs; @@ -589,26 +207,38 @@ namespace { BBState() : TopDownPathCount(0), BottomUpPathCount(0) { } - typedef MapTy::iterator ptr_iterator; - typedef MapTy::const_iterator ptr_const_iterator; + typedef decltype(PerPtrTopDown)::iterator top_down_ptr_iterator; + typedef decltype(PerPtrTopDown)::const_iterator const_top_down_ptr_iterator; - ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); } - ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); } - ptr_const_iterator top_down_ptr_begin() const { + top_down_ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); } + top_down_ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); } + const_top_down_ptr_iterator top_down_ptr_begin() const { return PerPtrTopDown.begin(); } - ptr_const_iterator top_down_ptr_end() const { + const_top_down_ptr_iterator top_down_ptr_end() const { return PerPtrTopDown.end(); } + bool hasTopDownPtrs() const { + return !PerPtrTopDown.empty(); + } - ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); } - ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); } - ptr_const_iterator bottom_up_ptr_begin() const { + typedef decltype(PerPtrBottomUp)::iterator bottom_up_ptr_iterator; + typedef decltype( + PerPtrBottomUp)::const_iterator const_bottom_up_ptr_iterator; + + bottom_up_ptr_iterator bottom_up_ptr_begin() { + return PerPtrBottomUp.begin(); + } + bottom_up_ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); } + const_bottom_up_ptr_iterator bottom_up_ptr_begin() const { return PerPtrBottomUp.begin(); } - ptr_const_iterator bottom_up_ptr_end() const { + const_bottom_up_ptr_iterator bottom_up_ptr_end() const { return PerPtrBottomUp.end(); } + bool hasBottomUpPtrs() const { + return !PerPtrBottomUp.empty(); + } /// Mark this block as being an entry block, which has one path from the /// entry by definition. @@ -621,20 +251,20 @@ namespace { /// Attempt to find the PtrState object describing the top down state for /// pointer Arg. Return a new initialized PtrState describing the top down /// state for Arg if we do not find one. - PtrState &getPtrTopDownState(const Value *Arg) { + TopDownPtrState &getPtrTopDownState(const Value *Arg) { return PerPtrTopDown[Arg]; } /// Attempt to find the PtrState object describing the bottom up state for /// pointer Arg. Return a new initialized PtrState describing the bottom up /// state for Arg if we do not find one. - PtrState &getPtrBottomUpState(const Value *Arg) { + BottomUpPtrState &getPtrBottomUpState(const Value *Arg) { return PerPtrBottomUp[Arg]; } /// Attempt to find the PtrState object describing the bottom up state for /// pointer Arg. - ptr_iterator findPtrBottomUpState(const Value *Arg) { + bottom_up_ptr_iterator findPtrBottomUpState(const Value *Arg) { return PerPtrBottomUp.find(Arg); } @@ -685,6 +315,11 @@ namespace { const unsigned BBState::OverflowOccurredValue = 0xffffffff; } +namespace llvm { +raw_ostream &operator<<(raw_ostream &OS, + BBState &BBState) LLVM_ATTRIBUTE_UNUSED; +} + void BBState::InitFromPred(const BBState &Other) { PerPtrTopDown = Other.PerPtrTopDown; TopDownPathCount = Other.TopDownPathCount; @@ -724,19 +359,18 @@ void BBState::MergePred(const BBState &Other) { // For each entry in the other set, if our set has an entry with the same key, // merge the entries. Otherwise, copy the entry and merge it with an empty // entry. - for (ptr_const_iterator MI = Other.top_down_ptr_begin(), - ME = Other.top_down_ptr_end(); MI != ME; ++MI) { - std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI); - Pair.first->second.Merge(Pair.second ? PtrState() : MI->second, + for (auto MI = Other.top_down_ptr_begin(), ME = Other.top_down_ptr_end(); + MI != ME; ++MI) { + auto Pair = PerPtrTopDown.insert(*MI); + Pair.first->second.Merge(Pair.second ? TopDownPtrState() : MI->second, /*TopDown=*/true); } // For each entry in our set, if the other set doesn't have an entry with the // same key, force it to merge with an empty entry. - for (ptr_iterator MI = top_down_ptr_begin(), - ME = top_down_ptr_end(); MI != ME; ++MI) + for (auto MI = top_down_ptr_begin(), ME = top_down_ptr_end(); MI != ME; ++MI) if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end()) - MI->second.Merge(PtrState(), /*TopDown=*/true); + MI->second.Merge(TopDownPtrState(), /*TopDown=*/true); } /// The bottom-up traversal uses this to merge information about successors to @@ -768,304 +402,80 @@ void BBState::MergeSucc(const BBState &Other) { // For each entry in the other set, if our set has an entry with the // same key, merge the entries. Otherwise, copy the entry and merge // it with an empty entry. - for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(), - ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) { - std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI); - Pair.first->second.Merge(Pair.second ? PtrState() : MI->second, + for (auto MI = Other.bottom_up_ptr_begin(), ME = Other.bottom_up_ptr_end(); + MI != ME; ++MI) { + auto Pair = PerPtrBottomUp.insert(*MI); + Pair.first->second.Merge(Pair.second ? BottomUpPtrState() : MI->second, /*TopDown=*/false); } // For each entry in our set, if the other set doesn't have an entry // with the same key, force it to merge with an empty entry. - for (ptr_iterator MI = bottom_up_ptr_begin(), - ME = bottom_up_ptr_end(); MI != ME; ++MI) + for (auto MI = bottom_up_ptr_begin(), ME = bottom_up_ptr_end(); MI != ME; + ++MI) if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end()) - MI->second.Merge(PtrState(), /*TopDown=*/false); + MI->second.Merge(BottomUpPtrState(), /*TopDown=*/false); } -// Only enable ARC Annotations if we are building a debug version of -// libObjCARCOpts. -#ifndef NDEBUG -#define ARC_ANNOTATIONS -#endif - -// Define some macros along the lines of DEBUG and some helper functions to make -// it cleaner to create annotations in the source code and to no-op when not -// building in debug mode. -#ifdef ARC_ANNOTATIONS - -#include "llvm/Support/CommandLine.h" - -/// Enable/disable ARC sequence annotations. -static cl::opt<bool> -EnableARCAnnotations("enable-objc-arc-annotations", cl::init(false), - cl::desc("Enable emission of arc data flow analysis " - "annotations")); -static cl::opt<bool> -DisableCheckForCFGHazards("disable-objc-arc-checkforcfghazards", cl::init(false), - cl::desc("Disable check for cfg hazards when " - "annotating")); -static cl::opt<std::string> -ARCAnnotationTargetIdentifier("objc-arc-annotation-target-identifier", - cl::init(""), - cl::desc("filter out all data flow annotations " - "but those that apply to the given " - "target llvm identifier.")); - -/// This function appends a unique ARCAnnotationProvenanceSourceMDKind id to an -/// instruction so that we can track backwards when post processing via the llvm -/// arc annotation processor tool. If the function is an -static MDString *AppendMDNodeToSourcePtr(unsigned NodeId, - Value *Ptr) { - MDString *Hash = nullptr; - - // If pointer is a result of an instruction and it does not have a source - // MDNode it, attach a new MDNode onto it. If pointer is a result of - // an instruction and does have a source MDNode attached to it, return a - // reference to said Node. Otherwise just return 0. - if (Instruction *Inst = dyn_cast<Instruction>(Ptr)) { - MDNode *Node; - if (!(Node = Inst->getMetadata(NodeId))) { - // We do not have any node. Generate and attatch the hash MDString to the - // instruction. - - // We just use an MDString to ensure that this metadata gets written out - // of line at the module level and to provide a very simple format - // encoding the information herein. Both of these makes it simpler to - // parse the annotations by a simple external program. - std::string Str; - raw_string_ostream os(Str); - os << "(" << Inst->getParent()->getParent()->getName() << ",%" - << Inst->getName() << ")"; - - Hash = MDString::get(Inst->getContext(), os.str()); - Inst->setMetadata(NodeId, MDNode::get(Inst->getContext(),Hash)); - } else { - // We have a node. Grab its hash and return it. - assert(Node->getNumOperands() == 1 && - "An ARCAnnotationProvenanceSourceMDKind can only have 1 operand."); - Hash = cast<MDString>(Node->getOperand(0)); +raw_ostream &llvm::operator<<(raw_ostream &OS, BBState &BBInfo) { + // Dump the pointers we are tracking. + OS << " TopDown State:\n"; + if (!BBInfo.hasTopDownPtrs()) { + DEBUG(llvm::dbgs() << " NONE!\n"); + } else { + for (auto I = BBInfo.top_down_ptr_begin(), E = BBInfo.top_down_ptr_end(); + I != E; ++I) { + const PtrState &P = I->second; + OS << " Ptr: " << *I->first + << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false") + << "\n ImpreciseRelease: " + << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n" + << " HasCFGHazards: " + << (P.IsCFGHazardAfflicted()?"true":"false") << "\n" + << " KnownPositive: " + << (P.HasKnownPositiveRefCount()?"true":"false") << "\n" + << " Seq: " + << P.GetSeq() << "\n"; } - } else if (Argument *Arg = dyn_cast<Argument>(Ptr)) { - std::string str; - raw_string_ostream os(str); - os << "(" << Arg->getParent()->getName() << ",%" << Arg->getName() - << ")"; - Hash = MDString::get(Arg->getContext(), os.str()); } - return Hash; -} - -static std::string SequenceToString(Sequence A) { - std::string str; - raw_string_ostream os(str); - os << A; - return os.str(); -} - -/// Helper function to change a Sequence into a String object using our overload -/// for raw_ostream so we only have printing code in one location. -static MDString *SequenceToMDString(LLVMContext &Context, - Sequence A) { - return MDString::get(Context, SequenceToString(A)); -} - -/// A simple function to generate a MDNode which describes the change in state -/// for Value *Ptr caused by Instruction *Inst. -static void AppendMDNodeToInstForPtr(unsigned NodeId, - Instruction *Inst, - Value *Ptr, - MDString *PtrSourceMDNodeID, - Sequence OldSeq, - Sequence NewSeq) { - MDNode *Node = nullptr; - Metadata *tmp[3] = {PtrSourceMDNodeID, - SequenceToMDString(Inst->getContext(), OldSeq), - SequenceToMDString(Inst->getContext(), NewSeq)}; - Node = MDNode::get(Inst->getContext(), tmp); - - Inst->setMetadata(NodeId, Node); -} - -/// Add to the beginning of the basic block llvm.ptr.annotations which show the -/// state of a pointer at the entrance to a basic block. -static void GenerateARCBBEntranceAnnotation(const char *Name, BasicBlock *BB, - Value *Ptr, Sequence Seq) { - // If we have a target identifier, make sure that we match it before - // continuing. - if(!ARCAnnotationTargetIdentifier.empty() && - !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) - return; - - Module *M = BB->getParent()->getParent(); - LLVMContext &C = M->getContext(); - Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); - Type *I8XX = PointerType::getUnqual(I8X); - Type *Params[] = {I8XX, I8XX}; - FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), Params, - /*isVarArg=*/false); - Constant *Callee = M->getOrInsertFunction(Name, FTy); - - IRBuilder<> Builder(BB, BB->getFirstInsertionPt()); - - Value *PtrName; - StringRef Tmp = Ptr->getName(); - if (nullptr == (PtrName = M->getGlobalVariable(Tmp, true))) { - Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp, - Tmp + "_STR"); - PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, - cast<Constant>(ActualPtrName), Tmp); - } - - Value *S; - std::string SeqStr = SequenceToString(Seq); - if (nullptr == (S = M->getGlobalVariable(SeqStr, true))) { - Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr, - SeqStr + "_STR"); - S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, - cast<Constant>(ActualPtrName), SeqStr); - } - - Builder.CreateCall2(Callee, PtrName, S); -} - -/// Add to the end of the basic block llvm.ptr.annotations which show the state -/// of the pointer at the bottom of the basic block. -static void GenerateARCBBTerminatorAnnotation(const char *Name, BasicBlock *BB, - Value *Ptr, Sequence Seq) { - // If we have a target identifier, make sure that we match it before emitting - // an annotation. - if(!ARCAnnotationTargetIdentifier.empty() && - !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) - return; - - Module *M = BB->getParent()->getParent(); - LLVMContext &C = M->getContext(); - Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); - Type *I8XX = PointerType::getUnqual(I8X); - Type *Params[] = {I8XX, I8XX}; - FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), Params, - /*isVarArg=*/false); - Constant *Callee = M->getOrInsertFunction(Name, FTy); - - IRBuilder<> Builder(BB, std::prev(BB->end())); - - Value *PtrName; - StringRef Tmp = Ptr->getName(); - if (nullptr == (PtrName = M->getGlobalVariable(Tmp, true))) { - Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp, - Tmp + "_STR"); - PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, - cast<Constant>(ActualPtrName), Tmp); - } - - Value *S; - std::string SeqStr = SequenceToString(Seq); - if (nullptr == (S = M->getGlobalVariable(SeqStr, true))) { - Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr, - SeqStr + "_STR"); - S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, - cast<Constant>(ActualPtrName), SeqStr); + OS << " BottomUp State:\n"; + if (!BBInfo.hasBottomUpPtrs()) { + DEBUG(llvm::dbgs() << " NONE!\n"); + } else { + for (auto I = BBInfo.bottom_up_ptr_begin(), E = BBInfo.bottom_up_ptr_end(); + I != E; ++I) { + const PtrState &P = I->second; + OS << " Ptr: " << *I->first + << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false") + << "\n ImpreciseRelease: " + << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n" + << " HasCFGHazards: " + << (P.IsCFGHazardAfflicted()?"true":"false") << "\n" + << " KnownPositive: " + << (P.HasKnownPositiveRefCount()?"true":"false") << "\n" + << " Seq: " + << P.GetSeq() << "\n"; + } } - Builder.CreateCall2(Callee, PtrName, S); -} -/// Adds a source annotation to pointer and a state change annotation to Inst -/// referencing the source annotation and the old/new state of pointer. -static void GenerateARCAnnotation(unsigned InstMDId, - unsigned PtrMDId, - Instruction *Inst, - Value *Ptr, - Sequence OldSeq, - Sequence NewSeq) { - if (EnableARCAnnotations) { - // If we have a target identifier, make sure that we match it before - // emitting an annotation. - if(!ARCAnnotationTargetIdentifier.empty() && - !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) - return; - - // First generate the source annotation on our pointer. This will return an - // MDString* if Ptr actually comes from an instruction implying we can put - // in a source annotation. If AppendMDNodeToSourcePtr returns 0 (i.e. NULL), - // then we know that our pointer is from an Argument so we put a reference - // to the argument number. - // - // The point of this is to make it easy for the - // llvm-arc-annotation-processor tool to cross reference where the source - // pointer is in the LLVM IR since the LLVM IR parser does not submit such - // information via debug info for backends to use (since why would anyone - // need such a thing from LLVM IR besides in non-standard cases - // [i.e. this]). - MDString *SourcePtrMDNode = - AppendMDNodeToSourcePtr(PtrMDId, Ptr); - AppendMDNodeToInstForPtr(InstMDId, Inst, Ptr, SourcePtrMDNode, OldSeq, - NewSeq); - } + return OS; } -// The actual interface for accessing the above functionality is defined via -// some simple macros which are defined below. We do this so that the user does -// not need to pass in what metadata id is needed resulting in cleaner code and -// additionally since it provides an easy way to conditionally no-op all -// annotation support in a non-debug build. - -/// Use this macro to annotate a sequence state change when processing -/// instructions bottom up, -#define ANNOTATE_BOTTOMUP(inst, ptr, old, new) \ - GenerateARCAnnotation(ARCAnnotationBottomUpMDKind, \ - ARCAnnotationProvenanceSourceMDKind, (inst), \ - const_cast<Value*>(ptr), (old), (new)) -/// Use this macro to annotate a sequence state change when processing -/// instructions top down. -#define ANNOTATE_TOPDOWN(inst, ptr, old, new) \ - GenerateARCAnnotation(ARCAnnotationTopDownMDKind, \ - ARCAnnotationProvenanceSourceMDKind, (inst), \ - const_cast<Value*>(ptr), (old), (new)) - -#define ANNOTATE_BB(_states, _bb, _name, _type, _direction) \ - do { \ - if (EnableARCAnnotations) { \ - for(BBState::ptr_const_iterator I = (_states)._direction##_ptr_begin(), \ - E = (_states)._direction##_ptr_end(); I != E; ++I) { \ - Value *Ptr = const_cast<Value*>(I->first); \ - Sequence Seq = I->second.GetSeq(); \ - GenerateARCBB ## _type ## Annotation(_name, (_bb), Ptr, Seq); \ - } \ - } \ - } while (0) - -#define ANNOTATE_BOTTOMUP_BBSTART(_states, _basicblock) \ - ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbstart", \ - Entrance, bottom_up) -#define ANNOTATE_BOTTOMUP_BBEND(_states, _basicblock) \ - ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbend", \ - Terminator, bottom_up) -#define ANNOTATE_TOPDOWN_BBSTART(_states, _basicblock) \ - ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbstart", \ - Entrance, top_down) -#define ANNOTATE_TOPDOWN_BBEND(_states, _basicblock) \ - ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbend", \ - Terminator, top_down) - -#else // !ARC_ANNOTATION -// If annotations are off, noop. -#define ANNOTATE_BOTTOMUP(inst, ptr, old, new) -#define ANNOTATE_TOPDOWN(inst, ptr, old, new) -#define ANNOTATE_BOTTOMUP_BBSTART(states, basicblock) -#define ANNOTATE_BOTTOMUP_BBEND(states, basicblock) -#define ANNOTATE_TOPDOWN_BBSTART(states, basicblock) -#define ANNOTATE_TOPDOWN_BBEND(states, basicblock) -#endif // !ARC_ANNOTATION - namespace { + /// \brief The main ARC optimization pass. class ObjCARCOpt : public FunctionPass { bool Changed; ProvenanceAnalysis PA; + + /// A cache of references to runtime entry point constants. ARCRuntimeEntryPoints EP; + /// A cache of MDKinds that can be passed into other functions to propagate + /// MDKind identifiers. + ARCMDKindCache MDKindCache; + // This is used to track if a pointer is stored into an alloca. DenseSet<const Value *> MultiOwnersSet; @@ -1076,73 +486,49 @@ namespace { /// is in fact used in the current function. unsigned UsedInThisFunction; - /// The Metadata Kind for clang.imprecise_release metadata. - unsigned ImpreciseReleaseMDKind; - - /// The Metadata Kind for clang.arc.copy_on_escape metadata. - unsigned CopyOnEscapeMDKind; - - /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata. - unsigned NoObjCARCExceptionsMDKind; - -#ifdef ARC_ANNOTATIONS - /// The Metadata Kind for llvm.arc.annotation.bottomup metadata. - unsigned ARCAnnotationBottomUpMDKind; - /// The Metadata Kind for llvm.arc.annotation.topdown metadata. - unsigned ARCAnnotationTopDownMDKind; - /// The Metadata Kind for llvm.arc.annotation.provenancesource metadata. - unsigned ARCAnnotationProvenanceSourceMDKind; -#endif // ARC_ANNOATIONS - bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV); void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, - InstructionClass &Class); + ARCInstKind &Class); void OptimizeIndividualCalls(Function &F); void CheckForCFGHazards(const BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates, BBState &MyStates) const; - bool VisitInstructionBottomUp(Instruction *Inst, - BasicBlock *BB, - MapVector<Value *, RRInfo> &Retains, + bool VisitInstructionBottomUp(Instruction *Inst, BasicBlock *BB, + BlotMapVector<Value *, RRInfo> &Retains, BBState &MyStates); bool VisitBottomUp(BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates, - MapVector<Value *, RRInfo> &Retains); + BlotMapVector<Value *, RRInfo> &Retains); bool VisitInstructionTopDown(Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates); bool VisitTopDown(BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates, DenseMap<Value *, RRInfo> &Releases); - bool Visit(Function &F, - DenseMap<const BasicBlock *, BBState> &BBStates, - MapVector<Value *, RRInfo> &Retains, + bool Visit(Function &F, DenseMap<const BasicBlock *, BBState> &BBStates, + BlotMapVector<Value *, RRInfo> &Retains, DenseMap<Value *, RRInfo> &Releases); void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove, - MapVector<Value *, RRInfo> &Retains, + BlotMapVector<Value *, RRInfo> &Retains, DenseMap<Value *, RRInfo> &Releases, - SmallVectorImpl<Instruction *> &DeadInsts, - Module *M); - - bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates, - MapVector<Value *, RRInfo> &Retains, - DenseMap<Value *, RRInfo> &Releases, - Module *M, - SmallVectorImpl<Instruction *> &NewRetains, - SmallVectorImpl<Instruction *> &NewReleases, - SmallVectorImpl<Instruction *> &DeadInsts, - RRInfo &RetainsToMove, - RRInfo &ReleasesToMove, - Value *Arg, - bool KnownSafe, - bool &AnyPairsCompletelyEliminated); + SmallVectorImpl<Instruction *> &DeadInsts, Module *M); + + bool + PairUpRetainsAndReleases(DenseMap<const BasicBlock *, BBState> &BBStates, + BlotMapVector<Value *, RRInfo> &Retains, + DenseMap<Value *, RRInfo> &Releases, Module *M, + SmallVectorImpl<Instruction *> &NewRetains, + SmallVectorImpl<Instruction *> &NewReleases, + SmallVectorImpl<Instruction *> &DeadInsts, + RRInfo &RetainsToMove, RRInfo &ReleasesToMove, + Value *Arg, bool KnownSafe, + bool &AnyPairsCompletelyEliminated); bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates, - MapVector<Value *, RRInfo> &Retains, - DenseMap<Value *, RRInfo> &Releases, - Module *M); + BlotMapVector<Value *, RRInfo> &Retains, + DenseMap<Value *, RRInfo> &Releases, Module *M); void OptimizeWeakCalls(Function &F); @@ -1191,7 +577,7 @@ void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const { bool ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { // Check for the argument being from an immediately preceding call or invoke. - const Value *Arg = GetObjCArg(RetainRV); + const Value *Arg = GetArgRCIdentityRoot(RetainRV); ImmutableCallSite CS(Arg); if (const Instruction *Call = CS.getInstruction()) { if (Call->getParent() == RetainRV->getParent()) { @@ -1216,8 +602,8 @@ ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin(); if (I != Begin) { do --I; while (I != Begin && IsNoopInstruction(I)); - if (GetBasicInstructionClass(I) == IC_AutoreleaseRV && - GetObjCArg(I) == Arg) { + if (GetBasicARCInstKind(I) == ARCInstKind::AutoreleaseRV && + GetArgRCIdentityRoot(I) == Arg) { Changed = true; ++NumPeeps; @@ -1238,7 +624,7 @@ ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { "objc_retain since the operand is not a return value.\n" "Old = " << *RetainRV << "\n"); - Constant *NewDecl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); + Constant *NewDecl = EP.get(ARCRuntimeEntryPointKind::Retain); cast<CallInst>(RetainRV)->setCalledFunction(NewDecl); DEBUG(dbgs() << "New = " << *RetainRV << "\n"); @@ -1248,17 +634,17 @@ ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not /// used as a return value. -void -ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, - InstructionClass &Class) { +void ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, + Instruction *AutoreleaseRV, + ARCInstKind &Class) { // Check for a return of the pointer value. - const Value *Ptr = GetObjCArg(AutoreleaseRV); + const Value *Ptr = GetArgRCIdentityRoot(AutoreleaseRV); SmallVector<const Value *, 2> Users; Users.push_back(Ptr); do { Ptr = Users.pop_back_val(); for (const User *U : Ptr->users()) { - if (isa<ReturnInst>(U) || GetBasicInstructionClass(U) == IC_RetainRV) + if (isa<ReturnInst>(U) || GetBasicARCInstKind(U) == ARCInstKind::RetainRV) return; if (isa<BitCastInst>(U)) Users.push_back(U); @@ -1274,10 +660,10 @@ ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, "Old = " << *AutoreleaseRV << "\n"); CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV); - Constant *NewDecl = EP.get(ARCRuntimeEntryPoints::EPT_Autorelease); + Constant *NewDecl = EP.get(ARCRuntimeEntryPointKind::Autorelease); AutoreleaseRVCI->setCalledFunction(NewDecl); AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease. - Class = IC_Autorelease; + Class = ARCInstKind::Autorelease; DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n"); @@ -1294,7 +680,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { Instruction *Inst = &*I++; - InstructionClass Class = GetBasicInstructionClass(Inst); + ARCInstKind Class = GetBasicARCInstKind(Inst); DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n"); @@ -1309,7 +695,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { // There are gray areas here, as the ability to cast reference-counted // pointers to raw void* and back allows code to break ARC assumptions, // however these are currently considered to be unimportant. - case IC_NoopCast: + case ARCInstKind::NoopCast: Changed = true; ++NumNoops; DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n"); @@ -1317,11 +703,11 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { continue; // If the pointer-to-weak-pointer is null, it's undefined behavior. - case IC_StoreWeak: - case IC_LoadWeak: - case IC_LoadWeakRetained: - case IC_InitWeak: - case IC_DestroyWeak: { + case ARCInstKind::StoreWeak: + case ARCInstKind::LoadWeak: + case ARCInstKind::LoadWeakRetained: + case ARCInstKind::InitWeak: + case ARCInstKind::DestroyWeak: { CallInst *CI = cast<CallInst>(Inst); if (IsNullOrUndef(CI->getArgOperand(0))) { Changed = true; @@ -1338,8 +724,8 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { } break; } - case IC_CopyWeak: - case IC_MoveWeak: { + case ARCInstKind::CopyWeak: + case ARCInstKind::MoveWeak: { CallInst *CI = cast<CallInst>(Inst); if (IsNullOrUndef(CI->getArgOperand(0)) || IsNullOrUndef(CI->getArgOperand(1))) { @@ -1359,11 +745,11 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { } break; } - case IC_RetainRV: + case ARCInstKind::RetainRV: if (OptimizeRetainRVCall(F, Inst)) continue; break; - case IC_AutoreleaseRV: + case ARCInstKind::AutoreleaseRV: OptimizeAutoreleaseRVCall(F, Inst, Class); break; } @@ -1380,10 +766,11 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { // Create the declaration lazily. LLVMContext &C = Inst->getContext(); - Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release); + Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Release); CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "", Call); - NewCall->setMetadata(ImpreciseReleaseMDKind, MDNode::get(C, None)); + NewCall->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), + MDNode::get(C, None)); DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) " "since x is otherwise unused.\nOld: " << *Call << "\nNew: " @@ -1391,7 +778,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { EraseInstruction(Call); Inst = NewCall; - Class = IC_Release; + Class = ARCInstKind::Release; } } @@ -1422,11 +809,11 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { } if (!IsNoopOnNull(Class)) { - UsedInThisFunction |= 1 << Class; + UsedInThisFunction |= 1 << unsigned(Class); continue; } - const Value *Arg = GetObjCArg(Inst); + const Value *Arg = GetArgRCIdentityRoot(Inst); // ARC calls with null are no-ops. Delete them. if (IsNullOrUndef(Arg)) { @@ -1440,7 +827,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { // Keep track of which of retain, release, autorelease, and retain_block // are actually present in this function. - UsedInThisFunction |= 1 << Class; + UsedInThisFunction |= 1 << unsigned(Class); // If Arg is a PHI, and one or more incoming values to the // PHI are null, and the call is control-equivalent to the PHI, and there @@ -1463,7 +850,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { bool HasCriticalEdges = false; for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { Value *Incoming = - StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); + GetRCIdentityRoot(PN->getIncomingValue(i)); if (IsNullOrUndef(Incoming)) HasNull = true; else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back()) @@ -1480,25 +867,25 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { // Check that there is nothing that cares about the reference // count between the call and the phi. switch (Class) { - case IC_Retain: - case IC_RetainBlock: + case ARCInstKind::Retain: + case ARCInstKind::RetainBlock: // These can always be moved up. break; - case IC_Release: + case ARCInstKind::Release: // These can't be moved across things that care about the retain // count. FindDependencies(NeedsPositiveRetainCount, Arg, Inst->getParent(), Inst, DependingInstructions, Visited, PA); break; - case IC_Autorelease: + case ARCInstKind::Autorelease: // These can't be moved across autorelease pool scope boundaries. FindDependencies(AutoreleasePoolBoundary, Arg, Inst->getParent(), Inst, DependingInstructions, Visited, PA); break; - case IC_RetainRV: - case IC_AutoreleaseRV: + case ARCInstKind::RetainRV: + case ARCInstKind::AutoreleaseRV: // Don't move these; the RV optimization depends on the autoreleaseRV // being tail called, and the retainRV being immediately after a call // (which might still happen if we get lucky with codegen layout, but @@ -1517,7 +904,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { Type *ParamTy = CInst->getArgOperand(0)->getType(); for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { Value *Incoming = - StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); + GetRCIdentityRoot(PN->getIncomingValue(i)); if (!IsNullOrUndef(Incoming)) { CallInst *Clone = cast<CallInst>(CInst->clone()); Value *Op = PN->getIncomingValue(i); @@ -1547,7 +934,7 @@ void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { /// no CFG hazards by checking the states of various bottom up pointers. static void CheckForUseCFGHazard(const Sequence SuccSSeq, const bool SuccSRRIKnownSafe, - PtrState &S, + TopDownPtrState &S, bool &SomeSuccHasSame, bool &AllSuccsHaveSame, bool &NotAllSeqEqualButKnownSafe, @@ -1585,7 +972,7 @@ static void CheckForUseCFGHazard(const Sequence SuccSSeq, /// pointers. static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq, const bool SuccSRRIKnownSafe, - PtrState &S, + TopDownPtrState &S, bool &SomeSuccHasSame, bool &AllSuccsHaveSame, bool &NotAllSeqEqualButKnownSafe) { @@ -1618,9 +1005,9 @@ ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB, BBState &MyStates) const { // If any top-down local-use or possible-dec has a succ which is earlier in // the sequence, forget it. - for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(), - E = MyStates.top_down_ptr_end(); I != E; ++I) { - PtrState &S = I->second; + for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end(); + I != E; ++I) { + TopDownPtrState &S = I->second; const Sequence Seq = I->second.GetSeq(); // We only care about S_Retain, S_CanRelease, and S_Use. @@ -1646,7 +1033,7 @@ ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB, const DenseMap<const BasicBlock *, BBState>::iterator BBI = BBStates.find(*SI); assert(BBI != BBStates.end()); - const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); + const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); const Sequence SuccSSeq = SuccS.GetSeq(); // If bottom up, the pointer is in an S_None state, clear the sequence @@ -1705,94 +1092,53 @@ ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB, } } -bool -ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, - BasicBlock *BB, - MapVector<Value *, RRInfo> &Retains, - BBState &MyStates) { +bool ObjCARCOpt::VisitInstructionBottomUp( + Instruction *Inst, BasicBlock *BB, BlotMapVector<Value *, RRInfo> &Retains, + BBState &MyStates) { bool NestingDetected = false; - InstructionClass Class = GetInstructionClass(Inst); + ARCInstKind Class = GetARCInstKind(Inst); const Value *Arg = nullptr; - DEBUG(dbgs() << "Class: " << Class << "\n"); + DEBUG(dbgs() << " Class: " << Class << "\n"); switch (Class) { - case IC_Release: { - Arg = GetObjCArg(Inst); - - PtrState &S = MyStates.getPtrBottomUpState(Arg); - - // If we see two releases in a row on the same pointer. If so, make - // a note, and we'll cicle back to revisit it after we've - // hopefully eliminated the second release, which may allow us to - // eliminate the first release too. - // Theoretically we could implement removal of nested retain+release - // pairs by making PtrState hold a stack of states, but this is - // simple and avoids adding overhead for the non-nested case. - if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) { - DEBUG(dbgs() << "Found nested releases (i.e. a release pair)\n"); - NestingDetected = true; - } + case ARCInstKind::Release: { + Arg = GetArgRCIdentityRoot(Inst); - MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); - Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release; - ANNOTATE_BOTTOMUP(Inst, Arg, S.GetSeq(), NewSeq); - S.ResetSequenceProgress(NewSeq); - S.SetReleaseMetadata(ReleaseMetadata); - S.SetKnownSafe(S.HasKnownPositiveRefCount()); - S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall()); - S.InsertCall(Inst); - S.SetKnownPositiveRefCount(); + BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg); + NestingDetected |= S.InitBottomUp(MDKindCache, Inst); break; } - case IC_RetainBlock: + case ARCInstKind::RetainBlock: // In OptimizeIndividualCalls, we have strength reduced all optimizable // objc_retainBlocks to objc_retains. Thus at this point any // objc_retainBlocks that we see are not optimizable. break; - case IC_Retain: - case IC_RetainRV: { - Arg = GetObjCArg(Inst); - - PtrState &S = MyStates.getPtrBottomUpState(Arg); - S.SetKnownPositiveRefCount(); - - Sequence OldSeq = S.GetSeq(); - switch (OldSeq) { - case S_Stop: - case S_Release: - case S_MovableRelease: - case S_Use: - // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an - // imprecise release, clear our reverse insertion points. - if (OldSeq != S_Use || S.IsTrackingImpreciseReleases()) - S.ClearReverseInsertPts(); - // FALL THROUGH - case S_CanRelease: - // Don't do retain+release tracking for IC_RetainRV, because it's - // better to let it remain as the first instruction after a call. - if (Class != IC_RetainRV) + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: { + Arg = GetArgRCIdentityRoot(Inst); + BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg); + if (S.MatchWithRetain()) { + // Don't do retain+release tracking for ARCInstKind::RetainRV, because + // it's better to let it remain as the first instruction after a call. + if (Class != ARCInstKind::RetainRV) { + DEBUG(llvm::dbgs() << " Matching with: " << *Inst << "\n"); Retains[Inst] = S.GetRRInfo(); + } S.ClearSequenceProgress(); - break; - case S_None: - break; - case S_Retain: - llvm_unreachable("bottom-up pointer in retain state!"); } - ANNOTATE_BOTTOMUP(Inst, Arg, OldSeq, S.GetSeq()); // A retain moving bottom up can be a use. break; } - case IC_AutoreleasepoolPop: + case ARCInstKind::AutoreleasepoolPop: // Conservatively, clear MyStates for all known pointers. MyStates.clearBottomUpPointers(); return NestingDetected; - case IC_AutoreleasepoolPush: - case IC_None: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::None: // These are irrelevant. return NestingDetected; - case IC_User: + case ARCInstKind::User: // If we have a store into an alloca of a pointer we are tracking, the // pointer has multiple owners implying that we must be more conservative. // @@ -1806,9 +1152,10 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, // in the presence of allocas we only unconditionally remove pointers if // both our retain and our release are KnownSafe. if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { - if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand())) { - BBState::ptr_iterator I = MyStates.findPtrBottomUpState( - StripPointerCastsAndObjCCalls(SI->getValueOperand())); + const DataLayout &DL = BB->getModule()->getDataLayout(); + if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand(), DL)) { + auto I = MyStates.findPtrBottomUpState( + GetRCIdentityRoot(SI->getValueOperand())); if (I != MyStates.bottom_up_ptr_end()) MultiOwnersSet.insert(I->first); } @@ -1820,90 +1167,26 @@ ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, // Consider any other possible effects of this instruction on each // pointer being tracked. - for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(), - ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) { + for (auto MI = MyStates.bottom_up_ptr_begin(), + ME = MyStates.bottom_up_ptr_end(); + MI != ME; ++MI) { const Value *Ptr = MI->first; if (Ptr == Arg) continue; // Handled above. - PtrState &S = MI->second; - Sequence Seq = S.GetSeq(); + BottomUpPtrState &S = MI->second; - // Check for possible releases. - if (CanAlterRefCount(Inst, Ptr, PA, Class)) { - DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr - << "\n"); - S.ClearKnownPositiveRefCount(); - switch (Seq) { - case S_Use: - S.SetSeq(S_CanRelease); - ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S.GetSeq()); - continue; - case S_CanRelease: - case S_Release: - case S_MovableRelease: - case S_Stop: - case S_None: - break; - case S_Retain: - llvm_unreachable("bottom-up pointer in retain state!"); - } - } + if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class)) + continue; - // Check for possible direct uses. - switch (Seq) { - case S_Release: - case S_MovableRelease: - if (CanUse(Inst, Ptr, PA, Class)) { - DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr - << "\n"); - assert(!S.HasReverseInsertPts()); - // If this is an invoke instruction, we're scanning it as part of - // one of its successor blocks, since we can't insert code after it - // in its own block, and we don't want to split critical edges. - if (isa<InvokeInst>(Inst)) - S.InsertReverseInsertPt(BB->getFirstInsertionPt()); - else - S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst))); - S.SetSeq(S_Use); - ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); - } else if (Seq == S_Release && IsUser(Class)) { - DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr - << "\n"); - // Non-movable releases depend on any possible objc pointer use. - S.SetSeq(S_Stop); - ANNOTATE_BOTTOMUP(Inst, Ptr, S_Release, S_Stop); - assert(!S.HasReverseInsertPts()); - // As above; handle invoke specially. - if (isa<InvokeInst>(Inst)) - S.InsertReverseInsertPt(BB->getFirstInsertionPt()); - else - S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst))); - } - break; - case S_Stop: - if (CanUse(Inst, Ptr, PA, Class)) { - DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr - << "\n"); - S.SetSeq(S_Use); - ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); - } - break; - case S_CanRelease: - case S_Use: - case S_None: - break; - case S_Retain: - llvm_unreachable("bottom-up pointer in retain state!"); - } + S.HandlePotentialUse(BB, Inst, Ptr, PA, Class); } return NestingDetected; } -bool -ObjCARCOpt::VisitBottomUp(BasicBlock *BB, - DenseMap<const BasicBlock *, BBState> &BBStates, - MapVector<Value *, RRInfo> &Retains) { +bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB, + DenseMap<const BasicBlock *, BBState> &BBStates, + BlotMapVector<Value *, RRInfo> &Retains) { DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n"); @@ -1928,9 +1211,8 @@ ObjCARCOpt::VisitBottomUp(BasicBlock *BB, } } - // If ARC Annotations are enabled, output the current state of pointers at the - // bottom of the basic block. - ANNOTATE_BOTTOMUP_BBEND(MyStates, BB); + DEBUG(llvm::dbgs() << "Before:\n" << BBStates[BB] << "\n" + << "Performing Dataflow:\n"); // Visit all the instructions, bottom-up. for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) { @@ -1940,7 +1222,7 @@ ObjCARCOpt::VisitBottomUp(BasicBlock *BB, if (isa<InvokeInst>(Inst)) continue; - DEBUG(dbgs() << "Visiting " << *Inst << "\n"); + DEBUG(dbgs() << " Visiting " << *Inst << "\n"); NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates); } @@ -1955,9 +1237,7 @@ ObjCARCOpt::VisitBottomUp(BasicBlock *BB, NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates); } - // If ARC Annotations are enabled, output the current state of pointers at the - // top of the basic block. - ANNOTATE_BOTTOMUP_BBSTART(MyStates, BB); + DEBUG(llvm::dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n"); return NestingDetected; } @@ -1967,146 +1247,66 @@ ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates) { bool NestingDetected = false; - InstructionClass Class = GetInstructionClass(Inst); + ARCInstKind Class = GetARCInstKind(Inst); const Value *Arg = nullptr; + DEBUG(llvm::dbgs() << " Class: " << Class << "\n"); + switch (Class) { - case IC_RetainBlock: + case ARCInstKind::RetainBlock: // In OptimizeIndividualCalls, we have strength reduced all optimizable // objc_retainBlocks to objc_retains. Thus at this point any - // objc_retainBlocks that we see are not optimizable. + // objc_retainBlocks that we see are not optimizable. We need to break since + // a retain can be a potential use. break; - case IC_Retain: - case IC_RetainRV: { - Arg = GetObjCArg(Inst); - - PtrState &S = MyStates.getPtrTopDownState(Arg); - - // Don't do retain+release tracking for IC_RetainRV, because it's - // better to let it remain as the first instruction after a call. - if (Class != IC_RetainRV) { - // If we see two retains in a row on the same pointer. If so, make - // a note, and we'll cicle back to revisit it after we've - // hopefully eliminated the second retain, which may allow us to - // eliminate the first retain too. - // Theoretically we could implement removal of nested retain+release - // pairs by making PtrState hold a stack of states, but this is - // simple and avoids adding overhead for the non-nested case. - if (S.GetSeq() == S_Retain) - NestingDetected = true; - - ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_Retain); - S.ResetSequenceProgress(S_Retain); - S.SetKnownSafe(S.HasKnownPositiveRefCount()); - S.InsertCall(Inst); - } - - S.SetKnownPositiveRefCount(); - + case ARCInstKind::Retain: + case ARCInstKind::RetainRV: { + Arg = GetArgRCIdentityRoot(Inst); + TopDownPtrState &S = MyStates.getPtrTopDownState(Arg); + NestingDetected |= S.InitTopDown(Class, Inst); // A retain can be a potential use; procede to the generic checking // code below. break; } - case IC_Release: { - Arg = GetObjCArg(Inst); - - PtrState &S = MyStates.getPtrTopDownState(Arg); - S.ClearKnownPositiveRefCount(); - - Sequence OldSeq = S.GetSeq(); - - MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); - - switch (OldSeq) { - case S_Retain: - case S_CanRelease: - if (OldSeq == S_Retain || ReleaseMetadata != nullptr) - S.ClearReverseInsertPts(); - // FALL THROUGH - case S_Use: - S.SetReleaseMetadata(ReleaseMetadata); - S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall()); + case ARCInstKind::Release: { + Arg = GetArgRCIdentityRoot(Inst); + TopDownPtrState &S = MyStates.getPtrTopDownState(Arg); + // Try to form a tentative pair in between this release instruction and the + // top down pointers that we are tracking. + if (S.MatchWithRelease(MDKindCache, Inst)) { + // If we succeed, copy S's RRInfo into the Release -> {Retain Set + // Map}. Then we clear S. + DEBUG(llvm::dbgs() << " Matching with: " << *Inst << "\n"); Releases[Inst] = S.GetRRInfo(); - ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_None); S.ClearSequenceProgress(); - break; - case S_None: - break; - case S_Stop: - case S_Release: - case S_MovableRelease: - llvm_unreachable("top-down pointer in release state!"); } break; } - case IC_AutoreleasepoolPop: + case ARCInstKind::AutoreleasepoolPop: // Conservatively, clear MyStates for all known pointers. MyStates.clearTopDownPointers(); - return NestingDetected; - case IC_AutoreleasepoolPush: - case IC_None: - // These are irrelevant. - return NestingDetected; + return false; + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::None: + // These can not be uses of + return false; default: break; } // Consider any other possible effects of this instruction on each // pointer being tracked. - for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(), - ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) { + for (auto MI = MyStates.top_down_ptr_begin(), + ME = MyStates.top_down_ptr_end(); + MI != ME; ++MI) { const Value *Ptr = MI->first; if (Ptr == Arg) continue; // Handled above. - PtrState &S = MI->second; - Sequence Seq = S.GetSeq(); - - // Check for possible releases. - if (CanAlterRefCount(Inst, Ptr, PA, Class)) { - DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr - << "\n"); - S.ClearKnownPositiveRefCount(); - switch (Seq) { - case S_Retain: - S.SetSeq(S_CanRelease); - ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_CanRelease); - assert(!S.HasReverseInsertPts()); - S.InsertReverseInsertPt(Inst); - - // One call can't cause a transition from S_Retain to S_CanRelease - // and S_CanRelease to S_Use. If we've made the first transition, - // we're done. - continue; - case S_Use: - case S_CanRelease: - case S_None: - break; - case S_Stop: - case S_Release: - case S_MovableRelease: - llvm_unreachable("top-down pointer in release state!"); - } - } + TopDownPtrState &S = MI->second; + if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class)) + continue; - // Check for possible direct uses. - switch (Seq) { - case S_CanRelease: - if (CanUse(Inst, Ptr, PA, Class)) { - DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr - << "\n"); - S.SetSeq(S_Use); - ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_Use); - } - break; - case S_Retain: - case S_Use: - case S_None: - break; - case S_Stop: - case S_Release: - case S_MovableRelease: - llvm_unreachable("top-down pointer in release state!"); - } + S.HandlePotentialUse(Inst, Ptr, PA, Class); } return NestingDetected; @@ -2138,27 +1338,22 @@ ObjCARCOpt::VisitTopDown(BasicBlock *BB, } } - // If ARC Annotations are enabled, output the current state of pointers at the - // top of the basic block. - ANNOTATE_TOPDOWN_BBSTART(MyStates, BB); + DEBUG(llvm::dbgs() << "Before:\n" << BBStates[BB] << "\n" + << "Performing Dataflow:\n"); // Visit all the instructions, top-down. for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { Instruction *Inst = I; - DEBUG(dbgs() << "Visiting " << *Inst << "\n"); + DEBUG(dbgs() << " Visiting " << *Inst << "\n"); NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates); } - // If ARC Annotations are enabled, output the current state of pointers at the - // bottom of the basic block. - ANNOTATE_TOPDOWN_BBEND(MyStates, BB); - -#ifdef ARC_ANNOTATIONS - if (!(EnableARCAnnotations && DisableCheckForCFGHazards)) -#endif + DEBUG(llvm::dbgs() << "\nState Before Checking for CFG Hazards:\n" + << BBStates[BB] << "\n\n"); CheckForCFGHazards(BB, BBStates, MyStates); + DEBUG(llvm::dbgs() << "Final State:\n" << BBStates[BB] << "\n"); return NestingDetected; } @@ -2244,11 +1439,10 @@ ComputePostOrders(Function &F, } // Visit the function both top-down and bottom-up. -bool -ObjCARCOpt::Visit(Function &F, - DenseMap<const BasicBlock *, BBState> &BBStates, - MapVector<Value *, RRInfo> &Retains, - DenseMap<Value *, RRInfo> &Releases) { +bool ObjCARCOpt::Visit(Function &F, + DenseMap<const BasicBlock *, BBState> &BBStates, + BlotMapVector<Value *, RRInfo> &Retains, + DenseMap<Value *, RRInfo> &Releases) { // Use reverse-postorder traversals, because we magically know that loops // will be well behaved, i.e. they won't repeatedly call retain on a single @@ -2258,7 +1452,7 @@ ObjCARCOpt::Visit(Function &F, SmallVector<BasicBlock *, 16> PostOrder; SmallVector<BasicBlock *, 16> ReverseCFGPostOrder; ComputePostOrders(F, PostOrder, ReverseCFGPostOrder, - NoObjCARCExceptionsMDKind, + MDKindCache.get(ARCMDKindID::NoObjCARCExceptions), BBStates); // Use reverse-postorder on the reverse CFG for bottom-up. @@ -2279,10 +1473,9 @@ ObjCARCOpt::Visit(Function &F, } /// Move the calls in RetainsToMove and ReleasesToMove. -void ObjCARCOpt::MoveCalls(Value *Arg, - RRInfo &RetainsToMove, +void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove, - MapVector<Value *, RRInfo> &Retains, + BlotMapVector<Value *, RRInfo> &Retains, DenseMap<Value *, RRInfo> &Releases, SmallVectorImpl<Instruction *> &DeadInsts, Module *M) { @@ -2295,7 +1488,7 @@ void ObjCARCOpt::MoveCalls(Value *Arg, for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) { Value *MyArg = ArgTy == ParamTy ? Arg : new BitCastInst(Arg, ParamTy, "", InsertPt); - Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); + Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain); CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt); Call->setDoesNotThrow(); Call->setTailCall(); @@ -2306,11 +1499,11 @@ void ObjCARCOpt::MoveCalls(Value *Arg, for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) { Value *MyArg = ArgTy == ParamTy ? Arg : new BitCastInst(Arg, ParamTy, "", InsertPt); - Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release); + Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Release); CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt); // Attach a clang.imprecise_release metadata tag, if appropriate. if (MDNode *M = ReleasesToMove.ReleaseMetadata) - Call->setMetadata(ImpreciseReleaseMDKind, M); + Call->setMetadata(MDKindCache.get(ARCMDKindID::ImpreciseRelease), M); Call->setDoesNotThrow(); if (ReleasesToMove.IsTailCallRelease) Call->setTailCall(); @@ -2333,20 +1526,15 @@ void ObjCARCOpt::MoveCalls(Value *Arg, } -bool -ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> - &BBStates, - MapVector<Value *, RRInfo> &Retains, - DenseMap<Value *, RRInfo> &Releases, - Module *M, - SmallVectorImpl<Instruction *> &NewRetains, - SmallVectorImpl<Instruction *> &NewReleases, - SmallVectorImpl<Instruction *> &DeadInsts, - RRInfo &RetainsToMove, - RRInfo &ReleasesToMove, - Value *Arg, - bool KnownSafe, - bool &AnyPairsCompletelyEliminated) { +bool ObjCARCOpt::PairUpRetainsAndReleases( + DenseMap<const BasicBlock *, BBState> &BBStates, + BlotMapVector<Value *, RRInfo> &Retains, + DenseMap<Value *, RRInfo> &Releases, Module *M, + SmallVectorImpl<Instruction *> &NewRetains, + SmallVectorImpl<Instruction *> &NewReleases, + SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove, + RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe, + bool &AnyPairsCompletelyEliminated) { // If a pair happens in a region where it is known that the reference count // is already incremented, we can similarly ignore possible decrements unless // we are dealing with a retainable object with multiple provenance sources. @@ -2367,15 +1555,14 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> for (SmallVectorImpl<Instruction *>::const_iterator NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) { Instruction *NewRetain = *NI; - MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain); + auto It = Retains.find(NewRetain); assert(It != Retains.end()); const RRInfo &NewRetainRRI = It->second; KnownSafeTD &= NewRetainRRI.KnownSafe; MultipleOwners = - MultipleOwners || MultiOwnersSet.count(GetObjCArg(NewRetain)); + MultipleOwners || MultiOwnersSet.count(GetArgRCIdentityRoot(NewRetain)); for (Instruction *NewRetainRelease : NewRetainRRI.Calls) { - DenseMap<Value *, RRInfo>::const_iterator Jt = - Releases.find(NewRetainRelease); + auto Jt = Releases.find(NewRetainRelease); if (Jt == Releases.end()) return false; const RRInfo &NewRetainReleaseRRI = Jt->second; @@ -2444,15 +1631,13 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> for (SmallVectorImpl<Instruction *>::const_iterator NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) { Instruction *NewRelease = *NI; - DenseMap<Value *, RRInfo>::const_iterator It = - Releases.find(NewRelease); + auto It = Releases.find(NewRelease); assert(It != Releases.end()); const RRInfo &NewReleaseRRI = It->second; KnownSafeBU &= NewReleaseRRI.KnownSafe; CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted; for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) { - MapVector<Value *, RRInfo>::const_iterator Jt = - Retains.find(NewReleaseRetain); + auto Jt = Retains.find(NewReleaseRetain); if (Jt == Retains.end()) return false; const RRInfo &NewReleaseRetainRRI = Jt->second; @@ -2504,11 +1689,8 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> if (NewRetains.empty()) break; } - // If the pointer is known incremented in 1 direction and we do not have - // MultipleOwners, we can safely remove the retain/releases. Otherwise we need - // to be known safe in both directions. - bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU) || - ((KnownSafeTD || KnownSafeBU) && !MultipleOwners); + // We can only remove pointers if we are known safe in both directions. + bool UnconditionallySafe = KnownSafeTD && KnownSafeBU; if (UnconditionallySafe) { RetainsToMove.ReverseInsertPts.clear(); ReleasesToMove.ReverseInsertPts.clear(); @@ -2538,12 +1720,6 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> if (OldDelta != 0) return false; -#ifdef ARC_ANNOTATIONS - // Do not move calls if ARC annotations are requested. - if (EnableARCAnnotations) - return false; -#endif // ARC_ANNOTATIONS - Changed = true; assert(OldCount != 0 && "Unreachable code?"); NumRRs += OldCount - NewCount; @@ -2556,12 +1732,10 @@ ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> /// Identify pairings between the retains and releases, and delete and/or move /// them. -bool -ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState> - &BBStates, - MapVector<Value *, RRInfo> &Retains, - DenseMap<Value *, RRInfo> &Releases, - Module *M) { +bool ObjCARCOpt::PerformCodePlacement( + DenseMap<const BasicBlock *, BBState> &BBStates, + BlotMapVector<Value *, RRInfo> &Retains, + DenseMap<Value *, RRInfo> &Releases, Module *M) { DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n"); bool AnyPairsCompletelyEliminated = false; @@ -2572,8 +1746,9 @@ ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState> SmallVector<Instruction *, 8> DeadInsts; // Visit each retain. - for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(), - E = Retains.end(); I != E; ++I) { + for (BlotMapVector<Value *, RRInfo>::const_iterator I = Retains.begin(), + E = Retains.end(); + I != E; ++I) { Value *V = I->first; if (!V) continue; // blotted @@ -2581,7 +1756,7 @@ ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState> DEBUG(dbgs() << "Visiting: " << *Retain << "\n"); - Value *Arg = GetObjCArg(Retain); + Value *Arg = GetArgRCIdentityRoot(Retain); // If the object being released is in static or stack storage, we know it's // not being managed by ObjC reference counting, so we can delete pairs @@ -2593,18 +1768,17 @@ ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState> if (const LoadInst *LI = dyn_cast<LoadInst>(Arg)) if (const GlobalVariable *GV = dyn_cast<GlobalVariable>( - StripPointerCastsAndObjCCalls(LI->getPointerOperand()))) + GetRCIdentityRoot(LI->getPointerOperand()))) if (GV->isConstant()) KnownSafe = true; // Connect the dots between the top-down-collected RetainsToMove and // bottom-up-collected ReleasesToMove to form sets of related calls. NewRetains.push_back(Retain); - bool PerformMoveCalls = - ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains, - NewReleases, DeadInsts, RetainsToMove, - ReleasesToMove, Arg, KnownSafe, - AnyPairsCompletelyEliminated); + bool PerformMoveCalls = PairUpRetainsAndReleases( + BBStates, Retains, Releases, M, NewRetains, NewReleases, DeadInsts, + RetainsToMove, ReleasesToMove, Arg, KnownSafe, + AnyPairsCompletelyEliminated); if (PerformMoveCalls) { // Ok, everything checks out and we're all set. Let's move/delete some @@ -2640,12 +1814,13 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { DEBUG(dbgs() << "Visiting: " << *Inst << "\n"); - InstructionClass Class = GetBasicInstructionClass(Inst); - if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained) + ARCInstKind Class = GetBasicARCInstKind(Inst); + if (Class != ARCInstKind::LoadWeak && + Class != ARCInstKind::LoadWeakRetained) continue; // Delete objc_loadWeak calls with no users. - if (Class == IC_LoadWeak && Inst->use_empty()) { + if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) { Inst->eraseFromParent(); continue; } @@ -2660,10 +1835,10 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { J = Current.getInstructionIterator(); J != B; --J) { Instruction *EarlierInst = &*std::prev(J); - InstructionClass EarlierClass = GetInstructionClass(EarlierInst); + ARCInstKind EarlierClass = GetARCInstKind(EarlierInst); switch (EarlierClass) { - case IC_LoadWeak: - case IC_LoadWeakRetained: { + case ARCInstKind::LoadWeak: + case ARCInstKind::LoadWeakRetained: { // If this is loading from the same pointer, replace this load's value // with that one. CallInst *Call = cast<CallInst>(Inst); @@ -2674,8 +1849,8 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { case AliasAnalysis::MustAlias: Changed = true; // If the load has a builtin retain, insert a plain retain for it. - if (Class == IC_LoadWeakRetained) { - Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); + if (Class == ARCInstKind::LoadWeakRetained) { + Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain); CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call); CI->setTailCall(); } @@ -2691,8 +1866,8 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { } break; } - case IC_StoreWeak: - case IC_InitWeak: { + case ARCInstKind::StoreWeak: + case ARCInstKind::InitWeak: { // If this is storing to the same pointer and has the same size etc. // replace this load's value with the stored value. CallInst *Call = cast<CallInst>(Inst); @@ -2703,8 +1878,8 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { case AliasAnalysis::MustAlias: Changed = true; // If the load has a builtin retain, insert a plain retain for it. - if (Class == IC_LoadWeakRetained) { - Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); + if (Class == ARCInstKind::LoadWeakRetained) { + Constant *Decl = EP.get(ARCRuntimeEntryPointKind::Retain); CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call); CI->setTailCall(); } @@ -2720,14 +1895,14 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { } break; } - case IC_MoveWeak: - case IC_CopyWeak: + case ARCInstKind::MoveWeak: + case ARCInstKind::CopyWeak: // TOOD: Grab the copied value. goto clobbered; - case IC_AutoreleasepoolPush: - case IC_None: - case IC_IntrinsicUser: - case IC_User: + case ARCInstKind::AutoreleasepoolPush: + case ARCInstKind::None: + case ARCInstKind::IntrinsicUser: + case ARCInstKind::User: // Weak pointers are only modified through the weak entry points // (and arbitrary calls, which could call the weak entry points). break; @@ -2743,8 +1918,8 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { // the alloca and all its users can be zapped. for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { Instruction *Inst = &*I++; - InstructionClass Class = GetBasicInstructionClass(Inst); - if (Class != IC_DestroyWeak) + ARCInstKind Class = GetBasicARCInstKind(Inst); + if (Class != ARCInstKind::DestroyWeak) continue; CallInst *Call = cast<CallInst>(Inst); @@ -2752,10 +1927,10 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) { for (User *U : Alloca->users()) { const Instruction *UserInst = cast<Instruction>(U); - switch (GetBasicInstructionClass(UserInst)) { - case IC_InitWeak: - case IC_StoreWeak: - case IC_DestroyWeak: + switch (GetBasicARCInstKind(UserInst)) { + case ARCInstKind::InitWeak: + case ARCInstKind::StoreWeak: + case ARCInstKind::DestroyWeak: continue; default: goto done; @@ -2764,13 +1939,13 @@ void ObjCARCOpt::OptimizeWeakCalls(Function &F) { Changed = true; for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) { CallInst *UserInst = cast<CallInst>(*UI++); - switch (GetBasicInstructionClass(UserInst)) { - case IC_InitWeak: - case IC_StoreWeak: + switch (GetBasicARCInstKind(UserInst)) { + case ARCInstKind::InitWeak: + case ARCInstKind::StoreWeak: // These functions return their second argument. UserInst->replaceAllUsesWith(UserInst->getArgOperand(1)); break; - case IC_DestroyWeak: + case ARCInstKind::DestroyWeak: // No return value. break; default: @@ -2792,7 +1967,7 @@ bool ObjCARCOpt::OptimizeSequences(Function &F) { // map stays valid when we get around to rewriting code and calls get // replaced by arguments. DenseMap<Value *, RRInfo> Releases; - MapVector<Value *, RRInfo> Retains; + BlotMapVector<Value *, RRInfo> Retains; // This is used during the traversal of the function to track the // states for each identified object at each block. @@ -2825,16 +2000,15 @@ HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain, if (DepInsts.size() != 1) return false; - CallInst *Call = - dyn_cast_or_null<CallInst>(*DepInsts.begin()); + auto *Call = dyn_cast_or_null<CallInst>(*DepInsts.begin()); // Check that the pointer is the return value of the call. if (!Call || Arg != Call) return false; // Check that the call is a regular call. - InstructionClass Class = GetBasicInstructionClass(Call); - if (Class != IC_CallOrUser && Class != IC_Call) + ARCInstKind Class = GetBasicARCInstKind(Call); + if (Class != ARCInstKind::CallOrUser && Class != ARCInstKind::Call) return false; return true; @@ -2854,13 +2028,11 @@ FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB, if (DepInsts.size() != 1) return nullptr; - CallInst *Retain = - dyn_cast_or_null<CallInst>(*DepInsts.begin()); + auto *Retain = dyn_cast_or_null<CallInst>(*DepInsts.begin()); // Check that we found a retain with the same argument. - if (!Retain || - !IsRetain(GetBasicInstructionClass(Retain)) || - GetObjCArg(Retain) != Arg) { + if (!Retain || !IsRetain(GetBasicARCInstKind(Retain)) || + GetArgRCIdentityRoot(Retain) != Arg) { return nullptr; } @@ -2881,14 +2053,13 @@ FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB, if (DepInsts.size() != 1) return nullptr; - CallInst *Autorelease = - dyn_cast_or_null<CallInst>(*DepInsts.begin()); + auto *Autorelease = dyn_cast_or_null<CallInst>(*DepInsts.begin()); if (!Autorelease) return nullptr; - InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease); + ARCInstKind AutoreleaseClass = GetBasicARCInstKind(Autorelease); if (!IsAutorelease(AutoreleaseClass)) return nullptr; - if (GetObjCArg(Autorelease) != Arg) + if (GetArgRCIdentityRoot(Autorelease) != Arg) return nullptr; return Autorelease; @@ -2919,7 +2090,7 @@ void ObjCARCOpt::OptimizeReturns(Function &F) { if (!Ret) continue; - const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0)); + const Value *Arg = GetRCIdentityRoot(Ret->getOperand(0)); // Look for an ``autorelease'' instruction that is a predecessor of Ret and // dependent on Arg such that there are no instructions dependent on Arg @@ -2974,13 +2145,13 @@ ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) { for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { Instruction *Inst = &*I++; - switch (GetBasicInstructionClass(Inst)) { + switch (GetBasicARCInstKind(Inst)) { default: break; - case IC_Retain: + case ARCInstKind::Retain: ++NumRetains; break; - case IC_Release: + case ARCInstKind::Release: ++NumReleases; break; } @@ -2997,28 +2168,13 @@ bool ObjCARCOpt::doInitialization(Module &M) { if (!Run) return false; - // Identify the imprecise release metadata kind. - ImpreciseReleaseMDKind = - M.getContext().getMDKindID("clang.imprecise_release"); - CopyOnEscapeMDKind = - M.getContext().getMDKindID("clang.arc.copy_on_escape"); - NoObjCARCExceptionsMDKind = - M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions"); -#ifdef ARC_ANNOTATIONS - ARCAnnotationBottomUpMDKind = - M.getContext().getMDKindID("llvm.arc.annotation.bottomup"); - ARCAnnotationTopDownMDKind = - M.getContext().getMDKindID("llvm.arc.annotation.topdown"); - ARCAnnotationProvenanceSourceMDKind = - M.getContext().getMDKindID("llvm.arc.annotation.provenancesource"); -#endif // ARC_ANNOTATIONS - // Intuitively, objc_retain and others are nocapture, however in practice // they are not, because they return their argument value. And objc_release // calls finalizers which can have arbitrary side effects. + MDKindCache.init(&M); // Initialize our runtime entry point cache. - EP.Initialize(&M); + EP.init(&M); return false; } @@ -3052,27 +2208,27 @@ bool ObjCARCOpt::runOnFunction(Function &F) { OptimizeIndividualCalls(F); // Optimizations for weak pointers. - if (UsedInThisFunction & ((1 << IC_LoadWeak) | - (1 << IC_LoadWeakRetained) | - (1 << IC_StoreWeak) | - (1 << IC_InitWeak) | - (1 << IC_CopyWeak) | - (1 << IC_MoveWeak) | - (1 << IC_DestroyWeak))) + if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) | + (1 << unsigned(ARCInstKind::LoadWeakRetained)) | + (1 << unsigned(ARCInstKind::StoreWeak)) | + (1 << unsigned(ARCInstKind::InitWeak)) | + (1 << unsigned(ARCInstKind::CopyWeak)) | + (1 << unsigned(ARCInstKind::MoveWeak)) | + (1 << unsigned(ARCInstKind::DestroyWeak)))) OptimizeWeakCalls(F); // Optimizations for retain+release pairs. - if (UsedInThisFunction & ((1 << IC_Retain) | - (1 << IC_RetainRV) | - (1 << IC_RetainBlock))) - if (UsedInThisFunction & (1 << IC_Release)) + if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) | + (1 << unsigned(ARCInstKind::RetainRV)) | + (1 << unsigned(ARCInstKind::RetainBlock)))) + if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release))) // Run OptimizeSequences until it either stops making changes or // no retain+release pair nesting is detected. while (OptimizeSequences(F)) {} // Optimizations if objc_autorelease is used. - if (UsedInThisFunction & ((1 << IC_Autorelease) | - (1 << IC_AutoreleaseRV))) + if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) | + (1 << unsigned(ARCInstKind::AutoreleaseRV)))) OptimizeReturns(F); // Gather statistics after optimization. diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCUtil.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCUtil.cpp deleted file mode 100644 index 53c077e..0000000 --- a/contrib/llvm/lib/Transforms/ObjCARC/ObjCARCUtil.cpp +++ /dev/null @@ -1,254 +0,0 @@ -//===- ObjCARCUtil.cpp - ObjC ARC Optimization ----------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// \file -/// This file defines several utility functions used by various ARC -/// optimizations which are IMHO too big to be in a header file. -/// -/// WARNING: This file knows about certain library functions. It recognizes them -/// by name, and hardwires knowledge of their semantics. -/// -/// WARNING: This file knows about how certain Objective-C library functions are -/// used. Naive LLVM IR transformations which would otherwise be -/// behavior-preserving may break these assumptions. -/// -//===----------------------------------------------------------------------===// - -#include "ObjCARC.h" -#include "llvm/IR/Intrinsics.h" - -using namespace llvm; -using namespace llvm::objcarc; - -raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, - const InstructionClass Class) { - switch (Class) { - case IC_Retain: - return OS << "IC_Retain"; - case IC_RetainRV: - return OS << "IC_RetainRV"; - case IC_RetainBlock: - return OS << "IC_RetainBlock"; - case IC_Release: - return OS << "IC_Release"; - case IC_Autorelease: - return OS << "IC_Autorelease"; - case IC_AutoreleaseRV: - return OS << "IC_AutoreleaseRV"; - case IC_AutoreleasepoolPush: - return OS << "IC_AutoreleasepoolPush"; - case IC_AutoreleasepoolPop: - return OS << "IC_AutoreleasepoolPop"; - case IC_NoopCast: - return OS << "IC_NoopCast"; - case IC_FusedRetainAutorelease: - return OS << "IC_FusedRetainAutorelease"; - case IC_FusedRetainAutoreleaseRV: - return OS << "IC_FusedRetainAutoreleaseRV"; - case IC_LoadWeakRetained: - return OS << "IC_LoadWeakRetained"; - case IC_StoreWeak: - return OS << "IC_StoreWeak"; - case IC_InitWeak: - return OS << "IC_InitWeak"; - case IC_LoadWeak: - return OS << "IC_LoadWeak"; - case IC_MoveWeak: - return OS << "IC_MoveWeak"; - case IC_CopyWeak: - return OS << "IC_CopyWeak"; - case IC_DestroyWeak: - return OS << "IC_DestroyWeak"; - case IC_StoreStrong: - return OS << "IC_StoreStrong"; - case IC_CallOrUser: - return OS << "IC_CallOrUser"; - case IC_Call: - return OS << "IC_Call"; - case IC_User: - return OS << "IC_User"; - case IC_IntrinsicUser: - return OS << "IC_IntrinsicUser"; - case IC_None: - return OS << "IC_None"; - } - llvm_unreachable("Unknown instruction class!"); -} - -InstructionClass llvm::objcarc::GetFunctionClass(const Function *F) { - Function::const_arg_iterator AI = F->arg_begin(), AE = F->arg_end(); - - // No (mandatory) arguments. - if (AI == AE) - return StringSwitch<InstructionClass>(F->getName()) - .Case("objc_autoreleasePoolPush", IC_AutoreleasepoolPush) - .Case("clang.arc.use", IC_IntrinsicUser) - .Default(IC_CallOrUser); - - // One argument. - const Argument *A0 = AI++; - if (AI == AE) - // Argument is a pointer. - if (PointerType *PTy = dyn_cast<PointerType>(A0->getType())) { - Type *ETy = PTy->getElementType(); - // Argument is i8*. - if (ETy->isIntegerTy(8)) - return StringSwitch<InstructionClass>(F->getName()) - .Case("objc_retain", IC_Retain) - .Case("objc_retainAutoreleasedReturnValue", IC_RetainRV) - .Case("objc_retainBlock", IC_RetainBlock) - .Case("objc_release", IC_Release) - .Case("objc_autorelease", IC_Autorelease) - .Case("objc_autoreleaseReturnValue", IC_AutoreleaseRV) - .Case("objc_autoreleasePoolPop", IC_AutoreleasepoolPop) - .Case("objc_retainedObject", IC_NoopCast) - .Case("objc_unretainedObject", IC_NoopCast) - .Case("objc_unretainedPointer", IC_NoopCast) - .Case("objc_retain_autorelease", IC_FusedRetainAutorelease) - .Case("objc_retainAutorelease", IC_FusedRetainAutorelease) - .Case("objc_retainAutoreleaseReturnValue",IC_FusedRetainAutoreleaseRV) - .Case("objc_sync_enter", IC_User) - .Case("objc_sync_exit", IC_User) - .Default(IC_CallOrUser); - - // Argument is i8** - if (PointerType *Pte = dyn_cast<PointerType>(ETy)) - if (Pte->getElementType()->isIntegerTy(8)) - return StringSwitch<InstructionClass>(F->getName()) - .Case("objc_loadWeakRetained", IC_LoadWeakRetained) - .Case("objc_loadWeak", IC_LoadWeak) - .Case("objc_destroyWeak", IC_DestroyWeak) - .Default(IC_CallOrUser); - } - - // Two arguments, first is i8**. - const Argument *A1 = AI++; - if (AI == AE) - if (PointerType *PTy = dyn_cast<PointerType>(A0->getType())) - if (PointerType *Pte = dyn_cast<PointerType>(PTy->getElementType())) - if (Pte->getElementType()->isIntegerTy(8)) - if (PointerType *PTy1 = dyn_cast<PointerType>(A1->getType())) { - Type *ETy1 = PTy1->getElementType(); - // Second argument is i8* - if (ETy1->isIntegerTy(8)) - return StringSwitch<InstructionClass>(F->getName()) - .Case("objc_storeWeak", IC_StoreWeak) - .Case("objc_initWeak", IC_InitWeak) - .Case("objc_storeStrong", IC_StoreStrong) - .Default(IC_CallOrUser); - // Second argument is i8**. - if (PointerType *Pte1 = dyn_cast<PointerType>(ETy1)) - if (Pte1->getElementType()->isIntegerTy(8)) - return StringSwitch<InstructionClass>(F->getName()) - .Case("objc_moveWeak", IC_MoveWeak) - .Case("objc_copyWeak", IC_CopyWeak) - // Ignore annotation calls. This is important to stop the - // optimizer from treating annotations as uses which would - // make the state of the pointers they are attempting to - // elucidate to be incorrect. - .Case("llvm.arc.annotation.topdown.bbstart", IC_None) - .Case("llvm.arc.annotation.topdown.bbend", IC_None) - .Case("llvm.arc.annotation.bottomup.bbstart", IC_None) - .Case("llvm.arc.annotation.bottomup.bbend", IC_None) - .Default(IC_CallOrUser); - } - - // Anything else. - return IC_CallOrUser; -} - -/// \brief Determine what kind of construct V is. -InstructionClass -llvm::objcarc::GetInstructionClass(const Value *V) { - if (const Instruction *I = dyn_cast<Instruction>(V)) { - // Any instruction other than bitcast and gep with a pointer operand have a - // use of an objc pointer. Bitcasts, GEPs, Selects, PHIs transfer a pointer - // to a subsequent use, rather than using it themselves, in this sense. - // As a short cut, several other opcodes are known to have no pointer - // operands of interest. And ret is never followed by a release, so it's - // not interesting to examine. - switch (I->getOpcode()) { - case Instruction::Call: { - const CallInst *CI = cast<CallInst>(I); - // Check for calls to special functions. - if (const Function *F = CI->getCalledFunction()) { - InstructionClass Class = GetFunctionClass(F); - if (Class != IC_CallOrUser) - return Class; - - // None of the intrinsic functions do objc_release. For intrinsics, the - // only question is whether or not they may be users. - switch (F->getIntrinsicID()) { - case Intrinsic::returnaddress: case Intrinsic::frameaddress: - case Intrinsic::stacksave: case Intrinsic::stackrestore: - case Intrinsic::vastart: case Intrinsic::vacopy: case Intrinsic::vaend: - case Intrinsic::objectsize: case Intrinsic::prefetch: - case Intrinsic::stackprotector: - case Intrinsic::eh_return_i32: case Intrinsic::eh_return_i64: - case Intrinsic::eh_typeid_for: case Intrinsic::eh_dwarf_cfa: - case Intrinsic::eh_sjlj_lsda: case Intrinsic::eh_sjlj_functioncontext: - case Intrinsic::init_trampoline: case Intrinsic::adjust_trampoline: - case Intrinsic::lifetime_start: case Intrinsic::lifetime_end: - case Intrinsic::invariant_start: case Intrinsic::invariant_end: - // Don't let dbg info affect our results. - case Intrinsic::dbg_declare: case Intrinsic::dbg_value: - // Short cut: Some intrinsics obviously don't use ObjC pointers. - return IC_None; - default: - break; - } - } - return GetCallSiteClass(CI); - } - case Instruction::Invoke: - return GetCallSiteClass(cast<InvokeInst>(I)); - case Instruction::BitCast: - case Instruction::GetElementPtr: - case Instruction::Select: case Instruction::PHI: - case Instruction::Ret: case Instruction::Br: - case Instruction::Switch: case Instruction::IndirectBr: - case Instruction::Alloca: case Instruction::VAArg: - case Instruction::Add: case Instruction::FAdd: - case Instruction::Sub: case Instruction::FSub: - case Instruction::Mul: case Instruction::FMul: - case Instruction::SDiv: case Instruction::UDiv: case Instruction::FDiv: - case Instruction::SRem: case Instruction::URem: case Instruction::FRem: - case Instruction::Shl: case Instruction::LShr: case Instruction::AShr: - case Instruction::And: case Instruction::Or: case Instruction::Xor: - case Instruction::SExt: case Instruction::ZExt: case Instruction::Trunc: - case Instruction::IntToPtr: case Instruction::FCmp: - case Instruction::FPTrunc: case Instruction::FPExt: - case Instruction::FPToUI: case Instruction::FPToSI: - case Instruction::UIToFP: case Instruction::SIToFP: - case Instruction::InsertElement: case Instruction::ExtractElement: - case Instruction::ShuffleVector: - case Instruction::ExtractValue: - break; - case Instruction::ICmp: - // Comparing a pointer with null, or any other constant, isn't an - // interesting use, because we don't care what the pointer points to, or - // about the values of any other dynamic reference-counted pointers. - if (IsPotentialRetainableObjPtr(I->getOperand(1))) - return IC_User; - break; - default: - // For anything else, check all the operands. - // Note that this includes both operands of a Store: while the first - // operand isn't actually being dereferenced, it is being stored to - // memory where we can no longer track who might read it and dereference - // it, so we have to consider it potentially used. - for (User::const_op_iterator OI = I->op_begin(), OE = I->op_end(); - OI != OE; ++OI) - if (IsPotentialRetainableObjPtr(*OI)) - return IC_User; - } - } - - // Otherwise, it's totally inert for ARC purposes. - return IC_None; -} diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp index 410abfc..8346345 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp +++ b/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp @@ -32,20 +32,22 @@ using namespace llvm::objcarc; bool ProvenanceAnalysis::relatedSelect(const SelectInst *A, const Value *B) { + const DataLayout &DL = A->getModule()->getDataLayout(); // If the values are Selects with the same condition, we can do a more precise // check: just check for relations between the values on corresponding arms. if (const SelectInst *SB = dyn_cast<SelectInst>(B)) if (A->getCondition() == SB->getCondition()) - return related(A->getTrueValue(), SB->getTrueValue()) || - related(A->getFalseValue(), SB->getFalseValue()); + return related(A->getTrueValue(), SB->getTrueValue(), DL) || + related(A->getFalseValue(), SB->getFalseValue(), DL); // Check both arms of the Select node individually. - return related(A->getTrueValue(), B) || - related(A->getFalseValue(), B); + return related(A->getTrueValue(), B, DL) || + related(A->getFalseValue(), B, DL); } bool ProvenanceAnalysis::relatedPHI(const PHINode *A, const Value *B) { + const DataLayout &DL = A->getModule()->getDataLayout(); // If the values are PHIs in the same block, we can do a more precise as well // as efficient check: just check for relations between the values on // corresponding edges. @@ -53,16 +55,15 @@ bool ProvenanceAnalysis::relatedPHI(const PHINode *A, if (PNB->getParent() == A->getParent()) { for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) if (related(A->getIncomingValue(i), - PNB->getIncomingValueForBlock(A->getIncomingBlock(i)))) + PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL)) return true; return false; } // Check each unique source of the PHI node against B. SmallPtrSet<const Value *, 4> UniqueSrc; - for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) { - const Value *PV1 = A->getIncomingValue(i); - if (UniqueSrc.insert(PV1).second && related(PV1, B)) + for (Value *PV1 : A->incoming_values()) { + if (UniqueSrc.insert(PV1).second && related(PV1, B, DL)) return true; } @@ -103,11 +104,11 @@ static bool IsStoredObjCPointer(const Value *P) { return false; } -bool ProvenanceAnalysis::relatedCheck(const Value *A, - const Value *B) { +bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B, + const DataLayout &DL) { // Skip past provenance pass-throughs. - A = GetUnderlyingObjCPtr(A); - B = GetUnderlyingObjCPtr(B); + A = GetUnderlyingObjCPtr(A, DL); + B = GetUnderlyingObjCPtr(B, DL); // Quick check. if (A == B) @@ -159,8 +160,8 @@ bool ProvenanceAnalysis::relatedCheck(const Value *A, return true; } -bool ProvenanceAnalysis::related(const Value *A, - const Value *B) { +bool ProvenanceAnalysis::related(const Value *A, const Value *B, + const DataLayout &DL) { // Begin by inserting a conservative value into the map. If the insertion // fails, we have the answer already. If it succeeds, leave it there until we // compute the real answer to guard against recursive queries. @@ -170,7 +171,7 @@ bool ProvenanceAnalysis::related(const Value *A, if (!Pair.second) return Pair.first->second; - bool Result = relatedCheck(A, B); + bool Result = relatedCheck(A, B, DL); CachedResults[ValuePairTy(A, B)] = Result; return Result; } diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.h b/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.h index 7820468..0ac41d3 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.h +++ b/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.h @@ -30,6 +30,7 @@ namespace llvm { class Value; class AliasAnalysis; + class DataLayout; class PHINode; class SelectInst; } @@ -53,12 +54,12 @@ class ProvenanceAnalysis { typedef DenseMap<ValuePairTy, bool> CachedResultsTy; CachedResultsTy CachedResults; - bool relatedCheck(const Value *A, const Value *B); + bool relatedCheck(const Value *A, const Value *B, const DataLayout &DL); bool relatedSelect(const SelectInst *A, const Value *B); bool relatedPHI(const PHINode *A, const Value *B); - void operator=(const ProvenanceAnalysis &) LLVM_DELETED_FUNCTION; - ProvenanceAnalysis(const ProvenanceAnalysis &) LLVM_DELETED_FUNCTION; + void operator=(const ProvenanceAnalysis &) = delete; + ProvenanceAnalysis(const ProvenanceAnalysis &) = delete; public: ProvenanceAnalysis() {} @@ -67,7 +68,7 @@ public: AliasAnalysis *getAA() const { return AA; } - bool related(const Value *A, const Value *B); + bool related(const Value *A, const Value *B, const DataLayout &DL); void clear() { CachedResults.clear(); diff --git a/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysisEvaluator.cpp b/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysisEvaluator.cpp index d836632..0be75af 100644 --- a/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysisEvaluator.cpp +++ b/contrib/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysisEvaluator.cpp @@ -14,6 +14,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -65,6 +66,7 @@ bool PAEval::runOnFunction(Function &F) { ProvenanceAnalysis PA; PA.setAA(&getAnalysis<AliasAnalysis>()); + const DataLayout &DL = F.getParent()->getDataLayout(); for (Value *V1 : Values) { StringRef NameV1 = getName(V1); @@ -73,7 +75,7 @@ bool PAEval::runOnFunction(Function &F) { if (NameV1 >= NameV2) continue; errs() << NameV1 << " and " << NameV2; - if (PA.related(V1, V2)) + if (PA.related(V1, V2, DL)) errs() << " are related.\n"; else errs() << " are not related.\n"; diff --git a/contrib/llvm/lib/Transforms/ObjCARC/PtrState.cpp b/contrib/llvm/lib/Transforms/ObjCARC/PtrState.cpp new file mode 100644 index 0000000..ae20e7e --- /dev/null +++ b/contrib/llvm/lib/Transforms/ObjCARC/PtrState.cpp @@ -0,0 +1,404 @@ +//===--- PtrState.cpp -----------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "PtrState.h" +#include "DependencyAnalysis.h" +#include "ObjCARC.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; +using namespace llvm::objcarc; + +#define DEBUG_TYPE "objc-arc-ptr-state" + +//===----------------------------------------------------------------------===// +// Utility +//===----------------------------------------------------------------------===// + +raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, const Sequence S) { + switch (S) { + case S_None: + return OS << "S_None"; + case S_Retain: + return OS << "S_Retain"; + case S_CanRelease: + return OS << "S_CanRelease"; + case S_Use: + return OS << "S_Use"; + case S_Release: + return OS << "S_Release"; + case S_MovableRelease: + return OS << "S_MovableRelease"; + case S_Stop: + return OS << "S_Stop"; + } + llvm_unreachable("Unknown sequence type."); +} + +//===----------------------------------------------------------------------===// +// Sequence +//===----------------------------------------------------------------------===// + +static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) { + // The easy cases. + if (A == B) + return A; + if (A == S_None || B == S_None) + return S_None; + + if (A > B) + std::swap(A, B); + if (TopDown) { + // Choose the side which is further along in the sequence. + if ((A == S_Retain || A == S_CanRelease) && + (B == S_CanRelease || B == S_Use)) + return B; + } else { + // Choose the side which is further along in the sequence. + if ((A == S_Use || A == S_CanRelease) && + (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease)) + return A; + // If both sides are releases, choose the more conservative one. + if (A == S_Stop && (B == S_Release || B == S_MovableRelease)) + return A; + if (A == S_Release && B == S_MovableRelease) + return A; + } + + return S_None; +} + +//===----------------------------------------------------------------------===// +// RRInfo +//===----------------------------------------------------------------------===// + +void RRInfo::clear() { + KnownSafe = false; + IsTailCallRelease = false; + ReleaseMetadata = nullptr; + Calls.clear(); + ReverseInsertPts.clear(); + CFGHazardAfflicted = false; +} + +bool RRInfo::Merge(const RRInfo &Other) { + // Conservatively merge the ReleaseMetadata information. + if (ReleaseMetadata != Other.ReleaseMetadata) + ReleaseMetadata = nullptr; + + // Conservatively merge the boolean state. + KnownSafe &= Other.KnownSafe; + IsTailCallRelease &= Other.IsTailCallRelease; + CFGHazardAfflicted |= Other.CFGHazardAfflicted; + + // Merge the call sets. + Calls.insert(Other.Calls.begin(), Other.Calls.end()); + + // Merge the insert point sets. If there are any differences, + // that makes this a partial merge. + bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size(); + for (Instruction *Inst : Other.ReverseInsertPts) + Partial |= ReverseInsertPts.insert(Inst).second; + return Partial; +} + +//===----------------------------------------------------------------------===// +// PtrState +//===----------------------------------------------------------------------===// + +void PtrState::SetKnownPositiveRefCount() { + DEBUG(dbgs() << " Setting Known Positive.\n"); + KnownPositiveRefCount = true; +} + +void PtrState::ClearKnownPositiveRefCount() { + DEBUG(dbgs() << " Clearing Known Positive.\n"); + KnownPositiveRefCount = false; +} + +void PtrState::SetSeq(Sequence NewSeq) { + DEBUG(dbgs() << " Old: " << GetSeq() << "; New: " << NewSeq << "\n"); + Seq = NewSeq; +} + +void PtrState::ResetSequenceProgress(Sequence NewSeq) { + DEBUG(dbgs() << " Resetting sequence progress.\n"); + SetSeq(NewSeq); + Partial = false; + RRI.clear(); +} + +void PtrState::Merge(const PtrState &Other, bool TopDown) { + Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown); + KnownPositiveRefCount &= Other.KnownPositiveRefCount; + + // If we're not in a sequence (anymore), drop all associated state. + if (Seq == S_None) { + Partial = false; + RRI.clear(); + } else if (Partial || Other.Partial) { + // If we're doing a merge on a path that's previously seen a partial + // merge, conservatively drop the sequence, to avoid doing partial + // RR elimination. If the branch predicates for the two merge differ, + // mixing them is unsafe. + ClearSequenceProgress(); + } else { + // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this + // point, we know that currently we are not partial. Stash whether or not + // the merge operation caused us to undergo a partial merging of reverse + // insertion points. + Partial = RRI.Merge(Other.RRI); + } +} + +//===----------------------------------------------------------------------===// +// BottomUpPtrState +//===----------------------------------------------------------------------===// + +bool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) { + // If we see two releases in a row on the same pointer. If so, make + // a note, and we'll cicle back to revisit it after we've + // hopefully eliminated the second release, which may allow us to + // eliminate the first release too. + // Theoretically we could implement removal of nested retain+release + // pairs by making PtrState hold a stack of states, but this is + // simple and avoids adding overhead for the non-nested case. + bool NestingDetected = false; + if (GetSeq() == S_Release || GetSeq() == S_MovableRelease) { + DEBUG(dbgs() << " Found nested releases (i.e. a release pair)\n"); + NestingDetected = true; + } + + MDNode *ReleaseMetadata = + I->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease)); + Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release; + ResetSequenceProgress(NewSeq); + SetReleaseMetadata(ReleaseMetadata); + SetKnownSafe(HasKnownPositiveRefCount()); + SetTailCallRelease(cast<CallInst>(I)->isTailCall()); + InsertCall(I); + SetKnownPositiveRefCount(); + return NestingDetected; +} + +bool BottomUpPtrState::MatchWithRetain() { + SetKnownPositiveRefCount(); + + Sequence OldSeq = GetSeq(); + switch (OldSeq) { + case S_Stop: + case S_Release: + case S_MovableRelease: + case S_Use: + // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an + // imprecise release, clear our reverse insertion points. + if (OldSeq != S_Use || IsTrackingImpreciseReleases()) + ClearReverseInsertPts(); + // FALL THROUGH + case S_CanRelease: + return true; + case S_None: + return false; + case S_Retain: + llvm_unreachable("bottom-up pointer in retain state!"); + } + llvm_unreachable("Sequence unknown enum value"); +} + +bool BottomUpPtrState::HandlePotentialAlterRefCount(Instruction *Inst, + const Value *Ptr, + ProvenanceAnalysis &PA, + ARCInstKind Class) { + Sequence S = GetSeq(); + + // Check for possible releases. + if (!CanAlterRefCount(Inst, Ptr, PA, Class)) + return false; + + DEBUG(dbgs() << " CanAlterRefCount: Seq: " << S << "; " << *Ptr + << "\n"); + switch (S) { + case S_Use: + SetSeq(S_CanRelease); + return true; + case S_CanRelease: + case S_Release: + case S_MovableRelease: + case S_Stop: + case S_None: + return false; + case S_Retain: + llvm_unreachable("bottom-up pointer in retain state!"); + } + llvm_unreachable("Sequence unknown enum value"); +} + +void BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst, + const Value *Ptr, + ProvenanceAnalysis &PA, + ARCInstKind Class) { + // Check for possible direct uses. + switch (GetSeq()) { + case S_Release: + case S_MovableRelease: + if (CanUse(Inst, Ptr, PA, Class)) { + DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr + << "\n"); + assert(!HasReverseInsertPts()); + // If this is an invoke instruction, we're scanning it as part of + // one of its successor blocks, since we can't insert code after it + // in its own block, and we don't want to split critical edges. + if (isa<InvokeInst>(Inst)) + InsertReverseInsertPt(BB->getFirstInsertionPt()); + else + InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst))); + SetSeq(S_Use); + } else if (Seq == S_Release && IsUser(Class)) { + DEBUG(dbgs() << " PreciseReleaseUse: Seq: " << GetSeq() << "; " + << *Ptr << "\n"); + // Non-movable releases depend on any possible objc pointer use. + SetSeq(S_Stop); + assert(!HasReverseInsertPts()); + // As above; handle invoke specially. + if (isa<InvokeInst>(Inst)) + InsertReverseInsertPt(BB->getFirstInsertionPt()); + else + InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst))); + } + break; + case S_Stop: + if (CanUse(Inst, Ptr, PA, Class)) { + DEBUG(dbgs() << " PreciseStopUse: Seq: " << GetSeq() << "; " + << *Ptr << "\n"); + SetSeq(S_Use); + } + break; + case S_CanRelease: + case S_Use: + case S_None: + break; + case S_Retain: + llvm_unreachable("bottom-up pointer in retain state!"); + } +} + +//===----------------------------------------------------------------------===// +// TopDownPtrState +//===----------------------------------------------------------------------===// + +bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) { + bool NestingDetected = false; + // Don't do retain+release tracking for ARCInstKind::RetainRV, because + // it's + // better to let it remain as the first instruction after a call. + if (Kind != ARCInstKind::RetainRV) { + // If we see two retains in a row on the same pointer. If so, make + // a note, and we'll cicle back to revisit it after we've + // hopefully eliminated the second retain, which may allow us to + // eliminate the first retain too. + // Theoretically we could implement removal of nested retain+release + // pairs by making PtrState hold a stack of states, but this is + // simple and avoids adding overhead for the non-nested case. + if (GetSeq() == S_Retain) + NestingDetected = true; + + ResetSequenceProgress(S_Retain); + SetKnownSafe(HasKnownPositiveRefCount()); + InsertCall(I); + } + + SetKnownPositiveRefCount(); + return NestingDetected; +} + +bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache, + Instruction *Release) { + ClearKnownPositiveRefCount(); + + Sequence OldSeq = GetSeq(); + + MDNode *ReleaseMetadata = + Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease)); + + switch (OldSeq) { + case S_Retain: + case S_CanRelease: + if (OldSeq == S_Retain || ReleaseMetadata != nullptr) + ClearReverseInsertPts(); + // FALL THROUGH + case S_Use: + SetReleaseMetadata(ReleaseMetadata); + SetTailCallRelease(cast<CallInst>(Release)->isTailCall()); + return true; + case S_None: + return false; + case S_Stop: + case S_Release: + case S_MovableRelease: + llvm_unreachable("top-down pointer in bottom up state!"); + } + llvm_unreachable("Sequence unknown enum value"); +} + +bool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst, + const Value *Ptr, + ProvenanceAnalysis &PA, + ARCInstKind Class) { + // Check for possible releases. + if (!CanAlterRefCount(Inst, Ptr, PA, Class)) + return false; + + DEBUG(dbgs() << " CanAlterRefCount: Seq: " << GetSeq() << "; " << *Ptr + << "\n"); + ClearKnownPositiveRefCount(); + switch (GetSeq()) { + case S_Retain: + SetSeq(S_CanRelease); + assert(!HasReverseInsertPts()); + InsertReverseInsertPt(Inst); + + // One call can't cause a transition from S_Retain to S_CanRelease + // and S_CanRelease to S_Use. If we've made the first transition, + // we're done. + return true; + case S_Use: + case S_CanRelease: + case S_None: + return false; + case S_Stop: + case S_Release: + case S_MovableRelease: + llvm_unreachable("top-down pointer in release state!"); + } + llvm_unreachable("covered switch is not covered!?"); +} + +void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, + ARCInstKind Class) { + // Check for possible direct uses. + switch (GetSeq()) { + case S_CanRelease: + if (!CanUse(Inst, Ptr, PA, Class)) + return; + DEBUG(dbgs() << " CanUse: Seq: " << GetSeq() << "; " << *Ptr + << "\n"); + SetSeq(S_Use); + return; + case S_Retain: + case S_Use: + case S_None: + return; + case S_Stop: + case S_Release: + case S_MovableRelease: + llvm_unreachable("top-down pointer in release state!"); + } +} diff --git a/contrib/llvm/lib/Transforms/ObjCARC/PtrState.h b/contrib/llvm/lib/Transforms/ObjCARC/PtrState.h new file mode 100644 index 0000000..e45e1ea --- /dev/null +++ b/contrib/llvm/lib/Transforms/ObjCARC/PtrState.h @@ -0,0 +1,210 @@ +//===--- PtrState.h - ARC State for a Ptr -------------------*- C++ -*-----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains declarations for the ARC state associated with a ptr. It +// is only used by the ARC Sequence Dataflow computation. By separating this +// from the actual dataflow, it is easier to consider the mechanics of the ARC +// optimization separate from the actual predicates being used. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_TRANSFORMS_OBJCARC_PTRSTATE_H +#define LLVM_LIB_TRANSFORMS_OBJCARC_PTRSTATE_H + +#include "ARCInstKind.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Value.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/Debug.h" + +namespace llvm { +namespace objcarc { + +class ARCMDKindCache; +class ProvenanceAnalysis; + +/// \enum Sequence +/// +/// \brief A sequence of states that a pointer may go through in which an +/// objc_retain and objc_release are actually needed. +enum Sequence { + S_None, + S_Retain, ///< objc_retain(x). + S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement. + S_Use, ///< any use of x. + S_Stop, ///< like S_Release, but code motion is stopped. + S_Release, ///< objc_release(x). + S_MovableRelease ///< objc_release(x), !clang.imprecise_release. +}; + +raw_ostream &operator<<(raw_ostream &OS, + const Sequence S) LLVM_ATTRIBUTE_UNUSED; + +/// \brief Unidirectional information about either a +/// retain-decrement-use-release sequence or release-use-decrement-retain +/// reverse sequence. +struct RRInfo { + /// After an objc_retain, the reference count of the referenced + /// object is known to be positive. Similarly, before an objc_release, the + /// reference count of the referenced object is known to be positive. If + /// there are retain-release pairs in code regions where the retain count + /// is known to be positive, they can be eliminated, regardless of any side + /// effects between them. + /// + /// Also, a retain+release pair nested within another retain+release + /// pair all on the known same pointer value can be eliminated, regardless + /// of any intervening side effects. + /// + /// KnownSafe is true when either of these conditions is satisfied. + bool KnownSafe; + + /// True of the objc_release calls are all marked with the "tail" keyword. + bool IsTailCallRelease; + + /// If the Calls are objc_release calls and they all have a + /// clang.imprecise_release tag, this is the metadata tag. + MDNode *ReleaseMetadata; + + /// For a top-down sequence, the set of objc_retains or + /// objc_retainBlocks. For bottom-up, the set of objc_releases. + SmallPtrSet<Instruction *, 2> Calls; + + /// The set of optimal insert positions for moving calls in the opposite + /// sequence. + SmallPtrSet<Instruction *, 2> ReverseInsertPts; + + /// If this is true, we cannot perform code motion but can still remove + /// retain/release pairs. + bool CFGHazardAfflicted; + + RRInfo() + : KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(nullptr), + CFGHazardAfflicted(false) {} + + void clear(); + + /// Conservatively merge the two RRInfo. Returns true if a partial merge has + /// occurred, false otherwise. + bool Merge(const RRInfo &Other); +}; + +/// \brief This class summarizes several per-pointer runtime properties which +/// are propogated through the flow graph. +class PtrState { +protected: + /// True if the reference count is known to be incremented. + bool KnownPositiveRefCount; + + /// True if we've seen an opportunity for partial RR elimination, such as + /// pushing calls into a CFG triangle or into one side of a CFG diamond. + bool Partial; + + /// The current position in the sequence. + unsigned char Seq : 8; + + /// Unidirectional information about the current sequence. + RRInfo RRI; + + PtrState() : KnownPositiveRefCount(false), Partial(false), Seq(S_None) {} + +public: + bool IsKnownSafe() const { return RRI.KnownSafe; } + + void SetKnownSafe(const bool NewValue) { RRI.KnownSafe = NewValue; } + + bool IsTailCallRelease() const { return RRI.IsTailCallRelease; } + + void SetTailCallRelease(const bool NewValue) { + RRI.IsTailCallRelease = NewValue; + } + + bool IsTrackingImpreciseReleases() const { + return RRI.ReleaseMetadata != nullptr; + } + + const MDNode *GetReleaseMetadata() const { return RRI.ReleaseMetadata; } + + void SetReleaseMetadata(MDNode *NewValue) { RRI.ReleaseMetadata = NewValue; } + + bool IsCFGHazardAfflicted() const { return RRI.CFGHazardAfflicted; } + + void SetCFGHazardAfflicted(const bool NewValue) { + RRI.CFGHazardAfflicted = NewValue; + } + + void SetKnownPositiveRefCount(); + void ClearKnownPositiveRefCount(); + + bool HasKnownPositiveRefCount() const { return KnownPositiveRefCount; } + + void SetSeq(Sequence NewSeq); + + Sequence GetSeq() const { return static_cast<Sequence>(Seq); } + + void ClearSequenceProgress() { ResetSequenceProgress(S_None); } + + void ResetSequenceProgress(Sequence NewSeq); + void Merge(const PtrState &Other, bool TopDown); + + void InsertCall(Instruction *I) { RRI.Calls.insert(I); } + + void InsertReverseInsertPt(Instruction *I) { RRI.ReverseInsertPts.insert(I); } + + void ClearReverseInsertPts() { RRI.ReverseInsertPts.clear(); } + + bool HasReverseInsertPts() const { return !RRI.ReverseInsertPts.empty(); } + + const RRInfo &GetRRInfo() const { return RRI; } +}; + +struct BottomUpPtrState : PtrState { + BottomUpPtrState() : PtrState() {} + + /// (Re-)Initialize this bottom up pointer returning true if we detected a + /// pointer with nested releases. + bool InitBottomUp(ARCMDKindCache &Cache, Instruction *I); + + /// Return true if this set of releases can be paired with a release. Modifies + /// state appropriately to reflect that the matching occured if it is + /// successful. + /// + /// It is assumed that one has already checked that the RCIdentity of the + /// retain and the RCIdentity of this ptr state are the same. + bool MatchWithRetain(); + + void HandlePotentialUse(BasicBlock *BB, Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, ARCInstKind Class); + bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, ARCInstKind Class); +}; + +struct TopDownPtrState : PtrState { + TopDownPtrState() : PtrState() {} + + /// (Re-)Initialize this bottom up pointer returning true if we detected a + /// pointer with nested releases. + bool InitTopDown(ARCInstKind Kind, Instruction *I); + + /// Return true if this set of retains can be paired with the given + /// release. Modifies state appropriately to reflect that the matching + /// occured. + bool MatchWithRelease(ARCMDKindCache &Cache, Instruction *Release); + + void HandlePotentialUse(Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, ARCInstKind Class); + + bool HandlePotentialAlterRefCount(Instruction *Inst, const Value *Ptr, + ProvenanceAnalysis &PA, ARCInstKind Class); +}; + +} // end namespace objcarc +} // end namespace llvm + +#endif |
