109467b48Spatrick //===- HexagonHardwareLoops.cpp - Identify and generate hardware loops ----===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick //
909467b48Spatrick // This pass identifies loops where we can generate the Hexagon hardware
1009467b48Spatrick // loop instruction. The hardware loop can perform loop branches with a
1109467b48Spatrick // zero-cycle overhead.
1209467b48Spatrick //
1309467b48Spatrick // The pattern that defines the induction variable can changed depending on
1409467b48Spatrick // prior optimizations. For example, the IndVarSimplify phase run by 'opt'
1509467b48Spatrick // normalizes induction variables, and the Loop Strength Reduction pass
1609467b48Spatrick // run by 'llc' may also make changes to the induction variable.
1709467b48Spatrick // The pattern detected by this phase is due to running Strength Reduction.
1809467b48Spatrick //
1909467b48Spatrick // Criteria for hardware loops:
2009467b48Spatrick // - Countable loops (w/ ind. var for a trip count)
2109467b48Spatrick // - Assumes loops are normalized by IndVarSimplify
2209467b48Spatrick // - Try inner-most loops first
2309467b48Spatrick // - No function calls in loops.
2409467b48Spatrick //
2509467b48Spatrick //===----------------------------------------------------------------------===//
2609467b48Spatrick
2709467b48Spatrick #include "HexagonInstrInfo.h"
2809467b48Spatrick #include "HexagonSubtarget.h"
2909467b48Spatrick #include "llvm/ADT/ArrayRef.h"
3009467b48Spatrick #include "llvm/ADT/STLExtras.h"
3109467b48Spatrick #include "llvm/ADT/SmallSet.h"
3209467b48Spatrick #include "llvm/ADT/SmallVector.h"
3309467b48Spatrick #include "llvm/ADT/Statistic.h"
3409467b48Spatrick #include "llvm/ADT/StringRef.h"
3509467b48Spatrick #include "llvm/CodeGen/MachineBasicBlock.h"
3609467b48Spatrick #include "llvm/CodeGen/MachineDominators.h"
3709467b48Spatrick #include "llvm/CodeGen/MachineFunction.h"
3809467b48Spatrick #include "llvm/CodeGen/MachineFunctionPass.h"
3909467b48Spatrick #include "llvm/CodeGen/MachineInstr.h"
4009467b48Spatrick #include "llvm/CodeGen/MachineInstrBuilder.h"
4109467b48Spatrick #include "llvm/CodeGen/MachineLoopInfo.h"
4209467b48Spatrick #include "llvm/CodeGen/MachineOperand.h"
4309467b48Spatrick #include "llvm/CodeGen/MachineRegisterInfo.h"
4409467b48Spatrick #include "llvm/CodeGen/TargetRegisterInfo.h"
4509467b48Spatrick #include "llvm/IR/Constants.h"
4609467b48Spatrick #include "llvm/IR/DebugLoc.h"
4709467b48Spatrick #include "llvm/InitializePasses.h"
4809467b48Spatrick #include "llvm/Pass.h"
4909467b48Spatrick #include "llvm/Support/CommandLine.h"
5009467b48Spatrick #include "llvm/Support/Debug.h"
5109467b48Spatrick #include "llvm/Support/ErrorHandling.h"
5209467b48Spatrick #include "llvm/Support/MathExtras.h"
5309467b48Spatrick #include "llvm/Support/raw_ostream.h"
5409467b48Spatrick #include <cassert>
5509467b48Spatrick #include <cstdint>
5609467b48Spatrick #include <cstdlib>
5709467b48Spatrick #include <iterator>
5809467b48Spatrick #include <map>
5909467b48Spatrick #include <set>
6009467b48Spatrick #include <string>
6109467b48Spatrick #include <utility>
6209467b48Spatrick #include <vector>
6309467b48Spatrick
6409467b48Spatrick using namespace llvm;
6509467b48Spatrick
6609467b48Spatrick #define DEBUG_TYPE "hwloops"
6709467b48Spatrick
6809467b48Spatrick #ifndef NDEBUG
6909467b48Spatrick static cl::opt<int> HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1));
7009467b48Spatrick
7109467b48Spatrick // Option to create preheader only for a specific function.
7209467b48Spatrick static cl::opt<std::string> PHFn("hexagon-hwloop-phfn", cl::Hidden,
7309467b48Spatrick cl::init(""));
7409467b48Spatrick #endif
7509467b48Spatrick
7609467b48Spatrick // Option to create a preheader if one doesn't exist.
7709467b48Spatrick static cl::opt<bool> HWCreatePreheader("hexagon-hwloop-preheader",
7809467b48Spatrick cl::Hidden, cl::init(true),
7909467b48Spatrick cl::desc("Add a preheader to a hardware loop if one doesn't exist"));
8009467b48Spatrick
8109467b48Spatrick // Turn it off by default. If a preheader block is not created here, the
8209467b48Spatrick // software pipeliner may be unable to find a block suitable to serve as
8309467b48Spatrick // a preheader. In that case SWP will not run.
84*d415bd75Srobert static cl::opt<bool> SpecPreheader("hwloop-spec-preheader", cl::Hidden,
85*d415bd75Srobert cl::desc("Allow speculation of preheader "
8609467b48Spatrick "instructions"));
8709467b48Spatrick
8809467b48Spatrick STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
8909467b48Spatrick
9009467b48Spatrick namespace llvm {
9109467b48Spatrick
9209467b48Spatrick FunctionPass *createHexagonHardwareLoops();
9309467b48Spatrick void initializeHexagonHardwareLoopsPass(PassRegistry&);
9409467b48Spatrick
9509467b48Spatrick } // end namespace llvm
9609467b48Spatrick
9709467b48Spatrick namespace {
9809467b48Spatrick
9909467b48Spatrick class CountValue;
10009467b48Spatrick
10109467b48Spatrick struct HexagonHardwareLoops : public MachineFunctionPass {
10209467b48Spatrick MachineLoopInfo *MLI;
10309467b48Spatrick MachineRegisterInfo *MRI;
10409467b48Spatrick MachineDominatorTree *MDT;
10509467b48Spatrick const HexagonInstrInfo *TII;
10609467b48Spatrick const HexagonRegisterInfo *TRI;
10709467b48Spatrick #ifndef NDEBUG
10809467b48Spatrick static int Counter;
10909467b48Spatrick #endif
11009467b48Spatrick
11109467b48Spatrick public:
11209467b48Spatrick static char ID;
11309467b48Spatrick
HexagonHardwareLoops__anon6c38a3910111::HexagonHardwareLoops11409467b48Spatrick HexagonHardwareLoops() : MachineFunctionPass(ID) {}
11509467b48Spatrick
11609467b48Spatrick bool runOnMachineFunction(MachineFunction &MF) override;
11709467b48Spatrick
getPassName__anon6c38a3910111::HexagonHardwareLoops11809467b48Spatrick StringRef getPassName() const override { return "Hexagon Hardware Loops"; }
11909467b48Spatrick
getAnalysisUsage__anon6c38a3910111::HexagonHardwareLoops12009467b48Spatrick void getAnalysisUsage(AnalysisUsage &AU) const override {
12109467b48Spatrick AU.addRequired<MachineDominatorTree>();
12209467b48Spatrick AU.addRequired<MachineLoopInfo>();
12309467b48Spatrick MachineFunctionPass::getAnalysisUsage(AU);
12409467b48Spatrick }
12509467b48Spatrick
12609467b48Spatrick private:
127*d415bd75Srobert using LoopFeederMap = std::map<Register, MachineInstr *>;
12809467b48Spatrick
12909467b48Spatrick /// Kinds of comparisons in the compare instructions.
13009467b48Spatrick struct Comparison {
13109467b48Spatrick enum Kind {
13209467b48Spatrick EQ = 0x01,
13309467b48Spatrick NE = 0x02,
13409467b48Spatrick L = 0x04,
13509467b48Spatrick G = 0x08,
13609467b48Spatrick U = 0x40,
13709467b48Spatrick LTs = L,
13809467b48Spatrick LEs = L | EQ,
13909467b48Spatrick GTs = G,
14009467b48Spatrick GEs = G | EQ,
14109467b48Spatrick LTu = L | U,
14209467b48Spatrick LEu = L | EQ | U,
14309467b48Spatrick GTu = G | U,
14409467b48Spatrick GEu = G | EQ | U
14509467b48Spatrick };
14609467b48Spatrick
getSwappedComparison__anon6c38a3910111::HexagonHardwareLoops::Comparison14709467b48Spatrick static Kind getSwappedComparison(Kind Cmp) {
14809467b48Spatrick assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator");
14909467b48Spatrick if ((Cmp & L) || (Cmp & G))
15009467b48Spatrick return (Kind)(Cmp ^ (L|G));
15109467b48Spatrick return Cmp;
15209467b48Spatrick }
15309467b48Spatrick
getNegatedComparison__anon6c38a3910111::HexagonHardwareLoops::Comparison15409467b48Spatrick static Kind getNegatedComparison(Kind Cmp) {
15509467b48Spatrick if ((Cmp & L) || (Cmp & G))
15609467b48Spatrick return (Kind)((Cmp ^ (L | G)) ^ EQ);
15709467b48Spatrick if ((Cmp & NE) || (Cmp & EQ))
15809467b48Spatrick return (Kind)(Cmp ^ (EQ | NE));
15909467b48Spatrick return (Kind)0;
16009467b48Spatrick }
16109467b48Spatrick
isSigned__anon6c38a3910111::HexagonHardwareLoops::Comparison16209467b48Spatrick static bool isSigned(Kind Cmp) {
16309467b48Spatrick return (Cmp & (L | G) && !(Cmp & U));
16409467b48Spatrick }
16509467b48Spatrick
isUnsigned__anon6c38a3910111::HexagonHardwareLoops::Comparison16609467b48Spatrick static bool isUnsigned(Kind Cmp) {
16709467b48Spatrick return (Cmp & U);
16809467b48Spatrick }
16909467b48Spatrick };
17009467b48Spatrick
17109467b48Spatrick /// Find the register that contains the loop controlling
17209467b48Spatrick /// induction variable.
17309467b48Spatrick /// If successful, it will return true and set the \p Reg, \p IVBump
17409467b48Spatrick /// and \p IVOp arguments. Otherwise it will return false.
17509467b48Spatrick /// The returned induction register is the register R that follows the
17609467b48Spatrick /// following induction pattern:
17709467b48Spatrick /// loop:
17809467b48Spatrick /// R = phi ..., [ R.next, LatchBlock ]
17909467b48Spatrick /// R.next = R + #bump
18009467b48Spatrick /// if (R.next < #N) goto loop
18109467b48Spatrick /// IVBump is the immediate value added to R, and IVOp is the instruction
18209467b48Spatrick /// "R.next = R + #bump".
183*d415bd75Srobert bool findInductionRegister(MachineLoop *L, Register &Reg,
18409467b48Spatrick int64_t &IVBump, MachineInstr *&IVOp) const;
18509467b48Spatrick
18609467b48Spatrick /// Return the comparison kind for the specified opcode.
18709467b48Spatrick Comparison::Kind getComparisonKind(unsigned CondOpc,
18809467b48Spatrick MachineOperand *InitialValue,
18909467b48Spatrick const MachineOperand *Endvalue,
19009467b48Spatrick int64_t IVBump) const;
19109467b48Spatrick
19209467b48Spatrick /// Analyze the statements in a loop to determine if the loop
19309467b48Spatrick /// has a computable trip count and, if so, return a value that represents
19409467b48Spatrick /// the trip count expression.
19509467b48Spatrick CountValue *getLoopTripCount(MachineLoop *L,
19609467b48Spatrick SmallVectorImpl<MachineInstr *> &OldInsts);
19709467b48Spatrick
19809467b48Spatrick /// Return the expression that represents the number of times
19909467b48Spatrick /// a loop iterates. The function takes the operands that represent the
20009467b48Spatrick /// loop start value, loop end value, and induction value. Based upon
20109467b48Spatrick /// these operands, the function attempts to compute the trip count.
20209467b48Spatrick /// If the trip count is not directly available (as an immediate value,
20309467b48Spatrick /// or a register), the function will attempt to insert computation of it
20409467b48Spatrick /// to the loop's preheader.
20509467b48Spatrick CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start,
206*d415bd75Srobert const MachineOperand *End, Register IVReg,
20709467b48Spatrick int64_t IVBump, Comparison::Kind Cmp) const;
20809467b48Spatrick
20909467b48Spatrick /// Return true if the instruction is not valid within a hardware
21009467b48Spatrick /// loop.
21109467b48Spatrick bool isInvalidLoopOperation(const MachineInstr *MI,
21209467b48Spatrick bool IsInnerHWLoop) const;
21309467b48Spatrick
21409467b48Spatrick /// Return true if the loop contains an instruction that inhibits
21509467b48Spatrick /// using the hardware loop.
21609467b48Spatrick bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const;
21709467b48Spatrick
21809467b48Spatrick /// Given a loop, check if we can convert it to a hardware loop.
21909467b48Spatrick /// If so, then perform the conversion and return true.
22009467b48Spatrick bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used);
22109467b48Spatrick
22209467b48Spatrick /// Return true if the instruction is now dead.
22309467b48Spatrick bool isDead(const MachineInstr *MI,
22409467b48Spatrick SmallVectorImpl<MachineInstr *> &DeadPhis) const;
22509467b48Spatrick
22609467b48Spatrick /// Remove the instruction if it is now dead.
22709467b48Spatrick void removeIfDead(MachineInstr *MI);
22809467b48Spatrick
22909467b48Spatrick /// Make sure that the "bump" instruction executes before the
23009467b48Spatrick /// compare. We need that for the IV fixup, so that the compare
23109467b48Spatrick /// instruction would not use a bumped value that has not yet been
23209467b48Spatrick /// defined. If the instructions are out of order, try to reorder them.
23309467b48Spatrick bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI);
23409467b48Spatrick
23509467b48Spatrick /// Return true if MO and MI pair is visited only once. If visited
23609467b48Spatrick /// more than once, this indicates there is recursion. In such a case,
23709467b48Spatrick /// return false.
23809467b48Spatrick bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI,
23909467b48Spatrick const MachineOperand *MO,
24009467b48Spatrick LoopFeederMap &LoopFeederPhi) const;
24109467b48Spatrick
24209467b48Spatrick /// Return true if the Phi may generate a value that may underflow,
24309467b48Spatrick /// or may wrap.
24409467b48Spatrick bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal,
24509467b48Spatrick MachineBasicBlock *MBB, MachineLoop *L,
24609467b48Spatrick LoopFeederMap &LoopFeederPhi) const;
24709467b48Spatrick
24809467b48Spatrick /// Return true if the induction variable may underflow an unsigned
24909467b48Spatrick /// value in the first iteration.
25009467b48Spatrick bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal,
25109467b48Spatrick const MachineOperand *EndVal,
25209467b48Spatrick MachineBasicBlock *MBB, MachineLoop *L,
25309467b48Spatrick LoopFeederMap &LoopFeederPhi) const;
25409467b48Spatrick
25509467b48Spatrick /// Check if the given operand has a compile-time known constant
25609467b48Spatrick /// value. Return true if yes, and false otherwise. When returning true, set
25709467b48Spatrick /// Val to the corresponding constant value.
25809467b48Spatrick bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const;
25909467b48Spatrick
26009467b48Spatrick /// Check if the operand has a compile-time known constant value.
isImmediate__anon6c38a3910111::HexagonHardwareLoops26109467b48Spatrick bool isImmediate(const MachineOperand &MO) const {
26209467b48Spatrick int64_t V;
26309467b48Spatrick return checkForImmediate(MO, V);
26409467b48Spatrick }
26509467b48Spatrick
26609467b48Spatrick /// Return the immediate for the specified operand.
getImmediate__anon6c38a3910111::HexagonHardwareLoops26709467b48Spatrick int64_t getImmediate(const MachineOperand &MO) const {
26809467b48Spatrick int64_t V;
26909467b48Spatrick if (!checkForImmediate(MO, V))
27009467b48Spatrick llvm_unreachable("Invalid operand");
27109467b48Spatrick return V;
27209467b48Spatrick }
27309467b48Spatrick
27409467b48Spatrick /// Reset the given machine operand to now refer to a new immediate
27509467b48Spatrick /// value. Assumes that the operand was already referencing an immediate
27609467b48Spatrick /// value, either directly, or via a register.
27709467b48Spatrick void setImmediate(MachineOperand &MO, int64_t Val);
27809467b48Spatrick
27909467b48Spatrick /// Fix the data flow of the induction variable.
28009467b48Spatrick /// The desired flow is: phi ---> bump -+-> comparison-in-latch.
28109467b48Spatrick /// |
28209467b48Spatrick /// +-> back to phi
28309467b48Spatrick /// where "bump" is the increment of the induction variable:
28409467b48Spatrick /// iv = iv + #const.
28509467b48Spatrick /// Due to some prior code transformations, the actual flow may look
28609467b48Spatrick /// like this:
28709467b48Spatrick /// phi -+-> bump ---> back to phi
28809467b48Spatrick /// |
28909467b48Spatrick /// +-> comparison-in-latch (against upper_bound-bump),
29009467b48Spatrick /// i.e. the comparison that controls the loop execution may be using
29109467b48Spatrick /// the value of the induction variable from before the increment.
29209467b48Spatrick ///
29309467b48Spatrick /// Return true if the loop's flow is the desired one (i.e. it's
29409467b48Spatrick /// either been fixed, or no fixing was necessary).
29509467b48Spatrick /// Otherwise, return false. This can happen if the induction variable
29609467b48Spatrick /// couldn't be identified, or if the value in the latch's comparison
29709467b48Spatrick /// cannot be adjusted to reflect the post-bump value.
29809467b48Spatrick bool fixupInductionVariable(MachineLoop *L);
29909467b48Spatrick
30009467b48Spatrick /// Given a loop, if it does not have a preheader, create one.
30109467b48Spatrick /// Return the block that is the preheader.
30209467b48Spatrick MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
30309467b48Spatrick };
30409467b48Spatrick
30509467b48Spatrick char HexagonHardwareLoops::ID = 0;
30609467b48Spatrick #ifndef NDEBUG
30709467b48Spatrick int HexagonHardwareLoops::Counter = 0;
30809467b48Spatrick #endif
30909467b48Spatrick
31009467b48Spatrick /// Abstraction for a trip count of a loop. A smaller version
31109467b48Spatrick /// of the MachineOperand class without the concerns of changing the
31209467b48Spatrick /// operand representation.
31309467b48Spatrick class CountValue {
31409467b48Spatrick public:
31509467b48Spatrick enum CountValueType {
31609467b48Spatrick CV_Register,
31709467b48Spatrick CV_Immediate
31809467b48Spatrick };
31909467b48Spatrick
32009467b48Spatrick private:
32109467b48Spatrick CountValueType Kind;
32209467b48Spatrick union Values {
Values()323*d415bd75Srobert Values() : R{Register(), 0} {}
324*d415bd75Srobert Values(const Values&) = default;
32509467b48Spatrick struct {
326*d415bd75Srobert Register Reg;
32709467b48Spatrick unsigned Sub;
32809467b48Spatrick } R;
32909467b48Spatrick unsigned ImmVal;
33009467b48Spatrick } Contents;
33109467b48Spatrick
33209467b48Spatrick public:
CountValue(CountValueType t,Register v,unsigned u=0)333*d415bd75Srobert explicit CountValue(CountValueType t, Register v, unsigned u = 0) {
33409467b48Spatrick Kind = t;
33509467b48Spatrick if (Kind == CV_Register) {
33609467b48Spatrick Contents.R.Reg = v;
33709467b48Spatrick Contents.R.Sub = u;
33809467b48Spatrick } else {
33909467b48Spatrick Contents.ImmVal = v;
34009467b48Spatrick }
34109467b48Spatrick }
34209467b48Spatrick
isReg() const34309467b48Spatrick bool isReg() const { return Kind == CV_Register; }
isImm() const34409467b48Spatrick bool isImm() const { return Kind == CV_Immediate; }
34509467b48Spatrick
getReg() const346*d415bd75Srobert Register getReg() const {
34709467b48Spatrick assert(isReg() && "Wrong CountValue accessor");
34809467b48Spatrick return Contents.R.Reg;
34909467b48Spatrick }
35009467b48Spatrick
getSubReg() const35109467b48Spatrick unsigned getSubReg() const {
35209467b48Spatrick assert(isReg() && "Wrong CountValue accessor");
35309467b48Spatrick return Contents.R.Sub;
35409467b48Spatrick }
35509467b48Spatrick
getImm() const35609467b48Spatrick unsigned getImm() const {
35709467b48Spatrick assert(isImm() && "Wrong CountValue accessor");
35809467b48Spatrick return Contents.ImmVal;
35909467b48Spatrick }
36009467b48Spatrick
print(raw_ostream & OS,const TargetRegisterInfo * TRI=nullptr) const36109467b48Spatrick void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const {
36209467b48Spatrick if (isReg()) { OS << printReg(Contents.R.Reg, TRI, Contents.R.Sub); }
36309467b48Spatrick if (isImm()) { OS << Contents.ImmVal; }
36409467b48Spatrick }
36509467b48Spatrick };
36609467b48Spatrick
36709467b48Spatrick } // end anonymous namespace
36809467b48Spatrick
36909467b48Spatrick INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
37009467b48Spatrick "Hexagon Hardware Loops", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)37109467b48Spatrick INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
37209467b48Spatrick INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
37309467b48Spatrick INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
37409467b48Spatrick "Hexagon Hardware Loops", false, false)
37509467b48Spatrick
37609467b48Spatrick FunctionPass *llvm::createHexagonHardwareLoops() {
37709467b48Spatrick return new HexagonHardwareLoops();
37809467b48Spatrick }
37909467b48Spatrick
runOnMachineFunction(MachineFunction & MF)38009467b48Spatrick bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) {
38109467b48Spatrick LLVM_DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n");
38209467b48Spatrick if (skipFunction(MF.getFunction()))
38309467b48Spatrick return false;
38409467b48Spatrick
38509467b48Spatrick bool Changed = false;
38609467b48Spatrick
38709467b48Spatrick MLI = &getAnalysis<MachineLoopInfo>();
38809467b48Spatrick MRI = &MF.getRegInfo();
38909467b48Spatrick MDT = &getAnalysis<MachineDominatorTree>();
39009467b48Spatrick const HexagonSubtarget &HST = MF.getSubtarget<HexagonSubtarget>();
39109467b48Spatrick TII = HST.getInstrInfo();
39209467b48Spatrick TRI = HST.getRegisterInfo();
39309467b48Spatrick
39409467b48Spatrick for (auto &L : *MLI)
39573471bf0Spatrick if (L->isOutermost()) {
39609467b48Spatrick bool L0Used = false;
39709467b48Spatrick bool L1Used = false;
39809467b48Spatrick Changed |= convertToHardwareLoop(L, L0Used, L1Used);
39909467b48Spatrick }
40009467b48Spatrick
40109467b48Spatrick return Changed;
40209467b48Spatrick }
40309467b48Spatrick
findInductionRegister(MachineLoop * L,Register & Reg,int64_t & IVBump,MachineInstr * & IVOp) const40409467b48Spatrick bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
405*d415bd75Srobert Register &Reg,
40609467b48Spatrick int64_t &IVBump,
40709467b48Spatrick MachineInstr *&IVOp
40809467b48Spatrick ) const {
40909467b48Spatrick MachineBasicBlock *Header = L->getHeader();
41009467b48Spatrick MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
41109467b48Spatrick MachineBasicBlock *Latch = L->getLoopLatch();
41209467b48Spatrick MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
41309467b48Spatrick if (!Header || !Preheader || !Latch || !ExitingBlock)
41409467b48Spatrick return false;
41509467b48Spatrick
41609467b48Spatrick // This pair represents an induction register together with an immediate
41709467b48Spatrick // value that will be added to it in each loop iteration.
418*d415bd75Srobert using RegisterBump = std::pair<Register, int64_t>;
41909467b48Spatrick
42009467b48Spatrick // Mapping: R.next -> (R, bump), where R, R.next and bump are derived
42109467b48Spatrick // from an induction operation
42209467b48Spatrick // R.next = R + bump
42309467b48Spatrick // where bump is an immediate value.
424*d415bd75Srobert using InductionMap = std::map<Register, RegisterBump>;
42509467b48Spatrick
42609467b48Spatrick InductionMap IndMap;
42709467b48Spatrick
42809467b48Spatrick using instr_iterator = MachineBasicBlock::instr_iterator;
42909467b48Spatrick
43009467b48Spatrick for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
43109467b48Spatrick I != E && I->isPHI(); ++I) {
43209467b48Spatrick MachineInstr *Phi = &*I;
43309467b48Spatrick
43409467b48Spatrick // Have a PHI instruction. Get the operand that corresponds to the
43509467b48Spatrick // latch block, and see if is a result of an addition of form "reg+imm",
43609467b48Spatrick // where the "reg" is defined by the PHI node we are looking at.
43709467b48Spatrick for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
43809467b48Spatrick if (Phi->getOperand(i+1).getMBB() != Latch)
43909467b48Spatrick continue;
44009467b48Spatrick
44109467b48Spatrick Register PhiOpReg = Phi->getOperand(i).getReg();
44209467b48Spatrick MachineInstr *DI = MRI->getVRegDef(PhiOpReg);
44309467b48Spatrick
44409467b48Spatrick if (DI->getDesc().isAdd()) {
44509467b48Spatrick // If the register operand to the add is the PHI we're looking at, this
44609467b48Spatrick // meets the induction pattern.
44709467b48Spatrick Register IndReg = DI->getOperand(1).getReg();
44809467b48Spatrick MachineOperand &Opnd2 = DI->getOperand(2);
44909467b48Spatrick int64_t V;
45009467b48Spatrick if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
45109467b48Spatrick Register UpdReg = DI->getOperand(0).getReg();
45209467b48Spatrick IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
45309467b48Spatrick }
45409467b48Spatrick }
45509467b48Spatrick } // for (i)
45609467b48Spatrick } // for (instr)
45709467b48Spatrick
45809467b48Spatrick SmallVector<MachineOperand,2> Cond;
45909467b48Spatrick MachineBasicBlock *TB = nullptr, *FB = nullptr;
46009467b48Spatrick bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
46109467b48Spatrick if (NotAnalyzed)
46209467b48Spatrick return false;
46309467b48Spatrick
464*d415bd75Srobert Register PredR;
465*d415bd75Srobert unsigned PredPos, PredRegFlags;
46609467b48Spatrick if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags))
46709467b48Spatrick return false;
46809467b48Spatrick
46909467b48Spatrick MachineInstr *PredI = MRI->getVRegDef(PredR);
47009467b48Spatrick if (!PredI->isCompare())
47109467b48Spatrick return false;
47209467b48Spatrick
473097a140dSpatrick Register CmpReg1, CmpReg2;
474*d415bd75Srobert int64_t CmpImm = 0, CmpMask = 0;
47509467b48Spatrick bool CmpAnalyzed =
47609467b48Spatrick TII->analyzeCompare(*PredI, CmpReg1, CmpReg2, CmpMask, CmpImm);
47709467b48Spatrick // Fail if the compare was not analyzed, or it's not comparing a register
47809467b48Spatrick // with an immediate value. Not checking the mask here, since we handle
47909467b48Spatrick // the individual compare opcodes (including A4_cmpb*) later on.
48009467b48Spatrick if (!CmpAnalyzed)
48109467b48Spatrick return false;
48209467b48Spatrick
48309467b48Spatrick // Exactly one of the input registers to the comparison should be among
48409467b48Spatrick // the induction registers.
48509467b48Spatrick InductionMap::iterator IndMapEnd = IndMap.end();
48609467b48Spatrick InductionMap::iterator F = IndMapEnd;
48709467b48Spatrick if (CmpReg1 != 0) {
48809467b48Spatrick InductionMap::iterator F1 = IndMap.find(CmpReg1);
48909467b48Spatrick if (F1 != IndMapEnd)
49009467b48Spatrick F = F1;
49109467b48Spatrick }
49209467b48Spatrick if (CmpReg2 != 0) {
49309467b48Spatrick InductionMap::iterator F2 = IndMap.find(CmpReg2);
49409467b48Spatrick if (F2 != IndMapEnd) {
49509467b48Spatrick if (F != IndMapEnd)
49609467b48Spatrick return false;
49709467b48Spatrick F = F2;
49809467b48Spatrick }
49909467b48Spatrick }
50009467b48Spatrick if (F == IndMapEnd)
50109467b48Spatrick return false;
50209467b48Spatrick
50309467b48Spatrick Reg = F->second.first;
50409467b48Spatrick IVBump = F->second.second;
50509467b48Spatrick IVOp = MRI->getVRegDef(F->first);
50609467b48Spatrick return true;
50709467b48Spatrick }
50809467b48Spatrick
50909467b48Spatrick // Return the comparison kind for the specified opcode.
51009467b48Spatrick HexagonHardwareLoops::Comparison::Kind
getComparisonKind(unsigned CondOpc,MachineOperand * InitialValue,const MachineOperand * EndValue,int64_t IVBump) const51109467b48Spatrick HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
51209467b48Spatrick MachineOperand *InitialValue,
51309467b48Spatrick const MachineOperand *EndValue,
51409467b48Spatrick int64_t IVBump) const {
51509467b48Spatrick Comparison::Kind Cmp = (Comparison::Kind)0;
51609467b48Spatrick switch (CondOpc) {
51709467b48Spatrick case Hexagon::C2_cmpeq:
51809467b48Spatrick case Hexagon::C2_cmpeqi:
51909467b48Spatrick case Hexagon::C2_cmpeqp:
52009467b48Spatrick Cmp = Comparison::EQ;
52109467b48Spatrick break;
52209467b48Spatrick case Hexagon::C4_cmpneq:
52309467b48Spatrick case Hexagon::C4_cmpneqi:
52409467b48Spatrick Cmp = Comparison::NE;
52509467b48Spatrick break;
52609467b48Spatrick case Hexagon::C2_cmplt:
52709467b48Spatrick Cmp = Comparison::LTs;
52809467b48Spatrick break;
52909467b48Spatrick case Hexagon::C2_cmpltu:
53009467b48Spatrick Cmp = Comparison::LTu;
53109467b48Spatrick break;
53209467b48Spatrick case Hexagon::C4_cmplte:
53309467b48Spatrick case Hexagon::C4_cmpltei:
53409467b48Spatrick Cmp = Comparison::LEs;
53509467b48Spatrick break;
53609467b48Spatrick case Hexagon::C4_cmplteu:
53709467b48Spatrick case Hexagon::C4_cmplteui:
53809467b48Spatrick Cmp = Comparison::LEu;
53909467b48Spatrick break;
54009467b48Spatrick case Hexagon::C2_cmpgt:
54109467b48Spatrick case Hexagon::C2_cmpgti:
54209467b48Spatrick case Hexagon::C2_cmpgtp:
54309467b48Spatrick Cmp = Comparison::GTs;
54409467b48Spatrick break;
54509467b48Spatrick case Hexagon::C2_cmpgtu:
54609467b48Spatrick case Hexagon::C2_cmpgtui:
54709467b48Spatrick case Hexagon::C2_cmpgtup:
54809467b48Spatrick Cmp = Comparison::GTu;
54909467b48Spatrick break;
55009467b48Spatrick case Hexagon::C2_cmpgei:
55109467b48Spatrick Cmp = Comparison::GEs;
55209467b48Spatrick break;
55309467b48Spatrick case Hexagon::C2_cmpgeui:
55409467b48Spatrick Cmp = Comparison::GEs;
55509467b48Spatrick break;
55609467b48Spatrick default:
55709467b48Spatrick return (Comparison::Kind)0;
55809467b48Spatrick }
55909467b48Spatrick return Cmp;
56009467b48Spatrick }
56109467b48Spatrick
56209467b48Spatrick /// Analyze the statements in a loop to determine if the loop has
56309467b48Spatrick /// a computable trip count and, if so, return a value that represents
56409467b48Spatrick /// the trip count expression.
56509467b48Spatrick ///
56609467b48Spatrick /// This function iterates over the phi nodes in the loop to check for
56709467b48Spatrick /// induction variable patterns that are used in the calculation for
56809467b48Spatrick /// the number of time the loop is executed.
getLoopTripCount(MachineLoop * L,SmallVectorImpl<MachineInstr * > & OldInsts)56909467b48Spatrick CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
57009467b48Spatrick SmallVectorImpl<MachineInstr *> &OldInsts) {
57109467b48Spatrick MachineBasicBlock *TopMBB = L->getTopBlock();
57209467b48Spatrick MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin();
57309467b48Spatrick assert(PI != TopMBB->pred_end() &&
57409467b48Spatrick "Loop must have more than one incoming edge!");
57509467b48Spatrick MachineBasicBlock *Backedge = *PI++;
57609467b48Spatrick if (PI == TopMBB->pred_end()) // dead loop?
57709467b48Spatrick return nullptr;
57809467b48Spatrick MachineBasicBlock *Incoming = *PI++;
57909467b48Spatrick if (PI != TopMBB->pred_end()) // multiple backedges?
58009467b48Spatrick return nullptr;
58109467b48Spatrick
58209467b48Spatrick // Make sure there is one incoming and one backedge and determine which
58309467b48Spatrick // is which.
58409467b48Spatrick if (L->contains(Incoming)) {
58509467b48Spatrick if (L->contains(Backedge))
58609467b48Spatrick return nullptr;
58709467b48Spatrick std::swap(Incoming, Backedge);
58809467b48Spatrick } else if (!L->contains(Backedge))
58909467b48Spatrick return nullptr;
59009467b48Spatrick
59109467b48Spatrick // Look for the cmp instruction to determine if we can get a useful trip
59209467b48Spatrick // count. The trip count can be either a register or an immediate. The
59309467b48Spatrick // location of the value depends upon the type (reg or imm).
59409467b48Spatrick MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
59509467b48Spatrick if (!ExitingBlock)
59609467b48Spatrick return nullptr;
59709467b48Spatrick
598*d415bd75Srobert Register IVReg = 0;
59909467b48Spatrick int64_t IVBump = 0;
60009467b48Spatrick MachineInstr *IVOp;
60109467b48Spatrick bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
60209467b48Spatrick if (!FoundIV)
60309467b48Spatrick return nullptr;
60409467b48Spatrick
60509467b48Spatrick MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
60609467b48Spatrick
60709467b48Spatrick MachineOperand *InitialValue = nullptr;
60809467b48Spatrick MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
60909467b48Spatrick MachineBasicBlock *Latch = L->getLoopLatch();
61009467b48Spatrick for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
61109467b48Spatrick MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
61209467b48Spatrick if (MBB == Preheader)
61309467b48Spatrick InitialValue = &IV_Phi->getOperand(i);
61409467b48Spatrick else if (MBB == Latch)
61509467b48Spatrick IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump.
61609467b48Spatrick }
61709467b48Spatrick if (!InitialValue)
61809467b48Spatrick return nullptr;
61909467b48Spatrick
62009467b48Spatrick SmallVector<MachineOperand,2> Cond;
62109467b48Spatrick MachineBasicBlock *TB = nullptr, *FB = nullptr;
62209467b48Spatrick bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
62309467b48Spatrick if (NotAnalyzed)
62409467b48Spatrick return nullptr;
62509467b48Spatrick
62609467b48Spatrick MachineBasicBlock *Header = L->getHeader();
62709467b48Spatrick // TB must be non-null. If FB is also non-null, one of them must be
62809467b48Spatrick // the header. Otherwise, branch to TB could be exiting the loop, and
62909467b48Spatrick // the fall through can go to the header.
63009467b48Spatrick assert (TB && "Exit block without a branch?");
63109467b48Spatrick if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
63209467b48Spatrick MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
63309467b48Spatrick SmallVector<MachineOperand,2> LCond;
63409467b48Spatrick bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
63509467b48Spatrick if (NotAnalyzed)
63609467b48Spatrick return nullptr;
63709467b48Spatrick if (TB == Latch)
63809467b48Spatrick TB = (LTB == Header) ? LTB : LFB;
63909467b48Spatrick else
64009467b48Spatrick FB = (LTB == Header) ? LTB: LFB;
64109467b48Spatrick }
64209467b48Spatrick assert ((!FB || TB == Header || FB == Header) && "Branches not to header?");
64309467b48Spatrick if (!TB || (FB && TB != Header && FB != Header))
64409467b48Spatrick return nullptr;
64509467b48Spatrick
646097a140dSpatrick // Branches of form "if (!P) ..." cause HexagonInstrInfo::analyzeBranch
64709467b48Spatrick // to put imm(0), followed by P in the vector Cond.
64809467b48Spatrick // If TB is not the header, it means that the "not-taken" path must lead
64909467b48Spatrick // to the header.
65009467b48Spatrick bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header);
651*d415bd75Srobert Register PredReg;
652*d415bd75Srobert unsigned PredPos, PredRegFlags;
65309467b48Spatrick if (!TII->getPredReg(Cond, PredReg, PredPos, PredRegFlags))
65409467b48Spatrick return nullptr;
65509467b48Spatrick MachineInstr *CondI = MRI->getVRegDef(PredReg);
65609467b48Spatrick unsigned CondOpc = CondI->getOpcode();
65709467b48Spatrick
658097a140dSpatrick Register CmpReg1, CmpReg2;
659*d415bd75Srobert int64_t Mask = 0, ImmValue = 0;
66009467b48Spatrick bool AnalyzedCmp =
66109467b48Spatrick TII->analyzeCompare(*CondI, CmpReg1, CmpReg2, Mask, ImmValue);
66209467b48Spatrick if (!AnalyzedCmp)
66309467b48Spatrick return nullptr;
66409467b48Spatrick
66509467b48Spatrick // The comparison operator type determines how we compute the loop
66609467b48Spatrick // trip count.
66709467b48Spatrick OldInsts.push_back(CondI);
66809467b48Spatrick OldInsts.push_back(IVOp);
66909467b48Spatrick
67009467b48Spatrick // Sadly, the following code gets information based on the position
67109467b48Spatrick // of the operands in the compare instruction. This has to be done
67209467b48Spatrick // this way, because the comparisons check for a specific relationship
67309467b48Spatrick // between the operands (e.g. is-less-than), rather than to find out
67409467b48Spatrick // what relationship the operands are in (as on PPC).
67509467b48Spatrick Comparison::Kind Cmp;
67609467b48Spatrick bool isSwapped = false;
67709467b48Spatrick const MachineOperand &Op1 = CondI->getOperand(1);
67809467b48Spatrick const MachineOperand &Op2 = CondI->getOperand(2);
67909467b48Spatrick const MachineOperand *EndValue = nullptr;
68009467b48Spatrick
68109467b48Spatrick if (Op1.isReg()) {
68209467b48Spatrick if (Op2.isImm() || Op1.getReg() == IVReg)
68309467b48Spatrick EndValue = &Op2;
68409467b48Spatrick else {
68509467b48Spatrick EndValue = &Op1;
68609467b48Spatrick isSwapped = true;
68709467b48Spatrick }
68809467b48Spatrick }
68909467b48Spatrick
69009467b48Spatrick if (!EndValue)
69109467b48Spatrick return nullptr;
69209467b48Spatrick
69309467b48Spatrick Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump);
69409467b48Spatrick if (!Cmp)
69509467b48Spatrick return nullptr;
69609467b48Spatrick if (Negated)
69709467b48Spatrick Cmp = Comparison::getNegatedComparison(Cmp);
69809467b48Spatrick if (isSwapped)
69909467b48Spatrick Cmp = Comparison::getSwappedComparison(Cmp);
70009467b48Spatrick
70109467b48Spatrick if (InitialValue->isReg()) {
70209467b48Spatrick Register R = InitialValue->getReg();
70309467b48Spatrick MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
70409467b48Spatrick if (!MDT->properlyDominates(DefBB, Header)) {
70509467b48Spatrick int64_t V;
70609467b48Spatrick if (!checkForImmediate(*InitialValue, V))
70709467b48Spatrick return nullptr;
70809467b48Spatrick }
70909467b48Spatrick OldInsts.push_back(MRI->getVRegDef(R));
71009467b48Spatrick }
71109467b48Spatrick if (EndValue->isReg()) {
71209467b48Spatrick Register R = EndValue->getReg();
71309467b48Spatrick MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent();
71409467b48Spatrick if (!MDT->properlyDominates(DefBB, Header)) {
71509467b48Spatrick int64_t V;
71609467b48Spatrick if (!checkForImmediate(*EndValue, V))
71709467b48Spatrick return nullptr;
71809467b48Spatrick }
71909467b48Spatrick OldInsts.push_back(MRI->getVRegDef(R));
72009467b48Spatrick }
72109467b48Spatrick
72209467b48Spatrick return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp);
72309467b48Spatrick }
72409467b48Spatrick
72509467b48Spatrick /// Helper function that returns the expression that represents the
72609467b48Spatrick /// number of times a loop iterates. The function takes the operands that
72709467b48Spatrick /// represent the loop start value, loop end value, and induction value.
72809467b48Spatrick /// Based upon these operands, the function attempts to compute the trip count.
computeCount(MachineLoop * Loop,const MachineOperand * Start,const MachineOperand * End,Register IVReg,int64_t IVBump,Comparison::Kind Cmp) const72909467b48Spatrick CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
73009467b48Spatrick const MachineOperand *Start,
73109467b48Spatrick const MachineOperand *End,
732*d415bd75Srobert Register IVReg,
73309467b48Spatrick int64_t IVBump,
73409467b48Spatrick Comparison::Kind Cmp) const {
73509467b48Spatrick // Cannot handle comparison EQ, i.e. while (A == B).
73609467b48Spatrick if (Cmp == Comparison::EQ)
73709467b48Spatrick return nullptr;
73809467b48Spatrick
73909467b48Spatrick // Check if either the start or end values are an assignment of an immediate.
74009467b48Spatrick // If so, use the immediate value rather than the register.
74109467b48Spatrick if (Start->isReg()) {
74209467b48Spatrick const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg());
74309467b48Spatrick if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi ||
74409467b48Spatrick StartValInstr->getOpcode() == Hexagon::A2_tfrpi))
74509467b48Spatrick Start = &StartValInstr->getOperand(1);
74609467b48Spatrick }
74709467b48Spatrick if (End->isReg()) {
74809467b48Spatrick const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
74909467b48Spatrick if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi ||
75009467b48Spatrick EndValInstr->getOpcode() == Hexagon::A2_tfrpi))
75109467b48Spatrick End = &EndValInstr->getOperand(1);
75209467b48Spatrick }
75309467b48Spatrick
75409467b48Spatrick if (!Start->isReg() && !Start->isImm())
75509467b48Spatrick return nullptr;
75609467b48Spatrick if (!End->isReg() && !End->isImm())
75709467b48Spatrick return nullptr;
75809467b48Spatrick
75909467b48Spatrick bool CmpLess = Cmp & Comparison::L;
76009467b48Spatrick bool CmpGreater = Cmp & Comparison::G;
76109467b48Spatrick bool CmpHasEqual = Cmp & Comparison::EQ;
76209467b48Spatrick
76309467b48Spatrick // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds.
76409467b48Spatrick if (CmpLess && IVBump < 0)
76509467b48Spatrick // Loop going while iv is "less" with the iv value going down. Must wrap.
76609467b48Spatrick return nullptr;
76709467b48Spatrick
76809467b48Spatrick if (CmpGreater && IVBump > 0)
76909467b48Spatrick // Loop going while iv is "greater" with the iv value going up. Must wrap.
77009467b48Spatrick return nullptr;
77109467b48Spatrick
77209467b48Spatrick // Phis that may feed into the loop.
77309467b48Spatrick LoopFeederMap LoopFeederPhi;
77409467b48Spatrick
77509467b48Spatrick // Check if the initial value may be zero and can be decremented in the first
77609467b48Spatrick // iteration. If the value is zero, the endloop instruction will not decrement
77709467b48Spatrick // the loop counter, so we shouldn't generate a hardware loop in this case.
77809467b48Spatrick if (loopCountMayWrapOrUnderFlow(Start, End, Loop->getLoopPreheader(), Loop,
77909467b48Spatrick LoopFeederPhi))
78009467b48Spatrick return nullptr;
78109467b48Spatrick
78209467b48Spatrick if (Start->isImm() && End->isImm()) {
78309467b48Spatrick // Both, start and end are immediates.
78409467b48Spatrick int64_t StartV = Start->getImm();
78509467b48Spatrick int64_t EndV = End->getImm();
78609467b48Spatrick int64_t Dist = EndV - StartV;
78709467b48Spatrick if (Dist == 0)
78809467b48Spatrick return nullptr;
78909467b48Spatrick
79009467b48Spatrick bool Exact = (Dist % IVBump) == 0;
79109467b48Spatrick
79209467b48Spatrick if (Cmp == Comparison::NE) {
79309467b48Spatrick if (!Exact)
79409467b48Spatrick return nullptr;
79509467b48Spatrick if ((Dist < 0) ^ (IVBump < 0))
79609467b48Spatrick return nullptr;
79709467b48Spatrick }
79809467b48Spatrick
79909467b48Spatrick // For comparisons that include the final value (i.e. include equality
80009467b48Spatrick // with the final value), we need to increase the distance by 1.
80109467b48Spatrick if (CmpHasEqual)
80209467b48Spatrick Dist = Dist > 0 ? Dist+1 : Dist-1;
80309467b48Spatrick
80409467b48Spatrick // For the loop to iterate, CmpLess should imply Dist > 0. Similarly,
80509467b48Spatrick // CmpGreater should imply Dist < 0. These conditions could actually
80609467b48Spatrick // fail, for example, in unreachable code (which may still appear to be
80709467b48Spatrick // reachable in the CFG).
80809467b48Spatrick if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0))
80909467b48Spatrick return nullptr;
81009467b48Spatrick
81109467b48Spatrick // "Normalized" distance, i.e. with the bump set to +-1.
81209467b48Spatrick int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump - 1)) / IVBump
81309467b48Spatrick : (-Dist + (-IVBump - 1)) / (-IVBump);
81409467b48Spatrick assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign.");
81509467b48Spatrick
81609467b48Spatrick uint64_t Count = Dist1;
81709467b48Spatrick
81809467b48Spatrick if (Count > 0xFFFFFFFFULL)
81909467b48Spatrick return nullptr;
82009467b48Spatrick
82109467b48Spatrick return new CountValue(CountValue::CV_Immediate, Count);
82209467b48Spatrick }
82309467b48Spatrick
82409467b48Spatrick // A general case: Start and End are some values, but the actual
82509467b48Spatrick // iteration count may not be available. If it is not, insert
82609467b48Spatrick // a computation of it into the preheader.
82709467b48Spatrick
82809467b48Spatrick // If the induction variable bump is not a power of 2, quit.
82909467b48Spatrick // Othwerise we'd need a general integer division.
83009467b48Spatrick if (!isPowerOf2_64(std::abs(IVBump)))
83109467b48Spatrick return nullptr;
83209467b48Spatrick
83309467b48Spatrick MachineBasicBlock *PH = MLI->findLoopPreheader(Loop, SpecPreheader);
83409467b48Spatrick assert (PH && "Should have a preheader by now");
83509467b48Spatrick MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
83609467b48Spatrick DebugLoc DL;
83709467b48Spatrick if (InsertPos != PH->end())
83809467b48Spatrick DL = InsertPos->getDebugLoc();
83909467b48Spatrick
84009467b48Spatrick // If Start is an immediate and End is a register, the trip count
84109467b48Spatrick // will be "reg - imm". Hexagon's "subtract immediate" instruction
84209467b48Spatrick // is actually "reg + -imm".
84309467b48Spatrick
84409467b48Spatrick // If the loop IV is going downwards, i.e. if the bump is negative,
84509467b48Spatrick // then the iteration count (computed as End-Start) will need to be
84609467b48Spatrick // negated. To avoid the negation, just swap Start and End.
84709467b48Spatrick if (IVBump < 0) {
84809467b48Spatrick std::swap(Start, End);
84909467b48Spatrick IVBump = -IVBump;
85009467b48Spatrick }
85109467b48Spatrick // Cmp may now have a wrong direction, e.g. LEs may now be GEs.
85209467b48Spatrick // Signedness, and "including equality" are preserved.
85309467b48Spatrick
85409467b48Spatrick bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm)
85509467b48Spatrick bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg)
85609467b48Spatrick
85709467b48Spatrick int64_t StartV = 0, EndV = 0;
85809467b48Spatrick if (Start->isImm())
85909467b48Spatrick StartV = Start->getImm();
86009467b48Spatrick if (End->isImm())
86109467b48Spatrick EndV = End->getImm();
86209467b48Spatrick
86309467b48Spatrick int64_t AdjV = 0;
86409467b48Spatrick // To compute the iteration count, we would need this computation:
86509467b48Spatrick // Count = (End - Start + (IVBump-1)) / IVBump
86609467b48Spatrick // or, when CmpHasEqual:
86709467b48Spatrick // Count = (End - Start + (IVBump-1)+1) / IVBump
86809467b48Spatrick // The "IVBump-1" part is the adjustment (AdjV). We can avoid
86909467b48Spatrick // generating an instruction specifically to add it if we can adjust
87009467b48Spatrick // the immediate values for Start or End.
87109467b48Spatrick
87209467b48Spatrick if (CmpHasEqual) {
87309467b48Spatrick // Need to add 1 to the total iteration count.
87409467b48Spatrick if (Start->isImm())
87509467b48Spatrick StartV--;
87609467b48Spatrick else if (End->isImm())
87709467b48Spatrick EndV++;
87809467b48Spatrick else
87909467b48Spatrick AdjV += 1;
88009467b48Spatrick }
88109467b48Spatrick
88209467b48Spatrick if (Cmp != Comparison::NE) {
88309467b48Spatrick if (Start->isImm())
88409467b48Spatrick StartV -= (IVBump-1);
88509467b48Spatrick else if (End->isImm())
88609467b48Spatrick EndV += (IVBump-1);
88709467b48Spatrick else
88809467b48Spatrick AdjV += (IVBump-1);
88909467b48Spatrick }
89009467b48Spatrick
891*d415bd75Srobert Register R = 0;
892*d415bd75Srobert unsigned SR = 0;
89309467b48Spatrick if (Start->isReg()) {
89409467b48Spatrick R = Start->getReg();
89509467b48Spatrick SR = Start->getSubReg();
89609467b48Spatrick } else {
89709467b48Spatrick R = End->getReg();
89809467b48Spatrick SR = End->getSubReg();
89909467b48Spatrick }
90009467b48Spatrick const TargetRegisterClass *RC = MRI->getRegClass(R);
90109467b48Spatrick // Hardware loops cannot handle 64-bit registers. If it's a double
90209467b48Spatrick // register, it has to have a subregister.
90309467b48Spatrick if (!SR && RC == &Hexagon::DoubleRegsRegClass)
90409467b48Spatrick return nullptr;
90509467b48Spatrick const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass;
90609467b48Spatrick
90709467b48Spatrick // Compute DistR (register with the distance between Start and End).
908*d415bd75Srobert Register DistR;
909*d415bd75Srobert unsigned DistSR;
91009467b48Spatrick
91109467b48Spatrick // Avoid special case, where the start value is an imm(0).
91209467b48Spatrick if (Start->isImm() && StartV == 0) {
91309467b48Spatrick DistR = End->getReg();
91409467b48Spatrick DistSR = End->getSubReg();
91509467b48Spatrick } else {
91609467b48Spatrick const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) :
91709467b48Spatrick (RegToImm ? TII->get(Hexagon::A2_subri) :
91809467b48Spatrick TII->get(Hexagon::A2_addi));
91909467b48Spatrick if (RegToReg || RegToImm) {
92009467b48Spatrick Register SubR = MRI->createVirtualRegister(IntRC);
92109467b48Spatrick MachineInstrBuilder SubIB =
92209467b48Spatrick BuildMI(*PH, InsertPos, DL, SubD, SubR);
92309467b48Spatrick
92409467b48Spatrick if (RegToReg)
92509467b48Spatrick SubIB.addReg(End->getReg(), 0, End->getSubReg())
92609467b48Spatrick .addReg(Start->getReg(), 0, Start->getSubReg());
92709467b48Spatrick else
92809467b48Spatrick SubIB.addImm(EndV)
92909467b48Spatrick .addReg(Start->getReg(), 0, Start->getSubReg());
93009467b48Spatrick DistR = SubR;
93109467b48Spatrick } else {
93209467b48Spatrick // If the loop has been unrolled, we should use the original loop count
93309467b48Spatrick // instead of recalculating the value. This will avoid additional
93409467b48Spatrick // 'Add' instruction.
93509467b48Spatrick const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg());
93609467b48Spatrick if (EndValInstr->getOpcode() == Hexagon::A2_addi &&
93709467b48Spatrick EndValInstr->getOperand(1).getSubReg() == 0 &&
93809467b48Spatrick EndValInstr->getOperand(2).getImm() == StartV) {
93909467b48Spatrick DistR = EndValInstr->getOperand(1).getReg();
94009467b48Spatrick } else {
94109467b48Spatrick Register SubR = MRI->createVirtualRegister(IntRC);
94209467b48Spatrick MachineInstrBuilder SubIB =
94309467b48Spatrick BuildMI(*PH, InsertPos, DL, SubD, SubR);
94409467b48Spatrick SubIB.addReg(End->getReg(), 0, End->getSubReg())
94509467b48Spatrick .addImm(-StartV);
94609467b48Spatrick DistR = SubR;
94709467b48Spatrick }
94809467b48Spatrick }
94909467b48Spatrick DistSR = 0;
95009467b48Spatrick }
95109467b48Spatrick
95209467b48Spatrick // From DistR, compute AdjR (register with the adjusted distance).
953*d415bd75Srobert Register AdjR;
954*d415bd75Srobert unsigned AdjSR;
95509467b48Spatrick
95609467b48Spatrick if (AdjV == 0) {
95709467b48Spatrick AdjR = DistR;
95809467b48Spatrick AdjSR = DistSR;
95909467b48Spatrick } else {
96009467b48Spatrick // Generate CountR = ADD DistR, AdjVal
96109467b48Spatrick Register AddR = MRI->createVirtualRegister(IntRC);
96209467b48Spatrick MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi);
96309467b48Spatrick BuildMI(*PH, InsertPos, DL, AddD, AddR)
96409467b48Spatrick .addReg(DistR, 0, DistSR)
96509467b48Spatrick .addImm(AdjV);
96609467b48Spatrick
96709467b48Spatrick AdjR = AddR;
96809467b48Spatrick AdjSR = 0;
96909467b48Spatrick }
97009467b48Spatrick
97109467b48Spatrick // From AdjR, compute CountR (register with the final count).
972*d415bd75Srobert Register CountR;
973*d415bd75Srobert unsigned CountSR;
97409467b48Spatrick
97509467b48Spatrick if (IVBump == 1) {
97609467b48Spatrick CountR = AdjR;
97709467b48Spatrick CountSR = AdjSR;
97809467b48Spatrick } else {
97909467b48Spatrick // The IV bump is a power of two. Log_2(IV bump) is the shift amount.
98009467b48Spatrick unsigned Shift = Log2_32(IVBump);
98109467b48Spatrick
98209467b48Spatrick // Generate NormR = LSR DistR, Shift.
98309467b48Spatrick Register LsrR = MRI->createVirtualRegister(IntRC);
98409467b48Spatrick const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r);
98509467b48Spatrick BuildMI(*PH, InsertPos, DL, LsrD, LsrR)
98609467b48Spatrick .addReg(AdjR, 0, AdjSR)
98709467b48Spatrick .addImm(Shift);
98809467b48Spatrick
98909467b48Spatrick CountR = LsrR;
99009467b48Spatrick CountSR = 0;
99109467b48Spatrick }
99209467b48Spatrick
99309467b48Spatrick return new CountValue(CountValue::CV_Register, CountR, CountSR);
99409467b48Spatrick }
99509467b48Spatrick
99609467b48Spatrick /// Return true if the operation is invalid within hardware loop.
isInvalidLoopOperation(const MachineInstr * MI,bool IsInnerHWLoop) const99709467b48Spatrick bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
99809467b48Spatrick bool IsInnerHWLoop) const {
99909467b48Spatrick // Call is not allowed because the callee may use a hardware loop except for
100009467b48Spatrick // the case when the call never returns.
100109467b48Spatrick if (MI->getDesc().isCall())
100209467b48Spatrick return !TII->doesNotReturn(*MI);
100309467b48Spatrick
100409467b48Spatrick // Check if the instruction defines a hardware loop register.
100509467b48Spatrick using namespace Hexagon;
100609467b48Spatrick
1007*d415bd75Srobert static const Register Regs01[] = { LC0, SA0, LC1, SA1 };
1008*d415bd75Srobert static const Register Regs1[] = { LC1, SA1 };
1009*d415bd75Srobert auto CheckRegs = IsInnerHWLoop ? ArrayRef(Regs01, std::size(Regs01))
1010*d415bd75Srobert : ArrayRef(Regs1, std::size(Regs1));
1011*d415bd75Srobert for (Register R : CheckRegs)
101209467b48Spatrick if (MI->modifiesRegister(R, TRI))
101309467b48Spatrick return true;
101409467b48Spatrick
101509467b48Spatrick return false;
101609467b48Spatrick }
101709467b48Spatrick
101809467b48Spatrick /// Return true if the loop contains an instruction that inhibits
101909467b48Spatrick /// the use of the hardware loop instruction.
containsInvalidInstruction(MachineLoop * L,bool IsInnerHWLoop) const102009467b48Spatrick bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
102109467b48Spatrick bool IsInnerHWLoop) const {
102209467b48Spatrick LLVM_DEBUG(dbgs() << "\nhw_loop head, "
102309467b48Spatrick << printMBBReference(**L->block_begin()));
102409467b48Spatrick for (MachineBasicBlock *MBB : L->getBlocks()) {
1025*d415bd75Srobert for (const MachineInstr &MI : *MBB) {
1026*d415bd75Srobert if (isInvalidLoopOperation(&MI, IsInnerHWLoop)) {
102709467b48Spatrick LLVM_DEBUG(dbgs() << "\nCannot convert to hw_loop due to:";
1028*d415bd75Srobert MI.dump(););
102909467b48Spatrick return true;
103009467b48Spatrick }
103109467b48Spatrick }
103209467b48Spatrick }
103309467b48Spatrick return false;
103409467b48Spatrick }
103509467b48Spatrick
103609467b48Spatrick /// Returns true if the instruction is dead. This was essentially
103709467b48Spatrick /// copied from DeadMachineInstructionElim::isDead, but with special cases
103809467b48Spatrick /// for inline asm, physical registers and instructions with side effects
103909467b48Spatrick /// removed.
isDead(const MachineInstr * MI,SmallVectorImpl<MachineInstr * > & DeadPhis) const104009467b48Spatrick bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
104109467b48Spatrick SmallVectorImpl<MachineInstr *> &DeadPhis) const {
104209467b48Spatrick // Examine each operand.
1043*d415bd75Srobert for (const MachineOperand &MO : MI->operands()) {
104409467b48Spatrick if (!MO.isReg() || !MO.isDef())
104509467b48Spatrick continue;
104609467b48Spatrick
104709467b48Spatrick Register Reg = MO.getReg();
104809467b48Spatrick if (MRI->use_nodbg_empty(Reg))
104909467b48Spatrick continue;
105009467b48Spatrick
105109467b48Spatrick using use_nodbg_iterator = MachineRegisterInfo::use_nodbg_iterator;
105209467b48Spatrick
105309467b48Spatrick // This instruction has users, but if the only user is the phi node for the
105409467b48Spatrick // parent block, and the only use of that phi node is this instruction, then
105509467b48Spatrick // this instruction is dead: both it (and the phi node) can be removed.
105609467b48Spatrick use_nodbg_iterator I = MRI->use_nodbg_begin(Reg);
105709467b48Spatrick use_nodbg_iterator End = MRI->use_nodbg_end();
105809467b48Spatrick if (std::next(I) != End || !I->getParent()->isPHI())
105909467b48Spatrick return false;
106009467b48Spatrick
106109467b48Spatrick MachineInstr *OnePhi = I->getParent();
106209467b48Spatrick for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) {
106309467b48Spatrick const MachineOperand &OPO = OnePhi->getOperand(j);
106409467b48Spatrick if (!OPO.isReg() || !OPO.isDef())
106509467b48Spatrick continue;
106609467b48Spatrick
106709467b48Spatrick Register OPReg = OPO.getReg();
106809467b48Spatrick use_nodbg_iterator nextJ;
106909467b48Spatrick for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg);
107009467b48Spatrick J != End; J = nextJ) {
107109467b48Spatrick nextJ = std::next(J);
107209467b48Spatrick MachineOperand &Use = *J;
107309467b48Spatrick MachineInstr *UseMI = Use.getParent();
107409467b48Spatrick
107509467b48Spatrick // If the phi node has a user that is not MI, bail.
107609467b48Spatrick if (MI != UseMI)
107709467b48Spatrick return false;
107809467b48Spatrick }
107909467b48Spatrick }
108009467b48Spatrick DeadPhis.push_back(OnePhi);
108109467b48Spatrick }
108209467b48Spatrick
108309467b48Spatrick // If there are no defs with uses, the instruction is dead.
108409467b48Spatrick return true;
108509467b48Spatrick }
108609467b48Spatrick
removeIfDead(MachineInstr * MI)108709467b48Spatrick void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) {
108809467b48Spatrick // This procedure was essentially copied from DeadMachineInstructionElim.
108909467b48Spatrick
109009467b48Spatrick SmallVector<MachineInstr*, 1> DeadPhis;
109109467b48Spatrick if (isDead(MI, DeadPhis)) {
109209467b48Spatrick LLVM_DEBUG(dbgs() << "HW looping will remove: " << *MI);
109309467b48Spatrick
109409467b48Spatrick // It is possible that some DBG_VALUE instructions refer to this
109509467b48Spatrick // instruction. Examine each def operand for such references;
109609467b48Spatrick // if found, mark the DBG_VALUE as undef (but don't delete it).
1097*d415bd75Srobert for (const MachineOperand &MO : MI->operands()) {
109809467b48Spatrick if (!MO.isReg() || !MO.isDef())
109909467b48Spatrick continue;
110009467b48Spatrick Register Reg = MO.getReg();
1101*d415bd75Srobert // We use make_early_inc_range here because setReg below invalidates the
1102*d415bd75Srobert // iterator.
1103*d415bd75Srobert for (MachineOperand &MO :
1104*d415bd75Srobert llvm::make_early_inc_range(MRI->use_operands(Reg))) {
1105*d415bd75Srobert MachineInstr *UseMI = MO.getParent();
110609467b48Spatrick if (UseMI == MI)
110709467b48Spatrick continue;
1108*d415bd75Srobert if (MO.isDebug())
1109*d415bd75Srobert MO.setReg(0U);
111009467b48Spatrick }
111109467b48Spatrick }
111209467b48Spatrick
111309467b48Spatrick MI->eraseFromParent();
111409467b48Spatrick for (unsigned i = 0; i < DeadPhis.size(); ++i)
111509467b48Spatrick DeadPhis[i]->eraseFromParent();
111609467b48Spatrick }
111709467b48Spatrick }
111809467b48Spatrick
111909467b48Spatrick /// Check if the loop is a candidate for converting to a hardware
112009467b48Spatrick /// loop. If so, then perform the transformation.
112109467b48Spatrick ///
112209467b48Spatrick /// This function works on innermost loops first. A loop can be converted
112309467b48Spatrick /// if it is a counting loop; either a register value or an immediate.
112409467b48Spatrick ///
112509467b48Spatrick /// The code makes several assumptions about the representation of the loop
112609467b48Spatrick /// in llvm.
convertToHardwareLoop(MachineLoop * L,bool & RecL0used,bool & RecL1used)112709467b48Spatrick bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
112809467b48Spatrick bool &RecL0used,
112909467b48Spatrick bool &RecL1used) {
1130*d415bd75Srobert // This is just to confirm basic correctness.
113109467b48Spatrick assert(L->getHeader() && "Loop without a header?");
113209467b48Spatrick
113309467b48Spatrick bool Changed = false;
113409467b48Spatrick bool L0Used = false;
113509467b48Spatrick bool L1Used = false;
113609467b48Spatrick
113709467b48Spatrick // Process nested loops first.
1138*d415bd75Srobert for (MachineLoop *I : *L) {
1139*d415bd75Srobert Changed |= convertToHardwareLoop(I, RecL0used, RecL1used);
114009467b48Spatrick L0Used |= RecL0used;
114109467b48Spatrick L1Used |= RecL1used;
114209467b48Spatrick }
114309467b48Spatrick
114409467b48Spatrick // If a nested loop has been converted, then we can't convert this loop.
114509467b48Spatrick if (Changed && L0Used && L1Used)
114609467b48Spatrick return Changed;
114709467b48Spatrick
114809467b48Spatrick unsigned LOOP_i;
114909467b48Spatrick unsigned LOOP_r;
115009467b48Spatrick unsigned ENDLOOP;
115109467b48Spatrick
115209467b48Spatrick // Flag used to track loopN instruction:
115309467b48Spatrick // 1 - Hardware loop is being generated for the inner most loop.
115409467b48Spatrick // 0 - Hardware loop is being generated for the outer loop.
115509467b48Spatrick unsigned IsInnerHWLoop = 1;
115609467b48Spatrick
115709467b48Spatrick if (L0Used) {
115809467b48Spatrick LOOP_i = Hexagon::J2_loop1i;
115909467b48Spatrick LOOP_r = Hexagon::J2_loop1r;
116009467b48Spatrick ENDLOOP = Hexagon::ENDLOOP1;
116109467b48Spatrick IsInnerHWLoop = 0;
116209467b48Spatrick } else {
116309467b48Spatrick LOOP_i = Hexagon::J2_loop0i;
116409467b48Spatrick LOOP_r = Hexagon::J2_loop0r;
116509467b48Spatrick ENDLOOP = Hexagon::ENDLOOP0;
116609467b48Spatrick }
116709467b48Spatrick
116809467b48Spatrick #ifndef NDEBUG
116909467b48Spatrick // Stop trying after reaching the limit (if any).
117009467b48Spatrick int Limit = HWLoopLimit;
117109467b48Spatrick if (Limit >= 0) {
117209467b48Spatrick if (Counter >= HWLoopLimit)
117309467b48Spatrick return false;
117409467b48Spatrick Counter++;
117509467b48Spatrick }
117609467b48Spatrick #endif
117709467b48Spatrick
117809467b48Spatrick // Does the loop contain any invalid instructions?
117909467b48Spatrick if (containsInvalidInstruction(L, IsInnerHWLoop))
118009467b48Spatrick return false;
118109467b48Spatrick
118209467b48Spatrick MachineBasicBlock *LastMBB = L->findLoopControlBlock();
118309467b48Spatrick // Don't generate hw loop if the loop has more than one exit.
118409467b48Spatrick if (!LastMBB)
118509467b48Spatrick return false;
118609467b48Spatrick
118709467b48Spatrick MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
118809467b48Spatrick if (LastI == LastMBB->end())
118909467b48Spatrick return false;
119009467b48Spatrick
119109467b48Spatrick // Is the induction variable bump feeding the latch condition?
119209467b48Spatrick if (!fixupInductionVariable(L))
119309467b48Spatrick return false;
119409467b48Spatrick
119509467b48Spatrick // Ensure the loop has a preheader: the loop instruction will be
119609467b48Spatrick // placed there.
119709467b48Spatrick MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
119809467b48Spatrick if (!Preheader) {
119909467b48Spatrick Preheader = createPreheaderForLoop(L);
120009467b48Spatrick if (!Preheader)
120109467b48Spatrick return false;
120209467b48Spatrick }
120309467b48Spatrick
120409467b48Spatrick MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
120509467b48Spatrick
120609467b48Spatrick SmallVector<MachineInstr*, 2> OldInsts;
120709467b48Spatrick // Are we able to determine the trip count for the loop?
120809467b48Spatrick CountValue *TripCount = getLoopTripCount(L, OldInsts);
120909467b48Spatrick if (!TripCount)
121009467b48Spatrick return false;
121109467b48Spatrick
121209467b48Spatrick // Is the trip count available in the preheader?
121309467b48Spatrick if (TripCount->isReg()) {
121409467b48Spatrick // There will be a use of the register inserted into the preheader,
121509467b48Spatrick // so make sure that the register is actually defined at that point.
121609467b48Spatrick MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
121709467b48Spatrick MachineBasicBlock *BBDef = TCDef->getParent();
121809467b48Spatrick if (!MDT->dominates(BBDef, Preheader))
121909467b48Spatrick return false;
122009467b48Spatrick }
122109467b48Spatrick
122209467b48Spatrick // Determine the loop start.
122309467b48Spatrick MachineBasicBlock *TopBlock = L->getTopBlock();
122409467b48Spatrick MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
122509467b48Spatrick MachineBasicBlock *LoopStart = nullptr;
122609467b48Spatrick if (ExitingBlock != L->getLoopLatch()) {
122709467b48Spatrick MachineBasicBlock *TB = nullptr, *FB = nullptr;
122809467b48Spatrick SmallVector<MachineOperand, 2> Cond;
122909467b48Spatrick
123009467b48Spatrick if (TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false))
123109467b48Spatrick return false;
123209467b48Spatrick
123309467b48Spatrick if (L->contains(TB))
123409467b48Spatrick LoopStart = TB;
123509467b48Spatrick else if (L->contains(FB))
123609467b48Spatrick LoopStart = FB;
123709467b48Spatrick else
123809467b48Spatrick return false;
123909467b48Spatrick }
124009467b48Spatrick else
124109467b48Spatrick LoopStart = TopBlock;
124209467b48Spatrick
124309467b48Spatrick // Convert the loop to a hardware loop.
124409467b48Spatrick LLVM_DEBUG(dbgs() << "Change to hardware loop at "; L->dump());
124509467b48Spatrick DebugLoc DL;
124609467b48Spatrick if (InsertPos != Preheader->end())
124709467b48Spatrick DL = InsertPos->getDebugLoc();
124809467b48Spatrick
124909467b48Spatrick if (TripCount->isReg()) {
125009467b48Spatrick // Create a copy of the loop count register.
125109467b48Spatrick Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
125209467b48Spatrick BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg)
125309467b48Spatrick .addReg(TripCount->getReg(), 0, TripCount->getSubReg());
125409467b48Spatrick // Add the Loop instruction to the beginning of the loop.
125509467b48Spatrick BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart)
125609467b48Spatrick .addReg(CountReg);
125709467b48Spatrick } else {
125809467b48Spatrick assert(TripCount->isImm() && "Expecting immediate value for trip count");
125909467b48Spatrick // Add the Loop immediate instruction to the beginning of the loop,
126009467b48Spatrick // if the immediate fits in the instructions. Otherwise, we need to
126109467b48Spatrick // create a new virtual register.
126209467b48Spatrick int64_t CountImm = TripCount->getImm();
126309467b48Spatrick if (!TII->isValidOffset(LOOP_i, CountImm, TRI)) {
126409467b48Spatrick Register CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
126509467b48Spatrick BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg)
126609467b48Spatrick .addImm(CountImm);
126709467b48Spatrick BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r))
126809467b48Spatrick .addMBB(LoopStart).addReg(CountReg);
126909467b48Spatrick } else
127009467b48Spatrick BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i))
127109467b48Spatrick .addMBB(LoopStart).addImm(CountImm);
127209467b48Spatrick }
127309467b48Spatrick
1274*d415bd75Srobert // Make sure the loop start always has a reference in the CFG.
1275*d415bd75Srobert LoopStart->setMachineBlockAddressTaken();
127609467b48Spatrick
127709467b48Spatrick // Replace the loop branch with an endloop instruction.
127809467b48Spatrick DebugLoc LastIDL = LastI->getDebugLoc();
127909467b48Spatrick BuildMI(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(LoopStart);
128009467b48Spatrick
128109467b48Spatrick // The loop ends with either:
128209467b48Spatrick // - a conditional branch followed by an unconditional branch, or
128309467b48Spatrick // - a conditional branch to the loop start.
128409467b48Spatrick if (LastI->getOpcode() == Hexagon::J2_jumpt ||
128509467b48Spatrick LastI->getOpcode() == Hexagon::J2_jumpf) {
128609467b48Spatrick // Delete one and change/add an uncond. branch to out of the loop.
128709467b48Spatrick MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB();
128809467b48Spatrick LastI = LastMBB->erase(LastI);
128909467b48Spatrick if (!L->contains(BranchTarget)) {
129009467b48Spatrick if (LastI != LastMBB->end())
129109467b48Spatrick LastI = LastMBB->erase(LastI);
129209467b48Spatrick SmallVector<MachineOperand, 0> Cond;
129309467b48Spatrick TII->insertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL);
129409467b48Spatrick }
129509467b48Spatrick } else {
129609467b48Spatrick // Conditional branch to loop start; just delete it.
129709467b48Spatrick LastMBB->erase(LastI);
129809467b48Spatrick }
129909467b48Spatrick delete TripCount;
130009467b48Spatrick
130109467b48Spatrick // The induction operation and the comparison may now be
130209467b48Spatrick // unneeded. If these are unneeded, then remove them.
130309467b48Spatrick for (unsigned i = 0; i < OldInsts.size(); ++i)
130409467b48Spatrick removeIfDead(OldInsts[i]);
130509467b48Spatrick
130609467b48Spatrick ++NumHWLoops;
130709467b48Spatrick
130809467b48Spatrick // Set RecL1used and RecL0used only after hardware loop has been
130909467b48Spatrick // successfully generated. Doing it earlier can cause wrong loop instruction
131009467b48Spatrick // to be used.
131109467b48Spatrick if (L0Used) // Loop0 was already used. So, the correct loop must be loop1.
131209467b48Spatrick RecL1used = true;
131309467b48Spatrick else
131409467b48Spatrick RecL0used = true;
131509467b48Spatrick
131609467b48Spatrick return true;
131709467b48Spatrick }
131809467b48Spatrick
orderBumpCompare(MachineInstr * BumpI,MachineInstr * CmpI)131909467b48Spatrick bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
132009467b48Spatrick MachineInstr *CmpI) {
132109467b48Spatrick assert (BumpI != CmpI && "Bump and compare in the same instruction?");
132209467b48Spatrick
132309467b48Spatrick MachineBasicBlock *BB = BumpI->getParent();
132409467b48Spatrick if (CmpI->getParent() != BB)
132509467b48Spatrick return false;
132609467b48Spatrick
132709467b48Spatrick using instr_iterator = MachineBasicBlock::instr_iterator;
132809467b48Spatrick
132909467b48Spatrick // Check if things are in order to begin with.
133009467b48Spatrick for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I)
133109467b48Spatrick if (&*I == CmpI)
133209467b48Spatrick return true;
133309467b48Spatrick
133409467b48Spatrick // Out of order.
133509467b48Spatrick Register PredR = CmpI->getOperand(0).getReg();
133609467b48Spatrick bool FoundBump = false;
133709467b48Spatrick instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(CmpIt);
133809467b48Spatrick for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) {
133909467b48Spatrick MachineInstr *In = &*I;
134009467b48Spatrick for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) {
134109467b48Spatrick MachineOperand &MO = In->getOperand(i);
134209467b48Spatrick if (MO.isReg() && MO.isUse()) {
134309467b48Spatrick if (MO.getReg() == PredR) // Found an intervening use of PredR.
134409467b48Spatrick return false;
134509467b48Spatrick }
134609467b48Spatrick }
134709467b48Spatrick
134809467b48Spatrick if (In == BumpI) {
134909467b48Spatrick BB->splice(++BumpI->getIterator(), BB, CmpI->getIterator());
135009467b48Spatrick FoundBump = true;
135109467b48Spatrick break;
135209467b48Spatrick }
135309467b48Spatrick }
135409467b48Spatrick assert (FoundBump && "Cannot determine instruction order");
135509467b48Spatrick return FoundBump;
135609467b48Spatrick }
135709467b48Spatrick
135809467b48Spatrick /// This function is required to break recursion. Visiting phis in a loop may
135909467b48Spatrick /// result in recursion during compilation. We break the recursion by making
136009467b48Spatrick /// sure that we visit a MachineOperand and its definition in a
136109467b48Spatrick /// MachineInstruction only once. If we attempt to visit more than once, then
136209467b48Spatrick /// there is recursion, and will return false.
isLoopFeeder(MachineLoop * L,MachineBasicBlock * A,MachineInstr * MI,const MachineOperand * MO,LoopFeederMap & LoopFeederPhi) const136309467b48Spatrick bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
136409467b48Spatrick MachineInstr *MI,
136509467b48Spatrick const MachineOperand *MO,
136609467b48Spatrick LoopFeederMap &LoopFeederPhi) const {
136709467b48Spatrick if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) {
136809467b48Spatrick LLVM_DEBUG(dbgs() << "\nhw_loop head, "
136909467b48Spatrick << printMBBReference(**L->block_begin()));
137009467b48Spatrick // Ignore all BBs that form Loop.
137173471bf0Spatrick if (llvm::is_contained(L->getBlocks(), A))
137209467b48Spatrick return false;
137309467b48Spatrick MachineInstr *Def = MRI->getVRegDef(MO->getReg());
137409467b48Spatrick LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def));
137509467b48Spatrick return true;
137609467b48Spatrick } else
137709467b48Spatrick // Already visited node.
137809467b48Spatrick return false;
137909467b48Spatrick }
138009467b48Spatrick
138109467b48Spatrick /// Return true if a Phi may generate a value that can underflow.
138209467b48Spatrick /// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
phiMayWrapOrUnderflow(MachineInstr * Phi,const MachineOperand * EndVal,MachineBasicBlock * MBB,MachineLoop * L,LoopFeederMap & LoopFeederPhi) const138309467b48Spatrick bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
138409467b48Spatrick MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
138509467b48Spatrick MachineLoop *L, LoopFeederMap &LoopFeederPhi) const {
138609467b48Spatrick assert(Phi->isPHI() && "Expecting a Phi.");
138709467b48Spatrick // Walk through each Phi, and its used operands. Make sure that
138809467b48Spatrick // if there is recursion in Phi, we won't generate hardware loops.
138909467b48Spatrick for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2)
139009467b48Spatrick if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi))
139109467b48Spatrick if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal,
139209467b48Spatrick Phi->getParent(), L, LoopFeederPhi))
139309467b48Spatrick return true;
139409467b48Spatrick return false;
139509467b48Spatrick }
139609467b48Spatrick
139709467b48Spatrick /// Return true if the induction variable can underflow in the first iteration.
139809467b48Spatrick /// An example, is an initial unsigned value that is 0 and is decrement in the
139909467b48Spatrick /// first itertion of a do-while loop. In this case, we cannot generate a
140009467b48Spatrick /// hardware loop because the endloop instruction does not decrement the loop
140109467b48Spatrick /// counter if it is <= 1. We only need to perform this analysis if the
140209467b48Spatrick /// initial value is a register.
140309467b48Spatrick ///
140409467b48Spatrick /// This function assumes the initial value may underfow unless proven
140509467b48Spatrick /// otherwise. If the type is signed, then we don't care because signed
140609467b48Spatrick /// underflow is undefined. We attempt to prove the initial value is not
140709467b48Spatrick /// zero by perfoming a crude analysis of the loop counter. This function
140809467b48Spatrick /// checks if the initial value is used in any comparison prior to the loop
140909467b48Spatrick /// and, if so, assumes the comparison is a range check. This is inexact,
141009467b48Spatrick /// but will catch the simple cases.
loopCountMayWrapOrUnderFlow(const MachineOperand * InitVal,const MachineOperand * EndVal,MachineBasicBlock * MBB,MachineLoop * L,LoopFeederMap & LoopFeederPhi) const141109467b48Spatrick bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
141209467b48Spatrick const MachineOperand *InitVal, const MachineOperand *EndVal,
141309467b48Spatrick MachineBasicBlock *MBB, MachineLoop *L,
141409467b48Spatrick LoopFeederMap &LoopFeederPhi) const {
141509467b48Spatrick // Only check register values since they are unknown.
141609467b48Spatrick if (!InitVal->isReg())
141709467b48Spatrick return false;
141809467b48Spatrick
141909467b48Spatrick if (!EndVal->isImm())
142009467b48Spatrick return false;
142109467b48Spatrick
142209467b48Spatrick // A register value that is assigned an immediate is a known value, and it
142309467b48Spatrick // won't underflow in the first iteration.
142409467b48Spatrick int64_t Imm;
142509467b48Spatrick if (checkForImmediate(*InitVal, Imm))
142609467b48Spatrick return (EndVal->getImm() == Imm);
142709467b48Spatrick
142809467b48Spatrick Register Reg = InitVal->getReg();
142909467b48Spatrick
143009467b48Spatrick // We don't know the value of a physical register.
143173471bf0Spatrick if (!Reg.isVirtual())
143209467b48Spatrick return true;
143309467b48Spatrick
143409467b48Spatrick MachineInstr *Def = MRI->getVRegDef(Reg);
143509467b48Spatrick if (!Def)
143609467b48Spatrick return true;
143709467b48Spatrick
143809467b48Spatrick // If the initial value is a Phi or copy and the operands may not underflow,
143909467b48Spatrick // then the definition cannot be underflow either.
144009467b48Spatrick if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),
144109467b48Spatrick L, LoopFeederPhi))
144209467b48Spatrick return false;
144309467b48Spatrick if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
144409467b48Spatrick EndVal, Def->getParent(),
144509467b48Spatrick L, LoopFeederPhi))
144609467b48Spatrick return false;
144709467b48Spatrick
144809467b48Spatrick // Iterate over the uses of the initial value. If the initial value is used
144909467b48Spatrick // in a compare, then we assume this is a range check that ensures the loop
145009467b48Spatrick // doesn't underflow. This is not an exact test and should be improved.
145109467b48Spatrick for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg),
145209467b48Spatrick E = MRI->use_instr_nodbg_end(); I != E; ++I) {
145309467b48Spatrick MachineInstr *MI = &*I;
1454097a140dSpatrick Register CmpReg1, CmpReg2;
1455*d415bd75Srobert int64_t CmpMask = 0, CmpValue = 0;
145609467b48Spatrick
145709467b48Spatrick if (!TII->analyzeCompare(*MI, CmpReg1, CmpReg2, CmpMask, CmpValue))
145809467b48Spatrick continue;
145909467b48Spatrick
146009467b48Spatrick MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
146109467b48Spatrick SmallVector<MachineOperand, 2> Cond;
146209467b48Spatrick if (TII->analyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
146309467b48Spatrick continue;
146409467b48Spatrick
146509467b48Spatrick Comparison::Kind Cmp =
146609467b48Spatrick getComparisonKind(MI->getOpcode(), nullptr, nullptr, 0);
146709467b48Spatrick if (Cmp == 0)
146809467b48Spatrick continue;
146909467b48Spatrick if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
147009467b48Spatrick Cmp = Comparison::getNegatedComparison(Cmp);
147109467b48Spatrick if (CmpReg2 != 0 && CmpReg2 == Reg)
147209467b48Spatrick Cmp = Comparison::getSwappedComparison(Cmp);
147309467b48Spatrick
147409467b48Spatrick // Signed underflow is undefined.
147509467b48Spatrick if (Comparison::isSigned(Cmp))
147609467b48Spatrick return false;
147709467b48Spatrick
147809467b48Spatrick // Check if there is a comparison of the initial value. If the initial value
147909467b48Spatrick // is greater than or not equal to another value, then assume this is a
148009467b48Spatrick // range check.
148109467b48Spatrick if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
148209467b48Spatrick return false;
148309467b48Spatrick }
148409467b48Spatrick
148509467b48Spatrick // OK - this is a hack that needs to be improved. We really need to analyze
148609467b48Spatrick // the instructions performed on the initial value. This works on the simplest
148709467b48Spatrick // cases only.
148809467b48Spatrick if (!Def->isCopy() && !Def->isPHI())
148909467b48Spatrick return false;
149009467b48Spatrick
149109467b48Spatrick return true;
149209467b48Spatrick }
149309467b48Spatrick
checkForImmediate(const MachineOperand & MO,int64_t & Val) const149409467b48Spatrick bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
149509467b48Spatrick int64_t &Val) const {
149609467b48Spatrick if (MO.isImm()) {
149709467b48Spatrick Val = MO.getImm();
149809467b48Spatrick return true;
149909467b48Spatrick }
150009467b48Spatrick if (!MO.isReg())
150109467b48Spatrick return false;
150209467b48Spatrick
150309467b48Spatrick // MO is a register. Check whether it is defined as an immediate value,
150409467b48Spatrick // and if so, get the value of it in TV. That value will then need to be
150509467b48Spatrick // processed to handle potential subregisters in MO.
150609467b48Spatrick int64_t TV;
150709467b48Spatrick
150809467b48Spatrick Register R = MO.getReg();
150973471bf0Spatrick if (!R.isVirtual())
151009467b48Spatrick return false;
151109467b48Spatrick MachineInstr *DI = MRI->getVRegDef(R);
151209467b48Spatrick unsigned DOpc = DI->getOpcode();
151309467b48Spatrick switch (DOpc) {
151409467b48Spatrick case TargetOpcode::COPY:
151509467b48Spatrick case Hexagon::A2_tfrsi:
151609467b48Spatrick case Hexagon::A2_tfrpi:
151709467b48Spatrick case Hexagon::CONST32:
151809467b48Spatrick case Hexagon::CONST64:
151909467b48Spatrick // Call recursively to avoid an extra check whether operand(1) is
152009467b48Spatrick // indeed an immediate (it could be a global address, for example),
152109467b48Spatrick // plus we can handle COPY at the same time.
152209467b48Spatrick if (!checkForImmediate(DI->getOperand(1), TV))
152309467b48Spatrick return false;
152409467b48Spatrick break;
152509467b48Spatrick case Hexagon::A2_combineii:
152609467b48Spatrick case Hexagon::A4_combineir:
152709467b48Spatrick case Hexagon::A4_combineii:
152809467b48Spatrick case Hexagon::A4_combineri:
152909467b48Spatrick case Hexagon::A2_combinew: {
153009467b48Spatrick const MachineOperand &S1 = DI->getOperand(1);
153109467b48Spatrick const MachineOperand &S2 = DI->getOperand(2);
153209467b48Spatrick int64_t V1, V2;
153309467b48Spatrick if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))
153409467b48Spatrick return false;
153509467b48Spatrick TV = V2 | (static_cast<uint64_t>(V1) << 32);
153609467b48Spatrick break;
153709467b48Spatrick }
153809467b48Spatrick case TargetOpcode::REG_SEQUENCE: {
153909467b48Spatrick const MachineOperand &S1 = DI->getOperand(1);
154009467b48Spatrick const MachineOperand &S3 = DI->getOperand(3);
154109467b48Spatrick int64_t V1, V3;
154209467b48Spatrick if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
154309467b48Spatrick return false;
154409467b48Spatrick unsigned Sub2 = DI->getOperand(2).getImm();
154509467b48Spatrick unsigned Sub4 = DI->getOperand(4).getImm();
154609467b48Spatrick if (Sub2 == Hexagon::isub_lo && Sub4 == Hexagon::isub_hi)
154709467b48Spatrick TV = V1 | (V3 << 32);
154809467b48Spatrick else if (Sub2 == Hexagon::isub_hi && Sub4 == Hexagon::isub_lo)
154909467b48Spatrick TV = V3 | (V1 << 32);
155009467b48Spatrick else
155109467b48Spatrick llvm_unreachable("Unexpected form of REG_SEQUENCE");
155209467b48Spatrick break;
155309467b48Spatrick }
155409467b48Spatrick
155509467b48Spatrick default:
155609467b48Spatrick return false;
155709467b48Spatrick }
155809467b48Spatrick
155909467b48Spatrick // By now, we should have successfully obtained the immediate value defining
156009467b48Spatrick // the register referenced in MO. Handle a potential use of a subregister.
156109467b48Spatrick switch (MO.getSubReg()) {
156209467b48Spatrick case Hexagon::isub_lo:
156309467b48Spatrick Val = TV & 0xFFFFFFFFULL;
156409467b48Spatrick break;
156509467b48Spatrick case Hexagon::isub_hi:
156609467b48Spatrick Val = (TV >> 32) & 0xFFFFFFFFULL;
156709467b48Spatrick break;
156809467b48Spatrick default:
156909467b48Spatrick Val = TV;
157009467b48Spatrick break;
157109467b48Spatrick }
157209467b48Spatrick return true;
157309467b48Spatrick }
157409467b48Spatrick
setImmediate(MachineOperand & MO,int64_t Val)157509467b48Spatrick void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
157609467b48Spatrick if (MO.isImm()) {
157709467b48Spatrick MO.setImm(Val);
157809467b48Spatrick return;
157909467b48Spatrick }
158009467b48Spatrick
158109467b48Spatrick assert(MO.isReg());
158209467b48Spatrick Register R = MO.getReg();
158309467b48Spatrick MachineInstr *DI = MRI->getVRegDef(R);
158409467b48Spatrick
158509467b48Spatrick const TargetRegisterClass *RC = MRI->getRegClass(R);
158609467b48Spatrick Register NewR = MRI->createVirtualRegister(RC);
158709467b48Spatrick MachineBasicBlock &B = *DI->getParent();
158809467b48Spatrick DebugLoc DL = DI->getDebugLoc();
158909467b48Spatrick BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val);
159009467b48Spatrick MO.setReg(NewR);
159109467b48Spatrick }
159209467b48Spatrick
fixupInductionVariable(MachineLoop * L)159309467b48Spatrick bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
159409467b48Spatrick MachineBasicBlock *Header = L->getHeader();
159509467b48Spatrick MachineBasicBlock *Latch = L->getLoopLatch();
159609467b48Spatrick MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
159709467b48Spatrick
159809467b48Spatrick if (!(Header && Latch && ExitingBlock))
159909467b48Spatrick return false;
160009467b48Spatrick
160109467b48Spatrick // These data structures follow the same concept as the corresponding
160209467b48Spatrick // ones in findInductionRegister (where some comments are).
1603*d415bd75Srobert using RegisterBump = std::pair<Register, int64_t>;
1604*d415bd75Srobert using RegisterInduction = std::pair<Register, RegisterBump>;
160509467b48Spatrick using RegisterInductionSet = std::set<RegisterInduction>;
160609467b48Spatrick
160709467b48Spatrick // Register candidates for induction variables, with their associated bumps.
160809467b48Spatrick RegisterInductionSet IndRegs;
160909467b48Spatrick
161009467b48Spatrick // Look for induction patterns:
161109467b48Spatrick // %1 = PHI ..., [ latch, %2 ]
161209467b48Spatrick // %2 = ADD %1, imm
161309467b48Spatrick using instr_iterator = MachineBasicBlock::instr_iterator;
161409467b48Spatrick
161509467b48Spatrick for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
161609467b48Spatrick I != E && I->isPHI(); ++I) {
161709467b48Spatrick MachineInstr *Phi = &*I;
161809467b48Spatrick
161909467b48Spatrick // Have a PHI instruction.
162009467b48Spatrick for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
162109467b48Spatrick if (Phi->getOperand(i+1).getMBB() != Latch)
162209467b48Spatrick continue;
162309467b48Spatrick
162409467b48Spatrick Register PhiReg = Phi->getOperand(i).getReg();
162509467b48Spatrick MachineInstr *DI = MRI->getVRegDef(PhiReg);
162609467b48Spatrick
162709467b48Spatrick if (DI->getDesc().isAdd()) {
162809467b48Spatrick // If the register operand to the add/sub is the PHI we are looking
162909467b48Spatrick // at, this meets the induction pattern.
163009467b48Spatrick Register IndReg = DI->getOperand(1).getReg();
163109467b48Spatrick MachineOperand &Opnd2 = DI->getOperand(2);
163209467b48Spatrick int64_t V;
163309467b48Spatrick if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
163409467b48Spatrick Register UpdReg = DI->getOperand(0).getReg();
163509467b48Spatrick IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));
163609467b48Spatrick }
163709467b48Spatrick }
163809467b48Spatrick } // for (i)
163909467b48Spatrick } // for (instr)
164009467b48Spatrick
164109467b48Spatrick if (IndRegs.empty())
164209467b48Spatrick return false;
164309467b48Spatrick
164409467b48Spatrick MachineBasicBlock *TB = nullptr, *FB = nullptr;
164509467b48Spatrick SmallVector<MachineOperand,2> Cond;
1646097a140dSpatrick // analyzeBranch returns true if it fails to analyze branch.
164709467b48Spatrick bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false);
164809467b48Spatrick if (NotAnalyzed || Cond.empty())
164909467b48Spatrick return false;
165009467b48Spatrick
165109467b48Spatrick if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) {
165209467b48Spatrick MachineBasicBlock *LTB = nullptr, *LFB = nullptr;
165309467b48Spatrick SmallVector<MachineOperand,2> LCond;
165409467b48Spatrick bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false);
165509467b48Spatrick if (NotAnalyzed)
165609467b48Spatrick return false;
165709467b48Spatrick
165809467b48Spatrick // Since latch is not the exiting block, the latch branch should be an
165909467b48Spatrick // unconditional branch to the loop header.
166009467b48Spatrick if (TB == Latch)
166109467b48Spatrick TB = (LTB == Header) ? LTB : LFB;
166209467b48Spatrick else
166309467b48Spatrick FB = (LTB == Header) ? LTB : LFB;
166409467b48Spatrick }
166509467b48Spatrick if (TB != Header) {
166609467b48Spatrick if (FB != Header) {
166709467b48Spatrick // The latch/exit block does not go back to the header.
166809467b48Spatrick return false;
166909467b48Spatrick }
167009467b48Spatrick // FB is the header (i.e., uncond. jump to branch header)
167109467b48Spatrick // In this case, the LoopBody -> TB should not be a back edge otherwise
167209467b48Spatrick // it could result in an infinite loop after conversion to hw_loop.
167309467b48Spatrick // This case can happen when the Latch has two jumps like this:
167409467b48Spatrick // Jmp_c OuterLoopHeader <-- TB
167509467b48Spatrick // Jmp InnerLoopHeader <-- FB
167609467b48Spatrick if (MDT->dominates(TB, FB))
167709467b48Spatrick return false;
167809467b48Spatrick }
167909467b48Spatrick
168009467b48Spatrick // Expecting a predicate register as a condition. It won't be a hardware
168109467b48Spatrick // predicate register at this point yet, just a vreg.
1682097a140dSpatrick // HexagonInstrInfo::analyzeBranch for negated branches inserts imm(0)
168309467b48Spatrick // into Cond, followed by the predicate register. For non-negated branches
168409467b48Spatrick // it's just the register.
168509467b48Spatrick unsigned CSz = Cond.size();
168609467b48Spatrick if (CSz != 1 && CSz != 2)
168709467b48Spatrick return false;
168809467b48Spatrick
168909467b48Spatrick if (!Cond[CSz-1].isReg())
169009467b48Spatrick return false;
169109467b48Spatrick
169209467b48Spatrick Register P = Cond[CSz - 1].getReg();
169309467b48Spatrick MachineInstr *PredDef = MRI->getVRegDef(P);
169409467b48Spatrick
169509467b48Spatrick if (!PredDef->isCompare())
169609467b48Spatrick return false;
169709467b48Spatrick
1698*d415bd75Srobert SmallSet<Register,2> CmpRegs;
169909467b48Spatrick MachineOperand *CmpImmOp = nullptr;
170009467b48Spatrick
170109467b48Spatrick // Go over all operands to the compare and look for immediate and register
170209467b48Spatrick // operands. Assume that if the compare has a single register use and a
170309467b48Spatrick // single immediate operand, then the register is being compared with the
170409467b48Spatrick // immediate value.
170509467b48Spatrick for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
170609467b48Spatrick MachineOperand &MO = PredDef->getOperand(i);
170709467b48Spatrick if (MO.isReg()) {
170809467b48Spatrick // Skip all implicit references. In one case there was:
170909467b48Spatrick // %140 = FCMPUGT32_rr %138, %139, implicit %usr
171009467b48Spatrick if (MO.isImplicit())
171109467b48Spatrick continue;
171209467b48Spatrick if (MO.isUse()) {
171309467b48Spatrick if (!isImmediate(MO)) {
171409467b48Spatrick CmpRegs.insert(MO.getReg());
171509467b48Spatrick continue;
171609467b48Spatrick }
171709467b48Spatrick // Consider the register to be the "immediate" operand.
171809467b48Spatrick if (CmpImmOp)
171909467b48Spatrick return false;
172009467b48Spatrick CmpImmOp = &MO;
172109467b48Spatrick }
172209467b48Spatrick } else if (MO.isImm()) {
172309467b48Spatrick if (CmpImmOp) // A second immediate argument? Confusing. Bail out.
172409467b48Spatrick return false;
172509467b48Spatrick CmpImmOp = &MO;
172609467b48Spatrick }
172709467b48Spatrick }
172809467b48Spatrick
172909467b48Spatrick if (CmpRegs.empty())
173009467b48Spatrick return false;
173109467b48Spatrick
173209467b48Spatrick // Check if the compared register follows the order we want. Fix if needed.
173309467b48Spatrick for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end();
173409467b48Spatrick I != E; ++I) {
173509467b48Spatrick // This is a success. If the register used in the comparison is one that
173609467b48Spatrick // we have identified as a bumped (updated) induction register, there is
173709467b48Spatrick // nothing to do.
173809467b48Spatrick if (CmpRegs.count(I->first))
173909467b48Spatrick return true;
174009467b48Spatrick
174109467b48Spatrick // Otherwise, if the register being compared comes out of a PHI node,
174209467b48Spatrick // and has been recognized as following the induction pattern, and is
174309467b48Spatrick // compared against an immediate, we can fix it.
174409467b48Spatrick const RegisterBump &RB = I->second;
174509467b48Spatrick if (CmpRegs.count(RB.first)) {
174609467b48Spatrick if (!CmpImmOp) {
174709467b48Spatrick // If both operands to the compare instruction are registers, see if
174809467b48Spatrick // it can be changed to use induction register as one of the operands.
174909467b48Spatrick MachineInstr *IndI = nullptr;
175009467b48Spatrick MachineInstr *nonIndI = nullptr;
175109467b48Spatrick MachineOperand *IndMO = nullptr;
175209467b48Spatrick MachineOperand *nonIndMO = nullptr;
175309467b48Spatrick
175409467b48Spatrick for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) {
175509467b48Spatrick MachineOperand &MO = PredDef->getOperand(i);
175609467b48Spatrick if (MO.isReg() && MO.getReg() == RB.first) {
175709467b48Spatrick LLVM_DEBUG(dbgs() << "\n DefMI(" << i
175809467b48Spatrick << ") = " << *(MRI->getVRegDef(I->first)));
175909467b48Spatrick if (IndI)
176009467b48Spatrick return false;
176109467b48Spatrick
176209467b48Spatrick IndI = MRI->getVRegDef(I->first);
176309467b48Spatrick IndMO = &MO;
176409467b48Spatrick } else if (MO.isReg()) {
176509467b48Spatrick LLVM_DEBUG(dbgs() << "\n DefMI(" << i
176609467b48Spatrick << ") = " << *(MRI->getVRegDef(MO.getReg())));
176709467b48Spatrick if (nonIndI)
176809467b48Spatrick return false;
176909467b48Spatrick
177009467b48Spatrick nonIndI = MRI->getVRegDef(MO.getReg());
177109467b48Spatrick nonIndMO = &MO;
177209467b48Spatrick }
177309467b48Spatrick }
177409467b48Spatrick if (IndI && nonIndI &&
177509467b48Spatrick nonIndI->getOpcode() == Hexagon::A2_addi &&
177609467b48Spatrick nonIndI->getOperand(2).isImm() &&
177709467b48Spatrick nonIndI->getOperand(2).getImm() == - RB.second) {
177809467b48Spatrick bool Order = orderBumpCompare(IndI, PredDef);
177909467b48Spatrick if (Order) {
178009467b48Spatrick IndMO->setReg(I->first);
178109467b48Spatrick nonIndMO->setReg(nonIndI->getOperand(1).getReg());
178209467b48Spatrick return true;
178309467b48Spatrick }
178409467b48Spatrick }
178509467b48Spatrick return false;
178609467b48Spatrick }
178709467b48Spatrick
178809467b48Spatrick // It is not valid to do this transformation on an unsigned comparison
178909467b48Spatrick // because it may underflow.
179009467b48Spatrick Comparison::Kind Cmp =
179109467b48Spatrick getComparisonKind(PredDef->getOpcode(), nullptr, nullptr, 0);
179209467b48Spatrick if (!Cmp || Comparison::isUnsigned(Cmp))
179309467b48Spatrick return false;
179409467b48Spatrick
179509467b48Spatrick // If the register is being compared against an immediate, try changing
179609467b48Spatrick // the compare instruction to use induction register and adjust the
179709467b48Spatrick // immediate operand.
179809467b48Spatrick int64_t CmpImm = getImmediate(*CmpImmOp);
179909467b48Spatrick int64_t V = RB.second;
180009467b48Spatrick // Handle Overflow (64-bit).
180109467b48Spatrick if (((V > 0) && (CmpImm > INT64_MAX - V)) ||
180209467b48Spatrick ((V < 0) && (CmpImm < INT64_MIN - V)))
180309467b48Spatrick return false;
180409467b48Spatrick CmpImm += V;
180509467b48Spatrick // Most comparisons of register against an immediate value allow
180609467b48Spatrick // the immediate to be constant-extended. There are some exceptions
180709467b48Spatrick // though. Make sure the new combination will work.
1808*d415bd75Srobert if (CmpImmOp->isImm() && !TII->isExtendable(*PredDef) &&
1809*d415bd75Srobert !TII->isValidOffset(PredDef->getOpcode(), CmpImm, TRI, false))
181009467b48Spatrick return false;
181109467b48Spatrick
181209467b48Spatrick // Make sure that the compare happens after the bump. Otherwise,
181309467b48Spatrick // after the fixup, the compare would use a yet-undefined register.
181409467b48Spatrick MachineInstr *BumpI = MRI->getVRegDef(I->first);
181509467b48Spatrick bool Order = orderBumpCompare(BumpI, PredDef);
181609467b48Spatrick if (!Order)
181709467b48Spatrick return false;
181809467b48Spatrick
181909467b48Spatrick // Finally, fix the compare instruction.
182009467b48Spatrick setImmediate(*CmpImmOp, CmpImm);
182109467b48Spatrick for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) {
182209467b48Spatrick MachineOperand &MO = PredDef->getOperand(i);
182309467b48Spatrick if (MO.isReg() && MO.getReg() == RB.first) {
182409467b48Spatrick MO.setReg(I->first);
182509467b48Spatrick return true;
182609467b48Spatrick }
182709467b48Spatrick }
182809467b48Spatrick }
182909467b48Spatrick }
183009467b48Spatrick
183109467b48Spatrick return false;
183209467b48Spatrick }
183309467b48Spatrick
183409467b48Spatrick /// createPreheaderForLoop - Create a preheader for a given loop.
createPreheaderForLoop(MachineLoop * L)183509467b48Spatrick MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
183609467b48Spatrick MachineLoop *L) {
183709467b48Spatrick if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpecPreheader))
183809467b48Spatrick return TmpPH;
183909467b48Spatrick if (!HWCreatePreheader)
184009467b48Spatrick return nullptr;
184109467b48Spatrick
184209467b48Spatrick MachineBasicBlock *Header = L->getHeader();
184309467b48Spatrick MachineBasicBlock *Latch = L->getLoopLatch();
184409467b48Spatrick MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
184509467b48Spatrick MachineFunction *MF = Header->getParent();
184609467b48Spatrick DebugLoc DL;
184709467b48Spatrick
184809467b48Spatrick #ifndef NDEBUG
184909467b48Spatrick if ((!PHFn.empty()) && (PHFn != MF->getName()))
185009467b48Spatrick return nullptr;
185109467b48Spatrick #endif
185209467b48Spatrick
185309467b48Spatrick if (!Latch || !ExitingBlock || Header->hasAddressTaken())
185409467b48Spatrick return nullptr;
185509467b48Spatrick
185609467b48Spatrick using instr_iterator = MachineBasicBlock::instr_iterator;
185709467b48Spatrick
185809467b48Spatrick // Verify that all existing predecessors have analyzable branches
185909467b48Spatrick // (or no branches at all).
186009467b48Spatrick using MBBVector = std::vector<MachineBasicBlock *>;
186109467b48Spatrick
186209467b48Spatrick MBBVector Preds(Header->pred_begin(), Header->pred_end());
186309467b48Spatrick SmallVector<MachineOperand,2> Tmp1;
186409467b48Spatrick MachineBasicBlock *TB = nullptr, *FB = nullptr;
186509467b48Spatrick
186609467b48Spatrick if (TII->analyzeBranch(*ExitingBlock, TB, FB, Tmp1, false))
186709467b48Spatrick return nullptr;
186809467b48Spatrick
1869*d415bd75Srobert for (MachineBasicBlock *PB : Preds) {
187009467b48Spatrick bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp1, false);
187109467b48Spatrick if (NotAnalyzed)
187209467b48Spatrick return nullptr;
187309467b48Spatrick }
187409467b48Spatrick
187509467b48Spatrick MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock();
187609467b48Spatrick MF->insert(Header->getIterator(), NewPH);
187709467b48Spatrick
187809467b48Spatrick if (Header->pred_size() > 2) {
187909467b48Spatrick // Ensure that the header has only two predecessors: the preheader and
188009467b48Spatrick // the loop latch. Any additional predecessors of the header should
188109467b48Spatrick // join at the newly created preheader. Inspect all PHI nodes from the
188209467b48Spatrick // header and create appropriate corresponding PHI nodes in the preheader.
188309467b48Spatrick
188409467b48Spatrick for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
188509467b48Spatrick I != E && I->isPHI(); ++I) {
188609467b48Spatrick MachineInstr *PN = &*I;
188709467b48Spatrick
188809467b48Spatrick const MCInstrDesc &PD = TII->get(TargetOpcode::PHI);
188909467b48Spatrick MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL);
189009467b48Spatrick NewPH->insert(NewPH->end(), NewPN);
189109467b48Spatrick
189209467b48Spatrick Register PR = PN->getOperand(0).getReg();
189309467b48Spatrick const TargetRegisterClass *RC = MRI->getRegClass(PR);
189409467b48Spatrick Register NewPR = MRI->createVirtualRegister(RC);
189509467b48Spatrick NewPN->addOperand(MachineOperand::CreateReg(NewPR, true));
189609467b48Spatrick
189709467b48Spatrick // Copy all non-latch operands of a header's PHI node to the newly
189809467b48Spatrick // created PHI node in the preheader.
189909467b48Spatrick for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
190009467b48Spatrick Register PredR = PN->getOperand(i).getReg();
190109467b48Spatrick unsigned PredRSub = PN->getOperand(i).getSubReg();
190209467b48Spatrick MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
190309467b48Spatrick if (PredB == Latch)
190409467b48Spatrick continue;
190509467b48Spatrick
190609467b48Spatrick MachineOperand MO = MachineOperand::CreateReg(PredR, false);
190709467b48Spatrick MO.setSubReg(PredRSub);
190809467b48Spatrick NewPN->addOperand(MO);
190909467b48Spatrick NewPN->addOperand(MachineOperand::CreateMBB(PredB));
191009467b48Spatrick }
191109467b48Spatrick
191209467b48Spatrick // Remove copied operands from the old PHI node and add the value
191309467b48Spatrick // coming from the preheader's PHI.
191409467b48Spatrick for (int i = PN->getNumOperands()-2; i > 0; i -= 2) {
191509467b48Spatrick MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB();
191609467b48Spatrick if (PredB != Latch) {
1917*d415bd75Srobert PN->removeOperand(i+1);
1918*d415bd75Srobert PN->removeOperand(i);
191909467b48Spatrick }
192009467b48Spatrick }
192109467b48Spatrick PN->addOperand(MachineOperand::CreateReg(NewPR, false));
192209467b48Spatrick PN->addOperand(MachineOperand::CreateMBB(NewPH));
192309467b48Spatrick }
192409467b48Spatrick } else {
192509467b48Spatrick assert(Header->pred_size() == 2);
192609467b48Spatrick
192709467b48Spatrick // The header has only two predecessors, but the non-latch predecessor
192809467b48Spatrick // is not a preheader (e.g. it has other successors, etc.)
192909467b48Spatrick // In such a case we don't need any extra PHI nodes in the new preheader,
193009467b48Spatrick // all we need is to adjust existing PHIs in the header to now refer to
193109467b48Spatrick // the new preheader.
193209467b48Spatrick for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
193309467b48Spatrick I != E && I->isPHI(); ++I) {
193409467b48Spatrick MachineInstr *PN = &*I;
193509467b48Spatrick for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) {
193609467b48Spatrick MachineOperand &MO = PN->getOperand(i+1);
193709467b48Spatrick if (MO.getMBB() != Latch)
193809467b48Spatrick MO.setMBB(NewPH);
193909467b48Spatrick }
194009467b48Spatrick }
194109467b48Spatrick }
194209467b48Spatrick
194309467b48Spatrick // "Reroute" the CFG edges to link in the new preheader.
194409467b48Spatrick // If any of the predecessors falls through to the header, insert a branch
194509467b48Spatrick // to the new preheader in that place.
194609467b48Spatrick SmallVector<MachineOperand,1> Tmp2;
194709467b48Spatrick SmallVector<MachineOperand,1> EmptyCond;
194809467b48Spatrick
194909467b48Spatrick TB = FB = nullptr;
195009467b48Spatrick
1951*d415bd75Srobert for (MachineBasicBlock *PB : Preds) {
195209467b48Spatrick if (PB != Latch) {
195309467b48Spatrick Tmp2.clear();
195409467b48Spatrick bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp2, false);
195509467b48Spatrick (void)NotAnalyzed; // suppress compiler warning
195609467b48Spatrick assert (!NotAnalyzed && "Should be analyzable!");
195709467b48Spatrick if (TB != Header && (Tmp2.empty() || FB != Header))
195809467b48Spatrick TII->insertBranch(*PB, NewPH, nullptr, EmptyCond, DL);
195909467b48Spatrick PB->ReplaceUsesOfBlockWith(Header, NewPH);
196009467b48Spatrick }
196109467b48Spatrick }
196209467b48Spatrick
196309467b48Spatrick // It can happen that the latch block will fall through into the header.
196409467b48Spatrick // Insert an unconditional branch to the header.
196509467b48Spatrick TB = FB = nullptr;
196609467b48Spatrick bool LatchNotAnalyzed = TII->analyzeBranch(*Latch, TB, FB, Tmp2, false);
196709467b48Spatrick (void)LatchNotAnalyzed; // suppress compiler warning
196809467b48Spatrick assert (!LatchNotAnalyzed && "Should be analyzable!");
196909467b48Spatrick if (!TB && !FB)
197009467b48Spatrick TII->insertBranch(*Latch, Header, nullptr, EmptyCond, DL);
197109467b48Spatrick
197209467b48Spatrick // Finally, the branch from the preheader to the header.
197309467b48Spatrick TII->insertBranch(*NewPH, Header, nullptr, EmptyCond, DL);
197409467b48Spatrick NewPH->addSuccessor(Header);
197509467b48Spatrick
197609467b48Spatrick MachineLoop *ParentLoop = L->getParentLoop();
197709467b48Spatrick if (ParentLoop)
197809467b48Spatrick ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase());
197909467b48Spatrick
198009467b48Spatrick // Update the dominator information with the new preheader.
198109467b48Spatrick if (MDT) {
198209467b48Spatrick if (MachineDomTreeNode *HN = MDT->getNode(Header)) {
198309467b48Spatrick if (MachineDomTreeNode *DHN = HN->getIDom()) {
198409467b48Spatrick MDT->addNewBlock(NewPH, DHN->getBlock());
198509467b48Spatrick MDT->changeImmediateDominator(Header, NewPH);
198609467b48Spatrick }
198709467b48Spatrick }
198809467b48Spatrick }
198909467b48Spatrick
199009467b48Spatrick return NewPH;
199109467b48Spatrick }
1992