Index: lib/Transforms/Utils/MemorySSA.cpp
===================================================================
--- lib/Transforms/Utils/MemorySSA.cpp
+++ lib/Transforms/Utils/MemorySSA.cpp
@@ -249,26 +249,74 @@
   // could just look up the memory access for every possible instruction in the
   // stream.
   SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
-
+  SmallPtrSet<BasicBlock *, 32> DefUseBlocks;
   // Go through each block, figure out where defs occur, and chain together all
   // the accesses.
   for (BasicBlock &B : F) {
+    bool InsertIntoDefUse = false;
+    bool InsertIntoDef = false;
     AccessListType *Accesses = nullptr;
     for (Instruction &I : B) {
       MemoryAccess *MA = createNewAccess(&I, true);
       if (!MA)
         continue;
       if (isa<MemoryDef>(MA))
-        DefiningBlocks.insert(&B);
+        InsertIntoDef = true;
+      else if (isa<MemoryUse>(MA))
+        InsertIntoDefUse = true;
+
       if (!Accesses)
         Accesses = getOrCreateAccessList(&B);
       Accesses->push_back(MA);
     }
+    if (InsertIntoDef)
+      DefiningBlocks.insert(&B);
+    if (InsertIntoDefUse)
+      DefUseBlocks.insert(&B);
+  }
+
+  // Compute live-in.
+  // Live in is normally defined as "all the blocks on the path from each def to
+  // each of it's uses".
+  // MemoryDef's are implicit uses of previous state, so they are also uses.
+  // This means we don't really have def-only instructions.  The only
+  // MemoryDef's that are not really uses are those that are of the LiveOnEntry
+  // variable (because LiveOnEntry can reach anywhere, and every def is a
+  // must-kill of LiveOnEntry).
+  // In theory, you could precisely compute live-in by using alias-analysis to
+  // disambiguate defs and uses to see which really pair up with which.
+  // In practice, this would be really expensive and difficult. So we simply
+  // assume all defs are also uses that need to be kept live.
+  // Because of this, the end result of this live-in computation will be "the
+  // entire set of basic blocks that reach any use".
+
+  SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
+  SmallVector<BasicBlock *, 64> LiveInBlockWorklist(DefUseBlocks.begin(),
+                                                    DefUseBlocks.end());
+  // Now that we have a set of blocks where a value is live-in, recursively add
+  // predecessors until we find the full region the value is live.
+  while (!LiveInBlockWorklist.empty()) {
+    BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
+
+    // The block really is live in here, insert it into the set.  If already in
+    // the set, then it has already been processed.
+    if (!LiveInBlocks.insert(BB).second)
+      continue;
+
+    // Since the value is live into BB, it is either defined in a predecessor or
+    // live into it to.
+    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+      BasicBlock *P = *PI;
+
+      // Otherwise it is, add to the worklist.
+      LiveInBlockWorklist.push_back(P);
+    }
   }
 
   // Determine where our MemoryPhi's should go
   IDFCalculator IDFs(*DT);
   IDFs.setDefiningBlocks(DefiningBlocks);
+  IDFs.setLiveInBlocks(LiveInBlocks);
   SmallVector<BasicBlock *, 32> IDFBlocks;
   IDFs.calculate(IDFBlocks);
 
Index: test/Transforms/Util/MemorySSA/livein.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/MemorySSA/livein.ll
@@ -0,0 +1,29 @@
+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+define void @F(i8*) {
+  br i1 true, label %left, label %right
+left:
+; CHECK: 1 = MemoryDef(liveOnEntry)
+  store i8 16, i8* %0
+  br label %merge
+right:
+  br label %merge
+
+merge:
+; CHECK-NOT: 2 = MemoryPhi
+ret void 
+}
+
+define void @F2(i8*) {
+  br i1 true, label %left, label %right
+left:
+; CHECK: 1 = MemoryDef(liveOnEntry)
+  store i8 16, i8* %0
+  br label %merge
+right:
+  br label %merge
+
+merge:
+;CHECK: 2 = MemoryPhi({left,1},{right,liveOnEntry})
+%c = load i8, i8* %0
+ret void 
+}