## LSU EE 3755 -- Fall 2004-- Computer Organization

## LSU EE 3755 --OCT 18 Fall 2004 -- Computer Organization

## MIPS� Notes 5 -- More Procedure Code and Compiler

#procedure swap

#1. registers to program variables.

#2. Produce code for the body of the procedure

#3. Preserve registers across the procedure invocation

#�� swap(int v[ ], int k)

#�� {

#�� int temp;

#�� temp = v[k];

#�� v[k] = v[k+1];

#�� v[k+1] = temp;

#�� }

#� Swap

#� Register Usage

#�� $a0 : Address of array element v[0].

#�� $a1: index k.

#�� $t1 : k * 4 ; because array v element is integer which is 4byte long.

#�� $t1: v[k]� ;�� for swapping

#�� $t2: v[k+1] ;� for swapping

swap:

�� add $t1, $a1, $a1�� #� $t1 = k * 2;

�� add $t1, $t1,� $t1�� # �$t1 = k * 4;

�� add $t1, $a0, $t1�� #�� $t1 = v + (k *4)

�� #� $t1 has the address of v[k]

��

�� lw $t0,0($t1)�� # $t0 (temp) = v[k]�

�� # $t0 has the value of v[k]

�� lw $t2,4($t1)�� #� $t2 = v[k+1]

�� # $t2 has the value of v[k+1]

��

�� sw $t2,0($t1)�� # save the value of v[k+1] to address of v[k]

�� sw $t0,4($t1)�� # save the value of v[k] to address of v[k+1]

�� # so swapped

�� jr� $ra�� # return to calling routine

�# other way of doing this

�� # add $t1, $a1, $zero�� //only these two lines are different

�� # sll�� $t1,2�� //.........� k*4

�� # add� $t1, $a0, $t1�� // remaining are same

�� 

��

�� # lw $t0,0($t1)�� # $t0 (temp) = v[k]�

�� # $t0 has the value of v[k]

�� # lw $t2,4($t1)�� #� $t2 = v[k+1]

�� # $t2 has the value of v[k+1]

��

�� # sw $t2,0($t1)�� # save the value of v[k+1] to address of v[k]

�� # sw $t0,4($t1)�� # save the value of v[k] to address of v[k+1]

�� # so swapped

�� # jr� $ra�� # return to calling routine

�� # #� changing that� to� one instruction

�� #� sll $a1, 2�� // now we are using only one instruction

�� // instead of two instructions.

�� // code becomes short.

�� // is this better than above?

�� # add� $t1, $a0, $a1� //�� #� $t1 has the address of v[k]

�� // only above two are different

�� //�� remaining are same

��

�� # lw $t0,0($t1)�� # $t0 (temp) = v[k]�

�� # $t0 has the value of v[k]

�� # lw $t2,4($t1)�� #� $t2 = v[k+1]

�� # $t2 has the value of v[k+1]

��

�� # sw $t2,0($t1)�� # save the value of v[k+1] to address of v[k]

�� # sw $t0,4($t1)�� # save the value of v[k] to address of v[k+1]

�� # so swapped

�� # jr� $ra�� # return to calling routine

###� This is Why..

#�� main()� //� incomplete code.

#�� for (k = 1; k < 10; k++)� {

#� ��swap(v[], k);

#�� }

# procedure sort

# sort (int v[], int n)

# {

#�� int i, j;

#�� for(i = 0; i < n; i = i +1) {

#�� for (j = i -1 ; j > =0 && v [j] > v [j +1 ] ; j = j-1) { swap(v,j);}

#�� }

# }

## primitive way of sorting is shown below

##(slower than above one)

## sort (int v[], int n)

## {

##�� int i, j;

##�� for(i = 0; i < n; i = i +1) {

##�� for (j = 0; j <n; j = j+1) {

##�� if(v[j] > v[j+1])� swap(v,j);

##�� }

## }

�

#�� MIPS code for the first sort program

#�� Register usage :��

#�� $a0 : Address of array element v[0].

#�� $a1: Array size n

#�� $s0: index i for for loop

#�� $s1: index j for for loop

# saving registers

�� sort:��

�� addi $sp,$sp, -20� # make room on stack for 5 registers

�� sw� $ra,16($sp)�� #save $ra on stack

�� sw� $s3,12($sp)�� #save $s3 on stack

�� sw� $s2, 8($sp)�� #save $s2 on stack

�� sw� $s1, 4($sp)�� #save $s1 on stack

�� sw� $s0, 0($sp)�� #save $s0 on stack

�� #we save $s' registers.

�� #procedure call shouldn't modify $s' registers.

�� #we save $ra register.

