effect of goto on C++ compiler optimization

Question

What are the performance benefits or penalties of using goto with a modern C++ compiler?

I am writing a C++ code generator and use of goto will make it easier to write. No one will touch the resulting C++ files so don't get all "goto is bad" on me. As a benefit, they save the use of temporary variables.

I was wondering, from a purely compiler optimization perspective, the result that goto has on the compiler's optimizer? Does it make code faster, slower, or generally no change in performance compared to using temporaries / flags.

@MrLister: in C or in C++ ? In C I would say `goto` is necessary. In C++, I don't see any reason to use them... we already have exceptions! — Matthieu M., Apr 30 '12 at 15:40
@MatthieuM. *please*, don't use exceptions as glorified gotos. Exceptions are great for exceptional cases; errors and unexpected events. If you want to change control flow, don't use exceptions for that, but rather something specialized such as if statements or even gotos. There are rare cases in C++ where a goto is appropriate, and using an exception instead leads to runtime overhead and confusion. — , Apr 30 '12 at 15:45
Also, Mr. Lister, which part of "so don't get all 'goto's are bad' on me" don't you understand? — , Apr 30 '12 at 15:47
@unixman83: It might be helpful if you could post a small example of the kind of code your generator will create. That way we can assess the possible efficiency you'll gain *and* whether using `goto` is the most appropriate way to acheive this. — Component 10, Apr 30 '12 at 15:56
@classdaknok_t: I believe you have Matthieu's intent backwards. It's not about using exceptions as glorified gotos. It's about using gotos to emulate exceptions because C doesn't support them. — Benjamin Lindley, Apr 30 '12 at 16:10
@classdaknok_t: Actually it was a joke because most of what you use `goto` for in C is proper cleanup in case of errors. However in C++, *because* we have exceptions already, we are used to RAII. I believe that most reasonable uses of `goto` can be converted to RAII + multiple return code. — Matthieu M., Apr 30 '12 at 16:43
@Matthieu M. I see. Ah well, I'll leave the comment there for future visitors with evil minds. — , Apr 30 '12 at 16:51
@MatthieuM.: RAII has larger overhead than gotos - you'll have to rely on boost if compiler is not recent, write custom deleters (when you're dealing with system resource), when goto alternative is 3 lines big. Honestly, until goto is removed from language, I'd say you should use it when situation calls for it. Trying to use RAII/Exceptions **everywhere**, just because you like the idea is counterproductive. There are situations when old-fashioned solution is more suitable. — SigTerm, Apr 30 '12 at 16:55
@SigTerm: I care little about older compilers ;) When you combine a simple class that store a `std::function` and executes it in its destructor with lambdas... RAII **really** shines. And you just reinvented the `defer` statement ;) — Matthieu M., Apr 30 '12 at 17:07
@MatthieuM.: "I care little about older" I you want to upgrade toolchain just to support your favorite concept, you have it backwards. Reconfiguration/Reinstallation takes time, and can potentially introduce problem. What's important is your final product, not your favorite concept. "When you combine a simple class" With goto you don't need that simple class. Introducing helper class for simple scenario that happens once in the program smells like YAGNI and is violation of KISS. In this scenario your solution takes more time to write and provides no benefit. — SigTerm, Apr 30 '12 at 17:18
@MatthieuM.: "RAII really shines" Irrelevant. No technique is silver bullet. In any situation, the most suitable tool should be used, even if it is not your favorite. Technique that takes more development time and produces no benefit should not be used. "don't use goto" is not a good advice. Good advice is "write clean human-readable code". Exceptions can be used to produce spaghetty even worse than goto, and should not be used to simulate flow control. Another important thing is that goto does not terminate the program by default. — SigTerm, Apr 30 '12 at 17:22
@SigTerm: No offense, but I am so glad I don't work with you if you believe that there are actually situations where goto should be preferred over RAII. There are in fact situations where one tool is superior to another in every single way. — Benjamin Lindley, Apr 30 '12 at 17:31
@BenjaminLindley: "where goto should be preferred over RAII" They're rare, but they do exist. If you haven't encountered them, that's not my problem. "I am so glad I don't work with you" I prefer working with people that are open-minded enough to recognize that any "forbidden" language construct can be useful under certain circumstances, (instead of sticking to their favorite technique in "when you have a hammer, everything looks like a nail" fashion). If a feature exists in language, it exists for a reason. It is programmer's job to recognize for which situation this feature has been created. — SigTerm, Apr 30 '12 at 17:38
@BenjaminLindley: Also, jumping to conclusions is generally a bad idea. — SigTerm, Apr 30 '12 at 17:46
@SigTerm: Wow! *offers SigTerm a cool beer* ... It seems I have hit a nerve... and I am unsure that I'll be able to completely explain myself in such a limiting format. First, obviously, *I care little about older compilers* was a taunt. Actually, I have a *single* header file that allows me to use defer statements as long as I limited myself to one variable per statement (template!) and which I have used with success with gcc 3.4.2 (oldest version I worked with). It is, obviously, an inferior solution to lambdas, but gets the job done in 99% of the cases, `boost::tie` subdues the others. — Matthieu M., Apr 30 '12 at 17:56
@SigTerm: [cont] and I do **believe** that this technic is **much better** than using `goto` **for cleanup**. Because the cleanup statement is co-localized with the original statement, saving you from jumping to the end of the function and check the cleanup code is present; better readability overall. It also makes it possible to *disarm* the cleanup on some paths, making it easier to achieve transactions-like semantics: the infamous A in ACID! — Matthieu M., Apr 30 '12 at 17:59
@SigTerm: [cont] for uses of `goto`... I have not met any other reasonnable use of `goto` so far. I have seen some dubious uses in spaghetti code. Amusingly once split into several functions there were no `goto` any longer... and the overall code was shorter and easier to read! As far as I am concerned, `goto` and `delete` are red-herring. Not that they are bad *inherently*, but they are usually indicative of noob's work (99.99%). I have not met the 0.01% with `goto`, for `delete` it corresponds to writing my own smart pointer class with deep copying semantics ;) — Matthieu M., Apr 30 '12 at 18:03
@MatthieuM.: "but they are usually indicative of noob's" While you're correct about newbies, I had more experienced people in mind while talking about goto. I assume that a person with several years of C++ experience knows enough to avoid bad case of spaghetti. A encountered total 4 or 5 situations in the whole life where goto use was justified (IMO). Typically it went like this: non-C++ pointer resource initialized in perverted way by API(by double-pointer), shared_ptr N/A, code does not ever throw. In this situation C-style `goto cleanup;` produced cleaner code...(continued) — SigTerm, Apr 30 '12 at 18:17
@MatthieuM.: [cont.] ... while writing a proper wrapper would take more time/place in the program, and was not really necessary, because that was the only place in the program where this particular initialization scheme was required. If the program was flooded by similar patterns, it would make sense to make wrapper/switch to RAII. As a result of that experience, I have concluded that "never use goto" advice isn't good, and should be changed "don't write spaghetty code" instead. — SigTerm, Apr 30 '12 at 18:21
@MatthieuM.: "I have not met any other reasonnable use of goto so far." I can think of two. One is finite state machines, the subject of this topic. The other is where some fool of a project manager has mandated "single point of entry / single point of return". Sometimes such managers can be convinced to abandon this rule by telling them that this pretty much mandates use of the goto. But what if the fool of a manager says "That's right. That's how you're supposed to do it." ? You pick your jaw up off the floor and write some downright ugly code. Or you find another project / project manager. — David Hammen, Apr 30 '12 at 18:48
@DavidHammen: I am fortunate enough not to have encountered such a fool. I don't think he and I would have a good relationship; French is revolution: I do not obey silly rules ;) — Matthieu M., Apr 30 '12 at 18:59
@SigTerm: This usecase would not have been an issue, I have the `Defer` class already written (and used for other reasons), so I would have just dropped it here and walked away :) We have a saying in France: *A good artisan can be recognized by the quality of his tools*; similarly, I think it applies to programmers. My toolbox is not extensive, but I polish the few routines I have aggressively, and I make a point of foraging in Boost to keep sharp tools at hand. — Matthieu M., Apr 30 '12 at 19:04

