1//===-- SPIRVStructurizer.cpp ----------------------*- 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//===----------------------------------------------------------------------===//
10
11#include "Analysis/SPIRVConvergenceRegionAnalysis.h"
12#include "SPIRV.h"
13#include "SPIRVStructurizerWrapper.h"
14#include "SPIRVSubtarget.h"
15#include "SPIRVUtils.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/Analysis/LoopInfo.h"
20#include "llvm/IR/CFG.h"
21#include "llvm/IR/Dominators.h"
22#include "llvm/IR/IRBuilder.h"
23#include "llvm/IR/IntrinsicInst.h"
24#include "llvm/IR/Intrinsics.h"
25#include "llvm/IR/IntrinsicsSPIRV.h"
26#include "llvm/InitializePasses.h"
27#include "llvm/Transforms/Utils.h"
28#include "llvm/Transforms/Utils/Cloning.h"
29#include "llvm/Transforms/Utils/LoopSimplify.h"
30#include "llvm/Transforms/Utils/LowerMemIntrinsics.h"
31#include <stack>
32
33using namespace llvm;
34using namespace SPIRV;
35
36using BlockSet = SmallPtrSet<BasicBlock *, 0>;
37using Edge = std::pair<BasicBlock *, BasicBlock *>;
38
39// Helper function to do a partial order visit from the block |Start|, calling
40// |Op| on each visited node.
41static void partialOrderVisit(BasicBlock &Start,
42 std::function<bool(BasicBlock *)> Op) {
43 PartialOrderingVisitor V(*Start.getParent());
44 V.partialOrderVisit(Start, Op: std::move(Op));
45}
46
47// Returns the exact convergence region in the tree defined by `Node` for which
48// `BB` is the header, nullptr otherwise.
49static const ConvergenceRegion *
50getRegionForHeader(const ConvergenceRegion *Node, BasicBlock *BB) {
51 if (Node->Entry == BB)
52 return Node;
53
54 for (auto *Child : Node->Children) {
55 const auto *CR = getRegionForHeader(Node: Child, BB);
56 if (CR != nullptr)
57 return CR;
58 }
59 return nullptr;
60}
61
62// Returns the single BasicBlock exiting the convergence region `CR`,
63// nullptr if no such exit exists.
64static BasicBlock *getExitFor(const ConvergenceRegion *CR) {
65 SmallPtrSet<BasicBlock *, 0> ExitTargets;
66 for (BasicBlock *Exit : CR->Exits) {
67 for (BasicBlock *Successor : successors(BB: Exit)) {
68 if (CR->Blocks.count(Ptr: Successor) == 0)
69 ExitTargets.insert(Ptr: Successor);
70 }
71 }
72
73 assert(ExitTargets.size() <= 1);
74 if (ExitTargets.size() == 0)
75 return nullptr;
76
77 return *ExitTargets.begin();
78}
79
80// Returns the merge block designated by I if I is a merge instruction, nullptr
81// otherwise.
82static BasicBlock *getDesignatedMergeBlock(Instruction *I) {
83 IntrinsicInst *II = dyn_cast_or_null<IntrinsicInst>(Val: I);
84 if (II == nullptr)
85 return nullptr;
86
87 if (II->getIntrinsicID() != Intrinsic::spv_loop_merge &&
88 II->getIntrinsicID() != Intrinsic::spv_selection_merge)
89 return nullptr;
90
91 BlockAddress *BA = cast<BlockAddress>(Val: II->getOperand(i_nocapture: 0));
92 return BA->getBasicBlock();
93}
94
95// Returns the continue block designated by I if I is an OpLoopMerge, nullptr
96// otherwise.
97static BasicBlock *getDesignatedContinueBlock(Instruction *I) {
98 IntrinsicInst *II = dyn_cast_or_null<IntrinsicInst>(Val: I);
99 if (II == nullptr)
100 return nullptr;
101
102 if (II->getIntrinsicID() != Intrinsic::spv_loop_merge)
103 return nullptr;
104
105 BlockAddress *BA = cast<BlockAddress>(Val: II->getOperand(i_nocapture: 1));
106 return BA->getBasicBlock();
107}
108
109// Returns true if Header has one merge instruction which designated Merge as
110// merge block.
111static bool isDefinedAsSelectionMergeBy(BasicBlock &Header, BasicBlock &Merge) {
112 for (auto &I : Header) {
113 BasicBlock *MB = getDesignatedMergeBlock(I: &I);
114 if (MB == &Merge)
115 return true;
116 }
117 return false;
118}
119
120// Returns true if the BB has one OpLoopMerge instruction.
121static bool hasLoopMergeInstruction(BasicBlock &BB) {
122 for (auto &I : BB)
123 if (getDesignatedContinueBlock(I: &I))
124 return true;
125 return false;
126}
127
128// Returns true is I is an OpSelectionMerge or OpLoopMerge instruction, false
129// otherwise.
130static bool isMergeInstruction(Instruction *I) {
131 return getDesignatedMergeBlock(I) != nullptr;
132}
133
134// Returns all blocks in F having at least one OpLoopMerge or OpSelectionMerge
135// instruction.
136static SmallPtrSet<BasicBlock *, 2> getHeaderBlocks(Function &F) {
137 SmallPtrSet<BasicBlock *, 2> Output;
138 for (BasicBlock &BB : F) {
139 for (Instruction &I : BB) {
140 if (getDesignatedMergeBlock(I: &I) != nullptr)
141 Output.insert(Ptr: &BB);
142 }
143 }
144 return Output;
145}
146
147// Returns all basic blocks in |F| referenced by at least 1
148// OpSelectionMerge/OpLoopMerge instruction.
149static SmallPtrSet<BasicBlock *, 2> getMergeBlocks(Function &F) {
150 SmallPtrSet<BasicBlock *, 2> Output;
151 for (BasicBlock &BB : F) {
152 for (Instruction &I : BB) {
153 BasicBlock *MB = getDesignatedMergeBlock(I: &I);
154 if (MB != nullptr)
155 Output.insert(Ptr: MB);
156 }
157 }
158 return Output;
159}
160
161// Return all the merge instructions contained in BB.
162// Note: the SPIR-V spec doesn't allow a single BB to contain more than 1 merge
163// instruction, but this can happen while we structurize the CFG.
164static std::vector<Instruction *> getMergeInstructions(BasicBlock &BB) {
165 std::vector<Instruction *> Output;
166 for (Instruction &I : BB)
167 if (isMergeInstruction(I: &I))
168 Output.push_back(x: &I);
169 return Output;
170}
171
172// Returns all basic blocks in |F| referenced as continue target by at least 1
173// OpLoopMerge instruction.
174static SmallPtrSet<BasicBlock *, 2> getContinueBlocks(Function &F) {
175 SmallPtrSet<BasicBlock *, 2> Output;
176 for (BasicBlock &BB : F) {
177 for (Instruction &I : BB) {
178 BasicBlock *MB = getDesignatedContinueBlock(I: &I);
179 if (MB != nullptr)
180 Output.insert(Ptr: MB);
181 }
182 }
183 return Output;
184}
185
186// Do a preorder traversal of the CFG starting from the BB |Start|.
187// point. Calls |op| on each basic block encountered during the traversal.
188static void visit(BasicBlock &Start, std::function<bool(BasicBlock *)> op) {
189 std::stack<BasicBlock *> ToVisit;
190 SmallPtrSet<BasicBlock *, 8> Seen;
191
192 ToVisit.push(x: &Start);
193 Seen.insert(Ptr: ToVisit.top());
194 while (ToVisit.size() != 0) {
195 BasicBlock *BB = ToVisit.top();
196 ToVisit.pop();
197
198 if (!op(BB))
199 continue;
200
201 for (auto Succ : successors(BB)) {
202 if (Seen.contains(Ptr: Succ))
203 continue;
204 ToVisit.push(x: Succ);
205 Seen.insert(Ptr: Succ);
206 }
207 }
208}
209
210// Replaces the conditional and unconditional branch targets of |BB| by
211// |NewTarget| if the target was |OldTarget|. This function also makes sure the
212// associated merge instruction gets updated accordingly.
213static void replaceIfBranchTargets(BasicBlock *BB, BasicBlock *OldTarget,
214 BasicBlock *NewTarget) {
215 auto *BI = cast<CondBrInst>(Val: BB->getTerminator());
216
217 // 1. Replace all matching successors.
218 for (size_t i = 0; i < BI->getNumSuccessors(); i++) {
219 if (BI->getSuccessor(i) == OldTarget)
220 BI->setSuccessor(idx: i, NewSucc: NewTarget);
221 }
222
223 // Branch had 2 successors, maybe now both are the same?
224 if (BI->getSuccessor(i: 0) != BI->getSuccessor(i: 1))
225 return;
226
227 // Note: we may end up here because the original IR had such branches.
228 // This means Target is not necessarily equal to NewTarget.
229 IRBuilder<> Builder(BB);
230 Builder.SetInsertPoint(BI);
231 Builder.CreateBr(Dest: BI->getSuccessor(i: 0));
232 BI->eraseFromParent();
233
234 // The branch was the only instruction, nothing else to do.
235 if (BB->size() == 1)
236 return;
237
238 // Otherwise, we need to check: was there an OpSelectionMerge before this
239 // branch? If we removed the OpBranchConditional, we must also remove the
240 // OpSelectionMerge. This is not valid for OpLoopMerge:
241 IntrinsicInst *II =
242 dyn_cast<IntrinsicInst>(Val: BB->getTerminator()->getPrevNode());
243 if (!II || II->getIntrinsicID() != Intrinsic::spv_selection_merge)
244 return;
245
246 Constant *C = cast<Constant>(Val: II->getOperand(i_nocapture: 0));
247 II->eraseFromParent();
248 if (!C->isConstantUsed())
249 C->destroyConstant();
250}
251
252// Replaces the target of branch instruction in |BB| with |NewTarget| if it
253// was |OldTarget|. This function also fixes the associated merge instruction.
254// Note: this function does not simplify branching instructions, it only updates
255// targets. See also: simplifyBranches.
256static void replaceBranchTargets(BasicBlock *BB, BasicBlock *OldTarget,
257 BasicBlock *NewTarget) {
258 auto *T = BB->getTerminator();
259 if (isa<ReturnInst>(Val: T))
260 return;
261 if (auto *BI = dyn_cast<UncondBrInst>(Val: T)) {
262 if (BI->getSuccessor() == OldTarget)
263 BI->setSuccessor(NewTarget);
264 return;
265 }
266
267 if (isa<CondBrInst>(Val: T))
268 return replaceIfBranchTargets(BB, OldTarget, NewTarget);
269
270 if (auto *SI = dyn_cast<SwitchInst>(Val: T)) {
271 for (size_t i = 0; i < SI->getNumSuccessors(); i++) {
272 if (SI->getSuccessor(idx: i) == OldTarget)
273 SI->setSuccessor(idx: i, NewSucc: NewTarget);
274 }
275 return;
276 }
277
278 assert(false && "Unhandled terminator type.");
279}
280
281namespace {
282// Given a reducible CFG, produces a structurized CFG in the SPIR-V sense,
283// adding merge instructions when required.
284class SPIRVStructurizerImpl {
285 LoopInfo &LI;
286 ConvergenceRegionInfo &RegionInfo;
287
288 struct DivergentConstruct;
289 // Represents a list of condition/loops/switch constructs.
290 // See SPIR-V 2.11.2. Structured Control-flow Constructs for the list of
291 // constructs.
292 using ConstructList = std::vector<std::unique_ptr<DivergentConstruct>>;
293
294 // Represents a divergent construct in the SPIR-V sense.
295 // Such constructs are represented by a header (entry), a merge block (exit),
296 // and possibly a continue block (back-edge). A construct can contain other
297 // constructs, but their boundaries do not cross.
298 struct DivergentConstruct {
299 BasicBlock *Header = nullptr;
300 BasicBlock *Merge = nullptr;
301 BasicBlock *Continue = nullptr;
302
303 DivergentConstruct *Parent = nullptr;
304 ConstructList Children;
305 };
306
307 // An helper class to clean the construct boundaries.
308 // It is used to gather the list of blocks that should belong to each
309 // divergent construct, and possibly modify CFG edges when exits would cross
310 // the boundary of multiple constructs.
311 struct Splitter {
312 Function &F;
313 LoopInfo &LI;
314 DomTreeBuilder::BBDomTree DT;
315 DomTreeBuilder::BBPostDomTree PDT;
316
317 Splitter(Function &F, LoopInfo &LI) : F(F), LI(LI) { invalidate(); }
318
319 void invalidate() {
320 PDT.recalculate(Func&: F);
321 DT.recalculate(Func&: F);
322 }
323
324 // Returns the list of blocks that belong to a SPIR-V loop construct,
325 // including the continue construct.
326 std::vector<BasicBlock *> getLoopConstructBlocks(BasicBlock *Header,
327 BasicBlock *Merge) {
328 assert(DT.dominates(Header, Merge));
329 std::vector<BasicBlock *> Output;
330 partialOrderVisit(Start&: *Header, Op: [&](BasicBlock *BB) {
331 if (BB == Merge)
332 return false;
333 if (DT.dominates(A: Merge, B: BB) || !DT.dominates(A: Header, B: BB))
334 return false;
335 Output.push_back(x: BB);
336 return true;
337 });
338 return Output;
339 }
340
341 // Returns the list of blocks that belong to a SPIR-V selection construct.
342 std::vector<BasicBlock *>
343 getSelectionConstructBlocks(DivergentConstruct *Node) {
344 assert(DT.dominates(Node->Header, Node->Merge));
345 BlockSet OutsideBlocks;
346 OutsideBlocks.insert(Ptr: Node->Merge);
347
348 for (DivergentConstruct *It = Node->Parent; It != nullptr;
349 It = It->Parent) {
350 OutsideBlocks.insert(Ptr: It->Merge);
351 if (It->Continue)
352 OutsideBlocks.insert(Ptr: It->Continue);
353 }
354
355 std::vector<BasicBlock *> Output;
356 partialOrderVisit(Start&: *Node->Header, Op: [&](BasicBlock *BB) {
357 if (OutsideBlocks.count(Ptr: BB) != 0)
358 return false;
359 if (DT.dominates(A: Node->Merge, B: BB) || !DT.dominates(A: Node->Header, B: BB))
360 return false;
361 Output.push_back(x: BB);
362 return true;
363 });
364 return Output;
365 }
366
367 // Returns the list of blocks that belong to a SPIR-V switch construct.
368 std::vector<BasicBlock *> getSwitchConstructBlocks(BasicBlock *Header,
369 BasicBlock *Merge) {
370 assert(DT.dominates(Header, Merge));
371
372 std::vector<BasicBlock *> Output;
373 partialOrderVisit(Start&: *Header, Op: [&](BasicBlock *BB) {
374 // the blocks structurally dominated by a switch header,
375 if (!DT.dominates(A: Header, B: BB))
376 return false;
377 // excluding blocks structurally dominated by the switch header’s merge
378 // block.
379 if (DT.dominates(A: Merge, B: BB) || BB == Merge)
380 return false;
381 Output.push_back(x: BB);
382 return true;
383 });
384 return Output;
385 }
386
387 // Returns the list of blocks that belong to a SPIR-V case construct.
388 std::vector<BasicBlock *> getCaseConstructBlocks(BasicBlock *Target,
389 BasicBlock *Merge) {
390 assert(DT.dominates(Target, Merge));
391
392 std::vector<BasicBlock *> Output;
393 partialOrderVisit(Start&: *Target, Op: [&](BasicBlock *BB) {
394 // the blocks structurally dominated by an OpSwitch Target or Default
395 // block
396 if (!DT.dominates(A: Target, B: BB))
397 return false;
398 // excluding the blocks structurally dominated by the OpSwitch
399 // construct’s corresponding merge block.
400 if (DT.dominates(A: Merge, B: BB) || BB == Merge)
401 return false;
402 Output.push_back(x: BB);
403 return true;
404 });
405 return Output;
406 }
407
408 // Splits the given edges by recreating proxy nodes so that the destination
409 // has unique incoming edges from this region.
410 //
411 // clang-format off
412 //
413 // In SPIR-V, constructs must have a single exit/merge.
414 // Given nodes A and B in the construct, a node C outside, and the following edges.
415 // A -> C
416 // B -> C
417 //
418 // In such cases, we must create a new exit node D, that belong to the construct to make is viable:
419 // A -> D -> C
420 // B -> D -> C
421 //
422 // This is fine (assuming C has no PHI nodes), but requires handling the merge instruction here.
423 // By adding a proxy node, we create a regular divergent shape which can easily be regularized later on.
424 // A -> D -> D1 -> C
425 // B -> D -> D2 -> C
426 //
427 // A, B, D belongs to the construct. D is the exit. D1 and D2 are empty.
428 //
429 // clang-format on
430 std::vector<Edge>
431 createAliasBlocksForComplexEdges(std::vector<Edge> Edges) {
432 SmallPtrSet<BasicBlock *, 0> Seen;
433 std::vector<Edge> Output;
434 Output.reserve(n: Edges.size());
435
436 for (auto &[Src, Dst] : Edges) {
437 auto [Iterator, Inserted] = Seen.insert(Ptr: Src);
438 if (!Inserted) {
439 // Src already a source node. Cannot have 2 edges from A to B.
440 // Creating alias source block.
441 BasicBlock *NewSrc = BasicBlock::Create(
442 Context&: F.getContext(), Name: Src->getName() + ".new.src", Parent: &F);
443 replaceBranchTargets(BB: Src, OldTarget: Dst, NewTarget: NewSrc);
444 IRBuilder<> Builder(NewSrc);
445 Builder.CreateBr(Dest: Dst);
446 Src = NewSrc;
447 }
448
449 Output.emplace_back(args&: Src, args&: Dst);
450 }
451
452 return Output;
453 }
454
455 // Given a construct defined by |Header|, and a list of exiting edges
456 // |Edges|, creates a new single exit node, fixing up those edges.
457 BasicBlock *createSingleExitNode(BasicBlock *Header,
458 std::vector<Edge> &Edges) {
459
460 std::vector<Edge> FixedEdges = createAliasBlocksForComplexEdges(Edges);
461
462 std::vector<BasicBlock *> Dsts;
463 DenseMap<BasicBlock *, ConstantInt *> DstToIndex;
464 auto NewExit = BasicBlock::Create(Context&: F.getContext(),
465 Name: Header->getName() + ".new.exit", Parent: &F);
466 IRBuilder<> ExitBuilder(NewExit);
467 for (auto &[Src, Dst] : FixedEdges) {
468 if (DstToIndex.count(Val: Dst) != 0)
469 continue;
470 DstToIndex.try_emplace(Key: Dst, Args: ExitBuilder.getInt32(C: DstToIndex.size()));
471 Dsts.push_back(x: Dst);
472 }
473
474 if (Dsts.size() == 1) {
475 for (auto &[Src, Dst] : FixedEdges) {
476 replaceBranchTargets(BB: Src, OldTarget: Dst, NewTarget: NewExit);
477 }
478 ExitBuilder.CreateBr(Dest: Dsts[0]);
479 return NewExit;
480 }
481
482 AllocaInst *Variable = createVariable(F, Type: ExitBuilder.getInt32Ty());
483 for (auto &[Src, Dst] : FixedEdges) {
484 IRBuilder<> B2(Src);
485 B2.SetInsertPoint(Src->getFirstInsertionPt());
486 B2.CreateStore(Val: DstToIndex[Dst], Ptr: Variable);
487 replaceBranchTargets(BB: Src, OldTarget: Dst, NewTarget: NewExit);
488 }
489
490 Value *Load = ExitBuilder.CreateLoad(Ty: ExitBuilder.getInt32Ty(), Ptr: Variable);
491
492 // If we can avoid an OpSwitch, generate an OpBranch. Reason is some
493 // OpBranch are allowed to exist without a new OpSelectionMerge if one of
494 // the branch is the parent's merge node, while OpSwitches are not.
495 if (Dsts.size() == 2) {
496 Value *Condition =
497 ExitBuilder.CreateCmp(Pred: CmpInst::ICMP_EQ, LHS: DstToIndex[Dsts[0]], RHS: Load);
498 ExitBuilder.CreateCondBr(Cond: Condition, True: Dsts[0], False: Dsts[1]);
499 return NewExit;
500 }
501
502 SwitchInst *Sw = ExitBuilder.CreateSwitch(V: Load, Dest: Dsts[0], NumCases: Dsts.size() - 1);
503 for (BasicBlock *BB : drop_begin(RangeOrContainer&: Dsts))
504 Sw->addCase(OnVal: DstToIndex[BB], Dest: BB);
505 return NewExit;
506 }
507 };
508
509 // Creates a new basic block in F with a single OpUnreachable instruction.
510 BasicBlock *CreateUnreachable(Function &F) {
511 BasicBlock *BB = BasicBlock::Create(Context&: F.getContext(), Name: "unreachable", Parent: &F);
512 IRBuilder<> Builder(BB);
513 Builder.CreateUnreachable();
514 return BB;
515 }
516
517 // Add OpLoopMerge instruction on cycles.
518 bool addMergeForLoops(Function &F) {
519 auto *TopLevelRegion = RegionInfo.getTopLevelRegion();
520
521 bool Modified = false;
522 for (auto &BB : F) {
523 // Not a loop header. Ignoring for now.
524 if (!LI.isLoopHeader(BB: &BB))
525 continue;
526 auto *L = LI.getLoopFor(BB: &BB);
527
528 // This loop header is not the entrance of a convergence region. Ignoring
529 // this block.
530 auto *CR = getRegionForHeader(Node: TopLevelRegion, BB: &BB);
531 if (CR == nullptr)
532 continue;
533
534 IRBuilder<> Builder(&BB);
535
536 auto *Merge = getExitFor(CR);
537 // We are indeed in a loop, but there are no exits (infinite loop).
538 // This could be caused by a bad shader, but also could be an artifact
539 // from an earlier optimization. It is not always clear if structurally
540 // reachable means runtime reachable, so we cannot error-out. What we must
541 // do however is to make is legal on the SPIR-V point of view, hence
542 // adding an unreachable merge block.
543 if (Merge == nullptr) {
544 UncondBrInst *Br = cast<UncondBrInst>(Val: BB.getTerminator());
545 Merge = CreateUnreachable(F);
546 Builder.SetInsertPoint(Br);
547 Builder.CreateCondBr(Cond: Builder.getFalse(), True: Merge, False: Br->getSuccessor(i: 0));
548 Br->eraseFromParent();
549 }
550
551 auto *Continue = L->getLoopLatch();
552
553 Builder.SetInsertPoint(BB.getTerminator());
554 auto MergeAddress = BlockAddress::get(F: Merge->getParent(), BB: Merge);
555 auto ContinueAddress = BlockAddress::get(F: Continue->getParent(), BB: Continue);
556 SmallVector<Value *, 2> Args = {MergeAddress, ContinueAddress};
557 SmallVector<unsigned, 1> LoopControlImms =
558 getSpirvLoopControlOperandsFromLoopMetadata(L);
559 for (unsigned Imm : LoopControlImms)
560 Args.emplace_back(Args: ConstantInt::get(Ty: Builder.getInt32Ty(), V: Imm));
561 Builder.CreateIntrinsic(ID: Intrinsic::spv_loop_merge, Args: {Args});
562 Modified = true;
563 }
564
565 return Modified;
566 }
567
568 // Adds an OpSelectionMerge to the immediate dominator or each node with an
569 // in-degree of 2 or more which is not already the merge target of an
570 // OpLoopMerge/OpSelectionMerge.
571 bool addMergeForNodesWithMultiplePredecessors(Function &F) {
572 DomTreeBuilder::BBDomTree DT;
573 DT.recalculate(Func&: F);
574
575 bool Modified = false;
576 for (auto &BB : F) {
577 if (pred_size(BB: &BB) <= 1)
578 continue;
579
580 if (hasLoopMergeInstruction(BB) && pred_size(BB: &BB) <= 2)
581 continue;
582
583 assert(DT.getNode(&BB)->getIDom());
584 BasicBlock *Header = DT.getNode(BB: &BB)->getIDom()->getBlock();
585
586 if (isDefinedAsSelectionMergeBy(Header&: *Header, Merge&: BB))
587 continue;
588
589 IRBuilder<> Builder(Header);
590 Builder.SetInsertPoint(Header->getTerminator());
591
592 auto MergeAddress = BlockAddress::get(F: BB.getParent(), BB: &BB);
593 createOpSelectMerge(Builder: &Builder, MergeAddress);
594
595 Modified = true;
596 }
597
598 return Modified;
599 }
600
601 // When a block has multiple OpSelectionMerge/OpLoopMerge instructions, sorts
602 // them to put the "largest" first. A merge instruction is defined as larger
603 // than another when its target merge block post-dominates the other target's
604 // merge block. (This ordering should match the nesting ordering of the source
605 // HLSL).
606 bool sortSelectionMerge(Function &F, BasicBlock &Block) {
607 std::vector<Instruction *> MergeInstructions;
608 for (Instruction &I : Block)
609 if (isMergeInstruction(I: &I))
610 MergeInstructions.push_back(x: &I);
611
612 if (MergeInstructions.size() <= 1)
613 return false;
614
615 Instruction *InsertionPoint = *MergeInstructions.begin();
616
617 PartialOrderingVisitor Visitor(F);
618 llvm::sort(C&: MergeInstructions,
619 Comp: [&Visitor](Instruction *Left, Instruction *Right) {
620 if (Left == Right)
621 return false;
622 BasicBlock *RightMerge = getDesignatedMergeBlock(I: Right);
623 BasicBlock *LeftMerge = getDesignatedMergeBlock(I: Left);
624 return !Visitor.compare(LHS: RightMerge, RHS: LeftMerge);
625 });
626
627 for (Instruction *I : MergeInstructions) {
628 I->moveBefore(InsertPos: InsertionPoint->getIterator());
629 InsertionPoint = I;
630 }
631
632 return true;
633 }
634
635 // Sorts selection merge headers in |F|.
636 // A is sorted before B if the merge block designated by B is an ancestor of
637 // the one designated by A.
638 bool sortSelectionMergeHeaders(Function &F) {
639 bool Modified = false;
640 for (BasicBlock &BB : F) {
641 Modified |= sortSelectionMerge(F, Block&: BB);
642 }
643 return Modified;
644 }
645
646 // Split basic blocks containing multiple OpLoopMerge/OpSelectionMerge
647 // instructions so each basic block contains only a single merge instruction.
648 bool splitBlocksWithMultipleHeaders(Function &F) {
649 std::stack<BasicBlock *> Work;
650 for (auto &BB : F) {
651 std::vector<Instruction *> MergeInstructions = getMergeInstructions(BB);
652 if (MergeInstructions.size() <= 1)
653 continue;
654 Work.push(x: &BB);
655 }
656
657 const bool Modified = Work.size() > 0;
658 while (Work.size() > 0) {
659 BasicBlock *Header = Work.top();
660 Work.pop();
661
662 std::vector<Instruction *> MergeInstructions =
663 getMergeInstructions(BB&: *Header);
664 for (unsigned i = 1; i < MergeInstructions.size(); i++) {
665 BasicBlock *NewBlock =
666 Header->splitBasicBlock(I: MergeInstructions[i], BBName: "new.header");
667
668 if (getDesignatedContinueBlock(I: MergeInstructions[0]) == nullptr) {
669 BasicBlock *Unreachable = CreateUnreachable(F);
670
671 Instruction *Term = Header->getTerminator();
672 IRBuilder<> Builder(Header);
673 Builder.SetInsertPoint(Term);
674 Builder.CreateCondBr(Cond: Builder.getTrue(), True: NewBlock, False: Unreachable);
675 Term->eraseFromParent();
676 }
677
678 Header = NewBlock;
679 }
680 }
681
682 return Modified;
683 }
684
685 // Adds an OpSelectionMerge to each block with an out-degree >= 2 which
686 // doesn't already have an OpSelectionMerge.
687 bool addMergeForDivergentBlocks(Function &F) {
688 DomTreeBuilder::BBPostDomTree PDT;
689 PDT.recalculate(Func&: F);
690 bool Modified = false;
691
692 auto MergeBlocks = getMergeBlocks(F);
693 auto ContinueBlocks = getContinueBlocks(F);
694
695 for (auto &BB : F) {
696 if (getMergeInstructions(BB).size() != 0)
697 continue;
698
699 std::vector<BasicBlock *> Candidates;
700 for (BasicBlock *Successor : successors(BB: &BB)) {
701 if (MergeBlocks.contains(Ptr: Successor))
702 continue;
703 if (ContinueBlocks.contains(Ptr: Successor))
704 continue;
705 Candidates.push_back(x: Successor);
706 }
707
708 if (Candidates.size() <= 1)
709 continue;
710
711 Modified = true;
712 BasicBlock *Merge = Candidates[0];
713
714 auto MergeAddress = BlockAddress::get(F: Merge->getParent(), BB: Merge);
715 IRBuilder<> Builder(&BB);
716 Builder.SetInsertPoint(BB.getTerminator());
717 createOpSelectMerge(Builder: &Builder, MergeAddress);
718 }
719
720 return Modified;
721 }
722
723 // Gather all the exit nodes for the construct header by |Header| and
724 // containing the blocks |Construct|.
725 std::vector<Edge> getExitsFrom(const BlockSet &Construct,
726 BasicBlock &Header) {
727 std::vector<Edge> Output;
728 visit(Start&: Header, op: [&](BasicBlock *Item) {
729 if (Construct.count(Ptr: Item) == 0)
730 return false;
731
732 for (BasicBlock *Successor : successors(BB: Item)) {
733 if (Construct.count(Ptr: Successor) == 0)
734 Output.emplace_back(args&: Item, args&: Successor);
735 }
736 return true;
737 });
738
739 return Output;
740 }
741
742 // Build a divergent construct tree searching from |BB|.
743 // If |Parent| is not null, this tree is attached to the parent's tree.
744 void constructDivergentConstruct(BlockSet &Visited, Splitter &S,
745 BasicBlock *BB, DivergentConstruct *Parent) {
746 if (Visited.count(Ptr: BB) != 0)
747 return;
748 Visited.insert(Ptr: BB);
749
750 auto MIS = getMergeInstructions(BB&: *BB);
751 if (MIS.size() == 0) {
752 for (BasicBlock *Successor : successors(BB))
753 constructDivergentConstruct(Visited, S, BB: Successor, Parent);
754 return;
755 }
756
757 assert(MIS.size() == 1);
758 Instruction *MI = MIS[0];
759
760 BasicBlock *Merge = getDesignatedMergeBlock(I: MI);
761 BasicBlock *Continue = getDesignatedContinueBlock(I: MI);
762
763 auto Output = std::make_unique<DivergentConstruct>();
764 Output->Header = BB;
765 Output->Merge = Merge;
766 Output->Continue = Continue;
767 Output->Parent = Parent;
768
769 constructDivergentConstruct(Visited, S, BB: Merge, Parent);
770 if (Continue)
771 constructDivergentConstruct(Visited, S, BB: Continue, Parent: Output.get());
772
773 for (BasicBlock *Successor : successors(BB))
774 constructDivergentConstruct(Visited, S, BB: Successor, Parent: Output.get());
775
776 if (Parent)
777 Parent->Children.emplace_back(args: std::move(Output));
778 }
779
780 // Returns the blocks belonging to the divergent construct |Node|.
781 BlockSet getConstructBlocks(Splitter &S, DivergentConstruct *Node) {
782 assert(Node->Header && Node->Merge);
783
784 if (Node->Continue) {
785 auto LoopBlocks = S.getLoopConstructBlocks(Header: Node->Header, Merge: Node->Merge);
786 return BlockSet(LoopBlocks.begin(), LoopBlocks.end());
787 }
788
789 auto SelectionBlocks = S.getSelectionConstructBlocks(Node);
790 return BlockSet(SelectionBlocks.begin(), SelectionBlocks.end());
791 }
792
793 // Fixup the construct |Node| to respect a set of rules defined by the SPIR-V
794 // spec.
795 bool fixupConstruct(Splitter &S, DivergentConstruct *Node) {
796 bool Modified = false;
797 for (auto &Child : Node->Children)
798 Modified |= fixupConstruct(S, Node: Child.get());
799
800 // This construct is the root construct. Does not represent any real
801 // construct, just a way to access the first level of the forest.
802 if (Node->Parent == nullptr)
803 return Modified;
804
805 // This node's parent is the root. Meaning this is a top-level construct.
806 // There can be multiple exists, but all are guaranteed to exit at most 1
807 // construct since we are at first level.
808 if (Node->Parent->Header == nullptr)
809 return Modified;
810
811 // Health check for the structure.
812 assert(Node->Header && Node->Merge);
813 assert(Node->Parent->Header && Node->Parent->Merge);
814
815 BlockSet ConstructBlocks = getConstructBlocks(S, Node);
816 auto Edges = getExitsFrom(Construct: ConstructBlocks, Header&: *Node->Header);
817
818 // No edges exiting the construct.
819 if (Edges.size() < 1)
820 return Modified;
821
822 bool HasBadEdge = Node->Merge == Node->Parent->Merge ||
823 Node->Merge == Node->Parent->Continue;
824 // BasicBlock *Target = Edges[0].second;
825 for (auto &[Src, Dst] : Edges) {
826 // - Breaking from a selection construct: S is a selection construct, S is
827 // the innermost structured
828 // control-flow construct containing A, and B is the merge block for S
829 // - Breaking from the innermost loop: S is the innermost loop construct
830 // containing A,
831 // and B is the merge block for S
832 if (Node->Merge == Dst)
833 continue;
834
835 // Entering the innermost loop’s continue construct: S is the innermost
836 // loop construct containing A, and B is the continue target for S
837 if (Node->Continue == Dst)
838 continue;
839
840 // TODO: what about cases branching to another case in the switch? Seems
841 // to work, but need to double check.
842 HasBadEdge = true;
843 }
844
845 if (!HasBadEdge)
846 return Modified;
847
848 // Create a single exit node gathering all exit edges.
849 BasicBlock *NewExit = S.createSingleExitNode(Header: Node->Header, Edges);
850
851 // Fixup this construct's merge node to point to the new exit.
852 // Note: this algorithm fixes inner-most divergence construct first. So
853 // recursive structures sharing a single merge node are fixed from the
854 // inside toward the outside.
855 auto MergeInstructions = getMergeInstructions(BB&: *Node->Header);
856 assert(MergeInstructions.size() == 1);
857 Instruction *I = MergeInstructions[0];
858 BlockAddress *BA = cast<BlockAddress>(Val: I->getOperand(i: 0));
859 if (BA->getBasicBlock() == Node->Merge) {
860 auto MergeAddress = BlockAddress::get(F: NewExit->getParent(), BB: NewExit);
861 I->setOperand(i: 0, Val: MergeAddress);
862 }
863
864 // Clean up of the possible dangling BockAddr operands to prevent MIR
865 // comments about "address of removed block taken".
866 if (!BA->isConstantUsed())
867 BA->destroyConstant();
868
869 Node->Merge = NewExit;
870 // Regenerate the dom trees.
871 S.invalidate();
872 return true;
873 }
874
875 bool splitCriticalEdges(Function &F) {
876 Splitter S(F, LI);
877
878 DivergentConstruct Root;
879 BlockSet Visited;
880 constructDivergentConstruct(Visited, S, BB: &*F.begin(), Parent: &Root);
881 return fixupConstruct(S, Node: &Root);
882 }
883
884 // Simplify branches when possible:
885 // - if the 2 sides of a conditional branch are the same, transforms it to an
886 // unconditional branch.
887 // - if a switch has only 2 distinct successors, converts it to a conditional
888 // branch.
889 bool simplifyBranches(Function &F) {
890 bool Modified = false;
891
892 for (BasicBlock &BB : F) {
893 SwitchInst *SI = dyn_cast<SwitchInst>(Val: BB.getTerminator());
894 if (!SI)
895 continue;
896 if (SI->getNumCases() > 1)
897 continue;
898
899 Modified = true;
900 IRBuilder<> Builder(&BB);
901 Builder.SetInsertPoint(SI);
902
903 if (SI->getNumCases() == 0) {
904 Builder.CreateBr(Dest: SI->getDefaultDest());
905 } else {
906 Value *Condition =
907 Builder.CreateCmp(Pred: CmpInst::ICMP_EQ, LHS: SI->getCondition(),
908 RHS: SI->case_begin()->getCaseValue());
909 Builder.CreateCondBr(Cond: Condition, True: SI->case_begin()->getCaseSuccessor(),
910 False: SI->getDefaultDest());
911 }
912 SI->eraseFromParent();
913 }
914
915 return Modified;
916 }
917
918 // Makes sure every case target in |F| is unique. If 2 cases branch to the
919 // same basic block, one of the targets is updated so it jumps to a new basic
920 // block ending with a single unconditional branch to the original target.
921 bool splitSwitchCases(Function &F) {
922 bool Modified = false;
923
924 for (BasicBlock &BB : F) {
925 SwitchInst *SI = dyn_cast<SwitchInst>(Val: BB.getTerminator());
926 if (!SI)
927 continue;
928
929 BlockSet Seen;
930 Seen.insert(Ptr: SI->getDefaultDest());
931
932 auto It = SI->case_begin();
933 while (It != SI->case_end()) {
934 BasicBlock *Target = It->getCaseSuccessor();
935 if (Seen.count(Ptr: Target) == 0) {
936 Seen.insert(Ptr: Target);
937 ++It;
938 continue;
939 }
940
941 Modified = true;
942 BasicBlock *NewTarget =
943 BasicBlock::Create(Context&: F.getContext(), Name: "new.sw.case", Parent: &F);
944 IRBuilder<> Builder(NewTarget);
945 Builder.CreateBr(Dest: Target);
946 SI->addCase(OnVal: It->getCaseValue(), Dest: NewTarget);
947 It = SI->removeCase(I: It);
948 }
949 }
950
951 return Modified;
952 }
953
954 // Removes blocks not contributing to any structured CFG. This assumes there
955 // is no PHI nodes.
956 bool removeUselessBlocks(Function &F) {
957 std::vector<BasicBlock *> ToRemove;
958
959 auto MergeBlocks = getMergeBlocks(F);
960 auto ContinueBlocks = getContinueBlocks(F);
961
962 for (BasicBlock &BB : F) {
963 if (BB.size() != 1)
964 continue;
965
966 if (isa<ReturnInst>(Val: BB.getTerminator()))
967 continue;
968
969 if (MergeBlocks.count(Ptr: &BB) != 0 || ContinueBlocks.count(Ptr: &BB) != 0)
970 continue;
971
972 if (BB.getUniqueSuccessor() == nullptr)
973 continue;
974
975 BasicBlock *Successor = BB.getUniqueSuccessor();
976 std::vector<BasicBlock *> Predecessors(predecessors(BB: &BB).begin(),
977 predecessors(BB: &BB).end());
978 for (BasicBlock *Predecessor : Predecessors)
979 replaceBranchTargets(BB: Predecessor, OldTarget: &BB, NewTarget: Successor);
980 ToRemove.push_back(x: &BB);
981 }
982
983 for (BasicBlock *BB : ToRemove)
984 BB->eraseFromParent();
985
986 return ToRemove.size() != 0;
987 }
988
989 bool addHeaderToRemainingDivergentDAG(Function &F) {
990 bool Modified = false;
991
992 auto MergeBlocks = getMergeBlocks(F);
993 auto ContinueBlocks = getContinueBlocks(F);
994 auto HeaderBlocks = getHeaderBlocks(F);
995
996 DomTreeBuilder::BBDomTree DT;
997 DomTreeBuilder::BBPostDomTree PDT;
998 PDT.recalculate(Func&: F);
999 DT.recalculate(Func&: F);
1000
1001 for (BasicBlock &BB : F) {
1002 if (HeaderBlocks.count(Ptr: &BB) != 0)
1003 continue;
1004 if (succ_size(BB: &BB) < 2)
1005 continue;
1006
1007 size_t CandidateEdges = 0;
1008 for (BasicBlock *Successor : successors(BB: &BB)) {
1009 if (MergeBlocks.count(Ptr: Successor) != 0 ||
1010 ContinueBlocks.count(Ptr: Successor) != 0)
1011 continue;
1012 if (HeaderBlocks.count(Ptr: Successor) != 0)
1013 continue;
1014 CandidateEdges += 1;
1015 }
1016
1017 if (CandidateEdges <= 1)
1018 continue;
1019
1020 BasicBlock *Header = &BB;
1021 BasicBlock *Merge = PDT.getNode(BB: &BB)->getIDom()->getBlock();
1022
1023 bool HasBadBlock = false;
1024 visit(Start&: *Header, op: [&](const BasicBlock *Node) {
1025 if (DT.dominates(A: Header, B: Node))
1026 return false;
1027 if (PDT.dominates(A: Merge, B: Node))
1028 return false;
1029 if (Node == Header || Node == Merge)
1030 return true;
1031
1032 HasBadBlock |= MergeBlocks.count(Ptr: Node) != 0 ||
1033 ContinueBlocks.count(Ptr: Node) != 0 ||
1034 HeaderBlocks.count(Ptr: Node) != 0;
1035 return !HasBadBlock;
1036 });
1037
1038 if (HasBadBlock)
1039 continue;
1040
1041 Modified = true;
1042
1043 if (Merge == nullptr) {
1044 Merge = *successors(BB: Header).begin();
1045 IRBuilder<> Builder(Header);
1046 Builder.SetInsertPoint(Header->getTerminator());
1047
1048 auto MergeAddress = BlockAddress::get(F: Merge->getParent(), BB: Merge);
1049 createOpSelectMerge(Builder: &Builder, MergeAddress);
1050 continue;
1051 }
1052
1053 Instruction *SplitInstruction = Merge->getTerminator();
1054 if (isMergeInstruction(I: SplitInstruction->getPrevNode()))
1055 SplitInstruction = SplitInstruction->getPrevNode();
1056 BasicBlock *NewMerge =
1057 Merge->splitBasicBlockBefore(I: SplitInstruction, BBName: "new.merge");
1058
1059 IRBuilder<> Builder(Header);
1060 Builder.SetInsertPoint(Header->getTerminator());
1061
1062 auto MergeAddress = BlockAddress::get(F: NewMerge->getParent(), BB: NewMerge);
1063 createOpSelectMerge(Builder: &Builder, MergeAddress);
1064 }
1065
1066 return Modified;
1067 }
1068
1069public:
1070 SPIRVStructurizerImpl(LoopInfo &LI, ConvergenceRegionInfo &RegionInfo)
1071 : LI(LI), RegionInfo(RegionInfo) {}
1072
1073 bool run(Function &F) {
1074 bool Modified = false;
1075
1076 // In LLVM, Switches are allowed to have several cases branching to the same
1077 // basic block. This is allowed in SPIR-V, but can make structurizing SPIR-V
1078 // harder, so first remove edge cases.
1079 Modified |= splitSwitchCases(F);
1080
1081 // LLVM allows conditional branches to have both side jumping to the same
1082 // block. It also allows switched to have a single default, or just one
1083 // case. Cleaning this up now.
1084 Modified |= simplifyBranches(F);
1085
1086 // At this state, we should have a reducible CFG with cycles.
1087 // STEP 1: Adding OpLoopMerge instructions to loop headers.
1088 Modified |= addMergeForLoops(F);
1089
1090 // STEP 2: adding OpSelectionMerge to each node with an in-degree >= 2.
1091 Modified |= addMergeForNodesWithMultiplePredecessors(F);
1092
1093 // STEP 3:
1094 // Sort selection merge, the largest construct goes first.
1095 // This simplifies the next step.
1096 Modified |= sortSelectionMergeHeaders(F);
1097
1098 // STEP 4: As this stage, we can have a single basic block with multiple
1099 // OpLoopMerge/OpSelectionMerge instructions. Splitting this block so each
1100 // BB has a single merge instruction.
1101 Modified |= splitBlocksWithMultipleHeaders(F);
1102
1103 // STEP 5: In the previous steps, we added merge blocks the loops and
1104 // natural merge blocks (in-degree >= 2). What remains are conditions with
1105 // an exiting branch (return, unreachable). In such case, we must start from
1106 // the header, and add headers to divergent construct with no headers.
1107 Modified |= addMergeForDivergentBlocks(F);
1108
1109 // STEP 6: At this stage, we have several divergent construct defines by a
1110 // header and a merge block. But their boundaries have no constraints: a
1111 // construct exit could be outside of the parents' construct exit. Such
1112 // edges are called critical edges. What we need is to split those edges
1113 // into several parts. Each part exiting the parent's construct by its merge
1114 // block.
1115 Modified |= splitCriticalEdges(F);
1116
1117 // STEP 7: The previous steps possibly created a lot of "proxy" blocks.
1118 // Blocks with a single unconditional branch, used to create a valid
1119 // divergent construct tree. Some nodes are still requires (e.g: nodes
1120 // allowing a valid exit through the parent's merge block). But some are
1121 // left-overs of past transformations, and could cause actual validation
1122 // issues. E.g: the SPIR-V spec allows a construct to break to the parents
1123 // loop construct without an OpSelectionMerge, but this requires a straight
1124 // jump. If a proxy block lies between the conditional branch and the
1125 // parent's merge, the CFG is not valid.
1126 Modified |= removeUselessBlocks(F);
1127
1128 // STEP 8: Final fix-up steps: our tree boundaries are correct, but some
1129 // blocks are branching with no header. Those are often simple conditional
1130 // branches with 1 or 2 returning edges. Adding a header for those.
1131 Modified |= addHeaderToRemainingDivergentDAG(F);
1132
1133 // STEP 9: sort basic blocks to match both the LLVM & SPIR-V requirements.
1134 Modified |= sortBlocks(F);
1135
1136 return Modified;
1137 }
1138
1139 void createOpSelectMerge(IRBuilder<> *Builder, BlockAddress *MergeAddress) {
1140 Instruction *BBTerminatorInst = Builder->GetInsertBlock()->getTerminator();
1141
1142 MDNode *MDNode = BBTerminatorInst->getMetadata(Kind: "hlsl.controlflow.hint");
1143
1144 ConstantInt *BranchHint = ConstantInt::get(Ty: Builder->getInt32Ty(), V: 0);
1145
1146 if (MDNode) {
1147 assert(MDNode->getNumOperands() == 2 &&
1148 "invalid metadata hlsl.controlflow.hint");
1149 BranchHint = mdconst::extract<ConstantInt>(MD: MDNode->getOperand(I: 1));
1150 }
1151
1152 SmallVector<Value *, 2> Args = {MergeAddress, BranchHint};
1153
1154 Builder->CreateIntrinsic(ID: Intrinsic::spv_selection_merge,
1155 OverloadTypes: {MergeAddress->getType()}, Args);
1156 }
1157};
1158
1159class SPIRVStructurizer : public FunctionPass {
1160public:
1161 static char ID;
1162
1163 SPIRVStructurizer() : FunctionPass(ID) {}
1164
1165 bool runOnFunction(Function &F) override {
1166 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1167 ConvergenceRegionInfo &RegionInfo =
1168 getAnalysis<SPIRVConvergenceRegionAnalysisWrapperPass>()
1169 .getRegionInfo();
1170 return SPIRVStructurizerImpl(LI, RegionInfo).run(F);
1171 }
1172
1173 void getAnalysisUsage(AnalysisUsage &AU) const override {
1174 AU.addRequired<DominatorTreeWrapperPass>();
1175 AU.addRequired<LoopInfoWrapperPass>();
1176 AU.addRequired<SPIRVConvergenceRegionAnalysisWrapperPass>();
1177
1178 AU.addPreserved<SPIRVConvergenceRegionAnalysisWrapperPass>();
1179 FunctionPass::getAnalysisUsage(AU);
1180 }
1181};
1182} // anonymous namespace
1183
1184char SPIRVStructurizer::ID = 0;
1185
1186INITIALIZE_PASS_BEGIN(SPIRVStructurizer, "spirv-structurizer",
1187 "structurize SPIRV", false, false)
1188INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1189INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1190INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1191INITIALIZE_PASS_DEPENDENCY(SPIRVConvergenceRegionAnalysisWrapperPass)
1192
1193INITIALIZE_PASS_END(SPIRVStructurizer, "spirv-structurizer",
1194 "structurize SPIRV", false, false)
1195
1196FunctionPass *llvm::createSPIRVStructurizerPass() {
1197 return new SPIRVStructurizer();
1198}
1199
1200PreservedAnalyses SPIRVStructurizerWrapper::run(Function &F,
1201 FunctionAnalysisManager &AM) {
1202 LoopInfo &LI = AM.getResult<LoopAnalysis>(IR&: F);
1203 ConvergenceRegionInfo &RegionInfo =
1204 AM.getResult<SPIRVConvergenceRegionAnalysis>(IR&: F);
1205 return SPIRVStructurizerImpl(LI, RegionInfo).run(F)
1206 ? PreservedAnalyses::none()
1207 : PreservedAnalyses::all();
1208}
1209