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