diff options
53 files changed, 1439 insertions, 376 deletions
diff --git a/Documentation/dev-options.rst b/Documentation/dev-options.rst index bf2d49a7..04fb651f 100644 --- a/Documentation/dev-options.rst +++ b/Documentation/dev-options.rst @@ -44,6 +44,14 @@ OPTIONS Add ``OP_DEATHNOTE`` annotations to dead pseudos. +.. option:: -vdomtree + + Dump the dominance tree after its calculation. + .. option:: -ventry Dump the IR after all optimization passes. + +.. option:: -vpostorder + + Dump the reverse postorder traversal of the CFG. @@ -37,10 +37,12 @@ LIB_OBJS += char.o LIB_OBJS += compat-$(OS).o LIB_OBJS += cse.o LIB_OBJS += dissect.o +LIB_OBJS += dominate.o LIB_OBJS += evaluate.o LIB_OBJS += expand.o LIB_OBJS += expression.o LIB_OBJS += flow.o +LIB_OBJS += flowgraph.o LIB_OBJS += inline.o LIB_OBJS += ir.o LIB_OBJS += lib.o @@ -52,10 +54,13 @@ LIB_OBJS += optimize.o LIB_OBJS += parse.o LIB_OBJS += pre-process.o LIB_OBJS += ptrlist.o +LIB_OBJS += ptrmap.o LIB_OBJS += scope.o 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 @@ -14,6 +14,7 @@ #include "parse.h" #include "expression.h" +#include "flowgraph.h" #include "linearize.h" #include "flow.h" #include "cse.h" @@ -276,28 +277,6 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct return def; } -/* - * Does "bb1" dominate "bb2"? - */ -static int bb_dominates(struct entrypoint *ep, struct basic_block *bb1, struct basic_block *bb2, unsigned long generation) -{ - struct basic_block *parent; - - /* Nothing dominates the entrypoint.. */ - if (bb2 == ep->entry->bb) - return 0; - FOR_EACH_PTR(bb2->parents, parent) { - if (parent == bb1) - continue; - if (parent->generation == generation) - continue; - parent->generation = generation; - if (!bb_dominates(ep, bb1, parent, generation)) - return 0; - } END_FOR_EACH_PTR(parent); - return 1; -} - static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2) { struct basic_block *parent; @@ -351,10 +330,10 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction warning(b1->pos, "Whaa? unable to find CSE instructions"); return i1; } - if (bb_dominates(ep, b1, b2, ++bb_generation)) + if (domtree_dominates(b1, b2)) return cse_one_instruction(i2, i1); - if (bb_dominates(ep, b2, b1, ++bb_generation)) + if (domtree_dominates(b2, b1)) return cse_one_instruction(i1, i2); /* No direct dominance - but we could try to find a common ancestor.. */ diff --git a/dominate.c b/dominate.c new file mode 100644 index 00000000..8085171d --- /dev/null +++ b/dominate.c @@ -0,0 +1,153 @@ +// SPDX-License-Identifier: MIT +// +// dominate.c - compute the (iterated) dominance frontier of (a set of) nodes. +// +// Copyright (C) 2017 - Luc Van Oostenryck +// +// The algorithm used is the one described in: +// "A Linear Time Algorithm for Placing phi-nodes" +// by Vugranam C. Sreedhar and Guang R. Gao +// + +#include "dominate.h" +#include "flowgraph.h" +#include "linearize.h" +#include "flow.h" +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> + + +struct piggy { + unsigned int max; + struct basic_block_list *lists[0]; +}; + +struct piggy *bank_init(unsigned levels) +{ + struct piggy *bank; + bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists[0])); + bank->max = levels - 1; + return bank; +} + +static void bank_free(struct piggy *bank, unsigned int levels) +{ + for (; levels-- ;) + free_ptr_list(&bank->lists[levels]); + free(bank); +} + +static void bank_put(struct piggy *bank, struct basic_block *bb) +{ + unsigned int level = bb->dom_level; + assert(level <= bank->max); + add_bb(&bank->lists[level], bb); +} + +static inline struct basic_block *pop_bb(struct basic_block_list **list) +{ + return delete_ptr_list_last((struct ptr_list **)list); +} + +static struct basic_block *bank_get(struct piggy *bank) +{ + int level = bank->max; + do { + struct basic_block *bb = pop_bb(&bank->lists[level]); + if (bb) + return bb; + if (!level) + return NULL; + bank->max = --level; + } while (1); +} + + +#define VISITED 0x1 +#define INPHI 0x2 +#define ALPHA 0x4 +#define FLAGS 0x7 + +static void visit(struct piggy *bank, struct basic_block_list **idf, struct basic_block *x, int curr_level) +{ + struct basic_block *y; + + x->generation |= 1; + FOR_EACH_PTR(x->children, y) { + unsigned flags = y->generation & FLAGS; + if (y->idom == x) // J-edges will be processed later + continue; + if (y->dom_level > curr_level) + continue; + if (flags & INPHI) + continue; + y->generation |= INPHI; + add_bb(idf, y); + if (flags & ALPHA) + continue; + bank_put(bank, y); + } END_FOR_EACH_PTR(y); + + FOR_EACH_PTR(x->doms, y) { + if (y->generation & VISITED) + continue; + visit(bank, idf, y, curr_level); + } END_FOR_EACH_PTR(y); +} + +void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha) +{ + int levels = ep->dom_levels; + struct piggy *bank = bank_init(levels); + struct basic_block *bb; + unsigned long generation = bb_generation; + + generation = bb_generation; + generation += -generation & FLAGS; + bb_generation = generation + (FLAGS + 1); + + // init all the nodes + FOR_EACH_PTR(ep->bbs, bb) { + // FIXME: this should be removed and the tests for + // visited/in_phi/alpha should use a sparse set + bb->generation = generation; + } END_FOR_EACH_PTR(bb); + + FOR_EACH_PTR(alpha, bb) { + bb->generation = generation | ALPHA; + bank_put(bank, bb); + } END_FOR_EACH_PTR(bb); + + while ((bb = bank_get(bank))) { + visit(bank, idf, bb, bb->dom_level); + } + + bank_free(bank, levels); +} + +void idf_dump(struct entrypoint *ep) +{ + struct basic_block *bb; + + domtree_build(ep); + + printf("%s's IDF:\n", show_ident(ep->name->ident)); + FOR_EACH_PTR(ep->bbs, bb) { + struct basic_block_list *alpha = NULL; + struct basic_block_list *idf = NULL; + struct basic_block *df; + + add_bb(&alpha, bb); + idf_compute(ep, &idf, alpha); + + printf("\t%s\t<-", show_label(bb)); + FOR_EACH_PTR(idf, df) { + printf(" %s", show_label(df)); + } END_FOR_EACH_PTR(df); + printf("\n"); + + free_ptr_list(&idf); + free_ptr_list(&alpha); + } END_FOR_EACH_PTR(bb); +} diff --git a/dominate.h b/dominate.h new file mode 100644 index 00000000..6ac515d0 --- /dev/null +++ b/dominate.h @@ -0,0 +1,9 @@ +#ifndef DOMINATE_H +#define DOMINATE_H + +struct entrypoint; +struct basic_block_list; + +void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha); + +#endif @@ -370,68 +370,6 @@ int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom return 1; } -static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb) -{ - pseudo_t p; - FOR_EACH_PTR(list, p) { - if (p->def->bb == bb) - return 1; - } END_FOR_EACH_PTR(p); - - return 0; -} - -static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn, - struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators, - int local) -{ - struct basic_block *parent; - - if (!bb->parents) - return !!local; - - FOR_EACH_PTR(bb->parents, parent) { - struct instruction *one; - struct instruction *br; - pseudo_t phi; - - FOR_EACH_PTR_REVERSE(parent->insns, one) { - int dominance; - if (!one->bb) - continue; - if (one == insn) - goto no_dominance; - dominance = dominates(pseudo, insn, one, local); - if (dominance < 0) { - if (one->opcode == OP_LOAD) - continue; - return 0; - } - if (!dominance) - continue; - goto found_dominator; - } END_FOR_EACH_PTR_REVERSE(one); -no_dominance: - if (parent->generation == generation) - continue; - parent->generation = generation; - - if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local)) - return 0; - continue; - -found_dominator: - if (dominators && phisrc_in_bb(*dominators, parent)) - continue; - br = delete_last_instruction(&parent->insns); - phi = alloc_phi(parent, one->target, one->type); - phi->ident = phi->ident ? : pseudo->ident; - add_instruction(&parent->insns, br); - use_pseudo(insn, phi, add_pseudo(dominators, phi)); - } END_FOR_EACH_PTR(parent); - return 1; -} - /* * We should probably sort the phi list just to make it easier to compare * later for equality. @@ -473,79 +411,6 @@ end: repeat_phase |= REPEAT_SYMBOL_CLEANUP; } -static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn, - unsigned long generation, int local) -{ - struct basic_block *bb = insn->bb; - struct instruction *one, *dom = NULL; - struct pseudo_list *dominators; - int partial; - - /* Unreachable load? Undo it */ - if (!bb) { - kill_use(&insn->src); - return 1; - } - - partial = 0; - FOR_EACH_PTR(bb->insns, one) { - int dominance; - if (!one->bb) - continue; - if (one == insn) - goto found; - dominance = dominates(pseudo, insn, one, local); - if (dominance < 0) { - /* Ignore partial load dominators */ - if (one->opcode == OP_LOAD) - continue; - dom = NULL; - partial = 1; - continue; - } - if (!dominance) - continue; - dom = one; - partial = 0; - } END_FOR_EACH_PTR(one); - /* Whaa? */ - warning(pseudo->sym->pos, "unable to find symbol read"); - return 0; -found: - if (partial) - return 0; - - if (dom) { - convert_load_instruction(insn, dom->target); - return 1; - } - - /* OK, go find the parents */ - bb->generation = generation; - - dominators = NULL; - if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) - return 0; - - /* This happens with initial assignments to structures etc.. */ - if (!dominators) { - if (!local) - return 0; - check_access(insn); - convert_load_instruction(insn, value_pseudo(0)); - return 1; - } - - /* - * If we find just one dominating instruction, we - * can turn it into a direct thing. Otherwise we'll - * have to turn the load into a phi-node of the - * dominators. - */ - rewrite_load_instruction(insn, dominators); - return 1; -} - /* Kill a pseudo that is dead on exit from the bb */ // The context is: // * the variable is not global but may have its address used (local/non-local) @@ -600,59 +465,6 @@ static void kill_dead_stores_bb(pseudo_t pseudo, unsigned long generation, struc } END_FOR_EACH_PTR(parent); } -/* - * This should see if the "insn" trivially dominates some previous store, and kill the - * store if unnecessary. - */ -static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn, - unsigned long generation, struct basic_block *bb, int local, int found) -{ - struct instruction *one; - struct basic_block *parent; - - /* Unreachable store? Undo it */ - if (!bb) { - kill_instruction_force(insn); - return; - } - if (bb->generation == generation) - return; - bb->generation = generation; - FOR_EACH_PTR_REVERSE(bb->insns, one) { - int dominance; - if (!one->bb) - continue; - if (!found) { - if (one != insn) - continue; - found = 1; - continue; - } - dominance = dominates(pseudo, insn, one, local); - if (!dominance) - continue; - if (dominance < 0) - return; - if (one->opcode == OP_LOAD) - return; - kill_instruction_force(one); - } END_FOR_EACH_PTR_REVERSE(one); - - if (!found) { - warning(bb->pos, "Unable to find instruction"); - return; - } - - 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_dominated_stores(pseudo, insn, generation, parent, local, found); - } END_FOR_EACH_PTR(parent); -} - void check_access(struct instruction *insn) { pseudo_t pseudo = insn->src; @@ -673,96 +485,6 @@ void check_access(struct instruction *insn) } } -static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) -{ - pseudo_t pseudo; - struct pseudo_user *pu; - unsigned long mod; - int all; - - /* Never used as a symbol? */ - pseudo = sym->pseudo; - if (!pseudo) - return; - - /* We don't do coverage analysis of volatiles.. */ - if (sym->ctype.modifiers & MOD_VOLATILE) - return; - - /* ..and symbols with external visibility need more care */ - mod = sym->ctype.modifiers & (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE); - if (mod) - goto external_visibility; - - FOR_EACH_PTR(pseudo->users, pu) { - /* We know that the symbol-pseudo use is the "src" in the instruction */ - struct instruction *insn = pu->insn; - - switch (insn->opcode) { - case OP_STORE: - break; - case OP_LOAD: - break; - case OP_SYMADDR: - if (!insn->bb) - continue; - mod |= MOD_ADDRESSABLE; - goto external_visibility; - case OP_NOP: - case OP_PHI: - continue; - default: - warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident)); - } - } END_FOR_EACH_PTR(pu); - -external_visibility: - all = 1; - FOR_EACH_PTR_REVERSE(pseudo->users, pu) { - struct instruction *insn = pu->insn; - if (insn->opcode == OP_LOAD) - all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod); - } END_FOR_EACH_PTR_REVERSE(pu); - - /* If we converted all the loads, remove the stores. They are dead */ - if (all && !mod) { - FOR_EACH_PTR(pseudo->users, pu) { - struct instruction *insn = pu->insn; - if (insn->opcode == OP_STORE) - kill_instruction_force(insn); - } END_FOR_EACH_PTR(pu); - } else { - /* - * If we couldn't take the shortcut, see if we can at least kill some - * of them.. - */ - FOR_EACH_PTR(pseudo->users, pu) { - struct instruction *insn = pu->insn; - if (insn->opcode == OP_STORE) - kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0); - } END_FOR_EACH_PTR(pu); - - if (!(mod & (MOD_NONLOCAL | MOD_STATIC))) { - struct basic_block *bb; - FOR_EACH_PTR(ep->bbs, bb) { - if (!bb->children) - kill_dead_stores_bb(pseudo, ++bb_generation, bb, !mod); - } END_FOR_EACH_PTR(bb); - } - } - - return; -} - -void simplify_symbol_usage(struct entrypoint *ep) -{ - pseudo_t pseudo; - - FOR_EACH_PTR(ep->accesses, pseudo) { - simplify_one_symbol(ep, pseudo->sym); - } END_FOR_EACH_PTR(pseudo); -} - static struct pseudo_user *first_user(pseudo_t p) { struct pseudo_user *pu; diff --git a/flowgraph.c b/flowgraph.c new file mode 100644 index 00000000..8fc22dcf --- /dev/null +++ b/flowgraph.c @@ -0,0 +1,219 @@ +// SPDX-License-Identifier: MIT +// +// Various utilities for flowgraphs. +// +// Copyright (c) 2017 Luc Van Oostenryck. +// + +#include "flowgraph.h" +#include "linearize.h" +#include "flow.h" // for bb_generation +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> + + +struct cfg_info { + struct basic_block_list *list; + unsigned long gen; + unsigned int nr; +}; + + +static void label_postorder(struct basic_block *bb, struct cfg_info *info) +{ + struct basic_block *child; + + if (bb->generation == info->gen) + return; + + bb->generation = info->gen; + FOR_EACH_PTR_REVERSE(bb->children, child) { + label_postorder(child, info); + } END_FOR_EACH_PTR_REVERSE(child); + + bb->postorder_nr = info->nr++; + add_bb(&info->list, bb); +} + +static void reverse_bbs(struct basic_block_list **dst, struct basic_block_list *src) +{ + struct basic_block *bb; + FOR_EACH_PTR_REVERSE(src, bb) { + add_bb(dst, bb); + } END_FOR_EACH_PTR_REVERSE(bb); +} + +static void debug_postorder(struct entrypoint *ep) +{ + struct basic_block *bb; + + printf("%s's reverse postorder:\n", show_ident(ep->name->ident)); + FOR_EACH_PTR(ep->bbs, bb) { + printf("\t.L%u: %u\n", bb->nr, bb->postorder_nr); + } END_FOR_EACH_PTR(bb); +} + +// +// cfg_postorder - Set the BB's reverse postorder links +// +// Do a postorder DFS walk and set the links +// (which will do the reverse part). +// +int cfg_postorder(struct entrypoint *ep) +{ + struct cfg_info info = { + .gen = ++bb_generation, + }; + + label_postorder(ep->entry->bb, &info); + + // OK, now info.list contains the node in postorder + // Reuse ep->bbs for the reverse postorder. + free_ptr_list(&ep->bbs); + ep->bbs = NULL; + reverse_bbs(&ep->bbs, info.list); + free_ptr_list(&info.list); + if (dbg_postorder) + debug_postorder(ep); + return info.nr; +} + +// +// Calculate the dominance tree following: +// "A simple, fast dominance algorithm" +// by K. D. Cooper, T. J. Harvey, and K. Kennedy. +// cfr. http://www.cs.rice.edu/∼keith/EMBED/dom.pdf +// +static struct basic_block *intersect_dom(struct basic_block *doms[], + struct basic_block *b1, struct basic_block *b2) +{ + int f1 = b1->postorder_nr, f2 = b2->postorder_nr; + while (f1 != f2) { + while (f1 < f2) { + b1 = doms[f1]; + f1 = b1->postorder_nr; + } + while (f2 < f1) { + b2 = doms[f2]; + f2 = b2->postorder_nr; + } + } + return b1; +} + +static void debug_domtree(struct entrypoint *ep) +{ + struct basic_block *bb = ep->entry->bb; + + printf("%s's idoms:\n", show_ident(ep->name->ident)); + FOR_EACH_PTR(ep->bbs, bb) { + if (bb == ep->entry->bb) + continue; // entry node has no idom + printf("\t%s <- %s\n", show_label(bb), show_label(bb->idom)); + } END_FOR_EACH_PTR(bb); +} + +void domtree_build(struct entrypoint *ep) +{ + struct basic_block *entry = ep->entry->bb; + struct basic_block **doms; + struct basic_block *bb; + unsigned int size; + int max_level = 0; + int changed; + + // First calculate the (reverse) postorder. + // This will give use us: + // - the links to do a reverse postorder traversal + // - the order number for each block + size = cfg_postorder(ep); + + // initialize the dominators array + doms = calloc(size, sizeof(*doms)); + assert(entry->postorder_nr == size-1); + doms[size-1] = entry; + + do { + struct basic_block *b; + + changed = 0; + FOR_EACH_PTR(ep->bbs, b) { + struct basic_block *p; + int bnr = b->postorder_nr; + struct basic_block *new_idom = NULL; + + if (b == entry) + continue; // ignore entry node + + FOR_EACH_PTR(b->parents, p) { + unsigned int pnr = p->postorder_nr; + if (!doms[pnr]) + continue; + if (!new_idom) { + new_idom = p; + continue; + } + + new_idom = intersect_dom(doms, p, new_idom); + } END_FOR_EACH_PTR(p); + + assert(new_idom); + if (doms[bnr] != new_idom) { + doms[bnr] = new_idom; + changed = 1; + } + } END_FOR_EACH_PTR(b); + } while (changed); + + // set the idom links + FOR_EACH_PTR(ep->bbs, bb) { + struct basic_block *idom = doms[bb->postorder_nr]; + + if (bb == entry) + continue; // ignore entry node + + bb->idom = idom; + add_bb(&idom->doms, bb); + } END_FOR_EACH_PTR(bb); + entry->idom = NULL; + + // set the dominance levels + FOR_EACH_PTR(ep->bbs, bb) { + struct basic_block *idom = bb->idom; + int level = idom ? idom->dom_level + 1 : 0; + + bb->dom_level = level; + if (max_level < level) + max_level = level; + } END_FOR_EACH_PTR(bb); + ep->dom_levels = max_level + 1; + + free(doms); + if (dbg_domtree) + debug_domtree(ep); +} + +// dt_dominates - does BB a dominates BB b? +bool domtree_dominates(struct basic_block *a, struct basic_block *b) +{ + if (a == b) // dominance is reflexive + return true; + if (a == b->idom) + return true; + if (b == a->idom) + return false; + + // can't dominate if deeper in the DT + if (a->dom_level >= b->dom_level) + return false; + + // FIXME: can be faster if we have the DFS in-out numbers + + // walk up the dominator tree + for (b = b->idom; b; b = b->idom) { + if (b == a) + return true; + } + return false; +} diff --git a/flowgraph.h b/flowgraph.h new file mode 100644 index 00000000..7226c55f --- /dev/null +++ b/flowgraph.h @@ -0,0 +1,13 @@ +#ifndef FLOWGRAPH_H +#define FLOWGRAPH_H + +#include <stdbool.h> + +struct entrypoint; +struct basic_block; + +int cfg_postorder(struct entrypoint *ep); +void domtree_build(struct entrypoint *ep); +bool domtree_dominates(struct basic_block *a, struct basic_block *b); + +#endif @@ -289,8 +289,10 @@ int dump_macro_defs = 0; int dbg_compound = 0; int dbg_dead = 0; +int dbg_domtree = 0; int dbg_entry = 0; int dbg_ir = 0; +int dbg_postorder = 0; unsigned long fdump_ir; int fmem_report = 0; @@ -770,8 +772,10 @@ static char **handle_switch_W(char *arg, char **next) static struct flag debugs[] = { { "compound", &dbg_compound}, { "dead", &dbg_dead}, + { "domtree", &dbg_domtree}, { "entry", &dbg_entry}, { "ir", &dbg_ir}, + { "postorder", &dbg_postorder}, }; @@ -179,8 +179,10 @@ extern int dump_macro_defs; extern int dbg_compound; extern int dbg_dead; +extern int dbg_domtree; extern int dbg_entry; extern int dbg_ir; +extern int dbg_postorder; extern unsigned int fmax_warnings; extern int fmem_report; diff --git a/linearize.c b/linearize.c index 2e9a5638..a56c272f 100644 --- a/linearize.c +++ b/linearize.c @@ -172,6 +172,8 @@ const char *show_pseudo(pseudo_t pseudo) if (pseudo->ident) sprintf(buf+i, "(%s)", show_ident(pseudo->ident)); break; + case PSEUDO_UNDEF: + return "UNDEF"; default: snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type); } @@ -829,6 +831,13 @@ pseudo_t value_pseudo(long long val) return pseudo; } +pseudo_t undef_pseudo(void) +{ + pseudo_t pseudo = __alloc_pseudo(0); + pseudo->type = PSEUDO_UNDEF; + return pseudo; +} + static pseudo_t argument_pseudo(struct entrypoint *ep, int nr) { pseudo_t pseudo = __alloc_pseudo(0); @@ -871,6 +880,42 @@ pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *t return insn->target; } +struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident) +{ + struct instruction *phi_node = alloc_typed_instruction(OP_PHI, type); + pseudo_t phi; + + phi = alloc_pseudo(phi_node); + phi->ident = ident; + phi->def = phi_node; + phi_node->target = phi; + phi_node->bb = bb; + return phi_node; +} + +void add_phi_node(struct basic_block *bb, struct instruction *phi_node) +{ + struct instruction *insn; + + FOR_EACH_PTR(bb->insns, insn) { + enum opcode op = insn->opcode; + if (op == OP_PHI) + continue; + INSERT_CURRENT(phi_node, insn); + return; + } END_FOR_EACH_PTR(insn); + + // FIXME + add_instruction(&bb->insns, phi_node); +} + +struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var) +{ + struct instruction *phi_node = alloc_phi_node(bb, var, var->ident); + add_phi_node(bb, phi_node); + return phi_node; +} + /* * We carry the "access_data" structure around for any accesses, * which simplifies things a lot. It contains all the access diff --git a/linearize.h b/linearize.h index 1184df98..413bf013 100644 --- a/linearize.h +++ b/linearize.h @@ -7,6 +7,7 @@ #include "opcode.h" #include "parse.h" #include "symbol.h" +#include "ptrmap.h" struct instruction; @@ -17,10 +18,12 @@ struct pseudo_user { DECLARE_ALLOCATOR(pseudo_user); DECLARE_PTR_LIST(pseudo_user_list, struct pseudo_user); +DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t); enum pseudo_type { PSEUDO_VOID, + PSEUDO_UNDEF, PSEUDO_REG, PSEUDO_SYM, PSEUDO_VAL, @@ -99,7 +102,9 @@ struct instruction { struct multijmp_list *multijmp_list; }; struct /* phi_node */ { + pseudo_t phi_var; // used for SSA conversion struct pseudo_list *phi_list; + unsigned int used:1; }; struct /* phi source */ { pseudo_t phi_src; @@ -265,11 +270,18 @@ struct instruction_list; struct basic_block { struct position pos; unsigned long generation; - int context; + union { + int context; + int postorder_nr; /* postorder number */ + int dom_level; /* level in the dominance tree */ + }; struct entrypoint *ep; struct basic_block_list *parents; /* sources */ struct basic_block_list *children; /* destinations */ struct instruction_list *insns; /* Linear list of instructions */ + struct basic_block *idom; /* link to the immediate dominator */ + struct basic_block_list *doms; /* list of BB idominated by this one */ + struct phi_map *phi_map; struct pseudo_list *needs, *defines; union { unsigned int nr; /* unique id for label's names */ @@ -330,7 +342,7 @@ static inline void add_pseudo_user_ptr(struct pseudo_user *user, struct pseudo_u static inline int has_use_list(pseudo_t p) { - return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_VAL); + return (p && p->type != PSEUDO_VOID && p->type != PSEUDO_UNDEF && p->type != PSEUDO_VAL); } static inline int pseudo_user_list_size(struct pseudo_user_list *list) @@ -391,16 +403,21 @@ struct entrypoint { struct basic_block_list *bbs; struct basic_block *active; struct instruction *entry; + unsigned int dom_levels; /* max levels in the dom tree */ }; extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false); extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target); struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type); +struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident); +struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var); +void add_phi_node(struct basic_block *bb, struct instruction *phi_node); pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type); pseudo_t alloc_pseudo(struct instruction *def); pseudo_t value_pseudo(long long val); +pseudo_t undef_pseudo(void); struct entrypoint *linearize_symbol(struct symbol *sym); int unssa(struct entrypoint *ep); @@ -7,11 +7,13 @@ #include <assert.h> #include "optimize.h" +#include "flowgraph.h" #include "linearize.h" #include "liveness.h" #include "flow.h" #include "cse.h" #include "ir.h" +#include "ssa.h" int repeat_phase; @@ -53,11 +55,13 @@ void optimize(struct entrypoint *ep) kill_unreachable_bbs(ep); ir_validate(ep); + domtree_build(ep); + /* * Turn symbols into pseudos */ if (fpasses & PASS_MEM2REG) - simplify_symbol_usage(ep); + ssa_convert(ep); ir_validate(ep); if (fdump_ir & PASS_MEM2REG) show_entry(ep); diff --git a/ptrmap.c b/ptrmap.c new file mode 100644 index 00000000..ff07e19a --- /dev/null +++ b/ptrmap.c @@ -0,0 +1,109 @@ +// SPDX-License-Identifier: MIT +/* + * Stupid implementation of pointer -> pointer map. + * + * Copyright (c) 2017 Luc Van Oostenryck. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include "ptrmap.h" +#include "allocate.h" +#include <stddef.h> + +#define MAP_NR 7 + +struct ptrpair { + void *key; + void *val; +}; +struct ptrmap { + struct ptrmap *next; + int nr; + struct ptrpair pairs[MAP_NR]; +}; + +DECLARE_ALLOCATOR(ptrmap); +ALLOCATOR(ptrmap, "ptrmap"); + +void __ptrmap_add(struct ptrmap **mapp, void *key, void *val) +{ + struct ptrmap *head = *mapp; + struct ptrmap *newmap; + struct ptrmap *map; + struct ptrpair *pair; + int nr; + + if ((map = head)) { + struct ptrmap *next = map->next; + if (next) // head is full + map = next; + if ((nr = map->nr) < MAP_NR) + goto oldmap; + } + + // need a new block + newmap = __alloc_ptrmap(0); + if (!head) { + *mapp = newmap; + } else { + newmap->next = head->next; + head->next = newmap; + } + map = newmap; + nr = 0; + +oldmap: + pair = &map->pairs[nr]; + pair->key = key; + pair->val = val; + map->nr = ++nr; +} + +void *__ptrmap_lookup(struct ptrmap *map, void *key) +{ + for (; map; map = map->next) { + int i, n = map->nr; + for (i = 0; i < n; i++) { + struct ptrpair *pair = &map->pairs[i]; + if (pair->key == key) + return pair->val; + } + } + return NULL; +} + +void __ptrmap_update(struct ptrmap **mapp, void *key, void *val) +{ + struct ptrmap *map = *mapp; + + for (; map; map = map->next) { + int i, n = map->nr; + for (i = 0; i < n; i++) { + struct ptrpair *pair = &map->pairs[i]; + if (pair->key == key) { + if (pair->val != val) + pair->val = val; + return; + } + } + } + + __ptrmap_add(mapp, key, val); +} diff --git a/ptrmap.h b/ptrmap.h new file mode 100644 index 00000000..cbbb61da --- /dev/null +++ b/ptrmap.h @@ -0,0 +1,28 @@ +#ifndef PTRMAP_H +#define PTRMAP_H + +struct ptrmap; + +#define DECLARE_PTRMAP(name, ktype, vtype) \ + struct name ## _pair { ktype key; vtype val; }; \ + struct name { struct name ## _pair block[1]; }; \ + static inline \ + void name##_add(struct name **map, ktype k, vtype v) { \ + __ptrmap_add((struct ptrmap**)map, k, v); \ + } \ + static inline \ + void name##_update(struct name **map, ktype k, vtype v) { \ + __ptrmap_update((struct ptrmap**)map, k, v); \ + } \ + static inline \ + vtype name##_lookup(struct name *map, ktype k) { \ + vtype val = __ptrmap_lookup((struct ptrmap*)map, k); \ + return val; \ + } \ + +/* ptrmap.c */ +void __ptrmap_add(struct ptrmap **mapp, void *key, void *val); +void __ptrmap_update(struct ptrmap **mapp, void *key, void *val); +void *__ptrmap_lookup(struct ptrmap *map, void *key); + +#endif diff --git a/sparse-llvm.c b/sparse-llvm.c index 58811309..c7a9fbb7 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -270,6 +270,9 @@ static const char *pseudo_name(pseudo_t pseudo, char *buf) case PSEUDO_VOID: buf[0] = '\0'; break; + case PSEUDO_UNDEF: + assert(0); + break; default: assert(0); } @@ -387,6 +390,9 @@ static LLVMValueRef pseudo_to_value(struct function *fn, struct symbol *ctype, p case PSEUDO_VOID: result = NULL; break; + case PSEUDO_UNDEF: + result = LLVMGetUndef(symbol_type(ctype)); + break; default: assert(0); } @@ -0,0 +1,401 @@ +// SPDX-License-Identifier: MIT +// +// SSA conversion +// Copyright (C) 2005 Luc Van Oostenryck +// + +#include <assert.h> +#include "lib.h" +#include "sset.h" +#include "dominate.h" +#include "flowgraph.h" +#include "linearize.h" +#include "flow.h" // for convert_load_instruction() + + +// Is it possible and desirable for this to be promoted to a pseudo? +static inline bool is_promotable(struct symbol *type) +{ + struct symbol *member; + int bf_seen; + int nbr; + + if (type->type == SYM_NODE) + type = type->ctype.base_type; + switch (type->type) { + case SYM_ENUM: + case SYM_BITFIELD: + case SYM_PTR: + case SYM_RESTRICT: // OK, always integer types + return 1; + case SYM_STRUCT: + if (type->bit_size > long_ctype.bit_size) + return 0; + // we allow a single scalar field + // but a run of bitfields count for 1 + nbr = 0; + bf_seen = 0; + FOR_EACH_PTR(type->symbol_list, member) { + if (is_bitfield_type(member)) { + if (bf_seen) + continue; + bf_seen = 1; + } else { + bf_seen = 0; + } + if (!is_scalar_type(member)) + return 0; + if (nbr++) + return 0; + } END_FOR_EACH_PTR(member); + return 1; + case SYM_UNION: + // FIXME: should be like struct but has problem + // when used with/for type cohercion + // -----> OK if only same sized integral types + FOR_EACH_PTR(type->symbol_list, member) { + if (member->bit_size != type->bit_size) + return 0; + if (!is_integral_type(member)) + return 0; + } END_FOR_EACH_PTR(member); + return 1; + default: + break; + } + if (type->ctype.base_type == &int_type) + return 1; + if (type->ctype.base_type == &fp_type) + return 1; + return 0; +} + +static bool insn_before(struct instruction *a, struct instruction *b) +{ + struct basic_block *bb = a->bb; + struct instruction *insn; + + assert(b->bb == bb); + FOR_EACH_PTR(bb->insns, insn) { + if (insn == a) + return true; + if (insn == b) + return false; + } END_FOR_EACH_PTR(insn); + assert(0); +} + +static void kill_store(struct instruction *insn) +{ + remove_use(&insn->src); + remove_use(&insn->target); + insn->bb = NULL; +} + +static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses) +{ + struct instruction *insn; + pseudo_t val = NULL; + + if (!bb) + return; + + FOR_EACH_PTR(bb->insns, insn) { + + if (!insn->bb || insn->src != addr) + continue; + switch (insn->opcode) { + case OP_LOAD: + if (!val) + val = undef_pseudo(); + convert_load_instruction(insn, val); + break; + case OP_STORE: + val = insn->target; + // can't use kill_instruction() unless + // we add a fake user to val + kill_store(insn); + break; + } + } END_FOR_EACH_PTR(insn); +} + +static bool rewrite_single_store(struct instruction *store) +{ + pseudo_t addr = store->src; + struct pseudo_user *pu; + + FOR_EACH_PTR(addr->users, pu) { + struct instruction *insn = pu->insn; + + if (insn->opcode != OP_LOAD) + continue; + + // Let's try to replace the value of the load + // by the value from the store. This is only valid + // if the store dominate the load. + + 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. + if (!insn_before(store, insn)) + continue; + } else if (!domtree_dominates(store->bb, insn->bb)) { + // we can't convert this load + continue; + } + + // OK, we can rewrite this load + + // undefs ? + + convert_load_instruction(insn, store->target); + } END_FOR_EACH_PTR(pu); + + // is there some unconverted loads? + if (pseudo_user_list_size(addr->users) > 1) + return false; + + kill_store(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) +{ + struct basic_block_list *alpha = NULL; + struct basic_block_list *idf = NULL; + struct basic_block *samebb = NULL; + struct instruction *store = NULL; + struct basic_block *bb; + struct pseudo_user *pu; + unsigned long mod = var->ctype.modifiers; + bool local = true; + int nbr_stores = 0; + int nbr_uses = 0; + pseudo_t addr; + + /* Never used as a symbol? */ + addr = var->pseudo; + if (!addr) + return; + + /* We don't do coverage analysis of volatiles.. */ + if (mod & MOD_VOLATILE) + return; + + /* ..and symbols with external visibility need more care */ + mod &= (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE); + if (mod) + goto external_visibility; + + if (!is_promotable(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; + + switch (insn->opcode) { + case OP_STORE: + nbr_stores++; + store = insn; + if (!sset_testset(processed, bb->nr)) + add_bb(&alpha, bb); + /* fall through */ + case OP_LOAD: + if (local) { + if (!samebb) + samebb = bb; + else if (samebb != bb) + local = false; + } + nbr_uses++; + break; + case OP_SYMADDR: + mod |= MOD_ADDRESSABLE; + goto external_visibility; + default: + warning(var->pos, "symbol '%s' pseudo used in unexpected way", + show_ident(var->ident)); + } + } END_FOR_EACH_PTR(pu); + + if (nbr_stores == 1) { + if (rewrite_single_store(store)) + return; + } + + // if all uses are local to a single block + // they can easily be rewritten and doesn't need phi-nodes + // FIXME: could be done for extended BB too + if (local) { + rewrite_local_var(samebb, addr, nbr_stores, nbr_uses); + return; + } + + idf_compute(ep, &idf, alpha); + FOR_EACH_PTR(idf, bb) { + struct instruction *node = insert_phi_node(bb, var); + node->phi_var = var->pseudo; + } END_FOR_EACH_PTR(bb); + var->torename = 1; + +external_visibility: + if (mod & (MOD_NONLOCAL | MOD_STATIC)) + return; + kill_dead_stores(ep, addr, !mod); +} + +static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var) +{ + do { + pseudo_t val = phi_map_lookup(bb->phi_map, var); + if (val) + return val; + } while ((bb = bb->idom)); + return undef_pseudo(); +} + +static struct instruction_list *phis_all; +static struct instruction_list *phis_used; + +static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn) +{ + struct symbol *var; + pseudo_t addr; + pseudo_t val; + + switch (insn->opcode) { + case OP_STORE: + addr = insn->src; + if (addr->type != PSEUDO_SYM) + break; + var = addr->sym; + if (!var || !var->torename) + break; + phi_map_update(&bb->phi_map, var, insn->target); + kill_store(insn); + break; + case OP_LOAD: + addr = insn->src; + if (addr->type != PSEUDO_SYM) + break; + var = addr->sym; + if (!var || !var->torename) + break; + val = lookup_var(bb, var); + convert_load_instruction(insn, val); + break; + case OP_PHI: + var = insn->type; + if (!var || !var->torename) + break; + phi_map_update(&bb->phi_map, var, insn->target); + add_instruction(&phis_all, insn); + break; + } +} + +static void ssa_rename_insns(struct entrypoint *ep) +{ + struct basic_block *bb; + + FOR_EACH_PTR(ep->bbs, bb) { + struct instruction *insn; + FOR_EACH_PTR(bb->insns, insn) { + if (!insn->bb) + continue; + ssa_rename_insn(bb, insn); + } END_FOR_EACH_PTR(insn); + } END_FOR_EACH_PTR(bb); +} + +static void mark_phi_used(pseudo_t val) +{ + struct instruction *node; + + if (val->type != PSEUDO_REG) + return; + node = val->def; + if (node->opcode != OP_PHI) + return; + if (node->used) + return; + node->used = 1; + add_instruction(&phis_used, node); +} + +static void ssa_rename_phi(struct instruction *insn) +{ + struct basic_block *par; + struct symbol *var; + + if (!insn->phi_var) + return; + var = insn->phi_var->sym; + if (!var->torename) + return; + FOR_EACH_PTR(insn->bb->parents, par) { + struct instruction *term = delete_last_instruction(&par->insns); + pseudo_t val = lookup_var(par, var); + pseudo_t phi = alloc_phi(par, val, var); + phi->ident = var->ident; + add_instruction(&par->insns, term); + use_pseudo(insn, phi, add_pseudo(&insn->phi_list, phi)); + mark_phi_used(val); + } END_FOR_EACH_PTR(par); +} + +static void ssa_rename_phis(struct entrypoint *ep) +{ + struct instruction *phi; + + phis_used = NULL; + FOR_EACH_PTR(phis_all, phi) { + if (has_users(phi->target)) { + phi->used = 1; + add_instruction(&phis_used, phi); + } + } END_FOR_EACH_PTR(phi); + + FOR_EACH_PTR(phis_used, phi) { + if (!phi->bb) + continue; + ssa_rename_phi(phi); + } END_FOR_EACH_PTR(phi); +} + +void ssa_convert(struct entrypoint *ep) +{ + struct basic_block *bb; + pseudo_t pseudo; + int first, last; + + // calculate the number of BBs + first = ep->entry->bb->nr; + last = first; + FOR_EACH_PTR(ep->bbs, bb) { + int nr = bb->nr; + if (nr > last) + last = nr; + } 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); + } END_FOR_EACH_PTR(pseudo); + + // rename the converted accesses + phis_all = phis_used = NULL; + ssa_rename_insns(ep); + ssa_rename_phis(ep); +} @@ -0,0 +1,6 @@ +#ifndef SSA_H +#define SSA_H + +void ssa_convert(struct entrypoint *ep); + +#endif @@ -0,0 +1,28 @@ +// 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); +} @@ -0,0 +1,56 @@ +// 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 @@ -175,6 +175,7 @@ struct symbol { forced_arg:1, accessed:1, builtin:1, + torename:1, transparent_union:1; struct expression *array_size; struct ctype ctype; @@ -432,6 +433,24 @@ static inline int is_scalar_type(struct symbol *type) return 0; } +/// return true for integer & pointer types +static inline bool is_integral_type(struct symbol *type) +{ + if (type->type == SYM_NODE) + type = type->ctype.base_type; + switch (type->type) { + case SYM_ENUM: + case SYM_PTR: + case SYM_RESTRICT: // OK, always integer types + return 1; + default: + break; + } + if (type->ctype.base_type == &int_type) + return 1; + return 0; +} + static inline int is_function(struct symbol *type) { return type && type->type == SYM_FN; diff --git a/validation/crash-select.c b/validation/crash-select.c new file mode 100644 index 00000000..cec00baf --- /dev/null +++ b/validation/crash-select.c @@ -0,0 +1,18 @@ +struct s { + void *b; + long c; +}; + +long d(void); +static long f(void) +{ + struct s s; + s.c = d(); + if (s.c) + s.c = 2; + return s.c; +} + +/* + * check-name: crash-select + */ diff --git a/validation/compound-literal00.c b/validation/linear/compound-literal00.c index f3069d2c..f3069d2c 100644 --- a/validation/compound-literal00.c +++ b/validation/linear/compound-literal00.c diff --git a/validation/linear/compound-literal01.c b/validation/linear/compound-literal01.c new file mode 100644 index 00000000..e45fade3 --- /dev/null +++ b/validation/linear/compound-literal01.c @@ -0,0 +1,18 @@ +struct bfs { + int a: 2; + int b: 30; +}; + +int foo(void) +{ + struct bfs bf = { .a = 1, .b = 2 }; + return (struct bfs[]){bf}[0].b; +} + +/* + * check-name: compound-literal01.c + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-contains: ret\\..*\\$2 + */ diff --git a/validation/compound-literal01.c b/validation/linear/compound-literal02.c index 8a4935ea..87b98d76 100644 --- a/validation/compound-literal01.c +++ b/validation/linear/compound-literal02.c @@ -3,12 +3,6 @@ struct bfs { int b: 30; }; -int foo(void) -{ - struct bfs bf = { .a = 1, .b = 2 }; - return (struct bfs[]){bf}[0].b; -} - int bar(void) { struct bfs bf = { .a = 1, .b = 4 }; @@ -16,12 +10,10 @@ int bar(void) } /* - * check-name: compound-literal01.c + * check-name: compound-literal02.c * check-command: test-linearize -Wno-decl $file * * check-known-to-fail * check-output-ignore - * check-output-contains: ret\\..*\\$2 * check-output-contains: ret\\..*\\$6 - * check-error-end */ diff --git a/validation/linear/logical.c b/validation/linear/logical.c index 148ad427..0f502c6b 100644 --- a/validation/linear/logical.c +++ b/validation/linear/logical.c @@ -56,7 +56,7 @@ ou: <entry-point> store.32 %arg1 -> 0[i] store.64 %arg2 -> 0[b] - phisrc.32 %phi5 <- $1 + phisrc.32 %phi4 <- $1 load.32 %r11 <- 0[i] setne.1 %r12 <- %r11, $0 cbr %r12, .L7, .L6 @@ -68,16 +68,16 @@ ou: trunc.3 %r16 <- (32) %r15 setne.1 %r17 <- %r16, $0 zext.32 %r18 <- (1) %r17 - phisrc.32 %phi6 <- %r18 + phisrc.32 %phi5 <- %r18 br .L7 .L7: - phi.32 %r19 <- %phi5, %phi6 - phisrc.32 %phi7(return) <- %r19 + phi.32 %r19 <- %phi4, %phi5 + phisrc.32 %phi6(return) <- %r19 br .L5 .L5: - phi.32 %r20 <- %phi7(return) + phi.32 %r20 <- %phi6(return) ret.32 %r20 @@ -86,7 +86,7 @@ ol: <entry-point> store.32 %arg1 -> 0[i] store.64 %arg2 -> 0[b] - phisrc.32 %phi9 <- $1 + phisrc.32 %phi7 <- $1 load.32 %r21 <- 0[i] setne.1 %r22 <- %r21, $0 cbr %r22, .L11, .L10 @@ -96,16 +96,16 @@ ol: load.64 %r24 <- 8[%r23] setne.1 %r25 <- %r24, $0 zext.32 %r26 <- (1) %r25 - phisrc.32 %phi10 <- %r26 + phisrc.32 %phi8 <- %r26 br .L11 .L11: - phi.32 %r27 <- %phi9, %phi10 - phisrc.32 %phi11(return) <- %r27 + phi.32 %r27 <- %phi7, %phi8 + phisrc.32 %phi9(return) <- %r27 br .L9 .L9: - phi.32 %r28 <- %phi11(return) + phi.32 %r28 <- %phi9(return) ret.32 %r28 @@ -114,7 +114,7 @@ od: <entry-point> store.32 %arg1 -> 0[i] store.64 %arg2 -> 0[b] - phisrc.32 %phi13 <- $1 + phisrc.32 %phi10 <- $1 load.32 %r29 <- 0[i] setne.1 %r30 <- %r29, $0 cbr %r30, .L15, .L14 @@ -125,16 +125,16 @@ od: setfval.64 %r33 <- 0.000000e+00 fcmpune.1 %r34 <- %r32, %r33 zext.32 %r35 <- (1) %r34 - phisrc.32 %phi14 <- %r35 + phisrc.32 %phi11 <- %r35 br .L15 .L15: - phi.32 %r36 <- %phi13, %phi14 - phisrc.32 %phi15(return) <- %r36 + phi.32 %r36 <- %phi10, %phi11 + phisrc.32 %phi12(return) <- %r36 br .L13 .L13: - phi.32 %r37 <- %phi15(return) + phi.32 %r37 <- %phi12(return) ret.32 %r37 @@ -143,7 +143,7 @@ as: <entry-point> store.32 %arg1 -> 0[i] store.64 %arg2 -> 0[b] - phisrc.32 %phi17 <- $0 + phisrc.32 %phi13 <- $0 load.32 %r38 <- 0[i] setne.1 %r39 <- %r38, $0 cbr %r39, .L18, .L19 @@ -155,16 +155,16 @@ as: trunc.2 %r43 <- (32) %r42 setne.1 %r44 <- %r43, $0 zext.32 %r45 <- (1) %r44 - phisrc.32 %phi18 <- %r45 + phisrc.32 %phi14 <- %r45 br .L19 .L19: - phi.32 %r46 <- %phi18, %phi17 - phisrc.32 %phi19(return) <- %r46 + phi.32 %r46 <- %phi14, %phi13 + phisrc.32 %phi15(return) <- %r46 br .L17 .L17: - phi.32 %r47 <- %phi19(return) + phi.32 %r47 <- %phi15(return) ret.32 %r47 @@ -173,7 +173,7 @@ au: <entry-point> store.32 %arg1 -> 0[i] store.64 %arg2 -> 0[b] - phisrc.32 %phi21 <- $0 + phisrc.32 %phi16 <- $0 load.32 %r48 <- 0[i] setne.1 %r49 <- %r48, $0 cbr %r49, .L22, .L23 @@ -185,16 +185,16 @@ au: trunc.3 %r53 <- (32) %r52 setne.1 %r54 <- %r53, $0 zext.32 %r55 <- (1) %r54 - phisrc.32 %phi22 <- %r55 + phisrc.32 %phi17 <- %r55 br .L23 .L23: - phi.32 %r56 <- %phi22, %phi21 - phisrc.32 %phi23(return) <- %r56 + phi.32 %r56 <- %phi17, %phi16 + phisrc.32 %phi18(return) <- %r56 br .L21 .L21: - phi.32 %r57 <- %phi23(return) + phi.32 %r57 <- %phi18(return) ret.32 %r57 @@ -203,7 +203,7 @@ al: <entry-point> store.32 %arg1 -> 0[i] store.64 %arg2 -> 0[b] - phisrc.32 %phi25 <- $0 + phisrc.32 %phi19 <- $0 load.32 %r58 <- 0[i] setne.1 %r59 <- %r58, $0 cbr %r59, .L26, .L27 @@ -213,16 +213,16 @@ al: load.64 %r61 <- 8[%r60] setne.1 %r62 <- %r61, $0 zext.32 %r63 <- (1) %r62 - phisrc.32 %phi26 <- %r63 + phisrc.32 %phi20 <- %r63 br .L27 .L27: - phi.32 %r64 <- %phi26, %phi25 - phisrc.32 %phi27(return) <- %r64 + phi.32 %r64 <- %phi20, %phi19 + phisrc.32 %phi21(return) <- %r64 br .L25 .L25: - phi.32 %r65 <- %phi27(return) + phi.32 %r65 <- %phi21(return) ret.32 %r65 @@ -231,7 +231,7 @@ ad: <entry-point> store.32 %arg1 -> 0[i] store.64 %arg2 -> 0[b] - phisrc.32 %phi29 <- $0 + phisrc.32 %phi22 <- $0 load.32 %r66 <- 0[i] setne.1 %r67 <- %r66, $0 cbr %r67, .L30, .L31 @@ -242,16 +242,16 @@ ad: setfval.64 %r70 <- 0.000000e+00 fcmpune.1 %r71 <- %r69, %r70 zext.32 %r72 <- (1) %r71 - phisrc.32 %phi30 <- %r72 + phisrc.32 %phi23 <- %r72 br .L31 .L31: - phi.32 %r73 <- %phi30, %phi29 - phisrc.32 %phi31(return) <- %r73 + phi.32 %r73 <- %phi23, %phi22 + phisrc.32 %phi24(return) <- %r73 br .L29 .L29: - phi.32 %r74 <- %phi31(return) + phi.32 %r74 <- %phi24(return) ret.32 %r74 diff --git a/validation/alias-distinct.c b/validation/mem2reg/alias-distinct.c index 42937b24..42937b24 100644 --- a/validation/alias-distinct.c +++ b/validation/mem2reg/alias-distinct.c diff --git a/validation/alias-mixed.c b/validation/mem2reg/alias-mixed.c index 0cfbe36b..0cfbe36b 100644 --- a/validation/alias-mixed.c +++ b/validation/mem2reg/alias-mixed.c diff --git a/validation/alias-same.c b/validation/mem2reg/alias-same.c index 55cf4244..55cf4244 100644 --- a/validation/alias-same.c +++ b/validation/mem2reg/alias-same.c diff --git a/validation/mem2reg/broken-phi02.c b/validation/mem2reg/broken-phi02.c index 69776e0f..5aa65071 100644 --- a/validation/mem2reg/broken-phi02.c +++ b/validation/mem2reg/broken-phi02.c @@ -22,7 +22,6 @@ int foo(int a, int b) * is used) causes a missed select-conversion at later stage. * * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * check-output-ignore * check-output-contains: select\\. */ diff --git a/validation/mem2reg/broken-phi03.c b/validation/mem2reg/broken-phi03.c index 58b47979..eff1ff8a 100644 --- a/validation/mem2reg/broken-phi03.c +++ b/validation/mem2reg/broken-phi03.c @@ -23,7 +23,6 @@ int foo(int a, int b) * is used) causes a missed select-conversion at later stage. * * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * check-output-ignore * check-output-contains: select\\. */ diff --git a/validation/mem2reg/cond-expr.c b/validation/mem2reg/cond-expr.c index f38564ef..8acb00ac 100644 --- a/validation/mem2reg/cond-expr.c +++ b/validation/mem2reg/cond-expr.c @@ -10,4 +10,5 @@ int foo(int a, int b, int c) * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file * check-output-ignore * check-output-pattern(2): phi\\. + * check-output-pattern(3): phisrc\\. */ diff --git a/validation/mem2reg/cond-expr5.c b/validation/mem2reg/cond-expr5.c index 6c1e1c34..a3ce5e3a 100644 --- a/validation/mem2reg/cond-expr5.c +++ b/validation/mem2reg/cond-expr5.c @@ -11,8 +11,11 @@ int foo(int p, int q, int a) /* * check-name: cond-expr5 * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file + * * check-output-ignore * check-output-excludes: load\\. * check-output-excludes: store\\. - * check-output-pattern(2): phi\\. + * check-output-excludes: phi\\..*, .*, .* + * check-output-pattern(3): phi\\. + * check-output-pattern(5): phisrc\\. */ diff --git a/validation/mem2reg/init-global-array.c b/validation/mem2reg/init-global-array.c index aea4135a..51ca50e3 100644 --- a/validation/mem2reg/init-global-array.c +++ b/validation/mem2reg/init-global-array.c @@ -1,8 +1,11 @@ -struct { +struct s { int a[2]; -} s; +}; -int sarray(void) + +static struct s s; + +static int sarray(void) { s.a[1] = 1; return s.a[1]; @@ -10,8 +13,9 @@ int sarray(void) /* * check-name: init global array - * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file + * check-command: test-linearize $file * check-output-ignore * check-output-excludes: load\\. * check-output-pattern(1): store\\. + * check-output-pattern(1): ret.32 *\\$1 */ diff --git a/validation/mem2reg/init-local-array.c b/validation/mem2reg/init-local-array.c index 2ac53bc7..639a74f1 100644 --- a/validation/mem2reg/init-local-array.c +++ b/validation/mem2reg/init-local-array.c @@ -1,25 +1,28 @@ -int array(void) +static int array(void) { int a[2]; a[1] = 1; + a[0] = 0; return a[1]; } -int sarray(void) +static int sarray(void) { struct { int a[2]; } s; s.a[1] = 1; + s.a[0] = 0; return s.a[1]; } /* * check-name: init local array - * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file + * check-command: test-linearize $file * check-output-ignore - * check-output-excludes: load\\. - * check-output-excludes: store\\. + * check-output-excludes: load + * check-output-excludes: store + * check-output-pattern(2): ret.32 *\\$1 */ diff --git a/validation/mem2reg/loop02-global.c b/validation/mem2reg/loop02-global.c index a0a8b42b..b627b33d 100644 --- a/validation/mem2reg/loop02-global.c +++ b/validation/mem2reg/loop02-global.c @@ -16,7 +16,7 @@ int foo(void) /* * check-name: loop02 global - * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file + * check-command: test-linearize -Wno-decl $file * check-output-ignore * check-output-excludes: load\\. */ diff --git a/validation/mem2reg/missing-return.c b/validation/mem2reg/missing-return.c new file mode 100644 index 00000000..06f6e4d5 --- /dev/null +++ b/validation/mem2reg/missing-return.c @@ -0,0 +1,34 @@ +int f1(void) +{ + if (1) + return 1; +} + +int f0(void) +{ + if (0) + return 0; +} + +int fx(int p) +{ + if (p) + return 0; +} + +int bar(int p) +{ + if (p) + return 0; + p++; +} + +/* + * check-name: missing-return + * check-command: test-linearize -m32 -fdump-ir=mem2reg -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-pattern(1): ret.32 *\\$1 + * check-output-pattern(3): ret.32 *UNDEF + */ diff --git a/validation/mem2reg/quadra00.c b/validation/mem2reg/quadra00.c index 63b489c9..69ddc977 100644 --- a/validation/mem2reg/quadra00.c +++ b/validation/mem2reg/quadra00.c @@ -20,7 +20,6 @@ int foo(int *a, int b, int c) /* * check-name: quadratic phisrc * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * check-output-ignore * check-output-excludes: phi\\..*, .*, .* * check-output-excludes: phi\\..*, .*, .*, .* diff --git a/validation/mem2reg/quadra01.c b/validation/mem2reg/quadra01.c new file mode 100644 index 00000000..b71f4696 --- /dev/null +++ b/validation/mem2reg/quadra01.c @@ -0,0 +1,27 @@ +#include "repeat.h" + +void use(void *, void *, void *, void *); +void *def(void); + +#define BLOCK(n) { \ + void *label; \ + use(&&w##n, &&x##n, &&y##n, &&z##n); \ +w##n: label = def(); goto *label; \ +x##n: label = def(); goto *label; \ +y##n: label = def(); goto *label; \ +z##n: label = def(); goto *label; \ +} + +static void foo(void) { + REPEAT2(5, BLOCK) +} + +/* + * check-name: quadratic @ liveness + * check-command: test-linearize -I. $file + * check-timeout: + * + * check-output-ignore + * check-output-excludes: phi\\. + * check-output-excludes: phisrc\\. + */ diff --git a/validation/mem2reg/quadra02.c b/validation/mem2reg/quadra02.c new file mode 100644 index 00000000..6475c780 --- /dev/null +++ b/validation/mem2reg/quadra02.c @@ -0,0 +1,18 @@ +#include "repeat.h" + +#define PAT(X) int a##X = X; +static void foo(void) +{ + REPEAT2(12, PAT) +} + +/* + * check-name: quadratic vars + * check-command: test-linearize -I. $file + * check-timeout: + * + * check-output-ignore + * check-output-excludes: phi\\. + * check-output-excludes: phisrc\\. + * check-output-excludes: store\\. + */ diff --git a/validation/reload-aliasing.c b/validation/mem2reg/reload-aliasing.c index 3aad317b..3aad317b 100644 --- a/validation/reload-aliasing.c +++ b/validation/mem2reg/reload-aliasing.c diff --git a/validation/mem2reg/store-deadborn.c b/validation/mem2reg/store-deadborn.c new file mode 100644 index 00000000..cca34d59 --- /dev/null +++ b/validation/mem2reg/store-deadborn.c @@ -0,0 +1,9 @@ +static void foo(int a) +{ + return; + a = 0; +} + +/* + * check-name: store-deadborn + */ diff --git a/validation/linear/stray-phisrc.c b/validation/mem2reg/stray-phisrc.c index e9f35c89..0da7df7a 100644 --- a/validation/linear/stray-phisrc.c +++ b/validation/mem2reg/stray-phisrc.c @@ -18,7 +18,6 @@ static int foo(int **g) /* * check-name: stray phisrc * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-excludes: phisrc\\. diff --git a/validation/mem2reg/struct.c b/validation/mem2reg/struct.c new file mode 100644 index 00000000..13962a8e --- /dev/null +++ b/validation/mem2reg/struct.c @@ -0,0 +1,32 @@ +struct s { + int a; + int b; +}; + +int f0(void) +{ + struct s s; + + s.a = 0; + s.b = 1; + + return s.a; +} + +int f1(void) +{ + struct s s; + + s.a = 1; + s.b = 0; + + return s.b; +} + +/* + * check-name: struct + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-pattern(2): ret.32 *\\$0 + */ diff --git a/validation/mem2reg/undef00.c b/validation/mem2reg/undef00.c index ba9ba915..20ea962c 100644 --- a/validation/mem2reg/undef00.c +++ b/validation/mem2reg/undef00.c @@ -1,14 +1,21 @@ -void bad0(void) +static int badr(void) { int *a; - *a++; + return *a; +} + +static void badw(int v) +{ + int *a; + *a = v; } /* * check-name: undef00 - * check-command: test-linearize -Wno-decl -fdump-ir=mem2reg $file - * check-known-to-fail + * check-command: test-linearize -fdump-ir=mem2reg $file * check-output-ignore * check-output-pattern(1): load\\. * check-output-pattern(1): load\\..*\\[UNDEF\\] + * check-output-pattern(1): store\\. + * check-output-pattern(1): store\\..*\\[UNDEF\\] */ diff --git a/validation/mem2reg/undef01.c b/validation/mem2reg/undef01.c new file mode 100644 index 00000000..985c73d6 --- /dev/null +++ b/validation/mem2reg/undef01.c @@ -0,0 +1,16 @@ +static void foo(void) +{ + int *b; + for (;;) + *b++ = 0; +} + +/* + * check-name: undef01 + * check-command: sparse -Wmaybe-uninitialized $file + * check-known-to-fail + * + * check-error-start +crazy04.c:3:13: warning: variable 'b' may be uninitialized + * check-error-end + */ diff --git a/validation/mem2reg/unused-var.c b/validation/mem2reg/unused-var.c new file mode 100644 index 00000000..ac394582 --- /dev/null +++ b/validation/mem2reg/unused-var.c @@ -0,0 +1,23 @@ +int foo(int a) +{ + switch (a) { + int u = 1; + + default: + return a; + } +} + +/* + * check-name: unused-var + * check-command: test-linearize -Wno-decl $file + * + * check-output-start +foo: +.L0: + <entry-point> + ret.32 %arg1 + + + * check-output-end + */ diff --git a/validation/optim/cse-size.c b/validation/optim/cse-size.c index b75e4bfe..e98c3cde 100644 --- a/validation/optim/cse-size.c +++ b/validation/optim/cse-size.c @@ -13,6 +13,5 @@ static void foo(void) * check-command: test-linearize -Wno-decl $file * * check-output-ignore - * check-output-excludes: phi\\. - * check-output-excludes: phisrc\\. + * check-output-pattern(2): phi\\. */ diff --git a/validation/mem2reg/killed-insn.c b/validation/optim/killed-insn.c index adbef980..d1cdd02e 100644 --- a/validation/mem2reg/killed-insn.c +++ b/validation/optim/killed-insn.c @@ -1,14 +1,13 @@ -static int g; -static void foo(void) +static void foo(int v) { int a[2] = { }; a; - a[1] = g; + a[1] = v; } /* * check-name: killed-insn - * check-command: test-linearize -fdump-ir=mem2reg $file + * check-command: test-linearize $file * * check-output-ignore * check-output-excludes: store\\. diff --git a/validation/optim/missing-select.c b/validation/optim/missing-select.c index 4796e058..07ea008f 100644 --- a/validation/optim/missing-select.c +++ b/validation/optim/missing-select.c @@ -17,7 +17,6 @@ static int foo(int **g) /* * check-name: missing-select * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-contains: select\\. diff --git a/validation/optim/null-phi.c b/validation/optim/null-phi.c new file mode 100644 index 00000000..1f9de4d5 --- /dev/null +++ b/validation/optim/null-phi.c @@ -0,0 +1,9 @@ +static int foo(void) +{ + if (0) + return 0; +} + +/* + * check-name: null-phi + */ diff --git a/validation/repeat.h b/validation/repeat.h new file mode 100644 index 00000000..83433b2a --- /dev/null +++ b/validation/repeat.h @@ -0,0 +1,24 @@ +#define R0(P, S) P(S) +#define R1(P, S) R0(P,S##0) R0(P,S##1) +#define R2(P, S) R0(P,S##0) R0(P,S##1) R0(P,S##2) R0(P,S##3) +#define R3(P, S) R0(P,S##0) R0(P,S##1) R0(P,S##2) R0(P,S##3) R0(P,S##4) R0(P,S##5) R0(P,S##6) R0(P,S##7) +#define R4(P, S) R3(P,S##0) R3(P,S##1) +#define R5(P, S) R3(P,S##0) R3(P,S##1) R3(P,S##2) R3(P,S##3) +#define R6(P, S) R3(P,S##0) R3(P,S##1) R3(P,S##2) R3(P,S##3) R3(P,S##4) R3(P,S##5) R3(P,S##6) R3(P,S##7) +#define R7(P, S) R6(P,S##0) R6(P,S##1) +#define R8(P, S) R6(P,S##0) R6(P,S##1) R6(P,S##2) R6(P,S##3) +#define R9(P, S) R6(P,S##0) R6(P,S##1) R6(P,S##2) R6(P,S##3) R6(P,S##4) R6(P,S##5) R6(P,S##6) R6(P,S##7) +#define R10(P, S) R9(P,S##0) R9(P,S##1) +#define R11(P, S) R9(P,S##0) R9(P,S##1) R9(P,S##2) R9(P,S##3) +#define R12(P, S) R9(P,S##0) R9(P,S##1) R9(P,S##2) R9(P,S##3) R9(P,S##4) R9(P,S##5) R9(P,S##6) R9(P,S##7) +#define R13(P, S) R12(P,S##0) R12(P,S##1) +#define R14(P, S) R12(P,S##0) R12(P,S##1) R12(P,S##2) R12(P,S##3) +#define R15(P, S) R12(P,S##0) R12(P,S##1) R12(P,S##2) R12(P,S##3) R12(P,S##4) R12(P,S##5) R12(P,S##6) R12(P,S##7) +#define R16(P, S) R15(P,S##0) R15(P,S##1) +#define R17(P, S) R15(P,S##0) R15(P,S##1) R15(P,S##2) R15(P,S##3) +#define R18(P, S) R15(P,S##0) R15(P,S##1) R15(P,S##2) R15(P,S##3) R15(P,S##4) R15(P,S##5) R15(P,S##6) R15(P,S##7) +#define R19(P, S) R18(P,S##0) R18(P,S##1) +#define R20(P, S) R18(P,S##0) R18(P,S##1) R18(P,S##2) R18(P,S##3) + +#define REPEAT_(RN, P) RN(P,) +#define REPEAT2(N, P) REPEAT_(R##N,P) diff --git a/validation/var-undef-partial.c b/validation/var-undef-partial.c index 2b665834..f1a07bea 100644 --- a/validation/var-undef-partial.c +++ b/validation/var-undef-partial.c @@ -16,6 +16,5 @@ int foo(int a, int b) * check-description: trigger a bug in symbol/memop simplification * check-description: sparse-llvm is used here as semantic checker of sparse's IR * check-command: sparse-llvm -Wno-decl $file - * check-known-to-fail * check-output-ignore */ |