From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 90892 invoked by alias); 14 Dec 2019 17:17:44 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Received: (qmail 90884 invoked by uid 89); 14 Dec 2019 17:17:44 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-6.0 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.1 spammy=HX-Languages-Length:1665, Guaranteed, HContent-Transfer-Encoding:8bit X-HELO: smtp.polymtl.ca Received: from smtp.polymtl.ca (HELO smtp.polymtl.ca) (132.207.4.11) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sat, 14 Dec 2019 17:17:42 +0000 Received: from simark.ca (simark.ca [158.69.221.121]) (authenticated bits=0) by smtp.polymtl.ca (8.14.7/8.14.7) with ESMTP id xBEHHW7T010026 (version=TLSv1/SSLv3 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Sat, 14 Dec 2019 12:17:37 -0500 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp.polymtl.ca xBEHHW7T010026 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=polymtl.ca; s=default; t=1576343858; bh=7DCmUIBYnJrYJqiIAq5TcZ/t84eG6G5KKw3kBO+gDCQ=; h=Subject:To:References:From:Date:In-Reply-To:From; b=tMryz3nNJZkx1LNee3dlEVASnEbB/4kCFJD9tOZ63qrlw+PlFiVWK1KWkZdgmswb4 2jjqS8HVMXo5jIeze+gwPEijIfyM7R5M10rZLQcxhNSYnVVy3kLwv+95U5EJZt/1Cw fz2VmXv3gVOYITcyH7j3GLNQdcJkm2+GCfiE/04c= Received: from [10.0.0.11] (unknown [192.222.164.54]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPSA id 7533D1E08E; Sat, 14 Dec 2019 12:17:32 -0500 (EST) Subject: Re: [PATCH 4/7] jit: make gdb_symtab::blocks a vector To: Pedro Alves , gdb-patches@sourceware.org References: <20191213060323.1799590-1-simon.marchi@polymtl.ca> <20191213060323.1799590-5-simon.marchi@polymtl.ca> From: Simon Marchi Message-ID: <60d0c65c-7bce-798c-8e40-9f139e62ded1@polymtl.ca> Date: Sat, 14 Dec 2019 17:17:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.3.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-IsSubscribed: yes X-SW-Source: 2019-12/txt/msg00663.txt.bz2 On 2019-12-13 5:14 p.m., Pedro Alves wrote: > On 12/13/19 6:03 AM, Simon Marchi wrote: >> I don't think it's true that "next" points to the next node at the same >> depth. It might happen to be true for some nodes, but it can't be true >> in general, as this is a simple linked list containing all the created >> blocks. > > Is this really true? I mean, the comment you're removing talks about > a tree. I see that jit_block_open_impl starts by doing: > > block->next = symtab->blocks; > > but then the else branch writes to blocl->next again: > > /* Guaranteed to terminate, since compare_block (NULL, _) > returns 1. */ > if (compare_block (i->next, block)) > { > block->next = i->next; > > I don't pretend to understand this code, but it does sound like at > least the intention was to have a tree of blocks, which is not > a surprising data structure for blocks. Well, the code builds a singly linked list and takes care of keeping it sorted in the reverse order of the expected order for a blockvector But that doesn't make it a tree. If the JIT generates this code, conceptually: { // A { // B } { // C  } } It could be represented by this tree: A / \ B C The created linked list will be: C -> B -> A Node B points to node A, which doesn't match the comment "Next points to the next node at the same depth as this block". Maybe the original intention of the author was to build an actual tree, where each node has a singly linked list of its children, in which case it would have been true, but then changed the implementation to use a single linked list in reversed blockvector order. Simon