Index: llvm/include/llvm/Transforms/IPO/IROutliner.h =================================================================== --- llvm/include/llvm/Transforms/IPO/IROutliner.h +++ llvm/include/llvm/Transforms/IPO/IROutliner.h @@ -119,6 +119,9 @@ /// Used to create an outlined function. CodeExtractor *CE = nullptr; + /// Used to create an outlined function. + CodeExtractorAnalysisCache *CEAC = nullptr; + /// The call site of the extracted region. CallInst *Call = nullptr; @@ -333,6 +336,11 @@ /// that Value, back to its original Value. DenseMap OutputMappings; + /// A mapping from functions in the original modules to CodeExtractorAnalyis + /// Caches. These are updated as functions are outlined in order to be + /// consistent with vairbale sthat may have been removed, or moved. + DenseMap CEACs; + /// IRSimilarityIdentifier lambda to retrieve IRSimilarityIdentifier. function_ref getIRSI; @@ -342,6 +350,9 @@ /// The memory allocator used to allocate the CodeExtractors. SpecificBumpPtrAllocator ExtractorAllocator; + /// The memory allocator used to allocate the CodeExtractors. + SpecificBumpPtrAllocator CEACAllocator; + /// The memory allocator used to allocate the OutlinableRegions. SpecificBumpPtrAllocator RegionAllocator; Index: llvm/include/llvm/Transforms/Utils/CodeExtractor.h =================================================================== --- llvm/include/llvm/Transforms/Utils/CodeExtractor.h +++ llvm/include/llvm/Transforms/Utils/CodeExtractor.h @@ -53,12 +53,32 @@ /// Blocks which contain instructions which may have unknown side-effects /// on memory. DenseSet SideEffectingBlocks; + + /// The set of Instructions that have side effects, and the BasicBlock they + /// were initially in. + DenseMap SideEffectingInstructions; void findSideEffectInfoForBlock(BasicBlock &BB); public: CodeExtractorAnalysisCache(Function &F); + /// For a \p NewBlock that has been created from \p OldBlock, such that \p + /// OldBlock is a predecessor of \p NewBlock, check if \p NewBlock constains + /// any side effecting instructions such as the corresponding allocations for + /// loads, and stores, and record them. + /// + /// \param OldBlock - The original BasicBlock that was in the function. + /// \param NewBlock - The new BasicBlock with \p OldBlock as a predecessor. + void TestAndAddSideEffectingBlock(BasicBlock *OldBlock, BasicBlock *NewBlock); + + /// Remove enteries in the CodeExtractorAnalysisCache reference \p RemoveBlock + /// when it is no longer included in the Function that the cache was created + /// from. + /// + /// \param RemoveBlock - The BasicBlock to remove references to in the cache. + void TestAndRemoveSideEffectingBlock(BasicBlock *RemovedBlock); + /// Get the allocas in the function at the time the analysis was created. /// Note that some of these allocas may no longer be present in the function, /// due to \ref CodeExtractor::extractCodeRegion. Index: llvm/lib/Transforms/IPO/IROutliner.cpp =================================================================== --- llvm/lib/Transforms/IPO/IROutliner.cpp +++ llvm/lib/Transforms/IPO/IROutliner.cpp @@ -354,12 +354,26 @@ if (PHIPredBlock) PrevBB->replaceSuccessorsPhiUsesWith(PHIPredBlock, PrevBB); + // Add StartBB to the cache, and record its corresponding side effects so that + // inputs and outputs will be correctly analyzed. + CEAC->TestAndAddSideEffectingBlock(PrevBB, StartBB); + CandidateSplit = true; if (!BackInst->isTerminator()) { EndBB = EndInst->getParent(); FollowBB = EndBB->splitBasicBlock(EndInst, OriginalName + "_after_outline"); EndBB->replaceSuccessorsPhiUsesWith(EndBB, FollowBB); FollowBB->replaceSuccessorsPhiUsesWith(PrevBB, FollowBB); + + if (EndBB == StartBB) + // Add FollowBB to the cache, and record its corresponding side effects so + // that inputs and outputs will be correctly analyzed. + CEAC->TestAndAddSideEffectingBlock(PrevBB, FollowBB); + else + // Add FollowBB to the cache, and record its corresponding side effects so + // that inputs and outputs will be correctly analyzed. In this case we had + // multiple BasicBlocks, and EndBB is the parent block. + CEAC->TestAndAddSideEffectingBlock(EndBB, FollowBB); } else { EndBB = BackInst->getParent(); EndsInBranch = true; @@ -430,6 +444,9 @@ } moveBBContents(*StartBB, *PrevBB); + // As StartBB no longer exists, we remove references to it from the + // CodeExtractorAnalysis cache. + CEAC->TestAndRemoveSideEffectingBlock(StartBB); BasicBlock *PlacementBB = PrevBB; if (StartBB != EndBB) @@ -439,6 +456,9 @@ assert(PlacementBB->getTerminator() && "Terminator removed from EndBB!"); PlacementBB->getTerminator()->eraseFromParent(); moveBBContents(*FollowBB, *PlacementBB); + // As FollowBB no longer exists, we remove references to it from the + // CodeExtractorAnalysis cache. + CEAC->TestAndRemoveSideEffectingBlock(FollowBB); PlacementBB->replaceSuccessorsPhiUsesWith(FollowBB, PlacementBB); FollowBB->eraseFromParent(); } @@ -885,11 +905,6 @@ // allocas or removing llvm.assumes. CodeExtractor *CE = Region.CE; CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands); - assert(Region.StartBB && "Region must have a start BasicBlock!"); - Function *OrigF = Region.StartBB->getParent(); - CodeExtractorAnalysisCache CEAC(*OrigF); - BasicBlock *Dummy = nullptr; - // The region may be ineligible due to VarArgs in the parent function. In this // case we ignore the region. if (!CE->isEligible()) { @@ -897,8 +912,11 @@ return; } + assert(Region.StartBB && "Region must have a start BasicBlock!"); + BasicBlock *Dummy = nullptr; + // Find if any values are going to be sunk into the function when extracted - CE->findAllocas(CEAC, SinkCands, HoistCands, Dummy); + CE->findAllocas(*Region.CEAC, SinkCands, HoistCands, Dummy); CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands); // TODO: Support regions with sunken allocas: values whose lifetimes are @@ -2705,10 +2723,8 @@ SetVector ArgInputs, Outputs, SinkCands; assert(Region.StartBB && "StartBB for the OutlinableRegion is nullptr!"); BasicBlock *InitialStart = Region.StartBB; - Function *OrigF = Region.StartBB->getParent(); - CodeExtractorAnalysisCache CEAC(*OrigF); Region.ExtractedFunction = - Region.CE->extractCodeRegion(CEAC, ArgInputs, Outputs); + Region.CE->extractCodeRegion(*Region.CEAC, ArgInputs, Outputs); // If the extraction was successful, find the BasicBlock, and reassign the // OutlinableRegion blocks @@ -2830,6 +2846,19 @@ // types for the Aggregate Outlining Function. OutlinedRegions.clear(); for (OutlinableRegion *OS : CurrentGroup.Regions) { + Function *OrigF = OS->Candidate->getFunction(); + DenseMap::iterator CEACIt = + CEACs.find(OrigF); + if (CEACIt == CEACs.end()) { + bool Inserted = false; + CodeExtractorAnalysisCache *CEAC = + new (CEACAllocator.Allocate()) CodeExtractorAnalysisCache(*OrigF); + std::tie(CEACIt, Inserted) = CEACs.insert(std::make_pair(OrigF, CEAC)); + } + assert(CEACIt != CEACs.end() && + "Could not find a CodeExtractorAnalysisCache for function!"); + OS->CEAC = CEACIt->second; + // Break the outlinable region out of its parent BasicBlock into its own // BasicBlocks (see function implementation). OS->splitCandidate(); Index: llvm/lib/Transforms/Utils/CodeExtractor.cpp =================================================================== --- llvm/lib/Transforms/Utils/CodeExtractor.cpp +++ llvm/lib/Transforms/Utils/CodeExtractor.cpp @@ -317,6 +317,30 @@ } } +void CodeExtractorAnalysisCache::TestAndAddSideEffectingBlock( + BasicBlock *OldBlock, BasicBlock *NewBlock) { + if (BaseMemAddrs.find(OldBlock) != BaseMemAddrs.end()) { + findSideEffectInfoForBlock(*NewBlock); + return; + } + + if (SideEffectingBlocks.find(OldBlock) == SideEffectingBlocks.end()) + return; + + findSideEffectInfoForBlock(*NewBlock); +} + +void CodeExtractorAnalysisCache::TestAndRemoveSideEffectingBlock( + BasicBlock *RemovedBlock) { + if (BaseMemAddrs.find(RemovedBlock) != BaseMemAddrs.end()) + BaseMemAddrs.erase(RemovedBlock); + + if (SideEffectingBlocks.find(RemovedBlock) == SideEffectingBlocks.end()) + return; + + SideEffectingBlocks.erase(RemovedBlock); +} + void CodeExtractorAnalysisCache::findSideEffectInfoForBlock(BasicBlock &BB) { for (Instruction &II : BB.instructionsWithoutDebug()) { unsigned Opcode = II.getOpcode(); @@ -337,6 +361,7 @@ Value *Base = MemAddr->stripInBoundsConstantOffsets(); if (!isa(Base)) { SideEffectingBlocks.insert(&BB); + SideEffectingInstructions.insert(std::make_pair(&BB, &II)); return; } BaseMemAddrs[&BB].insert(Base); @@ -348,11 +373,13 @@ if (IntrInst->isLifetimeStartOrEnd()) break; SideEffectingBlocks.insert(&BB); + SideEffectingInstructions.insert(std::make_pair(&BB, &II)); return; } // Treat all the other cases conservatively if it has side effects. if (II.mayHaveSideEffects()) { SideEffectingBlocks.insert(&BB); + SideEffectingInstructions.insert(std::make_pair(&BB, &II)); return; } }