Bug Summary

File:llvm/lib/Transforms/IPO/IROutliner.cpp
Warning:line 957, column 7
Value stored to 'WrongSize' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name IROutliner.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/IPO -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/IPO -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-04-14-063029-18377-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp
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/PassManager.h"
20#include "llvm/InitializePasses.h"
21#include "llvm/Pass.h"
22#include "llvm/Support/CommandLine.h"
23#include "llvm/Transforms/IPO.h"
24#include <map>
25#include <set>
26#include <vector>
27
28#define DEBUG_TYPE"iroutliner" "iroutliner"
29
30using namespace llvm;
31using namespace IRSimilarity;
32
33// Set to true if the user wants the ir outliner to run on linkonceodr linkage
34// functions. This is false by default because the linker can dedupe linkonceodr
35// functions. Since the outliner is confined to a single module (modulo LTO),
36// this is off by default. It should, however, be the default behavior in
37// LTO.
38static cl::opt<bool> EnableLinkOnceODRIROutlining(
39 "enable-linkonceodr-ir-outlining", cl::Hidden,
40 cl::desc("Enable the IR outliner on linkonceodr functions"),
41 cl::init(false));
42
43// This is a debug option to test small pieces of code to ensure that outlining
44// works correctly.
45static cl::opt<bool> NoCostModel(
46 "ir-outlining-no-cost", cl::init(false), cl::ReallyHidden,
47 cl::desc("Debug option to outline greedily, without restriction that "
48 "calculated benefit outweighs cost"));
49
50/// The OutlinableGroup holds all the overarching information for outlining
51/// a set of regions that are structurally similar to one another, such as the
52/// types of the overall function, the output blocks, the sets of stores needed
53/// and a list of the different regions. This information is used in the
54/// deduplication of extracted regions with the same structure.
55struct OutlinableGroup {
56 /// The sections that could be outlined
57 std::vector<OutlinableRegion *> Regions;
58
59 /// The argument types for the function created as the overall function to
60 /// replace the extracted function for each region.
61 std::vector<Type *> ArgumentTypes;
62 /// The FunctionType for the overall function.
63 FunctionType *OutlinedFunctionType = nullptr;
64 /// The Function for the collective overall function.
65 Function *OutlinedFunction = nullptr;
66
67 /// Flag for whether we should not consider this group of OutlinableRegions
68 /// for extraction.
69 bool IgnoreGroup = false;
70
71 /// The return block for the overall function.
72 BasicBlock *EndBB = nullptr;
73
74 /// A set containing the different GVN store sets needed. Each array contains
75 /// a sorted list of the different values that need to be stored into output
76 /// registers.
77 DenseSet<ArrayRef<unsigned>> OutputGVNCombinations;
78
79 /// Flag for whether the \ref ArgumentTypes have been defined after the
80 /// extraction of the first region.
81 bool InputTypesSet = false;
82
83 /// The number of input values in \ref ArgumentTypes. Anything after this
84 /// index in ArgumentTypes is an output argument.
85 unsigned NumAggregateInputs = 0;
86
87 /// The number of instructions that will be outlined by extracting \ref
88 /// Regions.
89 InstructionCost Benefit = 0;
90 /// The number of added instructions needed for the outlining of the \ref
91 /// Regions.
92 InstructionCost Cost = 0;
93
94 /// The argument that needs to be marked with the swifterr attribute. If not
95 /// needed, there is no value.
96 Optional<unsigned> SwiftErrorArgument;
97
98 /// For the \ref Regions, we look at every Value. If it is a constant,
99 /// we check whether it is the same in Region.
100 ///
101 /// \param [in,out] NotSame contains the global value numbers where the
102 /// constant is not always the same, and must be passed in as an argument.
103 void findSameConstants(DenseSet<unsigned> &NotSame);
104
105 /// For the regions, look at each set of GVN stores needed and account for
106 /// each combination. Add an argument to the argument types if there is
107 /// more than one combination.
108 ///
109 /// \param [in] M - The module we are outlining from.
110 void collectGVNStoreSets(Module &M);
111};
112
113/// Move the contents of \p SourceBB to before the last instruction of \p
114/// TargetBB.
115/// \param SourceBB - the BasicBlock to pull Instructions from.
116/// \param TargetBB - the BasicBlock to put Instruction into.
117static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB) {
118 BasicBlock::iterator BBCurr, BBEnd, BBNext;
119 for (BBCurr = SourceBB.begin(), BBEnd = SourceBB.end(); BBCurr != BBEnd;
120 BBCurr = BBNext) {
121 BBNext = std::next(BBCurr);
122 BBCurr->moveBefore(TargetBB, TargetBB.end());
123 }
124}
125
126void OutlinableRegion::splitCandidate() {
127 assert(!CandidateSplit && "Candidate already split!")((!CandidateSplit && "Candidate already split!") ? static_cast
<void> (0) : __assert_fail ("!CandidateSplit && \"Candidate already split!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 127, __PRETTY_FUNCTION__))
;
128
129 Instruction *StartInst = (*Candidate->begin()).Inst;
130 Instruction *EndInst = (*Candidate->end()).Inst;
131 assert(StartInst && EndInst && "Expected a start and end instruction?")((StartInst && EndInst && "Expected a start and end instruction?"
) ? static_cast<void> (0) : __assert_fail ("StartInst && EndInst && \"Expected a start and end instruction?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 131, __PRETTY_FUNCTION__))
;
132 StartBB = StartInst->getParent();
133 PrevBB = StartBB;
134
135 // The basic block gets split like so:
136 // block: block:
137 // inst1 inst1
138 // inst2 inst2
139 // region1 br block_to_outline
140 // region2 block_to_outline:
141 // region3 -> region1
142 // region4 region2
143 // inst3 region3
144 // inst4 region4
145 // br block_after_outline
146 // block_after_outline:
147 // inst3
148 // inst4
149
150 std::string OriginalName = PrevBB->getName().str();
151
152 StartBB = PrevBB->splitBasicBlock(StartInst, OriginalName + "_to_outline");
153
154 // This is the case for the inner block since we do not have to include
155 // multiple blocks.
156 EndBB = StartBB;
157 FollowBB = EndBB->splitBasicBlock(EndInst, OriginalName + "_after_outline");
158
159 CandidateSplit = true;
160}
161
162void OutlinableRegion::reattachCandidate() {
163 assert(CandidateSplit && "Candidate is not split!")((CandidateSplit && "Candidate is not split!") ? static_cast
<void> (0) : __assert_fail ("CandidateSplit && \"Candidate is not split!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 163, __PRETTY_FUNCTION__))
;
164
165 // The basic block gets reattached like so:
166 // block: block:
167 // inst1 inst1
168 // inst2 inst2
169 // br block_to_outline region1
170 // block_to_outline: -> region2
171 // region1 region3
172 // region2 region4
173 // region3 inst3
174 // region4 inst4
175 // br block_after_outline
176 // block_after_outline:
177 // inst3
178 // inst4
179 assert(StartBB != nullptr && "StartBB for Candidate is not defined!")((StartBB != nullptr && "StartBB for Candidate is not defined!"
) ? static_cast<void> (0) : __assert_fail ("StartBB != nullptr && \"StartBB for Candidate is not defined!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 179, __PRETTY_FUNCTION__))
;
180 assert(FollowBB != nullptr && "StartBB for Candidate is not defined!")((FollowBB != nullptr && "StartBB for Candidate is not defined!"
) ? static_cast<void> (0) : __assert_fail ("FollowBB != nullptr && \"StartBB for Candidate is not defined!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 180, __PRETTY_FUNCTION__))
;
181
182 // StartBB should only have one predecessor since we put an unconditional
183 // branch at the end of PrevBB when we split the BasicBlock.
184 PrevBB = StartBB->getSinglePredecessor();
185 assert(PrevBB != nullptr &&((PrevBB != nullptr && "No Predecessor for the region start basic block!"
) ? static_cast<void> (0) : __assert_fail ("PrevBB != nullptr && \"No Predecessor for the region start basic block!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 186, __PRETTY_FUNCTION__))
186 "No Predecessor for the region start basic block!")((PrevBB != nullptr && "No Predecessor for the region start basic block!"
) ? static_cast<void> (0) : __assert_fail ("PrevBB != nullptr && \"No Predecessor for the region start basic block!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 186, __PRETTY_FUNCTION__))
;
187
188 assert(PrevBB->getTerminator() && "Terminator removed from PrevBB!")((PrevBB->getTerminator() && "Terminator removed from PrevBB!"
) ? static_cast<void> (0) : __assert_fail ("PrevBB->getTerminator() && \"Terminator removed from PrevBB!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 188, __PRETTY_FUNCTION__))
;
189 assert(EndBB->getTerminator() && "Terminator removed from EndBB!")((EndBB->getTerminator() && "Terminator removed from EndBB!"
) ? static_cast<void> (0) : __assert_fail ("EndBB->getTerminator() && \"Terminator removed from EndBB!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 189, __PRETTY_FUNCTION__))
;
190 PrevBB->getTerminator()->eraseFromParent();
191 EndBB->getTerminator()->eraseFromParent();
192
193 moveBBContents(*StartBB, *PrevBB);
194
195 BasicBlock *PlacementBB = PrevBB;
196 if (StartBB != EndBB)
197 PlacementBB = EndBB;
198 moveBBContents(*FollowBB, *PlacementBB);
199
200 PrevBB->replaceSuccessorsPhiUsesWith(StartBB, PrevBB);
201 PrevBB->replaceSuccessorsPhiUsesWith(FollowBB, PlacementBB);
202 StartBB->eraseFromParent();
203 FollowBB->eraseFromParent();
204
205 // Make sure to save changes back to the StartBB.
206 StartBB = PrevBB;
207 EndBB = nullptr;
208 PrevBB = nullptr;
209 FollowBB = nullptr;
210
211 CandidateSplit = false;
212}
213
214/// Find whether \p V matches the Constants previously found for the \p GVN.
215///
216/// \param V - The value to check for consistency.
217/// \param GVN - The global value number assigned to \p V.
218/// \param GVNToConstant - The mapping of global value number to Constants.
219/// \returns true if the Value matches the Constant mapped to by V and false if
220/// it \p V is a Constant but does not match.
221/// \returns None if \p V is not a Constant.
222static Optional<bool>
223constantMatches(Value *V, unsigned GVN,
224 DenseMap<unsigned, Constant *> &GVNToConstant) {
225 // See if we have a constants
226 Constant *CST = dyn_cast<Constant>(V);
227 if (!CST)
228 return None;
229
230 // Holds a mapping from a global value number to a Constant.
231 DenseMap<unsigned, Constant *>::iterator GVNToConstantIt;
232 bool Inserted;
233
234
235 // If we have a constant, try to make a new entry in the GVNToConstant.
236 std::tie(GVNToConstantIt, Inserted) =
237 GVNToConstant.insert(std::make_pair(GVN, CST));
238 // If it was found and is not equal, it is not the same. We do not
239 // handle this case yet, and exit early.
240 if (Inserted || (GVNToConstantIt->second == CST))
241 return true;
242
243 return false;
244}
245
246InstructionCost OutlinableRegion::getBenefit(TargetTransformInfo &TTI) {
247 InstructionCost Benefit = 0;
248
249 // Estimate the benefit of outlining a specific sections of the program. We
250 // delegate mostly this task to the TargetTransformInfo so that if the target
251 // has specific changes, we can have a more accurate estimate.
252
253 // However, getInstructionCost delegates the code size calculation for
254 // arithmetic instructions to getArithmeticInstrCost in
255 // include/Analysis/TargetTransformImpl.h, where it always estimates that the
256 // code size for a division and remainder instruction to be equal to 4, and
257 // everything else to 1. This is not an accurate representation of the
258 // division instruction for targets that have a native division instruction.
259 // To be overly conservative, we only add 1 to the number of instructions for
260 // each division instruction.
261 for (Instruction &I : *StartBB) {
262 switch (I.getOpcode()) {
263 case Instruction::FDiv:
264 case Instruction::FRem:
265 case Instruction::SDiv:
266 case Instruction::SRem:
267 case Instruction::UDiv:
268 case Instruction::URem:
269 Benefit += 1;
270 break;
271 default:
272 Benefit += TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
273 break;
274 }
275 }
276
277 return Benefit;
278}
279
280/// Find whether \p Region matches the global value numbering to Constant
281/// mapping found so far.
282///
283/// \param Region - The OutlinableRegion we are checking for constants
284/// \param GVNToConstant - The mapping of global value number to Constants.
285/// \param NotSame - The set of global value numbers that do not have the same
286/// constant in each region.
287/// \returns true if all Constants are the same in every use of a Constant in \p
288/// Region and false if not
289static bool
290collectRegionsConstants(OutlinableRegion &Region,
291 DenseMap<unsigned, Constant *> &GVNToConstant,
292 DenseSet<unsigned> &NotSame) {
293 bool ConstantsTheSame = true;
294
295 IRSimilarityCandidate &C = *Region.Candidate;
296 for (IRInstructionData &ID : C) {
297
298 // Iterate over the operands in an instruction. If the global value number,
299 // assigned by the IRSimilarityCandidate, has been seen before, we check if
300 // the the number has been found to be not the same value in each instance.
301 for (Value *V : ID.OperVals) {
302 Optional<unsigned> GVNOpt = C.getGVN(V);
303 assert(GVNOpt.hasValue() && "Expected a GVN for operand?")((GVNOpt.hasValue() && "Expected a GVN for operand?")
? static_cast<void> (0) : __assert_fail ("GVNOpt.hasValue() && \"Expected a GVN for operand?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 303, __PRETTY_FUNCTION__))
;
304 unsigned GVN = GVNOpt.getValue();
305
306 // Check if this global value has been found to not be the same already.
307 if (NotSame.contains(GVN)) {
308 if (isa<Constant>(V))
309 ConstantsTheSame = false;
310 continue;
311 }
312
313 // If it has been the same so far, we check the value for if the
314 // associated Constant value match the previous instances of the same
315 // global value number. If the global value does not map to a Constant,
316 // it is considered to not be the same value.
317 Optional<bool> ConstantMatches = constantMatches(V, GVN, GVNToConstant);
318 if (ConstantMatches.hasValue()) {
319 if (ConstantMatches.getValue())
320 continue;
321 else
322 ConstantsTheSame = false;
323 }
324
325 // While this value is a register, it might not have been previously,
326 // make sure we don't already have a constant mapped to this global value
327 // number.
328 if (GVNToConstant.find(GVN) != GVNToConstant.end())
329 ConstantsTheSame = false;
330
331 NotSame.insert(GVN);
332 }
333 }
334
335 return ConstantsTheSame;
336}
337
338void OutlinableGroup::findSameConstants(DenseSet<unsigned> &NotSame) {
339 DenseMap<unsigned, Constant *> GVNToConstant;
340
341 for (OutlinableRegion *Region : Regions)
342 collectRegionsConstants(*Region, GVNToConstant, NotSame);
343}
344
345void OutlinableGroup::collectGVNStoreSets(Module &M) {
346 for (OutlinableRegion *OS : Regions)
347 OutputGVNCombinations.insert(OS->GVNStores);
348
349 // We are adding an extracted argument to decide between which output path
350 // to use in the basic block. It is used in a switch statement and only
351 // needs to be an integer.
352 if (OutputGVNCombinations.size() > 1)
353 ArgumentTypes.push_back(Type::getInt32Ty(M.getContext()));
354}
355
356Function *IROutliner::createFunction(Module &M, OutlinableGroup &Group,
357 unsigned FunctionNameSuffix) {
358 assert(!Group.OutlinedFunction && "Function is already defined!")((!Group.OutlinedFunction && "Function is already defined!"
) ? static_cast<void> (0) : __assert_fail ("!Group.OutlinedFunction && \"Function is already defined!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 358, __PRETTY_FUNCTION__))
;
359
360 Group.OutlinedFunctionType = FunctionType::get(
361 Type::getVoidTy(M.getContext()), Group.ArgumentTypes, false);
362
363 // These functions will only be called from within the same module, so
364 // we can set an internal linkage.
365 Group.OutlinedFunction = Function::Create(
366 Group.OutlinedFunctionType, GlobalValue::InternalLinkage,
367 "outlined_ir_func_" + std::to_string(FunctionNameSuffix), M);
368
369 // Transfer the swifterr attribute to the correct function parameter.
370 if (Group.SwiftErrorArgument.hasValue())
371 Group.OutlinedFunction->addParamAttr(Group.SwiftErrorArgument.getValue(),
372 Attribute::SwiftError);
373
374 Group.OutlinedFunction->addFnAttr(Attribute::OptimizeForSize);
375 Group.OutlinedFunction->addFnAttr(Attribute::MinSize);
376
377 return Group.OutlinedFunction;
378}
379
380/// Move each BasicBlock in \p Old to \p New.
381///
382/// \param [in] Old - the function to move the basic blocks from.
383/// \param [in] New - The function to move the basic blocks to.
384/// \returns the first return block for the function in New.
385static BasicBlock *moveFunctionData(Function &Old, Function &New) {
386 Function::iterator CurrBB, NextBB, FinalBB;
387 BasicBlock *NewEnd = nullptr;
388 std::vector<Instruction *> DebugInsts;
389 for (CurrBB = Old.begin(), FinalBB = Old.end(); CurrBB != FinalBB;
390 CurrBB = NextBB) {
391 NextBB = std::next(CurrBB);
392 CurrBB->removeFromParent();
393 CurrBB->insertInto(&New);
394 Instruction *I = CurrBB->getTerminator();
395 if (isa<ReturnInst>(I))
396 NewEnd = &(*CurrBB);
397 }
398
399 assert(NewEnd && "No return instruction for new function?")((NewEnd && "No return instruction for new function?"
) ? static_cast<void> (0) : __assert_fail ("NewEnd && \"No return instruction for new function?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 399, __PRETTY_FUNCTION__))
;
400 return NewEnd;
401}
402
403/// Find the the constants that will need to be lifted into arguments
404/// as they are not the same in each instance of the region.
405///
406/// \param [in] C - The IRSimilarityCandidate containing the region we are
407/// analyzing.
408/// \param [in] NotSame - The set of global value numbers that do not have a
409/// single Constant across all OutlinableRegions similar to \p C.
410/// \param [out] Inputs - The list containing the global value numbers of the
411/// arguments needed for the region of code.
412static void findConstants(IRSimilarityCandidate &C, DenseSet<unsigned> &NotSame,
413 std::vector<unsigned> &Inputs) {
414 DenseSet<unsigned> Seen;
415 // Iterate over the instructions, and find what constants will need to be
416 // extracted into arguments.
417 for (IRInstructionDataList::iterator IDIt = C.begin(), EndIDIt = C.end();
418 IDIt != EndIDIt; IDIt++) {
419 for (Value *V : (*IDIt).OperVals) {
420 // Since these are stored before any outlining, they will be in the
421 // global value numbering.
422 unsigned GVN = C.getGVN(V).getValue();
423 if (isa<Constant>(V))
424 if (NotSame.contains(GVN) && !Seen.contains(GVN)) {
425 Inputs.push_back(GVN);
426 Seen.insert(GVN);
427 }
428 }
429 }
430}
431
432/// Find the GVN for the inputs that have been found by the CodeExtractor.
433///
434/// \param [in] C - The IRSimilarityCandidate containing the region we are
435/// analyzing.
436/// \param [in] CurrentInputs - The set of inputs found by the
437/// CodeExtractor.
438/// \param [in] OutputMappings - The mapping of values that have been replaced
439/// by a new output value.
440/// \param [out] EndInputNumbers - The global value numbers for the extracted
441/// arguments.
442static void mapInputsToGVNs(IRSimilarityCandidate &C,
443 SetVector<Value *> &CurrentInputs,
444 const DenseMap<Value *, Value *> &OutputMappings,
445 std::vector<unsigned> &EndInputNumbers) {
446 // Get the Global Value Number for each input. We check if the Value has been
447 // replaced by a different value at output, and use the original value before
448 // replacement.
449 for (Value *Input : CurrentInputs) {
450 assert(Input && "Have a nullptr as an input")((Input && "Have a nullptr as an input") ? static_cast
<void> (0) : __assert_fail ("Input && \"Have a nullptr as an input\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 450, __PRETTY_FUNCTION__))
;
451 if (OutputMappings.find(Input) != OutputMappings.end())
452 Input = OutputMappings.find(Input)->second;
453 assert(C.getGVN(Input).hasValue() &&((C.getGVN(Input).hasValue() && "Could not find a numbering for the given input"
) ? static_cast<void> (0) : __assert_fail ("C.getGVN(Input).hasValue() && \"Could not find a numbering for the given input\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 454, __PRETTY_FUNCTION__))
454 "Could not find a numbering for the given input")((C.getGVN(Input).hasValue() && "Could not find a numbering for the given input"
) ? static_cast<void> (0) : __assert_fail ("C.getGVN(Input).hasValue() && \"Could not find a numbering for the given input\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 454, __PRETTY_FUNCTION__))
;
455 EndInputNumbers.push_back(C.getGVN(Input).getValue());
456 }
457}
458
459/// Find the original value for the \p ArgInput values if any one of them was
460/// replaced during a previous extraction.
461///
462/// \param [in] ArgInputs - The inputs to be extracted by the code extractor.
463/// \param [in] OutputMappings - The mapping of values that have been replaced
464/// by a new output value.
465/// \param [out] RemappedArgInputs - The remapped values according to
466/// \p OutputMappings that will be extracted.
467static void
468remapExtractedInputs(const ArrayRef<Value *> ArgInputs,
469 const DenseMap<Value *, Value *> &OutputMappings,
470 SetVector<Value *> &RemappedArgInputs) {
471 // Get the global value number for each input that will be extracted as an
472 // argument by the code extractor, remapping if needed for reloaded values.
473 for (Value *Input : ArgInputs) {
474 if (OutputMappings.find(Input) != OutputMappings.end())
475 Input = OutputMappings.find(Input)->second;
476 RemappedArgInputs.insert(Input);
477 }
478}
479
480/// Find the input GVNs and the output values for a region of Instructions.
481/// Using the code extractor, we collect the inputs to the extracted function.
482///
483/// The \p Region can be identified as needing to be ignored in this function.
484/// It should be checked whether it should be ignored after a call to this
485/// function.
486///
487/// \param [in,out] Region - The region of code to be analyzed.
488/// \param [out] InputGVNs - The global value numbers for the extracted
489/// arguments.
490/// \param [in] NotSame - The global value numbers in the region that do not
491/// have the same constant value in the regions structurally similar to
492/// \p Region.
493/// \param [in] OutputMappings - The mapping of values that have been replaced
494/// by a new output value after extraction.
495/// \param [out] ArgInputs - The values of the inputs to the extracted function.
496/// \param [out] Outputs - The set of values extracted by the CodeExtractor
497/// as outputs.
498static void getCodeExtractorArguments(
499 OutlinableRegion &Region, std::vector<unsigned> &InputGVNs,
500 DenseSet<unsigned> &NotSame, DenseMap<Value *, Value *> &OutputMappings,
501 SetVector<Value *> &ArgInputs, SetVector<Value *> &Outputs) {
502 IRSimilarityCandidate &C = *Region.Candidate;
503
504 // OverallInputs are the inputs to the region found by the CodeExtractor,
505 // SinkCands and HoistCands are used by the CodeExtractor to find sunken
506 // allocas of values whose lifetimes are contained completely within the
507 // outlined region. PremappedInputs are the arguments found by the
508 // CodeExtractor, removing conditions such as sunken allocas, but that
509 // may need to be remapped due to the extracted output values replacing
510 // the original values. We use DummyOutputs for this first run of finding
511 // inputs and outputs since the outputs could change during findAllocas,
512 // the correct set of extracted outputs will be in the final Outputs ValueSet.
513 SetVector<Value *> OverallInputs, PremappedInputs, SinkCands, HoistCands,
514 DummyOutputs;
515
516 // Use the code extractor to get the inputs and outputs, without sunken
517 // allocas or removing llvm.assumes.
518 CodeExtractor *CE = Region.CE;
519 CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands);
520 assert(Region.StartBB && "Region must have a start BasicBlock!")((Region.StartBB && "Region must have a start BasicBlock!"
) ? static_cast<void> (0) : __assert_fail ("Region.StartBB && \"Region must have a start BasicBlock!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 520, __PRETTY_FUNCTION__))
;
521 Function *OrigF = Region.StartBB->getParent();
522 CodeExtractorAnalysisCache CEAC(*OrigF);
523 BasicBlock *Dummy = nullptr;
524
525 // The region may be ineligible due to VarArgs in the parent function. In this
526 // case we ignore the region.
527 if (!CE->isEligible()) {
528 Region.IgnoreRegion = true;
529 return;
530 }
531
532 // Find if any values are going to be sunk into the function when extracted
533 CE->findAllocas(CEAC, SinkCands, HoistCands, Dummy);
534 CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands);
535
536 // TODO: Support regions with sunken allocas: values whose lifetimes are
537 // contained completely within the outlined region. These are not guaranteed
538 // to be the same in every region, so we must elevate them all to arguments
539 // when they appear. If these values are not equal, it means there is some
540 // Input in OverallInputs that was removed for ArgInputs.
541 if (OverallInputs.size() != PremappedInputs.size()) {
542 Region.IgnoreRegion = true;
543 return;
544 }
545
546 findConstants(C, NotSame, InputGVNs);
547
548 mapInputsToGVNs(C, OverallInputs, OutputMappings, InputGVNs);
549
550 remapExtractedInputs(PremappedInputs.getArrayRef(), OutputMappings,
551 ArgInputs);
552
553 // Sort the GVNs, since we now have constants included in the \ref InputGVNs
554 // we need to make sure they are in a deterministic order.
555 stable_sort(InputGVNs);
556}
557
558/// Look over the inputs and map each input argument to an argument in the
559/// overall function for the OutlinableRegions. This creates a way to replace
560/// the arguments of the extracted function with the arguments of the new
561/// overall function.
562///
563/// \param [in,out] Region - The region of code to be analyzed.
564/// \param [in] InputGVNs - The global value numbering of the input values
565/// collected.
566/// \param [in] ArgInputs - The values of the arguments to the extracted
567/// function.
568static void
569findExtractedInputToOverallInputMapping(OutlinableRegion &Region,
570 std::vector<unsigned> &InputGVNs,
571 SetVector<Value *> &ArgInputs) {
572
573 IRSimilarityCandidate &C = *Region.Candidate;
574 OutlinableGroup &Group = *Region.Parent;
575
576 // This counts the argument number in the overall function.
577 unsigned TypeIndex = 0;
578
579 // This counts the argument number in the extracted function.
580 unsigned OriginalIndex = 0;
581
582 // Find the mapping of the extracted arguments to the arguments for the
583 // overall function. Since there may be extra arguments in the overall
584 // function to account for the extracted constants, we have two different
585 // counters as we find extracted arguments, and as we come across overall
586 // arguments.
587 for (unsigned InputVal : InputGVNs) {
588 Optional<Value *> InputOpt = C.fromGVN(InputVal);
589 assert(InputOpt.hasValue() && "Global value number not found?")((InputOpt.hasValue() && "Global value number not found?"
) ? static_cast<void> (0) : __assert_fail ("InputOpt.hasValue() && \"Global value number not found?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 589, __PRETTY_FUNCTION__))
;
590 Value *Input = InputOpt.getValue();
591
592 if (!Group.InputTypesSet) {
593 Group.ArgumentTypes.push_back(Input->getType());
594 // If the input value has a swifterr attribute, make sure to mark the
595 // argument in the overall function.
596 if (Input->isSwiftError()) {
597 assert(((!Group.SwiftErrorArgument.hasValue() && "Argument already marked with swifterr for this OutlinableGroup!"
) ? static_cast<void> (0) : __assert_fail ("!Group.SwiftErrorArgument.hasValue() && \"Argument already marked with swifterr for this OutlinableGroup!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 599, __PRETTY_FUNCTION__))
598 !Group.SwiftErrorArgument.hasValue() &&((!Group.SwiftErrorArgument.hasValue() && "Argument already marked with swifterr for this OutlinableGroup!"
) ? static_cast<void> (0) : __assert_fail ("!Group.SwiftErrorArgument.hasValue() && \"Argument already marked with swifterr for this OutlinableGroup!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 599, __PRETTY_FUNCTION__))
599 "Argument already marked with swifterr for this OutlinableGroup!")((!Group.SwiftErrorArgument.hasValue() && "Argument already marked with swifterr for this OutlinableGroup!"
) ? static_cast<void> (0) : __assert_fail ("!Group.SwiftErrorArgument.hasValue() && \"Argument already marked with swifterr for this OutlinableGroup!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 599, __PRETTY_FUNCTION__))
;
600 Group.SwiftErrorArgument = TypeIndex;
601 }
602 }
603
604 // Check if we have a constant. If we do add it to the overall argument
605 // number to Constant map for the region, and continue to the next input.
606 if (Constant *CST = dyn_cast<Constant>(Input)) {
607 Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST));
608 TypeIndex++;
609 continue;
610 }
611
612 // It is not a constant, we create the mapping from extracted argument list
613 // to the overall argument list.
614 assert(ArgInputs.count(Input) && "Input cannot be found!")((ArgInputs.count(Input) && "Input cannot be found!")
? static_cast<void> (0) : __assert_fail ("ArgInputs.count(Input) && \"Input cannot be found!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 614, __PRETTY_FUNCTION__))
;
615
616 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex));
617 Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex));
618 OriginalIndex++;
619 TypeIndex++;
620 }
621
622 // If the function type definitions for the OutlinableGroup holding the region
623 // have not been set, set the length of the inputs here. We should have the
624 // same inputs for all of the different regions contained in the
625 // OutlinableGroup since they are all structurally similar to one another.
626 if (!Group.InputTypesSet) {
627 Group.NumAggregateInputs = TypeIndex;
628 Group.InputTypesSet = true;
629 }
630
631 Region.NumExtractedInputs = OriginalIndex;
632}
633
634/// Create a mapping of the output arguments for the \p Region to the output
635/// arguments of the overall outlined function.
636///
637/// \param [in,out] Region - The region of code to be analyzed.
638/// \param [in] Outputs - The values found by the code extractor.
639static void
640findExtractedOutputToOverallOutputMapping(OutlinableRegion &Region,
641 ArrayRef<Value *> Outputs) {
642 OutlinableGroup &Group = *Region.Parent;
643 IRSimilarityCandidate &C = *Region.Candidate;
644
645 // This counts the argument number in the extracted function.
646 unsigned OriginalIndex = Region.NumExtractedInputs;
647
648 // This counts the argument number in the overall function.
649 unsigned TypeIndex = Group.NumAggregateInputs;
650 bool TypeFound;
651 DenseSet<unsigned> AggArgsUsed;
652
653 // Iterate over the output types and identify if there is an aggregate pointer
654 // type whose base type matches the current output type. If there is, we mark
655 // that we will use this output register for this value. If not we add another
656 // type to the overall argument type list. We also store the GVNs used for
657 // stores to identify which values will need to be moved into an special
658 // block that holds the stores to the output registers.
659 for (Value *Output : Outputs) {
660 TypeFound = false;
661 // We can do this since it is a result value, and will have a number
662 // that is necessarily the same. BUT if in the future, the instructions
663 // do not have to be in same order, but are functionally the same, we will
664 // have to use a different scheme, as one-to-one correspondence is not
665 // guaranteed.
666 unsigned GlobalValue = C.getGVN(Output).getValue();
667 unsigned ArgumentSize = Group.ArgumentTypes.size();
668
669 for (unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {
670 if (Group.ArgumentTypes[Jdx] != PointerType::getUnqual(Output->getType()))
671 continue;
672
673 if (AggArgsUsed.contains(Jdx))
674 continue;
675
676 TypeFound = true;
677 AggArgsUsed.insert(Jdx);
678 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, Jdx));
679 Region.AggArgToExtracted.insert(std::make_pair(Jdx, OriginalIndex));
680 Region.GVNStores.push_back(GlobalValue);
681 break;
682 }
683
684 // We were unable to find an unused type in the output type set that matches
685 // the output, so we add a pointer type to the argument types of the overall
686 // function to handle this output and create a mapping to it.
687 if (!TypeFound) {
688 Group.ArgumentTypes.push_back(PointerType::getUnqual(Output->getType()));
689 AggArgsUsed.insert(Group.ArgumentTypes.size() - 1);
690 Region.ExtractedArgToAgg.insert(
691 std::make_pair(OriginalIndex, Group.ArgumentTypes.size() - 1));
692 Region.AggArgToExtracted.insert(
693 std::make_pair(Group.ArgumentTypes.size() - 1, OriginalIndex));
694 Region.GVNStores.push_back(GlobalValue);
695 }
696
697 stable_sort(Region.GVNStores);
698 OriginalIndex++;
699 TypeIndex++;
700 }
701}
702
703void IROutliner::findAddInputsOutputs(Module &M, OutlinableRegion &Region,
704 DenseSet<unsigned> &NotSame) {
705 std::vector<unsigned> Inputs;
706 SetVector<Value *> ArgInputs, Outputs;
707
708 getCodeExtractorArguments(Region, Inputs, NotSame, OutputMappings, ArgInputs,
709 Outputs);
710
711 if (Region.IgnoreRegion)
712 return;
713
714 // Map the inputs found by the CodeExtractor to the arguments found for
715 // the overall function.
716 findExtractedInputToOverallInputMapping(Region, Inputs, ArgInputs);
717
718 // Map the outputs found by the CodeExtractor to the arguments found for
719 // the overall function.
720 findExtractedOutputToOverallOutputMapping(Region, Outputs.getArrayRef());
721}
722
723/// Replace the extracted function in the Region with a call to the overall
724/// function constructed from the deduplicated similar regions, replacing and
725/// remapping the values passed to the extracted function as arguments to the
726/// new arguments of the overall function.
727///
728/// \param [in] M - The module to outline from.
729/// \param [in] Region - The regions of extracted code to be replaced with a new
730/// function.
731/// \returns a call instruction with the replaced function.
732CallInst *replaceCalledFunction(Module &M, OutlinableRegion &Region) {
733 std::vector<Value *> NewCallArgs;
734 DenseMap<unsigned, unsigned>::iterator ArgPair;
735
736 OutlinableGroup &Group = *Region.Parent;
737 CallInst *Call = Region.Call;
738 assert(Call && "Call to replace is nullptr?")((Call && "Call to replace is nullptr?") ? static_cast
<void> (0) : __assert_fail ("Call && \"Call to replace is nullptr?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 738, __PRETTY_FUNCTION__))
;
739 Function *AggFunc = Group.OutlinedFunction;
740 assert(AggFunc && "Function to replace with is nullptr?")((AggFunc && "Function to replace with is nullptr?") ?
static_cast<void> (0) : __assert_fail ("AggFunc && \"Function to replace with is nullptr?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 740, __PRETTY_FUNCTION__))
;
741
742 // If the arguments are the same size, there are not values that need to be
743 // made argument, or different output registers to handle. We can simply
744 // replace the called function in this case.
745 if (AggFunc->arg_size() == Call->arg_size()) {
746 LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replace call to " <<
*Call << " with call to " << *AggFunc << " with same number of arguments\n"
; } } while (false)
747 << *AggFunc << " with same number of arguments\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replace call to " <<
*Call << " with call to " << *AggFunc << " with same number of arguments\n"
; } } while (false)
;
748 Call->setCalledFunction(AggFunc);
749 return Call;
750 }
751
752 // We have a different number of arguments than the new function, so
753 // we need to use our previously mappings off extracted argument to overall
754 // function argument, and constants to overall function argument to create the
755 // new argument list.
756 for (unsigned AggArgIdx = 0; AggArgIdx < AggFunc->arg_size(); AggArgIdx++) {
757
758 if (AggArgIdx == AggFunc->arg_size() - 1 &&
759 Group.OutputGVNCombinations.size() > 1) {
760 // If we are on the last argument, and we need to differentiate between
761 // output blocks, add an integer to the argument list to determine
762 // what block to take
763 LLVM_DEBUG(dbgs() << "Set switch block argument to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Set switch block argument to "
<< Region.OutputBlockNum << "\n"; } } while (false
)
764 << Region.OutputBlockNum << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Set switch block argument to "
<< Region.OutputBlockNum << "\n"; } } while (false
)
;
765 NewCallArgs.push_back(ConstantInt::get(Type::getInt32Ty(M.getContext()),
766 Region.OutputBlockNum));
767 continue;
768 }
769
770 ArgPair = Region.AggArgToExtracted.find(AggArgIdx);
771 if (ArgPair != Region.AggArgToExtracted.end()) {
772 Value *ArgumentValue = Call->getArgOperand(ArgPair->second);
773 // If we found the mapping from the extracted function to the overall
774 // function, we simply add it to the argument list. We use the same
775 // value, it just needs to honor the new order of arguments.
776 LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Setting argument " <<
AggArgIdx << " to value " << *ArgumentValue <<
"\n"; } } while (false)
777 << *ArgumentValue << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Setting argument " <<
AggArgIdx << " to value " << *ArgumentValue <<
"\n"; } } while (false)
;
778 NewCallArgs.push_back(ArgumentValue);
779 continue;
780 }
781
782 // If it is a constant, we simply add it to the argument list as a value.
783 if (Region.AggArgToConstant.find(AggArgIdx) !=
784 Region.AggArgToConstant.end()) {
785 Constant *CST = Region.AggArgToConstant.find(AggArgIdx)->second;
786 LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Setting argument " <<
AggArgIdx << " to value " << *CST << "\n";
} } while (false)
787 << *CST << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Setting argument " <<
AggArgIdx << " to value " << *CST << "\n";
} } while (false)
;
788 NewCallArgs.push_back(CST);
789 continue;
790 }
791
792 // Add a nullptr value if the argument is not found in the extracted
793 // function. If we cannot find a value, it means it is not in use
794 // for the region, so we should not pass anything to it.
795 LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to nullptr\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Setting argument " <<
AggArgIdx << " to nullptr\n"; } } while (false)
;
796 NewCallArgs.push_back(ConstantPointerNull::get(
797 static_cast<PointerType *>(AggFunc->getArg(AggArgIdx)->getType())));
798 }
799
800 LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replace call to " <<
*Call << " with call to " << *AggFunc << " with new set of arguments\n"
; } } while (false)
801 << *AggFunc << " with new set of arguments\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replace call to " <<
*Call << " with call to " << *AggFunc << " with new set of arguments\n"
; } } while (false)
;
802 // Create the new call instruction and erase the old one.
803 Call = CallInst::Create(AggFunc->getFunctionType(), AggFunc, NewCallArgs, "",
804 Call);
805
806 // It is possible that the call to the outlined function is either the first
807 // instruction is in the new block, the last instruction, or both. If either
808 // of these is the case, we need to make sure that we replace the instruction
809 // in the IRInstructionData struct with the new call.
810 CallInst *OldCall = Region.Call;
811 if (Region.NewFront->Inst == OldCall)
812 Region.NewFront->Inst = Call;
813 if (Region.NewBack->Inst == OldCall)
814 Region.NewBack->Inst = Call;
815
816 // Transfer any debug information.
817 Call->setDebugLoc(Region.Call->getDebugLoc());
818
819 // Remove the old instruction.
820 OldCall->eraseFromParent();
821 Region.Call = Call;
822
823 // Make sure that the argument in the new function has the SwiftError
824 // argument.
825 if (Group.SwiftErrorArgument.hasValue())
826 Call->addParamAttr(Group.SwiftErrorArgument.getValue(),
827 Attribute::SwiftError);
828
829 return Call;
830}
831
832// Within an extracted function, replace the argument uses of the extracted
833// region with the arguments of the function for an OutlinableGroup.
834//
835/// \param [in] Region - The region of extracted code to be changed.
836/// \param [in,out] OutputBB - The BasicBlock for the output stores for this
837/// region.
838static void replaceArgumentUses(OutlinableRegion &Region,
839 BasicBlock *OutputBB) {
840 OutlinableGroup &Group = *Region.Parent;
841 assert(Region.ExtractedFunction && "Region has no extracted function?")((Region.ExtractedFunction && "Region has no extracted function?"
) ? static_cast<void> (0) : __assert_fail ("Region.ExtractedFunction && \"Region has no extracted function?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 841, __PRETTY_FUNCTION__))
;
842
843 for (unsigned ArgIdx = 0; ArgIdx < Region.ExtractedFunction->arg_size();
844 ArgIdx++) {
845 assert(Region.ExtractedArgToAgg.find(ArgIdx) !=((Region.ExtractedArgToAgg.find(ArgIdx) != Region.ExtractedArgToAgg
.end() && "No mapping from extracted to outlined?") ?
static_cast<void> (0) : __assert_fail ("Region.ExtractedArgToAgg.find(ArgIdx) != Region.ExtractedArgToAgg.end() && \"No mapping from extracted to outlined?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 847, __PRETTY_FUNCTION__))
846 Region.ExtractedArgToAgg.end() &&((Region.ExtractedArgToAgg.find(ArgIdx) != Region.ExtractedArgToAgg
.end() && "No mapping from extracted to outlined?") ?
static_cast<void> (0) : __assert_fail ("Region.ExtractedArgToAgg.find(ArgIdx) != Region.ExtractedArgToAgg.end() && \"No mapping from extracted to outlined?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 847, __PRETTY_FUNCTION__))
847 "No mapping from extracted to outlined?")((Region.ExtractedArgToAgg.find(ArgIdx) != Region.ExtractedArgToAgg
.end() && "No mapping from extracted to outlined?") ?
static_cast<void> (0) : __assert_fail ("Region.ExtractedArgToAgg.find(ArgIdx) != Region.ExtractedArgToAgg.end() && \"No mapping from extracted to outlined?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 847, __PRETTY_FUNCTION__))
;
848 unsigned AggArgIdx = Region.ExtractedArgToAgg.find(ArgIdx)->second;
849 Argument *AggArg = Group.OutlinedFunction->getArg(AggArgIdx);
850 Argument *Arg = Region.ExtractedFunction->getArg(ArgIdx);
851 // The argument is an input, so we can simply replace it with the overall
852 // argument value
853 if (ArgIdx < Region.NumExtractedInputs) {
854 LLVM_DEBUG(dbgs() << "Replacing uses of input " << *Arg << " in function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of input " <<
*Arg << " in function " << *Region.ExtractedFunction
<< " with " << *AggArg << " in function " <<
*Group.OutlinedFunction << "\n"; } } while (false)
855 << *Region.ExtractedFunction << " with " << *AggArgdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of input " <<
*Arg << " in function " << *Region.ExtractedFunction
<< " with " << *AggArg << " in function " <<
*Group.OutlinedFunction << "\n"; } } while (false)
856 << " in function " << *Group.OutlinedFunction << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of input " <<
*Arg << " in function " << *Region.ExtractedFunction
<< " with " << *AggArg << " in function " <<
*Group.OutlinedFunction << "\n"; } } while (false)
;
857 Arg->replaceAllUsesWith(AggArg);
858 continue;
859 }
860
861 // If we are replacing an output, we place the store value in its own
862 // block inside the overall function before replacing the use of the output
863 // in the function.
864 assert(Arg->hasOneUse() && "Output argument can only have one use")((Arg->hasOneUse() && "Output argument can only have one use"
) ? static_cast<void> (0) : __assert_fail ("Arg->hasOneUse() && \"Output argument can only have one use\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 864, __PRETTY_FUNCTION__))
;
865 User *InstAsUser = Arg->user_back();
866 assert(InstAsUser && "User is nullptr!")((InstAsUser && "User is nullptr!") ? static_cast<
void> (0) : __assert_fail ("InstAsUser && \"User is nullptr!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 866, __PRETTY_FUNCTION__))
;
867
868 Instruction *I = cast<Instruction>(InstAsUser);
869 I->setDebugLoc(DebugLoc());
870 LLVM_DEBUG(dbgs() << "Move store for instruction " << *I << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move store for instruction "
<< *I << " to " << *OutputBB << "\n"
; } } while (false)
871 << *OutputBB << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move store for instruction "
<< *I << " to " << *OutputBB << "\n"
; } } while (false)
;
872
873 I->moveBefore(*OutputBB, OutputBB->end());
874
875 LLVM_DEBUG(dbgs() << "Replacing uses of output " << *Arg << " in function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of output "
<< *Arg << " in function " << *Region.ExtractedFunction
<< " with " << *AggArg << " in function " <<
*Group.OutlinedFunction << "\n"; } } while (false)
876 << *Region.ExtractedFunction << " with " << *AggArgdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of output "
<< *Arg << " in function " << *Region.ExtractedFunction
<< " with " << *AggArg << " in function " <<
*Group.OutlinedFunction << "\n"; } } while (false)
877 << " in function " << *Group.OutlinedFunction << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of output "
<< *Arg << " in function " << *Region.ExtractedFunction
<< " with " << *AggArg << " in function " <<
*Group.OutlinedFunction << "\n"; } } while (false)
;
878 Arg->replaceAllUsesWith(AggArg);
879 }
880}
881
882/// Within an extracted function, replace the constants that need to be lifted
883/// into arguments with the actual argument.
884///
885/// \param Region [in] - The region of extracted code to be changed.
886void replaceConstants(OutlinableRegion &Region) {
887 OutlinableGroup &Group = *Region.Parent;
888 // Iterate over the constants that need to be elevated into arguments
889 for (std::pair<unsigned, Constant *> &Const : Region.AggArgToConstant) {
890 unsigned AggArgIdx = Const.first;
891 Function *OutlinedFunction = Group.OutlinedFunction;
892 assert(OutlinedFunction && "Overall Function is not defined?")((OutlinedFunction && "Overall Function is not defined?"
) ? static_cast<void> (0) : __assert_fail ("OutlinedFunction && \"Overall Function is not defined?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 892, __PRETTY_FUNCTION__))
;
893 Constant *CST = Const.second;
894 Argument *Arg = Group.OutlinedFunction->getArg(AggArgIdx);
895 // Identify the argument it will be elevated to, and replace instances of
896 // that constant in the function.
897
898 // TODO: If in the future constants do not have one global value number,
899 // i.e. a constant 1 could be mapped to several values, this check will
900 // have to be more strict. It cannot be using only replaceUsesWithIf.
901
902 LLVM_DEBUG(dbgs() << "Replacing uses of constant " << *CSTdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of constant "
<< *CST << " in function " << *OutlinedFunction
<< " with " << *Arg << "\n"; } } while (false
)
903 << " in function " << *OutlinedFunction << " with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of constant "
<< *CST << " in function " << *OutlinedFunction
<< " with " << *Arg << "\n"; } } while (false
)
904 << *Arg << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of constant "
<< *CST << " in function " << *OutlinedFunction
<< " with " << *Arg << "\n"; } } while (false
)
;
905 CST->replaceUsesWithIf(Arg, [OutlinedFunction](Use &U) {
906 if (Instruction *I = dyn_cast<Instruction>(U.getUser()))
907 return I->getFunction() == OutlinedFunction;
908 return false;
909 });
910 }
911}
912
913/// For the given function, find all the nondebug or lifetime instructions,
914/// and return them as a vector. Exclude any blocks in \p ExludeBlocks.
915///
916/// \param [in] F - The function we collect the instructions from.
917/// \param [in] ExcludeBlocks - BasicBlocks to ignore.
918/// \returns the list of instructions extracted.
919static std::vector<Instruction *>
920collectRelevantInstructions(Function &F,
921 DenseSet<BasicBlock *> &ExcludeBlocks) {
922 std::vector<Instruction *> RelevantInstructions;
923
924 for (BasicBlock &BB : F) {
925 if (ExcludeBlocks.contains(&BB))
926 continue;
927
928 for (Instruction &Inst : BB) {
929 if (Inst.isLifetimeStartOrEnd())
930 continue;
931 if (isa<DbgInfoIntrinsic>(Inst))
932 continue;
933
934 RelevantInstructions.push_back(&Inst);
935 }
936 }
937
938 return RelevantInstructions;
939}
940
941/// It is possible that there is a basic block that already performs the same
942/// stores. This returns a duplicate block, if it exists
943///
944/// \param OutputBB [in] the block we are looking for a duplicate of.
945/// \param OutputStoreBBs [in] The existing output blocks.
946/// \returns an optional value with the number output block if there is a match.
947Optional<unsigned>
948findDuplicateOutputBlock(BasicBlock *OutputBB,
949 ArrayRef<BasicBlock *> OutputStoreBBs) {
950
951 bool WrongInst = false;
952 bool WrongSize = false;
953 unsigned MatchingNum = 0;
954 for (BasicBlock *CompBB : OutputStoreBBs) {
955 WrongInst = false;
956 if (CompBB->size() - 1 != OutputBB->size()) {
957 WrongSize = true;
Value stored to 'WrongSize' is never read
958 MatchingNum++;
959 continue;
960 }
961
962 WrongSize = false;
963 BasicBlock::iterator NIt = OutputBB->begin();
964 for (Instruction &I : *CompBB) {
965 if (isa<BranchInst>(&I))
966 continue;
967
968 if (!I.isIdenticalTo(&(*NIt))) {
969 WrongInst = true;
970 break;
971 }
972
973 NIt++;
974 }
975 if (!WrongInst && !WrongSize)
976 return MatchingNum;
977
978 MatchingNum++;
979 }
980
981 return None;
982}
983
984/// For the outlined section, move needed the StoreInsts for the output
985/// registers into their own block. Then, determine if there is a duplicate
986/// output block already created.
987///
988/// \param [in] OG - The OutlinableGroup of regions to be outlined.
989/// \param [in] Region - The OutlinableRegion that is being analyzed.
990/// \param [in,out] OutputBB - the block that stores for this region will be
991/// placed in.
992/// \param [in] EndBB - the final block of the extracted function.
993/// \param [in] OutputMappings - OutputMappings the mapping of values that have
994/// been replaced by a new output value.
995/// \param [in,out] OutputStoreBBs - The existing output blocks.
996static void
997alignOutputBlockWithAggFunc(OutlinableGroup &OG, OutlinableRegion &Region,
998 BasicBlock *OutputBB, BasicBlock *EndBB,
999 const DenseMap<Value *, Value *> &OutputMappings,
1000 std::vector<BasicBlock *> &OutputStoreBBs) {
1001 DenseSet<unsigned> ValuesToFind(Region.GVNStores.begin(),
1002 Region.GVNStores.end());
1003
1004 // We iterate over the instructions in the extracted function, and find the
1005 // global value number of the instructions. If we find a value that should
1006 // be contained in a store, we replace the uses of the value with the value
1007 // from the overall function, so that the store is storing the correct
1008 // value from the overall function.
1009 DenseSet<BasicBlock *> ExcludeBBs(OutputStoreBBs.begin(),
1010 OutputStoreBBs.end());
1011 ExcludeBBs.insert(OutputBB);
1012 std::vector<Instruction *> ExtractedFunctionInsts =
1013 collectRelevantInstructions(*(Region.ExtractedFunction), ExcludeBBs);
1014 std::vector<Instruction *> OverallFunctionInsts =
1015 collectRelevantInstructions(*OG.OutlinedFunction, ExcludeBBs);
1016
1017 assert(ExtractedFunctionInsts.size() == OverallFunctionInsts.size() &&((ExtractedFunctionInsts.size() == OverallFunctionInsts.size(
) && "Number of relevant instructions not equal!") ? static_cast
<void> (0) : __assert_fail ("ExtractedFunctionInsts.size() == OverallFunctionInsts.size() && \"Number of relevant instructions not equal!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1018, __PRETTY_FUNCTION__))
1018 "Number of relevant instructions not equal!")((ExtractedFunctionInsts.size() == OverallFunctionInsts.size(
) && "Number of relevant instructions not equal!") ? static_cast
<void> (0) : __assert_fail ("ExtractedFunctionInsts.size() == OverallFunctionInsts.size() && \"Number of relevant instructions not equal!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1018, __PRETTY_FUNCTION__))
;
1019
1020 unsigned NumInstructions = ExtractedFunctionInsts.size();
1021 for (unsigned Idx = 0; Idx < NumInstructions; Idx++) {
1022 Value *V = ExtractedFunctionInsts[Idx];
1023
1024 if (OutputMappings.find(V) != OutputMappings.end())
1025 V = OutputMappings.find(V)->second;
1026 Optional<unsigned> GVN = Region.Candidate->getGVN(V);
1027
1028 // If we have found one of the stored values for output, replace the value
1029 // with the corresponding one from the overall function.
1030 if (GVN.hasValue() && ValuesToFind.erase(GVN.getValue())) {
1031 V->replaceAllUsesWith(OverallFunctionInsts[Idx]);
1032 if (ValuesToFind.size() == 0)
1033 break;
1034 }
1035
1036 if (ValuesToFind.size() == 0)
1037 break;
1038 }
1039
1040 assert(ValuesToFind.size() == 0 && "Not all store values were handled!")((ValuesToFind.size() == 0 && "Not all store values were handled!"
) ? static_cast<void> (0) : __assert_fail ("ValuesToFind.size() == 0 && \"Not all store values were handled!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1040, __PRETTY_FUNCTION__))
;
1041
1042 // If the size of the block is 0, then there are no stores, and we do not
1043 // need to save this block.
1044 if (OutputBB->size() == 0) {
1045 Region.OutputBlockNum = -1;
1046 OutputBB->eraseFromParent();
1047 return;
1048 }
1049
1050 // Determine is there is a duplicate block.
1051 Optional<unsigned> MatchingBB =
1052 findDuplicateOutputBlock(OutputBB, OutputStoreBBs);
1053
1054 // If there is, we remove the new output block. If it does not,
1055 // we add it to our list of output blocks.
1056 if (MatchingBB.hasValue()) {
1057 LLVM_DEBUG(dbgs() << "Set output block for region in function"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Set output block for region in function"
<< Region.ExtractedFunction << " to " << MatchingBB
.getValue(); } } while (false)
1058 << Region.ExtractedFunction << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Set output block for region in function"
<< Region.ExtractedFunction << " to " << MatchingBB
.getValue(); } } while (false)
1059 << MatchingBB.getValue())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Set output block for region in function"
<< Region.ExtractedFunction << " to " << MatchingBB
.getValue(); } } while (false)
;
1060
1061 Region.OutputBlockNum = MatchingBB.getValue();
1062 OutputBB->eraseFromParent();
1063 return;
1064 }
1065
1066 Region.OutputBlockNum = OutputStoreBBs.size();
1067
1068 LLVM_DEBUG(dbgs() << "Create output block for region in"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Create output block for region in"
<< Region.ExtractedFunction << " to " << *
OutputBB; } } while (false)
1069 << Region.ExtractedFunction << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Create output block for region in"
<< Region.ExtractedFunction << " to " << *
OutputBB; } } while (false)
1070 << *OutputBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Create output block for region in"
<< Region.ExtractedFunction << " to " << *
OutputBB; } } while (false)
;
1071 OutputStoreBBs.push_back(OutputBB);
1072 BranchInst::Create(EndBB, OutputBB);
1073}
1074
1075/// Create the switch statement for outlined function to differentiate between
1076/// all the output blocks.
1077///
1078/// For the outlined section, determine if an outlined block already exists that
1079/// matches the needed stores for the extracted section.
1080/// \param [in] M - The module we are outlining from.
1081/// \param [in] OG - The group of regions to be outlined.
1082/// \param [in] EndBB - The final block of the extracted function.
1083/// \param [in,out] OutputStoreBBs - The existing output blocks.
1084void createSwitchStatement(Module &M, OutlinableGroup &OG, BasicBlock *EndBB,
1085 ArrayRef<BasicBlock *> OutputStoreBBs) {
1086 // We only need the switch statement if there is more than one store
1087 // combination.
1088 if (OG.OutputGVNCombinations.size() > 1) {
1089 Function *AggFunc = OG.OutlinedFunction;
1090 // Create a final block
1091 BasicBlock *ReturnBlock =
1092 BasicBlock::Create(M.getContext(), "final_block", AggFunc);
1093 Instruction *Term = EndBB->getTerminator();
1094 Term->moveBefore(*ReturnBlock, ReturnBlock->end());
1095 // Put the switch statement in the old end basic block for the function with
1096 // a fall through to the new return block
1097 LLVM_DEBUG(dbgs() << "Create switch statement in " << *AggFunc << " for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Create switch statement in "
<< *AggFunc << " for " << OutputStoreBBs.size
() << "\n"; } } while (false)
1098 << OutputStoreBBs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Create switch statement in "
<< *AggFunc << " for " << OutputStoreBBs.size
() << "\n"; } } while (false)
;
1099 SwitchInst *SwitchI =
1100 SwitchInst::Create(AggFunc->getArg(AggFunc->arg_size() - 1),
1101 ReturnBlock, OutputStoreBBs.size(), EndBB);
1102
1103 unsigned Idx = 0;
1104 for (BasicBlock *BB : OutputStoreBBs) {
1105 SwitchI->addCase(ConstantInt::get(Type::getInt32Ty(M.getContext()), Idx),
1106 BB);
1107 Term = BB->getTerminator();
1108 Term->setSuccessor(0, ReturnBlock);
1109 Idx++;
1110 }
1111 return;
1112 }
1113
1114 // If there needs to be stores, move them from the output block to the end
1115 // block to save on branching instructions.
1116 if (OutputStoreBBs.size() == 1) {
1117 LLVM_DEBUG(dbgs() << "Move store instructions to the end block in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move store instructions to the end block in "
<< *OG.OutlinedFunction << "\n"; } } while (false
)
1118 << *OG.OutlinedFunction << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move store instructions to the end block in "
<< *OG.OutlinedFunction << "\n"; } } while (false
)
;
1119 BasicBlock *OutputBlock = OutputStoreBBs[0];
1120 Instruction *Term = OutputBlock->getTerminator();
1121 Term->eraseFromParent();
1122 Term = EndBB->getTerminator();
1123 moveBBContents(*OutputBlock, *EndBB);
1124 Term->moveBefore(*EndBB, EndBB->end());
1125 OutputBlock->eraseFromParent();
1126 }
1127}
1128
1129/// Fill the new function that will serve as the replacement function for all of
1130/// the extracted regions of a certain structure from the first region in the
1131/// list of regions. Replace this first region's extracted function with the
1132/// new overall function.
1133///
1134/// \param [in] M - The module we are outlining from.
1135/// \param [in] CurrentGroup - The group of regions to be outlined.
1136/// \param [in,out] OutputStoreBBs - The output blocks for each different
1137/// set of stores needed for the different functions.
1138/// \param [in,out] FuncsToRemove - Extracted functions to erase from module
1139/// once outlining is complete.
1140static void fillOverallFunction(Module &M, OutlinableGroup &CurrentGroup,
1141 std::vector<BasicBlock *> &OutputStoreBBs,
1142 std::vector<Function *> &FuncsToRemove) {
1143 OutlinableRegion *CurrentOS = CurrentGroup.Regions[0];
1144
1145 // Move first extracted function's instructions into new function.
1146 LLVM_DEBUG(dbgs() << "Move instructions from "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move instructions from " <<
*CurrentOS->ExtractedFunction << " to instruction "
<< *CurrentGroup.OutlinedFunction << "\n"; } } while
(false)
1147 << *CurrentOS->ExtractedFunction << " to instruction "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move instructions from " <<
*CurrentOS->ExtractedFunction << " to instruction "
<< *CurrentGroup.OutlinedFunction << "\n"; } } while
(false)
1148 << *CurrentGroup.OutlinedFunction << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move instructions from " <<
*CurrentOS->ExtractedFunction << " to instruction "
<< *CurrentGroup.OutlinedFunction << "\n"; } } while
(false)
;
1149
1150 CurrentGroup.EndBB = moveFunctionData(*CurrentOS->ExtractedFunction,
1151 *CurrentGroup.OutlinedFunction);
1152
1153 // Transfer the attributes from the function to the new function.
1154 for (Attribute A :
1155 CurrentOS->ExtractedFunction->getAttributes().getFnAttributes())
1156 CurrentGroup.OutlinedFunction->addFnAttr(A);
1157
1158 // Create an output block for the first extracted function.
1159 BasicBlock *NewBB = BasicBlock::Create(
1160 M.getContext(), Twine("output_block_") + Twine(static_cast<unsigned>(0)),
1161 CurrentGroup.OutlinedFunction);
1162 CurrentOS->OutputBlockNum = 0;
1163
1164 replaceArgumentUses(*CurrentOS, NewBB);
1165 replaceConstants(*CurrentOS);
1166
1167 // If the new basic block has no new stores, we can erase it from the module.
1168 // It it does, we create a branch instruction to the last basic block from the
1169 // new one.
1170 if (NewBB->size() == 0) {
1171 CurrentOS->OutputBlockNum = -1;
1172 NewBB->eraseFromParent();
1173 } else {
1174 BranchInst::Create(CurrentGroup.EndBB, NewBB);
1175 OutputStoreBBs.push_back(NewBB);
1176 }
1177
1178 // Replace the call to the extracted function with the outlined function.
1179 CurrentOS->Call = replaceCalledFunction(M, *CurrentOS);
1180
1181 // We only delete the extracted functions at the end since we may need to
1182 // reference instructions contained in them for mapping purposes.
1183 FuncsToRemove.push_back(CurrentOS->ExtractedFunction);
1184}
1185
1186void IROutliner::deduplicateExtractedSections(
1187 Module &M, OutlinableGroup &CurrentGroup,
1188 std::vector<Function *> &FuncsToRemove, unsigned &OutlinedFunctionNum) {
1189 createFunction(M, CurrentGroup, OutlinedFunctionNum);
1190
1191 std::vector<BasicBlock *> OutputStoreBBs;
1192
1193 OutlinableRegion *CurrentOS;
1194
1195 fillOverallFunction(M, CurrentGroup, OutputStoreBBs, FuncsToRemove);
1196
1197 for (unsigned Idx = 1; Idx < CurrentGroup.Regions.size(); Idx++) {
1198 CurrentOS = CurrentGroup.Regions[Idx];
1199 AttributeFuncs::mergeAttributesForOutlining(*CurrentGroup.OutlinedFunction,
1200 *CurrentOS->ExtractedFunction);
1201
1202 // Create a new BasicBlock to hold the needed store instructions.
1203 BasicBlock *NewBB = BasicBlock::Create(
1204 M.getContext(), "output_block_" + std::to_string(Idx),
1205 CurrentGroup.OutlinedFunction);
1206 replaceArgumentUses(*CurrentOS, NewBB);
1207
1208 alignOutputBlockWithAggFunc(CurrentGroup, *CurrentOS, NewBB,
1209 CurrentGroup.EndBB, OutputMappings,
1210 OutputStoreBBs);
1211
1212 CurrentOS->Call = replaceCalledFunction(M, *CurrentOS);
1213 FuncsToRemove.push_back(CurrentOS->ExtractedFunction);
1214 }
1215
1216 // Create a switch statement to handle the different output schemes.
1217 createSwitchStatement(M, CurrentGroup, CurrentGroup.EndBB, OutputStoreBBs);
1218
1219 OutlinedFunctionNum++;
1220}
1221
1222void IROutliner::pruneIncompatibleRegions(
1223 std::vector<IRSimilarityCandidate> &CandidateVec,
1224 OutlinableGroup &CurrentGroup) {
1225 bool PreviouslyOutlined;
1226
1227 // Sort from beginning to end, so the IRSimilarityCandidates are in order.
1228 stable_sort(CandidateVec, [](const IRSimilarityCandidate &LHS,
1229 const IRSimilarityCandidate &RHS) {
1230 return LHS.getStartIdx() < RHS.getStartIdx();
1231 });
1232
1233 unsigned CurrentEndIdx = 0;
1234 for (IRSimilarityCandidate &IRSC : CandidateVec) {
1235 PreviouslyOutlined = false;
1236 unsigned StartIdx = IRSC.getStartIdx();
1237 unsigned EndIdx = IRSC.getEndIdx();
1238
1239 for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
1240 if (Outlined.contains(Idx)) {
1241 PreviouslyOutlined = true;
1242 break;
1243 }
1244
1245 if (PreviouslyOutlined)
1246 continue;
1247
1248 // TODO: If in the future we can outline across BasicBlocks, we will need to
1249 // check all BasicBlocks contained in the region.
1250 if (IRSC.getStartBB()->hasAddressTaken())
1251 continue;
1252
1253 if (IRSC.front()->Inst->getFunction()->hasLinkOnceODRLinkage() &&
1254 !OutlineFromLinkODRs)
1255 continue;
1256
1257 // Greedily prune out any regions that will overlap with already chosen
1258 // regions.
1259 if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
1260 continue;
1261
1262 bool BadInst = any_of(IRSC, [this](IRInstructionData &ID) {
1263 // We check if there is a discrepancy between the InstructionDataList
1264 // and the actual next instruction in the module. If there is, it means
1265 // that an extra instruction was added, likely by the CodeExtractor.
1266
1267 // Since we do not have any similarity data about this particular
1268 // instruction, we cannot confidently outline it, and must discard this
1269 // candidate.
1270 if (std::next(ID.getIterator())->Inst !=
1271 ID.Inst->getNextNonDebugInstruction())
1272 return true;
1273 return !this->InstructionClassifier.visit(ID.Inst);
1274 });
1275
1276 if (BadInst)
1277 continue;
1278
1279 OutlinableRegion *OS = new (RegionAllocator.Allocate())
1280 OutlinableRegion(IRSC, CurrentGroup);
1281 CurrentGroup.Regions.push_back(OS);
1282
1283 CurrentEndIdx = EndIdx;
1284 }
1285}
1286
1287InstructionCost
1288IROutliner::findBenefitFromAllRegions(OutlinableGroup &CurrentGroup) {
1289 InstructionCost RegionBenefit = 0;
1290 for (OutlinableRegion *Region : CurrentGroup.Regions) {
1291 TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
1292 // We add the number of instructions in the region to the benefit as an
1293 // estimate as to how much will be removed.
1294 RegionBenefit += Region->getBenefit(TTI);
1295 LLVM_DEBUG(dbgs() << "Adding: " << RegionBenefitdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << RegionBenefit
<< " saved instructions to overfall benefit.\n"; } } while
(false)
1296 << " saved instructions to overfall benefit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << RegionBenefit
<< " saved instructions to overfall benefit.\n"; } } while
(false)
;
1297 }
1298
1299 return RegionBenefit;
1300}
1301
1302InstructionCost
1303IROutliner::findCostOutputReloads(OutlinableGroup &CurrentGroup) {
1304 InstructionCost OverallCost = 0;
1305 for (OutlinableRegion *Region : CurrentGroup.Regions) {
1306 TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
1307
1308 // Each output incurs a load after the call, so we add that to the cost.
1309 for (unsigned OutputGVN : Region->GVNStores) {
1310 Optional<Value *> OV = Region->Candidate->fromGVN(OutputGVN);
1311 assert(OV.hasValue() && "Could not find value for GVN?")((OV.hasValue() && "Could not find value for GVN?") ?
static_cast<void> (0) : __assert_fail ("OV.hasValue() && \"Could not find value for GVN?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1311, __PRETTY_FUNCTION__))
;
1312 Value *V = OV.getValue();
1313 InstructionCost LoadCost =
1314 TTI.getMemoryOpCost(Instruction::Load, V->getType(), Align(1), 0,
1315 TargetTransformInfo::TCK_CodeSize);
1316
1317 LLVM_DEBUG(dbgs() << "Adding: " << LoadCostdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << LoadCost
<< " instructions to cost for output of type " <<
*V->getType() << "\n"; } } while (false)
1318 << " instructions to cost for output of type "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << LoadCost
<< " instructions to cost for output of type " <<
*V->getType() << "\n"; } } while (false)
1319 << *V->getType() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << LoadCost
<< " instructions to cost for output of type " <<
*V->getType() << "\n"; } } while (false)
;
1320 OverallCost += LoadCost;
1321 }
1322 }
1323
1324 return OverallCost;
1325}
1326
1327/// Find the extra instructions needed to handle any output values for the
1328/// region.
1329///
1330/// \param [in] M - The Module to outline from.
1331/// \param [in] CurrentGroup - The collection of OutlinableRegions to analyze.
1332/// \param [in] TTI - The TargetTransformInfo used to collect information for
1333/// new instruction costs.
1334/// \returns the additional cost to handle the outputs.
1335static InstructionCost findCostForOutputBlocks(Module &M,
1336 OutlinableGroup &CurrentGroup,
1337 TargetTransformInfo &TTI) {
1338 InstructionCost OutputCost = 0;
1339
1340 for (const ArrayRef<unsigned> &OutputUse :
1341 CurrentGroup.OutputGVNCombinations) {
1342 IRSimilarityCandidate &Candidate = *CurrentGroup.Regions[0]->Candidate;
1343 for (unsigned GVN : OutputUse) {
1344 Optional<Value *> OV = Candidate.fromGVN(GVN);
1345 assert(OV.hasValue() && "Could not find value for GVN?")((OV.hasValue() && "Could not find value for GVN?") ?
static_cast<void> (0) : __assert_fail ("OV.hasValue() && \"Could not find value for GVN?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1345, __PRETTY_FUNCTION__))
;
1346 Value *V = OV.getValue();
1347 InstructionCost StoreCost =
1348 TTI.getMemoryOpCost(Instruction::Load, V->getType(), Align(1), 0,
1349 TargetTransformInfo::TCK_CodeSize);
1350
1351 // An instruction cost is added for each store set that needs to occur for
1352 // various output combinations inside the function, plus a branch to
1353 // return to the exit block.
1354 LLVM_DEBUG(dbgs() << "Adding: " << StoreCostdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << StoreCost
<< " instructions to cost for output of type " <<
*V->getType() << "\n"; } } while (false)
1355 << " instructions to cost for output of type "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << StoreCost
<< " instructions to cost for output of type " <<
*V->getType() << "\n"; } } while (false)
1356 << *V->getType() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << StoreCost
<< " instructions to cost for output of type " <<
*V->getType() << "\n"; } } while (false)
;
1357 OutputCost += StoreCost;
1358 }
1359
1360 InstructionCost BranchCost =
1361 TTI.getCFInstrCost(Instruction::Br, TargetTransformInfo::TCK_CodeSize);
1362 LLVM_DEBUG(dbgs() << "Adding " << BranchCost << " to the current cost for"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding " << BranchCost
<< " to the current cost for" << " a branch instruction\n"
; } } while (false)
1363 << " a branch instruction\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding " << BranchCost
<< " to the current cost for" << " a branch instruction\n"
; } } while (false)
;
1364 OutputCost += BranchCost;
1365 }
1366
1367 // If there is more than one output scheme, we must have a comparison and
1368 // branch for each different item in the switch statement.
1369 if (CurrentGroup.OutputGVNCombinations.size() > 1) {
1370 InstructionCost ComparisonCost = TTI.getCmpSelInstrCost(
1371 Instruction::ICmp, Type::getInt32Ty(M.getContext()),
1372 Type::getInt32Ty(M.getContext()), CmpInst::BAD_ICMP_PREDICATE,
1373 TargetTransformInfo::TCK_CodeSize);
1374 InstructionCost BranchCost =
1375 TTI.getCFInstrCost(Instruction::Br, TargetTransformInfo::TCK_CodeSize);
1376
1377 unsigned DifferentBlocks = CurrentGroup.OutputGVNCombinations.size();
1378 InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
1379
1380 LLVM_DEBUG(dbgs() << "Adding: " << TotalCostdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << TotalCost
<< " instructions for each switch case for each different"
<< " output path in a function\n"; } } while (false)
1381 << " instructions for each switch case for each different"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << TotalCost
<< " instructions for each switch case for each different"
<< " output path in a function\n"; } } while (false)
1382 << " output path in a function\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << TotalCost
<< " instructions for each switch case for each different"
<< " output path in a function\n"; } } while (false)
;
1383 OutputCost += TotalCost;
1384 }
1385
1386 return OutputCost;
1387}
1388
1389void IROutliner::findCostBenefit(Module &M, OutlinableGroup &CurrentGroup) {
1390 InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
1391 CurrentGroup.Benefit += RegionBenefit;
1392 LLVM_DEBUG(dbgs() << "Current Benefit: " << CurrentGroup.Benefit << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Benefit: " <<
CurrentGroup.Benefit << "\n"; } } while (false)
;
1393
1394 InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);
1395 CurrentGroup.Cost += OutputReloadCost;
1396 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1397
1398 InstructionCost AverageRegionBenefit =
1399 RegionBenefit / CurrentGroup.Regions.size();
1400 unsigned OverallArgumentNum = CurrentGroup.ArgumentTypes.size();
1401 unsigned NumRegions = CurrentGroup.Regions.size();
1402 TargetTransformInfo &TTI =
1403 getTTI(*CurrentGroup.Regions[0]->Candidate->getFunction());
1404
1405 // We add one region to the cost once, to account for the instructions added
1406 // inside of the newly created function.
1407 LLVM_DEBUG(dbgs() << "Adding: " << AverageRegionBenefitdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << AverageRegionBenefit
<< " instructions to cost for body of new function.\n"
; } } while (false)
1408 << " instructions to cost for body of new function.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << AverageRegionBenefit
<< " instructions to cost for body of new function.\n"
; } } while (false)
;
1409 CurrentGroup.Cost += AverageRegionBenefit;
1410 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1411
1412 // For each argument, we must add an instruction for loading the argument
1413 // out of the register and into a value inside of the newly outlined function.
1414 LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << OverallArgumentNum
<< " instructions to cost for each argument in the new"
<< " function.\n"; } } while (false)
1415 << " instructions to cost for each argument in the new"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << OverallArgumentNum
<< " instructions to cost for each argument in the new"
<< " function.\n"; } } while (false)
1416 << " function.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << OverallArgumentNum
<< " instructions to cost for each argument in the new"
<< " function.\n"; } } while (false)
;
1417 CurrentGroup.Cost +=
1418 OverallArgumentNum * TargetTransformInfo::TCC_Basic;
1419 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1420
1421 // Each argument needs to either be loaded into a register or onto the stack.
1422 // Some arguments will only be loaded into the stack once the argument
1423 // registers are filled.
1424 LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << OverallArgumentNum
<< " instructions to cost for each argument in the new"
<< " function " << NumRegions << " times for the "
<< "needed argument handling at the call site.\n"; } }
while (false)
1425 << " instructions to cost for each argument in the new"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << OverallArgumentNum
<< " instructions to cost for each argument in the new"
<< " function " << NumRegions << " times for the "
<< "needed argument handling at the call site.\n"; } }
while (false)
1426 << " function " << NumRegions << " times for the "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << OverallArgumentNum
<< " instructions to cost for each argument in the new"
<< " function " << NumRegions << " times for the "
<< "needed argument handling at the call site.\n"; } }
while (false)
1427 << "needed argument handling at the call site.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << OverallArgumentNum
<< " instructions to cost for each argument in the new"
<< " function " << NumRegions << " times for the "
<< "needed argument handling at the call site.\n"; } }
while (false)
;
1428 CurrentGroup.Cost +=
1429 2 * OverallArgumentNum * TargetTransformInfo::TCC_Basic * NumRegions;
1430 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1431
1432 CurrentGroup.Cost += findCostForOutputBlocks(M, CurrentGroup, TTI);
1433 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1434}
1435
1436void IROutliner::updateOutputMapping(OutlinableRegion &Region,
1437 ArrayRef<Value *> Outputs,
1438 LoadInst *LI) {
1439 // For and load instructions following the call
1440 Value *Operand = LI->getPointerOperand();
1441 Optional<unsigned> OutputIdx = None;
1442 // Find if the operand it is an output register.
1443 for (unsigned ArgIdx = Region.NumExtractedInputs;
1444 ArgIdx < Region.Call->arg_size(); ArgIdx++) {
1445 if (Operand == Region.Call->getArgOperand(ArgIdx)) {
1446 OutputIdx = ArgIdx - Region.NumExtractedInputs;
1447 break;
1448 }
1449 }
1450
1451 // If we found an output register, place a mapping of the new value
1452 // to the original in the mapping.
1453 if (!OutputIdx.hasValue())
1454 return;
1455
1456 if (OutputMappings.find(Outputs[OutputIdx.getValue()]) ==
1457 OutputMappings.end()) {
1458 LLVM_DEBUG(dbgs() << "Mapping extracted output " << *LI << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Mapping extracted output "
<< *LI << " to " << *Outputs[OutputIdx.getValue
()] << "\n"; } } while (false)
1459 << *Outputs[OutputIdx.getValue()] << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Mapping extracted output "
<< *LI << " to " << *Outputs[OutputIdx.getValue
()] << "\n"; } } while (false)
;
1460 OutputMappings.insert(std::make_pair(LI, Outputs[OutputIdx.getValue()]));
1461 } else {
1462 Value *Orig = OutputMappings.find(Outputs[OutputIdx.getValue()])->second;
1463 LLVM_DEBUG(dbgs() << "Mapping extracted output " << *Orig << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Mapping extracted output "
<< *Orig << " to " << *Outputs[OutputIdx.getValue
()] << "\n"; } } while (false)
1464 << *Outputs[OutputIdx.getValue()] << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Mapping extracted output "
<< *Orig << " to " << *Outputs[OutputIdx.getValue
()] << "\n"; } } while (false)
;
1465 OutputMappings.insert(std::make_pair(LI, Orig));
1466 }
1467}
1468
1469bool IROutliner::extractSection(OutlinableRegion &Region) {
1470 SetVector<Value *> ArgInputs, Outputs, SinkCands;
1471 Region.CE->findInputsOutputs(ArgInputs, Outputs, SinkCands);
1472
1473 assert(Region.StartBB && "StartBB for the OutlinableRegion is nullptr!")((Region.StartBB && "StartBB for the OutlinableRegion is nullptr!"
) ? static_cast<void> (0) : __assert_fail ("Region.StartBB && \"StartBB for the OutlinableRegion is nullptr!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1473, __PRETTY_FUNCTION__))
;
1474 assert(Region.FollowBB && "FollowBB for the OutlinableRegion is nullptr!")((Region.FollowBB && "FollowBB for the OutlinableRegion is nullptr!"
) ? static_cast<void> (0) : __assert_fail ("Region.FollowBB && \"FollowBB for the OutlinableRegion is nullptr!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1474, __PRETTY_FUNCTION__))
;
1475 Function *OrigF = Region.StartBB->getParent();
1476 CodeExtractorAnalysisCache CEAC(*OrigF);
1477 Region.ExtractedFunction = Region.CE->extractCodeRegion(CEAC);
1478
1479 // If the extraction was successful, find the BasicBlock, and reassign the
1480 // OutlinableRegion blocks
1481 if (!Region.ExtractedFunction) {
1482 LLVM_DEBUG(dbgs() << "CodeExtractor failed to outline " << Region.StartBBdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "CodeExtractor failed to outline "
<< Region.StartBB << "\n"; } } while (false)
1483 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "CodeExtractor failed to outline "
<< Region.StartBB << "\n"; } } while (false)
;
1484 Region.reattachCandidate();
1485 return false;
1486 }
1487
1488 BasicBlock *RewrittenBB = Region.FollowBB->getSinglePredecessor();
1489 Region.StartBB = RewrittenBB;
1490 Region.EndBB = RewrittenBB;
1491
1492 // The sequences of outlinable regions has now changed. We must fix the
1493 // IRInstructionDataList for consistency. Although they may not be illegal
1494 // instructions, they should not be compared with anything else as they
1495 // should not be outlined in this round. So marking these as illegal is
1496 // allowed.
1497 IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
1498 Instruction *BeginRewritten = &*RewrittenBB->begin();
1499 Instruction *EndRewritten = &*RewrittenBB->begin();
1500 Region.NewFront = new (InstDataAllocator.Allocate()) IRInstructionData(
1501 *BeginRewritten, InstructionClassifier.visit(*BeginRewritten), *IDL);
1502 Region.NewBack = new (InstDataAllocator.Allocate()) IRInstructionData(
1503 *EndRewritten, InstructionClassifier.visit(*EndRewritten), *IDL);
1504
1505 // Insert the first IRInstructionData of the new region in front of the
1506 // first IRInstructionData of the IRSimilarityCandidate.
1507 IDL->insert(Region.Candidate->begin(), *Region.NewFront);
1508 // Insert the first IRInstructionData of the new region after the
1509 // last IRInstructionData of the IRSimilarityCandidate.
1510 IDL->insert(Region.Candidate->end(), *Region.NewBack);
1511 // Remove the IRInstructionData from the IRSimilarityCandidate.
1512 IDL->erase(Region.Candidate->begin(), std::prev(Region.Candidate->end()));
1513
1514 assert(RewrittenBB != nullptr &&((RewrittenBB != nullptr && "Could not find a predecessor after extraction!"
) ? static_cast<void> (0) : __assert_fail ("RewrittenBB != nullptr && \"Could not find a predecessor after extraction!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1515, __PRETTY_FUNCTION__))
1515 "Could not find a predecessor after extraction!")((RewrittenBB != nullptr && "Could not find a predecessor after extraction!"
) ? static_cast<void> (0) : __assert_fail ("RewrittenBB != nullptr && \"Could not find a predecessor after extraction!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1515, __PRETTY_FUNCTION__))
;
1516
1517 // Iterate over the new set of instructions to find the new call
1518 // instruction.
1519 for (Instruction &I : *RewrittenBB)
1520 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1521 if (Region.ExtractedFunction == CI->getCalledFunction())
1522 Region.Call = CI;
1523 } else if (LoadInst *LI = dyn_cast<LoadInst>(&I))
1524 updateOutputMapping(Region, Outputs.getArrayRef(), LI);
1525 Region.reattachCandidate();
1526 return true;
1527}
1528
1529unsigned IROutliner::doOutline(Module &M) {
1530 // Find the possible similarity sections.
1531 IRSimilarityIdentifier &Identifier = getIRSI(M);
1532 SimilarityGroupList &SimilarityCandidates = *Identifier.getSimilarity();
1533
1534 // Sort them by size of extracted sections
1535 unsigned OutlinedFunctionNum = 0;
1536 // If we only have one SimilarityGroup in SimilarityCandidates, we do not have
1537 // to sort them by the potential number of instructions to be outlined
1538 if (SimilarityCandidates.size() > 1)
1539 llvm::stable_sort(SimilarityCandidates,
1540 [](const std::vector<IRSimilarityCandidate> &LHS,
1541 const std::vector<IRSimilarityCandidate> &RHS) {
1542 return LHS[0].getLength() * LHS.size() >
1543 RHS[0].getLength() * RHS.size();
1544 });
1545
1546 DenseSet<unsigned> NotSame;
1547 std::vector<Function *> FuncsToRemove;
1548 // Iterate over the possible sets of similarity.
1549 for (SimilarityGroup &CandidateVec : SimilarityCandidates) {
1550 OutlinableGroup CurrentGroup;
1551
1552 // Remove entries that were previously outlined
1553 pruneIncompatibleRegions(CandidateVec, CurrentGroup);
1554
1555 // We pruned the number of regions to 0 to 1, meaning that it's not worth
1556 // trying to outlined since there is no compatible similar instance of this
1557 // code.
1558 if (CurrentGroup.Regions.size() < 2)
1559 continue;
1560
1561 // Determine if there are any values that are the same constant throughout
1562 // each section in the set.
1563 NotSame.clear();
1564 CurrentGroup.findSameConstants(NotSame);
1565
1566 if (CurrentGroup.IgnoreGroup)
1567 continue;
1568
1569 // Create a CodeExtractor for each outlinable region. Identify inputs and
1570 // outputs for each section using the code extractor and create the argument
1571 // types for the Aggregate Outlining Function.
1572 std::vector<OutlinableRegion *> OutlinedRegions;
1573 for (OutlinableRegion *OS : CurrentGroup.Regions) {
1574 // Break the outlinable region out of its parent BasicBlock into its own
1575 // BasicBlocks (see function implementation).
1576 OS->splitCandidate();
1577 std::vector<BasicBlock *> BE = {OS->StartBB};
1578 OS->CE = new (ExtractorAllocator.Allocate())
1579 CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
1580 false, "outlined");
1581 findAddInputsOutputs(M, *OS, NotSame);
1582 if (!OS->IgnoreRegion)
1583 OutlinedRegions.push_back(OS);
1584 else
1585 OS->reattachCandidate();
1586 }
1587
1588 CurrentGroup.Regions = std::move(OutlinedRegions);
1589
1590 if (CurrentGroup.Regions.empty())
1591 continue;
1592
1593 CurrentGroup.collectGVNStoreSets(M);
1594
1595 if (CostModel)
1596 findCostBenefit(M, CurrentGroup);
1597
1598 // If we are adhering to the cost model, reattach all the candidates
1599 if (CurrentGroup.Cost >= CurrentGroup.Benefit && CostModel) {
1600 for (OutlinableRegion *OS : CurrentGroup.Regions)
1601 OS->reattachCandidate();
1602 OptimizationRemarkEmitter &ORE = getORE(
1603 *CurrentGroup.Regions[0]->Candidate->getFunction());
1604 ORE.emit([&]() {
1605 IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
1606 OptimizationRemarkMissed R(DEBUG_TYPE"iroutliner", "WouldNotDecreaseSize",
1607 C->frontInstruction());
1608 R << "did not outline "
1609 << ore::NV(std::to_string(CurrentGroup.Regions.size()))
1610 << " regions due to estimated increase of "
1611 << ore::NV("InstructionIncrease",
1612 CurrentGroup.Cost - CurrentGroup.Benefit)
1613 << " instructions at locations ";
1614 interleave(
1615 CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
1616 [&R](OutlinableRegion *Region) {
1617 R << ore::NV(
1618 "DebugLoc",
1619 Region->Candidate->frontInstruction()->getDebugLoc());
1620 },
1621 [&R]() { R << " "; });
1622 return R;
1623 });
1624 continue;
1625 }
1626
1627 LLVM_DEBUG(dbgs() << "Outlining regions with cost " << CurrentGroup.Costdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Outlining regions with cost "
<< CurrentGroup.Cost << " and benefit " <<
CurrentGroup.Benefit << "\n"; } } while (false)
1628 << " and benefit " << CurrentGroup.Benefit << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Outlining regions with cost "
<< CurrentGroup.Cost << " and benefit " <<
CurrentGroup.Benefit << "\n"; } } while (false)
;
1629
1630 // Create functions out of all the sections, and mark them as outlined.
1631 OutlinedRegions.clear();
1632 for (OutlinableRegion *OS : CurrentGroup.Regions) {
1633 bool FunctionOutlined = extractSection(*OS);
1634 if (FunctionOutlined) {
1635 unsigned StartIdx = OS->Candidate->getStartIdx();
1636 unsigned EndIdx = OS->Candidate->getEndIdx();
1637 for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
1638 Outlined.insert(Idx);
1639
1640 OutlinedRegions.push_back(OS);
1641 }
1642 }
1643
1644 LLVM_DEBUG(dbgs() << "Outlined " << OutlinedRegions.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Outlined " << OutlinedRegions
.size() << " with benefit " << CurrentGroup.Benefit
<< " and cost " << CurrentGroup.Cost << "\n"
; } } while (false)
1645 << " with benefit " << CurrentGroup.Benefitdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Outlined " << OutlinedRegions
.size() << " with benefit " << CurrentGroup.Benefit
<< " and cost " << CurrentGroup.Cost << "\n"
; } } while (false)
1646 << " and cost " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Outlined " << OutlinedRegions
.size() << " with benefit " << CurrentGroup.Benefit
<< " and cost " << CurrentGroup.Cost << "\n"
; } } while (false)
;
1647
1648 CurrentGroup.Regions = std::move(OutlinedRegions);
1649
1650 if (CurrentGroup.Regions.empty())
1651 continue;
1652
1653 OptimizationRemarkEmitter &ORE =
1654 getORE(*CurrentGroup.Regions[0]->Call->getFunction());
1655 ORE.emit([&]() {
1656 IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
1657 OptimizationRemark R(DEBUG_TYPE"iroutliner", "Outlined", C->front()->Inst);
1658 R << "outlined " << ore::NV(std::to_string(CurrentGroup.Regions.size()))
1659 << " regions with decrease of "
1660 << ore::NV("Benefit", CurrentGroup.Benefit - CurrentGroup.Cost)
1661 << " instructions at locations ";
1662 interleave(
1663 CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
1664 [&R](OutlinableRegion *Region) {
1665 R << ore::NV("DebugLoc",
1666 Region->Candidate->frontInstruction()->getDebugLoc());
1667 },
1668 [&R]() { R << " "; });
1669 return R;
1670 });
1671
1672 deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,
1673 OutlinedFunctionNum);
1674 }
1675
1676 for (Function *F : FuncsToRemove)
1677 F->eraseFromParent();
1678
1679 return OutlinedFunctionNum;
1680}
1681
1682bool IROutliner::run(Module &M) {
1683 CostModel = !NoCostModel;
1684 OutlineFromLinkODRs = EnableLinkOnceODRIROutlining;
1685
1686 return doOutline(M) > 0;
1687}
1688
1689// Pass Manager Boilerplate
1690class IROutlinerLegacyPass : public ModulePass {
1691public:
1692 static char ID;
1693 IROutlinerLegacyPass() : ModulePass(ID) {
1694 initializeIROutlinerLegacyPassPass(*PassRegistry::getPassRegistry());
1695 }
1696
1697 void getAnalysisUsage(AnalysisUsage &AU) const override {
1698 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
1699 AU.addRequired<TargetTransformInfoWrapperPass>();
1700 AU.addRequired<IRSimilarityIdentifierWrapperPass>();
1701 }
1702
1703 bool runOnModule(Module &M) override;
1704};
1705
1706bool IROutlinerLegacyPass::runOnModule(Module &M) {
1707 if (skipModule(M))
1708 return false;
1709
1710 std::unique_ptr<OptimizationRemarkEmitter> ORE;
1711 auto GORE = [&ORE](Function &F) -> OptimizationRemarkEmitter & {
1712 ORE.reset(new OptimizationRemarkEmitter(&F));
1713 return *ORE.get();
1714 };
1715
1716 auto GTTI = [this](Function &F) -> TargetTransformInfo & {
1717 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1718 };
1719
1720 auto GIRSI = [this](Module &) -> IRSimilarityIdentifier & {
1721 return this->getAnalysis<IRSimilarityIdentifierWrapperPass>().getIRSI();
1722 };
1723
1724 return IROutliner(GTTI, GIRSI, GORE).run(M);
1725}
1726
1727PreservedAnalyses IROutlinerPass::run(Module &M, ModuleAnalysisManager &AM) {
1728 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1729
1730 std::function<TargetTransformInfo &(Function &)> GTTI =
1731 [&FAM](Function &F) -> TargetTransformInfo & {
1732 return FAM.getResult<TargetIRAnalysis>(F);
1733 };
1734
1735 std::function<IRSimilarityIdentifier &(Module &)> GIRSI =
1736 [&AM](Module &M) -> IRSimilarityIdentifier & {
1737 return AM.getResult<IRSimilarityAnalysis>(M);
1738 };
1739
1740 std::unique_ptr<OptimizationRemarkEmitter> ORE;
1741 std::function<OptimizationRemarkEmitter &(Function &)> GORE =
1742 [&ORE](Function &F) -> OptimizationRemarkEmitter & {
1743 ORE.reset(new OptimizationRemarkEmitter(&F));
1744 return *ORE.get();
1745 };
1746
1747 if (IROutliner(GTTI, GIRSI, GORE).run(M))
1748 return PreservedAnalyses::none();
1749 return PreservedAnalyses::all();
1750}
1751
1752char IROutlinerLegacyPass::ID = 0;
1753INITIALIZE_PASS_BEGIN(IROutlinerLegacyPass, "iroutliner", "IR Outliner", false,static void *initializeIROutlinerLegacyPassPassOnce(PassRegistry
&Registry) {
1754 false)static void *initializeIROutlinerLegacyPassPassOnce(PassRegistry
&Registry) {
1755INITIALIZE_PASS_DEPENDENCY(IRSimilarityIdentifierWrapperPass)initializeIRSimilarityIdentifierWrapperPassPass(Registry);
1756INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
1757INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
1758INITIALIZE_PASS_END(IROutlinerLegacyPass, "iroutliner", "IR Outliner", false,PassInfo *PI = new PassInfo( "IR Outliner", "iroutliner", &
IROutlinerLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<IROutlinerLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeIROutlinerLegacyPassPassFlag
; void llvm::initializeIROutlinerLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeIROutlinerLegacyPassPassFlag
, initializeIROutlinerLegacyPassPassOnce, std::ref(Registry))
; }
1759 false)PassInfo *PI = new PassInfo( "IR Outliner", "iroutliner", &
IROutlinerLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<IROutlinerLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeIROutlinerLegacyPassPassFlag
; void llvm::initializeIROutlinerLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeIROutlinerLegacyPassPassFlag
, initializeIROutlinerLegacyPassPassOnce, std::ref(Registry))
; }
1760
1761ModulePass *llvm::createIROutlinerPass() { return new IROutlinerLegacyPass(); }