[RFC PATCH 00/48] fix promotion of symbol to register

[RFC PATCH 00/48] fix promotion of symbol to register

[Luc Van Oostenryck]

This series fixes the promotion of symbols accesses from
memory to pseudos.
The fix in itself is in the few of the last patches (40-43)
but is preceded by an extensive rework of the whole thing.

As is, it seems to work quite well and of course more
accesses are promoted than the Simple SSA was able to do
(SSSA only cared about purely local vars of which the address
was never ever taken).

For performance, the situation is highly dependent on the
type of code: the amount of work that is done in
simplify_loads() can easily take 80% of the time for complex
files.

Warning 1: this is for review & testing only
Warning 2: it's not (yet) bissectable between patches 40 & 43
Warning 3: simplify_loads is still broken and will need the same
           fix (but the code is currently disabled)


This series is  available in the git repository at:

  git://github.com/lucvoo/sparse.git mem2reg


Luc Van Oostenryck (48):
      remove wrong part of simplify_loads()
      remove trivial phi-nodes during clean_up_phi()
      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 PSEUDO_UNDEF
      add undef_pseudo()
      add insert_phi_node()
      extract alloc_phisrc() from alloc_phi()
      add remove_use()
      rename 'struct warning' to 'struct flag'
      let handle_simple_switch() handle an array of flags
      dump-ir: rename -fdump-linearize to -fdump-ir
      dump-ir: use defines
      dump-ir: add an helper to parse sub-options
      dump-ir: make it more flexible
      sssa: move simplify_one_symbol() to a separate file
      mem2reg: rename to use 'promote' instead of 'simplify'
      mem2reg: simplify check of modifiers for external visibility
      mem2reg: extract externaly_visible()
      mem2reg: reorg externaly_visible() returns
      mem2reg: ignore all killed instructions
      mem2reg: extract kill_pseudo_stores()
      mem2reg: extract kill_pseudo_dominated_stores()
      mem2reg: extract kill_pseudo_dead_stores()
      mem2reg: remove one indent level
      mem2reg: add comment to find_dominating_stores()
      mem2reg: add flags to enable/disable some parts
      mem2reg: rename the other kill_dominated_stores()
      mem2reg: move rewrite_load_instruction() here
      mem2reg: be clear that we're using a symbol/var
      mem2reg: be clear that we're using a symbol/var here too
      mem2reg: add description for find_dominating_parents()
      mem2reg: let rewrite_load_instruction() take the symbol as arg
      mem2reg: remove check phisrc_in_bb()
      mem2reg: delay the creation of phi-sources
      mem2reg: make rewrite_load_instruction() functional
      mem2reg: rename one->target to dom
      mem2reg: get recursion right
      mem2reg: don't check dominance by removed instructions
      mem2reg: update copyright
      mem2reg: allow dumping IR
      mem2reg: add some small test cases
      mem2reg: don't promote unused or already promoted vars

 Makefile                                |   1 +
 cgcc                                    |   2 +-
 flow.c                                  | 362 -------------------------
 flow.h                                  |   4 +-
 lib.c                                   | 102 +++++--
 lib.h                                   |  11 +-
 linearize.c                             | 101 +++++--
 linearize.h                             |   8 +-
 mem2reg.c                               | 453 ++++++++++++++++++++++++++++++++
 memops.c                                |  85 ++----
 simplify.c                              |  69 +++--
 sparse-llvm.c                           |   4 +
 sparse.1                                |  30 ++-
 validation/bad-return-type.c            |  19 ++
 validation/incomplete-struct.c          |  23 ++
 validation/kill-casts.c                 |   1 -
 validation/kill-phi-ttsbb.c             |   2 +-
 validation/linear/bitfield-init-mask.c  |   2 +-
 validation/loop-linearization.c         |  60 ++---
 validation/mem2reg/global-direct00.c    |  24 ++
 validation/mem2reg/local-addr-taken00.c |  21 ++
 validation/mem2reg/local-direct00.c     |  20 ++
 validation/optim/trivial-phis.c         |  15 ++
 23 files changed, 883 insertions(+), 536 deletions(-)
 create mode 100644 mem2reg.c
 create mode 100644 validation/bad-return-type.c
 create mode 100644 validation/incomplete-struct.c
 create mode 100644 validation/mem2reg/global-direct00.c
 create mode 100644 validation/mem2reg/local-addr-taken00.c
 create mode 100644 validation/mem2reg/local-direct00.c
 create mode 100644 validation/optim/trivial-phis.c

[RFC PATCH 01/48] 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

[RFC PATCH 02/48] remove trivial phi-nodes during clean_up_phi()

[Luc Van Oostenryck]

In a set of related phi-nodes and phi-sources
if all phi-sources but one correspond to the target of one
of the phi-sources, then no phi-nodes is needed and all
%phis can be replaced by the unique source.
For example, if we have something like:
	foo:
		phisrc.32   %phi1 <- %arg1
		br          .L1
	.L1:
		phi.32      %r2 <- %phi1, %phi2
		phisrc.32   %phi2 <- %r2
		...
we can see that %phi2 is the target of the phi-node that use it
thus neither %phi2 nor %r2 are completly inter-dependent and the
only true soure is %arg1. In this case %r2 can be replaced by
%arg1 and the phi-node can be removed as well as its phi-sources.

There are also more complex cases with several inter-related
phi-nodes, the source of a phi-node being defined by another
phi-node. Like for the simple case, if there is only a single
independent source, all the related phi-nodes can be replaced by
this unique true source and the the phi-sources can be removed.

Removing these trivial phi-nodes will usually trigger other
simplifications, especially those concerning the CFG.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                      | 56 ++++++++++++++++++++++++++++-------------
 validation/optim/trivial-phis.c | 15 +++++++++++
 2 files changed, 54 insertions(+), 17 deletions(-)
 create mode 100644 validation/optim/trivial-phis.c

diff --git a/simplify.c b/simplify.c
index 2bc86f53e..766ac451d 100644
--- a/simplify.c
+++ b/simplify.c
@@ -133,37 +133,59 @@ static int if_convert_phi(struct instruction *insn)
 	return REPEAT_CSE;
 }
 
-static int clean_up_phi(struct instruction *insn)
+static int trivial_phi(pseudo_t *same, struct instruction *insn, struct pseudo_list **list)
 {
+	pseudo_t target = insn->target;
 	pseudo_t phi;
-	struct instruction *last;
-	int same;
 
-	last = NULL;
-	same = 1;
+	assert(insn->opcode == OP_PHI);
+
+	if (pseudo_in_list(*list, target))
+		return 1;
+	add_pseudo(list, target);
+
 	FOR_EACH_PTR(insn->phi_list, phi) {
 		struct instruction *def;
+		pseudo_t src;
+
 		if (phi == VOID)
 			continue;
 		def = phi->def;
-		if (def->src1 == VOID || !def->bb)
+		assert(def->bb);
+		if (!def->bb)
 			continue;
-		if (last) {
-			if (last->src1 != def->src1)
-				same = 0;
+
+		src = def->src;	// bypass OP_PHISRC & get the real source
+
+		if (src == VOID || src == target || src == *same)
+			continue;
+		if (!*same) {
+			*same = src;
 			continue;
 		}
-		last = def;
+		if (src->type == PSEUDO_REG && src->def->opcode == OP_PHI) {
+			if (trivial_phi(same, src->def, list))
+				continue;
+		}
+		return 0;
 	} END_FOR_EACH_PTR(phi);
 
-	if (same) {
-		pseudo_t pseudo = last ? last->src1 : VOID;
-		convert_instruction_target(insn, pseudo);
-		kill_instruction(insn);
-		return REPEAT_CSE;
-	}
+	return 1;
+}
+
+static int clean_up_phi(struct instruction *insn)
+{
+	struct pseudo_list *list = NULL;
+	pseudo_t same = NULL;
+
+	if (!trivial_phi(&same, insn, &list))
+		return if_convert_phi(insn);
 
-	return if_convert_phi(insn);
+	if (!same)
+		same = VOID;
+	convert_instruction_target(insn, same);
+	kill_instruction(insn);
+	return REPEAT_CSE;
 }
 
 static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
diff --git a/validation/optim/trivial-phis.c b/validation/optim/trivial-phis.c
new file mode 100644
index 000000000..9cb9a2c78
--- /dev/null
+++ b/validation/optim/trivial-phis.c
@@ -0,0 +1,15 @@
+void foo(int *p)
+{
+	int a = *p;
+	while (1)
+		a ^= 0;
+}
+
+/*
+ * check-name: trivial phis
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ * check-output-excludes: phi\\.
+ * check-output-excludes: phisrc\\.
+ * check-output-end
+ */
-- 
2.14.0

[RFC PATCH 03/48] 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

[RFC PATCH 04/48] 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

[RFC PATCH 05/48] 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

[RFC PATCH 06/48] 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

[RFC PATCH 07/48] 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

[RFC PATCH 08/48] 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

[RFC PATCH 09/48] 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

[RFC PATCH 10/48] 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 3a1bc74ed..aadecfc5d 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

[RFC PATCH 11/48] 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 aadecfc5d..3ef65d585 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

[RFC PATCH 12/48] 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 3ef65d585..4f4102af7 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

[RFC PATCH 13/48] 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 4f4102af7..6cf97a42e 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

[RFC PATCH 14/48] 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 766ac451d..cea903a24 100644
--- a/simplify.c
+++ b/simplify.c
@@ -224,6 +224,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

[RFC PATCH 15/48] rename 'struct warning' to 'struct flag'

[Luc Van Oostenryck]

'struct warning' can be reused for flags other than warnings.

To avoid future confusion, rename it to something more general:
'struct flag' (which in its context, handling of compiler flags,
is clear enough).

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

diff --git a/lib.c b/lib.c
index 73e9a2fe6..f847d1aba 100644
--- a/lib.c
+++ b/lib.c
@@ -506,7 +506,7 @@ static char **handle_switch_o(char *arg, char **next)
 	return next;
 }
 
