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))
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);
745void CodeExtractor::severSplitPHINodesOfExits(
750 for (
PHINode &PN : ExitBB->phis()) {
760 if (IncomingVals.
size() <= 1)
767 ExitBB->getName() +
".split",
768 ExitBB->getParent(), ExitBB);
771 if (Blocks.count(PredBB))
772 PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
774 Blocks.insert(NewBB);
781 for (
unsigned i : IncomingVals)
783 for (
unsigned i :
reverse(IncomingVals))
790void CodeExtractor::splitReturnBlocks() {
794 Block->splitBasicBlock(RI->getIterator(),
Block->getName() +
".ret");
812Function *CodeExtractor::constructFunction(
const ValueSet &inputs,
813 const ValueSet &outputs,
823 switch (NumExitBlocks) {
830 std::vector<Type *> ParamTy;
831 std::vector<Type *> AggParamTy;
832 ValueSet StructValues;
838 if (AggregateArgs && !ExcludeArgsFromAggregate.
contains(
value)) {
839 AggParamTy.push_back(
value->getType());
840 StructValues.insert(
value);
842 ParamTy.push_back(
value->getType());
846 for (
Value *output : outputs) {
848 if (AggregateArgs && !ExcludeArgsFromAggregate.
contains(output)) {
849 AggParamTy.push_back(output->getType());
850 StructValues.insert(output);
857 (ParamTy.size() + AggParamTy.size()) ==
858 (inputs.size() + outputs.size()) &&
859 "Number of scalar and aggregate params does not match inputs, outputs");
860 assert((StructValues.empty() || AggregateArgs) &&
861 "Expeced StructValues only with AggregateArgs set");
864 size_t NumScalarParams = ParamTy.size();
866 if (AggregateArgs && !AggParamTy.empty()) {
872 dbgs() <<
"Function type: " << *RetTy <<
" f(";
873 for (
Type *i : ParamTy)
874 dbgs() << *i <<
", ";
879 RetTy, ParamTy, AllowVarArgs && oldFunction->
isVarArg());
881 std::string SuffixToUse =
888 oldFunction->
getName() +
"." + SuffixToUse, M);
898 if (Attr.isStringAttribute()) {
899 if (Attr.getKindAsString() ==
"thunk")
902 switch (Attr.getKindAsEnum()) {
905 case Attribute::AllocSize:
906 case Attribute::Builtin:
907 case Attribute::Convergent:
908 case Attribute::JumpTable:
909 case Attribute::Naked:
910 case Attribute::NoBuiltin:
911 case Attribute::NoMerge:
912 case Attribute::NoReturn:
913 case Attribute::NoSync:
914 case Attribute::ReturnsTwice:
915 case Attribute::Speculatable:
916 case Attribute::StackAlignment:
917 case Attribute::WillReturn:
918 case Attribute::AllocKind:
919 case Attribute::PresplitCoroutine:
920 case Attribute::Memory:
921 case Attribute::NoFPClass:
924 case Attribute::AlwaysInline:
925 case Attribute::Cold:
926 case Attribute::DisableSanitizerInstrumentation:
927 case Attribute::FnRetThunkExtern:
929 case Attribute::NoRecurse:
930 case Attribute::InlineHint:
931 case Attribute::MinSize:
932 case Attribute::NoCallback:
933 case Attribute::NoDuplicate:
934 case Attribute::NoFree:
935 case Attribute::NoImplicitFloat:
936 case Attribute::NoInline:
937 case Attribute::NonLazyBind:
938 case Attribute::NoRedZone:
939 case Attribute::NoUnwind:
940 case Attribute::NoSanitizeBounds:
941 case Attribute::NoSanitizeCoverage:
942 case Attribute::NullPointerIsValid:
943 case Attribute::OptForFuzzing:
944 case Attribute::OptimizeNone:
945 case Attribute::OptimizeForSize:
946 case Attribute::SafeStack:
947 case Attribute::ShadowCallStack:
948 case Attribute::SanitizeAddress:
949 case Attribute::SanitizeMemory:
950 case Attribute::SanitizeThread:
951 case Attribute::SanitizeHWAddress:
952 case Attribute::SanitizeMemTag:
953 case Attribute::SpeculativeLoadHardening:
954 case Attribute::StackProtect:
955 case Attribute::StackProtectReq:
956 case Attribute::StackProtectStrong:
957 case Attribute::StrictFP:
958 case Attribute::UWTable:
959 case Attribute::VScaleRange:
960 case Attribute::NoCfCheck:
961 case Attribute::MustProgress:
962 case Attribute::NoProfile:
963 case Attribute::SkipProfile:
966 case Attribute::Alignment:
967 case Attribute::AllocatedPointer:
968 case Attribute::AllocAlign:
969 case Attribute::ByVal:
970 case Attribute::Dereferenceable:
971 case Attribute::DereferenceableOrNull:
972 case Attribute::ElementType:
973 case Attribute::InAlloca:
974 case Attribute::InReg:
975 case Attribute::Nest:
976 case Attribute::NoAlias:
977 case Attribute::NoCapture:
978 case Attribute::NoUndef:
979 case Attribute::NonNull:
980 case Attribute::Preallocated:
981 case Attribute::ReadNone:
982 case Attribute::ReadOnly:
983 case Attribute::Returned:
984 case Attribute::SExt:
985 case Attribute::StructRet:
986 case Attribute::SwiftError:
987 case Attribute::SwiftSelf:
988 case Attribute::SwiftAsync:
989 case Attribute::ZExt:
990 case Attribute::ImmArg:
991 case Attribute::ByRef:
992 case Attribute::WriteOnly:
1003 newFunction->
insert(newFunction->
end(), newRootNode);
1012 for (
unsigned i = 0, e = inputs.size(), aggIdx = 0; i != e; ++i) {
1014 if (AggregateArgs && StructValues.contains(inputs[i])) {
1020 StructTy, &*AggAI,
Idx,
"gep_" + inputs[i]->
getName(), TI);
1022 "loadgep_" + inputs[i]->getName(), TI);
1025 RewriteVal = &*ScalarAI++;
1027 std::vector<User *>
Users(inputs[i]->user_begin(), inputs[i]->user_end());
1030 if (
Blocks.count(inst->getParent()))
1031 inst->replaceUsesOfWith(inputs[i], RewriteVal);
1035 if (NumScalarParams) {
1037 for (
unsigned i = 0, e = inputs.size(); i != e; ++i, ++ScalarAI)
1038 if (!StructValues.contains(inputs[i]))
1040 for (
unsigned i = 0, e = outputs.size(); i != e; ++i, ++ScalarAI)
1041 if (!StructValues.contains(outputs[i]))
1049 for (
auto &U :
Users)
1053 if (
I->isTerminator() &&
I->getFunction() == oldFunction &&
1054 !
Blocks.count(
I->getParent()))
1055 I->replaceUsesOfWith(header, newHeader);
1071 auto *II = dyn_cast<IntrinsicInst>(&
I);
1072 if (!II || !II->isLifetimeStartOrEnd())
1082 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1083 LifetimesStart.
insert(Mem);
1084 II->eraseFromParent();
1101 bool InsertBefore) {
1102 for (
Value *Mem : Objects) {
1105 "Input memory not defined in original function");
1112 Marker->insertBefore(Term);
1116 if (!LifetimesStart.
empty()) {
1117 insertMarkers(Intrinsic::lifetime_start, LifetimesStart,
1121 if (!LifetimesEnd.
empty()) {
1122 insertMarkers(Intrinsic::lifetime_end, LifetimesEnd,
1133 ValueSet &outputs) {
1136 std::vector<Value *> params, ReloadOutputs, Reloads;
1137 ValueSet StructValues;
1145 unsigned ScalarInputArgNo = 0;
1147 for (
Value *input : inputs) {
1148 if (AggregateArgs && !ExcludeArgsFromAggregate.
contains(input))
1149 StructValues.
insert(input);
1151 params.push_back(input);
1152 if (input->isSwiftError())
1153 SwiftErrorArgs.
push_back(ScalarInputArgNo);
1159 unsigned ScalarOutputArgNo = 0;
1160 for (
Value *output : outputs) {
1161 if (AggregateArgs && !ExcludeArgsFromAggregate.
contains(output)) {
1162 StructValues.insert(output);
1165 new AllocaInst(output->getType(),
DL.getAllocaAddrSpace(),
1166 nullptr, output->
getName() +
".loc",
1168 ReloadOutputs.push_back(alloca);
1169 params.push_back(alloca);
1170 ++ScalarOutputArgNo;
1176 unsigned NumAggregatedInputs = 0;
1177 if (AggregateArgs && !StructValues.empty()) {
1178 std::vector<Type *> ArgTypes;
1179 for (
Value *V : StructValues)
1180 ArgTypes.push_back(
V->getType());
1185 StructArgTy,
DL.getAllocaAddrSpace(),
nullptr,
"structArg",
1188 params.push_back(
Struct);
1191 for (
unsigned i = 0, e = StructValues.size(); i != e; ++i) {
1192 if (inputs.contains(StructValues[i])) {
1198 GEP->insertInto(codeReplacer, codeReplacer->
end());
1200 NumAggregatedInputs++;
1207 NumExitBlocks > 1 ?
"targetBlock" :
"");
1219 for (
unsigned SwiftErrArgNo : SwiftErrorArgs) {
1220 call->
addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1221 newFunction->
addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
1226 for (
unsigned i = 0, e = outputs.size(), scalarIdx = 0,
1227 aggIdx = NumAggregatedInputs;
1229 Value *Output =
nullptr;
1230 if (AggregateArgs && StructValues.contains(outputs[i])) {
1236 GEP->insertInto(codeReplacer, codeReplacer->
end());
1240 Output = ReloadOutputs[scalarIdx];
1244 outputs[i]->
getName() +
".reload",
1246 Reloads.push_back(load);
1247 std::vector<User *>
Users(outputs[i]->user_begin(), outputs[i]->user_end());
1258 codeReplacer, 0, codeReplacer);
1265 std::map<BasicBlock *, BasicBlock *> ExitBlockMap;
1269 unsigned switchVal = 0;
1271 if (
Blocks.count(OldTarget))
1273 BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
1280 OldTarget->getName() +
".exitStub",
1282 unsigned SuccNum = switchVal++;
1284 Value *brVal =
nullptr;
1285 assert(NumExitBlocks < 0xffff &&
"too many exit blocks for switch");
1286 switch (NumExitBlocks) {
1312 BasicBlock *NewTarget = ExitBlockMap[OldTarget];
1313 assert(NewTarget &&
"Unknown target block!");
1324 std::advance(ScalarOutputArgBegin, ScalarInputArgNo);
1326 std::advance(AggOutputArgBegin, ScalarInputArgNo + ScalarOutputArgNo);
1328 for (
unsigned i = 0, e = outputs.size(), aggIdx = NumAggregatedInputs; i != e;
1330 auto *OutI = dyn_cast<Instruction>(outputs[i]);
1338 if (
auto *InvokeI = dyn_cast<InvokeInst>(OutI))
1339 InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
1340 else if (
auto *Phi = dyn_cast<PHINode>(OutI))
1341 InsertPt = Phi->getParent()->getFirstInsertionPt();
1343 InsertPt = std::next(OutI->getIterator());
1348 "InsertPt should be in new function");
1349 if (AggregateArgs && StructValues.contains(outputs[i])) {
1351 "Number of aggregate output arguments should match "
1352 "the number of defined values");
1357 StructArgTy, &*AggOutputArgBegin,
Idx,
"gep_" + outputs[i]->
getName(),
1366 "Number of scalar output arguments should match "
1367 "the number of defined values");
1368 new StoreInst(outputs[i], &*ScalarOutputArgBegin, InsertBefore);
1369 ++ScalarOutputArgBegin;
1375 switch (NumExitBlocks) {
1424void CodeExtractor::moveCodeToFunction(
Function *newFunction) {
1428 Block->removeFromParent();
1435 newFuncIt = newFunction->
insert(std::next(newFuncIt),
Block);
1439void CodeExtractor::calculateNewCallTerminatorWeights(
1451 Distribution BranchDist;
1458 BlockNode ExitNode(i);
1461 BranchDist.addExit(ExitNode, ExitFreq);
1467 if (BranchDist.Total == 0) {
1473 BranchDist.normalize();
1476 for (
unsigned I = 0,
E = BranchDist.Weights.size();
I <
E; ++
I) {
1477 const auto &Weight = BranchDist.Weights[
I];
1480 BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
1482 EdgeProbabilities[Weight.TargetNode.Index] = BP;
1486 LLVMContext::MD_prof,
1497 if (DVI->getFunction() != &
F)
1498 DVI->eraseFromParent();
1521 assert(OldSP->getUnit() &&
"Missing compile unit for subprogram");
1527 DISubprogram::SPFlagOptimized |
1528 DISubprogram::SPFlagLocalToUnit;
1531 0, SPType, 0, DINode::FlagZero, SPFlags);
1544 auto *DII = dyn_cast<DbgInfoIntrinsic>(&
I);
1550 if (
auto *DLI = dyn_cast<DbgLabelInst>(&
I)) {
1551 if (DLI->getDebugLoc().getInlinedAt())
1553 DILabel *OldLabel = DLI->getLabel();
1554 DINode *&NewLabel = RemappedMetadata[OldLabel];
1557 *OldLabel->
getScope(), *NewSP, Ctx, Cache);
1565 auto IsInvalidLocation = [&NewFunc](
Value *Location) {
1569 (!isa<Constant>(Location) && !isa<Instruction>(Location)))
1571 Instruction *LocationInst = dyn_cast<Instruction>(Location);
1572 return LocationInst && LocationInst->
getFunction() != &NewFunc;
1575 auto *DVI = cast<DbgVariableIntrinsic>(DII);
1577 if (
any_of(DVI->location_ops(), IsInvalidLocation)) {
1583 if (!DVI->getDebugLoc().getInlinedAt()) {
1585 DINode *&NewVar = RemappedMetadata[OldVar];
1588 *OldVar->
getScope(), *NewSP, Ctx, Cache);
1591 OldVar->
getType(),
false, DINode::FlagZero,
1594 DVI->setVariable(cast<DILocalVariable>(NewVar));
1598 for (
auto *DII : DebugIntrinsicsToDelete)
1599 DII->eraseFromParent();
1610 auto updateLoopInfoLoc = [&Ctx, &Cache, NewSP](
Metadata *MD) ->
Metadata * {
1611 if (
auto *Loc = dyn_cast_or_null<DILocation>(MD))
1644 assert(BPI &&
"Both BPI and BFI are required to preserve profile info");
1657 if (
auto *AI = dyn_cast<AssumeInst>(&
I)) {
1660 AI->eraseFromParent();
1667 splitReturnBlocks();
1675 if (!
Blocks.count(Succ)) {
1685 NumExitBlocks = ExitBlocks.
size();
1693 OldTargets.push_back(OldTarget);
1698 severSplitPHINodesOfEntry(header);
1699 severSplitPHINodesOfExits(ExitBlocks);
1703 "codeRepl", oldFunction,
1718 if (!
I.getDebugLoc())
1720 BranchI->setDebugLoc(
I.getDebugLoc());
1725 BranchI->insertInto(newFuncRoot, newFuncRoot->
end());
1727 ValueSet SinkingCands, HoistingCands;
1729 findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1739 for (
auto *II : SinkingCands) {
1740 if (
auto *AI = dyn_cast<AllocaInst>(II)) {
1742 if (!FirstSunkAlloca)
1743 FirstSunkAlloca = AI;
1746 assert((SinkingCands.
empty() || FirstSunkAlloca) &&
1747 "Did not expect a sink candidate without any allocas");
1748 for (
auto *II : SinkingCands) {
1749 if (!isa<AllocaInst>(II)) {
1750 cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
1754 if (!HoistingCands.
empty()) {
1757 for (
auto *II : HoistingCands)
1770 constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
1783 emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);
1785 moveCodeToFunction(newFunction);
1797 if (BFI && NumExitBlocks > 1)
1798 calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);
1810 for (
PHINode &PN : ExitBB->phis()) {
1811 Value *IncomingCodeReplacerVal =
nullptr;
1818 if (!IncomingCodeReplacerVal) {
1823 "PHI has two incompatbile incoming values from codeRepl");
1834 return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
1840 newFunction->
dump();
1854 auto *
I = dyn_cast_or_null<CallInst>(AssumeVH);
1859 if (
I->getFunction() != &OldFunc)
1866 auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
1869 if (AffectedCI->getFunction() != &OldFunc)
1871 auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));
1872 if (AssumedInst->getFunction() != &OldFunc)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Callee
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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
Move duplicate certain instructions close to their use
Module.h This file contains the declarations for the Module class.
print must be executed print the must be executed context for all instructions
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 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.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
ArrayRef< value_type > getArrayRef() const
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.
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.
auto predecessors(const MachineBasicBlock *BB)
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
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.