Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/MachineSSAUpdater.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MachineSSAUpdater.cpp - Unstructured SSA Update Tool ---------------===//
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 file implements the MachineSSAUpdater class. It's based on SSAUpdater
10
// class in lib/Transforms/Utils.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/CodeGen/MachineSSAUpdater.h"
15
#include "llvm/ADT/DenseMap.h"
16
#include "llvm/ADT/SmallVector.h"
17
#include "llvm/CodeGen/MachineBasicBlock.h"
18
#include "llvm/CodeGen/MachineFunction.h"
19
#include "llvm/CodeGen/MachineInstr.h"
20
#include "llvm/CodeGen/MachineInstrBuilder.h"
21
#include "llvm/CodeGen/MachineOperand.h"
22
#include "llvm/CodeGen/MachineRegisterInfo.h"
23
#include "llvm/CodeGen/TargetInstrInfo.h"
24
#include "llvm/CodeGen/TargetOpcodes.h"
25
#include "llvm/CodeGen/TargetSubtargetInfo.h"
26
#include "llvm/IR/DebugLoc.h"
27
#include "llvm/Support/Debug.h"
28
#include "llvm/Support/ErrorHandling.h"
29
#include "llvm/Support/raw_ostream.h"
30
#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
31
#include <utility>
32
33
using namespace llvm;
34
35
#define DEBUG_TYPE "machine-ssaupdater"
36
37
using AvailableValsTy = DenseMap<MachineBasicBlock *, unsigned>;
38
39
5.70k
static AvailableValsTy &getAvailableVals(void *AV) {
40
5.70k
  return *static_cast<AvailableValsTy*>(AV);
41
5.70k
}
42
43
MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF,
44
                                     SmallVectorImpl<MachineInstr*> *NewPHI)
45
  : InsertedPHIs(NewPHI), TII(MF.getSubtarget().getInstrInfo()),
46
198k
    MRI(&MF.getRegInfo()) {}
47
48
198k
MachineSSAUpdater::~MachineSSAUpdater() {
49
198k
  delete static_cast<AvailableValsTy*>(AV);
50
198k
}
51
52
/// Initialize - Reset this object to get ready for a new set of SSA
53
/// updates.  ProtoValue is the value used to name PHI nodes.
54
1.20k
void MachineSSAUpdater::Initialize(unsigned V) {
55
1.20k
  if (!AV)
56
938
    AV = new AvailableValsTy();
57
265
  else
58
265
    getAvailableVals(AV).clear();
59
1.20k
60
1.20k
  VR = V;
61
1.20k
  VRC = MRI->getRegClass(VR);
62
1.20k
}
63
64
/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for
65
/// the specified block.
66
704
bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const {
67
704
  return getAvailableVals(AV).count(BB);
68
704
}
69
70
/// AddAvailableValue - Indicate that a rewritten value is available in the
71
/// specified block with the specified value.
72
3.21k
void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) {
73
3.21k
  getAvailableVals(AV)[BB] = V;
74
3.21k
}
75
76
/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
77
/// live at the end of the specified block.
78
272
unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) {
79
272
  return GetValueAtEndOfBlockInternal(BB);
80
272
}
81
82
static
83
unsigned LookForIdenticalPHI(MachineBasicBlock *BB,
84
159
        SmallVectorImpl<std::pair<MachineBasicBlock *, unsigned>> &PredValues) {
85
159
  if (BB->empty())
86
0
    return 0;
87
159
88
159
  MachineBasicBlock::iterator I = BB->begin();
89
159
  if (!I->isPHI())
90
19
    return 0;
91
140
92
140
  AvailableValsTy AVals;
93
440
  for (unsigned i = 0, e = PredValues.size(); i != e; 
++i300
)
94
300
    AVals[PredValues[i].first] = PredValues[i].second;
95
1.37k
  while (I != BB->end() && I->isPHI()) {
96
1.30k
    bool Same = true;
97
1.45k
    for (unsigned i = 1, e = I->getNumOperands(); i != e; 
i += 2150
) {
98
1.38k
      unsigned SrcReg = I->getOperand(i).getReg();
99
1.38k
      MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB();
100
1.38k
      if (AVals[SrcBB] != SrcReg) {
101
1.23k
        Same = false;
102
1.23k
        break;
103
1.23k
      }
104
1.38k
    }
105
1.30k
    if (Same)
106
67
      return I->getOperand(0).getReg();
107
1.23k
    ++I;
108
1.23k
  }
109
140
  
return 073
;
110
140
}
111
112
/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define
113
/// a value of the given register class at the start of the specified basic
114
/// block. It returns the virtual register defined by the instruction.
115
static
116
MachineInstrBuilder InsertNewDef(unsigned Opcode,
117
                           MachineBasicBlock *BB, MachineBasicBlock::iterator I,
118
                           const TargetRegisterClass *RC,
119
                           MachineRegisterInfo *MRI,
120
376
                           const TargetInstrInfo *TII) {
121
376
  unsigned NewVR = MRI->createVirtualRegister(RC);
122
376
  return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR);
