Dominance.hpp

Go to the documentation of this file.

/*
 *
 *                   _/_/_/    _/_/   _/    _/ _/_/_/    _/_/
 *                  _/   _/ _/    _/ _/_/  _/ _/   _/ _/    _/
 *                 _/_/_/  _/_/_/_/ _/  _/_/ _/   _/ _/_/_/_/
 *                _/      _/    _/ _/    _/ _/   _/ _/    _/
 *               _/      _/    _/ _/    _/ _/_/_/  _/    _/
 *
 *             ***********************************************
 *                              PandA Project
 *                     URL: http://panda.dei.polimi.it
 *                       Politecnico di Milano - DEIB
 *                        System Architectures Group
 *             ***********************************************
 *              Copyright (C) 2004-2024 Politecnico di Milano
 *
 *   This file is part of the PandA framework.
 *
 *   The PandA framework is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
#ifndef DOMINANCE_HPP
#define DOMINANCE_HPP

#include "Parameter.hpp"

#include "custom_map.hpp"
#include "custom_set.hpp"
#include <vector>

#include "dbgPrintHelper.hpp" // for DEBUG_LEVEL_NONE
#include "exceptions.hpp"
#include "string_manipulation.hpp" // for GET_CLASS
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/version.hpp>

using TBB = unsigned long;

template <typename GraphObj>
class dom_info
{
 private:
   using Vertex = typename boost::graph_traits<const GraphObj>::vertex_descriptor;
   using in_edge_iterator = typename boost::graph_traits<const GraphObj>::in_edge_iterator;
   using out_edge_iterator = typename boost::graph_traits<const GraphObj>::out_edge_iterator;
   using edge = typename boost::graph_traits<const GraphObj>::edge_descriptor;
   using Vertex_iterator = typename boost::graph_traits<const GraphObj>::vertex_iterator;

   std::vector<TBB> dfs_parent;

   std::vector<TBB> key;

   std::vector<TBB> path_min;

   std::vector<TBB> bucket;

   std::vector<TBB> next_bucket;

   std::vector<TBB> set_chain;

   std::vector<unsigned int> set_size;
   std::vector<TBB> set_child;

   unsigned int dfsnum;

   unsigned int nodes;

   CustomOrderedSet<TBB> fake_exit_edge;

   const unsigned long int last_basic_block;

   const Vertex& en_block;

   const Vertex& ex_block;

   const GraphObj& g;

   std::vector<TBB> dom;

   std::vector<TBB> dfs_order;
   std::vector<Vertex> dfs_to_bb;

   std::map<Vertex, size_t> index_map;

   int debug_level;

   void calc_dfs_tree_rec(Vertex bb)
   {
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
                     "-->Computing dfs tree starting from v_" + std::to_string(index_map[bb]));
      // bb is the parent Vertex
      /* We call this _only_ if bb is not already visited.  */
      edge e;
      TBB child_i, my_i = 0;
      typename boost::graph_traits<GraphObj>::out_edge_iterator ei, ei_end;

      for(boost::tie(ei, ei_end) = boost::out_edges(bb, g); ei != ei_end; ei++)
      {
         // bn is the child Vertex
         Vertex bn = boost::target(*ei, g);
         // if it has yet been visited we skip it
         if(dfs_order[index_map[bn]])
         {
            continue;
         }

         /* Fill the DFS tree info calculatable _before_ recursing.  */
         if(bb != en_block)
         {
            my_i = dfs_order[index_map[bb]];
         }
         else
         {
            // In this way dfs_parent of entry is itself
            my_i = dfs_order[last_basic_block];
         }
         // Computed a new dfs index for this Vertex
         child_i = dfs_order[index_map[bn]] = dfsnum++;
         dfs_to_bb[child_i] = bn;
         dfs_parent[child_i] = my_i;
         // recursive call
         calc_dfs_tree_rec(bn);
      }
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
                     "<--Computed dfs tree starting from v_" + std::to_string(index_map[bb]));
   }
   void compress(TBB v)
   {
      /* Btw. It's not worth to unrecurse compress() as the depth is usually not
      greater than 5 even for huge graphs (I've not seen call depth > 4).
      Also performance wise compress() ranges _far_ behind eval().  */
      TBB parent = set_chain[v];
      if(set_chain[parent])
      {
         compress(parent);
         if(key[path_min[parent]] < key[path_min[v]])
         {
            path_min[v] = path_min[parent];
         }
         set_chain[v] = set_chain[parent];
      }
   }

   TBB eval(TBB v)
   {
      /* The representant of the set V is in, also called root (as the set
      representation is a tree).  */
      TBB rep = set_chain[v];
      /* V itself is the root.  */
      if(!rep)
      {
         return path_min[v];
      }

      /* Compress only if necessary.  */
      if(set_chain[rep])
      {
         compress(v);
         rep = set_chain[v];
      }

      if(key[path_min[rep]] >= key[path_min[v]])
      {
         return path_min[v];
      }
      else
      {
         return path_min[rep];
      }
   }

   void link_roots(TBB v, TBB w)
   {
      TBB s = w;
      /* Rebalance the tree.  */
      while(key[path_min[w]] < key[path_min[set_child[s]]])
      {
         if(set_size[s] + set_size[set_child[set_child[s]]] >= 2 * set_size[set_child[s]])
         {
            set_chain[set_child[s]] = s;
            set_child[s] = set_child[set_child[s]];
         }
         else
         {
            set_size[set_child[s]] = set_size[s];
            s = set_chain[s] = set_child[s];
         }
      }
      path_min[s] = path_min[w];
      set_size[v] += set_size[w];
      if(set_size[v] < 2 * set_size[w])
      {
         TBB tmp = s;
         s = set_child[v];
         set_child[v] = tmp;
      }
      /* Merge all subtrees.  */
      while(s)
      {
         set_chain[s] = v;
         s = set_child[s];
      }
   }

 public:
   dom_info(const GraphObj& _g, const Vertex& _en_block, const Vertex& _ex_block, const ParameterConstRef param)
       : dfs_parent(boost::num_vertices(_g) + 1, 0),
         key(boost::num_vertices(_g) + 1, 0),
         path_min(boost::num_vertices(_g) + 1, 0),
         bucket(boost::num_vertices(_g) + 1, 0),
         next_bucket(boost::num_vertices(_g) + 1, 0),
         set_chain(boost::num_vertices(_g) + 1, 0),
         set_size(boost::num_vertices(_g) + 1, 1),
         set_child(boost::num_vertices(_g) + 1, 0),
         dfsnum(1),
         nodes(0),
         last_basic_block(boost::num_vertices(_g)),
         en_block(_en_block),
         ex_block(_ex_block),
         g(_g),
         dom(boost::num_vertices(_g) + 1, 0),
         dfs_order(boost::num_vertices(_g) + 1, 0),
         dfs_to_bb(boost::num_vertices(_g) + 1, boost::graph_traits<GraphObj>::null_vertex()),
         debug_level(param->get_class_debug_level(GET_CLASS(*this), DEBUG_LEVEL_NONE))
   {
      size_t index_counter = 0;
      Vertex_iterator v, v_end;
      for(boost::tie(v, v_end) = boost::vertices(g); v != v_end; v++, index_counter++)
      {
         index_map[*v] = index_counter;
      }
      for(unsigned int i = 0; i < boost::num_vertices(_g) + 1; i++)
      {
         path_min[i] = i;
         key[i] = i;
      }
   }

   void calc_dfs_tree(bool reverse)
   {
      Vertex begin = en_block;
      dfs_order[last_basic_block] = dfsnum;
      dfs_to_bb[dfsnum] = begin;
      dfsnum++;
      calc_dfs_tree_rec(begin);
      if(reverse)
      {
         /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
            They are reverse-unreachable.  In the dom-case we disallow such
            nodes, but in post-dom we have to deal with them.

            There are two situations in which this occurs.  First, noreturn
            functions.  Second, infinite loops.  In the first case we need to
            pretend that there is an edge to the exit block.  In the second
            case, we wind up with a forest.  We need to process all noreturn
            blocks before we know if we've got any infinite loops.  */

         Vertex b;
         bool saw_unconnected = false;

         Vertex_iterator vi, vi_end;
         for(boost::tie(vi, vi_end) = boost::vertices(g); vi != vi_end; vi++)
         {
            b = *vi;
            // skip entry
            if(en_block == b)
            {
               continue;
            }
            if(boost::in_degree(b, g) > 0)
            {
               if(dfs_order[index_map[b]] == 0)
               {
                  saw_unconnected = true;
               }
               continue;
            }
            fake_exit_edge.insert(index_map[b]);
            dfs_order[index_map[b]] = dfsnum;
            dfs_to_bb[dfsnum] = b;
            dfs_parent[dfsnum] = dfs_order[last_basic_block];
            dfsnum++;
            calc_dfs_tree_rec(b);
         }

         if(saw_unconnected)
         {
            for(boost::tie(vi, vi_end) = boost::vertices(g); vi != vi_end; vi++)
            {
               b = *vi;
               // skip entry
               if(en_block == b)
               {
                  continue;
               }
               if(dfs_order[index_map[b]])
               {
                  continue;
               }
               fake_exit_edge.insert(index_map[b]);
               dfs_order[index_map[b]] = dfsnum;
               dfs_to_bb[dfsnum] = b;
               dfs_parent[dfsnum] = dfs_order[last_basic_block];
               dfsnum++;
               calc_dfs_tree_rec(b);
            }
         }
      }

      nodes = dfsnum - 1;

      Vertex_iterator i, i_end;
#if HAVE_ASSERTS
      unsigned int counter = 0;
      for(boost::tie(i, i_end) = boost::vertices(g); i != i_end; i++)
      {
         ++counter;
      }
#endif
      /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
      THROW_ASSERT(nodes == counter, "there is _no_ path from ENTRY to EXIT at all. Number of vertices in the graph: " +
                                         std::to_string(num_vertices(g)) + " Number of reachable from entry vertices " +
                                         std::to_string(nodes));
#ifndef NDEBUG
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Vertices in dfs order");
      for(size_t index = 0; index < dfs_to_bb.size(); index++)
      {
         INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
                        "---" + std::to_string(index) + " v_" + std::to_string(index_map[dfs_to_bb[index]]));
      }
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--");
#endif
   }

   void calc_idoms(bool reverse)
   {
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Computing immediate dominators");
      TBB v, w;
      typename boost::graph_traits<GraphObj>::in_edge_iterator ei, einext, ei_end, einext_end;

      /* Go backwards in DFS order, to first look at the leafs.  */
      v = nodes;
      while(v > 1)
      {
         INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
                        "-->Analyzing node in position " + std::to_string(v) + " v_" +
                            std::to_string(index_map[dfs_to_bb[v]]));
         Vertex bb = dfs_to_bb[v];
         edge e;
         bool do_fake_exit_edge = false;

         INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Parent is " + std::to_string(dfs_parent[v]));
         TBB par = dfs_parent[v];
         TBB k = v;

         boost::tie(ei, ei_end) = boost::in_edges(bb, g);

         if(reverse)
         {
            /* If this block has a fake edge to exit, process that first.  */
            if(fake_exit_edge.find(index_map[bb]) != fake_exit_edge.end())
            {
               einext = ei;
               do_fake_exit_edge = true;
            }
         }

         /* Search all direct predecessors for the smallest node with a path
         to them.  That way we have the smallest node with also a path to
         us only over nodes behind us.  In effect we search for our
         semidominator.  */
         while(do_fake_exit_edge || ei != ei_end)
         {
            TBB k1;
            Vertex b;
            if(do_fake_exit_edge)
            {
               k1 = dfs_order[last_basic_block];
               do_fake_exit_edge = false;
            }
            else
            {
               e = *ei;
               b = boost::source(e, g);
               einext = ei;
               einext++;

               if(b == en_block)
               {
                  k1 = dfs_order[last_basic_block];
               }
               else
               {
                  k1 = dfs_order[index_map[b]];
               }
            }
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
                           "---Predecessor is " + std::to_string(k1) + " v_" + std::to_string(index_map[b]));
            /* Call eval() only if really needed.  If k1 is above V in DFS tree,
            then we know, that eval(k1) == k1 and key[k1] == k1.  */
            // k1 is the dfs index of the predecessor, v is the dfs of this Vertex
            if(k1 > v)
            {
               k1 = key[eval(k1)];
            }
            if(k1 < k)
            {
               k = k1;
            }

            ei = einext;
         }

         INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---Key is " + std::to_string(k));

         // k becomes the key for v, so we have to add v to the bucket of k. It becomes the first element because we are
         // reverse counting v
         key[v] = k;
         link_roots(par, v);
         next_bucket[v] = bucket[k];
         bucket[k] = v;

         /* Transform semidominators into dominators.  */
         for(w = bucket[par]; w; w = next_bucket[w])
         {
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---w is " + std::to_string(w));
            k = eval(w);
            if(key[k] < key[w])
            {
               dom[w] = k;
            }
            else
            {
               dom[w] = par;
            }
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "---dom[w] is " + std::to_string(dom[w]));
         }
         /* We don't need to cleanup next_bucket[].  */
         bucket[par] = 0;
         INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Analyzed node in position " + std::to_string(v));
         v--;
      }

      /* Explicitly define the dominators.  */
      for(v = 1; v <= nodes; v++)
      {
         if(dom[v] != key[v])
         {
            dom[v] = dom[dom[v]];
         }
      }
      INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Computed immediate dominators");
   }

   void fill_dom_map(CustomUnorderedMapStable<Vertex, Vertex>& dom_map)
   {
      Vertex_iterator vi, vi_end;
      dom_map[en_block] = en_block;
      for(boost::tie(vi, vi_end) = boost::vertices(g); vi != vi_end; vi++)
      {
         TBB d = dom[dfs_order[index_map[*vi]]];
         if(dfs_to_bb[d] != boost::graph_traits<GraphObj>::null_vertex())
         {
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level,
                           "---dom is " + std::to_string(index_map[dfs_to_bb[d]]));
            dom_map[*vi] = dfs_to_bb[d];
         }
      }
   }
};

