[X86] Fix the LEA optimization pass

[kazu]

Summary

The LEA optimization pass visits each basic block of a given machine
function. In each basic block, for each pair of LEAs that differ only
in their displacement fields, we replace all uses of the second LEA
with the first LEA while adjusting the displacement.

Now, without this patch, after all the replacements are made, the
following assert triggers:

assert(MRI->use_empty(LastVReg) &&
       "The LEA's def register must have no uses");

The replacement loop uses:

for (MachineOperand &MO :
     llvm::make_early_inc_range(MRI->use_operands(LastVReg))) {

which is equivalent to:

for (auto UI = MRI->use_begin(LastVReg), UE = MRI->use_end();
     UI != UE;) {
  MachineOperand &MO = *UI++;  // <-- Look!

That is, immediately after the post increment, make_early_inc_range
already has the iterator for the next iteration in its mind.

The problem is that in one iteration of the loop, we could replace two
uses in a debug instruction like:

DBG_VALUE_LIST !"r", !DIExpression(DW_OP_LLVM_arg, 0), %0:gr64, %0:gr64, ...

So, the iterator for the next iteration becomes invalid. We end up
traversing a garbage use list from that point on. In turn, we don't
get to visit remaining uses.

The patch fixes the problem by switching to a "draining" while loop:

while (!MRI->use_empty(LastVReg)) {
  MachineOperand &MO = *MRI->use_begin(LastVReg);
  MachineInstr &MI = *MO.getParent();

The credit goes to Simon Pilgrim for reducing the test case.

Fixes https://github.com/llvm/llvm-project/issues/57673

[RKSimon]

@kazu Please can you raise a bug with your reduced test case to see if we can help get it reduced any further?

[kazu]

In D133631#3782149, @RKSimon wrote:

@kazu Please can you raise a bug with your reduced test case to see if we can help get it reduced any further?

Thank you for the offer. I've filed https://github.com/llvm/llvm-project/issues/57673.

[RKSimon]

In D133631#3782364, @kazu wrote:

In D133631#3782149, @RKSimon wrote:

@kazu Please can you raise a bug with your reduced test case to see if we can help get it reduced any further?

Thank you for the offer. I've filed https://github.com/llvm/llvm-project/issues/57673.

I've managed a minor reduction - please can you add as a test case? We might be able to further reduce this yet.

[kazu]

In D133631#3783498, @RKSimon wrote:

In D133631#3782364, @kazu wrote:

In D133631#3782149, @RKSimon wrote:

@kazu Please can you raise a bug with your reduced test case to see if we can help get it reduced any further?

Thank you for the offer. I've filed https://github.com/llvm/llvm-project/issues/57673.

I've managed a minor reduction - please can you add as a test case? We might be able to further reduce this yet.

Thanks a lot Simon for the reduced testcase! You made it possible to see the crash even at today's HEAD, not just the 13-day old revision 23dec4a3524aa5c9cc3cb401987014c6c5ee9de0. I'll upload the revised patch shortly.

[kazu]

Added a test case.

[kazu]

Added a "Fixes" message.

[kazu]

Please take a look. Thanks!

[kazu]

I'd appreciate a review. Thanks!

[RKSimon]

Your fix SGTM - its just a question of whether we can simplify the regression test any further

[kazu]

In D133631#3789845, @RKSimon wrote:

Your fix SGTM - its just a question of whether we can simplify the regression test any further

I am not familiar, but should we consider an MIR test to precisely control what goes into the backend?

[RKSimon]

Yes that might be a good idea - we should keep the ll test file as well if we can.

llvm/test/CodeGen/X86/lea-optimize-crash.ll

3

rename this file pr57673.ll?

[kazu]

Added an MIR test case.

[kazu]

In D133631#3789881, @RKSimon wrote:

Yes that might be a good idea - we should keep the ll test file as well if we can.

I added my very first MIR test case. I hope I got it right. Tested with and without the "while" loop change.

Please take a look. Thanks!

[kazu]

Please take a look. Thanks!

[pengfei]

LGTM.

[kazu]

In D133631#3798570, @pengfei wrote:

LGTM.

Thank you for reviewing the patch!

llvm/lib/Target/X86/X86OptimizeLEAs.cpp

while (I1 != List.end()) {
           continue;
         }
 
         // Loop over all uses of the Last LEA and update their operands. Note
         // that the correctness of this has already been checked in the
         // isReplaceable function.
         Register FirstVReg = First.getOperand(0).getReg();
         Register LastVReg = Last.getOperand(0).getReg();
-        for (MachineOperand &MO :
-             llvm::make_early_inc_range(MRI->use_operands(LastVReg))) {
+        // We use MRI->use_empty here instead of the combination of
+        // llvm::make_early_inc_range and MRI->use_operands because we could
+        // replace two or more uses in a debug instruction in one iteration, and
+        // that would deeply confuse llvm::make_early_inc_range.
+        while (!MRI->use_empty(LastVReg)) {
+          MachineOperand &MO = *MRI->use_begin(LastVReg);
           MachineInstr &MI = *MO.getParent();
 
           if (MI.isDebugValue()) {
             // Replace DBG_VALUE instruction with modified version using the
             // register from the replacing LEA and the address displacement
             // between the LEA instructions.
             replaceDebugValue(MI, LastVReg, FirstVReg, AddrDispShift);
             continue;

llvm/test/CodeGen/X86/lea-optimize-crash.ll

+; RUN: llc -mtriple=x86_64-unknown-unknown -mcpu=x86-64 < %s | FileCheck %s
+
+; The LEA optimization pass used to crash on this testcase.
+
+target triple = "x86_64-unknown-linux-gnu"
+
+%t10 = type { i8*, [32 x i8] }
+
+; CHECK: foo:
+define void @foo() {
+bb_entry:
+  %tmp11 = alloca [0 x [0 x i32]], i32 0, align 4
+  %i = alloca %t10, align 8
+  %i1 = alloca %t10, align 8
+  %tmp1.sub = getelementptr inbounds [0 x [0 x i32]], [0 x [0 x i32]]* %tmp11, i64 0, i64 0, i64 0
+  %i2 = bitcast [0 x [0 x i32]]* %tmp11 to i8*
+  br label %bb_8
+
+bb_8:                                             ; preds = %bb_last, %bb_entry
+  br i1 undef, label %bb_last, label %bb_mid
+
+bb_mid:                                           ; preds = %bb_8
+  %i3 = bitcast %t10* %i1 to i8*
+  %i4 = getelementptr inbounds %t10, %t10* %i1, i64 0, i32 1, i64 32
+  %i5 = bitcast %t10* %i to i8*
+  %i6 = getelementptr inbounds %t10, %t10* %i, i64 0, i32 1, i64 32
+  call void @llvm.lifetime.start.p0i8(i64 0, i8* nonnull %i3)
+  %v21 = call i64 @llvm.ctlz.i64(i64 undef, i1 false)
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull dereferenceable(16) null, i8* noundef nonnull align 8 dereferenceable(16) %i4, i64 16, i1 false)
+  call void @llvm.dbg.value(metadata !DIArgList(i8* %i4, i8* %i4), metadata !4, metadata !DIExpression(DW_OP_LLVM_arg, 0)), !dbg !9
+  call void @llvm.lifetime.end.p0i8(i64 0, i8* nonnull %i3)
+  call void @llvm.lifetime.start.p0i8(i64 0, i8* nonnull %i5)
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull dereferenceable(16) null, i8* noundef nonnull align 8 dereferenceable(16) %i6, i64 16, i1 false)
+  call void @llvm.lifetime.end.p0i8(i64 0, i8* nonnull %i5)
+  br label %bb_last
+
+bb_last:                                          ; preds = %bb_mid, %bb_8
+  call void @llvm.lifetime.start.p0i8(i64 0, i8* nonnull %i2)
+  call void undef(i32* null, i32* null, i32* null, i32 0, i32* nonnull %tmp1.sub)
+  call void @llvm.lifetime.end.p0i8(i64 0, i8* nonnull %i2)
+  br label %bb_8
+}
+
+declare i64 @llvm.ctlz.i64(i64, i1 immarg)
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i64, i1 immarg)
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture)
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture)
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, isOptimized: false, runtimeVersion: 0, emissionKind: NoDebug)
+!1 = !DIFile(filename: "n", directory: "/proc/self/cwd", checksumkind: CSK_MD5, checksum: "e588179fedd8fcdfada963f2434cb950")
+!2 = !{i32 2, !"Debug Info Version", i32 3}
+!3 = !{!"function_entry_count", i64 2423}
+!4 = !DILocalVariable(name: "r", scope: !5, file: !6, line: 93)
+!5 = distinct !DISubprogram(name: "c", scope: !7, file: !6, line: 92, spFlags: DISPFlagDefinition, unit: !0)
+!6 = !DIFile(filename: "a", directory: "/proc/self/cwd")
+!7 = !DINamespace(name: "u", scope: !8)
+!8 = !DINamespace(name: "s", scope: null)
+!9 = !DILocation(line: 0, scope: !5)