SystemZElimCompare.cpp revision 9b05c709c65ba05645853ca49bc2a1ea8b554f37 
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
29using namespace llvm;
30
31STATISTIC(EliminatedComparisons, "Number of eliminated comparisons");
32STATISTIC(FusedComparisons, "Number of fused compare-and-branch instructions");
33
34namespace {
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
64FunctionPass *llvm::createSystemZElimComparePass(SystemZTargetMachine &TM) {
65  return new SystemZElimCompare(TM);
66}
67
68// Return true if CC is live out of MBB.
69static 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.
79static 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.
104bool 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.
120bool SystemZElimCompare::
121adjustCCMasksForInstr(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.
199bool SystemZElimCompare::
200optimizeCompareZero(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.
234bool SystemZElimCompare::
235fuseCompareAndBranch(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.
296bool 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
331bool 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}
342