From bfc2d688b591c574c0cc788348c74545ce894efa Mon Sep 17 00:00:00 2001 From: Stephen Hines Date: Fri, 17 Oct 2014 08:47:43 -0700 Subject: Bring in fixes for Cortex-A53 errata + build updates. Bug: 18034609 Change-Id: I2cf0094eb9df801a84274ff29018431d75da89dd --- lib/CodeGen/CriticalAntiDepBreaker.cpp | 19 +- lib/CodeGen/LiveRangeEdit.cpp | 2 +- lib/CodeGen/MachineCSE.cpp | 2 +- lib/CodeGen/MachineLICM.cpp | 2 +- lib/CodeGen/MachineSink.cpp | 2 +- lib/CodeGen/RegisterCoalescer.cpp | 2 +- lib/Target/AArch64/AArch64.h | 2 + lib/Target/AArch64/AArch64A53Fix835769.cpp | 240 ++++++++ lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp | 694 +++++++++++++++++++++++ lib/Target/AArch64/AArch64InstrFormats.td | 8 +- lib/Target/AArch64/AArch64InstrInfo.cpp | 45 ++ lib/Target/AArch64/AArch64InstrInfo.h | 2 + lib/Target/AArch64/AArch64Subtarget.h | 2 + lib/Target/AArch64/AArch64TargetMachine.cpp | 20 +- lib/Target/AArch64/Android.mk | 2 + lib/Target/AArch64/CMakeLists.txt | 2 + 16 files changed, 1035 insertions(+), 11 deletions(-) create mode 100644 lib/Target/AArch64/AArch64A53Fix835769.cpp create mode 100644 lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp (limited to 'lib') diff --git a/lib/CodeGen/CriticalAntiDepBreaker.cpp b/lib/CodeGen/CriticalAntiDepBreaker.cpp index d3ffcc7..d2231ec 100644 --- a/lib/CodeGen/CriticalAntiDepBreaker.cpp +++ b/lib/CodeGen/CriticalAntiDepBreaker.cpp @@ -94,7 +94,14 @@ void CriticalAntiDepBreaker::FinishBlock() { void CriticalAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex) { - if (MI->isDebugValue()) + // Kill instructions can define registers but are really nops, and there might + // be a real definition earlier that needs to be paired with uses dominated by + // this kill. + + // FIXME: It may be possible to remove the isKill() restriction once PR18663 + // has been properly fixed. There can be value in processing kills as seen in + // the AggressiveAntiDepBreaker class. + if (MI->isDebugValue() || MI->isKill()) return; assert(Count < InsertPosIndex && "Instruction index out of expected range!"); @@ -237,6 +244,7 @@ void CriticalAntiDepBreaker::ScanInstruction(MachineInstr *MI, // Update liveness. // Proceeding upwards, registers that are defed but not used in this // instruction are now dead. + assert(!MI->isKill() && "Attempting to scan a kill instruction"); if (!TII->isPredicated(MI)) { // Predicated defs are modeled as read + write, i.e. similar to two @@ -527,7 +535,14 @@ BreakAntiDependencies(const std::vector& SUnits, unsigned Count = InsertPosIndex - 1; for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) { MachineInstr *MI = --I; - if (MI->isDebugValue()) + // Kill instructions can define registers but are really nops, and there + // might be a real definition earlier that needs to be paired with uses + // dominated by this kill. + + // FIXME: It may be possible to remove the isKill() restriction once PR18663 + // has been properly fixed. There can be value in processing kills as seen + // in the AggressiveAntiDepBreaker class. + if (MI->isDebugValue() || MI->isKill()) continue; // Check if this instruction has a dependence on the critical path that diff --git a/lib/CodeGen/LiveRangeEdit.cpp b/lib/CodeGen/LiveRangeEdit.cpp index 431241f..c27d630 100644 --- a/lib/CodeGen/LiveRangeEdit.cpp +++ b/lib/CodeGen/LiveRangeEdit.cpp @@ -135,7 +135,7 @@ bool LiveRangeEdit::canRematerializeAt(Remat &RM, } // If only cheap remats were requested, bail out early. - if (cheapAsAMove && !RM.OrigMI->isAsCheapAsAMove()) + if (cheapAsAMove && !TII.isAsCheapAsAMove(RM.OrigMI)) return false; // Verify that all used registers are available with the same values. diff --git a/lib/CodeGen/MachineCSE.cpp b/lib/CodeGen/MachineCSE.cpp index 7da439c..c2ab76e 100644 --- a/lib/CodeGen/MachineCSE.cpp +++ b/lib/CodeGen/MachineCSE.cpp @@ -380,7 +380,7 @@ bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in // an immediate predecessor. We don't want to increase register pressure and // end up causing other computation to be spilled. - if (MI->isAsCheapAsAMove()) { + if (TII->isAsCheapAsAMove(MI)) { MachineBasicBlock *CSBB = CSMI->getParent(); MachineBasicBlock *BB = MI->getParent(); if (CSBB != BB && !CSBB->isSuccessor(BB)) diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 68d2efd..94cdab5 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -1039,7 +1039,7 @@ bool MachineLICM::HasHighOperandLatency(MachineInstr &MI, /// IsCheapInstruction - Return true if the instruction is marked "cheap" or /// the operand latency between its def and a use is one or less. bool MachineLICM::IsCheapInstruction(MachineInstr &MI) const { - if (MI.isAsCheapAsAMove() || MI.isCopyLike()) + if (TII->isAsCheapAsAMove(&MI) || MI.isCopyLike()) return true; if (!InstrItins || InstrItins->isEmpty()) return false; diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index f44e4d1..0ae495c 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -292,7 +292,7 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, if (!CEBCandidates.insert(std::make_pair(From, To))) return true; - if (!MI->isCopy() && !MI->isAsCheapAsAMove()) + if (!MI->isCopy() && !TII->isAsCheapAsAMove(MI)) return true; // MI is cheap, we probably don't want to break the critical edge for it. diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp index 5aaeb87..65b0528 100644 --- a/lib/CodeGen/RegisterCoalescer.cpp +++ b/lib/CodeGen/RegisterCoalescer.cpp @@ -751,7 +751,7 @@ bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, IsDefCopy = true; return false; } - if (!DefMI->isAsCheapAsAMove()) + if (!TII->isAsCheapAsAMove(DefMI)) return false; if (!TII->isTriviallyReMaterializable(DefMI, AA)) return false; diff --git a/lib/Target/AArch64/AArch64.h b/lib/Target/AArch64/AArch64.h index 1c022aa..7b52e55 100644 --- a/lib/Target/AArch64/AArch64.h +++ b/lib/Target/AArch64/AArch64.h @@ -37,6 +37,8 @@ FunctionPass *createAArch64ExpandPseudoPass(); FunctionPass *createAArch64LoadStoreOptimizationPass(); ModulePass *createAArch64PromoteConstantPass(); FunctionPass *createAArch64AddressTypePromotionPass(); +FunctionPass *createAArch64A57FPLoadBalancing(); +FunctionPass *createAArch64A53Fix835769(); /// \brief Creates an ARM-specific Target Transformation Info pass. ImmutablePass * createAArch64TargetTransformInfoPass(const AArch64TargetMachine *TM); diff --git a/lib/Target/AArch64/AArch64A53Fix835769.cpp b/lib/Target/AArch64/AArch64A53Fix835769.cpp new file mode 100644 index 0000000..852a635 --- /dev/null +++ b/lib/Target/AArch64/AArch64A53Fix835769.cpp @@ -0,0 +1,240 @@ +//===-- AArch64A53Fix835769.cpp -------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// This pass changes code to work around Cortex-A53 erratum 835769. +// It works around it by inserting a nop instruction in code sequences that +// in some circumstances may trigger the erratum. +// It inserts a nop instruction between a sequence of the following 2 classes +// of instructions: +// instr 1: mem-instr (including loads, stores and prefetches). +// instr 2: non-SIMD integer multiply-accumulate writing 64-bit X registers. +//===----------------------------------------------------------------------===// + +#include "AArch64.h" +#include "AArch64InstrInfo.h" +#include "AArch64Subtarget.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +#define DEBUG_TYPE "aarch64-fix-cortex-a53-835769" + +STATISTIC(NumNopsAdded, "Number of Nops added to work around erratum 835769"); + +//===----------------------------------------------------------------------===// +// Helper functions + +// Is the instruction a match for the instruction that comes first in the +// sequence of instructions that can trigger the erratum? +static bool isFirstInstructionInSequence(MachineInstr *MI) { + // Must return true if this instruction is a load, a store or a prefetch. + switch (MI->getOpcode()) { + case AArch64::PRFMl: + case AArch64::PRFMroW: + case AArch64::PRFMroX: + case AArch64::PRFMui: + case AArch64::PRFUMi: + return true; + default: + return (MI->mayLoad() || MI->mayStore()); + } +} + +// Is the instruction a match for the instruction that comes second in the +// sequence that can trigger the erratum? +static bool isSecondInstructionInSequence(MachineInstr *MI) { + // Must return true for non-SIMD integer multiply-accumulates, writing + // to a 64-bit register. + switch (MI->getOpcode()) { + // Erratum cannot be triggered when the destination register is 32 bits, + // therefore only include the following. + case AArch64::MSUBXrrr: + case AArch64::MADDXrrr: + case AArch64::SMADDLrrr: + case AArch64::SMSUBLrrr: + case AArch64::UMADDLrrr: + case AArch64::UMSUBLrrr: + // Erratum can only be triggered by multiply-adds, not by regular + // non-accumulating multiplies, i.e. when Ra=XZR='11111' + return MI->getOperand(3).getReg() != AArch64::XZR; + default: + return false; + } +} + + +//===----------------------------------------------------------------------===// + +namespace { +class AArch64A53Fix835769 : public MachineFunctionPass { + const AArch64InstrInfo *TII; + +public: + static char ID; + explicit AArch64A53Fix835769() : MachineFunctionPass(ID) {} + + bool runOnMachineFunction(MachineFunction &F) override; + + const char *getPassName() const override { + return "Workaround A53 erratum 835769 pass"; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + MachineFunctionPass::getAnalysisUsage(AU); + } + +private: + bool runOnBasicBlock(MachineBasicBlock &MBB); +}; +char AArch64A53Fix835769::ID = 0; + +} // end anonymous namespace + +//===----------------------------------------------------------------------===// + +bool +AArch64A53Fix835769::runOnMachineFunction(MachineFunction &F) { + const TargetMachine &TM = F.getTarget(); + + bool Changed = false; + DEBUG(dbgs() << "***** AArch64A53Fix835769 *****\n"); + + TII = TM.getSubtarget().getInstrInfo(); + + for (auto &MBB : F) { + Changed |= runOnBasicBlock(MBB); + } + + return Changed; +} + +// Return the block that was fallen through to get to MBB, if any, +// otherwise nullptr. +static MachineBasicBlock *getBBFallenThrough(MachineBasicBlock *MBB, + const TargetInstrInfo *TII) { + // Get the previous machine basic block in the function. + MachineFunction::iterator MBBI = *MBB; + + // Can't go off top of function. + if (MBBI == MBB->getParent()->begin()) + return nullptr; + + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; + SmallVector Cond; + + MachineBasicBlock *PrevBB = std::prev(MBBI); + for (MachineBasicBlock *S : MBB->predecessors()) + if (S == PrevBB && !TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond) && + !TBB && !FBB) + return S; + + return nullptr; +} + +// Iterate through fallen through blocks trying to find a previous non-pseudo if +// there is one, otherwise return nullptr. Only look for instructions in +// previous blocks, not the current block, since we only use this to look at +// previous blocks. +static MachineInstr *getLastNonPseudo(MachineBasicBlock &MBB, + const TargetInstrInfo *TII) { + MachineBasicBlock *FMBB = &MBB; + + // If there is no non-pseudo in the current block, loop back around and try + // the previous block (if there is one). + while ((FMBB = getBBFallenThrough(FMBB, TII))) { + for (auto I = FMBB->rbegin(), E = FMBB->rend(); I != E; ++I) { + if (!I->isPseudo()) + return &*I; + } + } + + // There was no previous non-pseudo in the fallen through blocks + return nullptr; +} + +static void insertNopBeforeInstruction(MachineBasicBlock &MBB, MachineInstr* MI, + const TargetInstrInfo *TII) { + // If we are the first instruction of the block, put the NOP at the end of + // the previous fallthrough block + if (MI == &MBB.front()) { + MachineInstr *I = getLastNonPseudo(MBB, TII); + assert(I && "Expected instruction"); + DebugLoc DL = I->getDebugLoc(); + BuildMI(I->getParent(), DL, TII->get(AArch64::HINT)).addImm(0); + } + else { + DebugLoc DL = MI->getDebugLoc(); + BuildMI(MBB, MI, DL, TII->get(AArch64::HINT)).addImm(0); + } + + ++NumNopsAdded; +} + +bool +AArch64A53Fix835769::runOnBasicBlock(MachineBasicBlock &MBB) { + bool Changed = false; + DEBUG(dbgs() << "Running on MBB: " << MBB << " - scanning instructions...\n"); + + // First, scan the basic block, looking for a sequence of 2 instructions + // that match the conditions under which the erratum may trigger. + + // List of terminating instructions in matching sequences + std::vector Sequences; + unsigned Idx = 0; + MachineInstr *PrevInstr = nullptr; + + // Try and find the last non-pseudo instruction in any fallen through blocks, + // if there isn't one, then we use nullptr to represent that. + PrevInstr = getLastNonPseudo(MBB, TII); + + for (auto &MI : MBB) { + MachineInstr *CurrInstr = &MI; + DEBUG(dbgs() << " Examining: " << MI); + if (PrevInstr) { + DEBUG(dbgs() << " PrevInstr: " << *PrevInstr + << " CurrInstr: " << *CurrInstr + << " isFirstInstructionInSequence(PrevInstr): " + << isFirstInstructionInSequence(PrevInstr) << "\n" + << " isSecondInstructionInSequence(CurrInstr): " + << isSecondInstructionInSequence(CurrInstr) << "\n"); + if (isFirstInstructionInSequence(PrevInstr) && + isSecondInstructionInSequence(CurrInstr)) { + DEBUG(dbgs() << " ** pattern found at Idx " << Idx << "!\n"); + Sequences.push_back(CurrInstr); + } + } + if (!CurrInstr->isPseudo()) + PrevInstr = CurrInstr; + ++Idx; + } + + DEBUG(dbgs() << "Scan complete, "<< Sequences.size() + << " occurences of pattern found.\n"); + + // Then update the basic block, inserting nops between the detected sequences. + for (auto &MI : Sequences) { + Changed = true; + insertNopBeforeInstruction(MBB, MI, TII); + } + + return Changed; +} + +// Factory function used by AArch64TargetMachine to add the pass to +// the passmanager. +FunctionPass *llvm::createAArch64A53Fix835769() { + return new AArch64A53Fix835769(); +} diff --git a/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp b/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp new file mode 100644 index 0000000..195a48e --- /dev/null +++ b/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp @@ -0,0 +1,694 @@ +//===-- AArch64A57FPLoadBalancing.cpp - Balance FP ops statically on A57---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// For best-case performance on Cortex-A57, we should try to use a balanced +// mix of odd and even D-registers when performing a critical sequence of +// independent, non-quadword FP/ASIMD floating-point multiply or +// multiply-accumulate operations. +// +// This pass attempts to detect situations where the register allocation may +// adversely affect this load balancing and to change the registers used so as +// to better utilize the CPU. +// +// Ideally we'd just take each multiply or multiply-accumulate in turn and +// allocate it alternating even or odd registers. However, multiply-accumulates +// are most efficiently performed in the same functional unit as their +// accumulation operand. Therefore this pass tries to find maximal sequences +// ("Chains") of multiply-accumulates linked via their accumulation operand, +// and assign them all the same "color" (oddness/evenness). +// +// This optimization affects S-register and D-register floating point +// multiplies and FMADD/FMAs, as well as vector (floating point only) muls and +// FMADD/FMA. Q register instructions (and 128-bit vector instructions) are +// not affected. +//===----------------------------------------------------------------------===// + +#include "AArch64.h" +#include "AArch64InstrInfo.h" +#include "AArch64Subtarget.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/EquivalenceClasses.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RegisterScavenging.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include +using namespace llvm; + +#define DEBUG_TYPE "aarch64-a57-fp-load-balancing" + +// Enforce the algorithm to use the scavenged register even when the original +// destination register is the correct color. Used for testing. +static cl::opt +TransformAll("aarch64-a57-fp-load-balancing-force-all", + cl::desc("Always modify dest registers regardless of color"), + cl::init(false), cl::Hidden); + +// Never use the balance information obtained from chains - return a specific +// color always. Used for testing. +static cl::opt +OverrideBalance("aarch64-a57-fp-load-balancing-override", + cl::desc("Ignore balance information, always return " + "(1: Even, 2: Odd)."), + cl::init(0), cl::Hidden); + +//===----------------------------------------------------------------------===// +// Helper functions + +// Is the instruction a type of multiply on 64-bit (or 32-bit) FPRs? +static bool isMul(MachineInstr *MI) { + switch (MI->getOpcode()) { + case AArch64::FMULSrr: + case AArch64::FNMULSrr: + case AArch64::FMULDrr: + case AArch64::FNMULDrr: + + case AArch64::FMULv2f32: + return true; + default: + return false; + } +} + +// Is the instruction a type of FP multiply-accumulate on 64-bit (or 32-bit) FPRs? +static bool isMla(MachineInstr *MI) { + switch (MI->getOpcode()) { + case AArch64::FMSUBSrrr: + case AArch64::FMADDSrrr: + case AArch64::FNMSUBSrrr: + case AArch64::FNMADDSrrr: + case AArch64::FMSUBDrrr: + case AArch64::FMADDDrrr: + case AArch64::FNMSUBDrrr: + case AArch64::FNMADDDrrr: + + case AArch64::FMLAv2f32: + case AArch64::FMLSv2f32: + return true; + default: + return false; + } +} + +//===----------------------------------------------------------------------===// + +namespace { +/// A "color", which is either even or odd. Yes, these aren't really colors +/// but the algorithm is conceptually doing two-color graph coloring. +enum class Color { Even, Odd }; +static const char *ColorNames[2] = { "Even", "Odd" }; + +class Chain; + +class AArch64A57FPLoadBalancing : public MachineFunctionPass { + const AArch64InstrInfo *TII; + MachineRegisterInfo *MRI; + const TargetRegisterInfo *TRI; + RegisterClassInfo RCI; + +public: + static char ID; + explicit AArch64A57FPLoadBalancing() : MachineFunctionPass(ID) {} + + bool runOnMachineFunction(MachineFunction &F) override; + + const char *getPassName() const override { + return "A57 FP Anti-dependency breaker"; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + MachineFunctionPass::getAnalysisUsage(AU); + } + +private: + bool runOnBasicBlock(MachineBasicBlock &MBB); + bool colorChainSet(std::vector GV, MachineBasicBlock &MBB, + int &Balance); + bool colorChain(Chain *G, Color C, MachineBasicBlock &MBB); + int scavengeRegister(Chain *G, Color C, MachineBasicBlock &MBB); + void scanInstruction(MachineInstr *MI, unsigned Idx, + std::map &Chains, + std::set &ChainSet); + void maybeKillChain(MachineOperand &MO, unsigned Idx, + std::map &RegChains); + Color getColor(unsigned Register); + Chain *getAndEraseNext(Color PreferredColor, std::vector &L); +}; +char AArch64A57FPLoadBalancing::ID = 0; + +/// A Chain is a sequence of instructions that are linked together by +/// an accumulation operand. For example: +/// +/// fmul d0, ? +/// fmla d1, ?, ?, d0 +/// fmla d2, ?, ?, d1 +/// +/// There may be other instructions interleaved in the sequence that +/// do not belong to the chain. These other instructions must not use +/// the "chain" register at any point. +/// +/// We currently only support chains where the "chain" operand is killed +/// at each link in the chain for simplicity. +/// A chain has three important instructions - Start, Last and Kill. +/// * The start instruction is the first instruction in the chain. +/// * Last is the final instruction in the chain. +/// * Kill may or may not be defined. If defined, Kill is the instruction +/// where the outgoing value of the Last instruction is killed. +/// This information is important as if we know the outgoing value is +/// killed with no intervening uses, we can safely change its register. +/// +/// Without a kill instruction, we must assume the outgoing value escapes +/// beyond our model and either must not change its register or must +/// create a fixup FMOV to keep the old register value consistent. +/// +class Chain { +public: + /// The important (marker) instructions. + MachineInstr *StartInst, *LastInst, *KillInst; + /// The index, from the start of the basic block, that each marker + /// appears. These are stored so we can do quick interval tests. + unsigned StartInstIdx, LastInstIdx, KillInstIdx; + /// All instructions in the chain. + std::set Insts; + /// True if KillInst cannot be modified. If this is true, + /// we cannot change LastInst's outgoing register. + /// This will be true for tied values and regmasks. + bool KillIsImmutable; + /// The "color" of LastInst. This will be the preferred chain color, + /// as changing intermediate nodes is easy but changing the last + /// instruction can be more tricky. + Color LastColor; + + Chain(MachineInstr *MI, unsigned Idx, Color C) : + StartInst(MI), LastInst(MI), KillInst(NULL), + StartInstIdx(Idx), LastInstIdx(Idx), KillInstIdx(0), + LastColor(C) { + Insts.insert(MI); + } + + /// Add a new instruction into the chain. The instruction's dest operand + /// has the given color. + void add(MachineInstr *MI, unsigned Idx, Color C) { + LastInst = MI; + LastInstIdx = Idx; + LastColor = C; + + Insts.insert(MI); + } + + /// Return true if MI is a member of the chain. + bool contains(MachineInstr *MI) { return Insts.count(MI) > 0; } + + /// Return the number of instructions in the chain. + unsigned size() const { + return Insts.size(); + } + + /// Inform the chain that its last active register (the dest register of + /// LastInst) is killed by MI with no intervening uses or defs. + void setKill(MachineInstr *MI, unsigned Idx, bool Immutable) { + KillInst = MI; + KillInstIdx = Idx; + KillIsImmutable = Immutable; + } + + /// Return the first instruction in the chain. + MachineInstr *getStart() const { return StartInst; } + /// Return the last instruction in the chain. + MachineInstr *getLast() const { return LastInst; } + /// Return the "kill" instruction (as set with setKill()) or NULL. + MachineInstr *getKill() const { return KillInst; } + /// Return an instruction that can be used as an iterator for the end + /// of the chain. This is the maximum of KillInst (if set) and LastInst. + MachineInstr *getEnd() const { + return ++MachineBasicBlock::iterator(KillInst ? KillInst : LastInst); + } + + /// Can the Kill instruction (assuming one exists) be modified? + bool isKillImmutable() const { return KillIsImmutable; } + + /// Return the preferred color of this chain. + Color getPreferredColor() { + if (OverrideBalance != 0) + return OverrideBalance == 1 ? Color::Even : Color::Odd; + return LastColor; + } + + /// Return true if this chain (StartInst..KillInst) overlaps with Other. + bool rangeOverlapsWith(Chain *Other) { + unsigned End = KillInst ? KillInstIdx : LastInstIdx; + unsigned OtherEnd = Other->KillInst ? + Other->KillInstIdx : Other->LastInstIdx; + + return StartInstIdx <= OtherEnd && Other->StartInstIdx <= End; + } + + /// Return true if this chain starts before Other. + bool startsBefore(Chain *Other) { + return StartInstIdx < Other->StartInstIdx; + } + + /// Return true if the group will require a fixup MOV at the end. + bool requiresFixup() const { + return (getKill() && isKillImmutable()) || !getKill(); + } + + /// Return a simple string representation of the chain. + std::string str() const { + std::string S; + raw_string_ostream OS(S); + + OS << "{"; + StartInst->print(OS, NULL, true); + OS << " -> "; + LastInst->print(OS, NULL, true); + if (KillInst) { + OS << " (kill @ "; + KillInst->print(OS, NULL, true); + OS << ")"; + } + OS << "}"; + + return OS.str(); + } + +}; + +} // end anonymous namespace + +//===----------------------------------------------------------------------===// + +bool AArch64A57FPLoadBalancing::runOnMachineFunction(MachineFunction &F) { + bool Changed = false; + DEBUG(dbgs() << "***** AArch64A57FPLoadBalancing *****\n"); + + const TargetMachine &TM = F.getTarget(); + MRI = &F.getRegInfo(); + TRI = F.getRegInfo().getTargetRegisterInfo(); + TII = TM.getSubtarget().getInstrInfo(); + RCI.runOnMachineFunction(F); + + for (auto &MBB : F) { + Changed |= runOnBasicBlock(MBB); + } + + return Changed; +} + +bool AArch64A57FPLoadBalancing::runOnBasicBlock(MachineBasicBlock &MBB) { + bool Changed = false; + DEBUG(dbgs() << "Running on MBB: " << MBB << " - scanning instructions...\n"); + + // First, scan the basic block producing a set of chains. + + // The currently "active" chains - chains that can be added to and haven't + // been killed yet. This is keyed by register - all chains can only have one + // "link" register between each inst in the chain. + std::map ActiveChains; + std::set AllChains; + unsigned Idx = 0; + for (auto &MI : MBB) + scanInstruction(&MI, Idx++, ActiveChains, AllChains); + + DEBUG(dbgs() << "Scan complete, "<< AllChains.size() << " chains created.\n"); + + // Group the chains into disjoint sets based on their liveness range. This is + // a poor-man's version of graph coloring. Ideally we'd create an interference + // graph and perform full-on graph coloring on that, but; + // (a) That's rather heavyweight for only two colors. + // (b) We expect multiple disjoint interference regions - in practice the live + // range of chains is quite small and they are clustered between loads + // and stores. + EquivalenceClasses EC; + for (auto *I : AllChains) + EC.insert(I); + + for (auto *I : AllChains) { + for (auto *J : AllChains) { + if (I != J && I->rangeOverlapsWith(J)) + EC.unionSets(I, J); + } + } + DEBUG(dbgs() << "Created " << EC.getNumClasses() << " disjoint sets.\n"); + + // Now we assume that every member of an equivalence class interferes + // with every other member of that class, and with no members of other classes. + + // Convert the EquivalenceClasses to a simpler set of sets. + std::vector > V; + for (auto I = EC.begin(), E = EC.end(); I != E; ++I) { + std::vector Cs(EC.member_begin(I), EC.member_end()); + if (Cs.empty()) continue; + V.push_back(Cs); + } + + // Now we have a set of sets, order them by start address so + // we can iterate over them sequentially. + std::sort(V.begin(), V.end(), + [](const std::vector &A, + const std::vector &B) { + return A.front()->startsBefore(B.front()); + }); + + // As we only have two colors, we can track the global (BB-level) balance of + // odds versus evens. We aim to keep this near zero to keep both execution + // units fed. + // Positive means we're even-heavy, negative we're odd-heavy. + // + // FIXME: If chains have interdependencies, for example: + // mul r0, r1, r2 + // mul r3, r0, r1 + // We do not model this and may color each one differently, assuming we'll + // get ILP when we obviously can't. This hasn't been seen to be a problem + // in practice so far, so we simplify the algorithm by ignoring it. + int Parity = 0; + + for (auto &I : V) + Changed |= colorChainSet(I, MBB, Parity); + + for (auto *C : AllChains) + delete C; + + return Changed; +} + +Chain *AArch64A57FPLoadBalancing::getAndEraseNext(Color PreferredColor, + std::vector &L) { + if (L.empty()) + return nullptr; + + // We try and get the best candidate from L to color next, given that our + // preferred color is "PreferredColor". L is ordered from larger to smaller + // chains. It is beneficial to color the large chains before the small chains, + // but if we can't find a chain of the maximum length with the preferred color, + // we fuzz the size and look for slightly smaller chains before giving up and + // returning a chain that must be recolored. + + // FIXME: Does this need to be configurable? + const unsigned SizeFuzz = 1; + unsigned MinSize = L.front()->size() - SizeFuzz; + for (auto I = L.begin(), E = L.end(); I != E; ++I) { + if ((*I)->size() <= MinSize) { + // We've gone past the size limit. Return the previous item. + Chain *Ch = *--I; + L.erase(I); + return Ch; + } + + if ((*I)->getPreferredColor() == PreferredColor) { + Chain *Ch = *I; + L.erase(I); + return Ch; + } + } + + // Bailout case - just return the first item. + Chain *Ch = L.front(); + L.erase(L.begin()); + return Ch; +} + +bool AArch64A57FPLoadBalancing::colorChainSet(std::vector GV, + MachineBasicBlock &MBB, + int &Parity) { + bool Changed = false; + DEBUG(dbgs() << "colorChainSet(): #sets=" << GV.size() << "\n"); + + // Sort by descending size order so that we allocate the most important + // sets first. + // Tie-break equivalent sizes by sorting chains requiring fixups before + // those without fixups. The logic here is that we should look at the + // chains that we cannot change before we look at those we can, + // so the parity counter is updated and we know what color we should + // change them to! + std::sort(GV.begin(), GV.end(), [](const Chain *G1, const Chain *G2) { + if (G1->size() != G2->size()) + return G1->size() > G2->size(); + return G1->requiresFixup() > G2->requiresFixup(); + }); + + Color PreferredColor = Parity < 0 ? Color::Even : Color::Odd; + while (Chain *G = getAndEraseNext(PreferredColor, GV)) { + // Start off by assuming we'll color to our own preferred color. + Color C = PreferredColor; + if (Parity == 0) + // But if we really don't care, use the chain's preferred color. + C = G->getPreferredColor(); + + DEBUG(dbgs() << " - Parity=" << Parity << ", Color=" + << ColorNames[(int)C] << "\n"); + + // If we'll need a fixup FMOV, don't bother. Testing has shown that this + // happens infrequently and when it does it has at least a 50% chance of + // slowing code down instead of speeding it up. + if (G->requiresFixup() && C != G->getPreferredColor()) { + C = G->getPreferredColor(); + DEBUG(dbgs() << " - " << G->str() << " - not worthwhile changing; " + "color remains " << ColorNames[(int)C] << "\n"); + } + + Changed |= colorChain(G, C, MBB); + + Parity += (C == Color::Even) ? G->size() : -G->size(); + PreferredColor = Parity < 0 ? Color::Even : Color::Odd; + } + + return Changed; +} + +int AArch64A57FPLoadBalancing::scavengeRegister(Chain *G, Color C, + MachineBasicBlock &MBB) { + RegScavenger RS; + RS.enterBasicBlock(&MBB); + RS.forward(MachineBasicBlock::iterator(G->getStart())); + + // Can we find an appropriate register that is available throughout the life + // of the chain? + unsigned RegClassID = G->getStart()->getDesc().OpInfo[0].RegClass; + BitVector AvailableRegs = RS.getRegsAvailable(TRI->getRegClass(RegClassID)); + for (MachineBasicBlock::iterator I = G->getStart(), E = G->getEnd(); + I != E; ++I) { + RS.forward(I); + AvailableRegs &= RS.getRegsAvailable(TRI->getRegClass(RegClassID)); + + // Remove any registers clobbered by a regmask. + for (auto J : I->operands()) { + if (J.isRegMask()) + AvailableRegs.clearBitsNotInMask(J.getRegMask()); + } + } + + // Make sure we allocate in-order, to get the cheapest registers first. + auto Ord = RCI.getOrder(TRI->getRegClass(RegClassID)); + for (auto Reg : Ord) { + if (!AvailableRegs[Reg]) + continue; + if ((C == Color::Even && (Reg % 2) == 0) || + (C == Color::Odd && (Reg % 2) == 1)) + return Reg; + } + + return -1; +} + +bool AArch64A57FPLoadBalancing::colorChain(Chain *G, Color C, + MachineBasicBlock &MBB) { + bool Changed = false; + DEBUG(dbgs() << " - colorChain(" << G->str() << ", " + << ColorNames[(int)C] << ")\n"); + + // Try and obtain a free register of the right class. Without a register + // to play with we cannot continue. + int Reg = scavengeRegister(G, C, MBB); + if (Reg == -1) { + DEBUG(dbgs() << "Scavenging (thus coloring) failed!\n"); + return false; + } + DEBUG(dbgs() << " - Scavenged register: " << TRI->getName(Reg) << "\n"); + + std::map Substs; + for (MachineBasicBlock::iterator I = G->getStart(), E = G->getEnd(); + I != E; ++I) { + if (!G->contains(I) && + (&*I != G->getKill() || G->isKillImmutable())) + continue; + + // I is a member of G, or I is a mutable instruction that kills G. + + std::vector ToErase; + for (auto &U : I->operands()) { + if (U.isReg() && U.isUse() && Substs.find(U.getReg()) != Substs.end()) { + unsigned OrigReg = U.getReg(); + U.setReg(Substs[OrigReg]); + if (U.isKill()) + // Don't erase straight away, because there may be other operands + // that also reference this substitution! + ToErase.push_back(OrigReg); + } else if (U.isRegMask()) { + for (auto J : Substs) { + if (U.clobbersPhysReg(J.first)) + ToErase.push_back(J.first); + } + } + } + // Now it's safe to remove the substs identified earlier. + for (auto J : ToErase) + Substs.erase(J); + + // Only change the def if this isn't the last instruction. + if (&*I != G->getKill()) { + MachineOperand &MO = I->getOperand(0); + + bool Change = TransformAll || getColor(MO.getReg()) != C; + if (G->requiresFixup() && &*I == G->getLast()) + Change = false; + + if (Change) { + Substs[MO.getReg()] = Reg; + MO.setReg(Reg); + MRI->setPhysRegUsed(Reg); + + Changed = true; + } + } + } + assert(Substs.size() == 0 && "No substitutions should be left active!"); + + if (G->getKill()) { + DEBUG(dbgs() << " - Kill instruction seen.\n"); + } else { + // We didn't have a kill instruction, but we didn't seem to need to change + // the destination register anyway. + DEBUG(dbgs() << " - Destination register not changed.\n"); + } + return Changed; +} + +void AArch64A57FPLoadBalancing:: +scanInstruction(MachineInstr *MI, unsigned Idx, + std::map &ActiveChains, + std::set &AllChains) { + // Inspect "MI", updating ActiveChains and AllChains. + + if (isMul(MI)) { + + for (auto &I : MI->operands()) + maybeKillChain(I, Idx, ActiveChains); + + // Create a new chain. Multiplies don't require forwarding so can go on any + // unit. + unsigned DestReg = MI->getOperand(0).getReg(); + + DEBUG(dbgs() << "New chain started for register " + << TRI->getName(DestReg) << " at " << *MI); + + Chain *G = new Chain(MI, Idx, getColor(DestReg)); + ActiveChains[DestReg] = G; + AllChains.insert(G); + + } else if (isMla(MI)) { + + // It is beneficial to keep MLAs on the same functional unit as their + // accumulator operand. + unsigned DestReg = MI->getOperand(0).getReg(); + unsigned AccumReg = MI->getOperand(3).getReg(); + + maybeKillChain(MI->getOperand(1), Idx, ActiveChains); + maybeKillChain(MI->getOperand(2), Idx, ActiveChains); + if (DestReg != AccumReg) + maybeKillChain(MI->getOperand(0), Idx, ActiveChains); + + if (ActiveChains.find(AccumReg) != ActiveChains.end()) { + DEBUG(dbgs() << "Chain found for accumulator register " + << TRI->getName(AccumReg) << " in MI " << *MI); + + // For simplicity we only chain together sequences of MULs/MLAs where the + // accumulator register is killed on each instruction. This means we don't + // need to track other uses of the registers we want to rewrite. + // + // FIXME: We could extend to handle the non-kill cases for more coverage. + if (MI->getOperand(3).isKill()) { + // Add to chain. + DEBUG(dbgs() << "Instruction was successfully added to chain.\n"); + ActiveChains[AccumReg]->add(MI, Idx, getColor(DestReg)); + // Handle cases where the destination is not the same as the accumulator. + ActiveChains[DestReg] = ActiveChains[AccumReg]; + return; + } + + DEBUG(dbgs() << "Cannot add to chain because accumulator operand wasn't " + << "marked !\n"); + maybeKillChain(MI->getOperand(3), Idx, ActiveChains); + } + + DEBUG(dbgs() << "Creating new chain for dest register " + << TRI->getName(DestReg) << "\n"); + Chain *G = new Chain(MI, Idx, getColor(DestReg)); + ActiveChains[DestReg] = G; + AllChains.insert(G); + + } else { + + // Non-MUL or MLA instruction. Invalidate any chain in the uses or defs + // lists. + for (auto &I : MI->operands()) + maybeKillChain(I, Idx, ActiveChains); + + } +} + +void AArch64A57FPLoadBalancing:: +maybeKillChain(MachineOperand &MO, unsigned Idx, + std::map &ActiveChains) { + // Given an operand and the set of active chains (keyed by register), + // determine if a chain should be ended and remove from ActiveChains. + MachineInstr *MI = MO.getParent(); + + if (MO.isReg()) { + + // If this is a KILL of a current chain, record it. + if (MO.isKill() && ActiveChains.find(MO.getReg()) != ActiveChains.end()) { + DEBUG(dbgs() << "Kill seen for chain " << TRI->getName(MO.getReg()) + << "\n"); + ActiveChains[MO.getReg()]->setKill(MI, Idx, /*Immutable=*/MO.isTied()); + } + ActiveChains.erase(MO.getReg()); + + } else if (MO.isRegMask()) { + + for (auto I = ActiveChains.begin(), E = ActiveChains.end(); + I != E; ++I) { + if (MO.clobbersPhysReg(I->first)) { + DEBUG(dbgs() << "Kill (regmask) seen for chain " + << TRI->getName(I->first) << "\n"); + I->second->setKill(MI, Idx, /*Immutable=*/true); + ActiveChains.erase(I); + } + } + + } +} + +Color AArch64A57FPLoadBalancing::getColor(unsigned Reg) { + if ((TRI->getEncodingValue(Reg) % 2) == 0) + return Color::Even; + else + return Color::Odd; +} + +// Factory function used by AArch64TargetMachine to add the pass to the passmanager. +FunctionPass *llvm::createAArch64A57FPLoadBalancing() { + return new AArch64A57FPLoadBalancing(); +} diff --git a/lib/Target/AArch64/AArch64InstrFormats.td b/lib/Target/AArch64/AArch64InstrFormats.td index 5007172..4876c7d 100644 --- a/lib/Target/AArch64/AArch64InstrFormats.td +++ b/lib/Target/AArch64/AArch64InstrFormats.td @@ -1624,7 +1624,7 @@ class AddSubRegAlias { - let hasSideEffects = 0 in { + let hasSideEffects = 0, isReMaterializable = 1, isAsCheapAsAMove = 1 in { // Add/Subtract immediate def Wri : BaseAddSubImm { @@ -1949,14 +1949,14 @@ class LogicalRegAlias multiclass LogicalImm opc, string mnemonic, SDNode OpNode, string Alias> { - let AddedComplexity = 6 in + let AddedComplexity = 6, isReMaterializable = 1, isAsCheapAsAMove = 1 in def Wri : BaseLogicalImm { let Inst{31} = 0; let Inst{22} = 0; // 64-bit version has an additional bit of immediate. } - let AddedComplexity = 6 in + let AddedComplexity = 6, isReMaterializable = 1, isAsCheapAsAMove = 1 in def Xri : BaseLogicalImm { @@ -2001,8 +2001,10 @@ class BaseLogicalRegPseudo // Split from LogicalImm as not all instructions have both. multiclass LogicalReg opc, bit N, string mnemonic, SDPatternOperator OpNode> { + let isReMaterializable = 1, isAsCheapAsAMove = 1 in { def Wrr : BaseLogicalRegPseudo; def Xrr : BaseLogicalRegPseudo; + } def Wrs : BaseLogicalSRegisAsCheapAsAMove(); + + switch (MI->getOpcode()) { + default: + return false; + + // add/sub on register without shift + case AArch64::ADDWri: + case AArch64::ADDXri: + case AArch64::SUBWri: + case AArch64::SUBXri: + return (MI->getOperand(3).getImm() == 0); + + // logical ops on immediate + case AArch64::ANDWri: + case AArch64::ANDXri: + case AArch64::EORWri: + case AArch64::EORXri: + case AArch64::ORRWri: + case AArch64::ORRXri: + return true; + + // logical ops on register without shift + case AArch64::ANDWrr: + case AArch64::ANDXrr: + case AArch64::BICWrr: + case AArch64::BICXrr: + case AArch64::EONWrr: + case AArch64::EONXrr: + case AArch64::EORWrr: + case AArch64::EORXrr: + case AArch64::ORNWrr: + case AArch64::ORNXrr: + case AArch64::ORRWrr: + case AArch64::ORRXrr: + return true; + } + + llvm_unreachable("Unknown opcode to check as cheap as a move!"); +} + bool AArch64InstrInfo::isCoalescableExtInstr(const MachineInstr &MI, unsigned &SrcReg, unsigned &DstReg, unsigned &SubIdx) const { diff --git a/lib/Target/AArch64/AArch64InstrInfo.h b/lib/Target/AArch64/AArch64InstrInfo.h index f70b82b..b27565e 100644 --- a/lib/Target/AArch64/AArch64InstrInfo.h +++ b/lib/Target/AArch64/AArch64InstrInfo.h @@ -46,6 +46,8 @@ public: unsigned GetInstSizeInBytes(const MachineInstr *MI) const; + bool isAsCheapAsAMove(const MachineInstr *MI) const override; + bool isCoalescableExtInstr(const MachineInstr &MI, unsigned &SrcReg, unsigned &DstReg, unsigned &SubIdx) const override; diff --git a/lib/Target/AArch64/AArch64Subtarget.h b/lib/Target/AArch64/AArch64Subtarget.h index 52124f6..10c646d 100644 --- a/lib/Target/AArch64/AArch64Subtarget.h +++ b/lib/Target/AArch64/AArch64Subtarget.h @@ -100,6 +100,8 @@ public: bool isTargetMachO() const { return TargetTriple.isOSBinFormatMachO(); } bool isCyclone() const { return CPUString == "cyclone"; } + bool isCortexA57() const { return CPUString == "cortex-a57"; } + bool isCortexA53() const { return CPUString == "cortex-a53"; } /// getMaxInlineSizeThreshold - Returns the maximum memset / memcpy size /// that still makes it profitable to inline the call. diff --git a/lib/Target/AArch64/AArch64TargetMachine.cpp b/lib/Target/AArch64/AArch64TargetMachine.cpp index f99b90b..722e5e7 100644 --- a/lib/Target/AArch64/AArch64TargetMachine.cpp +++ b/lib/Target/AArch64/AArch64TargetMachine.cpp @@ -59,6 +59,17 @@ EnableAtomicTidy("aarch64-atomic-cfg-tidy", cl::Hidden, " to make use of cmpxchg flow-based information"), cl::init(true)); +static cl::opt +EnableEarlyIfConversion("aarch64-enable-early-ifcvt", cl::Hidden, + cl::desc("Run early if-conversion"), + cl::init(true)); + + +static cl::opt +EnableA53Fix835769("aarch64-fix-cortex-a53-835769", cl::Hidden, + cl::desc("Work around Cortex-A53 erratum 835769"), + cl::init(false)); + extern "C" void LLVMInitializeAArch64Target() { // Register the target. RegisterTargetMachine X(TheAArch64leTarget); @@ -176,7 +187,8 @@ bool AArch64PassConfig::addInstSelector() { bool AArch64PassConfig::addILPOpts() { if (EnableCCMP) addPass(createAArch64ConditionalCompares()); - addPass(&EarlyIfConverterID); + if (EnableEarlyIfConversion) + addPass(&EarlyIfConverterID); if (EnableStPairSuppress) addPass(createAArch64StorePairSuppressPass()); return true; @@ -193,6 +205,10 @@ bool AArch64PassConfig::addPostRegAlloc() { // Change dead register definitions to refer to the zero register. if (TM->getOptLevel() != CodeGenOpt::None && EnableDeadRegisterElimination) addPass(createAArch64DeadRegisterDefinitions()); + if (TM->getOptLevel() != CodeGenOpt::None && + TM->getSubtarget().isCortexA57()) + // Improve performance for some FP/SIMD code for A57. + addPass(createAArch64A57FPLoadBalancing()); return true; } @@ -206,6 +222,8 @@ bool AArch64PassConfig::addPreSched2() { } bool AArch64PassConfig::addPreEmitPass() { + if (EnableA53Fix835769) + addPass(createAArch64A53Fix835769()); // Relax conditional branch instructions if they're otherwise out of // range of their destination. addPass(createAArch64BranchRelaxation()); diff --git a/lib/Target/AArch64/Android.mk b/lib/Target/AArch64/Android.mk index 6b29c77..d7b3317 100644 --- a/lib/Target/AArch64/Android.mk +++ b/lib/Target/AArch64/Android.mk @@ -15,6 +15,8 @@ aarch64_codegen_TBLGEN_TABLES := \ AArch64GenMCPseudoLowering.inc \ aarch64_codegen_SRC_FILES := \ + AArch64A53Fix835769.cpp \ + AArch64A57FPLoadBalancing.cpp \ AArch64AddressTypePromotion.cpp \ AArch64AdvSIMDScalarPass.cpp \ AArch64AsmPrinter.cpp \ diff --git a/lib/Target/AArch64/CMakeLists.txt b/lib/Target/AArch64/CMakeLists.txt index 789d549..c2f0488 100644 --- a/lib/Target/AArch64/CMakeLists.txt +++ b/lib/Target/AArch64/CMakeLists.txt @@ -15,6 +15,7 @@ tablegen(LLVM AArch64GenDisassemblerTables.inc -gen-disassembler) add_public_tablegen_target(AArch64CommonTableGen) add_llvm_target(AArch64CodeGen + AArch64A57FPLoadBalancing.cpp AArch64AddressTypePromotion.cpp AArch64AdvSIMDScalarPass.cpp AArch64AsmPrinter.cpp @@ -25,6 +26,7 @@ add_llvm_target(AArch64CodeGen AArch64DeadRegisterDefinitionsPass.cpp AArch64ExpandPseudoInsts.cpp AArch64FastISel.cpp + AArch64A53Fix835769.cpp AArch64FrameLowering.cpp AArch64ISelDAGToDAG.cpp AArch64ISelLowering.cpp -- cgit v1.1