This patch implement the SSA conversion in the classical way,
via the iterated dominance frontier.
It's a drop-in replacement for simplify_symbol_usage() which
has several problems with the placement of phi-nodes.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
---
Makefile | 1 +
linearize.h | 4 +
optimize.c | 3 +-
ssa.c | 369 ++++++++++++++++++++++++++++++++++++++
ssa.h | 6 +
symbol.h | 1 +
validation/mem2reg/broken-phi02.c | 1 -
validation/mem2reg/broken-phi03.c | 1 -
validation/mem2reg/cond-expr5.c | 1 -
validation/mem2reg/quadra00.c | 1 -
validation/mem2reg/quadra01.c | 1 +
validation/mem2reg/stray-phisrc.c | 1 -
validation/mem2reg/undef00.c | 1 -
validation/optim/cse-size.c | 3 +-
validation/optim/missing-select.c | 1 -
validation/var-undef-partial.c | 1 -
16 files changed, 385 insertions(+), 11 deletions(-)
create mode 100644 ssa.c
create mode 100644 ssa.h
diff --git a/Makefile b/Makefile
index 43bbaa9bc..7e0d4ad92 100644
--- a/Makefile
+++ b/Makefile
@@ -58,6 +58,7 @@ LIB_OBJS += scope.o
LIB_OBJS += show-parse.o
LIB_OBJS += simplify.o
LIB_OBJS += sort.o
+LIB_OBJS += ssa.o
LIB_OBJS += sset.o
LIB_OBJS += stats.o
LIB_OBJS += storage.o
diff --git a/linearize.h b/linearize.h
index 0aaf11da5..5592b2c52 100644
--- a/linearize.h
+++ b/linearize.h
@@ -7,6 +7,7 @@
#include "opcode.h"
#include "parse.h"
#include "symbol.h"
+#include "ptrmap.h"
struct instruction;
@@ -17,6 +18,7 @@ struct pseudo_user {
DECLARE_ALLOCATOR(pseudo_user);
DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user);
+DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t);
enum pseudo_type {
@@ -100,6 +102,7 @@ struct instruction {
struct multijmp_list *multijmp_list;
};
struct /* phi_node */ {
+ pseudo_t phi_var; // used for SSA conversion
struct pseudo_list *phi_list;
};
struct /* phi source */ {
@@ -269,6 +272,7 @@ struct basic_block {
struct instruction_list *insns; /* Linear list of instructions */
struct basic_block *idom; /* link to the immediate dominator */
struct basic_block_list *doms; /* list of BB idominated by this one */
+ struct phi_map *phi_map;
struct pseudo_list *needs, *defines;
union {
unsigned int nr; /* unique id for label's names */
diff --git a/optimize.c b/optimize.c
index 2f9c7910d..429d42433 100644
--- a/optimize.c
+++ b/optimize.c
@@ -12,6 +12,7 @@
#include "liveness.h"
#include "flow.h"
#include "cse.h"
+#include "ssa.h"
int repeat_phase;
@@ -58,7 +59,7 @@ void optimize(struct entrypoint *ep)
* Turn symbols into pseudos
*/
if (fpasses & PASS_MEM2REG)
- simplify_symbol_usage(ep);
+ ssa_convert(ep);
if (fdump_ir & PASS_MEM2REG)
show_entry(ep);
diff --git a/ssa.c b/ssa.c
new file mode 100644
index 000000000..85f8acde2
--- /dev/null
+++ b/ssa.c
@@ -0,0 +1,369 @@
+// SPDX-License-Identifier: MIT
+//
+// SSA conversion
+// Copyright (C) 2005 Luc Van Oostenryck
+//
+
+#include <assert.h>
+#include "lib.h"
+#include "sset.h"
+#include "dominate.h"
+#include "flowgraph.h"
+#include "linearize.h"
+#include "flow.h" // for convert_load_instruction()
+
+
+// Is it possible and desirable for this to be promoted to a pseudo?
+static inline bool is_promotable(struct symbol *type)
+{
+ struct symbol *member;
+ int bf_seen;
+ int nbr;
+
+ if (type->type == SYM_NODE)
+ type = type->ctype.base_type;
+ switch (type->type) {
+ case SYM_ENUM:
+ case SYM_BITFIELD:
+ case SYM_PTR:
+ case SYM_RESTRICT: // OK, always integer types
+ return 1;
+ case SYM_STRUCT:
+ if (type->bit_size > long_ctype.bit_size)
+ return 0;
+ // we allow a single scalar field
+ // but a run of bitfields count for 1
+ nbr = 0;
+ bf_seen = 0;
+ FOR_EACH_PTR(type->symbol_list, member) {
+ if (is_bitfield_type(member)) {
+ if (bf_seen)
+ continue;
+ bf_seen = 1;
+ } else {
+ bf_seen = 0;
+ }
+ if (!is_scalar_type(member))
+ return 0;
+ if (nbr++)
+ return 0;
+ } END_FOR_EACH_PTR(member);
+ return 1;
+ case SYM_UNION:
+ // FIXME: should be like struct but has problem
+ // when used with/for type cohercion
+ // -----> OK if only same sized integral types
+ FOR_EACH_PTR(type->symbol_list, member) {
+ if (member->bit_size != type->bit_size)
+ return 0;
+ if (!is_integral_type(member))
+ return 0;
+ } END_FOR_EACH_PTR(member);
+ return 1;
+ default:
+ break;
+ }
+ if (type->ctype.base_type == &int_type)
+ return 1;
+ if (type->ctype.base_type == &fp_type)
+ return 1;
+ return 0;
+}
+
+static bool insn_before(struct instruction *a, struct instruction *b)
+{
+ struct basic_block *bb = a->bb;
+ struct instruction *insn;
+
+ assert(b->bb == bb);
+ FOR_EACH_PTR(bb->insns, insn) {
+ if (insn == a)
+ return true;
+ if (insn == b)
+ return false;
+ } END_FOR_EACH_PTR(insn);
+ assert(0);
+}
+
+static void kill_store(struct instruction *insn)
+{
+ remove_use(&insn->src);
+ remove_use(&insn->target);
+ insn->bb = NULL;
+}
+
+static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses)
+{
+ struct instruction *insn;
+ pseudo_t val = NULL;
+
+ if (!bb)
+ return;
+
+ FOR_EACH_PTR(bb->insns, insn) {
+
+ if (!insn->bb || insn->src != addr)
+ continue;
+ switch (insn->opcode) {
+ case OP_LOAD:
+ if (!val)
+ val = undef_pseudo();
+ convert_load_instruction(insn, val);
+ break;
+ case OP_STORE:
+ val = insn->target;
+ // can't use kill_instruction() unless
+ // we add a fake user to val
+ kill_store(insn);
+ break;
+ }
+ } END_FOR_EACH_PTR(insn);
+}
+
+static bool rewrite_single_store(struct instruction *store)
+{
+ pseudo_t addr = store->src;
+ struct pseudo_user *pu;
+
+ FOR_EACH_PTR(addr->users, pu) {
+ struct instruction *insn = pu->insn;
+
+ if (insn->opcode != OP_LOAD)
+ continue;
+
+ // Let's try to replace the value of the load
+ // by the value from the store. This is only valid
+ // if the store dominate the load.
+
+ if (insn->bb == store->bb) {
+ // the load and the store are in the same BB
+ // we can convert if the load is after the store.
+ if (!insn_before(store, insn))
+ continue;
+ } else if (!domtree_dominates(store->bb, insn->bb)) {
+ // we can't convert this load
+ continue;
+ }
+
+ // OK, we can rewrite this load
+
+ // undefs ?
+
+ convert_load_instruction(insn, store->target);
+ } END_FOR_EACH_PTR(pu);
+
+ // is there some unconverted loads?
+ if (pseudo_user_list_size(addr->users) > 1)
+ return false;
+
+ kill_store(store);
+ return true;
+}
+
+static struct sset *processed;
+
+// we would like to know:
+// is there one or more stores?
+// are all loads & stores local/done in a single block?
+static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
+{
+ struct basic_block_list *alpha = NULL;
+ struct basic_block_list *idf = NULL;
+ struct basic_block *samebb = NULL;
+ struct instruction *store = NULL;
+ struct basic_block *bb;
+ struct pseudo_user *pu;
+ unsigned long mod = var->ctype.modifiers;
+ bool local = true;
+ int nbr_stores = 0;
+ int nbr_uses = 0;
+ pseudo_t addr;
+
+ /* Never used as a symbol? */
+ addr = var->pseudo;
+ if (!addr)
+ return;
+
+ /* We don't do coverage analysis of volatiles.. */
+ if (mod & MOD_VOLATILE)
+ return;
+
+ /* ..and symbols with external visibility need more care */
+ mod &= (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
+ if (mod)
+ goto external_visibility;
+
+ if (!is_promotable(var))
+ return;
+
+ // 1) insert in the worklist all BBs that may modify var
+ sset_reset(processed);
+ FOR_EACH_PTR(addr->users, pu) {
+ struct instruction *insn = pu->insn;
+ struct basic_block *bb = insn->bb;
+
+ switch (insn->opcode) {
+ case OP_STORE:
+ nbr_stores++;
+ store = insn;
+ if (!sset_testset(processed, bb->nr))
+ add_bb(&alpha, bb);
+ /* fall through */
+ case OP_LOAD:
+ if (local) {
+ if (!samebb)
+ samebb = bb;
+ else if (samebb != bb)
+ local = false;
+ }
+ nbr_uses++;
+ break;
+ case OP_SYMADDR:
+ mod |= MOD_ADDRESSABLE;
+ goto external_visibility;
+ default:
+ warning(var->pos, "symbol '%s' pseudo used in unexpected way",
+ show_ident(var->ident));
+ }
+ } END_FOR_EACH_PTR(pu);
+
+ if (nbr_stores == 1) {
+ if (rewrite_single_store(store))
+ return;
+ }
+
+ // if all uses are local to a single block
+ // they can easily be rewritten and doesn't need phi-nodes
+ // FIXME: could be done for extended BB too
+ if (local) {
+ rewrite_local_var(samebb, addr, nbr_stores, nbr_uses);
+ return;
+ }
+
+ idf_compute(ep, &idf, alpha);
+ FOR_EACH_PTR(idf, bb) {
+ struct instruction *node = insert_phi_node(bb, var);
+ node->phi_var = var->pseudo;
+ } END_FOR_EACH_PTR(bb);
+ var->torename = 1;
+
+external_visibility:
+ if (mod & (MOD_NONLOCAL | MOD_STATIC))
+ return;
+ kill_dead_stores(ep, addr, !mod);
+}
+
+static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var)
+{
+ do {
+ pseudo_t val = phi_map_lookup(bb->phi_map, var);
+ if (val)
+ return val;
+ } while ((bb = bb->idom));
+ return undef_pseudo();
+}
+
+static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
+{
+ struct symbol *var;
+ pseudo_t addr;
+ pseudo_t val;
+
+ switch (insn->opcode) {
+ case OP_STORE:
+ addr = insn->src;
+ if (addr->type != PSEUDO_SYM)
+ break;
+ var = addr->sym;
+ if (!var || !var->torename)
+ break;
+ phi_map_update(&bb->phi_map, var, insn->target);
+ kill_store(insn);
+ break;
+ case OP_LOAD:
+ addr = insn->src;
+ if (addr->type != PSEUDO_SYM)
+ break;
+ var = addr->sym;
+ if (!var || !var->torename)
+ break;
+ val = lookup_var(bb, var);
+ convert_load_instruction(insn, val);
+ break;
+ case OP_PHI:
+ var = insn->type;
+ if (!var || !var->torename)
+ break;
+ phi_map_update(&bb->phi_map, var, insn->target);
+ break;
+ }
+}
+
+static void ssa_rename_phi(struct basic_block *bb, struct instruction *insn)
+{
+ struct basic_block *par;
+ struct symbol *var;
+
+ if (!insn->phi_var)
+ return;
+ var = insn->phi_var->sym;
+ if (!var->torename)
+ return;
+ FOR_EACH_PTR(bb->parents, par) {
+ struct instruction *term = delete_last_instruction(&par->insns);
+ pseudo_t val = lookup_var(par, var);
+ pseudo_t phi = alloc_phi(par, val, var);
+ phi->ident = var->ident;
+ add_instruction(&par->insns, term);
+ use_pseudo(insn, phi, add_pseudo(&insn->phi_list, phi));
+ } END_FOR_EACH_PTR(par);
+}
+
+static void ssa_rename_vars(struct entrypoint *ep)
+{
+ struct basic_block *bb;
+
+ FOR_EACH_PTR(ep->bbs, bb) {
+ struct instruction *insn;
+ FOR_EACH_PTR(bb->insns, insn) {
+ if (!insn->bb)
+ continue;
+ ssa_rename_insn(bb, insn);
+ } END_FOR_EACH_PTR(insn);
+ } END_FOR_EACH_PTR(bb);
+
+ FOR_EACH_PTR(ep->bbs, bb) {
+ struct instruction *insn;
+ FOR_EACH_PTR(bb->insns, insn) {
+ if (!insn->bb || insn->opcode != OP_PHI)
+ continue;
+ ssa_rename_phi(bb, insn);
+ } END_FOR_EACH_PTR(insn);
+ } END_FOR_EACH_PTR(bb);
+}
+
+void ssa_convert(struct entrypoint *ep)
+{
+ struct basic_block *bb;
+ pseudo_t pseudo;
+ int first, last;
+
+ // calculate the number of BBs
+ first = ep->entry->bb->nr;
+ last = first;
+ FOR_EACH_PTR(ep->bbs, bb) {
+ int nr = bb->nr;
+ if (nr > last)
+ last = nr;
+ } END_FOR_EACH_PTR(bb);
+
+ processed = sset_init(first, last);
+
+ // try to promote memory accesses to pseudos
+ FOR_EACH_PTR(ep->accesses, pseudo) {
+ ssa_convert_one_var(ep, pseudo->sym);
+ } END_FOR_EACH_PTR(pseudo);
+
+ // rename the converted accesses
+ ssa_rename_vars(ep);
+}
diff --git a/ssa.h b/ssa.h
new file mode 100644
index 000000000..cbcbc3a41
--- /dev/null
+++ b/ssa.h
@@ -0,0 +1,6 @@
+#ifndef SSA_H
+#define SSA_H
+
+void ssa_convert(struct entrypoint *ep);
+
+#endif
diff --git a/symbol.h b/symbol.h
index 5901a85aa..a4fdbcfec 100644
--- a/symbol.h
+++ b/symbol.h
@@ -173,6 +173,7 @@ struct symbol {
designated_init:1,
forced_arg:1,
accessed:1,
+ torename:1,
transparent_union:1;
struct expression *array_size;
struct ctype ctype;
diff --git a/validation/mem2reg/broken-phi02.c b/validation/mem2reg/broken-phi02.c
index 69776e0f1..5aa650716 100644
--- a/validation/mem2reg/broken-phi02.c
+++ b/validation/mem2reg/broken-phi02.c
@@ -22,7 +22,6 @@ int foo(int a, int b)
* is used) causes a missed select-conversion at later stage.
*
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
* check-output-ignore
* check-output-contains: select\\.
*/
diff --git a/validation/mem2reg/broken-phi03.c b/validation/mem2reg/broken-phi03.c
index 58b479791..eff1ff8a8 100644
--- a/validation/mem2reg/broken-phi03.c
+++ b/validation/mem2reg/broken-phi03.c
@@ -23,7 +23,6 @@ int foo(int a, int b)
* is used) causes a missed select-conversion at later stage.
*
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
* check-output-ignore
* check-output-contains: select\\.
*/
diff --git a/validation/mem2reg/cond-expr5.c b/validation/mem2reg/cond-expr5.c
index 62ac6c15d..a3ce5e3a9 100644
--- a/validation/mem2reg/cond-expr5.c
+++ b/validation/mem2reg/cond-expr5.c
@@ -11,7 +11,6 @@ int foo(int p, int q, int a)
/*
* check-name: cond-expr5
* check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file
- * check-known-to-fail
*
* check-output-ignore
* check-output-excludes: load\\.
diff --git a/validation/mem2reg/quadra00.c b/validation/mem2reg/quadra00.c
index 63b489c98..69ddc9772 100644
--- a/validation/mem2reg/quadra00.c
+++ b/validation/mem2reg/quadra00.c
@@ -20,7 +20,6 @@ int foo(int *a, int b, int c)
/*
* check-name: quadratic phisrc
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
* check-output-ignore
* check-output-excludes: phi\\..*, .*, .*
* check-output-excludes: phi\\..*, .*, .*, .*
diff --git a/validation/mem2reg/quadra01.c b/validation/mem2reg/quadra01.c
index b71f46969..bab337f2b 100644
--- a/validation/mem2reg/quadra01.c
+++ b/validation/mem2reg/quadra01.c
@@ -20,6 +20,7 @@ static void foo(void) {
* check-name: quadratic @ liveness
* check-command: test-linearize -I. $file
* check-timeout:
+ * check-known-to-fail
*
* check-output-ignore
* check-output-excludes: phi\\.
diff --git a/validation/mem2reg/stray-phisrc.c b/validation/mem2reg/stray-phisrc.c
index e9f35c89c..0da7df7a4 100644
--- a/validation/mem2reg/stray-phisrc.c
+++ b/validation/mem2reg/stray-phisrc.c
@@ -18,7 +18,6 @@ static int foo(int **g)
/*
* check-name: stray phisrc
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
*
* check-output-ignore
* check-output-excludes: phisrc\\.
diff --git a/validation/mem2reg/undef00.c b/validation/mem2reg/undef00.c
index 27f0aaa82..20ea962ce 100644
--- a/validation/mem2reg/undef00.c
+++ b/validation/mem2reg/undef00.c
@@ -13,7 +13,6 @@ static void badw(int v)
/*
* check-name: undef00
* check-command: test-linearize -fdump-ir=mem2reg $file
- * check-known-to-fail
* check-output-ignore
* check-output-pattern(1): load\\.
* check-output-pattern(1): load\\..*\\[UNDEF\\]
diff --git a/validation/optim/cse-size.c b/validation/optim/cse-size.c
index b75e4bfe9..e98c3cde7 100644
--- a/validation/optim/cse-size.c
+++ b/validation/optim/cse-size.c
@@ -13,6 +13,5 @@ static void foo(void)
* check-command: test-linearize -Wno-decl $file
*
* check-output-ignore
- * check-output-excludes: phi\\.
- * check-output-excludes: phisrc\\.
+ * check-output-pattern(2): phi\\.
*/
diff --git a/validation/optim/missing-select.c b/validation/optim/missing-select.c
index 4796e0586..07ea008f9 100644
--- a/validation/optim/missing-select.c
+++ b/validation/optim/missing-select.c
@@ -17,7 +17,6 @@ static int foo(int **g)
/*
* check-name: missing-select
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
*
* check-output-ignore
* check-output-contains: select\\.
diff --git a/validation/var-undef-partial.c b/validation/var-undef-partial.c
index 2b6658342..f1a07bea7 100644
--- a/validation/var-undef-partial.c
+++ b/validation/var-undef-partial.c
@@ -16,6 +16,5 @@ int foo(int a, int b)
* check-description: trigger a bug in symbol/memop simplification
* check-description: sparse-llvm is used here as semantic checker of sparse's IR
* check-command: sparse-llvm -Wno-decl $file
- * check-known-to-fail
* check-output-ignore
*/
--
2.16.2
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
