From 262c22617c9c3d3ca1675b87b5434c770ad38322 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Wed, 19 Oct 2016 13:33:23 +0100 Subject: [PATCH] Moved tag liveness data out of Tagpool. This is necessary to introduce tag versions: we'll have to calculate liveness of tag versions (rather than tags) and won't be able to keep liveness data in Tagpool. --- re2c/src/ir/dfa/fallback_tags.cc | 6 +- re2c/src/ir/dfa/tag_deduplication.cc | 246 ++++++++++++++++----------- re2c/src/ir/skeleton/skeleton.cc | 20 ++- re2c/src/ir/skeleton/skeleton.h | 1 + re2c/src/ir/tag.cc | 60 ------- re2c/src/ir/tag.h | 4 - 6 files changed, 170 insertions(+), 167 deletions(-) diff --git a/re2c/src/ir/dfa/fallback_tags.cc b/re2c/src/ir/dfa/fallback_tags.cc index f5cfb77b..fe667989 100644 --- a/re2c/src/ir/dfa/fallback_tags.cc +++ b/re2c/src/ir/dfa/fallback_tags.cc @@ -64,6 +64,8 @@ void insert_fallback_tags(dfa_t &dfa) nstates = dfa.states.size(), ntags = dfa.tags.size(); bool *been = new bool[nstates]; + bool *total = dfa.tagpool.buffer2; + std::fill(total, total + ntags, false); for (size_t i = 0; i < nstates; ++i) { dfa_state_t *s = dfa.states[i]; @@ -80,6 +82,7 @@ void insert_fallback_tags(dfa_t &dfa) *upd = dfa.tagpool[s->rule_tags.set]; for (size_t t = 0; t < ntags; ++t) { owrt[t] &= fin[t] && !upd[t]; + total[t] |= owrt[t]; } const size_t copy = dfa.tagpool.insert(owrt); @@ -91,10 +94,11 @@ void insert_fallback_tags(dfa_t &dfa) } } s->rule_tags.copy = copy; - dfa.copy_tags = dfa.tagpool.orl(dfa.copy_tags, copy); } } + dfa.copy_tags = dfa.tagpool.insert(total); + delete[] been; } diff --git a/re2c/src/ir/dfa/tag_deduplication.cc b/re2c/src/ir/dfa/tag_deduplication.cc index 3ce25c34..95243dff 100644 --- a/re2c/src/ir/dfa/tag_deduplication.cc +++ b/re2c/src/ir/dfa/tag_deduplication.cc @@ -1,4 +1,5 @@ #include +#include #include "src/ir/dfa/dfa.h" @@ -6,28 +7,36 @@ namespace re2c { static void forwprop(const dfa_t &dfa, bool *been, size_t state, - size_t *live, size_t need) + bool *live, const bool *need) { if (been[state]) return; been[state] = true; + const size_t + nsym = dfa.nchars, + ntag = dfa.tags.size(); const dfa_state_t *s = dfa.states[state]; - size_t *l = &live[state * dfa.nchars]; - for (size_t c = 0; c < dfa.nchars; ++c) { + + for (size_t c = 0; c < nsym; ++c) { const size_t dest = s->arcs[c]; if (dest != dfa_t::NIL && dfa.states[dest]->fallthru) { - l[c] = dfa.tagpool.orl(l[c], need); + bool *l = &live[(state * nsym + c) * ntag]; + for (size_t t = 0; t < ntag; ++t) { + l[t] |= need[t]; + } forwprop(dfa, been, dest, live, need); } } } -static void calc_live(const dfa_t &dfa, size_t *live) +static void liveness(const dfa_t &dfa, bool *live) { const size_t nstate = dfa.states.size(), nsym = dfa.nchars, - narc = nstate * nsym; + narc = nstate * nsym, + ntag = dfa.tags.size(); + bool *l0 = dfa.tagpool.buffer1; /* note [control flow equations for tag liveness] * @@ -41,7 +50,7 @@ static void calc_live(const dfa_t &dfa, size_t *live) * - all outgoing arcs from state s2 * - if state s2 is final, corresponding rule action */ - std::fill(live, live + narc, ZERO_TAGS); + memset(live, 0, narc * ntag * sizeof(bool)); for (bool loop = true; loop;) { loop = false; @@ -50,21 +59,29 @@ static void calc_live(const dfa_t &dfa, size_t *live) if (i == dfa_t::NIL) continue; const dfa_state_t *s = dfa.states[i]; - size_t l = s->rule == Rule::NONE - ? ZERO_TAGS - : dfa.tagpool.andlinv(dfa.rules[s->rule].tags, s->rule_tags.set); + bool *l = &live[a * ntag]; + memcpy(l0, l, ntag * sizeof(bool)); + memset(l, 0, ntag * sizeof(bool)); - const size_t *live_i = &live[i * nsym]; - for (size_t c = 0; c < nsym; ++c) { - l = dfa.tagpool.orl(l, - dfa.tagpool.andlinv(live_i[c], s->tags[c].set)); + if (s->rule != Rule::NONE) { + const bool + *use = dfa.tagpool[dfa.rules[s->rule].tags], + *def = dfa.tagpool[s->rule_tags.set]; + for (size_t t = 0; t < ntag; ++t) { + l[t] |= use[t] && !def[t]; + } } - size_t *pl = &live[a]; - if (*pl != l) { - *pl = l; - loop = true; + for (size_t c = 0; c < nsym; ++c) { + const bool + *use = &live[(i * nsym + c) * ntag], + *def = dfa.tagpool[s->tags[c].set]; + for (size_t t = 0; t < ntag; ++t) { + l[t] |= use[t] && !def[t]; + } } + + loop |= memcmp(l, l0, ntag * sizeof(bool)) != 0; } } @@ -76,82 +93,102 @@ static void calc_live(const dfa_t &dfa, size_t *live) */ bool *been = new bool[nstate]; for (size_t i = 0; i < nstate; ++i) { - dfa_state_t *s = dfa.states[i]; + const dfa_state_t *s = dfa.states[i]; if (s->fallback) { - const size_t need = dfa.tagpool.andlinv( - dfa.rules[s->rule].tags, s->rule_tags.set); + const bool + *use = dfa.tagpool[dfa.rules[s->rule].tags], + *def = dfa.tagpool[s->rule_tags.set]; + for (size_t t = 0; t < ntag; ++t) { + l0[t] = use[t] && !def[t]; + } std::fill(been, been + nstate, false); - forwprop(dfa, been, i, live, need); + forwprop(dfa, been, i, live, l0); } } delete[] been; } -static void mask_dead(dfa_t &dfa, const size_t *live) +static void mask_dead(dfa_t &dfa, const bool *live) { - const size_t nstates = dfa.states.size(); - for (size_t i = 0; i < nstates; ++i) { - dfa_state_t *s = dfa.states[i]; - const size_t *l = &live[i * dfa.nchars]; - for (size_t c = 0; c < dfa.nchars; ++c) { - const size_t j = s->arcs[c]; - if (j != dfa_t::NIL) { - s->tags[c].set = dfa.tagpool.andl(s->tags[c].set, l[c]); + const size_t + nsym = dfa.nchars, + narc = dfa.states.size() * nsym, + ntag = dfa.tags.size(); + + for (size_t a = 0; a < narc; ++a) { + const size_t + c = a % nsym, + i = a / nsym; + const dfa_state_t *s = dfa.states[i]; + // rule tags can't be dead by construction + + size_t *p = &s->tags[c].set; + if (*p != ZERO_TAGS) { + const bool + *liv = &live[a * ntag], + *set = dfa.tagpool[*p]; + bool *set_liv = dfa.tagpool.buffer1; + for (size_t t = 0; t < ntag; ++t) { + set_liv[t] = set[t] && liv[t]; } - } - if (s->rule != Rule::NONE) { - s->rule_tags.set = dfa.tagpool.andl(s->rule_tags.set, - dfa.rules[s->rule].tags); + *p = dfa.tagpool.insert(set_liv); } } } // tags that are updated here are pairwise incompatible // with all tags that are alive, but not updated here -static void incompatible(bool *tbl, - Tagpool &tagpool, size_t l, size_t t) +static void interfere(bool *intrf, size_t ntag, + const bool *live, const bool *tags) { - const size_t ntags = tagpool.ntags; - const bool *live = tagpool[l]; - const bool *tags = tagpool[t]; - for (size_t i = 0; i < ntags; ++i) { + for (size_t i = 0; i < ntag; ++i) { if (live[i] && !tags[i]) { - for (size_t j = 0; j < ntags; ++j) { + for (size_t j = 0; j < ntag; ++j) { if (tags[j]) { - tbl[i * ntags + j] = tbl[j * ntags + i] = true; + intrf[i * ntag + j] = intrf[j * ntag + i] = true; } } } } } -static void incompatibility_table(const dfa_t &dfa, - const size_t *livetags, bool *incompattbl) +static void interference(const dfa_t &dfa, + const bool *live, bool *intrf) { - const size_t nstates = dfa.states.size(); - const size_t ntags = dfa.tags.size(); - for (size_t i = 0; i < nstates; ++i) { + const size_t + nstate = dfa.states.size(), + ntag = dfa.tags.size(), + nsym = dfa.nchars; + + memset(intrf, 0, ntag * ntag * sizeof(bool)); + for (size_t i = 0; i < nstate; ++i) { const dfa_state_t *s = dfa.states[i]; - const size_t *l = &livetags[i * dfa.nchars]; - for (size_t c = 0; c < dfa.nchars; ++c) { - const size_t j = s->arcs[c]; - if (j != dfa_t::NIL) { - incompatible(incompattbl, dfa.tagpool, l[c], s->tags[c].set); - } - } + if (s->rule != Rule::NONE) { - incompatible(incompattbl, dfa.tagpool, - dfa.rules[s->rule].tags, s->rule_tags.set); + const bool + *liv = dfa.tagpool[dfa.rules[s->rule].tags], + *set = dfa.tagpool[s->rule_tags.set]; + interfere(intrf, ntag, liv, set); + } + + for (size_t c = 0; c < nsym; ++c) { + const size_t x = s->tags[c].set; + if (x != ZERO_TAGS) { + const bool + *liv = &live[(i * nsym + c) * ntag], + *set = dfa.tagpool[x]; + interfere(intrf, ntag, liv, set); + } } } // fixed tags should not participate in deduplication, so // each fixed tag is incompatible with all other tags - for (size_t i = 0; i < ntags; ++i) { + for (size_t i = 0; i < ntag; ++i) { if (dfa.tags[i].type == Tag::FIX) { - for (size_t j = 0; j < ntags; ++j) { - incompattbl[i * ntags + j] - = incompattbl[j * ntags + i] + for (size_t j = 0; j < ntag; ++j) { + intrf[i * ntag + j] + = intrf[j * ntag + i] = j != i; } } @@ -169,21 +206,23 @@ static void incompatibility_table(const dfa_t &dfa, * We build just some cover (not necessarily minimal). * The algorithm takes quadratic (in the number of tags) time. */ -static void equivalence_classes(const bool *incompattbl, - size_t ntags, size_t *represent) +static size_t equivalence_classes(const dfa_t &dfa, + const bool *intrf, size_t *represent) { static const size_t END = std::numeric_limits::max(); + const size_t ntags = dfa.tags.size(); std::vector head(ntags, END), // list of representatives next(ntags, END); // list of tags mapped to the same representative // skip the 1st tag, it maps to itself + memset(represent, 0, ntags * sizeof(size_t)); for (size_t c = 1; c < ntags; ++c) { size_t h; for (h = 0; h != END; h = head[h]) { size_t n; for (n = h; n != END; n = next[n]) { - if (incompattbl[c * ntags + n]) { + if (intrf[c * ntags + n]) { break; } } @@ -200,23 +239,47 @@ static void equivalence_classes(const bool *incompattbl, head[0] = c; } } + + size_t nreps = 0; + for (size_t i = 0; i < ntags; ++i) { + if (dfa.tags[i].type == Tag::VAR && represent[i] == i) { + ++nreps; + } + } + return nreps; } -static void patch_tags(dfa_t &dfa, const size_t *represent) +static void subst(Tagpool &tagpool, size_t *ptags, const size_t *represent) { - const size_t nstates = dfa.states.size(); + const size_t ntag = tagpool.ntags; + const bool *tags = tagpool[*ptags]; + bool *subs = tagpool.buffer1; + memset(subs, 0, ntag * sizeof(bool)); + for (size_t t = 0; t < ntag; ++t) { + if (tags[t]) { + subs[represent[t]] = true; + } + } + *ptags = tagpool.insert(subs); +} + +static void substitute(dfa_t &dfa, const size_t *represent) +{ + const size_t + nstates = dfa.states.size(), + ntags = dfa.tags.size(); + for (size_t i = 0; i < nstates; ++i) { dfa_state_t *s = dfa.states[i]; for (size_t c = 0; c < dfa.nchars; ++c) { - s->tags[c].set = dfa.tagpool.subst(s->tags[c].set, represent); - s->tags[c].copy = dfa.tagpool.subst(s->tags[c].copy, represent); + subst(dfa.tagpool, &s->tags[c].set, represent); + subst(dfa.tagpool, &s->tags[c].copy, represent); } - s->rule_tags.set = dfa.tagpool.subst(s->rule_tags.set, represent); - s->rule_tags.copy = dfa.tagpool.subst(s->rule_tags.copy, represent); + subst(dfa.tagpool, &s->rule_tags.set, represent); + subst(dfa.tagpool, &s->rule_tags.copy, represent); } - dfa.copy_tags = dfa.tagpool.subst(dfa.copy_tags, represent); + subst(dfa.tagpool, &dfa.copy_tags, represent); - const size_t ntags = dfa.tags.size(); for (size_t i = 0; i < ntags; ++i) { Tag &t = dfa.tags[i]; if (t.type == Tag::VAR) { @@ -227,41 +290,26 @@ static void patch_tags(dfa_t &dfa, const size_t *represent) size_t deduplicate_tags(dfa_t &dfa) { - const size_t ntags = dfa.tags.size(); - if (ntags == 0) { - return 0; - } + const size_t ntag = dfa.tags.size(); + if (ntag == 0) return 0; - const size_t - nstates = dfa.states.size(), - nedges = nstates * dfa.nchars; - size_t *live = new size_t[nedges](); - calc_live(dfa, live); + bool *live = new bool[dfa.states.size() * dfa.nchars * ntag]; + bool *interfere = new bool[ntag * ntag]; + size_t *represent = new size_t[ntag]; + liveness(dfa, live); mask_dead(dfa, live); - - bool *incompattbl = new bool[ntags * ntags](); - incompatibility_table(dfa, live, incompattbl); - - size_t *represent = new size_t[ntags](); - equivalence_classes(incompattbl, ntags, represent); - - size_t nreps = 0; - for (size_t i = 0; i < ntags; ++i) { - if (dfa.tags[i].type == Tag::VAR && represent[i] == i) { - ++nreps; - } - } - - if (nreps < ntags) { - patch_tags(dfa, represent); + interference(dfa, live, interfere); + const size_t nrep = equivalence_classes(dfa, interfere, represent); + if (nrep < ntag) { + substitute(dfa, represent); } delete[] live; - delete[] incompattbl; + delete[] interfere; delete[] represent; - return nreps; + return nrep; } } // namespace re2c diff --git a/re2c/src/ir/skeleton/skeleton.cc b/re2c/src/ir/skeleton/skeleton.cc index 6b40ecee..0ebae734 100644 --- a/re2c/src/ir/skeleton/skeleton.cc +++ b/re2c/src/ir/skeleton/skeleton.cc @@ -1,4 +1,5 @@ #include +#include #include "src/ir/dfa/dfa.h" #include "src/ir/skeleton/path.h" @@ -14,6 +15,11 @@ Node::Node() , tags(NULL) {} +Node::~Node() +{ + delete[] tags; +} + void Node::init(const bool *ts, size_t r, const std::vector > &a) { @@ -88,12 +94,20 @@ Skeleton::Skeleton( // in skeleton we are only interested in trailing contexts // which may be attributed to states rather than transitions // trailing context also cannot have fallback tag - size_t tags = s->rule_tags.set; + Tagpool &tagpool = dfa.tagpool; + const size_t ntag = tagpool.ntags; + bool *tags = new bool[ntag]; + memcpy(tags, tagpool[s->rule_tags.set], ntag * sizeof(bool)); for (size_t c = 0; c < nc; ++c) { - tags = dfa.tagpool.orl(tags, s->tags[c].set); + const size_t x = s->tags[c].set; + if (x == ZERO_TAGS) continue; + const bool *set = tagpool[x]; + for (size_t t = 0; t < ntag; ++t) { + tags[t] |= set[t]; + } } - nodes[i].init(dfa.tagpool[tags], s->rule, arcs); + nodes[i].init(tags, s->rule, arcs); } // initialize size of key diff --git a/re2c/src/ir/skeleton/skeleton.h b/re2c/src/ir/skeleton/skeleton.h index 1ac6da18..cbe5c6f7 100644 --- a/re2c/src/ir/skeleton/skeleton.h +++ b/re2c/src/ir/skeleton/skeleton.h @@ -39,6 +39,7 @@ struct Node const bool *tags; Node(); + ~Node(); void init(const bool *ts, size_t r, const std::vector > &arcs); bool end() const; diff --git a/re2c/src/ir/tag.cc b/re2c/src/ir/tag.cc index 0f5ebf82..7c33bfce 100644 --- a/re2c/src/ir/tag.cc +++ b/re2c/src/ir/tag.cc @@ -88,64 +88,4 @@ const bool *Tagpool::operator[](size_t idx) const return lookup[idx]; } -size_t Tagpool::orl(size_t t, size_t o) -{ - if (t == o || o == 0) { - return t; - } else if (t == ZERO_TAGS) { - return o; - } - - const bool *tags = operator[](t); - const bool *ortags = operator[](o); - for (size_t i = 0; i < ntags; ++i) { - buffer[i] = tags[i] | ortags[i]; - } - return insert(buffer); -} - -size_t Tagpool::andl(size_t t, size_t a) -{ - if (t == a) { - return t; - } else if (t == ZERO_TAGS || a == ZERO_TAGS) { - return ZERO_TAGS; - } - - const bool *tags = operator[](t); - const bool *andtags = operator[](a); - for (size_t i = 0; i < ntags; ++i) { - buffer[i] = tags[i] & andtags[i]; - } - return insert(buffer); -} - -size_t Tagpool::andlinv(size_t t, size_t a) -{ - if (a == ZERO_TAGS) { - return t; - } else if (t == ZERO_TAGS || t == a) { - return ZERO_TAGS; - } - - const bool *tags = operator[](t); - const bool *andinvtags = operator[](a); - for (size_t i = 0; i < ntags; ++i) { - buffer[i] = tags[i] & ~andinvtags[i]; - } - return insert(buffer); -} - -size_t Tagpool::subst(size_t t, const size_t *represent) -{ - const bool *tags = operator[](t); - memset(buffer, 0, ntags * sizeof(bool)); - for (size_t i = 0; i < ntags; ++i) { - if (tags[i]) { - buffer[represent[i]] = true; - } - } - return insert(buffer); -} - } // namespace re2c diff --git a/re2c/src/ir/tag.h b/re2c/src/ir/tag.h index 9b981eba..a046d32c 100644 --- a/re2c/src/ir/tag.h +++ b/re2c/src/ir/tag.h @@ -53,10 +53,6 @@ public: explicit Tagpool(size_t n); ~Tagpool(); size_t insert(const bool *tags); - size_t orl(size_t t, size_t o); - size_t andl(size_t t, size_t a); - size_t andlinv(size_t t, size_t a); - size_t subst(size_t t, const size_t *represent); const bool *operator[](size_t idx) const; FORBID_COPY(Tagpool); }; -- 2.40.0