-static const struct warning {
+static const struct flag {
 	const char *name;
 	int *flag;
 } warnings[] = {
@@ -551,7 +551,7 @@ enum {
 };
 
 
-static char **handle_onoff_switch(char *arg, char **next, const struct warning warnings[], int n)
+static char **handle_onoff_switch(char *arg, char **next, const struct flag warnings[], int n)
 {
 	int flag = WARNING_ON;
 	char *p = arg + 1;
@@ -593,7 +593,7 @@ static char **handle_switch_W(char *arg, char **next)
 	return next;
 }
 
-static struct warning debugs[] = {
+static struct flag debugs[] = {
 	{ "entry", &dbg_entry},
 	{ "dead", &dbg_dead},
 };
@@ -612,7 +612,7 @@ static char **handle_switch_v(char *arg, char **next)
 	return next;
 }
 
-static struct warning dumps[] = {
+static struct flag dumps[] = {
 	{ "D", &dump_macro_defs},
 };
 
@@ -626,7 +626,7 @@ static char **handle_switch_d(char *arg, char **next)
 }
 
 
-static void handle_onoff_switch_finalize(const struct warning warnings[], int n)
+static void handle_onoff_switch_finalize(const struct flag warnings[], int n)
 {
 	unsigned i;
 
-- 
2.14.0

[RFC PATCH 16/48] let handle_simple_switch() handle an array of flags

[Luc Van Oostenryck]

This was used to handle a single flag but we need something
more compact when we need to handle several flags.

So, adapt this helper so that it now takes an array of flags
instead of a single flag.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 lib.c | 32 ++++++++++++++++++++------------
 1 file changed, 20 insertions(+), 12 deletions(-)

diff --git a/lib.c b/lib.c
index f847d1aba..c46798d0f 100644
--- a/lib.c
+++ b/lib.c
@@ -476,7 +476,12 @@ static void handle_arch_finalize(void)
 }
 
 
-static int handle_simple_switch(const char *arg, const char *name, int *flag)
+struct flag {
+	const char *name;
+	int *flag;
+};
+
+static int handle_simple_switch(const char *arg, const struct flag *flags)
 {
 	int val = 1;
 
@@ -486,9 +491,11 @@ static int handle_simple_switch(const char *arg, const char *name, int *flag)
 		val = 0;
 	}
 
-	if (strcmp(arg, name) == 0) {
-		*flag = val;
-		return 1;
+	for (; flags->name; flags++) {
+		if (strcmp(arg, flags->name) == 0) {
+			*flags->flag = val;
+			return 1;
+		}
 	}
 
 	// not handled
@@ -506,10 +513,7 @@ static char **handle_switch_o(char *arg, char **next)
 	return next;
 }
 
-static const struct flag {
-	const char *name;
-	int *flag;
-} warnings[] = {
+static const struct flag warnings[] = {
 	{ "address", &Waddress },
 	{ "address-space", &Waddress_space },
 	{ "bitwise", &Wbitwise },
@@ -737,10 +741,18 @@ err:
 	die("error: unknown flag \"-fdump-%s\"", arg);
 }
 
+static struct flag fflags[] = {
+	{ "mem-report",			&fmem_report },
+	{ },
+};
+
 static char **handle_switch_f(char *arg, char **next)
 {
 	arg++;
 
+	if (handle_simple_switch(arg, fflags))
+		return next;
+
 	if (!strncmp(arg, "tabstop=", 8))
 		return handle_switch_ftabstop(arg+8, next);
 	if (!strncmp(arg, "dump-", 5))
@@ -748,10 +760,6 @@ static char **handle_switch_f(char *arg, char **next)
 	if (!strncmp(arg, "memcpy-max-count=", 17))
 		return handle_switch_fmemcpy_max_count(arg+17, next);
 
-	/* handle switches w/ arguments above, boolean and only boolean below */
-	if (handle_simple_switch(arg, "mem-report", &fmem_report))
-		return next;

[RFC PATCH 17/48] dump-ir: rename -fdump-linearize to -fdump-ir

[Luc Van Oostenryck]

---
 cgcc                                   |  2 +-
 lib.c                                  | 10 +++++-----
 lib.h                                  |  2 +-
 linearize.c                            |  4 ++--
 sparse.1                               |  2 +-
 validation/linear/bitfield-init-mask.c |  2 +-
 6 files changed, 11 insertions(+), 11 deletions(-)

diff --git a/cgcc b/cgcc
index a8d7b4f21..644627109 100755
--- a/cgcc
+++ b/cgcc
@@ -103,7 +103,7 @@ sub check_only_option {
     my ($arg) = @_;
     return 1 if $arg =~ /^-W(no-?)?(address-space|bitwise|cast-to-as|cast-truncate|context|decl|default-bitfield-sign|designated-init|do-while|enum-mismatch|init-cstring|memcpy-max-count|non-pointer-null|old-initializer|one-bit-signed-bitfield|override-init-all|paren-string|ptr-subtraction-blows|return-void|sizeof-bool|sparse-all|sparse-error|transparent-union|typesign|undef|unknown-attribute)$/;
     return 1 if $arg =~ /^-v(no-?)?(entry|dead)$/;
-    return 1 if $arg =~ /^-f(dump-linearize|memcpy-max-count)(=\S*)?$/;
+    return 1 if $arg =~ /^-f(dump-ir|memcpy-max-count)(=\S*)?$/;
     return 0;
 }
 
diff --git a/lib.c b/lib.c
index c46798d0f..a0ed29c3e 100644
--- a/lib.c
+++ b/lib.c
@@ -258,7 +258,7 @@ int dbg_entry = 0;
 int dbg_dead = 0;
 
 int fmem_report = 0;
-int fdump_linearize;
+int fdump_ir;
 unsigned long long fmemcpy_max_count = 100000;
 
 int preprocess_only;
@@ -724,12 +724,12 @@ static char **handle_switch_ftabstop(char *arg, char **next)
 
 static char **handle_switch_fdump(char *arg, char **next)
 {
-	if (!strncmp(arg, "linearize", 9)) {
-		arg += 9;
+	if (!strncmp(arg, "ir", 2)) {
+		arg += 2;
 		if (*arg == '\0')
-			fdump_linearize = 1;
+			fdump_ir = 1;
 		else if (!strcmp(arg, "=only"))
-			fdump_linearize = 2;
+			fdump_ir = 2;
 		else
 			goto err;
 	}
diff --git a/lib.h b/lib.h
index 307ccaeb2..ccac27d0b 100644
--- a/lib.h
+++ b/lib.h
@@ -151,7 +151,7 @@ extern int dbg_entry;
 extern int dbg_dead;
 
 extern int fmem_report;
-extern int fdump_linearize;
+extern int fdump_ir;
 extern unsigned long long fmemcpy_max_count;
 
 extern int arch_m64;
diff --git a/linearize.c b/linearize.c
index 6cf97a42e..85acfd9c1 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2262,8 +2262,8 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 		add_one_insn(ep, insn);
 	}
 
-	if (fdump_linearize) {
-		if (fdump_linearize == 2)
+	if (fdump_ir) {
+		if (fdump_ir == 2)
 			return ep;
 		show_entry(ep);
 	}
diff --git a/sparse.1 b/sparse.1
index b79c58767..c7ad4483b 100644
--- a/sparse.1
+++ b/sparse.1
@@ -357,7 +357,7 @@ normalized GNU triplet. (e.g. i386-linux-gnu).
 .
 .SH DEBUG OPTIONS
 .TP
-.B \-fdump-linearize[=only]
+.B \-fdump-ir[=only]
 Dump the IR code of a function directly after its linearization,
 before any simplifications is made. If the argument \fB=only\fR is
 also given no further processing is done on the function.
diff --git a/validation/linear/bitfield-init-mask.c b/validation/linear/bitfield-init-mask.c
index 94afa400c..f43605855 100644
--- a/validation/linear/bitfield-init-mask.c
+++ b/validation/linear/bitfield-init-mask.c
@@ -18,7 +18,7 @@ struct bfu bfu_init_20_23(int a)
 
 /*
  * check-name: bitfield initializer mask
- * check-command: test-linearize -fdump-linearize=only -Wno-decl $file
+ * check-command: test-linearize -fdump-ir=only -Wno-decl $file
  * check-output-ignore
  *
  * check-output-contains: and\\..*fffff800\$
-- 
2.14.0

Re: [RFC PATCH 17/48] dump-ir: rename -fdump-linearize to -fdump-ir

[Christopher Li]

FYI, this one and the few follows does not have a signed off.
I assume you will add commit messages and signed off later.

Chris


On Wed, Aug 23, 2017 at 4:15 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> ---
>  cgcc                                   |  2 +-
>  lib.c                                  | 10 +++++-----
>  lib.h                                  |  2 +-
>  linearize.c                            |  4 ++--
>  sparse.1                               |  2 +-
>  validation/linear/bitfield-init-mask.c |  2 +-
>  6 files changed, 11 insertions(+), 11 deletions(-)
>
> diff --git a/cgcc b/cgcc
> index a8d7b4f21..644627109 100755
> --- a/cgcc
> +++ b/cgcc
> @@ -103,7 +103,7 @@ sub check_only_option {
>      my ($arg) = @_;
>      return 1 if $arg =~ /^-W(no-?)?(address-space|bitwise|cast-to-as|cast-truncate|context|decl|default-bitfield-sign|designated-init|do-while|enum-mismatch|init-cstring|memcpy-max-count|non-pointer-null|old-initializer|one-bit-signed-bitfield|override-init-all|paren-string|ptr-subtraction-blows|return-void|sizeof-bool|sparse-all|sparse-error|transparent-union|typesign|undef|unknown-attribute)$/;
>      return 1 if $arg =~ /^-v(no-?)?(entry|dead)$/;
> -    return 1 if $arg =~ /^-f(dump-linearize|memcpy-max-count)(=\S*)?$/;
> +    return 1 if $arg =~ /^-f(dump-ir|memcpy-max-count)(=\S*)?$/;
>      return 0;
>  }
>
> diff --git a/lib.c b/lib.c
> index c46798d0f..a0ed29c3e 100644
> --- a/lib.c
> +++ b/lib.c
> @@ -258,7 +258,7 @@ int dbg_entry = 0;
>  int dbg_dead = 0;
>
>  int fmem_report = 0;
> -int fdump_linearize;
> +int fdump_ir;
>  unsigned long long fmemcpy_max_count = 100000;
>
>  int preprocess_only;
> @@ -724,12 +724,12 @@ static char **handle_switch_ftabstop(char *arg, char **next)
>
>  static char **handle_switch_fdump(char *arg, char **next)
>  {
> -       if (!strncmp(arg, "linearize", 9)) {
> -               arg += 9;
> +       if (!strncmp(arg, "ir", 2)) {
> +               arg += 2;
>                 if (*arg == '\0')
> -                       fdump_linearize = 1;
> +                       fdump_ir = 1;
>                 else if (!strcmp(arg, "=only"))
> -                       fdump_linearize = 2;
> +                       fdump_ir = 2;
>                 else
>                         goto err;
>         }
> diff --git a/lib.h b/lib.h
> index 307ccaeb2..ccac27d0b 100644
> --- a/lib.h
> +++ b/lib.h
> @@ -151,7 +151,7 @@ extern int dbg_entry;
>  extern int dbg_dead;
>
>  extern int fmem_report;
> -extern int fdump_linearize;
> +extern int fdump_ir;
>  extern unsigned long long fmemcpy_max_count;
>
>  extern int arch_m64;
> diff --git a/linearize.c b/linearize.c
> index 6cf97a42e..85acfd9c1 100644
> --- a/linearize.c
> +++ b/linearize.c
> @@ -2262,8 +2262,8 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
>                 add_one_insn(ep, insn);
>         }
>
> -       if (fdump_linearize) {
> -               if (fdump_linearize == 2)
> +       if (fdump_ir) {
> +               if (fdump_ir == 2)
>                         return ep;
>                 show_entry(ep);
>         }
> diff --git a/sparse.1 b/sparse.1
> index b79c58767..c7ad4483b 100644
> --- a/sparse.1
> +++ b/sparse.1
> @@ -357,7 +357,7 @@ normalized GNU triplet. (e.g. i386-linux-gnu).
>  .
>  .SH DEBUG OPTIONS
>  .TP
> -.B \-fdump-linearize[=only]
> +.B \-fdump-ir[=only]
>  Dump the IR code of a function directly after its linearization,
>  before any simplifications is made. If the argument \fB=only\fR is
>  also given no further processing is done on the function.
> diff --git a/validation/linear/bitfield-init-mask.c b/validation/linear/bitfield-init-mask.c
> index 94afa400c..f43605855 100644
> --- a/validation/linear/bitfield-init-mask.c
> +++ b/validation/linear/bitfield-init-mask.c
> @@ -18,7 +18,7 @@ struct bfu bfu_init_20_23(int a)
>
>  /*
>   * check-name: bitfield initializer mask
> - * check-command: test-linearize -fdump-linearize=only -Wno-decl $file
> + * check-command: test-linearize -fdump-ir=only -Wno-decl $file
>   * check-output-ignore
>   *
>   * check-output-contains: and\\..*fffff800\$
> --
> 2.14.0
>

[RFC PATCH 18/48] dump-ir: use defines

[Luc Van Oostenryck]

---
 lib.c       | 5 +++--
 lib.h       | 4 ++++
 linearize.c | 4 ++--
 3 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/lib.c b/lib.c
index a0ed29c3e..e1454661b 100644
--- a/lib.c
+++ b/lib.c
@@ -725,11 +725,12 @@ static char **handle_switch_ftabstop(char *arg, char **next)
 static char **handle_switch_fdump(char *arg, char **next)
 {
 	if (!strncmp(arg, "ir", 2)) {
+		fdump_ir = DUMP_IR_LINEARIZE;
 		arg += 2;
 		if (*arg == '\0')
-			fdump_ir = 1;
+			fdump_ir = DUMP_IR_LINEARIZE;
 		else if (!strcmp(arg, "=only"))
-			fdump_ir = 2;
+			fdump_ir |= DUMP_IR_ONLY;
 		else
 			goto err;
 	}
diff --git a/lib.h b/lib.h
index ccac27d0b..d0b699535 100644
--- a/lib.h
+++ b/lib.h
@@ -107,6 +107,10 @@ extern void expression_error(struct expression *, const char *, ...) FORMAT_ATTR
 #define	ERROR_PREV_PHASE	(1 << 1)
 extern int has_error;
 
+#define	DUMP_IR_ONLY		(1 << 0)
+#define	DUMP_IR_LINEARIZE	(1 << 1)
+#define	DUMP_IR_STOP(F,D)	(((F) & DUMP_IR_ONLY) && ((F) < ((D) << 1)))
+
 extern void add_pre_buffer(const char *fmt, ...) FORMAT_ATTR(1);
 
 extern int preprocess_only;
diff --git a/linearize.c b/linearize.c
index 85acfd9c1..d5606b708 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2262,8 +2262,8 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 		add_one_insn(ep, insn);
 	}
 
-	if (fdump_ir) {
-		if (fdump_ir == 2)
+	if (fdump_ir & DUMP_IR_LINEARIZE) {
+		if (DUMP_IR_STOP(fdump_ir, DUMP_IR_LINEARIZE))
 			return ep;
 		show_entry(ep);
 	}
-- 
2.14.0

[RFC PATCH 19/48] dump-ir: add an helper to parse sub-options

[Luc Van Oostenryck]

---
 lib.c | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

diff --git a/lib.c b/lib.c
index e1454661b..c107505a7 100644
--- a/lib.c
+++ b/lib.c
@@ -476,6 +476,41 @@ static void handle_arch_finalize(void)
 }
 
 
+struct mask_map {
+	const char *name;
+	unsigned long mask;
+};
+
+static unsigned long lookup_mask(const char *name, const struct mask_map *map)
+{
+	for (; map->name; map++) {
+		if (strcmp(name, map->name) == 0)
+			return map->mask;
+	}
+	return 0;
+}
+
+inline
+static unsigned long handle_suboption_mask(char *arg, const struct mask_map *map)
+{
+	const char *token;
+	unsigned long mask = 0;
+
+	if (*arg == '\0')
+		return lookup_mask("$default", map);
+	if (*arg != '=')
+		return ~0UL;
+	arg++;
+	while ((token = strsep(&arg, ",+"))) {
+		unsigned long opt = lookup_mask(token, map);
+		if (!opt)
+			return ~0UL;
+		mask |= opt;
+	}
+	return mask;
+}
+
+
 struct flag {
 	const char *name;
 	int *flag;
-- 
2.14.0

[RFC PATCH 20/48] dump-ir: make it more flexible

[Luc Van Oostenryck]

---
 lib.c                                  | 17 +++++++++--------
 validation/linear/bitfield-init-mask.c |  2 +-
 2 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/lib.c b/lib.c
index c107505a7..d3aaf10d2 100644
--- a/lib.c
+++ b/lib.c
@@ -490,7 +490,6 @@ static unsigned long lookup_mask(const char *name, const struct mask_map *map)
 	return 0;
 }
 
-inline
 static unsigned long handle_suboption_mask(char *arg, const struct mask_map *map)
 {
 	const char *token;
@@ -757,16 +756,18 @@ static char **handle_switch_ftabstop(char *arg, char **next)
 	return next;
 }
 
+static const struct mask_map dump_ir_options[] = {
+	{ "$default",		DUMP_IR_LINEARIZE },
+	{ "linearize",		DUMP_IR_LINEARIZE },
+	{ "only",		DUMP_IR_ONLY },
+	{ },
+};
+
 static char **handle_switch_fdump(char *arg, char **next)
 {
 	if (!strncmp(arg, "ir", 2)) {
-		fdump_ir = DUMP_IR_LINEARIZE;
-		arg += 2;
-		if (*arg == '\0')
-			fdump_ir = DUMP_IR_LINEARIZE;
-		else if (!strcmp(arg, "=only"))
-			fdump_ir |= DUMP_IR_ONLY;
-		else
+		fdump_ir = handle_suboption_mask(arg+2, dump_ir_options);
+		if (fdump_ir == ~0UL)
 			goto err;
 	}
 
diff --git a/validation/linear/bitfield-init-mask.c b/validation/linear/bitfield-init-mask.c
index f43605855..fa91fec90 100644
--- a/validation/linear/bitfield-init-mask.c
+++ b/validation/linear/bitfield-init-mask.c
@@ -18,7 +18,7 @@ struct bfu bfu_init_20_23(int a)
 
 /*
  * check-name: bitfield initializer mask
- * check-command: test-linearize -fdump-ir=only -Wno-decl $file
+ * check-command: test-linearize -fdump-ir=linearize,only -Wno-decl $file
  * check-output-ignore
  *
  * check-output-contains: and\\..*fffff800\$
-- 
2.14.0

[RFC PATCH 21/48] sssa: move simplify_one_symbol() to a separate file

[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>
---
 Makefile  |   1 +
 flow.c    | 324 ------------------------------------------------------------
 mem2reg.c | 333 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 334 insertions(+), 324 deletions(-)
 create mode 100644 mem2reg.c

diff --git a/Makefile b/Makefile
index 48e1f508f..f7e6e6eb5 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 \
+	  mem2reg.o \
 	  stats.o \
 	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
 
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);
-}
-
 static void mark_bb_reachable(struct basic_block *bb, unsigned long generation)
 {
 	struct basic_block *child;
diff --git a/mem2reg.c b/mem2reg.c
new file mode 100644
index 000000000..41ba54442
--- /dev/null
+++ b/mem2reg.c
@@ -0,0 +1,333 @@
+/*
+ * mem2reg - promote memory accesses to registers.
+ *
+ * Copyright (C) 2004 Linus Torvalds
+ */
+
+#include "linearize.h"
+#include "flow.h"
+
+
+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;
+}
+
+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);
+}
+
+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);
+}
-- 
2.14.0

[RFC PATCH 22/48] mem2reg: rename to use 'promote' instead of 'simplify'

[Luc Van Oostenryck]

---
 flow.h      | 2 +-
 linearize.c | 2 +-
 mem2reg.c   | 6 +++---
 3 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/flow.h b/flow.h
index 3133245e5..b9fc13723 100644
--- a/flow.h
+++ b/flow.h
@@ -14,7 +14,7 @@ struct instruction;
 
 extern int simplify_flow(struct entrypoint *ep);
 
-extern void simplify_symbol_usage(struct entrypoint *ep);
+extern void promote_symbols_usage(struct entrypoint *ep);
 extern void simplify_memops(struct entrypoint *ep);
 extern void pack_basic_blocks(struct entrypoint *ep);
 
diff --git a/linearize.c b/linearize.c
index d5606b708..2c49d29d9 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2277,7 +2277,7 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	/*
 	 * Turn symbols into pseudos
 	 */
-	simplify_symbol_usage(ep);
+	promote_symbols_usage(ep);
 
 repeat:
 	/*
diff --git a/mem2reg.c b/mem2reg.c
index 41ba54442..0567e98fe 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -240,7 +240,7 @@ static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn,
 	} END_FOR_EACH_PTR(parent);
 }
 
-static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
+static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 {
 	pseudo_t pseudo;
 	struct pseudo_user *pu;
@@ -323,11 +323,11 @@ external_visibility:
 	return;
 }
 
-void simplify_symbol_usage(struct entrypoint *ep)
+void promote_symbols_usage(struct entrypoint *ep)
 {
 	pseudo_t pseudo;
 
 	FOR_EACH_PTR(ep->accesses, pseudo) {
-		simplify_one_symbol(ep, pseudo->sym);
+		promote_symbol(ep, pseudo->sym);
 	} END_FOR_EACH_PTR(pseudo);
 }
-- 
2.14.0

[RFC PATCH 23/48] mem2reg: simplify check of modifiers for external visibility

[Luc Van Oostenryck]

---
 mem2reg.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 0567e98fe..2309d11c1 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -252,12 +252,14 @@ static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 	if (!pseudo)
 		return;
 
+	mod = sym->ctype.modifiers;
+
 	/* We don't do coverage analysis of volatiles.. */
-	if (sym->ctype.modifiers & MOD_VOLATILE)
+	if (mod & MOD_VOLATILE)
 		return;
 
 	/* ..and symbols with external visibility need more care */
-	mod = sym->ctype.modifiers & (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
+	mod = mod & (MOD_NONLOCAL|MOD_STATIC|MOD_ADDRESSABLE);
 	if (mod)
 		goto external_visibility;
 
-- 
2.14.0

[RFC PATCH 24/48] mem2reg: extract externaly_visible()

[Luc Van Oostenryck]

---
 mem2reg.c | 45 ++++++++++++++++++++++++++++-----------------
 1 file changed, 28 insertions(+), 17 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 2309d11c1..6fe864df0 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -240,26 +240,12 @@ static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn,
 	} END_FOR_EACH_PTR(parent);
 }
 
