[ARM] Define ComplexPatternFuncMutatesDAG

[dmgreen]

Summary

Some of the Arm complex pattern functions call canExtractShiftFromMul, which can modify the DAG in-place. For this to be valid and handled successfully we need to define ComplexPatternFuncMutatesDAG.

The test case is a little big, but I didn't have a lot of luck reducing it further.

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp

83

Nice find. Bit of an "obscure" hook, doesn't seem to be documented very well. But I guess it will eventually call canExtractShiftFromMul, perhaps you can clarify that a little bit in the comment.

llvm/test/CodeGen/ARM/shifter_operand.ll

520

You already mentioned the test case being a bit big, but do we need a loop? I guess you do, but that's unclear to me.

If it can't be reduced, can you precommit the test? Then we can see the diff here.

[dmgreen]

Update comment and formatting.

llvm/test/CodeGen/ARM/shifter_operand.ll

520

Unfortunately it crashes, so no changes can be shown and it can't be precommitted. I've not been able to reduce it much beyond this. The smaller example above is doing the same thing - you can see it's turning a mul into a smaller mul and a shift- but not hitting the same assert with deleted nodes.
It's not too big though, all things considered. Some of the other examples I have for other work I haven't been able to reduce past a few thousand instructions, only happening when certain register allocation patterns occur.

[SjoerdMeijer]

llvm/test/CodeGen/ARM/shifter_operand.ll

520

Alright, cheers, LGTM.

[dim]

David, in this particular change, does "valid and handled successfully" mean "not crash or assert"? I just ran into the following assertion when building part of llvm (13.0.0) itself under FreeBSD 12:

Assertion failed: (NodeToMatch->getOpcode() != ISD::DELETED_NODE && "NodeToMatch was removed partway through selection"), function SelectCodeCommon, file /home/dim/src/llvm/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp, line 3573.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: /home/dim/ins/llvmorg-14-init-00920-gf88ad8d00f9/bin/clang -cc1 -triple armv6kz-unknown-freebsd12.3-gnueabihf -S --mrelax-relocations -disable-free -disable-llvm-verifier -discard-value-names -mrelocation-model static -mconstructor-aliases -target-cpu arm1176jzf-s -target-feature +vfp2 -target-feature +vfp2sp -target-feature -vfp3 -target-feature -vfp3d16 -target-feature -vfp3d16sp -target-feature -vfp3sp -target-feature -fp16 -target-feature -vfp4 -target-feature -vfp4d16 -target-feature -vfp4d16sp -target-feature -vfp4sp -target-feature -fp-armv8 -target-feature -fp-armv8d16 -target-feature -fp-armv8d16sp -target-feature -fp-armv8sp -target-feature -fullfp16 -target-feature +fp64 -target-feature -d32 -target-feature -neon -target-feature -sha2 -target-feature -aes -target-feature -fp16fml -target-feature +strict-align -target-abi aapcs-linux -mfloat-abi hard -fallow-half-arguments-and-returns -ffunction-sections -fdata-sections -O1 -std=c++14 -fdeprecated-macro -fno-rtti -fno-signed-char -faddrsig -fexperimental-new-pass-manager PPCISelLowering-009095.ii
1.      <eof> parser at end of file
2.      Code generation
3.      Running pass 'Function Pass Manager' on module 'PPCISelLowering-009095.cpp'.
4.      Running pass 'ARM Instruction Selection' on function '@_ZN4llvm17PPCTargetLoweringC2ERKNS_16PPCTargetMachineERKNS_12PPCSubtargetE'

And bisecting for the commit that fixed this assertion, I ended up here (and at rG77e8f4eeeeed516a1c79365a4b8128da463d96c4 obviously). Interestingly it crashes during the compilation of the PowerPC instruction selection sources, but when it is targeting ARMv6.

Similar to yours this test case is rather big, namely the preprocessed PPCISelLowering.cpp file, but I'm reducing it too. I would like to see if the end result looks similar to your case here.

[dim]

Okay, in my case the test case is quite a bit shorter:

; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "PPCISelLowering-min.cpp"
target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
target triple = "armv6-unknown-unknown"

%0 = type { %1, [3 x i8] }
%1 = type { %2 }
%2 = type <{ %3, i8, i8, [179 x [179 x i16]], [179 x [179 x i8]] }>
%3 = type { i32 }
%4 = type <{ %3, i8, i8, [179 x [179 x i16]], [179 x [179 x i8]], [3 x i8] }>

define dso_local arm_aapcscc void @_ZN1jC2Ev(%0* %0) unnamed_addr #0 align 2 {
  %2 = bitcast %0* %0 to %4*
  br i1 undef, label %3, label %4

3:                                                ; preds = %1
  ret void

4:                                                ; preds = %4, %1
  %5 = call arm_aapcscc i32 @_ZN1bIN1g2aiEEdeEv() #1
  %6 = getelementptr inbounds %4, %4* %2, i32 0, i32 3, i32 %5, i32 0
  store i16 0, i16* %6, align 2
  %7 = getelementptr inbounds %4, %4* %2, i32 0, i32 4, i32 %5, i32 0
  store i8 0, i8* %7, align 1
  br label %4, !llvm.loop !1
}

declare arm_aapcscc i32 @_ZN1bIN1g2aiEEdeEv() local_unnamed_addr #0

attributes #0 = { "target-features"="+armv6,-thumb-mode" }
attributes #1 = { nounwind }

!llvm.ident = !{!0}

!0 = !{!"FreeBSD clang version 13.0.0 ([e-mail]:llvm/llvm-project.git llvmorg-13.0.0-0-gd7b669b3a303)"}
!1 = distinct !{!1, !2}
!2 = !{!"llvm.loop.unroll.disable"}

[dmgreen]

OK great. Thanks for the report. llvm 14 should be all OK then?

in this particular change, does "valid and handled successfully" mean "not crash or assert"?

Yep - I think it was some sort of crash IIRC.

[DavidSpickett]

https://github.com/llvm/llvm-project/issues/53396, also targeting armv6kz, was fixed by this change, . 13.0.1-rc3 doesn't have the issue thanks to the cherry-pick.

[dmgreen]

Good stuff. I was wondering if it was. Thanks for checking.

llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp

public:
   /// getI32Imm - Return a target constant of type i32 with the specified
   /// value.
   inline SDValue getI32Imm(unsigned Imm, const SDLoc &dl) {
     return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
   }
 
   void Select(SDNode *N) override;
 
+  /// canExtractShiftFromMul perform mul to shift mutations.
+  bool ComplexPatternFuncMutatesDAG() const override {
+    return true;
+  }
+
   bool hasNoVMLxHazardUse(SDNode *N) const;
   bool isShifterOpProfitable(const SDValue &Shift,
                              ARM_AM::ShiftOpc ShOpcVal, unsigned ShAmt);
   bool SelectRegShifterOperand(SDValue N, SDValue &A,
                                SDValue &B, SDValue &C,
                                bool CheckProfitability = true);
   bool SelectImmShifterOperand(SDValue N, SDValue &A,
                                SDValue &B, bool CheckProfitability = true);

llvm/test/CodeGen/ARM/shifter_operand.ll

; CHECK-THUMB-NEXT:    bx lr
   %ptr = inttoptr i32 %sum to i32*
   %loaded = load i32, i32* %ptr
 
   %ret.tmp = insertvalue { i32, i32 } undef, i32 %sum, 0
   %ret = insertvalue { i32, i32 } %ret.tmp, i32 %loaded, 1
 
   ret { i32, i32 } %ret
 }
