<commit_before>/*
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief       New approach to allocation and copy coalescing
 * @author      <NAME>
 * @date        14.2.2009
 * @version     $Id$
 *
 * ... WE NEED A NAME FOR THIS ...
 *
 * Only a proof of concept at this moment...
 *
 * The idea is to allocate registers in 2 passes:
 * 1. A first pass to determine "preferred" registers for live-ranges. This
 *    calculates for each register and each live-range a value indicating
 *    the usefulness. (You can roughly think of the value as the negative
 *    costs needed for copies when the value is in the specific registers...)
 *
 * 2. Walk blocks and assigns registers in a greedy fashion. Preferring
 *    registers with high preferences. When register constraints are not met,
 *    add copies and split live-ranges.
 *
 * TODO:
 *  - make use of free registers in the permute_values code
 *  - think about a smarter sequence of visiting the blocks. Sorted by
 *    execfreq might be good, or looptree from inner to outermost loops going
 *    over blocks in a reverse postorder
 *  - propagate preferences through Phis
 */
#include "config.h"

#include <float.h>
#include <stdbool.h>
#include <math.h>

#include "error.h"
#include "execfreq.h"
#include "ircons.h"
#include "irdom.h"
#include "iredges_t.h"
#include "irgraph_t.h"
#include "irgwalk.h"
#include "irnode_t.h"
#include "irprintf.h"
#include "obst.h"
#include "raw_bitset.h"
#include "unionfind.h"
#include "pdeq.h"
#include "hungarian.h"

#include "beabi.h"
#include "bechordal_t.h"
#include "be.h"
#include "beirg.h"
#include "belive_t.h"
#include "bemodule.h"
#include "benode_t.h"
#include "bera.h"
#include "besched.h"
#include "bespill.h"
#include "bespillutil.h"
#include "beverify.h"
#include "beutil.h"

#define USE_FACTOR                     1.0f
#define DEF_FACTOR                     1.0f
#define NEIGHBOR_FACTOR                0.2f
#define AFF_SHOULD_BE_SAME             0.5f
#define AFF_PHI                        1.0f
#define SPLIT_DELTA                    1.0f
#define MAX_OPTIMISTIC_SPLIT_RECURSION 0

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

static struct obstack               obst;
static be_irg_t                    *birg;
static ir_graph                    *irg;
static const arch_register_class_t *cls;
static const arch_register_req_t   *default_cls_req;
static be_lv_t                     *lv;
static const ir_exec_freq          *execfreqs;
static unsigned                     n_regs;
static unsigned                    *normal_regs;
static int                         *congruence_classes;
static ir_node                    **block_order;
static int                          n_block_order;
static bool                         create_preferences        = true;
static bool                         create_congruence_classes = true;
static bool                         propagate_phi_registers   = true;

static const lc_opt_table_entry_t options[] = {
	LC_OPT_ENT_BOOL("prefs", "use preference based coloring", &create_preferences),
	LC_OPT_ENT_BOOL("congruences", "create congruence classes", &create_congruence_classes),
	LC_OPT_ENT_BOOL("prop_phi", "propagate phi registers", &propagate_phi_registers),
	LC_OPT_LAST
};

/** currently active assignments (while processing a basic block)
 * maps registers to values(their current copies) */
static ir_node **assignments;

/**<commit_msg>libcore wants int, not bool.<commit_after>/*
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief       New approach to allocation and copy coalescing
 * @author      <NAME>
 * @date        14.2.2009
 * @version     $Id$
 *
 * ... WE NEED A NAME FOR THIS ...
 *
 * Only a proof of concept at this moment...
 *
 * The idea is to allocate registers in 2 passes:
 * 1. A first pass to determine "preferred" registers for live-ranges. This
 *    calculates for each register and each live-range a value indicating
 *    the usefulness. (You can roughly think of the value as the negative
 *    costs needed for copies when the value is in the specific registers...)
 *
 * 2. Walk blocks and assigns registers in a greedy fashion. Preferring
 *    registers with high preferences. When register constraints are not met,
 *    add copies and split live-ranges.
 *
 * TODO:
 *  - make use of free registers in the permute_values code
 *  - think about a smarter sequence of visiting the blocks. Sorted by
 *    execfreq might be good, or looptree from inner to outermost loops going
 *    over blocks in a reverse postorder
 *  - propagate preferences through Phis
 */
#include "config.h"

#include <float.h>
#include <stdbool.h>
#include <math.h>

#include "error.h"
#include "execfreq.h"
#include "ircons.h"
#include "irdom.h"
#include "iredges_t.h"
#include "irgraph_t.h"
#include "irgwalk.h"
#include "irnode_t.h"
#include "irprintf.h"
#include "obst.h"
#include "raw_bitset.h"
#include "unionfind.h"
#include "pdeq.h"
#include "hungarian.h"

#include "beabi.h"
#include "bechordal_t.h"
#include "be.h"
#include "beirg.h"
#include "belive_t.h"
#include "bemodule.h"
#include "benode_t.h"
#include "bera.h"
#include "besched.h"
#include "bespill.h"
#include "bespillutil.h"
#include "beverify.h"
#include "beutil.h"

#define USE_FACTOR                     1.0f
#define DEF_FACTOR                     1.0f
#define NEIGHBOR_FACTOR                0.2f
#define AFF_SHOULD_BE_SAME             0.5f
#define AFF_PHI                        1.0f
#define SPLIT_DELTA                    1.0f
#define MAX_OPTIMISTIC_SPLIT_RECURSION 0

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

static struct obstack               obst;
static be_irg_t                    *birg;
static ir_graph                    *irg;
static const arch_register_class_t *cls;
static const arch_register_req_t   *default_cls_req;
static be_lv_t                     *lv;
static const ir_exec_freq          *execfreqs;
static unsigned                     n_regs;
static unsigned                    *normal_regs;
static int                         *congruence_classes;
static ir_node                    **block_order;
static int                          n_block_order;
static int                          create_preferences        = true;
static int                          create_congruence_classes = true;
static int                          propagate_phi_registers   = true;

static const lc_opt_table_entry_t options[] = {
	LC_OPT_ENT_BOOL("prefs", "use preference based coloring", &create_preferences),
	LC_OPT_ENT_BOOL("congruences", "create congruence classes", &create_congruence_classes),
	LC_OPT_ENT_BOOL("prop_phi", "propagate phi registers", &propagate_phi_registers),
	LC_OPT_LAST
};

/** currently active assignments (while processing a basic block)
 * maps registers to values(their current copies) */
static ir_node **assignments;

/**
{'fraction_non_alphanumeric': 0.08262633714496495, 'fraction_numerical': 0.007869174966187139, 'mean_word_length': 2.8277647058823527, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '4467758', 'n_tokens_mistral': 2513, 'n_tokens_neox': 2430, 'n_words': 864}