Index: llvm/trunk/include/llvm/CodeGen/AsmPrinter.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/AsmPrinter.h +++ llvm/trunk/include/llvm/CodeGen/AsmPrinter.h @@ -58,6 +58,7 @@ class MachineOptimizationRemarkEmitter; class MCAsmInfo; class MCCFIInstruction; +struct MCCodePaddingContext; class MCContext; class MCExpr; class MCInst; @@ -377,7 +378,7 @@ virtual void EmitBasicBlockStart(const MachineBasicBlock &MBB) const; /// Targets can override this to emit stuff at the end of a basic block. - virtual void EmitBasicBlockEnd(const MachineBasicBlock &MBB) {} + virtual void EmitBasicBlockEnd(const MachineBasicBlock &MBB); /// Targets should implement this to emit instructions. virtual void EmitInstruction(const MachineInstr *) { @@ -626,6 +627,8 @@ /// Emit GlobalAlias or GlobalIFunc. void emitGlobalIndirectSymbol(Module &M, const GlobalIndirectSymbol& GIS); + void setupCodePaddingContext(const MachineBasicBlock &MBB, + MCCodePaddingContext &Context) const; }; } // end namespace llvm Index: llvm/trunk/include/llvm/MC/MCAsmBackend.h =================================================================== --- llvm/trunk/include/llvm/MC/MCAsmBackend.h +++ llvm/trunk/include/llvm/MC/MCAsmBackend.h @@ -15,17 +15,22 @@ #include "llvm/ADT/StringRef.h" #include "llvm/MC/MCDirectives.h" #include "llvm/MC/MCFixup.h" +#include "llvm/MC/MCFragment.h" #include +#include namespace llvm { class MCAsmLayout; class MCAssembler; class MCCFIInstruction; +class MCCodePadder; struct MCFixupKindInfo; class MCFragment; class MCInst; +class MCObjectStreamer; class MCObjectWriter; +struct MCCodePaddingContext; class MCRelaxableFragment; class MCSubtargetInfo; class MCValue; @@ -33,8 +38,11 @@ /// Generic interface to target specific assembler backends. class MCAsmBackend { + std::unique_ptr CodePadder; + protected: // Can only create subclasses. MCAsmBackend(); + MCAsmBackend(std::unique_ptr TargetCodePadder); public: MCAsmBackend(const MCAsmBackend &) = delete; @@ -133,6 +141,40 @@ generateCompactUnwindEncoding(ArrayRef) const { return 0; } + + /// Handles all target related code padding when starting to write a new + /// basic block to an object file. + /// + /// \param OS The streamer used for writing the padding data and function. + /// \param Context the context of the padding, Embeds the basic block's + /// parameters. + void handleCodePaddingBasicBlockStart(MCObjectStreamer *OS, + const MCCodePaddingContext &Context); + /// Handles all target related code padding after writing a block to an object + /// file. + /// + /// \param Context the context of the padding, Embeds the basic block's + /// parameters. + void handleCodePaddingBasicBlockEnd(const MCCodePaddingContext &Context); + /// 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: llvm/trunk/include/llvm/MC/MCAssembler.h =================================================================== --- llvm/trunk/include/llvm/MC/MCAssembler.h +++ llvm/trunk/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: llvm/trunk/include/llvm/MC/MCCodePadder.h =================================================================== --- llvm/trunk/include/llvm/MC/MCCodePadder.h +++ llvm/trunk/include/llvm/MC/MCCodePadder.h @@ -0,0 +1,243 @@ +//===- 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/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" + +namespace llvm { + +class MCAsmLayout; +class MCCodePaddingPolicy; +class MCFragment; +class MCInst; +class MCObjectStreamer; +class MCPaddingFragment; +class MCSection; + +typedef SmallVector MCPFRange; + +struct MCCodePaddingContext { + bool IsPaddingActive; + bool IsBasicBlockInsideInnermostLoop; + bool IsBasicBlockReachableViaFallthrough; + bool IsBasicBlockReachableViaBranch; +}; + +/// 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; + + /// Determines if the MCCodePaddingPolicies are active. + bool ArePoliciesActive; + + /// All the supported MCCodePaddingPolicies. + SmallPtrSet CodePaddingPolicies; + + /// 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. + DenseMap FragmentToJurisdiction; + MCPFRange &getJurisdiction(MCPaddingFragment *Fragment, MCAsmLayout &Layout); + + /// A map holding the maximal instruction window size relevant for a padding + /// fragment. + DenseMap FragmentToMaxWindowSize; + uint64_t getMaxWindowSize(MCPaddingFragment *Fragment, MCAsmLayout &Layout); + +protected: + /// The current streamer, used to stream code padding. + MCObjectStreamer *OS; + + bool addPolicy(MCCodePaddingPolicy *Policy); + + virtual bool + basicBlockRequiresInsertionPoint(const MCCodePaddingContext &Context) { + return false; + } + + virtual bool instructionRequiresInsertionPoint(const MCInst &Inst) { + return false; + } + + virtual bool usePoliciesForBasicBlock(const MCCodePaddingContext &Context) { + return Context.IsPaddingActive; + } + +public: + MCCodePadder() + : ArePoliciesActive(false), CurrHandledInstFragment(nullptr), + OS(nullptr) {} + virtual ~MCCodePadder(); + + /// Handles all target related code padding when starting to write a new + /// basic block to an object file. + /// + /// \param OS The streamer used for writing the padding data and function. + /// \param Context the context of the padding, Embeds the basic block's + /// parameters. + void handleBasicBlockStart(MCObjectStreamer *OS, + const MCCodePaddingContext &Context); + /// Handles all target related code padding when done writing a block to an + /// object file. + /// + /// \param Context the context of the padding, Embeds the basic block's + /// parameters. + void handleBasicBlockEnd(const MCCodePaddingContext &Context); + /// 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 Context the context of the padding, Embeds the basic block's + /// parameters. + /// + /// \returns true iff this policy needs padding for the basic block. + virtual bool + basicBlockRequiresPaddingFragment(const MCCodePaddingContext &Context) 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 instructionRequiresPaddingFragment(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: llvm/trunk/include/llvm/MC/MCFragment.h =================================================================== --- llvm/trunk/include/llvm/MC/MCFragment.h +++ llvm/trunk/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,98 @@ } }; +/// Fragment for adding required padding. +/// This fragment is always inserted before an instruction, and holds that +/// instruction as context information (as well as a mask of kinds) for +/// determining the padding size. +/// +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; + + struct MCInstInfo { + 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 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: llvm/trunk/include/llvm/MC/MCObjectStreamer.h =================================================================== --- llvm/trunk/include/llvm/MC/MCObjectStreamer.h +++ llvm/trunk/include/llvm/MC/MCObjectStreamer.h @@ -47,6 +47,7 @@ void EmitCFIStartProcImpl(MCDwarfFrameInfo &Frame) override; void EmitCFIEndProcImpl(MCDwarfFrameInfo &Frame) override; MCSymbol *EmitCFILabel() override; + void EmitInstructionImpl(const MCInst &Inst, const MCSubtargetInfo &STI); protected: MCObjectStreamer(MCContext &Context, std::unique_ptr TAB, @@ -76,6 +77,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); @@ -121,6 +123,10 @@ unsigned MaxBytesToEmit = 0) override; void emitValueToOffset(const MCExpr *Offset, unsigned char Value, SMLoc Loc) override; + void + EmitCodePaddingBasicBlockStart(const MCCodePaddingContext &Context) override; + void + EmitCodePaddingBasicBlockEnd(const MCCodePaddingContext &Context) override; void EmitDwarfLocDirective(unsigned FileNo, unsigned Line, unsigned Column, unsigned Flags, unsigned Isa, unsigned Discriminator, Index: llvm/trunk/include/llvm/MC/MCStreamer.h =================================================================== --- llvm/trunk/include/llvm/MC/MCStreamer.h +++ llvm/trunk/include/llvm/MC/MCStreamer.h @@ -38,6 +38,7 @@ class formatted_raw_ostream; class MCAsmBackend; class MCCodeEmitter; +struct MCCodePaddingContext; class MCContext; class MCExpr; class MCInst; @@ -716,6 +717,12 @@ virtual void emitValueToOffset(const MCExpr *Offset, unsigned char Value, SMLoc Loc); + virtual void + EmitCodePaddingBasicBlockStart(const MCCodePaddingContext &Context) {} + + virtual void + EmitCodePaddingBasicBlockEnd(const MCCodePaddingContext &Context) {} + /// @} /// \brief Switch to a new logical file. This is used to implement the '.file Index: llvm/trunk/lib/CodeGen/AsmPrinter/AsmPrinter.cpp =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/AsmPrinter.cpp +++ llvm/trunk/lib/CodeGen/AsmPrinter/AsmPrinter.cpp @@ -73,6 +73,7 @@ #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" #include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCCodePadder.h" #include "llvm/MC/MCContext.h" #include "llvm/MC/MCDirectives.h" #include "llvm/MC/MCDwarf.h" @@ -233,8 +234,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - if (isVerbose()) - AU.addRequired(); + AU.addRequired(); } bool AsmPrinter::doInitialization(Module &M) { @@ -1440,8 +1440,7 @@ } ORE = &getAnalysis().getORE(); - if (isVerbose()) - LI = &getAnalysis(); + LI = &getAnalysis(); const TargetSubtargetInfo &STI = MF.getSubtarget(); EnablePrintSchedInfo = PrintSchedule.getNumOccurrences() @@ -2614,6 +2613,23 @@ PrintChildLoopComment(OS, Loop, AP.getFunctionNumber()); } +void AsmPrinter::setupCodePaddingContext(const MachineBasicBlock &MBB, + MCCodePaddingContext &Context) const { + assert(MF != nullptr && "Machine function must be valid"); + assert(LI != nullptr && "Loop info must be valid"); + Context.IsPaddingActive = !MF->hasInlineAsm() && + !MF->getFunction()->optForSize() && + TM.getOptLevel() != CodeGenOpt::None; + const MachineLoop *CurrentLoop = LI->getLoopFor(&MBB); + Context.IsBasicBlockInsideInnermostLoop = + CurrentLoop != nullptr && CurrentLoop->getSubLoops().empty(); + Context.IsBasicBlockReachableViaFallthrough = + std::find(MBB.pred_begin(), MBB.pred_end(), MBB.getPrevNode()) != + MBB.pred_end(); + Context.IsBasicBlockReachableViaBranch = + MBB.pred_size() > 0 && !isBlockOnlyReachableByFallthrough(&MBB); +} + /// EmitBasicBlockStart - This method prints the label for the specified /// MachineBasicBlock, an alignment (if present) and a comment describing /// it if appropriate. @@ -2629,6 +2645,9 @@ // Emit an alignment directive for this block, if needed. if (unsigned Align = MBB.getAlignment()) EmitAlignment(Align); + MCCodePaddingContext Context; + setupCodePaddingContext(MBB, Context); + OutStreamer->EmitCodePaddingBasicBlockStart(Context); // 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 @@ -2670,6 +2689,12 @@ } } +void AsmPrinter::EmitBasicBlockEnd(const MachineBasicBlock &MBB) { + MCCodePaddingContext Context; + setupCodePaddingContext(MBB, Context); + OutStreamer->EmitCodePaddingBasicBlockEnd(Context); +} + void AsmPrinter::EmitVisibility(MCSymbol *Sym, unsigned Visibility, bool IsDefinition) const { MCSymbolAttr Attr = MCSA_Invalid; Index: llvm/trunk/lib/MC/CMakeLists.txt =================================================================== --- llvm/trunk/lib/MC/CMakeLists.txt +++ llvm/trunk/lib/MC/CMakeLists.txt @@ -10,6 +10,7 @@ MCAsmStreamer.cpp MCAssembler.cpp MCCodeEmitter.cpp + MCCodePadder.cpp MCCodeView.cpp MCContext.cpp MCDwarf.cpp Index: llvm/trunk/lib/MC/MCAsmBackend.cpp =================================================================== --- llvm/trunk/lib/MC/MCAsmBackend.cpp +++ llvm/trunk/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,7 +18,10 @@ using namespace llvm; -MCAsmBackend::MCAsmBackend() = default; +MCAsmBackend::MCAsmBackend() : CodePadder(new MCCodePadder()) {} + +MCAsmBackend::MCAsmBackend(std::unique_ptr TargetCodePadder) + : CodePadder(std::move(TargetCodePadder)) {} MCAsmBackend::~MCAsmBackend() = default; @@ -59,3 +63,25 @@ return true; return fixupNeedsRelaxation(Fixup, Value, DF, Layout); } + +void MCAsmBackend::handleCodePaddingBasicBlockStart( + MCObjectStreamer *OS, const MCCodePaddingContext &Context) { + CodePadder->handleBasicBlockStart(OS, Context); +} + +void MCAsmBackend::handleCodePaddingBasicBlockEnd( + const MCCodePaddingContext &Context) { + CodePadder->handleBasicBlockEnd(Context); +} + +void MCAsmBackend::handleCodePaddingInstructionBegin(const MCInst &Inst) { + CodePadder->handleInstructionBegin(Inst); +} + +void MCAsmBackend::handleCodePaddingInstructionEnd(const MCInst &Inst) { + CodePadder->handleInstructionEnd(Inst); +} + +bool MCAsmBackend::relaxFragment(MCPaddingFragment *PF, MCAsmLayout &Layout) { + return CodePadder->relaxFragment(PF, Layout); +} \ No newline at end of file Index: llvm/trunk/lib/MC/MCAssembler.cpp =================================================================== --- llvm/trunk/lib/MC/MCAssembler.cpp +++ llvm/trunk/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 @@ -283,6 +287,9 @@ case MCFragment::FT_LEB: return cast(F).getContents().size(); + case MCFragment::FT_Padding: + return cast(F).getSize(); + case MCFragment::FT_SafeSEH: return 4; @@ -549,6 +556,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()); @@ -822,6 +836,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; @@ -916,6 +943,9 @@ 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: llvm/trunk/lib/MC/MCCodePadder.cpp =================================================================== --- llvm/trunk/lib/MC/MCCodePadder.cpp +++ llvm/trunk/lib/MC/MCCodePadder.cpp @@ -0,0 +1,371 @@ +//===- 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 : CodePaddingPolicies) + delete Policy; +} + +bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) { + assert(Policy && "Policy must be valid"); + return CodePaddingPolicies.insert(Policy).second; +} + +void MCCodePadder::handleBasicBlockStart(MCObjectStreamer *OS, + const MCCodePaddingContext &Context) { + assert(OS != nullptr && "OS must be valid"); + assert(this->OS == nullptr && "Still handling another basic block"); + this->OS = OS; + + ArePoliciesActive = usePoliciesForBasicBlock(Context); + + bool InsertionPoint = basicBlockRequiresInsertionPoint(Context); + 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( + CodePaddingPolicies.begin(), CodePaddingPolicies.end(), + MCPaddingFragment::PFK_None, + [&Context](uint64_t Mask, + const MCCodePaddingPolicy *Policy) -> uint64_t { + return Policy->basicBlockRequiresPaddingFragment(Context) + ? (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::handleBasicBlockEnd(const MCCodePaddingContext &Context) { + assert(this->OS != nullptr && "Not handling a basic block"); + OS = nullptr; +} + +void MCCodePadder::handleInstructionBegin(const MCInst &Inst) { + if (!OS) + return; // instruction was emitted outside a function + + assert(CurrHandledInstFragment == nullptr && "Can't start handling an " + "instruction while still " + "handling another instruction"); + + bool InsertionPoint = instructionRequiresInsertionPoint(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( + CodePaddingPolicies.begin(), CodePaddingPolicies.end(), + MCPaddingFragment::PFK_None, + [&Inst](uint64_t Mask, const MCCodePaddingPolicy *Policy) -> uint64_t { + return Policy->instructionRequiresPaddingFragment(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 + if (CurrHandledInstFragment == nullptr) + return; + + 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) { + auto 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 : CodePaddingPolicies) { + 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) { + auto 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 : CodePaddingPolicies) + 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) { + 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( + CodePaddingPolicies.begin(), CodePaddingPolicies.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: llvm/trunk/lib/MC/MCFragment.cpp =================================================================== --- llvm/trunk/lib/MC/MCFragment.cpp +++ llvm/trunk/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; @@ -419,6 +423,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: llvm/trunk/lib/MC/MCObjectStreamer.cpp =================================================================== --- llvm/trunk/lib/MC/MCObjectStreamer.cpp +++ llvm/trunk/lib/MC/MCObjectStreamer.cpp @@ -108,6 +108,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); } @@ -247,6 +257,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(); @@ -467,6 +484,16 @@ insert(new MCOrgFragment(*Offset, Value, Loc)); } +void MCObjectStreamer::EmitCodePaddingBasicBlockStart( + const MCCodePaddingContext &Context) { + getAssembler().getBackend().handleCodePaddingBasicBlockStart(this, Context); +} + +void MCObjectStreamer::EmitCodePaddingBasicBlockEnd( + const MCCodePaddingContext &Context) { + getAssembler().getBackend().handleCodePaddingBasicBlockEnd(Context); +} + // Associate DTPRel32 fixup with data and resize data area void MCObjectStreamer::EmitDTPRel32Value(const MCExpr *Value) { MCDataFragment *DF = getOrCreateDataFragment(); Index: llvm/trunk/lib/Target/Mips/MipsAsmPrinter.cpp =================================================================== --- llvm/trunk/lib/Target/Mips/MipsAsmPrinter.cpp +++ llvm/trunk/lib/Target/Mips/MipsAsmPrinter.cpp @@ -417,6 +417,7 @@ } void MipsAsmPrinter::EmitBasicBlockEnd(const MachineBasicBlock &MBB) { + AsmPrinter::EmitBasicBlockEnd(MBB); MipsTargetStreamer &TS = getTargetStreamer(); if (MBB.empty()) TS.emitDirectiveInsn(); Index: llvm/trunk/lib/Target/X86/X86AsmPrinter.h =================================================================== --- llvm/trunk/lib/Target/X86/X86AsmPrinter.h +++ llvm/trunk/lib/Target/X86/X86AsmPrinter.h @@ -119,6 +119,7 @@ void EmitInstruction(const MachineInstr *MI) override; void EmitBasicBlockEnd(const MachineBasicBlock &MBB) override { + AsmPrinter::EmitBasicBlockEnd(MBB); SMShadowTracker.emitShadowPadding(*OutStreamer, getSubtargetInfo()); } Index: llvm/trunk/test/CodeGen/AArch64/arm64-opt-remarks-lazy-bfi.ll =================================================================== --- llvm/trunk/test/CodeGen/AArch64/arm64-opt-remarks-lazy-bfi.ll +++ llvm/trunk/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{{$}}