/* Induction variable optimizations.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
- Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Free Software Foundation, Inc.
This file is part of GCC.
/* Cost of a computation. */
typedef struct
{
- unsigned cost; /* The runtime cost. */
+ int cost; /* The runtime cost. */
unsigned complexity; /* The estimate of the complexity of the code for
the computation (in no concrete units --
complexity field should be larger for more
{
IP_NORMAL, /* At the end, just before the exit condition. */
IP_END, /* At the end of the latch block. */
+ IP_BEFORE_USE, /* Immediately before a specific use. */
+ IP_AFTER_USE, /* Immediately after a specific use. */
IP_ORIGINAL /* The original biv. */
};
to replace the final value of an iv by direct
computation of the value. */
unsigned cost; /* Cost of the candidate. */
+ unsigned cost_step; /* Cost of the candidate's increment operation. */
+ struct iv_use *ainc_use; /* For IP_{BEFORE,AFTER}_USE candidates, the place
+ where it is incremented. */
bitmap depends_on; /* The list of invariants that are used in step of the
biv. */
};
/* The currently optimized loop. */
struct loop *current_loop;
- /* Number of registers used in it. */
- unsigned regs_used;
-
/* Numbers of iterations for all exits of the current loop. */
struct pointer_map_t *niters;
+ /* Number of registers used in it. */
+ unsigned regs_used;
+
/* The size of version_info array allocated. */
unsigned version_info_size;
/* The bitmap of indices in version_info whose value was changed. */
bitmap relevant;
- /* The maximum invariant id. */
- unsigned max_inv_id;
-
/* The uses of induction variables. */
VEC(iv_use_p,heap) *iv_uses;
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* The maximum invariant id. */
+ unsigned max_inv_id;
+
/* Whether to consider just related and important candidates when replacing a
use. */
bool consider_all_candidates;
+
+ /* Are we optimizing for speed? */
+ bool speed;
};
/* An assignment of iv candidates to uses. */
fprintf (file, " incremented before exit test\n");
break;
+ case IP_BEFORE_USE:
+ fprintf (file, " incremented before use %d\n", cand->ainc_use->id);
+ break;
+
+ case IP_AFTER_USE:
+ fprintf (file, " incremented after use %d\n", cand->ainc_use->id);
+ break;
+
case IP_END:
fprintf (file, " incremented at end\n");
break;
}
/* Returns true if STMT if after the place where the original induction
- variable CAND is incremented. */
+ variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
+ if the positions are identical. */
static bool
-stmt_after_ip_original_pos (struct iv_cand *cand, gimple stmt)
+stmt_after_inc_pos (struct iv_cand *cand, gimple stmt, bool true_if_equal)
{
basic_block cand_bb = gimple_bb (cand->incremented_at);
basic_block stmt_bb = gimple_bb (stmt);
- gimple_stmt_iterator bsi;
if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
return false;
if (stmt_bb != cand_bb)
return true;
- /* Scan the block from the end, since the original ivs are usually
- incremented at the end of the loop body. */
- for (bsi = gsi_last_bb (stmt_bb); ; gsi_prev (&bsi))
- {
- if (gsi_stmt (bsi) == cand->incremented_at)
- return false;
- if (gsi_stmt (bsi) == stmt)
- return true;
- }
+ if (true_if_equal
+ && gimple_uid (stmt) == gimple_uid (cand->incremented_at))
+ return true;
+ return gimple_uid (stmt) > gimple_uid (cand->incremented_at);
}
/* Returns true if STMT if after the place where the induction variable
return stmt_after_ip_normal_pos (loop, stmt);
case IP_ORIGINAL:
- return stmt_after_ip_original_pos (cand, stmt);
+ case IP_AFTER_USE:
+ return stmt_after_inc_pos (cand, stmt, false);
+
+ case IP_BEFORE_USE:
+ return stmt_after_inc_pos (cand, stmt, true);
default:
gcc_unreachable ();
idx_contains_abnormal_ssa_name_p (tree base, tree *index,
void *data ATTRIBUTE_UNUSED)
{
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
if (abnormal_ssa_name_p (TREE_OPERAND (base, 2)))
return false;
if (!is_gimple_reg (name))
return NULL_TREE;
- if (!simple_iv (loop, phi, name, &iv, true))
+ if (!simple_iv (loop, loop, name, &iv, true))
return NULL_TREE;
return integer_zerop (iv.step) ? NULL_TREE : iv.step;
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, lhs, iv, true))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
return false;
iv->base = expand_simple_operations (iv->base);
reference out of the loop (in order to take its address in strength
reduction). In order for this to work we need both lower bound
and step to be loop invariants. */
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
+ /* Moreover, for a range, the size needs to be invariant as well. */
+ if (TREE_CODE (base) == ARRAY_RANGE_REF
+ && !expr_invariant_in_loop_p (loop, TYPE_SIZE (TREE_TYPE (base))))
+ return false;
+
step = array_ref_element_size (base);
lbound = array_ref_low_bound (base);
if (integer_zerop (iv->step))
return true;
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
step = array_ref_element_size (base);
{
struct ivopts_data *data = (struct ivopts_data *) vdata;
find_interesting_uses_op (data, *idx);
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
find_interesting_uses_op (data, array_ref_element_size (base));
find_interesting_uses_op (data, array_ref_low_bound (base));
non-addressability may be uncovered again, causing ADDR_EXPRs
of inappropriate objects to be built. */
if (is_gimple_reg (TREE_OPERAND (expr, 0))
- || is_gimple_min_invariant (TREE_OPERAND (expr, 0)))
+ || !is_gimple_addressable (TREE_OPERAND (expr, 0)))
return true;
/* ... fall through ... */
for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
find_interesting_uses_stmt (data, gsi_stmt (bsi));
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
- find_interesting_uses_stmt (data, gsi_stmt (bsi));
+ if (!is_gimple_debug (gsi_stmt (bsi)))
+ find_interesting_uses_stmt (data, gsi_stmt (bsi));
}
if (dump_file && (dump_flags & TDF_DETAILS))
return fold_convert (orig_type, expr);
+ case MULT_EXPR:
+ op1 = TREE_OPERAND (expr, 1);
+ if (!cst_and_fits_in_hwi (op1))
+ return orig_expr;
+
+ op0 = TREE_OPERAND (expr, 0);
+ op0 = strip_offset_1 (op0, false, false, &off0);
+ if (op0 == TREE_OPERAND (expr, 0))
+ return orig_expr;
+
+ *offset = off0 * int_cst_value (op1);
+ if (integer_zerop (op0))
+ expr = op0;
+ else
+ expr = fold_build2 (MULT_EXPR, type, op0, op1);
+
+ return fold_convert (orig_type, expr);
+
case ARRAY_REF:
+ case ARRAY_RANGE_REF:
if (!inside_addr)
return orig_expr;
{
orig_type = TREE_TYPE (base);
type = generic_type_for (orig_type);
- /* Don't convert the base to the generic type for pointers as the generic
- type is an integer type with the same size as the pointer type. */
- if (type != orig_type && !POINTER_TYPE_P (orig_type))
+ if (type != orig_type)
{
base = fold_convert (type, base);
step = fold_convert (type, step);
if (cand->pos != pos)
continue;
- if (cand->incremented_at != incremented_at)
+ if (cand->incremented_at != incremented_at
+ || ((pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
+ && cand->ainc_use != use))
continue;
if (!cand->iv)
walk_tree (&step, find_depends, &cand->depends_on, NULL);
}
+ if (pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
+ cand->ainc_use = use;
+ else
+ cand->ainc_use = NULL;
+
if (dump_file && (dump_flags & TDF_DETAILS))
dump_cand (dump_file, cand);
}
return false;
}
+/* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
+ Important field is set to IMPORTANT. */
+
+static void
+add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
+ bool important, struct iv_use *use)
+{
+ basic_block use_bb = gimple_bb (use->stmt);
+ enum machine_mode mem_mode;
+ unsigned HOST_WIDE_INT cstepi;
+
+ /* If we insert the increment in any position other than the standard
+ ones, we must ensure that it is incremented once per iteration.
+ It must not be in an inner nested loop, or one side of an if
+ statement. */
+ if (use_bb->loop_father != data->current_loop
+ || !dominated_by_p (CDI_DOMINATORS, data->current_loop->latch, use_bb)
+ || stmt_could_throw_p (use->stmt)
+ || !cst_and_fits_in_hwi (step))
+ return;
+
+ cstepi = int_cst_value (step);
+
+ mem_mode = TYPE_MODE (TREE_TYPE (*use->op_p));
+ if ((HAVE_PRE_INCREMENT && GET_MODE_SIZE (mem_mode) == cstepi)
+ || (HAVE_PRE_DECREMENT && GET_MODE_SIZE (mem_mode) == -cstepi))
+ {
+ enum tree_code code = MINUS_EXPR;
+ tree new_base;
+ tree new_step = step;
+
+ if (POINTER_TYPE_P (TREE_TYPE (base)))
+ {
+ new_step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
+ code = POINTER_PLUS_EXPR;
+ }
+ else
+ new_step = fold_convert (TREE_TYPE (base), new_step);
+ new_base = fold_build2 (code, TREE_TYPE (base), base, new_step);
+ add_candidate_1 (data, new_base, step, important, IP_BEFORE_USE, use,
+ use->stmt);
+ }
+ if ((HAVE_POST_INCREMENT && GET_MODE_SIZE (mem_mode) == cstepi)
+ || (HAVE_POST_DECREMENT && GET_MODE_SIZE (mem_mode) == -cstepi))
+ {
+ add_candidate_1 (data, base, step, important, IP_AFTER_USE, use,
+ use->stmt);
+ }
+}
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. The candidate computation is scheduled on all available positions. */
if (ip_end_pos (data->current_loop)
&& allow_ip_end_pos_p (data->current_loop))
add_candidate_1 (data, base, step, important, IP_END, use, NULL);
+
+ if (use != NULL && use->type == USE_ADDRESS)
+ add_autoinc_candidates (data, base, step, important, use);
}
/* Add a standard "0 + 1 * iteration" iv candidate for a
add_candidate (data, iv->base, iv->step, true, NULL);
/* The same, but with initial value zero. */
- add_candidate (data,
- build_int_cst (TREE_TYPE (iv->base), 0),
- iv->step, true, NULL);
+ if (POINTER_TYPE_P (TREE_TYPE (iv->base)))
+ add_candidate (data, size_int (0), iv->step, true, NULL);
+ else
+ add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0),
+ iv->step, true, NULL);
phi = SSA_NAME_DEF_STMT (iv->ssa_name);
if (gimple_code (phi) == GIMPLE_PHI)
}
}
-/* Finds the candidates for the induction variables. */
-
-static void
-find_iv_candidates (struct ivopts_data *data)
-{
- /* Add commonly used ivs. */
- add_standard_iv_candidates (data);
-
- /* Add old induction variables. */
- add_old_ivs_candidates (data);
-
- /* Add induction variables derived from uses. */
- add_derived_ivs_candidates (data);
-
- /* Record the important candidates. */
- record_important_candidates (data);
-}
-
/* Allocates the data structure mapping the (use, candidate) pairs to costs.
If consider_all_candidates is true, we use a two-dimensional array, otherwise
we allocate a simple list to every use. */
/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
on invariants DEPENDS_ON and that the value used in expressing it
- is VALUE.*/
+ is VALUE. */
static void
set_use_iv_cost (struct ivopts_data *data,
/* Returns estimate on cost of computing SEQ. */
static unsigned
-seq_cost (rtx seq)
+seq_cost (rtx seq, bool speed)
{
unsigned cost = 0;
rtx set;
{
set = single_set (seq);
if (set)
- cost += rtx_cost (set, SET);
+ cost += rtx_cost (set, SET,speed);
else
cost++;
}
/* Determines cost of the computation of EXPR. */
static unsigned
-computation_cost (tree expr)
+computation_cost (tree expr, bool speed)
{
rtx seq, rslt;
tree type = TREE_TYPE (expr);
unsigned cost;
/* Avoid using hard regs in ways which may be unsupported. */
int regno = LAST_VIRTUAL_REGISTER + 1;
+ enum function_frequency real_frequency = cfun->function_frequency;
+ cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
+ crtl->maybe_hot_insn_p = speed;
walk_tree (&expr, prepare_decl_rtl, ®no, NULL);
start_sequence ();
rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL);
seq = get_insns ();
end_sequence ();
+ default_rtl_profile ();
+ cfun->function_frequency = real_frequency;
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (MEM_P (rslt))
- cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type));
+ cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type), speed);
return cost;
}
/* Returns cost of addition in MODE. */
static unsigned
-add_cost (enum machine_mode mode)
+add_cost (enum machine_mode mode, bool speed)
{
static unsigned costs[NUM_MACHINE_MODES];
rtx seq;
seq = get_insns ();
end_sequence ();
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (!cost)
cost = 1;
/* Returns cost of multiplication by constant CST in MODE. */
unsigned
-multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode)
+multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode, bool speed)
{
static htab_t costs;
struct mbc_entry **cached, act;
seq = get_insns ();
end_sequence ();
- cost = seq_cost (seq);
+ cost = seq_cost (seq, speed);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
variable is omitted. Compute the cost for a memory reference that accesses
a memory location of mode MEM_MODE.
+ MAY_AUTOINC is set to true if the autoincrement (increasing index by
+ size of MEM_MODE / RATIO) is available. To make this determination, we
+ look at the size of the increment to be made, which is given in CSTEP.
+ CSTEP may be zero if the step is unknown.
+ STMT_AFTER_INC is true iff the statement we're looking at is after the
+ increment of the original biv.
+
TODO -- there must be some better way. This all is quite crude. */
static comp_cost
get_address_cost (bool symbol_present, bool var_present,
unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
- enum machine_mode mem_mode)
+ HOST_WIDE_INT cstep, enum machine_mode mem_mode, bool speed,
+ bool stmt_after_inc, bool *may_autoinc)
{
static bool initialized[MAX_MACHINE_MODE];
static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
+ static bool has_preinc[MAX_MACHINE_MODE], has_postinc[MAX_MACHINE_MODE];
+ static bool has_predec[MAX_MACHINE_MODE], has_postdec[MAX_MACHINE_MODE];
unsigned cost, acost, complexity;
- bool offset_p, ratio_p;
- HOST_WIDE_INT s_offset;
+ bool offset_p, ratio_p, autoinc;
+ HOST_WIDE_INT s_offset, autoinc_offset, msize;
unsigned HOST_WIDE_INT mask;
unsigned bits;
reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
+ if (HAVE_PRE_DECREMENT)
+ {
+ addr = gen_rtx_PRE_DEC (Pmode, reg0);
+ has_predec[mem_mode] = memory_address_p (mem_mode, addr);
+ }
+ if (HAVE_POST_DECREMENT)
+ {
+ addr = gen_rtx_POST_DEC (Pmode, reg0);
+ has_postdec[mem_mode] = memory_address_p (mem_mode, addr);
+ }
+ if (HAVE_PRE_INCREMENT)
+ {
+ addr = gen_rtx_PRE_INC (Pmode, reg0);
+ has_preinc[mem_mode] = memory_address_p (mem_mode, addr);
+ }
+ if (HAVE_POST_INCREMENT)
+ {
+ addr = gen_rtx_POST_INC (Pmode, reg0);
+ has_postinc[mem_mode] = memory_address_p (mem_mode, addr);
+ }
for (i = 0; i < 16; i++)
{
sym_p = i & 1;
if (base)
addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
-
+
start_sequence ();
/* To avoid splitting addressing modes, pretend that no cse will
follow. */
seq = get_insns ();
end_sequence ();
- acost = seq_cost (seq);
- acost += address_cost (addr, mem_mode);
+ acost = seq_cost (seq, speed);
+ acost += address_cost (addr, mem_mode, speed);
if (!acost)
acost = 1;
If VAR_PRESENT is true, try whether the mode with
SYMBOL_PRESENT = false is cheaper even with cost of addition, and
if this is the case, use it. */
- add_c = add_cost (Pmode);
+ add_c = add_cost (Pmode, speed);
for (i = 0; i < 8; i++)
{
var_p = i & 1;
if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
costs[mem_mode][1][var_p][off_p][rat_p] = acost;
}
-
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Address costs:\n");
acost = costs[mem_mode][sym_p][var_p][off_p][rat_p];
fprintf (dump_file, "index costs %d\n", acost);
}
+ if (has_predec[mem_mode] || has_postdec[mem_mode]
+ || has_preinc[mem_mode] || has_postinc[mem_mode])
+ fprintf (dump_file, " May include autoinc/dec\n");
fprintf (dump_file, "\n");
}
}
offset |= ~mask;
s_offset = offset;
+ autoinc = false;
+ msize = GET_MODE_SIZE (mem_mode);
+ autoinc_offset = offset;
+ if (stmt_after_inc)
+ autoinc_offset += ratio * cstep;
+ if (symbol_present || var_present || ratio != 1)
+ autoinc = false;
+ else if ((has_postinc[mem_mode] && autoinc_offset == 0
+ && msize == cstep)
+ || (has_postdec[mem_mode] && autoinc_offset == 0
+ && msize == -cstep)
+ || (has_preinc[mem_mode] && autoinc_offset == msize
+ && msize == cstep)
+ || (has_predec[mem_mode] && autoinc_offset == -msize
+ && msize == -cstep))
+ autoinc = true;
+
cost = 0;
offset_p = (s_offset != 0
&& min_offset[mem_mode] <= s_offset
&& multiplier_allowed_in_address_p (ratio, mem_mode));
if (ratio != 1 && !ratio_p)
- cost += multiply_by_cost (ratio, Pmode);
+ cost += multiply_by_cost (ratio, Pmode, speed);
if (s_offset && !offset_p && !symbol_present)
- cost += add_cost (Pmode);
+ cost += add_cost (Pmode, speed);
+ if (may_autoinc)
+ *may_autoinc = autoinc;
acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
return new_cost (cost + acost, complexity);
/* Estimates cost of forcing expression EXPR into a variable. */
static comp_cost
-force_expr_to_var_cost (tree expr)
+force_expr_to_var_cost (tree expr, bool speed)
{
static bool costs_initialized = false;
- static unsigned integer_cost;
- static unsigned symbol_cost;
- static unsigned address_cost;
+ static unsigned integer_cost [2];
+ static unsigned symbol_cost [2];
+ static unsigned address_cost [2];
tree op0, op1;
comp_cost cost0, cost1, cost;
enum machine_mode mode;
tree type = build_pointer_type (integer_type_node);
tree var, addr;
rtx x;
+ int i;
var = create_tmp_var_raw (integer_type_node, "test_var");
TREE_STATIC (var) = 1;
x = produce_memory_decl_rtl (var, NULL);
SET_DECL_RTL (var, x);
- integer_cost = computation_cost (build_int_cst (integer_type_node,
- 2000));
-
addr = build1 (ADDR_EXPR, type, var);
- symbol_cost = computation_cost (addr) + 1;
- address_cost
- = computation_cost (build2 (POINTER_PLUS_EXPR, type,
- addr,
- build_int_cst (sizetype, 2000))) + 1;
- if (dump_file && (dump_flags & TDF_DETAILS))
+
+ for (i = 0; i < 2; i++)
{
- fprintf (dump_file, "force_expr_to_var_cost:\n");
- fprintf (dump_file, " integer %d\n", (int) integer_cost);
- fprintf (dump_file, " symbol %d\n", (int) symbol_cost);
- fprintf (dump_file, " address %d\n", (int) address_cost);
- fprintf (dump_file, " other %d\n", (int) target_spill_cost);
- fprintf (dump_file, "\n");
+ integer_cost[i] = computation_cost (build_int_cst (integer_type_node,
+ 2000), i);
+
+ symbol_cost[i] = computation_cost (addr, i) + 1;
+
+ address_cost[i]
+ = computation_cost (build2 (POINTER_PLUS_EXPR, type,
+ addr,
+ build_int_cst (sizetype, 2000)), i) + 1;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "force_expr_to_var_cost %s costs:\n", i ? "speed" : "size");
+ fprintf (dump_file, " integer %d\n", (int) integer_cost[i]);
+ fprintf (dump_file, " symbol %d\n", (int) symbol_cost[i]);
+ fprintf (dump_file, " address %d\n", (int) address_cost[i]);
+ fprintf (dump_file, " other %d\n", (int) target_spill_cost[i]);
+ fprintf (dump_file, "\n");
+ }
}
costs_initialized = true;
if (is_gimple_min_invariant (expr))
{
if (TREE_CODE (expr) == INTEGER_CST)
- return new_cost (integer_cost, 0);
+ return new_cost (integer_cost [speed], 0);
if (TREE_CODE (expr) == ADDR_EXPR)
{
if (TREE_CODE (obj) == VAR_DECL
|| TREE_CODE (obj) == PARM_DECL
|| TREE_CODE (obj) == RESULT_DECL)
- return new_cost (symbol_cost, 0);
+ return new_cost (symbol_cost [speed], 0);
}
- return new_cost (address_cost, 0);
+ return new_cost (address_cost [speed], 0);
}
switch (TREE_CODE (expr))
if (is_gimple_val (op0))
cost0 = zero_cost;
else
- cost0 = force_expr_to_var_cost (op0);
+ cost0 = force_expr_to_var_cost (op0, speed);
if (is_gimple_val (op1))
cost1 = zero_cost;
else
- cost1 = force_expr_to_var_cost (op1);
+ cost1 = force_expr_to_var_cost (op1, speed);
+
+ break;
+
+ case NEGATE_EXPR:
+ op0 = TREE_OPERAND (expr, 0);
+ STRIP_NOPS (op0);
+ op1 = NULL_TREE;
+
+ if (is_gimple_val (op0))
+ cost0 = zero_cost;
+ else
+ cost0 = force_expr_to_var_cost (op0, speed);
+ cost1 = zero_cost;
break;
default:
/* Just an arbitrary value, FIXME. */
- return new_cost (target_spill_cost, 0);
+ return new_cost (target_spill_cost[speed], 0);
}
mode = TYPE_MODE (TREE_TYPE (expr));
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
- cost = new_cost (add_cost (mode), 0);
+ case NEGATE_EXPR:
+ cost = new_cost (add_cost (mode, speed), 0);
break;
case MULT_EXPR:
if (cst_and_fits_in_hwi (op0))
- cost = new_cost (multiply_by_cost (int_cst_value (op0), mode), 0);
- else if (cst_and_fits_in_hwi (op1))
- cost = new_cost (multiply_by_cost (int_cst_value (op1), mode), 0);
+ cost = new_cost (multiply_by_cost (int_cst_value (op0), mode, speed), 0);
+ else if (cst_and_fits_in_hwi (op1))
+ cost = new_cost (multiply_by_cost (int_cst_value (op1), mode, speed), 0);
else
- return new_cost (target_spill_cost, 0);
+ return new_cost (target_spill_cost [speed], 0);
break;
default:
computations often are either loop invariant or at least can
be shared between several iv uses, so letting this grow without
limits would not give reasonable results. */
- if (cost.cost > target_spill_cost)
- cost.cost = target_spill_cost;
+ if (cost.cost > (int) target_spill_cost [speed])
+ cost.cost = target_spill_cost [speed];
return cost;
}
walk_tree (&expr, find_depends, depends_on, NULL);
}
- return force_expr_to_var_cost (expr);
+ return force_expr_to_var_cost (expr, data->speed);
}
/* Estimates cost of expressing address ADDR as var + symbol + offset. The
*var_present = true;
fd_ivopts_data = data;
walk_tree (&addr, find_depends, depends_on, NULL);
- return new_cost (target_spill_cost, 0);
+ return new_cost (target_spill_cost[data->speed], 0);
}
*offset += bitpos / BITS_PER_UNIT;
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
HOST_WIDE_INT diff = 0;
- comp_cost cost;
+ aff_tree aff_e1, aff_e2;
+ tree type;
gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
*symbol_present = false;
*var_present = true;
-
- cost = force_var_cost (data, e1, depends_on);
- cost = add_costs (cost, force_var_cost (data, e2, depends_on));
- cost.cost += add_cost (Pmode);
- return cost;
+ type = signed_type_for (TREE_TYPE (e1));
+ tree_to_aff_combination (e1, type, &aff_e1);
+ tree_to_aff_combination (e2, type, &aff_e2);
+ aff_combination_scale (&aff_e2, double_int_minus_one);
+ aff_combination_add (&aff_e1, &aff_e2);
+
+ return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
}
/* Estimates cost of expressing difference E1 - E2 as
tree e1, tree e2, bool *symbol_present, bool *var_present,
unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
{
- comp_cost cost;
enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
unsigned HOST_WIDE_INT off1, off2;
+ aff_tree aff_e1, aff_e2;
+ tree type;
e1 = strip_offset (e1, &off1);
e2 = strip_offset (e2, &off2);
STRIP_NOPS (e2);
if (TREE_CODE (e1) == ADDR_EXPR)
- return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
- depends_on);
+ return ptr_difference_cost (data, e1, e2, symbol_present, var_present,
+ offset, depends_on);
*symbol_present = false;
if (operand_equal_p (e1, e2, 0))
*var_present = false;
return zero_cost;
}
+
*var_present = true;
+
if (integer_zerop (e2))
return force_var_cost (data, e1, depends_on);
if (integer_zerop (e1))
{
- cost = force_var_cost (data, e2, depends_on);
- cost.cost += multiply_by_cost (-1, mode);
-
+ comp_cost cost = force_var_cost (data, e2, depends_on);
+ cost.cost += multiply_by_cost (-1, mode, data->speed);
return cost;
}
- cost = force_var_cost (data, e1, depends_on);
- cost = add_costs (cost, force_var_cost (data, e2, depends_on));
- cost.cost += add_cost (mode);
+ type = signed_type_for (TREE_TYPE (e1));
+ tree_to_aff_combination (e1, type, &aff_e1);
+ tree_to_aff_combination (e2, type, &aff_e2);
+ aff_combination_scale (&aff_e2, double_int_minus_one);
+ aff_combination_add (&aff_e1, &aff_e2);
- return cost;
+ return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
}
/* Determines the cost of the computation by that USE is expressed
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
register. A set of invariants we depend on is stored in
- DEPENDS_ON. AT is the statement at that the value is computed. */
+ DEPENDS_ON. AT is the statement at that the value is computed.
+ If CAN_AUTOINC is nonnull, use it to record whether autoinc
+ addressing is likely. */
static comp_cost
get_computation_cost_at (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on, gimple at)
+ bool address_p, bitmap *depends_on, gimple at,
+ bool *can_autoinc)
{
tree ubase = use->iv->base, ustep = use->iv->step;
tree cbase, cstep;
tree utype = TREE_TYPE (ubase), ctype;
unsigned HOST_WIDE_INT cstepi, offset = 0;
HOST_WIDE_INT ratio, aratio;
- bool var_present, symbol_present;
+ bool var_present, symbol_present, stmt_is_after_inc;
comp_cost cost;
- unsigned n_sums;
double_int rat;
+ bool speed = optimize_bb_for_speed_p (gimple_bb (at));
*depends_on = NULL;
return infinite_cost;
}
- if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
+ if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
{
/* TODO -- add direct handling of this case. */
goto fallback;
else
return infinite_cost;
+ STRIP_NOPS (cbase);
+ ctype = TREE_TYPE (cbase);
+
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
&symbol_present, &var_present, &offset,
depends_on);
}
+ else if (address_p
+ && !POINTER_TYPE_P (ctype)
+ && multiplier_allowed_in_address_p (ratio,
+ TYPE_MODE (TREE_TYPE (utype))))
+ {
+ cbase
+ = fold_build2 (MULT_EXPR, ctype, cbase, build_int_cst (ctype, ratio));
+ cost = difference_cost (data,
+ ubase, cbase,
+ &symbol_present, &var_present, &offset,
+ depends_on);
+ }
else
{
cost = force_var_cost (data, cbase, depends_on);
- cost.cost += add_cost (TYPE_MODE (ctype));
+ cost.cost += add_cost (TYPE_MODE (ctype), data->speed);
cost = add_costs (cost,
difference_cost (data,
ubase, build_int_cst (utype, 0),
/* If we are after the increment, the value of the candidate is higher by
one iteration. */
- if (stmt_after_increment (data->current_loop, cand, at))
+ stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
+ if (stmt_is_after_inc)
offset -= ratio * cstepi;
/* Now the computation is in shape symbol + var1 + const + ratio * var2.
- (symbol/var/const parts may be omitted). If we are looking for an address,
- find the cost of addressing this. */
+ (symbol/var1/const parts may be omitted). If we are looking for an
+ address, find the cost of addressing this. */
if (address_p)
- return add_costs (cost, get_address_cost (symbol_present, var_present,
- offset, ratio,
- TYPE_MODE (TREE_TYPE (*use->op_p))));
+ return add_costs (cost,
+ get_address_cost (symbol_present, var_present,
+ offset, ratio, cstepi,
+ TYPE_MODE (TREE_TYPE (utype)),
+ speed, stmt_is_after_inc,
+ can_autoinc));
/* Otherwise estimate the costs for computing the expression. */
- aratio = ratio > 0 ? ratio : -ratio;
if (!symbol_present && !var_present && !offset)
{
if (ratio != 1)
- cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype));
-
+ cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype), speed);
return cost;
}
- if (aratio != 1)
- cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype));
-
- n_sums = 1;
- if (var_present
- /* Symbol + offset should be compile-time computable. */
- && (symbol_present || offset))
- n_sums++;
+ /* Symbol + offset should be compile-time computable so consider that they
+ are added once to the variable, if present. */
+ if (var_present && (symbol_present || offset))
+ cost.cost += add_cost (TYPE_MODE (ctype), speed)
+ / AVG_LOOP_NITER (data->current_loop);
/* Having offset does not affect runtime cost in case it is added to
symbol, but it increases complexity. */
if (offset)
cost.complexity++;
- cost.cost += n_sums * add_cost (TYPE_MODE (ctype));
- return cost;
+ cost.cost += add_cost (TYPE_MODE (ctype), speed);
+
+ aratio = ratio > 0 ? ratio : -ratio;
+ if (aratio != 1)
+ cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);
fallback:
+ if (can_autoinc)
+ *can_autoinc = false;
+
{
/* Just get the expression, expand it and measure the cost. */
tree comp = get_computation_at (data->current_loop, use, cand, at);
if (address_p)
comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp);
- return new_cost (computation_cost (comp), 0);
+ return new_cost (computation_cost (comp, speed), 0);
}
}
from induction variable CAND. If ADDRESS_P is true, we just need
to create an address from it, otherwise we want to get it into
register. A set of invariants we depend on is stored in
- DEPENDS_ON. */
+ DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether
+ autoinc addressing is likely. */
static comp_cost
get_computation_cost (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
- bool address_p, bitmap *depends_on)
+ bool address_p, bitmap *depends_on, bool *can_autoinc)
{
return get_computation_cost_at (data,
- use, cand, address_p, depends_on, use->stmt);
+ use, cand, address_p, depends_on, use->stmt,
+ can_autoinc);
}
/* Determines cost of basing replacement of USE on CAND in a generic
return true;
}
- cost = get_computation_cost (data, use, cand, false, &depends_on);
+ cost = get_computation_cost (data, use, cand, false, &depends_on, NULL);
set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
return !infinite_cost_p (cost);
struct iv_use *use, struct iv_cand *cand)
{
bitmap depends_on;
- comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on);
+ bool can_autoinc;
+ comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on,
+ &can_autoinc);
+ if (cand->ainc_use == use)
+ {
+ if (can_autoinc)
+ cost.cost -= cand->cost_step;
+ /* If we generated the candidate solely for exploiting autoincrement
+ opportunities, and it turns out it can't be used, set the cost to
+ infinity to make sure we ignore it. */
+ else if (cand->pos == IP_AFTER_USE || cand->pos == IP_BEFORE_USE)
+ cost = infinite_cost;
+ }
set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
return !infinite_cost_p (cost);
return false;
cand_value_at (loop, cand, use->stmt, nit, &bnd);
+
*bound = aff_combination_to_tree (&bnd);
+ /* It is unlikely that computing the number of iterations using division
+ would be more profitable than keeping the original induction variable. */
+ if (expression_expensive_p (*bound))
+ return false;
return true;
}
gcc_assert (ok);
express_cost = get_computation_cost (data, use, cand, false,
- &depends_on_express);
+ &depends_on_express, NULL);
fd_ivopts_data = data;
walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
- /* Choose the better approach. */
- if (compare_costs (elim_cost, express_cost) < 0)
+ /* Choose the better approach, preferring the eliminated IV. */
+ if (compare_costs (elim_cost, express_cost) <= 0)
{
cost = elim_cost;
depends_on = depends_on_elim;
}
}
+/* Return true if get_computation_cost indicates that autoincrement is
+ a possibility for the pair of USE and CAND, false otherwise. */
+
+static bool
+autoinc_possible_for_pair (struct ivopts_data *data, struct iv_use *use,
+ struct iv_cand *cand)
+{
+ bitmap depends_on;
+ bool can_autoinc;
+ comp_cost cost;
+
+ if (use->type != USE_ADDRESS)
+ return false;
+
+ cost = get_computation_cost (data, use, cand, true, &depends_on,
+ &can_autoinc);
+
+ BITMAP_FREE (depends_on);
+
+ return !infinite_cost_p (cost) && can_autoinc;
+}
+
+/* Examine IP_ORIGINAL candidates to see if they are incremented next to a
+ use that allows autoincrement, and set their AINC_USE if possible. */
+
+static void
+set_autoinc_for_original_candidates (struct ivopts_data *data)
+{
+ unsigned i, j;
+
+ for (i = 0; i < n_iv_cands (data); i++)
+ {
+ struct iv_cand *cand = iv_cand (data, i);
+ struct iv_use *closest = NULL;
+ if (cand->pos != IP_ORIGINAL)
+ continue;
+ for (j = 0; j < n_iv_uses (data); j++)
+ {
+ struct iv_use *use = iv_use (data, j);
+ unsigned uid = gimple_uid (use->stmt);
+ if (gimple_bb (use->stmt) != gimple_bb (cand->incremented_at)
+ || uid > gimple_uid (cand->incremented_at))
+ continue;
+ if (closest == NULL || uid > gimple_uid (closest->stmt))
+ closest = use;
+ }
+ if (closest == NULL || !autoinc_possible_for_pair (data, closest, cand))
+ continue;
+ cand->ainc_use = closest;
+ }
+}
+
+/* Finds the candidates for the induction variables. */
+
+static void
+find_iv_candidates (struct ivopts_data *data)
+{
+ /* Add commonly used ivs. */
+ add_standard_iv_candidates (data);
+
+ /* Add old induction variables. */
+ add_old_ivs_candidates (data);
+
+ /* Add induction variables derived from uses. */
+ add_derived_ivs_candidates (data);
+
+ set_autoinc_for_original_candidates (data);
+
+ /* Record the important candidates. */
+ record_important_candidates (data);
+}
+
/* Determines costs of basing the use of the iv on an iv candidate. */
static void
base = cand->iv->base;
cost_base = force_var_cost (data, base, NULL);
- cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)));
+ cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
cost = cost_step + cost_base.cost / AVG_LOOP_NITER (current_loop);
cost++;
cand->cost = cost;
+ cand->cost_step = cost_step;
}
/* Determines costs of computation of the candidates. */
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " %d\t%d\n", i, cand->cost);
}
-
+
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n");
}
{
/* We add size to the cost, so that we prefer eliminating ivs
if possible. */
- return size + estimate_reg_pressure_cost (size, data->regs_used);
+ return size + estimate_reg_pressure_cost (size, data->regs_used, data->speed);
}
/* For each size of the induction variable set determine the penalty. */
{
fprintf (dump_file, "Global costs:\n");
fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs);
- fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost);
- fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost);
+ fprintf (dump_file, " target_reg_cost %d\n", target_reg_cost[data->speed]);
+ fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost[data->speed]);
}
n = 0;
static comp_cost
iv_ca_cost (struct iv_ca *ivs)
{
- return (ivs->bad_uses ? infinite_cost : ivs->cost);
+ /* This was a conditional expression but it triggered a bug in
+ Sun C 5.5. */
+ if (ivs->bad_uses)
+ return infinite_cost;
+ else
+ return ivs->cost;
}
/* Returns true if all dependences of CP are among invariants in IVS. */
after = true;
break;
+ case IP_AFTER_USE:
+ after = true;
+ /* fall through */
+ case IP_BEFORE_USE:
+ incr_pos = gsi_for_stmt (cand->incremented_at);
+ break;
+
case IP_ORIGINAL:
/* Mark that the iv is preserved. */
name_info (data, cand->var_before)->preserve_biv = true;
}
}
-/* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME
- is true, remove also the ssa name defined by the statement. */
-
-static void
-remove_statement (gimple stmt, bool including_defined_name)
-{
- gimple_stmt_iterator bsi = gsi_for_stmt (stmt);
-
- if (gimple_code (stmt) == GIMPLE_PHI)
- remove_phi_node (&bsi, including_defined_name);
- else
- {
- gsi_remove (&bsi, true);
- release_defs (stmt);
- }
-}
/* Rewrites USE (definition of iv used in a nonlinear expression)
using candidate CAND. */
{
ass = gimple_build_assign (tgt, op);
gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
- remove_statement (use->stmt, false);
+
+ bsi = gsi_for_stmt (use->stmt);
+ remove_phi_node (&bsi, false);
}
else
{
if (TREE_CODE (*idx) == SSA_NAME)
*idx = SSA_NAME_VAR (*idx);
- if (TREE_CODE (base) == ARRAY_REF)
+ if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
op = &TREE_OPERAND (base, 2);
if (*op
return ref;
}
-/* Extract the alias analysis info for the memory reference REF. There are
- several ways how this information may be stored and what precisely is
- its semantics depending on the type of the reference, but there always is
- somewhere hidden one _DECL node that is used to determine the set of
- virtual operands for the reference. The code below deciphers this jungle
- and extracts this single useful piece of information. */
-
-static tree
-get_ref_tag (tree ref, tree orig)
-{
- tree var = get_base_address (ref);
- tree aref = NULL_TREE, tag, sv;
- HOST_WIDE_INT offset, size, maxsize;
-
- for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
- {
- aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
- if (ref)
- break;
- }
-
- if (!var)
- return NULL_TREE;
-
- if (TREE_CODE (var) == INDIRECT_REF)
- {
- /* If the base is a dereference of a pointer, first check its name memory
- tag. If it does not have one, use its symbol memory tag. */
- var = TREE_OPERAND (var, 0);
- if (TREE_CODE (var) != SSA_NAME)
- return NULL_TREE;
-
- if (SSA_NAME_PTR_INFO (var))
- {
- tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
- if (tag)
- return tag;
- }
-
- var = SSA_NAME_VAR (var);
- tag = symbol_mem_tag (var);
- gcc_assert (tag != NULL_TREE);
- return tag;
- }
- else
- {
- if (!DECL_P (var))
- return NULL_TREE;
-
- tag = symbol_mem_tag (var);
- if (tag)
- return tag;
-
- return var;
- }
-}
-
/* Copies the reference information from OLD_REF to NEW_REF. */
static void
if (TREE_CODE (old_ref) == TARGET_MEM_REF)
copy_mem_ref_info (new_ref, old_ref);
else
- {
- TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
- TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
- }
+ TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
}
/* Rewrites USE (address that is an iv) using candidate CAND. */
gcc_assert (ok);
unshare_aff_combination (&aff);
- ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff);
+ ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff, data->speed);
copy_ref_info (ref, *use->op_p);
*use->op_p = ref;
}
{
tree var = var_at_stmt (data->current_loop, cand, use->stmt);
tree var_type = TREE_TYPE (var);
+ gimple_seq stmts;
compare = iv_elimination_compare (data, use);
bound = unshare_expr (fold_convert (var_type, bound));
- op = force_gimple_operand_gsi (&bsi, bound, true, NULL_TREE,
- true, GSI_SAME_STMT);
+ op = force_gimple_operand (bound, &stmts, true, NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (
+ loop_preheader_edge (data->current_loop),
+ stmts);
gimple_cond_set_lhs (use->stmt, var);
gimple_cond_set_code (use->stmt, compare);
static void
rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
{
- push_stmt_changes (&use->stmt);
-
switch (use->type)
{
case USE_NONLINEAR_EXPR:
default:
gcc_unreachable ();
}
-
- pop_stmt_changes (&use->stmt);
+
+ update_stmt (use->stmt);
}
/* Rewrite the uses using the selected induction variables. */
{
unsigned j;
bitmap_iterator bi;
+ bitmap toremove = BITMAP_ALLOC (NULL);
+ /* Figure out an order in which to release SSA DEFs so that we don't
+ release something that we'd have to propagate into a debug stmt
+ afterwards. */
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
{
struct version_info *info;
&& !info->inv_id
&& !info->iv->have_use_for
&& !info->preserve_biv)
- remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
+ bitmap_set_bit (toremove, SSA_NAME_VERSION (info->iv->ssa_name));
}
+
+ release_defs_bitset (toremove);
+
+ BITMAP_FREE (toremove);
}
/* Frees data allocated by the optimization of a single loop. */
bool changed = false;
struct iv_ca *iv_ca;
edge exit;
+ basic_block *body;
gcc_assert (!data->niters);
data->current_loop = loop;
+ data->speed = optimize_loop_for_speed_p (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\n");
}
+ body = get_loop_body (loop);
+ renumber_gimple_stmt_uids_in_blocks (body, loop->num_nodes);
+ free (body);
+
/* For each ssa name determines whether it behaves as an induction variable
in some loop. */
if (!find_induction_variables (data))
find_iv_candidates (data);
/* Calculates the costs (item 3, part 1). */
- determine_use_iv_costs (data);
determine_iv_costs (data);
+ determine_use_iv_costs (data);
determine_set_costs (data);
/* Find the optimal set of induction variables (item 3, part 2). */
OSDN Git Service