template <typename GraphObj>
class dominance
{
 public:
   enum cdi_direction
   {
      CDI_DOMINATORS,
      CDI_POST_DOMINATORS,
      CDI_NONE
   };
   enum dom_state
   {
      DOM_NONE,          
      DOM_NO_FAST_QUERY, 
      DOM_OK             
   };

 private:
   friend class loop_regions_computation;
   friend class add_loop_nop;

   using Vertex = typename boost::graph_traits<const GraphObj>::vertex_descriptor;

   using Vertex_iterator = typename boost::graph_traits<const GraphObj>::vertex_iterator;

   enum cdi_direction dom_dir;

   enum dom_state dom_computed;

   const GraphObj& g;

   const Vertex en_block;
   const Vertex ex_block;

   CustomUnorderedMapStable<Vertex, Vertex> dom;

   const ParameterConstRef param;

   int debug_level;

 public:
   dominance(const dominance<GraphObj>&) = delete;

   dominance<GraphObj> operator=(const dominance<GraphObj>&) = delete;
   void calculate_dominance_info(enum dominance::cdi_direction dir)
   {
      if(dom_computed == DOM_OK)
      {
         return;
      }
      if(dom_computed == DOM_NONE)
      {
         bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
         if(reverse)
         {
            boost::reverse_graph<GraphObj, GraphObj> Rcfg(g);
            dom_info<boost::reverse_graph<GraphObj, GraphObj>> di(Rcfg, ex_block, en_block, param);
            di.calc_dfs_tree(reverse);
            di.calc_idoms(reverse);
            di.fill_dom_map(dom);
         }
         else
         {
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "-->Computing dominators");
            dom_info<GraphObj> di(g, en_block, ex_block, param);
            di.calc_dfs_tree(reverse);
            di.calc_idoms(reverse);
            di.fill_dom_map(dom);
            INDENT_DBG_MEX(DEBUG_LEVEL_VERY_PEDANTIC, debug_level, "<--Computed dominators");
         }
         dom_computed = DOM_NO_FAST_QUERY;
      }
      // compute_dom_fast_query (dir);
   }
   dominance(const GraphObj& _g, const Vertex _en_block, const Vertex _ex_block, const ParameterConstRef _param)
       : dom_dir(CDI_NONE),
         dom_computed(DOM_NONE),
         g(_g),
         en_block(_en_block),
         ex_block(_ex_block),
         param(_param),
         debug_level(_param->get_class_debug_level(GET_CLASS(*this), DEBUG_LEVEL_NONE))
   {
      THROW_ASSERT(_en_block != _ex_block, "incorrect entry and exit basic blocks");
   }
   Vertex get_immediate_dominator(Vertex v) const
   {
      return dom.find(v)->second;
   }

   const CustomUnorderedMapStable<Vertex, CustomOrderedSet<Vertex>> getAllDominated() const
   {
      CustomUnorderedMapStable<Vertex, CustomOrderedSet<Vertex>> dominated;
      // These are the immediate dominated nodes
      auto dom_it_end = dom.end();
      for(auto dom_it = dom.begin(); dom_it != dom_it_end; ++dom_it)
      {
         dominated[dom_it->second].insert(dom_it->first);
         dominated[dom_it->first].insert(dom_it->first);
      }

      // Now I have to consider also the non immediate dominators
      bool changed = false;
      do
      {
         changed = false;
         // for(domBeg = this->dom.begin(), domEnd = this->dom.end(); domBeg != domEnd; domBeg++)
         for(auto dom_it = dom.begin(); dom_it != dom_it_end; ++dom_it)
         {
            using mSetIter = typename CustomUnorderedMapStable<Vertex, CustomOrderedSet<Vertex>>::iterator;
            mSetIter mSetBeg, mSetEnd;
            for(mSetBeg = dominated.begin(), mSetEnd = dominated.end(); mSetBeg != mSetEnd; ++mSetBeg)
            {
               if((mSetBeg->second).find(dom_it->second) != (mSetBeg->second).end() &&
                  (mSetBeg->second).find(dom_it->first) == (mSetBeg->second).end())
               {
                  dominated[mSetBeg->first].insert(dom_it->first);
                  changed = true;
               }
            }
         }
      } while(changed);

      return dominated;
   }

   const CustomUnorderedMapStable<Vertex, Vertex>& get_dominator_map() const
   {
      return dom;
   }
};
#endif