diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -115,6 +115,7 @@ void initializeConstantMergeLegacyPassPass(PassRegistry&); void initializeConstantPropagationPass(PassRegistry&); void initializeControlHeightReductionLegacyPassPass(PassRegistry&); +void initializeConvergenceControlHeuristicLegacyPassPass(PassRegistry&); void initializeConvergenceInfoWrapperPassPass(PassRegistry&); void initializeCorrelatedValuePropagationPass(PassRegistry&); void initializeCostModelAnalysisPass(PassRegistry&); diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -15,6 +15,7 @@ CloneModule.cpp CodeExtractor.cpp CodeMoverUtils.cpp + ConvergenceControlHeuristic.cpp CtorUtils.cpp Debugify.cpp DemoteRegToStack.cpp diff --git a/llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp b/llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp @@ -0,0 +1,282 @@ +//===- ConvergenceControlHeuristic.cpp ------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +/// \brief Heuristic insertion of convergence control tokens +/// +/// This pass converts uncontrolled convergent operations to controlled ones +/// by inserting entry, anchor and loop intrinsics as well as operand bundles +/// according to the following heuristics: +/// +/// 1. In acyclic code, refer to the nearest dominating convergence token if +/// one exists. +/// 2. Otherwise, refer to an `entry` intrinsic if the containing function +/// is convergent, and to an `anchor` intrinsic otherwise. +/// 3. In natural loops, refer to a `loop` heart intrinsic in the loop header. +/// 4. In irreducible cycles, place a heart intrinsic in one of the maximal +/// dominating blocks inside the cycle, and anchor intrinsics in any others. +/// +/// These heuristics will often succeed at inserting convergence control tokens +/// in a way that reflects the intention of a programmer writing high-level +/// language code -- but there are exceptions. Frontends should prefer to +/// insert the tokens directly based on additional information that is +/// available in the HLL source. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ConvergenceUtils.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" + +using namespace llvm; + +#define DEBUG_TYPE "convergence-control-heuristic" + +namespace { + +class ConvergenceControlHeuristic { + Function &m_function; + DominatorTree &m_domTree; + ConvergenceInfo &m_convergenceInfo; + +public: + ConvergenceControlHeuristic(Function &function, DominatorTree &domTree, + ConvergenceInfo &convergenceInfo) + : m_function(function), m_domTree(domTree), + m_convergenceInfo(convergenceInfo) {} + + bool run(); + +private: + ConvergentOperation *findOrInsertToken(BasicBlock *block, + ConvergentOperation *op, + const Cycle *cycle); +}; + +struct ConvergenceControlHeuristicLegacyPass : public FunctionPass { + static char ID; + + ConvergenceControlHeuristicLegacyPass() : FunctionPass(ID) { + initializeConvergenceControlHeuristicLegacyPassPass( + *PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &fn) override { + DominatorTree &domTree = + getAnalysis().getDomTree(); + ConvergenceInfo &convergenceInfo = + getAnalysis().getConvergenceInfo(); + ConvergenceControlHeuristic cch(fn, domTree, convergenceInfo); + return cch.run(); + } + + void getAnalysisUsage(AnalysisUsage &au) const override { + au.addRequired(); + au.addRequired(); + + au.addPreserved(); + au.setPreservesCFG(); + } +}; + +} // end anonymous namespace + +char ConvergenceControlHeuristicLegacyPass::ID = 0; + +INITIALIZE_PASS_BEGIN(ConvergenceControlHeuristicLegacyPass, DEBUG_TYPE, + "Heuristically insert convergence control bundles", false, + false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ConvergenceInfoWrapperPass) +INITIALIZE_PASS_END(ConvergenceControlHeuristicLegacyPass, DEBUG_TYPE, + "Heuristically insert convergence control bundles", false, + false) + +bool ConvergenceControlHeuristic::run() { + // Take a copy of uncontrolled operations -- this is because we may be + // changing the set of roots. + SmallVector uncontrolled; + for (ConvergentOperation *op : m_convergenceInfo.roots()) { + if (op->getKind() == ConvergentOperation::Uncontrolled) + uncontrolled.push_back(op); + } + + for (ConvergentOperation *op : uncontrolled) { + ConvergentOperation *token = + findOrInsertToken(op->getBlock(), op, op->getCycle()); + + if (auto *call = dyn_cast(op->getInstruction())) { + // Recreate the call, adding a single additional operand bundle. + IRBuilder<> builder(call); + + SmallVector args(call->args()); + SmallVector bundles; + + for (const auto &boi : call->bundle_op_infos()) + bundles.emplace_back(call->operandBundleFromBundleOpInfo(boi)); + + bundles.push_back(m_convergenceInfo.makeOperandBundleDef(token)); + + CallInst *newCall = + builder.CreateCall(call->getFunctionType(), call->getCalledOperand(), + args, bundles, call->getName()); + newCall->setAttributes(call->getAttributes()); + newCall->copyMetadata(*call); + + m_convergenceInfo.insertOperation(token, ConvergentOperation::User, + newCall->getParent(), newCall); + m_convergenceInfo.eraseOperation(op); + + call->replaceAllUsesWith(newCall); + call->eraseFromParent(); + } else { + LLVM_DEBUG(dbgs() << "unhandled operation type: " << *op->getInstruction() + << '\n'); + } + } + + return !uncontrolled.empty(); +} + +/// Find or insert a convergent operation producing a token suitable for use +/// inside \p block for a convergent operation that is associated to \p cycle. +/// If \p op is non-null, the location is the indicated operation inside the +/// block; otherwise it is at the end of the block. +ConvergentOperation *ConvergenceControlHeuristic::findOrInsertToken( + BasicBlock *block, ConvergentOperation *op, const Cycle *cycle) { + auto reverseBlockOps = llvm::reverse(m_convergenceInfo.block(block)); + auto it = std::begin(reverseBlockOps); + + if (op) { + do { /* nothing */ + } while (*it++ != op); + } + + auto findToken = [cycle](auto opRange) -> ConvergentOperation * { + for (ConvergentOperation *op : opRange) { + if (op->getKind() == ConvergentOperation::Anchor || + op->getKind() == ConvergentOperation::Entry || + op->getKind() == ConvergentOperation::Copy || + op->getKind() == ConvergentOperation::Heart) { + if (op->getCycle() == cycle) + return op; + } + } + return nullptr; + }; + + ConvergentOperation *token = + findToken(llvm::make_range(it, std::end(reverseBlockOps))); + if (token) + return token; + + const CycleInfo &cycleInfo = m_convergenceInfo.getCycleInfo(); + DomTreeNode *blockNode = m_domTree.getNode(block); + + for (DomTreeNode *parentNode; (parentNode = blockNode->getIDom()) != nullptr; + blockNode = parentNode) { + const Cycle *parentCycle = cycleInfo.getCycle(parentNode->getBlock()); + if (parentCycle == cycle) { + // Block in the same cycle as the operation. Scan backwards for + // a token to use. + token = findToken( + llvm::reverse(m_convergenceInfo.block(parentNode->getBlock()))); + if (token) + return token; + continue; + } + + // Skip over blocks in inner cycles (relative to the cycle that we're + // trying to find the token for). + if (cycleInfo.contains(cycle, parentCycle)) + continue; + + // We're at the "top" of the cycle we're trying to find the token for, + // i.e. blockNode is a node of the cycle whose immediate dominator is + // outside the cycle. Insert a heart or anchor. + assert(cycleInfo.getCycle(blockNode->getBlock()) == cycle); + + block = blockNode->getBlock(); + bool insertHeart = false; + + // If there's no heart in the cycle yet, we can potentially insert a heart + // here. However, a prerequisite for being able to do this reliably without + // breaking the validity of the program is that there is a dominator in + // the direct parent cycle. This isn't always the case in irreducible + // control flow. Example: + // + // I + // / \ + // A<->B + // ^ ^ + // | | + // v v + // C D + // | | + // + // There are two cycles here. Without loss of generality, assume that the + // DFS during cycle analysis was chosen such that the cycle hierarchy is: + // + // Depth 1: Header A, additional entry B, additional blocks C & D + // Depth 2: Header B, additional block D + // + // If we're at block B, we can just insert a heart, because if we were to + // later also insert a heart in A for the outer cycle, we'd then have a + // cycle that goes through two heart uses of a token without going through + // its definition. + if (!m_convergenceInfo.getHeartBlock(cycle)) { + if (parentCycle == cycle->getParent()) { + insertHeart = true; + } else { + // We may find a block in the direct parent further up in the dominator + // tree, e.g. in cases with successive self-loops: + // + // | + // A + // | + // B] + // | + // C] + // | + // + // Starting at block C, we find a dominator in the direct parent cycle + // at A. + for (DomTreeNode *parentNode = blockNode->getIDom(); parentNode; + parentNode = parentNode->getIDom()) { + const Cycle *parentCycle = cycleInfo.getCycle(parentNode->getBlock()); + if (parentCycle == cycle->getParent()) { + insertHeart = true; + break; + } + if (cycleInfo.contains(parentCycle, cycle)) + break; // no more chance of finding a block in the direct parent + } + } + } + + ConvergentOperation *parent = nullptr; + if (insertHeart) { + parent = findOrInsertToken(parentNode->getBlock(), nullptr, + cycle->getParent()); + } + + return m_convergenceInfo.createIntrinsic( + insertHeart ? ConvergentOperation::Heart : ConvergentOperation::Anchor, + parent, block, block->getFirstInsertionPt()); + } + + // We've reached the entry block without finding a suitable intrinsic. + // Insert an entry or anchor. + block = blockNode->getBlock(); + assert(block == &m_function.getEntryBlock()); + + return m_convergenceInfo.createIntrinsic( + m_function.isConvergent() ? ConvergentOperation::Entry + : ConvergentOperation::Anchor, + nullptr, block, block->getFirstInsertionPt()); +} diff --git a/llvm/lib/Transforms/Utils/Utils.cpp b/llvm/lib/Transforms/Utils/Utils.cpp --- a/llvm/lib/Transforms/Utils/Utils.cpp +++ b/llvm/lib/Transforms/Utils/Utils.cpp @@ -29,6 +29,7 @@ initializeBreakCriticalEdgesPass(Registry); initializeCanonicalizeAliasesLegacyPassPass(Registry); initializeCanonicalizeFreezeInLoopsPass(Registry); + initializeConvergenceControlHeuristicLegacyPassPass(Registry); initializeInstNamerPass(Registry); initializeLCSSAWrapperPassPass(Registry); initializeLibCallsShrinkWrapLegacyPassPass(Registry); diff --git a/llvm/test/Transforms/ConvergenceControlHeuristic/basic.ll b/llvm/test/Transforms/ConvergenceControlHeuristic/basic.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/ConvergenceControlHeuristic/basic.ll @@ -0,0 +1,191 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -S -convergence-control-heuristic | FileCheck %s -check-prefix=CHECK + +define void @empty() { +; CHECK-LABEL: @empty( +; CHECK-NEXT: ret void +; + ret void +} + +define void @simple_convergent() convergent { +; CHECK-LABEL: @simple_convergent( +; CHECK-NEXT: [[TMP1:%.*]] = call token @llvm.experimental.convergence.entry() +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ] +; CHECK-NEXT: ret void +; + call void @convergent.op(i32 0) + ret void +} + +define void @simple_nonconvergent() { +; CHECK-LABEL: @simple_nonconvergent( +; CHECK-NEXT: [[TMP1:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ] +; CHECK-NEXT: ret void +; + call void @convergent.op(i32 0) + ret void +} + +define void @preserve_bundles_and_metadata() { +; CHECK-LABEL: @preserve_bundles_and_metadata( +; CHECK-NEXT: [[TMP1:%.*]] = call token @llvm.experimental.convergence.anchor(), !dbg !1 +; CHECK-NEXT: call void @convergent.op(i32 0) [ "unknown-bundle"(i32 0), "convergencectrl"(token [[TMP1]]) ], !dbg !1, !unknown !5 +; CHECK-NEXT: ret void +; + call void @convergent.op(i32 0) [ "unknown-bundle"(i32 0) ], !dbg !2, !unknown !0 + ret void +} + +define void @acyclic() convergent { +; CHECK-LABEL: @acyclic( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = call token @llvm.experimental.convergence.entry() +; CHECK-NEXT: br i1 undef, label [[A:%.*]], label [[B:%.*]] +; CHECK: A: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: br label [[B]] +; CHECK: B: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: ret void +; +entry: + br i1 undef, label %A, label %B + +A: + call void @convergent.op(i32 0) + br label %B + +B: + call void @convergent.op(i32 0) + ret void +} + +; +; | +; A] +; | +; /->B +; | |\ +; | | C] +; | |/ +; ^-B +; ^ ^ +; | | +; v v +; C D +; \ / +; E +; +define void @irreducible() convergent { +; CHECK-LABEL: @irreducible( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = call token @llvm.experimental.convergence.entry() +; CHECK-NEXT: br i1 undef, label [[A:%.*]], label [[B:%.*]] +; CHECK: A: +; CHECK-NEXT: [[TMP1:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[C:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TMP2:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP2]]) ] +; CHECK-NEXT: br i1 undef, label [[A]], label [[D:%.*]] +; CHECK: C: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ] +; CHECK-NEXT: br i1 undef, label [[A]], label [[E:%.*]] +; CHECK: D: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP2]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[E]] +; CHECK: E: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: ret void +; +entry: + br i1 undef, label %A, label %B + +A: + call void @convergent.op(i32 0) + br i1 undef, label %B, label %C + +B: + call void @convergent.op(i32 0) + br i1 undef, label %A, label %D + +C: + call void @convergent.op(i32 0) + br i1 undef, label %A, label %E + +D: + call void @convergent.op(i32 0) + br i1 undef, label %B, label %E + +E: + call void @convergent.op(i32 0) + ret void +} + +!llvm.module.flags = !{!1} + +!0 = !{} +!1 = !{i32 2, !"Debug Info Version", i32 3} +!2 = !DILocation(scope: !3) +!3 = distinct !DISubprogram(name: "main", unit: !4) +!4 = distinct !DICompileUnit(language: DW_LANG_C99, file: !5) +!5 = !DIFile(filename: "foo", directory: "bar") + +declare void @convergent.op(i32) convergent diff --git a/llvm/test/Transforms/ConvergenceControlHeuristic/inlineasm.ll b/llvm/test/Transforms/ConvergenceControlHeuristic/inlineasm.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/ConvergenceControlHeuristic/inlineasm.ll @@ -0,0 +1,12 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -S -convergence-control-heuristic | FileCheck %s -check-prefix=CHECK + +define void @basic() { +; CHECK-LABEL: @basic( +; CHECK-NEXT: [[TMP1:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: call void asm sideeffect "dummy", ""() #1 [ "convergencectrl"(token [[TMP1]]) ] +; CHECK-NEXT: ret void +; + call void asm sideeffect "dummy", ""() convergent + ret void +} diff --git a/llvm/test/Transforms/ConvergenceControlHeuristic/preexisting.ll b/llvm/test/Transforms/ConvergenceControlHeuristic/preexisting.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/ConvergenceControlHeuristic/preexisting.ll @@ -0,0 +1,347 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -S -convergence-control-heuristic | FileCheck %s -check-prefix=CHECK + +define void @simple() convergent { +; CHECK-LABEL: @simple( +; CHECK-NEXT: A: +; CHECK-NEXT: [[A:%.*]] = call token @llvm.experimental.convergence.entry() +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[A]]) ] +; CHECK-NEXT: call void @convergent.op(i32 1) [ "convergencectrl"(token [[A]]) ] +; CHECK-NEXT: ret void +; +A: + %a = call token @llvm.experimental.convergence.entry() + call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ] + call void @convergent.op(i32 1) + ret void +} + +define void @simple2() { +; CHECK-LABEL: @simple2( +; CHECK-NEXT: A: +; CHECK-NEXT: [[A:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[A]]) ] +; CHECK-NEXT: call void @convergent.op(i32 1) [ "convergencectrl"(token [[A]]) ] +; CHECK-NEXT: ret void +; +A: + %a = call token @llvm.experimental.convergence.anchor() + call void @convergent.op(i32 0) + call void @convergent.op(i32 1) [ "convergencectrl"(token %a) ] + ret void +} + +define void @natural_loop() { +; CHECK-LABEL: @natural_loop( +; CHECK-NEXT: A: +; CHECK-NEXT: [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br label [[B:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[C:%.*]] +; CHECK: C: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: ret void +; +A: + %tok.a = call token @llvm.experimental.convergence.anchor() + br label %B + +B: + %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ] + call void @convergent.op(i32 0) + br i1 undef, label %B, label %C + +C: + call void @convergent.op(i32 0) + ret void +} + +define void @natural_loop2() { +; CHECK-LABEL: @natural_loop2( +; CHECK-NEXT: A: +; CHECK-NEXT: [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br label [[B:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[C:%.*]] +; CHECK: C: +; CHECK-NEXT: [[TMP0:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: br i1 undef, label [[C]], label [[D:%.*]] +; CHECK: D: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: ret void +; +A: + %tok.a = call token @llvm.experimental.convergence.anchor() + br label %B + +B: + %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ] + br i1 undef, label %B, label %C + +C: + call void @convergent.op(i32 0) + br i1 undef, label %C, label %D + +D: + call void @convergent.op(i32 0) + ret void +} + +define void @natural_loop_extended1() { +; CHECK-LABEL: @natural_loop_extended1( +; CHECK-NEXT: A: +; CHECK-NEXT: [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br label [[B:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[C:%.*]] +; CHECK: C: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ] +; CHECK-NEXT: call void @convergent.op(i32 1) [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: ret void +; +A: + %tok.a = call token @llvm.experimental.convergence.anchor() + br label %B + +B: + %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ] + br i1 undef, label %B, label %C + +C: + call void @convergent.op(i32 0) [ "convergencectrl"(token %tok.b) ] + call void @convergent.op(i32 1) + ret void +} + +define void @natural_loop_extended2() { +; CHECK-LABEL: @natural_loop_extended2( +; CHECK-NEXT: A: +; CHECK-NEXT: [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br label [[B:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[C:%.*]] +; CHECK: C: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ] +; CHECK-NEXT: call void @convergent.op(i32 1) [ "convergencectrl"(token [[TOK_B]]) ] +; CHECK-NEXT: ret void +; +A: + %tok.a = call token @llvm.experimental.convergence.anchor() + br label %B + +B: + %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ] + br i1 undef, label %B, label %C + +C: + call void @convergent.op(i32 0) + call void @convergent.op(i32 1) [ "convergencectrl"(token %tok.b) ] + ret void +} + +; +; A +; | +; B] +; | +; C] +; | +; D +; |\ +; | E +; |/ +; F +; +define void @natural_loop_extended3() { +; CHECK-LABEL: @natural_loop_extended3( +; CHECK-NEXT: A: +; CHECK-NEXT: [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br label [[B:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[C:%.*]] +; CHECK: C: +; CHECK-NEXT: [[TMP0:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_B]]) ] +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: br i1 undef, label [[C]], label [[D:%.*]] +; CHECK: D: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ] +; CHECK-NEXT: br i1 undef, label [[E:%.*]], label [[F:%.*]] +; CHECK: E: +; CHECK-NEXT: call void @convergent.op(i32 1) [ "convergencectrl"(token [[TOK_B]]) ] +; CHECK-NEXT: br label [[F]] +; CHECK: F: +; CHECK-NEXT: ret void +; +A: + %tok.a = call token @llvm.experimental.convergence.anchor() + br label %B + +B: + %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ] + br i1 undef, label %B, label %C + +C: + call void @convergent.op(i32 0) + br i1 undef, label %C, label %D + +D: + call void @convergent.op(i32 0) + br i1 undef, label %E, label %F + +E: + call void @convergent.op(i32 1) [ "convergencectrl"(token %tok.b) ] + br label %F + +F: + ret void +} + +define void @unusual_heart() { +; CHECK-LABEL: @unusual_heart( +; CHECK-NEXT: A: +; CHECK-NEXT: [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br label [[B:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TMP0:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: br i1 undef, label [[C:%.*]], label [[D:%.*]] +; CHECK: C: +; CHECK-NEXT: [[TOK_C:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_C]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[D]] +; CHECK: D: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[E:%.*]] +; CHECK: E: +; CHECK-NEXT: ret void +; +A: + %tok.a = call token @llvm.experimental.convergence.anchor() + br label %B + +B: + call void @convergent.op(i32 0) + br i1 undef, label %C, label %D + +C: + %tok.c = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ] + call void @convergent.op(i32 0) + br i1 undef, label %B, label %D + +D: + call void @convergent.op(i32 0) + br i1 undef, label %B, label %E + +E: + ret void +} + +; +; | | +; A<->B +; ^ ^ +; | | +; v v +; C D +; \ / +; E +; +define void @irreducible1() { +; CHECK-LABEL: @irreducible1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br i1 undef, label [[A:%.*]], label [[B:%.*]] +; CHECK: A: +; CHECK-NEXT: [[TOK_A:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[C:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TMP0:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br i1 undef, label [[A]], label [[D:%.*]] +; CHECK: C: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_A]]) ] +; CHECK-NEXT: br i1 undef, label [[A]], label [[E:%.*]] +; CHECK: D: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[E]] +; CHECK: E: +; CHECK-NEXT: ret void +; +entry: + %anchor = call token @llvm.experimental.convergence.anchor() + br i1 undef, label %A, label %B + +A: + %tok.a = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ] + br i1 undef, label %B, label %C + +B: + br i1 undef, label %A, label %D + +C: + call void @convergent.op(i32 0) + br i1 undef, label %A, label %E + +D: + call void @convergent.op(i32 0) + br i1 undef, label %B, label %E + +E: + ret void +} + +; Same CFG, different initial loop heart +define void @irreducible2() { +; CHECK-LABEL: @irreducible2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br i1 undef, label [[A:%.*]], label [[B:%.*]] +; CHECK: A: +; CHECK-NEXT: [[TMP0:%.*]] = call token @llvm.experimental.convergence.anchor() +; CHECK-NEXT: br i1 undef, label [[B]], label [[C:%.*]] +; CHECK: B: +; CHECK-NEXT: [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ] +; CHECK-NEXT: br i1 undef, label [[A]], label [[D:%.*]] +; CHECK: C: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ] +; CHECK-NEXT: br i1 undef, label [[A]], label [[E:%.*]] +; CHECK: D: +; CHECK-NEXT: call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ] +; CHECK-NEXT: br i1 undef, label [[B]], label [[E]] +; CHECK: E: +; CHECK-NEXT: ret void +; +entry: + %anchor = call token @llvm.experimental.convergence.anchor() + br i1 undef, label %A, label %B + +A: + br i1 undef, label %B, label %C + +B: + %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ] + br i1 undef, label %A, label %D + +C: + call void @convergent.op(i32 0) + br i1 undef, label %A, label %E + +D: + call void @convergent.op(i32 0) + br i1 undef, label %B, label %E + +E: + ret void +} + +declare void @convergent.op(i32) convergent + +declare token @llvm.experimental.convergence.entry() +declare token @llvm.experimental.convergence.anchor() +declare token @llvm.experimental.convergence.loop()