diff --git a/lib/CodeGen/EarlyIfConversion.cpp b/lib/CodeGen/EarlyIfConversion.cpp
index a19e9ad..f5cf107 100644
--- a/lib/CodeGen/EarlyIfConversion.cpp
+++ b/lib/CodeGen/EarlyIfConversion.cpp
@@ -586,11 +586,13 @@
 
 /// Invalidate MachineTraceMetrics before if-conversion.
 void EarlyIfConverter::invalidateTraces() {
+  Traces->verify();
   Traces->invalidate(IfConv.Head);
   Traces->invalidate(IfConv.Tail);
   Traces->invalidate(IfConv.TBB);
   Traces->invalidate(IfConv.FBB);
   DEBUG(if (MinInstr) MinInstr->print(dbgs()));
+  Traces->verify();
 }
 
 /// Apply cost model and heuristics to the if-conversion in IfConv.
diff --git a/lib/CodeGen/MachineTraceMetrics.cpp b/lib/CodeGen/MachineTraceMetrics.cpp
index d5ff128..3037cb3 100644
--- a/lib/CodeGen/MachineTraceMetrics.cpp
+++ b/lib/CodeGen/MachineTraceMetrics.cpp
@@ -44,13 +44,13 @@
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
-bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &MF) {
-  TII = MF.getTarget().getInstrInfo();
-  TRI = MF.getTarget().getRegisterInfo();
-  MRI = &MF.getRegInfo();
+bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) {
+  MF = &Func;
+  TII = MF->getTarget().getInstrInfo();
+  TRI = MF->getTarget().getRegisterInfo();
+  MRI = &MF->getRegInfo();
   Loops = &getAnalysis<MachineLoopInfo>();
-  unsigned NumBlocks = MF.getNumBlockIDs();
-  BlockInfo.resize(NumBlocks);
+  BlockInfo.resize(MF->getNumBlockIDs());
   return false;
 }
 
@@ -128,8 +128,8 @@
 // Virtual destructor serves as an anchor.
 MachineTraceMetrics::Ensemble::~Ensemble() {}
 
-MachineLoop*
-MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) {
+const MachineLoop*
+MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const {
   return CT.Loops->getLoopFor(MBB);
 }
 
@@ -226,7 +226,7 @@
 MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) {
   if (MBB->pred_empty())
     return 0;
-  MachineLoop *CurLoop = getLoopFor(MBB);
+  const MachineLoop *CurLoop = getLoopFor(MBB);
   // Don't leave loops, and never follow back-edges.
   if (CurLoop && MBB == CurLoop->getHeader())
     return 0;
@@ -258,7 +258,7 @@
 MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) {
   if (MBB->pred_empty())
     return 0;
-  MachineLoop *CurLoop = getLoopFor(MBB);
+  const MachineLoop *CurLoop = getLoopFor(MBB);
   const MachineBasicBlock *Best = 0;
   unsigned BestHeight = 0;
   for (MachineBasicBlock::const_succ_iterator
@@ -306,6 +306,15 @@
       Ensembles[i]->invalidate(MBB);
 }
 
+void MachineTraceMetrics::verify() const {
+#ifndef NDEBUG
+  assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size");
+  for (unsigned i = 0; i != TS_NumStrategies; ++i)
+    if (Ensembles[i])
+      Ensembles[i]->verify();
+#endif
+}
+
 //===----------------------------------------------------------------------===//
 //                               Trace building
 //===----------------------------------------------------------------------===//
@@ -460,6 +469,33 @@
   }
 }
 
+void MachineTraceMetrics::Ensemble::verify() const {
+#ifndef NDEBUG
+  assert(BlockInfo.size() == CT.MF->getNumBlockIDs() &&
+         "Outdated BlockInfo size");
+  for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) {
+    const TraceBlockInfo &TBI = BlockInfo[Num];
+    if (TBI.hasValidDepth() && TBI.Pred) {
+      const MachineBasicBlock *MBB = CT.MF->getBlockNumbered(Num);
+      assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace");
+      assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() &&
+             "Trace is broken, depth should have been invalidated.");
+      const MachineLoop *Loop = getLoopFor(MBB);
+      assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge");
+    }
+    if (TBI.hasValidHeight() && TBI.Succ) {
+      const MachineBasicBlock *MBB = CT.MF->getBlockNumbered(Num);
+      assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace");
+      assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() &&
+             "Trace is broken, height should have been invalidated.");
+      const MachineLoop *Loop = getLoopFor(MBB);
+      const MachineLoop *SuccLoop = getLoopFor(TBI.Succ);
+      assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) &&
+             "Trace contains backedge");
+    }
+  }
+#endif
+}
 
 MachineTraceMetrics::Trace
 MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) {
diff --git a/lib/CodeGen/MachineTraceMetrics.h b/lib/CodeGen/MachineTraceMetrics.h
index 40da272..fa4970a 100644
--- a/lib/CodeGen/MachineTraceMetrics.h
+++ b/lib/CodeGen/MachineTraceMetrics.h
@@ -61,6 +61,7 @@
 class raw_ostream;
 
 class MachineTraceMetrics : public MachineFunctionPass {
+  const MachineFunction *MF;
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
   const MachineRegisterInfo *MRI;
@@ -178,7 +179,7 @@
     virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0;
     virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0;
     explicit Ensemble(MachineTraceMetrics*);
-    MachineLoop *getLoopFor(const MachineBasicBlock*);
+    const MachineLoop *getLoopFor(const MachineBasicBlock*) const;
     const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const;
     const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const;
 
@@ -187,6 +188,7 @@
     virtual const char *getName() const =0;
     void print(raw_ostream&) const;
     void invalidate(const MachineBasicBlock *MBB);
+    void verify() const;
 
     /// Get the trace that passes through MBB.
     /// The trace is computed on demand.
@@ -210,6 +212,10 @@
   /// is erased, or the CFG is otherwise changed.
   void invalidate(const MachineBasicBlock *MBB);
 
+  /// Verify the internal consistency of cached data.
+  /// This does nothing in NDEBUG builds.
+  void verify() const;
+
 private:
   // One entry per basic block, indexed by block number.
   SmallVector<FixedBlockInfo, 4> BlockInfo;