gas: gcfg: add_bb_at_ginsn must return root_bb

A GCFG (ginsn control flow graph) is created for SCFI purposes in GAS.
The existing GCFG creation process was ignoring some paths.

add_bb_at_ginsn () is a recursive function which should return the root
of the added basic blocks.  This property was being violated in some
traversals, e.g., where a taken path involving a sequence of a few basic
blocks eventually culminated in a GINSN_TYPE_RETURN instruction.  This
patch fixes the issue by keeping an explicit variable root_bb to
memorize the bb to be returned.

Next, find_or_make_bb () must either create or find the bb with the
first ginsn as the provided ginsn.  Add a few assertions to ensure
health of the cfg creation process.

Note that the testcase, in its current shape, is not fit for catching
regressions for the issue at hand.  Although the testcase does exercise
the updated code path, the testcase passes even without the current fix,
because the added edge in this specific testcase does not alter the
synthesized CFI.  (The missing edge is the fallthrough edge of the
conditional branch "jne .L13" in the testcase.)

Using a manual gcfg_print (), one can see the missing edge without the
fix.  Lets keep the testcase for now, until there is a better way to
test the GCFG for this issue (e.g., either by dumping the GCFG in
textual format, or a case when the missing edge does cause wrong
synthesized CFI).

gas/
	* ginsn.c (bb_add_edge): Fix a code comment.
	(find_bb): Likewise.
	(find_or_make_bb): Add new assertions to ensure health of cfg
	creation process.
	(add_bb_at_ginsn): Keep reference to the root_bb and return it.

gas/testsuite/
	* gas/scfi/x86_64/scfi-x86-64.exp: Add new test.
	* gas/scfi/x86_64/scfi-cfg-4.d: New test.
	* gas/scfi/x86_64/scfi-cfg-4.l: New test.
	* gas/scfi/x86_64/scfi-cfg-4.s: New test.

5 files changed, 164 insertions, 26 deletions

diff --git a/gas/ginsn.c b/gas/ginsn.c
index 492e161..be06324 100644
--- a/gas/ginsn.c
+++ b/gas/ginsn.c
@@ -614,6 +614,8 @@ gbb_cleanup (gbbS **bbp)
   *bbp = NULL;
 }
 
+/* Add an edge from the source bb FROM_BB to the sink bb TO_BB.  */
+
 static void
 bb_add_edge (gbbS* from_bb, gbbS *to_bb)
 {
@@ -638,7 +640,7 @@ bb_add_edge (gbbS* from_bb, gbbS *to_bb)
     }
   else
     {
-      /* Get the tail of the list.  */
+      /* Get the head of the list.  */
       tmpedge = from_bb->out_gedges;
       while (tmpedge)
 	{
@@ -689,6 +691,9 @@ static gbbS *
 add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 		 int *errp);
 
+/* Return the already existing basic block (if present), which begins with
+   GINSN, in the given GCFG.  Return NULL otherwise.  */
+
 static gbbS *
 find_bb (gcfgS *gcfg, ginsnS *ginsn)
 {
@@ -708,13 +713,18 @@ find_bb (gcfgS *gcfg, ginsnS *ginsn)
 	      break;
 	    }
 	}
-      /* Must be found if ginsn is visited.  */
+      /* Must be found because ginsn is visited.  */
       gas_assert (found_bb);
     }
 
   return found_bb;
 }
 
+/* Get the basic block starting at GINSN in the GCFG.
+
+   If not already present, the function will make one, while adding an edge
+   from the PREV_BB to it.  */
+
 static gbbS *
 find_or_make_bb (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 		 int *errp)
@@ -722,26 +732,40 @@ find_or_make_bb (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
   gbbS *found_bb = NULL;
 
   found_bb = find_bb (gcfg, ginsn);
-  if (found_bb)
-    return found_bb;
+  if (!found_bb)
+    found_bb = add_bb_at_ginsn (func, gcfg, ginsn, prev_bb, errp);
+
+  gas_assert (found_bb);
+  gas_assert (found_bb->first_ginsn == ginsn);
 
-  return add_bb_at_ginsn (func, gcfg, ginsn, prev_bb, errp);
+  return found_bb;
 }
 
