[CodeGenPrepare] Check that erased sunken address are not reused

[sdardis]

Summary

CodeGenPrepare sinks address computations from one basic block to another
and attempts to reuse address computations that have already been sunk. If
the same address computation appears twice with the first instance as an
operand of a load whose result is an operand to a simplifable select,
CodeGenPrepare simplifies the select and recursively erases the now dead
instructions. CodeGenPrepare then attempts to use the erased address
computation for the second load.

Fix this by erasing the cached address value if it has zero uses before
looking for the address value in the sunken address map.

This partially resolves PR35209.

Thanks to Alexander Richardson for reporting the issue!

[arichardson]

I just tried applying this patch locally and compiling the FreeBSD kernel again. The runtime crash that goes away if I revert https://reviews.llvm.org/rL314794 is still present even with this patch.

I am not sure what is going wrong there, I will have to try and find a reduced test case.

[john.brawn]

test/Transforms/CodeGenPrepare/pr35209.ll

1 ↗

(On Diff #122234)

Could you change this to use opt instead with explicit triple? Whether the transformation happens depends on the target's isLegalAddressingMode and llc defaults to the host target, so the test wouldn't always be testing the same thing depending on what machine you're running it on.

3–6 ↗

(On Diff #122234)

You could do with some CHECKs in this file to check that the address sinking is actually happening.

[sdardis]

Address review comments.

[john.brawn]

LGTM.

[sdardis]

Reopening this as some changes were required to pacify some buildbots.

[sdardis]

Address the failures on the sanitizer bots by reworking SunkAddrs in a <Value*, WeakTrackingVH*> map, so that if a computation is erased, the end value is not read after deletion to see if it is still live.

[john.brawn]

lib/CodeGen/CodeGenPrepare.cpp

233

whose

4369–4370

You no longer have a reference to an element of SunkAddrs here, which means SunkAddrs never has anything added to it so we never reuse a sunk addrmode. test3 in test/Transforms/CodeGenPrepare/X86/sink-addrmode.ll was trying to test this but had a misplaced comma: I've just now fixed that and so I now see a test failure with this patch.

[sdardis]

Address review comments.

[john.brawn]

LGTM.

[sdardis]

Thanks for the review

lib/CodeGen/CodeGenPrepare.cpp

class CodeGenPrepare : public FunctionPass {
     std::unique_ptr<BranchProbabilityInfo> BPI;
 
     /// As we scan instructions optimizing them, this is the next instruction
     /// to optimize. Transforms that can invalidate this should update it.
     BasicBlock::iterator CurInstIterator;
 
     /// Keeps track of non-local addresses that have been sunk into a block.
     /// This allows us to avoid inserting duplicate code for blocks with
-    /// multiple load/stores of the same address.
-    ValueMap<Value*, Value*> SunkAddrs;
+    /// multiple load/stores of the same address. The usage of WeakTrackingVH
+    /// enables SunkAddrs to be treated as a cache whoae entries can be
+    /// invalidated if a sunken address computation has been erased.
+    ValueMap<Value*, WeakTrackingVH*> SunkAddrs;
 
     /// Keeps track of all instructions inserted for the current function.
     SetOfInstrs InsertedInsts;
 
     /// Keeps track of the type of the related instruction before their
     /// promotion for the current function.
     InstrToOrigTy PromotedInsts;
 
bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
   // Insert this computation right after this user.  Since our caller is
   // scanning from the top of the BB to the bottom, reuse of the expr are
   // guaranteed to happen later.
   IRBuilder<> Builder(MemoryInst);
 
   // Now that we determined the addressing expression we want to use and know
   // that we have to sink it into this block.  Check to see if we have already
   // done this for some other load/store instr in this block.  If so, reuse the
-  // computation.
-  Value *&SunkAddr = SunkAddrs[Addr];
-  if (SunkAddr) {
+  // computation.  Before attempting reuse, check if the address is valid as it
+  // may have been erased.
+  auto I = SunkAddrs.find(Addr);
+  if (I != SunkAddrs.end() && I->second && I->second->pointsToAliveValue())
+    SunkAddrs.erase(I);
+
+  WeakTrackingVH * SunkAddrVH = SunkAddrs[Addr];
+  Value * SunkAddr = nullptr;
+  if (SunkAddrVH) {
+    SunkAddr = *SunkAddrVH;
     DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
                  << *MemoryInst << "\n");
     if (SunkAddr->getType() != Addr->getType())
       SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->getType());
   } else if (AddrSinkUsingGEPs ||
              (!AddrSinkUsingGEPs.getNumOccurrences() && TM &&
               SubtargetInfo->useAA())) {
     // By default, we use the GEP-based method when AA is used later. This

test/Transforms/CodeGenPrepare/Mips/lit.local.cfg

+if not 'Mips' in config.root.targets:
+    config.unsupported = True

test/Transforms/CodeGenPrepare/Mips/pr35209.ll

+; RUN: opt -S -mtriple=mips64-mti-linux-gnu -codegenprepare < %s | FileCheck %s
+
+; Test that if an address that was sunk from a dominating bb, used in a
+; select that is erased along with its' trivally dead operand, that the
+; sunken address is not reused if the same address computation occurs
+; after the select. Previously, this caused a ICE.
+
+%struct.az = type { i32, %struct.bt* }
+%struct.bt = type { i32 }
+%struct.f = type { %struct.ax, %union.anon }
+%struct.ax = type { %struct.az* }
+%union.anon = type { %struct.bd }
+%struct.bd = type { i64 }
+%struct.bg = type { i32, i32 }
+%struct.ap = type { i32, i32 }
+
+@ch = common global %struct.f zeroinitializer, align 8
+@j = common global %struct.az* null, align 8
+@ck = common global i32 0, align 4
+@h = common global i32 0, align 4
+@.str = private unnamed_addr constant [1 x i8] zeroinitializer, align 1
+
+define internal void @probestart() {
+entry:
+  %0 = load %struct.az*, %struct.az** @j, align 8
+  %bw = getelementptr inbounds %struct.az, %struct.az* %0, i64 0, i32 1
+  %1 = load i32, i32* @h, align 4
+  %cond = icmp eq i32 %1, 0
+  br i1 %cond, label %sw.bb, label %cl
+
+sw.bb:                                            ; preds = %entry
+  %call = tail call inreg { i64, i64 } @ba(i32* bitcast (%struct.f* @ch to i32*))
+  br label %cl
+
+cl:                                               ; preds = %sw.bb, %entry
+  %2 = load %struct.bt*, %struct.bt** %bw, align 8
+  %tobool = icmp eq %struct.bt* %2, null
+  %3 = load i32, i32* @ck, align 4
+  %.sink5 = select i1 %tobool, i32* getelementptr (%struct.bg, %struct.bg* bitcast (%union.anon* getelementptr inbounds (%struct.f, %struct.f* @ch, i64 0, i32 1) to %struct.bg*), i64 0, i32 1), i32* getelementptr (%struct.ap, %struct.ap* bitcast (%union.anon* getelementptr inbounds (%struct.f, %struct.f* @ch, i64 0, i32 1) to %struct.ap*), i64 0, i32 1)
+  store i32 %3, i32* %.sink5, align 4
+  store i32 1, i32* bitcast (i64* getelementptr inbounds (%struct.f, %struct.f* @ch, i64 0, i32 1, i32 0, i32 0) to i32*), align 8
+  %4 = load %struct.bt*, %struct.bt** %bw, align 8
+  tail call void (i8*, ...) @a(i8* getelementptr inbounds ([1 x i8], [1 x i8]* @.str, i64 0, i64 0), %struct.bt* %4)
+  ret void
+}
+
+; CHECK-LABEL: @probestart()
+; CHECK-LABEL: entry:
+; CHECK: %[[I0:[0-9]+]] = load %struct.az*, %struct.az** @j
+; CHECK-LABEL: cl:
+
+; CHECK-NOT: %{{[0-9]+}}  = load %struct.bt*, %struct.bt** %bw
+; CHECK-NOT: %{{[.a-z0-9]}} = select
+; CHECK-NOT: %{{[0-9]+}}  = load %struct.bt*, %struct.bt** %bw
+
+; CHECK: %[[I1:[0-9]+]] = bitcast %struct.az* %[[I0]] to i8*
+; CHECK-NEXT: %sunkaddr = getelementptr i8, i8* %[[I1]], i64 8
+; CHECK-NEXT: %[[I2:[0-9]+]] = bitcast i8* %sunkaddr to %struct.bt**
+; CHECK-NEXT: %{{[0-9]+}} = load %struct.bt*, %struct.bt** %[[I2]]
+; CHECK-NEXT: tail call void (i8*, ...) @a
+
+declare inreg { i64, i64 } @ba(i32*)
+
+declare void @a(i8*, ...)