<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote id="DWT8227" style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Gerolf Hoflehner" <ghoflehner@apple.com><br><b>To: </b>"Nirav Rana" <nirav076@gmail.com><br><b>Cc: </b>hfinkel@anl.gov, llvm-dev@lists.llvm.org, "Pandya Vivek" <h2015078@pilani.bits-pilani.ac.in>, h2015089@pilani.bits-pilani.ac.in, h2015172@pilani.bits-pilani.ac.in<br><b>Sent: </b>Thursday, December 1, 2016 6:14:06 PM<br><b>Subject: </b>Re: [llvm-dev] Extending Register Rematerialization<br><br>
On which targets & apps/benchmarks do you expect a speed-up? In practice I expect spills/fills to be hard to beat by longer remat sequences.</blockquote>Why?<br><br>Perhaps it depends on how you define "longer." A larger OOO core with multiple pipelines can often execute a materialization sequence consisting of several instructions faster than it can get data from the L1 cache. If the code is already putting pressure on the load/store units then the extra spill/restore code can be noticeably worse.<br><br>Note the following from AArch64InstrInfo.td:<br><br>let isReMaterializable = 1, isCodeGenOnly = 1, isMoveImm = 1,<br> isAsCheapAsAMove = 1 in {<br>// FIXME: The following pseudo instructions are only needed because remat<br>// cannot handle multiple instructions. When that changes, we can select<br>// directly to the real instructions and get rid of these pseudos.<br><br>def MOVi32imm<br> : Pseudo<(outs GPR32:$dst), (ins i32imm:$src),<br> [(set GPR32:$dst, imm:$src)]>,<br> Sched<[WriteImm]>;<br>def MOVi64imm<br> : Pseudo<(outs GPR64:$dst), (ins i64imm:$src),<br> [(set GPR64:$dst, imm:$src)]>,<br> Sched<[WriteImm]>;<br>} // isReMaterializable, isCodeGenOnly<br><br><br>Also, I think that Ivan Baev's talk at the developers' meeting a couple of years ago also provides some good hints of places to look for where this might matter: http://llvm.org/devmtg/2014-10/#talk20<br><br>Thanks again,<br>Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div class=""><br class=""></div><div class="">Thanks</div><div class="">Gerolf</div><div class=""><br class=""><div><blockquote class=""><div class="">On Nov 27, 2016, at 12:37 PM, Nirav Rana via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hello LLVM Developers,<div class=""><br class=""></div><div class="">We are working on extending currently available register rematerialization to include cases where sequence of multiple instructions is required to rematerialize a value.</div><div class=""><br class=""></div><div class="">We had a discussion on this in community mailing list and link is here: </div><div class=""><a href="http://lists.llvm.org/pipermail/llvm-dev/2016-September/subject.html#104777" class="" target="_blank">http://lists.llvm.org/pipermail/llvm-dev/2016-September/subject.html#104777</a><br class=""></div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">Here is the code:</div><div class="">//New function added for checking complex multi-instruction-sequence rematerializable</div><div class="">bool LiveRangeEdit::checkComplexRematerializable(VNInfo *VNI,</div><div class=""> const MachineInstr *DefMI,</div><div class=""> unsigned int depth,</div><div class=""> AliasAnalysis *aa) {</div><div class=""> if(TII.isReMaterializablePossible(*DefMI, aa))</div><div class=""> return false;</div><div class=""> DEBUG(dbgs() << " ComplexRemat MI: " << *DefMI);</div><div class=""> for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {</div><div class=""> const MachineOperand &MO = DefMI->getOperand(i);</div><div class=""><br class=""></div><div class=""> if (!MO.isReg() || !MO.getReg() || !MO.readsReg())</div><div class=""> continue;</div><div class=""> if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {</div><div class=""> if (MRI.isConstantPhysReg(MO.getReg(), *DefMI->getParent()->getParent()))</div><div class=""> continue;</div><div class=""> //If not constant then check its def</div><div class=""> if(depth > 6)</div><div class=""> return false;</div><div class=""><br class=""></div><div class=""> LiveInterval &li = LIS.getInterval(MO.getReg());</div><div class=""> SlotIndex UseIdx = LIS.getInstructionIndex(*DefMI);</div><div class=""> VNInfo *UseVNInfo = li.getVNInfoAt(UseIdx);</div><div class=""><br class=""></div><div class=""> MachineInstr *NewDefMI = LIS.getInstructionFromIndex(UseVNInfo->def);</div><div class=""> if(!checkComplexRematerializable(UseVNInfo, NewDefMI, depth+1, aa))</div><div class=""> return false;</div><div class=""> }</div><div class=""> }</div><div class=""> Remattable.insert(VNI); //May have to add new data structure</div><div class=""> return true;</div><div class="">} </div><div class=""><br class=""></div><div class="">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:</div><div class=""><br class=""></div><div class=""><div class="">bool TargetInstrInfo::isReMaterializablePossible(</div><div class=""> const MachineInstr &MI, AliasAnalysis *AA) const {</div><div class=""> const MachineFunction &MF = *MI.getParent()->getParent();</div><div class=""> const MachineRegisterInfo &MRI = MF.getRegInfo();</div><div class=""><br class=""></div><div class=""> // Remat clients assume operand 0 is the defined register.</div><div class=""> if (!MI.getNumOperands() || !MI.getOperand(0).isReg())</div><div class=""> return false;</div><div class=""> unsigned DefReg = MI.getOperand(0).getReg();</div><div class=""><br class=""></div><div class=""> // A sub-register definition can only be rematerialized if the instruction</div><div class=""> // doesn't read the other parts of the register. Otherwise it is really a</div><div class=""> // read-modify-write operation on the full virtual register which cannot be</div><div class=""> // moved safely.</div><div class=""> if (TargetRegisterInfo::isVirtualRegister(DefReg) &&</div><div class=""> MI.getOperand(0).getSubReg() && MI.readsVirtualRegister(DefReg))</div><div class=""> return false;</div><div class=""><br class=""></div><div class=""> // Avoid instructions obviously unsafe for remat.</div><div class=""> if (MI.isNotDuplicable() || MI.mayStore() || MI.hasUnmodeledSideEffects())</div><div class=""> return false;</div><div class=""><br class=""></div><div class=""> // Don't remat inline asm. We have no idea how expensive it is</div><div class=""> // even if it's side effect free.</div><div class=""> if (MI.isInlineAsm())</div><div class=""> return false;</div><div class="">}</div></div><div class=""><br class=""></div><div class="">We have following doubts and require guidance and suggestion to move ahead:</div><div class="">1. Is the approach we are following feasible?</div><div class="">2. What will be the suitable method to store the sequence of instruction for recomputing value which will be used during transformation.</div><div class="">3. Suggestion for deciding termination condition for checking use-def chain as it should be terminated when remat will be costly that spill. </div><div class="">4. What other cases or instruction could be included in isReMaterializablePossible() function. Some suggestions for direction to look in.</div><div class=""><br class=""></div><div class="">Any other suggestions will also be helpful for us to move in right direction.</div><div class=""><br class=""></div><div class="">- Nirav</div></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></div></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Lead, Compiler Technology and Programming Languages<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>