Index: lib/Transforms/Utils/BreakCriticalEdges.cpp
===================================================================
--- lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -161,6 +161,13 @@
   BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
   NewBI->setDebugLoc(TI->getDebugLoc());
 
+  // Reset the llvm.loop metadata (if present) and adjust it later if LoopInfo
+  // is available. This ensures that neither branch carries falsified
+  // llvm.loop metadata.
+  MDNode *LoopMD = TI->getMetadata("llvm.loop");
+  if (LoopMD)
+    TI->setMetadata("llvm.loop", nullptr);
+
   // Branch to the new block, breaking the edge.
   TI->setSuccessor(SuccNum, NewBB);
 
@@ -350,6 +357,44 @@
               P->mustPreserveAnalysisID(LoopSimplifyID)) &&
              "SplitCriticalEdge doesn't know how to update LCCSA form "
              "without LoopSimplify!");
+
+      // We removed llvm.loop metadata earlier as we do not know if it is still
+      // valid for the old and new branch respectively. If it was present at the
+      // original (old) branch we check if the new branch should carry it from
+      // now on or if we should reattach it to the old branch. In either case we
+      // will check if any remaining successor of the old branch is a loop
+      // loop header. Afterwards, we check if the new branch destination block
+      // is a loop header. Possible outcomes:
+      //  1) The old branch but not the new branch may jump to a loop header.
+      //     ==> We reattach the loop ID to the old branch.
+      //  2) The new branch but not the old branch may jump to a loop header.
+      //     ==> We attach the loop ID to the new branch.
+      //  3) Both branches (new and old) may jump to a loop header.
+      //     ==> We won't attach the loop ID to either one as we cannot
+      //         guarantee which one it was for. Other annotations (e.g.,
+      //         llvm.mem.parallel_loop_access) could be invalid if we choose
+      //         the wrong one.
+      //  4) Neither branch may jump to a loop header.
+      //     ==> We won't attach the loop ID since it was invalid before.
+      if (LoopMD) {
+        bool NewBrJumpsToHeader = LI->isLoopHeader(DestBB);
+        bool OldBrJumpsToHeader = false;
+        for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
+          BasicBlock *SuccBB = TI->getSuccessor(i);
+          if (SuccBB == DestBB || !LI->isLoopHeader(SuccBB))
+            continue;
+          OldBrJumpsToHeader = true;
+          break;
+        }
+
+        // Case 1)
+        if (OldBrJumpsToHeader && !NewBrJumpsToHeader)
+          TI->setMetadata("llvm.loop", LoopMD);
+        // Case 2)
+        if (NewBrJumpsToHeader && !OldBrJumpsToHeader)
+          NewBI->setMetadata("llvm.loop", LoopMD);
+        // Case 3) and 4) are noops.
+      }
     }
   }
 
Index: test/Transforms/Util/break-critical-edges-loop-metadata.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/break-critical-edges-loop-metadata.ll
@@ -0,0 +1,34 @@
+; Run LoopInfo before BreakCriticalEdges and use LoopSimplify as a real user of
+; LoopInfo to ensure the pass survives.
+; RUN: opt < %s -loops -break-crit-edges -loop-simplify -S | FileCheck %s
+
+; Check that the new loop backedge (after we split critical edges)
+; will carry the same llvm.loop annotation as the old (critical) backedge.
+
+define void @jd(i1 %b, i32* nocapture %A) {
+entry:
+  br i1 %b, label %loop.exit, label %loop.header
+
+loop.header:                             ; preds = %loop.header, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %loop.header ]
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvar
+  %tmp = trunc i64 %indvar to i32
+  store i32 %tmp, i32* %arrayidx, align 4
+  %indvar.next = add nsw i64 %indvar, 1
+  %exitcond = icmp eq i64 %indvar.next, 512
+
+; This is a critical edge for both destination blocks, thus critical edge
+; splitting will create two new blocks one to jump to %inner.loop.header
+; and one to jump to %loop.exit. We verify only the former keeps the
+; loop ID annotation.
+
+  br i1 %exitcond, label %loop.exit, label %loop.header, !llvm.loop !0
+; CHECK:     br label %loop.header, !llvm.loop !0
+; CHECK-NOT: br label %loop.exit, !llvm.loop
+
+loop.exit:                                  ; preds = %loop.header
+  ret void
+
+}
+
+!0 = metadata !{metadata !0}
Index: test/Transforms/Util/break-critical-edges-loops-metadata.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/break-critical-edges-loops-metadata.ll
@@ -0,0 +1,43 @@
+; Run LoopInfo before BreakCriticalEdges and use LoopSimplify as a real user of
+; LoopInfo to ensure the pass survives.
+; RUN: opt < %s -loops -break-crit-edges -loop-simplify -S | FileCheck %s
+
+; Check that the new loop backedges (after we split critical edges)
+; will carry the same llvm.loop annotation as the old (critical) backedges.
+
+define void @jd(i32* nocapture %A) {
+entry:
+  br label %outer.loop.header
+
+outer.loop.header:                            ; preds = %loop_exit3, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar_next, %loop_exit3 ]
+  %p_tmp7 = shl i64 %indvar, 9
+  br label %inner.loop.header
+
+inner.loop.header:                             ; preds = %inner.loop.header, %outer.loop.header
+  %indvar4 = phi i64 [ 0, %outer.loop.header ], [ %indvar_next5, %inner.loop.header ]
+  %p_tmp = add nsw i64 %indvar4, %indvar
+  %p_tmp8 = add nsw i64 %indvar4, %p_tmp7
+  %p_arrayidx = getelementptr inbounds i32* %A, i64 %p_tmp8
+  %p_tmp9 = trunc i64 %p_tmp to i32
+  store i32 %p_tmp9, i32* %p_arrayidx, align 4
+  %indvar_next5 = add nsw i64 %indvar4, 1
+  %exitcond = icmp eq i64 %indvar_next5, 512
+; This is a critical edge.
+  br i1 %exitcond, label %loop_exit3, label %inner.loop.header, !llvm.loop !0
+; CHECK: br label %inner.loop.header, !llvm.loop !0
+
+loop_exit3:                                 ; preds = %inner.loop.header
+  %indvar_next = add nsw i64 %indvar, 1
+  %exitcond1 = icmp eq i64 %indvar_next, 1024
+; This is a critical edge.
+  br i1 %exitcond1, label %loop_exit, label %outer.loop.header, !llvm.loop !1
+; CHECK: br label %outer.loop.header, !llvm.loop !1
+
+loop_exit:                                  ; preds = %loop_exit3
+  ret void
+
+}
+
+!0 = metadata !{metadata !0}
+!1 = metadata !{metadata !1}
Index: test/Transforms/Util/break-critical-edges-loops-same-latch-metadata.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/break-critical-edges-loops-same-latch-metadata.ll
@@ -0,0 +1,43 @@
+; Run LoopInfo before BreakCriticalEdges and use LoopSimplify as a real user of
+; LoopInfo to ensure the pass survives.
+; RUN: opt < %s -loops -break-crit-edges -loop-simplify -S | FileCheck %s
+
+; Here the critical backedge is the backedge of two nested loops. We ensure at
+; none will keep the loop ID annotation as it might be invalid for either one
+; of them.
+
+define void @jd(i32* nocapture %A) {
+entry:
+  br label %outer.loop.header
+
+outer.loop.header:                            ; preds = %inner.loop.header, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar_next, %inner.loop.header ]
+  %p_tmp7 = shl i64 %indvar, 9
+  %indvar_next = add nsw i64 %indvar, 1
+  %exitcond1 = icmp eq i64 %indvar_next, 1024
+  br i1 %exitcond1, label %loop_exit, label %inner.loop.header
+
+inner.loop.header:                             ; preds = %inner.loop.header, %outer.loop.header
+  %indvar4 = phi i64 [ 0, %outer.loop.header ], [ %indvar_next5, %inner.loop.header ]
+  %p_tmp = add nsw i64 %indvar4, %indvar
+  %p_tmp8 = add nsw i64 %indvar4, %p_tmp7
+  %p_arrayidx = getelementptr inbounds i32* %A, i64 %p_tmp8
+  %p_tmp9 = trunc i64 %p_tmp to i32
+  store i32 %p_tmp9, i32* %p_arrayidx, align 4
+  %indvar_next5 = add nsw i64 %indvar4, 1
+  %exitcond = icmp eq i64 %indvar_next5, 512
+
+; This is a critical edge and a backedge for both the inner as well as the
+; outer loop. As we cannot know for which it was initialy placed we remove
+; it and ensure other annotations (e.g., llvm.mem.parallel_loop_access) are
+; not invalidated by the splitting.
+
+; CHECK-NOT: !llvm.loop
+  br i1 %exitcond, label %outer.loop.header, label %inner.loop.header, !llvm.loop !0
+
+loop_exit:                                  ; preds = %loop_exit3
+  ret void
+
+}
+
+!0 = metadata !{metadata !0}
Index: test/Transforms/Util/break-critical-edges-no-loop-info-but-loop-id-metadata.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/break-critical-edges-no-loop-info-but-loop-id-metadata.ll
@@ -0,0 +1,30 @@
+; Run only BreakCriticalEdges without LoopInfo.
+; RUN: opt < %s -break-crit-edges -S | FileCheck %s
+
+; Check that the new loop backedge (after we split critical edges)
+; won't carry llvm.loop annotation as the old (critical) backedge.
+; This is a safety meassure since we cannot know (without LoopInfo)
+; which branch, the new one inserted by splitting the edge, or the
+; old one is a loop backedge now.
+
+define void @jd(i1 %b, i32* nocapture %A) {
+entry:
+  br i1 %b, label %loop_exit, label %loop.header
+
+loop.header:                             ; preds = %loop.header, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar_next, %loop.header ]
+  %p_arrayidx = getelementptr inbounds i32* %A, i64 %indvar
+  %p_tmp9 = trunc i64 %indvar to i32
+  store i32 %p_tmp9, i32* %p_arrayidx, align 4
+  %indvar_next = add nsw i64 %indvar, 1
+  %exitcond = icmp eq i64 %indvar_next, 512
+; This is a critical edge.
+  br i1 %exitcond, label %loop_exit, label %loop.header, !llvm.loop !0
+; CHECK-NOT:!llvm.loop
+
+loop_exit:                                  ; preds = %loop.header
+  ret void
+
+}
+
+!0 = metadata !{metadata !0}
Index: test/Transforms/Util/break-critical-edges-non-loop-backedge-but-llvm-loop-metadata.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/break-critical-edges-non-loop-backedge-but-llvm-loop-metadata.ll
@@ -0,0 +1,27 @@
+; Run LoopInfo before BreakCriticalEdges and use LoopSimplify as a real user of
+; LoopInfo to ensure the pass survives.
+; RUN: opt < %s -loops -break-crit-edges -loop-simplify -S | FileCheck %s
+
+; Here the llvm.loop annotation is invalid in the beginning as the branch is
+; not a backedge of any loop.
+
+define void @jd(i1 %b0, i1 %b1, i32* nocapture %A) {
+block1:
+; This edge is critical but not a loop backedge.
+  br i1 %b0, label %exit1, label %block2
+
+block2:                             ; preds = %block1
+; This edge is critical but not a loop backedge. The annotation is already
+; invalid and BreakCriticalEdges should therefor remove it.
+  br i1 %b1, label %exit1, label %exit2, !llvm.loop !0
+
+exit1:                                  ; preds = %block1, %block2
+  ret void
+
+exit2:                                  ; preds = %block2
+  ret void
+}
+
+!0 = metadata !{metadata !0}
+
+; CHECK-NOT: !llvm.loop