| 1 | //===---- MachineOutliner.cpp - Outline instructions -----------*- 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 | /// Replaces repeated sequences of instructions with function calls. |
| 11 | /// |
| 12 | /// This works by placing every instruction from every basic block in a |
| 13 | /// suffix tree, and repeatedly querying that tree for repeated sequences of |
| 14 | /// instructions. If a sequence of instructions appears often, then it ought |
| 15 | /// to be beneficial to pull out into a function. |
| 16 | /// |
| 17 | /// The MachineOutliner communicates with a given target using hooks defined in |
| 18 | /// TargetInstrInfo.h. The target supplies the outliner with information on how |
| 19 | /// a specific sequence of instructions should be outlined. This information |
| 20 | /// is used to deduce the number of instructions necessary to |
| 21 | /// |
| 22 | /// * Create an outlined function |
| 23 | /// * Call that outlined function |
| 24 | /// |
| 25 | /// Targets must implement |
| 26 | /// * getOutliningCandidateInfo |
| 27 | /// * buildOutlinedFrame |
| 28 | /// * insertOutlinedCall |
| 29 | /// * isFunctionSafeToOutlineFrom |
| 30 | /// |
| 31 | /// in order to make use of the MachineOutliner. |
| 32 | /// |
| 33 | /// This was originally presented at the 2016 LLVM Developers' Meeting in the |
| 34 | /// talk "Reducing Code Size Using Outlining". For a high-level overview of |
| 35 | /// how this pass works, the talk is available on YouTube at |
| 36 | /// |
| 37 | /// https://www.youtube.com/watch?v=yorld-WSOeU |
| 38 | /// |
| 39 | /// The slides for the talk are available at |
| 40 | /// |
| 41 | /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf |
| 42 | /// |
| 43 | /// The talk provides an overview of how the outliner finds candidates and |
| 44 | /// ultimately outlines them. It describes how the main data structure for this |
| 45 | /// pass, the suffix tree, is queried and purged for candidates. It also gives |
| 46 | /// a simplified suffix tree construction algorithm for suffix trees based off |
| 47 | /// of the algorithm actually used here, Ukkonen's algorithm. |
| 48 | /// |
| 49 | /// For the original RFC for this pass, please see |
| 50 | /// |
| 51 | /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html |
| 52 | /// |
| 53 | /// For more information on the suffix tree data structure, please see |
| 54 | /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf |
| 55 | /// |
| 56 | //===----------------------------------------------------------------------===// |
| 57 | #include "llvm/CodeGen/MachineOutliner.h" |
| 58 | #include "CodeGenOptions.h" |
| 59 | #include "llvm/ADT/BitVector.h" |
| 60 | #include "llvm/ADT/DenseMap.h" |
| 61 | #include "llvm/ADT/SmallSet.h" |
| 62 | #include "llvm/ADT/Statistic.h" |
| 63 | #include "llvm/ADT/Twine.h" |
| 64 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
| 65 | #include "llvm/Analysis/ModuleSummaryAnalysis.h" |
| 66 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
| 67 | #include "llvm/Analysis/ProfileSummaryInfo.h" |
| 68 | #include "llvm/CGData/CodeGenDataReader.h" |
| 69 | #include "llvm/CodeGen/LivePhysRegs.h" |
| 70 | #include "llvm/CodeGen/MachineInstrBundle.h" |
| 71 | #include "llvm/CodeGen/MachineModuleInfo.h" |
| 72 | #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" |
| 73 | #include "llvm/CodeGen/Passes.h" |
| 74 | #include "llvm/CodeGen/TargetInstrInfo.h" |
| 75 | #include "llvm/CodeGen/TargetPassConfig.h" |
| 76 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
| 77 | #include "llvm/IR/DIBuilder.h" |
| 78 | #include "llvm/IR/IRBuilder.h" |
| 79 | #include "llvm/IR/Mangler.h" |
| 80 | #include "llvm/IR/Module.h" |
| 81 | #include "llvm/InitializePasses.h" |
| 82 | #include "llvm/Support/Debug.h" |
| 83 | #include "llvm/Support/SuffixTree.h" |
| 84 | #include "llvm/Support/raw_ostream.h" |
| 85 | #include "llvm/Target/TargetMachine.h" |
| 86 | #include "llvm/Transforms/Utils/ModuleUtils.h" |
| 87 | #include <tuple> |
| 88 | #include <vector> |
| 89 | |
| 90 | #define DEBUG_TYPE "machine-outliner" |
| 91 | |
| 92 | using namespace llvm; |
| 93 | using namespace ore; |
| 94 | using namespace outliner; |
| 95 | |
| 96 | // Statistics for outlined functions. |
| 97 | STATISTIC(NumOutlined, "Number of candidates outlined" ); |
| 98 | STATISTIC(FunctionsCreated, "Number of functions created" ); |
| 99 | |
| 100 | // Statistics for instruction mapping. |
| 101 | STATISTIC(NumLegalInUnsignedVec, "Outlinable instructions mapped" ); |
| 102 | STATISTIC(NumIllegalInUnsignedVec, |
| 103 | "Unoutlinable instructions mapped + number of sentinel values" ); |
| 104 | STATISTIC(NumSentinels, "Sentinel values inserted during mapping" ); |
| 105 | STATISTIC(NumInvisible, |
| 106 | "Non-debug invisible instructions skipped during mapping" ); |
| 107 | STATISTIC(UnsignedVecSize, |
| 108 | "Total number of instructions mapped and saved to mapping vector" ); |
| 109 | STATISTIC(StableHashAttempts, |
| 110 | "Count of hashing attempts made for outlined functions" ); |
| 111 | STATISTIC(StableHashDropped, |
| 112 | "Count of unsuccessful hashing attempts for outlined functions" ); |
| 113 | STATISTIC(UnprofitableCandidateGroupsPublished, |
| 114 | "Number of locally unprofitable candidate groups published" ); |
| 115 | STATISTIC(UnprofitableCandidateSitesPublished, |
| 116 | "Number of locally unprofitable candidate sites published" ); |
| 117 | STATISTIC(NumRemovedLOHs, "Total number of Linker Optimization Hints removed" ); |
| 118 | STATISTIC(NumPGOBlockedOutlined, |
| 119 | "Number of times outlining was blocked by PGO" ); |
| 120 | STATISTIC(NumPGOAllowedCold, |
| 121 | "Number of times outlining was allowed from cold functions" ); |
| 122 | STATISTIC(NumPGOConservativeBlockedOutlined, |
| 123 | "Number of times outlining was blocked conservatively when profile " |
| 124 | "counts were missing" ); |
| 125 | STATISTIC(NumPGOOptimisticOutlined, |
| 126 | "Number of times outlining was allowed optimistically when profile " |
| 127 | "counts were missing" ); |
| 128 | |
| 129 | namespace { |
| 130 | |
| 131 | /// Maps \p MachineInstrs to unsigned integers and stores the mappings. |
| 132 | struct InstructionMapper { |
| 133 | const MachineModuleInfo &MMI; |
| 134 | |
| 135 | /// The next available integer to assign to a \p MachineInstr that |
| 136 | /// cannot be outlined. |
| 137 | /// |
| 138 | /// Set to -3 for compatability with \p DenseMapInfo<unsigned>. |
| 139 | unsigned IllegalInstrNumber = -3; |
| 140 | |
| 141 | /// The next available integer to assign to a \p MachineInstr that can |
| 142 | /// be outlined. |
| 143 | unsigned LegalInstrNumber = 0; |
| 144 | |
| 145 | /// Correspondence from \p MachineInstrs to unsigned integers. |
| 146 | DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait> |
| 147 | InstructionIntegerMap; |
| 148 | |
| 149 | /// Correspondence between \p MachineBasicBlocks and target-defined flags. |
| 150 | DenseMap<MachineBasicBlock *, unsigned> MBBFlagsMap; |
| 151 | |
| 152 | /// The vector of unsigned integers that the module is mapped to. |
| 153 | SmallVector<unsigned> UnsignedVec; |
| 154 | |
| 155 | /// Stores the location of the instruction associated with the integer |
| 156 | /// at index i in \p UnsignedVec for each index i. |
| 157 | SmallVector<MachineBasicBlock::iterator> InstrList; |
| 158 | |
| 159 | // Set if we added an illegal number in the previous step. |
| 160 | // Since each illegal number is unique, we only need one of them between |
| 161 | // each range of legal numbers. This lets us make sure we don't add more |
| 162 | // than one illegal number per range. |
| 163 | bool AddedIllegalLastTime = false; |
| 164 | |
| 165 | /// Maps \p *It to a legal integer. |
| 166 | /// |
| 167 | /// Updates \p CanOutlineWithPrevInstr, \p HaveLegalRange, \p InstrListForMBB, |
| 168 | /// \p UnsignedVecForMBB, \p InstructionIntegerMap, and \p LegalInstrNumber. |
| 169 | /// |
| 170 | /// \returns The integer that \p *It was mapped to. |
| 171 | unsigned mapToLegalUnsigned( |
| 172 | MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr, |
| 173 | bool &HaveLegalRange, unsigned &NumLegalInBlock, |
| 174 | SmallVector<unsigned> &UnsignedVecForMBB, |
| 175 | SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) { |
| 176 | // We added something legal, so we should unset the AddedLegalLastTime |
| 177 | // flag. |
| 178 | AddedIllegalLastTime = false; |
| 179 | |
| 180 | // If we have at least two adjacent legal instructions (which may have |
| 181 | // invisible instructions in between), remember that. |
| 182 | if (CanOutlineWithPrevInstr) |
| 183 | HaveLegalRange = true; |
| 184 | CanOutlineWithPrevInstr = true; |
| 185 | |
| 186 | // Keep track of the number of legal instructions we insert. |
| 187 | NumLegalInBlock++; |
| 188 | |
| 189 | // Get the integer for this instruction or give it the current |
| 190 | // LegalInstrNumber. |
| 191 | InstrListForMBB.push_back(Elt: It); |
| 192 | MachineInstr &MI = *It; |
| 193 | bool WasInserted; |
| 194 | DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator |
| 195 | ResultIt; |
| 196 | std::tie(args&: ResultIt, args&: WasInserted) = |
| 197 | InstructionIntegerMap.insert(KV: std::make_pair(x: &MI, y&: LegalInstrNumber)); |
| 198 | unsigned MINumber = ResultIt->second; |
| 199 | |
| 200 | // There was an insertion. |
| 201 | if (WasInserted) |
| 202 | LegalInstrNumber++; |
| 203 | |
| 204 | UnsignedVecForMBB.push_back(Elt: MINumber); |
| 205 | |
| 206 | // Make sure we don't overflow or use any integers reserved by the DenseMap. |
| 207 | if (LegalInstrNumber >= IllegalInstrNumber) |
| 208 | report_fatal_error(reason: "Instruction mapping overflow!" ); |
| 209 | |
| 210 | // Statistics. |
| 211 | ++NumLegalInUnsignedVec; |
| 212 | return MINumber; |
| 213 | } |
| 214 | |
| 215 | /// Maps \p *It to an illegal integer. |
| 216 | /// |
| 217 | /// Updates \p InstrListForMBB, \p UnsignedVecForMBB, and \p |
| 218 | /// IllegalInstrNumber. |
| 219 | /// |
| 220 | /// \returns The integer that \p *It was mapped to. |
| 221 | unsigned mapToIllegalUnsigned( |
| 222 | MachineBasicBlock::iterator &It, bool &CanOutlineWithPrevInstr, |
| 223 | SmallVector<unsigned> &UnsignedVecForMBB, |
| 224 | SmallVector<MachineBasicBlock::iterator> &InstrListForMBB) { |
| 225 | // Can't outline an illegal instruction. Set the flag. |
| 226 | CanOutlineWithPrevInstr = false; |
| 227 | |
| 228 | // Only add one illegal number per range of legal numbers. |
| 229 | if (AddedIllegalLastTime) |
| 230 | return IllegalInstrNumber; |
| 231 | |
| 232 | // Remember that we added an illegal number last time. |
| 233 | AddedIllegalLastTime = true; |
| 234 | unsigned MINumber = IllegalInstrNumber; |
| 235 | |
| 236 | InstrListForMBB.push_back(Elt: It); |
| 237 | UnsignedVecForMBB.push_back(Elt: IllegalInstrNumber); |
| 238 | IllegalInstrNumber--; |
| 239 | // Statistics. |
| 240 | ++NumIllegalInUnsignedVec; |
| 241 | |
| 242 | assert(LegalInstrNumber < IllegalInstrNumber && |
| 243 | "Instruction mapping overflow!" ); |
| 244 | |
| 245 | return MINumber; |
| 246 | } |
| 247 | |
| 248 | /// Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds |
| 249 | /// and appends it to \p UnsignedVec and \p InstrList. |
| 250 | /// |
| 251 | /// Two instructions are assigned the same integer if they are identical. |
| 252 | /// If an instruction is deemed unsafe to outline, then it will be assigned an |
| 253 | /// unique integer. The resulting mapping is placed into a suffix tree and |
| 254 | /// queried for candidates. |
| 255 | /// |
| 256 | /// \param MBB The \p MachineBasicBlock to be translated into integers. |
| 257 | /// \param TII \p TargetInstrInfo for the function. |
| 258 | void convertToUnsignedVec(MachineBasicBlock &MBB, |
| 259 | const TargetInstrInfo &TII) { |
| 260 | LLVM_DEBUG(dbgs() << "*** Converting MBB '" << MBB.getName() |
| 261 | << "' to unsigned vector ***\n" ); |
| 262 | unsigned Flags = 0; |
| 263 | |
| 264 | // Don't even map in this case. |
| 265 | if (!TII.isMBBSafeToOutlineFrom(MBB, Flags)) |
| 266 | return; |
| 267 | |
| 268 | auto OutlinableRanges = TII.getOutlinableRanges(MBB, Flags); |
| 269 | LLVM_DEBUG(dbgs() << MBB.getName() << ": " << OutlinableRanges.size() |
| 270 | << " outlinable range(s)\n" ); |
| 271 | if (OutlinableRanges.empty()) |
| 272 | return; |
| 273 | |
| 274 | // Store info for the MBB for later outlining. |
| 275 | MBBFlagsMap[&MBB] = Flags; |
| 276 | |
| 277 | MachineBasicBlock::iterator It = MBB.begin(); |
| 278 | |
| 279 | // The number of instructions in this block that will be considered for |
| 280 | // outlining. |
| 281 | unsigned NumLegalInBlock = 0; |
| 282 | |
| 283 | // True if we have at least two legal instructions which aren't separated |
| 284 | // by an illegal instruction. |
| 285 | bool HaveLegalRange = false; |
| 286 | |
| 287 | // True if we can perform outlining given the last mapped (non-invisible) |
| 288 | // instruction. This lets us know if we have a legal range. |
| 289 | bool CanOutlineWithPrevInstr = false; |
| 290 | |
| 291 | // FIXME: Should this all just be handled in the target, rather than using |
| 292 | // repeated calls to getOutliningType? |
| 293 | SmallVector<unsigned> UnsignedVecForMBB; |
| 294 | SmallVector<MachineBasicBlock::iterator> InstrListForMBB; |
| 295 | |
| 296 | LLVM_DEBUG(dbgs() << "*** Mapping outlinable ranges ***\n" ); |
| 297 | for (auto &OutlinableRange : OutlinableRanges) { |
| 298 | auto OutlinableRangeBegin = OutlinableRange.first; |
| 299 | auto OutlinableRangeEnd = OutlinableRange.second; |
| 300 | #ifndef NDEBUG |
| 301 | LLVM_DEBUG( |
| 302 | dbgs() << "Mapping " |
| 303 | << std::distance(OutlinableRangeBegin, OutlinableRangeEnd) |
| 304 | << " instruction range\n" ); |
| 305 | // Everything outside of an outlinable range is illegal. |
| 306 | unsigned NumSkippedInRange = 0; |
| 307 | #endif |
| 308 | for (; It != OutlinableRangeBegin; ++It) { |
| 309 | if (It->isDebugInstr()) |
| 310 | continue; |
| 311 | #ifndef NDEBUG |
| 312 | ++NumSkippedInRange; |
| 313 | #endif |
| 314 | mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
| 315 | InstrListForMBB); |
| 316 | } |
| 317 | #ifndef NDEBUG |
| 318 | LLVM_DEBUG(dbgs() << "Skipped " << NumSkippedInRange |
| 319 | << " instructions outside outlinable range\n" ); |
| 320 | #endif |
| 321 | assert(It != MBB.end() && "Should still have instructions?" ); |
| 322 | // `It` is now positioned at the beginning of a range of instructions |
| 323 | // which may be outlinable. Check if each instruction is known to be safe. |
| 324 | for (; It != OutlinableRangeEnd; ++It) { |
| 325 | if (It->isDebugInstr()) |
| 326 | continue; |
| 327 | // Keep track of where this instruction is in the module. |
| 328 | switch (TII.getOutliningType(MMI, MIT&: It, Flags)) { |
| 329 | case InstrType::Illegal: |
| 330 | mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
| 331 | InstrListForMBB); |
| 332 | break; |
| 333 | |
| 334 | case InstrType::Legal: |
| 335 | mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, |
| 336 | NumLegalInBlock, UnsignedVecForMBB, |
| 337 | InstrListForMBB); |
| 338 | break; |
| 339 | |
| 340 | case InstrType::LegalTerminator: |
| 341 | mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange, |
| 342 | NumLegalInBlock, UnsignedVecForMBB, |
| 343 | InstrListForMBB); |
| 344 | // The instruction also acts as a terminator, so we have to record |
| 345 | // that in the string. |
| 346 | mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
| 347 | InstrListForMBB); |
| 348 | break; |
| 349 | |
| 350 | case InstrType::Invisible: |
| 351 | // Normally this is set by mapTo(Blah)Unsigned, but we just want to |
| 352 | // skip this instruction. So, unset the flag here. |
| 353 | ++NumInvisible; |
| 354 | AddedIllegalLastTime = false; |
| 355 | break; |
| 356 | } |
| 357 | } |
| 358 | } |
| 359 | |
| 360 | LLVM_DEBUG(dbgs() << "HaveLegalRange = " << HaveLegalRange << "\n" ); |
| 361 | |
| 362 | // Are there enough legal instructions in the block for outlining to be |
| 363 | // possible? |
| 364 | if (HaveLegalRange) { |
| 365 | // After we're done every insertion, uniquely terminate this part of the |
| 366 | // "string". This makes sure we won't match across basic block or function |
| 367 | // boundaries since the "end" is encoded uniquely and thus appears in no |
| 368 | // repeated substring. |
| 369 | mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB, |
| 370 | InstrListForMBB); |
| 371 | ++NumSentinels; |
| 372 | append_range(C&: InstrList, R&: InstrListForMBB); |
| 373 | append_range(C&: UnsignedVec, R&: UnsignedVecForMBB); |
| 374 | } |
| 375 | } |
| 376 | |
| 377 | InstructionMapper(const MachineModuleInfo &MMI_) : MMI(MMI_) {} |
| 378 | }; |
| 379 | |
| 380 | /// An interprocedural pass which finds repeated sequences of |
| 381 | /// instructions and replaces them with calls to functions. |
| 382 | /// |
| 383 | /// Each instruction is mapped to an unsigned integer and placed in a string. |
| 384 | /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree |
| 385 | /// is then repeatedly queried for repeated sequences of instructions. Each |
| 386 | /// non-overlapping repeated sequence is then placed in its own |
| 387 | /// \p MachineFunction and each instance is then replaced with a call to that |
| 388 | /// function. |
| 389 | struct MachineOutliner : public ModulePass { |
| 390 | |
| 391 | static char ID; |
| 392 | |
| 393 | const CodeGenOptions *Opts = nullptr; |
| 394 | MachineModuleInfo *MMI = nullptr; |
| 395 | const TargetMachine *TM = nullptr; |
| 396 | |
| 397 | /// Set to true if the outliner should consider functions with |
| 398 | /// linkonceodr linkage. |
| 399 | bool OutlineFromLinkOnceODRs = false; |
| 400 | |
| 401 | /// The current repeat number of machine outlining. |
| 402 | unsigned OutlineRepeatedNum = 0; |
| 403 | |
| 404 | /// The mode for whether to run the outliner |
| 405 | /// Set to always-outline by default for compatibility with llc's -run-pass |
| 406 | /// option. |
| 407 | RunOutliner RunOutlinerMode = RunOutliner::AlwaysOutline; |
| 408 | |
| 409 | /// This is a compact representation of hash sequences of outlined functions. |
| 410 | /// It is used when OutlinerMode = CGDataMode::Write. |
| 411 | /// The resulting hash tree will be emitted into __llvm_outlined section |
| 412 | /// which will be dead-stripped not going to the final binary. |
| 413 | /// A post-process using llvm-cgdata, lld, or ThinLTO can merge them into |
| 414 | /// a global oulined hash tree for the subsequent codegen. |
| 415 | std::unique_ptr<OutlinedHashTree> LocalHashTree; |
| 416 | |
| 417 | /// The mode of the outliner. |
| 418 | /// When is's CGDataMode::None, candidates are populated with the suffix tree |
| 419 | /// within a module and outlined. |
| 420 | /// When it's CGDataMode::Write, in addition to CGDataMode::None, the hash |
| 421 | /// sequences of outlined functions are published into LocalHashTree. |
| 422 | /// When it's CGDataMode::Read, candidates are populated with the global |
| 423 | /// outlined hash tree that has been built by the previous codegen. |
| 424 | CGDataMode OutlinerMode = CGDataMode::None; |
| 425 | |
| 426 | /// Distinct locally unprofitable sequences discovered across all iterations. |
| 427 | /// Keep hashes rather than candidates, whose instruction iterators can be |
| 428 | /// invalidated by outlining. Their surviving sites are recounted at the end. |
| 429 | SmallVector<SmallVector<stable_hash>> UnprofitableCandidates; |
| 430 | // Terminals store one-based indices into UnprofitableCandidates. |
| 431 | OutlinedHashTree UnprofitableCandidateHashTree; |
| 432 | |
| 433 | StringRef getPassName() const override { return "Machine Outliner" ; } |
| 434 | |
| 435 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 436 | AU.addRequired<MachineModuleInfoWrapperPass>(); |
| 437 | AU.addRequired<TargetPassConfig>(); |
| 438 | AU.addPreserved<MachineModuleInfoWrapperPass>(); |
| 439 | AU.addUsedIfAvailable<ImmutableModuleSummaryIndexWrapperPass>(); |
| 440 | if (RunOutlinerMode == RunOutliner::OptimisticPGO || |
| 441 | RunOutlinerMode == RunOutliner::ConservativePGO) { |
| 442 | AU.addRequired<BlockFrequencyInfoWrapperPass>(); |
| 443 | AU.addRequired<ProfileSummaryInfoWrapperPass>(); |
| 444 | } |
| 445 | AU.setPreservesAll(); |
| 446 | ModulePass::getAnalysisUsage(AU); |
| 447 | } |
| 448 | |
| 449 | MachineOutliner() : ModulePass(ID) {} |
| 450 | |
| 451 | /// Remark output explaining that not outlining a set of candidates would be |
| 452 | /// better than outlining that set. |
| 453 | void emitNotOutliningCheaperRemark( |
| 454 | unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq, |
| 455 | OutlinedFunction &OF); |
| 456 | |
| 457 | /// Run the outlining cost model for a group of candidates and append the |
| 458 | /// resulting outlined function if it is profitable. |
| 459 | void createOutlinedFunctionIfBeneficial( |
| 460 | std::vector<Candidate> &Candidates, unsigned StringLen, |
| 461 | unsigned MinRepeats, const TargetInstrInfo &TII, |
| 462 | std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList); |
| 463 | |
| 464 | /// Remark output explaining that a function was outlined. |
| 465 | void emitOutlinedFunctionRemark(OutlinedFunction &OF); |
| 466 | |
| 467 | /// Find all repeated substrings that satisfy the outlining cost model by |
| 468 | /// constructing a suffix tree. |
| 469 | /// |
| 470 | /// If a substring appears at least twice, then it must be represented by |
| 471 | /// an internal node which appears in at least two suffixes. Each suffix |
| 472 | /// is represented by a leaf node. To do this, we visit each internal node |
| 473 | /// in the tree, using the leaf children of each internal node. If an |
| 474 | /// internal node represents a beneficial substring, then we use each of |
| 475 | /// its leaf children to find the locations of its substring. |
| 476 | /// |
| 477 | /// \param Mapper Contains outlining mapping information. |
| 478 | /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions |
| 479 | /// each type of candidate. |
| 480 | void |
| 481 | findCandidates(InstructionMapper &Mapper, |
| 482 | std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList); |
| 483 | |
| 484 | /// Find all repeated substrings that match in the global outlined hash |
| 485 | /// tree built from the previous codegen. |
| 486 | /// |
| 487 | /// \param Mapper Contains outlining mapping information. |
| 488 | /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions |
| 489 | /// each type of candidate. |
| 490 | void findGlobalCandidates( |
| 491 | InstructionMapper &Mapper, |
| 492 | std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList); |
| 493 | |
| 494 | /// Replace the sequences of instructions represented by \p OutlinedFunctions |
| 495 | /// with calls to functions. |
| 496 | /// |
| 497 | /// \param M The module we are outlining from. |
| 498 | /// \param FunctionList A list of functions to be inserted into the module. |
| 499 | /// \param Mapper Contains the instruction mappings for the module. |
| 500 | /// \param[out] OutlinedFunctionNum The outlined function number. |
| 501 | bool outline(Module &M, |
| 502 | std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList, |
| 503 | InstructionMapper &Mapper, unsigned &OutlinedFunctionNum); |
| 504 | |
| 505 | /// Creates a function for \p OF and inserts it into the module. |
| 506 | MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF, |
| 507 | InstructionMapper &Mapper, |
| 508 | unsigned Name); |
| 509 | |
| 510 | /// Compute and publish the stable hash sequence of instructions in the |
| 511 | /// outlined function, \p MF. The parameter \p CandSize represents the number |
| 512 | /// of candidates that have identical instruction sequences to \p MF. |
| 513 | void computeAndPublishHashSequence(MachineFunction &MF, unsigned CandSize); |
| 514 | |
| 515 | /// Remember short sequences rejected by any iteration's profitability check. |
| 516 | void recordUnprofitableCandidate(OutlinedFunction &OF); |
| 517 | |
| 518 | /// Recount surviving sites in the final mapper and publish their counts. |
| 519 | bool publishUnprofitableCandidates(InstructionMapper &Mapper); |
| 520 | |
| 521 | /// Initialize the outliner mode. |
| 522 | void initializeOutlinerMode(const Module &M); |
| 523 | |
| 524 | /// Emit the outlined hash tree into __llvm_outline section. |
| 525 | void emitOutlinedHashTree(Module &M); |
| 526 | |
| 527 | /// Calls 'doOutline()' 1 + OutlinerReruns times. |
| 528 | bool runOnModule(Module &M) override; |
| 529 | |
| 530 | /// Construct a suffix tree on the instructions in \p M and outline repeated |
| 531 | /// strings from that tree. |
| 532 | /// \p Mapper is reset with this iteration's instruction mapping. |
| 533 | bool doOutline(Module &M, std::optional<InstructionMapper> &Mapper, |
| 534 | unsigned &OutlinedFunctionNum); |
| 535 | |
| 536 | /// Return a DISubprogram for OF if one exists, and null otherwise. Helper |
| 537 | /// function for remark emission. |
| 538 | DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) { |
| 539 | for (const Candidate &C : OF.Candidates) |
| 540 | if (MachineFunction *MF = C.getMF()) |
| 541 | if (DISubprogram *SP = MF->getFunction().getSubprogram()) |
| 542 | return SP; |
| 543 | return nullptr; |
| 544 | } |
| 545 | |
| 546 | /// Populate and \p InstructionMapper with instruction-to-integer mappings. |
| 547 | /// These are used to construct a suffix tree. |
| 548 | void populateMapper(InstructionMapper &Mapper, Module &M); |
| 549 | |
| 550 | /// Initialize information necessary to output a size remark. |
| 551 | /// FIXME: This should be handled by the pass manager, not the outliner. |
| 552 | /// FIXME: This is nearly identical to the initSizeRemarkInfo in the legacy |
| 553 | /// pass manager. |
| 554 | void initSizeRemarkInfo(const Module &M, |
| 555 | StringMap<unsigned> &FunctionToInstrCount); |
| 556 | |
| 557 | /// Emit the remark. |
| 558 | // FIXME: This should be handled by the pass manager, not the outliner. |
| 559 | void |
| 560 | emitInstrCountChangedRemark(const Module &M, |
| 561 | const StringMap<unsigned> &FunctionToInstrCount); |
| 562 | }; |
| 563 | } // Anonymous namespace. |
| 564 | |
| 565 | char MachineOutliner::ID = 0; |
| 566 | |
| 567 | ModulePass *llvm::createMachineOutlinerPass(RunOutliner RunOutlinerMode) { |
| 568 | MachineOutliner *OL = new MachineOutliner(); |
| 569 | OL->RunOutlinerMode = RunOutlinerMode; |
| 570 | return OL; |
| 571 | } |
| 572 | |
| 573 | INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner" , false, |
| 574 | false) |
| 575 | |
| 576 | void MachineOutliner::emitNotOutliningCheaperRemark( |
| 577 | unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq, |
| 578 | OutlinedFunction &OF) { |
| 579 | // FIXME: Right now, we arbitrarily choose some Candidate from the |
| 580 | // OutlinedFunction. This isn't necessarily fixed, nor does it have to be. |
| 581 | // We should probably sort these by function name or something to make sure |
| 582 | // the remarks are stable. |
| 583 | Candidate &C = CandidatesForRepeatedSeq.front(); |
| 584 | MachineOptimizationRemarkEmitter MORE(*(C.getMF()), nullptr); |
| 585 | MORE.emit(RemarkBuilder: [&]() { |
| 586 | MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper" , |
| 587 | C.front().getDebugLoc(), C.getMBB()); |
| 588 | R << "Did not outline " << NV("Length" , StringLen) << " instructions" |
| 589 | << " from " << NV("NumOccurrences" , CandidatesForRepeatedSeq.size()) |
| 590 | << " locations." |
| 591 | << " Bytes from outlining all occurrences (" |
| 592 | << NV("OutliningCost" , OF.getOutliningCost()) << ")" |
| 593 | << " >= Unoutlined instruction bytes (" |
| 594 | << NV("NotOutliningCost" , OF.getNotOutlinedCost()) << ")" |
| 595 | << " (Also found at: " ; |
| 596 | |
| 597 | // Tell the user the other places the candidate was found. |
| 598 | for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) { |
| 599 | R << NV((Twine("OtherStartLoc" ) + Twine(i)).str(), |
| 600 | CandidatesForRepeatedSeq[i].front().getDebugLoc()); |
| 601 | if (i != e - 1) |
| 602 | R << ", " ; |
| 603 | } |
| 604 | |
| 605 | R << ")" ; |
| 606 | return R; |
| 607 | }); |
| 608 | } |
| 609 | |
| 610 | void MachineOutliner::(OutlinedFunction &OF) { |
| 611 | MachineBasicBlock *MBB = &*OF.MF->begin(); |
| 612 | MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr); |
| 613 | MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction" , |
| 614 | MBB->findDebugLoc(MBBI: MBB->begin()), MBB); |
| 615 | R << "Saved " << NV("OutliningBenefit" , OF.getBenefit()) << " bytes by " |
| 616 | << "outlining " << NV("Length" , OF.getNumInstrs()) << " instructions " |
| 617 | << "from " << NV("NumOccurrences" , OF.getOccurrenceCount()) |
| 618 | << " locations. " |
| 619 | << "(Found at: " ; |
| 620 | |
| 621 | // Tell the user the other places the candidate was found. |
| 622 | for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) { |
| 623 | |
| 624 | R << NV((Twine("StartLoc" ) + Twine(i)).str(), |
| 625 | OF.Candidates[i].front().getDebugLoc()); |
| 626 | if (i != e - 1) |
| 627 | R << ", " ; |
| 628 | } |
| 629 | |
| 630 | R << ")" ; |
| 631 | |
| 632 | MORE.emit(OptDiag&: R); |
| 633 | } |
| 634 | |
| 635 | static stable_hash hashInstruction(const MachineInstr &MI) { |
| 636 | // Globals with local linkage are qualified with their module's source file |
| 637 | // name so that same-named locals in different modules do not match when hash |
| 638 | // sequences are compared across modules. |
| 639 | return stableHashValue(MI, /*HashVRegs=*/false, |
| 640 | /*HashConstantPoolIndices=*/false, |
| 641 | /*HashMemOperands=*/false, |
| 642 | /*SourceQualifyLocalGlobals=*/true); |
| 643 | } |
| 644 | |
| 645 | struct MatchedEntry { |
| 646 | unsigned StartIdx; |
| 647 | unsigned EndIdx; |
| 648 | unsigned Count; |
| 649 | MatchedEntry(unsigned StartIdx, unsigned EndIdx, unsigned Count) |
| 650 | : StartIdx(StartIdx), EndIdx(EndIdx), Count(Count) {} |
| 651 | MatchedEntry() = delete; |
| 652 | }; |
| 653 | |
| 654 | // Find all matches in an outlined hash tree. |
| 655 | // It's quadratic complexity in theory, but it's nearly linear in practice |
| 656 | // since the length of outlined sequences are small within a block. |
| 657 | static SmallVector<MatchedEntry> |
| 658 | getMatchedEntries(InstructionMapper &Mapper, const OutlinedHashTree &HashTree) { |
| 659 | auto &InstrList = Mapper.InstrList; |
| 660 | auto &UnsignedVec = Mapper.UnsignedVec; |
| 661 | |
| 662 | SmallVector<MatchedEntry> MatchedEntries; |
| 663 | auto Size = UnsignedVec.size(); |
| 664 | |
| 665 | const auto *RootNode = HashTree.getRoot(); |
| 666 | |
| 667 | auto getValidInstr = [&](unsigned Index) -> const MachineInstr * { |
| 668 | if (UnsignedVec[Index] >= Mapper.LegalInstrNumber) |
| 669 | return nullptr; |
| 670 | return &(*InstrList[Index]); |
| 671 | }; |
| 672 | |
| 673 | auto getStableHashAndFollow = |
| 674 | [](const MachineInstr &MI, const HashNode *CurrNode) -> const HashNode * { |
| 675 | stable_hash StableHash = hashInstruction(MI); |
| 676 | if (!StableHash) |
| 677 | return nullptr; |
| 678 | auto It = CurrNode->Successors.find(Val: StableHash); |
| 679 | return (It == CurrNode->Successors.end()) ? nullptr : It->second.get(); |
| 680 | }; |
| 681 | |
| 682 | for (unsigned I = 0; I < Size; ++I) { |
| 683 | const MachineInstr *MI = getValidInstr(I); |
| 684 | if (!MI || MI->isDebugInstr()) |
| 685 | continue; |
| 686 | const HashNode *CurrNode = getStableHashAndFollow(*MI, RootNode); |
| 687 | if (!CurrNode) |
| 688 | continue; |
| 689 | |
| 690 | for (unsigned J = I + 1; J < Size; ++J) { |
| 691 | const MachineInstr *MJ = getValidInstr(J); |
| 692 | if (!MJ) |
| 693 | break; |
| 694 | // Skip debug instructions as we did for the outlined function. |
| 695 | if (MJ->isDebugInstr()) |
| 696 | continue; |
| 697 | CurrNode = getStableHashAndFollow(*MJ, CurrNode); |
| 698 | if (!CurrNode) |
| 699 | break; |
| 700 | // Even with a match ending with a terminal, we continue finding |
| 701 | // matches to populate all candidates. |
| 702 | if (auto Count = CurrNode->Terminals) |
| 703 | MatchedEntries.emplace_back(Args&: I, Args&: J, Args&: *Count); |
| 704 | } |
| 705 | } |
| 706 | |
| 707 | return MatchedEntries; |
| 708 | } |
| 709 | |
| 710 | void MachineOutliner::findGlobalCandidates( |
| 711 | InstructionMapper &Mapper, |
| 712 | std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) { |
| 713 | FunctionList.clear(); |
| 714 | auto &InstrList = Mapper.InstrList; |
| 715 | auto &MBBFlagsMap = Mapper.MBBFlagsMap; |
| 716 | |
| 717 | const cl::LibraryOptionsContext &LibraryOptions = |
| 718 | Mapper.MMI.getModule()->getContext().getLibraryOptions(); |
| 719 | assert(cgdata::hasOutlinedHashTree(LibraryOptions)); |
| 720 | const auto &HashTree = *cgdata::getOutlinedHashTree(LibraryOptions); |
| 721 | std::vector<Candidate> CandidatesForRepeatedSeq; |
| 722 | for (auto &ME : getMatchedEntries(Mapper, HashTree)) { |
| 723 | CandidatesForRepeatedSeq.clear(); |
| 724 | MachineBasicBlock::iterator StartIt = InstrList[ME.StartIdx]; |
| 725 | MachineBasicBlock::iterator EndIt = InstrList[ME.EndIdx]; |
| 726 | auto Length = ME.EndIdx - ME.StartIdx + 1; |
| 727 | MachineBasicBlock *MBB = StartIt->getParent(); |
| 728 | CandidatesForRepeatedSeq.emplace_back(args&: ME.StartIdx, args&: Length, args&: StartIt, args&: EndIt, |
| 729 | args&: MBB, args&: MBBFlagsMap[MBB]); |
| 730 | const TargetInstrInfo *TII = |
| 731 | MBB->getParent()->getSubtarget().getInstrInfo(); |
| 732 | unsigned MinRepeats = 1; |
| 733 | std::optional<std::unique_ptr<OutlinedFunction>> OF = |
| 734 | TII->getOutliningCandidateInfo(MMI: *MMI, RepeatedSequenceLocs&: CandidatesForRepeatedSeq, |
| 735 | MinRepeats); |
| 736 | if (!OF.has_value() || OF.value()->Candidates.empty()) |
| 737 | continue; |
| 738 | // We create a global candidate for each match. |
| 739 | assert(OF.value()->Candidates.size() == MinRepeats); |
| 740 | FunctionList.emplace_back(args: std::make_unique<GlobalOutlinedFunction>( |
| 741 | args: std::move(OF.value()), args&: ME.Count)); |
| 742 | } |
| 743 | } |
| 744 | |
| 745 | static StringRef getCandidateInputSection(const Candidate &C) { |
| 746 | const Function &F = C.getMF()->getFunction(); |
| 747 | return F.hasSection() ? F.getSection() : StringRef(); |
| 748 | } |
| 749 | |
| 750 | static SmallVector<std::vector<Candidate>> |
| 751 | partitionCandidatesByInputSection(std::vector<Candidate> &Candidates) { |
| 752 | // Each candidate belongs to exactly one MachineFunction, so the partitions |
| 753 | // are disjoint and can be outlined independently. |
| 754 | SmallVector<std::vector<Candidate>> Partitions; |
| 755 | SmallVector<StringRef> Sections; |
| 756 | for (Candidate &C : Candidates) { |
| 757 | StringRef Section = getCandidateInputSection(C); |
| 758 | auto It = llvm::find(Range&: Sections, Val: Section); |
| 759 | if (It == Sections.end()) { |
| 760 | Sections.push_back(Elt: Section); |
| 761 | Partitions.emplace_back(); |
| 762 | It = Sections.end() - 1; |
| 763 | } |
| 764 | Partitions[std::distance(first: Sections.begin(), last: It)].push_back(x: std::move(C)); |
| 765 | } |
| 766 | return Partitions; |
| 767 | } |
| 768 | |
| 769 | void MachineOutliner::createOutlinedFunctionIfBeneficial( |
| 770 | std::vector<Candidate> &Candidates, unsigned StringLen, unsigned MinRepeats, |
| 771 | const TargetInstrInfo &TII, |
| 772 | std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) { |
| 773 | if (Candidates.size() < MinRepeats) |
| 774 | return; |
| 775 | |
| 776 | std::optional<std::unique_ptr<OutlinedFunction>> OF = |
| 777 | TII.getOutliningCandidateInfo(MMI: *MMI, RepeatedSequenceLocs&: Candidates, MinRepeats); |
| 778 | |
| 779 | // If we deleted too many candidates, then there's nothing worth outlining. |
| 780 | // FIXME: This should take target-specified instruction sizes into account. |
| 781 | if (!OF.has_value() || OF.value()->Candidates.size() < MinRepeats) |
| 782 | return; |
| 783 | |
| 784 | // Is it better to outline this candidate than not? |
| 785 | if (OF.value()->getBenefit() < Opts->outliner_benefit_threshold) { |
| 786 | recordUnprofitableCandidate(OF&: *OF.value()); |
| 787 | emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq&: Candidates, OF&: *OF.value()); |
| 788 | return; |
| 789 | } |
| 790 | |
| 791 | FunctionList.emplace_back(args: std::move(OF.value())); |
| 792 | } |
| 793 | |
| 794 | void MachineOutliner::findCandidates( |
| 795 | InstructionMapper &Mapper, |
| 796 | std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) { |
| 797 | FunctionList.clear(); |
| 798 | // IllegalInstrNumber is decremented after assigning each unique separator. |
| 799 | SuffixTree ST(Mapper.UnsignedVec, Opts->outliner_leaf_descendants, |
| 800 | /*BoundaryStart=*/Mapper.IllegalInstrNumber + 1); |
| 801 | |
| 802 | // First, find all of the repeated substrings in the tree of minimum length |
| 803 | // 2. |
| 804 | std::vector<Candidate> CandidatesForRepeatedSeq; |
| 805 | LLVM_DEBUG(dbgs() << "*** Discarding overlapping candidates *** \n" ); |
| 806 | LLVM_DEBUG( |
| 807 | dbgs() << "Searching for overlaps in all repeated sequences...\n" ); |
| 808 | for (SuffixTree::RepeatedSubstring &RS : ST) { |
| 809 | CandidatesForRepeatedSeq.clear(); |
| 810 | unsigned StringLen = RS.Length; |
| 811 | LLVM_DEBUG(dbgs() << " Sequence length: " << StringLen << "\n" ); |
| 812 | // Debug code to keep track of how many candidates we removed. |
| 813 | #ifndef NDEBUG |
| 814 | unsigned NumDiscarded = 0; |
| 815 | unsigned NumKept = 0; |
| 816 | #endif |
| 817 | // Sort the start indices so that we can efficiently check if candidates |
| 818 | // overlap with the ones we've already found for this sequence. |
| 819 | llvm::sort(C&: RS.StartIndices); |
| 820 | for (const unsigned &StartIdx : RS.StartIndices) { |
| 821 | // Trick: Discard some candidates that would be incompatible with the |
| 822 | // ones we've already found for this sequence. This will save us some |
| 823 | // work in candidate selection. |
| 824 | // |
| 825 | // If two candidates overlap, then we can't outline them both. This |
| 826 | // happens when we have candidates that look like, say |
| 827 | // |
| 828 | // AA (where each "A" is an instruction). |
| 829 | // |
| 830 | // We might have some portion of the module that looks like this: |
| 831 | // AAAAAA (6 A's) |
| 832 | // |
| 833 | // In this case, there are 5 different copies of "AA" in this range, but |
| 834 | // at most 3 can be outlined. If only outlining 3 of these is going to |
| 835 | // be unbeneficial, then we ought to not bother. |
| 836 | // |
| 837 | // Note that two things DON'T overlap when they look like this: |
| 838 | // start1...end1 .... start2...end2 |
| 839 | // That is, one must either |
| 840 | // * End before the other starts |
| 841 | // * Start after the other ends |
| 842 | unsigned EndIdx = StartIdx + StringLen - 1; |
| 843 | if (!CandidatesForRepeatedSeq.empty() && |
| 844 | StartIdx <= CandidatesForRepeatedSeq.back().getEndIdx()) { |
| 845 | #ifndef NDEBUG |
| 846 | ++NumDiscarded; |
| 847 | LLVM_DEBUG(dbgs() << " .. DISCARD candidate @ [" << StartIdx << ", " |
| 848 | << EndIdx << "]; overlaps with candidate @ [" |
| 849 | << CandidatesForRepeatedSeq.back().getStartIdx() |
| 850 | << ", " << CandidatesForRepeatedSeq.back().getEndIdx() |
| 851 | << "]\n" ); |
| 852 | #endif |
| 853 | continue; |
| 854 | } |
| 855 | // It doesn't overlap with anything, so we can outline it. |
| 856 | // Each sequence is over [StartIt, EndIt]. |
| 857 | // Save the candidate and its location. |
| 858 | #ifndef NDEBUG |
| 859 | ++NumKept; |
| 860 | #endif |
| 861 | MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx]; |
| 862 | MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx]; |
| 863 | MachineBasicBlock *MBB = StartIt->getParent(); |
| 864 | CandidatesForRepeatedSeq.emplace_back(args: StartIdx, args&: StringLen, args&: StartIt, args&: EndIt, |
| 865 | args&: MBB, args&: Mapper.MBBFlagsMap[MBB]); |
| 866 | } |
| 867 | #ifndef NDEBUG |
| 868 | LLVM_DEBUG(dbgs() << " Candidates discarded: " << NumDiscarded |
| 869 | << "\n" ); |
| 870 | LLVM_DEBUG(dbgs() << " Candidates kept: " << NumKept << "\n\n" ); |
| 871 | #endif |
| 872 | unsigned MinRepeats = 2; |
| 873 | |
| 874 | // We've found something we might want to outline. |
| 875 | // Create an OutlinedFunction to store it and check if it'd be beneficial |
| 876 | // to outline. |
| 877 | if (CandidatesForRepeatedSeq.size() < MinRepeats) |
| 878 | continue; |
| 879 | |
| 880 | // Arbitrarily choose a TII from the first candidate. |
| 881 | // FIXME: Should getOutliningCandidateInfo move to TargetMachine? |
| 882 | const TargetInstrInfo *TII = |
| 883 | CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo(); |
| 884 | |
| 885 | // Targets that do not opt in to section aware outlining never map |
| 886 | // functions with a section marking, so every candidate would land in a |
| 887 | // single partition. Skip partitioning entirely to avoid the allocation. |
| 888 | if (!TII->supportsSectionAwareOutlining()) { |
| 889 | createOutlinedFunctionIfBeneficial(Candidates&: CandidatesForRepeatedSeq, StringLen, |
| 890 | MinRepeats, TII: *TII, FunctionList); |
| 891 | continue; |
| 892 | } |
| 893 | |
| 894 | LLVM_DEBUG( |
| 895 | dbgs() |
| 896 | << "*** Section Aware Outlining is enabled for the target *** \n" ); |
| 897 | |
| 898 | SmallVector<std::vector<Candidate>> Partitions = |
| 899 | partitionCandidatesByInputSection(Candidates&: CandidatesForRepeatedSeq); |
| 900 | LLVM_DEBUG(dbgs() << " Input section partitions: " << Partitions.size() |
| 901 | << "\n" ); |
| 902 | |
| 903 | for (std::vector<Candidate> &Partition : Partitions) { |
| 904 | LLVM_DEBUG({ |
| 905 | StringRef Section = getCandidateInputSection(Partition.front()); |
| 906 | dbgs() << " .. section '" |
| 907 | << (Section.empty() ? StringRef("<none>" ) : Section) |
| 908 | << "': " << Partition.size() << " candidates\n" ; |
| 909 | }); |
| 910 | createOutlinedFunctionIfBeneficial(Candidates&: Partition, StringLen, MinRepeats, TII: *TII, |
| 911 | FunctionList); |
| 912 | } |
| 913 | } |
| 914 | } |
| 915 | |
| 916 | void MachineOutliner::computeAndPublishHashSequence(MachineFunction &MF, |
| 917 | unsigned CandSize) { |
| 918 | // Compute the hash sequence for the outlined function. |
| 919 | SmallVector<stable_hash> OutlinedHashSequence; |
| 920 | for (auto &MBB : MF) { |
| 921 | for (auto &NewMI : MBB) { |
| 922 | stable_hash Hash = hashInstruction(MI: NewMI); |
| 923 | if (!Hash) { |
| 924 | OutlinedHashSequence.clear(); |
| 925 | break; |
| 926 | } |
| 927 | OutlinedHashSequence.push_back(Elt: Hash); |
| 928 | } |
| 929 | } |
| 930 | |
| 931 | // Append a unique name based on the non-empty hash sequence. |
| 932 | if (Opts->append_content_hash_outlined_name && |
| 933 | !OutlinedHashSequence.empty()) { |
| 934 | auto CombinedHash = stable_hash_combine(Buffer: OutlinedHashSequence); |
| 935 | auto NewName = |
| 936 | MF.getName().str() + ".content." + std::to_string(val: CombinedHash); |
| 937 | MF.getFunction().setName(NewName); |
| 938 | } |
| 939 | |
| 940 | // Publish the non-empty hash sequence to the local hash tree. |
| 941 | if (OutlinerMode == CGDataMode::Write) { |
| 942 | StableHashAttempts++; |
| 943 | if (!OutlinedHashSequence.empty()) |
| 944 | LocalHashTree->insert(SequencePair: {OutlinedHashSequence, CandSize}); |
| 945 | else |
| 946 | StableHashDropped++; |
| 947 | } |
| 948 | } |
| 949 | |
| 950 | void MachineOutliner::recordUnprofitableCandidate(OutlinedFunction &OF) { |
| 951 | if (!Opts->machine_outliner_publish_unprofitable_candidates || |
| 952 | OutlinerMode != CGDataMode::Write || |
| 953 | OF.getNumInstrs() > |
| 954 | Opts->machine_outliner_unprofitable_candidate_max_instrs) |
| 955 | return; |
| 956 | |
| 957 | // Read mode uses the merged count to check frame costs. |
| 958 | if (llvm::all_of(Range&: OF.Candidates, P: [&](const Candidate &C) { |
| 959 | return OF.SequenceSize <= C.getCallOverhead(); |
| 960 | })) |
| 961 | return; |
| 962 | |
| 963 | SmallVector<stable_hash> HashSequence; |
| 964 | for (MachineInstr &MI : OF.Candidates.front()) { |
| 965 | if (MI.isDebugInstr()) |
| 966 | continue; |
| 967 | const stable_hash Hash = hashInstruction(MI); |
| 968 | if (!Hash) |
| 969 | return; |
| 970 | HashSequence.push_back(Elt: Hash); |
| 971 | } |
| 972 | if (HashSequence.empty() || |
| 973 | UnprofitableCandidateHashTree.find(Sequence: HashSequence).value_or(u: 0)) |
| 974 | return; |
| 975 | |
| 976 | const unsigned SequenceID = UnprofitableCandidates.size(); |
| 977 | // This temporary tree uses the terminal field for a one-based sequence ID, |
| 978 | // not an occurrence count. Reserve zero for sequences without a terminal. |
| 979 | UnprofitableCandidateHashTree.insert(SequencePair: {HashSequence, SequenceID + 1}); |
| 980 | UnprofitableCandidates.push_back(Elt: std::move(HashSequence)); |
| 981 | } |
| 982 | |
| 983 | bool MachineOutliner::publishUnprofitableCandidates(InstructionMapper &Mapper) { |
| 984 | if (!Opts->machine_outliner_publish_unprofitable_candidates || |
| 985 | OutlinerMode != CGDataMode::Write || UnprofitableCandidates.empty()) |
| 986 | return false; |
| 987 | |
| 988 | SmallVector<std::vector<Candidate>> CandidateGroups( |
| 989 | UnprofitableCandidates.size()); |
| 990 | BitVector ConflictingGroups(UnprofitableCandidates.size()); |
| 991 | SmallVector<MatchedEntry> ActiveMatches; |
| 992 | for (const auto &ME : |
| 993 | getMatchedEntries(Mapper, HashTree: UnprofitableCandidateHashTree)) { |
| 994 | assert(ME.Count && ME.Count <= CandidateGroups.size()); |
| 995 | // Unlike the global tree, this tree stores SequenceID + 1 in its terminal |
| 996 | // field. Decode the sequence index; ME.Count is not an occurrence count. |
| 997 | const unsigned SequenceID = ME.Count - 1; |
| 998 | |
| 999 | // Matches arrive in start-index order. Keep the ranges overlapping this |
| 1000 | // match, including those rejected by the same-sequence overlap check below. |
| 1001 | llvm::erase_if(C&: ActiveMatches, P: [&](const MatchedEntry &Other) { |
| 1002 | return Other.EndIdx < ME.StartIdx; |
| 1003 | }); |
| 1004 | for (const MatchedEntry &Other : ActiveMatches) { |
| 1005 | if (Other.Count == ME.Count) |
| 1006 | continue; |
| 1007 | // A containing sequence already covers the instructions of a sequence |
| 1008 | // nested in it, so drop only the nested group. A partial overlap drops |
| 1009 | // both groups. |
| 1010 | const bool MEContained = ME.EndIdx <= Other.EndIdx; |
| 1011 | const bool OtherContained = |
| 1012 | Other.StartIdx == ME.StartIdx && Other.EndIdx <= ME.EndIdx; |
| 1013 | if (!OtherContained) |
| 1014 | ConflictingGroups.set(SequenceID); |
| 1015 | if (!MEContained) |
| 1016 | ConflictingGroups.set(Other.Count - 1); |
| 1017 | } |
| 1018 | ActiveMatches.push_back(Elt: ME); |
| 1019 | |
| 1020 | auto &Candidates = CandidateGroups[SequenceID]; |
| 1021 | if (!Candidates.empty() && ME.StartIdx <= Candidates.back().getEndIdx()) |
| 1022 | continue; |
| 1023 | |
| 1024 | auto StartIt = Mapper.InstrList[ME.StartIdx]; |
| 1025 | auto EndIt = Mapper.InstrList[ME.EndIdx]; |
| 1026 | auto *MBB = StartIt->getParent(); |
| 1027 | Candidates.emplace_back(args: ME.StartIdx, args: ME.EndIdx - ME.StartIdx + 1, args&: StartIt, |
| 1028 | args&: EndIt, args&: MBB, args: Mapper.MBBFlagsMap.lookup(Val: MBB)); |
| 1029 | } |
| 1030 | |
| 1031 | bool Published = false; |
| 1032 | for (const auto &[SequenceID, Candidates] : |
| 1033 | llvm::enumerate(First&: CandidateGroups)) { |
| 1034 | // Publishing overlapping sequences would count the same instructions twice. |
| 1035 | // Read mode prunes overlapping sites, but cannot reconcile their merged |
| 1036 | // counts across modules. Conservatively discard conflicting groups rather |
| 1037 | // than assigning sites using a local order that can differ from Read mode. |
| 1038 | if (Candidates.empty() || ConflictingGroups.test(Idx: SequenceID)) |
| 1039 | continue; |
| 1040 | |
| 1041 | unsigned NumSites = 0; |
| 1042 | for (auto &Partition : partitionCandidatesByInputSection(Candidates)) { |
| 1043 | const auto *TII = |
| 1044 | Partition.front().getMF()->getSubtarget().getInstrInfo(); |
| 1045 | auto OF = |
| 1046 | TII->getOutliningCandidateInfo(MMI: *MMI, RepeatedSequenceLocs&: Partition, /*MinRepeats=*/1); |
| 1047 | if (!OF || OF.value()->Candidates.empty()) |
| 1048 | continue; |
| 1049 | NumSites += |
| 1050 | llvm::count_if(Range&: OF.value()->Candidates, P: [&](const Candidate &C) { |
| 1051 | return OF.value()->SequenceSize > C.getCallOverhead(); |
| 1052 | }); |
| 1053 | } |
| 1054 | if (!NumSites) |
| 1055 | continue; |
| 1056 | |
| 1057 | LocalHashTree->insert(SequencePair: {UnprofitableCandidates[SequenceID], NumSites}); |
| 1058 | ++UnprofitableCandidateGroupsPublished; |
| 1059 | UnprofitableCandidateSitesPublished += NumSites; |
| 1060 | Published = true; |
| 1061 | } |
| 1062 | return Published; |
| 1063 | } |
| 1064 | |
| 1065 | MachineFunction *MachineOutliner::createOutlinedFunction( |
| 1066 | Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) { |
| 1067 | |
| 1068 | // Create the function name. This should be unique. |
| 1069 | // FIXME: We should have a better naming scheme. This should be stable, |
| 1070 | // regardless of changes to the outliner's cost model/traversal order. |
| 1071 | std::string FunctionName = "OUTLINED_FUNCTION_" ; |
| 1072 | if (OutlineRepeatedNum > 0) |
| 1073 | FunctionName += std::to_string(val: OutlineRepeatedNum + 1) + "_" ; |
| 1074 | FunctionName += std::to_string(val: Name); |
| 1075 | LLVM_DEBUG(dbgs() << "NEW FUNCTION: " << FunctionName << "\n" ); |
| 1076 | |
| 1077 | // Create the function using an IR-level function. |
| 1078 | LLVMContext &C = M.getContext(); |
| 1079 | Function *F = Function::Create(Ty: FunctionType::get(Result: Type::getVoidTy(C), isVarArg: false), |
| 1080 | Linkage: Function::ExternalLinkage, N: FunctionName, M); |
| 1081 | |
| 1082 | // NOTE: If this is linkonceodr, then we can take advantage of linker deduping |
| 1083 | // which gives us better results when we outline from linkonceodr functions. |
| 1084 | F->setLinkage(GlobalValue::InternalLinkage); |
| 1085 | F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); |
| 1086 | |
| 1087 | // Set optsize/minsize, so we don't insert padding between outlined |
| 1088 | // functions. |
| 1089 | F->addFnAttr(Kind: Attribute::OptimizeForSize); |
| 1090 | F->addFnAttr(Kind: Attribute::MinSize); |
| 1091 | |
| 1092 | Candidate &FirstCand = OF.Candidates.front(); |
| 1093 | const TargetInstrInfo &TII = |
| 1094 | *FirstCand.getMF()->getSubtarget().getInstrInfo(); |
| 1095 | |
| 1096 | TII.mergeOutliningCandidateAttributes(F&: *F, Candidates&: OF.Candidates); |
| 1097 | |
| 1098 | if (TII.supportsSectionAwareOutlining()) { |
| 1099 | const Function &ParentFn = FirstCand.getMF()->getFunction(); |
| 1100 | if (ParentFn.hasSection()) { |
| 1101 | F->setSection(ParentFn.getSection()); |
| 1102 | LLVM_DEBUG(dbgs() << " INHERITED SECTION: " << ParentFn.getSection() |
| 1103 | << "\n" ); |
| 1104 | } |
| 1105 | } |
| 1106 | |
| 1107 | // Set uwtable, so we generate eh_frame. |
| 1108 | UWTableKind UW = std::accumulate( |
| 1109 | first: OF.Candidates.cbegin(), last: OF.Candidates.cend(), init: UWTableKind::None, |
| 1110 | binary_op: [](UWTableKind K, const outliner::Candidate &C) { |
| 1111 | return std::max(a: K, b: C.getMF()->getFunction().getUWTableKind()); |
| 1112 | }); |
| 1113 | F->setUWTableKind(UW); |
| 1114 | |
| 1115 | BasicBlock *EntryBB = BasicBlock::Create(Context&: C, Name: "entry" , Parent: F); |
| 1116 | IRBuilder<> Builder(EntryBB); |
| 1117 | Builder.CreateRetVoid(); |
| 1118 | |
| 1119 | MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI(); |
| 1120 | MachineFunction &MF = MMI.getOrCreateMachineFunction(F&: *F); |
| 1121 | MF.setIsOutlined(true); |
| 1122 | MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock(); |
| 1123 | |
| 1124 | // Insert the new function into the module. |
| 1125 | MF.insert(MBBI: MF.begin(), MBB: &MBB); |
| 1126 | |
| 1127 | MachineFunction *OriginalMF = FirstCand.front().getMF(); |
| 1128 | const std::vector<MCCFIInstruction> &Instrs = |
| 1129 | OriginalMF->getFrameInstructions(); |
| 1130 | for (auto &MI : FirstCand) { |
| 1131 | if (MI.isDebugInstr()) |
| 1132 | continue; |
| 1133 | |
| 1134 | // Don't keep debug information for outlined instructions. |
| 1135 | auto DL = DebugLoc(); |
| 1136 | if (MI.isCFIInstruction()) { |
| 1137 | unsigned CFIIndex = MI.getOperand(i: 0).getCFIIndex(); |
| 1138 | MCCFIInstruction CFI = Instrs[CFIIndex]; |
| 1139 | BuildMI(BB&: MBB, I: MBB.end(), MIMD: DL, MCID: TII.get(Opcode: TargetOpcode::CFI_INSTRUCTION)) |
| 1140 | .addCFIIndex(CFIIndex: MF.addFrameInst(Inst: CFI)); |
| 1141 | } else { |
| 1142 | MachineInstr &NewMI = TII.duplicate(MBB, InsertBefore: MBB.end(), Orig: MI); |
| 1143 | NewMI.dropMemRefs(MF); |
| 1144 | NewMI.setDebugLoc(DL); |
| 1145 | NewMI.clearKillInfo(); |
| 1146 | // Also clear debug locations and kill info on any bundled instructions. |
| 1147 | if (NewMI.isBundledWithSucc()) { |
| 1148 | auto BundleEnd = getBundleEnd(I: NewMI.getIterator()); |
| 1149 | for (auto I = std::next(x: NewMI.getIterator()); I != BundleEnd; ++I) { |
| 1150 | I->setDebugLoc(DL); |
| 1151 | I->clearKillInfo(); |
| 1152 | } |
| 1153 | } |
| 1154 | } |
| 1155 | } |
| 1156 | |
| 1157 | if (OutlinerMode != CGDataMode::None) |
| 1158 | computeAndPublishHashSequence(MF, CandSize: OF.Candidates.size()); |
| 1159 | |
| 1160 | // Set normal properties for a late MachineFunction. |
| 1161 | MF.getProperties().resetIsSSA(); |
| 1162 | MF.getProperties().setNoPHIs(); |
| 1163 | MF.getProperties().setNoVRegs(); |
| 1164 | MF.getProperties().setTracksLiveness(); |
| 1165 | MF.getRegInfo().freezeReservedRegs(); |
| 1166 | |
| 1167 | // Compute live-in set for outlined fn |
| 1168 | const MachineRegisterInfo &MRI = MF.getRegInfo(); |
| 1169 | const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); |
| 1170 | LivePhysRegs LiveIns(TRI); |
| 1171 | for (auto &Cand : OF.Candidates) { |
| 1172 | // Figure out live-ins at the first instruction. |
| 1173 | MachineBasicBlock &OutlineBB = *Cand.front().getParent(); |
| 1174 | LivePhysRegs CandLiveIns(TRI); |
| 1175 | CandLiveIns.addLiveOuts(MBB: OutlineBB); |
| 1176 | for (const MachineInstr &MI : |
| 1177 | reverse(C: make_range(x: Cand.begin(), y: OutlineBB.end()))) |
| 1178 | CandLiveIns.stepBackward(MI); |
| 1179 | |
| 1180 | // The live-in set for the outlined function is the union of the live-ins |
| 1181 | // from all the outlining points. |
| 1182 | for (MCPhysReg Reg : CandLiveIns) |
| 1183 | LiveIns.addReg(Reg); |
| 1184 | } |
| 1185 | addLiveIns(MBB, LiveRegs: LiveIns); |
| 1186 | |
| 1187 | TII.buildOutlinedFrame(MBB, MF, OF); |
| 1188 | |
| 1189 | // If there's a DISubprogram associated with this outlined function, then |
| 1190 | // emit debug info for the outlined function. |
| 1191 | if (DISubprogram *SP = getSubprogramOrNull(OF)) { |
| 1192 | // We have a DISubprogram. Get its DICompileUnit. |
| 1193 | DICompileUnit *CU = SP->getUnit(); |
| 1194 | DIBuilder DB(M, true, CU); |
| 1195 | DIFile *Unit = SP->getFile(); |
| 1196 | Mangler Mg; |
| 1197 | // Get the mangled name of the function for the linkage name. |
| 1198 | std::string Dummy; |
| 1199 | raw_string_ostream MangledNameStream(Dummy); |
| 1200 | Mg.getNameWithPrefix(OS&: MangledNameStream, GV: F, CannotUsePrivateLabel: false); |
| 1201 | |
| 1202 | DISubprogram *OutlinedSP = DB.createFunction( |
| 1203 | Scope: Unit /* Context */, Name: F->getName(), LinkageName: StringRef(Dummy), File: Unit /* File */, |
| 1204 | LineNo: 0 /* Line 0 is reserved for compiler-generated code. */, |
| 1205 | Ty: DB.createSubroutineType(ParameterTypes: DB.getOrCreateTypeArray(Elements: {})), /* void type */ |
| 1206 | ScopeLine: 0, /* Line 0 is reserved for compiler-generated code. */ |
| 1207 | Flags: DINode::DIFlags::FlagArtificial /* Compiler-generated code. */, |
| 1208 | /* Outlined code is optimized code by definition. */ |
| 1209 | SPFlags: DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized); |
| 1210 | |
| 1211 | // Attach subprogram to the function. |
| 1212 | F->setSubprogram(OutlinedSP); |
| 1213 | // We're done with the DIBuilder. |
| 1214 | DB.finalize(); |
| 1215 | } |
| 1216 | |
| 1217 | return &MF; |
| 1218 | } |
| 1219 | |
| 1220 | bool MachineOutliner::outline( |
| 1221 | Module &M, std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList, |
| 1222 | InstructionMapper &Mapper, unsigned &OutlinedFunctionNum) { |
| 1223 | LLVM_DEBUG(dbgs() << "*** Outlining ***\n" ); |
| 1224 | LLVM_DEBUG(dbgs() << "NUMBER OF POTENTIAL FUNCTIONS: " << FunctionList.size() |
| 1225 | << "\n" ); |
| 1226 | bool OutlinedSomething = false; |
| 1227 | |
| 1228 | // Sort by priority where priority := getNotOutlinedCost / getOutliningCost. |
| 1229 | // The function with highest priority should be outlined first. |
| 1230 | stable_sort(Range&: FunctionList, C: [](const std::unique_ptr<OutlinedFunction> &LHS, |
| 1231 | const std::unique_ptr<OutlinedFunction> &RHS) { |
| 1232 | return LHS->getNotOutlinedCost() * RHS->getOutliningCost() > |
| 1233 | RHS->getNotOutlinedCost() * LHS->getOutliningCost(); |
| 1234 | }); |
| 1235 | |
| 1236 | // Walk over each function, outlining them as we go along. Functions are |
| 1237 | // outlined greedily, based off the sort above. |
| 1238 | auto *UnsignedVecBegin = Mapper.UnsignedVec.begin(); |
| 1239 | LLVM_DEBUG(dbgs() << "WALKING FUNCTION LIST\n" ); |
| 1240 | for (auto &OF : FunctionList) { |
| 1241 | #ifndef NDEBUG |
| 1242 | auto NumCandidatesBefore = OF->Candidates.size(); |
| 1243 | #endif |
| 1244 | // If we outlined something that overlapped with a candidate in a previous |
| 1245 | // step, then we can't outline from it. |
| 1246 | erase_if(C&: OF->Candidates, P: [&UnsignedVecBegin](Candidate &C) { |
| 1247 | return std::any_of(first: UnsignedVecBegin + C.getStartIdx(), |
| 1248 | last: UnsignedVecBegin + C.getEndIdx() + 1, pred: [](unsigned I) { |
| 1249 | return I == static_cast<unsigned>(-1); |
| 1250 | }); |
| 1251 | }); |
| 1252 | |
| 1253 | #ifndef NDEBUG |
| 1254 | auto NumCandidatesAfter = OF->Candidates.size(); |
| 1255 | LLVM_DEBUG(dbgs() << "PRUNED: " << NumCandidatesBefore - NumCandidatesAfter |
| 1256 | << "/" << NumCandidatesBefore << " candidates\n" ); |
| 1257 | #endif |
| 1258 | |
| 1259 | // If we made it unbeneficial to outline this function, skip it. |
| 1260 | if (OF->getBenefit() < Opts->outliner_benefit_threshold) { |
| 1261 | // Overlap pruning can make a sequence that was profitable at discovery |
| 1262 | // locally unprofitable. Record it like one rejected at discovery. |
| 1263 | if (!OF->Candidates.empty()) |
| 1264 | recordUnprofitableCandidate(OF&: *OF); |
| 1265 | LLVM_DEBUG(dbgs() << "SKIP: Expected benefit (" << OF->getBenefit() |
| 1266 | << " B) < threshold (" |
| 1267 | << Opts->outliner_benefit_threshold << " B)\n" ); |
| 1268 | continue; |
| 1269 | } |
| 1270 | |
| 1271 | LLVM_DEBUG(dbgs() << "OUTLINE: Expected benefit (" << OF->getBenefit() |
| 1272 | << " B) > threshold (" << Opts->outliner_benefit_threshold |
| 1273 | << " B)\n" ); |
| 1274 | |
| 1275 | // Remove all Linker Optimization Hints from the candidates. |
| 1276 | // TODO: The intersection of the LOHs from all candidates should be legal in |
| 1277 | // the outlined function. |
| 1278 | SmallPtrSet<MachineInstr *, 2> MIs; |
| 1279 | for (Candidate &C : OF->Candidates) { |
| 1280 | for (MachineInstr &MI : C) |
| 1281 | MIs.insert(Ptr: &MI); |
| 1282 | NumRemovedLOHs += TM->clearLinkerOptimizationHints(MIs); |
| 1283 | MIs.clear(); |
| 1284 | } |
| 1285 | |
| 1286 | // It's beneficial. Create the function and outline its sequence's |
| 1287 | // occurrences. |
| 1288 | OF->MF = createOutlinedFunction(M, OF&: *OF, Mapper, Name: OutlinedFunctionNum); |
| 1289 | emitOutlinedFunctionRemark(OF&: *OF); |
| 1290 | FunctionsCreated++; |
| 1291 | OutlinedFunctionNum++; // Created a function, move to the next name. |
| 1292 | MachineFunction *MF = OF->MF; |
| 1293 | const TargetSubtargetInfo &STI = MF->getSubtarget(); |
| 1294 | const TargetInstrInfo &TII = *STI.getInstrInfo(); |
| 1295 | |
| 1296 | // Replace occurrences of the sequence with calls to the new function. |
| 1297 | LLVM_DEBUG(dbgs() << "CREATE OUTLINED CALLS\n" ); |
| 1298 | for (Candidate &C : OF->Candidates) { |
| 1299 | MachineBasicBlock &MBB = *C.getMBB(); |
| 1300 | MachineBasicBlock::iterator StartIt = C.begin(); |
| 1301 | MachineBasicBlock::iterator EndIt = std::prev(x: C.end()); |
| 1302 | |
| 1303 | // Find the first non-debug instruction with a non-zero source line, and |
| 1304 | // merge the locations of the calls in the candidate that have one. |
| 1305 | DebugLoc FirstLoc, MergedCallLoc; |
| 1306 | for (MachineInstr &MI : C) { |
| 1307 | if (MI.isDebugInstr()) |
| 1308 | continue; |
| 1309 | const DebugLoc &DL = MI.getDebugLoc(); |
| 1310 | if (!DL || !DL.getLine()) |
| 1311 | continue; |
| 1312 | if (!FirstLoc) |
| 1313 | FirstLoc = DL; |
| 1314 | if (MI.isCall()) |
| 1315 | MergedCallLoc = MergedCallLoc |
| 1316 | ? DebugLoc::getMergedLocation(LocA: MergedCallLoc, LocB: DL) |
| 1317 | : DL; |
| 1318 | } |
| 1319 | |
| 1320 | // Remember the instruction the call sequence will be inserted after, so |
| 1321 | // we can find every instruction the target inserts below. |
| 1322 | MachineBasicBlock::iterator PrevIt = |
| 1323 | StartIt == MBB.begin() ? MBB.end() : std::prev(x: StartIt); |
| 1324 | |
| 1325 | // Insert the call. |
| 1326 | auto CallInst = TII.insertOutlinedCall(M, MBB, It&: StartIt, MF&: *MF, C); |
| 1327 | |
| 1328 | // Unwinding through a call in the candidate symbolizes the caller frame |
| 1329 | // at the outlined call, so it should carry that call's location. With |
| 1330 | // multiple calls, every one of them is symbolized there, so use their |
| 1331 | // merged location: it may be less precise when the calls differ, but it |
| 1332 | // never attributes a call to an inlined scope it was not in. Nothing |
| 1333 | // returns to a tail branch, so it keeps the first location. |
| 1334 | DebugLoc CallLoc = |
| 1335 | !CallInst->isTerminator() && MergedCallLoc ? MergedCallLoc : FirstLoc; |
| 1336 | |
| 1337 | // insertOutlinedCall may emit link register save/restore instructions |
| 1338 | // around the call, and leaves StartIt on the last instruction it |
| 1339 | // inserted. Give the whole sequence the same location. Otherwise, when |
| 1340 | // that location has a source line, a locationless save or restore can |
| 1341 | // introduce a line 0 row, including at the return address immediately |
| 1342 | // after the call. |
| 1343 | MachineBasicBlock::iterator SeqBegin = |
| 1344 | PrevIt == MBB.end() ? MBB.begin() : std::next(x: PrevIt); |
| 1345 | for (MachineInstr &MI : make_range(x: SeqBegin, y: std::next(x: StartIt))) |
| 1346 | MI.setDebugLoc(CallLoc); |
| 1347 | |
| 1348 | #ifndef NDEBUG |
| 1349 | auto MBBBeingOutlinedFromName = |
| 1350 | MBB.getName().empty() ? "<unknown>" : MBB.getName().str(); |
| 1351 | auto MFBeingOutlinedFromName = MBB.getParent()->getName().empty() |
| 1352 | ? "<unknown>" |
| 1353 | : MBB.getParent()->getName().str(); |
| 1354 | LLVM_DEBUG(dbgs() << " CALL: " << MF->getName() << " in " |
| 1355 | << MFBeingOutlinedFromName << ":" |
| 1356 | << MBBBeingOutlinedFromName << "\n" ); |
| 1357 | LLVM_DEBUG(dbgs() << " .. " << *CallInst); |
| 1358 | #endif |
| 1359 | |
| 1360 | // If the caller tracks liveness, then we need to make sure that |
| 1361 | // anything we outline doesn't break liveness assumptions. The outlined |
| 1362 | // functions themselves currently don't track liveness, but we should |
| 1363 | // make sure that the ranges we yank things out of aren't wrong. |
| 1364 | if (MBB.getParent()->getProperties().hasTracksLiveness()) { |
| 1365 | // The following code is to add implicit def operands to the call |
| 1366 | // instruction. It also updates call site information for moved |
| 1367 | // code. |
| 1368 | SmallSet<Register, 2> UseRegs, DefRegs; |
| 1369 | // Copy over the defs in the outlined range. |
| 1370 | // First inst in outlined range <-- Anything that's defined in this |
| 1371 | // ... .. range has to be added as an |
| 1372 | // implicit Last inst in outlined range <-- def to the call |
| 1373 | // instruction. Also remove call site information for outlined block |
| 1374 | // of code. The exposed uses need to be copied in the outlined range. |
| 1375 | for (MachineBasicBlock::reverse_iterator |
| 1376 | Iter = EndIt.getReverse(), |
| 1377 | Last = std::next(x: CallInst.getReverse()); |
| 1378 | Iter != Last; Iter++) { |
| 1379 | MachineInstr *MI = &*Iter; |
| 1380 | if (MI->isDebugInstr()) |
| 1381 | continue; |
| 1382 | SmallSet<Register, 2> InstrUseRegs; |
| 1383 | for (MachineOperand &MOP : MI->operands()) { |
| 1384 | // Skip over anything that isn't a register. |
| 1385 | if (!MOP.isReg()) |
| 1386 | continue; |
| 1387 | |
| 1388 | if (MOP.isDef()) { |
| 1389 | // Introduce DefRegs set to skip the redundant register. |
| 1390 | DefRegs.insert(V: MOP.getReg()); |
| 1391 | if (UseRegs.count(V: MOP.getReg()) && |
| 1392 | !InstrUseRegs.count(V: MOP.getReg())) |
| 1393 | // Since the regiester is modeled as defined, |
| 1394 | // it is not necessary to be put in use register set. |
| 1395 | UseRegs.erase(V: MOP.getReg()); |
| 1396 | } else if (!MOP.isUndef()) { |
| 1397 | // Any register which is not undefined should |
| 1398 | // be put in the use register set. |
| 1399 | UseRegs.insert(V: MOP.getReg()); |
| 1400 | InstrUseRegs.insert(V: MOP.getReg()); |
| 1401 | } |
| 1402 | } |
| 1403 | if (MI->isCandidateForAdditionalCallInfo()) |
| 1404 | MI->getMF()->eraseAdditionalCallInfo(MI); |
| 1405 | } |
| 1406 | |
| 1407 | for (const Register &I : DefRegs) |
| 1408 | // If it's a def, add it to the call instruction. |
| 1409 | CallInst->addOperand( |
| 1410 | Op: MachineOperand::CreateReg(Reg: I, isDef: true, /* isDef = true */ |
| 1411 | isImp: true /* isImp = true */)); |
| 1412 | |
| 1413 | for (const Register &I : UseRegs) |
| 1414 | // If it's a exposed use, add it to the call instruction. |
| 1415 | CallInst->addOperand( |
| 1416 | Op: MachineOperand::CreateReg(Reg: I, isDef: false, /* isDef = false */ |
| 1417 | isImp: true /* isImp = true */)); |
| 1418 | } |
| 1419 | |
| 1420 | // Erase from the point after where the call was inserted up to, and |
| 1421 | // including, the final instruction in the sequence. |
| 1422 | // Erase needs one past the end, so we need std::next there too. |
| 1423 | MBB.erase(I: std::next(x: StartIt), E: std::next(x: EndIt)); |
| 1424 | |
| 1425 | // Keep track of what we removed by marking them all as -1. |
| 1426 | for (unsigned &I : make_range(x: UnsignedVecBegin + C.getStartIdx(), |
| 1427 | y: UnsignedVecBegin + C.getEndIdx() + 1)) |
| 1428 | I = static_cast<unsigned>(-1); |
| 1429 | OutlinedSomething = true; |
| 1430 | |
| 1431 | // Statistics. |
| 1432 | NumOutlined++; |
| 1433 | } |
| 1434 | } |
| 1435 | |
| 1436 | LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n" ); |
| 1437 | return OutlinedSomething; |
| 1438 | } |
| 1439 | |
| 1440 | static bool allowPGOOutlining(RunOutliner RunOutlinerMode, |
| 1441 | const ProfileSummaryInfo *PSI, |
| 1442 | const BlockFrequencyInfo *BFI, |
| 1443 | MachineBasicBlock &MBB) { |
| 1444 | if (RunOutlinerMode != RunOutliner::OptimisticPGO && |
| 1445 | RunOutlinerMode != RunOutliner::ConservativePGO) |
| 1446 | return true; |
| 1447 | auto *MF = MBB.getParent(); |
| 1448 | if (MF->getFunction().hasFnAttribute(Kind: Attribute::Cold)) { |
| 1449 | ++NumPGOAllowedCold; |
| 1450 | return true; |
| 1451 | } |
| 1452 | |
| 1453 | auto *BB = MBB.getBasicBlock(); |
| 1454 | if (BB && PSI && BFI) |
| 1455 | if (auto Count = BFI->getBlockProfileCount(BB)) |
| 1456 | return *Count <= PSI->getOrCompColdCountThreshold(); |
| 1457 | |
| 1458 | if (RunOutlinerMode == RunOutliner::OptimisticPGO) { |
| 1459 | auto *TII = MF->getSubtarget().getInstrInfo(); |
| 1460 | if (TII->shouldOutlineFromFunctionByDefault(MF&: *MF)) { |
| 1461 | // Profile data is unavailable, but we optimistically allow outlining |
| 1462 | ++NumPGOOptimisticOutlined; |
| 1463 | return true; |
| 1464 | } |
| 1465 | return false; |
| 1466 | } |
| 1467 | assert(RunOutlinerMode == RunOutliner::ConservativePGO); |
| 1468 | // Profile data is unavailable, so we conservatively block outlining |
| 1469 | ++NumPGOConservativeBlockedOutlined; |
| 1470 | return false; |
| 1471 | } |
| 1472 | |
| 1473 | void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M) { |
| 1474 | // Build instruction mappings for each function in the module. Start by |
| 1475 | // iterating over each Function in M. |
| 1476 | LLVM_DEBUG(dbgs() << "*** Populating mapper ***\n" ); |
| 1477 | bool EnableProfileGuidedOutlining = |
| 1478 | RunOutlinerMode == RunOutliner::OptimisticPGO || |
| 1479 | RunOutlinerMode == RunOutliner::ConservativePGO; |
| 1480 | ProfileSummaryInfo *PSI = nullptr; |
| 1481 | if (EnableProfileGuidedOutlining) |
| 1482 | PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); |
| 1483 | for (Function &F : M) { |
| 1484 | LLVM_DEBUG(dbgs() << "MAPPING FUNCTION: " << F.getName() << "\n" ); |
| 1485 | |
| 1486 | if (F.hasFnAttribute(Kind: Attribute::NoOutline)) { |
| 1487 | LLVM_DEBUG(dbgs() << "SKIP: Function has nooutline attribute\n" ); |
| 1488 | continue; |
| 1489 | } |
| 1490 | |
| 1491 | // There's something in F. Check if it has a MachineFunction associated with |
| 1492 | // it. |
| 1493 | MachineFunction *MF = MMI->getMachineFunction(F); |
| 1494 | |
| 1495 | // If it doesn't, then there's nothing to outline from. Move to the next |
| 1496 | // Function. |
| 1497 | if (!MF) { |
| 1498 | LLVM_DEBUG(dbgs() << "SKIP: Function does not have a MachineFunction\n" ); |
| 1499 | continue; |
| 1500 | } |
| 1501 | |
| 1502 | // If the function returns twice, skip it. |
| 1503 | // The context saved by functions such as setjmp will be different if |
| 1504 | // they take place within an outlined function. |
| 1505 | // Ex: Saved stack pointer will be different. |
| 1506 | if (F.hasFnAttribute(Kind: Attribute::ReturnsTwice)) { |
| 1507 | LLVM_DEBUG(dbgs() << "SKIP: Function has returnstwice attribute\n" ); |
| 1508 | continue; |
| 1509 | } |
| 1510 | |
| 1511 | // If the function calls a function that can return twice, skip it, |
| 1512 | // for the same reasons. |
| 1513 | if (MF->exposesReturnsTwice()) { |
| 1514 | LLVM_DEBUG(dbgs() << "SKIP: Function calls a function with " |
| 1515 | "returnstwice attribute\n" ); |
| 1516 | continue; |
| 1517 | } |
| 1518 | |
| 1519 | const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); |
| 1520 | BlockFrequencyInfo *BFI = nullptr; |
| 1521 | if (EnableProfileGuidedOutlining && F.hasProfileData()) |
| 1522 | BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI(); |
| 1523 | if (RunOutlinerMode == RunOutliner::TargetDefault && |
| 1524 | !TII->shouldOutlineFromFunctionByDefault(MF&: *MF)) { |
| 1525 | LLVM_DEBUG(dbgs() << "SKIP: Target does not want to outline from " |
| 1526 | "function by default\n" ); |
| 1527 | continue; |
| 1528 | } |
| 1529 | |
| 1530 | // We have a MachineFunction. Ask the target if it's suitable for outlining. |
| 1531 | // If it isn't, then move on to the next Function in the module. |
| 1532 | if (!TII->isFunctionSafeToOutlineFrom(MF&: *MF, OutlineFromLinkOnceODRs)) { |
| 1533 | LLVM_DEBUG(dbgs() << "SKIP: " << MF->getName() |
| 1534 | << ": unsafe to outline from\n" ); |
| 1535 | continue; |
| 1536 | } |
| 1537 | |
| 1538 | // We have a function suitable for outlining. Iterate over every |
| 1539 | // MachineBasicBlock in MF and try to map its instructions to a list of |
| 1540 | // unsigned integers. |
| 1541 | const unsigned MinMBBSize = 2; |
| 1542 | |
| 1543 | for (MachineBasicBlock &MBB : *MF) { |
| 1544 | LLVM_DEBUG(dbgs() << " MAPPING MBB: '" << MBB.getName() << "'\n" ); |
| 1545 | // If there isn't anything in MBB, then there's no point in outlining from |
| 1546 | // it. |
| 1547 | // If there are fewer than 2 non-debug instructions in the MBB, then it |
| 1548 | // can't ever contain something worth outlining. Count raw instructions, |
| 1549 | // including bundle interiors, to preserve MBB.size() behavior. Pseudo |
| 1550 | // probes also retain their historical treatment as ordinary |
| 1551 | // instructions. |
| 1552 | // FIXME: This should be based off of the maximum size in B of an outlined |
| 1553 | // call versus the size in B of the MBB. |
| 1554 | if (!hasNItemsOrMore(C: instructionsWithoutDebug(It: MBB.instr_begin(), |
| 1555 | End: MBB.instr_end(), |
| 1556 | /* SkipPseudoOp */ false), |
| 1557 | N: MinMBBSize)) { |
| 1558 | LLVM_DEBUG(dbgs() << " SKIP: MBB size less than minimum size of " |
| 1559 | << MinMBBSize << "\n" ); |
| 1560 | continue; |
| 1561 | } |
| 1562 | |
| 1563 | // Check if MBB could be the target of an indirect branch. If it is, then |
| 1564 | // we don't want to outline from it. |
| 1565 | if (MBB.hasAddressTaken()) { |
| 1566 | LLVM_DEBUG(dbgs() << " SKIP: MBB's address is taken\n" ); |
| 1567 | continue; |
| 1568 | } |
| 1569 | |
| 1570 | if (!allowPGOOutlining(RunOutlinerMode, PSI, BFI, MBB)) { |
| 1571 | ++NumPGOBlockedOutlined; |
| 1572 | continue; |
| 1573 | } |
| 1574 | |
| 1575 | // MBB is suitable for outlining. Map it to a list of unsigneds. |
| 1576 | Mapper.convertToUnsignedVec(MBB, TII: *TII); |
| 1577 | } |
| 1578 | } |
| 1579 | // Statistics. |
| 1580 | UnsignedVecSize = Mapper.UnsignedVec.size(); |
| 1581 | } |
| 1582 | |
| 1583 | void MachineOutliner::( |
| 1584 | const Module &M, StringMap<unsigned> &FunctionToInstrCount) { |
| 1585 | // Collect instruction counts for every function. We'll use this to emit |
| 1586 | // per-function size remarks later. |
| 1587 | for (const Function &F : M) { |
| 1588 | MachineFunction *MF = MMI->getMachineFunction(F); |
| 1589 | |
| 1590 | // We only care about MI counts here. If there's no MachineFunction at this |
| 1591 | // point, then there won't be after the outliner runs, so let's move on. |
| 1592 | if (!MF) |
| 1593 | continue; |
| 1594 | FunctionToInstrCount[F.getName().str()] = MF->getInstructionCount(); |
| 1595 | } |
| 1596 | } |
| 1597 | |
| 1598 | void MachineOutliner::( |
| 1599 | const Module &M, const StringMap<unsigned> &FunctionToInstrCount) { |
| 1600 | // Iterate over each function in the module and emit remarks. |
| 1601 | // Note that we won't miss anything by doing this, because the outliner never |
| 1602 | // deletes functions. |
| 1603 | for (const Function &F : M) { |
| 1604 | MachineFunction *MF = MMI->getMachineFunction(F); |
| 1605 | |
| 1606 | // The outliner never deletes functions. If we don't have a MF here, then we |
| 1607 | // didn't have one prior to outlining either. |
| 1608 | if (!MF) |
| 1609 | continue; |
| 1610 | |
| 1611 | std::string Fname = std::string(F.getName()); |
| 1612 | unsigned FnCountAfter = MF->getInstructionCount(); |
| 1613 | unsigned FnCountBefore = 0; |
| 1614 | |
| 1615 | // Check if the function was recorded before. |
| 1616 | auto It = FunctionToInstrCount.find(Key: Fname); |
| 1617 | |
| 1618 | // Did we have a previously-recorded size? If yes, then set FnCountBefore |
| 1619 | // to that. |
| 1620 | if (It != FunctionToInstrCount.end()) |
| 1621 | FnCountBefore = It->second; |
| 1622 | |
| 1623 | // Compute the delta and emit a remark if there was a change. |
| 1624 | int64_t FnDelta = static_cast<int64_t>(FnCountAfter) - |
| 1625 | static_cast<int64_t>(FnCountBefore); |
| 1626 | if (FnDelta == 0) |
| 1627 | continue; |
| 1628 | |
| 1629 | MachineOptimizationRemarkEmitter MORE(*MF, nullptr); |
| 1630 | MORE.emit(RemarkBuilder: [&]() { |
| 1631 | MachineOptimizationRemarkAnalysis R("size-info" , "FunctionMISizeChange" , |
| 1632 | DiagnosticLocation(), &MF->front()); |
| 1633 | R << DiagnosticInfoOptimizationBase::Argument("Pass" , "Machine Outliner" ) |
| 1634 | << ": Function: " |
| 1635 | << DiagnosticInfoOptimizationBase::Argument("Function" , F.getName()) |
| 1636 | << ": MI instruction count changed from " |
| 1637 | << DiagnosticInfoOptimizationBase::Argument("MIInstrsBefore" , |
| 1638 | FnCountBefore) |
| 1639 | << " to " |
| 1640 | << DiagnosticInfoOptimizationBase::Argument("MIInstrsAfter" , |
| 1641 | FnCountAfter) |
| 1642 | << "; Delta: " |
| 1643 | << DiagnosticInfoOptimizationBase::Argument("Delta" , FnDelta); |
| 1644 | return R; |
| 1645 | }); |
| 1646 | } |
| 1647 | } |
| 1648 | |
| 1649 | void MachineOutliner::initializeOutlinerMode(const Module &M) { |
| 1650 | if (!Opts->global_outlining) |
| 1651 | return; |
| 1652 | |
| 1653 | if (auto *IndexWrapperPass = |
| 1654 | getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>()) { |
| 1655 | auto *TheIndex = IndexWrapperPass->getIndex(); |
| 1656 | // (Full)LTO module does not have functions added to the index. |
| 1657 | // In this case, we run the outliner without using codegen data as usual. |
| 1658 | if (TheIndex && !TheIndex->hasExportedFunctions(M)) |
| 1659 | return; |
| 1660 | } |
| 1661 | |
| 1662 | // When codegen data write is enabled, we want to write the local outlined |
| 1663 | // hash tree to the custom section, `__llvm_outline`. |
| 1664 | // When the outlined hash tree is available from the previous codegen data, |
| 1665 | // we want to read it to optimistically create global outlining candidates. |
| 1666 | const cl::LibraryOptionsContext &LibraryOptions = |
| 1667 | M.getContext().getLibraryOptions(); |
| 1668 | if (cgdata::emitCGData(LibraryOptions)) { |
| 1669 | OutlinerMode = CGDataMode::Write; |
| 1670 | // Create a local outlined hash tree to be published. |
| 1671 | LocalHashTree = std::make_unique<OutlinedHashTree>(); |
| 1672 | // We don't need to read the outlined hash tree from the previous codegen |
| 1673 | } else if (cgdata::hasOutlinedHashTree(LibraryOptions)) |
| 1674 | OutlinerMode = CGDataMode::Read; |
| 1675 | } |
| 1676 | |
| 1677 | void MachineOutliner::emitOutlinedHashTree(Module &M) { |
| 1678 | assert(LocalHashTree); |
| 1679 | if (!LocalHashTree->empty()) { |
| 1680 | LLVM_DEBUG({ |
| 1681 | dbgs() << "Emit outlined hash tree. Size: " << LocalHashTree->size() |
| 1682 | << "\n" ; |
| 1683 | }); |
| 1684 | SmallVector<char> Buf; |
| 1685 | raw_svector_ostream OS(Buf); |
| 1686 | |
| 1687 | OutlinedHashTreeRecord HTR(std::move(LocalHashTree)); |
| 1688 | HTR.serialize(OS); |
| 1689 | |
| 1690 | llvm::StringRef Data(Buf.data(), Buf.size()); |
| 1691 | std::unique_ptr<MemoryBuffer> Buffer = |
| 1692 | MemoryBuffer::getMemBuffer(InputData: Data, BufferName: "in-memory outlined hash tree" , RequiresNullTerminator: false); |
| 1693 | |
| 1694 | Triple TT(M.getTargetTriple()); |
| 1695 | embedBufferInModule( |
| 1696 | M, Buf: *Buffer, |
| 1697 | SectionName: getCodeGenDataSectionName(CGSK: CG_outline, OF: TT.getObjectFormat())); |
| 1698 | } |
| 1699 | } |
| 1700 | |
| 1701 | bool MachineOutliner::runOnModule(Module &M) { |
| 1702 | if (skipModule(M)) |
| 1703 | return false; |
| 1704 | |
| 1705 | // Check if there's anything in the module. If it's empty, then there's |
| 1706 | // nothing to outline. |
| 1707 | if (M.empty()) |
| 1708 | return false; |
| 1709 | |
| 1710 | Opts = &getCodeGenOptions(M); |
| 1711 | |
| 1712 | // Initialize the outliner mode. |
| 1713 | initializeOutlinerMode(M); |
| 1714 | |
| 1715 | MMI = &getAnalysis<MachineModuleInfoWrapperPass>().getMMI(); |
| 1716 | TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>(); |
| 1717 | |
| 1718 | // Number to append to the current outlined function. |
| 1719 | unsigned OutlinedFunctionNum = 0; |
| 1720 | |
| 1721 | OutlineRepeatedNum = 0; |
| 1722 | // Clear once per module so candidates discovered before a rerun are retained, |
| 1723 | // even if too few sites survive for the suffix tree to rediscover them. |
| 1724 | UnprofitableCandidates.clear(); |
| 1725 | UnprofitableCandidateHashTree.clear(); |
| 1726 | // Each doOutline replaces the mapping; publishing below uses the last one. |
| 1727 | std::optional<InstructionMapper> Mapper; |
| 1728 | const bool OutlinedSomething = doOutline(M, Mapper, OutlinedFunctionNum); |
| 1729 | |
| 1730 | for (unsigned I = 0; OutlinedSomething && I < Opts->machine_outliner_reruns; |
| 1731 | ++I) { |
| 1732 | OutlinedFunctionNum = 0; |
| 1733 | OutlineRepeatedNum++; |
| 1734 | if (!doOutline(M, Mapper, OutlinedFunctionNum)) { |
| 1735 | LLVM_DEBUG({ |
| 1736 | dbgs() << "Did not outline on iteration " << I + 2 << " out of " |
| 1737 | << Opts->machine_outliner_reruns + 1 << "\n" ; |
| 1738 | }); |
| 1739 | break; |
| 1740 | } |
| 1741 | } |
| 1742 | |
| 1743 | // Recount sequences collected across all iterations in the final mapping, |
| 1744 | // which excludes sites consumed by local outlining. Remapping the module |
| 1745 | // would also count sites inside the functions outlined by that iteration. |
| 1746 | const bool PublishedUnprofitableCandidates = |
| 1747 | publishUnprofitableCandidates(Mapper&: *Mapper); |
| 1748 | if (!OutlinedSomething && !PublishedUnprofitableCandidates) |
| 1749 | return false; |
| 1750 | |
| 1751 | if (OutlinerMode == CGDataMode::Write) |
| 1752 | emitOutlinedHashTree(M); |
| 1753 | |
| 1754 | return true; |
| 1755 | } |
| 1756 | |
| 1757 | bool MachineOutliner::doOutline(Module &M, |
| 1758 | std::optional<InstructionMapper> &Mapper, |
| 1759 | unsigned &OutlinedFunctionNum) { |
| 1760 | // If the user passed -enable-machine-outliner=always or |
| 1761 | // -enable-machine-outliner, the pass will run on all functions in the module. |
| 1762 | // Otherwise, if the target supports default outlining, it will run on all |
| 1763 | // functions deemed by the target to be worth outlining from by default. Tell |
| 1764 | // the user how the outliner is running. |
| 1765 | LLVM_DEBUG({ |
| 1766 | dbgs() << "Machine Outliner: Running on " ; |
| 1767 | switch (RunOutlinerMode) { |
| 1768 | case RunOutliner::AlwaysOutline: |
| 1769 | dbgs() << "all functions" ; |
| 1770 | break; |
| 1771 | case RunOutliner::OptimisticPGO: |
| 1772 | dbgs() << "optimistically cold functions" ; |
| 1773 | break; |
| 1774 | case RunOutliner::ConservativePGO: |
| 1775 | dbgs() << "conservatively cold functions" ; |
| 1776 | break; |
| 1777 | case RunOutliner::TargetDefault: |
| 1778 | dbgs() << "target-default functions" ; |
| 1779 | break; |
| 1780 | case RunOutliner::NeverOutline: |
| 1781 | llvm_unreachable("should not outline" ); |
| 1782 | } |
| 1783 | dbgs() << "\n" ; |
| 1784 | }); |
| 1785 | |
| 1786 | // If the user specifies that they want to outline from linkonceodrs, set |
| 1787 | // it here. |
| 1788 | OutlineFromLinkOnceODRs = Opts->enable_linkonceodr_outlining; |
| 1789 | Mapper.emplace(args&: *MMI); |
| 1790 | |
| 1791 | // Prepare instruction mappings for the suffix tree. |
| 1792 | populateMapper(Mapper&: *Mapper, M); |
| 1793 | std::vector<std::unique_ptr<OutlinedFunction>> FunctionList; |
| 1794 | |
| 1795 | // Find all of the outlining candidates. |
| 1796 | if (OutlinerMode == CGDataMode::Read) |
| 1797 | findGlobalCandidates(Mapper&: *Mapper, FunctionList); |
| 1798 | else |
| 1799 | findCandidates(Mapper&: *Mapper, FunctionList); |
| 1800 | |
| 1801 | // If we've requested size remarks, then collect the MI counts of every |
| 1802 | // function before outlining, and the MI counts after outlining. |
| 1803 | // FIXME: This shouldn't be in the outliner at all; it should ultimately be |
| 1804 | // the pass manager's responsibility. |
| 1805 | // This could pretty easily be placed in outline instead, but because we |
| 1806 | // really ultimately *don't* want this here, it's done like this for now |
| 1807 | // instead. |
| 1808 | |
| 1809 | // Check if we want size remarks. |
| 1810 | bool = M.shouldEmitInstrCountChangedRemark(); |
| 1811 | StringMap<unsigned> FunctionToInstrCount; |
| 1812 | if (ShouldEmitSizeRemarks) |
| 1813 | initSizeRemarkInfo(M, FunctionToInstrCount); |
| 1814 | |
| 1815 | // Outline each of the candidates and return true if something was outlined. |
| 1816 | bool OutlinedSomething = |
| 1817 | outline(M, FunctionList, Mapper&: *Mapper, OutlinedFunctionNum); |
| 1818 | |
| 1819 | // If we outlined something, we definitely changed the MI count of the |
| 1820 | // module. If we've asked for size remarks, then output them. |
| 1821 | // FIXME: This should be in the pass manager. |
| 1822 | if (ShouldEmitSizeRemarks && OutlinedSomething) |
| 1823 | emitInstrCountChangedRemark(M, FunctionToInstrCount); |
| 1824 | |
| 1825 | LLVM_DEBUG({ |
| 1826 | if (!OutlinedSomething) |
| 1827 | dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum |
| 1828 | << " because no changes were found.\n" ; |
| 1829 | }); |
| 1830 | |
| 1831 | return OutlinedSomething; |
| 1832 | } |
| 1833 | |