New pre-isel pass SystemZBRCTLoops

[jonpa]

Summary

I experimented with making a new pass for the improved generation of BRCT loops for SystemZ. This is based on PPCCTRLoops.cpp.

Results:
Number of brct's on SPEC:
w/out patch: 4752
w/out patch, unrolled: 1367
w/ patch: 8743
w/ patch, unrolled: 11518 (new prologue loops increase the number)

gcc with unrolling generates 20864 brct's, so this result is an improvement, although not necessarily near optimal.

This seemed necessary in order to activate the loop-unroller and tune it properly, otherwise a loop might get unrolled but the BRCT and some performance will be lost.

[uweigand]

Can you explain why we need this new intrinsic (int_s390_hwloop_count)? I can understand why the PowerPC code needs intrinsics, since it has to access the special CTR register. But on SystemZ we don't have any special registers for BRCT, so why the intrinsic?

[jonpa]

Since there seems to be some general interest for a target independent hw-loop pass, I started out thinking that the hw-loop counter might be a simple beginning for it. So I actually first made just a 'hw-loop-count' intrinsic in the main file, but then moved it into a '-s390-' since this is still only a SystemZ pass.

I think this pass could basically be target-independent right now, so the question is if anyone would want this right now? Should I make a systemz pre-isel pass out of this or a new target-independent hw-loop pass with just the hw-loop-count intrinsic implemented?

Regardless, I don't think SystemZ needs the intrinsic, like you pointed out. For just a SystemZ pre-isel pass, it could just be removed. With a target-independent pass, just the isel patterns for it would remain.

[hfinkel]

In D18900#396671, @jonpa wrote:

Since there seems to be some general interest for a target independent hw-loop pass, I started out thinking that the hw-loop counter might be a simple beginning for it. So I actually first made just a 'hw-loop-count' intrinsic in the main file, but then moved it into a '-s390-' since this is still only a SystemZ pass.

I think this pass could basically be target-independent right now, so the question is if anyone would want this right now? Should I make a systemz pre-isel pass out of this or a new target-independent hw-loop pass with just the hw-loop-count intrinsic implemented?

Regardless, I don't think SystemZ needs the intrinsic, like you pointed out. For just a SystemZ pre-isel pass, it could just be removed. With a target-independent pass, just the isel patterns for it would remain.

I think this could make sense as a target-independent pass? Did you just copy the PPCCTRLoops pass, change the name, change the name of the intrinsics generated, and remove the PPC-specific CTR-register use legality checking? I could certainly see abstracting those bits into callbacks (or just adding some target-independent intrinsics if we can both use the same ones, and adding a callback for additional legality checking to TLI). That seems a much better option than copy-and-paste here.

[jonpa]

Yes, I started my experiment by copying and modifying until I had a simplest version that seemed to work.
I also think it should definitely be possible to make a target independent version like you proposed.

For SystemZ, this is currently giving mixed results, and I think it will have to wait until the pre-ra scheduler is in place. Thanks for review so far.

[jonpa]

After improving on LSR and loop unrolling, this pass has been found beneficial on benchmarks on SystemZ

As a first step, it has therefore been rewritten for the purposes of the SystemZ target, which means an intrinsic is not used for the trip count.

It also now handles loop counters of i8 and i16, by zero extending the trip count in the pre-header.

Once this has come to use, the opportunity is still there for a target independent pre-isel pass.

