1b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum//===-- HexagonHardwareLoops.cpp - Identify and generate hardware loops ---===// 2b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// 3b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// The LLVM Compiler Infrastructure 4b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// 5b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// This file is distributed under the University of Illinois Open Source 6b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// License. See LICENSE.TXT for details. 7b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// 8b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum//===----------------------------------------------------------------------===// 9b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// 10b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// This pass identifies loops where we can generate the Hexagon hardware 11b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// loop instruction. The hardware loop can perform loop branches with a 12b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// zero-cycle overhead. 13b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// 14b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// The pattern that defines the induction variable can changed depending on 15b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// prior optimizations. For example, the IndVarSimplify phase run by 'opt' 16b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// normalizes induction variables, and the Loop Strength Reduction pass 17b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// run by 'llc' may also make changes to the induction variable. 18b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// The pattern detected by this phase is due to running Strength Reduction. 19b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// 20b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// Criteria for hardware loops: 21b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// - Countable loops (w/ ind. var for a trip count) 22b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// - Assumes loops are normalized by IndVarSimplify 23b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// - Try inner-most loops first 24b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// - No nested hardware loops. 25b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// - No function calls in loops. 26b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// 27b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum//===----------------------------------------------------------------------===// 28b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 2971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#include "llvm/ADT/SmallSet.h" 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "Hexagon.h" 31ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "HexagonSubtarget.h" 32b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/ADT/Statistic.h" 33b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineDominators.h" 34b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineFunction.h" 35b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineFunctionPass.h" 36b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineInstrBuilder.h" 37b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineLoopInfo.h" 38b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineRegisterInfo.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/PassSupport.h" 4071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#include "llvm/Support/CommandLine.h" 41b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/Support/Debug.h" 42b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/Support/raw_ostream.h" 43b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/Target/TargetInstrInfo.h" 44b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include <algorithm> 4571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#include <vector> 46b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 47b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumusing namespace llvm; 48b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "hwloops" 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 5171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#ifndef NDEBUG 5271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekstatic cl::opt<int> HWLoopLimit("max-hwloop", cl::Hidden, cl::init(-1)); 5371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#endif 5471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 55b4b54153ad760c69a00a08531abef4ed434a5092Tony LinthicumSTATISTIC(NumHWLoops, "Number of loops converted to hardware loops"); 56b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 5771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszeknamespace llvm { 5871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek void initializeHexagonHardwareLoopsPass(PassRegistry&); 5971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 6071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 61b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumnamespace { 62b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum class CountValue; 63b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum struct HexagonHardwareLoops : public MachineFunctionPass { 6471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineLoopInfo *MLI; 6571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineRegisterInfo *MRI; 6671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineDominatorTree *MDT; 6771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const HexagonInstrInfo *TII; 6871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#ifndef NDEBUG 6971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek static int Counter; 7071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#endif 71b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 72b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum public: 7371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek static char ID; 74b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 7571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek HexagonHardwareLoops() : MachineFunctionPass(ID) { 7671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry()); 7771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 78b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool runOnMachineFunction(MachineFunction &MF) override; 80b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 81dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *getPassName() const override { return "Hexagon Hardware Loops"; } 82b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 84b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum AU.addRequired<MachineDominatorTree>(); 85b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum AU.addRequired<MachineLoopInfo>(); 86b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineFunctionPass::getAnalysisUsage(AU); 87b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 88b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 89b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum private: 9071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Kinds of comparisons in the compare instructions. 9171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek struct Comparison { 9271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek enum Kind { 9371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EQ = 0x01, 9471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NE = 0x02, 9571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek L = 0x04, // Less-than property. 9671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek G = 0x08, // Greater-than property. 9771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek U = 0x40, // Unsigned property. 9871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LTs = L, 9971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LEs = L | EQ, 10071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek GTs = G, 10171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek GEs = G | EQ, 10271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LTu = L | U, 10371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LEu = L | EQ | U, 10471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek GTu = G | U, 10571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek GEu = G | EQ | U 10671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek }; 10771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 10871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek static Kind getSwappedComparison(Kind Cmp) { 10971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator"); 11071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if ((Cmp & L) || (Cmp & G)) 11171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return (Kind)(Cmp ^ (L|G)); 11271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return Cmp; 11371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 11471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek }; 115b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 11671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Find the register that contains the loop controlling 11771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// induction variable. 11871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// If successful, it will return true and set the \p Reg, \p IVBump 11971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// and \p IVOp arguments. Otherwise it will return false. 12071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// The returned induction register is the register R that follows the 12171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// following induction pattern: 12271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// loop: 12371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// R = phi ..., [ R.next, LatchBlock ] 12471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// R.next = R + #bump 12571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// if (R.next < #N) goto loop 12671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// IVBump is the immediate value added to R, and IVOp is the instruction 12771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// "R.next = R + #bump". 12871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool findInductionRegister(MachineLoop *L, unsigned &Reg, 12971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t &IVBump, MachineInstr *&IVOp) const; 13071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 13171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Analyze the statements in a loop to determine if the loop 13271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// has a computable trip count and, if so, return a value that represents 13371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// the trip count expression. 13471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountValue *getLoopTripCount(MachineLoop *L, 135a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &OldInsts); 13671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 13771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Return the expression that represents the number of times 13871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// a loop iterates. The function takes the operands that represent the 13971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// loop start value, loop end value, and induction value. Based upon 14071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// these operands, the function attempts to compute the trip count. 14171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// If the trip count is not directly available (as an immediate value, 14271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// or a register), the function will attempt to insert computation of it 14371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// to the loop's preheader. 14471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountValue *computeCount(MachineLoop *Loop, 14571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand *Start, 14671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand *End, 14771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IVReg, 14871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t IVBump, 14971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Comparison::Kind Cmp) const; 15071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 15171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Return true if the instruction is not valid within a hardware 15271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// loop. 153b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool isInvalidLoopOperation(const MachineInstr *MI) const; 154b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 15571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Return true if the loop contains an instruction that inhibits 15671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// using the hardware loop. 157b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool containsInvalidInstruction(MachineLoop *L) const; 158b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 15971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Given a loop, check if we can convert it to a hardware loop. 16071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// If so, then perform the conversion and return true. 161b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool convertToHardwareLoop(MachineLoop *L); 162b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 16371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Return true if the instruction is now dead. 16471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool isDead(const MachineInstr *MI, 165a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &DeadPhis) const; 16671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 16771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Remove the instruction if it is now dead. 16871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek void removeIfDead(MachineInstr *MI); 16971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 17071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Make sure that the "bump" instruction executes before the 17171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// compare. We need that for the IV fixup, so that the compare 17271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// instruction would not use a bumped value that has not yet been 17371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// defined. If the instructions are out of order, try to reorder them. 17471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI); 17571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 17671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Get the instruction that loads an immediate value into \p R, 17771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// or 0 if such an instruction does not exist. 17871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *defWithImmediate(unsigned R); 17971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 18071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Get the immediate value referenced to by \p MO, either for 18171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// immediate operands, or for register operands, where the register 18271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// was defined with an immediate value. 18371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t getImmediate(MachineOperand &MO); 18471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 18571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Reset the given machine operand to now refer to a new immediate 18671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// value. Assumes that the operand was already referencing an immediate 18771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// value, either directly, or via a register. 18871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek void setImmediate(MachineOperand &MO, int64_t Val); 18971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 19071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Fix the data flow of the induction varible. 19171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// The desired flow is: phi ---> bump -+-> comparison-in-latch. 19271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// | 19371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// +-> back to phi 19471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// where "bump" is the increment of the induction variable: 19571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// iv = iv + #const. 19671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Due to some prior code transformations, the actual flow may look 19771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// like this: 19871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// phi -+-> bump ---> back to phi 19971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// | 20071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// +-> comparison-in-latch (against upper_bound-bump), 20171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// i.e. the comparison that controls the loop execution may be using 20271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// the value of the induction variable from before the increment. 20371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// 20471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Return true if the loop's flow is the desired one (i.e. it's 20571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// either been fixed, or no fixing was necessary). 20671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Otherwise, return false. This can happen if the induction variable 20771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// couldn't be identified, or if the value in the latch's comparison 20871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// cannot be adjusted to reflect the post-bump value. 20971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool fixupInductionVariable(MachineLoop *L); 21071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 21171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Given a loop, if it does not have a preheader, create one. 21271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Return the block that is the preheader. 21371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *createPreheaderForLoop(MachineLoop *L); 214b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum }; 215b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 216b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum char HexagonHardwareLoops::ID = 0; 21771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#ifndef NDEBUG 21871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int HexagonHardwareLoops::Counter = 0; 21971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#endif 220b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 22137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /// \brief Abstraction for a trip count of a loop. A smaller version 22271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// of the MachineOperand class without the concerns of changing the 22371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// operand representation. 224b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum class CountValue { 225b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum public: 226b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum enum CountValueType { 227b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum CV_Register, 228b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum CV_Immediate 229b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum }; 230b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum private: 231b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum CountValueType Kind; 232b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum union Values { 23371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek struct { 23471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Reg; 23571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Sub; 23671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } R; 23771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned ImmVal; 238b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } Contents; 239b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 240b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum public: 24171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) { 24271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Kind = t; 24371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Kind == CV_Register) { 24471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Contents.R.Reg = v; 24571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Contents.R.Sub = u; 24671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 24771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Contents.ImmVal = v; 24871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 24971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 250b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool isReg() const { return Kind == CV_Register; } 251b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool isImm() const { return Kind == CV_Immediate; } 252b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 253b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum unsigned getReg() const { 254b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum assert(isReg() && "Wrong CountValue accessor"); 25571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return Contents.R.Reg; 256b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 25771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned getSubReg() const { 25871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(isReg() && "Wrong CountValue accessor"); 25971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return Contents.R.Sub; 260b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 26171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned getImm() const { 262b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum assert(isImm() && "Wrong CountValue accessor"); 263b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return Contents.ImmVal; 264b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 265b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 266ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const { 26771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); } 26871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isImm()) { OS << Contents.ImmVal; } 269b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 270b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum }; 27171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} // end anonymous namespace 272b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 273b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 27471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekINITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops", 27571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek "Hexagon Hardware Loops", false, false) 27671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 27771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 27871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekINITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops", 27971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek "Hexagon Hardware Loops", false, false) 280b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 281b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 28271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Returns true if the instruction is a hardware loop instruction. 283b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumstatic bool isHardwareLoop(const MachineInstr *MI) { 284ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return MI->getOpcode() == Hexagon::J2_loop0r || 285ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines MI->getOpcode() == Hexagon::J2_loop0i; 286b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 287b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 288b4b54153ad760c69a00a08531abef4ed434a5092Tony LinthicumFunctionPass *llvm::createHexagonHardwareLoops() { 289b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return new HexagonHardwareLoops(); 290b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 291b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 292b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 293b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumbool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) { 294b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n"); 295b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 296b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool Changed = false; 297b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 298b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MLI = &getAnalysis<MachineLoopInfo>(); 299b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MRI = &MF.getRegInfo(); 30071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MDT = &getAnalysis<MachineDominatorTree>(); 301ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo(); 302b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 303b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); 304b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum I != E; ++I) { 305b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineLoop *L = *I; 30671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!L->getParentLoop()) 307b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum Changed |= convertToHardwareLoop(L); 308b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 309b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 310b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return Changed; 311b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 312b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 31371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 31471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::findInductionRegister(MachineLoop *L, 31571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned &Reg, 31671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t &IVBump, 31771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *&IVOp 31871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek ) const { 31971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Header = L->getHeader(); 32071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Preheader = L->getLoopPreheader(); 32171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Latch = L->getLoopLatch(); 32271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Header || !Preheader || !Latch) 32371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 32471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 32571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This pair represents an induction register together with an immediate 32671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // value that will be added to it in each loop iteration. 32771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::pair<unsigned,int64_t> RegisterBump; 32871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 32971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Mapping: R.next -> (R, bump), where R, R.next and bump are derived 33071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // from an induction operation 33171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // R.next = R + bump 33271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // where bump is an immediate value. 33371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::map<unsigned,RegisterBump> InductionMap; 33471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 33571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap IndMap; 33671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 33771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineBasicBlock::instr_iterator instr_iterator; 33871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 33971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E && I->isPHI(); ++I) { 34071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *Phi = &*I; 34171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 34271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Have a PHI instruction. Get the operand that corresponds to the 34371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // latch block, and see if is a result of an addition of form "reg+imm", 34471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // where the "reg" is defined by the PHI node we are looking at. 34571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) { 34671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Phi->getOperand(i+1).getMBB() != Latch) 34771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 34871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 34971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PhiOpReg = Phi->getOperand(i).getReg(); 35071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *DI = MRI->getVRegDef(PhiOpReg); 35171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned UpdOpc = DI->getOpcode(); 352ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool isAdd = (UpdOpc == Hexagon::A2_addi); 35371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 35471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isAdd) { 35571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If the register operand to the add is the PHI we're 35671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // looking at, this meets the induction pattern. 35771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IndReg = DI->getOperand(1).getReg(); 35871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MRI->getVRegDef(IndReg) == Phi) { 35971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned UpdReg = DI->getOperand(0).getReg(); 36071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t V = DI->getOperand(2).getImm(); 36171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V))); 36271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 36371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 36471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } // for (i) 36571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } // for (instr) 36671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 36771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,2> Cond; 368dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TB = nullptr, *FB = nullptr; 36971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); 37071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (NotAnalyzed) 37171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 37271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 37371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CSz = Cond.size(); 37471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (CSz == 1 || CSz == 2); 37571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PredR = Cond[CSz-1].getReg(); 37671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 37771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *PredI = MRI->getVRegDef(PredR); 37871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!PredI->isCompare()) 37971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 38071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 38171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CmpReg1 = 0, CmpReg2 = 0; 38271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int CmpImm = 0, CmpMask = 0; 38371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool CmpAnalyzed = TII->analyzeCompare(PredI, CmpReg1, CmpReg2, 38471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpMask, CmpImm); 38571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Fail if the compare was not analyzed, or it's not comparing a register 38671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // with an immediate value. Not checking the mask here, since we handle 38771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the individual compare opcodes (including CMPb) later on. 38871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!CmpAnalyzed) 38971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 39071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 39171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Exactly one of the input registers to the comparison should be among 39271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the induction registers. 39371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap::iterator IndMapEnd = IndMap.end(); 39471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap::iterator F = IndMapEnd; 39571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpReg1 != 0) { 39671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap::iterator F1 = IndMap.find(CmpReg1); 39771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (F1 != IndMapEnd) 39871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek F = F1; 39971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 40071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpReg2 != 0) { 40171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap::iterator F2 = IndMap.find(CmpReg2); 40271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (F2 != IndMapEnd) { 40371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (F != IndMapEnd) 40471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 40571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek F = F2; 40671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 40771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 40871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (F == IndMapEnd) 40971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 41071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 41171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Reg = F->second.first; 41271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IVBump = F->second.second; 41371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IVOp = MRI->getVRegDef(F->first); 41471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 41571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 41671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 41771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 41871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Analyze the statements in a loop to determine if the loop has 41971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// a computable trip count and, if so, return a value that represents 42071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// the trip count expression. 421b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum/// 42271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// This function iterates over the phi nodes in the loop to check for 42371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// induction variable patterns that are used in the calculation for 42471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// the number of time the loop is executed. 42571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekCountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L, 426a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &OldInsts) { 427b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *TopMBB = L->getTopBlock(); 428b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(); 429b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum assert(PI != TopMBB->pred_end() && 430b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum "Loop must have more than one incoming edge!"); 431b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *Backedge = *PI++; 43271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PI == TopMBB->pred_end()) // dead loop? 433dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 434b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *Incoming = *PI++; 43571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PI != TopMBB->pred_end()) // multiple backedges? 436dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 437b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 43871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Make sure there is one incoming and one backedge and determine which 439b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // is which. 440b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (L->contains(Incoming)) { 441b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (L->contains(Backedge)) 442dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 443b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum std::swap(Incoming, Backedge); 444b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else if (!L->contains(Backedge)) 445dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 446b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 44771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Look for the cmp instruction to determine if we can get a useful trip 44871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // count. The trip count can be either a register or an immediate. The 44971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // location of the value depends upon the type (reg or imm). 45071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Latch = L->getLoopLatch(); 45171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Latch) 452dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 45371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 45471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IVReg = 0; 45571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t IVBump = 0; 45671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *IVOp; 45771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp); 45871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!FoundIV) 459dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 46071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 46171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Preheader = L->getLoopPreheader(); 46271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 463dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineOperand *InitialValue = nullptr; 46471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *IV_Phi = MRI->getVRegDef(IVReg); 46571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) { 46671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB(); 46771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MBB == Preheader) 46871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InitialValue = &IV_Phi->getOperand(i); 46971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else if (MBB == Latch) 47071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump. 47171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 47271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!InitialValue) 473dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 47471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 47571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,2> Cond; 476dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TB = nullptr, *FB = nullptr; 47771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); 47871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (NotAnalyzed) 479dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 48071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 48171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Header = L->getHeader(); 48271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // TB must be non-null. If FB is also non-null, one of them must be 48371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the header. Otherwise, branch to TB could be exiting the loop, and 48471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the fall through can go to the header. 48571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (TB && "Latch block without a branch?"); 48671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert ((!FB || TB == Header || FB == Header) && "Branches not to header?"); 48771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!TB || (FB && TB != Header && FB != Header)) 488dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 48971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 49071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch 49171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // to put imm(0), followed by P in the vector Cond. 49271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If TB is not the header, it means that the "not-taken" path must lead 49371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // to the header. 49471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool Negated = (Cond.size() > 1) ^ (TB != Header); 49571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PredReg = Cond[Cond.size()-1].getReg(); 49671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *CondI = MRI->getVRegDef(PredReg); 49771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CondOpc = CondI->getOpcode(); 49871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 49971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CmpReg1 = 0, CmpReg2 = 0; 50071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int Mask = 0, ImmValue = 0; 50171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool AnalyzedCmp = TII->analyzeCompare(CondI, CmpReg1, CmpReg2, 50271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Mask, ImmValue); 50371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!AnalyzedCmp) 504dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 50571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 50671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The comparison operator type determines how we compute the loop 50771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // trip count. 50871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek OldInsts.push_back(CondI); 50971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek OldInsts.push_back(IVOp); 51071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 51171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Sadly, the following code gets information based on the position 51271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // of the operands in the compare instruction. This has to be done 51371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // this way, because the comparisons check for a specific relationship 51471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // between the operands (e.g. is-less-than), rather than to find out 51571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // what relationship the operands are in (as on PPC). 51671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Comparison::Kind Cmp; 51771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool isSwapped = false; 51871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &Op1 = CondI->getOperand(1); 51971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &Op2 = CondI->getOperand(2); 520dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const MachineOperand *EndValue = nullptr; 52171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 52271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Op1.isReg()) { 52371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Op2.isImm() || Op1.getReg() == IVReg) 52471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndValue = &Op2; 52571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else { 52671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndValue = &Op1; 52771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek isSwapped = true; 528b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 529b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 530b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 53171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!EndValue) 532dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 53371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 53471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek switch (CondOpc) { 535ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::C2_cmpeqi: 536ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::C2_cmpeq: 53771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Cmp = !Negated ? Comparison::EQ : Comparison::NE; 53871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek break; 539ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::C2_cmpgtui: 540ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::C2_cmpgtu: 54171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Cmp = !Negated ? Comparison::GTu : Comparison::LEu; 54271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek break; 543ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::C2_cmpgti: 544ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::C2_cmpgt: 54571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Cmp = !Negated ? Comparison::GTs : Comparison::LEs; 54671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek break; 54771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Very limited support for byte/halfword compares. 548ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::A4_cmpbeqi: 549ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::A4_cmpheqi: { 55071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (IVBump != 1) 551dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 55271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 55371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t InitV, EndV; 55471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Since the comparisons are "ri", the EndValue should be an 55571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // immediate. Check it just in case. 55671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(EndValue->isImm() && "Unrecognized latch comparison"); 55771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndV = EndValue->getImm(); 55871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Allow InitialValue to be a register defined with an immediate. 55971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (InitialValue->isReg()) { 56071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!defWithImmediate(InitialValue->getReg())) 561dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 56271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InitV = getImmediate(*InitialValue); 563b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else { 56471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(InitialValue->isImm()); 56571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InitV = InitialValue->getImm(); 56671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 56771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (InitV >= EndV) 568dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 569ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (CondOpc == Hexagon::A4_cmpbeqi) { 57071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!isInt<8>(InitV) || !isInt<8>(EndV)) 571dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 57271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { // Hexagon::CMPhEQri_V4 57371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!isInt<16>(InitV) || !isInt<16>(EndV)) 574dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 575b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 57671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Cmp = !Negated ? Comparison::EQ : Comparison::NE; 57771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek break; 578b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 57971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek default: 580dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 581b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 58271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 58371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isSwapped) 58471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Cmp = Comparison::getSwappedComparison(Cmp); 58571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 58671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (InitialValue->isReg()) { 58771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = InitialValue->getReg(); 58871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent(); 58971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MDT->properlyDominates(DefBB, Header)) 590dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 59171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek OldInsts.push_back(MRI->getVRegDef(R)); 59271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 59371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (EndValue->isReg()) { 59471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = EndValue->getReg(); 59571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent(); 59671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MDT->properlyDominates(DefBB, Header)) 597dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 59871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 59971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 60071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp); 601b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 602b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 60371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Helper function that returns the expression that represents the 60471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// number of times a loop iterates. The function takes the operands that 60571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// represent the loop start value, loop end value, and induction value. 60671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// Based upon these operands, the function attempts to compute the trip count. 60771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekCountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop, 60871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand *Start, 60971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand *End, 61071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IVReg, 61171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t IVBump, 61271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Comparison::Kind Cmp) const { 61371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Cannot handle comparison EQ, i.e. while (A == B). 61471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Cmp == Comparison::EQ) 615dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 61671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 61771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Check if either the start or end values are an assignment of an immediate. 61871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If so, use the immediate value rather than the register. 61971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isReg()) { 62071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg()); 621ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (StartValInstr && StartValInstr->getOpcode() == Hexagon::A2_tfrsi) 62271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Start = &StartValInstr->getOperand(1); 62371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 62471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (End->isReg()) { 62571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg()); 626ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (EndValInstr && EndValInstr->getOpcode() == Hexagon::A2_tfrsi) 62771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek End = &EndValInstr->getOperand(1); 62871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 62971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 63071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (Start->isReg() || Start->isImm()); 63171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (End->isReg() || End->isImm()); 63271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 63371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool CmpLess = Cmp & Comparison::L; 63471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool CmpGreater = Cmp & Comparison::G; 63571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool CmpHasEqual = Cmp & Comparison::EQ; 63671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 63771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds. 63871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If loop executes while iv is "less" with the iv value going down, then 63971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the iv must wrap. 64071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpLess && IVBump < 0) 641dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 64271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If loop executes while iv is "greater" with the iv value going up, then 64371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the iv must wrap. 64471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpGreater && IVBump > 0) 645dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 64671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 64771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm() && End->isImm()) { 64871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Both, start and end are immediates. 64971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t StartV = Start->getImm(); 65071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t EndV = End->getImm(); 65171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t Dist = EndV - StartV; 65271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Dist == 0) 653dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 65471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 65571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool Exact = (Dist % IVBump) == 0; 65671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 65771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Cmp == Comparison::NE) { 65871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Exact) 659dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 66071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if ((Dist < 0) ^ (IVBump < 0)) 661dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 66271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 66371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 66471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // For comparisons that include the final value (i.e. include equality 66571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // with the final value), we need to increase the distance by 1. 66671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpHasEqual) 66771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Dist = Dist > 0 ? Dist+1 : Dist-1; 66871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 66971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // assert (CmpLess => Dist > 0); 67071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert ((!CmpLess || Dist > 0) && "Loop should never iterate!"); 67171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // assert (CmpGreater => Dist < 0); 67271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert ((!CmpGreater || Dist < 0) && "Loop should never iterate!"); 67371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 67471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // "Normalized" distance, i.e. with the bump set to +-1. 67571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump-1)) / IVBump 67671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek : (-Dist + (-IVBump-1)) / (-IVBump); 67771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign."); 67871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 67971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek uint64_t Count = Dist1; 68071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 68171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Count > 0xFFFFFFFFULL) 682dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 68371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 68471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return new CountValue(CountValue::CV_Immediate, Count); 68571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 68671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 68771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // A general case: Start and End are some values, but the actual 68871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // iteration count may not be available. If it is not, insert 68971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // a computation of it into the preheader. 69071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 69171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If the induction variable bump is not a power of 2, quit. 69271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Othwerise we'd need a general integer division. 6934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!isPowerOf2_64(std::abs(IVBump))) 694dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 69571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 69671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PH = Loop->getLoopPreheader(); 69771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (PH && "Should have a preheader by now"); 69871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator(); 69971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DebugLoc DL = (InsertPos != PH->end()) ? InsertPos->getDebugLoc() 70071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek : DebugLoc(); 70171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 70271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If Start is an immediate and End is a register, the trip count 70371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // will be "reg - imm". Hexagon's "subtract immediate" instruction 70471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // is actually "reg + -imm". 70571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 70671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If the loop IV is going downwards, i.e. if the bump is negative, 70771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // then the iteration count (computed as End-Start) will need to be 70871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // negated. To avoid the negation, just swap Start and End. 70971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (IVBump < 0) { 71071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek std::swap(Start, End); 71171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IVBump = -IVBump; 71271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 71371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Cmp may now have a wrong direction, e.g. LEs may now be GEs. 71471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Signedness, and "including equality" are preserved. 71571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 71671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm) 71771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg) 71871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 71971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t StartV = 0, EndV = 0; 72071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm()) 72171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek StartV = Start->getImm(); 72271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (End->isImm()) 72371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndV = End->getImm(); 72471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 72571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t AdjV = 0; 72671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // To compute the iteration count, we would need this computation: 72771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Count = (End - Start + (IVBump-1)) / IVBump 72871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // or, when CmpHasEqual: 72971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Count = (End - Start + (IVBump-1)+1) / IVBump 73071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The "IVBump-1" part is the adjustment (AdjV). We can avoid 73171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // generating an instruction specifically to add it if we can adjust 73271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the immediate values for Start or End. 73371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 73471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpHasEqual) { 73571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Need to add 1 to the total iteration count. 73671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm()) 73771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek StartV--; 73871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else if (End->isImm()) 73971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndV++; 74071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else 74171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjV += 1; 74271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 74371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 74471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Cmp != Comparison::NE) { 74571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm()) 74671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek StartV -= (IVBump-1); 74771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else if (End->isImm()) 74871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndV += (IVBump-1); 74971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else 75071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjV += (IVBump-1); 75171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 75271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 75371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = 0, SR = 0; 75471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isReg()) { 75571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek R = Start->getReg(); 75671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SR = Start->getSubReg(); 75771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 75871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek R = End->getReg(); 75971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SR = End->getSubReg(); 76071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 76171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const TargetRegisterClass *RC = MRI->getRegClass(R); 76271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Hardware loops cannot handle 64-bit registers. If it's a double 76371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // register, it has to have a subregister. 76471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!SR && RC == &Hexagon::DoubleRegsRegClass) 765dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 76671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass; 76771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 76871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Compute DistR (register with the distance between Start and End). 76971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned DistR, DistSR; 77071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 77171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Avoid special case, where the start value is an imm(0). 77271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm() && StartV == 0) { 77371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DistR = End->getReg(); 77471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DistSR = End->getSubReg(); 77571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 776ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) : 777ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines (RegToImm ? TII->get(Hexagon::A2_subri) : 778ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TII->get(Hexagon::A2_addi)); 77971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned SubR = MRI->createVirtualRegister(IntRC); 78071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstrBuilder SubIB = 78171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek BuildMI(*PH, InsertPos, DL, SubD, SubR); 78271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 78371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (RegToReg) { 78471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SubIB.addReg(End->getReg(), 0, End->getSubReg()) 78571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(Start->getReg(), 0, Start->getSubReg()); 78671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else if (RegToImm) { 78771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SubIB.addImm(EndV) 78871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(Start->getReg(), 0, Start->getSubReg()); 78971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { // ImmToReg 79071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SubIB.addReg(End->getReg(), 0, End->getSubReg()) 79171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addImm(-StartV); 79271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 79371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DistR = SubR; 79471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DistSR = 0; 79571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 79671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 79771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // From DistR, compute AdjR (register with the adjusted distance). 79871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned AdjR, AdjSR; 79971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 80071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (AdjV == 0) { 80171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjR = DistR; 80271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjSR = DistSR; 80371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 80471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Generate CountR = ADD DistR, AdjVal 80571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned AddR = MRI->createVirtualRegister(IntRC); 806ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi); 80771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek BuildMI(*PH, InsertPos, DL, AddD, AddR) 80871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(DistR, 0, DistSR) 80971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addImm(AdjV); 81071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 81171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjR = AddR; 81271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjSR = 0; 81371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 81471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 81571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // From AdjR, compute CountR (register with the final count). 81671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CountR, CountSR; 81771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 81871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (IVBump == 1) { 81971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountR = AdjR; 82071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountSR = AdjSR; 82171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 82271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The IV bump is a power of two. Log_2(IV bump) is the shift amount. 82371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Shift = Log2_32(IVBump); 82471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 82571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Generate NormR = LSR DistR, Shift. 82671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned LsrR = MRI->createVirtualRegister(IntRC); 827ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r); 82871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek BuildMI(*PH, InsertPos, DL, LsrD, LsrR) 82971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(AdjR, 0, AdjSR) 83071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addImm(Shift); 83171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 83271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountR = LsrR; 83371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountSR = 0; 83471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 83571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 83671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return new CountValue(CountValue::CV_Register, CountR, CountSR); 837b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 838b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 83971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 84071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Return true if the operation is invalid within hardware loop. 84171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::isInvalidLoopOperation( 84271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineInstr *MI) const { 843b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 844b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // call is not allowed because the callee may use a hardware loop 84571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MI->getDesc().isCall()) 846b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 84771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 848b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // do not allow nested hardware loops 84971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isHardwareLoop(MI)) 850b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 85171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 852b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // check if the instruction defines a hardware loop register 853b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 854b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum const MachineOperand &MO = MI->getOperand(i); 85571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MO.isReg() || !MO.isDef()) 85671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 85771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = MO.getReg(); 85871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (R == Hexagon::LC0 || R == Hexagon::LC1 || 85971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek R == Hexagon::SA0 || R == Hexagon::SA1) 860b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 861b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 862b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 863b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 864b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 86571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 86671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief - Return true if the loop contains an instruction that inhibits 86771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// the use of the hardware loop function. 868b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumbool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L) const { 86994ee55d4b39d6506cf4e0f4e4b1c0b7fbbfeaed5Benjamin Kramer const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks(); 870b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 871b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *MBB = Blocks[i]; 872b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum for (MachineBasicBlock::iterator 873b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) { 874b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum const MachineInstr *MI = &*MII; 87571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isInvalidLoopOperation(MI)) 876b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 877b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 878b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 879b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 880b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 881b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 88271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 88371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Returns true if the instruction is dead. This was essentially 88471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// copied from DeadMachineInstructionElim::isDead, but with special cases 88571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// for inline asm, physical registers and instructions with side effects 88671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// removed. 88771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::isDead(const MachineInstr *MI, 888a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &DeadPhis) const { 88971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Examine each operand. 89071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 89171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &MO = MI->getOperand(i); 89271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MO.isReg() || !MO.isDef()) 89371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 89471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 89571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Reg = MO.getReg(); 89671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MRI->use_nodbg_empty(Reg)) 89771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 89871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 89971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator; 90071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 90171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This instruction has users, but if the only user is the phi node for the 90271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // parent block, and the only use of that phi node is this instruction, then 90371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // this instruction is dead: both it (and the phi node) can be removed. 90471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek use_nodbg_iterator I = MRI->use_nodbg_begin(Reg); 90571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek use_nodbg_iterator End = MRI->use_nodbg_end(); 90636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (std::next(I) != End || !I->getParent()->isPHI()) 90771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 90871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 90936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineInstr *OnePhi = I->getParent(); 91071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) { 91171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &OPO = OnePhi->getOperand(j); 91271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!OPO.isReg() || !OPO.isDef()) 91371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 91471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 91571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned OPReg = OPO.getReg(); 91671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek use_nodbg_iterator nextJ; 91771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg); 91871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek J != End; J = nextJ) { 91936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines nextJ = std::next(J); 92036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineOperand &Use = *J; 92171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *UseMI = Use.getParent(); 92271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 92371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If the phi node has a user that is not MI, bail... 92471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MI != UseMI) 92571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 92671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 92771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 92871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DeadPhis.push_back(OnePhi); 92971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 93071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 93171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If there are no defs with uses, the instruction is dead. 93271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 93371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 93471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 93571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekvoid HexagonHardwareLoops::removeIfDead(MachineInstr *MI) { 93671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This procedure was essentially copied from DeadMachineInstructionElim. 93771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 93871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineInstr*, 1> DeadPhis; 93971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isDead(MI, DeadPhis)) { 94071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DEBUG(dbgs() << "HW looping will remove: " << *MI); 94171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 94271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // It is possible that some DBG_VALUE instructions refer to this 94371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // instruction. Examine each def operand for such references; 94471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // if found, mark the DBG_VALUE as undef (but don't delete it). 94571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 94671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &MO = MI->getOperand(i); 94771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MO.isReg() || !MO.isDef()) 94871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 94971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Reg = MO.getReg(); 95071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineRegisterInfo::use_iterator nextI; 95171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg), 95271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek E = MRI->use_end(); I != E; I = nextI) { 95336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines nextI = std::next(I); // I is invalidated by the setReg 95436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineOperand &Use = *I; 95536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineInstr *UseMI = I->getParent(); 95671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (UseMI == MI) 95771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 95871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Use.isDebug()) 95971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek UseMI->getOperand(0).setReg(0U); 96071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This may also be a "instr -> phi -> instr" case which can 96171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // be removed too. 96271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 96371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 96471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 96571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MI->eraseFromParent(); 96671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0; i < DeadPhis.size(); ++i) 96771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DeadPhis[i]->eraseFromParent(); 96871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 96971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 97071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 97171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Check if the loop is a candidate for converting to a hardware 97271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// loop. If so, then perform the transformation. 973b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum/// 97471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// This function works on innermost loops first. A loop can be converted 97571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// if it is a counting loop; either a register value or an immediate. 976b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum/// 97771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// The code makes several assumptions about the representation of the loop 97871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// in llvm. 979b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumbool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L) { 98071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This is just for sanity. 98171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(L->getHeader() && "Loop without a header?"); 98271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 983b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool Changed = false; 984b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Process nested loops first. 98571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 986b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum Changed |= convertToHardwareLoop(*I); 98771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 988b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // If a nested loop has been converted, then we can't convert this loop. 98971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Changed) 990b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return Changed; 99171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 99271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#ifndef NDEBUG 99371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Stop trying after reaching the limit (if any). 99471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int Limit = HWLoopLimit; 99571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Limit >= 0) { 99671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Counter >= HWLoopLimit) 99771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 99871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Counter++; 999b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 100071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#endif 100171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1002b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Does the loop contain any invalid instructions? 100371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (containsInvalidInstruction(L)) 1004b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 100571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 100671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Is the induction variable bump feeding the latch condition? 100771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!fixupInductionVariable(L)) 1008b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 1009b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1010b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *LastMBB = L->getExitingBlock(); 1011b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Don't generate hw loop if the loop has more than one exit. 1012dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!LastMBB) 1013b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 101471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1015b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); 101671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (LastI == LastMBB->end()) 1017ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis return false; 101871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 101971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Ensure the loop has a preheader: the loop instruction will be 102071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // placed there. 102171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool NewPreheader = false; 102271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Preheader = L->getLoopPreheader(); 102371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Preheader) { 102471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Preheader = createPreheaderForLoop(L); 102571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Preheader) 102671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 102771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPreheader = true; 102871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 102971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator(); 103071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 103171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineInstr*, 2> OldInsts; 103271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Are we able to determine the trip count for the loop? 103371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountValue *TripCount = getLoopTripCount(L, OldInsts); 1034dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!TripCount) 103571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 103671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 103771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Is the trip count available in the preheader? 103871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (TripCount->isReg()) { 103971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // There will be a use of the register inserted into the preheader, 104071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // so make sure that the register is actually defined at that point. 104171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg()); 104271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *BBDef = TCDef->getParent(); 104371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!NewPreheader) { 104471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MDT->dominates(BBDef, Preheader)) 104571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 104671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 104771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If we have just created a preheader, the dominator tree won't be 104871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // aware of it. Check if the definition of the register dominates 104971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the header, but is not the header itself. 105071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MDT->properlyDominates(BBDef, L->getHeader())) 105171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 105271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 1053ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis } 1054b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1055b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Determine the loop start. 1056b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *LoopStart = L->getTopBlock(); 1057b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (L->getLoopLatch() != LastMBB) { 1058b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // When the exit and latch are not the same, use the latch block as the 1059b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // start. 106071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The loop start address is used only after the 1st iteration, and the 106171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // loop latch may contains instrs. that need to be executed after the 106271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // first iteration. 1063b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum LoopStart = L->getLoopLatch(); 1064b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Make sure the latch is a successor of the exit, otherwise it won't work. 106571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!LastMBB->isSuccessor(LoopStart)) 1066b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 1067b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1068b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 106971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Convert the loop to a hardware loop. 1070b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum DEBUG(dbgs() << "Change to hardware loop at "; L->dump()); 107171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DebugLoc DL; 1072ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis if (InsertPos != Preheader->end()) 107371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DL = InsertPos->getDebugLoc(); 1074b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1075b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (TripCount->isReg()) { 1076b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Create a copy of the loop count register. 107771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); 107871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg) 107971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(TripCount->getReg(), 0, TripCount->getSubReg()); 1080d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // Add the Loop instruction to the beginning of the loop. 1081ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0r)) 108271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addMBB(LoopStart) 108371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(CountReg); 1084b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else { 108571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(TripCount->isImm() && "Expecting immediate value for trip count"); 108671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Add the Loop immediate instruction to the beginning of the loop, 108771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // if the immediate fits in the instructions. Otherwise, we need to 108871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // create a new virtual register. 1089b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum int64_t CountImm = TripCount->getImm(); 1090ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!TII->isValidOffset(Hexagon::J2_loop0i, CountImm)) { 109171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); 1092ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg) 109371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addImm(CountImm); 1094ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0r)) 109571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addMBB(LoopStart).addReg(CountReg); 109671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else 1097ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::J2_loop0i)) 109871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addMBB(LoopStart).addImm(CountImm); 1099b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1100b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 110171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Make sure the loop start always has a reference in the CFG. We need 110271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // to create a BlockAddress operand to get this mechanism to work both the 1103b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // MachineBasicBlock and BasicBlock objects need the flag set. 1104b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum LoopStart->setHasAddressTaken(); 1105b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // This line is needed to set the hasAddressTaken flag on the BasicBlock 110671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // object. 1107b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock())); 1108b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1109b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Replace the loop branch with an endloop instruction. 1110ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis DebugLoc LastIDL = LastI->getDebugLoc(); 1111ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis BuildMI(*LastMBB, LastI, LastIDL, 1112ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis TII->get(Hexagon::ENDLOOP0)).addMBB(LoopStart); 1113b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1114b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // The loop ends with either: 1115b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // - a conditional branch followed by an unconditional branch, or 1116b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // - a conditional branch to the loop start. 1117ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (LastI->getOpcode() == Hexagon::J2_jumpt || 1118ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LastI->getOpcode() == Hexagon::J2_jumpf) { 111971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Delete one and change/add an uncond. branch to out of the loop. 1120b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB(); 1121b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum LastI = LastMBB->erase(LastI); 1122b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (!L->contains(BranchTarget)) { 112371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (LastI != LastMBB->end()) 112471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LastI = LastMBB->erase(LastI); 1125b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum SmallVector<MachineOperand, 0> Cond; 1126dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TII->InsertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL); 1127b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1128b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else { 1129b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Conditional branch to loop start; just delete it. 1130b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum LastMBB->erase(LastI); 1131b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1132b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum delete TripCount; 1133b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 113471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The induction operation and the comparison may now be 113571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // unneeded. If these are unneeded, then remove them. 113671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0; i < OldInsts.size(); ++i) 113771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek removeIfDead(OldInsts[i]); 113871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1139b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum ++NumHWLoops; 1140b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 1141b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1142b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 114371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 114471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI, 114571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *CmpI) { 114671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (BumpI != CmpI && "Bump and compare in the same instruction?"); 114771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 114871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *BB = BumpI->getParent(); 114971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpI->getParent() != BB) 115071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 115171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 115271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineBasicBlock::instr_iterator instr_iterator; 115371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Check if things are in order to begin with. 115471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = BumpI, E = BB->instr_end(); I != E; ++I) 115571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (&*I == CmpI) 115671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 115771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 115871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Out of order. 115971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PredR = CmpI->getOperand(0).getReg(); 116071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool FoundBump = false; 116136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines instr_iterator CmpIt = CmpI, NextIt = std::next(CmpIt); 116271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) { 116371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *In = &*I; 116471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) { 116571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineOperand &MO = In->getOperand(i); 116671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isReg() && MO.isUse()) { 116771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.getReg() == PredR) // Found an intervening use of PredR. 116871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 116971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 117071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 117171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 117271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (In == BumpI) { 117371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek instr_iterator After = BumpI; 117471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek instr_iterator From = CmpI; 117536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BB->splice(std::next(After), BB, From); 117671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek FoundBump = true; 117771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek break; 117871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 117971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 118071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (FoundBump && "Cannot determine instruction order"); 118171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return FoundBump; 1182b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1183b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1184b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 118571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekMachineInstr *HexagonHardwareLoops::defWithImmediate(unsigned R) { 118671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *DI = MRI->getVRegDef(R); 118771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned DOpc = DI->getOpcode(); 118871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek switch (DOpc) { 1189ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::A2_tfrsi: 1190ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::A2_tfrpi: 119171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek case Hexagon::CONST32_Int_Real: 119271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek case Hexagon::CONST64_Int_Real: 119371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return DI; 119471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 1195dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1196b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1197b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 119871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 119971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekint64_t HexagonHardwareLoops::getImmediate(MachineOperand &MO) { 120071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isImm()) 120171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return MO.getImm(); 120271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(MO.isReg()); 120371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = MO.getReg(); 120471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *DI = defWithImmediate(R); 120571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(DI && "Need an immediate operand"); 120671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // All currently supported "define-with-immediate" instructions have the 120771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // actual immediate value in the operand(1). 120871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t v = DI->getOperand(1).getImm(); 120971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return v; 121071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 121171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 121271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 121371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekvoid HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) { 121471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isImm()) { 121571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MO.setImm(Val); 121671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return; 121771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 121871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 121971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(MO.isReg()); 122071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = MO.getReg(); 122171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *DI = defWithImmediate(R); 122271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MRI->hasOneNonDBGUse(R)) { 122371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If R has only one use, then just change its defining instruction to 122471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the new immediate value. 122571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DI->getOperand(1).setImm(Val); 122671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return; 122771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 122871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 122971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const TargetRegisterClass *RC = MRI->getRegClass(R); 123071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned NewR = MRI->createVirtualRegister(RC); 123171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock &B = *DI->getParent(); 123271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DebugLoc DL = DI->getDebugLoc(); 123371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR) 123471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addImm(Val); 123571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MO.setReg(NewR); 123671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 123771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 123871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 123971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) { 124071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Header = L->getHeader(); 124171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Preheader = L->getLoopPreheader(); 124271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Latch = L->getLoopLatch(); 124371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 124471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Header || !Preheader || !Latch) 124571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 124671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 124771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // These data structures follow the same concept as the corresponding 124871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // ones in findInductionRegister (where some comments are). 124971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::pair<unsigned,int64_t> RegisterBump; 125071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::pair<unsigned,RegisterBump> RegisterInduction; 125171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::set<RegisterInduction> RegisterInductionSet; 125271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 125371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Register candidates for induction variables, with their associated bumps. 125471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek RegisterInductionSet IndRegs; 125571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 125671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Look for induction patterns: 125771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // vreg1 = PHI ..., [ latch, vreg2 ] 125871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // vreg2 = ADD vreg1, imm 125971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineBasicBlock::instr_iterator instr_iterator; 126071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 126171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E && I->isPHI(); ++I) { 126271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *Phi = &*I; 126371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 126471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Have a PHI instruction. 126571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) { 126671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Phi->getOperand(i+1).getMBB() != Latch) 126771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 126871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 126971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PhiReg = Phi->getOperand(i).getReg(); 127071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *DI = MRI->getVRegDef(PhiReg); 127171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned UpdOpc = DI->getOpcode(); 1272ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool isAdd = (UpdOpc == Hexagon::A2_addi); 127371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 127471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isAdd) { 127571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If the register operand to the add/sub is the PHI we are looking 127671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // at, this meets the induction pattern. 127771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IndReg = DI->getOperand(1).getReg(); 127871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MRI->getVRegDef(IndReg) == Phi) { 127971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned UpdReg = DI->getOperand(0).getReg(); 128071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t V = DI->getOperand(2).getImm(); 128171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V))); 1282b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1283b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 128471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } // for (i) 128571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } // for (instr) 128671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 128771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (IndRegs.empty()) 128871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 128971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1290dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TB = nullptr, *FB = nullptr; 129171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,2> Cond; 129271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // AnalyzeBranch returns true if it fails to analyze branch. 129371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool NotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Cond, false); 129471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (NotAnalyzed) 129571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 129671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 129771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Check if the latch branch is unconditional. 129871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Cond.empty()) 129971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 130071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 130171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (TB != Header && FB != Header) 130271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The latch does not go back to the header. Not a latch we know and love. 130371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 130471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 130571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Expecting a predicate register as a condition. It won't be a hardware 130671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // predicate register at this point yet, just a vreg. 130771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0) 130871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // into Cond, followed by the predicate register. For non-negated branches 130971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // it's just the register. 131071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CSz = Cond.size(); 131171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CSz != 1 && CSz != 2) 131271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 131371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 131471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned P = Cond[CSz-1].getReg(); 131571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *PredDef = MRI->getVRegDef(P); 131671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 131771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!PredDef->isCompare()) 131871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 131971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 132071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallSet<unsigned,2> CmpRegs; 1321dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineOperand *CmpImmOp = nullptr; 132271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 132371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Go over all operands to the compare and look for immediate and register 132471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // operands. Assume that if the compare has a single register use and a 132571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // single immediate operand, then the register is being compared with the 132671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // immediate value. 132771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) { 132871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineOperand &MO = PredDef->getOperand(i); 132971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isReg()) { 133071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Skip all implicit references. In one case there was: 133171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use> 133271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isImplicit()) 133371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 133471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isUse()) { 133571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = MO.getReg(); 133671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!defWithImmediate(R)) { 133771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpRegs.insert(MO.getReg()); 133871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 133971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 134071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Consider the register to be the "immediate" operand. 134171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpImmOp) 134271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 134371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpImmOp = &MO; 134471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 134571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else if (MO.isImm()) { 134671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpImmOp) // A second immediate argument? Confusing. Bail out. 134771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 134871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpImmOp = &MO; 1349b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1350b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1351b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 135271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpRegs.empty()) 135371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 135471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 135571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Check if the compared register follows the order we want. Fix if needed. 135671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end(); 135771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E; ++I) { 135871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This is a success. If the register used in the comparison is one that 135971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // we have identified as a bumped (updated) induction register, there is 136071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // nothing to do. 136171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpRegs.count(I->first)) 136271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 136371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 136471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Otherwise, if the register being compared comes out of a PHI node, 136571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // and has been recognized as following the induction pattern, and is 136671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // compared against an immediate, we can fix it. 136771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const RegisterBump &RB = I->second; 136871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpRegs.count(RB.first)) { 136971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!CmpImmOp) 137071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 137171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 137271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t CmpImm = getImmediate(*CmpImmOp); 137371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t V = RB.second; 137471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (V > 0 && CmpImm+V < CmpImm) // Overflow (64-bit). 137571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 137671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (V < 0 && CmpImm+V > CmpImm) // Overflow (64-bit). 137771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 137871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpImm += V; 137971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Some forms of cmp-immediate allow u9 and s10. Assume the worst case 138071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // scenario, i.e. an 8-bit value. 138171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpImmOp->isImm() && !isInt<8>(CmpImm)) 138271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 138371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 138471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Make sure that the compare happens after the bump. Otherwise, 138571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // after the fixup, the compare would use a yet-undefined register. 138671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *BumpI = MRI->getVRegDef(I->first); 138771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool Order = orderBumpCompare(BumpI, PredDef); 138871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Order) 138971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 139071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 139171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Finally, fix the compare instruction. 139271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek setImmediate(*CmpImmOp, CmpImm); 139371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) { 139471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineOperand &MO = PredDef->getOperand(i); 139571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isReg() && MO.getReg() == RB.first) { 139671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MO.setReg(I->first); 139771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 139871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 139971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 140071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 140171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 1402b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 140371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 1404b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1405b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 140671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 140771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Create a preheader for a given loop. 140871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekMachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop( 140971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineLoop *L) { 141071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MachineBasicBlock *TmpPH = L->getLoopPreheader()) 141171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return TmpPH; 141271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 141371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Header = L->getHeader(); 141471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Latch = L->getLoopLatch(); 141571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineFunction *MF = Header->getParent(); 141671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DebugLoc DL; 141771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 141871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Latch || Header->hasAddressTaken()) 1419dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 142071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 142171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineBasicBlock::instr_iterator instr_iterator; 142271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 142371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Verify that all existing predecessors have analyzable branches 142471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // (or no branches at all). 142571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::vector<MachineBasicBlock*> MBBVector; 142671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MBBVector Preds(Header->pred_begin(), Header->pred_end()); 142771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,2> Tmp1; 1428dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TB = nullptr, *FB = nullptr; 142971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 143071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (TII->AnalyzeBranch(*Latch, TB, FB, Tmp1, false)) 1431dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 143271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 143371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) { 143471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PB = *I; 143571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PB != Latch) { 143671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp1, false); 143771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (NotAnalyzed) 1438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 143971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 144071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 144171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 144271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock(); 144371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MF->insert(Header, NewPH); 144471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 144571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Header->pred_size() > 2) { 144671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Ensure that the header has only two predecessors: the preheader and 144771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the loop latch. Any additional predecessors of the header should 144871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // join at the newly created preheader. Inspect all PHI nodes from the 144971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // header and create appropriate corresponding PHI nodes in the preheader. 145071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 145171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 145271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E && I->isPHI(); ++I) { 145371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *PN = &*I; 145471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 145571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MCInstrDesc &PD = TII->get(TargetOpcode::PHI); 145671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL); 145771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPH->insert(NewPH->end(), NewPN); 145871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 145971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PR = PN->getOperand(0).getReg(); 146071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const TargetRegisterClass *RC = MRI->getRegClass(PR); 146171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned NewPR = MRI->createVirtualRegister(RC); 146271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPN->addOperand(MachineOperand::CreateReg(NewPR, true)); 146371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 146471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Copy all non-latch operands of a header's PHI node to the newly 146571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // created PHI node in the preheader. 146671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) { 146771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PredR = PN->getOperand(i).getReg(); 146871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB(); 146971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PredB == Latch) 147071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 147171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 147271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPN->addOperand(MachineOperand::CreateReg(PredR, false)); 147371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPN->addOperand(MachineOperand::CreateMBB(PredB)); 147471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 147571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 147671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Remove copied operands from the old PHI node and add the value 147771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // coming from the preheader's PHI. 147871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (int i = PN->getNumOperands()-2; i > 0; i -= 2) { 147971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB(); 148071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PredB != Latch) { 148171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PN->RemoveOperand(i+1); 148271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PN->RemoveOperand(i); 148371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 148471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 148571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PN->addOperand(MachineOperand::CreateReg(NewPR, false)); 148671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PN->addOperand(MachineOperand::CreateMBB(NewPH)); 148771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 148871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1489b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else { 149071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(Header->pred_size() == 2); 149171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 149271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The header has only two predecessors, but the non-latch predecessor 149371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // is not a preheader (e.g. it has other successors, etc.) 149471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // In such a case we don't need any extra PHI nodes in the new preheader, 149571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // all we need is to adjust existing PHIs in the header to now refer to 149671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the new preheader. 149771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 149871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E && I->isPHI(); ++I) { 149971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *PN = &*I; 150071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) { 150171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineOperand &MO = PN->getOperand(i+1); 150271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.getMBB() != Latch) 150371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MO.setMBB(NewPH); 150471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 150571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 150671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 150771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 150871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // "Reroute" the CFG edges to link in the new preheader. 150971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If any of the predecessors falls through to the header, insert a branch 151071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // to the new preheader in that place. 151171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,1> Tmp2; 151271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,1> EmptyCond; 151371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1514dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TB = FB = nullptr; 151571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 151671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) { 151771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PB = *I; 151871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PB != Latch) { 151971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Tmp2.clear(); 152071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool NotAnalyzed = TII->AnalyzeBranch(*PB, TB, FB, Tmp2, false); 152136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (void)NotAnalyzed; // suppress compiler warning 152271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (!NotAnalyzed && "Should be analyzable!"); 152371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (TB != Header && (Tmp2.empty() || FB != Header)) 1524dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TII->InsertBranch(*PB, NewPH, nullptr, EmptyCond, DL); 152571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PB->ReplaceUsesOfBlockWith(Header, NewPH); 152671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 152771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 152871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 152971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // It can happen that the latch block will fall through into the header. 153071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Insert an unconditional branch to the header. 1531dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TB = FB = nullptr; 153271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool LatchNotAnalyzed = TII->AnalyzeBranch(*Latch, TB, FB, Tmp2, false); 153336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (void)LatchNotAnalyzed; // suppress compiler warning 153471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (!LatchNotAnalyzed && "Should be analyzable!"); 153571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!TB && !FB) 1536dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TII->InsertBranch(*Latch, Header, nullptr, EmptyCond, DL); 153771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 153871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Finally, the branch from the preheader to the header. 1539dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TII->InsertBranch(*NewPH, Header, nullptr, EmptyCond, DL); 154071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPH->addSuccessor(Header); 154171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 154271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return NewPH; 1543b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1544