A better __builtin_constant_p

A better __builtin_constant_p

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 3464 bytes --]

I'd like to introduce a new builtin, __builtin_constant_function_p,
with nicer semantics and better performance than __builtin_constant_p.


Background:

I want to define an assert_or_assume() macro that is equivalent to
assume() or assert(), whichever results in better compiled code.

I'd like to use __builtin_constant_p to decide whether
assert_or_assume evaluates this construct:

if (!(CONDITION))
  __builtin_unreachable ();

My current idea is to write:

if (__builtin_constant_p (!(CONDITION) != !(CONDITION)))
  if (!(CONDITION))
    __builtin_unreachable ();

This would check that evaluating CONDITION "twice" (in undefined
order) results in the same truth value; if CONDITION includes, for
example, external function calls, we won't be able to prove that, so
the expensive construct would be skipped.  However, for common
conditions such as read-only logical and arithmetic expressions,
!(CONDITION) != !(CONDITION) will be folded to 0, which
__builtin_constant_p can then recognize as a constant.


The Problem:

However, it seems that with trunk GCC, __builtin_constant_p always
returns false for expressions which contain calls to functions not
explicitly marked with attribute((const)), even when those functions
are both inlined and found to allow the const attribute by
-Wsuggest-attr=const.

This is in contrast to macros which work just fine in
__builtin_constant_p's argument.  So, in this case, an inline function
isn't as fast as a macro.

The problem is that __builtin_constant_p must fold its argument very
early, before gimplification, to avoid evaluation of the argument.


My proposed solution:

The idea I'm currently playing around with is to add a new
__builtin_constant_function_p builtin, which folds to 1 as soon if its
argument can be shown, at compile time, to be a pointer to a constant
function.  This can be used in conjunction with inner functions (C
only) to redefine constant_p as:

#define constant_p(EXPR) ({ int inner(void) { return EXPR; };
__builtin_constant_function_p (inner); })

As mentioned, this definition of constant_p would be superior to
__builtin_constant_p while also ensuring the expression itself is
never evaluated.


Patch:

In early test runs, the attached patch appears to work, but I'm
inexperienced when it comes to GCC internals, and I also find that
people often disagree with me for good reasons.


Limitations:

This currently works for C only (using lambdas to expand it to C++
looks like it ought to be possible to me).

Compilation time probably increases significantly, because an inner
function is generated and optimized only to be eventually
discarded. It's also possible this affects code generation in the rest
of the outer function.

This absolutely hasn't been tested enough. I'm attaching my main test
case.

We give up in the fold-builtins pass. It might be a better idea to
wait for the last such pass, if we could.

For very good reasons, this doesn't work as I naively expected it
would for functions marked with attribute((const)), because the
compiler cannot assume that those functions, if called, would return.

Questions:

Am I totally on the wrong track here?

Should we have __builtin_assume?

Should we instead fix our code so forgetting a "const" attribute won't
hurt performance, if it can be inferred?

Should there be a new function attribute to mark functions that may be
assumed by the compiler to return?

Should we fix after-the-fact assume()s to work better?

