LLVM 24.0.0git
GenericUniformityImpl.h
Go to the documentation of this file.
1//===- GenericUniformityImpl.h -----------------------*- C++ -*------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This template implementation resides in a separate file so that it
10// does not get injected into every .cpp file that includes the
11// generic header.
12//
13// DO NOT INCLUDE THIS FILE WHEN MERELY USING UNIFORMITYINFO.
14//
15// This file should only be included by files that implement a
16// specialization of the relvant templates. Currently these are:
17// - UniformityAnalysis.cpp
18//
19// Note: The DEBUG_TYPE macro should be defined before using this
20// file so that any use of LLVM_DEBUG is associated with the
21// including file rather than this file.
22//
23//===----------------------------------------------------------------------===//
24///
25/// \file
26/// \brief Implementation of uniformity analysis.
27///
28/// The algorithm is a fixed point iteration that starts with the assumption
29/// that all control flow and all values are uniform. Starting from sources of
30/// divergence (whose discovery must be implemented by a CFG- or even
31/// target-specific derived class), divergence of values is propagated from
32/// definition to uses in a straight-forward way. The main complexity lies in
33/// the propagation of the impact of divergent control flow on the divergence of
34/// values (sync dependencies).
35///
36/// NOTE: In general, no interface exists for a transform to update
37/// (Machine)UniformityInfo. Additionally, (Machine)CycleAnalysis is a
38/// transitive dependence, but it also does not provide an interface for
39/// updating itself. Given that, transforms should not preserve uniformity in
40/// their getAnalysisUsage() callback.
41///
42//===----------------------------------------------------------------------===//
43
44#ifndef LLVM_ADT_GENERICUNIFORMITYIMPL_H
45#define LLVM_ADT_GENERICUNIFORMITYIMPL_H
46
48
49#include "llvm/ADT/DenseSet.h"
50#include "llvm/ADT/STLExtras.h"
51#include "llvm/ADT/SetVector.h"
56
57#define DEBUG_TYPE "uniformity"
58
59namespace llvm {
60
61// Forward decl from llvm/CodeGen/MachineInstr.h
62class MachineInstr;
63
64/// Construct a specially modified post-order traversal of cycles.
65///
66/// The ModifiedPO is contructed using a virtually modified CFG as follows:
67///
68/// 1. The successors of pre-entry nodes (predecessors of an cycle
69/// entry that are outside the cycle) are replaced by the
70/// successors of the successors of the header.
71/// 2. Successors of the cycle header are replaced by the exit blocks
72/// of the cycle.
73///
74/// Effectively, we produce a depth-first numbering with the following
75/// properties:
76///
77/// 1. Nodes after a cycle are numbered earlier than the cycle header.
78/// 2. The header is numbered earlier than the nodes in the cycle.
79/// 3. The numbering of the nodes within the cycle forms an interval
80/// starting with the header.
81///
82/// Effectively, the virtual modification arranges the nodes in a
83/// cycle as a DAG with the header as the sole leaf, and successors of
84/// the header as the roots. A reverse traversal of this numbering has
85/// the following invariant on the unmodified original CFG:
86///
87/// Each node is visited after all its predecessors, except if that
88/// predecessor is the cycle header.
89///
90template <typename ContextT> class ModifiedPostOrder {
91public:
92 using BlockT = typename ContextT::BlockT;
93 using FunctionT = typename ContextT::FunctionT;
94 using DominatorTreeT = typename ContextT::DominatorTreeT;
95
97 using const_iterator = typename std::vector<BlockT *>::const_iterator;
98
99 ModifiedPostOrder(const ContextT &C) : Context(C) {}
100
101 bool empty() const { return Order.empty(); }
102 size_t size() const { return Order.size(); }
103
104 void clear() { Order.clear(); }
105 void compute(const CycleInfoT &CI);
106
107 unsigned count(BlockT *BB) const {
108 unsigned Num = GraphTraits<BlockT *>::getNumber(BB);
109 return Num < POIndex.size() && POIndex[Num] != InvalidIndex;
110 }
111 const BlockT *operator[](size_t Idx) const { return Order[Idx]; }
112
113 void appendBlock(const BlockT &BB, bool IsReducibleCycleHeader = false) {
114 unsigned Num = GraphTraits<const BlockT *>::getNumber(&BB);
115 POIndex[Num] = Order.size();
116 Order.push_back(&BB);
117 LLVM_DEBUG(dbgs() << "ModifiedPO(" << POIndex[Num]
118 << "): " << Context.print(&BB) << "\n");
119 if (IsReducibleCycleHeader)
120 ReducibleCycleHeaders.insert(&BB);
121 }
122
123 unsigned getIndex(const BlockT *BB) const {
125 assert(Num < POIndex.size() && POIndex[Num] != InvalidIndex);
126 return POIndex[Num];
127 }
128
129 bool isReducibleCycleHeader(const BlockT *BB) const {
130 return ReducibleCycleHeaders.contains(BB);
131 }
132
133private:
134 static constexpr unsigned InvalidIndex = -1u;
135
137 SmallVector<unsigned> POIndex;
138 SmallPtrSet<const BlockT *, 32> ReducibleCycleHeaders;
139 const ContextT &Context;
140
141 void computeCyclePO(const CycleInfoT &CI, CycleRef C,
143
144 void computeStackPO(SmallVectorImpl<const BlockT *> &Stack,
145 const CycleInfoT &CI, CycleRef C,
147};
148
149template <typename> class DivergencePropagator;
150
151/// \class GenericSyncDependenceAnalysis
152///
153/// \brief Locate join blocks for disjoint paths starting at a divergent branch.
154///
155/// An analysis per divergent branch that returns the set of basic
156/// blocks whose phi nodes become divergent due to divergent control.
157/// These are the blocks that are reachable by two disjoint paths from
158/// the branch, or cycle exits reachable along a path that is disjoint
159/// from a path to the cycle latch.
160
161// --- Above line is not a doxygen comment; intentionally left blank ---
162//
163// Originally implemented in SyncDependenceAnalysis.cpp for DivergenceAnalysis.
164//
165// The SyncDependenceAnalysis is used in the UniformityAnalysis to model
166// control-induced divergence in phi nodes.
167//
168// -- Reference --
169// The algorithm is an extension of Section 5 of
170//
171// An abstract interpretation for SPMD divergence
172// on reducible control flow graphs.
173// Julian Rosemann, Simon Moll and Sebastian Hack
174// POPL '21
175//
176//
177// -- Sync dependence --
178// Sync dependence characterizes the control flow aspect of the
179// propagation of branch divergence. For example,
180//
181// %cond = icmp slt i32 %tid, 10
182// br i1 %cond, label %then, label %else
183// then:
184// br label %merge
185// else:
186// br label %merge
187// merge:
188// %a = phi i32 [ 0, %then ], [ 1, %else ]
189//
190// Suppose %tid holds the thread ID. Although %a is not data dependent on %tid
191// because %tid is not on its use-def chains, %a is sync dependent on %tid
192// because the branch "br i1 %cond" depends on %tid and affects which value %a
193// is assigned to.
194//
195//
196// -- Reduction to SSA construction --
197// There are two disjoint paths from A to X, if a certain variant of SSA
198// construction places a phi node in X under the following set-up scheme.
199//
200// This variant of SSA construction ignores incoming undef values.
201// That is paths from the entry without a definition do not result in
202// phi nodes.
203//
204// entry
205// / \
206// A \
207// / \ Y
208// B C /
209// \ / \ /
210// D E
211// \ /
212// F
213//
214// Assume that A contains a divergent branch. We are interested
215// in the set of all blocks where each block is reachable from A
216// via two disjoint paths. This would be the set {D, F} in this
217// case.
218// To generally reduce this query to SSA construction we introduce
219// a virtual variable x and assign to x different values in each
220// successor block of A.
221//
222// entry
223// / \
224// A \
225// / \ Y
226// x = 0 x = 1 /
227// \ / \ /
228// D E
229// \ /
230// F
231//
232// Our flavor of SSA construction for x will construct the following
233//
234// entry
235// / \
236// A \
237// / \ Y
238// x0 = 0 x1 = 1 /
239// \ / \ /
240// x2 = phi E
241// \ /
242// x3 = phi
243//
244// The blocks D and F contain phi nodes and are thus each reachable
245// by two disjoins paths from A.
246//
247// -- Remarks --
248// * In case of cycle exits we need to check for temporal divergence.
249// To this end, we check whether the definition of x differs between the
250// cycle exit and the cycle header (_after_ SSA construction).
251//
252// * In the presence of irreducible control flow, the fixed point is
253// reached only after multiple iterations. This is because labels
254// reaching the header of a cycle must be repropagated through the
255// cycle. This is true even in a reducible cycle, since the labels
256// may have been produced by a nested irreducible cycle.
257//
258// * Note that SyncDependenceAnalysis is not concerned with the points
259// of convergence in an irreducible cycle. It's only purpose is to
260// identify join blocks. The "diverged entry" criterion is
261// separately applied on join blocks to determine if an entire
262// irreducible cycle is assumed to be divergent.
263//
264// * Relevant related work:
265// A simple algorithm for global data flow analysis problems.
266// Matthew S. Hecht and Jeffrey D. Ullman.
267// SIAM Journal on Computing, 4(4):519–532, December 1975.
268//
269template <typename ContextT> class GenericSyncDependenceAnalysis {
270public:
271 using BlockT = typename ContextT::BlockT;
272 using DominatorTreeT = typename ContextT::DominatorTreeT;
273 using FunctionT = typename ContextT::FunctionT;
274 using ValueRefT = typename ContextT::ValueRefT;
275 using InstructionT = typename ContextT::InstructionT;
276
278
281
282 /// Information discovered by the sync dependence analysis for each
283 /// divergent branch.
285 // Join points of diverged paths.
287 // Divergent cycle exits
289 };
290
292
293 GenericSyncDependenceAnalysis(const ContextT &Context,
294 const DominatorTreeT &DT, const CycleInfoT &CI);
295
296 /// \brief Computes divergent join points and cycle exits caused by branch
297 /// divergence in \p Term.
298 ///
299 /// This returns a pair of sets:
300 /// * The set of blocks which are reachable by disjoint paths from
301 /// \p Term.
302 /// * The set also contains cycle exits if there two disjoint paths:
303 /// one from \p Term to the cycle exit and another from \p Term to
304 /// the cycle header.
305 const DivergenceDescriptor &getJoinBlocks(const BlockT *DivTermBlock);
306
307private:
308 static inline DivergenceDescriptor EmptyDivergenceDesc;
309
310 ModifiedPO CyclePO;
311
312 const DominatorTreeT &DT;
313 const CycleInfoT &CI;
314
316 CachedControlDivDescs;
317};
318
319/// \brief Analysis that identifies uniform values in a data-parallel
320/// execution.
321///
322/// This analysis propagates divergence in a data-parallel context
323/// from sources of divergence to all users. It can be instantiated
324/// for an IR that provides a suitable SSAContext.
325template <typename ContextT> class GenericUniformityAnalysisImpl {
326public:
327 using BlockT = typename ContextT::BlockT;
328 using FunctionT = typename ContextT::FunctionT;
329 using ValueRefT = typename ContextT::ValueRefT;
330 using ConstValueRefT = typename ContextT::ConstValueRefT;
331 using UseT = typename ContextT::UseT;
332 using InstructionT = typename ContextT::InstructionT;
333 using DominatorTreeT = typename ContextT::DominatorTreeT;
334
336
339 typename SyncDependenceAnalysisT::DivergenceDescriptor;
340
342 std::tuple<ConstValueRefT, InstructionT *, CycleRef>;
343
346 : Context(CI.getSSAContext()), F(*Context.getFunction()), CI(CI),
347 TTI(TTI), DT(DT), SDA(Context, DT, CI) {}
348
350
351 const FunctionT &getFunction() const { return F; }
352
353 const CycleInfoT &getCycleInfo() const { return CI; }
354
355 /// \brief Mark \p UniVal as a value that is always uniform.
356 void addUniformOverride(const InstructionT &Instr);
357
358 /// \brief Examine \p I for divergent outputs and add to the worklist.
359 void markDivergent(const InstructionT &I);
360
361 /// \brief Mark \p DivVal as a divergent value by removing it from
362 /// UniformValues. \returns Whether the tracked divergence state of
363 /// \p DivVal changed.
364 bool markDivergent(ConstValueRefT DivVal);
365
366 /// \brief Mark outputs of \p Instr as divergent.
367 /// \returns Whether the tracked divergence state of any output has changed.
368 bool markDefsDivergent(const InstructionT &Instr);
369
370 /// \brief Propagate divergence to all instructions in the region.
371 /// Divergence is seeded by calls to \p markDivergent.
372 void compute();
373
374 /// \brief Whether \p Val will always return a uniform value regardless of its
375 /// operands
376 bool isAlwaysUniform(const InstructionT &Instr) const;
377
378 bool hasDivergentDefs(const InstructionT &I) const;
379
381 assert(I.isTerminator() && "Expected a terminator instruction!");
382 return DivergentTermBlocks.contains(I.getParent());
383 };
384
385 /// \brief Whether \p Val is divergent at its definition.
386 /// When the target has no branch divergence, compute() is never called
387 /// and everything is uniform. Otherwise, values not in UniformValues
388 /// (e.g. newly created) are conservatively treated as divergent.
391 return false;
392 // Only values that were present during analysis are tracked in
393 // UniformValues (Instructions/Arguments for IR, Registers for MIR).
394 // Other values (e.g. constants, globals) are always uniform but are
395 // not added to UniformValues; this check avoids false divergence.
396 if (ContextT::isAlwaysUniform(V))
397 return false;
398 return !UniformValues.contains(V);
399 }
400
401 bool isDivergentUse(const UseT &U) const;
402
403 bool hasDivergentTerminator(const BlockT &B) const {
404 return DivergentTermBlocks.contains(&B);
405 }
406
407 void print(raw_ostream &Out) const;
408
409 /// Print divergent arguments and return true if any were found.
410 /// IR specialization iterates F.args(); default is a no-op.
411 bool printDivergentArgs(raw_ostream &Out) const;
412
414
416
417 /// Check if an instruction with Custom uniformity can be proven uniform
418 /// based on its operands. This queries the target-specific callback.
419 bool isCustomUniform(const InstructionT &I) const;
420
421 /// \brief Add an instruction that requires custom uniformity analysis.
423
424protected:
425 const ContextT &Context;
426 const FunctionT &F;
428 const TargetTransformInfo *TTI = nullptr;
429
430 // Whether the target has branch divergence. Set at the start of compute(),
431 // which is only called when the target has branch divergence. When false,
432 // isDivergent() returns false for all values.
434
436
437 // Values known to be uniform. Populated in initialize() with all values,
438 // then values are removed as divergence is propagated. After analysis,
439 // values not in this set are conservatively treated as divergent.
441
442 // Internal worklist for divergence propagation.
443 std::vector<const InstructionT *> Worklist;
444
445 // Set of instructions that require custom uniformity analysis based on
446 // operand uniformity.
448
449 /// \brief Mark \p Term as divergent and push all Instructions that become
450 /// divergent as a result on the worklist.
451 void analyzeControlDivergence(const InstructionT &Term);
452
453private:
454 const DominatorTreeT &DT;
455
456 // Recognized cycles with divergent exits.
457 SmallSetVector<CycleRef, 8> DivergentExitCycles;
458
459 // Cycles assumed to be divergent.
460 //
461 // We don't use a set here because every insertion needs an explicit
462 // traversal of all existing members.
463 SmallVector<CycleRef> AssumedDivergent;
464
465 // The SDA links divergent branches to divergent control-flow joins.
467
468 // Set of known-uniform values.
470
471 /// \brief Mark all nodes in \p JoinBlock as divergent and push them on
472 /// the worklist.
473 void taintAndPushAllDefs(const BlockT &JoinBlock);
474
475 /// \brief Mark all phi nodes in \p JoinBlock as divergent and push them on
476 /// the worklist.
477 void taintAndPushPhiNodes(const BlockT &JoinBlock);
478
479 /// \brief Identify all Instructions that become divergent because \p DivExit
480 /// is a divergent cycle exit of \p DivCycle. Mark those instructions as
481 /// divergent and push them on the worklist.
482 void propagateCycleExitDivergence(const BlockT &DivExit, CycleRef DivCycle);
483
484 /// Mark as divergent all external uses of values defined in \p DefCycle.
485 void analyzeCycleExitDivergence(CycleRef DefCycle);
486
487 /// \brief Mark as divergent all uses of \p I that are outside \p DefCycle.
488 void propagateTemporalDivergence(const InstructionT &I, CycleRef DefCycle);
489
490 /// \brief Push all users of \p Val (in the region) to the worklist.
491 void pushUsers(const InstructionT &I);
492 void pushUsers(ConstValueRefT V);
493
494 bool usesValueFromCycle(const InstructionT &I, CycleRef DefCycle) const;
495
496 /// \brief Whether \p Def is divergent when read in \p ObservingBlock.
497 bool isTemporalDivergent(const BlockT &ObservingBlock,
498 const InstructionT &Def) const;
499};
500
501template <typename ImplT>
505
506/// Compute divergence starting with a divergent branch.
507template <typename ContextT> class DivergencePropagator {
508public:
509 using BlockT = typename ContextT::BlockT;
510 using DominatorTreeT = typename ContextT::DominatorTreeT;
511 using FunctionT = typename ContextT::FunctionT;
512 using ValueRefT = typename ContextT::ValueRefT;
513
515
519 typename SyncDependenceAnalysisT::DivergenceDescriptor;
520
525 const ContextT &Context;
526
527 // Track blocks that receive a new label. Every time we relabel a
528 // cycle header, we another pass over the modified post-order in
529 // order to propagate the header label. The bit vector also allows
530 // us to skip labels that have not changed.
532
533 // divergent join and cycle exit descriptor.
534 std::unique_ptr<DivergenceDescriptorT> DivDesc;
535
536 // Dominating definition at each block on diverged paths, indexed by block
537 // number. Transient to this propagation; not stored in the descriptor.
538 // * label(B) == C : C is the dominating definition at B
539 // * label(B) == nullptr : we haven't seen B yet
540 // * label(B) == B : B is a join of disjoint paths, an immediate
541 // successor of the divergent term, or the term
542 // itself
544
545 const BlockT *&label(const BlockT *BB) {
547 }
548
550 const CycleInfoT &CI, const BlockT &DivTermBlock)
552 Context(CI.getSSAContext()), DivDesc(new DivergenceDescriptorT),
554 GraphTraits<const FunctionT *>::getMaxNumber(CI.getFunction()),
555 nullptr) {}
556
558 Out << "Propagator::BlockLabels {\n";
559 for (int BlockIdx = (int)CyclePOT.size() - 1; BlockIdx >= 0; --BlockIdx) {
560 const auto *Block = CyclePOT[BlockIdx];
561 const auto *Label = label(Block);
562 Out << Context.print(Block) << "(" << BlockIdx << ") : ";
563 if (!Label) {
564 Out << "<null>\n";
565 } else {
566 Out << Context.print(Label) << "\n";
567 }
568 }
569 Out << "}\n";
570 }
571
572 // Push a definition (\p PushedLabel) to \p SuccBlock and return whether this
573 // causes a divergent join.
574 bool computeJoin(const BlockT &SuccBlock, const BlockT &PushedLabel) {
575 const auto *OldLabel = label(&SuccBlock);
576
577 LLVM_DEBUG(dbgs() << "labeling " << Context.print(&SuccBlock) << ":\n"
578 << "\tpushed label: " << Context.print(&PushedLabel)
579 << "\n"
580 << "\told label: " << Context.print(OldLabel) << "\n");
581
582 // Early exit if there is no change in the label.
583 if (OldLabel == &PushedLabel)
584 return false;
585
586 if (OldLabel != &SuccBlock) {
587 auto SuccIdx = CyclePOT.getIndex(&SuccBlock);
588 // Assigning a new label, mark this in FreshLabels.
589 LLVM_DEBUG(dbgs() << "\tfresh label: " << SuccIdx << "\n");
590 FreshLabels.set(SuccIdx);
591 }
592
593 // This is not a join if the succ was previously unlabeled.
594 if (!OldLabel) {
595 LLVM_DEBUG(dbgs() << "\tnew label: " << Context.print(&PushedLabel)
596 << "\n");
597 label(&SuccBlock) = &PushedLabel;
598 return false;
599 }
600
601 // This is a new join. Label the join block as itself, and not as
602 // the pushed label.
603 LLVM_DEBUG(dbgs() << "\tnew label: " << Context.print(&SuccBlock) << "\n");
604 label(&SuccBlock) = &SuccBlock;
605
606 return true;
607 }
608
609 // visiting a virtual cycle exit edge from the cycle header --> temporal
610 // divergence on join
611 bool visitCycleExitEdge(const BlockT &ExitBlock, const BlockT &Label) {
612 if (!computeJoin(ExitBlock, Label))
613 return false;
614
615 // Identified a divergent cycle exit
616 DivDesc->CycleDivBlocks.insert(&ExitBlock);
617 LLVM_DEBUG(dbgs() << "\tDivergent cycle exit: " << Context.print(&ExitBlock)
618 << "\n");
619 return true;
620 }
621
622 // process \p SuccBlock with reaching definition \p Label
623 bool visitEdge(const BlockT &SuccBlock, const BlockT &Label) {
624 if (!computeJoin(SuccBlock, Label))
625 return false;
626
627 // Divergent, disjoint paths join.
628 DivDesc->JoinDivBlocks.insert(&SuccBlock);
629 LLVM_DEBUG(dbgs() << "\tDivergent join: " << Context.print(&SuccBlock)
630 << "\n");
631 return true;
632 }
633
634 std::unique_ptr<DivergenceDescriptorT> computeJoinPoints() {
636
637 LLVM_DEBUG(dbgs() << "SDA:computeJoinPoints: "
638 << Context.print(&DivTermBlock) << "\n");
639
640 int DivTermIdx = CyclePOT.getIndex(&DivTermBlock);
641 CycleRef DivTermCycle = CI.getCycle(&DivTermBlock);
642
643 // Locate the largest ancestor cycle that is not reducible and does not
644 // contain a reducible ancestor. This is done with a lambda that is defined
645 // and invoked in the same statement.
646 CycleRef IrreducibleAncestor = [this](CycleRef C) -> CycleRef {
647 if (!C)
648 return CycleRef();
649 if (CI.isReducible(C))
650 return CycleRef();
651 while (CycleRef P = CI.getParentCycle(C)) {
652 if (CI.isReducible(P))
653 return C;
654 C = P;
655 }
656 assert(!CI.getParentCycle(C));
657 assert(!CI.isReducible(C));
658 return C;
659 }(DivTermCycle);
660
661 // Bootstrap with branch targets
662 for (const auto *SuccBlock : successors(&DivTermBlock)) {
663 if (DivTermCycle && !CI.contains(DivTermCycle, SuccBlock)) {
664 // If DivTerm exits the cycle immediately, computeJoin() might
665 // not reach SuccBlock with a different label. We need to
666 // check for this exit now.
667 DivDesc->CycleDivBlocks.insert(SuccBlock);
668 LLVM_DEBUG(dbgs() << "\tImmediate divergent cycle exit: "
669 << Context.print(SuccBlock) << "\n");
670 }
671 visitEdge(*SuccBlock, *SuccBlock);
672 }
673
674 // Technically propagation can continue until it reaches the last node.
675 //
676 // For efficiency, propagation can stop if FreshLabels.count()==1. But
677 // For irreducible cycles, let propagation continue until it reaches
678 // out of irreducible cycles (see code for details.)
679 while (true) {
680 auto BlockIdx = FreshLabels.find_last();
681 if (BlockIdx == -1)
682 break;
683
684 const auto *Block = CyclePOT[BlockIdx];
685 // If no irreducible cycle, stop if freshLable.count() = 1 and Block
686 // is the IPD. If it is in any irreducible cycle, continue propagation.
687 if (FreshLabels.count() == 1 &&
688 (!IrreducibleAncestor || !CI.contains(IrreducibleAncestor, Block)))
689 break;
690
691 LLVM_DEBUG(dbgs() << "Current labels:\n"; printDefs(dbgs()));
692
693 FreshLabels.reset(BlockIdx);
694 if (BlockIdx == DivTermIdx) {
695 LLVM_DEBUG(dbgs() << "Skipping DivTermBlock\n");
696 continue;
697 }
698
699 LLVM_DEBUG(dbgs() << "visiting " << Context.print(Block) << " at index "
700 << BlockIdx << "\n");
701
702 const auto *Label = label(Block);
703 assert(Label);
704
705 // If the current block is the header of a reducible cycle, then the label
706 // should be propagated to the cycle exits. If this cycle contains the
707 // branch, then those exits are divergent exits. This is true for any DFS.
708 //
709 // If some DFS has a reducible cycle C with header H, then for
710 // any other DFS, H is the header of a cycle C' that is a
711 // superset of C.
712 //
713 // - For a divergent branch inside the subgraph C, any join node inside
714 // C is either H, or some node encountered by paths within C, without
715 // passing through H.
716 //
717 // - For a divergent branch outside the subgraph C, H is the only node
718 // in C reachable from multiple paths since it is the only entry to C.
719 LLVM_DEBUG(dbgs() << "Check for reducible cycle: " << Context.print(Block)
720 << '\n');
721 if (CyclePOT.isReducibleCycleHeader(Block)) {
722 CycleRef BlockCycle = CI.getCycle(Block);
723 LLVM_DEBUG(dbgs() << CI.print(BlockCycle) << '\n');
724 SmallVector<BlockT *, 4> BlockCycleExits;
725 CI.getExitBlocks(BlockCycle, BlockCycleExits);
726 bool BranchIsInside = CI.contains(BlockCycle, &DivTermBlock);
727 for (auto *BlockCycleExit : BlockCycleExits) {
728 if (BranchIsInside)
729 visitCycleExitEdge(*BlockCycleExit, *Label);
730 else
731 visitEdge(*BlockCycleExit, *Label);
732 }
733 } else {
734 for (const auto *SuccBlock : successors(Block))
735 visitEdge(*SuccBlock, *Label);
736 }
737 }
738
739 LLVM_DEBUG(dbgs() << "Final labeling:\n"; printDefs(dbgs()));
740
741 // Check every cycle containing DivTermBlock for exit divergence.
742 // A cycle has exit divergence if the label of an exit block does
743 // not match the label of its header.
744 for (auto C = CI.getCycle(&DivTermBlock); C; C = CI.getParentCycle(C)) {
745 if (CI.isReducible(C)) {
746 // The exit divergence of a reducible cycle is recorded while
747 // propagating labels.
748 continue;
749 }
751 CI.getExitBlocks(C, Exits);
752 auto *Header = CI.getHeader(C);
753 auto *HeaderLabel = label(Header);
754 for (const auto *Exit : Exits) {
755 if (label(Exit) != HeaderLabel) {
756 // Identified a divergent cycle exit
757 DivDesc->CycleDivBlocks.insert(Exit);
758 LLVM_DEBUG(dbgs() << "\tDivergent cycle exit: " << Context.print(Exit)
759 << "\n");
760 }
761 }
762 }
763
764 return std::move(DivDesc);
765 }
766};
767
768template <typename ContextT>
770 const ContextT &Context, const DominatorTreeT &DT, const CycleInfoT &CI)
771 : CyclePO(Context), DT(DT), CI(CI) {
772 CyclePO.compute(CI);
773}
774
775template <typename ContextT>
777 const BlockT *DivTermBlock) -> const DivergenceDescriptor & {
778 // trivial case
779 if (succ_size(DivTermBlock) <= 1) {
780 return EmptyDivergenceDesc;
781 }
782
783 // already available in cache?
784 auto ItCached = CachedControlDivDescs.find(DivTermBlock);
785 if (ItCached != CachedControlDivDescs.end())
786 return *ItCached->second;
787
788 // compute all join points
789 DivergencePropagatorT Propagator(CyclePO, DT, CI, *DivTermBlock);
790 auto DivDesc = Propagator.computeJoinPoints();
791
792 auto PrintBlockSet = [&](ConstBlockSet &Blocks) {
793 return Printable([&](raw_ostream &Out) {
794 Out << "[";
795 ListSeparator LS;
796 for (const auto *BB : Blocks) {
797 Out << LS << CI.getSSAContext().print(BB);
798 }
799 Out << "]\n";
800 });
801 };
802
804 dbgs() << "\nResult (" << CI.getSSAContext().print(DivTermBlock)
805 << "):\n JoinDivBlocks: " << PrintBlockSet(DivDesc->JoinDivBlocks)
806 << " CycleDivBlocks: " << PrintBlockSet(DivDesc->CycleDivBlocks)
807 << "\n");
808 (void)PrintBlockSet;
809
810 auto ItInserted =
811 CachedControlDivDescs.try_emplace(DivTermBlock, std::move(DivDesc));
812 assert(ItInserted.second);
813 return *ItInserted.first->second;
814}
815
816template <typename ContextT>
818 const InstructionT &I) {
819 if (isAlwaysUniform(I))
820 return;
821 // For custom uniformity candidates, check if the instruction can be
822 // proven uniform based on which operands are uniform/divergent.
823 // The candidate will be re-evaluated as operands become divergent.
824 if (CustomUniformityCandidates.contains(&I)) {
825 if (isCustomUniform(I))
826 return;
827 }
828 bool Marked = false;
829 if (I.isTerminator()) {
830 Marked = DivergentTermBlocks.insert(I.getParent()).second;
831 if (Marked) {
832 LLVM_DEBUG(dbgs() << "marked divergent term block: "
833 << Context.print(I.getParent()) << "\n");
834 }
835 } else {
836 Marked = markDefsDivergent(I);
837 }
838
839 if (Marked)
840 Worklist.push_back(&I);
841}
842
843template <typename ContextT>
845 ConstValueRefT Val) {
846 if (UniformValues.erase(Val)) {
847 LLVM_DEBUG(dbgs() << "marked divergent: " << Context.print(Val) << "\n");
848 return true;
849 }
850 return false;
851}
852
853template <typename ContextT>
855 const InstructionT &Instr) {
856 UniformOverrides.insert(&Instr);
857}
858
859template <typename ContextT>
864
865// Mark as divergent all external uses of values defined in \p DefCycle.
866//
867// A value V defined by a block B inside \p DefCycle may be used outside the
868// cycle only if the use is a PHI in some exit block, or B dominates some exit
869// block. Thus, we check uses as follows:
870//
871// - Check all PHIs in all exit blocks for inputs defined inside \p DefCycle.
872// - For every block B inside \p DefCycle that dominates at least one exit
873// block, check all uses outside \p DefCycle.
874//
875// FIXME: This function does not distinguish between divergent and uniform
876// exits. For each divergent exit, only the values that are live at that exit
877// need to be propagated as divergent at their use outside the cycle.
878template <typename ContextT>
879void GenericUniformityAnalysisImpl<ContextT>::analyzeCycleExitDivergence(
880 CycleRef DefCycle) {
882 CI.getExitBlocks(DefCycle, Exits);
883 for (auto *Exit : Exits) {
884 for (auto &Phi : Exit->phis()) {
885 if (usesValueFromCycle(Phi, DefCycle)) {
886 markDivergent(Phi);
887 }
888 }
889 }
890
891 for (auto *BB : CI.getBlocks(DefCycle)) {
892 if (!llvm::any_of(Exits,
893 [&](BlockT *Exit) { return DT.dominates(BB, Exit); }))
894 continue;
895 for (auto &II : *BB) {
896 propagateTemporalDivergence(II, DefCycle);
897 }
898 }
899}
900
901template <typename ContextT>
902void GenericUniformityAnalysisImpl<ContextT>::propagateCycleExitDivergence(
903 const BlockT &DivExit, CycleRef InnerDivCycle) {
904 LLVM_DEBUG(dbgs() << "\tpropCycleExitDiv " << Context.print(&DivExit)
905 << "\n");
906 CycleRef DivCycle = InnerDivCycle;
907 CycleRef OuterDivCycle = DivCycle;
908 CycleRef ExitLevelCycle = CI.getCycle(&DivExit);
909 const unsigned CycleExitDepth =
910 ExitLevelCycle ? CI.getDepth(ExitLevelCycle) : 0;
911
912 // Find outer-most cycle that does not contain \p DivExit
913 while (DivCycle && CI.getDepth(DivCycle) > CycleExitDepth) {
914 LLVM_DEBUG(dbgs() << " Found exiting cycle: "
915 << Context.print(CI.getHeader(DivCycle)) << "\n");
916 OuterDivCycle = DivCycle;
917 DivCycle = CI.getParentCycle(DivCycle);
918 }
919 LLVM_DEBUG(dbgs() << "\tOuter-most exiting cycle: "
920 << Context.print(CI.getHeader(OuterDivCycle)) << "\n");
921
922 if (!DivergentExitCycles.insert(OuterDivCycle))
923 return;
924
925 // Exit divergence does not matter if the cycle itself is assumed to
926 // be divergent.
927 for (auto C : AssumedDivergent) {
928 if (CI.contains(C, OuterDivCycle))
929 return;
930 }
931
932 analyzeCycleExitDivergence(OuterDivCycle);
933}
934
935template <typename ContextT>
936void GenericUniformityAnalysisImpl<ContextT>::taintAndPushAllDefs(
937 const BlockT &BB) {
938 LLVM_DEBUG(dbgs() << "taintAndPushAllDefs " << Context.print(&BB) << "\n");
939 for (const auto &I : instrs(BB)) {
940 // Terminators do not produce values; they are divergent only if
941 // the condition is divergent. That is handled when the divergent
942 // condition is placed in the worklist.
943 if (I.isTerminator())
944 break;
945
946 markDivergent(I);
947 }
948}
949
950/// Mark divergent phi nodes in a join block
951template <typename ContextT>
952void GenericUniformityAnalysisImpl<ContextT>::taintAndPushPhiNodes(
953 const BlockT &JoinBlock) {
954 LLVM_DEBUG(dbgs() << "taintAndPushPhiNodes in " << Context.print(&JoinBlock)
955 << "\n");
956 for (const auto &Phi : JoinBlock.phis()) {
957 // FIXME: The non-undef value is not constant per se; it just happens to be
958 // uniform and may not dominate this PHI. So assuming that the same value
959 // reaches along all incoming edges may itself be undefined behaviour. This
960 // particular interpretation of the undef value was added to
961 // DivergenceAnalysis in the following review:
962 //
963 // https://reviews.llvm.org/D19013
964 if (ContextT::isConstantOrUndefValuePhi(Phi))
965 continue;
966 markDivergent(Phi);
967 }
968}
969
970/// Add \p Candidate to \p Cycles if it is not already contained in \p Cycles.
971///
972/// \return true iff \p Candidate was added to \p Cycles.
973template <typename CycleInfoT>
974bool insertIfNotContained(const CycleInfoT &CI, SmallVector<CycleRef> &Cycles,
975 CycleRef Candidate) {
976 if (llvm::any_of(Cycles,
977 [&](CycleRef C) { return CI.contains(C, Candidate); }))
978 return false;
979 Cycles.push_back(Candidate);
980 return true;
981}
982
983/// Return the outermost cycle made divergent by branch outside it.
984///
985/// If two paths that diverged outside an irreducible cycle join
986/// inside that cycle, then that whole cycle is assumed to be
987/// divergent. This does not apply if the cycle is reducible.
988template <typename CycleInfoT, typename BlockT>
989CycleRef getExtDivCycle(const CycleInfoT &CI, CycleRef Cycle,
990 const BlockT *DivTermBlock, const BlockT *JoinBlock) {
991 assert(Cycle);
992 assert(CI.contains(Cycle, JoinBlock));
993
994 if (CI.contains(Cycle, DivTermBlock))
995 return CycleRef();
996
997 CycleRef OriginalCycle = Cycle;
998 CycleRef Parent = CI.getParentCycle(Cycle);
999 while (Parent && !CI.contains(Parent, DivTermBlock)) {
1000 Cycle = Parent;
1001 Parent = CI.getParentCycle(Cycle);
1002 }
1003
1004 // If the original cycle is not the outermost cycle, then the outermost cycle
1005 // is irreducible. If the outermost cycle were reducible, then external
1006 // diverged paths would not reach the original inner cycle.
1007 (void)OriginalCycle;
1008 assert(Cycle == OriginalCycle || !CI.isReducible(Cycle));
1009
1010 if (CI.isReducible(Cycle)) {
1011 assert(CI.getHeader(Cycle) == JoinBlock);
1012 return CycleRef();
1013 }
1014
1015 LLVM_DEBUG(dbgs() << "cycle made divergent by external branch\n");
1016 return Cycle;
1017}
1018
1019/// Return the outermost cycle made divergent by branch inside it.
1020///
1021/// This checks the "diverged entry" criterion defined in the
1022/// docs/ConvergenceAnalysis.html.
1023template <typename ContextT, typename CycleInfoT, typename BlockT,
1024 typename DominatorTreeT>
1025CycleRef getIntDivCycle(const CycleInfoT &CI, CycleRef Cycle,
1026 const BlockT *DivTermBlock, const BlockT *JoinBlock,
1027 const DominatorTreeT &DT, ContextT &Context) {
1028 LLVM_DEBUG(dbgs() << "examine join " << Context.print(JoinBlock)
1029 << " for internal branch " << Context.print(DivTermBlock)
1030 << "\n");
1031 if (DT.properlyDominates(DivTermBlock, JoinBlock))
1032 return CycleRef();
1033
1034 // Find the smallest common cycle, if one exists.
1035 assert(Cycle && CI.contains(Cycle, JoinBlock));
1036 while (Cycle && !CI.contains(Cycle, DivTermBlock)) {
1037 Cycle = CI.getParentCycle(Cycle);
1038 }
1039 if (!Cycle || CI.isReducible(Cycle))
1040 return CycleRef();
1041
1042 if (DT.properlyDominates(CI.getHeader(Cycle), JoinBlock))
1043 return CycleRef();
1044
1045 LLVM_DEBUG(dbgs() << " header " << Context.print(CI.getHeader(Cycle))
1046 << " does not dominate join\n");
1047
1048 CycleRef Parent = CI.getParentCycle(Cycle);
1049 while (Parent && !DT.properlyDominates(CI.getHeader(Parent), JoinBlock)) {
1050 LLVM_DEBUG(dbgs() << " header " << Context.print(CI.getHeader(Parent))
1051 << " does not dominate join\n");
1052 Cycle = Parent;
1053 Parent = CI.getParentCycle(Parent);
1054 }
1055
1056 LLVM_DEBUG(dbgs() << " cycle made divergent by internal branch\n");
1057 return Cycle;
1058}
1059
1060template <typename ContextT, typename CycleInfoT, typename BlockT,
1061 typename DominatorTreeT>
1062CycleRef
1063getOutermostDivergentCycle(const CycleInfoT &CI, CycleRef Cycle,
1064 const BlockT *DivTermBlock, const BlockT *JoinBlock,
1065 const DominatorTreeT &DT, ContextT &Context) {
1066 if (!Cycle)
1067 return CycleRef();
1068
1069 // First try to expand Cycle to the largest that contains JoinBlock
1070 // but not DivTermBlock.
1071 CycleRef Ext = getExtDivCycle(CI, Cycle, DivTermBlock, JoinBlock);
1072
1073 // Continue expanding to the largest cycle that contains both.
1074 CycleRef Int =
1075 getIntDivCycle(CI, Cycle, DivTermBlock, JoinBlock, DT, Context);
1076
1077 if (Int)
1078 return Int;
1079 return Ext;
1080}
1081
1082template <typename ContextT>
1083bool GenericUniformityAnalysisImpl<ContextT>::isTemporalDivergent(
1084 const BlockT &ObservingBlock, const InstructionT &Def) const {
1085 const BlockT *DefBlock = Def.getParent();
1086 for (auto C = CI.getCycle(DefBlock); C && !CI.contains(C, &ObservingBlock);
1087 C = CI.getParentCycle(C)) {
1088 if (DivergentExitCycles.contains(C)) {
1089 return true;
1090 }
1091 }
1092 return false;
1093}
1094
1095template <typename ContextT>
1097 const InstructionT &Term) {
1098 const auto *DivTermBlock = Term.getParent();
1099 DivergentTermBlocks.insert(DivTermBlock);
1100 LLVM_DEBUG(dbgs() << "analyzeControlDiv " << Context.print(DivTermBlock)
1101 << "\n");
1102
1103 // Don't propagate divergence from unreachable blocks.
1104 if (!DT.isReachableFromEntry(DivTermBlock))
1105 return;
1106
1107 const auto &DivDesc = SDA.getJoinBlocks(DivTermBlock);
1108 SmallVector<CycleRef> DivCycles;
1109
1110 // Iterate over all blocks now reachable by a disjoint path join
1111 for (const auto *JoinBlock : DivDesc.JoinDivBlocks) {
1112 CycleRef C = CI.getCycle(JoinBlock);
1113 LLVM_DEBUG(dbgs() << "visiting join block " << Context.print(JoinBlock)
1114 << "\n");
1115 if (CycleRef Outermost = getOutermostDivergentCycle(
1116 CI, C, DivTermBlock, JoinBlock, DT, Context)) {
1117 LLVM_DEBUG(dbgs() << "found divergent cycle\n");
1118 DivCycles.push_back(Outermost);
1119 continue;
1120 }
1121 taintAndPushPhiNodes(*JoinBlock);
1122 }
1123
1124 // Sort by order of decreasing depth. This allows later cycles to be skipped
1125 // because they are already contained in earlier ones.
1126 llvm::sort(DivCycles, [this](CycleRef A, CycleRef B) {
1127 return CI.getDepth(A) > CI.getDepth(B);
1128 });
1129
1130 // Cycles that are assumed divergent due to the diverged entry
1131 // criterion potentially contain temporal divergence depending on
1132 // the DFS chosen. Conservatively, all values produced in such a
1133 // cycle are assumed divergent. "Cycle invariant" values may be
1134 // assumed uniform, but that requires further analysis.
1135 for (auto C : DivCycles) {
1136 if (!insertIfNotContained(CI, AssumedDivergent, C))
1137 continue;
1138 LLVM_DEBUG(dbgs() << "process divergent cycle\n");
1139 for (const BlockT *BB : CI.getBlocks(C)) {
1140 taintAndPushAllDefs(*BB);
1141 }
1142 }
1143
1144 CycleRef BranchCycle = CI.getCycle(DivTermBlock);
1145 assert(DivDesc.CycleDivBlocks.empty() || BranchCycle);
1146 for (const auto *DivExitBlock : DivDesc.CycleDivBlocks) {
1147 propagateCycleExitDivergence(*DivExitBlock, BranchCycle);
1148 }
1149}
1150
1151template <typename ContextT>
1153 HasBranchDivergence = true;
1154
1155 // All values on the Worklist are divergent.
1156 // Their users may not have been updated yet.
1157 while (!Worklist.empty()) {
1158 const InstructionT *I = Worklist.back();
1159 Worklist.pop_back();
1160
1161 LLVM_DEBUG(dbgs() << "worklist pop: " << Context.print(I) << "\n");
1162
1163 if (I->isTerminator()) {
1165 continue;
1166 }
1167
1168 // propagate value divergence to users
1169 assert(hasDivergentDefs(*I) && "Worklist invariant violated!");
1170 pushUsers(*I);
1171 }
1172}
1173
1174template <typename ContextT>
1179
1180template <typename ContextT>
1182 const InstructionT &Instr) const {
1183 return UniformOverrides.contains(&Instr);
1184}
1185
1186template <typename ContextT>
1191
1192template <typename ContextT>
1194 const DominatorTreeT &DT, const CycleInfoT &CI,
1195 const TargetTransformInfo *TTI) {
1196 DA.reset(new ImplT{DT, CI, TTI});
1197}
1198
1199template <typename ContextT>
1201 // When we print Value, LLVM IR instruction, we want to print extra new line.
1202 // In LLVM IR print function for Value does not print new line at the end.
1203 // In MIR print for MachineInstr prints new line at the end.
1204 constexpr bool IsMIR = std::is_same<InstructionT, MachineInstr>::value;
1205 std::string NewLine = IsMIR ? "" : "\n";
1206
1207 bool FoundDivergence = false;
1208
1209 FoundDivergence |= printDivergentArgs(OS);
1210
1211 if (!AssumedDivergent.empty()) {
1212 FoundDivergence = true;
1213 OS << "CYCLES ASSUMED DIVERGENT:\n";
1214 for (auto C : AssumedDivergent) {
1215 OS << " " << CI.print(C) << '\n';
1216 }
1217 }
1218
1219 if (!DivergentExitCycles.empty()) {
1220 FoundDivergence = true;
1221 OS << "CYCLES WITH DIVERGENT EXIT:\n";
1222 for (auto C : DivergentExitCycles) {
1223 OS << " " << CI.print(C) << '\n';
1224 }
1225 }
1226
1227 if (!TemporalDivergenceList.empty()) {
1228 FoundDivergence = true;
1229 OS << "\nTEMPORAL DIVERGENCE LIST:\n";
1230
1231 for (auto [Val, UseInst, C] : TemporalDivergenceList) {
1232 OS << "Value :" << Context.print(Val) << NewLine
1233 << "Used by :" << Context.print(UseInst) << NewLine
1234 << "Outside cycle :" << CI.print(C) << "\n\n";
1235 }
1236 }
1237
1238 for (auto &Block : F) {
1239 OS << "\nBLOCK " << Context.print(&Block) << '\n';
1240
1241 OS << "DEFINITIONS\n";
1243 Context.appendBlockDefs(Defs, Block);
1244 for (auto Value : Defs) {
1245 if (isDivergent(Value)) {
1246 FoundDivergence = true;
1247 OS << " DIVERGENT: ";
1248 } else {
1249 OS << " ";
1250 }
1251 OS << Context.print(Value) << NewLine;
1252 }
1253
1254 OS << "TERMINATORS\n";
1256 Context.appendBlockTerms(Terms, Block);
1257 bool DivergentTerminators = hasDivergentTerminator(Block);
1258 if (DivergentTerminators)
1259 FoundDivergence = true;
1260 for (auto *T : Terms) {
1261 if (DivergentTerminators)
1262 OS << " DIVERGENT: ";
1263 else
1264 OS << " ";
1265 OS << Context.print(T) << NewLine;
1266 }
1267
1268 OS << "END BLOCK\n";
1269 }
1270
1271 if (!FoundDivergence)
1272 OS << "ALL VALUES UNIFORM\n";
1273}
1274
1275template <typename ContextT>
1279 return make_range(DA->TemporalDivergenceList.begin(),
1280 DA->TemporalDivergenceList.end());
1281}
1282
1283template <typename ContextT>
1284const typename ContextT::FunctionT &
1286 return DA->getFunction();
1287}
1288
1289template <typename ContextT>
1292 return DA->getCycleInfo();
1293}
1294
1295/// Whether \p V is divergent at its definition.
1296/// A default-constructed instance (no analysis computed) reports everything
1297/// as uniform, which is conservatively correct for non-divergent targets.
1298template <typename ContextT>
1300 return DA && DA->isDivergent(V);
1301}
1302
1303template <typename ContextT>
1305 const InstructionT *I) const {
1306 assert(I->isTerminator() && "Expected a terminator instruction!");
1307 return DA && DA->isDivergentTerminator(*I);
1308}
1309
1310template <typename ContextT>
1312 return DA && DA->isDivergentUse(U);
1313}
1314
1315template <typename ContextT>
1317 return DA && DA->hasDivergentTerminator(B);
1318}
1319
1320/// \brief T helper function for printing.
1321template <typename ContextT>
1323 if (!DA) {
1324 Out << " Uniformity analysis not computed (no branch divergence).\n";
1325 return;
1326 }
1327 DA->print(Out);
1328}
1329
1330template <typename ContextT>
1331void llvm::ModifiedPostOrder<ContextT>::computeStackPO(
1332 SmallVectorImpl<const BlockT *> &Stack, const CycleInfoT &CI, CycleRef C,
1334 LLVM_DEBUG(dbgs() << "inside computeStackPO\n");
1335 while (!Stack.empty()) {
1336 auto *NextBB = Stack.back();
1337 if (Finalized.count(NextBB)) {
1338 Stack.pop_back();
1339 continue;
1340 }
1341 LLVM_DEBUG(dbgs() << " visiting " << CI.getSSAContext().print(NextBB)
1342 << "\n");
1343 CycleRef NestedCycle = CI.getCycle(NextBB);
1344 if (C != NestedCycle &&
1345 (!C || (NestedCycle && CI.contains(C, NestedCycle)))) {
1346 LLVM_DEBUG(dbgs() << " found a cycle\n");
1347 while (CI.getParentCycle(NestedCycle) != C)
1348 NestedCycle = CI.getParentCycle(NestedCycle);
1349
1350 SmallVector<BlockT *, 3> NestedExits;
1351 CI.getExitBlocks(NestedCycle, NestedExits);
1352 bool PushedNodes = false;
1353 for (auto *NestedExitBB : NestedExits) {
1354 LLVM_DEBUG(dbgs() << " examine exit: "
1355 << CI.getSSAContext().print(NestedExitBB) << "\n");
1356 if (C && !CI.contains(C, NestedExitBB))
1357 continue;
1358 if (Finalized.count(NestedExitBB))
1359 continue;
1360 PushedNodes = true;
1361 Stack.push_back(NestedExitBB);
1362 LLVM_DEBUG(dbgs() << " pushed exit: "
1363 << CI.getSSAContext().print(NestedExitBB) << "\n");
1364 }
1365 if (!PushedNodes) {
1366 // All loop exits finalized -> finish this node
1367 Stack.pop_back();
1368 computeCyclePO(CI, NestedCycle, Finalized);
1369 }
1370 continue;
1371 }
1372
1373 LLVM_DEBUG(dbgs() << " no nested cycle, going into DAG\n");
1374 // DAG-style
1375 bool PushedNodes = false;
1376 for (auto *SuccBB : successors(NextBB)) {
1377 LLVM_DEBUG(dbgs() << " examine succ: "
1378 << CI.getSSAContext().print(SuccBB) << "\n");
1379 if (C && !CI.contains(C, SuccBB))
1380 continue;
1381 if (Finalized.count(SuccBB))
1382 continue;
1383 PushedNodes = true;
1384 Stack.push_back(SuccBB);
1385 LLVM_DEBUG(dbgs() << " pushed succ: " << CI.getSSAContext().print(SuccBB)
1386 << "\n");
1387 }
1388 if (!PushedNodes) {
1389 // Never push nodes twice
1390 LLVM_DEBUG(dbgs() << " finishing node: "
1391 << CI.getSSAContext().print(NextBB) << "\n");
1392 Stack.pop_back();
1393 Finalized.insert(NextBB);
1394 appendBlock(*NextBB);
1395 }
1396 }
1397 LLVM_DEBUG(dbgs() << "exited computeStackPO\n");
1398}
1399
1400template <typename ContextT>
1401void ModifiedPostOrder<ContextT>::computeCyclePO(
1402 const CycleInfoT &CI, CycleRef C,
1404 LLVM_DEBUG(dbgs() << "inside computeCyclePO\n");
1406 auto *CycleHeader = CI.getHeader(C);
1407
1408 LLVM_DEBUG(dbgs() << " noted header: "
1409 << CI.getSSAContext().print(CycleHeader) << "\n");
1410 assert(!Finalized.count(CycleHeader));
1411 Finalized.insert(CycleHeader);
1412
1413 // Visit the header last
1414 LLVM_DEBUG(dbgs() << " finishing header: "
1415 << CI.getSSAContext().print(CycleHeader) << "\n");
1416 appendBlock(*CycleHeader, CI.isReducible(C));
1417
1418 // Initialize with immediate successors
1419 for (auto *BB : successors(CycleHeader)) {
1420 LLVM_DEBUG(dbgs() << " examine succ: " << CI.getSSAContext().print(BB)
1421 << "\n");
1422 if (!CI.contains(C, BB))
1423 continue;
1424 if (BB == CycleHeader)
1425 continue;
1426 if (!Finalized.count(BB)) {
1427 LLVM_DEBUG(dbgs() << " pushed succ: " << CI.getSSAContext().print(BB)
1428 << "\n");
1429 Stack.push_back(BB);
1430 }
1431 }
1432
1433 // Compute PO inside region
1434 computeStackPO(Stack, CI, C, Finalized);
1435
1436 LLVM_DEBUG(dbgs() << "exited computeCyclePO\n");
1437}
1438
1439/// \brief Generically compute the modified post order.
1440template <typename ContextT>
1444 auto *F = CI.getFunction();
1445 POIndex.assign(GraphTraits<const FunctionT *>::getMaxNumber(F), InvalidIndex);
1446 Stack.reserve(24); // FIXME made-up number
1447 Stack.push_back(&F->front());
1448 computeStackPO(Stack, CI, CycleRef(), Finalized);
1449}
1450
1451} // namespace llvm
1452
1453#undef DEBUG_TYPE
1454
1455#endif // LLVM_ADT_GENERICUNIFORMITYIMPL_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
aarch64 promote const
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseSet and SmallDenseSet classes.
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
#define T
uint64_t IntrinsicInst * II
#define P(N)
This file contains some templates that are useful if you are working with the STL at all.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SparseBitVector class.
This file contains some functions that are useful when dealing with strings.
#define LLVM_DEBUG(...)
Definition Debug.h:119
static const unsigned InvalidIndex
static Function * getFunction(FunctionType *Ty, const Twine &Name, Module *M)
Opaque handle to a cycle within a GenericCycleInfo that wraps the cycle's preorder index.
Implements a dense probed hash-table based set.
Definition DenseSet.h:281
Compute divergence starting with a divergent branch.
GenericSyncDependenceAnalysis< ContextT > SyncDependenceAnalysisT
const BlockT *& label(const BlockT *BB)
typename ContextT::DominatorTreeT DominatorTreeT
bool computeJoin(const BlockT &SuccBlock, const BlockT &PushedLabel)
std::unique_ptr< DivergenceDescriptorT > DivDesc
void printDefs(raw_ostream &Out)
typename ContextT::FunctionT FunctionT
GenericCycleInfo< ContextT > CycleInfoT
SmallVector< const BlockT * > BlockLabels
ModifiedPostOrder< ContextT > ModifiedPO
std::unique_ptr< DivergenceDescriptorT > computeJoinPoints()
bool visitCycleExitEdge(const BlockT &ExitBlock, const BlockT &Label)
typename ContextT::ValueRefT ValueRefT
typename ContextT::BlockT BlockT
DivergencePropagator(const ModifiedPO &CyclePOT, const DominatorTreeT &DT, const CycleInfoT &CI, const BlockT &DivTermBlock)
bool visitEdge(const BlockT &SuccBlock, const BlockT &Label)
typename SyncDependenceAnalysisT::DivergenceDescriptor DivergenceDescriptorT
Cycle information for a function.
Locate join blocks for disjoint paths starting at a divergent branch.
GenericSyncDependenceAnalysis(const ContextT &Context, const DominatorTreeT &DT, const CycleInfoT &CI)
ModifiedPostOrder< ContextT > ModifiedPO
DivergencePropagator< ContextT > DivergencePropagatorT
SmallPtrSet< const BlockT *, 4 > ConstBlockSet
typename ContextT::DominatorTreeT DominatorTreeT
GenericCycleInfo< ContextT > CycleInfoT
typename ContextT::FunctionT FunctionT
typename ContextT::InstructionT InstructionT
typename ContextT::ValueRefT ValueRefT
const DivergenceDescriptor & getJoinBlocks(const BlockT *DivTermBlock)
Computes divergent join points and cycle exits caused by branch divergence in Term.
SmallVector< TemporalDivergenceTuple, 8 > TemporalDivergenceList
bool isAlwaysUniform(const InstructionT &Instr) const
Whether Val will always return a uniform value regardless of its operands.
bool isCustomUniform(const InstructionT &I) const
Check if an instruction with Custom uniformity can be proven uniform based on its operands.
typename ContextT::ValueRefT ValueRefT
void analyzeControlDivergence(const InstructionT &Term)
Mark Term as divergent and push all Instructions that become divergent as a result on the worklist.
void addCustomUniformityCandidate(const InstructionT *I)
Add an instruction that requires custom uniformity analysis.
bool isDivergent(ConstValueRefT V) const
Whether Val is divergent at its definition.
void recordTemporalDivergence(ConstValueRefT, const InstructionT *, CycleRef)
bool isDivergentUse(const UseT &U) const
bool hasDivergentDefs(const InstructionT &I) const
SmallPtrSet< const InstructionT *, 8 > CustomUniformityCandidates
typename ContextT::InstructionT InstructionT
bool printDivergentArgs(raw_ostream &Out) const
Print divergent arguments and return true if any were found.
typename ContextT::ConstValueRefT ConstValueRefT
typename ContextT::DominatorTreeT DominatorTreeT
void compute()
Propagate divergence to all instructions in the region.
bool hasDivergentTerminator(const BlockT &B) const
GenericUniformityAnalysisImpl(const DominatorTreeT &DT, const CycleInfoT &CI, const TargetTransformInfo *TTI)
bool markDefsDivergent(const InstructionT &Instr)
Mark outputs of Instr as divergent.
typename ContextT::FunctionT FunctionT
std::vector< const InstructionT * > Worklist
void markDivergent(const InstructionT &I)
Examine I for divergent outputs and add to the worklist.
SmallPtrSet< const BlockT *, 32 > DivergentTermBlocks
bool isDivergentTerminator(const InstructionT &I) const
GenericCycleInfo< ContextT > CycleInfoT
void addUniformOverride(const InstructionT &Instr)
Mark UniVal as a value that is always uniform.
std::tuple< ConstValueRefT, InstructionT *, CycleRef > TemporalDivergenceTuple
typename SyncDependenceAnalysisT::DivergenceDescriptor DivergenceDescriptorT
GenericSyncDependenceAnalysis< ContextT > SyncDependenceAnalysisT
bool hasDivergentTerminator(const BlockT &B)
void print(raw_ostream &Out) const
T helper function for printing.
bool isDivergentAtDef(ConstValueRefT V) const
Whether V is divergent at its definition.
std::tuple< ConstValueRefT, InstructionT *, CycleRef > TemporalDivergenceTuple
typename ContextT::ConstValueRefT ConstValueRefT
typename ContextT::BlockT BlockT
bool isDivergentAtUse(const UseT &U) const
Whether U is divergent at its use.
const CycleInfoT & getCycleInfo() const
The cycle info this analysis was computed with.
typename ContextT::InstructionT InstructionT
const FunctionT & getFunction() const
The GPU kernel this analysis result is for.
bool isDivergentTerminator(const InstructionT *I) const
GenericCycleInfo< ContextT > CycleInfoT
typename ContextT::DominatorTreeT DominatorTreeT
iterator_range< TemporalDivergenceTuple * > getTemporalDivergenceList() const
A helper class to return the specified delimiter string after the first invocation of operator String...
Construct a specially modified post-order traversal of cycles.
typename ContextT::FunctionT FunctionT
bool isReducibleCycleHeader(const BlockT *BB) const
void appendBlock(const BlockT &BB, bool IsReducibleCycleHeader=false)
const BlockT * operator[](size_t Idx) const
ModifiedPostOrder(const ContextT &C)
unsigned count(BlockT *BB) const
void compute(const CycleInfoT &CI)
Generically compute the modified post order.
GenericCycleInfo< ContextT > CycleInfoT
unsigned getIndex(const BlockT *BB) const
typename std::vector< BlockT * >::const_iterator const_iterator
typename ContextT::DominatorTreeT DominatorTreeT
typename ContextT::BlockT BlockT
Simple wrapper around std::function<void(raw_ostream&)>.
Definition Printable.h:38
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:339
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM Value Representation.
Definition Value.h:75
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
@ C
The default llvm calling convention, compatible with C.
Definition CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
bool insertIfNotContained(const CycleInfoT &CI, SmallVector< CycleRef > &Cycles, CycleRef Candidate)
Add Candidate to Cycles if it is not already contained in Cycles.
CycleRef getExtDivCycle(const CycleInfoT &CI, CycleRef Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock)
Return the outermost cycle made divergent by branch outside it.
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1746
CycleRef getOutermostDivergentCycle(const CycleInfoT &CI, CycleRef Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock, const DominatorTreeT &DT, ContextT &Context)
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1636
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
auto succ_size(const MachineBasicBlock *BB)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
TargetTransformInfo TTI
auto instrs(const MachineBasicBlock &BB)
CycleRef getIntDivCycle(const CycleInfoT &CI, CycleRef Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock, const DominatorTreeT &DT, ContextT &Context)
Return the outermost cycle made divergent by branch inside it.
Information discovered by the sync dependence analysis for each divergent branch.