[SSAUpdaterImpl] Do not generate phi node with all the same incoming values

[skatkov]

Summary

If all available vals to basic block are the same - do not build new phi node and
just use this value.

[djtodoro]

This is interesting! Can you please make a simple/dedicated LLVM IR case for this only, so we can go over the example to get the whole picture?

[skatkov]

In D126525#3542391, @djtodoro wrote:

This is interesting! Can you please make a simple/dedicated LLVM IR case for this only, so we can go over the example to get the whole picture?

llvm/test/CodeGen/AArch64/tail-dup-redundant-phi.mir is dedicated test for this patch and https://reviews.llvm.org/D126523. This test is not landed yet. I just uploaded it here as diff to show the difference.

[sameerds]

Requesting @arsenm to take a look at the AMDGPU test.

llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h

332

Is this assert really needed? For someone unfamiliar with this code (like me), seeing this assert creates a doubt about the surrounding code ... as if there are complicated paths reaching here, where it might be possible that the BBInfo may be in an invalid state at this point.

338

Is this assert really needed?

347

When is "Info->AvailableVal" assigned? If it's the same as the previous statement, then the implicit identity relationship between BBMap[Info->BB] and Info is quite confusing. Can this function be rewritten to consistently use just one of these two expressions?

[sameerds]

In D126525#3544805, @skatkov wrote:

In D126525#3542391, @djtodoro wrote:

This is interesting! Can you please make a simple/dedicated LLVM IR case for this only, so we can go over the example to get the whole picture?

llvm/test/CodeGen/AArch64/tail-dup-redundant-phi.mir is dedicated test for this patch and https://reviews.llvm.org/D126523. This test is not landed yet. I just uploaded it here as diff to show the difference.

Even then, a target independent test in LLVM IR will certainly be useful.

[skatkov]

llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h

332

This is more or less paranoid. The comment for BBInfo class states that predecessor info is a cache to speedup predecessor traversal.
So with this assert I'd like to ensure that the cache is filled. If it confuses I can remove an assert.

338

Is this assert really needed?

ditto

347

When is "Info->AvailableVal" assigned? If it's the same as the previous statement, then the implicit identity relationship between BBMap[Info->BB] and Info is quite confusing. Can this function be rewritten to consistently use just one of these two expressions?

Incoming Info object comes from BlockList which is filled in BuildBlockList where BBMap is filled. So in reality BBMap[Info->BB] == Info and this is something complicated traversal, so I've added the assert above.

I wrote the code in this way to ensure that all "outer" data structures are filled.

[skatkov]

In D126525#3544896, @sameerds wrote:

In D126525#3544805, @skatkov wrote:

In D126525#3542391, @djtodoro wrote:

This is interesting! Can you please make a simple/dedicated LLVM IR case for this only, so we can go over the example to get the whole picture?

llvm/test/CodeGen/AArch64/tail-dup-redundant-phi.mir is dedicated test for this patch and https://reviews.llvm.org/D126523. This test is not landed yet. I just uploaded it here as diff to show the difference.

Even then, a target independent test in LLVM IR will certainly be useful.

That would be good but SSA Updater is not triggered directly as a pass. I found the motivation case in tailduplication codegen pass, so I've written it in mir format. Writing it in LLVM IR will just include a lot of other passes where the changes might disappear the case I'm testing. I though the more precise test is better than something general.

If you'd like I can try to create unittest triggering directly SSA Updater.

[sameerds]

llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h

332

Yeah, I think we should not have this assert. Cache or not, it is quite reasonable to bravely work under the assumption that the array contains valid elements if NumPreds is non-zero. If the cache were unreliable, then there should be a function such as "fetchPreds" or something, to be called by any point in code where the preds must be valid.

347

I don't think there is any side-effect in the BBMap container other than this one pointer being updated. I think it's more readable to update only Info. If it is useful to be paranoid, then the assert should be on "BBMap[Info->BB] == Info".

[sameerds]

In D126525#3544916, @skatkov wrote:

In D126525#3544896, @sameerds wrote:

Even then, a target independent test in LLVM IR will certainly be useful.

That would be good but SSA Updater is not triggered directly as a pass. I found the motivation case in tailduplication codegen pass, so I've written it in mir format. Writing it in LLVM IR will just include a lot of other passes where the changes might disappear the case I'm testing. I though the more precise test is better than something general.

If you'd like I can try to create unittest triggering directly SSA Updater.

I see now. I looked into the places where SSAUpdater is used, and I am okay with not having an LLVM IR or unit test here.

[skatkov]

