[PowerPC Peephole] Constants into a join add, use ADDI over LI/ADD.

[jtony]

Summary

Two blocks prior to the join each perform an li and the the join block has an add using the initialized register. Optimize each predecessor block to instead use addi and delete the li's and add.

[nemanjai]

Lambda functions are useful constructs in some cases, but if a patch consists of 3 lambda functions and 5 lines of code to just call them, it's an indication of an overuse of this construct. I would say that as general guidance, use a lambda when it:

1. Saves code repetition
2. Capturing values from the enclosing function is necessary
3. Functionality isn't needed outside of the function

or if you need to pass a functor to something and will likely just define it inline.

For this patch, neither of these 3 lambdas fulfill these requirements.
getVRegDefMI() is useful elsewhere and doesn't capture anything
replaceLiWithAddi() is a big lambda that doesn't save code repetition and I didn't notice it capturing anything (although I may have missed something in that big function)
replaceAddWithCopy() is useful elsewhere, doesn't save code repetition and only captures things which it shouldn't be concerned about

lib/Target/PowerPC/PPCMIPeephole.cpp

72

You don't modify MDT, right? Why not addPreserved() as well?

79

Why initialize this if you're going to early exit? Seems more logical to put this in initialize().

368

It isn't clear to me why the default capture? Are you actually capturing something and I just missed it?
In any case, I think this function would be useful elsewhere in this file. Can it be a static function in this pass and called something like getVregDefOrNull()?

375

I don't think it's meaningful to cast nullptr.

380

Why implement this as a large lambda function that is (in effect) called only once (i.e. the two calls are symmetrical)? Would it not be much clearer and more readable to decide on the direction of the replacement early (i.e. is Op1 or Op2 checked for being a dominator, etc.) and then just transform instructions if possible?

382

I don't think it's very useful to put both of these in a single assert. If you want to add an assert for both, I think they should be separate so it is clear which is null.

421

Everything after In such case, ... is kind of meaningless. We're in SSA here, there's no "first one" - the vreg is defined only once.
Please change that sentence to something like:
So if we've already replaced the def instruction, skip.

435

The comment is confusing. LiMI is a variable name you used, AddiMI is not. Please remove the comment - there's no reason to explain what you're doing here, it is clear that you're just dumping the new instruction.

441

Again, this function has wider utility than this. It should probably be a static function available everywhere in this pass. And it should take an instruction that it is to replace with a copy.

test/CodeGen/PowerPC/opt-li-add-to-addi.ll

5

This test case is inadequate. Your code does more than just this:

1. Add a case where the same vreg can come from multiple blocks as outlined in your code
2. Add a case where the PHI has more than two incoming vregs (i.e. more LI instructions that will be replaced)

[jtony]

Address the comments from Nemanja.

lib/Target/PowerPC/PPCMIPeephole.cpp

368

Changed to a static function call for this lambda function.

375

Without that cast, the compiler couldn't figure out the return type for the function, but after changing to a static function, this won't be needed anymore.

380

I thought this is more clear actually, we are trying both the two cases in the calling part of this function replaceLiWithAddi. It is either Op1 is the DominatorOp and Op2 is the PhiOp or it is the other way: Op2 is the DominatorOp and Op1 is the PhiOp, we don't have to handle the logic which is which ( by either set a flag or swap the two operands). But I may be wrong, if that is a quite easy way to decide on the direction of the replacement early and then just call the function replaceLiWithAddi once, then I can implement it and get rid of the lambda replaceLiWithAddi here.

441

