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(BranchOnCounts, "Number of branch-on-count instructions");
  32 STATISTIC(EliminatedComparisons, "Number of eliminated comparisons");
  33 STATISTIC(FusedComparisons, "Number of fused compare-and-branch instructions");
  34
  35 namespace {
  36   // Represents the references to a particular register in one or more
  37   // instructions.
  38   struct Reference {
  39     Reference()
  40       : Def(false), Use(false), IndirectDef(false), IndirectUse(false) {}
  41
  42     Reference &operator|=(const Reference &Other) {
  43       Def |= Other.Def;
  44       IndirectDef |= Other.IndirectDef;
  45       Use |= Other.Use;
  46       IndirectUse |= Other.IndirectUse;
  47       return *this;
  48     }
  49
  50     operator bool() const { return Def || Use; }
  51
  52     // True if the register is defined or used in some form, either directly or
  53     // via a sub- or super-register.
  54     bool Def;
  55     bool Use;
  56
  57     // True if the register is defined or used indirectly, by a sub- or
  58     // super-register.
  59     bool IndirectDef;
  60     bool IndirectUse;
  61   };
  62
  63   class SystemZElimCompare : public MachineFunctionPass {
  64   public:
  65     static char ID;
  66     SystemZElimCompare(const SystemZTargetMachine &tm)
  67       : MachineFunctionPass(ID), TII(0), TRI(0) {}
  68
  69     virtual const char *getPassName() const {
  70       return "SystemZ Comparison Elimination";
  71     }
  72
  73     bool processBlock(MachineBasicBlock *MBB);
  74     bool runOnMachineFunction(MachineFunction &F);
  75
  76   private:
  77     Reference getRegReferences(MachineInstr *MI, unsigned Reg);
  78     bool convertToBRCT(MachineInstr *MI, MachineInstr *Compare,
  79                        SmallVectorImpl<MachineInstr *> &CCUsers);
  80     bool convertToLoadAndTest(MachineInstr *MI);
  81     bool adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare,
  82                                SmallVectorImpl<MachineInstr *> &CCUsers);
  83     bool optimizeCompareZero(MachineInstr *Compare,
  84                              SmallVectorImpl<MachineInstr *> &CCUsers);
  85     bool fuseCompareAndBranch(MachineInstr *Compare,
  86                               SmallVectorImpl<MachineInstr *> &CCUsers);
  87
  88     const SystemZInstrInfo *TII;
  89     const TargetRegisterInfo *TRI;
  90   };
  91
  92   char SystemZElimCompare::ID = 0;
  93 } // end of anonymous namespace
  94
  95 FunctionPass *llvm::createSystemZElimComparePass(SystemZTargetMachine &TM) {
  96   return new SystemZElimCompare(TM);
  97 }
  98
  99 // Return true if CC is live out of MBB.
 100 static bool isCCLiveOut(MachineBasicBlock *MBB) {
 101   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 102          SE = MBB->succ_end(); SI != SE; ++SI)
 103     if ((*SI)->isLiveIn(SystemZ::CC))
 104       return true;
 105   return false;
 106 }
 107
 108 // Return true if any CC result of MI would reflect the value of subreg
 109 // SubReg of Reg.
 110 static bool resultTests(MachineInstr *MI, unsigned Reg, unsigned SubReg) {
 111   if (MI->getNumOperands() > 0 &&
 112       MI->getOperand(0).isReg() &&
 113       MI->getOperand(0).isDef() &&
 114       MI->getOperand(0).getReg() == Reg &&
 115       MI->getOperand(0).getSubReg() == SubReg)
 116     return true;
 117
 118   switch (MI->getOpcode()) {
 119   case SystemZ::LR:
 120   case SystemZ::LGR:
 121   case SystemZ::LGFR:
 122   case SystemZ::LTR:
 123   case SystemZ::LTGR:
 124   case SystemZ::LTGFR:
 125     if (MI->getOperand(1).getReg() == Reg &&
 126         MI->getOperand(1).getSubReg() == SubReg)
 127       return true;
 128   }
 129
 130   return false;
 131 }
 132
 133 // Describe the references to Reg in MI, including sub- and super-registers.
 134 Reference SystemZElimCompare::getRegReferences(MachineInstr *MI, unsigned Reg) {
 135   Reference Ref;
 136   for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) {
 137     const MachineOperand &MO = MI->getOperand(I);
 138     if (MO.isReg()) {
 139       if (unsigned MOReg = MO.getReg()) {
 140         if (MOReg == Reg || TRI->regsOverlap(MOReg, Reg)) {
 141           if (MO.isUse()) {
 142             Ref.Use = true;
 143             Ref.IndirectUse |= (MOReg != Reg);
 144           }
 145           if (MO.isDef()) {
 146             Ref.Def = true;
 147             Ref.IndirectDef |= (MOReg != Reg);
 148           }
 149         }
 150       }
 151     }
 152   }
 153   return Ref;
 154 }
 155
 156 // Compare compares the result of MI against zero.  If MI is an addition
 157 // of -1 and if CCUsers is a single branch on nonzero, eliminate the addition
 158 // and convert the branch to a BRCT(G).  Return true on success.
 159 bool
 160 SystemZElimCompare::convertToBRCT(MachineInstr *MI, MachineInstr *Compare,
 161                                   SmallVectorImpl<MachineInstr *> &CCUsers) {
 162   // Check whether we have an addition of -1.
 163   unsigned Opcode = MI->getOpcode();
 164   unsigned BRCT;
 165   if (Opcode == SystemZ::AHI)
 166     BRCT = SystemZ::BRCT;
 167   else if (Opcode == SystemZ::AGHI)
 168     BRCT = SystemZ::BRCTG;
 169   else
 170     return false;
 171   if (MI->getOperand(2).getImm() != -1)
 172     return false;
 173
 174   // Check whether we have a single JLH.
 175   if (CCUsers.size() != 1)
 176     return false;
 177   MachineInstr *Branch = CCUsers[0];
 178   if (Branch->getOpcode() != SystemZ::BRC ||
 179       Branch->getOperand(0).getImm() != SystemZ::CCMASK_ICMP ||
 180       Branch->getOperand(1).getImm() != SystemZ::CCMASK_CMP_NE)
 181     return false;
 182
 183   // We already know that there are no references to the register between
 184   // MI and Compare.  Make sure that there are also no references between
 185   // Compare and Branch.
 186   unsigned SrcReg = Compare->getOperand(0).getReg();
 187   MachineBasicBlock::iterator MBBI = Compare, MBBE = Branch;
 188   for (++MBBI; MBBI != MBBE; ++MBBI)
 189     if (getRegReferences(MBBI, SrcReg))
 190       return false;
 191
 192   // The transformation is OK.  Rebuild Branch as a BRCT(G).
 193   MachineOperand Target(Branch->getOperand(2));
 194   Branch->RemoveOperand(2);
 195   Branch->RemoveOperand(1);
 196   Branch->RemoveOperand(0);
 197   Branch->setDesc(TII->get(BRCT));
 198   MachineInstrBuilder(*Branch->getParent()->getParent(), Branch)
 199     .addOperand(MI->getOperand(0))
 200     .addOperand(MI->getOperand(1))
 201     .addOperand(Target)
 202     .addReg(SystemZ::CC, RegState::ImplicitDefine);
 203   MI->removeFromParent();
 204   return true;
 205 }
 206
 207 // If MI is a load instruction, try to convert it into a LOAD AND TEST.
 208 // Return true on success.
 209 bool SystemZElimCompare::convertToLoadAndTest(MachineInstr *MI) {
 210   unsigned Opcode = TII->getLoadAndTest(MI->getOpcode());
 211   if (!Opcode)
 212     return false;
 213
 214   MI->setDesc(TII->get(Opcode));
 215   MachineInstrBuilder(*MI->getParent()->getParent(), MI)
 216     .addReg(SystemZ::CC, RegState::ImplicitDefine);
 217   return true;
 218 }
 219
 220 // The CC users in CCUsers are testing the result of a comparison of some
 221 // value X against zero and we know that any CC value produced by MI
 222 // would also reflect the value of X.  Try to adjust CCUsers so that
 223 // they test the result of MI directly, returning true on success.
 224 // Leave everything unchanged on failure.
 225 bool SystemZElimCompare::
 226 adjustCCMasksForInstr(MachineInstr *MI, MachineInstr *Compare,
 227                       SmallVectorImpl<MachineInstr *> &CCUsers) {
 228   int Opcode = MI->getOpcode();
 229   const MCInstrDesc &Desc = TII->get(Opcode);
 230   unsigned MIFlags = Desc.TSFlags;
 231
 232   // See which compare-style condition codes are available.
 233   unsigned ReusableCCMask = 0;
 234   if (MIFlags & SystemZII::CCHasZero)
 235     ReusableCCMask |= SystemZ::CCMASK_CMP_EQ;
 236
 237   // For unsigned comparisons with zero, only equality makes sense.
 238   unsigned CompareFlags = Compare->getDesc().TSFlags;
 239   if (!(CompareFlags & SystemZII::IsLogical) &&
 240       (MIFlags & SystemZII::CCHasOrder))
 241     ReusableCCMask |= SystemZ::CCMASK_CMP_LT | SystemZ::CCMASK_CMP_GT;
 242
 243   if (ReusableCCMask == 0)
 244     return false;
 245
 246   unsigned CCValues = SystemZII::getCCValues(MIFlags);
 247   assert((ReusableCCMask & ~CCValues) == 0 && "Invalid CCValues");
 248
 249   // Now check whether these flags are enough for all users.
 250   SmallVector<MachineOperand *, 4> AlterMasks;
 251   for (unsigned int I = 0, E = CCUsers.size(); I != E; ++I) {
 252     MachineInstr *MI = CCUsers[I];
 253
 254     // Fail if this isn't a use of CC that we understand.
 255     unsigned Flags = MI->getDesc().TSFlags;
 256     unsigned FirstOpNum;
 257     if (Flags & SystemZII::CCMaskFirst)
 258       FirstOpNum = 0;
 259     else if (Flags & SystemZII::CCMaskLast)
 260       FirstOpNum = MI->getNumExplicitOperands() - 2;
 261     else
 262       return false;
 263
 264     // Check whether the instruction predicate treats all CC values
 265     // outside of ReusableCCMask in the same way.  In that case it
 266     // doesn't matter what those CC values mean.
 267     unsigned CCValid = MI->getOperand(FirstOpNum).getImm();
 268     unsigned CCMask = MI->getOperand(FirstOpNum + 1).getImm();
 269     unsigned OutValid = ~ReusableCCMask & CCValid;
 270     unsigned OutMask = ~ReusableCCMask & CCMask;
 271     if (OutMask != 0 && OutMask != OutValid)
 272       return false;
 273
 274     AlterMasks.push_back(&MI->getOperand(FirstOpNum));
 275     AlterMasks.push_back(&MI->getOperand(FirstOpNum + 1));
 276   }
 277
 278   // All users are OK.  Adjust the masks for MI.
 279   for (unsigned I = 0, E = AlterMasks.size(); I != E; I += 2) {
 280     AlterMasks[I]->setImm(CCValues);
 281     unsigned CCMask = AlterMasks[I + 1]->getImm();
 282     if (CCMask & ~ReusableCCMask)
 283       AlterMasks[I + 1]->setImm((CCMask & ReusableCCMask) |
 284                                 (CCValues & ~ReusableCCMask));
 285   }
 286
 287   // CC is now live after MI.
 288   int CCDef = MI->findRegisterDefOperandIdx(SystemZ::CC, false, true, TRI);
 289   assert(CCDef >= 0 && "Couldn't find CC set");
 290   MI->getOperand(CCDef).setIsDead(false);
 291
 292   // Clear any intervening kills of CC.
 293   MachineBasicBlock::iterator MBBI = MI, MBBE = Compare;
 294   for (++MBBI; MBBI != MBBE; ++MBBI)
 295     MBBI->clearRegisterKills(SystemZ::CC, TRI);
 296
 297   return true;
 298 }
 299
 300 // Try to optimize cases where comparison instruction Compare is testing
 301 // a value against zero.  Return true on success and if Compare should be
 302 // deleted as dead.  CCUsers is the list of instructions that use the CC
 303 // value produced by Compare.
 304 bool SystemZElimCompare::
 305 optimizeCompareZero(MachineInstr *Compare,
 306                     SmallVectorImpl<MachineInstr *> &CCUsers) {
 307   // Check whether this is a comparison against zero.
 308   if (Compare->getNumExplicitOperands() != 2 ||
 309       !Compare->getOperand(1).isImm() ||
 310       Compare->getOperand(1).getImm() != 0)
 311     return false;
 312
 313   // Search back for CC results that are based on the first operand.
 314   unsigned SrcReg = Compare->getOperand(0).getReg();
 315   unsigned SrcSubReg = Compare->getOperand(0).getSubReg();
 316   MachineBasicBlock *MBB = Compare->getParent();
 317   MachineBasicBlock::iterator MBBI = Compare, MBBE = MBB->begin();
 318   Reference CCRefs;
 319   Reference SrcRefs;
 320   while (MBBI != MBBE) {
 321     --MBBI;
 322     MachineInstr *MI = MBBI;
 323     if (resultTests(MI, SrcReg, SrcSubReg)) {
 324       // Try to remove both MI and Compare by converting a branch to BRCT(G).
 325       // We don't care in this case whether CC is modified between MI and
 326       // Compare.
 327       if (!CCRefs.Use && !SrcRefs && convertToBRCT(MI, Compare, CCUsers)) {
 328         BranchOnCounts += 1;
 329         return true;
 330       }
 331       // Try to eliminate Compare by reusing a CC result from MI.
 332       if ((!CCRefs && convertToLoadAndTest(MI)) ||
 333           (!CCRefs.Def && adjustCCMasksForInstr(MI, Compare, CCUsers))) {
 334         EliminatedComparisons += 1;
 335         return true;
 336       }
 337     }
 338     SrcRefs |= getRegReferences(MI, SrcReg);
 339     if (SrcRefs.Def)
 340       return false;
 341     CCRefs |= getRegReferences(MI, SystemZ::CC);
 342     if (CCRefs.Use && CCRefs.Def)
 343       return false;
 344   }
 345   return false;
 346 }
 347
 348 // Try to fuse comparison instruction Compare into a later branch.
 349 // Return true on success and if Compare is therefore redundant.
 350 bool SystemZElimCompare::
 351 fuseCompareAndBranch(MachineInstr *Compare,
 352                      SmallVectorImpl<MachineInstr *> &CCUsers) {
 353   // See whether we have a comparison that can be fused.
 354   unsigned FusedOpcode = TII->getCompareAndBranch(Compare->getOpcode(),
 355                                                   Compare);
 356   if (!FusedOpcode)
 357     return false;
 358
 359   // See whether we have a single branch with which to fuse.
 360   if (CCUsers.size() != 1)
 361     return false;
 362   MachineInstr *Branch = CCUsers[0];
 363   if (Branch->getOpcode() != SystemZ::BRC)
 364     return false;
 365
 366   // Make sure that the operands are available at the branch.
 367   unsigned SrcReg = Compare->getOperand(0).getReg();
 368   unsigned SrcReg2 = (Compare->getOperand(1).isReg() ?
 369                       Compare->getOperand(1).getReg() : 0);
 370   MachineBasicBlock::iterator MBBI = Compare, MBBE = Branch;
 371   for (++MBBI; MBBI != MBBE; ++MBBI)
 372     if (MBBI->modifiesRegister(SrcReg, TRI) ||
 373         (SrcReg2 && MBBI->modifiesRegister(SrcReg2, TRI)))
 374       return false;
 375
 376   // Read the branch mask and target.
 377   MachineOperand CCMask(MBBI->getOperand(1));
 378   MachineOperand Target(MBBI->getOperand(2));
 379   assert((CCMask.getImm() & ~SystemZ::CCMASK_ICMP) == 0 &&
 380          "Invalid condition-code mask for integer comparison");
 381
 382   // Clear out all current operands.
 383   int CCUse = MBBI->findRegisterUseOperandIdx(SystemZ::CC, false, TRI);
 384   assert(CCUse >= 0 && "BRC must use CC");
 385   Branch->RemoveOperand(CCUse);
 386   Branch->RemoveOperand(2);
 387   Branch->RemoveOperand(1);
 388   Branch->RemoveOperand(0);
 389
 390   // Rebuild Branch as a fused compare and branch.
 391   Branch->setDesc(TII->get(FusedOpcode));
 392   MachineInstrBuilder(*Branch->getParent()->getParent(), Branch)
 393     .addOperand(Compare->getOperand(0))
 394     .addOperand(Compare->getOperand(1))
 395     .addOperand(CCMask)
 396     .addOperand(Target)
 397     .addReg(SystemZ::CC, RegState::ImplicitDefine);
 398
 399   // Clear any intervening kills of SrcReg and SrcReg2.
 400   MBBI = Compare;
 401   for (++MBBI; MBBI != MBBE; ++MBBI) {
 402     MBBI->clearRegisterKills(SrcReg, TRI);
 403     if (SrcReg2)
 404       MBBI->clearRegisterKills(SrcReg2, TRI);
 405   }
 406   FusedComparisons += 1;
 407   return true;
 408 }
 409
 410 // Process all comparison instructions in MBB.  Return true if something
 411 // changed.
 412 bool SystemZElimCompare::processBlock(MachineBasicBlock *MBB) {
 413   bool Changed = false;
 414
 415   // Walk backwards through the block looking for comparisons, recording
 416   // all CC users as we go.  The subroutines can delete Compare and
 417   // instructions before it.
 418   bool CompleteCCUsers = !isCCLiveOut(MBB);
 419   SmallVector<MachineInstr *, 4> CCUsers;
 420   MachineBasicBlock::iterator MBBI = MBB->end();
 421   while (MBBI != MBB->begin()) {
 422     MachineInstr *MI = --MBBI;
 423     if (CompleteCCUsers &&
 424         MI->isCompare() &&
 425         (optimizeCompareZero(MI, CCUsers) ||
 426          fuseCompareAndBranch(MI, CCUsers))) {
 427       ++MBBI;
 428       MI->removeFromParent();
 429       Changed = true;
 430       CCUsers.clear();
 431       CompleteCCUsers = true;
 432       continue;
 433     }
 434
 435     Reference CCRefs(getRegReferences(MI, SystemZ::CC));
 436     if (CCRefs.Def) {
 437       CCUsers.clear();
 438       CompleteCCUsers = !CCRefs.IndirectDef;
 439     }
 440     if (CompleteCCUsers && CCRefs.Use)
 441       CCUsers.push_back(MI);
 442   }
 443   return Changed;
 444 }
 445
 446 bool SystemZElimCompare::runOnMachineFunction(MachineFunction &F) {
 447   TII = static_cast<const SystemZInstrInfo *>(F.getTarget().getInstrInfo());
 448   TRI = &TII->getRegisterInfo();
 449
 450   bool Changed = false;
 451   for (MachineFunction::iterator MFI = F.begin(), MFE = F.end();
 452        MFI != MFE; ++MFI)
 453     Changed |= processBlock(MFI);
 454
 455   return Changed;
 456 }