-static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
+
+static unsigned long externaly_visible(struct symbol *sym, unsigned long mod)
 {
-	pseudo_t pseudo;
+	pseudo_t pseudo = sym->pseudo;
 	struct pseudo_user *pu;
-	unsigned long mod;
-	int all;
 
-	/* Never used as a symbol? */
-	pseudo = sym->pseudo;
-	if (!pseudo)
-		return;
-
-	mod = sym->ctype.modifiers;
-
-	/* We don't do coverage analysis of volatiles.. */
-	if (mod & MOD_VOLATILE)
-		return;
-
-	/* ..and symbols with external visibility need more care */
-	mod = mod & (MOD_NONLOCAL|MOD_STATIC|MOD_ADDRESSABLE);
 	if (mod)
 		goto external_visibility;
 
@@ -288,6 +274,31 @@ static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 	} END_FOR_EACH_PTR(pu);
 
 external_visibility:
+	return mod;
+}
+
+static void promote_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;
+
+	mod = sym->ctype.modifiers;
+
+	/* We don't do coverage analysis of volatiles.. */
+	if (mod & MOD_VOLATILE)
+		return;
+
+	/* ..and symbols with external visibility need more care */
+	mod = mod & (MOD_NONLOCAL|MOD_STATIC|MOD_ADDRESSABLE);
+	mod = externaly_visible(sym, mod);
+
 	all = 1;
 	FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
 		struct instruction *insn = pu->insn;
