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 function calls in loops. 25b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum// 26b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum//===----------------------------------------------------------------------===// 27b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 2871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#include "llvm/ADT/SmallSet.h" 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "Hexagon.h" 30ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "HexagonSubtarget.h" 31b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/ADT/Statistic.h" 32b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineDominators.h" 33b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineFunction.h" 34b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineFunctionPass.h" 35b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineInstrBuilder.h" 36b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineLoopInfo.h" 37b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/CodeGen/MachineRegisterInfo.h" 38d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/PassSupport.h" 3971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#include "llvm/Support/CommandLine.h" 40b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/Support/Debug.h" 41b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/Support/raw_ostream.h" 42b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include "llvm/Target/TargetInstrInfo.h" 43b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum#include <algorithm> 4471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#include <vector> 45b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 46b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumusing namespace llvm; 47b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "hwloops" 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 5071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#ifndef NDEBUG 516948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic cl::opt<int> HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1)); 526948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar// Option to create preheader only for a specific function. 546948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic cl::opt<std::string> PHFn("hexagon-hwloop-phfn", cl::Hidden, 556948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar cl::init("")); 5671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#endif 5771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar// Option to create a preheader if one doesn't exist. 596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic cl::opt<bool> HWCreatePreheader("hexagon-hwloop-preheader", 606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar cl::Hidden, cl::init(true), 616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar cl::desc("Add a preheader to a hardware loop if one doesn't exist")); 626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 63b4b54153ad760c69a00a08531abef4ed434a5092Tony LinthicumSTATISTIC(NumHWLoops, "Number of loops converted to hardware loops"); 64b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 6571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszeknamespace llvm { 666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar FunctionPass *createHexagonHardwareLoops(); 6771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek void initializeHexagonHardwareLoopsPass(PassRegistry&); 6871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 6971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 70b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumnamespace { 71b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum class CountValue; 72b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum struct HexagonHardwareLoops : public MachineFunctionPass { 7371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineLoopInfo *MLI; 7471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineRegisterInfo *MRI; 7571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineDominatorTree *MDT; 7671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const HexagonInstrInfo *TII; 7771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#ifndef NDEBUG 7871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek static int Counter; 7971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#endif 80b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 81b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum public: 8271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek static char ID; 83b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 8471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek HexagonHardwareLoops() : MachineFunctionPass(ID) { 8571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek initializeHexagonHardwareLoopsPass(*PassRegistry::getPassRegistry()); 8671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 87b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 88dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool runOnMachineFunction(MachineFunction &MF) override; 89b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 90dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *getPassName() const override { return "Hexagon Hardware Loops"; } 91b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 92dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 93b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum AU.addRequired<MachineDominatorTree>(); 94b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum AU.addRequired<MachineLoopInfo>(); 95b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineFunctionPass::getAnalysisUsage(AU); 96b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 97b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 98b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum private: 996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar typedef std::map<unsigned, MachineInstr *> LoopFeederMap; 1006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 10171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Kinds of comparisons in the compare instructions. 10271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek struct Comparison { 10371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek enum Kind { 10471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EQ = 0x01, 10571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NE = 0x02, 1066948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar L = 0x04, 1076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar G = 0x08, 1086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar U = 0x40, 10971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LTs = L, 11071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LEs = L | EQ, 11171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek GTs = G, 11271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek GEs = G | EQ, 11371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LTu = L | U, 11471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LEu = L | EQ | U, 11571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek GTu = G | U, 11671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek GEu = G | EQ | U 11771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek }; 11871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 11971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek static Kind getSwappedComparison(Kind Cmp) { 12071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert ((!((Cmp & L) && (Cmp & G))) && "Malformed comparison operator"); 12171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if ((Cmp & L) || (Cmp & G)) 12271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return (Kind)(Cmp ^ (L|G)); 12371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return Cmp; 12471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 1256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar static Kind getNegatedComparison(Kind Cmp) { 1276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if ((Cmp & L) || (Cmp & G)) 1286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return (Kind)((Cmp ^ (L | G)) ^ EQ); 1296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if ((Cmp & NE) || (Cmp & EQ)) 1306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return (Kind)(Cmp ^ (EQ | NE)); 1316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return (Kind)0; 1326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar static bool isSigned(Kind Cmp) { 1356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return (Cmp & (L | G) && !(Cmp & U)); 1366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar static bool isUnsigned(Kind Cmp) { 1396948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return (Cmp & U); 1406948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek }; 143b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 14471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Find the register that contains the loop controlling 14571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// induction variable. 14671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// If successful, it will return true and set the \p Reg, \p IVBump 14771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// and \p IVOp arguments. Otherwise it will return false. 14871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// The returned induction register is the register R that follows the 14971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// following induction pattern: 15071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// loop: 15171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// R = phi ..., [ R.next, LatchBlock ] 15271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// R.next = R + #bump 15371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// if (R.next < #N) goto loop 15471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// IVBump is the immediate value added to R, and IVOp is the instruction 15571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// "R.next = R + #bump". 15671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool findInductionRegister(MachineLoop *L, unsigned &Reg, 15771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t &IVBump, MachineInstr *&IVOp) const; 15871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// \brief Return the comparison kind for the specified opcode. 1606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Comparison::Kind getComparisonKind(unsigned CondOpc, 1616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineOperand *InitialValue, 1626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand *Endvalue, 1636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t IVBump) const; 1646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 16571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Analyze the statements in a loop to determine if the loop 16671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// has a computable trip count and, if so, return a value that represents 16771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// the trip count expression. 16871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountValue *getLoopTripCount(MachineLoop *L, 169a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &OldInsts); 17071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 17171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Return the expression that represents the number of times 17271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// a loop iterates. The function takes the operands that represent the 17371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// loop start value, loop end value, and induction value. Based upon 17471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// these operands, the function attempts to compute the trip count. 17571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// If the trip count is not directly available (as an immediate value, 17671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// or a register), the function will attempt to insert computation of it 17771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// to the loop's preheader. 1786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar CountValue *computeCount(MachineLoop *Loop, const MachineOperand *Start, 1796948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand *End, unsigned IVReg, 1806948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t IVBump, Comparison::Kind Cmp) const; 18171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 18271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Return true if the instruction is not valid within a hardware 18371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// loop. 1846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool isInvalidLoopOperation(const MachineInstr *MI, 1856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool IsInnerHWLoop) const; 186b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 18771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Return true if the loop contains an instruction that inhibits 18871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// using the hardware loop. 1896948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool containsInvalidInstruction(MachineLoop *L, bool IsInnerHWLoop) const; 190b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 19171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Given a loop, check if we can convert it to a hardware loop. 19271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// If so, then perform the conversion and return true. 1936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool convertToHardwareLoop(MachineLoop *L, bool &L0used, bool &L1used); 194b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 19571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Return true if the instruction is now dead. 19671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool isDead(const MachineInstr *MI, 197a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &DeadPhis) const; 19871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 19971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Remove the instruction if it is now dead. 20071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek void removeIfDead(MachineInstr *MI); 20171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 20271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Make sure that the "bump" instruction executes before the 20371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// compare. We need that for the IV fixup, so that the compare 20471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// instruction would not use a bumped value that has not yet been 20571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// defined. If the instructions are out of order, try to reorder them. 20671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool orderBumpCompare(MachineInstr *BumpI, MachineInstr *CmpI); 20771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 2086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// \brief Return true if MO and MI pair is visited only once. If visited 2096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// more than once, this indicates there is recursion. In such a case, 2106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// return false. 2116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, MachineInstr *MI, 2126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand *MO, 2136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopFeederMap &LoopFeederPhi) const; 2146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 2156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// \brief Return true if the Phi may generate a value that may underflow, 2166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// or may wrap. 2176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool phiMayWrapOrUnderflow(MachineInstr *Phi, const MachineOperand *EndVal, 2186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *MBB, MachineLoop *L, 2196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopFeederMap &LoopFeederPhi) const; 2206948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 2216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// \brief Return true if the induction variable may underflow an unsigned 2226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// value in the first iteration. 2236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool loopCountMayWrapOrUnderFlow(const MachineOperand *InitVal, 2246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand *EndVal, 2256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *MBB, MachineLoop *L, 2266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopFeederMap &LoopFeederPhi) const; 2276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 2286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// \brief Check if the given operand has a compile-time known constant 2296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// value. Return true if yes, and false otherwise. When returning true, set 2306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// Val to the corresponding constant value. 2316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool checkForImmediate(const MachineOperand &MO, int64_t &Val) const; 2326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 2336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// \brief Check if the operand has a compile-time known constant value. 2346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool isImmediate(const MachineOperand &MO) const { 2356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t V; 2366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return checkForImmediate(MO, V); 2376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 23871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 2396948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar /// \brief Return the immediate for the specified operand. 2406948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t getImmediate(const MachineOperand &MO) const { 2416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t V; 2426948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!checkForImmediate(MO, V)) 2436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar llvm_unreachable("Invalid operand"); 2446948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return V; 2456948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 24671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 24771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Reset the given machine operand to now refer to a new immediate 24871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// value. Assumes that the operand was already referencing an immediate 24971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// value, either directly, or via a register. 25071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek void setImmediate(MachineOperand &MO, int64_t Val); 25171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 25271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Fix the data flow of the induction varible. 25371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// The desired flow is: phi ---> bump -+-> comparison-in-latch. 25471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// | 25571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// +-> back to phi 25671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// where "bump" is the increment of the induction variable: 25771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// iv = iv + #const. 25871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Due to some prior code transformations, the actual flow may look 25971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// like this: 26071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// phi -+-> bump ---> back to phi 26171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// | 26271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// +-> comparison-in-latch (against upper_bound-bump), 26371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// i.e. the comparison that controls the loop execution may be using 26471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// the value of the induction variable from before the increment. 26571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// 26671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Return true if the loop's flow is the desired one (i.e. it's 26771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// either been fixed, or no fixing was necessary). 26871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Otherwise, return false. This can happen if the induction variable 26971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// couldn't be identified, or if the value in the latch's comparison 27071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// cannot be adjusted to reflect the post-bump value. 27171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool fixupInductionVariable(MachineLoop *L); 27271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 27371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// \brief Given a loop, if it does not have a preheader, create one. 27471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// Return the block that is the preheader. 27571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *createPreheaderForLoop(MachineLoop *L); 276b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum }; 277b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 278b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum char HexagonHardwareLoops::ID = 0; 27971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#ifndef NDEBUG 28071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int HexagonHardwareLoops::Counter = 0; 28171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#endif 282b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 28337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /// \brief Abstraction for a trip count of a loop. A smaller version 28471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// of the MachineOperand class without the concerns of changing the 28571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek /// operand representation. 286b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum class CountValue { 287b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum public: 288b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum enum CountValueType { 289b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum CV_Register, 290b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum CV_Immediate 291b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum }; 292b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum private: 293b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum CountValueType Kind; 294b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum union Values { 29571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek struct { 29671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Reg; 29771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Sub; 29871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } R; 29971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned ImmVal; 300b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } Contents; 301b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 302b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum public: 30371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek explicit CountValue(CountValueType t, unsigned v, unsigned u = 0) { 30471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Kind = t; 30571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Kind == CV_Register) { 30671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Contents.R.Reg = v; 30771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Contents.R.Sub = u; 30871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 30971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Contents.ImmVal = v; 31071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 31171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 312b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool isReg() const { return Kind == CV_Register; } 313b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool isImm() const { return Kind == CV_Immediate; } 314b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 315b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum unsigned getReg() const { 316b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum assert(isReg() && "Wrong CountValue accessor"); 31771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return Contents.R.Reg; 318b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 31971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned getSubReg() const { 32071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(isReg() && "Wrong CountValue accessor"); 32171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return Contents.R.Sub; 322b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 32371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned getImm() const { 324b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum assert(isImm() && "Wrong CountValue accessor"); 325b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return Contents.ImmVal; 326b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 327b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 328ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr) const { 32971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isReg()) { OS << PrintReg(Contents.R.Reg, TRI, Contents.R.Sub); } 33071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isImm()) { OS << Contents.ImmVal; } 331b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 332b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum }; 33371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} // end anonymous namespace 334b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 335b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 33671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekINITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops", 33771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek "Hexagon Hardware Loops", false, false) 33871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 33971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 34071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekINITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops", 34171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek "Hexagon Hardware Loops", false, false) 342b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 343b4b54153ad760c69a00a08531abef4ed434a5092Tony LinthicumFunctionPass *llvm::createHexagonHardwareLoops() { 344b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return new HexagonHardwareLoops(); 345b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 346b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 347b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicumbool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) { 348b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum DEBUG(dbgs() << "********* Hexagon Hardware Loops *********\n"); 349de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (skipFunction(*MF.getFunction())) 350de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 351b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 352b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool Changed = false; 353b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 354b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MLI = &getAnalysis<MachineLoopInfo>(); 355b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MRI = &MF.getRegInfo(); 35671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MDT = &getAnalysis<MachineDominatorTree>(); 357ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo(); 358b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 3596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (auto &L : *MLI) 3606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!L->getParentLoop()) { 3616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool L0Used = false; 3626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool L1Used = false; 3636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Changed |= convertToHardwareLoop(L, L0Used, L1Used); 3646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 365b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 366b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return Changed; 367b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 368b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 3696948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// \brief Return the latch block if it's one of the exiting blocks. Otherwise, 3706948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// return the exiting block. Return 'null' when multiple exiting blocks are 3716948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// present. 3726948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic MachineBasicBlock* getExitingBlock(MachineLoop *L) { 3736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (MachineBasicBlock *Latch = L->getLoopLatch()) { 3746948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (L->isLoopExiting(Latch)) 3756948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return Latch; 3766948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else 3776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return L->getExitingBlock(); 3786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 3796948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 3806948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 38171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 38271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::findInductionRegister(MachineLoop *L, 38371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned &Reg, 38471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t &IVBump, 38571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *&IVOp 38671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek ) const { 38771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Header = L->getHeader(); 38871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Preheader = L->getLoopPreheader(); 38971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Latch = L->getLoopLatch(); 3906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *ExitingBlock = getExitingBlock(L); 3916948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Header || !Preheader || !Latch || !ExitingBlock) 39271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 39371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 39471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This pair represents an induction register together with an immediate 39571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // value that will be added to it in each loop iteration. 39671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::pair<unsigned,int64_t> RegisterBump; 39771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 39871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Mapping: R.next -> (R, bump), where R, R.next and bump are derived 39971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // from an induction operation 40071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // R.next = R + bump 40171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // where bump is an immediate value. 40271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::map<unsigned,RegisterBump> InductionMap; 40371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 40471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap IndMap; 40571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 40671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineBasicBlock::instr_iterator instr_iterator; 40771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 40871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E && I->isPHI(); ++I) { 40971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *Phi = &*I; 41071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 41171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Have a PHI instruction. Get the operand that corresponds to the 41271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // latch block, and see if is a result of an addition of form "reg+imm", 41371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // where the "reg" is defined by the PHI node we are looking at. 41471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) { 41571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Phi->getOperand(i+1).getMBB() != Latch) 41671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 41771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 41871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PhiOpReg = Phi->getOperand(i).getReg(); 41971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *DI = MRI->getVRegDef(PhiOpReg); 42071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned UpdOpc = DI->getOpcode(); 4216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool isAdd = (UpdOpc == Hexagon::A2_addi || UpdOpc == Hexagon::A2_addp); 42271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 42371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isAdd) { 4246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // If the register operand to the add is the PHI we're looking at, this 4256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // meets the induction pattern. 42671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IndReg = DI->getOperand(1).getReg(); 4276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineOperand &Opnd2 = DI->getOperand(2); 4286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t V; 4296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) { 43071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned UpdReg = DI->getOperand(0).getReg(); 43171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IndMap.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V))); 43271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 43371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 43471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } // for (i) 43571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } // for (instr) 43671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 43771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,2> Cond; 438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TB = nullptr, *FB = nullptr; 439de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false); 44071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (NotAnalyzed) 44171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 44271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 4436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned PredR, PredPos, PredRegFlags; 4446948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!TII->getPredReg(Cond, PredR, PredPos, PredRegFlags)) 4456948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 44671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 44771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *PredI = MRI->getVRegDef(PredR); 44871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!PredI->isCompare()) 44971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 45071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 45171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CmpReg1 = 0, CmpReg2 = 0; 45271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int CmpImm = 0, CmpMask = 0; 453de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool CmpAnalyzed = 454de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TII->analyzeCompare(*PredI, CmpReg1, CmpReg2, CmpMask, CmpImm); 45571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Fail if the compare was not analyzed, or it's not comparing a register 45671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // with an immediate value. Not checking the mask here, since we handle 4576948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // the individual compare opcodes (including A4_cmpb*) later on. 45871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!CmpAnalyzed) 45971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 46071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 46171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Exactly one of the input registers to the comparison should be among 46271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the induction registers. 46371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap::iterator IndMapEnd = IndMap.end(); 46471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap::iterator F = IndMapEnd; 46571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpReg1 != 0) { 46671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap::iterator F1 = IndMap.find(CmpReg1); 46771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (F1 != IndMapEnd) 46871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek F = F1; 46971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 47071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpReg2 != 0) { 47171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InductionMap::iterator F2 = IndMap.find(CmpReg2); 47271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (F2 != IndMapEnd) { 47371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (F != IndMapEnd) 47471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 47571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek F = F2; 47671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 47771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 47871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (F == IndMapEnd) 47971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 48071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 48171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Reg = F->second.first; 48271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IVBump = F->second.second; 48371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IVOp = MRI->getVRegDef(F->first); 48471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 48571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 48671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 4876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar// Return the comparison kind for the specified opcode. 4886948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga NainarHexagonHardwareLoops::Comparison::Kind 4896948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga NainarHexagonHardwareLoops::getComparisonKind(unsigned CondOpc, 4906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineOperand *InitialValue, 4916948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand *EndValue, 4926948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t IVBump) const { 4936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Comparison::Kind Cmp = (Comparison::Kind)0; 4946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar switch (CondOpc) { 4956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpeqi: 4966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpeq: 4976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpeqp: 4986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::EQ; 4996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 5006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C4_cmpneq: 5016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C4_cmpneqi: 5026948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::NE; 5036948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 5046948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C4_cmplte: 5056948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::LEs; 5066948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 5076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C4_cmplteu: 5086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::LEu; 5096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 5106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpgtui: 5116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpgtu: 5126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpgtup: 5136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::GTu; 5146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 5156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpgti: 5166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpgt: 5176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::C2_cmpgtp: 5186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::GTs; 5196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 5206948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar default: 5216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return (Comparison::Kind)0; 5226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 5236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return Cmp; 5246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 52571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 52671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Analyze the statements in a loop to determine if the loop has 52771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// a computable trip count and, if so, return a value that represents 52871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// the trip count expression. 529b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum/// 53071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// This function iterates over the phi nodes in the loop to check for 53171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// induction variable patterns that are used in the calculation for 53271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// the number of time the loop is executed. 53371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekCountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L, 5346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVectorImpl<MachineInstr *> &OldInsts) { 535b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *TopMBB = L->getTopBlock(); 536b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(); 537b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum assert(PI != TopMBB->pred_end() && 538b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum "Loop must have more than one incoming edge!"); 539b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *Backedge = *PI++; 54071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PI == TopMBB->pred_end()) // dead loop? 541dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 542b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *Incoming = *PI++; 54371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PI != TopMBB->pred_end()) // multiple backedges? 544dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 545b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 54671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Make sure there is one incoming and one backedge and determine which 547b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // is which. 548b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (L->contains(Incoming)) { 549b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (L->contains(Backedge)) 550dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 551b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum std::swap(Incoming, Backedge); 552b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else if (!L->contains(Backedge)) 553dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 554b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 55571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Look for the cmp instruction to determine if we can get a useful trip 55671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // count. The trip count can be either a register or an immediate. The 55771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // location of the value depends upon the type (reg or imm). 5586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *ExitingBlock = getExitingBlock(L); 5596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!ExitingBlock) 560dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 56171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 56271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IVReg = 0; 56371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t IVBump = 0; 56471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *IVOp; 56571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp); 56671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!FoundIV) 567dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 56871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 56971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Preheader = L->getLoopPreheader(); 57071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 571dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineOperand *InitialValue = nullptr; 57271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *IV_Phi = MRI->getVRegDef(IVReg); 5736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *Latch = L->getLoopLatch(); 57471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) { 57571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB(); 57671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MBB == Preheader) 57771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek InitialValue = &IV_Phi->getOperand(i); 57871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else if (MBB == Latch) 57971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IVReg = IV_Phi->getOperand(i).getReg(); // Want IV reg after bump. 58071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 58171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!InitialValue) 582dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 58371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 58471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,2> Cond; 585dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TB = nullptr, *FB = nullptr; 586de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false); 58771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (NotAnalyzed) 588dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 58971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 59071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Header = L->getHeader(); 59171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // TB must be non-null. If FB is also non-null, one of them must be 59271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the header. Otherwise, branch to TB could be exiting the loop, and 59371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the fall through can go to the header. 5946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar assert (TB && "Exit block without a branch?"); 5956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) { 5966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *LTB = 0, *LFB = 0; 5976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<MachineOperand,2> LCond; 598de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false); 5996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (NotAnalyzed) 6006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 6016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (TB == Latch) 6026948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar TB = (LTB == Header) ? LTB : LFB; 6036948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else 6046948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar FB = (LTB == Header) ? LTB: LFB; 6056948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 60671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert ((!FB || TB == Header || FB == Header) && "Branches not to header?"); 60771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!TB || (FB && TB != Header && FB != Header)) 608dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 60971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 61071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Branches of form "if (!P) ..." cause HexagonInstrInfo::AnalyzeBranch 61171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // to put imm(0), followed by P in the vector Cond. 61271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If TB is not the header, it means that the "not-taken" path must lead 61371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // to the header. 6146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool Negated = TII->predOpcodeHasNot(Cond) ^ (TB != Header); 6156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned PredReg, PredPos, PredRegFlags; 6166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!TII->getPredReg(Cond, PredReg, PredPos, PredRegFlags)) 6176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 61871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *CondI = MRI->getVRegDef(PredReg); 61971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CondOpc = CondI->getOpcode(); 62071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 62171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CmpReg1 = 0, CmpReg2 = 0; 62271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int Mask = 0, ImmValue = 0; 623de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool AnalyzedCmp = 624de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TII->analyzeCompare(*CondI, CmpReg1, CmpReg2, Mask, ImmValue); 62571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!AnalyzedCmp) 626dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 62771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 62871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The comparison operator type determines how we compute the loop 62971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // trip count. 63071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek OldInsts.push_back(CondI); 63171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek OldInsts.push_back(IVOp); 63271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 63371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Sadly, the following code gets information based on the position 63471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // of the operands in the compare instruction. This has to be done 63571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // this way, because the comparisons check for a specific relationship 63671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // between the operands (e.g. is-less-than), rather than to find out 63771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // what relationship the operands are in (as on PPC). 63871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Comparison::Kind Cmp; 63971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool isSwapped = false; 64071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &Op1 = CondI->getOperand(1); 64171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &Op2 = CondI->getOperand(2); 642dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const MachineOperand *EndValue = nullptr; 64371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 64471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Op1.isReg()) { 64571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Op2.isImm() || Op1.getReg() == IVReg) 64671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndValue = &Op2; 64771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else { 64871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndValue = &Op1; 64971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek isSwapped = true; 650b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 651b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 652b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 65371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!EndValue) 654dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 65571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 6566948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = getComparisonKind(CondOpc, InitialValue, EndValue, IVBump); 6576948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Cmp) 6586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 6596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Negated) 6606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::getNegatedComparison(Cmp); 66171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isSwapped) 6626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::getSwappedComparison(Cmp); 66371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 66471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (InitialValue->isReg()) { 66571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = InitialValue->getReg(); 66671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent(); 66771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MDT->properlyDominates(DefBB, Header)) 668dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 66971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek OldInsts.push_back(MRI->getVRegDef(R)); 67071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 67171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (EndValue->isReg()) { 67271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = EndValue->getReg(); 67371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *DefBB = MRI->getVRegDef(R)->getParent(); 67471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MDT->properlyDominates(DefBB, Header)) 675dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 6766948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar OldInsts.push_back(MRI->getVRegDef(R)); 67771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 67871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 67971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return computeCount(L, InitialValue, EndValue, IVReg, IVBump, Cmp); 680b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 681b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 68271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Helper function that returns the expression that represents the 68371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// number of times a loop iterates. The function takes the operands that 68471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// represent the loop start value, loop end value, and induction value. 68571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// Based upon these operands, the function attempts to compute the trip count. 68671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekCountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop, 68771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand *Start, 68871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand *End, 68971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IVReg, 69071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t IVBump, 69171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Comparison::Kind Cmp) const { 69271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Cannot handle comparison EQ, i.e. while (A == B). 69371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Cmp == Comparison::EQ) 694dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 69571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 69671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Check if either the start or end values are an assignment of an immediate. 69771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If so, use the immediate value rather than the register. 69871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isReg()) { 69971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineInstr *StartValInstr = MRI->getVRegDef(Start->getReg()); 7006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (StartValInstr && (StartValInstr->getOpcode() == Hexagon::A2_tfrsi || 7016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar StartValInstr->getOpcode() == Hexagon::A2_tfrpi)) 70271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Start = &StartValInstr->getOperand(1); 70371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 70471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (End->isReg()) { 70571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg()); 7066948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (EndValInstr && (EndValInstr->getOpcode() == Hexagon::A2_tfrsi || 7076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar EndValInstr->getOpcode() == Hexagon::A2_tfrpi)) 70871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek End = &EndValInstr->getOperand(1); 70971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 71071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 7116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Start->isReg() && !Start->isImm()) 7126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 7136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!End->isReg() && !End->isImm()) 7146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 71571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 71671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool CmpLess = Cmp & Comparison::L; 71771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool CmpGreater = Cmp & Comparison::G; 71871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool CmpHasEqual = Cmp & Comparison::EQ; 71971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 72071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Avoid certain wrap-arounds. This doesn't detect all wrap-arounds. 72171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpLess && IVBump < 0) 7226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Loop going while iv is "less" with the iv value going down. Must wrap. 723dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 7246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 72571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpGreater && IVBump > 0) 7266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Loop going while iv is "greater" with the iv value going up. Must wrap. 727dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 72871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 7296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Phis that may feed into the loop. 7306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopFeederMap LoopFeederPhi; 7316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 732f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Check if the initial value may be zero and can be decremented in the first 7336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // iteration. If the value is zero, the endloop instruction will not decrement 734f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the loop counter, so we shouldn't generate a hardware loop in this case. 7356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (loopCountMayWrapOrUnderFlow(Start, End, Loop->getLoopPreheader(), Loop, 7366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopFeederPhi)) 7376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 7386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 73971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm() && End->isImm()) { 74071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Both, start and end are immediates. 74171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t StartV = Start->getImm(); 74271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t EndV = End->getImm(); 74371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t Dist = EndV - StartV; 74471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Dist == 0) 745dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 74671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 74771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool Exact = (Dist % IVBump) == 0; 74871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 74971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Cmp == Comparison::NE) { 75071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Exact) 751dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 75271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if ((Dist < 0) ^ (IVBump < 0)) 753dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 75471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 75571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 75671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // For comparisons that include the final value (i.e. include equality 75771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // with the final value), we need to increase the distance by 1. 75871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpHasEqual) 75971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Dist = Dist > 0 ? Dist+1 : Dist-1; 76071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 7616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // For the loop to iterate, CmpLess should imply Dist > 0. Similarly, 7626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // CmpGreater should imply Dist < 0. These conditions could actually 7636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // fail, for example, in unreachable code (which may still appear to be 7646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // reachable in the CFG). 7656948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if ((CmpLess && Dist < 0) || (CmpGreater && Dist > 0)) 7666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 76771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 76871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // "Normalized" distance, i.e. with the bump set to +-1. 7696948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t Dist1 = (IVBump > 0) ? (Dist + (IVBump - 1)) / IVBump 7706948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar : (-Dist + (-IVBump - 1)) / (-IVBump); 77171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (Dist1 > 0 && "Fishy thing. Both operands have the same sign."); 77271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 77371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek uint64_t Count = Dist1; 77471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 77571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Count > 0xFFFFFFFFULL) 776dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 77771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 77871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return new CountValue(CountValue::CV_Immediate, Count); 77971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 78071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 78171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // A general case: Start and End are some values, but the actual 78271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // iteration count may not be available. If it is not, insert 78371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // a computation of it into the preheader. 78471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 78571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If the induction variable bump is not a power of 2, quit. 78671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Othwerise we'd need a general integer division. 7874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!isPowerOf2_64(std::abs(IVBump))) 788dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 78971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 79071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PH = Loop->getLoopPreheader(); 79171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (PH && "Should have a preheader by now"); 79271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator(); 7936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DebugLoc DL; 7946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (InsertPos != PH->end()) 7956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DL = InsertPos->getDebugLoc(); 79671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 79771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If Start is an immediate and End is a register, the trip count 79871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // will be "reg - imm". Hexagon's "subtract immediate" instruction 79971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // is actually "reg + -imm". 80071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 80171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If the loop IV is going downwards, i.e. if the bump is negative, 80271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // then the iteration count (computed as End-Start) will need to be 80371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // negated. To avoid the negation, just swap Start and End. 80471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (IVBump < 0) { 80571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek std::swap(Start, End); 80671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IVBump = -IVBump; 80771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 80871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Cmp may now have a wrong direction, e.g. LEs may now be GEs. 80971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Signedness, and "including equality" are preserved. 81071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 81171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool RegToImm = Start->isReg() && End->isImm(); // for (reg..imm) 81271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool RegToReg = Start->isReg() && End->isReg(); // for (reg..reg) 81371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 81471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t StartV = 0, EndV = 0; 81571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm()) 81671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek StartV = Start->getImm(); 81771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (End->isImm()) 81871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndV = End->getImm(); 81971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 82071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t AdjV = 0; 82171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // To compute the iteration count, we would need this computation: 82271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Count = (End - Start + (IVBump-1)) / IVBump 82371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // or, when CmpHasEqual: 82471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Count = (End - Start + (IVBump-1)+1) / IVBump 82571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The "IVBump-1" part is the adjustment (AdjV). We can avoid 82671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // generating an instruction specifically to add it if we can adjust 82771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the immediate values for Start or End. 82871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 82971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpHasEqual) { 83071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Need to add 1 to the total iteration count. 83171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm()) 83271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek StartV--; 83371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else if (End->isImm()) 83471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndV++; 83571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else 83671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjV += 1; 83771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 83871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 83971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Cmp != Comparison::NE) { 84071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm()) 84171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek StartV -= (IVBump-1); 84271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else if (End->isImm()) 84371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek EndV += (IVBump-1); 84471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek else 84571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjV += (IVBump-1); 84671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 84771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 84871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = 0, SR = 0; 84971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isReg()) { 85071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek R = Start->getReg(); 85171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SR = Start->getSubReg(); 85271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 85371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek R = End->getReg(); 85471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SR = End->getSubReg(); 85571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 85671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const TargetRegisterClass *RC = MRI->getRegClass(R); 85771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Hardware loops cannot handle 64-bit registers. If it's a double 85871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // register, it has to have a subregister. 85971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!SR && RC == &Hexagon::DoubleRegsRegClass) 860dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 86171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const TargetRegisterClass *IntRC = &Hexagon::IntRegsRegClass; 86271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 86371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Compute DistR (register with the distance between Start and End). 86471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned DistR, DistSR; 86571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 86671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Avoid special case, where the start value is an imm(0). 86771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Start->isImm() && StartV == 0) { 86871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DistR = End->getReg(); 86971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DistSR = End->getSubReg(); 87071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 871ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const MCInstrDesc &SubD = RegToReg ? TII->get(Hexagon::A2_sub) : 872ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines (RegToImm ? TII->get(Hexagon::A2_subri) : 873ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines TII->get(Hexagon::A2_addi)); 8746948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (RegToReg || RegToImm) { 8756948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned SubR = MRI->createVirtualRegister(IntRC); 8766948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstrBuilder SubIB = 8776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BuildMI(*PH, InsertPos, DL, SubD, SubR); 8786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 8796948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (RegToReg) 8806948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SubIB.addReg(End->getReg(), 0, End->getSubReg()) 8816948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar .addReg(Start->getReg(), 0, Start->getSubReg()); 8826948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else 8836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SubIB.addImm(EndV) 8846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar .addReg(Start->getReg(), 0, Start->getSubReg()); 8856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DistR = SubR; 8866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else { 8876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // If the loop has been unrolled, we should use the original loop count 8886948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // instead of recalculating the value. This will avoid additional 8896948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // 'Add' instruction. 8906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineInstr *EndValInstr = MRI->getVRegDef(End->getReg()); 8916948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (EndValInstr->getOpcode() == Hexagon::A2_addi && 8926948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar EndValInstr->getOperand(2).getImm() == StartV) { 8936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DistR = EndValInstr->getOperand(1).getReg(); 8946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else { 8956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned SubR = MRI->createVirtualRegister(IntRC); 8966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstrBuilder SubIB = 8976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BuildMI(*PH, InsertPos, DL, SubD, SubR); 8986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SubIB.addReg(End->getReg(), 0, End->getSubReg()) 8996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar .addImm(-StartV); 9006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DistR = SubR; 9016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 90271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 90371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DistSR = 0; 90471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 90571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 90671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // From DistR, compute AdjR (register with the adjusted distance). 90771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned AdjR, AdjSR; 90871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 90971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (AdjV == 0) { 91071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjR = DistR; 91171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjSR = DistSR; 91271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 91371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Generate CountR = ADD DistR, AdjVal 91471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned AddR = MRI->createVirtualRegister(IntRC); 915ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines MCInstrDesc const &AddD = TII->get(Hexagon::A2_addi); 91671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek BuildMI(*PH, InsertPos, DL, AddD, AddR) 91771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(DistR, 0, DistSR) 91871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addImm(AdjV); 91971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 92071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjR = AddR; 92171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek AdjSR = 0; 92271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 92371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 92471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // From AdjR, compute CountR (register with the final count). 92571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CountR, CountSR; 92671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 92771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (IVBump == 1) { 92871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountR = AdjR; 92971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountSR = AdjSR; 93071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else { 93171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The IV bump is a power of two. Log_2(IV bump) is the shift amount. 93271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Shift = Log2_32(IVBump); 93371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 93471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Generate NormR = LSR DistR, Shift. 93571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned LsrR = MRI->createVirtualRegister(IntRC); 936ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const MCInstrDesc &LsrD = TII->get(Hexagon::S2_lsr_i_r); 93771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek BuildMI(*PH, InsertPos, DL, LsrD, LsrR) 93871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(AdjR, 0, AdjSR) 93971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addImm(Shift); 94071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 94171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountR = LsrR; 94271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountSR = 0; 94371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 94471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 94571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return new CountValue(CountValue::CV_Register, CountR, CountSR); 946b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 947b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 94871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Return true if the operation is invalid within hardware loop. 9496948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI, 9506948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool IsInnerHWLoop) const { 951b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 9526948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Call is not allowed because the callee may use a hardware loop except for 9536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // the case when the call never returns. 9546948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (MI->getDesc().isCall() && MI->getOpcode() != Hexagon::CALLv3nr) 955b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 95671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 9576948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Check if the instruction defines a hardware loop register. 958b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 959b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum const MachineOperand &MO = MI->getOperand(i); 96071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MO.isReg() || !MO.isDef()) 96171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 96271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = MO.getReg(); 9636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (IsInnerHWLoop && (R == Hexagon::LC0 || R == Hexagon::SA0 || 9646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar R == Hexagon::LC1 || R == Hexagon::SA1)) 9656948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 9666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!IsInnerHWLoop && (R == Hexagon::LC1 || R == Hexagon::SA1)) 967b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 968b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 969b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 970b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 971b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 9726948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// \brief Return true if the loop contains an instruction that inhibits 9736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// the use of the hardware loop instruction. 9746948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L, 9756948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool IsInnerHWLoop) const { 97694ee55d4b39d6506cf4e0f4e4b1c0b7fbbfeaed5Benjamin Kramer const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks(); 9776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG(dbgs() << "\nhw_loop head, BB#" << Blocks[0]->getNumber();); 978b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 979b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *MBB = Blocks[i]; 980b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum for (MachineBasicBlock::iterator 981b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) { 982b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum const MachineInstr *MI = &*MII; 9836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (isInvalidLoopOperation(MI, IsInnerHWLoop)) { 9846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG(dbgs()<< "\nCannot convert to hw_loop due to:"; MI->dump();); 985b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 9866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 987b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 988b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 989b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 990b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 991b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 99271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Returns true if the instruction is dead. This was essentially 99371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// copied from DeadMachineInstructionElim::isDead, but with special cases 99471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// for inline asm, physical registers and instructions with side effects 99571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// removed. 99671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::isDead(const MachineInstr *MI, 997a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<MachineInstr *> &DeadPhis) const { 99871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Examine each operand. 99971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 100071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &MO = MI->getOperand(i); 100171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MO.isReg() || !MO.isDef()) 100271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 100371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 100471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Reg = MO.getReg(); 100571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MRI->use_nodbg_empty(Reg)) 100671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 100771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 100871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineRegisterInfo::use_nodbg_iterator use_nodbg_iterator; 100971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 101071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This instruction has users, but if the only user is the phi node for the 101171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // parent block, and the only use of that phi node is this instruction, then 101271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // this instruction is dead: both it (and the phi node) can be removed. 101371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek use_nodbg_iterator I = MRI->use_nodbg_begin(Reg); 101471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek use_nodbg_iterator End = MRI->use_nodbg_end(); 101536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (std::next(I) != End || !I->getParent()->isPHI()) 101671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 101771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 101836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineInstr *OnePhi = I->getParent(); 101971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned j = 0, f = OnePhi->getNumOperands(); j != f; ++j) { 102071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &OPO = OnePhi->getOperand(j); 102171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!OPO.isReg() || !OPO.isDef()) 102271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 102371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 102471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned OPReg = OPO.getReg(); 102571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek use_nodbg_iterator nextJ; 102671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (use_nodbg_iterator J = MRI->use_nodbg_begin(OPReg); 102771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek J != End; J = nextJ) { 102836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines nextJ = std::next(J); 102936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineOperand &Use = *J; 103071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *UseMI = Use.getParent(); 103171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 10326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // If the phi node has a user that is not MI, bail. 103371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MI != UseMI) 103471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 103571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 103671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 103771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DeadPhis.push_back(OnePhi); 103871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 103971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 104071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If there are no defs with uses, the instruction is dead. 104171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 104271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 104371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 104471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekvoid HexagonHardwareLoops::removeIfDead(MachineInstr *MI) { 104571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This procedure was essentially copied from DeadMachineInstructionElim. 104671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 104771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineInstr*, 1> DeadPhis; 104871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isDead(MI, DeadPhis)) { 104971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DEBUG(dbgs() << "HW looping will remove: " << *MI); 105071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 105171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // It is possible that some DBG_VALUE instructions refer to this 105271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // instruction. Examine each def operand for such references; 105371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // if found, mark the DBG_VALUE as undef (but don't delete it). 105471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 105571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MachineOperand &MO = MI->getOperand(i); 105671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!MO.isReg() || !MO.isDef()) 105771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 105871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned Reg = MO.getReg(); 105971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineRegisterInfo::use_iterator nextI; 106071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (MachineRegisterInfo::use_iterator I = MRI->use_begin(Reg), 106171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek E = MRI->use_end(); I != E; I = nextI) { 106236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines nextI = std::next(I); // I is invalidated by the setReg 106336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineOperand &Use = *I; 106436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineInstr *UseMI = I->getParent(); 106571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (UseMI == MI) 106671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 106771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Use.isDebug()) 106871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek UseMI->getOperand(0).setReg(0U); 106971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 107071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 107171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 107271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MI->eraseFromParent(); 107371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0; i < DeadPhis.size(); ++i) 107471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DeadPhis[i]->eraseFromParent(); 107571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 107671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 107771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 107871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Check if the loop is a candidate for converting to a hardware 107971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// loop. If so, then perform the transformation. 1080b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum/// 108171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// This function works on innermost loops first. A loop can be converted 108271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// if it is a counting loop; either a register value or an immediate. 1083b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum/// 108471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// The code makes several assumptions about the representation of the loop 108571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// in llvm. 10866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L, 10876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool &RecL0used, 10886948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool &RecL1used) { 108971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This is just for sanity. 109071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(L->getHeader() && "Loop without a header?"); 109171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1092b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum bool Changed = false; 10936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool L0Used = false; 10946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool L1Used = false; 10956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1096b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Process nested loops first. 10976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 10986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Changed |= convertToHardwareLoop(*I, RecL0used, RecL1used); 10996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar L0Used |= RecL0used; 11006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar L1Used |= RecL1used; 11016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 110271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1103b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // If a nested loop has been converted, then we can't convert this loop. 11046948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Changed && L0Used && L1Used) 1105b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return Changed; 110671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 11076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned LOOP_i; 11086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned LOOP_r; 11096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned ENDLOOP; 11106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 11116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Flag used to track loopN instruction: 11126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // 1 - Hardware loop is being generated for the inner most loop. 11136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // 0 - Hardware loop is being generated for the outer loop. 11146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned IsInnerHWLoop = 1; 11156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 11166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (L0Used) { 11176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LOOP_i = Hexagon::J2_loop1i; 11186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LOOP_r = Hexagon::J2_loop1r; 11196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar ENDLOOP = Hexagon::ENDLOOP1; 11206948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar IsInnerHWLoop = 0; 11216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else { 11226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LOOP_i = Hexagon::J2_loop0i; 11236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LOOP_r = Hexagon::J2_loop0r; 11246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar ENDLOOP = Hexagon::ENDLOOP0; 11256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 11266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 112771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#ifndef NDEBUG 112871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Stop trying after reaching the limit (if any). 112971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int Limit = HWLoopLimit; 113071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Limit >= 0) { 113171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Counter >= HWLoopLimit) 113271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 113371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Counter++; 1134b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 113571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek#endif 113671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1137b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Does the loop contain any invalid instructions? 11386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (containsInvalidInstruction(L, IsInnerHWLoop)) 1139b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 114071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 11416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *LastMBB = getExitingBlock(L); 1142b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Don't generate hw loop if the loop has more than one exit. 1143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!LastMBB) 1144b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 114571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1146b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator(); 114771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (LastI == LastMBB->end()) 1148ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis return false; 114971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 11506948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Is the induction variable bump feeding the latch condition? 11516948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!fixupInductionVariable(L)) 11526948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 11536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 115471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Ensure the loop has a preheader: the loop instruction will be 115571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // placed there. 115671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Preheader = L->getLoopPreheader(); 115771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Preheader) { 115871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Preheader = createPreheaderForLoop(L); 115971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Preheader) 116071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 116171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 11626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 116371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator(); 116471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 116571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineInstr*, 2> OldInsts; 116671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Are we able to determine the trip count for the loop? 116771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CountValue *TripCount = getLoopTripCount(L, OldInsts); 1168dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!TripCount) 116971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 117071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 117171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Is the trip count available in the preheader? 117271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (TripCount->isReg()) { 117371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // There will be a use of the register inserted into the preheader, 117471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // so make sure that the register is actually defined at that point. 117571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg()); 117671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *BBDef = TCDef->getParent(); 11776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!MDT->dominates(BBDef, Preheader)) 11786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 1179ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis } 1180b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1181b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Determine the loop start. 11826948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *TopBlock = L->getTopBlock(); 11836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *ExitingBlock = getExitingBlock(L); 11846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *LoopStart = 0; 11856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (ExitingBlock != L->getLoopLatch()) { 11866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *TB = 0, *FB = 0; 11876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<MachineOperand, 2> Cond; 11886948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1189de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false)) 11906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 11916948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 11926948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (L->contains(TB)) 11936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopStart = TB; 11946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else if (L->contains(FB)) 11956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopStart = FB; 11966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else 1197b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return false; 1198b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 11996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else 12006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopStart = TopBlock; 1201b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 120271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Convert the loop to a hardware loop. 1203b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum DEBUG(dbgs() << "Change to hardware loop at "; L->dump()); 120471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DebugLoc DL; 1205ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis if (InsertPos != Preheader->end()) 120671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DL = InsertPos->getDebugLoc(); 1207b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1208b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (TripCount->isReg()) { 1209b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Create a copy of the loop count register. 121071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); 121171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek BuildMI(*Preheader, InsertPos, DL, TII->get(TargetOpcode::COPY), CountReg) 121271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(TripCount->getReg(), 0, TripCount->getSubReg()); 1213d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // Add the Loop instruction to the beginning of the loop. 12146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)).addMBB(LoopStart) 121571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addReg(CountReg); 1216b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else { 121771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(TripCount->isImm() && "Expecting immediate value for trip count"); 121871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Add the Loop immediate instruction to the beginning of the loop, 121971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // if the immediate fits in the instructions. Otherwise, we need to 122071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // create a new virtual register. 1221b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum int64_t CountImm = TripCount->getImm(); 12226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!TII->isValidOffset(LOOP_i, CountImm)) { 122371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CountReg = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass); 1224ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BuildMI(*Preheader, InsertPos, DL, TII->get(Hexagon::A2_tfrsi), CountReg) 122571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addImm(CountImm); 12266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_r)) 122771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addMBB(LoopStart).addReg(CountReg); 122871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else 12296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BuildMI(*Preheader, InsertPos, DL, TII->get(LOOP_i)) 123071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek .addMBB(LoopStart).addImm(CountImm); 1231b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1232b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 123371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Make sure the loop start always has a reference in the CFG. We need 123471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // to create a BlockAddress operand to get this mechanism to work both the 1235b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // MachineBasicBlock and BasicBlock objects need the flag set. 1236b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum LoopStart->setHasAddressTaken(); 1237b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // This line is needed to set the hasAddressTaken flag on the BasicBlock 123871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // object. 1239b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum BlockAddress::get(const_cast<BasicBlock *>(LoopStart->getBasicBlock())); 1240b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1241b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Replace the loop branch with an endloop instruction. 1242ade50dc6c7d18ba2e47aab7e535c709de76fe152Matthew Curtis DebugLoc LastIDL = LastI->getDebugLoc(); 12436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BuildMI(*LastMBB, LastI, LastIDL, TII->get(ENDLOOP)).addMBB(LoopStart); 1244b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 1245b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // The loop ends with either: 1246b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // - a conditional branch followed by an unconditional branch, or 1247b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // - a conditional branch to the loop start. 1248ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (LastI->getOpcode() == Hexagon::J2_jumpt || 1249ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LastI->getOpcode() == Hexagon::J2_jumpf) { 125071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Delete one and change/add an uncond. branch to out of the loop. 1251b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum MachineBasicBlock *BranchTarget = LastI->getOperand(1).getMBB(); 1252b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum LastI = LastMBB->erase(LastI); 1253b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum if (!L->contains(BranchTarget)) { 125471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (LastI != LastMBB->end()) 125571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek LastI = LastMBB->erase(LastI); 1256b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum SmallVector<MachineOperand, 0> Cond; 1257dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TII->InsertBranch(*LastMBB, BranchTarget, nullptr, Cond, LastIDL); 1258b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1259b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else { 1260b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum // Conditional branch to loop start; just delete it. 1261b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum LastMBB->erase(LastI); 1262b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1263b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum delete TripCount; 1264b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 126571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The induction operation and the comparison may now be 126671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // unneeded. If these are unneeded, then remove them. 126771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0; i < OldInsts.size(); ++i) 126871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek removeIfDead(OldInsts[i]); 126971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1270b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum ++NumHWLoops; 12716948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 12726948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Set RecL1used and RecL0used only after hardware loop has been 12736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // successfully generated. Doing it earlier can cause wrong loop instruction 12746948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // to be used. 12756948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (L0Used) // Loop0 was already used. So, the correct loop must be loop1. 12766948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar RecL1used = true; 12776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else 12786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar RecL0used = true; 12796948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1280b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum return true; 1281b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1282b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 128371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI, 128471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *CmpI) { 128571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (BumpI != CmpI && "Bump and compare in the same instruction?"); 128671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 128771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *BB = BumpI->getParent(); 128871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpI->getParent() != BB) 128971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 129071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 129171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineBasicBlock::instr_iterator instr_iterator; 129271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Check if things are in order to begin with. 1293f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (instr_iterator I(BumpI), E = BB->instr_end(); I != E; ++I) 129471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (&*I == CmpI) 129571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 129671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 129771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Out of order. 129871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PredR = CmpI->getOperand(0).getReg(); 129971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool FoundBump = false; 1300f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar instr_iterator CmpIt = CmpI->getIterator(), NextIt = std::next(CmpIt); 130171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = NextIt, E = BB->instr_end(); I != E; ++I) { 130271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *In = &*I; 130371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, n = In->getNumOperands(); i < n; ++i) { 130471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineOperand &MO = In->getOperand(i); 130571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isReg() && MO.isUse()) { 130671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.getReg() == PredR) // Found an intervening use of PredR. 130771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 130871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 130971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 131071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 131171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (In == BumpI) { 1312f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BB->splice(++BumpI->getIterator(), BB, CmpI->getIterator()); 131371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek FoundBump = true; 131471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek break; 131571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 131671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 131771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (FoundBump && "Cannot determine instruction order"); 131871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return FoundBump; 1319b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1320b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 13216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// This function is required to break recursion. Visiting phis in a loop may 13226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// result in recursion during compilation. We break the recursion by making 13236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// sure that we visit a MachineOperand and its definition in a 13246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// MachineInstruction only once. If we attempt to visit more than once, then 13256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// there is recursion, and will return false. 13266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A, 13276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstr *MI, 13286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand *MO, 13296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopFeederMap &LoopFeederPhi) const { 13306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (LoopFeederPhi.find(MO->getReg()) == LoopFeederPhi.end()) { 13316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const std::vector<MachineBasicBlock *> &Blocks = L->getBlocks(); 13326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG(dbgs() << "\nhw_loop head, BB#" << Blocks[0]->getNumber();); 13336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Ignore all BBs that form Loop. 13346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 13356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *MBB = Blocks[i]; 13366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (A == MBB) 13376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 13386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 13396948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstr *Def = MRI->getVRegDef(MO->getReg()); 13406948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopFeederPhi.insert(std::make_pair(MO->getReg(), Def)); 13416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 13426948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else 13436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Already visited node. 13446948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 13456948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 13466948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 13476948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// Return true if a Phi may generate a value that can underflow. 13486948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// This function calls loopCountMayWrapOrUnderFlow for each Phi operand. 13496948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool HexagonHardwareLoops::phiMayWrapOrUnderflow( 13506948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB, 13516948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineLoop *L, LoopFeederMap &LoopFeederPhi) const { 13526948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar assert(Phi->isPHI() && "Expecting a Phi."); 13536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Walk through each Phi, and its used operands. Make sure that 13546948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // if there is recursion in Phi, we won't generate hardware loops. 13556948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (int i = 1, n = Phi->getNumOperands(); i < n; i += 2) 13566948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (isLoopFeeder(L, MBB, Phi, &(Phi->getOperand(i)), LoopFeederPhi)) 13576948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (loopCountMayWrapOrUnderFlow(&(Phi->getOperand(i)), EndVal, 13586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Phi->getParent(), L, LoopFeederPhi)) 13596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 13606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 13616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 13626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 13636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// Return true if the induction variable can underflow in the first iteration. 13646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// An example, is an initial unsigned value that is 0 and is decrement in the 13656948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// first itertion of a do-while loop. In this case, we cannot generate a 13666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// hardware loop because the endloop instruction does not decrement the loop 13676948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// counter if it is <= 1. We only need to perform this analysis if the 13686948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// initial value is a register. 13696948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// 13706948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// This function assumes the initial value may underfow unless proven 13716948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// otherwise. If the type is signed, then we don't care because signed 13726948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// underflow is undefined. We attempt to prove the initial value is not 13736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// zero by perfoming a crude analysis of the loop counter. This function 13746948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// checks if the initial value is used in any comparison prior to the loop 13756948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// and, if so, assumes the comparison is a range check. This is inexact, 13766948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar/// but will catch the simple cases. 13776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow( 13786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand *InitVal, const MachineOperand *EndVal, 13796948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *MBB, MachineLoop *L, 13806948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LoopFeederMap &LoopFeederPhi) const { 13816948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Only check register values since they are unknown. 13826948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!InitVal->isReg()) 13836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 13846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 13856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!EndVal->isImm()) 13866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 13876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 13886948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // A register value that is assigned an immediate is a known value, and it 13896948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // won't underflow in the first iteration. 13906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t Imm; 13916948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (checkForImmediate(*InitVal, Imm)) 13926948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return (EndVal->getImm() == Imm); 13936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 13946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned Reg = InitVal->getReg(); 13956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 13966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // We don't know the value of a physical register. 13976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!TargetRegisterInfo::isVirtualRegister(Reg)) 13986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 13996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstr *Def = MRI->getVRegDef(Reg); 14016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Def) 14026948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 1403b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 14046948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // If the initial value is a Phi or copy and the operands may not underflow, 14056948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // then the definition cannot be underflow either. 14066948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(), 14076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar L, LoopFeederPhi)) 14086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 14096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)), 14106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar EndVal, Def->getParent(), 14116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar L, LoopFeederPhi)) 14126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 14136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Iterate over the uses of the initial value. If the initial value is used 14156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // in a compare, then we assume this is a range check that ensures the loop 14166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // doesn't underflow. This is not an exact test and should be improved. 14176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg), 14186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar E = MRI->use_instr_nodbg_end(); I != E; ++I) { 14196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstr *MI = &*I; 14206948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned CmpReg1 = 0, CmpReg2 = 0; 14216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int CmpMask = 0, CmpValue = 0; 14226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1423de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!TII->analyzeCompare(*MI, CmpReg1, CmpReg2, CmpMask, CmpValue)) 14246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar continue; 14256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *TBB = 0, *FBB = 0; 14276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<MachineOperand, 2> Cond; 1428de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (TII->analyzeBranch(*MI->getParent(), TBB, FBB, Cond, false)) 14296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar continue; 14306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Comparison::Kind Cmp = getComparisonKind(MI->getOpcode(), 0, 0, 0); 14326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Cmp == 0) 14336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar continue; 14346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB)) 14356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::getNegatedComparison(Cmp); 14366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (CmpReg2 != 0 && CmpReg2 == Reg) 14376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Cmp = Comparison::getSwappedComparison(Cmp); 14386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14396948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Signed underflow is undefined. 14406948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Comparison::isSigned(Cmp)) 14416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 14426948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1443f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Check if there is a comparison of the initial value. If the initial value 14446948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // is greater than or not equal to another value, then assume this is a 14456948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // range check. 14466948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if ((Cmp & Comparison::G) || Cmp == Comparison::NE) 14476948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 14486948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 14496948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14506948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // OK - this is a hack that needs to be improved. We really need to analyze 14516948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // the instructions performed on the initial value. This works on the simplest 14526948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // cases only. 14536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Def->isCopy() && !Def->isPHI()) 14546948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 14556948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14566948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 14576948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 14586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarbool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO, 14606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t &Val) const { 14616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (MO.isImm()) { 14626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Val = MO.getImm(); 14636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 14646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 14656948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!MO.isReg()) 14666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 14676948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14686948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // MO is a register. Check whether it is defined as an immediate value, 14696948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // and if so, get the value of it in TV. That value will then need to be 14706948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // processed to handle potential subregisters in MO. 14716948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t TV; 14726948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 14736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned R = MO.getReg(); 14746948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!TargetRegisterInfo::isVirtualRegister(R)) 14756948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 147671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *DI = MRI->getVRegDef(R); 147771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned DOpc = DI->getOpcode(); 147871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek switch (DOpc) { 14796948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case TargetOpcode::COPY: 1480ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::A2_tfrsi: 1481ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines case Hexagon::A2_tfrpi: 148271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek case Hexagon::CONST32_Int_Real: 14836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::CONST64_Int_Real: { 14846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Call recursively to avoid an extra check whether operand(1) is 14856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // indeed an immediate (it could be a global address, for example), 14866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // plus we can handle COPY at the same time. 14876948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!checkForImmediate(DI->getOperand(1), TV)) 14886948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 14896948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 14906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 14916948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::A2_combineii: 14926948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::A4_combineir: 14936948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::A4_combineii: 14946948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::A4_combineri: 14956948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::A2_combinew: { 14966948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand &S1 = DI->getOperand(1); 14976948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand &S2 = DI->getOperand(2); 14986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t V1, V2; 14996948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2)) 15006948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 15016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar TV = V2 | (V1 << 32); 15026948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 15036948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 15046948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case TargetOpcode::REG_SEQUENCE: { 15056948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand &S1 = DI->getOperand(1); 15066948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar const MachineOperand &S3 = DI->getOperand(3); 15076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t V1, V3; 15086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3)) 15096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 15106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned Sub2 = DI->getOperand(2).getImm(); 15116948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned Sub4 = DI->getOperand(4).getImm(); 15126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Sub2 == Hexagon::subreg_loreg && Sub4 == Hexagon::subreg_hireg) 15136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar TV = V1 | (V3 << 32); 15146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else if (Sub2 == Hexagon::subreg_hireg && Sub4 == Hexagon::subreg_loreg) 15156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar TV = V3 | (V1 << 32); 15166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else 15176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar llvm_unreachable("Unexpected form of REG_SEQUENCE"); 15186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 15196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1520b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 15216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar default: 15226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 15236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 152471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 15256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // By now, we should have successfuly obtained the immediate value defining 15266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // the register referenced in MO. Handle a potential use of a subregister. 15276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar switch (MO.getSubReg()) { 15286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::subreg_loreg: 15296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Val = TV & 0xFFFFFFFFULL; 15306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 15316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar case Hexagon::subreg_hireg: 15326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Val = (TV >> 32) & 0xFFFFFFFFULL; 15336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 15346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar default: 15356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Val = TV; 15366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar break; 15376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 15386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 153971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 154071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 154171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekvoid HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) { 154271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isImm()) { 154371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MO.setImm(Val); 154471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return; 154571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 154671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 154771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(MO.isReg()); 154871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned R = MO.getReg(); 15496948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstr *DI = MRI->getVRegDef(R); 155071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 155171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const TargetRegisterClass *RC = MRI->getRegClass(R); 155271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned NewR = MRI->createVirtualRegister(RC); 155371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock &B = *DI->getParent(); 155471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DebugLoc DL = DI->getDebugLoc(); 15556948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val); 155671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MO.setReg(NewR); 155771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek} 155871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 15596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainarstatic bool isImmValidForOpcode(unsigned CmpOpc, int64_t Imm) { 15606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // These two instructions are not extendable. 15616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (CmpOpc == Hexagon::A4_cmpbeqi) 15626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return isUInt<8>(Imm); 15636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (CmpOpc == Hexagon::A4_cmpbgti) 15646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return isInt<8>(Imm); 15656948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // The rest of the comparison-with-immediate instructions are extendable. 15666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 15676948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar} 156871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 156971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszekbool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) { 157071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Header = L->getHeader(); 157171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Latch = L->getLoopLatch(); 15726948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *ExitingBlock = getExitingBlock(L); 157371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 15746948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!(Header && Latch && ExitingBlock)) 157571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 157671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 157771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // These data structures follow the same concept as the corresponding 157871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // ones in findInductionRegister (where some comments are). 157971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::pair<unsigned,int64_t> RegisterBump; 158071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::pair<unsigned,RegisterBump> RegisterInduction; 158171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::set<RegisterInduction> RegisterInductionSet; 158271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 158371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Register candidates for induction variables, with their associated bumps. 158471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek RegisterInductionSet IndRegs; 158571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 158671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Look for induction patterns: 158771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // vreg1 = PHI ..., [ latch, vreg2 ] 158871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // vreg2 = ADD vreg1, imm 158971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineBasicBlock::instr_iterator instr_iterator; 159071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 159171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E && I->isPHI(); ++I) { 159271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *Phi = &*I; 159371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 159471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Have a PHI instruction. 159571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) { 159671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Phi->getOperand(i+1).getMBB() != Latch) 159771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 159871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 159971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PhiReg = Phi->getOperand(i).getReg(); 160071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *DI = MRI->getVRegDef(PhiReg); 160171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned UpdOpc = DI->getOpcode(); 16026948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool isAdd = (UpdOpc == Hexagon::A2_addi || UpdOpc == Hexagon::A2_addp); 160371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 160471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (isAdd) { 160571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If the register operand to the add/sub is the PHI we are looking 160671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // at, this meets the induction pattern. 160771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned IndReg = DI->getOperand(1).getReg(); 16086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineOperand &Opnd2 = DI->getOperand(2); 16096948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar int64_t V; 16106948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) { 161171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned UpdReg = DI->getOperand(0).getReg(); 161271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V))); 1613b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1614b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 161571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } // for (i) 161671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } // for (instr) 161771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 161871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (IndRegs.empty()) 161971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 162071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1621dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TB = nullptr, *FB = nullptr; 162271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,2> Cond; 162371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // AnalyzeBranch returns true if it fails to analyze branch. 1624de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool NotAnalyzed = TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false); 16256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (NotAnalyzed || Cond.empty()) 162671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 162771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 16286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (ExitingBlock != Latch && (TB == Latch || FB == Latch)) { 16296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *LTB = 0, *LFB = 0; 16306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar SmallVector<MachineOperand,2> LCond; 1631de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool NotAnalyzed = TII->analyzeBranch(*Latch, LTB, LFB, LCond, false); 16326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (NotAnalyzed) 16336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 163471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 16356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Since latch is not the exiting block, the latch branch should be an 16366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // unconditional branch to the loop header. 16376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (TB == Latch) 16386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar TB = (LTB == Header) ? LTB : LFB; 16396948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar else 16406948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar FB = (LTB == Header) ? LTB : LFB; 16416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 16426948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (TB != Header) { 16436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (FB != Header) { 16446948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // The latch/exit block does not go back to the header. 16456948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 16466948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 16476948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // FB is the header (i.e., uncond. jump to branch header) 16486948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // In this case, the LoopBody -> TB should not be a back edge otherwise 16496948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // it could result in an infinite loop after conversion to hw_loop. 16506948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // This case can happen when the Latch has two jumps like this: 16516948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Jmp_c OuterLoopHeader <-- TB 16526948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Jmp InnerLoopHeader <-- FB 16536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (MDT->dominates(TB, FB)) 16546948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 16556948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 165671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 165771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Expecting a predicate register as a condition. It won't be a hardware 165871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // predicate register at this point yet, just a vreg. 165971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // HexagonInstrInfo::AnalyzeBranch for negated branches inserts imm(0) 166071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // into Cond, followed by the predicate register. For non-negated branches 166171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // it's just the register. 166271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned CSz = Cond.size(); 166371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CSz != 1 && CSz != 2) 166471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 166571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 16666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Cond[CSz-1].isReg()) 16676948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 16686948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 166971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned P = Cond[CSz-1].getReg(); 167071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *PredDef = MRI->getVRegDef(P); 167171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 167271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!PredDef->isCompare()) 167371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 167471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 167571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallSet<unsigned,2> CmpRegs; 1676dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineOperand *CmpImmOp = nullptr; 167771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 167871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Go over all operands to the compare and look for immediate and register 167971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // operands. Assume that if the compare has a single register use and a 168071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // single immediate operand, then the register is being compared with the 168171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // immediate value. 168271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) { 168371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineOperand &MO = PredDef->getOperand(i); 168471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isReg()) { 168571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Skip all implicit references. In one case there was: 168671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // %vreg140<def> = FCMPUGT32_rr %vreg138, %vreg139, %USR<imp-use> 168771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isImplicit()) 168871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 168971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isUse()) { 16906948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!isImmediate(MO)) { 169171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpRegs.insert(MO.getReg()); 169271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 169371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 169471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Consider the register to be the "immediate" operand. 169571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpImmOp) 169671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 169771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpImmOp = &MO; 169871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 169971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } else if (MO.isImm()) { 170071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpImmOp) // A second immediate argument? Confusing. Bail out. 170171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 170271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpImmOp = &MO; 1703b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1704b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } 1705b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 170671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpRegs.empty()) 170771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 170871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 170971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Check if the compared register follows the order we want. Fix if needed. 171071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (RegisterInductionSet::iterator I = IndRegs.begin(), E = IndRegs.end(); 171171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E; ++I) { 171271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // This is a success. If the register used in the comparison is one that 171371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // we have identified as a bumped (updated) induction register, there is 171471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // nothing to do. 171571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpRegs.count(I->first)) 171671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 171771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 171871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Otherwise, if the register being compared comes out of a PHI node, 171971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // and has been recognized as following the induction pattern, and is 172071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // compared against an immediate, we can fix it. 172171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const RegisterBump &RB = I->second; 172271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (CmpRegs.count(RB.first)) { 17236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!CmpImmOp) { 17246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // If both operands to the compare instruction are registers, see if 17256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // it can be changed to use induction register as one of the operands. 17266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstr *IndI = nullptr; 17276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineInstr *nonIndI = nullptr; 17286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineOperand *IndMO = nullptr; 17296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineOperand *nonIndMO = nullptr; 17306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 17316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (unsigned i = 1, n = PredDef->getNumOperands(); i < n; ++i) { 17326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineOperand &MO = PredDef->getOperand(i); 17336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (MO.isReg() && MO.getReg() == RB.first) { 17346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG(dbgs() << "\n DefMI(" << i << ") = " 17356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar << *(MRI->getVRegDef(I->first))); 17366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (IndI) 17376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 17386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 17396948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar IndI = MRI->getVRegDef(I->first); 17406948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar IndMO = &MO; 17416948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else if (MO.isReg()) { 17426948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar DEBUG(dbgs() << "\n DefMI(" << i << ") = " 17436948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar << *(MRI->getVRegDef(MO.getReg()))); 17446948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (nonIndI) 17456948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 17466948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 17476948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar nonIndI = MRI->getVRegDef(MO.getReg()); 17486948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar nonIndMO = &MO; 17496948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 17506948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 17516948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (IndI && nonIndI && 17526948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar nonIndI->getOpcode() == Hexagon::A2_addi && 17536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar nonIndI->getOperand(2).isImm() && 17546948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar nonIndI->getOperand(2).getImm() == - RB.second) { 17556948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar bool Order = orderBumpCompare(IndI, PredDef); 17566948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Order) { 17576948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar IndMO->setReg(I->first); 17586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar nonIndMO->setReg(nonIndI->getOperand(1).getReg()); 17596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return true; 17606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 17616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 176271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 17636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 176471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 17656948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // It is not valid to do this transformation on an unsigned comparison 17666948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // because it may underflow. 17676948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Comparison::Kind Cmp = getComparisonKind(PredDef->getOpcode(), 0, 0, 0); 17686948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Cmp || Comparison::isUnsigned(Cmp)) 17696948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 17706948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 17716948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // If the register is being compared against an immediate, try changing 17726948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // the compare instruction to use induction register and adjust the 17736948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // immediate operand. 177471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t CmpImm = getImmediate(*CmpImmOp); 177571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek int64_t V = RB.second; 17766948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Handle Overflow (64-bit). 17776948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (((V > 0) && (CmpImm > INT64_MAX - V)) || 17786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar ((V < 0) && (CmpImm < INT64_MIN - V))) 177971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 178071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek CmpImm += V; 17816948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Most comparisons of register against an immediate value allow 17826948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // the immediate to be constant-extended. There are some exceptions 17836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // though. Make sure the new combination will work. 17846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (CmpImmOp->isImm()) 17856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!isImmValidForOpcode(PredDef->getOpcode(), CmpImm)) 17866948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return false; 178771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 178871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Make sure that the compare happens after the bump. Otherwise, 178971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // after the fixup, the compare would use a yet-undefined register. 179071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *BumpI = MRI->getVRegDef(I->first); 179171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek bool Order = orderBumpCompare(BumpI, PredDef); 179271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!Order) 179371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 179471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 179571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Finally, fix the compare instruction. 179671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek setImmediate(*CmpImmOp, CmpImm); 179771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 0, n = PredDef->getNumOperands(); i < n; ++i) { 179871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineOperand &MO = PredDef->getOperand(i); 179971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.isReg() && MO.getReg() == RB.first) { 180071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MO.setReg(I->first); 180171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return true; 180271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 180371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 180471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 180571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 1806b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 180771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return false; 1808b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1809b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum 181071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek/// \brief Create a preheader for a given loop. 181171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof ParzyszekMachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop( 181271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineLoop *L) { 181371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MachineBasicBlock *TmpPH = L->getLoopPreheader()) 181471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return TmpPH; 181571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 18166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!HWCreatePreheader) 18176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 18186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 181971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Header = L->getHeader(); 182071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *Latch = L->getLoopLatch(); 18216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineBasicBlock *ExitingBlock = getExitingBlock(L); 182271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineFunction *MF = Header->getParent(); 182371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek DebugLoc DL; 182471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 18256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar#ifndef NDEBUG 18266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if ((PHFn != "") && (PHFn != MF->getName())) 18276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 18286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar#endif 18296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 18306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Latch || !ExitingBlock || Header->hasAddressTaken()) 1831dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 183271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 183371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef MachineBasicBlock::instr_iterator instr_iterator; 183471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 183571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Verify that all existing predecessors have analyzable branches 183671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // (or no branches at all). 183771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek typedef std::vector<MachineBasicBlock*> MBBVector; 183871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MBBVector Preds(Header->pred_begin(), Header->pred_end()); 183971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,2> Tmp1; 1840dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TB = nullptr, *FB = nullptr; 184171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1842de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (TII->analyzeBranch(*ExitingBlock, TB, FB, Tmp1, false)) 1843dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 184471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 184571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) { 184671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PB = *I; 1847de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp1, false); 18486948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (NotAnalyzed) 18496948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar return nullptr; 185071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 185171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 185271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *NewPH = MF->CreateMachineBasicBlock(); 1853f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar MF->insert(Header->getIterator(), NewPH); 185471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 185571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (Header->pred_size() > 2) { 185671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Ensure that the header has only two predecessors: the preheader and 185771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the loop latch. Any additional predecessors of the header should 18586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // join at the newly created preheader. Inspect all PHI nodes from the 185971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // header and create appropriate corresponding PHI nodes in the preheader. 186071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 186171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 186271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E && I->isPHI(); ++I) { 186371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *PN = &*I; 186471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 186571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const MCInstrDesc &PD = TII->get(TargetOpcode::PHI); 186671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *NewPN = MF->CreateMachineInstr(PD, DL); 186771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPH->insert(NewPH->end(), NewPN); 186871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 186971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PR = PN->getOperand(0).getReg(); 187071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek const TargetRegisterClass *RC = MRI->getRegClass(PR); 187171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned NewPR = MRI->createVirtualRegister(RC); 187271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPN->addOperand(MachineOperand::CreateReg(NewPR, true)); 187371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 187471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Copy all non-latch operands of a header's PHI node to the newly 187571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // created PHI node in the preheader. 187671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) { 187771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek unsigned PredR = PN->getOperand(i).getReg(); 18786948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar unsigned PredRSub = PN->getOperand(i).getSubReg(); 187971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB(); 188071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PredB == Latch) 188171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek continue; 188271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 18836948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineOperand MO = MachineOperand::CreateReg(PredR, false); 18846948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MO.setSubReg(PredRSub); 18856948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar NewPN->addOperand(MO); 188671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPN->addOperand(MachineOperand::CreateMBB(PredB)); 188771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 188871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 188971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Remove copied operands from the old PHI node and add the value 189071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // coming from the preheader's PHI. 189171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (int i = PN->getNumOperands()-2; i > 0; i -= 2) { 189271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PredB = PN->getOperand(i+1).getMBB(); 189371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PredB != Latch) { 189471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PN->RemoveOperand(i+1); 189571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PN->RemoveOperand(i); 189671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 189771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 189871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PN->addOperand(MachineOperand::CreateReg(NewPR, false)); 189971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PN->addOperand(MachineOperand::CreateMBB(NewPH)); 190071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 190171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1902b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum } else { 190371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert(Header->pred_size() == 2); 190471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 190571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // The header has only two predecessors, but the non-latch predecessor 190671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // is not a preheader (e.g. it has other successors, etc.) 190771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // In such a case we don't need any extra PHI nodes in the new preheader, 190871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // all we need is to adjust existing PHIs in the header to now refer to 190971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // the new preheader. 191071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (instr_iterator I = Header->instr_begin(), E = Header->instr_end(); 191171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek I != E && I->isPHI(); ++I) { 191271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineInstr *PN = &*I; 191371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (unsigned i = 1, n = PN->getNumOperands(); i < n; i += 2) { 191471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineOperand &MO = PN->getOperand(i+1); 191571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (MO.getMBB() != Latch) 191671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MO.setMBB(NewPH); 191771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 191871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 191971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 192071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 192171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // "Reroute" the CFG edges to link in the new preheader. 192271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // If any of the predecessors falls through to the header, insert a branch 192371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // to the new preheader in that place. 192471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,1> Tmp2; 192571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek SmallVector<MachineOperand,1> EmptyCond; 192671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 1927dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TB = FB = nullptr; 192871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 192971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek for (MBBVector::iterator I = Preds.begin(), E = Preds.end(); I != E; ++I) { 193071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek MachineBasicBlock *PB = *I; 193171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (PB != Latch) { 193271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek Tmp2.clear(); 1933de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool NotAnalyzed = TII->analyzeBranch(*PB, TB, FB, Tmp2, false); 193436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (void)NotAnalyzed; // suppress compiler warning 193571490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (!NotAnalyzed && "Should be analyzable!"); 193671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (TB != Header && (Tmp2.empty() || FB != Header)) 1937dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TII->InsertBranch(*PB, NewPH, nullptr, EmptyCond, DL); 193871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek PB->ReplaceUsesOfBlockWith(Header, NewPH); 193971490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 194071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek } 194171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 194271490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // It can happen that the latch block will fall through into the header. 194371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Insert an unconditional branch to the header. 1944dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TB = FB = nullptr; 1945de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool LatchNotAnalyzed = TII->analyzeBranch(*Latch, TB, FB, Tmp2, false); 194636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (void)LatchNotAnalyzed; // suppress compiler warning 194771490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek assert (!LatchNotAnalyzed && "Should be analyzable!"); 194871490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek if (!TB && !FB) 1949dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TII->InsertBranch(*Latch, Header, nullptr, EmptyCond, DL); 195071490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 195171490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek // Finally, the branch from the preheader to the header. 1952dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TII->InsertBranch(*NewPH, Header, nullptr, EmptyCond, DL); 195371490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek NewPH->addSuccessor(Header); 195471490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek 19556948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineLoop *ParentLoop = L->getParentLoop(); 19566948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (ParentLoop) 19576948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar ParentLoop->addBasicBlockToLoop(NewPH, MLI->getBase()); 19586948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 19596948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Update the dominator information with the new preheader. 19606948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (MDT) { 19616948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MachineDomTreeNode *HDom = MDT->getNode(Header); 19626948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MDT->addNewBlock(NewPH, HDom->getIDom()->getBlock()); 19636948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar MDT->changeImmediateDominator(Header, NewPH); 19646948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 19656948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 196671490fa946f750fb3afe7228a32d31d401d4c1d8Krzysztof Parzyszek return NewPH; 1967b4b54153ad760c69a00a08531abef4ed434a5092Tony Linthicum} 1968