Add isRegSequence property

[qcolombet]

Summary

Hi,

This patch adds a new property: isRegSequence and the related target hook: TargetIntrInfo::getRegSequenceInputs to specify that a target specific instruction is a (kind of) REG_SEQUENCE.

I am looking forward for your feedbacks!

• Context **

This patch is a follow-up of the copy rewriting work made in peephole (http://reviews.llvm.org/D4086), which landed in r212100.

This patch is the first of a set of three patches that would teach how to get rid of some target specific copy in the advanced copy optimization of the peephole optimizer. See http://reviews.llvm.org/D4086 for more details.

Thanks to the property introduced in this patch, we would be able to optimize the following sequence:
_simpleVectorDiv: @ @simpleVectorDiv
@ BB#0: @ %entry
vmov d0, r2, r3
vmov d1, r0, r1
vmov r0, s0
vmov r1, s2
udiv r0, r1, r0
vmov r1, s1
vmov r2, s3
udiv r1, r2, r1
vmov.32 d16[0], r0
vmov.32 d16[1], r1
vmov r0, r1, d16
bx lr

into:
udiv r0, r0, r2
udiv r1, r1, r3
vmov.32 d16[0], r0
vmov.32 d16[1], r1
vmov r0, r1, d16
bx lr

But this is for the next patches (see next section).

• Proposed Patch **

The proposed patch allows to specify that an instruction behaves like a (kind of) REG_SEQUENCE.

In that case, "vmov d0, r2, r3" is equivalent to D0 = REG_SEQUENCE r2, ssub0, r3, ssub1.
The isRegSequence property is used to specify that, and the target hook TargetInstrInfo::getRegSequenceInputs is used to specify how to interpret those instructions if it was a REG_SEQUENCE.

The target hook takes a DefIdx because it is possible that an instruction behaves like a REG_SEQUENCE for a given definition, but not for another.

• What Is Next? **

• Make use of this property on target specific instruction
  ARM_reg_sequence.patch2 KBDownload
  .
• Teach the advanced copy optimizer about those instructions
  useRegSequenceAttribute.patch41 KBDownload
  .
• Do the same for insert_subreg and extract_subreg.

As soon as this patch lands, the next ones would be available through llvm-review.
I am attaching them to show the global direction of this.

Thanks,
-Quentin

[hfinkel]

I think that the general direction seems reasonable. Some comments...

lib/CodeGen/TargetInstrInfo.cpp

854

I would actually arrange this the other way. Have a target hook called getRegSequenceLikeInputs, which is called by this function. This function need not be virtual, but getRegSequenceLikeInputs would be virtual (and just return false by default). In this way, implementers of the callback don't need to remember to call the base class implementation to get the desired behavior for REG_SEQUENCE itself.

utils/TableGen/InstrInfoEmitter.cpp

507

All of the others are on one line, so this one should be too.

[qcolombet]

Hi Hal,

Thanks for the feedbacks, I’ll make the changes shortly.

Cheers,
-Quentin

lib/CodeGen/TargetInstrInfo.cpp

854

Good idea, I’ll update accordingly.

utils/TableGen/InstrInfoEmitter.cpp

507

Agree, looks like clang-format disagreed ;).

[qcolombet]

Update according Hal's feedbacks.

• Fix a formatting issue.
• Introduce a new target hook TargetInstrInfo::getRegSequenceLikeInputs called directly by TargetInstrInfo::getRegSequenceInputs.

[qcolombet]

Ping?

[hfinkel]

LGTM, thanks!

[qcolombet]

Thanks Hal!

Committed revision 215394.

include/llvm/CodeGen/MachineInstr.h

public:
   /// that can be expressed as constant-pool loads, such as V_SETALLONES
   /// on x86, to allow them to be folded when it is beneficial.
   /// This should only be set on instructions that return a value in their
   /// only virtual register definition.
   bool canFoldAsLoad(QueryType Type = IgnoreBundle) const {
     return hasProperty(MCID::FoldableAsLoad, Type);
   }
 
