MachineVerifier.cpp revision 4314268128be6d54c9a7f0709680e5a5b40f3ab3 
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/LiveStackAnalysis.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineFrameInfo.h"
32#include "llvm/CodeGen/MachineMemOperand.h"
33#include "llvm/CodeGen/MachineRegisterInfo.h"
34#include "llvm/CodeGen/Passes.h"
35#include "llvm/Target/TargetMachine.h"
36#include "llvm/Target/TargetRegisterInfo.h"
37#include "llvm/Target/TargetInstrInfo.h"
38#include "llvm/ADT/DenseSet.h"
39#include "llvm/ADT/SetOperations.h"
40#include "llvm/ADT/SmallVector.h"
41#include "llvm/Support/Debug.h"
42#include "llvm/Support/ErrorHandling.h"
43#include "llvm/Support/raw_ostream.h"
44using namespace llvm;
45
46namespace {
47  struct MachineVerifier {
48
49    MachineVerifier(Pass *pass, const char *b) :
50      PASS(pass),
51      Banner(b),
52      OutFileName(getenv("LLVM_VERIFY_MACHINEINSTRS"))
53      {}
54
55    bool runOnMachineFunction(MachineFunction &MF);
56
57    Pass *const PASS;
58    const char *Banner;
59    const char *const OutFileName;
60    raw_ostream *OS;
61    const MachineFunction *MF;
62    const TargetMachine *TM;
63    const TargetRegisterInfo *TRI;
64    const MachineRegisterInfo *MRI;
65
66    unsigned foundErrors;
67
68    typedef SmallVector<unsigned, 16> RegVector;
69    typedef DenseSet<unsigned> RegSet;
70    typedef DenseMap<unsigned, const MachineInstr*> RegMap;
71
72    BitVector regsReserved;
73    RegSet regsLive;
74    RegVector regsDefined, regsDead, regsKilled;
75    RegSet regsLiveInButUnused;
76
77    // Add Reg and any sub-registers to RV
78    void addRegWithSubRegs(RegVector &RV, unsigned Reg) {
79      RV.push_back(Reg);
80      if (TargetRegisterInfo::isPhysicalRegister(Reg))
81        for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
82          RV.push_back(*R);
83    }
84
85    struct BBInfo {
86      // Is this MBB reachable from the MF entry point?
87      bool reachable;
88
89      // Vregs that must be live in because they are used without being
90      // defined. Map value is the user.
91      RegMap vregsLiveIn;
92
93      // Regs killed in MBB. They may be defined again, and will then be in both
94      // regsKilled and regsLiveOut.
95      RegSet regsKilled;
96
97      // Regs defined in MBB and live out. Note that vregs passing through may
98      // be live out without being mentioned here.
99      RegSet regsLiveOut;
100
101      // Vregs that pass through MBB untouched. This set is disjoint from
102      // regsKilled and regsLiveOut.
103      RegSet vregsPassed;
104
105      // Vregs that must pass through MBB because they are needed by a successor
106      // block. This set is disjoint from regsLiveOut.
107      RegSet vregsRequired;
108
109      BBInfo() : reachable(false) {}
110
111      // Add register to vregsPassed if it belongs there. Return true if
112      // anything changed.
113      bool addPassed(unsigned Reg) {
114        if (!TargetRegisterInfo::isVirtualRegister(Reg))
115          return false;
116        if (regsKilled.count(Reg) || regsLiveOut.count(Reg))
117          return false;
118        return vregsPassed.insert(Reg).second;
119      }
120
121      // Same for a full set.
122      bool addPassed(const RegSet &RS) {
123        bool changed = false;
124        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
125          if (addPassed(*I))
126            changed = true;
127        return changed;
128      }
129
130      // Add register to vregsRequired if it belongs there. Return true if
131      // anything changed.
132      bool addRequired(unsigned Reg) {
133        if (!TargetRegisterInfo::isVirtualRegister(Reg))
134          return false;
135        if (regsLiveOut.count(Reg))
136          return false;
137        return vregsRequired.insert(Reg).second;
138      }
139
140      // Same for a full set.
141      bool addRequired(const RegSet &RS) {
142        bool changed = false;
143        for (RegSet::const_iterator I = RS.begin(), E = RS.end(); I != E; ++I)
144          if (addRequired(*I))
145            changed = true;
146        return changed;
147      }
148
149      // Same for a full map.
150      bool addRequired(const RegMap &RM) {
151        bool changed = false;
152        for (RegMap::const_iterator I = RM.begin(), E = RM.end(); I != E; ++I)
153          if (addRequired(I->first))
154            changed = true;
155        return changed;
156      }
157
158      // Live-out registers are either in regsLiveOut or vregsPassed.
159      bool isLiveOut(unsigned Reg) const {
160        return regsLiveOut.count(Reg) || vregsPassed.count(Reg);
161      }
162    };
163
164    // Extra register info per MBB.
165    DenseMap<const MachineBasicBlock*, BBInfo> MBBInfoMap;
166
167    bool isReserved(unsigned Reg) {
168      return Reg < regsReserved.size() && regsReserved.test(Reg);
169    }
170
171    // Analysis information if available
172    LiveVariables *LiveVars;
173    LiveIntervals *LiveInts;
174    LiveStacks *LiveStks;
175    SlotIndexes *Indexes;
176
177    void visitMachineFunctionBefore();
178    void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
179    void visitMachineInstrBefore(const MachineInstr *MI);
180    void visitMachineOperand(const MachineOperand *MO, unsigned MONum);
181    void visitMachineInstrAfter(const MachineInstr *MI);
182    void visitMachineBasicBlockAfter(const MachineBasicBlock *MBB);
183    void visitMachineFunctionAfter();
184
185    void report(const char *msg, const MachineFunction *MF);
186    void report(const char *msg, const MachineBasicBlock *MBB);
187    void report(const char *msg, const MachineInstr *MI);
188    void report(const char *msg, const MachineOperand *MO, unsigned MONum);
189
190    void markReachable(const MachineBasicBlock *MBB);
191    void calcRegsPassed();
192    void checkPHIOps(const MachineBasicBlock *MBB);
193
194    void calcRegsRequired();
195    void verifyLiveVariables();
196    void verifyLiveIntervals();
197  };
198
199  struct MachineVerifierPass : public MachineFunctionPass {
200    static char ID; // Pass ID, replacement for typeid
201    const char *const Banner;
202
203    MachineVerifierPass(const char *b = 0)
204      : MachineFunctionPass(ID), Banner(b) {
205        initializeMachineVerifierPassPass(*PassRegistry::getPassRegistry());
206      }
207
208    void getAnalysisUsage(AnalysisUsage &AU) const {
209      AU.setPreservesAll();
210      MachineFunctionPass::getAnalysisUsage(AU);
211    }
212
213    bool runOnMachineFunction(MachineFunction &MF) {
214      MF.verify(this, Banner);
215      return false;
216    }
217  };
218
219}
220
221char MachineVerifierPass::ID = 0;
222INITIALIZE_PASS(MachineVerifierPass, "machineverifier",
223                "Verify generated machine code", false, false)
224
225FunctionPass *llvm::createMachineVerifierPass(const char *Banner) {
226  return new MachineVerifierPass(Banner);
227}
228
229void MachineFunction::verify(Pass *p, const char *Banner) const {
230  MachineVerifier(p, Banner)
231    .runOnMachineFunction(const_cast<MachineFunction&>(*this));
232}
233
234bool MachineVerifier::runOnMachineFunction(MachineFunction &MF) {
235  raw_ostream *OutFile = 0;
236  if (OutFileName) {
237    std::string ErrorInfo;
238    OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
239                                 raw_fd_ostream::F_Append);
240    if (!ErrorInfo.empty()) {
241      errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
242      exit(1);
243    }
244
245    OS = OutFile;
246  } else {
247    OS = &errs();
248  }
249
250  foundErrors = 0;
251
252  this->MF = &MF;
253  TM = &MF.getTarget();
254  TRI = TM->getRegisterInfo();
255  MRI = &MF.getRegInfo();
256
257  LiveVars = NULL;
258  LiveInts = NULL;
259  LiveStks = NULL;
260  Indexes = NULL;
261  if (PASS) {
262    LiveInts = PASS->getAnalysisIfAvailable<LiveIntervals>();
263    // We don't want to verify LiveVariables if LiveIntervals is available.
264    if (!LiveInts)
265      LiveVars = PASS->getAnalysisIfAvailable<LiveVariables>();
266    LiveStks = PASS->getAnalysisIfAvailable<LiveStacks>();
267    Indexes = PASS->getAnalysisIfAvailable<SlotIndexes>();
268  }
269
270  visitMachineFunctionBefore();
271  for (MachineFunction::const_iterator MFI = MF.begin(), MFE = MF.end();
272       MFI!=MFE; ++MFI) {
273    visitMachineBasicBlockBefore(MFI);
274    for (MachineBasicBlock::const_iterator MBBI = MFI->begin(),
275           MBBE = MFI->end(); MBBI != MBBE; ++MBBI) {
276      visitMachineInstrBefore(MBBI);
277      for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
278        visitMachineOperand(&MBBI->getOperand(I), I);
279      visitMachineInstrAfter(MBBI);
280    }
281    visitMachineBasicBlockAfter(MFI);
282  }
283  visitMachineFunctionAfter();
284
285  if (OutFile)
286    delete OutFile;
287  else if (foundErrors)
288    report_fatal_error("Found "+Twine(foundErrors)+" machine code errors.");
289
290  // Clean up.
291  regsLive.clear();
292  regsDefined.clear();
293  regsDead.clear();
294  regsKilled.clear();
295  regsLiveInButUnused.clear();
296  MBBInfoMap.clear();
297
298  return false;                 // no changes
299}
300
301void MachineVerifier::report(const char *msg, const MachineFunction *MF) {
302  assert(MF);
303  *OS << '\n';
304  if (!foundErrors++) {
305    if (Banner)
306      *OS << "# " << Banner << '\n';
307    MF->print(*OS, Indexes);
308  }
309  *OS << "*** Bad machine code: " << msg << " ***\n"
310      << "- function:    " << MF->getFunction()->getNameStr() << "\n";
311}
312
313void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
314  assert(MBB);
315  report(msg, MBB->getParent());
316  *OS << "- basic block: " << MBB->getName()
317      << " " << (void*)MBB
318      << " (BB#" << MBB->getNumber() << ")";
319  if (Indexes)
320    *OS << " [" << Indexes->getMBBStartIdx(MBB)
321        << ';' <<  Indexes->getMBBEndIdx(MBB) << ')';
322  *OS << '\n';
323}
324
325void MachineVerifier::report(const char *msg, const MachineInstr *MI) {
326  assert(MI);
327  report(msg, MI->getParent());
328  *OS << "- instruction: ";
329  if (Indexes && Indexes->hasIndex(MI))
330    *OS << Indexes->getInstructionIndex(MI) << '\t';
331  MI->print(*OS, TM);
332}
333
334void MachineVerifier::report(const char *msg,
335                             const MachineOperand *MO, unsigned MONum) {
336  assert(MO);
337  report(msg, MO->getParent());
338  *OS << "- operand " << MONum << ":   ";
339  MO->print(*OS, TM);
340  *OS << "\n";
341}
342
343void MachineVerifier::markReachable(const MachineBasicBlock *MBB) {
344  BBInfo &MInfo = MBBInfoMap[MBB];
345  if (!MInfo.reachable) {
346    MInfo.reachable = true;
347    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
348           SuE = MBB->succ_end(); SuI != SuE; ++SuI)
349      markReachable(*SuI);
350  }
351}
352
353void MachineVerifier::visitMachineFunctionBefore() {
354  regsReserved = TRI->getReservedRegs(*MF);
355
356  // A sub-register of a reserved register is also reserved
357  for (int Reg = regsReserved.find_first(); Reg>=0;
358       Reg = regsReserved.find_next(Reg)) {
359    for (const unsigned *Sub = TRI->getSubRegisters(Reg); *Sub; ++Sub) {
360      // FIXME: This should probably be:
361      // assert(regsReserved.test(*Sub) && "Non-reserved sub-register");
362      regsReserved.set(*Sub);
363    }
364  }
365  markReachable(&MF->front());
366}
367
368// Does iterator point to a and b as the first two elements?
369static bool matchPair(MachineBasicBlock::const_succ_iterator i,
370                      const MachineBasicBlock *a, const MachineBasicBlock *b) {
371  if (*i == a)
372    return *++i == b;
373  if (*i == b)
374    return *++i == a;
375  return false;
376}
377
378void
379MachineVerifier::visitMachineBasicBlockBefore(const MachineBasicBlock *MBB) {
380  const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
381
382  // Count the number of landing pad successors.
383  SmallPtrSet<MachineBasicBlock*, 4> LandingPadSuccs;
384  for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
385       E = MBB->succ_end(); I != E; ++I) {
386    if ((*I)->isLandingPad())
387      LandingPadSuccs.insert(*I);
388  }
389  if (LandingPadSuccs.size() > 1)
390    report("MBB has more than one landing pad successor", MBB);
391
392  // Call AnalyzeBranch. If it succeeds, there several more conditions to check.
393  MachineBasicBlock *TBB = 0, *FBB = 0;
394  SmallVector<MachineOperand, 4> Cond;
395  if (!TII->AnalyzeBranch(*const_cast<MachineBasicBlock *>(MBB),
396                          TBB, FBB, Cond)) {
397    // Ok, AnalyzeBranch thinks it knows what's going on with this block. Let's
398    // check whether its answers match up with reality.
399    if (!TBB && !FBB) {
400      // Block falls through to its successor.
401      MachineFunction::const_iterator MBBI = MBB;
402      ++MBBI;
403      if (MBBI == MF->end()) {
404        // It's possible that the block legitimately ends with a noreturn
405        // call or an unreachable, in which case it won't actually fall
406        // out the bottom of the function.
407      } else if (MBB->succ_size() == LandingPadSuccs.size()) {
408        // It's possible that the block legitimately ends with a noreturn
409        // call or an unreachable, in which case it won't actuall fall
410        // out of the block.
411      } else if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
412        report("MBB exits via unconditional fall-through but doesn't have "
413               "exactly one CFG successor!", MBB);
414      } else if (!MBB->isSuccessor(MBBI)) {
415        report("MBB exits via unconditional fall-through but its successor "
416               "differs from its CFG successor!", MBB);
417      }
418      if (!MBB->empty() && MBB->back().getDesc().isBarrier() &&
419          !TII->isPredicated(&MBB->back())) {
420        report("MBB exits via unconditional fall-through but ends with a "
421               "barrier instruction!", MBB);
422      }
423      if (!Cond.empty()) {
424        report("MBB exits via unconditional fall-through but has a condition!",
425               MBB);
426      }
427    } else if (TBB && !FBB && Cond.empty()) {
428      // Block unconditionally branches somewhere.
429      if (MBB->succ_size() != 1+LandingPadSuccs.size()) {
430        report("MBB exits via unconditional branch but doesn't have "
431               "exactly one CFG successor!", MBB);
432      } else if (!MBB->isSuccessor(TBB)) {
433        report("MBB exits via unconditional branch but the CFG "
434               "successor doesn't match the actual successor!", MBB);
435      }
436      if (MBB->empty()) {
437        report("MBB exits via unconditional branch but doesn't contain "
438               "any instructions!", MBB);
439      } else if (!MBB->back().getDesc().isBarrier()) {
440        report("MBB exits via unconditional branch but doesn't end with a "
441               "barrier instruction!", MBB);
442      } else if (!MBB->back().getDesc().isTerminator()) {
443        report("MBB exits via unconditional branch but the branch isn't a "
444               "terminator instruction!", MBB);
445      }
446    } else if (TBB && !FBB && !Cond.empty()) {
447      // Block conditionally branches somewhere, otherwise falls through.
448      MachineFunction::const_iterator MBBI = MBB;
449      ++MBBI;
450      if (MBBI == MF->end()) {
451        report("MBB conditionally falls through out of function!", MBB);
452      } if (MBB->succ_size() != 2) {
453        report("MBB exits via conditional branch/fall-through but doesn't have "
454               "exactly two CFG successors!", MBB);
455      } else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
456        report("MBB exits via conditional branch/fall-through but the CFG "
457               "successors don't match the actual successors!", MBB);
458      }
459      if (MBB->empty()) {
460        report("MBB exits via conditional branch/fall-through but doesn't "
461               "contain any instructions!", MBB);
462      } else if (MBB->back().getDesc().isBarrier()) {
463        report("MBB exits via conditional branch/fall-through but ends with a "
464               "barrier instruction!", MBB);
465      } else if (!MBB->back().getDesc().isTerminator()) {
466        report("MBB exits via conditional branch/fall-through but the branch "
467               "isn't a terminator instruction!", MBB);
468      }
469    } else if (TBB && FBB) {
470      // Block conditionally branches somewhere, otherwise branches
471      // somewhere else.
472      if (MBB->succ_size() != 2) {
473        report("MBB exits via conditional branch/branch but doesn't have "
474               "exactly two CFG successors!", MBB);
475      } else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
476        report("MBB exits via conditional branch/branch but the CFG "
477               "successors don't match the actual successors!", MBB);
478      }
479      if (MBB->empty()) {
480        report("MBB exits via conditional branch/branch but doesn't "
481               "contain any instructions!", MBB);
482      } else if (!MBB->back().getDesc().isBarrier()) {
483        report("MBB exits via conditional branch/branch but doesn't end with a "
484               "barrier instruction!", MBB);
485      } else if (!MBB->back().getDesc().isTerminator()) {
486        report("MBB exits via conditional branch/branch but the branch "
487               "isn't a terminator instruction!", MBB);
488      }
489      if (Cond.empty()) {
490        report("MBB exits via conditinal branch/branch but there's no "
491               "condition!", MBB);
492      }
493    } else {
494      report("AnalyzeBranch returned invalid data!", MBB);
495    }
496  }
497
498  regsLive.clear();
499  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
500         E = MBB->livein_end(); I != E; ++I) {
501    if (!TargetRegisterInfo::isPhysicalRegister(*I)) {
502      report("MBB live-in list contains non-physical register", MBB);
503      continue;
504    }
505    regsLive.insert(*I);
506    for (const unsigned *R = TRI->getSubRegisters(*I); *R; R++)
507      regsLive.insert(*R);
508  }
509  regsLiveInButUnused = regsLive;
510
511  const MachineFrameInfo *MFI = MF->getFrameInfo();
512  assert(MFI && "Function has no frame info");
513  BitVector PR = MFI->getPristineRegs(MBB);
514  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
515    regsLive.insert(I);
516    for (const unsigned *R = TRI->getSubRegisters(I); *R; R++)
517      regsLive.insert(*R);
518  }
519
520  regsKilled.clear();
521  regsDefined.clear();
522}
523
524void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
525  const TargetInstrDesc &TI = MI->getDesc();
526  if (MI->getNumOperands() < TI.getNumOperands()) {
527    report("Too few operands", MI);
528    *OS << TI.getNumOperands() << " operands expected, but "
529        << MI->getNumExplicitOperands() << " given.\n";
530  }
531
532  // Check the MachineMemOperands for basic consistency.
533  for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
534       E = MI->memoperands_end(); I != E; ++I) {
535    if ((*I)->isLoad() && !TI.mayLoad())
536      report("Missing mayLoad flag", MI);
537    if ((*I)->isStore() && !TI.mayStore())
538      report("Missing mayStore flag", MI);
539  }
540
541  // Debug values must not have a slot index.
542  // Other instructions must have one.
543  if (LiveInts) {
544    bool mapped = !LiveInts->isNotInMIMap(MI);
545    if (MI->isDebugValue()) {
546      if (mapped)
547        report("Debug instruction has a slot index", MI);
548    } else {
549      if (!mapped)
550        report("Missing slot index", MI);
551    }
552  }
553
554}
555
556void
557MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
558  const MachineInstr *MI = MO->getParent();
559  const TargetInstrDesc &TI = MI->getDesc();
560  const TargetOperandInfo &TOI = TI.OpInfo[MONum];
561
562  // The first TI.NumDefs operands must be explicit register defines
563  if (MONum < TI.getNumDefs()) {
564    if (!MO->isReg())
565      report("Explicit definition must be a register", MO, MONum);
566    else if (!MO->isDef())
567      report("Explicit definition marked as use", MO, MONum);
568    else if (MO->isImplicit())
569      report("Explicit definition marked as implicit", MO, MONum);
570  } else if (MONum < TI.getNumOperands()) {
571    // Don't check if it's the last operand in a variadic instruction. See,
572    // e.g., LDM_RET in the arm back end.
573    if (MO->isReg() && !(TI.isVariadic() && MONum == TI.getNumOperands()-1)) {
574      if (MO->isDef() && !TOI.isOptionalDef())
575          report("Explicit operand marked as def", MO, MONum);
576      if (MO->isImplicit())
577        report("Explicit operand marked as implicit", MO, MONum);
578    }
579  } else {
580    // ARM adds %reg0 operands to indicate predicates. We'll allow that.
581    if (MO->isReg() && !MO->isImplicit() && !TI.isVariadic() && MO->getReg())
582      report("Extra explicit operand on non-variadic instruction", MO, MONum);
583  }
584
585  switch (MO->getType()) {
586  case MachineOperand::MO_Register: {
587    const unsigned Reg = MO->getReg();
588    if (!Reg)
589      return;
590
591    // Check Live Variables.
592    if (MI->isDebugValue()) {
593      // Liveness checks are not valid for debug values.
594    } else if (MO->isUndef()) {
595      // An <undef> doesn't refer to any register, so just skip it.
596    } else if (MO->isUse()) {
597      regsLiveInButUnused.erase(Reg);
598
599      bool isKill = false;
600      unsigned defIdx;
601      if (MI->isRegTiedToDefOperand(MONum, &defIdx)) {
602        // A two-addr use counts as a kill if use and def are the same.
603        unsigned DefReg = MI->getOperand(defIdx).getReg();
604        if (Reg == DefReg) {
605          isKill = true;
606          // And in that case an explicit kill flag is not allowed.
607          if (MO->isKill())
608            report("Illegal kill flag on two-address instruction operand",
609                   MO, MONum);
610        } else if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
611          report("Two-address instruction operands must be identical",
612                 MO, MONum);
613        }
614      } else
615        isKill = MO->isKill();
616
617      if (isKill)
618        addRegWithSubRegs(regsKilled, Reg);
619
620      // Check that LiveVars knows this kill.
621      if (LiveVars && TargetRegisterInfo::isVirtualRegister(Reg) &&
622          MO->isKill()) {
623        LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
624        if (std::find(VI.Kills.begin(),
625                      VI.Kills.end(), MI) == VI.Kills.end())
626          report("Kill missing from LiveVariables", MO, MONum);
627      }
628
629      // Check LiveInts liveness and kill.
630      if (TargetRegisterInfo::isVirtualRegister(Reg) &&
631          LiveInts && !LiveInts->isNotInMIMap(MI)) {
632        SlotIndex UseIdx = LiveInts->getInstructionIndex(MI).getUseIndex();
633        if (LiveInts->hasInterval(Reg)) {
634          const LiveInterval &LI = LiveInts->getInterval(Reg);
635          if (!LI.liveAt(UseIdx)) {
636            report("No live range at use", MO, MONum);
637            *OS << UseIdx << " is not live in " << LI << '\n';
638          }
639          // Verify isKill == LI.killedAt.
640          // Two-address instrs don't have kill flags on the tied operands, and
641          // we even allow
642          //   %r1 = add %r1, %r1
643          // without a kill flag on the untied operand.
644          // MI->findRegisterUseOperandIdx finds the first operand using reg.
645          if (!MI->isRegTiedToDefOperand(MI->findRegisterUseOperandIdx(Reg))) {
646            // MI could kill register without a kill flag on MO.
647            bool miKill = MI->killsRegister(Reg);
648            bool liKill = LI.killedAt(UseIdx.getDefIndex());
649            if (miKill && !liKill) {
650              report("Live range continues after kill flag", MO, MONum);
651              *OS << "Live range: " << LI << '\n';
652            }
653            if (!miKill && liKill) {
654              report("Live range ends without kill flag", MO, MONum);
655              *OS << "Live range: " << LI << '\n';
656            }
657          }
658        } else {
659          report("Virtual register has no Live interval", MO, MONum);
660        }
661      }
662
663      // Use of a dead register.
664      if (!regsLive.count(Reg)) {
665        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
666          // Reserved registers may be used even when 'dead'.
667          if (!isReserved(Reg))
668            report("Using an undefined physical register", MO, MONum);
669        } else {
670          BBInfo &MInfo = MBBInfoMap[MI->getParent()];
671          // We don't know which virtual registers are live in, so only complain
672          // if vreg was killed in this MBB. Otherwise keep track of vregs that
673          // must be live in. PHI instructions are handled separately.
674          if (MInfo.regsKilled.count(Reg))
675            report("Using a killed virtual register", MO, MONum);
676          else if (!MI->isPHI())
677            MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI));
678        }
679      }
680    } else {
681      assert(MO->isDef());
682      // Register defined.
683      // TODO: verify that earlyclobber ops are not used.
684      if (MO->isDead())
685        addRegWithSubRegs(regsDead, Reg);
686      else
687        addRegWithSubRegs(regsDefined, Reg);
688
689      // Check LiveInts for a live range, but only for virtual registers.
690      if (LiveInts && TargetRegisterInfo::isVirtualRegister(Reg) &&
691          !LiveInts->isNotInMIMap(MI)) {
692        SlotIndex DefIdx = LiveInts->getInstructionIndex(MI).getDefIndex();
693        if (LiveInts->hasInterval(Reg)) {
694          const LiveInterval &LI = LiveInts->getInterval(Reg);
695          if (const VNInfo *VNI = LI.getVNInfoAt(DefIdx)) {
696            assert(VNI && "NULL valno is not allowed");
697            if (VNI->def != DefIdx && !MO->isEarlyClobber()) {
698              report("Inconsistent valno->def", MO, MONum);
699              *OS << "Valno " << VNI->id << " is not defined at "
700                  << DefIdx << " in " << LI << '\n';
701            }
702          } else {
703            report("No live range at def", MO, MONum);
704            *OS << DefIdx << " is not live in " << LI << '\n';
705          }
706        } else {
707          report("Virtual register has no Live interval", MO, MONum);
708        }
709      }
710    }
711
712    // Check register classes.
713    if (MONum < TI.getNumOperands() && !MO->isImplicit()) {
714      unsigned SubIdx = MO->getSubReg();
715
716      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
717        unsigned sr = Reg;
718        if (SubIdx) {
719          unsigned s = TRI->getSubReg(Reg, SubIdx);
720          if (!s) {
721            report("Invalid subregister index for physical register",
722                   MO, MONum);
723            return;
724          }
725          sr = s;
726        }
727        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
728          if (!DRC->contains(sr)) {
729            report("Illegal physical register for instruction", MO, MONum);
730            *OS << TRI->getName(sr) << " is not a "
731                << DRC->getName() << " register.\n";
732          }
733        }
734      } else {
735        // Virtual register.
736        const TargetRegisterClass *RC = MRI->getRegClass(Reg);
737        if (SubIdx) {
738          const TargetRegisterClass *SRC = RC->getSubRegisterRegClass(SubIdx);
739          if (!SRC) {
740            report("Invalid subregister index for virtual register", MO, MONum);
741            *OS << "Register class " << RC->getName()
742                << " does not support subreg index " << SubIdx << "\n";
743            return;
744          }
745          RC = SRC;
746        }
747        if (const TargetRegisterClass *DRC = TOI.getRegClass(TRI)) {
748          if (RC != DRC && !RC->hasSuperClass(DRC)) {
749            report("Illegal virtual register for instruction", MO, MONum);
750            *OS << "Expected a " << DRC->getName() << " register, but got a "
751                << RC->getName() << " register\n";
752          }
753        }
754      }
755    }
756    break;
757  }
758
759  case MachineOperand::MO_MachineBasicBlock:
760    if (MI->isPHI() && !MO->getMBB()->isSuccessor(MI->getParent()))
761      report("PHI operand is not in the CFG", MO, MONum);
762    break;
763
764  case MachineOperand::MO_FrameIndex:
765    if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
766        LiveInts && !LiveInts->isNotInMIMap(MI)) {
767      LiveInterval &LI = LiveStks->getInterval(MO->getIndex());
768      SlotIndex Idx = LiveInts->getInstructionIndex(MI);
769      if (TI.mayLoad() && !LI.liveAt(Idx.getUseIndex())) {
770        report("Instruction loads from dead spill slot", MO, MONum);
771        *OS << "Live stack: " << LI << '\n';
772      }
773      if (TI.mayStore() && !LI.liveAt(Idx.getDefIndex())) {
774        report("Instruction stores to dead spill slot", MO, MONum);
775        *OS << "Live stack: " << LI << '\n';
776      }
777    }
778    break;
779
780  default:
781    break;
782  }
783}
784
785void MachineVerifier::visitMachineInstrAfter(const MachineInstr *MI) {
786  BBInfo &MInfo = MBBInfoMap[MI->getParent()];
787  set_union(MInfo.regsKilled, regsKilled);
788  set_subtract(regsLive, regsKilled); regsKilled.clear();
789  set_subtract(regsLive, regsDead);   regsDead.clear();
790  set_union(regsLive, regsDefined);   regsDefined.clear();
791}
792
793void
794MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) {
795  MBBInfoMap[MBB].regsLiveOut = regsLive;
796  regsLive.clear();
797}
798
799// Calculate the largest possible vregsPassed sets. These are the registers that
800// can pass through an MBB live, but may not be live every time. It is assumed
801// that all vregsPassed sets are empty before the call.
802void MachineVerifier::calcRegsPassed() {
803  // First push live-out regs to successors' vregsPassed. Remember the MBBs that
804  // have any vregsPassed.
805  DenseSet<const MachineBasicBlock*> todo;
806  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
807       MFI != MFE; ++MFI) {
808    const MachineBasicBlock &MBB(*MFI);
809    BBInfo &MInfo = MBBInfoMap[&MBB];
810    if (!MInfo.reachable)
811      continue;
812    for (MachineBasicBlock::const_succ_iterator SuI = MBB.succ_begin(),
813           SuE = MBB.succ_end(); SuI != SuE; ++SuI) {
814      BBInfo &SInfo = MBBInfoMap[*SuI];
815      if (SInfo.addPassed(MInfo.regsLiveOut))
816        todo.insert(*SuI);
817    }
818  }
819
820  // Iteratively push vregsPassed to successors. This will converge to the same
821  // final state regardless of DenseSet iteration order.
822  while (!todo.empty()) {
823    const MachineBasicBlock *MBB = *todo.begin();
824    todo.erase(MBB);
825    BBInfo &MInfo = MBBInfoMap[MBB];
826    for (MachineBasicBlock::const_succ_iterator SuI = MBB->succ_begin(),
827           SuE = MBB->succ_end(); SuI != SuE; ++SuI) {
828      if (*SuI == MBB)
829        continue;
830      BBInfo &SInfo = MBBInfoMap[*SuI];
831      if (SInfo.addPassed(MInfo.vregsPassed))
832        todo.insert(*SuI);
833    }
834  }
835}
836
837// Calculate the set of virtual registers that must be passed through each basic
838// block in order to satisfy the requirements of successor blocks. This is very
839// similar to calcRegsPassed, only backwards.
840void MachineVerifier::calcRegsRequired() {
841  // First push live-in regs to predecessors' vregsRequired.
842  DenseSet<const MachineBasicBlock*> todo;
843  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
844       MFI != MFE; ++MFI) {
845    const MachineBasicBlock &MBB(*MFI);
846    BBInfo &MInfo = MBBInfoMap[&MBB];
847    for (MachineBasicBlock::const_pred_iterator PrI = MBB.pred_begin(),
848           PrE = MBB.pred_end(); PrI != PrE; ++PrI) {
849      BBInfo &PInfo = MBBInfoMap[*PrI];
850      if (PInfo.addRequired(MInfo.vregsLiveIn))
851        todo.insert(*PrI);
852    }
853  }
854
855  // Iteratively push vregsRequired to predecessors. This will converge to the
856  // same final state regardless of DenseSet iteration order.
857  while (!todo.empty()) {
858    const MachineBasicBlock *MBB = *todo.begin();
859    todo.erase(MBB);
860    BBInfo &MInfo = MBBInfoMap[MBB];
861    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
862           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
863      if (*PrI == MBB)
864        continue;
865      BBInfo &SInfo = MBBInfoMap[*PrI];
866      if (SInfo.addRequired(MInfo.vregsRequired))
867        todo.insert(*PrI);
868    }
869  }
870}
871
872// Check PHI instructions at the beginning of MBB. It is assumed that
873// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
874void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
875  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
876       BBI != BBE && BBI->isPHI(); ++BBI) {
877    DenseSet<const MachineBasicBlock*> seen;
878
879    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
880      unsigned Reg = BBI->getOperand(i).getReg();
881      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
882      if (!Pre->isSuccessor(MBB))
883        continue;
884      seen.insert(Pre);
885      BBInfo &PrInfo = MBBInfoMap[Pre];
886      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
887        report("PHI operand is not live-out from predecessor",
888               &BBI->getOperand(i), i);
889    }
890
891    // Did we see all predecessors?
892    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
893           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
894      if (!seen.count(*PrI)) {
895        report("Missing PHI operand", BBI);
896        *OS << "BB#" << (*PrI)->getNumber()
897            << " is a predecessor according to the CFG.\n";
898      }
899    }
900  }
901}
902
903void MachineVerifier::visitMachineFunctionAfter() {
904  calcRegsPassed();
905
906  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
907       MFI != MFE; ++MFI) {
908    BBInfo &MInfo = MBBInfoMap[MFI];
909
910    // Skip unreachable MBBs.
911    if (!MInfo.reachable)
912      continue;
913
914    checkPHIOps(MFI);
915  }
916
917  // Now check liveness info if available
918  if (LiveVars || LiveInts)
919    calcRegsRequired();
920  if (LiveVars)
921    verifyLiveVariables();
922  if (LiveInts)
923    verifyLiveIntervals();
924}
925
926void MachineVerifier::verifyLiveVariables() {
927  assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
928  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
929    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
930    LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
931    for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
932         MFI != MFE; ++MFI) {
933      BBInfo &MInfo = MBBInfoMap[MFI];
934
935      // Our vregsRequired should be identical to LiveVariables' AliveBlocks
936      if (MInfo.vregsRequired.count(Reg)) {
937        if (!VI.AliveBlocks.test(MFI->getNumber())) {
938          report("LiveVariables: Block missing from AliveBlocks", MFI);
939          *OS << "Virtual register " << PrintReg(Reg)
940              << " must be live through the block.\n";
941        }
942      } else {
943        if (VI.AliveBlocks.test(MFI->getNumber())) {
944          report("LiveVariables: Block should not be in AliveBlocks", MFI);
945          *OS << "Virtual register " << PrintReg(Reg)
946              << " is not needed live through the block.\n";
947        }
948      }
949    }
950  }
951}
952
953void MachineVerifier::verifyLiveIntervals() {
954  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
955  for (LiveIntervals::const_iterator LVI = LiveInts->begin(),
956       LVE = LiveInts->end(); LVI != LVE; ++LVI) {
957    const LiveInterval &LI = *LVI->second;
958
959    // Spilling and splitting may leave unused registers around. Skip them.
960    if (MRI->use_empty(LI.reg))
961      continue;
962
963    // Physical registers have much weirdness going on, mostly from coalescing.
964    // We should probably fix it, but for now just ignore them.
965    if (TargetRegisterInfo::isPhysicalRegister(LI.reg))
966      continue;
967
968    assert(LVI->first == LI.reg && "Invalid reg to interval mapping");
969
970    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
971         I!=E; ++I) {
972      VNInfo *VNI = *I;
973      const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);
974
975      if (!DefVNI) {
976        if (!VNI->isUnused()) {
977          report("Valno not live at def and not marked unused", MF);
978          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
979        }
980        continue;
981      }
982
983      if (VNI->isUnused())
984        continue;
985
986      if (DefVNI != VNI) {
987        report("Live range at def has different valno", MF);
988        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
989            << " where valno #" << DefVNI->id << " is live in " << LI << '\n';
990        continue;
991      }
992
993      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
994      if (!MBB) {
995        report("Invalid definition index", MF);
996        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
997            << " in " << LI << '\n';
998        continue;
999      }
1000
1001      if (VNI->isPHIDef()) {
1002        if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
1003          report("PHIDef value is not defined at MBB start", MF);
1004          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1005              << ", not at the beginning of BB#" << MBB->getNumber()
1006              << " in " << LI << '\n';
1007        }
1008      } else {
1009        // Non-PHI def.
1010        const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
1011        if (!MI) {
1012          report("No instruction at def index", MF);
1013          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1014              << " in " << LI << '\n';
1015        } else if (!MI->modifiesRegister(LI.reg, TRI)) {
1016          report("Defining instruction does not modify register", MI);
1017          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
1018        }
1019
1020        bool isEarlyClobber = false;
1021        if (MI) {
1022          for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
1023               MOE = MI->operands_end(); MOI != MOE; ++MOI) {
1024            if (MOI->isReg() && MOI->getReg() == LI.reg && MOI->isDef() &&
1025                MOI->isEarlyClobber()) {
1026              isEarlyClobber = true;
1027              break;
1028            }
1029          }
1030        }
1031
1032        // Early clobber defs begin at USE slots, but other defs must begin at
1033        // DEF slots.
1034        if (isEarlyClobber) {
1035          if (!VNI->def.isUse()) {
1036            report("Early clobber def must be at a USE slot", MF);
1037            *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1038                << " in " << LI << '\n';
1039          }
1040        } else if (!VNI->def.isDef()) {
1041          report("Non-PHI, non-early clobber def must be at a DEF slot", MF);
1042          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
1043              << " in " << LI << '\n';
1044        }
1045      }
1046    }
1047
1048    for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
1049      const VNInfo *VNI = I->valno;
1050      assert(VNI && "Live range has no valno");
1051
1052      if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
1053        report("Foreign valno in live range", MF);
1054        I->print(*OS);
1055        *OS << " has a valno not in " << LI << '\n';
1056      }
1057
1058      if (VNI->isUnused()) {
1059        report("Live range valno is marked unused", MF);
1060        I->print(*OS);
1061        *OS << " in " << LI << '\n';
1062      }
1063
1064      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start);
1065      if (!MBB) {
1066        report("Bad start of live segment, no basic block", MF);
1067        I->print(*OS);
1068        *OS << " in " << LI << '\n';
1069        continue;
1070      }
1071      SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
1072      if (I->start != MBBStartIdx && I->start != VNI->def) {
1073        report("Live segment must begin at MBB entry or valno def", MBB);
1074        I->print(*OS);
1075        *OS << " in " << LI << '\n' << "Basic block starts at "
1076            << MBBStartIdx << '\n';
1077      }
1078
1079      const MachineBasicBlock *EndMBB =
1080                                LiveInts->getMBBFromIndex(I->end.getPrevSlot());
1081      if (!EndMBB) {
1082        report("Bad end of live segment, no basic block", MF);
1083        I->print(*OS);
1084        *OS << " in " << LI << '\n';
1085        continue;
1086      }
1087      if (I->end != LiveInts->getMBBEndIdx(EndMBB)) {
1088        // The live segment is ending inside EndMBB
1089        const MachineInstr *MI =
1090                        LiveInts->getInstructionFromIndex(I->end.getPrevSlot());
1091        if (!MI) {
1092          report("Live segment doesn't end at a valid instruction", EndMBB);
1093        I->print(*OS);
1094        *OS << " in " << LI << '\n' << "Basic block starts at "
1095            << MBBStartIdx << '\n';
1096        } else if (TargetRegisterInfo::isVirtualRegister(LI.reg) &&
1097                   !MI->readsVirtualRegister(LI.reg)) {
1098          // A live range can end with either a redefinition, a kill flag on a
1099          // use, or a dead flag on a def.
1100          // FIXME: Should we check for each of these?
1101          bool hasDeadDef = false;
1102          for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
1103               MOE = MI->operands_end(); MOI != MOE; ++MOI) {
1104            if (MOI->isReg() && MOI->getReg() == LI.reg && MOI->isDef() && MOI->isDead()) {
1105              hasDeadDef = true;
1106              break;
1107            }
1108          }
1109
1110          if (!hasDeadDef) {
1111            report("Instruction killing live segment neither defines nor reads "
1112                   "register", MI);
1113            I->print(*OS);
1114            *OS << " in " << LI << '\n';
1115          }
1116        }
1117      }
1118
1119      // Now check all the basic blocks in this live segment.
1120      MachineFunction::const_iterator MFI = MBB;
1121      // Is this live range the beginning of a non-PHIDef VN?
1122      if (I->start == VNI->def && !VNI->isPHIDef()) {
1123        // Not live-in to any blocks.
1124        if (MBB == EndMBB)
1125          continue;
1126        // Skip this block.
1127        ++MFI;
1128      }
1129      for (;;) {
1130        assert(LiveInts->isLiveInToMBB(LI, MFI));
1131        // We don't know how to track physregs into a landing pad.
1132        if (TargetRegisterInfo::isPhysicalRegister(LI.reg) &&
1133            MFI->isLandingPad()) {
1134          if (&*MFI == EndMBB)
1135            break;
1136          ++MFI;
1137          continue;
1138        }
1139        // Check that VNI is live-out of all predecessors.
1140        for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
1141             PE = MFI->pred_end(); PI != PE; ++PI) {
1142          SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI).getPrevSlot();
1143          const VNInfo *PVNI = LI.getVNInfoAt(PEnd);
1144
1145          if (VNI->isPHIDef() && VNI->def == LiveInts->getMBBStartIdx(MFI)) {
1146            if (PVNI && !PVNI->hasPHIKill()) {
1147              report("Value live out of predecessor doesn't have PHIKill", MF);
1148              *OS << "Valno #" << PVNI->id << " live out of BB#"
1149                  << (*PI)->getNumber() << '@' << PEnd
1150                  << " doesn't have PHIKill, but Valno #" << VNI->id
1151                  << " is PHIDef and defined at the beginning of BB#"
1152                  << MFI->getNumber() << '@' << LiveInts->getMBBStartIdx(MFI)
1153                  << " in " << LI << '\n';
1154            }
1155            continue;
1156          }
1157
1158          if (!PVNI) {
1159            report("Register not marked live out of predecessor", *PI);
1160            *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
1161                << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live at "
1162                << PEnd << " in " << LI << '\n';
1163            continue;
1164          }
1165
1166          if (PVNI != VNI) {
1167            report("Different value live out of predecessor", *PI);
1168            *OS << "Valno #" << PVNI->id << " live out of BB#"
1169                << (*PI)->getNumber() << '@' << PEnd
1170                << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
1171                << '@' << LiveInts->getMBBStartIdx(MFI) << " in " << LI << '\n';
1172          }
1173        }
1174        if (&*MFI == EndMBB)
1175          break;
1176        ++MFI;
1177      }
1178    }
1179
1180    // Check the LI only has one connected component.
1181    if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
1182      ConnectedVNInfoEqClasses ConEQ(*LiveInts);
1183      unsigned NumComp = ConEQ.Classify(&LI);
1184      if (NumComp > 1) {
1185        report("Multiple connected components in live interval", MF);
1186        *OS << NumComp << " components in " << LI << '\n';
1187        for (unsigned comp = 0; comp != NumComp; ++comp) {
1188          *OS << comp << ": valnos";
1189          for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
1190               E = LI.vni_end(); I!=E; ++I)
1191            if (comp == ConEQ.getEqClass(*I))
1192              *OS << ' ' << (*I)->id;
1193          *OS << '\n';
1194        }
1195      }
1196    }
1197  }
1198}
1199
1200