← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/MachineVerifier.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/MachineVerifier.cpp
1
 
//===-- MachineVerifier.cpp - Machine Code Verifier -----------------------===//
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
 
// Pass to verify generated machine code. The following is checked:
11
 
//
12
 
// Operand counts: All explicit operands must be present.
13
 
//
14
 
// Register classes: All physical and virtual register operands must be
15
 
// compatible with the register class required by the instruction descriptor.
16
 
//
17
 
// Register live intervals: Registers must be defined only once, and must be
18
 
// defined before use.
19
 
//
20
 
// The machine code verifier is enabled from LLVMTargetMachine.cpp with the
21
 
// command-line option -verify-machineinstrs, or by defining the environment
22
 
// variable LLVM_VERIFY_MACHINEINSTRS to the name of a file that will receive
23
 
// the verifier errors.
24
 
//===----------------------------------------------------------------------===//
25
 
 
26
 
#include "llvm/Function.h"
27
 
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
28
 
#include "llvm/CodeGen/LiveVariables.h"
29
 
#include "llvm/CodeGen/MachineFunctionPass.h"
30
 
#include "llvm/CodeGen/MachineFrameInfo.h"
31
 
#include "llvm/CodeGen/MachineMemOperand.h"
32
 
#include "llvm/CodeGen/MachineRegisterInfo.h"
33
 
#include "llvm/CodeGen/Passes.h"
34
 
#include "llvm/Target/TargetMachine.h"
35
 
#include "llvm/Target/TargetRegisterInfo.h"
36
 
#include "llvm/Target/TargetInstrInfo.h"
37
 
#include "llvm/ADT/DenseSet.h"
38
 
#include "llvm/ADT/SetOperations.h"
39
 
#include "llvm/ADT/SmallVector.h"
40
 
#include "llvm/Support/Debug.h"
41
 
#include "llvm/Support/ErrorHandling.h"
42
 
#include "llvm/Support/raw_ostream.h"
43
 
using namespace llvm;
44
 
 
45
 
namespace {
46
 
  struct MachineVerifier {
47
 
 
48
 
    MachineVerifier(Pass *pass) :
49
 
      PASS(pass),
50
 
      OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
51
 
      {}
52
 
 
53
 
    bool runOnMachineFunction(MachineFunction &MF);
54
 
 
55
 
    Pass *const PASS;
56
 
    const char *const OutFileName;
57
 
    raw_ostream *OS;
58
 
    const MachineFunction *MF;
59
 
    const TargetMachine *TM;
60
 
    const TargetRegisterInfo *TRI;
61
 
    const MachineRegisterInfo *MRI;
62
 
 
63
 
    unsigned foundErrors;
64
 
 
65
 
    typedef SmallVector<unsigned, 16> RegVector;
66
 
    typedef DenseSet<unsigned> RegSet;
67
 
    typedef DenseMap<unsigned, const MachineInstr*> RegMap;
68
 
 
69
 
    BitVector regsReserved;
70
 
    RegSet regsLive;
71
 
    RegVector regsDefined, regsDead, regsKilled;
72
 
    RegSet regsLiveInButUnused;
73
 
 
74
 
    // Add Reg and any sub-registers to RV
75
 
    void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
76
 
      RV.push_back(Reg);
77
 
      if (TargetRegisterInfo::isPhysicalRegister(Reg))
78
 
        for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
79
 
          RV.push_back(*R);
80
 
    }
81
 
 
82
 
    struct BBInfo {
83
 
      // Is this MBB reachable from the MF entry point?
84
 
      bool reachable;
85
 
 
86
 
      // Vregs that must be live in because they are used without being
87
 
      // defined. Map value is the user.
88
 
      RegMap vregsLiveIn;
89
 
 
90
 
      // Regs killed in MBB. They may be defined again, and will then be in both
91
 
      // regsKilled and regsLiveOut.
92
 
      RegSet regsKilled;
93
 
 
94
 
      // Regs defined in MBB and live out. Note that vregs passing through may
95
 
      // be live out without being mentioned here.
96
 
      RegSet regsLiveOut;
97
 
 
98
 
      // Vregs that pass through MBB untouched. This set is disjoint from
99
 
      // regsKilled and regsLiveOut.
100
 
      RegSet vregsPassed;
101
 
 
102
 
      // Vregs that must pass through MBB because they are needed by a successor
103
 
      // block. This set is disjoint from regsLiveOut.
104
 
      RegSet vregsRequired;
105
 
 
106
 
      BBInfo() : reachable(false) {}
107
 
 
108
 
      // Add register to vregsPassed if it belongs there. Return true if
109
 
      // anything changed.
110
 
      bool addPassed(unsigned Reg) {
111
 
        if (!TargetRegisterInfo::isVirtualRegister(Reg))
112
 
          return false;
113
 
        if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
114
 
          return false;
115
 
        return vregsPassed.insert(Reg).second;
116
 
      }
117
 
 
118
 
