llvm/lib/CodeGen/LiveVariables.cpp

   1 //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===//
   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 // This file implements the LiveVariable analysis pass.  For each machine
  10 // instruction in the function, this pass calculates the set of registers that
  11 // are immediately dead after the instruction (i.e., the instruction calculates
  12 // the value, but it is never used) and the set of registers that are used by
  13 // the instruction, but are never used after the instruction (i.e., they are
  14 // killed).
  15 //
  16 // This class computes live variables using a sparse implementation based on
  17 // the machine code SSA form.  This class computes live variable information for
  18 // each virtual and _register allocatable_ physical register in a function.  It
  19 // uses the dominance properties of SSA form to efficiently compute live
  20 // variables for virtual registers, and assumes that physical registers are only
  21 // live within a single basic block (allowing it to do a single local analysis
  22 // to resolve physical register lifetimes in each basic block).  If a physical
  23 // register is not register allocatable, it is not tracked.  This is useful for
  24 // things like the stack pointer and condition codes.
  25 //
  26 //===----------------------------------------------------------------------===//
  27
  28 #include "llvm/CodeGen/LiveVariables.h"
  29 #include "llvm/ADT/DenseSet.h"
  30 #include "llvm/ADT/DepthFirstIterator.h"
  31 #include "llvm/ADT/STLExtras.h"
  32 #include "llvm/ADT/SmallPtrSet.h"
  33 #include "llvm/ADT/SmallSet.h"
  34 #include "llvm/CodeGen/MachineInstr.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/Config/llvm-config.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/ErrorHandling.h"
  40 #include "llvm/Support/raw_ostream.h"
  41 #include <algorithm>
  42 using namespace llvm;
  43
  44 AnalysisKey LiveVariablesAnalysis::Key;
  45
  46 LiveVariablesAnalysis::Result
  47 LiveVariablesAnalysis::run(MachineFunction &MF,
  48                            MachineFunctionAnalysisManager &) {
  49   return Result(MF);
  50 }
  51
  52 PreservedAnalyses
  53 LiveVariablesPrinterPass::run(MachineFunction &MF,
  54                               MachineFunctionAnalysisManager &MFAM) {
  55   OS << "Live variables in machine function: " << MF.getName() << '\n';
  56   MFAM.getResult<LiveVariablesAnalysis>(MF).print(OS);
  57   return PreservedAnalyses::all();
  58 }
  59
  60 char LiveVariablesWrapperPass::ID = 0;
  61 char &llvm::LiveVariablesID = LiveVariablesWrapperPass::ID;
  62 INITIALIZE_PASS_BEGIN(LiveVariablesWrapperPass, "livevars",
  63                       "Live Variable Analysis", false, false)
  64 INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim)
  65 INITIALIZE_PASS_END(LiveVariablesWrapperPass, "livevars",
  66                     "Live Variable Analysis", false, false)
  67
  68 void LiveVariablesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
  69   AU.addRequiredID(UnreachableMachineBlockElimID);
  70   AU.setPreservesAll();
  71   MachineFunctionPass::getAnalysisUsage(AU);
  72 }
  73
  74 LiveVariables::LiveVariables(MachineFunction &MF)
  75     : MF(&MF), MRI(&MF.getRegInfo()), TRI(MF.getSubtarget().getRegisterInfo()) {
  76   analyze(MF);
  77 }
  78
  79 void LiveVariables::print(raw_ostream &OS) const {
  80   for (size_t I = 0, E = VirtRegInfo.size(); I != E; ++I) {
  81     const Register Reg = Register::index2VirtReg(I);
  82     OS << "Virtual register '%" << I << "':\n";
  83     VirtRegInfo[Reg].print(OS);
  84   }
  85 }
  86
  87 MachineInstr *
  88 LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const {
  89   for (MachineInstr *MI : Kills)
  90     if (MI->getParent() == MBB)
  91       return MI;
  92   return nullptr;
  93 }
  94
  95 void LiveVariables::VarInfo::print(raw_ostream &OS) const {
  96   OS << "  Alive in blocks: ";
  97   for (unsigned AB : AliveBlocks)
  98     OS << AB << ", ";
  99   OS << "\n  Killed by:";
 100   if (Kills.empty())
 101     OS << " No instructions.\n\n";
 102   else {
 103     for (unsigned i = 0, e = Kills.size(); i != e; ++i)
 104       OS << "\n    #" << i << ": " << *Kills[i];
 105     OS << "\n";
 106   }
 107 }
 108
 109 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 110 LLVM_DUMP_METHOD void LiveVariables::VarInfo::dump() const { print(dbgs()); }
 111 #endif
 112
 113 /// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg.
 114 LiveVariables::VarInfo &LiveVariables::getVarInfo(Register Reg) {
 115   assert(Reg.isVirtual() && "getVarInfo: not a virtual register!");
 116   VirtRegInfo.grow(Reg);
 117   return VirtRegInfo[Reg];
 118 }
 119
 120 void LiveVariables::MarkVirtRegAliveInBlock(
 121     VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *MBB,
 122     SmallVectorImpl<MachineBasicBlock *> &WorkList) {
 123   unsigned BBNum = MBB->getNumber();
 124
 125   // Check to see if this basic block is one of the killing blocks.  If so,
 126   // remove it.
 127   for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
 128     if (VRInfo.Kills[i]->getParent() == MBB) {
 129       VRInfo.Kills.erase(VRInfo.Kills.begin()+i);  // Erase entry
 130       break;
 131     }
 132
 133   if (MBB == DefBlock) return;  // Terminate recursion
 134
 135   if (VRInfo.AliveBlocks.test(BBNum))
 136     return;  // We already know the block is live
 137
 138   // Mark the variable known alive in this bb
 139   VRInfo.AliveBlocks.set(BBNum);
 140
 141   assert(MBB != &MF->front() && "Can't find reaching def for virtreg");
 142   WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend());
 143 }
 144
 145 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
 146                                             MachineBasicBlock *DefBlock,
 147                                             MachineBasicBlock *MBB) {
 148   SmallVector<MachineBasicBlock *, 16> WorkList;
 149   MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList);
 150
 151   while (!WorkList.empty()) {
 152     MachineBasicBlock *Pred = WorkList.pop_back_val();
 153     MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList);
 154   }
 155 }
 156
 157 void LiveVariables::HandleVirtRegUse(Register Reg, MachineBasicBlock *MBB,
 158                                      MachineInstr &MI) {
 159   assert(MRI->getVRegDef(Reg) && "Register use before def!");
 160
 161   unsigned BBNum = MBB->getNumber();
 162
 163   VarInfo &VRInfo = getVarInfo(Reg);
 164
 165   // Check to see if this basic block is already a kill block.
 166   if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
 167     // Yes, this register is killed in this basic block already. Increase the
 168     // live range by updating the kill instruction.
 169     VRInfo.Kills.back() = &MI;
 170     return;
 171   }
 172
 173 #ifndef NDEBUG
 174   for (MachineInstr *Kill : VRInfo.Kills)
 175     assert(Kill->getParent() != MBB && "entry should be at end!");
 176 #endif
 177
 178   // This situation can occur:
 179   //
 180   //     ,------.
 181   //     |      |
 182   //     |      v
 183   //     |   t2 = phi ... t1 ...
 184   //     |      |
 185   //     |      v
 186   //     |   t1 = ...
 187   //     |  ... = ... t1 ...
 188   //     |      |
 189   //     `------'
 190   //
 191   // where there is a use in a PHI node that's a predecessor to the defining
 192   // block. We don't want to mark all predecessors as having the value "alive"
 193   // in this case.
 194   if (MBB == MRI->getVRegDef(Reg)->getParent())
 195     return;
 196
 197   // Add a new kill entry for this basic block. If this virtual register is
 198   // already marked as alive in this basic block, that means it is alive in at
 199   // least one of the successor blocks, it's not a kill.
 200   if (!VRInfo.AliveBlocks.test(BBNum))
 201     VRInfo.Kills.push_back(&MI);
 202
 203   // Update all dominating blocks to mark them as "known live".
 204   for (MachineBasicBlock *Pred : MBB->predecessors())
 205     MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(Reg)->getParent(), Pred);
 206 }
 207
 208 void LiveVariables::HandleVirtRegDef(Register Reg, MachineInstr &MI) {
 209   VarInfo &VRInfo = getVarInfo(Reg);
 210
 211   if (VRInfo.AliveBlocks.empty())
 212     // If vr is not alive in any block, then defaults to dead.
 213     VRInfo.Kills.push_back(&MI);
 214 }
 215
 216 /// FindLastPartialDef - Return the last partial def of the specified register.
 217 /// Also returns the sub-registers that're defined by the instruction.
 218 MachineInstr *
 219 LiveVariables::FindLastPartialDef(Register Reg,
 220                                   SmallSet<unsigned, 4> &PartDefRegs) {
 221   unsigned LastDefReg = 0;
 222   unsigned LastDefDist = 0;
 223   MachineInstr *LastDef = nullptr;
 224   for (MCPhysReg SubReg : TRI->subregs(Reg)) {
 225     MachineInstr *Def = PhysRegDef[SubReg];
 226     if (!Def)
 227       continue;
 228     unsigned Dist = DistanceMap[Def];
 229     if (Dist > LastDefDist) {
 230       LastDefReg  = SubReg;
 231       LastDef     = Def;
 232       LastDefDist = Dist;
 233     }
 234   }
 235
 236   if (!LastDef)
 237     return nullptr;
 238
 239   PartDefRegs.insert(LastDefReg);
 240   for (MachineOperand &MO : LastDef->all_defs()) {
 241     if (MO.getReg() == 0)
 242       continue;
 243     Register DefReg = MO.getReg();
 244     if (TRI->isSubRegister(Reg, DefReg)) {
 245       for (MCPhysReg SubReg : TRI->subregs_inclusive(DefReg))
 246         PartDefRegs.insert(SubReg);
 247     }
 248   }
 249   return LastDef;
 250 }
 251
 252 /// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
 253 /// implicit defs to a machine instruction if there was an earlier def of its
 254 /// super-register.
 255 void LiveVariables::HandlePhysRegUse(Register Reg, MachineInstr &MI) {
 256   MachineInstr *LastDef = PhysRegDef[Reg];
 257   // If there was a previous use or a "full" def all is well.
 258   if (!LastDef && !PhysRegUse[Reg]) {
 259     // Otherwise, the last sub-register def implicitly defines this register.
 260     // e.g.
 261     // AH =
 262     // AL = ... implicit-def EAX, implicit killed AH
 263     //    = AH
 264     // ...
 265     //    = EAX
 266     // All of the sub-registers must have been defined before the use of Reg!
 267     SmallSet<unsigned, 4> PartDefRegs;
 268     MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs);
 269     // If LastPartialDef is NULL, it must be using a livein register.
 270     if (LastPartialDef) {
 271       LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
 272                                                            true/*IsImp*/));
 273       PhysRegDef[Reg] = LastPartialDef;
 274       SmallSet<unsigned, 8> Processed;
 275       for (MCPhysReg SubReg : TRI->subregs(Reg)) {
 276         if (Processed.count(SubReg))
 277           continue;
 278         if (PartDefRegs.count(SubReg))
 279           continue;
 280         // This part of Reg was defined before the last partial def. It's killed
 281         // here.
 282         LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg,
 283                                                              false/*IsDef*/,
 284                                                              true/*IsImp*/));
 285         PhysRegDef[SubReg] = LastPartialDef;
 286         for (MCPhysReg SS : TRI->subregs(SubReg))
 287           Processed.insert(SS);
 288       }
 289     }
 290   } else if (LastDef && !PhysRegUse[Reg] &&
 291              !LastDef->findRegisterDefOperand(Reg, /*TRI=*/nullptr))
 292     // Last def defines the super register, add an implicit def of reg.
 293     LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
 294                                                   true/*IsImp*/));
 295
 296   // Remember this use.
 297   for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
 298     PhysRegUse[SubReg] = &MI;
 299 }
 300
 301 /// FindLastRefOrPartRef - Return the last reference or partial reference of
 302 /// the specified register.
 303 MachineInstr *LiveVariables::FindLastRefOrPartRef(Register Reg) {
 304   MachineInstr *LastDef = PhysRegDef[Reg];
 305   MachineInstr *LastUse = PhysRegUse[Reg];
 306   if (!LastDef && !LastUse)
 307     return nullptr;
 308
 309   MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
 310   unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
 311   unsigned LastPartDefDist = 0;
 312   for (MCPhysReg SubReg : TRI->subregs(Reg)) {
 313     MachineInstr *Def = PhysRegDef[SubReg];
 314     if (Def && Def != LastDef) {
 315       // There was a def of this sub-register in between. This is a partial
 316       // def, keep track of the last one.
 317       unsigned Dist = DistanceMap[Def];
 318       if (Dist > LastPartDefDist)
 319         LastPartDefDist = Dist;
 320     } else if (MachineInstr *Use = PhysRegUse[SubReg]) {
 321       unsigned Dist = DistanceMap[Use];
 322       if (Dist > LastRefOrPartRefDist) {
 323         LastRefOrPartRefDist = Dist;
 324         LastRefOrPartRef = Use;
 325       }
 326     }
 327   }
 328
 329   return LastRefOrPartRef;
 330 }
 331
 332 bool LiveVariables::HandlePhysRegKill(Register Reg, MachineInstr *MI) {
 333   MachineInstr *LastDef = PhysRegDef[Reg];
 334   MachineInstr *LastUse = PhysRegUse[Reg];
 335   if (!LastDef && !LastUse)
 336     return false;
 337
 338   MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
 339   unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
 340   // The whole register is used.
 341   // AL =
 342   // AH =
 343   //
 344   //    = AX
 345   //    = AL, implicit killed AX
 346   // AX =
 347   //
 348   // Or whole register is defined, but not used at all.
 349   // dead AX =
 350   // ...
 351   // AX =
 352   //
 353   // Or whole register is defined, but only partly used.
 354   // dead AX = implicit-def AL
 355   //    = killed AL
 356   // AX =
 357   MachineInstr *LastPartDef = nullptr;
 358   unsigned LastPartDefDist = 0;
 359   SmallSet<unsigned, 8> PartUses;
 360   for (MCPhysReg SubReg : TRI->subregs(Reg)) {
 361     MachineInstr *Def = PhysRegDef[SubReg];
 362     if (Def && Def != LastDef) {
 363       // There was a def of this sub-register in between. This is a partial
 364       // def, keep track of the last one.
 365       unsigned Dist = DistanceMap[Def];
 366       if (Dist > LastPartDefDist) {
 367         LastPartDefDist = Dist;
 368         LastPartDef = Def;
 369       }
 370       continue;
 371     }
 372     if (MachineInstr *Use = PhysRegUse[SubReg]) {
 373       for (MCPhysReg SS : TRI->subregs_inclusive(SubReg))
 374         PartUses.insert(SS);
 375       unsigned Dist = DistanceMap[Use];
 376       if (Dist > LastRefOrPartRefDist) {
 377         LastRefOrPartRefDist = Dist;
 378         LastRefOrPartRef = Use;
 379       }
 380     }
 381   }
 382
 383   if (!PhysRegUse[Reg]) {
 384     // Partial uses. Mark register def dead and add implicit def of
 385     // sub-registers which are used.
 386     // dead EAX  = op  implicit-def AL
 387     // That is, EAX def is dead but AL def extends pass it.
 388     PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true);
 389     for (MCPhysReg SubReg : TRI->subregs(Reg)) {
 390       if (!PartUses.count(SubReg))
 391         continue;
 392       bool NeedDef = true;
 393       if (PhysRegDef[Reg] == PhysRegDef[SubReg]) {
 394         MachineOperand *MO =
 395             PhysRegDef[Reg]->findRegisterDefOperand(SubReg, /*TRI=*/nullptr);
 396         if (MO) {
 397           NeedDef = false;
 398           assert(!MO->isDead());
 399         }
 400       }
 401       if (NeedDef)
 402         PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
 403                                                  true/*IsDef*/, true/*IsImp*/));
 404       MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
 405       if (LastSubRef)
 406         LastSubRef->addRegisterKilled(SubReg, TRI, true);
 407       else {
 408         LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
 409         for (MCPhysReg SS : TRI->subregs_inclusive(SubReg))
 410           PhysRegUse[SS] = LastRefOrPartRef;
 411       }
 412       for (MCPhysReg SS : TRI->subregs(SubReg))
 413         PartUses.erase(SS);
 414     }
 415   } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) {
 416     if (LastPartDef)
 417       // The last partial def kills the register.
 418       LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
 419                                                 true/*IsImp*/, true/*IsKill*/));
 420     else {
 421       MachineOperand *MO =
 422           LastRefOrPartRef->findRegisterDefOperand(Reg, TRI, false, false);
 423       bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
 424       // If the last reference is the last def, then it's not used at all.
 425       // That is, unless we are currently processing the last reference itself.
 426       LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
 427       if (NeedEC) {
 428         // If we are adding a subreg def and the superreg def is marked early
 429         // clobber, add an early clobber marker to the subreg def.
 430         MO = LastRefOrPartRef->findRegisterDefOperand(Reg, /*TRI=*/nullptr);
 431         if (MO)
 432           MO->setIsEarlyClobber();
 433       }
 434     }
 435   } else
 436     LastRefOrPartRef->addRegisterKilled(Reg, TRI, true);
 437   return true;
 438 }
 439
 440 void LiveVariables::HandleRegMask(const MachineOperand &MO, unsigned NumRegs) {
 441   // Call HandlePhysRegKill() for all live registers clobbered by Mask.
 442   // Clobbered registers are always dead, sp there is no need to use
 443   // HandlePhysRegDef().
 444   for (unsigned Reg = 1; Reg != NumRegs; ++Reg) {
 445     // Skip dead regs.
 446     if (!PhysRegDef[Reg] && !PhysRegUse[Reg])
 447       continue;
 448     // Skip mask-preserved regs.
 449     if (!MO.clobbersPhysReg(Reg))
 450       continue;
 451     // Kill the largest clobbered super-register.
 452     // This avoids needless implicit operands.
 453     unsigned Super = Reg;
 454     for (MCPhysReg SR : TRI->superregs(Reg))
 455       if (SR < NumRegs && (PhysRegDef[SR] || PhysRegUse[SR]) &&
 456           MO.clobbersPhysReg(SR))
 457         Super = SR;
 458     HandlePhysRegKill(Super, nullptr);
 459   }
 460 }
 461
 462 void LiveVariables::HandlePhysRegDef(Register Reg, MachineInstr *MI,
 463                                      SmallVectorImpl<unsigned> &Defs) {
 464   // What parts of the register are previously defined?
 465   SmallSet<unsigned, 32> Live;
 466   if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
 467     for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg))
 468       Live.insert(SubReg);
 469   } else {
 470     for (MCPhysReg SubReg : TRI->subregs(Reg)) {
 471       // If a register isn't itself defined, but all parts that make up of it
 472       // are defined, then consider it also defined.
 473       // e.g.
 474       // AL =
 475       // AH =
 476       //    = AX
 477       if (Live.count(SubReg))
 478         continue;
 479       if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) {
 480         for (MCPhysReg SS : TRI->subregs_inclusive(SubReg))
 481           Live.insert(SS);
 482       }
 483     }
 484   }
 485
 486   // Start from the largest piece, find the last time any part of the register
 487   // is referenced.
 488   HandlePhysRegKill(Reg, MI);
 489   // Only some of the sub-registers are used.
 490   for (MCPhysReg SubReg : TRI->subregs(Reg)) {
 491     if (!Live.count(SubReg))
 492       // Skip if this sub-register isn't defined.
 493       continue;
 494     HandlePhysRegKill(SubReg, MI);
 495   }
 496
 497   if (MI)
 498     Defs.push_back(Reg);  // Remember this def.
 499 }
 500
 501 void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
 502                                       SmallVectorImpl<unsigned> &Defs) {
 503   while (!Defs.empty()) {
 504     Register Reg = Defs.pop_back_val();
 505     for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) {
 506       PhysRegDef[SubReg] = &MI;
 507       PhysRegUse[SubReg]  = nullptr;
 508     }
 509   }
 510 }
 511
 512 void LiveVariables::runOnInstr(MachineInstr &MI,
 513                                SmallVectorImpl<unsigned> &Defs,
 514                                unsigned NumRegs) {
 515   assert(!MI.isDebugOrPseudoInstr());
 516   // Process all of the operands of the instruction...
 517   unsigned NumOperandsToProcess = MI.getNumOperands();
 518
 519   // Unless it is a PHI node.  In this case, ONLY process the DEF, not any
 520   // of the uses.  They will be handled in other basic blocks.
 521   if (MI.isPHI())
 522     NumOperandsToProcess = 1;
 523
 524   // Clear kill and dead markers. LV will recompute them.
 525   SmallVector<unsigned, 4> UseRegs;
 526   SmallVector<unsigned, 4> DefRegs;
 527   SmallVector<unsigned, 1> RegMasks;
 528   for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
 529     MachineOperand &MO = MI.getOperand(i);
 530     if (MO.isRegMask()) {
 531       RegMasks.push_back(i);
 532       continue;
 533     }
 534     if (!MO.isReg() || MO.getReg() == 0)
 535       continue;
 536     Register MOReg = MO.getReg();
 537     if (MO.isUse()) {
 538       if (!(MOReg.isPhysical() && MRI->isReserved(MOReg)))
 539         MO.setIsKill(false);
 540       if (MO.readsReg())
 541         UseRegs.push_back(MOReg);
 542     } else {
 543       assert(MO.isDef());
 544       // FIXME: We should not remove any dead flags. However the MIPS RDDSP
 545       // instruction needs it at the moment: http://llvm.org/PR27116.
 546       if (MOReg.isPhysical() && !MRI->isReserved(MOReg))
 547         MO.setIsDead(false);
 548       DefRegs.push_back(MOReg);
 549     }
 550   }
 551
 552   MachineBasicBlock *MBB = MI.getParent();
 553   // Process all uses.
 554   for (unsigned MOReg : UseRegs) {
 555     if (Register::isVirtualRegister(MOReg))
 556       HandleVirtRegUse(MOReg, MBB, MI);
 557     else if (!MRI->isReserved(MOReg))
 558       HandlePhysRegUse(MOReg, MI);
 559   }
 560
 561   // Process all masked registers. (Call clobbers).
 562   for (unsigned Mask : RegMasks)
 563     HandleRegMask(MI.getOperand(Mask), NumRegs);
 564
 565   // Process all defs.
 566   for (unsigned MOReg : DefRegs) {
 567     if (Register::isVirtualRegister(MOReg))
 568       HandleVirtRegDef(MOReg, MI);
 569     else if (!MRI->isReserved(MOReg))
 570       HandlePhysRegDef(MOReg, &MI, Defs);
 571   }
 572   UpdatePhysRegDefs(MI, Defs);
 573 }
 574
 575 void LiveVariables::runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs) {
 576   // Mark live-in registers as live-in.
 577   SmallVector<unsigned, 4> Defs;
 578   for (const auto &LI : MBB->liveins()) {
 579     assert(Register::isPhysicalRegister(LI.PhysReg) &&
 580            "Cannot have a live-in virtual register!");
 581     HandlePhysRegDef(LI.PhysReg, nullptr, Defs);
 582   }
 583
 584   // Loop over all of the instructions, processing them.
 585   DistanceMap.clear();
 586   unsigned Dist = 0;
 587   for (MachineInstr &MI : *MBB) {
 588     if (MI.isDebugOrPseudoInstr())
 589       continue;
 590     DistanceMap.insert(std::make_pair(&MI, Dist++));
 591
 592     runOnInstr(MI, Defs, NumRegs);
 593   }
 594
 595   // Handle any virtual assignments from PHI nodes which might be at the
 596   // bottom of this basic block.  We check all of our successor blocks to see
 597   // if they have PHI nodes, and if so, we simulate an assignment at the end
 598   // of the current block.
 599   if (!PHIVarInfo[MBB->getNumber()].empty()) {
 600     SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()];
 601
 602     for (unsigned I : VarInfoVec)
 603       // Mark it alive only in the block we are representing.
 604       MarkVirtRegAliveInBlock(getVarInfo(I), MRI->getVRegDef(I)->getParent(),
 605                               MBB);
 606   }
 607
 608   // MachineCSE may CSE instructions which write to non-allocatable physical
 609   // registers across MBBs. Remember if any reserved register is liveout.
 610   SmallSet<unsigned, 4> LiveOuts;
 611   for (const MachineBasicBlock *SuccMBB : MBB->successors()) {
 612     if (SuccMBB->isEHPad())
 613       continue;
 614     for (const auto &LI : SuccMBB->liveins()) {
 615       if (!TRI->isInAllocatableClass(LI.PhysReg))
 616         // Ignore other live-ins, e.g. those that are live into landing pads.
 617         LiveOuts.insert(LI.PhysReg);
 618     }
 619   }
 620
 621   // Loop over PhysRegDef / PhysRegUse, killing any registers that are
 622   // available at the end of the basic block.
 623   for (unsigned i = 0; i != NumRegs; ++i)
 624     if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i))
 625       HandlePhysRegDef(i, nullptr, Defs);
 626 }
 627
 628 void LiveVariables::analyze(MachineFunction &mf) {
 629   MF = &mf;
 630   MRI = &mf.getRegInfo();
 631   TRI = MF->getSubtarget().getRegisterInfo();
 632
 633   const unsigned NumRegs = TRI->getNumSupportedRegs(mf);
 634   PhysRegDef.assign(NumRegs, nullptr);
 635   PhysRegUse.assign(NumRegs, nullptr);
 636   PHIVarInfo.resize(MF->getNumBlockIDs());
 637
 638   // FIXME: LiveIntervals will be updated to remove its dependence on
 639   // LiveVariables to improve compilation time and eliminate bizarre pass
 640   // dependencies. Until then, we can't change much in -O0.
 641   if (!MRI->isSSA())
 642     report_fatal_error("regalloc=... not currently supported with -O0");
 643
 644   analyzePHINodes(mf);
 645
 646   // Calculate live variable information in depth first order on the CFG of the
 647   // function.  This guarantees that we will see the definition of a virtual
 648   // register before its uses due to dominance properties of SSA (except for PHI
 649   // nodes, which are treated as a special case).
 650   MachineBasicBlock *Entry = &MF->front();
 651   df_iterator_default_set<MachineBasicBlock*,16> Visited;
 652
 653   for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) {
 654     runOnBlock(MBB, NumRegs);
 655
 656     PhysRegDef.assign(NumRegs, nullptr);
 657     PhysRegUse.assign(NumRegs, nullptr);
 658   }
 659
 660   // Convert and transfer the dead / killed information we have gathered into
 661   // VirtRegInfo onto MI's.
 662   for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) {
 663     const Register Reg = Register::index2VirtReg(i);
 664     for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
 665       if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg))
 666         VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
 667       else
 668         VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
 669   }
 670
 671   // Check to make sure there are no unreachable blocks in the MC CFG for the
 672   // function.  If so, it is due to a bug in the instruction selector or some
 673   // other part of the code generator if this happens.
 674 #ifndef NDEBUG
 675   for (const MachineBasicBlock &MBB : *MF)
 676     assert(Visited.contains(&MBB) && "unreachable basic block found");
 677 #endif
 678
 679   PhysRegDef.clear();
 680   PhysRegUse.clear();
 681   PHIVarInfo.clear();
 682 }
 683
 684 void LiveVariables::recomputeForSingleDefVirtReg(Register Reg) {
 685   assert(Reg.isVirtual());
 686
 687   VarInfo &VI = getVarInfo(Reg);
 688   VI.AliveBlocks.clear();
 689   VI.Kills.clear();
 690
 691   MachineInstr &DefMI = *MRI->getUniqueVRegDef(Reg);
 692   MachineBasicBlock &DefBB = *DefMI.getParent();
 693
 694   // Initialize a worklist of BBs that Reg is live-to-end of. (Here
 695   // "live-to-end" means Reg is live at the end of a block even if it is only
 696   // live because of phi uses in a successor. This is different from isLiveOut()
 697   // which does not consider phi uses.)
 698   SmallVector<MachineBasicBlock *> LiveToEndBlocks;
 699   SparseBitVector<> UseBlocks;
 700   unsigned NumRealUses = 0;
 701   for (auto &UseMO : MRI->use_nodbg_operands(Reg)) {
 702     UseMO.setIsKill(false);
 703     if (!UseMO.readsReg())
 704       continue;
 705     ++NumRealUses;
 706     MachineInstr &UseMI = *UseMO.getParent();
 707     MachineBasicBlock &UseBB = *UseMI.getParent();
 708     UseBlocks.set(UseBB.getNumber());
 709     if (UseMI.isPHI()) {
 710       // If Reg is used in a phi then it is live-to-end of the corresponding
 711       // predecessor.
 712       unsigned Idx = UseMO.getOperandNo();
 713       LiveToEndBlocks.push_back(UseMI.getOperand(Idx + 1).getMBB());
 714     } else if (&UseBB == &DefBB) {
 715       // A non-phi use in the same BB as the single def must come after the def.
 716     } else {
 717       // Otherwise Reg must be live-to-end of all predecessors.
 718       LiveToEndBlocks.append(UseBB.pred_begin(), UseBB.pred_end());
 719     }
 720   }
 721
 722   // Handle the case where all uses have been removed.
 723   if (NumRealUses == 0) {
 724     VI.Kills.push_back(&DefMI);
 725     DefMI.addRegisterDead(Reg, nullptr);
 726     return;
 727   }
 728   DefMI.clearRegisterDeads(Reg);
 729
 730   // Iterate over the worklist adding blocks to AliveBlocks.
 731   bool LiveToEndOfDefBB = false;
 732   while (!LiveToEndBlocks.empty()) {
 733     MachineBasicBlock &BB = *LiveToEndBlocks.pop_back_val();
 734     if (&BB == &DefBB) {
 735       LiveToEndOfDefBB = true;
 736       continue;
 737     }
 738     if (VI.AliveBlocks.test(BB.getNumber()))
 739       continue;
 740     VI.AliveBlocks.set(BB.getNumber());
 741     LiveToEndBlocks.append(BB.pred_begin(), BB.pred_end());
 742   }
 743
 744   // Recompute kill flags. For each block in which Reg is used but is not
 745   // live-through, find the last instruction that uses Reg. Ignore phi nodes
 746   // because they should not be included in Kills.
 747   for (unsigned UseBBNum : UseBlocks) {
 748     if (VI.AliveBlocks.test(UseBBNum))
 749       continue;
 750     MachineBasicBlock &UseBB = *MF->getBlockNumbered(UseBBNum);
 751     if (&UseBB == &DefBB && LiveToEndOfDefBB)
 752       continue;
 753     for (auto &MI : reverse(UseBB)) {
 754       if (MI.isDebugOrPseudoInstr())
 755         continue;
 756       if (MI.isPHI())
 757         break;
 758       if (MI.readsVirtualRegister(Reg)) {
 759         assert(!MI.killsRegister(Reg, /*TRI=*/nullptr));
 760         MI.addRegisterKilled(Reg, nullptr);
 761         VI.Kills.push_back(&MI);
 762         break;
 763       }
 764     }
 765   }
 766 }
 767
 768 /// replaceKillInstruction - Update register kill info by replacing a kill
 769 /// instruction with a new one.
 770 void LiveVariables::replaceKillInstruction(Register Reg, MachineInstr &OldMI,
 771                                            MachineInstr &NewMI) {
 772   VarInfo &VI = getVarInfo(Reg);
 773   std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
 774 }
 775
 776 /// removeVirtualRegistersKilled - Remove all killed info for the specified
 777 /// instruction.
 778 void LiveVariables::removeVirtualRegistersKilled(MachineInstr &MI) {
 779   for (MachineOperand &MO : MI.operands()) {
 780     if (MO.isReg() && MO.isKill()) {
 781       MO.setIsKill(false);
 782       Register Reg = MO.getReg();
 783       if (Reg.isVirtual()) {
 784         bool removed = getVarInfo(Reg).removeKill(MI);
 785         assert(removed && "kill not in register's VarInfo?");
 786         (void)removed;
 787       }
 788     }
 789   }
 790 }
 791
 792 /// analyzePHINodes - Gather information about the PHI nodes in here. In
 793 /// particular, we want to map the variable information of a virtual register
 794 /// which is used in a PHI node. We map that to the BB the vreg is coming from.
 795 ///
 796 void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
 797   for (const auto &MBB : Fn)
 798     for (const auto &BBI : MBB) {
 799       if (!BBI.isPHI())
 800         break;
 801       for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
 802         if (BBI.getOperand(i).readsReg())
 803           PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
 804             .push_back(BBI.getOperand(i).getReg());
 805     }
 806 }
 807
 808 bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB,
 809                                       Register Reg, MachineRegisterInfo &MRI) {
 810   unsigned Num = MBB.getNumber();
 811
 812   // Reg is live-through.
 813   if (AliveBlocks.test(Num))
 814     return true;
 815
 816   // Registers defined in MBB cannot be live in.
 817   const MachineInstr *Def = MRI.getVRegDef(Reg);
 818   if (Def && Def->getParent() == &MBB)
 819     return false;
 820
 821  // Reg was not defined in MBB, was it killed here?
 822   return findKill(&MBB);
 823 }
 824
 825 bool LiveVariables::isLiveOut(Register Reg, const MachineBasicBlock &MBB) {
 826   LiveVariables::VarInfo &VI = getVarInfo(Reg);
 827
 828   SmallPtrSet<const MachineBasicBlock *, 8> Kills;
 829   for (MachineInstr *MI : VI.Kills)
 830     Kills.insert(MI->getParent());
 831
 832   // Loop over all of the successors of the basic block, checking to see if
 833   // the value is either live in the block, or if it is killed in the block.
 834   for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
 835     // Is it alive in this successor?
 836     unsigned SuccIdx = SuccMBB->getNumber();
 837     if (VI.AliveBlocks.test(SuccIdx))
 838       return true;
 839     // Or is it live because there is a use in a successor that kills it?
 840     if (Kills.count(SuccMBB))
 841       return true;
 842   }
 843
 844   return false;
 845 }
 846
 847 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
 848 /// variables that are live out of DomBB will be marked as passing live through
 849 /// BB.
 850 void LiveVariables::addNewBlock(MachineBasicBlock *BB,
 851                                 MachineBasicBlock *DomBB,
 852                                 MachineBasicBlock *SuccBB) {
 853   const unsigned NumNew = BB->getNumber();
 854
 855   DenseSet<unsigned> Defs, Kills;
 856
 857   MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
 858   for (; BBI != BBE && BBI->isPHI(); ++BBI) {
 859     // Record the def of the PHI node.
 860     Defs.insert(BBI->getOperand(0).getReg());
 861
 862     // All registers used by PHI nodes in SuccBB must be live through BB.
 863     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
 864       if (BBI->getOperand(i+1).getMBB() == BB)
 865         getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
 866   }
 867
 868   // Record all vreg defs and kills of all instructions in SuccBB.
 869   for (; BBI != BBE; ++BBI) {
 870     for (const MachineOperand &Op : BBI->operands()) {
 871       if (Op.isReg() && Op.getReg().isVirtual()) {
 872         if (Op.isDef())
 873           Defs.insert(Op.getReg());
 874         else if (Op.isKill())
 875           Kills.insert(Op.getReg());
 876       }
 877     }
 878   }
 879
 880   // Update info for all live variables
 881   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 882     Register Reg = Register::index2VirtReg(i);
 883
 884     // If the Defs is defined in the successor it can't be live in BB.
 885     if (Defs.count(Reg))
 886       continue;
 887
 888     // If the register is either killed in or live through SuccBB it's also live
 889     // through BB.
 890     VarInfo &VI = getVarInfo(Reg);
 891     if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber()))
 892       VI.AliveBlocks.set(NumNew);
 893   }
 894 }
 895
 896 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
 897 /// variables that are live out of DomBB will be marked as passing live through
 898 /// BB. LiveInSets[BB] is *not* updated (because it is not needed during
 899 /// PHIElimination).
 900 void LiveVariables::addNewBlock(MachineBasicBlock *BB,
 901                                 MachineBasicBlock *DomBB,
 902                                 MachineBasicBlock *SuccBB,
 903                                 std::vector<SparseBitVector<>> &LiveInSets) {
 904   const unsigned NumNew = BB->getNumber();
 905
 906   SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()];
 907   for (unsigned R : BV) {
 908     Register VirtReg = Register::index2VirtReg(R);
 909     LiveVariables::VarInfo &VI = getVarInfo(VirtReg);
 910     VI.AliveBlocks.set(NumNew);
 911   }
 912   // All registers used by PHI nodes in SuccBB must be live through BB.
 913   for (MachineBasicBlock::iterator BBI = SuccBB->begin(),
 914          BBE = SuccBB->end();
 915        BBI != BBE && BBI->isPHI(); ++BBI) {
 916     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
 917       if (BBI->getOperand(i + 1).getMBB() == BB &&
 918           BBI->getOperand(i).readsReg())
 919         getVarInfo(BBI->getOperand(i).getReg())
 920           .AliveBlocks.set(NumNew);
 921   }
 922 }