LLVM 24.0.0git
SuspendCrossingInfo.h
Go to the documentation of this file.
1//===- SuspendCrossingInfo.cpp - Utility for suspend crossing values ------===//
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// The SuspendCrossingInfo maintains data that allows to answer a question
9// whether given two BasicBlocks A and B there is a path from A to B that
10// passes through a suspend point. Note, SuspendCrossingInfo is invalidated
11// by changes to the block numbering.
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_TRANSFORMS_COROUTINES_SUSPENDCROSSINGINFO_H
15#define LLVM_TRANSFORMS_COROUTINES_SUSPENDCROSSINGINFO_H
16
17#include "llvm/ADT/BitVector.h"
20#include "llvm/IR/BasicBlock.h"
21#include "llvm/IR/Function.h"
22#include "llvm/IR/Instruction.h"
26
27namespace llvm {
28
30
31// The SuspendCrossingInfo maintains data that allows to answer a question
32// whether given two BasicBlocks A and B there is a path from A to B that
33// passes through a suspend point.
34//
35// For every basic block 'i' it maintains a BlockData that consists of:
36// Consumes: a bit vector which contains a set of indices of blocks that can
37// reach block 'i'. A block can trivially reach itself.
38// Kills: a bit vector which contains a set of indices of blocks that can
39// reach block 'i' but there is a path crossing a suspend point
40// not repeating 'i' (path to 'i' without cycles containing 'i').
41// AlwaysKill: a boolean indicating whether block 'i' always propagate kills.
42// NeverKill: a boolean indicating whether block 'i' never propagate kills.
43// KillLoop: There is a path from 'i' to 'i' not otherwise repeating 'i' that
44// crosses a suspend point.
45//
47 struct BlockData {
48 BitVector Consumes;
49 BitVector Kills;
50 bool KillLoop = false;
51 bool Changed = false;
52
53 private:
54 bool AlwaysKill = false;
55 bool NeverKill = false;
56
57 public:
58 bool isAlwaysKill() const { return AlwaysKill; }
59 bool isNeverKill() const { return NeverKill; }
60 void setAlwaysKill() {
61 AlwaysKill = true;
62 NeverKill = false;
63 }
64 void setNeverKill() {
65 AlwaysKill = false;
66 NeverKill = true;
67 }
68 };
69 [[maybe_unused]] Function *F;
71
72 /// Compute the BlockData for the current function in one iteration.
73 /// Initialize - Whether this is the first iteration, we can optimize
74 /// the initial case a little bit by manual loop switch.
75 /// Returns whether the BlockData changes in this iteration.
76 template <bool Initialize = false>
77 bool computeBlockData(const ReversePostOrderTraversal<Function *> &RPOT);
78
79public:
80#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
81 // Print order is in RPO
82 void dump() const;
83 void dump(StringRef Label, BitVector const &BV,
85 ModuleSlotTracker &MST) const;
86#endif
87
90
91 /// Returns true if there is a path from \p From to \p To crossing a suspend
92 /// point without crossing \p From a 2nd time.
94 BasicBlock *To) const;
95
96 /// Returns true if there is a path from \p From to \p To crossing a suspend
97 /// point without crossing \p From a 2nd time. If \p From is the same as \p To
98 /// this will also check if there is a looping path crossing a suspend point.
100 BasicBlock *To) const;
101
103 auto *I = cast<Instruction>(U);
104
105 // We rewrote PHINodes, so that only the ones with exactly one incoming
106 // value need to be analyzed.
107 if (auto *PN = dyn_cast<PHINode>(I))
108 if (PN->getNumIncomingValues() > 1)
109 return false;
110
111 BasicBlock *UseBB = I->getParent();
112
113 // As a special case, treat uses by an llvm.coro.suspend.retcon or an
114 // llvm.coro.suspend.async as if they were uses in the suspend's single
115 // predecessor: the uses conceptually occur before the suspend.
117 UseBB = UseBB->getSinglePredecessor();
118 assert(UseBB && "should have split coro.suspend into its own block");
119 }
120
121 return hasPathCrossingSuspendPoint(DefBB, UseBB);
122 }
123
125 return isDefinitionAcrossSuspend(&A.getParent()->getEntryBlock(), U);
126 }
127
129 auto *DefBB = I.getParent();
130
131 // As a special case, treat values produced by an llvm.coro.suspend.*
132 // as if they were defined in the single successor: the uses
133 // conceptually occur after the suspend.
135 DefBB = DefBB->getSingleSuccessor();
136 assert(DefBB && "should have split coro.suspend into its own block");
137 }
138
139 return isDefinitionAcrossSuspend(DefBB, U);
140 }
141
143 if (auto *Arg = dyn_cast<Argument>(&V))
144 return isDefinitionAcrossSuspend(*Arg, U);
145 if (auto *Inst = dyn_cast<Instruction>(&V))
146 return isDefinitionAcrossSuspend(*Inst, U);
147
149 "Coroutine could only collect Argument and Instruction now.");
150 }
151
153 if (auto *Arg = dyn_cast<Argument>(&V)) {
154 for (User *U : Arg->users())
155 if (isDefinitionAcrossSuspend(*Arg, U))
156 return true;
157 } else if (auto *Inst = dyn_cast<Instruction>(&V)) {
158 for (User *U : Inst->users())
159 if (isDefinitionAcrossSuspend(*Inst, U))
160 return true;
161 }
162
164 "Coroutine could only collect Argument and Instruction now.");
165 }
166};
167
168} // namespace llvm
169
170#endif // LLVM_TRANSFORMS_COROUTINES_SUSPENDCROSSINGINFO_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements the BitVector class.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_ABI
Definition Compiler.h:211
#define I(x, y, z)
Definition MD5.cpp:57
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file defines the SmallVector class.
This class represents an incoming formal argument to a Function.
Definition Argument.h:32
LLVM Basic Block Representation.
Definition BasicBlock.h:62
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Manage lifetime of a slot tracker for printing IR.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
bool isDefinitionAcrossSuspend(Value &V) const
bool isDefinitionAcrossSuspend(Value &V, User *U) const
bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const
LLVM_ABI bool hasPathCrossingSuspendPoint(BasicBlock *From, BasicBlock *To) const
Returns true if there is a path from From to To crossing a suspend point without crossing From a 2nd ...
bool isDefinitionAcrossSuspend(Instruction &I, User *U) const
LLVM_ABI bool hasPathOrLoopCrossingSuspendPoint(BasicBlock *From, BasicBlock *To) const
Returns true if there is a path from From to To crossing a suspend point without crossing From a 2nd ...
LLVM_ABI SuspendCrossingInfo(Function &F, const coro::Shape &Shape)
bool isDefinitionAcrossSuspend(Argument &A, User *U) const
LLVM Value Representation.
Definition Value.h:75
iterator_range< user_iterator > users()
Definition Value.h:428
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559