lib/Target/X86/PeepholeOptimizer.cpp

   1 //===-- PeepholeOptimizer.cpp - X86 Peephole Optimizer --------------------===//
   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 contains a peephole optimizer for the X86.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "X86.h"
  15 #include "llvm/CodeGen/MachineFunctionPass.h"
  16 #include "llvm/CodeGen/MachineInstrBuilder.h"
  17 #include "llvm/Target/MRegisterInfo.h"
  18 #include "Support/Statistic.h"
  19 #include "Support/STLExtras.h"
  20
  21 using namespace llvm;
  22
  23 namespace {
  24   Statistic<> NumPHOpts("x86-peephole",
  25                         "Number of peephole optimization performed");
  26   struct PH : public MachineFunctionPass {
  27     virtual bool runOnMachineFunction(MachineFunction &MF);
  28
  29     bool PeepholeOptimize(MachineBasicBlock &MBB,
  30                           MachineBasicBlock::iterator &I);
  31
  32     virtual const char *getPassName() const { return "X86 Peephole Optimizer"; }
  33   };
  34 }
  35
  36 FunctionPass *llvm::createX86PeepholeOptimizerPass() { return new PH(); }
  37
  38 bool PH::runOnMachineFunction(MachineFunction &MF) {
  39   bool Changed = false;
  40
  41   for (MachineFunction::iterator BI = MF.begin(), E = MF.end(); BI != E; ++BI)
  42     for (MachineBasicBlock::iterator I = BI->begin(); I != BI->end(); )
  43       if (PeepholeOptimize(*BI, I)) {
  44         Changed = true;
  45         ++NumPHOpts;
  46       } else
  47         ++I;
  48
  49   return Changed;
  50 }
  51
  52
  53 bool PH::PeepholeOptimize(MachineBasicBlock &MBB,
  54                           MachineBasicBlock::iterator &I) {
  55   assert(I != MBB.end());
  56   MachineBasicBlock::iterator NextI = next(I);
  57
  58   MachineInstr *MI = I;
  59   MachineInstr *Next = (NextI != MBB.end()) ? &*NextI : (MachineInstr*)0;
  60   unsigned Size = 0;
  61   switch (MI->getOpcode()) {
  62   case X86::MOVrr8:
  63   case X86::MOVrr16:
  64   case X86::MOVrr32:   // Destroy X = X copies...
  65     if (MI->getOperand(0).getReg() == MI->getOperand(1).getReg()) {
  66       I = MBB.erase(I);
  67       return true;
  68     }
  69     return false;
  70
  71     // A large number of X86 instructions have forms which take an 8-bit
  72     // immediate despite the fact that the operands are 16 or 32 bits.  Because
  73     // this can save three bytes of code size (and icache space), we want to
  74     // shrink them if possible.
  75   case X86::IMULrri16: case X86::IMULrri32:
  76     assert(MI->getNumOperands() == 3 && "These should all have 3 operands!");
  77     if (MI->getOperand(2).isImmediate()) {
  78       int Val = MI->getOperand(2).getImmedValue();
  79       // If the value is the same when signed extended from 8 bits...
  80       if (Val == (signed int)(signed char)Val) {
  81         unsigned Opcode;
  82         switch (MI->getOpcode()) {
  83         default: assert(0 && "Unknown opcode value!");
  84         case X86::IMULrri16: Opcode = X86::IMULrri16b; break;
  85         case X86::IMULrri32: Opcode = X86::IMULrri32b; break;
  86         }
  87         unsigned R0 = MI->getOperand(0).getReg();
  88         unsigned R1 = MI->getOperand(1).getReg();
  89         I = MBB.insert(MBB.erase(I),
  90                        BuildMI(Opcode, 2, R0).addReg(R1).addZImm((char)Val));
  91         return true;
  92       }
  93     }
  94     return false;
  95
  96   case X86::IMULrmi16: case X86::IMULrmi32:
  97     assert(MI->getNumOperands() == 6 && "These should all have 6 operands!");
  98     if (MI->getOperand(5).isImmediate()) {
  99       int Val = MI->getOperand(5).getImmedValue();
 100       // If the value is the same when signed extended from 8 bits...
 101       if (Val == (signed int)(signed char)Val) {
 102         unsigned Opcode;
 103         switch (MI->getOpcode()) {
 104         default: assert(0 && "Unknown opcode value!");
 105         case X86::IMULrmi16: Opcode = X86::IMULrmi16b; break;
 106         case X86::IMULrmi32: Opcode = X86::IMULrmi32b; break;
 107         }
 108         unsigned R0 = MI->getOperand(0).getReg();
 109         unsigned R1 = MI->getOperand(1).getReg();
 110         unsigned Scale = MI->getOperand(2).getImmedValue();
 111         unsigned R2 = MI->getOperand(3).getReg();
 112         unsigned Offset = MI->getOperand(4).getImmedValue();
 113         I = MBB.insert(MBB.erase(I),
 114                        BuildMI(Opcode, 5, R0).addReg(R1).addZImm(Scale).
 115                              addReg(R2).addSImm(Offset).addZImm((char)Val));
 116         return true;
 117       }
 118     }
 119     return false;
 120
 121   case X86::ADDri16:  case X86::ADDri32:
 122   case X86::ADDmi16:  case X86::ADDmi32:
 123   case X86::SUBri16:  case X86::SUBri32:
 124   case X86::ANDri16:  case X86::ANDri32:
 125   case X86::ORri16:   case X86::ORri32:
 126   case X86::XORri16:  case X86::XORri32:
 127     assert(MI->getNumOperands() == 2 && "These should all have 2 operands!");
 128     if (MI->getOperand(1).isImmediate()) {
 129       int Val = MI->getOperand(1).getImmedValue();
 130       // If the value is the same when signed extended from 8 bits...
 131       if (Val == (signed int)(signed char)Val) {
 132         unsigned Opcode;
 133         switch (MI->getOpcode()) {
 134         default: assert(0 && "Unknown opcode value!");
 135         case X86::ADDri16:  Opcode = X86::ADDri16b; break;
 136         case X86::ADDri32:  Opcode = X86::ADDri32b; break;
 137         case X86::ADDmi16:  Opcode = X86::ADDmi16b; break;
 138         case X86::ADDmi32:  Opcode = X86::ADDmi32b; break;
 139         case X86::SUBri16:  Opcode = X86::SUBri16b; break;
 140         case X86::SUBri32:  Opcode = X86::SUBri32b; break;
 141         case X86::ANDri16:  Opcode = X86::ANDri16b; break;
 142         case X86::ANDri32:  Opcode = X86::ANDri32b; break;
 143         case X86::ORri16:   Opcode = X86::ORri16b; break;
 144         case X86::ORri32:   Opcode = X86::ORri32b; break;
 145         case X86::XORri16:  Opcode = X86::XORri16b; break;
 146         case X86::XORri32:  Opcode = X86::XORri32b; break;
 147         }
 148         unsigned R0 = MI->getOperand(0).getReg();
 149         I = MBB.insert(MBB.erase(I),
 150                     BuildMI(Opcode, 1, R0, MOTy::UseAndDef).addZImm((char)Val));
 151         return true;
 152       }
 153     }
 154     return false;
 155
 156
 157   case X86::ANDmi16:  case X86::ANDmi32:
 158     assert(MI->getNumOperands() == 5 && "These should all have 5 operands!");
 159     if (MI->getOperand(4).isImmediate()) {
 160       int Val = MI->getOperand(4).getImmedValue();
 161       // If the value is the same when signed extended from 8 bits...
 162       if (Val == (signed int)(signed char)Val) {
 163         unsigned Opcode;
 164         switch (MI->getOpcode()) {
 165         default: assert(0 && "Unknown opcode value!");
 166         case X86::ANDmi16:  Opcode = X86::ANDmi16b; break;
 167         case X86::ANDmi32:  Opcode = X86::ANDmi32b; break;
 168         }
 169         unsigned R0 = MI->getOperand(0).getReg();
 170         unsigned Scale = MI->getOperand(1).getImmedValue();
 171         unsigned R1 = MI->getOperand(2).getReg();
 172         unsigned Offset = MI->getOperand(3).getImmedValue();
 173         I = MBB.insert(MBB.erase(I),
 174                        BuildMI(Opcode, 5).addReg(R0).addZImm(Scale).
 175                              addReg(R1).addSImm(Offset).addZImm((char)Val));
 176         return true;
 177       }
 178     }
 179     return false;
 180
 181 #if 0
 182   case X86::MOVri32: Size++;
 183   case X86::MOVri16: Size++;
 184   case X86::MOVri8:
 185     // FIXME: We can only do this transformation if we know that flags are not
 186     // used here, because XOR clobbers the flags!
 187     if (MI->getOperand(1).isImmediate()) {         // avoid mov EAX, <value>
 188       int Val = MI->getOperand(1).getImmedValue();
 189       if (Val == 0) {                              // mov EAX, 0 -> xor EAX, EAX
 190         static const unsigned Opcode[] ={X86::XORrr8,X86::XORrr16,X86::XORrr32};
 191         unsigned Reg = MI->getOperand(0).getReg();
 192         I = MBB.insert(MBB.erase(I),
 193                        BuildMI(Opcode[Size], 2, Reg).addReg(Reg).addReg(Reg));
 194         return true;
 195       } else if (Val == -1) {                     // mov EAX, -1 -> or EAX, -1
 196         // TODO: 'or Reg, -1' has a smaller encoding than 'mov Reg, -1'
 197       }
 198     }
 199     return false;
 200 #endif
 201   case X86::BSWAPr32:        // Change bswap EAX, bswap EAX into nothing
 202     if (Next->getOpcode() == X86::BSWAPr32 &&
 203         MI->getOperand(0).getReg() == Next->getOperand(0).getReg()) {
 204       I = MBB.erase(MBB.erase(I));
 205       return true;
 206     }
 207     return false;
 208   default:
 209     return false;
 210   }
 211 }
 212
 213 namespace {
 214   class UseDefChains : public MachineFunctionPass {
 215     std::vector<MachineInstr*> DefiningInst;
 216   public:
 217     // getDefinition - Return the machine instruction that defines the specified
 218     // SSA virtual register.
 219     MachineInstr *getDefinition(unsigned Reg) {
 220       assert(MRegisterInfo::isVirtualRegister(Reg) &&
 221              "use-def chains only exist for SSA registers!");
 222       assert(Reg - MRegisterInfo::FirstVirtualRegister < DefiningInst.size() &&
 223              "Unknown register number!");
 224       assert(DefiningInst[Reg-MRegisterInfo::FirstVirtualRegister] &&
 225              "Unknown register number!");
 226       return DefiningInst[Reg-MRegisterInfo::FirstVirtualRegister];
 227     }
 228
 229     // setDefinition - Update the use-def chains to indicate that MI defines
 230     // register Reg.
 231     void setDefinition(unsigned Reg, MachineInstr *MI) {
 232       if (Reg-MRegisterInfo::FirstVirtualRegister >= DefiningInst.size())
 233         DefiningInst.resize(Reg-MRegisterInfo::FirstVirtualRegister+1);
 234       DefiningInst[Reg-MRegisterInfo::FirstVirtualRegister] = MI;
 235     }
 236
 237     // removeDefinition - Update the use-def chains to forget about Reg
 238     // entirely.
 239     void removeDefinition(unsigned Reg) {
 240       assert(getDefinition(Reg));      // Check validity
 241       DefiningInst[Reg-MRegisterInfo::FirstVirtualRegister] = 0;
 242     }
 243
 244     virtual bool runOnMachineFunction(MachineFunction &MF) {
 245       for (MachineFunction::iterator BI = MF.begin(), E = MF.end(); BI!=E; ++BI)
 246         for (MachineBasicBlock::iterator I = BI->begin(); I != BI->end(); ++I) {
 247           for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 248             MachineOperand &MO = I->getOperand(i);
 249             if (MO.isRegister() && MO.isDef() && !MO.isUse() &&
 250                 MRegisterInfo::isVirtualRegister(MO.getReg()))
 251               setDefinition(MO.getReg(), I);
 252           }
 253         }
 254       return false;
 255     }
 256
 257     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 258       AU.setPreservesAll();
 259       MachineFunctionPass::getAnalysisUsage(AU);
 260     }
 261
 262     virtual void releaseMemory() {
 263       std::vector<MachineInstr*>().swap(DefiningInst);
 264     }
 265   };
 266
 267   RegisterAnalysis<UseDefChains> X("use-def-chains",
 268                                 "use-def chain construction for machine code");
 269 }
 270
 271
 272 namespace {
 273   Statistic<> NumSSAPHOpts("x86-ssa-peephole",
 274                            "Number of SSA peephole optimization performed");
 275
 276   /// SSAPH - This pass is an X86-specific, SSA-based, peephole optimizer.  This
 277   /// pass is really a bad idea: a better instruction selector should completely
 278   /// supersume it.  However, that will take some time to develop, and the
 279   /// simple things this can do are important now.
 280   class SSAPH : public MachineFunctionPass {
 281     UseDefChains *UDC;
 282   public:
 283     virtual bool runOnMachineFunction(MachineFunction &MF);
 284
 285     bool PeepholeOptimize(MachineBasicBlock &MBB,
 286                           MachineBasicBlock::iterator &I);
 287
 288     virtual const char *getPassName() const {
 289       return "X86 SSA-based Peephole Optimizer";
 290     }
 291
 292     /// Propagate - Set MI[DestOpNo] = Src[SrcOpNo], optionally change the
 293     /// opcode of the instruction, then return true.
 294     bool Propagate(MachineInstr *MI, unsigned DestOpNo,
 295                    MachineInstr *Src, unsigned SrcOpNo, unsigned NewOpcode = 0){
 296       MI->getOperand(DestOpNo) = Src->getOperand(SrcOpNo);
 297       if (NewOpcode) MI->setOpcode(NewOpcode);
 298       return true;
 299     }
 300
 301     /// OptimizeAddress - If we can fold the addressing arithmetic for this
 302     /// memory instruction into the instruction itself, do so and return true.
 303     bool OptimizeAddress(MachineInstr *MI, unsigned OpNo);
 304
 305     /// getDefininingInst - If the specified operand is a read of an SSA
 306     /// register, return the machine instruction defining it, otherwise, return
 307     /// null.
 308     MachineInstr *getDefiningInst(MachineOperand &MO) {
 309       if (MO.isDef() || !MO.isRegister() ||
 310           !MRegisterInfo::isVirtualRegister(MO.getReg())) return 0;
 311       return UDC->getDefinition(MO.getReg());
 312     }
 313
 314     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 315       AU.addRequired<UseDefChains>();
 316       AU.addPreserved<UseDefChains>();
 317       MachineFunctionPass::getAnalysisUsage(AU);
 318     }
 319   };
 320 }
 321
 322 FunctionPass *llvm::createX86SSAPeepholeOptimizerPass() { return new SSAPH(); }
 323
 324 bool SSAPH::runOnMachineFunction(MachineFunction &MF) {
 325   bool Changed = false;
 326   bool LocalChanged;
 327
 328   UDC = &getAnalysis<UseDefChains>();
 329
 330   do {
 331     LocalChanged = false;
 332
 333     for (MachineFunction::iterator BI = MF.begin(), E = MF.end(); BI != E; ++BI)
 334       for (MachineBasicBlock::iterator I = BI->begin(); I != BI->end(); )
 335         if (PeepholeOptimize(*BI, I)) {
 336           LocalChanged = true;
 337           ++NumSSAPHOpts;
 338         } else
 339           ++I;
 340     Changed |= LocalChanged;
 341   } while (LocalChanged);
 342
 343   return Changed;
 344 }
 345
 346 static bool isValidScaleAmount(unsigned Scale) {
 347   return Scale == 1 || Scale == 2 || Scale == 4 || Scale == 8;
 348 }
 349
 350 /// OptimizeAddress - If we can fold the addressing arithmetic for this
 351 /// memory instruction into the instruction itself, do so and return true.
 352 bool SSAPH::OptimizeAddress(MachineInstr *MI, unsigned OpNo) {
 353   MachineOperand &BaseRegOp      = MI->getOperand(OpNo+0);
 354   MachineOperand &ScaleOp        = MI->getOperand(OpNo+1);
 355   MachineOperand &IndexRegOp     = MI->getOperand(OpNo+2);
 356   MachineOperand &DisplacementOp = MI->getOperand(OpNo+3);
 357
 358   unsigned BaseReg  = BaseRegOp.hasAllocatedReg() ? BaseRegOp.getReg() : 0;
 359   unsigned Scale    = ScaleOp.getImmedValue();
 360   unsigned IndexReg = IndexRegOp.hasAllocatedReg() ? IndexRegOp.getReg() : 0;
 361
 362   bool Changed = false;
 363
 364   // If the base register is unset, and the index register is set with a scale
 365   // of 1, move it to be the base register.
 366   if (BaseRegOp.hasAllocatedReg() && BaseReg == 0 &&
 367       Scale == 1 && IndexReg != 0) {
 368     BaseRegOp.setReg(IndexReg);
 369     IndexRegOp.setReg(0);
 370     return true;
 371   }
 372
 373   // Attempt to fold instructions used by the base register into the instruction
 374   if (MachineInstr *DefInst = getDefiningInst(BaseRegOp)) {
 375     switch (DefInst->getOpcode()) {
 376     case X86::MOVri32:
 377       // If there is no displacement set for this instruction set one now.
 378       // FIXME: If we can fold two immediates together, we should do so!
 379       if (DisplacementOp.isImmediate() && !DisplacementOp.getImmedValue()) {
 380         if (DefInst->getOperand(1).isImmediate()) {
 381           BaseRegOp.setReg(0);
 382           return Propagate(MI, OpNo+3, DefInst, 1);
 383         }
 384       }
 385       break;
 386
 387     case X86::ADDrr32:
 388       // If the source is a register-register add, and we do not yet have an
 389       // index register, fold the add into the memory address.
 390       if (IndexReg == 0) {
 391         BaseRegOp = DefInst->getOperand(1);
 392         IndexRegOp = DefInst->getOperand(2);
 393         ScaleOp.setImmedValue(1);
 394         return true;
 395       }
 396       break;
 397
 398     case X86::SHLri32:
 399       // If this shift could be folded into the index portion of the address if
 400       // it were the index register, move it to the index register operand now,
 401       // so it will be folded in below.
 402       if ((Scale == 1 || (IndexReg == 0 && IndexRegOp.hasAllocatedReg())) &&
 403           DefInst->getOperand(2).getImmedValue() < 4) {
 404         std::swap(BaseRegOp, IndexRegOp);
 405         ScaleOp.setImmedValue(1); Scale = 1;
 406         std::swap(IndexReg, BaseReg);
 407         Changed = true;
 408         break;
 409       }
 410     }
 411   }
 412
 413   // Attempt to fold instructions used by the index into the instruction
 414   if (MachineInstr *DefInst = getDefiningInst(IndexRegOp)) {
 415     switch (DefInst->getOpcode()) {
 416     case X86::SHLri32: {
 417       // Figure out what the resulting scale would be if we folded this shift.
 418       unsigned ResScale = Scale * (1 << DefInst->getOperand(2).getImmedValue());
 419       if (isValidScaleAmount(ResScale)) {
 420         IndexRegOp = DefInst->getOperand(1);
 421         ScaleOp.setImmedValue(ResScale);
 422         return true;
 423       }
 424       break;
 425     }
 426     }
 427   }
 428
 429   return Changed;
 430 }
 431
 432 bool SSAPH::PeepholeOptimize(MachineBasicBlock &MBB,
 433                              MachineBasicBlock::iterator &I) {
 434     MachineBasicBlock::iterator NextI = next(I);
 435
 436   MachineInstr *MI = I;
 437   MachineInstr *Next = (NextI != MBB.end()) ? &*NextI : (MachineInstr*)0;
 438
 439   bool Changed = false;
 440
 441   // Scan the operands of this instruction.  If any operands are
 442   // register-register copies, replace the operand with the source.
 443   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 444     // Is this an SSA register use?
 445     if (MachineInstr *DefInst = getDefiningInst(MI->getOperand(i)))
 446       // If the operand is a vreg-vreg copy, it is always safe to replace the
 447       // source value with the input operand.
 448       if (DefInst->getOpcode() == X86::MOVrr8  ||
 449           DefInst->getOpcode() == X86::MOVrr16 ||
 450           DefInst->getOpcode() == X86::MOVrr32) {
 451         // Don't propagate physical registers into PHI nodes...
 452         if (MI->getOpcode() != X86::PHI ||
 453             (DefInst->getOperand(1).isRegister() &&
 454              MRegisterInfo::isVirtualRegister(DefInst->getOperand(1).getReg())))
 455         Changed = Propagate(MI, i, DefInst, 1);
 456       }
 457
 458
 459   // Perform instruction specific optimizations.
 460   switch (MI->getOpcode()) {
 461
 462     // Register to memory stores.  Format: <base,scale,indexreg,immdisp>, srcreg
 463   case X86::MOVrm32: case X86::MOVrm16: case X86::MOVrm8:
 464   case X86::MOVmi32: case X86::MOVmi16: case X86::MOVmi8:
 465     // Check to see if we can fold the source instruction into this one...
 466     if (MachineInstr *SrcInst = getDefiningInst(MI->getOperand(4))) {
 467       switch (SrcInst->getOpcode()) {
 468         // Fold the immediate value into the store, if possible.
 469       case X86::MOVri8:  return Propagate(MI, 4, SrcInst, 1, X86::MOVmi8);
 470       case X86::MOVri16: return Propagate(MI, 4, SrcInst, 1, X86::MOVmi16);
 471       case X86::MOVri32: return Propagate(MI, 4, SrcInst, 1, X86::MOVmi32);
 472       default: break;
 473       }
 474     }
 475
 476     // If we can optimize the addressing expression, do so now.
 477     if (OptimizeAddress(MI, 0))
 478       return true;
 479     break;
 480
 481   case X86::MOVmr32:
 482   case X86::MOVmr16:
 483   case X86::MOVmr8:
 484     // If we can optimize the addressing expression, do so now.
 485     if (OptimizeAddress(MI, 1))
 486       return true;
 487     break;
 488
 489   default: break;
 490   }
 491
 492   return Changed;
 493 }