Index: include/llvm/IR/Instructions.h =================================================================== --- include/llvm/IR/Instructions.h +++ include/llvm/IR/Instructions.h @@ -35,6 +35,7 @@ class ConstantRange; class DataLayout; class LLVMContext; +template class UnwindDestIterator; enum AtomicOrdering { NotAtomic = 0, @@ -3706,8 +3707,12 @@ void setNormalDest(BasicBlock *B) { Op<-2>() = reinterpret_cast(B); } - void setUnwindDest(BasicBlock *B) { - Op<-1>() = reinterpret_cast(B); + void setUnwindDest(BasicBlock *B) { Op<-1>() = reinterpret_cast(B); } + + template + iterator_range> + getTransitiveUnwindDests() const { + return UnwindDestIterator::range(getUnwindDest()); } /// getLandingPadInst - Get the landingpad instruction from the landing pad @@ -3915,6 +3920,12 @@ setOperand(1, UnwindDest); } + template + iterator_range> + getTransitiveUnwindDests() const { + return UnwindDestIterator::range(getUnwindDest()); + } + /// getNumHandlers - return the number of 'handlers' in this catchswitch /// instruction, except the default handler unsigned getNumHandlers() const { @@ -4242,6 +4253,12 @@ Op<1>() = NewDest; } + template + iterator_range> + getTransitiveUnwindDests() const { + return UnwindDestIterator::range(getUnwindDest()); + } + // Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const Instruction *I) { return (I->getOpcode() == Instruction::CleanupRet); @@ -4820,6 +4837,72 @@ } }; +// TODO: Figure out where this should live +template class UnwindDestIterator { +public: + BasicBlock *operator*() { return CurrentInstr->getParent(); } + UnwindDestIterator &operator++() { + if (CurrentHandler) { + CatchSwitchInst *CatchSwitch = + cast(CurrentInstr)->getCatchSwitch(); + if (++(*CurrentHandler) != CatchSwitch->handler_end()) { + CurrentInstr = (**CurrentHandler)->getFirstNonPHI(); + return *this; + } + CurrentHandler.reset(); + visitUnwindDest(CatchSwitch->getUnwindDest()); + return *this; + } + if (auto *CatchSwitch = dyn_cast(CurrentInstr)) { + visitFirstHandler(CatchSwitch); + return *this; + } + CurrentInstr = nullptr; + return *this; + } + bool operator==(const UnwindDestIterator &Other) const { + if (CurrentInstr != Other.CurrentInstr) + return false; + if (CurrentHandler.hasValue() != Other.CurrentHandler.hasValue()) + return false; + if (CurrentHandler && + (CurrentHandler.getValue() != Other.CurrentHandler.getValue())) + return false; + return true; + } + bool operator!=(const UnwindDestIterator &Other) const { + return !operator==(Other); + } + static iterator_range range(BasicBlock *UnwindDest) { + return iterator_range(UnwindDestIterator(UnwindDest), + UnwindDestIterator()); + } + +private: + explicit UnwindDestIterator() {} + explicit UnwindDestIterator(BasicBlock *UnwindDest) { + visitUnwindDest(UnwindDest); + } + Instruction *CurrentInstr = nullptr; + llvm::Optional CurrentHandler; + + void visitUnwindDest(BasicBlock *UnwindDest) { + assert(!CurrentHandler); + if (!UnwindDest) { + CurrentInstr = nullptr; + return; + } + CurrentInstr = UnwindDest->getFirstNonPHI(); + if (SkipUnsplittable) + if (auto *CatchSwitch = dyn_cast(CurrentInstr)) + visitFirstHandler(CatchSwitch); + } + void visitFirstHandler(CatchSwitchInst *CatchSwitch) { + CurrentHandler = CatchSwitch->handler_begin(); + CurrentInstr = (**CurrentHandler)->getFirstNonPHI(); + } +}; + } // End llvm namespace #endif Index: include/llvm/IR/Statepoint.h =================================================================== --- include/llvm/IR/Statepoint.h +++ include/llvm/IR/Statepoint.h @@ -330,6 +330,8 @@ // This takes care both of relocates for call statepoints and relocates // on normal path of invoke statepoint. if (!isa(Token)) { + assert(!cast(Token)->isEHPad() && + "Funclet pads don't support 1:1 relocate:statepoint mapping"); return cast(Token); } @@ -390,13 +392,21 @@ return Result; // We need to scan thorough exceptional relocations if it is invoke statepoint - LandingPadInst *LandingPad = - cast(getInstruction())->getLandingPadInst(); + const InvokeInst *Invoke = cast(getInstruction()); + + for (BasicBlock *UnwindDest : Invoke->getTransitiveUnwindDests()) { + if (!UnwindDest->isLandingPad()) { + assert(llvm::all_of(UnwindDest->users(), + [](User *U) { return !isa(U); }) && + "Relocates on funclet EH not supported"); + continue; + } - // Search for gc relocates that are attached to this landingpad. - for (const User *LandingPadUser : LandingPad->users()) { - if (auto *Relocate = dyn_cast(LandingPadUser)) - Result.push_back(Relocate); + // Search for gc relocates that are attached to this landingpad. + for (const User *LandingPadUser : UnwindDest->getFirstNonPHI()->users()) { + if (auto *Relocate = dyn_cast(LandingPadUser)) + Result.push_back(Relocate); + } } return Result; } Index: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -74,6 +74,11 @@ static cl::opt UseDeoptBundles("rs4gc-use-deopt-bundles", cl::Hidden, cl::init(false)); +static cl::opt SpillOnExceptionPath("rs4gc-spill-on-exception-path", + cl::Hidden, cl::init(false)); +static cl::opt SpillOnNormalPath("rs4gc-spill-on-normal-path", cl::Hidden, + cl::init(false)); + static cl::opt AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", cl::Hidden, cl::init(true)); @@ -174,7 +179,9 @@ typedef DenseMap DefiningValueMapTy; typedef DenseSet StatepointLiveSetTy; typedef DenseMap, AssertingVH> - RematerializedValueMapTy; + RematerializedValueMapTy; +typedef DenseMap SpillMapTy; +typedef std::set> FillSetTy; struct PartiallyConstructedSafepointRecord { /// The set of values known to be live across this safepoint @@ -195,6 +202,28 @@ /// They are not included into 'LiveSet' field. /// Maps rematerialized copy to it's original value. RematerializedValueMapTy RematerializedValues; + + /// Record which values get spilled, and which allocas they get + /// spilled to + SpillMapTy &SpillMap; + + /// Record fills where we spilled a live value instead of relocating. + RematerializedValueMapTy FillMap; + + /// Record which (EH pad, value) pairs we've inserted fills for + FillSetTy &FillSet; + + PartiallyConstructedSafepointRecord(SpillMapTy &SpillMap, FillSetTy &FillSet) + : SpillMap(SpillMap), FillSet(FillSet) {} +}; + +struct PartiallyConstructedSafepointRecordSet { + SmallVector Records; + SpillMapTy SpillMap; + FillSetTy FillSet; + + PartiallyConstructedSafepointRecordSet(size_t size) + : Records(size, PartiallyConstructedSafepointRecord(SpillMap, FillSet)) {} }; } @@ -1390,7 +1419,6 @@ Instruction *InsertBefore = CS.getInstruction(); IRBuilder<> Builder(InsertBefore); - ArrayRef GCArgs(LiveVariables); uint64_t StatepointID = 0xABCDEF00; uint32_t NumPatchBytes = 0; uint32_t Flags = uint32_t(StatepointFlags::None); @@ -1401,6 +1429,74 @@ Value *CallTarget = nullptr; + // Insert any necessary spills, and bulid up the GCArgs which consist of + // the LiveVariables and/or spill slots. + SpillMapTy &SpillMap = Result.SpillMap; + MapVector IncomingPHIValueMap; + ArrayRef GCArgs; + SmallVector ArgBacking; + if (SpillOnNormalPath || CS.isInvoke() && SpillOnExceptionPath) { + // We need to generate spill slots. + + // The spill slots will need to be appended to the GC args, so + // copy the LiveVariables into ArgBacking; + ArgBacking.append(LiveVariables.begin(), LiveVariables.end()); + + BasicBlock *CallBlock = InsertBefore->getParent(); + Function *F = CallBlock->getParent(); + BasicBlock *EntryBlock = &F->getEntryBlock(); + Instruction *AllocaInsertBefore = &EntryBlock->front(); + + for (Value *Var : LiveVariables) { + AllocaInst *&Alloca = SpillMap[Var]; + if (!Alloca) + Alloca = + new AllocaInst(Var->getType(), suffixed_name_or(Var, ".spill", ""), + AllocaInsertBefore); + ArgBacking.push_back(Alloca); + Builder.CreateStore(Var, Alloca); + } + + if (CS.isInvoke() && SpillOnExceptionPath) { + // We also need to spill the incoming values to any PHIs on the exception + // path + BasicBlock *Pred = CS.getParent(); + for (BasicBlock *UnwindDest : cast(CS.getInstruction()) + ->getTransitiveUnwindDests()) { + for (Instruction &I : *UnwindDest) { + auto *PHI = dyn_cast(&I); + if (!PHI) + break; + // Find/create the Alloca for this PHI + AllocaInst *&Alloca = SpillMap[PHI]; + if (!Alloca) + Alloca = new AllocaInst(PHI->getType(), + suffixed_name_or(PHI, ".spill", ""), + AllocaInsertBefore); + ArgBacking.push_back(Alloca); + // Find/create the value to store for this PHI + Value *IncomingValue = PHI->getIncomingValueForBlock(Pred); + // If the incoming value was itself a PHI we've walked over, + // recurse to that incoming value + auto MapIter = IncomingPHIValueMap.find(IncomingValue); + if (MapIter != IncomingPHIValueMap.end()) + IncomingValue = MapIter->second; + IncomingPHIValueMap[PHI] = IncomingValue; + // Store the value into the spill slot. + Builder.CreateStore(IncomingValue, Alloca); + } + // Update pred if we're going to visit this block's successors, + // which we'll do iff it's a catchswitch. + if (isa(UnwindDest->getFirstNonPHI())) + Pred = UnwindDest; + } + } + + GCArgs = ArrayRef(ArgBacking); + } else { + GCArgs = ArrayRef(LiveVariables); + } + if (UseDeoptBundles) { CallArgs = {CS.arg_begin(), CS.arg_end()}; DeoptArgs = GetDeoptBundleOperands(CS); @@ -1485,21 +1581,41 @@ Token = Invoke; // Generate gc relocates in exceptional path - BasicBlock *UnwindBlock = ToReplace->getUnwindDest(); - assert(!isa(UnwindBlock->begin()) && - UnwindBlock->getUniquePredecessor() && - "can't safely insert in this block!"); - - Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt()); - Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc()); - - // Attach exceptional gc relocates to the landingpad. - Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst(); - Result.UnwindToken = ExceptionalToken; + Result.UnwindToken = nullptr; + for (BasicBlock *UnwindBlock : ToReplace->getTransitiveUnwindDests()) { + Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt()); + Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc()); + + if (SpillOnExceptionPath) { + auto insertSpill = [&, UnwindBlock](Value *Var) { + AllocaInst *SpillSlot = SpillMap[Var]; + if (Result.FillSet.insert({UnwindBlock, SpillSlot}).second) { + LoadInst *Fill = Builder.CreateLoad( + SpillSlot, suffixed_name_or(Var, ".reload", "")); + Result.FillMap[Fill] = Var; + } + }; - const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx(); - CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, ExceptionalToken, - Builder); + for (Value *LiveVar : LiveVariables) + insertSpill(LiveVar); + for (auto &Pair : IncomingPHIValueMap) + insertSpill(Pair.first); + } else { + assert(!isa(UnwindBlock->begin()) && + UnwindBlock->getUniquePredecessor() && + "can't safely insert in this block!"); + + // Attach exceptional gc relocates to the landingpad. + Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst(); + assert(Result.UnwindToken == nullptr && + "Cannot report multiple unwind tokens"); + Result.UnwindToken = ExceptionalToken; + + const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx(); + CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, + ExceptionalToken, Builder); + } + } // Generate gc relocates and returns for normal block BasicBlock *NormalDest = ToReplace->getNormalDest(); @@ -1551,8 +1667,16 @@ Result.StatepointToken = Token; // Second, create a gc.relocate for every live variable - const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx(); - CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder); + if (SpillOnNormalPath) { + for (Value *LiveVar : LiveVariables) { + LoadInst *Fill = Builder.CreateLoad( + SpillMap[LiveVar], suffixed_name_or(LiveVar, ".reload", "")); + Result.FillMap[Fill] = LiveVar; + } + } else { + const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx(); + CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder); + } } namespace { @@ -1659,12 +1783,12 @@ } // Helper function for the "relocationViaAlloca". Similar to the -// "insertRelocationStores" but works for rematerialized values. -static void -insertRematerializationStores( - RematerializedValueMapTy RematerializedValues, - DenseMap &AllocaMap, - DenseSet &VisitedLiveValues) { +// "insertRelocationStores" but works for rematerialized values +// and reloads of spilled values. +static void insertRematerializationStores( + const RematerializedValueMapTy &RematerializedValues, + DenseMap &AllocaMap, + DenseSet &VisitedLiveValues) { for (auto RematerializedValuePair: RematerializedValues) { Instruction *RematerializedValue = RematerializedValuePair.first; @@ -1702,6 +1826,7 @@ SmallVector PromotableAllocas; // Used later to chack that we have enough allocas to store all values std::size_t NumRematerializedValues = 0; + std::size_t NumSpilledValues = 0; PromotableAllocas.reserve(Live.size()); // Emit alloca for "LiveValue" and record it in "allocaMap" and @@ -1718,7 +1843,7 @@ emitAllocaFor(V); // Emit allocas for rematerialized values - for (const auto &Info : Records) + for (const auto &Info : Records) { for (auto RematerializedValuePair : Info.RematerializedValues) { Value *OriginalValue = RematerializedValuePair.second; if (AllocaMap.count(OriginalValue) != 0) @@ -1727,6 +1852,15 @@ emitAllocaFor(OriginalValue); ++NumRematerializedValues; } + for (auto SpilledValuePair : Info.FillMap) { + Value *OriginalValue = SpilledValuePair.second; + if (AllocaMap.count(OriginalValue) != 0) + continue; + + emitAllocaFor(OriginalValue); + ++NumSpilledValues; + } + } // The next two loops are part of the same conceptual operation. We need to // insert a store to the alloca after the original def and at each @@ -1748,7 +1882,7 @@ // In case if it was invoke statepoint // we will insert stores for exceptional path gc relocates. - if (isa(Statepoint)) { + if (isa(Statepoint) && Info.UnwindToken) { insertRelocationStores(Info.UnwindToken->users(), AllocaMap, VisitedLiveValues); } @@ -1757,6 +1891,9 @@ insertRematerializationStores(Info.RematerializedValues, AllocaMap, VisitedLiveValues); + // And with reloads + insertRematerializationStores(Info.FillMap, AllocaMap, VisitedLiveValues); + if (ClobberNonLive) { // As a debugging aid, pretend that an unrelocated pointer becomes null at // the gc.statepoint. This will turn some subtle GC problems into @@ -1789,7 +1926,8 @@ // gc.results and gc.relocates, but that's fine. if (auto II = dyn_cast(Statepoint)) { InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt()); - InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt()); + for (BasicBlock *UnwindDest : II->getTransitiveUnwindDests()) + InsertClobbersAt(&*UnwindDest->getFirstInsertionPt()); } else { InsertClobbersAt(cast(Statepoint)->getNextNode()); } @@ -1860,7 +1998,8 @@ } } - assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues && + assert(PromotableAllocas.size() == + Live.size() + NumRematerializedValues + NumSpilledValues && "we must have the same allocas with lives"); if (!PromotableAllocas.empty()) { // Apply mem2reg to promote alloca to SSA @@ -1908,8 +2047,9 @@ auto *II = cast(CS.getInstruction()); Holders.push_back(CallInst::Create( Func, Values, "", &*II->getNormalDest()->getFirstInsertionPt())); - Holders.push_back(CallInst::Create( - Func, Values, "", &*II->getUnwindDest()->getFirstInsertionPt())); + for (BasicBlock *UnwindDest : II->getTransitiveUnwindDests()) + Holders.push_back(CallInst::Create(Func, Values, "", + &*UnwindDest->getFirstInsertionPt())); } static void findLiveReferences( @@ -2229,16 +2369,16 @@ Instruction *NormalInsertBefore = &*Invoke->getNormalDest()->getFirstInsertionPt(); - Instruction *UnwindInsertBefore = - &*Invoke->getUnwindDest()->getFirstInsertionPt(); - Instruction *NormalRematerializedValue = rematerializeChain(NormalInsertBefore); - Instruction *UnwindRematerializedValue = - rematerializeChain(UnwindInsertBefore); - Info.RematerializedValues[NormalRematerializedValue] = LiveValue; - Info.RematerializedValues[UnwindRematerializedValue] = LiveValue; + + for (BasicBlock *UnwindDest : Invoke->getTransitiveUnwindDests()) { + Instruction *UnwindInsertBefore = &*UnwindDest->getFirstInsertionPt(); + Instruction *UnwindRematerializedValue = + rematerializeChain(UnwindInsertBefore); + Info.RematerializedValues[UnwindRematerializedValue] = LiveValue; + } } } @@ -2266,14 +2406,16 @@ // When inserting gc.relocates for invokes, we need to be able to insert at // the top of the successor blocks. See the comment on - // normalForInvokeSafepoint on exactly what is needed. Note that this step + // normalizeForInvokeSafepoint on exactly what is needed. Note that this step // may restructure the CFG. for (CallSite CS : ToUpdate) { if (!CS.isInvoke()) continue; auto *II = cast(CS.getInstruction()); normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT); - normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT); + if (!SpillOnExceptionPath) + for (BasicBlock *UnwindDest : II->getTransitiveUnwindDests()) + normalizeForInvokeSafepoint(UnwindDest, II->getParent(), DT); } // A list of dummy calls added to the IR to keep various values obviously @@ -2302,7 +2444,9 @@ insertUseHolderAfter(CS, DeoptValues, Holders); } - SmallVector Records(ToUpdate.size()); + PartiallyConstructedSafepointRecordSet RecordSet(ToUpdate.size()); + MutableArrayRef Records = + RecordSet.Records; // A) Identify all gc pointers which are statically live at the given call // site. @@ -2474,11 +2618,11 @@ #ifndef NDEBUG // sanity check for (auto *Ptr : Live) - assert(isHandledGCPointerType(Ptr->getType()) && - "must be a gc pointer type"); +// TODO: repiar this: assert(isGCPointerType(Ptr->getType()) && "must be a gc +// pointer type"); #endif - relocationViaAlloca(F, DT, Live, Records); + relocationViaAlloca(F, DT, Live, Records); return !Records.empty(); }