[SPARSE PATCH 0/5] detect invalid branches in the IR

[SPARSE PATCH 0/5] detect invalid branches in the IR

[Luc Van Oostenryck]

It's not allowed to do a goto into an expression statement.
For exemple, it's not well defined what should happen if such
an expression is not otherwise reachable and/or can be optimized
away. For such situations GCC issues an error, clang doesn't
and produce a valid IR but spare produce an invalid IR with
branches to unexisting BBs.

The goal of the patches in this series is:
*) To detect such gotos and issue a sensible error.
*) To make the IR somehow valid. Since the original
   expression has been optimized away, the IR replace
   the goto by a branch to itself.

-- Luc

base-commit: 79f7ac984473d031dfb9cef00119c2d542d0d4a6
-- 
2.26.0

[SPARSE PATCH 1/5] add testcase for 'jump inside discarded expression statement'

[Luc Van Oostenryck]

A goto done into an piece of code discarded at expand or
linearize time will produce an invalid IR.

Add a testcase for it.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/linear/goto-and-expr-stmt0.c | 28 +++++++++++++++++++++++++
 1 file changed, 28 insertions(+)
 create mode 100644 validation/linear/goto-and-expr-stmt0.c

diff --git a/validation/linear/goto-and-expr-stmt0.c b/validation/linear/goto-and-expr-stmt0.c
new file mode 100644
index 000000000000..548813531779
--- /dev/null
+++ b/validation/linear/goto-and-expr-stmt0.c
@@ -0,0 +1,28 @@
+int t(void)
+{
+	goto inside;
+	return 1 ? 2 : ({
+inside:
+			return 3;
+			4;
+		    });
+}
+
+void f(int x, int y)
+{
+	1 ? x : ({
+a:
+		 y;
+	});
+	goto a;
+}
+
+/*
+ * check-name: goto-and-expr-stmt0
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: END
+ * check-error-ignore
+ */
-- 
2.26.0

[SPARSE PATCH 2/5] add testcases for linearization of invalid labels

[Luc Van Oostenryck]

A goto to a reserved or a undeclared label will generate
an IR with a branch to a non-existing BB. Bad.

Add a testcase for these.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/linear/invalid-labels0.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)
 create mode 100644 validation/linear/invalid-labels0.c

diff --git a/validation/linear/invalid-labels0.c b/validation/linear/invalid-labels0.c
new file mode 100644
index 000000000000..ae3bf7283fb8
--- /dev/null
+++ b/validation/linear/invalid-labels0.c
@@ -0,0 +1,19 @@
+static void foo(void)
+{
+	goto return;
+}
+
+void bar(void)
+{
+	goto neverland;
+}
+
+/*
+ * check-name: invalid-labels0
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: END
+ * check-error-ignore
+ */
-- 
2.26.0

[SPARSE PATCH 3/5] do not issue a branch to non-existent label

[Luc Van Oostenryck]

If the label doesn't exist, the corresponding BB will never
be created and the CFG will be invalid.

So, do not issue the branch for goto to these labels.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                         | 13 +++++++++++--
 validation/linear/invalid-labels0.c |  1 -
 2 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/linearize.c b/linearize.c
