2016-07-24 - In IL: Largest of Two Numbers (if-else)

Last time we looked at IL branching Instructions. The simplest use of branching instructions is probably the If statement which allows the program to conditionally execute a set of instructions. If the condition is true then the program executes the code within the if block. Statements like this exist in most high level languages because they allow the program to make decisions about whether or not code should be executed. If statements can also have Else blocks which are only executed if the condition is false.

Let's look at a simple program that reports which of two numbers is the largest using if, else statements in C#.

Compile it and we get something like this.

The first few lines are things we've seen before. You have the stack size directive, the local variable declaration and then variable initialization. At line 69 is where things get interesting. We start by loading both local variables and then calling a branch less-than-or-equal instruction.

The target of the branch is encoded using a label. labels appear at the start of a line and ends with a colon. When the program is compiled into its binary form the branching instruction encodes the target as an integer offset from the branching instruction to the instruction marked with the given label. The IL disassembler generates a label for each instruction based on its offset from the start of the method. This is the IL_XXXX: that appears at the start of each line.

If we look past the branch instructions we will see two sets of instructions which print a formatted string to the console. This code is very similar to instructions to print the volume of a cylinder that we saw earlier except it uses Console.WriteLine to perform the formatting and not string.format. The first set of instructions prints "numberA ({0}) is larger than numberB ({1})" and the second prints "numberB ({0}) is larger than numberA ({1})". If we compare this to the original C# program we see these sets of instructions match the if and else blocks respectively.

From last time we know that ble.s will cause the program to jump if the second value it pops off the stack is less than or equal to the first value it pops off the stack. The target of the branch has the label IL_0021 which is on line 83. At this point in the program the stack and local variables would look like this.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
int32	17	0	int32	17
int32	96	1	int32	96

The first value popped off the stack will be 96 and the second will be 17. Since 17 is less than or equal to 96 the condition will be true and the program branches. The next instruction to be executed will be at line 83. The program will print out "numberB (96) is larger than numberA (17)" and then return.

The ble instruction checks if numberB <= numberA. If we compare this to the original program we see that this is the inverse of the if statement condition, why is that? If you think about it the if statement and branching are opposites. An If statement says "Execute this code if the condition is true" while a branch instruction says "Jump away from this code if the condition is true". So the compiler inverses the logic to better match the instructions.

If you compile this program in debug mode you will see that the un-optimized  version includes a greater-than comparison and then a branch false. This matches the original if statement better but requires more instructions. When running with optimizations on, the compiler tries to come up with the simplest set of instructions that functionally match the original program. This is also why both sets of instructions contain their own return instruction instead of a common return instruction which would have required the if set to end with a branch back to a point past the else instructions.

Next time we are going to do the same thing with three numbers.

2016-07-02 - I Dream of School

I haven't been in school for years but for some reason I still have the occasional school dream. Dreams where I'm late to class, didn't study, or got lost in the school. Things that I have absolutely no reason to worry about and yet my brain still brings them up. The weirdest part is that in the dreams I start buying into the idea of being in back in school.

I remember one dream recently where I was in class and couldn't find my textbook. I started thinking I should get a locker so I always know where my books. The idea of being back in school seemed completely normal and my brain started problem solving the issue. Then I woke up and realized I don't have to go to school. None of this is relevant to me and it doesn't matter anymore.

I want to realize I am having a school dream while I am having it so I can run out of the class screaming "Screw you guys, I don't have to be here". That would be fun.

2016-06-18 - In IL: Branching Instructions

Conditional logic is what allows a program to appear as though it's making decisions. Certain parts of code are executed only if specific conditions are met. In higher level programming languages this would be handled by if, switch, or select statements. In IL these decisions are handled by branching instructions. Instructions that change the next instruction to be executed if certain conditions are true.

Generally instructions are executed one after the other. A branching instruction causes a jump. Instead of executing the next instruction it jumps to the instruction indicated by the branching instruction. It then continues to executes instructions after that point until another branching instruction is found.

br (BRanch)

The unconditional branch instruction always jumps to the instruction indicated by its argument.

Instruction	Description	Binary Format
br.s<target>	Short branch unconditional	0x2B <int8>
br	Branch unconditional	0x38 <int32>

brfalse (BRanch FALSE), brtrue (BRanch TRUE)

Pops a single value off of the stack. The brfalse instruction jumps to the instruction indicated by its argument if the value is 0. The brtrue instruction jumps to the instruction indicated by its argument if the value is nonzero.

The brfalse instruction is aliased as brnull (BRanch NULL) and brzero (BRanch ZERO). The brtrue function is aliased as brinst (BRanch INSTance)

Instruction	Description	Binary Format
brfalse.s<target>	Short branch if false (brnull.s, brzero.s)	0x2C <int8>
brtrue.s<target>	Short branch if true (brinst.s)	0x2D <int8>
brfalse	Branch if false (brnull, brzero)	0x39 <int32>
brtrue	Branch if true (brinst)	0x3A <int32>

beq (Branch EQual), ceq (Compare EQual)

Pops two values off of the stack, and compares them. The branching instruction jumps to the instruction indicated by its argument if they are equal. The compare instruction pushes 1 onto the stack if they are equal and 0 otherwise.

Instruction	Description	Binary Format
beq.s <target>	Short branch if values are equal	0x2E <int8>
beq <target>	Branch if values are equal	0x3B <int32>
ceq	Compares if values are equal	0xFE 01

bge (Branch Greater-than or Equal)

Pops two values off of the stack, and compares them. The branching instruction jumps to the instruction indicated by its argument if the second value popped is greater than or equal to the first.

Instruction	Description	Binary Format
bge.s <target>	Short branch greater than or equal	0x2F <int8>
bge.un.s<target>	Short branch greater than or equal unsigned	0x34 <int8>
bge	Branch greater than or equal	0x3C <int32>
bge.un	Branch greater than or equal unsigned	0x41 <int32>

bgt (Branch Greater-Than), cgt (Compare Greater-Than)

Pops two values off of the stack, and compares them. The branching instruction jumps to the instruction indicated by its argument if the second value popped is greater than the first. The compare instruction pushes 1 onto the stack if the second value popped is greater than the first and 0 otherwise.

Instruction	Description	Binary Format
bgt.s <target>	Short branch greater than	0x30 <int8>
bgt.un.s<target>	Short branch greater than unsigned	0x35 <int8>
bgt	Branch greater than	0x3D <int32>
bgt.un	Branch greater than unsigned	0x42 <int32>
cgt	Compare greater than	0xFE 02
cgt.un	Compare greater than unsigned	0xFE 03

ble (Branch Less-than or Equal)

Pops two values off of the stack, and compares them. The branching instruction jumps to the instruction indicated by its argument if the second value popped is less than or equal to the first.

Instruction	Description	Binary Format
ble.s<target>	Short branch less than or equal to	0x31 <int8>
ble.un.s<target>	Short branch less than or equal to unsigned	0x36 <int8>
ble	Branch less than or equal to	0x3E <int32>
ble.un	Branch less than or equal to unsigned	0x43 <int32>

blt (Branch Less-Than), clt (Compare Less-Than)

Pops two values off of the stack, and compares them. The branching instruction jumps to the instruction indicated by its argument if the second value popped is less than the first. The compare instruction pushes 1 onto the stack if the second value popped is less than the first and 0 otherwise.

Instruction	Description	Binary Format
blt.s<target>	Short branch less than	0x32 <int8>
blt.un.s<target>	Short branch less than unsigned	0x37 <int8>
blt	Branch less than	0x3F <int32>
blt.un	Branch less than unsigned	0x44 <int32>
clt	Compare less than	0xFE 04
clt.un	Compare less than unsigned	0xFE 05

bne (Branch Not Equal)

Pops two values off of the stack, and compares them. The branching instruction jumps to the instruction indicated by its argument if they are not equal.

Instruction	Description	Binary Format
bne.un.s<target>	Short branch unequal unsigned	0x33 <int8>
bne.un	Branch unequal unsigned unsigned	0x40 <int32>

and, or, xor, not

These instructions perform the specified bitwise action on values popped from the stack. The not instruction takes a single value while the rest take two.

Instruction	Description	Binary Format
and	Bitwise and	0x5F
or	Bitwise or	0x60
xor	Bitwise exclusive-or	0x61
not	Bitwise complement	0x66

Next time we will look at if statements and how they get represented in IL.

2016-05-28 - Every Programming Language is Alright

I love programming languages. I want to learn as many programming languages as I can. I find all the differences between languages to be fascinating. The way two similar languages choose to focus on different things. The different way languages solve the same problem. While reading about programming languages I sometimes come across very general comparisons. Language Y is better than Language X. Language Y sucks, use Language Z instead. These kind of statements bug me because they miss the point of why multiple languages exist.

There are very few accidental languages. No one has ever been bashing their keyboard and went "Woops, I made a compiler" or "Damn, I inadvertently wrote a language specification". These things are difficult and very complex so people only put the time and effort into making them if they actually want them to exist for some reason. Languages also only become popular if people want to use them for some reason. It's those reasons which are the key.

If you look at why different programming languages exist you will often find that their creators wanted to solve a particular type of problem and felt that the existing languages weren't suitable for doing so. C was created to make it easier to develop operating systems. Basic was designed to make it easier for non-mathematicians to program. The multitude of web frameworks exist to try and find an easy way of making web applications. The problem that a language was created to solve should be the focus of most comparisons.

Language Y is better at solving A Problems than Language X. Language Y sucks at solving B Problems, use Language Z instead. There are no languages that are good at solving all problems and there are no languages that aren't good at solving any problems. By giving context to the comparison it becomes less general and more specific.