-- 
2.14.0

[RFC PATCH 25/48] mem2reg: reorg externaly_visible() returns

[Luc Van Oostenryck]

---
 mem2reg.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 6fe864df0..a9bf78ed4 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -247,7 +247,7 @@ static unsigned long externaly_visible(struct symbol *sym, unsigned long mod)
 	struct pseudo_user *pu;
 
 	if (mod)
-		goto external_visibility;
+		return mod;
 
 	FOR_EACH_PTR(pseudo->users, pu) {
 		/* We know that the symbol-pseudo use is the "src" in the instruction */
@@ -261,8 +261,7 @@ static unsigned long externaly_visible(struct symbol *sym, unsigned long mod)
 		case OP_SYMADDR:
 			if (!insn->bb)
 				continue;
-			mod |= MOD_ADDRESSABLE;
-			goto external_visibility;
+			return MOD_ADDRESSABLE;
 		case OP_NOP:
 		case OP_SNOP:
 		case OP_LNOP:
@@ -273,8 +272,7 @@ static unsigned long externaly_visible(struct symbol *sym, unsigned long mod)
 		}
 	} END_FOR_EACH_PTR(pu);
 
-external_visibility:
-	return mod;
+	return 0;
 }
 
 static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
-- 
2.14.0

[RFC PATCH 26/48] mem2reg: ignore all killed instructions

[Luc Van Oostenryck]

---
 mem2reg.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index a9bf78ed4..7096a4bf2 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -253,14 +253,15 @@ static unsigned long externaly_visible(struct symbol *sym, unsigned long mod)
 		/* We know that the symbol-pseudo use is the "src" in the instruction */
 		struct instruction *insn = pu->insn;
 
+		if (!insn->bb)
+			continue;
+
 		switch (insn->opcode) {
 		case OP_STORE:
 			break;
 		case OP_LOAD:
 			break;
 		case OP_SYMADDR:
-			if (!insn->bb)
-				continue;
 			return MOD_ADDRESSABLE;
 		case OP_NOP:
 		case OP_SNOP:
-- 
2.14.0

[RFC PATCH 27/48] mem2reg: extract kill_pseudo_stores()

[Luc Van Oostenryck]

---
 mem2reg.c | 17 ++++++++++++-----
 1 file changed, 12 insertions(+), 5 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 7096a4bf2..4671d4710 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -148,6 +148,17 @@ static void kill_store(struct instruction *insn)
 	}
 }
 
+static void kill_pseudo_stores(pseudo_t pseudo)
+{
+	struct pseudo_user *pu;
+
+	FOR_EACH_PTR(pseudo->users, pu) {
+		struct instruction *insn = pu->insn;
+		if (insn->opcode == OP_STORE)
+			kill_store(insn);
+	} END_FOR_EACH_PTR(pu);
+}
+
 /* 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)
 {
@@ -307,11 +318,7 @@ static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 
 	/* 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);
+		return kill_pseudo_stores(pseudo);
 	} else {
 		/*
 		 * If we couldn't take the shortcut, see if we can at least kill some
-- 
2.14.0

[RFC PATCH 28/48] mem2reg: extract kill_pseudo_dominated_stores()

[Luc Van Oostenryck]

---
 mem2reg.c | 17 ++++++++++++-----
 1 file changed, 12 insertions(+), 5 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 4671d4710..d13af1dd2 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -251,6 +251,17 @@ static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn,
 	} END_FOR_EACH_PTR(parent);
 }
 
+static void kill_pseudo_dominated_stores(pseudo_t pseudo, int local)
+{
+	struct pseudo_user *pu;
+
+	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, local, 0);
+	} END_FOR_EACH_PTR(pu);
+}
+
 
 static unsigned long externaly_visible(struct symbol *sym, unsigned long mod)
 {
@@ -324,11 +335,7 @@ static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 		 * 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);
+		kill_pseudo_dominated_stores(pseudo, !mod);
 
 		if (!(mod & (MOD_NONLOCAL | MOD_STATIC))) {
 			struct basic_block *bb;
-- 
2.14.0

[RFC PATCH 29/48] mem2reg: extract kill_pseudo_dead_stores()

[Luc Van Oostenryck]

---
 mem2reg.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index d13af1dd2..2a976e826 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -200,6 +200,15 @@ static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct b
 	} END_FOR_EACH_PTR(parent);
 }
 
+static void kill_pseudo_dead_stores(struct entrypoint *ep, pseudo_t pseudo, int local)
+{
+	struct basic_block *bb;
+	FOR_EACH_PTR(ep->bbs, bb) {
+		if (!bb->children)
+			kill_dead_stores(pseudo, ++bb_generation, bb, local);
+	} END_FOR_EACH_PTR(bb);
+}
+
 /*
  * This should see if the "insn" trivially dominates some previous store, and kill the
  * store if unnecessary.
@@ -338,11 +347,7 @@ static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 		kill_pseudo_dominated_stores(pseudo, !mod);
 
 		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);
+			kill_pseudo_dead_stores(ep, pseudo, !mod);
 		}
 	}
 
-- 
2.14.0

[RFC PATCH 30/48] mem2reg: remove one indent level

[Luc Van Oostenryck]

---
 mem2reg.c | 22 +++++++++-------------
 1 file changed, 9 insertions(+), 13 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 2a976e826..b7dc3cb4b 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -337,21 +337,17 @@ static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 	} END_FOR_EACH_PTR_REVERSE(pu);
 
 	/* If we converted all the loads, remove the stores. They are dead */
