MachineLoopInfo: add function findInductionRegister.

[SjoerdMeijer]

Summary

MachineLoopInfo: add function findInductionRegister. This is mainly refactored from the Hexagon backend and is intended to be NFC. This is more groundwork to recognise loop induction variables and trip counts for MachineLoops, and is related to D27191 and D27192.

[qcolombet]

include/llvm/CodeGen/MachineLoopInfo.h

174

Which register would you return in such case:

///   R0 = phi ..., [ R1, LatchBlock ]
///   R1 = R0 + #bump
///   if (R1 < #N) goto loop

Is this supposed to work only on non-SSA code?

176

What do we do we more general representation?
E.g., R = R * 2
Or with R = R + RuntimeConstant?

Basically where I am going is shouldn't we have a representation a la SCEV?

[kparzysz]

include/llvm/CodeGen/MachineLoopInfo.h

174

The induction register is the one that is being "bumped", i.e. R0 in your case. This code only works on SSA.

176

Runtime constants won't work, neither will *=. This code was meant to get the typical "+= const" patterns.

Regarding the M-SCEV: yes, we should have it. What's missing is the time to do it. :)

It's been on my to-do-eventually list, and my idea was to use some sort of a common underlying representation of instructions (i.e. all add instructions for all targets would be represented as a generic "add" instruction). Now that we have GlobalISel, this groundwork is in place, we could develop some sort of a translation scheme from MIR to GIR(?), and then develop SCEV on top of that.

[SjoerdMeijer]

include/llvm/CodeGen/MachineLoopInfo.h

176

Thanks for the reviews. Yes, I agree, the recognised loops will be simple loops, and thus the approach is not very general, but it could serve some purposes though. Or now that GlobalIsel is being developed, is this technical debt that we don't want to develop further? I haven't followed the development of GlobalIsel close enough, but is it stable enough that we could be looking into SCEVs for machine instructions/GIR?

[qcolombet]

include/llvm/CodeGen/MachineLoopInfo.h

174

Thanks Krzysztof.
Could we update the comment accordingly?

176

GlobalISel simplifies some bits by providing generic opcodes with known semantic, but, by design, GlobalISel allows to mix those with target specific opcodes, so we would still need some way to retrieve the semantic of those.

Regarding the general approach, I would say this is up to you. I think it make sense to have a SCEV like framework at the machine level, I don't see how that patch helps us toward that goal though.

I think what we lack is a way to extract semantic from the instructions. GlobalISel partially solves that. The general problem is still open.

[SjoerdMeijer]

include/llvm/CodeGen/MachineLoopInfo.h

176

Regarding the general approach, I would say this is up to you.

Well, I am very much interested in your feedback. :-) What I also mean is that I don't want to have this in at all costs, or in other words, if we agree this patch is not going to help in any way then yes let's not waste time and abandon it. The way I could see this useful is that the we anyway need interfaces like this (e.g. findInductionRegister), but the implementation could different, i.e. ad-hoc at the moment, but should be done with proper MI scev analysis in the future. Perhaps this first hacky (but proven?) implementation could serve as reference when the scev analysis is developed? But again, if we think this is not the case let's abandon.
By the way, I am very interested in machine level scev analysis and think I am going to look into it soon.

[qcolombet]

Hi,

Thanks for your patience!

What I also mean is that I don't want to have this in at all costs, or in other words, if we agree this patch is not going to help in any way then yes let's not waste time and abandon it.

