MachineVerifier.cpp

}

// Check PHI instructions at the beginning of MBB. It is assumed that
// calcRegsPassed has been run so BBInfo::isLiveOut is valid.
void MachineVerifier::checkPHIOps(const MachineBasicBlock *MBB) {
  SmallPtrSet<const MachineBasicBlock*, 8> seen;
  for (MachineBasicBlock::const_iterator BBI = MBB->begin(), BBE = MBB->end();
       BBI != BBE && BBI->isPHI(); ++BBI) {
    seen.clear();

    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
      unsigned Reg = BBI->getOperand(i).getReg();
      const MachineBasicBlock *Pre = BBI->getOperand(i + 1).getMBB();
      if (!Pre->isSuccessor(MBB))
        continue;
      seen.insert(Pre);
      BBInfo &PrInfo = MBBInfoMap[Pre];
      if (PrInfo.reachable && !PrInfo.isLiveOut(Reg))
        report("PHI operand is not live-out from predecessor",
               &BBI->getOperand(i), i);
    }

    // Did we see all predecessors?
    for (MachineBasicBlock::const_pred_iterator PrI = MBB->pred_begin(),
           PrE = MBB->pred_end(); PrI != PrE; ++PrI) {
      if (!seen.count(*PrI)) {
        report("Missing PHI operand", BBI);
        *OS << "BB#" << (*PrI)->getNumber()
            << " is a predecessor according to the CFG.\n";
      }
    }
  }
}

void MachineVerifier::visitMachineFunctionAfter() {
  calcRegsPassed();

  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
       MFI != MFE; ++MFI) {
    BBInfo &MInfo = MBBInfoMap[MFI];

    // Skip unreachable MBBs.
    if (!MInfo.reachable)
      continue;

    checkPHIOps(MFI);
  }

  // Now check liveness info if available
  calcRegsRequired();

  // Check for killed virtual registers that should be live out.
  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
       MFI != MFE; ++MFI) {
    BBInfo &MInfo = MBBInfoMap[MFI];
    for (RegSet::iterator
         I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
         ++I)
      if (MInfo.regsKilled.count(*I)) {
	report("Virtual register killed in block, but needed live out.", MFI);
	*OS << "Virtual register " << PrintReg(*I)
            << " is used after the block.\n";
      }
  }

  if (!MF->empty()) {
    BBInfo &MInfo = MBBInfoMap[&MF->front()];
    for (RegSet::iterator
         I = MInfo.vregsRequired.begin(), E = MInfo.vregsRequired.end(); I != E;
         ++I)
      report("Virtual register def doesn't dominate all uses.",
             MRI->getVRegDef(*I));
  }

  if (LiveVars)
    verifyLiveVariables();
  if (LiveInts)
    verifyLiveIntervals();
}

void MachineVerifier::verifyLiveVariables() {
  assert(LiveVars && "Don't call verifyLiveVariables without LiveVars");
  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg);
    for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
         MFI != MFE; ++MFI) {
      BBInfo &MInfo = MBBInfoMap[MFI];

      // Our vregsRequired should be identical to LiveVariables' AliveBlocks
      if (MInfo.vregsRequired.count(Reg)) {
        if (!VI.AliveBlocks.test(MFI->getNumber())) {
          report("LiveVariables: Block missing from AliveBlocks", MFI);
          *OS << "Virtual register " << PrintReg(Reg)
              << " must be live through the block.\n";
        }
      } else {
        if (VI.AliveBlocks.test(MFI->getNumber())) {
          report("LiveVariables: Block should not be in AliveBlocks", MFI);
          *OS << "Virtual register " << PrintReg(Reg)
              << " is not needed live through the block.\n";
        }
      }
    }
  }
}

