From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2140) id 8A5633858284; Wed, 24 Aug 2022 22:59:26 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8A5633858284 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661381966; bh=wY5j1q1LLBWlRKcQ+0zZWeM+6njaLXfQzJQXlZUQYZQ=; h=From:To:Subject:Date:From; b=HwcpHhYnwBm2+7jRiwgMJ+pNJwvgADDauCQJcMA0qHqIFu7sZ6JWpfMXWr0YThfLZ tgU3AIIWFbF+DZND5SpWwiM5Q4pD/ayiBofwSwJrQyv4eeeeWtcZ85a2iZu0XEQZRj PA0LJSflUl2/G+/7v/9baXExC2xS4eGRrNn8THio= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Alexandre Oliva To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/aoliva/heads/testme)] Control flow redundancy hardening X-Act-Checkin: gcc X-Git-Author: Alexandre Oliva X-Git-Refname: refs/users/aoliva/heads/testme X-Git-Oldrev: e5428086c2c8daf69e5916dd5016d1e7b85d3f0d X-Git-Newrev: e8f59982ad27b3e7c88d88f5515b205992be8bb5 Message-Id: <20220824225926.8A5633858284@sourceware.org> Date: Wed, 24 Aug 2022 22:59:26 +0000 (GMT) List-Id: https://gcc.gnu.org/g:e8f59982ad27b3e7c88d88f5515b205992be8bb5 commit e8f59982ad27b3e7c88d88f5515b205992be8bb5 Author: Alexandre Oliva Date: Wed Aug 24 19:57:58 2022 -0300 Control flow redundancy hardening This patch introduces an optional hardening pass to catch unexpected execution flows. Functions are transformed so that basic blocks set a bit in an automatic array, and (non-exceptional) function exit edges check that the bits in the array represent an expected execution path in the CFG. Functions with multiple exit edges, or with too many blocks, call an out-of-line checker builtin implemented in libgcc. For simpler functions, the verification is performed in-line. -fharden-control-flow-redundancy enables the pass for eligible functions, --param hardcfr-max-blocks sets a block count limit for functions to be eligible, and --param hardcfr-max-inline-blocks tunes the "too many blocks" limit for in-line verification. for gcc/ChangeLog * Makefile.in (OBJS): Add gimple-harden-control-flow.o. * builtins.def (BUILT_IN___HARDCFR_CHECK): New. * common.opt (fharden-control-flow-redundancy): New. * doc/invoke.texi (fharden-control-flow-redundancy): New. (hardcfr-max-blocks, hardcfr-max-inline-blocks): New params. * gimple-harden-control-flow.cc: New. * params.opt (-param=hardcfr-max-blocks=): New. (-param=hradcfr-max-inline-blocks=): New. * passes.def (pass_harden_control_flow_redundancy): Add. * tree-pass.h (make_pass_harden_control_flow_redundancy): Declare. for gcc/testsuite/ChangeLog * c-c++-common/torture/harden-cfr.c: New. * c-c++-common/torture/harden-abrt.c: New. * c-c++-common/torture/harden-bref.c: New. * c-c++-common/torture/harden-tail.c: New. * gnat.dg/hardcfr.adb: New. for libgcc/ChangeLog * Makefile.in (LIB2ADD): Add hardcfr.c. * hardcfr.c: New. Diff: --- gcc/Makefile.in | 1 + gcc/builtins.def | 3 + gcc/common.opt | 4 + gcc/doc/invoke.texi | 19 + gcc/gimple-harden-control-flow.cc | 713 +++++++++++++++++++++ gcc/params.opt | 8 + gcc/passes.def | 1 + .../c-c++-common/torture/harden-cfr-abrt.c | 11 + .../c-c++-common/torture/harden-cfr-bret.c | 11 + .../c-c++-common/torture/harden-cfr-tail.c | 17 + gcc/testsuite/c-c++-common/torture/harden-cfr.c | 81 +++ gcc/testsuite/gnat.dg/hardcfr.adb | 76 +++ gcc/tree-pass.h | 2 + libgcc/Makefile.in | 3 + libgcc/hardcfr.c | 176 +++++ 15 files changed, 1126 insertions(+) diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 203f0a15187..eb2cb8cbf6b 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1403,6 +1403,7 @@ OBJS = \ gimple-iterator.o \ gimple-fold.o \ gimple-harden-conditionals.o \ + gimple-harden-control-flow.o \ gimple-laddress.o \ gimple-loop-interchange.o \ gimple-loop-jam.o \ diff --git a/gcc/builtins.def b/gcc/builtins.def index 005976f34e9..b987f9af425 100644 --- a/gcc/builtins.def +++ b/gcc/builtins.def @@ -1055,6 +1055,9 @@ DEF_GCC_BUILTIN (BUILT_IN_FILE, "FILE", BT_FN_CONST_STRING, ATTR_NOTHROW_LEAF_LI DEF_GCC_BUILTIN (BUILT_IN_FUNCTION, "FUNCTION", BT_FN_CONST_STRING, ATTR_NOTHROW_LEAF_LIST) DEF_GCC_BUILTIN (BUILT_IN_LINE, "LINE", BT_FN_INT, ATTR_NOTHROW_LEAF_LIST) +/* Control Flow Redundancy hardening out-of-line checker. */ +DEF_BUILTIN_STUB (BUILT_IN___HARDCFR_CHECK, "__builtin___hardcfr_check") + /* Synchronization Primitives. */ #include "sync-builtins.def" diff --git a/gcc/common.opt b/gcc/common.opt index fba90ff6dcb..e347251f713 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1797,6 +1797,10 @@ fharden-conditional-branches Common Var(flag_harden_conditional_branches) Optimization Harden conditional branches by checking reversed conditions. +fharden-control-flow-redundancy +Common Var(flag_harden_control_flow_redundancy) Optimization +Harden control flow by recording and checking execution paths. + ; Nonzero means ignore `#ident' directives. 0 means handle them. ; Generate position-independent code for executables if possible ; On SVR4 targets, it also controls whether or not to emit a diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 3359313d9c5..df626a0ea39 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -624,6 +624,7 @@ Objective-C and Objective-C++ Dialects}. -fsanitize-undefined-trap-on-error -fbounds-check @gol -fcf-protection=@r{[}full@r{|}branch@r{|}return@r{|}none@r{|}check@r{]} @gol -fharden-compares -fharden-conditional-branches @gol +-fharden-control-flow-redundancy @gol -fstack-protector -fstack-protector-all -fstack-protector-strong @gol -fstack-protector-explicit -fstack-check @gol -fstack-limit-register=@var{reg} -fstack-limit-symbol=@var{sym} @gol @@ -15118,6 +15119,16 @@ A value of zero can be used to lift the bound. A variable whose value is unknown at compilation time and defined outside a SCoP is a parameter of the SCoP. +@item hardcfr-max-blocks +Disable @option{-fharden-control-flow-redundancy} for functions with a +larger number of blocks than the specified value. Zero removes any +limit. + +@item hardcfr-max-inline-blocks +Force @option{-fharden-control-flow-redundancy} to use out-of-line +checking for functions with a larger number of basic blocks than the +specified value. + @item loop-block-tile-size Loop blocking or strip mining transforms, enabled with @option{-floop-block} or @option{-floop-strip-mine}, strip mine each @@ -16542,6 +16553,14 @@ condition, and to call @code{__builtin_trap} if the result is unexpected. Use with @samp{-fharden-compares} to cover all conditionals. +@item -fharden-control-flow-redundancy +@opindex fharden-control-flow-redundancy +Emit extra code to set booleans when entering basic blocks, and to +verify, at function exits, that they amount to an execution path that is +consistent with the control flow graph, trapping otherwise. Tuning +options @option{--param hardcfr-max-blocks} and @option{--param +hardcfr-max-inline-blocks} are available. + @item -fstack-protector @opindex fstack-protector Emit extra code to check for buffer overflows, such as stack smashing diff --git a/gcc/gimple-harden-control-flow.cc b/gcc/gimple-harden-control-flow.cc new file mode 100644 index 00000000000..6b08846dbb1 --- /dev/null +++ b/gcc/gimple-harden-control-flow.cc @@ -0,0 +1,713 @@ +/* Control flow redundancy hardening. + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Alexandre Oliva . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "fold-const.h" +#include "gimple.h" +#include "gimplify.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "basic-block.h" +#include "cfghooks.h" +#include "cfgloop.h" +#include "cgraph.h" +#include "alias.h" +#include "varasm.h" +#include "output.h" +#include "langhooks.h" +#include "diagnostic.h" +#include "intl.h" + +namespace { + +/* This pass introduces verification, at function exits, that booleans + set in each basic block during function execution reflect the + control flow graph: for each visited block, check that at least one + predecessor and at least one successor were also visited. This + sort of hardening may detect various kinds of attacks. */ + +/* Define a pass to harden code through control flow redundancy. */ + +const pass_data pass_data_harden_control_flow_redundancy = { + GIMPLE_PASS, + "hardcfr", + OPTGROUP_NONE, + TV_NONE, + PROP_cfg | PROP_ssa, // properties_required + 0, // properties_provided + 0, // properties_destroyed + TODO_cleanup_cfg, // properties_start + TODO_update_ssa + | TODO_cleanup_cfg + | TODO_verify_il, // properties_finish +}; + +class pass_harden_control_flow_redundancy : public gimple_opt_pass +{ +public: + pass_harden_control_flow_redundancy (gcc::context *ctxt) + : gimple_opt_pass (pass_data_harden_control_flow_redundancy, ctxt) + {} + opt_pass *clone () { return new pass_harden_control_flow_redundancy (m_ctxt); } + virtual bool gate (function *fun) { + /* Return quickly if the pass is disabled, without checking any of + the conditions that might give rise to warnings that would only + be appropriate if hardening was requested. */ + if (!flag_harden_control_flow_redundancy) + return false; + + /* We don't verify when an exception escapes, propagated or raised + by the function itself, so we're only concerned with edges to + the exit block. If there aren't any, the function doesn't + return normally, so there won't be any checking point, so + there's no point in running the pass. Should we add + verification at exception escapes, we should at least look at + !flag_exceptions here. */ + if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (fun)->preds) == 0) + return false; + + /* Functions that return more than once, like setjmp and vfork + (that also gets this flag set), will start recording a path + after the first return, and then may take another path when + they return again. The unterminated path may then be flagged + as an error. ??? We could save the visited array before the + call and restore it if it returns again. */ + if (fun->calls_setjmp) + { + warning_at (DECL_SOURCE_LOCATION (fun->decl), 0, + "%qD calls % or similar," + " %<-fharden-control-flow-redundancy%> is not supported", + fun->decl); + return false; + } + + /* Some targets bypass the abnormal dispatcher block in nonlocal + gotos, and then we'd miss its visited bit. It might be doable + to make it work uniformly, but this feature is not used often + enough to make it worthwhile. */ + if (fun->has_nonlocal_label) + { + warning_at (DECL_SOURCE_LOCATION (fun->decl), 0, + "%qD receives nonlocal gotos," + " %<-fharden-control-flow-redundancy%> is not supported", + fun->decl); + return false; + } + + if (param_hardcfr_max_blocks > 0 + && n_basic_blocks_for_fn (fun) - 2 > param_hardcfr_max_blocks) + { + warning_at (DECL_SOURCE_LOCATION (fun->decl), 0, + "%qD has more than %u blocks, the requested" + " maximum for %<-fharden-control-flow-redundancy%>", + fun->decl, param_hardcfr_max_blocks); + return false; + } + + return true; + } + virtual unsigned int execute (function *); +}; + +} + +class rt_bb_visited +{ + /* Use a sufficiently wide unsigned type to hold basic block numbers. */ + typedef size_t blknum; + + /* Record the original block count of the function. */ + blknum nblocks; + /* Record the number of bits per VWORD (short for VISITED WORD), an + efficient mode to set and test bits for blocks we visited, and to + encode the CFG in case out-of-line verification is used. */ + unsigned vword_bits; + + /* Hold the unsigned integral VWORD type. */ + tree vword_type; + /* Hold a pointer-to-VWORD type. */ + tree vword_ptr; + + /* Hold a growing sequence used to check, inline or out-of-line, + that VISITED encodes an expected execution path. */ + gimple_seq ckseq; + /* If nonNULL, hold a growing representation of the CFG for + out-of-line testing. */ + tree rtcfg; + + /* Hold the declaration of an array of VWORDs, used as an array of + NBLOCKS-2 bits. */ + tree visited; + + /* If performing inline checking, hold a declarations of boolean + variables used for inline checking. CKBLK holds the result of + testing whether the VISITED bit corresponding to a predecessor or + successor is set, CKINV inverts that bit, CKPART gets cleared if + a block was not visited or if CKINV for any of its predecessors + or successors is set, and CKFAIL gets set if CKPART remains set + at the end of a block's predecessors or successors list. */ + tree ckfail, ckpart, ckinv, ckblk; + + /* Convert a block index N to a block vindex, the index used to + identify it in the VISITED array. Check that it's in range: + neither ENTRY nor EXIT, but maybe one-past-the-end, to compute + the visited array length. */ + blknum num2idx (blknum n) { + gcc_checking_assert (n >= 2 && n <= nblocks); + return (n - 2); + } + /* Return the block vindex for BB, that must not be ENTRY or + EXIT. */ + blknum bb2idx (basic_block bb) { + gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) + && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); + gcc_checking_assert (blknum (bb->index) < nblocks); + return num2idx (bb->index); + } + + /* Compute the type to be used for the VISITED array. */ + tree vtype () + { + blknum n = num2idx (nblocks); + return build_array_type_nelts (vword_type, + (n + vword_bits - 1) / vword_bits); + } + + /* Compute and return the index into VISITED for block BB. If BITP + is non-NULL, also compute and store the bit mask corresponding to + block BB in *BITP, so that (visited[index] & mask) tells whether + BB was visited. */ + tree vwordidx (basic_block bb, tree *bitp = NULL) + { + blknum idx = bb2idx (bb); + if (bitp) + { + unsigned bit = idx % vword_bits; + if (BITS_BIG_ENDIAN) + bit = vword_bits - bit - 1; + wide_int wbit = wi::set_bit_in_zero (bit, vword_bits); + *bitp = wide_int_to_tree (vword_type, wbit); + } + return build_int_cst (vword_ptr, idx / vword_bits); + } + + /* Return an expr to accesses the visited element that holds + information about BB. If BITP is non-NULL, set it to the mask to + tell which bit in that expr refers to BB. */ + tree vword (basic_block bb, tree *bitp = NULL) + { + return build2 (MEM_REF, vword_type, + build1 (ADDR_EXPR, vword_ptr, visited), + int_const_binop (MULT_EXPR, vwordidx (bb, bitp), + fold_convert (vword_ptr, + TYPE_SIZE_UNIT + (vword_type)))); + } + + /* Return an expr that evaluates to true iff BB was marked as + VISITED. Add any gimple stmts to SEQP. */ + tree vindex (basic_block bb, gimple_seq *seqp) + { + if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) + || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) + return boolean_true_node; + + tree bit, setme = vword (bb, &bit); + tree temp = create_tmp_var (vword_type, ".cfrtemp"); + + gassign *vload = gimple_build_assign (temp, setme); + gimple_seq_add_stmt (seqp, vload); + + gassign *vmask = gimple_build_assign (temp, BIT_AND_EXPR, temp, bit); + gimple_seq_add_stmt (seqp, vmask); + + return build2 (NE_EXPR, boolean_type_node, + temp, build_int_cst (vword_type, 0)); + } + + /* Set the bit corresponding to BB in VISITED. Add to SEQ any + required gimple statements, and return SEQ, possibly + modified. */ + gimple_seq vset (basic_block bb, gimple_seq seq = NULL) + { + tree bit, setme = vword (bb, &bit); + tree temp = create_tmp_var (vword_type, ".cfrtemp"); + + gassign *vload = gimple_build_assign (temp, setme); + gimple_seq_add_stmt (&seq, vload); + + gassign *vbitset = gimple_build_assign (temp, BIT_IOR_EXPR, temp, bit); + gimple_seq_add_stmt (&seq, vbitset); + + gassign *vstore = gimple_build_assign (unshare_expr (setme), temp); + gimple_seq_add_stmt (&seq, vstore); + + return seq; + } + +public: + /* Prepare to add control flow redundancy testing to CFUN. */ + rt_bb_visited () + : nblocks (n_basic_blocks_for_fn (cfun)), + vword_type (NULL), ckseq (NULL), rtcfg (NULL) + { + /* If we've already added a declaration for the builtin checker, + extract vword_type and vword_bits from its declaration. */ + if (tree checkfn = builtin_decl_explicit (BUILT_IN___HARDCFR_CHECK)) + { + tree check_arg_list = TYPE_ARG_TYPES (TREE_TYPE (checkfn)); + tree vword_const_ptr_type = TREE_VALUE (TREE_CHAIN (check_arg_list)); + vword_type = TYPE_MAIN_VARIANT (TREE_TYPE (vword_const_ptr_type)); + vword_bits = tree_to_shwi (TYPE_SIZE (vword_type)); + } + /* Otherwise, select vword_bits, vword_type et al, and use it to + declare the builtin checker. */ + else + { + /* This setting needs to be kept in sync with libgcc/hardcfr.c. + We aim for at least 28 bits, which enables us to refer to as + many as 28 << 28 blocks in a function's CFG. That's way over + 4G blocks. */ + machine_mode VWORDmode; + if (BITS_PER_UNIT >= 28) + { + VWORDmode = QImode; + vword_bits = BITS_PER_UNIT; + } + else if (BITS_PER_UNIT >= 14) + { + VWORDmode = HImode; + vword_bits = 2 * BITS_PER_UNIT; + } + else + { + VWORDmode = SImode; + vword_bits = 4 * BITS_PER_UNIT; + } + + vword_type = lang_hooks.types.type_for_mode (VWORDmode, 1); + gcc_checking_assert (vword_bits == tree_to_shwi (TYPE_SIZE + (vword_type))); + + vword_type = build_variant_type_copy (vword_type); + TYPE_ALIAS_SET (vword_type) = new_alias_set (); + + tree vword_const = build_qualified_type (vword_type, TYPE_QUAL_CONST); + tree vword_const_ptr = build_pointer_type (vword_const); + tree type = build_function_type_list (void_type_node, sizetype, + vword_const_ptr, vword_const_ptr, + NULL_TREE); + tree decl = add_builtin_function_ext_scope + ("__builtin___hardcfr_check", + type, BUILT_IN___HARDCFR_CHECK, BUILT_IN_NORMAL, + "__hardcfr_check", NULL_TREE); + TREE_NOTHROW (decl) = true; + set_builtin_decl (BUILT_IN___HARDCFR_CHECK, decl, true); + } + + /* The checker uses a qualified pointer, so we can't reuse it, + so build a new one. */ + vword_ptr = build_pointer_type (vword_type); + + tree visited_type = vtype (); + visited = create_tmp_var (visited_type, ".cfrvisited"); + + /* Prevent stores into visited from being used to optimize the + control flow redundancy checks. asm ("" : "+m" (visited)); */ + vec *inputs = NULL; + vec *outputs = NULL; + vec_safe_push (outputs, + build_tree_list + (build_tree_list + (NULL_TREE, build_string (2, "=m")), + visited)); + vec_safe_push (inputs, + build_tree_list + (build_tree_list + (NULL_TREE, build_string (1, "m")), + visited)); + gasm *detach = gimple_build_asm_vec ("", inputs, outputs, + NULL, NULL); + gimple_seq_add_stmt (&ckseq, detach); + + if (nblocks - 2 > blknum (param_hardcfr_max_inline_blocks) + || !single_pred_p (EXIT_BLOCK_PTR_FOR_FN (cfun))) + { + /* Make sure vword_bits is wide enough for the representation + of nblocks in rtcfg. Compare with vword_bits << vword_bits, + but avoiding overflows, shifting nblocks right instead. If + vword_bits is wider than HOST_WIDE_INT, assume it fits, so + as to avoid undefined shifts. */ + gcc_assert (HOST_BITS_PER_WIDE_INT <= vword_bits + || (((unsigned HOST_WIDE_INT)(num2idx (nblocks)) + >> vword_bits) < vword_bits)); + + /* Build a terminator for the constructor list. */ + rtcfg = build_tree_list (NULL_TREE, NULL_TREE); + return; + } + + ckfail = create_tmp_var (boolean_type_node, ".cfrfail"); + ckpart = create_tmp_var (boolean_type_node, ".cfrpart"); + ckinv = create_tmp_var (boolean_type_node, ".cfrinv"); + ckblk = create_tmp_var (boolean_type_node, ".cfrblk"); + + gassign *ckfail_init = gimple_build_assign (ckfail, boolean_false_node); + gimple_seq_add_stmt (&ckseq, ckfail_init); + } + + /* Insert SEQ on E, or close enough (e.g., before a noreturn or tail + call at the end of E->src). */ + void insert_exit_check (gimple_seq seq, edge e) + { + basic_block insbb = e->src; + + /* If the returning block ends with a noreturn call, insert + checking before it. This is particularly important for + __builtin_return. Other noreturn calls won't have an edge to + the exit block, so they won't even be considered as exit paths. + + Insert-on-edge inserts before other return stmts, but not + before calls, and if a single-block function had the check + sequence inserted after a noreturn call, it would be useless, + but checking would still flag it as malformed if block 2 has a + fallthru edge to the exit block. + + Also avoid disrupting tail calls, inserting the check before + them. This works for must-tail calls, but tail calling as an + optimization is detected too late for us. */ + gimple_stmt_iterator gsi = gsi_last_bb (insbb); + gimple *ret = gsi_stmt (gsi); + if (ret && is_a (ret)) + { + gsi_prev (&gsi); + if (!gsi_end_p (gsi)) + ret = gsi_stmt (gsi); + } + if (ret && is_a (ret) + && (gimple_call_noreturn_p (ret) + || gimple_call_must_tail_p (as_a (ret)) + || gimple_call_tail_p (as_a (ret)))) + gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT); + else + gsi_insert_seq_on_edge_immediate (e, seq); + } + + /* Add checking code on every exit edge, and initialization code on + the entry edge. Before this point, the CFG has been undisturbed, + and all the needed data has been collected and safely stowed. */ + void check () + { + /* Insert initializers for visited at the entry. */ + gimple_seq iseq = NULL; + + gcall *vinit = gimple_build_call (builtin_decl_explicit + (BUILT_IN_MEMSET), 3, + build1 (ADDR_EXPR, + build_pointer_type + (TREE_TYPE (visited)), + visited), + integer_zero_node, + TYPE_SIZE_UNIT (TREE_TYPE (visited))); + gimple_seq_add_stmt (&iseq, vinit); + + gsi_insert_seq_on_edge_immediate (single_succ_edge + (ENTRY_BLOCK_PTR_FOR_FN (cfun)), + iseq); + + /* If we're using out-of-line checking, create and statically + initialize the CFG checking representation, generate the + checker call for the checking sequence, and insert it in all + exit edges, if there's more than one. If there's only one, we + use the same logic as the inline case to insert the check + sequence. */ + if (rtcfg) + { + /* Unreverse the list, and drop the tail node turned into head. */ + rtcfg = TREE_CHAIN (nreverse (rtcfg)); + + /* Turn the indices stored in TREE_PURPOSE into separate + nodes. It was useful to keep them together to enable + combination of masks and for clear separation of + terminators while constructing it, but now we have to turn + it into a sequence of words. */ + for (tree node = rtcfg; node; node = TREE_CHAIN (node)) + { + tree wordidx = TREE_PURPOSE (node); + if (!wordidx) + continue; + + TREE_PURPOSE (node) = NULL_TREE; + TREE_CHAIN (node) = tree_cons (NULL_TREE, + fold_convert (vword_type, wordidx), + TREE_CHAIN (node)); + } + + /* Build the static initializer for the array with the CFG + representation for out-of-line checking. */ + tree init = build_constructor_from_list (NULL_TREE, rtcfg); + TREE_TYPE (init) = build_array_type_nelts (vword_type, + CONSTRUCTOR_NELTS (init)); + char buf[32]; + ASM_GENERATE_INTERNAL_LABEL (buf, "Lhardcfg", + current_function_funcdef_no); + rtcfg = build_decl (UNKNOWN_LOCATION, VAR_DECL, + get_identifier (buf), + TREE_TYPE (init)); + TREE_READONLY (rtcfg) = 1; + TREE_STATIC (rtcfg) = 1; + TREE_ADDRESSABLE (rtcfg) = 1; + TREE_USED (rtcfg) = 1; + DECL_ARTIFICIAL (rtcfg) = 1; + DECL_IGNORED_P (rtcfg) = 1; + DECL_INITIAL (rtcfg) = init; + make_decl_rtl (rtcfg); + varpool_node::finalize_decl (rtcfg); + + /* Add the checker call to ckseq. */ + gcall *call_chk = gimple_build_call (builtin_decl_explicit + (BUILT_IN___HARDCFR_CHECK), 3, + build_int_cst (sizetype, + num2idx (nblocks)), + build1 (ADDR_EXPR, vword_ptr, + visited), + build1 (ADDR_EXPR, vword_ptr, + rtcfg)); + gimple_seq_add_stmt (&ckseq, call_chk); + + /* If we have multiple exit edges, insert (copies of) + ckseq in all of them. */ + for (int i = EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds); + i--; ) + { + gimple_seq seq = ckseq; + /* Copy the sequence, unless we're dealing with the + last edge (we're counting down to zero). */ + if (i) + seq = gimple_seq_copy (seq); + + insert_exit_check (seq, + EDGE_PRED (EXIT_BLOCK_PTR_FOR_FN (cfun), i)); + } + } + else + { + /* Inline checking requires a single exit edge. */ + gimple *last = gsi_stmt (gsi_last (ckseq)); + + insert_exit_check (ckseq, + single_pred_edge (EXIT_BLOCK_PTR_FOR_FN (cfun))); + + /* The inserted ckseq computes CKFAIL at LAST. Now we have to + conditionally trap on it. */ + basic_block insbb = gimple_bb (last); + + /* Create a block with the unconditional trap. */ + basic_block trp = create_empty_bb (insbb); + gimple_stmt_iterator gsit = gsi_after_labels (trp); + + gcall *trap = gimple_build_call (builtin_decl_explicit + (BUILT_IN_TRAP), 0); + gsi_insert_before (&gsit, trap, GSI_SAME_STMT); + + if (BB_PARTITION (insbb)) + BB_SET_PARTITION (trp, BB_COLD_PARTITION); + + if (current_loops) + add_bb_to_loop (trp, current_loops->tree_root); + + /* Insert a conditional branch to the trap block. If the + conditional wouldn't be the last statement, split the + block. */ + gimple_stmt_iterator gsi = gsi_for_stmt (last); + if (!gsi_one_before_end_p (gsi)) + split_block (gsi_bb (gsi), gsi_stmt (gsi)); + + gcond *cond = gimple_build_cond (NE_EXPR, ckfail, + fold_convert (TREE_TYPE (ckfail), + boolean_false_node), + NULL, NULL); + gsi_insert_after (&gsi, cond, GSI_SAME_STMT); + + /* Adjust the edges. */ + single_succ_edge (gsi_bb (gsi))->flags &= ~EDGE_FALLTHRU; + single_succ_edge (gsi_bb (gsi))->flags |= EDGE_FALSE_VALUE; + single_succ_edge (gsi_bb (gsi))->probability + = profile_probability::always (); + edge e = make_edge (gsi_bb (gsi), trp, EDGE_TRUE_VALUE); + e->probability = profile_probability::never (); + + /* Set the trap's dominator after splitting. */ + if (dom_info_available_p (CDI_DOMINATORS)) + set_immediate_dominator (CDI_DOMINATORS, trp, gimple_bb (last)); + } + } + + /* Push onto RTCFG a (mask, index) pair to test for IBB when BB is + visited. XSELF is to be the ENTRY or EXIT block (depending on + whether we're looking at preds or succs), to be remapped to BB + because we can't represent them, and there's no point in testing + them anyway. Return true if no further blocks need to be visited + in the list, because we've already encountered a + self-reference. */ + bool + push_rtcfg_pair (basic_block ibb, basic_block bb, + basic_block xself) + { + /* We don't have a bit to test for the entry and exit + blocks, but it is always visited, so we test for the + block itself, which gets us the right result and + enables the self-test optimization below. */ + if (ibb == xself) + ibb = bb; + + tree mask, idx = vwordidx (ibb, &mask); + /* Combine masks with the same idx, but not if we're going + to optimize for self-test. */ + if (ibb != bb && TREE_PURPOSE (rtcfg) + && tree_int_cst_equal (idx, TREE_PURPOSE (rtcfg))) + TREE_VALUE (rtcfg) = int_const_binop (BIT_IOR_EXPR, mask, + TREE_VALUE (rtcfg)); + else + rtcfg = tree_cons (idx, mask, rtcfg); + + /* For self-tests (i.e., tests that the block itself was + also visited), testing anything else is pointless, + because it's a tautology, so just drop other edges. */ + if (ibb == bb) + { + while (TREE_PURPOSE (TREE_CHAIN (rtcfg))) + TREE_CHAIN (rtcfg) = TREE_CHAIN (TREE_CHAIN (rtcfg)); + return true; + } + + return false; + } + + /* Add to CKSEQ statements to clear CKPART if OBB is visited. */ + void + build_block_check (basic_block obb) + { + tree vobb = fold_convert (TREE_TYPE (ckblk), + vindex (obb, &ckseq)); + gassign *blkrunp = gimple_build_assign (ckblk, vobb); + gimple_seq_add_stmt (&ckseq, blkrunp); + + gassign *blknotrunp = gimple_build_assign (ckinv, + EQ_EXPR, + ckblk, + fold_convert + (TREE_TYPE (ckblk), + boolean_false_node)); + gimple_seq_add_stmt (&ckseq, blknotrunp); + + gassign *andblk = gimple_build_assign (ckpart, + BIT_AND_EXPR, + ckpart, ckinv); + gimple_seq_add_stmt (&ckseq, andblk); + } + + /* Add to BB code to set its bit in VISITED, and add to RTCFG or + CKSEQ the data or code needed to check BB's predecessors and + successors. Do NOT change the CFG. */ + void visit (basic_block bb) + { + /* Set the bit in VISITED when entering the block. */ + gimple_stmt_iterator gsi = gsi_after_labels (bb); + gsi_insert_seq_before (&gsi, vset (bb), GSI_SAME_STMT); + + if (rtcfg) + { + /* Build a list of (index, mask) terminated by (NULL, 0). + Consolidate masks with the same index when they're + adjacent. First, predecessors. Count backwards, because + we're going to reverse the list. The order shouldn't + matter, but let's not make it surprising. */ + for (int i = EDGE_COUNT (bb->preds); i--; ) + if (push_rtcfg_pair (EDGE_PRED (bb, i)->src, bb, + ENTRY_BLOCK_PTR_FOR_FN (cfun))) + break; + rtcfg = tree_cons (NULL_TREE, build_int_cst (vword_type, 0), rtcfg); + + /* Then, successors. */ + for (int i = EDGE_COUNT (bb->succs); i--; ) + if (push_rtcfg_pair (EDGE_SUCC (bb, i)->dest, bb, + EXIT_BLOCK_PTR_FOR_FN (cfun))) + break; + rtcfg = tree_cons (NULL_TREE, build_int_cst (vword_type, 0), rtcfg); + } + else + { + /* Schedule test to fail if the block was reached but somehow none + of its predecessors were. */ + tree bit = fold_convert (TREE_TYPE (ckpart), vindex (bb, &ckseq)); + gassign *blkrunp = gimple_build_assign (ckpart, bit); + gimple_seq_add_stmt (&ckseq, blkrunp); + + for (int i = 0, e = EDGE_COUNT (bb->preds); i < e; i++) + build_block_check (EDGE_PRED (bb, i)->src); + gimple *orfailp = gimple_build_assign (ckfail, BIT_IOR_EXPR, + ckfail, ckpart); + gimple_seq_add_stmt (&ckseq, orfailp); + + /* Likewise for successors. */ + gassign *blkruns = gimple_build_assign (ckpart, unshare_expr (bit)); + gimple_seq_add_stmt (&ckseq, blkruns); + + for (int i = 0, e = EDGE_COUNT (bb->succs); i < e; i++) + build_block_check (EDGE_SUCC (bb, i)->dest); + + gimple *orfails = gimple_build_assign (ckfail, BIT_IOR_EXPR, + ckfail, ckpart); + gimple_seq_add_stmt (&ckseq, orfails); + } + } +}; + +/* Control flow redundancy hardening: record the execution path, and + verify at exit that an expect path was taken. */ + +unsigned int +pass_harden_control_flow_redundancy::execute (function *) +{ + rt_bb_visited vstd; + + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + vstd.visit (bb); + + vstd.check (); + + return 0; +} + +/* Instantiate a hardcfr pass. */ + +gimple_opt_pass * +make_pass_harden_control_flow_redundancy (gcc::context *ctxt) +{ + return new pass_harden_control_flow_redundancy (ctxt); +} diff --git a/gcc/params.opt b/gcc/params.opt index 201b5c9f56f..ae214daa207 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -182,6 +182,14 @@ Maximum number of arrays per SCoP. Common Joined UInteger Var(param_graphite_max_nb_scop_params) Init(10) Param Optimization Maximum number of parameters in a SCoP. +-param=hardcfr-max-blocks= +Common Joined UInteger Var(param_hardcfr_max_blocks) Init(0) Param Optimization +Maximum number of blocks for -fharden-control-flow-redundancy. + +-param=hardcfr-max-inline-blocks= +Common Joined UInteger Var(param_hardcfr_max_inline_blocks) Init(16) Param Optimization +Maximum number of blocks for in-line -fharden-control-flow-redundancy. + -param=hash-table-verification-limit= Common Joined UInteger Var(param_hash_table_verification_limit) Init(10) Param The number of elements for which hash table verification is done for each searched element. diff --git a/gcc/passes.def b/gcc/passes.def index 6bb92efacd4..71588e4915b 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -191,6 +191,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_omp_device_lower); NEXT_PASS (pass_omp_target_link); NEXT_PASS (pass_adjust_alignment); + NEXT_PASS (pass_harden_control_flow_redundancy); NEXT_PASS (pass_all_optimizations); PUSH_INSERT_PASSES_WITHIN (pass_all_optimizations) NEXT_PASS (pass_remove_cgraph_callee_edges); diff --git a/gcc/testsuite/c-c++-common/torture/harden-cfr-abrt.c b/gcc/testsuite/c-c++-common/torture/harden-cfr-abrt.c new file mode 100644 index 00000000000..4aada93ad94 --- /dev/null +++ b/gcc/testsuite/c-c++-common/torture/harden-cfr-abrt.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr -ffat-lto-objects" } */ + +int f(int i) { + if (!i) + __builtin_abort (); + return i; +} + +/* No checking before the noreturn abort, so single inline check. */ +/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "hardcfr" } } */ diff --git a/gcc/testsuite/c-c++-common/torture/harden-cfr-bret.c b/gcc/testsuite/c-c++-common/torture/harden-cfr-bret.c new file mode 100644 index 00000000000..70acdc95f25 --- /dev/null +++ b/gcc/testsuite/c-c++-common/torture/harden-cfr-bret.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr -ffat-lto-objects" } */ + +int f(int i) { + if (i) + __builtin_return (&i); + return i; +} + +/* Out-of-line checking, before both builtin_return and return. */ +/* { dg-final { scan-tree-dump-times "__hardcfr_check" 2 "hardcfr" } } */ diff --git a/gcc/testsuite/c-c++-common/torture/harden-cfr-tail.c b/gcc/testsuite/c-c++-common/torture/harden-cfr-tail.c new file mode 100644 index 00000000000..40d76c5c163 --- /dev/null +++ b/gcc/testsuite/c-c++-common/torture/harden-cfr-tail.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr -ffat-lto-objects" } */ + +/* We'd like to check that we insert checking so as to not disrupt tail calls, + but unfortunately mandatory tail calls are not available in C, and optimizing + calls as tail calls only takes place after hardcfr. */ + +extern int g(int i); + +int f(int i) { + return g (i); +} + +/* Inline checking before the tail call. */ +/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "hardcfr" } } */ +/* Inline checking before the tail call. */ +/* { dg-final { scan-tree-dump-times "\\\[tail\]" 1 "hardcfr" { xfail *-*-* } } } */ diff --git a/gcc/testsuite/c-c++-common/torture/harden-cfr.c b/gcc/testsuite/c-c++-common/torture/harden-cfr.c new file mode 100644 index 00000000000..2f5946c0387 --- /dev/null +++ b/gcc/testsuite/c-c++-common/torture/harden-cfr.c @@ -0,0 +1,81 @@ +/* { dg-do run } */ +/* { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr --param hardcfr-max-blocks=9 --param hardcfr-max-inline-blocks=5 -ffat-lto-objects" } */ + +int +f (int i, int j) +{ + if (i < j) + return 2 * i; + else + return 3 * j; +} + +int +g (unsigned i, int j) +{ + switch (i) + { + case 0: + return j * 2; + + case 1: + return j * 3; + + case 2: + return j * 5; + + default: + return j * 7; + } +} + +int +h (unsigned i, int j) /* { dg-warning "has more than 9 blocks, the requested maximum" } */ +{ + switch (i) + { + case 0: + return j * 2; + + case 1: + return j * 3; + + case 2: + return j * 5; + + case 3: + return j * 7; + + case 4: + return j * 11; + + case 5: + return j * 13; + + case 6: + return j * 17; + + case 7: + return j * 19; + + default: + return j * 23; + } +} + +int +main () +{ + if (f (1, 2) != 2 || f (3, 2) != 6 + || g (2, 5) != 25 || h (4, 3) != 33) + __builtin_abort (); + /* Call exit, instead of returning, to avoid an edge to the exit block and + thus implicitly disable hardening of main. */ + __builtin_exit (0); +} + +/* Inlined checking thus trap for f. */ +/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "hardcfr" } } */ +/* Out-of-line checking for g. */ +/* { dg-final { scan-tree-dump-times "__hardcfr_check" 1 "hardcfr" } } */ +/* No checking for h (too many blocks) or main (no edges to exit block). */ diff --git a/gcc/testsuite/gnat.dg/hardcfr.adb b/gcc/testsuite/gnat.dg/hardcfr.adb new file mode 100644 index 00000000000..b578a913d75 --- /dev/null +++ b/gcc/testsuite/gnat.dg/hardcfr.adb @@ -0,0 +1,76 @@ +-- { dg-do run } +-- { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr --param=hardcfr-max-blocks=22 --param=hardcfr-max-inline-blocks=12 -O0" } + +procedure HardCFR is + function F (I, J : Integer) return Integer is + begin + if (I < J) then + return 2 * I; + else + return 3 * J; + end if; + end F; + + function G (I : Natural; J : Integer) return Integer is + begin + case I is + when 0 => + return J * 2; + + when 1 => + return J * 3; + + when 2 => + return J * 5; + + when others => + return J * 7; + end case; + end G; + + function H (I : Natural; -- { dg-warning "has more than 22 blocks, the requested maximum" } + J : Integer) + return Integer is + begin + case I is + when 0 => + return J * 2; + + when 1 => + return J * 3; + + when 2 => + return J * 5; + + when 3 => + return J * 7; + + when 4 => + return J * 11; + + when 5 => + return J * 13; + + when 6 => + return J * 17; + + when 7 => + return J * 19; + + when others => + return J * 23; + end case; + end H; +begin + if (F (1, 2) /= 2 or else F (3, 2) /= 6 + or else G (2, 5) /= 25 or else H (4, 3) /= 33) + then + raise Program_Error; + end if; +end HardCFR; + +-- HardCFR and HardCFR.F: +-- { dg-final { scan-tree-dump-times ".builtin_trap" 2 "hardcfr" } } + +-- This is __builtin___hardcfr_check in HardCFR.G: +-- { dg-final { scan-tree-dump-times ".builtin " 1 "hardcfr" } } diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 4dfe05ed8e0..6dfe7c5ec73 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -648,6 +648,8 @@ extern gimple_opt_pass *make_pass_gimple_isel (gcc::context *ctxt); extern gimple_opt_pass *make_pass_harden_compares (gcc::context *ctxt); extern gimple_opt_pass *make_pass_harden_conditional_branches (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_harden_control_flow_redundancy (gcc::context + *ctxt); /* Current optimization pass. */ extern opt_pass *current_pass; diff --git a/libgcc/Makefile.in b/libgcc/Makefile.in index 1fe708a93f7..2bdc1d4891a 100644 --- a/libgcc/Makefile.in +++ b/libgcc/Makefile.in @@ -430,6 +430,9 @@ endif LIB2ADD += enable-execute-stack.c +# Control Flow Redundancy hardening out-of-line checker. +LIB2ADD += $(srcdir)/hardcfr.c + # While emutls.c has nothing to do with EH, it is in LIB2ADDEH* # instead of LIB2ADD because that's the way to be sure on some targets # (e.g. *-*-darwin*) only one copy of it is linked. diff --git a/libgcc/hardcfr.c b/libgcc/hardcfr.c new file mode 100644 index 00000000000..8ef29428111 --- /dev/null +++ b/libgcc/hardcfr.c @@ -0,0 +1,176 @@ +/* Control flow redundancy hardening + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Alexandre Oliva + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +Under Section 7 of GPL version 3, you are granted additional +permissions described in the GCC Runtime Library Exception, version +3.1, as published by the Free Software Foundation. + +You should have received a copy of the GNU General Public License and +a copy of the GCC Runtime Library Exception along with this program; +see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +. */ + +/* Avoid infinite recursion. */ +#pragma GCC optimize ("-fno-harden-control-flow-redundancy") + +#include +#include + +/* This should be kept in sync with gcc/gimple-harden-control-flow.cc. */ +#if __CHAR_BIT__ >= 28 +# define VWORDmode __QI__ +#elif __CHHAR_BIT__ >= 14 +# define VWORDmode __HI__ +#else +# define VWORDmode __SI__ +#endif + +typedef unsigned int __attribute__ ((__mode__ (VWORDmode))) vword; + +/* This function is optionally called at the end of a function to verify that + the VISITED array represents a sensible execution path in the CFG. It is + always expected to pass; the purpose is to detect attempts to subvert + execution by taking unexpected paths, or other execution errors. The + function, instrumented by pass_harden_control_flow_redundancy at a time in + which it had BLOCKS basic blocks (not counting ENTER and EXIT, so block 2 + maps to index 0, the first bit of the first VWORD), sets a bit in the bit + array VISITED as it enters the corresponding basic block. CFG holds a + representation of the control flow graph at the time of the instrumentation: + an array of VWORDs holding, for each block, a sequence of predecessors, and + a sequence of successors. Each pred and succ sequence is represented as a + sequence of pairs (mask, index), terminated by an index-less all-zero mask. + If the bit corresponding to the block is set, then at least one of the pred + masks, and at least one of the succ masks, must have a bit set in + VISITED[index]. An ENTRY block predecessor and an EXIT block successor are + represented in a (mask, index) pair that tests the block's own bit. */ +extern void __hardcfr_check (size_t blocks, + vword const *visited, + vword const *cfg); + + +/* Check whether the bit corresponding to BLOCK is set in VISITED. */ +static inline bool +visited_p (size_t const block, vword const *const visited) +{ + size_t wbits = __CHAR_BIT__ * sizeof (vword); + vword w = visited[block / wbits]; + return (w & ((vword)1 << (block % wbits))) != 0; +} + +/* Read and consume a mask from **CFG_IT. (Consume meaning advancing the + iterator to the next word). If the mask is zero, return FALSE. Otherwise, + also read and consume an index, and set *MASK and/or *WORDIDX, whichever are + nonNULL, to the corresponding read values, and finally return TRUE. */ +static inline bool +next_pair (vword const **const cfg_it, + vword *const mask, + size_t *const wordidx) +{ + vword m = **cfg_it; + ++*cfg_it; + if (!m) + return false; + + if (mask) + *mask = m; + + size_t word = **cfg_it; + ++*cfg_it; + + if (wordidx) + *wordidx = word; + + return true; +} + +/* Return TRUE iff any of the bits in MASK is set in VISITED[WORDIDX]. */ +static inline bool +test_mask (vword const *const visited, + vword const mask, size_t const wordidx) +{ + return (visited[wordidx] & mask) != 0; +} + +/* Scan a sequence of pairs (mask, index) at **CFG_IT until its terminator is + reached and consumed. */ +static inline void +consume_seq (vword const **const cfg_it) +{ + while (next_pair (cfg_it, NULL, NULL)) + /* Do nothing. */; +} + +/* Check that at least one of the MASK bits in a sequence of pairs (mask, + index) at **CFG_IT is set in the corresponding VISITED[INDEX] word. Trap if + we reach the terminator without finding any. Consume the entire sequence + otherwise, so that *CFG_IT points just past the terminator, which may be the + beginning of the next sequence. */ +static inline void +check_seq (vword const *const visited, vword const **const cfg_it) +{ + vword mask; + size_t wordidx; + + /* If the block was visited, check that at least one of the + preds was also visited. */ + do + /* If we get to the end of the sequence without finding any + match, something is amiss. */ + if (!next_pair (cfg_it, &mask, &wordidx)) + __builtin_trap (); + /* Keep searching until we find a match, at which point the + condition is satisfied. */ + while (!test_mask (visited, mask, wordidx)); + + /* Consume the remaining entries in the sequence, whether we found a match or + skipped the block, so as to position the iterator at the beginning of the + next . */ + consume_seq (cfg_it); +} + +/* Check that, for each of the BLOCKS basic blocks, if its bit is set in + VISITED, at least one of its predecessors in CFG is also set, and at also + that at least one of its successors in CFG is also set. */ +void +__hardcfr_check (size_t const blocks, + vword const *const visited, + vword const *const cfg) +{ + vword const *cfg_it = cfg; + for (size_t i = 0; i < blocks; i++) + { + bool v = visited_p (i, visited); + + /* For each block, there are two sequences of pairs (mask, index), each + sequence terminated by a single all-zero mask (no index). The first + sequence is for predecessor blocks, the second is for successors. At + least one of each must be set. */ + if (!v) + { + /* Consume predecessors. */ + consume_seq (&cfg_it); + /* Consume successors. */ + consume_seq (&cfg_it); + } + else + { + /* Check predecessors. */ + check_seq (visited, &cfg_it); + /* Check successors. */ + check_seq (visited, &cfg_it); + } + } +}