* [PATCH 2/4] ssa: the sparse set is not needed
2021-03-09 23:42 [PATCH 0/4] fix SSA conversion of mismatched memops Luc Van Oostenryck
2021-03-09 23:42 ` [PATCH 1/4] ssa: add some testcases for " Luc Van Oostenryck
@ 2021-03-09 23:42 ` Luc Van Oostenryck
2021-03-09 23:42 ` [PATCH 3/4] ssa: avoid SSA conversion of packed bitfields Luc Van Oostenryck
2021-03-09 23:42 ` [PATCH 4/4] ssa: fix conversion with mismatched size or offset Luc Van Oostenryck
3 siblings, 0 replies; 5+ messages in thread
From: Luc Van Oostenryck @ 2021-03-09 23:42 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
The implementation of a 'sparse set without initialization' was
somehow needed during the initial design but it's not needed anymore.
So, remove the implementation and replace its use by the usual
bb->generation mechanism.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
Makefile | 1 -
ssa.c | 11 ++++-------
sset.c | 28 ----------------------------
sset.h | 56 --------------------------------------------------------
4 files changed, 4 insertions(+), 92 deletions(-)
delete mode 100644 sset.c
delete mode 100644 sset.h
diff --git a/Makefile b/Makefile
index f9883da101c7..6ad14375b3cd 100644
--- a/Makefile
+++ b/Makefile
@@ -63,7 +63,6 @@ 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
LIB_OBJS += symbol.o
diff --git a/ssa.c b/ssa.c
index b9044207db16..3f4fa1a831df 100644
--- a/ssa.c
+++ b/ssa.c
@@ -7,7 +7,6 @@
#include <assert.h>
#include "ssa.h"
#include "lib.h"
-#include "sset.h"
#include "dominate.h"
#include "flowgraph.h"
#include "linearize.h"
@@ -162,13 +161,12 @@ static bool rewrite_single_store(struct instruction *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)
{
+ unsigned long generation = ++bb_generation;
struct basic_block_list *alpha = NULL;
struct basic_block_list *idf = NULL;
struct basic_block *samebb = NULL;
@@ -199,7 +197,6 @@ static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *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;
@@ -208,8 +205,10 @@ static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
case OP_STORE:
nbr_stores++;
store = insn;
- if (!sset_testset(processed, bb->nr))
+ if (bb->generation != generation) {
+ bb->generation = generation;
add_bb(&alpha, bb);
+ }
/* fall through */
case OP_LOAD:
if (local) {
@@ -390,8 +389,6 @@ void ssa_convert(struct entrypoint *ep)
bb->phi_map = NULL;
} 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);
diff --git a/sset.c b/sset.c
deleted file mode 100644
index e9681e00ddd4..000000000000
--- a/sset.c
+++ /dev/null
@@ -1,28 +0,0 @@
-// SPDX-License-Identifier: MIT
-//
-// sset.c - an all O(1) implementation of sparse sets as presented in:
-// "An Efficient Representation for Sparse Sets"
-// by Preston Briggs and Linda Torczon
-//
-// Copyright (C) 2017 - Luc Van Oostenryck
-
-#include "sset.h"
-#include "lib.h"
-#include <stdlib.h>
-
-
-struct sset *sset_init(unsigned int first, unsigned int last)
-{
- unsigned int size = last - first + 1;
- struct sset *s = malloc(sizeof(*s) + size * 2 * sizeof(s->sets[0]));
-
- s->size = size;
- s->off = first;
- s->nbr = 0;
- return s;
-}
-
-void sset_free(struct sset *s)
-{
- free(s);
-}
diff --git a/sset.h b/sset.h
deleted file mode 100644
index 69cee18a2768..000000000000
--- a/sset.h
+++ /dev/null
@@ -1,56 +0,0 @@
-// SPDX-License-Identifier: MIT
-
-#ifndef SSET_H
-#define SSET_H
-
-/*
- * sset.h - an all O(1) implementation of sparse sets as presented in:
- * "An Efficient Representation for Sparse Sets"
- * by Preston Briggs and Linda Torczon
- *
- * Copyright (C) 2017 - Luc Van Oostenryck
- */
-
-#include <stdbool.h>
-
-struct sset {
- unsigned int nbr;
- unsigned int off;
- unsigned int size;
- unsigned int sets[0];
-};
-
-extern struct sset *sset_init(unsigned int size, unsigned int off);
-extern void sset_free(struct sset *s);
-
-
-static inline void sset_reset(struct sset *s)
-{
- s->nbr = 0;
-}
-
-static inline void sset_add(struct sset *s, unsigned int idx)
-{
- unsigned int __idx = idx - s->off;
- unsigned int n = s->nbr++;
- s->sets[__idx] = n;
- s->sets[s->size + n] = __idx;
-}
-
-static inline bool sset_test(struct sset *s, unsigned int idx)
-{
- unsigned int __idx = idx - s->off;
- unsigned int n = s->sets[__idx];
-
- return (n < s->nbr) && (s->sets[s->size + n] == __idx);
-}
-
-static inline bool sset_testset(struct sset *s, unsigned int idx)
-{
- if (sset_test(s, idx))
- return true;
- sset_add(s, idx);
- return false;
-}
-
-#endif
--
2.30.0
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH 4/4] ssa: fix conversion with mismatched size or offset
2021-03-09 23:42 [PATCH 0/4] fix SSA conversion of mismatched memops Luc Van Oostenryck
` (2 preceding siblings ...)
2021-03-09 23:42 ` [PATCH 3/4] ssa: avoid SSA conversion of packed bitfields Luc Van Oostenryck
@ 2021-03-09 23:42 ` Luc Van Oostenryck
3 siblings, 0 replies; 5+ messages in thread
From: Luc Van Oostenryck @ 2021-03-09 23:42 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
The SSA conversion works under the assumption that all the memory
operations on a given symbol always refer to the same object.
So, exclude the conversion of variables where:
* memory operations do not always match in size or offset
* there is an implicit integer/float conversion.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
linearize.h | 2 +-
ssa.c | 97 ++++++++++++++++++++++------
validation/mem2reg/not-same-memop0.c | 1 -
3 files changed, 80 insertions(+), 20 deletions(-)
diff --git a/linearize.h b/linearize.h
index 7909b01f29c5..86ae119c82e6 100644
--- a/linearize.h
+++ b/linearize.h
@@ -18,7 +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);
+DECLARE_PTRMAP(phi_map, struct symbol *, struct instruction *);
enum pseudo_type {
diff --git a/ssa.c b/ssa.c
index 26d46baaa16c..f61672a0b530 100644
--- a/ssa.c
+++ b/ssa.c
@@ -96,10 +96,22 @@ static void kill_store(struct instruction *insn)
insn->bb = NULL;
}
+static bool same_memop(struct instruction *a, struct instruction *b)
+{
+ if (a->size != b->size || a->offset != b->offset)
+ return false;
+ if (is_integral_type(a->type) && is_float_type(b->type))
+ return false;
+ if (is_float_type(a->type) && is_integral_type(b->type))
+ return false;
+ return true;
+}
+
static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses)
{
+ struct instruction *store = NULL;
struct instruction *insn;
- pseudo_t val = NULL;
+ bool remove = false;
if (!bb)
return;
@@ -110,18 +122,21 @@ static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_sto
continue;
switch (insn->opcode) {
case OP_LOAD:
- if (!val)
- val = undef_pseudo();
- replace_with_pseudo(insn, val);
+ if (!store)
+ replace_with_pseudo(insn, undef_pseudo());
+ else if (same_memop(store, insn))
+ replace_with_pseudo(insn, store->target);
+ else
+ remove = false;
break;
case OP_STORE:
- val = insn->target;
- // can't use kill_instruction() unless
- // we add a fake user to val
- kill_store(insn);
+ store = insn;
+ remove = true;
break;
}
} END_FOR_EACH_PTR(insn);
+ if (remove)
+ kill_store(store);
}
static bool rewrite_single_store(struct instruction *store)
@@ -139,6 +154,8 @@ static bool rewrite_single_store(struct instruction *store)
// by the value from the store. This is only valid
// if the store dominate the load.
+ if (!same_memop(store, insn))
+ continue;
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.
@@ -257,21 +274,40 @@ external_visibility:
kill_dead_stores(ep, addr, !mod);
}
-static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var)
+static struct instruction *lookup_var(struct basic_block *bb, struct symbol *var)
{
do {
- pseudo_t val = phi_map_lookup(bb->phi_map, var);
- if (val)
- return val;
+ struct instruction *insn = phi_map_lookup(bb->phi_map, var);
+ if (insn)
+ return insn;
} while ((bb = bb->idom));
- return undef_pseudo();
+ return NULL;
}
static struct instruction_list *phis_all;
static struct instruction_list *phis_used;
+static struct instruction_list *stores;
+
+static bool matching_load(struct instruction *def, struct instruction *insn)
+{
+ if (insn->size != def->size)
+ return false;
+ switch (def->opcode) {
+ case OP_STORE:
+ case OP_LOAD:
+ if (insn->offset != def->offset)
+ return false;
+ case OP_PHI:
+ break;
+ default:
+ return false;
+ }
+ return true;
+}
static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
{
+ struct instruction *def;
struct symbol *var;
pseudo_t addr;
pseudo_t val;
@@ -284,8 +320,8 @@ static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
var = addr->sym;
if (!var || !var->torename)
break;
- phi_map_update(&bb->phi_map, var, insn->target);
- kill_store(insn);
+ phi_map_update(&bb->phi_map, var, insn);
+ add_instruction(&stores, insn);
break;
case OP_LOAD:
addr = insn->src;
@@ -294,14 +330,22 @@ static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
var = addr->sym;
if (!var || !var->torename)
break;
- val = lookup_var(bb, var);
+ def = lookup_var(bb, var);
+ if (!def) {
+ val = undef_pseudo();
+ } else if (!matching_load(def, insn)) {
+ var->torename = false;
+ break;
+ } else {
+ val = def->target;
+ }
replace_with_pseudo(insn, val);
break;
case OP_PHI:
var = insn->type;
if (!var || !var->torename)
break;
- phi_map_update(&bb->phi_map, var, insn->target);
+ phi_map_update(&bb->phi_map, var, insn);
add_instruction(&phis_all, insn);
break;
}
@@ -348,7 +392,8 @@ static void ssa_rename_phi(struct instruction *insn)
return;
FOR_EACH_PTR(insn->bb->parents, par) {
struct instruction *term = delete_last_instruction(&par->insns);
- pseudo_t val = lookup_var(par, var);
+ struct instruction *def = lookup_var(par, var);
+ pseudo_t val = def ? def->target : undef_pseudo();
pseudo_t phi = alloc_phi(par, val, var);
phi->ident = var->ident;
add_instruction(&par->insns, term);
@@ -376,6 +421,18 @@ static void ssa_rename_phis(struct entrypoint *ep)
} END_FOR_EACH_PTR(phi);
}
+static void remove_dead_stores(struct instruction_list *stores)
+{
+ struct instruction *store;
+
+ FOR_EACH_PTR(stores, store) {
+ struct symbol *var = store->addr->sym;
+
+ if (var->torename)
+ kill_store(store);
+ } END_FOR_EACH_PTR(store);
+}
+
void ssa_convert(struct entrypoint *ep)
{
struct basic_block *bb;
@@ -393,6 +450,7 @@ void ssa_convert(struct entrypoint *ep)
} END_FOR_EACH_PTR(bb);
// try to promote memory accesses to pseudos
+ stores = NULL;
FOR_EACH_PTR(ep->accesses, pseudo) {
ssa_convert_one_var(ep, pseudo->sym);
} END_FOR_EACH_PTR(pseudo);
@@ -401,4 +459,7 @@ void ssa_convert(struct entrypoint *ep)
phis_all = phis_used = NULL;
ssa_rename_insns(ep);
ssa_rename_phis(ep);
+
+ // remove now dead stores
+ remove_dead_stores(stores);
}
diff --git a/validation/mem2reg/not-same-memop0.c b/validation/mem2reg/not-same-memop0.c
index 7a84ddce4efc..4de981956b74 100644
--- a/validation/mem2reg/not-same-memop0.c
+++ b/validation/mem2reg/not-same-memop0.c
@@ -16,7 +16,6 @@ static void foo(struct s s)
/*
* check-name: not-same-memop0
* check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file
- * check-known-to-fail
*
* check-output-start
local:
--
2.30.0
^ permalink raw reply related [flat|nested] 5+ messages in thread