llvm/lib/Target/Hexagon/HexagonBlockRanges.cpp

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