--- a/js/src/jit/Ion.cpp
+++ b/js/src/jit/Ion.cpp
@@ -1472,16 +1472,20 @@ OptimizeMIR(MIRGenerator *mir)
             return false;
     }
 
     if (graph.entryBlock()->info().executionMode() == ParallelExecution) {
         AutoTraceLog log(logger, TraceLogger::ParallelSafetyAnalysis);
         ParallelSafetyAnalysis analysis(mir, graph);
         if (!analysis.analyze())
             return false;
+        IonSpewPass("Parallel Safety Analysis");
+        AssertExtendedGraphCoherency(graph);
+        if (mir->shouldCancel("Parallel Safety Analysis"))
+            return false;
     }
 
     // Alias analysis is required for LICM and GVN so that we don't move
     // loads across stores.
     if (mir->optimizationInfo().licmEnabled() ||
         mir->optimizationInfo().gvnEnabled())
     {
         AutoTraceLog log(logger, TraceLogger::AliasAnalysis);

--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -1736,26 +1736,36 @@ CheckPredecessorImpliesSuccessor(MBasicB
             return true;
     }
     return false;
 }
 
 static bool
 CheckOperandImpliesUse(MNode *n, MDefinition *operand)
 {
+    // TODO: Fix code that leaves discarded things in resume point operands
+    // (bug 1055690).
+    MOZ_ASSERT_IF(!n->isResumePoint(), !operand->isDiscarded());
+    MOZ_ASSERT(operand->block() != nullptr);
+
     for (MUseIterator i = operand->usesBegin(); i != operand->usesEnd(); i++) {
         if (i->consumer() == n)
             return true;
     }
     return false;
 }
 
 static bool
 CheckUseImpliesOperand(MDefinition *def, MUse *use)
 {
+    MOZ_ASSERT(!use->consumer()->block()->isDead());
+    MOZ_ASSERT_IF(use->consumer()->isDefinition(),
+                  !use->consumer()->toDefinition()->isDiscarded());
+    MOZ_ASSERT(use->consumer()->block() != nullptr);
+
     return use->consumer()->getOperand(use->index()) == def;
 }
 #endif // DEBUG
 
 void
 jit::AssertBasicGraphCoherency(MIRGraph &graph)
 {
 #ifdef DEBUG
@@ -1774,16 +1784,19 @@ jit::AssertBasicGraphCoherency(MIRGraph 
         JS_ASSERT(resumePoint->block() == graph.entryBlock());
 
     // Assert successor and predecessor list coherency.
     uint32_t count = 0;
     for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
         count++;
 
         JS_ASSERT(&block->graph() == &graph);
+        MOZ_ASSERT(!block->isDead());
+        MOZ_ASSERT_IF(block->outerResumePoint() != nullptr,
+                      block->entryResumePoint() != nullptr);
 
         for (size_t i = 0; i < block->numSuccessors(); i++)
             JS_ASSERT(CheckSuccessorImpliesPredecessor(*block, block->getSuccessor(i)));
 
         for (size_t i = 0; i < block->numPredecessors(); i++)
             JS_ASSERT(CheckPredecessorImpliesSuccessor(*block, block->getPredecessor(i)));
 
         if (block->entryResumePoint()) {
@@ -1802,36 +1815,56 @@ jit::AssertBasicGraphCoherency(MIRGraph 
             for (uint32_t i = 0, e = iter->numOperands(); i < e; i++) {
                 MOZ_ASSERT(iter->getUseFor(i)->hasProducer());
                 MOZ_ASSERT(CheckOperandImpliesUse(*iter, iter->getOperand(i)));
             }
         }
         for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
             JS_ASSERT(phi->numOperands() == block->numPredecessors());
             MOZ_ASSERT(!phi->isRecoveredOnBailout());
+            MOZ_ASSERT(phi->type() != MIRType_None);
         }
         for (MDefinitionIterator iter(*block); iter; iter++) {
             JS_ASSERT(iter->block() == *block);
+            MOZ_ASSERT_IF(iter->hasUses(), iter->type() != MIRType_None);
+            MOZ_ASSERT(!iter->isDiscarded());
+            MOZ_ASSERT_IF(iter->isStart(),
+                          *block == graph.entryBlock() || *block == graph.osrBlock());
+            MOZ_ASSERT_IF(iter->isParameter(),
+                          *block == graph.entryBlock() || *block == graph.osrBlock());
+            MOZ_ASSERT_IF(iter->isOsrEntry(), *block == graph.osrBlock());
+            MOZ_ASSERT_IF(iter->isOsrValue(), *block == graph.osrBlock());
 
             // Assert that use chains are valid for this instruction.
             for (uint32_t i = 0, end = iter->numOperands(); i < end; i++)
                 JS_ASSERT(CheckOperandImpliesUse(*iter, iter->getOperand(i)));
             for (MUseIterator use(iter->usesBegin()); use != iter->usesEnd(); use++)
                 JS_ASSERT(CheckUseImpliesOperand(*iter, *use));
 
             if (iter->isInstruction()) {
                 if (MResumePoint *resume = iter->toInstruction()->resumePoint()) {
                     MOZ_ASSERT(resume->instruction() == *iter);
                     MOZ_ASSERT(resume->block() == *block);
+                    MOZ_ASSERT(resume->block()->entryResumePoint() != nullptr);
                 }
             }
 
             if (iter->isRecoveredOnBailout())
                 MOZ_ASSERT(!iter->hasLiveDefUses());
         }
+
+        MControlInstruction *control = block->lastIns();
+        MOZ_ASSERT(control->block() == *block);
+        MOZ_ASSERT(!control->hasUses());
+        MOZ_ASSERT(control->type() == MIRType_None);
+        MOZ_ASSERT(!control->isDiscarded());
+        MOZ_ASSERT(!control->isRecoveredOnBailout());
+        MOZ_ASSERT(control->resumePoint() == nullptr);
+        for (uint32_t i = 0, end = control->numOperands(); i < end; ++i)
+            MOZ_ASSERT(CheckOperandImpliesUse(control, control->getOperand(i)));
     }
 
     JS_ASSERT(graph.numBlocks() == count);
 #endif
 }
 
 #ifdef DEBUG
 static void
@@ -1925,18 +1958,21 @@ jit::AssertExtendedGraphCoherency(MIRGra
 {
     // Checks the basic GraphCoherency but also other conditions that
     // do not hold immediately (such as the fact that critical edges
     // are split)
 
 #ifdef DEBUG
     if (!js_JitOptions.checkGraphConsistency)
         return;
+
     AssertGraphCoherency(graph);
 
+    AssertDominatorTree(graph);
+
     uint32_t idx = 0;
     for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
         JS_ASSERT(block->id() == idx++);
 
         // No critical edges:
         if (block->numSuccessors() > 1)
             for (size_t i = 0; i < block->numSuccessors(); i++)
                 JS_ASSERT(block->getSuccessor(i)->numPredecessors() == 1);
@@ -1959,19 +1995,55 @@ jit::AssertExtendedGraphCoherency(MIRGra
 
         uint32_t successorWithPhis = 0;
         for (size_t i = 0; i < block->numSuccessors(); i++)
             if (!block->getSuccessor(i)->phisEmpty())
                 successorWithPhis++;
 
         JS_ASSERT(successorWithPhis <= 1);
         JS_ASSERT((successorWithPhis != 0) == (block->successorWithPhis() != nullptr));
+
+        // Verify that phi operands dominate the corresponding CFG predecessor
+        // edges.
+        for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd()); iter != end; ++iter) {
+            MPhi *phi = *iter;
+            for (size_t i = 0, e = phi->numOperands(); i < e; ++i) {
+                // We sometimes see a phi with a magic-optimized-arguments
+                // operand defined in the normal entry block, while the phi is
+                // also reachable from the OSR entry (auto-regress/bug779818.js)
+                if (phi->getOperand(i)->type() == MIRType_MagicOptimizedArguments)
+                    continue;
+
+                MOZ_ASSERT(phi->getOperand(i)->block()->dominates(block->getPredecessor(i)),
+                           "Phi input is not dominated by its operand");
+            }
+        }
+
+        // Verify that instructions are dominated by their operands.
+        for (MInstructionIterator iter(block->begin()), end(block->end()); iter != end; ++iter) {
+            MInstruction *ins = *iter;
+            for (size_t i = 0, e = ins->numOperands(); i < e; ++i) {
+                MDefinition *op = ins->getOperand(i);
+                MBasicBlock *opBlock = op->block();
+                MOZ_ASSERT(opBlock->dominates(*block),
+                           "Instruction is not dominated by its operands");
+
+                // If the operand is an instruction in the same block, check
+                // that it comes first.
+                if (opBlock == *block && !op->isPhi()) {
+                    MInstructionIterator opIter = block->begin(op->toInstruction());
+                    do {
+                        ++opIter;
+                        MOZ_ASSERT(opIter != block->end(),
+                                   "Operand in same block as instruction does not precede");
+                    } while (*opIter != ins);
+                }
+            }
+        }
     }
