diff --git a/llvm/include/llvm/Analysis/CFGPrinter.h b/llvm/include/llvm/Analysis/CFGPrinter.h
--- a/llvm/include/llvm/Analysis/CFGPrinter.h
+++ b/llvm/include/llvm/Analysis/CFGPrinter.h
@@ -153,6 +153,8 @@
   if (OutStr[0] == '%') {
     OutStr.erase(OutStr.begin());
   }
+  // Place | after BB name to separate it into header
+  OutStr.insert(OutStr.find_first_of('\n') + 1, "\\|");
 
   unsigned ColNum = 0;
   unsigned LastSpace = 0;
@@ -178,8 +180,6 @@
     if (OutStr[i] == ' ')
       LastSpace = i;
   }
-  // Replace \l after BB name with | to separate it into header
-  OutStr.replace(OutStr.find_first_of('\\') + 1, 1, "|");
   return OutStr;
 }
 
diff --git a/llvm/test/Analysis/DotMachineCFG/AMDGPU/functions.mir b/llvm/test/Analysis/DotMachineCFG/AMDGPU/functions.mir
--- a/llvm/test/Analysis/DotMachineCFG/AMDGPU/functions.mir
+++ b/llvm/test/Analysis/DotMachineCFG/AMDGPU/functions.mir
@@ -12,7 +12,7 @@
 
 # MCFG: digraph "Machine CFG for 'func2' function"
 # MCFG-NEXT: label="Machine CFG for 'func2' function"
-# MCFG: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.0:| $sgpr0 = S_LOAD_DWORD_IMM $sgpr12_sgpr13, 0, 0\l $sgpr1 = S_LOAD_DWORD_IMM $sgpr6_sgpr7, 0, 0\l $sgpr2 = S_LOAD_DWORD_IMM $sgpr14_sgpr15, 0, 0\l S_ENDPGM 0\l}"];
+# MCFG: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.0:\l| $sgpr0 = S_LOAD_DWORD_IMM $sgpr12_sgpr13, 0, 0\l $sgpr1 = S_LOAD_DWORD_IMM $sgpr6_sgpr7, 0, 0\l $sgpr2 = S_LOAD_DWORD_IMM $sgpr14_sgpr15, 0, 0\l S_ENDPGM 0\l}"];
 ---
 name: func2
 body: |
diff --git a/llvm/test/Analysis/DotMachineCFG/AMDGPU/irreducible.mir b/llvm/test/Analysis/DotMachineCFG/AMDGPU/irreducible.mir
--- a/llvm/test/Analysis/DotMachineCFG/AMDGPU/irreducible.mir
+++ b/llvm/test/Analysis/DotMachineCFG/AMDGPU/irreducible.mir
@@ -5,22 +5,22 @@
 
 # MCFG: digraph "Machine CFG for 'irreducible' function"
 # MCFG-NEXT: label="Machine CFG for 'irreducible' function"
