From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 87ABF3858D28 for ; Tue, 3 Oct 2023 11:02:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 87ABF3858D28 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1696330934; h=from:from:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:in-reply-to:in-reply-to: references:references; bh=cWVl6SZqqHAOS2ElSqKbz6KKp7FLwmRo3bOa+hSC+MY=; b=hyOLV+Zj8S3/sQoTgZ0IKfbkiFXGKQU5cfIspHZldtQFLy6V6r9zfnVoHK4922hU56pN7e dku/hMKpmWrgFuIJYVhEJv90BqwulyoiN8vr6Gfp8S85ZcajcrPpQHyRbclOjcr7g1UibU NA9eKXuqZjT6Extwk+1pfOu4YWCDOps= Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-94-KBH-K4mTOcK2krmWDWFz-g-1; Tue, 03 Oct 2023 07:02:05 -0400 X-MC-Unique: KBH-K4mTOcK2krmWDWFz-g-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.rdu2.redhat.com [10.11.54.3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 8CAA01C06357; Tue, 3 Oct 2023 11:02:01 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.193.202]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 4DE7A1054FC1; Tue, 3 Oct 2023 11:02:01 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.17.1/8.17.1) with ESMTPS id 393B1wtv3542192 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 3 Oct 2023 13:01:58 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 393B1v2e3542191; Tue, 3 Oct 2023 13:01:57 +0200 Date: Tue, 3 Oct 2023 13:01:57 +0200 From: Jakub Jelinek To: Tamar Christina Cc: "gcc-patches@gcc.gnu.org" , nd , "jwakely@redhat.com" Subject: Re: [PATCH]middle-end: Recursively check is_trivially_copyable_or_pair in vec.h Message-ID: Reply-To: Jakub Jelinek References: MIME-Version: 1.0 In-Reply-To: X-Scanned-By: MIMEDefang 3.1 on 10.11.54.3 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Status: No, score=-3.7 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Tue, Oct 03, 2023 at 10:27:16AM +0000, Tamar Christina wrote: > +/* Structure used to track meta-data on PHI arguments used to generate > + most efficient comparison sequence to slatten a PHI node. */ ^^^ typo (at least, never heard of this word, and wiktionary doesn't know it either (except for Dannish/Swedish)) > @@ -2045,6 +2065,25 @@ gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi, > return lhs; > } > Perhaps add a short function comment here? > +static int > +cmp_arg_entry (const void *p1, const void *p2) > +{ > + const ifcvt_arg_entry sval1 = *(const ifcvt_arg_entry *)p1; > + const ifcvt_arg_entry sval2 = *(const ifcvt_arg_entry *)p2; > + > + if (sval1.num_compares < sval2.num_compares) > + return -1; > + else if (sval1.num_compares > sval2.num_compares) > + return 1; > + > + if (sval1.occurs < sval2.occurs) > + return -1; > + else if (sval1.occurs > sval2.occurs) > + return 1; > + > + return 0; > +} > + > @@ -2167,61 +2206,53 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) > /* Create hashmap for PHI node which contain vector of argument indexes > having the same value. */ > bool swap = false; > - hash_map > phi_arg_map; > + hash_map > phi_arg_map; > unsigned int num_args = gimple_phi_num_args (phi); > /* Vector of different PHI argument values. */ > - auto_vec args (num_args); > + auto_vec args; > > - /* Compute phi_arg_map. */ > + /* Compute phi_arg_map, determine the list of unique PHI args and the indices > + where they are in the PHI node. The indices will be used to determine > + the conditions to apply and their complexity. */ > for (i = 0; i < num_args; i++) > { > tree arg; > > arg = gimple_phi_arg_def (phi, i); > - if (!phi_arg_map.get (arg)) > - args.quick_push (arg); > phi_arg_map.get_or_insert (arg).safe_push (i); > } > > - /* Determine element with max number of occurrences and complexity. Looking at only > - number of occurrences as a measure for complexity isn't enough as all usages can > - be unique but the comparisons to reach the PHI node differ per branch. */ > - typedef std::pair > ArgEntry; > - auto_vec argsKV; > - for (i = 0; i < args.length (); i++) > + /* Determine element with max number of occurrences and complexity. Looking > + at only number of occurrences as a measure for complexity isn't enough as > + all usages can be unique but the comparisons to reach the PHI node differ > + per branch. */ > + for (auto entry : phi_arg_map) > { > unsigned int len = 0; > - for (int index : phi_arg_map.get (args[i])) > + for (int index : entry.second) > { > edge e = gimple_phi_arg_edge (phi, index); > len += get_bb_num_predicate_stmts (e->src); > } > > - unsigned occur = phi_arg_map.get (args[i])->length (); > + unsigned occur = entry.second.length (); > if (dump_file && (dump_flags & TDF_DETAILS)) > fprintf (dump_file, "Ranking %d as len=%d, idx=%d\n", i, len, occur); > - argsKV.safe_push ({ args[i], { len, occur }}); > + args.safe_push ({ entry.first, len, occur, entry.second }); > } > > /* Sort elements based on rankings ARGS. */ > - std::sort(argsKV.begin(), argsKV.end(), [](const ArgEntry &left, > - const ArgEntry &right) { > - return left.second < right.second; > - }); > - > - for (i = 0; i < args.length (); i++) > - args[i] = argsKV[i].first; > + args.qsort (cmp_arg_entry); I admit I don't know what you're using the args vector later on for and whether its ordering affects code generation, but because you qsort it I assume it does. My worry is that a hash_map traversal might not be the same order on all hosts and similarly qsort doesn't achieve stable sorting in case num_compares and occurrs members are equal for two or more different arguments. Can that ever happen? We have stablesort method instead of qsort but that would require consistent ordering in the vector (std::sort doesn't ensure stable sorting either). If it is a non-issue, the patch is ok with the above nits fixed. Otherwise perhaps we'd need to push in the first loop into the vector (but that if (!phi_arg_map.get (arg)) args.quick_push (arg); phi_arg_map.get_or_insert (arg).safe_push (i); in there was quite inefficient, better would be bool existed; phi_arg_map.get_or_insert (arg, &existed).safe_push (i); if (!existed) args.safe_push (ifcvt_arg_entry { arg, 0, 0, vNULL }); or something similar), plus use stablesort. Or add another compared member which would be the first position. Jakub