      // Same for a full set.
119
 
      bool addPassed(const RegSet &RS) {
120
 
        bool changed = false;
121
 
        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
122
 
          if (addPassed(*I))
123
 
            changed = true;
124
 
        return changed;
125
 
      }
126
 
 
127
 
      // Add register to vregsRequired if it belongs there. Return true if
128
 
      // anything changed.
129
 
      bool addRequired(unsigned Reg) {
130
 
        if (!TargetRegisterInfo::isVirtualRegister(Reg))
131
 
          return false;
132
 
        if (regsLiveOut.count(Reg))
133
 
          return false;
134
 
        return vregsRequired.insert(Reg).second;
135
 
      }
136
 
 
137
 
      // Same for a full set.
138
 
      bool addRequired(const RegSet &RS) {
139
 
        bool changed = false;
140
 
        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
141
 
          if (addRequired(*I))
142
 
            changed = true;
143
 
        return changed;
144
 
      }
145
 
 
146
 
      // Same for a full map.
147
 
      bool addRequired(const RegMap &RM) {
148
 
        bool changed = false;
149
 
        for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
150
 
          if (addRequired(I->first))
151
 
            changed = true;
152
 
        return changed;
153
 
      }
154
 
 
155
 
      // Live-out registers are either in regsLiveOut or vregsPassed.
156
 
      bool isLiveOut(unsigned Reg) const {
157
 
        return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
158
 
      }
159
 
    };
160
 
 
161
 
    // Extra register info per MBB.
162
 
    DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
163
 
 
164
 
    bool isReserved(unsigned Reg) {
165
 
      return Reg < regsReserved.size() && regsReserved.test(Reg);
166
 
    }
167
 
 
168
 
    // Analysis information if available
169
 
    LiveVariables *LiveVars;
170
 
    const LiveIntervals *LiveInts;
171
 
 
172
 
    void visitMachineFunctionBefore();
173
 
    void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
174
 
    void visitMachineInstrBefore(const MachineInstr *MI);
175
 
    void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
176
 
    void visitMachineInstrAfter(const MachineInstr *MI);
177
 
    void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
178
 
    void visitMachineFunctionAfter();
179
 
 
180
 
    void report(const char *msg, const MachineFunction *MF);
181
 
    void report(const char *msg, const MachineBasicBlock *MBB);
182
 
    void report(const char *msg, const MachineInstr *MI);
183
 
    void report(const char *msg, const MachineOperand *MO, unsigned MONum);
184
 
 
185
 
    void markReachable(const MachineBasicBlock *MBB);
186
 
    void calcRegsPassed();
187
 
    void checkPHIOps(const MachineBasicBlock *MBB);
188
 
 
189
 
    void calcRegsRequired();
190
 
    void verifyLiveVariables();
191
 
    void verifyLiveIntervals();
192
 
  };
193
 
 
194
 
  struct MachineVerifierPass : public MachineFunctionPass {
195
 
    static char ID; // Pass ID, replacement for typeid
196
 
 
197
 
    MachineVerifierPass()
198
 
      : MachineFunctionPass(ID) {}
199
 
 
200
 
    void getAnalysisUsage(AnalysisUsage &AU) const {
201
 
      AU.setPreservesAll();
202
 
      MachineFunctionPass::getAnalysisUsage(AU);
203
 
    }
204
 
 
205
 
    bool runOnMachineFunction(MachineFunction &MF) {
206
 
      MF.verify(this);
207
 
      return false;
208
 
    }
209
 
  };
210
 
 
211
 
}
212
 
 
213
 
char MachineVerifierPass::ID = 0;
214
 
INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
215
 
                "Verify generated machine code", false, false);
216
 
 
217
 
FunctionPass *llvm::createMachineVerifierPass() {
218
 
  return new MachineVerifierPass();
219
 
}
220
 
 
221
 
void MachineFunction::verify(Pass *p) const {
222
 
  MachineVerifier(p).runOnMachineFunction(const_cast<MachineFunction&>(*this));
223
 
}
224
 
 
225
 
bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
226
 
  raw_ostream *OutFile = 0;
227
 
  if (OutFileName) {
228
 
    std::string ErrorInfo;
229
 
    OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
230
 
                                 raw_fd_ostream::F_Append);
231
 
    if (!ErrorInfo.empty()) {
232
 
      errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
233
 
      exit(1);
234
 
    }
235
 
 
236
 
    OS = OutFile;
237
 
  } else {
238
 
    OS = &errs();
239
 
  }
240
 
 
241
 
  foundErrors = 0;
242
 
 
243
 
  this->MF = &MF;
244
 
  TM = &MF.getTarget();
245
 
  TRI = TM->getRegisterInfo();
246
 
  MRI = &MF.getRegInfo();
247
 
 
248
 
  LiveVars = NULL;
