<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    Loop peeling and unrolling
 * @author   <NAME>
 * @version  $Id$
 */
#include "config.h"

#include "irnode.h"
#include "debug.h"

#include "ircons.h"
#include "irgopt.h"
#include "irgmod.h"
#include "irgwalk.h"
#include "irouts.h"
#include "iredges.h"
#include "irtools.h"
#include "array_t.h"	/* automatic array */
#include "beutil.h"		/* get_block */
#include "irloop_t.h"	/* set_irn_loop */

// TODO during DBG
//#include "irnode_t.h"
#include "irdump.h"

DEBUG_ONLY(static firm_dbg_module_t *dbg);

/**
 * Convenience macro for iterating over every phi node of the given block.
 * Requires phi list per block.
 */
#define for_each_phi(block, phi) \
	for ( (phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next( (phi) ) )

/* current loop */
static ir_loop *cur_loop;

/* The loop walker should be possible to abort if nothing can be done anymore */
typedef unsigned irg_walk_func_abortable(ir_node *, void *);

/* condition for breaking a copy_walk */
typedef unsigned walker_condition(ir_node *);

/* stores node and position of a predecessor */
typedef struct out_edges {
	ir_node *node;
	int pred_irn_n;
} out_edges;

/* access complex values through the nodes links */
typedef struct node_info {
	unsigned invariant:1;
	ir_node *copy;
	ir_node *link;					/* temporary links for ssa creation */
	ir_node **ins;					/* ins for phi nodes, during rewiring of blocks */
	struct node_info *freelistnext; /* linked list to free all node_infos */
} node_info;

static node_info *link_node_state_list;		/* head of the linked list to free all node_infos */

static out_edges *cur_loop_outs;				/* A walker may start visiting the current loop with these nodes. */
static out_edges *cur_head_outs;				/* A walker may start visiting the cur head with these nodes. */

static ir_node *loop_cf_head = NULL;				/* Loop head node */
static unsigned loop_cf_head_valid = 1;				/* A loop may have one head, otherwise we do not touch it. */

/* Inverted head */
static ir_node *loop_inv_head = NULL;
/* Peeled head */
static ir_node *loop_peeled_head = NULL;

/* Loop analysis informations */
typedef struct loop_info_t {
	unsigned calls;
	unsigned loads;
	unsigned invariant_loads;	/* number of load nodes */
	unsigned stores;			/* number of store nodes */
	unsigned blocks;			/* number of blocks in the loop */
	unsigned opnodes_n;			/* nodes that should result in an instruction */
	unsigned opnodes_head;
} loop_info_t;

/* Information about the current loop */
static loop_info_t loop_info;

/* A walker may start visiting a condition chain with these nodes. */
static out_edges *cond_chain_entries;

static unsigned head_inversion_node_count;
static unsigned head_inversion_node_limit;
static unsigned head_inversion_block_count;

/**
 *
 * ============= AUXILIARY FUNCTIONS =====================================
 */

/**
 * Creates object on the heap, and adds it to a linked list to free it later.
 */
static node_info *new_node_info(void) {
	node_info *l = XMALLOCZ(node_info);
	l->freelistnext = link_node_state_list;
	link_node_state_list = l;
	l->copy = NULL;
	l->invariant = 0;
	return l;
}

static node_info *get_node_info(ir_node *n)
{
	return ((node_info *)get_irn_link(n));
}

/* Allocates a node_info struct for the given node. For use with a walker. */
static void alloc_node_info(ir_node *node, void *env)
{
	node_info *state = new_node_info();
	(void) env;
	set_irn_link(node, (void *)state);
}

static void free_node_info(void)
{
	node_info *next;
	next = link_node_state_list;
	while(next->freelistnext) {
		node_info *cur = next;
		next = cur->freelistnext;
		xfree( cur );
	}
}

/**
 * Use the linked list to reset the reused values of all node_infos
 * Reset in particular the copy attribute as copy_walk uses it to determine a present copy
 */
static void reset_node_infos(void)
{
	node_info *next;
	next = link_node_state_list;
	while(next->freelistnext) {
		node_info *cur = next;
		next = cur->freelistnext;
		cur->copy = NULL;
		cur->ins = NULL;
		cur->link = NULL;
	}
}

/* Returns the  */
static ir_node *get_copy(ir_node *n)
{
	return ((node_info *)get_irn_link(n))->copy;
}

/* Links the node to its copy */
static void set_copy(ir_node *n, ir_node *copy)
{
	((node_info *)get_irn_link(n) )->copy = copy;
}

/* Returns 0 if the node or block is not in cur_loop */
static unsigned is_in_loop(ir_node *node)
{
	return (get_irn_loop(get_block(node)) == cur_loop);
}

/* Returns if the given be is an alien edge. This is the case when the pred is not in the loop. */
static unsigned is_alien_edge(ir_node *n, int i)
{
	return(!is_in_loop(get_irn_n(n, i)));
}

/* used for walker */
static void unmark_block(ir_node *node, void * env)
{
	(void) env;
	DB((dbg, LEVEL_4, "UNMARK ..."));
	DB((dbg, LEVEL_4, " UNMARK %ld\n", get_irn_node_nr(node)));
	if(is_Block(node))
		set_Block_mark(node, 0);
}

static unsigned is_nodesblock_marked(ir_node* node)
{
	return (get_Block_mark(get_block(node)));
}

/* Returns the number of blocks in a loop. */
int get_loop_n_blocks(ir_loop *loop) {
	int elements, e;
	int blocks = 0;
	elements = get_loop_n_elements(loop);

	for(e=0; e<elements; e++) {
		loop_element elem = get_loop_element(loop, e);
		if  (is_ir_node(elem.kind) && is_Block(elem.node) )
			++blocks;
	}
	return blocks;
}

/**
 * Add newpred at position pos to node and also add the corresponding value to the phis.
 * Requires block phi list.
 */
static void duplicate_preds(ir_node* node, unsigned pos, ir_node* newpred)
{
	ir_node** ins;
	ir_node *phi;
	int block_arity;
	int i;

	assert(is_Block(node) && "duplicate_preds is only allowed for blocks");

	DB((dbg, LEVEL_4, "duplicate_preds(node %ld, pos %d, newpred %ld)\n", get_irn_node_nr(node), pos, get_irn_node_nr(newpred)));

	block_arity = get_irn_arity(node);

	NEW_ARR_A(ir_node*, ins, block_arity + 1 );
	for (i = 0; i < block_arity; ++i)
		ins[i] = get_irn_n(node, i);
	ins[block_arity] = newpred;

	set_irn_in(node, block_arity + 1, ins);

	for_each_phi(node, phi) {
		int phi_arity = get_irn_arity(phi);
		DB((dbg, LEVEL_4, "duplicate_preds: fixing phi %ld\n", get_irn_node_nr(phi)));

		NEW_ARR_A(ir_node *, ins, block_arity + 1);
		for(i=0; i < phi_arity; ++i) {
			DB((dbg, LEVEL_4, "in %ld\n", get_irn_node_nr(get_irn_n(phi, i))));
			ins[i] = get_irn_n(phi, i);
		}
		ins[block_arity] = get_irn_n(phi, pos);
		set_irn_in(phi, block_arity + 1, ins);
	}
}

/* Adds all nodes pointing into the loop to loop_entries and also finds the loops head */
static void get_loop_outs_and_info(ir_node *node, void *env)
{
	unsigned node_in_loop, pred_in_loop;
	int i, arity;
	(void) env;

	arity = get_irn_arity(node);
	for (i = 0; i < arity; i++) {
		ir_node *pred = get_irn_n(node, i);

		pred_in_loop = is_in_loop(pred);
		node_in_loop = is_in_loop(node);

		/* collect some loop information */
		if (node_in_loop) {
			if ( !is_Store(node) )
				++loop_info.stores;
			if ( !is_Load(node) )
				++loop_info.loads;
			if ( !is_Call(node) )
				++loop_info.calls;
			if ( !is_Block(node) && !is_Proj(node) && !is_Phi(node) )
				++loop_info.opnodes_n;
		}

		//Find the loops head/the blocks with cfpred outside of the loop
		if (is_Block(node) && node_in_loop && !pred_in_loop && loop_cf_head_valid) {
			ir_node *cfgpred = get_Block_cfgpred(node, i);
			if ( !is_in_loop(cfgpred) ) {
				//DB((dbg, LEVEL_1, "potential head %+F\n", node));
				/* another head? We do not touch this. */<commit_msg>Fixed some obviously wrong conditions.<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    Loop peeling and unrolling
 * @author   <NAME>
 * @version  $Id$
 */
#include "config.h"

#include "irnode.h"
#include "debug.h"

#include "ircons.h"
#include "irgopt.h"
#include "irgmod.h"
#include "irgwalk.h"
#include "irouts.h"
#include "iredges.h"
#include "irtools.h"
#include "array_t.h"	/* automatic array */
#include "beutil.h"		/* get_block */
#include "irloop_t.h"	/* set_irn_loop */

// TODO during DBG
//#include "irnode_t.h"
#include "irdump.h"

DEBUG_ONLY(static firm_dbg_module_t *dbg);

/**
 * Convenience macro for iterating over every phi node of the given block.
 * Requires phi list per block.
 */
#define for_each_phi(block, phi) \
	for ( (phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next( (phi) ) )

/* current loop */
static ir_loop *cur_loop;

/* The loop walker should be possible to abort if nothing can be done anymore */
typedef unsigned irg_walk_func_abortable(ir_node *, void *);

/* condition for breaking a copy_walk */
typedef unsigned walker_condition(ir_node *);

/* stores node and position of a predecessor */
typedef struct out_edges {
	ir_node *node;
	int pred_irn_n;
} out_edges;

/* access complex values through the nodes links */
typedef struct node_info {
	unsigned invariant:1;
	ir_node *copy;
	ir_node *link;					/* temporary links for ssa creation */
	ir_node **ins;					/* ins for phi nodes, during rewiring of blocks */
	struct node_info *freelistnext; /* linked list to free all node_infos */
} node_info;

static node_info *link_node_state_list;		/* head of the linked list to free all node_infos */

static out_edges *cur_loop_outs;				/* A walker may start visiting the current loop with these nodes. */
static out_edges *cur_head_outs;				/* A walker may start visiting the cur head with these nodes. */

static ir_node *loop_cf_head = NULL;				/* Loop head node */
static unsigned loop_cf_head_valid = 1;				/* A loop may have one head, otherwise we do not touch it. */

/* Inverted head */
static ir_node *loop_inv_head = NULL;
/* Peeled head */
static ir_node *loop_peeled_head = NULL;

/* Loop analysis informations */
typedef struct loop_info_t {
	unsigned calls;
	unsigned loads;
	unsigned invariant_loads;	/* number of load nodes */
	unsigned stores;			/* number of store nodes */
	unsigned blocks;			/* number of blocks in the loop */
	unsigned opnodes_n;			/* nodes that should result in an instruction */
	unsigned opnodes_head;
} loop_info_t;

/* Information about the current loop */
static loop_info_t loop_info;

/* A walker may start visiting a condition chain with these nodes. */
static out_edges *cond_chain_entries;

static unsigned head_inversion_node_count;
static unsigned head_inversion_node_limit;
static unsigned head_inversion_block_count;

/**
 *
 * ============= AUXILIARY FUNCTIONS =====================================
 */

/**
 * Creates object on the heap, and adds it to a linked list to free it later.
 */
static node_info *new_node_info(void) {
	node_info *l = XMALLOCZ(node_info);
	l->freelistnext = link_node_state_list;
	link_node_state_list = l;
	l->copy = NULL;
	l->invariant = 0;
	return l;
}

static node_info *get_node_info(ir_node *n)
{
	return ((node_info *)get_irn_link(n));
}

/* Allocates a node_info struct for the given node. For use with a walker. */
static void alloc_node_info(ir_node *node, void *env)
{
	node_info *state = new_node_info();
	(void) env;
	set_irn_link(node, (void *)state);
}

static void free_node_info(void)
{
	node_info *next;
	next = link_node_state_list;
	while(next->freelistnext) {
		node_info *cur = next;
		next = cur->freelistnext;
		xfree( cur );
	}
}

/**
 * Use the linked list to reset the reused values of all node_infos
 * Reset in particular the copy attribute as copy_walk uses it to determine a present copy
 */
static void reset_node_infos(void)
{
	node_info *next;
	next = link_node_state_list;
	while(next->freelistnext) {
		node_info *cur = next;
		next = cur->freelistnext;
		cur->copy = NULL;
		cur->ins = NULL;
		cur->link = NULL;
	}
}

/* Returns the  */
static ir_node *get_copy(ir_node *n)
{
	return ((node_info *)get_irn_link(n))->copy;
}

/* Links the node to its copy */
static void set_copy(ir_node *n, ir_node *copy)
{
	((node_info *)get_irn_link(n) )->copy = copy;
}

/* Returns 0 if the node or block is not in cur_loop */
static unsigned is_in_loop(ir_node *node)
{
	return (get_irn_loop(get_block(node)) == cur_loop);
}

/* Returns if the given be is an alien edge. This is the case when the pred is not in the loop. */
static unsigned is_alien_edge(ir_node *n, int i)
{
	return(!is_in_loop(get_irn_n(n, i)));
}

/* used for walker */
static void unmark_block(ir_node *node, void * env)
{
	(void) env;
	DB((dbg, LEVEL_4, "UNMARK ..."));
	DB((dbg, LEVEL_4, " UNMARK %ld\n", get_irn_node_nr(node)));
	if(is_Block(node))
		set_Block_mark(node, 0);
}

static unsigned is_nodesblock_marked(ir_node* node)
{
	return (get_Block_mark(get_block(node)));
}

/* Returns the number of blocks in a loop. */
int get_loop_n_blocks(ir_loop *loop) {
	int elements, e;
	int blocks = 0;
	elements = get_loop_n_elements(loop);

	for(e=0; e<elements; e++) {
		loop_element elem = get_loop_element(loop, e);
		if  (is_ir_node(elem.kind) && is_Block(elem.node) )
			++blocks;
	}
	return blocks;
}

/**
 * Add newpred at position pos to node and also add the corresponding value to the phis.
 * Requires block phi list.
 */
static void duplicate_preds(ir_node* node, unsigned pos, ir_node* newpred)
{
	ir_node** ins;
	ir_node *phi;
	int block_arity;
	int i;

	assert(is_Block(node) && "duplicate_preds is only allowed for blocks");

	DB((dbg, LEVEL_4, "duplicate_preds(node %ld, pos %d, newpred %ld)\n", get_irn_node_nr(node), pos, get_irn_node_nr(newpred)));

	block_arity = get_irn_arity(node);

	NEW_ARR_A(ir_node*, ins, block_arity + 1 );
	for (i = 0; i < block_arity; ++i)
		ins[i] = get_irn_n(node, i);
	ins[block_arity] = newpred;

	set_irn_in(node, block_arity + 1, ins);

	for_each_phi(node, phi) {
		int phi_arity = get_irn_arity(phi);
		DB((dbg, LEVEL_4, "duplicate_preds: fixing phi %ld\n", get_irn_node_nr(phi)));

		NEW_ARR_A(ir_node *, ins, block_arity + 1);
		for(i=0; i < phi_arity; ++i) {
			DB((dbg, LEVEL_4, "in %ld\n", get_irn_node_nr(get_irn_n(phi, i))));
			ins[i] = get_irn_n(phi, i);
		}
		ins[block_arity] = get_irn_n(phi, pos);
		set_irn_in(phi, block_arity + 1, ins);
	}
}

/* Adds all nodes pointing into the loop to loop_entries and also finds the loops head */
static void get_loop_outs_and_info(ir_node *node, void *env)
{
	unsigned node_in_loop, pred_in_loop;
	int i, arity;
	(void) env;

	arity = get_irn_arity(node);
	for (i = 0; i < arity; i++) {
		ir_node *pred = get_irn_n(node, i);

		pred_in_loop = is_in_loop(pred);
		node_in_loop = is_in_loop(node);

		/* collect some loop information */
		if (node_in_loop) {
			if ( is_Store(node) )
				++loop_info.stores;
			if ( is_Load(node) )
				++loop_info.loads;
			if ( is_Call(node) )
				++loop_info.calls;
			if ( !is_Block(node) && !is_Proj(node) && !is_Phi(node) )
				++loop_info.opnodes_n;
		}

		//Find the loops head/the blocks with cfpred outside of the loop
		if (is_Block(node) && node_in_loop && !pred_in_loop && loop_cf_head_valid) {
			ir_node *cfgpred = get_Block_cfgpred(node, i);
			if ( !is_in_loop(cfgpred) ) {
				//DB((dbg, LEVEL_1, "potential head %+F\n", node));
				/* another head? We do not touch this. */
{'fraction_non_alphanumeric': 0.1262135922330097, 'fraction_numerical': 0.0035639670640285116, 'mean_word_length': 4.150316455696203, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 29, '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': '6221485', 'n_tokens_mistral': 6176, 'n_tokens_neox': 5895, 'n_words': 1776}