From patchwork Sat Nov 9 19:43:25 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mariam Arutunian X-Patchwork-Id: 2009135 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=D0wnSYVE; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Xm5pw06XGz1xy0 for ; Sun, 10 Nov 2024 06:44:08 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 34BBF3858D29 for ; Sat, 9 Nov 2024 19:44:06 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-qv1-xf2d.google.com (mail-qv1-xf2d.google.com [IPv6:2607:f8b0:4864:20::f2d]) by sourceware.org (Postfix) with ESMTPS id 2DCCC3858D21 for ; Sat, 9 Nov 2024 19:43:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2DCCC3858D21 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 2DCCC3858D21 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::f2d ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731181424; cv=none; b=QoO3C2McT8JFkBLCmBWAAo0W0Au8OFLSz0VmOy3lMnmIUL79rQU3WYtHpe80tLjdN/czDJGqpyRExPFbpUW2Sqmfq2n5RC5zRxHar5F5MhaLqMFtxn/BP1vRP/lvYPPTNYWPA5AbpivvyqRu40G4aXPbo04JDwMCz4L0ood0CLs= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731181424; c=relaxed/simple; bh=sOI7iYNiF8KDD8BTv93IkQI4nN5yvm8ocdKAgHGVIu0=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=YDC9BpndnvjYNg0qYg2qbQNHFn29fbPjQ+F/L5nghmZuoqhYWu8VX2o5NIWJaKswRoFPqqq3ZjM+u+FYfqleYGV6FdG6Tj2YFVzmiFPdudtaDVNNoitMerlEktav3Ha8X+ptr6asFeCUP81tRyAmo96WIpo6U2BTXcbsYTk5Cd0= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-qv1-xf2d.google.com with SMTP id 6a1803df08f44-6cbce9e4598so19555296d6.2 for ; Sat, 09 Nov 2024 11:43:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731181418; x=1731786218; darn=gcc.gnu.org; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=cZZ2rCVq6pfXHPVQIHH9d4Y2wsMmtIzzQNSsT4VYFJY=; b=D0wnSYVEakSFbRD6DcHVH4pxDudDFhSa7IUpnmziyhhfFJCtwnv8293xsUct3Ior/r GrTHyFuz8xiRZZXfOEmU/7EXuveSPQTtwDzQie5NZ3iJxrEOi5ZCxmyTSVZ1hjPQMVJJ OV3IwGbn2zXejgqRE7hBM4vx9oit1r0U6ymm4BAUi7a2yH8HKYTrIgWt3BeH0wHG4u9T vxezd+Qcm5Tisht246jQxhJgwx9nU4jODHa4V48/JKKAseDhsoAUYIw+Kbu9aimHE4JS IVvJrOcRPXqSS4vGfm3tF/1UjjvpgcgYjMzzas6Ru/+Fq6EzRk3zlvqr7tuAyvdbmXBE ph2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731181418; x=1731786218; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=cZZ2rCVq6pfXHPVQIHH9d4Y2wsMmtIzzQNSsT4VYFJY=; b=YISa8Y4qC5veoBKQpV14M+RRvPMGFnl5eSdDLfiTm8I+h8ax0mt67S/WzpqbGWnIRK ZgZOdquCF41BJs5zLnPQ0lagl7bEtmrNfG2m3FNeWfL4bQcSP2bTfM/PnYrsgbgz84ln xdbj3rri637dnV9YD070nJU6Q1OXY9aTRKqZUP11g6MbbBqxalvzr9lOwCmK31Iit7ND ixov3KcwuIOj+WM6sBazP17pBfUati9D+NiHb07VRs9QPT+0X62qDgJe0era0fPi8TSV clj1xDazXUw4g+fS2DN42D9AtKEX78HNGsT6kWyoy4HWbIG+q7XpRshjeHH+bqDl7Fsg IjkQ== X-Gm-Message-State: AOJu0Yxe0hdcZ+ump8FyvIuJCBLo7BTdTsfSlRZZSwIpuHpyU2+7qDP2 mk5dd6mqRiEB5UbD/kXCKM5x3Xc9XXuFGRjoctSoV1t7V4ZOXVr2uzVBi0KKi/zISvSiqfq0y9V Jj+1tMmBHydLCF1O1DI5a9tMpBNYvtrrX X-Google-Smtp-Source: AGHT+IFLh+KB54OV2wZvoE5wVcI8D2xrZ8DT6gwXHjy8CSBjdaZgz60/hu8T8XMnZws1rAispdGj2WjtAtjhWR9anF8= X-Received: by 2002:a05:6214:320f:b0:6ce:26d0:c7af with SMTP id 6a1803df08f44-6d39e199927mr104034616d6.31.1731181418023; Sat, 09 Nov 2024 11:43:38 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Mariam Arutunian Date: Sat, 9 Nov 2024 23:43:25 +0400 Message-ID: Subject: [RFC/RFA] [PATCH v7 01/12] Implement internal functions for efficient CRC computation. To: GCC Patches , Jeff Law X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Add two new internal functions (IFN_CRC, IFN_CRC_REV), to provide faster CRC generation. One performs bit-forward and the other bit-reversed CRC computation. If CRC optabs are supported, they are used for the CRC computation. Otherwise, table-based CRC is generated. The supported data and CRC sizes are 8, 16, 32, and 64 bits. The polynomial is without the leading 1. A table with 256 elements is used to store precomputed CRCs. For the reflection of inputs and the output, a simple algorithm involving SHIFT, AND, and OR operations is used. gcc/ * doc/md.texi (crc@var{m}@var{n}4, crc_rev@var{m}@var{n}4): Document. * expr.cc (calculate_crc): New function. (assemble_crc_table): Likewise. (generate_crc_table): Likewise. (calculate_table_based_CRC): Likewise. (emit_crc): Likewise. (expand_crc_table_based): Likewise. (gen_common_operation_to_reflect): Likewise. (reflect_64_bit_value): Likewise. (reflect_32_bit_value): Likewise. (reflect_16_bit_value): Likewise. (reflect_8_bit_value): Likewise. (generate_reflecting_code_standard): Likewise. (expand_reversed_crc_table_based): Likewise. * expr.h (generate_reflecting_code_standard): New function declaration. (expand_crc_table_based): Likewise. (expand_reversed_crc_table_based): Likewise. * internal-fn.cc: (crc_direct): Define. (direct_crc_optab_supported_p): Likewise. (expand_crc_optab_fn): New function * internal-fn.def (CRC, CRC_REV): New internal functions. * optabs.def (crc_optab, crc_rev_optab): New optabs. Signed-off-by: Mariam Arutunian Co-authored-by: Joern Rennecke Mentored-by: Jeff Law --- gcc/doc/md.texi | 14 ++ gcc/expr.cc | 372 ++++++++++++++++++++++++++++++++++++++++++++ gcc/expr.h | 6 + gcc/internal-fn.cc | 54 +++++++ gcc/internal-fn.def | 2 + gcc/optabs.def | 2 + 6 files changed, 450 insertions(+) diff --git a/gcc/doc/md.texi b/gcc/doc/md.texi index a9259112251..913d1f96373 100644 --- a/gcc/doc/md.texi +++ b/gcc/doc/md.texi @@ -8591,6 +8591,20 @@ Return 1 if operand 1 is a normal floating point number and 0 otherwise. @var{m} is a scalar floating point mode. Operand 0 has mode @code{SImode}, and operand 1 has mode @var{m}. +@cindex @code{crc@var{m}@var{n}4} instruction pattern +@item @samp{crc@var{m}@var{n}4} +Calculate a bit-forward CRC using operands 1, 2 and 3, +then store the result in operand 0. +Operands 1 is the initial CRC, operands 2 is the data and operands 3 is the +polynomial without leading 1. +Operands 0, 1 and 3 have mode @var{n} and operand 2 has mode @var{m}, where +both modes are integers. The size of CRC to be calculated is determined by the +mode; for example, if @var{n} is 'hi', a CRC16 is calculated. + +@cindex @code{crc_rev@var{m}@var{n}4} instruction pattern +@item @samp{crc_rev@var{m}@var{n}4} +Similar to @samp{crc@var{m}@var{n}4}, but calculates a bit-reversed CRC. + @end table @end ifset diff --git a/gcc/expr.cc b/gcc/expr.cc index 7a471f20e79..94c608f782c 100644 --- a/gcc/expr.cc +++ b/gcc/expr.cc @@ -14124,3 +14124,375 @@ int_expr_size (const_tree exp) return tree_to_shwi (size); } + +/* Calculate CRC for the initial CRC and given POLYNOMIAL. + CRC_BITS is CRC size. */ + +static unsigned HOST_WIDE_INT +calculate_crc (unsigned HOST_WIDE_INT crc, + unsigned HOST_WIDE_INT polynomial, + unsigned short crc_bits) +{ + unsigned HOST_WIDE_INT msb = HOST_WIDE_INT_1U << (crc_bits - 1); + crc = crc << (crc_bits - 8); + for (short i = 8; i > 0; --i) + { + if (crc & msb) + crc = (crc << 1) ^ polynomial; + else + crc <<= 1; + } + /* Zero out bits in crc beyond the specified number of crc_bits. */ + if (crc_bits < sizeof (crc) * CHAR_BIT) + crc &= (HOST_WIDE_INT_1U << crc_bits) - 1; + return crc; +} + +/* Assemble CRC table with 256 elements for the given POLYNOM and CRC_BITS with + given ID. + ID is the identifier of the table, the name of the table is unique, + contains CRC size and the polynomial. + POLYNOM is the polynomial used to calculate the CRC table's elements. + CRC_BITS is the size of CRC, may be 8, 16, ... . */ + +rtx +assemble_crc_table (tree id, unsigned HOST_WIDE_INT polynom, + unsigned short crc_bits) +{ + unsigned table_el_n = 0x100; + tree ar = build_array_type (make_unsigned_type (crc_bits), + build_index_type (size_int (table_el_n - 1))); + tree decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, id, ar); + SET_DECL_ASSEMBLER_NAME (decl, id); + DECL_ARTIFICIAL (decl) = 1; + rtx tab = gen_rtx_SYMBOL_REF (Pmode, IDENTIFIER_POINTER (id)); + TREE_ASM_WRITTEN (decl) = 0; + + /* Initialize the table. */ + vec *initial_values; + vec_alloc (initial_values, table_el_n); + for (size_t i = 0; i < table_el_n; ++i) + { + unsigned HOST_WIDE_INT crc = calculate_crc (i, polynom, crc_bits); + tree element = build_int_cstu (make_unsigned_type (crc_bits), crc); + vec_safe_push (initial_values, element); + } + DECL_INITIAL (decl) = build_constructor_from_vec (ar, initial_values); + + TREE_READONLY (decl) = 1; + TREE_STATIC (decl) = 1; + + if (TREE_PUBLIC (id)) + { + TREE_PUBLIC (decl) = 1; + make_decl_one_only (decl, DECL_ASSEMBLER_NAME (decl)); + } + + mark_decl_referenced (decl); + varpool_node::finalize_decl (decl); + + return tab; +} + +/* Generate CRC lookup table by calculating CRC for all possible + 8-bit data values. The table is stored with a specific name in the read-only + static data section. + POLYNOM is the polynomial used to calculate the CRC table's elements. + CRC_BITS is the size of CRC, may be 8, 16, ... . */ + +rtx +generate_crc_table (unsigned HOST_WIDE_INT polynom, unsigned short crc_bits) +{ + gcc_assert (crc_bits <= 64); + + /* Buf size - 24 letters + 6 '_' + + 20 numbers (2 for crc bit size + 2 for 0x + 16 for 64-bit polynomial) + + 1 for \0. */ + char buf[51]; + sprintf (buf, "crc_table_for_crc_%u_polynomial_" HOST_WIDE_INT_PRINT_HEX, + crc_bits, polynom); + + tree id = maybe_get_identifier (buf); + if (id) + return gen_rtx_SYMBOL_REF (Pmode, IDENTIFIER_POINTER (id)); + + id = get_identifier (buf); + return assemble_crc_table (id, polynom, crc_bits); +} + +/* Generate table-based CRC code for the given CRC, INPUT_DATA and the + POLYNOMIAL (without leading 1). + + First, using POLYNOMIAL's value generates CRC table of 256 elements, + then generates the assembly for the following code, + where crc_bit_size and data_bit_size may be 8, 16, 32, 64, depending on CRC: + + for (int i = 0; i < data_bit_size / 8; i++) + crc = (crc << 8) ^ crc_table[(crc >> (crc_bit_size - 8)) + ^ (data >> (data_bit_size - (i + 1) * 8) + & 0xFF))]; + + So to take values from the table, we need 8-bit data. + If input data size is not 8, then first we extract upper 8 bits, + then the other 8 bits, and so on. */ + +void +calculate_table_based_CRC (rtx *crc, const rtx &input_data, + const rtx &polynomial, + machine_mode crc_mode, machine_mode data_mode) +{ + unsigned short crc_bit_size = GET_MODE_BITSIZE (crc_mode).to_constant (); + unsigned short data_size = GET_MODE_SIZE (data_mode).to_constant (); + + rtx tab = generate_crc_table (UINTVAL (polynomial), crc_bit_size); + + for (unsigned short i = 0; i < data_size; i++) + { + /* crc >> (crc_bit_size - 8). */ + rtx op1 = expand_shift (RSHIFT_EXPR, word_mode, *crc, crc_bit_size - 8, + NULL_RTX, 1); + + /* data >> (8 * (GET_MODE_SIZE (data_mode).to_constant () - i - 1)). */ + unsigned range_8 = 8 * (data_size - i - 1); + rtx data = expand_shift (RSHIFT_EXPR, word_mode, input_data, range_8, + NULL_RTX, 1); + + /* data >> (8 * (GET_MODE_SIZE (data_mode) + .to_constant () - i - 1)) & 0xFF. */ + rtx data_final = expand_and (word_mode, data, + gen_int_mode (255, data_mode), NULL_RTX); + + /* (crc >> (crc_bit_size - 8)) ^ data_8bit. */ + rtx in = expand_binop (Pmode, xor_optab, op1, data_final, + NULL_RTX, 1, OPTAB_WIDEN); + + /* ((crc >> (crc_bit_size - 8)) ^ data_8bit) & 0xFF. */ + rtx index = expand_and (Pmode, in, gen_int_mode (255, word_mode), + NULL_RTX); + int log_crc_size = exact_log2 (GET_MODE_SIZE (crc_mode).to_constant ()); + index = expand_shift (LSHIFT_EXPR, Pmode, index, + log_crc_size, NULL_RTX, 0); + + index = expand_binop (Pmode, add_optab, index, tab, NULL_RTX, + 0, OPTAB_DIRECT); + + /* crc_table[(crc >> (crc_bit_size - 8)) ^ data_8bit] */ + rtx tab_el = validize_mem (gen_rtx_MEM (crc_mode, index)); + + /* (crc << 8) if CRC is larger than 8, otherwise crc = 0. */ + rtx high = NULL_RTX; + if (crc_bit_size != 8) + { + high = expand_shift (LSHIFT_EXPR, word_mode, *crc, 8, NULL_RTX, 0); + if (crc_mode != word_mode) + { + rtx crc_mode_mask = gen_int_mode (GET_MODE_MASK (crc_mode), + word_mode); + high = expand_and (word_mode, high, crc_mode_mask, NULL_RTX); + } + } + else + high = gen_int_mode (0, word_mode); + + /* crc = (crc << 8) + ^ crc_table[(crc >> (crc_bit_size - 8)) ^ data_8bit]; */ + *crc = expand_binop (word_mode, xor_optab, tab_el, high, NULL_RTX, 1, + OPTAB_WIDEN); + } +} + +/* Converts and moves a CRC value to a target register. + + CRC_MODE is the mode (data type) of the CRC value. + CRC is the initial CRC value. + OP0 is the target register. */ + +void +emit_crc (machine_mode crc_mode, rtx* crc, rtx* op0) +{ + if (word_mode != crc_mode) + { + rtx tgt = simplify_gen_subreg (word_mode, *op0, crc_mode, 0); + rtx crc_low = gen_lowpart (crc_mode, *crc); + if (SUBREG_P (*op0) && SUBREG_PROMOTED_VAR_P (*op0)) + convert_move (tgt, crc_low, SUBREG_PROMOTED_SIGN (*op0)); + else + convert_move (tgt, crc_low, 0); + } + else + emit_move_insn (*op0, *crc); +} + +/* Generate table-based CRC code for the given CRC, INPUT_DATA and the + POLYNOMIAL (without leading 1). + + CRC is OP1, data is OP2 and the polynomial is OP3. + This must generate a CRC table and an assembly for the following code, + where crc_bit_size and data_bit_size may be 8, 16, 32, 64: + uint_crc_bit_size_t + crc_crc_bit_size (uint_crc_bit_size_t crc_init, + uint_data_bit_size_t data, size_t size) + { + uint_crc_bit_size_t crc = crc_init; + for (int i = 0; i < data_bit_size / 8; i++) + crc = (crc << 8) ^ crc_table[(crc >> (crc_bit_size - 8)) + ^ (data >> (data_bit_size - (i + 1) * 8) + & 0xFF))]; + return crc; + } */ + +void +expand_crc_table_based (rtx op0, rtx op1, rtx op2, rtx op3, + machine_mode data_mode) +{ + gcc_assert (!CONST_INT_P (op0)); + gcc_assert (CONST_INT_P (op3)); + machine_mode crc_mode = GET_MODE (op0); + rtx crc = gen_reg_rtx (word_mode); + convert_move (crc, op1, 0); + calculate_table_based_CRC (&crc, op2, op3, crc_mode, data_mode); + emit_crc (crc_mode, &crc, &op0); +} + +/* Generate the common operation for reflecting values: + *OP = (*OP & AND1_VALUE) << SHIFT_VAL | (*OP & AND2_VALUE) >> SHIFT_VAL; */ + +void +gen_common_operation_to_reflect (rtx *op, + unsigned HOST_WIDE_INT and1_value, + unsigned HOST_WIDE_INT and2_value, + unsigned shift_val) +{ + rtx op1 = expand_and (word_mode, *op, gen_int_mode (and1_value, word_mode), + NULL_RTX); + op1 = expand_shift (LSHIFT_EXPR, word_mode, op1, shift_val, op1, 0); + rtx op2 = expand_and (word_mode, *op, gen_int_mode (and2_value, word_mode), + NULL_RTX); + op2 = expand_shift (RSHIFT_EXPR, word_mode, op2, shift_val, op2, 1); + *op = expand_binop (word_mode, ior_optab, op1, op2, *op, 0, OPTAB_DIRECT); +} + +/* Reflect 64-bit value for the 64-bit target. */ + +void +reflect_64_bit_value (rtx *op) +{ + gen_common_operation_to_reflect (op, 0x00000000FFFFFFFF, + 0xFFFFFFFF00000000, 32); + gen_common_operation_to_reflect (op, 0x0000FFFF0000FFFF, + 0xFFFF0000FFFF0000, 16); + gen_common_operation_to_reflect (op, 0x00FF00FF00FF00FF, + 0xFF00FF00FF00FF00, 8); + gen_common_operation_to_reflect (op, 0x0F0F0F0F0F0F0F0F, + 0xF0F0F0F0F0F0F0F0, 4); + gen_common_operation_to_reflect (op, 0x3333333333333333, + 0xCCCCCCCCCCCCCCCC, 2); + gen_common_operation_to_reflect (op, 0x5555555555555555, + 0xAAAAAAAAAAAAAAAA, 1); +} + +/* Reflect 32-bit value for the 32-bit target. */ + +void +reflect_32_bit_value (rtx *op) +{ + gen_common_operation_to_reflect (op, 0x0000FFFF, 0xFFFF0000, 16); + gen_common_operation_to_reflect (op, 0x00FF00FF, 0xFF00FF00, 8); + gen_common_operation_to_reflect (op, 0x0F0F0F0F, 0xF0F0F0F0, 4); + gen_common_operation_to_reflect (op, 0x33333333, 0xCCCCCCCC, 2); + gen_common_operation_to_reflect (op, 0x55555555, 0xAAAAAAAA, 1); +} + +/* Reflect 16-bit value for the 16-bit target. */ + +void +reflect_16_bit_value (rtx *op) +{ + gen_common_operation_to_reflect (op, 0x00FF, 0xFF00, 8); + gen_common_operation_to_reflect (op, 0x0F0F, 0xF0F0, 4); + gen_common_operation_to_reflect (op, 0x3333, 0xCCCC, 2); + gen_common_operation_to_reflect (op, 0x5555, 0xAAAA, 1); +} + +/* Reflect 8-bit value for the 8-bit target. */ + +void +reflect_8_bit_value (rtx *op) +{ + gen_common_operation_to_reflect (op, 0x0F, 0xF0, 4); + gen_common_operation_to_reflect (op, 0x33, 0xCC, 2); + gen_common_operation_to_reflect (op, 0x55, 0xAA, 1); +} + +/* Generate instruction sequence + which reflects the value of the OP using shift, and, or operations. + OP's mode may be less than word_mode. To get the correct number, + after reflecting we shift right the value by SHIFT_VAL. + E.g. we have 1111 0001, after reflection (target 32-bit) we will get + 1000 1111 0000 0000, if we shift-out 16 bits, + we will get the desired one: 1000 1111. */ + +void +generate_reflecting_code_standard (rtx *op, int shift_val) +{ + gcc_assert (BITS_PER_WORD >= 8 && BITS_PER_WORD <= 64); + + if (BITS_PER_WORD == 64) + reflect_64_bit_value (op); + else if (BITS_PER_WORD == 32) + reflect_32_bit_value (op); + else if (BITS_PER_WORD == 16) + reflect_16_bit_value (op); + else + reflect_8_bit_value (op); + + *op = expand_shift (RSHIFT_EXPR, word_mode, *op, shift_val, *op, 1); +} + +/* Generate table-based reversed CRC code for the given CRC, INPUT_DATA and + the POLYNOMIAL (without leading 1). + + CRC is OP1, data is OP2 and the polynomial is OP3. + This must generate CRC table and assembly for the following code, + where crc_bit_size and data_bit_size may be 8, 16, 32, 64: + uint_crc_bit_size_t + crc_crc_bit_size (uint_crc_bit_size_t crc_init, + uint_data_bit_size_t data, size_t size) + { + reflect (crc_init) + uint_crc_bit_size_t crc = crc_init; + reflect (data); + for (int i = 0; i < data_bit_size / 8; i++) + crc = (crc << 8) ^ crc_table[(crc >> (crc_bit_size - 8)) + ^ (data >> (data_bit_size - (i + 1) * 8) & 0xFF))]; + reflect (crc); + return crc; + } */ + +void +expand_reversed_crc_table_based (rtx op0, rtx op1, rtx op2, rtx op3, + machine_mode data_mode, + void (*gen_reflecting_code) (rtx *op, + int shift_val)) +{ + gcc_assert (!CONST_INT_P (op0)); + gcc_assert (CONST_INT_P (op3)); + machine_mode crc_mode = GET_MODE (op0); + + unsigned short crc_bit_size = GET_MODE_BITSIZE (crc_mode).to_constant (); + unsigned short data_bit_size = GET_MODE_BITSIZE (data_mode).to_constant (); + unsigned short word_size = GET_MODE_BITSIZE (word_mode); + + rtx crc = gen_reg_rtx (word_mode); + convert_move (crc, op1, 0); + gen_reflecting_code (&crc, word_size - crc_bit_size); + + rtx data = gen_reg_rtx (word_mode); + convert_move (data, op2, 0); + gen_reflecting_code (&data, word_size - data_bit_size); + + calculate_table_based_CRC (&crc, data, op3, crc_mode, data_mode); + + gen_reflecting_code (&crc, word_size - crc_bit_size); + emit_crc (crc_mode, &crc, &op0); +} diff --git a/gcc/expr.h b/gcc/expr.h index 04782b15f19..9373c7913a2 100644 --- a/gcc/expr.h +++ b/gcc/expr.h @@ -377,4 +377,10 @@ extern rtx expr_size (tree); extern bool mem_ref_refers_to_non_mem_p (tree); extern bool non_mem_decl_p (tree); +/* Generate table-based CRC. */ +extern void generate_reflecting_code_standard (rtx *, int); +extern void expand_crc_table_based (rtx, rtx, rtx, rtx, machine_mode); +extern void expand_reversed_crc_table_based (rtx, rtx, rtx, rtx, machine_mode, + void (*) (rtx *, int)); + #endif /* GCC_EXPR_H */ diff --git a/gcc/internal-fn.cc b/gcc/internal-fn.cc index 4e33db365ac..d59a9243cf9 100644 --- a/gcc/internal-fn.cc +++ b/gcc/internal-fn.cc @@ -189,6 +189,7 @@ init_internal_fns () #define mask_fold_left_direct { 1, 1, false } #define mask_len_fold_left_direct { 1, 1, false } #define check_ptrs_direct { 0, 0, false } +#define crc_direct { 1, -1, true } const direct_internal_fn_info direct_internal_fn_array[IFN_LAST + 1] = { #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) not_direct, @@ -3961,6 +3962,58 @@ expand_convert_optab_fn (internal_fn fn, gcall *stmt, convert_optab optab, expand_fn_using_insn (stmt, icode, 1, nargs); } +/* Expand CRC call STMT. */ + +static void +expand_crc_optab_fn (internal_fn fn, gcall *stmt, convert_optab optab) +{ + tree lhs = gimple_call_lhs (stmt); + tree rhs1 = gimple_call_arg (stmt, 0); // crc + tree rhs2 = gimple_call_arg (stmt, 1); // data + tree rhs3 = gimple_call_arg (stmt, 2); // polynomial + + tree result_type = TREE_TYPE (lhs); + tree data_type = TREE_TYPE (rhs2); + + gcc_assert (TYPE_MODE (result_type) >= TYPE_MODE (data_type)); + gcc_assert (word_mode >= TYPE_MODE (result_type)); + + rtx dest = expand_expr (lhs, NULL_RTX, VOIDmode, EXPAND_WRITE); + rtx crc = expand_normal (rhs1); + rtx data = expand_normal (rhs2); + gcc_assert (TREE_CODE (rhs3) == INTEGER_CST); + rtx polynomial = gen_rtx_CONST_INT (TYPE_MODE (result_type), + TREE_INT_CST_LOW (rhs3)); + + /* Use target specific expansion if it exists. + Otherwise, generate table-based CRC. */ + if (direct_internal_fn_supported_p (fn, tree_pair (data_type, result_type), + OPTIMIZE_FOR_SPEED)) + { + class expand_operand ops[4]; + create_call_lhs_operand (&ops[0], dest, TYPE_MODE (result_type)); + create_input_operand (&ops[1], crc, TYPE_MODE (result_type)); + create_input_operand (&ops[2], data, TYPE_MODE (data_type)); + create_input_operand (&ops[3], polynomial, TYPE_MODE (result_type)); + insn_code icode = convert_optab_handler (optab, TYPE_MODE (data_type), + TYPE_MODE (result_type)); + expand_insn (icode, 4, ops); + assign_call_lhs (lhs, dest, &ops[0]); + } + else + { + /* If it's IFN_CRC generate bit-forward CRC. */ + if (fn == IFN_CRC) + expand_crc_table_based (dest, crc, data, polynomial, + TYPE_MODE (data_type)); + else + /* If it's IFN_CRC_REV generate bit-reversed CRC. */ + expand_reversed_crc_table_based (dest, crc, data, polynomial, + TYPE_MODE (data_type), + generate_reflecting_code_standard); + } +} + /* Expanders for optabs that can use expand_direct_optab_fn. */ #define expand_unary_optab_fn(FN, STMT, OPTAB) \ @@ -4097,6 +4150,7 @@ multi_vector_optab_supported_p (convert_optab optab, tree_pair types, #define direct_cond_len_unary_optab_supported_p direct_optab_supported_p #define direct_cond_len_binary_optab_supported_p direct_optab_supported_p #define direct_cond_len_ternary_optab_supported_p direct_optab_supported_p +#define direct_crc_optab_supported_p convert_optab_supported_p #define direct_mask_load_optab_supported_p convert_optab_supported_p #define direct_load_lanes_optab_supported_p multi_vector_optab_supported_p #define direct_mask_load_lanes_optab_supported_p multi_vector_optab_supported_p diff --git a/gcc/internal-fn.def b/gcc/internal-fn.def index 23b4ab02b30..5749a1d2cab 100644 --- a/gcc/internal-fn.def +++ b/gcc/internal-fn.def @@ -200,6 +200,8 @@ along with GCC; see the file COPYING3. If not see cond_len_##UNSIGNED_OPTAB, cond_len_##TYPE) #endif +DEF_INTERNAL_OPTAB_FN (CRC, ECF_CONST | ECF_NOTHROW, crc, crc) +DEF_INTERNAL_OPTAB_FN (CRC_REV, ECF_CONST | ECF_NOTHROW, crc_rev, crc) DEF_INTERNAL_OPTAB_FN (MASK_LOAD, ECF_PURE, maskload, mask_load) DEF_INTERNAL_OPTAB_FN (LOAD_LANES, ECF_CONST, vec_load_lanes, load_lanes) DEF_INTERNAL_OPTAB_FN (MASK_LOAD_LANES, ECF_PURE, diff --git a/gcc/optabs.def b/gcc/optabs.def index 58a939442bd..9b5b1673ccb 100644 --- a/gcc/optabs.def +++ b/gcc/optabs.def @@ -85,6 +85,8 @@ OPTAB_CD(smsub_widen_optab, "msub$b$a4") OPTAB_CD(umsub_widen_optab, "umsub$b$a4") OPTAB_CD(ssmsub_widen_optab, "ssmsub$b$a4") OPTAB_CD(usmsub_widen_optab, "usmsub$a$b4") +OPTAB_CD(crc_optab, "crc$a$b4") +OPTAB_CD(crc_rev_optab, "crc_rev$a$b4") OPTAB_CD(vec_load_lanes_optab, "vec_load_lanes$a$b") OPTAB_CD(vec_store_lanes_optab, "vec_store_lanes$a$b") OPTAB_CD(vec_mask_load_lanes_optab, "vec_mask_load_lanes$a$b") -- 2.25.1 From patchwork Sat Nov 9 19:44:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mariam Arutunian X-Patchwork-Id: 2009138 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=JqPU+jjV; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Xm5wF5lYzz1xyp for ; Sun, 10 Nov 2024 06:48:45 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E37213858C33 for ; Sat, 9 Nov 2024 19:48:43 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-qv1-xf33.google.com (mail-qv1-xf33.google.com [IPv6:2607:f8b0:4864:20::f33]) by sourceware.org (Postfix) with ESMTPS id EA89E3858288 for ; Sat, 9 Nov 2024 19:44:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org EA89E3858288 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org EA89E3858288 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::f33 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731181479; cv=none; b=wMpDEj2LNMfVxzCMvPJ60rMdFYz4TaHWg87AQeMjeeAIApPp/8sBjT7mQczrRK86L1GkJronAD/2qYLitYO+EqrJXYyT7Rwmu4NZ24HoH8RHRht3pKEGhrv9ppFrCZ3B3FQ4STyM8X2LkAGl97X0KYbN3pqUY5OWxMTa3I8tzyY= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731181479; c=relaxed/simple; bh=8yIxfyqyGMcgPrSwqSk7jLj1Dz3ASaOHVlOf8MgZG6I=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=c2N1ajg5ycbvIZ8ZPp5/DDcUXTSjfXPBKZMviVeaKCjEAX7f0MCI0fCmRg9pnYRcfjKOB4G4xAqCV8GO78Gr5rSqScaJA2GYPvPhTXL5cBL0zu9RJNBcF/Oznz1I+fyfPmtqFXrpJSpbAZMsiWQP7hnbE/JTJKCtjct1AyV90Lg= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-qv1-xf33.google.com with SMTP id 6a1803df08f44-6cbe68f787dso21142546d6.2 for ; Sat, 09 Nov 2024 11:44:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731181470; x=1731786270; darn=gcc.gnu.org; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=P4l8eLRty3YFdpgQ+gtN/410zGUs1cH6Qb2nXkHpaOo=; b=JqPU+jjVGrPX3DZNmuEuZANg3/LCAKUTSk6nDMLN/bbfHlZJqSOiJTUa/wzvCD2J/q HPVyEjslKrNJmXGfUrOCmCWiz9bSMTh8VywheU7fZBjroM3jLjjjEheEtVw8gnV23LbT pCHBuSmLkSqN0OwAoFnLNakqOhVh/N8s4PRVKwKLAwAxAefbZhTJdX3PkxBg5WUklKUt arCanGur7wIaTpBYWxnWPc7liQNjUaRPHn9hzWwkxYWwIogH4FHunNkJ8vNDdrEt7u92 5EPfazOC4kk/ZDFXEELwxnQ6EIMXeZuvoB3FJWXSn6ROofJunHkKN16CL0YXdfg5qVfQ 0IHA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731181470; x=1731786270; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=P4l8eLRty3YFdpgQ+gtN/410zGUs1cH6Qb2nXkHpaOo=; b=VginU38lfVri1aMfq6rnFL2k9+V37+Jzsx49+VEB7nCZAMFzJjXZ3C12dbPTEonc7Q dEc2gKWTu02/kzdmTqQ035y19ZAMVG8xHva+zzFBIXGEq5a7KxsqfTIJWmYeJ+K6ujig TQUMo2OdN4k7tWsutFxrl8bcmpHMZcJGLPGfEoksoHti+iDZOtRjjNT0SYF8GpEDdHna pHiEHE67yDwB9uCXcRGifQZktNHmEavdl+FWdSu9i7G51mZYKNggZyllWCnflOIh0gvp yQDSDqi1w/7z1L6r7pENUwQAbbGfCqR1SqoWHfoNIFDOCtf/7O4Vu/h2u5mUC+eMIDdE +npA== X-Gm-Message-State: AOJu0Yx4fg7cpCUhPOjKVm878d6LpQbdPDwmBY6apnFMA8cndLHOkKdj 7Hl4fSV/gaAOHzPy6R/BB69/9zU/p66V/8/kpL5OBvCloFnrp4Ca6Qi+x/n6h4dQyg+U12+xRNM ARtCJri/AICUHLCsfpWCGv9+94yjGkUOBuRk= X-Google-Smtp-Source: AGHT+IEl6iJGLHZHSMQ0G5WGYqnO8aadJdpnibN01xq+nAXMJr0acmZLZ+BQEbAfb9+G9rAuhj0eAuVd05HipsvBXSQ= X-Received: by 2002:a05:6214:5bc5:b0:6cb:be8f:a6b1 with SMTP id 6a1803df08f44-6d39e1506demr95187976d6.25.1731181469965; Sat, 09 Nov 2024 11:44:29 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Mariam Arutunian Date: Sat, 9 Nov 2024 23:44:17 +0400 Message-ID: Subject: [RFC/RFA][PATCH v7 06/12] aarch64: Implement new expander for efficient CRC computation. To: GCC Patches , Jeff Law X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org This patch introduces two new expanders for the aarch64 backend, dedicated to generate optimized code for CRC computations. The new expanders are designed to leverage specific hardware capabilities to achieve faster CRC calculations, particularly using the crc32, crc32c and pmull instructions when supported by the target architecture. Expander 1: Bit-Forward CRC (crc4) For targets that support pmul instruction (TARGET_AES), the expander will generate code that uses the pmull (crypto_pmulldi) instruction for CRC computation. Expander 2: Bit-Reversed CRC (crc_rev4) The expander first checks if the target supports the CRC32* instruction set (TARGET_CRC32) and the polynomial in use is 0x1EDC6F41 (iSCSI) or 0x04C11DB7 (HDLC). If the conditions are met, it emits calls to the corresponding crc32* instruction (depending on the data size and the polynomial). If the target does not support crc32* but supports pmull, it then uses the pmull (crypto_pmulldi) instruction for bit-reversed CRC computation. Otherwise table-based CRC is generated. gcc/config/aarch64/ * aarch64-protos.h (aarch64_expand_crc_using_pmull): New extern function declaration. (aarch64_expand_reversed_crc_using_pmull): Likewise. * aarch64-simd.md (aarch64_get_lane): Rename to @aarch64_get_lane. * aarch64.cc (aarch64_expand_crc_using_pmull): New function. (aarch64_expand_reversed_crc_using_pmull): Likewise. * aarch64.md (crc_rev4): New expander for reversed CRC. (crc4): New expander for bit-forward CRC. * iterators.md (crc_data_type): New mode attribute. gcc/testsuite/gcc.target/aarch64/ * crc-1-pmul.c: New test. * crc-10-pmul.c: Likewise. * crc-12-pmul.c: Likewise. * crc-13-pmul.c: Likewise. * crc-14-pmul.c: Likewise. * crc-17-pmul.c: Likewise. * crc-18-pmul.c: Likewise. * crc-21-pmul.c: Likewise. * crc-22-pmul.c: Likewise. * crc-23-pmul.c: Likewise. * crc-4-pmul.c: Likewise. * crc-5-pmul.c: Likewise. * crc-6-pmul.c: Likewise. * crc-7-pmul.c: Likewise. * crc-8-pmul.c: Likewise. * crc-9-pmul.c: Likewise. * crc-CCIT-data16-pmul.c: Likewise. * crc-CCIT-data8-pmul.c: Likewise. * crc-coremark-16bitdata-pmul.c: Likewise. * crc-crc32-data16.c: Likewise. * crc-crc32-data32.c: Likewise. * crc-crc32-data8.c: Likewise. * crc-crc32c-data16.c: Likewise. * crc-crc32c-data32.c: Likewise. * crc-crc32c-data8.c: Likewise. Signed-off-by: Mariam Arutunian Co-authored-by: Richard Sandiford --- gcc/config/aarch64/aarch64-protos.h | 3 + gcc/config/aarch64/aarch64-simd.md | 2 +- gcc/config/aarch64/aarch64.cc | 131 ++++++++++++++++++ gcc/config/aarch64/aarch64.md | 57 ++++++++ gcc/config/aarch64/iterators.md | 4 + gcc/testsuite/gcc.target/aarch64/crc-1-pmul.c | 8 ++ .../gcc.target/aarch64/crc-10-pmul.c | 8 ++ .../gcc.target/aarch64/crc-12-pmul.c | 9 ++ .../gcc.target/aarch64/crc-13-pmul.c | 8 ++ .../gcc.target/aarch64/crc-14-pmul.c | 8 ++ .../gcc.target/aarch64/crc-17-pmul.c | 8 ++ .../gcc.target/aarch64/crc-18-pmul.c | 8 ++ .../gcc.target/aarch64/crc-21-pmul.c | 8 ++ .../gcc.target/aarch64/crc-22-pmul.c | 8 ++ .../gcc.target/aarch64/crc-23-pmul.c | 8 ++ gcc/testsuite/gcc.target/aarch64/crc-4-pmul.c | 8 ++ gcc/testsuite/gcc.target/aarch64/crc-5-pmul.c | 8 ++ gcc/testsuite/gcc.target/aarch64/crc-6-pmul.c | 8 ++ gcc/testsuite/gcc.target/aarch64/crc-7-pmul.c | 8 ++ gcc/testsuite/gcc.target/aarch64/crc-8-pmul.c | 8 ++ gcc/testsuite/gcc.target/aarch64/crc-9-pmul.c | 8 ++ .../gcc.target/aarch64/crc-CCIT-data16-pmul.c | 9 ++ .../gcc.target/aarch64/crc-CCIT-data8-pmul.c | 9 ++ .../aarch64/crc-coremark-16bitdata-pmul.c | 9 ++ .../gcc.target/aarch64/crc-crc32-data16.c | 53 +++++++ .../gcc.target/aarch64/crc-crc32-data32.c | 52 +++++++ .../gcc.target/aarch64/crc-crc32-data8.c | 53 +++++++ .../gcc.target/aarch64/crc-crc32c-data16.c | 53 +++++++ .../gcc.target/aarch64/crc-crc32c-data32.c | 52 +++++++ .../gcc.target/aarch64/crc-crc32c-data8.c | 53 +++++++ 30 files changed, 668 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-1-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-10-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-12-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-13-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-14-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-17-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-18-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-21-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-22-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-23-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-4-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-5-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-6-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-7-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-8-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-9-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-CCIT-data16-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-CCIT-data8-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-coremark-16bitdata-pmul.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-crc32-data16.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-crc32-data32.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-crc32-data8.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-crc32c-data16.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-crc32c-data32.c create mode 100644 gcc/testsuite/gcc.target/aarch64/crc-crc32c-data8.c diff --git a/gcc/config/aarch64/aarch64-protos.h b/gcc/config/aarch64/aarch64-protos.h index d03c1fe798b..7c157073cc6 100644 --- a/gcc/config/aarch64/aarch64-protos.h +++ b/gcc/config/aarch64/aarch64-protos.h @@ -1124,5 +1124,8 @@ extern void aarch64_adjust_reg_alloc_order (); bool aarch64_optimize_mode_switching (aarch64_mode_entity); void aarch64_restore_za (rtx); +void aarch64_expand_crc_using_pmull (scalar_mode, scalar_mode, rtx *); +void aarch64_expand_reversed_crc_using_pmull (scalar_mode, scalar_mode, rtx *); + #endif /* GCC_AARCH64_PROTOS_H */ diff --git a/gcc/config/aarch64/aarch64-simd.md b/gcc/config/aarch64/aarch64-simd.md index 23c03a96371..eb5591a7bd1 100644 --- a/gcc/config/aarch64/aarch64-simd.md +++ b/gcc/config/aarch64/aarch64-simd.md @@ -4312,7 +4312,7 @@ ;; RTL uses GCC vector extension indices throughout so flip only for assembly. ;; Extracting lane zero is split into a simple move when it is between SIMD ;; registers or a store. -(define_insn_and_split "aarch64_get_lane" +(define_insn_and_split "@aarch64_get_lane" [(set (match_operand: 0 "aarch64_simd_nonimmediate_operand" "=?r, w, Utv") (vec_select: (match_operand:VALL_F16 1 "register_operand" "w, w, w") diff --git a/gcc/config/aarch64/aarch64.cc b/gcc/config/aarch64/aarch64.cc index 6a3f1a23a9f..1cc549c5023 100644 --- a/gcc/config/aarch64/aarch64.cc +++ b/gcc/config/aarch64/aarch64.cc @@ -30386,6 +30386,137 @@ aarch64_retrieve_sysreg (const char *regname, bool write_p, bool is128op) return sysreg->encoding; } +/* Generate assembly to calculate CRC + using carry-less multiplication instruction. + OPERANDS[1] is input CRC, + OPERANDS[2] is data (message), + OPERANDS[3] is the polynomial without the leading 1. */ + +void +aarch64_expand_crc_using_pmull (scalar_mode crc_mode, + scalar_mode data_mode, + rtx *operands) +{ + /* Check and keep arguments. */ + gcc_assert (!CONST_INT_P (operands[0])); + gcc_assert (CONST_INT_P (operands[3])); + rtx crc = operands[1]; + rtx data = operands[2]; + rtx polynomial = operands[3]; + + unsigned HOST_WIDE_INT crc_size = GET_MODE_BITSIZE (crc_mode); + unsigned HOST_WIDE_INT data_size = GET_MODE_BITSIZE (data_mode); + gcc_assert (crc_size <= 32); + gcc_assert (data_size <= crc_size); + + /* Calculate the quotient. */ + unsigned HOST_WIDE_INT + q = gf2n_poly_long_div_quotient (UINTVAL (polynomial), crc_size); + /* CRC calculation's main part. */ + if (crc_size > data_size) + crc = expand_shift (RSHIFT_EXPR, DImode, crc, crc_size - data_size, + NULL_RTX, 1); + + rtx t0 = force_reg (DImode, gen_int_mode (q, DImode)); + polynomial = simplify_gen_unary (ZERO_EXTEND, DImode, polynomial, + GET_MODE (polynomial)); + rtx t1 = force_reg (DImode, polynomial); + + rtx a0 = expand_binop (DImode, xor_optab, crc, data, NULL_RTX, 1, + OPTAB_WIDEN); + + rtx pmull_res = gen_reg_rtx (TImode); + emit_insn (gen_aarch64_crypto_pmulldi (pmull_res, a0, t0)); + a0 = gen_lowpart (DImode, pmull_res); + + a0 = expand_shift (RSHIFT_EXPR, DImode, a0, crc_size, NULL_RTX, 1); + + emit_insn (gen_aarch64_crypto_pmulldi (pmull_res, a0, t1)); + a0 = gen_lowpart (DImode, pmull_res); + + if (crc_size > data_size) + { + rtx crc_part = expand_shift (LSHIFT_EXPR, DImode, operands[1], data_size, + NULL_RTX, 0); + a0 = expand_binop (DImode, xor_optab, a0, crc_part, NULL_RTX, 1, + OPTAB_DIRECT); + } + + aarch64_emit_move (operands[0], gen_lowpart (crc_mode, a0)); +} + +/* Generate assembly to calculate reversed CRC + using carry-less multiplication instruction. + OPERANDS[1] is input CRC, + OPERANDS[2] is data, + OPERANDS[3] is the polynomial without the leading 1. */ + +void +aarch64_expand_reversed_crc_using_pmull (scalar_mode crc_mode, + scalar_mode data_mode, + rtx *operands) +{ + /* Check and keep arguments. */ + gcc_assert (!CONST_INT_P (operands[0])); + gcc_assert (CONST_INT_P (operands[3])); + rtx crc = operands[1]; + rtx data = operands[2]; + rtx polynomial = operands[3]; + + unsigned HOST_WIDE_INT crc_size = GET_MODE_BITSIZE (crc_mode); + unsigned HOST_WIDE_INT data_size = GET_MODE_BITSIZE (data_mode); + gcc_assert (crc_size <= 32); + gcc_assert (data_size <= crc_size); + + /* Calculate the quotient. */ + unsigned HOST_WIDE_INT + q = gf2n_poly_long_div_quotient (UINTVAL (polynomial), crc_size); + /* Reflect the calculated quotient. */ + q = reflect_hwi (q, crc_size + 1); + rtx t0 = force_reg (DImode, gen_int_mode (q, DImode)); + + /* Reflect the polynomial. */ + unsigned HOST_WIDE_INT ref_polynomial = reflect_hwi (UINTVAL (polynomial), + crc_size); + /* An unshifted multiplier would require the final result to be extracted + using a shift right by DATA_SIZE - 1 bits. Shift the multiplier left + so that the shift right can be by CRC_SIZE bits instead. */ + ref_polynomial <<= crc_size - data_size + 1; + rtx t1 = force_reg (DImode, gen_int_mode (ref_polynomial, DImode)); + + /* CRC calculation's main part. */ + rtx a0 = expand_binop (DImode, xor_optab, crc, data, NULL_RTX, 1, + OPTAB_WIDEN); + + /* Perform carry-less multiplication and get low part. */ + rtx pmull_res = gen_reg_rtx (TImode); + emit_insn (gen_aarch64_crypto_pmulldi (pmull_res, a0, t0)); + a0 = gen_lowpart (DImode, pmull_res); + + a0 = expand_binop (DImode, and_optab, a0, + gen_int_mode (GET_MODE_MASK (data_mode), DImode), + NULL_RTX, 1, OPTAB_WIDEN); + + /* Perform carry-less multiplication. */ + emit_insn (gen_aarch64_crypto_pmulldi (pmull_res, a0, t1)); + + /* Perform a shift right by CRC_SIZE as an extraction of lane 1. */ + machine_mode crc_vmode = aarch64_vq_mode (crc_mode).require (); + a0 = (crc_size > data_size ? gen_reg_rtx (crc_mode) : operands[0]); + emit_insn (gen_aarch64_get_lane (crc_vmode, a0, + gen_lowpart (crc_vmode, pmull_res), + aarch64_endian_lane_rtx (crc_vmode, 1))); + + if (crc_size > data_size) + { + rtx crc_part = expand_shift (RSHIFT_EXPR, crc_mode, crc, data_size, + NULL_RTX, 1); + a0 = expand_binop (crc_mode, xor_optab, a0, crc_part, operands[0], 1, + OPTAB_WIDEN); + aarch64_emit_move (operands[0], a0); + } +} + /* Target-specific selftests. */ #if CHECKING_P diff --git a/gcc/config/aarch64/aarch64.md b/gcc/config/aarch64/aarch64.md index c54b29cd64b..d390d45f77f 100644 --- a/gcc/config/aarch64/aarch64.md +++ b/gcc/config/aarch64/aarch64.md @@ -4566,6 +4566,63 @@ [(set_attr "type" "crc")] ) +;; Reversed CRC +(define_expand "crc_rev4" + [;; return value (calculated CRC) + (match_operand:ALLX 0 "register_operand" "=r") + ;; initial CRC + (match_operand:ALLX 1 "register_operand" "r") + ;; data + (match_operand:ALLI 2 "register_operand" "r") + ;; polynomial without leading 1 + (match_operand:ALLX 3)] + "" + { + /* If the polynomial is the same as the polynomial of crc32c* instruction, + put that instruction. crc32c uses iSCSI polynomial. */ + if (TARGET_CRC32 && INTVAL (operands[3]) == 0x1EDC6F41 + && mode == SImode) + emit_insn (gen_aarch64_crc32c (operands[0], + operands[1], + operands[2])); + /* If the polynomial is the same as the polynomial of crc32* instruction, + put that instruction. crc32 uses HDLC etc. polynomial. */ + else if (TARGET_CRC32 && INTVAL (operands[3]) == 0x04C11DB7 + && mode == SImode) + emit_insn (gen_aarch64_crc32 (operands[0], + operands[1], + operands[2])); + else if (TARGET_AES && <= ) + aarch64_expand_reversed_crc_using_pmull (mode, + mode, + operands); + else + /* Otherwise, generate table-based CRC. */ + expand_reversed_crc_table_based (operands[0], operands[1], operands[2], + operands[3], mode, + generate_reflecting_code_standard); + DONE; + } +) + +;; Bit-forward CRC +(define_expand "crc4" + [;; return value (calculated CRC) + (match_operand:ALLX 0 "register_operand" "=r") + ;; initial CRC + (match_operand:ALLX 1 "register_operand" "r") + ;; data + (match_operand:ALLI 2 "register_operand" "r") + ;; polynomial without leading 1 + (match_operand:ALLX 3)] + "TARGET_AES && <= " + { + aarch64_expand_crc_using_pmull (mode, mode, + operands); + DONE; + } +) + (define_insn "*csinc2_insn" [(set (match_operand:GPI 0 "register_operand" "=r") (plus:GPI (match_operand 2 "aarch64_comparison_operation" "") diff --git a/gcc/config/aarch64/iterators.md b/gcc/config/aarch64/iterators.md index 20a318e023b..9c439c45dd3 100644 --- a/gcc/config/aarch64/iterators.md +++ b/gcc/config/aarch64/iterators.md @@ -1280,6 +1280,10 @@ ;; Map a mode to a specific constraint character. (define_mode_attr cmode [(QI "q") (HI "h") (SI "s") (DI "d")]) +;; Map a mode to a specific constraint character for calling +;; appropriate version of crc. +(define_mode_attr crc_data_type [(QI "b") (HI "h") (SI "w") (DI "x")]) + ;; Map modes to Usg and Usj constraints for SISD right shifts (define_mode_attr cmode_simd [(SI "g") (DI "j")]) diff --git a/gcc/testsuite/gcc.target/aarch64/crc-1-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-1-pmul.c new file mode 100644 index 00000000000..4043251dbd8 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-1-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc -fdisable-tree-phiopt2 -fdisable-tree-phiopt3" } */ + +#include "../../gcc.dg/torture/crc-1.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.target/aarch64/crc-10-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-10-pmul.c new file mode 100644 index 00000000000..0078eebe35c --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-10-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-10.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-12-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-12-pmul.c new file mode 100644 index 00000000000..16d901eeaef --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-12-pmul.c @@ -0,0 +1,9 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc -fdisable-tree-phiopt2 -fdisable-tree-phiopt3" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include "../../gcc.dg/torture/crc-12.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-13-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-13-pmul.c new file mode 100644 index 00000000000..bd8f32e6924 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-13-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-13.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-14-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-14-pmul.c new file mode 100644 index 00000000000..d35c1110c89 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-14-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-14.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-17-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-17-pmul.c new file mode 100644 index 00000000000..99b84c8dde0 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-17-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-17.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-18-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-18-pmul.c new file mode 100644 index 00000000000..888c99a7dd7 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-18-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-18.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-21-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-21-pmul.c new file mode 100644 index 00000000000..4b92deceaac --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-21-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-21.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-22-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-22-pmul.c new file mode 100644 index 00000000000..b42b8525b24 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-22-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-22.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-23-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-23-pmul.c new file mode 100644 index 00000000000..eb2efae0c41 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-23-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-23.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-4-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-4-pmul.c new file mode 100644 index 00000000000..c7d50017fe8 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-4-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-4.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-5-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-5-pmul.c new file mode 100644 index 00000000000..2a4b87cc5d6 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-5-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -w -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-5.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.target/aarch64/crc-6-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-6-pmul.c new file mode 100644 index 00000000000..84604af525a --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-6-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-6.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.target/aarch64/crc-7-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-7-pmul.c new file mode 100644 index 00000000000..e1263fca91d --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-7-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-7.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-8-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-8-pmul.c new file mode 100644 index 00000000000..141b474578b --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-8-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-8.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-9-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-9-pmul.c new file mode 100644 index 00000000000..2fdcd425a3b --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-9-pmul.c @@ -0,0 +1,8 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ + +#include "../../gcc.dg/torture/crc-9.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-CCIT-data16-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-CCIT-data16-pmul.c new file mode 100644 index 00000000000..21520474564 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-CCIT-data16-pmul.c @@ -0,0 +1,9 @@ +/* { dg-do run } */ +/* { dg-options "-w -march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include "../../gcc.dg/torture/crc-CCIT-data16.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.target/aarch64/crc-CCIT-data8-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-CCIT-data8-pmul.c new file mode 100644 index 00000000000..3dcc92320f3 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-CCIT-data8-pmul.c @@ -0,0 +1,9 @@ +/* { dg-do run } */ +/* { dg-options "-w -march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto" } } */ + +#include "../../gcc.dg/torture/crc-CCIT-data8.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.target/aarch64/crc-coremark-16bitdata-pmul.c b/gcc/testsuite/gcc.target/aarch64/crc-coremark-16bitdata-pmul.c new file mode 100644 index 00000000000..e5196aaafef --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-coremark-16bitdata-pmul.c @@ -0,0 +1,9 @@ +/* { dg-do run } */ +/* { dg-options "-w -march=armv8-a+crypto -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include "../../gcc.dg/torture/crc-coremark16-data16.c" + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "pmull" "dfinish"} } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.target/aarch64/crc-crc32-data16.c b/gcc/testsuite/gcc.target/aarch64/crc-crc32-data16.c new file mode 100644 index 00000000000..e82cb04fcc3 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-crc32-data16.c @@ -0,0 +1,53 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crc -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include +#include + +__attribute__ ((noinline,optimize(0))) +uint32_t _crc32_O0 (uint32_t crc, uint16_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 8; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0xEDB88320; + else + crc = (crc >> 1); + } + + return crc; +} + +uint32_t _crc32 (uint32_t crc, uint16_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 8; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0xEDB88320; + else + crc = (crc >> 1); + } + + return crc; +} + +int main () +{ + uint32_t crc = 0x0D800D80; + for (uint16_t i = 0; i < 0xffff; i++) + { + uint32_t res1 = _crc32_O0 (crc, i); + uint32_t res2 = _crc32 (crc, i); + if (res1 != res2) + abort (); + crc = res1; + } +} + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "UNSPEC_CRC32" "dfinish"} } */ +/* { dg-final { scan-rtl-dump-times "pmull" 0 "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-crc32-data32.c b/gcc/testsuite/gcc.target/aarch64/crc-crc32-data32.c new file mode 100644 index 00000000000..a7564a7e28a --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-crc32-data32.c @@ -0,0 +1,52 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crc -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include +#include +__attribute__ ((noinline,optimize(0))) +uint32_t _crc32_O0 (uint32_t crc, uint32_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 32; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0xEDB88320; + else + crc = (crc >> 1); + } + + return crc; +} + +uint32_t _crc32 (uint32_t crc, uint32_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 32; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0xEDB88320; + else + crc = (crc >> 1); + } + + return crc; +} + +int main () +{ + uint32_t crc = 0x0D800D80; + for (uint8_t i = 0; i < 0xff; i++) + { + uint32_t res1 = _crc32_O0 (crc, i); + uint32_t res2 = _crc32 (crc, i); + if (res1 != res2) + abort (); + crc = res1; + } +} + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "UNSPEC_CRC32" "dfinish"} } */ +/* { dg-final { scan-rtl-dump-times "pmull" 0 "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-crc32-data8.c b/gcc/testsuite/gcc.target/aarch64/crc-crc32-data8.c new file mode 100644 index 00000000000..c88cafadedc --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-crc32-data8.c @@ -0,0 +1,53 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crc -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include +#include + +__attribute__ ((noinline,optimize(0))) +uint32_t _crc32_O0 (uint32_t crc, uint8_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 8; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0xEDB88320; + else + crc = (crc >> 1); + } + + return crc; +} + +uint32_t _crc32 (uint32_t crc, uint8_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 8; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0xEDB88320; + else + crc = (crc >> 1); + } + + return crc; +} + +int main () +{ + uint32_t crc = 0x0D800D80; + for (uint8_t i = 0; i < 0xff; i++) + { + uint32_t res1 = _crc32_O0 (crc, i); + uint32_t res2 = _crc32 (crc, i); + if (res1 != res2) + abort (); + crc = res1; + } +} + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "UNSPEC_CRC32" "dfinish"} } */ +/* { dg-final { scan-rtl-dump-times "pmull" 0 "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data16.c b/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data16.c new file mode 100644 index 00000000000..d82e6252603 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data16.c @@ -0,0 +1,53 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crc -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include +#include + +__attribute__ ((noinline,optimize(0))) +uint32_t _crc32_O0 (uint32_t crc, uint16_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 8; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0x82F63B78; + else + crc = (crc >> 1); + } + + return crc; +} + +uint32_t _crc32 (uint32_t crc, uint16_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 8; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0x82F63B78; + else + crc = (crc >> 1); + } + + return crc; +} + +int main () +{ + uint32_t crc = 0x0D800D80; + for (uint16_t i = 0; i < 0xffff; i++) + { + uint32_t res1 = _crc32_O0 (crc, i); + uint32_t res2 = _crc32 (crc, i); + if (res1 != res2) + abort (); + crc = res1; + } +} + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "UNSPEC_CRC32C" "dfinish"} } */ +/* { dg-final { scan-rtl-dump-times "pmull" 0 "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data32.c b/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data32.c new file mode 100644 index 00000000000..7acb6fc239c --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data32.c @@ -0,0 +1,52 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crc -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include +#include +__attribute__ ((noinline,optimize(0))) +uint32_t _crc32_O0 (uint32_t crc, uint32_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 32; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0x82F63B78; + else + crc = (crc >> 1); + } + + return crc; +} + +uint32_t _crc32 (uint32_t crc, uint32_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 32; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0x82F63B78; + else + crc = (crc >> 1); + } + + return crc; +} + +int main () +{ + uint32_t crc = 0x0D800D80; + for (uint8_t i = 0; i < 0xff; i++) + { + uint32_t res1 = _crc32_O0 (crc, i); + uint32_t res2 = _crc32 (crc, i); + if (res1 != res2) + abort (); + crc = res1; + } +} + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "UNSPEC_CRC32C" "dfinish"} } */ +/* { dg-final { scan-rtl-dump-times "pmull" 0 "dfinish"} } */ diff --git a/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data8.c b/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data8.c new file mode 100644 index 00000000000..e8a8901e453 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/crc-crc32c-data8.c @@ -0,0 +1,53 @@ +/* { dg-do run } */ +/* { dg-options "-march=armv8-a+crc -O2 -fdump-rtl-dfinish -fdump-tree-crc" } */ +/* { dg-skip-if "" { *-*-* } { "-flto"} } */ + +#include +#include + +__attribute__ ((noinline,optimize(0))) +uint32_t _crc32_O0 (uint32_t crc, uint8_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 8; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0x82F63B78; + else + crc = (crc >> 1); + } + + return crc; +} + +uint32_t _crc32 (uint32_t crc, uint8_t data) { + int i; + crc = crc ^ data; + + for (i = 0; i < 8; i++) { + if (crc & 1) + crc = (crc >> 1) ^ 0x82F63B78; + else + crc = (crc >> 1); + } + + return crc; +} + +int main () +{ + uint32_t crc = 0x0D800D80; + for (uint8_t i = 0; i < 0xff; i++) + { + uint32_t res1 = _crc32_O0 (crc, i); + uint32_t res2 = _crc32 (crc, i); + if (res1 != res2) + abort (); + crc = res1; + } +} + +/* { dg-final { scan-tree-dump "calculates CRC!" "crc"} } */ +/* { dg-final { scan-tree-dump-times "Couldn't generate faster CRC code." 0 "crc"} } */ +/* { dg-final { scan-rtl-dump "UNSPEC_CRC32C" "dfinish"} } */ +/* { dg-final { scan-rtl-dump-times "pmull" 0 "dfinish"} } */ -- 2.25.1 From patchwork Sat Nov 9 19:44:48 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mariam Arutunian X-Patchwork-Id: 2009136 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=hX62lOSw; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Xm5rk4zGTz1xyp for ; Sun, 10 Nov 2024 06:45:42 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7ED943858431 for ; Sat, 9 Nov 2024 19:45:39 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-qv1-xf32.google.com (mail-qv1-xf32.google.com [IPv6:2607:f8b0:4864:20::f32]) by sourceware.org (Postfix) with ESMTPS id A479F3858C66 for ; Sat, 9 Nov 2024 19:45:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A479F3858C66 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org A479F3858C66 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::f32 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731181512; cv=none; b=hq9cGdLm82Gv7KLJq//6XhxkTWhOUektnMDcplaWFqF+tDtcqpm1Bm0EPggbXDqy3ostSAMjUt73NF/HCaJy17Yuk+/tCI2bm7RE63jd8bviW6dkOqQIvW2M8z1H47mLtsb0VAqMLb8jRiINJqvVyk7L/IRttXMLwPvofRYmjKs= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731181512; c=relaxed/simple; bh=nHdOvT3TCWtLnCXckhMdI+janZQW6b2pZmq53j99Zz0=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=QMxMS5OG/tbxck7lxzcjAPX4xMTOhgW5vtNue6WBViPyeAz9+Vr/Iz8JGAMRt2GgqaZqN/+u6SQkEEQ98ZmRPeX87FoKUk6M0o6kvhpdGa3bHBmOorl7T/w5o0LwHakQZS6BzfbiOH38fUO3rIM00GxVghfzvDmKPG7x1dH/9Es= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-qv1-xf32.google.com with SMTP id 6a1803df08f44-6d18cdab29dso20895446d6.0 for ; Sat, 09 Nov 2024 11:45:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731181503; x=1731786303; darn=gcc.gnu.org; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=pSDVK/dJ/CWe0v7nHAfVDndYOKE4mo916/mgw0RRGjk=; b=hX62lOSwFaONOxnGkOqJn4XqqoLOTKlCh2FWvw4i6WQtFaYIdx2MHkpWjFupwARzbi M/mFnyNb6BjQKl0lO6H+QmfVnJPMQomgVd+azmpSTlf190jvZJsRfx2LUH33w4+abRyK HXkGTv5MCqeCFHjsQ/UWTWFIElTPc2JCBNUMX/u8gxnA6aiCytjGs3KSQkHbNUJpBul0 ZIsOEJRKm5n1yrVPvCLjpQCUJxse8M3vbZ/1KYoY1gVte8bHVsXbJia3rnZqCUcX/Aql 01Siz3Z9JNBBjl/j7gTnRnDjjUi0moP7mJGBVsUEj9QDBXRTGK0RWZ7Zf7FokIR0L+ef y1zQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731181503; x=1731786303; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=pSDVK/dJ/CWe0v7nHAfVDndYOKE4mo916/mgw0RRGjk=; b=chPrQUy3XZ94eOXQTp0J1llMm20QG4MtDRNh2o3VStbs4u6l+yrJw2p6UdgYthAE7P 2ABXB9ZirNCe1LNN7kPA8b6fQzDCH3jTwNvQ6+VwRysjpmOUJs/xERKZR3NVeC3kVip3 nHs95l15kAAOXz3NC19USoReIGQllpvtplNw7gG/PGr+uVqwwrELQzXJKyvx2U50D3te 9WcjBkDbzmBlRMq0UqFMLwbiUect84z9HUx1jPT5whd2HstGrgPBSiWCq6RWV/+ReV95 a4Hlo/qafxph9cnzcA0EIgPkN56k1RdE88DFps068+MnRZ4jY3ofiqSfvQbST0ZEoDHc T7GQ== X-Gm-Message-State: AOJu0YzNusP6dRSAdDV3/qX1qUJo8TV3dDZVydA0J7fnUb99hnPrEUjL U9FVaUr8wChPUPxQW8ZhmeD/+74GEc451QIEFJBFKjKj7vaaC6qXAhN6cUMtAjsLYb1dtBHBCgc 41zA0SgPdW1dJgJYI7OgJqlP1+4giSQ1W X-Google-Smtp-Source: AGHT+IF4NUuU5Mnd0fUXJ7xhiQw5jCHmLkckd6HDdN7K8Qx1JEs6+PN6YrBhi+v0s1SX7SLv9gxT5pUEp+b7vSCE3vE= X-Received: by 2002:a05:6214:3d05:b0:6cc:42c:feb with SMTP id 6a1803df08f44-6d39e109443mr102987086d6.2.1731181501994; Sat, 09 Nov 2024 11:45:01 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Mariam Arutunian Date: Sat, 9 Nov 2024 23:44:48 +0400 Message-ID: Subject: [RFC/RFA] [PATCH v7 09/12] Add symbolic execution support. To: GCC Patches , Jeff Law X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Gives an opportunity to execute the code on bit level, assigning symbolic values to the variables which don't have initial values. Supports only CRC specific operations. Example: uint8_t crc; uint8_t pol = 1; crc = crc ^ pol; during symbolic execution crc's value will be: crc(8), crc(7), ... crc(1), crc(0) ^ 1 gcc/ * Makefile.in (OBJS): Add sym-exec/sym-exec-expression.o, sym-exec/sym-exec-state.o, sym-exec/sym-exec-condition.o. * configure (sym-exec): New subdir. gcc/sym-exec/ * sym-exec-condition.cc: New file. * sym-exec-condition.h: New file. * sym-exec-expression-is-a-helper.h: New file. * sym-exec-expression.cc: New file. * sym-exec-expression.h: New file. * sym-exec-state.cc: New file. * sym-exec-state.h: New file. Signed-off-by: Mariam Arutunian Author: Matevos Mehrabyan Co-authored-by: Mariam Arutunian Mentored-by: Jeff Law --- gcc/Makefile.in | 3 + gcc/configure | 2 +- gcc/sym-exec/sym-exec-condition.cc | 86 + gcc/sym-exec/sym-exec-condition.h | 63 + gcc/sym-exec/sym-exec-expr-is-a-helper.h | 287 +++ gcc/sym-exec/sym-exec-expression.cc | 490 +++++ gcc/sym-exec/sym-exec-expression.h | 332 ++++ gcc/sym-exec/sym-exec-state.cc | 2321 ++++++++++++++++++++++ gcc/sym-exec/sym-exec-state.h | 471 +++++ 9 files changed, 4054 insertions(+), 1 deletion(-) create mode 100644 gcc/sym-exec/sym-exec-condition.cc create mode 100644 gcc/sym-exec/sym-exec-condition.h create mode 100644 gcc/sym-exec/sym-exec-expr-is-a-helper.h create mode 100644 gcc/sym-exec/sym-exec-expression.cc create mode 100644 gcc/sym-exec/sym-exec-expression.h create mode 100644 gcc/sym-exec/sym-exec-state.cc create mode 100644 gcc/sym-exec/sym-exec-state.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index a7054eda9c5..6eab34d62bb 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1718,6 +1718,9 @@ OBJS = \ tree-logical-location.o \ tree-loop-distribution.o \ gimple-crc-optimization.o \ + sym-exec/sym-exec-expression.o \ + sym-exec/sym-exec-state.o \ + sym-exec/sym-exec-condition.o \ tree-nested.o \ tree-nrv.o \ tree-object-size.o \ diff --git a/gcc/configure b/gcc/configure index 3d301b6ecd3..c781f4c24b6 100755 --- a/gcc/configure +++ b/gcc/configure @@ -36232,7 +36232,7 @@ $as_echo "$as_me: executing $ac_file commands" >&6;} "depdir":C) $SHELL $ac_aux_dir/mkinstalldirs $DEPDIR ;; "gccdepdir":C) ${CONFIG_SHELL-/bin/sh} $ac_aux_dir/mkinstalldirs build/$DEPDIR - for lang in $subdirs c-family common analyzer text-art rtl-ssa + for lang in $subdirs c-family common analyzer text-art rtl-ssa sym-exec do ${CONFIG_SHELL-/bin/sh} $ac_aux_dir/mkinstalldirs $lang/$DEPDIR done ;; diff --git a/gcc/sym-exec/sym-exec-condition.cc b/gcc/sym-exec/sym-exec-condition.cc new file mode 100644 index 00000000000..fef03d04d55 --- /dev/null +++ b/gcc/sym-exec/sym-exec-condition.cc @@ -0,0 +1,86 @@ +/* Everything defined here is used for representing conditions for bits + and their status. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Matevos Mehrabyan + +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 "sym-exec-condition.h" + +/* Constructor where the first argument is the bit left to the condition sign, + the second argument is the bit right to the condition sign and the third + argument is the code of the condition. */ + +bit_condition::bit_condition (value_bit *left, value_bit *right, tree_code code) +{ + this->m_left = left; + this->m_right = right; + this->m_code = code; + m_type = BIT_CONDITION; +} + + +/* Copy constructor. */ + +bit_condition::bit_condition (const bit_condition &expr) +{ + bit_expression::copy (&expr); + m_code = expr.get_code (); +} + + +/* Returns the condition's code. */ + +tree_code +bit_condition::get_code () const +{ + return m_code; +} + + +/* Returns a copy of the condition. */ + +value_bit * +bit_condition::copy () const +{ + return new bit_condition (*this); +} + + +/* Prints the condition's sign. */ + +void +bit_condition::print_expr_sign () +{ + switch (m_code) + { + case GT_EXPR: + fprintf (dump_file, " > "); + break; + case LT_EXPR: + fprintf (dump_file, " < "); + break; + case EQ_EXPR: + fprintf (dump_file, " == "); + break; + case NE_EXPR: + fprintf (dump_file, " != "); + break; + default: + fprintf (dump_file, " ? "); + } +} \ No newline at end of file diff --git a/gcc/sym-exec/sym-exec-condition.h b/gcc/sym-exec/sym-exec-condition.h new file mode 100644 index 00000000000..ee5b8703f48 --- /dev/null +++ b/gcc/sym-exec/sym-exec-condition.h @@ -0,0 +1,63 @@ +/* Everything defined here is used for representing conditions for bits + and their status. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Matevos Mehrabyan + +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 +. */ + + +#ifndef SYM_EXEC_CONDITION_H +#define SYM_EXEC_CONDITION_H + +#include "sym-exec-expression.h" + +/* Enum representing condition status. */ + +enum condition_status { + CS_NO_COND, + CS_TRUE, + CS_FALSE, + CS_SYM +}; + +/* Class used for describing and storing condition for a single bit. */ + +class bit_condition : public bit_expression { + private: + /* Condition's code. */ + tree_code m_code; + + /* Prints the condition's sign. */ + void print_expr_sign (); + + public: + /* Constructor where the first argument is the bit left to the condition sign, + the second argument is the bit right to the condition sign and the third + argument is the code of the condition. */ + bit_condition (value_bit *left, value_bit *right, tree_code type); + + /* Copy constructor. */ + bit_condition (const bit_condition &expr); + + /* Returns the condition's code. */ + tree_code get_code () const; + + /* Returns a copy of the condition. */ + value_bit *copy () const; +}; + +#endif /* SYM_EXEC_CONDITION_H. */ \ No newline at end of file diff --git a/gcc/sym-exec/sym-exec-expr-is-a-helper.h b/gcc/sym-exec/sym-exec-expr-is-a-helper.h new file mode 100644 index 00000000000..1a262b47fad --- /dev/null +++ b/gcc/sym-exec/sym-exec-expr-is-a-helper.h @@ -0,0 +1,287 @@ +/* Defining test functions for value conversion via dyn_cast. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Matevos Mehrabyan + +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 +. */ + + +#ifndef SYM_EXEC_EXPRESSION_IS_A_HELPER_H +#define SYM_EXEC_EXPRESSION_IS_A_HELPER_H + +#include "sym-exec-condition.h" + +/* Test function used by dyn_cast checks if the value_bit is of + the value_type::SYMBOLIC_BIT type. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::SYMBOLIC_BIT; +} + + +/* Test function used by dyn_cast checks if the value_bit is of + the value_type::BIT type. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::BIT; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a bit_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + value_type type = ptr->get_type (); + return type == value_type::BIT_AND_EXPRESSION + || type == value_type::BIT_OR_EXPRESSION + || type == value_type::BIT_XOR_EXPRESSION + || type == value_type::BIT_COMPLEMENT_EXPRESSION + || type == value_type::SHIFT_RIGHT_EXPRESSION + || type == value_type::SHIFT_LEFT_EXPRESSION + || type == value_type::ADD_EXPRESSION + || type == value_type::SUB_EXPRESSION + || type == value_type::BIT_CONDITION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a bit_and_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::BIT_AND_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a bit_or_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::BIT_OR_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a bit_xor_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::BIT_XOR_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a bit_complement_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::BIT_COMPLEMENT_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a shift_left_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::SHIFT_LEFT_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a shift_right_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::SHIFT_RIGHT_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is an add_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::ADD_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a sub_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::SUB_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the value_bit + is a bit_condition. */ + +template<> +template<> +inline bool +is_a_helper::test (value_bit *ptr) +{ + return ptr->get_type () == value_type::BIT_CONDITION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a bit_and_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::BIT_AND_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a bit_or_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::BIT_OR_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a bit_xor_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::BIT_XOR_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a bit_complement_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::BIT_COMPLEMENT_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a shift_left_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::SHIFT_LEFT_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a shift_right_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::SHIFT_RIGHT_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a add_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::ADD_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a sub_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::SUB_EXPRESSION; +} + + +/* Test function used by dyn_cast checks if the bit_expression + is a bit_condition_expression. */ + +template<> +template<> +inline bool +is_a_helper::test (bit_expression *ptr) +{ + return ptr->get_type () == value_type::BIT_CONDITION; +} + +#endif /* SYM_EXEC_EXPRESSION_IS_A_HELPER_H. */ \ No newline at end of file diff --git a/gcc/sym-exec/sym-exec-expression.cc b/gcc/sym-exec/sym-exec-expression.cc new file mode 100644 index 00000000000..8abae6a993f --- /dev/null +++ b/gcc/sym-exec/sym-exec-expression.cc @@ -0,0 +1,490 @@ +/* Every class defined here represents a single bit value of a variable. + Every variable will be represented as a vector of these classes which later + will be used for bit-level symbolic execution. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Matevos Mehrabyan + +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 "sym-exec-expr-is-a-helper.h" + +/* Returns type of the bit. */ + +value_type +value_bit::get_type () const +{ + return m_type; +} + + +/* Constructor that sets the bit's initial position and its origin. */ + +symbolic_bit::symbolic_bit (size_t i, tree orig) + : value_bit (i), m_origin (orig) +{ + m_type = SYMBOLIC_BIT; +} + + +/* Constructor that sets m_val to the specified value. */ + +bit::bit (unsigned char i) : m_val (i) +{ + m_type = BIT; +} + + +/* Returns left operand of the expression. */ + +value_bit * +bit_expression::get_left () +{ + return m_left; +} + + +/* Returns right operand of the expression. */ + +value_bit * +bit_expression::get_right () +{ + return m_right; +} + + +/* Sets left operand of the expression. */ + +void +bit_expression::set_left (value_bit *expr) +{ + m_left = expr; +} + + +/* Sets right operand of the expression. */ + +void +bit_expression::set_right (value_bit *expr) +{ + m_right = expr; +} + + +/* Returns the bit's initial index in bit-vector. */ + +size_t +value_bit::get_index () const +{ + return m_index; +} + + +/* Returns the value of the bit. */ + +unsigned char +bit::get_val () const +{ + return m_val; +} + + +/* Sets the value of the bit. */ + +void +bit::set_val (unsigned char new_val) +{ + m_val = new_val; +} + + +/* Constructor that sets the left and right side bits + of the bit_complement_expression sign. */ + +bit_complement_expression::bit_complement_expression (value_bit *right) +{ + /* As complement has only one argument, we use only the m_right. */ + this->m_left = nullptr; + this->m_right = right; + m_type = BIT_COMPLEMENT_EXPRESSION; +} + + +/* Copy constructor for bit_complement_expression. */ + +bit_complement_expression::bit_complement_expression ( + const bit_complement_expression &expr) +{ + bit_expression::copy (&expr); +} + + +/* Destructor for bit_expression. */ + +bit_expression::~bit_expression () +{ + delete m_left; + m_left = nullptr; + delete m_right; + m_right = nullptr; +} + + +/* Returns a copy of the bit. */ + +value_bit * +symbolic_bit::copy () const +{ + return new symbolic_bit (*this); +} + + +/* Return a copy of the bit. */ + +value_bit * +bit::copy () const +{ + return new bit (*this); +} + + +/* Copies the given expression to it by copying the left and right operands. */ + +void +bit_expression::copy (const bit_expression *expr) +{ + if (expr->m_left) + m_left = expr->m_left->copy (); + + if (expr->m_right) + m_right = expr->m_right->copy (); + + m_type = expr->m_type; +} + + +/* Returns a copy of the expression. */ + +value_bit * +bit_xor_expression::copy () const +{ + return new bit_xor_expression (*this); +} + + +/* Returns a copy of the expression. */ + +value_bit * +bit_and_expression::copy () const +{ + return new bit_and_expression (*this); +} + + +/* Returns a copy of the expression. */ + +value_bit * +bit_or_expression::copy () const +{ + return new bit_or_expression (*this); +} + + +/* Returns a copy of the expression. */ + +value_bit * +shift_right_expression::copy () const +{ + return new shift_right_expression (*this); +} + + +/* Returns a copy of the expression. */ + +value_bit * +shift_left_expression::copy () const +{ + return new shift_left_expression (*this); +} + + +/* Returns a copy of the expression. */ + +value_bit * +add_expression::copy () const +{ + return new add_expression (*this); +} + + +/* Returns a copy of the expression. */ + +value_bit * +sub_expression::copy () const +{ + return new sub_expression (*this); +} + + +/* Returns a copy of the expression. */ + +value_bit * +bit_complement_expression::copy () const +{ + return new bit_complement_expression (*this); +} + + +/* Constructor that sets the left and right side bits + of the bit_xor_expression sign. */ + +bit_xor_expression::bit_xor_expression (value_bit *left, value_bit *right) +{ + this->m_left = left; + this->m_right = right; + m_type = BIT_XOR_EXPRESSION; +} + + +/* Copy constructor for bit_xor_expression. */ + +bit_xor_expression::bit_xor_expression (const bit_xor_expression &expr) +{ + bit_expression::copy (&expr); +} + + +/* Constructor that sets the left and right side bits + of the bit_and_expression sign. */ + +bit_and_expression::bit_and_expression (value_bit *left, value_bit *right) +{ + this->m_left = left; + this->m_right = right; + m_type = BIT_AND_EXPRESSION; +} + + +/* Copy constructor for bit_and_expression. */ + +bit_and_expression::bit_and_expression (const bit_and_expression &expr) +{ + bit_expression::copy (&expr); +} + + +/* Constructor that sets the left and right side bits + of the bit_or_expression sign. */ + +bit_or_expression::bit_or_expression (value_bit *left, value_bit *right) +{ + this->m_left = left; + this->m_right = right; + m_type = BIT_OR_EXPRESSION; +} + + +/* Copy constructor for bit_or_expression. */ + +bit_or_expression::bit_or_expression (const bit_or_expression &expr) +{ + bit_expression::copy (&expr); +} + + +/* Constructor that sets the left and right side bits + of the shift_right_expression sign. */ + +shift_right_expression::shift_right_expression (value_bit *left, + value_bit *right) +{ + this->m_left = left; + this->m_right = right; + m_type = SHIFT_RIGHT_EXPRESSION; +} + + +/* Copy constructor for shift_right_expression. */ + +shift_right_expression::shift_right_expression ( + const shift_right_expression &expr) +{ + bit_expression::copy (&expr); +} + + +/* Constructor that sets the left and right side bits + of the shift_left_expression sign. */ + +shift_left_expression::shift_left_expression (value_bit *left, value_bit *right) +{ + this->m_left = left; + this->m_right = right; + m_type = SHIFT_LEFT_EXPRESSION; +} + + +/* Copy constructor for shift_left_expression. */ + +shift_left_expression::shift_left_expression (const shift_left_expression &expr) +{ + bit_expression::copy (&expr); +} + + +/* Constructor that sets the left and right side bits + of the add_expression sign. */ + +add_expression::add_expression (value_bit *left, value_bit *right) +{ + this->m_left = left; + this->m_right = right; + m_type = ADD_EXPRESSION; +} + + +/* Copy constructor for add_expression. */ + +add_expression::add_expression (const add_expression &expr) +{ + bit_expression::copy (&expr); +} + + +/* Constructor that sets the left and right side bits + of the sub_expression sign. */ + +sub_expression::sub_expression (value_bit *left, value_bit *right) +{ + this->m_left = left; + this->m_right = right; + m_type = SUB_EXPRESSION; +} + + +/* Copy constructor for sub_expression. */ + +sub_expression::sub_expression (const sub_expression &expr) +{ + bit_expression::copy (&expr); +} + + +/* Returns the origin of the bit, to whom it belongs. */ + +tree +symbolic_bit::get_origin () +{ + return m_origin; +} + + +/* Prints the bit. */ + +void +symbolic_bit::print () +{ + if (dump_file) + { + print_generic_expr (dump_file, m_origin, dump_flags); + fprintf (dump_file, "[%zu]", m_index); + } +} + + +/* Prints the bit. */ + +void +bit::print () +{ + if (dump_file) + fprintf (dump_file, "%u", m_val); +} + + +/* Depending on the expression, prints its sign. */ + +void +bit_expression::print_expr_sign () +{ + switch (m_type) + { + case BIT_XOR_EXPRESSION: + fprintf (dump_file, " ^ "); + break; + case BIT_AND_EXPRESSION: + fprintf (dump_file, " & "); + break; + case BIT_OR_EXPRESSION: + fprintf (dump_file, " | "); + break; + case SHIFT_RIGHT_EXPRESSION: + fprintf (dump_file, " >> "); + break; + case SHIFT_LEFT_EXPRESSION: + fprintf (dump_file, " << "); + break; + case ADD_EXPRESSION: + fprintf (dump_file, " + "); + break; + case SUB_EXPRESSION: + fprintf (dump_file, " - "); + break; + default: + fprintf (dump_file, " ?? "); + } +} + + +/* Prints the expression. */ + +void +bit_expression::print () +{ + if (dump_file) + { + fprintf (dump_file, "("); + if (m_left) + m_left->print (); + else + fprintf (dump_file, "null"); + + print_expr_sign (); + + if (m_right) + m_right->print (); + else + fprintf (dump_file, "null"); + + fprintf (dump_file, ")"); + } +} + + +/* Prints the expression. */ + +void +bit_complement_expression::print () +{ + if (dump_file) + { + fprintf (dump_file, "!"); + if (m_right) + m_right->print (); + else + fprintf (dump_file, "null"); + } +} \ No newline at end of file diff --git a/gcc/sym-exec/sym-exec-expression.h b/gcc/sym-exec/sym-exec-expression.h new file mode 100644 index 00000000000..610088c9637 --- /dev/null +++ b/gcc/sym-exec/sym-exec-expression.h @@ -0,0 +1,332 @@ +/* Every class defined here represents a single bit value of a variable. + Every variable will be represented as a vector of these classes which later + will be used for bit-level symbolic execution. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Matevos Mehrabyan + +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 +. */ + +#ifndef SYM_EXEC_EXPRESSION_H +#define SYM_EXEC_EXPRESSION_H + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "hwint.h" +#include "gimple-pretty-print.h" +#include "is-a.h" +#include "vec.h" +#include "hash-map.h" +#include "hash-set.h" +#include "stddef.h" + +/* Enum used for identifying the class of the bit. */ + +enum value_type { + SYMBOLIC_BIT, + BIT, + BIT_XOR_EXPRESSION, + BIT_AND_EXPRESSION, + BIT_OR_EXPRESSION, + BIT_COMPLEMENT_EXPRESSION, + SHIFT_RIGHT_EXPRESSION, + SHIFT_LEFT_EXPRESSION, + ADD_EXPRESSION, + SUB_EXPRESSION, + BIT_CONDITION +}; + + +/* Base class for single bit value. */ + +class value_bit { + protected: + /* This will help us to understand where is moved the bit + from its initial position. */ + const size_t m_index; + + /* Type of the bit. Used by type checkers. */ + value_type m_type; + + public: + + /* Default constructor. Sets m_index 0. */ + value_bit () : m_index (0) + {}; + + /* Constructor that sets m_index to the specified value. */ + value_bit (size_t i) : m_index (i) + {}; + + /* Copy constructor for value_bit. */ + value_bit (const value_bit &val) : m_index (val.m_index) + {}; + + /* Returns the bit's initial index in bit-vector. */ + size_t get_index () const; + + /* Returns type of the bit. */ + value_type get_type () const; + + /* This will support deep copy of objects' values. */ + virtual value_bit *copy () const = 0; + + /* Prints the bit. Inherited classes must implement it. */ + virtual void print () = 0; + + /* Destructor. */ + virtual ~value_bit () = default; +}; + + +/* Represents value of a single bit of symbolic marked variables. */ + +class symbolic_bit : public value_bit { + /* The Origin of the bit. */ + tree m_origin = nullptr; + + public: + /* Constructor that sets the bit's initial position and its origin. */ + symbolic_bit (size_t i, tree orig); + + /* Copy constructor for symbolic_bit. */ + symbolic_bit (const symbolic_bit &sym_bit) : symbolic_bit (sym_bit.m_index, + sym_bit.m_origin) + {}; + + /* Returns a copy of the bit. */ + value_bit *copy () const; + + /* Prints the bit. */ + void print (); + + /* Returns the origin of the bit, to whom it belongs. */ + tree get_origin (); +}; + + +/* Represents value of a single bit. */ + +class bit : public value_bit { + private: + /* This is the value of a bit. It must be either 1 or 0. */ + unsigned char m_val = 0; + + public: + /* Constructor that sets m_val to the specified value. */ + bit (unsigned char i); + + /* Copy constructor for bit. */ + bit (const bit &b) : bit (b.m_val) + {}; + + /* Returns the value of the bit. */ + unsigned char get_val () const; + + /* Sets the value of the bit. */ + void set_val (unsigned char new_val); + + /* Return a copy of the bit. */ + value_bit *copy () const; + + /* Prints the bit. */ + void print (); +}; + + +/* Bit-level base expression class. In general expressions consist of + two operands. Here we named them m_left and m_right. */ + +class bit_expression : public value_bit { + protected: + /* The bit left to the expression sign. */ + value_bit *m_left = nullptr; + + /* The bit right to the expression sign. */ + value_bit *m_right = nullptr; + + /* Copies the given expression to it by copying + the left and right operands. */ + void copy (const bit_expression *expr); + + /* Depending on the expression, prints its sign. */ + virtual void print_expr_sign (); + + public: + + /* Returns left operand of the expression. */ + value_bit *get_left (); + + /* Returns right operand of the expression. */ + value_bit *get_right (); + + /* Destructor for bit_expression. */ + ~bit_expression (); + + /* Sets left operand of the expression. */ + void set_left (value_bit *expr); + + /* Sets right operand of the expression. */ + void set_right (value_bit *expr); + + /* Returns a deep copy of the expression. */ + value_bit *copy () const = 0; + + /* Prints the expression. */ + void print (); +}; + + +/* Bit-level XOR expression. XOR operation on two variables (when one of + them is symbolic) can be represented by XOR operations on + each of their bits. */ + +class bit_xor_expression : public bit_expression { + public: + /* Constructor that sets the left and right side bits + of the bit_xor_expression sign. */ + bit_xor_expression (value_bit *left, value_bit *right); + + /* Copy constructor for bit_xor_expression. */ + bit_xor_expression (const bit_xor_expression &expr); + + /* Returns a copy of the expression. */ + value_bit *copy () const; +}; + + +/* Bit-level AND expression. AND operation on two variables (when one of + them is symbolic) can be represented by AND operations on + each of their bits. */ + +class bit_and_expression : public bit_expression { + public: + /* Constructor that sets the left and right side bits + of the bit_and_expression sign. */ + bit_and_expression (value_bit *left, value_bit *right); + + /* Copy constructor for bit_and_expression. */ + bit_and_expression (const bit_and_expression &expr); + + /* Returns a copy of the expression. */ + value_bit *copy () const; +}; + + +/* Bit-level OR expression. OR operation on two variables (when one of + them is symbolic) can be represented by OR operations on + each of their bits. */ + +class bit_or_expression : public bit_expression { + public: + /* Constructor that sets the left and right side bits + of the bit_or_expression sign. */ + bit_or_expression (value_bit *left, value_bit *right); + + /* Copy constructor for bit_or_expression. */ + bit_or_expression (const bit_or_expression &expr); + + /* Returns a copy of the expression. */ + value_bit *copy () const; +}; + + +/* SHIFT_RIGHT expression. Result must be stored bit by bit. */ + +class shift_right_expression : public bit_expression { + public: + /* Constructor that sets the left and right side bits + of the shift_right_expression sign. */ + shift_right_expression (value_bit *left, value_bit *right); + + /* Copy constructor for shift_right_expression. */ + shift_right_expression (const shift_right_expression &expr); + + /* Returns a copy of the expression. */ + value_bit *copy () const; +}; + + +/* SHIFT_LEFT expression. Result must be stored bit by bit. */ + +class shift_left_expression : public bit_expression { + public: + /* Constructor that sets the left and right side bits + of the shift_left_expression sign. */ + shift_left_expression (value_bit *left, value_bit *right); + + /* Copy constructor for shift_left_expression. */ + shift_left_expression (const shift_left_expression &expr); + + /* Returns a copy of the expression. */ + value_bit *copy () const; +}; + + +/* ADD expression. Result must be stored bit by bit. */ + +class add_expression : public bit_expression { + public: + /* Constructor that sets the left and right side bits + of the add_expression sign. */ + add_expression (value_bit *left, value_bit *right); + + /* Copy constructor for add_expression. */ + add_expression (const add_expression &expr); + + /* Returns a copy of the expression. */ + value_bit *copy () const; +}; + + +/* SUB expression. Result must be stored bit by bit. */ + +class sub_expression : public bit_expression { + public: + /* Constructor that sets the left and right side bits + of the sub_expression sign. */ + sub_expression (value_bit *left, value_bit *right); + + /* Copy constructor for sub_expression. */ + sub_expression (const sub_expression &expr); + + /* Returns a copy of the expression. */ + value_bit *copy () const; +}; + + +/* Bit-level negation expression. */ + +class bit_complement_expression : public bit_expression { + public: + /* Constructor that sets the left and right side bits + of the bit_complement_expression sign. */ + bit_complement_expression (value_bit *right); + + /* Copy constructor for bit_complement_expression. */ + bit_complement_expression (const bit_complement_expression &expr); + + /* Returns a copy of the expression. */ + value_bit *copy () const; + + /* Prints the expression. */ + void print (); +}; + +#endif /* SYM_EXEC_EXPRESSION_H. */ \ No newline at end of file diff --git a/gcc/sym-exec/sym-exec-state.cc b/gcc/sym-exec/sym-exec-state.cc new file mode 100644 index 00000000000..85e6093c362 --- /dev/null +++ b/gcc/sym-exec/sym-exec-state.cc @@ -0,0 +1,2321 @@ +/* State will store states of variables for a function's single execution path. + It will be used for bit-level symbolic execution to determine values of bits + of function's return value and symbolic marked arguments. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Matevos Mehrabyan + +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 +. */ + +/* This symbolic executor is designed to handle operations on the bit level. + It can save values of variables on the bit level. For example byte x = 9 + would be represented by the bit-vector x = <0, 0, 0, 0, 1, 0, 1, 0> of + size 8. Variables without values will be represented by bit-vectors of + symbolic bits: x = where x[i] is the value + of bit i of variable x. + + Operations are also performed on the bit level. For example, for operation + z = x & y + where + x = + y = + z will have the value + z = + + Each bit of variable can be accessed and examined separately if needed. + Moreover, it does basic optimizations in place. + For example, for operation + z = x | y + where + x = , + y = <1, ..., 0, 1>, + z will have the value + z = <1, ..., x[1], 1> + as x | 0 == x and x | 1 == 1 + + Besides variables, the symbolic executor can also store + conditions on the bit level. + For example, for x == y + It would add {x[size - 1] == y[size - 1], ..., x[1] == y[1], x[0] == y[0]} + conditions. + + For a more complex condition x > y, it would add + {x[size - 1] > y[size - 1] || (x[size - 1] == y[size -1] + && (x[size - 2] > y[size - 2] || (x[size - 2] == y[size - 2] + && ... (x[0] >= y[0])...)} + + The symbolic executor doesn't run by itself. Instead, it must be dictated + what to do. This makes it flexible and allows for various pre- and + post-processing tasks. Developers adding new operation support must consider + that the operation must be represented on the bit level. Because of + this restriction, it may be hard to add support for some operations. + + To use the symbolic executor, you must create a state object. It is the main + object that contains variables as bit-vectors and conditions. + It is the state object that provides operations for symbolic execution. + + If you are going to execute multiple execution paths, you should clone + the state at branching instructions and execute one state for the execution + path where the branching condition evaluates to 'true', and + the other state for the execution path where the branching condition + evaluates to 'false'. Besides that, you should add the corresponding + conditions to states if you need them. + + Variables are stored in the state's 'var_states' field. It maps the tree + object of the variable to its bit-vector. Path conditions are stored in + the 'conditions' field. + + To declare a variable, you should use 'declare_if_needed' method of state. + It declares the variable if it was not previously declared. + 'create_val_for_const' is used for constant declaration. + + The list of supported operations can be found in 'state::do_operation' + method. It calls the corresponding operation based on the specified + tree_code operation. This is the method that you should use to dictate + to the symbolic executor what operations to perform. You can execute the + desired operations explicitly if needed. Variables for participant + operands will be created implicitly if it was not previously declared. + To add conditions to the state, you should use 'state::add_*_cond' methods. + + A sample usage of the symbolic executor: + + // Example. + + unsigned char foo (unsigned char x, unsigned char y) + { + unsigned char D.2352; + unsigned char result; + + result = x & y; + result = result | 9; + if (result == 23) goto ; else goto ; + : + result = result ^ y; + : + D.2352 = result; + return D.2352; + } + + // Now, we create the initial state and add the variables to it. + state s; + s.declare_if_needed (x, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (x)))); + s.declare_if_needed (y, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (y)))); + s.declare_if_needed (d_2352, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (d_2352)))); + s.declare_if_needed (result, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (result)))); + + s.do_operation (BIT_AND_EXPR, x, y, result); + s.do_operation (BIT_OR_EXPR, result, 9, result); + + state s2 (s); // We duplicate the state to save values for each branch. + s.add_equal_cond (result, 23); + s2.add_not_equal_cond (result, 23); + + s.do_operation (BIT_XOR_EXPR, result, y, result); + s.do_assign (result, d_2352); + s2.do_assign (result, d_2352); + + // Now, we have variable values for each execution branch, and we can examine + // them to make decisions. + + value * res = s.get_value (result); + if (is_a ((*res)[0])) + { + bit_expression * expr = is_a ((*res)[0]); + if (is_a (expr->get_left ()) + && as_a (expr->get_left ())->get_val () == 0) + { + ... // Do something. + } + } + + A more general usage would be to iterate over instructions and + call the executor: + + state s; + ... + + for (inst : instructions) + { + enum tree_code rhs_code = gimple_assign_rhs_code (inst); + tree op1 = gimple_assign_rhs1 (gs); + tree op2 = gimple_assign_rhs2 (gs); + tree lhs = gimple_assign_lhs (gs); + s.do_operation (rhs_code, op1, op2, lhs); + ... + } + + */ + +#include "sym-exec-state.h" + +/* Returns the minimum of A, B, C. */ + +size_t min (size_t a, size_t b, size_t c) +{ + size_t min = (a < b ? a : b); + return min < c ? min : c; +} + + +/* Copy constructor for state. It copies all variables and conditions + of the given state. */ + +state::state (const state &s) +{ + for (auto iter = s.var_states.begin (); iter != s.var_states.end (); ++iter) + { + value val ((*iter).second.length (), (*iter).second.is_unsigned); + for (size_t i = 0; i < (*iter).second.length (); i++) + val.push ((*iter).second[i]->copy ()); + + var_states.put ((*iter).first, val); + } + + for (auto iter = s.conditions.begin (); iter != s.conditions.end (); ++iter) + conditions.add (as_a ((*iter)->copy ())); +} + + +/* Destructor for state. */ + +state::~state () +{ + clear_conditions (); +} + + +/* Checks whether state for variable with specified name already + exists or not. */ + +bool +state::is_declared (tree var) +{ + return var_states.get (var) != NULL; +} + + +/* Declares given variable if it has not been declared yet. */ + +void +state::declare_if_needed (tree var, size_t size) +{ + if (TREE_CODE (var) != INTEGER_CST && !is_declared (var)) + { + make_symbolic (var, size); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "Declaring var "); + print_generic_expr (dump_file, var, dump_flags); + fprintf (dump_file, + " with size %zd\n", size); + } + } +} + + +/* Get value of the given variable. */ + +value * +state::get_value (tree var) +{ + return var_states.get (var); +} + + +/* Get the value of the tree, which is in the beginning of the var_states. */ + +value * +state::get_first_value () +{ + return &(*(var_states.begin ())).second; +} + + +/* Returns the list of conditions in the state. */ + +const hash_set & +state::get_conditions () +{ + return conditions; +} + + +/* Checks if sizes of arguments and destination are compatible. */ + +bool +state::check_args_compatibility (tree arg1, tree arg2, tree dest) +{ + if (!(get_var_size (arg1) == get_var_size (dest) + || TREE_CODE (arg1) == INTEGER_CST) + || !(get_var_size (arg2) == get_var_size (dest) + || TREE_CODE (arg2) == INTEGER_CST)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Sym-Exec: Incompatible destination" + "and argument sizes.\n"); + + return false; + } + + return true; +} + + +/* Creates value for given constant tree. */ + +value +state::create_val_for_const (tree var, size_t size) +{ + unsigned HOST_WIDE_INT val = TYPE_UNSIGNED (TREE_TYPE (var)) + ? tree_to_uhwi (var) : tree_to_shwi (var); + value result (size, TYPE_UNSIGNED (TREE_TYPE (var))); + + for (size_t i = 0; i < size; i++) + { + result.push (new bit (val & 1)); + val >>= 1; + } + + return result; +} + + +/* Adds the given variable to state. */ + +bool +state::add_var_state (tree var, value *vstate) +{ + size_t size = vstate->length (); + value val (size, vstate->is_unsigned); + for (size_t i = 0; i < size; i++) + val.push ((*vstate)[i]->copy ()); + + return var_states.put (var, val); +} + + +/* Adds the given condition to the state. */ + +bool +state::add_condition (bit_expression *cond) +{ + return conditions.add (as_a (cond->copy ())); +} + + +/* Bulk add the given conditions to the state. */ + +bool +state::bulk_add_conditions (const hash_set &conds) +{ + bool status = true; + for (auto iter = conds.begin (); iter != conds.end (); ++iter) + status &= add_condition (*iter); + + return status; +} + + +/* Remove all states from the states' vector. */ + +void +state::remove_states (vec *states) +{ + while (!states->is_empty ()) + { + delete states->last (); + states->pop (); + } +} + + +/* Remove all states from the states' vector and release the vector. */ + +void +state::clear_states (vec *states) +{ + remove_states (states); + states->release (); +} + + +/* Removes all variables added to the state. */ + +void +state::clear_var_states () +{ + var_states.empty (); +} + + +/* Removes all conditions added to the state. */ + +void +state::clear_conditions () +{ + for (auto iter = conditions.begin (); iter != conditions.end (); ++iter) + delete (*iter); + conditions.empty (); +} + + +/* Performs AND operation for 2 symbolic_bit operands. */ + +value_bit * +state::and_sym_bits (const value_bit *var1, const value_bit *var2) +{ + return new bit_and_expression (var1->copy (), var2->copy ()); +} + + +/* Performs AND operation for a symbolic_bit and const_bit operands. */ + +value_bit * +state::and_var_const (const value_bit *var1, const bit *const_bit) +{ + if (const_bit->get_val () == 1) + return var1->copy (); + + return new bit (0); +} + + +/* Performs AND operation for 2 constant bit operands. */ + +bit * +state::and_const_bits (const bit *const_bit1, const bit *const_bit2) +{ + if (const_bit1->get_val () == const_bit2->get_val ()) + return new bit (*const_bit1); + + return new bit (0); +} + + +/* Performs OR operation for 2 symbolic_bit operands. */ + +value_bit * +state::or_sym_bits (const value_bit *var1, const value_bit *var2) +{ + return new bit_or_expression (var1->copy (), var2->copy ()); +} + + +/* Performs OR operation for a symbolic_bit and a constant bit operands. */ + +value_bit * +state::or_var_const (const value_bit *var1, const bit *const_bit) +{ + if (const_bit->get_val () == 0) + return var1->copy (); + + return new bit (1); +} + + +/* Performs OR operation for 2 constant bit operands. */ + +bit * +state::or_const_bits (const bit *const_bit1, const bit *const_bit2) +{ + if (const_bit1->get_val () == const_bit2->get_val ()) + return new bit (*const_bit1); + + return new bit (1); +} + + +/* Adds an empty state for the given variable. */ + +bool +state::decl_var (tree var, unsigned size) +{ + if (is_declared (var)) + return false; + + value val (size, TYPE_UNSIGNED (TREE_TYPE (var))); + for (unsigned i = 0; i < size; i++) + val.push (nullptr); + + return var_states.put (var, val); +} + + +/* Returns size of the given variable. */ + +unsigned +state::get_var_size (tree var) +{ + value *content = var_states.get (var); + if (content == NULL) + return 0; + + return content->allocated (); +} + + +/* Adds a variable with unknown value to state. Such variables are + represented as sequence of symbolic bits. */ + +bool +state::make_symbolic (tree var, unsigned size) +{ + if (is_declared (var)) + return false; + + value val (size, TYPE_UNSIGNED (TREE_TYPE (var))); + /* Initialize each bit of a variable with unknown value. */ + for (size_t i = 0; i < size; i++) + val.push (new symbolic_bit (i, var)); + + return var_states.put (var, val); +} + + +/* Performs AND operation on two bits. */ + +value_bit * +state::and_two_bits (value_bit *arg1, value_bit *arg2) +{ + value_bit *result = nullptr; + + if (is_a (arg1) && is_a (arg2)) + result = and_const_bits (as_a (arg1), as_a (arg2)); + + else if (is_a (arg1) && (is_a (arg2) + || (is_a (arg2)))) + result = and_var_const (arg2, as_a (arg1)); + + else if ((is_a (arg1) + || (is_a (arg1))) && is_a (arg2)) + result = and_var_const (arg1, as_a (arg2)); + + else + result = and_sym_bits (arg1, arg2); + + return result; +} + + +/* A wrapper for operations on two bits. + Operation and operands are passed as arguments. */ + +value_bit * +state::operate_bits (bit_func bit_op, value_bit *bit1, value_bit *bit2, + value_bit **) +{ + return (bit_op) (bit1, bit2); +} + + +/* A wrapper for operations on three bits. + Operation and operands are passed as arguments. */ + +value_bit * +state::operate_bits (bit_func3 bit_op, value_bit *bit1, value_bit *bit2, + value_bit **bit3) +{ + return (bit_op) (bit1, bit2, bit3); +} + + +/* Does preprocessing and postprocessing for expressions with tree operands. + Handles value creation for constant and their removement in the end. */ + +bool +state::do_binary_operation (tree arg1, tree arg2, tree dest, + binary_func bin_func) +{ + declare_if_needed (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest)))); + declare_if_needed (arg1, var_states.get (dest)->allocated ()); + declare_if_needed (arg2, var_states.get (dest)->allocated ()); + + if (!check_args_compatibility (arg1, arg2, dest)) + return false; + + size_t dest_size = var_states.get (dest)->length (); + + value *arg1_val = var_states.get (arg1); + value arg1_const_val (dest_size, false); + if (arg1_val == NULL && TREE_CODE (arg1) == INTEGER_CST) + { + arg1_const_val = create_val_for_const (arg1, dest_size); + arg1_val = &arg1_const_val; + } + + value *arg2_val = var_states.get (arg2); + value arg2_const_val (dest_size, false); + if (arg2_val == NULL && TREE_CODE (arg2) == INTEGER_CST) + { + arg2_const_val = create_val_for_const (arg2, dest_size); + arg2_val = &arg2_const_val; + } + + (this->*bin_func) (arg1_val, arg2_val, dest); + print_value (var_states.get (dest)); + return true; +} + + +/* Performs AND operation on given values. The result is stored in dest. */ + +void +state::do_and (value *arg1, value *arg2, tree dest) +{ + /* Creating AND expressions for every bit pair of given arguments + and store them as a new state for given destination. */ + + operate (arg1, arg2, nullptr, dest, &state::and_two_bits); +} + + +/* Performs OR operation on two bits. */ + +value_bit * +state::or_two_bits (value_bit *arg1_bit, value_bit *arg2_bit) +{ + value_bit *result = nullptr; + + if (is_a (arg1_bit) && is_a (arg2_bit)) + result = or_const_bits (as_a (arg1_bit), as_a (arg2_bit)); + + else if (is_a (arg1_bit) && (is_a (arg2_bit) + || is_a (arg2_bit))) + result = or_var_const (arg2_bit, as_a (arg1_bit)); + + else if ((is_a (arg1_bit) + || is_a (arg1_bit)) + && is_a (arg2_bit)) + result = or_var_const (arg1_bit, as_a (arg2_bit)); + + else + result = or_sym_bits (arg1_bit, arg2_bit); + + return result; +} + + +/* Performs OR operation on given values. The result is stored in dest. */ + +void +state::do_or (value *arg1, value *arg2, tree dest) +{ + /* Creating OR expressions for every bit pair of given arguments + and store them as a new state for given destination. */ + operate (arg1, arg2, nullptr, dest, &state::or_two_bits); +} + + +/* Performs XOR operation on two bits. */ + +value_bit * +state::xor_two_bits (value_bit *arg1_bit, value_bit *arg2_bit) +{ + value_bit *result = nullptr; + + if (is_a (arg1_bit) && is_a (arg2_bit)) + result = xor_const_bits (as_a (arg1_bit), as_a (arg2_bit)); + + else if (is_a (arg1_bit) && (is_a (arg2_bit) + || is_a (arg2_bit))) + result = xor_var_const (arg2_bit, as_a (arg1_bit)); + + else if ((is_a (arg1_bit) + || is_a (arg1_bit)) + && is_a (arg2_bit)) + result = xor_var_const (arg1_bit, as_a (arg2_bit)); + + else + result = xor_sym_bits (arg1_bit, arg2_bit); + + return result; +} + + +/* Performs XOR operation on given values. The result is stored in dest. */ + +void +state::do_xor (value *arg1, value *arg2, tree dest) +{ + operate (arg1, arg2, nullptr, dest, &state::xor_two_bits); +} + + +/* Shifts value right by size of shift_value. */ + +value * +state::shift_right_by_const (value *var, size_t shift_value) +{ + value *shift_result = new value (var->length (), var->is_unsigned); + if (var->length () <= shift_value) + for (size_t i = 0; i < var->length (); i++) + shift_result->push (new bit (0)); + else + { + size_t i = 0; + for (; i < var->length () - shift_value; ++i) + shift_result->push (((*var)[shift_value + i])->copy ()); + + for (; i < var->length (); ++i) + shift_result->push (var->is_unsigned ? new bit (0) + : var->last ()->copy ()); + } + return shift_result; +} + + +/* Checks if all bits of the given value have constant bit type. */ + +bool +state::is_bit_vector (const value *var) +{ + if (var == nullptr || !var->exists ()) + return false; + + for (size_t i = 0; i < var->length (); i++) + if (!(is_a ((*var)[i]))) + return false; + return true; +} + + +/* Returns the number represented by the value. */ + +unsigned HOST_WIDE_INT +state::make_number (const value *var) +{ + unsigned HOST_WIDE_INT + number = 0; + int value_size = var->length (); + for (int i = value_size - 1; i >= 0; i--) + { + if (is_a ((*var)[i])) + number = (number << 1) | as_a ((*var)[i])->get_val (); + else + return 0; + } + return number; +} + + +/* Shift_left operation. Case: var2 is a symbolic value. */ + +value_bit * +state::shift_left_sym_bits (value_bit *var1, value_bit *var2) +{ + return new shift_left_expression (var1->copy (), var2->copy ()); +} + + +/* Performs shift left operation on given values. + The result is stored in dest. */ + +void +state::do_shift_left (value *arg1, value *arg2, tree dest) +{ + if (is_bit_vector (arg2)) + { + size_t shift_value = make_number (arg2); + value *result = shift_left_by_const (arg1, shift_value); + for (size_t i = 0; i < get_var_size (dest); i++) + { + delete (*var_states.get (dest))[i]; + (*var_states.get (dest))[i] = (*result)[i]->copy (); + } + delete result; + } + else + operate (arg1, arg2, nullptr, dest, &state::shift_left_sym_bits); +} + + +/* Performs shift right operation on given values. + The result is stored in dest. */ + +void +state::do_shift_right (value *arg1, value *arg2, tree dest) +{ + if (is_bit_vector (arg2)) + { + size_t shift_value = make_number (arg2); + value *result = shift_right_by_const (arg1, shift_value); + for (size_t i = 0; i < get_var_size (dest); i++) + { + delete (*var_states.get (dest))[i]; + (*var_states.get (dest))[i] = (*result)[i]->copy (); + } + + delete result; + } + else + operate (arg1, arg2, nullptr, dest, &state::shift_right_sym_bits); +} + + +/* Adds two bits and carry value. + Resturn result and stores new carry bit in "carry". */ + +value_bit * +state::full_adder (value_bit *var1, value_bit *var2, value_bit **carry) +{ + value_bit *new_carry = and_two_bits (var1, var2); + value_bit *sum = xor_two_bits (var1, var2); + + value_bit *result = xor_two_bits (sum, *carry); + value_bit *sum_and_carry = and_two_bits (sum, *carry); + + delete *carry; + delete sum; + + *carry = or_two_bits (sum_and_carry, new_carry); + + delete sum_and_carry; + delete new_carry; + + return result; +} + + +/* Adds given values. The result is stored in dest. */ + +void +state::do_add (value *arg1, value *arg2, tree dest) +{ + value_bit *carry = new bit (0); + operate (arg1, arg2, &carry, dest, &state::full_adder); + delete carry; +} + + +/* Returns the additive inverse of the given number. */ + +value * +state::additive_inverse (const value *number) +{ + value *result = new value (number->length (), number->is_unsigned); + value one (number->length (), number->is_unsigned); + + size_t size = number->length (); + one.push (new bit (1)); + result->push (complement_a_bit ((*number)[0])); + + for (size_t i = 1; i < size; i++) + { + one.push (new bit (0)); + result->push (complement_a_bit ((*number)[i])); + } + + value_bit *carry = new bit (0); + for (size_t i = 0; i < size; ++i) + { + value_bit *cur_bit = (*result)[i]; + (*result)[i] = full_adder (cur_bit, one[i], &carry); + delete cur_bit; + } + + delete carry; + return result; +} + + +/* Subtracks second value from the first. The result is stored in dest. */ + +void +state::do_sub (value *arg1, value *arg2, tree dest) +{ + value *neg_arg2 = additive_inverse (arg2); + do_add (arg1, neg_arg2, dest); + delete neg_arg2; +} + + +/* Performs complement operation on a bit. */ + +value_bit * +state::complement_a_bit (value_bit *var) +{ + value_bit *result = nullptr; + if (is_a (var)) + result = complement_const_bit (as_a (var)); + else + result = complement_sym_bit (var); + + return result; +} + + +/* Negates given variable. */ + +bool +state::do_complement (tree arg, tree dest) +{ + declare_if_needed (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest)))); + declare_if_needed (arg, var_states.get (dest)->allocated ()); + + /* Creating complement expressions for every bit the given argument + and store it as a new state for given destination. */ + size_t iter_count = min (get_var_size (dest), get_var_size (arg), + get_var_size (arg)); + + size_t i = 0; + for (; i < iter_count; i++) + { + value_bit *result = complement_a_bit ((*var_states.get (arg))[i]); + delete (*var_states.get (dest))[i]; + (*var_states.get (dest))[i] = result; + } + + if (i >= get_var_size (dest)) + { + print_value (var_states.get (dest)); + return true; + } + + for (; i < get_var_size (dest); i++) + { + delete (*var_states.get (dest))[i]; + bit tmp (0); + (*var_states.get (dest))[i] = complement_a_bit (&tmp); + } + + print_value (var_states.get (dest)); + return true; +} + + +/* Does Assignment. */ + +bool +state::do_assign (tree arg, tree dest) +{ + declare_if_needed (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest)))); + if (TREE_CODE (arg) != INTEGER_CST) + declare_if_needed (arg, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (arg)))); + else + declare_if_needed (arg, var_states.get (dest)->allocated ()); + + value *dest_val = var_states.get (dest); + + /* If the argument is already defined, then we must just copy its bits. */ + if (auto arg_val = var_states.get (arg)) + { + for (size_t i = 0; i < dest_val->length (); i++) + { + value_bit *new_val = nullptr; + if (i < arg_val->length ()) + new_val = (*arg_val)[i]->copy (); + else + new_val = new bit (0); + + delete (*dest_val)[i]; + (*dest_val)[i] = new_val; + } + } + /* If the argument is a constant, we must save it as sequence of bits. */ + else if (TREE_CODE (arg) == INTEGER_CST) + { + value arg_val + = create_val_for_const (arg, dest_val->length ()); + for (size_t i = 0; i < dest_val->length (); i++) + { + delete (*dest_val)[i]; + (*dest_val)[i] = arg_val[i]->copy (); + } + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Sym-Exec: Unsupported assignment" + " for given argument.\n"); + + return false; + } + + print_value (var_states.get (dest)); + return true; +} + + +/* Assigns pow 2 value. */ + +bool +state::do_assign_pow2 (tree dest, unsigned pow) +{ + value *dest_val = var_states.get (dest); + unsigned dest_size = dest_val ? dest_val->allocated () + : tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest))); + if (pow > dest_size) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Sym-Exec: pow %u of 2 won't fit in" + " specified destination\n", pow); + return false; + } + + if (!dest_val) + { + decl_var (dest, tree_to_uhwi (TYPE_SIZE (TREE_TYPE (dest)))); + dest_val = var_states.get (dest); + } + else + dest_val->free_bits (); + + for (unsigned i = 0; i < dest_val->length (); i++) + { + if (i == pow) + (*dest_val)[i] = new bit (1); + else + (*dest_val)[i] = new bit (0); + } + + print_value (dest_val); + return true; +} + + +/* Performs NOT operation for constant bit. */ + +bit * +state::complement_const_bit (const bit *const_bit) +{ + return new bit (1u ^ const_bit->get_val ()); +} + + +/* Performs NOT operation for symbolic_bit. */ + +value_bit * +state::complement_sym_bit (const value_bit *var) +{ + return new bit_complement_expression (var->copy ()); +} + + +/* Performs XOR operation for 2 symbolic_bit operands. */ + +value_bit * +state::xor_sym_bits (const value_bit *var1, const value_bit *var2) +{ + value_bit *var2_copy = var2->copy (); + bit_expression *node2_with_const_child = nullptr; + bit_expression *parent_of_node2_with_child = nullptr; + get_parent_with_const_child (var2_copy, node2_with_const_child, + parent_of_node2_with_child); + + if (node2_with_const_child != nullptr) + { + value_bit *var1_copy = var1->copy (); + bit_expression *node1_with_const_child = nullptr; + bit_expression *parent_of_node1_with_child = nullptr; + get_parent_with_const_child (var1_copy, node1_with_const_child, + parent_of_node1_with_child); + + /* If both subtrees have constant bit nodes, + we can merge them together. */ + if (node1_with_const_child != nullptr) + { + value_bit *var1_reformed = nullptr; + value_bit *var2_reformed = nullptr; + + /* If var1's const bit is in its left subtree. */ + value_bit *var1_left = node1_with_const_child->get_left (); + if (var1_left != nullptr && is_a (var1_left)) + { + var1_reformed = node1_with_const_child->get_right ()->copy (); + value_bit *var2_left = node2_with_const_child->get_left (); + + /* If var2's const bit is in its left subtree. */ + if (var2_left != nullptr && is_a (var2_left)) + var2_reformed = node2_with_const_child->get_right ()->copy (); + else /* Var2's const bit is in its right subtree. */ + var2_reformed = node2_with_const_child->get_left ()->copy (); + } + else /* Var1's const bit is in its right subtree. */ + { + var1_reformed = node1_with_const_child->get_left ()->copy (); + value_bit *var2_left = node2_with_const_child->get_left (); + + /* If var2's const bit is in its left subtree. */ + if (var2_left != nullptr && is_a (var2_left)) + var2_reformed = node2_with_const_child->get_right ()->copy (); + else /* Var2's const bit is in its right subtree. */ + var2_reformed = node2_with_const_child->get_left ()->copy (); + } + + if (parent_of_node1_with_child) + { + parent_of_node1_with_child->get_left () + == node1_with_const_child + ? parent_of_node1_with_child->set_left (var1_reformed) + : parent_of_node1_with_child->set_right (var1_reformed); + delete node1_with_const_child; + } + else + { + delete var1_copy; + var1_copy = var1_reformed; + } + + if (parent_of_node2_with_child) + { + parent_of_node2_with_child->get_left () + == node2_with_const_child + ? parent_of_node2_with_child->set_left (var2_reformed) + : parent_of_node2_with_child->set_right (var2_reformed); + delete node2_with_const_child; + } + else + { + delete var2_copy; + var2_copy = var2_reformed; + } + + return new bit_xor_expression (var1_copy, var2_copy); + } + delete var1_copy; + } + + delete var2_copy; + return new bit_xor_expression (var1->copy (), var2->copy ()); +} + + +/* Performs XOR operation for 2 constant bit operands. */ + +bit * +state::xor_const_bits (const bit *const_bit1, const bit *const_bit2) +{ + return new bit (const_bit1->get_val () ^ const_bit2->get_val ()); +} + + +/* Performs XOR operation for a symbolic_bit and const_bit operands. */ + +value_bit * +state::xor_var_const (const value_bit *var, const bit *const_bit) +{ + if (const_bit->get_val () == 0) + return var->copy (); + + value_bit *var_copy = var->copy (); + bit_expression *node_with_const_child = nullptr; + bit_expression *tmp = nullptr; + get_parent_with_const_child (var_copy, node_with_const_child, tmp); + + if (node_with_const_child != nullptr) + { + value_bit *left = node_with_const_child->get_left (); + if (left != nullptr && is_a (left)) + { + bit *new_left = xor_const_bits (as_a (left), const_bit); + delete left; + node_with_const_child->set_left (new_left); + } + else + { + value_bit *right = node_with_const_child->get_right (); + bit *new_right = xor_const_bits (as_a (right), const_bit); + delete right; + node_with_const_child->set_right (new_right); + } + return var_copy; + } + + delete var_copy; + return new bit_xor_expression (var->copy (), const_bit->copy ()); +} + + +/* Return node which has a const bit child. Traversal is done based + on safe branching. */ + +void +state::get_parent_with_const_child (value_bit *root, bit_expression *&parent, + bit_expression *&parent_of_parent) +{ + parent_of_parent = nullptr; + parent = nullptr; + + if (!is_a (root)) + return; + + bit_expression *expr_root = as_a (root); + hash_set < bit_expression * > nodes_to_consider; + nodes_to_consider.add (expr_root); + + hash_map < bit_expression * , bit_expression * > node_to_parent; + node_to_parent.put (expr_root, nullptr); + + /* Traversing expression tree: + considering only comutative expression nodes. */ + while (!nodes_to_consider.is_empty ()) + { + bit_expression *cur_element = *nodes_to_consider.begin (); + nodes_to_consider.remove (cur_element); + + value_bit *left = cur_element->get_left (); + value_bit *right = cur_element->get_right (); + + if ((left != nullptr && is_a (left)) + || (right != nullptr && is_a (right))) + { + parent = cur_element; + parent_of_parent = *node_to_parent.get (cur_element); + } + + if (left != nullptr && is_a (left)) + { + nodes_to_consider.add (as_a (left)); + node_to_parent.put (as_a (left), cur_element); + } + + if (right != nullptr && is_a (right)) + { + nodes_to_consider.add (as_a (right)); + node_to_parent.put (as_a (right), cur_element); + } + } +} + + +/* Shifts number left by size of shift_value. */ + +value * +state::shift_left_by_const (const value *number, size_t shift_value) +{ + value *shift_result = new value (number->length (), number->is_unsigned); + if (number->length () <= shift_value) + for (size_t i = 0; i < number->length (); i++) + shift_result->push (new bit (0)); + + else + { + size_t i = 0; + for (; i < shift_value; ++i) + shift_result->push (new bit (0)); + for (size_t j = 0; i < number->length (); ++i, j++) + shift_result->push (((*number)[j])->copy ()); + } + return shift_result; +} + + +/* Shift_right operation. Case: var2 is a symbolic value. */ + +value_bit * +state::shift_right_sym_bits (value_bit *var1, value_bit *var2) +{ + return new shift_right_expression (var1->copy (), var2->copy ()); +} + + +/* Adds two values, stores the result in the first one. */ + +void +state::add_numbers (value *var1, const value *var2) +{ + value_bit *carry = new bit (0); + for (unsigned i = 0; i < var1->length (); i++) + { + value_bit *temp = (*var1)[i]; + (*var1)[i] = full_adder ((*var1)[i], (*var2)[i], &carry); + delete temp; + } + delete carry; +} + + +/* ANDs every bit of the vector with var_bit, stroes the result in var1. */ + +void +state::and_number_bit (value *var1, value_bit *var_bit) +{ + for (unsigned i = 0; i < var1->length (); i++) + { + value_bit *tmp = (*var1)[i]; + (*var1)[i] = and_two_bits ((*var1)[i], var_bit); + delete tmp; + } + +} + + +/* Multiplies given values. The result is stored in dest. */ + +void +state::do_mul (value *arg1, value *arg2, tree dest) +{ + value *shifted = new value (*arg1); + value *dest_val = var_states.get (dest); + + for (unsigned i = 0; i < dest_val->length (); i++) + { + delete (*dest_val)[i]; + (*dest_val)[i] = new bit (0); + } + + for (unsigned i = arg2->length (); i != 0; --i) + { + if (is_a ((*arg2)[i - 1]) + && as_a ((*arg2)[i - 1])->get_val () != 0) + add_numbers (dest_val, shifted); + else if (is_a ((*arg2)[i - 1])) + { + and_number_bit (shifted, as_a ((*arg2)[i - 1])); + add_numbers (dest_val, shifted); + } + + value *temp = shifted; + shifted = shift_left_by_const (shifted, 1); + delete temp; + } + delete shifted; +} + + +/* Checks whether the given two constant values are equal. */ + +bool +state::check_const_value_equality (value *arg1, value *arg2) +{ + for (size_t i = 0; i < arg1->length (); i++) + if (as_a ((*arg1)[i])->get_val () + != as_a ((*arg2)[i])->get_val ()) + return false; + return true; +} + + +/* Adds EQUAL condition of given variables to state. */ + +bool +state::add_equal_cond (tree arg1, tree arg2) +{ + return add_binary_cond (arg1, arg2, &state::add_equal_cond); +} + + +/* Adds equality condition for two values. */ + +void +state::add_equal_cond (value *arg1, value *arg2) +{ + + /* If both arguments are constants then we can evaluate it. */ + if (is_bit_vector (arg1) && is_bit_vector (arg2)) + { + bool result = check_const_value_equality (arg1, arg2); + last_cond_status = result ? condition_status::CS_TRUE + : condition_status::CS_FALSE; + return; + } + + /* When some of bits are constants and they differ by value, + then we can evalate it to be false. */ + for (size_t i = 0; i < arg1->length (); i++) + { + if (is_a ((*arg1)[i]) && is_a ((*arg2)[i]) + && as_a ((*arg1)[i])->get_val () + != as_a ((*arg2)[i])->get_val ()) + { + last_cond_status = condition_status::CS_FALSE; + return; + } + } + + for (size_t i = 0; i < arg1->length (); i++) + { + /* If there is a constant bit pair, then they are equal + as we checked not equality above. */ + if (is_a ((*arg1)[i]) && is_a ((*arg2)[i])) + continue; + + conditions.add (new bit_condition ((*arg1)[i]->copy (), + (*arg2)[i]->copy (), + EQ_EXPR)); + } + last_cond_status = condition_status::CS_SYM; +} + + +/* Checks whether the given two constant values are not equal. */ + +bool +state::check_const_value_are_not_equal (value *arg1, value *arg2) +{ + for (size_t i = 0; i < arg1->length (); i++) + if (as_a ((*arg1)[i])->get_val () + != as_a ((*arg2)[i])->get_val ()) + return true; + return false; +} + + +/* Adds NOT EQUAL condition of given variables to state. */ + +bool +state::add_not_equal_cond (tree arg1, tree arg2) +{ + return add_binary_cond (arg1, arg2, &state::add_not_equal_cond); +} + + +/* Adds not equal condition for two values. */ + +void +state::add_not_equal_cond (value *arg1, value *arg2) +{ + if (is_bit_vector (arg1) && is_bit_vector (arg2)) + { + bool result = check_const_value_are_not_equal (arg1, arg2); + last_cond_status = result ? condition_status::CS_TRUE + : condition_status::CS_FALSE; + return; + } + + /* When some of bits are constants and they differ by value, + then we can evalate it to be true. */ + for (size_t i = 0; i < arg1->length (); i++) + { + if (is_a ((*arg1)[i]) && is_a ((*arg2)[i]) + && as_a ((*arg1)[i])->get_val () + != as_a ((*arg2)[i])->get_val ()) + { + last_cond_status = condition_status::CS_TRUE; + return; + } + } + + bit_expression *prev = nullptr; + for (size_t i = 0; i < arg1->length (); i++) + { + /* If there is a constant bit pair, then they are equal + as we checked not equality above. */ + if (is_a ((*arg1)[i]) && is_a ((*arg2)[i])) + continue; + + bit_condition *new_cond = new bit_condition ((*arg1)[i]->copy (), + (*arg2)[i]->copy (), + NE_EXPR); + if (prev) + prev = new bit_or_expression (prev, new_cond); + else + prev = new_cond; + } + + last_cond_status = condition_status::CS_SYM; + conditions.add (prev); +} + + +/* Checks whether the first given constant value + is greater than the second one. */ + +bool +state::check_const_value_is_greater_than (value *arg1, value *arg2) +{ + for (int i = arg1->length () - 1; i >= 0; i--) + { + if (as_a ((*arg1)[i])->get_val () + > as_a ((*arg2)[i])->get_val ()) + return true; + else if (as_a ((*arg1)[i])->get_val () + < as_a ((*arg2)[i])->get_val ()) + return false; + } + return false; +} + + +/* Adds GREATER THAN condition of given variables to state. */ + +bool +state::add_greater_than_cond (tree arg1, tree arg2) +{ + return add_binary_cond (arg1, arg2, &state::add_greater_than_cond); +} + + +/* Adds greater than condition for two values. */ + +void +state::add_greater_than_cond (value *arg1, value *arg2) +{ + if (is_bit_vector (arg1) && is_bit_vector (arg2)) + { + bool result = check_const_value_is_greater_than (arg1, arg2); + last_cond_status = result ? condition_status::CS_TRUE + : condition_status::CS_FALSE; + return; + } + + if (is_bit_vector (arg2) && is_a (arg1->last ()) + && make_number (arg2) == 0 && !arg1->is_unsigned) + { + if (as_a (arg1->last ())->get_val () == 1) + last_cond_status = condition_status::CS_FALSE; + else + { + for (size_t i = 0; i < arg1->length (); i++) + if (is_a ((*arg1)[i]) + && as_a ((*arg1)[i])->get_val ()) + { + last_cond_status = condition_status::CS_TRUE; + return; + } + } + } + + bit_expression *gt_cond = construct_great_than_cond (arg1, arg2); + if (gt_cond) + { + /* Otherwise its status is already set. */ + last_cond_status = condition_status::CS_SYM; + conditions.add (gt_cond); + } +} + + +/* Constructs expression trees of greater than condition for given values. */ + +bit_expression * +state::construct_great_than_cond (value *arg1, value *arg2) +{ + bit_expression *prev = nullptr; + int i = arg1->length () - 1; + for (; i >= 0; i--) + { + if (is_a ((*arg1)[i]) && is_a ((*arg2)[i])) + { + if (as_a ((*arg1)[i])->get_val () + > as_a ((*arg2)[i])->get_val ()) + { + if (!prev) + last_cond_status = condition_status::CS_TRUE; + return prev; + } + else if (as_a ((*arg1)[i])->get_val () + < as_a ((*arg2)[i])->get_val ()) + { + if (prev) + { + bit_expression *ret_val + = as_a (prev->get_left ()->copy ()); + delete prev; + return ret_val; + } + else + { + last_cond_status = condition_status::CS_FALSE; + return nullptr; + } + } + } + else + { + bit_condition *gt_cond + = new bit_condition ((*arg1)[i]->copy (), (*arg2)[i]->copy (), + GT_EXPR); + bit_expression *expr = nullptr; + if (i) + { + bit_condition *eq_cond + = new bit_condition ((*arg1)[i]->copy (), (*arg2)[i]->copy (), + EQ_EXPR); + expr = new bit_or_expression (gt_cond, eq_cond); + } + else + expr = gt_cond; + + if (prev) + prev = new bit_and_expression (expr, prev); + else + prev = expr; + } + } + + return prev; +} + + +/* Checks whether the first given constant value + is less than the second one. */ + +bool +state::check_const_value_is_less_than (value *arg1, value *arg2) +{ + for (int i = arg1->length () - 1; i >= 0; i--) + { + if (as_a ((*arg1)[i])->get_val () + < as_a ((*arg2)[i])->get_val ()) + return true; + else if (as_a ((*arg1)[i])->get_val () + > as_a ((*arg2)[i])->get_val ()) + return false; + } + return false; +} + + +/* Adds LESS THAN condition of given variables to state. */ + +bool +state::add_less_than_cond (tree arg1, tree arg2) +{ + return add_binary_cond (arg1, arg2, &state::add_less_than_cond); +} + + +/* Adds less than condition for two values. */ + +void +state::add_less_than_cond (value *arg1, value *arg2) +{ + if (is_bit_vector (arg1) && is_bit_vector (arg2) + && (make_number (arg2) != 0 || arg1->is_unsigned)) + { + bool result = check_const_value_is_less_than (arg1, arg2); + last_cond_status = result ? condition_status::CS_TRUE + : condition_status::CS_FALSE; + return; + } + + last_cond_status = condition_status::CS_SYM; + if (is_bit_vector (arg2) && make_number (arg2) == 0 && !arg1->is_unsigned) + { + if (is_a (arg1->last ())) + { + if (as_a (arg1->last ())->get_val () == 1) + last_cond_status = condition_status::CS_TRUE; + else + last_cond_status = condition_status::CS_FALSE; + } + else + conditions.add (new bit_condition (arg1->last ()->copy (), new bit (1), + EQ_EXPR)); + + return; + } + + bit_expression *lt_cond = construct_less_than_cond (arg1, arg2); + if (lt_cond) + /* Otherwise its status is already set. */ + conditions.add (lt_cond); +} + + +/* Constructs expression trees of less than condition for given values. */ + +bit_expression * +state::construct_less_than_cond (value *arg1, value *arg2) +{ + bit_expression *prev = nullptr; + int i = arg1->length () - 1; + for (; i >= 0; i--) + { + if (is_a ((*arg1)[i]) && is_a ((*arg2)[i])) + { + if (as_a ((*arg1)[i])->get_val () + < as_a ((*arg2)[i])->get_val ()) + { + if (!prev) + last_cond_status = condition_status::CS_TRUE; + return prev; + } + else if (as_a ((*arg1)[i])->get_val () + > as_a ((*arg2)[i])->get_val ()) + { + if (prev) + { + bit_expression *ret_val + = as_a (prev->get_left ()->copy ()); + delete prev; + return ret_val; + } + else + { + last_cond_status = condition_status::CS_FALSE; + return nullptr; + } + } + } + else + { + bit_condition *lt_cond + = new bit_condition ((*arg1)[i]->copy (), (*arg2)[i]->copy (), + LT_EXPR); + bit_expression *expr = nullptr; + if (i) + { + bit_condition *eq_cond + = new bit_condition ((*arg1)[i]->copy (), (*arg2)[i]->copy (), + EQ_EXPR); + expr = new bit_or_expression (lt_cond, eq_cond); + } + else + expr = lt_cond; + + if (prev) + prev = new bit_and_expression (expr, prev); + else + prev = expr; + } + } + + return prev; +} + + +/* Adds GREATER OR EQUAL condition of given variables to state. */ + +bool +state::add_greater_or_equal_cond (tree arg1, tree arg2) +{ + return add_binary_cond (arg1, arg2, &state::add_greater_or_equal_cond); +} + + +/* Adds greater or equal condition for two values. */ + +void +state::add_greater_or_equal_cond (value *arg1, value *arg2) +{ + if (is_bit_vector (arg1) && is_bit_vector (arg2) + && (make_number (arg2) != 0 || arg1->is_unsigned)) + { + bool is_greater_than = check_const_value_is_greater_than (arg1, + arg2); + bool is_equal = check_const_value_equality (arg1, arg2); + last_cond_status = (is_greater_than | is_equal) + ? condition_status::CS_TRUE + : condition_status::CS_FALSE; + return; + } + + last_cond_status = condition_status::CS_SYM; + if (is_bit_vector (arg2) && make_number (arg2) == 0 && !arg1->is_unsigned) + { + if (is_a (arg1->last ())) + { + if (as_a (arg1->last ())->get_val () == 1) + last_cond_status = condition_status::CS_FALSE; + else + last_cond_status = condition_status::CS_TRUE; + } + else + conditions.add (new bit_condition (arg1->last ()->copy (), new bit (0), + EQ_EXPR)); + + return; + } + + bit_expression *eq_cond = construct_equal_cond (arg1, arg2); + if (!eq_cond) + return; + + bit_expression *gt_cond = construct_great_than_cond (arg1, arg2); + if (gt_cond) + /* Otherwise its status is already set. */ + conditions.add (new bit_or_expression (eq_cond, gt_cond)); +} + + +/* Adds LESS OR EQUAL condition of given variables to state. */ + +bool +state::add_less_or_equal_cond (tree arg1, tree arg2) +{ + return add_binary_cond (arg1, arg2, &state::add_less_or_equal_cond); +} + + +/* Adds less or equal condition for two values. */ + +void +state::add_less_or_equal_cond (value *arg1, value *arg2) +{ + if (is_bit_vector (arg1) && is_bit_vector (arg2)) + { + bool is_less_than = check_const_value_is_less_than (arg1, arg2); + bool is_equal = check_const_value_equality (arg1, arg2); + last_cond_status = (is_less_than | is_equal) + ? condition_status::CS_TRUE + : condition_status::CS_FALSE; + return; + } + + last_cond_status = condition_status::CS_SYM; + bit_expression *eq_cond = construct_equal_cond (arg1, arg2); + if (!eq_cond) + return; + + bit_expression *lt_cond = construct_less_than_cond (arg1, arg2); + if (lt_cond) + /* Otherwise its status is already set. */ + conditions.add (new bit_or_expression (eq_cond, lt_cond)); +} + + +/* Adds a bool condition to state. */ + +bool +state::add_bool_cond (tree arg) +{ + if (!is_declared (arg)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Sym-Exec: Argument must be declared " + "for bool condition.\n"); + + return false; + } + + value *arg_bits = var_states.get (arg); + for (size_t i = 0; i < arg_bits->length (); i++) + if (is_a ((*arg_bits)[i]) + && as_a ((*arg_bits)[i])->get_val () != 0) + { + last_cond_status = condition_status::CS_TRUE; + print_conditions (); + return true; + } + + if (is_bit_vector (arg_bits)) + { + last_cond_status = condition_status::CS_FALSE; + print_conditions (); + return true; + } + + bit_expression *prev = nullptr; + for (size_t i = 0; i < arg_bits->length (); i++) + { + if (is_a ((*arg_bits)[i])) + continue; + + bit_condition *not_eq_cond + = new bit_condition ((*arg_bits)[i], new bit (0), NE_EXPR); + if (prev) + prev = new bit_or_expression (not_eq_cond, prev); + else + prev = not_eq_cond; + } + + last_cond_status = condition_status::CS_SYM; + conditions.add (prev); + print_conditions (); + return true; +} + + +/* Does preprocessing and postprocessing for condition adding. + Handles value creation for constants and their removement in the end. */ + +bool +state::add_binary_cond (tree arg1, tree arg2, binary_cond_func cond_func) +{ + bool arg1_is_declared = is_declared (arg1); + bool arg2_is_declared = is_declared (arg2); + + if (!arg1_is_declared && !arg2_is_declared) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Sym-Exec: At least one of arguments must be" + " declared for adding the condition.\n"); + + return false; + } + + if (arg1_is_declared) + declare_if_needed (arg2, var_states.get (arg1)->length ()); + + if (arg2_is_declared) + declare_if_needed (arg1, var_states.get (arg2)->length ()); + + value *arg1_val = var_states.get (arg1); + value arg1_const_val (MAX_VALUE_SIZE, false); + + if (arg1_val == NULL && TREE_CODE (arg1) == INTEGER_CST) + { + arg1_const_val = create_val_for_const (arg1, + var_states.get (arg2)->length ()); + arg1_val = &arg1_const_val; + } + + value *arg2_val = var_states.get (arg2); + value arg2_const_val (MAX_VALUE_SIZE, false); + if (arg2_val == NULL && TREE_CODE (arg2) == INTEGER_CST) + { + arg2_const_val = create_val_for_const (arg2, + var_states.get (arg1)->length ()); + arg2_val = &arg2_const_val; + } + + (this->*cond_func) (arg1_val, arg2_val); + print_conditions (); + return true; +} + + +/* Constructs expression trees of equal condition for given values. */ + +bit_expression * +state::construct_equal_cond (value *arg1, value *arg2) +{ + /* If both arguments are constants then we can evaluate it. */ + if (is_bit_vector (arg1) && is_bit_vector (arg2)) + { + bool result = check_const_value_equality (arg1, arg2); + last_cond_status = result ? condition_status::CS_TRUE + : condition_status::CS_FALSE; + return nullptr; + } + + /* When some bits are constants, and they differ by value, + then we can evaluate it to be false. */ + for (size_t i = 0; i < arg1->length (); i++) + { + if (is_a ((*arg1)[i]) && is_a ((*arg2)[i]) + && as_a ((*arg1)[i])->get_val () + != as_a ((*arg2)[i])->get_val ()) + { + last_cond_status = condition_status::CS_FALSE; + return nullptr; + } + } + + bit_expression *prev = nullptr; + for (size_t i = 0; i < arg1->length (); i++) + { + bit_condition *eq_expr = new bit_condition ((*arg1)[i]->copy (), + (*arg2)[i]->copy (), EQ_EXPR); + if (prev) + prev = new bit_and_expression (eq_expr, prev); + else + prev = eq_expr; + } + + return prev; +} + + +/* Constructor for value. The first argument is the size of the bit-vector + and the second argument is the sign of the number. */ + +value::value (unsigned size, bool is_unsigned) : is_unsigned (is_unsigned) +{ + number.create (size); +} + + +/* Copy constructor for value. */ + +value::value (const value &other) : is_unsigned (other.is_unsigned) +{ + number.create (other.length ()); + for (size_t i = 0; i < other.length (); ++i) + { + value_bit *temp = other[i] ? other[i]->copy () : other[i]; + number.quick_push (temp); + } +} + + +/* Returns pushed bits count. */ + +unsigned +value::length () const +{ + return number.length (); +} + + +/* Wrapper of vec<..>::operator[] for the bit-vector. */ + +value_bit *& +value::operator[] (unsigned i) +{ + return number[i]; +} + + +/* Assignment operator. If the specified value's size is smaller, + then 0 constant bit will be assigned to the remaining upper bits. */ + +value & +value::operator= (const value &other) +{ + unsigned smallest = number.allocated () < other.length () + ? number.allocated () : other.length (); + + for (size_t i = 0; i < smallest; i++) + if (i < number.length ()) + { + delete number[i]; + number[i] = other[i]->copy (); + } + else + number.quick_push (other[i]->copy ()); + + for (size_t i = smallest; i < number.allocated (); i++) + if (i < number.length ()) + { + delete number[i]; + number[i] = other.is_unsigned ? new bit (0) + : other[other.length () - 1]->copy (); + } + else + number.quick_push (other.is_unsigned + ? new bit (0) : other[other.length () - 1]->copy ()); + + return (*this); +} + + +/* Wrapper of vec<..>::operator[] const for the bit-vector. */ + +value_bit * +value::operator[] (unsigned i) const +{ + return number[i]; +} + + +/* Wrapper of vec<..>.exists for the bit-vector. */ + +bool +value::exists () const +{ + return number.exists (); +} + + +/* Returns the size in bits. */ + +unsigned +value::allocated () const +{ + return number.allocated (); +} + + +/* Returns a reference the last bit. */ + +value_bit *& +value::last () +{ + return number.last (); +} + + +/* Make a copy of given bits. */ + +vec * +state::make_copy (vec *bits) +{ + vec < value_bit * > *copied_bits = new vec (); + copied_bits->create (bits->length ()); + for (size_t i = 0; i < bits->length (); i++) + copied_bits->quick_push ((*bits)[i]->copy ()); + + return copied_bits; +} + + +/* Returns status of last added condition. */ + +condition_status +state::get_last_cond_status () +{ + return last_cond_status; +} + + +/* Prints the given value. */ + +void +state::print_value (value *var) +{ + if (!dump_file || !(dump_flags & TDF_DETAILS)) + return; + + fprintf (dump_file, "{"); + for (int i = var->length () - 1; i >= 0; i--) + { + (*var)[i]->print (); + + if (i) + fprintf (dump_file, ", "); + } + fprintf (dump_file, "}\n"); +} + + +/* Get the last 1 bit index. */ + +size_t +last_set_bit (const value &polynomial) +{ + for (size_t i = 0; i < polynomial.length (); ++i) + { + if (as_a (polynomial[polynomial.length () - i - 1])->get_val ()) + return polynomial.length () - i - 1; + } + return 0; +} + + +/* Prints added conditions. */ + +void +state::print_conditions () +{ + if (!dump_file || !(dump_flags & TDF_DETAILS)) + return; + + fprintf (dump_file, "Conditions {"); + auto iter = conditions.begin (); + while (true) + { + if (iter != conditions.end ()) + { + (*iter)->print (); + ++iter; + } + + if (iter != conditions.end ()) + fprintf (dump_file, ", "); + else + break; + } + fprintf (dump_file, "}\n"); +} + + +/* Pushes the given bit to the end of the bit vector. */ + +value_bit ** +value::push (value_bit *elem) +{ + return number.quick_push (elem); +} + + +/* Destructor for value. */ + +value::~value () +{ + free_bits (); + number.release (); +} + + +/* Removes given sequence of bits. */ + +void +value::free_bits () +{ + if (!number.exists ()) + return; + + for (size_t i = 0; i < number.length (); i++) + { + delete number[i]; + number[i] = nullptr; + } +} + + +/* For the given value_bit, iterates over its expression tree, complements + those bit which came from the given origin. */ + +value_bit * +state::complement_bits_with_origin (value_bit *root, tree origin) +{ + /* Be careful. This function doesn't make a full copy of the bit. */ + if (!is_a (root)) + { + if (is_a (root) + && as_a (root)->get_origin () == origin) + root = new bit_complement_expression (root); + + return root; + } + + bit_expression *expr_root = as_a (root); + hash_set nodes_to_consider; + nodes_to_consider.add (expr_root); + hash_map node_to_parent; + node_to_parent.put (expr_root, nullptr); + + /* Traversing expression tree. */ + while (!nodes_to_consider.is_empty ()) + { + value_bit *cur_element = *nodes_to_consider.begin (); + nodes_to_consider.remove (cur_element); + + if (is_a (cur_element)) + { + if (as_a (cur_element)->get_origin () != origin) + continue; + + bit_expression *parent + = as_a (*node_to_parent.get (cur_element)); + if (is_a (parent)) + { + value_bit *parent_of_parent = *node_to_parent.get (parent); + if (parent_of_parent) + { + bit_expression *parent_of_parent_expr + = as_a (parent_of_parent); + parent->set_right (nullptr); + delete parent; + parent_of_parent_expr->get_left () == parent + ? parent_of_parent_expr->set_left (cur_element) + : parent_of_parent_expr->set_right (cur_element); + } + else + { + /* Parent is our root. */ + as_a (root)->set_right (nullptr); + delete root; + root = cur_element; + } + } + else + { + value_bit* new_bit = new bit_complement_expression (cur_element); + parent->get_left () == cur_element ? parent->set_left (new_bit) + : parent->set_right (new_bit); + } + continue; + } + + bit_expression* cur_elem_expr = as_a (cur_element); + value_bit *left = cur_elem_expr->get_left (); + value_bit *right = cur_elem_expr->get_right (); + if (left != nullptr && !is_a (left)) + { + nodes_to_consider.add (left); + node_to_parent.put (left, cur_element); + } + + if (right != nullptr && !is_a (right)) + { + nodes_to_consider.add (right); + node_to_parent.put (right, cur_element); + } + } + + return root; +} + + +/* Iterates over every bit of the given value and complements their + expression trees' those bits, that came from the given origin. */ + +void +state::complement_val_bits_with_origin (value *val, tree origin) +{ + for (size_t i = 0; i < val->length (); i++) + { + (*val)[i] = complement_bits_with_origin ((*val)[i], origin); + } +} + + +/* Complements all bits of all values that came from the given origin. */ + +void +state::complement_all_vars_bits_with_origin (tree origin) +{ + for (auto iter = var_states.begin (); iter != var_states.end (); ++iter) + { + complement_val_bits_with_origin (&(*iter).second, origin); + } +} + + +/* Complements all bits with the given origin of all added conditions. */ + +void +state::complement_conditions_with_origin (tree origin) +{ + hash_set updated_conditions; + for (auto iter = conditions.begin (); iter != conditions.end (); ++iter) + updated_conditions.add (as_a ( + complement_bits_with_origin (*iter, origin))); + + conditions.empty (); + for (auto iter = updated_conditions.begin (); + iter != updated_conditions.end (); ++iter) + conditions.add (*iter); +} + + +/* Complements all bits with the given origin of all values + and added conditions. */ + +void +state::complement_state_with_origin (tree origin) +{ + complement_all_vars_bits_with_origin (origin); + complement_conditions_with_origin (origin); +} + + +/* Performs the specified operation on passed variables. */ + +bool +state::do_operation (tree_code op_code, tree arg1, tree arg2, tree dest) +{ + switch (op_code) + { + case BIT_NOT_EXPR: + return do_complement (arg1, dest); + case NOP_EXPR: + case SSA_NAME: + case VAR_DECL: + case INTEGER_CST: + return do_assign (arg1, dest); + case LSHIFT_EXPR: + return do_binary_operation (arg1, arg2, dest, &state::do_shift_left); + case RSHIFT_EXPR: + return do_binary_operation (arg1, arg2, dest, &state::do_shift_right); + case BIT_AND_EXPR: + return do_binary_operation (arg1, arg2, dest, &state::do_and); + case BIT_IOR_EXPR: + return do_binary_operation (arg1, arg2, dest, &state::do_or); + case BIT_XOR_EXPR: + return do_binary_operation (arg1, arg2, dest, &state::do_xor); + case PLUS_EXPR: + return do_binary_operation (arg1, arg2, dest, &state::do_add); + case MINUS_EXPR: + return do_binary_operation (arg1, arg2, dest, &state::do_sub); + case MULT_EXPR: + return do_binary_operation (arg1, arg2, dest, &state::do_mul); + default: + { + if (dump_file) + fprintf (dump_file, + "Warning, encountered unsupported operation " + "with %s code while executing assign statement!\n", + get_tree_code_name (op_code)); + return false; + } + } +} diff --git a/gcc/sym-exec/sym-exec-state.h b/gcc/sym-exec/sym-exec-state.h new file mode 100644 index 00000000000..e9e68b6478a --- /dev/null +++ b/gcc/sym-exec/sym-exec-state.h @@ -0,0 +1,471 @@ +/* State will store states of variables for a function's single execution path. + It will be used for bit-level symbolic execution to determine values of bits + of function's return value and symbolic marked arguments. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Matevos Mehrabyan + +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 +. */ + + +#ifndef SYM_EXEC_STATE_H +#define SYM_EXEC_STATE_H + +#define MAX_VALUE_SIZE 64 + +#include "sym-exec-expr-is-a-helper.h" + +/* Struct used for representing values. */ + +struct value { + private: + /* bit-vector that represents the value. */ + vec number; + + public: + /* Used for denoting whether the number is unsigned. */ + const bool is_unsigned; + + /* Constructor for value. The first argument is the size of the bit-vector + and the second argument is the sign of the number. */ + value (unsigned size, bool is_unsigned); + + /* Copy constructor for value. */ + value (const value &other); + + /* Pushes the given bit to the end of the bit-vector. */ + value_bit **push (value_bit *elem); + + /* Returns pushed bits count. */ + unsigned length () const; + + /* Returns a reference the last bit. */ + value_bit *&last (); + + /* Returns the size in bits. */ + unsigned allocated () const; + + /* Wrapper of vec<..>.exists for the bit-vector. */ + bool exists () const; + + /* Wrapper of vec<..>::operator[] for the bit-vector. */ + value_bit *&operator[] (unsigned i); + + /* Assignment operator. If the specified value's size is smaller, + then 0 constant bit will be assigned to the remaining upper bits. */ + value &operator= (const value &other); + + /* Wrapper of vec<..>::operator[] const for the bit-vector. */ + value_bit *operator[] (unsigned i) const; + + /* Destructor for value. */ + ~value (); + + /* Removes given sequence of bits. */ + void free_bits (); +}; + + +/* Stores states of variables' values on bit-level. */ + +class state { + typedef void (state::*binary_func) (value *arg1, value *arg2, tree dest); + typedef value_bit *(*bit_func) (value_bit *bit1, value_bit *bit2); + typedef value_bit *(*bit_func3) (value_bit *var1, value_bit *var2, + value_bit **var3); + typedef void (state::*binary_cond_func) (value *arg1, value *arg2); + + private: + + /* Here is stored values by bits of each variable. */ + hash_map var_states; + + /* Here is stored conditions of symbolic bits. */ + hash_set conditions; + + /* The result of last added condition. */ + condition_status last_cond_status = condition_status::CS_NO_COND; + + /* Creates value for given constant tree. */ + static value create_val_for_const (tree var, size_t size); + + /* Checks if sizes of arguments and destination are compatible. */ + bool check_args_compatibility (tree arg1, tree arg2, tree dest); + + /* Adds equality condition for two values. */ + void add_equal_cond (value *arg1, value *arg2); + + /* Adds not equal condition for two values. */ + void add_not_equal_cond (value *arg1, value *arg2); + + /* Adds greater than condition for two values. */ + void add_greater_than_cond (value *arg1, value *arg2); + + /* Adds less than condition for two values. */ + void add_less_than_cond (value *arg1, value *arg2); + + /* Adds greater or equal condition for two values. */ + void add_greater_or_equal_cond (value *arg1, value *arg2); + + /* Adds less or equal condition for two values. */ + void add_less_or_equal_cond (value *arg1, value *arg2); + + /* Does preprocessing and postprocessing for condition adding. + Handles value creation for constants and their removement in the end. */ + bool add_binary_cond (tree arg1, tree arg2, binary_cond_func cond_func); + + /* Constructs expression trees of greater than condition for given values. */ + bit_expression *construct_great_than_cond (value *arg1, value *arg2); + + /* Constructs expression trees of less than condition for given values. */ + bit_expression *construct_less_than_cond (value *arg1, value *arg2); + + /* Constructs expression trees of equal condition for given values. */ + bit_expression *construct_equal_cond (value *arg1, value *arg2); + + /* A wrapper for operations on two bits. + Operation and operands are passed as arguments. */ + static value_bit *operate_bits (bit_func bit_op, value_bit *bit1, + value_bit *bit2, value_bit **bit3); + + /* A wrapper for operations on three bits. + Operation and operands are passed as arguments. */ + static value_bit *operate_bits (bit_func3 bit_op, value_bit *bit1, + value_bit *bit2, value_bit **bit3); + + /* Performs the given operation on passed arguments. + The result is stored in dest. */ + template + void operate (value *arg1, value *arg2, value_bit **bit_arg, tree dest, + func bit_op); + + /* Does preprocessing and postprocessing for expressions with tree operands. + Handles value creation for constant and their removement in the end. */ + bool do_binary_operation (tree arg1, tree arg2, tree dest, + binary_func bin_func); + + /* Performs AND operation on given values. The result is stored in dest. */ + void do_and (value *arg1, value *arg2, tree dest); + + /* Performs OR operation on given values. The result is stored in dest. */ + void do_or (value *arg1, value *arg2, tree dest); + + /* Performs XOR operation on given values. The result is stored in dest. */ + void do_xor (value *arg1, value *arg2, tree dest); + + /* Performs shift right operation on given values. + The result is stored in dest. */ + void do_shift_right (value *arg1, value *arg2, tree dest); + + /* Performs shift left operation on given values. + The result is stored in dest. */ + void do_shift_left (value *arg1, value *arg2, tree dest); + + /* Adds given values. The result is stored in dest. */ + void do_add (value *arg1, value *arg2, tree dest); + + /* Subtracks second value from the first. The result is stored in dest. */ + void do_sub (value *arg1, value *arg2, tree dest); + + /* Performs AND operation on two bits. */ + static value_bit *and_two_bits (value_bit *arg1, value_bit *arg2); + + /* ANDs every bit of the value with var_bit, stroes the result in var1. */ + void and_number_bit (value *var1, value_bit *var_bit); + + /* Multiplies given values. The result is stored in dest. */ + void do_mul (value *arg1, value *arg2, tree dest); + + /* Performs AND operation for 2 symbolic_bit operands. */ + static value_bit *and_sym_bits (const value_bit *var1, + const value_bit *var2); + + /* Performs AND operation for a symbolic_bit and const_bit operands. */ + static value_bit *and_var_const (const value_bit *var1, + const bit *const_bit); + + /* Performs AND operation for 2 constant bit operands. */ + static bit *and_const_bits (const bit *const_bit1, const bit *const_bit2); + + /* Performs OR operation on two bits. */ + static value_bit *or_two_bits (value_bit *arg1_bit, value_bit *arg2_bit); + + /* Performs OR operation for 2 symbolic_bit operands. */ + static value_bit *or_sym_bits (const value_bit *var1, + const value_bit *var2); + + /* Performs OR operation for a symbolic_bit and a constant bit operands. */ + static value_bit *or_var_const (const value_bit *var1, + const bit *const_bit); + + /* Performs OR operation for 2 constant bit operands. */ + static bit *or_const_bits (const bit *const_bit1, const bit *const_bit2); + + /* Performs complement operation on a bit. */ + static value_bit *complement_a_bit (value_bit *var); + + /* Performs NOT operation for constant bit. */ + static bit *complement_const_bit (const bit *const_bit); + + /* Performs NOT operation for symbolic_bit. */ + static value_bit *complement_sym_bit (const value_bit *var); + + /* Performs XOR operation on two bits. */ + static value_bit *xor_two_bits (value_bit *var1, value_bit *var2); + + /* Performs XOR operation for 2 symbolic_bit operands. */ + static value_bit *xor_sym_bits (const value_bit *var1, + const value_bit *var2); + + /* Performs XOR operation for 2 constant bit operands. */ + static bit *xor_const_bits (const bit *const_bit1, const bit *const_bit2); + + /* Performs XOR operation for a symbolic_bit and const_bit operands. */ + static value_bit *xor_var_const (const value_bit *var, + const bit *const_bit); + + /* Shift_right operation. Case: var2 is a symbolic value. */ + static value_bit *shift_right_sym_bits (value_bit *var1, value_bit *var2); + + /* Shift_left operation. Case: var2 is a symbolic value. */ + static value_bit *shift_left_sym_bits (value_bit *var1, value_bit *var2); + + /* Shifts var right by size of shift_value. */ + value *shift_right_by_const (value *var, size_t shift_value); + + /* Return node which has a const bit child. Traversal is done based + on safe branching. */ + static void get_parent_with_const_child (value_bit *root, + bit_expression *&parent, + bit_expression *&parent_of_parent); + + /* Checks whether state for variable with specified name already + exists or not. */ + bool is_declared (tree var); + + /* Declares given variable if it has not been declared yet. */ + void declare_if_needed (tree var, size_t size); + + /* Shifts number left by size of shift_value. */ + value *shift_left_by_const (const value *number, size_t shift_value); + + /* Adds two bits and carry value. + Resturn result and stores new carry bit in "carry". */ + static value_bit *full_adder (value_bit *var1, value_bit *var2, + value_bit **carry); + + /* Returns the additive inverse of the given number. */ + value *additive_inverse (const value *number); + + /* Adds two values, stores the result in the first one. */ + void add_numbers (value *var1, const value *var2); + + /* Make a copy of given bits. */ + static vec *make_copy (vec *bits); + + public: + /* Default constructor for state. */ + state () = default; + + /* Destructor for state. */ + ~state (); + + /* Adds an empty state for the given variable. */ + bool decl_var (tree name, unsigned size); + + /* Copy constructor for state. It copies all variables and conditions + of the given state. */ + state (const state &s); + + /* Adds the given variable to state. */ + bool add_var_state (tree var, value *state); + + /* Remove all states from the states' vector. */ + static void remove_states (vec *states); + + /* Remove all states from the states' vector and release the vector. */ + static void clear_states (vec *states); + + /* Removes all variables added to the state. */ + void clear_var_states (); + + /* Removes all conditions added to the state. */ + void clear_conditions (); + + /* Adds the given condition to the state. */ + bool add_condition (bit_expression *cond); + + /* Bulk add the given conditions to the state. */ + bool bulk_add_conditions (const hash_set &conds); + + /* Get value of the given variable. */ + value *get_value (tree var); + + /* Get the value of the tree, which is in the beginning of the var_states. */ + value *get_first_value (); + + /* Returns the list of conditions in the state. */ + const hash_set &get_conditions (); + + /* Adds a variable with unknown value to state. Such variables are + represented as sequence of symbolic bits. */ + bool make_symbolic (tree var, unsigned size); + + /* Returns size of the given variable. */ + unsigned get_var_size (tree var); + + /* Prints the given value. */ + static void print_value (value *var); + + /* Prints added conditions. */ + void print_conditions (); + + /* Returns the number represented by the value. */ + static unsigned HOST_WIDE_INT + make_number (const value *var); + + /* Checks if all bits of the given value have constant bit type. */ + static bool is_bit_vector (const value *var); + + /* Performs the specified operation on passed variables. */ + bool do_operation (tree_code op_code, tree arg1, tree arg2, tree dest); + + /* Does Assignment. */ + bool do_assign (tree arg, tree dest); + + /* Assigns pow 2 value. */ + bool do_assign_pow2 (tree dest, unsigned pow); + + /* Negates given variable. */ + bool do_complement (tree arg, tree dest); + + /* Adds EQUAL condition of given variables to state. */ + bool add_equal_cond (tree arg1, tree arg2); + + /* Adds NOT EQUAL condition of given variables to state. */ + bool add_not_equal_cond (tree arg1, tree arg2); + + /* Adds GREATER THAN condition of given variables to state. */ + bool add_greater_than_cond (tree arg1, tree arg2); + + /* Adds LESS THAN condition of given variables to state. */ + bool add_less_than_cond (tree arg1, tree arg2); + + /* Adds GREATER OR EQUAL condition of given variables to state. */ + bool add_greater_or_equal_cond (tree arg1, tree arg2); + + /* Adds LESS OR EQUAL condition of given variables to state. */ + bool add_less_or_equal_cond (tree arg1, tree arg2); + + /* Adds a bool condition to state. */ + bool add_bool_cond (tree arg); + + /* Checks whether the given two constant values are equal. */ + static bool check_const_value_equality (value *arg1, value *arg2); + + /* Checks whether the given two constant values are not equal. */ + static bool check_const_value_are_not_equal (value *arg1, value *arg2); + + /* Checks whether the first given constant value + is greater than the second one. */ + static bool check_const_value_is_greater_than (value *arg1, value *arg2); + + /* Checks whether the first given constant value + is less than the second one. */ + static bool check_const_value_is_less_than (value *arg1, value *arg2); + + /* For the given value_bit, iterates over its expression tree, complements + those bit which came from the given origin. */ + static value_bit *complement_bits_with_origin (value_bit *root, tree origin); + + /* Iterates over every bit of the given value and complements their + expression trees' those bits, that came from the given origin. */ + static void complement_val_bits_with_origin (value *val, tree origin); + + /* Complements all bits of all values that came from the given origin. */ + void complement_all_vars_bits_with_origin (tree origin); + + /* Complements all bits with the given origin of all added conditions. */ + void complement_conditions_with_origin (tree origin); + + /* Complements all bits with the given origin of all values + and added conditions. */ + void complement_state_with_origin (tree origin); + + /* Returns status of last added condition. */ + condition_status get_last_cond_status (); +}; + + +/* Returns the minimum of A, B, C. */ + +size_t min (size_t a, size_t b, size_t c); + + +/* Performs the given operation on passed arguments. + The result is stored in dest. */ + +template +void +state::operate (value *arg1, value *arg2, value_bit **bit_arg, tree dest, + func bit_op) +{ + value *dest_var = var_states.get (dest); + size_t min_iter = min (arg1->length (), arg2->length (), dest_var->length ()); + + size_t i = 0; + for (; i < min_iter; i++) + { + value_bit *temp = (*var_states.get (dest))[i]; + (*var_states.get (dest))[i] = operate_bits (bit_op, (*arg1)[i], + (*arg2)[i], bit_arg); + delete temp; + } + + if (i >= dest_var->length ()) + return; + + value *biggest = arg1; + value_bit *sign_bit = (*arg2)[i - 1]; + if (arg2->length () > arg1->length ()) + { + biggest = arg2; + sign_bit = (*arg1)[i - 1]; + } + + min_iter = min (biggest->length (), dest_var->length (), dest_var->length ()); + for (; i < min_iter; i++) + { + value_bit *temp = (*var_states.get (dest))[i]; + (*var_states.get (dest))[i] = operate_bits (bit_op, (*biggest)[i], + sign_bit, bit_arg); + delete temp; + } + + if (i >= dest_var->length ()) + return; + + sign_bit = (*biggest)[i - 1]; + for (; i < dest_var->length (); i++) + { + value_bit *temp = (*var_states.get (dest))[i]; + (*var_states.get (dest))[i] = operate_bits (bit_op, sign_bit, sign_bit, + bit_arg); + delete temp; + } +} + +#endif /* SYM_EXEC_STATE_H. */ -- 2.25.1 From patchwork Sat Nov 9 19:45:03 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Mariam Arutunian X-Patchwork-Id: 2009137 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=C7j0unBc; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Xm5sD4dfXz1xyp for ; Sun, 10 Nov 2024 06:46:08 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D771F3858C62 for ; Sat, 9 Nov 2024 19:46:06 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-qv1-xf30.google.com (mail-qv1-xf30.google.com [IPv6:2607:f8b0:4864:20::f30]) by sourceware.org (Postfix) with ESMTPS id 5366E3858D28 for ; Sat, 9 Nov 2024 19:45:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5366E3858D28 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 5366E3858D28 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::f30 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731181531; cv=none; b=bt5b87h0hLy/2QdXHYjnGYXyMD5BTJSEYF3kEHqi5p/+xt2jul095vuKswW0vlZRtk3OAjR/BXh+vqp1HlwQtyUCHYYwSlWwxVhWKa7QrxngJfNd8iu+Jp2pccICprRl9cz+V9RzMr44rCQEGw7MhFgrj+vBYy5PYhp14snJZLs= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731181531; c=relaxed/simple; bh=nQCVxHnjuaqDH8GgkF/jZ4NUa4T6ktrSVr6drZ80Ueo=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=u9TWvMYJoXrlfT/dwNIlv9iJ0zdPRdUSAncVeefTqZMvknhEZgZ5kVhhsEVZrC5U0nXVm7jXPADTm1u/rUDW8WGNoXF2NiKIWhBWT7kJDyeXeuQIRS+0/mjEPTyiU+cxXCcaYyXWDMsWCg4lUiBRcoc7EOEtw7y6S2YnV7nh10A= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-qv1-xf30.google.com with SMTP id 6a1803df08f44-6cbf347dc66so21076736d6.3 for ; Sat, 09 Nov 2024 11:45:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731181517; x=1731786317; darn=gcc.gnu.org; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=4GezzzRXwsa6q7Ze/oqB/I9naSu7UzpX0rN2cPY4wJg=; b=C7j0unBcF1NAxyQX3EjiErgXvVWSl2tTjJ6BQIYML/t6BnaambomQM/0WqEc1Sq30E SdP0wsp2cnBSkT55EbqOqENaLansOsq52GQRasWfrKhGkdYIvU2qijF9o2A0EeRLxMDp PIWoHyByPQp+6c8VYMxTBSas8jFw7fsytnQNxAimiM2Uhjv7UjL9detQ7W+i94HWi66t SVH/7FtIqYs4vc2Or7ZB2r+i3smvubajSIh6vp67ThuLwM6d/UGoZDiOtJFNPB298WsV sc5M70Wo9GzEj7J0lU5LENjPG6D3FvP2JL93M7qF+HmQY/1XUjlSMA7dYobOsT05PVQh DmVw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731181517; x=1731786317; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=4GezzzRXwsa6q7Ze/oqB/I9naSu7UzpX0rN2cPY4wJg=; b=OyBgOvYIUyl7OopPGsG7MG1LOeMevk/2SHh/xc0ta/iAtCwzwTeuDK2HrMxTEyGMXw 5QsRupq8TO8MEEH1sX+LltC0iCyEfmjj3Loe+iBpklxDZfiLtcVgEfENXfX9AysMbEcf MOvVOdnKD/eMW6s9bKF8nkdlTVeo06usHCqA12Dkd18lDsymB7sMcKYy+vkcelvJtO0P 9V2M83K0+gRXnX7Q5lx96J3tczVPoHikal/KUI9z0nv7+h7iNI4xVmofc5mPwiJFbSVC Aaw6H67BH0rIPEq8fWorZXKBXd51qSCzmpGBztXDcYZRN4ILRzklaAG7uJ3Di3MKtLnP eh6Q== X-Gm-Message-State: AOJu0YxIO3fg2JlsShMQUaUNXnhcA1vxrrJvlCDC8eNpxvylb+Z812y2 iDJKhKJwkXsMJ6yAQW2HtHoL8dL/SIbhhPqr69NxbcInhmUA4X7hFjsPS/gfWZhWyzO/eK5GmWf 9UAGMHOd3y/smp80y5Ucsda7Eup203+Cj X-Google-Smtp-Source: AGHT+IHo8B0+uTVo2jzhcSQxDpe17Q/v2nbSjgZ0Hz7XPIuHjSB2GUmQvLCrEDQXRvKCdhyFe9A+fRXagw7yXbarvkc= X-Received: by 2002:a05:6214:498b:b0:6cb:6089:eb83 with SMTP id 6a1803df08f44-6d39e145db9mr90883486d6.28.1731181517194; Sat, 09 Nov 2024 11:45:17 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Mariam Arutunian Date: Sat, 9 Nov 2024 23:45:03 +0400 Message-ID: Subject: [RFC/RFA] [PATCH v7 10/12] Verify detected CRC loop with symbolic execution and LFSR matching. To: GCC Patches , Jeff Law X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Symbolically execute potential CRC loops and check whether the loop actually calculates CRC (uses LFSR matching). Calculated CRC and created LFSR are compared on each iteration of the potential CRC loop. gcc/ * Makefile.in (OBJS): Add crc-verification.o. * crc-verification.cc: New file. * crc-verification.h: New file. * gimple-crc-optimization.cc (loop_calculates_crc): New function. (is_output_crc): Likewise. (swap_crc_and_data_if_needed): Likewise. (validate_crc_and_data): Likewise. (optimize_crc_loop): Likewise. (get_output_phi): Likewise. (execute): Add check whether potential CRC loop calculates CRC. gcc/sym-exec/ * sym-exec-state.cc (create_reversed_lfsr): New function. (create_forward_lfsr): Likewise. (last_set_bit): Likewise. (create_lfsr): Likewise. * sym-exec-state.h (is_bit_vector): Reorder, make the function public and static. (create_reversed_lfsr): New static function declaration. (create_forward_lfsr): New static function declaration. Signed-off-by: Mariam Arutunian Mentored-by: Jeff Law --- gcc/Makefile.in | 1 + gcc/crc-verification.cc | 1299 ++++++++++++++++++++++++++++++++ gcc/crc-verification.h | 162 ++++ gcc/gimple-crc-optimization.cc | 327 +++++++- gcc/sym-exec/sym-exec-state.cc | 101 +++ gcc/sym-exec/sym-exec-state.h | 11 + 6 files changed, 1899 insertions(+), 2 deletions(-) create mode 100644 gcc/crc-verification.cc create mode 100644 gcc/crc-verification.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 6eab34d62bb..6b8a37a180c 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1717,6 +1717,7 @@ OBJS = \ tree-iterator.o \ tree-logical-location.o \ tree-loop-distribution.o \ + crc-verification.o \ gimple-crc-optimization.o \ sym-exec/sym-exec-expression.o \ sym-exec/sym-exec-state.o \ diff --git a/gcc/crc-verification.cc b/gcc/crc-verification.cc new file mode 100644 index 00000000000..19d53303f69 --- /dev/null +++ b/gcc/crc-verification.cc @@ -0,0 +1,1299 @@ +/* Execute symbolically all paths of the loop. + Calculate the value of the polynomial by executing loop with real values to + create LFSR state. + After each iteration check that final states of calculated CRC values match + determined LFSR. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Mariam Arutunian + +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 "crc-verification.h" +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "cfganal.h" +#include "tree-ssa-loop.h" + +/* Check whether defined variable is used outside the loop, only + CRC's definition is allowed to be used outside the loop. */ + +bool +crc_symbolic_execution::is_used_outside_the_loop (tree def) +{ + imm_use_iterator imm_iter; + gimple *use_stmt; + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) + { + if (!flow_bb_inside_loop_p (m_crc_loop, use_stmt->bb)) + { + if (is_a (use_stmt) + && as_a (use_stmt) == m_output_crc) + return false; + if (dump_file) + fprintf (dump_file, "Defined variable is used outside the loop.\n"); + return true; + } + } + return false; +} + +/* Calculate value of the rhs operation of GS assigment statement + and assign it to lhs variable. */ + +bool +crc_symbolic_execution::execute_assign_statement (const gassign *gs) +{ + enum tree_code rhs_code = gimple_assign_rhs_code (gs); + tree lhs = gimple_assign_lhs (gs); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "lhs type : %s \n", + get_tree_code_name (TREE_CODE (lhs))); + + /* This will filter some normal cases too. Ex. usage of array. */ + if (TREE_CODE (lhs) != SSA_NAME) + return false; + + /* Check uses only when m_output_crc is known. */ + if (m_output_crc) + if (is_used_outside_the_loop (lhs)) + return false; + + if (gimple_num_ops (gs) != 2 && gimple_num_ops (gs) != 3) + { + if (dump_file) + fprintf (dump_file, + "Warning, encountered unsupported operation, " + "with %s code while executing assign statement!\n", + get_tree_code_name (rhs_code)); + return false; + } + + tree op1 = gimple_assign_rhs1 (gs); + tree op2 = nullptr; + + if (gimple_num_ops (gs) == 3) + op2 = gimple_assign_rhs2 (gs); + + state *current_state = m_states.last (); + return current_state->do_operation (rhs_code, op1, op2, lhs); +} + +/* Add E edge into the STACK if it doesn't have an immediate + successor edge going to the loop header. + + When loop counter is checked in the if condition, + we mustn't continue on real path as we want to stop the execution before + the second iteration. */ + +bool +crc_symbolic_execution::add_edge (edge e, auto_vec &stack) +{ + if (EDGE_COUNT (e->dest->succs) == 0) + return false; + + edge next_bb_edge = EDGE_SUCC (e->dest, 0); + if (next_bb_edge && next_bb_edge->dest == m_crc_loop->header) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Completed one iteration. " + "Won't iterate loop once more, yet.\n"); + + return keep_states (); + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Adding the edge into the stack.\n"); + + /* If the result of the condition is true/false, + continue execution only by the true/false branch. */ + stack.quick_push (e); + } + return true; +} + +/* Add next basic blocks of the conditional block COND_BB + for the execution path into the STACK. + If the condition depends on symbolic values, keep both edges. + If the condition is true, keep true edge, else - false edge. + Returns true if addition succeeds. Otherwise - false. */ + +bool +crc_symbolic_execution::add_next_bbs (basic_block cond_bb, + state *new_branch_state, + auto_vec &stack) +{ + edge true_edge; + edge false_edge; + extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge); + + /* When the condition depends on symbolic values. */ + if (new_branch_state->get_last_cond_status () == CS_SYM) + { + /* Supported CRC cases may have only two states. */ + if (m_states.length () == 2) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Going to add a new state, " + "but there's already two states.\n"); + return false; + } + /* Add true branch's state into the states. + False branch's state will be kept in the current state. */ + m_states.quick_push (new_branch_state); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Adding true and false edges into the stack.\n"); + + /* Add outgoing edges to the stack. */ + stack.quick_push (false_edge); + stack.quick_push (true_edge); + + return true; + } + /* When the condition evaluates to true. */ + else if (new_branch_state->get_last_cond_status () == CS_TRUE) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Condition is true.\n"); + add_edge (true_edge, stack); + } + /* When the condition evaluates to false. */ + else if (new_branch_state->get_last_cond_status () == CS_FALSE) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Condition is false.\n"); + add_edge (false_edge, stack); + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Something went wrong " + "during handling conditional statement.\n"); + return false; + } + + /* When we continue execution of only one path, + there's no need of new state. */ + delete new_branch_state; + return true; +} + +/* Add conditions depending on symbolic variables in the states. + + Keep conditions of each branch execution in its state. + Ex. + if (a == 0) // a's value is unknown + + new_branch_state.keep (a==0) + current_state.keep (a!=0) + + The condition is kept in the bit level. + For ex. + If a's size is 8 and its value is {symb_a, 0, 0, 0, 0, 0, 0, 0}, + then for a == 0 we'll have symb_a == 0 condition. */ + +bool +crc_symbolic_execution::add_condition (const gcond *cond, + state *current_state, + state *new_branch_state) +{ + tree lhs = gimple_cond_lhs (cond); + tree rhs = gimple_cond_rhs (cond); + switch (gimple_cond_code (cond)) + { + case EQ_EXPR: + { + new_branch_state->add_equal_cond (lhs, rhs); + if (new_branch_state->get_last_cond_status () == CS_SYM) + current_state->add_not_equal_cond (lhs, rhs); + return true; + } + case NE_EXPR: + { + new_branch_state->add_not_equal_cond (lhs, rhs); + if (new_branch_state->get_last_cond_status () == CS_SYM) + current_state->add_equal_cond (lhs, rhs); + return true; + } + case GT_EXPR: + { + new_branch_state->add_greater_than_cond (lhs, rhs); + if (new_branch_state->get_last_cond_status () == CS_SYM) + current_state->add_less_or_equal_cond (lhs, rhs); + return true; + } + case LT_EXPR: + { + new_branch_state->add_less_than_cond (lhs, rhs); + if (new_branch_state->get_last_cond_status () == CS_SYM) + current_state->add_greater_or_equal_cond (lhs, rhs); + return true; + } + case GE_EXPR: + { + new_branch_state->add_greater_or_equal_cond (lhs, rhs); + if (new_branch_state->get_last_cond_status () == CS_SYM) + current_state->add_less_than_cond (lhs, rhs); + return true; + } + case LE_EXPR: + { + new_branch_state->add_less_or_equal_cond (lhs, rhs); + if (new_branch_state->get_last_cond_status () == CS_SYM) + current_state->add_greater_than_cond (lhs, rhs); + return true; + } + default: + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Unsupported condition.\n"); + return false; + } + } +} + +/* Create new states for true and false branches. + Keep conditions in new created states. */ + +bool +crc_symbolic_execution::resolve_condition (const gcond *cond, + auto_vec &stack) +{ + state *current_state = m_states.last (); + state *new_branch_state = new state (*current_state); + + /* Create new states and for true and false branches keep corresponding + conditions. */ + if (!add_condition (cond, current_state, new_branch_state)) + return false; + + /* Add true and false edges to the stack. */ + return add_next_bbs (cond->bb, new_branch_state, stack); +} + +/* If final states are less than two, add new FINAL_STATE and return true. + Otherwise, return false. + Supported CRC cases may not have more than two final states. */ +bool crc_symbolic_execution::add_final_state (state *final_state) +{ + if (m_final_states.length () < 2) + m_final_states.quick_push (final_state); + else + { + if (dump_file) + fprintf (dump_file, + "There are already two final states\n"); + return false; + } + return true; +} + +/* Keep the state of the executed path in final states. */ + +bool crc_symbolic_execution::keep_states () +{ + if (m_states.is_empty ()) + return false; + + if (!add_final_state (m_states.last ())) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Couldn't add final state.\n"); + return false; + } + + m_states.pop (); + return true; +} + +/* Execute gimple statements of BB. + Keeping values of variables in the state. */ + +bool +crc_symbolic_execution::execute_bb_gimple_statements (basic_block bb, + auto_vec &stack) +{ + for (gimple_stmt_iterator bsi = gsi_start_bb (bb); + !gsi_end_p (bsi); gsi_next (&bsi)) + { + gimple *gs = gsi_stmt (bsi); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Executing "); + print_gimple_stmt (dump_file, gs, dump_flags); + } + switch (gimple_code (gs)) + { + case GIMPLE_ASSIGN: + { + if (!execute_assign_statement (as_a (gs))) + return false; + break; + } + case GIMPLE_COND: + { + return resolve_condition (as_a (gs), stack); + } + /* Just skip debug statements. */ + case GIMPLE_DEBUG: + break; + default: + { + if (dump_file) + fprintf (dump_file, + "Warning, encountered unsupported statement, " + "while executing gimple statements!\n"); + return false; + } + } + } + + /* Add each outgoing edge of the current block to the stack, + despite the edges going to the loop header. + This code isn't reachable if the last statement of the basic block + is a conditional statement or return statement. + Those cases are handled separately. + We mustn't encounter edges going to the CRC loop header. */ + + edge out_edge; + edge_iterator ei; + FOR_EACH_EDGE (out_edge, ei, bb->succs) + if (out_edge->dest != m_crc_loop->header) + stack.quick_push (out_edge); + else + return false; + + return true; +} + +/* Assign values of phi instruction to its result. + Keep updated values in the state. */ + +bool +crc_symbolic_execution::execute_bb_phi_statements (basic_block bb, + edge incoming_edge) +{ + for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + tree lhs = gimple_phi_result (phi); + + /* Check uses only when m_output_crc is known. */ + if (m_output_crc) + if (is_used_outside_the_loop (lhs)) + return false; + + /* Don't consider virtual operands. */ + if (virtual_operand_p (lhs)) + continue; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Determining the value " + "for the following phi.\n"); + print_gimple_stmt (dump_file, phi, dump_flags); + } + + tree rhs = PHI_ARG_DEF_FROM_EDGE (phi, incoming_edge); + + state *current_state = m_states.last (); + if (!current_state->do_operation (VAR_DECL, rhs, nullptr, lhs)) + return false; + } + return true; +} + +/* Execute all statements of BB. + Keeping values of variables in the state. */ + +bool +crc_symbolic_execution::execute_bb_statements (basic_block bb, + edge incoming_edge, + auto_vec &stack) +{ + if (!execute_bb_phi_statements (bb, incoming_edge)) + return false; + + return execute_bb_gimple_statements (bb, stack); +} + +/* If the phi statements' result variables have initial constant value in the + beginning of the loop, initialize those variables. */ + +void +assign_known_vals_to_header_phis (state *state, class loop *crc_loop) +{ + basic_block bb = crc_loop->header; + for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) + { + + gphi *phi = gsi.phi (); + tree lhs = gimple_phi_result (phi); + + /* Don't consider virtual operands. */ + if (virtual_operand_p (lhs)) + continue; + + tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi, + loop_preheader_edge (crc_loop)); + if (TREE_CODE (inital_val) == INTEGER_CST) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "First value of phi is a constant, " + "assigning the number to "); + print_generic_expr (dump_file, lhs, dump_flags); + fprintf (dump_file, " variable.\n"); + } + state->do_operation (VAR_DECL, inital_val, + nullptr, lhs); + } + } +} + +/* If the phi statements' result variables have initial constant value in the + beginning of the loop, initialize those variables with + the value calculated during the previous iteration. */ + +bool +assign_calc_vals_to_header_phis (const vec &prev_states, + state *curr_state, + class loop *crc_loop) +{ + basic_block bb = crc_loop->header; + for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + tree lhs = gimple_phi_result (phi); + + /* Don't consider virtual operands. */ + if (virtual_operand_p (lhs)) + continue; + tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi, + loop_preheader_edge (crc_loop)); + if (TREE_CODE (inital_val) == INTEGER_CST) + { + tree input_tree = PHI_ARG_DEF_FROM_EDGE (phi, + loop_latch_edge (crc_loop)); + value * val_st1 = prev_states[0]->get_value (input_tree), + *val_st2 = prev_states[1]->get_value (input_tree); + if (!state::is_bit_vector (val_st1) + || !state::is_bit_vector (val_st2)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "The calculated values of "); + print_generic_expr (dump_file, input_tree, dump_flags); + fprintf (dump_file, " variable is not constant.\n"); + } + return false; + } + else if (!state::check_const_value_equality (val_st1, val_st2)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "The calculated values of "); + print_generic_expr (dump_file, input_tree, dump_flags); + fprintf (dump_file, " variable is different in the previous " + "iteration paths.\n"); + } + return false; + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Assigning calculated number to "); + print_generic_expr (dump_file, lhs, dump_flags); + fprintf (dump_file, " variable.\n"); + } + unsigned HOST_WIDE_INT calc_number + = state::make_number (val_st1); + tree calc_num_tree = build_int_cstu (TREE_TYPE (lhs), + calc_number); + curr_state->do_operation (VAR_DECL, calc_num_tree, nullptr, lhs); + } + } + } + return true; +} + +/* Create initial state of the CRC_LOOP's header BB variables which have + constant values. + If it is the first iteration of the loop, initialise variables with the + initial values, otherwise initialise the variable with the value calculated + during the previous execution. */ + +state * +crc_symbolic_execution::create_initial_state (class loop *crc_loop) +{ + state *curr_state = new state; + if (!m_final_states.is_empty ()) + { + if (!assign_calc_vals_to_header_phis (m_final_states, curr_state, + crc_loop)) + return nullptr; + state::remove_states (&m_final_states); + } + else + assign_known_vals_to_header_phis (curr_state, crc_loop); + return curr_state; +} + +/* Symbolically execute the CRC loop, doing one iteration. */ + +bool +crc_symbolic_execution::symb_execute_crc_loop () +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\n\nExecuting the loop with symbolic values.\n\n"); + + state *curr_state = create_initial_state (m_crc_loop); + if (!curr_state) + return false; + + m_states.quick_push (curr_state); + + auto_vec stack (m_crc_loop->num_nodes); + + basic_block header_bb = m_crc_loop->header; + if (!execute_bb_gimple_statements (header_bb, stack)) + return false; + + /* Successor BB's are added into the stack + from the execute_bb_gimple_statements function. */ + while (!stack.is_empty ()) + { + /* Look at the edge on the top of the stack. */ + edge e = stack.last (); + stack.pop (); + + /* Get destination block of the edge. */ + basic_block dest_bb = e->dest; + + /* Execute only basic blocks of the m_crc_loop. + At the end of the execution path save states in final states. */ + if (!flow_bb_inside_loop_p (m_crc_loop, dest_bb)) + { + m_is_last_iteration = true; + if (!keep_states ()) + return false; + continue; + } + + /* Execute statements. */ + if (!execute_bb_statements (dest_bb, e, stack)) + return false; + } + return true; +} + +/* Determine which bit of the DATA must be 1. + We assume that last bit must be 1. */ + +unsigned HOST_WIDE_INT +determine_index (tree data, bool is_shift_left) +{ + if (is_shift_left) + /* This won't work correctly in the case when data's size is larger, + but MSB is checked for the middle bit. */ + return tree_to_uhwi (TYPE_SIZE (TREE_TYPE (data))) - 1; + return 0; +} + +/* Assign appropriate values to data, CRC + and other phi results to calculate the polynomial. */ + +void +assign_vals_to_header_phis (state *polynomial_state, class loop *crc_loop, + gphi *crc_phi, gphi *data_phi, + bool is_shift_left) +{ + basic_block bb = crc_loop->header; + for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) + { + + gphi *phi = gsi.phi (); + tree lhs = gimple_phi_result (phi); + + /* Don't consider virtual operands. */ + if (virtual_operand_p (lhs)) + continue; + + if ((data_phi && phi == data_phi) || (!data_phi && phi == crc_phi)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Assigning the required value to "); + print_generic_expr (dump_file, lhs, dump_flags); + fprintf (dump_file, " variable.\n"); + } + polynomial_state->do_assign_pow2 (lhs, + determine_index (lhs, + is_shift_left)); + } + else if (phi == crc_phi) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Assigning 0 value to "); + print_generic_expr (dump_file, lhs, dump_flags); + fprintf (dump_file, " variable.\n"); + } + polynomial_state->do_operation (VAR_DECL, + build_zero_cst (TREE_TYPE (lhs)), + nullptr, lhs); + } + else + { + edge loop_preheader = loop_preheader_edge (crc_loop); + tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader); + if (TREE_CODE (inital_val) == INTEGER_CST) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "First value of phi is a constant, " + "assigning the number to "); + print_generic_expr (dump_file, lhs, dump_flags); + fprintf (dump_file, " variable.\n"); + } + polynomial_state->do_operation (VAR_DECL, inital_val, + nullptr, lhs); + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "First value of phi isn't constant, " + "assigning to "); + print_generic_expr (dump_file, lhs, dump_flags); + fprintf (dump_file, " variable.\n"); + } + polynomial_state->do_operation (VAR_DECL, + build_zero_cst (TREE_TYPE (lhs)), + nullptr, lhs); + } + } + } +} + +/* Execute the loop, which calculates CRC with initial values, + to calculate the polynomial. */ + +bool +crc_symbolic_execution::execute_crc_loop (gphi *crc_phi, + gphi *data_phi, + bool is_shift_left) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\n\nTrying to calculate the polynomial.\n\n"); + + m_states.quick_push (new state); + + basic_block bb = m_crc_loop->header; + assign_vals_to_header_phis (m_states.last (), m_crc_loop, crc_phi, data_phi, + is_shift_left); + + auto_vec stack (m_crc_loop->num_nodes); + + if (!execute_bb_gimple_statements (bb, stack)) + return false; + + /* stack may not be empty. Successor BB's are added into the stack + from the execute_bb_gimple_statements function. */ + while (!stack.is_empty ()) + { + /* Look at the edge on the top of the stack. */ + edge e = stack.last (); + stack.pop (); + + /* Get dest block of the edge. */ + basic_block bb = e->dest; + + /* Execute only basic blocks of the m_crc_loop. */ + if (!flow_bb_inside_loop_p (m_crc_loop, bb)) + continue; + + /* Execute statements. */ + if (!execute_bb_statements (bb, e, stack)) + return false; + } + + if (m_final_states.length () != 1) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "The number of states is not one when executed " + "the loop for calculating the polynomial.\n"); + return false; + } + return true; +} + +/* Return true if all bits of the POLYNOMIAL are constants (0 or 1). + Otherwise return false. */ + +bool +polynomial_is_known (const value *polynomial) +{ + for (size_t i = 0; i < polynomial->length (); i++) + { + if (!is_a ((*polynomial)[i])) + return false; + } + return true; +} + +/* Execute the loop, which is expected to calculate CRC, + to extract polynomial, assigning real numbers to CRC and data. + Returns a pair, first value of the pair is the tree containing + the value of the polynomial, second is the calculated polynomial. + The pair may contain nullptr. */ + +std::pair +crc_symbolic_execution::extract_polynomial (gphi *crc_phi, gphi *data_phi, + tree calculated_crc, + bool is_shift_left) +{ + if (!execute_crc_loop (crc_phi, data_phi, is_shift_left)) + return std::make_pair (nullptr, nullptr); + + if (m_final_states.length () != 1) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "The number of states isn't one " + "after executing the loop.\n"); + return std::make_pair (nullptr, nullptr); + } + state *polynomial_state = m_final_states.last (); + + /* CALCULATED_CRC contains the value of the polynomial + after one iteration of the loop. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Getting the value of "); + print_generic_expr (dump_file, calculated_crc, dump_flags); + fprintf (dump_file, " variable.\n"); + } + + /* Get the value (bit vector) of the tree (it may be the polynomial). */ + value *polynomial = polynomial_state->get_value (calculated_crc); + if (!polynomial) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Polynomial's value is null.\n"); + return std::make_pair (nullptr, nullptr); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + /* Note: It may not be the real polynomial. + If it's a bit reflected CRC, + then to get a real polynomial, + it must be reflected and 1 bit added. */ + fprintf (dump_file, "Polynomial's value is "); + state::print_value (polynomial); + } + + /* Check that polynomial's all bits are constants. */ + if (!polynomial_is_known (polynomial)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Polynomial's value is not constant.\n"); + return std::make_pair (nullptr, nullptr); + } + + return std::make_pair (calculated_crc, polynomial); +} + + +/**************************** LFSR MATCHING *********************************/ + + +/* Return true if CONST_BIT value equals to 1. + Otherwise, return false. */ + +bool +is_one (value_bit *const_bit) +{ + return is_a (const_bit) + && (as_a (const_bit))->get_val () == 1; +} + +/* Return true if BIT is symbolic, + its index is same as LFSR bit's index (LFSR_BIT_INDEX) + and the origin is same as CRC_ORIGIN. */ + +bool +is_a_valid_symb (value_bit *bit, tree crc_origin, size_t lfsr_bit_index) +{ + if (!is_a (bit)) + return false; + + symbolic_bit *sym_bit = as_a (bit); + bool is_correct_index = (sym_bit->get_index () == lfsr_bit_index); + bool is_same_crc_origin = (sym_bit->get_origin () == crc_origin); + return is_correct_index && is_same_crc_origin; +} + +/* Return true if the BIT is a valid crc[LFSR_BIT_INDEX] ^ 1, + where i is a whole number and left part's origin is same as CRC_ORIGIN. + LFSR_BIT_INDEX is the index of the LFSR bit from the same position as in CRC. + + If there is lfsr[8] at LFSR value vectors' 9-th bit, + when in the CRC vectors' 9-th bit's value must be + crc[8]. + + Otherwise, return false. */ + +bool +is_a_valid_xor_one (value_bit *bit, tree crc_origin, size_t lfsr_bit_index) +{ + if (is_a (bit)) + { + bit_xor_expression *xor_exp = as_a (bit); + if (is_one (xor_exp->get_right ())) + return is_a_valid_symb (xor_exp->get_left (), crc_origin, + lfsr_bit_index); + return false; + } + return false; +} + +/* Return true, if CONDITION_EXP checks CRC's MSB/LSB value + (under which xor is/not done). + Otherwise, return false. */ + +bool +may_be_xors_condition (tree crc_origin, value_bit *condition_exp, + size_t sb_index) +{ + if (!crc_origin) + return false; + + if (!condition_exp) + return false; + + /* The CONDITION_EXP of CRC may be a symbolic bit, if CRC is xor-ed with + the data, and updated CRC's significant bit is checked. + So, the CONDITION_EXP will be CRC's condition if it's origin is the same as + CRC_ORIGIN, and it's index equals to checked significant bit's index. */ + if (is_a (condition_exp)) + { + symbolic_bit *condition_symbolic = as_a (condition_exp); + return crc_origin == condition_symbolic->get_origin () + && sb_index == condition_symbolic->get_index (); + } + /* The CONDITION_EXP of CRC may be a bit_xor_expression, + if CRC and data are xor-ed only for significant bit's check. + I.e. CONDITION_EXP in this case may be crc[]^data[]. + So, the CONDITION_EXP will be CRC's condition if it's left or right + part's origin is the same as CRC_ORIGIN, and it's index equals to checked + significant bit's index. */ + else if (is_a (condition_exp)) + { + bit_xor_expression *condition_xor_exp = as_a + (condition_exp); + if (!(is_a (condition_xor_exp->get_left ()) + && is_a (condition_xor_exp->get_right ()))) + return false; + + symbolic_bit *cond_left + = as_a (condition_xor_exp->get_left ()); + symbolic_bit *cond_right + = as_a (condition_xor_exp->get_right ()); + bool cond_left_is_crc = (crc_origin == cond_left->get_origin () + && sb_index == cond_left->get_index ()); + bool cond_right_is_crc = (crc_origin == cond_right->get_origin () + && sb_index == cond_right->get_index ()); + return cond_left_is_crc || cond_right_is_crc; + } + return false; +} + +/* Check whether the condition is checked for significant bit being 0 or 1. + If IS_ONE is 1, when check whether the significant bit is 1 (xor branch), + if 0, whether the significant bit is 0 (not xor branch). */ + +bool +is_crc_xor_condition (tree crc_origin, unsigned char is_one, + size_t sb_index, state *final_state) +{ + /* The CRC cases we detect must contain only one condition related to CRC. */ + if (final_state->get_conditions ().elements () != 1) + return false; + + auto condition_iter = final_state->get_conditions ().begin (); + if (!is_a (*condition_iter)) + return false; + + /* If the condition is for checking MSB/LSB, then + if is_one is 1 and the condition is for checking MSB/LSB being one, or + if is_one is 0 and condition is for checking MSB/LSB being 0 + return true, otherwise - false. */ + value_bit *cond_exp = (*condition_iter)->get_left (); + if (may_be_xors_condition (crc_origin, cond_exp, sb_index)) + { + if (!is_a ((*condition_iter)->get_right ())) + return false; + + bit_condition *condition = as_a (*condition_iter); + unsigned char comparison_val + = as_a ((*condition_iter)->get_right ())->get_val (); + if (condition->get_code () == EQ_EXPR) + return comparison_val == is_one; + if (condition->get_code () == NE_EXPR) + return comparison_val != is_one; + return false; + } + return false; +} + +/* Check whether LSB/MSB of LFSR and calculated (maybe)CRC match. + If MSB is checked in the CRC loop, then here we check LSB, or vice versa. + CHECKED_SB_VALUE indicates which state of CRC value is checked. + If the CHECKED_SB_VALUE is 1 - then xor-ed CRC value is checked, + otherwise, not xor-ed is checked. */ + +bool +given_sb_match (value_bit *crc, value_bit *lfsr, + unsigned short checked_sb_value) +{ + /* If LFSR's MSB/LSB value is a constant (0 or 1), + then CRC's MSB/LSB must have the same value. */ + if (is_a (lfsr)) + { + if (!((is_a (crc) + && as_a (crc)->get_val () + == as_a (lfsr)->get_val ()))) + return false; + return true; + } + /* If LFSR's MSB/LSB value is a symbolic_bit + (that means MSB/LSB of the polynomial is 1), + then CRC's MSB/LSB must be equal to CHECKED_SB_VALUE. */ + else if (is_a (lfsr)) + { + if (!(is_a (crc) + && (as_a (crc)->get_val () == checked_sb_value))) + return false; + return true; + } + return false; +} + +/* Check whether significant bit of LFSR and calculated (maybe)CRC match. */ + +bool +sb_match (const value *lfsr, const value *crc_value, size_t sb_index, + size_t it_end, unsigned short value) +{ + /* If it's bit-forward CRC, check 0 bit's value. */ + if (sb_index == it_end - 1) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Checking 0 bit.\n"); + + if (!given_sb_match ((*crc_value)[0], (*lfsr)[0], value)) + return false; + } + /* If it's bit-reversed CRC, check last bit's value. */ + else if (sb_index == 0) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Checking %zu bit.\n", it_end); + + if (!given_sb_match ((*crc_value)[it_end], (*lfsr)[it_end], value)) + return false; + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Significant bit index is incorrect.\n"); + } + return true; +} + +/* Match the CRC to the LFSR, where CRC's all bit values are + symbolic_bit or symbolic_bit ^ 1, besides MSB/LSB (it may be constant). */ + +bool +lfsr_and_crc_bits_match (const value *lfsr, const value *crc_state, + tree crc_origin, size_t i, size_t it_end, + size_t sb_index, unsigned short checked_sb_value) +{ + + /* Check whether significant bits of LFSR and CRC match. */ + if (!sb_match (lfsr, crc_state, sb_index, it_end, checked_sb_value)) + return false; + + for (; i < it_end; i++) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Checking %zu bit.\n", i); + + /* Check the case when in lfsr we have LFSR (i)^LFSR (SBi), + where 0 ((*lfsr)[i])) + { + size_t index = (as_a ((*lfsr)[i]))->get_left () + ->get_index (); + /* Check CRC value of xor branch. */ + if (checked_sb_value == 1) + { + if (!(is_a_valid_xor_one ((*crc_state)[i], crc_origin, index))) + return false; + } + else /* Check CRC value of not xor branch. */ + { + if (!(is_a_valid_symb ((*crc_state)[i], crc_origin, index))) + return false; + } + } + /* Check the case when in LFSR we have LFSR (i), where 0 ((*lfsr)[i])) + { + size_t index = (as_a ((*lfsr)[i]))->get_index (); + if (!(is_a_valid_symb ((*crc_state)[i], crc_origin, index))) + return false; + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Not expected expression in LFSR.\n"); + return false; + } + } + return true; +} + +/* Return origin of CRC_BIT. + The first tree in loop, from which CRC's calculation is started. */ + +tree +get_origin_of_crc_from_symb_bit (value_bit *crc_bit) +{ + if (is_a (crc_bit)) + return as_a (crc_bit)->get_origin (); + return nullptr; +} + +/* Return origin of CRC_BIT. The first tree in loop, from which CRC's + calculation is started. If the CRC_BIT is symbolic value, return its origin, + otherwise return its left part's origin (right must be 1 if its CRC's + value). */ + +tree +get_origin_of_crc (value_bit *crc_bit) +{ + tree origin = get_origin_of_crc_from_symb_bit (crc_bit); + if (origin) + return origin; + else if (is_a (crc_bit)) + { + value_bit *crc_bit_left + = as_a (crc_bit)->get_left (); + return get_origin_of_crc_from_symb_bit (crc_bit_left); + } + return nullptr; +} + +/* Determine and initialize significant bit index + (if MSB is checked for CRC, then it's LSB index, and vice versa) + and the remaining part's begin and end. + SB_INDEX is the significant bit index. + IT_BEG is the beginning of the remaining part. + IT_END is the end of the remaining part. */ + +void +init_sb_index_and_other_part_begin_end (size_t &it_beg, size_t &it_end, + size_t &sb_index, size_t crc_size, + bool is_bit_forward) +{ + it_end = crc_size; + if (is_bit_forward) + { + sb_index = it_end - 1; + it_beg = 1; + } + else + { + it_beg = 0; + sb_index = 0; + --it_end; + } +} + +/* Return true if CRC_STATE matches the LFSR, otherwise - false. + LFSR - is created LFSR value for the given polynomial and CRC size. + CRC_STATE - contains CRC's calculated value and execution path condition. + IT_BEG and IT_END - are the border indexes of the value to be matched. + SB_INDEX - is the significant bit index of the CRC value, + which will be checked separately. + IF MSB is checked for CRC, when sb_index will be the index of LSB. + Otherwise, will be the index of MSB. + CHECKED_SB_VALUE - is the significant bit's value (used for CRC's condition). + If CHECKED_SB_VALUE is 1, it indicates that CRC_STATE is + xor-ed path's state. + If CHECKED_SB_VALUE is 0, then CRC_STATE is the state of the + not xor branch. */ + +bool +lfsr_matches_crc_state (const value *lfsr, state *crc_state, value *crc_value, + size_t it_beg, size_t it_end, size_t sb_index, + unsigned short checked_sb_value) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Starting to match the following CRC value: "); + state::print_value (crc_value); + } + + /* Get the origin (name) of the calculated CRC value. + All bits must have the same origin. */ + tree crc_origin = get_origin_of_crc ((*crc_value)[it_beg]); + if (!crc_origin) + return false; + + if (!is_crc_xor_condition (crc_origin, checked_sb_value, sb_index, crc_state)) + return false; + + /* Check whether CRC_VALUE and LFSR bits match. */ + return lfsr_and_crc_bits_match (lfsr, crc_value, crc_origin, + it_beg, it_end, sb_index, checked_sb_value); +} + +/* Return true if in the CRC_VALUE exists xor expression. + Otherwise, return false. */ + +bool +is_xor_state (value *crc_value, size_t it_beg, size_t it_end) +{ + for (unsigned j = it_beg; j < it_end; ++j) + if ((*crc_value)[j]->get_type () == BIT_XOR_EXPRESSION) + return true; + return false; +} + +/* Keep the value of calculated CRC. */ + +value * +get_crc_val (tree calculated_crc, state *curr_state) +{ + if (!calculated_crc) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Couldn't get the potential CRC variable.\n"); + return nullptr; + } + + /* When the calculated CRC is constant, it's not possible to determine + whether the CRC has been calculated. */ + if (TREE_CODE (calculated_crc) == INTEGER_CST) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Calculated CRC is a constant.\n"); + return nullptr; + } + + /* Get calculated return value. */ + value * crc_value = curr_state->get_value (calculated_crc); + + if (!crc_value) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "CRC is not in the state.\n"); + return nullptr; + } + return crc_value; +} + +/* Return true if all states from the FINAL_STATES match the LFSR, + otherwise - false. */ + +bool +all_states_match_lfsr (value *lfsr, bool is_bit_forward, tree calculated_crc, + const vec &final_states) +{ + if (final_states.length () != 2) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "The final states count isn't two.\n"); + return false; + } + + value *crc_xor_value = get_crc_val (calculated_crc, final_states[0]); + value *crc_not_xor_value = get_crc_val (calculated_crc, final_states[1]); + + /* LFSR's size must be equal to CRC's size. */ + if ((crc_xor_value->length () != lfsr->length ()) + || (crc_not_xor_value->length () != lfsr->length ())) + return false; + + /* Depending on whether it is bit-forward or reversed CRC, + determine in which significant bit new value is added, + to examine that bit separately. + If in the CRC algorithm MSB (sb_index) is checked to be one for xor, + then here we check LSB separately (marginal bit). + If LSB (sb_index) is checked, then we separate MSB (marginal bit). */ + size_t it_beg, it_end, sb_index; + init_sb_index_and_other_part_begin_end (it_beg, it_end, sb_index, + crc_xor_value->length (), + is_bit_forward); + + size_t xor_st_index = 0, not_xor_st_index = 1; + /* If first is not xor's state, + then the second state is assumed to be xor's state. */ + if (!is_xor_state (crc_xor_value, it_beg, it_end)) + { + std::swap (crc_xor_value, crc_not_xor_value); + xor_st_index = 1; + not_xor_st_index = 0; + } + + /* If xor-ed CRC value doesn't match the LFSR value, return false. */ + if (!lfsr_matches_crc_state (lfsr, final_states[xor_st_index], crc_xor_value, + it_beg, it_end, sb_index, 1)) + return false; + + /* If not xor-ed CRC value doesn't match the LFSR value, return false. */ + if (!lfsr_matches_crc_state (lfsr, final_states[not_xor_st_index], + crc_not_xor_value, it_beg, it_end, sb_index, 0)) + return false; + + return true; +} \ No newline at end of file diff --git a/gcc/crc-verification.h b/gcc/crc-verification.h new file mode 100644 index 00000000000..d802f4ddb70 --- /dev/null +++ b/gcc/crc-verification.h @@ -0,0 +1,162 @@ +/* Execute symbolically all paths of the loop. + Copyright (C) 2022-2024 Free Software Foundation, Inc. + Contributed by Mariam Arutunian + +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 +. */ + +#ifndef GCC_CRC_VERIFICATION +#define GCC_CRC_VERIFICATION + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "cfgloop.h" +#include "sym-exec/sym-exec-state.h" + +class crc_symbolic_execution { + + private: + /* A vector of states to keep the current state of each executed path. */ + vec m_states; + + /* A vector of final states + to keep the returned_value and path conditions. */ + vec m_final_states; + + /* Potential CRC loop, which must be executed symbolically, + to check whether it calculates CRC. */ + class loop *m_crc_loop; + + /* Output CRC from the last block of the loop. */ + gphi *m_output_crc; + + /* Indicates whether the loop execution brought to loop exit. + I.e. the condition of the loop is false. */ + bool m_is_last_iteration; + + /* Returns true if the variable is used outside the loop. + Otherwise, returns false. */ + bool is_used_outside_the_loop (tree); + + /* Add next basic blocks of the conditional block + for the execution path into the stack. + If the condition depends on symbolic values, keep both edges. + If the condition is true, keep true edge, else - false edge. + Returns true if addition succeed. Otherwise - false. */ + bool add_next_bbs (basic_block, state *, auto_vec &); + + /* Keep conditions depending on symbolic variables in the states. */ + static bool add_condition (const gcond *, state *, state *); + + /* The function adds E edge into the STACK if it doesn't have an immediate + successor back edge. + + When loop counter is checked in the if condition, + we mustn't continue on real path as we want to stop the execution before + the second iteration. */ + bool add_edge (edge, auto_vec &); + + /* Create new state for true and false branch. + Keep conditions in new created states. */ + bool resolve_condition (const gcond *, auto_vec &); + + /* If final states are less than two, adds new FINAL_STATE and returns true. + Otherwise, returns false. + In CRC cases we detect may not occur more than two final states. */ + bool add_final_state (state *); + + /* Keep the state of the executed path in final states. */ + bool keep_states (); + + bool execute_assign_statement (const gassign *); + + /* Execute gimple statements of the basic block. + Keeping values of variables in the state. */ + bool execute_bb_gimple_statements (basic_block, auto_vec &); + + /* Assign values of phi instruction to its result. + Keep updated values in the state. */ + bool execute_bb_phi_statements (basic_block, edge); + + /* Execute all statements of the basic block. + Keeping values of variables in the state. */ + bool execute_bb_statements (basic_block, edge, auto_vec &); + + /* Create initial state of the loop's header BB variables which have constant + values. + If it is the first iteration of the loop, initialise variables with the + initial values, otherwise initialise the variable with the value calculated + during the previous execution. */ + state *create_initial_state (class loop *); + +/* Traverse function fun's all paths from the first basic block to the last. + Each time iterate loops only once. + Symbolically execute statements of each path. */ + bool traverse_function (function *); + + /* Execute the loop, which calculates crc with initial values, + to calculate the polynomial. */ + bool execute_crc_loop (gphi *, gphi *, bool); + + public: + + /* Returns calculated polynomial by executing the loop + with concrete values. + First value of the pair is the tree containing the value of the polynomial, + second is the calculated polynomial. The pair may contain nullptr. */ + std::pair + extract_polynomial (gphi *, gphi *, tree, bool); + + /* Symbolically execute the CRC loop, doing one iteration. */ + bool symb_execute_crc_loop (); + + const vec &get_final_states () + { + return m_final_states; + } + + bool is_last_iteration () + { + return m_is_last_iteration; + } + + crc_symbolic_execution (class loop *loop, gphi * output_crc) : + m_crc_loop (loop), m_output_crc (output_crc), m_is_last_iteration (false) + { + /* Reserve memory for the vectors of states. */ + int max_states = 2; + m_states.create (max_states); + m_final_states.create (max_states); + } + + ~crc_symbolic_execution () + { + /* Free memory. */ + state::clear_states (&m_states); + state::clear_states (&m_final_states); + } +}; + + +/**************************** LFSR MATCHING *********************************/ + +/* Returns true if all states match the LFSR, otherwise - false. */ +bool all_states_match_lfsr (value *, bool, tree, const vec &); + + +#endif //GCC_CRC_VERIFICATION diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc index c67b0fd38c3..a05aaf9f217 100644 --- a/gcc/gimple-crc-optimization.cc +++ b/gcc/gimple-crc-optimization.cc @@ -31,9 +31,19 @@ along with GCC; see the file COPYING3. If not see #include "tree-cfg.h" #include "cfgloop.h" #include "tree-scalar-evolution.h" +#include "crc-verification.h" class crc_optimization { private: + /* Record of statements already seen. */ + bitmap m_visited_stmts; + + /* Input CRC of the loop. */ + tree m_crc_arg; + + /* Input data of the loop. */ + tree m_data_arg; + /* The statement doing shift 1 operation before/after xor operation. */ gimple *m_shift_stmt; @@ -47,6 +57,9 @@ class crc_optimization { /* The loop, which probably calculates CRC. */ class loop *m_crc_loop; + /* Polynomial used in CRC calculation. */ + unsigned HOST_WIDE_INT m_polynomial; + /* Depending on the value of M_IS_BIT_FORWARD, may be forward or reversed CRC. If M_IS_BIT_FORWARD, then it is bit-forward implementation, otherwise bit-reversed. */ @@ -65,6 +78,15 @@ class crc_optimization { Xor must be done under the condition of MSB/LSB being 1. */ bool loop_may_calculate_crc (class loop *loop); + /* Symbolically executes the loop and checks that LFSR and resulting states + match. + Returns true if it is verified that the loop calculates CRC. + Otherwise, return false. + OUTPUT_CRC is the phi statement which will hold the calculated CRC value + after the loop exit. */ + bool loop_calculates_crc (gphi *output_crc, + std::pair calc_polynom); + /* Returns true if there is only two conditional blocks in the loop (one may be for the CRC bit check and the other for the loop counter). This may filter out some real CRCs, where more than one condition @@ -179,9 +201,33 @@ class crc_optimization { /* Prints extracted details of CRC calculation. */ void dump_crc_information (); + /* Returns true if OUTPUT_CRC's result is the input of m_phi_for_crc. + Otherwise, returns false. */ + bool is_output_crc (gphi *output_crc); + + /* Swaps m_phi_for_crc and m_phi_for_data if they are mixed. */ + void swap_crc_and_data_if_needed (gphi *output_crc); + + /* Validates CRC and data arguments and + sets them for potential CRC loop replacement. + + The function extracts the CRC and data arguments from PHI nodes and + performs several checks to ensure that the CRC and data are suitable for + replacing the CRC loop with a more efficient implementation. + + Returns true if the arguments are valid and the loop replacement is possible, + false otherwise. */ + bool validate_crc_and_data (); + + /* Convert polynomial to unsigned HOST_WIDE_INT. */ + void construct_constant_polynomial (value *polynomial); + + /* Returns phi statement which may hold the calculated CRC. */ + gphi *get_output_phi (); + public: crc_optimization () : m_visited_stmts (BITMAP_ALLOC (NULL)), - m_crc_loop (nullptr) + m_crc_loop (nullptr), m_polynomial (0) { set_initial_values (); } @@ -705,6 +751,8 @@ crc_optimization::cond_depends_on_crc (auto_vec& stmts) void crc_optimization::set_initial_values () { + m_crc_arg = nullptr; + m_data_arg = nullptr; m_shift_stmt = nullptr; m_phi_for_crc = nullptr; m_phi_for_data = nullptr; @@ -933,6 +981,240 @@ crc_optimization::loop_may_calculate_crc (class loop *loop) return false; } +/* Symbolically executes the loop and checks that LFSR and resulting states + match. + Returns true if it is verified that the loop calculates CRC. + Otherwise, return false. + OUTPUT_CRC is the phi statement which will hold the calculated CRC value + after the loop exit. */ + +bool +crc_optimization::loop_calculates_crc (gphi *output_crc, + std::pair calc_polynom) +{ + /* Create LFSR state using extracted polynomial. */ + value * lfsr = state::create_lfsr (calc_polynom.first, calc_polynom.second, + m_is_bit_forward); + if (!lfsr) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Couldn't create LFSR!\n"); + return false; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nLFSR value is \n"); + state::print_value (lfsr); + } + + /* Execute the loop with symbolic values + (symbolic value is assigned to the variable when its value isn't known) + to keep states, for further comparison. */ + bool is_crc = true; + crc_symbolic_execution loop_executor (m_crc_loop, output_crc); + while (!loop_executor.is_last_iteration ()) + { + if (!loop_executor.symb_execute_crc_loop ()) + { + if (dump_file) + fprintf (dump_file, "\nCRC verification didn't succeed " + "during symbolic execution!\n"); + is_crc = false; + break; + } + + /* Check whether LFSR and obtained states are same. */ + tree calculated_crc = PHI_ARG_DEF_FROM_EDGE (output_crc, + single_exit (m_crc_loop)); + if (!all_states_match_lfsr (lfsr, m_is_bit_forward, calculated_crc, + loop_executor.get_final_states ())) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Returned state and LFSR differ.\n"); + is_crc = false; + break; + } + } + delete lfsr; + return is_crc; +} + +/* Returns true if OUTPUT_CRC's result is the input of M_PHI_FOR_CRC. + Otherwise, returns false. */ + +bool +crc_optimization::is_output_crc (gphi *output_crc) +{ + tree crc_of_exit + = PHI_ARG_DEF_FROM_EDGE (output_crc, single_exit (m_crc_loop)); + tree crc_of_latch + = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, loop_latch_edge (m_crc_loop)); + if (crc_of_exit == crc_of_latch) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Output CRC is "); + print_gimple_expr (dump_file, (gimple *) output_crc, dump_flags); + fprintf (dump_file, "\n"); + } + return true; + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Output CRC and determined input CRC " + "differ.\n"); + return false; + } +} + +/* Swaps M_PHI_FOR_CRC and M_PHI_FOR_DATA if they are mixed. */ + +void +crc_optimization::swap_crc_and_data_if_needed (gphi *output_crc) +{ + tree crc_of_exit + = PHI_ARG_DEF_FROM_EDGE (output_crc, single_exit (m_crc_loop)); + edge crc_loop_latch = loop_latch_edge (m_crc_loop); + if (crc_of_exit != PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, crc_loop_latch)) + { + if (m_phi_for_data + && crc_of_exit == PHI_ARG_DEF_FROM_EDGE (m_phi_for_data, + crc_loop_latch)) + { + std::swap (m_phi_for_crc, m_phi_for_data); + } + } +} + +/* Validates CRC and data arguments and + sets them for potential CRC loop replacement. + + The function extracts the CRC and data arguments from PHI nodes and + performs several checks to ensure that the CRC and data are suitable for + replacing the CRC loop with a more efficient implementation. + + Returns true if the arguments are valid and the loop replacement is possible, + false otherwise. */ + +bool crc_optimization::validate_crc_and_data () +{ + /* Set m_crc_arg and check if fits in word_mode. */ + gcc_assert (m_phi_for_crc); + m_crc_arg = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, + loop_preheader_edge (m_crc_loop)); + gcc_assert (m_crc_arg); + + if (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (m_crc_arg))).to_constant () + > GET_MODE_SIZE (word_mode)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "word_mode is less than CRC mode.\n"); + return false; + } + + unsigned HOST_WIDE_INT + data_size = tree_to_uhwi (m_crc_loop->nb_iterations) + 1; + /* We don't support the case where data is larger than the CRC. */ + if (TYPE_PRECISION (TREE_TYPE (m_crc_arg)) < data_size) + return false; + + /* Set m_data_arg if a PHI node for data exists, + and check its size against loop iterations. + This is the case when data and CRC are XOR-ed in the loop. */ + if (m_phi_for_data) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Data and CRC are xor-ed in the for loop. Initializing data " + "with its value.\n"); + m_data_arg = PHI_ARG_DEF_FROM_EDGE (m_phi_for_data, + loop_preheader_edge (m_crc_loop)); + gcc_assert (m_data_arg); + if (TYPE_PRECISION (TREE_TYPE (m_data_arg)) != data_size) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Loop iteration number and data's size differ.\n"); + return false; + } + return true; + } + return true; +} + +/* Convert polynomial to unsigned HOST_WIDE_INT. */ + +void +crc_optimization::construct_constant_polynomial (value *polynomial) +{ + m_polynomial = 0; + for (unsigned i = 0; i < (*polynomial).length (); i++) + { + value_bit *const_bit; + if (m_is_bit_forward) + const_bit = (*polynomial)[(*polynomial).length () - 1 - i]; + else + const_bit = (*polynomial)[i]; + m_polynomial <<= 1; + m_polynomial ^= (as_a (const_bit))->get_val () ? 1 : 0; + } +} + +/* Returns phi statement which may hold the calculated CRC. */ + +gphi * +crc_optimization::get_output_phi () +{ + edge loop_exit = single_exit (m_crc_loop); + if (!loop_exit) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "The loop doesn't have single exit.\n"); + return nullptr; + } + basic_block bb = loop_exit->dest; + gphi *output_crc = nullptr; + int phi_count = 0; + + /* We are only interested in cases when there is only one phi at the + loop exit, and that phi can potentially represent the CRC. + If there are other phis present, it indicates that additional values are + being calculated within the loop that are used outside it. */ + for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) + { + tree phi_result = gimple_phi_result (gsi.phi ()); + + /* Don't consider virtual operands. */ + if (!virtual_operand_p (phi_result)) + { + if (phi_count < 1) + { + output_crc = gsi.phi (); + phi_count++; + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "There is more than one output phi.\n"); + return nullptr; + } + } + } + + if (output_crc) + { + if (gimple_phi_num_args (output_crc) == 1) + return output_crc; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Couldn't determine output CRC.\n"); + return nullptr; +} + unsigned int crc_optimization::execute (function *fun) { @@ -948,7 +1230,48 @@ crc_optimization::execute (function *fun) for (auto loop: loop_list) { /* Perform initial checks to filter out non-CRCs. */ - loop_may_calculate_crc (loop); + if (loop_may_calculate_crc (loop)) + { + /* Get the phi which will hold the calculated CRC. */ + gphi *output_crc = get_output_phi (); + if (!output_crc) + break; + + swap_crc_and_data_if_needed (output_crc); + if (!is_output_crc (output_crc)) + break; + if (!validate_crc_and_data ()) + break; + + edge loop_latch = loop_latch_edge (m_crc_loop); + tree calced_crc = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, loop_latch); + crc_symbolic_execution execute_loop (m_crc_loop, nullptr); + /* Execute the loop assigning specific values to CRC and data + for extracting the polynomial. */ + std::pair + calc_polynom = execute_loop.extract_polynomial (m_phi_for_crc, + m_phi_for_data, + calced_crc, + m_is_bit_forward); + + value *polynom_value = calc_polynom.second; + /* Stop analysis if we couldn't get the polynomial's value. */ + if (!polynom_value) + break; + + /* Stop analysis in case optimize_size is specified + and table-based would be generated. This check is only needed for + TARGET_CRC case, as polynomial's value isn't known in the + beginning. */ + construct_constant_polynomial (polynom_value); + + if (!loop_calculates_crc (output_crc, calc_polynom)) + break; + + if (dump_file) + fprintf (dump_file, "The loop with %d header BB index " + "calculates CRC!\n", m_crc_loop->header->index); + } } return 0; } diff --git a/gcc/sym-exec/sym-exec-state.cc b/gcc/sym-exec/sym-exec-state.cc index 85e6093c362..c51e2aa3c1f 100644 --- a/gcc/sym-exec/sym-exec-state.cc +++ b/gcc/sym-exec/sym-exec-state.cc @@ -2065,6 +2065,55 @@ state::print_value (value *var) } +/* Create LFSR value for the reversed CRC. */ + +void +state::create_reversed_lfsr (value &lfsr, const value &crc, + const value &polynomial) +{ + size_t size = polynomial.length (); + + /* Determine values of all bits, except MSB. */ + for (size_t i = 0; i < size - 1; i++) + { + if (as_a (polynomial[i])->get_val ()) + lfsr.push (state::xor_two_bits (crc[i + 1], crc[0])); + else + lfsr.push (crc[i + 1]->copy ()); + } + + /* Determine value of MSB. */ + if (as_a (polynomial[size - 1])->get_val ()) + lfsr.push (crc[0]->copy ()); + else + lfsr.push (new bit (0)); +} + + +/* Create LFSR value for the forward CRC. */ + +void +state::create_forward_lfsr (value &lfsr, const value &crc, + const value &polynomial) +{ + size_t size = polynomial.length (); + /* Determine value of LSB. */ + if (as_a (polynomial[0])->get_val ()) + lfsr.push (crc[size - 1]->copy ()); + else + lfsr.push (new bit (0)); + + /* Determine values of remaining bits. */ + for (size_t i = 1; i < size; i++) + { + if (as_a (polynomial[i])->get_val ()) + lfsr.push (state::xor_two_bits (crc[i - 1], crc[size - 1])); + else + lfsr.push (crc[i - 1]->copy ()); + } +} + + /* Get the last 1 bit index. */ size_t @@ -2079,6 +2128,58 @@ last_set_bit (const value &polynomial) } +/* Create LFSR value. */ + +value * +state::create_lfsr (tree crc, value *polynomial, bool is_bit_forward) +{ + /* Check size compatibility․ */ + unsigned HOST_WIDE_INT polynomial_length = polynomial->length (); + unsigned HOST_WIDE_INT crc_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (crc))); + if (crc_size < polynomial_length) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "LFSR state creation: " + "Polynomial doesn't fit into the crc.\n"); + + return nullptr; + } + + /* Get the minimal byte size to keep the polynomial. + Ie, if the last 1 bit of the polynomial is at 6 index, size will be 8. */ + size_t required_polynomial_size = ((last_set_bit (*polynomial)/8) + 1) * 8; + + /* Polynomial's length actually equals to the CRC variable's size. + Now we detect only those CRC calculation algorithms, where leading 1 of the + polynomial isn't kept. */ + if (required_polynomial_size == 0 + || required_polynomial_size != polynomial_length) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Polynomial's all bits are zeros " + "or the size of the polynomial is uncertain.\n"); + return nullptr; + } + + /* Create vector of symbolic bits for crc. */ + value crc_value (polynomial_length, TYPE_UNSIGNED (TREE_TYPE (crc))); + + for (unsigned HOST_WIDE_INT i = 0; i < polynomial_length; i++) + crc_value.push (new symbolic_bit (i, crc)); + + /* create LFSR vector. */ + value *lfsr = new value (polynomial_length, TYPE_UNSIGNED (TREE_TYPE (crc))); + + /* Calculate values for LFSR. */ + if (is_bit_forward) + create_forward_lfsr (*lfsr, crc_value, *polynomial); + else + create_reversed_lfsr (*lfsr, crc_value, *polynomial); + + return lfsr; +} + + /* Prints added conditions. */ void diff --git a/gcc/sym-exec/sym-exec-state.h b/gcc/sym-exec/sym-exec-state.h index e9e68b6478a..07771a52288 100644 --- a/gcc/sym-exec/sym-exec-state.h +++ b/gcc/sym-exec/sym-exec-state.h @@ -276,6 +276,14 @@ class state { /* Make a copy of given bits. */ static vec *make_copy (vec *bits); + /* Create LFSR value for the reversed CRC. */ + static void create_reversed_lfsr (value &lfsr, const value &crc, + const value &polynomial); + + /* Create LFSR value for the forward CRC. */ + static void create_forward_lfsr (value &lfsr, const value &crc, + const value &polynomial); + public: /* Default constructor for state. */ state () = default; @@ -407,6 +415,9 @@ class state { /* Returns status of last added condition. */ condition_status get_last_cond_status (); + + /* Create LFSR value. */ + static value *create_lfsr (tree crc, value *polynomial, bool is_bit_forward); }; -- 2.25.1