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