[PowerPC] Remove redundant TOC saves

[syzaara]

Summary

This patch adds a peep hole optimization to remove any redundant toc save instructions added as part of the call sequence for indirect calls. It removes any toc saves within a function that are dominated by another toc save.

[nemanjai]

lib/Target/PowerPC/PPCMIPeephole.cpp

81

Please don't copy the list by passing it by-value.

215

I know that this won't really change for the ABI you're doing this on, but the TOC frame offset is available in PPCFrameLowering::getTOCSaveOffset(). In fact, I would extract the logic into a function like PPCInstrInfo::isTOCSaveMI(MachineInstr &) so that we contain the logic in one place if we want to handle other ABI's, etc.

217

These won't change within the enclosing loop. So why not check this first and don't bother with any of the other checks if this doesn't pass (i.e. this should be the first early exit from this case).

914

To be honest with you, I kind of cringe when I see code that does a quadratic iteration over a container and erases elements from the container, invalidating the iterators.
I don't know if it is a problem if the iterator you're using to erase is before the iterator in the outer loop. How about before?

I think I'd opt for a solution that does all the erasing in a single pass over the data structure. Whether the easiest way to achieve that is to maintain two lists (ToErase and ToKeep) or converting this to a map<MachineInstr *, bool> where the bool would be set if the instruction is proven safe to erase, or something entirely different...

[nemanjai]

Also, for the test cases that have to keep multiple TOC saves, can you just add a comment as to why it isn't safe to remove one (i.e. neither dominates the other, etc.).

lib/Target/PowerPC/PPCMIPeephole.cpp

192

If we already know we're not keeping the instruction at the iterator point, no reason to check.

if (It->second && MDT->dominates(MI, CurrInst))
  It->second = false;

198

It should be safe to break out of the loop here. Dominance is transitive. If CurrInst dominates MI, it will also dominate anything that MI dominates - and when CurrInst was inserted, it has updated all instructions it dominates.

915

I think this can be a range-based for loop now.

[nemanjai]

LGTM.
The remaining comments are essentially just minor nits.

lib/Target/PowerPC/PPCMIPeephole.cpp

187

Please add an assert that MI is the right type of instruction. Perhaps

assert(TII.isTOCSaveMI(MI) &&
       "Expecting a TOC save instruction here");

202

Formatting nit - no space after the left paren. It also seems more natural to use the array access operator here:
TOCSaves[MI] = Keep;

915

I think it would be useful to have a statistic that would count the number of functions that have multiple TOC saves that must be kept here. You would then increment that statistic if you hit more than one element here that has .second == true.

lib/Target/PowerPC/PPCMIPeephole.cpp

 #include "PPCInstrInfo.h"
 #include "PPCTargetMachine.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
-#include "llvm/ADT/Statistic.h"
 #include "MCTargetDesc/PPCPredicates.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "ppc-mi-peepholes"
 
+STATISTIC(RemoveTOCSave, "Number of TOC saves removed");
 STATISTIC(NumEliminatedSExt, "Number of eliminated sign-extensions");
 STATISTIC(NumEliminatedZExt, "Number of eliminated zero-extensions");
 STATISTIC(NumOptADDLIs, "Number of optimized ADD instruction fed by LI");
 
 static cl::opt<bool>
     EnableSExtElimination("ppc-eliminate-signext",
                           cl::desc("enable elimination of sign-extensions"),
                           cl::init(false), cl::Hidden);
private:
   // Initialize class variables.
   void initialize(MachineFunction &MFParm);
 
   // Perform peepholes.
   bool simplifyCode(void);
 
   // Perform peepholes.
   bool eliminateRedundantCompare(void);
