From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 30228 invoked by alias); 14 Aug 2014 16:53:46 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 30212 invoked by uid 89); 14 Aug 2014 16:53:44 -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,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-vc0-f175.google.com Received: from mail-vc0-f175.google.com (HELO mail-vc0-f175.google.com) (209.85.220.175) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Thu, 14 Aug 2014 16:53:42 +0000 Received: by mail-vc0-f175.google.com with SMTP id ik5so1710152vcb.20 for ; Thu, 14 Aug 2014 09:53:40 -0700 (PDT) X-Received: by 10.52.137.2 with SMTP id qe2mr9382529vdb.11.1408035219914; Thu, 14 Aug 2014 09:53:39 -0700 (PDT) MIME-Version: 1.0 Received: by 10.52.22.52 with HTTP; Thu, 14 Aug 2014 09:53:19 -0700 (PDT) In-Reply-To: <53E4A5D1.8050007@samsung.com> References: <53E4A5D1.8050007@samsung.com> From: Konstantin Serebryany Date: Thu, 14 Aug 2014 16:53:00 -0000 Message-ID: Subject: Re: [PATCH] Asan static optimization (draft) To: Yury Gribov Cc: GCC Patches , Jakub Jelinek , Marek Polacek , Dmitry Vyukov , Dodji Seketeli , Yuri Gribov , Viacheslav Garbuzov Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2014-08/txt/msg01500.txt.bz2 Indeed, thanks for working on this. We've been wanting such optimization phase from day one, but never got to implementing it (except for a few simple ones). https://code.google.com/p/address-sanitizer/wiki/CompileTimeOptimizations There have been several attempts outside of our team to do such optimizations, but none of them made it to llvm trunk. In order for your work to be generally useful, I'd ask several things: - Update https://code.google.com/p/address-sanitizer/wiki/CompileTimeOptimizations with examples that will be handled - Create small standalone test cases in C - Don't put the tests under GPL (otherwise we'll not be able to reuse them in LLVM) >> make sure that sanopt performs conservative optimization Yes. I don't know a good solution to this problem, which is why we did not attack it before. Increasing asan speed will save lots of CPU time, but missing a single software bug due to an overly aggressive optimization may cost much more. We can do a detailed analysis of *simple* peephole-like optimizers, but *proving* that a complex optimizer does not remove needed checks is hardly practically possible. On Fri, Aug 8, 2014 at 3:26 AM, Yury Gribov wrote: > Hi all, > > I have been working on Asan global optimization pass lately. The goal is to > remove redundant Asan checks from sanitized code. This should hopefully > reduce Asan's speed/size overhead (which is currently ~2x). The patch is not > yet ready for trunk (e.g. I haven't done bootstrap, etc. but Asan testsuite > passed wo errors) but I thought I'd send it for preliminary review of > algorithm and data structures (*). > > Current implementation (based on existing sanopt pass) uses a simple > iterative intra-procedural dataflow to compute information about living > checks. For each pointer we track the size of memory that was already > checked for it. During dataflow iterations, living checks are merged at > blocks start in a natural way. > > I decided to keep current (local) Asan optimizations because they reduce > compilation time by dropping many obviously redundant checks much earlier in > the compilation pipeline. > > Current results seem to be encouraging: the pass was able to remove 112 > checks (out of 1768) in gcc/asan.c without significant increase in sanopt > pass runtime. > > Before upstreaming this code, I plan to > 1) develop extensive set of tests to make sure that sanopt performs > conservative optimization i.e. does not remove checks too agressively (I > guess this is a critically important prerequisite so any suggestions are > welcomed) > 2) disable optimizations for very large functions to avoid unbearable > compile times > 3) do detailed performance and efficiency measuments for Asan-bootstrap > > I also have some ideas for improving this code (and I'm certainly open to > suggestions from community): > 1) propagating checking information through assignments and PHI-nodes (and > maybe even pointer arithmetic) should improve efficiency > 2) ditto for optimization of symbolic ranges; actually this looks like a > relatively easy addition to current code (I just need to keep a list of > checked symbolic ranges to check_info structure) > 3) in addition to redundant check removal, we could also move duplicate > checks from e.g. branches of if-statement to their dominators. > > -Y > > (*) The patch relies on some additional changes in hash-table and CFG which > have not yet been upstreamed so it won't go with current trunk.