lib/CodeGen/TwoAddressInstructionPass.cpp

   1 //===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===//
   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 // This file implements the TwoAddress instruction pass which is used
  11 // by most register allocators. Two-Address instructions are rewritten
  12 // from:
  13 //
  14 //     A = B op C
  15 //
  16 // to:
  17 //
  18 //     A = B
  19 //     A op= C
  20 //
  21 // Note that if a register allocator chooses to use this pass, that it
  22 // has to be capable of handling the non-SSA nature of these rewritten
  23 // virtual registers.
  24 //
  25 // It is also worth noting that the duplicate operand of the two
  26 // address instruction is removed.
  27 //
  28 //===----------------------------------------------------------------------===//
  29
  30 #define DEBUG_TYPE "twoaddrinstr"
  31 #include "llvm/CodeGen/Passes.h"
  32 #include "llvm/Function.h"
  33 #include "llvm/CodeGen/LiveVariables.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineInstr.h"
  36 #include "llvm/CodeGen/MachineRegisterInfo.h"
  37 #include "llvm/Target/TargetRegisterInfo.h"
  38 #include "llvm/Target/TargetInstrInfo.h"
  39 #include "llvm/Target/TargetMachine.h"
  40 #include "llvm/Support/Compiler.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/ADT/BitVector.h"
  43 #include "llvm/ADT/DenseMap.h"
  44 #include "llvm/ADT/SmallPtrSet.h"
  45 #include "llvm/ADT/Statistic.h"
  46 #include "llvm/ADT/STLExtras.h"
  47 using namespace llvm;
  48
  49 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
  50 STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
  51 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
  52 STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
  53 STATISTIC(NumReMats,           "Number of instructions re-materialized");
  54
  55 namespace {
  56   class VISIBILITY_HIDDEN TwoAddressInstructionPass
  57     : public MachineFunctionPass {
  58     const TargetInstrInfo *TII;
  59     const TargetRegisterInfo *TRI;
  60     MachineRegisterInfo *MRI;
  61     LiveVariables *LV;
  62
  63     bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
  64                               unsigned Reg,
  65                               MachineBasicBlock::iterator OldPos);
  66
  67     bool isSafeToReMat(unsigned DstReg, MachineInstr *MI);
  68     bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
  69                              MachineInstr *MI, MachineInstr *DefMI,
  70                              MachineBasicBlock *MBB, unsigned Loc,
  71                              DenseMap<MachineInstr*, unsigned> &DistanceMap);
  72   public:
  73     static char ID; // Pass identification, replacement for typeid
  74     TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
  75
  76     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  77       AU.addPreserved<LiveVariables>();
  78       AU.addPreservedID(MachineLoopInfoID);
  79       AU.addPreservedID(MachineDominatorsID);
  80       AU.addPreservedID(PHIEliminationID);
  81       MachineFunctionPass::getAnalysisUsage(AU);
  82     }
  83
  84     /// runOnMachineFunction - Pass entry point.
  85     bool runOnMachineFunction(MachineFunction&);
  86   };
  87 }
  88
  89 char TwoAddressInstructionPass::ID = 0;
  90 static RegisterPass<TwoAddressInstructionPass>
  91 X("twoaddressinstruction", "Two-Address instruction pass");
  92
  93 const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
  94
  95 /// Sink3AddrInstruction - A two-address instruction has been converted to a
  96 /// three-address instruction to avoid clobbering a register. Try to sink it
  97 /// past the instruction that would kill the above mentioned register to reduce
  98 /// register pressure.
  99 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
 100                                            MachineInstr *MI, unsigned SavedReg,
 101                                            MachineBasicBlock::iterator OldPos) {
 102   // Check if it's safe to move this instruction.
 103   bool SeenStore = true; // Be conservative.
 104   if (!MI->isSafeToMove(TII, SeenStore))
 105     return false;
 106
 107   unsigned DefReg = 0;
 108   SmallSet<unsigned, 4> UseRegs;
 109
 110   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 111     const MachineOperand &MO = MI->getOperand(i);
 112     if (!MO.isRegister())
 113       continue;
 114     unsigned MOReg = MO.getReg();
 115     if (!MOReg)
 116       continue;
 117     if (MO.isUse() && MOReg != SavedReg)
 118       UseRegs.insert(MO.getReg());
 119     if (!MO.isDef())
 120       continue;
 121     if (MO.isImplicit())
 122       // Don't try to move it if it implicitly defines a register.
 123       return false;
 124     if (DefReg)
 125       // For now, don't move any instructions that define multiple registers.
 126       return false;
 127     DefReg = MO.getReg();
 128   }
 129
 130   // Find the instruction that kills SavedReg.
 131   MachineInstr *KillMI = NULL;
 132   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
 133          UE = MRI->use_end(); UI != UE; ++UI) {
 134     MachineOperand &UseMO = UI.getOperand();
 135     if (!UseMO.isKill())
 136       continue;
 137     KillMI = UseMO.getParent();
 138     break;
 139   }
 140
 141   if (!KillMI || KillMI->getParent() != MBB)
 142     return false;
 143
 144   // If any of the definitions are used by another instruction between the
 145   // position and the kill use, then it's not safe to sink it.
 146   //
 147   // FIXME: This can be sped up if there is an easy way to query whether an
 148   // instruction is before or after another instruction. Then we can use
 149   // MachineRegisterInfo def / use instead.
 150   MachineOperand *KillMO = NULL;
 151   MachineBasicBlock::iterator KillPos = KillMI;
 152   ++KillPos;
 153
 154   unsigned NumVisited = 0;
 155   for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
 156     MachineInstr *OtherMI = I;
 157     if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
 158       return false;
 159     ++NumVisited;
 160     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 161       MachineOperand &MO = OtherMI->getOperand(i);
 162       if (!MO.isRegister())
 163         continue;
 164       unsigned MOReg = MO.getReg();
 165       if (!MOReg)
 166         continue;
 167       if (DefReg == MOReg)
 168         return false;
 169
 170       if (MO.isKill()) {
 171         if (OtherMI == KillMI && MOReg == SavedReg)
 172           // Save the operand that kills the register. We want to unset the kill
 173           // marker if we can sink MI past it.
 174           KillMO = &MO;
 175         else if (UseRegs.count(MOReg))
 176           // One of the uses is killed before the destination.
 177           return false;
 178       }
 179     }
 180   }
 181
 182   // Update kill and LV information.
 183   KillMO->setIsKill(false);
 184   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
 185   KillMO->setIsKill(true);
 186
 187   if (LV) {
 188     LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
 189     VarInfo.removeKill(KillMI);
 190     VarInfo.Kills.push_back(MI);
 191   }
 192
 193   // Move instruction to its destination.
 194   MBB->remove(MI);
 195   MBB->insert(KillPos, MI);
 196
 197   ++Num3AddrSunk;
 198   return true;
 199 }
 200
 201 /// isSafeToReMat - Return true if it's safe to rematerialize the specified
 202 /// instruction which defined the specified register instead of copying it.
 203 bool
 204 TwoAddressInstructionPass::isSafeToReMat(unsigned DstReg, MachineInstr *MI) {
 205   const TargetInstrDesc &TID = MI->getDesc();
 206   if (!TID.isAsCheapAsAMove())
 207     return false;
 208   bool SawStore = false;
 209   if (!MI->isSafeToMove(TII, SawStore))
 210     return false;
 211   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 212     MachineOperand &MO = MI->getOperand(i);
 213     if (!MO.isRegister())
 214       continue;
 215     // FIXME: For now, do not remat any instruction with register operands.
 216     // Later on, we can loosen the restriction is the register operands have
 217     // not been modified between the def and use. Note, this is different from
 218     // MachineSink because the code in no longer in two-address form (at least
 219     // partially).
 220     if (MO.isUse())
 221       return false;
 222     else if (!MO.isDead() && MO.getReg() != DstReg)
 223       return false;
 224   }
 225   return true;
 226 }
 227
 228 /// isTwoAddrUse - Return true if the specified MI is using the specified
 229 /// register as a two-address operand.
 230 static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
 231   const TargetInstrDesc &TID = UseMI->getDesc();
 232   for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
 233     MachineOperand &MO = UseMI->getOperand(i);
 234     if (MO.isRegister() && MO.getReg() == Reg &&
 235         (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
 236       // Earlier use is a two-address one.
 237       return true;
 238   }
 239   return false;
 240 }
 241
 242 /// isProfitableToReMat - Return true if the heuristics determines it is likely
 243 /// to be profitable to re-materialize the definition of Reg rather than copy
 244 /// the register.
 245 bool
 246 TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
 247                                 const TargetRegisterClass *RC,
 248                                 MachineInstr *MI, MachineInstr *DefMI,
 249                                 MachineBasicBlock *MBB, unsigned Loc,
 250                                 DenseMap<MachineInstr*, unsigned> &DistanceMap){
 251   bool OtherUse = false;
 252   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
 253          UE = MRI->use_end(); UI != UE; ++UI) {
 254     MachineOperand &UseMO = UI.getOperand();
 255     if (!UseMO.isUse())
 256       continue;
 257     MachineInstr *UseMI = UseMO.getParent();
 258     MachineBasicBlock *UseMBB = UseMI->getParent();
 259     if (UseMBB == MBB) {
 260       DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
 261       if (DI != DistanceMap.end() && DI->second == Loc)
 262         continue;  // Current use.
 263       OtherUse = true;
 264       // There is at least one other use in the MBB that will clobber the
 265       // register.
 266       if (isTwoAddrUse(UseMI, Reg))
 267         return true;
 268     }
 269   }
 270
 271   // If other uses in MBB are not two-address uses, then don't remat.
 272   if (OtherUse)
 273     return false;
 274
 275   // No other uses in the same block, remat if it's defined in the same
 276   // block so it does not unnecessarily extend the live range.
 277   return MBB == DefMI->getParent();
 278 }
 279
 280 /// runOnMachineFunction - Reduce two-address instructions to two operands.
 281 ///
 282 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
 283   DOUT << "Machine Function\n";
 284   const TargetMachine &TM = MF.getTarget();
 285   MRI = &MF.getRegInfo();
 286   TII = TM.getInstrInfo();
 287   TRI = TM.getRegisterInfo();
 288   LV = getAnalysisToUpdate<LiveVariables>();
 289
 290   bool MadeChange = false;
 291
 292   DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
 293   DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
 294
 295   // ReMatRegs - Keep track of the registers whose def's are remat'ed.
 296   BitVector ReMatRegs;
 297   ReMatRegs.resize(MRI->getLastVirtReg()+1);
 298
 299   // DistanceMap - Keep track the distance of a MI from the start of the
 300   // current basic block.
 301   DenseMap<MachineInstr*, unsigned> DistanceMap;
 302
 303   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
 304        mbbi != mbbe; ++mbbi) {
 305     unsigned Dist = 0;
 306     DistanceMap.clear();
 307     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
 308          mi != me; ) {
 309       MachineBasicBlock::iterator nmi = next(mi);
 310       const TargetInstrDesc &TID = mi->getDesc();
 311       bool FirstTied = true;
 312
 313       DistanceMap.insert(std::make_pair(mi, ++Dist));
 314       for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
 315         int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
 316         if (ti == -1)
 317           continue;
 318
 319         if (FirstTied) {
 320           ++NumTwoAddressInstrs;
 321           DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
 322         }
 323
 324         FirstTied = false;
 325
 326         assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
 327                mi->getOperand(si).isUse() && "two address instruction invalid");
 328
 329         // If the two operands are the same we just remove the use
 330         // and mark the def as def&use, otherwise we have to insert a copy.
 331         if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
 332           // Rewrite:
 333           //     a = b op c
 334           // to:
 335           //     a = b
 336           //     a = a op c
 337           unsigned regA = mi->getOperand(ti).getReg();
 338           unsigned regB = mi->getOperand(si).getReg();
 339
 340           assert(TargetRegisterInfo::isVirtualRegister(regA) &&
 341                  TargetRegisterInfo::isVirtualRegister(regB) &&
 342                  "cannot update physical register live information");
 343
 344 #ifndef NDEBUG
 345           // First, verify that we don't have a use of a in the instruction (a =
 346           // b + a for example) because our transformation will not work. This
 347           // should never occur because we are in SSA form.
 348           for (unsigned i = 0; i != mi->getNumOperands(); ++i)
 349             assert((int)i == ti ||
 350                    !mi->getOperand(i).isRegister() ||
 351                    mi->getOperand(i).getReg() != regA);
 352 #endif
 353
 354           // If this instruction is not the killing user of B, see if we can
 355           // rearrange the code to make it so.  Making it the killing user will
 356           // allow us to coalesce A and B together, eliminating the copy we are
 357           // about to insert.
 358           if (!mi->killsRegister(regB)) {
 359             // If this instruction is commutative, check to see if C dies.  If
 360             // so, swap the B and C operands.  This makes the live ranges of A
 361             // and C joinable.
 362             // FIXME: This code also works for A := B op C instructions.
 363             if (TID.isCommutable() && mi->getNumOperands() >= 3) {
 364               assert(mi->getOperand(3-si).isRegister() &&
 365                      "Not a proper commutative instruction!");
 366               unsigned regC = mi->getOperand(3-si).getReg();
 367
 368               if (mi->killsRegister(regC)) {
 369                 DOUT << "2addr: COMMUTING  : " << *mi;
 370                 MachineInstr *NewMI = TII->commuteInstruction(mi);
 371
 372                 if (NewMI == 0) {
 373                   DOUT << "2addr: COMMUTING FAILED!\n";
 374                 } else {
 375                   DOUT << "2addr: COMMUTED TO: " << *NewMI;
 376                   // If the instruction changed to commute it, update livevar.
 377                   if (NewMI != mi) {
 378                     if (LV) {
 379                       // Update live variables
 380                       LV->instructionChanged(mi, NewMI);
 381                     } else {
 382                       // Update flags manually
 383                       for (unsigned i = 0, e = mi->getNumOperands();
 384                            i != e; ++i) {
 385                         MachineOperand &MO = mi->getOperand(i);
 386                         if (MO.isRegister() && MO.getReg() &&
 387                           TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
 388                           unsigned Reg = MO.getReg();
 389                           if (MO.isDef()) {
 390                             if (MO.isDead()) {
 391                               MO.setIsDead(false);
 392                               NewMI->addRegisterDead(Reg, TRI);
 393                             }
 394                           }
 395
 396                           if (MO.isKill()) {
 397                             MO.setIsKill(false);
 398                             NewMI->addRegisterKilled(Reg, TRI);
 399                           }
 400                         }
 401                       }
 402                     }
 403
 404                     mbbi->insert(mi, NewMI);           // Insert the new inst
 405                     mbbi->erase(mi);                   // Nuke the old inst.
 406                     mi = NewMI;
 407                     DistanceMap.insert(std::make_pair(NewMI, Dist));
 408                   }
 409
 410                   ++NumCommuted;
 411                   regB = regC;
 412                   goto InstructionRearranged;
 413                 }
 414               }
 415             }
 416
 417             // If this instruction is potentially convertible to a true
 418             // three-address instruction,
 419             if (TID.isConvertibleTo3Addr()) {
 420               // FIXME: This assumes there are no more operands which are tied
 421               // to another register.
 422 #ifndef NDEBUG
 423               for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
 424                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 425 #endif
 426
 427               MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, *LV);
 428               if (NewMI) {
 429                 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
 430                 DOUT << "2addr:         TO 3-ADDR: " << *NewMI;
 431                 bool Sunk = false;
 432
 433                 if (NewMI->findRegisterUseOperand(regB, false, TRI))
 434                   // FIXME: Temporary workaround. If the new instruction doesn't
 435                   // uses regB, convertToThreeAddress must have created more
 436                   // then one instruction.
 437                   Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi);
 438
 439                 mbbi->erase(mi); // Nuke the old inst.
 440
 441                 if (!Sunk) {
 442                   DistanceMap.insert(std::make_pair(NewMI, Dist));
 443                   mi = NewMI;
 444                   nmi = next(mi);
 445                 }
 446
 447                 ++NumConvertedTo3Addr;
 448                 break; // Done with this instruction.
 449               }
 450             }
 451           }
 452
 453         InstructionRearranged:
 454           const TargetRegisterClass* rc = MRI->getRegClass(regA);
 455           MachineInstr *DefMI = MRI->getVRegDef(regB);
 456           // If it's safe and profitable, remat the definition instead of
 457           // copying it.
 458           if (DefMI &&
 459               isSafeToReMat(regB, DefMI) &&
 460               isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist,DistanceMap)){
 461             DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n");
 462             TII->reMaterialize(*mbbi, mi, regA, DefMI);
 463             ReMatRegs.set(regB);
 464             ++NumReMats;
 465           } else {
 466             TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
 467           }
 468
 469           MachineBasicBlock::iterator prevMi = prior(mi);
 470           DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
 471
 472           // Update live variables for regB.
 473           if (LV) {
 474             LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
 475
 476             // regB is used in this BB.
 477             varInfoB.UsedBlocks[mbbi->getNumber()] = true;
 478
 479             if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
 480               LV->addVirtualRegisterKilled(regB, prevMi);
 481
 482             if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
 483               LV->addVirtualRegisterDead(regB, prevMi);
 484           } else {
 485             // Manually update kill/dead flags.
 486             bool RemovedKill = false;
 487             bool RemovedDead = false;
 488             for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 489               MachineOperand &MO = mi->getOperand(i);
 490               if (MO.isRegister() && MO.isKill() && MO.getReg() == regB) {
 491                 MO.setIsKill(false);
 492                 RemovedKill = true;
 493                 break;
 494               }
 495
 496               if (MO.isRegister() && MO.isDef() && MO.getReg() == regB) {
 497                 MO.setIsDead(false);
 498                 RemovedDead = true;
 499               }
 500
 501               if (RemovedKill && RemovedDead) break;
 502             }
 503
 504             if (RemovedKill)
 505               prevMi->addRegisterKilled(regB, TRI);
 506             if (RemovedDead)
 507               prevMi->addRegisterDead(regB, TRI);
 508           }
 509
 510           // Replace all occurences of regB with regA.
 511           for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 512             if (mi->getOperand(i).isRegister() &&
 513                 mi->getOperand(i).getReg() == regB)
 514               mi->getOperand(i).setReg(regA);
 515           }
 516         }
 517
 518         assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
 519         mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
 520         MadeChange = true;
 521
 522         DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
 523       }
 524
 525       mi = nmi;
 526     }
 527   }
 528
 529   // Some remat'ed instructions are dead.
 530   int VReg = ReMatRegs.find_first();
 531   while (VReg != -1) {
 532     if (MRI->use_empty(VReg)) {
 533       MachineInstr *DefMI = MRI->getVRegDef(VReg);
 534       DefMI->eraseFromParent();
 535     }
 536     VReg = ReMatRegs.find_next(VReg);
 537   }
 538
 539   return MadeChange;
 540 }