1

While attempting to answer a question by Mehrdad, I concocted the little function below (in action at liveworkspace):

template <typename T, unsigned low, unsigned high>
static constexpr auto highest_index_in() ->
   typename std::enable_if<high >= low, unsigned>::type
{
   return low == high                 ? low :
          high == low + 1             ? (exists<T, high>() ? high : low) :
          exists<T, (high + low)/2>() ? highest_index_in<T, (high+low)/2, high>() :
                                        highest_index_in<T, low, (high+low)/2>();
} // highest_index_in

(where exists is O(1))

The compilation is extremely slow though (on liveworkspace), and attempting to use wide ranges fail utterly with compiler crashes ([0, ~0u] does not work...).

I believe I managed to implement the recursion correctly (I would be glad to be contradicted), and yet...

Thus the question: when evaluating the various ternary operators calls here, may the compiler elide the computation of the not-taken branch ?

Community
  • 1
  • 1
Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • No, all conditional branches must be evaluated, and `constexpr` doesn't help, since it can be executed as a normal function. – Xeo Jan 08 '13 at 11:29
  • @Xeo: this is my point, when evaluated as a normal function only one branch is executed! .... I just suddenly realized that even though the computation is not executed it might be necessary to actually instantiate the function template. – Matthieu M. Jan 08 '13 at 11:41
  • @MatthieuM.: yes, it is necessary to instantiate it, the compiler can't just not attempt to figure out what the code means in an untaken branch. – PlasmaHH Jan 08 '13 at 12:02
  • @MatthieuM. : *"even though the computation is not executed it might be necessary to actually instantiate the function template"*.... THAT is what I was saying in the other topic. :P – Nawaz Jan 08 '13 at 12:07
  • 1
    That's why people are asking for a static if, that would only instantiate one branch. – Marc Glisse Jan 08 '13 at 12:26
  • 1
    If not actually instantiate the dead-code, the compiler must at least do enough work to establish that it *could* instantiate it. Otherwise it might fail to provide a required diagnostic. Presumably if the compiler is somehow smart enough to figure out that it can instantiate it, but that having done so it can then remove it, *then* it would be permitted not to instantiate it ("as-if"). I suspect the compiler would have to prove that the recursion is well-founded in order to do that, though, or at least that it doesn't hit any "bad" cases requiring diagnostics. – Steve Jessop Jan 08 '13 at 12:47
  • ... And that at least would include figuring out what template specializations might be hit, either directly in the elided instantiation or indirectly. – MSalters Jan 08 '13 at 14:46
  • @SteveJessop: it's a bit of a bummer (makes `?:`, `||` and `&&` much less powerful than they could be), I wonder if it could be revised for C++1y or we are just going down the `static_if` road here. – Matthieu M. Jan 08 '13 at 14:56
  • @MatthieuM: I can sort of imagine a relaxation of what it means to odr-use an instantiation, saying that it's unspecified whether templates used in unreachable code are instantiated. I think the committee is wary, though, of code that's accepted or rejected according to how good the optimizer is. To date, compilers have always validated dead code. – Steve Jessop Jan 08 '13 at 15:26
  • @SteveJessop: I understand, however for the `constexpr` function here it is not a matter of optimization; compile-time evaluation is *necessary*. – Matthieu M. Jan 08 '13 at 15:53
  • @MatthieuM.: but there's still a difference between the compiler evaluating the constexpr code (and perhaps in doing so observing that the branch wasn't taken) vs the compiler proving to itself that the branch is unreachable. Are you in effect asking for the compiler to be allowed to construct an AST top-down, and only actually resolve expressions properly if they're evaluated at compile-time as part of some constant expression? Extreme lazy evaluation. If so I think that's a fair request but pretty powerful compiler magic :-) – Steve Jessop Jan 08 '13 at 15:59
  • The same problem was subject of this question: http://stackoverflow.com/questions/12237126/a-workaround-for-partial-specialization-of-function-template – Johannes Schaub - litb Jan 08 '13 at 19:51
  • @JohannesSchaub-litb: I do see how this will allow to select different overloads, but I do not see how this will prevent the instantiation of the full recursive tree ? – Matthieu M. Jan 09 '13 at 07:39

1 Answers1

4

No, the compiler can not skip the evaluation of the not-taken branches of the ternary operator, because to do so means the compiler first has to establish there are no conflicting overloads and/or template specialisations in any of those branches possible that could render the program ill-formed. To do that determination, the compiler effectively has to instantiate the templates used on the branches and perform overload resolution on the functions.

Bart van Ingen Schenau
  • 15,488
  • 4
  • 32
  • 41
  • Yes, just realized that... it can avoid to compute the value but must instantiate (recursively) the function body. – Matthieu M. Jan 08 '13 at 14:20