249
 
  LiveInts = NULL;
250
 
  if (PASS) {
251
 
    LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
252
 
    // We don't want to verify LiveVariables if LiveIntervals is available.
253
 
    if (!LiveInts)
254
 
      LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
255
 
  }
256
 
 
257
 
  visitMachineFunctionBefore();
258
 
  for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
259
 
       MFI!=MFE; ++MFI) {
260
 
    visitMachineBasicBlockBefore(MFI);
261
 
    for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
262
 
           MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
263
 
      visitMachineInstrBefore(MBBI);
264
 
      for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
265
 
        visitMachineOperand(&MBBI->getOperand(I), I);
266
 
      visitMachineInstrAfter(MBBI);
267
 
    }
268
 
    visitMachineBasicBlockAfter(MFI);
269
 
  }
270
 
  visitMachineFunctionAfter();
271
 
 
272
 
  if (OutFile)
273
 
    delete OutFile;
274
 
  else if (foundErrors)
275
 
    report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
276
 
 
277
 
  // Clean up.
278
 
  regsLive.clear();
279
 
  regsDefined.clear();
280
 
  regsDead.clear();
281
 
  regsKilled.clear();
282
 
  regsLiveInButUnused.clear();
283
 
  MBBInfoMap.clear();
284
 
 
285
 
  return false;                 // no changes
286
 
}
287
 
 
288
 
void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
289
 
  assert(MF);
290
 
  *OS << '\n';
291
 
  if (!foundErrors++)
292
 
    MF->print(*OS);
293
 
  *OS << "*** Bad machine code: " << msg << " ***\n"
294
 
      << "- function:    " << MF->getFunction()->getNameStr() << "\n";
295
 
}
296
 
 
297
 
void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
298
 
  assert(MBB);
299
 
  report(msg, MBB->getParent());
300
 
  *OS << "- basic block: " << MBB->getName()
301
 
      << " " << (void*)MBB
302
 
      << " (BB#" << MBB->getNumber() << ")\n";
303
 
}
304
 
 
305
 
void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
306
 
  assert(MI);
307
 
  report(msg, MI->getParent());
308
 
  *OS << "- instruction: ";
309
 
  MI->print(*OS, TM);
310
 
}
311
 
 
312
 
void MachineVerifier::report(const char *msg,
313
 
                             const MachineOperand *MO, unsigned MONum) {
314
 
  assert(MO);
315
 
  report(msg, MO->getParent());
316
 
  *OS << "- operand " << MONum << ":   ";
317
 
  MO->print(*OS, TM);
318
 
  *OS << "\n";
319
 
}
320
 
 
321
 
void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
322
 
  BBInfo &MInfo = MBBInfoMap[MBB];
323
 
  if (!MInfo.reachable) {
324
 
    MInfo.reachable = true;
325
 
    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
326
 
           SuE = MBB->succ_end(); SuI != SuE; ++SuI)
327
 
      markReachable(*SuI);
328
 
  }
329
 
}
330
 
 
331
 
void MachineVerifier::visitMachineFunctionBefore() {
332
 
  regsReserved = TRI->getReservedRegs(*MF);
333
 
 
334
 
  // A sub-register of a reserved register is also reserved
335
 
  for (int Reg = regsReserved.find_first(); Reg>=0;
336
 
       Reg = regsReserved.find_next(Reg)) {
337
 
    for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
338
 
      // FIXME: This should probably be:
339
 
      // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
340
 
      regsReserved.set(*Sub);
341
 
    }
342
 
  }
343
 
  markReachable(&MF->front());
344
 
}
345
 
 
346
 
// Does iterator point to a and b as the first two elements?
347
 
static bool matchPair(MachineBasicBlock::const_succ_iterator i,
348
 
                      const MachineBasicBlock *a, const MachineBasicBlock *b) {
349
 
  if (*i == a)
350
 
    return *++i == b;
351
 
  if (*i == b)
352
 
    return *++i == a;
353
 
  return false;
354
 
}
355
 
 
356
 
void
357
 
MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
358
 
  const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
359
 
 
360
 
  // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
361
 
  MachineBasicBlock *TBB = 0, *FBB = 0;
362
 
  SmallVector<MachineOperand, 4> Cond;
363
 
  if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