+
+define i32 @test_new(i32 %x, i32 %y) {
+; CHECK-ARM-LABEL: test_new:
+; CHECK-ARM:       @ %bb.0: @ %entry
+; CHECK-ARM-NEXT:    movw r2, #48047
+; CHECK-ARM-NEXT:    mul r1, r1, r2
+; CHECK-ARM-NEXT:    add r0, r0, r1, lsl #1
+; CHECK-ARM-NEXT:    bx lr
+;
+; CHECK-THUMB-LABEL: test_new:
+; CHECK-THUMB:       @ %bb.0: @ %entry
+; CHECK-THUMB-NEXT:    movw r2, #48047
+; CHECK-THUMB-NEXT:    muls r1, r2, r1
+; CHECK-THUMB-NEXT:    add.w r0, r0, r1, lsl #1
+; CHECK-THUMB-NEXT:    bx lr
+entry:
+  %mul = mul i32 %y, 96094
+  %conv = add i32 %mul, %x
+  ret i32 %conv
+}
+
+; This test was hitting issues with deleted nodes because ComplexPatternFuncMutatesDAG
+; was not defined.
+@arr_9 = external dso_local local_unnamed_addr global [15 x [25 x [18 x i8]]], align 1
+define void @test_mutateddag(i32 %b, i32 %c, i32 %d, i1 %cc) {
+; CHECK-THUMB-LABEL: test_mutateddag:
+; CHECK-THUMB:       @ %bb.0: @ %entry
+; CHECK-THUMB-NEXT:    .save {r4, lr}
+; CHECK-THUMB-NEXT:    push {r4, lr}
+; CHECK-THUMB-NEXT:    movw r12, #50608
+; CHECK-THUMB-NEXT:    movw r4, #51512
+; CHECK-THUMB-NEXT:    movt r12, #17917
+; CHECK-THUMB-NEXT:    movt r4, #52
+; CHECK-THUMB-NEXT:    mla r12, r1, r4, r12
+; CHECK-THUMB-NEXT:    mov.w r4, #450
+; CHECK-THUMB-NEXT:    lsls r3, r3, #31
+; CHECK-THUMB-NEXT:    mul lr, r0, r4
+; CHECK-THUMB-NEXT:    movw r0, #48047
+; CHECK-THUMB-NEXT:    muls r0, r1, r0
+; CHECK-THUMB-NEXT:    movw r1, :lower16:arr_9
+; CHECK-THUMB-NEXT:    movt r1, :upper16:arr_9
+; CHECK-THUMB-NEXT:    add.w r0, r2, r0, lsl #1
+; CHECK-THUMB-NEXT:    movw r2, #24404
+; CHECK-THUMB-NEXT:    movt r2, #19356
+; CHECK-THUMB-NEXT:    add.w r0, r0, r0, lsl #3
+; CHECK-THUMB-NEXT:    add.w r0, r1, r0, lsl #1
+; CHECK-THUMB-NEXT:    movw r1, #60904
+; CHECK-THUMB-NEXT:    movt r1, #64028
+; CHECK-THUMB-NEXT:    add r2, r0
+; CHECK-THUMB-NEXT:    add r1, r0
+; CHECK-THUMB-NEXT:    movs r0, #0
+; CHECK-THUMB-NEXT:    b .LBB19_2
+; CHECK-THUMB-NEXT:  .LBB19_1: @ %for.cond1.for.cond.cleanup_crit_edge
+; CHECK-THUMB-NEXT:    @ in Loop: Header=BB19_2 Depth=1
+; CHECK-THUMB-NEXT:    add r1, lr
+; CHECK-THUMB-NEXT:    add r2, lr
+; CHECK-THUMB-NEXT:  .LBB19_2: @ %for.cond
+; CHECK-THUMB-NEXT:    @ =>This Loop Header: Depth=1
+; CHECK-THUMB-NEXT:    @ Child Loop BB19_3 Depth 2
+; CHECK-THUMB-NEXT:    movs r4, #0
+; CHECK-THUMB-NEXT:  .LBB19_3: @ %for.cond2.preheader
+; CHECK-THUMB-NEXT:    @ Parent Loop BB19_2 Depth=1
+; CHECK-THUMB-NEXT:    @ => This Inner Loop Header: Depth=2
+; CHECK-THUMB-NEXT:    cmp r3, #0
+; CHECK-THUMB-NEXT:    str r0, [r1, r4]
+; CHECK-THUMB-NEXT:    bne .LBB19_1
+; CHECK-THUMB-NEXT:  @ %bb.4: @ %for.cond2.preheader.2
+; CHECK-THUMB-NEXT:    @ in Loop: Header=BB19_3 Depth=2
+; CHECK-THUMB-NEXT:    str r0, [r2, r4]
+; CHECK-THUMB-NEXT:    add r4, r12
+; CHECK-THUMB-NEXT:    b .LBB19_3
+entry:
+  %0 = add i32 %d, -4
+  %1 = mul i32 %c, 864846
+  %2 = add i32 %1, 1367306604
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond1.for.cond.cleanup_crit_edge, %for.cond.preheader
+  %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %for.cond1.for.cond.cleanup_crit_edge ]
+  %3 = mul i32 %indvar, %b
+  %4 = add i32 %3, -2
+  br label %for.cond2.preheader
+
+for.cond2.preheader:                              ; preds = %for.cond2.preheader.2, %for.cond
+  %indvar24 = phi i32 [ 0, %for.cond ], [ %indvar.next25.3, %for.cond2.preheader.2 ]
+  %indvar.next25 = or i32 %indvar24, 1
+  %5 = mul i32 %2, %indvar.next25
+  %6 = add i32 %5, -16
+  %scevgep.1 = getelementptr [15 x [25 x [18 x i8]]], [15 x [25 x [18 x i8]]]* @arr_9, i32 -217196, i32 %4, i32 %0, i32 %6
+  %7 = bitcast i8* %scevgep.1 to i32*
+  store i32 0, i32* %7, align 1
+  br i1 %cc, label %for.cond1.for.cond.cleanup_crit_edge, label %for.cond2.preheader.2
+
+for.cond2.preheader.2:                            ; preds = %for.cond2.preheader
+  %indvar.next25.1 = or i32 %indvar24, 2
+  %8 = mul i32 %2, %indvar.next25.1
+  %9 = add i32 %8, -16
+  %scevgep.2 = getelementptr [15 x [25 x [18 x i8]]], [15 x [25 x [18 x i8]]]* @arr_9, i32 -217196, i32 %4, i32 %0, i32 %9
+  %10 = bitcast i8* %scevgep.2 to i32*
+  store i32 0, i32* %10, align 1
+  %indvar.next25.3 = add i32 %indvar24, 4
+  br label %for.cond2.preheader
+
+for.cond1.for.cond.cleanup_crit_edge:             ; preds = %for.cond2.preheader
+  %indvar.next = add i32 %indvar, 1
+  br label %for.cond
+}