CloneFunction.cpp 33 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830
  1. //===- CloneFunction.cpp - Clone a function into another function ---------===//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  8. //===----------------------------------------------------------------------===//
  9. //
  10. // This file implements the CloneFunctionInto interface, which is used as the
  11. // low-level function cloner. This is used by the CloneFunction and function
  12. // inliner to do the dirty work of copying the body of a function around.
  13. //
  14. //===----------------------------------------------------------------------===//
  15. #include "llvm/ADT/SetVector.h"
  16. #include "llvm/ADT/SmallVector.h"
  17. #include "llvm/Analysis/ConstantFolding.h"
  18. #include "llvm/Analysis/InstructionSimplify.h"
  19. #include "llvm/Analysis/LoopInfo.h"
  20. #include "llvm/IR/CFG.h"
  21. #include "llvm/IR/Constants.h"
  22. #include "llvm/IR/DebugInfo.h"
  23. #include "llvm/IR/DerivedTypes.h"
  24. #include "llvm/IR/Function.h"
  25. #include "llvm/IR/GlobalVariable.h"
  26. #include "llvm/IR/Instructions.h"
  27. #include "llvm/IR/IntrinsicInst.h"
  28. #include "llvm/IR/LLVMContext.h"
  29. #include "llvm/IR/Metadata.h"
  30. #include "llvm/IR/Module.h"
  31. #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  32. #include "llvm/Transforms/Utils/Cloning.h"
  33. #include "llvm/Transforms/Utils/Local.h"
  34. #include "llvm/Transforms/Utils/ValueMapper.h"
  35. #include <map>
  36. using namespace llvm;
  37. /// See comments in Cloning.h.
  38. BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap,
  39. const Twine &NameSuffix, Function *F,
  40. ClonedCodeInfo *CodeInfo,
  41. DebugInfoFinder *DIFinder) {
  42. DenseMap<const MDNode *, MDNode *> Cache;
  43. BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "", F);
  44. if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
  45. bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
  46. Module *TheModule = F ? F->getParent() : nullptr;
  47. // Loop over all instructions, and copy them over.
  48. for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
  49. II != IE; ++II) {
  50. if (DIFinder && TheModule) {
  51. if (auto *DDI = dyn_cast<DbgDeclareInst>(II))
  52. DIFinder->processDeclare(*TheModule, DDI);
  53. else if (auto *DVI = dyn_cast<DbgValueInst>(II))
  54. DIFinder->processValue(*TheModule, DVI);
  55. if (auto DbgLoc = II->getDebugLoc())
  56. DIFinder->processLocation(*TheModule, DbgLoc.get());
  57. }
  58. Instruction *NewInst = II->clone();
  59. if (II->hasName())
  60. NewInst->setName(II->getName()+NameSuffix);
  61. NewBB->getInstList().push_back(NewInst);
  62. VMap[&*II] = NewInst; // Add instruction map to value.
  63. hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
  64. if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
  65. if (isa<ConstantInt>(AI->getArraySize()))
  66. hasStaticAllocas = true;
  67. else
  68. hasDynamicAllocas = true;
  69. }
  70. }
  71. if (CodeInfo) {
  72. CodeInfo->ContainsCalls |= hasCalls;
  73. CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
  74. CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
  75. BB != &BB->getParent()->getEntryBlock();
  76. }
  77. return NewBB;
  78. }
  79. // Clone OldFunc into NewFunc, transforming the old arguments into references to
  80. // VMap values.
  81. //
  82. void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
  83. ValueToValueMapTy &VMap,
  84. bool ModuleLevelChanges,
  85. SmallVectorImpl<ReturnInst*> &Returns,
  86. const char *NameSuffix, ClonedCodeInfo *CodeInfo,
  87. ValueMapTypeRemapper *TypeMapper,
  88. ValueMaterializer *Materializer) {
  89. assert(NameSuffix && "NameSuffix cannot be null!");
  90. #ifndef NDEBUG
  91. for (const Argument &I : OldFunc->args())
  92. assert(VMap.count(&I) && "No mapping from source argument specified!");
  93. #endif
  94. // Copy all attributes other than those stored in the AttributeList. We need
  95. // to remap the parameter indices of the AttributeList.
  96. AttributeList NewAttrs = NewFunc->getAttributes();
  97. NewFunc->copyAttributesFrom(OldFunc);
  98. NewFunc->setAttributes(NewAttrs);
  99. // Fix up the personality function that got copied over.
  100. if (OldFunc->hasPersonalityFn())
  101. NewFunc->setPersonalityFn(
  102. MapValue(OldFunc->getPersonalityFn(), VMap,
  103. ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
  104. TypeMapper, Materializer));
  105. SmallVector<AttributeSet, 4> NewArgAttrs(NewFunc->arg_size());
  106. AttributeList OldAttrs = OldFunc->getAttributes();
  107. // Clone any argument attributes that are present in the VMap.
  108. for (const Argument &OldArg : OldFunc->args()) {
  109. if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) {
  110. NewArgAttrs[NewArg->getArgNo()] =
  111. OldAttrs.getParamAttributes(OldArg.getArgNo());
  112. }
  113. }
  114. NewFunc->setAttributes(
  115. AttributeList::get(NewFunc->getContext(), OldAttrs.getFnAttributes(),
  116. OldAttrs.getRetAttributes(), NewArgAttrs));
  117. bool MustCloneSP =
  118. OldFunc->getParent() && OldFunc->getParent() == NewFunc->getParent();
  119. DISubprogram *SP = OldFunc->getSubprogram();
  120. if (SP) {
  121. assert(!MustCloneSP || ModuleLevelChanges);
  122. // Add mappings for some DebugInfo nodes that we don't want duplicated
  123. // even if they're distinct.
  124. auto &MD = VMap.MD();
  125. MD[SP->getUnit()].reset(SP->getUnit());
  126. MD[SP->getType()].reset(SP->getType());
  127. MD[SP->getFile()].reset(SP->getFile());
  128. // If we're not cloning into the same module, no need to clone the
  129. // subprogram
  130. if (!MustCloneSP)
  131. MD[SP].reset(SP);
  132. }
  133. SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
  134. OldFunc->getAllMetadata(MDs);
  135. for (auto MD : MDs) {
  136. NewFunc->addMetadata(
  137. MD.first,
  138. *MapMetadata(MD.second, VMap,
  139. ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
  140. TypeMapper, Materializer));
  141. }
  142. // When we remap instructions, we want to avoid duplicating inlined
  143. // DISubprograms, so record all subprograms we find as we duplicate
  144. // instructions and then freeze them in the MD map.
  145. // We also record information about dbg.value and dbg.declare to avoid
  146. // duplicating the types.
  147. DebugInfoFinder DIFinder;
  148. // Loop over all of the basic blocks in the function, cloning them as
  149. // appropriate. Note that we save BE this way in order to handle cloning of
  150. // recursive functions into themselves.
  151. //
  152. for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
  153. BI != BE; ++BI) {
  154. const BasicBlock &BB = *BI;
  155. // Create a new basic block and copy instructions into it!
  156. BasicBlock *CBB = CloneBasicBlock(&BB, VMap, NameSuffix, NewFunc, CodeInfo,
  157. SP ? &DIFinder : nullptr);
  158. // Add basic block mapping.
  159. VMap[&BB] = CBB;
  160. // It is only legal to clone a function if a block address within that
  161. // function is never referenced outside of the function. Given that, we
  162. // want to map block addresses from the old function to block addresses in
  163. // the clone. (This is different from the generic ValueMapper
  164. // implementation, which generates an invalid blockaddress when
  165. // cloning a function.)
  166. if (BB.hasAddressTaken()) {
  167. Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
  168. const_cast<BasicBlock*>(&BB));
  169. VMap[OldBBAddr] = BlockAddress::get(NewFunc, CBB);
  170. }
  171. // Note return instructions for the caller.
  172. if (ReturnInst *RI = dyn_cast<ReturnInst>(CBB->getTerminator()))
  173. Returns.push_back(RI);
  174. }
  175. for (DISubprogram *ISP : DIFinder.subprograms()) {
  176. if (ISP != SP) {
  177. VMap.MD()[ISP].reset(ISP);
  178. }
  179. }
  180. for (auto *Type : DIFinder.types()) {
  181. VMap.MD()[Type].reset(Type);
  182. }
  183. // Loop over all of the instructions in the function, fixing up operand
  184. // references as we go. This uses VMap to do all the hard work.
  185. for (Function::iterator BB =
  186. cast<BasicBlock>(VMap[&OldFunc->front()])->getIterator(),
  187. BE = NewFunc->end();
  188. BB != BE; ++BB)
  189. // Loop over all instructions, fixing each one as we find it...
  190. for (Instruction &II : *BB)
  191. RemapInstruction(&II, VMap,
  192. ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
  193. TypeMapper, Materializer);
  194. }
  195. /// Return a copy of the specified function and add it to that function's
  196. /// module. Also, any references specified in the VMap are changed to refer to
  197. /// their mapped value instead of the original one. If any of the arguments to
  198. /// the function are in the VMap, the arguments are deleted from the resultant
  199. /// function. The VMap is updated to include mappings from all of the
  200. /// instructions and basicblocks in the function from their old to new values.
  201. ///
  202. Function *llvm::CloneFunction(Function *F, ValueToValueMapTy &VMap,
  203. ClonedCodeInfo *CodeInfo) {
  204. std::vector<Type*> ArgTypes;
  205. // The user might be deleting arguments to the function by specifying them in
  206. // the VMap. If so, we need to not add the arguments to the arg ty vector
  207. //
  208. for (const Argument &I : F->args())
  209. if (VMap.count(&I) == 0) // Haven't mapped the argument to anything yet?
  210. ArgTypes.push_back(I.getType());
  211. // Create a new function type...
  212. FunctionType *FTy = FunctionType::get(F->getFunctionType()->getReturnType(),
  213. ArgTypes, F->getFunctionType()->isVarArg());
  214. // Create the new function...
  215. Function *NewF =
  216. Function::Create(FTy, F->getLinkage(), F->getName(), F->getParent());
  217. // Loop over the arguments, copying the names of the mapped arguments over...
  218. Function::arg_iterator DestI = NewF->arg_begin();
  219. for (const Argument & I : F->args())
  220. if (VMap.count(&I) == 0) { // Is this argument preserved?
  221. DestI->setName(I.getName()); // Copy the name over...
  222. VMap[&I] = &*DestI++; // Add mapping to VMap
  223. }
  224. SmallVector<ReturnInst*, 8> Returns; // Ignore returns cloned.
  225. CloneFunctionInto(NewF, F, VMap, F->getSubprogram() != nullptr, Returns, "",
  226. CodeInfo);
  227. return NewF;
  228. }
  229. namespace {
  230. /// This is a private class used to implement CloneAndPruneFunctionInto.
  231. struct PruningFunctionCloner {
  232. Function *NewFunc;
  233. const Function *OldFunc;
  234. ValueToValueMapTy &VMap;
  235. bool ModuleLevelChanges;
  236. const char *NameSuffix;
  237. ClonedCodeInfo *CodeInfo;
  238. public:
  239. PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
  240. ValueToValueMapTy &valueMap, bool moduleLevelChanges,
  241. const char *nameSuffix, ClonedCodeInfo *codeInfo)
  242. : NewFunc(newFunc), OldFunc(oldFunc), VMap(valueMap),
  243. ModuleLevelChanges(moduleLevelChanges), NameSuffix(nameSuffix),
  244. CodeInfo(codeInfo) {}
  245. /// The specified block is found to be reachable, clone it and
  246. /// anything that it can reach.
  247. void CloneBlock(const BasicBlock *BB,
  248. BasicBlock::const_iterator StartingInst,
  249. std::vector<const BasicBlock*> &ToClone);
  250. };
  251. }
  252. /// The specified block is found to be reachable, clone it and
  253. /// anything that it can reach.
  254. void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
  255. BasicBlock::const_iterator StartingInst,
  256. std::vector<const BasicBlock*> &ToClone){
  257. WeakTrackingVH &BBEntry = VMap[BB];
  258. // Have we already cloned this block?
  259. if (BBEntry) return;
  260. // Nope, clone it now.
  261. BasicBlock *NewBB;
  262. BBEntry = NewBB = BasicBlock::Create(BB->getContext());
  263. if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
  264. // It is only legal to clone a function if a block address within that
  265. // function is never referenced outside of the function. Given that, we
  266. // want to map block addresses from the old function to block addresses in
  267. // the clone. (This is different from the generic ValueMapper
  268. // implementation, which generates an invalid blockaddress when
  269. // cloning a function.)
  270. //
  271. // Note that we don't need to fix the mapping for unreachable blocks;
  272. // the default mapping there is safe.
  273. if (BB->hasAddressTaken()) {
  274. Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
  275. const_cast<BasicBlock*>(BB));
  276. VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB);
  277. }
  278. bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
  279. // Loop over all instructions, and copy them over, DCE'ing as we go. This
  280. // loop doesn't include the terminator.
  281. for (BasicBlock::const_iterator II = StartingInst, IE = --BB->end();
  282. II != IE; ++II) {
  283. Instruction *NewInst = II->clone();
  284. // Eagerly remap operands to the newly cloned instruction, except for PHI
  285. // nodes for which we defer processing until we update the CFG.
  286. if (!isa<PHINode>(NewInst)) {
  287. RemapInstruction(NewInst, VMap,
  288. ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
  289. // If we can simplify this instruction to some other value, simply add
  290. // a mapping to that value rather than inserting a new instruction into
  291. // the basic block.
  292. if (Value *V =
  293. SimplifyInstruction(NewInst, BB->getModule()->getDataLayout())) {
  294. // On the off-chance that this simplifies to an instruction in the old
  295. // function, map it back into the new function.
  296. if (NewFunc != OldFunc)
  297. if (Value *MappedV = VMap.lookup(V))
  298. V = MappedV;
  299. if (!NewInst->mayHaveSideEffects()) {
  300. VMap[&*II] = V;
  301. NewInst->deleteValue();
  302. continue;
  303. }
  304. }
  305. }
  306. if (II->hasName())
  307. NewInst->setName(II->getName()+NameSuffix);
  308. VMap[&*II] = NewInst; // Add instruction map to value.
  309. NewBB->getInstList().push_back(NewInst);
  310. hasCalls |= (isa<CallInst>(II) && !isa<DbgInfoIntrinsic>(II));
  311. if (CodeInfo)
  312. if (auto CS = ImmutableCallSite(&*II))
  313. if (CS.hasOperandBundles())
  314. CodeInfo->OperandBundleCallSites.push_back(NewInst);
  315. if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
  316. if (isa<ConstantInt>(AI->getArraySize()))
  317. hasStaticAllocas = true;
  318. else
  319. hasDynamicAllocas = true;
  320. }
  321. }
  322. // Finally, clone over the terminator.
  323. const TerminatorInst *OldTI = BB->getTerminator();
  324. bool TerminatorDone = false;
  325. if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
  326. if (BI->isConditional()) {
  327. // If the condition was a known constant in the callee...
  328. ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
  329. // Or is a known constant in the caller...
  330. if (!Cond) {
  331. Value *V = VMap.lookup(BI->getCondition());
  332. Cond = dyn_cast_or_null<ConstantInt>(V);
  333. }
  334. // Constant fold to uncond branch!
  335. if (Cond) {
  336. BasicBlock *Dest = BI->getSuccessor(!Cond->getZExtValue());
  337. VMap[OldTI] = BranchInst::Create(Dest, NewBB);
  338. ToClone.push_back(Dest);
  339. TerminatorDone = true;
  340. }
  341. }
  342. } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
  343. // If switching on a value known constant in the caller.
  344. ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
  345. if (!Cond) { // Or known constant after constant prop in the callee...
  346. Value *V = VMap.lookup(SI->getCondition());
  347. Cond = dyn_cast_or_null<ConstantInt>(V);
  348. }
  349. if (Cond) { // Constant fold to uncond branch!
  350. SwitchInst::ConstCaseHandle Case = *SI->findCaseValue(Cond);
  351. BasicBlock *Dest = const_cast<BasicBlock*>(Case.getCaseSuccessor());
  352. VMap[OldTI] = BranchInst::Create(Dest, NewBB);
  353. ToClone.push_back(Dest);
  354. TerminatorDone = true;
  355. }
  356. }
  357. if (!TerminatorDone) {
  358. Instruction *NewInst = OldTI->clone();
  359. if (OldTI->hasName())
  360. NewInst->setName(OldTI->getName()+NameSuffix);
  361. NewBB->getInstList().push_back(NewInst);
  362. VMap[OldTI] = NewInst; // Add instruction map to value.
  363. if (CodeInfo)
  364. if (auto CS = ImmutableCallSite(OldTI))
  365. if (CS.hasOperandBundles())
  366. CodeInfo->OperandBundleCallSites.push_back(NewInst);
  367. // Recursively clone any reachable successor blocks.
  368. const TerminatorInst *TI = BB->getTerminator();
  369. for (const BasicBlock *Succ : TI->successors())
  370. ToClone.push_back(Succ);
  371. }
  372. if (CodeInfo) {
  373. CodeInfo->ContainsCalls |= hasCalls;
  374. CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
  375. CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
  376. BB != &BB->getParent()->front();
  377. }
  378. }
  379. /// This works like CloneAndPruneFunctionInto, except that it does not clone the
  380. /// entire function. Instead it starts at an instruction provided by the caller
  381. /// and copies (and prunes) only the code reachable from that instruction.
  382. void llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
  383. const Instruction *StartingInst,
  384. ValueToValueMapTy &VMap,
  385. bool ModuleLevelChanges,
  386. SmallVectorImpl<ReturnInst *> &Returns,
  387. const char *NameSuffix,
  388. ClonedCodeInfo *CodeInfo) {
  389. assert(NameSuffix && "NameSuffix cannot be null!");
  390. ValueMapTypeRemapper *TypeMapper = nullptr;
  391. ValueMaterializer *Materializer = nullptr;
  392. #ifndef NDEBUG
  393. // If the cloning starts at the beginning of the function, verify that
  394. // the function arguments are mapped.
  395. if (!StartingInst)
  396. for (const Argument &II : OldFunc->args())
  397. assert(VMap.count(&II) && "No mapping from source argument specified!");
  398. #endif
  399. PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
  400. NameSuffix, CodeInfo);
  401. const BasicBlock *StartingBB;
  402. if (StartingInst)
  403. StartingBB = StartingInst->getParent();
  404. else {
  405. StartingBB = &OldFunc->getEntryBlock();
  406. StartingInst = &StartingBB->front();
  407. }
  408. // Clone the entry block, and anything recursively reachable from it.
  409. std::vector<const BasicBlock*> CloneWorklist;
  410. PFC.CloneBlock(StartingBB, StartingInst->getIterator(), CloneWorklist);
  411. while (!CloneWorklist.empty()) {
  412. const BasicBlock *BB = CloneWorklist.back();
  413. CloneWorklist.pop_back();
  414. PFC.CloneBlock(BB, BB->begin(), CloneWorklist);
  415. }
  416. // Loop over all of the basic blocks in the old function. If the block was
  417. // reachable, we have cloned it and the old block is now in the value map:
  418. // insert it into the new function in the right order. If not, ignore it.
  419. //
  420. // Defer PHI resolution until rest of function is resolved.
  421. SmallVector<const PHINode*, 16> PHIToResolve;
  422. for (const BasicBlock &BI : *OldFunc) {
  423. Value *V = VMap.lookup(&BI);
  424. BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
  425. if (!NewBB) continue; // Dead block.
  426. // Add the new block to the new function.
  427. NewFunc->getBasicBlockList().push_back(NewBB);
  428. // Handle PHI nodes specially, as we have to remove references to dead
  429. // blocks.
  430. for (const PHINode &PN : BI.phis()) {
  431. // PHI nodes may have been remapped to non-PHI nodes by the caller or
  432. // during the cloning process.
  433. if (isa<PHINode>(VMap[&PN]))
  434. PHIToResolve.push_back(&PN);
  435. else
  436. break;
  437. }
  438. // Finally, remap the terminator instructions, as those can't be remapped
  439. // until all BBs are mapped.
  440. RemapInstruction(NewBB->getTerminator(), VMap,
  441. ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
  442. TypeMapper, Materializer);
  443. }
  444. // Defer PHI resolution until rest of function is resolved, PHI resolution
  445. // requires the CFG to be up-to-date.
  446. for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
  447. const PHINode *OPN = PHIToResolve[phino];
  448. unsigned NumPreds = OPN->getNumIncomingValues();
  449. const BasicBlock *OldBB = OPN->getParent();
  450. BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]);
  451. // Map operands for blocks that are live and remove operands for blocks
  452. // that are dead.
  453. for (; phino != PHIToResolve.size() &&
  454. PHIToResolve[phino]->getParent() == OldBB; ++phino) {
  455. OPN = PHIToResolve[phino];
  456. PHINode *PN = cast<PHINode>(VMap[OPN]);
  457. for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
  458. Value *V = VMap.lookup(PN->getIncomingBlock(pred));
  459. if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) {
  460. Value *InVal = MapValue(PN->getIncomingValue(pred),
  461. VMap,
  462. ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
  463. assert(InVal && "Unknown input value?");
  464. PN->setIncomingValue(pred, InVal);
  465. PN->setIncomingBlock(pred, MappedBlock);
  466. } else {
  467. PN->removeIncomingValue(pred, false);
  468. --pred; // Revisit the next entry.
  469. --e;
  470. }
  471. }
  472. }
  473. // The loop above has removed PHI entries for those blocks that are dead
  474. // and has updated others. However, if a block is live (i.e. copied over)
  475. // but its terminator has been changed to not go to this block, then our
  476. // phi nodes will have invalid entries. Update the PHI nodes in this
  477. // case.
  478. PHINode *PN = cast<PHINode>(NewBB->begin());
  479. NumPreds = std::distance(pred_begin(NewBB), pred_end(NewBB));
  480. if (NumPreds != PN->getNumIncomingValues()) {
  481. assert(NumPreds < PN->getNumIncomingValues());
  482. // Count how many times each predecessor comes to this block.
  483. std::map<BasicBlock*, unsigned> PredCount;
  484. for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB);
  485. PI != E; ++PI)
  486. --PredCount[*PI];
  487. // Figure out how many entries to remove from each PHI.
  488. for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
  489. ++PredCount[PN->getIncomingBlock(i)];
  490. // At this point, the excess predecessor entries are positive in the
  491. // map. Loop over all of the PHIs and remove excess predecessor
  492. // entries.
  493. BasicBlock::iterator I = NewBB->begin();
  494. for (; (PN = dyn_cast<PHINode>(I)); ++I) {
  495. for (const auto &PCI : PredCount) {
  496. BasicBlock *Pred = PCI.first;
  497. for (unsigned NumToRemove = PCI.second; NumToRemove; --NumToRemove)
  498. PN->removeIncomingValue(Pred, false);
  499. }
  500. }
  501. }
  502. // If the loops above have made these phi nodes have 0 or 1 operand,
  503. // replace them with undef or the input value. We must do this for
  504. // correctness, because 0-operand phis are not valid.
  505. PN = cast<PHINode>(NewBB->begin());
  506. if (PN->getNumIncomingValues() == 0) {
  507. BasicBlock::iterator I = NewBB->begin();
  508. BasicBlock::const_iterator OldI = OldBB->begin();
  509. while ((PN = dyn_cast<PHINode>(I++))) {
  510. Value *NV = UndefValue::get(PN->getType());
  511. PN->replaceAllUsesWith(NV);
  512. assert(VMap[&*OldI] == PN && "VMap mismatch");
  513. VMap[&*OldI] = NV;
  514. PN->eraseFromParent();
  515. ++OldI;
  516. }
  517. }
  518. }
  519. // Make a second pass over the PHINodes now that all of them have been
  520. // remapped into the new function, simplifying the PHINode and performing any
  521. // recursive simplifications exposed. This will transparently update the
  522. // WeakTrackingVH in the VMap. Notably, we rely on that so that if we coalesce
  523. // two PHINodes, the iteration over the old PHIs remains valid, and the
  524. // mapping will just map us to the new node (which may not even be a PHI
  525. // node).
  526. const DataLayout &DL = NewFunc->getParent()->getDataLayout();
  527. SmallSetVector<const Value *, 8> Worklist;
  528. for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx)
  529. if (isa<PHINode>(VMap[PHIToResolve[Idx]]))
  530. Worklist.insert(PHIToResolve[Idx]);
  531. // Note that we must test the size on each iteration, the worklist can grow.
  532. for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
  533. const Value *OrigV = Worklist[Idx];
  534. auto *I = dyn_cast_or_null<Instruction>(VMap.lookup(OrigV));
  535. if (!I)
  536. continue;
  537. // Skip over non-intrinsic callsites, we don't want to remove any nodes from
  538. // the CGSCC.
  539. CallSite CS = CallSite(I);
  540. if (CS && CS.getCalledFunction() && !CS.getCalledFunction()->isIntrinsic())
  541. continue;
  542. // See if this instruction simplifies.
  543. Value *SimpleV = SimplifyInstruction(I, DL);
  544. if (!SimpleV)
  545. continue;
  546. // Stash away all the uses of the old instruction so we can check them for
  547. // recursive simplifications after a RAUW. This is cheaper than checking all
  548. // uses of To on the recursive step in most cases.
  549. for (const User *U : OrigV->users())
  550. Worklist.insert(cast<Instruction>(U));
  551. // Replace the instruction with its simplified value.
  552. I->replaceAllUsesWith(SimpleV);
  553. // If the original instruction had no side effects, remove it.
  554. if (isInstructionTriviallyDead(I))
  555. I->eraseFromParent();
  556. else
  557. VMap[OrigV] = I;
  558. }
  559. // Now that the inlined function body has been fully constructed, go through
  560. // and zap unconditional fall-through branches. This happens all the time when
  561. // specializing code: code specialization turns conditional branches into
  562. // uncond branches, and this code folds them.
  563. Function::iterator Begin = cast<BasicBlock>(VMap[StartingBB])->getIterator();
  564. Function::iterator I = Begin;
  565. while (I != NewFunc->end()) {
  566. // Check if this block has become dead during inlining or other
  567. // simplifications. Note that the first block will appear dead, as it has
  568. // not yet been wired up properly.
  569. if (I != Begin && (pred_begin(&*I) == pred_end(&*I) ||
  570. I->getSinglePredecessor() == &*I)) {
  571. BasicBlock *DeadBB = &*I++;
  572. DeleteDeadBlock(DeadBB);
  573. continue;
  574. }
  575. // We need to simplify conditional branches and switches with a constant
  576. // operand. We try to prune these out when cloning, but if the
  577. // simplification required looking through PHI nodes, those are only
  578. // available after forming the full basic block. That may leave some here,
  579. // and we still want to prune the dead code as early as possible.
  580. ConstantFoldTerminator(&*I);
  581. BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
  582. if (!BI || BI->isConditional()) { ++I; continue; }
  583. BasicBlock *Dest = BI->getSuccessor(0);
  584. if (!Dest->getSinglePredecessor()) {
  585. ++I; continue;
  586. }
  587. // We shouldn't be able to get single-entry PHI nodes here, as instsimplify
  588. // above should have zapped all of them..
  589. assert(!isa<PHINode>(Dest->begin()));
  590. // We know all single-entry PHI nodes in the inlined function have been
  591. // removed, so we just need to splice the blocks.
  592. BI->eraseFromParent();
  593. // Make all PHI nodes that referred to Dest now refer to I as their source.
  594. Dest->replaceAllUsesWith(&*I);
  595. // Move all the instructions in the succ to the pred.
  596. I->getInstList().splice(I->end(), Dest->getInstList());
  597. // Remove the dest block.
  598. Dest->eraseFromParent();
  599. // Do not increment I, iteratively merge all things this block branches to.
  600. }
  601. // Make a final pass over the basic blocks from the old function to gather
  602. // any return instructions which survived folding. We have to do this here
  603. // because we can iteratively remove and merge returns above.
  604. for (Function::iterator I = cast<BasicBlock>(VMap[StartingBB])->getIterator(),
  605. E = NewFunc->end();
  606. I != E; ++I)
  607. if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator()))
  608. Returns.push_back(RI);
  609. }
  610. /// This works exactly like CloneFunctionInto,
  611. /// except that it does some simple constant prop and DCE on the fly. The
  612. /// effect of this is to copy significantly less code in cases where (for
  613. /// example) a function call with constant arguments is inlined, and those
  614. /// constant arguments cause a significant amount of code in the callee to be
  615. /// dead. Since this doesn't produce an exact copy of the input, it can't be
  616. /// used for things like CloneFunction or CloneModule.
  617. void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
  618. ValueToValueMapTy &VMap,
  619. bool ModuleLevelChanges,
  620. SmallVectorImpl<ReturnInst*> &Returns,
  621. const char *NameSuffix,
  622. ClonedCodeInfo *CodeInfo,
  623. Instruction *TheCall) {
  624. CloneAndPruneIntoFromInst(NewFunc, OldFunc, &OldFunc->front().front(), VMap,
  625. ModuleLevelChanges, Returns, NameSuffix, CodeInfo);
  626. }
  627. /// \brief Remaps instructions in \p Blocks using the mapping in \p VMap.
  628. void llvm::remapInstructionsInBlocks(
  629. const SmallVectorImpl<BasicBlock *> &Blocks, ValueToValueMapTy &VMap) {
  630. // Rewrite the code to refer to itself.
  631. for (auto *BB : Blocks)
  632. for (auto &Inst : *BB)
  633. RemapInstruction(&Inst, VMap,
  634. RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
  635. }
  636. /// \brief Clones a loop \p OrigLoop. Returns the loop and the blocks in \p
  637. /// Blocks.
  638. ///
  639. /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block
  640. /// \p LoopDomBB. Insert the new blocks before block specified in \p Before.
  641. Loop *llvm::cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
  642. Loop *OrigLoop, ValueToValueMapTy &VMap,
  643. const Twine &NameSuffix, LoopInfo *LI,
  644. DominatorTree *DT,
  645. SmallVectorImpl<BasicBlock *> &Blocks) {
  646. assert(OrigLoop->getSubLoops().empty() &&
  647. "Loop to be cloned cannot have inner loop");
  648. Function *F = OrigLoop->getHeader()->getParent();
  649. Loop *ParentLoop = OrigLoop->getParentLoop();
  650. Loop *NewLoop = LI->AllocateLoop();
  651. if (ParentLoop)
  652. ParentLoop->addChildLoop(NewLoop);
  653. else
  654. LI->addTopLevelLoop(NewLoop);
  655. BasicBlock *OrigPH = OrigLoop->getLoopPreheader();
  656. assert(OrigPH && "No preheader");
  657. BasicBlock *NewPH = CloneBasicBlock(OrigPH, VMap, NameSuffix, F);
  658. // To rename the loop PHIs.
  659. VMap[OrigPH] = NewPH;
  660. Blocks.push_back(NewPH);
  661. // Update LoopInfo.
  662. if (ParentLoop)
  663. ParentLoop->addBasicBlockToLoop(NewPH, *LI);
  664. // Update DominatorTree.
  665. DT->addNewBlock(NewPH, LoopDomBB);
  666. for (BasicBlock *BB : OrigLoop->getBlocks()) {
  667. BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix, F);
  668. VMap[BB] = NewBB;
  669. // Update LoopInfo.
  670. NewLoop->addBasicBlockToLoop(NewBB, *LI);
  671. // Add DominatorTree node. After seeing all blocks, update to correct IDom.
  672. DT->addNewBlock(NewBB, NewPH);
  673. Blocks.push_back(NewBB);
  674. }
  675. for (BasicBlock *BB : OrigLoop->getBlocks()) {
  676. // Update DominatorTree.
  677. BasicBlock *IDomBB = DT->getNode(BB)->getIDom()->getBlock();
  678. DT->changeImmediateDominator(cast<BasicBlock>(VMap[BB]),
  679. cast<BasicBlock>(VMap[IDomBB]));
  680. }
  681. // Move them physically from the end of the block list.
  682. F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(),
  683. NewPH);
  684. F->getBasicBlockList().splice(Before->getIterator(), F->getBasicBlockList(),
  685. NewLoop->getHeader()->getIterator(), F->end());
  686. return NewLoop;
  687. }
  688. /// \brief Duplicate non-Phi instructions from the beginning of block up to
  689. /// StopAt instruction into a split block between BB and its predecessor.
  690. BasicBlock *
  691. llvm::DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB,
  692. Instruction *StopAt,
  693. ValueToValueMapTy &ValueMapping) {
  694. // We are going to have to map operands from the original BB block to the new
  695. // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to
  696. // account for entry from PredBB.
  697. BasicBlock::iterator BI = BB->begin();
  698. for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
  699. ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
  700. BasicBlock *NewBB = SplitEdge(PredBB, BB);
  701. NewBB->setName(PredBB->getName() + ".split");
  702. Instruction *NewTerm = NewBB->getTerminator();
  703. // Clone the non-phi instructions of BB into NewBB, keeping track of the
  704. // mapping and using it to remap operands in the cloned instructions.
  705. for (; StopAt != &*BI; ++BI) {
  706. Instruction *New = BI->clone();
  707. New->setName(BI->getName());
  708. New->insertBefore(NewTerm);
  709. ValueMapping[&*BI] = New;
  710. // Remap operands to patch up intra-block references.
  711. for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
  712. if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
  713. auto I = ValueMapping.find(Inst);
  714. if (I != ValueMapping.end())
  715. New->setOperand(i, I->second);
  716. }
  717. }
  718. return NewBB;
  719. }