Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/OptimizePHIs.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- OptimizePHIs.cpp - Optimize machine instruction PHIs ---------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This pass optimizes machine instruction PHIs to take advantage of
10
// opportunities created during DAG legalization.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/ADT/SmallPtrSet.h"
15
#include "llvm/ADT/Statistic.h"
16
#include "llvm/CodeGen/MachineBasicBlock.h"
17
#include "llvm/CodeGen/MachineFunction.h"
18
#include "llvm/CodeGen/MachineFunctionPass.h"
19
#include "llvm/CodeGen/MachineInstr.h"
20
#include "llvm/CodeGen/MachineOperand.h"
21
#include "llvm/CodeGen/MachineRegisterInfo.h"
22
#include "llvm/CodeGen/TargetRegisterInfo.h"
23
#include "llvm/CodeGen/TargetSubtargetInfo.h"
24
#include "llvm/Pass.h"
25
#include <cassert>
26
27
using namespace llvm;
28
29
#define DEBUG_TYPE "opt-phis"
30
31
STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
32
STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
33
34
namespace {
35
36
  class OptimizePHIs : public MachineFunctionPass {
37
    MachineRegisterInfo *MRI;
38
    const TargetInstrInfo *TII;
39
40
  public:
41
    static char ID; // Pass identification
42
43
34.5k
    OptimizePHIs() : MachineFunctionPass(ID) {
44
34.5k
      initializeOptimizePHIsPass(*PassRegistry::getPassRegistry());
45
34.5k
    }
46
47
    bool runOnMachineFunction(MachineFunction &Fn) override;
48
49
34.2k
    void getAnalysisUsage(AnalysisUsage &AU) const override {
50
34.2k
      AU.setPreservesCFG();
51
34.2k
      MachineFunctionPass::getAnalysisUsage(AU);
52
34.2k
    }
53
54
  private:
55
    using InstrSet = SmallPtrSet<MachineInstr *, 16>;
56
    using InstrSetIterator = SmallPtrSetIterator<MachineInstr *>;
57
58
    bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
59
                               InstrSet &PHIsInCycle);
60
    bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
61
    bool OptimizeBB(MachineBasicBlock &MBB);
62
  };
63
64
} // end anonymous namespace
65
66
char OptimizePHIs::ID = 0;
67
68
char &llvm::OptimizePHIsID = OptimizePHIs::ID;
69
70
INITIALIZE_PASS(OptimizePHIs, DEBUG_TYPE,
71
                "Optimize machine instruction PHIs", false, false)
72
73
489k
bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
74
489k
  if (skipFunction(Fn.getFunction()))
75
270
    return false;
76
489k
77
489k
  MRI = &Fn.getRegInfo();
78
489k
  TII = Fn.getSubtarget().getInstrInfo();
79
489k
80
489k
  // Find dead PHI cycles and PHI cycles that can be replaced by a single
81
489k
  // value.  InstCombine does these optimizations, but DAG legalization may
82
489k
  // introduce new opportunities, e.g., when i64 values are split up for
83
489k
  // 32-bit targets.
84
489k
  bool Changed = false;
85
3.07M
  for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; 
++I2.58M
)
86
2.58M
    Changed |= OptimizeBB(*I);
87
489k
88
489k
  return Changed;
89
489k
}
90
91
/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
92
/// are copies of SingleValReg, possibly via copies through other PHIs. If
93
/// SingleValReg is zero on entry, it is set to the register with the single
94
/// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that
95
/// have been scanned. PHIs may be grouped by cycle, several cycles or chains.
96
bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
97
                                         unsigned &SingleValReg,
