1 /*========================== begin_copyright_notice ============================
2
3 Copyright (C) 2017-2021 Intel Corporation
4
5 SPDX-License-Identifier: MIT
6
7 ============================= end_copyright_notice ===========================*/
8
9 //
10 // Utility functions relating to SIMD CF goto/join.
11 //
12 //===----------------------------------------------------------------------===//
13 #include "GenXGotoJoin.h"
14 #include "GenX.h"
15 #include "llvm/IR/Dominators.h"
16 #include "llvm/IR/Function.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/Intrinsics.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "Probe/Assertion.h"
21
22 using namespace llvm;
23 using namespace genx;
24
25 /***********************************************************************
26 * isEMValue : detect whether a value is an EM (execution mask)
27 *
28 * It is an EM value if it is an extractvalue instruction extracting element
29 * 0 from the struct returned by goto/join.
30 */
isEMValue(Value * V)31 bool GotoJoin::isEMValue(Value *V)
32 {
33 if (auto EI = dyn_cast<ExtractValueInst>(V)) {
34 if (EI->getIndices()[0] == 0/* element number of EM in goto/join struct */) {
35 switch (GenXIntrinsic::getGenXIntrinsicID(EI->getAggregateOperand())) {
36 case GenXIntrinsic::genx_simdcf_goto:
37 case GenXIntrinsic::genx_simdcf_join:
38 return true;
39 default:
40 break;
41 }
42 }
43 }
44 return false;
45 }
46
47 /***********************************************************************
48 * findJoin : given a goto, find the join whose RM it modifies
49 *
50 * Return: the join instruction, 0 if join not found
51 */
findJoin(CallInst * Goto)52 CallInst *GotoJoin::findJoin(CallInst *Goto)
53 {
54 // Find the RM value from the goto. We know that the only
55 // uses of the goto are extracts.
56 ExtractValueInst *RM = nullptr;
57 for (auto ui = Goto->use_begin(), ue = Goto->use_end(); ui != ue; ++ui) {
58 auto Extract = dyn_cast<ExtractValueInst>(ui->getUser());
59 if (Extract && Extract->getIndices()[0] == 1/* RM index in struct */) {
60 RM = Extract;
61 break;
62 }
63 }
64 if (!RM)
65 return nullptr;
66 // Find the single use of the RM in a join, possibly via phi nodes and
67 // other goto instructions.
68 CallInst *Join = nullptr;
69 SetVector<Instruction *> RMVals;
70 RMVals.insert(RM);
71 for (unsigned ri = 0; !Join && ri != RMVals.size(); ++ri) {
72 auto RM = RMVals[ri];
73 for (auto ui = RM->use_begin(), ue = RM->use_end();
74 !Join && ui != ue; ++ui) {
75 auto User = cast<Instruction>(ui->getUser());
76 if (isa<PHINode>(User))
77 RMVals.insert(User);
78 else switch (GenXIntrinsic::getGenXIntrinsicID(User)) {
79 case GenXIntrinsic::genx_simdcf_join:
80 // We have found the join the RM is for.
81 Join = cast<CallInst>(User);
82 break;
83 case GenXIntrinsic::genx_simdcf_goto: {
84 // This is another goto that modifies the same RM. Find the
85 // extractvalue for the updated RM value.
86 ExtractValueInst *Extract = nullptr;
87 for (auto gui = User->use_begin(), gue = User->use_end();
88 gui != gue; ++gui) {
89 auto ThisExtract = dyn_cast<ExtractValueInst>(gui->getUser());
90 if (ThisExtract
91 && ThisExtract->getIndices()[0] == 1/*RM index in struct*/) {
92 Extract = ThisExtract;
93 break;
94 }
95 }
96 if (Extract)
97 RMVals.insert(Extract);
98 break;
99 }
100 default:
101 return nullptr; // unexpected use of RM
102 }
103 }
104 }
105 return Join;
106 }
107
108 /***********************************************************************
109 * isValidJoin : check that a join is valid
110 *
111 * In a block that is a join label (the "true" successor of a goto/join), there
112 * must be a join at the start of the block, ignoring phi nodes and bitcasts
113 * (which generate no code).
114 *
115 */
isValidJoin(CallInst * Join)116 bool GotoJoin::isValidJoin(CallInst *Join)
117 {
118 IGC_ASSERT(GenXIntrinsic::getGenXIntrinsicID(Join) == GenXIntrinsic::genx_simdcf_join);
119 auto BB = Join->getParent();
120 // If this block has a goto/join predecessor of which it is "true" successor,
121 // check that this block starts with a join -- not necessarily the join we
122 // were given.
123 if (!isJoinLabel(BB))
124 return true;
125 auto Inst = BB->getFirstNonPHIOrDbg();
126 while (isa<BitCastInst>(Inst))
127 Inst = Inst->getNextNode();
128 if (GenXIntrinsic::getGenXIntrinsicID(Inst) == GenXIntrinsic::genx_simdcf_join)
129 return true;
130 return false;
131 }
132
133 /***********************************************************************
134 * isBranchingJoinLabelBlock : check whether a block has a single join and
135 * is both a join label and a branching join
136 *
137 * This only works after GenXLateSimdCFConformance.
138 *
139 * For a block for which this returns true, a pass must not insert code.
140 */
isBranchingJoinLabelBlock(BasicBlock * BB)141 bool GotoJoin::isBranchingJoinLabelBlock(BasicBlock *BB)
142 {
143 auto Join = isBranchingJoinBlock(BB);
144 if (!Join || Join != BB->getFirstNonPHIOrDbg())
145 return false;
146 return isJoinLabel(BB);
147 }
148
149 /***********************************************************************
150 * getBranchingBlockForBB : if this block is "true" successor of branching
151 * goto/join then return this branching block. Otherwise return nullptr.
152 *
153 * Enter: BB = the basic block
154 * SkipCriticalEdgeSplitter = if true, skip a critical edge splitter
155 * block when trying to find a branching goto/join
156 *
157 * SkipCriticalEdgeSplitter only needs to be set when used from inside
158 * GenXSimdCFConformance, before it has removed critical edge splitter blocks
159 * that separate a branching goto/join and the join label.
160 *
161 * "true" successor of branching block has to be a join label if it is not
162 * empty. This function does not test that.
163 *
164 */
getBranchingBlockForBB(BasicBlock * BB,bool SkipCriticalEdgeSplitter)165 BasicBlock *GotoJoin::getBranchingBlockForBB(BasicBlock *BB,
166 bool SkipCriticalEdgeSplitter) {
167 for (auto ui = BB->use_begin(), ue = BB->use_end(); ui != ue; ++ui) {
168 auto PredBr = dyn_cast<BranchInst>(ui->getUser());
169 if (!PredBr || ui->getOperandNo() != PredBr->getNumOperands() - 1)
170 continue;
171 // PredBr is a branch that has BB as its "true" successor. First skip a
172 // critical edge splitter.
173 auto PredBB = PredBr->getParent();
174 if (SkipCriticalEdgeSplitter && PredBr->getNumSuccessors() == 1
175 && PredBr == PredBB->getFirstNonPHIOrDbg() && PredBB->hasOneUse()) {
176 auto ui2 = PredBB->use_begin();
177 PredBr = dyn_cast<BranchInst>(ui2->getUser());
178 if (!PredBr || ui2->getOperandNo() != PredBr->getNumOperands() - 1)
179 continue;
180 PredBB = PredBr->getParent();
181 }
182 // Check to see if it is a goto/join.
183 if (isBranchingGotoJoinBlock(PredBB))
184 return PredBB;
185 }
186 return nullptr;
187 }
188
189 /***********************************************************************
190 * isJoinLabel : check whether this block needs to be a join label, because
191 * it is the "true" successor of at least one goto/join branch
192 *
193 * See getBranchingBlockForBB for details.
194 *
195 */
isJoinLabel(BasicBlock * BB,bool SkipCriticalEdgeSplitter)196 bool GotoJoin::isJoinLabel(BasicBlock *BB, bool SkipCriticalEdgeSplitter) {
197 return getBranchingBlockForBB(BB, SkipCriticalEdgeSplitter);
198 }
199
200 /***********************************************************************
201 * isGotoBlock : see if a basic block is a goto block (hence branching),
202 * returning the goto if so
203 *
204 * See the comment at the top of isBranchingGotoJoinBlock regarding the case
205 * of a goto with an unconditional branch.
206 */
isGotoBlock(BasicBlock * BB)207 CallInst *GotoJoin::isGotoBlock(BasicBlock *BB)
208 {
209 auto Goto = isBranchingGotoJoinBlock(BB);
210 if (GenXIntrinsic::getGenXIntrinsicID(Goto) != GenXIntrinsic::genx_simdcf_goto)
211 Goto = nullptr;
212 return Goto;
213 }
214
215 /***********************************************************************
216 * isBranchingJoinBlock : see if a basic block is a branching
217 * join block, returning the join if so
218 */
isBranchingJoinBlock(BasicBlock * BB)219 CallInst *GotoJoin::isBranchingJoinBlock(BasicBlock *BB)
220 {
221 auto Join = isBranchingGotoJoinBlock(BB);
222 if (GenXIntrinsic::getGenXIntrinsicID(Join) != GenXIntrinsic::genx_simdcf_join)
223 Join = nullptr;
224 return Join;
225 }
226
227 /***********************************************************************
228 * isBranchingGotoJoinBlock : see if a basic block is a branching
229 * goto/join block, returning the goto/join if so
230 *
231 * This includes the case of a goto with an unconditional branch, as long as
232 * this is after GenXLateSimdCFConformance (or during GenX*SimdCFConformance
233 * after it has run moveCodeInGotoBlocks), because it relies on
234 * moveCodeInGotoBlocks having sunk the goto and its extracts to the end of the
235 * block.
236 */
isBranchingGotoJoinBlock(BasicBlock * BB)237 CallInst *GotoJoin::isBranchingGotoJoinBlock(BasicBlock *BB)
238 {
239 auto Br = dyn_cast<BranchInst>(BB->getTerminator());
240 if (!Br)
241 return nullptr;
242 if (!Br->isConditional()) {
243 // Unconditional branch. Check for the block ending with a goto or an
244 // extract from a goto.
245 if (Br == &BB->front())
246 return nullptr;
247 Value *LastInst = Br->getPrevNode();
248 if (auto EV = dyn_cast<ExtractValueInst>(LastInst))
249 LastInst = EV->getOperand(0);
250 if (GenXIntrinsic::getGenXIntrinsicID(LastInst) == GenXIntrinsic::genx_simdcf_goto)
251 return cast<CallInst>(LastInst);
252 return nullptr;
253 }
254 // Conditional branch. Check for the condition being an extractvalue from a
255 // goto/join.
256 auto EV = dyn_cast<ExtractValueInst>(Br->getCondition());
257 if (!EV)
258 return nullptr;
259 auto GotoJoin = dyn_cast<CallInst>(EV->getOperand(0));
260 if (!GotoJoin || GotoJoin->getParent() != BB)
261 return nullptr;
262 switch (GenXIntrinsic::getGenXIntrinsicID(GotoJoin)) {
263 case GenXIntrinsic::genx_simdcf_goto:
264 case GenXIntrinsic::genx_simdcf_join:
265 return GotoJoin;
266 default:
267 break;
268 }
269 return nullptr;
270 }
271
272 /***********************************************************************
273 * getLegalInsertionPoint : ensure an insertion point is legal in the presence
274 * of SIMD CF
275 *
276 * This is used by a pass that inserts or moves code after
277 * GenXLateSimdCFConformance.
278 *
279 * A branching join label block is not allowed any other code. If the insertion
280 * point is in one of those, move up to its immediate dominator.
281 *
282 * A goto or branching join is not allowed code after the goto/join. If the
283 * insertion point is there, move to just before the goto/join.
284 */
getLegalInsertionPoint(Instruction * InsertBefore,DominatorTree * DomTree)285 Instruction *GotoJoin::getLegalInsertionPoint(Instruction *InsertBefore,
286 DominatorTree *DomTree)
287 {
288 auto *InsertPoint = InsertBefore;
289 auto *InsertBB = InsertBefore->getParent();
290 while (isBranchingJoinLabelBlock(InsertBB)) {
291 auto Node = DomTree->getNode(InsertBB);
292 IGC_ASSERT(Node);
293 auto IDom = Node->getIDom();
294 IGC_ASSERT(IDom);
295 InsertBB = IDom->getBlock();
296 InsertPoint = InsertBB->getTerminator();
297 }
298 if (auto GotoJoin = isBranchingGotoJoinBlock(InsertBB))
299 InsertPoint = GotoJoin;
300
301 if (InsertBB == InsertBefore->getParent()) {
302 // If this is the same BB check that our InsertPoint
303 // goes before than InsertBefore
304 auto *TermInst = InsertBB->getTerminator();
305 Instruction *t = InsertPoint;
306 while (t != InsertBefore) {
307 if (t == TermInst) {
308 InsertPoint = InsertBefore;
309 break;
310 }
311 t = t->getNextNode();
312 }
313 }
314 return InsertPoint;
315 }
316
317