Optimization Topics - Revision history

Root: Redirected page to ist:Optimization Topics

2018-12-06T18:20:02Z

Redirected page to ist:Optimization Topics

← Older revision		Revision as of 18:20, 6 December 2018
Line 1:		Line 1:
	~~{{NAVCompiladores}}~~		#REDIRECT [[ist:Optimization Topics]]
	~~{{TOCright}}~~
	~~== Basic Blocks ==~~

	~~Instruction sequence where control flow starts at the first instruction and ends at the last, without jumps (except at the last instruction).~~

	~~Transformations in a basic block maintain the block semantics (considered as an atomic entity).~~

	~~== Optimization Levels ==~~

	* User - algorithm- and application-level optimizations
	* Generic - considers intermediate code (processor-independent)
	* Peephole - window over a series of consecutive instructions
	* Local - optimization within a basic block
	* Inter-block (information flow between blocks, mainly cycles)
	* Global - multiple jumps (jumps to jumps, jumps to the next instruction)

	~~= Machine-independent optimizations =~~

	~~== Constant folding ==~~

	~~Direct evaluation of expressions using only literal and known values:~~
	~~<c>~~
	~~int x = (int )malloc(1024 * 4);~~
	~~int y = 3;~~
	~~int z = 20 * y + 10;~~
	~~</c>~~

	~~Becomes:~~
	~~<c>~~
	~~int x = (int )malloc(4096);~~
	~~int y = 3;~~
	~~int z = 70;~~
	~~</c>~~

	~~== Elimination of Common Subexpressions ==~~

	~~Using temporary variables to store common results:~~
	~~<c>~~
	~~d = c * (a + b)~~
	~~e = (a + b) / 2~~
	~~</c>~~

	~~Becomes:~~
	~~<c>~~
	~~t = a + b~~
	~~d = c * t~~
	~~e = t / 2~~
	~~</c>~~

	~~== Cycles / Loops ==~~

	~~=== Loop unrolling ===~~
	~~<c>~~
	~~for (i = 1; i < n; i++)~~
	~~a[i] = b[i] + 10;~~
	~~</c>~~

	~~Becomes:~~
	~~<c>~~
	~~for (i = 1; i < (n/4)*4; i+=4) {~~
	~~a[i] = b[i] + 10;~~
	~~a[i+1] = b[i+1] + 10;~~
	~~a[i+2] = b[i+2] + 10;~~
	~~a[i+3] = b[i+3] + 10;~~
	}

	~~// rest of the cycle~~
	~~for (; i < n; i++)~~
	a[~~i] = b~~[~~i] + 10;~~
	~~</c>~~

	~~=== Moving invariant code ===~~
	~~<c>~~
	~~for (i = 1; i < n; i++) {~~
	~~a[i] = b[i] + c * d;~~
	~~e = g[k];~~
	}
	~~</c>~~

	~~Becomes~~:
	~~<c>~~
	~~t = c * d;~~
	~~for (i = 1; i < n; i++) {~~
	~~a[i] = b[i] + t;~~
	}
	~~e = g[k];~~
	~~</c>~~

	~~=== Variable induction ===~~
	~~<c>~~
	~~for (i = 1; i < n; i++)~~
	~~k = i * 4 + m;~~
	~~</c>~~

	~~Becomes:~~
	~~<c>~~
	~~k = m;~~
	~~for (i = 1; i < n; i++)~~
	~~k = k + 4;~~
	~~</c>~~

	~~=== Other ===~~

	~~= Machine-dependent Optimizations =~~

	~~== Algebraic Simplification ==~~
	~~<asm>~~
	~~xor eax,eax~~
	~~</asm>~~

	~~instead of~~
	~~<asm>~~
	~~mov 0,eax~~
	~~</asm>~~

	~~== Strength Reduction ==~~
	~~<c>~~
	~~x << 2 + x~~
	~~</c>~~

	~~instead of~~
	~~<c>~~
	~~x * 5~~
	~~</c>~~

	~~== Instruction Reordering ==~~

	~~Reorder independent instructions in order to avoid register spilling.~~

	~~== Other ==~~

	~~== Exercises ==~~

	* [[Optimization Topics~~/Exercise 01\|Exercises 01]]~~
	* [[Optimization Topics/Exercise 02\|Exercises 02]]
	* [[Optimization Topics/Exercise 03\|Exercises 03]]
	* [[Optimization Topics/Exercise 04\|Exercises 04]]
	* [[Optimization Topics/Exercise 05\|Exercises 05]]
	* [[Optimization Topics/Exercise 06\|Exercises 06]]

	~~[[category:Compiladores]]~~
	~~[[category:Ensino~~]]

Root: /* Strength Reduction */

2015-03-03T08:23:08Z

Strength Reduction

← Older revision		Revision as of 08:23, 3 March 2015
Line 116:		Line 116:

	== Strength Reduction ==		== Strength Reduction ==
			<c>
	x << 2 + x		x << 2 + x
			</c>

	instead of		instead of
			<c>
	x * 5		x * 5
			</c>

	== Instruction Reordering ==		== Instruction Reordering ==

Root: /* Algebraic Simplification */

2015-03-03T08:22:44Z

Algebraic Simplification

← Older revision		Revision as of 08:22, 3 March 2015
Line 106:		Line 106:

	== Algebraic Simplification ==		== Algebraic Simplification ==
			<asm>
	xor eax,eax		xor eax,eax
			</asm>

	instead of		instead of
			<asm>
	mov 0,eax		mov 0,eax
			</asm>

	== Strength Reduction ==		== Strength Reduction ==

Root: /* Machine-independent optimizations */

2015-03-03T08:22:05Z

Machine-independent optimizations

← Older revision		Revision as of 08:22, 3 March 2015
Line 21:		Line 21:

	Direct evaluation of expressions using only literal and known values:		Direct evaluation of expressions using only literal and known values:
			<c>
	int x = (int )malloc(1024 * 4);		int x = (int )malloc(1024 * 4);
	int y = 3;		int y = 3;
	int z = 20 * y + 10;		int z = 20 * y + 10;
			</c>

	Becomes:		Becomes:
			<c>
	int x = (int )malloc(4096);		int x = (int )malloc(4096);
	int y = 3;		int y = 3;
	int z = 70;		int z = 70;
			</c>

	== Elimination of Common Subexpressions ==		== Elimination of Common Subexpressions ==

	Using temporary variables to store common results:		Using temporary variables to store common results:
			<c>
	d = c * (a + b)		d = c * (a + b)
	e = (a + b) / 2		e = (a + b) / 2
			</c>

	Becomes:		Becomes:
			<c>
	t = a + b		t = a + b
	d = c * t		d = c * t
	e = t / 2		e = t / 2
			</c>

	== Cycles / Loops ==		== Cycles / Loops ==

	=== Loop unrolling ===		=== Loop unrolling ===
			<c>
	for (i = 1; i < n; i++)		for (i = 1; i < n; i++)
	a[i] = b[i] + 10;		a[i] = b[i] + 10;
			</c>

	Becomes:		Becomes:
			<c>
	for (i = 1; i < (n/4)*4; i+=4) {		for (i = 1; i < (n/4)*4; i+=4) {
	a[i] = b[i] + 10;		a[i] = b[i] + 10;
Line 64:		Line 69:
	for (; i < n; i++)		for (; i < n; i++)
	a[i] = b[i] + 10;		a[i] = b[i] + 10;
			</c>

	=== Moving invariant code ===		=== Moving invariant code ===
			<c>
	for (i = 1; i < n; i++) {		for (i = 1; i < n; i++) {
	a[i] = b[i] + c * d;		a[i] = b[i] + c * d;
	e = g[k];		e = g[k];
	}		}
			</c>

	Becomes:		Becomes:
			<c>
	t = c * d;		t = c * d;
	for (i = 1; i < n; i++) {		for (i = 1; i < n; i++) {
Line 79:		Line 86:
	}		}
	e = g[k];		e = g[k];
			</c>

	=== Variable induction ===		=== Variable induction ===
			<c>
	for (i = 1; i < n; i++)		for (i = 1; i < n; i++)
	k = i * 4 + m;		k = i * 4 + m;
			</c>

	Becomes:		Becomes:
			<c>
	k = m;		k = m;
	for (i = 1; i < n; i++)		for (i = 1; i < n; i++)
	k = k + 4;		k = k + 4;
			</c>

	=== Other ===		=== Other ===

Root at 16:09, 2 June 2012

2012-06-02T16:09:31Z

← Older revision		Revision as of 16:09, 2 June 2012
Line 123:		Line 123:
	* [[Optimization Topics/Exercise 03\|Exercises 03]]		* [[Optimization Topics/Exercise 03\|Exercises 03]]
	* [[Optimization Topics/Exercise 04\|Exercises 04]]		* [[Optimization Topics/Exercise 04\|Exercises 04]]
			* [[Optimization Topics/Exercise 05\|Exercises 05]]
			* [[Optimization Topics/Exercise 06\|Exercises 06]]

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]

Root at 16:02, 2 June 2012

2012-06-02T16:02:01Z

← Older revision		Revision as of 16:02, 2 June 2012
Line 116:		Line 116:

	== Other ==		== Other ==

			== Exercises ==

			* [[Optimization Topics/Exercise 01\|Exercises 01]]
			* [[Optimization Topics/Exercise 02\|Exercises 02]]
			* [[Optimization Topics/Exercise 03\|Exercises 03]]
			* [[Optimization Topics/Exercise 04\|Exercises 04]]

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]

Root at 18:47, 26 June 2010

2010-06-26T18:47:51Z

← Older revision		Revision as of 18:47, 26 June 2010
Line 1:		Line 1:
	{{NAVCompiladores\|{{TOCright}}}}		{{NAVCompiladores}}
			{{TOCright}}
	== Basic Blocks ==		== Basic Blocks ==

Root at 18:47, 26 June 2010

2010-06-26T18:47:31Z

← Older revision		Revision as of 18:47, 26 June 2010
Line 1:		Line 1:
	{{NAVCompiladores}}		{{NAVCompiladores\|{{TOCright}}}}
	{{TOCright}}
	== Basic Blocks ==		== Basic Blocks ==

Root at 18:09, 26 June 2010

2010-06-26T18:09:40Z

← Older revision		Revision as of 18:09, 26 June 2010
Line 1:		Line 1:
			{{NAVCompiladores}}
	{{TOCright}}		{{TOCright}}
	== Basic Blocks ==		== Basic Blocks ==

Root: /* Loop unrolling */

2010-06-04T16:43:15Z

Loop unrolling

← Older revision		Revision as of 16:43, 4 June 2010
Line 53:		Line 53:
	Becomes:		Becomes:

	for (i = 1; i < (n/4)*n; i+=4) {		for (i = 1; i < (n/4)*4; i+=4) {
	a[i] = b[i] + 10;		a[i] = b[i] + 10;
	a[i+1] = b[i+1] + 10;		a[i+1] = b[i+1] + 10;