#include

g/computerscience

ago

public

earned

reactions

How Do Programmers Get rid of Unreachable Code?

When I say unreachable code, I mean parts of the code which have no control path that can reach it.

My inspiration for this is someone who had analyzed the assembly of Mario 64. One oddity is a lot of code that is unnecessarily duplicated or it performs calculations that are then thrown out leaving the memory, registers, and flags in the same state as they would be if the "throw away" calculations were replaced with NOPs. The values these "do nothing" calculations read from are already cached so they don't even change what's in the cache. Another funny feature was having a low poly model that used few triangles when Mario was far from the camera, but it's far cheaper to always render the regular model than check how far he is even if the low poly model is displaced. The inspiration for this post, is a check to see if an object is within 12K units of the camera and not move objects if they are out of range. But because of the way the levels are designed, unless someone ever discovers an arbitrary code execution glitch (which doesn't seem to exist for this game unlike some other N64 games), every object will always be within limits. This check might as well not exist and the code for dealing with out-of-range objects can't be reached!

When I use // (Stuff) in my examples, I don't mean a comment that says "(stuff)" I just mean a block of code that depends on things like process state or user input. Just imagine thousands of lines with the possibility of changing global variables.

Example 1

int n = 2 + 1;

if
(n == 4) {
goto UNREACHABLE

// unreachable
}

Ok that was easy to see it's unreachable.

Example 2

#include
<math.h>

float x = sqrt(2);

if
(x > 5) {
goto UNREACHABLE

// unreachable
}

What about this? Well, x is never going to be bigger than 5.

Example 3

int d = 0;

// (stuff)
if
(d == 4) {
goto Fun1
}

Well, since (stuff) might change d, this might be true at some point. So far examples 1 and 2 were unreachable and 3 could be reachable depending on what (stuff) does.

Example 4

int n = 2 + 1;

// (stuff)
if
(n > n) {
goto UNREACHABLE

// unreachable
}

Even though (stuff) can change n, this can't ever be true.

But some things in normal maths don't apply to modular arithmetic.

Example 5

long n = 4294967295;

// (stuff)
if
(n > (n+1)) {
goto fun2
// Logically Identical to check if n= 4294967295
}

Well n can never be bigger than (n+ 1) right? I wanted to use int for integer but I was told my example needed long or I'd need to come up with different numbers. If n= 4294967295, which is 2\^32-1, then (n+1) is 0. Although the overflow flag in the processor will be triggered when evaluating (n+1), this doesn't matter. Checking to see if n was the largest possible unsigned long integer, which is 4294967295, would also transfer the program to fun2 if n was 4294967295. So even checking if the statement can be true for math doesn't mean it can't be true in the control flow.

Example 6

long n = 0;

// (stuff)
if ((n/10) > 500000000) {
goto UNREACHABLE

// unreachable
}

No matter what (stuff) does to n, the division by 10 will mean this cannot be reached. 429,496,729 is still smaller than 500,000,000.

Example 7

long n = 0;

// (stuff)
long FiveHundredMillionTimesTen = 500000000 * 10
if (n > FiveHundredMillionTimesTen) {
goto fun3
}

FiveHundredMillionTimesTen is 705,032,704. (Stuff) can change n to a number from 0 to 4,294,967,295 so n can be bigger.

Example 8

long n = 0;

// (stuff)
if
(n > (n * n + 9) * (n) *(n+3)) {
Goto fun4
}

I was going to try to find small values of n that would evaluate to true, but MS excel cried. 4294967295 is larger than 4294967276 and presumably there are lower values this is true.

Example 9

goto NEXT;
UNREACHABLE:
// (stuff)
NEXT;

If no code can reach "UNREACHABLE" then it just gets skipped.

Here is another one https://en.wikipedia.org/wiki/Unreachable_code#goto_fail_bug

if ((err = SSLHashSHA1.update(&hashCtx, &serverRandom)) != 0)
goto fail;
if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
goto fail;
goto fail;
if ((err = SSLHashSHA1.final(&hashCtx , &hashOut)) != 0)
goto fail;

// ...

fail:
SSLFreeBuffer(&signedHashes);
SSLFreeBuffer(&hashCtx);
return err;

I changed one thing from the original code example on Wikipedia for legibility. The two goto fail means the final check is never made.

Then there are more complicated examples. So for example the Super Mario Bros has 207 unused bytes that can never be executed, or read meaning that 0.63% of the code is superfluous. This was discovered by someone I can't credit because the automod thinks trying to say his name is a violation of rule 4.

Mario 64 as I mentioned tried to not move objects too far from the camera, but in-game everything is always too close so the check always says to move objects every frame.

Team Fortress 2 has some logic to "unstuck" players characters who go inside parts of map geometry by detecting stuck players and trying to move them in various directions which usually works, although if the nudge is too short they'll stay stuck. During a time when a bug allowed people to walk on top of maps like Dustbowl, this also allowed players to get stuck inside props so the "unstuck" logic was needed. When this bug and two others got patched out, I want to say 2010, the "unstuck" logic could not be reached. Even if the server allowed a client to connect with SVCheats on which allows all sorts of crazy things, it was not possible to get stuck on any official map. So the "unstuck" logic was unreachable and just sitting in memory doing nothing. Then in 2013 SolidOb of the SteamPipe version Source Engine got broken and in some maps, even official ones like Upward, players can get stuck and trigger it again.

The examples 1 to 9 I gave were just silly that just needs a bit of math to realize the code is unreachable. But how do programmers get rid of unreachable code in a more general case? In the case of the goto fail bug, I guess someone needed to do code review. For Super Mario Bros and Mario 64, the game worked and there was no point in trying to save memory as long as the game fit in available memory, but if they had more time I wonder what could be done to make sure there was no unreachable code. TF2's "unstuck" logic is an odd case in that the game was never intended to allow players to get stuck, but it was used until 3 separate bugs were patched out and for awhile it was just unreachable. If before release they realized any of the ways it would be reached, they would have patched out those possibilities, but they'd probably still release the game with the code even if it was patched to the point it was unreachable. And now it's reachable again.
#technology
source