+  /// \brief Return true if this instruction behaves
+  /// the same way as the generic REG_SEQUENCE instructions.
+  /// E.g., on ARM,
+  /// dX VMOVDRR rY, rZ
+  /// is equivalent to
+  /// dX = REG_SEQUENCE rY, ssub_0, rZ, ssub_1.
+  ///
+  /// Note that for the optimizers to be able to take advantage of
+  /// this property, TargetInstrInfo::getRegSequenceInputs has to be
+  /// override accordingly.
+  bool isRegSequenceLike(QueryType Type = IgnoreBundle) const {
+    return hasProperty(MCID::RegSequence, Type);
+  }
+
   //===--------------------------------------------------------------------===//
   // Side Effect Analysis
   //===--------------------------------------------------------------------===//
 
   /// mayLoad - Return true if this instruction could possibly read memory.
   /// Instructions with this flag set are not necessarily simple load
   /// instructions, they may load a value and modify it, for example.
   bool mayLoad(QueryType Type = AnyInBundle) const {

include/llvm/MC/MCInstrDesc.h

enum {
     UnmodeledSideEffects,
     Commutable,
     ConvertibleTo3Addr,
     UsesCustomInserter,
     HasPostISelHook,
     Rematerializable,
     CheapAsAMove,
     ExtraSrcRegAllocReq,
-    ExtraDefRegAllocReq
+    ExtraDefRegAllocReq,
+    RegSequence
   };
 }
 
 /// MCInstrDesc - Describe properties that are true of each instruction in the
 /// target description file.  This captures information about side effects,
 /// register use and many other things.  There is one instance of this struct
 /// for each target instruction class, and the MachineInstr class points to
 /// this struct directly to describe itself.
public:
   /// that can be expressed as constant-pool loads, such as V_SETALLONES
   /// on x86, to allow them to be folded when it is beneficial.
   /// This should only be set on instructions that return a value in their
   /// only virtual register definition.
   bool canFoldAsLoad() const {
     return Flags & (1 << MCID::FoldableAsLoad);
   }
 
