[PATCH 00/29] Simple & Efficient SSA construction.

[PATCH 00/29] Simple & Efficient SSA construction.

[Luc Van Oostenryck]

The goal of this series is to implement and integrate to sparse
the method described in the paper:
    "Simple and Efficient Construction of Static Single Assignment Form"
	by Matthias Braun, Sebastian Buchwald, Sebastian Hack,
	   Roland Leissa, Christoph Mallon and Andreas Zwinkau.
    cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf

In the present case, the principal motivation to use this method
is that the current one in sparse is severely broken.


The series is also available in the git repository at:

  git://github.com/lucvoo/sparse.git sssa-mini-v1

for you to fetch changes up to 98a21bc0c82af5115687c7e03a277519836bcac6:

  sssa: remove now unneeded simplify_one_symbol() (2017-08-16 17:25:25 +0200)

----------------------------------------------------------------
Luc Van Oostenryck (29):
      remove wrong part of simplify_loads()
      give a type to OP_PHISOURCEs
      fix test case kill-phi-ttsb
      add test case for incomplete type
      add test case for bad return type
      topasm: top-level asm is special
      ret-void: return nothing only for void functions
      small code reorg of add_store()
      add helper to test if a variable is "simple"
      add helper imple_access() to test if an access is "simple"
      add PSEUDO_UNDEF
      add undef_pseudo()
      add insert_phi_node()
      extract alloc_phisrc() from alloc_phi()
      add remove_use()
      ptrmap: add missing #include "compat.h"
      ptrmap: core implementation
      ptrmap: add type-safe interface
      sssa: add Simple SSA interfaces
      sssa: add needed new members
      sssa: add basic implementation
      sssa: add seal_gotos() needed to seal BBs targeted by gotos
      sssa: set var's ident
      sssa: add PSEUDO_INDIR
      sssa: reorg load_var()
      sssa: protect against unreachable loops
      sssa: remove trivial phi-nodes
      sssa: switch to the new SSA construction
      sssa: remove now unneeded simplify_one_symbol()

 Makefile                                |   2 +
 allocate.h                              |   2 +
 flow.c                                  | 324 --------------------------------
 flow.h                                  |   2 +-
 linearize.c                             | 174 ++++++++++++-----
 linearize.h                             |  23 ++-
 memops.c                                |  63 -------
 ptrmap.c                                |  84 +++++++++
 ptrmap.h                                |  28 +++
 simplify.c                              |  13 ++
 sparse-llvm.c                           |   4 +
 ssa.c                                   | 219 +++++++++++++++++++++
 ssa.h                                   |  12 ++
 symbol.h                                |  34 ++++
 validation/bad-return-type.c            |  19 ++
 validation/cast-constant-to-float.c     |   8 +-
 validation/cast-constants.c             |  40 ++--
 validation/cast-kinds.c                 | 160 ++++++++--------
 validation/context.c                    |   2 +-
 validation/incomplete-struct.c          |  23 +++
 validation/kill-casts.c                 |   1 -
 validation/kill-phi-ttsbb.c             |   2 +-
 validation/linear/bitfield-init-zero.c  |  24 +--
 validation/linear/struct-init-partial.c |   8 +-
 validation/loop-linearization.c         |  60 +++---
 validation/memops-volatile.c            |   4 +-
 validation/optim/bool-simplify.c        |  12 +-
 27 files changed, 745 insertions(+), 602 deletions(-)
 create mode 100644 ptrmap.c
 create mode 100644 ptrmap.h
 create mode 100644 ssa.c
 create mode 100644 ssa.h
 create mode 100644 validation/bad-return-type.c
 create mode 100644 validation/incomplete-struct.c

[PATCH 01/29] remove wrong part of simplify_loads()

[Luc Van Oostenryck]

Currently simplify_loads() is broken with exactly the
same error as in simplify_one_symbol().

The core of the problem is that phi-nodes are stored at
the place where the value is needed, where the initial load
was, while phi-nodes must be placed where branches meet.

Temporary fix this removing this 'simplification'.

Note: It's possible to do this a bit less crudely
Note: This patch is kinda useless without the SSA construction
      first fixed..

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 memops.c                | 63 -------------------------------------------------
 validation/kill-casts.c |  1 -
 2 files changed, 64 deletions(-)

diff --git a/memops.c b/memops.c
index aeacdf566..99430e455 100644
--- a/memops.c
+++ b/memops.c
@@ -16,51 +16,6 @@
 #include "linearize.h"
 #include "flow.h"
 
-static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
-	struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
-	int local)
-{
-	struct basic_block *parent;
-
-	FOR_EACH_PTR(bb->parents, parent) {
-		struct instruction *one;
-		struct instruction *br;
-		pseudo_t phi;
-
-		FOR_EACH_PTR_REVERSE(parent->insns, one) {
-			int dominance;
-			if (!one->bb)
-				continue;
-			if (one == insn)
-				goto no_dominance;
-			dominance = dominates(pseudo, insn, one, local);
-			if (dominance < 0) {
-				if (one->opcode == OP_LOAD)
-					continue;
-				return 0;
-			}
-			if (!dominance)
-				continue;
-			goto found_dominator;
-		} END_FOR_EACH_PTR_REVERSE(one);
-no_dominance:
-		if (parent->generation == generation)
-			continue;
-		parent->generation = generation;
-
-		if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
-			return 0;
-		continue;
-
-found_dominator:
-		br = delete_last_instruction(&parent->insns);
-		phi = alloc_phi(parent, one->target, one->size);
-		phi->ident = phi->ident ? : one->target->ident;
-		add_instruction(&parent->insns, br);
-		use_pseudo(insn, phi, add_pseudo(dominators, phi));
-	} END_FOR_EACH_PTR(parent);
-	return 1;
-}		
 
 static int address_taken(pseudo_t pseudo)
 {
@@ -91,8 +46,6 @@ static void simplify_loads(struct basic_block *bb)
 			struct instruction *dom;
 			pseudo_t pseudo = insn->src;
 			int local = local_pseudo(pseudo);
-			struct pseudo_list *dominators;
-			unsigned long generation;
 
 			/* Check for illegal offsets.. */
 			check_access(insn);
@@ -117,22 +70,6 @@ static void simplify_loads(struct basic_block *bb)
 					goto next_load;
 				}
 			} END_FOR_EACH_PTR_REVERSE(dom);
-
-			/* OK, go find the parents */
-			generation = ++bb_generation;
-			bb->generation = generation;
-			dominators = NULL;
-			if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
-				/* This happens with initial assignments to structures etc.. */
-				if (!dominators) {
-					if (local) {
-						assert(pseudo->type != PSEUDO_ARG);
-						convert_load_instruction(insn, value_pseudo(0));
-					}
-					goto next_load;
-				}
-				rewrite_load_instruction(insn, dominators);
-			}
 		}
 next_load:
 		/* Do the next one */;
diff --git a/validation/kill-casts.c b/validation/kill-casts.c
index cf52f2460..7b72c4719 100644
--- a/validation/kill-casts.c
+++ b/validation/kill-casts.c
@@ -18,5 +18,4 @@ void foo(struct s *x)
  * check-command: test-linearize $file
  *
  * check-output-ignore
- * check-output-excludes: cast\\.
  */
-- 
2.14.0

[PATCH 02/29] give a type to OP_PHISOURCEs

[Luc Van Oostenryck]

Currently, OP_PHISOURCEs are given a size but not a type.

For consistency and for sparse-LLVM which need it,
give them a type too.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c      |  2 +-
 linearize.c | 16 +++++++---------
 linearize.h |  2 +-
 3 files changed, 9 insertions(+), 11 deletions(-)

diff --git a/flow.c b/flow.c
index 6b2c879a8..78dd6b3a5 100644
--- a/flow.c
+++ b/flow.c
@@ -414,7 +414,7 @@ found_dominator:
 		if (dominators && phisrc_in_bb(*dominators, parent))
 			continue;
 		br = delete_last_instruction(&parent->insns);
-		phi = alloc_phi(parent, one->target, one->size);
+		phi = alloc_phi(parent, one->target, one->type);
 		phi->ident = phi->ident ? : pseudo->ident;
 		add_instruction(&parent->insns, br);
 		use_pseudo(insn, phi, add_pseudo(dominators, phi));
diff --git a/linearize.c b/linearize.c
index ba76397ea..e3d234e7e 100644
--- a/linearize.c
+++ b/linearize.c
@@ -821,7 +821,7 @@ static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
 	return pseudo;
 }
 
-pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size)
+pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
 {
 	struct instruction *insn;
 	pseudo_t phi;
@@ -830,7 +830,7 @@ pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size)
 	if (!source)
 		return VOID;
 
-	insn = alloc_instruction(OP_PHISOURCE, size);
+	insn = alloc_typed_instruction(OP_PHISOURCE, type);
 	phi = __alloc_pseudo(0);
 	phi->type = PSEUDO_PHI;
 	phi->nr = ++nr;
@@ -1384,19 +1384,18 @@ static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expres
 	struct basic_block *bb_false;
 	struct basic_block *merge = alloc_basic_block(ep, expr->pos);
 	pseudo_t phi1, phi2;
-	int size = type_size(expr->ctype);
 
 	if (!expr_false || !ep->active)
 		return VOID;
 
 	bb_false = alloc_basic_block(ep, expr_false->pos);
 	src1 = linearize_expression(ep, cond);
-	phi1 = alloc_phi(ep->active, src1, size);
+	phi1 = alloc_phi(ep->active, src1, expr->ctype);
 	add_branch(ep, expr, src1, merge, bb_false);
 
 	set_activeblock(ep, bb_false);
 	src2 = linearize_expression(ep, expr_false);
-	phi2 = alloc_phi(ep->active, src2, size);
+	phi2 = alloc_phi(ep->active, src2, expr->ctype);
 	set_activeblock(ep, merge);
 
 	return add_join_conditional(ep, expr, phi1, phi2);
@@ -1410,7 +1409,6 @@ static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *
 	pseudo_t src1, src2;
 	pseudo_t phi1, phi2;
 	struct basic_block *bb_true, *bb_false, *merge;
-	int size = type_size(expr->ctype);
 
 	if (!cond || !expr_true || !expr_false || !ep->active)
 		return VOID;
@@ -1422,12 +1420,12 @@ static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *
 
 	set_activeblock(ep, bb_true);
 	src1 = linearize_expression(ep, expr_true);
-	phi1 = alloc_phi(ep->active, src1, size);
+	phi1 = alloc_phi(ep->active, src1, expr->ctype);
 	add_goto(ep, merge); 
 
 	set_activeblock(ep, bb_false);
 	src2 = linearize_expression(ep, expr_false);
-	phi2 = alloc_phi(ep->active, src2, size);
+	phi2 = alloc_phi(ep->active, src2, expr->ctype);
 	set_activeblock(ep, merge);
 
 	return add_join_conditional(ep, expr, phi1, phi2);
@@ -1926,7 +1924,7 @@ static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
 			phi_node->bb = bb_return;
 			add_instruction(&bb_return->insns, phi_node);
 		}
-		phi = alloc_phi(active, src, type_size(expr->ctype));
+		phi = alloc_phi(active, src, expr->ctype);
 		phi->ident = &return_ident;
 		use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
 	}
diff --git a/linearize.h b/linearize.h
index bac82d7ff..c03940eea 100644
--- a/linearize.h
+++ b/linearize.h
@@ -331,7 +331,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);
 
-pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size);
+pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
 pseudo_t alloc_pseudo(struct instruction *def);
 pseudo_t value_pseudo(long long val);
 
-- 
2.14.0

[PATCH 03/29] fix test case kill-phi-ttsb

[Luc Van Oostenryck]

The functon used in te test case has a return type of 'int'
but has nothing to return.

This was not diagnosticated.

Fix this by using the correct return type: 'void'

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/kill-phi-ttsbb.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/validation/kill-phi-ttsbb.c b/validation/kill-phi-ttsbb.c
index 178a65d19..7fea30bfd 100644
--- a/validation/kill-phi-ttsbb.c
+++ b/validation/kill-phi-ttsbb.c
@@ -1,7 +1,7 @@
 int def(void);
 void use(int);
 
-static int foo(int a, int b)
+static void foo(int a, int b)
 {
 	int c;
 
-- 
2.14.0

[PATCH 04/29] add test case for incomplete type

[Luc Van Oostenryck]

Add a test case for the diagnostic of returning an
incomplete type.

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

diff --git a/validation/incomplete-struct.c b/validation/incomplete-struct.c
new file mode 100644
index 000000000..f9429f33a
--- /dev/null
+++ b/validation/incomplete-struct.c
@@ -0,0 +1,23 @@
+struct s;
+
+void foo(struct s s)
+{
+}
+
+struct s bar(void)
+{
+	struct s s;
+	return s;
+}
+
+/*
+ * check-name: incomplete struct
+ * check-command: sparse -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-error-start
+incomplete-struct.c:3:19: error: parameter 's' has incomplete type
+incomplete-struct.c:7:10: error: return type is incomplete
+incomplete-struct.c:9:11: error: 's' has incompelete type
+ * check-error-end
+ */
-- 
2.14.0

[PATCH 05/29] add test case for bad return type

[Luc Van Oostenryck]

add test cases for the diagnostic of:
- void function returning an integer
- int function returning with a bare 'return'

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

diff --git a/validation/bad-return-type.c b/validation/bad-return-type.c
new file mode 100644
index 000000000..0f3b3f516
--- /dev/null
+++ b/validation/bad-return-type.c
@@ -0,0 +1,19 @@
+void foo(int a)
+{
+	return a;
+}
+
+int bar(void)
+{
+	return;
+}
+
+/*
+ * check-name: bad return type
+ * check-command: sparse -Wno-decl $file
+ *
+ * check-error-start
+bad-return-type.c:3:16: error: return expression in void function
+bad-return-type.c:8:9: error: return with no return value
+ * check-error-end
+ */
-- 
2.14.0

[PATCH 06/29] topasm: top-level asm is special

[Luc Van Oostenryck]

Top-level asm is parsed as a fake anonymous function.

Obviously it also doesn't have a return type and such
and this may complicate things if we continue to treat it
as a function.

Avoid potential problems by special casing it and returning
early in linearize_fn().

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

diff --git a/linearize.c b/linearize.c
index e3d234e7e..298991dcd 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2200,6 +2200,11 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	add_one_insn(ep, entry);
 	ep->entry = entry;
 
+	if (!sym->ident) {	// top-level asm
+		linearize_statement(ep, base_type->stmt);
+		return ep;
+	}
+
 	concat_symbol_list(base_type->arguments, &ep->syms);
 
 	/* FIXME!! We should do something else about varargs.. */
-- 
2.14.0

[PATCH 07/29] ret-void: return nothing only for void functions

[Luc Van Oostenryck]

Only void functions should return nothing.
Others functions should return something and if not
we want to be able to emit a diagnostic.

Fix this by testing the return type instead of the size
of the return type.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/linearize.c b/linearize.c
index 298991dcd..69e4f3e8f 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2218,7 +2218,7 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 		struct symbol *ret_type = base_type->ctype.base_type;
 		struct instruction *insn = alloc_typed_instruction(OP_RET, ret_type);
 
-		if (type_size(ret_type) > 0)
+		if (!is_void_type(ret_type))
 			use_pseudo(insn, result, &insn->src);
 		add_one_insn(ep, insn);
 	}
-- 
2.14.0

[PATCH 08/29] small code reorg of add_store()

[Luc Van Oostenryck]

No functional changes here. Just prepare for coming changes.

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

diff --git a/linearize.c b/linearize.c
index 69e4f3e8f..3a1bc74ed 100644
--- a/linearize.c
+++ b/linearize.c
@@ -930,14 +930,16 @@ static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
 static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
 {
 	struct basic_block *bb = ep->active;
+	struct instruction *store;
 
-	if (bb_reachable(bb)) {
-		struct instruction *store = alloc_typed_instruction(OP_STORE, ad->source_type);
-		store->offset = ad->offset;
-		use_pseudo(store, value, &store->target);
-		use_pseudo(store, ad->address, &store->src);
-		add_one_insn(ep, store);
-	}
+	if (!bb)
+		return;
+
+	store = alloc_typed_instruction(OP_STORE, ad->source_type);
+	store->offset = ad->offset;
+	use_pseudo(store, value, &store->target);
+	use_pseudo(store, ad->address, &store->src);
+	add_one_insn(ep, store);
 }
 
 static pseudo_t linearize_store_gen(struct entrypoint *ep,
-- 
2.14.0

[PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

Here by 'simple' we really mean 'worth of putting in a register'.

We select all scalar types as well as struct and unions with a
size not bigger than a long (register).

Global and static variables, variables which address have been
taken and volatiles variables are never selected.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 symbol.h | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/symbol.h b/symbol.h
index 327449611..3f075c5bc 100644
--- a/symbol.h
+++ b/symbol.h
@@ -407,6 +407,39 @@ static inline int is_scalar_type(struct symbol *type)
 	return 0;
 }
 
+static inline int is_simple_type(struct symbol *type)
+{
+	if (type->type == SYM_NODE)
+		type = type->ctype.base_type;
+	switch (type->type) {
+	case SYM_ENUM:
+	case SYM_BITFIELD:
+	case SYM_PTR:
+	case SYM_RESTRICT:	// OK, always integer types
+		return 1;
+	case SYM_STRUCT:
+	case SYM_UNION:
+		return type->bit_size <= long_ctype.bit_size;
+	default:
+		break;
+	}
+	if (type->ctype.base_type == &int_type)
+		return 1;
+	if (type->ctype.base_type == &fp_type)
+		return 1;
+	return 0;
+}
+
+static inline int is_simple_var(struct symbol *var)
+{
+	if (!is_simple_type(var))
+		return 0;
+#define	MOD_NONREG	(MOD_STATIC|MOD_NONLOCAL|MOD_ADDRESSABLE|MOD_VOLATILE)
+	if (var->ctype.modifiers & MOD_NONREG)
+		return 0;
+	return 1;
+}
+
 static inline int is_function(struct symbol *type)
 {
 	return type && type->type == SYM_FN;
-- 
2.14.0

[PATCH 10/29] add helper imple_access() to test if an access is "simple"

[Luc Van Oostenryck]

This helper simply check if an access is to a simple variable
as defined by is_simple_var().

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

diff --git a/linearize.c b/linearize.c
index 3a1bc74ed..190c47241 100644
--- a/linearize.c
+++ b/linearize.c
@@ -912,6 +912,19 @@ static int linearize_address_gen(struct entrypoint *ep,
 	return 0;
 }
 
+static inline struct symbol *simple_access(struct access_data *ad)
+{
+	pseudo_t addr = ad->address;
+	struct symbol *sym;
+
+	if (addr->type != PSEUDO_SYM)
+		return NULL;
+	sym = addr->sym;
+	if (!is_simple_var(sym))
+		return NULL;
+	return sym;
+}
+
 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
 {
 	struct instruction *insn;
-- 
2.14.0

[PATCH 11/29] add PSEUDO_UNDEF

[Luc Van Oostenryck]

Processing in the middle-end are much easier if undefined values
have been clearly identified. Once done, we can then make
choices like:
- always initialize them to zero
- allow arbitraly simplification,
- ...

Prepare for this by declaring a new type of pseudo: PSEUDO_UNDEF
somewhat similar to PSEUDO_VOID.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c   | 2 ++
 linearize.h   | 3 ++-
 sparse-llvm.c | 4 ++++
 3 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/linearize.c b/linearize.c
index 190c47241..9ec65079a 100644
--- a/linearize.c
+++ b/linearize.c
@@ -155,6 +155,8 @@ const char *show_pseudo(pseudo_t pseudo)
 		if (pseudo->ident)
 			sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
 		break;
+	case PSEUDO_UNDEF:
+		return "UNDEF";
 	default:
 		snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
 	}
diff --git a/linearize.h b/linearize.h
index c03940eea..54fcf2a46 100644
--- a/linearize.h
+++ b/linearize.h
@@ -21,6 +21,7 @@ DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
 
 enum pseudo_type {
 	PSEUDO_VOID,
+	PSEUDO_UNDEF,
 	PSEUDO_REG,
 	PSEUDO_SYM,
 	PSEUDO_VAL,
@@ -290,7 +291,7 @@ static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_u
 
 static inline int has_use_list(pseudo_t p)
 {
-	return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_VAL);
+	return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_UNDEF && p->type != PSEUDO_VAL);
 }
 
 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
diff --git a/sparse-llvm.c b/sparse-llvm.c
index 29fb65f15..f8d48d264 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -289,6 +289,7 @@ static void pseudo_name(pseudo_t pseudo, char *buf)
 		assert(0);
 		break;
 	case PSEUDO_VAL:
+	case PSEUDO_UNDEF:
 		assert(0);
 		break;
 	case PSEUDO_ARG: {
@@ -372,6 +373,9 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *ins
 	case PSEUDO_VOID:
 		result = NULL;
 		break;
+	case PSEUDO_UNDEF:
+		result = LLVMGetUndef(symbol_type(fn->module, insn->type));
+		break;
 	default:
 		assert(0);
 	}
-- 
2.14.0

[PATCH 12/29] add undef_pseudo()

[Luc Van Oostenryck]

This helper simply create a pseudo of type PSEUDO_UNDEF.

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

diff --git a/linearize.c b/linearize.c
index 9ec65079a..3d14892cd 100644
--- a/linearize.c
+++ b/linearize.c
@@ -823,6 +823,13 @@ static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
 	return pseudo;
 }
 