98
997k
                                         InstrSet &PHIsInCycle) {
99
997k
  assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
100
997k
  unsigned DstReg = MI->getOperand(0).getReg();
101
997k
102
997k
  // See if we already saw this register.
103
997k
  if (!PHIsInCycle.insert(MI).second)
104
86.0k
    return true;
105
911k
106
911k
  // Don't scan crazily complex things.
107
911k
  if (PHIsInCycle.size() == 16)
108
1.80k
    return false;
109
909k
110
909k
  // Scan the PHI operands.
111
1.69M
  
for (unsigned i = 1; 909k
i != MI->getNumOperands();
i += 2786k
) {
112
1.66M
    unsigned SrcReg = MI->getOperand(i).getReg();
113
1.66M
    if (SrcReg == DstReg)
114
765
      continue;
115
1.66M
    MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
116
1.66M
117
1.66M
    // Skip over register-to-register moves.
118
1.66M
    if (SrcMI && SrcMI->isCopy() &&
119
1.66M
        
!SrcMI->getOperand(0).getSubReg()535k
&&
120
1.66M
        
!SrcMI->getOperand(1).getSubReg()535k
&&
121
1.66M
        
TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg())517k
) {
122
360k
      SrcReg = SrcMI->getOperand(1).getReg();
123
360k
      SrcMI = MRI->getVRegDef(SrcReg);
124
360k
    }
125
1.66M
    if (!SrcMI)
126
0
      return false;
127
1.66M
128
1.66M
    if (SrcMI->isPHI()) {
129
359k
      if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
130
243k
        return false;
131
1.30M
    } else {
132
1.30M
      // Fail if there is more than one non-phi/non-move register.
133
1.30M
      if (SingleValReg != 0 && 
SingleValReg != SrcReg668k
)
134
634k
        return false;
135
670k
      SingleValReg = SrcReg;
136
670k
    }
137
1.66M
  }
138
909k
  
return true30.8k
;
139
909k
}
140
141
/// IsDeadPHICycle - Check if the register defined by a PHI is only used by
142
/// other PHIs in a cycle.
143
889k
bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
144
889k
  assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
145
889k
  unsigned DstReg = MI->getOperand(0).getReg();
146
889k
  assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
147
889k
         "PHI destination is not a virtual register");
148
889k
149
889k
  // See if we already saw this register.
150
889k
  if (!PHIsInCycle.insert(MI).second)
151
34.9k
    return true;
152
854k
153
854k
  // Don't scan crazily complex things.
154
854k
  if (PHIsInCycle.size() == 16)
155
1.94k
    return false;
156
852k
157
886k
  
for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DstReg))852k
{
158
886k
    if (!UseMI.isPHI() || 
!IsDeadPHICycle(&UseMI, PHIsInCycle)252k
)
159
835k
      return false;
160
886k
  }
161
852k
162
852k
  
return true16.5k
;
163
852k
}
164
165
/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
166
/// a single value.
167
2.58M
bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
168
2.58M
  bool Changed = false;
169
2.58M
  for (MachineBasicBlock::iterator
170
3.22M
         MII = MBB.begin(), E = MBB.end(); MII != E; ) {
171
3.15M
    MachineInstr *MI = &*MII++;
172
3.15M
    if (!MI->isPHI())
173
2.51M
      break;
174
637k
175
637k
    // Check for single-value PHI cycles.
176
637k
    unsigned SingleValReg = 0;
177
637k
    InstrSet PHIsInCycle;
178
637k
    if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
179
637k
        
SingleValReg != 0841
) {
180
840
      unsigned OldReg = MI->getOperand(0).getReg();
181
840
      if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg)))
182
4
        continue;
183
836
184
836
      MRI->replaceRegWith(OldReg, SingleValReg);
185
836
      MI->eraseFromParent();
186
836
187
836
      // The kill flags on OldReg and SingleValReg may no longer be correct.
188
836
      MRI->clearKillFlags(SingleValReg);
189
836
190
836
      ++NumPHICycles;
191
836
      Changed = true;
192
836
      continue;
193
836
    }
194
636k
195
636k
    // Check for dead PHI cycles.
196
636k
    PHIsInCycle.clear();
197
636k
    if (IsDeadPHICycle(MI, PHIsInCycle)) {
198
611
      for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
199
1.59k
           PI != PE; 
++PI988
) {
200
988
        MachineInstr *PhiMI = *PI;
201
988
        if (MII == PhiMI)
202
0
          ++MII;
203
988
        PhiMI->eraseFromParent();
204
988
      }
205
611
      ++NumDeadPHICycles;
206
611
      Changed = true;
207
611
    }
208
636k
  }
209
2.58M
  return Changed;
210
2.58M
}