Go to the documentation of this file.
28 #define DEBUG_TYPE "iroutliner"
31 using namespace IRSimilarity;
40 cl::desc(
"Enable the IR outliner on linkonceodr functions"),
47 cl::desc(
"Debug option to outline greedily, without restriction that "
48 "calculated benefit outweighs cost"));
69 bool IgnoreGroup =
false;
81 bool InputTypesSet =
false;
85 unsigned NumAggregateInputs = 0;
110 void collectGVNStoreSets(
Module &M);
119 for (BBCurr = SourceBB.
begin(), BBEnd = SourceBB.
end(); BBCurr != BBEnd;
121 BBNext = std::next(BBCurr);
122 BBCurr->moveBefore(TargetBB, TargetBB.
end());
127 assert(!CandidateSplit &&
"Candidate already split!");
129 Instruction *StartInst = (*Candidate->begin()).Inst;
131 assert(StartInst && EndInst &&
"Expected a start and end instruction?");
150 std::string OriginalName = PrevBB->
getName().
str();
152 StartBB = PrevBB->splitBasicBlock(StartInst, OriginalName +
"_to_outline");
157 FollowBB = EndBB->splitBasicBlock(EndInst, OriginalName +
"_after_outline");
159 CandidateSplit =
true;
163 assert(CandidateSplit &&
"Candidate is not split!");
179 assert(StartBB !=
nullptr &&
"StartBB for Candidate is not defined!");
180 assert(FollowBB !=
nullptr &&
"StartBB for Candidate is not defined!");
184 PrevBB = StartBB->getSinglePredecessor();
185 assert(PrevBB !=
nullptr &&
186 "No Predecessor for the region start basic block!");
188 assert(PrevBB->getTerminator() &&
"Terminator removed from PrevBB!");
189 assert(EndBB->getTerminator() &&
"Terminator removed from EndBB!");
190 PrevBB->getTerminator()->eraseFromParent();
191 EndBB->getTerminator()->eraseFromParent();
196 if (StartBB != EndBB)
200 PrevBB->replaceSuccessorsPhiUsesWith(StartBB, PrevBB);
201 PrevBB->replaceSuccessorsPhiUsesWith(FollowBB, PlacementBB);
202 StartBB->eraseFromParent();
203 FollowBB->eraseFromParent();
211 CandidateSplit =
false;
226 Constant *CST = dyn_cast<Constant>(V);
236 std::tie(GVNToConstantIt, Inserted) =
237 GVNToConstant.
insert(std::make_pair(
GVN, CST));
240 if (Inserted || (GVNToConstantIt->second == CST))
262 switch (
I.getOpcode()) {
263 case Instruction::FDiv:
264 case Instruction::FRem:
265 case Instruction::SDiv:
266 case Instruction::SRem:
267 case Instruction::UDiv:
268 case Instruction::URem:
293 bool ConstantsTheSame =
true;
308 if (isa<Constant>(V))
309 ConstantsTheSame =
false;
322 ConstantsTheSame =
false;
328 if (GVNToConstant.
find(
GVN) != GVNToConstant.
end())
329 ConstantsTheSame =
false;
335 return ConstantsTheSame;
347 OutputGVNCombinations.insert(OS->GVNStores);
352 if (OutputGVNCombinations.size() > 1)
357 unsigned FunctionNameSuffix) {
372 Attribute::SwiftError);
388 std::vector<Instruction *> DebugInsts;
389 for (CurrBB = Old.
begin(), FinalBB = Old.
end(); CurrBB != FinalBB;
391 NextBB = std::next(CurrBB);
392 CurrBB->removeFromParent();
393 CurrBB->insertInto(&New);
395 if (isa<ReturnInst>(
I))
399 assert(NewEnd &&
"No return instruction for new function?");
413 std::vector<unsigned> &Inputs) {
418 IDIt != EndIDIt; IDIt++) {
419 for (
Value *V : (*IDIt).OperVals) {
422 unsigned GVN =
C.getGVN(V).getValue();
423 if (isa<Constant>(V))
425 Inputs.push_back(
GVN);
445 std::vector<unsigned> &EndInputNumbers) {
449 for (
Value *Input : CurrentInputs) {
450 assert(Input &&
"Have a nullptr as an input");
451 if (OutputMappings.
find(Input) != OutputMappings.
end())
452 Input = OutputMappings.
find(Input)->second;
453 assert(
C.getGVN(Input).hasValue() &&
454 "Could not find a numbering for the given input");
455 EndInputNumbers.push_back(
C.getGVN(Input).getValue());
473 for (
Value *Input : ArgInputs) {
474 if (OutputMappings.
find(Input) != OutputMappings.
end())
475 Input = OutputMappings.
find(Input)->second;
476 RemappedArgInputs.
insert(Input);
519 CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands);
520 assert(
Region.StartBB &&
"Region must have a start BasicBlock!");
527 if (!CE->isEligible()) {
528 Region.IgnoreRegion =
true;
533 CE->findAllocas(CEAC, SinkCands, HoistCands,
Dummy);
534 CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands);
541 if (OverallInputs.
size() != PremappedInputs.
size()) {
542 Region.IgnoreRegion =
true;
570 std::vector<unsigned> &InputGVNs,
577 unsigned TypeIndex = 0;
580 unsigned OriginalIndex = 0;
587 for (
unsigned InputVal : InputGVNs) {
599 "Argument already marked with swifterr for this OutlinableGroup!");
606 if (
Constant *CST = dyn_cast<Constant>(Input)) {
607 Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST));
614 assert(ArgInputs.
count(Input) &&
"Input cannot be found!");
616 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex));
617 Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex));
631 Region.NumExtractedInputs = OriginalIndex;
646 unsigned OriginalIndex =
Region.NumExtractedInputs;
659 for (
Value *Output : Outputs) {
669 for (
unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {
678 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, Jdx));
679 Region.AggArgToExtracted.insert(std::make_pair(Jdx, OriginalIndex));
690 Region.ExtractedArgToAgg.insert(
691 std::make_pair(OriginalIndex, Group.
ArgumentTypes.size() - 1));
692 Region.AggArgToExtracted.insert(
693 std::make_pair(Group.
ArgumentTypes.size() - 1, OriginalIndex));
705 std::vector<unsigned> Inputs;
733 std::vector<Value *> NewCallArgs;
738 assert(Call &&
"Call to replace is nullptr?");
740 assert(AggFunc &&
"Function to replace with is nullptr?");
745 if (AggFunc->
arg_size() == Call->arg_size()) {
746 LLVM_DEBUG(
dbgs() <<
"Replace call to " << *Call <<
" with call to "
747 << *AggFunc <<
" with same number of arguments\n");
748 Call->setCalledFunction(AggFunc);
756 for (
unsigned AggArgIdx = 0; AggArgIdx < AggFunc->
arg_size(); AggArgIdx++) {
758 if (AggArgIdx == AggFunc->
arg_size() - 1 &&
764 <<
Region.OutputBlockNum <<
"\n");
770 ArgPair =
Region.AggArgToExtracted.find(AggArgIdx);
771 if (ArgPair !=
Region.AggArgToExtracted.
end()) {
772 Value *ArgumentValue = Call->getArgOperand(ArgPair->second);
776 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to value "
777 << *ArgumentValue <<
"\n");
778 NewCallArgs.push_back(ArgumentValue);
783 if (
Region.AggArgToConstant.find(AggArgIdx) !=
786 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to value "
788 NewCallArgs.push_back(CST);
795 LLVM_DEBUG(
dbgs() <<
"Setting argument " << AggArgIdx <<
" to nullptr\n");
800 LLVM_DEBUG(
dbgs() <<
"Replace call to " << *Call <<
" with call to "
801 << *AggFunc <<
" with new set of arguments\n");
811 if (
Region.NewFront->Inst == OldCall)
812 Region.NewFront->Inst = Call;
813 if (
Region.NewBack->Inst == OldCall)
814 Region.NewBack->Inst = Call;
817 Call->setDebugLoc(
Region.Call->getDebugLoc());
827 Attribute::SwiftError);
841 assert(
Region.ExtractedFunction &&
"Region has no extracted function?");
843 for (
unsigned ArgIdx = 0; ArgIdx <
Region.ExtractedFunction->arg_size();
847 "No mapping from extracted to outlined?");
848 unsigned AggArgIdx =
Region.ExtractedArgToAgg.find(ArgIdx)->second;
853 if (ArgIdx <
Region.NumExtractedInputs) {
855 << *
Region.ExtractedFunction <<
" with " << *AggArg
857 Arg->replaceAllUsesWith(AggArg);
864 assert(
Arg->hasOneUse() &&
"Output argument can only have one use");
865 User *InstAsUser =
Arg->user_back();
866 assert(InstAsUser &&
"User is nullptr!");
871 << *OutputBB <<
"\n");
873 I->moveBefore(*OutputBB, OutputBB->
end());
876 << *
Region.ExtractedFunction <<
" with " << *AggArg
878 Arg->replaceAllUsesWith(AggArg);
889 for (std::pair<unsigned, Constant *> &Const :
Region.AggArgToConstant) {
890 unsigned AggArgIdx = Const.first;
892 assert(OutlinedFunction &&
"Overall Function is not defined?");
903 <<
" in function " << *OutlinedFunction <<
" with "
907 return I->getFunction() == OutlinedFunction;
919 static std::vector<Instruction *>
922 std::vector<Instruction *> RelevantInstructions;
929 if (Inst.isLifetimeStartOrEnd())
931 if (isa<DbgInfoIntrinsic>(Inst))
934 RelevantInstructions.push_back(&Inst);
938 return RelevantInstructions;
951 bool WrongInst =
false;
952 bool WrongSize =
false;
953 unsigned MatchingNum = 0;
956 if (CompBB->size() - 1 != OutputBB->
size()) {
965 if (isa<BranchInst>(&
I))
968 if (!
I.isIdenticalTo(&(*NIt))) {
975 if (!WrongInst && !WrongSize)
1000 std::vector<BasicBlock *> &OutputStoreBBs) {
1010 OutputStoreBBs.end());
1011 ExcludeBBs.
insert(OutputBB);
1012 std::vector<Instruction *> ExtractedFunctionInsts =
1014 std::vector<Instruction *> OverallFunctionInsts =
1017 assert(ExtractedFunctionInsts.size() == OverallFunctionInsts.size() &&
1018 "Number of relevant instructions not equal!");
1020 unsigned NumInstructions = ExtractedFunctionInsts.size();
1021 for (
unsigned Idx = 0; Idx < NumInstructions; Idx++) {
1022 Value *V = ExtractedFunctionInsts[Idx];
1024 if (OutputMappings.
find(V) != OutputMappings.
end())
1025 V = OutputMappings.
find(V)->second;
1030 if (
GVN.hasValue() && ValuesToFind.
erase(
GVN.getValue())) {
1032 if (ValuesToFind.
size() == 0)
1036 if (ValuesToFind.
size() == 0)
1040 assert(ValuesToFind.
size() == 0 &&
"Not all store values were handled!");
1044 if (OutputBB->
size() == 0) {
1045 Region.OutputBlockNum = -1;
1058 <<
Region.ExtractedFunction <<
" to "
1066 Region.OutputBlockNum = OutputStoreBBs.size();
1069 <<
Region.ExtractedFunction <<
" to "
1071 OutputStoreBBs.push_back(OutputBB);
1097 LLVM_DEBUG(
dbgs() <<
"Create switch statement in " << *AggFunc <<
" for "
1098 << OutputStoreBBs.
size() <<
"\n");
1101 ReturnBlock, OutputStoreBBs.
size(), EndBB);
1107 Term =
BB->getTerminator();
1116 if (OutputStoreBBs.
size() == 1) {
1117 LLVM_DEBUG(
dbgs() <<
"Move store instructions to the end block in "
1141 std::vector<BasicBlock *> &OutputStoreBBs,
1142 std::vector<Function *> &FuncsToRemove) {
1160 M.getContext(),
Twine(
"output_block_") +
Twine(
static_cast<unsigned>(0)),
1170 if (NewBB->
size() == 0) {
1175 OutputStoreBBs.push_back(NewBB);
1186 void IROutliner::deduplicateExtractedSections(
1188 std::vector<Function *> &FuncsToRemove,
unsigned &OutlinedFunctionNum) {
1189 createFunction(M, CurrentGroup, OutlinedFunctionNum);
1191 std::vector<BasicBlock *> OutputStoreBBs;
1197 for (
unsigned Idx = 1; Idx < CurrentGroup.
Regions.size(); Idx++) {
1198 CurrentOS = CurrentGroup.
Regions[Idx];
1209 CurrentGroup.
EndBB, OutputMappings,
1219 OutlinedFunctionNum++;
1222 void IROutliner::pruneIncompatibleRegions(
1223 std::vector<IRSimilarityCandidate> &CandidateVec,
1225 bool PreviouslyOutlined;
1233 unsigned CurrentEndIdx = 0;
1235 PreviouslyOutlined =
false;
1236 unsigned StartIdx = IRSC.getStartIdx();
1237 unsigned EndIdx = IRSC.getEndIdx();
1239 for (
unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
1240 if (Outlined.contains(Idx)) {
1241 PreviouslyOutlined =
true;
1245 if (PreviouslyOutlined)
1250 if (IRSC.getStartBB()->hasAddressTaken())
1253 if (IRSC.front()->Inst->getFunction()->hasLinkOnceODRLinkage() &&
1254 !OutlineFromLinkODRs)
1259 if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
1270 if (std::next(
ID.getIterator())->Inst !=
1271 ID.Inst->getNextNonDebugInstruction())
1273 return !
this->InstructionClassifier.visit(
ID.Inst);
1281 CurrentGroup.
Regions.push_back(OS);
1283 CurrentEndIdx = EndIdx;
1288 IROutliner::findBenefitFromAllRegions(
OutlinableGroup &CurrentGroup) {
1294 RegionBenefit +=
Region->getBenefit(
TTI);
1296 <<
" saved instructions to overfall benefit.\n");
1299 return RegionBenefit;
1309 for (
unsigned OutputGVN :
Region->GVNStores) {
1318 <<
" instructions to cost for output of type "
1320 OverallCost += LoadCost;
1343 for (
unsigned GVN : OutputUse) {
1355 <<
" instructions to cost for output of type "
1357 OutputCost += StoreCost;
1362 LLVM_DEBUG(
dbgs() <<
"Adding " << BranchCost <<
" to the current cost for"
1363 <<
" a branch instruction\n");
1364 OutputCost += BranchCost;
1378 InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
1381 <<
" instructions for each switch case for each different"
1382 <<
" output path in a function\n");
1383 OutputCost += TotalCost;
1390 InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
1391 CurrentGroup.
Benefit += RegionBenefit;
1394 InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);
1395 CurrentGroup.
Cost += OutputReloadCost;
1399 RegionBenefit / CurrentGroup.
Regions.size();
1400 unsigned OverallArgumentNum = CurrentGroup.
ArgumentTypes.size();
1401 unsigned NumRegions = CurrentGroup.
Regions.size();
1403 getTTI(*CurrentGroup.
Regions[0]->Candidate->getFunction());
1408 <<
" instructions to cost for body of new function.\n");
1409 CurrentGroup.
Cost += AverageRegionBenefit;
1415 <<
" instructions to cost for each argument in the new"
1417 CurrentGroup.
Cost +=
1425 <<
" instructions to cost for each argument in the new"
1426 <<
" function " << NumRegions <<
" times for the "
1427 <<
"needed argument handling at the call site.\n");
1428 CurrentGroup.
Cost +=
1443 for (
unsigned ArgIdx =
Region.NumExtractedInputs;
1444 ArgIdx < Region.Call->arg_size(); ArgIdx++) {
1445 if (Operand ==
Region.Call->getArgOperand(ArgIdx)) {
1446 OutputIdx = ArgIdx -
Region.NumExtractedInputs;
1456 if (OutputMappings.find(Outputs[OutputIdx.
getValue()]) ==
1457 OutputMappings.end()) {
1458 LLVM_DEBUG(
dbgs() <<
"Mapping extracted output " << *LI <<
" to "
1459 << *Outputs[OutputIdx.
getValue()] <<
"\n");
1460 OutputMappings.insert(std::make_pair(LI, Outputs[OutputIdx.
getValue()]));
1462 Value *Orig = OutputMappings.find(Outputs[OutputIdx.
getValue()])->second;
1463 LLVM_DEBUG(
dbgs() <<
"Mapping extracted output " << *Orig <<
" to "
1464 << *Outputs[OutputIdx.
getValue()] <<
"\n");
1465 OutputMappings.insert(std::make_pair(LI, Orig));
1471 Region.CE->findInputsOutputs(ArgInputs, Outputs, SinkCands);
1473 assert(
Region.StartBB &&
"StartBB for the OutlinableRegion is nullptr!");
1474 assert(
Region.FollowBB &&
"FollowBB for the OutlinableRegion is nullptr!");
1477 Region.ExtractedFunction =
Region.CE->extractCodeRegion(CEAC);
1481 if (!
Region.ExtractedFunction) {
1484 Region.reattachCandidate();
1489 Region.StartBB = RewrittenBB;
1490 Region.EndBB = RewrittenBB;
1501 *BeginRewritten, InstructionClassifier.visit(*BeginRewritten), *IDL);
1503 *EndRewritten, InstructionClassifier.visit(*EndRewritten), *IDL);
1514 assert(RewrittenBB !=
nullptr &&
1515 "Could not find a predecessor after extraction!");
1520 if (
CallInst *CI = dyn_cast<CallInst>(&
I)) {
1521 if (
Region.ExtractedFunction == CI->getCalledFunction())
1523 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(&
I))
1525 Region.reattachCandidate();
1529 unsigned IROutliner::doOutline(
Module &M) {
1535 unsigned OutlinedFunctionNum = 0;
1538 if (SimilarityCandidates.size() > 1)
1540 [](
const std::vector<IRSimilarityCandidate> &LHS,
1541 const std::vector<IRSimilarityCandidate> &RHS) {
1542 return LHS[0].getLength() * LHS.size() >
1543 RHS[0].getLength() * RHS.size();
1547 std::vector<Function *> FuncsToRemove;
1553 pruneIncompatibleRegions(CandidateVec, CurrentGroup);
1558 if (CurrentGroup.
Regions.size() < 2)
1572 std::vector<OutlinableRegion *> OutlinedRegions;
1577 std::vector<BasicBlock *> BE = {OS->
StartBB};
1578 OS->
CE =
new (ExtractorAllocator.Allocate())
1579 CodeExtractor(BE,
nullptr,
false,
nullptr,
nullptr,
nullptr,
false,
1581 findAddInputsOutputs(M, *OS, NotSame);
1583 OutlinedRegions.push_back(OS);
1590 if (CurrentGroup.
Regions.empty())
1596 findCostBenefit(M, CurrentGroup);
1599 if (CurrentGroup.
Cost >= CurrentGroup.
Benefit && CostModel) {
1603 *CurrentGroup.
Regions[0]->Candidate->getFunction());
1607 C->frontInstruction());
1608 R <<
"did not outline "
1610 <<
" regions due to estimated increase of "
1611 <<
ore::NV(
"InstructionIncrease",
1613 <<
" instructions at locations ";
1619 Region->Candidate->frontInstruction()->getDebugLoc());
1621 [&R]() { R <<
" "; });
1628 <<
" and benefit " << CurrentGroup.
Benefit <<
"\n");
1631 OutlinedRegions.clear();
1633 bool FunctionOutlined = extractSection(*OS);
1634 if (FunctionOutlined) {
1637 for (
unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
1638 Outlined.insert(Idx);
1640 OutlinedRegions.push_back(OS);
1645 <<
" with benefit " << CurrentGroup.
Benefit
1646 <<
" and cost " << CurrentGroup.
Cost <<
"\n");
1650 if (CurrentGroup.
Regions.empty())
1654 getORE(*CurrentGroup.
Regions[0]->Call->getFunction());
1659 <<
" regions with decrease of "
1661 <<
" instructions at locations ";
1665 R << ore::NV(
"DebugLoc",
1666 Region->Candidate->frontInstruction()->getDebugLoc());
1668 [&R]() { R <<
" "; });
1672 deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,
1673 OutlinedFunctionNum);
1677 F->eraseFromParent();
1679 return OutlinedFunctionNum;
1686 return doOutline(
M) > 0;
1703 bool runOnModule(
Module &M)
override;
1710 std::unique_ptr<OptimizationRemarkEmitter> ORE;
1717 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1721 return this->getAnalysis<IRSimilarityIdentifierWrapperPass>().getIRSI();
1740 std::unique_ptr<OptimizationRemarkEmitter> ORE;
A set of analyses that are preserved following a run of a transformation pass.
This class represents an incoming formal argument to a Function.
Analysis pass providing the TargetTransformInfo.
void mergeAttributesForOutlining(Function &Base, const Function &ToMerge)
Merges the functions attributes from ToMerge into function Base.
This class represents lattice values for constants.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB)
Move the contents of SourceBB to before the last instruction of TargetBB.
std::vector< Type * > ArgumentTypes
The argument types for the function created as the overall function to replace the extracted function...
InstListType::iterator iterator
Instruction iterators...
void createSwitchStatement(Module &M, OutlinableGroup &OG, BasicBlock *EndBB, ArrayRef< BasicBlock * > OutputStoreBBs)
Create the switch statement for outlined function to differentiate between all the output blocks.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
void collectGVNStoreSets(Module &M)
For the regions, look at each set of GVN stores needed and account for each combination.
DenseSet< ArrayRef< unsigned > > OutputGVNCombinations
A set containing the different GVN store sets needed.
static void alignOutputBlockWithAggFunc(OutlinableGroup &OG, OutlinableRegion &Region, BasicBlock *OutputBB, BasicBlock *EndBB, const DenseMap< Value *, Value * > &OutputMappings, std::vector< BasicBlock * > &OutputStoreBBs)
For the outlined section, move needed the StoreInsts for the output registers into their own block.
size_type size() const
Determine the number of elements in the SetVector.
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
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...
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
void findSameConstants(DenseSet< unsigned > &NotSame)
For the Regions, we look at every Value.
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
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 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...
FunctionType * OutlinedFunctionType
The FunctionType for the overall function.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
ArrayRef< T > getArrayRef() const
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
std::vector< IRSimilarityCandidate > SimilarityGroup
DiagnosticInfoOptimizationBase::Argument NV
Value * getPointerOperand()
std::vector< SimilarityGroup > SimilarityGroupList
Function * OutlinedFunction
The Function for the collective overall function.
std::pair< iterator, bool > insert(const ValueT &V)
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
static IntegerType * getInt32Ty(LLVMContext &C)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
LLVM Basic Block Representation.
Optional< Value * > fromGVN(unsigned Num)
Finds the Value associate with Num if it exists.
bool isSwiftError() const
Return true if this value is a swifterror value.
constexpr bool hasValue() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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.
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...
std::vector< OutlinableRegion * > Regions
The sections that could be outlined.
static BasicBlock * moveFunctionData(Function &Old, Function &New)
Move each BasicBlock in Old to New.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...
(vector float) vec_cmpeq(*A, *B) C
AttributeSet getFnAttributes() const
The function attributes are returned.
iterator begin()
Instruction iterator methods.
unsigned NumAggregateInputs
The number of input values in ArgumentTypes.
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 CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Represent the analysis usage information of a pass.
bool InputTypesSet
Flag for whether the ArgumentTypes have been defined after the extraction of the first region.
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
User * getUser() const
Returns the User that contains this Use.
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.
Statically lint checks LLVM IR
Optional< unsigned > findDuplicateOutputBlock(BasicBlock *OutputBB, ArrayRef< BasicBlock * > OutputStoreBBs)
It is possible that there is a basic block that already performs the same stores.
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...
unsigned OutputBlockNum
The corresponding BasicBlock with the appropriate stores for this OutlinableRegion in the overall fun...
@ InternalLinkage
Rename collisions when linking (static functions).
This struct is a compact representation of a valid (non-zero power of two) alignment.
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
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::vector< Instruction * > collectRelevantInstructions(Function &F, DenseSet< BasicBlock * > &ExcludeBlocks)
For the given function, find all the nondebug or lifetime instructions, and return them as a vector.
AttributeList getAttributes() const
Return the attribute list for this Function.
unsigned getEndIdx() const
InstructionCost getBenefit(TargetTransformInfo &TTI)
Get the size of the code removed from the region.
static void replaceArgumentUses(OutlinableRegion &Region, BasicBlock *OutputBB)
Implements a dense probed hash-table based set.
Function * ExtractedFunction
The function for the extracted region.
This is an important base class in LLVM.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
The core GVN pass object.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the generic address space (address sp...
ilist_iterator< OptionsT, false, false > iterator
CallInst * Call
The call site of the extracted region.
static void findExtractedOutputToOverallOutputMapping(OutlinableRegion &Region, ArrayRef< Value * > Outputs)
Create a mapping of the output arguments for the Region to the output arguments of the overall outlin...
iterator erase(iterator I)
Remove a node by iterator; never deletes.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
initializer< Ty > init(const Ty &Val)
CodeExtractor * CE
Used to create an outlined function.
Class to represent pointers.
static void fillOverallFunction(Module &M, OutlinableGroup &CurrentGroup, std::vector< BasicBlock * > &OutputStoreBBs, std::vector< Function * > &FuncsToRemove)
Fill the new function that will serve as the replacement function for all of the extracted regions of...
iterator find(const_arg_type_t< KeyT > Val)
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void initializeIROutlinerLegacyPassPass(PassRegistry &)
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.
This provides the utilities for hashing an Instruction to an unsigned integer.
print Print MemDeps of function
A Module instance is used to store all the information related to an LLVM module.
bool insert(const value_type &X)
Insert a new element into the SetVector.
InstructionCost Cost
The number of added instructions needed for the outlining of the Regions.
The OutlinableGroup holds all the overarching information for outlining a set of regions that are str...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
INITIALIZE_PASS_BEGIN(IROutlinerLegacyPass, "iroutliner", "IR Outliner", false, false) INITIALIZE_PASS_END(IROutlinerLegacyPass
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void splitCandidate()
For the contained region, split the parent BasicBlock at the starting and ending instructions of the ...
Analysis the ScalarEvolution expression for r is this
static Optional< bool > constantMatches(Value *V, unsigned GVN, DenseMap< unsigned, Constant * > &GVNToConstant)
Find whether V matches the Constants previously found for the GVN.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
ModulePass * createIROutlinerPass()
createIROutlinerPass - This pass finds similar code regions and factors those regions out into functi...
CallInst * replaceCalledFunction(Module &M, OutlinableRegion &Region)
Replace the extracted function in the Region with a call to the overall function constructed from the...
Type * getType() const
All values are typed, get the type of this value.
InstructionCost Benefit
The number of instructions that will be outlined by extracting Regions.
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
static InstructionCost findCostForOutputBlocks(Module &M, OutlinableGroup &CurrentGroup, TargetTransformInfo &TTI)
Find the extra instructions needed to handle any output values for the region.
bool IgnoreRegion
Flag for whether we should not consider this region for extraction.
StringRef getName() const
Return a constant reference to the value's name.
An instruction for reading from memory.
bool IgnoreGroup
Flag for whether we should not consider this group of OutlinableRegions for extraction.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
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...
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"))
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
adds the attribute to the list of attributes for the given arg.
void replaceConstants(OutlinableRegion &Region)
Within an extracted function, replace the constants that need to be lifted into arguments with the ac...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
void stable_sort(R &&Range)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Argument * getArg(unsigned i) const
The OutlinableRegion holds all the information for a specific region, or sequence of instructions.
unsigned getStartIdx() const
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
FunctionType * getFunctionType() const
Returns the FunctionType for me.
This is a class that wraps a range of IRInstructionData from one point to another in the vector of IR...
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 Type * getVoidTy(LLVMContext &C)
Optional< unsigned > SwiftErrorArgument
The argument that needs to be marked with the swifterr attribute.
const BasicBlock * getParent() const
std::string to_string(const T &Value)
size_t size() const
size - Get the array size.
bool erase(const ValueT &V)
A container for analyses that lazily runs them and caches their results.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
This class is a pass that identifies similarity in a Module, extracts instances of the similarity,...
This class represents a function call, abstracting a target machine's calling convention.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
BasicBlock * EndBB
The return block for the overall function.
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
AnalysisUsage & addRequired()
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
LLVM Value Representation.
IRSimilarityCandidate * Candidate
Describes the region of code.
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Class to represent function types.
A Use represents the edge between a Value definition and its users.
BasicBlockListType::iterator iterator
RegionT * getParent() const
Get the parent of the Region.