+pseudo_t undef_pseudo(void)
+{
+	pseudo_t pseudo = __alloc_pseudo(0);
+	pseudo->type = PSEUDO_UNDEF;
+	return pseudo;
+}
+
 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
 {
 	struct instruction *insn;
diff --git a/linearize.h b/linearize.h
index 54fcf2a46..060d5f327 100644
--- a/linearize.h
+++ b/linearize.h
@@ -335,6 +335,7 @@ extern void insert_branch(struct basic_block *bb, struct instruction *br, struct
 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
 pseudo_t alloc_pseudo(struct instruction *def);
 pseudo_t value_pseudo(long long val);
+pseudo_t undef_pseudo(void);
 
 struct entrypoint *linearize_symbol(struct symbol *sym);
 int unssa(struct entrypoint *ep);
-- 
2.14.0

[PATCH 13/29] add insert_phi_node()

[Luc Van Oostenryck]

This helper is used later during the SSA construction and is,
as its name suggest, used to insert phi-nodes in the
instruction stream.

More exactly, the phi-node will be put at the begining of the
specified BB, just after the others phi-nodes but before
any other instructions.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 22 ++++++++++++++++++++++
 linearize.h |  1 +
 2 files changed, 23 insertions(+)

diff --git a/linearize.c b/linearize.c
index 3d14892cd..0af92a08e 100644
--- a/linearize.c
+++ b/linearize.c
@@ -852,6 +852,28 @@ pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *t
 	return phi;
 }
 
+pseudo_t insert_phi_node(struct basic_block *bb, struct symbol *type)
+{
+	struct instruction *phi_node = alloc_typed_instruction(OP_PHI, type);
+	struct instruction *insn;
+	pseudo_t phi;
+
+	phi = alloc_pseudo(phi_node);
+	phi_node->target = phi;
+	phi_node->bb = bb;
+
+	FOR_EACH_PTR(bb->insns, insn) {
+		enum opcode op = insn->opcode;
+		if (op == OP_ENTRY || op == OP_PHI)
+			continue;
+		INSERT_CURRENT(phi_node, insn);
+		return phi;
+	} END_FOR_EACH_PTR(insn);
+
+	add_instruction(&bb->insns, phi_node);
+	return phi;
+}
+
 /*
  * We carry the "access_data" structure around for any accesses,
  * which simplifies things a lot. It contains all the access
diff --git a/linearize.h b/linearize.h
index 060d5f327..a67f5b3e7 100644
--- a/linearize.h
+++ b/linearize.h
@@ -332,6 +332,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);
 
+pseudo_t insert_phi_node(struct basic_block *bb, struct symbol *type);
 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
 pseudo_t alloc_pseudo(struct instruction *def);
 pseudo_t value_pseudo(long long val);
-- 
2.14.0

[PATCH 14/29] extract alloc_phisrc() from alloc_phi()

[Luc Van Oostenryck]

This give us:
- a clearer name (than alloc_phi())
- more flexibility when we need the instruction and not the pseudo.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 26 ++++++++++++++++----------
 linearize.h |  1 +
 2 files changed, 17 insertions(+), 10 deletions(-)

diff --git a/linearize.c b/linearize.c
index 0af92a08e..1630810d4 100644
--- a/linearize.c
+++ b/linearize.c
@@ -830,26 +830,32 @@ pseudo_t undef_pseudo(void)
 	return pseudo;
 }
 
-pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
+struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type)
 {
-	struct instruction *insn;
-	pseudo_t phi;
+	struct instruction *insn = alloc_typed_instruction(OP_PHISOURCE, type);
+	pseudo_t phi = __alloc_pseudo(0);
 	static int nr = 0;
 
-	if (!source)
-		return VOID;
-
-	insn = alloc_typed_instruction(OP_PHISOURCE, type);
-	phi = __alloc_pseudo(0);
 	phi->type = PSEUDO_PHI;
 	phi->nr = ++nr;
 	phi->def = insn;
 
 	use_pseudo(insn, pseudo, &insn->phi_src);
-	insn->bb = source;
 	insn->target = phi;
+	return insn;
+}
+
+pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
+{
+	struct instruction *insn;
+
+	if (!source)
+		return VOID;
+
+	insn = alloc_phisrc(pseudo, type);
+	insn->bb = source;
 	add_instruction(&source->insns, insn);
-	return phi;
+	return insn->target;
 }
 
 pseudo_t insert_phi_node(struct basic_block *bb, struct symbol *type)
diff --git a/linearize.h b/linearize.h
index a67f5b3e7..a550035d3 100644
--- a/linearize.h
+++ b/linearize.h
@@ -332,6 +332,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);
 
+struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type);
 pseudo_t insert_phi_node(struct basic_block *bb, struct symbol *type);
 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type);
 pseudo_t alloc_pseudo(struct instruction *def);
-- 
2.14.0

[PATCH 15/29] add remove_use()

[Luc Van Oostenryck]

Add an helper to remove the usage of a pseudo, like kill_use()
do but unlike kill_use(), without trying to kill (recursively!)
the defining instruction if the usage drop to zero.

It will be used during SSA construction, when it is not yet safe
to kill instructions. If the usage drop to zero, nothing special
is done, the instruaction becomes dead and will be eliminated
later.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.h     |  1 +
 simplify.c | 13 +++++++++++++
 2 files changed, 14 insertions(+)

diff --git a/flow.h b/flow.h
index b592ad4d3..3133245e5 100644
--- a/flow.h
+++ b/flow.h
@@ -24,6 +24,7 @@ extern int simplify_instruction(struct instruction *);
 
 extern void kill_bb(struct basic_block *);
 extern void kill_use(pseudo_t *);
+extern void remove_use(pseudo_t *);
 extern void kill_unreachable_bbs(struct entrypoint *ep);
 
 extern void kill_insn(struct instruction *, int force);
diff --git a/simplify.c b/simplify.c
index 2bc86f53e..d007bee02 100644
--- a/simplify.c
+++ b/simplify.c
@@ -202,6 +202,19 @@ void kill_use(pseudo_t *usep)
 	}
 }
 
+/*
+ * Like kill_use() but do not recursively kill instructions
+ * that become without users.
+ */
+void remove_use(pseudo_t *usep)
+{
+	pseudo_t p = *usep;
+	*usep = VOID;
+	if (has_use_list(p)) {
+		delete_pseudo_user_list_entry(&p->users, usep, 1);
+	}
+}
+
 static void kill_use_list(struct pseudo_list *list)
 {
 	pseudo_t p;
-- 
2.14.0

[PATCH 16/29] ptrmap: add missing #include "compat.h"

[Luc Van Oostenryck]

"allocate.h" need to include "compat.h" for the definition of
	CHUNK

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 allocate.h | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/allocate.h b/allocate.h
index 64bb6dd64..6a57ed26c 100644
--- a/allocate.h
+++ b/allocate.h
@@ -1,6 +1,8 @@
 #ifndef ALLOCATE_H
 #define ALLOCATE_H
 
+#include "compat.h"
+
 struct allocation_blob {
 	struct allocation_blob *next;
 	unsigned int left, offset;
-- 
2.14.0

[PATCH 17/29] ptrmap: core implementation

[Luc Van Oostenryck]

Sparse currently has a memory efficient implementation for lists
of pointers to some objects.

These are used for 2 different purposes:
- either for a simple set of objects
- either as a sequence (ordered) of objects.

Incoming develpment has another need:
- a map of object (aka: dictionnary, table, ...)
where the only needed operations are:
- add a new element (with it's key)
- replace the element corresponding to a key)
- lookup an element via it's key

The implementation done in this patch is a very simple one
based on list of blocks of key-value pairs.

The idea being to later switch to a dynamic structure using
a hash-table as soon as the number of element reach some threshold.
However, these hash-table are only needed for some huge
and artificial input files.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Makefile |  1 +
 ptrmap.c | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ptrmap.h | 12 ++++++++++
 3 files changed, 97 insertions(+)
 create mode 100644 ptrmap.c
 create mode 100644 ptrmap.h

diff --git a/Makefile b/Makefile
index 48e1f508f..762aee505 100644
--- a/Makefile
+++ b/Makefile
@@ -117,6 +117,7 @@ LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
 	  expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \
 	  char.o sort.o allocate.o compat-$(OS).o ptrlist.o \
 	  builtin.o \
+	  ptrmap.o \
 	  stats.o \
 	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
 
diff --git a/ptrmap.c b/ptrmap.c
new file mode 100644
index 000000000..2a08380c9
--- /dev/null
+++ b/ptrmap.c
@@ -0,0 +1,84 @@
+#include "ptrmap.h"
+#include "allocate.h"
+#include <stddef.h>
+
+#define	MAP_NR	7
+
+struct ptrpair {
+	void *key;
+	void *val;
+};
+struct ptrmap {
+	struct ptrmap *next;
+	int nr;
+	struct ptrpair pairs[MAP_NR];
+};
+
+DECLARE_ALLOCATOR(ptrmap);
+ALLOCATOR(ptrmap, "ptrmap");
+
+void __ptrmap_add(struct ptrmap **mapp, void *key, void *val)
+{
+	struct ptrmap *head = *mapp;
+	struct ptrmap *newmap;
+	struct ptrmap *map;
+	struct ptrpair *pair;
+	int nr;
+
+	if ((map = head)) {
+		struct ptrmap *next = map->next;
+		if (next)		// head is full
+			map = next;
+		if ((nr = map->nr) < MAP_NR)
+			goto oldmap;
+	}
+
+	// need a new block
+	newmap = __alloc_ptrmap(0);
+	if (!head) {
+		*mapp = newmap;
+	} else {
+		newmap->next = head->next;
+		head->next = newmap;
+	}
+	map = newmap;
+	nr = 0;
+
+oldmap:
+	pair = &map->pairs[nr];
+	pair->key = key;
+	pair->val = val;
+	map->nr = ++nr;
+}
+
+void *__ptrmap_lookup(struct ptrmap *map, void *key)
+{
+	for (; map; map = map->next) {
+		int i, n = map->nr;
+		for (i = 0; i < n; i++) {
+			struct ptrpair *pair = &map->pairs[i];
+			if (pair->key == key)
+				return pair->val;
+		}
+	}
+	return NULL;
+}
+
+void __ptrmap_update(struct ptrmap **mapp, void *key, void *val)
+{
+	struct ptrmap *map = *mapp;
+
+	for (; map; map = map->next) {
+		int i, n = map->nr;
+		for (i = 0; i < n; i++) {
+			struct ptrpair *pair = &map->pairs[i];
+			if (pair->key == key) {
+				if (pair->val != val)
+					pair->val = val;
+				return;
+			}
+		}
+	}
+
+	__ptrmap_add(mapp, key, val);
+}
diff --git a/ptrmap.h b/ptrmap.h
new file mode 100644
index 000000000..070db15e2
--- /dev/null
+++ b/ptrmap.h
@@ -0,0 +1,12 @@
+#ifndef PTRMAP_H
+#define PTRMAP_H
+
+struct ptrmap;
+
+
+/* ptrmap.c */
+void __ptrmap_add(struct ptrmap **mapp, void *key, void *val);
+void __ptrmap_update(struct ptrmap **mapp, void *key, void *val);
+void *__ptrmap_lookup(struct ptrmap *map, void *key);
+
+#endif
-- 
2.14.0

[PATCH 18/29] ptrmap: add type-safe interface

[Luc Van Oostenryck]

Add the external API for the ptrmap implementation.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ptrmap.h | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/ptrmap.h b/ptrmap.h
index 070db15e2..cbbb61da9 100644
--- a/ptrmap.h
+++ b/ptrmap.h
@@ -3,6 +3,22 @@
 
 struct ptrmap;
 
+#define DECLARE_PTRMAP(name, ktype, vtype)				\
+	struct name ## _pair { ktype key; vtype val; };			\
+	struct name { struct name ## _pair block[1]; };			\
+	static inline							\
+	void name##_add(struct name **map, ktype k, vtype v) {		\
+		__ptrmap_add((struct ptrmap**)map, k, v);		\
+	}								\
+	static inline							\
+	void name##_update(struct name **map, ktype k, vtype v) {	\
+		__ptrmap_update((struct ptrmap**)map, k, v);		\
+	}								\
+	static inline							\
+	vtype name##_lookup(struct name *map, ktype k) {		\
+		vtype val = __ptrmap_lookup((struct ptrmap*)map, k);	\
+		return val;						\
+	}								\
 
 /* ptrmap.c */
 void __ptrmap_add(struct ptrmap **mapp, void *key, void *val);
-- 
2.14.0

[PATCH 19/29] sssa: add Simple SSA interfaces

[Luc Van Oostenryck]

The incoming new method to construct the SSA form that
can be done during the linearization.
It needs only and a small API:
- store_var()
- load_var()
- seal_bb()

These calls can easily be inserted into the current linearization.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ssa.h | 11 +++++++++++
 1 file changed, 11 insertions(+)
 create mode 100644 ssa.h

diff --git a/ssa.h b/ssa.h
new file mode 100644
index 000000000..484c2b418
--- /dev/null
+++ b/ssa.h
@@ -0,0 +1,11 @@
+#ifndef	SSA_H
+#define	SSA_H
+
+#include "linearize.h"
+
+/* ssa.c */
+pseudo_t load_var(struct basic_block *bb, struct symbol *var);
+void store_var(struct basic_block *bb, struct symbol *var, pseudo_t val);
+void seal_bb(struct basic_block *bb);
+
+#endif
-- 
2.14.0

[PATCH 20/29] sssa: add needed new members

[Luc Van Oostenryck]

The incoming new method to construct the SSA needs
a few new members for pseudos, basic_blocks & symbols.

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

diff --git a/linearize.h b/linearize.h
index a550035d3..30f34aa8f 100644
--- a/linearize.h
+++ b/linearize.h
@@ -6,6 +6,7 @@
 #include "token.h"
 #include "parse.h"
 #include "symbol.h"
+#include "ptrmap.h"
 
 struct instruction;
 DECLARE_PTR_LIST(pseudo_ptr_list, pseudo_t);
@@ -18,6 +19,7 @@ struct pseudo_user {
 DECLARE_ALLOCATOR(pseudo_user);
 DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
 
+DECLARE_PTRMAP(phi_map, struct basic_block *, pseudo_t);
 
 enum pseudo_type {
 	PSEUDO_VOID,
@@ -90,6 +92,7 @@ struct instruction {
 		};
 		struct /* phi_node */ {
 			struct pseudo_list *phi_list;
+			struct symbol *var;		/* SSSA only */
 		};
 		struct /* phi source */ {
 			pseudo_t phi_src;
@@ -231,7 +234,14 @@ struct basic_block {
 	struct basic_block_list *parents; /* sources */
 	struct basic_block_list *children; /* destinations */
 	struct instruction_list *insns;	/* Linear list of instructions */
-	struct pseudo_list *needs, *defines;
+	union {
+		struct {		// SSA construction
+			unsigned int sealed:1;
+		};
+		struct {		// liveness
+			struct pseudo_list *needs, *defines;
+		};
+	};
 	union {
 		unsigned int nr;	/* unique id for label's names */
 		void *priv;
diff --git a/symbol.h b/symbol.h
index 3f075c5bc..05a0d801c 100644
--- a/symbol.h
+++ b/symbol.h
@@ -184,6 +184,7 @@ struct symbol {
 			struct expression *initializer;
 			struct entrypoint *ep;
 			long long value;		/* Initial value */
+			struct phi_map *phi_map;
 			struct symbol *definition;
 		};
 	};
-- 
2.14.0

[PATCH 21/29] sssa: add basic implementation

[Luc Van Oostenryck]

This a direct implementation of the pseudo-code for the
new SSA construction method a described in it's paper:

  "Simple and Efficient Construction of Static Single Assignment Form"
	by Matthias Braun, Sebastian Buchwald, Sebastian Hack,
	   Roland Leissa, Christoph Mallon and Andreas Zwinkau.

[cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Makefile |  1 +
 ssa.c    | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 99 insertions(+)
 create mode 100644 ssa.c

diff --git a/Makefile b/Makefile
index 762aee505..bcd7ab7da 100644
--- a/Makefile
+++ b/Makefile
@@ -118,6 +118,7 @@ LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
 	  char.o sort.o allocate.o compat-$(OS).o ptrlist.o \
 	  builtin.o \
 	  ptrmap.o \
+	  ssa.o \
 	  stats.o \
 	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
 
diff --git a/ssa.c b/ssa.c
new file mode 100644
index 000000000..32e440669
--- /dev/null
+++ b/ssa.c
@@ -0,0 +1,98 @@
+/*
+ * This is an implementation of the SSA construction algorithm:
+ *	"Simple and Efficient Construction of Static Single Assignment Form"
+ * by Matthias Braun, Sebastian Buchwald, Sebastian Hack, Roland Leissa,
+ *    Christoph Mallon and Andreas Zwinkau.
+ * cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf
+ */
+
+#include "ssa.h"
+#include "linearize.h"
+#include "flow.h"
+#include "lib.h"
+#include <assert.h>
+
+
+// FIXME: -> common file
+static void append_instruction(struct basic_block *bb, struct instruction *insn)
+{
+	struct instruction *br = delete_last_instruction(&bb->insns);
+	insn->bb = bb;
+	add_instruction(&bb->insns, insn);
+	add_instruction(&bb->insns, br);
+}
+
+static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi)
+{
+	struct instruction *node = phi->def;
+	struct basic_block *parent;
+
+	FOR_EACH_PTR(node->bb->parents, parent) {
+		pseudo_t val = load_var(parent, var);
+		struct instruction *phisrc = alloc_phisrc(val, var);
+		pseudo_t src = phisrc->target;
+		append_instruction(parent, phisrc);
+		use_pseudo(node, src, add_pseudo(&node->phi_list, src));
+	} END_FOR_EACH_PTR(parent);
+	return phi;
+}
+
+static pseudo_t load_var_parents(struct basic_block *bb, struct symbol *var)
+{
+	pseudo_t val;
+
+	if (!bb->sealed) {	// incomplete CFG
+		val = insert_phi_node(bb, var);
+		val->def->var = var;
+		goto out;
+	}
+
+	switch (bb_list_size(bb->parents)) {
+	case 0:	// never defined
+		val = undef_pseudo();
+		break;
+	case 1: // no phi needed
+		val = load_var(first_basic_block(bb->parents), var);
+		break;
+	default:
+		val = insert_phi_node(bb, var);
+		store_var(bb, var, val);
+		val = add_phi_operand(var, val);
+	}
+
+out:
+	store_var(bb, var, val);
+	return val;
+}
+
+pseudo_t load_var(struct basic_block *bb, struct symbol *var)
+{
+	pseudo_t val = phi_map_lookup(var->phi_map, bb);
+	if (!val)
+		val = load_var_parents(bb, var);
+	return val;
+}
+
+void store_var(struct basic_block *bb, struct symbol *var, pseudo_t val)
+{
+	phi_map_update(&var->phi_map, bb, val);
+}
+
+void seal_bb(struct basic_block *bb)
+{
+	struct instruction *insn;
+	if (bb->sealed)
+		return;
+	FOR_EACH_PTR(bb->insns, insn) {
+		struct symbol *var;
+		if (!insn->bb)
+			continue;
+		if (insn->opcode != OP_PHI)
+			break;
+		var = insn->var;
+		assert(var);
+		insn->var = NULL;
+		add_phi_operand(var, insn->target);
+	} END_FOR_EACH_PTR(insn);
+	bb->sealed = 1;
+}
-- 
2.14.0

[PATCH 22/29] sssa: add seal_gotos() needed to seal BBs targeted by gotos

[Luc Van Oostenryck]

The paper for the new SSA construction nicely leave the question
of GOTOs as en exercice for the student.

This patch is such an exercice.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h |  1 +
 ssa.c       | 20 +++++++++++++++++++-
 ssa.h       |  1 +
 3 files changed, 21 insertions(+), 1 deletion(-)

diff --git a/linearize.h b/linearize.h
index 30f34aa8f..eba0323d0 100644
--- a/linearize.h
+++ b/linearize.h
@@ -237,6 +237,7 @@ struct basic_block {
 	union {
 		struct {		// SSA construction
 			unsigned int sealed:1;
+			unsigned int unsealable:1;
 		};
 		struct {		// liveness
 			struct pseudo_list *needs, *defines;
diff --git a/ssa.c b/ssa.c
index 32e440669..d8fa32d93 100644
--- a/ssa.c
+++ b/ssa.c
@@ -81,7 +81,7 @@ void store_var(struct basic_block *bb, struct symbol *var, pseudo_t val)
 void seal_bb(struct basic_block *bb)
 {
 	struct instruction *insn;
-	if (bb->sealed)
+	if (bb->sealed || bb->unsealable)
 		return;
 	FOR_EACH_PTR(bb->insns, insn) {
 		struct symbol *var;
@@ -96,3 +96,21 @@ void seal_bb(struct basic_block *bb)
 	} END_FOR_EACH_PTR(insn);
 	bb->sealed = 1;
 }
+
+void seal_gotos(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		if (bb->sealed)
+			continue;
+		if (bb->unsealable)
+			bb->unsealable = 0;
+		seal_bb(bb);
+	} END_FOR_EACH_PTR(bb);
+
+	// cleanup these fields as they are aliased to ::needs & ::defines
+	FOR_EACH_PTR(ep->bbs, bb) {
+		bb->sealed = bb->unsealable = 0;
+	} END_FOR_EACH_PTR(bb);
+}
diff --git a/ssa.h b/ssa.h
index 484c2b418..e88b857b5 100644
--- a/ssa.h
+++ b/ssa.h
@@ -7,5 +7,6 @@
 pseudo_t load_var(struct basic_block *bb, struct symbol *var);
 void store_var(struct basic_block *bb, struct symbol *var, pseudo_t val);
 void seal_bb(struct basic_block *bb);
+void seal_gotos(struct entrypoint *ep);
 
 #endif
-- 
2.14.0

[PATCH 23/29] sssa: set var's ident

[Luc Van Oostenryck]

With this new method it's easier to assign an indent
to each phi-nodes.

THis patch has to simply assign the variable's ident to
the corresponding phi-node's pseudo.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ssa.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/ssa.c b/ssa.c
index d8fa32d93..e50fae0cc 100644
--- a/ssa.c
+++ b/ssa.c
@@ -33,6 +33,7 @@ static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi)
 		pseudo_t src = phisrc->target;
 		append_instruction(parent, phisrc);
 		use_pseudo(node, src, add_pseudo(&node->phi_list, src));
+		src->ident = var->ident;
 	} END_FOR_EACH_PTR(parent);
 	return phi;
 }
@@ -44,6 +45,7 @@ static pseudo_t load_var_parents(struct basic_block *bb, struct symbol *var)
 	if (!bb->sealed) {	// incomplete CFG
 		val = insert_phi_node(bb, var);
 		val->def->var = var;
+		val->ident = var->ident;
 		goto out;
 	}
 
@@ -56,6 +58,7 @@ static pseudo_t load_var_parents(struct basic_block *bb, struct symbol *var)
 		break;
 	default:
 		val = insert_phi_node(bb, var);
+		val->ident = var->ident;
 		store_var(bb, var, val);
 		val = add_phi_operand(var, val);
 	}
-- 
2.14.0

[PATCH 24/29] sssa: add PSEUDO_INDIR

[Luc Van Oostenryck]

Simplification of trivial pseudos require to replace
a pseudo for another in all ptrmap. Since this could
be an annoying and relatively costly operation
if effectively done by looking after each pseudos,
this patch introduce a new type of pseudo used as a
a sort of a symlink for another one: PSEUDO_INDIR.

So the processing is almost for free and this indirection
has just to be done when looking after the corresponding var.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c | 2 ++
 linearize.h | 2 ++
 ssa.c       | 2 ++
 3 files changed, 6 insertions(+)

diff --git a/linearize.c b/linearize.c
index 1630810d4..f47748b38 100644
--- a/linearize.c
+++ b/linearize.c
@@ -157,6 +157,8 @@ const char *show_pseudo(pseudo_t pseudo)
 		break;
 	case PSEUDO_UNDEF:
 		return "UNDEF";
+	case PSEUDO_INDIR:
+		return show_pseudo(pseudo->target);
 	default:
 		snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
 	}
diff --git a/linearize.h b/linearize.h
index eba0323d0..3fdcd487c 100644
--- a/linearize.h
+++ b/linearize.h
@@ -29,6 +29,7 @@ enum pseudo_type {
 	PSEUDO_VAL,
 	PSEUDO_ARG,
 	PSEUDO_PHI,
+	PSEUDO_INDIR,
 };
 
 struct pseudo {
@@ -40,6 +41,7 @@ struct pseudo {
 		struct symbol *sym;
 		struct instruction *def;
 		long long value;
+		pseudo_t target;
 	};
 	void *priv;
 };
diff --git a/ssa.c b/ssa.c
index e50fae0cc..10279a602 100644
--- a/ssa.c
+++ b/ssa.c
@@ -73,6 +73,8 @@ pseudo_t load_var(struct basic_block *bb, struct symbol *var)
 	pseudo_t val = phi_map_lookup(var->phi_map, bb);
 	if (!val)
 		val = load_var_parents(bb, var);
+	while (val->type == PSEUDO_INDIR)
+		val = val->target;
 	return val;
 }
 
-- 
2.14.0

[PATCH 25/29] sssa: reorg load_var()

[Luc Van Oostenryck]

No functional changes here. Only shuffling some code
arround to make the next patch more readable.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ssa.c | 25 +++++++++++++++----------
 1 file changed, 15 insertions(+), 10 deletions(-)

diff --git a/ssa.c b/ssa.c
index 10279a602..7950ffeaf 100644
--- a/ssa.c
+++ b/ssa.c
@@ -13,6 +13,9 @@
 #include <assert.h>
 
 
+static pseudo_t load_var_(struct basic_block*, struct symbol*);
+
+
 // FIXME: -> common file
 static void append_instruction(struct basic_block *bb, struct instruction *insn)
 {
@@ -28,7 +31,7 @@ static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi)
 	struct basic_block *parent;
 
 	FOR_EACH_PTR(node->bb->parents, parent) {
-		pseudo_t val = load_var(parent, var);
+		pseudo_t val = load_var_(parent, var);
 		struct instruction *phisrc = alloc_phisrc(val, var);
 		pseudo_t src = phisrc->target;
 		append_instruction(parent, phisrc);
@@ -38,9 +41,15 @@ static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi)
 	return phi;
 }
 