-	if (all && !mod) {
+	if (all && !mod)
 		return kill_pseudo_stores(pseudo);
-	} else {
-		/*
-		 * If we couldn't take the shortcut, see if we can at least kill some
-		 * of them..
-		 */
-		kill_pseudo_dominated_stores(pseudo, !mod);

[RFC PATCH 31/48] mem2reg: add comment to find_dominating_stores()

[Luc Van Oostenryck]

---
 mem2reg.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/mem2reg.c b/mem2reg.c
index b7dc3cb4b..26837935c 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -68,6 +68,11 @@ found_dominator:
 	return 1;
 }
 
+/*
+ * pseudo: pseudo for a symbol
+ * insn: is a load of the symbol 'pseudo'.
+ * local: is the symbol local or externally visible?
+ */
 static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
 	unsigned long generation, int local)
 {
-- 
2.14.0

[RFC PATCH 32/48] mem2reg: add flags to enable/disable some parts

[Luc Van Oostenryck]

---
 lib.c     |  8 ++++++++
 lib.h     |  6 +++++-
 mem2reg.c |  3 +++
 memops.c  | 17 ++++++++++++++++-
 sparse.1  | 28 ++++++++++++++++++++++++++++
 5 files changed, 60 insertions(+), 2 deletions(-)

diff --git a/lib.c b/lib.c
index d3aaf10d2..0705775e5 100644
--- a/lib.c
+++ b/lib.c
@@ -260,6 +260,10 @@ int dbg_dead = 0;
 int fmem_report = 0;
 int fdump_ir;
 unsigned long long fmemcpy_max_count = 100000;
+int fpromote_symbols_usage = 1;
+int fsimplify_loads = 1;
+int fsimplify_loads_full = 0;		// currently broken
+int fsimplify_stores = 1;
 
 int preprocess_only;
 
@@ -780,6 +784,10 @@ err:
 
 static struct flag fflags[] = {
 	{ "mem-report",			&fmem_report },
+	{ "promote-symbols-usage",	&fpromote_symbols_usage },
+	{ "simplify-loads",		&fsimplify_loads },
+	{ "simplify-loads-full",	&fsimplify_loads_full },
+	{ "simplify-stores",		&fsimplify_stores },
 	{ },
 };
 
diff --git a/lib.h b/lib.h
index d0b699535..a2fd04e67 100644
--- a/lib.h
+++ b/lib.h
@@ -154,9 +154,13 @@ extern int dump_macro_defs;
 extern int dbg_entry;
 extern int dbg_dead;
 
-extern int fmem_report;
 extern int fdump_ir;
+extern int fmem_report;
 extern unsigned long long fmemcpy_max_count;
+extern int fpromote_symbols_usage;
+extern int fsimplify_loads;
+extern int fsimplify_loads_full;
+extern int fsimplify_stores;
 
 extern int arch_m64;
 extern int arch_msize_long;
diff --git a/mem2reg.c b/mem2reg.c
index 26837935c..c2f77ffbe 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -359,6 +359,9 @@ void promote_symbols_usage(struct entrypoint *ep)
 {
 	pseudo_t pseudo;
 
+	if (!fpromote_symbols_usage)
+		return;
+
 	FOR_EACH_PTR(ep->accesses, pseudo) {
 		promote_symbol(ep, pseudo->sym);
 	} END_FOR_EACH_PTR(pseudo);
diff --git a/memops.c b/memops.c
index 99430e455..501973788 100644
--- a/memops.c
+++ b/memops.c
@@ -120,15 +120,30 @@ next_store:
 	} END_FOR_EACH_PTR_REVERSE(insn);
 }
 
-void simplify_memops(struct entrypoint *ep)
+static void simplify_all_loads(struct entrypoint *ep)
 {
 	struct basic_block *bb;
 
+	if (!fsimplify_loads)
+		return;
 	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 		simplify_loads(bb);
 	} END_FOR_EACH_PTR_REVERSE(bb);
+}
+
+static void simplify_all_stores(struct entrypoint *ep)
+{
+	struct basic_block *bb;
 
+	if (!fsimplify_stores)
+		return;
 	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 		kill_dominated_stores(bb);
 	} END_FOR_EACH_PTR_REVERSE(bb);
 }
+
+void simplify_memops(struct entrypoint *ep)
+{
+	simplify_all_loads(ep);
+	simplify_all_stores(ep);
+}
diff --git a/sparse.1 b/sparse.1
index c7ad4483b..87958ef35 100644
--- a/sparse.1
+++ b/sparse.1
@@ -378,6 +378,34 @@ Set the distance between tab stops.  This helps sparse report correct
 column numbers in warnings or errors.  If the value is less than 1 or
 greater than 100, the option is ignored.  The default is 8.
 .
+.SH DEVELOPER OPTIONS
+.TP
+.B \-fno-promote-symbol-usage
+Enable or disable the promotion of memory accesses via symbol to registers.
+
+This option is enabled by default.
+.
+.TP
+.B \-fno-simplify-loads
+Enable or disable the promotion of memory loads to registers during
+the optimization passes.
+
+This option is enabled by default.
+.
+.TP
+.B \-fsimplify-loads-full
+Enable or disable the promotion of complex memory loads to registers during
+the optimization passes.
+
+This option is disabled by default.
+.
+.TP
+.B \-fno-simplify-stores
+Enable or disable the elimination of some stores to memory during
+the optimization passes.
+
+This option is enabled by default.
+.
 .SH SEE ALSO
 .BR cgcc (1)
 .
-- 
2.14.0

[RFC PATCH 33/48] mem2reg: rename the other kill_dominated_stores()

[Luc Van Oostenryck]

---
 memops.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/memops.c b/memops.c
index 501973788..294c89cbd 100644
--- a/memops.c
+++ b/memops.c
@@ -85,10 +85,11 @@ static void kill_store(struct instruction *insn)
 	}
 }
 
-static void kill_dominated_stores(struct basic_block *bb)
+static void simplify_stores(struct basic_block *bb)
 {
 	struct instruction *insn;
 
+	/* kill the dominated stores */
 	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 		if (!insn->bb)
 			continue;
@@ -138,7 +139,7 @@ static void simplify_all_stores(struct entrypoint *ep)
 	if (!fsimplify_stores)
 		return;
 	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
-		kill_dominated_stores(bb);
+		simplify_stores(bb);
 	} END_FOR_EACH_PTR_REVERSE(bb);
 }
 
-- 
2.14.0

[RFC PATCH 34/48] mem2reg: move rewrite_load_instruction() here

[Luc Van Oostenryck]

---
 flow.c    | 38 --------------------------------------
 flow.h    |  1 -
 mem2reg.c | 38 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 38 insertions(+), 39 deletions(-)

diff --git a/flow.c b/flow.c
index 58ff24d23..78445713c 100644
--- a/flow.c
+++ b/flow.c
@@ -362,44 +362,6 @@ int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom
 	return 1;
 }
 
-/*
- * We should probably sort the phi list just to make it easier to compare
- * later for equality. 
- */
-void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
-{
-	pseudo_t new, phi;
-
-	/*
-	 * Check for somewhat common case of duplicate
-	 * phi nodes.
-	 */
-	new = first_pseudo(dominators)->def->src1;
-	FOR_EACH_PTR(dominators, phi) {
-		if (new != phi->def->src1)
-			goto complex_phi;
-		new->ident = new->ident ? : phi->ident;
-	} END_FOR_EACH_PTR(phi);
-
-	/*
-	 * All the same pseudo - mark the phi-nodes unused
-	 * and convert the load into a LNOP and replace the
-	 * pseudo.
-	 */
-	FOR_EACH_PTR(dominators, phi) {
-		kill_instruction(phi->def);
-	} END_FOR_EACH_PTR(phi);
-	convert_load_instruction(insn, new);
-	return;
-
-complex_phi:
-	/* We leave symbol pseudos with a bogus usage list here */
-	if (insn->src->type != PSEUDO_SYM)
-		kill_use(&insn->src);
-	insn->opcode = OP_PHI;
-	insn->phi_list = dominators;
-}
-
 void check_access(struct instruction *insn)
 {
 	pseudo_t pseudo = insn->src;
diff --git a/flow.h b/flow.h
index b9fc13723..d14987027 100644
--- a/flow.h
+++ b/flow.h
@@ -39,7 +39,6 @@ static inline void kill_instruction_force(struct instruction *insn)
 
 void check_access(struct instruction *insn);
 void convert_load_instruction(struct instruction *, pseudo_t);
-void rewrite_load_instruction(struct instruction *, struct pseudo_list *);
 int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local);
 
 extern void clear_liveness(struct entrypoint *ep);
diff --git a/mem2reg.c b/mem2reg.c
index c2f77ffbe..dca409f5d 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -8,6 +8,44 @@
 #include "flow.h"
 
 
+/*
+ * We should probably sort the phi list just to make it easier to compare
+ * later for equality.
+ */
+static void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
+{
+	pseudo_t new, phi;
+
+	/*
+	 * Check for somewhat common case of duplicate
+	 * phi nodes.
+	 */
+	new = first_pseudo(dominators)->def->src1;
+	FOR_EACH_PTR(dominators, phi) {
+		if (new != phi->def->src1)
+			goto complex_phi;
+		new->ident = new->ident ? : phi->ident;
+	} END_FOR_EACH_PTR(phi);
+
+	/*
+	 * All the same pseudo - mark the phi-nodes unused
+	 * and convert the load into a LNOP and replace the
+	 * pseudo.
+	 */
+	FOR_EACH_PTR(dominators, phi) {
+		kill_instruction(phi->def);
+	} END_FOR_EACH_PTR(phi);
+	convert_load_instruction(insn, new);
+	return;
+
+complex_phi:
+	/* We leave symbol pseudos with a bogus usage list here */
+	if (insn->src->type != PSEUDO_SYM)
+		kill_use(&insn->src);
+	insn->opcode = OP_PHI;
+	insn->phi_list = dominators;
+}
+
 static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
 {
 	pseudo_t p;
-- 
2.14.0

[RFC PATCH 35/48] mem2reg: be clear that we're using a symbol/var

[Luc Van Oostenryck]

---
 mem2reg.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index dca409f5d..641a1f65d 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -107,16 +107,17 @@ found_dominator:
 }
 
 /*
- * pseudo: pseudo for a symbol
- * insn: is a load of the symbol 'pseudo'.
+ * sym: a symbol/variable
+ * insn: is a load of the symbol 'sym'.
  * local: is the symbol local or externally visible?
  */
