[PowerPC] define target hook isReallyTriviallyReMaterializable

[lei]

Summary

Trivially rematerializable instructions are instructions that has no side effects and requires no operands that are not always available. The PPC instructions ADDIStocHA and ADDItocL are trivially rematerializable because it does a ADDIS/ADDI on the TOC register and an immediate. On PowerPC the ABI reserves the TOC register (X2) in any functions that have calls or access global variables.

Define target hook isReallyTriviallyReMaterializable() to explicitly specify PowerPC instructions that are trivially rematerializable. This will allow MachineLICM pass to accurately identify PPC instructions that should always be hoisted.

Spec 2006 Results (>1 indicates improvement):

	SpeedUp
SPEC_INT
400.perlbench	1.000
401.bzip2	1.000
403.gcc	0.998
429.mcf	1.009
445.gobmk	1.005
456.hmmer	1.001
458.sjeng	1.011
462.libquantum	1.006
464.h264ref	1.044
471.omnetpp	1.001
473.astar	1.000
483.xalancbmk	1.005
SPEC_FP
433.milc	0.999
444.namd	0.987
447.dealII	1.000
450.soplex	0.995
453.povray	0.995
470.lbm	0.996
482.sphinx3	1.001

[lei]

test/CodeGen/PowerPC/licm-remat.ll

29 ↗

