74#define DEBUG_TYPE "code-extractor"
82 cl::desc(
"Aggregate arguments to code-extracted functions"));
87 bool AllowVarArgs,
bool AllowAlloca) {
100 while (!ToVisit.
empty()) {
102 if (!Visited.
insert(Curr).second)
104 if (isa<BlockAddress const>(Curr))
107 if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->
getParent() != &BB)
110 for (
auto const &U : Curr->
operands()) {
111 if (
auto *UU = dyn_cast<User>(U))
119 if (isa<AllocaInst>(
I)) {
125 if (
const auto *II = dyn_cast<InvokeInst>(
I)) {
128 if (
auto *UBB = II->getUnwindDest())
129 if (!Result.count(UBB))
136 if (
const auto *CSI = dyn_cast<CatchSwitchInst>(
I)) {
137 if (
auto *UBB = CSI->getUnwindDest())
138 if (!Result.count(UBB))
140 for (
const auto *HBB : CSI->handlers())
141 if (!Result.count(
const_cast<BasicBlock*
>(HBB)))
148 if (
const auto *CPI = dyn_cast<CatchPadInst>(
I)) {
149 for (
const auto *U : CPI->users())
150 if (
const auto *CRI = dyn_cast<CatchReturnInst>(U))
151 if (!Result.count(
const_cast<BasicBlock*
>(CRI->getParent())))
159 if (
const auto *CPI = dyn_cast<CleanupPadInst>(
I)) {
160 for (
const auto *U : CPI->users())
161 if (
const auto *CRI = dyn_cast<CleanupReturnInst>(U))
162 if (!Result.count(
const_cast<BasicBlock*
>(CRI->getParent())))
166 if (
const auto *CRI = dyn_cast<CleanupReturnInst>(
I)) {
167 if (
auto *UBB = CRI->getUnwindDest())
168 if (!Result.count(UBB))
173 if (
const CallInst *CI = dyn_cast<CallInst>(
I)) {
174 if (
const Function *
F = CI->getCalledFunction()) {
175 auto IID =
F->getIntrinsicID();
176 if (IID == Intrinsic::vastart) {
185 if (IID == Intrinsic::eh_typeid_for)
197 bool AllowVarArgs,
bool AllowAlloca) {
198 assert(!BBs.
empty() &&
"The set of blocks to extract must be non-empty");
208 if (!Result.insert(BB))
212 LLVM_DEBUG(
dbgs() <<
"Region front block: " << Result.front()->getName()
215 for (
auto *BB : Result) {
220 if (BB == Result.front()) {
222 LLVM_DEBUG(
dbgs() <<
"The first block cannot be an unwind block\n");
231 if (!Result.count(PBB)) {
232 LLVM_DEBUG(
dbgs() <<
"No blocks in this region may have entries from "
233 "outside the region except for the first block!\n"
234 <<
"Problematic source BB: " << BB->getName() <<
"\n"
235 <<
"Problematic destination BB: " << PBB->getName()
247 bool AllowVarArgs,
bool AllowAlloca,
248 BasicBlock *AllocationBlock, std::string Suffix)
250 BPI(BPI), AC(AC), AllocationBlock(AllocationBlock),
251 AllowVarArgs(AllowVarArgs),
260 BPI(BPI), AC(AC), AllocationBlock(nullptr), AllowVarArgs(
false),
270 if (
Blocks.count(
I->getParent()))
279 if (isa<Argument>(V))
return true;
281 if (!
Blocks.count(
I->getParent()))
293 if (!CommonExitBlock) {
294 CommonExitBlock = Succ;
297 if (CommonExitBlock != Succ)
306 return CommonExitBlock;
311 for (
Instruction &II : BB.instructionsWithoutDebug())
312 if (
auto *AI = dyn_cast<AllocaInst>(&II))
313 Allocas.push_back(AI);
315 findSideEffectInfoForBlock(BB);
319void CodeExtractorAnalysisCache::findSideEffectInfoForBlock(
BasicBlock &BB) {
321 unsigned Opcode = II.getOpcode();
322 Value *MemAddr =
nullptr;
324 case Instruction::Store:
325 case Instruction::Load: {
326 if (Opcode == Instruction::Store) {
328 MemAddr = SI->getPointerOperand();
334 if (isa<Constant>(MemAddr))
337 if (!isa<AllocaInst>(
Base)) {
338 SideEffectingBlocks.insert(&BB);
341 BaseMemAddrs[&BB].insert(
Base);
349 SideEffectingBlocks.insert(&BB);
353 if (II.mayHaveSideEffects()) {
354 SideEffectingBlocks.insert(&BB);
364 if (SideEffectingBlocks.count(&BB))
366 auto It = BaseMemAddrs.find(&BB);
367 if (It != BaseMemAddrs.end())
368 return It->second.count(
Addr);
374 AllocaInst *AI = cast<AllocaInst>(
Addr->stripInBoundsConstantOffsets());
377 if (Blocks.count(&BB))
387 BasicBlock *SinglePredFromOutlineRegion =
nullptr;
388 assert(!Blocks.count(CommonExitBlock) &&
389 "Expect a block outside the region!");
391 if (!Blocks.count(Pred))
393 if (!SinglePredFromOutlineRegion) {
394 SinglePredFromOutlineRegion = Pred;
395 }
else if (SinglePredFromOutlineRegion != Pred) {
396 SinglePredFromOutlineRegion =
nullptr;
401 if (SinglePredFromOutlineRegion)
402 return SinglePredFromOutlineRegion;
408 while (
I != BB->
end()) {
409 PHINode *Phi = dyn_cast<PHINode>(
I);
421 assert(!getFirstPHI(CommonExitBlock) &&
"Phi not expected");
429 if (Blocks.count(Pred))
434 Blocks.insert(CommonExitBlock);
435 OldTargets.push_back(NewExitBlock);
436 return CommonExitBlock;
443CodeExtractor::LifetimeMarkerInfo
447 LifetimeMarkerInfo
Info;
457 Info.LifeStart = IntrInst;
463 Info.LifeEnd = IntrInst;
468 if (isa<DbgInfoIntrinsic>(IntrInst))
476 if (!
Info.LifeStart || !
Info.LifeEnd)
482 if ((
Info.SinkLifeStart ||
Info.HoistLifeEnd) &&
487 if (
Info.HoistLifeEnd && !ExitBlock)
499 auto moveOrIgnoreLifetimeMarkers =
500 [&](
const LifetimeMarkerInfo &LMI) ->
bool {
503 if (LMI.SinkLifeStart) {
506 SinkCands.
insert(LMI.LifeStart);
508 if (LMI.HoistLifeEnd) {
509 LLVM_DEBUG(
dbgs() <<
"Hoisting lifetime.end: " << *LMI.LifeEnd <<
"\n");
510 HoistCands.
insert(LMI.LifeEnd);
519 if (Blocks.count(BB))
528 LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(CEAC, AI, ExitBlock);
529 bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo);
541 for (
User *U : AI->users()) {
545 if (U->stripInBoundsConstantOffsets() != AI)
549 for (
User *BU : Bitcast->users()) {
561 << *Bitcast <<
" in out-of-region lifetime marker "
562 << *IntrInst <<
"\n");
563 LifetimeBitcastUsers.
push_back(IntrInst);
573 I->replaceUsesOfWith(
I->getOperand(1), CastI);
579 for (
User *U : AI->users()) {
580 if (U->stripInBoundsConstantOffsets() == AI) {
582 LifetimeMarkerInfo LMI = getLifetimeMarkers(CEAC, Bitcast, ExitBlock);
598 if (Bitcasts.
empty())
601 LLVM_DEBUG(
dbgs() <<
"Sinking alloca (via bitcast): " << *AI <<
"\n");
603 for (
unsigned I = 0,
E = Bitcasts.
size();
I !=
E; ++
I) {
605 const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[
I];
607 "Unsafe to sink bitcast without lifetime markers");
608 moveOrIgnoreLifetimeMarkers(LMI);
610 LLVM_DEBUG(
dbgs() <<
"Sinking bitcast-of-alloca: " << *BitcastAddr
612 SinkCands.
insert(BitcastAddr);
626 if (AllowVarArgs &&
F->getFunctionType()->isVarArg()) {
627 auto containsVarArgIntrinsic = [](
const Instruction &
I) {
628 if (
const CallInst *CI = dyn_cast<CallInst>(&
I))
629 if (
const Function *Callee = CI->getCalledFunction())
630 return Callee->getIntrinsicID() == Intrinsic::vastart ||
631 Callee->getIntrinsicID() == Intrinsic::vaend;
635 for (
auto &BB : *
F) {
636 if (Blocks.count(&BB))
651 for (
auto &OI : II.operands()) {
657 for (
User *U : II.users())
669void CodeExtractor::severSplitPHINodesOfEntry(
BasicBlock *&Header) {
670 unsigned NumPredsFromRegion = 0;
671 unsigned NumPredsOutsideRegion = 0;
673 if (Header != &Header->getParent()->getEntryBlock()) {
674 PHINode *PN = dyn_cast<PHINode>(Header->begin());
682 ++NumPredsFromRegion;
684 ++NumPredsOutsideRegion;
688 if (NumPredsOutsideRegion <= 1)
return;
700 Blocks.remove(OldPred);
701 Blocks.insert(NewBB);
706 if (NumPredsFromRegion) {
719 for (AfterPHIs = OldPred->
begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
720 PHINode *PN = cast<PHINode>(AfterPHIs);
746void CodeExtractor::severSplitPHINodesOfExits(
751 for (
PHINode &PN : ExitBB->phis()) {
761 if (IncomingVals.
size() <= 1)
768 ExitBB->getName() +
".split",
769 ExitBB->getParent(), ExitBB);
772 if (Blocks.count(PredBB))
773 PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
775 Blocks.insert(NewBB);
782 for (
unsigned i : IncomingVals)
784 for (
unsigned i :
reverse(IncomingVals))
791void CodeExtractor::splitReturnBlocks() {
795 Block->splitBasicBlock(RI->getIterator(),
Block->getName() +
".ret");
813Function *CodeExtractor::constructFunction(
const ValueSet &inputs,
814 const ValueSet &outputs,
824 switch (NumExitBlocks) {
831 std::vector<Type *> ParamTy;
832 std::vector<Type *> AggParamTy;
833 ValueSet StructValues;
839 if (AggregateArgs && !ExcludeArgsFromAggregate.
contains(
value)) {
840 AggParamTy.push_back(
value->getType());
841 StructValues.insert(
value);
843 ParamTy.push_back(
value->getType());
847 for (
Value *output : outputs) {
849 if (AggregateArgs && !ExcludeArgsFromAggregate.
contains(output)) {
850 AggParamTy.push_back(output->getType());
851 StructValues.insert(output);
858 (ParamTy.size() + AggParamTy.size()) ==
859 (inputs.size() + outputs.size()) &&
860 "Number of scalar and aggregate params does not match inputs, outputs");
861 assert((StructValues.empty() || AggregateArgs) &&
862 "Expeced StructValues only with AggregateArgs set");
865 size_t NumScalarParams = ParamTy.size();
867 if (AggregateArgs && !AggParamTy.empty()) {
873 dbgs() <<
"Function type: " << *RetTy <<
" f(";
874 for (
Type *i : ParamTy)
875 dbgs() << *i <<
", ";
880 RetTy, ParamTy, AllowVarArgs && oldFunction->
isVarArg());
882 std::string SuffixToUse =
889 oldFunction->
getName() +
"." + SuffixToUse, M);
899 if (Attr.isStringAttribute()) {
900 if (Attr.getKindAsString() ==
"thunk")
903 switch (Attr.getKindAsEnum()) {
906 case Attribute::AllocSize:
907 case Attribute::Builtin:
908 case Attribute::Convergent:
909 case Attribute::JumpTable:
910 case Attribute::Naked:
911 case Attribute::NoBuiltin:
912 case Attribute::NoMerge:
913 case Attribute::NoReturn:
914 case Attribute::NoSync:
915 case Attribute::ReturnsTwice:
916 case Attribute::Speculatable:
917 case Attribute::StackAlignment:
918 case Attribute::WillReturn:
919 case Attribute::AllocKind:
920 case Attribute::PresplitCoroutine:
921 case Attribute::Memory:
922 case Attribute::NoFPClass:
925 case Attribute::AlwaysInline:
926 case Attribute::Cold:
927 case Attribute::DisableSanitizerInstrumentation:
928 case Attribute::FnRetThunkExtern:
930 case Attribute::NoRecurse:
931 case Attribute::InlineHint:
932 case Attribute::MinSize:
933 case Attribute::NoCallback:
934 case Attribute::NoDuplicate:
935 case Attribute::NoFree:
936 case Attribute::NoImplicitFloat:
937 case Attribute::NoInline:
938 case Attribute::NonLazyBind:
939 case Attribute::NoRedZone:
940 case Attribute::NoUnwind:
941 case Attribute::NoSanitizeBounds:
942 case Attribute::NoSanitizeCoverage:
943 case Attribute::NullPointerIsValid:
944 case Attribute::OptForFuzzing:
945 case Attribute::OptimizeNone:
946 case Attribute::OptimizeForSize:
947 case Attribute::SafeStack:
948 case Attribute::ShadowCallStack:
949 case Attribute::SanitizeAddress:
950 case Attribute::SanitizeMemory:
951 case Attribute::SanitizeThread:
952 case Attribute::SanitizeHWAddress:
953 case Attribute::SanitizeMemTag:
954 case Attribute::SpeculativeLoadHardening:
955 case Attribute::StackProtect:
956 case Attribute::StackProtectReq:
957 case Attribute::StackProtectStrong:
958 case Attribute::StrictFP:
959 case Attribute::UWTable:
960 case Attribute::VScaleRange:
961 case Attribute::NoCfCheck:
962 case Attribute::MustProgress:
963 case Attribute::NoProfile:
964 case Attribute::SkipProfile:
967 case Attribute::Alignment:
968 case Attribute::AllocatedPointer:
969 case Attribute::AllocAlign:
970 case Attribute::ByVal:
971 case Attribute::Dereferenceable:
972 case Attribute::DereferenceableOrNull:
973 case Attribute::ElementType:
974 case Attribute::InAlloca:
975 case Attribute::InReg:
976 case Attribute::Nest:
977 case Attribute::NoAlias:
978 case Attribute::NoCapture:
979 case Attribute::NoUndef:
980 case Attribute::NonNull:
981 case Attribute::Preallocated:
982 case Attribute::ReadNone:
983 case Attribute::ReadOnly:
984 case Attribute::Returned:
985 case Attribute::SExt:
986 case Attribute::StructRet:
987 case Attribute::SwiftError:
988 case Attribute::SwiftSelf:
989 case Attribute::SwiftAsync:
990 case Attribute::ZExt:
991 case Attribute::ImmArg:
992 case Attribute::ByRef:
993 case Attribute::WriteOnly:
1004 newFunction->
insert(newFunction->
end(), newRootNode);
1013 for (
unsigned i = 0, e = inputs.size(), aggIdx = 0; i != e; ++i) {
1015 if (AggregateArgs && StructValues.contains(inputs[i])) {
1021 StructTy, &*AggAI,
Idx,
"gep_" + inputs[i]->
getName(), TI);
1023 "loadgep_" + inputs[i]->getName(), TI);
1026 RewriteVal = &*ScalarAI++;
1028 std::vector<User *>
Users(inputs[i]->user_begin(), inputs[i]->user_end());
1031 if (
Blocks.count(inst->getParent()))
1032 inst->replaceUsesOfWith(inputs[i], RewriteVal);
1036 if (NumScalarParams) {
1038 for (
unsigned i = 0, e = inputs.size(); i != e; ++i, ++ScalarAI)
1039 if (!StructValues.contains(inputs[i]))
1041 for (
unsigned i = 0, e = outputs.size(); i != e; ++i, ++ScalarAI)
1042 if (!StructValues.contains(outputs[i]))
1050 for (
auto &U :
Users)
1054 if (
I->isTerminator() &&
I->getFunction() == oldFunction &&
1055 !
Blocks.count(
I->getParent()))
1056 I->replaceUsesOfWith(header, newHeader);
1072 auto *II = dyn_cast<IntrinsicInst>(&
I);
1073 if (!II || !II->isLifetimeStartOrEnd())
1083 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1084 LifetimesStart.
insert(Mem);
1085 II->eraseFromParent();
1102 bool InsertBefore) {
1103 for (
Value *Mem : Objects) {
1106 "Input memory not defined in original function");
1113 Marker->insertBefore(Term);
1117 if (!LifetimesStart.
empty()) {
1118 insertMarkers(Intrinsic::lifetime_start, LifetimesStart,
1122 if (!LifetimesEnd.
empty()) {
1123 insertMarkers(Intrinsic::lifetime_end, LifetimesEnd,
1134 ValueSet &outputs) {
1137 std::vector<Value *> params, ReloadOutputs, Reloads;
1138 ValueSet StructValues;
1146 unsigned ScalarInputArgNo = 0;
1148 for (
Value *input : inputs) {
1149 if (AggregateArgs && !ExcludeArgsFromAggregate.
contains(input))
1150 StructValues.
insert(input);
1152 params.push_back(input);
1153 if (input->isSwiftError())
1154 SwiftErrorArgs.
push_back(ScalarInputArgNo);
1160 unsigned ScalarOutputArgNo = 0;
1161 for (
Value *output : outputs) {
1162 if (AggregateArgs && !ExcludeArgsFromAggregate.
contains(output)) {
1163 StructValues.insert(output);
1166 new AllocaInst(output->getType(),
DL.getAllocaAddrSpace(),
1167 nullptr, output->
getName() +
".loc",
1169 ReloadOutputs.push_back(alloca);
1170 params.push_back(alloca);
1171 ++ScalarOutputArgNo;
1177 unsigned NumAggregatedInputs = 0;
1178 if (AggregateArgs && !StructValues.empty()) {
1179 std::vector<Type *> ArgTypes;
1180 for (
Value *V : StructValues)
1181 ArgTypes.push_back(
V->getType());
1186 StructArgTy,
DL.getAllocaAddrSpace(),
nullptr,
"structArg",
1189 params.push_back(
Struct);
1192 for (
unsigned i = 0, e = StructValues.size(); i != e; ++i) {
1193 if (inputs.contains(StructValues[i])) {
1199 GEP->insertInto(codeReplacer, codeReplacer->
end());
1201 NumAggregatedInputs++;
1208 NumExitBlocks > 1 ?
"targetBlock" :
"");
1220 for (
unsigned SwiftErrArgNo : SwiftErrorArgs) {
1221 call->
addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1222 newFunction->
addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1227 for (
unsigned i = 0, e = outputs.size(), scalarIdx = 0,
1228 aggIdx = NumAggregatedInputs;
1230 Value *Output =
nullptr;
1231 if (AggregateArgs && StructValues.contains(outputs[i])) {
1237 GEP->insertInto(codeReplacer, codeReplacer->
end());
1241 Output = ReloadOutputs[scalarIdx];
1245 outputs[i]->
getName() +
".reload",
1247 Reloads.push_back(load);
1248 std::vector<User *>
Users(outputs[i]->user_begin(), outputs[i]->user_end());
1259 codeReplacer, 0, codeReplacer);
1266 std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1270 unsigned switchVal = 0;
1272 if (
Blocks.count(OldTarget))
1274 BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1281 OldTarget->getName() +
".exitStub",
1283 unsigned SuccNum = switchVal++;
1285 Value *brVal =
nullptr;
1286 assert(NumExitBlocks < 0xffff &&
"too many exit blocks for switch");
1287 switch (NumExitBlocks) {
1313 BasicBlock *NewTarget = ExitBlockMap[OldTarget];
1314 assert(NewTarget &&
"Unknown target block!");
1325 std::advance(ScalarOutputArgBegin, ScalarInputArgNo);
1327 std::advance(AggOutputArgBegin, ScalarInputArgNo + ScalarOutputArgNo);
1329 for (
unsigned i = 0, e = outputs.size(), aggIdx = NumAggregatedInputs; i != e;
1331 auto *OutI = dyn_cast<Instruction>(outputs[i]);
1339 if (
auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1340 InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1341 else if (
auto *Phi = dyn_cast<PHINode>(OutI))
1342 InsertPt =
Phi->getParent()->getFirstInsertionPt();
1344 InsertPt = std::next(OutI->getIterator());
1349 "InsertPt should be in new function");
1350 if (AggregateArgs && StructValues.contains(outputs[i])) {
1352 "Number of aggregate output arguments should match "
1353 "the number of defined values");
1358 StructArgTy, &*AggOutputArgBegin,
Idx,
"gep_" + outputs[i]->
getName(),
1367 "Number of scalar output arguments should match "
1368 "the number of defined values");
1369 new StoreInst(outputs[i], &*ScalarOutputArgBegin, InsertBefore);
1370 ++ScalarOutputArgBegin;
1376 switch (NumExitBlocks) {
1425void CodeExtractor::moveCodeToFunction(
Function *newFunction) {
1429 Block->removeFromParent();
1436 newFuncIt = newFunction->
insert(std::next(newFuncIt),
Block);
1440void CodeExtractor::calculateNewCallTerminatorWeights(
1452 Distribution BranchDist;
1459 BlockNode ExitNode(i);
1462 BranchDist.addExit(ExitNode, ExitFreq);
1468 if (BranchDist.Total == 0) {
1474 BranchDist.normalize();
1477 for (
unsigned I = 0,
E = BranchDist.Weights.size();
I <
E; ++
I) {
1478 const auto &Weight = BranchDist.Weights[
I];
1481 BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1483 EdgeProbabilities[Weight.TargetNode.Index] = BP;
1487 LLVMContext::MD_prof,
1498 if (DVI->getFunction() != &
F)
1499 DVI->eraseFromParent();
1522 assert(OldSP->getUnit() &&
"Missing compile unit for subprogram");
1528 DISubprogram::SPFlagOptimized |
1529 DISubprogram::SPFlagLocalToUnit;
1532 0, SPType, 0, DINode::FlagZero, SPFlags);
1545 auto *DII = dyn_cast<DbgInfoIntrinsic>(&
I);
1551 if (
auto *DLI = dyn_cast<DbgLabelInst>(&
I)) {
1552 if (DLI->getDebugLoc().getInlinedAt())
1554 DILabel *OldLabel = DLI->getLabel();
1555 DINode *&NewLabel = RemappedMetadata[OldLabel];
1558 *OldLabel->
getScope(), *NewSP, Ctx, Cache);
1566 auto IsInvalidLocation = [&NewFunc](
Value *Location) {
1570 (!isa<Constant>(Location) && !isa<Instruction>(Location)))
1572 Instruction *LocationInst = dyn_cast<Instruction>(Location);
1573 return LocationInst && LocationInst->
getFunction() != &NewFunc;
1576 auto *DVI = cast<DbgVariableIntrinsic>(DII);
1578 if (
any_of(DVI->location_ops(), IsInvalidLocation)) {
1584 if (!DVI->getDebugLoc().getInlinedAt()) {
1586 DINode *&NewVar = RemappedMetadata[OldVar];
1589 *OldVar->
getScope(), *NewSP, Ctx, Cache);
1592 OldVar->
getType(),
false, DINode::FlagZero,
1595 DVI->setVariable(cast<DILocalVariable>(NewVar));
1599 for (
auto *DII : DebugIntrinsicsToDelete)
1600 DII->eraseFromParent();
1611 auto updateLoopInfoLoc = [&Ctx, &Cache, NewSP](
Metadata *MD) ->
Metadata * {
1612 if (
auto *Loc = dyn_cast_or_null<DILocation>(MD))
1645 assert(BPI &&
"Both BPI and BFI are required to preserve profile info");
1658 if (
auto *AI = dyn_cast<AssumeInst>(&
I)) {
1661 AI->eraseFromParent();
1668 splitReturnBlocks();
1676 if (!
Blocks.count(Succ)) {
1686 NumExitBlocks = ExitBlocks.
size();
1694 OldTargets.push_back(OldTarget);
1699 severSplitPHINodesOfEntry(header);
1700 severSplitPHINodesOfExits(ExitBlocks);
1704 "codeRepl", oldFunction,
1719 if (!
I.getDebugLoc())
1721 BranchI->setDebugLoc(
I.getDebugLoc());
1726 BranchI->insertInto(newFuncRoot, newFuncRoot->
end());
1728 ValueSet SinkingCands, HoistingCands;
1730 findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1740 for (
auto *II : SinkingCands) {
1741 if (
auto *AI = dyn_cast<AllocaInst>(II)) {
1743 if (!FirstSunkAlloca)
1744 FirstSunkAlloca = AI;
1747 assert((SinkingCands.
empty() || FirstSunkAlloca) &&
1748 "Did not expect a sink candidate without any allocas");
1749 for (
auto *II : SinkingCands) {
1750 if (!isa<AllocaInst>(II)) {
1751 cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1755 if (!HoistingCands.
empty()) {
1758 for (
auto *II : HoistingCands)
1771 constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1784 emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1786 moveCodeToFunction(newFunction);
1798 if (BFI && NumExitBlocks > 1)
1799 calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1811 for (
PHINode &PN : ExitBB->phis()) {
1812 Value *IncomingCodeReplacerVal =
nullptr;
1819 if (!IncomingCodeReplacerVal) {
1824 "PHI has two incompatbile incoming values from codeRepl");
1835 return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1841 newFunction->
dump();
1855 auto *
I = dyn_cast_or_null<CallInst>(AssumeVH);
1860 if (
I->getFunction() != &OldFunc)
1867 auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1870 if (AffectedCI->getFunction() != &OldFunc)
1872 auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));
1873 if (AssumedInst->getFunction() != &OldFunc)
1881 ExcludeArgsFromAggregate.
insert(Arg);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Given that RA is a live value
This file defines the DenseMap class.
DenseMap< Block *, BlockRelaxAux > Blocks
static Function * getFunction(Constant *C)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
Select target instructions out of generic instructions
Move duplicate certain instructions close to their use
Module.h This file contains the declarations for the Module class.
static StringRef getName(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static SymbolRef::Type getType(const Symbol *Sym)
an instruction to allocate memory on the stack
This class represents an incoming formal argument to a Function.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool empty() const
empty - Check if the array is empty.
A cache of @llvm.assume calls within a function.
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
void unregisterAssumption(AssumeInst *CI)
Remove an @llvm.assume intrinsic from this function's cache if it has been added to the cache earlier...
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
AttributeSet getFnAttrs() const
The function attributes are returned.
@ TombstoneKey
Use as Tombstone key for DenseMap of AttrKind.
@ None
No attributes have been set.
@ EmptyKey
Use as Empty key for DenseMap of AttrKind.
@ EndAttrKinds
Sentinal value useful for loops.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
InstListType::const_iterator getFirstNonPHIIt() const
Iterator returning form of getFirstNonPHI.
InstListType::const_iterator const_iterator
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
void setBlockFreq(const BasicBlock *BB, uint64_t Freq)
std::optional< uint64_t > getProfileCountFromFreq(uint64_t Freq) const
Returns the estimated profile count of Freq.
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Analysis providing branch probability information.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
static BranchProbability getUnknown()
static BranchProbability getZero()
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Adds the attribute to the indicated argument.
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
This is the base class for all instructions that perform data casts.
static CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast AddrSpaceCast, or a PtrToInt cast instruction.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
DISubroutineType * createSubroutineType(DITypeRefArray ParameterTypes, DINode::DIFlags Flags=DINode::FlagZero, unsigned CC=0)
Create subroutine type.
void finalizeSubprogram(DISubprogram *SP)
Finalize a specific subprogram - no new variables may be added to this subprogram afterwards.
DISubprogram * createFunction(DIScope *Scope, StringRef Name, StringRef LinkageName, DIFile *File, unsigned LineNo, DISubroutineType *Ty, unsigned ScopeLine, DINode::DIFlags Flags=DINode::FlagZero, DISubprogram::DISPFlags SPFlags=DISubprogram::SPFlagZero, DITemplateParameterArray TParams=nullptr, DISubprogram *Decl=nullptr, DITypeArray ThrownTypes=nullptr, DINodeArray Annotations=nullptr, StringRef TargetFuncName="")
Create a new descriptor for the specified subprogram.
DITypeRefArray getOrCreateTypeArray(ArrayRef< Metadata * > Elements)
Get a DITypeRefArray, create one if required.
DILocalVariable * createAutoVariable(DIScope *Scope, StringRef Name, DIFile *File, unsigned LineNo, DIType *Ty, bool AlwaysPreserve=false, DINode::DIFlags Flags=DINode::FlagZero, uint32_t AlignInBits=0)
Create a new descriptor for an auto variable.
StringRef getName() const
DILocalScope * getScope() const
Get the local scope for this label.
static DILocalScope * cloneScopeForSubprogram(DILocalScope &RootScope, DISubprogram &NewSP, LLVMContext &Ctx, DenseMap< const MDNode *, MDNode * > &Cache)
Traverses the scope chain rooted at RootScope until it hits a Subprogram, recreating the chain with "...
DILocalScope * getScope() const
Get the local scope for this variable.
Tagged DWARF-like metadata node.
DISPFlags
Debug info subprogram flags.
uint32_t getAlignInBits() const
StringRef getName() const
A parsed version of the target data layout string in and methods for querying it.
This is the common base class for debug info intrinsics for variables.
static DebugLoc replaceInlinedAtSubprogram(const DebugLoc &DL, DISubprogram &NewSP, LLVMContext &Ctx, DenseMap< const MDNode *, MDNode * > &Cache)
Rebuild the entire inline-at chain by replacing the subprogram at the end of the chain with NewSP.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Class to represent profile counts.
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
const BasicBlock & getEntryBlock() const
const BasicBlock & front() const
DISubprogram * getSubprogram() const
Get the attached subprogram.
bool hasPersonalityFn() const
Check whether this function has a personality function.
Constant * getPersonalityFn() const
Get the personality function associated with this function.
void setPersonalityFn(Constant *Fn)
AttributeList getAttributes() const
Return the attribute list for this Function.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
adds the attribute to the list of attributes for the given arg.
Function::iterator insert(Function::iterator Position, BasicBlock *BB)
Insert BB in the basic block list at Position.
Type * getReturnType() const
Returns the type of the ret val.
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
unsigned getAddressSpace() const
Module * getParent()
Get the module that this global value is contained inside of...
@ InternalLinkage
Rename collisions when linking (static functions).
bool isLifetimeStartOrEnd() const LLVM_READONLY
Return true if the instruction is a llvm.lifetime.start or llvm.lifetime.end marker.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const BasicBlock * getParent() const
const Function * getFunction() const
Return the function this instruction belongs to.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
SymbolTableList< Instruction >::iterator insertInto(BasicBlock *ParentBB, SymbolTableList< Instruction >::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
Value * getPointerOperand()
Represents a single loop in the control flow graph.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void setIncomingBlock(unsigned i, BasicBlock *BB)
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
Return a value (possibly void), from a function.
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
A vector that has set insertion semantics.
ArrayRef< value_type > getArrayRef() const
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
std::string str() const
str - Get the contents as an std::string.
constexpr bool empty() const
empty - Check if the string is empty.
Class to represent struct types.
static StructType * get(LLVMContext &Context, ArrayRef< Type * > Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
Type * getElementType(unsigned N) const
BasicBlock * getSuccessor(unsigned idx) const
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
void setCondition(Value *V)
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
void setDefaultDest(BasicBlock *DefaultCase)
Value * getCondition() const
CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
The instances of the Type class are immutable: once they are created, they are never changed.
static IntegerType * getInt1Ty(LLVMContext &C)
static Type * getVoidTy(LLVMContext &C)
static IntegerType * getInt16Ty(LLVMContext &C)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
static IntegerType * getInt32Ty(LLVMContext &C)
static IntegerType * getInt64Ty(LLVMContext &C)
bool isVoidTy() const
Return true if this is 'void'.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
void setName(const Twine &Name)
Change the name of the value.
const Value * stripInBoundsConstantOffsets() const
Strip off pointer casts and all-constant inbounds GEPs.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
LLVMContext & getContext() const
All values hold a context through their type.
StringRef getName() const
Return a constant reference to the value's name.
void dump() const
Support for debugging, callable in GDB: V->dump()
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
NodeAddr< PhiNode * > Phi
This is an optimization pass for GlobalISel generic memory operations.
bool stripDebugInfo(Function &F)
Function::ProfileCount ProfileCount
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto predecessors(const MachineBasicBlock *BB)
void updateLoopMetadataDebugLocations(Instruction &I, function_ref< Metadata *(Metadata *)> Updater)
Update the debug locations contained within the MD_loop metadata attached to the instruction I,...
Representative of a block.
Distribution of unscaled probability weight.