aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
authorLuc Van Oostenryck <luc.vanoostenryck@looxix.net>2005-11-22 00:41:56 +0100
committerLinus Torvalds <torvalds@g5.osdl.org>2005-11-21 17:55:24 -0800
commit4c520e1ad243ed347dfc0e1f8c6e3dec19994f42 (patch)
tree7b2701aa6135f3ba95ecf98e55bb8497de3e245d
parentca682df2d73399c4d24d4400cc1a06c9dfc79477 (diff)
downloadsparse-dev-4c520e1ad243ed347dfc0e1f8c6e3dec19994f42.tar.gz
[PATCH] Add a function to translate the SSA form back to normal form.
For now, it use a simple method but which introduces a lot more copies than necessary. Can be fixed later. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@looxix.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat
-rw-r--r--.gitignore1
-rw-r--r--Makefile7
-rw-r--r--linearize.h1
-rw-r--r--test-unssa.c81
-rw-r--r--unssa.c116
5 files changed, 204 insertions, 2 deletions
diff --git a/.gitignore b/.gitignore
index 6c331ace..a7e55141 100644
--- a/.gitignore
+++ b/.gitignore
@@ -15,3 +15,4 @@ check
compile
test-linearize
example
+test-unssa
diff --git a/Makefile b/Makefile
index 714348aa..d7c2d093 100644
--- a/Makefile
+++ b/Makefile
@@ -21,7 +21,7 @@ CFLAGS += -DDEBUG
PREFIX=$(HOME)
BINDIR=$(PREFIX)/bin
-PROGRAMS=test-lexing test-parsing obfuscate check compile test-linearize example
+PROGRAMS=test-lexing test-parsing obfuscate check compile test-linearize example test-unssa
LIB_H= token.h parse.h lib.h symbol.h scope.h expression.h target.h \
linearize.h bitmap.h ident-list.h compat.h flow.h allocate.h \
@@ -30,7 +30,7 @@ LIB_H= token.h parse.h lib.h symbol.h scope.h expression.h target.h \
LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \
sort.o allocate.o compat-$(OS).o ptrlist.o \
- flow.o cse.o simplify.o memops.o liveness.o storage.o
+ flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o
LIB_FILE= libsparse.a
SLIB_FILE= libsparse.so
@@ -80,6 +80,9 @@ check: check.o $(LIBS)
example: example.o $(LIBS)
$(CC) $(LDFLAGS) -o $@ $< $(LIBS)
+test-unssa: test-unssa.o $(LIBS)
+ $(CC) $(LDFLAGS) -o $@ $< $(LIBS)
+
$(LIB_FILE): $(LIB_OBJS)
$(AR) rcs $@ $(LIB_OBJS)
diff --git a/linearize.h b/linearize.h
index 16264494..5f021a3b 100644
--- a/linearize.h
+++ b/linearize.h
@@ -306,6 +306,7 @@ pseudo_t alloc_pseudo(struct instruction *def);
pseudo_t value_pseudo(long long val);
struct entrypoint *linearize_symbol(struct symbol *sym);
+int unssa(struct entrypoint *ep);
void show_entry(struct entrypoint *ep);
const char *show_pseudo(pseudo_t pseudo);
void show_bb(struct basic_block *bb);
diff --git a/test-unssa.c b/test-unssa.c
new file mode 100644
index 00000000..15ff9d72
--- /dev/null
+++ b/test-unssa.c
@@ -0,0 +1,81 @@
+#include <stdio.h>
+#include <assert.h>
+
+#include "symbol.h"
+#include "expression.h"
+#include "linearize.h"
+#include "flow.h"
+
+
+static void output_bb(struct basic_block *bb, unsigned long generation)
+{
+ struct instruction *insn;
+
+ bb->generation = generation;
+ printf(".L%p\n", bb);
+
+ FOR_EACH_PTR(bb->insns, insn) {
+ if (!insn->bb)
+ continue;
+ printf("\t%s\n", show_instruction(insn));
+ }
+ END_FOR_EACH_PTR(insn);
+
+ printf("\n");
+}
+
+static void output_fn(struct entrypoint *ep)
+{
+ struct basic_block *bb;
+ unsigned long generation = ++bb_generation;
+ struct symbol *sym = ep->name;
+ const char *name = show_ident(sym->ident);
+
+ if (sym->ctype.modifiers & MOD_STATIC)
+ printf("\n\n%s:\n", name);
+ else
+ printf("\n\n.globl %s\n%s:\n", name, name);
+
+ unssa(ep);
+
+ FOR_EACH_PTR(ep->bbs, bb) {
+ if (bb->generation == generation)
+ continue;
+ output_bb(bb, generation);
+ }
+ END_FOR_EACH_PTR(bb);
+}
+
+static int output_data(struct symbol *sym)
+{
+ printf("symbol %s:\n", show_ident(sym->ident));
+ printf("\ttype = %d\n", sym->ctype.base_type->type);
+ printf("\tmodif= %lx\n", sym->ctype.modifiers);
+
+ return 0;
+}
+
+static int compile(struct symbol_list *list)
+{
+ struct symbol *sym;
+ FOR_EACH_PTR(list, sym) {
+ struct entrypoint *ep;
+ expand_symbol(sym);
+ ep = linearize_symbol(sym);
+ if (ep)
+ output_fn(ep);
+ else
+ output_data(sym);
+ }
+ END_FOR_EACH_PTR(sym);
+
+ return 0;
+}
+
+int main(int argc, char **argv)
+{
+ compile(sparse_initialize(argc, argv));
+ while (*argv)
+ compile(sparse(argv));
+ return 0;
+}
diff --git a/unssa.c b/unssa.c
new file mode 100644
index 00000000..b12cf4b4
--- /dev/null
+++ b/unssa.c
@@ -0,0 +1,116 @@
+/*
+ * UnSSA - translate the SSA back to normal form.
+ *
+ * For now it's done by replacing to set of copies:
+ * 1) For each phi-node, replace all their phisrc by copies to a common
+ * temporary.
+ * 2) Replace all the phi-nodes by copies of the temporaries to the phi-node target.
+ * This is node to preserve the semantic of the phi-node (they should all "execute"
+ * simultaneously on entry in the basic block in which they belong).
+ *
+ * This is similar to the "Sreedhar method I" except that the copies to the
+ * temporaries are not placed at the end of the predecessor basic blocks, but
+ * at the place where the phi-node operands are defined (the same place where the
+ * phisrc were present).
+ * Is this a problem?
+ *
+ * While very simple this method create a lot more copies that really necessary.
+ * Ideally, "Sreedhar method III" should be used:
+ * "Translating Out of Static Single Assignment Form", V. C. Sreedhar, R. D.-C. Ju,
+ * D. M. Gillies and V. Santhanam. SAS'99, Vol. 1694 of Lecture Notes in Computer
+ * Science, Springer-Verlag, pp. 194-210, 1999.
+ *
+ * Copyright (C) 2005 Luc Van Oostenryck
+ */
+
+#include "lib.h"
+#include "linearize.h"
+#include "allocate.h"
+#include <assert.h>
+
+static struct instruction *alloc_copy_insn(struct instruction *phisrc)
+{
+ struct instruction *insn = __alloc_instruction(0);
+ insn->opcode = OP_COPY;
+ insn->size = phisrc->size;
+ insn->pos = phisrc->pos;
+ return insn;
+}
+
+// Is there a better way to do this ???
+static void insert_insn_before(struct instruction *old, struct instruction *new)
+{
+ struct instruction *insn;
+
+ FOR_EACH_PTR_REVERSE(old->bb->insns, insn) {
+ if (insn == old)
+ INSERT_CURRENT(new, insn);
+ }
+ END_FOR_EACH_PTR_REVERSE(insn);
+}
+
+static void insert_copy(struct instruction *phisrc, pseudo_t tmp)
+{
+ struct instruction *cpy;
+
+ assert(phisrc->opcode == OP_PHISOURCE);
+
+ cpy = alloc_copy_insn(phisrc);
+ cpy->target = tmp;
+ cpy->src = phisrc->phi_src;
+ cpy->bb = phisrc->bb;
+ insert_insn_before(phisrc, cpy);
+}
+
+static void copy_phi_args(struct instruction *phi, struct pseudo_list **list)
+{
+ pseudo_t tmp, orig = phi->target;
+ pseudo_t phisrc;
+
+ tmp = alloc_pseudo(NULL);
+ tmp->type = orig->type;
+ tmp->def = phi; // wrongly set to the phi-node !!!
+ // but used later
+ add_pseudo(list, tmp);
+
+ FOR_EACH_PTR(phi->phi_list, phisrc) {
+ if (!phisrc->def)
+ continue;
+ insert_copy(phisrc->def, tmp);
+ } END_FOR_EACH_PTR(phisrc);
+}
+
+static void unssa_bb(struct basic_block *bb)
+{
+ struct pseudo_list *list = NULL;
+ struct pseudo *tmp;
+ struct instruction *insn;
+
+ // copy all the phi nodes arguments to a new temporary pseudo
+ FOR_EACH_PTR(bb->insns, insn) {
+ if (insn->opcode != OP_PHI)
+ continue;
+ copy_phi_args(insn, &list);
+ } END_FOR_EACH_PTR(insn);
+
+ // now replace all the phi nodes themselves by copies of the
+ // temporaries to the phi nodes targets
+ FOR_EACH_PTR(list, tmp) {
+ struct instruction *phi = tmp->def;
+
+ phi->opcode = OP_COPY;
+ phi->src = tmp;
+ } END_FOR_EACH_PTR(tmp);
+ free_ptr_list(&list);
+}
+
+int unssa(struct entrypoint *ep)
+{
+ struct basic_block *bb;
+
+ FOR_EACH_PTR(ep->bbs, bb) {
+ unssa_bb(bb);
+ } END_FOR_EACH_PTR(bb);
+
+ return 0;
+}
generated by cgit 1.2.3-korg (git 2.43.0) at 2025-11-03 08:01:33 +0000