364
 
                          TBB, FBB, Cond)) {
365
 
    // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
366
 
    // check whether its answers match up with reality.
367
 
    if (!TBB && !FBB) {
368
 
      // Block falls through to its successor.
369
 
      MachineFunction::const_iterator MBBI = MBB;
370
 
      ++MBBI;
371
 
      if (MBBI == MF->end()) {
372
 
        // It's possible that the block legitimately ends with a noreturn
373
 
        // call or an unreachable, in which case it won't actually fall
374
 
        // out the bottom of the function.
375
 
      } else if (MBB->succ_empty()) {
376
 
        // It's possible that the block legitimately ends with a noreturn
377
 
        // call or an unreachable, in which case it won't actuall fall
378
 
        // out of the block.
379
 
      } else if (MBB->succ_size() != 1) {
380
 
        report("MBB exits via unconditional fall-through but doesn't have "
381
 
               "exactly one CFG successor!", MBB);
382
 
      } else if (MBB->succ_begin()[0] != MBBI) {
383
 
        report("MBB exits via unconditional fall-through but its successor "
384
 
               "differs from its CFG successor!", MBB);
385
 
      }
386
 
      if (!MBB->empty() && MBB->back().getDesc().isBarrier() &&
387
 
          !TII->isPredicated(&MBB->back())) {
388
 
        report("MBB exits via unconditional fall-through but ends with a "
389
 
               "barrier instruction!", MBB);
390
 
      }
391
 
      if (!Cond.empty()) {
392
 
        report("MBB exits via unconditional fall-through but has a condition!",
393
 
               MBB);
394
 
      }
395
 
    } else if (TBB && !FBB && Cond.empty()) {
396
 
      // Block unconditionally branches somewhere.
397
 
      if (MBB->succ_size() != 1) {
398
 
        report("MBB exits via unconditional branch but doesn't have "
399
 
               "exactly one CFG successor!", MBB);
400
 
      } else if (MBB->succ_begin()[0] != TBB) {
401
 
        report("MBB exits via unconditional branch but the CFG "
402
 
               "successor doesn't match the actual successor!", MBB);
403
 
      }
404
 
      if (MBB->empty()) {
405
 
        report("MBB exits via unconditional branch but doesn't contain "
406
 
               "any instructions!", MBB);
407
 
      } else if (!MBB->back().getDesc().isBarrier()) {
408
 
        report("MBB exits via unconditional branch but doesn't end with a "
409
 
               "barrier instruction!", MBB);
410
 
      } else if (!MBB->back().getDesc().isTerminator()) {
411
 
        report("MBB exits via unconditional branch but the branch isn't a "
412
 
               "terminator instruction!", MBB);
413
 
      }
414
 
    } else if (TBB && !FBB && !Cond.empty()) {
415
 
      // Block conditionally branches somewhere, otherwise falls through.
416
 
      MachineFunction::const_iterator MBBI = MBB;
417
 
      ++MBBI;
418
 
      if (MBBI == MF->end()) {
419
 
        report("MBB conditionally falls through out of function!", MBB);
420
 
      } if (MBB->succ_size() != 2) {
421
 
        report("MBB exits via conditional branch/fall-through but doesn't have "
422
 
               "exactly two CFG successors!", MBB);
423
 
      } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
424
 
        report("MBB exits via conditional branch/fall-through but the CFG "
425
 
               "successors don't match the actual successors!", MBB);
426
 
      }
427
 
      if (MBB->empty()) {
428
 
        report("MBB exits via conditional branch/fall-through but doesn't "
429
 
               "contain any instructions!", MBB);
430
 
      } else if (MBB->back().getDesc().isBarrier()) {
431
 
        report("MBB exits via conditional branch/fall-through but ends with a "
432
 
               "barrier instruction!", MBB);
433
 
      } else if (!MBB->back().getDesc().isTerminator()) {
434
 
        report("MBB exits via conditional branch/fall-through but the branch "
435
 
               "isn't a terminator instruction!", MBB);
436
 
      }
437
 
    } else if (TBB && FBB) {
438
 
      // Block conditionally branches somewhere, otherwise branches
439
 
      // somewhere else.
440
 
      if (MBB->succ_size() != 2) {
441
 
        report("MBB exits via conditional branch/branch but doesn't have "
442
 
               "exactly two CFG successors!", MBB);
443
 
      } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
444
 
        report("MBB exits via conditional branch/branch but the CFG "
445
 
               "successors don't match the actual successors!", MBB);
446
 
      }
447
 
      if (MBB->empty()) {
448
 
        report("MBB exits via conditional branch/branch but doesn't "
449
 
               "contain any instructions!", MBB);
450
 
      } else if (!MBB->back().getDesc().isBarrier()) {
451
 
        report("MBB exits via conditional branch/branch but doesn't end with a "
452
 
               "barrier instruction!", MBB);
453
 
      } else if (!MBB->back().getDesc().isTerminator()) {
454
 
        report("MBB exits via conditional branch/branch but the branch "
455
 
               "isn't a terminator instruction!", MBB);
456
 
      }
457
 
      if (Cond.empty()) {
458
 
        report("MBB exits via conditinal branch/branch but there's no "
459
 
               "condition!", MBB);
460
 
      }
461
 
    } else {
462
 
      report("AnalyzeBranch returned invalid data!", MBB);
463
 
    }
464
 
  }
465
 
 
466
 
  regsLive.clear();
467
 
  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