index b040d345d469..4e9f9b3693e9 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2379,6 +2379,7 @@ static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stm
 	}
 
 	case STMT_GOTO: {
+		struct symbol *label;
 		struct symbol *sym;
 		struct expression *expr;
 		struct instruction *goto_ins;
@@ -2389,8 +2390,16 @@ static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stm
 		if (!bb_reachable(active))
 			break;
 
-		if (stmt->goto_label) {
-			add_goto(ep, get_bound_block(ep, stmt->goto_label));
+		label = stmt->goto_label;
+		if (label) {
+			if (!label->stmt) {
+				// do not issue a branch to non-existent labels
+				if (label->namespace == NS_LABEL)
+					break;
+				if (label->namespace == NS_NONE)
+					break;
+			}
+			add_goto(ep, get_bound_block(ep, label));
 			break;
 		}
 
diff --git a/validation/linear/invalid-labels0.c b/validation/linear/invalid-labels0.c
index ae3bf7283fb8..a15e9d434011 100644
--- a/validation/linear/invalid-labels0.c
+++ b/validation/linear/invalid-labels0.c
@@ -11,7 +11,6 @@ void bar(void)
 /*
  * check-name: invalid-labels0
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: END
-- 
2.26.0

[SPARSE PATCH 4/5] extract add_jump() from add_goto()

[Luc Van Oostenryck]

add_goto() uses the active BB (and automaticallydesactive
it just after). This is fine at linearization but is not
what is needed at later stages.

So, extract the gist into a separate helper: add_jump().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 17 +++++++++++------
 1 file changed, 11 insertions(+), 6 deletions(-)

diff --git a/linearize.c b/linearize.c
index 4e9f9b3693e9..a2cde941ce18 100644
--- a/linearize.c
+++ b/linearize.c
@@ -633,16 +633,21 @@ static void finish_block(struct entrypoint *ep)
 		ep->active = NULL;
 }
 
+static void add_jump(struct basic_block *src, struct basic_block *dst)
+{
+	struct instruction *br = alloc_instruction(OP_BR, 0);
+	br->bb_true = dst;
+	add_bb(&dst->parents, src);
+	add_bb(&src->children, dst);
+	br->bb = src;
+	add_instruction(&src->insns, br);
+}
+
 static void add_goto(struct entrypoint *ep, struct basic_block *dst)
 {
 	struct basic_block *src = ep->active;
 	if (bb_reachable(src)) {
-		struct instruction *br = alloc_instruction(OP_BR, 0);
-		br->bb_true = dst;
-		add_bb(&dst->parents, src);
-		add_bb(&src->children, dst);
-		br->bb = src;
-		add_instruction(&src->insns, br);
+		add_jump(src, dst);
 		ep->active = NULL;
 	}
 }
-- 
2.26.0

[SPARSE PATCH 5/5] perform early CFG cleanup

[Luc Van Oostenryck]

add insert_self_branch()

A goto done into an piece of code discarded at expand or
linearize time will produce an invalid IR. More precisely,
the BB containing this goto will have as children a BB which:
1) has no instructions at all, so no terminator
2) has a null ->ep (normaly interpreted as unreachable)
3) is not added to the list of BBs.

What's really annoying is that such gotos are not detected at
earlier stages, so such invalid IR can be created completly
silently.

Fix this by adding, before any optimizations, a cleanup phase
which will detect such BBs and:
1) add a warning for the corresponding gotos
1) add branch to themselves as a way to properly terminate
   (any terminator would do the job).
2) add them to the list of BBs and make them reachable.

Note: the downside of a cleanup like this is that it could
      hide other problems with invalid CFG and assumptions
      are made (in the warning) about the origin of the
      problem.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                                  | 27 +++++++++++++++++++++++++
 flow.h                                  |  1 +
 linearize.c                             |  5 +++++
 linearize.h                             |  1 +
 optimize.c                              |  3 +++
 validation/linear/goto-and-expr-stmt0.c |  1 -
 6 files changed, 37 insertions(+), 1 deletion(-)

diff --git a/flow.c b/flow.c
index ef8d04e5827f..976d476cdacd 100644
--- a/flow.c
+++ b/flow.c
@@ -814,4 +814,31 @@ out:
 	} END_FOR_EACH_PTR(bb);
 }
 
+void cleanup_cfg(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		struct basic_block *tgt;
+		struct instruction *br;
+
+		if (!bb->insns)
+			continue;
+		if (!bb->ep)
+			continue;
+
+		br = last_instruction(bb->insns);
+		if (!br)
+			continue;
 
+		FOR_EACH_PTR(bb->children, tgt) {
+			if (!tgt->insns) {
+				sparse_error(br->pos, "branch to unexisting label");
+				insert_self_branch(tgt);
+				tgt->ep = ep;
+				if (!lookup_bb(ep->bbs, tgt))
+					add_bb(&ep->bbs, tgt);
+			}
+		} END_FOR_EACH_PTR(tgt);
+	} END_FOR_EACH_PTR(bb);
+}
diff --git a/flow.h b/flow.h
index 099767d408f5..13eca195bab4 100644
--- a/flow.h
+++ b/flow.h
@@ -18,6 +18,7 @@ extern void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local);
 extern void simplify_symbol_usage(struct entrypoint *ep);
 extern void simplify_memops(struct entrypoint *ep);
 extern void pack_basic_blocks(struct entrypoint *ep);
+extern void cleanup_cfg(struct entrypoint *ep);
 
 extern void convert_instruction_target(struct instruction *insn, pseudo_t src);
 extern void remove_dead_insns(struct entrypoint *);
diff --git a/linearize.c b/linearize.c
index a2cde941ce18..7b685016ea3e 100644
--- a/linearize.c
+++ b/linearize.c
@@ -740,6 +740,11 @@ void insert_select(struct basic_block *bb, struct instruction *br, struct instru
 	add_instruction(&bb->insns, br);
 }
 
+void insert_self_branch(struct basic_block *bb)
+{
+	add_jump(bb, bb);
+}
+
 static inline int bb_empty(struct basic_block *bb)
 {
 	return !bb->insns;
diff --git a/linearize.h b/linearize.h
index 76efd0b47ffa..7eca88016e26 100644
--- a/linearize.h
+++ b/linearize.h
@@ -308,6 +308,7 @@ struct entrypoint {
 
 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);
 extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target);
+extern void insert_self_branch(struct basic_block *bb);
 
 struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
 struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident);
diff --git a/optimize.c b/optimize.c
index e8cb7fc31e4b..515d6d8d81e5 100644
--- a/optimize.c
+++ b/optimize.c
@@ -48,6 +48,9 @@ void optimize(struct entrypoint *ep)
 	if (fdump_ir & PASS_LINEARIZE)
 		show_entry(ep);
 
+	// Detect invalid gotos and band-aid them
+	cleanup_cfg(ep);
+
 	/*
 	 * Do trivial flow simplification - branches to
 	 * branches, kill dead basicblocks etc
diff --git a/validation/linear/goto-and-expr-stmt0.c b/validation/linear/goto-and-expr-stmt0.c
index 548813531779..a68aa59bcbcf 100644
--- a/validation/linear/goto-and-expr-stmt0.c
+++ b/validation/linear/goto-and-expr-stmt0.c
@@ -20,7 +20,6 @@ a:
 /*
  * check-name: goto-and-expr-stmt0
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: END
-- 
2.26.0