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 /// GenXLiveness 11 /// ------------ 12 /// 13 /// GenXLiveness is an analysis that contains the liveness information for the 14 /// values in the code. Unlike the usual LLVM liveness analysis, the values 15 /// are in LLVM IR rather than machine IR. 16 /// 17 /// This GenXLiveness pass is a container for the data structures required 18 /// for liveness analysis, plus methods to perform the analysis. The pass itself 19 /// does nothing; later passes manipulate it: 20 /// 21 /// * GenXCategory creates a LiveRange and sets the category on it for each 22 /// value. 23 /// 24 /// * GenXLiveRanges calls GenXLiveness to set up the LiveRange for each 25 /// value that needs one (a non-baled instruction or a function argument), 26 /// and erases the LiveRange for a value that does not need one (a baled 27 /// in instruction). 28 /// 29 /// GenXLiveness is a FunctionGroupWrapperPass, because we want to share 30 /// liveness information between all the Functions in a FunctionGroup (i.e. 31 /// between a GenX kernel/function and its subroutines). Any pass that uses 32 /// GenXLiveness, which is almost all passes that run after it, must itself be a 33 /// FunctionGroupWrapperPass. 34 /// 35 /// Here is what a LiveRange might look like if you dump() it in the debugger, 36 /// or see it as part of the liveness info in a -print-after-all: 37 /// 38 /// ``add12.split48172:[145,199){general,align32}`` 39 /// 40 /// * ``add12.split48172`` is the Value attached to the LiveRange. As outlined 41 /// below, 42 /// a LiveRange actually has SimpleValues rather than Values; if the attached 43 /// SimpleValue had been an element of a struct rather than a scalar value in 44 /// its own right, the name would have had # then the flattened index 45 /// appended. 46 /// 47 /// * A LiveRange can have more than one value attached after GenXCoalescing. 48 /// This would be shown by multiple comma-separated names. 49 /// 50 /// * ``[145,199)`` is the segment in which the LiveRange is live. A LiveRange 51 /// can 52 /// have multiple segments. This one is a normal (strong) segment; a weak one 53 /// has the start number prefixed with 'w' and a phicpy one has the start 54 /// number prefixed with 'ph'. 55 /// 56 /// * ``general`` is the register category of the LiveRange. 57 /// 58 /// * ``align32`` shows that the LiveRange has been marked as needing to be 32 59 /// byte (i.e. GRF) aligned. 60 /// 61 /// * If the LiveRange was a kernel argument, its allocated offset would have 62 /// been shown with the word 'offset'. 63 /// 64 /// SimpleValue 65 /// ^^^^^^^^^^^ 66 /// 67 /// Liveness information deals with SimpleValues rather than Values. 68 /// SimpleValue (a GenX backend specific class) is the entity that can have 69 /// a live range attached and a register allocated. A SimpleValue is either a 70 /// non-struct Value, or a non-struct element of a struct Value (where the 71 /// struct can contain nested structs). 72 /// 73 /// A SimpleValue is represented by a pair: 74 /// 75 /// - a Value * 76 /// - a flattened index for a non-struct element of a struct, otherwise 0 77 /// 78 /// Having a flattened index (as generated by IndexFlattener::flatten()) allows 79 /// us to encode an element in multiply nested structs with a single index. 80 /// 81 /// The idea of SimpleValue is that, where the LLVM IR contains a struct value, 82 /// which is unavoidable when a function has multiple return values, we want 83 /// to allocate a register to each non-struct element, not the whole struct. 84 /// 85 /// Segments 86 /// ^^^^^^^^ 87 /// 88 /// A live range consists of one or more non-overlapping *segments*, where each 89 /// segment has a start (inclusive) and end (exclusive) instruction number, and 90 /// a strength, which is strong (normal), weak (see below) or phicpy (see 91 /// below). Two segments cannot be abutting if they have the same strength. 92 /// Later passes can interrogate this information to find out whether two live 93 /// ranges interfere, and can modify it by coalescing (merging) two live ranges. 94 /// After coalescing, multiple SimpleValues share the same live range. 95 /// 96 /// The numbering of instructions is handled in GenXNumbering. 97 /// 98 /// Weak liveness 99 /// ^^^^^^^^^^^^^ 100 /// 101 /// A live range that extends over a call has the entire range of the called 102 /// subroutine, and any subroutines it can call, added to it. This makes that 103 /// live range interfere with any live range inside the subroutine, and thus 104 /// stops them using the same register. 105 /// 106 /// However, because a subroutine has a single range in instruction numbering, 107 /// rather than one range per call site, this scheme means that two values A 108 /// and B that are live over two *different* call sites of the same subroutine 109 /// both include the subroutine's range, and thus look like they interfere. 110 /// This could stop A and B being coalesced, and thus add extra code and 111 /// register pressure. 112 /// 113 /// To fix this, we have the concept of *weak liveness*. The values A and B 114 /// are only weakly live inside the subroutine. Two values are considered to 115 /// interfere only if there is some point where both are live, and at least 116 /// one of them is not weakly live at that point. 117 /// 118 /// Thus, in our A and B example, A and B each interferes with any value inside 119 /// the subroutine, but not with each other. 120 /// 121 /// Phicpy liveness 122 /// ^^^^^^^^^^^^^^^ 123 /// 124 /// A phi node has a short segment of liveness (a *phicpy segment*) at the end 125 /// of each of its incoming blocks, from the phi copy insertion point up to the 126 /// end of the block. The use of the incoming value in the phi node is counted 127 /// as being at that phi copy insertion point. 128 /// 129 /// Normally, we split critical edges, so an incoming block to a phi node has 130 /// only the one successor, and the use of the incoming value at the phi copy 131 /// insertion point is a kill use. Often, the phi node and the incoming can be 132 /// coalesced, unless there is some interference elsewhere due to other values 133 /// previously coalesced into the two live ranges. 134 /// 135 /// However, in one case (a goto/join branching to a join), we cannot split the 136 /// critical edge. Thus the phi copy insertion point is before the conditional 137 /// branch in a block with two successors, and the incoming value is likely to 138 /// be used in the other successor too. Then, there is interference between the 139 /// phi node and the incoming value, even though they could be coalesced. 140 /// 141 /// To avoid this problem, each phicpy segment in a live range is marked as 142 /// such. A phicpy segment is valid only if there is no segment abutting it 143 /// before; if there is an abutting before segment, the coalescing code turns it 144 /// into a normal strong segment and merges the two together. 145 /// 146 /// Then, interference between two live ranges LR1 and LR2 is ignored if: 147 /// 148 /// 1. the interference arises between a phicpy segment in LR1 and a normal 149 /// (strong) segment in LR2; and 150 /// 151 /// 2. the start of the phicpy segment is the phi copy insertion point where the 152 /// phi node is in LR1 and the incoming value is in LR2. 153 /// 154 /// This then allows the incoming value and the phi node to be coalesced, even 155 /// if the incoming value is also used in the branch's other successor. 156 /// 157 //===----------------------------------------------------------------------===// 158 #ifndef GENXLIVENESS_H 159 #define GENXLIVENESS_H 160 161 #include "FunctionGroup.h" 162 #include "GenXSubtarget.h" 163 #include "IgnoreRAUWValueMap.h" 164 #include "llvm/IR/DerivedTypes.h" 165 #include "llvm/IR/Value.h" 166 #include "llvm/IR/ValueHandle.h" 167 #include "llvm/ADT/Hashing.h" 168 #include "llvm/ADT/MapVector.h" 169 #include <map> 170 #include <set> 171 #include <string> 172 #include <vector> 173 #include "Probe/Assertion.h" 174 175 namespace llvm { 176 177 class BasicBlock; 178 class CastInst; 179 class CallInst; 180 class Function; 181 class FunctionPass; 182 class GenXBaling; 183 class GenXLiveness; 184 class GenXNumbering; 185 class GenXSubtarget; 186 class Instruction; 187 class PHINode; 188 class raw_ostream; 189 class ReturnInst; 190 class Value; 191 192 ModulePass *createGenXGroupPrinterPass(raw_ostream &O, 193 const std::string &Banner); 194 195 namespace genx { 196 197 class Bale; 198 199 /*********************************************************************** 200 * IndexFlattener : a class containing some (static) utility functions to 201 * convert between struct indices (as found in an extractelement instruction) 202 * and a flattened index, in which a struct containing further structs is 203 * flattened as if it is a single struct containing just the non-struct 204 * elements. 205 * 206 * SimpleValue uses this to encode and decode its flattened index. 207 * Liveness and coalescing use flattenArg and getNumArgElements to calculate 208 * live ranges for function args at the call sites. 209 */ 210 struct IndexFlattener { 211 // flatten : convert struct indices into a flattened index 212 static unsigned flatten(StructType *ST, ArrayRef<unsigned> Indices); 213 // getNumElements : get the number of non-struct elements in the flattened 214 // struct. Returns 1 if it is not a struct type, but 0 for void type. getNumElementsIndexFlattener215 static unsigned getNumElements(Type *Ty) { 216 if (auto ST = dyn_cast<StructType>(Ty)) 217 return flatten(ST, ST->getNumElements()); 218 return !Ty->isVoidTy(); 219 } 220 // unflatten : convert a flattened index back into normal struct indices 221 static unsigned unflatten(StructType *ST, unsigned Unflattened, SmallVectorImpl<unsigned> *Indices); 222 // getElementType : get type of struct element from flattened index 223 static Type *getElementType(Type *Ty, unsigned FlattenedIndex); 224 // flattenArg : flatten an arg in a function or call, i.e. calculate the 225 // total number of flattened indices used up by previous args. If all 226 // previous args are not struct type, then this just returns the arg 227 // index 228 static unsigned flattenArg(FunctionType *FT, unsigned ArgIndex); 229 // getNumArgElements : get the number of non-struct elements in all args 230 // of the function getNumArgElementsIndexFlattener231 static unsigned getNumArgElements(FunctionType *FT) { 232 return flattenArg(FT, FT->getNumParams()); 233 } 234 }; 235 236 class AssertingSV; 237 238 /*********************************************************************** 239 * SimpleValue : a non-struct value, possibly inside a struct 240 * See comment at the top of the file. 241 */ 242 class SimpleValue { 243 Value *V; 244 unsigned Index; // flattened struct index 245 public: SimpleValue()246 SimpleValue() : V(nullptr), Index(0) {} 247 // Constructor from a non-struct value SimpleValue(Value * V)248 SimpleValue(Value *V) : V(V), Index(0) {} 249 // Constructor from a struct value and an already flattened index SimpleValue(Value * V,unsigned Index)250 SimpleValue(Value *V, unsigned Index) : V(V), Index(Index) {} 251 // Constructor from a struct value and unflattened indices (as found in extractelement) SimpleValue(Value * V,ArrayRef<unsigned> Indices)252 SimpleValue(Value *V, ArrayRef<unsigned> Indices) : V(V), 253 Index(IndexFlattener::flatten(cast<StructType>(V->getType()), Indices)) {} 254 SimpleValue(const AssertingSV &); 255 // Accessors getValue()256 Value *getValue() const { return V; } getIndex()257 unsigned getIndex() const { return Index; } 258 // getType : get the type of the (element) value 259 Type *getType() const; 260 // Comparisons 261 bool operator==(SimpleValue Rhs) const { return V == Rhs.V && Index == Rhs.Index; } 262 bool operator!=(SimpleValue Rhs) const { return !(*this == Rhs); } 263 bool operator<(SimpleValue Rhs) const { 264 if (V != Rhs.V) 265 return V < Rhs.V; 266 return Index < Rhs.Index; 267 } 268 // Debug dump/print 269 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 270 void dump() const; 271 #endif 272 void print(raw_ostream &OS) const; 273 void printName(raw_ostream &OS) const; 274 }; 275 276 inline raw_ostream &operator<<(raw_ostream &OS, SimpleValue V) { 277 V.print(OS); 278 return OS; 279 } 280 281 // AssertingSV : like a SimpleValue, but contains an AssertingVH 282 class AssertingSV { 283 AssertingVH<Value> V; 284 unsigned Index = 0; 285 public: AssertingSV(SimpleValue SV)286 AssertingSV(SimpleValue SV) : V(SV.getValue()), Index(SV.getIndex()) {} get()287 SimpleValue get() const { return SimpleValue(V, Index); } getValue()288 Value *getValue() const { return V; } getIndex()289 unsigned getIndex() const { return Index; } getType()290 Type *getType() const { return get().getType(); } 291 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) dump()292 void dump() const { get().dump(); } 293 #endif print(raw_ostream & OS)294 void print(raw_ostream &OS) const { get().print(OS); } printName(raw_ostream & OS)295 void printName(raw_ostream &OS) const { get().printName(OS); } 296 }; 297 298 // Segment : a single range of instruction numbers in which a value is 299 // live 300 struct Segment { 301 enum SegmentType : unsigned char { WEAK, PHICPY, STRONG }; 302 SegmentType Strength; 303 304 private: 305 unsigned Start; 306 unsigned End; 307 public: SegmentSegment308 Segment() : Strength(STRONG), Start(0), End(0) {} 309 Segment(unsigned S, unsigned E, SegmentType Strength = STRONG) StrengthSegment310 : Strength(Strength) { 311 IGC_ASSERT(E >= S); 312 Start = S; 313 End = E; 314 } getStartSegment315 unsigned getStart() const noexcept { return Start; } setStartSegment316 void setStart(unsigned S) noexcept { 317 IGC_ASSERT(End >= S); 318 Start = S; 319 } getEndSegment320 unsigned getEnd() const noexcept{ return End; } setEndSegment321 void setEnd(unsigned E) noexcept{ 322 IGC_ASSERT(E >= Start); 323 End = E; 324 } setStartEndSegment325 void setStartEnd(unsigned S, unsigned E) noexcept{ 326 IGC_ASSERT(E >= S); 327 Start = S; 328 End = E; 329 } 330 bool operator<(Segment Rhs) const noexcept{ 331 if (Start != Rhs.Start) 332 return Start < Rhs.Start; 333 return End < Rhs.End; 334 } 335 336 // use this via std::hash<Segment> (see end of this file) hashSegment337 size_t hash() const noexcept { 338 return hash_combine(Start, End, Strength); 339 } 340 bool operator==(Segment Rhs) const noexcept{ 341 return (Start == Rhs.Start) && (End == Rhs.End) && 342 (Strength == Rhs.Strength); 343 } isWeakSegment344 bool isWeak() const noexcept{ return Strength == WEAK; } 345 }; 346 347 // LiveRange : a collection of Segment structs, in order, describing 348 // all points in the program in which a value is live. 349 // Also contains a list of each SimpleValue that points to this LiveRange. 350 // Also a bitmap of register classes (general, surface, etc) that 351 // its def and uses need. 352 class LiveRange { 353 friend class llvm::GenXLiveness; 354 typedef SmallVector<Segment, 2> Segments_t; 355 Segments_t Segments; 356 typedef SmallVector<AssertingSV, 2> Values_t; 357 Values_t Values; 358 public: 359 // kernel/stack functions that this LR spans across 360 std::set<llvm::Function*> Funcs; 361 unsigned Category :8; 362 unsigned LogAlignment :7; 363 bool DisallowCASC: 1; // disallow call arg special coalescing 364 unsigned Offset :12; // kernel arg offset, else 0 LiveRange()365 LiveRange() : Category(0), LogAlignment(0), DisallowCASC(false), Offset(0) {} 366 // Iterator forwarders for Segments 367 typedef Segments_t::iterator iterator; 368 typedef Segments_t::const_iterator const_iterator; begin()369 iterator begin() { return Segments.begin(); } end()370 iterator end() { return Segments.end(); } begin()371 const_iterator begin() const { return Segments.begin(); } end()372 const_iterator end() const { return Segments.end(); } size()373 unsigned size() const { return Segments.size(); } resize(unsigned len)374 void resize(unsigned len) { Segments.resize(len); } 375 // Iterator forwarders for Values. 376 using value_iterator = Values_t::iterator; 377 using const_value_iterator = Values_t::const_iterator; getValues()378 Values_t& getValues() { return Values; } value_begin()379 value_iterator value_begin() { return Values.begin(); } value_end()380 value_iterator value_end() { return Values.end(); } value_begin()381 const_value_iterator value_begin() const { return Values.begin(); } value_end()382 const_value_iterator value_end() const { return Values.end(); } 383 value_size()384 unsigned value_size() { return Values.size(); } value_empty()385 bool value_empty() { return Values.empty(); } 386 // find : return iterator to segment containing Num (including the case 387 // of being equal to the segment's End), or, if in a hole, the 388 // iterator of the next segment, or, if at end, end(). 389 iterator find(unsigned Num); clear()390 void clear() { Segments.clear(); Values.clear(); } push_back(Segment Seg)391 void push_back(Segment Seg) { Segments.push_back(Seg); } push_back(unsigned S,unsigned E)392 void push_back(unsigned S, unsigned E) { Segments.push_back(Segment(S, E)); } addValue(SimpleValue V)393 SimpleValue addValue(SimpleValue V) { Values.push_back(V); return V; } 394 // contains : test whether live range contains instruction number contains(unsigned Num)395 bool contains(unsigned Num) { 396 iterator i = find(Num); 397 return i != end() && i->getEnd() != Num && i->getStart() <= Num; 398 } 399 // getCategory : get the LR's register category getCategory()400 unsigned getCategory() const { return Category; } 401 // setCategory : set the LR's register category setCategory(unsigned Cat)402 void setCategory(unsigned Cat) { Category = Cat; } 403 // getOrDefaultCategory : return category; if none, set default 404 unsigned getOrDefaultCategory(); 405 // getLogAlignment : get log alignment getLogAlignment()406 unsigned getLogAlignment() const { return LogAlignment; } 407 // setAlignmentFromValue : increase alignment if necessary from a value 408 void setAlignmentFromValue(const DataLayout &DL, const SimpleValue V, 409 const unsigned GRFWidth); 410 // setLogAlignment : set log alignment to greater than implied by the LR's values setLogAlignment(unsigned Align)411 void setLogAlignment(unsigned Align) { LogAlignment = std::max(LogAlignment, Align); } 412 // addSegment : add a segment to a live range 413 void addSegment(Segment Seg); 414 // setSegmentsFrom : for this live range, clear out its segments 415 // and copy them from the other live range 416 void setSegmentsFrom(LiveRange *Other); 417 // addSegments : add segments from another LR to this one 418 void addSegments(LiveRange *LR2); 419 // sortAndMerge : after doing some push_backs, sort the segments 420 // and merge overlapping/adjacent ones 421 void sortAndMerge(); 422 // prepareFuncs : fill the Funcs set with kernel or stack functions which this 423 // LR is alive in 424 void prepareFuncs(FunctionGroupAnalysis *FGA); 425 // getLength : add up the number of instructions covered by this LR 426 unsigned getLength(bool WithWeak) const; 427 // debug dump/print 428 void dump() const; 429 void print(raw_ostream &OS, bool Detailed = false) const; 430 void printSegments(raw_ostream &OS) const; 431 private: value_clear()432 void value_clear() { Values.clear(); } 433 bool testLiveRanges() const; 434 }; 435 436 inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { 437 LR.print(OS); 438 return OS; 439 } 440 441 // CallGraph : the call graph within a FunctionGroup 442 class CallGraph { 443 FunctionGroup *FG = nullptr; 444 public: 445 class Node; 446 struct Edge { 447 unsigned Number = 0; 448 CallInst *Call = nullptr; 449 Node *Callee = nullptr; 450 bool operator==(Edge Rhs) const { return Number == Rhs.Number; } 451 bool operator!=(Edge Rhs) const { return !(*this == Rhs); } 452 bool operator<(Edge Rhs) const { return Number < Rhs.Number; } EdgeEdge453 Edge() : Number(0), Call(0) {} EdgeEdge454 Edge(unsigned Number, CallInst *Call) : Number(Number), Call(Call) {} 455 }; 456 class Node { 457 std::set<Edge> Edges; 458 public: 459 typedef std::set<Edge>::iterator iterator; begin()460 iterator begin() { return Edges.begin(); } end()461 iterator end() { return Edges.end(); } insert(Edge E)462 void insert(Edge E) { Edges.insert(E); } 463 }; 464 private: 465 std::map<Function *, Node> Nodes; 466 public: 467 // constructor from FunctionGroup CallGraph(FunctionGroup * FG)468 CallGraph(FunctionGroup *FG) : FG(FG) {} 469 // build : build the call graph from the FunctionGroup 470 void build(GenXLiveness *Liveness); 471 472 // getRoot : get the root node getRoot()473 Node *getRoot() { return &Nodes[FG->getHead()]; } 474 // getNode : get the node for a Function getNode(Function * F)475 Node *getNode(Function *F) { return &Nodes[F]; } 476 }; 477 478 } // end namespace genx 479 480 class GenXLiveness : public FGPassImplInterface, public IDMixin<GenXLiveness> { 481 FunctionGroup *FG = nullptr; 482 using LiveRangeMap_t = std::map<genx::SimpleValue, genx::LiveRange *>; 483 LiveRangeMap_t LiveRangeMap; 484 std::unique_ptr<genx::CallGraph> CG; 485 GenXBaling *Baling = nullptr; 486 GenXNumbering *Numbering = nullptr; 487 const GenXSubtarget *Subtarget = nullptr; 488 const DataLayout *DL = nullptr; 489 std::map<Function *, Value *> UnifiedRets; 490 std::map<Value *, Function *> UnifiedRetToFunc; 491 std::map<AssertingVH<Value>, Value *> ArgAddressBaseMap; 492 // Flipped ArgAddressBaseMap. Mulpimap is chosen because the same base may be 493 // used for different convert.addr instructions. 494 std::multimap<Value *, Value *> BaseToArgAddrMap; 495 496 bool CoalescingDisabled = false; 497 498 public: 499 static void getAnalysisUsage(AnalysisUsage &Info); getPassName()500 static StringRef getPassName() { return "GenX liveness analysis"; } 501 ~GenXLiveness()502 ~GenXLiveness() { releaseMemory(); } 503 bool runOnFunctionGroup(FunctionGroup &FG) override; 504 // setBaling : tell GenXLiveness where GenXBaling is setBaling(GenXBaling * B)505 void setBaling(GenXBaling *B) { Baling = B; } 506 // experimental option to extend all LR till the end of a function setNoCoalescingMode(bool NoCoalescingMode)507 void setNoCoalescingMode(bool NoCoalescingMode) { 508 CoalescingDisabled = NoCoalescingMode; 509 } 510 // Iterator forwarders. 511 // This gives you an iterator of LiveRangeMap. The ->first field is the 512 // value, and you only get each value once. The ->second field is the 513 // LiveRange pointer, and you may get each one multiple times because 514 // a live range may contain multiple values. 515 typedef LiveRangeMap_t::iterator iterator; 516 typedef LiveRangeMap_t::const_iterator const_iterator; begin()517 iterator begin() { return LiveRangeMap.begin(); } end()518 iterator end() { return LiveRangeMap.end(); } begin()519 const_iterator begin() const { return LiveRangeMap.begin(); } end()520 const_iterator end() const { return LiveRangeMap.end(); } 521 // getLiveRange : get the live range for a Value of non-struct type getLiveRange(Value * V)522 genx::LiveRange *getLiveRange(Value *V) { return getLiveRange(genx::SimpleValue(V)); } 523 // getLiveRange : get the live range for a genx::SimpleValue 524 genx::LiveRange *getLiveRange(genx::SimpleValue V); 525 // getLiveRangeOrNull : get the live range for a Value, or 0 if none 526 genx::LiveRange *getLiveRangeOrNull(genx::SimpleValue V); 527 const genx::LiveRange *getLiveRangeOrNull(genx::SimpleValue V) const; 528 // getOrCreateLiveRange : get the live range for a Value, or create 529 // a new one if none 530 genx::LiveRange *getOrCreateLiveRange(genx::SimpleValue V); 531 genx::LiveRange *getOrCreateLiveRange(genx::SimpleValue V, unsigned Cat, unsigned LogAlign); 532 // eraseLiveRange : get rid of live range for a Value, possibly multiple 533 // ones if it is a struct value 534 void eraseLiveRange(Value *V); 535 // eraseLiveRange : get rid of live range for a SimpleValue, if any. 536 // It is assumed that the LiveRange (if any) has no other value atached. 537 void eraseLiveRange(genx::SimpleValue V); 538 // eraseLiveRange : get rid of the specified live range, and remove its 539 // values from the map 540 void eraseLiveRange(genx::LiveRange *LR); 541 // twoAddrInterfere : check whether two live ranges interfere, allowing for single number interference sites at two address ops 542 bool twoAddrInterfere(genx::LiveRange *LR1, genx::LiveRange *LR2); 543 // interfere : test whether two live ranges interfere 544 bool interfere(genx::LiveRange *LR1, genx::LiveRange *LR2); 545 // getSingleInterferenceSites : check whether two live ranges interfere, returning single number interference sites 546 bool getSingleInterferenceSites(genx::LiveRange *LR1, genx::LiveRange *LR2, SmallVectorImpl<unsigned> *Sites); 547 // checkIfOverlappingSegmentsInterfere : given two segments that have been 548 // shown to overlap, check whether their strengths make them interfere 549 bool checkIfOverlappingSegmentsInterfere(genx::LiveRange *LR1, genx::Segment *S1, genx::LiveRange *LR2, genx::Segment *S2); 550 // coalesce : coalesce two live ranges 551 genx::LiveRange *coalesce(genx::LiveRange *LR1, genx::LiveRange *LR2, bool DisallowCASC); 552 // Set the GenXNumbering pointer for use by live range building setNumbering(GenXNumbering * N)553 void setNumbering(GenXNumbering *N) { Numbering = N; } getNumbering()554 GenXNumbering *getNumbering() { return Numbering; } 555 // rebuildCallGraph : rebuild GenXLiveness's call graph 556 void rebuildCallGraph(); 557 // buildSubroutineLRs : build an LR for each subroutine. Must be called 558 // before the first BuildLiveRange 559 void buildSubroutineLRs(); 560 // buildLiveRange : build live range for given value if it is simple, 561 // or one for each flattened index if it is struct type 562 void buildLiveRange(Value *V); 563 // buildLiveRange : build live range for given value 564 genx::LiveRange *buildLiveRange(genx::SimpleValue V); 565 // rebuildLiveRange : rebuild a live range that only has one value 566 void rebuildLiveRange(genx::LiveRange *LR); 567 // removeBale : remove the bale from its live range, and delete the range if 568 // it now has no values. 569 void removeBale(genx::Bale &B); 570 // removeValue : remove the value from its live range, and delete the 571 // range if it now has no values 572 void removeValue(Value *V); 573 void removeValue(genx::SimpleValue V); 574 // removeValue : remove the value from its live range. Do not delete the 575 // LR if it now has no values. 576 genx::LiveRange *removeValueNoDelete(genx::SimpleValue V); 577 // removeValuesNoDelete : remove all values from the live range, but do not 578 // delete the LR 579 void removeValuesNoDelete(genx::LiveRange *LR); 580 // replaceValue : update liveness such that NewVal has OldVal's live range, 581 // and OldVal does not have one at all. 582 void replaceValue(Value *OldVal, Value *NewVal); 583 void replaceValue(genx::SimpleValue OldVal, genx::SimpleValue(NewVal)); 584 // Set the LiveRange for a value in the map 585 void setLiveRange(genx::SimpleValue V, genx::LiveRange *LR); 586 // Get/create the unified return value for a function 587 Value *getUnifiedRet(Function *F); 588 Value *createUnifiedRet(Function *F); 589 Value *getUnifiedRetIfExist(Function *F) const; 590 // Test whether a value is a unified return value (and return its Function). 591 Function *isUnifiedRet(Value *V); 592 // Move unified return value from OldF to NewF. 593 void moveUnifiedRet(Function *OldF, Function *NewF); 594 // copyInterfere : test whether two live ranges copy-interfere 595 bool copyInterfere(genx::LiveRange *LR1, genx::LiveRange *LR2); 596 // See if V1 is a phi node and V2 wraps round to a phi use in the same BB after V1's def 597 static bool wrapsAround(Value *V1, Value *V2); 598 // Insert a copy of a non-struct value. 599 Instruction *insertCopy(Value *InputVal, genx::LiveRange *LR, 600 Instruction *InsertBefore, const Twine &Name, 601 unsigned Number, const GenXSubtarget *ST); 602 // eraseUnusedTree : erase unused tree of instructions, and remove from GenXLiveness 603 void eraseUnusedTree(Instruction *Inst); 604 // setArgAddressBase : set the base value of an argument indirect address 605 void setArgAddressBase(Value *Addr, Value *Base); 606 // getAddressBase : get the base register of an address 607 Value *getAddressBase(Value *Addr); 608 // getAddressWithBase : get addresses that base register is a Base 609 std::vector<Value *> getAddressWithBase(Value *Base); 610 // isNoopCastCoalesced : see if the no-op cast has been coalesced away 611 bool isNoopCastCoalesced(CastInst *CI); 612 // Debug dump 613 void dump(); 614 void print(raw_ostream &OS, 615 const FunctionGroup *dummy = nullptr) const override; 616 void releaseMemory() override; 617 618 private: 619 unsigned numberInstructionsInFunc(Function *Func, unsigned Num); 620 unsigned getPhiOffset(PHINode *Phi) const; 621 void rebuildLiveRangeForValue(genx::LiveRange *LR, genx::SimpleValue SV); 622 genx::LiveRange *visitPropagateSLRs(Function *F); 623 void merge(genx::LiveRange *LR1, genx::LiveRange *LR2); 624 void printValueLiveness(Value *V, raw_ostream &OS) const; 625 }; 626 using GenXLivenessWrapper = FunctionGroupWrapperPass<GenXLiveness>; 627 628 void initializeGenXLivenessWrapperPass(PassRegistry &); 629 630 // Specialize DenseMapInfo for SimpleValue. 631 template <> struct DenseMapInfo<genx::SimpleValue> { 632 static inline genx::SimpleValue getEmptyKey() { 633 return genx::SimpleValue(DenseMapInfo<Value *>::getEmptyKey()); 634 } 635 static inline genx::SimpleValue getTombstoneKey() { 636 return genx::SimpleValue(DenseMapInfo<Value *>::getTombstoneKey()); 637 } 638 static unsigned getHashValue(const genx::SimpleValue &SV) { 639 return DenseMapInfo<Value *>::getHashValue(SV.getValue()) ^ 640 DenseMapInfo<unsigned>::getHashValue(SV.getIndex()); 641 } 642 static bool isEqual(const genx::SimpleValue &LHS, 643 const genx::SimpleValue &RHS) { 644 return LHS == RHS; 645 } 646 }; 647 648 } // end namespace llvm 649 namespace std { 650 template <> struct hash<llvm::genx::Segment> { 651 size_t operator()(llvm::genx::Segment const &x) const noexcept { 652 return x.hash(); 653 } 654 }; 655 } // end namespace std 656 #endif // GENXLIVENESS_H 657