-# MCFG: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.0:| successors: %bb.1(0x40000000), %bb.2(0x40000000)\l  liveins: $vgpr0, $vgpr1, $vgpr2, $sgpr4_sgpr5, $sgpr6_sgpr7, $sgpr8_sgpr9,\l... $sgpr10_sgpr11, $sgpr14, $sgpr15, $sgpr16\l  %0:sreg_32 = IMPLICIT_DEF\l  %1:vgpr_32 = COPY $vgpr0\l  %2:vgpr_32 = V_MOV_B32_e32 0, implicit $exec\l  S_CMP_EQ_U32 %0:sreg_32, 0, implicit-def $scc\l  S_CBRANCH_SCC1 %bb.1, implicit $scc\l  S_BRANCH %bb.2\l}"];
+# MCFG: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.0:\l| successors: %bb.1(0x40000000), %bb.2(0x40000000)\l  liveins: $vgpr0, $vgpr1, $vgpr2, $sgpr4_sgpr5, $sgpr6_sgpr7, $sgpr8_sgpr9,\l... $sgpr10_sgpr11, $sgpr14, $sgpr15, $sgpr16\l  %0:sreg_32 = IMPLICIT_DEF\l  %1:vgpr_32 = COPY $vgpr0\l  %2:vgpr_32 = V_MOV_B32_e32 0, implicit $exec\l  S_CMP_EQ_U32 %0:sreg_32, 0, implicit-def $scc\l  S_CBRANCH_SCC1 %bb.1, implicit $scc\l  S_BRANCH %bb.2\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.1:|\l successors: %bb.3(0x80000000)\l\l  %3:vgpr_32 = PHI %2:vgpr_32, %bb.0, %4:vgpr_32, %bb.5\l  %5:vgpr_32 = V_ADD_U32_e64 %3:vgpr_32, 1, 0, implicit $exec\l  S_BRANCH %bb.3\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.1:\l|\l successors: %bb.3(0x80000000)\l\l  %3:vgpr_32 = PHI %2:vgpr_32, %bb.0, %4:vgpr_32, %bb.5\l  %5:vgpr_32 = V_ADD_U32_e64 %3:vgpr_32, 1, 0, implicit $exec\l  S_BRANCH %bb.3\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.2:|\l successors: %bb.3(0x80000000)\l\l  %6:vgpr_32 = PHI %2:vgpr_32, %bb.0, %4:vgpr_32, %bb.4\l  %7:vgpr_32 = V_ADD_U32_e64 %6:vgpr_32, 2, 0, implicit $exec\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.2:\l|\l successors: %bb.3(0x80000000)\l\l  %6:vgpr_32 = PHI %2:vgpr_32, %bb.0, %4:vgpr_32, %bb.4\l  %7:vgpr_32 = V_ADD_U32_e64 %6:vgpr_32, 2, 0, implicit $exec\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.3:|\l successors: %bb.4(0x80000000)\l\l  %4:vgpr_32 = PHI %5:vgpr_32, %bb.1, %7:vgpr_32, %bb.2\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.3:\l|\l successors: %bb.4(0x80000000)\l\l  %4:vgpr_32 = PHI %5:vgpr_32, %bb.1, %7:vgpr_32, %bb.2\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.4:|\l successors: %bb.2(0x40000000), %bb.5(0x40000000)\l\l  %8:vgpr_32 = V_AND_B32_e32 3, %1:vgpr_32, implicit $exec\l  %9:sreg_64 = V_CMP_EQ_U32_e64 %8:vgpr_32, 2, implicit $exec\l  %10:sreg_64 = SI_IF killed %9:sreg_64, %bb.2, implicit-def dead $exec,\l... implicit-def dead $scc, implicit $exec\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.4:\l|\l successors: %bb.2(0x40000000), %bb.5(0x40000000)\l\l  %8:vgpr_32 = V_AND_B32_e32 3, %1:vgpr_32, implicit $exec\l  %9:sreg_64 = V_CMP_EQ_U32_e64 %8:vgpr_32, 2, implicit $exec\l  %10:sreg_64 = SI_IF killed %9:sreg_64, %bb.2, implicit-def dead $exec,\l... implicit-def dead $scc, implicit $exec\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.5:|\l successors: %bb.1(0x40000000), %bb.6(0x40000000)\l\l  %11:sreg_64 = V_CMP_EQ_U32_e64 %8:vgpr_32, 1, implicit $exec\l  %12:sreg_64 = SI_IF killed %11:sreg_64, %bb.1, implicit-def dead $exec,\l... implicit-def dead $scc, implicit $exec\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.5:\l|\l successors: %bb.1(0x40000000), %bb.6(0x40000000)\l\l  %11:sreg_64 = V_CMP_EQ_U32_e64 %8:vgpr_32, 1, implicit $exec\l  %12:sreg_64 = SI_IF killed %11:sreg_64, %bb.1, implicit-def dead $exec,\l... implicit-def dead $scc, implicit $exec\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.6:|\l\l S_ENDPGM 0\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.6:\l|\l\l S_ENDPGM 0\l}"];
 
 # MCFG-ONLY: digraph "Machine CFG for 'irreducible' function"
 # MCFG-ONLY-NEXT: label="Machine CFG for 'irreducible' function"
