Use CXX_FAST_TLS to enable shrink wrapping on PPC

[tjablin]

Summary

This patch depends on both D17533 and D16984.

Shrink wrapping functions can improve performance for functions when the stack is unused. However, all functions where value live-ranges contain function calls are ineligible for shrink wrapping. Why?

1. To avoid saving and restoring values across call-sites, LLVM allocates values with live-ranges that cross call sites to callee-saved registers

2. If callee-saved registers are used, they must be saved (usually in the function prolog)

3. ShrinkWrapping scans from the beginning of the function prolog to the first use of the stack. If a callee-saved register is saved to the stack in the function prolog, ShrinkWrapping will give up early.

To increase the applicability of ShrinkWrapping, this pass identifies instances where a live-range straddling a call-site prevents ShrinkWrapping. The pass switches the calling convention to CXX_FAST_TLS, that saves callee registers to virtual registers. This allows the backend to make better choices about where to save registers and in many cases avoids saving registers to the stack. The exit block is privatized for the fast and slow exit paths to allow each to be specialized independently.

[tjablin]

Switch from a ModulePass to a FunctionPass since outlining is no longer performed.

[cycheng]

lib/Target/PowerPC/PPCEnableShrinkWrap.cpp

51

Since the patch aims for creating more shrink-wrapping chances, maybe we could use more appropriate names?

132

use std::any_of ?

202

This do affect sibling call optimization, because callee and caller should have same calling convention, so SCO have to handle this case.

test/CodeGen/PowerPC/EnableShrinkWrapTest.ll

2

It would be better if we could have test cases for llc, because we would like to see how this change final code gen

[kbarton]

A couple general comments:

1. Can we add statistics to collect the number of times we've made changes? I think this would be useful to understand how effective this is.
2. In general, I think we should prefer references to pointers unless there is a chance the parameter can be null. I think most of the cases here could be references. If they need to stay as pointers, please make sure we check that they are valid before using them.
3. We should also mark the parameters as const whenever they are not expected to change. I believe that is true for many of the methods here, as they are just checking for a property and then returning true/false.

lib/Target/PowerPC/PPCEnableShrinkWrap.cpp

69

These could both be reference parameters, instead of pointers.
Can they be made const as well?

116

Could this be a reference instead of a pointer?

129

Can F be const?

146

Can BB be const?

lib/Target/PowerPC/CMakeLists.txt

