[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.

241

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.

243

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).

935

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

193

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;

199

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.

936

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

188

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

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

203

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

936

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/PPCInstrInfo.h

static bool isVFRegister(unsigned Reg) {
     return Reg >= PPC::VF0 && Reg <= PPC::VF31;
   }
   static bool isVRRegister(unsigned Reg) {
     return Reg >= PPC::V0 && Reg <= PPC::V31;
   }
   const TargetRegisterClass *updatedRC(const TargetRegisterClass *RC) const;
   static int getRecordFormOpcode(unsigned Opcode);
 
+  bool isTOCSaveMI(const MachineInstr &MI) const;
+
   bool isSignOrZeroExtended(const MachineInstr &MI, bool SignExt,
                             const unsigned PhiDepth) const;
 
   /// Return true if the output of the instruction is always a sign-extended,
   /// i.e. 0 to 31-th bits are same as 32-th bit.
   bool isSignExtended(const MachineInstr &MI, const unsigned depth = 0) const {
     return isSignOrZeroExtended(MI, true, depth);
   }

lib/Target/PowerPC/PPCInstrInfo.cpp

if (Opcode == PPC::CNTLZW  || Opcode == PPC::CNTLZWo ||
       Opcode == PPC::ROTRWI  || Opcode == PPC::ROTRWIo ||
       Opcode == PPC::EXTLWI  || Opcode == PPC::EXTLWIo ||
       Opcode == PPC::MFVSRWZ)
     return true;
 
   return false;
 }
 
+// This function returns true if the input MachineInstr is a TOC save
+// instruction.
+bool PPCInstrInfo::isTOCSaveMI(const MachineInstr &MI) const {
+  if (!MI.getOperand(1).isImm() || !MI.getOperand(2).isReg())
+    return false;
+  unsigned TOCSaveOffset = Subtarget.getFrameLowering()->getTOCSaveOffset();
+  unsigned StackOffset = MI.getOperand(1).getImm();
+  unsigned StackReg = MI.getOperand(2).getReg();
+  if (StackReg == PPC::X1 && StackOffset == TOCSaveOffset)
+    return true;
+
+  return false;
+}
+
 // We limit the max depth to track incoming values of PHIs or binary ops
 // (e.g. AND) to avoid exsessive cost.
 const unsigned MAX_DEPTH = 1;
 
 bool
 PPCInstrInfo::isSignOrZeroExtended(const MachineInstr &MI, bool SignExt,
                                    const unsigned Depth) const {
   const MachineFunction *MF = MI.getParent()->getParent();

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::map<MachineInstr *, bool> &TOCSaves);
+  void UpdateTOCSaves(std::map<MachineInstr *, bool> &TOCSaves,
+                      MachineInstr *MI);
   // 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 {
     AU.addRequired<MachineDominatorTree>();
if (Opcode == PPC::LBZ   || Opcode == PPC::LBZX  ||
     return 56;
 
   if (TII->isZeroExtended(*MI))
     return 32;
 
   return 0;
 }
 
+// This function maintains a map for the pairs <TOC Save Instr, Keep>
+// Each time a new TOC save is encountered, it checks if any of the exisiting
+// ones are dominated by the new one. If so, it marks the exisiting one as
+// redundant by setting it's entry in the map as false. It then adds the new
+// instruction to the map with either true or false depending on if any
+// exisiting instructions dominated the new one.
+void PPCMIPeephole::UpdateTOCSaves(
+  std::map<MachineInstr *, bool> &TOCSaves, MachineInstr *MI) {
+  bool Keep = true;
+  for (auto It = TOCSaves.begin(); It != TOCSaves.end(); It++ ) {
+    MachineInstr *CurrInst = It->first;
+    // If new instruction dominates an exisiting one, mark exisiting one as
+    // redundant.
+    if (It->second && MDT->dominates(MI, CurrInst))
+      It->second = false;
+    // Check if the new instruction is redundant.
+    if (MDT->dominates(CurrInst, MI)) {
+      Keep = false;
+      break;
+    }
+  }
+  // Add new instruction to map.
+  TOCSaves.insert( std::pair<MachineInstr *, bool> (MI, Keep));
+}
+
 // Perform peephole optimizations.
 bool PPCMIPeephole::simplifyCode(void) {
   bool Simplified = false;
   MachineInstr* ToErase = nullptr;
+  std::map<MachineInstr *, bool> 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: {
+        MachineFrameInfo &MFI = MF->getFrameInfo();
+        if (MFI.hasVarSizedObjects() ||
+            !MF->getSubtarget<PPCSubtarget>().isELFv2ABI())
+          break;
+        // When encountering a TOC save instruction, call UpdateTOCSaves
+        // to add it to the TOCSaves map and mark any exisiting TOC saves
+        // it dominates as redundant.
+        if (TII->isTOCSaveMI(MI))
+          UpdateTOCSaves(TOCSaves, &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;
     }
   }
 
+  // Eliminate all the TOC save instructions which are redundant.
+  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 map containing a pair of TOC save
+// instruction and a flag. The flag will be set to false if the TOC save is proven
+// redundant. This function will erase from the basic block all the TOC saves
+// marked as redundant.
+bool PPCMIPeephole::eliminateRedundantTOCSaves(
+    std::map<MachineInstr *, bool> &TOCSaves) {
+  bool Simplified = false;
+  for (auto TOCSave : TOCSaves) {
+    if (!TOCSave.second) {
+      TOCSave.first->eraseFromParent();
+      RemoveTOCSave++;
+      Simplified = true;
+    }
+  }
+
+  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
+}
+
+; Check for multiple TOC saves with if then else where neither dominates the other.
+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
+}
+
+; Check for multiple TOC saves with if then where neither is redundant.
+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
+}
+
+; Check for multiple TOC saves if there are dynamic allocations on the stack.
+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)