[PowerPC] Follow-up to r318436 to get the missed CSE opportunities

[nemanjai]

Summary

In r318436, the PPC back end improved the code-gen for stores of constant values. However, there's a class of patterns that this misses and a class that it actually makes worse.

• The revision isn't able to do anything for indexed stores (pre-inc in the case of PPC) as the target-specific DAG combine isn't run on the indexed stores produced by the generic combiner.
• The revision makes code-gen worse for 8-32 bit stores of negative values as the new 64-bit constant isn't sign-extended so just appears to be a large positive value. Example:

extern int IVal;
void test() {
  IVal = -7;
}

Generates this code:

li 4, 0
oris 4, 4, 65535
ori 4, 4, 65529
stw 4, 0(3)

Rather than the obviously better:

li 4, -7
stw 4, 0(3)

This patch does the following:

• Modifies the generic DAG combiner to add the new indexed LD/ST to the worklist so the target-specific combiner has an opportunity to fix it up
• Sign-extends the constant to 64-bit from the bit width of MemoryVT
• Canonicalizes the materialization of constants that fit in a 16-bit signed field so that the DAG can CSE them as expected (i.e. 64-bit constants are always materialized as values sign-extended to 64 bits)

The result is

• Pre-inc loads are handled
• Good code-gen for storing negative constants
• CSE for all 64-bit constants that can be emitted using just the PPC "Load-immediate" instruction

[nemanjai]

Ping.

[bogner]

This change is really three different changes. In general it's easier to review changes that only do one thing. The DAGCombiner change here looks correct, and I took a cursory glance at the PPC changes and didn't see anything wrong.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

11372 ↗

(On Diff #123913)

This change LGTM.

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

862–863 ↗

(On Diff #123913)

This can be simplified using range-for and N->uses().

[nemanjai]

In D40348#941119, @bogner wrote:

This change is really three different changes. In general it's easier to review changes that only do one thing. The DAGCombiner change here looks correct, and I took a cursory glance at the PPC changes and didn't see anything wrong.

First off, thanks for the review Justin.

I agree that this kind of conflates multiple conceptual changes and am happy to split them out on the commit (or even just commit the first one now and post the other two as separate reviews).

1. The DAGCombiner change
2. Sign-extending the immediate for the wider constant to be stored
3. Improvements to materialization of constants

I felt that posting the DAGCombiner change in isolation wouldn't provide enough motivation so I wrapped it into this. Sorry about that.

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

862–863 ↗

(On Diff #123913)

Good point. I wonder why I did this. I think the original implementation needed to increment the iterator within the loop. In any case, it is now good for a range-for. Thanks for pointing it out.

llvm/trunk/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

static SDNode *selectI64ImmDirect(SelectionDAG *CurDAG, const SDLoc &dl,
   unsigned Hi = (Imm >> 16) & 0xFFFF;
 
   auto getI32Imm = [CurDAG, dl](unsigned Imm) {
       return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
   };
 
   // Simple value.
   if (isInt<16>(Imm)) {
+    uint64_t SextImm = SignExtend64(Lo, 16);
+    SDValue SDImm = CurDAG->getTargetConstant(SextImm, dl, MVT::i64);
     // Just the Lo bits.
-    Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, getI32Imm(Lo));
+    Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, SDImm);
   } else if (Lo) {
     // Handle the Hi bits.
     unsigned OpC = Hi ? PPC::LIS8 : PPC::LI8;
     Result = CurDAG->getMachineNode(OpC, dl, MVT::i64, getI32Imm(Hi));
     // And Lo bits.
     Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64,
                                     SDValue(Result, 0), getI32Imm(Lo));
   } else {
auto getI32Imm = [CurDAG, dl](unsigned Imm) {
       return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
   };
 
   SDValue Val = SDValue(selectI64ImmDirect(CurDAG, dl, MatImm), 0);
   return CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64, Val,
                                 getI32Imm(64 - RMin), getI32Imm(MaskEnd));
 }
 
