18uint64_t CFNode::gid_counter_ = 0;
20void CFNode::link(
const CFNode* other)
const {
21 this->succs_.emplace(other);
22 other->preds_.emplace(
this);
31 , entry_(node(scope.entry()))
32 , exit_(node(scope.exit())) {
33 std::queue<Def*> cfg_queue;
36 auto cfg_enqueue = [&](
Def* mut) {
37 if (mut->is_set() && cfg_done.emplace(mut).second) cfg_queue.push(mut);
42 while (!cfg_queue.empty()) {
43 auto src =
pop(cfg_queue);
44 std::queue<const Def*> queue;
47 auto enqueue = [&](
const Def* def) {
48 if (def->isa<
Var>())
return;
50 if (
scope.
bound(def) && done.emplace(def).second) {
51 if (
auto dst = def->isa_mut()) {
53 node(src)->link(node(dst));
61 while (!queue.empty()) {
62 auto def =
pop(queue);
63 for (
auto op : def->ops()) enqueue(op);
72 auto&& n = nodes_[mut];
73 if (n ==
nullptr) n =
new CFNode(mut);
78 for (
const auto& p : nodes_)
delete p.second;
84void CFA::link_to_exit() {
88 std::queue<const CFNode*> queue;
91 for (
auto p :
nodes()) {
93 if (n != exit() && n->succs().empty()) n->link(exit());
96 auto backwards_reachable = [&](
const CFNode* n) {
97 auto enqueue = [&](
const CFNode* n) {
98 if (reachable.emplace(n).second) queue.push(n);
103 while (!queue.empty())
104 for (
auto pred :
pop(queue)->preds()) enqueue(pred);
107 std::stack<const CFNode*> stack;
110 auto push = [&](
const CFNode* n) {
111 if (on_stack.emplace(n).second) {
119 backwards_reachable(exit());
122 while (!stack.empty()) {
123 auto n = stack.top();
126 for (
auto succ : n->succs()) todo |= push(succ);
129 if (!reachable.contains(n)) {
131 backwards_reachable(n);
141 for (
const auto& p :
nodes()) {
143 if (in != entry() && in->preds_.size() == 0) {
144 world().VLOG(
"missing predecessors: {}", in->mut());
151 assert(
false &&
"CFG not sound");
157template<
bool forward>
162 assert_unused(
index == 0);
166 auto& n_index = forward ? n->f_index_ : n->b_index_;
167 n_index = size_t(-2);
169 for (
auto succ : succs(n))
170 if (index(succ) == size_t(-1)) i = post_order_visit(succ, i);
const MutMap< const CFNode * > & nodes() const
const Scope & scope() const
const B_CFG & b_cfg() const
const F_CFG & f_cfg() const
const LoopTree< forward > & looptree() const
const CFNodes & preds(const CFNode *n) const
const CFNode * entry() const
static size_t index(const CFNode *n)
const DomTreeBase< forward > & domtree() const
const CFNodes & succs(const CFNode *n) const
const DomFrontierBase< forward > & domfrontier() const
A Dominance Frontier Graph.
Calculates a loop nesting forest rooted at LoopTree::root_.
A Scope represents a region of Defs that are live from the view of an entry's Var.
bool bound(const Def *def) const
void error(const Def *def, const char *fmt, Args &&... args)
GIDSet< const Def * > DefSet
GIDSet< const CFNode * > CFNodes
std::ostream & operator<<(std::ostream &, const CFNode *)
auto pop(S &s) -> decltype(s.top(), typename S::value_type())
absl::flat_hash_set< K, GIDHash< K >, GIDEq< K > > GIDSet
T & lazy_init(const This *self, std::unique_ptr< T > &ptr)