color.hh

Go to the documentation of this file.

#ifndef REGALLOC_COLOR_HH
# define REGALLOC_COLOR_HH

# include <vector>
# include <map>

# include <temp/fwd.hh>

# include <liveness/flowgraph.hh>
# include <liveness/interference-graph.hh>

// FIXME: should be libtarget.hh
# include <target/target.hh>

namespace regalloc
{
  class Color
  {
    // Shortand typedefs
  public:
    typedef liveness::InterferenceGraph InterferenceGraph;
    typedef liveness::interferencegraph_vertex_iter_type hnodes_iterator;

    typedef InterferenceGraph::vertex_descriptor  node_type;
    typedef misc::set<node_type>                  node_set_type;
    typedef std::list<node_type>                  node_list_type;

    typedef InterferenceGraph::move_type     move_type;
    typedef InterferenceGraph::move_set_type move_set_type;

    typedef std::vector<move_set_type> move_list_map_type;

    typedef std::vector<temp::Temp> color_map_type;

    typedef std::vector<node_type>  alias_map_type;

  public:
    Color(assem::ProcFrag& frag, const target::Cpu& cpu,
          const temp::TempMap& tempmap,
          bool coalesce_p = false, bool trace_p = false);
  public:
    // The color timer.
    const misc::timer& timer_get() const;
  protected:
    void import_nodes();

    void import_moves();

    void precolor();

    void priorities_compute();

    void degrees_compute();
    void add_edge(const node_type u, const node_type v);

    void make_work_list(const node_type n);

    void make_work_list();

    node_set_type adjacent(const node_type n) const;

    bool adjacent(const node_type a, const node_type b) const;

    move_set_type node_moves(const node_type n) const;

    bool move_related(const node_type n) const;

    bool coalesce_briggs_p(const node_type a, const node_type b) const;

    bool coalesce_george_p(const node_type a, const node_type b) const;

    void coalesce();

    void add_work_list(const node_type u);

  protected:
    node_type get_alias(const node_type a) const;

    void combine(const node_type u, const node_type v);

    void freeze_moves(const node_type u);

    void freeze();

    void select_spill();


    void simplify();

    void decrement_degree(node_type n);

    void enable_moves(node_type n);

    void enable_moves(const node_set_type& nodes);

    void assign_color(node_type n);

    void assign_colors();

  public:
    bool operator()();

  public:
    const temp::temp_set_type spilled_get() const;

    temp::TempMap tempmap_get() const;
  protected:
    void trace(const std::string& what, const node_type& n) const;

    void trace(const std::string& what, const move_type& m) const;

    void dump(std::ostream& ostr, const node_type& n) const;

    void dump(std::ostream& ostr, const node_set_type& s) const;

    void dump(std::ostream& ostr, const node_list_type& s) const;

    void dump(std::ostream& ostr, const move_type& s) const;

    void dump(std::ostream& ostr, const move_set_type& s) const;

    void dump(std::ostream& ostr) const;
  protected:
    InterferenceGraph ig_;

    const target::Cpu& cpu_;

    size_t nb_regs_;

    assem::ProcFrag& asm_proc_frag_;

    bool trace_p_;

    bool coalesce_p_;


    node_set_type precolored_;

    node_set_type initial_;

    node_set_type simplify_work_list_;

    node_set_type freeze_work_list_;

    node_set_type spill_work_list_;

    node_set_type spilled_nodes_;

    node_set_type coalesced_nodes_;

    node_set_type colored_nodes_;

    node_list_type select_stack_;


    move_set_type coalesced_moves_;

    move_set_type constrained_moves_;

    move_set_type frozen_moves_;

    move_set_type work_list_moves_;

    move_set_type active_moves_;


    std::vector<size_t> degree_;

    move_list_map_type move_list_;

    alias_map_type alias_;

    color_map_type color_;


    std::map<temp::Temp, int> temps_priority_;


  private:
    misc::timer timer_;
  };

} // namespace regalloc


# undef DO

#endif // !REGALLOC_COLOR_HH