+static unsigned allUsesTruncate(SelectionDAG *CurDAG, SDNode *N) {
+  unsigned MaxTruncation = 0;
+  // Cannot use range-based for loop here as we need the actual use (i.e. we
+  // need the operand number corresponding to the use). A range-based for
+  // will unbox the use and provide an SDNode*.
+  for (SDNode::use_iterator Use = N->use_begin(), UseEnd = N->use_end();
+       Use != UseEnd; ++Use) {
+    unsigned Opc =
+      Use->isMachineOpcode() ? Use->getMachineOpcode() : Use->getOpcode();
+    switch (Opc) {
+    default: return 0;
+    case ISD::TRUNCATE:
+      if (Use->isMachineOpcode())
+        return 0;
+      MaxTruncation =
+        std::max(MaxTruncation, Use->getValueType(0).getSizeInBits());
+      continue;
+    case ISD::STORE: {
+      if (Use->isMachineOpcode())
+        return 0;
+      StoreSDNode *STN = cast<StoreSDNode>(*Use);
+      unsigned MemVTSize = STN->getMemoryVT().getSizeInBits();
+      if (MemVTSize == 64 || Use.getOperandNo() != 0)
+        return 0;
+      MaxTruncation = std::max(MaxTruncation, MemVTSize);
+      continue;
+    }
+    case PPC::STW8:
+    case PPC::STWX8:
+    case PPC::STWU8:
+    case PPC::STWUX8:
+      if (Use.getOperandNo() != 0)
+        return 0;
+      MaxTruncation = std::max(MaxTruncation, 32u);
+      continue;
+    case PPC::STH8:
+    case PPC::STHX8:
+    case PPC::STHU8:
+    case PPC::STHUX8:
+      if (Use.getOperandNo() != 0)
+        return 0;
+      MaxTruncation = std::max(MaxTruncation, 16u);
+      continue;
+    case PPC::STB8:
+    case PPC::STBX8:
+    case PPC::STBU8:
+    case PPC::STBUX8:
+      if (Use.getOperandNo() != 0)
+        return 0;
+      MaxTruncation = std::max(MaxTruncation, 8u);
+      continue;
+    }
+  }
+  return MaxTruncation;
+}
+
 // Select a 64-bit constant.
 static SDNode *selectI64Imm(SelectionDAG *CurDAG, SDNode *N) {
   SDLoc dl(N);
 
   // Get 64 bit value.
   int64_t Imm = cast<ConstantSDNode>(N)->getZExtValue();
+  if (unsigned MinSize = allUsesTruncate(CurDAG, N)) {
+    uint64_t SextImm = SignExtend64(Imm, MinSize);
+    SDValue SDImm = CurDAG->getTargetConstant(SextImm, dl, MVT::i64);
+    if (isInt<16>(SextImm))
+      return CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, SDImm);
+  }
   return selectI64Imm(CurDAG, dl, Imm);
 }
 
 namespace {
 
 class BitPermutationSelector {
   struct ValueBit {
     SDValue V;

llvm/trunk/test/CodeGen/PowerPC/store-constant.ll

 ; RUN: llc < %s -mtriple=powerpc64-unknown-linux-gnu -mcpu=pwr8 -verify-machineinstrs | FileCheck %s
 
+@CVal = external local_unnamed_addr global i8, align 1
+@SVal = external local_unnamed_addr global i16, align 2
+@IVal = external local_unnamed_addr global i32, align 4
+@LVal = external local_unnamed_addr global i64, align 8
+@USVal = external local_unnamed_addr global i16, align 2
+@arr = external local_unnamed_addr global i64*, align 8
+@arri = external local_unnamed_addr global i32*, align 8
+
 ; Test the same constant can be used by different stores.
 
 %struct.S = type { i64, i8, i16, i32 }
 
 define void @foo(%struct.S* %p) {
   %l4 = bitcast %struct.S* %p to i64*
   store i64 0, i64* %l4, align 8
   %c = getelementptr %struct.S, %struct.S* %p, i64 0, i32 1

 ; CHECK-LABEL: @bar
 ; CHECK:       li 4, 2
 ; CHECK:       stw 4, 12(3)
 ; CHECK:       sth 4, 10(3)
 ; CHECK:       std 4, 0(3)
 ; CHECK:       stb 4, 8(3)
 }
 
+; Function Attrs: norecurse nounwind
+define void @setSmallNeg() {
+entry:
+  store i8 -7, i8* @CVal, align 1
+  store i16 -7, i16* @SVal, align 2
+  store i32 -7, i32* @IVal, align 4
+  store i64 -7, i64* @LVal, align 8
+  ret void
+; CHECK-LABEL: setSmallNeg
+; CHECK: li 7, -7
+; CHECK-DAG: stb 7,
+; CHECK-DAG: sth 7,
+; CHECK-DAG: stw 7,
+; CHECK-DAG: std 7,
+}
+
+; Function Attrs: norecurse nounwind
+define void @setSmallPos() {
+entry:
+  store i8 8, i8* @CVal, align 1
+  store i16 8, i16* @SVal, align 2
+  store i32 8, i32* @IVal, align 4
+  store i64 8, i64* @LVal, align 8
+  ret void
+; CHECK-LABEL: setSmallPos
+; CHECK: li 7, 8
+; CHECK-DAG: stb 7,
+; CHECK-DAG: sth 7,
+; CHECK-DAG: stw 7,
+; CHECK-DAG: std 7,
+}
+
+; Function Attrs: norecurse nounwind
+define void @setMaxNeg() {
+entry:
+  store i16 -32768, i16* @SVal, align 2
+  store i32 -32768, i32* @IVal, align 4
+  store i64 -32768, i64* @LVal, align 8
+  ret void
+; CHECK-LABEL: setMaxNeg
+; CHECK: li 6, -32768
+; CHECK-DAG: sth 6,
+; CHECK-DAG: stw 6,
+; CHECK-DAG: std 6,
+}
+
+; Function Attrs: norecurse nounwind
+define void @setMaxPos() {
+entry:
+  store i16 32767, i16* @SVal, align 2
+  store i32 32767, i32* @IVal, align 4
+  store i64 32767, i64* @LVal, align 8
+  ret void
+; CHECK-LABEL: setMaxPos
+; CHECK: li 6, 32767
+; CHECK-DAG: sth 6,
+; CHECK-DAG: stw 6,
+; CHECK-DAG: std 6,
+}
+
+; Function Attrs: norecurse nounwind
+define void @setExcessiveNeg() {
+entry:
+  store i32 -32769, i32* @IVal, align 4
+  store i64 -32769, i64* @LVal, align 8
+  ret void
+; CHECK-LABEL: setExcessiveNeg
+; CHECK: lis 5, -1
+; CHECK: ori 5, 5, 32767
+; CHECK-DAG: stw 5,
+; CHECK-DAG: std 5,
+}
+
+; Function Attrs: norecurse nounwind
+define void @setExcessivePos() {
+entry:
+  store i16 -32768, i16* @USVal, align 2
+  store i32 32768, i32* @IVal, align 4
+  store i64 32768, i64* @LVal, align 8
+  ret void
+; CHECK-LABEL: setExcessivePos
+; CHECK: li 6, 0
+; CHECK: ori 6, 6, 32768
+; CHECK-DAG: sth 6,
+; CHECK-DAG: stw 6,
+; CHECK-DAG: std 6,
+}
+
+define void @SetArr(i32 signext %Len) {
+entry:
+  %cmp7 = icmp sgt i32 %Len, 0
+  br i1 %cmp7, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry
+  %0 = load i64*, i64** @arr, align 8
+  %1 = load i32*, i32** @arri, align 8
+  %wide.trip.count = zext i32 %Len to i64
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i64, i64* %0, i64 %indvars.iv
+  store i64 -7, i64* %arrayidx, align 8
+  %arrayidx2 = getelementptr inbounds i32, i32* %1, i64 %indvars.iv
+  store i32 -7, i32* %arrayidx2, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+; CHECK-LABEL: SetArr
+; CHECK: li 5, -7
+; CHECK: stdu 5, 8(3)
+; CHECK: stwu 5, 4(4)
+}
+
+define void @setSameValDiffSizeCI() {
+entry:
+  store i32 255, i32* @IVal, align 4
+  store i8 -1, i8* @CVal, align 1
+  ret void
+; CHECK-LABEL: setSameValDiffSizeCI
+; CHECK: li 5, 255
+; CHECK-DAG: stb 5,
+; CHECK-DAG: stw 5,
+}
+
+define void @setSameValDiffSizeSI() {
+entry:
+  store i32 65535, i32* @IVal, align 4
+  store i16 -1, i16* @SVal, align 2
+  ret void
+; CHECK-LABEL: setSameValDiffSizeSI
+; CHECK: li 5, 0
+; CHECK: ori 5, 5, 65535
+; CHECK-DAG: sth 5,
+; CHECK-DAG: stw 5,
+}

llvm/trunk/test/CodeGen/PowerPC/testComparesigeuc.ll

 ; Function Attrs: norecurse nounwind
 define void @test_igeuc_sext_z_store(i8 zeroext %a) {
 entry:
   %cmp = icmp uge i8 %a, 0
   %conv3 = sext i1 %cmp to i8
   store i8 %conv3, i8* @glob
   ret void
 ; CHECK-LABEL: @test_igeuc_sext_z_store
-; CHECK: li [[REG1:r[0-9]+]], 255
+; CHECK: li [[REG1:r[0-9]+]], -1
 ; CHECK: stb [[REG1]]
 ; CHECK: blr
 }

llvm/trunk/test/CodeGen/PowerPC/testComparesigeus.ll

 ; Function Attrs: norecurse nounwind
 define void @test_igeus_sext_z_store(i16 zeroext %a) {
 entry:
   %cmp = icmp uge i16 %a, 0
   %conv3 = sext i1 %cmp to i16
   store i16 %conv3, i16* @glob
   ret void
 ; CHECK-LABEL: @test_igeus_sext_z_store
-; CHECK: li [[REG1:r[0-9]+]], 0
-; CHECK: ori [[REG2:r[0-9]+]], [[REG1]], 65535
-; CHECK: sth [[REG2]]
+; CHECK: li [[REG1:r[0-9]+]], -1
+; CHECK: sth [[REG1]]
 ; CHECK: blr
 }
 

llvm/trunk/test/CodeGen/PowerPC/testComparesllgeuc.ll

 ; Function Attrs: norecurse nounwind
 define void @test_llgeuc_sext_z_store(i8 zeroext %a) {
 entry:
   %cmp = icmp uge i8 %a, 0
   %conv1 = sext i1 %cmp to i8
   store i8 %conv1, i8* @glob
   ret void
 ; CHECK-LABEL: @test_llgeuc_sext_z_store
-; CHECK: li [[REG1:r[0-9]+]], 255
+; CHECK: li [[REG1:r[0-9]+]], -1
 ; CHECK: stb [[REG1]]
 ; CHECK: blr
 }
 

llvm/trunk/test/CodeGen/PowerPC/testComparesllgeus.ll

 ; Function Attrs: norecurse nounwind
 define void @test_llgeus_sext_z_store(i16 zeroext %a) {
 entry:
   %cmp = icmp uge i16 %a, 0
   %conv1 = sext i1 %cmp to i16
   store i16 %conv1, i16* @glob
   ret void
 ; CHECK-LABEL: @test_llgeus_sext_z_store
-; CHECK: li [[REG1:r[0-9]+]], 0
-; CHECK: ori [[REG2:r[0-9]+]], [[REG1]], 65535
-; CHECK: sth [[REG2]]
+; CHECK: li [[REG1:r[0-9]+]], -1
+; CHECK: sth [[REG1]]
 ; CHECK: blr  
 }