[DSE] Translate killing locations through phis.

[fhahn]

Summary

This patch updates DSE to translate the address of the killing access
through phis when traversing MemoryPhis. Note that this still misses
cases where we could translate phis, but there are no MemoryPhis in the
block with the translatable phi.

This is an initial step to improve DSE in the presence of address phis.
It can be improved in the future to also do phi translation when
stepping over any type of access, not just MemoryPhis. There's also a
related patch D90095.

[ebrevnov]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1954

Are you sure 32 is good default? Maybe just not to set it?

1966

Why do you need that?

1971

My understanding is the third parameter of getDomMemoryDef should be location of killing store. Changing it to phi translated one seems problematic.

2003

Addr is expected to be non null if successfully translated. Turn into assert?

[ebrevnov]

In general this patch seems to take exactly the same direction as D90095 and is a strict subset of it. We can choose to either re-build functionality step by step or take D90095 and split it to several smaller pieces. D90095 adds the follwoing functionality:

1. Replaces main 'do-while' loop to 'for' loop in getDomMemoryDef. This is NFC and aimed at simplifying code structure and allows to minimize future changes.
2. Supports phi translation to any predecessor (not only immediate one)
3. Is able to phi translate in presence of geps and casts. In order to support this we have to track offests.

Please let me know which way you prefer to go.

[asbirlea]

I'm seeing a crash with this. Repro: opt -passes=dse on:

%"struct.type" = type <{ i8 }>

; Function Attrs: noreturn
define void @f() {
entry:
  br label %while.cond

while.cond:                                       ; preds = %exit, %entry
  br i1 undef, label %if.end.i, label %if.then.i

if.then.i:                                        ; preds = %while.cond
  br label %exit

if.end.i:                                         ; preds = %while.cond
  store i8* undef, i8** inttoptr (i64 16 to i8**), align 16
  %.cast1.i = bitcast i8* undef to %"struct.type"*
  %IsMemberPointer.i.i = getelementptr inbounds %"struct.type", %"struct.type"* %.cast1.i, i64 0, i32 0
  store i8 0, i8* %IsMemberPointer.i.i, align 4
  br label %exit

exit: ; preds = %if.end.i, %if.then.i
  %retval.0.i = phi %"struct.type"* [ undef, %if.then.i ], [ %.cast1.i, %if.end.i ]
  %IsMemberPointer = getelementptr inbounds %"struct.type", %"struct.type"* %retval.0.i, i64 0, i32 0
  store i8 1, i8* %IsMemberPointer, align 4
  br label %while.cond
}

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1945–1946

Current unused in release builds.

[fhahn]

In D98288#2618947, @ebrevnov wrote:

In general this patch seems to take exactly the same direction as D90095 and is a strict subset of it. We can choose to either re-build functionality step by step or take D90095 and split it to several smaller pieces. D90095 adds the follwoing functionality:

1. Replaces main 'do-while' loop to 'for' loop in getDomMemoryDef. This is NFC and aimed at simplifying code structure and allows to minimize future changes.
2. Supports phi translation to any predecessor (not only immediate one)
3. Is able to phi translate in presence of geps and casts. In order to support this we have to track offests.

Please let me know which way you prefer to go.

Now that this code is enabled by default (and the legacy implementation has gone away), I think we try to proceed in small steps if possible to keep things as stable as possible, because subtle correctness issues may remain dormant for a while.

If you'd be happy to break up your patch, that sounds great. I think the missing features (2. and 3. above) at least should be separate patches, with independent evaluation of the benefits & trade-offs. It might still make sense to start with the current patch as initial starting point and add functionality from D90095 step-by-step.

In D98288#2672680, @asbirlea wrote:

I'm seeing a crash with this. Repro: opt -passes=dse on:

Is it possible you did not apply the dependent patch D98287 as well? Without this patch, I see a crash with the example you shared, but with D98287 I do not see a crash.

[fhahn]

Addressed outstanding comments & rebased

[fhahn]

remove manual size from ToCheck declaration.

[fhahn]

Remove Current variable, which was only used in LLVM_DEBUG.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1945–1946

thanks, I removed the variable.

1954

Thanks, I went ahead and removed it.

1966

It's not needed in the latest version. I removed it. Thanks!

1971

The location is used to find a potentially dead store. We should already have checked all candidates after the phi, so I don't think we would miss any candidates after translating. And when scanning for reads, AA should be conservative when dealing with the translated location. Is there anything in particular you think could be problematic?

2003

good point, done!

[vdsered]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1999

Why do we need to check if IncomingBlock is in a set of predecessors of PhiBlock? Isn't it always true? I thought there could probably be a reason like PhiBlock points to itself, but it seems that I'm wrong because we shouldn't get here in that case as we forbid it by the if-statement

if (State.PostOrderNumbers[IncomingBlock] >
              State.PostOrderNumbers[PhiBlock])

don't we?

[vdsered]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1999

*A little correction*
I meant that there could be a reason to check this if PhiBlock == IncomingBlock

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
     if (ScanLimit == 0 || WalkerStepLimit == 0) {
       LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");
       return None;
     }
 
     MemoryAccess *Current = StartAccess;
     Instruction *KillingI = KillingDef->getMemoryInst();
     bool StepAgain;
-    LLVM_DEBUG(dbgs() << "  trying to get dominating access\n");
+    LLVM_DEBUG(dbgs() << "  trying to get dominating access for "
+                      << *StartAccess << " and " << *DefLoc.Ptr << "\n");
 
     // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
     Optional<MemoryLocation> CurrentLoc;
     do {
       StepAgain = false;
       LLVM_DEBUG({
         dbgs() << "   visiting " << *Current;
         if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef>(Current))
for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     if (!MaybeSILoc) {
       LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "
                         << *SI << "\n");
       continue;
     }
     MemoryLocation SILoc = *MaybeSILoc;
     assert(SILoc.Ptr && "SILoc should not be null");
     const Value *SILocUnd = getUnderlyingObject(SILoc.Ptr);
 
-    MemoryAccess *Current = KillingDef;
     LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "
-                      << *Current << " (" << *SI << ")\n");
+                      << *KillingDef << " (" << *SI << ")\n");
 
     unsigned ScanLimit = MemorySSAScanLimit;
     unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
     unsigned PartialLimit = MemorySSAPartialStoreLimit;
     // Worklist of MemoryAccesses that may be killed by KillingDef.
-    SetVector<MemoryAccess *> ToCheck;
+    SmallVector<std::pair<MemoryAccess *, MemoryLocation>> ToCheck;
 
-    if (SILocUnd)
-      ToCheck.insert(KillingDef->getDefiningAccess());
+    if (SILocUnd) {
+      ToCheck.emplace_back(KillingDef->getDefiningAccess(), SILoc);
+    }
 
     bool Shortend = false;
     bool IsMemTerm = State.isMemTerminatorInst(SI);
     // Check if MemoryAccesses in the worklist are killed by KillingDef.
     for (unsigned I = 0; I < ToCheck.size(); I++) {
-      Current = ToCheck[I];
+      MemoryAccess *Current;
+      MemoryLocation CurrentLoc;
+      std::tie(Current, CurrentLoc) = ToCheck[I];
       if (State.SkipStores.count(Current))
         continue;
 
+      const Value *SILocUnd = getUnderlyingObject(CurrentLoc.Ptr);
       Optional<MemoryAccess *> Next = State.getDomMemoryDef(
-          KillingDef, Current, SILoc, SILocUnd, ScanLimit, WalkerStepLimit,
+          KillingDef, Current, CurrentLoc, SILocUnd, ScanLimit, WalkerStepLimit,
           IsMemTerm, PartialLimit);
 
       if (!Next) {
         LLVM_DEBUG(dbgs() << "  finished walk\n");
         continue;
       }
 
       MemoryAccess *EarlierAccess = *Next;
       LLVM_DEBUG(dbgs() << " Checking if we can kill " << *EarlierAccess);
       if (isa<MemoryPhi>(EarlierAccess)) {
         LLVM_DEBUG(dbgs() << "\n  ... adding incoming values to worklist\n");
+        BasicBlock *PhiBlock = EarlierAccess->getBlock();
+        SmallPtrSet<BasicBlock *, 4> Predecessors(pred_begin(PhiBlock),
+                                                  pred_end(PhiBlock));
         for (Value *V : cast<MemoryPhi>(EarlierAccess)->incoming_values()) {
           MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
           BasicBlock *IncomingBlock = IncomingAccess->getBlock();
-          BasicBlock *PhiBlock = EarlierAccess->getBlock();
 
           // We only consider incoming MemoryAccesses that come before the
           // MemoryPhi. Otherwise we could discover candidates that do not
           // strictly dominate our starting def.
           if (State.PostOrderNumbers[IncomingBlock] >
-              State.PostOrderNumbers[PhiBlock])
-            ToCheck.insert(IncomingAccess);
+              State.PostOrderNumbers[PhiBlock]) {
+            auto NewLoc = CurrentLoc;
+            PHITransAddr Addr(const_cast<Value *>(CurrentLoc.Ptr), State.DL,
+                              nullptr);
+            if (Addr.NeedsPHITranslationFromBlock(PhiBlock) &&
+                Predecessors.count(IncomingBlock)) {
+              if (Addr.IsPotentiallyPHITranslatable() &&
+                  !Addr.PHITranslateValue(PhiBlock, IncomingBlock, &DT,
+                                          false)) {
+                assert(Addr.getAddr() && "phi translation unsuccessful?");
+                NewLoc = CurrentLoc.getWithNewPtr(Addr.getAddr());
+              }
+            }
+            ToCheck.emplace_back(IncomingAccess, NewLoc);
+          }
         }
         continue;
       }
       auto *NextDef = cast<MemoryDef>(EarlierAccess);
       Instruction *NI = NextDef->getMemoryInst();
       LLVM_DEBUG(dbgs() << " (" << *NI << ")\n");