[-- Attachment #2: constant_function_p.c --]
[-- Type: text/x-csrc, Size: 441 bytes --]

#include <stdio.h>

extern int nonnegative (int) __attribute__((const));
#ifdef FAST
int nonnegative (int i)
{
  return i >= 0;
}
#endif

int main(int argc, char **argv)
{
  int i = argc;
  int c;
  {
    auto int inner(void)
    {
      return nonnegative(i) == nonnegative(i);
    }

    c = __builtin_constant_function_p(inner);
  }

  if (c)
    if (!nonnegative(i))
      __builtin_unreachable ();

  printf("%d\n", i & 0x80000000);
}


[-- Attachment #3: 0001-Add-a-__builtin_constant_function_p-builtin.patch --]
[-- Type: text/x-patch, Size: 5506 bytes --]

From 5e694e0e35b56caf4469cb516db50608f026c741 Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@gmail.com>
Date: Sun, 30 Jun 2019 12:24:17 +0000
Subject: [PATCH] Add a __builtin_constant_function_p builtin.

---
 gcc/builtins.c     | 78 ++++++++++++++++++++++++++++++++++++++++++++++
 gcc/builtins.def   |  1 +
 gcc/expr.c         |  4 ++-
 gcc/tree-ssa-ccp.c |  8 +++++
 4 files changed, 90 insertions(+), 1 deletion(-)

diff --git a/gcc/builtins.c b/gcc/builtins.c
index 4ecfd49d03c..e1ff327c84b 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -30,6 +30,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree.h"
 #include "memmodel.h"
 #include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
 #include "predict.h"
 #include "params.h"
 #include "tm_p.h"
@@ -150,6 +152,7 @@ static tree stabilize_va_list_loc (location_t, tree, int);
 static rtx expand_builtin_expect (tree, rtx);
 static rtx expand_builtin_expect_with_probability (tree, rtx);
 static tree fold_builtin_constant_p (tree);
+static tree fold_builtin_constant_function_p (tree);
 static tree fold_builtin_classify_type (tree);
 static tree fold_builtin_strlen (location_t, tree, tree);
 static tree fold_builtin_inf (location_t, tree, int);
@@ -8449,6 +8452,78 @@ fold_builtin_constant_p (tree arg)
   return NULL_TREE;
 }
 
+/* Fold a call to __builtin_constant_function_p, if we know its
+   argument ARG will evaluate to a constant function.  */
+
+static bool
+check_stmt (gimple_stmt_iterator *gsi)
+{
+  gimple *stmt = gsi_stmt (*gsi);
+  if (is_gimple_debug (stmt))
+    return true;
+
+  if (gimple_clobber_p (stmt) ||
+      gimple_has_volatile_ops (stmt))
+    return false;
+
+  if (greturn *gr = dyn_cast<greturn *> (stmt))
+    {
+      if (TREE_CODE (gr->op[0]) != INTEGER_CST)
+	return false;
+
+      if (gr->op[1] != NULL_TREE)
+	return false;
+
+      return true;
+    }
+
+  return false;
+}
+
+static tree
+fold_builtin_constant_function_p (tree arg)
+{
+  if (TREE_CODE (arg) == ADDR_EXPR)
+    arg = TREE_OPERAND (arg, 0);
+  if (!arg)
+    return NULL_TREE;
+  if (TREE_CODE (arg) != FUNCTION_DECL)
+    return NULL_TREE;
+  if (DECL_PURE_P (arg) || TREE_READONLY (arg))
+    {
+      struct function *fun = DECL_STRUCT_FUNCTION (arg);
+      if (!fun)
+	return NULL_TREE;
+      push_cfun (DECL_STRUCT_FUNCTION (arg));
+      gimple_stmt_iterator gsi;
+      basic_block this_block;
+      bool good = true;
+      FOR_EACH_BB_FN (this_block, cfun)
+	{
+	  for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi);
+	       gsi_next (&gsi))
+	    {
+	      if (check_stmt (&gsi))
+		continue;
+	      else
+		{
+		  good = false;
+		  goto bad;
+		}
+	    }
+	}
+    bad:
+      pop_cfun ();
+
+      if (good)
+	return integer_one_node;
+
+      return NULL_TREE;
+    }
+
+  return NULL_TREE;
+}
+
 /* Create builtin_expect or builtin_expect_with_probability
    with PRED and EXPECTED as its arguments and return it as a truthvalue.
    Fortran FE can also produce builtin_expect with PREDICTOR as third argument.
@@ -9491,6 +9566,9 @@ fold_builtin_1 (location_t loc, tree fndecl, tree arg0)
 
   switch (fcode)
     {
+    case BUILT_IN_CONSTANT_FUNCTION_P:
+      return fold_builtin_constant_function_p (arg0);
+
     case BUILT_IN_CONSTANT_P:
       {
 	tree val = fold_builtin_constant_p (arg0);
diff --git a/gcc/builtins.def b/gcc/builtins.def
index 6d41bdb4f44..6bff6f7f4e3 100644
--- a/gcc/builtins.def
+++ b/gcc/builtins.def
@@ -826,6 +826,7 @@ DEF_GCC_BUILTIN        (BUILT_IN_CLZIMAX, "clzimax", BT_FN_INT_UINTMAX, ATTR_CON
 DEF_GCC_BUILTIN        (BUILT_IN_CLZL, "clzl", BT_FN_INT_ULONG, ATTR_CONST_NOTHROW_LEAF_LIST)
 DEF_GCC_BUILTIN        (BUILT_IN_CLZLL, "clzll", BT_FN_INT_ULONGLONG, ATTR_CONST_NOTHROW_LEAF_LIST)
 DEF_GCC_BUILTIN        (BUILT_IN_CONSTANT_P, "constant_p", BT_FN_INT_VAR, ATTR_CONST_NOTHROW_LEAF_LIST)
+DEF_GCC_BUILTIN        (BUILT_IN_CONSTANT_FUNCTION_P, "constant_function_p", BT_FN_INT_VAR, ATTR_CONST_NOTHROW_LEAF_LIST)
 DEF_GCC_BUILTIN        (BUILT_IN_CTZ, "ctz", BT_FN_INT_UINT, ATTR_CONST_NOTHROW_LEAF_LIST)
 DEF_GCC_BUILTIN        (BUILT_IN_CTZIMAX, "ctzimax", BT_FN_INT_UINTMAX, ATTR_CONST_NOTHROW_LEAF_LIST)
 DEF_GCC_BUILTIN        (BUILT_IN_CTZL, "ctzl", BT_FN_INT_ULONG, ATTR_CONST_NOTHROW_LEAF_LIST)
diff --git a/gcc/expr.c b/gcc/expr.c
index c78bc74c0d9..8465a937639 100644
--- a/gcc/expr.c
+++ b/gcc/expr.c
@@ -10026,7 +10026,9 @@ expand_expr_real_1 (tree exp, rtx target, machine_mode tmode,
 		  || TREE_STATIC (exp)
 		  || DECL_EXTERNAL (exp)
 		  /* ??? C++ creates functions that are not TREE_STATIC.  */