-static pseudo_t load_var_parents(struct basic_block *bb, struct symbol *var)
+static pseudo_t load_var_(struct basic_block *bb, struct symbol *var)
 {
-	pseudo_t val;
+	pseudo_t val = phi_map_lookup(var->phi_map, bb);
+
+	if (val) {
+		while (val->type == PSEUDO_INDIR)
+			val = val->target;
+		return val;
+	}
 
 	if (!bb->sealed) {	// incomplete CFG
 		val = insert_phi_node(bb, var);
@@ -54,7 +63,7 @@ static pseudo_t load_var_parents(struct basic_block *bb, struct symbol *var)
 		val = undef_pseudo();
 		break;
 	case 1: // no phi needed
-		val = load_var(first_basic_block(bb->parents), var);
+		val = load_var_(first_basic_block(bb->parents), var);
 		break;
 	default:
 		val = insert_phi_node(bb, var);
@@ -64,18 +73,14 @@ static pseudo_t load_var_parents(struct basic_block *bb, struct symbol *var)
 	}
 
 out:
+	assert(val->type != PSEUDO_INDIR);
 	store_var(bb, var, val);
 	return val;
 }
 
 pseudo_t load_var(struct basic_block *bb, struct symbol *var)
 {
-	pseudo_t val = phi_map_lookup(var->phi_map, bb);
-	if (!val)
-		val = load_var_parents(bb, var);
-	while (val->type == PSEUDO_INDIR)
-		val = val->target;
-	return val;
+	return load_var_(bb, var);
 }
 
 void store_var(struct basic_block *bb, struct symbol *var, pseudo_t val)
-- 
2.14.0

[PATCH 26/29] sssa: protect against unreachable loops

[Luc Van Oostenryck]

If unreachable loops are somehow presetn at the moment
we're doing a lookup things can turn into infinite loops.
Protect us agaisnt this by using the classic 'generation'
counter to detech any cycle and take the appropriate actions.

Note: reachable loops don't need this protection since
      at least one node will have more than 1 parent.
Note: how libfirm handle this? By adding keep-alive edge
      (to keep endless loops to be observable)?

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ssa.c | 24 +++++++++++++++---------
 1 file changed, 15 insertions(+), 9 deletions(-)

diff --git a/ssa.c b/ssa.c
index 7950ffeaf..9d532dbf6 100644
--- a/ssa.c
+++ b/ssa.c
@@ -13,7 +13,7 @@
 #include <assert.h>
 
 
-static pseudo_t load_var_(struct basic_block*, struct symbol*);
+static pseudo_t load_var_(struct basic_block*, struct symbol*, unsigned long);
 
 
 // FIXME: -> common file
@@ -25,13 +25,13 @@ static void append_instruction(struct basic_block *bb, struct instruction *insn)
 	add_instruction(&bb->insns, br);
 }
 
-static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi)
+static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi, unsigned long generation)
 {
 	struct instruction *node = phi->def;
 	struct basic_block *parent;
 
 	FOR_EACH_PTR(node->bb->parents, parent) {
-		pseudo_t val = load_var_(parent, var);
+		pseudo_t val = load_var_(parent, var, generation);
 		struct instruction *phisrc = alloc_phisrc(val, var);
 		pseudo_t src = phisrc->target;
 		append_instruction(parent, phisrc);
@@ -41,9 +41,10 @@ static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi)
 	return phi;
 }
 
-static pseudo_t load_var_(struct basic_block *bb, struct symbol *var)
+static pseudo_t load_var_(struct basic_block *bb, struct symbol *var, unsigned long generation)
 {
 	pseudo_t val = phi_map_lookup(var->phi_map, bb);
+	unsigned long bbgen = bb->generation;
 
 	if (val) {
 		while (val->type == PSEUDO_INDIR)
@@ -62,14 +63,19 @@ static pseudo_t load_var_(struct basic_block *bb, struct symbol *var)
 	case 0:	// never defined
 		val = undef_pseudo();
 		break;
-	case 1: // no phi needed
-		val = load_var_(first_basic_block(bb->parents), var);
+	case 1:
+		if (bbgen == generation)
+			goto cycle;
+		bb->generation = generation;
+		// no phi needed
+		val = load_var_(first_basic_block(bb->parents), var, generation);
 		break;
 	default:
+	cycle:
 		val = insert_phi_node(bb, var);
 		val->ident = var->ident;
 		store_var(bb, var, val);
-		val = add_phi_operand(var, val);
+		val = add_phi_operand(var, val, generation);
 	}
 
 out:
@@ -80,7 +86,7 @@ out:
 
 pseudo_t load_var(struct basic_block *bb, struct symbol *var)
 {
-	return load_var_(bb, var);
+	return load_var_(bb, var, ++bb_generation);
 }
 
 void store_var(struct basic_block *bb, struct symbol *var, pseudo_t val)
@@ -102,7 +108,7 @@ void seal_bb(struct basic_block *bb)
 		var = insn->var;
 		assert(var);
 		insn->var = NULL;
-		add_phi_operand(var, insn->target);
+		add_phi_operand(var, insn->target, ++bb_generation);
 	} END_FOR_EACH_PTR(insn);
 	bb->sealed = 1;
 }
-- 
2.14.0

[PATCH 27/29] sssa: remove trivial phi-nodes

[Luc Van Oostenryck]

These trivial phi-nodes have all their sources but one
which are defined by the phi-node itself . This typically
arise if a var is presetn in a loop and only set in the
loop header.

In this case, the only possible value for the phi-node and
these sources is the value of the other unique source.
These phi-nodes can this easily be replaced by this value
avoiding firther unwanted processing.

This patch remove these trivial phi-nodes in most, simple
cases.

More complex cases need more complex method to get rid of them.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 ssa.c | 87 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 87 insertions(+)

diff --git a/ssa.c b/ssa.c
index 9d532dbf6..1b7f7cda3 100644
--- a/ssa.c
+++ b/ssa.c
@@ -16,6 +16,92 @@
 static pseudo_t load_var_(struct basic_block*, struct symbol*, unsigned long);
 
 
+static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst)
+{
+	concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst);
+}
+
+/*
+ * Go through the "insn->users" list and replace them all..
+ */
+static void convert_phi(struct instruction *insn, pseudo_t src)
+{
+	pseudo_t phi = insn->target;
+	struct pseudo_user *pu;
+
+	assert(phi != src);
+	if (phi == src)
+		return;
+	FOR_EACH_PTR(phi->users, pu) {
+		pseudo_t *pp = pu->userp;
+		pseudo_t p = *pp;
+
+		if (p == VOID)
+			continue;
+		assert(p == phi);
+		if (p->def->src == phi)
+			continue;
+		*pu->userp = src;
+	} END_FOR_EACH_PTR(pu);
+	if (has_use_list(src))
+		concat_user_list(phi->users, &src->users);
+	phi->users = NULL;
+}
+
+static void kill_phi_node(struct instruction *node)
+{
+	struct pseudo_list *phi_list = node->phi_list;
+	pseudo_t phi;
+
+	node->phi_list = NULL;
+	node->bb = NULL;
+	FOR_EACH_PTR(phi_list, phi) {
+		struct instruction *phisrc;
+		if (phi == VOID)
+			continue;
+		phisrc = phi->def;
+		remove_use(&phisrc->src);
+		phisrc->bb = NULL;
+	} END_FOR_EACH_PTR(phi);
+	free_ptr_list(&node->phi_list);
+}
+
+static pseudo_t try_remove_trivial_phi(pseudo_t phi)
+{
+	struct instruction *node = phi->def;
+	pseudo_t same = NULL;
+	pseudo_t p;
+
+	if (phi == VOID)
+		return phi;
+	if (phi->type != PSEUDO_REG)
+		return phi;
+	if (node->opcode != OP_PHI)
+		return phi;
+	FOR_EACH_PTR(node->phi_list, p) {
+		pseudo_t src;
+
+		if (p == VOID)
+			continue;
+		src = p->def->src;
+		if (src == same || src == phi)
+			continue;
+		if (same)
+			return phi;
+		same = src;
+	} END_FOR_EACH_PTR(p);
+
+	if (same == NULL)
+		same = undef_pseudo();
+
+	convert_phi(node, same);
+	phi->target = same;
+	phi->type = PSEUDO_INDIR;
+	kill_phi_node(node);
+
+	return same;
+}
+
 // FIXME: -> common file
 static void append_instruction(struct basic_block *bb, struct instruction *insn)
 {
@@ -38,6 +124,7 @@ static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi, unsigned long
 		use_pseudo(node, src, add_pseudo(&node->phi_list, src));
 		src->ident = var->ident;
 	} END_FOR_EACH_PTR(parent);
+	phi = try_remove_trivial_phi(phi);
 	return phi;
 }
 
-- 
2.14.0

[PATCH 28/29] sssa: switch to the new SSA construction

[Luc Van Oostenryck]

This patch makes the needed changes in the linearization
to use the new SA construction method.

The main changes are:
- hook into add_load() & add_store() to directly get the
  variables's SSA form if the variable is 'simple enough'
- sprinkle calls to seal_bb() each time we know the current
  can't possibly have another parent. In this case the paper
  talk of the BB being 'sealed' hence the name.
- a minor simplification can be done for returns.
- labels need a bit more care
- when reaching the end f the function, we can seal all the BB
  which are the target of a goto.
- last but not least we can unhook the previous method of
  SSA construction: simplify_one_symbol().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                             |  73 +++++++++------
 validation/cast-constant-to-float.c     |   8 +-
 validation/cast-constants.c             |  40 ++++----
 validation/cast-kinds.c                 | 160 ++++++++++++++++----------------
 validation/context.c                    |   2 +-
 validation/linear/bitfield-init-zero.c  |  24 ++---
 validation/linear/struct-init-partial.c |   8 +-
 validation/loop-linearization.c         |  60 ++++++------
 validation/memops-volatile.c            |   4 +-
 validation/optim/bool-simplify.c        |  12 +--
 10 files changed, 204 insertions(+), 187 deletions(-)

diff --git a/linearize.c b/linearize.c
index f47748b38..8d907c5ca 100644
--- a/linearize.c
+++ b/linearize.c
@@ -21,6 +21,7 @@
 #include "linearize.h"
 #include "flow.h"
 #include "target.h"
+#include "ssa.h"
 
 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
@@ -722,7 +723,7 @@ static struct basic_block * add_label(struct entrypoint *ep, struct symbol *labe
 		return bb;
 	}
 	bb = ep->active;
-	if (!bb_reachable(bb) || !bb_empty(bb)) {
+	if (!bb_reachable(bb) || !bb_empty(bb) || bb->sealed) {
 		bb = alloc_basic_block(ep, label->pos);
 		set_activeblock(ep, bb);
 	}
@@ -966,9 +967,18 @@ static inline struct symbol *simple_access(struct access_data *ad)
 
 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
 {
+	struct basic_block *bb = ep->active;
 	struct instruction *insn;
+	struct symbol *var;
 	pseudo_t new;
 
+	if (!bb)
+		return VOID;
+	if ((var = simple_access(ad))) {
+		new = load_var(bb, var);
+		return new;
+	}
+
 	insn = alloc_typed_instruction(OP_LOAD, ad->source_type);
 	new = alloc_pseudo(insn);
 
@@ -983,10 +993,16 @@ static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t va
 {
 	struct basic_block *bb = ep->active;
 	struct instruction *store;
+	struct symbol *var;
 
 	if (!bb)
 		return;
 
+	if ((var = simple_access(ad))) {
+		store_var(bb, var, value);
+		return;
+	}
+
 	store = alloc_typed_instruction(OP_STORE, ad->source_type);
 	store->offset = ad->offset;
 	use_pseudo(store, value, &store->target);
@@ -1447,9 +1463,11 @@ static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expres
 	phi1 = alloc_phi(ep->active, src1, expr->ctype);
 	add_branch(ep, expr, src1, merge, bb_false);
 
+	seal_bb(bb_false);
 	set_activeblock(ep, bb_false);
 	src2 = linearize_expression(ep, expr_false);
 	phi2 = alloc_phi(ep->active, src2, expr->ctype);
+	seal_bb(merge);
 	set_activeblock(ep, merge);
 
 	return add_join_conditional(ep, expr, phi1, phi2);
@@ -1472,14 +1490,17 @@ static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *
 
 	linearize_cond_branch(ep, cond, bb_true, bb_false);
 
+	seal_bb(bb_true);
 	set_activeblock(ep, bb_true);
 	src1 = linearize_expression(ep, expr_true);
 	phi1 = alloc_phi(ep->active, src1, expr->ctype);
 	add_goto(ep, merge); 
 
+	seal_bb(bb_false);
 	set_activeblock(ep, bb_false);
 	src2 = linearize_expression(ep, expr_false);
 	phi2 = alloc_phi(ep->active, src2, expr->ctype);
+	seal_bb(merge);
 	set_activeblock(ep, merge);
 
 	return add_join_conditional(ep, expr, phi1, phi2);
@@ -1568,6 +1589,7 @@ static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expressio
 		linearize_cond_branch(ep, expr->left, bb_true, next);
 	else
 		linearize_cond_branch(ep, expr->left, next, bb_false);
+	seal_bb(next);
 	set_activeblock(ep, next);
 	linearize_cond_branch(ep, expr->right, bb_true, bb_false);
 	return VOID;
@@ -1754,17 +1776,11 @@ static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct state
 
 	if (ret) {
 		struct basic_block *bb = add_label(ep, ret);
-		struct instruction *phi_node = first_instruction(bb->insns);
 
-		if (!phi_node)
-			return pseudo;
-
-		if (pseudo_list_size(phi_node->phi_list)==1) {
-			pseudo = first_pseudo(phi_node->phi_list);
-			assert(pseudo->type == PSEUDO_PHI);
-			return pseudo->def->src1;
-		}
-		return phi_node->target;
+		seal_bb(bb);
+		pseudo = VOID;
+		if (!is_void_type(ret))
+			pseudo = load_var(bb, ret);
 	}
 
 	return pseudo;
@@ -1970,17 +1986,7 @@ static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
 	pseudo_t src = linearize_expression(ep, expr);
 	active = ep->active;
 	if (active && src != VOID) {
-		struct instruction *phi_node = first_instruction(bb_return->insns);
-		pseudo_t phi;
-		if (!phi_node) {
-			phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
-			phi_node->target = alloc_pseudo(phi_node);
-			phi_node->bb = bb_return;
-			add_instruction(&bb_return->insns, phi_node);
-		}
-		phi = alloc_phi(active, src, expr->ctype);
-		phi->ident = &return_ident;
-		use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
+		store_var(active, stmt->ret_target, src);
 	}
 	add_goto(ep, bb_return);
 	return VOID;
@@ -2028,6 +2034,7 @@ static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
 		}
 		add_multijmp(&switch_ins->multijmp_list, jmp);
 		add_bb(&bb_case->parents, active);
+		seal_bb(bb_case);
 		add_bb(&active->children, bb_case);
 	} END_FOR_EACH_PTR(sym);
 
@@ -2035,6 +2042,7 @@ static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
 
 	/* And linearize the actual statement */
 	linearize_statement(ep, stmt->switch_statement);
+	seal_bb(switch_end);
 	set_activeblock(ep, switch_end);
 
 	if (!default_case)
@@ -2044,6 +2052,7 @@ static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
 	add_multijmp(&switch_ins->multijmp_list, jmp);
 	add_bb(&default_case->parents, active);
 	add_bb(&active->children, default_case);
+	seal_bb(default_case);
 	sort_switch_cases(switch_ins);
 
 	return VOID;
@@ -2085,12 +2094,16 @@ static pseudo_t linearize_iterator(struct entrypoint *ep, struct statement *stmt
 	linearize_statement(ep, statement);
 	add_goto(ep, loop_continue);
 
+	seal_bb(loop_continue);
 	set_activeblock(ep, loop_continue);
 	linearize_statement(ep, post_statement);
 	if (!post_condition)
 		add_goto(ep, loop_top);
 	else
 		linearize_cond_branch(ep, post_condition, loop_top, loop_end);
+	seal_bb(loop_body);	// FIXME: can be early if precond
+	seal_bb(loop_top);
+	seal_bb(loop_end);
 	set_activeblock(ep, loop_end);
 
 	return VOID;
@@ -2140,7 +2153,11 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 		struct symbol *label = stmt->label_identifier;
 
 		if (label->used) {
-			add_label(ep, label);
+			bb = add_label(ep, label);
+			// label's bb must not be sealed if some
+			// goto to this label hasn't been issued yet
+			assert(!bb->sealed);
+			bb->unsealable = 1;
 		}
 		return linearize_statement(ep, stmt->label_statement);
 	}
@@ -2206,15 +2223,18 @@ pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
 
  		linearize_cond_branch(ep, cond, bb_true, bb_false);
 
+		seal_bb(bb_true);
 		set_activeblock(ep, bb_true);
  		linearize_statement(ep, stmt->if_true);
  
  		if (stmt->if_false) {
 			endif = alloc_basic_block(ep, stmt->pos);
 			add_goto(ep, endif);
+			seal_bb(bb_false);
 			set_activeblock(ep, bb_false);
  			linearize_statement(ep, stmt->if_false);
 		}
+		seal_bb(endif);
 		set_activeblock(ep, endif);
 		break;
 	}