I would leave this one as a lambda function to save several parameter passing if there is no strong objection (otherwise you have to pass ToErase / Simplified / MBB / MI. And Simplified is bool parameter, which the community also doesn't like)

test/CodeGen/PowerPC/opt-li-add-to-addi.ll

5

I added one test for case 2. but for case 1, it is not trivial to create one test case , the reduced test case for it is too large, we don't want to commit that in.

[nemanjai]

lib/Target/PowerPC/PPCMIPeephole.cpp

441

You've clearly not read my comment about this function. The arguments you're making for keeping this a lambda are that the things you currently capture would have to become parameters. As I've stated - this function is capturing things it shouldn't be concerned with.
ToErase and Simplified have nothing to do with what this function should do. This function should simply take a MachineInstr and replace it with a PPC::COPY. We do that all over the place in this pass. It would be good to have it in a function.
Then it is the caller that should be responsible for setting those.

If all the places where we replace an instruction with a PPC::COPY are in the same function, this can remain a lambda and I suppose it can capture these things, but it should be defined outside the switch and be available to the entire function.

[jtony]

Refactor the implementation according to Nemanja's suggestion (get rid of the large lambda function replaceLiWithAddi, and inline replaceAddWithCopy)

[inouehrs]

lib/Target/PowerPC/PPCMIPeephole.cpp

96

It's better to make this local helper method static.

366

Why specific to add?
Don't we have much optimization opportunity for arithmetic operations other than add?

375

return DefPhiMI && (DefPhiMI->getOpcode() != PPC::PHI &&
       MRI->hasOneNonDBGUse(DefPhiMI->getOperand(0).getReg());

might be clearer (but its up to your preference.)

407

We don't have and ADD fed -> redundant "and"?

409

Now we now -> do you mean "Now we know"?

[jtony]

lib/Target/PowerPC/PPCMIPeephole.cpp

366

Discussed in our scrum, we don't want to do this for now.

375

That's indeed a good idea, I will change it. But the code you provided has a small error in it. It should be DefPhiMI->getOpcode() == PPC::PHI, i.e.

return DefPhiMI && (DefPhiMI->getOpcode() == PPC::PHI &&

MRI->hasOneNonDBGUse(DefPhiMI->getOperand(0).getReg());

[jtony]

Address comments from Hiroshi and rebase on trunk.

[nemanjai]

LGTM. Just a request for a comment to be added to the code.

lib/Target/PowerPC/PPCMIPeephole.cpp

366

It is fine to leave it as is for the time being. But please add a comment such as this:

// FIXME: Any instruction that has an immediate form fed only by
// a PHI whose operands are all load immediate can be folded away.
// We currently do this for ADD instructions, but should expand it to
// arithmetic and binary instructions with immediate forms in the future.

lib/Target/PowerPC/PPCMIPeephole.cpp

 // swap removal.
 //
 //===---------------------------------------------------------------------===//
 
 #include "PPC.h"
 #include "PPCInstrBuilder.h"
 #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"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "ppc-mi-peepholes"
 
+STATISTIC(NumOptADDLIs, "Number of optimized ADD instruction fed by LI");
+
 namespace llvm {
   void initializePPCMIPeepholePass(PassRegistry&);
 }
 
 namespace {
 
 struct PPCMIPeephole : public MachineFunctionPass {
 
   static char ID;
   const PPCInstrInfo *TII;
   MachineFunction *MF;
   MachineRegisterInfo *MRI;
 
   PPCMIPeephole() : MachineFunctionPass(ID) {
     initializePPCMIPeepholePass(*PassRegistry::getPassRegistry());
   }
 
 private:
+  MachineDominatorTree *MDT;
+
   // Initialize class variables.
   void initialize(MachineFunction &MFParm);
 
   // Perform peepholes.
   bool simplifyCode(void);
 
   // 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>();
+    AU.addPreserved<MachineDominatorTree>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
   // Main entry point for this pass.
   bool runOnMachineFunction(MachineFunction &MF) override {
     if (skipFunction(*MF.getFunction()))
       return false;
     initialize(MF);
     return simplifyCode();
   }
 };
 
 // Initialize class variables.
 void PPCMIPeephole::initialize(MachineFunction &MFParm) {
   MF = &MFParm;
   MRI = &MF->getRegInfo();
+  MDT = &getAnalysis<MachineDominatorTree>();
   TII = MF->getSubtarget<PPCSubtarget>().getInstrInfo();
   DEBUG(dbgs() << "*** PowerPC MI peephole pass ***\n\n");
   DEBUG(MF->dump());
 }
 
+MachineInstr *getVRegDefOrNull(MachineOperand *Op, MachineRegisterInfo *MRI) {
+  assert(Op && "Invalid Operand!");
+  if (!Op->isReg())
+    return nullptr;
+
+  unsigned Reg = Op->getReg();
+  if (!TargetRegisterInfo::isVirtualRegister(Reg))
+    return nullptr;
+
+  return MRI->getVRegDef(Reg);
+}
+
 // Perform peephole optimizations.
 bool PPCMIPeephole::simplifyCode(void) {
   bool Simplified = false;
   MachineInstr* ToErase = nullptr;
 
   for (MachineBasicBlock &MBB : *MF) {
     for (MachineInstr &MI : MBB) {
 
for (MachineInstr &MI : MBB) {
             removeFRSPIfPossible(P1);
             removeFRSPIfPossible(P2);
             break;
           }
           removeFRSPIfPossible(P1);
         }
         break;
       }
+
+      case PPC::ADD4:
+      case PPC::ADD8: {
+        auto isSingleUsePHI = [&](MachineOperand *PhiOp) {
+          assert(PhiOp && "Invalid Operand!");
+          MachineInstr *DefPhiMI = getVRegDefOrNull(PhiOp, MRI);
+
+          if (!DefPhiMI || (DefPhiMI->getOpcode() != PPC::PHI))
+            return false;
+
+          if (!MRI->hasOneNonDBGUse(DefPhiMI->getOperand(0).getReg()))
+            return false;
+
+          return true;
+        };
+
+        auto dominatesAllSingleUseLIs = [&](MachineOperand *DominatorOp,
+                                            MachineOperand *PhiOp) {
+          assert(PhiOp && "Invalid Operand!");
+          assert(DominatorOp && "Invalid Operand!");
+          MachineInstr *DefPhiMI = getVRegDefOrNull(PhiOp, MRI);
+          MachineInstr *DefDomMI = getVRegDefOrNull(DominatorOp, MRI);
+
+          // Note: the vregs only show up at odd indices position of PHI Node,
+          // the even indices position save the BB info.
+          for (unsigned i = 1; i < DefPhiMI->getNumOperands(); i += 2) {
+            MachineInstr *LiMI =
+                getVRegDefOrNull(&DefPhiMI->getOperand(i), MRI);
+            if (!LiMI || !MRI->hasOneNonDBGUse(LiMI->getOperand(0).getReg()) ||
+                !MDT->dominates(DefDomMI, LiMI) ||
+                (LiMI->getOpcode() != PPC::LI && LiMI->getOpcode() != PPC::LI8))
+              return false;
           }
+
+          return true;
+        };
+
+        MachineOperand Op1 = MI.getOperand(1);
+        MachineOperand Op2 = MI.getOperand(2);
+        if (isSingleUsePHI(&Op2) && dominatesAllSingleUseLIs(&Op1, &Op2))
+          std::swap(Op1, Op2);
+        else if (!isSingleUsePHI(&Op1) || !dominatesAllSingleUseLIs(&Op2, &Op1))
+          break; // We don't have and ADD fed by LI's that can be transformed
+
+        // Now we now that Op1 is the PHI node and Op2 is the dominator
+        unsigned DominatorReg = Op2.getReg();
+
+        const TargetRegisterClass *TRC =
+            MI.getOpcode() == PPC::ADD8 ? &PPC::G8RC_and_G8RC_NOX0RegClass
+                                        : &PPC::GPRC_and_GPRC_NOR0RegClass;
+        MRI->setRegClass(DominatorReg, TRC);
+
+        // replace LIs with ADDIs
+        MachineInstr *DefPhiMI = getVRegDefOrNull(&Op1, MRI);
+        for (unsigned i = 1; i < DefPhiMI->getNumOperands(); i += 2) {
+          MachineInstr *LiMI = getVRegDefOrNull(&DefPhiMI->getOperand(i), MRI);
+          DEBUG(dbgs() << "Optimizing LI to ADDI: ");
+          DEBUG(LiMI->dump());
+
+          // There could be repeated registers in the PHI, e.g: %vreg1<def> =
+          // PHI %vreg6, <BB#2>, %vreg8, <BB#3>, %vreg8, <BB#6>; So if we've
+          // already replaced the def instruction, skip.
+          if (LiMI->getOpcode() == PPC::ADDI ||
+              LiMI->getOpcode() == PPC::ADDI8)
+            continue;
+
+          assert((LiMI->getOpcode() == PPC::LI ||
+                  LiMI->getOpcode() == PPC::LI8) &&
+                 "Invalid Opcode!");
+          auto LiImm = LiMI->getOperand(1).getImm(); // save the imm of LI
+          LiMI->RemoveOperand(1);                    // remove the imm of LI
+          LiMI->setDesc(TII->get(LiMI->getOpcode() == PPC::LI ? PPC::ADDI
+                                                              : PPC::ADDI8));
+          MachineInstrBuilder(*LiMI->getParent()->getParent(), *LiMI)
+              .addReg(DominatorReg)
+              .addImm(LiImm); // restore the imm of LI
+          DEBUG(LiMI->dump());
         }
+
+        // replace ADD with COPY
+        DEBUG(dbgs() << "Optimizing ADD to COPY: ");
+        DEBUG(MI.dump());
+        BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::COPY),
+                MI.getOperand(0).getReg())
+            .add(Op1);
+        ToErase = &MI;
+        Simplified = true;
+        NumOptADDLIs++;
+        break;
+      }
+      }
+    }
+
     // If the last instruction was marked for elimination,
     // remove it now.
     if (ToErase) {
       ToErase->eraseFromParent();
       ToErase = nullptr;
     }
   }
 