-static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
+static int find_dominating_stores(struct symbol *sym, struct instruction *insn,
 	unsigned long generation, int local)
 {
 	struct basic_block *bb = insn->bb;
 	struct instruction *one, *dom = NULL;
 	struct pseudo_list *dominators;
+	pseudo_t pseudo = sym->pseudo;
 	int partial;
 
 	/* Unreachable load? Undo it */
@@ -376,7 +377,7 @@ static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 	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);
+			all &= find_dominating_stores(sym, insn, ++bb_generation, !mod);
 	} END_FOR_EACH_PTR_REVERSE(pu);
 
 	/* If we converted all the loads, remove the stores. They are dead */
-- 
2.14.0

[RFC PATCH 36/48] mem2reg: be clear that we're using a symbol/var here too

[Luc Van Oostenryck]

---
 mem2reg.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 641a1f65d..793a1d730 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -57,10 +57,11 @@ static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
 	return 0;
 }
 
-static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
+static int find_dominating_parents(struct symbol *sym, struct instruction *insn,
 	struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
 	int local)
 {
+	pseudo_t pseudo = sym->pseudo;
 	struct basic_block *parent;
 
 	if (!bb->parents)
@@ -90,7 +91,7 @@ no_dominance:
 			continue;
 		parent->generation = generation;
 
-		if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
+		if (!find_dominating_parents(sym, insn, parent, generation, dominators, local))
 			return 0;
 		continue;
 
@@ -161,7 +162,7 @@ found:
 	bb->generation = generation;
 
 	dominators = NULL;
-	if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local))
+	if (!find_dominating_parents(sym, insn, bb, generation, &dominators, local))
 		return 0;
 
 	/* This happens with initial assignments to structures etc.. */
-- 
2.14.0

[RFC PATCH 37/48] mem2reg: add description for find_dominating_parents()

[Luc Van Oostenryck]

---
 mem2reg.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/mem2reg.c b/mem2reg.c
index 793a1d730..0078485da 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -57,6 +57,16 @@ static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
 	return 0;
 }
 
+/*
+ * sym - the symbol/var we're looking the value for
+ * insn - a load of 'sym'
+ * bb - the current bb we're looking
+ * generation - ditto
+ * dominators - list of dominators for this load
+ * local: is the symbol local or externally visible?
+ *
+ * returns 1 if we found a value, 0 otherwise.
+ */
 static int find_dominating_parents(struct symbol *sym, struct instruction *insn,
 	struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
 	int local)
-- 
2.14.0

[RFC PATCH 38/48] mem2reg: let rewrite_load_instruction() take the symbol as arg

[Luc Van Oostenryck]

---
 mem2reg.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 0078485da..4ba0f3408 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -12,7 +12,7 @@
  * We should probably sort the phi list just to make it easier to compare
  * later for equality.
  */
-static void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
+static void rewrite_load_instruction(struct symbol *sym, struct instruction *insn, struct pseudo_list *dominators)
 {
 	pseudo_t new, phi;
 
@@ -24,7 +24,7 @@ static void rewrite_load_instruction(struct instruction *insn, struct pseudo_lis
 	FOR_EACH_PTR(dominators, phi) {
 		if (new != phi->def->src1)
 			goto complex_phi;
-		new->ident = new->ident ? : phi->ident;
+		new->ident = new->ident ? : sym->ident;
 	} END_FOR_EACH_PTR(phi);
 
 	/*
@@ -190,7 +190,7 @@ found:
 	 * have to turn the load into a phi-node of the
 	 * dominators.
 	 */
-	rewrite_load_instruction(insn, dominators);
+	rewrite_load_instruction(sym, insn, dominators);
 	return 1;
 }
 
-- 
2.14.0

[RFC PATCH 39/48] mem2reg: remove check phisrc_in_bb()

[Luc Van Oostenryck]

---
 mem2reg.c | 13 -------------
 1 file changed, 13 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index 4ba0f3408..ecda6675f 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -46,17 +46,6 @@ complex_phi:
 	insn->phi_list = dominators;
 }
 
-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;
-}

[RFC PATCH 40/48] mem2reg: delay the creation of phi-sources

[Luc Van Oostenryck]

---
 mem2reg.c | 67 ++++++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 43 insertions(+), 24 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index ecda6675f..d0873b051 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -12,38 +12,63 @@
  * We should probably sort the phi list just to make it easier to compare
  * later for equality.
  */
-static void rewrite_load_instruction(struct symbol *sym, struct instruction *insn, struct pseudo_list *dominators)
+static void rewrite_load_instruction(struct symbol *sym, struct instruction *insn,
+	struct basic_block *bb, struct pseudo_list *dominators)
 {
-	pseudo_t new, phi;
+	struct basic_block *parent;
+	struct instruction *node;
+	pseudo_t new, val;
 
 	/*
 	 * Check for somewhat common case of duplicate
 	 * phi nodes.
 	 */
-	new = first_pseudo(dominators)->def->src1;
-	FOR_EACH_PTR(dominators, phi) {
-		if (new != phi->def->src1)
+	new = first_pseudo(dominators);
+	FOR_EACH_PTR(dominators, val) {
+		if (new != val)
 			goto complex_phi;
 		new->ident = new->ident ? : sym->ident;
-	} END_FOR_EACH_PTR(phi);
+	} END_FOR_EACH_PTR(val);
 
 	/*
-	 * All the same pseudo - mark the phi-nodes unused
-	 * and convert the load into a LNOP and replace the
-	 * pseudo.
+	 * All the same pseudo - replace the load by the unique val
 	 */
-	FOR_EACH_PTR(dominators, phi) {
-		kill_instruction(phi->def);
-	} END_FOR_EACH_PTR(phi);
-	convert_load_instruction(insn, new);
-	return;
+	goto convert;
 
 complex_phi:
+	/*
+	 * insert a new phi-node on top and
+	 * insert a phi-src at the end of each parents
+	 */
+	new = insert_phi_node(bb, sym);
+	node = new->def;
+
+	PREPARE_PTR_LIST(bb->parents, parent)
+	FOR_EACH_PTR(dominators, val) {
+		struct instruction *br;
+		pseudo_t src;
+
+		br = delete_last_instruction(&parent->insns);
+		/*
+		 * We could check if br is really a branch
+		 * We could check if the type of val & sym matches
+		 */
+		src = alloc_phi(parent, val, sym);
+		add_instruction(&parent->insns, br);
+		use_pseudo(node, src, add_pseudo(&node->phi_list, src));
+
+		NEXT_PTR_LIST(parent);
+	} END_FOR_EACH_PTR(val);
+	FINISH_PTR_LIST(parent);
+
+#if 0	// FIXME
 	/* We leave symbol pseudos with a bogus usage list here */
 	if (insn->src->type != PSEUDO_SYM)
 		kill_use(&insn->src);
-	insn->opcode = OP_PHI;
-	insn->phi_list = dominators;
+#endif
+
+convert:
+	convert_load_instruction(insn, new);
 }
 
 /*
@@ -68,8 +93,6 @@ static int find_dominating_parents(struct symbol *sym, struct instruction *insn,
 
 	FOR_EACH_PTR(bb->parents, parent) {
 		struct instruction *one;
-		struct instruction *br;
-		pseudo_t phi;
 
 		FOR_EACH_PTR_REVERSE(parent->insns, one) {
 			int dominance;
@@ -95,11 +118,7 @@ no_dominance:
 		continue;
 
 found_dominator:
-		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));
+		add_pseudo(dominators, one->target);
 	} END_FOR_EACH_PTR(parent);
 	return 1;
 }
@@ -177,7 +196,7 @@ found:
 	 * have to turn the load into a phi-node of the
 	 * dominators.
 	 */
-	rewrite_load_instruction(sym, insn, dominators);
+	rewrite_load_instruction(sym, insn, bb, dominators);
 	return 1;
 }
 
-- 
2.14.0

[RFC PATCH 41/48] mem2reg: make rewrite_load_instruction() functional

[Luc Van Oostenryck]

---
 mem2reg.c                       | 25 ++++++++++-------
 validation/loop-linearization.c | 60 ++++++++++++++++++++---------------------
 2 files changed, 45 insertions(+), 40 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index d0873b051..bb5fadbf2 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -12,7 +12,7 @@
  * We should probably sort the phi list just to make it easier to compare
  * later for equality.
  */
-static void rewrite_load_instruction(struct symbol *sym, struct instruction *insn,
+static pseudo_t dominating_value(struct symbol *sym,
 	struct basic_block *bb, struct pseudo_list *dominators)
 {
 	struct basic_block *parent;
@@ -31,9 +31,9 @@ static void rewrite_load_instruction(struct symbol *sym, struct instruction *ins
 	} END_FOR_EACH_PTR(val);
 
 	/*
-	 * All the same pseudo - replace the load by the unique val
+	 * All the same pseudo - use it!
 	 */
-	goto convert;
+	return new;
 
 complex_phi:
 	/*
@@ -67,8 +67,7 @@ complex_phi:
 		kill_use(&insn->src);
 #endif
 
-convert:
-	convert_load_instruction(insn, new);
+	return new;
 }
 
 /*
@@ -135,6 +134,7 @@ static int find_dominating_stores(struct symbol *sym, struct instruction *insn,
 	struct instruction *one, *dom = NULL;
 	struct pseudo_list *dominators;
 	pseudo_t pseudo = sym->pseudo;
+	pseudo_t val;
 	int partial;
 
 	/* Unreachable load? Undo it */
@@ -170,8 +170,8 @@ found:
 		return 0;
 
 	if (dom) {
-		convert_load_instruction(insn, dom->target);
-		return 1;
+		val = dom->target;
+		goto convert;
 	}
 
 	/* OK, go find the parents */
@@ -186,8 +186,10 @@ found:
 		if (!local)
 			return 0;
 		check_access(insn);
-		convert_load_instruction(insn, value_pseudo(0));
-		return 1;
+
+		// FIXME: should be UNDEF
+		val = value_pseudo(0);
+		goto convert;
 	}
 
 	/*
@@ -196,7 +198,10 @@ found:
 	 * have to turn the load into a phi-node of the
 	 * dominators.
 	 */
-	rewrite_load_instruction(sym, insn, bb, dominators);
+	val = dominating_value(sym, bb, dominators);
+
+convert:
+	convert_load_instruction(insn, val);
 	return 1;
 }
 
diff --git a/validation/loop-linearization.c b/validation/loop-linearization.c
index 25c6dfb87..6c531d056 100644
--- a/validation/loop-linearization.c
+++ b/validation/loop-linearization.c
@@ -39,16 +39,16 @@ static int fdo(void)
 ffor:
 .L0:
 	<entry-point>
-	phisrc.32   %phi5(i) <- $0
+	phisrc.32   %phi3 <- $0
 	br          .L4
 
 .L4:
-	phi.32      %r1(i) <- %phi5(i), %phi6(i)
-	setlt.32    %r2 <- %r1(i), $10
+	phi.32      %r8 <- %phi3, %phi4
+	setlt.32    %r2 <- %r8, $10
 	cbr         %r2, .L1, .L3
 
 .L1:
-	call.32     %r4 <- p, %r1(i)
+	call.32     %r4 <- p, %r8
 	cbr         %r4, .L2, .L5
 
 .L5:
@@ -56,8 +56,8 @@ ffor:
 	br          .L7
 
 .L2:
-	add.32      %r7 <- %r1(i), $1
-	phisrc.32   %phi6(i) <- %r7
+	add.32      %r7 <- %r8, $1
+	phisrc.32   %phi4 <- %r7
 	br          .L4
 
 .L3:
@@ -72,64 +72,64 @@ ffor:
 fwhile:
 .L8:
 	<entry-point>
-	phisrc.32   %phi11(i) <- $0
+	phisrc.32   %phi7 <- $0
 	br          .L12
 
 .L12:
-	phi.32      %r8(i) <- %phi11(i), %phi12(i)
-	setlt.32    %r9 <- %r8(i), $10
-	cbr         %r9, .L9, .L11
+	phi.32      %r16 <- %phi7, %phi8
+	setlt.32    %r10 <- %r16, $10
+	cbr         %r10, .L9, .L11
 
 .L9:
-	call.32     %r11 <- p, %r8(i)
-	cbr         %r11, .L14, .L13
+	call.32     %r12 <- p, %r16
+	cbr         %r12, .L14, .L13
 
 .L13:
-	phisrc.32   %phi7(return) <- $0
+	phisrc.32   %phi5(return) <- $0
 	br          .L15
 
 .L14:
-	add.32      %r14 <- %r8(i), $1
-	phisrc.32   %phi12(i) <- %r14
+	add.32      %r15 <- %r16, $1
+	phisrc.32   %phi8 <- %r15
 	br          .L12
 
 .L11:
-	phisrc.32   %phi8(return) <- $1
+	phisrc.32   %phi6(return) <- $1
 	br          .L15
 
 .L15:
-	phi.32      %r12 <- %phi7(return), %phi8(return)
-	ret.32      %r12
+	phi.32      %r13 <- %phi5(return), %phi6(return)
+	ret.32      %r13
 
 
 fdo:
 .L16:
 	<entry-point>
-	phisrc.32   %phi16(i) <- $0
+	phisrc.32   %phi11 <- $0
 	br          .L17
 
 .L17:
-	phi.32      %r15(i) <- %phi16(i), %phi17(i)
-	call.32     %r16 <- p, %r15(i)
-	cbr         %r16, .L18, .L20
+	phi.32      %r23 <- %phi11, %phi12
+	call.32     %r18 <- p, %r23
+	cbr         %r18, .L18, .L20
 
 .L20:
-	phisrc.32   %phi13(return) <- $0
+	phisrc.32   %phi9(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      %r21 <- %r23, $1
+	setlt.32    %r22 <- %r23, $10
+	phisrc.32   %phi12 <- %r21
+	cbr         %r22, .L17, .L19
 
 .L19:
-	phisrc.32   %phi14(return) <- $1
+	phisrc.32   %phi10(return) <- $1
 	br          .L22
 
 .L22:
-	phi.32      %r17 <- %phi13(return), %phi14(return)
-	ret.32      %r17
+	phi.32      %r19 <- %phi9(return), %phi10(return)
+	ret.32      %r19
 
 
  * check-output-end
-- 
2.14.0

[RFC PATCH 42/48] mem2reg: rename one->target to dom

[Luc Van Oostenryck]

---
 mem2reg.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/mem2reg.c b/mem2reg.c
index bb5fadbf2..e27739701 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -86,6 +86,7 @@ static int find_dominating_parents(struct symbol *sym, struct instruction *insn,
 {
 	pseudo_t pseudo = sym->pseudo;
 	struct basic_block *parent;
+	pseudo_t dom;
 
 	if (!bb->parents)
 		return !!local;
@@ -105,6 +106,7 @@ static int find_dominating_parents(struct symbol *sym, struct instruction *insn,
 			}
 			if (!dominance)
 				continue;
+			dom = one->target;
 			goto found_dominator;
 		} END_FOR_EACH_PTR_REVERSE(one);
 no_dominance:
@@ -117,7 +119,7 @@ no_dominance:
 		continue;
 
 found_dominator:
-		add_pseudo(dominators, one->target);
+		add_pseudo(dominators, dom);
 	} END_FOR_EACH_PTR(parent);
 	return 1;
 }
-- 
2.14.0

[RFC PATCH 43/48] mem2reg: get recursion right

[Luc Van Oostenryck]

---
 mem2reg.c                       | 71 ++++++++++++++++++++++++-----------------
 validation/loop-linearization.c |  4 +--
 2 files changed, 43 insertions(+), 32 deletions(-)

diff --git a/mem2reg.c b/mem2reg.c
index e27739701..5f1c968a0 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -70,6 +70,10 @@ complex_phi:
 	return new;
 }
 
+
+static pseudo_t find_dominating_value(struct symbol *sym, struct instruction *insn,
+	struct basic_block *bb, unsigned long generation, int local);
+
 /*
  * sym - the symbol/var we're looking the value for
  * insn - a load of 'sym'
@@ -110,13 +114,9 @@ static int find_dominating_parents(struct symbol *sym, struct instruction *insn,
 			goto found_dominator;
 		} END_FOR_EACH_PTR_REVERSE(one);
 no_dominance:
-		if (parent->generation == generation)
-			continue;
-		parent->generation = generation;
-
-		if (!find_dominating_parents(sym, insn, parent, generation, dominators, local))
+		dom = find_dominating_value(sym, insn, parent, generation, local);
+		if (!dom)
 			return 0;
-		continue;
 
 found_dominator:
 		add_pseudo(dominators, dom);
@@ -124,6 +124,39 @@ found_dominator:
 	return 1;
 }
 
+static pseudo_t find_dominating_value(struct symbol *sym, struct instruction *insn,
+	struct basic_block *bb, unsigned long generation, int local)
+{
+	struct pseudo_list *dominators = NULL;
+
+	if (bb->generation == generation) {
+		return insn->target;
+		// FIXME: is that exact ?
+	}
+
+	bb->generation = generation;
+	if (!find_dominating_parents(sym, insn, bb, generation, &dominators, local))
+		return NULL;
+
+	/* This happens with initial assignments to structures etc.. */
+	if (!dominators) {
+		if (!local)
+			return NULL;
+		check_access(insn);
+
+		// FIXME: should be UNDEF
+		return value_pseudo(0);
+	}
+
+	/*
+	 * 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.
+	 */
+	return dominating_value(sym, bb, dominators);
+}
+
 /*
  * sym: a symbol/variable
  * insn: is a load of the symbol 'sym'.
@@ -134,7 +167,6 @@ static int find_dominating_stores(struct symbol *sym, struct instruction *insn,
 {
 	struct basic_block *bb = insn->bb;
 	struct instruction *one, *dom = NULL;
-	struct pseudo_list *dominators;
 	pseudo_t pseudo = sym->pseudo;
 	pseudo_t val;
 	int partial;
@@ -177,31 +209,10 @@ found:
 	}
 
 	/* OK, go find the parents */
-	bb->generation = generation;
-
-	dominators = NULL;
-	if (!find_dominating_parents(sym, insn, bb, generation, &dominators, local))
+	val = find_dominating_value(sym, insn, bb, generation, local);
+	if (!val)
 		return 0;
 
-	/* This happens with initial assignments to structures etc.. */
-	if (!dominators) {
-		if (!local)
-			return 0;
-		check_access(insn);
-
-		// FIXME: should be UNDEF
-		val = value_pseudo(0);
-		goto convert;
-	}
-
-	/*
-	 * 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.
-	 */
-	val = dominating_value(sym, bb, dominators);

[RFC PATCH 44/48] mem2reg: don't check dominance by removed instructions

[Luc Van Oostenryck]

---
 mem2reg.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/mem2reg.c b/mem2reg.c
index 5f1c968a0..493274df5 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -100,6 +100,8 @@ static int find_dominating_parents(struct symbol *sym, struct instruction *insn,
 
 		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);
