[Bug c++/53792] New: [C++11][constexpr] improving compiler-time constexpr evaluation

[Bug c++/53792] New: [C++11][constexpr] improving compiler-time constexpr evaluation

[vincenzo.innocente at cern dot ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

             Bug #: 53792
           Summary: [C++11][constexpr] improving compiler-time constexpr
                    evaluation
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: vincenzo.innocente@cern.ch


Filed under c++ even if it is most probably an optimization issue.

At the moment it looks like that constexpr are evaluated at compile time only
if explicitly assigned to a constexpr constant. There are cases though where
the compiler can infer that the expression can still be evaluated at compile
time even if used in a run-time context.

Take the following quite realistic example of a consexpr "indexing table" used
to access a non-const array using string literals though an inline function.
In principle foo and bar are equivalent.
At the moment gcc evaluates "getIndex" at compile time for bar (where the marco
expansion explicitly instantiates a constexpr int, while it generates runtime
code for foo that uses the inlined function getV.

Would the compiler be able to transform getV in something like the code in the
macro?



constexpr entry theMap[] = {
 {"a", 0},
 {"b", 1},
 {nullptr,2}
};

// filled at run time 
double v[3];


constexpr bool  same(char const *x, char const *y)   {
 return !*x && !*y ? true : (*x == *y && same(x+1, y+1));
}

constexpr int getIndex(char const *label, entry const *entries)   {
 return !entries->label ? entries->index  : same(entries->label, label) ?
entries->index : getIndex(label, entries+1);
}


inline  double __attribute__((always_inline)) getV(const char * name )  {
 return  v[getIndex(name,theMap)];
}



#define SetV(X,NAME) \
constexpr int i_##X = getIndex(NAME, theMap);\
const double X = v[i_##X]


int foo() {
 const double a = getV("a");
 const double b = getV("b");

 if (a==b) return 1;
 return 0;

}

int bar() {
 SetV(a,"a");
 SetV(b,"b");

 if (a==b) return 1;
 return 0;

}

[Bug c++/53792] [C++11][constexpr] improving compiler-time constexpr evaluation

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-06-28
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-28 09:34:20 UTC ---
Does the C++ standard require getIndex to be evaluated to a constant in getV?
Or is 'constexpr' only telling you that it is required in a context where
evaluation to a constant is required (and thus arguments to a constexpr
function are constrained)?

[Bug c++/53792] [C++11][constexpr] improving compiler-time constexpr evaluation

[vincenzo.innocente at cern dot ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

--- Comment #2 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2012-06-28 11:08:38 UTC ---
On 28 Jun, 2012, at 11:34 AM, rguenth at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792
> 
> Richard Guenther <rguenth at gcc dot gnu.org> changed:
> 
>           What    |Removed                     |Added
> ----------------------------------------------------------------------------
>             Status|UNCONFIRMED                 |NEW
>   Last reconfirmed|                            |2012-06-28
>     Ever Confirmed|0                           |1
> 
> --- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-28 09:34:20 UTC ---
> Does the C++ standard require getIndex to be evaluated to a constant in getV?
No, a constexpr function can be used as a "normal" function. For instance if
getV was not inlined 
the correct behaviour is what we observe 
> Or is 'constexpr' only telling you that it is required ina context where
> evaluation to a constant is required (and thus arguments to a constexpr
> function are constrained)?
I would say yes (a constant needs to be evaluated using a constexpr function.
see page 148-150 (166-168 of my pdf) of the standard (7.1.5 point 3 and
following)
> 
My point is that the compiler does not identify that "getIndex" is a constant
expression in the context of foo
 nor in context of the following foo2 that indeed produce (as it should)
identical code to foo

int foo2() {
  const double a = v[getIndex("a",theMap)];
  const double b = v[getIndex("b",theMap)];

  if (a==b) return 1;
  return 0;

}

[Bug c++/53792] [C++11][constexpr] improving compiler-time constexpr evaluation

[jason at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

Jason Merrill <jason at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jason at gcc dot gnu.org

--- Comment #3 from Jason Merrill <jason at gcc dot gnu.org> 2012-07-19 14:27:49 UTC ---
Since getV is not constexpr, constexpr doesn't help with optimization of foo,
so it relies on inlining.  constexpr should help with foo2, however.

[Bug c++/53792] [C++11][constexpr] improving compiler-time constexpr evaluation

[vincenzo.innocente at cern dot ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

--- Comment #4 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2012-07-27 10:47:49 UTC ---
is "__attribute__((always_inline)) " not making foo to transform in foo2 in a
very early compiler's stage?
I can make getV a macro if helps: I do not like SetV due to its "not natural"
syntax

[Bug c++/53792] [C++11][constexpr] improving compiler-time constexpr evaluation

[jason at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

--- Comment #5 from Jason Merrill <jason at redhat dot com> 2012-07-27 15:06:31 UTC ---
On 07/27/2012 06:47 AM, vincenzo.innocente at cern dot ch wrote:
> is "__attribute__((always_inline)) " not making foo to transform in foo2 in a
> very early compiler's stage?

Fairly early, but not as early as constant expression folding.

Jason

[Bug c++/53792] [C++11][constexpr] improving compiler-time constexpr evaluation

[giulio.eulisse at cern dot ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

Giulio Eulisse <giulio.eulisse at cern dot ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |giulio.eulisse at cern dot
                   |                            |ch

--- Comment #6 from Giulio Eulisse <giulio.eulisse at cern dot ch> 2012-08-08 11:17:58 UTC ---
A simpler testcase for the underlying problem is the following.

struct entry {                                                                  
  char const* label;
  int         value;
};

constexpr bool same(char const *x, char const *y) {
  return !*x && !*y     ? true                                                  
       : /* default */    (*x == *y && same(x+1, y+1));                         
}

constexpr int keyToValue(char const *label, entry const *entries) {             
  return !entries->label ? entries->value                         
       : same(entries->label, label) ? entries->value
       : /*default*/                   keyToValue(label, entries+1);            
}

constexpr entry foo[] = {{"Foo", 0}, {"Bar", 1}, {"FooBar", 2}, {0, -1}};

int
bar()
{
  /* constexpr */ int result = keyToValue("Foo", foo); // Uncomment constexpr
for optimized version.
  return result;
}

Without the constexpr the code is fully expanded as if the arguments were
generic:

0000000000000000 <_Z3barv>:
   0:   53                      push   %rbx
   1:   bf 00 00 00 00          mov    $0x0,%edi
   6:   bb 00 00 00 00          mov    $0x0,%ebx
   b:   eb 0f                   jmp    1c <_Z3barv+0x1c>
   d:   0f 1f 00                nopl   (%rax)
  10:   48 83 c3 10             add    $0x10,%rbx
  14:   48 8b 3b                mov    (%rbx),%rdi
  17:   48 85 ff                test   %rdi,%rdi
  1a:   74 1d                   je     39 <_Z3barv+0x39>
  1c:   80 3f 46                cmpb   $0x46,(%rdi)
  1f:   75 ef                   jne    10 <_Z3barv+0x10>
  21:   80 7f 01 6f             cmpb   $0x6f,0x1(%rdi)
  25:   75 e9                   jne    10 <_Z3barv+0x10>
  27:   48 83 c7 02             add    $0x2,%rdi
  2b:   be 00 00 00 00          mov    $0x0,%esi
  30:   e8 00 00 00 00          callq  35 <_Z3barv+0x35>
  35:   84 c0                   test   %al,%al
  37:   74 d7                   je     10 <_Z3barv+0x10>
  39:   8b 43 08                mov    0x8(%rbx),%eax
  3c:   5b                      pop    %rbx
  3d:   c3                      retq   

Disassembly of section .text._Z4samePKcS0_:

0000000000000000 <_Z4samePKcS0_>:
   0:   0f b6 17                movzbl (%rdi),%edx
   3:   84 d2                   test   %dl,%dl
   5:   75 09                   jne    10 <_Z4samePKcS0_+0x10>
   7:   80 3e 00                cmpb   $0x0,(%rsi)
   a:   0f 94 c0                sete   %al
   d:   c3                      retq   
   e:   66 90                   xchg   %ax,%ax
  10:   31 c0                   xor    %eax,%eax
  12:   3a 16                   cmp    (%rsi),%dl
  14:   74 0a                   je     20 <_Z4samePKcS0_+0x20>
  16:   c3                      retq   
  17:   66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
  1e:   00 00 
  20:   0f b6 47 01             movzbl 0x1(%rdi),%eax
  24:   84 c0                   test   %al,%al
  26:   75 10                   jne    38 <_Z4samePKcS0_+0x38>
  28:   80 7e 01 00             cmpb   $0x0,0x1(%rsi)
  2c:   b8 01 00 00 00          mov    $0x1,%eax
  31:   75 0a                   jne    3d <_Z4samePKcS0_+0x3d>
  33:   f3 c3                   repz retq 
  35:   0f 1f 00                nopl   (%rax)
  38:   3a 46 01                cmp    0x1(%rsi),%al
  3b:   74 0b                   je     48 <_Z4samePKcS0_+0x48>
  3d:   31 c0                   xor    %eax,%eax
  3f:   90                      nop
  40:   c3                      retq   
  41:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  48:   48 83 ec 08             sub    $0x8,%rsp
  4c:   48 83 c6 02             add    $0x2,%rsi
  50:   48 83 c7 02             add    $0x2,%rdi
  54:   e8 00 00 00 00          callq  59 <_Z4samePKcS0_+0x59>
  59:   84 c0                   test   %al,%al
  5b:   74 10                   je     6d <_Z4samePKcS0_+0x6d>
  5d:   b8 01 00 00 00          mov    $0x1,%eax
  62:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  68:   48 83 c4 08             add    $0x8,%rsp
  6c:   c3                      retq   
  6d:   31 c0                   xor    %eax,%eax
  6f:   eb f7                   jmp    68 <_Z4samePKcS0_+0x68>

while with constexpr on results everything is optimized out:

0000000000000000 <_Z3barv>:
   0:   31 c0                   xor    %eax,%eax
   2:   c3                      retq

[Bug c++/53792] [C++11][constexpr] improving compiler-time constexpr evaluation

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-08-08 18:18:51 UTC ---
Thanks Giulio!

[Bug c++/53792] [C++11] improving compiler-time constexpr evaluation

[balakrishnan.erode at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53792

Balakrishnan B <balakrishnan.erode at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |balakrishnan.erode at gmail dot co
                   |                            |m

--- Comment #8 from Balakrishnan B <balakrishnan.erode at gmail dot com> ---
Another testcase with c++14 extended constexpr (i.e supports loops and more
than one statement).

Code:

template<class T>
void sink(T);

constexpr unsigned foo(){
  unsigned  i = 1;
  while((i<<1) > i){
    i = i<<1;
  }
  return i;
}
template<unsigned i>
  struct Foo
        {
        };

void bar(){
  sink(foo());
  sink(Foo<foo()>{});
}

Assembly for bar: 
clang3.5.1 -O3 -std=c++14
bar():                                # @bar()
        pushq   %rax
        movl    $-2147483648, %edi      # imm = 0xFFFFFFFF80000000
        callq   void sink<unsigned int>(unsigned int)
        popq    %rax
        jmp     void sink<Foo<2147483648u> >(Foo<2147483648u>) # TAILCALL

gcc5.1.0 -O3 -std=c++14
bar():
        movl    $32, %eax
        movl    $1, %edi
        jmp     .L2
.L3:
        movl    %edx, %edi
.L2:
        subl    $1, %eax
        leal    (%rdi,%rdi), %edx
        jne     .L3
        subq    $8, %rsp
        call    void sink<unsigned int>(unsigned int)
        subq    $8, %rsp
        pushq   $0
        call    void sink<Foo<2147483648u> >(Foo<2147483648u>)
        addq    $24, %rsp
        ret

Live demo: http://goo.gl/b56Q5k