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