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