add_llvm_target(PowerPCCodeGen
   PPCAsmPrinter.cpp
   PPCBranchSelector.cpp
   PPCCTRLoops.cpp
   PPCHazardRecognizers.cpp
   PPCInstrInfo.cpp
   PPCISelDAGToDAG.cpp
   PPCISelLowering.cpp
   PPCEarlyReturn.cpp
+  PPCEnableShrinkWrap.cpp
   PPCFastISel.cpp
   PPCFrameLowering.cpp
   PPCLoopDataPrefetch.cpp
   PPCLoopPreIncPrep.cpp
   PPCMCInstLower.cpp
   PPCMachineFunctionInfo.cpp
   PPCMIPeephole.cpp
   PPCRegisterInfo.cpp

lib/Target/PowerPC/PPC.h

 #undef PPC
 
 namespace llvm {
   class PPCTargetMachine;
   class PassRegistry;
   class FunctionPass;
   class ImmutablePass;
   class MachineInstr;
+  class ModulePass;
   class AsmPrinter;
   class MCInst;
 
   FunctionPass *createPPCCTRLoops(PPCTargetMachine &TM);
 #ifndef NDEBUG
   FunctionPass *createPPCCTRLoopsVerify();
 #endif
   FunctionPass *createPPCLoopDataPrefetchPass();
   FunctionPass *createPPCLoopPreIncPrepPass(PPCTargetMachine &TM);
   FunctionPass *createPPCTOCRegDepsPass();
   FunctionPass *createPPCEarlyReturnPass();
   FunctionPass *createPPCVSXCopyPass();
   FunctionPass *createPPCVSXFMAMutatePass();
   FunctionPass *createPPCVSXSwapRemovalPass();
   FunctionPass *createPPCMIPeepholePass();
   FunctionPass *createPPCBranchSelectionPass();
   FunctionPass *createPPCISelDag(PPCTargetMachine &TM);
   FunctionPass *createPPCTLSDynamicCallPass();
   FunctionPass *createPPCBoolRetToIntPass();
+  ModulePass *createPPCEnableShrinkWrapPass();
   void LowerPPCMachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,
                                     AsmPrinter &AP, bool isDarwin);
 
   void initializePPCVSXFMAMutatePass(PassRegistry&);
   void initializePPCBoolRetToIntPass(PassRegistry&);
+  void initializePPCEnableShrinkWrapPass(PassRegistry&);
   extern char &PPCVSXFMAMutateID;
 
   namespace PPCII {
     
   /// Target Operand Flag enum.
   enum TOF {
     //===------------------------------------------------------------------===//
     // PPC Specific MachineOperand flags.

lib/Target/PowerPC/PPCEnableShrinkWrap.cpp

+//===- PPCEnableShrinkWrap.cpp - split functions to create shrink wrapping
+// opportunities ==/
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Shrink wrapping functions can improve performance for functions when the
+// stack is unused. However, all functions where value live-ranges contain
+// function calls are ineligible for shrink wrapping. Why?
+//
+// 1. To avoid saving and restoring values across call-sites, LLVM allocates
+// values with live-ranges that cross call sites to callee-saved registers
+//
+// 2. If callee-saved registers are used, they must be saved (usually in the
+// function prolog)
+//
+// 3. ShrinkWrapping scans from the beginning of the function prolog to the
+// first use of the stack. If a callee-saved register is saved to the stack in
+// the function prolog, ShrinkWrapping will give up early.
+//
+// To increase the applicability of ShrinkWrapping, this pass identifies
+// instances where a live-range straddling a call-site prevents ShrinkWrapping.
+// The pass switches the calling convention to CXX_FAST_TLS, that saves callee
+// registers to virtual registers. This allows the backend to make better
+// choices about where to save registers and in many cases avoids saving
+// registers to the stack. The exit block is privatized for the fast and slow
+// exit paths to allow each to be specialized independently.
+//
+//===----------------------------------------------------------------------===//
+#include "PPC.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+static cl::
+opt<bool> DisablePPCEnableShrink("disable-ppc-enable-shrink-wrap", cl::Hidden,
+                                 cl::desc("Disable PPC enable shrink wrap pass"));
+
+class PPCEnableShrinkWrap : public ModulePass {
+
+  static BasicBlock *getUniqueExitBlock(Function &F) {
+    BasicBlock *ExitBlock = nullptr;
+    for (auto &BB : F) {
+      if (isa<ReturnInst>(BB.getTerminator())) {
+        if (ExitBlock)
+          return nullptr;
+        else
+          ExitBlock = &BB;
+      }
+    }
+    return ExitBlock;
+  }
+
+  static bool branchesTo(TerminatorInst *Term, BasicBlock *Succ) {
+    for (unsigned i = 0; i < Term->getNumSuccessors(); ++i)
+      if (Term->getSuccessor(i) == Succ)
+        return true;
+    return false;
+  }
+
+  static bool canBeComputedWithoutStack(Value *V) {
+    if (isa<Constant>(V))
+      return true;
+    if (isa<Argument>(V))
+      return true;
+    if (isa<PHINode>(V))
+      return true;
+    if (isa<BasicBlock>(V))
+      return true;
+    if (isa<AllocaInst>(V))
+      return false;
+    if (IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
+      return
+        I->getIntrinsicID() == Intrinsic::lifetime_end ||
+        I->getIntrinsicID() == Intrinsic::lifetime_start;
+    if (isa<DbgInfoIntrinsic>(V))
+      return true;
+    if (isa<CallInst>(V))
+      return false;
+    // Some casts and extracts require a stack slot for proc <= P7
+    // Conservatively assume all casts and extracts use the stack, since there
+    // is no easy way to query this information from the Target
+    if (isa<CastInst>(V) || isa<ExtractValueInst>(V))
+      return false;
+
+    Instruction *I = dyn_cast<Instruction>(V);
+    if (!I)
+      return false;
+    if (I->mayHaveSideEffects())
+      return false;
+    if (I->mayReadFromMemory())
+      return false;
+
+    for (unsigned i = 0; i < I->getNumOperands(); ++i)
+      if (!canBeComputedWithoutStack(I->getOperand(i)))
+        return false;
+
+    return true;
+  }
+
+  static bool canBeComputedWithoutStack(BasicBlock *exitBlock,
+                                        BasicBlock &entry) {
+    for (auto &I : *exitBlock) {
+      if (PHINode *Phi = dyn_cast<PHINode>(&I)) {
+        if (!canBeComputedWithoutStack(Phi->getIncomingValueForBlock(&entry)))
+          return false;
+      } else if (!canBeComputedWithoutStack(&I)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  static bool hasCallInst(Function &F) {
+    for (auto &BB : F)
+      for (auto &I : BB)
+        if (isa<CallInst>(I) && !isa<IntrinsicInst>(I))
+          return true;
+    return false;
+  }
+
+  static bool hasVariadicCall(Function &F) {
+    for (auto &BB : F)
+      for (auto &I : BB)
+        if (CallInst *CI = dyn_cast<CallInst>(&I))
+          if (CI->getFunctionType()->isVarArg())
+            return true;
+    return false;
+  }
+
+  static bool mayHaveSideEffects(BasicBlock &BB) {
+    for (auto &I : BB)
+      if (I.mayHaveSideEffects())
+        return true;
+    return false;
+  }
+
+public:
+  static char ID;
+  PPCEnableShrinkWrap() : ModulePass(ID) {
+    initializePPCEnableShrinkWrapPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const {
+    ModulePass::getAnalysisUsage(AU);
+  }
+
+  bool runOnModule(Module &M) {
+    bool Changed = false;
+    if (DisablePPCEnableShrink) return Changed;
+    SmallVector<Function *, 16> Funcs;
+    for (auto &F : M)
+      Funcs.emplace_back(&F);
+    for (auto &F : Funcs)
+      if (!F->isDeclaration())
+        Changed |= runOnFunction(*F);
+    return Changed;
+  }
+
+  static bool runOnFunction(Function &F) {
+    // Presently, only implemented for non-variadic functions that don't call
+    // variadic functions and that contain at least one callsite.
+    if (F.isVarArg())
+      return false;
+    if (!hasCallInst(F))
+      return false;
+    if (hasVariadicCall(F))
+      return false;
+
+    // Only unique exit blocks are handled
+    BasicBlock *ExitBlock = getUniqueExitBlock(F);
+    if (!ExitBlock)
+      return false;
+
+    // Look for the pattern of entry blocks that immediately branch to exit
+    // where the entry block and the exit block can be computed without the
+    // stack.
+    BasicBlock &Entry = F.getEntryBlock();
+    BranchInst *EntryTerm = dyn_cast<BranchInst>(Entry.getTerminator());
+    if (!EntryTerm)
+      return false;
+    if (EntryTerm->isUnconditional())
+      return false;
+    if (isa<Constant>(EntryTerm->getCondition()))
+      return false;
+    if (!branchesTo(EntryTerm, ExitBlock))
+      return false;
+    if (!canBeComputedWithoutStack(EntryTerm))
+      return false;
+    if (!canBeComputedWithoutStack(ExitBlock, Entry))
+      return false;
+    if (mayHaveSideEffects(Entry))
+      return false;
+
+    if (F.getCallingConv() != CallingConv::C)
+      return false;
+
+    F.setCallingConv(CallingConv::CXX_FAST_TLS);
+
+    // Privatize the early exit path
+    ValueToValueMapTy VMap;
+    BasicBlock *PrivExitBlock = CloneBasicBlock(ExitBlock, VMap, ".private", &F);
+    for (auto I = PrivExitBlock->begin(); &*I != PrivExitBlock->getFirstNonPHI(); ++I) {
+      PHINode *Phi = cast<PHINode>(&*I);
+      int EntryIndex = Phi->getBasicBlockIndex(&Entry);
+      for (int Index = Phi->getNumIncomingValues() - 1; Index <= 0; --Index)
+        if (Index != EntryIndex)
+          Phi->removeIncomingValue(Index);
+    }
+
+    for (auto I = PrivExitBlock->begin(); &*I != PrivExitBlock->getFirstNonPHI(); ++I) {
+      PHINode *Phi = cast<PHINode>(&*I);
+      int EntryIndex = Phi->getBasicBlockIndex(&Entry);
+      for (int Index = Phi->getNumIncomingValues() - 1; Index <= 0; --Index)
+        if (Index == EntryIndex)
+          Phi->removeIncomingValue(Index);
+    }
+
+    for (unsigned i = 0; i < EntryTerm->getNumSuccessors(); ++i)
+      if (EntryTerm->getSuccessor(i) == ExitBlock)
+        EntryTerm->setSuccessor(i, PrivExitBlock);
+
+    return true;
+  }
+};
+
+char PPCEnableShrinkWrap::ID = 0;
+INITIALIZE_PASS(PPCEnableShrinkWrap, "create-wrapper-opps",
+                "Find opportunities for wrapping", false, false)
+
+ModulePass *llvm::createPPCEnableShrinkWrapPass() {
+  return new PPCEnableShrinkWrap();
+}

lib/Target/PowerPC/PPCTargetMachine.cpp

 extern "C" void LLVMInitializePowerPCTarget() {
   // Register the targets
   RegisterTargetMachine<PPC32TargetMachine> A(ThePPC32Target);
   RegisterTargetMachine<PPC64TargetMachine> B(ThePPC64Target);
   RegisterTargetMachine<PPC64TargetMachine> C(ThePPC64LETarget);
 
   PassRegistry &PR = *PassRegistry::getPassRegistry();
   initializePPCBoolRetToIntPass(PR);
+  initializePPCEnableShrinkWrapPass(PR);
 }
 
 /// Return the datalayout string of a subtarget.
 static std::string getDataLayoutString(const Triple &T) {
   bool is64Bit = T.getArch() == Triple::ppc64 || T.getArch() == Triple::ppc64le;
   std::string Ret;
 
   // Most PPC* platforms are big endian, PPC64LE is little endian.

 
 TargetPassConfig *PPCTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new PPCPassConfig(this, PM);
 }
 
 void PPCPassConfig::addIRPasses() {
   if (TM->getOptLevel() != CodeGenOpt::None)
     addPass(createPPCBoolRetToIntPass());
+  if (TM->getOptLevel() > CodeGenOpt::Default)
+    addPass(createPPCEnableShrinkWrapPass());
   addPass(createAtomicExpandPass(&getPPCTargetMachine()));
 
   // For the BG/Q (or if explicitly requested), add explicit data prefetch
   // intrinsics.
   bool UsePrefetching = TM->getTargetTriple().getVendor() == Triple::BGQ &&
                         getOptLevel() != CodeGenOpt::None;
   if (EnablePrefetch.getNumOccurrences() > 0)
     UsePrefetching = EnablePrefetch;

test/CodeGen/PowerPC/EnableShrinkWrapTest.ll

+; RUN: opt -create-wrapper-opps -S -o - < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-unknown-linux-gnu"
+
+; CHECK-LABEL: cxx_fast_tlscc signext i32 @testEnableShrinkWrap
+define signext i32 @testEnableShrinkWrap(i32 signext %i) {
+entry:
+  %tobool = icmp eq i32 %i, 0
+; CHECK: br i1 %tobool, label %if.end.private, label %if.then
+  br i1 %tobool, label %if.end, label %if.then
+
+; CHECK-LABEL: if.then:
+if.then:                                          ; preds = %entry
+  tail call void @doSomething()
+; CHECK: br label %if.end
+  br label %if.end
+; CHECK-LABEL: if.end.private:
+if.end:                                           ; preds = %entry, %if.then
+  ret i32 %i
+}
+
+; CHECK-LABEL: doSomething
+declare void @doSomething()
+
+; CHECK-LABEL: define signext i32 @testEnableShrinkWrapVariadic
+define signext i32 @testEnableShrinkWrapVariadic(i32 signext %i, ...) {
+entry:
+  %tobool = icmp eq i32 %i, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  tail call void @doSomething()
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret i32 %i
+}
+
+; CHECK-LABEL: define signext i32 @callVariadic
+define signext i32 @callVariadic(i32 signext %i) {
+entry:
+  %tobool = icmp eq i32 %i, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  tail call void (i32, ...) @doSomethingVariadic(i32 signext %i, i32 signext 7)
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret i32 %i
+}
+
+; CHECK-LABEL: declare void @doSomethingVariadic
+declare void @doSomethingVariadic(i32 signext, ...)
+
+; CHECK-LABEL: define signext i32 @tooComplicatedControlFlow
+define signext i32 @tooComplicatedControlFlow(i32 zeroext %i, i32 zeroext %j) {
+entry:
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry
+  %i.addr.0 = phi i32 [ %i, %entry ], [ %dec, %do.body ]
+; CHECK: call void @doSomething
+  tail call void @doSomething()
+  %dec = add i32 %i.addr.0, -1
+  %tobool = icmp eq i32 %dec, 0
+  br i1 %tobool, label %do.body.1.preheader, label %do.body
+
+do.body.1.preheader:                              ; preds = %do.body
+  br label %do.body.1
+
+do.body.1:                                        ; preds = %do.body.1.preheader, %do.body.1
+  %j.addr.0 = phi i32 [ %dec3, %do.body.1 ], [ %j, %do.body.1.preheader ]
+; CHECK: call void @doSomething
+  tail call void @doSomething()
+  %dec3 = add i32 %j.addr.0, -1
+  %tobool4 = icmp eq i32 %dec3, 0
+  br i1 %tobool4, label %do.end.5, label %do.body.1
+
+do.end.5:                                         ; preds = %do.body.1
+  ret i32 7
+}
+
+; CHECK-LABEL: define signext i32 @notSideEffectFree
+define signext i32 @notSideEffectFree(i32* nocapture readonly %i) {
+entry:
+  %incdec.ptr = getelementptr inbounds i32, i32* %i, i64 1
+  %0 = load i32, i32* %i, align 4
+  %tobool = icmp eq i32 %0, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  tail call void @doSomething()
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %1 = load i32, i32* %incdec.ptr, align 4
+  ret i32 %1
+}
 No newline at end of file