aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
authorLuc Van Oostenryck <luc.vanoostenryck@gmail.com>2018-08-25 09:40:52 +0200
committerLuc Van Oostenryck <luc.vanoostenryck@gmail.com>2018-08-25 14:25:48 +0200
commitfd43eab36ea0bb18942e3a7233db2efed4b84b30 (patch)
tree47162ba3fa25b6d13b1e18e76e3c4c56f6384162
parentdc49365a8026fad63297ffde53ca72e4252f4959 (diff)
parent13cf4aaeef36031fcee071a1efcf9092b7d7cdf7 (diff)
downloadsparse-dev-fd43eab36ea0bb18942e3a7233db2efed4b84b30.tar.gz
Merge branch 'kill-dead-stores' into tip
* fix buggy recursion in kill_dead_stores() * kill dead stores again after memops simplification is done. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Diffstat
-rw-r--r--flow.c95
-rw-r--r--flow.h1
-rw-r--r--memops.c12
-rw-r--r--validation/optim/kill-stores0.c34
-rw-r--r--validation/optim/kill-stores1.c48
-rw-r--r--validation/optim/kill-stores2.c17
-rw-r--r--validation/optim/live-stores0.c29
7 files changed, 214 insertions, 22 deletions
diff --git a/flow.c b/flow.c
index 9483938f..8bdd5984 100644
--- a/flow.c
+++ b/flow.c
@@ -547,7 +547,21 @@ found:
}
/* 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)
+// The context is:
+// * the variable is not global but may have its address used (local/non-local)
+// * the stores are only needed by others functions which would do some
+// loads via the escaped address
+// We start by the terminating BB (normal exit BB + no-return/unreachable)
+// We walkup the BB' intruction backward
+// * we're only concerned by loads, stores & calls
+// * if we reach a call -> we have to stop if var is non-local
+// * if we reach a load of our var -> we have to stop
+// * if we reach a store of our var -> we can kill it, it's dead
+// * we can ignore other stores & loads if the var is local
+// * if we reach another store or load done via non-symbol access
+// (so done via some address calculation) -> we have to stop
+// If we reach the top of the BB we can recurse into the parents BBs.
+static void kill_dead_stores_bb(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local)
{
struct instruction *insn;
struct basic_block *parent;
@@ -556,36 +570,33 @@ static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct b
return;
bb->generation = generation;
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;
- if (opcode == OP_CALL)
+ switch (insn->opcode) {
+ case OP_LOAD:
+ if (insn->src == pseudo)
return;
- continue;
- }
- if (insn->src == pseudo) {
- if (opcode == OP_LOAD)
+ break;
+ case OP_STORE:
+ if (insn->src == pseudo) {
+ kill_instruction_force(insn);
+ continue;
+ }
+ break;
+ case OP_CALL:
+ if (!local)
return;
- kill_instruction_force(insn);
+ default:
continue;
}
- if (local)
- continue;
- if (insn->src->type != PSEUDO_SYM)
+ if (!local && 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);
+ if (bb_list_size(parent->children) > 1)
+ continue;
+ kill_dead_stores_bb(pseudo, generation, parent, local);
} END_FOR_EACH_PTR(parent);
}
@@ -735,7 +746,7 @@ external_visibility:
struct basic_block *bb;
FOR_EACH_PTR(ep->bbs, bb) {
if (!bb->children)
- kill_dead_stores(pseudo, ++bb_generation, bb, !mod);
+ kill_dead_stores_bb(pseudo, ++bb_generation, bb, !mod);
} END_FOR_EACH_PTR(bb);
}
}
@@ -752,6 +763,46 @@ void simplify_symbol_usage(struct entrypoint *ep)
} END_FOR_EACH_PTR(pseudo);
}
+static struct pseudo_user *first_user(pseudo_t p)
+{
+ struct pseudo_user *pu;
+ FOR_EACH_PTR(p->users, pu) {
+ if (!pu)
+ continue;
+ return pu;
+ } END_FOR_EACH_PTR(pu);
+ return NULL;
+}
+
+void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local)
+{
+ unsigned long generation;
+ struct basic_block *bb;
+
+ switch (pseudo_user_list_size(addr->users)) {
+ case 0:
+ return;
+ case 1:
+ if (local) {
+ struct pseudo_user *pu = first_user(addr);
+ struct instruction *insn = pu->insn;
+ if (insn->opcode == OP_STORE) {
+ kill_instruction_force(insn);
+ return;
+ }
+ }
+ default:
+ break;
+ }
+
+ generation = ++bb_generation;
+ FOR_EACH_PTR(ep->bbs, bb) {
+ if (bb->children)
+ continue;
+ kill_dead_stores_bb(addr, generation, bb, local);
+ } END_FOR_EACH_PTR(bb);
+}
+
static void mark_bb_reachable(struct basic_block *bb, unsigned long generation)
{
struct basic_block *child;
diff --git a/flow.h b/flow.h
index 14cc144c..c8e12cf0 100644
--- a/flow.h
+++ b/flow.h
@@ -14,6 +14,7 @@ struct instruction;
extern int simplify_flow(struct entrypoint *ep);
+extern void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local);
extern void simplify_symbol_usage(struct entrypoint *ep);
extern void simplify_memops(struct entrypoint *ep);
extern void pack_basic_blocks(struct entrypoint *ep);
diff --git a/memops.c b/memops.c
index df2e4d6c..20806175 100644
--- a/memops.c
+++ b/memops.c
@@ -190,6 +190,7 @@ next_store:
void simplify_memops(struct entrypoint *ep)
{
struct basic_block *bb;
+ pseudo_t pseudo;
FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
simplify_loads(bb);
@@ -198,4 +199,15 @@ void simplify_memops(struct entrypoint *ep)
FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
kill_dominated_stores(bb);
} END_FOR_EACH_PTR_REVERSE(bb);
+
+ FOR_EACH_PTR(ep->accesses, pseudo) {
+ struct symbol *var = pseudo->sym;
+ unsigned long mod;
+ if (!var)
+ continue;
+ mod = var->ctype.modifiers;
+ if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
+ continue;
+ kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
+ } END_FOR_EACH_PTR(pseudo);
}
diff --git a/validation/optim/kill-stores0.c b/validation/optim/kill-stores0.c
new file mode 100644
index 00000000..00c005ff
--- /dev/null
+++ b/validation/optim/kill-stores0.c
@@ -0,0 +1,34 @@
+struct p {
+ int x, y;
+};
+
+struct q {
+ int w;
+};
+
+static int foo(void)
+{
+ int x = 1;
+ int y = x;
+ return &x == &y;
+}
+
+static int bar(struct p p)
+{
+ if (p.x != 0)
+ ;
+}
+
+static int baz(struct p p, struct q q)
+{
+ if (p.x != 0 || p.y != 1 || q.w == 0)
+ ;
+}
+
+/*
+ * check-name: kill-stores0
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-excludes: store\\.
+ */
diff --git a/validation/optim/kill-stores1.c b/validation/optim/kill-stores1.c
new file mode 100644
index 00000000..16a5dcf0
--- /dev/null
+++ b/validation/optim/kill-stores1.c
@@ -0,0 +1,48 @@
+struct s {
+ int c[1];
+};
+
+static struct s x, y;
+static int p;
+
+static void foo0(void)
+{
+ (x = y).c; // x = y;
+}
+
+static void foo1(void)
+{
+ int *t = (x = y).c; // x = y;
+}
+
+static void foo2(void)
+{
+ (x = y).c + 1; // x = y;
+}
+
+static void foo3(void)
+{
+ (x = y).c[0]; // x = y;
+}
+
+static void foo4(void)
+{
+ (p ? x : y).c[0]; // ;
+}
+
+static void foo5(void)
+{
+ (p, y).c[0]; // ;
+}
+
+/*
+ * check-name: kill-stores1
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-pattern(4): load\\.
+ * check-output-pattern(4): load\\..*0\\[y\\]
+ * check-output-pattern(4): store\\.
+ * check-output-pattern(4): store\\..*0\\[x\\]
+ * check-output-excludes: select\\.
+ */
diff --git a/validation/optim/kill-stores2.c b/validation/optim/kill-stores2.c
new file mode 100644
index 00000000..861b5ece
--- /dev/null
+++ b/validation/optim/kill-stores2.c
@@ -0,0 +1,17 @@
+extern void def(int *);
+
+static void foo(void)
+{
+ int c;
+ def(&c);
+ if (c)
+ c = c;
+}
+
+/*
+ * check-name: kill-stores2
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-excludes: store\\.
+ */
diff --git a/validation/optim/live-stores0.c b/validation/optim/live-stores0.c
new file mode 100644
index 00000000..2cbc5ab1
--- /dev/null
+++ b/validation/optim/live-stores0.c
@@ -0,0 +1,29 @@
+void init(int *x);
+
+static int foo(void)
+{
+ int a[2] = { 0, 123, };
+
+ if (a[1] != 123)
+ return 1;
+ init(a);
+ if (a[1] == 123)
+ return 2;
+ return 0;
+}
+
+#if 0
+void init(int *x)
+{
+ x[0] = x[1] = 0;
+}
+#endif
+
+/*
+ * check-name: live-stores
+ * check-command: test-linearize $file
+ *
+ * check-output-ignore
+ * check-output-contains: store.32 *\\$123
+ * check-output-pattern(2,3): store\\.
+ */
generated by cgit 1.2.3-korg (git 2.43.0) at 2025-11-03 07:53:38 +0000