�� #we call swap procedure, and we will modify $ra at that time.

#procedure body

�� move $s2, $a0�� # This is pseudo instruction .How do you do this?

�� move $s3, $a1�� # save the array size n($a1)� to $s3.

�� move $s0,$zero # index i for for loop ( i =0)

�for1tst:�� slt $t0, $s0,$s3�� # reg $t0 = 0 if $s0 >= $s3 (i>=n)

�� beq� $t0,$zero,exit1� # outside for loop conditon check.

�� addi $s1,$s0,-1� # set j = i -1 for second for loop.

for2tst:� ��slti� $t0,$s1,0�� # reg $t0 = 1 if $s1 <0 (j <0)

�� bne $t0,$zero,exit2

�� add $t1,$s1,$s1� # reg $t1 = j * 2

�� add $t1,$t1,$t1�� # reg $t1 = j * 4

�� add $t2,$s2,$t1�� # reg $t2 = v +(j * 4)//address of v[j]

�� lw $t3,0($t2)�� # reg $t3 = v[j]

�� lw $t4,4($t2)�� # reg $t4 = v[j + 1]

�� slt�� $t0,$t4,$t3�� # reg $t0 = 0 if v[j+1] >= v[j]

�� beg $t0,$zero,exit2

�� move $a0,$s2�� #1-st parameter of swap is v

�� move $a1,$s1�� #2 nd parameter of swap is j

�� jal swap�� # $ra will be modified by jal, $ra <=exit2+4.

�exit2:�� addi $s0,$s0, 1� # i= i +1

�� j for1tst�� # will be returned here after swap.

�

�� #now we restore saved $s' registers and $ra

�� #and adjust stack pointer.

exit1:�� lw $s0,0($sp)

�� lw $s1,4($sp)

�� lw $s2,8($sp)

�� lw $s3,12($sp)

�� lw $ra,16($sp)

�� addi $sp,$sp,20

�� jr� $ra�� # return to calling procedure.

#� Compiler

# Contents

# Optimization Introduction

# Steps in Preparing a Program

# Compiler Definitions

# High-Level Optimizations

# Low-Level Optimizations

# Compiler Optimization Options

# Use of Compiler Switches

#Lecture Goals

# Understand the Program Building and Compilation Process

#� Describe steps in program building and optimization, including

#� intermediate files (assembler, object, ...) and tool names (preprocessor,

#� compiler, etc.).

# Understand Specific Optimizations and Assumption Switches

#� Describe, work example, explain benefit.

# Understand Profiling

#� Steps, how performance is improved.

# Understand ISA and Implementation Options

#� How programmer chooses them, how compiler uses them.

# Understand how Programmers Use Compilation Options

#� Normal program development, high-performance programs, SPEC disclosure.

###################

# Optimization Introduction

# :Def: Optimization

# The optional steps in compiling a program that reduce the program's

#execution time, reduce the size of the program, or both.

# Typically, the only time optimization is NOT done is when a program

# is being debugged.

# In most cases, the programmer sets overall optimization effort (low,

#medium, high).

#When performance is very important the programmer can specify which

# specific optimizations to use.

# :Example:

# Data on a program that computes pi with and without optimization.

# System:�� SunOS sol 5.6 Generic_105181-31 sun4u sparc SUNW,Ultra-Enterprise

# Compiler: Sun WorkShop 6 2000/04/07 C 5.1

#Clock Frequency: 300 MHz

# Without Optimization

#� Size�� : 6408 bytes

#�� Run Time�� : 3.00 s

#� Instruction Count : 325,338,749

#� CPI�� : (/ (* 3.00 300e6) 325338749.0 ) = 2.7663

# With Optimization

#�� Size�� : 6340 bytes�� Smaller! (OK, only a tiny bit smaller.)

!�� Run Time�� : 1.65 s�� Faster!

!�� Instruction Count : 100,338,751

!�� CPI�� : (/ (* 1.65 300e6) 100338751.0) = 4.9333

# Reasons *not* to Optimize

# Percentage shows roughly how often reason applies.

# 95%� It makes debugging difficult, so don't optimize while debugging.

#�� This is true for almost everyone that uses a debugger.

#10%� It slows down compilation.

#�� Only important when there is a very large amount of code to

#�� recompile.� (Back in the 20th century when computers were slow

#�� this was important.)

#� 1%� Optimization introduces bugs.

#�� It does, but very rarely.

##############################

# Steps in Building a Program

# Typical Steps in Building a Program

#�� Pre-Process, Compile, Assemble, Link, Load

#�� pi.c ->�� pi.i� -> pi.s� ->� pi.o� -> pi

# These steps can all be automatically performed of the compiler

# driver. (cc, gcc, MS Visual Studio, etc.)

#:Sample: cc pi.c -o pi

# They can also be specified individually.

# More details appear below, compile is what we're interested in.

# Pre-Process

#� Load include files, expand macros.

#�� Typical pre-processor name: cpp

#� Input File: pi.c

#� Output File: pi.i� (High-Level Language)

# Compile

#�� Convert high-level language into assembly language.

#�� Typical compiler name: cc1 (not cc, or gcc, or Visual Studio)

#� Input File: pi.i

#� Output File: pi.s� (Assembly language)

# Assemble

#�� Convert assembly language in to machine language.

#�� Typical assembler name: as

#�� Input File: pi.s

#�� Output File: pi.o� (Object file containing machine code.)

# Link

#� Combine object files, libraries, and other code into executable.

#� Typical linker name: ld

#� Input File: pi.o

#� Output File: pi

# Load

#�� Copy executable into memory, link with shared libraries, and start.

#�� Loader name: exec system call.

#######################################

# Compiler Definitions

#� A program is compiled using� steps or /passes/.

#� The first pass reads the pre-processed high-level source code.

#�� The last pass produces assembly code.

#�� Between the first and last passes the program is in some

#�� intermediate representation.

#�� The way passes are defined and organized varies greatly from

#� compiler to compiler.

# :Def: Pass

#�� A step in compiling a program.� A pass usually looks at an entire function.

# :Def: Intermediate Representation

# The form of a program (sort of a special-purpose language) used internally

# by a compiler.� A compiler might use several intermediate representations.

# Typical Passes

# Parse

#�� Convert the source code to a high-level intermediate representation (H-IR).

#High-Level Optimization (Optional, may be done in several passes.)

#�� Also called front-end optimization.

#�� Modify H-IR to improve performance or reduce code size.

#� Reads and writes H-IR

# Low-Level Intermediate Representation (L-IR) Generation

#� Convert H-IR to a low-level intermediate representation (L-IR).

# Low-Level Optimization� (Optional, may be done in several passes.)

#�� Also called back-end optimization.

#�� Modify L-IR to improve performance or reduce code size.

# Register Assignment (Part of low-level optimization.)

#� Choose machine registers.

# Code Generation

#�� Convert L-IR to assembly code.

# Pigeonhole Optimizations� (Optional, may be done in several passes.)

#�� These are also called low-level optimizations.

#�� Modify L-IR to improve performance or reduce code size.

#� Some of these can be done at link time.

#:Def: Compiler Front End

# The parts of the compiler that do the parsing and high-level

# optimization passes.

# :Def: Compiler Back End

# The parts of the compiler that do the low-level optimization,

#register assignment, and code generation passes.

##############################

# High-Level Optimizations

# Easy high-level optimizations presented here.

#Some Easy-To-Explain Front-End Optimizations

# Dead-Code Elimination (DCE)

# Common Subexpression Elimination (CSE)

# Constant Propagation, Folding

# Dead-Code Elimination (DCE)

#� Removal of code which isn't used.

#� Yes, it happens.

# :Example:

# Code benefiting from DCE

# High-level code shown for clarity.� Most compilers will transform

# an intermediate representation.

# Before:

int

main(int argv, char� **argc)

{

� double i;�� double sum = 0;

� for(i=1; i<50000000;)

�� {

�� sum = sum + 4.0 / i;�� i += 2;

�� sum = sum - 4.0 / i;�� i += 2;

�� }

� printf("Performed %d iterations.� Thank you for running me.\n",i);

}

# After:

int

main(int argv, char **argc)

{

� double i;

� for(i=1; i<50000000;)

�� {

�� i += 2;

�� }

� printf("Performed %d iterations.� Thank you for running me.\n",i);

}

#� Note: Other optimizations would leave only the printf.

#� Common Subexpression Elimination

#� Remove duplicated code.

# Before:

� r = ( a + b ) / ( x + y );

� s = ( a + b ) / ( x - y );

# After:

� temp = a + b;

� r = ( temp ) / ( x + y );

� s = ( temp ) / ( x - y );

# Constant Propagation, Folding

#� The compiler performs whatever arithmetic it can at compile time

#�� rather than emitting code to perform the arithmetic at run time.

# Before:

� int sec_per_day = 60 * 60 * 24;

� int sec_per_year = sec_per_day * 365;

� some_routine(sec_per_day * x, sec_per_year * y);

# After:

� int sec_per_day = 86400;

� int sec_per_year = 31536000;

� some_routine(86400 * x, 31536000 * y);

#####################################

# Low-Level Optimizations

# Some Low-Level Optimizations

# This is not a complete list.

# Register Assignment

# Instruction Selection

# Scheduling

# :Def: Register Assignment

# Selection of which values will be held in registers.� Values

#not held in registers are stored in memory.

# Without Register Assignment Optimizations

# All values corresponding to variables (in high-level program) are

# written to memory (and not held in registers).� Intermediate results are

# held in registers.(accessing memory takes longer time than accessing regs.)

# With Register Assignment Optimization

# Registers are assigned to as many variables as possible, with priority

# given to frequently used variables.

#Advantage of Register Assignment Optimization

# Fewer memory writes and reads.(faster)

# :Def: Scheduling

# Re-arranging instructions to minimize the amount of time one instruction

# has to wait for another.

#For example, if an instruction takes a long time it will be started early

# so that other instructions will not have to wait for its result.

######################################

## Compiler Optimization Options

# Optimization options tell the compiler:

#� How much EFFORT to put into optimization.� E.g., -O2(do level 2 optimization)

#�� Which PARTICULAR optimizations to perform.� E.g., -fno-strength-reduce

#� (loop optimization)

#� The TARGET system the code will be running on.� E.g., -xultra2� (ultra2 machine)

#�� Whether to make certain ASSUMPTIONS about the code.

#�� Whether to use PROFILING data from a training run.

##Optimization EFFORT

# Most compilers have optimization levels.

# The higher the number, the more optimizations done.

# :Example:

# Optimization Levels for Sun Workshop 6 Compiler

#�� -xO [1|2|3|4|5]

#�� Optimizes the object code. Note the upper-case letter

#�� O.

#�� The levels (1, 2, 3, 4, or 5) you can use differ

#�� according to the platform you are using.

#�� ( SPARC)

#�� -xO1 Does basic local optimization (peephole).

#�� peephole: compiler is looking only small part of code

#�� and does optimization only for that part.

#�� if compiler is looking larger part of code,

#�� it may produce better code. but that kind of

#�� process takes more time and complicates.

#�� -xO2 Does basic local and global optimization.

#�� This is induction variable elimination, local

#�� and global common subexpression elimination,

#�� algebraic simplification, copy propagation,

#�� constant propagation, loop-invariant optimi-

#�� zation, register allocation, basic block

#�� merging, tail recursion elimination, dead

#�� code elimination, tail call elimination and

#�� complex expression expansion.

#�� : Any compiler Book will explain these.

#�� The -xO2 level does not assign global, exter-

#�� nal, or indirect references or definitions to

#�� registers. It treats these references and

#�� definitions as if they were declared "vola-

#�� tile." In general, the -xO2 level results in

#�� minimum code size.

#�� -xO3 Performs like -xO2 but, also optimizes refer-

#�� ences or definitions for external variables.

#�� Loop unrolling and software pipelining are

#�� also performed. The -xO3 level does not trace

#�� the effects of pointer assignments. When com-

#�� piling either device drivers, or programs

#�� that modify external variables from within

#�� signal handlers, you may need to use the

#�� volatile type qualifier to protect the object

#�� from optimization.� In general, the -xO3

#�� level results in increased code size.

#�� : loop unrolling : saving time at branch instruction.

#�� for(i=0;i<3;++i)�� s = s+i;

#�� becomes� :�� s = s+0;��

#�� s = s+1;

#�� s= s+ 2;

#�� longer code but no conditional branch.

#�� -xO4 Performs like -xO3 but, also does automatic

#�� inlining of functions contained in the same

#�� file; this usually improves execution speed.

#�� The -xO4 level does trace the effects of

#�� pointer assignments.� In general, the -xO4

#�� level results in increased code size.

#�� If you want to control which functions are

#�� inlined, see -xinline .

#�� -xO5 Generates the highest level of optimization.

#�� Uses optimization algorithms that take more

#�� compilation time or that do not have as high

#�� a certainty of improving execution time.

#�� Optimization at this level is more likely to

#�� improve performance if it is done with pro-

#�� file feedback.

## PARTICULAR Optimizations

# The levels specify sets of optimizations (like ordering the "Sport Package"

# for a new car).

# In contrast to optimization levels (-O3), the compiler can be told which

# particular optimizations to make.

# These are typically used by skilled programmers trying to get

# fastest code.

# Sun Workshop 6��

# Prefetch instructions read memory in advance, eliminating some cache

# misses .

#�� Cache is expensive but� a high speed memory.

# They can also increase

# cache misses or increase the time to access memory, hurting

# performance.� The compiler does not know if they will help or hurt.

#�� -xprefetch[=val],val

