<commit_before>//=======================================================================
// Copyright <NAME> 2011.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#include <boost/graph/dominator_tree.hpp>

#include "mtac/LoopAnalysis.hpp"
#include "mtac/GlobalOptimizations.hpp"
#include "mtac/ControlFlowGraph.hpp"

using namespace eddic;

typedef mtac::ControlFlowGraph::InternalControlFlowGraph G;
typedef mtac::ControlFlowGraph::BasicBlockInfo Vertex;
typedef boost::property_map<mtac::ControlFlowGraph::InternalControlFlowGraph, boost::vertex_index_t>::type IndexMap;
typedef boost::iterator_property_map<std::vector<Vertex>::iterator, IndexMap> PredMap;

struct dfs_visitor : public boost::default_dfs_visitor {
    G& graph;

    dfs_visitor(G& graph) : graph(graph) {}

    template<typename U>
    void discover_vertex(U u, const G& g){
        auto new_vertex = add_vertex(graph);
        graph[new_vertex].block = g[u].block;
    }
    
    template<typename E>
    void tree_edge(E e, const G& g){
        add_edge(boost::source(e, g), boost::target(e, g), graph); 
    }
};

void mtac::loop_analysis(std::shared_ptr<mtac::Program> program){
    for(auto& function : program->functions){
        auto graph = mtac::build_control_flow_graph(function);
        auto g = graph->get_graph();
        
        std::vector<Vertex> domTreePredVector = std::vector<Vertex>(boost::num_vertices(g), boost::graph_traits<G>::null_vertex());
        PredMap domTreePredMap = boost::make_iterator_property_map(domTreePredVector.begin(), boost::get(boost::vertex_index, g));

        boost::lengauer_tarjan_dominator_tree(g, boost::vertex(0, g), domTreePredMap);
        
        ControlFlowGraph::EdgeIterator it, end;
        for(boost::tie(it,end) = boost::edges(g); it != end; ++it){
            auto source = boost::source(*it, g);
            auto target = boost::target(*it, g);

            //A node dominates itself
            if(source == target){
                std::cout << "Found back edge" << std::endl;
            } else {
                if(boost::get(domTreePredMap, source) != boost::graph_traits<G>::null_vertex()){
                    auto dominator = boost::get(domTreePredMap,source);

                    if(dominator == target){
                        std::cout << "Found back edge" << std::endl;
                    }
                }
            }
        }

        /*G depth_first_tree;
        dfs_visitor visitor(depth_first_tree);

        boost::depth_first_search(g, boost::visitor(visitor));

        std::cout << "Dominators found" << std::endl;*/
    }
}<commit_msg>Go a bit further to loop analysis<commit_after>//=======================================================================
// Copyright <NAME> 2011.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#include <boost/graph/dominator_tree.hpp>

#include "mtac/LoopAnalysis.hpp"
#include "mtac/GlobalOptimizations.hpp"
#include "mtac/ControlFlowGraph.hpp"

using namespace eddic;

typedef mtac::ControlFlowGraph::InternalControlFlowGraph G;
typedef mtac::ControlFlowGraph::EdgeInfo Edge;
typedef mtac::ControlFlowGraph::BasicBlockInfo Vertex;
typedef boost::property_map<mtac::ControlFlowGraph::InternalControlFlowGraph, boost::vertex_index_t>::type IndexMap;
typedef boost::iterator_property_map<std::vector<Vertex>::iterator, IndexMap> PredMap;

void mtac::loop_analysis(std::shared_ptr<mtac::Program> program){
    for(auto& function : program->functions){
        auto graph = mtac::build_control_flow_graph(function);
        auto g = graph->get_graph();
        
        std::vector<Vertex> domTreePredVector = std::vector<Vertex>(boost::num_vertices(g), boost::graph_traits<G>::null_vertex());
        PredMap domTreePredMap = boost::make_iterator_property_map(domTreePredVector.begin(), boost::get(boost::vertex_index, g));

        boost::lengauer_tarjan_dominator_tree(g, boost::vertex(0, g), domTreePredMap);

        std::vector<Edge> back_edges;
        
        ControlFlowGraph::EdgeIterator it, end;
        for(boost::tie(it,end) = boost::edges(g); it != end; ++it){
            auto source = boost::source(*it, g);
            auto target = boost::target(*it, g);

            //A node dominates itself
            if(source == target){
                back_edges.push_back(*it);
            } else {
                if(boost::get(domTreePredMap, source) != boost::graph_traits<G>::null_vertex()){
                    auto dominator = boost::get(domTreePredMap,source);

                    if(dominator == target){
                        back_edges.push_back(*it);
                    }
                }
            }
        }

        std::vector<std::set<Vertex>> natural_loops;

        //Get all edges n -> d
        for(auto& back_edge : back_edges){
            std::set<Vertex> natural_loop;
            natural_loop.insert(boost::target(back_edge, g));

            //Add all predecessors of d in the set
            //
            
            natural_loops.push_back(natural_loop);
        }

        std::cout << "Found " << natural_loops.size() << " natural loops" << std::endl;
    }
}
{'fraction_non_alphanumeric': 0.18034281546316558, 'fraction_numerical': 0.0040116703136396795, 'mean_word_length': 3.2355212355212357, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '634280', 'n_tokens_mistral': 1633, 'n_tokens_neox': 1543, 'n_words': 299}