468
 
         E = MBB->livein_end(); I != E; ++I) {
469
 
    if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
470
 
      report("MBB live-in list contains non-physical register", MBB);
471
 
      continue;
472
 
    }
473
 
    regsLive.insert(*I);
474
 
    for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
475
 
      regsLive.insert(*R);
476
 
  }
477
 
  regsLiveInButUnused = regsLive;
478
 
 
479
 
  const MachineFrameInfo *MFI = MF->getFrameInfo();
480
 
  assert(MFI && "Function has no frame info");
481
 
  BitVector PR = MFI->getPristineRegs(MBB);
482
 
  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
483
 
    regsLive.insert(I);
484
 
    for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
485
 
      regsLive.insert(*R);
486
 
  }
487
 
 
488
 
  regsKilled.clear();
489
 
  regsDefined.clear();
490
 
}
491
 
 
492
 
void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
493
 
  const TargetInstrDesc &TI = MI->getDesc();
494
 
  if (MI->getNumOperands() < TI.getNumOperands()) {
495
 
    report("Too few operands", MI);
496
 
    *OS << TI.getNumOperands() << " operands expected, but "
497
 
        << MI->getNumExplicitOperands() << " given.\n";
498
 
  }
499
 
 
500
 
  // Check the MachineMemOperands for basic consistency.
501
 
  for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
502
 
       E = MI->memoperands_end(); I != E; ++I) {
503
 
    if ((*I)->isLoad() && !TI.mayLoad())
504
 
      report("Missing mayLoad flag", MI);
505
 
    if ((*I)->isStore() && !TI.mayStore())
506
 
      report("Missing mayStore flag", MI);
507
 
  }
508
 
 
509
 
  // Debug values must not have a slot index.
510
 
  // Other instructions must have one.
511
 
  if (LiveInts) {
512
 
    bool mapped = !LiveInts->isNotInMIMap(MI);
513
 
    if (MI->isDebugValue()) {
514
 
      if (mapped)
515
 
        report("Debug instruction has a slot index", MI);
516
 
    } else {
517
 
      if (!mapped)
518
 
        report("Missing slot index", MI);
519
 
    }
520
 
  }
521
 
 
522
 
}
523
 
 
524
 
void
525
 
MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
526
 
  const MachineInstr *MI = MO->getParent();
527
 
  const TargetInstrDesc &TI = MI->getDesc();
528
 
 
529
 
  // The first TI.NumDefs operands must be explicit register defines
530
 
  if (MONum < TI.getNumDefs()) {
531
 
    if (!MO->isReg())
532
 
      report("Explicit definition must be a register", MO, MONum);
533
 
    else if (!MO->isDef())
534
 
      report("Explicit definition marked as use", MO, MONum);
535
 
    else if (MO->isImplicit())
536
 
      report("Explicit definition marked as implicit", MO, MONum);
537
 
  } else if (MONum < TI.getNumOperands()) {
538
 
    if (MO->isReg()) {
539
 
      if (MO->isDef())
540
 
        report("Explicit operand marked as def", MO, MONum);
541
 
      if (MO->isImplicit())
542
 
        report("Explicit operand marked as implicit", MO, MONum);
543
 
    }
544
 
  } else {
545
 
    // ARM adds %reg0 operands to indicate predicates. We'll allow that.
546
 
    if (MO->isReg() && !MO->isImplicit() && !TI.isVariadic() && MO->getReg())
547
 
      report("Extra explicit operand on non-variadic instruction", MO, MONum);
548
 
  }
