Index: include/llvm/MC/MCAsmBackend.h =================================================================== --- include/llvm/MC/MCAsmBackend.h +++ include/llvm/MC/MCAsmBackend.h @@ -19,22 +19,33 @@ namespace llvm { +class MachineBasicBlock; +class MachineFunction; +class MachineLoopInfo; class MCAsmLayout; class MCAssembler; class MCCFIInstruction; +class MCCodePadder; struct MCFixupKindInfo; class MCFragment; class MCInst; +class MCObjectStreamer; class MCObjectWriter; +class MCPaddingFragment; class MCRelaxableFragment; class MCSubtargetInfo; class MCValue; class raw_pwrite_stream; +class TargetMachine; /// Generic interface to target specific assembler backends. class MCAsmBackend { + MCCodePadder *CodePadder; + MCCodePadder *getCodePadder(); + protected: // Can only create subclasses. MCAsmBackend(); + virtual MCCodePadder *createCodePadder(); public: MCAsmBackend(const MCAsmBackend &) = delete; @@ -134,6 +145,47 @@ generateCompactUnwindEncoding(ArrayRef) const { return 0; } + + /// Handles all target related code padding when starting to write a new + /// function to an object file. + /// + /// \param MF The function. + /// \param OS The streamer used for writing the padding data and function. + /// \param TM Target machine information. + /// \param LI Loop info for the starting function. + void handleCodePaddingFunctionStart(const MachineFunction &MF, + MCObjectStreamer *OS, + const TargetMachine &TM, + const MachineLoopInfo &LI); + /// Handles all target related code padding cleanup when done writing a + /// function to an object file. + /// + /// \param MF The function. + void handleCodePaddingFunctionEnd(const MachineFunction &MF); + /// Handles all target related code padding when starting to write a new + /// basic block to an object file. + /// + /// \param BB the basic block. + void handleCodePaddingBasicBlockStart(const MachineBasicBlock &MBB); + /// Handles all target related code padding before writing a new instruction + /// to an object file. + /// + /// \param Inst the instruction. + void handleCodePaddingInstructionBegin(const MCInst &Inst); + /// Handles all target related code padding after writing an instruction to an + /// object file. + /// + /// \param Inst the instruction. + void handleCodePaddingInstructionEnd(const MCInst &Inst); + + /// Relaxes a fragment (changes the size of the padding) according to target + /// requirements. The new size computation is done w.r.t a layout. + /// + /// \param Fragment The fragment to relax. + /// \param Layout Code layout information. + /// + /// \returns true iff any relaxation occured. + bool relaxFragment(MCPaddingFragment *PF, MCAsmLayout &Layout); }; } // end namespace llvm Index: include/llvm/MC/MCAssembler.h =================================================================== --- include/llvm/MC/MCAssembler.h +++ include/llvm/MC/MCAssembler.h @@ -183,6 +183,8 @@ bool relaxInstruction(MCAsmLayout &Layout, MCRelaxableFragment &IF); + bool relaxPaddingFragment(MCAsmLayout &Layout, MCPaddingFragment &PF); + bool relaxLEB(MCAsmLayout &Layout, MCLEBFragment &IF); bool relaxDwarfLineAddr(MCAsmLayout &Layout, MCDwarfLineAddrFragment &DF); Index: include/llvm/MC/MCCodePadder.h =================================================================== --- include/llvm/MC/MCCodePadder.h +++ include/llvm/MC/MCCodePadder.h @@ -0,0 +1,246 @@ +//===- llvm/MC/CodePadder.h - MC Code Padder --------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_MC_MCCODEPADDER_H +#define LLVM_MC_MCCODEPADDER_H + +#include "llvm/ADT/SmallVector.h" +#include +#include + +namespace llvm { + +class MachineBasicBlock; +class MachineFunction; +class MachineLoopInfo; +class MCAsmLayout; +class MCCodePaddingPolicy; +class MCFragment; +class MCInst; +class MCObjectStreamer; +class MCPaddingFragment; +class MCSection; +class TargetMachine; + +typedef SmallVector MCPFRange; + +/// Target-independent base class incharge of all code padding decisions for a +/// target. During encoding it determines if and where MCPaddingFragments will +/// be located, as later on, when layout information is available, it determines +/// their sizes. +class MCCodePadder { + MCCodePadder(const MCCodePadder &) = delete; + void operator=(const MCCodePadder &) = delete; + + /// All the supported MCCodePaddingPolicies. + std::unordered_set PaddingPolicies; + + /// All the MCSections that are not expected to change, e.g. by adding or + /// deleting MCFragments from them. + std::unordered_set SealedSections; + /// Unseals a sealed section. + void unsealSection(MCSection *Sec); + + /// A pointer to the fragment of the instruction whose padding is currently + /// done for. + MCPaddingFragment *CurrHandledInstFragment; + + /// A map holding the jurisdiction for each padding fragment. Key: padding + /// fragment. Value: The fragment's jurisdiction. A jurisdiction is a vector + /// of padding fragments whose conditions are being controlled by another + /// fragment, the key fragment. + std::unordered_map FragmentToJurisdiction; + MCPFRange &getJurisdiction(MCPaddingFragment *Fragment, MCAsmLayout &Layout); + + /// A map holding the maximal instruction window size relevant for a padding + /// fragment. + std::unordered_map FragmentToMaxWindowSize; + uint64_t getMaxWindowSize(MCPaddingFragment *Fragment, MCAsmLayout &Layout); + +protected: + /// The current streamer, used to stream code padding. + MCObjectStreamer *OS; + + const MachineLoopInfo *LI; + + /// Determines if the MCCodePaddingPolicies are active. + bool ArePoliciesActive; + + bool addPolicy(MCCodePaddingPolicy *Policy); + + virtual bool requiresInsertionPoint(const MachineBasicBlock &MBB) { + return false; + } + + virtual bool requiresInsertionPoint(const MCInst &Inst) { return false; } + +public: + MCCodePadder() + : CurrHandledInstFragment(nullptr), OS(nullptr), LI(nullptr), + ArePoliciesActive(false) {} + virtual ~MCCodePadder(); + + /// Handles all target related code padding when starting to write a new + /// function to an object file. + /// + /// \param MF The function. + /// \param OS The streamer used for writing the padding data and function. + /// \param TM Target machine information. + /// \param LI Loop info for the starting function. + virtual void handleFunctionStart(const MachineFunction &MF, + MCObjectStreamer *OS, + const TargetMachine &TM, + const MachineLoopInfo &LI); + /// Handles all target related code padding cleanup when done writing a + /// function to an object file. + /// + /// \param MF The function. + virtual void handleFunctionEnd(const MachineFunction &MF); + /// Handles all target related code padding when starting to write a new + /// basic block to an object file. + /// + /// \param BB the basic block. + virtual void handleBasicBlockStart(const MachineBasicBlock &MBB); + /// Handles all target related code padding before writing a new instruction + /// to an object file. + /// + /// \param Inst the instruction. + void handleInstructionBegin(const MCInst &Inst); + /// Handles all target related code padding after writing an instruction to an + /// object file. + /// + /// \param Inst the instruction. + void handleInstructionEnd(const MCInst &Inst); + + /// Relaxes a fragment (changes the size of the padding) according to target + /// requirements. The new size computation is done w.r.t a layout. + /// + /// \param Fragment The fragment to relax. + /// \param Layout Code layout information. + /// + /// \returns true iff any relaxation occured. + bool relaxFragment(MCPaddingFragment *Fragment, MCAsmLayout &Layout); +}; + +/// The base class for all padding policies, i.e. a rule or set of rules to pad +/// the generated code. +class MCCodePaddingPolicy { + MCCodePaddingPolicy() = delete; + MCCodePaddingPolicy(const MCCodePaddingPolicy &) = delete; + void operator=(const MCCodePaddingPolicy &) = delete; + +protected: + /// A mask holding the kind of this policy, i.e. only the i'th bit will be set + /// where i is the kind number. + const uint64_t KindMask; + /// Instruction window size relevant to this policy. + const uint64_t WindowSize; + /// A boolean indicating which byte of the instruction determies its + /// instruction window. If true - the last byte of the instructions, o.w. - + /// the first byte of the instruction. + const bool InstByteIsLastByte; + + MCCodePaddingPolicy(uint64_t Kind, uint64_t WindowSize, + bool InstByteIsLastByte) + : KindMask(UINT64_C(1) << Kind), WindowSize(WindowSize), + InstByteIsLastByte(InstByteIsLastByte) {} + + /// Computes and returns the offset of the consecutive fragment of a given + /// fragment. + /// + /// \param Fragment The fragment whose consecutive offset will be computed. + /// \param Layout Code layout information. + /// + /// \returns the offset of the consecutive fragment of \p Fragment. + static uint64_t getNextFragmentOffset(const MCFragment *Fragment, + const MCAsmLayout &Layout); + /// Returns the instruction byte of an instruction pointed by a given + /// MCPaddingFragment. An instruction byte is the address of the byte of an + /// instruction which determines its instruction window. + /// + /// \param Fragment The fragment pointing to the instruction. + /// \param Layout Code layout information. + /// + /// \returns the instruction byte of an instruction pointed by \p Fragment. + uint64_t getFragmentInstByte(const MCPaddingFragment *Fragment, + MCAsmLayout &Layout) const; + uint64_t computeWindowEndAddress(const MCPaddingFragment *Fragment, + uint64_t Offset, MCAsmLayout &Layout) const; + + /// Computes and returns the penalty weight of a first instruction window in a + /// range. This requires a special function since the first window does not + /// contain all the padding fragments in that window. It only contains all the + /// padding fragments starting from the relevant insertion point. + /// + /// \param Window The first window. + /// \param Offset The offset of the parent section relative to the beginning + /// of the file, mod the window size. + /// \param Layout Code layout information. + /// + /// \returns the penalty weight of a first instruction window in a range, \p + /// Window. + double computeFirstWindowPenaltyWeight(const MCPFRange &Window, + uint64_t Offset, + MCAsmLayout &Layout) const; + /// Computes and returns the penalty caused by an instruction window. + /// + /// \param Window The instruction window. + /// \param Offset The offset of the parent section relative to the beginning + /// of the file, mod the window size. + /// \param Layout Code layout information. + /// + /// \returns the penalty caused by \p Window. + virtual double computeWindowPenaltyWeight(const MCPFRange &Window, + uint64_t Offset, + MCAsmLayout &Layout) const = 0; + +public: + virtual ~MCCodePaddingPolicy() {} + + /// Returns the kind mask of this policy - A mask holding the kind of this + /// policy, i.e. only the i'th bit will be set where i is the kind number. + uint64_t getKindMask() const { return KindMask; } + /// Returns the instruction window size relevant to this policy. + uint64_t getWindowSize() const { return WindowSize; } + /// Returns true if the last byte of an instruction determines its instruction + /// window, or false if the first of an instruction determines it. + bool isInstByteLastByte() const { return InstByteIsLastByte; } + + /// Returns true iff this policy needs padding for a given basic block. + /// + /// \param MBB The given basic block. + /// + /// \returns true iff this policy needs padding for \p MBB. + virtual bool requiresPaddingFragment(const MachineBasicBlock &MBB) const { + return false; + } + /// Returns true iff this policy needs padding for a given instruction. + /// + /// \param Inst The given instruction. + /// + /// \returns true iff this policy needs padding for \p Inst. + virtual bool requiresPaddingFragment(const MCInst &Inst) const { + return false; + } + /// Computes and returns the penalty caused by a range of instruction windows. + /// The weight is computed for each window separelty and then accumulated. + /// + /// \param Range The range. + /// \param Offset The offset of the parent section relative to the beginning + /// of the file, mod the window size. + /// \param Layout Code layout information. + /// + /// \returns the penalty caused by \p Range. + double computeRangePenaltyWeight(const MCPFRange &Range, uint64_t Offset, + MCAsmLayout &Layout) const; +}; + +} // namespace llvm + +#endif // LLVM_MC_MCCODEPADDER_H Index: include/llvm/MC/MCFragment.h =================================================================== --- include/llvm/MC/MCFragment.h +++ include/llvm/MC/MCFragment.h @@ -41,6 +41,7 @@ FT_Dwarf, FT_DwarfFrame, FT_LEB, + FT_Padding, FT_SafeSEH, FT_CVInlineLines, FT_CVDefRange, @@ -323,6 +324,93 @@ } }; +class MCPaddingFragment : public MCFragment { + /// A mask containing all the kinds relevant to this fragment. i.e. the i'th + /// bit will be set iff kind i is relevant to this fragment. + uint64_t PaddingPoliciesMask; + /// A boolean indicating if this fragment will actually hold padding. If its + /// value is false, then this fragment serves only as a placeholder, + /// containing data to assist other insertion point in their decision making. + bool IsInsertionPoint; + + uint64_t Size; + + typedef struct { + bool IsInitialized; + MCInst Inst; + /// A boolean indicating whether the instruction pointed by this fragment is + /// a fixed size instruction or a relaxable instruction held by a + /// MCRelaxableFragment. + bool IsImmutableSizedInst; + union { + /// If the instruction is a fixed size instruction, hold its size. + size_t InstSize; + /// Otherwise, hold a pointer to the MCRelaxableFragment holding it. + MCRelaxableFragment *InstFragment; + }; + } MCInstInfo; + MCInstInfo InstInfo; + +public: + static const uint64_t PFK_None = UINT64_C(0); + + enum MCPaddingFragmentKind { + // values 0-7 are reserved for future target independet values. + + FirstTargetPerfNopFragmentKind = 8, + + /// Limit range of target MCPerfNopFragment kinds to fit in uint64_t + MaxTargetPerfNopFragmentKind = 63 + }; + + MCPaddingFragment(MCSection *Sec = nullptr) + : MCFragment(FT_Padding, false, 0, Sec), PaddingPoliciesMask(PFK_None), + IsInsertionPoint(false), Size(UINT64_C(0)), + InstInfo({false, MCInst(), false, {0}}) {} + + bool isInsertionPoint() const { return IsInsertionPoint; } + void setAsInsertionPoint() { IsInsertionPoint = true; } + uint64_t getPaddingPoliciesMask() const { return PaddingPoliciesMask; } + void setPaddingPoliciesMask(uint64_t Value) { PaddingPoliciesMask = Value; } + bool hasPaddingPolicy(uint64_t PolicyMask) const { + assert(isPowerOf2_64(PolicyMask) && + "Policy mask must contain exactly one policy"); + return (getPaddingPoliciesMask() & PolicyMask) != PFK_None; + } + const MCInst &getInst() const { + assert(isInstructionInitialized() && "Fragment has no instruction!"); + return InstInfo.Inst; + } + size_t getInstSize() const { + assert(isInstructionInitialized() && "Fragment has no instruction!"); + if (InstInfo.IsImmutableSizedInst) + return InstInfo.InstSize; + assert(InstInfo.InstFragment != nullptr && + "Must have a valid InstFragment to retrieve InstSize from"); + return InstInfo.InstFragment->getContents().size(); + } + void setInstAndInstSize(const MCInst &Inst, size_t InstSize) { + InstInfo.IsInitialized = true; + InstInfo.IsImmutableSizedInst = true; + InstInfo.Inst = Inst; + InstInfo.InstSize = InstSize; + } + void setInstAndInstFragment(const MCInst &Inst, + MCRelaxableFragment *InstFragment) { + InstInfo.IsInitialized = true; + InstInfo.IsImmutableSizedInst = false; + InstInfo.Inst = Inst; + InstInfo.InstFragment = InstFragment; + } + uint64_t getSize() const { return Size; } + void setSize(uint64_t Value) { Size = Value; } + bool isInstructionInitialized() const { return InstInfo.IsInitialized; } + + static bool classof(const MCFragment *F) { + return F->getKind() == MCFragment::FT_Padding; + } +}; + class MCFillFragment : public MCFragment { /// Value to use for filling bytes. uint8_t Value; Index: include/llvm/MC/MCObjectStreamer.h =================================================================== --- include/llvm/MC/MCObjectStreamer.h +++ include/llvm/MC/MCObjectStreamer.h @@ -16,6 +16,9 @@ #include "llvm/MC/MCStreamer.h" namespace llvm { +class MachineBasicBlock; +class MachineFunction; +class MachineLoopInfo; class MCAssembler; class MCCodeEmitter; class MCSubtargetInfo; @@ -25,6 +28,7 @@ class MCAsmBackend; class raw_ostream; class raw_pwrite_stream; +class TargetMachine; /// \brief Streaming object file generation interface. /// @@ -43,6 +47,7 @@ virtual void EmitInstToData(const MCInst &Inst, const MCSubtargetInfo&) = 0; void EmitCFIStartProcImpl(MCDwarfFrameInfo &Frame) override; void EmitCFIEndProcImpl(MCDwarfFrameInfo &Frame) override; + void EmitInstructionImpl(const MCInst &Inst, const MCSubtargetInfo &STI); protected: MCObjectStreamer(MCContext &Context, MCAsmBackend &TAB, raw_pwrite_stream &OS, @@ -71,6 +76,7 @@ /// Get a data fragment to write into, creating a new one if the current /// fragment is not a data fragment. MCDataFragment *getOrCreateDataFragment(); + MCPaddingFragment *getOrCreatePaddingFragment(); protected: bool changeSectionImpl(MCSection *Section, const MCExpr *Subsection); @@ -116,6 +122,11 @@ unsigned MaxBytesToEmit = 0) override; void emitValueToOffset(const MCExpr *Offset, unsigned char Value, SMLoc Loc) override; + void EmitCodePaddingFunctionStart(const TargetMachine &TM, + const MachineFunction &MF, + const MachineLoopInfo &LI) override; + void EmitCodePaddingFunctionEnd(const MachineFunction &MF) override; + void EmitCodePaddingBasicBlockStart(const MachineBasicBlock &MBB) override; void EmitDwarfLocDirective(unsigned FileNo, unsigned Line, unsigned Column, unsigned Flags, unsigned Isa, unsigned Discriminator, Index: include/llvm/MC/MCStreamer.h =================================================================== --- include/llvm/MC/MCStreamer.h +++ include/llvm/MC/MCStreamer.h @@ -35,6 +35,9 @@ class AssemblerConstantPools; class formatted_raw_ostream; +class MachineBasicBlock; +class MachineFunction; +class MachineLoopInfo; class MCAsmBackend; class MCCodeEmitter; class MCContext; @@ -46,6 +49,7 @@ class MCSymbolRefExpr; class MCSubtargetInfo; class raw_ostream; +class TargetMachine; class Twine; using MCSectionSubPair = std::pair; @@ -705,6 +709,14 @@ virtual void emitValueToOffset(const MCExpr *Offset, unsigned char Value, SMLoc Loc); + virtual void EmitCodePaddingFunctionStart(const TargetMachine &TM, + const MachineFunction &MF, + const MachineLoopInfo &LI) {} + + virtual void EmitCodePaddingFunctionEnd(const MachineFunction &MF) {} + + virtual void EmitCodePaddingBasicBlockStart(const MachineBasicBlock &MBB) {} + /// @} /// \brief Switch to a new logical file. This is used to implement the '.file Index: lib/CodeGen/AsmPrinter/AsmPrinter.cpp =================================================================== --- lib/CodeGen/AsmPrinter/AsmPrinter.cpp +++ lib/CodeGen/AsmPrinter/AsmPrinter.cpp @@ -221,8 +221,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - if (isVerbose()) - AU.addRequired(); + AU.addRequired(); } bool AsmPrinter::doInitialization(Module &M) { @@ -966,6 +965,7 @@ /// function. void AsmPrinter::EmitFunctionBody() { EmitFunctionHeader(); + OutStreamer->EmitCodePaddingFunctionStart(TM, *MF, *LI); // Emit target-specific gunk before the function body. EmitFunctionBodyStart(); @@ -1123,6 +1123,8 @@ HI.Handler->endFunction(MF); } + OutStreamer->EmitCodePaddingFunctionEnd(*MF); + if (isVerbose()) OutStreamer->GetCommentOS() << "-- End function\n"; @@ -1418,8 +1420,7 @@ } ORE = &getAnalysis().getORE(); - if (isVerbose()) - LI = &getAnalysis(); + LI = &getAnalysis(); const TargetSubtargetInfo &STI = MF.getSubtarget(); EnablePrintSchedInfo = PrintSchedule.getNumOccurrences() @@ -2616,6 +2617,7 @@ // Emit an alignment directive for this block, if needed. if (unsigned Align = MBB.getAlignment()) EmitAlignment(Align); + OutStreamer->EmitCodePaddingBasicBlockStart(MBB); // If the block has its address taken, emit any labels that were used to // reference the block. It is possible that there is more than one label Index: lib/MC/CMakeLists.txt =================================================================== --- lib/MC/CMakeLists.txt +++ lib/MC/CMakeLists.txt @@ -10,6 +10,7 @@ MCAsmStreamer.cpp MCAssembler.cpp MCCodeEmitter.cpp + MCCodePadder.cpp MCCodeView.cpp MCContext.cpp MCDwarf.cpp Index: lib/MC/MCAsmBackend.cpp =================================================================== --- lib/MC/MCAsmBackend.cpp +++ lib/MC/MCAsmBackend.cpp @@ -10,6 +10,7 @@ #include "llvm/MC/MCAsmBackend.h" #include "llvm/ADT/None.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/MC/MCCodePadder.h" #include "llvm/MC/MCFixupKindInfo.h" #include #include @@ -17,10 +18,18 @@ using namespace llvm; -MCAsmBackend::MCAsmBackend() = default; +MCAsmBackend::MCAsmBackend() : CodePadder(nullptr) {} -MCAsmBackend::~MCAsmBackend() = default; +MCAsmBackend::~MCAsmBackend() { delete CodePadder; } +MCCodePadder *MCAsmBackend::getCodePadder() { + if (CodePadder == nullptr) + CodePadder = createCodePadder(); + return CodePadder; +} + +MCCodePadder *MCAsmBackend::createCodePadder() { return new MCCodePadder(); } + Optional MCAsmBackend::getFixupKind(StringRef Name) const { return None; } @@ -59,3 +68,31 @@ return true; return fixupNeedsRelaxation(Fixup, Value, DF, Layout); } + +void MCAsmBackend::handleCodePaddingFunctionStart(const MachineFunction &MF, + MCObjectStreamer *OS, + const TargetMachine &TM, + const MachineLoopInfo &LI) { + getCodePadder()->handleFunctionStart(MF, OS, TM, LI); +} + +void MCAsmBackend::handleCodePaddingFunctionEnd(const MachineFunction &MF) { + getCodePadder()->handleFunctionEnd(MF); +} + +void MCAsmBackend::handleCodePaddingBasicBlockStart( + const MachineBasicBlock &MBB) { + getCodePadder()->handleBasicBlockStart(MBB); +} + +void MCAsmBackend::handleCodePaddingInstructionBegin(const MCInst &Inst) { + getCodePadder()->handleInstructionBegin(Inst); +} + +void MCAsmBackend::handleCodePaddingInstructionEnd(const MCInst &Inst) { + getCodePadder()->handleInstructionEnd(Inst); +} + +bool MCAsmBackend::relaxFragment(MCPaddingFragment *PF, MCAsmLayout &Layout) { + return getCodePadder()->relaxFragment(PF, Layout); +} \ No newline at end of file Index: lib/MC/MCAssembler.cpp =================================================================== --- lib/MC/MCAssembler.cpp +++ lib/MC/MCAssembler.cpp @@ -68,6 +68,10 @@ STATISTIC(ObjectBytes, "Number of emitted object file bytes"); STATISTIC(RelaxationSteps, "Number of assembler layout and relaxation steps"); STATISTIC(RelaxedInstructions, "Number of relaxed instructions"); +STATISTIC(PaddingFragmentsRelaxations, + "Number of Padding Fragments relaxations"); +STATISTIC(PaddingFragmentsBytes, + "Total size of all padding from adding Fragments"); } // end namespace stats } // end anonymous namespace @@ -275,6 +279,9 @@ case MCFragment::FT_LEB: return cast(F).getContents().size(); + case MCFragment::FT_Padding: + return cast(F).getSize(); + case MCFragment::FT_SafeSEH: return 4; @@ -541,6 +548,13 @@ break; } + case MCFragment::FT_Padding: { + if (!Asm.getBackend().writeNopData(FragmentSize, OW)) + report_fatal_error("unable to write nop sequence of " + + Twine(FragmentSize) + " bytes"); + break; + } + case MCFragment::FT_SafeSEH: { const MCSafeSEHFragment &SF = cast(F); OW->write32(SF.getSymbol()->getIndex()); @@ -814,6 +828,19 @@ return true; } +bool MCAssembler::relaxPaddingFragment(MCAsmLayout &Layout, + MCPaddingFragment &PF) { + uint64_t OldSize = PF.getSize(); + if (!getBackend().relaxFragment(&PF, Layout)) + return false; + uint64_t NewSize = PF.getSize(); + + ++stats::PaddingFragmentsRelaxations; + stats::PaddingFragmentsBytes += NewSize; + stats::PaddingFragmentsBytes -= OldSize; + return true; +} + bool MCAssembler::relaxLEB(MCAsmLayout &Layout, MCLEBFragment &LF) { uint64_t OldSize = LF.getContents().size(); int64_t Value; @@ -908,6 +935,11 @@ case MCFragment::FT_LEB: RelaxedFrag = relaxLEB(Layout, *cast(I)); break; + + case MCFragment::FT_Padding: + RelaxedFrag = relaxPaddingFragment(Layout, *cast(I)); + break; + case MCFragment::FT_CVInlineLines: RelaxedFrag = relaxCVInlineLineTable(Layout, *cast(I)); Index: lib/MC/MCCodePadder.cpp =================================================================== --- lib/MC/MCCodePadder.cpp +++ lib/MC/MCCodePadder.cpp @@ -0,0 +1,420 @@ +//===- MCCodePadder.cpp - Target MC Code Padder ---------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/MC/MCAsmLayout.h" +#include "llvm/MC/MCCodePadder.h" +#include "llvm/MC/MCObjectStreamer.h" +#include +#include +#include + +using namespace llvm; + +//--------------------------------------------------------------------------- +// MCCodePadder +// + +MCCodePadder::~MCCodePadder() { + for (auto *Policy : PaddingPolicies) + delete Policy; +} + +bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) { + assert(Policy && "Policy must be valid"); + return PaddingPolicies.insert(Policy).second; +} + +void MCCodePadder::unsealSection(MCSection *Sec) { + // remove Sec's fragment from FragmentToJurisdiction + for (auto It1 = FragmentToJurisdiction.begin(); + It1 != FragmentToJurisdiction.end();) { + if (It1->first->getParent() == Sec) + It1 = FragmentToJurisdiction.erase(It1); + else + ++It1; + } + // remove Sec's fragment from FragmentToMaxWindowSize + for (auto It2 = FragmentToMaxWindowSize.begin(); + It2 != FragmentToMaxWindowSize.end();) { + if (It2->first->getParent() == Sec) + It2 = FragmentToMaxWindowSize.erase(It2); + else + ++It2; + } + SealedSections.erase(Sec); +} + +void MCCodePadder::handleFunctionStart(const MachineFunction &MF, + MCObjectStreamer *OS, + const TargetMachine &TM, + const MachineLoopInfo &LI) { + assert(OS != nullptr && "OS must be valid"); + // If a section was previously marked as sealed, we did not expect it to + // change. If a function is being written to it, its changing. If we don't do + // anything, some of the data we've got will be out of date (e.g. the + // jurisdiction in FragmentToJurisdiction), so we must reset all of that out + // of date data. + if (SealedSections.find(OS->getCurrentSectionOnly()) != SealedSections.end()) + unsealSection(OS->getCurrentSectionOnly()); + this->OS = OS; + this->LI = &LI; +} + +void MCCodePadder::handleFunctionEnd(const MachineFunction &MF) { + this->OS = nullptr; + this->LI = nullptr; +} + +void MCCodePadder::handleBasicBlockStart(const MachineBasicBlock &MBB) { + assert(OS != nullptr && + "A call to handleFunctionStart with valid parameters must be made " + "before a call to handleBasicBlockStart"); + assert( + SealedSections.find(OS->getCurrentSectionOnly()) == + SealedSections.end() && + "Can't call handleBasicBlockStart after fragments creation is finished"); + + bool InsertionPoint = requiresInsertionPoint(MBB); + assert((!InsertionPoint || + OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) && + "Cannot insert padding nops right after an alignment fragment as it " + "will ruin the alignment"); + + uint64_t PoliciesMask = MCPaddingFragment::PFK_None; + if (ArePoliciesActive) { + PoliciesMask = std::accumulate( + PaddingPolicies.begin(), PaddingPolicies.end(), + MCPaddingFragment::PFK_None, + [&MBB](uint64_t Mask, const MCCodePaddingPolicy *Policy) -> uint64_t { + return Policy->requiresPaddingFragment(MBB) + ? (Mask | Policy->getKindMask()) + : Mask; + }); + } + + if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) { + MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment(); + if (InsertionPoint) + PaddingFragment->setAsInsertionPoint(); + PaddingFragment->setPaddingPoliciesMask( + PaddingFragment->getPaddingPoliciesMask() | PoliciesMask); + } +} + +void MCCodePadder::handleInstructionBegin(const MCInst &Inst) { + if (!OS) + return; // instruction was emitted outside a function + assert( + SealedSections.find(OS->getCurrentSectionOnly()) == + SealedSections.end() && + "Can't call handleInstructionBegin after fragments creation is finished"); + + assert(CurrHandledInstFragment == nullptr && "Can't start handling an " + "instruction while still " + "handling another instruction"); + + bool InsertionPoint = requiresInsertionPoint(Inst); + assert((!InsertionPoint || + OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) && + "Cannot insert padding nops right after an alignment fragment as it " + "will ruin the alignment"); + + uint64_t PoliciesMask = MCPaddingFragment::PFK_None; + if (ArePoliciesActive) { + PoliciesMask = std::accumulate( + PaddingPolicies.begin(), PaddingPolicies.end(), + MCPaddingFragment::PFK_None, + [&Inst](uint64_t Mask, const MCCodePaddingPolicy *Policy) -> uint64_t { + return Policy->requiresPaddingFragment(Inst) + ? (Mask | Policy->getKindMask()) + : Mask; + }); + } + MCFragment *CurrFragment = OS->getCurrentFragment(); + // CurrFragment can be a previously created MCPaddingFragment. If so, let's + // update it with the information we have, such as the instruction that it + // should point to. + bool needToUpdateCurrFragment = + CurrFragment != nullptr && + CurrFragment->getKind() == MCFragment::FT_Padding; + if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None || + needToUpdateCurrFragment) { + // temporarily holding the fragment as CurrHandledInstFragment, to be + // updated after the instruction will be written + CurrHandledInstFragment = OS->getOrCreatePaddingFragment(); + if (InsertionPoint) + CurrHandledInstFragment->setAsInsertionPoint(); + CurrHandledInstFragment->setPaddingPoliciesMask( + CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask); + } +} + +void MCCodePadder::handleInstructionEnd(const MCInst &Inst) { + if (!OS) + return; // instruction was emitted outside a function + assert( + SealedSections.find(OS->getCurrentSectionOnly()) == + SealedSections.end() && + "Can't call handleInstructionEnd after fragments creation is finished"); + if (CurrHandledInstFragment == nullptr) + return; + + if (ArePoliciesActive) { + MCFragment *InstFragment = OS->getCurrentFragment(); + if (MCDataFragment *InstDataFragment = + dyn_cast_or_null(InstFragment)) + // Inst is a fixed size instruction and was encoded into a MCDataFragment. + // Let the fragment hold it and its size. Its size is the current size of + // the data fragment, as the padding fragment was inserted right before it + // and nothing was written yet except Inst + CurrHandledInstFragment->setInstAndInstSize( + Inst, InstDataFragment->getContents().size()); + else if (MCRelaxableFragment *InstRelaxableFragment = + dyn_cast_or_null(InstFragment)) + // Inst may be relaxed and its size may vary. + // Let the fragment hold the instruction and the MCRelaxableFragment + // that's holding it. + CurrHandledInstFragment->setInstAndInstFragment(Inst, + InstRelaxableFragment); + else + llvm_unreachable("After encoding an instruction current fragment must be " + "either a MCDataFragment or a MCRelaxableFragment"); + } + + CurrHandledInstFragment = nullptr; +} + +MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment, + MCAsmLayout &Layout) { + std::unordered_map::iterator + JurisdictionLocation = FragmentToJurisdiction.find(Fragment); + if (JurisdictionLocation != FragmentToJurisdiction.end()) + return JurisdictionLocation->second; + + MCPFRange Jurisdiction; + + // Forward scanning the fragments in this section, starting from the given + // fragments, and adding relevant MCPaddingFragments to the Jurisdiction + for (MCFragment *CurrFragment = Fragment; CurrFragment != nullptr; + CurrFragment = CurrFragment->getNextNode()) { + + MCPaddingFragment *CurrPaddingFragment = + dyn_cast(CurrFragment); + if (CurrPaddingFragment == nullptr) + continue; + + if (CurrPaddingFragment != Fragment && + CurrPaddingFragment->isInsertionPoint()) + // Found next insertion point Fragment. From now on it's its jurisdiction. + break; + for (const auto *Policy : PaddingPolicies) { + if (CurrPaddingFragment->hasPaddingPolicy(Policy->getKindMask())) { + Jurisdiction.push_back(CurrPaddingFragment); + break; + } + } + } + + auto InsertionResult = + FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction)); + assert(InsertionResult.second && + "Insertion to FragmentToJurisdiction failed"); + return InsertionResult.first->second; +} + +uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment, + MCAsmLayout &Layout) { + std::unordered_map::iterator + MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment); + if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end()) + return MaxFragmentSizeLocation->second; + + MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout); + uint64_t JurisdictionMask = MCPaddingFragment::PFK_None; + for (const auto *Protege : Jurisdiction) + JurisdictionMask |= Protege->getPaddingPoliciesMask(); + + uint64_t MaxFragmentSize = UINT64_C(0); + for (const auto *Policy : PaddingPolicies) + if ((JurisdictionMask & Policy->getKindMask()) != + MCPaddingFragment::PFK_None) + MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize()); + + auto InsertionResult = + FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize)); + assert(InsertionResult.second && + "Insertion to FragmentToMaxWindowSize failed"); + return InsertionResult.first->second; +} + +bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment, + MCAsmLayout &Layout) { + SealedSections.insert(Fragment->getParent()); + if (!Fragment->isInsertionPoint()) + return false; + uint64_t OldSize = Fragment->getSize(); + + uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout); + if (MaxWindowSize == UINT64_C(0)) + return false; + assert(isPowerOf2_64(MaxWindowSize) && + "MaxWindowSize must be an integer power of 2"); + uint64_t SectionAlignment = Fragment->getParent()->getAlignment(); + assert(isPowerOf2_64(SectionAlignment) && + "SectionAlignment must be an integer power of 2"); + + MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout); + uint64_t OptimalSize = UINT64_C(0); + double OptimalWeight = std::numeric_limits::max(); + uint64_t MaxFragmentSize = MaxWindowSize - UINT16_C(1); + for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) { + Fragment->setSize(Size); + Layout.invalidateFragmentsFrom(Fragment); + double SizeWeight = 0.0; + // The section is guaranteed to be aligned to SectionAlignment, but that + // doesn't guarantee the exact section offset w.r.t. the policies window + // size. + // As a concrete example, the section could be aligned to 16B, but a + // policy's window size can be 32B. That means that the section actual start + // address can either be 0mod32 or 16mod32. The said policy will act + // differently for each case, so we need to take both into consideration. + for (uint64_t Offset = UINT64_C(0); Offset < MaxWindowSize; + Offset += SectionAlignment) { + double OffsetWeight = std::accumulate( + PaddingPolicies.begin(), PaddingPolicies.end(), 0.0, + [&Jurisdiction, &Offset, &Layout]( + double Weight, const MCCodePaddingPolicy *Policy) -> double { + double PolicyWeight = + Policy->computeRangePenaltyWeight(Jurisdiction, Offset, Layout); + assert(PolicyWeight >= 0.0 && "A penalty weight must be positive"); + return Weight + PolicyWeight; + }); + SizeWeight = std::max(SizeWeight, OffsetWeight); + } + if (SizeWeight < OptimalWeight) { + OptimalWeight = SizeWeight; + OptimalSize = Size; + } + if (OptimalWeight == 0.0) + break; + } + + Fragment->setSize(OptimalSize); + Layout.invalidateFragmentsFrom(Fragment); + return OldSize != OptimalSize; +} + +//--------------------------------------------------------------------------- +// MCCodePaddingPolicy +// + +uint64_t MCCodePaddingPolicy::getNextFragmentOffset(const MCFragment *Fragment, + const MCAsmLayout &Layout) { + assert(Fragment != nullptr && "Fragment cannot be null"); + MCFragment const *NextFragment = Fragment->getNextNode(); + return NextFragment == nullptr + ? Layout.getSectionAddressSize(Fragment->getParent()) + : Layout.getFragmentOffset(NextFragment); +} + +uint64_t +MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment, + MCAsmLayout &Layout) const { + uint64_t InstByte = getNextFragmentOffset(Fragment, Layout); + if (InstByteIsLastByte) + InstByte += Fragment->getInstSize() - UINT64_C(1); + return InstByte; +} + +uint64_t +MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment, + uint64_t Offset, + MCAsmLayout &Layout) const { + uint64_t InstByte = getFragmentInstByte(Fragment, Layout); + return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset; +} + +double MCCodePaddingPolicy::computeRangePenaltyWeight( + const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const { + + SmallVector Windows; + SmallVector::iterator CurrWindowLocation = Windows.end(); + for (const MCPaddingFragment *Fragment : Range) { + if (!Fragment->hasPaddingPolicy(getKindMask())) + continue; + uint64_t FragmentWindowEndAddress = + computeWindowEndAddress(Fragment, Offset, Layout); + if (CurrWindowLocation == Windows.end() || + FragmentWindowEndAddress != + computeWindowEndAddress(*CurrWindowLocation->begin(), Offset, + Layout)) { + // next window is starting + Windows.push_back(MCPFRange()); + CurrWindowLocation = Windows.end() - 1; + } + CurrWindowLocation->push_back(Fragment); + } + + if (Windows.empty()) + return 0.0; + + double RangeWeight = 0.0; + SmallVector::iterator I = Windows.begin(); + RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout); + ++I; + RangeWeight += std::accumulate( + I, Windows.end(), 0.0, + [this, &Layout, &Offset](double Weight, MCPFRange &Window) -> double { + return Weight += computeWindowPenaltyWeight(Window, Offset, Layout); + }); + return RangeWeight; +} + +double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight( + const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const { + if (Window.empty()) + return 0.0; + uint64_t WindowEndAddress = + computeWindowEndAddress(*Window.begin(), Offset, Layout); + + MCPFRange FullWindowFirstPart; // will hold all the fragments that are in the + // same window as the fragments in the given + // window but their penalty weight should not + // be added + for (const MCFragment *Fragment = (*Window.begin())->getPrevNode(); + Fragment != nullptr; Fragment = Fragment->getPrevNode()) { + const MCPaddingFragment *PaddingNopFragment = + dyn_cast(Fragment); + if (PaddingNopFragment == nullptr || + !PaddingNopFragment->hasPaddingPolicy(getKindMask())) + continue; + if (WindowEndAddress != + computeWindowEndAddress(PaddingNopFragment, Offset, Layout)) + break; + + FullWindowFirstPart.push_back(PaddingNopFragment); + } + + std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end()); + double FullWindowFirstPartWeight = + computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout); + + MCPFRange FullWindow( + FullWindowFirstPart); // will hold all the fragments that are in the + // same window as the fragments in the given + // window, whether their weight should be added + // or not + FullWindow.append(Window.begin(), Window.end()); + double FullWindowWeight = + computeWindowPenaltyWeight(FullWindow, Offset, Layout); + + assert(FullWindowWeight >= FullWindowFirstPartWeight && + "More fragments necessarily means bigger weight"); + return FullWindowWeight - FullWindowFirstPartWeight; +} Index: lib/MC/MCFragment.cpp =================================================================== --- lib/MC/MCFragment.cpp +++ lib/MC/MCFragment.cpp @@ -278,6 +278,9 @@ case FT_LEB: delete cast(this); return; + case FT_Padding: + delete cast(this); + return; case FT_SafeSEH: delete cast(this); return; @@ -322,6 +325,7 @@ case MCFragment::FT_Dwarf: OS << "MCDwarfFragment"; break; case MCFragment::FT_DwarfFrame: OS << "MCDwarfCallFrameFragment"; break; case MCFragment::FT_LEB: OS << "MCLEBFragment"; break; + case MCFragment::FT_Padding: OS << "MCPaddingFragment"; break; case MCFragment::FT_SafeSEH: OS << "MCSafeSEHFragment"; break; case MCFragment::FT_CVInlineLines: OS << "MCCVInlineLineTableFragment"; break; case MCFragment::FT_CVDefRange: OS << "MCCVDefRangeTableFragment"; break; @@ -417,6 +421,19 @@ OS << " Value:" << LF->getValue() << " Signed:" << LF->isSigned(); break; } + case MCFragment::FT_Padding: { + const MCPaddingFragment *F = cast(this); + OS << "\n "; + OS << " PaddingPoliciesMask:" << F->getPaddingPoliciesMask() + << " IsInsertionPoint:" << F->isInsertionPoint() + << " Size:" << F->getSize(); + OS << "\n "; + OS << " Inst:"; + F->getInst().dump_pretty(OS); + OS << " InstSize:" << F->getInstSize(); + OS << "\n "; + break; + } case MCFragment::FT_SafeSEH: { const MCSafeSEHFragment *F = cast(this); OS << "\n "; Index: lib/MC/MCObjectStreamer.cpp =================================================================== --- lib/MC/MCObjectStreamer.cpp +++ lib/MC/MCObjectStreamer.cpp @@ -111,6 +111,16 @@ return F; } +MCPaddingFragment *MCObjectStreamer::getOrCreatePaddingFragment() { + MCPaddingFragment *F = + dyn_cast_or_null(getCurrentFragment()); + if (!F) { + F = new MCPaddingFragment(); + insert(F); + } + return F; +} + void MCObjectStreamer::visitUsedSymbol(const MCSymbol &Sym) { Assembler->registerSymbol(Sym); } @@ -244,6 +254,13 @@ void MCObjectStreamer::EmitInstruction(const MCInst &Inst, const MCSubtargetInfo &STI, bool) { + getAssembler().getBackend().handleCodePaddingInstructionBegin(Inst); + EmitInstructionImpl(Inst, STI); + getAssembler().getBackend().handleCodePaddingInstructionEnd(Inst); +} + +void MCObjectStreamer::EmitInstructionImpl(const MCInst &Inst, + const MCSubtargetInfo &STI) { MCStreamer::EmitInstruction(Inst, STI); MCSection *Sec = getCurrentSectionOnly(); @@ -461,6 +478,21 @@ insert(new MCOrgFragment(*Offset, Value, Loc)); } +void MCObjectStreamer::EmitCodePaddingFunctionStart(const TargetMachine &TM, + const MachineFunction &MF, + const MachineLoopInfo &LI) { + getAssembler().getBackend().handleCodePaddingFunctionStart(MF, this, TM, LI); +} + +void MCObjectStreamer::EmitCodePaddingFunctionEnd(const MachineFunction &MF) { + getAssembler().getBackend().handleCodePaddingFunctionEnd(MF); +} + +void MCObjectStreamer::EmitCodePaddingBasicBlockStart( + const MachineBasicBlock &MBB) { + getAssembler().getBackend().handleCodePaddingBasicBlockStart(MBB); +} + // Associate DTPRel32 fixup with data and resize data area void MCObjectStreamer::EmitDTPRel32Value(const MCExpr *Value) { MCDataFragment *DF = getOrCreateDataFragment(); Index: test/CodeGen/AArch64/arm64-opt-remarks-lazy-bfi.ll =================================================================== --- test/CodeGen/AArch64/arm64-opt-remarks-lazy-bfi.ll +++ test/CodeGen/AArch64/arm64-opt-remarks-lazy-bfi.ll @@ -36,7 +36,9 @@ ; HOTNESS-NOT: Executing Pass ; HOTNESS: block-frequency: empty_func ; HOTNESS-NOT: Executing Pass -; HOTNESS: Executing Pass 'AArch64 Assembly Printer' +; HOTNESS: Executing Pass 'MachineDominator Tree Construction' +; HOTNESS-NEXT: Executing Pass 'Machine Natural Loop Construction' +; HOTNESS-NEXT: Executing Pass 'AArch64 Assembly Printer' ; HOTNESS: arm64-summary-remarks.ll:5:0: 1 instructions in function (hotness: 33) @@ -45,6 +47,8 @@ ; NO_HOTNESS-NEXT: Freeing Pass 'Implement the 'patchable-function' attribute' ; NO_HOTNESS-NEXT: Executing Pass 'Lazy Machine Block Frequency Analysis' ; NO_HOTNESS-NEXT: Executing Pass 'Machine Optimization Remark Emitter' +; NO_HOTNESS-NEXT: Executing Pass 'MachineDominator Tree Construction' +; NO_HOTNESS-NEXT: Executing Pass 'Machine Natural Loop Construction' ; NO_HOTNESS-NEXT: Executing Pass 'AArch64 Assembly Printer' ; NO_HOTNESS: arm64-summary-remarks.ll:5:0: 1 instructions in function{{$}}