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