-
-    AssertDominatorTree(graph);
 #endif
 }
 
 
 struct BoundsCheckInfo
 {
     MBoundsCheck *check;
     uint32_t validEnd;

--- a/js/src/jit/MIRGraph.cpp
+++ b/js/src/jit/MIRGraph.cpp
@@ -972,16 +972,17 @@ MBasicBlock::addPhi(MPhi *phi)
 }
 
 MPhiIterator
 MBasicBlock::discardPhiAt(MPhiIterator &at)
 {
     JS_ASSERT(!phis_.empty());
 
     at->removeAllOperands();
+    at->setDiscarded();
 
     MPhiIterator result = phis_.removeAt(at);
 
     if (phis_.empty()) {
         for (MBasicBlock **pred = predecessors_.begin(); pred != predecessors_.end(); pred++)
             (*pred)->setSuccessorWithPhis(nullptr, 0);
     }
     return result;

--- a/js/src/jit/MIRGraph.h
+++ b/js/src/jit/MIRGraph.h
@@ -293,16 +293,17 @@ class MBasicBlock : public TempObject, p
     // all operands are already discarded.
     void discardIgnoreOperands(MInstruction *ins);
 
     // Discards a phi instruction and updates predecessor successorWithPhis.
     MPhiIterator discardPhiAt(MPhiIterator &at);
 
     // Mark this block as having been removed from the graph.
     void markAsDead() {
+        MOZ_ASSERT(kind_ != DEAD);
         kind_ = DEAD;
     }
 
     ///////////////////////////////////////////////////////
     /////////// END GRAPH BUILDING INSTRUCTIONS ///////////
     ///////////////////////////////////////////////////////
 
     MIRGraph &graph() {
@@ -537,16 +538,17 @@ class MBasicBlock : public TempObject, p
         JS_ASSERT(!lir_);
         lir_ = lir;
     }
 
     MBasicBlock *successorWithPhis() const {
         return successorWithPhis_;
     }
     uint32_t positionInPhiSuccessor() const {
+        MOZ_ASSERT(successorWithPhis());
         return positionInPhiSuccessor_;
     }
     void setSuccessorWithPhis(MBasicBlock *successor, uint32_t id) {
         successorWithPhis_ = successor;
         positionInPhiSuccessor_ = id;
     }
     size_t numSuccessors() const;
     MBasicBlock *getSuccessor(size_t index) const;

--- a/js/src/jit/ValueNumbering.cpp
+++ b/js/src/jit/ValueNumbering.cpp
@@ -50,17 +50,19 @@ ValueNumberer::VisibleValues::ValueHashe
 bool
 ValueNumberer::VisibleValues::ValueHasher::match(Key k, Lookup l)
 {
     // If one of the instructions depends on a store, and the other instruction
     // does not depend on the same store, the instructions are not congruent.
     if (k->dependency() != l->dependency())
         return false;
 
-    return k->congruentTo(l); // Ask the values themselves what they think.
+    bool congruent = k->congruentTo(l); // Ask the values themselves what they think.
+    MOZ_ASSERT(congruent == l->congruentTo(k), "congruentTo relation is not symmetric");
+    return congruent;
 }
 
 void
 ValueNumberer::VisibleValues::ValueHasher::rekey(Key &k, Key newKey)
 {
     k = newKey;
 }