Debian Codegraph @

visa/iga/IGALibrary/IR/DUAnalysis.cpp

raw
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 /******************************************************************************
11 * This performs a basic liveness/DU analysis (reverse walk) of the
12 * register files (GRF and ARF). The RegSet abstraction tracks bytes
13 * touched by instructions.
14 *
15 * We choose a reverse (backwards) analysis because we want the algorithm to
16 * infer kernel inputs (or use of uninitialized variables).
17 * ==> Hence, read examples bottom up.
18 ******************************************************************************
19 * IMPLEMENTATION NOTES:
20 *
21 * - The analysis is conservative/approximate.
22 *
23 * - The algorithm runs in three steps.
24 * (a) precompute the data flow sets
25 * (b) iterate the graph until the fix point is reached
26 * (c) execute a final pass through to copy out data
27 *
28 * See below for notation and formalism below.
29 */
30 #include "DUAnalysis.hpp"
31
32 // Uncomment this for debug tracing of the algorithm
33 // #define ENABLE_TRACING
34
35 #include <algorithm>
36 #ifdef ENABLE_TRACING
37 #include "../strings.hpp"
38 #include <cstdio>
39 #endif
40 #include <list>
41 #include <map>
42 #include <set>
43 #include <sstream>
44 #include <string>
45 #include <unordered_set>
46 // #include <unordered_map>
47
48 using namespace iga;
49
50 #ifdef ENABLE_TRACING
51 #define TRACE(...) (std::cout << iga::format(__VA_ARGS__) << "\n")
52 #else
53 #define TRACE(...)
54 #endif
55 /***************************************************************************
56 * Notes: below we adopt an extremely compact notation, but which still
57 * captures all the absurd complexity this hardward induces. Here are some
58 * notes and examples on the notation in comments.
59 *
60 * - The analysis is bottom up; so generally read examples bottom up since
61 * that's the order we process things in.
62 *
63 * - This is standard reverse-order bottom up iterative data flow analysis
64 * with a few enhancements. Each block has a liveIN and liveOUT set.
65 * We recompute these iterateively and join them with the typical
66 * monotonic 'meet' function until a fixed point is reached. (The sets
67 * should form properly ordered latices and should converge to a fixed
68 * solution.)
69 *
70 * - Predication adds complexity classic compiler texts don't consider.
71 * At the simplest level consider a predicated instruction a short branch.
72 * I.e. X = (P) add ... is the same as: if (P) X = add ...
73 * However, often compilers will reduce if/else or expand selects into
74 * a predicate assignment and complement predicate. E.g.
75 * X = (P) add ...;
76 * X = (~P) add ... definitely kills X
77 * Without special help, regular data flow treats this as:
78 * if (P) add .. X
79 * if (~P) add .. X
80 * which fails to definitely kill off X.
81 * Worse, the scheduler might float these pairs far apart, and, if that
82 * wasn't bad enough, the writes may be chunked into smaller pieces due to
83 * hardware restriction (several predicated ops to create X);
84 * e.g.
85 * X[1] = (P[1]) add .. fragment #0 of P
86 * X[0] = (P[0]) add .. fragment #1 of P
87 * X[0,1] = (~P[0,1]) add .. full part of ~P[0,1]
88 * use X[0,1]
89 * This can happen since we must break things down to smaller instructions
90 * for hardware restrictions (e.g. DF's max ExecSize is half F's).
91 * This leads to a "Humpty Dumpty" dataflow analysis (a mess).
92 * Thus, to detect complement predicate pairs, we must track all
93 * predicated operations in a dataflow within a block.
94 * Nevertheless, if pairs are nearby and uncomplicated (not fragmented),
95 * it should be fairly efficient. However, pathological cases exist.
96 *
97 * - Notation. Rather that showing full complicated instructions,
98 * most examples reduce the to general 'def' and 'use' instructions
99 * in comments below.
100 * X = def ... // defines X
101 * X = P def ... // defines X under predicate P
102 * ...
103 * use X
104 *
105 * - Since we are dealing with fully vectorized code we use array
106 * notation to illustrate fragmenting. Formally, the values needn't
107 * be adjacent (X[0] may not be near X[1]), but in practice they will be.
108 * A: X[0,1] = def ... // defines X[0] and X[1] unconditionally
109 * B: X[1] = P[0] def ... // defines X[1] under predicate P[0]
110 * C: use X[1] // uses X[1] // uses just X[1]
111 * The above yields DU relations {(A,C,X[1]),(A,B,X[1])}
112 *
113 * - In some cases we give data flow graphs with ASCII characters.
114 * (read this bottom up)
115 * XXXX|||| X[0] = def ... // live range fully partially killed off
116 * |||||||| ... // nothing changes (disj. insts.)
117 * ||||++++ X[1] = P[0] def // part of range conditionally killed
118 * XXXXXXXX use X[0,1]
119 * Even if not explicitly stated in an example, one should assume there
120 * could be non-interfering instructions between each line above.
121 */
122
123 // A predicated kill within a live path within a basic block.
124 // These are created and killed off during analysis within a block.
125 struct PredicatedKill {
126 bool inverted;
127 const RegSet::Bits *predicate; // ptr for implicit constructors etc...
128 RegSet kills;
129 int instId; // instruction ID for debugging only
130
131 PredicatedKill(bool inv, const RegSet::Bits &pr, const RegSet &ks, int id)
132 : inverted(inv), predicate(&pr), kills(ks), instId(id) {}
133 };
134
135 // A set of distances (other instructions covered between def and use).
136 struct Dists {
137 int allPipes = 0;
138
139 void incrementFor(const Instruction &i) {
140 (void)i;
141 allPipes++;
142 }
143
144 bool meet(const Dists &rhs) {
145 bool changed = false;
146 if (rhs.allPipes < allPipes) {
147 allPipes = rhs.allPipes;
148 changed = true;
149 }
150 return changed;
151 }
152
153 bool operator==(const Dists &rhs) const { return allPipes == rhs.allPipes; }
154 bool operator!=(const Dists &rhs) const { return !(*this == rhs); }
155 };
156
157 // A live path is a use instruction paired with the bytes that are live
158 // at the given instruction's position.
159 struct LivePath {
160 // The instruction using the set of values we are tracking.
161 Instruction &use;
162 int useId;
163
164 // The current set of values still live within this path. We reduce
165 // this until live is empty, at which point the live the path is killed
166 // off.
167 RegSet live;
168 bool usePredInv;
169 RegSet::Bits usePred;
170
171 // Predicated kills are instructions prior to our current location
172 // that conditionally killed off some subset of 'live'; this is a
173 // local (block-only) view of predicated kills in this data flow.
174 // EXAMPLE: (read bottom up)
175 // X = !P def << finishes the kill (since we now have P and !P)
176 // ...
177 // X = P def ... << partial kill #2
178 // ...
179 // X = P def ... << partial kill #1
180 // ...
181 // U = use X (new LivePath)
182 //
183 // We do have to be careful about interference
184 // (e.g. someone redefines P or part of it)
185 // The easy solution there is to just clear interfering elements
186 // from this set when someone clobbers P.
187 //
188 // (It gets worse when you start considering partial kills and
189 // partial predicates: a real possibility with this SIMD non-sense)
190 // X[0,1] = def ..
191 // ...
192 // X[0] = @P[0] def
193 // ...
194 // X[1] = @P[1] def
195 // ...
196 // use X
197 //
198 // These are typically dropped during propagation back to a successor,
199 // though if the successor is unique (a unit edge), then we can safely
200 // do so.
201 std::vector<PredicatedKill> pKills;
202
203 // the minimum number of branches this path has crossed
204 unsigned minBlocksCrossed = (unsigned)-1;
205 // Same as above but excludes fallthrough
206 // (this includes fallthrough)
207 unsigned minBranchesCrossed = (unsigned)-1;
208
209 // the minimum number of instructions this path has traveled
210 Dists minDists;
211
212 LivePath(Instruction &u)
213 : use(u), useId(u.getID()), live(u.model()),
214 usePredInv(u.hasPredication() && u.getPredication().inverse),
215 usePred(RegSet(u.model()).bitSetFor(RegName::ARF_F)) {}
216
217 // State that should not be propagated across blocks
218 void clearLocalState() {
219 usePred.clear();
220 pKills.clear();
221 }
222
223 // The update() is called during path extension within a block against
224 // instruction 'i'.
225 //
226 // (read bottom to top)
227 //
228 // |||| (still have pending predicates on P[2,4])
229 // ^^^^
230 // XXXX|||| X[0] = def <<<<< YOU ARE HERE <<<<<
231 // ||||||||
232 // ||||++++ X[1] = P[4] def
233 //
234 // |||||||| P[2] = def // kills P[2]
235 //
236 // ||||||||
237 // ++++++++ X[0,1] = P[3,4] def
238 // ||||---- X[1] = P[2] def
239 // ||||||||
240 // ----|||| X[0] = ~P[0] def
241 // ||||||||
242 // XXXXXXXX use ... X[0,1]
243 //
244 // In the above, entering the example instruction pKills would be:
245 // X[0]|~P[0] def, X[0]|P[3], X[1]|P[4]
246 // (note: X[0,1]|P[3,4] split to X[0]|P[3] and X[1]|P4)
247 // The output should be:
248 // X[1]|P[4]
249 // since all X[0] predicates got killed off unconditionally
250 //
251 // SPECIFY: how to handle interfering definitions of P
252 // ==> I think we just ditch all predicates related to those new regions
253 // This is the analog of how it would work if they were proper branches
254 // (It'd be a fresh D/U pair only)
255 void update(int iId, const RegSet::Bits &iPred, bool iPredInv,
256 const RegSet &iKills, const RegSet &iOverlapU) {
257 if (!iOverlapU.empty()) {
258 // this instruction impacts our dataflow
259 // (without considering predication)
260 if (iPred.empty() ||
261 (iPredInv == usePredInv && usePred.intersects(iPred))) {
262 // definitely removing some values from this live range
263 live.destructiveSubtract(iOverlapU);
264 // see if this def is a complementary predicate
265 subtractComplPredKills(iOverlapU);
266 } else {
267 // see if we can combine this subtraction with complementary
268 // predicated kills
269 subtractComplPredKills(iOverlapU, iPred, iPredInv);
270 }
271 if (live.empty()) {
272 // we're about to be deleted; no need to tidy up our state
273 return;
274 }
275 }
276
277 addNewPredicatedKills(iOverlapU, iPred, iPredInv, iId);
278 }
279
280 // Checks if an instruction's predication interferes with this path's
281 // use predication.
282 // E.g.
283 // ? = def // everything matches unpred. def
284 // P* use X // YES
285 //
286 // OR
287 //
288 // ? = P[0,1] def
289 // ...
290 // use X // YES (conservative)
291 // P[0] use X // YES (intersects)
292 // P[0,1] use X // YES (intersects)
293 // P[0,1,2,3] use X // YES (intersects)
294 // ~* use X // NO (sign mismatch)
295 // P[2] use X // NO (disjoint predicate)
296 //
297
298 bool matchesPredication(const RegSet::Bits &iPred, bool iPredInv) const {
299 return (usePred.empty() || iPred.empty() ||
300 (iPredInv == usePredInv && usePred.intersects(iPred)));
301 }
302
303 // If the current instruction is predicated and overlaps, we must
304 // record the new predicated kills.
305 // EXAMPLE:
306 // ....
307 // ||||++++ X[1] = P[0] def << YOU ARE HERE
308 // ....
309 // XXXXXXXX = use X[0,1]
310 //
311 // We don't bother to see if this covers another similarly predicated
312 // kill later; extra copies are fine for our purposes.
313 void addNewPredicatedKills(const RegSet &overlap, const RegSet::Bits &pred,
314 bool predInverted, int instId) {
315 if (pred.empty() || overlap.empty()) {
316 return;
317 }
318 TRACE(" I#", use.getID(), ": inserting predicated kill ",
319 (predInverted ? "~" : ""),
320 RegSet::str(overlap.getModel(), RegName::ARF_F, pred), " against I#",
321 instId);
322 pKills.emplace_back(predInverted, pred, overlap, instId);
323 }
324
325 // Folds complementary predicate kills over the same bytes and
326 // same predication together an promotes them to unpredicated kills.
327 // EXAMPLE:
328 // ||||---- X[1] = ~P[0] def <<<< should kill off X[1]
329 // ++++|||| X[0] = P[0] def << don't match
330 // ||||++++ X[1] = P[0] def << do match
331 // XXXXXXXX = use X[0,1]
332 void subtractComplPredKills(const RegSet &overlap, // subset of kills
333 const RegSet::Bits &pred, bool predInverted) {
334 IGA_ASSERT(!pred.empty(), "predication should be non-empty");
335 for (int i = (int)pKills.size() - 1; i >= 0; --i) {
336 PredicatedKill &pk = pKills[i];
337 if (pk.inverted == predInverted) {
338 // sign matches, so we can't subtract
339 continue;
340 }
341 // RegSet::Bits prOverlap =
342 // RegSet::Bits::intersection(pred, *pk.predicate);
343 if (!pred.intersects(*pk.predicate)) {
344 continue;
345 }
346 RegSet killOverlap = RegSet::intersection(overlap, pk.kills);
347 if (killOverlap.empty()) {
348 continue;
349 }
350 // some part of kill and predicate overlap with mismatch of signs
351 // this overlap is "definitely" killed by this instruction
352 bool changedL = live.destructiveSubtract(killOverlap);
353 if (changedL && live.empty()) {
354 break; // early out: nothing live ==> no more work needed
355 }
356 bool changedP = pk.kills.destructiveSubtract(killOverlap);
357 if (changedP && pk.kills.empty()) {
358 TRACE(" I#", use.getID(), ": invalidating predicated write");
359 pKills.erase(pKills.begin() + i);
360 } else {
361 TRACE(" I#", use.getID(), ": eroding predicated write");
362 }
363 } // for: predicated kills
364 } // subtractPredicatedKills
365
366 // Remove all interfering predicated kills.
367 //
368 // We could merge this with the other, but one might argument it's a bit
369 // harder to read. (i.e. it's similar but easier.)
370 //
371 // EXAMPLE:
372 // ||||XXXX X[1] = def
373 // ++++|||| X[0] = P[0] def << mismatch on 'overlap'
374 // ||||++++ X[1] = P[0] def << erase this
375 // XXXXXXXX = use X[0,1]
376 void subtractComplPredKills(const RegSet &overlap) {
377 for (int i = (int)pKills.size() - 1; i >= 0; --i) {
378 PredicatedKill &pk = pKills[i];
379 RegSet killOverlap = RegSet::intersection(overlap, pk.kills);
380 if (killOverlap.empty()) {
381 continue;
382 }
383 bool changedP = pk.kills.destructiveSubtract(killOverlap);
384 if (changedP && pk.kills.empty()) {
385 TRACE(" I#", use.getID(),
386 ": invalidating predicated write (uncond.)");
387 pKills.erase(pKills.begin() + i);
388 } else {
389 TRACE(" I#", use.getID(),
390 ": eroding predicated write (uncond.)");
391 }
392 } // for: predicated kills
393 } // subtractPredicatedKills
394
395 // Remove predicated kills that interfere with this kill set even if
396 // the current instruction is also predicated; and even if the overlap
397 // is only partial.
398 // Theoretically, if it was an additive operation (e.g. OR, BFN.OR),
399 // we could safely retain it, but that's rare enough to be ignored.
400 //
401 // e.g. unconditional kill of a predicated kill
402 // ||||++++ X[1] = P[0] def <<< different P[0] than at A:
403 // |||||||| P[0] = def <<<<<< YOU ARE HERE
404 // A: ||||---- X[1] = P[0] def
405 // B: ++++|||| X[0] = P[1] def
406 // XXXXXXXX use X[0,1]
407 //
408 // e.g. even if the predicate kill is predicated itself
409 // ||||++++ X[1] = P[0] def <<< different P[0] than at A:
410 // |||||||| P[0] = P[2] def <<<<<< YOU ARE HERE
411 // A: ||||---- X[1] = ~P[0] def
412 // B: ++++|||| X[0] = P[1] def
413 // XXXXXXXX use X[0,1]
414 //
415 // e.g. partial kill of predicated kill still causes full removal
416 // ||||++++ X[1] = P[0] def <<< different P[0] than at A:
417 // |||||||| P[0] = P[2] def <<<<<< YOU ARE HERE
418 // B: -------- X[0] = ~P[0,1] def
419 // XXXXXXXX use X[0,1]
420 // Even though the partial kill only clobbers P[0] (P[1] is intact),
421 // we don't track which bytes that covers (alignment) in the predicated
422 // kill; consequently the easiest thing to do is punt and conservatively
423 // forget about the entire predicated kill. In practice, garbage like
424 // this, shouldn't be generated.
425 void updateForPredicateRedefs(const RegSet &kills) {
426 const RegSet::Bits &killsF = kills.bitSetFor(RegName::ARF_F);
427 if (killsF.empty()) {
428 return; // this instruction doesn't write predicates ==> done
429 }
430 if (killsF.intersects(usePred)) {
431 // this instruction fiddles writes the predicates we depend on
432 // conservatively stop trying to constrain defs by same predicate
433 usePred.clear();
434 }
435 // any predicated kills we are tracking
436 for (int i = (int)pKills.size() - 1; i >= 0; --i) {
437 PredicatedKill &pk = pKills[i];
438 if (pk.predicate->intersects(killsF)) {
439 pKills.erase(pKills.begin() + i);
440 }
441 } // for
442 }
443
444 // The meet operator
445 //
446 // This updates 'this' (implicit object / receiver) merging data from
447 // 'rhs' and indicates if something changed
448 bool meet(const LivePath &rhs) {
449 bool changed = false;
450
451 changed |= minDists.meet(rhs.minDists);
452
453 if (minBlocksCrossed == (unsigned)-1 ||
454 rhs.minBlocksCrossed < minBlocksCrossed) {
455 minBlocksCrossed = rhs.minBlocksCrossed;
456 changed = true;
457 }
458 if (minBranchesCrossed == (unsigned)-1 ||
459 rhs.minBranchesCrossed < minBranchesCrossed) {
460 minBranchesCrossed = rhs.minBranchesCrossed;
461 changed = true;
462 }
463
464 changed |= live.destructiveUnion(rhs.live);
465
466 return changed;
467 }
468
469 Dep toDep(Instruction *def, const RegSet &values) const {
470 Dep d(def, values, &use);
471 d.minInsts = minDists.allPipes;
472 // cast to int because (unsigned)0xFFFFFFFF needed for
473 // set reduction latice (min function)
474 d.crossesBlock = (int)minBlocksCrossed > 0;
475 d.crossesBranch = (int)minBranchesCrossed > 0;
476 return d;
477 }
478
479 bool operator==(const LivePath &rhs) const {
480 return &use == &rhs.use && live == rhs.live && minDists == rhs.minDists &&
481 minBlocksCrossed == rhs.minBlocksCrossed &&
482 minBranchesCrossed == rhs.minBranchesCrossed;
483 }
484 bool operator!=(const LivePath &rhs) const { return !(*this == rhs); }
485
486 std::string str() const {
487 std::stringstream ss;
488 ss << "#" << use.getID() << " = " << live.str();
489 return ss.str();
490 }
491 std::string strFull() const {
492 std::stringstream ss;
493 ss << str();
494 if (!pKills.empty()) {
495 ss << " with pkills ";
496 bool first = true;
497 for (const PredicatedKill &pk : pKills) {
498 if (first)
499 first = false;
500 else
501 ss << ", ";
502 pk.kills.str(ss);
503 ss << "=";
504 if (pk.inverted) {
505 ss << "~";
506 }
507 ss << RegSet::str(pk.kills.getModel(), RegName::ARF_F, *pk.predicate);
508 ss << " def I#" << pk.instId;
509 }
510 }
511 return ss.str();
512 }
513 }; // LivePath
514
515 #ifdef ENABLE_TRACING
516 // forces certain debug functions to be compiled under trace
517 void fake(const void *vlp, std::ostream &os) {
518 const LivePath *lp = (const LivePath *)vlp;
519 os << lp->strFull();
520 os << lp->pKills[0].predicate->str();
521 }
522 #endif
523
524 using LivePaths = std::map<Instruction *, LivePath>;
525
526 enum class EdgeType { FALLTHROUGH, JUMP };
527
528 // Information pertaining to a given block. We convert this to
529 // a public-facing BlockInfo that discards all the temporary and
530 // non-essential information from the algorithm when extracting
531 // and returning the results.
532 struct BlockState {
533 Block *block;
534
535 // predecessor info (second coordinate is true if the node is *not*
536 // a fallthrough (i.e. it's a jump)
537 // indexed by block ID
538 std::vector<std::pair<BlockState *, EdgeType>> pred;
539
540 LivePaths liveIn;
541 LivePaths liveOut;
542
543 // if a worklist algorithm is used
544 bool dirty = true;
545
546 BlockState(Block *b) : block(b) {}
547
548 std::string str() const {
549 std::stringstream ss;
550 ss << idstr() << " pred:{";
551 bool first = true;
552 for (const auto &pbse : pred) {
553 if (first)
554 first = false;
555 else
556 ss << ",";
557 ss << pbse.first->idstr();
558 }
559 ss << "}";
560 return ss.str();
561 }
562
563 std::string idstr() const { return "B#" + std::to_string(block->getID()); }
564 };
565
566 struct DepAnalysisComputer {
567 const Model &model;
568 const Kernel *k;
569
570 // precomputed sources and destination sets indexed by instruction ID
571 std::vector<RegSet> instDstsUnion;
572 std::vector<InstSrcs> instSrcs;
573
574 // mid-state and then output
575 std::vector<BlockState> blockState;
576
577 // outputs
578 DepAnalysis &results;
579
580 DepAnalysisComputer(const Kernel *_k, DepAnalysis &_results)
581 : model(_k->getModel()), k(_k), results(_results) {
582 sanityCheckIR(k); // should nop in release
583
584 results.deps.clear();
585 results.liveIn.clear();
586 results.sums.resize(k->getInstructionCount());
587
588 instSrcs.reserve(k->getInstructionCount());
589 instDstsUnion.reserve(k->getInstructionCount());
590
591 // we must do this so the vector doesn't resize
592 blockState.reserve(k->getBlockList().size());
593
594 // pre-assign ID's we know to be valid and
595 // precompute instruction dependencies
596 for (Block *b : k->getBlockList()) {
597 IGA_ASSERT((size_t)b->getID() == blockState.size(),
598 "we assume block ids go from 0 ... n-1");
599 blockState.emplace_back(b);
600
601 auto iitr = b->getInstList().begin();
602 while (iitr != b->getInstList().end()) {
603 Instruction *i = *iitr;
604 IGA_ASSERT((size_t)i->getID() == instSrcs.size(),
605 "we assume block ids go from 0 ... n-1");
606 instSrcs.emplace_back(InstSrcs::compute(*i));
607 IGA_ASSERT((size_t)i->getID() == instDstsUnion.size(),
608 "we assume block ids go from 0 ... n-1");
609 instDstsUnion.emplace_back(InstDsts::compute(*i).unionOf());
610 // Given Gather Send this attempts to resolve the registers accessed
611 // indirectly; we expect the pattern:
612 //
613 // (W) mov (1) s0.K<1>:{uq,q} 0x000000000105010A:{uq,q}
614 // ... maybe an instruction or two
615 // send ... r[s0.K]:4 ... // sends {r1,r5,r1,r10}
616 //
617 if (i->isGatherSend()) {
618 int src0Len = i->getSrc0Length();
619 auto gatheredGrfs =
620 findGatherSendMov(iitr, b->getInstList().begin(),
621 i->getSource(0).getDirRegRef().subRegNum, src0Len);
622 instSrcs.back().sources.destructiveUnion(gatheredGrfs);
623 }
624 iitr++;
625 }
626 }
627
628 // pre-calculate predecessor blocks by looking at the terminator op
629 for (size_t i = 0; i < blockState.size(); i++) {
630 BlockState &b = blockState[i];
631
632 const auto &il = b.block->getInstList();
633 bool isLast = i == blockState.size() - 1;
634 // not the last => potentially link the next block back to us
635 if (il.empty()) {
636 // empty block fallthrough
637 // E.g.
638 //
639 // ...
640 // FOO: // empty block, but valid branch target
641 // BAR:
642 // ...
643 if (!isLast)
644 blockState[i + 1].pred.emplace_back(&b, EdgeType::FALLTHROUGH);
645 } else {
646 // at least one instruction in this block;
647 // mark 'b' as a predecessor to all targets
648 //
649 // unpredicated JMPI and an EOT are the only op that
650 // stop the block hard
651 const Instruction *iTerm = il.back();
652 if (!isLast && fallthroughPossible(iTerm)) {
653 // normal fallthrough
654 blockState[i + 1].pred.emplace_back(&b, EdgeType::FALLTHROUGH);
655 }
656 for (unsigned srcIx = 0; srcIx < iTerm->getSourceCount(); srcIx++) {
657 const Operand &src = iTerm->getSource(srcIx);
658 if (src.getKind() == Operand::Kind::LABEL) {
659 BlockState &tb = blockState[src.getTargetBlock()->getID()];
660 tb.pred.emplace_back(&b, EdgeType::JUMP);
661 }
662 }
663 } // non-empty block 'b'
664 } // end for(block state)
665
666 TRACE("******** INITIAL CONDITIONS **********");
667 for (const Block *b : k->getBlockList()) {
668 TRACE(" BLOCK ", blockState[b->getID()].str());
669 for (const Instruction *i : b->getInstList()) {
670 (void)i;
671 TRACE(" DEF #", i->getID(), " | ", trimTrailingWs(i->str()),
672 " || ", instDsts[i->getID()].str(),
673 " <== ", instSrcs[i->getID()].str());
674 }
675 }
676 } // DepAnalysisComputer::DepAnalysisComputer
677
678 RegSet findGatherSendMov(InstList::iterator iitr, InstList::iterator ibegin,
679 uint16_t s0Subreg, int src0Len) {
680 RegSet grfs(model);
681 // The local match allows for kills of s0.K
682 // (P) mov ... s0.K:T IMM:T
683 // (P) mov ... s0.K:T IMM:T
684 // send r[s0.K]
685 if (iitr == ibegin)
686 return grfs; // first instruction of the block
687 // const Instruction *iSendg = *iitr;
688 //
689 if (src0Len <= 0)
690 return grfs;
691 //
692 RegSet rsPredFirstMov(model);
693 bool predFirstMovSign = false;
694
695 RegSet rsS0(model);
696 if (src0Len <= 4)
697 rsS0.add(RegName::ARF_S, RegRef((uint16_t)0, uint16_t(s0Subreg / 4)),
698 Type::UD);
699 else
700 rsS0.add(RegName::ARF_S, RegRef((uint16_t)0, uint16_t(s0Subreg / 8)),
701 Type::UQ);
702 //
703 do {
704 iitr--;
705 const Instruction *i = *iitr;
706 const Operand &dst = i->getDestination();
707 const Operand &src0 = i->getSource(0);
708
709 bool isS0Def =
710 i->is(Op::MOV) && dst.getKind() == Operand::Kind::DIRECT &&
711 dst.getDirRegName() == RegName::ARF_S && src0.isImm() &&
712 TypeSizeInBits(dst.getType()) >= 4 &&
713 TypeSizeInBits(dst.getType()) / 8 * dst.getDirRegRef().subRegNum ==
714 s0Subreg &&
715 TypeSizeInBits(src0.getType()) >= 4;
716 if (isS0Def) {
717 // (W) mov (1) s0.K:{q,uq} IMM64:{q,uq,d,ud,w,uw}
718 // (W) mov (1) s0.K:{d,ud} IMM64:{d,ud,w,uw}
719 // (W) mov (1) s0.K:{f} IMM:{f}
720 uint64_t imm = src0.getImmediateValue().u64;
721 for (int i = 0; i < src0Len; i++, imm >>= 8) {
722 int grf = (imm & 0xFF);
723 grfs.addReg(RegName::GRF_R, grf);
724 }
725 if (!i->hasPredication()) {
726 break; // unpredicated is full def (hopfeully the normal case)
727 } else {
728 // we also allow for two predicated definitions
729 // (W & fX) mov .. s0.K:q 0x0201:q
730 // (W & ~fX) mov .. s0.K:q 0x0304:q
731 if (rsPredFirstMov.empty()) {
732 rsPredFirstMov.add(RegName::ARF_F, i->getFlagReg(), Type::B);
733 predFirstMovSign = i->getPredication().inverse;
734 } else {
735 RegSet rsSecondPred{model};
736 rsSecondPred.add(RegName::ARF_F, i->getFlagReg(), Type::B);
737 if (rsSecondPred.intersects(rsPredFirstMov)) {
738 if (i->getPredication().inverse != predFirstMovSign) {
739 break; // full def
740 }
741 // else: dead def (continue to look for second)
742 }
743 }
744 }
745 } else {
746 // make sure it doesn't interfere with a partial definition's
747 // scalar or predication
748 const auto &rsDsts = instDstsUnion[i->getID()];
749 if (rsDsts.intersects(rsS0)) {
750 // some other jerk clobbered part of our s0.# with an
751 // instruction we don't deal with
752 break;
753 } else if (rsDsts.intersects(rsPredFirstMov)) {
754 // someone clobbered the predicate value we were tracking
755 break;
756 }
757 }
758 } while (iitr != ibegin);
759
760 return grfs;
761 } // findGatherSendMov
762
763 static bool fallthroughPossible(const Instruction *i) {
764 bool unconditionalJmp = i->getOp() == Op::JMPI && !i->hasPredication();
765 bool eotTerm = i->hasInstOpt(InstOpt::EOT);
766 return !unconditionalJmp && !eotTerm;
767 }
768
769 // in debug builds this ensures:
770 // 1. block and instruction IDs aren't huge random numbers
771 // (since we intend to index-map information)
772 // 2. ensure IDs are unique
773 // 3. ensure there are branch instructions hiding in the middle of
774 // a block
775 static void sanityCheckIR(const Kernel *k) {
776 #ifdef _DEBUG
777 // NOTE: this is redundant because we preset all the ids above;
778 // it does add checking for illegal mid-block branches
779 std::unordered_set<int> instIds, blockIds;
780 auto instCount = k->getInstructionCount();
781 for (const Block *b : k->getBlockList()) {
782 auto bId = b->getID();
783 IGA_ASSERT(bId < 2 * (int)k->getBlockList().size(),
784 "instruction ID's should be small");
785 IGA_ASSERT(blockIds.find(bId) == blockIds.end(), "duplicate block ID");
786 for (const Instruction *i : b->getInstList()) {
787 auto id = i->getID();
788 IGA_ASSERT(id < 2 * (int)instCount, "instruction ID's should be small");
789 IGA_ASSERT(instIds.find(id) == instIds.end(),
790 "duplicate instruction ID");
791 instIds.emplace(i->getID());
792
793 for (size_t sIx = 0; sIx < i->getSourceCount(); sIx++) {
794 if (i->getSource(sIx).getKind() == Operand::Kind::LABEL) {
795 IGA_ASSERT(b->getInstList().back() == i,
796 "label in the middle of a block");
797 }
798 }
799 }
800 }
801 #endif // _DEBUG
802 }
803
804 void runAnalysis() {
805 computeLiveInPaths();
806 completePaths();
807 }
808
809 enum class IterationStrategy { INORDER, REVERORD, WORKLIST };
810
811 void computeLiveInPaths() {
812 static const IterationStrategy strat = IterationStrategy::WORKLIST;
813
814 if (strat == IterationStrategy::INORDER) {
815 results.iterations = iterateLiveInSets<IterationStrategy::INORDER>();
816 } else if (strat == IterationStrategy::REVERORD) {
817 results.iterations = iterateLiveInSets<IterationStrategy::REVERORD>();
818 } else if (strat == IterationStrategy::WORKLIST) {
819 results.iterations = iterateLiveInSets<IterationStrategy::WORKLIST>();
820 } else {
821 IGA_ASSERT_FALSE("invalid walk strategy");
822 }
823 }
824
825 template <IterationStrategy STRAT> int iterateLiveInSets() {
826 int itr = 0;
827 bool changed = false;
828 do {
829 TRACE("******* STARTING LIVE-IN ITERATION ", itr);
830
831 changed = false;
832 if (STRAT == IterationStrategy::INORDER) {
833 for (BlockState &bs : blockState) {
834 TRACE(" *** processing ", bs.idstr());
835 changed |= recomputeBlockLiveIn(bs, false);
836 }
837 } else if (STRAT == IterationStrategy::REVERORD) {
838 for (int bsi = (int)blockState.size() - 1; bsi >= 0; bsi--) {
839 BlockState &bs = blockState[bsi];
840 TRACE(" *** processing ", bs.idstr());
841 changed |= recomputeBlockLiveIn(bs, false);
842 }
843 } else if (STRAT == IterationStrategy::WORKLIST) {
844 for (int bsi = (int)blockState.size() - 1; bsi >= 0; bsi--) {
845 BlockState &bs = blockState[bsi];
846 if (bs.dirty) {
847 TRACE(" *** processing ", bs.idstr());
848 changed |= recomputeBlockLiveIn(bs, false);
849 } else {
850 TRACE(" *** skipping ", bs.idstr());
851 }
852 }
853 } else {
854 IGA_ASSERT_FALSE("INVALID WALK STRATEGY");
855 }
856
857 TRACE("******* ENDING ITERATION ", itr);
858 itr++;
859 } while (changed);
860 return itr;
861 }
862
863 // Starting with liveOut, walk back through the instructions
864 // extending all paths backwards. Kill off stuff definitely defined,
865 // and start new paths. At the end, update this block's 'liveIn'
866 // and push it back across to predecessor block's 'liveOut'
867 bool recomputeBlockLiveIn(BlockState &bs, bool copyOut) {
868 #ifdef ENABLE_TRACING
869 std::string bLiveInBefore = FormatLivePaths(b.liveIn);
870 #endif
871 // all the live paths at the end of this block
872 LivePaths lps = bs.liveOut;
873
874 // FOR each instruction i
875 // extend paths backwards
876 // remove any paths killed off by a definition
877 // start any new paths induced by i's uses
878 auto &il = bs.block->getInstList();
879 for (auto iItr = il.rbegin(), iItrEnd = il.rend(); iItr != iItrEnd;) {
880 Instruction &i = **iItr;
881 TRACE(" *** I#", i.getID(), ": ", trimTrailingWs(i.str()));
882
883 // extend live ranges for all active paths
884 LivePaths::iterator lpsItr = lps.begin(), lpsEnd = lps.end();
885 while (lpsItr != lpsEnd) {
886 lpsItr = extendLivePathBackwards(i, lps, lpsItr, copyOut);
887 }
888
889 // any use of a variable starts a new live range
890 startNewLivePathBackwards(i, lps);
891
892 // after all paths are moved back we
893 if (copyOut) {
894 RegSet rs(model);
895 for (const auto &lps : lps) {
896 const LivePath &lp = lps.second;
897 rs.destructiveUnion(lp.live);
898 }
899 LiveCount &lc = results.sums[i.getID()];
900 lc.grfBytes = (unsigned)rs.bitSetFor(RegName::GRF_R).cardinality();
901 lc.accBytes = (unsigned)rs.bitSetFor(RegName::ARF_ACC).cardinality();
902 lc.scalarBytes = (unsigned)rs.bitSetFor(RegName::ARF_S).cardinality();
903 lc.flagBytes = (unsigned)rs.bitSetFor(RegName::ARF_F).cardinality();
904 lc.indexBytes = (unsigned)rs.bitSetFor(RegName::ARF_A).cardinality();
905 }
906
907 iItr++;
908 } // for instructions in this block
909
910 // clear all predicated kills before propagating the live path back
911 for (auto &e : lps) {
912 e.second.clearLocalState();
913 }
914
915 // mark this block as up to date; this must precede propagation since
916 // this block might be a predecessor of itself
917 bs.dirty = false;
918
919 //////////////////////////////////////////////////////////////////
920 // propagate live paths back into our liveIN and eventually across
921 // to caller
922 bool bLiveInChanged = updateLiveDefs(bs.liveIn, lps);
923 bool changedAnyPred = false;
924 if (bLiveInChanged) {
925 // push information back to predecessor nodes
926 TRACE(" ", bs.idstr(), ".IN changed from ", bLiveInBefore, " to ",
927 FormatLivePaths(bs.liveIn));
928 for (auto &predEdge : bs.pred) {
929 BlockState &bsPred = *(BlockState *)predEdge.first;
930
931 #ifdef ENABLE_TRACING
932 std::string predBefore = FormatLivePaths(bsPred.liveOut);
933 #endif
934 bool predChanged =
935 propagateLivePathsBack(bsPred.liveOut, bs.liveIn, predEdge.second);
936 bsPred.dirty |= predChanged;
937 changedAnyPred |= predChanged;
938 TRACE(" ", bs.idstr(), ".OUT changed from ", predBefore, " to ",
939 FormatLivePaths(bsPred.liveOut));
940 }
941 } else {
942 TRACE(" ", bs.idstr(), ".IN didn't change");
943 }
944
945 return changedAnyPred;
946 }
947
948 // extends a given dependency back one instruction,
949 // the range can be killed off and deleted or extended back normally
950 LivePaths::iterator extendLivePathBackwards(Instruction &i, LivePaths &lps,
951 LivePaths::iterator &lpItrs,
952 bool copyOut) {
953 const RegSet &iKills = instDstsUnion[i.getID()];
954
955 const RegSet::Bits &iPred =
956 instSrcs[i.getID()].predication.bitSetFor(RegName::ARF_F);
957 bool iPredInv = i.hasPredication() && i.getPredication().inverse;
958
959 LivePath &lp = lpItrs->second;
960
961 // capture changes to predicates before considering this instruction
962 // X = (~P) def (le)P
963 // (P) use X
964 // don't want to accidentially subtract out this def
965 lp.updateForPredicateRedefs(iKills);
966
967 RegSet iOverlap(model);
968
969 bool matchesPredication = lp.matchesPredication(iPred, iPredInv);
970 if (matchesPredication) {
971 bool overlapNotEmpty = lp.live.intersectInto(iKills, iOverlap);
972 // overlap are now the bytes we write that intersect with this live
973 // range; if not empty, this constitutes a new D/U pair
974 if (overlapNotEmpty && copyOut) {
975 results.deps.push_back(lp.toDep(&i, iOverlap));
976 }
977 }
978
979 lp.update(i.getID(), iPred, iPredInv, iKills, iOverlap);
980
981 if (lp.live.empty()) {
982 TRACE(" ", lp.str(), ": deleting range");
983 lpItrs = lps.erase(lpItrs);
984 } else {
985 lp.minDists.incrementFor(i);
986 TRACE(" ", lp.str(), ": extending range");
987 lpItrs++;
988 }
989
990 return lpItrs;
991 }
992
993 void startNewLivePathBackwards(Instruction &i, LivePaths &lps) {
994 const InstSrcs &iInps = instSrcs[i.getID()];
995 const RegSet &rsPreds = iInps.predication;
996 const RegSet &rsSrcs = iInps.sources;
997 const RegSet::Bits usePred = rsPreds.bitSetFor(RegName::ARF_F);
998
999 // early out (no dependencies on this instruction)
1000 if (rsPreds.empty() && rsSrcs.empty()) {
1001 return;
1002 }
1003
1004 LivePath *lp;
1005 const auto &itr = lps.find(&i);
1006 if (itr != lps.end()) {
1007 lp = &itr->second;
1008 } else {
1009 auto val = lps.emplace(&i, i);
1010 lp = &val.first->second;
1011 // lp->minBranchesCrossed = 0;
1012 // lp->minBlocksCrossed = -1;
1013 }
1014
1015 // clobber the old value
1016 lp->live.reset();
1017 lp->live.destructiveUnion(rsPreds);
1018 lp->live.destructiveUnion(rsSrcs);
1019 lp->usePred.clear();
1020 lp->usePred.add(usePred);
1021 TRACE(" ", lp->str(), ": starting live range");
1022 }
1023
1024 // propagates a successor's liveIN set to its predecessors's liveOUT
1025 bool
1026 propagateLivePathsBack(LivePaths &predOUT, // predecessor block live OUT
1027 const LivePaths &succIN, // successor block live IN
1028 EdgeType et) // jump or fallthrough
1029 {
1030 bool changed = false;
1031 for (const auto &lrElem : succIN) {
1032 const LivePath &lrSuccIN = lrElem.second;
1033 auto r = predOUT.emplace(lrElem.first, lrSuccIN);
1034 bool isNewValue = r.second;
1035 LivePath &lrPredOUT = r.first->second;
1036 if (isNewValue) {
1037 // a new path
1038 lrPredOUT.minBranchesCrossed = 0;
1039 lrPredOUT.minBlocksCrossed = 1;
1040 if (et == EdgeType::JUMP) {
1041 lrPredOUT.minBranchesCrossed = 1;
1042 }
1043 changed = true;
1044 } else {
1045 // changes an existing path
1046 changed |= lrPredOUT.meet(lrSuccIN);
1047 // TODO: if it's a unit branch, copy the live predicate info
1048 }
1049 } // for all source paths in succIN
1050 return changed;
1051 }
1052
1053 static bool updateLiveDefs(LivePaths &to, const LivePaths &from) {
1054 bool changed = from != to;
1055 if (changed) {
1056 #if defined(__ANDROID__)
1057 to.clear();
1058 for (auto iter : from) {
1059 to.insert(iter);
1060 }
1061 #else
1062 to = LivePaths(from);
1063 #endif
1064 }
1065 return changed;
1066 }
1067
1068 void completePaths() {
1069 // copy out the data
1070 TRACE("************ COPYING OUT RESULTS");
1071 for (BlockState &b : blockState) {
1072 recomputeBlockLiveIn(b, true);
1073 }
1074 if (!blockState.empty()) {
1075 // any ranges left over on the entry block can be tagged as
1076 // program inputs
1077 for (const auto &lpe : blockState.front().liveIn) {
1078 const auto &lp = lpe.second;
1079 results.liveIn.push_back(lp.toDep(nullptr, lp.live));
1080 }
1081 }
1082 }
1083 };
1084
1085 // #1 =*> #3 {r13..r14}
1086 // ? =*> #3 {r13..r14}
1087 void Dep::str(std::ostream &os) const {
1088 auto emitId = [&](const Instruction *i) {
1089 if (i) {
1090 os << "#" << i->getID();
1091 } else {
1092 os << "?";
1093 }
1094 };
1095 emitId(def);
1096 if (crossesBranch) {
1097 os << "=*>";
1098 } else {
1099 os << "=>";
1100 }
1101 emitId(use);
1102 os << " ";
1103 values.str(os);
1104 }
1105
1106 std::string Dep::str() const {
1107 std::stringstream ss;
1108 str(ss);
1109 return ss.str();
1110 }
1111
1112 bool Dep::operator==(const Dep &p) const {
1113 return def == p.def && use == p.use && values == p.values &&
1114 crossesBranch == p.crossesBranch && crossesBlock == p.crossesBlock &&
1115 minInsts == p.minInsts;
1116 }
1117
1118 DepAnalysis iga::ComputeDepAnalysis(const Kernel *k) {
1119 DepAnalysis la;
1120
1121 DepAnalysisComputer lac(k, la);
1122 lac.runAnalysis();
1123
1124 TRACE("=========== END ===========");
1125 return la;
1126 }
1127
1128 #ifdef _DEBUG
1129 // to suppress compiler warning
1130 std::string IGA_DUAnalysis_ForceCodeGen_ForDebug(const void *, const void *);
1131
1132 // dummy function to force codegen of certain internal functions for debug.
1133 std::string IGA_DUAnalysis_ForceCodeGen_ForDebug(const void *plp,
1134 const void *bs) {
1135 const LivePath *lp = (const LivePath *)plp;
1136 return lp->strFull() + ((const BlockState *)bs)->idstr();
1137 }
1138 #endif //