@@ -2248,6 +2268,7 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	
 	ep->name = sym;
 	sym->ep = ep;
+	seal_bb(bb);
 	set_activeblock(ep, bb);
 
 	entry = alloc_instruction(OP_ENTRY, 0);
@@ -2268,6 +2289,7 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	} END_FOR_EACH_PTR(arg);
 
 	result = linearize_statement(ep, base_type->stmt);
+	seal_gotos(ep);
 	if (bb_reachable(ep->active) && !bb_terminated(ep->active)) {
 		struct symbol *ret_type = base_type->ctype.base_type;
 		struct instruction *insn = alloc_typed_instruction(OP_RET, ret_type);
@@ -2289,11 +2311,6 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	 */
 	kill_unreachable_bbs(ep);
 
-	/*
-	 * Turn symbols into pseudos
-	 */
-	simplify_symbol_usage(ep);
-
 repeat:
 	/*
 	 * Remove trivial instructions, and try to CSE
diff --git a/validation/cast-constant-to-float.c b/validation/cast-constant-to-float.c
index 86b7ac0f7..d4d2bc426 100644
--- a/validation/cast-constant-to-float.c
+++ b/validation/cast-constant-to-float.c
@@ -20,15 +20,15 @@ f1:
 f2:
 .L2:
 	<entry-point>
-	set.64      %r3 <- -1.000000
-	ret.64      %r3
+	set.64      %r2 <- -1.000000
+	ret.64      %r2
 
 
 f3:
 .L4:
 	<entry-point>
-	set.64      %r5 <- -1.000000
-	ret.64      %r5
+	set.64      %r3 <- -1.000000
+	ret.64      %r3
 
 
  * check-output-end
diff --git a/validation/cast-constants.c b/validation/cast-constants.c
index f47d6fd34..30350aaec 100644
--- a/validation/cast-constants.c
+++ b/validation/cast-constants.c
@@ -286,71 +286,71 @@ vptr_2_iptr:
 int_2_float:
 .L76:
 	<entry-point>
-	set.32      %r39 <- 123.000000
-	ret.32      %r39
+	set.32      %r1 <- 123.000000
+	ret.32      %r1
 
 
 uint_2_float:
 .L78:
 	<entry-point>
-	set.32      %r41 <- 123.000000
-	ret.32      %r41
+	set.32      %r2 <- 123.000000
+	ret.32      %r2
 
 
 long_2_float:
 .L80:
 	<entry-point>
-	set.32      %r43 <- 123.000000
-	ret.32      %r43
+	set.32      %r3 <- 123.000000
+	ret.32      %r3
 
 
 ulong_2_float:
 .L82:
 	<entry-point>
-	set.32      %r45 <- 123.000000
-	ret.32      %r45
+	set.32      %r4 <- 123.000000
+	ret.32      %r4
 
 
 double_2_float:
 .L84:
 	<entry-point>
-	set.32      %r47 <- 1.123000
-	ret.32      %r47
+	set.32      %r5 <- 1.123000
+	ret.32      %r5
 
 
 int_2_double:
 .L86:
 	<entry-point>
-	set.64      %r49 <- 123.000000
-	ret.64      %r49
+	set.64      %r6 <- 123.000000
+	ret.64      %r6
 
 
 uint_2_double:
 .L88:
 	<entry-point>
-	set.64      %r51 <- 123.000000
-	ret.64      %r51
+	set.64      %r7 <- 123.000000
+	ret.64      %r7
 
 
 long_2_double:
 .L90:
 	<entry-point>
-	set.64      %r53 <- 123.000000
-	ret.64      %r53
+	set.64      %r8 <- 123.000000
+	ret.64      %r8
 
 
 ulong_2_double:
 .L92:
 	<entry-point>
-	set.64      %r55 <- 123.000000
-	ret.64      %r55
+	set.64      %r9 <- 123.000000
+	ret.64      %r9
 
 
 float_2_double:
 .L94:
 	<entry-point>
-	set.64      %r57 <- 1.123000
-	ret.64      %r57
+	set.64      %r10 <- 1.123000
+	ret.64      %r10
 
 
  * check-output-end
diff --git a/validation/cast-kinds.c b/validation/cast-kinds.c
index 697f9735e..5fb55a994 100644
--- a/validation/cast-kinds.c
+++ b/validation/cast-kinds.c
@@ -64,29 +64,29 @@ uint_2_int:
 long_2_int:
 .L2:
 	<entry-point>
-	scast.32    %r5 <- (64) %arg1
-	ret.32      %r5
+	scast.32    %r2 <- (64) %arg1
+	ret.32      %r2
 
 
 ulong_2_int:
 .L4:
 	<entry-point>
-	cast.32     %r8 <- (64) %arg1
-	ret.32      %r8
+	cast.32     %r3 <- (64) %arg1
+	ret.32      %r3
 
 
 vptr_2_int:
 .L6:
 	<entry-point>
-	cast.32     %r11 <- (64) %arg1
-	ret.32      %r11
+	cast.32     %r4 <- (64) %arg1
+	ret.32      %r4
 
 
 iptr_2_int:
 .L8:
 	<entry-point>
-	cast.32     %r14 <- (64) %arg1
-	ret.32      %r14
+	cast.32     %r5 <- (64) %arg1
+	ret.32      %r5
 
 
 float_2_int:
@@ -98,8 +98,8 @@ float_2_int:
 double_2_int:
 .L12:
 	<entry-point>
-	cast.32     %r20 <- (64) %arg1
-	ret.32      %r20
+	cast.32     %r7 <- (64) %arg1
+	ret.32      %r7
 
 
 int_2_uint:
@@ -111,29 +111,29 @@ int_2_uint:
 long_2_uint:
 .L16:
 	<entry-point>
-	scast.32    %r26 <- (64) %arg1
-	ret.32      %r26
+	scast.32    %r9 <- (64) %arg1
+	ret.32      %r9
 
 
 ulong_2_uint:
 .L18:
 	<entry-point>
-	cast.32     %r29 <- (64) %arg1
-	ret.32      %r29
+	cast.32     %r10 <- (64) %arg1
+	ret.32      %r10
 
 
 vptr_2_uint:
 .L20:
 	<entry-point>
-	cast.32     %r32 <- (64) %arg1
-	ret.32      %r32
+	cast.32     %r11 <- (64) %arg1
+	ret.32      %r11
 
 
 iptr_2_uint:
 .L22:
 	<entry-point>
-	cast.32     %r35 <- (64) %arg1
-	ret.32      %r35
+	cast.32     %r12 <- (64) %arg1
+	ret.32      %r12
 
 
 float_2_uint:
@@ -145,22 +145,22 @@ float_2_uint:
 double_2_uint:
 .L26:
 	<entry-point>
-	cast.32     %r41 <- (64) %arg1
-	ret.32      %r41
+	cast.32     %r14 <- (64) %arg1
+	ret.32      %r14
 
 
 int_2_long:
 .L28:
 	<entry-point>
-	scast.64    %r44 <- (32) %arg1
-	ret.64      %r44
+	scast.64    %r15 <- (32) %arg1
+	ret.64      %r15
 
 
 uint_2_long:
 .L30:
 	<entry-point>
-	cast.64     %r47 <- (32) %arg1
-	ret.64      %r47
+	cast.64     %r16 <- (32) %arg1
+	ret.64      %r16
 
 
 ulong_2_long:
@@ -172,22 +172,22 @@ ulong_2_long:
 vptr_2_long:
 .L34:
 	<entry-point>
-	cast.64     %r53 <- (64) %arg1
-	ret.64      %r53
+	cast.64     %r18 <- (64) %arg1
+	ret.64      %r18
 
 
 iptr_2_long:
 .L36:
 	<entry-point>
-	cast.64     %r56 <- (64) %arg1
-	ret.64      %r56
+	cast.64     %r19 <- (64) %arg1
+	ret.64      %r19
 
 
 float_2_long:
 .L38:
 	<entry-point>
-	cast.64     %r59 <- (32) %arg1
-	ret.64      %r59
+	cast.64     %r20 <- (32) %arg1
+	ret.64      %r20
 
 
 double_2_long:
@@ -199,15 +199,15 @@ double_2_long:
 int_2_ulong:
 .L42:
 	<entry-point>
-	scast.64    %r65 <- (32) %arg1
-	ret.64      %r65
+	scast.64    %r22 <- (32) %arg1
+	ret.64      %r22
 
 
 uint_2_ulong:
 .L44:
 	<entry-point>
-	cast.64     %r68 <- (32) %arg1
-	ret.64      %r68
+	cast.64     %r23 <- (32) %arg1
+	ret.64      %r23
 
 
 long_2_ulong:
@@ -219,22 +219,22 @@ long_2_ulong:
 vptr_2_ulong:
 .L48:
 	<entry-point>
-	cast.64     %r74 <- (64) %arg1
-	ret.64      %r74
+	cast.64     %r25 <- (64) %arg1
+	ret.64      %r25
 
 
 iptr_2_ulong:
 .L50:
 	<entry-point>
-	cast.64     %r77 <- (64) %arg1
-	ret.64      %r77
+	cast.64     %r26 <- (64) %arg1
+	ret.64      %r26
 
 
 float_2_ulong:
 .L52:
 	<entry-point>
-	cast.64     %r80 <- (32) %arg1
-	ret.64      %r80
+	cast.64     %r27 <- (32) %arg1
+	ret.64      %r27
 
 
 double_2_ulong:
@@ -246,141 +246,141 @@ double_2_ulong:
 int_2_vptr:
 .L56:
 	<entry-point>
-	scast.64    %r86 <- (32) %arg1
-	ret.64      %r86
+	scast.64    %r29 <- (32) %arg1
+	ret.64      %r29
 
 
 uint_2_vptr:
 .L58:
 	<entry-point>
-	cast.64     %r89 <- (32) %arg1
-	ret.64      %r89
+	cast.64     %r30 <- (32) %arg1
+	ret.64      %r30
 
 
 long_2_vptr:
 .L60:
 	<entry-point>
-	scast.64    %r92 <- (64) %arg1
-	ret.64      %r92
+	scast.64    %r31 <- (64) %arg1
+	ret.64      %r31
 
 
 ulong_2_vptr:
 .L62:
 	<entry-point>
-	cast.64     %r95 <- (64) %arg1
-	ret.64      %r95
+	cast.64     %r32 <- (64) %arg1
+	ret.64      %r32
 
 
 iptr_2_vptr:
 .L64:
 	<entry-point>
-	cast.64     %r98 <- (64) %arg1
-	ret.64      %r98
+	cast.64     %r33 <- (64) %arg1
+	ret.64      %r33
 
 
 int_2_iptr:
 .L66:
 	<entry-point>
-	ptrcast.64  %r101 <- (32) %arg1
-	ret.64      %r101
+	ptrcast.64  %r34 <- (32) %arg1
+	ret.64      %r34
 
 
 uint_2_iptr:
 .L68:
 	<entry-point>
-	ptrcast.64  %r104 <- (32) %arg1
-	ret.64      %r104
+	ptrcast.64  %r35 <- (32) %arg1
+	ret.64      %r35
 
 
 long_2_iptr:
 .L70:
 	<entry-point>
-	ptrcast.64  %r107 <- (64) %arg1
-	ret.64      %r107
+	ptrcast.64  %r36 <- (64) %arg1
+	ret.64      %r36
 
 
 ulong_2_iptr:
 .L72:
 	<entry-point>
-	ptrcast.64  %r110 <- (64) %arg1
-	ret.64      %r110
+	ptrcast.64  %r37 <- (64) %arg1
+	ret.64      %r37
 
 
 vptr_2_iptr:
 .L74:
 	<entry-point>
-	ptrcast.64  %r113 <- (64) %arg1
-	ret.64      %r113
+	ptrcast.64  %r38 <- (64) %arg1
+	ret.64      %r38
 
 
 int_2_float:
 .L76:
 	<entry-point>
-	fpcast.32   %r116 <- (32) %arg1
-	ret.32      %r116
+	fpcast.32   %r39 <- (32) %arg1
+	ret.32      %r39
 
 
 uint_2_float:
 .L78:
 	<entry-point>
-	fpcast.32   %r119 <- (32) %arg1
-	ret.32      %r119
+	fpcast.32   %r40 <- (32) %arg1
+	ret.32      %r40
 
 
 long_2_float:
 .L80:
 	<entry-point>
-	fpcast.32   %r122 <- (64) %arg1
-	ret.32      %r122
+	fpcast.32   %r41 <- (64) %arg1
+	ret.32      %r41
 
 
 ulong_2_float:
 .L82:
 	<entry-point>
-	fpcast.32   %r125 <- (64) %arg1
-	ret.32      %r125
+	fpcast.32   %r42 <- (64) %arg1
+	ret.32      %r42
 
 
 double_2_float:
 .L84:
 	<entry-point>
-	fpcast.32   %r128 <- (64) %arg1
-	ret.32      %r128
+	fpcast.32   %r43 <- (64) %arg1
+	ret.32      %r43
 
 
 int_2_double:
 .L86:
 	<entry-point>
-	fpcast.64   %r131 <- (32) %arg1
-	ret.64      %r131
+	fpcast.64   %r44 <- (32) %arg1
+	ret.64      %r44
 
 
 uint_2_double:
 .L88:
 	<entry-point>
-	fpcast.64   %r134 <- (32) %arg1
-	ret.64      %r134
+	fpcast.64   %r45 <- (32) %arg1
+	ret.64      %r45
 
 
 long_2_double:
 .L90:
 	<entry-point>
-	fpcast.64   %r137 <- (64) %arg1
-	ret.64      %r137
+	fpcast.64   %r46 <- (64) %arg1
+	ret.64      %r46
 
 
 ulong_2_double:
 .L92:
 	<entry-point>
-	fpcast.64   %r140 <- (64) %arg1
-	ret.64      %r140
+	fpcast.64   %r47 <- (64) %arg1
+	ret.64      %r47
 
 
 float_2_double:
 .L94:
 	<entry-point>
-	fpcast.64   %r143 <- (32) %arg1
-	ret.64      %r143
+	fpcast.64   %r48 <- (32) %arg1
+	ret.64      %r48
 
 
  * check-output-end
diff --git a/validation/context.c b/validation/context.c
index b9500dc75..9d82456b4 100644
--- a/validation/context.c
+++ b/validation/context.c
@@ -327,7 +327,7 @@ context.c:131:12: warning: context imbalance in 'warn_if1' - wrong count at exit
 context.c:140:12: warning: context imbalance in 'warn_if2' - different lock contexts for basic block
 context.c:202:9: warning: context imbalance in 'warn_while1' - different lock contexts for basic block
 context.c:210:17: warning: context imbalance in 'warn_while2' - unexpected unlock
-context.c:216:9: warning: context imbalance in 'warn_while3' - wrong count at exit
+context.c:214:13: warning: context imbalance in 'warn_while3' - wrong count at exit
 context.c:274:13: warning: context imbalance in 'warn_goto1' - wrong count at exit
 context.c:283:13: warning: context imbalance in 'warn_goto2' - wrong count at exit
 context.c:300:5: warning: context imbalance in 'warn_goto3' - different lock contexts for basic block
diff --git a/validation/linear/bitfield-init-zero.c b/validation/linear/bitfield-init-zero.c
index 39a64345e..1f7882751 100644
--- a/validation/linear/bitfield-init-zero.c
+++ b/validation/linear/bitfield-init-zero.c
@@ -57,17 +57,17 @@ int bfs_get0(void)
 bfuu_init:
 .L0:
 	<entry-point>
-	cast.9      %r2 <- (32) %arg1
-	shl.32      %r4 <- %r2, $11
-	ret.32      %r4
+	cast.9      %r1 <- (32) %arg1
+	shl.32      %r2 <- %r1, $11
+	ret.32      %r2
 
 
 bfus_init:
 .L2:
 	<entry-point>
-	scast.9     %r10 <- (32) %arg1
-	shl.32      %r12 <- %r10, $11
-	ret.32      %r12
+	scast.9     %r5 <- (32) %arg1
+	shl.32      %r6 <- %r5, $11
+	ret.32      %r6
 
 
 bfu_get0:
@@ -79,17 +79,17 @@ bfu_get0:
 bfsu_init:
 .L6:
 	<entry-point>
-	cast.9      %r23 <- (32) %arg1
-	shl.32      %r25 <- %r23, $11
-	ret.32      %r25
+	cast.9      %r12 <- (32) %arg1
+	shl.32      %r13 <- %r12, $11
+	ret.32      %r13
 
 
 bfss_init:
 .L8:
 	<entry-point>
-	scast.9     %r31 <- (32) %arg1
-	shl.32      %r33 <- %r31, $11
-	ret.32      %r33
+	scast.9     %r16 <- (32) %arg1
+	shl.32      %r17 <- %r16, $11
+	ret.32      %r17
 
 
 bfs_get0:
diff --git a/validation/linear/struct-init-partial.c b/validation/linear/struct-init-partial.c
index 1f5078bfa..a80031a5b 100644
--- a/validation/linear/struct-init-partial.c
+++ b/validation/linear/struct-init-partial.c
@@ -24,8 +24,8 @@ s_init_first:
 	<entry-point>
 	store.96    $0 -> 0[s]
 	store.32    %arg1 -> 0[s]
-	load.96     %r2 <- 0[s]
-	ret.96      %r2
+	load.96     %r1 <- 0[s]
+	ret.96      %r1
 
 
 s_init_third:
@@ -33,8 +33,8 @@ s_init_third:
 	<entry-point>
 	store.96    $0 -> 0[s]
 	store.32    %arg1 -> 8[s]
-	load.96     %r5 <- 0[s]
-	ret.96      %r5
+	load.96     %r2 <- 0[s]
+	ret.96      %r2
 
 
  * check-output-end
diff --git a/validation/loop-linearization.c b/validation/loop-linearization.c
index 25c6dfb87..0c829ff18 100644
--- a/validation/loop-linearization.c
+++ b/validation/loop-linearization.c
@@ -39,11 +39,11 @@ static int fdo(void)
 ffor:
 .L0:
 	<entry-point>
-	phisrc.32   %phi5(i) <- $0
+	phisrc.32   %phi2(i) <- $0
 	br          .L4
 
 .L4:
-	phi.32      %r1(i) <- %phi5(i), %phi6(i)
+	phi.32      %r1(i) <- %phi2(i), %phi3(i)
 	setlt.32    %r2 <- %r1(i), $10
 	cbr         %r2, .L1, .L3
 
@@ -52,84 +52,84 @@ ffor:
 	cbr         %r4, .L2, .L5
 
 .L5:
-	phisrc.32   %phi1(return) <- $0
+	phisrc.32   %phi4(return) <- $0
 	br          .L7
 
 .L2:
-	add.32      %r7 <- %r1(i), $1
-	phisrc.32   %phi6(i) <- %r7
+	add.32      %r5 <- %r1(i), $1
+	phisrc.32   %phi3(i) <- %r5
 	br          .L4
 
 .L3:
-	phisrc.32   %phi2(return) <- $1
+	phisrc.32   %phi5(return) <- $1
 	br          .L7
 
 .L7:
-	phi.32      %r5 <- %phi1(return), %phi2(return)
-	ret.32      %r5
+	phi.32      %r6(return) <- %phi4(return), %phi5(return)
+	ret.32      %r6(return)
 
 
 fwhile:
 .L8:
 	<entry-point>
-	phisrc.32   %phi11(i) <- $0
+	phisrc.32   %phi7(i) <- $0
 	br          .L12
 
 .L12:
-	phi.32      %r8(i) <- %phi11(i), %phi12(i)
-	setlt.32    %r9 <- %r8(i), $10
-	cbr         %r9, .L9, .L11
+	phi.32      %r7(i) <- %phi7(i), %phi8(i)
+	setlt.32    %r8 <- %r7(i), $10
+	cbr         %r8, .L9, .L11
 
 .L9:
-	call.32     %r11 <- p, %r8(i)
-	cbr         %r11, .L14, .L13
+	call.32     %r10 <- p, %r7(i)
+	cbr         %r10, .L14, .L13
 
 .L13:
-	phisrc.32   %phi7(return) <- $0
+	phisrc.32   %phi9(return) <- $0
 	br          .L15
 
 .L14:
-	add.32      %r14 <- %r8(i), $1
-	phisrc.32   %phi12(i) <- %r14
+	add.32      %r11 <- %r7(i), $1
+	phisrc.32   %phi8(i) <- %r11
 	br          .L12
 
 .L11:
-	phisrc.32   %phi8(return) <- $1
+	phisrc.32   %phi10(return) <- $1
 	br          .L15
 
 .L15:
-	phi.32      %r12 <- %phi7(return), %phi8(return)
-	ret.32      %r12
+	phi.32      %r12(return) <- %phi9(return), %phi10(return)
+	ret.32      %r12(return)
 
 
 fdo:
 .L16:
 	<entry-point>
-	phisrc.32   %phi16(i) <- $0
+	phisrc.32   %phi11(i) <- $0
 	br          .L17
 
 .L17:
-	phi.32      %r15(i) <- %phi16(i), %phi17(i)
-	call.32     %r16 <- p, %r15(i)
-	cbr         %r16, .L18, .L20
+	phi.32      %r13(i) <- %phi11(i), %phi12(i)
+	call.32     %r14 <- p, %r13(i)
+	cbr         %r14, .L18, .L20
 
 .L20:
 	phisrc.32   %phi13(return) <- $0
 	br          .L22
 
 .L18:
-	add.32      %r19 <- %r15(i), $1
-	setlt.32    %r20 <- %r15(i), $10
-	phisrc.32   %phi17(i) <- %r19
-	cbr         %r20, .L17, .L19
+	add.32      %r15 <- %r13(i), $1
+	setlt.32    %r16 <- %r13(i), $10
+	phisrc.32   %phi12(i) <- %r15
+	cbr         %r16, .L17, .L19
 
 .L19:
 	phisrc.32   %phi14(return) <- $1
 	br          .L22
 
 .L22:
-	phi.32      %r17 <- %phi13(return), %phi14(return)
-	ret.32      %r17
+	phi.32      %r17(return) <- %phi13(return), %phi14(return)
+	ret.32      %r17(return)
 
 
  * check-output-end
diff --git a/validation/memops-volatile.c b/validation/memops-volatile.c
index 0f3e12ad2..069aa73f3 100644
--- a/validation/memops-volatile.c
+++ b/validation/memops-volatile.c
@@ -13,8 +13,8 @@ foo:
 .L0:
 	<entry-point>
 	store.32    %arg2 -> 0[%arg1]
-	load.32     %r5 <- 0[%arg1]
-	ret.32      %r5
+	load.32     %r2 <- 0[%arg1]
+	ret.32      %r2
 
 
  * check-output-end
diff --git a/validation/optim/bool-simplify.c b/validation/optim/bool-simplify.c
index 05be11497..0c8cddbb8 100644
--- a/validation/optim/bool-simplify.c
+++ b/validation/optim/bool-simplify.c
@@ -32,17 +32,17 @@ and_0:
 and_1:
 .L2:
 	<entry-point>
-	setne.1     %r8 <- %arg1, $0
-	cast.32     %r11 <- (1) %r8
-	ret.32      %r11
+	setne.1     %r5 <- %arg1, $0
+	cast.32     %r8 <- (1) %r5
+	ret.32      %r8
 
 
 or_0:
 .L4:
 	<entry-point>
-	setne.1     %r14 <- %arg1, $0
-	cast.32     %r17 <- (1) %r14
-	ret.32      %r17
+	setne.1     %r9 <- %arg1, $0
+	cast.32     %r12 <- (1) %r9
+	ret.32      %r12
 
 
 or_1:
-- 
2.14.0

[PATCH 29/29] sssa: remove now unneeded simplify_one_symbol()

[Luc Van Oostenryck]

Now that this function is not called anymore, we can
remove the associated code.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c | 324 -----------------------------------------------------------------
 flow.h |   1 -
 2 files changed, 325 deletions(-)

diff --git a/flow.c b/flow.c
index 78dd6b3a5..58ff24d23 100644
--- a/flow.c
+++ b/flow.c
@@ -362,66 +362,6 @@ int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom
 	return 1;
 }
 
-static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
-{
-	pseudo_t p;
-	FOR_EACH_PTR(list, p) {
-		if (p->def->bb == bb)
-			return 1;
-	} END_FOR_EACH_PTR(p);
-
-	return 0;
-}
-
-static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
-	struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
-	int local)
-{
-	struct basic_block *parent;
-
-	if (!bb->parents)
-		return !!local;
-
-	FOR_EACH_PTR(bb->parents, parent) {
-		struct instruction *one;
-		struct instruction *br;
-		pseudo_t phi;
-
-		FOR_EACH_PTR_REVERSE(parent->insns, one) {
-			int dominance;
-			if (one == insn)
-				goto no_dominance;
-			dominance = dominates(pseudo, insn, one, local);
-			if (dominance < 0) {
-				if (one->opcode == OP_LOAD)
-					continue;
-				return 0;
-			}
-			if (!dominance)
-				continue;
-			goto found_dominator;
-		} END_FOR_EACH_PTR_REVERSE(one);
-no_dominance:
-		if (parent->generation == generation)
-			continue;
-		parent->generation = generation;
-
-		if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
-			return 0;
-		continue;
-
-found_dominator:
-		if (dominators && phisrc_in_bb(*dominators, parent))
-			continue;
-		br = delete_last_instruction(&parent->insns);
-		phi = alloc_phi(parent, one->target, one->type);
-		phi->ident = phi->ident ? : pseudo->ident;
-		add_instruction(&parent->insns, br);
-		use_pseudo(insn, phi, add_pseudo(dominators, phi));
-	} END_FOR_EACH_PTR(parent);
-	return 1;
-}		
-
 /*
  * We should probably sort the phi list just to make it easier to compare
  * later for equality. 
@@ -460,178 +400,6 @@ complex_phi:
 	insn->phi_list = dominators;
 }
 
-static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
-	unsigned long generation, int local)
-{
-	struct basic_block *bb = insn->bb;
-	struct instruction *one, *dom = NULL;
-	struct pseudo_list *dominators;
-	int partial;
-
-	/* Unreachable load? Undo it */
-	if (!bb) {
-		insn->opcode = OP_LNOP;
-		return 1;
-	}
-
-	partial = 0;
-	FOR_EACH_PTR(bb->insns, one) {
-		int dominance;
-		if (one == insn)
-			goto found;
-		dominance = dominates(pseudo, insn, one, local);
-		if (dominance < 0) {
-			/* Ignore partial load dominators */
-			if (one->opcode == OP_LOAD)
-				continue;
-			dom = NULL;
-			partial = 1;
-			continue;
-		}
-		if (!dominance)
-			continue;
-		dom = one;
-		partial = 0;
-	} END_FOR_EACH_PTR(one);
-	/* Whaa? */
-	warning(pseudo->sym->pos, "unable to find symbol read");
-	return 0;
-found:
-	if (partial)
-		return 0;
-
-	if (dom) {
-		convert_load_instruction(insn, dom->target);
-		return 1;
-	}
-
-	/* OK, go find the parents */
-	bb->generation = generation;
-
-	dominators = NULL;
-	if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local))
-		return 0;
-
-	/* This happens with initial assignments to structures etc.. */
-	if (!dominators) {
-		if (!local)
-			return 0;
-		check_access(insn);
-		convert_load_instruction(insn, value_pseudo(0));
-		return 1;
-	}
-
-	/*
-	 * If we find just one dominating instruction, we
-	 * can turn it into a direct thing. Otherwise we'll
-	 * have to turn the load into a phi-node of the
-	 * dominators.
-	 */
-	rewrite_load_instruction(insn, dominators);
-	return 1;
-}
-
-static void kill_store(struct instruction *insn)
-{
-	if (insn) {
-		insn->bb = NULL;
-		insn->opcode = OP_SNOP;
-		kill_use(&insn->target);
-	}
-}
-
-/* Kill a pseudo that is dead on exit from the bb */
-static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local)
-{
-	struct instruction *insn;
-	struct basic_block *parent;
-
-	if (bb->generation == generation)
-		return;
-	bb->generation = generation;
-	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
-		int opcode = insn->opcode;
-
-		if (opcode != OP_LOAD && opcode != OP_STORE) {
-			if (local)
-				continue;
-			if (opcode == OP_CALL)
-				return;
-			continue;
-		}
-		if (insn->src == pseudo) {
-			if (opcode == OP_LOAD)
-				return;
-			kill_store(insn);
-			continue;
-		}
-		if (local)
-			continue;
-		if (insn->src->type != PSEUDO_SYM)
-			return;
-	} END_FOR_EACH_PTR_REVERSE(insn);
-
-	FOR_EACH_PTR(bb->parents, parent) {
-		struct basic_block *child;
-		FOR_EACH_PTR(parent->children, child) {
-			if (child && child != bb)
-				return;
-		} END_FOR_EACH_PTR(child);
-		kill_dead_stores(pseudo, generation, parent, local);
-	} END_FOR_EACH_PTR(parent);
-}
-
-/*
- * This should see if the "insn" trivially dominates some previous store, and kill the
- * store if unnecessary.
- */
-static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn, 
-	unsigned long generation, struct basic_block *bb, int local, int found)
-{
-	struct instruction *one;
-	struct basic_block *parent;
-
-	/* Unreachable store? Undo it */
-	if (!bb) {
-		kill_store(insn);
-		return;
-	}
-	if (bb->generation == generation)
-		return;
-	bb->generation = generation;
-	FOR_EACH_PTR_REVERSE(bb->insns, one) {
-		int dominance;
-		if (!found) {
-			if (one != insn)
-				continue;
-			found = 1;
-			continue;
-		}
-		dominance = dominates(pseudo, insn, one, local);
-		if (!dominance)
-			continue;
-		if (dominance < 0)
-			return;
-		if (one->opcode == OP_LOAD)
-			return;
-		kill_store(one);
-	} END_FOR_EACH_PTR_REVERSE(one);
-
-	if (!found) {
-		warning(bb->pos, "Unable to find instruction");
-		return;
-	}
-
-	FOR_EACH_PTR(bb->parents, parent) {
-		struct basic_block *child;
-		FOR_EACH_PTR(parent->children, child) {
-			if (child && child != bb)
-				return;
-		} END_FOR_EACH_PTR(child);
-		kill_dominated_stores(pseudo, insn, generation, parent, local, found);
-	} END_FOR_EACH_PTR(parent);
-}
-
 void check_access(struct instruction *insn)
 {
 	pseudo_t pseudo = insn->src;
@@ -648,98 +416,6 @@ void check_access(struct instruction *insn)
 	}
 }
 