Jerry Coffin · Accepted Answer · 2021-12-17T18:23:11.290

24

The part of a compiler that would be affected works with a flow graph. The syntax you use to create a particular flow graph will normally be irrelevant as long as you're writing strictly portable code--if you create something like a while loop using a goto instead of an actual while statement, it's not going to produce the same flow graph as if you used the syntax for a while loop. Using non-portable code, however, modern compilers allow you to add annotations to loops to predict whether they'll be taken or not. Depending on the compiler, you may or may not be able to duplicate that extra information using a goto (but most that have annotation for loops also have annotation for if statements, so a likely taken or likely not taken on the if controlling a goto would generally have the same effect as a similar annotation on the corresponding loop).

It is possible, however, to produce a flow graph with gotos that couldn't be produced by any normal flow control statements (loops, switch, etc.), such conditionally jumping directly into the middle of a loop, depending on the value in a global. In such a case, you may produce an irreducible flow graph, and when/if you do, that will often limit the ability of the compiler to optimize the code.

In other words, if (for example) you took code that was written with normal for, while, switch, etc., and converted it to use goto in every case, but retained the same structure, almost any reasonably modern compiler could probably produce essentially identical code either way. If, however, you use gotos to produce the mess of spaghetti like some of the FORTRAN I had to look at decades ago, then the compiler probably won't be able to do much with it.

edited Dec 17 '21 at 18:23

answered Apr 30 '12 at 15:34

Jerry Coffin

476,176
80
629
1,111

2

Does not Turing completeness assures us that whatever mess can be created with `goto`, we can create an equivalent without it ? – Matthieu M. Apr 30 '12 at 15:39
1

@MatthieuM.: I suppose you could view it in terms of Turing completeness, but it's been studied much more specifically than that, and at least IIRC, there are proofs that the accepted elements of structured programming are sufficient to produce any possible flow of control (though sometimes at the expense of duplicating code or introducing extra variables). – Jerry Coffin Apr 30 '12 at 15:43
@JerryCoffin Your answer about use of `gotos` in the second case is very vague. So the compiler just inserts a raw `JMP` instruction? – unixman83 Apr 30 '12 at 15:46
2

@unixman83: Maybe an example would help it make more sense. Consider loop hoisting -- moving a computation out of a loop if it has the same effect every iteration. To do that, the compiler has to be able to figure out the boundary of what is or isn't "the loop", and it has to be sure you won't jump into the middle of the loop without executing the code it put before it. Without that, it can't hoist the code out of the loop. – Jerry Coffin Apr 30 '12 at 15:51
@JerryCoffin You're wrong about irreducible control flow. Any unstructured control flow can be reduced to structured control flow. This has been known since [1966](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.119.9119&rep=rep1&type=pdf). This transformation introduces additional temporary variables, which the compiler is perfectly capable of removing prior to code generation. – ccurtsinger Apr 30 '12 at 16:53
1

@ccurtsinger: yes, probably poor wording on my part -- in this case, "irreducible" doesn't mean it couldn't theoretically be reduced, only that the compiler doesn't know how to do it. Ultimately, this is pretty much what Matthieu's comment (and my reply) discuss as well. In most cases it's probably not even as much a matter of not being able to reduce the flow graph, as not being able to prove much when it does so, thus losing the chances for optimization. – Jerry Coffin Apr 30 '12 at 16:54
The first paragraph is untrue for modern compilers. Loops built with `while` will have conditional jumps that are tagged "likely taken". Even loop unrolling may be broken if you replace `while` with `goto`. – MSalters Apr 30 '12 at 20:54
irreducible flow graph seems to be the key – paulm Nov 30 '14 at 23:09
Any code example of the "goto mess that can't be rewritten in loops"? – Nakilon Dec 17 '21 at 13:53
@Nakilon: Well, ultimately it can always be rewritten in loops, but doing so may result in a lot of duplication. I've added one example though (conditional jump into the middle of a loop, depending on the value in a global). – Jerry Coffin Dec 17 '21 at 18:25
*couldn't be produced by any normal flow control statements (loops, switch, etc.)* - Duff's Device demonstrates that nesting a `do{}while()` inside a `switch` statement makes it possible to do an indirect jump into the middle of a loop. Although even `switch` statements have to nest, not partially overlap, so there might be goto spaghetti you can't directly replicate without it, at least in terms of having the same compile-time estimation of branch likelihood. As far as reproducing the exact behaviour, that's [always possible](https://stackoverflow.com/q/10386152#comment13393406_10386196) – Peter Cordes Dec 18 '21 at 03:16

Matthieu M. · Answer 2 · 2012-04-30T15:35:05.133

8

How do you think that loops are represented, at the assembly level ?

Using jump instructions to labels...

Many compilers will actually use jumps even in their Intermediate Representation:

int loop(int* i) {
  int result = 0;
  while(*i) {
    result += *i;
  }
  return result;
}

int jump(int* i) {
  int result = 0;
  while (true) {
    if (not *i) { goto end; }
    result += *i;
  }

end:
  return result;
}

Yields in LLVM:

define i32 @_Z4loopPi(i32* nocapture %i) nounwind uwtable readonly {
  %1 = load i32* %i, align 4, !tbaa !0
  %2 = icmp eq i32 %1, 0
  br i1 %2, label %3, label %.lr.ph..lr.ph.split_crit_edge

.lr.ph..lr.ph.split_crit_edge:                    ; preds = %.lr.ph..lr.ph.split_crit_edge, %0
  br label %.lr.ph..lr.ph.split_crit_edge

; <label>:3                                       ; preds = %0
  ret i32 0
}

define i32 @_Z4jumpPi(i32* nocapture %i) nounwind uwtable readonly {
  %1 = load i32* %i, align 4, !tbaa !0
  %2 = icmp eq i32 %1, 0
  br i1 %2, label %3, label %.lr.ph..lr.ph.split_crit_edge

.lr.ph..lr.ph.split_crit_edge:                    ; preds = %.lr.ph..lr.ph.split_crit_edge, %0
  br label %.lr.ph..lr.ph.split_crit_edge

; <label>:3                                       ; preds = %0
  ret i32 0
}

Where br is the branch instruction (a conditional jump).

All optimizations are performed on this structure. So, goto is the bread and butter of optimizers.

edited Apr 30 '12 at 15:35

answered Apr 30 '12 at 15:25

Matthieu M.

287,565
48
449
722

4

I guess the question is whether using goto prevents the compiler from inferring certain optimisations. – Oliver Charlesworth Apr 30 '12 at 15:27
1

@OliCharlesworth: I doubt it. The danger with `goto` is the issue on scopes (esp. jumping into a scope). I added the intermediate representation of LLVM (I suppose gcc's is quite similar) which is composed of blocks linked by jumps... and which is *the* representation on which optimizations are performed. – Matthieu M. Apr 30 '12 at 15:36
1

@Matthieu And there are clearly possible control flows that can't be reproduced with structured constructs, so gotos can have an effect there. One example I can think of, is that the simple single pass SSA generation doesn't work for arbitrary gotos - while you can achieve the same effect it's much more involved. – Voo Apr 30 '12 at 16:09
2

@Voo: does it work for Duff's Device ? Even though there is no literal `goto`, the use of `switch` to jump right in the middle of a loop is quite "unstructured". The point is, I believe that C and C++ are complicated enough that for any control flow graph generated for a `goto` implementation, an equivalent implementation without `goto` can be found that produces the same control flow graph. – Matthieu M. Apr 30 '12 at 16:45
1

@MatthieuM. [You're correct](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.119.9119&rep=rep1&type=pdf). In fact, even a very simple subset of C/C++'s structured control flow is sufficient to cover any possible control flow you could write with gotos. – ccurtsinger Apr 30 '12 at 17:02
@Matthieu Didn't consider that odd tidbit of C, in which case yes it seems so. Although I remember reading that gcc had an extra step built in that transformed duff's device into a usual loop, but I'm not sure at which step this is done and for what reasons. – Voo Apr 30 '12 at 18:05

score 5 · Answer 3 · answered Apr 30 '12 at 16:46

I was wondering, from a purely compiler optimzation prespective, the result that goto's have on the compiler's optimizer? Does it make code faster, slower, or generally no change in performance compared to using temporaries / flags.

Why do you care? Your primary concern should be getting your code generator to create the correct code. Efficiency is of much less importance than correctness. Your question should be "Will my use of gotos make my generated code more likely or less likely to be correct?"

Look at the code generated by lex/yacc or flex/bison. That code is chock full of gotos. There's a good reason for that. lex and yacc implement finite state machines. Since the machine goes to another state at state transitions, the goto is arguably the most natural tool for such transitions.

There is a simple way to eliminate those gotos in many cases by using a while loop around a switch statement. This is structured code. Per Douglas Jones (Jones D. W., How (not) to code a finite state machine, SIGPLAN Not. 23, 8 (Aug. 1988), 19-22.), this is the worst way to encode a FSM. He argues that a goto-based scheme is better.

He also argues that there is an even better approach, which is convert your FSM to a control flow diagram using graph theory techniques. That's not always easy. It is an NP hard problem. That's why you still see a lot of FSMs, particularly auto-generated FSMs, implemented as either a loop around a switch or with state transitions implemented via gotos.

*"Why do you care? Your primary concern should be getting your code generator to create the correct code."* Now that's the right mindset I respect. — SigTerm, Apr 30 '12 at 16:59
It's certainly the primary concern. However, the decision to shun `goto` can also be seen as a premature pessimization. Whether you use them or not is a decision either way, and as with all decisions should be made considering evidence at hand. The conventional decision to shun them is based on evidence which doesn't apply here (maintainability) and therefore other reasons are needed. — MSalters, Apr 30 '12 at 20:59

Mike Dunlavey · Answer 4 · 2012-04-30T18:16:38.890

I agree heartily with David Hammen's answer, but I only have one point to add.

When people are taught about compilers, they are taught about all the wonderful optimizations that compilers can do.

They are not taught that the actual value of this depends on who the user is.

If the code you are writing (or generating) and compiling contains very few function calls and could itself consume a large fraction of some other program's time, then yes, compiler optimization matters.

If the code being generated contains function calls, or if for some other reason the program counter spends a small fraction of its time in the generated code, it's not worth worrying about. Why? Because even if that code could be so aggressively optimized that it took zero time, it would save no more than that small fraction, and there are probably much bigger performance issues, that the compiler can't fix, that are happy to be evading your attention.

effect of goto on C++ compiler optimization

4 Answers4

Linked