See <https://wg21.link/p1774>.
Note, we'll need something similar for OpenMP #pragma omp assume (C/C++/Fortran). I thought we could represent it in the IL as: if (.IFN_ASSUME ()) { if (!cond) __builtin_unreachable (); } where .IFN_ASSUME would eventually be folded into false. We'd need to teach the ranger etc. to take advantage of the bbs guarded by .IFN_ASSUME () as if the condition would be true, the inliner to try to discover SESE regions guarded by that condition and ignore them for size estimation purposes and perhaps have somewhat higher code growth limits into those regions. Richi doesn't like that. Another possibility is to represent these as: .IFN_ASSUME (outlined_fun, args...); where the cond expression would be outlined into an artificial function. Ranger and other optimization passes then could try to evaluate the body of outlined_fun with the assumption that the function returns true (if it returns false, then it is UB). We'd never emit the artificial outlined functions into assembly nor debug info, but would inline into them and try to optimize them after IPA. Would be nice to have callgraph order their post IPA opts before functions that .IFN_ASSUME reference them. Either the outlined functions could be created in the FEs (e.g. for C++ we could perhaps partly use code that we use for lambda capture discoveries), but the disadvantage would be that we'd need to do it 3 times. So another option would be some new GENERIC/GIMPLE statement kind used for these and lower it only at say gimple lowering time (we have a precedent of creating outlined functions at ompexp time for OpenMP expansion). Thoughts on this? Aldy/Andrew, do you think it is something the ranger could handle?
Note my main dislike is because the former is essentially <if we run here, 'cond' must have hold> if (0) { if (!cond) __builtin_unreachable (); } <something where 'cond' should hold> that is, the assumption itself, not only its condition computation (and side-effects) are thrown away. With cond = .IFN_ASSUME (outlined_cond_computer, args...); if (!cond) __builtin_unreachable (); or as Jakub prefers with implicit unreachable, the side-effects we want to elide are in 'outlined_cond_computer' and we can later "optimize" the .IFN_ASSUME call to compute true. For ranger the difficulty in the latter form is that there will be assertions on 'args...', variables at the call site, but what they are is specified by outlined_cond_computer returning true. Consider _bool outlined_cond_computer (int i, int j) { return i_1(D) == j_2(D); } from [[assume(i == j)]]; we'd then have .IFN_ASSUME (cond_fn, i_2, j_5); and just like IPA does, we'd have to "connect" relations/ranges produced by outlined_cond_computer via argument positions. I think we can easily funnel in argument ranges from the caller and thus possibly compute outlined_cond_computer outgoing ranges for the arguments (only those are interesting!) on the "true" return edge. Complication is the IL is in another function, set_cfun is a bit expensive but in theory most things could be formulated in a way to not require 'cfun' be set "correctly". On the C++ frontend side I'd simply handle [[assume(expr)]] as if 'expr' were in a lambda -> bool with everything captured by value.
(In reply to Richard Biener from comment #2) > On the C++ frontend side I'd simply handle > > [[assume(expr)]] > > as if 'expr' were in a lambda -> bool with everything captured by value. ... because it seems (ick!) void foo() { int i = 0; [[assume(++i == 1)]]; if (i != 0) std::abort (); } needs to work. We couldn't let that ++i "escape" to GENERIC/GIMPLE, even when protected with if (.IFN_ASSUME ()) it would create ugly PHIs.
Note, I think for [[assume(i == j)]]; we can just emit if (i == j) ; else __builtin_unreachable (); - it is just the TREE_SIDE_EFFECTS case that would need the extra treatment (I think the no side-effect cases will be occur often enough that it is worth avoiding the outlining etc. costs). Well, possibly also anything that could trap or fault or with some expression size limit. If it doesn't have side-effects and can't trap/fault, we either DCE it, or it doesn't result in visible side-effects. But possible floating point side-effects, or integer division by zero, or memory dereferences etc. should go the new way.
(In reply to Jakub Jelinek from comment #4) > Note, I think for [[assume(i == j)]]; we can just emit if (i == j) ; else > __builtin_unreachable (); It would be great if the attribute were somewhat cleverer than that. For example: double my_sqrt(double const d) { [[assume(d >= 0.0)]]; return std::sqrt(d); } or even: double my_sqrt(double const d) { [[assume(std::isfinite(std::sqrt(d)))]] return std::sqrt(d); }
(In reply to Pilar Latiesa from comment #5) > (In reply to Jakub Jelinek from comment #4) > > Note, I think for [[assume(i == j)]]; we can just emit if (i == j) ; else > > __builtin_unreachable (); > > It would be great if the attribute were somewhat cleverer than that. You've cut the second part of sentence, the above was meant for !TREE_SIDE_EFFECTS conditions and the rest is about how to treat conditions which do have side-effects (and that we should probably use more than just TREE_SIDE_EFFECTS test, but watch for any expressions that could possibly raise exceptions, or fault or trap). For the simple cases, we already can handle it without actually invoking anything at runtime and it will be cheaper compile time to handle it as before, for the more complex expressions sure, we need to come up with something new and make ranger and perhaps other optimizations be able to cope with it. BTW, the C++ paper mentions clang __builtin_assume, but that one seems to do roughly what our if (cond) ; else __builtin_unreachable (); does (which they I think support too) only if the expression doesn't contain side-effects. If it does, it warns and doesn't do anything at all.
You could provide an API to access the different relations that hold in either the outline function, or the .IFN_ASSUME construct. Then ranger could use that API to access and record the different assertions. I'd hate for ranger to have to deconstruct some functions for clues. Silly question, why can't you expand the [[assume]] construct into: if (x > 5) __builtin_unreachable (); ...like we always have. Then no changes are needed to ranger :). Or does this have to do with the whole side-effect thing?
(In reply to Aldy Hernandez from comment #7) > Silly question, why can't you expand the [[assume]] construct into: > > if (x > 5) > __builtin_unreachable (); > > ...like we always have. Then no changes are needed to ranger :). Or does > this have to do with the whole side-effect thing? Exactly. For expressions with no side-effects, we can do that. For, say, a call to a non-const function, we need to avoid actually emitting the call.
(In reply to Jason Merrill from comment #8) > (In reply to Aldy Hernandez from comment #7) > > Silly question, why can't you expand the [[assume]] construct into: > > > > if (x > 5) > > __builtin_unreachable (); > > > > ...like we always have. Then no changes are needed to ranger :). Or does > > this have to do with the whole side-effect thing? > > Exactly. For expressions with no side-effects, we can do that. For, say, a > call to a non-const function, we need to avoid actually emitting the call. So...could we keep doing what we're doing for non side-effect code, and only do the outline function for side-effect stuff? Or is that too much to ask? But wait a minute, is calling a non-const function from [[assume]] even allowed?
(In reply to Aldy Hernandez from comment #9) > So...could we keep doing what we're doing for non side-effect code, and only > do the outline function for side-effect stuff? Or is that too much to ask? Yes, that's what Jakub proposed in comment #4. > But wait a minute, is calling a non-const function from [[assume]] even > allowed? Yep, that's the tricky part. Of course, as functions get more complicated, the compiler being able to do anything useful with it gets less likely. It seems entirely reasonable to start with calls to functions that the compiler knows are const even if they aren't declared with the attribute.
(In reply to Jason Merrill from comment #10) > > But wait a minute, is calling a non-const function from [[assume]] even > > allowed? > > Yep, that's the tricky part. Of course, as functions get more complicated, > the compiler being able to do anything useful with it gets less likely. It > seems entirely reasonable to start with calls to functions that the compiler > knows are const even if they aren't declared with the attribute. I see. Ok, so yeah...I'm sure we can work something out. When y'all have a prototype representable in the IL, we'd be happy to enhance ranger to handle it. Sounds like something very useful, particularly for floats-- without exposing signaling whathaveyous. Maybe Andrew has some further thoughts here?
Created attachment 53600 [details] gcc13-pr106654.patch Untested patch, with the more difficult cases optimized away during gimplification, so only the most simple assertions are transformed into if (cond); else __builtin_unreachable (); for now, but the FE handling should be all there, for C++ both as the standard attribute and [[gnu::assume (cond)]] or __attribute__((assume (cond))) with the same behavior, for C just the latter two. Similarly, for C++ constant evaluation, it will diagnose only the simple cases (mainly because we'd need to undo all changes to ctx->globals done during evaluation of the assumption). I believe such behavior in both places is standard conforming, but obviously want to work especially on the former (middle-end representation of those) soon.
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>: https://gcc.gnu.org/g:08b51baddc53d64aa4c5e7a81ef3c4bf320293be commit r13-3106-g08b51baddc53d64aa4c5e7a81ef3c4bf320293be Author: Jakub Jelinek <jakub@redhat.com> Date: Thu Oct 6 08:56:48 2022 +0200 c++, c: Implement C++23 P1774R8 - Portable assumptions [PR106654] The following patch implements C++23 P1774R8 - Portable assumptions paper, by introducing support for [[assume (cond)]]; attribute for C++. In addition to that the patch adds [[gnu::assume (cond)]]; and __attribute__((assume (cond))); support to both C and C++. As described in C++23, the attribute argument is conditional-expression rather than the usual assignment-expression for attribute arguments, the condition is contextually converted to bool (for C truthvalue conversion is done on it) and is never evaluated at runtime. For C++ constant expression evaluation, I only check the simplest conditions for undefined behavior, because otherwise I'd need to undo changes to *ctx->global which happened during the evaluation (but I believe the spec allows that and we can further improve later). The patch uses a new internal function, .ASSUME, to hold the condition in the FEs. At gimplification time, if the condition is simple/without side-effects, it is gimplified as if (cond) ; else __builtin_unreachable (); and otherwise for now dropped on the floor. The intent is to incrementally outline the conditions into separate artificial functions and use .ASSUME further to tell the ranger and perhaps other optimization passes about the assumptions, as detailed in the PR. When implementing it, I found that assume entry hasn't been added to https://eel.is/c++draft/cpp.cond#6 Jonathan said he'll file a NB comment about it, this patch assumes it has been added into the table as 202207L when the paper has been voted in. With the attributes for both C/C++, I'd say we don't need to add __builtin_assume with similar purpose, especially when __builtin_assume in LLVM is just weird. It is strange for side-effects in function call's argument not to be evaluated, and LLVM in that case (annoyingly) warns and ignores the side-effects (but doesn't do then anything with it), if there are no side-effects, it will work like our if (!cond) __builtin_unreachable (); 2022-10-06 Jakub Jelinek <jakub@redhat.com> PR c++/106654 gcc/ * internal-fn.def (ASSUME): New internal function. * internal-fn.h (expand_ASSUME): Declare. * internal-fn.cc (expand_ASSUME): Define. * gimplify.cc (gimplify_call_expr): Gimplify IFN_ASSUME. * fold-const.h (simple_condition_p): Declare. * fold-const.cc (simple_operand_p_2): Rename to ... (simple_condition_p): ... this. Remove forward declaration. No longer static. Adjust function comment and fix a typo in it. Adjust recursive call. (simple_operand_p): Adjust function comment. (fold_truth_andor): Adjust simple_operand_p_2 callers to call simple_condition_p. * doc/extend.texi: Document assume attribute. Move fallthrough attribute example to its section. gcc/c-family/ * c-attribs.cc (handle_assume_attribute): New function. (c_common_attribute_table): Add entry for assume attribute. * c-lex.cc (c_common_has_attribute): Handle __have_cpp_attribute (assume). gcc/c/ * c-parser.cc (handle_assume_attribute): New function. (c_parser_declaration_or_fndef): Handle assume attribute. (c_parser_attribute_arguments): Add assume_attr argument, if true, parse first argument as conditional expression. (c_parser_gnu_attribute, c_parser_std_attribute): Adjust c_parser_attribute_arguments callers. (c_parser_statement_after_labels) <case RID_ATTRIBUTE>: Handle assume attribute. gcc/cp/ * cp-tree.h (process_stmt_assume_attribute): Implement C++23 P1774R8 - Portable assumptions. Declare. (diagnose_failing_condition): Declare. (find_failing_clause): Likewise. * parser.cc (assume_attr): New enumerator. (cp_parser_parenthesized_expression_list): Handle assume_attr. Remove identifier variable, for id_attr push the identifier into expression_list right away instead of inserting it before all the others at the end. (cp_parser_conditional_expression): New function. (cp_parser_constant_expression): Use it. (cp_parser_statement): Handle assume attribute. (cp_parser_expression_statement): Likewise. (cp_parser_gnu_attribute_list): Use assume_attr for assume attribute. (cp_parser_std_attribute): Likewise. Handle standard assume attribute like gnu::assume. * cp-gimplify.cc (process_stmt_assume_attribute): New function. * constexpr.cc: Include fold-const.h. (find_failing_clause_r, find_failing_clause): New functions, moved from semantics.cc with ctx argument added and if non-NULL, call cxx_eval_constant_expression rather than fold_non_dependent_expr. (cxx_eval_internal_function): Handle IFN_ASSUME. (potential_constant_expression_1): Likewise. * pt.cc (tsubst_copy_and_build): Likewise. * semantics.cc (diagnose_failing_condition): New function. (find_failing_clause_r, find_failing_clause): Moved to constexpr.cc. (finish_static_assert): Use it. Add auto_diagnostic_group. gcc/testsuite/ * gcc.dg/attr-assume-1.c: New test. * gcc.dg/attr-assume-2.c: New test. * gcc.dg/attr-assume-3.c: New test. * g++.dg/cpp2a/feat-cxx2a.C: Add colon to C++20 features comment, add C++20 attributes comment and move C++20 new features after the attributes before them. * g++.dg/cpp23/feat-cxx2b.C: Likewise. Test __has_cpp_attribute(assume). * g++.dg/cpp23/attr-assume1.C: New test. * g++.dg/cpp23/attr-assume2.C: New test. * g++.dg/cpp23/attr-assume3.C: New test. * g++.dg/cpp23/attr-assume4.C: New test.
Created attachment 53675 [details] gcc13-pr106654-gimple-wip.patch My current WIP patch for the handling of more complex assumptions. My current testcase is for -O2: int foo (int x) { [[assume (x == 42)]]; return x; } int bar (int x) { [[assume (++x == 43)]]; return x; } int baz (int x) { [[assume (({ int z = ++x; if (z == 51) return -1; if (z == 53) goto lab1; z == 43; }))]]; lab1: return x; } Before IPA, that is roughly how I'd like it to look like. What still needs to be done is: 1) mark the assumption functions somehow and arrange for not being actually expanded into RTL, just the bodies kept around for optimization of other functions 2) for LTO ideally ensure they are duplicated in every partition that refers to them 3) teach ranger to get something useful ouf ot it 4) perhaps for later, decide what to do e.g. for SRA, so that passing an argument by value to .ASSUME doesn't prevent its SRA optimization 5) guess see if one can somehow bypass fab pass (-fdisable-tree-fab doesn't seem to work) and if yes, don't ICE if .ASSUME call makes it down to expansion, instead fold it away right before or during expansion such that args don't need to be evaluated) Anyway, I must be doing something wrong, because on the above testcase I get ICE in: during RTL pass: expand a.C: In function ‘_Z3bari._assume.0’: a.C:11:3: internal compiler error: in adjust_one_expanded_partition_var, at cfgexpand.cc:1577 11 | [[assume (++x == 43)]]; | ^~~~~~~~~~~~~~~~~~~~~~ 0x99d1ba adjust_one_expanded_partition_var ../../gcc/cfgexpand.cc:1577 0x9af44c execute ../../gcc/cfgexpand.cc:6737 where the name in question is default def for the argument - x_1(D): bool _Z3bari._assume.0 (int x) { bool _2; <bb 2> [local count: 1073741824]: _2 = x_1(D) == 42; return _2; }
Created attachment 53679 [details] gcc13-pr106654-gimple-wip.patch Updated patch with the ICE fixed (DECL_ARG_TYPE on the PARM_DECLs wasn't set) and 1) and 5) implemented.
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>: https://gcc.gnu.org/g:4dda30e9910c4f04a6258b053401249e213f29be commit r13-3353-g4dda30e9910c4f04a6258b053401249e213f29be Author: Jakub Jelinek <jakub@redhat.com> Date: Tue Oct 18 10:31:20 2022 +0200 middle-end IFN_ASSUME support [PR106654] My earlier patches gimplify the simplest non-side-effects assumptions into if (cond) ; else __builtin_unreachable (); and throw the rest on the floor. The following patch attempts to do something with the rest too. For -O0, it throws the more complex assumptions on the floor, we don't expect optimizations and the assumptions are there to allow optimizations. Otherwise arranges for the assumptions to be visible in the IL as .ASSUME (_Z2f4i._assume.0, i_1(D)); call where there is an artificial function like: bool _Z2f4i._assume.0 (int i) { bool _2; <bb 2> [local count: 1073741824]: _2 = i_1(D) == 43; return _2; } with the semantics that there is UB unless the assumption function would return true. Aldy, could ranger handle this? If it sees .ASSUME call, walk the body of such function from the edge(s) to exit with the assumption that the function returns true, so above set _2 [true, true] and from there derive that i_1(D) [43, 43] and then map the argument in the assumption function to argument passed to IFN_ASSUME (note, args there are shifted by 1)? During gimplification it actually gimplifies it into [[assume (D.2591)]] { { i = i + 1; D.2591 = i == 44; } } which is a new GIMPLE_ASSUME statement wrapping a GIMPLE_BIND and specifying a boolean_type_node variable which contains the result. The GIMPLE_ASSUME then survives just a couple of passes and is lowered during gimple lowering into an outlined separate function and IFN_ASSUME call. Variables declared inside of the condition (both static and automatic) just change context, automatic variables from the caller are turned into parameters (note, as the code is never executed, I handle this way even non-POD types, we don't need to bother pretending there would be user copy constructors etc. involved). The assume_function artificial functions are then optimized until the new assumptions pass which doesn't do much right now but I'd like to see there the backwards ranger walk and filling up of SSA_NAME_RANGE_INFO for the parameters. There are a few further changes I'd like to do, like ignoring the .ASSUME calls in inlining size estimations (but haven't figured out where it is done), or for LTO arrange for the assume functions to be emitted in all partitions that reference those (usually there will be just one, unless code with the assumption got inlined, versioned etc.). 2022-10-18 Jakub Jelinek <jakub@redhat.com> PR c++/106654 gcc/ * gimple.def (GIMPLE_ASSUME): New statement kind. * gimple.h (struct gimple_statement_assume): New type. (is_a_helper <gimple_statement_assume *>::test, is_a_helper <const gimple_statement_assume *>::test): New. (gimple_build_assume): Declare. (gimple_has_substatements): Return true for GIMPLE_ASSUME. (gimple_assume_guard, gimple_assume_set_guard, gimple_assume_guard_ptr, gimple_assume_body_ptr, gimple_assume_body): New inline functions. * gsstruct.def (GSS_ASSUME): New. * gimple.cc (gimple_build_assume): New function. (gimple_copy): Handle GIMPLE_ASSUME. * gimple-pretty-print.cc (dump_gimple_assume): New function. (pp_gimple_stmt_1): Handle GIMPLE_ASSUME. * gimple-walk.cc (walk_gimple_op): Handle GIMPLE_ASSUME. * omp-low.cc (WALK_SUBSTMTS): Likewise. (lower_omp_1): Likewise. * omp-oacc-kernels-decompose.cc (adjust_region_code_walk_stmt_fn): Likewise. * tree-cfg.cc (verify_gimple_stmt, verify_gimple_in_seq_2): Likewise. * function.h (struct function): Add assume_function bitfield. * gimplify.cc (gimplify_call_expr): If the assumption isn't simple enough, expand it into GIMPLE_ASSUME wrapped block or for -O0 drop it. * gimple-low.cc: Include attribs.h. (create_assumption_fn): New function. (struct lower_assumption_data): New type. (find_assumption_locals_r, assumption_copy_decl, adjust_assumption_stmt_r, adjust_assumption_stmt_op, lower_assumption): New functions. (lower_stmt): Handle GIMPLE_ASSUME. * tree-ssa-ccp.cc (pass_fold_builtins::execute): Remove IFN_ASSUME calls. * lto-streamer-out.cc (output_struct_function_base): Pack assume_function bit. * lto-streamer-in.cc (input_struct_function_base): And unpack it. * cgraphunit.cc (cgraph_node::expand): Don't verify assume_function has TREE_ASM_WRITTEN set and don't release its body. (symbol_table::compile): Allow assume functions not to have released body. * internal-fn.cc (expand_ASSUME): Remove gcc_unreachable. * passes.cc (execute_one_pass): For TODO_discard_function don't release body of assume functions. * cgraph.cc (cgraph_node::verify_node): Don't verify cgraph nodes of PROP_assumptions_done functions. * tree-pass.h (PROP_assumptions_done): Define. (TODO_discard_function): Adjust comment. (make_pass_assumptions): Declare. * passes.def (pass_assumptions): Add. * timevar.def (TV_TREE_ASSUMPTIONS): New. * tree-inline.cc (remap_gimple_stmt): Handle GIMPLE_ASSUME. * tree-vrp.cc (pass_data_assumptions): New variable. (pass_assumptions): New class. (make_pass_assumptions): New function. gcc/cp/ * cp-tree.h (build_assume_call): Declare. * parser.cc (cp_parser_omp_assumption_clauses): Use build_assume_call. * cp-gimplify.cc (build_assume_call): New function. (process_stmt_assume_attribute): Use build_assume_call. * pt.cc (tsubst_copy_and_build): Likewise. gcc/testsuite/ * g++.dg/cpp23/attr-assume5.C: New test. * g++.dg/cpp23/attr-assume6.C: New test. * g++.dg/cpp23/attr-assume7.C: New test.
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>: https://gcc.gnu.org/g:53e6d7a3102409f0f2a5a9ffbfbeaa62c135d991 commit r13-3394-g53e6d7a3102409f0f2a5a9ffbfbeaa62c135d991 Author: Andrew MacLeod <amacleod@redhat.com> Date: Tue Oct 18 16:29:49 2022 -0400 Add assume support to VRP. This provides an assume_query class using rangers GORI module to determine what ranges would be applied to any SSA NAMES in the function if the return value were [1, 1]. Any parameter ranges are stored in the SSA_NAME_RANGE_INFO field, and ranger's inferred range machinery is then used to look these up and match them to assume call parameteres in the bodies of other functions.. PR c++/106654 gcc/ * gimple-range-gori.h (compute_operand_range): Make public. * gimple-range-infer.cc (gimple_infer_range::check_assume_func): New. (gimple_infer_range::gimple_infer_range): Check for assume calls. * gimple-range-infer.h (check_assume_func): Add prototype. * gimple-range.cc (assume_query::assume_range_p): New. (assume_query::range_of_expr): New. (assume_query::assume_query): New. (assume_query::calculate_op): New. (assume_query::calculate_phi): New. (assume_query::check_taken_edge): New. (assume_query::calculate_stmt): New. (assume_query::dump): New. * gimple-range.h (class assume_query): New. * tree-vrp.cc (pass_assumptions::execute): Add processing. gcc/testsuite/ * g++.dg/cpp23/attr-assume-opt.C: New.
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>: https://gcc.gnu.org/g:d155442de043c1bef7d27cf2d6be4eba618afcb9 commit r13-3420-gd155442de043c1bef7d27cf2d6be4eba618afcb9 Author: Aldy Hernandez <aldyh@redhat.com> Date: Thu Oct 20 18:26:42 2022 +0200 [PR c++/106654] Handle non-irange ranges in get_range_global for default defs. With the upcoming [[assume]] work, Andrew has pointed out that non-irange ranges are not handled in get_range_global for SSA_NAME_IS_DEFAULT_DEF. This patch fixes the oversight. PR c++/106654 gcc/ChangeLog: * value-query.cc (get_range_global): Handle non integer ranges for default def SSA names.
Implemented for GCC 13.