-static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
-{
-	pseudo_t pseudo;
-	struct pseudo_user *pu;
-	unsigned long mod;
-	int all;
-
-	/* Never used as a symbol? */
-	pseudo = sym->pseudo;
-	if (!pseudo)
-		return;
-
-	/* We don't do coverage analysis of volatiles.. */
-	if (sym->ctype.modifiers & MOD_VOLATILE)
-		return;
-
-	/* ..and symbols with external visibility need more care */
-	mod = sym->ctype.modifiers & (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
-	if (mod)
-		goto external_visibility;
-
-	FOR_EACH_PTR(pseudo->users, pu) {
-		/* We know that the symbol-pseudo use is the "src" in the instruction */
-		struct instruction *insn = pu->insn;
-
-		switch (insn->opcode) {
-		case OP_STORE:
-			break;
-		case OP_LOAD:
-			break;
-		case OP_SYMADDR:
-			if (!insn->bb)
-				continue;
-			mod |= MOD_ADDRESSABLE;
-			goto external_visibility;
-		case OP_NOP:
-		case OP_SNOP:
-		case OP_LNOP:
-		case OP_PHI:
-			continue;
-		default:
-			warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident));
-		}
-	} END_FOR_EACH_PTR(pu);
-
-external_visibility:
-	all = 1;
-	FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
-		struct instruction *insn = pu->insn;
-		if (insn->opcode == OP_LOAD)
-			all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
-	} END_FOR_EACH_PTR_REVERSE(pu);
-
-	/* If we converted all the loads, remove the stores. They are dead */
-	if (all && !mod) {
-		FOR_EACH_PTR(pseudo->users, pu) {
-			struct instruction *insn = pu->insn;
-			if (insn->opcode == OP_STORE)
-				kill_store(insn);
-		} END_FOR_EACH_PTR(pu);
-	} else {
-		/*
-		 * If we couldn't take the shortcut, see if we can at least kill some
-		 * of them..
-		 */
-		FOR_EACH_PTR(pseudo->users, pu) {
-			struct instruction *insn = pu->insn;
-			if (insn->opcode == OP_STORE)
-				kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0);
-		} END_FOR_EACH_PTR(pu);
-
-		if (!(mod & (MOD_NONLOCAL | MOD_STATIC))) {
-			struct basic_block *bb;
-			FOR_EACH_PTR(ep->bbs, bb) {
-				if (!bb->children)
-					kill_dead_stores(pseudo, ++bb_generation, bb, !mod);
-			} END_FOR_EACH_PTR(bb);
-		}
-	}
-			
-	return;
-}
-
-void simplify_symbol_usage(struct entrypoint *ep)
-{
-	pseudo_t pseudo;
-
-	FOR_EACH_PTR(ep->accesses, pseudo) {
-		simplify_one_symbol(ep, pseudo->sym);
-	} END_FOR_EACH_PTR(pseudo);
-}

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Linus Torvalds]

On Wed, Aug 16, 2017 at 8:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The goal of this series is to implement and integrate to sparse
> the method described in the paper:

Thanks, now the changes have a good commit log, and the patches all
look good to me.

I didn't *test* any of it, or try to follow the logic, but it can't be
worse than what we had, so "just make it so".

               Linus

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Luc Van Oostenryck]

On Wed, Aug 16, 2017 at 5:51 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Wed, Aug 16, 2017 at 8:34 AM, Luc Van Oostenryck wrote:
>> The goal of this series is to implement and integrate to sparse
>> the method described in the paper:
>
> Thanks, now the changes have a good commit log, and the patches all
> look good to me.
>
> I didn't *test* any of it, or try to follow the logic, but it can't be
> worse than what we had, so "just make it so".

Thank you.

My own tests are pretty promising: no crashes, testsuite OK,
kernel allyesconfig OK too (but there is just 8 additional
'bad context' warnings I would like to investigate, OTOH,
knowing how broken the current SSA is I would bet that
these warnings were, in fact, missing in the old/present version).

For the logic, the (first part of the) paper is pretty straight
forward I won't be able to explain better than they did.

Best regards,
-- Luc Van Oostenryck

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The goal of this series is to implement and integrate to sparse
> the method described in the paper:
>     "Simple and Efficient Construction of Static Single Assignment Form"
>         by Matthias Braun, Sebastian Buchwald, Sebastian Hack,
>            Roland Leissa, Christoph Mallon and Andreas Zwinkau.
>     cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf
>
> In the present case, the principal motivation to use this method
> is that the current one in sparse is severely broken.
>
>
> The series is also available in the git repository at:
>
>   git://github.com/lucvoo/sparse.git sssa-mini-v1
>
> for you to fetch changes up to 98a21bc0c82af5115687c7e03a277519836bcac6:
>
>   sssa: remove now unneeded simplify_one_symbol() (2017-08-16 17:25:25 +0200)

Hi Luc,

Thank you so much for the patch.

Here is the kernel full allmodconfig running ssa-mini-v1 on my new
compile server. On the new server the timing is very consistent.
The variance of run to run is under 0.1 second.

ssa-mini-v1:
1205.82user 463.65system 1:16.97elapsed 2168%CPU (0avgtext+0avgdata
536216maxresident)k
0inputs+12824outputs (0major+132162996minor)pagefaults 0swaps
1206.35user 463.27system 1:16.95elapsed 2169%CPU (0avgtext+0avgdata
536296maxresident)k
0inputs+12824outputs (0major+132156314minor)pagefaults 0swaps


This is the rc5 as base line.
1173.42user 453.56system 1:15.21elapsed 2163%CPU (0avgtext+0avgdata
238072maxresident)k
0inputs+12784outputs (0major+128858147minor)pagefaults 0swaps
1172.86user 453.53system 1:15.14elapsed 2164%CPU (0avgtext+0avgdata
238076maxresident)k
0inputs+12784outputs (0major+128858804minor)pagefaults 0swaps

So the ssa-mini-v1 is about 2% slower than the current rc5.

I inline the sparse checking different here.
I will take a look at you patches next :-)

BTW, how do you want your patches to be merged? Assume there is
some feed back. Do you want to come up with V2 V3 or have them merged
to master then come up with fix up on master?

Thanks

Chris

diff -ruN linux-checker/rc5/drivers/base/firmware_class.sp
linux-checker/ssa/drivers/base/firmware_class.sp
--- linux-checker/rc5/drivers/base/firmware_class.sp 2017-08-17
00:27:32.065207474 -0400
+++ linux-checker/ssa/drivers/base/firmware_class.sp 2017-08-17
00:18:56.525833366 -0400
@@ -1 +1 @@
-drivers/base/firmware_class.c:395:9: warning: context imbalance in
'fw_free_buf' - wrong count at exit
+drivers/base/firmware_class.c:391:13: warning: context imbalance in
'fw_free_buf' - wrong count at exit
diff -ruN linux-checker/rc5/drivers/block/drbd/drbd_actlog.sp
linux-checker/ssa/drivers/block/drbd/drbd_actlog.sp
--- linux-checker/rc5/drivers/block/drbd/drbd_actlog.sp 2017-08-17
00:27:32.496218655 -0400
+++ linux-checker/ssa/drivers/block/drbd/drbd_actlog.sp 2017-08-17
00:18:57.015846078 -0400
@@ -26,3 +26,4 @@
 drivers/block/drbd/drbd_int.h:1773:14: error: incompatible types in
comparison expression (different address spaces)
 drivers/block/drbd/drbd_actlog.c:469:44: error: incompatible types in
comparison expression (different address spaces)
 drivers/block/drbd/drbd_actlog.c:173:16: warning: context imbalance
in '_drbd_md_sync_page_io' - different lock contexts for basic block
+drivers/block/drbd/drbd_actlog.c:1244:24: warning: context imbalance
in 'drbd_rs_del_all' - different lock contexts for basic block
diff -ruN linux-checker/rc5/drivers/block/drbd/drbd_nl.sp
linux-checker/ssa/drivers/block/drbd/drbd_nl.sp
--- linux-checker/rc5/drivers/block/drbd/drbd_nl.sp 2017-08-17
00:27:32.724224570 -0400
+++ linux-checker/ssa/drivers/block/drbd/drbd_nl.sp 2017-08-17
00:18:57.303853549 -0400
@@ -62,6 +62,7 @@
 drivers/block/drbd/drbd_int.h:791:24: error: incompatible types in
comparison expression (different address spaces)
 drivers/block/drbd/drbd_int.h:791:24: error: incompatible types in
comparison expression (different address spaces)
 drivers/block/drbd/drbd_int.h:791:24: error: incompatible types in
comparison expression (different address spaces)
+drivers/block/drbd/drbd_nl.c:436:17: warning: context imbalance in
'highest_fencing_policy' - different lock contexts for basic block
 drivers/block/drbd/drbd_nl.c:3419:9: warning: context imbalance in
'drbd_adm_dump_devices' - different lock contexts for basic block
 drivers/block/drbd/drbd_nl.c:3687:9: warning: context imbalance in
'drbd_adm_dump_peer_devices' - different lock contexts for basic block
-drivers/block/drbd/drbd_nl.c:3858:9: warning: context imbalance in
'nla_put_status_info' - different lock contexts for basic block
+drivers/block/drbd/drbd_nl.c:3735:12: warning: context imbalance in
'nla_put_status_info' - different lock contexts for basic block
diff -ruN linux-checker/rc5/drivers/block/drbd/drbd_state.sp
linux-checker/ssa/drivers/block/drbd/drbd_state.sp
--- linux-checker/rc5/drivers/block/drbd/drbd_state.sp 2017-08-17
00:27:32.669223143 -0400
+++ linux-checker/ssa/drivers/block/drbd/drbd_state.sp 2017-08-17
00:18:57.216851292 -0400
@@ -27,5 +27,7 @@
 drivers/block/drbd/drbd_state.c:1309:36: warning: cast to non-scalar
 drivers/block/drbd/drbd_state.c:1310:36: warning: cast to non-scalar
 drivers/block/drbd/drbd_state.c:2037:17: error: incompatible types in
comparison expression (different address spaces)
+drivers/block/drbd/drbd_state.c:806:14: warning: context imbalance in
'is_valid_state' - different lock contexts for basic block
+drivers/block/drbd/drbd_state.c:1074:9: warning: context imbalance in
'sanitize_state' - different lock contexts for basic block
 drivers/block/drbd/drbd_state.c:1917:25: warning: context imbalance
in 'after_state_ch' - unexpected unlock
 drivers/block/drbd/drbd_state.c:2333:32: warning: context imbalance
in '_conn_request_state' - unexpected unlock
diff -ruN linux-checker/rc5/drivers/block/drbd/drbd_worker.sp
linux-checker/ssa/drivers/block/drbd/drbd_worker.sp
--- linux-checker/rc5/drivers/block/drbd/drbd_worker.sp 2017-08-17
00:27:32.640222391 -0400
+++ linux-checker/ssa/drivers/block/drbd/drbd_worker.sp 2017-08-17
00:18:57.135849191 -0400
@@ -39,6 +39,6 @@
 drivers/block/drbd/drbd_worker.c:1876:38: error: incompatible types
in comparison expression (different address spaces)
 drivers/block/drbd/drbd_worker.c:2081:14: error: incompatible types
in comparison expression (different address spaces)
 drivers/block/drbd/drbd_worker.c:2136:14: error: incompatible types
in comparison expression (different address spaces)
-drivers/block/drbd/drbd_worker.c:84:25: warning: context imbalance in
'drbd_md_endio' - unexpected unlock
+drivers/block/drbd/drbd_int.h:2140:9: warning: context imbalance in
'drbd_md_endio' - unexpected unlock
 drivers/block/drbd/drbd_worker.c:274:9: warning: context imbalance in
