Transformations and Optimisations

Modules
	Flags
	Flags to customize the behavior of libfirm.
	Graph Transformations
	Local Optimizations
Defines
#define	osr_flag_default   osr_flag_lftr_with_ov_check
	default setting
#define	DEFAULT_CLONE_THRESHOLD   20
	A default threshold.
Typedefs
typedef int(*	check_alloc_entity_func )(ir_entity *ent)
	A callback that checks whether a entity is an allocation routine.
typedef int(*	arch_allow_ifconv_func )(ir_node *sel, ir_node *mux_false, ir_node *mux_true)
	This function is called to evaluate, if a mux(sel, mux_false, mux_true) should be built for the current architecture.
typedef ir_type *(*	gen_pointer_type_to_func )(ir_type *tp)
	This is the type for a method, that returns a pointer type to tp.
typedef void(*	opt_ptr )(ir_graph *irg)
	pointer to an optimization function
typedef ir_entity *(*	compilerlib_entity_creator_t )(ident *id, ir_type *mt)
	Type of callbacks for createing entities of the compiler library.
Enumerations
enum	osr_flags { osr_flag_none = 0, osr_flag_lftr_with_ov_check = 1, osr_flag_ignore_x86_shift = 2, osr_flag_keep_reg_pressure = 4 }
	Possible flags for the Operator Scalar Replacement. More...
Functions
void	optimize_cf (ir_graph *irg)
	Control flow optimization.
ir_graph_pass_t *	optimize_cf_pass (const char *name)
	Creates an ir_graph pass for optimize_cf().
void	opt_jumpthreading (ir_graph *irg)
	Perform path-sensitive jump threading on the given graph.
ir_graph_pass_t *	opt_jumpthreading_pass (const char *name)
	Creates an ir_graph pass for opt_jumpthreading().
void	opt_bool (ir_graph *irg)
	Simplifies boolean expression in the given ir graph.
ir_graph_pass_t *	opt_bool_pass (const char *name)
	Creates an ir_graph pass for opt_bool().
int	conv_opt (ir_graph *irg)
	Reduces the number of Conv nodes in the given ir graph.
ir_graph_pass_t *	conv_opt_pass (const char *name)
	Creates an ir_graph pass for conv_opt().
void	escape_enalysis_irg (ir_graph *irg, check_alloc_entity_func callback)
	Performs simple and fast escape analysis for one graph.
void	escape_analysis (int run_scalar_replace, check_alloc_entity_func callback)
	Performs simple and fast escape analysis for all graphs.
void	optimize_funccalls (void)
	Optimize function calls by handling const functions.
ir_prog_pass_t *	optimize_funccalls_pass (const char *name)
	Creates an ir_prog pass for optimize_funccalls().
void	do_gvn_pre (ir_graph *irg)
	Does Partial Redundancy Elimination combined with Global Value Numbering.
ir_graph_pass_t *	do_gvn_pre_pass (const char *name)
	Creates an ir_graph pass for do_gvn_pre().
void	opt_if_conv (ir_graph *irg)
	Perform If conversion on a graph.
ir_graph_pass_t *	opt_if_conv_pass (const char *name)
	Creates an ir_graph pass for opt_if_conv().
void	opt_parallelize_mem (ir_graph *irg)
	Tries to reduce dependencies for memory nodes where possible by parallelizing them and synchronizing with Sync nodes.
ir_graph_pass_t *	opt_parallelize_mem_pass (const char *name)
	Creates an ir_graph pass for opt_sync().
ir_node *	can_replace_load_by_const (const ir_node *load, ir_node *c)
	Check if we can replace the load by a given const from the const code irg.
int	optimize_load_store (ir_graph *irg)
	Load/Store optimization.
ir_graph_pass_t *	optimize_load_store_pass (const char *name)
	Creates an ir_graph pass for optimize_load_store().
int	opt_ldst (ir_graph *irg)
	New experimental alternative to optimize_load_store.
ir_graph_pass_t *	opt_ldst_pass (const char *name)
	Creates an ir_graph pass for opt_ldst().
void	loop_optimization (ir_graph *irg)
	Optimize loops by peeling or unrolling them if beneficial.
void	opt_frame_irg (ir_graph *irg)
	Optimize the frame type of an irg by removing never touched entities.
ir_graph_pass_t *	opt_frame_irg_pass (const char *name)
	Creates an ir_graph pass for opt_frame_irg().
void	opt_osr (ir_graph *irg, unsigned flags)
	Performs the Operator Scalar Replacement optimization and linear function test replacement for loop control.
ir_graph_pass_t *	opt_osr_pass (const char *name, unsigned flags)
	Creates an ir_graph pass for remove_phi_cycles().
void	remove_phi_cycles (ir_graph *irg)
	Removes useless Phi cycles, i.e cycles of Phi nodes with only one non-Phi node.
ir_graph_pass_t *	remove_phi_cycles_pass (const char *name)
	Creates an ir_graph pass for remove_phi_cycles().
void	proc_cloning (float threshold)
	Performs procedure cloning.
ir_prog_pass_t *	proc_cloning_pass (const char *name, float threshold)
	Creates an ir_prog pass for proc_cloning().
int	optimize_reassociation (ir_graph *irg)
	Reassociation.
ir_graph_pass_t *	optimize_reassociation_pass (const char *name)
	Creates an ir_graph pass for optimize_reassociation().
void	normalize_one_return (ir_graph *irg)
	Normalize the Returns of a graph by creating a new End block with One Return(Phi).
ir_graph_pass_t *	normalize_one_return_pass (const char *name)
	Creates an ir_graph pass for normalize_one_return().
void	normalize_n_returns (ir_graph *irg)
	Normalize the Returns of a graph by moving the Returns upwards as much as possible.
ir_graph_pass_t *	normalize_n_returns_pass (const char *name)
	Creates an ir_graph pass for normalize_n_returns().
int	scalar_replacement_opt (ir_graph *irg)
	Performs the scalar replacement optimization.
ir_graph_pass_t *	scalar_replacement_opt_pass (const char *name)
	Creates an ir_graph pass for scalar_replacement_opt().
int	opt_tail_rec_irg (ir_graph *irg)
	Optimizes tail-recursion calls by converting them into loops.
ir_graph_pass_t *	opt_tail_rec_irg_pass (const char *name)
	Creates an ir_graph pass for opt_tail_rec_irg().
void	opt_tail_recursion (void)
	Optimize tail-recursion calls for all IR-Graphs.
ir_prog_pass_t *	opt_tail_recursion_pass (const char *name)
	Creates an ir_prog pass for opt_tail_recursion().
void	normalize_irp_class_casts (gen_pointer_type_to_func gppt_fct)
	Insert Casts so that class type casts conform exactly with the type hierarchy.
void	normalize_irg_class_casts (ir_graph *irg, gen_pointer_type_to_func gppt_fct)
	Insert Casts so that class type casts conform exactly with the type hierarchy in given graph.
void	optimize_class_casts (void)
	Optimize casting between class types.
void	combo (ir_graph *irg)
	CLiff Click's combo algorithm from "Combining Analyses, combining Optimizations".
ir_graph_pass_t *	combo_pass (const char *name)
	Creates an ir_graph pass for combo.
void	inline_small_irgs (ir_graph *irg, int size)
	Inlines all small methods at call sites where the called address comes from a SymConst node that references the entity representing the called method.
ir_graph_pass_t *	inline_small_irgs_pass (const char *name, int size)
	Creates an ir_graph pass for inline_small_irgs().
void	inline_leave_functions (unsigned maxsize, unsigned leavesize, unsigned size, int ignore_runtime)
	Inlineing with a different heuristic than inline_small_irgs().
ir_prog_pass_t *	inline_leave_functions_pass (const char *name, unsigned maxsize, unsigned leavesize, unsigned size, int ignore_runtime)
	Creates an ir_prog pass for inline_leave_functions().
void	inline_functions (unsigned maxsize, int inline_threshold, opt_ptr after_inline_opt)
	Heuristic inliner.
ir_prog_pass_t *	inline_functions_pass (const char *name, unsigned maxsize, int inline_threshold, opt_ptr after_inline_opt)
	Creates an ir_prog pass for inline_functions().
int	shape_blocks (ir_graph *irg)
	Combines congruent blocks into one.
ir_graph_pass_t *	shape_blocks_pass (const char *name)
	Creates an ir_graph pass for shape_blocks().
void	do_loop_inversion (ir_graph *irg)
	Perform loop inversion on a given graph.
void	do_loop_unrolling (ir_graph *irg)
	Perform loop unrolling on a given graph.
void	do_loop_peeling (ir_graph *irg)
	Perform loop peeling on a given graph.
ir_graph_pass_t *	loop_inversion_pass (const char *name)
	Creates an ir_graph pass for loop inversion.
ir_graph_pass_t *	loop_unroll_pass (const char *name)
	Creates an ir_graph pass for loop unrolling.
ir_graph_pass_t *	loop_peeling_pass (const char *name)
	Creates an ir_graph pass for loop peeling.
ir_graph_pass_t *	set_vrp_pass (const char *name)
	Creates an ir_graph pass for set_vrp_data()
void	garbage_collect_entities (void)
	Removes all entities which are unused.
ir_prog_pass_t *	garbage_collect_entities_pass (const char *name)
	Pass for garbage_collect_entities.
void	dead_node_elimination (ir_graph *irg)
	Performs dead node elimination by copying the ir graph to a new obstack.
ir_graph_pass_t *	dead_node_elimination_pass (const char *name)
	Creates an ir_graph pass for dead_node_elimination().