(On Diff #102752)

This should be CHECK-DAG ... will update

[lei]

update test case

[echristo]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

This needs a comment as to why each of these need to be marked as rematerializable here rather than in the .td file.

299 ↗

(On Diff #102835)

I'm not sure an unreachable is the right thing here - usually this is reserved for switch cases that can't be true rather than just a return false.

[lei]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

Will add:

// The Rematerializable flag is deprecated and if it is set, isReallyTriviallyReMaterializable() method need to be called to verify the instruction is really rematable.

[echristo]

Can you send out a patch to make that comment on the base routine as well?

[MatzeB]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

Why do you get the impression that this flag is deprecated? It's just not the only thing checked as far as I can see.

299 ↗

(On Diff #102835)

This really should only be called for opcodes with the ReMaterializable flag set, so unreachable seems correct to me.

[echristo]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

Yeah. I was wondering about that. Also, that's really confusing. The routine itself could use a comment update explaining what's going on? Or at least it wasn't horribly clear to me.

299 ↗

(On Diff #102835)

Ah. I missed that, OK then. Probably needs to be something like "unknown rematerializable operation" or something.

[MatzeB]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

Indeed that is one of the many things in CodeGen that are really confusing (and unnecessarily so it seems). However stating it is deprecated will only add to to the confusion unless there are concrete plans to do something about it.

And I'd certainly welcome a change that removes the MCInstrDesc bit and only uses the callback and measures that it is indeed negligible in terms of compiletime.

[nemanjai]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

I would imagine that the comment about the deprecation of the flag comes right out of include/llvm/CodeGen/MachineInstr.h:

This flag is deprecated, please don't use it anymore.  If this
flag is set, the isReallyTriviallyReMaterializable() method is called to
verify the instruction is really rematable.

[lei]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

Yes. That is where I got the impression this flag is deprecated.

[lei]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

I'll add a comment here, but a detailed description can also be found in include/llvm/Target/TargetInstrInfo.h

/// For instructions with opcodes for which the M_REMATERIALIZABLE flag is
/// set, this hook lets the target specify whether the instruction is actually
/// trivially rematerializable, taking into consideration its operands. This
/// predicate must return false if the instruction has any side effects other
/// than producing a value, or if it requres any address registers that are
/// not always available.
/// Requirements must be check as stated in isTriviallyReMaterializable() .
virtual bool isReallyTriviallyReMaterializable(const MachineInstr &MI,
                                               AliasAnalysis *AA) const {
  return false;
}

[MatzeB]

lib/Target/PowerPC/PPCInstrInfo.cpp

295 ↗

(On Diff #102835)

I would imagine that the comment about the deprecation of the flag comes right out of include/llvm/CodeGen/MachineInstr.h:

Ah, I was looking at include/llvm/Target/Target.td for the definition/explanation of the instruction flags on the tablegen side (because at the point in MCInstrDesc.h where they are defined we have no further explanation). Odd that we only had the deprecation information on the convenience function in MachineInstr.

[lei]

Addressed all review comments.

[echristo]

This is fine with me. I'll let Matthias do the final ack.

[MatzeB]

LGTM

llvm/trunk/lib/Target/PowerPC/PPCInstr64Bit.td

 def LDMX : XForm_1<31, 309, (outs g8rc:$rD), (ins memrr:$src),
                    "ldmx $rD, $src", IIC_LdStLD, []>, isPPC64,
            Requires<[IsISA3_0]>;
 }
 }
 
 // Support for medium and large code model.
 let hasSideEffects = 0 in {
+let isReMaterializable = 1 in {
 def ADDIStocHA: Pseudo<(outs g8rc:$rD), (ins g8rc_nox0:$reg, tocentry:$disp),
                        "#ADDIStocHA", []>, isPPC64;
+def ADDItocL: Pseudo<(outs g8rc:$rD), (ins g8rc_nox0:$reg, tocentry:$disp),
+                     "#ADDItocL", []>, isPPC64;
+}
 let mayLoad = 1 in
 def LDtocL: Pseudo<(outs g8rc:$rD), (ins tocentry:$disp, g8rc_nox0:$reg),
                    "#LDtocL", []>, isPPC64;
-def ADDItocL: Pseudo<(outs g8rc:$rD), (ins g8rc_nox0:$reg, tocentry:$disp),
-                     "#ADDItocL", []>, isPPC64;
 }
 
 // Support for thread-local storage.
 def ADDISgotTprelHA: Pseudo<(outs g8rc:$rD), (ins g8rc_nox0:$reg, s16imm64:$disp),
                          "#ADDISgotTprelHA",
                          [(set i64:$rD,
                            (PPCaddisGotTprelHA i64:$reg,
                                                tglobaltlsaddr:$disp))]>,

llvm/trunk/lib/Target/PowerPC/PPCInstrInfo.h

public:
 
   bool isAssociativeAndCommutative(const MachineInstr &Inst) const override;
 
   bool isCoalescableExtInstr(const MachineInstr &MI,
                              unsigned &SrcReg, unsigned &DstReg,
                              unsigned &SubIdx) const override;
   unsigned isLoadFromStackSlot(const MachineInstr &MI,
                                int &FrameIndex) const override;
+  bool isReallyTriviallyReMaterializable(const MachineInstr &MI,
+                                         AliasAnalysis *AA) const override;
   unsigned isStoreToStackSlot(const MachineInstr &MI,
                               int &FrameIndex) const override;
 
   bool findCommutedOpIndices(MachineInstr &MI, unsigned &SrcOpIdx1,
                              unsigned &SrcOpIdx2) const override;
 
   void insertNoop(MachineBasicBlock &MBB,
                   MachineBasicBlock::iterator MI) const override;

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

if (MI.getOperand(1).isImm() && !MI.getOperand(1).getImm() &&
       FrameIndex = MI.getOperand(2).getIndex();
       return MI.getOperand(0).getReg();
     }
     break;
   }
   return 0;
 }
 
+// For opcodes with the ReMaterializable flag set, this function is called to
+// verify the instruction is really rematable.  
+bool PPCInstrInfo::isReallyTriviallyReMaterializable(const MachineInstr &MI,
+                                                     AliasAnalysis *AA) const {
+  switch (MI.getOpcode()) {
+  default: 
+    // This function should only be called for opcodes with the ReMaterializable
+    // flag set.
+    llvm_unreachable("Unknown rematerializable operation!");
+    break;
+  case PPC::LI:
+  case PPC::LI8:
+  case PPC::LIS:
+  case PPC::LIS8:
+  case PPC::QVGPCI:
+  case PPC::ADDIStocHA:
+  case PPC::ADDItocL:
+  case PPC::LOAD_STACK_GUARD:
+    return true;
+  }
+  return false;
+}
+
 unsigned PPCInstrInfo::isStoreToStackSlot(const MachineInstr &MI,
                                           int &FrameIndex) const {
   // Note: This list must be kept consistent with StoreRegToStackSlot.
   switch (MI.getOpcode()) {
   default: break;
   case PPC::STD:
   case PPC::STW:
   case PPC::STFS:

llvm/trunk/test/CodeGen/PowerPC/licm-remat.ll

+; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu < %s | FileCheck %s
+
+; Test case is reduced from the snappy benchmark.
+; Verify MachineLICM will always hoist trivially rematerializable instructions even when register pressure is high.
+
+%"class.snappy::SnappyDecompressor" = type <{ %"class.snappy::Source"*, i8*, i8*, i32, i8, [5 x i8], [6 x i8] }>
+%"class.snappy::Source" = type { i32 (...)** }
+%"struct.snappy::iovec" = type { i8*, i64 }
+%"class.snappy::SnappyIOVecWriter" = type { %"struct.snappy::iovec"*, i64, i64, i64, i64, i64 }
+
+@_ZN6snappy8internalL10char_tableE = internal unnamed_addr constant [5 x i16] [i16 1, i16 2052, i16 4097, i16 8193, i16 2], align 2
+@_ZN6snappy8internalL8wordmaskE = internal unnamed_addr constant [5 x i32] [i32 0, i32 255, i32 65535, i32 16777215, i32 -1], align 4
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1) #2
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1) #2
+
+define linkonce_odr void @ZN6snappyDecompressor_(%"class.snappy::SnappyDecompressor"* %this, %"class.snappy::SnappyIOVecWriter"* %writer) {
+; CHECK-LABEL: ZN6snappyDecompressor_:
+; CHECK:       # BB#0: # %entry
+; CHECK:       addis 3, 2, _ZN6snappy8internalL8wordmaskE@toc@ha
+; CHECK-DAG:   addi 25, 3, _ZN6snappy8internalL8wordmaskE@toc@l
+; CHECK-DAG:   addis 4, 2, _ZN6snappy8internalL10char_tableE@toc@ha
+; CHECK-DAG:   addi 24, 4, _ZN6snappy8internalL10char_tableE@toc@l
+; CHECK:       b .LBB0_2
+; CHECK:       .LBB0_2: # %for.cond
+; CHECK-NOT:   addis {{[0-9]+}}, 2, _ZN6snappy8internalL8wordmaskE@toc@ha
+; CHECK-NOT:   addis {{[0-9]+}}, 2, _ZN6snappy8internalL10char_tableE@toc@ha
+; CHECK:       bctrl
+entry:
+  %ip_limit_ = getelementptr inbounds %"class.snappy::SnappyDecompressor", %"class.snappy::SnappyDecompressor"* %this, i64 0, i32 2
+  %0 = bitcast i8** %ip_limit_ to i64*
+  %curr_iov_index_.i = getelementptr inbounds %"class.snappy::SnappyIOVecWriter", %"class.snappy::SnappyIOVecWriter"* %writer, i64 0, i32 2
+  %curr_iov_written_.i = getelementptr inbounds %"class.snappy::SnappyIOVecWriter", %"class.snappy::SnappyIOVecWriter"* %writer, i64 0, i32 3
+  %1 = bitcast i64* %curr_iov_written_.i to <2 x i64>*
+  br label %for.cond
+
+for.cond:                                         ; preds = %if.end82, %if.then56, %if.end49, %entry
+  %ip.0 = phi i8* [ null, %entry ], [ %add.ptr50, %if.end49 ], [ null, %if.then56 ], [ undef, %if.end82 ]
+  %incdec.ptr = getelementptr inbounds i8, i8* %ip.0, i64 1
+  %2 = load i8, i8* %ip.0, align 1
+  %conv = zext i8 %2 to i32
+  br i1 undef, label %if.then7, label %if.else
+
+if.then7:                                         ; preds = %for.cond
+  %3 = lshr i32 %conv, 2
+  %add = add nuw nsw i32 %3, 1
+  %conv9 = zext i32 %add to i64
+  %4 = load i64, i64* %0, align 8
+  %sub.ptr.sub13 = sub i64 %4, 0
+  %5 = load i64, i64* undef, align 8
+  %6 = load i64, i64* null, align 8
+  %sub.i = sub i64 %5, %6
+  %cmp.i = icmp ult i32 %add, 17
+  %cmp2.i = icmp ugt i64 %sub.ptr.sub13, 20
+  %or.cond.i = and i1 %cmp.i, %cmp2.i
+  %cmp4.i = icmp ugt i64 %sub.i, 15
+  %or.cond13.i = and i1 %or.cond.i, %cmp4.i
+  br i1 %or.cond13.i, label %land.lhs.true5.i, label %if.end17
+
+land.lhs.true5.i:                                 ; preds = %if.then7
+  %7 = load %"struct.snappy::iovec"*, %"struct.snappy::iovec"** undef, align 8
+  %8 = load i64, i64* %curr_iov_index_.i, align 8
+  %9 = load i64, i64* %curr_iov_written_.i, align 8
+  %sub6.i = sub i64 0, %9
+  %cmp7.i = icmp ugt i64 %sub6.i, 15
+  br i1 %cmp7.i, label %cleanup102, label %if.end17
+
+if.end17:                                         ; preds = %land.lhs.true5.i, %if.then7
+  %sub = add nsw i64 %conv9, -60
+  %10 = load i32, i32* undef, align 4
+  %arrayidx = getelementptr inbounds [5 x i32], [5 x i32]* @_ZN6snappy8internalL8wordmaskE, i64 0, i64 %sub
+  %11 = load i32, i32* %arrayidx, align 4
+  %and21 = and i32 %11, %10
+  %add22 = add i32 %and21, 1
+  %conv23 = zext i32 %add22 to i64
+  %add.ptr24 = getelementptr inbounds i8, i8* %incdec.ptr, i64 %sub
+  br label %if.end25
+
+if.end25:                                         ; preds = %if.end17
+  %sub.ptr.rhs.cast28 = ptrtoint i8* %add.ptr24 to i64
+  %cmp30233 = icmp ugt i64 %conv23, 0
+  br i1 %cmp30233, label %while.body.preheader, label %while.end
+
+while.body.preheader:                             ; preds = %if.end25
+  %add.i158256 = add i64 %6, 0
+  %cmp.i160257 = icmp ugt i64 %add.i158256, %5
+  br i1 %cmp.i160257, label %cleanup105, label %while.cond.preheader.i
+
+while.cond.preheader.i:                           ; preds = %while.body.preheader
+  %call39 = call i8* undef(%"class.snappy::Source"* undef, i64* nonnull undef)
+  unreachable
+
+while.end:                                        ; preds = %if.end25
+  br label %while.cond.preheader.i176
+
+while.cond.preheader.i176:                        ; preds = %while.end
+  br i1 undef, label %if.end49, label %while.body.lr.ph.i182
+
+while.body.lr.ph.i182:                            ; preds = %while.cond.preheader.i176
+  %.pre.i181 = load i64, i64* %curr_iov_written_.i, align 8
+  %12 = load %"struct.snappy::iovec"*, %"struct.snappy::iovec"** undef, align 8
+  %13 = load i64, i64* %curr_iov_index_.i, align 8
+  %iov_len.i185 = getelementptr inbounds %"struct.snappy::iovec", %"struct.snappy::iovec"* %12, i64 %13, i32 1
+  %14 = load i64, i64* %iov_len.i185, align 8
+  br label %cond.end.i190
+
+cond.end.i190:                                    ; preds = %while.body.lr.ph.i182
+  br i1 undef, label %if.end18.i207, label %if.then10.i193
+
+if.then10.i193:                                   ; preds = %cond.end.i190
+  %add12.i191 = add i64 %13, 1
+  %iov_len22.phi.trans.insert.i194 = getelementptr inbounds %"struct.snappy::iovec", %"struct.snappy::iovec"* %12, i64 %add12.i191, i32 1
+  %.pre48.i195 = load i64, i64* %iov_len22.phi.trans.insert.i194, align 8
+  br label %if.end18.i207
+
+if.end18.i207:                                    ; preds = %if.then10.i193, %cond.end.i190
+  %15 = phi i64 [ %.pre.i181, %cond.end.i190 ], [ 0, %if.then10.i193 ]
+  %16 = phi i64 [ %14, %cond.end.i190 ], [ %.pre48.i195, %if.then10.i193 ]
+  %17 = phi i64 [ %13, %cond.end.i190 ], [ %add12.i191, %if.then10.i193 ]
+  %sub.i197 = sub i64 %16, %15
+  %cmp.i.i198 = icmp ult i64 %sub.i197, %conv23
+  %.sroa.speculated.i199 = select i1 %cmp.i.i198, i64 %sub.i197, i64 %conv23
+  %iov_base.i.i200 = getelementptr inbounds %"struct.snappy::iovec", %"struct.snappy::iovec"* %12, i64 %17, i32 0
+  %18 = load i8*, i8** %iov_base.i.i200, align 8
+  %add.ptr.i.i201 = getelementptr inbounds i8, i8* %18, i64 %15
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %add.ptr.i.i201, i8* %add.ptr24, i64 %.sroa.speculated.i199, i32 1, i1 false) #12
+  %add30.i203 = add i64 0, %.sroa.speculated.i199
+  store i64 %add30.i203, i64* null, align 8
+  %.pre245 = load i64, i64* %0, align 8
+  br label %if.end49
+
+if.end49:                                         ; preds = %if.end18.i207, %while.cond.preheader.i176
+  %19 = phi i64 [ %.pre245, %if.end18.i207 ], [ %4, %while.cond.preheader.i176 ]
+  %add.ptr50 = getelementptr inbounds i8, i8* %add.ptr24, i64 %conv23
+  %sub.ptr.sub54 = sub i64 %19, 0
+  %cmp55 = icmp slt i64 %sub.ptr.sub54, 5
+  br i1 %cmp55, label %if.then56, label %for.cond
+
+if.then56:                                        ; preds = %if.end49
+  br label %for.cond
+
+if.else:                                          ; preds = %for.cond
+  %idxprom = zext i8 %2 to i64
+  %arrayidx68 = getelementptr inbounds [5 x i16], [5 x i16]* @_ZN6snappy8internalL10char_tableE, i64 0, i64 %idxprom
+  %20 = load i16, i16* %arrayidx68, align 2
+  %conv69 = zext i16 %20 to i64
+  %21 = load i32, i32* undef, align 4
+  %shr71 = lshr i64 %conv69, 11
+  %arrayidx72 = getelementptr inbounds [5 x i32], [5 x i32]* @_ZN6snappy8internalL8wordmaskE, i64 0, i64 %shr71
+  %22 = load i32, i32* %arrayidx72, align 4
+  %and73 = and i32 %22, %21
+  %conv74 = zext i32 %and73 to i64
+  %add79 = add nuw nsw i64 0, %conv74
+  %call80 = call zeroext i1 @_ZN6snappy17SnappyIOVecWriterAppendFromSelfEmm(%"class.snappy::SnappyIOVecWriter"* %writer, i64 %add79, i64 undef)
+  br i1 %call80, label %if.end82, label %cleanup105
+
+if.end82:                                         ; preds = %if.else
+  br label %for.cond
+
+cleanup102:                                       ; preds = %land.lhs.true5.i
+  %iov_base.i.i = getelementptr inbounds %"struct.snappy::iovec", %"struct.snappy::iovec"* %7, i64 %8, i32 0
+  %23 = load i8*, i8** %iov_base.i.i, align 8
+  %add.ptr.i.i = getelementptr inbounds i8, i8* %23, i64 %9
+  call void @llvm.memmove.p0i8.p0i8.i64(i8* %add.ptr.i.i, i8* %incdec.ptr, i64 16, i32 1, i1 false) #12
+  %24 = load <2 x i64>, <2 x i64>* %1, align 8
+  %25 = insertelement <2 x i64> undef, i64 %conv9, i32 0
+  %26 = shufflevector <2 x i64> %25, <2 x i64> undef, <2 x i32> zeroinitializer
+  %27 = add <2 x i64> %24, %26
+  store <2 x i64> %27, <2 x i64>* undef, align 8
+  unreachable
+
+cleanup105:                                       ; preds = %if.else, %while.body.preheader
+  ret void
+}
+
+; Function Attrs: inlinehint
+declare zeroext i1 @_ZN6snappy17SnappyIOVecWriterAppendFromSelfEmm(%"class.snappy::SnappyIOVecWriter"*, i64, i64) local_unnamed_addr #10 align 2