549
 
 
550
 
  switch (MO->getType()) {
551
 
  case MachineOperand::MO_Register: {
552
 
    const unsigned Reg = MO->getReg();
553
 
    if (!Reg)
554
 
      return;
555
 
 
556
 
    // Check Live Variables.
557
 
    if (MO->isUndef()) {
558
 
      // An <undef> doesn't refer to any register, so just skip it.
559
 
    } else if (MO->isUse()) {
560
 
      regsLiveInButUnused.erase(Reg);
561
 
 
562
 
      bool isKill = false;
563
 
      unsigned defIdx;
564
 
      if (MI->isRegTiedToDefOperand(MONum, &defIdx)) {
565
 
        // A two-addr use counts as a kill if use and def are the same.
566
 
        unsigned DefReg = MI->getOperand(defIdx).getReg();
567
 
        if (Reg == DefReg) {
568
 
          isKill = true;
569
 
          // ANd in that case an explicit kill flag is not allowed.
570
 
          if (MO->isKill())
571
 
            report("Illegal kill flag on two-address instruction operand",
572
 
                   MO, MONum);
573
 
        } else if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
574
 
          report("Two-address instruction operands must be identical",
575
 
                 MO, MONum);
576
 
        }
577
 
      } else
578
 
        isKill = MO->isKill();
579
 
 
580
 
      if (isKill)
581
 
        addRegWithSubRegs(regsKilled, Reg);
582
 
 
583
 
      // Check that LiveVars knows this kill.
584
 
      if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
585
 
          MO->isKill()) {
586
 
        LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
587
 
        if (std::find(VI.Kills.begin(),
588
 
                      VI.Kills.end(), MI) == VI.Kills.end())
589
 
          report("Kill missing from LiveVariables", MO, MONum);
590
 
      }
591
 
 
592
 
      // Check LiveInts liveness and kill.
593
 
      if (LiveInts && !LiveInts->isNotInMIMap(MI)) {
594
 
        SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getUseIndex();
595
 
        if (LiveInts->hasInterval(Reg)) {
596
 
          const LiveInterval &LI = LiveInts->getInterval(Reg);
597
 
          if (!LI.liveAt(UseIdx)) {
598
 
            report("No live range at use", MO, MONum);
599
 
            *OS << UseIdx << " is not live in " << LI << '\n';
600
 
          }
601
 
          // TODO: Verify isKill == LI.killedAt.
602
 
        } else if (TargetRegisterInfo::isVirtualRegister(Reg)) {
603
 
          report("Virtual register has no Live interval", MO, MONum);
604
 
        }
605
 
      }
606
 
 
607
 
      // Use of a dead register.
608
 
      if (!regsLive.count(Reg)) {
609
 
        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
610
 
          // Reserved registers may be used even when 'dead'.
611
 
          if (!isReserved(Reg))
612
 
            report("Using an undefined physical register", MO, MONum);
613
 
        } else {
614
 
          BBInfo &MInfo = MBBInfoMap[MI->getParent()];
615
 
          // We don't know which virtual registers are live in, so only complain
616
 
          // if vreg was killed in this MBB. Otherwise keep track of vregs that
617
 
          // must be live in. PHI instructions are handled separately.
618
 
          if (MInfo.regsKilled.count(Reg))
619
 
            report("Using a killed virtual register", MO, MONum);
620
 
          else if (!MI->isPHI())
621
 
            MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
622
 
        }
623
 
      }
624
 
    } else {
625
 
      assert(MO->isDef());
626
 
      // Register defined.
627
 
      // TODO: verify that earlyclobber ops are not used.
628
 
      if (MO->isDead())
629
 
        addRegWithSubRegs(regsDead, Reg);
630
 
      else
631
 
        addRegWithSubRegs(regsDefined, Reg);
632
 
 
633
 
      // Check LiveInts for a live range, but only for virtual registers.
634
 
      if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
635
 
          !LiveInts->isNotInMIMap(MI)) {
636
 
        SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getDefIndex();
637
 
        if (LiveInts->hasInterval(Reg)) {
638
 
          const LiveInterval &LI = LiveInts->getInterval(Reg);
639
 
          if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) {
640
 
            assert(LR->valno && "NULL valno is not allowed");
641
 
            if (LR->valno->def != DefIdx) {
642
 
              report("Inconsistent valno->def", MO, MONum);
643
 
              *OS << "Valno " << LR->valno->id << " is not defined at "
644
 
                  << DefIdx << " in " << LI << '\n';
645
 
            }
646
 
          } else {
647
 
            report("No live range at def", MO, MONum);
648
 
            *OS << DefIdx << " is not live in " << LI << '\n';
649
 
          }
650
 
        } else {
651
 
          report("Virtual register has no Live interval", MO, MONum);
652
 
        }
653
 
      }
654
 
    }
655
 
 
656
 
    // Check register classes.
657
 
    if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
658
 
      const TargetOperandInfo &TOI = TI.OpInfo[MONum];
659
 
      unsigned SubIdx = MO->getSubReg();
660
 
 
661
 
      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
662
 
        unsigned sr = Reg;
663
 
        if (SubIdx) {
664
 
          unsigned s = TRI->getSubReg(Reg, SubIdx);
665
 
          if (!s) {
666
 
            report("Invalid subregister index for physical register",
667
 
                   MO, MONum);
668
 
            return;
669
 
          }
670
 
          sr = s;
671
 
        }
672
 
        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
673
 
          if (!DRC->contains(sr)) {
674
 
            report("Illegal physical register for instruction", MO, MONum);
675
 
            *OS << TRI->getName(sr) << " is not a "
676
 
                << DRC->getName() << " register.\n";
677
 
          }
678
 
        }
679
 
      } else {
680
 
        // Virtual register.
681
 
        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
682
 
        if (SubIdx) {
683
 
          const TargetRegisterClass *SRC = RC->getSubRegisterRegClass(SubIdx);
684
 
          if (!SRC) {
685
 
            report("Invalid subregister index for virtual register", MO, MONum);
686
 
            *OS << "Register class " << RC->getName()
687
 
                << " does not support subreg index " << SubIdx << "\n";
688
 
            return;
689
 
          }
690
 
          RC = SRC;
691
 
        }
692
 
        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
693
 
          if (RC != DRC && !RC->hasSuperClass(DRC)) {
694
 
            report("Illegal virtual register for instruction", MO, MONum);
695
 
            *OS << "Expected a " << DRC->getName() << " register, but got a "
696
 
                << RC->getName() << " register\n";
697
 
          }
698
 
        }
