From lurker-index@localhost Sat May 10 14:28:15 2008 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.7-deb (2006-10-05) on mail.terpstra.ca X-Spam-Level: X-Spam-Status: No, score=-2.4 required=5.0 tests=AWL,BAYES_00, FORGED_RCVD_HELO autolearn=ham version=3.1.7-deb X-Original-To: wesley@terpstra.ca Delivered-To: wesley@terpstra.ca Received: from mail.terpstra.ca (localhost [127.0.0.1]) by mail.terpstra.ca (Postfix) with ESMTP id DCFF88001E for ; Sat, 10 May 2008 14:28:06 +0200 (CEST) Received: from mlton.org (mail.sweeks.com [69.55.226.86]) by mail.terpstra.ca (Postfix) with ESMTP id A922180001 for ; Sat, 10 May 2008 14:27:56 +0200 (CEST) Received: from localhost.johncompanies.com ([127.0.0.1] helo=mlton.org) by mlton.org with esmtp (Exim 4.50) id 1JuoAu-00038e-Si; Sat, 10 May 2008 05:27:41 -0700 Received: from nagoya.uchicago.edu ([128.135.191.165]) by mlton.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA:32) (Exim 4.50) id 1JuoAr-00038Z-N8 for mlton@mlton.org; Sat, 10 May 2008 05:27:37 -0700 Received: from nagoya.uchicago.edu (localhost.localdomain [127.0.0.1]) by nagoya.uchicago.edu (8.12.8/8.12.8) with ESMTP id m4ADPV0W003746; Sat, 10 May 2008 08:25:31 -0500 Received: from localhost (fluet@localhost) by nagoya.uchicago.edu (8.12.8/8.12.8/Submit) with ESMTP id m4ADPUug003742; Sat, 10 May 2008 08:25:31 -0500 X-Authentication-Warning: nagoya.uchicago.edu: fluet owned process doing -bs Date: Sat, 10 May 2008 08:25:30 -0500 (CDT) From: Matthew Fluet X-X-Sender: fluet@nagoya.uchicago.edu To: Vesa Karvonen Subject: Re: [MLton] Faster dominators for MLton In-Reply-To: <9e43b9a0805061607m27cf7345v6afb85841c674fe8@mail.gmail.com> Message-ID: References: <9e43b9a0805061607m27cf7345v6afb85841c674fe8@mail.gmail.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Cc: MLton X-BeenThere: mlton@mlton.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: mlton.mlton.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: mlton-bounces@mlton.org Errors-To: mlton-bounces@mlton.org On Wed, 7 May 2008, Vesa Karvonen wrote: > I was reading up on compiler optimizations and got interested in the > computation of dominators. So, looking for dominator algorithms, I > stumbled upon the following paper: > > A Simple, Fast Dominance Algorithm. > Keith Cooper and Timothy Harvey and Ken Kennedy. > Software Practice and Experience, 2001. > http://citeseer.ist.psu.edu/cooper01simple.html > http://www.cs.rice.edu/~keith/EMBED/dom.pdf > > The algorithm described in the paper is O(N^2), but the paper reports that > it runs faster, in practice, than the classic Lengauer-Tarjan algorithm. > I was a bit worried by the O(N^2) bound, because, I assume, MLton computes > dominators for the whole program, but decided to try to implement it > anyway. MLton never computes dominators for a graph that corresponds to all the basic blocks in an SSA IL program. For the contification analysis, the dominators are computed on a graph that has nodes equal to the number of SSA IL functions in the program + the number of non-tail transfers in the program; and has edges equal to the number of tail-transfers in the program + 2 * the number of non-tail transfers in the program. Other passes compute the dominator tree on the control-flow-graph of a single SSA IL function: common-subexp, redundant-tests, type-checking. So, a faster dominator algorithm would help in a number of places. I saw the commit to SVN, and think it is a great addition. _______________________________________________ MLton mailing list MLton@mlton.org http://mlton.org/mailman/listinfo/mlton