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.129.124]) by sourceware.org (Postfix) with ESMTPS id 6CB783858D33 for ; Tue, 3 Oct 2023 11:52:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6CB783858D33 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=1696333956; 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=1Ffzv8GKzu877YJharjviGsy1ZbMqpT7Y/JQ2hCTUXA=; b=Cdt5HuYhBuk4XNO6el7vs/TjgONmG7DTFQs7LmNQzp+Qgp4gaPyBzbJwsnlRtpCk3ziLHg FLOyUzPWSV9EJGKBhMTKPVrKSyDGr0f3lEIQvlDqfLTIHKG/IludGgvKBUsSnW/jbXUxdA AgKuOhUT6W392VFkKUWrDJotyGDn2Gg= 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-389-nvRGViEIOKSDw3vV834XVg-1; Tue, 03 Oct 2023 07:52:33 -0400 X-MC-Unique: nvRGViEIOKSDw3vV834XVg-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.rdu2.redhat.com [10.11.54.6]) (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 9A9331C0512A; Tue, 3 Oct 2023 11:52:32 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.193.202]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 575D42156A27; Tue, 3 Oct 2023 11:52:32 +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 393BqTlI3542274 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 3 Oct 2023 13:52:29 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 393BqS0X3542273; Tue, 3 Oct 2023 13:52:28 +0200 Date: Tue, 3 Oct 2023 13:52:28 +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.6 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_H4,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 11:41:01AM +0000, Tamar Christina wrote: > > 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. > > Hmm the problem here is that it would make the second loop that fills in the len > quadratic as it has to search for arg in the list. I suppose I could push a pointer > to the struct instead of `i` in the hashmap and the element into args and update > the pointer as we go along? Would that work? Only if the second loop traverses the hashmap elements and for each tries to find the corresponding vector element. If instead you do what you've done before in the second loop, walk the vector and for each arg in there lookup phi_args_map.get (v.arg) (but please just once, vanilla trunk looks it up twice in for (int index : phi_arg_map.get (args[i])) { 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 (); ), then I don't think it would be quadratic. Jakub