[PATCH 0/5] add support for __builtin_unreachable()

[PATCH 0/5] add support for __builtin_unreachable()

[Luc Van Oostenryck]

__builtin_unreachable() has direct consequences on the CFG
and should thus not be ignored. This series add minimal
support for it, motivated by some improvements in the
processing of contexts.


Luc Van Oostenryck (5):
  add testcases for OP_UNREACH
  add instruction OP_UNREACH
  add an implicit __builtin_unreachable() for __noreturn
  add support for linearization of builtins
  teach sparse to linearize __builtin_unreachable()

 Documentation/IR.rst                          |  3 ++
 builtin.c                                     |  2 +
 linearize.c                                   | 52 +++++++++++++++++++
 opcode.def                                    |  1 +
 symbol.h                                      |  7 ++-
 validation/context-unreachable.c              | 15 ++++++
 validation/linear/builtin_unreachable0.c      | 29 +++++++++++
 ...n_unreachable.c => builtin_unreachable1.c} | 15 +++---
 validation/linear/noreturn-unreachable0.c     | 22 ++++++++
 9 files changed, 137 insertions(+), 9 deletions(-)
 create mode 100644 validation/context-unreachable.c
 create mode 100644 validation/linear/builtin_unreachable0.c
 rename validation/linear/{builtin_unreachable.c => builtin_unreachable1.c} (59%)
 create mode 100644 validation/linear/noreturn-unreachable0.c


base-commit: 0558317d0c7a2e20a6d82b7ef35357ec02e2ad38
-- 
2.25.1

[PATCH 1/5] add testcases for OP_UNREACH

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/context-unreachable.c              | 16 ++++++++++
 validation/linear/builtin_unreachable0.c      | 30 +++++++++++++++++++
 ...n_unreachable.c => builtin_unreachable1.c} | 14 ++++-----
 validation/linear/noreturn-unreachable0.c     | 23 ++++++++++++++
 4 files changed, 76 insertions(+), 7 deletions(-)
 create mode 100644 validation/context-unreachable.c
 create mode 100644 validation/linear/builtin_unreachable0.c
 rename validation/linear/{builtin_unreachable.c => builtin_unreachable1.c} (65%)
 create mode 100644 validation/linear/noreturn-unreachable0.c

diff --git a/validation/context-unreachable.c b/validation/context-unreachable.c
new file mode 100644
index 000000000000..3e330403ce01
--- /dev/null
+++ b/validation/context-unreachable.c
@@ -0,0 +1,16 @@
+int fun(void);
+
+static void foo(void)
+{
+	__context__(1);
+	if (!fun()) {
+		__builtin_unreachable();
+		return;
+	}
+	__context__(-1);
+}
+
+/*
+ * check-name: context-unreachable
+ * check-known-to-fail
+ */
diff --git a/validation/linear/builtin_unreachable0.c b/validation/linear/builtin_unreachable0.c
new file mode 100644
index 000000000000..5da9d074ae5f
--- /dev/null
+++ b/validation/linear/builtin_unreachable0.c
@@ -0,0 +1,30 @@
+extern void die(void) __attribute__((noreturn));
+
+int foo(int p)
+{
+	if (p == 3)
+		__builtin_unreachable();
+	return p;
+}
+
+/*
+ * check-name: builtin_unreachable0
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-start
+foo:
+.L0:
+	<entry-point>
+	seteq.32    %r2 <- %arg1, $3
+	cbr         %r2, .L1, .L3
+
+.L1:
+	unreach
+
+.L3:
+	ret.32      %arg1
+
+
+ * check-output-end
+ */
diff --git a/validation/linear/builtin_unreachable.c b/validation/linear/builtin_unreachable1.c
similarity index 65%
rename from validation/linear/builtin_unreachable.c
rename to validation/linear/builtin_unreachable1.c
index 4f13b892af54..280f853d8a07 100644
--- a/validation/linear/builtin_unreachable.c
+++ b/validation/linear/builtin_unreachable1.c
@@ -1,15 +1,15 @@
-void function_that_never_returns(void);
+extern void die(void);
 
 int foo(int c)
 {
 	if (c)
 		return 1;
-	function_that_never_returns();
+	die();
 	__builtin_unreachable();
 }
 
 /*
- * check-name: __builtin_unreachable()
+ * check-name: builtin_unreachable1
  * check-command: test-linearize -Wno-decl $file
  *
  * check-known-to-fail
@@ -19,13 +19,13 @@ foo:
 	<entry-point>
 	cbr         %arg1, .L3, .L2
 
-.L2:
-	call        function_that_never_returns
-	unreach
-
 .L3:
 	ret.32      $1
 
+.L2:
+	call        die
+	unreach
+
 
  * check-output-end
  */
