lib/CodeGen/OptimizeExts.cpp

   1 //===-- OptimizeExts.cpp - Optimize sign / zero extension instrs -----===//
   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 pass performs optimization of sign / zero extension instructions. It
  11 // may be extended to handle other instructions of similar property.
  12 //
  13 // On some targets, some instructions, e.g. X86 sign / zero extension, may
  14 // leave the source value in the lower part of the result. This pass will
  15 // replace (some) uses of the pre-extension value with uses of the sub-register
  16 // of the results.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "ext-opt"
  21 #include "llvm/CodeGen/Passes.h"
  22 #include "llvm/CodeGen/MachineDominators.h"
  23 #include "llvm/CodeGen/MachineInstrBuilder.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/Target/TargetInstrInfo.h"
  26 #include "llvm/Target/TargetRegisterInfo.h"
  27 #include "llvm/Support/CommandLine.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/ADT/Statistic.h"
  30 using namespace llvm;
  31
  32 static cl::opt<bool> Aggressive("aggressive-ext-opt", cl::Hidden,
  33                                 cl::desc("Aggressive extension optimization"));
  34
  35 STATISTIC(NumReuse, "Number of extension results reused");
  36
  37 namespace {
  38   class OptimizeExts : public MachineFunctionPass {
  39     const TargetMachine   *TM;
  40     const TargetInstrInfo *TII;
  41     MachineRegisterInfo *MRI;
  42     MachineDominatorTree *DT;   // Machine dominator tree
  43
  44   public:
  45     static char ID; // Pass identification
  46     OptimizeExts() : MachineFunctionPass(ID) {}
  47
  48     virtual bool runOnMachineFunction(MachineFunction &MF);
  49
  50     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  51       AU.setPreservesCFG();
  52       MachineFunctionPass::getAnalysisUsage(AU);
  53       if (Aggressive) {
  54         AU.addRequired<MachineDominatorTree>();
  55         AU.addPreserved<MachineDominatorTree>();
  56       }
  57     }
  58
  59   private:
  60     bool OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB,
  61                        SmallPtrSet<MachineInstr*, 8> &LocalMIs);
  62   };
  63 }
  64
  65 char OptimizeExts::ID = 0;
  66 INITIALIZE_PASS(OptimizeExts, "opt-exts",
  67                 "Optimize sign / zero extensions", false, false);
  68
  69 FunctionPass *llvm::createOptimizeExtsPass() { return new OptimizeExts(); }
  70
  71 /// OptimizeInstr - If instruction is a copy-like instruction, i.e. it reads
  72 /// a single register and writes a single register and it does not modify
  73 /// the source, and if the source value is preserved as a sub-register of
  74 /// the result, then replace all reachable uses of the source with the subreg
  75 /// of the result.
  76 /// Do not generate an EXTRACT that is used only in a debug use, as this
  77 /// changes the code.  Since this code does not currently share EXTRACTs, just
  78 /// ignore all debug uses.
  79 bool OptimizeExts::OptimizeInstr(MachineInstr *MI, MachineBasicBlock *MBB,
  80                                  SmallPtrSet<MachineInstr*, 8> &LocalMIs) {
  81   LocalMIs.insert(MI);
  82
  83   unsigned SrcReg, DstReg, SubIdx;
  84   if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx))
  85     return false;
  86
  87   if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
  88       TargetRegisterInfo::isPhysicalRegister(SrcReg))
  89     return false;
  90
  91   MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(SrcReg);
  92   if (++UI == MRI->use_nodbg_end())
  93     // No other uses.
  94     return false;
  95
  96   // Ok, the source has other uses. See if we can replace the other uses
  97   // with use of the result of the extension.
  98   SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs;
  99   UI = MRI->use_nodbg_begin(DstReg);
 100   for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end();
 101        UI != UE; ++UI)
 102     ReachedBBs.insert(UI->getParent());
 103
 104   bool ExtendLife = true;
 105   // Uses that are in the same BB of uses of the result of the instruction.
 106   SmallVector<MachineOperand*, 8> Uses;
 107   // Uses that the result of the instruction can reach.
 108   SmallVector<MachineOperand*, 8> ExtendedUses;
 109
 110   UI = MRI->use_nodbg_begin(SrcReg);
 111   for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end();
 112        UI != UE; ++UI) {
 113     MachineOperand &UseMO = UI.getOperand();
 114     MachineInstr *UseMI = &*UI;
 115     if (UseMI == MI)
 116       continue;
 117     if (UseMI->isPHI()) {
 118       ExtendLife = false;
 119       continue;
 120     }
 121
 122     // It's an error to translate this:
 123     //
 124     //    %reg1025 = <sext> %reg1024
 125     //     ...
 126     //    %reg1026 = SUBREG_TO_REG 0, %reg1024, 4
 127     //
 128     // into this:
 129     //
 130     //    %reg1025 = <sext> %reg1024
 131     //     ...
 132     //    %reg1027 = COPY %reg1025:4
 133     //    %reg1026 = SUBREG_TO_REG 0, %reg1027, 4
 134     //
 135     // The problem here is that SUBREG_TO_REG is there to assert that an
 136     // implicit zext occurs. It doesn't insert a zext instruction. If we allow
 137     // the COPY here, it will give us the value after the <sext>, not the
 138     // original value of %reg1024 before <sext>.
 139     if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
 140       continue;
 141
 142     MachineBasicBlock *UseMBB = UseMI->getParent();
 143     if (UseMBB == MBB) {
 144       // Local uses that come after the extension.
 145       if (!LocalMIs.count(UseMI))
 146         Uses.push_back(&UseMO);
 147     } else if (ReachedBBs.count(UseMBB))
 148       // Non-local uses where the result of extension is used. Always replace
 149       // these unless it's a PHI.
 150       Uses.push_back(&UseMO);
 151     else if (Aggressive && DT->dominates(MBB, UseMBB))
 152       // We may want to extend live range of the extension result in order to
 153       // replace these uses.
 154       ExtendedUses.push_back(&UseMO);
 155     else {
 156       // Both will be live out of the def MBB anyway. Don't extend live range of
 157       // the extension result.
 158       ExtendLife = false;
 159       break;
 160     }
 161   }
 162
 163   if (ExtendLife && !ExtendedUses.empty())
 164     // Ok, we'll extend the liveness of the extension result.
 165     std::copy(ExtendedUses.begin(), ExtendedUses.end(),
 166               std::back_inserter(Uses));
 167
 168   // Now replace all uses.
 169   bool Changed = false;
 170   if (!Uses.empty()) {
 171     SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
 172     // Look for PHI uses of the extended result, we don't want to extend the
 173     // liveness of a PHI input. It breaks all kinds of assumptions down
 174     // stream. A PHI use is expected to be the kill of its source values.
 175     UI = MRI->use_nodbg_begin(DstReg);
 176     for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end();
 177          UI != UE; ++UI)
 178       if (UI->isPHI())
 179         PHIBBs.insert(UI->getParent());
 180
 181     const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
 182     for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
 183       MachineOperand *UseMO = Uses[i];
 184       MachineInstr *UseMI = UseMO->getParent();
 185       MachineBasicBlock *UseMBB = UseMI->getParent();
 186       if (PHIBBs.count(UseMBB))
 187         continue;
 188       unsigned NewVR = MRI->createVirtualRegister(RC);
 189       BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
 190               TII->get(TargetOpcode::COPY), NewVR)
 191         .addReg(DstReg, 0, SubIdx);
 192       UseMO->setReg(NewVR);
 193       ++NumReuse;
 194       Changed = true;
 195     }
 196   }
 197
 198   return Changed;
 199 }
 200
 201 bool OptimizeExts::runOnMachineFunction(MachineFunction &MF) {
 202   TM = &MF.getTarget();
 203   TII = TM->getInstrInfo();
 204   MRI = &MF.getRegInfo();
 205   DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : 0;
 206
 207   bool Changed = false;
 208
 209   SmallPtrSet<MachineInstr*, 8> LocalMIs;
 210   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 211     MachineBasicBlock *MBB = &*I;
 212     LocalMIs.clear();
 213     for (MachineBasicBlock::iterator MII = I->begin(), ME = I->end(); MII != ME;
 214          ++MII) {
 215       MachineInstr *MI = &*MII;
 216       Changed |= OptimizeInstr(MI, MBB, LocalMIs);
 217     }
 218   }
 219
 220   return Changed;
 221 }