#�� (SPARC) Enable prefetch instructions on those architec-

#�� tures that support prefetch, such as UltraSPARC II.

#�� (-xarch=v8plus, v9plusa, v9, or v9a)

#�� Explicit prefetching should only be used under special

#�� circumstances that are supported by measurements.

## TARGET

# Specify exact type of machine code will be run on.

# What might be specified:

# ISA

# The exact instruction set used.

# Specifies not just the ISA family, but a particular variation.

# A poor choice will limit the number of machines code can run on.

# Implementation

# Specify the implementation code will run on.

# A poor choice will result in slower code.

# Cache

#Specify configuration of cache.

#A poor choice will result in slower code.

## Background

# Sun SPARC Architecture

#� Developed by Sun

# Major Versions:� v7, v8, v9 (first 64-bit SPARC ISA).

# Sub Version: v8plusa (v9 subset for 32-bit operating systems)

# Some Implementations

# UltraSPARC III Cu�� Implements v9, (On newer Suns.)

# UltraSPARC II�� Implements v9, (On sol.)

#:Example:

# Switches for Sun Workshop 6 Compiler.

#�� -xarch� ��Specifies ISA

#�� -xchip�� Specifies implementation.

#�� -xcache�� Specifies cache.

#�� -xtarget�� Specifies system. ISA/implementation and cache.

#�� -xarch Values:

#�� v7, v8a, v8, v8plus (v8 with 32-bit v9), v8plusa (v8 with 32 bit v9 etc.)

#�� -xchip=c

#�� c must be one of: generic, generic64, native, native64,

#�� old, super, super2, micro, micro2, hyper, hyper2,

#�� powerup, ultra, ultra2, ultra2i, 386, 486, pentium,

#�� pentium_pro, 603, 604.

## ASSUMPTIONS About the Program

# Compilers must generate correct code.

#� That is, the code must execute in the way specified by the

#� high-level language definition.

# Correct code can be slow.

# Some options tell the compiler to make assumptions about the program.

#� These assumptions would not hold for every program.

#� The compiled program runs faster ...

# ... and correctly if the assumptions are valid.

# Some switches specifying assumptions:

#gcc, Assume the program does not require strict IEEE 754 FP features.

# `-ffast-math'

#�� This option allows GCC to violate some ANSI or IEEE rules and/or

#�� specifications in the interest of optimizing code for speed.� For

#�� example, it allows the compiler to assume arguments to the `sqrt'

#�� function are non-negative numbers and that no floating-point values

#�� are NaNs.

# cc (Sun Workshop 6 Compiler) Assume certain pointers do not overlap.

#�� -xrestrict=f

#�� (SPARC) Treats pointer-valued function parameters as

#�� restricted pointers. f is a comma-separated list that

#�� consists of one or more function parameters, %all,

#�� %none.� This command-line option can be used on its

#� ��own, but is best used with optimization of -xO3 or

#�� greater.

#�� The default is %none. Specifying -xrestrict is

#�� equivalent to specifying -xrestrict=%all.

## PROFILING

# :Def: Profiling

# A compilation technique in which data taken from a sample run is used

# to guide compiler decisions.

# Branches occur frequently in code.� There is a performance penalty

# in taking a branch and so it's best if the compiler organizes code

# (rearranges the intermediate representation) so that branches are

# not taken as much as possible.� To do that the compiler needs to

# know how often an "if" or other condition (for which the branch is

# emitted) is true.� Only in a few cases can the compiler figure that

# out on its own, because, for example, "if" conditions depend on

# input data.� To obtain this useful information a two-step

# compilation process called profiling is used.� In the first step the

# code is compiled so that it writes branch information (more

# precisely basic block, covered later) to a file.� The program is run

# with typical input data, called the training input, and it writes

# the branch information to a file.� In the second step the compiler

# reads the information and uses that to better organize the code.

# Sun Profiling Compiler Switches

#�� -xprofile=p

#�� Collects data for a profile or use a profile to optim-

#�� ize.

#�� p must be collect[:name], use[:name], or tcov.

#�� This option causes execution frequency data to be col-

#�� lected and saved during execution, then the data can be

#�� used in subsequent runs to improve performance. This

#�� option is only valid when a level of optimization is

#�� specified.

## Use of Compiler Switches

# ISA

# Type of system all uses have. (IA-32 for PCs, SPARC for Sun users, etc.)

# Users can't normally run code compiled for a different ISA.

# Implementation

#� Type of system most users have.

#� Other users can run code, but won't run as fast.

# Optimization

#�� Select medium or high optimization level.

#� If market very sensitive to performance, use specific optimizations.

��