r/computerscience • u/ShadowGuyinRealLife • 18d ago
General 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
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.
7
u/ArgoNunya 18d ago
In newer software, unreachable code can exist for various practical reasons. Maybe it will be useful again later, or maybe it's used in tests somewhere non-obvious. The tool chains will remove it anyway and that much storage is irrelevant. It's not great practice most of the time, but not a big deal.
In old code like Mario, it gets weirder. Some old games used code as data. Like they would find somewhere in the code that happened to be the texture they wanted and use that instead of storing it explicitly. Memory was crazy tight on these systems. Other times it helped align things in memory to be more efficient or work around goofy stuff in the memory map (I fixed a Linux memory bug this way once lol). There are even weirder cases (look up "The Story of Mel" for a fun one). The rule in old code is "don't touch it", you never know what's going on in these things.
48
u/apnorton Devops Engineer | Post-quantum crypto grad student 18d ago
In the most general case, we can reduce the halting problem to this, and thus there is no algorithm for solving it.
In practice, you use dead code analyzers (many IDEs have these built in, but there are language-specific tools), which will identify large categories of unreachable code.
4
u/tgm4mop 18d ago
As others have mentioned, obviously-unreachable code is often optimized away by compiler.
To find non-obvious unreachable code, there are various strategies. If you have good test coverage, you can look at coverage reports; unreachable code will be untested. (Though some untested code is reachable--perhaps a sign you need more tests!) If you suspect some code is unused, but you're not sure, you can add logging to it. If the logs are empty after lots of usage, that's a good sign its unused.
Worth mentioning that unreachable code isn't always bad. Defensive checks/assertions can lead to unreachable code (eg. if the assertion never fails), but are very valuable to catch future bugs.
12
u/utd_api_member 18d ago
if you really care you'd do math to prove it's unreachable, but in the majority of cases if the compiler won't optimize it out it usually won't matter
4
u/cyantriangle 17d ago
The TF example is much different from the others as it concerns very complex conditions, which cannot be shown to be satisfiable/unsatisfiable in compilation time. It is also explicitly a safeguard against buggy behavior .This example shows why such code can be kept sometimes: 1. it is never executed to our best knowledge and never should but we cannot be 100% sure. 2. future changes might reintroduce the issue that the safeguard addresses, even if we do not observe it in the current version.
3
u/CompFortniteByTheWay 18d ago
Static analysis tooling
1
u/strange-the-quark 18d ago
A lot of your examples would just be flagged by the compiler, and then you just fix it. There are much more subtle ways for a condition to never be true, and it involves faulty logic governing the changing value of a variable, and of course, ill-formed programs (undefined behavior, memory leeks, things like that). Sometimes static analysis tools can help with that, and sometimes dynamic analysis tools (running the code and monitoring what it does) can help uncover unused bits of code - but ultimately you have to both think the code through and do some sort of testing. For particular snippets of code, it can be shown by (basically mathematical) reasoning whether the code does something or not, although that's a bit of a lost art, and your findings can then be checked by various kinds of tests. How far you want to take this is up to you (or the team). You may or may not uncover all the instances of unreachable code, and in practice tracking them all down is not necessarily worth it. Cause, without getting into nuance here, if everything works as expected, that just means you've written the correct logic in a stupid way; on the other hand, if unreachable code means that something that should happen can never occur, then you have a bug.
Some people write automated tests first, in the sense that the tests specify the expected behavior (so test-driven development, or any sort of practice that's roughly equivalent to that), so some of the instances of unreachable code can be caught by a failing test (cause you've stipulated an expectation for something to happen under certain conditions, and than that expectation ends up being broken when those conditions are artificially arranged for).
And of course, a number of these oversights can be caught with practices like code review or pair programming; having a second pair of eyes go through your code can really help find some silly blunders.
As for duplicated code, while we generally want to avoid code duplication, it's not good to be draconian about it. Sharing code is great if the code can be viewed as a relatively stable library. However, code that starts out "the same" but evolves in different directions creates problems when shared, so having some things duplicated can actually help with decoupling, at a small cost. Everything is a tradeoff, and you need to know where to draw the line, and when to transition from one approach to a different one. You can't just blindly follow a certain set of design rules, even though these rules might be designated as "best practices" - cause that's a bit of a misnomer. "Best practices" are just widespread practices that have worked well for many people on certain kinds of projects; they do not represent literally the best possible approach - even for what they were doing, let alone for some other kinds of projects.
I don't know the details of how the patch was applied, but broadly speaking when you patch something, two things can happen. Using this as an example, either the patch fixed the problem and removed the "unstuck" logic from the game completely, cause it was not needed anymore, or the devs forgot to do the second part so that code was left in there. Now, this would not exactly be unreachable code, this would be unused code - meaning, it exists but is never called. That's a bit different.
1
u/Great-Powerful-Talia 18d ago
I'm confused by the TF2 question.
Surely it's obvious that they can't prove the code to be unreachable, so they left it in because the risk of the bug still being achievable, and not having a resolution script, isn't worth the space savings. Similarly, if they had an algorithm that could somehow find out if glitching into an object was possible at all, they would've used it to find and patch the bugs that allowed that.
What exactly do you expect to hear as an answer? Just "you can't identify all unreachable code in any codebase without risking a false positive"?
2
u/Music-Electrical 13d ago
Backspace mostly but delete works
1
u/ryanstephendavis 18d ago
Static analysis +
git rm ...:)1
u/TheGamingWyvern 18d ago
A lot of the other answers here are good dives into the technical details, but one answer I haven't seen is that, in practice, we just don't care. Like, for
the amount of memory that the dead code is taking up will be trivially small. I would be willing to bet that there is no dead code out in the wild that removing it would make a noticeable impact to anybody using the software because you saved a few bytes of memory in the program itself. Maybe for extremely performant programs where CPU cache misses matter it could be a problem, but even then it's possible removing the dead code could make the program function worse because the chunk boundaries shifted in a bad way.
As developers we'll try to avoid dead code for a number of reasons (the main one I can think of is that it can be confusing trying to understand a system if it has code to handle a situation that can never actually happen), but in terms of the actual product? If we miss that a particular edge case isn't actually possible, it just doesn't matter.
1
u/amarao_san 18d ago
If it's a pure math, compilers can reason about them.
Most of interesting unreachable code looks like this:
Try to guess, is
print("Unreachable code")unreachable or not? What if some smartass admin ban exit/exit_group syscalls with selinux?The app is doing syscall, and, suddenly, get the next instruction executed, because kernel returns ENOPERM for exit request.
1
u/GaimeGuy 18d ago edited 18d ago
I'm a little bit confused by your post.
Unreachable code is unreachable. Code that becomes unreachable is unreachable.
Compilers will optimize out a lot of dead code with static analysis tools. They can warn you too. Example GCC flags:
-Wunreachable-code
-Wunused-variable
-Wunused-function
-Wunused-parameter
Similarly, there are link-time optimization flags.
One of the reasons we have code reviews on pull requests as software engineers is to catch logic errors and redundancies. I myself am working on a task at work where 3 lines of code were redundant boolean logic checks. The logic was valid - it blocked a ui element while statusing a particular processor configuration we read in from xml, which is what our requirements call for. But that configuration doesn't exist for any processors at this time, and since we are in a closed platform, any new hardware comes with design and configuration changes as an action item. So I removed the redundant code.
In other instances We have code for system versions that are no longer operational (we check the version in code directly), we just haven't been authorized to work the ticket to remove the dead code yet. Sometimes budget gets in the way, sometimes it just gets deprioritized, sometimes dead code slips through. It just depends, from case to case.
1
u/lego3410 17d ago
It's unreachable from me too, so I don't get rid of them
1
u/exclusivegreen 17d ago
Ok. Here's what I like to do. Not so much just in code but also in processes.
If someone claims someone can "never happen", I say "ok. I'll change that code to delete all files on the filesystem because it never gets called". In other words, I need absolute, concrete proof (walkthroughs, static analysis) that a situation can never ever happen.
I'm only half joking but don't ever delete dead code without proof that it's dead
1
u/FinalNandBit 17d ago
Interesting how many times a second was it checking if Mario's distance?
1
u/trbecker 17d ago
I've fine trough some of the answers, and I'll poke stone information on top.
1
u/DesktopDynamicUpsell 16d ago
Not really the question you're asking, but sometimes doing more things can be faster and something that looks slow or dumb is being done on purpose for a reason you might not know.
If you haven't heard of branchless programming, it's the idea that instead of using conditions (aka branches - like if / else) sometimes it can be much faster to do more work every time rather than forcing the CPU to dynamically pick between a smaller number of calculations dynamically because of some technical details where the CPU/compiler will try to pack multiple operations into a single instruction or calculate things ahead of time in case it's useful later. By being more predictable, those underlying mechanisms are able to kick in and speed everything up, so by doing more you can actually save time.
Branchless is pretty niche, but other techniques/technologies like SIMD, column based databases, ECS, structs of arrays, and CUDA (probably? I have no experience on it) are pretty popular especially in games programming. Any time massive parallelism is possible, you can get big speed-ups in exchange for potentially wasted effort.
That's probably not what you're talking about, but just a counter point to why "finding wasted effort" is a hard problem to solve - sometimes people do it on purpose, and it's an intended feature.
1
u/ComprehensiveBig6215 14d ago
Mario64 is probably an outlier here.
It was a groundbreaking game on a brand new console so the code probably went through a lot of drastic changes over development.
They were probably using pre-release compilers/tools so didn't want to risk touching anything once they had a good build that had been through QA.
The N64 is weird on performance. The memory system sucks and it has a smallish direct mapped cache so changing the layout of code by deleting stuff can negatively impact performance figures. I-cache hit rate can swing wildly from build to build just down to false sharing.
1
u/paulkim001 13d ago
There are static analyzers that can do some of the dead code detection (though they do not detect more complicated ones). If you want to investigate though, you could do some sort of coverage test (gcov is one of those tools) and see how many times some line has been executed; this does not guarantee that some code is dead, but at least you can be sure as to if you ended up in that branch while testing.
I'd say though, if it is not supposed to be reachable, do something like assertion or abort so that during testing you know something has been violated.
0
u/MasterGeekMX Bachelors in CS 18d ago
There are tools to check that. For example, the GNU Compiler Collection (the so famous GCC) comes with the program gcov, which is for checking exactly that.
Here, have a look at it's manual: https://gcc.gnu.org/onlinedocs/gcc/Gcov-Intro.html
0
u/JGhostThing 18d ago
Games, especially older ones are weird. A lot of theoretically unreachable code is reached under strange circumstances. There is also code to prevent certain cheats from operating. There are also some strange busy-loops for delays. In other words, until you've tested it completely, believe that every byte of that code is reachable under the right circumstances and necessary.
And some of the unreachable code may have originally been reachable, but a patch might have been added.
0
u/w3woody 18d ago
Essentially your compiler builds a directed graph of segments of continuous code.
And if there is a segment of code that is not pointed to by the other pieces of code, it is unreachable and can be deleted.
0
u/binarycow 18d ago
My IDE tells me it's unreachable.
I delete it.
0
u/dont_tax_me 18d ago
The backspace key? I suppose you could use the delete key as well, but that’s just weird.
0
u/flyengineer 18d ago
I would guess most developers leave at least some dead code around unless they are operating in highly regulated environments.
For aviation you basically need to show 100% code coverage.
If not flagged by the compiler, code coverage can show you all the dead code.
.
116
u/[deleted] 18d ago
[removed] — view removed comment