contrib/llvm/lib/Target/Hexagon/HexagonBlockRanges.cpp

   1 //===- HexagonBlockRanges.cpp ---------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "HexagonBlockRanges.h"
  11 #include "HexagonInstrInfo.h"
  12 #include "HexagonSubtarget.h"
  13 #include "llvm/ADT/BitVector.h"
  14 #include "llvm/ADT/STLExtras.h"
  15 #include "llvm/CodeGen/MachineBasicBlock.h"
  16 #include "llvm/CodeGen/MachineFunction.h"
  17 #include "llvm/CodeGen/MachineInstr.h"
  18 #include "llvm/CodeGen/MachineOperand.h"
  19 #include "llvm/CodeGen/MachineRegisterInfo.h"
  20 #include "llvm/CodeGen/TargetRegisterInfo.h"
  21 #include "llvm/MC/MCRegisterInfo.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/raw_ostream.h"
  24 #include <algorithm>
  25 #include <cassert>
  26 #include <cstdint>
  27 #include <iterator>
  28 #include <map>
  29 #include <utility>
  30
  31 using namespace llvm;
  32
  33 #define DEBUG_TYPE "hbr"
  34
  35 bool HexagonBlockRanges::IndexRange::overlaps(const IndexRange &A) const {
  36   // If A contains start(), or "this" contains A.start(), then overlap.
  37   IndexType S = start(), E = end(), AS = A.start(), AE = A.end();
  38   if (AS == S)
  39     return true;
  40   bool SbAE = (S < AE) || (S == AE && A.TiedEnd);  // S-before-AE.
  41   bool ASbE = (AS < E) || (AS == E && TiedEnd);    // AS-before-E.
  42   if ((AS < S && SbAE) || (S < AS && ASbE))
  43     return true;
  44   // Otherwise no overlap.
  45   return false;
  46 }
  47
  48 bool HexagonBlockRanges::IndexRange::contains(const IndexRange &A) const {
  49   if (start() <= A.start()) {
  50     // Treat "None" in the range end as equal to the range start.
  51     IndexType E = (end() != IndexType::None) ? end() : start();
  52     IndexType AE = (A.end() != IndexType::None) ? A.end() : A.start();
  53     if (AE <= E)
  54       return true;
  55   }
  56   return false;
  57 }
  58
  59 void HexagonBlockRanges::IndexRange::merge(const IndexRange &A) {
  60   // Allow merging adjacent ranges.
  61   assert(end() == A.start() || overlaps(A));
  62   IndexType AS = A.start(), AE = A.end();
  63   if (AS < start() || start() == IndexType::None)
  64     setStart(AS);
  65   if (end() < AE || end() == IndexType::None) {
  66     setEnd(AE);
  67     TiedEnd = A.TiedEnd;
  68   } else {
  69     if (end() == AE)
  70       TiedEnd |= A.TiedEnd;
  71   }
  72   if (A.Fixed)
  73     Fixed = true;
  74 }
  75
  76 void HexagonBlockRanges::RangeList::include(const RangeList &RL) {
  77   for (auto &R : RL)
  78     if (!is_contained(*this, R))
  79       push_back(R);
  80 }
  81
  82 // Merge all overlapping ranges in the list, so that all that remains
  83 // is a list of disjoint ranges.
  84 void HexagonBlockRanges::RangeList::unionize(bool MergeAdjacent) {
  85   if (empty())
  86     return;
  87
  88   llvm::sort(begin(), end());
  89   iterator Iter = begin();
  90
  91   while (Iter != end()-1) {
  92     iterator Next = std::next(Iter);
  93     // If MergeAdjacent is true, merge ranges A and B, where A.end == B.start.
  94     // This allows merging dead ranges, but is not valid for live ranges.
  95     bool Merge = MergeAdjacent && (Iter->end() == Next->start());
  96     if (Merge || Iter->overlaps(*Next)) {
  97       Iter->merge(*Next);
  98       erase(Next);
  99       continue;
 100     }
 101     ++Iter;
 102   }
 103 }
 104
 105 // Compute a range A-B and add it to the list.
 106 void HexagonBlockRanges::RangeList::addsub(const IndexRange &A,
 107       const IndexRange &B) {
 108   // Exclusion of non-overlapping ranges makes some checks simpler
 109   // later in this function.
 110   if (!A.overlaps(B)) {
 111     // A - B = A.
 112     add(A);
 113     return;
 114   }
 115
 116   IndexType AS = A.start(), AE = A.end();
 117   IndexType BS = B.start(), BE = B.end();
 118
 119   // If AE is None, then A is included in B, since A and B overlap.
 120   // The result of subtraction if empty, so just return.
 121   if (AE == IndexType::None)
 122     return;
 123
 124   if (AS < BS) {
 125     // A starts before B.
 126     // AE cannot be None since A and B overlap.
 127     assert(AE != IndexType::None);
 128     // Add the part of A that extends on the "less" side of B.
 129     add(AS, BS, A.Fixed, false);
 130   }
 131
 132   if (BE < AE) {
 133     // BE cannot be Exit here.
 134     if (BE == IndexType::None)
 135       add(BS, AE, A.Fixed, false);
 136     else
 137       add(BE, AE, A.Fixed, false);
 138   }
 139 }
 140
 141 // Subtract a given range from each element in the list.
 142 void HexagonBlockRanges::RangeList::subtract(const IndexRange &Range) {
 143   // Cannot assume that the list is unionized (i.e. contains only non-
 144   // overlapping ranges.
 145   RangeList T;
 146   for (iterator Next, I = begin(); I != end(); I = Next) {
 147     IndexRange &Rg = *I;
 148     if (Rg.overlaps(Range)) {
 149       T.addsub(Rg, Range);
 150       Next = this->erase(I);
 151     } else {
 152       Next = std::next(I);
 153     }
 154   }
 155   include(T);
 156 }
 157
 158 HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B)
 159     : Block(B) {
 160   IndexType Idx = IndexType::First;
 161   First = Idx;
 162   for (auto &In : B) {
 163     if (In.isDebugInstr())
 164       continue;
 165     assert(getIndex(&In) == IndexType::None && "Instruction already in map");
 166     Map.insert(std::make_pair(Idx, &In));
 167     ++Idx;
 168   }
 169   Last = B.empty() ? IndexType::None : unsigned(Idx)-1;
 170 }
 171
 172 MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
 173   auto F = Map.find(Idx);
 174   return (F != Map.end()) ? F->second : nullptr;
 175 }
 176
 177 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex(
 178       MachineInstr *MI) const {
 179   for (auto &I : Map)
 180     if (I.second == MI)
 181       return I.first;
 182   return IndexType::None;
 183 }
 184
 185 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getPrevIndex(
 186       IndexType Idx) const {
 187   assert (Idx != IndexType::None);
 188   if (Idx == IndexType::Entry)
 189     return IndexType::None;
 190   if (Idx == IndexType::Exit)
 191     return Last;
 192   if (Idx == First)
 193     return IndexType::Entry;
 194   return unsigned(Idx)-1;
 195 }
 196
 197 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getNextIndex(
 198       IndexType Idx) const {
 199   assert (Idx != IndexType::None);
 200   if (Idx == IndexType::Entry)
 201     return IndexType::First;
 202   if (Idx == IndexType::Exit || Idx == Last)
 203     return IndexType::None;
 204   return unsigned(Idx)+1;
 205 }
 206
 207 void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI,
 208       MachineInstr *NewMI) {
 209   for (auto &I : Map) {
 210     if (I.second != OldMI)
 211       continue;
 212     if (NewMI != nullptr)
 213       I.second = NewMI;
 214     else
 215       Map.erase(I.first);
 216     break;
 217   }
 218 }
 219
 220 HexagonBlockRanges::HexagonBlockRanges(MachineFunction &mf)
 221   : MF(mf), HST(mf.getSubtarget<HexagonSubtarget>()),
 222     TII(*HST.getInstrInfo()), TRI(*HST.getRegisterInfo()),
 223     Reserved(TRI.getReservedRegs(mf)) {
 224   // Consider all non-allocatable registers as reserved.
 225   for (const TargetRegisterClass *RC : TRI.regclasses()) {
 226     if (RC->isAllocatable())
 227       continue;
 228     for (unsigned R : *RC)
 229       Reserved[R] = true;
 230   }
 231 }
 232
 233 HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns(
 234       const MachineBasicBlock &B, const MachineRegisterInfo &MRI,
 235       const TargetRegisterInfo &TRI) {
 236   RegisterSet LiveIns;
 237   RegisterSet Tmp;
 238
 239   for (auto I : B.liveins()) {
 240     MCSubRegIndexIterator S(I.PhysReg, &TRI);
 241     if (I.LaneMask.all() || (I.LaneMask.any() && !S.isValid())) {
 242       Tmp.insert({I.PhysReg, 0});
 243       continue;
 244     }
 245     for (; S.isValid(); ++S) {
 246       unsigned SI = S.getSubRegIndex();
 247       if ((I.LaneMask & TRI.getSubRegIndexLaneMask(SI)).any())
 248         Tmp.insert({S.getSubReg(), 0});
 249     }
 250   }
 251
 252   for (auto R : Tmp) {
 253     if (!Reserved[R.Reg])
 254       LiveIns.insert(R);
 255     for (auto S : expandToSubRegs(R, MRI, TRI))
 256       if (!Reserved[S.Reg])
 257         LiveIns.insert(S);
 258   }
 259   return LiveIns;
 260 }
 261
 262 HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs(
 263       RegisterRef R, const MachineRegisterInfo &MRI,
 264       const TargetRegisterInfo &TRI) {
 265   RegisterSet SRs;
 266
 267   if (R.Sub != 0) {
 268     SRs.insert(R);
 269     return SRs;
 270   }
 271
 272   if (TargetRegisterInfo::isPhysicalRegister(R.Reg)) {
 273     MCSubRegIterator I(R.Reg, &TRI);
 274     if (!I.isValid())
 275       SRs.insert({R.Reg, 0});
 276     for (; I.isValid(); ++I)
 277       SRs.insert({*I, 0});
 278   } else {
 279     assert(TargetRegisterInfo::isVirtualRegister(R.Reg));
 280     auto &RC = *MRI.getRegClass(R.Reg);
 281     unsigned PReg = *RC.begin();
 282     MCSubRegIndexIterator I(PReg, &TRI);
 283     if (!I.isValid())
 284       SRs.insert({R.Reg, 0});
 285     for (; I.isValid(); ++I)
 286       SRs.insert({R.Reg, I.getSubRegIndex()});
 287   }
 288   return SRs;
 289 }
 290
 291 void HexagonBlockRanges::computeInitialLiveRanges(InstrIndexMap &IndexMap,
 292       RegToRangeMap &LiveMap) {
 293   std::map<RegisterRef,IndexType> LastDef, LastUse;
 294   RegisterSet LiveOnEntry;
 295   MachineBasicBlock &B = IndexMap.getBlock();
 296   MachineRegisterInfo &MRI = B.getParent()->getRegInfo();
 297
 298   for (auto R : getLiveIns(B, MRI, TRI))
 299     LiveOnEntry.insert(R);
 300
 301   for (auto R : LiveOnEntry)
 302     LastDef[R] = IndexType::Entry;
 303
 304   auto closeRange = [&LastUse,&LastDef,&LiveMap] (RegisterRef R) -> void {
 305     auto LD = LastDef[R], LU = LastUse[R];
 306     if (LD == IndexType::None)
 307       LD = IndexType::Entry;
 308     if (LU == IndexType::None)
 309       LU = IndexType::Exit;
 310     LiveMap[R].add(LD, LU, false, false);
 311     LastUse[R] = LastDef[R] = IndexType::None;
 312   };
 313
 314   RegisterSet Defs, Clobbers;
 315
 316   for (auto &In : B) {
 317     if (In.isDebugInstr())
 318       continue;
 319     IndexType Index = IndexMap.getIndex(&In);
 320     // Process uses first.
 321     for (auto &Op : In.operands()) {
 322       if (!Op.isReg() || !Op.isUse() || Op.isUndef())
 323         continue;
 324       RegisterRef R = { Op.getReg(), Op.getSubReg() };
 325       if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
 326         continue;
 327       bool IsKill = Op.isKill();
 328       for (auto S : expandToSubRegs(R, MRI, TRI)) {
 329         LastUse[S] = Index;
 330         if (IsKill)
 331           closeRange(S);
 332       }
 333     }
 334     // Process defs and clobbers.
 335     Defs.clear();
 336     Clobbers.clear();
 337     for (auto &Op : In.operands()) {
 338       if (!Op.isReg() || !Op.isDef() || Op.isUndef())
 339         continue;
 340       RegisterRef R = { Op.getReg(), Op.getSubReg() };
 341       for (auto S : expandToSubRegs(R, MRI, TRI)) {
 342         if (TargetRegisterInfo::isPhysicalRegister(S.Reg) && Reserved[S.Reg])
 343           continue;
 344         if (Op.isDead())
 345           Clobbers.insert(S);
 346         else
 347           Defs.insert(S);
 348       }
 349     }
 350
 351     for (auto &Op : In.operands()) {
 352       if (!Op.isRegMask())
 353         continue;
 354       const uint32_t *BM = Op.getRegMask();
 355       for (unsigned PR = 1, N = TRI.getNumRegs(); PR != N; ++PR) {
 356         // Skip registers that have subregisters. A register is preserved
 357         // iff its bit is set in the regmask, so if R1:0 was preserved, both
 358         // R1 and R0 would also be present.
 359         if (MCSubRegIterator(PR, &TRI, false).isValid())
 360           continue;
 361         if (Reserved[PR])
 362           continue;
 363         if (BM[PR/32] & (1u << (PR%32)))
 364           continue;
 365         RegisterRef R = { PR, 0 };
 366         if (!Defs.count(R))
 367           Clobbers.insert(R);
 368       }
 369     }
 370     // Defs and clobbers can overlap, e.g.
 371     // dead %d0 = COPY %5, implicit-def %r0, implicit-def %r1
 372     for (RegisterRef R : Defs)
 373       Clobbers.erase(R);
 374
 375     // Update maps for defs.
 376     for (RegisterRef S : Defs) {
 377       // Defs should already be expanded into subregs.
 378       assert(!TargetRegisterInfo::isPhysicalRegister(S.Reg) ||
 379              !MCSubRegIterator(S.Reg, &TRI, false).isValid());
 380       if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
 381         closeRange(S);
 382       LastDef[S] = Index;
 383     }
 384     // Update maps for clobbers.
 385     for (RegisterRef S : Clobbers) {
 386       // Clobbers should already be expanded into subregs.
 387       assert(!TargetRegisterInfo::isPhysicalRegister(S.Reg) ||
 388              !MCSubRegIterator(S.Reg, &TRI, false).isValid());
 389       if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
 390         closeRange(S);
 391       // Create a single-instruction range.
 392       LastDef[S] = LastUse[S] = Index;
 393       closeRange(S);
 394     }
 395   }
 396
 397   // Collect live-on-exit.
 398   RegisterSet LiveOnExit;
 399   for (auto *SB : B.successors())
 400     for (auto R : getLiveIns(*SB, MRI, TRI))
 401       LiveOnExit.insert(R);
 402
 403   for (auto R : LiveOnExit)
 404     LastUse[R] = IndexType::Exit;
 405
 406   // Process remaining registers.
 407   RegisterSet Left;
 408   for (auto &I : LastUse)
 409     if (I.second != IndexType::None)
 410       Left.insert(I.first);
 411   for (auto &I : LastDef)
 412     if (I.second != IndexType::None)
 413       Left.insert(I.first);
 414   for (auto R : Left)
 415     closeRange(R);
 416
 417   // Finalize the live ranges.
 418   for (auto &P : LiveMap)
 419     P.second.unionize();
 420 }
 421
 422 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap(
 423       InstrIndexMap &IndexMap) {
 424   RegToRangeMap LiveMap;
 425   LLVM_DEBUG(dbgs() << __func__ << ": index map\n" << IndexMap << '\n');
 426   computeInitialLiveRanges(IndexMap, LiveMap);
 427   LLVM_DEBUG(dbgs() << __func__ << ": live map\n"
 428                     << PrintRangeMap(LiveMap, TRI) << '\n');
 429   return LiveMap;
 430 }
 431
 432 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap(
 433       InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) {
 434   RegToRangeMap DeadMap;
 435
 436   auto addDeadRanges = [&IndexMap,&LiveMap,&DeadMap] (RegisterRef R) -> void {
 437     auto F = LiveMap.find(R);
 438     if (F == LiveMap.end() || F->second.empty()) {
 439       DeadMap[R].add(IndexType::Entry, IndexType::Exit, false, false);
 440       return;
 441     }
 442
 443     RangeList &RL = F->second;
 444     RangeList::iterator A = RL.begin(), Z = RL.end()-1;
 445
 446     // Try to create the initial range.
 447     if (A->start() != IndexType::Entry) {
 448       IndexType DE = IndexMap.getPrevIndex(A->start());
 449       if (DE != IndexType::Entry)
 450         DeadMap[R].add(IndexType::Entry, DE, false, false);
 451     }
 452
 453     while (A != Z) {
 454       // Creating a dead range that follows A.  Pay attention to empty
 455       // ranges (i.e. those ending with "None").
 456       IndexType AE = (A->end() == IndexType::None) ? A->start() : A->end();
 457       IndexType DS = IndexMap.getNextIndex(AE);
 458       ++A;
 459       IndexType DE = IndexMap.getPrevIndex(A->start());
 460       if (DS < DE)
 461         DeadMap[R].add(DS, DE, false, false);
 462     }
 463
 464     // Try to create the final range.
 465     if (Z->end() != IndexType::Exit) {
 466       IndexType ZE = (Z->end() == IndexType::None) ? Z->start() : Z->end();
 467       IndexType DS = IndexMap.getNextIndex(ZE);
 468       if (DS < IndexType::Exit)
 469         DeadMap[R].add(DS, IndexType::Exit, false, false);
 470     }
 471   };
 472
 473   MachineFunction &MF = *IndexMap.getBlock().getParent();
 474   auto &MRI = MF.getRegInfo();
 475   unsigned NumRegs = TRI.getNumRegs();
 476   BitVector Visited(NumRegs);
 477   for (unsigned R = 1; R < NumRegs; ++R) {
 478     for (auto S : expandToSubRegs({R,0}, MRI, TRI)) {
 479       if (Reserved[S.Reg] || Visited[S.Reg])
 480         continue;
 481       addDeadRanges(S);
 482       Visited[S.Reg] = true;
 483     }
 484   }
 485   for (auto &P : LiveMap)
 486     if (TargetRegisterInfo::isVirtualRegister(P.first.Reg))
 487       addDeadRanges(P.first);
 488
 489   LLVM_DEBUG(dbgs() << __func__ << ": dead map\n"
 490                     << PrintRangeMap(DeadMap, TRI) << '\n');
 491   return DeadMap;
 492 }
 493
 494 raw_ostream &llvm::operator<<(raw_ostream &OS,
 495                               HexagonBlockRanges::IndexType Idx) {
 496   if (Idx == HexagonBlockRanges::IndexType::None)
 497     return OS << '-';
 498   if (Idx == HexagonBlockRanges::IndexType::Entry)
 499     return OS << 'n';
 500   if (Idx == HexagonBlockRanges::IndexType::Exit)
 501     return OS << 'x';
 502   return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1;
 503 }
 504
 505 // A mapping to translate between instructions and their indices.
 506 raw_ostream &llvm::operator<<(raw_ostream &OS,
 507                               const HexagonBlockRanges::IndexRange &IR) {
 508   OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}' : ']');
 509   if (IR.Fixed)
 510     OS << '!';
 511   return OS;
 512 }
 513
 514 raw_ostream &llvm::operator<<(raw_ostream &OS,
 515                               const HexagonBlockRanges::RangeList &RL) {
 516   for (auto &R : RL)
 517     OS << R << " ";
 518   return OS;
 519 }
 520
 521 raw_ostream &llvm::operator<<(raw_ostream &OS,
 522                               const HexagonBlockRanges::InstrIndexMap &M) {
 523   for (auto &In : M.Block) {
 524     HexagonBlockRanges::IndexType Idx = M.getIndex(&In);
 525     OS << Idx << (Idx == M.Last ? ". " : "  ") << In;
 526   }
 527   return OS;
 528 }
 529
 530 raw_ostream &llvm::operator<<(raw_ostream &OS,
 531                               const HexagonBlockRanges::PrintRangeMap &P) {
 532   for (auto &I : P.Map) {
 533     const HexagonBlockRanges::RangeList &RL = I.second;
 534     OS << printReg(I.first.Reg, &P.TRI, I.first.Sub) << " -> " << RL << "\n";
 535   }
 536   return OS;
 537 }