+  /// \brief Return true if this instruction behaves
+  /// the same way as the generic REG_SEQUENCE instructions.
+  /// E.g., on ARM,
+  /// dX VMOVDRR rY, rZ
+  /// is equivalent to
+  /// dX = REG_SEQUENCE rY, ssub_0, rZ, ssub_1.
+  ///
+  /// Note that for the optimizers to be able to take advantage of
+  /// this property, TargetInstrInfo::getRegSequenceInputs has to be
+  /// override accordingly.
+  bool isRegSequenceLike() const { return Flags & (1 << MCID::RegSequence); }
+
   //===--------------------------------------------------------------------===//
   // Side Effect Analysis
   //===--------------------------------------------------------------------===//
 
   /// \brief Return true if this instruction could possibly read memory.
   /// Instructions with this flag set are not necessarily simple load
   /// instructions, they may load a value and modify it, for example.
   bool mayLoad() const {

include/llvm/Target/TargetInstrInfo.h

virtual MachineInstr *commuteInstruction(MachineInstr *MI,
                                            bool NewMI = false) const;
 
   /// findCommutedOpIndices - If specified MI is commutable, return the two
   /// operand indices that would swap value. Return false if the instruction
   /// is not in a form which this routine understands.
   virtual bool findCommutedOpIndices(MachineInstr *MI, unsigned &SrcOpIdx1,
                                      unsigned &SrcOpIdx2) const;
 
+  /// A pair composed of a register and a sub-register index.
+  /// Used to give some type checking when modeling Reg:SubReg.
+  struct RegSubRegPair {
+    unsigned Reg;
+    unsigned SubReg;
+    RegSubRegPair(unsigned Reg = 0, unsigned SubReg = 0)
+        : Reg(Reg), SubReg(SubReg) {}
+  };
+  /// A pair composed of a pair of a register and a sub-register index,
+  /// and another sub-register index.
+  /// Used to give some type checking when modeling Reg:SubReg1, SubReg2.
+  struct RegSubRegPairAndIdx : RegSubRegPair {
+    unsigned SubIdx;
+    RegSubRegPairAndIdx(unsigned Reg = 0, unsigned SubReg = 0,
+                        unsigned SubIdx = 0)
+        : RegSubRegPair(Reg, SubReg), SubIdx(SubIdx) {}
+  };
+
+  /// Build the equivalent inputs of a REG_SEQUENCE for the given \p MI
+  /// and \p DefIdx.
+  /// \p [out] InputRegs of the equivalent REG_SEQUENCE. Each element of
+  /// the list is modeled as <Reg:SubReg, SubIdx>.
+  /// E.g., REG_SEQUENCE vreg1:sub1, sub0, vreg2, sub1 would produce
+  /// two elements:
+  /// - vreg1:sub1, sub0
+  /// - vreg2<:0>, sub1
+  ///
+  /// \returns true if it is possible to build such an input sequence
+  /// with the pair \p MI, \p DefIdx. False otherwise.
+  ///
+  /// \pre MI.isRegSequence() or MI.isRegSequenceLike().
+  ///
+  /// \note The generic implementation does not provide any support for
+  /// MI.isRegSequenceLike(). In other words, one has to override this
+  /// function for target specific instruction.
+  bool
+  getRegSequenceInputs(const MachineInstr &MI, unsigned DefIdx,
+                       SmallVectorImpl<RegSubRegPairAndIdx> &InputRegs) const;
+
   /// produceSameValue - Return true if two machine instructions would produce
   /// identical values. By default, this is only true when the two instructions
   /// are deemed identical except for defs. If this function is called when the
   /// IR is still in SSA form, the caller can pass the MachineRegisterInfo for
   /// aggressive checks.
   virtual bool produceSameValue(const MachineInstr *MI0,
                                 const MachineInstr *MI1,
                                 const MachineRegisterInfo *MRI = nullptr) const;
protected:
   /// take care of adding a MachineMemOperand to the newly created instruction.
   virtual MachineInstr* foldMemoryOperandImpl(MachineFunction &MF,
                                               MachineInstr* MI,
                                           const SmallVectorImpl<unsigned> &Ops,
                                               MachineInstr* LoadMI) const {
     return nullptr;
   }
 
+  /// \brief Target-dependent implementation of getRegSequenceInputs.
+  ///
+  /// \returns true if it is possible to build the equivalent
+  /// REG_SEQUENCE inputs with the pair \p MI, \p DefIdx. False otherwise.
+  ///
+  /// \pre MI.isRegSequenceLike().
+  ///
+  /// \see TargetInstrInfo::getRegSequenceInputs.
+  virtual bool getRegSequenceLikeInputs(
+      const MachineInstr &MI, unsigned DefIdx,
+      SmallVectorImpl<RegSubRegPairAndIdx> &InputRegs) const {
+    return false;
+  }
+
 public:
   /// canFoldMemoryOperand - Returns true for the specified load / store if
   /// folding is possible.
   virtual
   bool canFoldMemoryOperand(const MachineInstr *MI,
                             const SmallVectorImpl<unsigned> &Ops) const;
 
   /// unfoldMemoryOperand - Separate a single instruction which folded a load or

lib/CodeGen/TargetInstrInfo.cpp

computeOperandLatency(const InstrItineraryData *ItinData,
   // No operand latency was found.
   unsigned InstrLatency = getInstrLatency(ItinData, DefMI);
 
   // Expected latency is the max of the stage latency and itinerary props.
   InstrLatency = std::max(InstrLatency,
                           defaultDefLatency(ItinData->SchedModel, DefMI));
   return InstrLatency;
 }
+
+bool TargetInstrInfo::getRegSequenceInputs(
+    const MachineInstr &MI, unsigned DefIdx,
+    SmallVectorImpl<RegSubRegPairAndIdx> &InputRegs) const {
+  assert(MI.isRegSequence() ||
+         MI.isRegSequenceLike() && "Instruction do not have the proper type");
+
+  if (!MI.isRegSequence())
+    return getRegSequenceLikeInputs(MI, DefIdx, InputRegs);
+
+  // We are looking at:
+  // Def = REG_SEQUENCE v0, sub0, v1, sub1, ...
+  assert(DefIdx == 0 && "REG_SEQUENCE only has one def");
+  for (unsigned OpIdx = 1, EndOpIdx = MI.getNumOperands(); OpIdx != EndOpIdx;
+       OpIdx += 2) {
+    const MachineOperand &MOReg = MI.getOperand(OpIdx);
+    const MachineOperand &MOSubIdx = MI.getOperand(OpIdx + 1);
+    assert(MOSubIdx.isImm() &&
+           "One of the subindex of the reg_sequence is not an immediate");
+    // Record Reg:SubReg, SubIdx.
+    InputRegs.push_back(RegSubRegPairAndIdx(MOReg.getReg(), MOReg.getSubReg(),
+                                            (unsigned)MOSubIdx.getImm()));
+  }
+  return true;
+}

utils/TableGen/CodeGenInstruction.h

public:
     bool hasSideEffects : 1;
     bool hasSideEffects_Unset : 1;
     bool neverHasSideEffects : 1;
     bool isAsCheapAsAMove : 1;
     bool hasExtraSrcRegAllocReq : 1;
     bool hasExtraDefRegAllocReq : 1;
     bool isCodeGenOnly : 1;
     bool isPseudo : 1;
+    bool isRegSequence : 1;
 
     std::string DeprecatedReason;
     bool HasComplexDeprecationPredicate;
 
     /// Are there any undefined flags?
     bool hasUndefFlags() const {
       return mayLoad_Unset || mayStore_Unset || hasSideEffects_Unset;
     }

utils/TableGen/CodeGenInstruction.cpp

CodeGenInstruction::CodeGenInstruction(Record *R)
   isCommutable = R->getValueAsBit("isCommutable");
   isTerminator = R->getValueAsBit("isTerminator");
   isReMaterializable = R->getValueAsBit("isReMaterializable");
   hasDelaySlot = R->getValueAsBit("hasDelaySlot");
   usesCustomInserter = R->getValueAsBit("usesCustomInserter");
   hasPostISelHook = R->getValueAsBit("hasPostISelHook");
   hasCtrlDep   = R->getValueAsBit("hasCtrlDep");
   isNotDuplicable = R->getValueAsBit("isNotDuplicable");
+  isRegSequence = R->getValueAsBit("isRegSequence");
 
   bool Unset;
   mayLoad      = R->getValueAsBitOrUnset("mayLoad", Unset);
   mayLoad_Unset = Unset;
   mayStore     = R->getValueAsBitOrUnset("mayStore", Unset);
   mayStore_Unset = Unset;
   hasSideEffects = R->getValueAsBitOrUnset("hasSideEffects", Unset);
   hasSideEffects_Unset = Unset;

utils/TableGen/InstrInfoEmitter.cpp

void InstrInfoEmitter::emitRecord(const CodeGenInstruction &Inst, unsigned Num,
   if (Inst.Operands.hasOptionalDef) OS << "|(1<<MCID::HasOptionalDef)";
   if (Inst.usesCustomInserter) OS << "|(1<<MCID::UsesCustomInserter)";
   if (Inst.hasPostISelHook)    OS << "|(1<<MCID::HasPostISelHook)";
   if (Inst.Operands.isVariadic)OS << "|(1<<MCID::Variadic)";
   if (Inst.hasSideEffects)     OS << "|(1<<MCID::UnmodeledSideEffects)";
   if (Inst.isAsCheapAsAMove)   OS << "|(1<<MCID::CheapAsAMove)";
   if (Inst.hasExtraSrcRegAllocReq) OS << "|(1<<MCID::ExtraSrcRegAllocReq)";
   if (Inst.hasExtraDefRegAllocReq) OS << "|(1<<MCID::ExtraDefRegAllocReq)";
+  if (Inst.isRegSequence) OS << "|(1<<MCID::RegSequence)";
 
   // Emit all of the target-specific flags...
   BitsInit *TSF = Inst.TheDef->getValueAsBitsInit("TSFlags");
   if (!TSF)
     PrintFatalError("no TSFlags?");
   uint64_t Value = 0;
   for (unsigned i = 0, e = TSF->getNumBits(); i != e; ++i) {
     if (BitInit *Bit = dyn_cast<BitInit>(TSF->getBit(i)))