Modules
	Flags
	Flags to customize the behavior of libfirm.

	Graph Transformations

	Local Optimizations

Macros
#define	osr_flag_default osr_flag_lftr_with_ov_check
	default setting More...

#define	DEFAULT_CLONE_THRESHOLD 20
	A default threshold. More...

Typedefs
typedef int(*	check_alloc_entity_func) (ir_entity *ent)
	A callback that checks whether a entity is an allocation routine. More...

typedef int(*	arch_allow_ifconv_func) (ir_node const sel, ir_node const mux_false, ir_node const *mux_true)
	This function is called to evaluate, if a mux(`sel`, `mux_false`, `mux_true`) should be built for the current architecture. More...

typedef void(*	opt_ptr) (ir_graph *irg)
	pointer to an optimization function More...

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. More...

void	opt_jumpthreading (ir_graph *irg)
	Perform path-sensitive jump threading on the given graph. More...

void	opt_bool (ir_graph *irg)
	Simplifies boolean expression in the given ir graph. More...

void	conv_opt (ir_graph *irg)
	Reduces the number of Conv nodes in the given ir graph. More...

void	optimize_funccalls (void)
	Optimize function calls by handling const functions. More...

void	do_gvn_pre (ir_graph *irg)
	Does Partial Redundancy Elimination combined with Global Value Numbering. More...

void	opt_if_conv (ir_graph *irg)
	Perform If conversion on a graph. More...

void	opt_if_conv_cb (ir_graph *irg, arch_allow_ifconv_func callback)
	Perform If conversion on a graph - callback version. More...

void	opt_parallelize_mem (ir_graph *irg)
	Tries to reduce dependencies for memory nodes where possible by parallelizing them and synchronizing with Sync nodes. More...

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. More...

void	optimize_load_store (ir_graph *irg)
	Load/Store optimization. More...

void	combine_memops (ir_graph *irg)
	Combine adjacent "small" load/store operations into bigger ones. More...

void	opt_ldst (ir_graph *irg)
	New experimental alternative to optimize_load_store. More...

void	opt_frame_irg (ir_graph *irg)
	Optimize the frame type of an irg by removing never touched entities. More...

void	opt_osr (ir_graph *irg, unsigned flags)
	Performs the Operator Scalar Replacement optimization and linear function test replacement for loop control. More...

void	remove_phi_cycles (ir_graph *irg)
	Removes useless Phi cycles, i.e cycles of Phi nodes with only one non-Phi node. More...

void	proc_cloning (float threshold)
	Performs procedure cloning. More...

void	optimize_reassociation (ir_graph *irg)
	Reassociation. More...

void	normalize_one_return (ir_graph *irg)
	Normalize the Returns of a graph by creating a new End block with One Return(Phi). More...

void	normalize_n_returns (ir_graph *irg)
	Normalize the Returns of a graph by moving the Returns upwards as much as possible. More...

void	scalar_replacement_opt (ir_graph *irg)
	Performs the scalar replacement optimization. More...

void	opt_tail_rec_irg (ir_graph *irg)
	Optimizes tail-recursion calls by converting them into loops. More...

void	combo (ir_graph *irg)
	CLiff Click's combo algorithm from "Combining Analyses, combining Optimizations". More...

void	inline_functions (unsigned maxsize, int inline_threshold, opt_ptr after_inline_opt)
	Heuristic inliner. More...

void	shape_blocks (ir_graph *irg)
	Combines congruent blocks into one. More...

void	do_loop_inversion (ir_graph *irg)
	Perform loop inversion on a given graph. More...

void	do_loop_unrolling (ir_graph *irg)
	Perform loop unrolling on a given graph. More...

void	unroll_loops (ir_graph *irg, unsigned factor, unsigned maxsize)
	Perform loop unrolling on a given graph. More...

void	do_loop_peeling (ir_graph *irg)
	Perform loop peeling on a given graph. More...

void	garbage_collect_entities (void)
	Removes all entities which are unused. More...

void	dead_node_elimination (ir_graph *irg)
	Performs dead node elimination by copying the ir graph to a new obstack. More...

void	place_code (ir_graph *irg)
	Code Placement. More...

void	occult_consts (ir_graph *)
	This optimization finds values where the bits are either constant or irrelevant and exchanges them for a corresponding constant. More...

int	value_not_null (const ir_node n, const ir_node *confirm)
	Returns true if the value `n` is known not be zero/null. More...

ir_tarval *	computed_value_Cmp_Confirm (ir_node left, ir_node right, ir_relation relation)
	Returns the value of a Cmp if one or both predecessors are Confirm nodes. More...

ir_entity *	create_compilerlib_entity (char const name, ir_type mt)
	Constructs the entity for a given function using the current compilerlib entity creation callback. More...

Detailed Description

Macro Definition Documentation

◆ DEFAULT_CLONE_THRESHOLD

#define DEFAULT_CLONE_THRESHOLD 20

A default threshold.

Definition at line 289 of file iroptimize.h.

◆ osr_flag_default

#define osr_flag_default osr_flag_lftr_with_ov_check

default setting

Definition at line 216 of file iroptimize.h.

Typedef Documentation

◆ arch_allow_ifconv_func

typedef int(* arch_allow_ifconv_func) (ir_node const *sel, ir_node const *mux_false, ir_node const *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 109 of file iroptimize.h.

◆ check_alloc_entity_func

typedef int(* check_alloc_entity_func) (ir_entity *ent)

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

Definition at line 61 of file iroptimize.h.

◆ opt_ptr

typedef void(* opt_ptr) (ir_graph *irg)

pointer to an optimization function

Definition at line 401 of file iroptimize.h.

Enumeration Type Documentation

◆ osr_flags

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 206 of file iroptimize.h.

Function Documentation

◆ can_replace_load_by_const()

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: if the modes match or can be transformed using a reinterpret cast returns a copy of the constant (possibly Conv'ed) in the graph where the load is.

◆ combine_memops()

void combine_memops ( ir_graph * irg )

Combine adjacent "small" load/store operations into bigger ones.

◆ combo()

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

◆ computed_value_Cmp_Confirm()

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

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

Parameters

left	the left operand of the Cmp
right	the right operand of the Cmp
relation	the compare relation

◆ conv_opt()

void conv_opt ( ir_graph * irg )

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

Parameters

irg the graph

◆ create_compilerlib_entity()

ir_entity* create_compilerlib_entity	(	char const *	name,
		ir_type *	mt
	)

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

◆ dead_node_elimination()

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 data structure 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.

◆ do_gvn_pre()

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

◆ do_loop_inversion()

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(...)).

◆ do_loop_peeling()

void do_loop_peeling ( ir_graph * irg )

Perform loop peeling on a given graph.

◆ do_loop_unrolling()

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.

◆ garbage_collect_entities()

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.

◆ inline_functions()

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

◆ normalize_n_returns()

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;

◆ normalize_one_return()

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;

◆ occult_consts()

void occult_consts ( ir_graph * )

This optimization finds values where the bits are either constant or irrelevant and exchanges them for a corresponding constant.

◆ opt_bool()

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

◆ opt_frame_irg()

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.

◆ opt_if_conv()

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.

◆ opt_if_conv_cb()

void opt_if_conv_cb	(	ir_graph *	irg,
		arch_allow_ifconv_func	callback
	)

Perform If conversion on a graph - callback version.

Parameters

irg	The graph.
callback	The predicate.

Like above, but let the caller decide about valid transformations by supplying a predicate function.

◆ opt_jumpthreading()

void opt_jumpthreading ( ir_graph * irg )

Perform path-sensitive jump threading on the given graph.

Parameters

irg the graph

◆ opt_ldst()

void 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

◆ opt_osr()

void opt_osr	(	ir_graph *	irg,
		unsigned	flags
	)

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

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.

◆ opt_parallelize_mem()

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

◆ opt_tail_rec_irg()

void 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

◆ optimize_cf()

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.

◆ optimize_funccalls()

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 optimization reads the irg_const_function property of entities, and sets the irg_const_function property of graphs.

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

◆ optimize_load_store()

void 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.

◆ optimize_reassociation()

void 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. constant inside the loop) values.

See Muchnik 12.3.1 Algebraic Simplification and Reassociation of Addressing Expressions.

◆ place_code()

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.

◆ proc_cloning()

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.

◆ 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.

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.

◆ scalar_replacement_opt()

void 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

◆ shape_blocks()

void shape_blocks ( ir_graph * irg )

Combines congruent blocks into one.

Parameters

irg	The IR-graph to optimize.

◆ unroll_loops()

void unroll_loops	(	ir_graph *	irg,
		unsigned	factor,
		unsigned	maxsize
	)

Perform loop unrolling on a given graph.

Parameters

irg	the IR-graph to optimize
factor	the unroll factor
maxsize	the maximum number of nodes in a loop

◆ value_not_null()

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

Returns true if the value n is known not be zero/null.

Parameters

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

Modules

Macros

Typedefs

Enumerations

Functions

Detailed Description

Macro Definition Documentation

◆ DEFAULT_CLONE_THRESHOLD

◆ osr_flag_default

Typedef Documentation

◆ arch_allow_ifconv_func

◆ check_alloc_entity_func

◆ opt_ptr

Enumeration Type Documentation

◆ osr_flags

Function Documentation

◆ can_replace_load_by_const()

◆ combine_memops()

◆ combo()

◆ computed_value_Cmp_Confirm()

◆ conv_opt()

◆ create_compilerlib_entity()

◆ dead_node_elimination()

◆ do_gvn_pre()

◆ do_loop_inversion()

◆ do_loop_peeling()

◆ do_loop_unrolling()

◆ garbage_collect_entities()

◆ inline_functions()

◆ normalize_n_returns()

◆ normalize_one_return()

◆ occult_consts()

◆ opt_bool()

◆ opt_frame_irg()

◆ opt_if_conv()

◆ opt_if_conv_cb()

◆ opt_jumpthreading()

◆ opt_ldst()

◆ opt_osr()

◆ opt_parallelize_mem()

◆ opt_tail_rec_irg()

◆ optimize_cf()

◆ optimize_funccalls()

◆ optimize_load_store()

◆ optimize_reassociation()

◆ place_code()

◆ proc_cloning()

◆ remove_phi_cycles()

◆ scalar_replacement_opt()

◆ shape_blocks()

◆ unroll_loops()

◆ value_not_null()