| 1 | //===- StructurizeCFG.cpp -------------------------------------------------===// |
| 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 | #include "llvm/Transforms/Scalar/StructurizeCFG.h" |
| 10 | #include "ScalarOptions.h" |
| 11 | #include "llvm/ADT/DenseMap.h" |
| 12 | #include "llvm/ADT/EquivalenceClasses.h" |
| 13 | #include "llvm/ADT/MapVector.h" |
| 14 | #include "llvm/ADT/SCCIterator.h" |
| 15 | #include "llvm/ADT/STLExtras.h" |
| 16 | #include "llvm/ADT/SmallPtrSet.h" |
| 17 | #include "llvm/ADT/SmallVector.h" |
| 18 | #include "llvm/Analysis/InstructionSimplify.h" |
| 19 | #include "llvm/Analysis/RegionInfo.h" |
| 20 | #include "llvm/Analysis/RegionIterator.h" |
| 21 | #include "llvm/Analysis/TargetTransformInfo.h" |
| 22 | #include "llvm/Analysis/UniformityAnalysis.h" |
| 23 | #include "llvm/IR/BasicBlock.h" |
| 24 | #include "llvm/IR/CFG.h" |
| 25 | #include "llvm/IR/Constants.h" |
| 26 | #include "llvm/IR/Dominators.h" |
| 27 | #include "llvm/IR/Function.h" |
| 28 | #include "llvm/IR/InstrTypes.h" |
| 29 | #include "llvm/IR/Instruction.h" |
| 30 | #include "llvm/IR/Instructions.h" |
| 31 | #include "llvm/IR/Metadata.h" |
| 32 | #include "llvm/IR/PassManager.h" |
| 33 | #include "llvm/IR/PatternMatch.h" |
| 34 | #include "llvm/IR/ProfDataUtils.h" |
| 35 | #include "llvm/IR/Type.h" |
| 36 | #include "llvm/IR/Use.h" |
| 37 | #include "llvm/IR/Value.h" |
| 38 | #include "llvm/IR/ValueHandle.h" |
| 39 | #include "llvm/InitializePasses.h" |
| 40 | #include "llvm/Pass.h" |
| 41 | #include "llvm/Support/Casting.h" |
| 42 | #include "llvm/Support/Debug.h" |
| 43 | #include "llvm/Support/raw_ostream.h" |
| 44 | #include "llvm/Transforms/Scalar.h" |
| 45 | #include "llvm/Transforms/Utils.h" |
| 46 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
| 47 | #include "llvm/Transforms/Utils/Local.h" |
| 48 | #include "llvm/Transforms/Utils/SSAUpdater.h" |
| 49 | #include "llvm/Transforms/Utils/SSAUpdaterBulk.h" |
| 50 | #include <cassert> |
| 51 | #include <utility> |
| 52 | |
| 53 | using namespace llvm; |
| 54 | using namespace llvm::PatternMatch; |
| 55 | |
| 56 | #define DEBUG_TYPE "structurizecfg" |
| 57 | |
| 58 | // The name for newly created blocks. |
| 59 | const char FlowBlockName[] = "Flow" ; |
| 60 | |
| 61 | namespace { |
| 62 | |
| 63 | // Definition of the complex types used in this pass. |
| 64 | |
| 65 | using BBValuePair = std::pair<BasicBlock *, Value *>; |
| 66 | |
| 67 | using RNVector = SmallVector<RegionNode *, 8>; |
| 68 | using BBVector = SmallVector<BasicBlock *, 8>; |
| 69 | // Branch paired with the block whose predicates define its condition. |
| 70 | using BranchVector = SmallVector<std::pair<CondBrInst *, BasicBlock *>, 8>; |
| 71 | using BBValueVector = SmallVector<BBValuePair, 2>; |
| 72 | |
| 73 | using BBSet = SmallPtrSet<BasicBlock *, 8>; |
| 74 | |
| 75 | using PhiMap = MapVector<PHINode *, BBValueVector>; |
| 76 | using BB2BBVecMap = MapVector<BasicBlock *, BBVector>; |
| 77 | |
| 78 | using BBPhiMap = DenseMap<BasicBlock *, PhiMap>; |
| 79 | |
| 80 | using MaybeCondBranchWeights = std::optional<class CondBranchWeights>; |
| 81 | |
| 82 | class CondBranchWeights { |
| 83 | uint32_t TrueWeight; |
| 84 | uint32_t FalseWeight; |
| 85 | |
| 86 | CondBranchWeights(uint32_t T, uint32_t F) : TrueWeight(T), FalseWeight(F) {} |
| 87 | |
| 88 | public: |
| 89 | static MaybeCondBranchWeights tryParse(const CondBrInst &Br) { |
| 90 | uint64_t T, F; |
| 91 | if (!extractBranchWeights(I: Br, TrueVal&: T, FalseVal&: F)) |
| 92 | return std::nullopt; |
| 93 | |
| 94 | return CondBranchWeights(T, F); |
| 95 | } |
| 96 | |
| 97 | static void setMetadata(CondBrInst &Br, |
| 98 | const MaybeCondBranchWeights &Weights) { |
| 99 | if (!Weights) |
| 100 | return; |
| 101 | uint32_t Arr[] = {Weights->TrueWeight, Weights->FalseWeight}; |
| 102 | setBranchWeights(I&: Br, Weights: Arr, IsExpected: false); |
| 103 | } |
| 104 | |
| 105 | CondBranchWeights invert() const { |
| 106 | return CondBranchWeights{FalseWeight, TrueWeight}; |
| 107 | } |
| 108 | }; |
| 109 | |
| 110 | struct PredInfo { |
| 111 | Value *Pred; |
| 112 | MaybeCondBranchWeights Weights; |
| 113 | }; |
| 114 | |
| 115 | using BBPredicates = DenseMap<BasicBlock *, PredInfo>; |
| 116 | using PredMap = DenseMap<BasicBlock *, BBPredicates>; |
| 117 | using BB2BBMap = DenseMap<BasicBlock *, BasicBlock *>; |
| 118 | using Val2BBMap = DenseMap<Value *, BasicBlock *>; |
| 119 | |
| 120 | // A traits type that is intended to be used in graph algorithms. The graph |
| 121 | // traits starts at an entry node, and traverses the RegionNodes that are in |
| 122 | // the Nodes set. |
| 123 | struct SubGraphTraits { |
| 124 | using NodeRef = std::pair<RegionNode *, SmallDenseSet<RegionNode *> *>; |
| 125 | using BaseSuccIterator = GraphTraits<RegionNode *>::ChildIteratorType; |
| 126 | |
| 127 | // This wraps a set of Nodes into the iterator, so we know which edges to |
| 128 | // filter out. |
| 129 | class WrappedSuccIterator |
| 130 | : public iterator_adaptor_base< |
| 131 | WrappedSuccIterator, BaseSuccIterator, |
| 132 | std::iterator_traits<BaseSuccIterator>::iterator_category, NodeRef, |
| 133 | std::ptrdiff_t, NodeRef *, NodeRef> { |
| 134 | SmallDenseSet<RegionNode *> *Nodes; |
| 135 | |
| 136 | public: |
| 137 | WrappedSuccIterator(BaseSuccIterator It, SmallDenseSet<RegionNode *> *Nodes) |
| 138 | : iterator_adaptor_base(It), Nodes(Nodes) {} |
| 139 | |
| 140 | NodeRef operator*() const { return {*I, Nodes}; } |
| 141 | }; |
| 142 | |
| 143 | static bool filterAll(const NodeRef &N) { return true; } |
| 144 | static bool filterSet(const NodeRef &N) { return N.second->count(V: N.first); } |
| 145 | |
| 146 | using ChildIteratorType = |
| 147 | filter_iterator<WrappedSuccIterator, bool (*)(const NodeRef &)>; |
| 148 | |
| 149 | static NodeRef getEntryNode(Region *R) { |
| 150 | return {GraphTraits<Region *>::getEntryNode(R), nullptr}; |
| 151 | } |
| 152 | |
| 153 | static NodeRef getEntryNode(NodeRef N) { return N; } |
| 154 | |
| 155 | static iterator_range<ChildIteratorType> children(const NodeRef &N) { |
| 156 | auto *filter = N.second ? &filterSet : &filterAll; |
| 157 | return make_filter_range( |
| 158 | Range: make_range<WrappedSuccIterator>( |
| 159 | x: {GraphTraits<RegionNode *>::child_begin(N: N.first), N.second}, |
| 160 | y: {GraphTraits<RegionNode *>::child_end(N: N.first), N.second}), |
| 161 | Pred: filter); |
| 162 | } |
| 163 | |
| 164 | static ChildIteratorType child_begin(const NodeRef &N) { |
| 165 | return children(N).begin(); |
| 166 | } |
| 167 | |
| 168 | static ChildIteratorType child_end(const NodeRef &N) { |
| 169 | return children(N).end(); |
| 170 | } |
| 171 | }; |
| 172 | |
| 173 | /// Finds the nearest common dominator of a set of BasicBlocks. |
| 174 | /// |
| 175 | /// For every BB you add to the set, you can specify whether we "remember" the |
| 176 | /// block. When you get the common dominator, you can also ask whether it's one |
| 177 | /// of the blocks we remembered. |
| 178 | class NearestCommonDominator { |
| 179 | DominatorTree *DT; |
| 180 | BasicBlock *Result = nullptr; |
| 181 | bool ResultIsRemembered = false; |
| 182 | |
| 183 | /// Add BB to the resulting dominator. |
| 184 | void addBlock(BasicBlock *BB, bool Remember) { |
| 185 | if (!Result) { |
| 186 | Result = BB; |
| 187 | ResultIsRemembered = Remember; |
| 188 | return; |
| 189 | } |
| 190 | |
| 191 | BasicBlock *NewResult = DT->findNearestCommonDominator(A: Result, B: BB); |
| 192 | if (NewResult != Result) |
| 193 | ResultIsRemembered = false; |
| 194 | if (NewResult == BB) |
| 195 | ResultIsRemembered |= Remember; |
| 196 | Result = NewResult; |
| 197 | } |
| 198 | |
| 199 | public: |
| 200 | explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {} |
| 201 | |
| 202 | void addBlock(BasicBlock *BB) { |
| 203 | addBlock(BB, /* Remember = */ false); |
| 204 | } |
| 205 | |
| 206 | void addAndRememberBlock(BasicBlock *BB) { |
| 207 | addBlock(BB, /* Remember = */ true); |
| 208 | } |
| 209 | |
| 210 | /// Get the nearest common dominator of all the BBs added via addBlock() and |
| 211 | /// addAndRememberBlock(). |
| 212 | BasicBlock *result() { return Result; } |
| 213 | |
| 214 | /// Is the BB returned by getResult() one of the blocks we added to the set |
| 215 | /// with addAndRememberBlock()? |
| 216 | bool resultIsRememberedBlock() { return ResultIsRemembered; } |
| 217 | }; |
| 218 | |
| 219 | /// Transforms the control flow graph on one single entry/exit region |
| 220 | /// at a time. |
| 221 | /// |
| 222 | /// After the transform all "If"/"Then"/"Else" style control flow looks like |
| 223 | /// this: |
| 224 | /// |
| 225 | /// \verbatim |
| 226 | /// 1 |
| 227 | /// || |
| 228 | /// | | |
| 229 | /// 2 | |
| 230 | /// | / |
| 231 | /// |/ |
| 232 | /// 3 |
| 233 | /// || Where: |
| 234 | /// | | 1 = "If" block, calculates the condition |
| 235 | /// 4 | 2 = "Then" subregion, runs if the condition is true |
| 236 | /// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow |
| 237 | /// |/ 4 = "Else" optional subregion, runs if the condition is false |
| 238 | /// 5 5 = "End" block, also rejoins the control flow |
| 239 | /// \endverbatim |
| 240 | /// |
| 241 | /// Control flow is expressed as a branch where the true exit goes into the |
| 242 | /// "Then"/"Else" region, while the false exit skips the region |
| 243 | /// The condition for the optional "Else" region is expressed as a PHI node. |
| 244 | /// The incoming values of the PHI node are true for the "If" edge and false |
| 245 | /// for the "Then" edge. |
| 246 | /// |
| 247 | /// Additionally to that even complicated loops look like this: |
| 248 | /// |
| 249 | /// \verbatim |
| 250 | /// 1 |
| 251 | /// || |
| 252 | /// | | |
| 253 | /// 2 ^ Where: |
| 254 | /// | / 1 = "Entry" block |
| 255 | /// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block |
| 256 | /// 3 3 = "Flow" block, with back edge to entry block |
| 257 | /// | |
| 258 | /// \endverbatim |
| 259 | /// |
| 260 | /// The back edge of the "Flow" block is always on the false side of the branch |
| 261 | /// while the true side continues the general flow. So the loop condition |
| 262 | /// consist of a network of PHI nodes where the true incoming values expresses |
| 263 | /// breaks and the false values expresses continue states. |
| 264 | |
| 265 | class StructurizeCFG { |
| 266 | Type *Boolean; |
| 267 | ConstantInt *BoolTrue; |
| 268 | ConstantInt *BoolFalse; |
| 269 | Value *BoolPoison; |
| 270 | const TargetTransformInfo *TTI; |
| 271 | Function *Func; |
| 272 | Region *ParentRegion; |
| 273 | |
| 274 | DominatorTree *DT; |
| 275 | |
| 276 | SmallVector<RegionNode *, 8> Order; |
| 277 | BBSet Visited; |
| 278 | BBSet FlowSet; |
| 279 | |
| 280 | SmallVector<WeakVH, 8> AffectedPhis; |
| 281 | BBPhiMap DeletedPhis; |
| 282 | BB2BBVecMap AddedPhis; |
| 283 | |
| 284 | PredMap Predicates; |
| 285 | BranchVector Conditions; |
| 286 | |
| 287 | BB2BBMap Loops; |
| 288 | PredMap LoopPreds; |
| 289 | BranchVector LoopConds; |
| 290 | |
| 291 | Val2BBMap HoistedValues; |
| 292 | |
| 293 | RegionNode *PrevNode; |
| 294 | |
| 295 | void hoistZeroCostElseBlockPhiValues(BasicBlock *ElseBB, BasicBlock *ThenBB); |
| 296 | |
| 297 | bool isHoistableInstruction(Instruction *I, BasicBlock *BB, |
| 298 | BasicBlock *HoistTo); |
| 299 | |
| 300 | void orderNodes(); |
| 301 | |
| 302 | void analyzeLoops(RegionNode *N); |
| 303 | |
| 304 | PredInfo buildCondition(CondBrInst *Term, unsigned Idx, bool Invert); |
| 305 | |
| 306 | void gatherPredicates(RegionNode *N); |
| 307 | |
| 308 | void collectInfos(); |
| 309 | |
| 310 | void insertConditions(bool Loops, SSAUpdaterBulk &PhiInserter); |
| 311 | |
| 312 | void simplifyConditions(); |
| 313 | |
| 314 | void delPhiValues(BasicBlock *From, BasicBlock *To); |
| 315 | |
| 316 | void addPhiValues(BasicBlock *From, BasicBlock *To); |
| 317 | |
| 318 | void findUndefBlocks(BasicBlock *PHIBlock, |
| 319 | const SmallPtrSet<BasicBlock *, 8> &Incomings, |
| 320 | SmallVector<BasicBlock *> &UndefBlks) const; |
| 321 | |
| 322 | void mergeIfCompatible(EquivalenceClasses<PHINode *> &PhiClasses, PHINode *A, |
| 323 | PHINode *B); |
| 324 | |
| 325 | void setPhiValues(); |
| 326 | |
| 327 | void simplifyAffectedPhis(); |
| 328 | |
| 329 | void simplifyHoistedPhis(); |
| 330 | |
| 331 | DebugLoc killTerminator(BasicBlock *BB); |
| 332 | |
| 333 | void changeExit(RegionNode *Node, BasicBlock *NewExit, |
| 334 | bool IncludeDominator); |
| 335 | |
| 336 | BasicBlock *getNextFlow(BasicBlock *Dominator); |
| 337 | |
| 338 | std::pair<BasicBlock *, DebugLoc> needPrefix(bool NeedEmpty); |
| 339 | |
| 340 | BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed); |
| 341 | |
| 342 | void setPrevNode(BasicBlock *BB); |
| 343 | |
| 344 | bool dominatesPredicates(BasicBlock *BB, RegionNode *Node); |
| 345 | |
| 346 | bool isPredictableTrue(RegionNode *Node); |
| 347 | |
| 348 | void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd); |
| 349 | |
| 350 | void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd); |
| 351 | |
| 352 | void createFlow(); |
| 353 | |
| 354 | void rebuildSSA(); |
| 355 | |
| 356 | public: |
| 357 | void init(Region *R); |
| 358 | bool run(Region *R, DominatorTree *DT, const TargetTransformInfo *TTI); |
| 359 | bool makeUniformRegion(Region *R, const UniformityInfo &UA); |
| 360 | }; |
| 361 | |
| 362 | class StructurizeCFGLegacyPass : public FunctionPass { |
| 363 | bool SkipUniformRegions; |
| 364 | |
| 365 | public: |
| 366 | static char ID; |
| 367 | |
| 368 | explicit StructurizeCFGLegacyPass(bool SkipUniformRegions_ = false) |
| 369 | : FunctionPass(ID), SkipUniformRegions(SkipUniformRegions_) { |
| 370 | initializeStructurizeCFGLegacyPassPass(*PassRegistry::getPassRegistry()); |
| 371 | } |
| 372 | |
| 373 | bool runOnFunction(Function &F) override; |
| 374 | |
| 375 | StringRef getPassName() const override { return "Structurize control flow" ; } |
| 376 | |
| 377 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 378 | AU.addRequired<UniformityInfoWrapperPass>(); |
| 379 | AU.addRequired<DominatorTreeWrapperPass>(); |
| 380 | AU.addRequired<TargetTransformInfoWrapperPass>(); |
| 381 | AU.addRequired<RegionInfoPass>(); |
| 382 | |
| 383 | AU.addPreserved<DominatorTreeWrapperPass>(); |
| 384 | } |
| 385 | }; |
| 386 | |
| 387 | } // end anonymous namespace |
| 388 | |
| 389 | char StructurizeCFGLegacyPass::ID = 0; |
| 390 | |
| 391 | INITIALIZE_PASS_BEGIN(StructurizeCFGLegacyPass, "structurizecfg" , |
| 392 | "Structurize the CFG" , false, false) |
| 393 | INITIALIZE_PASS_DEPENDENCY(UniformityInfoWrapperPass) |
| 394 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
| 395 | INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) |
| 396 | INITIALIZE_PASS_DEPENDENCY(RegionInfoPass) |
| 397 | INITIALIZE_PASS_END(StructurizeCFGLegacyPass, "structurizecfg" , |
| 398 | "Structurize the CFG" , false, false) |
| 399 | |
| 400 | /// Checks whether an instruction is zero cost instruction and checks if the |
| 401 | /// operands are from different BB. If so, this instruction can be coalesced |
| 402 | /// if its hoisted to predecessor block. So, this returns true. |
| 403 | bool StructurizeCFG::isHoistableInstruction(Instruction *I, BasicBlock *BB, |
| 404 | BasicBlock *HoistTo) { |
| 405 | if (I->getParent() != BB || isa<PHINode>(Val: I)) |
| 406 | return false; |
| 407 | |
| 408 | // If the instruction is not a zero cost instruction, return false. |
| 409 | auto Cost = TTI->getInstructionCost(U: I, CostKind: TargetTransformInfo::TCK_Latency); |
| 410 | InstructionCost::CostType CostVal = |
| 411 | Cost.isValid() |
| 412 | ? Cost.getValue() |
| 413 | : (InstructionCost::CostType)TargetTransformInfo::TCC_Expensive; |
| 414 | if (CostVal != 0) |
| 415 | return false; |
| 416 | |
| 417 | // Check if all operands are available at the hoisting destination. |
| 418 | for (auto &Op : I->operands()) { |
| 419 | if (auto *OpI = dyn_cast<Instruction>(Val&: Op)) { |
| 420 | // Operand must dominate the hoisting destination. |
| 421 | if (!DT->dominates(A: OpI->getParent(), B: HoistTo)) |
| 422 | return false; |
| 423 | } |
| 424 | } |
| 425 | |
| 426 | return true; |
| 427 | } |
| 428 | |
| 429 | /// Structurization can introduce unnecessary VGPR copies due to register |
| 430 | /// coalescing interference. For example, if the Else block has a zero-cost |
| 431 | /// instruction and the Then block modifies the VGPR value, only one value is |
| 432 | /// live at a time in merge block before structurization. After structurization, |
| 433 | /// the coalescer may incorrectly treat the Then value as live in the Else block |
| 434 | /// (via the path Then → Flow → Else), leading to unnecessary VGPR copies. |
| 435 | /// |
| 436 | /// This function examines phi nodes whose incoming values are zero-cost |
| 437 | /// instructions in the Else block. It identifies such values that can be safely |
| 438 | /// hoisted and moves them to the nearest common dominator of Then and Else |
| 439 | /// blocks. A follow-up function after setting PhiNodes assigns the hoisted |
| 440 | /// value to poison phi nodes along the if→flow edge, aiding register coalescing |
| 441 | /// and minimizing unnecessary live ranges. |
| 442 | void StructurizeCFG::hoistZeroCostElseBlockPhiValues(BasicBlock *ElseBB, |
| 443 | BasicBlock *ThenBB) { |
| 444 | |
| 445 | BasicBlock *ElseSucc = ElseBB->getSingleSuccessor(); |
| 446 | BasicBlock *CommonDominator = DT->findNearestCommonDominator(A: ElseBB, B: ThenBB); |
| 447 | |
| 448 | if (!ElseSucc || !CommonDominator) |
| 449 | return; |
| 450 | // Only hoist in a simple if-else: ThenBB must branch directly to ElseSucc |
| 451 | // and ElseSucc must have exactly 2 predecessors (ThenBB and ElseBB). |
| 452 | // simplifyHoistedPhis assumes this exact shape; with additional predecessors |
| 453 | // the hoisted value leaks into unrelated control-flow paths. |
| 454 | if (ThenBB->getSingleSuccessor() != ElseSucc || |
| 455 | !ElseSucc->hasNPredecessors(N: 2)) |
| 456 | return; |
| 457 | Instruction *Term = CommonDominator->getTerminator(); |
| 458 | for (PHINode &Phi : ElseSucc->phis()) { |
| 459 | Value *ElseVal = Phi.getIncomingValueForBlock(BB: ElseBB); |
| 460 | auto *Inst = dyn_cast<Instruction>(Val: ElseVal); |
| 461 | if (!Inst || !isHoistableInstruction(I: Inst, BB: ElseBB, HoistTo: CommonDominator)) |
| 462 | continue; |
| 463 | Inst->removeFromParent(); |
| 464 | Inst->insertInto(ParentBB: CommonDominator, It: Term->getIterator()); |
| 465 | HoistedValues[Inst] = CommonDominator; |
| 466 | } |
| 467 | } |
| 468 | |
| 469 | /// Build up the general order of nodes, by performing a topological sort of the |
| 470 | /// parent region's nodes, while ensuring that there is no outer cycle node |
| 471 | /// between any two inner cycle nodes. |
| 472 | void StructurizeCFG::orderNodes() { |
| 473 | Order.resize(N: std::distance(first: GraphTraits<Region *>::nodes_begin(R: ParentRegion), |
| 474 | last: GraphTraits<Region *>::nodes_end(R: ParentRegion))); |
| 475 | if (Order.empty()) |
| 476 | return; |
| 477 | |
| 478 | SmallDenseSet<RegionNode *> Nodes; |
| 479 | auto EntryNode = SubGraphTraits::getEntryNode(R: ParentRegion); |
| 480 | |
| 481 | // A list of range indices of SCCs in Order, to be processed. |
| 482 | SmallVector<std::pair<unsigned, unsigned>, 8> WorkList; |
| 483 | unsigned I = 0, E = Order.size(); |
| 484 | while (true) { |
| 485 | // Run through all the SCCs in the subgraph starting with Entry. |
| 486 | for (auto SCCI = |
| 487 | scc_iterator<SubGraphTraits::NodeRef, SubGraphTraits>::begin( |
| 488 | G: EntryNode); |
| 489 | !SCCI.isAtEnd(); ++SCCI) { |
| 490 | auto &SCC = *SCCI; |
| 491 | |
| 492 | // An SCC up to the size of 2, can be reduced to an entry (the last node), |
| 493 | // and a possible additional node. Therefore, it is already in order, and |
| 494 | // there is no need to add it to the work-list. |
| 495 | unsigned Size = SCC.size(); |
| 496 | if (Size > 2) |
| 497 | WorkList.emplace_back(Args&: I, Args: I + Size); |
| 498 | |
| 499 | // Add the SCC nodes to the Order array. |
| 500 | for (const auto &N : SCC) { |
| 501 | assert(I < E && "SCC size mismatch!" ); |
| 502 | Order[I++] = N.first; |
| 503 | } |
| 504 | } |
| 505 | assert(I == E && "SCC size mismatch!" ); |
| 506 | |
| 507 | // If there are no more SCCs to order, then we are done. |
| 508 | if (WorkList.empty()) |
| 509 | break; |
| 510 | |
| 511 | std::tie(args&: I, args&: E) = WorkList.pop_back_val(); |
| 512 | |
| 513 | // Collect the set of nodes in the SCC's subgraph. These are only the |
| 514 | // possible child nodes; we do not add the entry (last node) otherwise we |
| 515 | // will have the same exact SCC all over again. |
| 516 | Nodes.clear(); |
| 517 | Nodes.insert(I: Order.begin() + I, E: Order.begin() + E - 1); |
| 518 | |
| 519 | // Update the entry node. |
| 520 | EntryNode.first = Order[E - 1]; |
| 521 | EntryNode.second = &Nodes; |
| 522 | } |
| 523 | } |
| 524 | |
| 525 | /// Determine the end of the loops |
| 526 | void StructurizeCFG::analyzeLoops(RegionNode *N) { |
| 527 | if (N->isSubRegion()) { |
| 528 | // Test for exit as back edge |
| 529 | BasicBlock *Exit = N->getNodeAs<Region>()->getExit(); |
| 530 | if (Visited.count(Ptr: Exit)) |
| 531 | Loops[Exit] = N->getEntry(); |
| 532 | |
| 533 | } else { |
| 534 | // Test for successors as back edge |
| 535 | // TODO: support other terminators other than branches. |
| 536 | BasicBlock *BB = N->getNodeAs<BasicBlock>(); |
| 537 | if (isa<UncondBrInst, CondBrInst>(Val: BB->getTerminator())) |
| 538 | for (BasicBlock *Succ : successors(BB)) |
| 539 | if (Visited.count(Ptr: Succ)) |
| 540 | Loops[Succ] = BB; |
| 541 | } |
| 542 | } |
| 543 | |
| 544 | /// Build the condition for one edge |
| 545 | PredInfo StructurizeCFG::buildCondition(CondBrInst *Term, unsigned Idx, |
| 546 | bool Invert) { |
| 547 | Value *Cond = Term->getCondition(); |
| 548 | auto Weights = CondBranchWeights::tryParse(Br: *Term); |
| 549 | if (Idx != (unsigned)Invert) { |
| 550 | Cond = invertCondition(Condition: Cond); |
| 551 | if (Weights) |
| 552 | Weights = Weights->invert(); |
| 553 | } |
| 554 | return {.Pred: Cond, .Weights: Weights}; |
| 555 | } |
| 556 | |
| 557 | /// Analyze the predecessors of each block and build up predicates |
| 558 | void StructurizeCFG::gatherPredicates(RegionNode *N) { |
| 559 | RegionInfo *RI = ParentRegion->getRegionInfo(); |
| 560 | BasicBlock *BB = N->getEntry(); |
| 561 | BBPredicates &Pred = Predicates[BB]; |
| 562 | BBPredicates &LPred = LoopPreds[BB]; |
| 563 | |
| 564 | for (BasicBlock *P : predecessors(BB)) { |
| 565 | // Ignore it if it's a branch from outside into our region entry |
| 566 | if (!ParentRegion->contains(BB: P)) |
| 567 | continue; |
| 568 | |
| 569 | Region *R = RI->getRegionFor(BB: P); |
| 570 | if (R == ParentRegion) { |
| 571 | if (isa<UncondBrInst>(Val: P->getTerminator())) { |
| 572 | if (Visited.count(Ptr: P)) |
| 573 | Pred[P] = {.Pred: BoolTrue, .Weights: std::nullopt}; |
| 574 | else |
| 575 | LPred[P] = {.Pred: BoolFalse, .Weights: std::nullopt}; |
| 576 | } else if (auto *CondBr = dyn_cast<CondBrInst>(Val: P->getTerminator())) { |
| 577 | bool Idx = CondBr->getSuccessor(i: 0) == BB ? 0 : 1; |
| 578 | if (Visited.count(Ptr: P)) { |
| 579 | // Normal forward edge |
| 580 | // Try to treat Other like an ELSE block |
| 581 | BasicBlock *Other = CondBr->getSuccessor(i: !Idx); |
| 582 | if (Visited.count(Ptr: Other) && !Loops.count(Val: Other) && |
| 583 | !Pred.count(Val: Other) && !Pred.count(Val: P)) { |
| 584 | hoistZeroCostElseBlockPhiValues(ElseBB: BB, ThenBB: Other); |
| 585 | Pred[Other] = {.Pred: BoolFalse, .Weights: std::nullopt}; |
| 586 | Pred[P] = {.Pred: BoolTrue, .Weights: std::nullopt}; |
| 587 | } else |
| 588 | Pred[P] = buildCondition(Term: CondBr, Idx, Invert: false); |
| 589 | } else { |
| 590 | // Back edge |
| 591 | LPred[P] = buildCondition(Term: CondBr, Idx, Invert: true); |
| 592 | } |
| 593 | } |
| 594 | } else { |
| 595 | // It's an exit from a sub region |
| 596 | while (R->getParent() != ParentRegion) |
| 597 | R = R->getParent(); |
| 598 | |
| 599 | // Edge from inside a subregion to its entry, ignore it |
| 600 | if (*R == *N) |
| 601 | continue; |
| 602 | |
| 603 | BasicBlock *Entry = R->getEntry(); |
| 604 | if (Visited.count(Ptr: Entry)) |
| 605 | Pred[Entry] = {.Pred: BoolTrue, .Weights: std::nullopt}; |
| 606 | else |
| 607 | LPred[Entry] = {.Pred: BoolFalse, .Weights: std::nullopt}; |
| 608 | } |
| 609 | } |
| 610 | } |
| 611 | |
| 612 | /// Collect various loop and predicate infos |
| 613 | void StructurizeCFG::collectInfos() { |
| 614 | // Reset predicate |
| 615 | Predicates.clear(); |
| 616 | |
| 617 | // and loop infos |
| 618 | Loops.clear(); |
| 619 | LoopPreds.clear(); |
| 620 | |
| 621 | // Reset the visited nodes |
| 622 | Visited.clear(); |
| 623 | |
| 624 | for (RegionNode *RN : reverse(C&: Order)) { |
| 625 | LLVM_DEBUG(dbgs() << "Visiting: " |
| 626 | << (RN->isSubRegion() ? "SubRegion with entry: " : "" ) |
| 627 | << RN->getEntry()->getName() << "\n" ); |
| 628 | |
| 629 | // Analyze all the conditions leading to a node |
| 630 | gatherPredicates(N: RN); |
| 631 | |
| 632 | // Remember that we've seen this node |
| 633 | Visited.insert(Ptr: RN->getEntry()); |
| 634 | |
| 635 | // Find the last back edges |
| 636 | analyzeLoops(N: RN); |
| 637 | } |
| 638 | } |
| 639 | |
| 640 | /// Insert the missing branch conditions |
| 641 | void StructurizeCFG::insertConditions(bool Loops, SSAUpdaterBulk &PhiInserter) { |
| 642 | BranchVector &Conds = Loops ? LoopConds : Conditions; |
| 643 | Value *Default = Loops ? BoolTrue : BoolFalse; |
| 644 | |
| 645 | for (auto [Term, Target] : Conds) { |
| 646 | BasicBlock *Parent = Term->getParent(); |
| 647 | BasicBlock *SuccFalse = Term->getSuccessor(i: 1); |
| 648 | |
| 649 | unsigned Variable = PhiInserter.AddVariable(Name: "" , Ty: Boolean); |
| 650 | PhiInserter.AddAvailableValue(Var: Variable, BB: Loops ? SuccFalse : Parent, |
| 651 | V: Default); |
| 652 | |
| 653 | BBPredicates &Preds = Loops ? LoopPreds[Target] : Predicates[Target]; |
| 654 | |
| 655 | NearestCommonDominator Dominator(DT); |
| 656 | Dominator.addBlock(BB: Parent); |
| 657 | |
| 658 | PredInfo ParentInfo{.Pred: nullptr, .Weights: std::nullopt}; |
| 659 | for (auto [BB, PI] : Preds) { |
| 660 | if (BB == Parent) { |
| 661 | ParentInfo = PI; |
| 662 | break; |
| 663 | } |
| 664 | PhiInserter.AddAvailableValue(Var: Variable, BB, V: PI.Pred); |
| 665 | Dominator.addAndRememberBlock(BB); |
| 666 | } |
| 667 | |
| 668 | if (ParentInfo.Pred) { |
| 669 | Term->setCondition(ParentInfo.Pred); |
| 670 | CondBranchWeights::setMetadata(Br&: *Term, Weights: ParentInfo.Weights); |
| 671 | } else { |
| 672 | if (!Dominator.resultIsRememberedBlock()) |
| 673 | PhiInserter.AddAvailableValue(Var: Variable, BB: Dominator.result(), V: Default); |
| 674 | |
| 675 | PhiInserter.AddUse(Var: Variable, U: &Term->getOperandUse(i: 0)); |
| 676 | } |
| 677 | } |
| 678 | } |
| 679 | |
| 680 | /// Simplify any inverted conditions that were built by buildConditions. |
| 681 | void StructurizeCFG::simplifyConditions() { |
| 682 | SmallVector<Instruction *> InstToErase; |
| 683 | for (auto &I : concat<PredMap::value_type>(Ranges&: Predicates, Ranges&: LoopPreds)) { |
| 684 | auto &Preds = I.second; |
| 685 | for (auto [BB, PI] : Preds) { |
| 686 | Instruction *Inverted; |
| 687 | if (match(V: PI.Pred, P: m_Not(V: m_OneUse(SubPattern: m_Instruction(I&: Inverted)))) && |
| 688 | !PI.Pred->use_empty()) { |
| 689 | if (auto *InvertedCmp = dyn_cast<CmpInst>(Val: Inverted)) { |
| 690 | InvertedCmp->setPredicate(InvertedCmp->getInversePredicate()); |
| 691 | PI.Pred->replaceAllUsesWith(V: InvertedCmp); |
| 692 | InstToErase.push_back(Elt: cast<Instruction>(Val: PI.Pred)); |
| 693 | } |
| 694 | } |
| 695 | } |
| 696 | } |
| 697 | for (auto *I : InstToErase) |
| 698 | I->eraseFromParent(); |
| 699 | } |
| 700 | |
| 701 | /// Remove all PHI values coming from "From" into "To" and remember |
| 702 | /// them in DeletedPhis |
| 703 | void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) { |
| 704 | PhiMap &Map = DeletedPhis[To]; |
| 705 | for (PHINode &Phi : To->phis()) { |
| 706 | bool Recorded = false; |
| 707 | while (Phi.getBasicBlockIndex(BB: From) != -1) { |
| 708 | Value *Deleted = Phi.removeIncomingValue(BB: From, DeletePHIIfEmpty: false); |
| 709 | Map[&Phi].push_back(Elt: std::make_pair(x&: From, y&: Deleted)); |
| 710 | if (!Recorded) { |
| 711 | AffectedPhis.push_back(Elt: &Phi); |
| 712 | Recorded = true; |
| 713 | } |
| 714 | } |
| 715 | } |
| 716 | } |
| 717 | |
| 718 | /// Add a dummy PHI value as soon as we knew the new predecessor |
| 719 | void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) { |
| 720 | for (PHINode &Phi : To->phis()) { |
| 721 | Value *Poison = PoisonValue::get(T: Phi.getType()); |
| 722 | Phi.addIncoming(V: Poison, BB: From); |
| 723 | } |
| 724 | AddedPhis[To].push_back(Elt: From); |
| 725 | } |
| 726 | |
| 727 | /// When we are reconstructing a PHI inside \p PHIBlock with incoming values |
| 728 | /// from predecessors \p Incomings, we have a chance to mark the available value |
| 729 | /// from some blocks as undefined. The function will find out all such blocks |
| 730 | /// and return in \p UndefBlks. |
| 731 | void StructurizeCFG::findUndefBlocks( |
| 732 | BasicBlock *PHIBlock, const SmallPtrSet<BasicBlock *, 8> &Incomings, |
| 733 | SmallVector<BasicBlock *> &UndefBlks) const { |
| 734 | // We may get a post-structured CFG like below: |
| 735 | // |
| 736 | // | P1 |
| 737 | // |/ |
| 738 | // F1 |
| 739 | // |\ |
| 740 | // | N |
| 741 | // |/ |
| 742 | // F2 |
| 743 | // |\ |
| 744 | // | P2 |
| 745 | // |/ |
| 746 | // F3 |
| 747 | // |\ |
| 748 | // B |
| 749 | // |
| 750 | // B is the block that has a PHI being reconstructed. P1/P2 are predecessors |
| 751 | // of B before structurization. F1/F2/F3 are flow blocks inserted during |
| 752 | // structurization process. Block N is not a predecessor of B before |
| 753 | // structurization, but are placed between the predecessors(P1/P2) of B after |
| 754 | // structurization. This usually means that threads went to N never take the |
| 755 | // path N->F2->F3->B. For example, the threads take the branch F1->N may |
| 756 | // always take the branch F2->P2. So, when we are reconstructing a PHI |
| 757 | // originally in B, we can safely say the incoming value from N is undefined. |
| 758 | SmallPtrSet<BasicBlock *, 8> VisitedBlock; |
| 759 | SmallVector<BasicBlock *, 8> Stack; |
| 760 | if (PHIBlock == ParentRegion->getExit()) { |
| 761 | for (auto P : predecessors(BB: PHIBlock)) { |
| 762 | if (ParentRegion->contains(BB: P)) |
| 763 | Stack.push_back(Elt: P); |
| 764 | } |
| 765 | } else { |
| 766 | append_range(C&: Stack, R: predecessors(BB: PHIBlock)); |
| 767 | } |
| 768 | |
| 769 | // Do a backward traversal over the CFG, and stop further searching if |
| 770 | // the block is not a Flow. If a block is neither flow block nor the |
| 771 | // incoming predecessor, then the incoming value from the block is |
| 772 | // undefined value for the PHI being reconstructed. |
| 773 | while (!Stack.empty()) { |
| 774 | BasicBlock *Current = Stack.pop_back_val(); |
| 775 | if (!VisitedBlock.insert(Ptr: Current).second) |
| 776 | continue; |
| 777 | |
| 778 | if (FlowSet.contains(Ptr: Current)) |
| 779 | llvm::append_range(C&: Stack, R: predecessors(BB: Current)); |
| 780 | else if (!Incomings.contains(Ptr: Current)) |
| 781 | UndefBlks.push_back(Elt: Current); |
| 782 | } |
| 783 | } |
| 784 | |
| 785 | // If two phi nodes have compatible incoming values (for each |
| 786 | // incoming block, either they have the same incoming value or only one phi |
| 787 | // node has an incoming value), let them share the merged incoming values. The |
| 788 | // merge process is guided by the equivalence information from \p PhiClasses. |
| 789 | // The function will possibly update the incoming values of leader phi in |
| 790 | // DeletedPhis. |
| 791 | void StructurizeCFG::mergeIfCompatible( |
| 792 | EquivalenceClasses<PHINode *> &PhiClasses, PHINode *A, PHINode *B) { |
| 793 | auto ItA = PhiClasses.findLeader(ECV: PhiClasses.insert(Data: A)); |
| 794 | auto ItB = PhiClasses.findLeader(ECV: PhiClasses.insert(Data: B)); |
| 795 | // They are already in the same class, no work needed. |
| 796 | if (ItA == ItB) |
| 797 | return; |
| 798 | |
| 799 | PHINode *LeaderA = *ItA; |
| 800 | PHINode *LeaderB = *ItB; |
| 801 | BBValueVector &IncomingA = DeletedPhis[LeaderA->getParent()][LeaderA]; |
| 802 | BBValueVector &IncomingB = DeletedPhis[LeaderB->getParent()][LeaderB]; |
| 803 | |
| 804 | DenseMap<BasicBlock *, Value *> Mergeable(IncomingA.begin(), IncomingA.end()); |
| 805 | for (auto [BB, V] : IncomingB) { |
| 806 | auto BBIt = Mergeable.find(Val: BB); |
| 807 | if (BBIt != Mergeable.end() && BBIt->second != V) |
| 808 | return; |
| 809 | // Either IncomingA does not have this value or IncomingA has the same |
| 810 | // value. |
| 811 | Mergeable.insert(KV: {BB, V}); |
| 812 | } |
| 813 | |
| 814 | // Update the incoming value of leaderA. |
| 815 | IncomingA.assign(in_start: Mergeable.begin(), in_end: Mergeable.end()); |
| 816 | PhiClasses.unionSets(L1: ItA, L2: ItB); |
| 817 | } |
| 818 | |
| 819 | /// Add the real PHI value as soon as everything is set up |
| 820 | void StructurizeCFG::setPhiValues() { |
| 821 | SmallVector<PHINode *, 8> InsertedPhis; |
| 822 | SSAUpdater Updater(&InsertedPhis); |
| 823 | DenseMap<BasicBlock *, SmallVector<BasicBlock *>> UndefBlksMap; |
| 824 | |
| 825 | // Find phi nodes that have compatible incoming values (either they have |
| 826 | // the same value for the same block or only one phi node has an incoming |
| 827 | // value, see example below). We only search again the phi's that are |
| 828 | // referenced by another phi, which is the case we care about. |
| 829 | // |
| 830 | // For example (-- means no incoming value): |
| 831 | // phi1 : BB1:phi2 BB2:v BB3:-- |
| 832 | // phi2: BB1:-- BB2:v BB3:w |
| 833 | // |
| 834 | // Then we can merge these incoming values and let phi1, phi2 use the |
| 835 | // same set of incoming values: |
| 836 | // |
| 837 | // phi1&phi2: BB1:phi2 BB2:v BB3:w |
| 838 | // |
| 839 | // By doing this, phi1 and phi2 would share more intermediate phi nodes. |
| 840 | // This would help reduce the number of phi nodes during SSA reconstruction |
| 841 | // and ultimately result in fewer COPY instructions. |
| 842 | // |
| 843 | // This should be correct, because if a phi node does not have incoming |
| 844 | // value from certain block, this means the block is not the predecessor |
| 845 | // of the parent block, so we actually don't care about its incoming value. |
| 846 | EquivalenceClasses<PHINode *> PhiClasses; |
| 847 | for (const auto &[To, From] : AddedPhis) { |
| 848 | auto OldPhiIt = DeletedPhis.find(Val: To); |
| 849 | if (OldPhiIt == DeletedPhis.end()) |
| 850 | continue; |
| 851 | |
| 852 | PhiMap &BlkPhis = OldPhiIt->second; |
| 853 | SmallVector<BasicBlock *> &UndefBlks = UndefBlksMap[To]; |
| 854 | SmallPtrSet<BasicBlock *, 8> Incomings; |
| 855 | |
| 856 | // Get the undefined blocks shared by all the phi nodes. |
| 857 | if (!BlkPhis.empty()) { |
| 858 | Incomings.insert_range(R: llvm::make_first_range(c&: BlkPhis.front().second)); |
| 859 | findUndefBlocks(PHIBlock: To, Incomings, UndefBlks); |
| 860 | } |
| 861 | |
| 862 | for (const auto &[Phi, Incomings] : OldPhiIt->second) { |
| 863 | SmallVector<PHINode *> IncomingPHIs; |
| 864 | for (const auto &[BB, V] : Incomings) { |
| 865 | // First, for each phi, check whether it has incoming value which is |
| 866 | // another phi. |
| 867 | if (PHINode *P = dyn_cast<PHINode>(Val: V)) |
| 868 | IncomingPHIs.push_back(Elt: P); |
| 869 | } |
| 870 | |
| 871 | for (auto *OtherPhi : IncomingPHIs) { |
| 872 | // Skip phis that are unrelated to the phi reconstruction for now. |
| 873 | if (!DeletedPhis.contains(Val: OtherPhi->getParent())) |
| 874 | continue; |
| 875 | mergeIfCompatible(PhiClasses, A: Phi, B: OtherPhi); |
| 876 | } |
| 877 | } |
| 878 | } |
| 879 | |
| 880 | for (const auto &AddedPhi : AddedPhis) { |
| 881 | BasicBlock *To = AddedPhi.first; |
| 882 | const BBVector &From = AddedPhi.second; |
| 883 | |
| 884 | auto It = DeletedPhis.find(Val: To); |
| 885 | if (It == DeletedPhis.end()) |
| 886 | continue; |
| 887 | |
| 888 | PhiMap &Map = It->second; |
| 889 | SmallVector<BasicBlock *> &UndefBlks = UndefBlksMap[To]; |
| 890 | for (const auto &[Phi, Incoming] : Map) { |
| 891 | Value *Poison = PoisonValue::get(T: Phi->getType()); |
| 892 | Updater.Initialize(Ty: Phi->getType(), Name: "" ); |
| 893 | Updater.AddAvailableValue(BB: &Func->getEntryBlock(), V: Poison); |
| 894 | Updater.AddAvailableValue(BB: To, V: Poison); |
| 895 | |
| 896 | // Use leader phi's incoming if there is. |
| 897 | auto LeaderIt = PhiClasses.findLeader(V: Phi); |
| 898 | bool UseIncomingOfLeader = |
| 899 | LeaderIt != PhiClasses.member_end() && *LeaderIt != Phi; |
| 900 | const auto &IncomingMap = |
| 901 | UseIncomingOfLeader ? DeletedPhis[(*LeaderIt)->getParent()][*LeaderIt] |
| 902 | : Incoming; |
| 903 | |
| 904 | SmallVector<BasicBlock *> ConstantPreds; |
| 905 | for (const auto &[BB, V] : IncomingMap) { |
| 906 | Updater.AddAvailableValue(BB, V); |
| 907 | if (isa<Constant>(Val: V)) |
| 908 | ConstantPreds.push_back(Elt: BB); |
| 909 | } |
| 910 | |
| 911 | for (auto UB : UndefBlks) { |
| 912 | // If this undef block is dominated by any predecessor(before |
| 913 | // structurization) of reconstructed PHI with constant incoming value, |
| 914 | // don't mark the available value as undefined. Setting undef to such |
| 915 | // block will stop us from getting optimal phi insertion. |
| 916 | if (any_of(Range&: ConstantPreds, |
| 917 | P: [&](BasicBlock *CP) { return DT->dominates(A: CP, B: UB); })) |
| 918 | continue; |
| 919 | // Maybe already get a value through sharing with other phi nodes. |
| 920 | if (Updater.HasValueForBlock(BB: UB)) |
| 921 | continue; |
| 922 | |
| 923 | Updater.AddAvailableValue(BB: UB, V: Poison); |
| 924 | } |
| 925 | |
| 926 | for (BasicBlock *FI : From) |
| 927 | Phi->setIncomingValueForBlock(BB: FI, V: Updater.GetValueAtEndOfBlock(BB: FI)); |
| 928 | AffectedPhis.push_back(Elt: Phi); |
| 929 | } |
| 930 | } |
| 931 | |
| 932 | AffectedPhis.append(in_start: InsertedPhis.begin(), in_end: InsertedPhis.end()); |
| 933 | } |
| 934 | |
| 935 | /// Updates PHI nodes after hoisted zero cost instructions by replacing poison |
| 936 | /// entries on Flow nodes with the appropriate hoisted values |
| 937 | void StructurizeCFG::simplifyHoistedPhis() { |
| 938 | for (WeakVH VH : AffectedPhis) { |
| 939 | PHINode *Phi = dyn_cast_or_null<PHINode>(Val&: VH); |
| 940 | if (!Phi || Phi->getNumIncomingValues() != 2) |
| 941 | continue; |
| 942 | |
| 943 | for (int i = 0; i < 2; i++) { |
| 944 | Value *V = Phi->getIncomingValue(i); |
| 945 | auto BBIt = HoistedValues.find(Val: V); |
| 946 | |
| 947 | if (BBIt == HoistedValues.end()) |
| 948 | continue; |
| 949 | |
| 950 | Value *OtherV = Phi->getIncomingValue(i: !i); |
| 951 | PHINode *OtherPhi = dyn_cast<PHINode>(Val: OtherV); |
| 952 | if (!OtherPhi) |
| 953 | continue; |
| 954 | |
| 955 | int PoisonValBBIdx = -1; |
| 956 | for (size_t i = 0; i < OtherPhi->getNumIncomingValues(); i++) { |
| 957 | if (!isa<PoisonValue>(Val: OtherPhi->getIncomingValue(i))) |
| 958 | continue; |
| 959 | PoisonValBBIdx = i; |
| 960 | break; |
| 961 | } |
| 962 | if (PoisonValBBIdx == -1 || |
| 963 | !DT->dominates(A: BBIt->second, |
| 964 | B: OtherPhi->getIncomingBlock(i: PoisonValBBIdx))) |
| 965 | continue; |
| 966 | |
| 967 | OtherPhi->setIncomingValue(i: PoisonValBBIdx, V); |
| 968 | if (DT->dominates(Def: OtherV, User: Phi)) |
| 969 | Phi->setIncomingValue(i, V: OtherV); |
| 970 | } |
| 971 | } |
| 972 | } |
| 973 | |
| 974 | void StructurizeCFG::simplifyAffectedPhis() { |
| 975 | bool Changed; |
| 976 | do { |
| 977 | Changed = false; |
| 978 | SimplifyQuery Q(Func->getDataLayout()); |
| 979 | Q.DT = DT; |
| 980 | // Setting CanUseUndef to true might extend value liveness, set it to false |
| 981 | // to achieve better register pressure. |
| 982 | Q.CanUseUndef = false; |
| 983 | for (WeakVH VH : AffectedPhis) { |
| 984 | if (auto Phi = dyn_cast_or_null<PHINode>(Val&: VH)) { |
| 985 | if (auto NewValue = simplifyInstruction(I: Phi, Q)) { |
| 986 | Phi->replaceAllUsesWith(V: NewValue); |
| 987 | Phi->eraseFromParent(); |
| 988 | Changed = true; |
| 989 | } |
| 990 | } |
| 991 | } |
| 992 | } while (Changed); |
| 993 | } |
| 994 | |
| 995 | /// Remove phi values from all successors and then remove the terminator. |
| 996 | DebugLoc StructurizeCFG::killTerminator(BasicBlock *BB) { |
| 997 | Instruction *Term = BB->getTerminatorOrNull(); |
| 998 | if (!Term) |
| 999 | return DebugLoc(); |
| 1000 | |
| 1001 | for (BasicBlock *Succ : successors(BB)) |
| 1002 | delPhiValues(From: BB, To: Succ); |
| 1003 | |
| 1004 | DebugLoc DL = Term->getDebugLoc(); |
| 1005 | Term->eraseFromParent(); |
| 1006 | return DL; |
| 1007 | } |
| 1008 | |
| 1009 | /// Let node exit(s) point to NewExit |
| 1010 | void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit, |
| 1011 | bool IncludeDominator) { |
| 1012 | if (Node->isSubRegion()) { |
| 1013 | Region *SubRegion = Node->getNodeAs<Region>(); |
| 1014 | BasicBlock *OldExit = SubRegion->getExit(); |
| 1015 | BasicBlock *Dominator = nullptr; |
| 1016 | |
| 1017 | // Find all the edges from the sub region to the exit. |
| 1018 | // We use make_early_inc_range here because we modify BB's terminator. |
| 1019 | for (BasicBlock *BB : llvm::make_early_inc_range(Range: predecessors(BB: OldExit))) { |
| 1020 | if (!SubRegion->contains(BB)) |
| 1021 | continue; |
| 1022 | |
| 1023 | // Modify the edges to point to the new exit |
| 1024 | delPhiValues(From: BB, To: OldExit); |
| 1025 | BB->getTerminator()->replaceUsesOfWith(From: OldExit, To: NewExit); |
| 1026 | addPhiValues(From: BB, To: NewExit); |
| 1027 | |
| 1028 | // Find the new dominator (if requested) |
| 1029 | if (IncludeDominator) { |
| 1030 | if (!Dominator) |
| 1031 | Dominator = BB; |
| 1032 | else |
| 1033 | Dominator = DT->findNearestCommonDominator(A: Dominator, B: BB); |
| 1034 | } |
| 1035 | } |
| 1036 | |
| 1037 | // Change the dominator (if requested) |
| 1038 | if (Dominator) |
| 1039 | DT->changeImmediateDominator(BB: NewExit, NewBB: Dominator); |
| 1040 | |
| 1041 | // Update the region info |
| 1042 | SubRegion->replaceExit(BB: NewExit); |
| 1043 | } else { |
| 1044 | BasicBlock *BB = Node->getNodeAs<BasicBlock>(); |
| 1045 | DebugLoc DL = killTerminator(BB); |
| 1046 | UncondBrInst *Br = UncondBrInst::Create(Target: NewExit, InsertBefore: BB); |
| 1047 | Br->setDebugLoc(DL); |
| 1048 | addPhiValues(From: BB, To: NewExit); |
| 1049 | if (IncludeDominator) |
| 1050 | DT->changeImmediateDominator(BB: NewExit, NewBB: BB); |
| 1051 | } |
| 1052 | } |
| 1053 | |
| 1054 | /// Create a new flow node and update dominator tree and region info |
| 1055 | BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) { |
| 1056 | LLVMContext &Context = Func->getContext(); |
| 1057 | BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() : |
| 1058 | Order.back()->getEntry(); |
| 1059 | BasicBlock *Flow = BasicBlock::Create(Context, Name: FlowBlockName, |
| 1060 | Parent: Func, InsertBefore: Insert); |
| 1061 | FlowSet.insert(Ptr: Flow); |
| 1062 | DT->addNewBlock(BB: Flow, DomBB: Dominator); |
| 1063 | ParentRegion->getRegionInfo()->setRegionFor(BB: Flow, R: ParentRegion); |
| 1064 | return Flow; |
| 1065 | } |
| 1066 | |
| 1067 | /// Create a new or reuse the previous node as flow node. Returns a block and a |
| 1068 | /// debug location to be used for new instructions in that block. |
| 1069 | std::pair<BasicBlock *, DebugLoc> StructurizeCFG::needPrefix(bool NeedEmpty) { |
| 1070 | BasicBlock *Entry = PrevNode->getEntry(); |
| 1071 | |
| 1072 | if (!PrevNode->isSubRegion()) { |
| 1073 | DebugLoc DL = killTerminator(BB: Entry); |
| 1074 | if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end()) |
| 1075 | return {Entry, DL}; |
| 1076 | } |
| 1077 | |
| 1078 | // create a new flow node |
| 1079 | BasicBlock *Flow = getNextFlow(Dominator: Entry); |
| 1080 | |
| 1081 | // and wire it up |
| 1082 | changeExit(Node: PrevNode, NewExit: Flow, IncludeDominator: true); |
| 1083 | PrevNode = ParentRegion->getBBNode(BB: Flow); |
| 1084 | return {Flow, DebugLoc()}; |
| 1085 | } |
| 1086 | |
| 1087 | /// Returns the region exit if possible, otherwise just a new flow node |
| 1088 | BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow, |
| 1089 | bool ExitUseAllowed) { |
| 1090 | if (!Order.empty() || !ExitUseAllowed) |
| 1091 | return getNextFlow(Dominator: Flow); |
| 1092 | |
| 1093 | BasicBlock *Exit = ParentRegion->getExit(); |
| 1094 | DT->changeImmediateDominator(BB: Exit, NewBB: Flow); |
| 1095 | addPhiValues(From: Flow, To: Exit); |
| 1096 | return Exit; |
| 1097 | } |
| 1098 | |
| 1099 | /// Set the previous node |
| 1100 | void StructurizeCFG::setPrevNode(BasicBlock *BB) { |
| 1101 | PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB) |
| 1102 | : nullptr; |
| 1103 | } |
| 1104 | |
| 1105 | /// Does BB dominate all the predicates of Node? |
| 1106 | bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) { |
| 1107 | BBPredicates &Preds = Predicates[Node->getEntry()]; |
| 1108 | return llvm::all_of( |
| 1109 | Range&: Preds, P: [&](const auto &Pred) { return DT->dominates(BB, Pred.first); }); |
| 1110 | } |
| 1111 | |
| 1112 | /// Can we predict that this node will always be called? |
| 1113 | bool StructurizeCFG::isPredictableTrue(RegionNode *Node) { |
| 1114 | BBPredicates &Preds = Predicates[Node->getEntry()]; |
| 1115 | bool Dominated = false; |
| 1116 | |
| 1117 | // Regionentry is always true |
| 1118 | if (!PrevNode) |
| 1119 | return true; |
| 1120 | |
| 1121 | for (auto [BB, PI] : Preds) { |
| 1122 | if (PI.Pred != BoolTrue) |
| 1123 | return false; |
| 1124 | |
| 1125 | if (!Dominated && DT->dominates(A: BB, B: PrevNode->getEntry())) |
| 1126 | Dominated = true; |
| 1127 | } |
| 1128 | |
| 1129 | // TODO: The dominator check is too strict |
| 1130 | return Dominated; |
| 1131 | } |
| 1132 | |
| 1133 | /// Take one node from the order vector and wire it up |
| 1134 | void StructurizeCFG::wireFlow(bool ExitUseAllowed, |
| 1135 | BasicBlock *LoopEnd) { |
| 1136 | RegionNode *Node = Order.pop_back_val(); |
| 1137 | Visited.insert(Ptr: Node->getEntry()); |
| 1138 | |
| 1139 | if (isPredictableTrue(Node)) { |
| 1140 | // Just a linear flow |
| 1141 | if (PrevNode) { |
| 1142 | changeExit(Node: PrevNode, NewExit: Node->getEntry(), IncludeDominator: true); |
| 1143 | } |
| 1144 | PrevNode = Node; |
| 1145 | } else { |
| 1146 | // Insert extra prefix node (or reuse last one) |
| 1147 | auto [Flow, DL] = needPrefix(NeedEmpty: false); |
| 1148 | |
| 1149 | // Insert extra postfix node (or use exit instead) |
| 1150 | BasicBlock *Entry = Node->getEntry(); |
| 1151 | BasicBlock *Next = needPostfix(Flow, ExitUseAllowed); |
| 1152 | |
| 1153 | // let it point to entry and next block |
| 1154 | CondBrInst *Br = CondBrInst::Create(Cond: BoolPoison, IfTrue: Entry, IfFalse: Next, InsertBefore: Flow); |
| 1155 | Br->setDebugLoc(DL); |
| 1156 | Conditions.push_back(Elt: {Br, Entry}); |
| 1157 | addPhiValues(From: Flow, To: Entry); |
| 1158 | DT->changeImmediateDominator(BB: Entry, NewBB: Flow); |
| 1159 | |
| 1160 | PrevNode = Node; |
| 1161 | while (!Order.empty() && !Visited.count(Ptr: LoopEnd) && |
| 1162 | dominatesPredicates(BB: Entry, Node: Order.back())) { |
| 1163 | handleLoops(ExitUseAllowed: false, LoopEnd); |
| 1164 | } |
| 1165 | |
| 1166 | changeExit(Node: PrevNode, NewExit: Next, IncludeDominator: false); |
| 1167 | setPrevNode(Next); |
| 1168 | } |
| 1169 | } |
| 1170 | |
| 1171 | void StructurizeCFG::handleLoops(bool ExitUseAllowed, |
| 1172 | BasicBlock *LoopEnd) { |
| 1173 | RegionNode *Node = Order.back(); |
| 1174 | BasicBlock *LoopStart = Node->getEntry(); |
| 1175 | |
| 1176 | if (!Loops.count(Val: LoopStart)) { |
| 1177 | wireFlow(ExitUseAllowed, LoopEnd); |
| 1178 | return; |
| 1179 | } |
| 1180 | |
| 1181 | if (!isPredictableTrue(Node)) |
| 1182 | LoopStart = needPrefix(NeedEmpty: true).first; |
| 1183 | |
| 1184 | LoopEnd = Loops[Node->getEntry()]; |
| 1185 | wireFlow(ExitUseAllowed: false, LoopEnd); |
| 1186 | while (!Visited.count(Ptr: LoopEnd)) { |
| 1187 | handleLoops(ExitUseAllowed: false, LoopEnd); |
| 1188 | } |
| 1189 | |
| 1190 | assert(LoopStart != &LoopStart->getParent()->getEntryBlock()); |
| 1191 | |
| 1192 | // Create an extra loop end node |
| 1193 | DebugLoc DL; |
| 1194 | std::tie(args&: LoopEnd, args&: DL) = needPrefix(NeedEmpty: false); |
| 1195 | BasicBlock *Next = needPostfix(Flow: LoopEnd, ExitUseAllowed); |
| 1196 | CondBrInst *Br = CondBrInst::Create(Cond: BoolPoison, IfTrue: Next, IfFalse: LoopStart, InsertBefore: LoopEnd); |
| 1197 | Br->setDebugLoc(DL); |
| 1198 | BasicBlock * = Node->getEntry(); |
| 1199 | LoopConds.push_back(Elt: {Br, Header}); |
| 1200 | |
| 1201 | // The backedge targets the prefix block, so it must always enter the header. |
| 1202 | if (LoopStart != Header) |
| 1203 | Predicates[Header][LoopEnd] = {.Pred: BoolTrue, .Weights: std::nullopt}; |
| 1204 | |
| 1205 | addPhiValues(From: LoopEnd, To: LoopStart); |
| 1206 | setPrevNode(Next); |
| 1207 | } |
| 1208 | |
| 1209 | /// After this function control flow looks like it should be, but |
| 1210 | /// branches and PHI nodes only have undefined conditions. |
| 1211 | void StructurizeCFG::createFlow() { |
| 1212 | BasicBlock *Exit = ParentRegion->getExit(); |
| 1213 | bool EntryDominatesExit = DT->dominates(A: ParentRegion->getEntry(), B: Exit); |
| 1214 | |
| 1215 | AffectedPhis.clear(); |
| 1216 | DeletedPhis.clear(); |
| 1217 | AddedPhis.clear(); |
| 1218 | Conditions.clear(); |
| 1219 | LoopConds.clear(); |
| 1220 | |
| 1221 | PrevNode = nullptr; |
| 1222 | Visited.clear(); |
| 1223 | |
| 1224 | while (!Order.empty()) { |
| 1225 | handleLoops(ExitUseAllowed: EntryDominatesExit, LoopEnd: nullptr); |
| 1226 | } |
| 1227 | |
| 1228 | if (PrevNode) |
| 1229 | changeExit(Node: PrevNode, NewExit: Exit, IncludeDominator: EntryDominatesExit); |
| 1230 | else |
| 1231 | assert(EntryDominatesExit); |
| 1232 | } |
| 1233 | |
| 1234 | /// Handle a rare case where the disintegrated nodes instructions |
| 1235 | /// no longer dominate all their uses. |
| 1236 | void StructurizeCFG::rebuildSSA() { |
| 1237 | SSAUpdater Updater; |
| 1238 | for (BasicBlock *BB : ParentRegion->blocks()) |
| 1239 | for (Instruction &I : *BB) { |
| 1240 | bool Initialized = false; |
| 1241 | // We may modify the use list as we iterate over it, so we use |
| 1242 | // make_early_inc_range. |
| 1243 | for (Use &U : llvm::make_early_inc_range(Range: I.uses())) { |
| 1244 | Instruction *User = cast<Instruction>(Val: U.getUser()); |
| 1245 | if (User->getParent() == BB) { |
| 1246 | continue; |
| 1247 | } else if (PHINode *UserPN = dyn_cast<PHINode>(Val: User)) { |
| 1248 | if (UserPN->getIncomingBlock(U) == BB) |
| 1249 | continue; |
| 1250 | } |
| 1251 | |
| 1252 | if (DT->dominates(Def: &I, User)) |
| 1253 | continue; |
| 1254 | |
| 1255 | if (!Initialized) { |
| 1256 | Value *Poison = PoisonValue::get(T: I.getType()); |
| 1257 | Updater.Initialize(Ty: I.getType(), Name: "" ); |
| 1258 | Updater.AddAvailableValue(BB: &Func->getEntryBlock(), V: Poison); |
| 1259 | Updater.AddAvailableValue(BB, V: &I); |
| 1260 | Initialized = true; |
| 1261 | } |
| 1262 | Updater.RewriteUseAfterInsertions(U); |
| 1263 | } |
| 1264 | } |
| 1265 | } |
| 1266 | |
| 1267 | /// Can region \p R be left unstructurized because all of its own control flow |
| 1268 | /// is uniform? |
| 1269 | /// |
| 1270 | /// Only the terminators of direct child blocks are checked. Sub-regions are |
| 1271 | /// processed before their parent, so any divergent control flow inside a |
| 1272 | /// sub-region has already been structurized and is self-contained: it is |
| 1273 | /// entered only through the sub-region's entry, and it rejoins either at Flow |
| 1274 | /// blocks inside the sub-region or, if the sub-region's entry dominates its |
| 1275 | /// exit, at the exit block itself. Uniform control flow around a sub-region |
| 1276 | /// therefore does not need structurizing, whatever the sub-region contains. |
| 1277 | /// (The branches inside sub-regions could not be checked anyway, because they |
| 1278 | /// may have been removed and re-created since UniformityAnalysis ran.) |
| 1279 | /// |
| 1280 | /// FIXME: This does not hold for a sub-region whose entry block ends in a |
| 1281 | /// callbr, because run() leaves such regions unstructurized. |
| 1282 | static bool hasOnlyUniformBranches(Region *R, const UniformityInfo &UA) { |
| 1283 | return none_of(Range: R->elements(), P: [&](RegionNode *E) { |
| 1284 | if (E->isSubRegion()) |
| 1285 | return false; |
| 1286 | auto *Br = dyn_cast<CondBrInst>(Val: E->getEntry()->getTerminator()); |
| 1287 | return Br && UA.isDivergentTerminator(I: Br); |
| 1288 | }); |
| 1289 | } |
| 1290 | |
| 1291 | void StructurizeCFG::init(Region *R) { |
| 1292 | LLVMContext &Context = R->getEntry()->getContext(); |
| 1293 | |
| 1294 | Boolean = Type::getInt1Ty(C&: Context); |
| 1295 | BoolTrue = ConstantInt::getTrue(Context); |
| 1296 | BoolFalse = ConstantInt::getFalse(Context); |
| 1297 | BoolPoison = PoisonValue::get(T: Boolean); |
| 1298 | } |
| 1299 | |
| 1300 | bool StructurizeCFG::makeUniformRegion(Region *R, const UniformityInfo &UA) { |
| 1301 | if (R->isTopLevelRegion()) |
| 1302 | return false; |
| 1303 | |
| 1304 | if (hasOnlyUniformBranches(R, UA)) { |
| 1305 | LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R |
| 1306 | << '\n'); |
| 1307 | |
| 1308 | // Mark all direct child block terminators as having been treated as |
| 1309 | // uniform. Indirect children must not be marked, because sub-regions may |
| 1310 | // contain divergent control flow. |
| 1311 | LLVMContext &Ctx = R->getEntry()->getContext(); |
| 1312 | unsigned UniformMDKindID = Ctx.getMDKindID(Name: "structurizecfg.uniform" ); |
| 1313 | MDNode *MD = MDNode::get(Context&: Ctx, MDs: {}); |
| 1314 | for (RegionNode *E : R->elements()) { |
| 1315 | if (E->isSubRegion()) |
| 1316 | continue; |
| 1317 | |
| 1318 | E->getEntry()->getTerminator()->setMetadata(KindID: UniformMDKindID, Node: MD); |
| 1319 | } |
| 1320 | |
| 1321 | return true; |
| 1322 | } |
| 1323 | return false; |
| 1324 | } |
| 1325 | |
| 1326 | /// Run the transformation for each region found |
| 1327 | bool StructurizeCFG::run(Region *R, DominatorTree *DT, |
| 1328 | const TargetTransformInfo *TTI) { |
| 1329 | // CallBr and its corresponding direct target blocks are for now ignored by |
| 1330 | // this pass. This is not a limitation for the currently intended uses cases |
| 1331 | // of callbr in the AMDGPU backend. |
| 1332 | // Parent and child regions are not affected by this (current) restriction. |
| 1333 | // See `llvm/test/Transforms/StructurizeCFG/callbr.ll` for details. |
| 1334 | if (R->isTopLevelRegion() || isa<CallBrInst>(Val: R->getEntry()->getTerminator())) |
| 1335 | return false; |
| 1336 | |
| 1337 | this->DT = DT; |
| 1338 | this->TTI = TTI; |
| 1339 | Func = R->getEntry()->getParent(); |
| 1340 | |
| 1341 | ParentRegion = R; |
| 1342 | |
| 1343 | orderNodes(); |
| 1344 | collectInfos(); |
| 1345 | createFlow(); |
| 1346 | |
| 1347 | SSAUpdaterBulk PhiInserter; |
| 1348 | insertConditions(Loops: false, PhiInserter); |
| 1349 | insertConditions(Loops: true, PhiInserter); |
| 1350 | PhiInserter.RewriteAndOptimizeAllUses(DT&: *DT); |
| 1351 | |
| 1352 | setPhiValues(); |
| 1353 | simplifyHoistedPhis(); |
| 1354 | simplifyConditions(); |
| 1355 | simplifyAffectedPhis(); |
| 1356 | rebuildSSA(); |
| 1357 | |
| 1358 | // Cleanup |
| 1359 | Order.clear(); |
| 1360 | Visited.clear(); |
| 1361 | DeletedPhis.clear(); |
| 1362 | AddedPhis.clear(); |
| 1363 | Predicates.clear(); |
| 1364 | Conditions.clear(); |
| 1365 | Loops.clear(); |
| 1366 | LoopPreds.clear(); |
| 1367 | LoopConds.clear(); |
| 1368 | FlowSet.clear(); |
| 1369 | |
| 1370 | return true; |
| 1371 | } |
| 1372 | |
| 1373 | Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) { |
| 1374 | return new StructurizeCFGLegacyPass(SkipUniformRegions); |
| 1375 | } |
| 1376 | |
| 1377 | static void addRegionIntoQueue(Region &R, std::vector<Region *> &Regions) { |
| 1378 | Regions.push_back(x: &R); |
| 1379 | for (const auto &E : R) |
| 1380 | addRegionIntoQueue(R&: *E, Regions); |
| 1381 | } |
| 1382 | |
| 1383 | StructurizeCFGPass::StructurizeCFGPass(bool SkipUniformRegions_) |
| 1384 | : SkipUniformRegions(SkipUniformRegions_) {} |
| 1385 | |
| 1386 | void StructurizeCFGPass::printPipeline( |
| 1387 | raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { |
| 1388 | static_cast<PassInfoMixin<StructurizeCFGPass> *>(this)->printPipeline( |
| 1389 | OS, MapClassName2PassName); |
| 1390 | if (SkipUniformRegions) |
| 1391 | OS << "<skip-uniform-regions>" ; |
| 1392 | } |
| 1393 | |
| 1394 | /// Structurize every region in \p RI, processing inner regions before the |
| 1395 | /// regions that contain them. If \p UI is non-null, skip uniform regions. |
| 1396 | static bool runImpl(DominatorTree &DT, RegionInfo &RI, |
| 1397 | const TargetTransformInfo &TTI, const UniformityInfo *UI) { |
| 1398 | bool Changed = false; |
| 1399 | std::vector<Region *> Regions; |
| 1400 | addRegionIntoQueue(R&: *RI.getTopLevelRegion(), Regions); |
| 1401 | while (!Regions.empty()) { |
| 1402 | Region *R = Regions.back(); |
| 1403 | Regions.pop_back(); |
| 1404 | |
| 1405 | StructurizeCFG SCFG; |
| 1406 | SCFG.init(R); |
| 1407 | |
| 1408 | if (UI && SCFG.makeUniformRegion(R, UA: *UI)) { |
| 1409 | Changed = true; // May have added metadata. |
| 1410 | continue; |
| 1411 | } |
| 1412 | |
| 1413 | Changed |= SCFG.run(R, DT: &DT, TTI: &TTI); |
| 1414 | } |
| 1415 | return Changed; |
| 1416 | } |
| 1417 | |
| 1418 | bool StructurizeCFGLegacyPass::runOnFunction(Function &F) { |
| 1419 | const ScalarOptions &Opts = getScalarOptions(F); |
| 1420 | const UniformityInfo *UI = nullptr; |
| 1421 | if (valueOr(X: Opts.structurizecfg_skip_uniform_regions, Default: SkipUniformRegions)) |
| 1422 | UI = &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo(); |
| 1423 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
| 1424 | RegionInfo &RI = getAnalysis<RegionInfoPass>().getRegionInfo(); |
| 1425 | const TargetTransformInfo &TTI = |
| 1426 | getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); |
| 1427 | return runImpl(DT, RI, TTI, UI); |
| 1428 | } |
| 1429 | |
| 1430 | PreservedAnalyses StructurizeCFGPass::run(Function &F, |
| 1431 | FunctionAnalysisManager &AM) { |
| 1432 | DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F); |
| 1433 | auto &RI = AM.getResult<RegionInfoAnalysis>(IR&: F); |
| 1434 | TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(IR&: F); |
| 1435 | const ScalarOptions &Opts = getScalarOptions(F); |
| 1436 | const UniformityInfo *UI = nullptr; |
| 1437 | if (valueOr(X: Opts.structurizecfg_skip_uniform_regions, Default: SkipUniformRegions)) |
| 1438 | UI = &AM.getResult<UniformityInfoAnalysis>(IR&: F); |
| 1439 | |
| 1440 | if (!runImpl(DT, RI, TTI, UI)) |
| 1441 | return PreservedAnalyses::all(); |
| 1442 | PreservedAnalyses PA; |
| 1443 | PA.preserve<DominatorTreeAnalysis>(); |
| 1444 | return PA; |
| 1445 | } |
| 1446 | |