+  bool eliminateRedundantTOCSaves(std::list<MachineInstr *> TOCSaves);
 
   // Find the "true" register represented by SrcReg (following chains
   // of copies and subreg_to_reg operations).
   unsigned lookThruCopyLike(unsigned SrcReg);
 
 public:
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
getKnownLeadingZeroCount(MachineInstr *MI, const PPCInstrInfo *TII) {
 
   return 0;
 }
 
 // Perform peephole optimizations.
 bool PPCMIPeephole::simplifyCode(void) {
   bool Simplified = false;
   MachineInstr* ToErase = nullptr;
+  std::list<MachineInstr *> TOCSaves;
 
   for (MachineBasicBlock &MBB : *MF) {
     for (MachineInstr &MI : MBB) {
 
       // If the previous instruction was marked for elimination,
       // remove it now.
       if (ToErase) {
         ToErase->eraseFromParent();
         ToErase = nullptr;
       }
 
       // Ignore debug instructions.
       if (MI.isDebugValue())
         continue;
 
       // Per-opcode peepholes.
       switch (MI.getOpcode()) {
 
       default:
         break;
 
+      case PPC::STD: {
+        // Store all TOC save instructions, std r2,24(r1), into TOCSaves list
+        // for function eliminateRedundantTOCSaves. This function will then
+        // remove any TOC saves which are redundant due to having a dominating
+        // save.
+        if (!MI.getOperand(1).isImm() || !MI.getOperand(2).isReg())
+          break;
+        unsigned StackOffset = MI.getOperand(1).getImm();
+        unsigned StackReg = MI.getOperand(2).getReg();
+        if (StackReg == PPC::X1 && StackOffset == 24) {
+          MachineFrameInfo &MFI = MF->getFrameInfo();
+          if (MFI.hasVarSizedObjects() ||
+              !MF->getSubtarget<PPCSubtarget>().isELFv2ABI())
+            break;
+          TOCSaves.push_back(&MI);
+        }
+        break;
+      }
       case PPC::XXPERMDI: {
         // Perform simplifications of 2x64 vector swaps and splats.
         // A swap is identified by an immediate value of 2, and a splat
         // is identified by an immediate value of 0 or 3.
         int Immed = MI.getOperand(3).getImm();
 
         if (Immed != 1) {
 
for (MachineBasicBlock &MBB : *MF) {
     // If the last instruction was marked for elimination,
     // remove it now.
     if (ToErase) {
       ToErase->eraseFromParent();
       ToErase = nullptr;
     }
   }
 
+  Simplified |= eliminateRedundantTOCSaves(TOCSaves);
   // We try to eliminate redundant compare instruction.
   Simplified |= eliminateRedundantCompare();
 
   return Simplified;
 }
 
 // helper functions for eliminateRedundantCompare
 static bool isEqOrNe(MachineInstr *BI) {
else if (NumPredBBs == 2) {
     PredMBB = Pred1MBB;
     MBBtoMoveCmp = Pred2MBB;
     return true;
   }
 
   return false;
 }
 
+// This function will iterate over the input list containing TOC save
+// instructions found in the Machine Function and remove the ones which are
+// dominated by another TOC Save instruction.
+bool PPCMIPeephole::eliminateRedundantTOCSaves(
+    std::list<MachineInstr *> TOCSaves) {
+  bool Simplified = false;
+  for (auto Iter = TOCSaves.begin(); Iter != TOCSaves.end(); Iter++) {
+    MachineInstr *CurrSave = *Iter;
+    auto Iter2 = TOCSaves.begin();
+    while (Iter2 != TOCSaves.end()) {
+      if ((Iter != Iter2) && (MDT->dominates(CurrSave, *Iter2))) {
+        (*Iter2)->eraseFromParent();
+        Iter2 = TOCSaves.erase(Iter2);
+        Simplified = true;
+        RemoveTOCSave++;
+      } else {
+        Iter2++;
+      }
+    }
+  }
+
+  return Simplified;
+}
+
 // If multiple conditional branches are executed based on the (essentially)
 // same comparison, we merge compare instructions into one and make multiple
 // conditional branches on this comparison.
 // For example,
 //   if (a == 0) { ... }
 //   else if (a < 0) { ... }
 // can be executed by one compare and two conditional branches instead of
 // two pairs of a compare and a conditional branch.

test/CodeGen/PowerPC/remove-redundant-toc-saves.ll

+; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu < %s | FileCheck %s
+define signext i32 @test1(i32 signext %i, i32 (i32)* nocapture %Func, i32 (i32)* nocapture %Func2) {
+entry:
+; CHECK-LABEL: test1:
+; CHECK:    std 2, 24(1)
+; CHECK-NOT:    std 2, 24(1)
+  %call = tail call signext i32 %Func(i32 signext %i)
+  %call1 = tail call signext i32 %Func2(i32 signext %i)
+  %add2 = add nsw i32 %call1, %call
+  ret i32 %add2
+}
+
+define signext i32 @test2(i32 signext %i, i32 signext %j, i32 (i32)* nocapture %Func, i32 (i32)* nocapture %Func2) {
+entry:
+; CHECK-LABEL: test2:
+; CHECK:    std 2, 24(1)
+; CHECK-NOT:    std 2, 24(1)
+  %call = tail call signext i32 %Func(i32 signext %i)
+  %tobool = icmp eq i32 %j, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call1 = tail call signext i32 %Func(i32 signext %i)
+  %add2 = add nsw i32 %call1, %call
+  %call3 = tail call signext i32 %Func2(i32 signext %i)
+  %add4 = add nsw i32 %add2, %call3
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %Sum.0 = phi i32 [ %add4, %if.then ], [ %call, %entry ]
+  %call5 = tail call signext i32 %Func(i32 signext %i)
+  %add6 = add nsw i32 %call5, %Sum.0
+  ret i32 %add6
+}
+
+define signext i32 @test3(i32 signext %i, i32 (i32)* nocapture %Func, i32 (i32)* nocapture %Func2) {
+; CHECK-LABEL: test3:
+; CHECK:    std 2, 24(1)
+; CHECK:    std 2, 24(1)
+; CHECK-NOT:    std 2, 24(1)
+entry:
+  %tobool = icmp eq i32 %i, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i32 %Func(i32 signext %i)
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %call1 = tail call signext i32 %Func2(i32 signext 0)
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %Sum.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]
+  %call3 = tail call signext i32 %Func(i32 signext %i)
+  %add4 = add nsw i32 %call3, %Sum.0
+  ret i32 %add4
+}
+
+define signext i32 @test4(i32 signext %i, i32 (i32)* nocapture %Func, i32 (i32)* nocapture %Func2) {
+; CHECK-LABEL: test4:
+; CHECK:    std 2, 24(1)
+; CHECK-NOT:    std 2, 24(1)
+
+entry:
+  %call = tail call signext i32 %Func(i32 signext %i)
+  %tobool = icmp eq i32 %i, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call1 = tail call signext i32 %Func(i32 signext %i)
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %call3 = tail call signext i32 %Func2(i32 signext 0)
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %call1.pn = phi i32 [ %call1, %if.then ], [ %call3, %if.else ]
+  %Sum.0 = add nsw i32 %call1.pn, %call
+  ret i32 %Sum.0
+}
+
+define signext i32 @test5(i32 signext %i, i32 (i32)* nocapture %Func, i32 (i32)* nocapture readnone %Func2) {
+entry:
+; CHECK-LABEL: test5:
+; CHECK:    std 2, 24(1)
+; CHECK:    std 2, 24(1)
+
+  %tobool = icmp eq i32 %i, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call signext i32 %Func(i32 signext %i)
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %Sum.0 = phi i32 [ %call, %if.then ], [ 0, %entry ]
+  %call1 = tail call signext i32 %Func(i32 signext %i)
+  %add2 = add nsw i32 %call1, %Sum.0
+  ret i32 %add2
+}
+
+define signext i32 @test6(i32 signext %i, i32 (i32)* nocapture %Func, i32 (i32)* nocapture %Func2) {
+entry:
+; CHECK-LABEL: test6:
+; CHECK:    std 2, 24(1)
+; CHECK:    std 2, 24(1)
+
+  %conv = sext i32 %i to i64
+  %0 = alloca i8, i64 %conv, align 16
+  %1 = bitcast i8* %0 to i32*
+  %call = tail call signext i32 %Func(i32 signext %i)
+  call void @useAlloca(i32* nonnull %1, i32 signext %call)
+  %call1 = call signext i32 %Func2(i32 signext %i)
+  %add2 = add nsw i32 %call1, %call
+  ret i32 %add2
+}
+
+declare void @useAlloca(i32*, i32 signext)