From patchwork Thu May 16 06:33:46 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Xi Wang X-Patchwork-Id: 2575381 Return-Path: X-Original-To: patchwork-linux-sparse@patchwork.kernel.org Delivered-To: patchwork-process-083081@patchwork1.kernel.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by patchwork1.kernel.org (Postfix) with ESMTP id 333FC3FC5A for ; Thu, 16 May 2013 06:35:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755057Ab3EPGf5 (ORCPT ); Thu, 16 May 2013 02:35:57 -0400 Received: from mail-vb0-f46.google.com ([209.85.212.46]:58084 "EHLO mail-vb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753287Ab3EPGf5 (ORCPT ); Thu, 16 May 2013 02:35:57 -0400 Received: by mail-vb0-f46.google.com with SMTP id 10so1127426vbe.33 for ; Wed, 15 May 2013 23:35:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:from:to:cc:subject:date:message-id:x-mailer:mime-version :content-type:content-transfer-encoding; bh=UYOBsel/ppkTjiZ5Ku/5R1hcOZLs8FUOlXZvMHfYFw8=; b=W8Lt9zOb5W62eXEJ2MfXYObXbCVFpNJ7V/YAvlDieRyKnMzr+NhZSFs+vUCb6Jf0fM cgS4jCKkYNgCA/2MolXtvl3AXoMATXcZoAGG+Xw3eqHrCdmNv+vIbGbrLDHfAprcb3ts DZhwKanCYZB4FtaL+Bgcl3knAle7nuPpbyxqgx21Exgv+1tqpx5bf+qqi+QRAjqjNv5J ApaTYugL0aUcsLDm3mIFYl66z7t8E9pO+5FGo+z9ZQSpzFAQCz7Mr2za65meYxGzJrjA 4QXuH1aT+HtsxO4Kx10BLkgZbjQdVD0xh7LWSUECWJXubZ/qECymndM/zhsrGFfsGwlb FrqA== X-Received: by 10.59.0.67 with SMTP id aw3mr5524933ved.21.1368686156199; Wed, 15 May 2013 23:35:56 -0700 (PDT) Received: from hchen.csail.mit.edu (hchen.csail.mit.edu. [18.26.5.5]) by mx.google.com with ESMTPSA id nr3sm6054147veb.4.2013.05.15.23.35.55 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 15 May 2013 23:35:55 -0700 (PDT) From: Xi Wang To: linux-sparse@vger.kernel.org Cc: Xi Wang , Pekka Enberg , Christopher Li , Jeff Garzik , Linus Torvalds , =?UTF-8?q?Jonathan=20Neusch=C3=A4fer?= Subject: [PATCH] sparse, llvm: fix phi generation Date: Thu, 16 May 2013 02:33:46 -0400 Message-Id: <1368686026-10206-1-git-send-email-xi.wang@gmail.com> X-Mailer: git-send-email 1.8.1.2 MIME-Version: 1.0 Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org PHI in LLVM is different from that in sparse. LLVM requires PHI "for each predecessor basic block of the current block" even if the current block doesn't use it. It's tricky to correctly place PHI. This patch implements a simpler and safer strategy: 1) allocate an alloca for each phi, and 2) translate phi/phisrc to load/store alloca. LLVM optimizations will promote load/store to registers. Cc: Pekka Enberg Cc: Christopher Li Cc: Jeff Garzik Cc: Linus Torvalds Cc: Jonathan Neuschäfer Signed-off-by: Xi Wang --- See also https://patchwork.kernel.org/patch/1571821/ --- sparse-llvm.c | 131 ++++++++++++++------------------------------- validation/backend/loop2.c | 14 +++++ 2 files changed, 54 insertions(+), 91 deletions(-) create mode 100644 validation/backend/loop2.c diff --git a/sparse-llvm.c b/sparse-llvm.c index 6f2fbd6..81ac764 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -18,21 +18,11 @@ #include "linearize.h" #include "flow.h" -struct phi_fwd { - struct phi_fwd *next; - - LLVMValueRef phi; - pseudo_t pseudo; - bool resolved; -}; - struct function { LLVMBuilderRef builder; LLVMTypeRef type; LLVMValueRef fn; LLVMModuleRef module; - - struct phi_fwd *fwd_list; }; static inline bool symbol_is_fp_type(struct symbol *sym) @@ -839,100 +829,39 @@ static void output_op_call(struct function *fn, struct instruction *insn) insn->target->priv = target; } -static void store_phi_fwd(struct function *fn, LLVMValueRef phi, - pseudo_t pseudo) -{ - struct phi_fwd *fwd; - - fwd = calloc(1, sizeof(*fwd)); - fwd->phi = phi; - fwd->pseudo = pseudo; - - /* append fwd ref to function-wide list */ - if (!fn->fwd_list) - fn->fwd_list = fwd; - else { - struct phi_fwd *last = fn->fwd_list; - - while (last->next) - last = last->next; - last->next = fwd; - } -} - -static void output_phi_fwd(struct function *fn, pseudo_t pseudo, LLVMValueRef v) -{ - struct phi_fwd *fwd = fn->fwd_list; - - while (fwd) { - struct phi_fwd *tmp; - - tmp = fwd; - fwd = fwd->next; - - if (tmp->pseudo == pseudo && !tmp->resolved) { - LLVMValueRef phi_vals[1]; - LLVMBasicBlockRef phi_blks[1]; - - phi_vals[0] = v; - phi_blks[0] = pseudo->def->bb->priv; - - LLVMAddIncoming(tmp->phi, phi_vals, phi_blks, 1); - - tmp->resolved = true; - } - } -} - static void output_op_phisrc(struct function *fn, struct instruction *insn) { LLVMValueRef v; + struct instruction *phi; assert(insn->target->priv == NULL); /* target = src */ v = pseudo_to_value(fn, insn, insn->phi_src); - insn->target->priv = v; - assert(insn->target->priv != NULL); + FOR_EACH_PTR(insn->phi_users, phi) { + LLVMValueRef load, ptr; - /* resolve forward references to this phi source, if present */ - output_phi_fwd(fn, insn->target, v); + assert(phi->opcode == OP_PHI); + /* phi must be load from alloca */ + load = phi->target->priv; + assert(LLVMGetInstructionOpcode(load) == LLVMLoad); + ptr = LLVMGetOperand(load, 0); + /* store v to alloca */ + LLVMBuildStore(fn->builder, v, ptr); + } END_FOR_EACH_PTR(phi); } static void output_op_phi(struct function *fn, struct instruction *insn) { - pseudo_t phi; - LLVMValueRef target; - - target = LLVMBuildPhi(fn->builder, insn_symbol_type(fn->module, insn), - "phi"); - int pll = 0; - FOR_EACH_PTR(insn->phi_list, phi) { - if (pseudo_to_value(fn, insn, phi)) /* skip VOID, fwd refs*/ - pll++; - } END_FOR_EACH_PTR(phi); - - LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef)); - LLVMBasicBlockRef *phi_blks = calloc(pll, sizeof(LLVMBasicBlockRef)); - - int idx = 0; - FOR_EACH_PTR(insn->phi_list, phi) { - LLVMValueRef v; - - v = pseudo_to_value(fn, insn, phi); - if (v) { /* skip VOID, fwd refs */ - phi_vals[idx] = v; - phi_blks[idx] = phi->def->bb->priv; - idx++; - } - else if (phi->type == PSEUDO_PHI) /* fwd ref */ - store_phi_fwd(fn, target, phi); - } END_FOR_EACH_PTR(phi); - - LLVMAddIncoming(target, phi_vals, phi_blks, pll); - - insn->target->priv = target; + LLVMValueRef load = insn->target->priv; + + /* forward load */ + assert(LLVMGetInstructionOpcode(load) == LLVMLoad); + /* forward load has no parent block */ + assert(!LLVMGetInstructionParent(load)); + /* finalize load in current block */ + LLVMInsertIntoBuilder(fn->builder, load); } static void output_op_ptrcast(struct function *fn, struct instruction *insn) @@ -1095,7 +1024,6 @@ static void output_insn(struct function *fn, struct instruction *insn) assert(0); break; case OP_DEATHNOTE: - assert(0); break; case OP_ASM: assert(0); @@ -1174,11 +1102,30 @@ static void output_fn(LLVMModuleRef module, struct entrypoint *ep) LLVMBasicBlockRef bbr; char bbname[32]; + struct instruction *insn; sprintf(bbname, "L%d", nr_bb++); bbr = LLVMAppendBasicBlock(function.fn, bbname); bb->priv = bbr; + + /* allocate alloca for each phi */ + FOR_EACH_PTR(bb->insns, insn) { + LLVMBasicBlockRef entrybbr; + LLVMTypeRef phi_type; + LLVMValueRef ptr; + + if (!insn->bb || insn->opcode != OP_PHI) + continue; + /* insert alloca into entry block */ + entrybbr = LLVMGetEntryBasicBlock(function.fn); + LLVMPositionBuilderAtEnd(function.builder, entrybbr); + phi_type = insn_symbol_type(module, insn); + ptr = LLVMBuildAlloca(function.builder, phi_type, ""); + /* emit forward load for phi */ + LLVMClearInsertionPosition(function.builder); + insn->target->priv = LLVMBuildLoad(function.builder, ptr, "phi"); + } END_FOR_EACH_PTR(insn); } END_FOR_EACH_PTR(bb); @@ -1267,6 +1214,8 @@ int main(int argc, char **argv) compile(module, sparse_initialize(argc, argv, &filelist)); + /* need ->phi_users */ + dbg_dead = 1; FOR_EACH_PTR_NOTAG(filelist, file) { compile(module, sparse(file)); } END_FOR_EACH_PTR_NOTAG(file); diff --git a/validation/backend/loop2.c b/validation/backend/loop2.c new file mode 100644 index 0000000..279af21 --- /dev/null +++ b/validation/backend/loop2.c @@ -0,0 +1,14 @@ +extern int op(void); + +static void test(void) +{ + int i; + for (i = 0; ; i++) { + op(); + } +} + +/* + * check-name: Loops with unused counter + * check-command: ./sparsec -c $file -o tmp.o + */