diff --git a/llvm/test/Other/cfg-multiline-header.ll b/llvm/test/Other/cfg-multiline-header.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Other/cfg-multiline-header.ll
@@ -0,0 +1,16 @@
+; RUN: opt < %s -passes=dot-cfg -cfg-dot-filename-prefix=cfg 2>/dev/null > /dev/null
+; RUN: FileCheck %s -input-file=cfg.foo.dot --check-prefix=CHECK
+
+define void @foo(ptr %A, ptr %B) {
+a_very_long_label_that_should_take_over_eight_symbols_and_span_2_lines_in_cfg_dot_graph:
+; CHECK: label="{a_very_long_label_that_should_take_over_eight_symbols_and_span_2_lines_in_cfg_do\l...t_graph:\l|  store i32 1, ptr %A, align 4\l  store i32 2, ptr %B, align 4\l  br label %short_label\l}"
+  store i32 1, ptr %A
+  store i32 2, ptr %B
+  br label %short_label
+short_label:
+; CHECK: label="{short_label:\l|  br label\l... %an_even_longer_multiline_label_that_will_span_muliple_lines_Lorem_ipsum_dolor\l..._sit_amet_consectetur_adipiscing_elit_sed_do_eiusmod_tempor_incididunt_ut_labor\l...e_et_dolore_magna_aliqua\l}"
+  br label %an_even_longer_multiline_label_that_will_span_muliple_lines_Lorem_ipsum_dolor_sit_amet_consectetur_adipiscing_elit_sed_do_eiusmod_tempor_incididunt_ut_labore_et_dolore_magna_aliqua
+an_even_longer_multiline_label_that_will_span_muliple_lines_Lorem_ipsum_dolor_sit_amet_consectetur_adipiscing_elit_sed_do_eiusmod_tempor_incididunt_ut_labore_et_dolore_magna_aliqua:
+; CHECK: label="{an_even_longer_multiline_label_that_will_span_muliple_lines_Lorem_ipsum_dolor_si\l...t_amet_consectetur_adipiscing_elit_sed_do_eiusmod_tempor_incididunt_ut_labore_e\l...t_dolore_magna_aliqua:\l|  ret void\l}"  
+  ret void
+}
diff --git a/llvm/test/Other/cfg_deopt_unreach.ll b/llvm/test/Other/cfg_deopt_unreach.ll
--- a/llvm/test/Other/cfg_deopt_unreach.ll
+++ b/llvm/test/Other/cfg_deopt_unreach.ll
@@ -14,18 +14,18 @@
 define i8 @callee(ptr %c) alwaysinline {
   %c0 = load volatile i1, ptr %c
   br i1 %c0, label %lleft, label %lright
-; NO-FLAGS: label="{lleft:|  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
-; DEOPT-NOT: label="{lleft:|  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
-; UNREACH: label="{lleft:|  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
-; BOTH-FLAGS-NOT: label="{lleft:|  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
+; NO-FLAGS: label="{lleft:\l|  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32\l... 1) ]\l  ret i8 %v0\l}"
+; DEOPT-NOT: label="{lleft:\l|  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32\l... 1) ]\l  ret i8 %v0\l}"
+; UNREACH: label="{lleft:\l|  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32\l... 1) ]\l  ret i8 %v0\l}"
+; BOTH-FLAGS-NOT: label="{lleft:\l|  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32\l... 1) ]\l  ret i8 %v0\l}"
 lleft:
   %v0 = call i8(...) @llvm.experimental.deoptimize.i8(i32 1) [ "deopt"(i32 1) ]
   ret i8 %v0
 
-; NO-FLAGS: label="{lright:|  unreachable\l}"
-; DEOPT: label="{lright:|  unreachable\l}"
-; UNREACH-NOT: label="{lright:|  unreachable\l}"
-; BOTH-FLAGS-NOT: label="{lright:|  unreachable\l}"
+; NO-FLAGS: label="{lright:\l|  unreachable\l}"
+; DEOPT: label="{lright:\l|  unreachable\l}"
+; UNREACH-NOT: label="{lright:\l|  unreachable\l}"
+; BOTH-FLAGS-NOT: label="{lright:\l|  unreachable\l}"
 lright:
   unreachable
 }
diff --git a/polly/test/ScopDetect/dot-scops-npm.ll b/polly/test/ScopDetect/dot-scops-npm.ll
--- a/polly/test/ScopDetect/dot-scops-npm.ll
+++ b/polly/test/ScopDetect/dot-scops-npm.ll
@@ -15,7 +15,7 @@
 define void @func_npm(i32 %n, i32 %m, ptr noalias nonnull %A) {
 ; CHECK:      digraph "Scop Graph for 'func_npm' function"
 ; CHECK-NEXT: label="Scop Graph for 'func_npm' function"
-; CHECK:      Node0x[[EntryID:.*]] [shape=record,label="{entry:|  br label %outer.for\l}"];
+; CHECK:      Node0x[[EntryID:.*]] [shape=record,label="{entry:\l|  br label %outer.for\l}"];
 ; CHECK-NEXT: Node0x[[EntryID]] -> Node0x[[OUTER_FOR_ID:.*]];
 ; CHECK-NEXT: Node0x[[OUTER_FOR_ID]] [shape=record,label="{outer.for:
 ; CHECK-NEXT: Node0x[[OUTER_FOR_ID]] -> Node0x[[INNER_FOR_ID:.*]];