| 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 // |