From patchwork Fri Dec 13 21:00:57 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Oleg Endo X-Patchwork-Id: 301173 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 18BEE2C009F for ; Sat, 14 Dec 2013 08:01:14 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:subject:from:to:cc:date:in-reply-to:references :content-type:content-transfer-encoding:mime-version; q=dns; s= default; b=IGR81tyWn5STTvuhfEJVEoIXlxDfCea0LgvzkfWY6uQZ9ryDQzk1m p4oJdXKIPiSVRYRSfYGJefVU+f1dt6Lfx+2vpGm2nNlWZgUqL4rpiFs+Tf8h1Zmr 7LAFlfdUsj5SeAB01BuhBtRkXAnunovPaZMR5vtvzA+c7iaZtUk1PY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:subject:from:to:cc:date:in-reply-to:references :content-type:content-transfer-encoding:mime-version; s=default; bh=Jr3qJfAKGI9s9G+BMmyiVubzsho=; b=fLN/n2MZkSknLGPf4i+lgOPPKoNl pxPaARSuUME/brGnCypy+8xZTyytA/cmf7ewfjClRKoahBDU+pctnS48bU11oZcY t2uePDaE62WBt6Co5WhWc+wcSTwJNh4ck4Qex8Eoanhg2XDJycIOcWD/YgHC91YL 9Vi3XxdJVQalxjU= Received: (qmail 30371 invoked by alias); 13 Dec 2013 21:01:07 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 30358 invoked by uid 89); 13 Dec 2013 21:01:06 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.7 required=5.0 tests=AWL, BAYES_50, RCVD_IN_DNSWL_NONE, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.2 X-HELO: mailout07.t-online.de Received: from mailout07.t-online.de (HELO mailout07.t-online.de) (194.25.134.83) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 13 Dec 2013 21:01:04 +0000 Received: from fwd31.aul.t-online.de (fwd31.aul.t-online.de ) by mailout07.t-online.de with smtp id 1VrZqz-0005Tx-PY; Fri, 13 Dec 2013 22:00:57 +0100 Received: from [192.168.0.103] (G-dPS-ZlrhYWiD-5TEHr1rcKCjrGKn2WWz6mKRbJohLx6dz7on5ylDTIMHnKHM8gwe@[87.155.245.9]) by fwd31.t-online.de with esmtp id 1VrZr0-36Y5GS0; Fri, 13 Dec 2013 22:00:58 +0100 Message-ID: <1386968457.2455.129.camel@yam-132-YW-E178-FTW> Subject: Re: C++ edge_iterator (was: Re: [SH] PR 53976 - Add RTL pass to eliminate clrt, sett insns) From: Oleg Endo To: Trevor Saunders Cc: gcc-patches@gcc.gnu.org Date: Fri, 13 Dec 2013 22:00:57 +0100 In-Reply-To: <20131212081349.GA1708@tsaunders-iceball.corp.tor1.mozilla.com> References: <1384975779.2438.119.camel@yam-132-YW-E178-FTW> <1386784057.2455.73.camel@yam-132-YW-E178-FTW> <20131212081349.GA1708@tsaunders-iceball.corp.tor1.mozilla.com> Mime-Version: 1.0 X-IsSubscribed: yes On Thu, 2013-12-12 at 03:13 -0500, Trevor Saunders wrote: > On Wed, Dec 11, 2013 at 06:47:37PM +0100, Oleg Endo wrote: > > On Thu, 2013-11-21 at 00:04 +0100, Steven Bosscher wrote: > > > Declaring the edge_iterator inside the for() is not a good argument > > > against FOR_EACH_EDGE. Of course, brownie points are up for grabs for > > > the brave soul daring enough to make edge iterators be proper C++ > > > iterators... ;-) > > so, as a first question why do we have a special edge iterator at all? it > seems like we could just have a vec iterator and use that removing a > bunch of indirection that seems pretty useless. I don't know why it's there. Looks like a remainder from the pre-C++ code, as the conversion is being done step by step. > > > So, I gave it a try -- see the attached patch. > > It allows edge iteration to look more like STL container iteration: > > > > for (basic_block::edge_iterator ei = bb->pred_edges ().begin (); > > ei != bb->pred_edges ().end (); ++ei) > > { > > basic_block pred_bb = (*ei)->src; > > ... > > } > > personally I'm not really a fan of overloading ++ / * that way, but I > can't speak for anyone else. I'd prefer something like > > for (vec_iterator i = vec.forward_iterator (); !i.done (); i.next ()) > and > for (backward_vec_iterator i = vec.backward_iterator (); !i.done (); i.next ()) > > but that might break range base for loops? Right, that doesn't work with range-based for loops, since it doesn't follow the standard concept of iteration. For a more detailed explanation, see also for example http://www.codesynthesis.com/~boris/blog/2012/05/16/cxx11-range-based-for-loop/ BTW, if you look at the patch, I haven't overloaded any ++ operators: > > Then the > > typedef struct basic_block_def* basic_block; > > > > is replaced with a wrapper class 'basic_block', which is just a simple > > POD wrapper around a basic_block_def*. There should be no penalties > > compared to passing/storing raw pointers. Because of the union with > > constructor restriction of C++98 an additional wrapper class > > 'basic_block_in_union' is required, which doesn't have any constructors > > defined. > > > > Having 'basic_block' as a class allows putting typedefs for the edge > > iterator types in there (initially I tried putting the typedefs into > > struct basic_block_def, but gengtype would bail out). > > namespacing like that seems a little messy, but so is vec_iterator or > such I guess. I'm not sure which part of the namespacing you're referring to exactly. The basic_block::edge_iterator thing? Usually the iterator type is defined in the container type. In this case it would be vec. The choice of the container type for storing edges is done in basic_block_def. Thus, ideally the iterator type should be obtained from the basic_block_def class somehow. A more bureaucratic way would be to have a typedef inside basic_block_def (which is not possible because of gengtype as mentioned before, so let's assume it's in basic_block)... class basic_block { public: typedef vec edge_container; edge_container& pred_edges (void); edge_container& succ_edges (void); ... }; and then access the iterator via for (basic_block::edge_container::iterator i = bb->bb->pred_edges ().begin (); ...) Having to type out iterator types is a well known annoyance of C++98. Of course it's shorter to write for (edge_iterator i = ...) but that means, that there can be only one type of edge container ever. > > It would also be possible to have a free standing definition / typedef > > of edge_iterator, but it would conflict with the existing one and > > require too many changes at once. Moreover, the iterator type actually > > I bet it'll be a lot of work but changing everything seems nice so maybe > its worth just sitting down for a couple days and banging it out if it > gives nicer names? Nicer names than "edge_iterator" you mean? I can't think of any at the moment... > > > depends on the container type, which is vec, and the > > container type is defined/selected by the basic_block class. > > I don't see how this is relevent I hope that the explanation above makes it somewhat clearer. > > > The following > > basic_block pred_bb = (*ei)->src; > > > > can also be written as > > basic_block pred_bb = ei->src; > > > > after converting the edge typedef to a wrapper of edge_def*. > > this is assuming you overload operator -> on the iterator? I'm a c++ guy > not a stl guy, but that seems pretty dubious to me. Yes, that requires overloading of "operator ->". However, in this case not in the iterator, but in the pointer wrapper as I've done it already in the patch for class basic_block (in the file basic_block2.h). This is common practice for pointer wrappers (see e.g. std::shared_ptr). Overloading "operator ->" is also required in iterators. See http://www.cplusplus.com/reference/iterator/ If raw pointers are used as iterators (as in my example patch), there's nothing to overload for those of course. > > The idea of the approach is to allow co-existence of the new > > edge_iterator and the old and thus be able to gradually convert code. > > The wrappers around raw pointers also helo encapsulating the underlying > > memory management issues. For example, it would be much easier to > > replace garbage collected objects with intrusive reference counting. > > I don't think there's actually a memory management issue here, > edge_iterator can only work if you allocate it on the stack since its > not marked for gty, and afaik ggc doesn't scan the stack so the > edge_iterator can't keep the vector alive. Now I think it would be nice > if these vectors moved out of gc memory, but I don't think this is > particularly helpful for that. Sorry, I think I caused a misunderstanding here. By "memory management issue" I just meant the way a container stores its objects, like whether it's storing pointers to garbage collected objects, smart pointers like shared_ptr or whatever. I didn't mean that the iterator should somehow influence the lifetime of the container. Cheers, Oleg Index: gcc/vec.h =================================================================== --- gcc/vec.h (revision 205866) +++ gcc/vec.h (working copy) @@ -482,6 +482,15 @@ void quick_grow (unsigned len); void quick_grow_cleared (unsigned len); + /* STL like iterator interface. */ + typedef T* iterator; + typedef const T* const_iterator; + + iterator begin (void) { return &m_vecdata[0]; } + iterator end (void) { return &m_vecdata[m_vecpfx.m_num]; } + const_iterator begin (void) const { return &m_vecdata[0]; } + const_iterator end (void) const { &m_vecdata[m_vecpfx.m_num]; } This is because raw pointers can be used as random access iterators.