diff --git a/validation/linear/noreturn-unreachable0.c b/validation/linear/noreturn-unreachable0.c
new file mode 100644
index 000000000000..b76319458e96
--- /dev/null
+++ b/validation/linear/noreturn-unreachable0.c
@@ -0,0 +1,23 @@
+extern void die(void) __attribute__((noreturn));
+
+int foo(void)
+{
+	die();
+	return 0;
+}
+
+/*
+ * check-name: noreturn-unreachable0
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-start
+foo:
+.L0:
+	<entry-point>
+	call        die
+	unreach
+
+
+ * check-output-end
+ */
-- 
2.25.1

Re: [PATCH 1/5] add testcases for OP_UNREACH

[Ramsay Jones]

On 18/03/2020 17:31, Luc Van Oostenryck wrote:
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  validation/context-unreachable.c              | 16 ++++++++++
>  validation/linear/builtin_unreachable0.c      | 30 +++++++++++++++++++
>  ...n_unreachable.c => builtin_unreachable1.c} | 14 ++++-----
>  validation/linear/noreturn-unreachable0.c     | 23 ++++++++++++++
>  4 files changed, 76 insertions(+), 7 deletions(-)
>  create mode 100644 validation/context-unreachable.c
>  create mode 100644 validation/linear/builtin_unreachable0.c
>  rename validation/linear/{builtin_unreachable.c => builtin_unreachable1.c} (65%)
>  create mode 100644 validation/linear/noreturn-unreachable0.c
> 
> diff --git a/validation/context-unreachable.c b/validation/context-unreachable.c
> new file mode 100644
> index 000000000000..3e330403ce01
> --- /dev/null
> +++ b/validation/context-unreachable.c
> @@ -0,0 +1,16 @@
> +int fun(void);
> +
> +static void foo(void)
> +{
> +	__context__(1);
> +	if (!fun()) {
> +		__builtin_unreachable();
> +		return;
> +	}
> +	__context__(-1);
> +}
> +
> +/*
> + * check-name: context-unreachable
> + * check-known-to-fail
> + */
> diff --git a/validation/linear/builtin_unreachable0.c b/validation/linear/builtin_unreachable0.c
> new file mode 100644
> index 000000000000..5da9d074ae5f
> --- /dev/null
> +++ b/validation/linear/builtin_unreachable0.c
> @@ -0,0 +1,30 @@
> +extern void die(void) __attribute__((noreturn));

Hmm, is this declaration intended?

ATB,
Ramsay Jones

> +
> +int foo(int p)
> +{
> +	if (p == 3)
> +		__builtin_unreachable();
> +	return p;
> +}
> +
> +/*
> + * check-name: builtin_unreachable0
> + * check-command: test-linearize -Wno-decl $file
> + * check-known-to-fail
> + *
> + * check-output-start
> +foo:
> +.L0:
> +	<entry-point>
> +	seteq.32    %r2 <- %arg1, $3
> +	cbr         %r2, .L1, .L3
> +
> +.L1:
> +	unreach
> +
> +.L3:
> +	ret.32      %arg1
> +
> +
> + * check-output-end
> + */
> diff --git a/validation/linear/builtin_unreachable.c b/validation/linear/builtin_unreachable1.c
> similarity index 65%
> rename from validation/linear/builtin_unreachable.c
> rename to validation/linear/builtin_unreachable1.c
> index 4f13b892af54..280f853d8a07 100644
> --- a/validation/linear/builtin_unreachable.c
> +++ b/validation/linear/builtin_unreachable1.c
> @@ -1,15 +1,15 @@
> -void function_that_never_returns(void);
> +extern void die(void);
>  
>  int foo(int c)
>  {
>  	if (c)
>  		return 1;
> -	function_that_never_returns();
> +	die();
>  	__builtin_unreachable();
>  }
>  
>  /*
> - * check-name: __builtin_unreachable()
> + * check-name: builtin_unreachable1
>   * check-command: test-linearize -Wno-decl $file
>   *
>   * check-known-to-fail
> @@ -19,13 +19,13 @@ foo:
>  	<entry-point>
>  	cbr         %arg1, .L3, .L2
>  
> -.L2:
> -	call        function_that_never_returns
> -	unreach
> -
>  .L3:
>  	ret.32      $1
>  
> +.L2:
> +	call        die
> +	unreach
> +
>  
>   * check-output-end
>   */
> diff --git a/validation/linear/noreturn-unreachable0.c b/validation/linear/noreturn-unreachable0.c
> new file mode 100644
> index 000000000000..b76319458e96
> --- /dev/null
> +++ b/validation/linear/noreturn-unreachable0.c
> @@ -0,0 +1,23 @@
> +extern void die(void) __attribute__((noreturn));
> +
> +int foo(void)
> +{
> +	die();
> +	return 0;
> +}
> +
> +/*
> + * check-name: noreturn-unreachable0
> + * check-command: test-linearize -Wno-decl $file
> + * check-known-to-fail
> + *
> + * check-output-start
> +foo:
> +.L0:
> +	<entry-point>
> +	call        die
> +	unreach
> +
> +
> + * check-output-end
> + */
> 

