<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 29, 2017 at 2:17 PM, Justin Bogner <span dir="ltr"><<a href="mailto:mail@justinbogner.com" target="_blank">mail@justinbogner.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">Puyan Lotfi via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> writes:<br>
> mir-canon: A new tool for canonicalizing MIR for cleaner diffing.<br>
><br>
> Problem Statement and Context:<br>
><br>
> Diff-tools are regularly used for comparing IR and assembly files. This often<br>
> involves reasoning through differences that are semantically equivalent and it<br>
> can be very time consuming for a person to do said reasoning.<br>
><br>
> Specifically in the context of GlobalISel development there are problems of<br>
> correctness verification. There is a need to compare two programs, compiled<br>
> from identical IR by two different instruction selectors in a way where the<br>
> true differences stand out.<br>
><br>
> Proposal:<br>
><br>
> We propose a new tool that we have tentatively named 'mir-canon' that performs<br>
> canonical transformations on MIR. The goal is for MIR pre-processed with<br>
> mir-canon to show fewer differences than if it were not pre-processed.<br>
<br>
</span>This sounds great. One place I'm hoping to use this for is in ISel<br>
fuzzing - we can currently catch crashes and machine verifier errors,<br>
but comparing SDAG to GlobalISel is a space that I'd really like to<br>
explore.<br></blockquote><div><br></div><div>Thats exactly what I'm trying to do. I'm still trying to think of good ways to narrow down the set of functions and basic blocks that get canonicalized. I have some opt flags to control that but I think the control could be better. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<span class=""><br>
> At the time of this writing we have a prototype canonicalization tool. We’ve<br>
> come up with some techniques that show promise and would like to open<br>
> discussion with the community to get feedback and suggestions on refining said<br>
> techniques. Currently we think of this as an open ended project.<br>
><br>
> Techniques:<br>
><br>
> Our prototype does the following for each basic block in a Reverse Post<br>
> Ordering:<br>
><br>
</span>> * Canonical instruction ordering is done by moving a given instruction as<br>
<span class="">> close to the nearest use of its def as possible.<br>
><br>
</span>> * Next, canonical VReg renaming is done by building a collection of<br>
<span class="">> candidate instructions that can be thought of as sinks in the def-use<br>
> graph: they are typically instructions that write to physical registers or<br>
> store to memory. These candidates are used as the root of a breadth first<br>
> walk over the vreg operand def-use graph that determines a canonical vreg<br>
> ordering.<br>
><br>
</span>> * Using said canonical vreg ordering we rename monotonically, but before we<br>
<span class="">> do this we skip several vreg values in order to increase the chance that<br>
> we land on the same vreg number for two different input MIR files.<br>
<br>
</span>This is one place where handling multiple files at once would help, correct?<br>
<span class=""><br></span></blockquote><div><br></div><div>I think so. I think if I were processing two files at once I could increment the vreg count by a more exact number between basic blocks processed and between def-use walks.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
> We also do this to reduce the chances that a difference in<br>
> previously def-use walks will affect the vreg renaming for<br>
> subsequent walks. This skipping step could be thought of as a kind<br>
> of vreg number reckoning: we skip modulo n vregs so that we are<br>
> likely to land on the same vreg for two different files.<br>
><br>
> This approach is completely agnostic of ISA specific semantics so it should<br>
> work for any target.<br>
><br>
> Current status:<br>
><br>
> At the moment we have a standalone llvm tool that uses a single pass to do<br>
> the above described transformations. We have test inputs that show promise<br>
> but we still need a wider set of tests as well as hard metrics.<br>
<br>
</span>This sounds like a great start, but I feel like this design won't quite<br>
scale to all the ways we want to use this.<br>
<br>
Consider, if this was a pass in the LLVM library rather than only<br>
accessible in a tool, you could potentially set it up to run at the end<br>
of an `llc` run. Similarly, if I want to use this in a fuzzer it would<br>
be nice to be able to do the canonicalization in memory.<br>
<span class=""><br></span></blockquote><div><br></div><div> I used to have it as an LLVM pass but a while ago I thought it could be more prudent to have contained in a separate tool as it wasn't actually for optimization or codegen. I can easily reintegrate it as an LLVM pass. I'll send out another patch. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
> Our approach processes a single file at a time. The primary benefit to this<br>
> approach is lower complexity in initial implementation and exploration of<br>
> building such a tool. We are open to other approaches such as an llvm-diff<br>
> like (two file at a time) approach, but we have not explored that avenue<br>
> fully yet.<br>
><br>
> We’re eager to hear community feedback and will be ready to share patches<br>
> for review soon.<br>
</span> ...<br>
> Patch for review.<br>
<br>
Please send the patch to llvm-commits (and refer back to this thread).<br>
Patch review is too much traffic for llvm-dev.<br>
<br></blockquote><div><br></div><div>Great, thanks!</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
> diff --git a/tools/mir-canon/CMakeLists.<wbr>txt b/tools/mir-canon/CMakeLists.<wbr>txt<br>
> new file mode 100644<br>
> index 00000000000..eb6722e4bd4<br>
> --- /dev/null<br>
> +++ b/tools/mir-canon/CMakeLists.<wbr>txt<br>
> @@ -0,0 +1,28 @@<br>
> +set(LLVM_LINK_COMPONENTS<br>
> + ${LLVM_TARGETS_TO_BUILD}<br>
> + Analysis<br>
> + AsmPrinter<br>
> + CodeGen<br>
> + Core<br>
> + IRReader<br>
> + MC<br>
> + MIRParser<br>
> + ScalarOpts<br>
> + SelectionDAG<br>
> + Support<br>
> + Target<br>
> + TransformUtils<br>
> + Vectorize<br>
> + )<br>
> +<br>
> +# Support plugins.<br>
> +set(LLVM_NO_DEAD_STRIP 1)<br>
> +<br>
> +add_llvm_tool(mir-canon<br>
> + mir-canon.cpp<br>
> + MIRCanonicalizerPass.cpp<br>
> +<br>
> + DEPENDS<br>
> + intrinsics_gen<br>
> + )<br>
> +export_executable_symbols(<wbr>mir-canon)<br>
> diff --git a/tools/mir-canon/Common.h b/tools/mir-canon/Common.h<br>
> new file mode 100644<br>
> index 00000000000..3e6be7ef643<br>
> --- /dev/null<br>
> +++ b/tools/mir-canon/Common.h<br>
> @@ -0,0 +1,21 @@<br>
> +#include <cassert><br>
> +<br>
> +namespace llvm {<br>
> +/// The purpose of this pass is to establish a canonical operand naming so<br>
> +/// that code compiled with slightly different IR passes can be diffed more<br>
> +/// effectively than otherwise. This is done by renaming vregs in a given<br>
> +/// LiveRange in a canonical way.<br>
> +extern char &MIRCanonicalizerID;<br>
> +<br>
> +void initializeMIRCanonicalizerPass<wbr>(PassRegistry &);<br>
> +<br>
> +} // namespace llvm<br>
> +<br>
> +#define CANON_CHECK(CHK, MSG) \<br>
> + do { \<br>
> + if ((CHK)) break; \<br>
> + errs() << (std::string("") + MSG) << '\n'; \<br>
> + assert(false && "CANON_CHECK FAILURE."); \<br>
> + exit(EXIT_FAILURE); \<br>
> + } while (false)<br>
> +<br>
> diff --git a/tools/mir-canon/LLVMBuild.<wbr>txt b/tools/mir-canon/LLVMBuild.<wbr>txt<br>
> new file mode 100644<br>
> index 00000000000..5d3e6bb5a91<br>
> --- /dev/null<br>
> +++ b/tools/mir-canon/LLVMBuild.<wbr>txt<br>
> @@ -0,0 +1,22 @@<br>
> +;===- ./tools/mir-canon/LLVMBuild.<wbr>txt --------------------------*- Conf -*--===;<br>
> +;<br>
> +; The LLVM Compiler Infrastructure<br>
> +;<br>
> +; This file is distributed under the University of Illinois Open Source<br>
> +; License. See LICENSE.TXT for details.<br>
> +;<br>
> +;===-------------------------<wbr>------------------------------<wbr>-----------------===;<br>
> +;<br>
> +; This is an LLVMBuild description file for the components in this subdirectory.<br>
> +;<br>
> +; For more information on the LLVMBuild system, please see:<br>
> +;<br>
> +; <a href="http://llvm.org/docs/LLVMBuild.html" rel="noreferrer" target="_blank">http://llvm.org/docs/<wbr>LLVMBuild.html</a><br>
> +;<br>
> +;===-------------------------<wbr>------------------------------<wbr>-----------------===;<br>
> +<br>
> +[component_0]<br>
> +type = Tool<br>
> +name = mir-canon<br>
> +parent = Tools<br>
> +required_libraries = AsmParser BitReader IRReader MIRParser TransformUtils Scalar Vectorize all-targets<br>
> diff --git a/tools/mir-canon/<wbr>MIRCanonicalizerPass.cpp b/tools/mir-canon/<wbr>MIRCanonicalizerPass.cpp<br>
> new file mode 100644<br>
> index 00000000000..a4a0a7a0e5f<br>
> --- /dev/null<br>
> +++ b/tools/mir-canon/<wbr>MIRCanonicalizerPass.cpp<br>
> @@ -0,0 +1,588 @@<br>
> +//===-------------- MIRCanonicalizer.cpp - MIR Canonicalizer --------------===//<br>
> +//<br>
> +// The LLVM Compiler Infrastructure<br>
> +//<br>
> +// This file is distributed under the University of Illinois Open Source<br>
> +// License. See LICENSE.TXT for details.<br>
> +//<br>
> +//===------------------------<wbr>------------------------------<wbr>----------------===//<br>
> +//<br>
> +// Reorders instructions canonically.<br>
> +// Renames virtual register operands canonically.<br>
> +// Strips certain MIR artifacts (optionally).<br>
> +//<br>
> +//===------------------------<wbr>------------------------------<wbr>----------------===//<br>
> +<br>
> +#include "llvm/CodeGen/Passes.h"<br>
> +#include "llvm/CodeGen/<wbr>MachineInstrBuilder.h"<br>
> +#include "llvm/CodeGen/<wbr>MachineFunctionPass.h"<br>
> +#include "llvm/CodeGen/<wbr>MachineRegisterInfo.h"<br>
> +<br>
> +#include "llvm/Support/raw_ostream.h"<br>
> +#include "llvm/ADT/PostOrderIterator.h"<br>
> +#include "llvm/Target/TargetInstrInfo.<wbr>h"<br>
> +<br>
> +#include <tuple><br>
> +#include <queue><br>
> +<br>
> +using namespace llvm;<br>
> +<br>
> +#include "Common.h"<br>
> +<br>
> +#define DEBUG_TYPE "mir-canonicalizer"<br>
> +<br>
> +static cl::opt<unsigned><br>
> +CanonicalizeFunctionNumber("<wbr>canon-nth-function", cl::Hidden, cl::init(~0u),<br>
> + cl::value_desc("N"),<br>
> + cl::desc("Function number to canonicalize."));<br>
> +<br>
> +static cl::opt<unsigned><br>
> +CanonicalizeBasicBlockNumber(<wbr>"canon-nth-basicblock", cl::Hidden, cl::init(~0u),<br>
> + cl::value_desc("N"),<br>
> + cl::desc("BasicBlock number to canonicalize."));<br>
> +<br>
> +namespace {<br>
> +<br>
> +class MIRCanonicalizer : public MachineFunctionPass {<br>
> +public:<br>
> + static char ID;<br>
> + MIRCanonicalizer() : MachineFunctionPass(ID) {}<br>
> +<br>
> + StringRef getPassName() const override {<br>
> + return "Rename register operands in a canonical ordering.";<br>
> + }<br>
> +<br>
> + void getAnalysisUsage(AnalysisUsage &AU) const override {<br>
> + AU.setPreservesCFG();<br>
> + MachineFunctionPass::<wbr>getAnalysisUsage(AU);<br>
> + }<br>
> +<br>
> + bool runOnMachineFunction(<wbr>MachineFunction &MF) override;<br>
> +};<br>
> +<br>
> +} // end anonymous namespace<br>
> +<br>
> +enum RSType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };<br>
> +typedef std::tuple<RSType, unsigned> typedRegStackEntry;<br>
> +<br>
> +char MIRCanonicalizer::ID;<br>
> +<br>
> +char &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID;<br>
> +<br>
> +INITIALIZE_PASS_BEGIN(<wbr>MIRCanonicalizer, "mir-canonicalizer",<br>
> + "Rename Register Operands Canonically", false, false);<br>
> +<br>
> +INITIALIZE_PASS_END(<wbr>MIRCanonicalizer, "mir-canonicalizer",<br>
> + "Rename Register Operands Canonically", false, false);<br>
> +<br>
> +static std::vector<MachineBasicBlock *> GetRPOList(MachineFunction &MF) {<br>
> + MachineBasicBlock *Entry = &*MF.begin();<br>
> + std::vector<MachineBasicBlock*<wbr>> RPOList;<br>
> + ReversePostOrderTraversal<<wbr>MachineBasicBlock*> RPOT(Entry);<br>
> + for (ReversePostOrderTraversal<<wbr>MachineBasicBlock*>::rpo_<wbr>iterator<br>
> + MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {<br>
> + MachineBasicBlock *MBB = *MBBI;<br>
> + RPOList.push_back(MBB);<br>
> + }<br>
> +<br>
> + return RPOList;<br>
> +}<br>
> +<br>
> +// Set a dummy vreg. We use this vregs register class to generate throw-away<br>
> +// vregs that are used to skip vreg numbers so that vreg numbers line up.<br>
> +static unsigned GetDummyVReg(const MachineFunction &MF) {<br>
> + for (auto &MBB : MF) {<br>
> + for (auto II = MBB.begin(), IE = MBB.end(); II != IE; ++II) {<br>
> + const MachineInstr *MI = &*II;<br>
> + for (unsigned i = 0; i < MI->getNumOperands(); i++) {<br>
> + const MachineOperand &MO = MI->getOperand(i);<br>
> + if (!MO.isReg() || !TargetRegisterInfo::<wbr>isVirtualRegister(MO.getReg())<wbr>)<br>
> + continue;<br>
> + return MO.getReg();<br>
> + }<br>
> + }<br>
> + }<br>
> +<br>
> + return ~0U;<br>
> +}<br>
> +<br>
> +static bool rescheduleCanoncally(<wbr>MachineBasicBlock *MBB) {<br>
> +<br>
> + bool Changed = false;<br>
> +<br>
> + // Calculates the distance of MI from the begining of its parent BB.<br>
> + auto getInstrIdx = [](const MachineInstr &MI) {<br>
> + unsigned i = 0;<br>
> + for (auto &I : *MI.getParent()) {<br>
> + if (&I == &MI)<br>
> + return i;<br>
> + i++;<br>
> + }<br>
> + return ~0U;<br>
> + };<br>
> +<br>
> + // Pre-Populate vector of instructions to reschedule so that we don't<br>
> + // clobber the iterator.<br>
> + std::vector<MachineInstr *> instructions;<br>
> + for (auto II = MBB->begin(); II != MBB->end(); ++II) {<br>
> + instructions.push_back(&*II);<br>
> + }<br>
> +<br>
> + for (auto II : instructions) {<br>
> + if (II->getNumOperands() == 0)<br>
> + continue;<br>
> +<br>
> + MachineOperand &MO = II->getOperand(0);<br>
> + if (!MO.isReg() || !TargetRegisterInfo::<wbr>isVirtualRegister(MO.getReg())<wbr>)<br>
> + continue;<br>
> +<br>
> + DEBUG(dbgs() << "Operand " << 0 << " of "; II->dump(); MO.dump(););<br>
> +<br>
> + MachineInstr *def = II;<br>
> + unsigned distance = ~0U;<br>
> + MachineInstr *useToBringDefCloserTo = nullptr;<br>
> + MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo(<wbr>);<br>
> + for (auto UI = MRI->use_begin(MO.getReg()), UE = MRI->use_end();<br>
> + UI != UE; ++UI) {<br>
> + MachineInstr *useInst = UI->getParent();<br>
> +<br>
> + const unsigned defLoc = getInstrIdx(*def);<br>
> + const unsigned useLoc = getInstrIdx(*useInst);<br>
> + const unsigned delta = (useLoc - defLoc);<br>
> +<br>
> + if (useInst->getParent() != def->getParent())<br>
> + continue;<br>
> + if (defLoc >= useLoc)<br>
> + continue;<br>
> +<br>
> + if (delta < distance) {<br>
> + distance = delta;<br>
> + useToBringDefCloserTo = useInst;<br>
> + }<br>
> + }<br>
> +<br>
> + MachineBasicBlock::iterator defI = MBB->instr_end();<br>
> + MachineBasicBlock::iterator useI = MBB->instr_end();<br>
> +<br>
> + for (auto BBI = MBB->instr_begin(); BBI != MBB->instr_end(); ++BBI) {<br>
> +<br>
> + if (defI != MBB->instr_end() && useI != MBB->instr_end())<br>
> + break;<br>
> +<br>
> + if ((&*BBI != def) && (&*BBI != useToBringDefCloserTo))<br>
> + continue;<br>
> +<br>
> + if (&*BBI == def) {<br>
> + defI = BBI;<br>
> + continue;<br>
> + }<br>
> +<br>
> + if (&*BBI == useToBringDefCloserTo) {<br>
> + useI = BBI;<br>
> + continue;<br>
> + }<br>
> + }<br>
> +<br>
> + if (defI == MBB->instr_end() || useI == MBB->instr_end())<br>
> + continue;<br>
> +<br>
> + DEBUG(dbgs() << "Splicing "; defI->dump(); dbgs() << " right before: ";<br>
> + useI->dump(););<br>
> +<br>
> + Changed = true;<br>
> + MBB->splice(useI, MBB, defI);<br>
> + }<br>
> +<br>
> + return Changed;<br>
> +}<br>
> +<br>
> +static std::vector<MachineInstr *> populateCandidates(<wbr>MachineBasicBlock *MBB) {<br>
> + std::vector<MachineInstr *> candidates;<br>
> + MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo()<wbr>;<br>
> +<br>
> + for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {<br>
> + MachineInstr *MI = &*II;<br>
> +<br>
> + bool doesMISideEffect = false;<br>
> +<br>
> + if (MI->getOperand(0).isReg()) {<br>
> + const unsigned dst = MI->getOperand(0).getReg();<br>
> + doesMISideEffect |= !TargetRegisterInfo::<wbr>isVirtualRegister(dst);<br>
> +<br>
> + for (auto UI = MRI.use_begin(dst); UI != MRI.use_end(); ++UI) {<br>
> + if (doesMISideEffect) break;<br>
> + doesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());<br>
> + }<br>
> + }<br>
> +<br>
> + if (!MI->mayStore() && !MI->isBranch() && !doesMISideEffect)<br>
> + continue;<br>
> +<br>
> + DEBUG(dbgs() << "Found Candidate: "; MI->dump(););<br>
> + candidates.push_back(MI);<br>
> + }<br>
> +<br>
> + return candidates;<br>
> +}<br>
> +<br>
> +void doCandidateWalk(std::vector<<wbr>typedRegStackEntry> &VRegs,<br>
> + std::queue <typedRegStackEntry> ®_queue,<br>
> + std::vector<MachineInstr *> &visitedMIs,<br>
> + const MachineBasicBlock *MBB) {<br>
> +<br>
> + const MachineFunction &MF = *MBB->getParent();<br>
> + const MachineRegisterInfo &MRI = MF.getRegInfo();<br>
> +<br>
> + while (reg_queue.size()) {<br>
> + auto regType = std::get<0>(reg_queue.front())<wbr>;<br>
> + auto reg = std::get<1>(reg_queue.front())<wbr>;<br>
> + reg_queue.pop();<br>
> +<br>
> + if (regType == RSE_FrameIndex) {<br>
> + DEBUG(dbgs() << "Popping frame index.\n";);<br>
> + VRegs.push_back(std::make_<wbr>tuple(RSE_FrameIndex, ~0U));<br>
> + continue;<br>
> + }<br>
> +<br>
> + assert(regType == RSE_Reg && "Expected vreg or physreg.");<br>
> +<br>
> + if (TargetRegisterInfo::<wbr>isVirtualRegister(reg)) {<br>
> + DEBUG(dbgs() << "Popping vreg ";<br>
> + MRI.def_begin(reg)->dump();<br>
> + dbgs() << "\n";);<br>
> +<br>
> + bool hasVisitedVReg = false;<br>
> + for (auto vreg : VRegs) {<br>
> + if (std::get<1>(vreg) == reg) {<br>
> + hasVisitedVReg = true;<br>
> + break;<br>
> + }<br>
> + }<br>
> +<br>
> + if (!hasVisitedVReg)<br>
> + VRegs.push_back(std::make_<wbr>tuple(RSE_Reg, reg));<br>
> + } else {<br>
> + DEBUG(dbgs() << "Popping physreg.\n";);<br>
> + VRegs.push_back(std::make_<wbr>tuple(RSE_Reg, reg));<br>
> + continue;<br>
> + }<br>
> +<br>
> + for (auto RI = MRI.def_begin(reg), RE = MRI.def_end(); RI != RE; ++RI) {<br>
> + MachineInstr *def = RI->getParent();<br>
> +<br>
> + if (def->getParent() != MBB)<br>
> + continue;<br>
> +<br>
> + bool hasVisited = false;<br>
> + for (auto VMI : visitedMIs) {<br>
> + if (def == VMI) {<br>
> + hasVisited = true;<br>
> + break;<br>
> + }<br>
> + }<br>
> +<br>
> + if (hasVisited)<br>
> + break;<br>
> +<br>
> + DEBUG(dbgs() << "\n========================\n"<wbr>;<br>
> + dbgs() << "Visited MI: "; def->dump();<br>
> + dbgs() << "BB Name: " << def->getParent()->getName() << "\n";<br>
> + dbgs() << "\n========================\n"<wbr>;);<br>
> + visitedMIs.push_back(def);<br>
> + for (unsigned I = 1, E = def->getNumOperands(); I != E; ++I) {<br>
> +<br>
> + MachineOperand &MO = def->getOperand(I);<br>
> + if (MO.isFI()) {<br>
> + DEBUG(dbgs() << "Pushing frame index.\n";);<br>
> + reg_queue.push(std::make_<wbr>tuple(RSE_FrameIndex, ~0U));<br>
> + }<br>
> +<br>
> + if (!MO.isReg())<br>
> + continue;<br>
> + reg_queue.push(std::make_<wbr>tuple(RSE_Reg, MO.getReg()));<br>
> + }<br>
> + }<br>
> + }<br>
> +}<br>
> +<br>
> +static void SkipVRegs(unsigned &VRegGapIndex, MachineRegisterInfo &MRI,<br>
> + const TargetRegisterClass *RC) {<br>
> + const unsigned VR_GAP = (++VRegGapIndex * 1000);<br>
> +<br>
> + DEBUG(dbgs() << "Adjusting per-BB VR_GAP for BB" << VRegGapIndex << " to "<br>
> + << VR_GAP << "\n";);<br>
> +<br>
> + unsigned I = MRI.createVirtualRegister(RC);<br>
> + const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;<br>
> + while (I != E) {<br>
> + I = MRI.createVirtualRegister(RC);<br>
> + }<br>
> +<br>
> + CANON_CHECK(I != ~0U && I != 0, "Invalid VReg");<br>
> +}<br>
> +<br>
> +static void GetVRegRenameMap(std::map<<wbr>unsigned, unsigned> &vregRenameMap,<br>
> + const std::vector<<wbr>typedRegStackEntry> &VRegs,<br>
> + const std::vector<unsigned> &renamedInOtherBB,<br>
> + MachineRegisterInfo &MRI,<br>
> + const TargetRegisterClass *RC) {<br>
> +<br>
> + unsigned lastRenameReg = MRI.createVirtualRegister(RC);<br>
> +<br>
> + bool firstCandidate = true;<br>
> + for (auto vreg : VRegs) {<br>
> +<br>
> + auto regType = std::get<0>(vreg);<br>
> + auto reg = std::get<1>(vreg);<br>
> +<br>
> + if (regType == RSE_FrameIndex) {<br>
> + lastRenameReg = MRI.createVirtualRegister(RC);<br>
> + DEBUG(dbgs() << "Skipping rename for FI " << lastRenameReg << "\n";);<br>
> + continue;<br>
> + } else if (regType == RSE_NewCandidate) {<br>
> + if (!firstCandidate) {<br>
> + while (lastRenameReg % 10) {<br>
> + lastRenameReg = MRI.createVirtualRegister(RC);<br>
> +<br>
> + DEBUG(dbgs() << "Skipping rename for new candidate " << lastRenameReg<br>
> + << "\n";);<br>
> + }<br>
> + }<br>
> + firstCandidate = false;<br>
> + continue;<br>
> + } else if (!TargetRegisterInfo::<wbr>isVirtualRegister(reg)) {<br>
> + lastRenameReg = MRI.createVirtualRegister(RC);<br>
> + DEBUG(dbgs() << "Skipping rename for Phys Reg " << lastRenameReg << "\n";);<br>
> + continue;<br>
> + }<br>
> +<br>
> + if (std::find(renamedInOtherBB.<wbr>begin(), renamedInOtherBB.end(), reg) !=<br>
> + renamedInOtherBB.end()) {<br>
> + DEBUG(dbgs() << "Vreg " << reg << " already renamed in other BB.\n";);<br>
> + continue;<br>
> + }<br>
> +<br>
> + auto rename = MRI.createVirtualRegister(MRI.<wbr>getRegClass(reg));<br>
> + lastRenameReg = rename;<br>
> +<br>
> + if (vregRenameMap.find(reg) == vregRenameMap.end()) {<br>
> + DEBUG(dbgs() << "Mapping vreg ";);<br>
> + if (MRI.reg_begin(reg) != MRI.reg_end()) {<br>
> + DEBUG(auto foo = &*MRI.reg_begin(reg); foo->dump(););<br>
> + } else {<br>
> + DEBUG(dbgs() << reg;);<br>
> + }<br>
> + DEBUG(dbgs() << " to ";);<br>
> + if (MRI.reg_begin(rename) != MRI.reg_end()) {<br>
> + DEBUG(auto foo = &*MRI.reg_begin(rename); foo->dump(););<br>
> + } else {<br>
> + DEBUG(dbgs() << rename;);<br>
> + }<br>
> + DEBUG(dbgs() << "\n";);<br>
> +<br>
> + vregRenameMap.insert(std::<wbr>pair<unsigned, unsigned>(reg, rename));<br>
> + }<br>
> + }<br>
> +}<br>
> +<br>
> +static bool doVRegRenaming(std::vector<<wbr>unsigned> &renamedInOtherBB,<br>
> + const std::map<unsigned, unsigned> &vregRenameMap,<br>
> + MachineRegisterInfo &MRI) {<br>
> + bool Changed = false;<br>
> + for (auto I = vregRenameMap.begin(), E = vregRenameMap.end(); I != E; ++I) {<br>
> +<br>
> + auto vreg = I->first;<br>
> + auto rename = I->second;<br>
> +<br>
> + renamedInOtherBB.push_back(<wbr>rename);<br>
> +<br>
> + std::vector<MachineOperand *> renameMOs;<br>
> + for (MachineOperand &MO : MRI.reg_operands(vreg)) {<br>
> + renameMOs.push_back(&MO);<br>
> + }<br>
> +<br>
> + for (auto MO : renameMOs) {<br>
> + Changed = true;<br>
> + MO->setReg(rename);<br>
> +<br>
> + if (!MO->isDef())<br>
> + MO->setIsKill(false);<br>
> + }<br>
> + }<br>
> +<br>
> + return Changed;<br>
> +}<br>
> +<br>
> +static bool doDefKillClear(<wbr>MachineBasicBlock *MBB) {<br>
> + bool Changed = false;<br>
> +<br>
> + for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {<br>
> + MachineInstr *MI = &*II;<br>
> +<br>
> + for (unsigned i = 0; i < MI->getNumOperands(); i++) {<br>
> + MachineOperand &MO = MI->getOperand(i);<br>
> + if (!MO.isReg())<br>
> + continue;<br>
> + if (!MO.isDef() && MO.isKill()) {<br>
> + Changed = true;<br>
> + MO.setIsKill(false);<br>
> + }<br>
> +<br>
> + if (MO.isDef() && MO.isDead()) {<br>
> + Changed = true;<br>
> + MO.setIsDead(false);<br>
> + }<br>
> + }<br>
> + }<br>
> +<br>
> + return Changed;<br>
> +}<br>
> +<br>
> +static bool runOnBasicBlock(<wbr>MachineBasicBlock *MBB,<br>
> + std::vector<StringRef> &bbNames,<br>
> + std::vector<unsigned> &renamedInOtherBB,<br>
> + unsigned &basicBlockNum, unsigned &VRegGapIndex) {<br>
> +<br>
> + if (CanonicalizeBasicBlockNumber != ~0U) {<br>
> + if (CanonicalizeBasicBlockNumber != basicBlockNum++)<br>
> + return false;<br>
> + DEBUG(dbgs() << "\n Canonicalizing BasicBlock " << MBB->getName() << "\n";);<br>
> + }<br>
> +<br>
> + if (std::find(bbNames.begin(), bbNames.end(), MBB->getName()) !=<br>
> + bbNames.end()) {<br>
> + DEBUG(dbgs() << "Found potentially duplicate BasicBlocks: "<br>
> + << MBB->getName() << "\n";);<br>
> + return false;<br>
> + }<br>
> +<br>
> + DEBUG(<br>
> + dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << " \n\n";<br>
> + dbgs() << "\n\n=========================<wbr>=======================\n\n";<br>
> + );<br>
> +<br>
> + bool Changed = false;<br>
> + MachineFunction &MF = *MBB->getParent();<br>
> + MachineRegisterInfo &MRI = MF.getRegInfo();<br>
> +<br>
> + const TargetRegisterClass *dummyRC = [] (const MachineFunction &MF) {<br>
> + const unsigned dummyVReg = GetDummyVReg(MF);<br>
> + CANON_CHECK(dummyVReg != ~0U, "Could not find a dummy VReg.");<br>
> + const MachineRegisterInfo &MRI = MF.getRegInfo();<br>
> + return MRI.getRegClass(dummyVReg);<br>
> + } (MF);<br>
> +<br>
> + bbNames.push_back(MBB-><wbr>getName());<br>
> + DEBUG(dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << "\n\n";);<br>
> +<br>
> + DEBUG(dbgs() << "MBB Before Scheduling:\n"; MBB->dump(););<br>
> + Changed |= rescheduleCanoncally(MBB);<br>
> + DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););<br>
> +<br>
> + std::vector<MachineInstr *> candidates = populateCandidates(MBB);<br>
> + std::vector<MachineInstr *> visitedMIs;<br>
> + std::copy(candidates.begin(), candidates.end(),<br>
> + std::back_inserter(visitedMIs)<wbr>);<br>
> +<br>
> + std::vector<<wbr>typedRegStackEntry> VRegs;<br>
> + for (auto candidate : candidates) {<br>
> + VRegs.push_back(std::make_<wbr>tuple(RSE_NewCandidate, ~0U));<br>
> +<br>
> + std::queue<typedRegStackEntry> reg_queue;<br>
> +<br>
> + // Here we walk the vreg operands of a non-root node along our walk.<br>
> + // The root nodes are the original candidates (stores normally).<br>
> + // These are normally not the root nodes (except for the case of copies to<br>
> + // physical registers).<br>
> + for (unsigned i = 1; i < candidate->getNumOperands(); i++) {<br>
> + if (candidate->mayStore() || candidate->isBranch())<br>
> + break;<br>
> +<br>
> + MachineOperand &MO = candidate->getOperand(i);<br>
> + if (!(MO.isReg() && TargetRegisterInfo::<wbr>isVirtualRegister(MO.getReg())<wbr>))<br>
> + continue;<br>
> +<br>
> + DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);<br>
> + reg_queue.push(std::make_<wbr>tuple(RSE_Reg, MO.getReg()));<br>
> + }<br>
> +<br>
> + // Here we walk the root candidates. We start from the 0th operand because<br>
> + // the root is normally a store to a vreg.<br>
> + for (unsigned i = 0; i < candidate->getNumOperands(); i++) {<br>
> +<br>
> + if (!candidate->mayStore() && !candidate->isBranch())<br>
> + break;<br>
> +<br>
> + MachineOperand &MO = candidate->getOperand(i);<br>
> +<br>
> + // TODO: Do we want to only add vregs here?<br>
> + if (!MO.isReg() && !MO.isFI())<br>
> + continue;<br>
> +<br>
> + DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);<br>
> +<br>
> + reg_queue.push(MO.isReg() ? std::make_tuple(RSE_Reg, MO.getReg()) :<br>
> + std::make_tuple(RSE_<wbr>FrameIndex, ~0U));<br>
> + }<br>
> +<br>
> + // Now that we have pushed the operands of the candidate here, we do the<br>
> + // full breadth first walk.<br>
> + doCandidateWalk(VRegs, reg_queue, visitedMIs, MBB);<br>
> + }<br>
> +<br>
> + // If we have populated no vregs to rename then bail.<br>
> + // The rest of this function does the vreg remaping.<br>
> + if (VRegs.size() == 0)<br>
> + return Changed;<br>
> +<br>
> + // Skip some vregs, so we can recon where we'll land next.<br>
> + SkipVRegs(VRegGapIndex, MRI, dummyRC);<br>
> +<br>
> + std::map<unsigned, unsigned> vregRenameMap;<br>
> + GetVRegRenameMap(<wbr>vregRenameMap, VRegs, renamedInOtherBB, MRI, dummyRC);<br>
> +<br>
> + Changed |= doVRegRenaming(<wbr>renamedInOtherBB, vregRenameMap, MRI);<br>
> + Changed |= doDefKillClear(MBB);<br>
> +<br>
> + DEBUG(dbgs() << "Updated MachineBasicBlock:\n"; MBB->dump(); dbgs() << "\n";);<br>
> + DEBUG(dbgs() << "\n\n=========================<wbr>=======================\n\n");<br>
> + return Changed;<br>
> +}<br>
> +<br>
> +bool MIRCanonicalizer::<wbr>runOnMachineFunction(<wbr>MachineFunction &MF) {<br>
> +<br>
> + static unsigned functionNum = 0;<br>
> + if (CanonicalizeFunctionNumber != ~0U) {<br>
> + if (CanonicalizeFunctionNumber != functionNum++)<br>
> + return false;<br>
> + DEBUG(dbgs() << "\n Canonicalizing Function " << MF.getName() << "\n";);<br>
> + }<br>
> +<br>
> + // we need a valid vreg to create a vreg type for skipping all those<br>
> + // stray vreg numbers so reach alignment/canonical vreg values.<br>
> + std::vector<MachineBasicBlock*<wbr>> RPOList = GetRPOList(MF);<br>
> +<br>
> + DEBUG(<br>
> + dbgs() << "\n\n NEW MACHINE FUNCTION: " << MF.getName() << " \n\n";<br>
> + dbgs() << "\n\n=========================<wbr>=======================\n\n";<br>
> + dbgs() << "Total Basic Blocks: " << RPOList.size() << "\n";<br>
> + for (auto MBB : RPOList) {<br>
> + dbgs() << MBB->getName() << "\n";<br>
> + }<br>
> + dbgs() << "\n\n=========================<wbr>=======================\n\n";<br>
> + );<br>
> +<br>
> + std::vector<StringRef> bbNames;<br>
> + std::vector<unsigned> renamedInOtherBB;<br>
> +<br>
> + unsigned gapIdx = 0;<br>
> + unsigned bbNum = 0;<br>
> +<br>
> + bool Changed = false;<br>
> +<br>
> + for (auto MBB : RPOList)<br>
> + Changed |= runOnBasicBlock(MBB, bbNames, renamedInOtherBB, bbNum, gapIdx);<br>
> +<br>
> + return Changed;<br>
> +}<br>
> +<br>
> diff --git a/tools/mir-canon/mir-canon.<wbr>cpp b/tools/mir-canon/mir-canon.<wbr>cpp<br>
> new file mode 100644<br>
> index 00000000000..bfe53c01906<br>
> --- /dev/null<br>
> +++ b/tools/mir-canon/mir-canon.<wbr>cpp<br>
> @@ -0,0 +1,175 @@<br>
> +//===------ mir-canon.cpp - Implement the LLVM Native Code Generator ------===//<br>
> +//<br>
> +// The LLVM Compiler Infrastructure<br>
> +//<br>
> +// This file is distributed under the University of Illinois Open Source<br>
> +// License. See LICENSE.TXT for details.<br>
> +//<br>
> +//===------------------------<wbr>------------------------------<wbr>----------------===//<br>
> +//<br>
> +// This is the mir-canon driver. It invokes the MIR canonicalization pass.<br>
> +//<br>
> +//===------------------------<wbr>------------------------------<wbr>----------------===//<br>
> +<br>
> +#include "llvm/CodeGen/CommandFlags.h"<br>
> +#include "llvm/CodeGen/<wbr>TargetPassConfig.h"<br>
> +#include "llvm/CodeGen/<wbr>MachineModuleInfo.h"<br>
> +#include "llvm/CodeGen/<wbr>MachineFunctionPass.h"<br>
> +#include "llvm/CodeGen/MIRParser/<wbr>MIRParser.h"<br>
> +<br>
> +#include "llvm/IR/LLVMContext.h"<br>
> +#include "llvm/IR/DiagnosticInfo.h"<br>
> +#include "llvm/IR/IRPrintingPasses.h"<br>
> +#include "llvm/IR/DiagnosticPrinter.h"<br>
> +#include "llvm/IR/LegacyPassManager.h"<br>
> +<br>
> +#include "llvm/Support/Signals.h"<br>
> +#include "llvm/Support/FileSystem.h"<br>
> +#include "llvm/Support/TargetSelect.h"<br>
> +#include "llvm/Support/TargetRegistry.<wbr>h"<br>
> +#include "llvm/Support/ToolOutputFile.<wbr>h"<br>
> +#include "llvm/Support/FormattedStream.<wbr>h"<br>
> +#include "llvm/Support/<wbr>PrettyStackTrace.h"<br>
> +<br>
> +#include "llvm/Target/TargetMachine.h"<br>
> +#include "llvm/Target/<wbr>TargetSubtargetInfo.h"<br>
> +<br>
> +#include "Common.h"<br>
> +<br>
> +using namespace llvm;<br>
> +<br>
> +static cl::opt<std::string><br>
> + InputFilename(cl::Positional, cl::desc("<input.mir>"), cl::init("-"));<br>
> +<br>
> +static cl::opt<std::string> OutputFilename("o", cl::desc("Output filename"),<br>
> + cl::value_desc("canon.mir"));<br>
> +<br>
> +static cl::opt<std::string> TargetTriple("mtriple",<br>
> + cl::desc("Override target triple."));<br>
> +<br>
> +int main(int argc, char **argv) {<br>
> + sys::<wbr>PrintStackTraceOnErrorSignal(<wbr>argv[0]);<br>
> + PrettyStackTraceProgram X(argc, argv);<br>
> +<br>
> + EnableDebugBuffering = true;<br>
> +<br>
> + LLVMContext Context;<br>
> + llvm_shutdown_obj Y;<br>
> +<br>
> + // Initialize targets first, so that --version shows registered targets.<br>
> + InitializeAllTargets();<br>
> + InitializeAllTargetMCs();<br>
> + InitializeAllAsmPrinters();<br>
> + InitializeAllAsmParsers();<br>
> +<br>
> + PassRegistry *Registry = PassRegistry::getPassRegistry(<wbr>);<br>
> + initializeCore(*Registry);<br>
> + initializeCodeGen(*Registry);<br>
> +<br>
> + initializeMIRCanonicalizerPass<wbr>(*Registry);<br>
> +<br>
> + // Register the target printer for --version.<br>
> + cl::AddExtraVersionPrinter(<wbr>TargetRegistry::<wbr>printRegisteredTargetsForVersi<wbr>on);<br>
> +<br>
> + cl::ParseCommandLineOptions(<wbr>argc, argv, "llvm system compiler\n");<br>
> +<br>
> + CANON_CHECK(StringRef(<wbr>InputFilename).endswith_lower(<wbr>".mir"),<br>
> + "Invalid Filename: " + InputFilename + ". " +<br>
> + "Expected a .mir file extension.");<br>
> +<br>
> + // Set a diagnostic handler that doesn't exit on the first error<br>
> + bool HasError = false;<br>
> + Context.setDiagnosticHandler(<br>
> + [](const DiagnosticInfo &DI, void *Context) {<br>
> + if (DI.getSeverity() == DS_Error) {<br>
> + bool *HasError = static_cast<bool *>(Context);<br>
> + *HasError = true;<br>
> + }<br>
> +<br>
> + auto *Remark = dyn_cast<<wbr>DiagnosticInfoOptimizationBase<wbr>>(&DI);<br>
> + if (Remark && !Remark->isEnabled())<br>
> + return;<br>
> +<br>
> + DiagnosticPrinterRawOStream DP(errs());<br>
> + errs() << LLVMContext::<wbr>getDiagnosticMessagePrefix(DI.<wbr>getSeverity());<br>
> + errs() << ": ";<br>
> + DI.print(DP);<br>
> + errs() << "\n";<br>
> + },<br>
> + &HasError);<br>
> +<br>
> + SMDiagnostic Err;<br>
> + auto MIR = createMIRParserFromFile(<wbr>InputFilename, Err, Context);<br>
> + auto M = MIR ? MIR->parseIRModule() : nullptr;<br>
> +<br>
> + CANON_CHECK(M, argv[0] + "Invalid Module or MIR.");<br>
> +<br>
> + if (!TargetTriple.empty())<br>
> + M->setTargetTriple(Triple::<wbr>normalize(TargetTriple));<br>
> +<br>
> + Triple TheTriple = Triple(M->getTargetTriple());<br>
> + if (TheTriple.getTriple().empty()<wbr>)<br>
> + TheTriple.setTriple(sys::<wbr>getDefaultTargetTriple());<br>
> +<br>
> + // Get the target specific parser.<br>
> + std::string Error;<br>
> + const Target *TheTarget =<br>
> + TargetRegistry::lookupTarget(<wbr>MArch, TheTriple, Error);<br>
> +<br>
> + CANON_CHECK(TheTarget, argv[0] + ": " + Error);<br>
> +<br>
> + std::string CPUStr = getCPUStr();<br>
> + std::string FeaturesStr = getFeaturesStr();<br>
> +<br>
> + std::unique_ptr<TargetMachine> Target(TheTarget-><wbr>createTargetMachine(<br>
> + TheTriple.getTriple(), CPUStr, FeaturesStr,<br>
> + InitTargetOptionsFromCodeGenFl<wbr>ags(), getRelocModel(), getCodeModel(),<br>
> + CodeGenOpt::Default));<br>
> +<br>
> + CANON_CHECK(Target, "Could not allocate target machine!");<br>
> +<br>
> + std::error_code EC;<br>
> + auto Out = llvm::make_unique<tool_output_<wbr>file>(OutputFilename, EC,<br>
> + sys::fs::F_Text);<br>
> + CANON_CHECK(!EC, EC.message());<br>
> + raw_pwrite_stream *OS = &Out->os();<br>
> +<br>
> + legacy::PassManager PM;<br>
> + TargetLibraryInfoImpl TLII(Triple(M-><wbr>getTargetTriple()));<br>
> + PM.add(new TargetLibraryInfoWrapperPass(<wbr>TLII));<br>
> + M->setDataLayout(Target-><wbr>createDataLayout());<br>
> + setFunctionAttributes(CPUStr, FeaturesStr, *M);<br>
> +<br>
> + LLVMTargetMachine &TM = static_cast<LLVMTargetMachine &>(*Target);<br>
> + TargetPassConfig &TPC = *TM.createPassConfig(PM);<br>
> + PM.add(&TPC);<br>
> + MachineModuleInfo *MMI = new MachineModuleInfo(&TM);<br>
> + PM.add(MMI);<br>
> + TPC.printAndVerify("");<br>
> +<br>
> + StringRef PassName = "mir-canonicalizer";<br>
> + const PassRegistry *PR = PassRegistry::getPassRegistry(<wbr>);<br>
> + const PassInfo *PI = PR->getPassInfo(PassName);<br>
> +<br>
> + CANON_CHECK(PI, argv[0] + ": " + PI->getPassName() + " not registered.");<br>
> + CANON_CHECK(PI->getNormalCtor(<wbr>),<br>
> + argv[0] + ": can't create pass: " + PI->getPassName());<br>
> +<br>
> + Pass *P = PI->getNormalCtor()();<br>
> + PM.add(P);<br>
> + TPC.printAndVerify(std::<wbr>string("After ") + std::string(P->getPassName()))<wbr>;<br>
> +<br>
> + PM.add(createPrintMIRPass(*OS)<wbr>);<br>
> +<br>
> + // Before executing passes, print the final values of the LLVM options.<br>
> + cl::PrintOptionValues();<br>
> +<br>
> + PM.run(*M);<br>
> +<br>
> + CANON_CHECK(!(*static_cast<<wbr>bool *>(Context.<wbr>getDiagnosticContext())),<br>
> + argv[0] + " Error: exiting...");<br>
> +<br>
> + Out->keep();<br>
> + return 0;<br>
> +}<br>
> +<br>
><br>
> ______________________________<wbr>_________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br>
</blockquote></div><br></div></div>