'drbd_request_endio' - unexpected unlock
 drivers/block/drbd/drbd_worker.c:393:12: warning: context imbalance
in 'read_for_csum' - wrong count at exit
diff -ruN linux-checker/rc5/drivers/block/zram/zram_drv.sp
linux-checker/ssa/drivers/block/zram/zram_drv.sp
--- linux-checker/rc5/drivers/block/zram/zram_drv.sp 2017-08-17
00:27:32.761225530 -0400
+++ linux-checker/ssa/drivers/block/zram/zram_drv.sp 2017-08-17
00:18:57.303853549 -0400
@@ -1,2 +1,2 @@
 drivers/block/zram/zram_drv.c:425:13: warning: context imbalance in
'zram_slot_lock' - wrong count at exit
-./include/linux/bit_spinlock.h:62:25: warning: context imbalance in
'zram_slot_unlock' - unexpected unlock
+./arch/x86/include/asm/bitops.h:133:9: warning: context imbalance in
'zram_slot_unlock' - unexpected unlock
diff -ruN linux-checker/rc5/drivers/net/ethernet/chelsio/cxgb4/l2t.sp
linux-checker/ssa/drivers/net/ethernet/chelsio/cxgb4/l2t.sp
--- linux-checker/rc5/drivers/net/ethernet/chelsio/cxgb4/l2t.sp
2017-08-17 00:27:55.087804725 -0400
+++ linux-checker/ssa/drivers/net/ethernet/chelsio/cxgb4/l2t.sp
2017-08-17 00:19:19.860438712 -0400
@@ -1 +1 @@
-./include/linux/skbuff.h:1754:29: warning: context imbalance in
'handle_failed_resolution' - unexpected unlock
+./include/linux/skbuff.h:1733:9: warning: context imbalance in
'handle_failed_resolution' - unexpected unlock
diff -ruN linux-checker/rc5/drivers/net/ethernet/chelsio/cxgb4/sge.sp
linux-checker/ssa/drivers/net/ethernet/chelsio/cxgb4/sge.sp
--- linux-checker/rc5/drivers/net/ethernet/chelsio/cxgb4/sge.sp
2017-08-17 00:27:55.177807060 -0400
+++ linux-checker/ssa/drivers/net/ethernet/chelsio/cxgb4/sge.sp
2017-08-17 00:19:19.965441436 -0400
@@ -10,3 +10,4 @@
 drivers/net/ethernet/chelsio/cxgb4/sge.c:2091:43: warning: cast to
restricted __be64
 drivers/net/ethernet/chelsio/cxgb4/sge.c:1189:34: warning: context
imbalance in 't4_eth_xmit' - different lock contexts for basic block
 drivers/net/ethernet/chelsio/cxgb4/sge.c:1645:28: warning: context
imbalance in 'service_ofldq' - unexpected unlock
+drivers/net/ethernet/chelsio/cxgb4/sge.c:2674:17: warning: context
imbalance in 'sge_tx_timer_cb' - different lock contexts for basic
block
diff -ruN linux-checker/rc5/drivers/net/ethernet/chelsio/cxgb4vf/sge.sp
linux-checker/ssa/drivers/net/ethernet/chelsio/cxgb4vf/sge.sp
--- linux-checker/rc5/drivers/net/ethernet/chelsio/cxgb4vf/sge.sp
2017-08-17 00:27:54.992802261 -0400
+++ linux-checker/ssa/drivers/net/ethernet/chelsio/cxgb4vf/sge.sp
2017-08-17 00:19:20.099444912 -0400
@@ -0,0 +1 @@
+drivers/net/ethernet/chelsio/cxgb4vf/sge.c:2146:17: warning: context
imbalance in 'sge_tx_timer_cb' - different lock contexts for basic
block
diff -ruN linux-checker/rc5/drivers/net/ethernet/myricom/myri10ge/myri10ge.sp
linux-checker/ssa/drivers/net/ethernet/myricom/myri10ge/myri10ge.sp
--- linux-checker/rc5/drivers/net/ethernet/myricom/myri10ge/myri10ge.sp
2017-08-17 00:27:57.390864471 -0400
+++ linux-checker/ssa/drivers/net/ethernet/myricom/myri10ge/myri10ge.sp
2017-08-17 00:19:22.537508160 -0400
@@ -0,0 +1 @@
+drivers/net/ethernet/myricom/myri10ge/myri10ge.c:1449:35: warning:
context imbalance in 'myri10ge_intr' - different lock contexts for
basic block
diff -ruN linux-checker/rc5/drivers/net/ethernet/neterion/vxge/vxge-config.sp
linux-checker/ssa/drivers/net/ethernet/neterion/vxge/vxge-config.sp
--- linux-checker/rc5/drivers/net/ethernet/neterion/vxge/vxge-config.sp
2017-08-17 00:27:57.707872695 -0400
+++ linux-checker/ssa/drivers/net/ethernet/neterion/vxge/vxge-config.sp
2017-08-17 00:19:22.506507356 -0400
@@ -58,4 +58,4 @@
 drivers/net/ethernet/neterion/vxge/vxge-config.c:919:46: warning:
cast to restricted __be64
 drivers/net/ethernet/neterion/vxge/vxge-config.c:919:46: warning:
cast to restricted __be64
 drivers/net/ethernet/neterion/vxge/vxge-config.c:919:46: warning:
cast to restricted __be64
-drivers/net/ethernet/neterion/vxge/vxge-config.c:218:9: warning:
context imbalance in 'vxge_hw_vpath_fw_api' - different lock contexts
for basic block
+drivers/net/ethernet/neterion/vxge/vxge-config.c:157:1: warning:
context imbalance in 'vxge_hw_vpath_fw_api' - different lock contexts
for basic block
diff -ruN linux-checker/rc5/drivers/net/ethernet/neterion/vxge/vxge-main.sp
linux-checker/ssa/drivers/net/ethernet/neterion/vxge/vxge-main.sp
--- linux-checker/rc5/drivers/net/ethernet/neterion/vxge/vxge-main.sp
2017-08-17 00:27:57.449866002 -0400
+++ linux-checker/ssa/drivers/net/ethernet/neterion/vxge/vxge-main.sp
2017-08-17 00:19:22.544508342 -0400
@@ -0,0 +1,3 @@
+drivers/net/ethernet/neterion/vxge/vxge-main.c:116:27: warning:
context imbalance in 'vxge_poll_inta' - different lock contexts for
basic block
+drivers/net/ethernet/neterion/vxge/vxge-main.c:116:27: warning:
context imbalance in 'vxge_netpoll' - different lock contexts for
basic block
+drivers/net/ethernet/neterion/vxge/vxge-main.c:116:27: warning:
context imbalance in 'vxge_tx_msix_handle' - different lock contexts
for basic block
diff -ruN linux-checker/rc5/drivers/net/wan/sbni.sp
linux-checker/ssa/drivers/net/wan/sbni.sp
--- linux-checker/rc5/drivers/net/wan/sbni.sp 2017-08-17
00:28:00.488944842 -0400
+++ linux-checker/ssa/drivers/net/wan/sbni.sp 2017-08-17
00:19:25.338580825 -0400
@@ -1,2 +1,2 @@
 drivers/net/wan/sbni.c:525:20: warning: context imbalance in
'sbni_interrupt' - different lock contexts for basic block
-drivers/net/wan/sbni.c:577:9: warning: context imbalance in
'handle_channel' - different lock contexts for basic block
+drivers/net/wan/sbni.c:531:1: warning: context imbalance in
'handle_channel' - different lock contexts for basic block
diff -ruN linux-checker/rc5/drivers/net/wireless/intel/iwlwifi/mvm/fw-dbg.sp
linux-checker/ssa/drivers/net/wireless/intel/iwlwifi/mvm/fw-dbg.sp
--- linux-checker/rc5/drivers/net/wireless/intel/iwlwifi/mvm/fw-dbg.sp
2017-08-17 00:28:01.987983730 -0400
+++ linux-checker/ssa/drivers/net/wireless/intel/iwlwifi/mvm/fw-dbg.sp
2017-08-17 00:19:27.150627834 -0400
@@ -0,0 +1 @@
+drivers/net/wireless/intel/iwlwifi/mvm/fw-dbg.c:459:9: warning:
context imbalance in 'iwl_read_prph_block' - different lock contexts
for basic block
diff -ruN linux-checker/rc5/drivers/scsi/device_handler/scsi_dh_alua.sp
linux-checker/ssa/drivers/scsi/device_handler/scsi_dh_alua.sp
--- linux-checker/rc5/drivers/scsi/device_handler/scsi_dh_alua.sp
2017-08-17 00:28:06.435099097 -0400
+++ linux-checker/ssa/drivers/scsi/device_handler/scsi_dh_alua.sp
2017-08-17 00:19:31.388737779 -0400
@@ -1,2 +1,3 @@
 drivers/scsi/device_handler/scsi_dh_alua.c:139:16: warning: Variable
length array is used.
 drivers/scsi/device_handler/scsi_dh_alua.c:167:16: warning: Variable
length array is used.
+drivers/scsi/device_handler/scsi_dh_alua.c:658:33: warning: context
imbalance in 'alua_rtpg' - different lock contexts for basic block
diff -ruN linux-checker/rc5/drivers/scsi/libfc/fc_fcp.sp
linux-checker/ssa/drivers/scsi/libfc/fc_fcp.sp
--- linux-checker/rc5/drivers/scsi/libfc/fc_fcp.sp 2017-08-17
00:28:07.033114610 -0400
+++ linux-checker/ssa/drivers/scsi/libfc/fc_fcp.sp 2017-08-17
00:19:31.949752332 -0400
@@ -7,6 +7,6 @@
 drivers/scsi/libfc/fc_fcp.c:1465:26: warning: context imbalance in
'fc_fcp_timeout' - unexpected unlock
 drivers/scsi/libfc/fc_fcp.c:1654:26: warning: context imbalance in
'fc_fcp_rec_resp' - unexpected unlock
 drivers/scsi/libfc/fc_fcp.c:1699:26: warning: context imbalance in
'fc_fcp_rec_error' - unexpected unlock
-drivers/scsi/libfc/fc_fcp.c:1804:34: warning: context imbalance in
'fc_fcp_srr_resp' - unexpected unlock
+drivers/scsi/libfc/fc_fcp.c:246:23: warning: context imbalance in
'fc_fcp_srr_resp' - unexpected unlock
 drivers/scsi/libfc/fc_fcp.c:1848:26: warning: context imbalance in
'fc_fcp_srr_error' - unexpected unlock
 drivers/scsi/libfc/fc_fcp.c:2153:9: warning: context imbalance in
'fc_eh_abort' - unexpected unlock
diff -ruN linux-checker/rc5/drivers/scsi/mvsas/mv_sas.sp
linux-checker/ssa/drivers/scsi/mvsas/mv_sas.sp
--- linux-checker/rc5/drivers/scsi/mvsas/mv_sas.sp 2017-08-17
00:28:07.361123120 -0400
+++ linux-checker/ssa/drivers/scsi/mvsas/mv_sas.sp 2017-08-17
00:19:32.287761101 -0400
@@ -31,5 +31,5 @@
 drivers/scsi/mvsas/mv_sas.c:1671:23: warning: cast to restricted __le32
 drivers/scsi/mvsas/mv_sas.c:1672:23: warning: cast to restricted __le32
 drivers/scsi/mvsas/mv_sas.c:1092:13: warning: context imbalance in
'mvs_port_notify_formed' - different lock contexts for basic block
-drivers/scsi/mvsas/mv_sas.c:1238:9: warning: context imbalance in
'mvs_dev_found_notify' - different lock contexts for basic block
+drivers/scsi/mvsas/mv_sas.c:1190:12: warning: context imbalance in
'mvs_dev_found_notify' - different lock contexts for basic block
 drivers/scsi/mvsas/mv_sas.c:1832:9: warning: context imbalance in
'mvs_slot_complete' - unexpected unlock
diff -ruN linux-checker/rc5/fs/btrfs/ctree.sp
linux-checker/ssa/fs/btrfs/ctree.sp
--- linux-checker/rc5/fs/btrfs/ctree.sp 2017-08-17 00:28:19.948449660 -0400
+++ linux-checker/ssa/fs/btrfs/ctree.sp 2017-08-17 00:19:45.049092155 -0400
@@ -1,3 +1,3 @@
 fs/btrfs/ctree.c:154:22: error: incompatible types in comparison
expression (different address spaces)
-fs/btrfs/ctree.c:635:42: warning: context imbalance in
'tree_mod_log_insert_move' - unexpected unlock
-fs/btrfs/ctree.c:864:42: warning: context imbalance in
'tree_mod_log_eb_copy' - unexpected unlock
+fs/btrfs/ctree.c:354:9: warning: context imbalance in
'tree_mod_log_insert_move' - unexpected unlock
+fs/btrfs/ctree.c:354:9: warning: context imbalance in
'tree_mod_log_eb_copy' - unexpected unlock
diff -ruN linux-checker/rc5/fs/btrfs/dev-replace.sp
linux-checker/ssa/fs/btrfs/dev-replace.sp
--- linux-checker/rc5/fs/btrfs/dev-replace.sp 2017-08-17
00:28:20.029451761 -0400
+++ linux-checker/ssa/fs/btrfs/dev-replace.sp 2017-08-17
00:19:45.090093219 -0400
@@ -6,7 +6,7 @@
 fs/btrfs/dev-replace.c:807:17: error: incompatible types in
comparison expression (different address spaces)
 fs/btrfs/dev-replace.c:364:9: error: incompatible types in comparison
expression (different address spaces)
 fs/btrfs/dev-replace.c:364:9: error: incompatible types in comparison
expression (different address spaces)
-fs/btrfs/dev-replace.c:866:9: warning: context imbalance in
'btrfs_dev_replace_lock' - wrong count at exit
+fs/btrfs/dev-replace.c:864:6: warning: context imbalance in
'btrfs_dev_replace_lock' - wrong count at exit
 fs/btrfs/dev-replace.c:886:17: warning: context imbalance in
'btrfs_dev_replace_unlock' - unexpected unlock
 fs/btrfs/dev-replace.c:900:9: warning: context imbalance in
'btrfs_dev_replace_set_lock_blocking' - unexpected unlock
 fs/btrfs/dev-replace.c:911:9: warning: context imbalance in
'btrfs_dev_replace_clear_lock_blocking' - wrong count at exit
diff -ruN linux-checker/rc5/fs/btrfs/extent-tree.sp
linux-checker/ssa/fs/btrfs/extent-tree.sp
--- linux-checker/rc5/fs/btrfs/extent-tree.sp 2017-08-17
00:28:19.860447377 -0400
+++ linux-checker/ssa/fs/btrfs/extent-tree.sp 2017-08-17
00:19:45.581105957 -0400
@@ -1,3 +1,3 @@
 fs/btrfs/extent-tree.c:7412:39: warning: context imbalance in
'btrfs_lock_cluster' - wrong count at exit
 fs/btrfs/extent-tree.c:7688:44: warning: context imbalance in
'find_free_extent' - unexpected unlock
-fs/btrfs/extent-tree.c:9764:9: warning: context imbalance in
'btrfs_put_block_group_cache' - wrong count at exit
+fs/btrfs/extent-tree.c:9759:6: warning: context imbalance in
'btrfs_put_block_group_cache' - wrong count at exit
diff -ruN linux-checker/rc5/fs/ceph/caps.sp linux-checker/ssa/fs/ceph/caps.sp
--- linux-checker/rc5/fs/ceph/caps.sp 2017-08-17 00:28:20.364460452 -0400
+++ linux-checker/ssa/fs/ceph/caps.sp 2017-08-17 00:19:45.554105256 -0400
@@ -1,3 +1,3 @@
 fs/ceph/caps.c:2036:9: warning: context imbalance in 'try_flush_caps'
- wrong count at exit
-fs/ceph/caps.c:3155:9: warning: context imbalance in
'handle_cap_grant' - wrong count at exit
+fs/ceph/caps.c:2909:13: warning: context imbalance in
'handle_cap_grant' - wrong count at exit
 fs/ceph/caps.c:3739:17: warning: context imbalance in
'ceph_handle_caps' - unexpected unlock
diff -ruN linux-checker/rc5/fs/ntfs/compress.sp
linux-checker/ssa/fs/ntfs/compress.sp
--- linux-checker/rc5/fs/ntfs/compress.sp 2017-08-17 00:28:24.202560020 -0400
+++ linux-checker/ssa/fs/ntfs/compress.sp 2017-08-17 00:19:49.671212062 -0400
@@ -1,3 +1,3 @@
 fs/ntfs/compress.c:195:58: warning: Variable length array is used.
 fs/ntfs/compress.c:220:28: warning: context imbalance in
'ntfs_decompress' - unexpected unlock
-fs/ntfs/compress.c:886:16: warning: context imbalance in
'ntfs_read_compressed_block' - different lock contexts for basic block
+fs/ntfs/compress.c:785:16: warning: context imbalance in
'ntfs_read_compressed_block' - different lock contexts for basic block
diff -ruN linux-checker/rc5/ipc/sem.sp linux-checker/ssa/ipc/sem.sp
--- linux-checker/rc5/ipc/sem.sp 2017-08-17 00:28:27.519646071 -0400
+++ linux-checker/ssa/ipc/sem.sp 2017-08-17 00:19:53.227304314 -0400
@@ -1,5 +1,5 @@
 ipc/sem.c:521:9: warning: context imbalance in 'newary' - unexpected unlock
-ipc/sem.c:1132:17: warning: context imbalance in 'freeary' - unexpected unlock
+ipc/sem.c:446:9: warning: context imbalance in 'freeary' - unexpected unlock
 ipc/sem.c:1585:9: warning: context imbalance in 'semctl_down' -
different lock contexts for basic block
 ipc/sem.c:1690:24: warning: context imbalance in 'find_alloc_undo' -
wrong count at exit
 ./include/linux/rcupdate.h:663:9: warning: context imbalance in
'SyS_semtimedop' - unexpected unlock
diff -ruN linux-checker/rc5/ipc/util.sp linux-checker/ssa/ipc/util.sp
--- linux-checker/rc5/ipc/util.sp 2017-08-17 00:28:27.471644826 -0400
+++ linux-checker/ssa/ipc/util.sp 2017-08-17 00:19:53.161302602 -0400
@@ -3,5 +3,5 @@
 ipc/util.c:373:27: warning: context imbalance in 'ipcget_public' -
unexpected unlock
 ipc/util.c:518:22: warning: context imbalance in 'ipc_lock' -
different lock contexts for basic block
 ipc/util.c:687:29: warning: context imbalance in 'sysvipc_find_ipc' -
different lock contexts for basic block
-ipc/util.c:725:27: warning: context imbalance in 'sysvipc_proc_next'
- unexpected unlock
-ipc/util.c:769:27: warning: context imbalance in 'sysvipc_proc_stop'
- unexpected unlock
+ipc/util.h:162:20: warning: context imbalance in 'sysvipc_proc_next'
- unexpected unlock
+ipc/util.h:162:20: warning: context imbalance in 'sysvipc_proc_stop'
- unexpected unlock
diff -ruN linux-checker/rc5/kernel/cgroup/cgroup.sp
linux-checker/ssa/kernel/cgroup/cgroup.sp
--- linux-checker/rc5/kernel/cgroup/cgroup.sp 2017-08-17
00:28:27.999658524 -0400
+++ linux-checker/ssa/kernel/cgroup/cgroup.sp 2017-08-17
00:19:53.705316715 -0400
@@ -1 +1 @@
-kernel/cgroup/cgroup.c:2656:9: warning: context imbalance in
'cgroup_lock_and_drain_offline' - wrong count at exit
+kernel/cgroup/cgroup.c:2645:6: warning: context imbalance in
'cgroup_lock_and_drain_offline' - wrong count at exit
diff -ruN linux-checker/rc5/kernel/debug/debug_core.sp
linux-checker/ssa/kernel/debug/debug_core.sp
--- linux-checker/rc5/kernel/debug/debug_core.sp 2017-08-17
00:28:27.883655514 -0400
+++ linux-checker/ssa/kernel/debug/debug_core.sp 2017-08-17
00:19:53.626314665 -0400
@@ -1 +1 @@
-./arch/x86/include/asm/paravirt.h:809:16: warning: context imbalance
in 'kgdb_cpu_enter' - different lock contexts for basic block
+kernel/debug/debug_core.c:495:9: warning: context imbalance in
'kgdb_cpu_enter' - different lock contexts for basic block
diff -ruN linux-checker/rc5/kernel/events/core.sp
linux-checker/ssa/kernel/events/core.sp
--- linux-checker/rc5/kernel/events/core.sp 2017-08-17 00:28:28.175663090 -0400
+++ linux-checker/ssa/kernel/events/core.sp 2017-08-17 00:19:53.907321955 -0400
@@ -136,9 +136,9 @@
 kernel/events/core.c:149:16: warning: incorrect type in initializer
(different address spaces)
 kernel/events/core.c:11016:26: warning: incorrect type in initializer
(different address spaces)
 kernel/events/core.c:11044:26: warning: incorrect type in initializer
(different address spaces)
-kernel/events/core.c:156:9: warning: context imbalance in
'perf_ctx_lock' - wrong count at exit
+kernel/events/core.c:152:13: warning: context imbalance in
'perf_ctx_lock' - wrong count at exit
 kernel/events/core.c:164:17: warning: context imbalance in
