← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/Target/SystemZ/SystemZElimCompare.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

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