diff options
author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2021-03-06 23:34:21 +0100 |
---|---|---|
committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2021-03-09 22:17:01 +0100 |
commit | e528e0755d46344f07e44bfbb3f90477747925cf (patch) | |
tree | 1bc0e3f9913140523e0605fcb851d072ddd48f51 | |
parent | 0603c7e28e8063dd8e56a7f89b7222971b9d4f34 (diff) | |
download | sparse-e528e0755d46344f07e44bfbb3f90477747925cf.tar.gz |
ssa: the sparse set is not needed
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>
-rw-r--r-- | Makefile | 1 | ||||
-rw-r--r-- | ssa.c | 11 | ||||
-rw-r--r-- | sset.c | 28 | ||||
-rw-r--r-- | sset.h | 56 |
4 files changed, 4 insertions, 92 deletions
@@ -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 @@ -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 e9681e00..00000000 --- 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 69cee18a..00000000 --- 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 |