1 //===- ObjCARCContract.cpp - ObjC ARC Optimization ------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 /// This file defines late ObjC ARC optimizations. ARC stands for Automatic
10 /// Reference Counting and is a system for managing reference counts for objects
11 /// in Objective C.
12 ///
13 /// This specific file mainly deals with ``contracting'' multiple lower level
14 /// operations into singular higher level operations through pattern matching.
15 ///
16 /// WARNING: This file knows about certain library functions. It recognizes them
17 /// by name, and hardwires knowledge of their semantics.
18 ///
19 /// WARNING: This file knows about how certain Objective-C library functions are
20 /// used. Naive LLVM IR transformations which would otherwise be
21 /// behavior-preserving may break these assumptions.
22 ///
23 //===----------------------------------------------------------------------===//
24
25 // TODO: ObjCARCContract could insert PHI nodes when uses aren't
26 // dominated by single calls.
27
28 #include "ARCRuntimeEntryPoints.h"
29 #include "DependencyAnalysis.h"
30 #include "ObjCARC.h"
31 #include "ProvenanceAnalysis.h"
32 #include "llvm/ADT/Statistic.h"
33 #include "llvm/Analysis/EHPersonalities.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/InlineAsm.h"
36 #include "llvm/IR/InstIterator.h"
37 #include "llvm/IR/Operator.h"
38 #include "llvm/IR/PassManager.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include "llvm/Transforms/ObjCARC.h"
44
45 using namespace llvm;
46 using namespace llvm::objcarc;
47
48 #define DEBUG_TYPE "objc-arc-contract"
49
50 STATISTIC(NumPeeps, "Number of calls peephole-optimized");
51 STATISTIC(NumStoreStrongs, "Number objc_storeStrong calls formed");
52
53 //===----------------------------------------------------------------------===//
54 // Declarations
55 //===----------------------------------------------------------------------===//
56
57 namespace {
58 /// Late ARC optimizations
59 ///
60 /// These change the IR in a way that makes it difficult to be analyzed by
61 /// ObjCARCOpt, so it's run late.
62
63 class ObjCARCContract {
64 bool Changed;
65 AliasAnalysis *AA;
66 DominatorTree *DT;
67 ProvenanceAnalysis PA;
68 ARCRuntimeEntryPoints EP;
69
70 /// A flag indicating whether this optimization pass should run.
71 bool Run;
72
73 /// The inline asm string to insert between calls and RetainRV calls to make
74 /// the optimization work on targets which need it.
75 const MDString *RVInstMarker;
76
77 /// The set of inserted objc_storeStrong calls. If at the end of walking the
78 /// function we have found no alloca instructions, these calls can be marked
79 /// "tail".
80 SmallPtrSet<CallInst *, 8> StoreStrongCalls;
81
82 /// Returns true if we eliminated Inst.
83 bool tryToPeepholeInstruction(
84 Function &F, Instruction *Inst, inst_iterator &Iter,
85 SmallPtrSetImpl<Instruction *> &DepInsts,
86 SmallPtrSetImpl<const BasicBlock *> &Visited, bool &TailOkForStoreStrong,
87 const DenseMap<BasicBlock *, ColorVector> &BlockColors);
88
89 bool optimizeRetainCall(Function &F, Instruction *Retain);
90
91 bool
92 contractAutorelease(Function &F, Instruction *Autorelease, ARCInstKind Class,
93 SmallPtrSetImpl<Instruction *> &DependingInstructions,
94 SmallPtrSetImpl<const BasicBlock *> &Visited);
95
96 void tryToContractReleaseIntoStoreStrong(
97 Instruction *Release, inst_iterator &Iter,
98 const DenseMap<BasicBlock *, ColorVector> &BlockColors);
99
100 public:
101 bool init(Module &M);
102 bool run(Function &F, AAResults *AA, DominatorTree *DT);
103 };
104
105 class ObjCARCContractLegacyPass : public FunctionPass {
106 ObjCARCContract OCARCC;
107
108 public:
109 void getAnalysisUsage(AnalysisUsage &AU) const override;
110 bool doInitialization(Module &M) override;
111 bool runOnFunction(Function &F) override;
112
113 static char ID;
ObjCARCContractLegacyPass()114 ObjCARCContractLegacyPass() : FunctionPass(ID) {
115 initializeObjCARCContractLegacyPassPass(*PassRegistry::getPassRegistry());
116 }
117 };
118 }
119
120 //===----------------------------------------------------------------------===//
121 // Implementation
122 //===----------------------------------------------------------------------===//
123
124 /// Turn objc_retain into objc_retainAutoreleasedReturnValue if the operand is a
125 /// return value. We do this late so we do not disrupt the dataflow analysis in
126 /// ObjCARCOpt.
optimizeRetainCall(Function & F,Instruction * Retain)127 bool ObjCARCContract::optimizeRetainCall(Function &F, Instruction *Retain) {
128 const auto *Call = dyn_cast<CallBase>(GetArgRCIdentityRoot(Retain));
129 if (!Call)
130 return false;
131 if (Call->getParent() != Retain->getParent())
132 return false;
133
134 // Check that the call is next to the retain.
135 BasicBlock::const_iterator I = ++Call->getIterator();
136 while (IsNoopInstruction(&*I))
137 ++I;
138 if (&*I != Retain)
139 return false;
140
141 // Turn it to an objc_retainAutoreleasedReturnValue.
142 Changed = true;
143 ++NumPeeps;
144
145 LLVM_DEBUG(
146 dbgs() << "Transforming objc_retain => "
147 "objc_retainAutoreleasedReturnValue since the operand is a "
148 "return value.\nOld: "
149 << *Retain << "\n");
150
151 // We do not have to worry about tail calls/does not throw since
152 // retain/retainRV have the same properties.
153 Function *Decl = EP.get(ARCRuntimeEntryPointKind::RetainRV);
154 cast<CallInst>(Retain)->setCalledFunction(Decl);
155
156 LLVM_DEBUG(dbgs() << "New: " << *Retain << "\n");
157 return true;
158 }
159
160 /// Merge an autorelease with a retain into a fused call.
contractAutorelease(Function & F,Instruction * Autorelease,ARCInstKind Class,SmallPtrSetImpl<Instruction * > & DependingInstructions,SmallPtrSetImpl<const BasicBlock * > & Visited)161 bool ObjCARCContract::contractAutorelease(
162 Function &F, Instruction *Autorelease, ARCInstKind Class,
163 SmallPtrSetImpl<Instruction *> &DependingInstructions,
164 SmallPtrSetImpl<const BasicBlock *> &Visited) {
165 const Value *Arg = GetArgRCIdentityRoot(Autorelease);
166
167 // Check that there are no instructions between the retain and the autorelease
168 // (such as an autorelease_pop) which may change the count.
169 CallInst *Retain = nullptr;
170 if (Class == ARCInstKind::AutoreleaseRV)
171 FindDependencies(RetainAutoreleaseRVDep, Arg,
172 Autorelease->getParent(), Autorelease,
173 DependingInstructions, Visited, PA);
174 else
175 FindDependencies(RetainAutoreleaseDep, Arg,
176 Autorelease->getParent(), Autorelease,
177 DependingInstructions, Visited, PA);
178
179 Visited.clear();
180 if (DependingInstructions.size() != 1) {
181 DependingInstructions.clear();
182 return false;
183 }
184
185 Retain = dyn_cast_or_null<CallInst>(*DependingInstructions.begin());
186 DependingInstructions.clear();
187
188 if (!Retain || GetBasicARCInstKind(Retain) != ARCInstKind::Retain ||
189 GetArgRCIdentityRoot(Retain) != Arg)
190 return false;
191
192 Changed = true;
193 ++NumPeeps;
194
195 LLVM_DEBUG(dbgs() << " Fusing retain/autorelease!\n"
196 " Autorelease:"
197 << *Autorelease
198 << "\n"
199 " Retain: "
200 << *Retain << "\n");
201
202 Function *Decl = EP.get(Class == ARCInstKind::AutoreleaseRV
203 ? ARCRuntimeEntryPointKind::RetainAutoreleaseRV
204 : ARCRuntimeEntryPointKind::RetainAutorelease);
205 Retain->setCalledFunction(Decl);
206
207 LLVM_DEBUG(dbgs() << " New RetainAutorelease: " << *Retain << "\n");
208
209 EraseInstruction(Autorelease);
210 return true;
211 }
212
findSafeStoreForStoreStrongContraction(LoadInst * Load,Instruction * Release,ProvenanceAnalysis & PA,AliasAnalysis * AA)213 static StoreInst *findSafeStoreForStoreStrongContraction(LoadInst *Load,
214 Instruction *Release,
215 ProvenanceAnalysis &PA,
216 AliasAnalysis *AA) {
217 StoreInst *Store = nullptr;
218 bool SawRelease = false;
219
220 // Get the location associated with Load.
221 MemoryLocation Loc = MemoryLocation::get(Load);
222 auto *LocPtr = Loc.Ptr->stripPointerCasts();
223
224 // Walk down to find the store and the release, which may be in either order.
225 for (auto I = std::next(BasicBlock::iterator(Load)),
226 E = Load->getParent()->end();
227 I != E; ++I) {
228 // If we found the store we were looking for and saw the release,
229 // break. There is no more work to be done.
230 if (Store && SawRelease)
231 break;
232
233 // Now we know that we have not seen either the store or the release. If I
234 // is the release, mark that we saw the release and continue.
235 Instruction *Inst = &*I;
236 if (Inst == Release) {
237 SawRelease = true;
238 continue;
239 }
240
241 // Otherwise, we check if Inst is a "good" store. Grab the instruction class
242 // of Inst.
243 ARCInstKind Class = GetBasicARCInstKind(Inst);
244
245 // If Inst is an unrelated retain, we don't care about it.
246 //
247 // TODO: This is one area where the optimization could be made more
248 // aggressive.
249 if (IsRetain(Class))
250 continue;
251
252 // If we have seen the store, but not the release...
253 if (Store) {
254 // We need to make sure that it is safe to move the release from its
255 // current position to the store. This implies proving that any
256 // instruction in between Store and the Release conservatively can not use
257 // the RCIdentityRoot of Release. If we can prove we can ignore Inst, so
258 // continue...
259 if (!CanUse(Inst, Load, PA, Class)) {
260 continue;
261 }
262
263 // Otherwise, be conservative and return nullptr.
264 return nullptr;
265 }
266
267 // Ok, now we know we have not seen a store yet. See if Inst can write to
268 // our load location, if it can not, just ignore the instruction.
269 if (!isModSet(AA->getModRefInfo(Inst, Loc)))
270 continue;
271
272 Store = dyn_cast<StoreInst>(Inst);
273
274 // If Inst can, then check if Inst is a simple store. If Inst is not a
275 // store or a store that is not simple, then we have some we do not
276 // understand writing to this memory implying we can not move the load
277 // over the write to any subsequent store that we may find.
278 if (!Store || !Store->isSimple())
279 return nullptr;
280
281 // Then make sure that the pointer we are storing to is Ptr. If so, we
282 // found our Store!
283 if (Store->getPointerOperand()->stripPointerCasts() == LocPtr)
284 continue;
285
286 // Otherwise, we have an unknown store to some other ptr that clobbers
287 // Loc.Ptr. Bail!
288 return nullptr;
289 }
290
291 // If we did not find the store or did not see the release, fail.
292 if (!Store || !SawRelease)
293 return nullptr;
294
295 // We succeeded!
296 return Store;
297 }
298
299 static Instruction *
findRetainForStoreStrongContraction(Value * New,StoreInst * Store,Instruction * Release,ProvenanceAnalysis & PA)300 findRetainForStoreStrongContraction(Value *New, StoreInst *Store,
301 Instruction *Release,
302 ProvenanceAnalysis &PA) {
303 // Walk up from the Store to find the retain.
304 BasicBlock::iterator I = Store->getIterator();
305 BasicBlock::iterator Begin = Store->getParent()->begin();
306 while (I != Begin && GetBasicARCInstKind(&*I) != ARCInstKind::Retain) {
307 Instruction *Inst = &*I;
308
309 // It is only safe to move the retain to the store if we can prove
310 // conservatively that nothing besides the release can decrement reference
311 // counts in between the retain and the store.
312 if (CanDecrementRefCount(Inst, New, PA) && Inst != Release)
313 return nullptr;
314 --I;
315 }
316 Instruction *Retain = &*I;
317 if (GetBasicARCInstKind(Retain) != ARCInstKind::Retain)
318 return nullptr;
319 if (GetArgRCIdentityRoot(Retain) != New)
320 return nullptr;
321 return Retain;
322 }
323
324 /// Create a call instruction with the correct funclet token. Should be used
325 /// instead of calling CallInst::Create directly.
326 static CallInst *
createCallInst(FunctionType * FTy,Value * Func,ArrayRef<Value * > Args,const Twine & NameStr,Instruction * InsertBefore,const DenseMap<BasicBlock *,ColorVector> & BlockColors)327 createCallInst(FunctionType *FTy, Value *Func, ArrayRef<Value *> Args,
328 const Twine &NameStr, Instruction *InsertBefore,
329 const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
330 SmallVector<OperandBundleDef, 1> OpBundles;
331 if (!BlockColors.empty()) {
332 const ColorVector &CV = BlockColors.find(InsertBefore->getParent())->second;
333 assert(CV.size() == 1 && "non-unique color for block!");
334 Instruction *EHPad = CV.front()->getFirstNonPHI();
335 if (EHPad->isEHPad())
336 OpBundles.emplace_back("funclet", EHPad);
337 }
338
339 return CallInst::Create(FTy, Func, Args, OpBundles, NameStr, InsertBefore);
340 }
341
342 static CallInst *
createCallInst(FunctionCallee Func,ArrayRef<Value * > Args,const Twine & NameStr,Instruction * InsertBefore,const DenseMap<BasicBlock *,ColorVector> & BlockColors)343 createCallInst(FunctionCallee Func, ArrayRef<Value *> Args, const Twine &NameStr,
344 Instruction *InsertBefore,
345 const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
346 return createCallInst(Func.getFunctionType(), Func.getCallee(), Args, NameStr,
347 InsertBefore, BlockColors);
348 }
349
350 /// Attempt to merge an objc_release with a store, load, and objc_retain to form
351 /// an objc_storeStrong. An objc_storeStrong:
352 ///
353 /// objc_storeStrong(i8** %old_ptr, i8* new_value)
354 ///
355 /// is equivalent to the following IR sequence:
356 ///
357 /// ; Load old value.
358 /// %old_value = load i8** %old_ptr (1)
359 ///
360 /// ; Increment the new value and then release the old value. This must occur
361 /// ; in order in case old_value releases new_value in its destructor causing
362 /// ; us to potentially have a dangling ptr.
363 /// tail call i8* @objc_retain(i8* %new_value) (2)
364 /// tail call void @objc_release(i8* %old_value) (3)
365 ///
366 /// ; Store the new_value into old_ptr
367 /// store i8* %new_value, i8** %old_ptr (4)
368 ///
369 /// The safety of this optimization is based around the following
370 /// considerations:
371 ///
372 /// 1. We are forming the store strong at the store. Thus to perform this
373 /// optimization it must be safe to move the retain, load, and release to
374 /// (4).
375 /// 2. We need to make sure that any re-orderings of (1), (2), (3), (4) are
376 /// safe.
tryToContractReleaseIntoStoreStrong(Instruction * Release,inst_iterator & Iter,const DenseMap<BasicBlock *,ColorVector> & BlockColors)377 void ObjCARCContract::tryToContractReleaseIntoStoreStrong(
378 Instruction *Release, inst_iterator &Iter,
379 const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
380 // See if we are releasing something that we just loaded.
381 auto *Load = dyn_cast<LoadInst>(GetArgRCIdentityRoot(Release));
382 if (!Load || !Load->isSimple())
383 return;
384
385 // For now, require everything to be in one basic block.
386 BasicBlock *BB = Release->getParent();
387 if (Load->getParent() != BB)
388 return;
389
390 // First scan down the BB from Load, looking for a store of the RCIdentityRoot
391 // of Load's
392 StoreInst *Store =
393 findSafeStoreForStoreStrongContraction(Load, Release, PA, AA);
394 // If we fail, bail.
395 if (!Store)
396 return;
397
398 // Then find what new_value's RCIdentity Root is.
399 Value *New = GetRCIdentityRoot(Store->getValueOperand());
400
401 // Then walk up the BB and look for a retain on New without any intervening
402 // instructions which conservatively might decrement ref counts.
403 Instruction *Retain =
404 findRetainForStoreStrongContraction(New, Store, Release, PA);
405
406 // If we fail, bail.
407 if (!Retain)
408 return;
409
410 Changed = true;
411 ++NumStoreStrongs;
412
413 LLVM_DEBUG(
414 llvm::dbgs() << " Contracting retain, release into objc_storeStrong.\n"
415 << " Old:\n"
416 << " Store: " << *Store << "\n"
417 << " Release: " << *Release << "\n"
418 << " Retain: " << *Retain << "\n"
419 << " Load: " << *Load << "\n");
420
421 LLVMContext &C = Release->getContext();
422 Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C));
423 Type *I8XX = PointerType::getUnqual(I8X);
424
425 Value *Args[] = { Load->getPointerOperand(), New };
426 if (Args[0]->getType() != I8XX)
427 Args[0] = new BitCastInst(Args[0], I8XX, "", Store);
428 if (Args[1]->getType() != I8X)
429 Args[1] = new BitCastInst(Args[1], I8X, "", Store);
430 Function *Decl = EP.get(ARCRuntimeEntryPointKind::StoreStrong);
431 CallInst *StoreStrong = createCallInst(Decl, Args, "", Store, BlockColors);
432 StoreStrong->setDoesNotThrow();
433 StoreStrong->setDebugLoc(Store->getDebugLoc());
434
435 // We can't set the tail flag yet, because we haven't yet determined
436 // whether there are any escaping allocas. Remember this call, so that
437 // we can set the tail flag once we know it's safe.
438 StoreStrongCalls.insert(StoreStrong);
439
440 LLVM_DEBUG(llvm::dbgs() << " New Store Strong: " << *StoreStrong
441 << "\n");
442
443 if (&*Iter == Retain) ++Iter;
444 if (&*Iter == Store) ++Iter;
445 Store->eraseFromParent();
446 Release->eraseFromParent();
447 EraseInstruction(Retain);
448 if (Load->use_empty())
449 Load->eraseFromParent();
450 }
451
tryToPeepholeInstruction(Function & F,Instruction * Inst,inst_iterator & Iter,SmallPtrSetImpl<Instruction * > & DependingInsts,SmallPtrSetImpl<const BasicBlock * > & Visited,bool & TailOkForStoreStrongs,const DenseMap<BasicBlock *,ColorVector> & BlockColors)452 bool ObjCARCContract::tryToPeepholeInstruction(
453 Function &F, Instruction *Inst, inst_iterator &Iter,
454 SmallPtrSetImpl<Instruction *> &DependingInsts,
455 SmallPtrSetImpl<const BasicBlock *> &Visited, bool &TailOkForStoreStrongs,
456 const DenseMap<BasicBlock *, ColorVector> &BlockColors) {
457 // Only these library routines return their argument. In particular,
458 // objc_retainBlock does not necessarily return its argument.
459 ARCInstKind Class = GetBasicARCInstKind(Inst);
460 switch (Class) {
461 case ARCInstKind::FusedRetainAutorelease:
462 case ARCInstKind::FusedRetainAutoreleaseRV:
463 return false;
464 case ARCInstKind::Autorelease:
465 case ARCInstKind::AutoreleaseRV:
466 return contractAutorelease(F, Inst, Class, DependingInsts, Visited);
467 case ARCInstKind::Retain:
468 // Attempt to convert retains to retainrvs if they are next to function
469 // calls.
470 if (!optimizeRetainCall(F, Inst))
471 return false;
472 // If we succeed in our optimization, fall through.
473 LLVM_FALLTHROUGH;
474 case ARCInstKind::RetainRV:
475 case ARCInstKind::ClaimRV: {
476 // If we're compiling for a target which needs a special inline-asm
477 // marker to do the return value optimization, insert it now.
478 if (!RVInstMarker)
479 return false;
480 BasicBlock::iterator BBI = Inst->getIterator();
481 BasicBlock *InstParent = Inst->getParent();
482
483 // Step up to see if the call immediately precedes the RV call.
484 // If it's an invoke, we have to cross a block boundary. And we have
485 // to carefully dodge no-op instructions.
486 do {
487 if (BBI == InstParent->begin()) {
488 BasicBlock *Pred = InstParent->getSinglePredecessor();
489 if (!Pred)
490 goto decline_rv_optimization;
491 BBI = Pred->getTerminator()->getIterator();
492 break;
493 }
494 --BBI;
495 } while (IsNoopInstruction(&*BBI));
496
497 if (&*BBI == GetArgRCIdentityRoot(Inst)) {
498 LLVM_DEBUG(dbgs() << "Adding inline asm marker for the return value "
499 "optimization.\n");
500 Changed = true;
501 InlineAsm *IA =
502 InlineAsm::get(FunctionType::get(Type::getVoidTy(Inst->getContext()),
503 /*isVarArg=*/false),
504 RVInstMarker->getString(),
505 /*Constraints=*/"", /*hasSideEffects=*/true);
506
507 createCallInst(IA, None, "", Inst, BlockColors);
508 }
509 decline_rv_optimization:
510 return false;
511 }
512 case ARCInstKind::InitWeak: {
513 // objc_initWeak(p, null) => *p = null
514 CallInst *CI = cast<CallInst>(Inst);
515 if (IsNullOrUndef(CI->getArgOperand(1))) {
516 Value *Null = ConstantPointerNull::get(cast<PointerType>(CI->getType()));
517 Changed = true;
518 new StoreInst(Null, CI->getArgOperand(0), CI);
519
520 LLVM_DEBUG(dbgs() << "OBJCARCContract: Old = " << *CI << "\n"
521 << " New = " << *Null << "\n");
522
523 CI->replaceAllUsesWith(Null);
524 CI->eraseFromParent();
525 }
526 return true;
527 }
528 case ARCInstKind::Release:
529 // Try to form an objc store strong from our release. If we fail, there is
530 // nothing further to do below, so continue.
531 tryToContractReleaseIntoStoreStrong(Inst, Iter, BlockColors);
532 return true;
533 case ARCInstKind::User:
534 // Be conservative if the function has any alloca instructions.
535 // Technically we only care about escaping alloca instructions,
536 // but this is sufficient to handle some interesting cases.
537 if (isa<AllocaInst>(Inst))
538 TailOkForStoreStrongs = false;
539 return true;
540 case ARCInstKind::IntrinsicUser:
541 // Remove calls to @llvm.objc.clang.arc.use(...).
542 Changed = true;
543 Inst->eraseFromParent();
544 return true;
545 default:
546 return true;
547 }
548 }
549
550 //===----------------------------------------------------------------------===//
551 // Top Level Driver
552 //===----------------------------------------------------------------------===//
553
init(Module & M)554 bool ObjCARCContract::init(Module &M) {
555 // If nothing in the Module uses ARC, don't do anything.
556 Run = ModuleHasARC(M);
557 if (!Run)
558 return false;
559
560 EP.init(&M);
561
562 // Initialize RVInstMarker.
563 const char *MarkerKey = "clang.arc.retainAutoreleasedReturnValueMarker";
564 RVInstMarker = dyn_cast_or_null<MDString>(M.getModuleFlag(MarkerKey));
565
566 return false;
567 }
568
run(Function & F,AAResults * A,DominatorTree * D)569 bool ObjCARCContract::run(Function &F, AAResults *A, DominatorTree *D) {
570 if (!EnableARCOpts)
571 return false;
572
573 // If nothing in the Module uses ARC, don't do anything.
574 if (!Run)
575 return false;
576
577 Changed = false;
578 AA = A;
579 DT = D;
580 PA.setAA(A);
581
582 DenseMap<BasicBlock *, ColorVector> BlockColors;
583 if (F.hasPersonalityFn() &&
584 isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
585 BlockColors = colorEHFunclets(F);
586
587 LLVM_DEBUG(llvm::dbgs() << "**** ObjCARC Contract ****\n");
588
589 // Track whether it's ok to mark objc_storeStrong calls with the "tail"
590 // keyword. Be conservative if the function has variadic arguments.
591 // It seems that functions which "return twice" are also unsafe for the
592 // "tail" argument, because they are setjmp, which could need to
593 // return to an earlier stack state.
594 bool TailOkForStoreStrongs =
595 !F.isVarArg() && !F.callsFunctionThatReturnsTwice();
596
597 // For ObjC library calls which return their argument, replace uses of the
598 // argument with uses of the call return value, if it dominates the use. This
599 // reduces register pressure.
600 SmallPtrSet<Instruction *, 4> DependingInstructions;
601 SmallPtrSet<const BasicBlock *, 4> Visited;
602
603 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E;) {
604 Instruction *Inst = &*I++;
605
606 LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
607
608 // First try to peephole Inst. If there is nothing further we can do in
609 // terms of undoing objc-arc-expand, process the next inst.
610 if (tryToPeepholeInstruction(F, Inst, I, DependingInstructions, Visited,
611 TailOkForStoreStrongs, BlockColors))
612 continue;
613
614 // Otherwise, try to undo objc-arc-expand.
615
616 // Don't use GetArgRCIdentityRoot because we don't want to look through bitcasts
617 // and such; to do the replacement, the argument must have type i8*.
618
619 // Function for replacing uses of Arg dominated by Inst.
620 auto ReplaceArgUses = [Inst, this](Value *Arg) {
621 // If we're compiling bugpointed code, don't get in trouble.
622 if (!isa<Instruction>(Arg) && !isa<Argument>(Arg))
623 return;
624
625 // Look through the uses of the pointer.
626 for (Value::use_iterator UI = Arg->use_begin(), UE = Arg->use_end();
627 UI != UE; ) {
628 // Increment UI now, because we may unlink its element.
629 Use &U = *UI++;
630 unsigned OperandNo = U.getOperandNo();
631
632 // If the call's return value dominates a use of the call's argument
633 // value, rewrite the use to use the return value. We check for
634 // reachability here because an unreachable call is considered to
635 // trivially dominate itself, which would lead us to rewriting its
636 // argument in terms of its return value, which would lead to
637 // infinite loops in GetArgRCIdentityRoot.
638 if (!DT->isReachableFromEntry(U) || !DT->dominates(Inst, U))
639 continue;
640
641 Changed = true;
642 Instruction *Replacement = Inst;
643 Type *UseTy = U.get()->getType();
644 if (PHINode *PHI = dyn_cast<PHINode>(U.getUser())) {
645 // For PHI nodes, insert the bitcast in the predecessor block.
646 unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo);
647 BasicBlock *IncomingBB = PHI->getIncomingBlock(ValNo);
648 if (Replacement->getType() != UseTy) {
649 // A catchswitch is both a pad and a terminator, meaning a basic
650 // block with a catchswitch has no insertion point. Keep going up
651 // the dominator tree until we find a non-catchswitch.
652 BasicBlock *InsertBB = IncomingBB;
653 while (isa<CatchSwitchInst>(InsertBB->getFirstNonPHI())) {
654 InsertBB = DT->getNode(InsertBB)->getIDom()->getBlock();
655 }
656
657 assert(DT->dominates(Inst, &InsertBB->back()) &&
658 "Invalid insertion point for bitcast");
659 Replacement =
660 new BitCastInst(Replacement, UseTy, "", &InsertBB->back());
661 }
662
663 // While we're here, rewrite all edges for this PHI, rather
664 // than just one use at a time, to minimize the number of
665 // bitcasts we emit.
666 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
667 if (PHI->getIncomingBlock(i) == IncomingBB) {
668 // Keep the UI iterator valid.
669 if (UI != UE &&
670 &PHI->getOperandUse(
671 PHINode::getOperandNumForIncomingValue(i)) == &*UI)
672 ++UI;
673 PHI->setIncomingValue(i, Replacement);
674 }
675 } else {
676 if (Replacement->getType() != UseTy)
677 Replacement = new BitCastInst(Replacement, UseTy, "",
678 cast<Instruction>(U.getUser()));
679 U.set(Replacement);
680 }
681 }
682 };
683
684 Value *Arg = cast<CallInst>(Inst)->getArgOperand(0);
685 Value *OrigArg = Arg;
686
687 // TODO: Change this to a do-while.
688 for (;;) {
689 ReplaceArgUses(Arg);
690
691 // If Arg is a no-op casted pointer, strip one level of casts and iterate.
692 if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
693 Arg = BI->getOperand(0);
694 else if (isa<GEPOperator>(Arg) &&
695 cast<GEPOperator>(Arg)->hasAllZeroIndices())
696 Arg = cast<GEPOperator>(Arg)->getPointerOperand();
697 else if (isa<GlobalAlias>(Arg) &&
698 !cast<GlobalAlias>(Arg)->isInterposable())
699 Arg = cast<GlobalAlias>(Arg)->getAliasee();
700 else {
701 // If Arg is a PHI node, get PHIs that are equivalent to it and replace
702 // their uses.
703 if (PHINode *PN = dyn_cast<PHINode>(Arg)) {
704 SmallVector<Value *, 1> PHIList;
705 getEquivalentPHIs(*PN, PHIList);
706 for (Value *PHI : PHIList)
707 ReplaceArgUses(PHI);
708 }
709 break;
710 }
711 }
712
713 // Replace bitcast users of Arg that are dominated by Inst.
714 SmallVector<BitCastInst *, 2> BitCastUsers;
715
716 // Add all bitcast users of the function argument first.
717 for (User *U : OrigArg->users())
718 if (auto *BC = dyn_cast<BitCastInst>(U))
719 BitCastUsers.push_back(BC);
720
721 // Replace the bitcasts with the call return. Iterate until list is empty.
722 while (!BitCastUsers.empty()) {
723 auto *BC = BitCastUsers.pop_back_val();
724 for (User *U : BC->users())
725 if (auto *B = dyn_cast<BitCastInst>(U))
726 BitCastUsers.push_back(B);
727
728 ReplaceArgUses(BC);
729 }
730 }
731
732 // If this function has no escaping allocas or suspicious vararg usage,
733 // objc_storeStrong calls can be marked with the "tail" keyword.
734 if (TailOkForStoreStrongs)
735 for (CallInst *CI : StoreStrongCalls)
736 CI->setTailCall();
737 StoreStrongCalls.clear();
738
739 return Changed;
740 }
741
742 //===----------------------------------------------------------------------===//
743 // Misc Pass Manager
744 //===----------------------------------------------------------------------===//
745
746 char ObjCARCContractLegacyPass::ID = 0;
747 INITIALIZE_PASS_BEGIN(ObjCARCContractLegacyPass, "objc-arc-contract",
748 "ObjC ARC contraction", false, false)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)749 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
750 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
751 INITIALIZE_PASS_END(ObjCARCContractLegacyPass, "objc-arc-contract",
752 "ObjC ARC contraction", false, false)
753
754 void ObjCARCContractLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
755 AU.addRequired<AAResultsWrapperPass>();
756 AU.addRequired<DominatorTreeWrapperPass>();
757 AU.setPreservesCFG();
758 }
759
createObjCARCContractPass()760 Pass *llvm::createObjCARCContractPass() {
761 return new ObjCARCContractLegacyPass();
762 }
763
doInitialization(Module & M)764 bool ObjCARCContractLegacyPass::doInitialization(Module &M) {
765 return OCARCC.init(M);
766 }
767
runOnFunction(Function & F)768 bool ObjCARCContractLegacyPass::runOnFunction(Function &F) {
769 auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
770 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
771 return OCARCC.run(F, AA, DT);
772 }
773
run(Module & M,ModuleAnalysisManager & AM)774 PreservedAnalyses ObjCARCContractPass::run(Module &M,
775 ModuleAnalysisManager &AM) {
776 ObjCARCContract OCAC;
777 OCAC.init(M);
778
779 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
780 bool Changed = false;
781 for (Function &F : M) {
782 if (F.isDeclaration())
783 continue;
784 Changed |= OCAC.run(F, &FAM.getResult<AAManager>(F),
785 &FAM.getResult<DominatorTreeAnalysis>(F));
786 }
787 if (Changed) {
788 PreservedAnalyses PA;
789 PA.preserveSet<CFGAnalyses>();
790 return PA;
791 }
792 return PreservedAnalyses::all();
793 }
794