[llvm-dev] Extending Register Rematerialization

[Nirav Rana via llvm-dev]

Hello LLVM Developers,

We are working on extending currently available register rematerialization
to include cases where sequence of multiple instructions is required to
rematerialize a value.

We had a discussion on this in community mailing list and link is here:
http://lists.llvm.org/pipermail/llvm-dev/2016-September/subject.html#104777

>From the above discussion and studying the code we believe that extension
can be implemented in same flow as current remat is implemented. What we
unterstood is RegAlloc<>.cpp will try to allocate register to live-range,
and if not possible, will call InlineSpiller.cpp to spill the live range.
InlineSpiller.cpp will try to first rematerialize the register value if
possible with help of LiveRangeEdit.cpp which provides various methods for
checking if value is rematable or not.

So we have added a new function in LiveRangeEdit that traverses sequence of
instruction in use-def chain recursively (instead of only current
instruction in consideration) upto depth 6 (arbitrarily taken for
testing) to check if value can be rematerialized with the sequence of
instruction or not.

Here is the code:
//New function added for checking complex multi-instruction-sequence
rematerializable
bool LiveRangeEdit::checkComplexRematerializable(VNInfo *VNI,
                                          const MachineInstr *DefMI,
                                          unsigned int depth,
                                          AliasAnalysis *aa) {
  if(TII.isReMaterializablePossible(*DefMI, aa))
    return false;
  DEBUG(dbgs() << " ComplexRemat MI: " << *DefMI);
  for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = DefMI->getOperand(i);

    if (!MO.isReg() || !MO.getReg() || !MO.readsReg())
      continue;
    if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {
      if (MRI.isConstantPhysReg(MO.getReg(),
*DefMI->getParent()->getParent()))
        continue;
      //If not constant then check its def
      if(depth > 6)
        return false;

      LiveInterval &li = LIS.getInterval(MO.getReg());
      SlotIndex UseIdx = LIS.getInstructionIndex(*DefMI);
      VNInfo *UseVNInfo = li.getVNInfoAt(UseIdx);

      MachineInstr *NewDefMI = LIS.getInstructionFromIndex(UseVNInfo->def);
      if(!checkComplexRematerializable(UseVNInfo, NewDefMI, depth+1, aa))
        return false;
    }
  }
  Remattable.insert(VNI);     //May have to add new data structure
  return true;
}

In above function we are calling a new function
TII.isReMaterializablePossible(*DefMI, aa) which will act as early
heuristic and return false by checking if instruction is definitely not
rematerialize. We have found some cases
from TargetInstrInfo::isReallyTriviallyReMaterializableGeneric and code for
same is here:

bool TargetInstrInfo::isReMaterializablePossible(
    const MachineInstr &MI, AliasAnalysis *AA) const {
  const MachineFunction &MF = *MI.getParent()->getParent();
  const MachineRegisterInfo &MRI = MF.getRegInfo();

  // Remat clients assume operand 0 is the defined register.
  if (!MI.getNumOperands() || !MI.getOperand(0).isReg())
    return false;
  unsigned DefReg = MI.getOperand(0).getReg();

  // A sub-register definition can only be rematerialized if the instruction
  // doesn't read the other parts of the register.  Otherwise it is really a
  // read-modify-write operation on the full virtual register which cannot
be
  // moved safely.
  if (TargetRegisterInfo::isVirtualRegister(DefReg) &&
      MI.getOperand(0).getSubReg() && MI.readsVirtualRegister(DefReg))
    return false;

  // Avoid instructions obviously unsafe for remat.
  if (MI.isNotDuplicable() || MI.mayStore() || MI.hasUnmodeledSideEffects())
    return false;

  // Don't remat inline asm. We have no idea how expensive it is
  // even if it's side effect free.
  if (MI.isInlineAsm())
    return false;
}

We have following doubts and require guidance and suggestion to move ahead:
1. Is the approach we are following feasible?
2. What will be the suitable method to store the sequence of instruction
for recomputing value which will be used during transformation.
3. Suggestion for deciding termination condition for checking use-def chain
as it should be terminated when remat will be costly that spill.
4. What other cases or instruction could be included in
isReMaterializablePossible() function. Some suggestions for direction to
look in.

Any other suggestions will also be helpful for us to move in right
direction.

- Nirav
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161128/e94038db/attachment.html>