int	inline_method (ir_node *call, ir_graph *called_graph)
	Inlines a method at the given call site.
void	place_code (ir_graph *irg)
	Code Placement.
ir_graph_pass_t *	place_code_pass (const char *name)
	Creates an ir_graph pass for place_code().
void	fixpoint_vrp (ir_graph *)
	Determines information about the values of nodes and perform simplifications using this information.
ir_graph_pass_t *	fixpoint_vrp_irg_pass (const char *name)
	Creates an ir_graph pass for fixpoint_vrp().
int	value_not_zero (const ir_node *n, const ir_node **confirm)
	Checks if the value of a node is != 0.
int	value_not_null (const ir_node *n, const ir_node **confirm)
	Checks if the value of a node cannot represent a NULL pointer.
ir_value_classify_sign	classify_value_sign (ir_node *n)
	Checks if the value of a node can be confirmed >= 0 or <= 0, If the mode of the value did not honor signed zeros, else check for >= 0 or < 0.
ir_tarval *	computed_value_Cmp_Confirm (const ir_node *cmp, ir_node *left, ir_node *right, ir_relation relation)
	Returns the value of a Cmp if one or both predecessors are Confirm nodes.
void	set_compilerlib_entity_creator (compilerlib_entity_creator_t cb)
	Sets the compilerlib entity creation callback that is used to create compilerlib function entities.
compilerlib_entity_creator_t	get_compilerlib_entity_creator (void)
	Returns the compilerlib entity creation callback.
ir_entity *	create_compilerlib_entity (ident *id, ir_type *mt)
	Constructs the entity for a given function using the current compilerlib entity creation callback.

---

Define Documentation

#define DEFAULT_CLONE_THRESHOLD   20

A default threshold.

Definition at line 456 of file iroptimize.h.

#define osr_flag_default   osr_flag_lftr_with_ov_check

default setting

Definition at line 361 of file iroptimize.h.

---

Typedef Documentation

typedef int(* arch_allow_ifconv_func)(ir_node *sel, ir_node *mux_false, ir_node *mux_true)

This function is called to evaluate, if a mux(sel, mux_false, mux_true) should be built for the current architecture.

If it returns non-zero, a mux is created, else the code is not modified.

Parameters:

sel	A selector of a Cond.
phi_list	phi node to be converted
i	First data predecessor involved in if conversion
j	Second data predecessor involved in if conversion

Definition at line 213 of file iroptimize.h.

typedef int(* check_alloc_entity_func)(ir_entity *ent)

A callback that checks whether a entity is an allocation routine.

Definition at line 113 of file iroptimize.h.

typedef ir_entity*(* compilerlib_entity_creator_t)(ident *id, ir_type *mt)

Type of callbacks for createing entities of the compiler library.

Definition at line 1080 of file iroptimize.h.

typedef ir_type*(* gen_pointer_type_to_func)(ir_type *tp)

This is the type for a method, that returns a pointer type to tp.

This is needed in the normalization.

Definition at line 641 of file iroptimize.h.

typedef void(* opt_ptr)(ir_graph *irg)

pointer to an optimization function

Definition at line 799 of file iroptimize.h.

---

Enumeration Type Documentation

enum osr_flags

Possible flags for the Operator Scalar Replacement.

Enumerator:

osr_flag_none	no additional flags
osr_flag_lftr_with_ov_check	do linear function test replacement only if no overflow can occur.
osr_flag_ignore_x86_shift	ignore Multiplications by 2, 4, 8
osr_flag_keep_reg_pressure	do NOT increase register pressure by introducing new induction variables.

Definition at line 351 of file iroptimize.h.

---

Function Documentation

ir_node* can_replace_load_by_const	(	const ir_node *	load,
		ir_node *	c
	)

Check if we can replace the load by a given const from the const code irg.

Parameters:

load	the load to replace
c	the constant

Returns:

in the modes match or can be transformed using a reinterpret cast returns a copy of the constant (possibly Conv'ed) on the current_ir_graph

ir_value_classify_sign classify_value_sign

(

ir_node *

n

)

Checks if the value of a node can be confirmed >= 0 or <= 0, If the mode of the value did not honor signed zeros, else check for >= 0 or < 0.

Parameters:

n	a node representing the value

void combo

(

ir_graph *

irg

)

CLiff Click's combo algorithm from "Combining Analyses, combining Optimizations".

Does conditional constant propagation, unreachable code elimination and optimistic global value numbering at once.

Parameters:

irg	the graph to run on

ir_graph_pass_t* combo_pass

(

const char *

name

)

Creates an ir_graph pass for combo.

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

ir_tarval* computed_value_Cmp_Confirm	(	const ir_node *	cmp,
		ir_node *	left,
		ir_node *	right,
		ir_relation	relation
	)

Returns the value of a Cmp if one or both predecessors are Confirm nodes.

Parameters:

cmp	the compare node that will be evaluated
left	the left operand of the Cmp
right	the right operand of the Cmp
relation	the compare relation

int conv_opt

(

ir_graph *

irg

)

Reduces the number of Conv nodes in the given ir graph.

Parameters:

irg

the graph

Returns:

non-zero if the optimization could be applied, 0 else

ir_graph_pass_t* conv_opt_pass

(

const char *

name

)

Creates an ir_graph pass for conv_opt().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

ir_entity* create_compilerlib_entity	(	ident *	id,
		ir_type *	mt
	)

Constructs the entity for a given function using the current compilerlib entity creation callback.

Parameters:

id	the identifier of the compilerlib function
mt	the method type of the compilerlib function

void dead_node_elimination

(

ir_graph *

irg

)

Performs dead node elimination by copying the ir graph to a new obstack.

The major intention of this pass is to free memory occupied by dead nodes and outdated analyzes information. Further this function removes Bad predecessors from Blocks and the corresponding inputs to Phi nodes. This opens optimization potential for other optimizations. Further this phase reduces dead Block<->Jmp self-cycles to Bad nodes.

Dead_node_elimination is only performed if options `optimize' and `opt_dead_node_elimination' are set. The graph may not be in state phase_building. The outs datastructure is freed, the outs state set to outs_none. Backedge information is conserved. Removes old attributes of nodes. Sets link field to NULL. Callee information must be freed (irg_callee_info_none).

Parameters:

irg	The graph to be optimized.

ir_graph_pass_t* dead_node_elimination_pass

(

const char *

name

)

Creates an ir_graph pass for dead_node_elimination().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void do_gvn_pre

(

ir_graph *

irg

)

Does Partial Redundancy Elimination combined with Global Value Numbering.

Can be used to replace place_code() completely.

Based on VanDrunen and Hosking 2004.

Parameters:

irg

the graph

ir_graph_pass_t* do_gvn_pre_pass

(

const char *

name

)

Creates an ir_graph pass for do_gvn_pre().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void do_loop_inversion

(

ir_graph *

irg

)

Perform loop inversion on a given graph.

Loop inversion transforms a head controlled loop (like while(...) {} and for(...) {}) into a foot controlled loop (do {} while(...)).

void do_loop_peeling

(

ir_graph *

irg

)

Perform loop peeling on a given graph.

void do_loop_unrolling

(

ir_graph *

irg

)

Perform loop unrolling on a given graph.

Loop unrolling multiplies the number loop completely by a number found through a heuristic.

void escape_analysis	(	int	run_scalar_replace,
		check_alloc_entity_func	callback
	)

Performs simple and fast escape analysis for all graphs.

This optimization implements a simple and fast but inexact escape analysis. Some addresses might be marked as 'escaped' even if they are not. The advantage is a low memory footprint and fast speed.

Parameters:

run_scalar_replace	if this flag in non-zero, scalar replacement optimization is run on graphs with removed allocation
callback	a callback function to check whether a given entity is a allocation call

This optimization removes allocation which are not used (rare) and replace allocation that can be proved dead at the end of the graph which stack variables.

The creation of stack variable allows scalar replacement to be run only on those graphs that have been changed.

This is most effective on Java where no other stack variables exists.

void escape_enalysis_irg	(	ir_graph *	irg,
		check_alloc_entity_func	callback
	)

Performs simple and fast escape analysis for one graph.

Parameters:

irg	the graph
callback	a callback function to check whether a given entity is a allocation call

void fixpoint_vrp

(

ir_graph *

)

Determines information about the values of nodes and perform simplifications using this information.

This optimization performs a data-flow analysis to find the minimal fixpoint.

ir_graph_pass_t* fixpoint_vrp_irg_pass

(

const char *

name

)

Creates an ir_graph pass for fixpoint_vrp().

This pass dDetermines information about the values of nodes and perform simplifications using this information. This optimization performs a data-flow analysis to find the minimal fixpoint.

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void garbage_collect_entities

(

void

)

Removes all entities which are unused.

Unused entities have ir_visibility_local and are not used directly or indirectly through entities/code visible outside the compilation unit. This is usually conservative than gc_irgs, but does not respect properties of object-oriented programs.

ir_prog_pass_t* garbage_collect_entities_pass

(

const char *

name

)

Pass for garbage_collect_entities.

compilerlib_entity_creator_t get_compilerlib_entity_creator

(

void

)

Returns the compilerlib entity creation callback.

void inline_functions	(	unsigned	maxsize,
		int	inline_threshold,
		opt_ptr	after_inline_opt
	)

Heuristic inliner.

Calculates a benefice value for every call and inlines those calls with a value higher than the threshold.

Parameters:

maxsize	Do not inline any calls if a method has more than maxsize firm nodes. It may reach this limit by inlining.
inline_threshold	inlining threshold
after_inline_opt	optimizations performed immediately after inlining some calls

ir_prog_pass_t* inline_functions_pass	(	const char *	name,
		unsigned	maxsize,
		int	inline_threshold,
		opt_ptr	after_inline_opt
	)

Creates an ir_prog pass for inline_functions().

Parameters:

name	the name of this pass or NULL
maxsize	Do not inline any calls if a method has more than maxsize firm nodes. It may reach this limit by inlineing.
inline_threshold	inlining threshold
after_inline_opt	a function that is called after inlining a procedure. You should run fast local optimisations here which cleanup the graph before further inlining

Returns:

the newly created ir_prog pass

void inline_leave_functions	(	unsigned	maxsize,
		unsigned	leavesize,
		unsigned	size,
		int	ignore_runtime
	)

Inlineing with a different heuristic than inline_small_irgs().

Inlines leave functions. If inlining creates new leave function inlines these, too. (If g calls f, and f calls leave h, h is first inlined in f and then f in g.)

Then inlines all small functions (this is not recursive).

For a heuristic this inlining uses firm node counts. It does not count auxiliary nodes as Proj, Tuple, End, Start, Id, Sync. If the ignore_runtime flag is set, calls to functions marked with the mtp_property_runtime property are ignored.

Parameters:

maxsize	Do not inline any calls if a method has more than maxsize firm nodes. It may reach this limit by inlining.
leavesize	Inline leave functions if they have less than leavesize nodes.
size	Inline all function smaller than size.
ignore_runtime	count a function only calling runtime functions as leave

ir_prog_pass_t* inline_leave_functions_pass	(	const char *	name,
		unsigned	maxsize,
		unsigned	leavesize,
		unsigned	size,
		int	ignore_runtime
	)

Creates an ir_prog pass for inline_leave_functions().

Parameters:

name	the name of this pass or NULL
maxsize	Do not inline any calls if a method has more than maxsize firm nodes. It may reach this limit by inlining.
leavesize	Inline leave functions if they have less than leavesize nodes.
size	Inline all function smaller than size.
ignore_runtime	count a function only calling runtime functions as leave

Returns:

the newly created ir_prog pass

int inline_method	(	ir_node *	call,
		ir_graph *	called_graph
	)

Inlines a method at the given call site.

Removes the call node and splits the basic block the call node belongs to. Inserts a copy of the called graph between these nodes. Assumes that call is a Call node in current_ir_graph and that the type in the Call nodes type attribute is the same as the type of the called graph. Further it assumes that all Phi nodes in a block of current_ir_graph are assembled in a "link" list in the link field of the corresponding block nodes. Further assumes that all Proj nodes are in a "link" list in the nodes producing the tuple. (This is only an optical feature for the graph.) Conserves this feature for the old nodes of the graph. This precondition can be established by a call to collect_phisprojs(), see irgmod.h. As dead_node_elimination this function reduces dead Block<->Jmp self-cycles to Bad nodes.

Called_graph must be unequal to current_ir_graph. Will not inline if they are equal. Sets visited masterflag in current_ir_graph to the max of the flag in current and called graph. Assumes that both, the called and the calling graph are in state "op_pin_state_pinned". It is recommended to call local_optimize_graph() after inlining as this function leaves a set of obscure Tuple nodes, e.g. a Proj-Tuple-Jmp combination as control flow operation.

Parameters:

call	the call node that should be inlined
called_graph	the IR-graph that is called at call

Returns:

zero if method could not be inlined (recursion for instance), non-zero if all went ok

void inline_small_irgs	(	ir_graph *	irg,
		int	size
	)

Inlines all small methods at call sites where the called address comes from a SymConst node that references the entity representing the called method.

Parameters:

irg	the graph
size	maximum function size

The size argument is a rough measure for the code size of the method: Methods where the obstack containing the firm graph is smaller than size are inlined. Further only a limited number of calls are inlined. If the method contains more than 1024 inlineable calls none will be inlined. Inlining is only performed if flags `optimize' and `inlining' are set. The graph may not be in state phase_building. It is recommended to call local_optimize_graph() after inlining as this function leaves a set of obscure Tuple nodes, e.g. a Proj-Tuple-Jmp combination as control flow operation.

ir_graph_pass_t* inline_small_irgs_pass	(	const char *	name,
		int	size
	)

Creates an ir_graph pass for inline_small_irgs().

Parameters:

name	the name of this pass or NULL
size	maximum function size

Returns:

the newly created ir_graph pass

ir_graph_pass_t* loop_inversion_pass

(

const char *

name

)

Creates an ir_graph pass for loop inversion.

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void loop_optimization

(

ir_graph *

irg

)

Optimize loops by peeling or unrolling them if beneficial.

Parameters:

irg	The graph whose loops will be processed

This function did not change the graph, only its frame type. The layout state of the frame type will be set to layout_undefined if entities were removed.

ir_graph_pass_t* loop_peeling_pass

(

const char *

name

)

Creates an ir_graph pass for loop peeling.

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

ir_graph_pass_t* loop_unroll_pass

(

const char *

name

)

Creates an ir_graph pass for loop unrolling.

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void normalize_irg_class_casts	(	ir_graph *	irg,
		gen_pointer_type_to_func	gppt_fct
	)

Insert Casts so that class type casts conform exactly with the type hierarchy in given graph.

For more details see normalize_irp_class_casts().

This transformation requires that type information is computed.

See also:

irtypeinfo.h.

void normalize_irp_class_casts

(

gen_pointer_type_to_func

gppt_fct

)

Insert Casts so that class type casts conform exactly with the type hierarchy.

Formulated in Java, this achieves the following:

For a class hierarchy class A {} class B extends A {} class C extends B {} we transforms a cast (A)new C() to (A)((B)new C()).

The algorithm works for Casts with class types, but also for Casts with all pointer types that point (over several indirections, i.e. ***A) to a class type. Normalizes all graphs. Computes type information (

See also:

irtypeinfo.h) if not available. Invalidates trout information as new casts are generated.

Parameters:

gppt_fct

A function that returns a pointer type that points to the type given as argument. If this parameter is NULL, a default function is used that either uses trout information or performs a O(n) search to find an existing pointer type. If it can not find a type, generates a pointer type with mode_P_mach and suffix "cc_ptr_tp".

void normalize_n_returns

(

ir_graph *

irg

)

Normalize the Returns of a graph by moving the Returns upwards as much as possible.

This might be preferred for code generation.

In pseudocode, it means:

if (a) res = b; else res = c; return res;

is transformed into

if (a) return b; else return c;

ir_graph_pass_t* normalize_n_returns_pass

(

const char *

name

)

Creates an ir_graph pass for normalize_n_returns().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void normalize_one_return

(

ir_graph *

irg

)

Normalize the Returns of a graph by creating a new End block with One Return(Phi).

This is the preferred input for the if-conversion.

In pseudocode, it means:

if (a) return b; else return c;

is transformed into

if (a) res = b; else res = c; return res;

ir_graph_pass_t* normalize_one_return_pass

(

const char *

name

)

Creates an ir_graph pass for normalize_one_return().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void opt_bool

(

ir_graph *

irg

)

Simplifies boolean expression in the given ir graph.

eg. x < 5 && x < 6 becomes x < 5

Parameters:

irg

the graph

ir_graph_pass_t* opt_bool_pass

(

const char *

name

)

Creates an ir_graph pass for opt_bool().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void opt_frame_irg

(

ir_graph *

irg

)

Optimize the frame type of an irg by removing never touched entities.

Parameters:

irg	The graph whose frame type will be optimized

This function did not change the graph, only its frame type. The layout state of the frame type will be set to layout_undefined if entities were removed.

ir_graph_pass_t* opt_frame_irg_pass

(

const char *

name

)

Creates an ir_graph pass for opt_frame_irg().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void opt_if_conv

(

ir_graph *

irg

)

Perform If conversion on a graph.

Parameters:

irg	The graph.

Cannot handle blocks with Bad control predecessors, so call it after control flow optimization.

ir_graph_pass_t* opt_if_conv_pass

(

const char *

name

)

Creates an ir_graph pass for opt_if_conv().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void opt_jumpthreading

(

ir_graph *

irg

)

Perform path-sensitive jump threading on the given graph.

Parameters:

irg

the graph

ir_graph_pass_t* opt_jumpthreading_pass

(

const char *

name

)

Creates an ir_graph pass for opt_jumpthreading().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

int opt_ldst

(

ir_graph *

irg

)

New experimental alternative to optimize_load_store.

Based on a dataflow analysis, so load/stores are moved out of loops where possible

ir_graph_pass_t* opt_ldst_pass

(

const char *

name

)

Creates an ir_graph pass for opt_ldst().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void opt_osr	(	ir_graph *	irg,
		unsigned	flags
	)

Performs the Operator Scalar Replacement optimization and linear function test replacement for loop control.

Can be switched off using the set_opt_strength_red() flag. In that case, only remove_phi_cycles() is executed.

Parameters:

irg	the graph which should be optimized
flags	set of osr_flags

The linear function replacement test is controlled by the flags. If the osr_flag_lftr_with_ov_check is set, the replacement is only done if do overflow can occur. Otherwise it is ALWAYS done which might be insecure.

For instance:

for (i = 0; i < 100; ++i)

might be replaced by

for (i = 0; i < 400; i += 4)

But

for (i = 0; i < 0x7FFFFFFF; ++i)

will not be replaced by

for (i = 0; i < 0xFFFFFFFC; i += 4)

because of overflow.

More bad cases:

for (i = 0; i <= 0xF; ++i)

will NOT be transformed into

for (i = 0xFFFFFFF0; i <= 0xFFFFFFFF; ++i)

although here is no direct overflow. The OV occurs when the ++i is executed (and would created an endless loop here!).

For the same reason, a loop

for (i = 0; i <= 9; i += x)

will NOT be transformed because we cannot estimate whether an overflow might happen adding x.

Note that i < a + 400 is also not possible with the current implementation although this might be allowed by other compilers...

Note further that tests for equality can be handled some simpler (but are not implemented yet).

This algorithm destroys the link field of nodes.

ir_graph_pass_t* opt_osr_pass	(	const char *	name,
		unsigned	flags
	)

Creates an ir_graph pass for remove_phi_cycles().

Parameters:

name	the name of this pass or NULL
flags	set of osr_flags

Returns:

the newly created ir_graph pass

void opt_parallelize_mem

(

ir_graph *

irg

)

Tries to reduce dependencies for memory nodes where possible by parallelizing them and synchronizing with Sync nodes.

Parameters:

irg	the graph where memory operations should be parallelized

ir_graph_pass_t* opt_parallelize_mem_pass

(

const char *

name

)

Creates an ir_graph pass for opt_sync().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

int opt_tail_rec_irg

(

ir_graph *

irg

)

Optimizes tail-recursion calls by converting them into loops.

Depends on the flag opt_tail_recursion. Currently supports the following forms:

• return func();
• return x + func();
• return func() - x;
• return x * func();
• return -func();

Does not work for Calls that use the exception stuff.

Parameters:

irg	the graph to be optimized

Returns:

non-zero if the optimization could be applied, 0 else

ir_graph_pass_t* opt_tail_rec_irg_pass

(

const char *

name

)

Creates an ir_graph pass for opt_tail_rec_irg().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void opt_tail_recursion

(

void

)

Optimize tail-recursion calls for all IR-Graphs.

Can currently handle:

• direct return value, i.e. return func().
• additive return value, i.e. return x +/- func()
• multiplicative return value, i.e. return x * func() or return -func()

The current implementation must be run before optimize_funccalls(), because it expects the memory edges pointing to calls, which might be removed by optimize_funccalls().

ir_prog_pass_t* opt_tail_recursion_pass

(

const char *

name

)

Creates an ir_prog pass for opt_tail_recursion().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_prog pass

void optimize_cf

(

ir_graph *

irg

)

Control flow optimization.

Removes empty blocks doing if simplifications and loop simplifications. A block is empty if it contains only a Jmp node and Phi nodes. Merges single entry single exit blocks with their predecessor and propagates dead control flow by calling equivalent_node(). Independent of compiler flag it removes Tuples from cf edges, Bad predecessors from Blocks and Phis, and unnecessary predecessors of End. Destroys backedge information.

ir_graph_pass_t* optimize_cf_pass

(

const char *

name

)

Creates an ir_graph pass for optimize_cf().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void optimize_class_casts

(

void

)

Optimize casting between class types.

class A { m(); } class B extends A { } class C extends B {} Performs the following transformations: C c = (C)(B)(A)(B)new C() --> C c = (C)(B)newC() --> C c = new C() (Optimizing downcasts as A a = (A)(B)(new A()) --> A a = new A() can be suppressed by setting the flag opt_suppress_downcast_optimization. Downcasting A to B might cause an exception. It is not clear whether this is modeled by the Firm Cast node, as it has no exception outputs.); If there is inh_m() that overwrites m() in B: ((A) new B()).m() --> (new B()).inh_m() Phi((A)x, (A)y) --> (A) Phi (x, y) if (A) is an upcast.

Computes type information if not available.

See also:

irtypeinfo.h. Typeinformation is valid after optimization. Invalidates trout information.

void optimize_funccalls

(

void

)

Optimize function calls by handling const functions.

This optimization first detects all "const functions", i.e., IR graphs that neither read nor write memory (and hence did not create exceptions, as these use memory in Firm).

The result of calls to such functions depends only on its arguments, hence those calls are no more pinned.

This is a rather strong criteria, so do not expect that a lot of functions will be found. Moreover, all of them might already be inlined if inlining is activated. Anyway, it might be good for handling builtin's even if the later read/write memory (but we know how).

This optimizations read the irg_const_function property of entities and and sets the irg_const_function property of graphs.

If callee information is valid, we also optimize polymorphic Calls.

ir_prog_pass_t* optimize_funccalls_pass

(

const char *

name

)

Creates an ir_prog pass for optimize_funccalls().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_prog pass

int optimize_load_store

(

ir_graph *

irg

)

Load/Store optimization.

Removes redundant non-volatile Loads and Stores. May introduce Bad nodes if exceptional control flow is removed. The following cases are optimized:

Load without result: A Load which has only a memory use is removed.

Load after Store: A Load after a Store is removed, if the Load doesn't have an exception handler OR is in the same block as the Store.

Load after Load: A Load after a Load is removed, if the Load doesn't have an exception handler OR is in the same block as the previous Load.

Store before Store: A Store immediately before another Store in the same block is removed, if the Store doesn't have an exception handler.

Store after Load: A Store after a Load is removed, if the Store doesn't have an exception handler.

Returns:

non-zero if the optimization could be applied, 0 else

ir_graph_pass_t* optimize_load_store_pass

(

const char *

name

)

Creates an ir_graph pass for optimize_load_store().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

int optimize_reassociation

(

ir_graph *

irg

)

Reassociation.

Applies Reassociation rules to integer expressions. Beware: Works only if integer overflow might be ignored, as for C, Java and for address expression. Works only if Constant folding is activated.

Uses loop information to detect loop-invariant (i.e. contant inside the loop) values.

See Muchnik 12.3.1 Algebraic Simplification and Reassociation of Addressing Expressions.

Returns:

non-zero if the optimization could be applied, 0 else

ir_graph_pass_t* optimize_reassociation_pass

(

const char *

name

)

Creates an ir_graph pass for optimize_reassociation().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void place_code

(

ir_graph *

irg

)

Code Placement.

Pins all floating nodes to a block where they will be executed only if needed. Depends on the flag opt_global_cse. Graph may not be in phase_building. Does not schedule control dead code. Uses dominator information which it computes if the irg is not in state dom_consistent. Destroys the out information as it moves nodes to other blocks. Optimizes Tuples in Control edges.

Call remove_critical_cf_edges() before place_code(). This normalizes the control flow graph so that for all operations a basic block exists where they can be optimally placed.

ir_graph_pass_t* place_code_pass

(

const char *

name

)

Creates an ir_graph pass for place_code().

This pass enables GCSE, runs optimize_graph_df() and finally place_code();

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void proc_cloning

(

float

threshold

)

Performs procedure cloning.

Evaluate a heuristic weight for every Call(..., Const, ...). If the weight is bigger than threshold, clone the entity and fix the calls.

Parameters:

threshold

the threshold for cloning

The threshold is an estimation of how many instructions are saved when executing a cloned method. If threshold is 0.0, every possible call is cloned.

ir_prog_pass_t* proc_cloning_pass	(	const char *	name,
		float	threshold
	)

Creates an ir_prog pass for proc_cloning().

Parameters:

name	the name of this pass or NULL
threshold	the threshold for cloning

Returns:

the newly created ir_prog pass

void remove_phi_cycles

(

ir_graph *

irg

)

Removes useless Phi cycles, i.e cycles of Phi nodes with only one non-Phi node.

This is automatically done in opt_osr(), so there is no need to call it additionally.

Parameters:

irg	the graph which should be optimized

This algorithm destroys the link field of nodes.

ir_graph_pass_t* remove_phi_cycles_pass

(

const char *

name

)

Creates an ir_graph pass for remove_phi_cycles().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

int scalar_replacement_opt

(

ir_graph *

irg

)

Performs the scalar replacement optimization.

Replaces local compound entities (like structures and arrays) with atomic values if possible. Does not handle classes yet.

Parameters:

irg	the graph which should be optimized

Returns:

non-zero, if at least one entity was replaced

ir_graph_pass_t* scalar_replacement_opt_pass

(

const char *

name

)

Creates an ir_graph pass for scalar_replacement_opt().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

void set_compilerlib_entity_creator

(

compilerlib_entity_creator_t

cb

)

Sets the compilerlib entity creation callback that is used to create compilerlib function entities.

Parameters:

cb	the new compilerlib entity creation callback

ir_graph_pass_t* set_vrp_pass

(

const char *

name

)

Creates an ir_graph pass for set_vrp_data()

Parameters:

name	The name of this pass or NULL

Returns:

the newly created ir_graph pass

int shape_blocks

(

ir_graph *

irg

)

Combines congruent blocks into one.

Parameters:

irg	The IR-graph to optimize.

Returns:

non-zero if the graph was transformed

ir_graph_pass_t* shape_blocks_pass

(

const char *

name

)

Creates an ir_graph pass for shape_blocks().

Parameters:

name	the name of this pass or NULL

Returns:

the newly created ir_graph pass

int value_not_null	(	const ir_node *	n,
		const ir_node **	confirm
	)

Checks if the value of a node cannot represent a NULL pointer.

• If option sel_based_null_check_elim is enabled, all Sel nodes can be skipped.
• A SymConst(entity) is NEVER a NULL pointer
• A Const != NULL is NEVER a NULL pointer
• Confirms are evaluated

Parameters:

n	a node representing the value
confirm	if n is confirmed to be != NULL, returns the the Confirm-node, else NULL

int value_not_zero	(	const ir_node *	n,
		const ir_node **	confirm
	)

Checks if the value of a node is != 0.

This is a often needed case, so we handle here Confirm nodes too.

Parameters:

n	a node representing the value
confirm	if n is confirmed to be != 0, returns the the Confirm-node, else NULL