test/CodeGen/PowerPC/opt-li-add-to-addi.ll

+; RUN: llc -verify-machineinstrs -mtriple=powerpc64-unknown-linux-gnu -mcpu=pwr8 < %s | FileCheck %s
+; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr8 < %s | FileCheck %s
+
+define i64 @testOptimizeLiAddToAddi(i64 %a) {
+; CHECK-LABEL: testOptimizeLiAddToAddi:
+; CHECK:    addi 3, 30, 2444
+; CHECK:    bl callv
+; CHECK:    addi 3, 30, 234
+; CHECK:    bl call
+; CHECK:    blr
+entry:
+  %cmp = icmp sgt i64 %a, 33
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void bitcast (void (...)* @callv to void ()*)()
+  br label %if.end
+
+if.end:
+  %add.0 = phi i64 [ 234, %if.then ], [ 2444, %entry ]
+  %add2 = add nsw i64 %add.0, %a
+  %call = tail call i64 @call(i64 %add2)
+  ret i64 %call
+}
+
+define i64 @testThreePhiIncomings(i64 %a) {
+; CHECK-LABEL: testThreePhiIncomings:
+; CHECK:    bl callv
+; CHECK:    addi 3, 30, 234
+; CHECK:    addi 3, 30, 2444
+; CHECK:    bl callv
+; CHECK:    addi 3, 30, 345
+; CHECK:    bl call
+; CHECK:    blr
+entry:
+  %cmp = icmp slt i64 %a, 33
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  tail call void bitcast (void (...)* @callv to void ()*)()
+  br label %if.end4
+
+if.else:
+  %cmp1 = icmp slt i64 %a, 55
+  br i1 %cmp1, label %if.then2, label %if.end4
+
+if.then2:
+  tail call void bitcast (void (...)* @callv to void ()*)()
+  br label %if.end4
+
+if.end4:
+  %add.0 = phi i64 [ 234, %if.then ], [ 345, %if.then2 ], [ 2444, %if.else ]
+  %add5 = add nsw i64 %add.0, %a
+  %call = tail call i64 @call(i64 %add5)
+  ret i64 %call
+}
+
+declare void @callv(...)
+
+declare i64 @call(i64)