From 3b67c8d0f7c6a15d802c6db377af7a57e39d67ba Mon Sep 17 00:00:00 2001 From: Chad Rosier Date: Tue, 10 Mar 2015 16:22:52 +0000 Subject: [PATCH] [BranchFolding] Remove MMOs during tail merge to preserve dependencies. When tail merging it may be necessary to remove MMOs from memory operations to ensures later passes (e.g., MI sched) conservatively compute dependencies. Currently, we only remove the MMO from the common tail if the MMO doesn't match with the relative instruction in the non-common tail(s). A more robust solution would be to add multiple MMOs from the duplicate MIs to the new MI. Currently ScheduleDAGInstrs.cpp ignores all MMOs on instructions with multiple MMOs, so this solution is equivalent for the time being. No test case included as this is incredibly difficult to reproduce. Patch was a collaborative effort between Ana Pazos and myself. Phabricator: http://reviews.llvm.org/D7769 llvm-svn: 231799 --- llvm/include/llvm/CodeGen/MachineInstr.h | 6 +++ llvm/include/llvm/CodeGen/MachineMemOperand.h | 18 +++++++++ llvm/lib/CodeGen/BranchFolding.cpp | 57 +++++++++++++++++++++++++++ 3 files changed, 81 insertions(+) diff --git a/llvm/include/llvm/CodeGen/MachineInstr.h b/llvm/include/llvm/CodeGen/MachineInstr.h index c876e4b..f9cdbf0 100644 --- a/llvm/include/llvm/CodeGen/MachineInstr.h +++ b/llvm/include/llvm/CodeGen/MachineInstr.h @@ -1169,6 +1169,12 @@ public: assert(NumMemRefs == NewMemRefsEnd - NewMemRefs && "Too many memrefs"); } + /// clearMemRefs - Clear this MachineInstr's memory reference descriptor list. + void clearMemRefs() { + MemRefs = nullptr; + NumMemRefs = 0; + } + private: /// getRegInfo - If this instruction is embedded into a MachineFunction, /// return the MachineRegisterInfo object for the current function, otherwise diff --git a/llvm/include/llvm/CodeGen/MachineMemOperand.h b/llvm/include/llvm/CodeGen/MachineMemOperand.h index eb5086c..a16c294 100644 --- a/llvm/include/llvm/CodeGen/MachineMemOperand.h +++ b/llvm/include/llvm/CodeGen/MachineMemOperand.h @@ -199,6 +199,24 @@ public: /// Profile - Gather unique data for the object. /// void Profile(FoldingSetNodeID &ID) const; + + friend bool operator==(const MachineMemOperand &LHS, + const MachineMemOperand &RHS) { + return LHS.getValue() == RHS.getValue() && + LHS.getPseudoValue() == RHS.getPseudoValue() && + LHS.getSize() == RHS.getSize() && + LHS.getOffset() == RHS.getOffset() && + LHS.getFlags() == RHS.getFlags() && + LHS.getAAInfo() == RHS.getAAInfo() && + LHS.getRanges() == RHS.getRanges() && + LHS.getAlignment() == RHS.getAlignment() && + LHS.getAddrSpace() == RHS.getAddrSpace(); + } + + friend bool operator!=(const MachineMemOperand &LHS, + const MachineMemOperand &RHS) { + return !(LHS == RHS); + } }; raw_ostream &operator<<(raw_ostream &OS, const MachineMemOperand &MRO); diff --git a/llvm/lib/CodeGen/BranchFolding.cpp b/llvm/lib/CodeGen/BranchFolding.cpp index b8f05cd..05bf31b 100644 --- a/llvm/lib/CodeGen/BranchFolding.cpp +++ b/llvm/lib/CodeGen/BranchFolding.cpp @@ -24,6 +24,7 @@ #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineJumpTableInfo.h" +#include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" @@ -727,6 +728,60 @@ bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, return true; } +static bool hasIdenticalMMOs(const MachineInstr *MI1, const MachineInstr *MI2) { + auto I1 = MI1->memoperands_begin(), E1 = MI1->memoperands_end(); + auto I2 = MI2->memoperands_begin(), E2 = MI2->memoperands_end(); + if ((E1 - I1) != (E2 - I2)) + return false; + for (; I1 != E1; ++I1, ++I2) { + if (**I1 != **I2) + return false; + } + return true; +} + +static void +removeMMOsFromMemoryOperations(MachineBasicBlock::iterator MBBIStartPos, + MachineBasicBlock &MBBCommon) { + // Remove MMOs from memory operations in the common block + // when they do not match the ones from the block being tail-merged. + // This ensures later passes conservatively compute dependencies. + MachineBasicBlock *MBB = MBBIStartPos->getParent(); + // Note CommonTailLen does not necessarily matches the size of + // the common BB nor all its instructions because of debug + // instructions differences. + unsigned CommonTailLen = 0; + for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos) + ++CommonTailLen; + + MachineBasicBlock::reverse_iterator MBBI = MBB->rbegin(); + MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin(); + MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend(); + + while (CommonTailLen--) { + assert(MBBI != MBB->rend() && "Reached BB end within common tail length!"); + + if (MBBI->isDebugValue()) { + ++MBBI; + continue; + } + + while ((MBBICommon != MBBIECommon) && MBBICommon->isDebugValue()) + ++MBBICommon; + + assert(MBBICommon != MBBIECommon && + "Reached BB end within common tail length!"); + assert(MBBICommon->isIdenticalTo(&*MBBI) && "Expected matching MIIs!"); + + if (MBBICommon->mayLoad() || MBBICommon->mayStore()) + if (!hasIdenticalMMOs(&*MBBI, &*MBBICommon)) + MBBICommon->clearMemRefs(); + + ++MBBI; + ++MBBICommon; + } +} + // See if any of the blocks in MergePotentials (which all have a common single // successor, or all have no successor) can be tail-merged. If there is a // successor, any blocks in MergePotentials that are not tail-merged and @@ -840,6 +895,8 @@ bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB, continue; DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber() << (i == e-1 ? "" : ", ")); + // Remove MMOs from memory operations as needed. + removeMMOsFromMemoryOperations(SameTails[i].getTailStartPos(), *MBB); // Hack the end off BB i, making it jump to BB commonTailIndex instead. ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB); // BB i is no longer a predecessor of SuccBB; remove it from the worklist. -- 2.7.4