32#define DEBUG_TYPE "iroutliner"
35using namespace IRSimilarity;
59 cl::desc(
"Enable the IR outliner on linkonceodr functions"),
66 cl::desc(
"Debug option to outline greedily, without restriction that "
67 "calculated benefit outweighs cost"));
160 I.moveBefore(TargetBB, TargetBB.
end());
170 for (
auto &VtoBB : Map)
171 SortedKeys.push_back(VtoBB.first);
175 if (SortedKeys.size() == 1) {
176 assert(!SortedKeys[0] &&
"Expected a single void value.");
184 assert(RHSC &&
"Not a constant integer in return value?");
185 assert(LHSC &&
"Not a constant integer in return value?");
194 assert(GVN &&
"No GVN for incoming value");
196 std::optional<unsigned> FirstGVN =
197 Other.Candidate->fromCanonicalNum(*CanonNum);
198 std::optional<Value *> FoundValueOpt =
Other.Candidate->fromGVN(*FirstGVN);
199 return FoundValueOpt.value_or(
nullptr);
206 assert(FirstNonPHI &&
"block is empty?");
208 if (!CorrespondingVal)
211 cast<Instruction>(CorrespondingVal)->
getParent();
212 return CorrespondingBlock;
229 for (
unsigned Idx = 0, PNEnd = PN.getNumIncomingValues();
Idx != PNEnd;
238 assert(BI &&
"Not a branch instruction?");
267 assert(EndInst &&
"Expected an end instruction?");
279 assert(StartInst &&
"Expected a start instruction?");
298 while (
PHINode *PN = dyn_cast<PHINode>(&*It)) {
299 unsigned NumPredsOutsideRegion = 0;
300 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
301 if (!BBSet.
contains(PN->getIncomingBlock(i))) {
302 PHIPredBlock = PN->getIncomingBlock(i);
303 ++NumPredsOutsideRegion;
310 IBlock = PN->getIncomingBlock(i);
311 if (IBlock ==
EndBB && EndBBTermAndBackInstDifferent) {
312 PHIPredBlock = PN->getIncomingBlock(i);
313 ++NumPredsOutsideRegion;
317 if (NumPredsOutsideRegion > 1)
325 if (isa<PHINode>(StartInst) && StartInst != &*
StartBB->
begin())
330 if (isa<PHINode>(BackInst) &&
397 assert(
StartBB !=
nullptr &&
"StartBB for Candidate is not defined!");
415 "PrevBB has more than one predecessor. Should be 0 or 1.");
439 assert(
FollowBB !=
nullptr &&
"FollowBB for Candidate is not defined!");
467static std::optional<bool>
471 Constant *CST = dyn_cast<Constant>(V);
481 std::tie(GVNToConstantIt, Inserted) =
482 GVNToConstant.
insert(std::make_pair(GVN, CST));
485 if (Inserted || (GVNToConstantIt->second == CST))
508 switch (
I->getOpcode()) {
509 case Instruction::FDiv:
510 case Instruction::FRem:
511 case Instruction::SDiv:
512 case Instruction::SRem:
513 case Instruction::UDiv:
514 case Instruction::URem:
538 OutputMappings.
find(Input);
539 if (OutputMapping != OutputMappings.
end())
540 return OutputMapping->second;
557 bool ConstantsTheSame =
true;
566 std::optional<unsigned> GVNOpt =
C.getGVN(V);
567 assert(GVNOpt &&
"Expected a GVN for operand?");
568 unsigned GVN = *GVNOpt;
572 if (isa<Constant>(V))
573 ConstantsTheSame =
false;
581 std::optional<bool> ConstantMatches =
583 if (ConstantMatches) {
584 if (*ConstantMatches)
587 ConstantsTheSame =
false;
593 if (GVNToConstant.
find(GVN) != GVNToConstant.
end())
594 ConstantsTheSame =
false;
600 return ConstantsTheSame;
612 OutputGVNCombinations.insert(OS->GVNStores);
617 if (OutputGVNCombinations.size() > 1)
635 unsigned FunctionNameSuffix) {
648 Type *ExtractedFuncType =
R->ExtractedFunction->getReturnType();
651 RetTy = ExtractedFuncType;
661 "outlined_ir_func_" + std::to_string(FunctionNameSuffix), M);
666 Attribute::SwiftError);
678 DIFile *Unit = SP->getFile();
686 Unit ,
F->getName(), MangledNameStream.str(),
689 DB.createSubroutineType(
690 DB.getOrCreateTypeArray(std::nullopt)),
692 DINode::DIFlags::FlagArtificial ,
694 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
697 DB.finalizeSubprogram(OutlinedSP);
700 F->setSubprogram(OutlinedSP);
716 CurrBB.removeFromParent();
717 CurrBB.insertInto(&New);
724 NewEnds.
insert(std::make_pair(RI->getReturnValue(), &CurrBB));
726 std::vector<Instruction *> DebugInsts;
731 if (!isa<CallInst>(&Val)) {
740 if (
auto *Loc = dyn_cast_or_null<DILocation>(MD))
742 Loc->getColumn(), SP,
nullptr);
750 CallInst *CI = cast<CallInst>(&Val);
756 if (isa<DbgInfoIntrinsic>(CI)) {
757 DebugInsts.push_back(&Val);
769 I->eraseFromParent();
783 std::vector<unsigned> &Inputs) {
787 for (IRInstructionDataList::iterator IDIt =
C.begin(), EndIDIt =
C.end();
788 IDIt != EndIDIt; IDIt++) {
789 for (
Value *V : (*IDIt).OperVals) {
792 unsigned GVN = *
C.getGVN(V);
793 if (isa<Constant>(V))
795 Inputs.push_back(GVN);
815 std::vector<unsigned> &EndInputNumbers) {
819 for (
Value *Input : CurrentInputs) {
820 assert(Input &&
"Have a nullptr as an input");
821 if (OutputMappings.
find(Input) != OutputMappings.
end())
822 Input = OutputMappings.
find(Input)->second;
823 assert(
C.getGVN(Input) &&
"Could not find a numbering for the given input");
824 EndInputNumbers.push_back(*
C.getGVN(Input));
842 for (
Value *Input : ArgInputs) {
843 if (OutputMappings.
find(Input) != OutputMappings.
end())
844 Input = OutputMappings.
find(Input)->second;
845 RemappedArgInputs.
insert(Input);
888 CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands);
889 assert(
Region.StartBB &&
"Region must have a start BasicBlock!");
896 if (!CE->isEligible()) {
897 Region.IgnoreRegion =
true;
902 CE->findAllocas(CEAC, SinkCands, HoistCands, Dummy);
903 CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands);
910 if (OverallInputs.
size() != PremappedInputs.
size()) {
911 Region.IgnoreRegion =
true;
939 std::vector<unsigned> &InputGVNs,
946 unsigned TypeIndex = 0;
949 unsigned OriginalIndex = 0;
960 for (
unsigned InputVal : InputGVNs) {
961 std::optional<unsigned> CanonicalNumberOpt =
C.getCanonicalNum(InputVal);
962 assert(CanonicalNumberOpt &&
"Canonical number not found?");
963 unsigned CanonicalNumber = *CanonicalNumberOpt;
965 std::optional<Value *> InputOpt =
C.fromGVN(InputVal);
966 assert(InputOpt &&
"Global value number not found?");
967 Value *Input = *InputOpt;
979 "Argument already marked with swifterr for this OutlinableGroup!");
986 if (
Constant *CST = dyn_cast<Constant>(Input)) {
988 Region.AggArgToConstant.insert(std::make_pair(AggArgIt->second, CST));
991 std::make_pair(CanonicalNumber, TypeIndex));
992 Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST));
1000 assert(ArgInputs.
count(Input) &&
"Input cannot be found!");
1003 if (OriginalIndex != AggArgIt->second)
1004 Region.ChangedArgOrder =
true;
1005 Region.ExtractedArgToAgg.insert(
1006 std::make_pair(OriginalIndex, AggArgIt->second));
1007 Region.AggArgToExtracted.insert(
1008 std::make_pair(AggArgIt->second, OriginalIndex));
1011 std::make_pair(CanonicalNumber, TypeIndex));
1012 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex));
1013 Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex));
1028 Region.NumExtractedInputs = OriginalIndex;
1047 [PHILoc, &PN, V, &BlocksInRegion](
unsigned Idx) {
1048 return (Idx != PHILoc && V == PN.getIncomingValue(Idx) &&
1049 !BlocksInRegion.contains(PN.getIncomingBlock(Idx)));
1055 Instruction *I = dyn_cast<Instruction>(U);
1062 BasicBlock *Parent = I->getParent();
1063 if (BlocksInRegion.contains(Parent))
1069 if (!isa<PHINode>(I))
1076 if (!Exits.contains(Parent))
1103 for (
PHINode &PN : CurrentExitFromRegion->
phis()) {
1106 for (
unsigned I = 0,
E = PN.getNumIncomingValues();
I <
E; ++
I)
1107 if (RegionBlocks.
contains(PN.getIncomingBlock(
I)))
1111 unsigned NumIncomingVals = IncomingVals.
size();
1112 if (NumIncomingVals == 0)
1117 if (NumIncomingVals == 1) {
1118 Value *V = PN.getIncomingValue(*IncomingVals.
begin());
1119 OutputsWithNonPhiUses.
insert(V);
1120 OutputsReplacedByPHINode.
erase(V);
1130 for (
unsigned Idx : IncomingVals) {
1131 Value *V = PN.getIncomingValue(
Idx);
1133 OutputsWithNonPhiUses.
insert(V);
1134 OutputsReplacedByPHINode.
erase(V);
1137 if (!OutputsWithNonPhiUses.
contains(V))
1138 OutputsReplacedByPHINode.
insert(V);
1181 unsigned AggArgIdx) {
1196 std::optional<unsigned> OGVN = Cand.
getGVN(Incoming);
1197 if (!OGVN && Blocks.
contains(IncomingBlock)) {
1198 Region.IgnoreRegion =
true;
1199 return std::nullopt;
1204 if (!Blocks.
contains(IncomingBlock))
1208 unsigned GVN = *OGVN;
1210 assert(OGVN &&
"No GVN found for incoming value?");
1215 OGVN = Cand.
getGVN(IncomingBlock);
1222 "Unknown basic block used in exit path PHINode.");
1234 assert(PrevBlock &&
"Expected a predecessor not in the reigon!");
1235 OGVN = Cand.
getGVN(PrevBlock);
1239 assert(OGVN &&
"No GVN found for incoming block?");
1248 std::optional<unsigned> BBGVN = Cand.
getGVN(PHIBB);
1249 assert(BBGVN &&
"Could not find GVN for the incoming block!");
1252 assert(BBGVN &&
"Could not find canonical number for the incoming block!");
1257 std::make_pair(std::make_pair(*BBGVN, AggArgIdx), PHIGVNs);
1264 bool Inserted =
false;
1271 return GVNToPHIIt->second;
1287 C.getBasicBlocks(BlocksInRegion, BE);
1293 if (!BlocksInRegion.
contains(Succ))
1303 OutputsReplacedByPHINode,
1304 OutputsWithNonPhiUses);
1307 unsigned OriginalIndex =
Region.NumExtractedInputs;
1320 for (
Value *Output : Outputs) {
1330 if (OutputsReplacedByPHINode.
contains(Output))
1333 unsigned AggArgIdx = 0;
1334 for (
unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {
1343 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, Jdx));
1344 Region.AggArgToExtracted.insert(std::make_pair(Jdx, OriginalIndex));
1353 Group.
ArgumentTypes.push_back(Output->getType()->getPointerTo(
1354 M.getDataLayout().getAllocaAddrSpace()));
1358 AggArgsUsed.
insert(ArgTypeIdx);
1359 Region.ExtractedArgToAgg.insert(
1360 std::make_pair(OriginalIndex, ArgTypeIdx));
1361 Region.AggArgToExtracted.insert(
1362 std::make_pair(ArgTypeIdx, OriginalIndex));
1363 AggArgIdx = ArgTypeIdx;
1367 PHINode *PN = dyn_cast<PHINode>(Output);
1369 std::optional<unsigned> GVN;
1387 GVN =
C.getGVN(Output);
1388 GVN =
C.getCanonicalNum(*GVN);
1394 Region.GVNStores.push_back(*GVN);
1407 std::vector<unsigned> Inputs;
1435 std::vector<Value *> NewCallArgs;
1440 assert(Call &&
"Call to replace is nullptr?");
1442 assert(AggFunc &&
"Function to replace with is nullptr?");
1448 if (!
Region.ChangedArgOrder && AggFunc->
arg_size() == Call->arg_size()) {
1449 LLVM_DEBUG(
dbgs() <<
"Replace call to " << *Call <<
" with call to "
1450 << *AggFunc <<
" with same number of arguments\n");
1451 Call->setCalledFunction(AggFunc);
1459 for (
unsigned AggArgIdx = 0; AggArgIdx < AggFunc->
arg_size(); AggArgIdx++) {
1461 if (AggArgIdx == AggFunc->
arg_size() - 1 &&
1467 <<
Region.OutputBlockNum <<
"\n");
1473 ArgPair =
Region.AggArgToExtracted.find(AggArgIdx);
1474 if (ArgPair !=
Region.AggArgToExtracted.
end()) {
1475 Value *ArgumentValue = Call->getArgOperand(ArgPair->second);
1479 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to value "
1480 << *ArgumentValue <<
"\n");
1481 NewCallArgs.push_back(ArgumentValue);
1486 if (
Region.AggArgToConstant.find(AggArgIdx) !=
1489 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to value "
1491 NewCallArgs.push_back(CST);
1498 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to nullptr\n");
1503 LLVM_DEBUG(
dbgs() <<
"Replace call to " << *Call <<
" with call to "
1504 << *AggFunc <<
" with new set of arguments\n");
1514 if (
Region.NewFront->Inst == OldCall)
1515 Region.NewFront->Inst = Call;
1516 if (
Region.NewBack->Inst == OldCall)
1517 Region.NewBack->Inst = Call;
1520 Call->setDebugLoc(
Region.Call->getDebugLoc());
1548 ReturnBlockForRetVal;
1550 ReturnBlockForRetVal = Group.
EndBBs.
find(RetVal);
1552 "Could not find output value!");
1553 BasicBlock *ReturnBB = ReturnBlockForRetVal->second;
1559 return PhiBlockForRetVal->second;
1563 bool Inserted =
false;
1566 std::tie(PhiBlockForRetVal, Inserted) =
1574 BranchesToChange.
push_back(cast<BranchInst>(Pred->getTerminator()));
1579 for (
unsigned Succ = 0, End = BI->getNumSuccessors(); Succ < End; Succ++) {
1580 if (BI->getSuccessor(Succ) != ReturnBB)
1582 BI->setSuccessor(Succ, PHIBlock);
1587 return PhiBlockForRetVal->second;
1604 return Region.Call->getArgOperand(
A->getArgNo());
1617 unsigned ArgNum =
A->getArgNo();
1621 if (
Region.AggArgToConstant.count(ArgNum))
1622 return Region.AggArgToConstant.find(ArgNum)->second;
1626 ArgNum =
Region.AggArgToExtracted.find(ArgNum)->second;
1627 return Region.Call->getArgOperand(ArgNum);
1643 SmallVector<std::pair<unsigned, BasicBlock *>> &CanonNums,
1644 bool ReplacedWithOutlinedCall =
true) {
1651 if (
Argument *
A = dyn_cast<Argument>(IVal)) {
1652 if (ReplacedWithOutlinedCall)
1662 std::optional<unsigned> GVN =
Region.Candidate->getGVN(IVal);
1663 assert(GVN &&
"No GVN for incoming value");
1664 std::optional<unsigned> CanonNum =
Region.Candidate->getCanonicalNum(*GVN);
1665 assert(CanonNum &&
"No Canonical Number for GVN");
1666 CanonNums.push_back(std::make_pair(*CanonNum, IBlock));
1717 CurrentCanonNums.
clear();
1723 if (PNCanonNums.
size() != CurrentCanonNums.
size())
1726 bool FoundMatch =
true;
1735 for (
unsigned Idx = 0, Edx = PNCanonNums.
size();
Idx < Edx; ++
Idx) {
1736 std::pair<unsigned, BasicBlock *> ToCompareTo = CurrentCanonNums[
Idx];
1737 std::pair<unsigned, BasicBlock *> ToAdd = PNCanonNums[
Idx];
1738 if (ToCompareTo.first != ToAdd.first) {
1744 Region.findCorrespondingBlockIn(*FirstRegion, ToAdd.second);
1745 assert(CorrespondingBlock &&
"Found block is nullptr");
1746 if (CorrespondingBlock != ToCompareTo.second) {
1755 UsedPHIs.
insert(&CurrPN);
1772 Region.findCorrespondingBlockIn(*FirstRegion, IncomingBlock);
1777 if (
Argument *
A = dyn_cast<Argument>(IncomingVal)) {
1785 Value *Val =
Region.findCorrespondingValueIn(*FirstRegion, IncomingVal);
1786 assert(Val &&
"Value is nullptr?");
1790 Val = RemappedIt->second;
1809 bool FirstFunction =
false) {
1811 assert(
Region.ExtractedFunction &&
"Region has no extracted function?");
1819 for (
unsigned ArgIdx = 0; ArgIdx <
Region.ExtractedFunction->arg_size();
1823 "No mapping from extracted to outlined?");
1824 unsigned AggArgIdx =
Region.ExtractedArgToAgg.find(ArgIdx)->second;
1829 if (ArgIdx <
Region.NumExtractedInputs) {
1831 << *
Region.ExtractedFunction <<
" with " << *AggArg
1833 Arg->replaceAllUsesWith(AggArg);
1835 Region.RemappedArguments.insert(std::make_pair(V, AggArg));
1842 assert(
Arg->hasOneUse() &&
"Output argument can only have one use");
1843 User *InstAsUser =
Arg->user_back();
1844 assert(InstAsUser &&
"User is nullptr!");
1850 bool EdgeAdded =
false;
1851 if (Descendants.
size() == 0) {
1861 ReturnInst *RI = dyn_cast<ReturnInst>(DescendBB->getTerminator());
1865 auto VBBIt = OutputBBs.
find(RetVal);
1866 assert(VBBIt != OutputBBs.
end() &&
"Could not find output value!");
1872 Value *ValueOperand =
SI->getValueOperand();
1874 StoreInst *NewI = cast<StoreInst>(
I->clone());
1879 << *OutputBB <<
"\n");
1883 if (!isa<PHINode>(ValueOperand) ||
1884 Region.Candidate->getGVN(ValueOperand).has_value()) {
1888 Region.findCorrespondingValueIn(*Group.
Regions[0], ValueOperand);
1889 assert(CorrVal &&
"Value is nullptr?");
1893 PHINode *PN = cast<PHINode>(
SI->getValueOperand());
1896 if (
Region.Candidate->getGVN(PN))
1906 if (FirstFunction) {
1920 OutputMappings, UsedPHIs);
1928 I->eraseFromParent();
1931 << *
Region.ExtractedFunction <<
" with " << *AggArg
1933 Arg->replaceAllUsesWith(AggArg);
1944 for (std::pair<unsigned, Constant *> &Const :
Region.AggArgToConstant) {
1945 unsigned AggArgIdx = Const.first;
1947 assert(OutlinedFunction &&
"Overall Function is not defined?");
1958 <<
" in function " << *OutlinedFunction <<
" with "
1962 return I->getFunction() == OutlinedFunction;
1978 bool Mismatch =
false;
1979 unsigned MatchingNum = 0;
1985 for (std::pair<Value *, BasicBlock *> &VToB : CompBBs) {
1987 OutputBBs.
find(VToB.first);
1988 if (OutputBBIt == OutputBBs.
end()) {
1995 if (CompBB->
size() - 1 != OutputBB->
size()) {
2002 if (isa<BranchInst>(&
I))
2005 if (!
I.isIdenticalTo(&(*NIt))) {
2020 return std::nullopt;
2031 bool AllRemoved =
true;
2032 Value *RetValueForBB;
2036 for (std::pair<Value *, BasicBlock *> &VtoBB : BlocksToPrune) {
2037 RetValueForBB = VtoBB.first;
2038 NewBB = VtoBB.second;
2042 if (NewBB->
size() == 0) {
2055 BlocksToPrune.
erase(V);
2059 Region.OutputBlockNum = -1;
2089 std::optional<unsigned> MatchingBB =
2096 <<
Region.ExtractedFunction <<
" to " << *MatchingBB);
2098 Region.OutputBlockNum = *MatchingBB;
2099 for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs)
2100 VtoBB.second->eraseFromParent();
2104 Region.OutputBlockNum = OutputStoreBBs.size();
2106 Value *RetValueForBB;
2109 for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs) {
2110 RetValueForBB = VtoBB.first;
2111 NewBB = VtoBB.second;
2113 EndBBs.
find(RetValueForBB);
2115 <<
Region.ExtractedFunction <<
" to "
2118 OutputStoreBBs.back().insert(std::make_pair(RetValueForBB, NewBB));
2135 std::vector<Value *> SortedKeys;
2139 for (
Value *RetVal : SortedKeys) {
2144 NewMap.
insert(std::make_pair(RetVal, NewBB));
2173 for (std::pair<Value *, BasicBlock *> &RetBlockPair : ReturnBBs) {
2174 std::pair<Value *, BasicBlock *> &OutputBlock =
2176 BasicBlock *ReturnBlock = RetBlockPair.second;
2181 Term->moveBefore(*ReturnBlock, ReturnBlock->
end());
2184 LLVM_DEBUG(
dbgs() <<
"Create switch statement in " << *AggFunc <<
" for "
2185 << OutputStoreBBs.
size() <<
"\n");
2188 ReturnBlock, OutputStoreBBs.
size(), EndBB);
2193 OutputStoreBB.
find(OutputBlock.first);
2195 if (OSBBIt == OutputStoreBB.
end())
2202 Term->setSuccessor(0, ReturnBlock);
2209 assert(OutputStoreBBs.size() < 2 &&
"Different store sets not handled!");
2217 if (OutputStoreBBs.size() == 1) {
2218 LLVM_DEBUG(
dbgs() <<
"Move store instructions to the end block in "
2221 for (std::pair<Value *, BasicBlock *> &VBPair : OutputBlocks) {
2223 EndBBs.
find(VBPair.first);
2224 assert(EndBBIt != EndBBs.
end() &&
"Could not find end block");
2228 Term->eraseFromParent();
2231 Term->moveBefore(*EndBB, EndBB->
end());
2253 std::vector<Function *> &FuncsToRemove,
2282 for (std::pair<Value *, BasicBlock *> &VToBB : NewBBs) {
2287 OutputStoreBBs.back().insert(VToBB);
2299void IROutliner::deduplicateExtractedSections(
2301 std::vector<Function *> &FuncsToRemove,
unsigned &OutlinedFunctionNum) {
2302 createFunction(M, CurrentGroup, OutlinedFunctionNum);
2304 std::vector<DenseMap<Value *, BasicBlock *>> OutputStoreBBs;
2311 std::vector<Value *> SortedKeys;
2322 "output_block_" +
Twine(
static_cast<unsigned>(
Idx)));
2325 CurrentGroup.
EndBBs, OutputMappings,
2335 OutlinedFunctionNum++;
2352 IRInstructionDataList::iterator NextIDIt = std::next(
ID.getIterator());
2355 if (!
ID.Inst->isTerminator())
2356 NextModuleInst =
ID.Inst->getNextNonDebugInstruction();
2357 else if (NextIDLInst !=
nullptr)
2361 if (NextIDLInst && NextIDLInst != NextModuleInst)
2367bool IROutliner::isCompatibleWithAlreadyOutlinedCode(
2375 for (
unsigned Idx = StartIdx;
Idx <= EndIdx;
Idx++)
2381 if (!
Region.Candidate->backInstruction()->isTerminator()) {
2383 Region.Candidate->backInstruction()->getNextNonDebugInstruction();
2384 assert(NewEndInst &&
"Next instruction is a nullptr?");
2385 if (
Region.Candidate->
end()->Inst != NewEndInst) {
2389 InstructionClassifier.visit(*NewEndInst), *IDL);
2401 return !this->InstructionClassifier.visit(
ID.Inst);
2405void IROutliner::pruneIncompatibleRegions(
2406 std::vector<IRSimilarityCandidate> &CandidateVec,
2408 bool PreviouslyOutlined;
2413 return LHS.getStartIdx() <
RHS.getStartIdx();
2419 if (FirstCandidate.getLength() == 2) {
2420 if (isa<CallInst>(FirstCandidate.front()->Inst) &&
2421 isa<BranchInst>(FirstCandidate.back()->Inst))
2425 unsigned CurrentEndIdx = 0;
2427 PreviouslyOutlined =
false;
2432 for (
unsigned Idx = StartIdx;
Idx <= EndIdx;
Idx++)
2434 PreviouslyOutlined =
true;
2438 if (PreviouslyOutlined)
2444 return ID.Inst->getParent()->hasAddressTaken();
2447 if (BBHasAddressTaken)
2455 dbgs() <<
"... Skipping function with nooutline attribute: "
2456 << FnForCurrCand.
getName() <<
"\n";
2462 !OutlineFromLinkODRs)
2467 if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
2474 return !this->InstructionClassifier.visit(
ID.Inst);
2482 CurrentGroup.
Regions.push_back(OS);
2484 CurrentEndIdx = EndIdx;
2495 RegionBenefit +=
Region->getBenefit(
TTI);
2497 <<
" saved instructions to overfall benefit.\n");
2500 return RegionBenefit;
2512 unsigned OutputCanon) {
2520 "Could not find GVN set for PHINode number!");
2521 assert(It->second.second.size() > 0 &&
"PHINode does not have any values!");
2522 OutputCanon = *It->second.second.begin();
2524 std::optional<unsigned> OGVN =
2525 Region.Candidate->fromCanonicalNum(OutputCanon);
2526 assert(OGVN &&
"Could not find GVN for Canonical Number?");
2527 std::optional<Value *> OV =
Region.Candidate->fromGVN(*OGVN);
2528 assert(OV &&
"Could not find value for GVN?");
2539 for (
unsigned OutputCanon :
Region->GVNStores) {
2546 <<
" instructions to cost for output of type "
2548 OverallCost += LoadCost;
2567 unsigned NumOutputBranches = 0;
2578 if (!isa<BranchInst>(
ID.Inst))
2581 for (
Value *V :
ID.OperVals) {
2583 if (!CandidateBlocks.
contains(BB) && FoundBlocks.
insert(BB).second)
2584 NumOutputBranches++;
2592 for (
unsigned OutputCanon : OutputUse) {
2602 <<
" instructions to cost for output of type "
2604 OutputCost += StoreCost * NumOutputBranches;
2609 LLVM_DEBUG(
dbgs() <<
"Adding " << BranchCost <<
" to the current cost for"
2610 <<
" a branch instruction\n");
2611 OutputCost += BranchCost * NumOutputBranches;
2625 InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
2628 <<
" instructions for each switch case for each different"
2629 <<
" output path in a function\n");
2630 OutputCost += TotalCost * NumOutputBranches;
2637 InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
2638 CurrentGroup.
Benefit += RegionBenefit;
2641 InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);
2642 CurrentGroup.
Cost += OutputReloadCost;
2646 RegionBenefit / CurrentGroup.
Regions.size();
2647 unsigned OverallArgumentNum = CurrentGroup.
ArgumentTypes.size();
2648 unsigned NumRegions = CurrentGroup.
Regions.size();
2650 getTTI(*CurrentGroup.
Regions[0]->Candidate->getFunction());
2655 <<
" instructions to cost for body of new function.\n");
2656 CurrentGroup.
Cost += AverageRegionBenefit;
2662 <<
" instructions to cost for each argument in the new"
2664 CurrentGroup.
Cost +=
2672 <<
" instructions to cost for each argument in the new"
2673 <<
" function " << NumRegions <<
" times for the "
2674 <<
"needed argument handling at the call site.\n");
2675 CurrentGroup.
Cost +=
2688 std::optional<unsigned> OutputIdx;
2690 for (
unsigned ArgIdx =
Region.NumExtractedInputs;
2691 ArgIdx < Region.Call->arg_size(); ArgIdx++) {
2692 if (Operand ==
Region.Call->getArgOperand(ArgIdx)) {
2693 OutputIdx = ArgIdx -
Region.NumExtractedInputs;
2703 if (OutputMappings.find(Outputs[*OutputIdx]) == OutputMappings.end()) {
2704 LLVM_DEBUG(
dbgs() <<
"Mapping extracted output " << *LI <<
" to "
2705 << *Outputs[*OutputIdx] <<
"\n");
2706 OutputMappings.insert(std::make_pair(LI, Outputs[*OutputIdx]));
2708 Value *Orig = OutputMappings.find(Outputs[*OutputIdx])->second;
2709 LLVM_DEBUG(
dbgs() <<
"Mapping extracted output " << *Orig <<
" to "
2710 << *Outputs[*OutputIdx] <<
"\n");
2711 OutputMappings.insert(std::make_pair(LI, Orig));
2717 assert(
Region.StartBB &&
"StartBB for the OutlinableRegion is nullptr!");
2721 Region.ExtractedFunction =
2722 Region.CE->extractCodeRegion(CEAC, ArgInputs, Outputs);
2726 if (!
Region.ExtractedFunction) {
2729 Region.reattachCandidate();
2737 User *InstAsUser =
Region.ExtractedFunction->user_back();
2741 if (
Region.PrevBB == InitialStart) {
2750 Region.StartBB = RewrittenBB;
2751 Region.EndBB = RewrittenBB;
2762 *BeginRewritten, InstructionClassifier.visit(*BeginRewritten), *IDL);
2764 *EndRewritten, InstructionClassifier.visit(*EndRewritten), *IDL);
2775 assert(RewrittenBB !=
nullptr &&
2776 "Could not find a predecessor after extraction!");
2781 if (
CallInst *CI = dyn_cast<CallInst>(&
I)) {
2782 if (
Region.ExtractedFunction == CI->getCalledFunction())
2784 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(&
I))
2786 Region.reattachCandidate();
2790unsigned IROutliner::doOutline(
Module &M) {
2800 unsigned OutlinedFunctionNum = 0;
2803 if (SimilarityCandidates.size() > 1)
2805 [](
const std::vector<IRSimilarityCandidate> &LHS,
2806 const std::vector<IRSimilarityCandidate> &RHS) {
2807 return LHS[0].getLength() *
LHS.size() >
2808 RHS[0].getLength() *
RHS.size();
2812 std::vector<OutlinableGroup> PotentialGroups(SimilarityCandidates.size());
2815 std::vector<OutlinableGroup *> NegativeCostGroups;
2816 std::vector<OutlinableRegion *> OutlinedRegions;
2818 unsigned PotentialGroupIdx = 0;
2823 pruneIncompatibleRegions(CandidateVec, CurrentGroup);
2828 if (CurrentGroup.
Regions.size() < 2)
2842 OutlinedRegions.clear();
2857 OS->
CE =
new (ExtractorAllocator.Allocate())
2858 CodeExtractor(BE,
nullptr,
false,
nullptr,
nullptr,
nullptr,
false,
2859 false,
nullptr,
"outlined");
2860 findAddInputsOutputs(M, *OS, NotSame);
2862 OutlinedRegions.push_back(OS);
2869 CurrentGroup.
Regions = std::move(OutlinedRegions);
2871 if (CurrentGroup.
Regions.empty())
2877 findCostBenefit(M, CurrentGroup);
2881 if (CurrentGroup.
Cost >= CurrentGroup.
Benefit && CostModel) {
2883 getORE(*CurrentGroup.
Regions[0]->Candidate->getFunction());
2887 C->frontInstruction());
2888 R <<
"did not outline "
2890 <<
" regions due to estimated increase of "
2891 <<
ore::NV(
"InstructionIncrease",
2893 <<
" instructions at locations ";
2899 Region->Candidate->frontInstruction()->getDebugLoc());
2901 [&R]() { R <<
" "; });
2907 NegativeCostGroups.push_back(&CurrentGroup);
2910 ExtractorAllocator.DestroyAll();
2912 if (NegativeCostGroups.size() > 1)
2915 return LHS->Benefit -
LHS->Cost >
RHS->Benefit -
RHS->Cost;
2918 std::vector<Function *> FuncsToRemove;
2922 OutlinedRegions.clear();
2926 if (!isCompatibleWithAlreadyOutlinedCode(*
Region))
2928 OutlinedRegions.push_back(
Region);
2931 if (OutlinedRegions.size() < 2)
2936 CurrentGroup.
Regions = std::move(OutlinedRegions);
2939 CurrentGroup.
Cost = 0;
2940 findCostBenefit(M, CurrentGroup);
2944 OutlinedRegions.clear();
2946 Region->splitCandidate();
2947 if (!
Region->CandidateSplit)
2949 OutlinedRegions.push_back(
Region);
2952 CurrentGroup.
Regions = std::move(OutlinedRegions);
2953 if (CurrentGroup.
Regions.size() < 2) {
2955 R->reattachCandidate();
2960 <<
" and benefit " << CurrentGroup.
Benefit <<
"\n");
2963 OutlinedRegions.clear();
2968 OS->
CE =
new (ExtractorAllocator.Allocate())
2969 CodeExtractor(BE,
nullptr,
false,
nullptr,
nullptr,
nullptr,
false,
2970 false,
nullptr,
"outlined");
2971 bool FunctionOutlined = extractSection(*OS);
2972 if (FunctionOutlined) {
2975 for (
unsigned Idx = StartIdx;
Idx <= EndIdx;
Idx++)
2978 OutlinedRegions.push_back(OS);
2983 <<
" with benefit " << CurrentGroup.
Benefit
2984 <<
" and cost " << CurrentGroup.
Cost <<
"\n");
2986 CurrentGroup.
Regions = std::move(OutlinedRegions);
2988 if (CurrentGroup.
Regions.empty())
2992 getORE(*CurrentGroup.
Regions[0]->Call->getFunction());
2996 R <<
"outlined " <<
ore::NV(std::to_string(CurrentGroup.
Regions.size()))
2997 <<
" regions with decrease of "
2999 <<
" instructions at locations ";
3003 R << ore::NV(
"DebugLoc",
3004 Region->Candidate->frontInstruction()->getDebugLoc());
3006 [&R]() { R <<
" "; });
3010 deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,
3011 OutlinedFunctionNum);
3015 F->eraseFromParent();
3017 return OutlinedFunctionNum;
3024 return doOutline(M) > 0;
3029class IROutlinerLegacyPass :
public ModulePass {
3042 bool runOnModule(
Module &M)
override;
3046bool IROutlinerLegacyPass::runOnModule(
Module &M) {
3050 std::unique_ptr<OptimizationRemarkEmitter> ORE;
3057 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
3061 return this->getAnalysis<IRSimilarityIdentifierWrapperPass>().getIRSI();
3080 std::unique_ptr<OptimizationRemarkEmitter> ORE;
3092char IROutlinerLegacyPass::ID = 0;
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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
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 the constants that will need to be lifted into arguments as they are not the same in each in...
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.
Statically lint checks LLVM IR
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.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
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)
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.
An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...
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.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
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.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
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.
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.
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.
ArrayRef< T > getArrayRef() const
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.
User * getUser() const
Returns the User that contains this Use.
void setOperand(unsigned i, Value *Val)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ 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."))
void initializeIROutlinerLegacyPassPass(PassRegistry &)
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)
ModulePass * createIROutlinerPass()
createIROutlinerPass - This pass finds similar code regions and factors those regions out into functi...
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.
CodeExtractor * CE
Used to create an outlined function.
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.
bool IgnoreRegion
Flag for whether we should not consider this region for extraction.
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...