'perf_ctx_unlock' - unexpected unlock
-./include/linux/rcupdate.h:661:9: warning: context imbalance in
'perf_lock_task_context' - different lock contexts for basic block
+kernel/events/core.c:1331:17: warning: context imbalance in
'perf_lock_task_context' - different lock contexts for basic block
 kernel/events/core.c:1358:17: warning: context imbalance in
'perf_pin_task_context' - unexpected unlock
 kernel/events/core.c:2363:9: warning: context imbalance in
'__perf_install_in_context' - wrong count at exit
 kernel/events/core.c:3862:17: warning: context imbalance in
'find_get_context' - unexpected unlock
diff -ruN linux-checker/rc5/net/irda/irqueue.sp
linux-checker/ssa/net/irda/irqueue.sp
--- linux-checker/rc5/net/irda/irqueue.sp 2017-08-17 00:28:30.494723251 -0400
+++ linux-checker/ssa/net/irda/irqueue.sp 2017-08-17 00:19:56.477388628 -0400
@@ -1,4 +1,4 @@
-net/irda/irqueue.c:405:25: warning: context imbalance in
'hashbin_delete' - different lock contexts for basic block
+net/irda/irqueue.c:414:33: warning: context imbalance in
'hashbin_delete' - different lock contexts for basic block
 net/irda/irqueue.c:445:6: warning: context imbalance in
'hashbin_insert' - different lock contexts for basic block
 net/irda/irqueue.c:538:9: warning: context imbalance in
'hashbin_remove_first' - different lock contexts for basic block
 net/irda/irqueue.c:628:9: warning: context imbalance in
'hashbin_remove' - different lock contexts for basic block
diff -ruN linux-checker/rc5/security/selinux/avc.sp
linux-checker/ssa/security/selinux/avc.sp
--- linux-checker/rc5/security/selinux/avc.sp 2017-08-17
00:28:32.946786862 -0400
+++ linux-checker/ssa/security/selinux/avc.sp 2017-08-17
00:19:59.397464380 -0400
@@ -0,0 +1 @@
+security/selinux/avc.c:523:58: warning: context imbalance in
'avc_alloc_node' - different lock contexts for basic block

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Christopher Li]

On Wed, Aug 16, 2017 at 11:51 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> Thanks, now the changes have a good commit log, and the patches all
> look good to me.
>
> I didn't *test* any of it, or try to follow the logic, but it can't be
> worse than what we had, so "just make it so".

I agree. And thanks for the feedback.  I really want to get the
SSA behave nicely on sparse too.

Chris

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 12:42:19AM -0400, Christopher Li wrote:
> Hi Luc,

Hi,
 
> Thank you so much for the patch.
> 
> Here is the kernel full allmodconfig running ssa-mini-v1 on my new
> compile server. On the new server the timing is very consistent.
> The variance of run to run is under 0.1 second.
> 
> ssa-mini-v1:
> 1205.82user 463.65system 1:16.97elapsed 2168%CPU (0avgtext+0avgdata
> 536216maxresident)k
> 0inputs+12824outputs (0major+132162996minor)pagefaults 0swaps
> 1206.35user 463.27system 1:16.95elapsed 2169%CPU (0avgtext+0avgdata
> 536296maxresident)k
> 0inputs+12824outputs (0major+132156314minor)pagefaults 0swaps
> 
> 
> This is the rc5 as base line.
> 1173.42user 453.56system 1:15.21elapsed 2163%CPU (0avgtext+0avgdata
> 238072maxresident)k
> 0inputs+12784outputs (0major+128858147minor)pagefaults 0swaps
> 1172.86user 453.53system 1:15.14elapsed 2164%CPU (0avgtext+0avgdata
> 238076maxresident)k
> 0inputs+12784outputs (0major+128858804minor)pagefaults 0swaps
> 
> So the ssa-mini-v1 is about 2% slower than the current rc5.

I haven't measured myself, but I guess that is because this series also
includes the removal of simplify_loads().

I wonder what would be these numbers if you measured:
1) r5 + removal of simplify_loads()
2) r5 + sssa-mini-v1 (which includes the removal).

> BTW, how do you want your patches to be merged? Assume there is
> some feed back. Do you want to come up with V2 V3 or have them merged
> to master then come up with fix up on master?

If there is some reasonable needed changes I can make a -v2
But I think that most changes can be done later as additional
patches once it's already in master.
 

> diff -ruN linux-checker/rc5/drivers/base/firmware_class.sp linux-checker/ssa/drivers/base/firmware_class.sp
> --- linux-checker/rc5/drivers/base/firmware_class.sp 2017-08-17
> +++ linux-checker/ssa/drivers/base/firmware_class.sp 2017-08-17
> @@ -1 +1 @@
> -drivers/base/firmware_class.c:395:9: warning: context imbalance in fw_free_buf' - wrong count at exit
> +drivers/base/firmware_class.c:391:13: warning: context imbalance in 'fw_free_buf' - wrong count at exit

There are often a little bunch of such changes, I've learnt to not
worry about them. Basically you have the same warning but at a
different line:colonm, something even a different file (source file /
include file). The cause is that the BBs are packed or merged
differently and the context checking use the position of the BB
and no the postion of a specific token.
It's annoying, I would like to not have that, but nothing to worry
about.


> diff -ruN linux-checker/rc5/drivers/block/drbd/drbd_actlog.sp linux-checker/ssa/drivers/block/drbd/drbd_actlog.sp
> --- linux-checker/rc5/drivers/block/drbd/drbd_actlog.sp 2017-08-17
> +++ linux-checker/ssa/drivers/block/drbd/drbd_actlog.sp 2017-08-17
> @@ -26,3 +26,4 @@
>  drivers/block/drbd/drbd_int.h:1773:14: error: incompatible types in comparison expression (different address spaces)
>  drivers/block/drbd/drbd_actlog.c:469:44: error: incompatible types in comparison expression (different address spaces)
>  drivers/block/drbd/drbd_actlog.c:173:16: warning: context imbalance in '_drbd_md_sync_page_io' - different lock contexts for basic block
> +drivers/block/drbd/drbd_actlog.c:1244:24: warning: context imbalance in 'drbd_rs_del_all' - different lock contexts for basic block

This one is different, it's part of the 8 or so new 'bad context' I was talking about.
I'll investigate about.

I have also one such warning that was present in -rc5 and absent in sssa-mini-v1.

-- Luc

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Christopher Li]

On Thu, Aug 17, 2017 at 1:16 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Thu, Aug 17, 2017 at 12:42:19AM -0400, Christopher Li wrote:
>> Hi Luc,
>
> Hi,
>
>> Thank you so much for the patch.
>>
>> Here is the kernel full allmodconfig running ssa-mini-v1 on my new
>> compile server. On the new server the timing is very consistent.
>> The variance of run to run is under 0.1 second.
>>
>> ssa-mini-v1:
>> 1205.82user 463.65system 1:16.97elapsed 2168%CPU (0avgtext+0avgdata
>> 536216maxresident)k
>> 0inputs+12824outputs (0major+132162996minor)pagefaults 0swaps
>> 1206.35user 463.27system 1:16.95elapsed 2169%CPU (0avgtext+0avgdata
>> 536296maxresident)k
>> 0inputs+12824outputs (0major+132156314minor)pagefaults 0swaps
>>
>>
>> This is the rc5 as base line.
>> 1173.42user 453.56system 1:15.21elapsed 2163%CPU (0avgtext+0avgdata
>> 238072maxresident)k
>> 0inputs+12784outputs (0major+128858147minor)pagefaults 0swaps
>> 1172.86user 453.53system 1:15.14elapsed 2164%CPU (0avgtext+0avgdata
>> 238076maxresident)k
>> 0inputs+12784outputs (0major+128858804minor)pagefaults 0swaps
>>
>> So the ssa-mini-v1 is about 2% slower than the current rc5.
>
> I haven't measured myself, but I guess that is because this series also
> includes the removal of simplify_loads().
>
> I wonder what would be these numbers if you measured:
> 1) r5 + removal of simplify_loads()

1170.54user 453.61system 1:15.05elapsed 2164%CPU (0avgtext+0avgdata
238104maxresident)k
0inputs+12792outputs (0major+128794771minor)pagefaults 0swaps
1172.00user 452.53system 1:14.96elapsed 2166%CPU (0avgtext+0avgdata
238076maxresident)k
0inputs+12784outputs (0major+128795134minor)pagefaults 0swaps


> 2) r5 + sssa-mini-v1 (which includes the removal).
1205.84user 463.12system 1:16.84elapsed 2171%CPU (0avgtext+0avgdata
536300maxresident)k
0inputs+12824outputs (0major+132152193minor)pagefaults 0swaps
1204.59user 462.09system 1:16.77elapsed 2170%CPU (0avgtext+0avgdata
536132maxresident)k
0inputs+12824outputs (0major+132160134minor)pagefaults 0swaps


>
>> BTW, how do you want your patches to be merged? Assume there is
>> some feed back. Do you want to come up with V2 V3 or have them merged
>> to master then come up with fix up on master?
>
> If there is some reasonable needed changes I can make a -v2
> But I think that most changes can be done later as additional
> patches once it's already in master.

Sure.

Speaking of which, can you do me a favor bump the -rc5 to finial?
Just drop the "-rc5" part in Makefile. Let's release the 0.5.1 and
start merging patches :-)

Thanks

Chris

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 7:16 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
>> diff -ruN linux-checker/rc5/drivers/block/drbd/drbd_actlog.sp linux-checker/ssa/drivers/block/drbd/drbd_actlog.sp
>> --- linux-checker/rc5/drivers/block/drbd/drbd_actlog.sp 2017-08-17
>> +++ linux-checker/ssa/drivers/block/drbd/drbd_actlog.sp 2017-08-17
>> @@ -26,3 +26,4 @@
>>  drivers/block/drbd/drbd_int.h:1773:14: error: incompatible types in comparison expression (different address spaces)
>>  drivers/block/drbd/drbd_actlog.c:469:44: error: incompatible types in comparison expression (different address spaces)
>>  drivers/block/drbd/drbd_actlog.c:173:16: warning: context imbalance in '_drbd_md_sync_page_io' - different lock contexts for basic block
>> +drivers/block/drbd/drbd_actlog.c:1244:24: warning: context imbalance in 'drbd_rs_del_all' - different lock contexts for basic block
>
> This one is different, it's part of the 8 or so new 'bad context' I was talking about.
> I'll investigate about.

I just took a quick look at this one. It's interesting.
The IR seems correct, the locking is correct too.
The problem seems that the 'correct' presence of phi-nodes make
that some BB that were merged are not anymore. Nothing is wrong,
just different code. But the context checking is quite limited and see now
a path where the context could differ. I practice they won't differ and with
previous code the context checking saw that because this patch was
unexisting due to more aggressive merge of BB.

One way to see at it is this is a false warning that appears because
of a lack of BB optimizations.
I've a vague idea of what can be done here. I'll look at it later, this evening.

-- Luc

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Christopher Li]

On Thu, Aug 17, 2017 at 2:09 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> I just took a quick look at this one. It's interesting.
> The IR seems correct, the locking is correct too.
> The problem seems that the 'correct' presence of phi-nodes make
> that some BB that were merged are not anymore. Nothing is wrong,

I assume you need the phi-node relocation similar to the one used
in "dead code elimination using ssa". That will get merge the block
with phi node in it.

> just different code. But the context checking is quite limited and see now
> a path where the context could differ. I practice they won't differ and with
> previous code the context checking saw that because this patch was
> unexisting due to more aggressive merge of BB.

Interesting.Context checking is very sensitive and give a lot of false
positives.

> One way to see at it is this is a false warning that appears because
> of a lack of BB optimizations.
> I've a vague idea of what can be done here. I'll look at it later, this evening.

Thanks. I will take a look at your patches series.

Chris

Re: [PATCH 06/29] topasm: top-level asm is special

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
>
> +       if (!sym->ident) {      // top-level asm

Maybe here we should check the statement is really top-level asm?
Later on we might have more than top-level asm as with sym->ident == NULL.

Chris

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Here by 'simple' we really mean 'worth of putting in a register'.
>
> We select all scalar types as well as struct and unions with a
> size not bigger than a long (register).
>
> Global and static variables, variables which address have been
> taken and volatiles variables are never selected.
>
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  symbol.h | 33 +++++++++++++++++++++++++++++++++
>  1 file changed, 33 insertions(+)
>
> diff --git a/symbol.h b/symbol.h
> index 327449611..3f075c5bc 100644
> --- a/symbol.h
> +++ b/symbol.h
> @@ -407,6 +407,39 @@ static inline int is_scalar_type(struct symbol *type)
>         return 0;
>  }
>
> +static inline int is_simple_type(struct symbol *type)
...
> +       case SYM_STRUCT:
> +       case SYM_UNION:
> +               return type->bit_size <= long_ctype.bit_size;

I think the function name should be some thing along the
line of "type fits register" or is_registerable_type.

union and struct are composite types. It is a bit
confusing calling them simple, if some one just looking
at the code without look at the commit message.


Chris

Re: [PATCH 11/29] add PSEUDO_UNDEF

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Processing in the middle-end are much easier if undefined values
> have been clearly identified. Once done, we can then make
> choices like:
> - always initialize them to zero
> - allow arbitraly simplification,

Can pick arbitrate initialized value, but can't do arbitraly simplification.

The chance looks good. I need to take a crash now.

To be continue...

Chris

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Dibyendu Majumdar]

Hi Chris,

On 17 August 2017 at 05:42, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> The goal of this series is to implement and integrate to sparse
>> the method described in the paper:
>>     "Simple and Efficient Construction of Static Single Assignment Form"
>>         by Matthias Braun, Sebastian Buchwald, Sebastian Hack,
>>            Roland Leissa, Christoph Mallon and Andreas Zwinkau.
>>     cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf
>>
> BTW, how do you want your patches to be merged? Assume there is
> some feed back. Do you want to come up with V2 V3 or have them merged
> to master then come up with fix up on master?
>

Please could we avoid redoing the patch series unless there is
something fundamentally wrong with the whole series such as missing
log messages or signoffs? I would suggest that we simply apply fixes
on top of the series if needed - and indeed if you want to change
something that would enable you to apply the fix as well.

This certainly makes downstream projects such as dmrC easier to maintain.

Thanks and Regards
Dibyendu

Re: [PATCH 11/29] add PSEUDO_UNDEF

[Dibyendu Majumdar]

Hi Chris,

On 17 August 2017 at 08:30, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> Processing in the middle-end are much easier if undefined values
>> have been clearly identified. Once done, we can then make
>> choices like:
>> - always initialize them to zero
>> - allow arbitraly simplification,
>
> Can pick arbitrate initialized value, but can't do arbitraly simplification.
>

I agree with that. Perhaps a specific default value can be set?

Regards
Dibyendu

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Dibyendu Majumdar]

Hi Chris,

On 17 August 2017 at 08:19, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> Here by 'simple' we really mean 'worth of putting in a register'.
>>
>> We select all scalar types as well as struct and unions with a
>> size not bigger than a long (register).
>>
>> Global and static variables, variables which address have been
>> taken and volatiles variables are never selected.
>>
>> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
>> ---
>>  symbol.h | 33 +++++++++++++++++++++++++++++++++
>>  1 file changed, 33 insertions(+)
>>
>> diff --git a/symbol.h b/symbol.h
>> index 327449611..3f075c5bc 100644
>> --- a/symbol.h
>> +++ b/symbol.h
>> @@ -407,6 +407,39 @@ static inline int is_scalar_type(struct symbol *type)
>>         return 0;
>>  }
>>
>> +static inline int is_simple_type(struct symbol *type)
> ...
>> +       case SYM_STRUCT:
>> +       case SYM_UNION:
>> +               return type->bit_size <= long_ctype.bit_size;
>
> I think the function name should be some thing along the
> line of "type fits register" or is_registerable_type.
>
> union and struct are composite types. It is a bit
> confusing calling them simple, if some one just looking
> at the code without look at the commit message.
>

Apart from that I faced a problem with this and had to disable
STRUCT/UNION from being treated as simple types.

The problem was when generating LLVM output for
https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/eic/testcbrt.c.
I will investigate more and report back my findings.

Meanwhile I would be interested to see the results of a test with above.

Regards
Dibyendu

Re: [PATCH 11/29] add PSEUDO_UNDEF

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 6:55 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>>> Processing in the middle-end are much easier if undefined values
>>> have been clearly identified. Once done, we can then make
>>> choices like:
>>> - always initialize them to zero
>>> - allow arbitraly simplification,
>>
>> Can pick arbitrate initialized value, but can't do arbitraly simplification.
>>
>
> I agree with that. Perhaps a specific default value can be set?

I was speaking loosely to say that a lot of simplifications are possible once
the involved pseudo(s) is/are undefined.

-- Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 9:19 AM, Christopher Li <sparse@chrisli.org> wrote:
>>
>> +static inline int is_simple_type(struct symbol *type)
> ...
>> +       case SYM_STRUCT:
>> +       case SYM_UNION:
>> +               return type->bit_size <= long_ctype.bit_size;
>
> I think the function name should be some thing along the
> line of "type fits register" or is_registerable_type.
>
> union and struct are composite types. It is a bit
> confusing calling them simple, if some one just looking
> at the code without look at the commit message.

I agree it's confusing, and yes I would like a better name.
OTOH 'registrable' is not exactly the conveyed meaning.
'register' is a concept that pertains to the backend, that
is machine specific, a pseudo may need several registers
and a register can hold several pseudos, ...

Here what we really want to select is something along:
'it's interesting to see it as a flow of value' vs.
'it's better to see it as a change in state'.
And yes, very often that just correspond to registers.

Note: it's not even 'what can be put in a pseudo(-register)'
          were selecting here. It's OK to have pseudos for
          'non-simple' values, They will just be transient and we
          won't be interested in their 'flow'.

-- Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 6:59 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Apart from that I faced a problem with this and had to disable
> STRUCT/UNION from being treated as simple types.

That's only a problem/a limitation of your backend.

-- Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Dibyendu Majumdar]

Hi Luc,

On 17 August 2017 at 20:17, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Thu, Aug 17, 2017 at 6:59 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> Apart from that I faced a problem with this and had to disable
>> STRUCT/UNION from being treated as simple types.
>
> That's only a problem/a limitation of your backend.
>

Possibly - I haven't checked yet. Are you able to generate code / and
run the test case using your LLVM backend?

Regards
Dibyendu

Re: [PATCH 06/29] topasm: top-level asm is special

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 8:49 AM, Christopher Li <sparse@chrisli.org> wrote:
>>
>> +       if (!sym->ident) {      // top-level asm
>
> Maybe here we should check the statement is really top-level asm?
> Later on we might have more than top-level asm as with sym->ident == NULL.

Sure but it's currently how they must be detected.

In fact (like the name may suggest) this patch is part of a series
that better deal with top-level asm (they are not really statement!').
For example, top-level asm must be parsed as basic asm and not
extended asm.

So yes, I totally agree, but not now.

-- Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 9:21 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>>> Apart from that I faced a problem with this and had to disable
>>> STRUCT/UNION from being treated as simple types.
>>
>> That's only a problem/a limitation of your backend.
>>
>
> Possibly - I haven't checked yet. Are you able to generate code / and
> run the test case using your LLVM backend?

Possibly not but you're the only use of the LLVM backend, so it's yours ;)

-- Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Dibyendu Majumdar]

Hi Luc,

On 17 August 2017 at 20:25, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Thu, Aug 17, 2017 at 9:21 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>>> Apart from that I faced a problem with this and had to disable
>>>> STRUCT/UNION from being treated as simple types.
>>>
>>> That's only a problem/a limitation of your backend.
>>>
>>
>> Possibly - I haven't checked yet. Are you able to generate code / and
>> run the test case using your LLVM backend?
>
> Possibly not but you're the only use of the LLVM backend, so it's yours ;)
>

I will check at my end and revert with my thoughts.

But I would have preferred if the SSA change was like for like
initially - rather than introducing new breaking changes. That should
ideally come as patches later on.

Regards
Dibyendu

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 7:58 AM, Christopher Li <sparse@chrisli.org> wrote:
>
> Speaking of which, can you do me a favor bump the -rc5 to finial?
> Just drop the "-rc5" part in Makefile. Let's release the 0.5.1 and
> start merging patches :-)

Sure, just gives me a moment, please.

Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 6:59 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Apart from that I faced a problem with this and had to disable
> STRUCT/UNION from being treated as simple types.
>
> The problem was when generating LLVM output for
> https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/eic/testcbrt.c.
> I will investigate more and report back my findings.

There is indeed a problem with this case. It seems there is a mixup
with types somewhere and sparse-llvm needs a few lines more.

I'll look at it in the following days.

-- Luc

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 8:16 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Thu, Aug 17, 2017 at 2:09 AM, Luc Van Oostenryck wrote:
>
> I assume you need the phi-node relocation similar to the one used
> in "dead code elimination using ssa". That will get merge the block
> with phi node in it.

No, it doesn't seems to be related. It's a miised opportunity of
'try_to_simplify_bb()'.

One of the patches in my complete series solves it (and, it seems,
the other differences too but I didn't yet checked it thoroughly).
It's totally independent of the series, I can send it just after the
series.

>> just different code. But the context checking is quite limited and see now
>> a path where the context could differ. I practice they won't differ and with
>> previous code the context checking saw that because this patch was
>> unexisting due to more aggressive merge of BB.
>
> Interesting.Context checking is very sensitive and give a lot of false
> positives.

Yes, but of course, the general case is impossible to have correctly.

-- Luc

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Luc Van Oostenryck]

