am 31675153: Merge branch \'upstream\' into merge_2

* commit '31675153bd2d7617db8cb6aeb58054934c7b9f73': (542 commits)
  MaximumSpanningTree::EdgeWeightCompare: Make this comparator actually be a strict weak ordering, and don't pass possibly-null pointers to dyn_cast.
  Fix misaligned access in MachO object file reader: despite containing an int64_t, Symbol64TableEntry is actually only stored with 4-byte alignment within the file.
  Fix unaligned memory accesses when performing relocations in X86 JIT. There's no cost to using memcpy here: the fixed code is optimized by LLVM to perfect machine code.
  Don't pass a null pointer to cast<> in its unit tests.
  Don't bind a reference to a dereferenced null pointer (for return value of WeakVH::operator*).
  [ms-inline asm] Do not report a Parser error when matching inline assembly.
  Ignore the documentation-suggested location for compile_commands.json
  The presence of the empty file "foo" unfortunately does not improve LLVM in any way.
  Remove unnecessary cast that was also unnecessarily casting away constness.
  Provide a portability macro for __builtin_trap.
  Fix macros arguments with an underscore, dot or dollar in them. This is based on a patch by Andy/PaX. I added the support for dot and dollar.
  [ms-inline asm] Expose the ErrorInfo from the MatchInstructionImpl.  In general, this is the index of the operand that failed to match.
  Formatting.  No functional change.
  Make the wording in of the "expected identifier" error in the .macro directive consistent with the other "expected identifier" errors. Extracted from the Andy/PaX patch. I added the test.
  Pacify PVS-Studio by changing the type rather than doing a cast, a tweak suggested by David Blaikie.
  Add support for the --param ssp-buffer-size= driver option. PR9673
  Use typedefs. Fix indentation. Extracted from the Andy/PaX patch.
  Remove unused variable. Extracted from the Andy/PaX patch.
  Fix typo. Extracted from the Andy/PaX patch.
  MCJIT: Tidy up the constructor.
  ...

1 files changed, 63 insertions, 27 deletions

diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 219e631..77b2403 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -39,6 +39,19 @@ static cl::opt<bool,true>
 VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
                cl::desc("Verify dominator info (time consuming)"));
 
+bool BasicBlockEdge::isSingleEdge() const {
+  const TerminatorInst *TI = Start->getTerminator();
+  unsigned NumEdgesToEnd = 0;
+  for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
+    if (TI->getSuccessor(i) == End)
+      ++NumEdgesToEnd;
+    if (NumEdgesToEnd >= 2)
+      return false;
+  }
+  assert(NumEdgesToEnd == 1);
+  return true;
+}
+
 //===----------------------------------------------------------------------===//
 //  DominatorTree Implementation
 //===----------------------------------------------------------------------===//
@@ -142,12 +155,27 @@ bool DominatorTree::dominates(const Instruction *Def,
   // Invoke results are only usable in the normal destination, not in the
   // exceptional destination.
   BasicBlock *NormalDest = II->getNormalDest();
-  if (!dominates(NormalDest, UseBB))
+  BasicBlockEdge E(DefBB, NormalDest);
+  return dominates(E, UseBB);
+}
+
+bool DominatorTree::dominates(const BasicBlockEdge &BBE,
+                              const BasicBlock *UseBB) const {
+  // Assert that we have a single edge. We could handle them by simply
+  // returning false, but since isSingleEdge is linear on the number of
+  // edges, the callers can normally handle them more efficiently.
+  assert(BBE.isSingleEdge());
+
+  // If the BB the edge ends in doesn't dominate the use BB, then the
+  // edge also doesn't.
+  const BasicBlock *Start = BBE.getStart();
+  const BasicBlock *End = BBE.getEnd();
+  if (!dominates(End, UseBB))
     return false;
 
-  // Simple case: if the normal destination has a single predecessor, the
-  // fact that it dominates the use block implies that we also do.
-  if (NormalDest->getSinglePredecessor())
+  // Simple case: if the end BB has a single predecessor, the fact that it
+  // dominates the use block implies that the edge also does.
+  if (End->getSinglePredecessor())
     return true;
 
   // The normal edge from the invoke is critical. Conceptually, what we would
@@ -170,29 +198,45 @@ bool DominatorTree::dominates(const Instruction *Def,
   // trivially dominates itself, so we only have to find if it dominates the
   // other predecessors. Since the only way out of X is via NormalDest, X can
   // only properly dominate a node if NormalDest dominates that node too.
-  for (pred_iterator PI = pred_begin(NormalDest),
-         E = pred_end(NormalDest); PI != E; ++PI) {
+  for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
+       PI != E; ++PI) {
     const BasicBlock *BB = *PI;
-    if (BB == DefBB)
+    if (BB == Start)
       continue;
 
-    if (!DT->isReachableFromEntry(BB))
-      continue;
-
-    if (!dominates(NormalDest, BB))
+    if (!dominates(End, BB))
       return false;
   }
   return true;
 }
 
-bool DominatorTree::dominates(const Instruction *Def,
+bool DominatorTree::dominates(const BasicBlockEdge &BBE,
                               const Use &U) const {
-  Instruction *UserInst = dyn_cast<Instruction>(U.getUser());
+  // Assert that we have a single edge. We could handle them by simply
+  // returning false, but since isSingleEdge is linear on the number of
+  // edges, the callers can normally handle them more efficiently.
+  assert(BBE.isSingleEdge());
+
+  Instruction *UserInst = cast<Instruction>(U.getUser());
+  // A PHI in the end of the edge is dominated by it.
+  PHINode *PN = dyn_cast<PHINode>(UserInst);
+  if (PN && PN->getParent() == BBE.getEnd() &&
+      PN->getIncomingBlock(U) == BBE.getStart())
+    return true;
 
-  // Instructions do not dominate non-instructions.
-  if (!UserInst)
-    return false;
+  // Otherwise use the edge-dominates-block query, which
+  // handles the crazy critical edge cases properly.
+  const BasicBlock *UseBB;
+  if (PN)
+    UseBB = PN->getIncomingBlock(U);
+  else
+    UseBB = UserInst->getParent();
+  return dominates(BBE, UseBB);
+}
 
+bool DominatorTree::dominates(const Instruction *Def,
+                              const Use &U) const {
+  Instruction *UserInst = cast<Instruction>(U.getUser());
   const BasicBlock *DefBB = Def->getParent();
 
   // Determine the block in which the use happens. PHI nodes use
@@ -218,17 +262,9 @@ bool DominatorTree::dominates(const Instruction *Def,
   // their own block, except possibly a phi, so we don't need to
   // walk the block in any case.
   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
-    // A PHI in the normal successor using the invoke's return value is
-    // dominated by the invoke's return value.
-    if (isa<PHINode>(UserInst) &&
-        UserInst->getParent() == II->getNormalDest() &&
-        cast<PHINode>(UserInst)->getIncomingBlock(U) == DefBB)
-      return true;
-
-    // Otherwise use the instruction-dominates-block query, which
-    // handles the crazy case of an invoke with a critical edge
-    // properly.
-    return dominates(Def, UseBB);
+    BasicBlock *NormalDest = II->getNormalDest();
+    BasicBlockEdge E(DefBB, NormalDest);
+    return dominates(E, U);
   }
 
   // If the def and use are in different blocks, do a simple CFG dominator