void MachineVerifier::verifyLiveIntervals() {
  assert(LiveInts && "Don't call verifyLiveIntervals without LiveInts");
  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);

    // Spilling and splitting may leave unused registers around. Skip them.
    if (MRI->reg_nodbg_empty(Reg))
      continue;

    if (!LiveInts->hasInterval(Reg)) {
      report("Missing live interval for virtual register", MF);
      *OS << PrintReg(Reg, TRI) << " still has defs or uses\n";
      continue;
    }

    const LiveInterval &LI = LiveInts->getInterval(Reg);
    assert(Reg == LI.reg && "Invalid reg to interval mapping");

    for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
         I!=E; ++I) {
      VNInfo *VNI = *I;
      const VNInfo *DefVNI = LI.getVNInfoAt(VNI->def);

      if (!DefVNI) {
        if (!VNI->isUnused()) {
          report("Valno not live at def and not marked unused", MF);
          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
        }
        continue;
      }

      if (VNI->isUnused())
        continue;

      if (DefVNI != VNI) {
        report("Live range at def has different valno", MF);
        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
            << " where valno #" << DefVNI->id << " is live in " << LI << '\n';
        continue;
      }

      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(VNI->def);
      if (!MBB) {
        report("Invalid definition index", MF);
        *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
            << " in " << LI << '\n';
        continue;
      }

      if (VNI->isPHIDef()) {
        if (VNI->def != LiveInts->getMBBStartIdx(MBB)) {
          report("PHIDef value is not defined at MBB start", MF);
          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
              << ", not at the beginning of BB#" << MBB->getNumber()
              << " in " << LI << '\n';
        }
      } else {
        // Non-PHI def.
        const MachineInstr *MI = LiveInts->getInstructionFromIndex(VNI->def);
        if (!MI) {
          report("No instruction at def index", MF);
          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
              << " in " << LI << '\n';
          continue;
        }

        bool hasDef = false;
        bool isEarlyClobber = false;
        for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
          if (!MOI->isReg() || !MOI->isDef())
            continue;
          if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
            if (MOI->getReg() != LI.reg)
              continue;
          } else {
            if (!TargetRegisterInfo::isPhysicalRegister(MOI->getReg()) ||
                !TRI->regsOverlap(LI.reg, MOI->getReg()))
              continue;
          }
          hasDef = true;
          if (MOI->isEarlyClobber())
            isEarlyClobber = true;
        }

        if (!hasDef) {
          report("Defining instruction does not modify register", MI);
          *OS << "Valno #" << VNI->id << " in " << LI << '\n';
        }

        // Early clobber defs begin at USE slots, but other defs must begin at
        // DEF slots.
        if (isEarlyClobber) {
          if (!VNI->def.isEarlyClobber()) {
            report("Early clobber def must be at an early-clobber slot", MF);
            *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
                << " in " << LI << '\n';
          }
        } else if (!VNI->def.isRegister()) {
          report("Non-PHI, non-early clobber def must be at a register slot",
                 MF);
          *OS << "Valno #" << VNI->id << " is defined at " << VNI->def
              << " in " << LI << '\n';
        }
      }
    }

    for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I!=E; ++I) {
      const VNInfo *VNI = I->valno;
      assert(VNI && "Live range has no valno");

      if (VNI->id >= LI.getNumValNums() || VNI != LI.getValNumInfo(VNI->id)) {
        report("Foreign valno in live range", MF);
        I->print(*OS);
        *OS << " has a valno not in " << LI << '\n';
      }

      if (VNI->isUnused()) {
        report("Live range valno is marked unused", MF);
        I->print(*OS);
        *OS << " in " << LI << '\n';
      }

      const MachineBasicBlock *MBB = LiveInts->getMBBFromIndex(I->start);
      if (!MBB) {
        report("Bad start of live segment, no basic block", MF);
        I->print(*OS);
        *OS << " in " << LI << '\n';
        continue;
      }
      SlotIndex MBBStartIdx = LiveInts->getMBBStartIdx(MBB);
      if (I->start != MBBStartIdx && I->start != VNI->def) {
        report("Live segment must begin at MBB entry or valno def", MBB);
        I->print(*OS);
        *OS << " in " << LI << '\n' << "Basic block starts at "
            << MBBStartIdx << '\n';
      }

      const MachineBasicBlock *EndMBB =
                                LiveInts->getMBBFromIndex(I->end.getPrevSlot());
      if (!EndMBB) {
        report("Bad end of live segment, no basic block", MF);
        I->print(*OS);
        *OS << " in " << LI << '\n';
        continue;
      }

      // No more checks for live-out segments.
      if (I->end == LiveInts->getMBBEndIdx(EndMBB))
        continue;

      // The live segment is ending inside EndMBB
      const MachineInstr *MI =
        LiveInts->getInstructionFromIndex(I->end.getPrevSlot());
      if (!MI) {
        report("Live segment doesn't end at a valid instruction", EndMBB);
        I->print(*OS);
        *OS << " in " << LI << '\n' << "Basic block starts at "
          << MBBStartIdx << '\n';
        continue;
      }

      // The block slot must refer to a basic block boundary.
      if (I->end.isBlock()) {
        report("Live segment ends at B slot of an instruction", MI);
        I->print(*OS);
        *OS << " in " << LI << '\n';
      }

      if (I->end.isDead()) {
        // Segment ends on the dead slot.
        // That means there must be a dead def.
        if (!SlotIndex::isSameInstr(I->start, I->end)) {
          report("Live segment ending at dead slot spans instructions", MI);
          I->print(*OS);
          *OS << " in " << LI << '\n';
        }
      }

      // A live segment can only end at an early-clobber slot if it is being
      // redefined by an early-clobber def.
      if (I->end.isEarlyClobber()) {
        if (I+1 == E || (I+1)->start != I->end) {
          report("Live segment ending at early clobber slot must be "
                 "redefined by an EC def in the same instruction", MI);
          I->print(*OS);
          *OS << " in " << LI << '\n';
        }
      }

      // The following checks only apply to virtual registers. Physreg liveness
      // is too weird to check.
      if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
        // A live range can end with either a redefinition, a kill flag on a
        // use, or a dead flag on a def.
        bool hasRead = false;
        bool hasDeadDef = false;
        for (ConstMIBundleOperands MOI(MI); MOI.isValid(); ++MOI) {
          if (!MOI->isReg() || MOI->getReg() != LI.reg)
            continue;
          if (MOI->readsReg())
            hasRead = true;
          if (MOI->isDef() && MOI->isDead())
            hasDeadDef = true;
        }

        if (I->end.isDead()) {
          if (!hasDeadDef) {
            report("Instruction doesn't have a dead def operand", MI);
            I->print(*OS);
            *OS << " in " << LI << '\n';
          }
        } else {
          if (!hasRead) {
            report("Instruction ending live range doesn't read the register",
                   MI);
            I->print(*OS);
            *OS << " in " << LI << '\n';
          }
        }
      }

      // Now check all the basic blocks in this live segment.
      MachineFunction::const_iterator MFI = MBB;
      // Is this live range the beginning of a non-PHIDef VN?
      if (I->start == VNI->def && !VNI->isPHIDef()) {
        // Not live-in to any blocks.
        if (MBB == EndMBB)
          continue;
        // Skip this block.
        ++MFI;
      }
      for (;;) {
        assert(LiveInts->isLiveInToMBB(LI, MFI));
        // We don't know how to track physregs into a landing pad.
        if (TargetRegisterInfo::isPhysicalRegister(LI.reg) &&
            MFI->isLandingPad()) {
          if (&*MFI == EndMBB)
            break;
          ++MFI;
          continue;
        }

        // Is VNI a PHI-def in the current block?
        bool IsPHI = VNI->isPHIDef() &&
                     VNI->def == LiveInts->getMBBStartIdx(MFI);

        // Check that VNI is live-out of all predecessors.
        for (MachineBasicBlock::const_pred_iterator PI = MFI->pred_begin(),
             PE = MFI->pred_end(); PI != PE; ++PI) {
          SlotIndex PEnd = LiveInts->getMBBEndIdx(*PI);
          const VNInfo *PVNI = LI.getVNInfoBefore(PEnd);

          // All predecessors must have a live-out value.
          if (!PVNI) {
            report("Register not marked live out of predecessor", *PI);
            *OS << "Valno #" << VNI->id << " live into BB#" << MFI->getNumber()
                << '@' << LiveInts->getMBBStartIdx(MFI) << ", not live before "
                << PEnd << " in " << LI << '\n';
            continue;
          }

          // Only PHI-defs can take different predecessor values.
          if (!IsPHI && PVNI != VNI) {
            report("Different value live out of predecessor", *PI);
            *OS << "Valno #" << PVNI->id << " live out of BB#"
                << (*PI)->getNumber() << '@' << PEnd
                << "\nValno #" << VNI->id << " live into BB#" << MFI->getNumber()
                << '@' << LiveInts->getMBBStartIdx(MFI) << " in "
                << PrintReg(Reg) << ": " << LI << '\n';
          }
        }
        if (&*MFI == EndMBB)
          break;
        ++MFI;
      }
    }

    // Check the LI only has one connected component.
    if (TargetRegisterInfo::isVirtualRegister(LI.reg)) {
      ConnectedVNInfoEqClasses ConEQ(*LiveInts);
      unsigned NumComp = ConEQ.Classify(&LI);
      if (NumComp > 1) {
        report("Multiple connected components in live interval", MF);
        *OS << NumComp << " components in " << LI << '\n';
        for (unsigned comp = 0; comp != NumComp; ++comp) {
          *OS << comp << ": valnos";
          for (LiveInterval::const_vni_iterator I = LI.vni_begin(),
               E = LI.vni_end(); I!=E; ++I)
            if (comp == ConEQ.getEqClass(*I))
              *OS << ' ' << (*I)->id;
          *OS << '\n';
        }
      }
    }
  }
}