-		  || TREE_CODE (exp) == FUNCTION_DECL);
+		  || TREE_CODE (exp) == FUNCTION_DECL
+		  /* ??? */
+		  || true);
 
       /* This is the case of an array whose size is to be determined
 	 from its initializer, while the initializer is still being parsed.
diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c
index 51b9d9f53d2..34319b7f17d 100644
--- a/gcc/tree-ssa-ccp.c
+++ b/gcc/tree-ssa-ccp.c
@@ -3246,6 +3246,14 @@ pass_fold_builtins::execute (function *fun)
 		  result = integer_zero_node;
 		  break;
 
+		case BUILT_IN_CONSTANT_FUNCTION_P:
+		  /* Resolve __builtin_constant_function_p.  If it
+		     hasn't been folded to integer_one_node by now,
+		     it's fairly certain that the value simply isn't
+		     constant.  */
+		  result = integer_zero_node;
+		  break;
+
 		case BUILT_IN_ASSUME_ALIGNED:
 		  /* Remove __builtin_assume_aligned.  */
 		  result = gimple_call_arg (stmt, 0);
-- 
2.20.1

Re: A better __builtin_constant_p

[Andrew Sutton]

> Am I totally on the wrong track here?

That depends on what you want your assumptions to do. This definitely
doesn't solve the problems I'm having implementing C++ contracts,
especially axioms, which can involve declarations of undecidable
functions. For example, is_reachable(p, q) for a pair of pointers
can't be implemented for normal systems (maybe it could with one
sanitizer or another), but it could be used for static analyzers (or
optimizers maybe?) that understood the inherent meaning of a "call" to
that function.

Our problem is that we need to communicate an assumption syntactically
through to GIMPLE, but without the usual ODR requirements of C++.
Specifically, we need to allow assumptions on conditions that use
functions that are declared but not defined anywhere.

Now, I'm not an optimizer expert at all, so I could be way wrong, but
my sense is that depending on the constantness of a function will not
help you get better assumptions, because you aren't necessarily
interested in the value of the expression, only the facts introduced
by it (e.g., for some x, x == 5).

> Should we have __builtin_assume?

I'd like it. The "if (predicate) unreachable" pattern doesn't work for
C++ contracts. This works just fine for C++ contracts in LLVM.

There's another solution to the problem: define undefinable functions
as "= undecidable".

> Should we instead fix our code so forgetting a "const" attribute won't
> hurt performance if it can be inferred?

Probably? If you have an assertion that you want to promote to an
assumption vial __builtin_assume (using LLVM), you'll get a warning.
Throw in -werror, and your program doesn't compile. That seems
unfortunate.

This has come up in WG21 discussions around contracts. There's some
momentum to relax the requirement that asserted contracts don't have
side effects because it's sometimes useful to call predicates that log
something, throw, terminate, etc. If we allow "promotion" of
assertions to assumptions, then that requirement is simply going to
break a lot of code. Also, most functions aren't declared const, and
requiring that broadly would be a non-starter for adding contracts to
a program.