123
376
}
124
125
/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
126
/// is live in the middle of the specified block.
127
///
128
/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
129
/// important case: if there is a definition of the rewritten value after the
130
/// 'use' in BB.  Consider code like this:
131
///
132
///      X1 = ...
133
///   SomeBB:
134
///      use(X)
135
///      X2 = ...
136
///      br Cond, SomeBB, OutBB
137
///
138
/// In this case, there are two values (X1 and X2) added to the AvailableVals
139
/// set by the client of the rewriter, and those values are both live out of
140
/// their respective blocks.  However, the use of X happens in the *middle* of
141
/// a block.  Because of this, we need to insert a new PHI node in SomeBB to
142
/// merge the appropriate values, and this value isn't live out of the block.
143
704
unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) {
144
704
  // If there is no definition of the renamed variable in this block, just use
145
704
  // GetValueAtEndOfBlock to do our work.
146
704
  if (!HasValueForBlock(BB))
147
232
    return GetValueAtEndOfBlockInternal(BB);
148
472
149
472
  // If there are no predecessors, just return undef.
150
472
  if (BB->pred_empty()) {
151
0
    // Insert an implicit_def to represent an undef value.
152
0
    MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
153
0
                                        BB, BB->getFirstTerminator(),
154
0
                                        VRC, MRI, TII);
155
0
    return NewDef->getOperand(0).getReg();
156
0
  }
157
472
158
472
  // Otherwise, we have the hard case.  Get the live-in values for each
159
472
  // predecessor.
160
472
  SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues;
161
472
  unsigned SingularValue = 0;
162
472
163
472
  bool isFirstPred = true;
164
472
  for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
165
1.44k
         E = BB->pred_end(); PI != E; 
++PI973
) {
166
973
    MachineBasicBlock *PredBB = *PI;
167
973
    unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);
168
973
    PredValues.push_back(std::make_pair(PredBB, PredVal));
169
973
170
973
    // Compute SingularValue.
171
973
    if (isFirstPred) {
172
472
      SingularValue = PredVal;
173
472
      isFirstPred = false;
174
501
    } else if (PredVal != SingularValue)
175
453
      SingularValue = 0;
176
973
  }
177
472
178
472
  // Otherwise, if all the merged values are the same, just use it.
179
472
  if (SingularValue != 0)
180
313
    return SingularValue;
181
159
182
159
  // If an identical PHI is already in BB, just reuse it.
183
159
  unsigned DupPHI = LookForIdenticalPHI(BB, PredValues);
184
159
  if (DupPHI)
185
67
    return DupPHI;
186
92
187
92
  // Otherwise, we do need a PHI: insert one now.
188
92
  MachineBasicBlock::iterator Loc = BB->empty() ? 
BB->end()0
: BB->begin();
189
92
  MachineInstrBuilder InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB,
190
92
                                                 Loc, VRC, MRI, TII);
191
92
192
92
  // Fill in all the predecessors of the PHI.
193
554
  for (unsigned i = 0, e = PredValues.size(); i != e; 
++i462
)
194
462
    InsertedPHI.addReg(PredValues[i].second).addMBB(PredValues[i].first);
195
92
196
92
  // See if the PHI node can be merged to a single value.  This can happen in
197
92
  // loop cases when we get a PHI of itself and one other value.
198
92
  if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
199
0
    InsertedPHI->eraseFromParent();
200
0
    return ConstVal;
201
0
  }
202
92
203
92
  // If the client wants to know about all new instructions, tell it.
204
92
  if (InsertedPHIs) 
InsertedPHIs->push_back(InsertedPHI)22
;
205
92
206
92
  LLVM_DEBUG(dbgs() << "  Inserted PHI: " << *InsertedPHI << "\n");
207
92
  return InsertedPHI->getOperand(0).getReg();
208
92
}
209
210
static
211
MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI,
212
42
                                         MachineOperand *U) {
213
144
  for (unsigned i = 1, e = MI->getNumOperands(); i != e; 
i += 2102
) {
214
144
    if (&MI->getOperand(i) == U)
215
42
      return MI->getOperand(i+1).getMBB();
216
144
  }
217
42
218
42
  
llvm_unreachable0
("MachineOperand::getParent() failure?");
219
42
}
220
221
/// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
222
/// which use their value in the corresponding predecessor.
223
222
void MachineSSAUpdater::RewriteUse(MachineOperand &U) {
224
222
  MachineInstr *UseMI = U.getParent();
225
222
  unsigned NewVR = 0;
226
222
  if (UseMI->isPHI()) {
227
42
    MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U);
228
42
    NewVR = GetValueAtEndOfBlockInternal(SourceBB);
229
180
  } else {
230
180
    NewVR = GetValueInMiddleOfBlock(UseMI->getParent());
231
180
  }
232
222
233
222
  U.setReg(NewVR);
