From patchwork Tue Nov 18 17:29:43 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Lance Taylor X-Patchwork-Id: 412111 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)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id EE05D14017E for ; Wed, 19 Nov 2014 04:30:11 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:date:message-id:subject:from:to:content-type; q= dns; s=default; b=jXczDuVl7NkbQDtoLtb0IYWvAlmT9rLs0YrCz94iyrbVZ0 YTtMZy8V7V95UlJ4iCYs7Xgt6XnZ4S/n+pQha0KgRxyfhTETnkEnNSsMRrkj/VK+ WoXlTPooPRtIjLvk0cqBIfOBWnwb/VfqXW/Ncpg9MBfBs4COdIjqcGJuGv+Kw= 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 :mime-version:date:message-id:subject:from:to:content-type; s= default; bh=PU25CiyIZbCMv5Ot4be334LmDm0=; b=PK1+ky0IDZlL/YtjB8kg nE1Oe1b+qYMGjWg/RWcfc6OlQNbmqSjALCQy7kAXL7LpWKZL7an95/6i5dtEHB38 1Pckb2mnD0ekggNLSKaHTU5VE8i0tX/LegR/3rZzL9Oht8YAdt/HiIU0s7lFD/6c DEnIrk2f9GiyQZHBJ+xMSXw= Received: (qmail 25281 invoked by alias); 18 Nov 2014 17:29:53 -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 25164 invoked by uid 89); 18 Nov 2014 17:29:51 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.4 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-yk0-f172.google.com Received: from mail-yk0-f172.google.com (HELO mail-yk0-f172.google.com) (209.85.160.172) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 18 Nov 2014 17:29:46 +0000 Received: by mail-yk0-f172.google.com with SMTP id 131so2571053ykp.31 for ; Tue, 18 Nov 2014 09:29:44 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:date:message-id:subject:from:to :content-type; bh=mT06vv8ZZATg3vRz/9Ptz2Znt7FEdvEvna/bxyjqe24=; b=eAZ+Ec5x2w7TAmIhmyachfl8o8JCa2RMWkQmKdrmZrJ3S6ms1VKsdEsYnO2msofYxg lGbagKdCF4Pd+VUk9h9UAca4Hz0zvGhz5C3z2EH47YXYJhrJnDucrOAqBjI5fOKgm+Xn 3255r/anatrcbeqvyCQ0Ot8Xn3sRKU+LJREn0YktanNy7LHGs4RpM3fEkAKIpUY26tMz mM+ShN9+VCilOI31yvaPdXghSHxcrEwPbT63HtiqgUsbXb2yUmSY8i2yzP9RYziaWwxy RngOXhC1T90UkhjyBR7a/vEbn834ksNrh8iVv0/PewoisiJlBrDhKOC+hB1M+c/nzK6a CAGQ== X-Gm-Message-State: ALoCoQnPV4sgXEh00rxPexdB4ImAqEZKRF6r3QwgA4wC69n7SEz3RVjN1p6HP9c6GIQ/r5UibbmW MIME-Version: 1.0 X-Received: by 10.236.13.17 with SMTP id a17mr5886486yha.10.1416331784503; Tue, 18 Nov 2014 09:29:44 -0800 (PST) Received: by 10.170.136.199 with HTTP; Tue, 18 Nov 2014 09:29:43 -0800 (PST) Date: Tue, 18 Nov 2014 09:29:43 -0800 Message-ID: Subject: Go patch committed: Fix initialization order From: Ian Taylor To: gcc-patches , "gofrontend-dev@googlegroups.com" The Go frontend was slightly incorrect in the way that it handled the order of initialization (http://golang.org/issue/8052). Fortunately it rarely made a difference in real code. This patch by Chris Manghane fixes it. Bootstrapped and ran Go testsuite on x86_64-unknown-linux-gnu. Committed to mainline. Ian diff -r 82f97044669e go/gogo.cc --- a/go/gogo.cc Fri Nov 14 10:02:13 2014 -0800 +++ b/go/gogo.cc Tue Nov 18 09:02:23 2014 -0800 @@ -1018,11 +1018,11 @@ { public: Var_init() - : var_(NULL), init_(NULL) + : var_(NULL), init_(NULL), dep_count_(0) { } Var_init(Named_object* var, Bstatement* init) - : var_(var), init_(init) + : var_(var), init_(init), dep_count_(0) { } // Return the variable. @@ -1035,13 +1035,38 @@ init() const { return this->init_; } + // Return the number of remaining dependencies. + size_t + dep_count() const + { return this->dep_count_; } + + // Increment the number of dependencies. + void + add_dependency() + { ++this->dep_count_; } + + // Decrement the number of dependencies. + void + remove_dependency() + { --this->dep_count_; } + private: // The variable being initialized. Named_object* var_; // The initialization statement. Bstatement* init_; + // The number of initializations this is dependent on. A variable + // initialization should not be emitted if any of its dependencies + // have not yet been resolved. + size_t dep_count_; }; +// For comparing Var_init keys in a map. + +inline bool +operator<(const Var_init& v1, const Var_init& v2) +{ return v1.var()->name() < v2.var()->name(); } + typedef std::list Var_inits; // Sort the variable initializations. The rule we follow is that we @@ -1052,14 +1077,21 @@ static void sort_var_inits(Gogo* gogo, Var_inits* var_inits) { + if (var_inits->empty()) + return; + typedef std::pair No_no; typedef std::map Cache; Cache cache; - Var_inits ready; - while (!var_inits->empty()) - { - Var_inits::iterator p1 = var_inits->begin(); + // A mapping from a variable initialization to a set of + // variable initializations that depend on it. + typedef std::map > Init_deps; + Init_deps init_deps; + for (Var_inits::iterator p1 = var_inits->begin(); + p1 != var_inits->end(); + ++p1) + { Named_object* var = p1->var(); Expression* init = var->var_value()->init(); Block* preinit = var->var_value()->preinit(); @@ -1067,11 +1099,13 @@ // Start walking through the list to see which variables VAR // needs to wait for. - Var_inits::iterator p2 = p1; - ++p2; - - for (; p2 != var_inits->end(); ++p2) + for (Var_inits::iterator p2 = var_inits->begin(); + p2 != var_inits->end(); + ++p2) { + if (var == p2->var()) + continue; + Named_object* p2var = p2->var(); No_no key(var, p2var); std::pair ins = @@ -1080,6 +1114,10 @@ ins.first->second = expression_requires(init, preinit, dep, p2var); if (ins.first->second) { + // VAR depends on P2VAR. + init_deps[*p2].insert(&(*p1)); + p1->add_dependency(); + // Check for cycles. key = std::make_pair(p2var, var); ins = cache.insert(std::make_pair(key, false)); @@ -1100,36 +1138,66 @@ p2var->message_name().c_str()); p2 = var_inits->end(); } - else - { - // We can't emit P1 until P2 is emitted. Move P1. - Var_inits::iterator p3 = p2; - ++p3; - var_inits->splice(p3, *var_inits, p1); - } - break; } } - - if (p2 == var_inits->end()) + } + + // If there are no dependencies then the declaration order is sorted. + if (!init_deps.empty()) + { + // Otherwise, sort variable initializations by emitting all variables with + // no dependencies in declaration order. VAR_INITS is already in + // declaration order. + Var_inits ready; + while (!var_inits->empty()) { - // VAR does not depends upon any other initialization expressions. - - // Check for a loop of VAR on itself. We only do this if - // INIT is not NULL and there is no dependency; when INIT is - // NULL, it means that PREINIT sets VAR, which we will - // interpret as a loop. - if (init != NULL && dep == NULL - && expression_requires(init, preinit, NULL, var)) - error_at(var->location(), - "initialization expression for %qs depends upon itself", - var->message_name().c_str()); - ready.splice(ready.end(), *var_inits, p1); + Var_inits::iterator v1;; + for (v1 = var_inits->begin(); v1 != var_inits->end(); ++v1) + { + if (v1->dep_count() == 0) + break; + } + go_assert(v1 != var_inits->end()); + + // V1 either has no dependencies or its dependencies have already + // been emitted, add it to READY next. When V1 is emitted, remove + // a dependency from each V that depends on V1. + ready.splice(ready.end(), *var_inits, v1); + + Init_deps::iterator p1 = init_deps.find(*v1); + if (p1 != init_deps.end()) + { + std::set resolved = p1->second; + for (std::set::iterator pv = resolved.begin(); + pv != resolved.end(); + ++pv) + (*pv)->remove_dependency(); + init_deps.erase(p1); + } } - } - - // Now READY is the list in the desired initialization order. - var_inits->swap(ready); + var_inits->swap(ready); + go_assert(init_deps.empty()); + } + + // VAR_INITS is in the correct order. For each VAR in VAR_INITS, + // check for a loop of VAR on itself. We only do this if + // INIT is not NULL and there is no dependency; when INIT is + // NULL, it means that PREINIT sets VAR, which we will + // interpret as a loop. + for (Var_inits::const_iterator p = var_inits->begin(); + p != var_inits->end(); + ++p) + { + Named_object* var = p->var(); + Expression* init = var->var_value()->init(); + Block* preinit = var->var_value()->preinit(); + Named_object* dep = gogo->var_depends_on(var->var_value()); + if (init != NULL && dep == NULL + && expression_requires(init, preinit, NULL, var)) + error_at(var->location(), + "initialization expression for %qs depends upon itself", + var->message_name().c_str()); + } } // Write out the global definitions.