Re: [PATCH 1/5] add testcases for OP_UNREACH

[Luc Van Oostenryck]

On Thu, Mar 19, 2020 at 10:24:28PM +0000, Ramsay Jones wrote:
> On 18/03/2020 17:31, Luc Van Oostenryck wrote:
> > diff --git a/validation/linear/builtin_unreachable0.c b/validation/linear/builtin_unreachable0.c
> > new file mode 100644
> > index 000000000000..5da9d074ae5f
> > --- /dev/null
> > +++ b/validation/linear/builtin_unreachable0.c
> > @@ -0,0 +1,30 @@
> > +extern void die(void) __attribute__((noreturn));
> 
> Hmm, is this declaration intended?

Only before it was cut-and-pasted ;)
Thanks for noticing.

-- Luc 

[PATCH 2/5] add instruction OP_UNREACH

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Documentation/IR.rst | 3 +++
 linearize.c          | 3 +++
 opcode.def           | 1 +
 3 files changed, 7 insertions(+)

diff --git a/Documentation/IR.rst b/Documentation/IR.rst
index 9d6f2299eaf1..33a761662fad 100644
--- a/Documentation/IR.rst
+++ b/Documentation/IR.rst
@@ -47,6 +47,9 @@ Terminators
 	* .type: type of .cond, must be an integral type
 	* .multijmp_list: pairs of case-value - destination basic block
 
+.. op:: OP_UNREACH
+	Mark code as unreachable
+
 .. op:: OP_COMPUTEDGOTO
 	Computed goto / branch to register
 
diff --git a/linearize.c b/linearize.c
index 30ed2a302d95..f1e538e23ae1 100644
--- a/linearize.c
+++ b/linearize.c
@@ -183,6 +183,7 @@ static const char *opcodes[] = {
 	[OP_BR] = "br",
 	[OP_CBR] = "cbr",
 	[OP_SWITCH] = "switch",
+	[OP_UNREACH] = "unreach",
 	[OP_COMPUTEDGOTO] = "jmp *",
 	
 	/* Binary */
@@ -399,6 +400,8 @@ const char *show_instruction(struct instruction *insn)
 		} END_FOR_EACH_PTR(jmp);
 		break;
 	}
+	case OP_UNREACH:
+		break;
 
 	case OP_PHISOURCE: {
 		struct instruction *phi;
diff --git a/opcode.def b/opcode.def
index 57d827f449b5..2583e2f4a602 100644
--- a/opcode.def
+++ b/opcode.def
@@ -10,6 +10,7 @@ OPCODE(RET,             BADOP,    BADOP,    BADOP, 1, OPF_NONE)
 OPCODE(BR,              BADOP,    BADOP,    BADOP, 0, OPF_NONE)
 OPCODE(CBR,             BADOP,    BADOP,    BADOP, 1, OPF_NONE)
 OPCODE(SWITCH,          BADOP,    BADOP,    BADOP, 1, OPF_NONE)
+OPCODE(UNREACH,         BADOP,    BADOP,    BADOP, 0, OPF_NONE)
 OPCODE(COMPUTEDGOTO,    BADOP,    BADOP,    BADOP, 1, OPF_NONE)
 OPCODE_RANGE(TERMINATOR, RET, COMPUTEDGOTO)
 
-- 
2.25.1

[PATCH 3/5] add an implicit __builtin_unreachable() for __noreturn

[Luc Van Oostenryck]

The semantic of a __noreturn function is that ... it doesn't return.

So, insert an instruction OP_UNREACH after calls to such functions.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                               | 10 ++++++++++
 validation/linear/noreturn-unreachable0.c |  1 -
 2 files changed, 10 insertions(+), 1 deletion(-)

diff --git a/linearize.c b/linearize.c
index f1e538e23ae1..19c284c4a456 100644
--- a/linearize.c
+++ b/linearize.c
@@ -657,6 +657,13 @@ static void add_one_insn(struct entrypoint *ep, struct instruction *insn)
 	}
 }
 