@@ -180,6 +182,8 @@ static int find_dominating_stores(struct symbol *sym, struct instruction *insn,
 	partial = 0;
 	FOR_EACH_PTR(bb->insns, one) {
 		int dominance;
+		if (!one->bb)
+			continue;
 		if (one == insn)
 			goto found;
 		dominance = dominates(pseudo, insn, one, local);
@@ -250,6 +254,8 @@ static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct b
 	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 		int opcode = insn->opcode;
 
+		if (!insn->bb)
+			continue;
 		if (opcode != OP_LOAD && opcode != OP_STORE) {
 			if (local)
 				continue;
-- 
2.14.0

[RFC PATCH 45/48] mem2reg: update copyright

[Luc Van Oostenryck]

---
 mem2reg.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/mem2reg.c b/mem2reg.c
index 493274df5..d31cd4121 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -2,6 +2,7 @@
  * mem2reg - promote memory accesses to registers.
  *
  * Copyright (C) 2004 Linus Torvalds
+ * Copyright (C) 2017 Luc Van Oostenryck
  */
 
 #include "linearize.h"
-- 
2.14.0

[RFC PATCH 46/48] mem2reg: allow dumping IR

[Luc Van Oostenryck]

---
 lib.c       | 1 +
 lib.h       | 1 +
 linearize.c | 5 +++++
 3 files changed, 7 insertions(+)

diff --git a/lib.c b/lib.c
index 0705775e5..f32fbda9f 100644
--- a/lib.c
+++ b/lib.c
@@ -763,6 +763,7 @@ static char **handle_switch_ftabstop(char *arg, char **next)
 static const struct mask_map dump_ir_options[] = {
 	{ "$default",		DUMP_IR_LINEARIZE },
 	{ "linearize",		DUMP_IR_LINEARIZE },
+	{ "mem2reg",		DUMP_IR_MEM2REG },
 	{ "only",		DUMP_IR_ONLY },
 	{ },
 };
diff --git a/lib.h b/lib.h
index a2fd04e67..30e097338 100644
--- a/lib.h
+++ b/lib.h
@@ -109,6 +109,7 @@ extern int has_error;
 
 #define	DUMP_IR_ONLY		(1 << 0)
 #define	DUMP_IR_LINEARIZE	(1 << 1)
+#define	DUMP_IR_MEM2REG		(1 << 2)
 #define	DUMP_IR_STOP(F,D)	(((F) & DUMP_IR_ONLY) && ((F) < ((D) << 1)))
 
 extern void add_pre_buffer(const char *fmt, ...) FORMAT_ATTR(1);
diff --git a/linearize.c b/linearize.c
index 2c49d29d9..8db4638bc 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2278,6 +2278,11 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	 * Turn symbols into pseudos
 	 */
 	promote_symbols_usage(ep);
+	if (fdump_ir & DUMP_IR_MEM2REG) {
+		if (DUMP_IR_STOP(fdump_ir, DUMP_IR_MEM2REG))
+			return ep;
+		show_entry(ep);
+	}
 
 repeat:
 	/*
-- 
2.14.0

[RFC PATCH 47/48] mem2reg: add some small test cases

[Luc Van Oostenryck]

---
 validation/mem2reg/global-direct00.c    | 24 ++++++++++++++++++++++++
 validation/mem2reg/local-addr-taken00.c | 21 +++++++++++++++++++++
 validation/mem2reg/local-direct00.c     | 20 ++++++++++++++++++++
 3 files changed, 65 insertions(+)
 create mode 100644 validation/mem2reg/global-direct00.c
 create mode 100644 validation/mem2reg/local-addr-taken00.c
 create mode 100644 validation/mem2reg/local-direct00.c

diff --git a/validation/mem2reg/global-direct00.c b/validation/mem2reg/global-direct00.c
new file mode 100644
index 000000000..cd0f0d1a0
--- /dev/null
+++ b/validation/mem2reg/global-direct00.c
@@ -0,0 +1,24 @@
+int a, c, d;
+
+int foo(void)
+{
+	int b, e;
+	if (a)
+		b = c;
+	else
+		b = d;
+	if (c)
+		a = b;
+	if (b)
+		e = a;
+	return e;
+}
+
+/*
+ * check-name: mem2reg global direct 00
+ * check-command: test-linearize -fdump-ir=mem2reg,only -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-pattern-4-times: load\\.
+ * check-output-pattern-1-times: store\\.
+ */
diff --git a/validation/mem2reg/local-addr-taken00.c b/validation/mem2reg/local-addr-taken00.c
new file mode 100644
index 000000000..bcfa32257
--- /dev/null
+++ b/validation/mem2reg/local-addr-taken00.c
@@ -0,0 +1,21 @@
+int foo(int c, int a, int b)
+{
+	int l;
+	int *p = &l;
+
+	if (c)
+		l = a;
+	else
+		l = b;
+
+	return l;
+}
+
+/*
+ * check-name: mem2reg local address taken 00
+ * check-command: test-linearize -fdump-ir=mem2reg,only -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: load\\.
+ * check-output-excludes: store\\.
+ */
diff --git a/validation/mem2reg/local-direct00.c b/validation/mem2reg/local-direct00.c
new file mode 100644
index 000000000..fc55fa076
--- /dev/null
+++ b/validation/mem2reg/local-direct00.c
@@ -0,0 +1,20 @@
+int foo(int c, int a, int b)
+{
+	int l;
+
+	if (c)
+		l = a;
+	else
+		l = b;
+
+	return l;
+}
+
+/*
+ * check-name: mem2reg local direct 00
+ * check-command: test-linearize -fdump-ir=mem2reg,only -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: load\\.
+ * check-output-excludes: store\\.
+ */
-- 
2.14.0

[RFC PATCH 48/48] mem2reg: don't promote unused or already promoted vars

[Luc Van Oostenryck]

---
 mem2reg.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/mem2reg.c b/mem2reg.c
index d31cd4121..490077d67 100644
--- a/mem2reg.c
+++ b/mem2reg.c
@@ -405,6 +405,10 @@ static void promote_symbol(struct entrypoint *ep, struct symbol *sym)
 	if (!pseudo)
 		return;
 
+	/* already converted ? */
+	if (!pseudo->users)
+		return;
+
 	mod = sym->ctype.modifiers;
 
 	/* We don't do coverage analysis of volatiles.. */
-- 
2.14.0

Re: [RFC PATCH 00/48] fix promotion of symbol to register

[Christopher Li]

On Wed, Aug 23, 2017 at 4:15 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This series fixes the promotion of symbols accesses from
> memory to pseudos.
> The fix in itself is in the few of the last patches (40-43)
> but is preceded by an extensive rework of the whole thing.
>
> As is, it seems to work quite well and of course more
> accesses are promoted than the Simple SSA was able to do
> (SSSA only cared about purely local vars of which the address
> was never ever taken).
>
> For performance, the situation is highly dependent on the
> type of code: the amount of work that is done in
> simplify_loads() can easily take 80% of the time for complex
> files.
>
> Warning 1: this is for review & testing only
> Warning 2: it's not (yet) bissectable between patches 40 & 43

We might want to fix that. I will take a look later tonight.

> Warning 3: simplify_loads is still broken and will need the same
>            fix (but the code is currently disabled)
>
>
> This series is  available in the git repository at:
>
>   git://github.com/lucvoo/sparse.git mem2reg
>

Here comes the patch bombs again :-)

I will take a look at it tonight.

Thanks for the patches.

Chris

Re: [RFC PATCH 00/48] fix promotion of symbol to register

[Christopher Li]

On Wed, Aug 23, 2017 at 4:15 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
>   git://github.com/lucvoo/sparse.git mem2reg
>

Hi Luc, I did not see your mem2reg branch on github.
Did you push it on github?

Sorry haven't have chance to get to it earlier.

Of course I can still apply patch for testing.

Chris

Re: [RFC PATCH 00/48] fix promotion of symbol to register

[Christopher Li]

On Sun, Aug 27, 2017 at 12:40 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Wed, Aug 23, 2017 at 4:15 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>>
>>   git://github.com/lucvoo/sparse.git mem2reg
>>
>
> Hi Luc, I did not see your mem2reg branch on github.
> Did you push it on github?
>
> Sorry haven't have chance to get to it earlier.

Hmm, with all the patch applied. sparse seems takes forever on
two files of the full kernel check stress test. It looks like it is
in a deadloop.

 sound/pci/hda/hda_generic.c
 drivers/block/drbd/drbd_receiver.c

Chris

Re: [RFC PATCH 00/48] fix promotion of symbol to register

[Christopher Li]

On Sun, Aug 27, 2017 at 1:16 AM, Christopher Li <sparse@chrisli.org> wrote:
> Hmm, with all the patch applied. sparse seems takes forever on
> two files of the full kernel check stress test. It looks like it is
> in a deadloop.
>
>  sound/pci/hda/hda_generic.c
>  drivers/block/drbd/drbd_receiver.c

Hi Luc, are you seeing this at all?

The full kernel check sparse is hanging on these two files.

>>>   git://github.com/lucvoo/sparse.git mem2reg
>>>

I haven't able to fetch your branch yet. The above
result is by applying patches to master.

Thanks

Chris

Re: [RFC PATCH 00/48] fix promotion of symbol to register

[Luc Van Oostenryck]

On Tue, Aug 29, 2017 at 2:37 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Sun, Aug 27, 2017 at 1:16 AM, Christopher Li <sparse@chrisli.org> wrote:
>> Hmm, with all the patch applied. sparse seems takes forever on
>> two files of the full kernel check stress test. It looks like it is
>> in a deadloop.
>>
>>  sound/pci/hda/hda_generic.c
>>  drivers/block/drbd/drbd_receiver.c
>
> Hi Luc, are you seeing this at all?
>
> The full kernel check sparse is hanging on these two files.

Yes, I know.
It's not a big problem in itself (was quickly solved) but ...

>>>>   git://github.com/lucvoo/sparse.git mem2reg
>>>>
>
> I haven't able to fetch your branch yet. The above
> result is by applying patches to master.

Yes, I removed it once I had some doubts about the whole series.
I hadn't the opportunity to send an email asking to ignore the series,
sorry about that.

-- Luc