-/* Add the basic block starting at GINSN to the given GCFG.
-   Also adds an edge from the PREV_BB to the newly added basic block.
+/* Add basic block(s) for all reachable, unvisited ginsns, starting from GINSN,
+   to the given GCFG.  Also add an edge from the PREV_BB to the root of the
+   newly added basic block(s).
 
-   This is a recursive function which returns the root of the added
-   basic blocks.  */
+   This is a recursive function which returns the root of the added basic
+   blocks.  */
 
 static gbbS *
 add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 		 int *errp)
 {
+  gbbS *root_bb = NULL;
   gbbS *current_bb = NULL;
   ginsnS *target_ginsn = NULL;
   const symbolS *taken_label;
 
+  /* Create a new bb.  N.B. The caller must ensure bb with this ginsn does not
+     already exist.  */
+  gas_assert (!find_bb (gcfg, ginsn));
+  root_bb = XCNEW (gbbS);
+  cfg_add_bb (gcfg, root_bb);
+  root_bb->first_ginsn = ginsn;
+
+  current_bb = root_bb;
+
   while (ginsn)
     {
       /* Skip these as they may be right after a GINSN_TYPE_RETURN.
@@ -749,6 +773,8 @@ add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 	 end of bb, and a logical exit from function.  */
       if (GINSN_F_FUNC_END_P (ginsn))
 	{
+	  /* Dont mark them visited yet though, leaving the option of these
+	     being visited via other control flows as applicable.  */
 	  ginsn = ginsn->next;
 	  continue;
 	}
@@ -765,27 +791,27 @@ add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 	    bb_add_edge (prev_bb, current_bb);
 	  break;
 	}
-      else if (current_bb && GINSN_F_USER_LABEL_P (ginsn))
+      else if (current_bb && current_bb->first_ginsn != ginsn
+	       && GINSN_F_USER_LABEL_P (ginsn))
 	{
-	  /* Create new bb starting at this label ginsn.  */
+	  /* Create new bb starting at ginsn for (user-defined) label.  This is
+	     likely going to be a destination of a some control flow.  */
 	  prev_bb = current_bb;
-	  find_or_make_bb (func, gcfg, ginsn, prev_bb, errp);
+	  current_bb = find_or_make_bb (func, gcfg, ginsn, prev_bb, errp);
+	  bb_add_edge (prev_bb, current_bb);
 	  break;
 	}
 
       if (current_bb == NULL)
 	{
-	  /* Create a new bb.  */
 	  current_bb = XCNEW (gbbS);
 	  cfg_add_bb (gcfg, current_bb);
+	  current_bb->first_ginsn = ginsn;
 	  /* Add edge for the Not Taken, or Fall-through path.  */
 	  if (prev_bb)
 	    bb_add_edge (prev_bb, current_bb);
 	}
 
-      if (current_bb->first_ginsn == NULL)
-	current_bb->first_ginsn = ginsn;
-
       ginsn->visited = true;
       current_bb->num_ginsns++;
       current_bb->last_ginsn = ginsn;
@@ -809,16 +835,21 @@ add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 	      taken_label = ginsn->src[0].sym;
 	      gas_assert (taken_label);
 
-	      /* Preserve the prev_bb to be the dominator bb as we are
-		 going to follow the taken path of the conditional branch
-		 soon.  */
+	      /* Preserve the prev_bb to be the source bb as we are going to
+		 follow the taken path of the conditional branch soon.  */
 	      prev_bb = current_bb;
 
 	      /* Follow the target on the taken path.  */
 	      target_ginsn = label_ginsn_map_find (taken_label);
 	      /* Add the bb for the target of the taken branch.  */
 	      if (target_ginsn)
-		find_or_make_bb (func, gcfg, target_ginsn, prev_bb, errp);
+		{
+		  current_bb = find_or_make_bb (func, gcfg, target_ginsn,
+						prev_bb, errp);
+		  gas_assert (prev_bb);
+		  bb_add_edge (prev_bb, current_bb);
+		  current_bb = NULL;
+		}
 	      else
 		{
 		  *errp = GCFG_JLABEL_NOT_PRESENT;
@@ -826,27 +857,45 @@ add_bb_at_ginsn (const symbolS *func, gcfgS *gcfg, ginsnS *ginsn, gbbS *prev_bb,
 				 _("missing label '%s' in func '%s' may result in imprecise cfg"),
 				 S_GET_NAME (taken_label), S_GET_NAME (func));
 		}
-	      /* Add the bb for the fall through path.  */
-	      find_or_make_bb (func, gcfg, ginsn->next, prev_bb, errp);
+
+	      if (ginsn->type == GINSN_TYPE_JUMP_COND)
+		{
+		  /* Add the bb for the fall through path.  */
+		  current_bb = find_or_make_bb (func, gcfg, ginsn->next,
+						prev_bb, errp);
+		  gas_assert (prev_bb);
+		  bb_add_edge (prev_bb, current_bb);
+		  current_bb = NULL;
+		}
+	      else
+		{
+		  /* Unconditional jump.  Current BB has been processed.  */
+		  current_bb = NULL;
+		  /* We'll come back to the ginsns following these (local)
+		     unconditional jmps from another path if they are indeed
+		     reachable code.  */
+		  break;
+		}
 	    }
 	 else
 	   {
 	     gas_assert (ginsn->type == GINSN_TYPE_RETURN
 			 || (ginsn->type == GINSN_TYPE_JUMP
 			     && !ginsn_direct_local_jump_p (ginsn)));
+	     /* Current BB has been processed.  */
+	     current_bb = NULL;
+
 	     /* We'll come back to the ginsns following GINSN_TYPE_RETURN or
 		other (non-local) unconditional jmps from another path if they
 		are indeed reachable code.  */
 	     break;
 	   }
-
-	 /* Current BB has been processed.  */
-	 current_bb = NULL;
 	}
+
       ginsn = ginsn->next;
     }
 