+static void add_unreachable(struct entrypoint *ep)
+{
+	struct instruction *insn = alloc_instruction(OP_UNREACH, 0);
+	add_one_insn(ep, insn);
+	ep->active = NULL;
+}
+
 static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
 {
 	if (!bb_terminated(ep->active))
@@ -1551,6 +1558,9 @@ static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expressi
 				add_one_insn(ep, insn);
 			}
 		} END_FOR_EACH_PTR(context);
+
+		if (ctype->modifiers & MOD_NORETURN)
+			add_unreachable(ep);
 	}
 
 	return retval;
diff --git a/validation/linear/noreturn-unreachable0.c b/validation/linear/noreturn-unreachable0.c
index b76319458e96..13fddc8cfd40 100644
--- a/validation/linear/noreturn-unreachable0.c
+++ b/validation/linear/noreturn-unreachable0.c
@@ -9,7 +9,6 @@ int foo(void)
 /*
  * check-name: noreturn-unreachable0
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-start
 foo:
-- 
2.25.1

[PATCH 4/5] add support for linearization of builtins

[Luc Van Oostenryck]

Sparse ignores most builtins. A few of them are directly
interpreted at parsing time (types_compatible_p, offsetof).
Some others are expanded if their argument(s) are constant
but that's all.

However, some of the builtins are significant at the IR
level and shouldn't thus be ignored.

This patch add the support needed for the linearization of
these builtins.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 builtin.c   |  2 ++
 linearize.c | 32 ++++++++++++++++++++++++++++++++
 symbol.h    |  7 ++++++-
 3 files changed, 40 insertions(+), 1 deletion(-)

diff --git a/builtin.c b/builtin.c
index 52285a91cd1e..debc22c036ec 100644
--- a/builtin.c
+++ b/builtin.c
@@ -418,6 +418,8 @@ void init_builtins(int stream)
 		sym->op = ptr->op;
 		sym->builtin = 1;
 	}
+
+	init_linearized_builtins(stream);
 }
 
 static void declare_builtin(const char *name, struct symbol *rtype, int variadic, ...)
diff --git a/linearize.c b/linearize.c
index 19c284c4a456..25d6327bf6f1 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1509,6 +1509,11 @@ static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expressi
 
 	fn = expr->fn;
 	fntype = fn->ctype;
+
+	// handle builtins
+	if (fntype->op && fntype->op->linearize)
+		return fntype->op->linearize(ep, expr);
+
 	ctype = &fntype->ctype;
 	if (fntype->type == SYM_NODE)
 		fntype = fntype->ctype.base_type;
@@ -2526,3 +2531,30 @@ struct entrypoint *linearize_symbol(struct symbol *sym)
 		return linearize_fn(sym, base_type);
 	return NULL;
 }
+
+/*
+ * Builtin functions
+ */
+
+static struct sym_init {
+	const char *name;
+	pseudo_t (*linearize)(struct entrypoint *, struct expression*);
+	struct symbol_op op;
+} builtins_table[] = {
+	// must be declared in builtin.c:declare_builtins[]
+	{ }
+};
+
+void init_linearized_builtins(int stream)
+{
+	struct sym_init *ptr;
+
+	for (ptr = builtins_table; ptr->name; ptr++) {
+		struct symbol *sym;
+		sym = create_symbol(stream, ptr->name, SYM_NODE, NS_SYMBOL);
+		if (!sym->op)
+			sym->op = &ptr->op;
+		sym->op->type |= KW_BUILTIN;
+		ptr->op.linearize = ptr->linearize;
+	}
+}
diff --git a/symbol.h b/symbol.h
index 9ef5a886172f..270ae098cacf 100644
--- a/symbol.h
+++ b/symbol.h
@@ -78,7 +78,7 @@ enum keyword {
 	KW_MODIFIER	= 1 << 1,
 	KW_QUALIFIER	= 1 << 2,
 	KW_ATTRIBUTE	= 1 << 3,
-     // KW UNUSED	= 1 << 4,
+	KW_BUILTIN	= 1 << 4,
 	KW_ASM		= 1 << 5,
 	KW_MODE		= 1 << 6,
      // KW UNUSED	= 1 << 7,
@@ -112,11 +112,15 @@ struct decl_state {
 	unsigned char is_ext_visible;
 };
 
+struct pseudo;
+struct entrypoint;
+
 struct symbol_op {
 	enum keyword type;
 	int (*evaluate)(struct expression *);
 	int (*expand)(struct expression *, int);
 	int (*args)(struct expression *);
+	struct pseudo *(*linearize)(struct entrypoint *, struct expression *);
 
 	/* keywords */
 	struct token *(*declarator)(struct token *token, struct decl_state *ctx);
@@ -308,6 +312,7 @@ extern struct symbol *lookup_symbol(struct ident *, enum namespace);
 extern struct symbol *create_symbol(int stream, const char *name, int type, int namespace);
 extern void init_symbols(void);
 extern void init_builtins(int stream);
+extern void init_linearized_builtins(int stream);
 extern void declare_builtins(void);
 extern void init_ctype(void);
 extern struct symbol *alloc_symbol(struct position, int type);
-- 
2.25.1

[PATCH 5/5] teach sparse to linearize __builtin_unreachable()

[Luc Van Oostenryck]

__builtin_unreachable() is one of the builtin that shouldn't
be ignored at IR level since it directly impact the CFG.

So, add the infrastructure put in place in the previous patch
to generate the OP_UNREACH instruction instead of generating
a call to a non-existing function "__builtin_unreachable()".

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                              | 7 +++++++
 validation/context-unreachable.c         | 1 -
 validation/linear/builtin_unreachable0.c | 1 -
 validation/linear/builtin_unreachable1.c | 1 -
 4 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/linearize.c b/linearize.c
index 25d6327bf6f1..615636ed1f83 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2536,12 +2536,19 @@ struct entrypoint *linearize_symbol(struct symbol *sym)
  * Builtin functions
  */
 
+static pseudo_t linearize_unreachable(struct entrypoint *ep, struct expression *exp)
+{
+	add_unreachable(ep);
+	return VOID;
+}
+
 static struct sym_init {
 	const char *name;
 	pseudo_t (*linearize)(struct entrypoint *, struct expression*);
 	struct symbol_op op;
 } builtins_table[] = {
 	// must be declared in builtin.c:declare_builtins[]
+	{ "__builtin_unreachable", linearize_unreachable },
 	{ }
 };
 
diff --git a/validation/context-unreachable.c b/validation/context-unreachable.c
index 3e330403ce01..8664962ea088 100644
--- a/validation/context-unreachable.c
+++ b/validation/context-unreachable.c
@@ -12,5 +12,4 @@ static void foo(void)
 
 /*
  * check-name: context-unreachable
- * check-known-to-fail
  */
diff --git a/validation/linear/builtin_unreachable0.c b/validation/linear/builtin_unreachable0.c
index 5da9d074ae5f..fb59a3408987 100644
--- a/validation/linear/builtin_unreachable0.c
+++ b/validation/linear/builtin_unreachable0.c
@@ -10,7 +10,6 @@ int foo(int p)
 /*
  * check-name: builtin_unreachable0
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-start
 foo:
diff --git a/validation/linear/builtin_unreachable1.c b/validation/linear/builtin_unreachable1.c
index 280f853d8a07..a83da079a3c9 100644
--- a/validation/linear/builtin_unreachable1.c
+++ b/validation/linear/builtin_unreachable1.c
@@ -12,7 +12,6 @@ int foo(int c)
  * check-name: builtin_unreachable1
  * check-command: test-linearize -Wno-decl $file
  *
- * check-known-to-fail
  * check-output-start
 foo:
 .L0:
-- 
2.25.1