| 1 | //===- PartialInlining.cpp - Inline parts of functions --------------------===// |
| 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 | // This pass performs partial inlining, typically by inlining an if statement |
| 10 | // that surrounds the body of the function. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "llvm/Transforms/IPO/PartialInlining.h" |
| 15 | #include "IPOOptions.h" |
| 16 | #include "llvm/ADT/DenseMap.h" |
| 17 | #include "llvm/ADT/DenseSet.h" |
| 18 | #include "llvm/ADT/DepthFirstIterator.h" |
| 19 | #include "llvm/ADT/STLExtras.h" |
| 20 | #include "llvm/ADT/SmallVector.h" |
| 21 | #include "llvm/ADT/Statistic.h" |
| 22 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
| 23 | #include "llvm/Analysis/BranchProbabilityInfo.h" |
| 24 | #include "llvm/Analysis/InlineCost.h" |
| 25 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
| 26 | #include "llvm/Analysis/ProfileSummaryInfo.h" |
| 27 | #include "llvm/Analysis/TargetLibraryInfo.h" |
| 28 | #include "llvm/Analysis/TargetTransformInfo.h" |
| 29 | #include "llvm/IR/Attributes.h" |
| 30 | #include "llvm/IR/BasicBlock.h" |
| 31 | #include "llvm/IR/CFG.h" |
| 32 | #include "llvm/IR/CycleInfo.h" |
| 33 | #include "llvm/IR/DebugLoc.h" |
| 34 | #include "llvm/IR/DiagnosticInfo.h" |
| 35 | #include "llvm/IR/Dominators.h" |
| 36 | #include "llvm/IR/Function.h" |
| 37 | #include "llvm/IR/InstrTypes.h" |
| 38 | #include "llvm/IR/Instruction.h" |
| 39 | #include "llvm/IR/Instructions.h" |
| 40 | #include "llvm/IR/IntrinsicInst.h" |
| 41 | #include "llvm/IR/Intrinsics.h" |
| 42 | #include "llvm/IR/Module.h" |
| 43 | #include "llvm/IR/Operator.h" |
| 44 | #include "llvm/IR/ProfDataUtils.h" |
| 45 | #include "llvm/IR/User.h" |
| 46 | #include "llvm/Support/BlockFrequency.h" |
| 47 | #include "llvm/Support/BranchProbability.h" |
| 48 | #include "llvm/Support/Casting.h" |
| 49 | #include "llvm/Support/ErrorHandling.h" |
| 50 | #include "llvm/Transforms/IPO.h" |
| 51 | #include "llvm/Transforms/Utils/Cloning.h" |
| 52 | #include "llvm/Transforms/Utils/CodeExtractor.h" |
| 53 | #include "llvm/Transforms/Utils/ValueMapper.h" |
| 54 | #include <algorithm> |
| 55 | #include <cassert> |
| 56 | #include <cstdint> |
| 57 | #include <memory> |
| 58 | #include <tuple> |
| 59 | #include <vector> |
| 60 | |
| 61 | using namespace llvm; |
| 62 | |
| 63 | #define DEBUG_TYPE "partial-inlining" |
| 64 | |
| 65 | STATISTIC(NumPartialInlined, |
| 66 | "Number of callsites functions partially inlined into." ); |
| 67 | STATISTIC(NumColdOutlinePartialInlined, "Number of times functions with " |
| 68 | "cold outlined regions were partially " |
| 69 | "inlined into its caller(s)." ); |
| 70 | STATISTIC(NumColdRegionsFound, |
| 71 | "Number of cold single entry/exit regions found." ); |
| 72 | STATISTIC(NumColdRegionsOutlined, |
| 73 | "Number of cold single entry/exit regions outlined." ); |
| 74 | |
| 75 | namespace { |
| 76 | |
| 77 | struct FunctionOutliningInfo { |
| 78 | FunctionOutliningInfo() = default; |
| 79 | |
| 80 | // Returns the number of blocks to be inlined including all blocks |
| 81 | // in Entries and one return block. |
| 82 | unsigned getNumInlinedBlocks() const { return Entries.size() + 1; } |
| 83 | |
| 84 | // A set of blocks including the function entry that guard |
| 85 | // the region to be outlined. |
| 86 | SmallVector<BasicBlock *, 4> Entries; |
| 87 | |
| 88 | // The return block that is not included in the outlined region. |
| 89 | BasicBlock *ReturnBlock = nullptr; |
| 90 | |
| 91 | // The dominating block of the region to be outlined. |
| 92 | BasicBlock *NonReturnBlock = nullptr; |
| 93 | |
| 94 | // The set of blocks in Entries that are predecessors to ReturnBlock |
| 95 | SmallVector<BasicBlock *, 4> ReturnBlockPreds; |
| 96 | }; |
| 97 | |
| 98 | struct FunctionOutliningMultiRegionInfo { |
| 99 | FunctionOutliningMultiRegionInfo() = default; |
| 100 | |
| 101 | // Container for outline regions |
| 102 | struct OutlineRegionInfo { |
| 103 | OutlineRegionInfo(ArrayRef<BasicBlock *> Region, BasicBlock *EntryBlock, |
| 104 | BasicBlock *ExitBlock, BasicBlock *ReturnBlock) |
| 105 | : Region(Region), EntryBlock(EntryBlock), ExitBlock(ExitBlock), |
| 106 | ReturnBlock(ReturnBlock) {} |
| 107 | SmallVector<BasicBlock *, 8> Region; |
| 108 | BasicBlock *EntryBlock; |
| 109 | BasicBlock *ExitBlock; |
| 110 | BasicBlock *ReturnBlock; |
| 111 | }; |
| 112 | |
| 113 | SmallVector<OutlineRegionInfo, 4> ORI; |
| 114 | }; |
| 115 | |
| 116 | struct PartialInlinerImpl { |
| 117 | |
| 118 | PartialInlinerImpl( |
| 119 | const IPOOptions &Opts, function_ref<AssumptionCache &(Function &)> GetAC, |
| 120 | function_ref<AssumptionCache *(Function &)> LookupAC, |
| 121 | function_ref<TargetTransformInfo &(Function &)> GTTI, |
| 122 | function_ref<const TargetLibraryInfo &(Function &)> GTLI, |
| 123 | ProfileSummaryInfo &ProfSI, |
| 124 | function_ref<BlockFrequencyInfo &(Function &)> GBFI = nullptr) |
| 125 | : Opts(Opts), GetAssumptionCache(GetAC), LookupAssumptionCache(LookupAC), |
| 126 | GetTTI(GTTI), GetBFI(GBFI), GetTLI(GTLI), PSI(ProfSI) {} |
| 127 | |
| 128 | bool run(Module &M); |
| 129 | // Main part of the transformation that calls helper functions to find |
| 130 | // outlining candidates, clone & outline the function, and attempt to |
| 131 | // partially inline the resulting function. Returns true if |
| 132 | // inlining was successful, false otherwise. Also returns the outline |
| 133 | // function (only if we partially inlined early returns) as there is a |
| 134 | // possibility to further "peel" early return statements that were left in the |
| 135 | // outline function due to code size. |
| 136 | std::pair<bool, Function *> unswitchFunction(Function &F); |
| 137 | |
| 138 | // This class speculatively clones the function to be partial inlined. |
| 139 | // At the end of partial inlining, the remaining callsites to the cloned |
| 140 | // function that are not partially inlined will be fixed up to reference |
| 141 | // the original function, and the cloned function will be erased. |
| 142 | struct FunctionCloner { |
| 143 | // Two constructors, one for single region outlining, the other for |
| 144 | // multi-region outlining. |
| 145 | FunctionCloner(Function *F, FunctionOutliningInfo *OI, |
| 146 | OptimizationRemarkEmitter &ORE, |
| 147 | function_ref<AssumptionCache *(Function &)> LookupAC, |
| 148 | function_ref<TargetTransformInfo &(Function &)> GetTTI); |
| 149 | FunctionCloner(Function *F, FunctionOutliningMultiRegionInfo *OMRI, |
| 150 | OptimizationRemarkEmitter &ORE, |
| 151 | function_ref<AssumptionCache *(Function &)> LookupAC, |
| 152 | function_ref<TargetTransformInfo &(Function &)> GetTTI); |
| 153 | |
| 154 | ~FunctionCloner(); |
| 155 | |
| 156 | // Prepare for function outlining: making sure there is only |
| 157 | // one incoming edge from the extracted/outlined region to |
| 158 | // the return block. |
| 159 | void normalizeReturnBlock() const; |
| 160 | |
| 161 | // Do function outlining for cold regions. |
| 162 | bool doMultiRegionFunctionOutlining(const IPOOptions &Opts); |
| 163 | // Do function outlining for region after early return block(s). |
| 164 | // NOTE: For vararg functions that do the vararg handling in the outlined |
| 165 | // function, we temporarily generate IR that does not properly |
| 166 | // forward varargs to the outlined function. Calling InlineFunction |
| 167 | // will update calls to the outlined functions to properly forward |
| 168 | // the varargs. |
| 169 | Function *doSingleRegionFunctionOutlining(); |
| 170 | |
| 171 | Function *OrigFunc = nullptr; |
| 172 | Function *ClonedFunc = nullptr; |
| 173 | |
| 174 | typedef std::pair<Function *, BasicBlock *> FuncBodyCallerPair; |
| 175 | // Keep track of Outlined Functions and the basic block they're called from. |
| 176 | SmallVector<FuncBodyCallerPair, 4> OutlinedFunctions; |
| 177 | |
| 178 | // ClonedFunc is inlined in one of its callers after function |
| 179 | // outlining. |
| 180 | bool IsFunctionInlined = false; |
| 181 | // The cost of the region to be outlined. |
| 182 | InstructionCost OutlinedRegionCost = 0; |
| 183 | // ClonedOI is specific to outlining non-early return blocks. |
| 184 | std::unique_ptr<FunctionOutliningInfo> ClonedOI = nullptr; |
| 185 | // ClonedOMRI is specific to outlining cold regions. |
| 186 | std::unique_ptr<FunctionOutliningMultiRegionInfo> ClonedOMRI = nullptr; |
| 187 | std::unique_ptr<BlockFrequencyInfo> ClonedFuncBFI = nullptr; |
| 188 | OptimizationRemarkEmitter &ORE; |
| 189 | function_ref<AssumptionCache *(Function &)> LookupAC; |
| 190 | function_ref<TargetTransformInfo &(Function &)> GetTTI; |
| 191 | }; |
| 192 | |
| 193 | private: |
| 194 | const IPOOptions &Opts; |
| 195 | int NumPartialInlining = 0; |
| 196 | function_ref<AssumptionCache &(Function &)> GetAssumptionCache; |
| 197 | function_ref<AssumptionCache *(Function &)> LookupAssumptionCache; |
| 198 | function_ref<TargetTransformInfo &(Function &)> GetTTI; |
| 199 | function_ref<BlockFrequencyInfo &(Function &)> GetBFI; |
| 200 | function_ref<const TargetLibraryInfo &(Function &)> GetTLI; |
| 201 | ProfileSummaryInfo &PSI; |
| 202 | |
| 203 | // Return the frequency of the OutlininingBB relative to F's entry point. |
| 204 | // The result is no larger than 1 and is represented using BP. |
| 205 | // (Note that the outlined region's 'head' block can only have incoming |
| 206 | // edges from the guarding entry blocks). |
| 207 | BranchProbability |
| 208 | getOutliningCallBBRelativeFreq(FunctionCloner &Cloner) const; |
| 209 | |
| 210 | // Return true if the callee of CB should be partially inlined with |
| 211 | // profit. |
| 212 | bool shouldPartialInline(CallBase &CB, FunctionCloner &Cloner, |
| 213 | BlockFrequency WeightedOutliningRcost, |
| 214 | OptimizationRemarkEmitter &ORE) const; |
| 215 | |
| 216 | // Try to inline DuplicateFunction (cloned from F with call to |
| 217 | // the OutlinedFunction into its callers. Return true |
| 218 | // if there is any successful inlining. |
| 219 | bool tryPartialInline(FunctionCloner &Cloner); |
| 220 | |
| 221 | // Compute the mapping from use site of DuplicationFunction to the enclosing |
| 222 | // BB's profile count. |
| 223 | void |
| 224 | computeCallsiteToProfCountMap(Function *DuplicateFunction, |
| 225 | DenseMap<User *, uint64_t> &SiteCountMap) const; |
| 226 | |
| 227 | bool isLimitReached() const { |
| 228 | return (Opts.max_partial_inlining != -1 && |
| 229 | NumPartialInlining >= Opts.max_partial_inlining); |
| 230 | } |
| 231 | |
| 232 | static CallBase *getSupportedCallBase(User *U) { |
| 233 | if (isa<CallInst>(Val: U) || isa<InvokeInst>(Val: U)) |
| 234 | return cast<CallBase>(Val: U); |
| 235 | llvm_unreachable("All uses must be calls" ); |
| 236 | return nullptr; |
| 237 | } |
| 238 | |
| 239 | static CallBase *getOneCallSiteTo(Function &F) { |
| 240 | User *User = *F.user_begin(); |
| 241 | return getSupportedCallBase(U: User); |
| 242 | } |
| 243 | |
| 244 | std::tuple<DebugLoc, BasicBlock *> getOneDebugLoc(Function &F) const { |
| 245 | CallBase *CB = getOneCallSiteTo(F); |
| 246 | DebugLoc DLoc = CB->getDebugLoc(); |
| 247 | BasicBlock *Block = CB->getParent(); |
| 248 | return std::make_tuple(args&: DLoc, args&: Block); |
| 249 | } |
| 250 | |
| 251 | // Returns the costs associated with function outlining: |
| 252 | // - The first value is the non-weighted runtime cost for making the call |
| 253 | // to the outlined function, including the addtional setup cost in the |
| 254 | // outlined function itself; |
| 255 | // - The second value is the estimated size of the new call sequence in |
| 256 | // basic block Cloner.OutliningCallBB; |
| 257 | std::tuple<InstructionCost, InstructionCost> |
| 258 | computeOutliningCosts(FunctionCloner &Cloner) const; |
| 259 | |
| 260 | // Compute the 'InlineCost' of block BB. InlineCost is a proxy used to |
| 261 | // approximate both the size and runtime cost (Note that in the current |
| 262 | // inline cost analysis, there is no clear distinction there either). |
| 263 | static InstructionCost computeBBInlineCost(BasicBlock *BB, |
| 264 | TargetTransformInfo *TTI); |
| 265 | |
| 266 | std::unique_ptr<FunctionOutliningInfo> |
| 267 | computeOutliningInfo(Function &F) const; |
| 268 | |
| 269 | std::unique_ptr<FunctionOutliningMultiRegionInfo> |
| 270 | computeOutliningColdRegionsInfo(Function &F, |
| 271 | OptimizationRemarkEmitter &ORE) const; |
| 272 | }; |
| 273 | |
| 274 | } // end anonymous namespace |
| 275 | |
| 276 | std::unique_ptr<FunctionOutliningMultiRegionInfo> |
| 277 | PartialInlinerImpl::( |
| 278 | Function &F, OptimizationRemarkEmitter &ORE) const { |
| 279 | BasicBlock *EntryBlock = &F.front(); |
| 280 | |
| 281 | DominatorTree DT(F); |
| 282 | CycleInfo CI; |
| 283 | CI.compute(F); |
| 284 | BranchProbabilityInfo BPI(F, CI); |
| 285 | std::unique_ptr<BlockFrequencyInfo> ScopedBFI; |
| 286 | BlockFrequencyInfo *BFI; |
| 287 | if (!GetBFI) { |
| 288 | ScopedBFI.reset(p: new BlockFrequencyInfo(F, BPI, CI)); |
| 289 | BFI = ScopedBFI.get(); |
| 290 | } else |
| 291 | BFI = &(GetBFI(F)); |
| 292 | |
| 293 | // Return if we don't have profiling information. |
| 294 | if (!PSI.hasInstrumentationProfile()) |
| 295 | return std::unique_ptr<FunctionOutliningMultiRegionInfo>(); |
| 296 | |
| 297 | std::unique_ptr<FunctionOutliningMultiRegionInfo> OutliningInfo = |
| 298 | std::make_unique<FunctionOutliningMultiRegionInfo>(); |
| 299 | |
| 300 | auto IsSingleExit = |
| 301 | [&ORE](SmallVectorImpl<BasicBlock *> &BlockList) -> BasicBlock * { |
| 302 | BasicBlock *ExitBlock = nullptr; |
| 303 | for (auto *Block : BlockList) { |
| 304 | for (BasicBlock *Succ : successors(BB: Block)) { |
| 305 | if (!is_contained(Range&: BlockList, Element: Succ)) { |
| 306 | if (ExitBlock) { |
| 307 | ORE.emit(RemarkBuilder: [&]() { |
| 308 | return OptimizationRemarkMissed(DEBUG_TYPE, "MultiExitRegion" , |
| 309 | &Succ->front()) |
| 310 | << "Region dominated by " |
| 311 | << ore::NV("Block" , BlockList.front()->getName()) |
| 312 | << " has more than one region exit edge." ; |
| 313 | }); |
| 314 | return nullptr; |
| 315 | } |
| 316 | |
| 317 | ExitBlock = Block; |
| 318 | } |
| 319 | } |
| 320 | } |
| 321 | return ExitBlock; |
| 322 | }; |
| 323 | |
| 324 | auto BBProfileCount = [BFI](BasicBlock *BB) { |
| 325 | return BFI->getBlockProfileCount(BB).value_or(u: 0); |
| 326 | }; |
| 327 | |
| 328 | // Use the same computeBBInlineCost function to compute the cost savings of |
| 329 | // the outlining the candidate region. |
| 330 | TargetTransformInfo *FTTI = &GetTTI(F); |
| 331 | InstructionCost OverallFunctionCost = 0; |
| 332 | for (auto &BB : F) |
| 333 | OverallFunctionCost += computeBBInlineCost(BB: &BB, TTI: FTTI); |
| 334 | |
| 335 | LLVM_DEBUG(dbgs() << "OverallFunctionCost = " << OverallFunctionCost |
| 336 | << "\n" ;); |
| 337 | |
| 338 | InstructionCost MinOutlineRegionCost = OverallFunctionCost.map( |
| 339 | F: [&](auto Cost) { return Cost * Opts.min_region_size_ratio; }); |
| 340 | |
| 341 | BranchProbability MinBranchProbability( |
| 342 | static_cast<int>(Opts.cold_branch_ratio * Opts.min_block_execution), |
| 343 | Opts.min_block_execution); |
| 344 | bool ColdCandidateFound = false; |
| 345 | BasicBlock *CurrEntry = EntryBlock; |
| 346 | std::vector<BasicBlock *> DFS; |
| 347 | SmallPtrSet<BasicBlock *, 8> VisitedSet; |
| 348 | DFS.push_back(x: CurrEntry); |
| 349 | VisitedSet.insert(Ptr: CurrEntry); |
| 350 | |
| 351 | // Use Depth First Search on the basic blocks to find CFG edges that are |
| 352 | // considered cold. |
| 353 | // Cold regions considered must also have its inline cost compared to the |
| 354 | // overall inline cost of the original function. The region is outlined only |
| 355 | // if it reduced the inline cost of the function by 'MinOutlineRegionCost' or |
| 356 | // more. |
| 357 | while (!DFS.empty()) { |
| 358 | auto *ThisBB = DFS.back(); |
| 359 | DFS.pop_back(); |
| 360 | // Only consider regions with predecessor blocks that are considered |
| 361 | // not-cold (default: part of the top 99.99% of all block counters) |
| 362 | // AND greater than our minimum block execution count (default: 100). |
| 363 | if (PSI.isColdBlock(BB: ThisBB, BFI) || |
| 364 | BBProfileCount(ThisBB) < Opts.min_block_execution) |
| 365 | continue; |
| 366 | for (auto SI = succ_begin(BB: ThisBB); SI != succ_end(BB: ThisBB); ++SI) { |
| 367 | if (!VisitedSet.insert(Ptr: *SI).second) |
| 368 | continue; |
| 369 | DFS.push_back(x: *SI); |
| 370 | // If branch isn't cold, we skip to the next one. |
| 371 | BranchProbability SuccProb = BPI.getEdgeProbability(Src: ThisBB, Dst: *SI); |
| 372 | if (SuccProb > MinBranchProbability) |
| 373 | continue; |
| 374 | |
| 375 | LLVM_DEBUG(dbgs() << "Found cold edge: " << ThisBB->getName() << "->" |
| 376 | << SI->getName() |
| 377 | << "\nBranch Probability = " << SuccProb << "\n" ;); |
| 378 | |
| 379 | SmallVector<BasicBlock *, 8> DominateVector; |
| 380 | DT.getDescendants(R: *SI, Result&: DominateVector); |
| 381 | assert(!DominateVector.empty() && |
| 382 | "SI should be reachable and have at least itself as descendant" ); |
| 383 | |
| 384 | // We can only outline single entry regions (for now). |
| 385 | if (!DominateVector.front()->hasNPredecessors(N: 1)) { |
| 386 | LLVM_DEBUG(dbgs() << "ABORT: Block " << SI->getName() |
| 387 | << " doesn't have a single predecessor in the " |
| 388 | "dominator tree\n" ;); |
| 389 | continue; |
| 390 | } |
| 391 | |
| 392 | BasicBlock *ExitBlock = nullptr; |
| 393 | // We can only outline single exit regions (for now). |
| 394 | if (!(ExitBlock = IsSingleExit(DominateVector))) { |
| 395 | LLVM_DEBUG(dbgs() << "ABORT: Block " << SI->getName() |
| 396 | << " doesn't have a unique successor\n" ;); |
| 397 | continue; |
| 398 | } |
| 399 | |
| 400 | InstructionCost OutlineRegionCost = 0; |
| 401 | for (auto *BB : DominateVector) |
| 402 | OutlineRegionCost += computeBBInlineCost(BB, TTI: &GetTTI(*BB->getParent())); |
| 403 | |
| 404 | LLVM_DEBUG(dbgs() << "OutlineRegionCost = " << OutlineRegionCost |
| 405 | << "\n" ;); |
| 406 | |
| 407 | if (!Opts.skip_partial_inlining_cost_analysis && |
| 408 | OutlineRegionCost < MinOutlineRegionCost) { |
| 409 | ORE.emit(RemarkBuilder: [&]() { |
| 410 | return OptimizationRemarkAnalysis(DEBUG_TYPE, "TooCostly" , |
| 411 | &SI->front()) |
| 412 | << ore::NV("Callee" , &F) |
| 413 | << " inline cost-savings smaller than " |
| 414 | << ore::NV("Cost" , MinOutlineRegionCost); |
| 415 | }); |
| 416 | |
| 417 | LLVM_DEBUG(dbgs() << "ABORT: Outline region cost is smaller than " |
| 418 | << MinOutlineRegionCost << "\n" ;); |
| 419 | continue; |
| 420 | } |
| 421 | |
| 422 | // For now, ignore blocks that belong to a SISE region that is a |
| 423 | // candidate for outlining. In the future, we may want to look |
| 424 | // at inner regions because the outer region may have live-exit |
| 425 | // variables. |
| 426 | VisitedSet.insert_range(R&: DominateVector); |
| 427 | |
| 428 | // ReturnBlock here means the block after the outline call |
| 429 | BasicBlock *ReturnBlock = ExitBlock->getSingleSuccessor(); |
| 430 | FunctionOutliningMultiRegionInfo::OutlineRegionInfo RegInfo( |
| 431 | DominateVector, DominateVector.front(), ExitBlock, ReturnBlock); |
| 432 | OutliningInfo->ORI.push_back(Elt: RegInfo); |
| 433 | LLVM_DEBUG(dbgs() << "Found Cold Candidate starting at block: " |
| 434 | << DominateVector.front()->getName() << "\n" ;); |
| 435 | ColdCandidateFound = true; |
| 436 | NumColdRegionsFound++; |
| 437 | } |
| 438 | } |
| 439 | |
| 440 | if (ColdCandidateFound) |
| 441 | return OutliningInfo; |
| 442 | |
| 443 | return std::unique_ptr<FunctionOutliningMultiRegionInfo>(); |
| 444 | } |
| 445 | |
| 446 | std::unique_ptr<FunctionOutliningInfo> |
| 447 | PartialInlinerImpl::computeOutliningInfo(Function &F) const { |
| 448 | BasicBlock *EntryBlock = &F.front(); |
| 449 | CondBrInst *BR = dyn_cast<CondBrInst>(Val: EntryBlock->getTerminator()); |
| 450 | if (!BR) |
| 451 | return std::unique_ptr<FunctionOutliningInfo>(); |
| 452 | |
| 453 | // Returns true if Succ is BB's successor |
| 454 | auto IsSuccessor = [](BasicBlock *Succ, BasicBlock *BB) { |
| 455 | return is_contained(Range: successors(BB), Element: Succ); |
| 456 | }; |
| 457 | |
| 458 | auto IsReturnBlock = [](BasicBlock *BB) { |
| 459 | Instruction *TI = BB->getTerminator(); |
| 460 | return isa<ReturnInst>(Val: TI); |
| 461 | }; |
| 462 | |
| 463 | auto GetReturnBlock = [&](BasicBlock *Succ1, BasicBlock *Succ2) { |
| 464 | if (IsReturnBlock(Succ1)) |
| 465 | return std::make_tuple(args&: Succ1, args&: Succ2); |
| 466 | if (IsReturnBlock(Succ2)) |
| 467 | return std::make_tuple(args&: Succ2, args&: Succ1); |
| 468 | |
| 469 | return std::make_tuple<BasicBlock *, BasicBlock *>(args: nullptr, args: nullptr); |
| 470 | }; |
| 471 | |
| 472 | // Detect a triangular shape: |
| 473 | auto GetCommonSucc = [&](BasicBlock *Succ1, BasicBlock *Succ2) { |
| 474 | if (IsSuccessor(Succ1, Succ2)) |
| 475 | return std::make_tuple(args&: Succ1, args&: Succ2); |
| 476 | if (IsSuccessor(Succ2, Succ1)) |
| 477 | return std::make_tuple(args&: Succ2, args&: Succ1); |
| 478 | |
| 479 | return std::make_tuple<BasicBlock *, BasicBlock *>(args: nullptr, args: nullptr); |
| 480 | }; |
| 481 | |
| 482 | std::unique_ptr<FunctionOutliningInfo> OutliningInfo = |
| 483 | std::make_unique<FunctionOutliningInfo>(); |
| 484 | |
| 485 | BasicBlock *CurrEntry = EntryBlock; |
| 486 | bool CandidateFound = false; |
| 487 | do { |
| 488 | // The number of blocks to be inlined has already reached |
| 489 | // the limit. When -max-num-inline-blocks is set to 0 or 1, this |
| 490 | // disables partial inlining for the function. |
| 491 | if (OutliningInfo->getNumInlinedBlocks() >= Opts.max_num_inline_blocks) |
| 492 | break; |
| 493 | |
| 494 | if (succ_size(BB: CurrEntry) != 2) |
| 495 | break; |
| 496 | |
| 497 | BasicBlock *Succ1 = *succ_begin(BB: CurrEntry); |
| 498 | BasicBlock *Succ2 = *(succ_begin(BB: CurrEntry) + 1); |
| 499 | |
| 500 | BasicBlock *ReturnBlock, *NonReturnBlock; |
| 501 | std::tie(args&: ReturnBlock, args&: NonReturnBlock) = GetReturnBlock(Succ1, Succ2); |
| 502 | |
| 503 | if (ReturnBlock) { |
| 504 | OutliningInfo->Entries.push_back(Elt: CurrEntry); |
| 505 | OutliningInfo->ReturnBlock = ReturnBlock; |
| 506 | OutliningInfo->NonReturnBlock = NonReturnBlock; |
| 507 | CandidateFound = true; |
| 508 | break; |
| 509 | } |
| 510 | |
| 511 | BasicBlock *CommSucc, *OtherSucc; |
| 512 | std::tie(args&: CommSucc, args&: OtherSucc) = GetCommonSucc(Succ1, Succ2); |
| 513 | |
| 514 | if (!CommSucc) |
| 515 | break; |
| 516 | |
| 517 | OutliningInfo->Entries.push_back(Elt: CurrEntry); |
| 518 | CurrEntry = OtherSucc; |
| 519 | } while (true); |
| 520 | |
| 521 | if (!CandidateFound) |
| 522 | return std::unique_ptr<FunctionOutliningInfo>(); |
| 523 | |
| 524 | // There should not be any successors (not in the entry set) other than |
| 525 | // {ReturnBlock, NonReturnBlock} |
| 526 | assert(OutliningInfo->Entries[0] == &F.front() && |
| 527 | "Function Entry must be the first in Entries vector" ); |
| 528 | DenseSet<BasicBlock *> Entries(llvm::from_range, OutliningInfo->Entries); |
| 529 | |
| 530 | // Returns true of BB has Predecessor which is not |
| 531 | // in Entries set. |
| 532 | auto HasNonEntryPred = [Entries](BasicBlock *BB) { |
| 533 | for (auto *Pred : predecessors(BB)) { |
| 534 | if (!Entries.count(V: Pred)) |
| 535 | return true; |
| 536 | } |
| 537 | return false; |
| 538 | }; |
| 539 | auto CheckAndNormalizeCandidate = |
| 540 | [Entries, HasNonEntryPred](FunctionOutliningInfo *OutliningInfo) { |
| 541 | for (BasicBlock *E : OutliningInfo->Entries) { |
| 542 | for (auto *Succ : successors(BB: E)) { |
| 543 | if (Entries.count(V: Succ)) |
| 544 | continue; |
| 545 | if (Succ == OutliningInfo->ReturnBlock) |
| 546 | OutliningInfo->ReturnBlockPreds.push_back(Elt: E); |
| 547 | else if (Succ != OutliningInfo->NonReturnBlock) |
| 548 | return false; |
| 549 | } |
| 550 | // There should not be any outside incoming edges either: |
| 551 | if (HasNonEntryPred(E)) |
| 552 | return false; |
| 553 | } |
| 554 | return true; |
| 555 | }; |
| 556 | |
| 557 | if (!CheckAndNormalizeCandidate(OutliningInfo.get())) |
| 558 | return std::unique_ptr<FunctionOutliningInfo>(); |
| 559 | |
| 560 | // Now further growing the candidate's inlining region by |
| 561 | // peeling off dominating blocks from the outlining region: |
| 562 | while (OutliningInfo->getNumInlinedBlocks() < Opts.max_num_inline_blocks) { |
| 563 | BasicBlock *Cand = OutliningInfo->NonReturnBlock; |
| 564 | if (succ_size(BB: Cand) != 2) |
| 565 | break; |
| 566 | |
| 567 | if (HasNonEntryPred(Cand)) |
| 568 | break; |
| 569 | |
| 570 | BasicBlock *Succ1 = *succ_begin(BB: Cand); |
| 571 | BasicBlock *Succ2 = *(succ_begin(BB: Cand) + 1); |
| 572 | |
| 573 | BasicBlock *ReturnBlock, *NonReturnBlock; |
| 574 | std::tie(args&: ReturnBlock, args&: NonReturnBlock) = GetReturnBlock(Succ1, Succ2); |
| 575 | if (!ReturnBlock || ReturnBlock != OutliningInfo->ReturnBlock) |
| 576 | break; |
| 577 | |
| 578 | if (NonReturnBlock->getSinglePredecessor() != Cand) |
| 579 | break; |
| 580 | |
| 581 | // Now grow and update OutlininigInfo: |
| 582 | OutliningInfo->Entries.push_back(Elt: Cand); |
| 583 | OutliningInfo->NonReturnBlock = NonReturnBlock; |
| 584 | OutliningInfo->ReturnBlockPreds.push_back(Elt: Cand); |
| 585 | Entries.insert(V: Cand); |
| 586 | } |
| 587 | |
| 588 | return OutliningInfo; |
| 589 | } |
| 590 | |
| 591 | // Check if there is PGO data or user annotated branch data: |
| 592 | static bool hasProfileData(const Function &F, const FunctionOutliningInfo &OI) { |
| 593 | if (F.hasProfileData()) |
| 594 | return true; |
| 595 | // Now check if any of the entry block has MD_prof data: |
| 596 | for (auto *E : OI.Entries) { |
| 597 | CondBrInst *BR = dyn_cast<CondBrInst>(Val: E->getTerminator()); |
| 598 | if (BR && hasBranchWeightMD(I: *BR)) |
| 599 | return true; |
| 600 | } |
| 601 | return false; |
| 602 | } |
| 603 | |
| 604 | BranchProbability PartialInlinerImpl::getOutliningCallBBRelativeFreq( |
| 605 | FunctionCloner &Cloner) const { |
| 606 | BasicBlock *OutliningCallBB = Cloner.OutlinedFunctions.back().second; |
| 607 | auto EntryFreq = |
| 608 | Cloner.ClonedFuncBFI->getBlockFreq(BB: &Cloner.ClonedFunc->getEntryBlock()); |
| 609 | auto OutliningCallFreq = |
| 610 | Cloner.ClonedFuncBFI->getBlockFreq(BB: OutliningCallBB); |
| 611 | // FIXME Hackery needed because ClonedFuncBFI is based on the function BEFORE |
| 612 | // we outlined any regions, so we may encounter situations where the |
| 613 | // OutliningCallFreq is *slightly* bigger than the EntryFreq. |
| 614 | if (OutliningCallFreq.getFrequency() > EntryFreq.getFrequency()) |
| 615 | OutliningCallFreq = EntryFreq; |
| 616 | |
| 617 | auto OutlineRegionRelFreq = BranchProbability::getBranchProbability( |
| 618 | Numerator: OutliningCallFreq.getFrequency(), Denominator: EntryFreq.getFrequency()); |
| 619 | |
| 620 | if (hasProfileData(F: *Cloner.OrigFunc, OI: *Cloner.ClonedOI)) |
| 621 | return OutlineRegionRelFreq; |
| 622 | |
| 623 | // When profile data is not available, we need to be conservative in |
| 624 | // estimating the overall savings. Static branch prediction can usually |
| 625 | // guess the branch direction right (taken/non-taken), but the guessed |
| 626 | // branch probability is usually not biased enough. In case when the |
| 627 | // outlined region is predicted to be likely, its probability needs |
| 628 | // to be made higher (more biased) to not under-estimate the cost of |
| 629 | // function outlining. On the other hand, if the outlined region |
| 630 | // is predicted to be less likely, the predicted probablity is usually |
| 631 | // higher than the actual. For instance, the actual probability of the |
| 632 | // less likely target is only 5%, but the guessed probablity can be |
| 633 | // 40%. In the latter case, there is no need for further adjustment. |
| 634 | // FIXME: add an option for this. |
| 635 | if (OutlineRegionRelFreq < BranchProbability(45, 100)) |
| 636 | return OutlineRegionRelFreq; |
| 637 | |
| 638 | OutlineRegionRelFreq = |
| 639 | std::max(a: OutlineRegionRelFreq, |
| 640 | b: BranchProbability(Opts.outline_region_freq_percent, 100)); |
| 641 | |
| 642 | return OutlineRegionRelFreq; |
| 643 | } |
| 644 | |
| 645 | bool PartialInlinerImpl::( |
| 646 | CallBase &CB, FunctionCloner &Cloner, BlockFrequency WeightedOutliningRcost, |
| 647 | OptimizationRemarkEmitter &ORE) const { |
| 648 | using namespace ore; |
| 649 | |
| 650 | Function *Callee = CB.getCalledFunction(); |
| 651 | assert(Callee == Cloner.ClonedFunc); |
| 652 | |
| 653 | if (Opts.skip_partial_inlining_cost_analysis) |
| 654 | return isInlineViable(Callee&: *Callee).isSuccess(); |
| 655 | |
| 656 | Function *Caller = CB.getCaller(); |
| 657 | auto &CallerTTI = GetTTI(*Caller); |
| 658 | bool = |
| 659 | Callee->getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled( |
| 660 | DEBUG_TYPE); |
| 661 | InlineCost IC = getInlineCost(Call&: CB, Params: getInlineParams(C: CB.getContext()), CallerTTI, |
| 662 | GetAssumptionCache, GetTLI, GetBFI, PSI: &PSI, |
| 663 | ORE: RemarksEnabled ? &ORE : nullptr); |
| 664 | |
| 665 | if (IC.isAlways()) { |
| 666 | ORE.emit(RemarkBuilder: [&]() { |
| 667 | return OptimizationRemarkAnalysis(DEBUG_TYPE, "AlwaysInline" , &CB) |
| 668 | << NV("Callee" , Cloner.OrigFunc) |
| 669 | << " should always be fully inlined, not partially" ; |
| 670 | }); |
| 671 | return false; |
| 672 | } |
| 673 | |
| 674 | if (IC.isNever()) { |
| 675 | ORE.emit(RemarkBuilder: [&]() { |
| 676 | return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline" , &CB) |
| 677 | << NV("Callee" , Cloner.OrigFunc) << " not partially inlined into " |
| 678 | << NV("Caller" , Caller) |
| 679 | << " because it should never be inlined (cost=never)" ; |
| 680 | }); |
| 681 | return false; |
| 682 | } |
| 683 | |
| 684 | if (!IC) { |
| 685 | ORE.emit(RemarkBuilder: [&]() { |
| 686 | return OptimizationRemarkAnalysis(DEBUG_TYPE, "TooCostly" , &CB) |
| 687 | << NV("Callee" , Cloner.OrigFunc) << " not partially inlined into " |
| 688 | << NV("Caller" , Caller) << " because too costly to inline (cost=" |
| 689 | << NV("Cost" , IC.getCost()) << ", threshold=" |
| 690 | << NV("Threshold" , IC.getCostDelta() + IC.getCost()) << ")" ; |
| 691 | }); |
| 692 | return false; |
| 693 | } |
| 694 | const DataLayout &DL = Caller->getDataLayout(); |
| 695 | |
| 696 | // The savings of eliminating the call: |
| 697 | int NonWeightedSavings = getCallsiteCost(TTI: CallerTTI, Call: CB, DL); |
| 698 | BlockFrequency NormWeightedSavings(NonWeightedSavings); |
| 699 | |
| 700 | // Weighted saving is smaller than weighted cost, return false |
| 701 | if (NormWeightedSavings < WeightedOutliningRcost) { |
| 702 | ORE.emit(RemarkBuilder: [&]() { |
| 703 | return OptimizationRemarkAnalysis(DEBUG_TYPE, "OutliningCallcostTooHigh" , |
| 704 | &CB) |
| 705 | << NV("Callee" , Cloner.OrigFunc) << " not partially inlined into " |
| 706 | << NV("Caller" , Caller) << " runtime overhead (overhead=" |
| 707 | << NV("Overhead" , (unsigned)WeightedOutliningRcost.getFrequency()) |
| 708 | << ", savings=" |
| 709 | << NV("Savings" , (unsigned)NormWeightedSavings.getFrequency()) |
| 710 | << ")" |
| 711 | << " of making the outlined call is too high" ; |
| 712 | }); |
| 713 | |
| 714 | return false; |
| 715 | } |
| 716 | |
| 717 | ORE.emit(RemarkBuilder: [&]() { |
| 718 | return OptimizationRemarkAnalysis(DEBUG_TYPE, "CanBePartiallyInlined" , &CB) |
| 719 | << NV("Callee" , Cloner.OrigFunc) << " can be partially inlined into " |
| 720 | << NV("Caller" , Caller) << " with cost=" << NV("Cost" , IC.getCost()) |
| 721 | << " (threshold=" |
| 722 | << NV("Threshold" , IC.getCostDelta() + IC.getCost()) << ")" ; |
| 723 | }); |
| 724 | return true; |
| 725 | } |
| 726 | |
| 727 | // TODO: Ideally we should share Inliner's InlineCost Analysis code. |
| 728 | // For now use a simplified version. The returned 'InlineCost' will be used |
| 729 | // to esimate the size cost as well as runtime cost of the BB. |
| 730 | InstructionCost |
| 731 | PartialInlinerImpl::computeBBInlineCost(BasicBlock *BB, |
| 732 | TargetTransformInfo *TTI) { |
| 733 | InstructionCost InlineCost = 0; |
| 734 | const DataLayout &DL = BB->getDataLayout(); |
| 735 | int InstrCost = InlineConstants::getInstrCost(C: BB->getContext()); |
| 736 | for (Instruction &I : *BB) { |
| 737 | // Skip free instructions. |
| 738 | switch (I.getOpcode()) { |
| 739 | case Instruction::BitCast: |
| 740 | case Instruction::PtrToInt: |
| 741 | case Instruction::IntToPtr: |
| 742 | case Instruction::Alloca: |
| 743 | case Instruction::PHI: |
| 744 | continue; |
| 745 | case Instruction::GetElementPtr: |
| 746 | if (cast<GetElementPtrInst>(Val: &I)->hasAllZeroIndices()) |
| 747 | continue; |
| 748 | break; |
| 749 | default: |
| 750 | break; |
| 751 | } |
| 752 | |
| 753 | if (I.isLifetimeStartOrEnd()) |
| 754 | continue; |
| 755 | |
| 756 | if (auto *II = dyn_cast<IntrinsicInst>(Val: &I)) { |
| 757 | Intrinsic::ID IID = II->getIntrinsicID(); |
| 758 | SmallVector<Type *, 4> Tys; |
| 759 | FastMathFlags FMF; |
| 760 | for (Value *Val : II->args()) |
| 761 | Tys.push_back(Elt: Val->getType()); |
| 762 | |
| 763 | if (auto *FPMO = dyn_cast<FPMathOperator>(Val: II)) |
| 764 | FMF = FPMO->getFastMathFlags(); |
| 765 | |
| 766 | IntrinsicCostAttributes ICA(IID, II->getType(), Tys, FMF); |
| 767 | InlineCost += TTI->getIntrinsicInstrCost(ICA, CostKind: TTI::TCK_SizeAndLatency); |
| 768 | continue; |
| 769 | } |
| 770 | |
| 771 | if (CallInst *CI = dyn_cast<CallInst>(Val: &I)) { |
| 772 | InlineCost += getCallsiteCost(TTI: *TTI, Call: *CI, DL); |
| 773 | continue; |
| 774 | } |
| 775 | |
| 776 | if (InvokeInst *II = dyn_cast<InvokeInst>(Val: &I)) { |
| 777 | InlineCost += getCallsiteCost(TTI: *TTI, Call: *II, DL); |
| 778 | continue; |
| 779 | } |
| 780 | |
| 781 | if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: &I)) { |
| 782 | InlineCost += (SI->getNumCases() + 1) * InstrCost; |
| 783 | continue; |
| 784 | } |
| 785 | InlineCost += InstrCost; |
| 786 | } |
| 787 | |
| 788 | return InlineCost; |
| 789 | } |
| 790 | |
| 791 | std::tuple<InstructionCost, InstructionCost> |
| 792 | PartialInlinerImpl::computeOutliningCosts(FunctionCloner &Cloner) const { |
| 793 | InstructionCost OutliningFuncCallCost = 0, OutlinedFunctionCost = 0; |
| 794 | for (auto FuncBBPair : Cloner.OutlinedFunctions) { |
| 795 | Function *OutlinedFunc = FuncBBPair.first; |
| 796 | BasicBlock* OutliningCallBB = FuncBBPair.second; |
| 797 | // Now compute the cost of the call sequence to the outlined function |
| 798 | // 'OutlinedFunction' in BB 'OutliningCallBB': |
| 799 | auto *OutlinedFuncTTI = &GetTTI(*OutlinedFunc); |
| 800 | OutliningFuncCallCost += |
| 801 | computeBBInlineCost(BB: OutliningCallBB, TTI: OutlinedFuncTTI); |
| 802 | |
| 803 | // Now compute the cost of the extracted/outlined function itself: |
| 804 | for (BasicBlock &BB : *OutlinedFunc) |
| 805 | OutlinedFunctionCost += computeBBInlineCost(BB: &BB, TTI: OutlinedFuncTTI); |
| 806 | } |
| 807 | assert(OutlinedFunctionCost >= Cloner.OutlinedRegionCost && |
| 808 | "Outlined function cost should be no less than the outlined region" ); |
| 809 | |
| 810 | // The code extractor introduces a new root and exit stub blocks with |
| 811 | // additional unconditional branches. Those branches will be eliminated |
| 812 | // later with bb layout. The cost should be adjusted accordingly: |
| 813 | OutlinedFunctionCost -= |
| 814 | 2 * InlineConstants::getInstrCost(C: Cloner.OrigFunc->getContext()) * |
| 815 | Cloner.OutlinedFunctions.size(); |
| 816 | |
| 817 | InstructionCost OutliningRuntimeOverhead = |
| 818 | OutliningFuncCallCost + |
| 819 | (OutlinedFunctionCost - Cloner.OutlinedRegionCost) + |
| 820 | Opts.partial_inlining_extra_penalty; |
| 821 | |
| 822 | return std::make_tuple(args&: OutliningFuncCallCost, args&: OutliningRuntimeOverhead); |
| 823 | } |
| 824 | |
| 825 | // Create the callsite to profile count map which is |
| 826 | // used to update the original function's entry count, |
| 827 | // after the function is partially inlined into the callsite. |
| 828 | void PartialInlinerImpl::computeCallsiteToProfCountMap( |
| 829 | Function *DuplicateFunction, |
| 830 | DenseMap<User *, uint64_t> &CallSiteToProfCountMap) const { |
| 831 | std::vector<User *> Users(DuplicateFunction->user_begin(), |
| 832 | DuplicateFunction->user_end()); |
| 833 | Function *CurrentCaller = nullptr; |
| 834 | std::unique_ptr<BlockFrequencyInfo> TempBFI; |
| 835 | BlockFrequencyInfo *CurrentCallerBFI = nullptr; |
| 836 | |
| 837 | auto ComputeCurrBFI = [&,this](Function *Caller) { |
| 838 | // For the old pass manager: |
| 839 | if (!GetBFI) { |
| 840 | CycleInfo CI; |
| 841 | CI.compute(F&: *Caller); |
| 842 | BranchProbabilityInfo BPI(*Caller, CI); |
| 843 | TempBFI.reset(p: new BlockFrequencyInfo(*Caller, BPI, CI)); |
| 844 | CurrentCallerBFI = TempBFI.get(); |
| 845 | } else { |
| 846 | // New pass manager: |
| 847 | CurrentCallerBFI = &(GetBFI(*Caller)); |
| 848 | } |
| 849 | }; |
| 850 | |
| 851 | for (User *User : Users) { |
| 852 | CallBase *CB = getSupportedCallBase(U: User); |
| 853 | Function *Caller = CB->getCaller(); |
| 854 | if (CurrentCaller != Caller) { |
| 855 | CurrentCaller = Caller; |
| 856 | ComputeCurrBFI(Caller); |
| 857 | } else { |
| 858 | assert(CurrentCallerBFI && "CallerBFI is not set" ); |
| 859 | } |
| 860 | BasicBlock *CallBB = CB->getParent(); |
| 861 | auto Count = CurrentCallerBFI->getBlockProfileCount(BB: CallBB); |
| 862 | if (Count) |
| 863 | CallSiteToProfCountMap[User] = *Count; |
| 864 | else |
| 865 | CallSiteToProfCountMap[User] = 0; |
| 866 | } |
| 867 | } |
| 868 | |
| 869 | PartialInlinerImpl::FunctionCloner::( |
| 870 | Function *F, FunctionOutliningInfo *OI, OptimizationRemarkEmitter &ORE, |
| 871 | function_ref<AssumptionCache *(Function &)> LookupAC, |
| 872 | function_ref<TargetTransformInfo &(Function &)> GetTTI) |
| 873 | : OrigFunc(F), ORE(ORE), LookupAC(LookupAC), GetTTI(GetTTI) { |
| 874 | ClonedOI = std::make_unique<FunctionOutliningInfo>(); |
| 875 | |
| 876 | // Clone the function, so that we can hack away on it. |
| 877 | ValueToValueMapTy VMap; |
| 878 | ClonedFunc = CloneFunction(F, VMap); |
| 879 | |
| 880 | ClonedOI->ReturnBlock = cast<BasicBlock>(Val&: VMap[OI->ReturnBlock]); |
| 881 | ClonedOI->NonReturnBlock = cast<BasicBlock>(Val&: VMap[OI->NonReturnBlock]); |
| 882 | for (BasicBlock *BB : OI->Entries) |
| 883 | ClonedOI->Entries.push_back(Elt: cast<BasicBlock>(Val&: VMap[BB])); |
| 884 | |
| 885 | for (BasicBlock *E : OI->ReturnBlockPreds) { |
| 886 | BasicBlock *NewE = cast<BasicBlock>(Val&: VMap[E]); |
| 887 | ClonedOI->ReturnBlockPreds.push_back(Elt: NewE); |
| 888 | } |
| 889 | // Go ahead and update all uses to the duplicate, so that we can just |
| 890 | // use the inliner functionality when we're done hacking. |
| 891 | F->replaceAllUsesWith(V: ClonedFunc); |
| 892 | } |
| 893 | |
| 894 | PartialInlinerImpl::FunctionCloner::( |
| 895 | Function *F, FunctionOutliningMultiRegionInfo *OI, |
| 896 | OptimizationRemarkEmitter &ORE, |
| 897 | function_ref<AssumptionCache *(Function &)> LookupAC, |
| 898 | function_ref<TargetTransformInfo &(Function &)> GetTTI) |
| 899 | : OrigFunc(F), ORE(ORE), LookupAC(LookupAC), GetTTI(GetTTI) { |
| 900 | ClonedOMRI = std::make_unique<FunctionOutliningMultiRegionInfo>(); |
| 901 | |
| 902 | // Clone the function, so that we can hack away on it. |
| 903 | ValueToValueMapTy VMap; |
| 904 | ClonedFunc = CloneFunction(F, VMap); |
| 905 | |
| 906 | // Go through all Outline Candidate Regions and update all BasicBlock |
| 907 | // information. |
| 908 | for (const FunctionOutliningMultiRegionInfo::OutlineRegionInfo &RegionInfo : |
| 909 | OI->ORI) { |
| 910 | SmallVector<BasicBlock *, 8> Region; |
| 911 | for (BasicBlock *BB : RegionInfo.Region) |
| 912 | Region.push_back(Elt: cast<BasicBlock>(Val&: VMap[BB])); |
| 913 | |
| 914 | BasicBlock *NewEntryBlock = cast<BasicBlock>(Val&: VMap[RegionInfo.EntryBlock]); |
| 915 | BasicBlock *NewExitBlock = cast<BasicBlock>(Val&: VMap[RegionInfo.ExitBlock]); |
| 916 | BasicBlock *NewReturnBlock = nullptr; |
| 917 | if (RegionInfo.ReturnBlock) |
| 918 | NewReturnBlock = cast<BasicBlock>(Val&: VMap[RegionInfo.ReturnBlock]); |
| 919 | FunctionOutliningMultiRegionInfo::OutlineRegionInfo MappedRegionInfo( |
| 920 | Region, NewEntryBlock, NewExitBlock, NewReturnBlock); |
| 921 | ClonedOMRI->ORI.push_back(Elt: MappedRegionInfo); |
| 922 | } |
| 923 | // Go ahead and update all uses to the duplicate, so that we can just |
| 924 | // use the inliner functionality when we're done hacking. |
| 925 | F->replaceAllUsesWith(V: ClonedFunc); |
| 926 | } |
| 927 | |
| 928 | void PartialInlinerImpl::FunctionCloner::normalizeReturnBlock() const { |
| 929 | auto GetFirstPHI = [](BasicBlock *BB) { |
| 930 | BasicBlock::iterator I = BB->begin(); |
| 931 | PHINode *FirstPhi = nullptr; |
| 932 | while (I != BB->end()) { |
| 933 | PHINode *Phi = dyn_cast<PHINode>(Val&: I); |
| 934 | if (!Phi) |
| 935 | break; |
| 936 | if (!FirstPhi) { |
| 937 | FirstPhi = Phi; |
| 938 | break; |
| 939 | } |
| 940 | } |
| 941 | return FirstPhi; |
| 942 | }; |
| 943 | |
| 944 | // Shouldn't need to normalize PHIs if we're not outlining non-early return |
| 945 | // blocks. |
| 946 | if (!ClonedOI) |
| 947 | return; |
| 948 | |
| 949 | // Special hackery is needed with PHI nodes that have inputs from more than |
| 950 | // one extracted block. For simplicity, just split the PHIs into a two-level |
| 951 | // sequence of PHIs, some of which will go in the extracted region, and some |
| 952 | // of which will go outside. |
| 953 | BasicBlock *PreReturn = ClonedOI->ReturnBlock; |
| 954 | // only split block when necessary: |
| 955 | PHINode *FirstPhi = GetFirstPHI(PreReturn); |
| 956 | unsigned NumPredsFromEntries = ClonedOI->ReturnBlockPreds.size(); |
| 957 | |
| 958 | if (!FirstPhi || FirstPhi->getNumIncomingValues() <= NumPredsFromEntries + 1) |
| 959 | return; |
| 960 | |
| 961 | auto IsTrivialPhi = [](PHINode *PN) -> Value * { |
| 962 | if (llvm::all_equal(Range: PN->incoming_values())) |
| 963 | return PN->getIncomingValue(i: 0); |
| 964 | return nullptr; |
| 965 | }; |
| 966 | |
| 967 | ClonedOI->ReturnBlock = ClonedOI->ReturnBlock->splitBasicBlock( |
| 968 | I: ClonedOI->ReturnBlock->getFirstNonPHIIt()); |
| 969 | BasicBlock::iterator I = PreReturn->begin(); |
| 970 | BasicBlock::iterator Ins = ClonedOI->ReturnBlock->begin(); |
| 971 | SmallVector<Instruction *, 4> DeadPhis; |
| 972 | while (I != PreReturn->end()) { |
| 973 | PHINode *OldPhi = dyn_cast<PHINode>(Val&: I); |
| 974 | if (!OldPhi) |
| 975 | break; |
| 976 | |
| 977 | PHINode *RetPhi = |
| 978 | PHINode::Create(Ty: OldPhi->getType(), NumReservedValues: NumPredsFromEntries + 1, NameStr: "" ); |
| 979 | RetPhi->insertBefore(InsertPos: Ins); |
| 980 | OldPhi->replaceAllUsesWith(V: RetPhi); |
| 981 | Ins = ClonedOI->ReturnBlock->getFirstNonPHIIt(); |
| 982 | |
| 983 | RetPhi->addIncoming(V: &*I, BB: PreReturn); |
| 984 | for (BasicBlock *E : ClonedOI->ReturnBlockPreds) { |
| 985 | RetPhi->addIncoming(V: OldPhi->getIncomingValueForBlock(BB: E), BB: E); |
| 986 | OldPhi->removeIncomingValue(BB: E); |
| 987 | } |
| 988 | |
| 989 | // After incoming values splitting, the old phi may become trivial. |
| 990 | // Keeping the trivial phi can introduce definition inside the outline |
| 991 | // region which is live-out, causing necessary overhead (load, store |
| 992 | // arg passing etc). |
| 993 | if (auto *OldPhiVal = IsTrivialPhi(OldPhi)) { |
| 994 | OldPhi->replaceAllUsesWith(V: OldPhiVal); |
| 995 | DeadPhis.push_back(Elt: OldPhi); |
| 996 | } |
| 997 | ++I; |
| 998 | } |
| 999 | for (auto *DP : DeadPhis) |
| 1000 | DP->eraseFromParent(); |
| 1001 | |
| 1002 | for (auto *E : ClonedOI->ReturnBlockPreds) |
| 1003 | E->getTerminator()->replaceUsesOfWith(From: PreReturn, To: ClonedOI->ReturnBlock); |
| 1004 | } |
| 1005 | |
| 1006 | bool PartialInlinerImpl::FunctionCloner::doMultiRegionFunctionOutlining( |
| 1007 | const IPOOptions &Opts) { |
| 1008 | auto ComputeRegionCost = |
| 1009 | [&](SmallVectorImpl<BasicBlock *> &Region) -> InstructionCost { |
| 1010 | InstructionCost Cost = 0; |
| 1011 | for (BasicBlock* BB : Region) |
| 1012 | Cost += computeBBInlineCost(BB, TTI: &GetTTI(*BB->getParent())); |
| 1013 | return Cost; |
| 1014 | }; |
| 1015 | |
| 1016 | assert(ClonedOMRI && "Expecting OutlineInfo for multi region outline" ); |
| 1017 | |
| 1018 | if (ClonedOMRI->ORI.empty()) |
| 1019 | return false; |
| 1020 | |
| 1021 | // The CodeExtractor needs a dominator tree. |
| 1022 | DominatorTree DT; |
| 1023 | DT.recalculate(Func&: *ClonedFunc); |
| 1024 | |
| 1025 | // Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo. |
| 1026 | CycleInfo CI; |
| 1027 | CI.compute(F&: *ClonedFunc); |
| 1028 | BranchProbabilityInfo BPI(*ClonedFunc, CI); |
| 1029 | ClonedFuncBFI.reset(p: new BlockFrequencyInfo(*ClonedFunc, BPI, CI)); |
| 1030 | |
| 1031 | // Cache and recycle the CodeExtractor analysis to avoid O(n^2) compile-time. |
| 1032 | CodeExtractorAnalysisCache CEAC(*ClonedFunc); |
| 1033 | |
| 1034 | SetVector<Value *> Inputs, Outputs, Sinks; |
| 1035 | for (FunctionOutliningMultiRegionInfo::OutlineRegionInfo RegionInfo : |
| 1036 | ClonedOMRI->ORI) { |
| 1037 | InstructionCost CurrentOutlinedRegionCost = |
| 1038 | ComputeRegionCost(RegionInfo.Region); |
| 1039 | |
| 1040 | CodeExtractor CE(RegionInfo.Region, &DT, /*AggregateArgs*/ false, |
| 1041 | ClonedFuncBFI.get(), &BPI, |
| 1042 | LookupAC(*RegionInfo.EntryBlock->getParent()), |
| 1043 | /* AllowVarargs */ false, /* AllowAlloca */ false, |
| 1044 | /* AllocaBlock */ nullptr, /* DeallocationBlocks */ {}, |
| 1045 | /* Suffix */ "" , /* ArgsInZeroAddressSpace */ false, |
| 1046 | /* VoidReturnWithSingleOutput */ false); |
| 1047 | |
| 1048 | CE.findInputsOutputs(Inputs, Outputs, Allocas: Sinks); |
| 1049 | |
| 1050 | LLVM_DEBUG({ |
| 1051 | dbgs() << "inputs: " << Inputs.size() << "\n" ; |
| 1052 | dbgs() << "outputs: " << Outputs.size() << "\n" ; |
| 1053 | for (Value *value : Inputs) |
| 1054 | dbgs() << "value used in func: " << *value << "\n" ; |
| 1055 | for (Value *output : Outputs) |
| 1056 | dbgs() << "instr used in func: " << *output << "\n" ; |
| 1057 | }); |
| 1058 | |
| 1059 | // Do not extract regions that have live exit variables. |
| 1060 | if (Outputs.size() > 0 && !Opts.pi_force_live_exit_outline) |
| 1061 | continue; |
| 1062 | |
| 1063 | if (Function *OutlinedFunc = CE.extractCodeRegion(CEAC)) { |
| 1064 | CallBase *OCS = PartialInlinerImpl::getOneCallSiteTo(F&: *OutlinedFunc); |
| 1065 | BasicBlock *OutliningCallBB = OCS->getParent(); |
| 1066 | assert(OutliningCallBB->getParent() == ClonedFunc); |
| 1067 | OutlinedFunctions.push_back(Elt: std::make_pair(x&: OutlinedFunc,y&: OutliningCallBB)); |
| 1068 | NumColdRegionsOutlined++; |
| 1069 | OutlinedRegionCost += CurrentOutlinedRegionCost; |
| 1070 | |
| 1071 | if (Opts.pi_mark_coldcc) { |
| 1072 | OutlinedFunc->setCallingConv(CallingConv::Cold); |
| 1073 | OCS->setCallingConv(CallingConv::Cold); |
| 1074 | } |
| 1075 | } else |
| 1076 | ORE.emit(RemarkBuilder: [&]() { |
| 1077 | return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed" , |
| 1078 | &RegionInfo.Region.front()->front()) |
| 1079 | << "Failed to extract region at block " |
| 1080 | << ore::NV("Block" , RegionInfo.Region.front()); |
| 1081 | }); |
| 1082 | } |
| 1083 | |
| 1084 | return !OutlinedFunctions.empty(); |
| 1085 | } |
| 1086 | |
| 1087 | Function * |
| 1088 | PartialInlinerImpl::FunctionCloner::doSingleRegionFunctionOutlining() { |
| 1089 | // Returns true if the block is to be partial inlined into the caller |
| 1090 | // (i.e. not to be extracted to the out of line function) |
| 1091 | auto ToBeInlined = [&, this](BasicBlock *BB) { |
| 1092 | return BB == ClonedOI->ReturnBlock || |
| 1093 | llvm::is_contained(Range&: ClonedOI->Entries, Element: BB); |
| 1094 | }; |
| 1095 | |
| 1096 | assert(ClonedOI && "Expecting OutlineInfo for single region outline" ); |
| 1097 | // The CodeExtractor needs a dominator tree. |
| 1098 | DominatorTree DT; |
| 1099 | DT.recalculate(Func&: *ClonedFunc); |
| 1100 | |
| 1101 | // Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo. |
| 1102 | CycleInfo CI; |
| 1103 | CI.compute(F&: *ClonedFunc); |
| 1104 | BranchProbabilityInfo BPI(*ClonedFunc, CI); |
| 1105 | ClonedFuncBFI.reset(p: new BlockFrequencyInfo(*ClonedFunc, BPI, CI)); |
| 1106 | |
| 1107 | // Gather up the blocks that we're going to extract. |
| 1108 | std::vector<BasicBlock *> ; |
| 1109 | auto *ClonedFuncTTI = &GetTTI(*ClonedFunc); |
| 1110 | ToExtract.push_back(x: ClonedOI->NonReturnBlock); |
| 1111 | OutlinedRegionCost += PartialInlinerImpl::computeBBInlineCost( |
| 1112 | BB: ClonedOI->NonReturnBlock, TTI: ClonedFuncTTI); |
| 1113 | for (BasicBlock *BB : depth_first(G: &ClonedFunc->getEntryBlock())) |
| 1114 | if (!ToBeInlined(BB) && BB != ClonedOI->NonReturnBlock) { |
| 1115 | ToExtract.push_back(x: BB); |
| 1116 | // FIXME: the code extractor may hoist/sink more code |
| 1117 | // into the outlined function which may make the outlining |
| 1118 | // overhead (the difference of the outlined function cost |
| 1119 | // and OutliningRegionCost) look larger. |
| 1120 | OutlinedRegionCost += computeBBInlineCost(BB, TTI: ClonedFuncTTI); |
| 1121 | } |
| 1122 | |
| 1123 | // Extract the body of the if. |
| 1124 | CodeExtractorAnalysisCache CEAC(*ClonedFunc); |
| 1125 | Function *OutlinedFunc = |
| 1126 | CodeExtractor(ToExtract, &DT, /*AggregateArgs*/ false, |
| 1127 | ClonedFuncBFI.get(), &BPI, LookupAC(*ClonedFunc), |
| 1128 | /* AllowVarargs */ true, /* AllowAlloca */ false, |
| 1129 | /* AllocaBlock */ nullptr, /* DeallocationBlocks */ {}, |
| 1130 | /* Suffix */ "" , /* ArgsInZeroAddressSpace */ false, |
| 1131 | /* VoidReturnWithSingleOutput */ false) |
| 1132 | .extractCodeRegion(CEAC); |
| 1133 | |
| 1134 | if (OutlinedFunc) { |
| 1135 | BasicBlock *OutliningCallBB = |
| 1136 | PartialInlinerImpl::getOneCallSiteTo(F&: *OutlinedFunc)->getParent(); |
| 1137 | assert(OutliningCallBB->getParent() == ClonedFunc); |
| 1138 | OutlinedFunctions.push_back(Elt: std::make_pair(x&: OutlinedFunc, y&: OutliningCallBB)); |
| 1139 | } else |
| 1140 | ORE.emit(RemarkBuilder: [&]() { |
| 1141 | return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed" , |
| 1142 | &ToExtract.front()->front()) |
| 1143 | << "Failed to extract region at block " |
| 1144 | << ore::NV("Block" , ToExtract.front()); |
| 1145 | }); |
| 1146 | |
| 1147 | return OutlinedFunc; |
| 1148 | } |
| 1149 | |
| 1150 | PartialInlinerImpl::FunctionCloner::~FunctionCloner() { |
| 1151 | // Ditch the duplicate, since we're done with it, and rewrite all remaining |
| 1152 | // users (function pointers, etc.) back to the original function. |
| 1153 | ClonedFunc->replaceAllUsesWith(V: OrigFunc); |
| 1154 | ClonedFunc->eraseFromParent(); |
| 1155 | if (!IsFunctionInlined) { |
| 1156 | // Remove each function that was speculatively created if there is no |
| 1157 | // reference. |
| 1158 | for (auto FuncBBPair : OutlinedFunctions) { |
| 1159 | Function *Func = FuncBBPair.first; |
| 1160 | Func->eraseFromParent(); |
| 1161 | } |
| 1162 | } |
| 1163 | } |
| 1164 | |
| 1165 | std::pair<bool, Function *> PartialInlinerImpl::unswitchFunction(Function &F) { |
| 1166 | if (F.hasAddressTaken()) |
| 1167 | return {false, nullptr}; |
| 1168 | |
| 1169 | // Let inliner handle it |
| 1170 | if (F.hasFnAttribute(Kind: Attribute::AlwaysInline)) |
| 1171 | return {false, nullptr}; |
| 1172 | |
| 1173 | if (F.isNoInline()) |
| 1174 | return {false, nullptr}; |
| 1175 | |
| 1176 | if (PSI.isFunctionEntryCold(F: &F)) |
| 1177 | return {false, nullptr}; |
| 1178 | |
| 1179 | if (F.users().empty()) |
| 1180 | return {false, nullptr}; |
| 1181 | |
| 1182 | OptimizationRemarkEmitter ORE(&F); |
| 1183 | |
| 1184 | // Only try to outline cold regions if we have a profile summary, which |
| 1185 | // implies we have profiling information. |
| 1186 | if (PSI.hasProfileSummary() && F.hasProfileData() && |
| 1187 | Opts.mr_partial_inlining) { |
| 1188 | std::unique_ptr<FunctionOutliningMultiRegionInfo> OMRI = |
| 1189 | computeOutliningColdRegionsInfo(F, ORE); |
| 1190 | if (OMRI) { |
| 1191 | FunctionCloner Cloner(&F, OMRI.get(), ORE, LookupAssumptionCache, GetTTI); |
| 1192 | |
| 1193 | LLVM_DEBUG({ |
| 1194 | dbgs() << "HotCountThreshold = " << PSI.getHotCountThreshold() << "\n" ; |
| 1195 | dbgs() << "ColdCountThreshold = " << PSI.getColdCountThreshold() |
| 1196 | << "\n" ; |
| 1197 | }); |
| 1198 | |
| 1199 | bool DidOutline = Cloner.doMultiRegionFunctionOutlining(Opts); |
| 1200 | |
| 1201 | if (DidOutline) { |
| 1202 | LLVM_DEBUG({ |
| 1203 | dbgs() << ">>>>>> Outlined (Cloned) Function >>>>>>\n" ; |
| 1204 | Cloner.ClonedFunc->print(dbgs()); |
| 1205 | dbgs() << "<<<<<< Outlined (Cloned) Function <<<<<<\n" ; |
| 1206 | }); |
| 1207 | |
| 1208 | if (tryPartialInline(Cloner)) |
| 1209 | return {true, nullptr}; |
| 1210 | } |
| 1211 | } |
| 1212 | } |
| 1213 | |
| 1214 | // Fall-thru to regular partial inlining if we: |
| 1215 | // i) can't find any cold regions to outline, or |
| 1216 | // ii) can't inline the outlined function anywhere. |
| 1217 | std::unique_ptr<FunctionOutliningInfo> OI = computeOutliningInfo(F); |
| 1218 | if (!OI) |
| 1219 | return {false, nullptr}; |
| 1220 | |
| 1221 | FunctionCloner Cloner(&F, OI.get(), ORE, LookupAssumptionCache, GetTTI); |
| 1222 | Cloner.normalizeReturnBlock(); |
| 1223 | |
| 1224 | Function *OutlinedFunction = Cloner.doSingleRegionFunctionOutlining(); |
| 1225 | |
| 1226 | if (!OutlinedFunction) |
| 1227 | return {false, nullptr}; |
| 1228 | |
| 1229 | if (tryPartialInline(Cloner)) |
| 1230 | return {true, OutlinedFunction}; |
| 1231 | |
| 1232 | return {false, nullptr}; |
| 1233 | } |
| 1234 | |
| 1235 | bool PartialInlinerImpl::tryPartialInline(FunctionCloner &Cloner) { |
| 1236 | if (Cloner.OutlinedFunctions.empty()) |
| 1237 | return false; |
| 1238 | |
| 1239 | auto OutliningCosts = computeOutliningCosts(Cloner); |
| 1240 | |
| 1241 | InstructionCost SizeCost = std::get<0>(t&: OutliningCosts); |
| 1242 | InstructionCost NonWeightedRcost = std::get<1>(t&: OutliningCosts); |
| 1243 | |
| 1244 | assert(SizeCost.isValid() && NonWeightedRcost.isValid() && |
| 1245 | "Expected valid costs" ); |
| 1246 | |
| 1247 | // Only calculate RelativeToEntryFreq when we are doing single region |
| 1248 | // outlining. |
| 1249 | BranchProbability RelativeToEntryFreq; |
| 1250 | if (Cloner.ClonedOI) |
| 1251 | RelativeToEntryFreq = getOutliningCallBBRelativeFreq(Cloner); |
| 1252 | else |
| 1253 | // RelativeToEntryFreq doesn't make sense when we have more than one |
| 1254 | // outlined call because each call will have a different relative frequency |
| 1255 | // to the entry block. We can consider using the average, but the |
| 1256 | // usefulness of that information is questionable. For now, assume we never |
| 1257 | // execute the calls to outlined functions. |
| 1258 | RelativeToEntryFreq = BranchProbability(0, 1); |
| 1259 | |
| 1260 | BlockFrequency WeightedRcost = |
| 1261 | BlockFrequency(NonWeightedRcost.getValue()) * RelativeToEntryFreq; |
| 1262 | |
| 1263 | // The call sequence(s) to the outlined function(s) are larger than the sum of |
| 1264 | // the original outlined region size(s), it does not increase the chances of |
| 1265 | // inlining the function with outlining (The inliner uses the size increase to |
| 1266 | // model the cost of inlining a callee). |
| 1267 | if (!Opts.skip_partial_inlining_cost_analysis && |
| 1268 | Cloner.OutlinedRegionCost < SizeCost) { |
| 1269 | OptimizationRemarkEmitter OrigFuncORE(Cloner.OrigFunc); |
| 1270 | DebugLoc DLoc; |
| 1271 | BasicBlock *Block; |
| 1272 | std::tie(args&: DLoc, args&: Block) = getOneDebugLoc(F&: *Cloner.ClonedFunc); |
| 1273 | OrigFuncORE.emit(RemarkBuilder: [&]() { |
| 1274 | return OptimizationRemarkAnalysis(DEBUG_TYPE, "OutlineRegionTooSmall" , |
| 1275 | DLoc, Block) |
| 1276 | << ore::NV("Function" , Cloner.OrigFunc) |
| 1277 | << " not partially inlined into callers (Original Size = " |
| 1278 | << ore::NV("OutlinedRegionOriginalSize" , Cloner.OutlinedRegionCost) |
| 1279 | << ", Size of call sequence to outlined function = " |
| 1280 | << ore::NV("NewSize" , SizeCost) << ")" ; |
| 1281 | }); |
| 1282 | return false; |
| 1283 | } |
| 1284 | |
| 1285 | assert(Cloner.OrigFunc->users().empty() && |
| 1286 | "F's users should all be replaced!" ); |
| 1287 | |
| 1288 | std::vector<User *> Users(Cloner.ClonedFunc->user_begin(), |
| 1289 | Cloner.ClonedFunc->user_end()); |
| 1290 | |
| 1291 | DenseMap<User *, uint64_t> CallSiteToProfCountMap; |
| 1292 | auto CalleeEntryCount = Cloner.OrigFunc->getEntryCount(); |
| 1293 | if (CalleeEntryCount) |
| 1294 | computeCallsiteToProfCountMap(DuplicateFunction: Cloner.ClonedFunc, CallSiteToProfCountMap); |
| 1295 | |
| 1296 | uint64_t CalleeEntryCountV = (CalleeEntryCount ? *CalleeEntryCount : 0); |
| 1297 | |
| 1298 | bool AnyInline = false; |
| 1299 | for (User *User : Users) { |
| 1300 | CallBase *CB = getSupportedCallBase(U: User); |
| 1301 | |
| 1302 | if (isLimitReached()) |
| 1303 | continue; |
| 1304 | |
| 1305 | OptimizationRemarkEmitter CallerORE(CB->getCaller()); |
| 1306 | if (!shouldPartialInline(CB&: *CB, Cloner, WeightedOutliningRcost: WeightedRcost, ORE&: CallerORE)) |
| 1307 | continue; |
| 1308 | |
| 1309 | // Construct remark before doing the inlining, as after successful inlining |
| 1310 | // the callsite is removed. |
| 1311 | OptimizationRemark OR(DEBUG_TYPE, "PartiallyInlined" , CB); |
| 1312 | OR << ore::NV("Callee" , Cloner.OrigFunc) << " partially inlined into " |
| 1313 | << ore::NV("Caller" , CB->getCaller()); |
| 1314 | |
| 1315 | InlineFunctionInfo IFI(GetAssumptionCache, &PSI); |
| 1316 | // We can only forward varargs when we outlined a single region, else we |
| 1317 | // bail on vararg functions. |
| 1318 | if (!InlineFunction(CB&: *CB, IFI, /*MergeAttributes=*/false, CalleeAAR: nullptr, |
| 1319 | /*InsertLifetime=*/true, /*TrackInlineHistory=*/true, |
| 1320 | ForwardVarArgsTo: (Cloner.ClonedOI ? Cloner.OutlinedFunctions.back().first |
| 1321 | : nullptr)) |
| 1322 | .isSuccess()) |
| 1323 | continue; |
| 1324 | |
| 1325 | CallerORE.emit(OptDiag&: OR); |
| 1326 | |
| 1327 | // Now update the entry count: |
| 1328 | if (CalleeEntryCountV) { |
| 1329 | if (auto It = CallSiteToProfCountMap.find(Val: User); |
| 1330 | It != CallSiteToProfCountMap.end()) { |
| 1331 | uint64_t CallSiteCount = It->second; |
| 1332 | CalleeEntryCountV -= std::min(a: CalleeEntryCountV, b: CallSiteCount); |
| 1333 | } |
| 1334 | } |
| 1335 | |
| 1336 | AnyInline = true; |
| 1337 | NumPartialInlining++; |
| 1338 | // Update the stats |
| 1339 | if (Cloner.ClonedOI) |
| 1340 | NumPartialInlined++; |
| 1341 | else |
| 1342 | NumColdOutlinePartialInlined++; |
| 1343 | } |
| 1344 | |
| 1345 | if (AnyInline) { |
| 1346 | Cloner.IsFunctionInlined = true; |
| 1347 | if (CalleeEntryCount) |
| 1348 | Cloner.OrigFunc->setEntryCount(Count: CalleeEntryCountV); |
| 1349 | OptimizationRemarkEmitter OrigFuncORE(Cloner.OrigFunc); |
| 1350 | OrigFuncORE.emit(RemarkBuilder: [&]() { |
| 1351 | return OptimizationRemark(DEBUG_TYPE, "PartiallyInlined" , Cloner.OrigFunc) |
| 1352 | << "Partially inlined into at least one caller" ; |
| 1353 | }); |
| 1354 | } |
| 1355 | |
| 1356 | return AnyInline; |
| 1357 | } |
| 1358 | |
| 1359 | bool PartialInlinerImpl::run(Module &M) { |
| 1360 | if (!Opts.partial_inlining) |
| 1361 | return false; |
| 1362 | |
| 1363 | std::vector<Function *> Worklist; |
| 1364 | Worklist.reserve(n: M.size()); |
| 1365 | for (Function &F : M) |
| 1366 | if (!F.use_empty() && !F.isDeclaration()) |
| 1367 | Worklist.push_back(x: &F); |
| 1368 | |
| 1369 | bool Changed = false; |
| 1370 | while (!Worklist.empty()) { |
| 1371 | Function *CurrFunc = Worklist.back(); |
| 1372 | Worklist.pop_back(); |
| 1373 | |
| 1374 | if (CurrFunc->use_empty()) |
| 1375 | continue; |
| 1376 | |
| 1377 | std::pair<bool, Function *> Result = unswitchFunction(F&: *CurrFunc); |
| 1378 | if (Result.second) |
| 1379 | Worklist.push_back(x: Result.second); |
| 1380 | Changed |= Result.first; |
| 1381 | } |
| 1382 | |
| 1383 | return Changed; |
| 1384 | } |
| 1385 | |
| 1386 | PreservedAnalyses PartialInlinerPass::run(Module &M, |
| 1387 | ModuleAnalysisManager &AM) { |
| 1388 | auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager(); |
| 1389 | |
| 1390 | auto GetAssumptionCache = [&FAM](Function &F) -> AssumptionCache & { |
| 1391 | return FAM.getResult<AssumptionAnalysis>(IR&: F); |
| 1392 | }; |
| 1393 | |
| 1394 | auto LookupAssumptionCache = [&FAM](Function &F) -> AssumptionCache * { |
| 1395 | return FAM.getCachedResult<AssumptionAnalysis>(IR&: F); |
| 1396 | }; |
| 1397 | |
| 1398 | auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & { |
| 1399 | return FAM.getResult<BlockFrequencyAnalysis>(IR&: F); |
| 1400 | }; |
| 1401 | |
| 1402 | auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & { |
| 1403 | return FAM.getResult<TargetIRAnalysis>(IR&: F); |
| 1404 | }; |
| 1405 | |
| 1406 | auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & { |
| 1407 | return FAM.getResult<TargetLibraryAnalysis>(IR&: F); |
| 1408 | }; |
| 1409 | |
| 1410 | ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(IR&: M); |
| 1411 | |
| 1412 | if (PartialInlinerImpl(getIPOOptions(M), GetAssumptionCache, |
| 1413 | LookupAssumptionCache, GetTTI, GetTLI, PSI, GetBFI) |
| 1414 | .run(M)) |
| 1415 | return PreservedAnalyses::none(); |
| 1416 | return PreservedAnalyses::all(); |
| 1417 | } |
| 1418 | |