-  return current_bb;
+  return root_bb;
 }
 
 static int
diff --git a/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.d b/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.d
new file mode 100644
index 0000000..841fc3c
--- /dev/null
+++ b/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.d
@@ -0,0 +1,43 @@
+#as: --scfi=experimental -W
+#as:
+#objdump: -Wf
+#name: Synthesize CFI in presence of control flow 4
+#...
+Contents of the .eh_frame section:
+
+00000000 0+0014 0+0000 CIE
+  Version:               1
+  Augmentation:          "zR"
+  Code alignment factor: 1
+  Data alignment factor: -8
+  Return address column: 16
+  Augmentation data:     1b
+  DW_CFA_def_cfa: r7 \(rsp\) ofs 8
+  DW_CFA_offset: r16 \(rip\) at cfa-8
+  DW_CFA_nop
+  DW_CFA_nop
+
+0+0018 0+002c 0+001c FDE cie=00000000 pc=0000000000000000..0000000000000045
+  DW_CFA_advance_loc: 1 to 0000000000000001
+  DW_CFA_def_cfa_offset: 16
+  DW_CFA_offset: r3 \(rbx\) at cfa-16
+  DW_CFA_advance_loc: 6 to 0000000000000007
+  DW_CFA_def_cfa_offset: 32
+  DW_CFA_advance_loc: 15 to 0000000000000016
+  DW_CFA_remember_state
+  DW_CFA_advance_loc: 4 to 000000000000001a
+  DW_CFA_def_cfa_offset: 16
+  DW_CFA_advance_loc: 1 to 000000000000001b
+  DW_CFA_restore: r3 \(rbx\)
+  DW_CFA_def_cfa_offset: 8
+  DW_CFA_advance_loc: 1 to 000000000000001c
+  DW_CFA_restore_state
+  DW_CFA_advance_loc: 35 to 000000000000003f
+  DW_CFA_def_cfa_offset: 16
+  DW_CFA_advance_loc: 1 to 0000000000000040
+  DW_CFA_restore: r3 \(rbx\)
+  DW_CFA_def_cfa_offset: 8
+  DW_CFA_nop
+#...
+
+#pass
diff --git a/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.l b/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.l
new file mode 100644
index 0000000..abca835
--- /dev/null
+++ b/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.l
@@ -0,0 +1,2 @@
+.*Assembler messages:
+.*5: Warning: SCFI ignores most user-specified CFI directives
diff --git a/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.s b/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.s
new file mode 100644
index 0000000..ebcc6ad
--- /dev/null
+++ b/gas/testsuite/gas/scfi/x86_64/scfi-cfg-4.s
@@ -0,0 +1,42 @@
+	.text
+	.globl  foo_handler
+	.type   foo_handler, @function
+foo_handler:
+	.cfi_startproc
+	pushq   %rbx
+	.cfi_def_cfa_offset 16
+	.cfi_offset %rbx, -16
+	movl    %esi, %ebx
+	subq    $16, %rsp
+	.cfi_def_cfa_offset 32
+	movl    current_style(%rip), %eax
+	cmpl    $-1, %eax
+	je      .L12
+	testb   $4, %al
+	jne     .L13
+.L1:
+	.cfi_remember_state
+	addq    $16, %rsp
+	.cfi_def_cfa_offset 16
+	popq    %rbx
+	.cfi_restore %rbx
+	.cfi_def_cfa_offset 8
+	ret
+.L13:
+	.cfi_restore_state
+	movq    %rdi, 8(%rsp)
+	call    foo_handler_v2
+	testq   %rax, %rax
+	jne     .L1
+	movl    current_style(%rip), %eax
+	movq    8(%rsp), %rdi
+	jmp     .L3
+.L12:
+	addq    $16, %rsp
+	.cfi_def_cfa_offset 16
+	popq    %rbx
+	.cfi_restore %rbx
+	.cfi_def_cfa_offset 8
+	jmp     xstrdup
+	.cfi_endproc
+	.size   foo_handler, .-foo_handler
diff --git a/gas/testsuite/gas/scfi/x86_64/scfi-x86-64.exp b/gas/testsuite/gas/scfi/x86_64/scfi-x86-64.exp
index c004d99..63f0d7e 100644
--- a/gas/testsuite/gas/scfi/x86_64/scfi-x86-64.exp
+++ b/gas/testsuite/gas/scfi/x86_64/scfi-x86-64.exp
@@ -80,6 +80,8 @@ if  { ([istarget "x86_64-*-*"] && ![istarget "x86_64-*-linux*-gnux32"]) } then {
     run_list_test "scfi-cfg-2" "--scfi=experimental --warn"
     run_dump_test "scfi-cfg-3"
     run_list_test "scfi-cfg-3" "--scfi=experimental --warn"
+    run_dump_test "scfi-cfg-4"
+    run_list_test "scfi-cfg-4" "--scfi=experimental --warn"
     run_dump_test "scfi-asm-marker-1"
     run_list_test "scfi-asm-marker-1" "--scfi=experimental --warn"
     run_dump_test "scfi-asm-marker-2"