-      ToCheck.insert(NextDef->getDefiningAccess());
+      ToCheck.emplace_back(NextDef->getDefiningAccess(), CurrentLoc);
       NumGetDomMemoryDefPassed++;
 
       if (!DebugCounter::shouldExecute(MemorySSACounter))
         continue;
 
       MemoryLocation NILoc = *State.getLocForWriteEx(NI);
 
       if (IsMemTerm) {
         const Value *NIUnd = getUnderlyingObject(NILoc.Ptr);
         if (SILocUnd != NIUnd)
           continue;
         LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *NI
                           << "\n  KILLER: " << *SI << '\n');
         State.deleteDeadInstruction(NI);
         ++NumFastStores;
         MadeChange = true;
       } else {
         // Check if NI overwrites SI.
         int64_t InstWriteOffset, DepWriteOffset;
-        OverwriteResult OR = State.isOverwrite(SI, NI, SILoc, NILoc,
+        OverwriteResult OR = State.isOverwrite(SI, NI, CurrentLoc, NILoc,
                                                DepWriteOffset, InstWriteOffset);
         if (OR == OW_MaybePartial) {
           auto Iter = State.IOLs.insert(
               std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                   NI->getParent(), InstOverlapIntervalsTy()));
           auto &IOL = Iter.first->second;
-          OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,
-                                  NI, IOL);
+          OR = isPartialOverwrite(CurrentLoc, NILoc, DepWriteOffset,
+                                  InstWriteOffset, NI, IOL);
         }
 
         if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
           auto *Earlier = dyn_cast<StoreInst>(NI);
           auto *Later = dyn_cast<StoreInst>(SI);
           // We are re-using tryToMergePartialOverlappingStores, which requires
           // Earlier to domiante Later.
           // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.

llvm/test/Transforms/DeadStoreElimination/phi-translation.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -dse -S %s | FileCheck %s
 
-; TODO: Both the stores in %then and %else can be eliminated by translating %p
+; Both the stores in %then and %else can be eliminated by translating %p
 ; through the phi.
 define void @memoryphi_translate_1(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
-; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a.1 = alloca i8
else:
   br label %end
 
 end:
   %p = phi i8* [ %a.1, %then ], [ %a.2, %else ]
   store i8 10, i8* %p
   ret void
 }
 
-; TODO: The store in %else can be eliminated by translating %p through the phi.
+; The store in %else can be eliminated by translating %p through the phi.
 ; The store in %then cannot be eliminated, because %a.1 is read before the final
 ; store.
 define i8 @memoryphi_translate_2(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
-; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    [[L:%.*]] = load i8, i8* [[A_1]], align 1
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1
 ; CHECK-NEXT:    ret i8 [[L]]
 ;
 entry:

 
 end:
   %p = phi i8* [ %a.1, %then ], [ %a.2, %else ]
   %l = load i8, i8* %a.1
   store i8 10, i8* %p
   ret i8 %l
 }
 
-; TODO: The store in %then can be eliminated by translating %p through the phi.
+; The store in %then can be eliminated by translating %p through the phi.
 ; The store in %else cannot be eliminated, because %a.2 is read before the final
 ; store.
 define i8 @memoryphi_translate_3(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    [[L:%.*]] = load i8, i8* [[A_2]], align 1
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1

 
 end:
   %p = phi i8* [ %a.1, %then ], [ %a.2, %else ]
   %l = load i8, i8* %p
   store i8 10, i8* %p
   ret i8 %l
 }
 
-; TODO: The store in %entry can be removed by translating %p through the phi.
+; The store in %entry can be removed by translating %p through the phi.
 define void @memoryphi_translate_5(i1 %cond) {
 ; CHECK-LABEL: @memoryphi_translate_5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[B:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[C:%.*]] = alloca i8, align 1
-; CHECK-NEXT:    store i8 0, i8* [[A]], align 1
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
 ; CHECK-NEXT:    store i8 0, i8* [[C]], align 1
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[B]], [[COND_TRUE]] ], [ [[A]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
 ; CHECK-NEXT:    call void @use(i8* [[P]])

 ; CHECK-LABEL: @test_trans_null(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    call void @fn()
 ; CHECK-NEXT:    [[BC:%.*]] = bitcast i8* undef to i16*
-; CHECK-NEXT:    [[GEP_1:%.*]] = getelementptr inbounds i16, i16* [[BC]], i64 2
-; CHECK-NEXT:    store i16 8, i16* [[GEP_1]], align 2
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[P:%.*]] = phi i16* [ [[PTR:%.*]], [[THEN]] ], [ [[BC]], [[ELSE]] ]
 ; CHECK-NEXT:    [[GEP_2:%.*]] = getelementptr inbounds i16, i16* [[P]], i64 2
 ; CHECK-NEXT:    store i16 8, i16* [[GEP_2]], align 2
 ; CHECK-NEXT:    ret void
 ;
 entry: