lib/CodeGen/LiveVariables.cpp

   1 //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LiveVariable analysis pass.  For each machine
  11 // instruction in the function, this pass calculates the set of registers that
  12 // are immediately dead after the instruction (i.e., the instruction calculates
  13 // the value, but it is never used) and the set of registers that are used by
  14 // the instruction, but are never used after the instruction (i.e., they are
  15 // killed).
  16 //
  17 // This class computes live variables using are sparse implementation based on
  18 // the machine code SSA form.  This class computes live variable information for
  19 // each virtual and _register allocatable_ physical register in a function.  It
  20 // uses the dominance properties of SSA form to efficiently compute live
  21 // variables for virtual registers, and assumes that physical registers are only
  22 // live within a single basic block (allowing it to do a single local analysis
  23 // to resolve physical register lifetimes in each basic block).  If a physical
  24 // register is not register allocatable, it is not tracked.  This is useful for
  25 // things like the stack pointer and condition codes.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #include "llvm/CodeGen/LiveVariables.h"
  30 #include "llvm/CodeGen/MachineInstr.h"
  31 #include "llvm/Target/MRegisterInfo.h"
  32 #include "llvm/Target/TargetInstrInfo.h"
  33 #include "llvm/Target/TargetMachine.h"
  34 #include "llvm/ADT/DepthFirstIterator.h"
  35 #include "llvm/ADT/STLExtras.h"
  36 #include "llvm/Config/alloca.h"
  37 #include <algorithm>
  38 using namespace llvm;
  39
  40 static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis");
  41
  42 void LiveVariables::VarInfo::dump() const {
  43   cerr << "Register Defined by: ";
  44   if (DefInst)
  45     cerr << *DefInst;
  46   else
  47     cerr << "<null>\n";
  48   cerr << "  Alive in blocks: ";
  49   for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i)
  50     if (AliveBlocks[i]) cerr << i << ", ";
  51   cerr << "\n  Killed by:";
  52   if (Kills.empty())
  53     cerr << " No instructions.\n";
  54   else {
  55     for (unsigned i = 0, e = Kills.size(); i != e; ++i)
  56       cerr << "\n    #" << i << ": " << *Kills[i];
  57     cerr << "\n";
  58   }
  59 }
  60
  61 LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) {
  62   assert(MRegisterInfo::isVirtualRegister(RegIdx) &&
  63          "getVarInfo: not a virtual register!");
  64   RegIdx -= MRegisterInfo::FirstVirtualRegister;
  65   if (RegIdx >= VirtRegInfo.size()) {
  66     if (RegIdx >= 2*VirtRegInfo.size())
  67       VirtRegInfo.resize(RegIdx*2);
  68     else
  69       VirtRegInfo.resize(2*VirtRegInfo.size());
  70   }
  71   VarInfo &VI = VirtRegInfo[RegIdx];
  72   VI.AliveBlocks.resize(MF->getNumBlockIDs());
  73   return VI;
  74 }
  75
  76 bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const {
  77   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  78     MachineOperand &MO = MI->getOperand(i);
  79     if (MO.isReg() && MO.isKill()) {
  80       if (RegInfo->regsOverlap(Reg, MO.getReg()))
  81         return true;
  82     }
  83   }
  84   return false;
  85 }
  86
  87 bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const {
  88   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  89     MachineOperand &MO = MI->getOperand(i);
  90     if (MO.isReg() && MO.isDead())
  91       if (RegInfo->regsOverlap(Reg, MO.getReg()))
  92         return true;
  93   }
  94   return false;
  95 }
  96
  97 bool LiveVariables::ModifiesRegister(MachineInstr *MI, unsigned Reg) const {
  98   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  99     MachineOperand &MO = MI->getOperand(i);
 100     if (MO.isReg() && MO.isDef()) {
 101       if (RegInfo->regsOverlap(Reg, MO.getReg()))
 102         return true;
 103     }
 104   }
 105   return false;
 106 }
 107
 108 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
 109                                             MachineBasicBlock *MBB) {
 110   unsigned BBNum = MBB->getNumber();
 111
 112   // Check to see if this basic block is one of the killing blocks.  If so,
 113   // remove it...
 114   for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
 115     if (VRInfo.Kills[i]->getParent() == MBB) {
 116       VRInfo.Kills.erase(VRInfo.Kills.begin()+i);  // Erase entry
 117       break;
 118     }
 119
 120   if (MBB == VRInfo.DefInst->getParent()) return;  // Terminate recursion
 121
 122   if (VRInfo.AliveBlocks[BBNum])
 123     return;  // We already know the block is live
 124
 125   // Mark the variable known alive in this bb
 126   VRInfo.AliveBlocks[BBNum] = true;
 127
 128   for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 129          E = MBB->pred_end(); PI != E; ++PI)
 130     MarkVirtRegAliveInBlock(VRInfo, *PI);
 131 }
 132
 133 void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB,
 134                                      MachineInstr *MI) {
 135   assert(VRInfo.DefInst && "Register use before def!");
 136
 137   VRInfo.NumUses++;
 138
 139   // Check to see if this basic block is already a kill block...
 140   if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
 141     // Yes, this register is killed in this basic block already.  Increase the
 142     // live range by updating the kill instruction.
 143     VRInfo.Kills.back() = MI;
 144     return;
 145   }
 146
 147 #ifndef NDEBUG
 148   for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
 149     assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!");
 150 #endif
 151
 152   assert(MBB != VRInfo.DefInst->getParent() &&
 153          "Should have kill for defblock!");
 154
 155   // Add a new kill entry for this basic block.
 156   // If this virtual register is already marked as alive in this basic block,
 157   // that means it is alive in at least one of the successor block, it's not
 158   // a kill.
 159   if (!VRInfo.AliveBlocks[MBB->getNumber()])
 160     VRInfo.Kills.push_back(MI);
 161
 162   // Update all dominating blocks to mark them known live.
 163   for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 164          E = MBB->pred_end(); PI != E; ++PI)
 165     MarkVirtRegAliveInBlock(VRInfo, *PI);
 166 }
 167
 168 void LiveVariables::addRegisterKilled(unsigned IncomingReg, MachineInstr *MI) {
 169   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 170     MachineOperand &MO = MI->getOperand(i);
 171     if (MO.isReg() && MO.isUse() && MO.getReg() == IncomingReg) {
 172       MO.setIsKill();
 173       break;
 174     }
 175   }
 176 }
 177
 178 void LiveVariables::addRegisterDead(unsigned IncomingReg, MachineInstr *MI) {
 179   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 180     MachineOperand &MO = MI->getOperand(i);
 181     if (MO.isReg() && MO.isDef() && MO.getReg() == IncomingReg) {
 182       MO.setIsDead();
 183       break;
 184     }
 185   }
 186 }
 187
 188 void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) {
 189   PhysRegInfo[Reg] = MI;
 190   PhysRegUsed[Reg] = true;
 191
 192   for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 193        unsigned Alias = *AliasSet; ++AliasSet) {
 194     PhysRegInfo[Alias] = MI;
 195     PhysRegUsed[Alias] = true;
 196   }
 197 }
 198
 199 void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
 200   // Does this kill a previous version of this register?
 201   if (MachineInstr *LastUse = PhysRegInfo[Reg]) {
 202     if (PhysRegUsed[Reg])
 203       addRegisterKilled(Reg, LastUse);
 204     else
 205       addRegisterDead(Reg, LastUse);
 206   }
 207   PhysRegInfo[Reg] = MI;
 208   PhysRegUsed[Reg] = false;
 209
 210   for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 211        unsigned Alias = *AliasSet; ++AliasSet) {
 212     if (MachineInstr *LastUse = PhysRegInfo[Alias]) {
 213       if (PhysRegUsed[Alias])
 214         addRegisterKilled(Alias, LastUse);
 215       else
 216         addRegisterDead(Alias, LastUse);
 217     }
 218     PhysRegInfo[Alias] = MI;
 219     PhysRegUsed[Alias] = false;
 220   }
 221 }
 222
 223 bool LiveVariables::runOnMachineFunction(MachineFunction &mf) {
 224   MF = &mf;
 225   const TargetInstrInfo &TII = *MF->getTarget().getInstrInfo();
 226   RegInfo = MF->getTarget().getRegisterInfo();
 227   assert(RegInfo && "Target doesn't have register information?");
 228
 229   ReservedRegisters = RegInfo->getReservedRegs(mf);
 230
 231   // PhysRegInfo - Keep track of which instruction was the last use of a
 232   // physical register.  This is a purely local property, because all physical
 233   // register references as presumed dead across basic blocks.
 234   //
 235   PhysRegInfo = (MachineInstr**)alloca(sizeof(MachineInstr*) *
 236                                        RegInfo->getNumRegs());
 237   PhysRegUsed = (bool*)alloca(sizeof(bool)*RegInfo->getNumRegs());
 238   std::fill(PhysRegInfo, PhysRegInfo+RegInfo->getNumRegs(), (MachineInstr*)0);
 239
 240   /// Get some space for a respectable number of registers...
 241   VirtRegInfo.resize(64);
 242
 243   analyzePHINodes(mf);
 244
 245   // Calculate live variable information in depth first order on the CFG of the
 246   // function.  This guarantees that we will see the definition of a virtual
 247   // register before its uses due to dominance properties of SSA (except for PHI
 248   // nodes, which are treated as a special case).
 249   //
 250   MachineBasicBlock *Entry = MF->begin();
 251   std::set<MachineBasicBlock*> Visited;
 252   for (df_ext_iterator<MachineBasicBlock*> DFI = df_ext_begin(Entry, Visited),
 253          E = df_ext_end(Entry, Visited); DFI != E; ++DFI) {
 254     MachineBasicBlock *MBB = *DFI;
 255
 256     // Mark live-in registers as live-in.
 257     for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(),
 258            EE = MBB->livein_end(); II != EE; ++II) {
 259       assert(MRegisterInfo::isPhysicalRegister(*II) &&
 260              "Cannot have a live-in virtual register!");
 261       HandlePhysRegDef(*II, 0);
 262     }
 263
 264     // Loop over all of the instructions, processing them.
 265     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 266          I != E; ++I) {
 267       MachineInstr *MI = I;
 268
 269       // Process all of the operands of the instruction...
 270       unsigned NumOperandsToProcess = MI->getNumOperands();
 271
 272       // Unless it is a PHI node.  In this case, ONLY process the DEF, not any
 273       // of the uses.  They will be handled in other basic blocks.
 274       if (MI->getOpcode() == TargetInstrInfo::PHI)
 275         NumOperandsToProcess = 1;
 276
 277       // Process all uses...
 278       for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
 279         MachineOperand &MO = MI->getOperand(i);
 280         if (MO.isRegister() && MO.isUse() && MO.getReg()) {
 281           if (MRegisterInfo::isVirtualRegister(MO.getReg())){
 282             HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI);
 283           } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
 284                      !ReservedRegisters[MO.getReg()]) {
 285             HandlePhysRegUse(MO.getReg(), MI);
 286           }
 287         }
 288       }
 289
 290       // Process all defs...
 291       for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
 292         MachineOperand &MO = MI->getOperand(i);
 293         if (MO.isRegister() && MO.isDef() && MO.getReg()) {
 294           if (MRegisterInfo::isVirtualRegister(MO.getReg())) {
 295             VarInfo &VRInfo = getVarInfo(MO.getReg());
 296
 297             assert(VRInfo.DefInst == 0 && "Variable multiply defined!");
 298             VRInfo.DefInst = MI;
 299             // Defaults to dead
 300             VRInfo.Kills.push_back(MI);
 301           } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
 302                      !ReservedRegisters[MO.getReg()]) {
 303             HandlePhysRegDef(MO.getReg(), MI);
 304           }
 305         }
 306       }
 307     }
 308
 309     // Handle any virtual assignments from PHI nodes which might be at the
 310     // bottom of this basic block.  We check all of our successor blocks to see
 311     // if they have PHI nodes, and if so, we simulate an assignment at the end
 312     // of the current block.
 313     if (!PHIVarInfo[MBB].empty()) {
 314       std::vector<unsigned>& VarInfoVec = PHIVarInfo[MBB];
 315
 316       for (std::vector<unsigned>::iterator I = VarInfoVec.begin(),
 317              E = VarInfoVec.end(); I != E; ++I) {
 318         VarInfo& VRInfo = getVarInfo(*I);
 319         assert(VRInfo.DefInst && "Register use before def (or no def)!");
 320
 321         // Only mark it alive only in the block we are representing.
 322         MarkVirtRegAliveInBlock(VRInfo, MBB);
 323       }
 324     }
 325
 326     // Finally, if the last instruction in the block is a return, make sure to mark
 327     // it as using all of the live-out values in the function.
 328     if (!MBB->empty() && TII.isReturn(MBB->back().getOpcode())) {
 329       MachineInstr *Ret = &MBB->back();
 330       for (MachineFunction::liveout_iterator I = MF->liveout_begin(),
 331              E = MF->liveout_end(); I != E; ++I) {
 332         assert(MRegisterInfo::isPhysicalRegister(*I) &&
 333                "Cannot have a live-in virtual register!");
 334         HandlePhysRegUse(*I, Ret);
 335         // Add live-out registers as implicit uses.
 336         Ret->addRegOperand(*I, false, true);
 337       }
 338     }
 339
 340     // Loop over PhysRegInfo, killing any registers that are available at the
 341     // end of the basic block.  This also resets the PhysRegInfo map.
 342     for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i)
 343       if (PhysRegInfo[i])
 344         HandlePhysRegDef(i, 0);
 345   }
 346
 347   // Convert and transfer the dead / killed information we have gathered into
 348   // VirtRegInfo onto MI's.
 349   //
 350   for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i)
 351     for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) {
 352       if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst)
 353         addRegisterDead(i + MRegisterInfo::FirstVirtualRegister,
 354                         VirtRegInfo[i].Kills[j]);
 355       else
 356         addRegisterKilled(i + MRegisterInfo::FirstVirtualRegister,
 357                           VirtRegInfo[i].Kills[j]);
 358     }
 359
 360   // Check to make sure there are no unreachable blocks in the MC CFG for the
 361   // function.  If so, it is due to a bug in the instruction selector or some
 362   // other part of the code generator if this happens.
 363 #ifndef NDEBUG
 364   for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i)
 365     assert(Visited.count(&*i) != 0 && "unreachable basic block found");
 366 #endif
 367
 368   PHIVarInfo.clear();
 369   return false;
 370 }
 371
 372 /// instructionChanged - When the address of an instruction changes, this
 373 /// method should be called so that live variables can update its internal
 374 /// data structures.  This removes the records for OldMI, transfering them to
 375 /// the records for NewMI.
 376 void LiveVariables::instructionChanged(MachineInstr *OldMI,
 377                                        MachineInstr *NewMI) {
 378   // If the instruction defines any virtual registers, update the VarInfo,
 379   // kill and dead information for the instruction.
 380   for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
 381     MachineOperand &MO = OldMI->getOperand(i);
 382     if (MO.isRegister() && MO.getReg() &&
 383         MRegisterInfo::isVirtualRegister(MO.getReg())) {
 384       unsigned Reg = MO.getReg();
 385       VarInfo &VI = getVarInfo(Reg);
 386       if (MO.isDef()) {
 387         if (MO.isDead()) {
 388           MO.unsetIsDead();
 389           addVirtualRegisterDead(Reg, NewMI);
 390         }
 391         // Update the defining instruction.
 392         if (VI.DefInst == OldMI)
 393           VI.DefInst = NewMI;
 394       }
 395       if (MO.isUse()) {
 396         if (MO.isKill()) {
 397           MO.unsetIsKill();
 398           addVirtualRegisterKilled(Reg, NewMI);
 399         }
 400         // If this is a kill of the value, update the VI kills list.
 401         if (VI.removeKill(OldMI))
 402           VI.Kills.push_back(NewMI);   // Yes, there was a kill of it
 403       }
 404     }
 405   }
 406 }
 407
 408 /// removeVirtualRegistersKilled - Remove all killed info for the specified
 409 /// instruction.
 410 void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) {
 411   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 412     MachineOperand &MO = MI->getOperand(i);
 413     if (MO.isReg() && MO.isKill()) {
 414       MO.unsetIsKill();
 415       unsigned Reg = MO.getReg();
 416       if (MRegisterInfo::isVirtualRegister(Reg)) {
 417         bool removed = getVarInfo(Reg).removeKill(MI);
 418         assert(removed && "kill not in register's VarInfo?");
 419       }
 420     }
 421   }
 422 }
 423
 424 /// removeVirtualRegistersDead - Remove all of the dead registers for the
 425 /// specified instruction from the live variable information.
 426 void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) {
 427   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 428     MachineOperand &MO = MI->getOperand(i);
 429     if (MO.isReg() && MO.isDead()) {
 430       MO.unsetIsDead();
 431       unsigned Reg = MO.getReg();
 432       if (MRegisterInfo::isVirtualRegister(Reg)) {
 433         bool removed = getVarInfo(Reg).removeKill(MI);
 434         assert(removed && "kill not in register's VarInfo?");
 435       }
 436     }
 437   }
 438 }
 439
 440 /// analyzePHINodes - Gather information about the PHI nodes in here. In
 441 /// particular, we want to map the variable information of a virtual
 442 /// register which is used in a PHI node. We map that to the BB the vreg is
 443 /// coming from.
 444 ///
 445 void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
 446   for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end();
 447        I != E; ++I)
 448     for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
 449          BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
 450       for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
 451         PHIVarInfo[BBI->getOperand(i + 1).getMachineBasicBlock()].
 452           push_back(BBI->getOperand(i).getReg());
 453 }