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