lib/Target/SystemZ/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS SystemZ.td)
 
 tablegen(LLVM SystemZGenAsmMatcher.inc -gen-asm-matcher)
 tablegen(LLVM SystemZGenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM SystemZGenCallingConv.inc -gen-callingconv)
 tablegen(LLVM SystemZGenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM SystemZGenDisassemblerTables.inc -gen-disassembler)
 tablegen(LLVM SystemZGenMCCodeEmitter.inc -gen-emitter)
 tablegen(LLVM SystemZGenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM SystemZGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM SystemZGenSubtargetInfo.inc -gen-subtarget)
 add_public_tablegen_target(SystemZCommonTableGen)
 
 add_llvm_target(SystemZCodeGen
+  SystemZBRCTLoops.cpp
   SystemZAsmPrinter.cpp
   SystemZCallingConv.cpp
   SystemZConstantPoolValue.cpp
   SystemZElimCompare.cpp
   SystemZExpandPseudo.cpp
   SystemZFrameLowering.cpp
   SystemZHazardRecognizer.cpp
   SystemZISelDAGToDAG.cpp

lib/Target/SystemZ/SystemZ.h

 }
 
 // Return true if Val fits an LLIHF operand.
 static inline bool isImmHF(uint64_t Val) {
   return (Val & ~0xffffffff00000000ULL) == 0;
 }
 } // end namespace SystemZ
 
+
+FunctionPass *createSystemZBRCTLoops(SystemZTargetMachine &TM);
 FunctionPass *createSystemZISelDag(SystemZTargetMachine &TM,
                                    CodeGenOpt::Level OptLevel);
 FunctionPass *createSystemZElimComparePass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZExpandPseudoPass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZShortenInstPass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZLongBranchPass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZLDCleanupPass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZTDCPass();
 } // end namespace llvm
 
 #endif

lib/Target/SystemZ/SystemZBRCTLoops.cpp

+//===-- SystemZBRCTLoops.cpp - Identify and generate BRCT loops ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass identifies loops where we can generate the branch-on-count type
+// branch instructions. It then rewrites the IV to make it possible for the
+// backend to generate a BRCT. It does so by putting the trip count in the
+// preheader, and a subtraction of 1 and compare against zero in the latch
+// block. It is better to do this before instruction selection, while the
+// ScalarEvolution is available and can assist the handling of the trip
+// count.
+//
+// Criteria for BRCT loops:
+//  - Any general register may be used for the induction variable.
+//  - BRCT instruction subtracts one and then compares to 0.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar.h"
+#include "SystemZ.h"
+#include "SystemZTargetMachine.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/InlineAsm.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/PassSupport.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/LoopUtils.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "brctloops"
+
+STATISTIC(NumBRCTLoops, "Number of loops converted to BRCT loops");
+
+namespace llvm {
+  void initializeSystemZBRCTLoopsPass(PassRegistry&);
+}
+
+namespace {
+  struct SystemZBRCTLoops : public FunctionPass {
+
+  public:
+    static char ID;
+
+    SystemZBRCTLoops() : FunctionPass(ID), TM(nullptr) {
+      initializeSystemZBRCTLoopsPass(*PassRegistry::getPassRegistry());
+    }
+    SystemZBRCTLoops(SystemZTargetMachine &TM) : FunctionPass(ID), TM(&TM) {
+      initializeSystemZBRCTLoopsPass(*PassRegistry::getPassRegistry());
+    }
+
+    bool runOnFunction(Function &F) override;
+
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addRequired<LoopInfoWrapperPass>();
+      AU.addPreserved<LoopInfoWrapperPass>();
+      AU.addRequired<DominatorTreeWrapperPass>();
+      AU.addPreserved<DominatorTreeWrapperPass>();
+      AU.addRequired<ScalarEvolutionWrapperPass>();
+    }
+
+  private:
+    bool convertToBRCTLoop(Loop *L);
+
+  private:
+    LLVMContext *Ctx;
+    SystemZTargetMachine *TM;
+    LoopInfo *LI;
+    ScalarEvolution *SE;
+    const DataLayout *DL;
+    DominatorTree *DT;
+    const TargetLibraryInfo *LibInfo;
+    bool PreserveLCSSA;
+
+  };
+
+  char SystemZBRCTLoops::ID = 0;
+} // end anonymous namespace
+
+INITIALIZE_PASS_BEGIN(SystemZBRCTLoops, "systemz-brct-loops", "SystemZ BRCT Loops",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_END(SystemZBRCTLoops, "systemz-brct-loops", "SystemZ BRCT Loops",
+                    false, false)
+
+FunctionPass *llvm::createSystemZBRCTLoops(SystemZTargetMachine &TM) {
+  return new SystemZBRCTLoops(TM);
+}
+
+bool SystemZBRCTLoops::runOnFunction(Function &F) {
+  Ctx = &F.getContext();
+  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  DL = &F.getParent()->getDataLayout();
+  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
+  LibInfo = TLIP ? &TLIP->getTLI() : nullptr;
+  PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
+
+  bool MadeChange = false;
+
+  for (LoopInfo::iterator I = LI->begin(), E = LI->end();
+       I != E; ++I) {
+    Loop *L = *I;
+    if (!L->getParentLoop())
+      MadeChange |= convertToBRCTLoop(L);
+  }
+
+  return MadeChange;
+}
+
+// The loop has a known invariant trip count, so it is possible to transform
+// it. We however only handle the simple case where the loop has an IV which
+// is used only for branching (no other uses):
+//   PHI            <--\
+//   |--> increment  --|
+//        |--> compare
+//             |--> conditional branch
+static bool IVReplacable(BranchInst *Branch) {
+  
+  // Branch is the conditional branch back to the header block from the latch.
+  // Compare instruction should have one user.
+  ICmpInst *Cmp = dyn_cast<ICmpInst>(Branch->getCondition());
+  if (Cmp == nullptr || !Cmp->hasOneUse())
+    return false;
+
+  // Look for incrementing instruction (e.g. add) with two users
+  // (compare and PHI).
+  Instruction *Increment = dyn_cast<Instruction>(Cmp->getOperand(0));
+  if (Increment == nullptr || !Increment->hasNUses(2))
+    return false;
+
+  // The Increment instruction should have one PHI node as part of its
+  // operands, and that PHI node must not have any other users.
+  bool SimplePhiUse = false;
+  for (Use &U : Increment->operands()) {
+    if (PHINode *PHI = dyn_cast<PHINode>(U)) {
+      if (!PHI->hasOneUse() || SimplePhiUse)
+        return false;
+      SimplePhiUse = true;
+    }
+  }
+  if (!SimplePhiUse)
+    return false;
+
+  return true;
+}
+
+bool SystemZBRCTLoops::convertToBRCTLoop(Loop *L) {
+  bool MadeChange = false;
+
+  // Process nested loops first.
+  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
+    MadeChange |= convertToBRCTLoop(*I);
+
+  // Every iteration must branch back to header from a single latch block.
+  BasicBlock *Latch = L->getLoopLatch();
+  if (Latch == nullptr)
+    return MadeChange;
+  
+  // Look for a SCEV that suits BRCT.
+  const SCEV *ExitCount = SE->getExitCount(L, Latch);
+  DEBUG(dbgs() << "Exit Count for " << *L << " from block " <<
+        Latch->getName() << ": " << *ExitCount << "\n");
+  if (isa<SCEVCouldNotCompute>(ExitCount))
+    return MadeChange;
+  if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(ExitCount)) {
+    if (ConstEC->getValue()->isZero())
+      return MadeChange;
+  }
+  else if (!SE->isLoopInvariant(ExitCount, L))
+    return MadeChange;
+  if (SE->getTypeSizeInBits(ExitCount->getType()) > 64)
+    return MadeChange;
+
+  // Make sure this blocks ends with a conditional branch.
+  BranchInst *CountedExitBranch = nullptr;
+  Instruction *TI = (Latch)->getTerminator();
+  if (!TI)
+    return MadeChange;
+  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+    if (!BI->isConditional())
+      return MadeChange;
+    CountedExitBranch = BI;
+  } else
+    return MadeChange;
+
+  // If there are other uses of the original IV, leave it alone.
+  if (!IVReplacable(CountedExitBranch))
+    return MadeChange;
+
+  BasicBlock *Preheader = L->getLoopPreheader();
+
+  // If we don't have a preheader, then insert one.
+  if (!Preheader)
+    Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
+  if (!Preheader)
+    return MadeChange;
+  DEBUG(dbgs() << "Preheader for exit count: " << Preheader->getName() << "\n");
+
+  MadeChange = true;
+
+  // Use SCEVExpander to get a Value for the trip count.
+  SCEVExpander SCEVE(*SE, Preheader->getModule()->getDataLayout(), "loopcnt");
+  Type *CountType = ExitCount->getType();
+  ExitCount = SE->getAddExpr(ExitCount, SE->getOne(CountType));
+  Value *TripCount =
+      SCEVE.expandCodeFor(ExitCount, CountType, Preheader->getTerminator());
+
+  // Zero extend the trip count if its an i8 or i16 since there are only
+  // BRCT instructions for i32 and i64 available.
+  if (SE->getTypeSizeInBits(TripCount->getType()) < 32) {
+    IRBuilder<> ZExtBuilder(Preheader->getTerminator());
+    CountType = Type::getInt32Ty(*Ctx);
+    TripCount = ZExtBuilder.CreateZExt(TripCount, CountType);
+  }
+
+  // Insert PHI in header
+  IRBuilder<> PhiBuilder(&*L->getHeader()->begin());
+  PHINode *HWPhi = PhiBuilder.CreatePHI(CountType, 4, "hwloopphi");
+
+  // Insert decrement and compare instructions in latch.
+  IRBuilder<> CondBuilder(CountedExitBranch);
+  Value *PostInc = CondBuilder.CreateSub(HWPhi,
+                                         ConstantInt::get(CountType, 1),
+                                         "hwloopdec");
+  Value *NewCond = CondBuilder.CreateICmpUGT(PostInc,
+                                             ConstantInt::get(CountType, 0),
+                                             "hwloopcmp");
+
+  // Insert PHI operands
+  HWPhi->addIncoming(TripCount, Preheader);
+  HWPhi->addIncoming(PostInc, Latch);
+
+  // Update branch
+  Value *OldCond = CountedExitBranch->getCondition();
+  CountedExitBranch->setCondition(NewCond);
+  if (!L->contains(CountedExitBranch->getSuccessor(0)))
+    // The false branch must exit the loop.
+    CountedExitBranch->swapSuccessors();
+
+  // The old condition may be dead now, and may have even created a dead PHI
+  // (the original induction variable).
+  RecursivelyDeleteTriviallyDeadInstructions(OldCond);
+  DeleteDeadPHIs(L->getHeader());
+
+  ++NumBRCTLoops;
+  return MadeChange;
+}

