<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Dec 2, 2016 at 3:06 AM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><br><hr id="m_-3732787234952924318gmail-m_-8342015262615401329zwchr"><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"><b>From: </b>"Nirav Rana" <<a href="mailto:nirav076@gmail.com" target="_blank">nirav076@gmail.com</a>><br><b>To: </b><a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>, <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br><b>Cc: </b>"Pandya Vivek" <<a href="mailto:h2015078@pilani.bits-pilani.ac.in" target="_blank">h2015078@pilani.bits-pilani.a<wbr>c.in</a>>, <a href="mailto:h2015089@pilani.bits-pilani.ac.in" target="_blank">h2015089@pilani.bits-pilani.ac<wbr>.in</a>, <a href="mailto:h2015172@pilani.bits-pilani.ac.in" target="_blank">h2015172@pilani.bits-pilani.ac<wbr>.in</a><br><b>Sent: </b>Sunday, November 27, 2016 2:37:14 PM<br><b>Subject: </b>Extending Register Rematerialization<div><div class="m_-3732787234952924318gmail-h5"><br><br><div dir="ltr">Hello LLVM Developers,<div><br></div><div>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><br></div><div>We had a discussion on this in community mailing list and link is here: </div><div><a href="http://lists.llvm.org/pipermail/llvm-dev/2016-September/subject.html#104777" target="_blank">http://lists.llvm.org/pipermai<wbr>l/llvm-dev/2016-September/<wbr>subject.html#104777</a><br></div><div><br></div><div>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><br></div><div>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><br></div><div>Here is the code:</div><div>//New function added for checking complex multi-instruction-sequence rematerializable</div><div>bool LiveRangeEdit::checkComplexRem<wbr>aterializable(VNInfo *VNI,</div><div> const MachineInstr *DefMI,</div><div> unsigned int depth,</div><div> AliasAnalysis *aa) {</div><div> if(TII.isReMaterializablePossi<wbr>ble(*DefMI, aa))</div><div> return false;</div><div> DEBUG(dbgs() << " ComplexRemat MI: " << *DefMI);</div><div> for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {</div><div> const MachineOperand &MO = DefMI->getOperand(i);</div><div><br></div><div> if (!MO.isReg() || !MO.getReg() || !MO.readsReg())</div><div> continue;</div><div> if (TargetRegisterInfo::isPhysica<wbr>lRegister(MO.getReg())) {</div><div> if (MRI.isConstantPhysReg(MO.getR<wbr>eg(), *DefMI->getParent()->getParent<wbr>()))</div><div> continue;</div><div> //If not constant then check its def</div><div> if(depth > 6)</div><div> return false;</div><div><br></div><div> LiveInterval &li = LIS.getInterval(MO.getReg());</div><div> SlotIndex UseIdx = LIS.getInstructionIndex(*DefMI<wbr>);</div><div> VNInfo *UseVNInfo = li.getVNInfoAt(UseIdx);</div><div><br></div><div> MachineInstr *NewDefMI = LIS.getInstructionFromIndex(Us<wbr>eVNInfo->def);</div><div> if(!checkComplexRematerializab<wbr>le(UseVNInfo, NewDefMI, depth+1, aa))</div><div> return false;</div><div> }</div><div> }</div><div> Remattable.insert(VNI); //May have to add new data structure</div><div> return true;</div><div>} </div><div><br></div><div>In above function we are calling a new function TII.isReMaterializablePossible<wbr>(*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::isReally<wbr>TriviallyReMaterializableGener<wbr>ic and code for same is here:</div><div><br></div><div><div>bool TargetInstrInfo::isReMateriali<wbr>zablePossible(</div><div> const MachineInstr &MI, AliasAnalysis *AA) const {</div><div> const MachineFunction &MF = *MI.getParent()->getParent();</div><div> const MachineRegisterInfo &MRI = MF.getRegInfo();</div><div><br></div><div> // Remat clients assume operand 0 is the defined register.</div><div> if (!MI.getNumOperands() || !MI.getOperand(0).isReg())</div><div> return false;</div><div> unsigned DefReg = MI.getOperand(0).getReg();</div><div><br></div><div> // A sub-register definition can only be rematerialized if the instruction</div><div> // doesn't read the other parts of the register. Otherwise it is really a</div><div> // read-modify-write operation on the full virtual register which cannot be</div><div> // moved safely.</div><div> if (TargetRegisterInfo::isVirtual<wbr>Register(DefReg) &&</div><div> MI.getOperand(0).getSubReg() && MI.readsVirtualRegister(DefReg<wbr>))</div><div> return false;</div><div><br></div><div> // Avoid instructions obviously unsafe for remat.</div><div> if (MI.isNotDuplicable() || MI.mayStore() || MI.hasUnmodeledSideEffects())</div><div> return false;</div><div><br></div><div> // Don't remat inline asm. We have no idea how expensive it is</div><div> // even if it's side effect free.</div><div> if (MI.isInlineAsm())</div><div> return false;</div><div>}</div></div><div><br></div><div>We have following doubts and require guidance and suggestion to move ahead:</div><div>1. Is the approach we are following feasible?</div><div>2. What will be the suitable method to store the sequence of instruction for recomputing value which will be used during transformation.</div><div>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>4. What other cases or instruction could be included in isReMaterializablePossible() function. Some suggestions for direction to look in.</div><div><br></div><div id="m_-3732787234952924318gmail-m_-8342015262615401329DWT4155">Any other suggestions will also be helpful for us to move in right direction.</div></div></div></div></blockquote>I think sounds feasible. Regarding the second question, I'm not sure what you're asking.<br></div></div></blockquote><div><br></div><div>Current rematerialization first checks if there is any remat possible or not and stores this information in Remattable variable. Actual remat is done by again getting the def, which is fine because we only need to get def (only one step above). But because in this case we are traversing use-def chain for multiple instructions, if we do not store this information of sequence of instructions required to recompute value, doing it again for actual remat would be redundant work. So my question is what structure could be used for storing this information, that can be used to clone and add those instruction for recomputing the value. Will a<span style="background-color:rgb(251,252,253);color:rgb(0,0,0);font-family:monospace,fixed;font-size:9pt"> </span><span style="color:rgb(0,0,0);font-family:consolas,"deja vu sans mono","bitstream vera sans mono",monospace;font-size:13.3px">SmallVector< </span><span style="color:rgb(0,0,0);font-family:consolas,"deja vu sans mono","bitstream vera sans mono",monospace;font-size:13.3px">TinyPtrVector</span><<wbr>const MachineInstr<span style="color:rgb(0,0,0);font-family:"lucida grande",verdana,geneva,arial,sans-serif;font-size:13px;text-align:-webkit-right;white-space:nowrap;background-color:rgb(249,250,252)"> *</span>, 6>> would be write choice? where TinyPtrVector with store sequence of instructions for remat.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><br>Regarding isReMaterializablePossible(), if you're allowing instructions that read from memory, and many of the use cases fall into that category, you'll need to consider whether you'd be moving any potential load past some aliasing store. We have code that does these kinds of checks in the instruction scheduler (in ScheduleDAGInstrs). The instruction scheduler builds a graph structure detailing these dependencies; maybe we should just keep it around for RA?<br><span style="font-family:arial,sans-serif;font-size:small;color:rgb(34,34,34)"> </span><br></div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)">One of the issues we obviously need to deal with is the relative cost of rematerialization vs. the spill/restore. We have code that does this kind of comparison today in the MachineCombiner, and I think that the same kind of comparison is needed here.<br></div></div></blockquote><div><br></div><div>Ok we will study both these modules (<span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;font-size:13.3333px">ScheduleDAGInstrs and </span><span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;font-size:13.3333px">MachineCombiner</span>).</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><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 dir="ltr"><div></div><div><br></div><div>- Nirav</div></div><span class="m_-3732787234952924318gmail-HOEnZb"><font color="#888888">
</font></span></blockquote><span class="m_-3732787234952924318gmail-HOEnZb"><font color="#888888"><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></font></span></div></div></blockquote></div><br></div></div>