| Message ID | 1349825676-1713-1-git-send-email-j.neuschaefer@gmx.net (mailing list archive) |
|---|---|
| State | Rejected, archived |
| Headers | show |
On 10/09/2012 07:34 PM, Jonathan Neuschäfer wrote: > This is required for producing valid LLVM bitcode. > > Cc: Pekka Enberg <penberg@kernel.org> > Cc: Christopher Li <sparse@chrisli.org> > Cc: Jeff Garzik <jgarzik@redhat.com> > Cc: Linus Torvalds <torvalds@linux-foundation.org> > Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net> > --- > sparse-llvm.c | 17 ++++++++++++++++- > validation/backend/loop2.c | 13 +++++++++++++ > 2 files changed, 29 insertions(+), 1 deletion(-) > create mode 100644 validation/backend/loop2.c Looks sane... but I did not verify whether or not this reordering is safe -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Oct 10, 2012 at 3:12 AM, Jeff Garzik <jgarzik@pobox.com> wrote: > On 10/09/2012 07:34 PM, Jonathan Neuschäfer wrote: >> >> This is required for producing valid LLVM bitcode. >> >> Cc: Pekka Enberg <penberg@kernel.org> >> Cc: Christopher Li <sparse@chrisli.org> >> Cc: Jeff Garzik <jgarzik@redhat.com> >> Cc: Linus Torvalds <torvalds@linux-foundation.org> >> Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net> >> --- >> sparse-llvm.c | 17 ++++++++++++++++- >> validation/backend/loop2.c | 13 +++++++++++++ >> 2 files changed, 29 insertions(+), 1 deletion(-) >> create mode 100644 validation/backend/loop2.c > > Looks sane... but I did not verify whether or not this reordering is safe Ditto. Jonathan, care to explain why you think it is safe? I still don't know Sparse's linearized IR well enough to convince myself this is OK. -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Oct 10, 2012 at 09:31:31AM +0300, Pekka Enberg wrote: > On Wed, Oct 10, 2012 at 3:12 AM, Jeff Garzik <jgarzik@pobox.com> wrote: > > On 10/09/2012 07:34 PM, Jonathan Neuschäfer wrote: > >> > >> This is required for producing valid LLVM bitcode. > >> > >> Cc: Pekka Enberg <penberg@kernel.org> > >> Cc: Christopher Li <sparse@chrisli.org> > >> Cc: Jeff Garzik <jgarzik@redhat.com> > >> Cc: Linus Torvalds <torvalds@linux-foundation.org> > >> Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net> > >> --- > >> sparse-llvm.c | 17 ++++++++++++++++- > >> validation/backend/loop2.c | 13 +++++++++++++ > >> 2 files changed, 29 insertions(+), 1 deletion(-) > >> create mode 100644 validation/backend/loop2.c > > > > Looks sane... but I did not verify whether or not this reordering is safe > > Ditto. Jonathan, care to explain why you think it is safe? I still > don't know Sparse's linearized IR well enough to convince myself this > is OK. I can't say with certainty that it's safe either, so I probably should have marked the patch with "request for comments". AFAICT there are three reasons an instruction cannot be moved up or down within a basic block: 1. If it takes previous SSA values as arguments, it can't be moved above the corresponding intructions. 2. If its value is used as an argument of an instruction further down in the BB, it can't be moved below that instruction. 3. Swapping two instructions that influence or are influenced by the "global state" (sorry for the loose wording), e.g. by doing memory accesses, performing I/O, or calling functions (which in turn can do about anything in general), is generally unsafe. Case 1 doesn't apply because PHI nodes don't use values computed in the same invocation of their basic block. Case 2 doesn't apply as I'm not moving the PHI nodes down. Case 3 doesn't seem to apply either. That's how I think this patch is safe. HTH, Jonathan -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Oct 10, 2012 at 7:33 PM, Jonathan Neuschäfer <j.neuschaefer@gmx.net> wrote: > I can't say with certainty that it's safe either, so I probably should > have marked the patch with "request for comments". > > AFAICT there are three reasons an instruction cannot be moved up or down > within a basic block: > 1. If it takes previous SSA values as arguments, it can't be moved > above the corresponding intructions. > 2. If its value is used as an argument of an instruction further down > in the BB, it can't be moved below that instruction. > 3. Swapping two instructions that influence or are influenced by the > "global state" (sorry for the loose wording), e.g. by doing memory > accesses, performing I/O, or calling functions (which in turn can > do about anything in general), is generally unsafe. > > Case 1 doesn't apply because PHI nodes don't use values computed in the > same invocation of their basic block. Case 2 doesn't apply as I'm not > moving the PHI nodes down. Case 3 doesn't seem to apply either. > > That's how I think this patch is safe. Sounds plausible but I'm still uneasy with the idea that LLVM backend needs to reshuffle instructions like this. Would it be possible to solve this in the frontend? Pekka -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Oct 12, 2012 at 9:25 PM, Pekka Enberg <penberg@kernel.org> wrote: > On Wed, Oct 10, 2012 at 7:33 PM, Jonathan Neuschäfer > <j.neuschaefer@gmx.net> wrote: >> I can't say with certainty that it's safe either, so I probably should >> have marked the patch with "request for comments". >> >> AFAICT there are three reasons an instruction cannot be moved up or down >> within a basic block: >> 1. If it takes previous SSA values as arguments, it can't be moved >> above the corresponding intructions. >> 2. If its value is used as an argument of an instruction further down >> in the BB, it can't be moved below that instruction. >> 3. Swapping two instructions that influence or are influenced by the >> "global state" (sorry for the loose wording), e.g. by doing memory >> accesses, performing I/O, or calling functions (which in turn can >> do about anything in general), is generally unsafe. >> >> Case 1 doesn't apply because PHI nodes don't use values computed in the >> same invocation of their basic block. Case 2 doesn't apply as I'm not >> moving the PHI nodes down. Case 3 doesn't seem to apply either. >> >> That's how I think this patch is safe. > > Sounds plausible but I'm still uneasy with the idea that LLVM backend > needs to reshuffle instructions like this. > > Would it be possible to solve this in the frontend? Linus, Chris, any thoughts on this? -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 16, 2012 at 08:59:27PM +0300, Pekka Enberg wrote: > On Fri, Oct 12, 2012 at 9:25 PM, Pekka Enberg <penberg@kernel.org> wrote: > > Sounds plausible but I'm still uneasy with the idea that LLVM backend > > needs to reshuffle instructions like this. Actually, the situation of Phi nodes in LLVM is actually slightly more complex: They require "one pair (of value and BB) for each predecessor basic block of the current block"[1]. This mean that we'll sometimes need to insert phi nodes into BBs that don't directly use a value. Consider the following piece of C code: extern int done(void); extern void foo(int); static void test(void) { int i; for (i = 0; ; i++) { if (done()) break; foo(i); } } Running it through test-linearize exhibits the problem: [ I renamed the basic blocks to L0-L3 to increase readability. ] test: .L0: <entry-point> phisrc.32 %phi2(i) <- $0 br .L1 .L1: call.32 %r1 <- done br %r1, .L3, .L2 .L2: phi.32 %r2(i) <- %phi2(i), %phi3(i) call foo, %r2(i) add.32 %r4 <- %r2(i), $1 phisrc.32 %phi3(i) <- %r4 br .L1 .L3: ret To comply with the "LLVM rules" we'd need to move the phi intruction up into "L1". regards, Jonathan -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 10/16/12 4:14 PM, Jonathan Neuschäfer wrote: > Actually, the situation of Phi nodes in LLVM is actually slightly more > complex: They require "one pair (of value and BB) for each predecessor > basic block of the current block"[1]. This mean that we'll sometimes > need to insert phi nodes into BBs that don't directly use a value. I ran into the same problem before. I would suggest a simpler and safer way: don't emit LLVM phi; instead emit load/store (of some alloca). phi => load from some alloca phisrc => store to some alloca You can find sample code from splay here (emit_phi & emit_phisrc): https://github.com/xiw/splay/blob/master/function.c#L356 > Consider the following piece of C code: > > extern int done(void); > extern void foo(int); > > static void test(void) { > int i; > for (i = 0; ; i++) { > if (done()) > break; > foo(i); > } > } This is what splay emits: define internal void @test() { entry: %0 = alloca i32 store i32 0, i32* %0 br label %bb bb: ; preds = %bb1, %entry %1 = call i32 @done() %2 = icmp ne i32 %1, 0 br i1 %2, label %bb2, label %bb1 bb1: ; preds = %bb %3 = load i32* %0 call void @foo(i32 %3) %4 = add nsw i32 %3, 1 store i32 %4, i32* %0 br label %bb bb2: ; preds = %bb ret void } After "-mem2reg" you get: define internal void @test() { entry: br label %bb bb: ; preds = %bb1, %entry %.0 = phi i32 [ 0, %entry ], [ %2, %bb1 ] %0 = call i32 @done() %1 = icmp ne i32 %0, 0 br i1 %1, label %bb2, label %bb1 bb1: ; preds = %bb call void @foo(i32 %.0) %2 = add nsw i32 %.0, 1 br label %bb bb2: ; preds = %bb ret void } - xi -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 10/16/12 4:14 PM, Jonathan Neuschäfer wrote: >> Actually, the situation of Phi nodes in LLVM is actually slightly more >> complex: They require "one pair (of value and BB) for each predecessor >> basic block of the current block"[1]. This mean that we'll sometimes >> need to insert phi nodes into BBs that don't directly use a value. On Tue, Oct 16, 2012 at 11:53 PM, Xi Wang <xi.wang@gmail.com> wrote: > I ran into the same problem before. I would suggest a simpler and safer > way: don't emit LLVM phi; instead emit load/store (of some alloca). > > phi => load from some alloca > phisrc => store to some alloca Is LLVM able to optimize away the allocas and use registers instead in the emitted code? If not, that means we'll spill and reload at every basic block boundary... -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 10/17/12 2:48 AM, Pekka Enberg wrote: > Is LLVM able to optimize away the allocas and use registers instead in > the emitted code? Yes. See the last part of my previous email, no load/store/alloca after LLVM's -mem2reg pass. - xi -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 10/17/12 2:48 AM, Pekka Enberg wrote: >> Is LLVM able to optimize away the allocas and use registers instead in >> the emitted code? On Wed, Oct 17, 2012 at 9:53 AM, Xi Wang <xi.wang@gmail.com> wrote: > Yes. See the last part of my previous email, no load/store/alloca after > LLVM's -mem2reg pass. Right. Jonathan, does Xi's suggestion sound reasonable to you? I'd certainly prefer that over instruction reordering. Pekka -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Oct 17, 2012 at 07:41:52PM +0300, Pekka Enberg wrote: > On 10/17/12 2:48 AM, Pekka Enberg wrote: > >> Is LLVM able to optimize away the allocas and use registers instead in > >> the emitted code? > > On Wed, Oct 17, 2012 at 9:53 AM, Xi Wang <xi.wang@gmail.com> wrote: > > Yes. See the last part of my previous email, no load/store/alloca after > > LLVM's -mem2reg pass. > > Right. Jonathan, does Xi's suggestion sound reasonable to you? I'd > certainly prefer that over instruction reordering. It certainly does. Thanks, Xi! Jonathan -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello, On Tue, Oct 16, 2012 at 11:53 PM, Xi Wang <xi.wang@gmail.com> wrote: > On 10/16/12 4:14 PM, Jonathan Neuschäfer wrote: >> Actually, the situation of Phi nodes in LLVM is actually slightly more >> complex: They require "one pair (of value and BB) for each predecessor >> basic block of the current block"[1]. This mean that we'll sometimes >> need to insert phi nodes into BBs that don't directly use a value. > > I ran into the same problem before. I would suggest a simpler and safer > way: don't emit LLVM phi; instead emit load/store (of some alloca). > > phi => load from some alloca > phisrc => store to some alloca > > You can find sample code from splay here (emit_phi & emit_phisrc): > > https://github.com/xiw/splay/blob/master/function.c#L356 > >> Consider the following piece of C code: >> >> extern int done(void); >> extern void foo(int); >> >> static void test(void) { >> int i; >> for (i = 0; ; i++) { >> if (done()) >> break; >> foo(i); >> } >> } > > This is what splay emits: > > define internal void @test() { > entry: > %0 = alloca i32 > store i32 0, i32* %0 > br label %bb > > bb: ; preds = %bb1, %entry > %1 = call i32 @done() > %2 = icmp ne i32 %1, 0 > br i1 %2, label %bb2, label %bb1 > > bb1: ; preds = %bb > %3 = load i32* %0 > call void @foo(i32 %3) > %4 = add nsw i32 %3, 1 > store i32 %4, i32* %0 > br label %bb > > bb2: ; preds = %bb > ret void > } > > After "-mem2reg" you get: > > define internal void @test() { > entry: > br label %bb > > bb: ; preds = %bb1, %entry > %.0 = phi i32 [ 0, %entry ], [ %2, %bb1 ] > %0 = call i32 @done() > %1 = icmp ne i32 %0, 0 > br i1 %1, label %bb2, label %bb1 > > bb1: ; preds = %bb > call void @foo(i32 %.0) > %2 = add nsw i32 %.0, 1 > br label %bb > > bb2: ; preds = %bb > ret void > } Ping, anyone interested in turning Xi's suggestion into a patch against current sparse master? Pekka -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, May 15, 2013 at 8:05 AM, Pekka Enberg <penberg@kernel.org> wrote: > Ping, anyone interested in turning Xi's suggestion into a patch > against current sparse master? I'll send a patch. -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/sparse-llvm.c b/sparse-llvm.c index 0fc0dae..2048a1b 100644 --- a/sparse-llvm.c +++ b/sparse-llvm.c @@ -1111,16 +1111,31 @@ static void output_insn(struct function *fn, struct instruction *insn) static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation) { struct instruction *insn; + struct instruction_list *remaining = NULL; bb->generation = generation; + /* + * LLVM requires the phi instructions to be grouped at the top of each + * basic block. + */ + FOR_EACH_PTR(bb->insns, insn) { if (!insn->bb) continue; - output_insn(fn, insn); + if (insn->opcode == OP_PHI) + output_insn(fn, insn); + else + add_instruction(&remaining, insn); } END_FOR_EACH_PTR(insn); + + FOR_EACH_PTR(remaining, insn) { + output_insn(fn, insn); + } END_FOR_EACH_PTR(insn); + + free_ptr_list(&remaining); } #define MAX_ARGS 64 diff --git a/validation/backend/loop2.c b/validation/backend/loop2.c new file mode 100644 index 0000000..4e44a15 --- /dev/null +++ b/validation/backend/loop2.c @@ -0,0 +1,13 @@ +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 + */
This is required for producing valid LLVM bitcode. Cc: Pekka Enberg <penberg@kernel.org> Cc: Christopher Li <sparse@chrisli.org> Cc: Jeff Garzik <jgarzik@redhat.com> Cc: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net> --- sparse-llvm.c | 17 ++++++++++++++++- validation/backend/loop2.c | 13 +++++++++++++ 2 files changed, 29 insertions(+), 1 deletion(-) create mode 100644 validation/backend/loop2.c