1023d2bbbbedc6ed991b11381a987673133be2c81Michael Gottesman//===- ObjCARCAliasAnalysis.cpp - ObjC ARC Optimization -------------------===// 26086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman// 36086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman// The LLVM Compiler Infrastructure 46086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman// 56086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman// This file is distributed under the University of Illinois Open Source 66086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman// License. See LICENSE.TXT for details. 76086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman// 86086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman//===----------------------------------------------------------------------===// 96086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// \file 106086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// This file defines a simple ARC-aware AliasAnalysis using special knowledge 116086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// of Objective C to enhance other optimization passes which rely on the Alias 126086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// Analysis infrastructure. 136086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// 146086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// WARNING: This file knows about certain library functions. It recognizes them 156086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// by name, and hardwires knowledge of their semantics. 166086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// 176086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// WARNING: This file knows about how certain Objective-C library functions are 186086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// used. Naive LLVM IR transformations which would otherwise be 196086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// behavior-preserving may break these assumptions. 206086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman/// 21f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// TODO: Theoretically we could check for dependencies between objc_* calls 22f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// and FMRB_OnlyAccessesArgumentPointees calls or other well-behaved calls. 23f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// 246086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman//===----------------------------------------------------------------------===// 256086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 26f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Analysis/ObjCARCAliasAnalysis.h" 27f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Analysis/ObjCARCAnalysisUtils.h" 28f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/IR/Function.h" 296086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman#include "llvm/IR/Instruction.h" 30f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/IR/Value.h" 316086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman#include "llvm/InitializePasses.h" 326086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman#include "llvm/PassAnalysisSupport.h" 336086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman#include "llvm/PassSupport.h" 346086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "objc-arc-aa" 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 376086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesmanusing namespace llvm; 386086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesmanusing namespace llvm::objcarc; 396086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 40f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarAliasResult ObjCARCAAResult::alias(const MemoryLocation &LocA, 41f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MemoryLocation &LocB) { 426086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman if (!EnableARCOpts) 43f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AAResultBase::alias(LocA, LocB); 446086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 456086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // First, strip off no-ops, including ObjC-specific no-ops, and try making a 466086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // precise alias query. 47ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const Value *SA = GetRCIdentityRoot(LocA.Ptr); 48ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const Value *SB = GetRCIdentityRoot(LocB.Ptr); 496086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman AliasResult Result = 50f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AAResultBase::alias(MemoryLocation(SA, LocA.Size, LocA.AATags), 51f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MemoryLocation(SB, LocB.Size, LocB.AATags)); 526086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman if (Result != MayAlias) 536086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman return Result; 546086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 556086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // If that failed, climb to the underlying object, including climbing through 566086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // ObjC-specific no-ops, and try making an imprecise alias query. 57f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const Value *UA = GetUnderlyingObjCPtr(SA, DL); 58f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const Value *UB = GetUnderlyingObjCPtr(SB, DL); 596086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman if (UA != SA || UB != SB) { 60f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Result = AAResultBase::alias(MemoryLocation(UA), MemoryLocation(UB)); 616086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // We can't use MustAlias or PartialAlias results here because 626086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // GetUnderlyingObjCPtr may return an offsetted pointer value. 636086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman if (Result == NoAlias) 646086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman return NoAlias; 656086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman } 666086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 676086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // If that failed, fail. We don't need to chain here, since that's covered 686086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // by the earlier precise query. 696086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman return MayAlias; 706086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman} 716086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 72f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool ObjCARCAAResult::pointsToConstantMemory(const MemoryLocation &Loc, 736086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman bool OrLocal) { 746086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman if (!EnableARCOpts) 75f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AAResultBase::pointsToConstantMemory(Loc, OrLocal); 766086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 776086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // First, strip off no-ops, including ObjC-specific no-ops, and try making 786086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // a precise alias query. 79ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const Value *S = GetRCIdentityRoot(Loc.Ptr); 80f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (AAResultBase::pointsToConstantMemory( 81f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MemoryLocation(S, Loc.Size, Loc.AATags), OrLocal)) 826086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman return true; 836086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 846086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // If that failed, climb to the underlying object, including climbing through 856086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // ObjC-specific no-ops, and try making an imprecise alias query. 86f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const Value *U = GetUnderlyingObjCPtr(S, DL); 876086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman if (U != S) 88f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AAResultBase::pointsToConstantMemory(MemoryLocation(U), OrLocal); 896086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 906086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // If that failed, fail. We don't need to chain here, since that's covered 916086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // by the earlier precise query. 926086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman return false; 936086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman} 946086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 95f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarFunctionModRefBehavior ObjCARCAAResult::getModRefBehavior(const Function *F) { 966086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman if (!EnableARCOpts) 97f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AAResultBase::getModRefBehavior(F); 986086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 996086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman switch (GetFunctionClass(F)) { 100ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::NoopCast: 101f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return FMRB_DoesNotAccessMemory; 1026086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman default: 1036086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman break; 1046086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman } 1056086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 106f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AAResultBase::getModRefBehavior(F); 1076086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman} 1086086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 109f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarModRefInfo ObjCARCAAResult::getModRefInfo(ImmutableCallSite CS, 110f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const MemoryLocation &Loc) { 1116086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman if (!EnableARCOpts) 112f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AAResultBase::getModRefInfo(CS, Loc); 1136086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 114ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines switch (GetBasicARCInstKind(CS.getInstruction())) { 115ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::Retain: 116ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::RetainRV: 117ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::Autorelease: 118ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::AutoreleaseRV: 119ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::NoopCast: 120ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::AutoreleasepoolPush: 121ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::FusedRetainAutorelease: 122ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case ARCInstKind::FusedRetainAutoreleaseRV: 1236086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // These functions don't access any memory visible to the compiler. 1246086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // Note that this doesn't include objc_retainBlock, because it updates 1256086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman // pointers when it copies block data. 126f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return MRI_NoModRef; 1276086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman default: 1286086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman break; 1296086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman } 1306086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 131f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return AAResultBase::getModRefInfo(CS, Loc); 132f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 133f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 134de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarObjCARCAAResult ObjCARCAA::run(Function &F, AnalysisManager<Function> &AM) { 135de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return ObjCARCAAResult(F.getParent()->getDataLayout()); 136f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 137f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 138f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarchar ObjCARCAAWrapperPass::ID = 0; 139de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS(ObjCARCAAWrapperPass, "objc-arc-aa", 140de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "ObjC-ARC-Based Alias Analysis", false, true) 141f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 142f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarImmutablePass *llvm::createObjCARCAAWrapperPass() { 143f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return new ObjCARCAAWrapperPass(); 144f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 145f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 146f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarObjCARCAAWrapperPass::ObjCARCAAWrapperPass() : ImmutablePass(ID) { 147f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar initializeObjCARCAAWrapperPassPass(*PassRegistry::getPassRegistry()); 1486086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman} 1496086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman 150f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool ObjCARCAAWrapperPass::doInitialization(Module &M) { 151de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Result.reset(new ObjCARCAAResult(M.getDataLayout())); 152f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 153f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 154f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 155f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarbool ObjCARCAAWrapperPass::doFinalization(Module &M) { 156f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Result.reset(); 157f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 158f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 159f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 160f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid ObjCARCAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 161f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.setPreservesAll(); 1626086847bfbc538b99305b4d7e0a53ab610f6a9bbMichael Gottesman} 163