234
222
}
235
236
/// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl
237
/// template, specialized for MachineSSAUpdater.
238
namespace llvm {
239
240
template<>
241
class SSAUpdaterTraits<MachineSSAUpdater> {
242
public:
243
  using BlkT = MachineBasicBlock;
244
  using ValT = unsigned;
245
  using PhiT = MachineInstr;
246
  using BlkSucc_iterator = MachineBasicBlock::succ_iterator;
247
248
1.34k
  static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
249
1.34k
  static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
250
251
  /// Iterator for PHI operands.
252
  class PHI_iterator {
253
  private:
254
    MachineInstr *PHI;
255
    unsigned idx;
256
257
  public:
258
    explicit PHI_iterator(MachineInstr *P) // begin iterator
259
1.61k
      : PHI(P), idx(1) {}
260
    PHI_iterator(MachineInstr *P, bool) // end iterator
261
1.61k
      : PHI(P), idx(PHI->getNumOperands()) {}
262
263
79
    PHI_iterator &operator++() { idx += 2; return *this; }
264
1.69k
    bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
265
1.69k
    bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
266
267
1.69k
    unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); }
268
269
1.69k
    MachineBasicBlock *getIncomingBlock() {
270
1.69k
      return PHI->getOperand(idx+1).getMBB();
271
1.69k
    }
272
  };
273
274
1.61k
  static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
275
276
1.61k
  static inline PHI_iterator PHI_end(PhiT *PHI) {
277
1.61k
    return PHI_iterator(PHI, true);
278
1.61k
  }
279
280
  /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
281
  /// vector.
282
  static void FindPredecessorBlocks(MachineBasicBlock *BB,
283
633
                                    SmallVectorImpl<MachineBasicBlock*> *Preds){
284
633
    for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
285
1.71k
           E = BB->pred_end(); PI != E; 
++PI1.08k
)
286
1.08k
      Preds->push_back(*PI);
287
633
  }
288
289
  /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register.
290
  /// Add it into the specified block and return the register.
291
  static unsigned GetUndefVal(MachineBasicBlock *BB,
292
0
                              MachineSSAUpdater *Updater) {
293
0
    // Insert an implicit_def to represent an undef value.
294
0
    MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
295
0
                                        BB, BB->getFirstTerminator(),
296
0
                                        Updater->VRC, Updater->MRI,
297
0
                                        Updater->TII);
298
0
    return NewDef->getOperand(0).getReg();
299
0
  }
300
301
  /// CreateEmptyPHI - Create a PHI instruction that defines a new register.
302
  /// Add it into the specified block and return the register.
303
  static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds,
304
284
                                 MachineSSAUpdater *Updater) {
305
284
    MachineBasicBlock::iterator Loc = BB->empty() ? 
BB->end()1
:
BB->begin()283
;
306
284
    MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
307
284
                                     Updater->VRC, Updater->MRI,
308
284
                                     Updater->TII);
309
284
    return PHI->getOperand(0).getReg();
310
284
  }
311
312
  /// AddPHIOperand - Add the specified value as an operand of the PHI for
313
  /// the specified predecessor block.
314
  static void AddPHIOperand(MachineInstr *PHI, unsigned Val,
315
634
                            MachineBasicBlock *Pred) {
316
634
    MachineInstrBuilder(*Pred->getParent(), PHI).addReg(Val).addMBB(Pred);
317
634
  }
318
319
  /// InstrIsPHI - Check if an instruction is a PHI.
320
302
  static MachineInstr *InstrIsPHI(MachineInstr *I) {
321
302
    if (I && I->isPHI())
322
297
      return I;
323
5
    return nullptr;
324
5
  }
325
326
  /// ValueIsPHI - Check if the instruction that defines the specified register
327
  /// is a PHI instruction.
328
302
  static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) {
329
302
    return InstrIsPHI(Updater->MRI->getVRegDef(Val));
330
302
  }
331
332
  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
333
  /// operands, i.e., it was just added.
334
285
  static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) {
335
285
    MachineInstr *PHI = ValueIsPHI(Val, Updater);
336
285
    if (PHI && PHI->getNumOperands() <= 1)
337
284
      return PHI;
338
1
    return nullptr;
339
1
  }
340
341
  /// GetPHIValue - For the specified PHI instruction, return the register
342
  /// that it defines.
343
1
  static unsigned GetPHIValue(MachineInstr *PHI) {
344
1
    return PHI->getOperand(0).getReg();
345
1
  }
346
};
347
348
} // end namespace llvm
349
350
/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
351
/// for the specified BB and if so, return it.  If not, construct SSA form by
352
/// first calculating the required placement of PHIs and then inserting new
353
/// PHIs where needed.
354
1.51k
unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){
355
1.51k
  AvailableValsTy &AvailableVals = getAvailableVals(AV);
356
1.51k
  if (unsigned V = AvailableVals[BB])
357
1.13k
    return V;
358
383
359
383
  SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
360
383
  return Impl.GetValue(BB);
361
383
}