[2/4] ssa: the sparse set is not needed

Commit Message

Luc Van Oostenryck March 9, 2021, 11:42 p.m. UTC

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 <[e-mail]>
---
 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

Patch

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