lib/Target/SystemZ/SystemZTargetMachine.cpp

 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/CodeGen/TargetLoweringObjectFileImpl.h"
 
 using namespace llvm;
 
+// Experimental option
+static cl::
+opt<bool> DisableBRCTLoops("disable-systemz-brctloops", cl::Hidden,
+            cl::desc("Disable extra optimization for BRCT loops for SystemZ."));
+
 extern "C" void LLVMInitializeSystemZTarget() {
   // Register the target.
   RegisterTargetMachine<SystemZTargetMachine> X(getTheSystemZTarget());
 }
 
 // Determine whether we use the vector ABI.
 static bool UsesVectorABI(StringRef CPU, StringRef FS) {
   // We use the vector ABI whenever the vector facility is avaiable.
public:
 
   ScheduleDAGInstrs *
   createPostMachineScheduler(MachineSchedContext *C) const override {
     return new ScheduleDAGMI(C, make_unique<SystemZPostRASchedStrategy>(C),
                              /*RemoveKillFlags=*/true);
   }
 
   void addIRPasses() override;
+  bool addPreISel() override;
   bool addInstSelector() override;
   bool addILPOpts() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
 };
 } // end anonymous namespace
 
 void SystemZPassConfig::addIRPasses() {
   if (getOptLevel() != CodeGenOpt::None)
     addPass(createSystemZTDCPass());
 
   TargetPassConfig::addIRPasses();
 }
 
