From patchwork Wed Aug 16 15:34:47 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 9904001 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 9B31660231 for ; Wed, 16 Aug 2017 15:35:47 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8D3A222B27 for ; Wed, 16 Aug 2017 15:35:47 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 824E1286AC; Wed, 16 Aug 2017 15:35:47 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.3 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RCVD_IN_SORBS_SPAM, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1B05122B27 for ; Wed, 16 Aug 2017 15:35:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751578AbdHPPfq (ORCPT ); Wed, 16 Aug 2017 11:35:46 -0400 Received: from mail-wr0-f196.google.com ([209.85.128.196]:38008 "EHLO mail-wr0-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751580AbdHPPfq (ORCPT ); Wed, 16 Aug 2017 11:35:46 -0400 Received: by mail-wr0-f196.google.com with SMTP id g32so3684483wrd.5 for ; Wed, 16 Aug 2017 08:35:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=BzFGqzTdEhKORL82PB+lKLAFI+TYdRN0yJxKQJDcXhg=; b=VnK8oAlrFrxCZKIxEM++JEIdVD6FdwmQBqgQxasN9GH156En5klZEeSNxwPyxL2o8Q mdZ+4T86f5ab+DrVFRFwXKGJ1oHXE3j1viOb52YInqHJcKpVzSEn8f/0z33EAi1AMpp+ k4e0+9S1vOsEz76Ury4RcYK1oh36nD9Kt1OrO0T2sw5t6XeUJej+w7hlRxhRDOcRbdrF c395mzX4qP8zJ7Jr8EDlKLs40RuG7xlZy/8ibDjc0bcrRL7ll99yf/JaaLrHQgX5LMde cQQl1eO9bmjW6j6s6XARNvnK8mP0/5qm2Q5QD8yA3gdakOrxc3q0gGuhIkKjWnJJPmYJ f8Ig== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=BzFGqzTdEhKORL82PB+lKLAFI+TYdRN0yJxKQJDcXhg=; b=MpXcnNORleJnPW55BIQn0GbGTQIVHivFhyqhMdev9glgUT0hDx8k3ojQaA/gSXu/TQ 3k0r7LKvIHnJRkvH3nIyrhmfrI4unSmKiZlaDfJMCAfgeip7lQYHMESv4BRWfhyVAbPb H6wVK30J02qaqa73uBwcIyTjMRSkR6H7N6euY8mJxZLks4klyjcl86PdA9c9HDLJQhvI CS8HBXRSfgDy3zvnViasZj8CIsdCHXT5m1J6xCA2e4UAs1Ax4wcv9XE7UwPx0XHlH03E gf8CM4qKFTf0Dkw9kcG4nWEAOIYNR6BzTBWi8NqGfvldtsb7w0Um9XlCAE7cVoV2ssPh xTvw== X-Gm-Message-State: AHYfb5iPb2Hyqpiz4ojhn8oLCh5QApbpd/HXXZm5RRGop5Te7vjCyeMF UlEik0zu4OpKf++CRJQ= X-Received: by 10.80.175.198 with SMTP id h64mr2356003edd.131.1502897744850; Wed, 16 Aug 2017 08:35:44 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:4076:600:895a:bb88:13f:9772]) by smtp.gmail.com with ESMTPSA id y19sm690635edi.6.2017.08.16.08.35.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 16 Aug 2017 08:35:44 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Linus Torvalds , Christopher Li , Luc Van Oostenryck Subject: [PATCH 21/29] sssa: add basic implementation Date: Wed, 16 Aug 2017 17:34:47 +0200 Message-Id: <20170816153455.97693-22-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.14.0 In-Reply-To: <20170816153455.97693-1-luc.vanoostenryck@gmail.com> References: <20170816153455.97693-1-luc.vanoostenryck@gmail.com> Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP This a direct implementation of the pseudo-code for the new SSA construction method a described in it's paper: "Simple and Efficient Construction of Static Single Assignment Form" by Matthias Braun, Sebastian Buchwald, Sebastian Hack, Roland Leissa, Christoph Mallon and Andreas Zwinkau. [cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf] Signed-off-by: Luc Van Oostenryck --- Makefile | 1 + ssa.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 99 insertions(+) create mode 100644 ssa.c diff --git a/Makefile b/Makefile index 762aee505..bcd7ab7da 100644 --- a/Makefile +++ b/Makefile @@ -118,6 +118,7 @@ LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \ char.o sort.o allocate.o compat-$(OS).o ptrlist.o \ builtin.o \ ptrmap.o \ + ssa.o \ stats.o \ flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o diff --git a/ssa.c b/ssa.c new file mode 100644 index 000000000..32e440669 --- /dev/null +++ b/ssa.c @@ -0,0 +1,98 @@ +/* + * This is an implementation of the SSA construction algorithm: + * "Simple and Efficient Construction of Static Single Assignment Form" + * by Matthias Braun, Sebastian Buchwald, Sebastian Hack, Roland Leissa, + * Christoph Mallon and Andreas Zwinkau. + * cfr. http://www.cdl.uni-saarland.de/papers/bbhlmz13cc.pdf + */ + +#include "ssa.h" +#include "linearize.h" +#include "flow.h" +#include "lib.h" +#include + + +// FIXME: -> common file +static void append_instruction(struct basic_block *bb, struct instruction *insn) +{ + struct instruction *br = delete_last_instruction(&bb->insns); + insn->bb = bb; + add_instruction(&bb->insns, insn); + add_instruction(&bb->insns, br); +} + +static pseudo_t add_phi_operand(struct symbol *var, pseudo_t phi) +{ + struct instruction *node = phi->def; + struct basic_block *parent; + + FOR_EACH_PTR(node->bb->parents, parent) { + pseudo_t val = load_var(parent, var); + struct instruction *phisrc = alloc_phisrc(val, var); + pseudo_t src = phisrc->target; + append_instruction(parent, phisrc); + use_pseudo(node, src, add_pseudo(&node->phi_list, src)); + } END_FOR_EACH_PTR(parent); + return phi; +} + +static pseudo_t load_var_parents(struct basic_block *bb, struct symbol *var) +{ + pseudo_t val; + + if (!bb->sealed) { // incomplete CFG + val = insert_phi_node(bb, var); + val->def->var = var; + goto out; + } + + switch (bb_list_size(bb->parents)) { + case 0: // never defined + val = undef_pseudo(); + break; + case 1: // no phi needed + val = load_var(first_basic_block(bb->parents), var); + break; + default: + val = insert_phi_node(bb, var); + store_var(bb, var, val); + val = add_phi_operand(var, val); + } + +out: + store_var(bb, var, val); + return val; +} + +pseudo_t load_var(struct basic_block *bb, struct symbol *var) +{ + pseudo_t val = phi_map_lookup(var->phi_map, bb); + if (!val) + val = load_var_parents(bb, var); + return val; +} + +void store_var(struct basic_block *bb, struct symbol *var, pseudo_t val) +{ + phi_map_update(&var->phi_map, bb, val); +} + +void seal_bb(struct basic_block *bb) +{ + struct instruction *insn; + if (bb->sealed) + return; + FOR_EACH_PTR(bb->insns, insn) { + struct symbol *var; + if (!insn->bb) + continue; + if (insn->opcode != OP_PHI) + break; + var = insn->var; + assert(var); + insn->var = NULL; + add_phi_operand(var, insn->target); + } END_FOR_EACH_PTR(insn); + bb->sealed = 1; +}