In that case, I would suggest to have a generic (Machine)Analysis pass that computes all the IVs. The way I envision this is by injecting more semantic on the target instructions. Hal suggested in another review (I don't remember which one though), that we could do that with a single API looking like bool TargetInstrInfo::isSimilarTo(const MachineInstr &MI, unsigned Opcode, SmallVectorImpl<MachineOperand *>& VRegs), where VRegs would contain the list of operands that matches Opcode behavior. We did not work out the details.
This gets possible thanks to GlobalISel that features generic opcodes that we can use as a reference (e.g., G_ADD, G_MUL, etc.).

The way we would use this API would look like:
// Check if this MI is an IV update of the form Def = Arg1 + Arg2.
SmallVector<MachineOperand *, 4> Opds;
if (TII->isSimilarTo(MI, TargetOpcode::G_ADD, Opds)) {

MachineOperand *Def = Opds[0];
MachineOperand *Arg1 = Opds[1]; 
MachineOperand *Arg2 = Opds[2];
// Check if the update is constant.
if (Arg2.isImm() || (Arg2.isReg && TII->isSimilarTo(MRI.getUniqueDef(Arg2.getReg()), G_CONSTANT, [...]))
[...]

}

Note: we may actually use something different than MachineOperand to represent similar construction but with no physical machine operand (e.g., a = b << 1 is equivalent to a = b * 2, but we don't have a MachineOperand to convey this information).

The nice thing about this direction is that we may be able to extract the semantic of some target specific instructions directly form the ISel patterns. E.g., if we have a pattern (add src1, src2) -> (ADDXrr src1, src2), we could deduce automatically that ADDXrr is similar to G_ADD.

Anyhow, there is a lot of work to be there and there may be dragons on the path!

Cheers,
-Quentin

[SjoerdMeijer]

Hi Quentin,
Apologies for my late reply, but thanks a lot for reviewing and for sharing your ideas/plans on this topic! I am going to follow your suggestions, will start prototyping an approach using global isel (and TII), and will abandon this patch.

Cheers,
Sjoerd.

include/llvm/CodeGen/MachineLoopInfo.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_MACHINELOOPINFO_H
 #define LLVM_CODEGEN_MACHINELOOPINFO_H
 
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
 
 namespace llvm {
 
 // Implementation in LoopInfoImpl.h
 class MachineLoop;
 extern template class LoopBase<MachineBasicBlock, MachineLoop>;
 
 class MachineLoop : public LoopBase<MachineBasicBlock, MachineLoop> {

 
 class MachineLoopInfo : public MachineFunctionPass {
   LoopInfoBase<MachineBasicBlock, MachineLoop> LI;
   friend class LoopBase<MachineBasicBlock, MachineLoop>;
 
   void operator=(const MachineLoopInfo &) = delete;
   MachineLoopInfo(const MachineLoopInfo &) = delete;
 
+  MachineRegisterInfo   *MRI;
+  const TargetInstrInfo *TII;
+
 public:
   static char ID; // Pass identification, replacement for typeid
 
   MachineLoopInfo() : MachineFunctionPass(ID) {
     initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
   }
 
   LoopInfoBase<MachineBasicBlock, MachineLoop>& getBase() { return LI; }
public:
   }
 
   /// This method completely removes BB from all data structures, including all
   /// of the Loop objects it is nested in and our mapping from
   /// MachineBasicBlocks to loops.
   void removeBlock(MachineBasicBlock *BB) {
     LI.removeBlock(BB);
   }
+
+  /// \brief Find the register that contains the loop controlling
+  /// induction variable.
+  /// If successful, it will return true and set the \p Reg, \p IVBump
+  /// and \p IVOp arguments.  Otherwise it will return false.
+  /// The returned induction register is the register R that follows the
+  /// following induction pattern:
+  /// loop:
+  ///   R = phi ..., [ R, LatchBlock ]
+  ///   R = R + #bump
+  ///   if (R < #N) goto loop
+  /// IVBump is the immediate value added to R, and IVOp is the instruction
+  /// "R = R + #bump".
+  bool findInductionRegister(MachineLoop *L, unsigned &Reg, int64_t &IVBump,
+                             MachineInstr *&IVOp) const;
+
 };
 
 
 // Allow clients to walk the list of nested loops...
 template <> struct GraphTraits<const MachineLoop*> {
   typedef const MachineLoop *NodeRef;
   typedef MachineLoopInfo::iterator ChildIteratorType;
 

lib/CodeGen/MachineLoopInfo.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/Analysis/LoopInfoImpl.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
 using namespace llvm;
 
 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
 template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
 template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
 
 char MachineLoopInfo::ID = 0;
 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
                 "Machine Natural Loop Construction", true, true)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
                 "Machine Natural Loop Construction", true, true)
 
 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
 
-bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
+bool MachineLoopInfo::runOnMachineFunction(MachineFunction &MF) {
   releaseMemory();
   LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
+  MRI = &MF.getRegInfo();
+  TII = MF.getSubtarget().getInstrInfo();
   return false;
 }
 
 void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<MachineDominatorTree>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
if (S == HB)
       continue;
     MachineLoop *T = getLoopFor(S);
     if (T && T->getHeader() == S)
       return nullptr;
   }
   return Preheader;
 }
 
+bool MachineLoopInfo::findInductionRegister(MachineLoop *L,
+                                            unsigned &Reg,
+                                            int64_t &IVBump,
+                                            MachineInstr *&IVOp) const {
+  MachineBasicBlock *Header = L->getHeader();
+  MachineBasicBlock *Preheader = findLoopPreheader(L, false);
+  MachineBasicBlock *Latch = L->getLoopLatch();
+  MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
+  if (!Header || !Preheader || !Latch || !ExitingBlock)
+    return false;
+
+  // This pair represents an induction register together with an immediate
+  // value that will be added to it in each loop iteration.
+  typedef std::pair<unsigned,int64_t> RegisterBump;
+
+  // Mapping:  R.next -> (R, bump), where R, R.next and bump are derived
+  // from an induction operation
+  //   R.next = R + bump
+  // where bump is an immediate value.
+  typedef std::map<unsigned,RegisterBump> InductionMap;
+
+  InductionMap IndMap;
+
+  typedef MachineBasicBlock::instr_iterator instr_iterator;
+  for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
+       I != E && I->isPHI(); ++I) {
+    MachineInstr *Phi = &*I;
+
+    // Have a PHI instruction.  Get the operand that corresponds to the
+    // latch block, and see if is a result of an addition of form "reg+imm",
+    // where the "reg" is defined by the PHI node we are looking at.
+    for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
+      if (Phi->getOperand(i+1).getMBB() != Latch)
+        continue;
+
+      unsigned PhiOpReg = Phi->getOperand(i).getReg();
+      MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
+
+      if (DI->getDesc().isAdd()) {
+        // If the register operand to the add is the PHI we're looking at, this
+        // meets the induction pattern.
+        unsigned IndReg = DI->getOperand(1).getReg();
+        MachineOperand &Opnd2 = DI->getOperand(2);
+        int64_t V;
+        if (MRI->getVRegDef(IndReg) == Phi &&
+            TII->getInstrOperandImmValue(*DI, Opnd2, V)) {
+          unsigned UpdReg = DI->getOperand(0).getReg();
+          IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
+        }
+      }
+    }  // for (i)
+  }  // for (instr)
+
+  unsigned CmpReg1 = 0, CmpReg2 = 0;
+  int CmpMask = 0, CmpImm = 0;
+  if (!TII->analyzeLoopTestBlock(*ExitingBlock, CmpReg1, CmpReg2, CmpMask, CmpImm))
+    return false;
+
+  // Exactly one of the input registers to the comparison should be among
+  // the induction registers.
+  InductionMap::iterator IndMapEnd = IndMap.end();
+  InductionMap::iterator F = IndMapEnd;
+  if (CmpReg1 != 0) {
+    InductionMap::iterator F1 = IndMap.find(CmpReg1);
+    if (F1 != IndMapEnd)
+      F = F1;
+  }
+  if (CmpReg2 != 0) {
+    InductionMap::iterator F2 = IndMap.find(CmpReg2);
+    if (F2 != IndMapEnd) {
+      if (F != IndMapEnd)
+        return false;
+      F = F2;
+    }
+  }
+  if (F == IndMapEnd)
+    return false;
+
+  Reg = F->second.first;
+  IVBump = F->second.second;
+  IVOp = MRI->getVRegDef(F->first);
+
+  return true;
+}
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void MachineLoop::dump() const {
   print(dbgs());
 }
 #endif

lib/Target/Hexagon/HexagonHardwareLoops.cpp

CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
   // location of the value depends upon the type (reg or imm).
   MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
   if (!ExitingBlock)
     return nullptr;
 
   unsigned IVReg = 0;
   int64_t IVBump = 0;
   MachineInstr *IVOp;
-  bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
-  if (!FoundIV)
+
+  if (!MLI->findInductionRegister(L, IVReg, IVBump, IVOp))
     return nullptr;
 
   MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
 
   MachineOperand *InitialValue = nullptr;
   MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
   MachineBasicBlock *Latch = L->getLoopLatch();
   for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {