<html><body><p><font size="2" face="Airal">I agree with Reid's suggestion. We can ignore the first stores of arguments into allocas in the SROA analysis.</font><br><br><font size="2" face="Airal">Orthogonal to Reid's suggestion, I implemented another approach to resolve the problem.</font><br><font size="2" face="Airal">This approach is more generic (not limited to arguments), simpler and ABI independent.</font><br><br><font size="2" face="Airal">Currently, SROA splits loads and stores only when they are accessing the whole alloca.</font><br><font size="2" face="Airal">I relax this limitation to split a load/store if all other loads and stores to the alloca are</font><br><font size="2" face="Airal">disjoint to or fully included in the current load/store.</font><br><font size="2" face="Airal">The whole-alloca loads and stores meet this new condition and so they are still splittable.</font><br><font size="2" face="Airal">Does this approach make sense?</font><br><br><font size="2" face="Airal">I updated the patch in Phabricator. </font><a href="https://reviews.llvm.org/D32998"><font size="2" face="Airal">https://reviews.llvm.org/D32998</font></a><br><br><font size="2" face="Airal">Since the new approach is ABI independent, I confirmed that it now works on both x86 and ppc.</font><br><font size="2" face="Airal">With this SROA optimization, the sample program is compiled into only few instructions without loop.</font><br><font size="2" face="Airal">Without the optimization, unnecessary loop-carried dependency is introduced by SROA and </font><br><font size="2" face="Airal">the loop cannot be eliminated by the later optimizers.</font><br><font size="2"><br>-----<br>Hiroshi Inoue <inouehrs@jp.ibm.com><br>IBM Research - Tokyo<br></font><br><br><tt><font size="2">Reid Kleckner <rnk@google.com> wrote on 2017/05/13 07:31:19:<br><br>> From: Reid Kleckner <rnk@google.com></font></tt><br><tt><font size="2">> To: "Friedman, Eli" <efriedma@codeaurora.org></font></tt><br><tt><font size="2">> Cc: Hiroshi 7 Inoue/Japan/IBM@IBMJP, llvm-dev <llvm-dev@lists.llvm.org></font></tt><br><tt><font size="2">> Date: 2017/05/13 07:32</font></tt><br><tt><font size="2">> Subject: Re: [llvm-dev] RFC: SROA for method argument</font></tt><br><tt><font size="2">> <br>> I'll propose a different heuristic. SROA should ignore stores of <br>> arguments into allocas in the entry block when deciding what slices <br>> to form. Such stores happen exactly once, and are usually coercions <br>> that we have to do for ABI reasons. SROA should generate code like <br>> this before promoting allocas to SSA form:</font></tt><br><tt><font size="2">> <br>> define i32 @func(i64 %r.coerce.0, i64 %r.coerce.1) {</font></tt><br><tt><font size="2">> %r.slice.0 = alloca i64</font></tt><br><tt><font size="2">> %r.slice.1 = alloca i32</font></tt><br><tt><font size="2">> %r.slice.2 = alloca i32</font></tt><br><tt><font size="2">> store i64 %r.coerce.0, i64* %r.slice.0</font></tt><br><tt><font size="2">> %r.1.shr = lshr i64 %r.coerce.1, 32</font></tt><br><tt><font size="2">> %r.1 = trunc i64 %r.1.shr</font></tt><br><tt><font size="2">> %r.2 = trunc i64 %r.coerce.1</font></tt><br><tt><font size="2">> store i32 %r.1, i32* %r.slice.1</font></tt><br><tt><font size="2">> store i32 %r.2, i32* %r.slice.2</font></tt><br><tt><font size="2">> ...</font></tt><br><tt><font size="2">> }</font></tt><br><tt><font size="2">> <br>> This is basically "reasoning about the CFG" without actually looking<br>> at loop info. Stores of arguments in the entry block can't be in a <br>> loop. Even if they end up in one after inlining, instcombine should <br>> be able to simplify the {i32,i32}->i64->{i32,i32} code.</font></tt><br><tt><font size="2">> <br>> On Tue, May 9, 2017 at 10:53 AM, Friedman, Eli via llvm-dev <llvm-<br>> dev@lists.llvm.org> wrote:</font></tt><br><tt><font size="2">> On 5/9/2017 6:05 AM, Hiroshi 7 Inoue via llvm-dev wrote:</font></tt><br><tt><font size="2">> Hi,<br>> <br>> I am working to improve SROA to generate better code when a method <br>> has a struct in its arguments. I would appreciate it if I could have<br>> any suggestions or comments on how I can best proceed with this optimization.<br>> <br>> * Problem *<br>> I observed that LLVM often generates redundant instructions around <br>> glibc’s istreambuf_iterator. The problem comes from the scalar <br>> replacement (SROA) for methods with an aggregate as an argument. <br>> Here is a simplified example in C. <br>> <br>> struct record {<br>> long long a;<br>> int b;<br>> int c;<br>> };<br>> <br>> int func(struct record r) {<br>> for (int i = 0; i < r.c; i++)<br>> r.b++;<br>> return r.b;<br>> }<br>> <br>> When updating r.b (or r.c as well), SROA generates redundant <br>> instructions on some platforms (such as x86_64 and ppc64); here, r.b<br>> and r.c are packed into one 64-bit GPR when the struct is passed as <br>> a method argument. The problem is caused when the same memory <br>> location is accessed by load/store instructions of different types.<br>> For this example, CLANG generates following IRs to initialize the <br>> struct for ppc64 and x86_64. For both platforms, the 64-bit value is<br>> stored into memory allocated by alloca first. Later, the same memory<br>> location is accessed as 32-bit integer values (r.b and r.c).<br>> <br>> for ppc64<br>> %struct.record = type { i64, i32, i32 }<br>> <br>> define signext i32 @ppc64le_func([2 x i64] %r.coerce) #0 {<br>> entry:<br>> %r = alloca %struct.record, align 8<br>> %0 = bitcast %struct.record* %r to [2 x i64]*<br>> store [2 x i64] %r.coerce, [2 x i64]* %0, align 8<br>> ....<br>> <br>> for x86_64<br>> define i32 @x86_64_func(i64 %r.coerce0, i64 %r.coerce1) #0 {<br>> entry:<br>> %r = alloca %struct.record, align 8<br>> %0 = bitcast %struct.record* %r to { i64, i64 }*<br>> %1 = getelementptr inbounds { i64, i64 }, { i64, i64 }* %0, i32 0, i32 0<br>> store i64 %r.coerce0, i64* %1, align 8<br>> %2 = getelementptr inbounds { i64, i64 }, { i64, i64 }* %0, i32 0, i32 1<br>> store i64 %r.coerce1, i64* %2, align 8<br>> ....<br>> <br>> For such code sequence, the current SROA generates instructions to <br>> update only upper (or lower) half of the 64-bit value when storing <br>> r.b (or r.c). SROA can split an i64 value into two i32 values under <br>> some conditions (e.g. when the struct contains only int b and int c <br>> in this example), but it is not capable of splitting complex cases.</font></tt><br><tt><font size="2">> When there are accesses of mixed type to an alloca, SROA just treats<br>> the whole alloca as a big integer, and generates PHI nodes <br>> appropriately. In many cases, instcombine would then slice up the <br>> generated PHI nodes to use more appropriate types, but that doesn't <br>> work out here. (See InstCombiner::SliceUpIllegalIntegerPHI.) <br>> Probably the right solution is to make instcombine more aggressive <br>> here; it's hard to come up with a generally useful transform in SROA<br>> without reasoning about control flow.</font></tt><br><tt><font size="2">> -Eli</font></tt><br><tt><font size="2">> -- <br>> Employee of Qualcomm Innovation Center, Inc.<br>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a<br>> Linux Foundation Collaborative Project</font></tt><br><tt><font size="2">> <br>> _______________________________________________<br>> LLVM Developers mailing list<br>> llvm-dev@lists.llvm.org<br>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br></font></tt><BR>
</body></html>