GenericConvergenceVerifierImpl.h Source File (original) (raw)

26#ifndef LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H

27#define LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H

34#define Check(C, ...) \

35 do { \

36 if (!(C)) { \

37 reportFailure(__VA_ARGS__); \

38 return; \

39 } \

40 } while (false)

42#define CheckOrNull(C, ...) \

43 do { \

44 if (!(C)) { \

45 reportFailure(__VA_ARGS__); \

46 return {}; \

47 } \

48 } while (false)

50namespace llvm {

52 Tokens.clear();

53 CI.clear();

54 ConvergenceKind = NoConvergence;

55}

57template

59 SeenFirstConvOp = false;

60}

62template

64 ConvOpKind ConvOp = getConvOp(I);

66 auto *TokenDef = findAndCheckConvergenceTokenUsed(I);

67 switch (ConvOp) {

68 case CONV_ENTRY:

69 Check(isInsideConvergentFunction(I),

70 "Entry intrinsic can occur only in a convergent function.",

71 {Context.print(&I)});

72 Check(I.getParent()->isEntryBlock(),

73 "Entry intrinsic can occur only in the entry block.",

74 {Context.print(&I)});

75 Check(!SeenFirstConvOp,

76 "Entry intrinsic cannot be preceded by a convergent operation in the "

77 "same basic block.",

78 {Context.print(&I)});

79 [[fallthrough]];

80 case CONV_ANCHOR:

82 "Entry or anchor intrinsic cannot have a convergencectrl token "

83 "operand.",

84 {Context.print(&I)});

85 break;

86 case CONV_LOOP:

87 Check(TokenDef, "Loop intrinsic must have a convergencectrl token operand.",

88 {Context.print(&I)});

89 Check(!SeenFirstConvOp,

90 "Loop intrinsic cannot be preceded by a convergent operation in the "

91 "same basic block.",

92 {Context.print(&I)});

93 break;

94 default:

95 break;

96 }

98 if (ConvOp != CONV_NONE)

99 checkConvergenceTokenProduced(I);

100

101 if (isConvergent(I))

102 SeenFirstConvOp = true;

103

104 if (TokenDef || ConvOp != CONV_NONE) {

105 Check(ConvergenceKind != UncontrolledConvergence,

106 "Cannot mix controlled and uncontrolled convergence in the same "

107 "function.",

108 {Context.print(&I)});

109 ConvergenceKind = ControlledConvergence;

110 } else if (isConvergent(I)) {

111 Check(ConvergenceKind != ControlledConvergence,

112 "Cannot mix controlled and uncontrolled convergence in the same "

113 "function.",

114 {Context.print(&I)});

115 ConvergenceKind = UncontrolledConvergence;

116 }

117}

118

119template

120void GenericConvergenceVerifier::reportFailure(

122 FailureCB(Message);

123 if (OS) {

124 for (auto V : DumpedValues)

125 *OS << V << '\n';

126 }

127}

128

129template

131 assert(Context.getFunction());

132 const auto &F = *Context.getFunction();

133

136

137

138

139

140 CI.compute(const_cast<FunctionT &>(F));

141

144 Check(DT.dominates(Token->getParent(), User->getParent()),

145 "Convergence control token must dominate all its uses.",

146 {Context.print(Token), Context.print(User)});

147

149 "Convergence region is not well-nested.",

150 {Context.print(Token), Context.print(User)});

151 while (LiveTokens.back() != Token)

152 LiveTokens.pop_back();

153

154

155 auto *BB = User->getParent();

156 auto *BBCycle = CI.getCycle(BB);

157 if (!BBCycle)

158 return;

159

160 auto *DefBB = Token->getParent();

161 if (DefBB == BB || BBCycle->contains(DefBB)) {

162

163 return;

164 }

165

166 Check(getConvOp(*User) == CONV_LOOP,

167 "Convergence token used by an instruction other than "

168 "llvm.experimental.convergence.loop in a cycle that does "

169 "not contain the token's definition.",

170 {Context.print(User), CI.print(BBCycle)});

171

172 while (true) {

173 auto *Parent = BBCycle->getParentCycle();

174 if (!Parent || Parent->contains(DefBB))

175 break;

176 BBCycle = Parent;

177 };

178

179 Check(BBCycle->isReducible() && BB == BBCycle->getHeader(),

180 "Cycle heart must dominate all blocks in the cycle.",

181 {Context.print(User), Context.printAsOperand(BB), CI.print(BBCycle)});

183 "Two static convergence token uses in a cycle that does "

184 "not contain either token's definition.",

185 {Context.print(User), Context.print(CycleHearts[BBCycle]),

186 CI.print(BBCycle)});

187 CycleHearts[BBCycle] = User;

188 };

189

192 for (auto *BB : RPOT) {

193 LiveTokens.clear();

194 auto LTIt = LiveTokenMap.find(BB);

195 if (LTIt != LiveTokenMap.end()) {

196 LiveTokens = std::move(LTIt->second);

197 LiveTokenMap.erase(LTIt);

198 }

199

200 for (auto &I : *BB) {

201 if (auto *Token = Tokens.lookup(&I))

202 checkToken(Token, &I, LiveTokens);

203 if (getConvOp(I) != CONV_NONE)

205 }

206

207

209 auto *SuccNode = DT.getNode(Succ);

210 auto [LTIt, Inserted] = LiveTokenMap.try_emplace(Succ);

211 if (Inserted) {

212

213

214 for (auto LiveToken : LiveTokens) {

215 if (!DT.dominates(DT.getNode(LiveToken->getParent()), SuccNode))

216 break;

217 LTIt->second.push_back(LiveToken);

218 }

219 } else {

220

222 LTIt->second, [&LiveTokens](const InstructionT *Token) {

223 return llvm::is_contained(LiveTokens, Token);

224 });

225 LTIt->second.erase(It, LTIt->second.end());

226 }

227 }

228 }

229}

230

231}

232

233#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

A verifier for the static rules of convergence control tokens that works with both LLVM IR and MIR.

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

iterator find(const_arg_type_t< KeyT > Val)

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

bool erase(const KeyT &Val)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

typename ContextT::InstructionT InstructionT

typename ContextT::DominatorTreeT DominatorTreeT

typename ContextT::BlockT BlockT

typename ContextT::FunctionT FunctionT

void verify(const DominatorTreeT &DT)

Definition GenericConvergenceVerifierImpl.h:130

void visit(const BlockT &BB)

Definition GenericConvergenceVerifierImpl.h:58

void clear()

Definition GenericConvergenceVerifierImpl.h:51

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.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

This is an optimization pass for GlobalISel generic memory operations.

auto successors(const MachineBasicBlock *BB)

auto partition(R &&Range, UnaryPredicate P)

Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.