loops.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 LOOPS_HPP
#define LOOPS_HPP

#include "config_HAVE_HOST_PROFILING_BUILT.hpp"

#include "custom_map.hpp" // for unordered_map
#include "custom_set.hpp" // for unordered_set
#include "graph.hpp"
#include "refcount.hpp"

#include <cstddef> // for size_t
#include <list>    // for list
#include <string>  // for string
#include <utility> // for pair
#include <vector>  // for vector

REF_FORWARD_DECL(BBGraph);
REF_FORWARD_DECL(FunctionBehavior);
CONSTREF_FORWARD_DECL(Loop);
REF_FORWARD_DECL(Loop);
CONSTREF_FORWARD_DECL(Parameter);
CONSTREF_FORWARD_DECL(ProfilingInformation);

// This class represents a loop forest for a given method.
// The loop forest is built by Tarjan algorithm and each loop
// is represented by a loop instance (see loop.h).
//
// The class allows a client to iterate on the loops in a method
// and provides a map from basic block to loop to know if a block
// belongs to a loop.
//
// If necessary it is possible to extend the class to navigate the
// hierarchy in an ordered way.
//
class Loops
{
 private:
   const FunctionBehaviorRef FB;

   const ParameterConstRef Param;

   int debug_level;

   CustomUnorderedMap<vertex, LoopRef> block_to_loop;

   std::list<LoopRef> modifiable_loops_list;
   std::list<LoopConstRef> const_loops_list;

   using vertex_pair = std::pair<vertex, vertex>;

   bool is_edge_in_list(CustomUnorderedSet<vertex_pair>& l, vertex source, vertex target);

   Loops() = delete;

   void DetectLoops();

   void DetectReducibleLoop(const BBGraphRef djg, CustomOrderedSet<vertex>& visited, LoopRef loop, vertex node,
                            vertex header);

   void DetectIrreducibleLoop(const BBGraphRef djg, unsigned int min_level, unsigned int max_level,
                              std::vector<std::list<vertex>>& level_vertices_rel);

   void tarjan_scc(const BBGraphRef djg, vertex v, CustomUnorderedMap<vertex, unsigned int>& dfs_order,
                   CustomUnorderedMap<vertex, unsigned int>& lowlink, std::list<vertex>& s, CustomOrderedSet<vertex>& u,
                   unsigned int& max_dfs);

   bool stack_contains(std::list<vertex> stack, vertex v);

   void BuildZeroLoop();

   void computeDepth(const LoopConstRef loop);

 public:
   Loops(const FunctionBehaviorRef FB, const ParameterConstRef parameter);

   size_t NumLoops() const;

   const std::list<LoopConstRef>& GetList() const;

   const std::list<LoopRef>& GetModifiableList() const;

   const LoopConstRef CGetLoop(unsigned int id) const;

   const LoopRef GetLoop(unsigned int id);

   void WriteDot(const std::string& file_name
#if HAVE_HOST_PROFILING_BUILT
                 ,
                 const ProfilingInformationConstRef profiling_information = ProfilingInformationConstRef()
#endif
   ) const;
};

#endif // LOOPS_HPP