699
 
      }
700
 
    }
701
 
    break;
702
 
  }
703
 
 
704
 
  case MachineOperand::MO_MachineBasicBlock:
705
 
    if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
706
 
      report("PHI operand is not in the CFG", MO, MONum);
707
 
    break;
708
 
 
709
 
  default:
710
 
    break;
711
 
  }
712
 
}
713
 
 
714
 
void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
715
 
  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
716
 
  set_union(MInfo.regsKilled, regsKilled);
717
 
  set_subtract(regsLive, regsKilled); regsKilled.clear();
718
 
  set_subtract(regsLive, regsDead);   regsDead.clear();
719
 
  set_union(regsLive, regsDefined);   regsDefined.clear();
720
 
}
721
 
 
722
 
void
723
 
MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
724
 
  MBBInfoMap[MBB].regsLiveOut = regsLive;
725
 
  regsLive.clear();
726
 
}
727
 
 
728
 
// Calculate the largest possible vregsPassed sets. These are the registers that
729
 
// can pass through an MBB live, but may not be live every time. It is assumed
730
 
// that all vregsPassed sets are empty before the call.
731
 
void MachineVerifier::calcRegsPassed() {
732
 
  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
733
 
  // have any vregsPassed.
734
 
  DenseSet<const MachineBasicBlock*> todo;
735
 
  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
736
 
       MFI != MFE; ++MFI) {
737
 
    const MachineBasicBlock &MBB(*MFI);
738
 
    BBInfo &MInfo = MBBInfoMap[&MBB];
739
 
    if (!MInfo.reachable)
740
 
      continue;
741
 
    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
742
 
           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
743
 
      BBInfo &SInfo = MBBInfoMap[*SuI];
744
 
      if (SInfo.addPassed(MInfo.regsLiveOut))
745
 
        todo.insert(*SuI);
746
 
    }
747
 
  }
748
 
 
749
 
  // Iteratively push vregsPassed to successors. This will converge to the same
750
 
  // final state regardless of DenseSet iteration order.
751
 
  while (!todo.empty()) {
752
 
    const MachineBasicBlock *MBB = *todo.begin();
753
 
    todo.erase(MBB);
754
 
    BBInfo &MInfo = MBBInfoMap[MBB];
755
 
    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
756
 
           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
757
 
      if (*SuI == MBB)
758
 
        continue;
759
 
      BBInfo &SInfo = MBBInfoMap[*SuI];
760
 
      if (SInfo.addPassed(MInfo.vregsPassed))
761
 
        todo.insert(*SuI);
762
 
    }
763
 
  }
764
 
}
765
 
 
766
 
// Calculate the set of virtual registers that must be passed through each basic
767
 
// block in order to satisfy the requirements of successor blocks. This is very
768
 
// similar to calcRegsPassed, only backwards.
769
 
void MachineVerifier::calcRegsRequired() {
770
 
  // First push live-in regs to predecessors' vregsRequired.
771
 
  DenseSet<const MachineBasicBlock*> todo;
772
 
  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
773
 
       MFI != MFE; ++MFI) {
774
 
    const MachineBasicBlock &MBB(*MFI);
775
 
    BBInfo &MInfo = MBBInfoMap[&MBB];
776
 
    for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
777
 
           PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
778
 
      BBInfo &PInfo = MBBInfoMap[*PrI];
779
 
      if (PInfo.addRequired(MInfo.vregsLiveIn))
780
 
        todo.insert(*PrI);
781
 
    }
782
 
  }
783
 
 
784
 
  // Iteratively push vregsRequired to predecessors. This will converge to the
785
 
  // same final state regardless of DenseSet iteration order.
786
 
  while (!todo.empty()) {
787
 
    const MachineBasicBlock *MBB = *todo.begin();
788
 
    todo.erase(MBB);
789
 
    BBInfo &MInfo = MBBInfoMap[MBB];
790
 
    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
791
 
           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
792
 
      if (*PrI == MBB)
793
 
        continue;
794
 
      BBInfo &SInfo = MBBInfoMap[*PrI];
795
 
      if (SInfo.addRequired(MInfo.vregsRequired))
796
 
        todo.insert(*PrI);
797
 
    }
798
 
  }
799
 
}
800
 
 
801
 
// Check PHI instructions at the beginning of MBB. It is assumed that
802
 
// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
803
 
void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
804
 
  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
805
 
       BBI != BBE && BBI->isPHI(); ++BBI) {
806
 
    DenseSet<const MachineBasicBlock*> seen;
807
 
 
808
 
    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
809
 
      unsigned Reg = BBI->getOperand(i).getReg();
810
 
      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
811
 
      if (!Pre->isSuccessor(MBB))
812
 
        continue;
813
 
      seen.insert(Pre);
814
 
      BBInfo &PrInfo = MBBInfoMap[Pre];
815
 
      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
816
 
        report("PHI operand is not live-out from predecessor",
817
 
               &BBI->getOperand(i), i);
818
 
    }
819
 
 
820
 
    // Did we see all predecessors?
821
 
    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
822
 
           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
823
 
      if (!seen.count(*PrI)) {
824
 
        report("Missing PHI operand", BBI);
825
 
        *OS << "BB#" << (*PrI)->getNumber()
826
 
            << " is a predecessor according to the CFG.\n";
827
 
      }
828
 
    }
829
 
  }
830
 
}
831
 
 
832
 
void MachineVerifier::visitMachineFunctionAfter() {
833
 
  calcRegsPassed();
834
 
 
835
 
  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
836
 
       MFI != MFE; ++MFI) {
837
 
    BBInfo &MInfo = MBBInfoMap[MFI];
838
 
 
839
 
    // Skip unreachable MBBs.
840
 
    if (!MInfo.reachable)
841
 
      continue;
842
 
 
843
 
    checkPHIOps(MFI);
844
 
  }
845
 
 
846
 
  // Now check liveness info if available
847
 
  if (LiveVars || LiveInts)
848
 
    calcRegsRequired();
849
 
  if (LiveVars)
850
 
    verifyLiveVariables();
851
 
  if (LiveInts)
852
 
    verifyLiveIntervals();
853
 
}
854
 
 
855
 
void MachineVerifier::verifyLiveVariables() {
856
 
  assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
857
 
  for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister,
858
 
         RegE = MRI->getLastVirtReg()-1; Reg != RegE; ++Reg) {
859
 
    LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
860
 
    for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
861
 
         MFI != MFE; ++MFI) {
862
 
      BBInfo &MInfo = MBBInfoMap[MFI];
863
 
 
864
 
      // Our vregsRequired should be identical to LiveVariables' AliveBlocks
865
 
      if (MInfo.vregsRequired.count(Reg)) {
866
 
        if (!VI.AliveBlocks.test(MFI->getNumber())) {
867
 
          report("LiveVariables: Block missing from AliveBlocks", MFI);
868
 
          *OS << "Virtual register %reg" << Reg
869
 
              << " must be live through the block.\n";
870
 
        }
871
 
      } else {
872
 
        if (VI.AliveBlocks.test(MFI->getNumber())) {
873
 
          report("LiveVariables: Block should not be in AliveBlocks", MFI);
874
 
          *OS << "Virtual register %reg" << Reg
875
 
              << " is not needed live through the block.\n";
876
 
        }
877
 
      }
878
 
    }
879
 
  }
880
 
}
881
 
 
882
 
void MachineVerifier::verifyLiveIntervals() {
883
 
  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
884
 
  for (LiveIntervals::const_iterator LVI = LiveInts->begin(),
885
 
       LVE = LiveInts->end(); LVI != LVE; ++LVI) {
886
 
    const LiveInterval &LI = *LVI->second;
887
 
    assert(LVI->first == LI.reg && "Invalid reg to interval mapping");
888
 
 
889
 
    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
890
 
         I!=E; ++I) {
891
 
      VNInfo *VNI = *I;
892
 
      const LiveRange *DefLR = LI.getLiveRangeContaining(VNI->def);
893
 
 
894
 
      if (!DefLR) {
895
 
        if (!VNI->isUnused()) {
896
 
          report("Valno not live at def and not marked unused", MF);
897
 
          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
898
 
        }
899
 
        continue;
900
 
      }
901
 
 
902
 
      if (VNI->isUnused())
903
 
        continue;
904
 
 
905
 
      if (DefLR->valno != VNI) {
906
 
        report("Live range at def has different valno", MF);
907
 
        DefLR->print(*OS);
908
 
        *OS << " should use valno #" << VNI->id << " in " << LI << '\n';
909
 
      }
910
 
 
911
 
    }
912
 
 
913
 
    for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
914
 
      const LiveRange &LR = *I;
915
 
      assert(LR.valno && "Live range has no valno");
916
 
 
917
 
      if (LR.valno->id >= LI.getNumValNums() ||
918
 
          LR.valno != LI.getValNumInfo(LR.valno->id)) {
919
 
        report("Foreign valno in live range", MF);
920
 
        LR.print(*OS);
921
 
        *OS << " has a valno not in " << LI << '\n';
922
 
      }
923
 
 
924
 
      if (LR.valno->isUnused()) {
925
 
        report("Live range valno is marked unused", MF);
926
 
        LR.print(*OS);
927
 
        *OS << " in " << LI << '\n';
928
 
      }
929
 
 
930
 
    }
931
 
  }
932
 
}
933