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 #define DEBUG_TYPE "hbr"
  11
  12 #include "HexagonBlockRanges.h"
  13 #include "HexagonInstrInfo.h"
  14 #include "HexagonSubtarget.h"
  15
  16 #include "llvm/ADT/BitVector.h"
  17 #include "llvm/CodeGen/MachineBasicBlock.h"
  18 #include "llvm/CodeGen/MachineInstr.h"
  19 #include "llvm/CodeGen/MachineRegisterInfo.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetRegisterInfo.h"
  25
  26 #include <map>
  27
  28 using namespace llvm;
  29
  30 bool HexagonBlockRanges::IndexRange::overlaps(const IndexRange &A) const {
  31   // If A contains start(), or "this" contains A.start(), then overlap.
  32   IndexType S = start(), E = end(), AS = A.start(), AE = A.end();
  33   if (AS == S)
  34     return true;
  35   bool SbAE = (S < AE) || (S == AE && A.TiedEnd);  // S-before-AE.
  36   bool ASbE = (AS < E) || (AS == E && TiedEnd);    // AS-before-E.
  37   if ((AS < S && SbAE) || (S < AS && ASbE))
  38     return true;
  39   // Otherwise no overlap.
  40   return false;
  41 }
  42
  43
  44 bool HexagonBlockRanges::IndexRange::contains(const IndexRange &A) const {
  45   if (start() <= A.start()) {
  46     // Treat "None" in the range end as equal to the range start.
  47     IndexType E = (end() != IndexType::None) ? end() : start();
  48     IndexType AE = (A.end() != IndexType::None) ? A.end() : A.start();
  49     if (AE <= E)
  50       return true;
  51   }
  52   return false;
  53 }
  54
  55
  56 void HexagonBlockRanges::IndexRange::merge(const IndexRange &A) {
  57   // Allow merging adjacent ranges.
  58   assert(end() == A.start() || overlaps(A));
  59   IndexType AS = A.start(), AE = A.end();
  60   if (AS < start() || start() == IndexType::None)
  61     setStart(AS);
  62   if (end() < AE || end() == IndexType::None) {
  63     setEnd(AE);
  64     TiedEnd = A.TiedEnd;
  65   } else {
  66     if (end() == AE)
  67       TiedEnd |= A.TiedEnd;
  68   }
  69   if (A.Fixed)
  70     Fixed = true;
  71 }
  72
  73
  74 void HexagonBlockRanges::RangeList::include(const RangeList &RL) {
  75   for (auto &R : RL)
  76     if (std::find(begin(), end(), R) == end())
  77       push_back(R);
  78 }
  79
  80
  81 // Merge all overlapping ranges in the list, so that all that remains
  82 // is a list of disjoint ranges.
  83 void HexagonBlockRanges::RangeList::unionize(bool MergeAdjacent) {
  84   if (empty())
  85     return;
  86
  87   std::sort(begin(), end());
  88   iterator Iter = begin();
  89
  90   while (Iter != end()-1) {
  91     iterator Next = std::next(Iter);
  92     // If MergeAdjacent is true, merge ranges A and B, where A.end == B.start.
  93     // This allows merging dead ranges, but is not valid for live ranges.
  94     bool Merge = MergeAdjacent && (Iter->end() == Next->start());
  95     if (Merge || Iter->overlaps(*Next)) {
  96       Iter->merge(*Next);
  97       erase(Next);
  98       continue;
  99     }
 100     ++Iter;
 101   }
 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
 142 // Subtract a given range from each element in the list.
 143 void HexagonBlockRanges::RangeList::subtract(const IndexRange &Range) {
 144   // Cannot assume that the list is unionized (i.e. contains only non-
 145   // overlapping ranges.
 146   RangeList T;
 147   for (iterator Next, I = begin(); I != end(); I = Next) {
 148     IndexRange &Rg = *I;
 149     if (Rg.overlaps(Range)) {
 150       T.addsub(Rg, Range);
 151       Next = this->erase(I);
 152     } else {
 153       Next = std::next(I);
 154     }
 155   }
 156   include(T);
 157 }
 158
 159
 160 HexagonBlockRanges::InstrIndexMap::InstrIndexMap(MachineBasicBlock &B)
 161     : Block(B) {
 162   IndexType Idx = IndexType::First;
 163   First = Idx;
 164   for (auto &In : B) {
 165     if (In.isDebugValue())
 166       continue;
 167     assert(getIndex(&In) == IndexType::None && "Instruction already in map");
 168     Map.insert(std::make_pair(Idx, &In));
 169     ++Idx;
 170   }
 171   Last = B.empty() ? IndexType::None : unsigned(Idx)-1;
 172 }
 173
 174
 175 MachineInstr *HexagonBlockRanges::InstrIndexMap::getInstr(IndexType Idx) const {
 176   auto F = Map.find(Idx);
 177   return (F != Map.end()) ? F->second : 0;
 178 }
 179
 180
 181 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getIndex(
 182       MachineInstr *MI) const {
 183   for (auto &I : Map)
 184     if (I.second == MI)
 185       return I.first;
 186   return IndexType::None;
 187 }
 188
 189
 190 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getPrevIndex(
 191       IndexType Idx) const {
 192   assert (Idx != IndexType::None);
 193   if (Idx == IndexType::Entry)
 194     return IndexType::None;
 195   if (Idx == IndexType::Exit)
 196     return Last;
 197   if (Idx == First)
 198     return IndexType::Entry;
 199   return unsigned(Idx)-1;
 200 }
 201
 202
 203 HexagonBlockRanges::IndexType HexagonBlockRanges::InstrIndexMap::getNextIndex(
 204       IndexType Idx) const {
 205   assert (Idx != IndexType::None);
 206   if (Idx == IndexType::Entry)
 207     return IndexType::First;
 208   if (Idx == IndexType::Exit || Idx == Last)
 209     return IndexType::None;
 210   return unsigned(Idx)+1;
 211 }
 212
 213
 214 void HexagonBlockRanges::InstrIndexMap::replaceInstr(MachineInstr *OldMI,
 215       MachineInstr *NewMI) {
 216   for (auto &I : Map) {
 217     if (I.second != OldMI)
 218       continue;
 219     if (NewMI != nullptr)
 220       I.second = NewMI;
 221     else
 222       Map.erase(I.first);
 223     break;
 224   }
 225 }
 226
 227
 228 HexagonBlockRanges::HexagonBlockRanges(MachineFunction &mf)
 229   : MF(mf), HST(mf.getSubtarget<HexagonSubtarget>()),
 230     TII(*HST.getInstrInfo()), TRI(*HST.getRegisterInfo()),
 231     Reserved(TRI.getReservedRegs(mf)) {
 232   // Consider all non-allocatable registers as reserved.
 233   for (auto I = TRI.regclass_begin(), E = TRI.regclass_end(); I != E; ++I) {
 234     auto *RC = *I;
 235     if (RC->isAllocatable())
 236       continue;
 237     for (unsigned R : *RC)
 238       Reserved[R] = true;
 239   }
 240 }
 241
 242
 243 HexagonBlockRanges::RegisterSet HexagonBlockRanges::getLiveIns(
 244       const MachineBasicBlock &B) {
 245   RegisterSet LiveIns;
 246   for (auto I : B.liveins())
 247     if (!Reserved[I.PhysReg])
 248       LiveIns.insert({I.PhysReg, 0});
 249   return LiveIns;
 250 }
 251
 252
 253 HexagonBlockRanges::RegisterSet HexagonBlockRanges::expandToSubRegs(
 254       RegisterRef R, const MachineRegisterInfo &MRI,
 255       const TargetRegisterInfo &TRI) {
 256   RegisterSet SRs;
 257
 258   if (R.Sub != 0) {
 259     SRs.insert(R);
 260     return SRs;
 261   }
 262
 263   if (TargetRegisterInfo::isPhysicalRegister(R.Reg)) {
 264     MCSubRegIterator I(R.Reg, &TRI);
 265     if (!I.isValid())
 266       SRs.insert({R.Reg, 0});
 267     for (; I.isValid(); ++I)
 268       SRs.insert({*I, 0});
 269   } else {
 270     assert(TargetRegisterInfo::isVirtualRegister(R.Reg));
 271     auto &RC = *MRI.getRegClass(R.Reg);
 272     unsigned PReg = *RC.begin();
 273     MCSubRegIndexIterator I(PReg, &TRI);
 274     if (!I.isValid())
 275       SRs.insert({R.Reg, 0});
 276     for (; I.isValid(); ++I)
 277       SRs.insert({R.Reg, I.getSubRegIndex()});
 278   }
 279   return SRs;
 280 }
 281
 282
 283 void HexagonBlockRanges::computeInitialLiveRanges(InstrIndexMap &IndexMap,
 284       RegToRangeMap &LiveMap) {
 285   std::map<RegisterRef,IndexType> LastDef, LastUse;
 286   RegisterSet LiveOnEntry;
 287   MachineBasicBlock &B = IndexMap.getBlock();
 288   MachineRegisterInfo &MRI = B.getParent()->getRegInfo();
 289
 290   for (auto R : getLiveIns(B))
 291     for (auto S : expandToSubRegs(R, MRI, TRI))
 292       LiveOnEntry.insert(S);
 293
 294   for (auto R : LiveOnEntry)
 295     LastDef[R] = IndexType::Entry;
 296
 297   auto closeRange = [&LastUse,&LastDef,&LiveMap] (RegisterRef R) -> void {
 298     auto LD = LastDef[R], LU = LastUse[R];
 299     if (LD == IndexType::None)
 300       LD = IndexType::Entry;
 301     if (LU == IndexType::None)
 302       LU = IndexType::Exit;
 303     LiveMap[R].add(LD, LU, false, false);
 304     LastUse[R] = LastDef[R] = IndexType::None;
 305   };
 306
 307   for (auto &In : B) {
 308     if (In.isDebugValue())
 309       continue;
 310     IndexType Index = IndexMap.getIndex(&In);
 311     // Process uses first.
 312     for (auto &Op : In.operands()) {
 313       if (!Op.isReg() || !Op.isUse() || Op.isUndef())
 314         continue;
 315       RegisterRef R = { Op.getReg(), Op.getSubReg() };
 316       if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
 317         continue;
 318       bool IsKill = Op.isKill();
 319       for (auto S : expandToSubRegs(R, MRI, TRI)) {
 320         LastUse[S] = Index;
 321         if (IsKill)
 322           closeRange(S);
 323       }
 324     }
 325     // Process defs.
 326     for (auto &Op : In.operands()) {
 327       if (!Op.isReg() || !Op.isDef() || Op.isUndef())
 328         continue;
 329       RegisterRef R = { Op.getReg(), Op.getSubReg() };
 330       if (TargetRegisterInfo::isPhysicalRegister(R.Reg) && Reserved[R.Reg])
 331         continue;
 332       for (auto S : expandToSubRegs(R, MRI, TRI)) {
 333         if (LastDef[S] != IndexType::None || LastUse[S] != IndexType::None)
 334           closeRange(S);
 335         LastDef[S] = Index;
 336       }
 337     }
 338   }
 339
 340   // Collect live-on-exit.
 341   RegisterSet LiveOnExit;
 342   for (auto *SB : B.successors())
 343     for (auto R : getLiveIns(*SB))
 344       for (auto S : expandToSubRegs(R, MRI, TRI))
 345         LiveOnExit.insert(S);
 346
 347   for (auto R : LiveOnExit)
 348     LastUse[R] = IndexType::Exit;
 349
 350   // Process remaining registers.
 351   RegisterSet Left;
 352   for (auto &I : LastUse)
 353     if (I.second != IndexType::None)
 354       Left.insert(I.first);
 355   for (auto &I : LastDef)
 356     if (I.second != IndexType::None)
 357       Left.insert(I.first);
 358   for (auto R : Left)
 359     closeRange(R);
 360
 361   // Finalize the live ranges.
 362   for (auto &P : LiveMap)
 363     P.second.unionize();
 364 }
 365
 366
 367 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeLiveMap(
 368       InstrIndexMap &IndexMap) {
 369   RegToRangeMap LiveMap;
 370   DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": index map\n" << IndexMap << '\n');
 371   computeInitialLiveRanges(IndexMap, LiveMap);
 372   DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": live map\n"
 373                << PrintRangeMap(LiveMap, TRI) << '\n');
 374   return LiveMap;
 375 }
 376
 377
 378 HexagonBlockRanges::RegToRangeMap HexagonBlockRanges::computeDeadMap(
 379       InstrIndexMap &IndexMap, RegToRangeMap &LiveMap) {
 380   RegToRangeMap DeadMap;
 381
 382   auto addDeadRanges = [&IndexMap,&LiveMap,&DeadMap] (RegisterRef R) -> void {
 383     auto F = LiveMap.find(R);
 384     if (F == LiveMap.end() || F->second.empty()) {
 385       DeadMap[R].add(IndexType::Entry, IndexType::Exit, false, false);
 386       return;
 387     }
 388
 389     RangeList &RL = F->second;
 390     RangeList::iterator A = RL.begin(), Z = RL.end()-1;
 391
 392     // Try to create the initial range.
 393     if (A->start() != IndexType::Entry) {
 394       IndexType DE = IndexMap.getPrevIndex(A->start());
 395       if (DE != IndexType::Entry)
 396         DeadMap[R].add(IndexType::Entry, DE, false, false);
 397     }
 398
 399     while (A != Z) {
 400       // Creating a dead range that follows A.  Pay attention to empty
 401       // ranges (i.e. those ending with "None").
 402       IndexType AE = (A->end() == IndexType::None) ? A->start() : A->end();
 403       IndexType DS = IndexMap.getNextIndex(AE);
 404       ++A;
 405       IndexType DE = IndexMap.getPrevIndex(A->start());
 406       if (DS < DE)
 407         DeadMap[R].add(DS, DE, false, false);
 408     }
 409
 410     // Try to create the final range.
 411     if (Z->end() != IndexType::Exit) {
 412       IndexType ZE = (Z->end() == IndexType::None) ? Z->start() : Z->end();
 413       IndexType DS = IndexMap.getNextIndex(ZE);
 414       if (DS < IndexType::Exit)
 415         DeadMap[R].add(DS, IndexType::Exit, false, false);
 416     }
 417   };
 418
 419   MachineFunction &MF = *IndexMap.getBlock().getParent();
 420   auto &MRI = MF.getRegInfo();
 421   unsigned NumRegs = TRI.getNumRegs();
 422   BitVector Visited(NumRegs);
 423   for (unsigned R = 1; R < NumRegs; ++R) {
 424     for (auto S : expandToSubRegs({R,0}, MRI, TRI)) {
 425       if (Reserved[S.Reg] || Visited[S.Reg])
 426         continue;
 427       addDeadRanges(S);
 428       Visited[S.Reg] = true;
 429     }
 430   }
 431   for (auto &P : LiveMap)
 432     if (TargetRegisterInfo::isVirtualRegister(P.first.Reg))
 433       addDeadRanges(P.first);
 434
 435   DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": dead map\n"
 436                << PrintRangeMap(DeadMap, TRI) << '\n');
 437   return DeadMap;
 438 }
 439
 440 raw_ostream &llvm::operator<<(raw_ostream &OS,
 441                               HexagonBlockRanges::IndexType Idx) {
 442   if (Idx == HexagonBlockRanges::IndexType::None)
 443     return OS << '-';
 444   if (Idx == HexagonBlockRanges::IndexType::Entry)
 445     return OS << 'n';
 446   if (Idx == HexagonBlockRanges::IndexType::Exit)
 447     return OS << 'x';
 448   return OS << unsigned(Idx)-HexagonBlockRanges::IndexType::First+1;
 449 }
 450
 451 // A mapping to translate between instructions and their indices.
 452 raw_ostream &llvm::operator<<(raw_ostream &OS,
 453                               const HexagonBlockRanges::IndexRange &IR) {
 454   OS << '[' << IR.start() << ':' << IR.end() << (IR.TiedEnd ? '}' : ']');
 455   if (IR.Fixed)
 456     OS << '!';
 457   return OS;
 458 }
 459
 460 raw_ostream &llvm::operator<<(raw_ostream &OS,
 461                               const HexagonBlockRanges::RangeList &RL) {
 462   for (auto &R : RL)
 463     OS << R << " ";
 464   return OS;
 465 }
 466
 467 raw_ostream &llvm::operator<<(raw_ostream &OS,
 468                               const HexagonBlockRanges::InstrIndexMap &M) {
 469   for (auto &In : M.Block) {
 470     HexagonBlockRanges::IndexType Idx = M.getIndex(&In);
 471     OS << Idx << (Idx == M.Last ? ". " : "  ") << In;
 472   }
 473   return OS;
 474 }
 475
 476 raw_ostream &llvm::operator<<(raw_ostream &OS,
 477                               const HexagonBlockRanges::PrintRangeMap &P) {
 478   for (auto &I : P.Map) {
 479     const HexagonBlockRanges::RangeList &RL = I.second;
 480     OS << PrintReg(I.first.Reg, &P.TRI, I.first.Sub) << " -> " << RL << "\n";
 481   }
 482   return OS;
 483 }