Bug Summary

File:llvm/lib/Transforms/IPO/IROutliner.cpp
Warning:line 959, 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 -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20210125100614+2cdb34efdac5/build-llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-12~++20210125100614+2cdb34efdac5/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20210125100614+2cdb34efdac5/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/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/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/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-12~++20210125100614+2cdb34efdac5/build-llvm/lib/Transforms/IPO -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20210125100614+2cdb34efdac5=. -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 -o /tmp/scan-build-2021-01-26-035717-31997-1 -x c++ /build/llvm-toolchain-snapshot-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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-12~++20210125100614+2cdb34efdac5/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 [out] EndInputNumbers - The global value numbers for the extracted
439/// arguments.
440/// \param [in] OutputMappings - The mapping of values that have been replaced
441/// by a new output value.
442/// \param [out] EndInputs - The global value numbers for the extracted
443/// arguments.
444static void mapInputsToGVNs(IRSimilarityCandidate &C,
445 SetVector<Value *> &CurrentInputs,
446 const DenseMap<Value *, Value *> &OutputMappings,
447 std::vector<unsigned> &EndInputNumbers) {
448 // Get the Global Value Number for each input. We check if the Value has been
449 // replaced by a different value at output, and use the original value before
450 // replacement.
451 for (Value *Input : CurrentInputs) {
452 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 452, __PRETTY_FUNCTION__))
;
453 if (OutputMappings.find(Input) != OutputMappings.end())
454 Input = OutputMappings.find(Input)->second;
455 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 456, __PRETTY_FUNCTION__))
456 "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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 456, __PRETTY_FUNCTION__))
;
457 EndInputNumbers.push_back(C.getGVN(Input).getValue());
458 }
459}
460
461/// Find the original value for the \p ArgInput values if any one of them was
462/// replaced during a previous extraction.
463///
464/// \param [in] ArgInputs - The inputs to be extracted by the code extractor.
465/// \param [in] OutputMappings - The mapping of values that have been replaced
466/// by a new output value.
467/// \param [out] RemappedArgInputs - The remapped values according to
468/// \p OutputMappings that will be extracted.
469static void
470remapExtractedInputs(const ArrayRef<Value *> ArgInputs,
471 const DenseMap<Value *, Value *> &OutputMappings,
472 SetVector<Value *> &RemappedArgInputs) {
473 // Get the global value number for each input that will be extracted as an
474 // argument by the code extractor, remapping if needed for reloaded values.
475 for (Value *Input : ArgInputs) {
476 if (OutputMappings.find(Input) != OutputMappings.end())
477 Input = OutputMappings.find(Input)->second;
478 RemappedArgInputs.insert(Input);
479 }
480}
481
482/// Find the input GVNs and the output values for a region of Instructions.
483/// Using the code extractor, we collect the inputs to the extracted function.
484///
485/// The \p Region can be identified as needing to be ignored in this function.
486/// It should be checked whether it should be ignored after a call to this
487/// function.
488///
489/// \param [in,out] Region - The region of code to be analyzed.
490/// \param [out] InputGVNs - The global value numbers for the extracted
491/// arguments.
492/// \param [in] NotSame - The global value numbers in the region that do not
493/// have the same constant value in the regions structurally similar to
494/// \p Region.
495/// \param [in] OutputMappings - The mapping of values that have been replaced
496/// by a new output value after extraction.
497/// \param [out] ArgInputs - The values of the inputs to the extracted function.
498/// \param [out] Outputs - The set of values extracted by the CodeExtractor
499/// as outputs.
500static void getCodeExtractorArguments(
501 OutlinableRegion &Region, std::vector<unsigned> &InputGVNs,
502 DenseSet<unsigned> &NotSame, DenseMap<Value *, Value *> &OutputMappings,
503 SetVector<Value *> &ArgInputs, SetVector<Value *> &Outputs) {
504 IRSimilarityCandidate &C = *Region.Candidate;
505
506 // OverallInputs are the inputs to the region found by the CodeExtractor,
507 // SinkCands and HoistCands are used by the CodeExtractor to find sunken
508 // allocas of values whose lifetimes are contained completely within the
509 // outlined region. PremappedInputs are the arguments found by the
510 // CodeExtractor, removing conditions such as sunken allocas, but that
511 // may need to be remapped due to the extracted output values replacing
512 // the original values. We use DummyOutputs for this first run of finding
513 // inputs and outputs since the outputs could change during findAllocas,
514 // the correct set of extracted outputs will be in the final Outputs ValueSet.
515 SetVector<Value *> OverallInputs, PremappedInputs, SinkCands, HoistCands,
516 DummyOutputs;
517
518 // Use the code extractor to get the inputs and outputs, without sunken
519 // allocas or removing llvm.assumes.
520 CodeExtractor *CE = Region.CE;
521 CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands);
522 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 522, __PRETTY_FUNCTION__))
;
523 Function *OrigF = Region.StartBB->getParent();
524 CodeExtractorAnalysisCache CEAC(*OrigF);
525 BasicBlock *Dummy = nullptr;
526
527 // The region may be ineligible due to VarArgs in the parent function. In this
528 // case we ignore the region.
529 if (!CE->isEligible()) {
530 Region.IgnoreRegion = true;
531 return;
532 }
533
534 // Find if any values are going to be sunk into the function when extracted
535 CE->findAllocas(CEAC, SinkCands, HoistCands, Dummy);
536 CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands);
537
538 // TODO: Support regions with sunken allocas: values whose lifetimes are
539 // contained completely within the outlined region. These are not guaranteed
540 // to be the same in every region, so we must elevate them all to arguments
541 // when they appear. If these values are not equal, it means there is some
542 // Input in OverallInputs that was removed for ArgInputs.
543 if (OverallInputs.size() != PremappedInputs.size()) {
544 Region.IgnoreRegion = true;
545 return;
546 }
547
548 findConstants(C, NotSame, InputGVNs);
549
550 mapInputsToGVNs(C, OverallInputs, OutputMappings, InputGVNs);
551
552 remapExtractedInputs(PremappedInputs.getArrayRef(), OutputMappings,
553 ArgInputs);
554
555 // Sort the GVNs, since we now have constants included in the \ref InputGVNs
556 // we need to make sure they are in a deterministic order.
557 stable_sort(InputGVNs);
558}
559
560/// Look over the inputs and map each input argument to an argument in the
561/// overall function for the OutlinableRegions. This creates a way to replace
562/// the arguments of the extracted function with the arguments of the new
563/// overall function.
564///
565/// \param [in,out] Region - The region of code to be analyzed.
566/// \param [in] InputsGVNs - The global value numbering of the input values
567/// collected.
568/// \param [in] ArgInputs - The values of the arguments to the extracted
569/// function.
570static void
571findExtractedInputToOverallInputMapping(OutlinableRegion &Region,
572 std::vector<unsigned> &InputGVNs,
573 SetVector<Value *> &ArgInputs) {
574
575 IRSimilarityCandidate &C = *Region.Candidate;
576 OutlinableGroup &Group = *Region.Parent;
577
578 // This counts the argument number in the overall function.
579 unsigned TypeIndex = 0;
580
581 // This counts the argument number in the extracted function.
582 unsigned OriginalIndex = 0;
583
584 // Find the mapping of the extracted arguments to the arguments for the
585 // overall function. Since there may be extra arguments in the overall
586 // function to account for the extracted constants, we have two different
587 // counters as we find extracted arguments, and as we come across overall
588 // arguments.
589 for (unsigned InputVal : InputGVNs) {
590 Optional<Value *> InputOpt = C.fromGVN(InputVal);
591 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 591, __PRETTY_FUNCTION__))
;
592 Value *Input = InputOpt.getValue();
593
594 if (!Group.InputTypesSet) {
595 Group.ArgumentTypes.push_back(Input->getType());
596 // If the input value has a swifterr attribute, make sure to mark the
597 // argument in the overall function.
598 if (Input->isSwiftError()) {
599 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 601, __PRETTY_FUNCTION__))
600 !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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 601, __PRETTY_FUNCTION__))
601 "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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 601, __PRETTY_FUNCTION__))
;
602 Group.SwiftErrorArgument = TypeIndex;
603 }
604 }
605
606 // Check if we have a constant. If we do add it to the overall argument
607 // number to Constant map for the region, and continue to the next input.
608 if (Constant *CST = dyn_cast<Constant>(Input)) {
609 Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST));
610 TypeIndex++;
611 continue;
612 }
613
614 // It is not a constant, we create the mapping from extracted argument list
615 // to the overall argument list.
616 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 616, __PRETTY_FUNCTION__))
;
617
618 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex));
619 Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex));
620 OriginalIndex++;
621 TypeIndex++;
622 }
623
624 // If the function type definitions for the OutlinableGroup holding the region
625 // have not been set, set the length of the inputs here. We should have the
626 // same inputs for all of the different regions contained in the
627 // OutlinableGroup since they are all structurally similar to one another.
628 if (!Group.InputTypesSet) {
629 Group.NumAggregateInputs = TypeIndex;
630 Group.InputTypesSet = true;
631 }
632
633 Region.NumExtractedInputs = OriginalIndex;
634}
635
636/// Create a mapping of the output arguments for the \p Region to the output
637/// arguments of the overall outlined function.
638///
639/// \param [in,out] Region - The region of code to be analyzed.
640/// \param [in] Outputs - The values found by the code extractor.
641static void
642findExtractedOutputToOverallOutputMapping(OutlinableRegion &Region,
643 ArrayRef<Value *> Outputs) {
644 OutlinableGroup &Group = *Region.Parent;
645 IRSimilarityCandidate &C = *Region.Candidate;
646
647 // This counts the argument number in the extracted function.
648 unsigned OriginalIndex = Region.NumExtractedInputs;
649
650 // This counts the argument number in the overall function.
651 unsigned TypeIndex = Group.NumAggregateInputs;
652 bool TypeFound;
653 DenseSet<unsigned> AggArgsUsed;
654
655 // Iterate over the output types and identify if there is an aggregate pointer
656 // type whose base type matches the current output type. If there is, we mark
657 // that we will use this output register for this value. If not we add another
658 // type to the overall argument type list. We also store the GVNs used for
659 // stores to identify which values will need to be moved into an special
660 // block that holds the stores to the output registers.
661 for (Value *Output : Outputs) {
662 TypeFound = false;
663 // We can do this since it is a result value, and will have a number
664 // that is necessarily the same. BUT if in the future, the instructions
665 // do not have to be in same order, but are functionally the same, we will
666 // have to use a different scheme, as one-to-one correspondence is not
667 // guaranteed.
668 unsigned GlobalValue = C.getGVN(Output).getValue();
669 unsigned ArgumentSize = Group.ArgumentTypes.size();
670
671 for (unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {
672 if (Group.ArgumentTypes[Jdx] != PointerType::getUnqual(Output->getType()))
673 continue;
674
675 if (AggArgsUsed.contains(Jdx))
676 continue;
677
678 TypeFound = true;
679 AggArgsUsed.insert(Jdx);
680 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, Jdx));
681 Region.AggArgToExtracted.insert(std::make_pair(Jdx, OriginalIndex));
682 Region.GVNStores.push_back(GlobalValue);
683 break;
684 }
685
686 // We were unable to find an unused type in the output type set that matches
687 // the output, so we add a pointer type to the argument types of the overall
688 // function to handle this output and create a mapping to it.
689 if (!TypeFound) {
690 Group.ArgumentTypes.push_back(PointerType::getUnqual(Output->getType()));
691 AggArgsUsed.insert(Group.ArgumentTypes.size() - 1);
692 Region.ExtractedArgToAgg.insert(
693 std::make_pair(OriginalIndex, Group.ArgumentTypes.size() - 1));
694 Region.AggArgToExtracted.insert(
695 std::make_pair(Group.ArgumentTypes.size() - 1, OriginalIndex));
696 Region.GVNStores.push_back(GlobalValue);
697 }
698
699 stable_sort(Region.GVNStores);
700 OriginalIndex++;
701 TypeIndex++;
702 }
703}
704
705void IROutliner::findAddInputsOutputs(Module &M, OutlinableRegion &Region,
706 DenseSet<unsigned> &NotSame) {
707 std::vector<unsigned> Inputs;
708 SetVector<Value *> ArgInputs, Outputs;
709
710 getCodeExtractorArguments(Region, Inputs, NotSame, OutputMappings, ArgInputs,
711 Outputs);
712
713 if (Region.IgnoreRegion)
714 return;
715
716 // Map the inputs found by the CodeExtractor to the arguments found for
717 // the overall function.
718 findExtractedInputToOverallInputMapping(Region, Inputs, ArgInputs);
719
720 // Map the outputs found by the CodeExtractor to the arguments found for
721 // the overall function.
722 findExtractedOutputToOverallOutputMapping(Region, Outputs.getArrayRef());
723}
724
725/// Replace the extracted function in the Region with a call to the overall
726/// function constructed from the deduplicated similar regions, replacing and
727/// remapping the values passed to the extracted function as arguments to the
728/// new arguments of the overall function.
729///
730/// \param [in] M - The module to outline from.
731/// \param [in] Region - The regions of extracted code to be replaced with a new
732/// function.
733/// \returns a call instruction with the replaced function.
734CallInst *replaceCalledFunction(Module &M, OutlinableRegion &Region) {
735 std::vector<Value *> NewCallArgs;
736 DenseMap<unsigned, unsigned>::iterator ArgPair;
737
738 OutlinableGroup &Group = *Region.Parent;
739 CallInst *Call = Region.Call;
740 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 740, __PRETTY_FUNCTION__))
;
741 Function *AggFunc = Group.OutlinedFunction;
742 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 742, __PRETTY_FUNCTION__))
;
743
744 // If the arguments are the same size, there are not values that need to be
745 // made argument, or different output registers to handle. We can simply
746 // replace the called function in this case.
747 if (AggFunc->arg_size() == Call->arg_size()) {
748 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)
749 << *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)
;
750 Call->setCalledFunction(AggFunc);
751 return Call;
752 }
753
754 // We have a different number of arguments than the new function, so
755 // we need to use our previously mappings off extracted argument to overall
756 // function argument, and constants to overall function argument to create the
757 // new argument list.
758 for (unsigned AggArgIdx = 0; AggArgIdx < AggFunc->arg_size(); AggArgIdx++) {
759
760 if (AggArgIdx == AggFunc->arg_size() - 1 &&
761 Group.OutputGVNCombinations.size() > 1) {
762 // If we are on the last argument, and we need to differentiate between
763 // output blocks, add an integer to the argument list to determine
764 // what block to take
765 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
)
766 << Region.OutputBlockNum << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Set switch block argument to "
<< Region.OutputBlockNum << "\n"; } } while (false
)
;
767 NewCallArgs.push_back(ConstantInt::get(Type::getInt32Ty(M.getContext()),
768 Region.OutputBlockNum));
769 continue;
770 }
771
772 ArgPair = Region.AggArgToExtracted.find(AggArgIdx);
773 if (ArgPair != Region.AggArgToExtracted.end()) {
774 Value *ArgumentValue = Call->getArgOperand(ArgPair->second);
775 // If we found the mapping from the extracted function to the overall
776 // function, we simply add it to the argument list. We use the same
777 // value, it just needs to honor the new order of arguments.
778 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)
779 << *ArgumentValue << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Setting argument " <<
AggArgIdx << " to value " << *ArgumentValue <<
"\n"; } } while (false)
;
780 NewCallArgs.push_back(ArgumentValue);
781 continue;
782 }
783
784 // If it is a constant, we simply add it to the argument list as a value.
785 if (Region.AggArgToConstant.find(AggArgIdx) !=
786 Region.AggArgToConstant.end()) {
787 Constant *CST = Region.AggArgToConstant.find(AggArgIdx)->second;
788 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)
789 << *CST << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Setting argument " <<
AggArgIdx << " to value " << *CST << "\n";
} } while (false)
;
790 NewCallArgs.push_back(CST);
791 continue;
792 }
793
794 // Add a nullptr value if the argument is not found in the extracted
795 // function. If we cannot find a value, it means it is not in use
796 // for the region, so we should not pass anything to it.
797 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)
;
798 NewCallArgs.push_back(ConstantPointerNull::get(
799 static_cast<PointerType *>(AggFunc->getArg(AggArgIdx)->getType())));
800 }
801
802 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)
803 << *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)
;
804 // Create the new call instruction and erase the old one.
805 Call = CallInst::Create(AggFunc->getFunctionType(), AggFunc, NewCallArgs, "",
806 Call);
807
808 // It is possible that the call to the outlined function is either the first
809 // instruction is in the new block, the last instruction, or both. If either
810 // of these is the case, we need to make sure that we replace the instruction
811 // in the IRInstructionData struct with the new call.
812 CallInst *OldCall = Region.Call;
813 if (Region.NewFront->Inst == OldCall)
814 Region.NewFront->Inst = Call;
815 if (Region.NewBack->Inst == OldCall)
816 Region.NewBack->Inst = Call;
817
818 // Transfer any debug information.
819 Call->setDebugLoc(Region.Call->getDebugLoc());
820
821 // Remove the old instruction.
822 OldCall->eraseFromParent();
823 Region.Call = Call;
824
825 // Make sure that the argument in the new function has the SwiftError
826 // argument.
827 if (Group.SwiftErrorArgument.hasValue())
828 Call->addParamAttr(Group.SwiftErrorArgument.getValue(),
829 Attribute::SwiftError);
830
831 return Call;
832}
833
834// Within an extracted function, replace the argument uses of the extracted
835// region with the arguments of the function for an OutlinableGroup.
836//
837/// \param [in] Region - The region of extracted code to be changed.
838/// \param [in,out] OutputBB - The BasicBlock for the output stores for this
839/// region.
840static void replaceArgumentUses(OutlinableRegion &Region,
841 BasicBlock *OutputBB) {
842 OutlinableGroup &Group = *Region.Parent;
843 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 843, __PRETTY_FUNCTION__))
;
844
845 for (unsigned ArgIdx = 0; ArgIdx < Region.ExtractedFunction->arg_size();
846 ArgIdx++) {
847 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 849, __PRETTY_FUNCTION__))
848 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 849, __PRETTY_FUNCTION__))
849 "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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 849, __PRETTY_FUNCTION__))
;
850 unsigned AggArgIdx = Region.ExtractedArgToAgg.find(ArgIdx)->second;
851 Argument *AggArg = Group.OutlinedFunction->getArg(AggArgIdx);
852 Argument *Arg = Region.ExtractedFunction->getArg(ArgIdx);
853 // The argument is an input, so we can simply replace it with the overall
854 // argument value
855 if (ArgIdx < Region.NumExtractedInputs) {
856 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)
857 << *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)
858 << " 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)
;
859 Arg->replaceAllUsesWith(AggArg);
860 continue;
861 }
862
863 // If we are replacing an output, we place the store value in its own
864 // block inside the overall function before replacing the use of the output
865 // in the function.
866 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 866, __PRETTY_FUNCTION__))
;
867 User *InstAsUser = Arg->user_back();
868 assert(InstAsUser && "User is nullptr!")((InstAsUser && "User is nullptr!") ? static_cast<
void> (0) : __assert_fail ("InstAsUser && \"User is nullptr!\""
, "/build/llvm-toolchain-snapshot-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 868, __PRETTY_FUNCTION__))
;
869
870 Instruction *I = cast<Instruction>(InstAsUser);
871 I->setDebugLoc(DebugLoc());
872 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)
873 << *OutputBB << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move store for instruction "
<< *I << " to " << *OutputBB << "\n"
; } } while (false)
;
874
875 I->moveBefore(*OutputBB, OutputBB->end());
876
877 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)
878 << *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)
879 << " 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)
;
880 Arg->replaceAllUsesWith(AggArg);
881 }
882}
883
884/// Within an extracted function, replace the constants that need to be lifted
885/// into arguments with the actual argument.
886///
887/// \param Region [in] - The region of extracted code to be changed.
888void replaceConstants(OutlinableRegion &Region) {
889 OutlinableGroup &Group = *Region.Parent;
890 // Iterate over the constants that need to be elevated into arguments
891 for (std::pair<unsigned, Constant *> &Const : Region.AggArgToConstant) {
892 unsigned AggArgIdx = Const.first;
893 Function *OutlinedFunction = Group.OutlinedFunction;
894 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 894, __PRETTY_FUNCTION__))
;
895 Constant *CST = Const.second;
896 Argument *Arg = Group.OutlinedFunction->getArg(AggArgIdx);
897 // Identify the argument it will be elevated to, and replace instances of
898 // that constant in the function.
899
900 // TODO: If in the future constants do not have one global value number,
901 // i.e. a constant 1 could be mapped to several values, this check will
902 // have to be more strict. It cannot be using only replaceUsesWithIf.
903
904 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
)
905 << " 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
)
906 << *Arg << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Replacing uses of constant "
<< *CST << " in function " << *OutlinedFunction
<< " with " << *Arg << "\n"; } } while (false
)
;
907 CST->replaceUsesWithIf(Arg, [OutlinedFunction](Use &U) {
908 if (Instruction *I = dyn_cast<Instruction>(U.getUser()))
909 return I->getFunction() == OutlinedFunction;
910 return false;
911 });
912 }
913}
914
915/// For the given function, find all the nondebug or lifetime instructions,
916/// and return them as a vector. Exclude any blocks in \p ExludeBlocks.
917///
918/// \param [in] F - The function we collect the instructions from.
919/// \param [in] ExcludeBlocks - BasicBlocks to ignore.
920/// \returns the list of instructions extracted.
921static std::vector<Instruction *>
922collectRelevantInstructions(Function &F,
923 DenseSet<BasicBlock *> &ExcludeBlocks) {
924 std::vector<Instruction *> RelevantInstructions;
925
926 for (BasicBlock &BB : F) {
927 if (ExcludeBlocks.contains(&BB))
928 continue;
929
930 for (Instruction &Inst : BB) {
931 if (Inst.isLifetimeStartOrEnd())
932 continue;
933 if (isa<DbgInfoIntrinsic>(Inst))
934 continue;
935
936 RelevantInstructions.push_back(&Inst);
937 }
938 }
939
940 return RelevantInstructions;
941}
942
943/// It is possible that there is a basic block that already performs the same
944/// stores. This returns a duplicate block, if it exists
945///
946/// \param OutputBB [in] the block we are looking for a duplicate of.
947/// \param OutputStoreBBs [in] The existing output blocks.
948/// \returns an optional value with the number output block if there is a match.
949Optional<unsigned>
950findDuplicateOutputBlock(BasicBlock *OutputBB,
951 ArrayRef<BasicBlock *> OutputStoreBBs) {
952
953 bool WrongInst = false;
954 bool WrongSize = false;
955 unsigned MatchingNum = 0;
956 for (BasicBlock *CompBB : OutputStoreBBs) {
957 WrongInst = false;
958 if (CompBB->size() - 1 != OutputBB->size()) {
959 WrongSize = true;
Value stored to 'WrongSize' is never read
960 MatchingNum++;
961 continue;
962 }
963
964 WrongSize = false;
965 BasicBlock::iterator NIt = OutputBB->begin();
966 for (Instruction &I : *CompBB) {
967 if (isa<BranchInst>(&I))
968 continue;
969
970 if (!I.isIdenticalTo(&(*NIt))) {
971 WrongInst = true;
972 break;
973 }
974
975 NIt++;
976 }
977 if (!WrongInst && !WrongSize)
978 return MatchingNum;
979
980 MatchingNum++;
981 }
982
983 return None;
984}
985
986/// For the outlined section, move needed the StoreInsts for the output
987/// registers into their own block. Then, determine if there is a duplicate
988/// output block already created.
989///
990/// \param [in] OG - The OutlinableGroup of regions to be outlined.
991/// \param [in] Region - The OutlinableRegion that is being analyzed.
992/// \param [in,out] OutputBB - the block that stores for this region will be
993/// placed in.
994/// \param [in] EndBB - the final block of the extracted function.
995/// \param [in] OutputMappings - OutputMappings the mapping of values that have
996/// been replaced by a new output value.
997/// \param [in,out] OutputStoreBBs - The existing output blocks.
998static void
999alignOutputBlockWithAggFunc(OutlinableGroup &OG, OutlinableRegion &Region,
1000 BasicBlock *OutputBB, BasicBlock *EndBB,
1001 const DenseMap<Value *, Value *> &OutputMappings,
1002 std::vector<BasicBlock *> &OutputStoreBBs) {
1003 DenseSet<unsigned> ValuesToFind(Region.GVNStores.begin(),
1004 Region.GVNStores.end());
1005
1006 // We iterate over the instructions in the extracted function, and find the
1007 // global value number of the instructions. If we find a value that should
1008 // be contained in a store, we replace the uses of the value with the value
1009 // from the overall function, so that the store is storing the correct
1010 // value from the overall function.
1011 DenseSet<BasicBlock *> ExcludeBBs(OutputStoreBBs.begin(),
1012 OutputStoreBBs.end());
1013 ExcludeBBs.insert(OutputBB);
1014 std::vector<Instruction *> ExtractedFunctionInsts =
1015 collectRelevantInstructions(*(Region.ExtractedFunction), ExcludeBBs);
1016 std::vector<Instruction *> OverallFunctionInsts =
1017 collectRelevantInstructions(*OG.OutlinedFunction, ExcludeBBs);
1018
1019 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1020, __PRETTY_FUNCTION__))
1020 "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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1020, __PRETTY_FUNCTION__))
;
1021
1022 unsigned NumInstructions = ExtractedFunctionInsts.size();
1023 for (unsigned Idx = 0; Idx < NumInstructions; Idx++) {
1024 Value *V = ExtractedFunctionInsts[Idx];
1025
1026 if (OutputMappings.find(V) != OutputMappings.end())
1027 V = OutputMappings.find(V)->second;
1028 Optional<unsigned> GVN = Region.Candidate->getGVN(V);
1029
1030 // If we have found one of the stored values for output, replace the value
1031 // with the corresponding one from the overall function.
1032 if (GVN.hasValue() && ValuesToFind.erase(GVN.getValue())) {
1033 V->replaceAllUsesWith(OverallFunctionInsts[Idx]);
1034 if (ValuesToFind.size() == 0)
1035 break;
1036 }
1037
1038 if (ValuesToFind.size() == 0)
1039 break;
1040 }
1041
1042 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1042, __PRETTY_FUNCTION__))
;
1043
1044 // If the size of the block is 0, then there are no stores, and we do not
1045 // need to save this block.
1046 if (OutputBB->size() == 0) {
1047 Region.OutputBlockNum = -1;
1048 OutputBB->eraseFromParent();
1049 return;
1050 }
1051
1052 // Determine is there is a duplicate block.
1053 Optional<unsigned> MatchingBB =
1054 findDuplicateOutputBlock(OutputBB, OutputStoreBBs);
1055
1056 // If there is, we remove the new output block. If it does not,
1057 // we add it to our list of output blocks.
1058 if (MatchingBB.hasValue()) {
1059 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)
1060 << 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)
1061 << MatchingBB.getValue())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Set output block for region in function"
<< Region.ExtractedFunction << " to " << MatchingBB
.getValue(); } } while (false)
;
1062
1063 Region.OutputBlockNum = MatchingBB.getValue();
1064 OutputBB->eraseFromParent();
1065 return;
1066 }
1067
1068 Region.OutputBlockNum = OutputStoreBBs.size();
1069
1070 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)
1071 << Region.ExtractedFunction << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Create output block for region in"
<< Region.ExtractedFunction << " to " << *
OutputBB; } } while (false)
1072 << *OutputBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Create output block for region in"
<< Region.ExtractedFunction << " to " << *
OutputBB; } } while (false)
;
1073 OutputStoreBBs.push_back(OutputBB);
1074 BranchInst::Create(EndBB, OutputBB);
1075}
1076
1077/// Create the switch statement for outlined function to differentiate between
1078/// all the output blocks.
1079///
1080/// For the outlined section, determine if an outlined block already exists that
1081/// matches the needed stores for the extracted section.
1082/// \param [in] M - The module we are outlining from.
1083/// \param [in] OG - The group of regions to be outlined.
1084/// \param [in] OS - The region that is being analyzed.
1085/// \param [in] EndBB - The final block of the extracted function.
1086/// \param [in,out] OutputStoreBBs - The existing output blocks.
1087void createSwitchStatement(Module &M, OutlinableGroup &OG, BasicBlock *EndBB,
1088 ArrayRef<BasicBlock *> OutputStoreBBs) {
1089 // We only need the switch statement if there is more than one store
1090 // combination.
1091 if (OG.OutputGVNCombinations.size() > 1) {
1092 Function *AggFunc = OG.OutlinedFunction;
1093 // Create a final block
1094 BasicBlock *ReturnBlock =
1095 BasicBlock::Create(M.getContext(), "final_block", AggFunc);
1096 Instruction *Term = EndBB->getTerminator();
1097 Term->moveBefore(*ReturnBlock, ReturnBlock->end());
1098 // Put the switch statement in the old end basic block for the function with
1099 // a fall through to the new return block
1100 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)
1101 << OutputStoreBBs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Create switch statement in "
<< *AggFunc << " for " << OutputStoreBBs.size
() << "\n"; } } while (false)
;
1102 SwitchInst *SwitchI =
1103 SwitchInst::Create(AggFunc->getArg(AggFunc->arg_size() - 1),
1104 ReturnBlock, OutputStoreBBs.size(), EndBB);
1105
1106 unsigned Idx = 0;
1107 for (BasicBlock *BB : OutputStoreBBs) {
1108 SwitchI->addCase(ConstantInt::get(Type::getInt32Ty(M.getContext()), Idx),
1109 BB);
1110 Term = BB->getTerminator();
1111 Term->setSuccessor(0, ReturnBlock);
1112 Idx++;
1113 }
1114 return;
1115 }
1116
1117 // If there needs to be stores, move them from the output block to the end
1118 // block to save on branching instructions.
1119 if (OutputStoreBBs.size() == 1) {
1120 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
)
1121 << *OG.OutlinedFunction << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move store instructions to the end block in "
<< *OG.OutlinedFunction << "\n"; } } while (false
)
;
1122 BasicBlock *OutputBlock = OutputStoreBBs[0];
1123 Instruction *Term = OutputBlock->getTerminator();
1124 Term->eraseFromParent();
1125 Term = EndBB->getTerminator();
1126 moveBBContents(*OutputBlock, *EndBB);
1127 Term->moveBefore(*EndBB, EndBB->end());
1128 OutputBlock->eraseFromParent();
1129 }
1130}
1131
1132/// Fill the new function that will serve as the replacement function for all of
1133/// the extracted regions of a certain structure from the first region in the
1134/// list of regions. Replace this first region's extracted function with the
1135/// new overall function.
1136///
1137/// \param [in] M - The module we are outlining from.
1138/// \param [in] CurrentGroup - The group of regions to be outlined.
1139/// \param [in,out] OutputStoreBBs - The output blocks for each different
1140/// set of stores needed for the different functions.
1141/// \param [in,out] FuncsToRemove - Extracted functions to erase from module
1142/// once outlining is complete.
1143static void fillOverallFunction(Module &M, OutlinableGroup &CurrentGroup,
1144 std::vector<BasicBlock *> &OutputStoreBBs,
1145 std::vector<Function *> &FuncsToRemove) {
1146 OutlinableRegion *CurrentOS = CurrentGroup.Regions[0];
1147
1148 // Move first extracted function's instructions into new function.
1149 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)
1150 << *CurrentOS->ExtractedFunction << " to instruction "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move instructions from " <<
*CurrentOS->ExtractedFunction << " to instruction "
<< *CurrentGroup.OutlinedFunction << "\n"; } } while
(false)
1151 << *CurrentGroup.OutlinedFunction << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Move instructions from " <<
*CurrentOS->ExtractedFunction << " to instruction "
<< *CurrentGroup.OutlinedFunction << "\n"; } } while
(false)
;
1152
1153 CurrentGroup.EndBB = moveFunctionData(*CurrentOS->ExtractedFunction,
1154 *CurrentGroup.OutlinedFunction);
1155
1156 // Transfer the attributes from the function to the new function.
1157 for (Attribute A :
1158 CurrentOS->ExtractedFunction->getAttributes().getFnAttributes())
1159 CurrentGroup.OutlinedFunction->addFnAttr(A);
1160
1161 // Create an output block for the first extracted function.
1162 BasicBlock *NewBB = BasicBlock::Create(
1163 M.getContext(), Twine("output_block_") + Twine(static_cast<unsigned>(0)),
1164 CurrentGroup.OutlinedFunction);
1165 CurrentOS->OutputBlockNum = 0;
1166
1167 replaceArgumentUses(*CurrentOS, NewBB);
1168 replaceConstants(*CurrentOS);
1169
1170 // If the new basic block has no new stores, we can erase it from the module.
1171 // It it does, we create a branch instruction to the last basic block from the
1172 // new one.
1173 if (NewBB->size() == 0) {
1174 CurrentOS->OutputBlockNum = -1;
1175 NewBB->eraseFromParent();
1176 } else {
1177 BranchInst::Create(CurrentGroup.EndBB, NewBB);
1178 OutputStoreBBs.push_back(NewBB);
1179 }
1180
1181 // Replace the call to the extracted function with the outlined function.
1182 CurrentOS->Call = replaceCalledFunction(M, *CurrentOS);
1183
1184 // We only delete the extracted functions at the end since we may need to
1185 // reference instructions contained in them for mapping purposes.
1186 FuncsToRemove.push_back(CurrentOS->ExtractedFunction);
1187}
1188
1189void IROutliner::deduplicateExtractedSections(
1190 Module &M, OutlinableGroup &CurrentGroup,
1191 std::vector<Function *> &FuncsToRemove, unsigned &OutlinedFunctionNum) {
1192 createFunction(M, CurrentGroup, OutlinedFunctionNum);
1193
1194 std::vector<BasicBlock *> OutputStoreBBs;
1195
1196 OutlinableRegion *CurrentOS;
1197
1198 fillOverallFunction(M, CurrentGroup, OutputStoreBBs, FuncsToRemove);
1199
1200 for (unsigned Idx = 1; Idx < CurrentGroup.Regions.size(); Idx++) {
1201 CurrentOS = CurrentGroup.Regions[Idx];
1202 AttributeFuncs::mergeAttributesForOutlining(*CurrentGroup.OutlinedFunction,
1203 *CurrentOS->ExtractedFunction);
1204
1205 // Create a new BasicBlock to hold the needed store instructions.
1206 BasicBlock *NewBB = BasicBlock::Create(
1207 M.getContext(), "output_block_" + std::to_string(Idx),
1208 CurrentGroup.OutlinedFunction);
1209 replaceArgumentUses(*CurrentOS, NewBB);
1210
1211 alignOutputBlockWithAggFunc(CurrentGroup, *CurrentOS, NewBB,
1212 CurrentGroup.EndBB, OutputMappings,
1213 OutputStoreBBs);
1214
1215 CurrentOS->Call = replaceCalledFunction(M, *CurrentOS);
1216 FuncsToRemove.push_back(CurrentOS->ExtractedFunction);
1217 }
1218
1219 // Create a switch statement to handle the different output schemes.
1220 createSwitchStatement(M, CurrentGroup, CurrentGroup.EndBB, OutputStoreBBs);
1221
1222 OutlinedFunctionNum++;
1223}
1224
1225void IROutliner::pruneIncompatibleRegions(
1226 std::vector<IRSimilarityCandidate> &CandidateVec,
1227 OutlinableGroup &CurrentGroup) {
1228 bool PreviouslyOutlined;
1229
1230 // Sort from beginning to end, so the IRSimilarityCandidates are in order.
1231 stable_sort(CandidateVec, [](const IRSimilarityCandidate &LHS,
1232 const IRSimilarityCandidate &RHS) {
1233 return LHS.getStartIdx() < RHS.getStartIdx();
1234 });
1235
1236 unsigned CurrentEndIdx = 0;
1237 for (IRSimilarityCandidate &IRSC : CandidateVec) {
1238 PreviouslyOutlined = false;
1239 unsigned StartIdx = IRSC.getStartIdx();
1240 unsigned EndIdx = IRSC.getEndIdx();
1241
1242 for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
1243 if (Outlined.contains(Idx)) {
1244 PreviouslyOutlined = true;
1245 break;
1246 }
1247
1248 if (PreviouslyOutlined)
1249 continue;
1250
1251 // TODO: If in the future we can outline across BasicBlocks, we will need to
1252 // check all BasicBlocks contained in the region.
1253 if (IRSC.getStartBB()->hasAddressTaken())
1254 continue;
1255
1256 if (IRSC.front()->Inst->getFunction()->hasLinkOnceODRLinkage() &&
1257 !OutlineFromLinkODRs)
1258 continue;
1259
1260 // Greedily prune out any regions that will overlap with already chosen
1261 // regions.
1262 if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)
1263 continue;
1264
1265 bool BadInst = any_of(IRSC, [this](IRInstructionData &ID) {
1266 // We check if there is a discrepancy between the InstructionDataList
1267 // and the actual next instruction in the module. If there is, it means
1268 // that an extra instruction was added, likely by the CodeExtractor.
1269
1270 // Since we do not have any similarity data about this particular
1271 // instruction, we cannot confidently outline it, and must discard this
1272 // candidate.
1273 if (std::next(ID.getIterator())->Inst !=
1274 ID.Inst->getNextNonDebugInstruction())
1275 return true;
1276 return !this->InstructionClassifier.visit(ID.Inst);
1277 });
1278
1279 if (BadInst)
1280 continue;
1281
1282 OutlinableRegion *OS = new (RegionAllocator.Allocate())
1283 OutlinableRegion(IRSC, CurrentGroup);
1284 CurrentGroup.Regions.push_back(OS);
1285
1286 CurrentEndIdx = EndIdx;
1287 }
1288}
1289
1290InstructionCost
1291IROutliner::findBenefitFromAllRegions(OutlinableGroup &CurrentGroup) {
1292 InstructionCost RegionBenefit = 0;
1293 for (OutlinableRegion *Region : CurrentGroup.Regions) {
1294 TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
1295 // We add the number of instructions in the region to the benefit as an
1296 // estimate as to how much will be removed.
1297 RegionBenefit += Region->getBenefit(TTI);
1298 LLVM_DEBUG(dbgs() << "Adding: " << RegionBenefitdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << RegionBenefit
<< " saved instructions to overfall benefit.\n"; } } while
(false)
1299 << " saved instructions to overfall benefit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Adding: " << RegionBenefit
<< " saved instructions to overfall benefit.\n"; } } while
(false)
;
1300 }
1301
1302 return RegionBenefit;
1303}
1304
1305InstructionCost
1306IROutliner::findCostOutputReloads(OutlinableGroup &CurrentGroup) {
1307 InstructionCost OverallCost = 0;
1308 for (OutlinableRegion *Region : CurrentGroup.Regions) {
1309 TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());
1310
1311 // Each output incurs a load after the call, so we add that to the cost.
1312 for (unsigned OutputGVN : Region->GVNStores) {
1313 Optional<Value *> OV = Region->Candidate->fromGVN(OutputGVN);
1314 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1314, __PRETTY_FUNCTION__))
;
1315 Value *V = OV.getValue();
1316 InstructionCost LoadCost =
1317 TTI.getMemoryOpCost(Instruction::Load, V->getType(), Align(1), 0,
1318 TargetTransformInfo::TCK_CodeSize);
1319
1320 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)
1321 << " 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)
1322 << *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)
;
1323 OverallCost += LoadCost;
1324 }
1325 }
1326
1327 return OverallCost;
1328}
1329
1330/// Find the extra instructions needed to handle any output values for the
1331/// region.
1332///
1333/// \param [in] M - The Module to outline from.
1334/// \param [in] CurrentGroup - The collection of OutlinableRegions to analyze.
1335/// \param [in] TTI - The TargetTransformInfo used to collect information for
1336/// new instruction costs.
1337/// \returns the additional cost to handle the outputs.
1338static InstructionCost findCostForOutputBlocks(Module &M,
1339 OutlinableGroup &CurrentGroup,
1340 TargetTransformInfo &TTI) {
1341 InstructionCost OutputCost = 0;
1342
1343 for (const ArrayRef<unsigned> &OutputUse :
1344 CurrentGroup.OutputGVNCombinations) {
1345 IRSimilarityCandidate &Candidate = *CurrentGroup.Regions[0]->Candidate;
1346 for (unsigned GVN : OutputUse) {
1347 Optional<Value *> OV = Candidate.fromGVN(GVN);
1348 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1348, __PRETTY_FUNCTION__))
;
1349 Value *V = OV.getValue();
1350 InstructionCost StoreCost =
1351 TTI.getMemoryOpCost(Instruction::Load, V->getType(), Align(1), 0,
1352 TargetTransformInfo::TCK_CodeSize);
1353
1354 // An instruction cost is added for each store set that needs to occur for
1355 // various output combinations inside the function, plus a branch to
1356 // return to the exit block.
1357 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)
1358 << " 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)
1359 << *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)
;
1360 OutputCost += StoreCost;
1361 }
1362
1363 InstructionCost BranchCost =
1364 TTI.getCFInstrCost(Instruction::Br, TargetTransformInfo::TCK_CodeSize);
1365 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)
1366 << " 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)
;
1367 OutputCost += BranchCost;
1368 }
1369
1370 // If there is more than one output scheme, we must have a comparison and
1371 // branch for each different item in the switch statement.
1372 if (CurrentGroup.OutputGVNCombinations.size() > 1) {
1373 InstructionCost ComparisonCost = TTI.getCmpSelInstrCost(
1374 Instruction::ICmp, Type::getInt32Ty(M.getContext()),
1375 Type::getInt32Ty(M.getContext()), CmpInst::BAD_ICMP_PREDICATE,
1376 TargetTransformInfo::TCK_CodeSize);
1377 InstructionCost BranchCost =
1378 TTI.getCFInstrCost(Instruction::Br, TargetTransformInfo::TCK_CodeSize);
1379
1380 unsigned DifferentBlocks = CurrentGroup.OutputGVNCombinations.size();
1381 InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;
1382
1383 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)
1384 << " 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)
1385 << " 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)
;
1386 OutputCost += TotalCost;
1387 }
1388
1389 return OutputCost;
1390}
1391
1392void IROutliner::findCostBenefit(Module &M, OutlinableGroup &CurrentGroup) {
1393 InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);
1394 CurrentGroup.Benefit += RegionBenefit;
1395 LLVM_DEBUG(dbgs() << "Current Benefit: " << CurrentGroup.Benefit << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Benefit: " <<
CurrentGroup.Benefit << "\n"; } } while (false)
;
1396
1397 InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);
1398 CurrentGroup.Cost += OutputReloadCost;
1399 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1400
1401 InstructionCost AverageRegionBenefit =
1402 RegionBenefit / CurrentGroup.Regions.size();
1403 unsigned OverallArgumentNum = CurrentGroup.ArgumentTypes.size();
1404 unsigned NumRegions = CurrentGroup.Regions.size();
1405 TargetTransformInfo &TTI =
1406 getTTI(*CurrentGroup.Regions[0]->Candidate->getFunction());
1407
1408 // We add one region to the cost once, to account for the instructions added
1409 // inside of the newly created function.
1410 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)
1411 << " 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)
;
1412 CurrentGroup.Cost += AverageRegionBenefit;
1413 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1414
1415 // For each argument, we must add an instruction for loading the argument
1416 // out of the register and into a value inside of the newly outlined function.
1417 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)
1418 << " 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)
1419 << " 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)
;
1420 CurrentGroup.Cost +=
1421 OverallArgumentNum * TargetTransformInfo::TCC_Basic;
1422 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1423
1424 // Each argument needs to either be loaded into a register or onto the stack.
1425 // Some arguments will only be loaded into the stack once the argument
1426 // registers are filled.
1427 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)
1428 << " 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)
1429 << " 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)
1430 << "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)
;
1431 CurrentGroup.Cost +=
1432 2 * OverallArgumentNum * TargetTransformInfo::TCC_Basic * NumRegions;
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 CurrentGroup.Cost += findCostForOutputBlocks(M, CurrentGroup, TTI);
1436 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Current Cost: " << CurrentGroup
.Cost << "\n"; } } while (false)
;
1437}
1438
1439void IROutliner::updateOutputMapping(OutlinableRegion &Region,
1440 ArrayRef<Value *> Outputs,
1441 LoadInst *LI) {
1442 // For and load instructions following the call
1443 Value *Operand = LI->getPointerOperand();
1444 Optional<unsigned> OutputIdx = None;
1445 // Find if the operand it is an output register.
1446 for (unsigned ArgIdx = Region.NumExtractedInputs;
1447 ArgIdx < Region.Call->arg_size(); ArgIdx++) {
1448 if (Operand == Region.Call->getArgOperand(ArgIdx)) {
1449 OutputIdx = ArgIdx - Region.NumExtractedInputs;
1450 break;
1451 }
1452 }
1453
1454 // If we found an output register, place a mapping of the new value
1455 // to the original in the mapping.
1456 if (!OutputIdx.hasValue())
1457 return;
1458
1459 if (OutputMappings.find(Outputs[OutputIdx.getValue()]) ==
1460 OutputMappings.end()) {
1461 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)
1462 << *Outputs[OutputIdx.getValue()] << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Mapping extracted output "
<< *LI << " to " << *Outputs[OutputIdx.getValue
()] << "\n"; } } while (false)
;
1463 OutputMappings.insert(std::make_pair(LI, Outputs[OutputIdx.getValue()]));
1464 } else {
1465 Value *Orig = OutputMappings.find(Outputs[OutputIdx.getValue()])->second;
1466 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)
1467 << *Outputs[OutputIdx.getValue()] << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "Mapping extracted output "
<< *Orig << " to " << *Outputs[OutputIdx.getValue
()] << "\n"; } } while (false)
;
1468 OutputMappings.insert(std::make_pair(LI, Orig));
1469 }
1470}
1471
1472bool IROutliner::extractSection(OutlinableRegion &Region) {
1473 SetVector<Value *> ArgInputs, Outputs, SinkCands;
1474 Region.CE->findInputsOutputs(ArgInputs, Outputs, SinkCands);
1475
1476 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1476, __PRETTY_FUNCTION__))
;
1477 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1477, __PRETTY_FUNCTION__))
;
1478 Function *OrigF = Region.StartBB->getParent();
1479 CodeExtractorAnalysisCache CEAC(*OrigF);
1480 Region.ExtractedFunction = Region.CE->extractCodeRegion(CEAC);
1481
1482 // If the extraction was successful, find the BasicBlock, and reassign the
1483 // OutlinableRegion blocks
1484 if (!Region.ExtractedFunction) {
1485 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)
1486 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("iroutliner")) { dbgs() << "CodeExtractor failed to outline "
<< Region.StartBB << "\n"; } } while (false)
;
1487 Region.reattachCandidate();
1488 return false;
1489 }
1490
1491 BasicBlock *RewrittenBB = Region.FollowBB->getSinglePredecessor();
1492 Region.StartBB = RewrittenBB;
1493 Region.EndBB = RewrittenBB;
1494
1495 // The sequences of outlinable regions has now changed. We must fix the
1496 // IRInstructionDataList for consistency. Although they may not be illegal
1497 // instructions, they should not be compared with anything else as they
1498 // should not be outlined in this round. So marking these as illegal is
1499 // allowed.
1500 IRInstructionDataList *IDL = Region.Candidate->front()->IDL;
1501 Instruction *BeginRewritten = &*RewrittenBB->begin();
1502 Instruction *EndRewritten = &*RewrittenBB->begin();
1503 Region.NewFront = new (InstDataAllocator.Allocate()) IRInstructionData(
1504 *BeginRewritten, InstructionClassifier.visit(*BeginRewritten), *IDL);
1505 Region.NewBack = new (InstDataAllocator.Allocate()) IRInstructionData(
1506 *EndRewritten, InstructionClassifier.visit(*EndRewritten), *IDL);
1507
1508 // Insert the first IRInstructionData of the new region in front of the
1509 // first IRInstructionData of the IRSimilarityCandidate.
1510 IDL->insert(Region.Candidate->begin(), *Region.NewFront);
1511 // Insert the first IRInstructionData of the new region after the
1512 // last IRInstructionData of the IRSimilarityCandidate.
1513 IDL->insert(Region.Candidate->end(), *Region.NewBack);
1514 // Remove the IRInstructionData from the IRSimilarityCandidate.
1515 IDL->erase(Region.Candidate->begin(), std::prev(Region.Candidate->end()));
1516
1517 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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1518, __PRETTY_FUNCTION__))
1518 "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-12~++20210125100614+2cdb34efdac5/llvm/lib/Transforms/IPO/IROutliner.cpp"
, 1518, __PRETTY_FUNCTION__))
;
1519
1520 // Iterate over the new set of instructions to find the new call
1521 // instruction.
1522 for (Instruction &I : *RewrittenBB)
1523 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1524 if (Region.ExtractedFunction == CI->getCalledFunction())
1525 Region.Call = CI;
1526 } else if (LoadInst *LI = dyn_cast<LoadInst>(&I))
1527 updateOutputMapping(Region, Outputs.getArrayRef(), LI);
1528 Region.reattachCandidate();
1529 return true;
1530}
1531
1532unsigned IROutliner::doOutline(Module &M) {
1533 // Find the possible similarity sections.
1534 IRSimilarityIdentifier &Identifier = getIRSI(M);
1535 SimilarityGroupList &SimilarityCandidates = *Identifier.getSimilarity();
1536
1537 // Sort them by size of extracted sections
1538 unsigned OutlinedFunctionNum = 0;
1539 // If we only have one SimilarityGroup in SimilarityCandidates, we do not have
1540 // to sort them by the potential number of instructions to be outlined
1541 if (SimilarityCandidates.size() > 1)
1542 llvm::stable_sort(SimilarityCandidates,
1543 [](const std::vector<IRSimilarityCandidate> &LHS,
1544 const std::vector<IRSimilarityCandidate> &RHS) {
1545 return LHS[0].getLength() * LHS.size() >
1546 RHS[0].getLength() * RHS.size();
1547 });
1548
1549 DenseSet<unsigned> NotSame;
1550 std::vector<Function *> FuncsToRemove;
1551 // Iterate over the possible sets of similarity.
1552 for (SimilarityGroup &CandidateVec : SimilarityCandidates) {
1553 OutlinableGroup CurrentGroup;
1554
1555 // Remove entries that were previously outlined
1556 pruneIncompatibleRegions(CandidateVec, CurrentGroup);
1557
1558 // We pruned the number of regions to 0 to 1, meaning that it's not worth
1559 // trying to outlined since there is no compatible similar instance of this
1560 // code.
1561 if (CurrentGroup.Regions.size() < 2)
1562 continue;
1563
1564 // Determine if there are any values that are the same constant throughout
1565 // each section in the set.
1566 NotSame.clear();
1567 CurrentGroup.findSameConstants(NotSame);
1568
1569 if (CurrentGroup.IgnoreGroup)
1570 continue;
1571
1572 // Create a CodeExtractor for each outlinable region. Identify inputs and
1573 // outputs for each section using the code extractor and create the argument
1574 // types for the Aggregate Outlining Function.
1575 std::vector<OutlinableRegion *> OutlinedRegions;
1576 for (OutlinableRegion *OS : CurrentGroup.Regions) {
1577 // Break the outlinable region out of its parent BasicBlock into its own
1578 // BasicBlocks (see function implementation).
1579 OS->splitCandidate();
1580 std::vector<BasicBlock *> BE = {OS->StartBB};
1581 OS->CE = new (ExtractorAllocator.Allocate())
1582 CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,
1583 false, "outlined");
1584 findAddInputsOutputs(M, *OS, NotSame);
1585 if (!OS->IgnoreRegion)
1586 OutlinedRegions.push_back(OS);
1587 else
1588 OS->reattachCandidate();
1589 }
1590
1591 CurrentGroup.Regions = std::move(OutlinedRegions);
1592
1593 if (CurrentGroup.Regions.empty())
1594 continue;
1595
1596 CurrentGroup.collectGVNStoreSets(M);
1597
1598 if (CostModel)
1599 findCostBenefit(M, CurrentGroup);
1600
1601 // If we are adhering to the cost model, reattach all the candidates
1602 if (CurrentGroup.Cost >= CurrentGroup.Benefit && CostModel) {
1603 for (OutlinableRegion *OS : CurrentGroup.Regions)
1604 OS->reattachCandidate();
1605 OptimizationRemarkEmitter &ORE = getORE(
1606 *CurrentGroup.Regions[0]->Candidate->getFunction());
1607 ORE.emit([&]() {
1608 IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
1609 OptimizationRemarkMissed R(DEBUG_TYPE"iroutliner", "WouldNotDecreaseSize",
1610 C->frontInstruction());
1611 R << "did not outline "
1612 << ore::NV(std::to_string(CurrentGroup.Regions.size()))
1613 << " regions due to estimated increase of "
1614 << ore::NV("InstructionIncrease",
1615 CurrentGroup.Cost - CurrentGroup.Benefit)
1616 << " instructions at locations ";
1617 interleave(
1618 CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
1619 [&R](OutlinableRegion *Region) {
1620 R << ore::NV(
1621 "DebugLoc",
1622 Region->Candidate->frontInstruction()->getDebugLoc());
1623 },
1624 [&R]() { R << " "; });
1625 return R;
1626 });
1627 continue;
1628 }
1629
1630 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)
1631 << " 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)
;
1632
1633 // Create functions out of all the sections, and mark them as outlined.
1634 OutlinedRegions.clear();
1635 for (OutlinableRegion *OS : CurrentGroup.Regions) {
1636 bool FunctionOutlined = extractSection(*OS);
1637 if (FunctionOutlined) {
1638 unsigned StartIdx = OS->Candidate->getStartIdx();
1639 unsigned EndIdx = OS->Candidate->getEndIdx();
1640 for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)
1641 Outlined.insert(Idx);
1642
1643 OutlinedRegions.push_back(OS);
1644 }
1645 }
1646
1647 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)
1648 << " 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)
1649 << " 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)
;
1650
1651 CurrentGroup.Regions = std::move(OutlinedRegions);
1652
1653 if (CurrentGroup.Regions.empty())
1654 continue;
1655
1656 OptimizationRemarkEmitter &ORE =
1657 getORE(*CurrentGroup.Regions[0]->Call->getFunction());
1658 ORE.emit([&]() {
1659 IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;
1660 OptimizationRemark R(DEBUG_TYPE"iroutliner", "Outlined", C->front()->Inst);
1661 R << "outlined " << ore::NV(std::to_string(CurrentGroup.Regions.size()))
1662 << " regions with decrease of "
1663 << ore::NV("Benefit", CurrentGroup.Benefit - CurrentGroup.Cost)
1664 << " instructions at locations ";
1665 interleave(
1666 CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),
1667 [&R](OutlinableRegion *Region) {
1668 R << ore::NV("DebugLoc",
1669 Region->Candidate->frontInstruction()->getDebugLoc());
1670 },
1671 [&R]() { R << " "; });
1672 return R;
1673 });
1674
1675 deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,
1676 OutlinedFunctionNum);
1677 }
1678
1679 for (Function *F : FuncsToRemove)
1680 F->eraseFromParent();
1681
1682 return OutlinedFunctionNum;
1683}
1684
1685bool IROutliner::run(Module &M) {
1686 CostModel = !NoCostModel;
1687 OutlineFromLinkODRs = EnableLinkOnceODRIROutlining;
1688
1689 return doOutline(M) > 0;
1690}
1691
1692// Pass Manager Boilerplate
1693class IROutlinerLegacyPass : public ModulePass {
1694public:
1695 static char ID;
1696 IROutlinerLegacyPass() : ModulePass(ID) {
1697 initializeIROutlinerLegacyPassPass(*PassRegistry::getPassRegistry());
1698 }
1699
1700 void getAnalysisUsage(AnalysisUsage &AU) const override {
1701 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
1702 AU.addRequired<TargetTransformInfoWrapperPass>();
1703 AU.addRequired<IRSimilarityIdentifierWrapperPass>();
1704 }
1705
1706 bool runOnModule(Module &M) override;
1707};
1708
1709bool IROutlinerLegacyPass::runOnModule(Module &M) {
1710 if (skipModule(M))
1711 return false;
1712
1713 std::unique_ptr<OptimizationRemarkEmitter> ORE;
1714 auto GORE = [&ORE](Function &F) -> OptimizationRemarkEmitter & {
1715 ORE.reset(new OptimizationRemarkEmitter(&F));
1716 return *ORE.get();
1717 };
1718
1719 auto GTTI = [this](Function &F) -> TargetTransformInfo & {
1720 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1721 };
1722
1723 auto GIRSI = [this](Module &) -> IRSimilarityIdentifier & {
1724 return this->getAnalysis<IRSimilarityIdentifierWrapperPass>().getIRSI();
1725 };
1726
1727 return IROutliner(GTTI, GIRSI, GORE).run(M);
1728}
1729
1730PreservedAnalyses IROutlinerPass::run(Module &M, ModuleAnalysisManager &AM) {
1731 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1732
1733 std::function<TargetTransformInfo &(Function &)> GTTI =
1734 [&FAM](Function &F) -> TargetTransformInfo & {
1735 return FAM.getResult<TargetIRAnalysis>(F);
1736 };
1737
1738 std::function<IRSimilarityIdentifier &(Module &)> GIRSI =
1739 [&AM](Module &M) -> IRSimilarityIdentifier & {
1740 return AM.getResult<IRSimilarityAnalysis>(M);
1741 };
1742
1743 std::unique_ptr<OptimizationRemarkEmitter> ORE;
1744 std::function<OptimizationRemarkEmitter &(Function &)> GORE =
1745 [&ORE](Function &F) -> OptimizationRemarkEmitter & {
1746 ORE.reset(new OptimizationRemarkEmitter(&F));
1747 return *ORE.get();
1748 };
1749
1750 if (IROutliner(GTTI, GIRSI, GORE).run(M))
1751 return PreservedAnalyses::none();
1752 return PreservedAnalyses::all();
1753}
1754
1755char IROutlinerLegacyPass::ID = 0;
1756INITIALIZE_PASS_BEGIN(IROutlinerLegacyPass, "iroutliner", "IR Outliner", false,static void *initializeIROutlinerLegacyPassPassOnce(PassRegistry
&Registry) {
1757 false)static void *initializeIROutlinerLegacyPassPassOnce(PassRegistry
&Registry) {
1758INITIALIZE_PASS_DEPENDENCY(IRSimilarityIdentifierWrapperPass)initializeIRSimilarityIdentifierWrapperPassPass(Registry);
1759INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
1760INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
1761INITIALIZE_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))
; }
1762 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))
; }
1763
1764ModulePass *llvm::createIROutlinerPass() { return new IROutlinerLegacyPass(); }