Re: [RFC] sparse SSA construction

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Hi Chris,

On 16 August 2017 at 05:58, Christopher Li <sparse@xxxxxxxxxxx> wrote:
> On Wed, Aug 16, 2017 at 12:23 AM, Christopher Li <sparse@xxxxxxxxxxx> wrote:
>> If sparse only place the phi node on where the loads are, which a lot of
>> case happen to be the DF (dominance frontier). In the case that DF
>> does not have loads, that is where current sparse do wrong, sparse
>> does not place a phi node  there. Which violate the SSA property.
>
> I give an example for the above situation I am talking about:
>
> int a, b, c, d;
>
> void foo(void)
> {
>   int e, f;
>   if (a)
>      e = b;
>   else
>      e = c;
>   if (b)
>      c = a+b;
>   d = e;
> }
>
> "if (b)" is where the dominance of "e = b" and "e =c" joined.
> I don't do any loading of "e" there.
> To insert some blocks before using "e", I use the "if (b)".
>

> Now let's look at the test-linearize output:

I think the linear output you obtained was post simplification. We
need to look at the output prior to any simplifications. I believe it
looks like this:

foo:
.L0:
        <entry-point>
        load.32     %r1 <- 0[a]
        cbr         %r1, .L1, .L2

.L1:
        load.32     %r2 <- 0[b]
        store.32    %r2 -> 0[e]
        br          .L3

.L2:
        load.32     %r3 <- 0[c]
        store.32    %r3 -> 0[e]
        br          .L3

.L3:
        load.32     %r4 <- 0[b]
        cbr         %r4, .L4, .L5

.L4:
        load.32     %r5 <- 0[a]
        load.32     %r6 <- 0[b]
        add.32      %r7 <- %r5, %r6
        store.32    %r7 -> 0[c]
        br          .L5

.L5:
        load.32     %r8 <- 0[e]
        store.32    %r8 -> 0[d]
        br          .L6

.L6:
        ret

And here is the output from the new SSA construction:

foo:
.L0:
        <entry-point>
        load.32     %r1 <- 0[a]
        cbr         %r1, .L1, .L2

.L1:
        load.32     %r2 <- 0[b]
        phisrc.32   %phi1(e) <- %r2
        br          .L3

.L2:
        load.32     %r3 <- 0[c]
        phisrc.32   %phi2(e) <- %r3
        br          .L3

.L3:
        phi.32      %r9(e) <- %phi1(e), %phi2(e)
        load.32     %r4 <- 0[b]
        cbr         %r4, .L4, .L5

.L4:
        load.32     %r5 <- 0[a]
        load.32     %r6 <- 0[b]
        add.32      %r7 <- %r5, %r6
        store.32    %r7 -> 0[c]
        br          .L5

.L5:
        store.32    %r9(e) -> 0[d]
        br          .L6

.L6:
        ret

Finally here is what clang does after some phases (initially clang
starts with local vars).

*** IR Dump After SROA ***
; Function Attrs: nounwind
define void @foo() #0 {
entry:
  %0 = load i32, i32* @a, align 4, !tbaa !1
  %tobool = icmp ne i32 %0, 0
  br i1 %tobool, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  %1 = load i32, i32* @b, align 4, !tbaa !1
  br label %if.end

if.else:                                          ; preds = %entry
  %2 = load i32, i32* @c, align 4, !tbaa !1
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then
  %e.0 = phi i32 [ %1, %if.then ], [ %2, %if.else ]
  %3 = load i32, i32* @b, align 4, !tbaa !1
  %tobool1 = icmp ne i32 %3, 0
  br i1 %tobool1, label %if.then2, label %if.end3

if.then2:                                         ; preds = %if.end
  %4 = load i32, i32* @a, align 4, !tbaa !1
  %5 = load i32, i32* @b, align 4, !tbaa !1
  %add = add nsw i32 %4, %5
  store i32 %add, i32* @c, align 4, !tbaa !1
  br label %if.end3

if.end3:                                          ; preds = %if.then2, %if.end
  store i32 %e.0, i32* @d, align 4, !tbaa !1
  ret void
}

Regards
Dibyendu
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html



[Index of Archives]     [Newbies FAQ]     [LKML]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Trinity Fuzzer Tool]

  Powered by Linux