1	//===- IROutliner.cpp -- Outline Similar Regions ----------------*- C++ -*-===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	///
9	/// \file
10	// Implementation for the IROutliner which is used by the IROutliner Pass.
11	//
12	//===----------------------------------------------------------------------===//
13
14	#include "llvm/Transforms/IPO/IROutliner.h"
15	#include "llvm/Analysis/IRSimilarityIdentifier.h"
16	#include "llvm/Analysis/OptimizationRemarkEmitter.h"
17	#include "llvm/Analysis/TargetTransformInfo.h"
18	#include "llvm/IR/Attributes.h"
19	#include "llvm/IR/DIBuilder.h"
20	#include "llvm/IR/DebugInfo.h"
21	#include "llvm/IR/DebugInfoMetadata.h"
22	#include "llvm/IR/Dominators.h"
23	#include "llvm/IR/Mangler.h"
24	#include "llvm/IR/PassManager.h"
25	#include "llvm/Support/CommandLine.h"
26	#include "llvm/Transforms/IPO.h"
27	#include <optional>
28	#include <vector>
29
30	#define DEBUG_TYPE "iroutliner"
31
32	using namespace llvm;
33	using namespace IRSimilarity;
34
35	// A command flag to be used for debugging to exclude branches from similarity
36	// matching and outlining.
37	namespace llvm {
38	extern cl::opt<bool> DisableBranches;
39
40	// A command flag to be used for debugging to indirect calls from similarity
41	// matching and outlining.
42	extern cl::opt<bool> DisableIndirectCalls;
43
44	// A command flag to be used for debugging to exclude intrinsics from similarity
45	// matching and outlining.
46	extern cl::opt<bool> DisableIntrinsics;
47
48	} // namespace llvm
49
50	// Set to true if the user wants the ir outliner to run on linkonceodr linkage
51	// functions. This is false by default because the linker can dedupe linkonceodr
52	// functions. Since the outliner is confined to a single module (modulo LTO),
53	// this is off by default. It should, however, be the default behavior in
54	// LTO.
55	static cl::opt<bool> EnableLinkOnceODRIROutlining(
56	"enable-linkonceodr-ir-outlining", cl::Hidden,
57	cl::desc("Enable the IR outliner on linkonceodr functions"),
58	cl::init(Val: false));
59
60	// This is a debug option to test small pieces of code to ensure that outlining
61	// works correctly.
62	static cl::opt<bool> NoCostModel(
63	"ir-outlining-no-cost", cl::init(Val: false), cl::ReallyHidden,
64	cl::desc("Debug option to outline greedily, without restriction that "
65	"calculated benefit outweighs cost"));
66
67	/// The OutlinableGroup holds all the overarching information for outlining
68	/// a set of regions that are structurally similar to one another, such as the
69	/// types of the overall function, the output blocks, the sets of stores needed
70	/// and a list of the different regions. This information is used in the
71	/// deduplication of extracted regions with the same structure.
72	struct OutlinableGroup {
73	/// The sections that could be outlined
74	std::vector<OutlinableRegion *> Regions;
75
76	/// The argument types for the function created as the overall function to
77	/// replace the extracted function for each region.
78	std::vector<Type *> ArgumentTypes;
79	/// The FunctionType for the overall function.
80	FunctionType *OutlinedFunctionType = nullptr;
81	/// The Function for the collective overall function.
82	Function *OutlinedFunction = nullptr;
83
84	/// Flag for whether we should not consider this group of OutlinableRegions
85	/// for extraction.
86	bool IgnoreGroup = false;
87
88	/// The return blocks for the overall function.
89	DenseMap<Value *, BasicBlock *> EndBBs;
90
91	/// The PHIBlocks with their corresponding return block based on the return
92	/// value as the key.
93	DenseMap<Value *, BasicBlock *> PHIBlocks;
94
95	/// A set containing the different GVN store sets needed. Each array contains
96	/// a sorted list of the different values that need to be stored into output
97	/// registers.
98	DenseSet<ArrayRef<unsigned>> OutputGVNCombinations;
99
100	/// Flag for whether the \ref ArgumentTypes have been defined after the
101	/// extraction of the first region.
102	bool InputTypesSet = false;
103
104	/// The number of input values in \ref ArgumentTypes. Anything after this
105	/// index in ArgumentTypes is an output argument.
106	unsigned NumAggregateInputs = 0;
107
108	/// The mapping of the canonical numbering of the values in outlined sections
109	/// to specific arguments.
110	DenseMap<unsigned, unsigned> CanonicalNumberToAggArg;
111
112	/// The number of branches in the region target a basic block that is outside
113	/// of the region.
114	unsigned BranchesToOutside = 0;
115
116	/// Tracker counting backwards from the highest unsigned value possible to
117	/// avoid conflicting with the GVNs of assigned values. We start at -3 since
118	/// -2 and -1 are assigned by the DenseMap.
119	unsigned PHINodeGVNTracker = -3;
120
121	DenseMap<unsigned,
122	std::pair<std::pair<unsigned, unsigned>, SmallVector<unsigned, 2>>>
123	PHINodeGVNToGVNs;
124	DenseMap<hash_code, unsigned> GVNsToPHINodeGVN;
125
126	/// The number of instructions that will be outlined by extracting \ref
127	/// Regions.
128	InstructionCost Benefit = 0;
129	/// The number of added instructions needed for the outlining of the \ref
130	/// Regions.
131	InstructionCost Cost = 0;
132
133	/// The argument that needs to be marked with the swifterr attribute. If not
134	/// needed, there is no value.
135	std::optional<unsigned> SwiftErrorArgument;
136
137	/// For the \ref Regions, we look at every Value. If it is a constant,
138	/// we check whether it is the same in Region.
139	///
140	/// \param [in,out] NotSame contains the global value numbers where the
141	/// constant is not always the same, and must be passed in as an argument.
142	void findSameConstants(DenseSet<unsigned> &NotSame);
143
144	/// For the regions, look at each set of GVN stores needed and account for
145	/// each combination. Add an argument to the argument types if there is
146	/// more than one combination.
147	///
148	/// \param [in] M - The module we are outlining from.
149	void collectGVNStoreSets(Module &M);
150	};
151
152	/// Move the contents of \p SourceBB to before the last instruction of \p
153	/// TargetBB.
154	/// \param SourceBB - the BasicBlock to pull Instructions from.
155	/// \param TargetBB - the BasicBlock to put Instruction into.
156	static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB) {
157	TargetBB.splice(ToIt: TargetBB.end(), FromBB: &SourceBB);
158	}
159
160	/// A function to sort the keys of \p Map, which must be a mapping of constant
161	/// values to basic blocks and return it in \p SortedKeys
162	///
163	/// \param SortedKeys - The vector the keys will be return in and sorted.
164	/// \param Map - The DenseMap containing keys to sort.
165	static void getSortedConstantKeys(std::vector<Value *> &SortedKeys,
166	DenseMap<Value *, BasicBlock *> &Map) {
167	for (auto &VtoBB : Map)
168	SortedKeys.push_back(x: VtoBB.first);
169
170	// Here we expect to have either 1 value that is void (nullptr) or multiple
171	// values that are all constant integers.
172	if (SortedKeys.size() == 1) {
173	assert(!SortedKeys[0] && "Expected a single void value.");
174	return;
175	}
176
177	stable_sort(Range&: SortedKeys, C: [](const Value *LHS, const Value *RHS) {
178	assert(LHS && RHS && "Expected non void values.");
179	const ConstantInt *LHSC = cast<ConstantInt>(Val: LHS);
180	const ConstantInt *RHSC = cast<ConstantInt>(Val: RHS);
181
182	return LHSC->getLimitedValue() < RHSC->getLimitedValue();
183	});
184	}
185
186	Value *OutlinableRegion::findCorrespondingValueIn(const OutlinableRegion &Other,
187	Value *V) {
188	std::optional<unsigned> GVN = Candidate->getGVN(V);
189	assert(GVN && "No GVN for incoming value");
190	std::optional<unsigned> CanonNum = Candidate->getCanonicalNum(N: *GVN);
191	std::optional<unsigned> FirstGVN =
192	Other.Candidate->fromCanonicalNum(N: *CanonNum);
193	std::optional<Value *> FoundValueOpt = Other.Candidate->fromGVN(Num: *FirstGVN);
194	return FoundValueOpt.value_or(u: nullptr);
195	}
196
197	BasicBlock *
198	OutlinableRegion::findCorrespondingBlockIn(const OutlinableRegion &Other,
199	BasicBlock *BB) {
200	Instruction *FirstNonPHI = BB->getFirstNonPHIOrDbg();
201	assert(FirstNonPHI && "block is empty?");
202	Value *CorrespondingVal = findCorrespondingValueIn(Other, V: FirstNonPHI);
203	if (!CorrespondingVal)
204	return nullptr;
205	BasicBlock *CorrespondingBlock =
206	cast<Instruction>(Val: CorrespondingVal)->getParent();
207	return CorrespondingBlock;
208	}
209
210	/// Rewrite the BranchInsts in the incoming blocks to \p PHIBlock that are found
211	/// in \p Included to branch to BasicBlock \p Replace if they currently branch
212	/// to the BasicBlock \p Find. This is used to fix up the incoming basic blocks
213	/// when PHINodes are included in outlined regions.
214	///
215	/// \param PHIBlock - The BasicBlock containing the PHINodes that need to be
216	/// checked.
217	/// \param Find - The successor block to be replaced.
218	/// \param Replace - The new succesor block to branch to.
219	/// \param Included - The set of blocks about to be outlined.
220	static void replaceTargetsFromPHINode(BasicBlock *PHIBlock, BasicBlock *Find,
221	BasicBlock *Replace,
222	DenseSet<BasicBlock *> &Included) {
223	for (PHINode &PN : PHIBlock->phis()) {
224	for (unsigned Idx = 0, PNEnd = PN.getNumIncomingValues(); Idx != PNEnd;
225	++Idx) {
226	// Check if the incoming block is included in the set of blocks being
227	// outlined.
228	BasicBlock *Incoming = PN.getIncomingBlock(i: Idx);
229	if (!Included.contains(V: Incoming))
230	continue;
231
232	BranchInst *BI = dyn_cast<BranchInst>(Val: Incoming->getTerminator());
233	assert(BI && "Not a branch instruction?");
234	// Look over the branching instructions into this block to see if we
235	// used to branch to Find in this outlined block.
236	for (unsigned Succ = 0, End = BI->getNumSuccessors(); Succ != End;
237	Succ++) {
238	// If we have found the block to replace, we do so here.
239	if (BI->getSuccessor(i: Succ) != Find)
240	continue;
241	BI->setSuccessor(idx: Succ, NewSucc: Replace);
242	}
243	}
244	}
245	}
246
247
248	void OutlinableRegion::splitCandidate() {
249	assert(!CandidateSplit && "Candidate already split!");
250
251	Instruction *BackInst = Candidate->backInstruction();
252
253	Instruction *EndInst = nullptr;
254	// Check whether the last instruction is a terminator, if it is, we do
255	// not split on the following instruction. We leave the block as it is. We
256	// also check that this is not the last instruction in the Module, otherwise
257	// the check for whether the current following instruction matches the
258	// previously recorded instruction will be incorrect.
259	if (!BackInst->isTerminator() ||
260	BackInst->getParent() != &BackInst->getFunction()->back()) {
261	EndInst = Candidate->end()->Inst;
262	assert(EndInst && "Expected an end instruction?");
263	}
264
265	// We check if the current instruction following the last instruction in the
266	// region is the same as the recorded instruction following the last
267	// instruction. If they do not match, there could be problems in rewriting
268	// the program after outlining, so we ignore it.
269	if (!BackInst->isTerminator() &&
270	EndInst != BackInst->getNextNonDebugInstruction())
271	return;
272
273	Instruction *StartInst = (*Candidate->begin()).Inst;
274	assert(StartInst && "Expected a start instruction?");
275	StartBB = StartInst->getParent();
276	PrevBB = StartBB;
277
278	DenseSet<BasicBlock *> BBSet;
279	Candidate->getBasicBlocks(BBSet);
280
281	// We iterate over the instructions in the region, if we find a PHINode, we
282	// check if there are predecessors outside of the region, if there are,
283	// we ignore this region since we are unable to handle the severing of the
284	// phi node right now.
285
286	// TODO: Handle extraneous inputs for PHINodes through variable number of
287	// inputs, similar to how outputs are handled.
288	BasicBlock::iterator It = StartInst->getIterator();
289	EndBB = BackInst->getParent();
290	BasicBlock *IBlock;
291	BasicBlock *PHIPredBlock = nullptr;
292	bool EndBBTermAndBackInstDifferent = EndBB->getTerminator() != BackInst;
293	while (PHINode *PN = dyn_cast<PHINode>(Val: &*It)) {
294	unsigned NumPredsOutsideRegion = 0;
295	for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
296	if (!BBSet.contains(V: PN->getIncomingBlock(i))) {
297	PHIPredBlock = PN->getIncomingBlock(i);
298	++NumPredsOutsideRegion;
299	continue;
300	}
301
302	// We must consider the case there the incoming block to the PHINode is
303	// the same as the final block of the OutlinableRegion. If this is the
304	// case, the branch from this block must also be outlined to be valid.
305	IBlock = PN->getIncomingBlock(i);
306	if (IBlock == EndBB && EndBBTermAndBackInstDifferent) {
307	PHIPredBlock = PN->getIncomingBlock(i);
308	++NumPredsOutsideRegion;
309	}
310	}
311
312	if (NumPredsOutsideRegion > 1)
313	return;
314
315	It++;
316	}
317
318	// If the region starts with a PHINode, but is not the initial instruction of
319	// the BasicBlock, we ignore this region for now.
320	if (isa<PHINode>(Val: StartInst) && StartInst != &*StartBB->begin())
321	return;
322
323	// If the region ends with a PHINode, but does not contain all of the phi node
324	// instructions of the region, we ignore it for now.
325	if (isa<PHINode>(Val: BackInst) &&
326	BackInst != &*std::prev(x: EndBB->getFirstInsertionPt()))
327	return;
328
329	// The basic block gets split like so:
330	// block: block:
331	// inst1 inst1
332	// inst2 inst2
333	// region1 br block_to_outline
334	// region2 block_to_outline:
335	// region3 -> region1
336	// region4 region2
337	// inst3 region3
338	// inst4 region4
339	// br block_after_outline
340	// block_after_outline:
341	// inst3
342	// inst4
343
344	std::string OriginalName = PrevBB->getName().str();
345
346	StartBB = PrevBB->splitBasicBlock(I: StartInst, BBName: OriginalName + "_to_outline");
347	PrevBB->replaceSuccessorsPhiUsesWith(Old: PrevBB, New: StartBB);
348	// If there was a PHINode with an incoming block outside the region,
349	// make sure is correctly updated in the newly split block.
350	if (PHIPredBlock)
351	PrevBB->replaceSuccessorsPhiUsesWith(Old: PHIPredBlock, New: PrevBB);
352
353	CandidateSplit = true;
354	if (!BackInst->isTerminator()) {
355	EndBB = EndInst->getParent();
356	FollowBB = EndBB->splitBasicBlock(I: EndInst, BBName: OriginalName + "_after_outline");
357	EndBB->replaceSuccessorsPhiUsesWith(Old: EndBB, New: FollowBB);
358	FollowBB->replaceSuccessorsPhiUsesWith(Old: PrevBB, New: FollowBB);
359	} else {
360	EndBB = BackInst->getParent();
361	EndsInBranch = true;
362	FollowBB = nullptr;
363	}
364
365	// Refind the basic block set.
366	BBSet.clear();
367	Candidate->getBasicBlocks(BBSet);
368	// For the phi nodes in the new starting basic block of the region, we
369	// reassign the targets of the basic blocks branching instructions.
370	replaceTargetsFromPHINode(PHIBlock: StartBB, Find: PrevBB, Replace: StartBB, Included&: BBSet);
371	if (FollowBB)
372	replaceTargetsFromPHINode(PHIBlock: FollowBB, Find: EndBB, Replace: FollowBB, Included&: BBSet);
373	}
374
375	void OutlinableRegion::reattachCandidate() {
376	assert(CandidateSplit && "Candidate is not split!");
377
378	// The basic block gets reattached like so:
379	// block: block:
380	// inst1 inst1
381	// inst2 inst2
382	// br block_to_outline region1
383	// block_to_outline: -> region2
384	// region1 region3
385	// region2 region4
386	// region3 inst3
387	// region4 inst4
388	// br block_after_outline
389	// block_after_outline:
390	// inst3
391	// inst4
392	assert(StartBB != nullptr && "StartBB for Candidate is not defined!");
393
394	assert(PrevBB->getTerminator() && "Terminator removed from PrevBB!");
395	// Make sure PHINode references to the block we are merging into are
396	// updated to be incoming blocks from the predecessor to the current block.
397
398	// NOTE: If this is updated such that the outlined block can have more than
399	// one incoming block to a PHINode, this logic will have to updated
400	// to handle multiple precessors instead.
401
402	// We only need to update this if the outlined section contains a PHINode, if
403	// it does not, then the incoming block was never changed in the first place.
404	// On the other hand, if PrevBB has no predecessors, it means that all
405	// incoming blocks to the first block are contained in the region, and there
406	// will be nothing to update.
407	Instruction *StartInst = (*Candidate->begin()).Inst;
408	if (isa<PHINode>(Val: StartInst) && !PrevBB->hasNPredecessors(N: 0)) {
409	assert(!PrevBB->hasNPredecessorsOrMore(2) &&
410	"PrevBB has more than one predecessor. Should be 0 or 1.");
411	BasicBlock *BeforePrevBB = PrevBB->getSinglePredecessor();
412	PrevBB->replaceSuccessorsPhiUsesWith(Old: PrevBB, New: BeforePrevBB);
413	}
414	PrevBB->getTerminator()->eraseFromParent();
415
416	// If we reattaching after outlining, we iterate over the phi nodes to
417	// the initial block, and reassign the branch instructions of the incoming
418	// blocks to the block we are remerging into.
419	if (!ExtractedFunction) {
420	DenseSet<BasicBlock *> BBSet;
421	Candidate->getBasicBlocks(BBSet);
422
423	replaceTargetsFromPHINode(PHIBlock: StartBB, Find: StartBB, Replace: PrevBB, Included&: BBSet);
424	if (!EndsInBranch)
425	replaceTargetsFromPHINode(PHIBlock: FollowBB, Find: FollowBB, Replace: EndBB, Included&: BBSet);
426	}
427
428	moveBBContents(SourceBB&: *StartBB, TargetBB&: *PrevBB);
429
430	BasicBlock *PlacementBB = PrevBB;
431	if (StartBB != EndBB)
432	PlacementBB = EndBB;
433	if (!EndsInBranch && PlacementBB->getUniqueSuccessor() != nullptr) {
434	assert(FollowBB != nullptr && "FollowBB for Candidate is not defined!");
435	assert(PlacementBB->getTerminator() && "Terminator removed from EndBB!");
436	PlacementBB->getTerminator()->eraseFromParent();
437	moveBBContents(SourceBB&: *FollowBB, TargetBB&: *PlacementBB);
438	PlacementBB->replaceSuccessorsPhiUsesWith(Old: FollowBB, New: PlacementBB);
439	FollowBB->eraseFromParent();
440	}
441
442	PrevBB->replaceSuccessorsPhiUsesWith(Old: StartBB, New: PrevBB);
443	StartBB->eraseFromParent();
444
445	// Make sure to save changes back to the StartBB.
446	StartBB = PrevBB;
447	EndBB = nullptr;
448	PrevBB = nullptr;
449	FollowBB = nullptr;
450
451	CandidateSplit = false;
452	}
453
454	/// Find whether \p V matches the Constants previously found for the \p GVN.
455	///
456	/// \param V - The value to check for consistency.
457	/// \param GVN - The global value number assigned to \p V.
458	/// \param GVNToConstant - The mapping of global value number to Constants.
459	/// \returns true if the Value matches the Constant mapped to by V and false if
460	/// it \p V is a Constant but does not match.
461	/// \returns std::nullopt if \p V is not a Constant.
462	static std::optional<bool>
463	constantMatches(Value *V, unsigned GVN,
464	DenseMap<unsigned, Constant *> &GVNToConstant) {
465	// See if we have a constants
466	Constant *CST = dyn_cast<Constant>(Val: V);
467	if (!CST)
468	return std::nullopt;
469
470	// Holds a mapping from a global value number to a Constant.
471	DenseMap<unsigned, Constant *>::iterator GVNToConstantIt;
472	bool Inserted;
473
474
475	// If we have a constant, try to make a new entry in the GVNToConstant.
476	std::tie(args&: GVNToConstantIt, args&: Inserted) =
477	GVNToConstant.insert(KV: std::make_pair(x&: GVN, y&: CST));
478	// If it was found and is not equal, it is not the same. We do not
479	// handle this case yet, and exit early.
480	if (Inserted || (GVNToConstantIt->second == CST))
481	return true;
482
483	return false;
484	}
485
486	InstructionCost OutlinableRegion::getBenefit(TargetTransformInfo &TTI) {
487	InstructionCost Benefit = 0;
488
489	// Estimate the benefit of outlining a specific sections of the program. We
490	// delegate mostly this task to the TargetTransformInfo so that if the target
491	// has specific changes, we can have a more accurate estimate.
492
493	// However, getInstructionCost delegates the code size calculation for
494	// arithmetic instructions to getArithmeticInstrCost in
495	// include/Analysis/TargetTransformImpl.h, where it always estimates that the
496	// code size for a division and remainder instruction to be equal to 4, and
497	// everything else to 1. This is not an accurate representation of the
498	// division instruction for targets that have a native division instruction.
499	// To be overly conservative, we only add 1 to the number of instructions for
500	// each division instruction.
501	for (IRInstructionData &ID : *Candidate) {
502	Instruction *I = ID.Inst;
503	switch (I->getOpcode()) {
504	case Instruction::FDiv:
505	case Instruction::FRem:
506	case Instruction::SDiv:
507	case Instruction::SRem:
508	case Instruction::UDiv:
509	case Instruction::URem:
510	Benefit += 1;
511	break;
512	default:
513	Benefit += TTI.getInstructionCost(U: I, CostKind: TargetTransformInfo::TCK_CodeSize);
514	break;
515	}
516	}
517
518	return Benefit;
519	}
520
521	/// Check the \p OutputMappings structure for value \p Input, if it exists
522	/// it has been used as an output for outlining, and has been renamed, and we
523	/// return the new value, otherwise, we return the same value.
524	///
525	/// \param OutputMappings [in] - The mapping of values to their renamed value
526	/// after being used as an output for an outlined region.
527	/// \param Input [in] - The value to find the remapped value of, if it exists.
528	/// \return The remapped value if it has been renamed, and the same value if has
529	/// not.
530	static Value *findOutputMapping(const DenseMap<Value *, Value *> OutputMappings,
531	Value *Input) {
532	DenseMap<Value *, Value *>::const_iterator OutputMapping =
533	OutputMappings.find(Val: Input);
534	if (OutputMapping != OutputMappings.end())
535	return OutputMapping->second;
536	return Input;
537	}
538
539	/// Find whether \p Region matches the global value numbering to Constant
540	/// mapping found so far.
541	///
542	/// \param Region - The OutlinableRegion we are checking for constants
543	/// \param GVNToConstant - The mapping of global value number to Constants.
544	/// \param NotSame - The set of global value numbers that do not have the same
545	/// constant in each region.
546	/// \returns true if all Constants are the same in every use of a Constant in \p
547	/// Region and false if not
548	static bool
549	collectRegionsConstants(OutlinableRegion &Region,
550	DenseMap<unsigned, Constant *> &GVNToConstant,
551	DenseSet<unsigned> &NotSame) {
552	bool ConstantsTheSame = true;
553
554	IRSimilarityCandidate &C = *Region.Candidate;
555	for (IRInstructionData &ID : C) {
556
557	// Iterate over the operands in an instruction. If the global value number,
558	// assigned by the IRSimilarityCandidate, has been seen before, we check if
559	// the number has been found to be not the same value in each instance.
560	for (Value *V : ID.OperVals) {
561	std::optional<unsigned> GVNOpt = C.getGVN(V);
562	assert(GVNOpt && "Expected a GVN for operand?");
563	unsigned GVN = *GVNOpt;
564
565	// Check if this global value has been found to not be the same already.
566	if (NotSame.contains(V: GVN)) {
567	if (isa<Constant>(Val: V))
568	ConstantsTheSame = false;
569	continue;
570	}
571
572	// If it has been the same so far, we check the value for if the
573	// associated Constant value match the previous instances of the same
574	// global value number. If the global value does not map to a Constant,
575	// it is considered to not be the same value.
576	std::optional<bool> ConstantMatches =
577	constantMatches(V, GVN, GVNToConstant);
578	if (ConstantMatches) {
579	if (*ConstantMatches)
580	continue;
581	else
582	ConstantsTheSame = false;
583	}
584
585	// While this value is a register, it might not have been previously,
586	// make sure we don't already have a constant mapped to this global value
587	// number.
588	if (GVNToConstant.contains(Val: GVN))
589	ConstantsTheSame = false;
590
591	NotSame.insert(V: GVN);
592	}
593	}
594
595	return ConstantsTheSame;
596	}
597
598	void OutlinableGroup::findSameConstants(DenseSet<unsigned> &NotSame) {
599	DenseMap<unsigned, Constant *> GVNToConstant;
600
601	for (OutlinableRegion *Region : Regions)
602	collectRegionsConstants(Region&: *Region, GVNToConstant, NotSame);
603	}
604
605	void OutlinableGroup::collectGVNStoreSets(Module &M) {
606	for (OutlinableRegion *OS : Regions)
607	OutputGVNCombinations.insert(V: OS->GVNStores);
608
609	// We are adding an extracted argument to decide between which output path
610	// to use in the basic block. It is used in a switch statement and only
611	// needs to be an integer.
612	if (OutputGVNCombinations.size() > 1)
613	ArgumentTypes.push_back(x: Type::getInt32Ty(C&: M.getContext()));
614	}
615
616	/// Get the subprogram if it exists for one of the outlined regions.
617	///
618	/// \param [in] Group - The set of regions to find a subprogram for.
619	/// \returns the subprogram if it exists, or nullptr.
620	static DISubprogram *getSubprogramOrNull(OutlinableGroup &Group) {
621	for (OutlinableRegion *OS : Group.Regions)
622	if (Function *F = OS->Call->getFunction())
623	if (DISubprogram *SP = F->getSubprogram())
624	return SP;
625
626	return nullptr;
627	}
628
629	Function *IROutliner::createFunction(Module &M, OutlinableGroup &Group,
630	unsigned FunctionNameSuffix) {
631	assert(!Group.OutlinedFunction && "Function is already defined!");
632
633	Type *RetTy = Type::getVoidTy(C&: M.getContext());
634	// All extracted functions _should_ have the same return type at this point
635	// since the similarity identifier ensures that all branches outside of the
636	// region occur in the same place.
637
638	// NOTE: Should we ever move to the model that uses a switch at every point
639	// needed, meaning that we could branch within the region or out, it is
640	// possible that we will need to switch to using the most general case all of
641	// the time.
642	for (OutlinableRegion *R : Group.Regions) {
643	Type *ExtractedFuncType = R->ExtractedFunction->getReturnType();
644	if ((RetTy->isVoidTy() && !ExtractedFuncType->isVoidTy()) ||
645	(RetTy->isIntegerTy(Bitwidth: 1) && ExtractedFuncType->isIntegerTy(Bitwidth: 16)))
646	RetTy = ExtractedFuncType;
647	}
648
649	Group.OutlinedFunctionType = FunctionType::get(
650	Result: RetTy, Params: Group.ArgumentTypes, isVarArg: false);
651
652	// These functions will only be called from within the same module, so
653	// we can set an internal linkage.
654	Group.OutlinedFunction = Function::Create(
655	Ty: Group.OutlinedFunctionType, Linkage: GlobalValue::InternalLinkage,
656	N: "outlined_ir_func_" + std::to_string(val: FunctionNameSuffix), M);
657
658	// Transfer the swifterr attribute to the correct function parameter.
659	if (Group.SwiftErrorArgument)
660	Group.OutlinedFunction->addParamAttr(*Group.SwiftErrorArgument,
661	Attribute::SwiftError);
662
663	Group.OutlinedFunction->addFnAttr(Attribute::OptimizeForSize);
664	Group.OutlinedFunction->addFnAttr(Attribute::MinSize);
665
666	// If there's a DISubprogram associated with this outlined function, then
667	// emit debug info for the outlined function.
668	if (DISubprogram *SP = getSubprogramOrNull(Group)) {
669	Function *F = Group.OutlinedFunction;
670	// We have a DISubprogram. Get its DICompileUnit.
671	DICompileUnit *CU = SP->getUnit();
672	DIBuilder DB(M, true, CU);
673	DIFile *Unit = SP->getFile();
674	Mangler Mg;
675	// Get the mangled name of the function for the linkage name.
676	std::string Dummy;
677	llvm::raw_string_ostream MangledNameStream(Dummy);
678	Mg.getNameWithPrefix(OS&: MangledNameStream, GV: F, CannotUsePrivateLabel: false);
679
680	DISubprogram *OutlinedSP = DB.createFunction(
681	Scope: Unit /* Context */, Name: F->getName(), LinkageName: MangledNameStream.str(),
682	File: Unit /* File */,
683	LineNo: 0 /* Line 0 is reserved for compiler-generated code. */,
684	Ty: DB.createSubroutineType(
685	ParameterTypes: DB.getOrCreateTypeArray(Elements: std::nullopt)), /* void type */
686	ScopeLine: 0, /* Line 0 is reserved for compiler-generated code. */
687	Flags: DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
688	/* Outlined code is optimized code by definition. */
689	SPFlags: DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
690
691	// Don't add any new variables to the subprogram.
692	DB.finalizeSubprogram(SP: OutlinedSP);
693
694	// Attach subprogram to the function.
695	F->setSubprogram(OutlinedSP);
696	// We're done with the DIBuilder.
697	DB.finalize();
698	}
699
700	return Group.OutlinedFunction;
701	}
702
703	/// Move each BasicBlock in \p Old to \p New.
704	///
705	/// \param [in] Old - The function to move the basic blocks from.
706	/// \param [in] New - The function to move the basic blocks to.
707	/// \param [out] NewEnds - The return blocks of the new overall function.
708	static void moveFunctionData(Function &Old, Function &New,
709	DenseMap<Value *, BasicBlock *> &NewEnds) {
710	for (BasicBlock &CurrBB : llvm::make_early_inc_range(Range&: Old)) {
711	CurrBB.removeFromParent();
712	CurrBB.insertInto(Parent: &New);
713	Instruction *I = CurrBB.getTerminator();
714
715	// For each block we find a return instruction is, it is a potential exit
716	// path for the function. We keep track of each block based on the return
717	// value here.
718	if (ReturnInst *RI = dyn_cast<ReturnInst>(Val: I))
719	NewEnds.insert(KV: std::make_pair(x: RI->getReturnValue(), y: &CurrBB));
720
721	std::vector<Instruction *> DebugInsts;
722
723	for (Instruction &Val : CurrBB) {
724	// Since debug-info originates from many different locations in the
725	// program, it will cause incorrect reporting from a debugger if we keep
726	// the same debug instructions. Drop non-intrinsic DbgVariableRecords
727	// here, collect intrinsics for removal later.
728	Val.dropDbgRecords();
729
730	// We must handle the scoping of called functions differently than
731	// other outlined instructions.
732	if (!isa<CallInst>(Val: &Val)) {
733	// Remove the debug information for outlined functions.
734	Val.setDebugLoc(DebugLoc());
735
736	// Loop info metadata may contain line locations. Update them to have no
737	// value in the new subprogram since the outlined code could be from
738	// several locations.
739	auto updateLoopInfoLoc = [&New](Metadata *MD) -> Metadata * {
740	if (DISubprogram *SP = New.getSubprogram())
741	if (auto *Loc = dyn_cast_or_null<DILocation>(Val: MD))
742	return DILocation::get(Context&: New.getContext(), Line: Loc->getLine(),
743	Column: Loc->getColumn(), Scope: SP, InlinedAt: nullptr);
744	return MD;
745	};
746	updateLoopMetadataDebugLocations(I&: Val, Updater: updateLoopInfoLoc);
747	continue;
748	}
749
750	// From this point we are only handling call instructions.
751	CallInst *CI = cast<CallInst>(Val: &Val);
752
753	// Collect debug intrinsics for later removal.
754	if (isa<DbgInfoIntrinsic>(Val: CI)) {
755	DebugInsts.push_back(x: &Val);
756	continue;
757	}
758
759	// Edit the scope of called functions inside of outlined functions.
760	if (DISubprogram *SP = New.getSubprogram()) {
761	DILocation *DI = DILocation::get(Context&: New.getContext(), Line: 0, Column: 0, Scope: SP);
762	Val.setDebugLoc(DI);
763	}
764	}
765
766	for (Instruction *I : DebugInsts)
767	I->eraseFromParent();
768	}
769	}
770
771	/// Find the constants that will need to be lifted into arguments
772	/// as they are not the same in each instance of the region.
773	///
774	/// \param [in] C - The IRSimilarityCandidate containing the region we are
775	/// analyzing.
776	/// \param [in] NotSame - The set of global value numbers that do not have a
777	/// single Constant across all OutlinableRegions similar to \p C.
778	/// \param [out] Inputs - The list containing the global value numbers of the
779	/// arguments needed for the region of code.
780	static void findConstants(IRSimilarityCandidate &C, DenseSet<unsigned> &NotSame,
781	std::vector<unsigned> &Inputs) {
782	DenseSet<unsigned> Seen;
783	// Iterate over the instructions, and find what constants will need to be
784	// extracted into arguments.
785	for (IRInstructionDataList::iterator IDIt = C.begin(), EndIDIt = C.end();
786	IDIt != EndIDIt; IDIt++) {
787	for (Value *V : (*IDIt).OperVals) {
788	// Since these are stored before any outlining, they will be in the
789	// global value numbering.
790	unsigned GVN = *C.getGVN(V);
791	if (isa<Constant>(Val: V))
792	if (NotSame.contains(V: GVN) && !Seen.contains(V: GVN)) {
793	Inputs.push_back(x: GVN);
794	Seen.insert(V: GVN);
795	}
796	}
797	}
798	}
799
800	/// Find the GVN for the inputs that have been found by the CodeExtractor.
801	///
802	/// \param [in] C - The IRSimilarityCandidate containing the region we are
803	/// analyzing.
804	/// \param [in] CurrentInputs - The set of inputs found by the
805	/// CodeExtractor.
806	/// \param [in] OutputMappings - The mapping of values that have been replaced
807	/// by a new output value.
808	/// \param [out] EndInputNumbers - The global value numbers for the extracted
809	/// arguments.
810	static void mapInputsToGVNs(IRSimilarityCandidate &C,
811	SetVector<Value *> &CurrentInputs,
812	const DenseMap<Value *, Value *> &OutputMappings,
813	std::vector<unsigned> &EndInputNumbers) {
814	// Get the Global Value Number for each input. We check if the Value has been
815	// replaced by a different value at output, and use the original value before
816	// replacement.
817	for (Value *Input : CurrentInputs) {
818	assert(Input && "Have a nullptr as an input");
819	if (OutputMappings.contains(Val: Input))
820	Input = OutputMappings.find(Val: Input)->second;
821	assert(C.getGVN(Input) && "Could not find a numbering for the given input");
822	EndInputNumbers.push_back(x: *C.getGVN(V: Input));
823	}
824	}
825
826	/// Find the original value for the \p ArgInput values if any one of them was
827	/// replaced during a previous extraction.
828	///
829	/// \param [in] ArgInputs - The inputs to be extracted by the code extractor.
830	/// \param [in] OutputMappings - The mapping of values that have been replaced
831	/// by a new output value.
832	/// \param [out] RemappedArgInputs - The remapped values according to
833	/// \p OutputMappings that will be extracted.
834	static void
835	remapExtractedInputs(const ArrayRef<Value *> ArgInputs,
836	const DenseMap<Value *, Value *> &OutputMappings,
837	SetVector<Value *> &RemappedArgInputs) {
838	// Get the global value number for each input that will be extracted as an
839	// argument by the code extractor, remapping if needed for reloaded values.
840	for (Value *Input : ArgInputs) {
841	if (OutputMappings.contains(Val: Input))
842	Input = OutputMappings.find(Val: Input)->second;
843	RemappedArgInputs.insert(X: Input);
844	}
845	}
846
847	/// Find the input GVNs and the output values for a region of Instructions.
848	/// Using the code extractor, we collect the inputs to the extracted function.
849	///
850	/// The \p Region can be identified as needing to be ignored in this function.
851	/// It should be checked whether it should be ignored after a call to this
852	/// function.
853	///
854	/// \param [in,out] Region - The region of code to be analyzed.
855	/// \param [out] InputGVNs - The global value numbers for the extracted
856	/// arguments.
857	/// \param [in] NotSame - The global value numbers in the region that do not
858	/// have the same constant value in the regions structurally similar to
859	/// \p Region.
860	/// \param [in] OutputMappings - The mapping of values that have been replaced
861	/// by a new output value after extraction.
862	/// \param [out] ArgInputs - The values of the inputs to the extracted function.
863	/// \param [out] Outputs - The set of values extracted by the CodeExtractor
864	/// as outputs.
865	static void getCodeExtractorArguments(
866	OutlinableRegion &Region, std::vector<unsigned> &InputGVNs,
867	DenseSet<unsigned> &NotSame, DenseMap<Value *, Value *> &OutputMappings,
868	SetVector<Value *> &ArgInputs, SetVector<Value *> &Outputs) {
869	IRSimilarityCandidate &C = *Region.Candidate;
870
871	// OverallInputs are the inputs to the region found by the CodeExtractor,
872	// SinkCands and HoistCands are used by the CodeExtractor to find sunken
873	// allocas of values whose lifetimes are contained completely within the
874	// outlined region. PremappedInputs are the arguments found by the
875	// CodeExtractor, removing conditions such as sunken allocas, but that
876	// may need to be remapped due to the extracted output values replacing
877	// the original values. We use DummyOutputs for this first run of finding
878	// inputs and outputs since the outputs could change during findAllocas,
879	// the correct set of extracted outputs will be in the final Outputs ValueSet.
880	SetVector<Value *> OverallInputs, PremappedInputs, SinkCands, HoistCands,
881	DummyOutputs;
882
883	// Use the code extractor to get the inputs and outputs, without sunken
884	// allocas or removing llvm.assumes.
885	CodeExtractor *CE = Region.CE;
886	CE->findInputsOutputs(Inputs&: OverallInputs, Outputs&: DummyOutputs, Allocas: SinkCands);
887	assert(Region.StartBB && "Region must have a start BasicBlock!");
888	Function *OrigF = Region.StartBB->getParent();
889	CodeExtractorAnalysisCache CEAC(*OrigF);
890	BasicBlock *Dummy = nullptr;
891
892	// The region may be ineligible due to VarArgs in the parent function. In this
893	// case we ignore the region.
894	if (!CE->isEligible()) {
895	Region.IgnoreRegion = true;
896	return;
897	}
898
899	// Find if any values are going to be sunk into the function when extracted
900	CE->findAllocas(CEAC, SinkCands, HoistCands, ExitBlock&: Dummy);
901	CE->findInputsOutputs(Inputs&: PremappedInputs, Outputs, Allocas: SinkCands);
902
903	// TODO: Support regions with sunken allocas: values whose lifetimes are
904	// contained completely within the outlined region. These are not guaranteed
905	// to be the same in every region, so we must elevate them all to arguments
906	// when they appear. If these values are not equal, it means there is some
907	// Input in OverallInputs that was removed for ArgInputs.
908	if (OverallInputs.size() != PremappedInputs.size()) {
909	Region.IgnoreRegion = true;
910	return;
911	}
912
913	findConstants(C, NotSame, Inputs&: InputGVNs);
914
915	mapInputsToGVNs(C, CurrentInputs&: OverallInputs, OutputMappings, EndInputNumbers&: InputGVNs);
916
917	remapExtractedInputs(ArgInputs: PremappedInputs.getArrayRef(), OutputMappings,
918	RemappedArgInputs&: ArgInputs);
919
920	// Sort the GVNs, since we now have constants included in the \ref InputGVNs
921	// we need to make sure they are in a deterministic order.
922	stable_sort(Range&: InputGVNs);
923	}
924
925	/// Look over the inputs and map each input argument to an argument in the
926	/// overall function for the OutlinableRegions. This creates a way to replace
927	/// the arguments of the extracted function with the arguments of the new
928	/// overall function.
929	///
930	/// \param [in,out] Region - The region of code to be analyzed.
931	/// \param [in] InputGVNs - The global value numbering of the input values
932	/// collected.
933	/// \param [in] ArgInputs - The values of the arguments to the extracted
934	/// function.
935	static void
936	findExtractedInputToOverallInputMapping(OutlinableRegion &Region,
937	std::vector<unsigned> &InputGVNs,
938	SetVector<Value *> &ArgInputs) {
939
940	IRSimilarityCandidate &C = *Region.Candidate;
941	OutlinableGroup &Group = *Region.Parent;
942
943	// This counts the argument number in the overall function.
944	unsigned TypeIndex = 0;
945
946	// This counts the argument number in the extracted function.
947	unsigned OriginalIndex = 0;
948
949	// Find the mapping of the extracted arguments to the arguments for the
950	// overall function. Since there may be extra arguments in the overall
951	// function to account for the extracted constants, we have two different
952	// counters as we find extracted arguments, and as we come across overall
953	// arguments.
954
955	// Additionally, in our first pass, for the first extracted function,
956	// we find argument locations for the canonical value numbering. This
957	// numbering overrides any discovered location for the extracted code.
958	for (unsigned InputVal : InputGVNs) {
959	std::optional<unsigned> CanonicalNumberOpt = C.getCanonicalNum(N: InputVal);
960	assert(CanonicalNumberOpt && "Canonical number not found?");
961	unsigned CanonicalNumber = *CanonicalNumberOpt;
962
963	std::optional<Value *> InputOpt = C.fromGVN(Num: InputVal);
964	assert(InputOpt && "Global value number not found?");
965	Value *Input = *InputOpt;
966
967	DenseMap<unsigned, unsigned>::iterator AggArgIt =
968	Group.CanonicalNumberToAggArg.find(Val: CanonicalNumber);
969
970	if (!Group.InputTypesSet) {
971	Group.ArgumentTypes.push_back(x: Input->getType());
972	// If the input value has a swifterr attribute, make sure to mark the
973	// argument in the overall function.
974	if (Input->isSwiftError()) {
975	assert(
976	!Group.SwiftErrorArgument &&
977	"Argument already marked with swifterr for this OutlinableGroup!");
978	Group.SwiftErrorArgument = TypeIndex;
979	}
980	}
981
982	// Check if we have a constant. If we do add it to the overall argument
983	// number to Constant map for the region, and continue to the next input.
984	if (Constant *CST = dyn_cast<Constant>(Val: Input)) {
985	if (AggArgIt != Group.CanonicalNumberToAggArg.end())
986	Region.AggArgToConstant.insert(KV: std::make_pair(x&: AggArgIt->second, y&: CST));
987	else {
988	Group.CanonicalNumberToAggArg.insert(
989	KV: std::make_pair(x&: CanonicalNumber, y&: TypeIndex));
990	Region.AggArgToConstant.insert(KV: std::make_pair(x&: TypeIndex, y&: CST));
991	}
992	TypeIndex++;
993	continue;
994	}
995
996	// It is not a constant, we create the mapping from extracted argument list
997	// to the overall argument list, using the canonical location, if it exists.
998	assert(ArgInputs.count(Input) && "Input cannot be found!");
999
1000	if (AggArgIt != Group.CanonicalNumberToAggArg.end()) {
1001	if (OriginalIndex != AggArgIt->second)
1002	Region.ChangedArgOrder = true;
1003	Region.ExtractedArgToAgg.insert(
1004	KV: std::make_pair(x&: OriginalIndex, y&: AggArgIt->second));
1005	Region.AggArgToExtracted.insert(
1006	KV: std::make_pair(x&: AggArgIt->second, y&: OriginalIndex));
1007	} else {
1008	Group.CanonicalNumberToAggArg.insert(
1009	KV: std::make_pair(x&: CanonicalNumber, y&: TypeIndex));
1010	Region.ExtractedArgToAgg.insert(KV: std::make_pair(x&: OriginalIndex, y&: TypeIndex));
1011	Region.AggArgToExtracted.insert(KV: std::make_pair(x&: TypeIndex, y&: OriginalIndex));
1012	}
1013	OriginalIndex++;
1014	TypeIndex++;
1015	}
1016
1017	// If the function type definitions for the OutlinableGroup holding the region
1018	// have not been set, set the length of the inputs here. We should have the
1019	// same inputs for all of the different regions contained in the
1020	// OutlinableGroup since they are all structurally similar to one another.
1021	if (!Group.InputTypesSet) {
1022	Group.NumAggregateInputs = TypeIndex;
1023	Group.InputTypesSet = true;
1024	}
1025
1026	Region.NumExtractedInputs = OriginalIndex;
1027	}
1028
1029	/// Check if the \p V has any uses outside of the region other than \p PN.
1030	///
1031	/// \param V [in] - The value to check.
1032	/// \param PHILoc [in] - The location in the PHINode of \p V.
1033	/// \param PN [in] - The PHINode using \p V.
1034	/// \param Exits [in] - The potential blocks we exit to from the outlined
1035	/// region.
1036	/// \param BlocksInRegion [in] - The basic blocks contained in the region.
1037	/// \returns true if \p V has any use soutside its region other than \p PN.
1038	static bool outputHasNonPHI(Value *V, unsigned PHILoc, PHINode &PN,
1039	SmallPtrSet<BasicBlock *, 1> &Exits,
1040	DenseSet<BasicBlock *> &BlocksInRegion) {
1041	// We check to see if the value is used by the PHINode from some other
1042	// predecessor not included in the region. If it is, we make sure
1043	// to keep it as an output.
1044	if (any_of(Range: llvm::seq<unsigned>(Begin: 0, End: PN.getNumIncomingValues()),
1045	P: [PHILoc, &PN, V, &BlocksInRegion](unsigned Idx) {
1046	return (Idx != PHILoc && V == PN.getIncomingValue(i: Idx) &&
1047	!BlocksInRegion.contains(V: PN.getIncomingBlock(i: Idx)));
1048	}))
1049	return true;
1050
1051	// Check if the value is used by any other instructions outside the region.
1052	return any_of(Range: V->users(), P: [&Exits, &BlocksInRegion](User *U) {
1053	Instruction *I = dyn_cast<Instruction>(Val: U);
1054	if (!I)
1055	return false;
1056
1057	// If the use of the item is inside the region, we skip it. Uses
1058	// inside the region give us useful information about how the item could be
1059	// used as an output.
1060	BasicBlock *Parent = I->getParent();
1061	if (BlocksInRegion.contains(V: Parent))
1062	return false;
1063
1064	// If it's not a PHINode then we definitely know the use matters. This
1065	// output value will not completely combined with another item in a PHINode
1066	// as it is directly reference by another non-phi instruction
1067	if (!isa<PHINode>(Val: I))
1068	return true;
1069
1070	// If we have a PHINode outside one of the exit locations, then it
1071	// can be considered an outside use as well. If there is a PHINode
1072	// contained in the Exit where this values use matters, it will be
1073	// caught when we analyze that PHINode.
1074	if (!Exits.contains(Ptr: Parent))
1075	return true;
1076
1077	return false;
1078	});
1079	}
1080
1081	/// Test whether \p CurrentExitFromRegion contains any PhiNodes that should be
1082	/// considered outputs. A PHINodes is an output when more than one incoming
1083	/// value has been marked by the CodeExtractor as an output.
1084	///
1085	/// \param CurrentExitFromRegion [in] - The block to analyze.
1086	/// \param PotentialExitsFromRegion [in] - The potential exit blocks from the
1087	/// region.
1088	/// \param RegionBlocks [in] - The basic blocks in the region.
1089	/// \param Outputs [in, out] - The existing outputs for the region, we may add
1090	/// PHINodes to this as we find that they replace output values.
1091	/// \param OutputsReplacedByPHINode [out] - A set containing outputs that are
1092	/// totally replaced by a PHINode.
1093	/// \param OutputsWithNonPhiUses [out] - A set containing outputs that are used
1094	/// in PHINodes, but have other uses, and should still be considered outputs.
1095	static void analyzeExitPHIsForOutputUses(
1096	BasicBlock *CurrentExitFromRegion,
1097	SmallPtrSet<BasicBlock *, 1> &PotentialExitsFromRegion,
1098	DenseSet<BasicBlock *> &RegionBlocks, SetVector<Value *> &Outputs,
1099	DenseSet<Value *> &OutputsReplacedByPHINode,
1100	DenseSet<Value *> &OutputsWithNonPhiUses) {
1101	for (PHINode &PN : CurrentExitFromRegion->phis()) {
1102	// Find all incoming values from the outlining region.
1103	SmallVector<unsigned, 2> IncomingVals;
1104	for (unsigned I = 0, E = PN.getNumIncomingValues(); I < E; ++I)
1105	if (RegionBlocks.contains(V: PN.getIncomingBlock(i: I)))
1106	IncomingVals.push_back(Elt: I);
1107
1108	// Do not process PHI if there are no predecessors from region.
1109	unsigned NumIncomingVals = IncomingVals.size();
1110	if (NumIncomingVals == 0)
1111	continue;
1112
1113	// If there is one predecessor, we mark it as a value that needs to be kept
1114	// as an output.
1115	if (NumIncomingVals == 1) {
1116	Value *V = PN.getIncomingValue(i: *IncomingVals.begin());
1117	OutputsWithNonPhiUses.insert(V);
1118	OutputsReplacedByPHINode.erase(V);
1119	continue;
1120	}
1121
1122	// This PHINode will be used as an output value, so we add it to our list.
1123	Outputs.insert(X: &PN);
1124
1125	// Not all of the incoming values should be ignored as other inputs and
1126	// outputs may have uses in outlined region. If they have other uses
1127	// outside of the single PHINode we should not skip over it.
1128	for (unsigned Idx : IncomingVals) {
1129	Value *V = PN.getIncomingValue(i: Idx);
1130	if (outputHasNonPHI(V, PHILoc: Idx, PN, Exits&: PotentialExitsFromRegion, BlocksInRegion&: RegionBlocks)) {
1131	OutputsWithNonPhiUses.insert(V);
1132	OutputsReplacedByPHINode.erase(V);
1133	continue;
1134	}
1135	if (!OutputsWithNonPhiUses.contains(V))
1136	OutputsReplacedByPHINode.insert(V);
1137	}
1138	}
1139	}
1140
1141	// Represents the type for the unsigned number denoting the output number for
1142	// phi node, along with the canonical number for the exit block.
1143	using ArgLocWithBBCanon = std::pair<unsigned, unsigned>;
1144	// The list of canonical numbers for the incoming values to a PHINode.
1145	using CanonList = SmallVector<unsigned, 2>;
1146	// The pair type representing the set of canonical values being combined in the
1147	// PHINode, along with the location data for the PHINode.
1148	using PHINodeData = std::pair<ArgLocWithBBCanon, CanonList>;
1149
1150	/// Encode \p PND as an integer for easy lookup based on the argument location,
1151	/// the parent BasicBlock canonical numbering, and the canonical numbering of
1152	/// the values stored in the PHINode.
1153	///
1154	/// \param PND - The data to hash.
1155	/// \returns The hash code of \p PND.
1156	static hash_code encodePHINodeData(PHINodeData &PND) {
1157	return llvm::hash_combine(
1158	args: llvm::hash_value(value: PND.first.first), args: llvm::hash_value(value: PND.first.second),
1159	args: llvm::hash_combine_range(first: PND.second.begin(), last: PND.second.end()));
1160	}
1161
1162	/// Create a special GVN for PHINodes that will be used outside of
1163	/// the region. We create a hash code based on the Canonical number of the
1164	/// parent BasicBlock, the canonical numbering of the values stored in the
1165	/// PHINode and the aggregate argument location. This is used to find whether
1166	/// this PHINode type has been given a canonical numbering already. If not, we
1167	/// assign it a value and store it for later use. The value is returned to
1168	/// identify different output schemes for the set of regions.
1169	///
1170	/// \param Region - The region that \p PN is an output for.
1171	/// \param PN - The PHINode we are analyzing.
1172	/// \param Blocks - The blocks for the region we are analyzing.
1173	/// \param AggArgIdx - The argument \p PN will be stored into.
1174	/// \returns An optional holding the assigned canonical number, or std::nullopt
1175	/// if there is some attribute of the PHINode blocking it from being used.
1176	static std::optional<unsigned> getGVNForPHINode(OutlinableRegion &Region,
1177	PHINode *PN,
1178	DenseSet<BasicBlock *> &Blocks,
1179	unsigned AggArgIdx) {
1180	OutlinableGroup &Group = *Region.Parent;
1181	IRSimilarityCandidate &Cand = *Region.Candidate;
1182	BasicBlock *PHIBB = PN->getParent();
1183	CanonList PHIGVNs;
1184	Value *Incoming;
1185	BasicBlock *IncomingBlock;
1186	for (unsigned Idx = 0, EIdx = PN->getNumIncomingValues(); Idx < EIdx; Idx++) {
1187	Incoming = PN->getIncomingValue(i: Idx);
1188	IncomingBlock = PN->getIncomingBlock(i: Idx);
1189	// If we cannot find a GVN, and the incoming block is included in the region
1190	// this means that the input to the PHINode is not included in the region we
1191	// are trying to analyze, meaning, that if it was outlined, we would be
1192	// adding an extra input. We ignore this case for now, and so ignore the
1193	// region.
1194	std::optional<unsigned> OGVN = Cand.getGVN(V: Incoming);
1195	if (!OGVN && Blocks.contains(V: IncomingBlock)) {
1196	Region.IgnoreRegion = true;
1197	return std::nullopt;
1198	}
1199
1200	// If the incoming block isn't in the region, we don't have to worry about
1201	// this incoming value.
1202	if (!Blocks.contains(V: IncomingBlock))
1203	continue;
1204
1205	// Collect the canonical numbers of the values in the PHINode.
1206	unsigned GVN = *OGVN;
1207	OGVN = Cand.getCanonicalNum(N: GVN);
1208	assert(OGVN && "No GVN found for incoming value?");
1209	PHIGVNs.push_back(Elt: *OGVN);
1210
1211	// Find the incoming block and use the canonical numbering as well to define
1212	// the hash for the PHINode.
1213	OGVN = Cand.getGVN(V: IncomingBlock);
1214
1215	// If there is no number for the incoming block, it is because we have
1216	// split the candidate basic blocks. So we use the previous block that it
1217	// was split from to find the valid global value numbering for the PHINode.
1218	if (!OGVN) {
1219	assert(Cand.getStartBB() == IncomingBlock &&
1220	"Unknown basic block used in exit path PHINode.");
1221
1222	BasicBlock *PrevBlock = nullptr;
1223	// Iterate over the predecessors to the incoming block of the
1224	// PHINode, when we find a block that is not contained in the region
1225	// we know that this is the first block that we split from, and should
1226	// have a valid global value numbering.
1227	for (BasicBlock *Pred : predecessors(BB: IncomingBlock))
1228	if (!Blocks.contains(V: Pred)) {
1229	PrevBlock = Pred;
1230	break;
1231	}
1232	assert(PrevBlock && "Expected a predecessor not in the reigon!");
1233	OGVN = Cand.getGVN(V: PrevBlock);
1234	}
1235	GVN = *OGVN;
1236	OGVN = Cand.getCanonicalNum(N: GVN);
1237	assert(OGVN && "No GVN found for incoming block?");
1238	PHIGVNs.push_back(Elt: *OGVN);
1239	}
1240
1241	// Now that we have the GVNs for the incoming values, we are going to combine
1242	// them with the GVN of the incoming bock, and the output location of the
1243	// PHINode to generate a hash value representing this instance of the PHINode.
1244	DenseMap<hash_code, unsigned>::iterator GVNToPHIIt;
1245	DenseMap<unsigned, PHINodeData>::iterator PHIToGVNIt;
1246	std::optional<unsigned> BBGVN = Cand.getGVN(V: PHIBB);
1247	assert(BBGVN && "Could not find GVN for the incoming block!");
1248
1249	BBGVN = Cand.getCanonicalNum(N: *BBGVN);
1250	assert(BBGVN && "Could not find canonical number for the incoming block!");
1251	// Create a pair of the exit block canonical value, and the aggregate
1252	// argument location, connected to the canonical numbers stored in the
1253	// PHINode.
1254	PHINodeData TemporaryPair =
1255	std::make_pair(x: std::make_pair(x&: *BBGVN, y&: AggArgIdx), y&: PHIGVNs);
1256	hash_code PHINodeDataHash = encodePHINodeData(PND&: TemporaryPair);
1257
1258	// Look for and create a new entry in our connection between canonical
1259	// numbers for PHINodes, and the set of objects we just created.
1260	GVNToPHIIt = Group.GVNsToPHINodeGVN.find(Val: PHINodeDataHash);
1261	if (GVNToPHIIt == Group.GVNsToPHINodeGVN.end()) {
1262	bool Inserted = false;
1263	std::tie(args&: PHIToGVNIt, args&: Inserted) = Group.PHINodeGVNToGVNs.insert(
1264	KV: std::make_pair(x&: Group.PHINodeGVNTracker, y&: TemporaryPair));
1265	std::tie(args&: GVNToPHIIt, args&: Inserted) = Group.GVNsToPHINodeGVN.insert(
1266	KV: std::make_pair(x&: PHINodeDataHash, y: Group.PHINodeGVNTracker--));
1267	}
1268
1269	return GVNToPHIIt->second;
1270	}
1271
1272	/// Create a mapping of the output arguments for the \p Region to the output
1273	/// arguments of the overall outlined function.
1274	///
1275	/// \param [in,out] Region - The region of code to be analyzed.
1276	/// \param [in] Outputs - The values found by the code extractor.
1277	static void
1278	findExtractedOutputToOverallOutputMapping(Module &M, OutlinableRegion &Region,
1279	SetVector<Value *> &Outputs) {
1280	OutlinableGroup &Group = *Region.Parent;
1281	IRSimilarityCandidate &C = *Region.Candidate;
1282
1283	SmallVector<BasicBlock *> BE;
1284	DenseSet<BasicBlock *> BlocksInRegion;
1285	C.getBasicBlocks(BBSet&: BlocksInRegion, BBList&: BE);
1286
1287	// Find the exits to the region.
1288	SmallPtrSet<BasicBlock *, 1> Exits;
1289	for (BasicBlock *Block : BE)
1290	for (BasicBlock *Succ : successors(BB: Block))
1291	if (!BlocksInRegion.contains(V: Succ))
1292	Exits.insert(Ptr: Succ);
1293
1294	// After determining which blocks exit to PHINodes, we add these PHINodes to
1295	// the set of outputs to be processed. We also check the incoming values of
1296	// the PHINodes for whether they should no longer be considered outputs.
1297	DenseSet<Value *> OutputsReplacedByPHINode;
1298	DenseSet<Value *> OutputsWithNonPhiUses;
1299	for (BasicBlock *ExitBB : Exits)
1300	analyzeExitPHIsForOutputUses(CurrentExitFromRegion: ExitBB, PotentialExitsFromRegion&: Exits, RegionBlocks&: BlocksInRegion, Outputs,
1301	OutputsReplacedByPHINode,
1302	OutputsWithNonPhiUses);
1303
1304	// This counts the argument number in the extracted function.
1305	unsigned OriginalIndex = Region.NumExtractedInputs;
1306
1307	// This counts the argument number in the overall function.
1308	unsigned TypeIndex = Group.NumAggregateInputs;
1309	bool TypeFound;
1310	DenseSet<unsigned> AggArgsUsed;
1311
1312	// Iterate over the output types and identify if there is an aggregate pointer
1313	// type whose base type matches the current output type. If there is, we mark
1314	// that we will use this output register for this value. If not we add another
1315	// type to the overall argument type list. We also store the GVNs used for
1316	// stores to identify which values will need to be moved into an special
1317	// block that holds the stores to the output registers.
1318	for (Value *Output : Outputs) {
1319	TypeFound = false;
1320	// We can do this since it is a result value, and will have a number
1321	// that is necessarily the same. BUT if in the future, the instructions
1322	// do not have to be in same order, but are functionally the same, we will
1323	// have to use a different scheme, as one-to-one correspondence is not
1324	// guaranteed.
1325	unsigned ArgumentSize = Group.ArgumentTypes.size();
1326
1327	// If the output is combined in a PHINode, we make sure to skip over it.
1328	if (OutputsReplacedByPHINode.contains(V: Output))
1329	continue;
1330
1331	unsigned AggArgIdx = 0;
1332	for (unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {
1333	if (!isa<PointerType>(Val: Group.ArgumentTypes[Jdx]))
1334	continue;
1335
1336	if (AggArgsUsed.contains(V: Jdx))
1337	continue;
1338
1339	TypeFound = true;
1340	AggArgsUsed.insert(V: Jdx);
1341	Region.ExtractedArgToAgg.insert(KV: std::make_pair(x&: OriginalIndex, y&: Jdx));
1342	Region.AggArgToExtracted.insert(KV: std::make_pair(x&: Jdx, y&: OriginalIndex));
1343	AggArgIdx = Jdx;
1344	break;
1345	}
1346
1347	// We were unable to find an unused type in the output type set that matches
1348	// the output, so we add a pointer type to the argument types of the overall
1349	// function to handle this output and create a mapping to it.
1350	if (!TypeFound) {
1351	Group.ArgumentTypes.push_back(x: PointerType::get(C&: Output->getContext(),
1352	AddressSpace: M.getDataLayout().getAllocaAddrSpace()));
1353	// Mark the new pointer type as the last value in the aggregate argument
1354	// list.
1355	unsigned ArgTypeIdx = Group.ArgumentTypes.size() - 1;
1356	AggArgsUsed.insert(V: ArgTypeIdx);
1357	Region.ExtractedArgToAgg.insert(
1358	KV: std::make_pair(x&: OriginalIndex, y&: ArgTypeIdx));
1359	Region.AggArgToExtracted.insert(
1360	KV: std::make_pair(x&: ArgTypeIdx, y&: OriginalIndex));
1361	AggArgIdx = ArgTypeIdx;
1362	}
1363
1364	// TODO: Adapt to the extra input from the PHINode.
1365	PHINode *PN = dyn_cast<PHINode>(Val: Output);
1366
1367	std::optional<unsigned> GVN;
1368	if (PN && !BlocksInRegion.contains(V: PN->getParent())) {
1369	// Values outside the region can be combined into PHINode when we
1370	// have multiple exits. We collect both of these into a list to identify
1371	// which values are being used in the PHINode. Each list identifies a
1372	// different PHINode, and a different output. We store the PHINode as it's
1373	// own canonical value. These canonical values are also dependent on the
1374	// output argument it is saved to.
1375
1376	// If two PHINodes have the same canonical values, but different aggregate
1377	// argument locations, then they will have distinct Canonical Values.
1378	GVN = getGVNForPHINode(Region, PN, Blocks&: BlocksInRegion, AggArgIdx);
1379	if (!GVN)
1380	return;
1381	} else {
1382	// If we do not have a PHINode we use the global value numbering for the
1383	// output value, to find the canonical number to add to the set of stored
1384	// values.
1385	GVN = C.getGVN(V: Output);
1386	GVN = C.getCanonicalNum(N: *GVN);
1387	}
1388
1389	// Each region has a potentially unique set of outputs. We save which
1390	// values are output in a list of canonical values so we can differentiate
1391	// among the different store schemes.
1392	Region.GVNStores.push_back(Elt: *GVN);
1393
1394	OriginalIndex++;
1395	TypeIndex++;
1396	}
1397
1398	// We sort the stored values to make sure that we are not affected by analysis
1399	// order when determining what combination of items were stored.
1400	stable_sort(Range&: Region.GVNStores);
1401	}
1402
1403	void IROutliner::findAddInputsOutputs(Module &M, OutlinableRegion &Region,
1404	DenseSet<unsigned> &NotSame) {
1405	std::vector<unsigned> Inputs;
1406	SetVector<Value *> ArgInputs, Outputs;
1407
1408	getCodeExtractorArguments(Region, InputGVNs&: Inputs, NotSame, OutputMappings, ArgInputs,
1409	Outputs);
1410
1411	if (Region.IgnoreRegion)
1412	return;
1413
1414	// Map the inputs found by the CodeExtractor to the arguments found for
1415	// the overall function.
1416	findExtractedInputToOverallInputMapping(Region, InputGVNs&: Inputs, ArgInputs);
1417
1418	// Map the outputs found by the CodeExtractor to the arguments found for
1419	// the overall function.
1420	findExtractedOutputToOverallOutputMapping(M, Region, Outputs);
1421	}
1422
1423	/// Replace the extracted function in the Region with a call to the overall
1424	/// function constructed from the deduplicated similar regions, replacing and
1425	/// remapping the values passed to the extracted function as arguments to the
1426	/// new arguments of the overall function.
1427	///
1428	/// \param [in] M - The module to outline from.
1429	/// \param [in] Region - The regions of extracted code to be replaced with a new
1430	/// function.
1431	/// \returns a call instruction with the replaced function.
1432	CallInst *replaceCalledFunction(Module &M, OutlinableRegion &Region) {
1433	std::vector<Value *> NewCallArgs;
1434	DenseMap<unsigned, unsigned>::iterator ArgPair;
1435
1436	OutlinableGroup &Group = *Region.Parent;
1437	CallInst *Call = Region.Call;
1438	assert(Call && "Call to replace is nullptr?");
1439	Function *AggFunc = Group.OutlinedFunction;
1440	assert(AggFunc && "Function to replace with is nullptr?");
1441
1442	// If the arguments are the same size, there are not values that need to be
1443	// made into an argument, the argument ordering has not been change, or
1444	// different output registers to handle. We can simply replace the called
1445	// function in this case.
1446	if (!Region.ChangedArgOrder && AggFunc->arg_size() == Call->arg_size()) {
1447	LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "
1448	<< *AggFunc << " with same number of arguments\n");
1449	Call->setCalledFunction(AggFunc);
1450	return Call;
1451	}
1452
1453	// We have a different number of arguments than the new function, so
1454	// we need to use our previously mappings off extracted argument to overall
1455	// function argument, and constants to overall function argument to create the
1456	// new argument list.
1457	for (unsigned AggArgIdx = 0; AggArgIdx < AggFunc->arg_size(); AggArgIdx++) {
1458
1459	if (AggArgIdx == AggFunc->arg_size() - 1 &&
1460	Group.OutputGVNCombinations.size() > 1) {
1461	// If we are on the last argument, and we need to differentiate between
1462	// output blocks, add an integer to the argument list to determine
1463	// what block to take
1464	LLVM_DEBUG(dbgs() << "Set switch block argument to "
1465	<< Region.OutputBlockNum << "\n");
1466	NewCallArgs.push_back(x: ConstantInt::get(Ty: Type::getInt32Ty(C&: M.getContext()),
1467	V: Region.OutputBlockNum));
1468	continue;
1469	}
1470
1471	ArgPair = Region.AggArgToExtracted.find(Val: AggArgIdx);
1472	if (ArgPair != Region.AggArgToExtracted.end()) {
1473	Value *ArgumentValue = Call->getArgOperand(i: ArgPair->second);
1474	// If we found the mapping from the extracted function to the overall
1475	// function, we simply add it to the argument list. We use the same
1476	// value, it just needs to honor the new order of arguments.
1477	LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "
1478	<< *ArgumentValue << "\n");
1479	NewCallArgs.push_back(x: ArgumentValue);
1480	continue;
1481	}
1482
1483	// If it is a constant, we simply add it to the argument list as a value.
1484	if (Region.AggArgToConstant.contains(Val: AggArgIdx)) {
1485	Constant *CST = Region.AggArgToConstant.find(Val: AggArgIdx)->second;
1486	LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "
1487	<< *CST << "\n");
1488	NewCallArgs.push_back(x: CST);
1489	continue;
1490	}
1491
1492	// Add a nullptr value if the argument is not found in the extracted
1493	// function. If we cannot find a value, it means it is not in use
1494	// for the region, so we should not pass anything to it.
1495	LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to nullptr\n");
1496	NewCallArgs.push_back(x: ConstantPointerNull::get(
1497	T: static_cast<PointerType *>(AggFunc->getArg(i: AggArgIdx)->getType())));
1498	}
1499
1500	LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "
1501	<< *AggFunc << " with new set of arguments\n");
1502	// Create the new call instruction and erase the old one.
1503	Call = CallInst::Create(Ty: AggFunc->getFunctionType(), Func: AggFunc, Args: NewCallArgs, NameStr: "",
1504	InsertBefore: Call->getIterator());
1505
1506	// It is possible that the call to the outlined function is either the first
1507	// instruction is in the new block, the last instruction, or both. If either
1508	// of these is the case, we need to make sure that we replace the instruction
1509	// in the IRInstructionData struct with the new call.
1510	CallInst *OldCall = Region.Call;
1511	if (Region.NewFront->Inst == OldCall)
1512	Region.NewFront->Inst = Call;
1513	if (Region.NewBack->Inst == OldCall)
1514	Region.NewBack->Inst = Call;
1515
1516	// Transfer any debug information.
1517	Call->setDebugLoc(Region.Call->getDebugLoc());
1518	// Since our output may determine which branch we go to, we make sure to
1519	// propogate this new call value through the module.
1520	OldCall->replaceAllUsesWith(V: Call);
1521
1522	// Remove the old instruction.
1523	OldCall->eraseFromParent();
1524	Region.Call = Call;
1525
1526	// Make sure that the argument in the new function has the SwiftError
1527	// argument.
1528	if (Group.SwiftErrorArgument)
1529	Call->addParamAttr(*Group.SwiftErrorArgument, Attribute::SwiftError);
1530
1531	return Call;
1532	}
1533
1534	/// Find or create a BasicBlock in the outlined function containing PhiBlocks
1535	/// for \p RetVal.
1536	///
1537	/// \param Group - The OutlinableGroup containing the information about the
1538	/// overall outlined function.
1539	/// \param RetVal - The return value or exit option that we are currently
1540	/// evaluating.
1541	/// \returns The found or newly created BasicBlock to contain the needed
1542	/// PHINodes to be used as outputs.
1543	static BasicBlock *findOrCreatePHIBlock(OutlinableGroup &Group, Value *RetVal) {
1544	DenseMap<Value *, BasicBlock *>::iterator PhiBlockForRetVal,
1545	ReturnBlockForRetVal;
1546	PhiBlockForRetVal = Group.PHIBlocks.find(Val: RetVal);
1547	ReturnBlockForRetVal = Group.EndBBs.find(Val: RetVal);
1548	assert(ReturnBlockForRetVal != Group.EndBBs.end() &&
1549	"Could not find output value!");
1550	BasicBlock *ReturnBB = ReturnBlockForRetVal->second;
1551
1552	// Find if a PHIBlock exists for this return value already. If it is
1553	// the first time we are analyzing this, we will not, so we record it.
1554	PhiBlockForRetVal = Group.PHIBlocks.find(Val: RetVal);
1555	if (PhiBlockForRetVal != Group.PHIBlocks.end())
1556	return PhiBlockForRetVal->second;
1557
1558	// If we did not find a block, we create one, and insert it into the
1559	// overall function and record it.
1560	bool Inserted = false;
1561	BasicBlock *PHIBlock = BasicBlock::Create(Context&: ReturnBB->getContext(), Name: "phi_block",
1562	Parent: ReturnBB->getParent());
1563	std::tie(args&: PhiBlockForRetVal, args&: Inserted) =
1564	Group.PHIBlocks.insert(KV: std::make_pair(x&: RetVal, y&: PHIBlock));
1565
1566	// We find the predecessors of the return block in the newly created outlined
1567	// function in order to point them to the new PHIBlock rather than the already
1568	// existing return block.
1569	SmallVector<BranchInst *, 2> BranchesToChange;
1570	for (BasicBlock *Pred : predecessors(BB: ReturnBB))
1571	BranchesToChange.push_back(Elt: cast<BranchInst>(Val: Pred->getTerminator()));
1572
1573	// Now we mark the branch instructions found, and change the references of the
1574	// return block to the newly created PHIBlock.
1575	for (BranchInst *BI : BranchesToChange)
1576	for (unsigned Succ = 0, End = BI->getNumSuccessors(); Succ < End; Succ++) {
1577	if (BI->getSuccessor(i: Succ) != ReturnBB)
1578	continue;
1579	BI->setSuccessor(idx: Succ, NewSucc: PHIBlock);
1580	}
1581
1582	BranchInst::Create(IfTrue: ReturnBB, InsertAtEnd: PHIBlock);
1583
1584	return PhiBlockForRetVal->second;
1585	}
1586
1587	/// For the function call now representing the \p Region, find the passed value
1588	/// to that call that represents Argument \p A at the call location if the
1589	/// call has already been replaced with a call to the overall, aggregate
1590	/// function.
1591	///
1592	/// \param A - The Argument to get the passed value for.
1593	/// \param Region - The extracted Region corresponding to the outlined function.
1594	/// \returns The Value representing \p A at the call site.
1595	static Value *
1596	getPassedArgumentInAlreadyOutlinedFunction(const Argument *A,
1597	const OutlinableRegion &Region) {
1598	// If we don't need to adjust the argument number at all (since the call
1599	// has already been replaced by a call to the overall outlined function)
1600	// we can just get the specified argument.
1601	return Region.Call->getArgOperand(i: A->getArgNo());
1602	}
1603
1604	/// For the function call now representing the \p Region, find the passed value
1605	/// to that call that represents Argument \p A at the call location if the
1606	/// call has only been replaced by the call to the aggregate function.
1607	///
1608	/// \param A - The Argument to get the passed value for.
1609	/// \param Region - The extracted Region corresponding to the outlined function.
1610	/// \returns The Value representing \p A at the call site.
1611	static Value *
1612	getPassedArgumentAndAdjustArgumentLocation(const Argument *A,
1613	const OutlinableRegion &Region) {
1614	unsigned ArgNum = A->getArgNo();
1615
1616	// If it is a constant, we can look at our mapping from when we created
1617	// the outputs to figure out what the constant value is.
1618	if (Region.AggArgToConstant.count(Val: ArgNum))
1619	return Region.AggArgToConstant.find(Val: ArgNum)->second;
1620
1621	// If it is not a constant, and we are not looking at the overall function, we
1622	// need to adjust which argument we are looking at.
1623	ArgNum = Region.AggArgToExtracted.find(Val: ArgNum)->second;
1624	return Region.Call->getArgOperand(i: ArgNum);
1625	}
1626
1627	/// Find the canonical numbering for the incoming Values into the PHINode \p PN.
1628	///
1629	/// \param PN [in] - The PHINode that we are finding the canonical numbers for.
1630	/// \param Region [in] - The OutlinableRegion containing \p PN.
1631	/// \param OutputMappings [in] - The mapping of output values from outlined
1632	/// region to their original values.
1633	/// \param CanonNums [out] - The canonical numbering for the incoming values to
1634	/// \p PN paired with their incoming block.
1635	/// \param ReplacedWithOutlinedCall - A flag to use the extracted function call
1636	/// of \p Region rather than the overall function's call.
1637	static void findCanonNumsForPHI(
1638	PHINode *PN, OutlinableRegion &Region,
1639	const DenseMap<Value *, Value *> &OutputMappings,
1640	SmallVector<std::pair<unsigned, BasicBlock *>> &CanonNums,
1641	bool ReplacedWithOutlinedCall = true) {
1642	// Iterate over the incoming values.
1643	for (unsigned Idx = 0, EIdx = PN->getNumIncomingValues(); Idx < EIdx; Idx++) {
1644	Value *IVal = PN->getIncomingValue(i: Idx);
1645	BasicBlock *IBlock = PN->getIncomingBlock(i: Idx);
1646	// If we have an argument as incoming value, we need to grab the passed
1647	// value from the call itself.
1648	if (Argument *A = dyn_cast<Argument>(Val: IVal)) {
1649	if (ReplacedWithOutlinedCall)
1650	IVal = getPassedArgumentInAlreadyOutlinedFunction(A, Region);
1651	else
1652	IVal = getPassedArgumentAndAdjustArgumentLocation(A, Region);
1653	}
1654
1655	// Get the original value if it has been replaced by an output value.
1656	IVal = findOutputMapping(OutputMappings, Input: IVal);
1657
1658	// Find and add the canonical number for the incoming value.
1659	std::optional<unsigned> GVN = Region.Candidate->getGVN(V: IVal);
1660	assert(GVN && "No GVN for incoming value");
1661	std::optional<unsigned> CanonNum = Region.Candidate->getCanonicalNum(N: *GVN);
1662	assert(CanonNum && "No Canonical Number for GVN");
1663	CanonNums.push_back(Elt: std::make_pair(x&: *CanonNum, y&: IBlock));
1664	}
1665	}
1666
1667	/// Find, or add PHINode \p PN to the combined PHINode Block \p OverallPHIBlock
1668	/// in order to condense the number of instructions added to the outlined
1669	/// function.
1670	///
1671	/// \param PN [in] - The PHINode that we are finding the canonical numbers for.
1672	/// \param Region [in] - The OutlinableRegion containing \p PN.
1673	/// \param OverallPhiBlock [in] - The overall PHIBlock we are trying to find
1674	/// \p PN in.
1675	/// \param OutputMappings [in] - The mapping of output values from outlined
1676	/// region to their original values.
1677	/// \param UsedPHIs [in, out] - The PHINodes in the block that have already been
1678	/// matched.
1679	/// \return the newly found or created PHINode in \p OverallPhiBlock.
1680	static PHINode*
1681	findOrCreatePHIInBlock(PHINode &PN, OutlinableRegion &Region,
1682	BasicBlock *OverallPhiBlock,
1683	const DenseMap<Value *, Value *> &OutputMappings,
1684	DenseSet<PHINode *> &UsedPHIs) {
1685	OutlinableGroup &Group = *Region.Parent;
1686
1687
1688	// A list of the canonical numbering assigned to each incoming value, paired
1689	// with the incoming block for the PHINode passed into this function.
1690	SmallVector<std::pair<unsigned, BasicBlock *>> PNCanonNums;
1691
1692	// We have to use the extracted function since we have merged this region into
1693	// the overall function yet. We make sure to reassign the argument numbering
1694	// since it is possible that the argument ordering is different between the
1695	// functions.
1696	findCanonNumsForPHI(PN: &PN, Region, OutputMappings, CanonNums&: PNCanonNums,
1697	/* ReplacedWithOutlinedCall = */ false);
1698
1699	OutlinableRegion *FirstRegion = Group.Regions[0];
1700
1701	// A list of the canonical numbering assigned to each incoming value, paired
1702	// with the incoming block for the PHINode that we are currently comparing
1703	// the passed PHINode to.
1704	SmallVector<std::pair<unsigned, BasicBlock *>> CurrentCanonNums;
1705
1706	// Find the Canonical Numbering for each PHINode, if it matches, we replace
1707	// the uses of the PHINode we are searching for, with the found PHINode.
1708	for (PHINode &CurrPN : OverallPhiBlock->phis()) {
1709	// If this PHINode has already been matched to another PHINode to be merged,
1710	// we skip it.
1711	if (UsedPHIs.contains(V: &CurrPN))
1712	continue;
1713
1714	CurrentCanonNums.clear();
1715	findCanonNumsForPHI(PN: &CurrPN, Region&: *FirstRegion, OutputMappings, CanonNums&: CurrentCanonNums,
1716	/* ReplacedWithOutlinedCall = */ true);
1717
1718	// If the list of incoming values is not the same length, then they cannot
1719	// match since there is not an analogue for each incoming value.
1720	if (PNCanonNums.size() != CurrentCanonNums.size())
1721	continue;
1722
1723	bool FoundMatch = true;
1724
1725	// We compare the canonical value for each incoming value in the passed
1726	// in PHINode to one already present in the outlined region. If the
1727	// incoming values do not match, then the PHINodes do not match.
1728
1729	// We also check to make sure that the incoming block matches as well by
1730	// finding the corresponding incoming block in the combined outlined region
1731	// for the current outlined region.
1732	for (unsigned Idx = 0, Edx = PNCanonNums.size(); Idx < Edx; ++Idx) {
1733	std::pair<unsigned, BasicBlock *> ToCompareTo = CurrentCanonNums[Idx];
1734	std::pair<unsigned, BasicBlock *> ToAdd = PNCanonNums[Idx];
1735	if (ToCompareTo.first != ToAdd.first) {
1736	FoundMatch = false;
1737	break;
1738	}
1739
1740	BasicBlock *CorrespondingBlock =
1741	Region.findCorrespondingBlockIn(Other: *FirstRegion, BB: ToAdd.second);
1742	assert(CorrespondingBlock && "Found block is nullptr");
1743	if (CorrespondingBlock != ToCompareTo.second) {
1744	FoundMatch = false;
1745	break;
1746	}
1747	}
1748
1749	// If all incoming values and branches matched, then we can merge
1750	// into the found PHINode.
1751	if (FoundMatch) {
1752	UsedPHIs.insert(V: &CurrPN);
1753	return &CurrPN;
1754	}
1755	}
1756
1757	// If we've made it here, it means we weren't able to replace the PHINode, so
1758	// we must insert it ourselves.
1759	PHINode *NewPN = cast<PHINode>(Val: PN.clone());
1760	NewPN->insertBefore(InsertPos: &*OverallPhiBlock->begin());
1761	for (unsigned Idx = 0, Edx = NewPN->getNumIncomingValues(); Idx < Edx;
1762	Idx++) {
1763	Value *IncomingVal = NewPN->getIncomingValue(i: Idx);
1764	BasicBlock *IncomingBlock = NewPN->getIncomingBlock(i: Idx);
1765
1766	// Find corresponding basic block in the overall function for the incoming
1767	// block.
1768	BasicBlock *BlockToUse =
1769	Region.findCorrespondingBlockIn(Other: *FirstRegion, BB: IncomingBlock);
1770	NewPN->setIncomingBlock(i: Idx, BB: BlockToUse);
1771
1772	// If we have an argument we make sure we replace using the argument from
1773	// the correct function.
1774	if (Argument *A = dyn_cast<Argument>(Val: IncomingVal)) {
1775	Value *Val = Group.OutlinedFunction->getArg(i: A->getArgNo());
1776	NewPN->setIncomingValue(i: Idx, V: Val);
1777	continue;
1778	}
1779
1780	// Find the corresponding value in the overall function.
1781	IncomingVal = findOutputMapping(OutputMappings, Input: IncomingVal);
1782	Value *Val = Region.findCorrespondingValueIn(Other: *FirstRegion, V: IncomingVal);
1783	assert(Val && "Value is nullptr?");
1784	DenseMap<Value *, Value *>::iterator RemappedIt =
1785	FirstRegion->RemappedArguments.find(Val);
1786	if (RemappedIt != FirstRegion->RemappedArguments.end())
1787	Val = RemappedIt->second;
1788	NewPN->setIncomingValue(i: Idx, V: Val);
1789	}
1790	return NewPN;
1791	}
1792
1793	// Within an extracted function, replace the argument uses of the extracted
1794	// region with the arguments of the function for an OutlinableGroup.
1795	//
1796	/// \param [in] Region - The region of extracted code to be changed.
1797	/// \param [in,out] OutputBBs - The BasicBlock for the output stores for this
1798	/// region.
1799	/// \param [in] FirstFunction - A flag to indicate whether we are using this
1800	/// function to define the overall outlined function for all the regions, or
1801	/// if we are operating on one of the following regions.
1802	static void
1803	replaceArgumentUses(OutlinableRegion &Region,
1804	DenseMap<Value *, BasicBlock *> &OutputBBs,
1805	const DenseMap<Value *, Value *> &OutputMappings,
1806	bool FirstFunction = false) {
1807	OutlinableGroup &Group = *Region.Parent;
1808	assert(Region.ExtractedFunction && "Region has no extracted function?");
1809
1810	Function *DominatingFunction = Region.ExtractedFunction;
1811	if (FirstFunction)
1812	DominatingFunction = Group.OutlinedFunction;
1813	DominatorTree DT(*DominatingFunction);
1814	DenseSet<PHINode *> UsedPHIs;
1815
1816	for (unsigned ArgIdx = 0; ArgIdx < Region.ExtractedFunction->arg_size();
1817	ArgIdx++) {
1818	assert(Region.ExtractedArgToAgg.contains(ArgIdx) &&
1819	"No mapping from extracted to outlined?");
1820	unsigned AggArgIdx = Region.ExtractedArgToAgg.find(Val: ArgIdx)->second;
1821	Argument *AggArg = Group.OutlinedFunction->getArg(i: AggArgIdx);
1822	Argument *Arg = Region.ExtractedFunction->getArg(i: ArgIdx);
1823	// The argument is an input, so we can simply replace it with the overall
1824	// argument value
1825	if (ArgIdx < Region.NumExtractedInputs) {
1826	LLVM_DEBUG(dbgs() << "Replacing uses of input " << *Arg << " in function "
1827	<< *Region.ExtractedFunction << " with " << *AggArg
1828	<< " in function " << *Group.OutlinedFunction << "\n");
1829	Arg->replaceAllUsesWith(V: AggArg);
1830	Value *V = Region.Call->getArgOperand(i: ArgIdx);
1831	Region.RemappedArguments.insert(KV: std::make_pair(x&: V, y&: AggArg));
1832	continue;
1833	}
1834
1835	// If we are replacing an output, we place the store value in its own
1836	// block inside the overall function before replacing the use of the output
1837	// in the function.
1838	assert(Arg->hasOneUse() && "Output argument can only have one use");
1839	User *InstAsUser = Arg->user_back();
1840	assert(InstAsUser && "User is nullptr!");
1841
1842	Instruction *I = cast<Instruction>(Val: InstAsUser);
1843	BasicBlock *BB = I->getParent();
1844	SmallVector<BasicBlock *, 4> Descendants;
1845	DT.getDescendants(R: BB, Result&: Descendants);
1846	bool EdgeAdded = false;
1847	if (Descendants.size() == 0) {
1848	EdgeAdded = true;
1849	DT.insertEdge(From: &DominatingFunction->getEntryBlock(), To: BB);
1850	DT.getDescendants(R: BB, Result&: Descendants);
1851	}
1852
1853	// Iterate over the following blocks, looking for return instructions,
1854	// if we find one, find the corresponding output block for the return value
1855	// and move our store instruction there.
1856	for (BasicBlock *DescendBB : Descendants) {
1857	ReturnInst *RI = dyn_cast<ReturnInst>(Val: DescendBB->getTerminator());
1858	if (!RI)
1859	continue;
1860	Value *RetVal = RI->getReturnValue();
1861	auto VBBIt = OutputBBs.find(Val: RetVal);
1862	assert(VBBIt != OutputBBs.end() && "Could not find output value!");
1863
1864	// If this is storing a PHINode, we must make sure it is included in the
1865	// overall function.
1866	StoreInst *SI = cast<StoreInst>(Val: I);
1867
1868	Value *ValueOperand = SI->getValueOperand();
1869
1870	StoreInst *NewI = cast<StoreInst>(Val: I->clone());
1871	NewI->setDebugLoc(DebugLoc());
1872	BasicBlock *OutputBB = VBBIt->second;
1873	NewI->insertInto(ParentBB: OutputBB, It: OutputBB->end());
1874	LLVM_DEBUG(dbgs() << "Move store for instruction " << *I << " to "
1875	<< *OutputBB << "\n");
1876
1877	// If this is storing a PHINode, we must make sure it is included in the
1878	// overall function.
1879	if (!isa<PHINode>(Val: ValueOperand) ||
1880	Region.Candidate->getGVN(V: ValueOperand).has_value()) {
1881	if (FirstFunction)
1882	continue;
1883	Value *CorrVal =
1884	Region.findCorrespondingValueIn(Other: *Group.Regions[0], V: ValueOperand);
1885	assert(CorrVal && "Value is nullptr?");
1886	NewI->setOperand(i_nocapture: 0, Val_nocapture: CorrVal);
1887	continue;
1888	}
1889	PHINode *PN = cast<PHINode>(Val: SI->getValueOperand());
1890	// If it has a value, it was not split by the code extractor, which
1891	// is what we are looking for.
1892	if (Region.Candidate->getGVN(V: PN))
1893	continue;
1894
1895	// We record the parent block for the PHINode in the Region so that
1896	// we can exclude it from checks later on.
1897	Region.PHIBlocks.insert(KV: std::make_pair(x&: RetVal, y: PN->getParent()));
1898
1899	// If this is the first function, we do not need to worry about mergiing
1900	// this with any other block in the overall outlined function, so we can
1901	// just continue.
1902	if (FirstFunction) {
1903	BasicBlock *PHIBlock = PN->getParent();
1904	Group.PHIBlocks.insert(KV: std::make_pair(x&: RetVal, y&: PHIBlock));
1905	continue;
1906	}
1907
1908	// We look for the aggregate block that contains the PHINodes leading into
1909	// this exit path. If we can't find one, we create one.
1910	BasicBlock *OverallPhiBlock = findOrCreatePHIBlock(Group, RetVal);
1911
1912	// For our PHINode, we find the combined canonical numbering, and
1913	// attempt to find a matching PHINode in the overall PHIBlock. If we
1914	// cannot, we copy the PHINode and move it into this new block.
1915	PHINode *NewPN = findOrCreatePHIInBlock(PN&: *PN, Region, OverallPhiBlock,
1916	OutputMappings, UsedPHIs);
1917	NewI->setOperand(i_nocapture: 0, Val_nocapture: NewPN);
1918	}
1919
1920	// If we added an edge for basic blocks without a predecessor, we remove it
1921	// here.
1922	if (EdgeAdded)
1923	DT.deleteEdge(From: &DominatingFunction->getEntryBlock(), To: BB);
1924	I->eraseFromParent();
1925
1926	LLVM_DEBUG(dbgs() << "Replacing uses of output " << *Arg << " in function "
1927	<< *Region.ExtractedFunction << " with " << *AggArg
1928	<< " in function " << *Group.OutlinedFunction << "\n");
1929	Arg->replaceAllUsesWith(V: AggArg);
1930	}
1931	}
1932
1933	/// Within an extracted function, replace the constants that need to be lifted
1934	/// into arguments with the actual argument.
1935	///
1936	/// \param Region [in] - The region of extracted code to be changed.
1937	void replaceConstants(OutlinableRegion &Region) {
1938	OutlinableGroup &Group = *Region.Parent;
1939	// Iterate over the constants that need to be elevated into arguments
1940	for (std::pair<unsigned, Constant *> &Const : Region.AggArgToConstant) {
1941	unsigned AggArgIdx = Const.first;
1942	Function *OutlinedFunction = Group.OutlinedFunction;
1943	assert(OutlinedFunction && "Overall Function is not defined?");
1944	Constant *CST = Const.second;
1945	Argument *Arg = Group.OutlinedFunction->getArg(i: AggArgIdx);
1946	// Identify the argument it will be elevated to, and replace instances of
1947	// that constant in the function.
1948
1949	// TODO: If in the future constants do not have one global value number,
1950	// i.e. a constant 1 could be mapped to several values, this check will
1951	// have to be more strict. It cannot be using only replaceUsesWithIf.
1952
1953	LLVM_DEBUG(dbgs() << "Replacing uses of constant " << *CST
1954	<< " in function " << *OutlinedFunction << " with "
1955	<< *Arg << "\n");
1956	CST->replaceUsesWithIf(New: Arg, ShouldReplace: [OutlinedFunction](Use &U) {
1957	if (Instruction *I = dyn_cast<Instruction>(Val: U.getUser()))
1958	return I->getFunction() == OutlinedFunction;
1959	return false;
1960	});
1961	}
1962	}
1963
1964	/// It is possible that there is a basic block that already performs the same
1965	/// stores. This returns a duplicate block, if it exists
1966	///
1967	/// \param OutputBBs [in] the blocks we are looking for a duplicate of.
1968	/// \param OutputStoreBBs [in] The existing output blocks.
1969	/// \returns an optional value with the number output block if there is a match.
1970	std::optional<unsigned> findDuplicateOutputBlock(
1971	DenseMap<Value *, BasicBlock *> &OutputBBs,
1972	std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs) {
1973
1974	bool Mismatch = false;
1975	unsigned MatchingNum = 0;
1976	// We compare the new set output blocks to the other sets of output blocks.
1977	// If they are the same number, and have identical instructions, they are
1978	// considered to be the same.
1979	for (DenseMap<Value *, BasicBlock *> &CompBBs : OutputStoreBBs) {
1980	Mismatch = false;
1981	for (std::pair<Value *, BasicBlock *> &VToB : CompBBs) {
1982	DenseMap<Value *, BasicBlock *>::iterator OutputBBIt =
1983	OutputBBs.find(Val: VToB.first);
1984	if (OutputBBIt == OutputBBs.end()) {
1985	Mismatch = true;
1986	break;
1987	}
1988
1989	BasicBlock *CompBB = VToB.second;
1990	BasicBlock *OutputBB = OutputBBIt->second;
1991	if (CompBB->size() - 1 != OutputBB->size()) {
1992	Mismatch = true;
1993	break;
1994	}
1995
1996	BasicBlock::iterator NIt = OutputBB->begin();
1997	for (Instruction &I : *CompBB) {
1998	if (isa<BranchInst>(Val: &I))
1999	continue;
2000
2001	if (!I.isIdenticalTo(I: &(*NIt))) {
2002	Mismatch = true;
2003	break;
2004	}
2005
2006	NIt++;
2007	}
2008	}
2009
2010	if (!Mismatch)
2011	return MatchingNum;
2012
2013	MatchingNum++;
2014	}
2015
2016	return std::nullopt;
2017	}
2018
2019	/// Remove empty output blocks from the outlined region.
2020	///
2021	/// \param BlocksToPrune - Mapping of return values output blocks for the \p
2022	/// Region.
2023	/// \param Region - The OutlinableRegion we are analyzing.
2024	static bool
2025	analyzeAndPruneOutputBlocks(DenseMap<Value *, BasicBlock *> &BlocksToPrune,
2026	OutlinableRegion &Region) {
2027	bool AllRemoved = true;
2028	Value *RetValueForBB;
2029	BasicBlock *NewBB;
2030	SmallVector<Value *, 4> ToRemove;
2031	// Iterate over the output blocks created in the outlined section.
2032	for (std::pair<Value *, BasicBlock *> &VtoBB : BlocksToPrune) {
2033	RetValueForBB = VtoBB.first;
2034	NewBB = VtoBB.second;
2035
2036	// If there are no instructions, we remove it from the module, and also
2037	// mark the value for removal from the return value to output block mapping.
2038	if (NewBB->size() == 0) {
2039	NewBB->eraseFromParent();
2040	ToRemove.push_back(Elt: RetValueForBB);
2041	continue;
2042	}
2043
2044	// Mark that we could not remove all the blocks since they were not all
2045	// empty.
2046	AllRemoved = false;
2047	}
2048
2049	// Remove the return value from the mapping.
2050	for (Value *V : ToRemove)
2051	BlocksToPrune.erase(Val: V);
2052
2053	// Mark the region as having the no output scheme.
2054	if (AllRemoved)
2055	Region.OutputBlockNum = -1;
2056
2057	return AllRemoved;
2058	}
2059
2060	/// For the outlined section, move needed the StoreInsts for the output
2061	/// registers into their own block. Then, determine if there is a duplicate
2062	/// output block already created.
2063	///
2064	/// \param [in] OG - The OutlinableGroup of regions to be outlined.
2065	/// \param [in] Region - The OutlinableRegion that is being analyzed.
2066	/// \param [in,out] OutputBBs - the blocks that stores for this region will be
2067	/// placed in.
2068	/// \param [in] EndBBs - the final blocks of the extracted function.
2069	/// \param [in] OutputMappings - OutputMappings the mapping of values that have
2070	/// been replaced by a new output value.
2071	/// \param [in,out] OutputStoreBBs - The existing output blocks.
2072	static void alignOutputBlockWithAggFunc(
2073	OutlinableGroup &OG, OutlinableRegion &Region,
2074	DenseMap<Value *, BasicBlock *> &OutputBBs,
2075	DenseMap<Value *, BasicBlock *> &EndBBs,
2076	const DenseMap<Value *, Value *> &OutputMappings,
2077	std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs) {
2078	// If none of the output blocks have any instructions, this means that we do
2079	// not have to determine if it matches any of the other output schemes, and we
2080	// don't have to do anything else.
2081	if (analyzeAndPruneOutputBlocks(BlocksToPrune&: OutputBBs, Region))
2082	return;
2083
2084	// Determine is there is a duplicate set of blocks.
2085	std::optional<unsigned> MatchingBB =
2086	findDuplicateOutputBlock(OutputBBs, OutputStoreBBs);
2087
2088	// If there is, we remove the new output blocks. If it does not,
2089	// we add it to our list of sets of output blocks.
2090	if (MatchingBB) {
2091	LLVM_DEBUG(dbgs() << "Set output block for region in function"
2092	<< Region.ExtractedFunction << " to " << *MatchingBB);
2093
2094	Region.OutputBlockNum = *MatchingBB;
2095	for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs)
2096	VtoBB.second->eraseFromParent();
2097	return;
2098	}
2099
2100	Region.OutputBlockNum = OutputStoreBBs.size();
2101
2102	Value *RetValueForBB;
2103	BasicBlock *NewBB;
2104	OutputStoreBBs.push_back(x: DenseMap<Value *, BasicBlock *>());
2105	for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs) {
2106	RetValueForBB = VtoBB.first;
2107	NewBB = VtoBB.second;
2108	DenseMap<Value *, BasicBlock *>::iterator VBBIt =
2109	EndBBs.find(Val: RetValueForBB);
2110	LLVM_DEBUG(dbgs() << "Create output block for region in"
2111	<< Region.ExtractedFunction << " to "
2112	<< *NewBB);
2113	BranchInst::Create(IfTrue: VBBIt->second, InsertAtEnd: NewBB);
2114	OutputStoreBBs.back().insert(KV: std::make_pair(x&: RetValueForBB, y&: NewBB));
2115	}
2116	}
2117
2118	/// Takes in a mapping, \p OldMap of ConstantValues to BasicBlocks, sorts keys,
2119	/// before creating a basic block for each \p NewMap, and inserting into the new
2120	/// block. Each BasicBlock is named with the scheme "<basename>_<key_idx>".
2121	///
2122	/// \param OldMap [in] - The mapping to base the new mapping off of.
2123	/// \param NewMap [out] - The output mapping using the keys of \p OldMap.
2124	/// \param ParentFunc [in] - The function to put the new basic block in.
2125	/// \param BaseName [in] - The start of the BasicBlock names to be appended to
2126	/// by an index value.
2127	static void createAndInsertBasicBlocks(DenseMap<Value *, BasicBlock *> &OldMap,
2128	DenseMap<Value *, BasicBlock *> &NewMap,
2129	Function *ParentFunc, Twine BaseName) {
2130	unsigned Idx = 0;
2131	std::vector<Value *> SortedKeys;
2132
2133	getSortedConstantKeys(SortedKeys, Map&: OldMap);
2134
2135	for (Value *RetVal : SortedKeys) {
2136	BasicBlock *NewBB = BasicBlock::Create(
2137	Context&: ParentFunc->getContext(),
2138	Name: Twine(BaseName) + Twine("_") + Twine(static_cast<unsigned>(Idx++)),
2139	Parent: ParentFunc);
2140	NewMap.insert(KV: std::make_pair(x&: RetVal, y&: NewBB));
2141	}
2142	}
2143
2144	/// Create the switch statement for outlined function to differentiate between
2145	/// all the output blocks.
2146	///
2147	/// For the outlined section, determine if an outlined block already exists that
2148	/// matches the needed stores for the extracted section.
2149	/// \param [in] M - The module we are outlining from.
2150	/// \param [in] OG - The group of regions to be outlined.
2151	/// \param [in] EndBBs - The final blocks of the extracted function.
2152	/// \param [in,out] OutputStoreBBs - The existing output blocks.
2153	void createSwitchStatement(
2154	Module &M, OutlinableGroup &OG, DenseMap<Value *, BasicBlock *> &EndBBs,
2155	std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs) {
2156	// We only need the switch statement if there is more than one store
2157	// combination, or there is more than one set of output blocks. The first
2158	// will occur when we store different sets of values for two different
2159	// regions. The second will occur when we have two outputs that are combined
2160	// in a PHINode outside of the region in one outlined instance, and are used
2161	// seaparately in another. This will create the same set of OutputGVNs, but
2162	// will generate two different output schemes.
2163	if (OG.OutputGVNCombinations.size() > 1) {
2164	Function *AggFunc = OG.OutlinedFunction;
2165	// Create a final block for each different return block.
2166	DenseMap<Value *, BasicBlock *> ReturnBBs;
2167	createAndInsertBasicBlocks(OldMap&: OG.EndBBs, NewMap&: ReturnBBs, ParentFunc: AggFunc, BaseName: "final_block");
2168
2169	for (std::pair<Value *, BasicBlock *> &RetBlockPair : ReturnBBs) {
2170	std::pair<Value *, BasicBlock *> &OutputBlock =
2171	*OG.EndBBs.find(Val: RetBlockPair.first);
2172	BasicBlock *ReturnBlock = RetBlockPair.second;
2173	BasicBlock *EndBB = OutputBlock.second;
2174	Instruction *Term = EndBB->getTerminator();
2175	// Move the return value to the final block instead of the original exit
2176	// stub.
2177	Term->moveBefore(BB&: *ReturnBlock, I: ReturnBlock->end());
2178	// Put the switch statement in the old end basic block for the function
2179	// with a fall through to the new return block.
2180	LLVM_DEBUG(dbgs() << "Create switch statement in " << *AggFunc << " for "
2181	<< OutputStoreBBs.size() << "\n");
2182	SwitchInst *SwitchI =
2183	SwitchInst::Create(Value: AggFunc->getArg(i: AggFunc->arg_size() - 1),
2184	Default: ReturnBlock, NumCases: OutputStoreBBs.size(), InsertAtEnd: EndBB);
2185
2186	unsigned Idx = 0;
2187	for (DenseMap<Value *, BasicBlock *> &OutputStoreBB : OutputStoreBBs) {
2188	DenseMap<Value *, BasicBlock *>::iterator OSBBIt =
2189	OutputStoreBB.find(Val: OutputBlock.first);
2190
2191	if (OSBBIt == OutputStoreBB.end())
2192	continue;
2193
2194	BasicBlock *BB = OSBBIt->second;
2195	SwitchI->addCase(
2196	OnVal: ConstantInt::get(Ty: Type::getInt32Ty(C&: M.getContext()), V: Idx), Dest: BB);
2197	Term = BB->getTerminator();
2198	Term->setSuccessor(Idx: 0, BB: ReturnBlock);
2199	Idx++;
2200	}
2201	}
2202	return;
2203	}
2204
2205	assert(OutputStoreBBs.size() < 2 && "Different store sets not handled!");
2206
2207	// If there needs to be stores, move them from the output blocks to their
2208	// corresponding ending block. We do not check that the OutputGVNCombinations
2209	// is equal to 1 here since that could just been the case where there are 0
2210	// outputs. Instead, we check whether there is more than one set of output
2211	// blocks since this is the only case where we would have to move the
2212	// stores, and erase the extraneous blocks.
2213	if (OutputStoreBBs.size() == 1) {
2214	LLVM_DEBUG(dbgs() << "Move store instructions to the end block in "
2215	<< *OG.OutlinedFunction << "\n");
2216	DenseMap<Value *, BasicBlock *> OutputBlocks = OutputStoreBBs[0];
2217	for (std::pair<Value *, BasicBlock *> &VBPair : OutputBlocks) {
2218	DenseMap<Value *, BasicBlock *>::iterator EndBBIt =
2219	EndBBs.find(Val: VBPair.first);
2220	assert(EndBBIt != EndBBs.end() && "Could not find end block");
2221	BasicBlock *EndBB = EndBBIt->second;
2222	BasicBlock *OutputBB = VBPair.second;
2223	Instruction *Term = OutputBB->getTerminator();
2224	Term->eraseFromParent();
2225	Term = EndBB->getTerminator();
2226	moveBBContents(SourceBB&: *OutputBB, TargetBB&: *EndBB);
2227	Term->moveBefore(BB&: *EndBB, I: EndBB->end());
2228	OutputBB->eraseFromParent();
2229	}
2230	}
2231	}
2232
2233	/// Fill the new function that will serve as the replacement function for all of
2234	/// the extracted regions of a certain structure from the first region in the
2235	/// list of regions. Replace this first region's extracted function with the
2236	/// new overall function.
2237	///
2238	/// \param [in] M - The module we are outlining from.
2239	/// \param [in] CurrentGroup - The group of regions to be outlined.
2240	/// \param [in,out] OutputStoreBBs - The output blocks for each different
2241	/// set of stores needed for the different functions.
2242	/// \param [in,out] FuncsToRemove - Extracted functions to erase from module
2243	/// once outlining is complete.
2244	/// \param [in] OutputMappings - Extracted functions to erase from module
2245	/// once outlining is complete.
2246	static void fillOverallFunction(
2247	Module &M, OutlinableGroup &CurrentGroup,
2248	std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs,
2249	std::vector<Function *> &FuncsToRemove,
2250	const DenseMap<Value *, Value *> &OutputMappings) {
2251	OutlinableRegion *CurrentOS = CurrentGroup.Regions[0];
2252
2253	// Move first extracted function's instructions into new function.
2254	LLVM_DEBUG(dbgs() << "Move instructions from "
2255	<< *CurrentOS->ExtractedFunction << " to instruction "
2256	<< *CurrentGroup.OutlinedFunction << "\n");
2257	moveFunctionData(Old&: *CurrentOS->ExtractedFunction,
2258	New&: *CurrentGroup.OutlinedFunction, NewEnds&: CurrentGroup.EndBBs);
2259
2260	// Transfer the attributes from the function to the new function.
2261	for (Attribute A : CurrentOS->ExtractedFunction->getAttributes().getFnAttrs())
2262	CurrentGroup.OutlinedFunction->addFnAttr(Attr: A);
2263
2264	// Create a new set of output blocks for the first extracted function.
2265	DenseMap<Value *, BasicBlock *> NewBBs;
2266	createAndInsertBasicBlocks(OldMap&: CurrentGroup.EndBBs, NewMap&: NewBBs,
2267	ParentFunc: CurrentGroup.OutlinedFunction, BaseName: "output_block_0");
2268	CurrentOS->OutputBlockNum = 0;
2269
2270	replaceArgumentUses(Region&: *CurrentOS, OutputBBs&: NewBBs, OutputMappings, FirstFunction: true);
2271	replaceConstants(Region&: *CurrentOS);
2272
2273	// We first identify if any output blocks are empty, if they are we remove
2274	// them. We then create a branch instruction to the basic block to the return
2275	// block for the function for each non empty output block.
2276	if (!analyzeAndPruneOutputBlocks(BlocksToPrune&: NewBBs, Region&: *CurrentOS)) {
2277	OutputStoreBBs.push_back(x: DenseMap<Value *, BasicBlock *>());
2278	for (std::pair<Value *, BasicBlock *> &VToBB : NewBBs) {
2279	DenseMap<Value *, BasicBlock *>::iterator VBBIt =
2280	CurrentGroup.EndBBs.find(Val: VToBB.first);
2281	BasicBlock *EndBB = VBBIt->second;
2282	BranchInst::Create(IfTrue: EndBB, InsertAtEnd: VToBB.second);
2283	OutputStoreBBs.back().insert(KV: VToBB);
2284	}
2285	}
2286
2287	// Replace the call to the extracted function with the outlined function.
2288	CurrentOS->Call = replaceCalledFunction(M, Region&: *CurrentOS);
2289
2290	// We only delete the extracted functions at the end since we may need to
2291	// reference instructions contained in them for mapping purposes.
2292	FuncsToRemove.push_back(x: CurrentOS->ExtractedFunction);
2293	}
2294
2295	void IROutliner::deduplicateExtractedSections(
2296	Module &M, OutlinableGroup &CurrentGroup,
2297	std::vector<Function *> &FuncsToRemove, unsigned &OutlinedFunctionNum) {
2298	createFunction(M, Group&: CurrentGroup, FunctionNameSuffix: OutlinedFunctionNum);
2299
2300	std::vector<DenseMap<Value *, BasicBlock *>> OutputStoreBBs;
2301
2302	OutlinableRegion *CurrentOS;
2303
2304	fillOverallFunction(M, CurrentGroup, OutputStoreBBs, FuncsToRemove,
2305	OutputMappings);
2306
2307	std::vector<Value *> SortedKeys;
2308	for (unsigned Idx = 1; Idx < CurrentGroup.Regions.size(); Idx++) {
2309	CurrentOS = CurrentGroup.Regions[Idx];
2310	AttributeFuncs::mergeAttributesForOutlining(Base&: *CurrentGroup.OutlinedFunction,
2311	ToMerge: *CurrentOS->ExtractedFunction);
2312
2313	// Create a set of BasicBlocks, one for each return block, to hold the
2314	// needed store instructions.
2315	DenseMap<Value *, BasicBlock *> NewBBs;
2316	createAndInsertBasicBlocks(
2317	OldMap&: CurrentGroup.EndBBs, NewMap&: NewBBs, ParentFunc: CurrentGroup.OutlinedFunction,
2318	BaseName: "output_block_" + Twine(static_cast<unsigned>(Idx)));
2319	replaceArgumentUses(Region&: *CurrentOS, OutputBBs&: NewBBs, OutputMappings);
2320	alignOutputBlockWithAggFunc(OG&: CurrentGroup, Region&: *CurrentOS, OutputBBs&: NewBBs,
2321	EndBBs&: CurrentGroup.EndBBs, OutputMappings,
2322	OutputStoreBBs);
2323
2324	CurrentOS->Call = replaceCalledFunction(M, Region&: *CurrentOS);
2325	FuncsToRemove.push_back(x: CurrentOS->ExtractedFunction);
2326	}
2327
2328	// Create a switch statement to handle the different output schemes.
2329	createSwitchStatement(M, OG&: CurrentGroup, EndBBs&: CurrentGroup.EndBBs, OutputStoreBBs);
2330
2331	OutlinedFunctionNum++;
2332	}
2333
2334	/// Checks that the next instruction in the InstructionDataList matches the
2335	/// next instruction in the module. If they do not, there could be the
2336	/// possibility that extra code has been inserted, and we must ignore it.
2337	///
2338	/// \param ID - The IRInstructionData to check the next instruction of.
2339	/// \returns true if the InstructionDataList and actual instruction match.
2340	static bool nextIRInstructionDataMatchesNextInst(IRInstructionData &ID) {
2341	// We check if there is a discrepancy between the InstructionDataList
2342	// and the actual next instruction in the module. If there is, it means
2343	// that an extra instruction was added, likely by the CodeExtractor.
2344
2345	// Since we do not have any similarity data about this particular
2346	// instruction, we cannot confidently outline it, and must discard this
2347	// candidate.
2348	IRInstructionDataList::iterator NextIDIt = std::next(x: ID.getIterator());
2349	Instruction *NextIDLInst = NextIDIt->Inst;
2350	Instruction *NextModuleInst = nullptr;
2351	if (!ID.Inst->isTerminator())
2352	NextModuleInst = ID.Inst->getNextNonDebugInstruction();
2353	else if (NextIDLInst != nullptr)
2354	NextModuleInst =
2355	&*NextIDIt->Inst->getParent()->instructionsWithoutDebug().begin();
2356
2357	if (NextIDLInst && NextIDLInst != NextModuleInst)
2358	return false;
2359
2360	return true;
2361	}
2362
2363	bool IROutliner::isCompatibleWithAlreadyOutlinedCode(
2364	const OutlinableRegion &Region) {
2365	IRSimilarityCandidate *IRSC = Region.Candidate;
2366	unsigned StartIdx = IRSC->getStartIdx();
2367	unsigned EndIdx = IRSC->getEndIdx();
2368
2369	// A check to make sure that we are not about to attempt to outline something
2370	// that has already been outlined.
2371	for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
2372	if (Outlined.contains(V: Idx))
2373	return false;
2374
2375	// We check if the recorded instruction matches the actual next instruction,
2376	// if it does not, we fix it in the InstructionDataList.
2377	if (!Region.Candidate->backInstruction()->isTerminator()) {
2378	Instruction *NewEndInst =
2379	Region.Candidate->backInstruction()->getNextNonDebugInstruction();
2380	assert(NewEndInst && "Next instruction is a nullptr?");
2381	if (Region.Candidate->end()->Inst != NewEndInst) {
2382	IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
2383	IRInstructionData *NewEndIRID = new (InstDataAllocator.Allocate())
2384	IRInstructionData(*NewEndInst,
2385	InstructionClassifier.visit(I&: *NewEndInst), *IDL);
2386
2387	// Insert the first IRInstructionData of the new region after the
2388	// last IRInstructionData of the IRSimilarityCandidate.
2389	IDL->insert(I: Region.Candidate->end(), Node&: *NewEndIRID);
2390	}
2391	}
2392
2393	return none_of(Range&: *IRSC, P: [this](IRInstructionData &ID) {
2394	if (!nextIRInstructionDataMatchesNextInst(ID))
2395	return true;
2396
2397	return !this->InstructionClassifier.visit(I: ID.Inst);
2398	});
2399	}
2400
2401	void IROutliner::pruneIncompatibleRegions(
2402	std::vector<IRSimilarityCandidate> &CandidateVec,
2403	OutlinableGroup &CurrentGroup) {
2404	bool PreviouslyOutlined;
2405
2406	// Sort from beginning to end, so the IRSimilarityCandidates are in order.
2407	stable_sort(Range&: CandidateVec, C: [](const IRSimilarityCandidate &LHS,
2408	const IRSimilarityCandidate &RHS) {
2409	return LHS.getStartIdx() < RHS.getStartIdx();
2410	});
2411
2412	IRSimilarityCandidate &FirstCandidate = CandidateVec[0];
2413	// Since outlining a call and a branch instruction will be the same as only
2414	// outlinining a call instruction, we ignore it as a space saving.
2415	if (FirstCandidate.getLength() == 2) {
2416	if (isa<CallInst>(Val: FirstCandidate.front()->Inst) &&
2417	isa<BranchInst>(Val: FirstCandidate.back()->Inst))
2418	return;
2419	}
2420
2421	unsigned CurrentEndIdx = 0;
2422	for (IRSimilarityCandidate &IRSC : CandidateVec) {
2423	PreviouslyOutlined = false;
2424	unsigned StartIdx = IRSC.getStartIdx();
2425	unsigned EndIdx = IRSC.getEndIdx();
2426	const Function &FnForCurrCand = *IRSC.getFunction();
2427
2428	for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
2429	if (Outlined.contains(V: Idx)) {
2430	PreviouslyOutlined = true;
2431	break;
2432	}
2433
2434	if (PreviouslyOutlined)
2435	continue;
2436
2437	// Check over the instructions, and if the basic block has its address
2438	// taken for use somewhere else, we do not outline that block.
2439	bool BBHasAddressTaken = any_of(Range&: IRSC, P: [](IRInstructionData &ID){
2440	return ID.Inst->getParent()->hasAddressTaken();
2441	});
2442
2443	if (BBHasAddressTaken)
2444	continue;
2445
2446	if (FnForCurrCand.hasOptNone())
2447	continue;
2448
2449	if (FnForCurrCand.hasFnAttribute(Kind: "nooutline")) {
2450	LLVM_DEBUG({
2451	dbgs() << "... Skipping function with nooutline attribute: "
2452	<< FnForCurrCand.getName() << "\n";
2453	});
2454	continue;
2455	}
2456
2457	if (IRSC.front()->Inst->getFunction()->hasLinkOnceODRLinkage() &&
2458	!OutlineFromLinkODRs)
2459	continue;
2460
2461	// Greedily prune out any regions that will overlap with already chosen
2462	// regions.
2463	if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
2464	continue;
2465
2466	bool BadInst = any_of(Range&: IRSC, P: [this](IRInstructionData &ID) {
2467	if (!nextIRInstructionDataMatchesNextInst(ID))
2468	return true;
2469
2470	return !this->InstructionClassifier.visit(I: ID.Inst);
2471	});
2472
2473	if (BadInst)
2474	continue;
2475
2476	OutlinableRegion *OS = new (RegionAllocator.Allocate())
2477	OutlinableRegion(IRSC, CurrentGroup);
2478	CurrentGroup.Regions.push_back(x: OS);
2479
2480	CurrentEndIdx = EndIdx;
2481	}
2482	}
2483
2484	InstructionCost
2485	IROutliner::findBenefitFromAllRegions(OutlinableGroup &CurrentGroup) {
2486	InstructionCost RegionBenefit = 0;
2487	for (OutlinableRegion *Region : CurrentGroup.Regions) {
2488	TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
2489	// We add the number of instructions in the region to the benefit as an
2490	// estimate as to how much will be removed.
2491	RegionBenefit += Region->getBenefit(TTI);
2492	LLVM_DEBUG(dbgs() << "Adding: " << RegionBenefit
2493	<< " saved instructions to overfall benefit.\n");
2494	}
2495
2496	return RegionBenefit;
2497	}
2498
2499	/// For the \p OutputCanon number passed in find the value represented by this
2500	/// canonical number. If it is from a PHINode, we pick the first incoming
2501	/// value and return that Value instead.
2502	///
2503	/// \param Region - The OutlinableRegion to get the Value from.
2504	/// \param OutputCanon - The canonical number to find the Value from.
2505	/// \returns The Value represented by a canonical number \p OutputCanon in \p
2506	/// Region.
2507	static Value *findOutputValueInRegion(OutlinableRegion &Region,
2508	unsigned OutputCanon) {
2509	OutlinableGroup &CurrentGroup = *Region.Parent;
2510	// If the value is greater than the value in the tracker, we have a
2511	// PHINode and will instead use one of the incoming values to find the
2512	// type.
2513	if (OutputCanon > CurrentGroup.PHINodeGVNTracker) {
2514	auto It = CurrentGroup.PHINodeGVNToGVNs.find(Val: OutputCanon);
2515	assert(It != CurrentGroup.PHINodeGVNToGVNs.end() &&
2516	"Could not find GVN set for PHINode number!");
2517	assert(It->second.second.size() > 0 && "PHINode does not have any values!");
2518	OutputCanon = *It->second.second.begin();
2519	}
2520	std::optional<unsigned> OGVN =
2521	Region.Candidate->fromCanonicalNum(N: OutputCanon);
2522	assert(OGVN && "Could not find GVN for Canonical Number?");
2523	std::optional<Value *> OV = Region.Candidate->fromGVN(Num: *OGVN);
2524	assert(OV && "Could not find value for GVN?");
2525	return *OV;
2526	}
2527
2528	InstructionCost
2529	IROutliner::findCostOutputReloads(OutlinableGroup &CurrentGroup) {
2530	InstructionCost OverallCost = 0;
2531	for (OutlinableRegion *Region : CurrentGroup.Regions) {
2532	TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
2533
2534	// Each output incurs a load after the call, so we add that to the cost.
2535	for (unsigned OutputCanon : Region->GVNStores) {
2536	Value *V = findOutputValueInRegion(Region&: *Region, OutputCanon);
2537	InstructionCost LoadCost =
2538	TTI.getMemoryOpCost(Opcode: Instruction::Load, Src: V->getType(), Alignment: Align(1), AddressSpace: 0,
2539	CostKind: TargetTransformInfo::TCK_CodeSize);
2540
2541	LLVM_DEBUG(dbgs() << "Adding: " << LoadCost
2542	<< " instructions to cost for output of type "
2543	<< *V->getType() << "\n");
2544	OverallCost += LoadCost;
2545	}
2546	}
2547
2548	return OverallCost;
2549	}
2550
2551	/// Find the extra instructions needed to handle any output values for the
2552	/// region.
2553	///
2554	/// \param [in] M - The Module to outline from.
2555	/// \param [in] CurrentGroup - The collection of OutlinableRegions to analyze.
2556	/// \param [in] TTI - The TargetTransformInfo used to collect information for
2557	/// new instruction costs.
2558	/// \returns the additional cost to handle the outputs.
2559	static InstructionCost findCostForOutputBlocks(Module &M,
2560	OutlinableGroup &CurrentGroup,
2561	TargetTransformInfo &TTI) {
2562	InstructionCost OutputCost = 0;
2563	unsigned NumOutputBranches = 0;
2564
2565	OutlinableRegion &FirstRegion = *CurrentGroup.Regions[0];
2566	IRSimilarityCandidate &Candidate = *CurrentGroup.Regions[0]->Candidate;
2567	DenseSet<BasicBlock *> CandidateBlocks;
2568	Candidate.getBasicBlocks(BBSet&: CandidateBlocks);
2569
2570	// Count the number of different output branches that point to blocks outside
2571	// of the region.
2572	DenseSet<BasicBlock *> FoundBlocks;
2573	for (IRInstructionData &ID : Candidate) {
2574	if (!isa<BranchInst>(Val: ID.Inst))
2575	continue;
2576
2577	for (Value *V : ID.OperVals) {
2578	BasicBlock *BB = static_cast<BasicBlock *>(V);
2579	if (!CandidateBlocks.contains(V: BB) && FoundBlocks.insert(V: BB).second)
2580	NumOutputBranches++;
2581	}
2582	}
2583
2584	CurrentGroup.BranchesToOutside = NumOutputBranches;
2585
2586	for (const ArrayRef<unsigned> &OutputUse :
2587	CurrentGroup.OutputGVNCombinations) {
2588	for (unsigned OutputCanon : OutputUse) {
2589	Value *V = findOutputValueInRegion(Region&: FirstRegion, OutputCanon);
2590	InstructionCost StoreCost =
2591	TTI.getMemoryOpCost(Opcode: Instruction::Load, Src: V->getType(), Alignment: Align(1), AddressSpace: 0,
2592	CostKind: TargetTransformInfo::TCK_CodeSize);
2593
2594	// An instruction cost is added for each store set that needs to occur for
2595	// various output combinations inside the function, plus a branch to
2596	// return to the exit block.
2597	LLVM_DEBUG(dbgs() << "Adding: " << StoreCost
2598	<< " instructions to cost for output of type "
2599	<< *V->getType() << "\n");
2600	OutputCost += StoreCost * NumOutputBranches;
2601	}
2602
2603	InstructionCost BranchCost =
2604	TTI.getCFInstrCost(Opcode: Instruction::Br, CostKind: TargetTransformInfo::TCK_CodeSize);
2605	LLVM_DEBUG(dbgs() << "Adding " << BranchCost << " to the current cost for"
2606	<< " a branch instruction\n");
2607	OutputCost += BranchCost * NumOutputBranches;
2608	}
2609
2610	// If there is more than one output scheme, we must have a comparison and
2611	// branch for each different item in the switch statement.
2612	if (CurrentGroup.OutputGVNCombinations.size() > 1) {
2613	InstructionCost ComparisonCost = TTI.getCmpSelInstrCost(
2614	Opcode: Instruction::ICmp, ValTy: Type::getInt32Ty(C&: M.getContext()),
2615	CondTy: Type::getInt32Ty(C&: M.getContext()), VecPred: CmpInst::BAD_ICMP_PREDICATE,
2616	CostKind: TargetTransformInfo::TCK_CodeSize);
2617	InstructionCost BranchCost =
2618	TTI.getCFInstrCost(Opcode: Instruction::Br, CostKind: TargetTransformInfo::TCK_CodeSize);
2619
2620	unsigned DifferentBlocks = CurrentGroup.OutputGVNCombinations.size();
2621	InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
2622
2623	LLVM_DEBUG(dbgs() << "Adding: " << TotalCost
2624	<< " instructions for each switch case for each different"
2625	<< " output path in a function\n");
2626	OutputCost += TotalCost * NumOutputBranches;
2627	}
2628
2629	return OutputCost;
2630	}
2631
2632	void IROutliner::findCostBenefit(Module &M, OutlinableGroup &CurrentGroup) {
2633	InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
2634	CurrentGroup.Benefit += RegionBenefit;
2635	LLVM_DEBUG(dbgs() << "Current Benefit: " << CurrentGroup.Benefit << "\n");
2636
2637	InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);
2638	CurrentGroup.Cost += OutputReloadCost;
2639	LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2640
2641	InstructionCost AverageRegionBenefit =
2642	RegionBenefit / CurrentGroup.Regions.size();
2643	unsigned OverallArgumentNum = CurrentGroup.ArgumentTypes.size();
2644	unsigned NumRegions = CurrentGroup.Regions.size();
2645	TargetTransformInfo &TTI =
2646	getTTI(*CurrentGroup.Regions[0]->Candidate->getFunction());
2647
2648	// We add one region to the cost once, to account for the instructions added
2649	// inside of the newly created function.
2650	LLVM_DEBUG(dbgs() << "Adding: " << AverageRegionBenefit
2651	<< " instructions to cost for body of new function.\n");
2652	CurrentGroup.Cost += AverageRegionBenefit;
2653	LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2654
2655	// For each argument, we must add an instruction for loading the argument
2656	// out of the register and into a value inside of the newly outlined function.
2657	LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNum
2658	<< " instructions to cost for each argument in the new"
2659	<< " function.\n");
2660	CurrentGroup.Cost +=
2661	OverallArgumentNum * TargetTransformInfo::TCC_Basic;
2662	LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2663
2664	// Each argument needs to either be loaded into a register or onto the stack.
2665	// Some arguments will only be loaded into the stack once the argument
2666	// registers are filled.
2667	LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNum
2668	<< " instructions to cost for each argument in the new"
2669	<< " function " << NumRegions << " times for the "
2670	<< "needed argument handling at the call site.\n");
2671	CurrentGroup.Cost +=
2672	2 * OverallArgumentNum * TargetTransformInfo::TCC_Basic * NumRegions;
2673	LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2674
2675	CurrentGroup.Cost += findCostForOutputBlocks(M, CurrentGroup, TTI);
2676	LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");
2677	}
2678
2679	void IROutliner::updateOutputMapping(OutlinableRegion &Region,
2680	ArrayRef<Value *> Outputs,
2681	LoadInst *LI) {
2682	// For and load instructions following the call
2683	Value *Operand = LI->getPointerOperand();
2684	std::optional<unsigned> OutputIdx;
2685	// Find if the operand it is an output register.
2686	for (unsigned ArgIdx = Region.NumExtractedInputs;
2687	ArgIdx < Region.Call->arg_size(); ArgIdx++) {
2688	if (Operand == Region.Call->getArgOperand(i: ArgIdx)) {
2689	OutputIdx = ArgIdx - Region.NumExtractedInputs;
2690	break;
2691	}
2692	}
2693
2694	// If we found an output register, place a mapping of the new value
2695	// to the original in the mapping.
2696	if (!OutputIdx)
2697	return;
2698
2699	if (!OutputMappings.contains(Val: Outputs[*OutputIdx])) {
2700	LLVM_DEBUG(dbgs() << "Mapping extracted output " << *LI << " to "
2701	<< *Outputs[*OutputIdx] << "\n");
2702	OutputMappings.insert(KV: std::make_pair(x&: LI, y: Outputs[*OutputIdx]));
2703	} else {
2704	Value *Orig = OutputMappings.find(Val: Outputs[*OutputIdx])->second;
2705	LLVM_DEBUG(dbgs() << "Mapping extracted output " << *Orig << " to "
2706	<< *Outputs[*OutputIdx] << "\n");
2707	OutputMappings.insert(KV: std::make_pair(x&: LI, y&: Orig));
2708	}
2709	}
2710
2711	bool IROutliner::extractSection(OutlinableRegion &Region) {
2712	SetVector<Value *> ArgInputs, Outputs, SinkCands;
2713	assert(Region.StartBB && "StartBB for the OutlinableRegion is nullptr!");
2714	BasicBlock *InitialStart = Region.StartBB;
2715	Function *OrigF = Region.StartBB->getParent();
2716	CodeExtractorAnalysisCache CEAC(*OrigF);
2717	Region.ExtractedFunction =
2718	Region.CE->extractCodeRegion(CEAC, Inputs&: ArgInputs, Outputs);
2719
2720	// If the extraction was successful, find the BasicBlock, and reassign the
2721	// OutlinableRegion blocks
2722	if (!Region.ExtractedFunction) {
2723	LLVM_DEBUG(dbgs() << "CodeExtractor failed to outline " << Region.StartBB
2724	<< "\n");
2725	Region.reattachCandidate();
2726	return false;
2727	}
2728
2729	// Get the block containing the called branch, and reassign the blocks as
2730	// necessary. If the original block still exists, it is because we ended on
2731	// a branch instruction, and so we move the contents into the block before
2732	// and assign the previous block correctly.
2733	User *InstAsUser = Region.ExtractedFunction->user_back();
2734	BasicBlock *RewrittenBB = cast<Instruction>(Val: InstAsUser)->getParent();
2735	Region.PrevBB = RewrittenBB->getSinglePredecessor();
2736	assert(Region.PrevBB && "PrevBB is nullptr?");
2737	if (Region.PrevBB == InitialStart) {
2738	BasicBlock *NewPrev = InitialStart->getSinglePredecessor();
2739	Instruction *BI = NewPrev->getTerminator();
2740	BI->eraseFromParent();
2741	moveBBContents(SourceBB&: *InitialStart, TargetBB&: *NewPrev);
2742	Region.PrevBB = NewPrev;
2743	InitialStart->eraseFromParent();
2744	}
2745
2746	Region.StartBB = RewrittenBB;
2747	Region.EndBB = RewrittenBB;
2748
2749	// The sequences of outlinable regions has now changed. We must fix the
2750	// IRInstructionDataList for consistency. Although they may not be illegal
2751	// instructions, they should not be compared with anything else as they
2752	// should not be outlined in this round. So marking these as illegal is
2753	// allowed.
2754	IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
2755	Instruction *BeginRewritten = &*RewrittenBB->begin();
2756	Instruction *EndRewritten = &*RewrittenBB->begin();
2757	Region.NewFront = new (InstDataAllocator.Allocate()) IRInstructionData(
2758	*BeginRewritten, InstructionClassifier.visit(I&: *BeginRewritten), *IDL);
2759	Region.NewBack = new (InstDataAllocator.Allocate()) IRInstructionData(
2760	*EndRewritten, InstructionClassifier.visit(I&: *EndRewritten), *IDL);
2761
2762	// Insert the first IRInstructionData of the new region in front of the
2763	// first IRInstructionData of the IRSimilarityCandidate.
2764	IDL->insert(I: Region.Candidate->begin(), Node&: *Region.NewFront);
2765	// Insert the first IRInstructionData of the new region after the
2766	// last IRInstructionData of the IRSimilarityCandidate.
2767	IDL->insert(I: Region.Candidate->end(), Node&: *Region.NewBack);
2768	// Remove the IRInstructionData from the IRSimilarityCandidate.
2769	IDL->erase(First: Region.Candidate->begin(), Last: std::prev(x: Region.Candidate->end()));
2770
2771	assert(RewrittenBB != nullptr &&
2772	"Could not find a predecessor after extraction!");
2773
2774	// Iterate over the new set of instructions to find the new call
2775	// instruction.
2776	for (Instruction &I : *RewrittenBB)
2777	if (CallInst *CI = dyn_cast<CallInst>(Val: &I)) {
2778	if (Region.ExtractedFunction == CI->getCalledFunction())
2779	Region.Call = CI;
2780	} else if (LoadInst *LI = dyn_cast<LoadInst>(Val: &I))
2781	updateOutputMapping(Region, Outputs: Outputs.getArrayRef(), LI);
2782	Region.reattachCandidate();
2783	return true;
2784	}
2785
2786	unsigned IROutliner::doOutline(Module &M) {
2787	// Find the possible similarity sections.
2788	InstructionClassifier.EnableBranches = !DisableBranches;
2789	InstructionClassifier.EnableIndirectCalls = !DisableIndirectCalls;
2790	InstructionClassifier.EnableIntrinsics = !DisableIntrinsics;
2791
2792	IRSimilarityIdentifier &Identifier = getIRSI(M);
2793	SimilarityGroupList &SimilarityCandidates = *Identifier.getSimilarity();
2794
2795	// Sort them by size of extracted sections
2796	unsigned OutlinedFunctionNum = 0;
2797	// If we only have one SimilarityGroup in SimilarityCandidates, we do not have
2798	// to sort them by the potential number of instructions to be outlined
2799	if (SimilarityCandidates.size() > 1)
2800	llvm::stable_sort(Range&: SimilarityCandidates,
2801	C: [](const std::vector<IRSimilarityCandidate> &LHS,
2802	const std::vector<IRSimilarityCandidate> &RHS) {
2803	return LHS[0].getLength() * LHS.size() >
2804	RHS[0].getLength() * RHS.size();
2805	});
2806	// Creating OutlinableGroups for each SimilarityCandidate to be used in
2807	// each of the following for loops to avoid making an allocator.
2808	std::vector<OutlinableGroup> PotentialGroups(SimilarityCandidates.size());
2809
2810	DenseSet<unsigned> NotSame;
2811	std::vector<OutlinableGroup *> NegativeCostGroups;
2812	std::vector<OutlinableRegion *> OutlinedRegions;
2813	// Iterate over the possible sets of similarity.
2814	unsigned PotentialGroupIdx = 0;
2815	for (SimilarityGroup &CandidateVec : SimilarityCandidates) {
2816	OutlinableGroup &CurrentGroup = PotentialGroups[PotentialGroupIdx++];
2817
2818	// Remove entries that were previously outlined
2819	pruneIncompatibleRegions(CandidateVec, CurrentGroup);
2820
2821	// We pruned the number of regions to 0 to 1, meaning that it's not worth
2822	// trying to outlined since there is no compatible similar instance of this
2823	// code.
2824	if (CurrentGroup.Regions.size() < 2)
2825	continue;
2826
2827	// Determine if there are any values that are the same constant throughout
2828	// each section in the set.
2829	NotSame.clear();
2830	CurrentGroup.findSameConstants(NotSame);
2831
2832	if (CurrentGroup.IgnoreGroup)
2833	continue;
2834
2835	// Create a CodeExtractor for each outlinable region. Identify inputs and
2836	// outputs for each section using the code extractor and create the argument
2837	// types for the Aggregate Outlining Function.
2838	OutlinedRegions.clear();
2839	for (OutlinableRegion *OS : CurrentGroup.Regions) {
2840	// Break the outlinable region out of its parent BasicBlock into its own
2841	// BasicBlocks (see function implementation).
2842	OS->splitCandidate();
2843
2844	// There's a chance that when the region is split, extra instructions are
2845	// added to the region. This makes the region no longer viable
2846	// to be split, so we ignore it for outlining.
2847	if (!OS->CandidateSplit)
2848	continue;
2849
2850	SmallVector<BasicBlock *> BE;
2851	DenseSet<BasicBlock *> BlocksInRegion;
2852	OS->Candidate->getBasicBlocks(BBSet&: BlocksInRegion, BBList&: BE);
2853	OS->CE = new (ExtractorAllocator.Allocate())
2854	CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
2855	false, nullptr, "outlined");
2856	findAddInputsOutputs(M, Region&: *OS, NotSame);
2857	if (!OS->IgnoreRegion)
2858	OutlinedRegions.push_back(x: OS);
2859
2860	// We recombine the blocks together now that we have gathered all the
2861	// needed information.
2862	OS->reattachCandidate();
2863	}
2864
2865	CurrentGroup.Regions = std::move(OutlinedRegions);
2866
2867	if (CurrentGroup.Regions.empty())
2868	continue;
2869
2870	CurrentGroup.collectGVNStoreSets(M);
2871
2872	if (CostModel)
2873	findCostBenefit(M, CurrentGroup);
2874
2875	// If we are adhering to the cost model, skip those groups where the cost
2876	// outweighs the benefits.
2877	if (CurrentGroup.Cost >= CurrentGroup.Benefit && CostModel) {
2878	OptimizationRemarkEmitter &ORE =
2879	getORE(*CurrentGroup.Regions[0]->Candidate->getFunction());
2880	ORE.emit(RemarkBuilder: [&]() {
2881	IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
2882	OptimizationRemarkMissed R(DEBUG_TYPE, "WouldNotDecreaseSize",
2883	C->frontInstruction());
2884	R << "did not outline "
2885	<< ore::NV(std::to_string(val: CurrentGroup.Regions.size()))
2886	<< " regions due to estimated increase of "
2887	<< ore::NV("InstructionIncrease",
2888	CurrentGroup.Cost - CurrentGroup.Benefit)
2889	<< " instructions at locations ";
2890	interleave(
2891	begin: CurrentGroup.Regions.begin(), end: CurrentGroup.Regions.end(),
2892	each_fn: [&R](OutlinableRegion *Region) {
2893	R << ore::NV(
2894	"DebugLoc",
2895	Region->Candidate->frontInstruction()->getDebugLoc());
2896	},
2897	between_fn: [&R]() { R << " "; });
2898	return R;
2899	});
2900	continue;
2901	}
2902
2903	NegativeCostGroups.push_back(x: &CurrentGroup);
2904	}
2905
2906	ExtractorAllocator.DestroyAll();
2907
2908	if (NegativeCostGroups.size() > 1)
2909	stable_sort(Range&: NegativeCostGroups,
2910	C: [](const OutlinableGroup *LHS, const OutlinableGroup *RHS) {
2911	return LHS->Benefit - LHS->Cost > RHS->Benefit - RHS->Cost;
2912	});
2913
2914	std::vector<Function *> FuncsToRemove;
2915	for (OutlinableGroup *CG : NegativeCostGroups) {
2916	OutlinableGroup &CurrentGroup = *CG;
2917
2918	OutlinedRegions.clear();
2919	for (OutlinableRegion *Region : CurrentGroup.Regions) {
2920	// We check whether our region is compatible with what has already been
2921	// outlined, and whether we need to ignore this item.
2922	if (!isCompatibleWithAlreadyOutlinedCode(Region: *Region))
2923	continue;
2924	OutlinedRegions.push_back(x: Region);
2925	}
2926
2927	if (OutlinedRegions.size() < 2)
2928	continue;
2929
2930	// Reestimate the cost and benefit of the OutlinableGroup. Continue only if
2931	// we are still outlining enough regions to make up for the added cost.
2932	CurrentGroup.Regions = std::move(OutlinedRegions);
2933	if (CostModel) {
2934	CurrentGroup.Benefit = 0;
2935	CurrentGroup.Cost = 0;
2936	findCostBenefit(M, CurrentGroup);
2937	if (CurrentGroup.Cost >= CurrentGroup.Benefit)
2938	continue;
2939	}
2940	OutlinedRegions.clear();
2941	for (OutlinableRegion *Region : CurrentGroup.Regions) {
2942	Region->splitCandidate();
2943	if (!Region->CandidateSplit)
2944	continue;
2945	OutlinedRegions.push_back(x: Region);
2946	}
2947
2948	CurrentGroup.Regions = std::move(OutlinedRegions);
2949	if (CurrentGroup.Regions.size() < 2) {
2950	for (OutlinableRegion *R : CurrentGroup.Regions)
2951	R->reattachCandidate();
2952	continue;
2953	}
2954
2955	LLVM_DEBUG(dbgs() << "Outlining regions with cost " << CurrentGroup.Cost
2956	<< " and benefit " << CurrentGroup.Benefit << "\n");
2957
2958	// Create functions out of all the sections, and mark them as outlined.
2959	OutlinedRegions.clear();
2960	for (OutlinableRegion *OS : CurrentGroup.Regions) {
2961	SmallVector<BasicBlock *> BE;
2962	DenseSet<BasicBlock *> BlocksInRegion;
2963	OS->Candidate->getBasicBlocks(BBSet&: BlocksInRegion, BBList&: BE);
2964	OS->CE = new (ExtractorAllocator.Allocate())
2965	CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
2966	false, nullptr, "outlined");
2967	bool FunctionOutlined = extractSection(Region&: *OS);
2968	if (FunctionOutlined) {
2969	unsigned StartIdx = OS->Candidate->getStartIdx();
2970	unsigned EndIdx = OS->Candidate->getEndIdx();
2971	for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
2972	Outlined.insert(V: Idx);
2973
2974	OutlinedRegions.push_back(x: OS);
2975	}
2976	}
2977
2978	LLVM_DEBUG(dbgs() << "Outlined " << OutlinedRegions.size()
2979	<< " with benefit " << CurrentGroup.Benefit
2980	<< " and cost " << CurrentGroup.Cost << "\n");
2981
2982	CurrentGroup.Regions = std::move(OutlinedRegions);
2983
2984	if (CurrentGroup.Regions.empty())
2985	continue;
2986
2987	OptimizationRemarkEmitter &ORE =
2988	getORE(*CurrentGroup.Regions[0]->Call->getFunction());
2989	ORE.emit(RemarkBuilder: [&]() {
2990	IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
2991	OptimizationRemark R(DEBUG_TYPE, "Outlined", C->front()->Inst);
2992	R << "outlined " << ore::NV(std::to_string(val: CurrentGroup.Regions.size()))
2993	<< " regions with decrease of "
2994	<< ore::NV("Benefit", CurrentGroup.Benefit - CurrentGroup.Cost)
2995	<< " instructions at locations ";
2996	interleave(
2997	begin: CurrentGroup.Regions.begin(), end: CurrentGroup.Regions.end(),
2998	each_fn: [&R](OutlinableRegion *Region) {
2999	R << ore::NV("DebugLoc",
3000	Region->Candidate->frontInstruction()->getDebugLoc());
3001	},
3002	between_fn: [&R]() { R << " "; });
3003	return R;
3004	});
3005
3006	deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,
3007	OutlinedFunctionNum);
3008	}
3009
3010	for (Function *F : FuncsToRemove)
3011	F->eraseFromParent();
3012
3013	return OutlinedFunctionNum;
3014	}
3015
3016	bool IROutliner::run(Module &M) {
3017	CostModel = !NoCostModel;
3018	OutlineFromLinkODRs = EnableLinkOnceODRIROutlining;
3019
3020	return doOutline(M) > 0;
3021	}
3022
3023	PreservedAnalyses IROutlinerPass::run(Module &M, ModuleAnalysisManager &AM) {
3024	auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
3025
3026	std::function<TargetTransformInfo &(Function &)> GTTI =
3027	[&FAM](Function &F) -> TargetTransformInfo & {
3028	return FAM.getResult<TargetIRAnalysis>(IR&: F);
3029	};
3030
3031	std::function<IRSimilarityIdentifier &(Module &)> GIRSI =
3032	[&AM](Module &M) -> IRSimilarityIdentifier & {
3033	return AM.getResult<IRSimilarityAnalysis>(IR&: M);
3034	};
3035
3036	std::unique_ptr<OptimizationRemarkEmitter> ORE;
3037	std::function<OptimizationRemarkEmitter &(Function &)> GORE =
3038	[&ORE](Function &F) -> OptimizationRemarkEmitter & {
3039	ORE.reset(p: new OptimizationRemarkEmitter(&F));
3040	return *ORE;
3041	};
3042
3043	if (IROutliner(GTTI, GIRSI, GORE).run(M))
3044	return PreservedAnalyses::none();
3045	return PreservedAnalyses::all();
3046	}
3047