On Thu, Aug 17, 2017 at 7:58 AM, Christopher Li <sparse@chrisli.org> wrote:
>>> ssa-mini-v1:
>>> 1205.82user 463.65system 1:16.97elapsed 2168%CPU (0avgtext+0avgdata
>>> 536216maxresident)k
>>> 0inputs+12824outputs (0major+132162996minor)pagefaults 0swaps
>>> 1206.35user 463.27system 1:16.95elapsed 2169%CPU (0avgtext+0avgdata
>>> 536296maxresident)k
>>> 0inputs+12824outputs (0major+132156314minor)pagefaults 0swaps
>>>
>>> This is the rc5 as base line.
>>> 1173.42user 453.56system 1:15.21elapsed 2163%CPU (0avgtext+0avgdata
>>> 238072maxresident)k
>>> 0inputs+12784outputs (0major+128858147minor)pagefaults 0swaps
>>> 1172.86user 453.53system 1:15.14elapsed 2164%CPU (0avgtext+0avgdata
>>> 238076maxresident)k
>>> 0inputs+12784outputs (0major+128858804minor)pagefaults 0swaps
>>>
>>> So the ssa-mini-v1 is about 2% slower than the current rc5.
>>
>> I wonder what would be these numbers if you measured:
>> 1) r5 + removal of simplify_loads()
> 1170.54user 453.61system 1:15.05elapsed 2164%CPU (0avgtext+0avgdata
> 238104maxresident)k
> 0inputs+12792outputs (0major+128794771minor)pagefaults 0swaps
> 1172.00user 452.53system 1:14.96elapsed 2166%CPU (0avgtext+0avgdata
> 238076maxresident)k
> 0inputs+12784outputs (0major+128795134minor)pagefaults 0swaps
>
>> 2) r5 + sssa-mini-v1 (which includes the removal).
> 1205.84user 463.12system 1:16.84elapsed 2171%CPU (0avgtext+0avgdata
> 536300maxresident)k
> 0inputs+12824outputs (0major+132152193minor)pagefaults 0swaps
> 1204.59user 462.09system 1:16.77elapsed 2170%CPU (0avgtext+0avgdata
> 536132maxresident)k
> 0inputs+12824outputs (0major+132160134minor)pagefaults 0swaps


Interesting and strange.
This doesn't really correspond to the numbers I have here.
Not at all, in fact, but I have only some rough measurements.

I'll look at that tomorrow or so.

-- Luc

Re: [PATCH 06/29] topasm: top-level asm is special

[Christopher Li]

On Thu, Aug 17, 2017 at 3:22 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Sure but it's currently how they must be detected.
>
> In fact (like the name may suggest) this patch is part of a series
> that better deal with top-level asm (they are not really statement!').
> For example, top-level asm must be parsed as basic asm and not
> extended asm.
>
> So yes, I totally agree, but not now.

Yes. I haven't finish looking at your series yet.  Still working on it.

Chris

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Christopher Li]

On Thu, Aug 17, 2017 at 3:14 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> I agree it's confusing, and yes I would like a better name.
> OTOH 'registrable' is not exactly the conveyed meaning.
> 'register' is a concept that pertains to the backend, that
> is machine specific, a pseudo may need several registers
> and a register can hold several pseudos, ...

Sure, I saw your new name some thing like promote-able.
That is good.

>
> Here what we really want to select is something along:
> 'it's interesting to see it as a flow of value' vs.
> 'it's better to see it as a change in state'.
> And yes, very often that just correspond to registers.
>
> Note: it's not even 'what can be put in a pseudo(-register)'
>           were selecting here. It's OK to have pseudos for
>           'non-simple' values, They will just be transient and we
>           won't be interested in their 'flow'.

We need to be very careful about composite type pointer alias.
Any pointer alias to the member of the struct need to take
into account as well.

Chris

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Christopher Li]

On Thu, Aug 17, 2017 at 3:28 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> I will check at my end and revert with my thoughts.
>
> But I would have preferred if the SSA change was like for like
> initially - rather than introducing new breaking changes. That should
> ideally come as patches later on.

I just realized another side effect of doing the SSA conversion on
the AST directly. It means we will not have access to the linearization
byte code before promoting the memory variable to pseudo.

If you are depending on that pre-simplified byte code, then you don't
have a choice not do it. Maybe later on we can consider an option to
avoid doing the SSA conversion on memory variable as an option.

Chris

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 6:13 PM, Christopher Li <sparse@chrisli.org> wrote:
>>
>> Note: it's not even 'what can be put in a pseudo(-register)'
>>           were selecting here. It's OK to have pseudos for
>>           'non-simple' values, They will just be transient and we
>>           won't be interested in their 'flow'.
>
> We need to be very careful about composite type pointer alias.

There are only pointer aliases if there are pointers. Here, we're only
interested in local variables.

But, and thanks to this remarks, I added a test and realized that
contrary to what I thought, the MOD_ADDRESSABLE is *not*
propagated from member to parent. So for the moment, I'll need
to drop this and only look at pure scalar variables. It's annoying.

-- Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 6:18 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> I just realized another side effect of doing the SSA conversion on
> the AST directly. It means we will not have access to the linearization
> byte code before promoting the memory variable to pseudo.

Of course.
But consider the other side: it means that you already have already
a lot of variables promoted to pseudo *while* doing the linearization.
It means that you already can know quite a bit about the 'values'
during linearization and avoid to generate code that will be thrown
away soon after being created.

> Maybe later on we can consider an option to
> avoid doing the SSA conversion on memory variable as an option.

Sure, but it's a serious research topic too.
Lots can be done. A few things are easy and cheap, most are quite
complex and expensive.

-- Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Dibyendu Majumdar]

Hi Chris,

On 18 August 2017 at 17:18, Christopher Li <sparse@chrisli.org> wrote:
> On Thu, Aug 17, 2017 at 3:28 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> I will check at my end and revert with my thoughts.
>>
>> But I would have preferred if the SSA change was like for like
>> initially - rather than introducing new breaking changes. That should
>> ideally come as patches later on.
>
> I just realized another side effect of doing the SSA conversion on
> the AST directly. It means we will not have access to the linearization
> byte code before promoting the memory variable to pseudo.
>
> If you are depending on that pre-simplified byte code, then you don't
> have a choice not do it. Maybe later on we can consider an option to
> avoid doing the SSA conversion on memory variable as an option.
>

I have it setup so that if optimization is switched off I skip the CSE
/ Flow Simplification steps. In the older version the
simplify_symbol_usage() was also being skipped but that is not used
now. (Although the way I have merged this - I have the old code still
there, and I can switch between the two implementations using a
#define).

As all my LLVM tests pass in this setup this is fine right now. I
still get failures in some cases when the other subsequent stages are
enabled - so there must be some incorrect simplifications occurring
somewhere. I do not yet have specific tests to track down where the
issues are.

As I mentioned before - ideally it would be good have a SSA step that
is reusable. Then you could run this step several times during the
process - and allow some simplification phases to generate non SSA
code. Perhaps the new SSA approach can be adapted for this. This would
also allow access to the first pass linearized output without
promotion to pseudos.

But this should not stop us from moving forward with this change - as
I think the SSA hooks into the linearization step are pretty specific
and it should be relatively easy to have a mode where those steps are
"dummied" - i.e. do nothing.

I have a question though. For my other backend I need liveness
analysis done even if I skip the other steps. Is it okay to run the
liveness analysis phase while skipping the CSE / Flow simplification
phases?

Regards
Dibyendu

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Christopher Li]

On Fri, Aug 18, 2017 at 2:15 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> I have it setup so that if optimization is switched off I skip the CSE
> / Flow Simplification steps. In the older version the
> simplify_symbol_usage() was also being skipped but that is not used
> now. (Although the way I have merged this - I have the old code still
> there, and I can switch between the two implementations using a
> #define).
>
> As all my LLVM tests pass in this setup this is fine right now. I
> still get failures in some cases when the other subsequent stages are
> enabled - so there must be some incorrect simplifications occurring
> somewhere. I do not yet have specific tests to track down where the
> issues are.

At the point the SSA code is not merge yet. After we merger it.
report back if you found some issue using the llvm back end.

>
> As I mentioned before - ideally it would be good have a SSA step that
> is reusable. Then you could run this step several times during the
> process - and allow some simplification phases to generate non SSA
> code. Perhaps the new SSA approach can be adapted for this. This would
> also allow access to the first pass linearized output without
> promotion to pseudos.

As the way this ssa conversion is implement. I actually don't know
how hard it is to skip the promotion. I haven't look to that part of
the code yet. I image there will be a test if this variable has been
taking address or not. If so, it can't directly promote to pseudo without
the load/store. That would be one possible place to insert the option
to disable this. But again, let me look at the code first.

> But this should not stop us from moving forward with this change - as
> I think the SSA hooks into the linearization step are pretty specific
> and it should be relatively easy to have a mode where those steps are
> "dummied" - i.e. do nothing.
>
> I have a question though. For my other backend I need liveness
> analysis done even if I skip the other steps. Is it okay to run the
> liveness analysis phase while skipping the CSE / Flow simplification
> phases?

You can, but it is less effective. You will see a lot of load/store into the
memory. SSA make it easy to trace the define and usage chain.
Without that you can't really see well what is going on with the content
of the memory.

Chris

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 8:35 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> As the way this ssa conversion is implement. I actually don't know
> how hard it is to skip the promotion.

It's very easy, you just need for is_promotable() to always return
false. But really, what would be the point?

The points that matter to me are:
1) generate correct SSA information.
    This is ultra-important because with incorrect SSA
     a lot of the optimizations are wrong, introduce errors
     and infinite loops or need ugly workarounds.
2) correct any other issues sparse could have with the generated IR
3) correct any errors sparse could have with an optimization
4) add support for construct sparse doesn't support yet
5) add more features, make the sparse's code more efficient
    and the generated IR too.
5') do not forget that sparse is firstly the/a C checker for the kernel
    (and others projects).

>> I have a question though. For my other backend I need liveness
>> analysis done even if I skip the other steps. Is it okay to run the
>> liveness analysis phase while skipping the CSE / Flow simplification
>> phases?
>
> You can, but it is less effective. You will see a lot of load/store into the
> memory. SSA make it easy to trace the define and usage chain.
> Without that you can't really see well what is going on with the content
> of the memory.

Indeed, but I'm not very sure about Dibyendu's question here.
You can have promoted all possible memory accesses to pseudos
and still generating totally un-optimized code because you skipped
the CSE and all others optimizations. It's two largely orthogonal
things.

-- Luc

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Christopher Li]

On Fri, Aug 18, 2017 at 3:21 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> It's very easy, you just need for is_promotable() to always return
> false. But really, what would be the point?

I was mostly thinking debugging and verification purpose.
AST to linearized byte code without the SSA conversion of
memory variable is very straight forward.

Also, I just realized that, promoting memory access into SSA
pseudo is actually not avoidable at instruction level. After CSE
and flow optimization, there might open up new chance to
promote local variable into SSA form. We might need some code
to promote memory access to SSA pseudo from instruction level
any way.

> The points that matter to me are:
> 1) generate correct SSA information.
>     This is ultra-important because with incorrect SSA
>      a lot of the optimizations are wrong, introduce errors
>      and infinite loops or need ugly workarounds.

That I totally agree. Incorrect SSA can't not use as SSA at all.

> 2) correct any other issues sparse could have with the generated IR
> 3) correct any errors sparse could have with an optimization
> 4) add support for construct sparse doesn't support yet
> 5) add more features, make the sparse's code more efficient
>     and the generated IR too.

All agree.

> 5') do not forget that sparse is firstly the/a C checker for the kernel
>     (and others projects).

Sure. But sparse need to get good IR to perform the checking.

Chris

Re: [PATCH 09/29] add helper to test if a variable is "simple"

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 10:14 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Fri, Aug 18, 2017 at 3:21 PM, Luc Van Oostenryck wrote:
>
>> The points that matter to me are:
>> 1) generate correct SSA information.
>>     This is ultra-important because with incorrect SSA
>>      a lot of the optimizations are wrong, introduce errors
>>      and infinite loops or need ugly workarounds.
>
> That I totally agree. Incorrect SSA can't not use as SSA at all.
>
>> 2) correct any other issues sparse could have with the generated IR
>> 3) correct any errors sparse could have with an optimization
>> 4) add support for construct sparse doesn't support yet
>> 5) add more features, make the sparse's code more efficient
>>     and the generated IR too.
>
> All agree.
>
>> 5') do not forget that sparse is firstly the/a C checker for the kernel
>>     (and others projects).
>
> Sure. But sparse need to get good IR to perform the checking.

Hence, points 2 & 3 :)

-- Luc

Re: [PATCH 13/29] add insert_phi_node()

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> +pseudo_t insert_phi_node(struct basic_block *bb, struct symbol *type)
> +{
> +       struct instruction *phi_node = alloc_typed_instruction(OP_PHI, type);
> +       struct instruction *insn;
> +       pseudo_t phi;
> +
> +       phi = alloc_pseudo(phi_node);
> +       phi_node->target = phi;
> +       phi_node->bb = bb;
> +
> +       FOR_EACH_PTR(bb->insns, insn) {
> +               enum opcode op = insn->opcode;
> +               if (op == OP_ENTRY || op == OP_PHI)
> +                       continue;
> +               INSERT_CURRENT(phi_node, insn);

You do need to preserve the order of the phi node, right?
At first I was thinking always insert the phi at the first instruction.
Then I realized that, it is possible some phi node use some other
phi node as source in case of a loop. So the order does need
to be preserved some how.

> +               return phi;
> +       } END_FOR_EACH_PTR(insn);
> +
> +       add_instruction(&bb->insns, phi_node);
> +       return phi;
> +}
> +


Chris

Re: [PATCH 15/29] add remove_use()

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Add an helper to remove the usage of a pseudo, like kill_use()
> do but unlike kill_use(), without trying to kill (recursively!)
> the defining instruction if the usage drop to zero.
>
>
> +/*
> + * Like kill_use() but do not recursively kill instructions
> + * that become without users.
> + */
> +void remove_use(pseudo_t *usep)

remove_use() vs remove_usage() in the above code look a bit
too close to tell apart. This two have total different behavior
not reflecting in the name.

I was confused there for a second. That is before I notice the
subtle different between remove_use() vs remove_usage()

Chris

Re: [PATCH 13/29] add insert_phi_node()

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 10:39 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> You do need to preserve the order of the phi node, right?
> At first I was thinking always insert the phi at the first instruction.
> Then I realized that, it is possible some phi node use some other
> phi node as source in case of a loop. So the order does need
> to be preserved some how.

It's not needed because:
1) phi-nodes need to have 'parallel-assignment' semantics anyway
    like in languages where you can write 'a, b = b, a' to exchange
    two variables. In other words, if the order would matter it would
    be a bug.
2) you can never have (the target of) a phi-node (OP_PHI)
    as another phi-node' source because all such sources are
    created by OP_PHISOURCEs.

-- Luc

Re: [PATCH 17/29] ptrmap: core implementation

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The implementation done in this patch is a very simple one
> based on list of blocks of key-value pairs.
>
> The idea being to later switch to a dynamic structure using
> a hash-table as soon as the number of element reach some threshold.
> However, these hash-table are only needed for some huge
> and artificial input files.
>
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  Makefile |  1 +
>  ptrmap.c | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  ptrmap.h | 12 ++++++++++
>  3 files changed, 97 insertions(+)
>  create mode 100644 ptrmap.c
>  create mode 100644 ptrmap.h
>
> diff --git a/Makefile b/Makefile
> index 48e1f508f..762aee505 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -117,6 +117,7 @@ LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
>           expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \
>           char.o sort.o allocate.o compat-$(OS).o ptrlist.o \
>           builtin.o \
> +         ptrmap.o \
>           stats.o \
>           flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
>
> diff --git a/ptrmap.c b/ptrmap.c
> new file mode 100644
> index 000000000..2a08380c9
> --- /dev/null
> +++ b/ptrmap.c
> @@ -0,0 +1,84 @@
> +#include "ptrmap.h"
> +#include "allocate.h"
> +#include <stddef.h>
> +
> +#define        MAP_NR  7
> +
> +struct ptrpair {
> +       void *key;
> +       void *val;
> +};
> +struct ptrmap {
> +       struct ptrmap *next;
> +       int nr;
> +       struct ptrpair pairs[MAP_NR];
> +};

If you are going for simple. why not just make
struct ptrpair as allocatable object then have
struct ptrpair_list as normal ptrlist?

The add would be normal ptrlist add.
The lookup is just FOREACH_PTR loop.
The update is lookup then change the value.

That could safe you some code. The difference
will be, your current ptrlist has better cache
behavior. But if you care that much then it should
move to hash implementation


Chris

Re: [PATCH 13/29] add insert_phi_node()

[Christopher Li]

On Fri, Aug 18, 2017 at 4:52 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Fri, Aug 18, 2017 at 10:39 PM, Christopher Li <sparse@chrisli.org> wrote:
>>
>
> It's not needed because:
> 1) phi-nodes need to have 'parallel-assignment' semantics anyway
>     like in languages where you can write 'a, b = b, a' to exchange
>     two variables. In other words, if the order would matter it would
>     be a bug.

I need to think more about that.

> 2) you can never have (the target of) a phi-node (OP_PHI)
>     as another phi-node' source because all such sources are
>     created by OP_PHISOURCEs.

I see. So that means you can just insert into the first instruction?

Chris

Re: [PATCH 22/29] sssa: add seal_gotos() needed to seal BBs targeted by gotos

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> +void seal_gotos(struct entrypoint *ep)
> +{
> +       struct basic_block *bb;
> +
> +       FOR_EACH_PTR(ep->bbs, bb) {
> +               if (bb->sealed)
> +                       continue;
> +               if (bb->unsealable)
> +                       bb->unsealable = 0;
> +               seal_bb(bb);
> +       } END_FOR_EACH_PTR(bb);
> +
> +       // cleanup these fields as they are aliased to ::needs & ::defines
> +       FOR_EACH_PTR(ep->bbs, bb) {
> +               bb->sealed = bb->unsealable = 0;

I think if you want bb->needs and bb->define to zero.
Best directly assign bb->needs && bb->defines to zero;

I am not sure C stander how to deal with the unused bit field
parts. If I recall correctly a lot of bit-field related stuff are implementation
define. So setting bb->sealed and bb->unsealable might not be enough
to make bb->needs zero.

Chris

Re: [PATCH 17/29] ptrmap: core implementation

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 11:02 PM, Christopher Li <sparse@chrisli.org> wrote:

>
> If you are going for simple. why not just make
> struct ptrpair as allocatable object then have
> struct ptrpair_list as normal ptrlist?

A bit less memory and one indirection less.

> The add would be normal ptrlist add.
> The lookup is just FOREACH_PTR loop.
> The update is lookup then change the value.
>
> That could safe you some code. The difference
> will be, your current ptrlist has better cache
> behavior. But if you care that much then it should
> move to hash implementation

It will be done soon.

-- Luc

Re: [PATCH 13/29] add insert_phi_node()

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 11:17 PM, Christopher Li <sparse@chrisli.org> wrote:

>> 2) you can never have (the target of) a phi-node (OP_PHI)
>>     as another phi-node' source because all such sources are
>>     created by OP_PHISOURCEs.
>
> I see. So that means you can just insert into the first instruction?

Yes, you would also, for example, add a list in the BB and just add
them in this list in any order. They are not really instructions, the best
way to see them in the see them in a kind of BB prologue where they
(virtually) select the value for their target pseudo (and if you know for
 sure from which patch the BB will always come, you can remove them
completely.On the other hand, it' an error when merging BB to leave
a phi-node in the middle of the new bigger BB, it needs special care
but also often it doesn't matter).

-- Luc

Re: [PATCH 22/29] sssa: add seal_gotos() needed to seal BBs targeted by gotos

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 11:26 PM, Christopher Li <sparse@chrisli.org> wrote:

> I think if you want bb->needs and bb->define to zero.
> Best directly assign bb->needs && bb->defines to zero;
>
> I am not sure C stander how to deal with the unused bit field
> parts. If I recall correctly a lot of bit-field related stuff are implementation
> define. So setting bb->sealed and bb->unsealable might not be enough
> to make bb->needs zero.

You're right.
I'm planning to move them away anyway with .nr & a new field.

-- Luc

Re: [PATCH 28/29] sssa: switch to the new SSA construction

[Christopher Li]

On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This patch makes the needed changes in the linearization
> to use the new SA construction method.

You mean SSA construction method :-)

Chris

Re: [PATCH 28/29] sssa: switch to the new SSA construction

[Luc Van Oostenryck]

On Fri, Aug 18, 2017 at 11:47 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck wrote:

>> to use the new SA construction method.
>
> You mean SSA construction method :-)

I'm used to more often use 'SSSA' for Simple SSA and thus refering
the method & implementation. Here I removed one more 'S'.

-- Luc

Re: [PATCH 00/29] Simple & Efficient SSA construction.

[Christopher Li]

On Thu, Aug 17, 2017 at 4:04 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Interesting and strange.
> This doesn't really correspond to the numbers I have here.
> Not at all, in fact, but I have only some rough measurements.
>
Just let me know if you need to get more number.
My new server is itchy to compile stuff :-)

The good thing about this server is that it does not do
CPU frequency scale due to CPU over heating.
So the number is very consistent.

I can kind of see why your patch is slightly slow
now. It allocate more phi nodes and remove them later.
Also there is the overhead of the ptrmap. Both of
those cause extra memory allocation, as we learn in the
ptrlist node size case, it can slow things down a bit.


Chris