lib/Target/SystemZ/SystemZElimCompare.cpp

   1 //===-- SystemZElimCompare.cpp - Eliminate comparison instructions --------===//
   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:
  11 // (1) tries to remove compares if CC already contains the required information
  12 // (2) fuses compares and branches into COMPARE AND BRANCH instructions
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "systemz-elim-compare"
  17
  18 #include "SystemZTargetMachine.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/IR/Function.h"
  23 #include "llvm/Support/CommandLine.h"
  24 #include "llvm/Support/MathExtras.h"
  25 #include "llvm/Target/TargetInstrInfo.h"
  26 #include "llvm/Target/TargetMachine.h"
  27 #include "llvm/Target/TargetRegisterInfo.h"
  28
  29 using namespace llvm;
  30
  31 STATISTIC(EliminatedComparisons, "Number of eliminated comparisons");
  32 STATISTIC(FusedComparisons, "Number of fused compare-and-branch instructions");
  33
  34 namespace {
  35   class SystemZElimCompare : public MachineFunctionPass {
  36   public:
  37     static char ID;
  38     SystemZElimCompare(const SystemZTargetMachine &tm)
  39       : MachineFunctionPass(ID), TII(0), TRI(0) {}
  40
  41     virtual const char *getPassName() const {
  42       return "SystemZ Comparison Elimination";
  43     }
  44
  45     bool processBlock(MachineBasicBlock *MBB);
  46     bool runOnMachineFunction(MachineFunction &F);
  47
  48   private:
  49     bool convertToLoadAndTest(MachineInstr *MI);
  50     bool adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare,
  51                                SmallVectorImpl<MachineInstr *> &CCUsers);
  52     bool optimizeCompareZero(MachineInstr *Compare,
  53                              SmallVectorImpl<MachineInstr *> &CCUsers);
  54     bool fuseCompareAndBranch(MachineInstr *Compare,
  55                               SmallVectorImpl<MachineInstr *> &CCUsers);
  56
  57     const SystemZInstrInfo *TII;
  58     const TargetRegisterInfo *TRI;
  59   };
  60
  61   char SystemZElimCompare::ID = 0;
  62 } // end of anonymous namespace
  63
  64 FunctionPass *llvm::createSystemZElimComparePass(SystemZTargetMachine &TM) {
  65   return new SystemZElimCompare(TM);
  66 }
  67
  68 // Return true if CC is live out of MBB.
  69 static bool isCCLiveOut(MachineBasicBlock *MBB) {
  70   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
  71          SE = MBB->succ_end(); SI != SE; ++SI)
  72     if ((*SI)->isLiveIn(SystemZ::CC))
  73       return true;
  74   return false;
  75 }
  76
  77 // Return true if any CC result of MI would reflect the value of subreg
  78 // SubReg of Reg.
  79 static bool resultTests(MachineInstr *MI, unsigned Reg, unsigned SubReg) {
  80   if (MI->getNumOperands() > 0 &&
  81       MI->getOperand(0).isReg() &&
  82       MI->getOperand(0).isDef() &&
  83       MI->getOperand(0).getReg() == Reg &&
  84       MI->getOperand(0).getSubReg() == SubReg)
  85     return true;
  86
  87   switch (MI->getOpcode()) {
  88   case SystemZ::LR:
  89   case SystemZ::LGR:
  90   case SystemZ::LGFR:
  91   case SystemZ::LTR:
  92   case SystemZ::LTGR:
  93   case SystemZ::LTGFR:
  94     if (MI->getOperand(1).getReg() == Reg &&
  95         MI->getOperand(1).getSubReg() == SubReg)
  96       return true;
  97   }
  98
  99   return false;
 100 }
 101
 102 // If MI is a load instruction, try to convert it into a LOAD AND TEST.
 103 // Return true on success.
 104 bool SystemZElimCompare::convertToLoadAndTest(MachineInstr *MI) {
 105   unsigned Opcode = TII->getLoadAndTest(MI->getOpcode());
 106   if (!Opcode)
 107     return false;
 108
 109   MI->setDesc(TII->get(Opcode));
 110   MachineInstrBuilder(*MI->getParent()->getParent(), MI)
 111     .addReg(SystemZ::CC, RegState::ImplicitDefine);
 112   return true;
 113 }
 114
 115 // The CC users in CCUsers are testing the result of a comparison of some
 116 // value X against zero and we know that any CC value produced by MI
 117 // would also reflect the value of X.  Try to adjust CCUsers so that
 118 // they test the result of MI directly, returning true on success.
 119 // Leave everything unchanged on failure.
 120 bool SystemZElimCompare::
 121 adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare,
 122                       SmallVectorImpl<MachineInstr *> &CCUsers) {
 123   int Opcode = MI->getOpcode();
 124   const MCInstrDesc &Desc = TII->get(Opcode);
 125   unsigned MIFlags = Desc.TSFlags;
 126
 127   // See which compare-style condition codes are available.
 128   unsigned ReusableCCMask = 0;
 129   if (MIFlags & SystemZII::CCHasZero)
 130     ReusableCCMask |= SystemZ::CCMASK_CMP_EQ;
 131
 132   // For unsigned comparisons with zero, only equality makes sense.
 133   unsigned CompareFlags = Compare->getDesc().TSFlags;
 134   if (!(CompareFlags & SystemZII::IsLogical) &&
 135       (MIFlags & SystemZII::CCHasOrder))
 136     ReusableCCMask |= SystemZ::CCMASK_CMP_LT | SystemZ::CCMASK_CMP_GT;
 137
 138   if (ReusableCCMask == 0)
 139     return false;
 140
 141   unsigned CCValues = SystemZII::getCCValues(MIFlags);
 142   assert((ReusableCCMask & ~CCValues) == 0 && "Invalid CCValues");
 143
 144   // Now check whether these flags are enough for all users.
 145   SmallVector<MachineOperand *, 4> AlterMasks;
 146   for (unsigned int I = 0, E = CCUsers.size(); I != E; ++I) {
 147     MachineInstr *MI = CCUsers[I];
 148
 149     // Fail if this isn't a use of CC that we understand.
 150     unsigned Flags = MI->getDesc().TSFlags;
 151     unsigned FirstOpNum;
 152     if (Flags & SystemZII::CCMaskFirst)
 153       FirstOpNum = 0;
 154     else if (Flags & SystemZII::CCMaskLast)
 155       FirstOpNum = MI->getNumExplicitOperands() - 2;
 156     else
 157       return false;
 158
 159     // Check whether the instruction predicate treats all CC values
 160     // outside of ReusableCCMask in the same way.  In that case it
 161     // doesn't matter what those CC values mean.
 162     unsigned CCValid = MI->getOperand(FirstOpNum).getImm();
 163     unsigned CCMask = MI->getOperand(FirstOpNum + 1).getImm();
 164     unsigned OutValid = ~ReusableCCMask & CCValid;
 165     unsigned OutMask = ~ReusableCCMask & CCMask;
 166     if (OutMask != 0 && OutMask != OutValid)
 167       return false;
 168
 169     AlterMasks.push_back(&MI->getOperand(FirstOpNum));
 170     AlterMasks.push_back(&MI->getOperand(FirstOpNum + 1));
 171   }
 172
 173   // All users are OK.  Adjust the masks for MI.
 174   for (unsigned I = 0, E = AlterMasks.size(); I != E; I += 2) {
 175     AlterMasks[I]->setImm(CCValues);
 176     unsigned CCMask = AlterMasks[I + 1]->getImm();
 177     if (CCMask & ~ReusableCCMask)
 178       AlterMasks[I + 1]->setImm((CCMask & ReusableCCMask) |
 179                                 (CCValues & ~ReusableCCMask));
 180   }
 181
 182   // CC is now live after MI.
 183   int CCDef = MI->findRegisterDefOperandIdx(SystemZ::CC, false, true, TRI);
 184   assert(CCDef >= 0 && "Couldn't find CC set");
 185   MI->getOperand(CCDef).setIsDead(false);
 186
 187   // Clear any intervening kills of CC.
 188   MachineBasicBlock::iterator MBBI = MI, MBBE = Compare;
 189   for (++MBBI; MBBI != MBBE; ++MBBI)
 190     MBBI->clearRegisterKills(SystemZ::CC, TRI);
 191
 192   return true;
 193 }
 194
 195 // Try to optimize cases where comparison instruction Compare is testing
 196 // a value against zero.  Return true on success and if Compare should be
 197 // deleted as dead.  CCUsers is the list of instructions that use the CC
 198 // value produced by Compare.
 199 bool SystemZElimCompare::
 200 optimizeCompareZero(MachineInstr *Compare,
 201                     SmallVectorImpl<MachineInstr *> &CCUsers) {
 202   // Check whether this is a comparison against zero.
 203   if (Compare->getNumExplicitOperands() != 2 ||
 204       !Compare->getOperand(1).isImm() ||
 205       Compare->getOperand(1).getImm() != 0)
 206     return false;
 207
 208   // Search back for CC results that are based on the first operand.
 209   unsigned SrcReg = Compare->getOperand(0).getReg();
 210   unsigned SrcSubReg = Compare->getOperand(0).getSubReg();
 211   MachineBasicBlock *MBB = Compare->getParent();
 212   MachineBasicBlock::iterator MBBI = Compare, MBBE = MBB->begin();
 213   bool SeenUseOfCC = false;
 214   while (MBBI != MBBE) {
 215     --MBBI;
 216     MachineInstr *MI = MBBI;
 217     if (resultTests(MI, SrcReg, SrcSubReg) &&
 218         ((!SeenUseOfCC && convertToLoadAndTest(MI)) ||
 219          adjustCCMasksForInstr(MI, Compare, CCUsers))) {
 220       EliminatedComparisons += 1;
 221       return true;
 222     }
 223     if (MI->modifiesRegister(SrcReg, TRI) ||
 224         MI->modifiesRegister(SystemZ::CC, TRI))
 225       return false;
 226     if (MI->readsRegister(SystemZ::CC, TRI))
 227       SeenUseOfCC = true;
 228   }
 229   return false;
 230 }
 231
 232 // Try to fuse comparison instruction Compare into a later branch.
 233 // Return true on success and if Compare is therefore redundant.
 234 bool SystemZElimCompare::
 235 fuseCompareAndBranch(MachineInstr *Compare,
 236                      SmallVectorImpl<MachineInstr *> &CCUsers) {
 237   // See whether we have a comparison that can be fused.
 238   unsigned FusedOpcode = TII->getCompareAndBranch(Compare->getOpcode(),
 239                                                   Compare);
 240   if (!FusedOpcode)
 241     return false;
 242
 243   // See whether we have a single branch with which to fuse.
 244   if (CCUsers.size() != 1)
 245     return false;
 246   MachineInstr *Branch = CCUsers[0];
 247   if (Branch->getOpcode() != SystemZ::BRC)
 248     return false;
 249
 250   // Make sure that the operands are available at the branch.
 251   unsigned SrcReg = Compare->getOperand(0).getReg();
 252   unsigned SrcReg2 = (Compare->getOperand(1).isReg() ?
 253                       Compare->getOperand(1).getReg() : 0);
 254   MachineBasicBlock::iterator MBBI = Compare, MBBE = Branch;
 255   for (++MBBI; MBBI != MBBE; ++MBBI)
 256     if (MBBI->modifiesRegister(SrcReg, TRI) ||
 257         (SrcReg2 && MBBI->modifiesRegister(SrcReg2, TRI)))
 258       return false;
 259
 260   // Read the branch mask and target.
 261   MachineOperand CCMask(MBBI->getOperand(1));
 262   MachineOperand Target(MBBI->getOperand(2));
 263   assert((CCMask.getImm() & ~SystemZ::CCMASK_ICMP) == 0 &&
 264          "Invalid condition-code mask for integer comparison");
 265
 266   // Clear out all current operands.
 267   int CCUse = MBBI->findRegisterUseOperandIdx(SystemZ::CC, false, TRI);
 268   assert(CCUse >= 0 && "BRC must use CC");
 269   Branch->RemoveOperand(CCUse);
 270   Branch->RemoveOperand(2);
 271   Branch->RemoveOperand(1);
 272   Branch->RemoveOperand(0);
 273
 274   // Rebuild Branch as a fused compare and branch.
 275   Branch->setDesc(TII->get(FusedOpcode));
 276   MachineInstrBuilder(*Branch->getParent()->getParent(), Branch)
 277     .addOperand(Compare->getOperand(0))
 278     .addOperand(Compare->getOperand(1))
 279     .addOperand(CCMask)
 280     .addOperand(Target)
 281     .addReg(SystemZ::CC, RegState::ImplicitDefine);
 282
 283   // Clear any intervening kills of SrcReg and SrcReg2.
 284   MBBI = Compare;
 285   for (++MBBI; MBBI != MBBE; ++MBBI) {
 286     MBBI->clearRegisterKills(SrcReg, TRI);
 287     if (SrcReg2)
 288       MBBI->clearRegisterKills(SrcReg2, TRI);
 289   }
 290   FusedComparisons += 1;
 291   return true;
 292 }
 293
 294 // Process all comparison instructions in MBB.  Return true if something
 295 // changed.
 296 bool SystemZElimCompare::processBlock(MachineBasicBlock *MBB) {
 297   bool Changed = false;
 298
 299   // Walk backwards through the block looking for comparisons, recording
 300   // all CC users as we go.  The subroutines can delete Compare and
 301   // instructions before it.
 302   bool CompleteCCUsers = !isCCLiveOut(MBB);
 303   SmallVector<MachineInstr *, 4> CCUsers;
 304   MachineBasicBlock::iterator MBBI = MBB->end();
 305   while (MBBI != MBB->begin()) {
 306     MachineInstr *MI = --MBBI;
 307     if (CompleteCCUsers &&
 308         MI->isCompare() &&
 309         (optimizeCompareZero(MI, CCUsers) ||
 310          fuseCompareAndBranch(MI, CCUsers))) {
 311       ++MBBI;
 312       MI->removeFromParent();
 313       Changed = true;
 314       CCUsers.clear();
 315       CompleteCCUsers = true;
 316       continue;
 317     }
 318
 319     if (MI->definesRegister(SystemZ::CC, TRI)) {
 320       CCUsers.clear();
 321       CompleteCCUsers = true;
 322     } else if (MI->modifiesRegister(SystemZ::CC, TRI))
 323       CompleteCCUsers = false;
 324
 325     if (CompleteCCUsers && MI->readsRegister(SystemZ::CC, TRI))
 326       CCUsers.push_back(MI);
 327   }
 328   return Changed;
 329 }
 330
 331 bool SystemZElimCompare::runOnMachineFunction(MachineFunction &F) {
 332   TII = static_cast<const SystemZInstrInfo *>(F.getTarget().getInstrInfo());
 333   TRI = &TII->getRegisterInfo();
 334
 335   bool Changed = false;
 336   for (MachineFunction::iterator MFI = F.begin(), MFE = F.end();
 337        MFI != MFE; ++MFI)
 338     Changed |= processBlock(MFI);
 339
 340   return Changed;
 341 }