remove redundant asserts, add usage of defBB.

[sameerds]

The code looks okay to me, but still need @arsenm to check the effect on the AMDGPU lit test. There seem to be superficial changes to the control flow, but Matt might be able to say whether the test still serves its original purpose after this change.

[skatkov]

Thanks! I'll wait for 1-2 days for @arsenm feedback before landing the patch.

If you do not mind, may I ask you to look at https://reviews.llvm.org/D126523. It is pretty close but after this patch, that patch might be considered as compile time improvement.

[djtodoro]

llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h

327

Nit: s/val/value/

342

I'd like a message with more description.

367

Nit: s/val/value/

[skatkov]

Handled comments

[skatkov]

ok, I take a liberty to land this and ready to revert or follow-up basing on @arsenm feedback.

llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h

do {
         if (NewDefBB != Info->DefBB) {
           Info->DefBB = NewDefBB;
           Changed = true;
         }
       }
     } while (Changed);
   }
 
+  /// Check all predecessors and if all of them has the same AvailableVal
+  /// then return it.
+  bool FindSingularVal(BBInfo *Info) {
+    if (!Info->NumPreds)
+      return false;
+    BBInfo *PredInfo = Info->Preds[0];
+    assert(PredInfo && "Pred Info?");
+    if (!PredInfo->AvailableVal)
+      return false;
+    ValT Singular = PredInfo->AvailableVal;
+    for (unsigned Idx = 1; Idx < Info->NumPreds; ++Idx) {
+      BBInfo *PredInfo = Info->Preds[Idx];
+      assert(PredInfo && "Pred Info?");
+      if (!PredInfo->AvailableVal || Singular != PredInfo->AvailableVal)
+        return false;
+    }
+    if (!Singular)
+      return false;
+    // Record Singular value.
+    (*AvailableVals)[Info->BB] = Singular;
+    BBMap[Info->BB]->AvailableVal = Singular;
+    assert(Info->AvailableVal && "Missed assignement?");
+    return true;
+  }
+  
   /// FindAvailableVal - If this block requires a PHI, first check if an
   /// existing PHI matches the PHI placement and reaching definitions computed
   /// earlier, and if not, create a new PHI.  Visit all the block's
   /// predecessors to calculate the available value for each one and fill in
   /// the incoming values for a new PHI.
   void FindAvailableVals(BlockListTy *BlockList) {
     // Go through the worklist in forward order (i.e., backward through the CFG)
     // and check if existing PHIs can be used.  If not, create empty PHIs where
     // they are needed.
     for (typename BlockListTy::iterator I = BlockList->begin(),
            E = BlockList->end(); I != E; ++I) {
       BBInfo *Info = *I;
       // Check if there needs to be a PHI in BB.
       if (Info->DefBB != Info)
         continue;
 
+      // Look for singluar val.
+      if (FindSingularVal(Info))
+        continue;
+      
       // Look for an existing PHI.
       FindExistingPHI(Info->BB, BlockList);
       if (Info->AvailableVal)
         continue;
 
       ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
       Info->AvailableVal = PHI;
       (*AvailableVals)[Info->BB] = PHI;

llvm/test/CodeGen/AArch64/tail-dup-redundant-phi.mir

body:             |
   ; CHECK-NEXT:   [[MOVi32imm4:%[0-9]+]]:gpr32 = MOVi32imm 14
   ; CHECK-NEXT:   $w0 = COPY [[MOVi32imm4]]
   ; CHECK-NEXT:   [[STATEPOINT:%[0-9]+]]:gpr64all, [[STATEPOINT1:%[0-9]+]]:gpr64all = STATEPOINT 2882400000, 0, 1, @wombat, $w0, 2, 0, 2, 0, 2, 2, [[PHI1]], [[PHI]], 2, 2, [[PHI1]](tied-def 0), [[PHI]](tied-def 1), 2, 0, 2, 2, 0, 0, 1, 1, csr_aarch64_aapcs, implicit-def $sp, implicit-def dead early-clobber $lr
   ; CHECK-NEXT:   ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.17.bb49:
   ; CHECK-NEXT:   successors:{{ $}}
   ; CHECK-NEXT: {{  $}}
-  ; CHECK-NEXT:   [[PHI2:%[0-9]+]]:gpr64 = PHI [[PHI]], %bb.14, [[PHI]], %bb.15
-  ; CHECK-NEXT:   [[PHI3:%[0-9]+]]:gpr64all = PHI [[PHI1]], %bb.14, [[PHI1]], %bb.15
   ; CHECK-NEXT:   ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
   ; CHECK-NEXT:   [[MOVi32imm5:%[0-9]+]]:gpr32 = MOVi32imm 10
   ; CHECK-NEXT:   $w0 = COPY [[MOVi32imm5]]
-  ; CHECK-NEXT:   [[STATEPOINT2:%[0-9]+]]:gpr64all, [[STATEPOINT3:%[0-9]+]]:gpr64all = STATEPOINT 2882400000, 0, 1, @wombat, $w0, 2, 0, 2, 0, 2, 3, [[PHI3]], [[PHI2]], [[PHI2]], 2, 2, [[PHI3]](tied-def 0), [[PHI2]](tied-def 1), 2, 0, 2, 2, 0, 0, 1, 1, csr_aarch64_aapcs, implicit-def $sp, implicit-def dead early-clobber $lr
+  ; CHECK-NEXT:   [[STATEPOINT2:%[0-9]+]]:gpr64all, [[STATEPOINT3:%[0-9]+]]:gpr64all = STATEPOINT 2882400000, 0, 1, @wombat, $w0, 2, 0, 2, 0, 2, 3, [[PHI1]], [[PHI]], [[PHI]], 2, 2, [[PHI1]](tied-def 0), [[PHI]](tied-def 1), 2, 0, 2, 2, 0, 0, 1, 1, csr_aarch64_aapcs, implicit-def $sp, implicit-def dead early-clobber $lr
   ; CHECK-NEXT:   ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.18.bb51:
-  ; CHECK-NEXT:   [[PHI4:%[0-9]+]]:gpr64all = PHI [[COPY10]], %bb.8, [[COPY13]], %bb.9
+  ; CHECK-NEXT:   [[PHI2:%[0-9]+]]:gpr64all = PHI [[COPY10]], %bb.8, [[COPY13]], %bb.9
   ; CHECK-NEXT:   ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
   ; CHECK-NEXT:   [[MOVi32imm6:%[0-9]+]]:gpr32 = MOVi32imm 24
   ; CHECK-NEXT:   $w0 = COPY [[MOVi32imm6]]
-  ; CHECK-NEXT:   [[STATEPOINT4:%[0-9]+]]:gpr64all = STATEPOINT 2882400000, 0, 1, @wombat, $w0, 2, 0, 2, 0, 2, 1, [[PHI4]], 2, 1, [[PHI4]](tied-def 0), 2, 0, 2, 1, 0, 0, csr_aarch64_aapcs, implicit-def $sp, implicit-def dead early-clobber $lr
+  ; CHECK-NEXT:   [[STATEPOINT4:%[0-9]+]]:gpr64all = STATEPOINT 2882400000, 0, 1, @wombat, $w0, 2, 0, 2, 0, 2, 1, [[PHI2]], 2, 1, [[PHI2]](tied-def 0), 2, 0, 2, 1, 0, 0, csr_aarch64_aapcs, implicit-def $sp, implicit-def dead early-clobber $lr
   ; CHECK-NEXT:   ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
   bb.0.bb:
     successors: %bb.2(0x2aaaaaab), %bb.15(0x55555555)
 
     %4:gpr32 = COPY $wzr
     CBNZW %4, %bb.2
     B %bb.15
 

llvm/test/CodeGen/AMDGPU/nested-loop-conditions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: opt -mtriple=amdgcn-- -S -structurizecfg -si-annotate-control-flow %s | FileCheck -check-prefix=IR %s
 ; RUN: llc -march=amdgcn -mcpu=hawaii -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
 
 ; After structurizing, there are 3 levels of loops. The i1 phi
 ; conditions mutually depend on each other, so it isn't safe to delete
 ; the condition that appears to have no uses until the loop is
 ; completely processed.
 
 define amdgpu_kernel void @reduced_nested_loop_conditions(i64 addrspace(3)* nocapture %arg) #0 {
 ; GCN-LABEL: reduced_nested_loop_conditions:
 ; GCN:       ; %bb.0: ; %bb
 ; GCN-NEXT:    s_load_dword s0, s[0:1], 0x9
 ; GCN-NEXT:    v_lshlrev_b32_e32 v0, 3, v0
 ; GCN-NEXT:    s_mov_b32 m0, -1
-; GCN-NEXT:    s_mov_b64 s[2:3], -1
+; GCN-NEXT:    s_and_b64 s[2:3], exec, -1
 ; GCN-NEXT:    s_waitcnt lgkmcnt(0)
 ; GCN-NEXT:    v_add_i32_e32 v0, vcc, s0, v0
 ; GCN-NEXT:    ds_read_b64 v[0:1], v0
-; GCN-NEXT:    s_and_b64 s[0:1], exec, -1
+; GCN-NEXT:    s_and_b64 s[0:1], exec, 0
 ; GCN-NEXT:    s_branch .LBB0_2
-; GCN-NEXT:  .LBB0_1: ; %bb10
+; GCN-NEXT:  .LBB0_1: ; %Flow
 ; GCN-NEXT:    ; in Loop: Header=BB0_2 Depth=1
-; GCN-NEXT:    s_mov_b64 s[4:5], 0
-; GCN-NEXT:    s_andn2_b64 vcc, exec, s[2:3]
+; GCN-NEXT:    s_mov_b64 vcc, s[0:1]
 ; GCN-NEXT:    s_cbranch_vccz .LBB0_4
 ; GCN-NEXT:  .LBB0_2: ; %bb5
 ; GCN-NEXT:    ; =>This Inner Loop Header: Depth=1
-; GCN-NEXT:    s_mov_b64 vcc, s[0:1]
-; GCN-NEXT:    s_cbranch_vccnz .LBB0_1
-; GCN-NEXT:  ; %bb.3: ; in Loop: Header=BB0_2 Depth=1
 ; GCN-NEXT:    s_mov_b64 s[4:5], -1
-; GCN-NEXT:    s_andn2_b64 vcc, exec, s[2:3]
-; GCN-NEXT:    s_cbranch_vccnz .LBB0_2
+; GCN-NEXT:    s_mov_b64 vcc, s[2:3]
+; GCN-NEXT:    s_cbranch_vccz .LBB0_1
+; GCN-NEXT:  ; %bb.3: ; %bb10
+; GCN-NEXT:    ; in Loop: Header=BB0_2 Depth=1
+; GCN-NEXT:    s_mov_b64 s[4:5], 0
+; GCN-NEXT:    s_branch .LBB0_1
 ; GCN-NEXT:  .LBB0_4: ; %loop.exit.guard
 ; GCN-NEXT:    s_and_b64 vcc, exec, s[4:5]
 ; GCN-NEXT:    s_cbranch_vccz .LBB0_7
 ; GCN-NEXT:  ; %bb.5: ; %bb8
 ; GCN-NEXT:    s_waitcnt lgkmcnt(0)
 ; GCN-NEXT:    ds_read_b32 v0, v0
 ; GCN-NEXT:    s_and_b64 vcc, exec, 0
 ; GCN-NEXT:  .LBB0_6: ; %bb9

llvm/test/CodeGen/WebAssembly/lower-em-ehsjlj.ll

if.end:                                           ; preds = %entry
   call void @foo()
   call void @foo()
   br label %return
 
 return:                                           ; preds = %entry, %if.end
   ret void
 
 ; CHECK:    rethrow.exn:
-; CHECK-NEXT: %setjmpTable{{.*}} = phi i32* [ %setjmpTable{{.*}}, %if.end.split ], [ %setjmpTable{{.*}}, %if.end ]
 ; CHECK-NEXT: %exn = call i8* @__cxa_find_matching_catch_2()
 ; CHECK-NEXT: %{{.*}} = bitcast i32* %setjmpTable{{.*}} to i8*
 ; CHECK-NEXT: tail call void @free(i8* %{{.*}})
 ; CHECK-NEXT: call void @__resumeException(i8* %exn)
 ; CHECK-NEXT: unreachable
 }
 
 ; int jmpval = setjmp(buf);

llvm/test/Transforms/LICM/sink-debuginfo-preserve.ll

 ; void f1() { 
 ;  while (a) { 
 ;    g = 0;
 ;    if (a)
 ;      g = 0;
 ;  } 
 ; }
 
-; CHECK: %.lcssa = phi i32
-; CHECK-NEXT: store i32 %.lcssa, i32* getelementptr inbounds ([2 x i32], [2 x i32]* @g_390, i64 0, i64 1), align 4, !dbg [[storeLocation:![0-9]+]] 
+; CHECK: bb22:
+; CHECK-NEXT: store i32 0, i32* getelementptr inbounds ([2 x i32], [2 x i32]* @g_390, i64 0, i64 1), align 4, !dbg [[storeLocation:![0-9]+]] 
 ; CHECK: [[storeLocation]] = !DILocation(line: 0
 
 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.15.0"
 
 @b = global i32 0, align 4, !dbg !0
 @c = global i32 0, align 4, !dbg !10
 @g_390 = local_unnamed_addr global [2 x i32] zeroinitializer, align 4, !dbg !12