From eeceb1d5baf3f868a64bf5fa0408f0a06cc48285 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Wed, 18 May 2016 15:30:49 +0100 Subject: [PATCH] Use backwards propagation for liveness analyses on tags. In commit a7a26d17cee825afcbe8659cb31a04a165172eed we added fix-point iterative algorithm to do liveness analyses on tags: The usual algorithm for liveness analyses doesn't use DFS; instead, it iterates on DFA states until fix point is reached (next iteration adds no changes to live set compared to the previous iteration). The fix applies this algorithm. However, instead of iterating until fix point is reached, one may use backwards propagation of live variables starting from the points where these variables are used. --- re2c/src/ir/dfa/tag_deduplication.cc | 127 ++++++++++++++++++++------- re2c/src/ir/skeleton/skeleton.cc | 2 +- re2c/src/ir/tagpool.cc | 50 +++++------ re2c/src/ir/tagpool.h | 8 +- 4 files changed, 122 insertions(+), 65 deletions(-) diff --git a/re2c/src/ir/dfa/tag_deduplication.cc b/re2c/src/ir/dfa/tag_deduplication.cc index c82ac598..3388be59 100644 --- a/re2c/src/ir/dfa/tag_deduplication.cc +++ b/re2c/src/ir/dfa/tag_deduplication.cc @@ -15,56 +15,114 @@ static bool dangling_arcs(const size_t *arcs, size_t narcs) return false; } +// reversed DFA +struct rdfa_t +{ + struct arc_t + { + size_t dest; + size_t tags; + arc_t *next; + + arc_t() + : dest(dfa_t::NIL) + , tags(0) + , next(NULL) + {} + }; + + arc_t **head; + arc_t *list; + + explicit rdfa_t(const dfa_t &dfa) + : head(NULL) + , list(NULL) + { + const size_t nstates = dfa.states.size(); + head = new arc_t*[nstates](); + list = new arc_t[nstates * dfa.nchars]; + + arc_t *a = list; + for (size_t i = 0; i < nstates; ++i) { + dfa_state_t *s = dfa.states[i]; + for (size_t c = 0; c < dfa.nchars; ++c) { + const size_t j = s->arcs[c]; + if (j != dfa_t::NIL) { + a->dest = i; + a->tags = s->tags[c]; + a->next = head[j]; + head[j] = a++; + } + } + } + } + + ~rdfa_t() + { + delete[] head; + delete[] list; + } + + FORBID_COPY(rdfa_t); +}; + +static void backprop(const rdfa_t &rdfa, + Tagpool &tagpool, + size_t *live, + size_t tags, + size_t state) +{ + const size_t l = live[state]; + live[state] = tagpool.orl(l, tags); + if (l == live[state]) return; + + for (rdfa_t::arc_t *a = rdfa.head[state]; a; a = a->next) { + backprop(rdfa, tagpool, live, + tagpool.andlinv(tags, a->tags), a->dest); + } +} + /* note [liveness analyses on tags] * * Tag T is alive in state S if there is a transition * from S to some state S' that does not update T * and either: * - * - S' is the default state + * (1) S' is the default state * and S is final * and T belongs to S's final tag set * - * - S' is the default state + * (2) S' is the default state * and S is not final * and T belongs to fallback tag set * - * - S' is not the default state + * (3) S' is not the default state * and T is alive in S' + * + * The algorithm inspects all DFA states one by one. + * If a state satisfies (1) or (2) for some set of tags, + * the algorithm propagates all these tags backwards to + * fulfill (3). Propagation stops if either all tags are masked + * or live set in not changed after adding new tags. */ static void calc_live(const dfa_t &dfa, size_t fallback, size_t *live) { - const size_t nstates = dfa.states.size(); + rdfa_t rdfa(dfa); + const size_t nstates = dfa.states.size(); for (size_t i = 0; i < nstates; ++i) { dfa_state_t *s = dfa.states[i]; if (dangling_arcs(s->arcs, dfa.nchars)) { - if (s->rule != Rule::NONE) { + const size_t tags = s->rule != Rule::NONE // final state, only rule tags are alive - dfa.tagpool.orl_with_mask(&live[i], - dfa.rules[s->rule].tags, s->rule_tags); - } else { + ? dfa.tagpool.andlinv(dfa.rules[s->rule].tags, + s->rule_tags) // transition to default state and dispatch on // 'yyaccept': all fallback rules are potentially // reachable, their tags are alive // no mask: no rule implies no rule tags - dfa.tagpool.orl(&live[i], fallback); - } - } - } - - for (bool loop = true; loop;) { - loop = false; - for (size_t i = 0; i < nstates; ++i) { - const size_t l = live[i]; - dfa_state_t *s = dfa.states[i]; - for (size_t c = 0; c < dfa.nchars; ++c) { - const size_t j = s->arcs[c]; - if (j != dfa_t::NIL) { - dfa.tagpool.orl_with_mask(&live[i], live[j], s->tags[c]); - } - } - loop |= live[i] != l; + : fallback; + backprop(rdfa, dfa.tagpool, live, tags, i); } } } @@ -77,11 +135,13 @@ static void mask_dead(dfa_t &dfa, const size_t *live) for (size_t c = 0; c < dfa.nchars; ++c) { const size_t j = s->arcs[c]; if (j != dfa_t::NIL) { - dfa.tagpool.andl(&s->tags[c], live[j]); + s->tags[c] = dfa.tagpool.andl(s->tags[c], + live[j]); } } if (s->rule != Rule::NONE) { - dfa.tagpool.andl(&s->rule_tags, dfa.rules[s->rule].tags); + s->rule_tags = dfa.tagpool.andl(s->rule_tags, + dfa.rules[s->rule].tags); } } } @@ -156,7 +216,7 @@ static void incompatibility_table(const dfa_t &dfa, * The algorithm takes quadratic (in the number of tags) time. */ static void equivalence_classes(const bool *incompattbl, - size_t ntags, std::vector &represent) + size_t ntags, size_t *represent) { static const size_t END = std::numeric_limits::max(); std::vector @@ -188,15 +248,15 @@ static void equivalence_classes(const bool *incompattbl, } } -static void patch_tags(dfa_t &dfa, const std::vector &represent) +static void patch_tags(dfa_t &dfa, const size_t *represent) { const size_t nstates = dfa.states.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) { - dfa.tagpool.subst(&s->tags[c], represent); + s->tags[c] = dfa.tagpool.subst(s->tags[c], represent); } - dfa.tagpool.subst(&s->rule_tags, represent); + s->rule_tags = dfa.tagpool.subst(s->rule_tags, represent); } const size_t ntags = dfa.tags.size(); @@ -219,7 +279,7 @@ size_t deduplicate_tags(dfa_t &dfa, size_t fbtags = 0; for (size_t i = 0; i < fallback.size(); ++i) { const size_t r = dfa.states[fallback[i]]->rule; - dfa.tagpool.orl(&fbtags, dfa.rules[r].tags); + fbtags = dfa.tagpool.orl(fbtags, dfa.rules[r].tags); } const size_t nstates = dfa.states.size(); @@ -231,7 +291,7 @@ size_t deduplicate_tags(dfa_t &dfa, bool *incompattbl = new bool[ntags * ntags](); incompatibility_table(dfa, live, fbtags, incompattbl); - std::vector represent(ntags, 0); + size_t *represent = new size_t[ntags](); equivalence_classes(incompattbl, ntags, represent); size_t nreps = 0; @@ -247,6 +307,7 @@ size_t deduplicate_tags(dfa_t &dfa, delete[] live; delete[] incompattbl; + delete[] represent; return nreps; } diff --git a/re2c/src/ir/skeleton/skeleton.cc b/re2c/src/ir/skeleton/skeleton.cc index 00140e21..5e7cc854 100644 --- a/re2c/src/ir/skeleton/skeleton.cc +++ b/re2c/src/ir/skeleton/skeleton.cc @@ -89,7 +89,7 @@ Skeleton::Skeleton( // which may be attributed to states rather than transitions size_t tags = s->rule_tags; for (size_t c = 0; c < nc; ++c) { - dfa.tagpool.orl(&tags, s->tags[c]); + tags = dfa.tagpool.orl(tags, s->tags[c]); } nodes[i].init(dfa.tagpool[tags], s->rule, arcs); diff --git a/re2c/src/ir/tagpool.cc b/re2c/src/ir/tagpool.cc index 3253ea29..9b24b912 100644 --- a/re2c/src/ir/tagpool.cc +++ b/re2c/src/ir/tagpool.cc @@ -23,14 +23,12 @@ size_t Tagpool::insert(const bool *tags) return pool.insert(tags, ntags * sizeof(bool)); } -void Tagpool::orl(size_t *pt, size_t o) +size_t Tagpool::orl(size_t t, size_t o) { - const size_t t = *pt; if (t == o || o == 0) { - return; + return t; } else if (t == 0) { - *pt = o; - return; + return o; } const bool *tags = operator[](t); @@ -38,53 +36,51 @@ void Tagpool::orl(size_t *pt, size_t o) for (size_t i = 0; i < ntags; ++i) { buff[i] = tags[i] | ortags[i]; } - *pt = insert(buff); + return insert(buff); } -void Tagpool::orl_with_mask(size_t *pt, size_t o, size_t m) +size_t Tagpool::andl(size_t t, size_t a) { - const size_t t = *pt; - if (t == o || o == 0) { - return; + if (t == a) { + return t; + } else if (t == 0 || a == 0) { + return 0; } const bool *tags = operator[](t); - const bool *ortags = operator[](o); - const bool *masktags = operator[](m); + const bool *andtags = operator[](a); for (size_t i = 0; i < ntags; ++i) { - buff[i] = tags[i] | (ortags[i] & ~masktags[i]); + buff[i] = tags[i] & andtags[i]; } - *pt = insert(buff); + return insert(buff); } -void Tagpool::andl(size_t *pt, size_t a) +size_t Tagpool::andlinv(size_t t, size_t a) { - const size_t t = *pt; - if (t == a) { - return; - } else if (t == 0 || a == 0) { - *pt = 0; - return; + if (a == 0) { + return t; + } else if (t == 0 || t == a) { + return 0; } const bool *tags = operator[](t); - const bool *andtags = operator[](a); + const bool *andinvtags = operator[](a); for (size_t i = 0; i < ntags; ++i) { - buff[i] = tags[i] & andtags[i]; + buff[i] = tags[i] & ~andinvtags[i]; } - *pt = insert(buff); + return insert(buff); } -void Tagpool::subst(size_t *pt, const std::vector &represent) +size_t Tagpool::subst(size_t t, const size_t *represent) { - const bool *tags = operator[](*pt); + const bool *tags = operator[](t); memset(buff, 0, ntags * sizeof(bool)); for (size_t i = 0; i < ntags; ++i) { if (tags[i]) { buff[represent[i]] = true; } } - *pt = insert(buff); + return insert(buff); } const bool *Tagpool::operator[](size_t idx) diff --git a/re2c/src/ir/tagpool.h b/re2c/src/ir/tagpool.h index 9b972965..fc9de8fc 100644 --- a/re2c/src/ir/tagpool.h +++ b/re2c/src/ir/tagpool.h @@ -19,10 +19,10 @@ public: explicit Tagpool(size_t n); ~Tagpool(); size_t insert(const bool *tags); - void orl(size_t *pt, size_t o); - void orl_with_mask(size_t *pt, size_t o, size_t m); - void andl(size_t *pt, size_t a); - void subst(size_t *pt, const std::vector &represent); + 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); FORBID_COPY(Tagpool); }; -- 2.40.0