+bool SystemZPassConfig::addPreISel() {
+  if (!DisableBRCTLoops && getOptLevel() != CodeGenOpt::None)
+    addPass(createSystemZBRCTLoops(getSystemZTargetMachine()));
+
+  return false;
+}
+
 bool SystemZPassConfig::addInstSelector() {
   addPass(createSystemZISelDag(getSystemZTargetMachine(), getOptLevel()));
 
  if (getOptLevel() != CodeGenOpt::None)
     addPass(createSystemZLDCleanupPass(getSystemZTargetMachine()));
 
   return false;
 }

test/CodeGen/SystemZ/loop-brct.ll

+; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s
+
+; Function Attrs: nounwind
+
+define zeroext i32 @f1(i32 zeroext %c, i32 zeroext %iter) {
+; CHECK-LABEL: f1:
+; CHECK: lgr %r13, %r3
+; CHECK: brct %r13, .LBB0_2
+
+entry:
+  %cmp6 = icmp eq i32 %iter, 0
+  br i1 %cmp6, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  %S.0.lcssa = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  ret i32 %S.0.lcssa
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.08 = phi i32 [ %add1, %for.body ], [ 0, %entry ]
+  %S.07 = phi i32 [ %add, %for.body ], [ 0, %entry ]
+  %call = tail call signext i32 bitcast (i32 (...)* @fun to i32 ()*)()
+  %add = add i32 %call, %S.07
+  %add1 = add nuw i32 %i.08, 1
+  %exitcond = icmp eq i32 %add1, %iter
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+declare signext i32 @fun(...)
+
+; Function Attrs: nounwind
+define zeroext i32 @f2(i32 zeroext %c, i64 %iter) {
+; CHECK-LABEL: f2:
+; CHECK: ltgr %r13, %r3
+; CHECK: brctg %r13, .LBB1_2
+
+entry:
+  %cmp6 = icmp eq i64 %iter, 0
+  br i1 %cmp6, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  %S.0.lcssa = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  ret i32 %S.0.lcssa
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.08 = phi i64 [ %add1, %for.body ], [ 0, %entry ]
+  %S.07 = phi i32 [ %add, %for.body ], [ 0, %entry ]
+  %call = tail call signext i32 bitcast (i32 (...)* @fun to i32 ()*)()
+  %add = add i32 %call, %S.07
+  %add1 = add nuw i64 %i.08, 1
+  %exitcond = icmp eq i64 %add1, %iter
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; Function Attrs: nounwind
+define zeroext i32 @f3(i32 zeroext %c) {
+; CHECK-LABEL: f3:
+; CHECK: lhi %r12, 16
+; CHECK: brct %r12, .LBB2_1
+
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret i32 %add
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.07 = phi i32 [ 0, %entry ], [ %add1, %for.body ]
+  %S.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %call = tail call signext i32 bitcast (i32 (...)* @fun to i32 ()*)()
+  %add = add i32 %call, %S.06
+  %add1 = add nuw nsw i32 %i.07, 16
+  %cmp = icmp ult i32 %add1, 256
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Function Attrs: nounwind
+define zeroext i32 @f4(i32 zeroext %c) {
+; CHECK-LABEL: f4:
+; CHECK: lgfi %r12, 500000000
+; CHECK: brctg %r12, .LBB3_1
+
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret i32 %add
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.07 = phi i64 [ 0, %entry ], [ %add1, %for.body ]
+  %S.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %call = tail call signext i32 bitcast (i32 (...)* @fun to i32 ()*)()
+  %add = add i32 %call, %S.06
+  %add1 = add nuw nsw i64 %i.07, 10
+  %cmp = icmp ult i64 %add1, 5000000000
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}