30#define DEBUG_TYPE "iroutliner"
33using namespace IRSimilarity;
57 cl::desc(
"Enable the IR outliner on linkonceodr functions"),
64 cl::desc(
"Debug option to outline greedily, without restriction that "
65 "calculated benefit outweighs cost"));
158 I.moveBeforePreserving(TargetBB, TargetBB.
end());
168 for (
auto &VtoBB : Map)
169 SortedKeys.push_back(VtoBB.first);
173 if (SortedKeys.size() == 1) {
174 assert(!SortedKeys[0] &&
"Expected a single void value.");
190 assert(GVN &&
"No GVN for incoming value");
192 std::optional<unsigned> FirstGVN =
193 Other.Candidate->fromCanonicalNum(*CanonNum);
194 std::optional<Value *> FoundValueOpt =
Other.Candidate->fromGVN(*FirstGVN);
195 return FoundValueOpt.value_or(
nullptr);
202 assert(FirstNonPHI &&
"block is empty?");
204 if (!CorrespondingVal)
207 cast<Instruction>(CorrespondingVal)->
getParent();
208 return CorrespondingBlock;
225 for (
unsigned Idx = 0, PNEnd = PN.getNumIncomingValues();
Idx != PNEnd;
234 assert(BI &&
"Not a branch instruction?");
263 assert(EndInst &&
"Expected an end instruction?");
275 assert(StartInst &&
"Expected a start instruction?");
294 while (
PHINode *PN = dyn_cast<PHINode>(&*It)) {
295 unsigned NumPredsOutsideRegion = 0;
296 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
297 if (!BBSet.
contains(PN->getIncomingBlock(i))) {
298 PHIPredBlock = PN->getIncomingBlock(i);
299 ++NumPredsOutsideRegion;
306 IBlock = PN->getIncomingBlock(i);
307 if (IBlock ==
EndBB && EndBBTermAndBackInstDifferent) {
308 PHIPredBlock = PN->getIncomingBlock(i);
309 ++NumPredsOutsideRegion;
313 if (NumPredsOutsideRegion > 1)
321 if (isa<PHINode>(StartInst) && StartInst != &*
StartBB->
begin())
326 if (isa<PHINode>(BackInst) &&
393 assert(
StartBB !=
nullptr &&
"StartBB for Candidate is not defined!");
411 "PrevBB has more than one predecessor. Should be 0 or 1.");
435 assert(
FollowBB !=
nullptr &&
"FollowBB for Candidate is not defined!");
463static std::optional<bool>
467 Constant *CST = dyn_cast<Constant>(V);
477 std::tie(GVNToConstantIt, Inserted) =
478 GVNToConstant.
insert(std::make_pair(GVN, CST));
481 if (Inserted || (GVNToConstantIt->second == CST))
504 switch (
I->getOpcode()) {
505 case Instruction::FDiv:
506 case Instruction::FRem:
507 case Instruction::SDiv:
508 case Instruction::SRem:
509 case Instruction::UDiv:
510 case Instruction::URem:
534 OutputMappings.
find(Input);
535 if (OutputMapping != OutputMappings.
end())
536 return OutputMapping->second;
553 bool ConstantsTheSame =
true;
562 std::optional<unsigned> GVNOpt =
C.getGVN(V);
563 assert(GVNOpt &&
"Expected a GVN for operand?");
564 unsigned GVN = *GVNOpt;
568 if (isa<Constant>(V))
569 ConstantsTheSame =
false;
577 std::optional<bool> ConstantMatches =
579 if (ConstantMatches) {
580 if (*ConstantMatches)
583 ConstantsTheSame =
false;
590 ConstantsTheSame =
false;
596 return ConstantsTheSame;
608 OutputGVNCombinations.insert(
OS->GVNStores);
613 if (OutputGVNCombinations.size() > 1)
631 unsigned FunctionNameSuffix) {
644 Type *ExtractedFuncType =
R->ExtractedFunction->getReturnType();
647 RetTy = ExtractedFuncType;
657 "outlined_ir_func_" + std::to_string(FunctionNameSuffix), M);
662 Attribute::SwiftError);
674 DIFile *Unit = SP->getFile();
682 Unit ,
F->getName(), MangledNameStream.str(),
685 DB.createSubroutineType(
686 DB.getOrCreateTypeArray(std::nullopt)),
688 DINode::DIFlags::FlagArtificial ,
690 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
693 DB.finalizeSubprogram(OutlinedSP);
696 F->setSubprogram(OutlinedSP);
712 CurrBB.removeFromParent();
713 CurrBB.insertInto(&New);
720 NewEnds.
insert(std::make_pair(RI->getReturnValue(), &CurrBB));
722 std::vector<Instruction *> DebugInsts;
727 if (!isa<CallInst>(&Val)) {
736 if (
auto *Loc = dyn_cast_or_null<DILocation>(MD))
738 Loc->getColumn(), SP,
nullptr);
746 CallInst *CI = cast<CallInst>(&Val);
752 if (isa<DbgInfoIntrinsic>(CI)) {
753 DebugInsts.push_back(&Val);
765 I->eraseFromParent();
779 std::vector<unsigned> &Inputs) {
783 for (IRInstructionDataList::iterator IDIt =
C.begin(), EndIDIt =
C.end();
784 IDIt != EndIDIt; IDIt++) {
785 for (
Value *V : (*IDIt).OperVals) {
788 unsigned GVN = *
C.getGVN(V);
789 if (isa<Constant>(V))
791 Inputs.push_back(GVN);
811 std::vector<unsigned> &EndInputNumbers) {
815 for (
Value *Input : CurrentInputs) {
816 assert(Input &&
"Have a nullptr as an input");
818 Input = OutputMappings.
find(Input)->second;
819 assert(
C.getGVN(Input) &&
"Could not find a numbering for the given input");
820 EndInputNumbers.push_back(*
C.getGVN(Input));
838 for (
Value *Input : ArgInputs) {
840 Input = OutputMappings.
find(Input)->second;
841 RemappedArgInputs.
insert(Input);
884 CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands);
885 assert(
Region.StartBB &&
"Region must have a start BasicBlock!");
892 if (!CE->isEligible()) {
893 Region.IgnoreRegion =
true;
898 CE->findAllocas(CEAC, SinkCands, HoistCands, Dummy);
899 CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands);
906 if (OverallInputs.
size() != PremappedInputs.
size()) {
907 Region.IgnoreRegion =
true;
935 std::vector<unsigned> &InputGVNs,
942 unsigned TypeIndex = 0;
945 unsigned OriginalIndex = 0;
956 for (
unsigned InputVal : InputGVNs) {
957 std::optional<unsigned> CanonicalNumberOpt =
C.getCanonicalNum(InputVal);
958 assert(CanonicalNumberOpt &&
"Canonical number not found?");
959 unsigned CanonicalNumber = *CanonicalNumberOpt;
961 std::optional<Value *> InputOpt =
C.fromGVN(InputVal);
962 assert(InputOpt &&
"Global value number not found?");
963 Value *Input = *InputOpt;
975 "Argument already marked with swifterr for this OutlinableGroup!");
982 if (
Constant *CST = dyn_cast<Constant>(Input)) {
984 Region.AggArgToConstant.insert(std::make_pair(AggArgIt->second, CST));
987 std::make_pair(CanonicalNumber, TypeIndex));
988 Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST));
996 assert(ArgInputs.
count(Input) &&
"Input cannot be found!");
999 if (OriginalIndex != AggArgIt->second)
1000 Region.ChangedArgOrder =
true;
1001 Region.ExtractedArgToAgg.insert(
1002 std::make_pair(OriginalIndex, AggArgIt->second));
1003 Region.AggArgToExtracted.insert(
1004 std::make_pair(AggArgIt->second, OriginalIndex));
1007 std::make_pair(CanonicalNumber, TypeIndex));
1008 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex));
1009 Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex));
1024 Region.NumExtractedInputs = OriginalIndex;
1043 [PHILoc, &PN, V, &BlocksInRegion](
unsigned Idx) {
1044 return (Idx != PHILoc && V == PN.getIncomingValue(Idx) &&
1045 !BlocksInRegion.contains(PN.getIncomingBlock(Idx)));
1050 return any_of(V->users(), [&Exits, &BlocksInRegion](
User *U) {
1051 Instruction *I = dyn_cast<Instruction>(U);
1058 BasicBlock *Parent = I->getParent();
1059 if (BlocksInRegion.contains(Parent))
1065 if (!isa<PHINode>(I))
1072 if (!Exits.contains(Parent))
1099 for (
PHINode &PN : CurrentExitFromRegion->
phis()) {
1102 for (
unsigned I = 0,
E = PN.getNumIncomingValues();
I <
E; ++
I)
1103 if (RegionBlocks.
contains(PN.getIncomingBlock(
I)))
1107 unsigned NumIncomingVals = IncomingVals.
size();
1108 if (NumIncomingVals == 0)
1113 if (NumIncomingVals == 1) {
1114 Value *V = PN.getIncomingValue(*IncomingVals.
begin());
1115 OutputsWithNonPhiUses.
insert(V);
1116 OutputsReplacedByPHINode.
erase(V);
1126 for (
unsigned Idx : IncomingVals) {
1127 Value *V = PN.getIncomingValue(
Idx);
1129 OutputsWithNonPhiUses.
insert(V);
1130 OutputsReplacedByPHINode.
erase(V);
1133 if (!OutputsWithNonPhiUses.
contains(V))
1134 OutputsReplacedByPHINode.
insert(V);
1177 unsigned AggArgIdx) {
1192 std::optional<unsigned> OGVN = Cand.
getGVN(Incoming);
1193 if (!OGVN &&
Blocks.contains(IncomingBlock)) {
1194 Region.IgnoreRegion =
true;
1195 return std::nullopt;
1200 if (!
Blocks.contains(IncomingBlock))
1204 unsigned GVN = *OGVN;
1206 assert(OGVN &&
"No GVN found for incoming value?");
1211 OGVN = Cand.
getGVN(IncomingBlock);
1218 "Unknown basic block used in exit path PHINode.");
1226 if (!
Blocks.contains(Pred)) {
1230 assert(PrevBlock &&
"Expected a predecessor not in the reigon!");
1231 OGVN = Cand.
getGVN(PrevBlock);
1235 assert(OGVN &&
"No GVN found for incoming block?");
1244 std::optional<unsigned> BBGVN = Cand.
getGVN(PHIBB);
1245 assert(BBGVN &&
"Could not find GVN for the incoming block!");
1248 assert(BBGVN &&
"Could not find canonical number for the incoming block!");
1253 std::make_pair(std::make_pair(*BBGVN, AggArgIdx), PHIGVNs);
1260 bool Inserted =
false;
1267 return GVNToPHIIt->second;
1283 C.getBasicBlocks(BlocksInRegion, BE);
1289 if (!BlocksInRegion.
contains(Succ))
1299 OutputsReplacedByPHINode,
1300 OutputsWithNonPhiUses);
1303 unsigned OriginalIndex =
Region.NumExtractedInputs;
1316 for (
Value *Output : Outputs) {
1326 if (OutputsReplacedByPHINode.
contains(Output))
1329 unsigned AggArgIdx = 0;
1330 for (
unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {
1339 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, Jdx));
1340 Region.AggArgToExtracted.insert(std::make_pair(Jdx, OriginalIndex));
1349 Group.
ArgumentTypes.push_back(Output->getType()->getPointerTo(
1350 M.getDataLayout().getAllocaAddrSpace()));
1354 AggArgsUsed.
insert(ArgTypeIdx);
1355 Region.ExtractedArgToAgg.insert(
1356 std::make_pair(OriginalIndex, ArgTypeIdx));
1357 Region.AggArgToExtracted.insert(
1358 std::make_pair(ArgTypeIdx, OriginalIndex));
1359 AggArgIdx = ArgTypeIdx;
1363 PHINode *PN = dyn_cast<PHINode>(Output);
1365 std::optional<unsigned> GVN;
1383 GVN =
C.getGVN(Output);
1384 GVN =
C.getCanonicalNum(*GVN);
1390 Region.GVNStores.push_back(*GVN);
1403 std::vector<unsigned> Inputs;
1431 std::vector<Value *> NewCallArgs;
1436 assert(Call &&
"Call to replace is nullptr?");
1438 assert(AggFunc &&
"Function to replace with is nullptr?");
1444 if (!
Region.ChangedArgOrder && AggFunc->
arg_size() == Call->arg_size()) {
1445 LLVM_DEBUG(
dbgs() <<
"Replace call to " << *Call <<
" with call to "
1446 << *AggFunc <<
" with same number of arguments\n");
1447 Call->setCalledFunction(AggFunc);
1455 for (
unsigned AggArgIdx = 0; AggArgIdx < AggFunc->
arg_size(); AggArgIdx++) {
1457 if (AggArgIdx == AggFunc->
arg_size() - 1 &&
1463 <<
Region.OutputBlockNum <<
"\n");
1469 ArgPair =
Region.AggArgToExtracted.find(AggArgIdx);
1470 if (ArgPair !=
Region.AggArgToExtracted.
end()) {
1471 Value *ArgumentValue = Call->getArgOperand(ArgPair->second);
1475 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to value "
1476 << *ArgumentValue <<
"\n");
1477 NewCallArgs.push_back(ArgumentValue);
1484 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to value "
1486 NewCallArgs.push_back(CST);
1493 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to nullptr\n");
1498 LLVM_DEBUG(
dbgs() <<
"Replace call to " << *Call <<
" with call to "
1499 << *AggFunc <<
" with new set of arguments\n");
1509 if (
Region.NewFront->Inst == OldCall)
1510 Region.NewFront->Inst = Call;
1511 if (
Region.NewBack->Inst == OldCall)
1512 Region.NewBack->Inst = Call;
1515 Call->setDebugLoc(
Region.Call->getDebugLoc());
1543 ReturnBlockForRetVal;
1545 ReturnBlockForRetVal = Group.
EndBBs.
find(RetVal);
1547 "Could not find output value!");
1548 BasicBlock *ReturnBB = ReturnBlockForRetVal->second;
1554 return PhiBlockForRetVal->second;
1558 bool Inserted =
false;
1561 std::tie(PhiBlockForRetVal, Inserted) =
1569 BranchesToChange.
push_back(cast<BranchInst>(Pred->getTerminator()));
1574 for (
unsigned Succ = 0,
End = BI->getNumSuccessors(); Succ <
End; Succ++) {
1575 if (BI->getSuccessor(Succ) != ReturnBB)
1577 BI->setSuccessor(Succ, PHIBlock);
1582 return PhiBlockForRetVal->second;
1599 return Region.Call->getArgOperand(
A->getArgNo());
1612 unsigned ArgNum =
A->getArgNo();
1616 if (
Region.AggArgToConstant.count(ArgNum))
1617 return Region.AggArgToConstant.find(ArgNum)->second;
1621 ArgNum =
Region.AggArgToExtracted.find(ArgNum)->second;
1622 return Region.Call->getArgOperand(ArgNum);
1638 SmallVector<std::pair<unsigned, BasicBlock *>> &CanonNums,
1639 bool ReplacedWithOutlinedCall =
true) {
1646 if (
Argument *
A = dyn_cast<Argument>(IVal)) {
1647 if (ReplacedWithOutlinedCall)
1657 std::optional<unsigned> GVN =
Region.Candidate->getGVN(IVal);
1658 assert(GVN &&
"No GVN for incoming value");
1659 std::optional<unsigned> CanonNum =
Region.Candidate->getCanonicalNum(*GVN);
1660 assert(CanonNum &&
"No Canonical Number for GVN");
1661 CanonNums.push_back(std::make_pair(*CanonNum, IBlock));
1712 CurrentCanonNums.
clear();
1718 if (PNCanonNums.
size() != CurrentCanonNums.
size())
1721 bool FoundMatch =
true;
1730 for (
unsigned Idx = 0, Edx = PNCanonNums.
size();
Idx < Edx; ++
Idx) {
1731 std::pair<unsigned, BasicBlock *> ToCompareTo = CurrentCanonNums[
Idx];
1732 std::pair<unsigned, BasicBlock *> ToAdd = PNCanonNums[
Idx];
1733 if (ToCompareTo.first != ToAdd.first) {
1739 Region.findCorrespondingBlockIn(*FirstRegion, ToAdd.second);
1740 assert(CorrespondingBlock &&
"Found block is nullptr");
1741 if (CorrespondingBlock != ToCompareTo.second) {
1750 UsedPHIs.
insert(&CurrPN);
1767 Region.findCorrespondingBlockIn(*FirstRegion, IncomingBlock);
1772 if (
Argument *
A = dyn_cast<Argument>(IncomingVal)) {
1780 Value *Val =
Region.findCorrespondingValueIn(*FirstRegion, IncomingVal);
1781 assert(Val &&
"Value is nullptr?");
1785 Val = RemappedIt->second;
1804 bool FirstFunction =
false) {
1806 assert(
Region.ExtractedFunction &&
"Region has no extracted function?");
1814 for (
unsigned ArgIdx = 0; ArgIdx <
Region.ExtractedFunction->arg_size();
1817 "No mapping from extracted to outlined?");
1818 unsigned AggArgIdx =
Region.ExtractedArgToAgg.find(ArgIdx)->second;
1823 if (ArgIdx <
Region.NumExtractedInputs) {
1824 LLVM_DEBUG(
dbgs() <<
"Replacing uses of input " << *Arg <<
" in function "
1825 << *
Region.ExtractedFunction <<
" with " << *AggArg
1829 Region.RemappedArguments.insert(std::make_pair(V, AggArg));
1838 assert(InstAsUser &&
"User is nullptr!");
1844 bool EdgeAdded =
false;
1845 if (Descendants.
size() == 0) {
1855 ReturnInst *RI = dyn_cast<ReturnInst>(DescendBB->getTerminator());
1859 auto VBBIt = OutputBBs.
find(RetVal);
1860 assert(VBBIt != OutputBBs.
end() &&
"Could not find output value!");
1866 Value *ValueOperand = SI->getValueOperand();
1868 StoreInst *NewI = cast<StoreInst>(
I->clone());
1873 << *OutputBB <<
"\n");
1877 if (!isa<PHINode>(ValueOperand) ||
1878 Region.Candidate->getGVN(ValueOperand).has_value()) {
1882 Region.findCorrespondingValueIn(*Group.
Regions[0], ValueOperand);
1883 assert(CorrVal &&
"Value is nullptr?");
1887 PHINode *PN = cast<PHINode>(SI->getValueOperand());
1890 if (
Region.Candidate->getGVN(PN))
1900 if (FirstFunction) {
1914 OutputMappings, UsedPHIs);
1922 I->eraseFromParent();
1924 LLVM_DEBUG(
dbgs() <<
"Replacing uses of output " << *Arg <<
" in function "
1925 << *
Region.ExtractedFunction <<
" with " << *AggArg
1938 for (std::pair<unsigned, Constant *> &Const :
Region.AggArgToConstant) {
1939 unsigned AggArgIdx = Const.first;
1941 assert(OutlinedFunction &&
"Overall Function is not defined?");
1952 <<
" in function " << *OutlinedFunction <<
" with "
1955 if (
Instruction *
I = dyn_cast<Instruction>(U.getUser()))
1956 return I->getFunction() == OutlinedFunction;
1972 bool Mismatch =
false;
1973 unsigned MatchingNum = 0;
1979 for (std::pair<Value *, BasicBlock *> &VToB : CompBBs) {
1981 OutputBBs.
find(VToB.first);
1982 if (OutputBBIt == OutputBBs.
end()) {
1989 if (CompBB->
size() - 1 != OutputBB->
size()) {
1996 if (isa<BranchInst>(&
I))
1999 if (!
I.isIdenticalTo(&(*NIt))) {
2014 return std::nullopt;
2025 bool AllRemoved =
true;
2026 Value *RetValueForBB;
2030 for (std::pair<Value *, BasicBlock *> &VtoBB : BlocksToPrune) {
2031 RetValueForBB = VtoBB.first;
2032 NewBB = VtoBB.second;
2036 if (NewBB->
size() == 0) {
2049 BlocksToPrune.
erase(V);
2053 Region.OutputBlockNum = -1;
2083 std::optional<unsigned> MatchingBB =
2090 <<
Region.ExtractedFunction <<
" to " << *MatchingBB);
2092 Region.OutputBlockNum = *MatchingBB;
2093 for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs)
2094 VtoBB.second->eraseFromParent();
2098 Region.OutputBlockNum = OutputStoreBBs.size();
2100 Value *RetValueForBB;
2103 for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs) {
2104 RetValueForBB = VtoBB.first;
2105 NewBB = VtoBB.second;
2107 EndBBs.
find(RetValueForBB);
2109 <<
Region.ExtractedFunction <<
" to "
2112 OutputStoreBBs.back().insert(std::make_pair(RetValueForBB, NewBB));
2129 std::vector<Value *> SortedKeys;
2133 for (
Value *RetVal : SortedKeys) {
2138 NewMap.
insert(std::make_pair(RetVal, NewBB));
2167 for (std::pair<Value *, BasicBlock *> &RetBlockPair : ReturnBBs) {
2168 std::pair<Value *, BasicBlock *> &OutputBlock =
2170 BasicBlock *ReturnBlock = RetBlockPair.second;
2175 Term->moveBefore(*ReturnBlock, ReturnBlock->
end());
2178 LLVM_DEBUG(
dbgs() <<
"Create switch statement in " << *AggFunc <<
" for "
2179 << OutputStoreBBs.
size() <<
"\n");
2182 ReturnBlock, OutputStoreBBs.
size(), EndBB);
2187 OutputStoreBB.
find(OutputBlock.first);
2189 if (OSBBIt == OutputStoreBB.
end())
2196 Term->setSuccessor(0, ReturnBlock);
2203 assert(OutputStoreBBs.size() < 2 &&
"Different store sets not handled!");
2211 if (OutputStoreBBs.size() == 1) {
2212 LLVM_DEBUG(
dbgs() <<
"Move store instructions to the end block in "
2215 for (std::pair<Value *, BasicBlock *> &VBPair : OutputBlocks) {
2217 EndBBs.
find(VBPair.first);
2218 assert(EndBBIt != EndBBs.
end() &&
"Could not find end block");
2222 Term->eraseFromParent();
2225 Term->moveBefore(*EndBB, EndBB->
end());
2247 std::vector<Function *> &FuncsToRemove,
2276 for (std::pair<Value *, BasicBlock *> &VToBB : NewBBs) {
2281 OutputStoreBBs.back().insert(VToBB);
2293void IROutliner::deduplicateExtractedSections(
2295 std::vector<Function *> &FuncsToRemove,
unsigned &OutlinedFunctionNum) {
2296 createFunction(M, CurrentGroup, OutlinedFunctionNum);
2298 std::vector<DenseMap<Value *, BasicBlock *>> OutputStoreBBs;
2305 std::vector<Value *> SortedKeys;
2316 "output_block_" +
Twine(
static_cast<unsigned>(
Idx)));
2319 CurrentGroup.
EndBBs, OutputMappings,
2329 OutlinedFunctionNum++;
2346 IRInstructionDataList::iterator NextIDIt = std::next(
ID.getIterator());
2349 if (!
ID.Inst->isTerminator())
2350 NextModuleInst =
ID.Inst->getNextNonDebugInstruction();
2351 else if (NextIDLInst !=
nullptr)
2355 if (NextIDLInst && NextIDLInst != NextModuleInst)
2361bool IROutliner::isCompatibleWithAlreadyOutlinedCode(
2369 for (
unsigned Idx = StartIdx;
Idx <= EndIdx;
Idx++)
2375 if (!
Region.Candidate->backInstruction()->isTerminator()) {
2377 Region.Candidate->backInstruction()->getNextNonDebugInstruction();
2378 assert(NewEndInst &&
"Next instruction is a nullptr?");
2379 if (
Region.Candidate->
end()->Inst != NewEndInst) {
2383 InstructionClassifier.visit(*NewEndInst), *IDL);
2395 return !this->InstructionClassifier.visit(
ID.Inst);
2399void IROutliner::pruneIncompatibleRegions(
2400 std::vector<IRSimilarityCandidate> &CandidateVec,
2402 bool PreviouslyOutlined;
2407 return LHS.getStartIdx() <
RHS.getStartIdx();
2413 if (FirstCandidate.getLength() == 2) {
2414 if (isa<CallInst>(FirstCandidate.front()->Inst) &&
2415 isa<BranchInst>(FirstCandidate.back()->Inst))
2419 unsigned CurrentEndIdx = 0;
2421 PreviouslyOutlined =
false;
2426 for (
unsigned Idx = StartIdx;
Idx <= EndIdx;
Idx++)
2428 PreviouslyOutlined =
true;
2432 if (PreviouslyOutlined)
2438 return ID.Inst->getParent()->hasAddressTaken();
2441 if (BBHasAddressTaken)
2449 dbgs() <<
"... Skipping function with nooutline attribute: "
2450 << FnForCurrCand.
getName() <<
"\n";
2456 !OutlineFromLinkODRs)
2461 if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
2468 return !this->InstructionClassifier.visit(
ID.Inst);
2478 CurrentEndIdx = EndIdx;
2489 RegionBenefit +=
Region->getBenefit(
TTI);
2491 <<
" saved instructions to overfall benefit.\n");
2494 return RegionBenefit;
2506 unsigned OutputCanon) {
2514 "Could not find GVN set for PHINode number!");
2515 assert(It->second.second.size() > 0 &&
"PHINode does not have any values!");
2516 OutputCanon = *It->second.second.begin();
2518 std::optional<unsigned> OGVN =
2519 Region.Candidate->fromCanonicalNum(OutputCanon);
2520 assert(OGVN &&
"Could not find GVN for Canonical Number?");
2521 std::optional<Value *> OV =
Region.Candidate->fromGVN(*OGVN);
2522 assert(OV &&
"Could not find value for GVN?");
2533 for (
unsigned OutputCanon :
Region->GVNStores) {
2540 <<
" instructions to cost for output of type "
2541 << *
V->getType() <<
"\n");
2542 OverallCost += LoadCost;
2561 unsigned NumOutputBranches = 0;
2572 if (!isa<BranchInst>(
ID.Inst))
2575 for (
Value *V :
ID.OperVals) {
2577 if (!CandidateBlocks.
contains(BB) && FoundBlocks.
insert(BB).second)
2578 NumOutputBranches++;
2586 for (
unsigned OutputCanon : OutputUse) {
2596 <<
" instructions to cost for output of type "
2597 << *V->getType() <<
"\n");
2598 OutputCost += StoreCost * NumOutputBranches;
2603 LLVM_DEBUG(
dbgs() <<
"Adding " << BranchCost <<
" to the current cost for"
2604 <<
" a branch instruction\n");
2605 OutputCost += BranchCost * NumOutputBranches;
2619 InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
2622 <<
" instructions for each switch case for each different"
2623 <<
" output path in a function\n");
2624 OutputCost += TotalCost * NumOutputBranches;
2631 InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
2632 CurrentGroup.
Benefit += RegionBenefit;
2635 InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);
2636 CurrentGroup.
Cost += OutputReloadCost;
2640 RegionBenefit / CurrentGroup.
Regions.size();
2641 unsigned OverallArgumentNum = CurrentGroup.
ArgumentTypes.size();
2642 unsigned NumRegions = CurrentGroup.
Regions.size();
2644 getTTI(*CurrentGroup.
Regions[0]->Candidate->getFunction());
2649 <<
" instructions to cost for body of new function.\n");
2650 CurrentGroup.
Cost += AverageRegionBenefit;
2656 <<
" instructions to cost for each argument in the new"
2658 CurrentGroup.
Cost +=
2666 <<
" instructions to cost for each argument in the new"
2667 <<
" function " << NumRegions <<
" times for the "
2668 <<
"needed argument handling at the call site.\n");
2669 CurrentGroup.
Cost +=
2682 std::optional<unsigned> OutputIdx;
2684 for (
unsigned ArgIdx =
Region.NumExtractedInputs;
2685 ArgIdx < Region.Call->arg_size(); ArgIdx++) {
2686 if (Operand ==
Region.Call->getArgOperand(ArgIdx)) {
2687 OutputIdx = ArgIdx -
Region.NumExtractedInputs;
2697 if (!OutputMappings.contains(Outputs[*OutputIdx])) {
2698 LLVM_DEBUG(
dbgs() <<
"Mapping extracted output " << *LI <<
" to "
2699 << *Outputs[*OutputIdx] <<
"\n");
2700 OutputMappings.insert(std::make_pair(LI, Outputs[*OutputIdx]));
2702 Value *Orig = OutputMappings.find(Outputs[*OutputIdx])->second;
2703 LLVM_DEBUG(
dbgs() <<
"Mapping extracted output " << *Orig <<
" to "
2704 << *Outputs[*OutputIdx] <<
"\n");
2705 OutputMappings.insert(std::make_pair(LI, Orig));
2711 assert(
Region.StartBB &&
"StartBB for the OutlinableRegion is nullptr!");
2715 Region.ExtractedFunction =
2716 Region.CE->extractCodeRegion(CEAC, ArgInputs, Outputs);
2720 if (!
Region.ExtractedFunction) {
2723 Region.reattachCandidate();
2731 User *InstAsUser =
Region.ExtractedFunction->user_back();
2735 if (
Region.PrevBB == InitialStart) {
2744 Region.StartBB = RewrittenBB;
2745 Region.EndBB = RewrittenBB;
2756 *BeginRewritten, InstructionClassifier.visit(*BeginRewritten), *IDL);
2758 *EndRewritten, InstructionClassifier.visit(*EndRewritten), *IDL);
2769 assert(RewrittenBB !=
nullptr &&
2770 "Could not find a predecessor after extraction!");
2775 if (
CallInst *CI = dyn_cast<CallInst>(&
I)) {
2776 if (
Region.ExtractedFunction == CI->getCalledFunction())
2778 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(&
I))
2780 Region.reattachCandidate();
2784unsigned IROutliner::doOutline(
Module &M) {
2794 unsigned OutlinedFunctionNum = 0;
2797 if (SimilarityCandidates.size() > 1)
2799 [](
const std::vector<IRSimilarityCandidate> &LHS,
2800 const std::vector<IRSimilarityCandidate> &RHS) {
2801 return LHS[0].getLength() *
LHS.size() >
2802 RHS[0].getLength() *
RHS.size();
2806 std::vector<OutlinableGroup> PotentialGroups(SimilarityCandidates.size());
2809 std::vector<OutlinableGroup *> NegativeCostGroups;
2810 std::vector<OutlinableRegion *> OutlinedRegions;
2812 unsigned PotentialGroupIdx = 0;
2817 pruneIncompatibleRegions(CandidateVec, CurrentGroup);
2822 if (CurrentGroup.
Regions.size() < 2)
2836 OutlinedRegions.clear();
2840 OS->splitCandidate();
2845 if (!
OS->CandidateSplit)
2850 OS->Candidate->getBasicBlocks(BlocksInRegion, BE);
2851 OS->CE =
new (ExtractorAllocator.Allocate())
2852 CodeExtractor(BE,
nullptr,
false,
nullptr,
nullptr,
nullptr,
false,
2853 false,
nullptr,
"outlined");
2854 findAddInputsOutputs(M, *
OS, NotSame);
2855 if (!
OS->IgnoreRegion)
2856 OutlinedRegions.push_back(
OS);
2860 OS->reattachCandidate();
2863 CurrentGroup.
Regions = std::move(OutlinedRegions);
2865 if (CurrentGroup.
Regions.empty())
2871 findCostBenefit(M, CurrentGroup);
2875 if (CurrentGroup.
Cost >= CurrentGroup.
Benefit && CostModel) {
2877 getORE(*CurrentGroup.
Regions[0]->Candidate->getFunction());
2881 C->frontInstruction());
2882 R <<
"did not outline "
2884 <<
" regions due to estimated increase of "
2885 <<
ore::NV(
"InstructionIncrease",
2887 <<
" instructions at locations ";
2893 Region->Candidate->frontInstruction()->getDebugLoc());
2895 [&R]() { R <<
" "; });
2901 NegativeCostGroups.push_back(&CurrentGroup);
2904 ExtractorAllocator.DestroyAll();
2906 if (NegativeCostGroups.size() > 1)
2909 return LHS->Benefit -
LHS->Cost >
RHS->Benefit -
RHS->Cost;
2912 std::vector<Function *> FuncsToRemove;
2916 OutlinedRegions.clear();
2920 if (!isCompatibleWithAlreadyOutlinedCode(*
Region))
2922 OutlinedRegions.push_back(
Region);
2925 if (OutlinedRegions.size() < 2)
2930 CurrentGroup.
Regions = std::move(OutlinedRegions);
2933 CurrentGroup.
Cost = 0;
2934 findCostBenefit(M, CurrentGroup);
2938 OutlinedRegions.clear();
2940 Region->splitCandidate();
2941 if (!
Region->CandidateSplit)
2943 OutlinedRegions.push_back(
Region);
2946 CurrentGroup.
Regions = std::move(OutlinedRegions);
2947 if (CurrentGroup.
Regions.size() < 2) {
2949 R->reattachCandidate();
2954 <<
" and benefit " << CurrentGroup.
Benefit <<
"\n");
2957 OutlinedRegions.clear();
2961 OS->Candidate->getBasicBlocks(BlocksInRegion, BE);
2962 OS->CE =
new (ExtractorAllocator.Allocate())
2963 CodeExtractor(BE,
nullptr,
false,
nullptr,
nullptr,
nullptr,
false,
2964 false,
nullptr,
"outlined");
2965 bool FunctionOutlined = extractSection(*
OS);
2966 if (FunctionOutlined) {
2967 unsigned StartIdx =
OS->Candidate->getStartIdx();
2968 unsigned EndIdx =
OS->Candidate->getEndIdx();
2969 for (
unsigned Idx = StartIdx;
Idx <= EndIdx;
Idx++)
2972 OutlinedRegions.push_back(
OS);
2977 <<
" with benefit " << CurrentGroup.
Benefit
2978 <<
" and cost " << CurrentGroup.
Cost <<
"\n");
2980 CurrentGroup.
Regions = std::move(OutlinedRegions);
2982 if (CurrentGroup.
Regions.empty())
2986 getORE(*CurrentGroup.
Regions[0]->Call->getFunction());
2990 R <<
"outlined " <<
ore::NV(std::to_string(CurrentGroup.
Regions.size()))
2991 <<
" regions with decrease of "
2993 <<
" instructions at locations ";
2997 R << ore::NV(
"DebugLoc",
2998 Region->Candidate->frontInstruction()->getDebugLoc());
3000 [&R]() { R <<
" "; });
3004 deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,
3005 OutlinedFunctionNum);
3009 F->eraseFromParent();
3011 return OutlinedFunctionNum;
3018 return doOutline(M) > 0;
3034 std::unique_ptr<OptimizationRemarkEmitter> ORE;
ReachingDefAnalysis InstSet & ToRemove
This file contains the simple types necessary to represent the attributes associated with functions a...
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
std::optional< std::vector< StOtherPiece > > Other
DenseMap< Block *, BlockRelaxAux > Blocks
std::pair< ArgLocWithBBCanon, CanonList > PHINodeData
static void remapExtractedInputs(const ArrayRef< Value * > ArgInputs, const DenseMap< Value *, Value * > &OutputMappings, SetVector< Value * > &RemappedArgInputs)
Find the original value for the ArgInput values if any one of them was replaced during a previous ext...
static std::optional< unsigned > getGVNForPHINode(OutlinableRegion &Region, PHINode *PN, DenseSet< BasicBlock * > &Blocks, unsigned AggArgIdx)
Create a special GVN for PHINodes that will be used outside of the region.
static Value * getPassedArgumentAndAdjustArgumentLocation(const Argument *A, const OutlinableRegion &Region)
For the function call now representing the Region, find the passed value to that call that represents...
static void findCanonNumsForPHI(PHINode *PN, OutlinableRegion &Region, const DenseMap< Value *, Value * > &OutputMappings, SmallVector< std::pair< unsigned, BasicBlock * > > &CanonNums, bool ReplacedWithOutlinedCall=true)
Find the canonical numbering for the incoming Values into the PHINode PN.
static cl::opt< bool > NoCostModel("ir-outlining-no-cost", cl::init(false), cl::ReallyHidden, cl::desc("Debug option to outline greedily, without restriction that " "calculated benefit outweighs cost"))
static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB)
Move the contents of SourceBB to before the last instruction of TargetBB.
static bool nextIRInstructionDataMatchesNextInst(IRInstructionData &ID)
Checks that the next instruction in the InstructionDataList matches the next instruction in the modul...
static void moveFunctionData(Function &Old, Function &New, DenseMap< Value *, BasicBlock * > &NewEnds)
Move each BasicBlock in Old to New.
static cl::opt< bool > EnableLinkOnceODRIROutlining("enable-linkonceodr-ir-outlining", cl::Hidden, cl::desc("Enable the IR outliner on linkonceodr functions"), cl::init(false))
static void getCodeExtractorArguments(OutlinableRegion &Region, std::vector< unsigned > &InputGVNs, DenseSet< unsigned > &NotSame, DenseMap< Value *, Value * > &OutputMappings, SetVector< Value * > &ArgInputs, SetVector< Value * > &Outputs)
Find the input GVNs and the output values for a region of Instructions.
static void fillOverallFunction(Module &M, OutlinableGroup &CurrentGroup, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs, std::vector< Function * > &FuncsToRemove, const DenseMap< Value *, Value * > &OutputMappings)
Fill the new function that will serve as the replacement function for all of the extracted regions of...
static void findExtractedOutputToOverallOutputMapping(Module &M, OutlinableRegion &Region, SetVector< Value * > &Outputs)
Create a mapping of the output arguments for the Region to the output arguments of the overall outlin...
static void alignOutputBlockWithAggFunc(OutlinableGroup &OG, OutlinableRegion &Region, DenseMap< Value *, BasicBlock * > &OutputBBs, DenseMap< Value *, BasicBlock * > &EndBBs, const DenseMap< Value *, Value * > &OutputMappings, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs)
For the outlined section, move needed the StoreInsts for the output registers into their own block.
static bool collectRegionsConstants(OutlinableRegion &Region, DenseMap< unsigned, Constant * > &GVNToConstant, DenseSet< unsigned > &NotSame)
Find whether Region matches the global value numbering to Constant mapping found so far.
static PHINode * findOrCreatePHIInBlock(PHINode &PN, OutlinableRegion &Region, BasicBlock *OverallPhiBlock, const DenseMap< Value *, Value * > &OutputMappings, DenseSet< PHINode * > &UsedPHIs)
Find, or add PHINode PN to the combined PHINode Block OverallPHIBlock in order to condense the number...
static bool analyzeAndPruneOutputBlocks(DenseMap< Value *, BasicBlock * > &BlocksToPrune, OutlinableRegion &Region)
Remove empty output blocks from the outlined region.
static hash_code encodePHINodeData(PHINodeData &PND)
Encode PND as an integer for easy lookup based on the argument location, the parent BasicBlock canoni...
CallInst * replaceCalledFunction(Module &M, OutlinableRegion &Region)
Replace the extracted function in the Region with a call to the overall function constructed from the...
static void createAndInsertBasicBlocks(DenseMap< Value *, BasicBlock * > &OldMap, DenseMap< Value *, BasicBlock * > &NewMap, Function *ParentFunc, Twine BaseName)
Takes in a mapping, OldMap of ConstantValues to BasicBlocks, sorts keys, before creating a basic bloc...
static bool outputHasNonPHI(Value *V, unsigned PHILoc, PHINode &PN, SmallPtrSet< BasicBlock *, 1 > &Exits, DenseSet< BasicBlock * > &BlocksInRegion)
Check if the V has any uses outside of the region other than PN.
static void analyzeExitPHIsForOutputUses(BasicBlock *CurrentExitFromRegion, SmallPtrSet< BasicBlock *, 1 > &PotentialExitsFromRegion, DenseSet< BasicBlock * > &RegionBlocks, SetVector< Value * > &Outputs, DenseSet< Value * > &OutputsReplacedByPHINode, DenseSet< Value * > &OutputsWithNonPhiUses)
Test whether CurrentExitFromRegion contains any PhiNodes that should be considered outputs.
static void getSortedConstantKeys(std::vector< Value * > &SortedKeys, DenseMap< Value *, BasicBlock * > &Map)
A function to sort the keys of Map, which must be a mapping of constant values to basic blocks and re...
static InstructionCost findCostForOutputBlocks(Module &M, OutlinableGroup &CurrentGroup, TargetTransformInfo &TTI)
Find the extra instructions needed to handle any output values for the region.
static void replaceTargetsFromPHINode(BasicBlock *PHIBlock, BasicBlock *Find, BasicBlock *Replace, DenseSet< BasicBlock * > &Included)
Rewrite the BranchInsts in the incoming blocks to PHIBlock that are found in Included to branch to Ba...
static void findExtractedInputToOverallInputMapping(OutlinableRegion &Region, std::vector< unsigned > &InputGVNs, SetVector< Value * > &ArgInputs)
Look over the inputs and map each input argument to an argument in the overall function for the Outli...
static void mapInputsToGVNs(IRSimilarityCandidate &C, SetVector< Value * > &CurrentInputs, const DenseMap< Value *, Value * > &OutputMappings, std::vector< unsigned > &EndInputNumbers)
Find the GVN for the inputs that have been found by the CodeExtractor.
static void replaceArgumentUses(OutlinableRegion &Region, DenseMap< Value *, BasicBlock * > &OutputBBs, const DenseMap< Value *, Value * > &OutputMappings, bool FirstFunction=false)
static DISubprogram * getSubprogramOrNull(OutlinableGroup &Group)
Get the subprogram if it exists for one of the outlined regions.
static Value * findOutputMapping(const DenseMap< Value *, Value * > OutputMappings, Value *Input)
Check the OutputMappings structure for value Input, if it exists it has been used as an output for ou...
static Value * findOutputValueInRegion(OutlinableRegion &Region, unsigned OutputCanon)
For the OutputCanon number passed in find the value represented by this canonical number.
static std::optional< bool > constantMatches(Value *V, unsigned GVN, DenseMap< unsigned, Constant * > &GVNToConstant)
Find whether V matches the Constants previously found for the GVN.
static void findConstants(IRSimilarityCandidate &C, DenseSet< unsigned > &NotSame, std::vector< unsigned > &Inputs)
Find the constants that will need to be lifted into arguments as they are not the same in each instan...
void replaceConstants(OutlinableRegion &Region)
Within an extracted function, replace the constants that need to be lifted into arguments with the ac...
std::pair< unsigned, unsigned > ArgLocWithBBCanon
static Value * getPassedArgumentInAlreadyOutlinedFunction(const Argument *A, const OutlinableRegion &Region)
For the function call now representing the Region, find the passed value to that call that represents...
void createSwitchStatement(Module &M, OutlinableGroup &OG, DenseMap< Value *, BasicBlock * > &EndBBs, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs)
Create the switch statement for outlined function to differentiate between all the output blocks.
static BasicBlock * findOrCreatePHIBlock(OutlinableGroup &Group, Value *RetVal)
Find or create a BasicBlock in the outlined function containing PhiBlocks for RetVal.
std::optional< unsigned > findDuplicateOutputBlock(DenseMap< Value *, BasicBlock * > &OutputBBs, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs)
It is possible that there is a basic block that already performs the same stores.
static const T * Find(StringRef S, ArrayRef< T > A)
Find KV in array using binary search.
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
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),...
AttributeSet getFnAttrs() const
The function attributes are returned.
LLVM Basic Block Representation.
void replaceSuccessorsPhiUsesWith(BasicBlock *Old, BasicBlock *New)
Update all phi nodes in this basic block's successors to refer to basic block New instead of basic bl...
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
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.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Function * getParent() const
Return the enclosing method, or null if none.
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
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...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
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 shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
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 ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This is an important base class in LLVM.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const
Get all nodes dominated by R, including R itself.
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Class to represent function types.
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
const BasicBlock & getEntryBlock() const
FunctionType * getFunctionType() const
Returns the FunctionType for me.
const BasicBlock & back() const
AttributeList getAttributes() const
Return the attribute list for this Function.
bool hasOptNone() const
Do not optimize this function (-O0).
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.
Argument * getArg(unsigned i) const
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
bool hasLinkOnceODRLinkage() const
@ InternalLinkage
Rename collisions when linking (static functions).
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
This class is a pass that identifies similarity in a Module, extracts instances of the similarity,...
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
This is a class that wraps a range of IRInstructionData from one point to another in the vector of IR...
Instruction * backInstruction()
std::optional< unsigned > getGVN(Value *V)
Finds the positive number associated with V if it has been mapped.
unsigned getEndIdx() const
void getBasicBlocks(DenseSet< BasicBlock * > &BBSet) const
unsigned getStartIdx() const
BasicBlock * getStartBB()
std::optional< unsigned > getCanonicalNum(unsigned N)
Find the canonical number from the global value number N stored in the candidate.
IRInstructionData * front() const
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const BasicBlock * getParent() const
const Function * getFunction() const
Return the function this instruction belongs to.
bool isTerminator() const
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
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.
An instruction for reading from memory.
Value * getPointerOperand()
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
void getNameWithPrefix(raw_ostream &OS, const GlobalValue *GV, bool CannotUsePrivateLabel) const
Print the appropriate prefix and the specified global variable's name.
A Module instance is used to store all the information related to an LLVM module.
void setIncomingBlock(unsigned i, BasicBlock *BB)
void setIncomingValue(unsigned i, Value *V)
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.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
RegionT * getParent() const
Get the parent of the Region.
Return a value (possibly void), from a function.
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
A vector that has set insertion semantics.
ArrayRef< value_type > getArrayRef() const
size_type size() const
Determine the number of elements in the SetVector.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
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.
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.
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Analysis pass providing the TargetTransformInfo.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
static Type * getVoidTy(LLVMContext &C)
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isVoidTy() const
Return true if this is 'void'.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
void replaceUsesWithIf(Value *New, llvm::function_ref< bool(Use &U)> ShouldReplace)
Go through the uses list for this definition and make each use point to "V" if the callback ShouldRep...
bool isSwiftError() const
Return true if this value is a swifterror value.
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
bool erase(const ValueT &V)
An opaque object representing a hash code.
self_iterator getIterator()
A raw_ostream that writes to an std::string.
iterator erase(iterator I)
Remove a node by iterator; never deletes.
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
void mergeAttributesForOutlining(Function &Base, const Function &ToMerge)
Merges the functions attributes from ToMerge into function Base.
@ C
The default llvm calling convention, compatible with C.
std::vector< SimilarityGroup > SimilarityGroupList
std::vector< IRSimilarityCandidate > SimilarityGroup
initializer< Ty > init(const Ty &Val)
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
hash_code hash_value(const FixedPointSemantics &Val)
void interleave(ForwardIterator begin, ForwardIterator end, UnaryFunctor each_fn, NullaryFunctor between_fn)
An STL-style algorithm similar to std::for_each that applies a second functor between every pair of e...
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...
cl::opt< bool > DisableIndirectCalls("no-ir-sim-indirect-calls", cl::init(false), cl::ReallyHidden, cl::desc("disable outlining indirect calls."))
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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.
cl::opt< bool > DisableBranches("no-ir-sim-branch-matching", cl::init(false), cl::ReallyHidden, cl::desc("disable similarity matching, and outlining, " "across branches for debugging purposes."))
cl::opt< bool > DisableIntrinsics("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden, cl::desc("Don't match or outline intrinsics"))
auto predecessors(const MachineBasicBlock *BB)
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
void updateLoopMetadataDebugLocations(Instruction &I, function_ref< Metadata *(Metadata *)> Updater)
Update the debug locations contained within the MD_loop metadata attached to the instruction I,...
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
The OutlinableGroup holds all the overarching information for outlining a set of regions that are str...
std::optional< unsigned > SwiftErrorArgument
The argument that needs to be marked with the swifterr attribute.
std::vector< Type * > ArgumentTypes
The argument types for the function created as the overall function to replace the extracted function...
DenseSet< ArrayRef< unsigned > > OutputGVNCombinations
A set containing the different GVN store sets needed.
void findSameConstants(DenseSet< unsigned > &NotSame)
For the Regions, we look at every Value.
InstructionCost Cost
The number of added instructions needed for the outlining of the Regions.
DenseMap< unsigned, std::pair< std::pair< unsigned, unsigned >, SmallVector< unsigned, 2 > > > PHINodeGVNToGVNs
unsigned PHINodeGVNTracker
Tracker counting backwards from the highest unsigned value possible to avoid conflicting with the GVN...
std::vector< OutlinableRegion * > Regions
The sections that could be outlined.
DenseMap< hash_code, unsigned > GVNsToPHINodeGVN
bool IgnoreGroup
Flag for whether we should not consider this group of OutlinableRegions for extraction.
DenseMap< Value *, BasicBlock * > EndBBs
The return blocks for the overall function.
unsigned BranchesToOutside
The number of branches in the region target a basic block that is outside of the region.
Function * OutlinedFunction
The Function for the collective overall function.
bool InputTypesSet
Flag for whether the ArgumentTypes have been defined after the extraction of the first region.
DenseMap< Value *, BasicBlock * > PHIBlocks
The PHIBlocks with their corresponding return block based on the return value as the key.
FunctionType * OutlinedFunctionType
The FunctionType for the overall function.
DenseMap< unsigned, unsigned > CanonicalNumberToAggArg
The mapping of the canonical numbering of the values in outlined sections to specific arguments.
void collectGVNStoreSets(Module &M)
For the regions, look at each set of GVN stores needed and account for each combination.
InstructionCost Benefit
The number of instructions that will be outlined by extracting Regions.
unsigned NumAggregateInputs
The number of input values in ArgumentTypes.
This struct is a compact representation of a valid (non-zero power of two) alignment.
This provides the utilities for hashing an Instruction to an unsigned integer.
Instruction * Inst
The source Instruction that is being wrapped.
The OutlinableRegion holds all the information for a specific region, or sequence of instructions.
CallInst * Call
The call site of the extracted region.
InstructionCost getBenefit(TargetTransformInfo &TTI)
Get the size of the code removed from the region.
BasicBlock * FollowBB
The BasicBlock that is after the start of the region BasicBlock, only defined when the region has bee...
unsigned OutputBlockNum
The corresponding BasicBlock with the appropriate stores for this OutlinableRegion in the overall fun...
bool CandidateSplit
Flag for whether we have split out the IRSimilarityCanidate.
void splitCandidate()
For the contained region, split the parent BasicBlock at the starting and ending instructions of the ...
Value * findCorrespondingValueIn(const OutlinableRegion &Other, Value *V)
Find a corresponding value for V in similar OutlinableRegion Other.
BasicBlock * findCorrespondingBlockIn(const OutlinableRegion &Other, BasicBlock *BB)
Find a corresponding BasicBlock for BB in similar OutlinableRegion Other.
BasicBlock * PrevBB
The BasicBlock that is before the start of the region BasicBlock, only defined when the region has be...
BasicBlock * EndBB
The BasicBlock that contains the ending instruction of the region.
IRSimilarityCandidate * Candidate
Describes the region of code.
DenseMap< Value *, Value * > RemappedArguments
Values in the outlined functions will often be replaced by arguments.
Function * ExtractedFunction
The function for the extracted region.
bool EndsInBranch
Marks whether this region ends in a branch, there is special handling required for the following basi...
BasicBlock * StartBB
The BasicBlock that contains the starting instruction of the region.
void reattachCandidate()
For the contained region, reattach the BasicBlock at the starting and ending instructions of the cont...