+/// This function assumes the initial value may underfow unless proven
+/// otherwise. If the type is signed, then we don't care because signed
+/// underflow is undefined. We attempt to prove the initial value is not
+/// zero by perfoming a crude analysis of the loop counter. This function
+/// checks if the initial value is used in any comparison prior to the loop
+/// and, if so, assumes the comparison is a range check. This is inexact,
+/// but will catch the simple cases.
+bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
+ const MachineOperand *InitVal, const MachineOperand *EndVal,
+ MachineBasicBlock *MBB, MachineLoop *L,
+ LoopFeederMap &LoopFeederPhi) const {
+ // Only check register values since they are unknown.
+ if (!InitVal->isReg())
+ return false;
+
+ if (!EndVal->isImm())
+ return false;
+
+ // A register value that is assigned an immediate is a known value, and it
+ // won't underflow in the first iteration.
+ int64_t Imm;
+ if (checkForImmediate(*InitVal, Imm))
+ return (EndVal->getImm() == Imm);
+
+ unsigned Reg = InitVal->getReg();
+
+ // We don't know the value of a physical register.
+ if (!TargetRegisterInfo::isVirtualRegister(Reg))
+ return true;
+
+ MachineInstr *Def = MRI->getVRegDef(Reg);
+ if (!Def)
+ return true;
+
+ // If the initial value is a Phi or copy and the operands may not underflow,
+ // then the definition cannot be underflow either.
+ if (Def->isPHI() && !phiMayWrapOrUnderflow(Def, EndVal, Def->getParent(),
+ L, LoopFeederPhi))
+ return false;
+ if (Def->isCopy() && !loopCountMayWrapOrUnderFlow(&(Def->getOperand(1)),
+ EndVal, Def->getParent(),
+ L, LoopFeederPhi))
+ return false;
+
+ // Iterate over the uses of the initial value. If the initial value is used
+ // in a compare, then we assume this is a range check that ensures the loop
+ // doesn't underflow. This is not an exact test and should be improved.
+ for (MachineRegisterInfo::use_instr_nodbg_iterator I = MRI->use_instr_nodbg_begin(Reg),
+ E = MRI->use_instr_nodbg_end(); I != E; ++I) {
+ MachineInstr *MI = &*I;
+ unsigned CmpReg1 = 0, CmpReg2 = 0;
+ int CmpMask = 0, CmpValue = 0;
+
+ if (!TII->analyzeCompare(MI, CmpReg1, CmpReg2, CmpMask, CmpValue))
+ continue;
+
+ MachineBasicBlock *TBB = 0, *FBB = 0;
+ SmallVector<MachineOperand, 2> Cond;
+ if (TII->AnalyzeBranch(*MI->getParent(), TBB, FBB, Cond, false))
+ continue;
+
+ Comparison::Kind Cmp = getComparisonKind(MI->getOpcode(), 0, 0, 0);
+ if (Cmp == 0)
+ continue;
+ if (TII->predOpcodeHasNot(Cond) ^ (TBB != MBB))
+ Cmp = Comparison::getNegatedComparison(Cmp);
+ if (CmpReg2 != 0 && CmpReg2 == Reg)
+ Cmp = Comparison::getSwappedComparison(Cmp);
+
+ // Signed underflow is undefined.
+ if (Comparison::isSigned(Cmp))
+ return false;
+
+ // Check if there is a comparison of the inital value. If the initial value
+ // is greater than or not equal to another value, then assume this is a
+ // range check.
+ if ((Cmp & Comparison::G) || Cmp == Comparison::NE)
+ return false;
+ }
+
+ // OK - this is a hack that needs to be improved. We really need to analyze
+ // the instructions performed on the initial value. This works on the simplest
+ // cases only.
+ if (!Def->isCopy() && !Def->isPHI())
+ return false;
+
+ return true;
+}
+
+bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
+ int64_t &Val) const {
+ if (MO.isImm()) {
+ Val = MO.getImm();
+ return true;
+ }
+ if (!MO.isReg())
+ return false;
+
+ // MO is a register. Check whether it is defined as an immediate value,
+ // and if so, get the value of it in TV. That value will then need to be
+ // processed to handle potential subregisters in MO.
+ int64_t TV;
+
+ unsigned R = MO.getReg();
+ if (!TargetRegisterInfo::isVirtualRegister(R))
+ return false;
+ MachineInstr *DI = MRI->getVRegDef(R);
+ unsigned DOpc = DI->getOpcode();
+ switch (DOpc) {
+ case TargetOpcode::COPY:
+ case Hexagon::A2_tfrsi:
+ case Hexagon::A2_tfrpi:
+ case Hexagon::CONST32_Int_Real:
+ case Hexagon::CONST64_Int_Real: {
+ // Call recursively to avoid an extra check whether operand(1) is
+ // indeed an immediate (it could be a global address, for example),
+ // plus we can handle COPY at the same time.
+ if (!checkForImmediate(DI->getOperand(1), TV))
+ return false;
+ break;
+ }
+ case Hexagon::A2_combineii:
+ case Hexagon::A4_combineir:
+ case Hexagon::A4_combineii:
+ case Hexagon::A4_combineri:
+ case Hexagon::A2_combinew: {
+ const MachineOperand &S1 = DI->getOperand(1);
+ const MachineOperand &S2 = DI->getOperand(2);
+ int64_t V1, V2;
+ if (!checkForImmediate(S1, V1) || !checkForImmediate(S2, V2))
+ return false;
+ TV = V2 | (V1 << 32);
+ break;
+ }
+ case TargetOpcode::REG_SEQUENCE: {
+ const MachineOperand &S1 = DI->getOperand(1);
+ const MachineOperand &S3 = DI->getOperand(3);
+ int64_t V1, V3;
+ if (!checkForImmediate(S1, V1) || !checkForImmediate(S3, V3))
+ return false;
+ unsigned Sub2 = DI->getOperand(2).getImm();
+ unsigned Sub4 = DI->getOperand(4).getImm();
+ if (Sub2 == Hexagon::subreg_loreg && Sub4 == Hexagon::subreg_hireg)
+ TV = V1 | (V3 << 32);
+ else if (Sub2 == Hexagon::subreg_hireg && Sub4 == Hexagon::subreg_loreg)
+ TV = V3 | (V1 << 32);
+ else
+ llvm_unreachable("Unexpected form of REG_SEQUENCE");
+ break;
+ }
+
+ default:
+ return false;
+ }
+
+ // By now, we should have successfuly obtained the immediate value defining
+ // the register referenced in MO. Handle a potential use of a subregister.
+ switch (MO.getSubReg()) {
+ case Hexagon::subreg_loreg:
+ Val = TV & 0xFFFFFFFFULL;
+ break;
+ case Hexagon::subreg_hireg:
+ Val = (TV >> 32) & 0xFFFFFFFFULL;
+ break;
+ default:
+ Val = TV;
+ break;
+ }
+ return true;
+}
+
+void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) {
+ if (MO.isImm()) {
+ MO.setImm(Val);
+ return;
+ }
+
+ assert(MO.isReg());
+ unsigned R = MO.getReg();
+ MachineInstr *DI = MRI->getVRegDef(R);
+
+ const TargetRegisterClass *RC = MRI->getRegClass(R);
+ unsigned NewR = MRI->createVirtualRegister(RC);
+ MachineBasicBlock &B = *DI->getParent();
+ DebugLoc DL = DI->getDebugLoc();
+ BuildMI(B, DI, DL, TII->get(DI->getOpcode()), NewR).addImm(Val);
+ MO.setReg(NewR);
+}
+
+static bool isImmValidForOpcode(unsigned CmpOpc, int64_t Imm) {
+ // These two instructions are not extendable.
+ if (CmpOpc == Hexagon::A4_cmpbeqi)
+ return isUInt<8>(Imm);
+ if (CmpOpc == Hexagon::A4_cmpbgti)
+ return isInt<8>(Imm);
+ // The rest of the comparison-with-immediate instructions are extendable.
+ return true;
+}
+
+bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
+ MachineBasicBlock *Header = L->getHeader();
+ MachineBasicBlock *Latch = L->getLoopLatch();
+ MachineBasicBlock *ExitingBlock = getExitingBlock(L);
+
+ if (!(Header && Latch && ExitingBlock))
+ return false;
+
+ // These data structures follow the same concept as the corresponding
+ // ones in findInductionRegister (where some comments are).
+ typedef std::pair<unsigned,int64_t> RegisterBump;
+ typedef std::pair<unsigned,RegisterBump> RegisterInduction;
+ typedef std::set<RegisterInduction> RegisterInductionSet;
+
+ // Register candidates for induction variables, with their associated bumps.
+ RegisterInductionSet IndRegs;
+
+ // Look for induction patterns:
+ // vreg1 = PHI ..., [ latch, vreg2 ]
+ // vreg2 = ADD vreg1, imm
+ typedef MachineBasicBlock::instr_iterator instr_iterator;
+ for (instr_iterator I = Header->instr_begin(), E = Header->instr_end();
+ I != E && I->isPHI(); ++I) {
+ MachineInstr *Phi = &*I;
+
+ // Have a PHI instruction.
+ for (unsigned i = 1, n = Phi->getNumOperands(); i < n; i += 2) {
+ if (Phi->getOperand(i+1).getMBB() != Latch)
+ continue;
+
+ unsigned PhiReg = Phi->getOperand(i).getReg();
+ MachineInstr *DI = MRI->getVRegDef(PhiReg);
+ unsigned UpdOpc = DI->getOpcode();
+ bool isAdd = (UpdOpc == Hexagon::A2_addi || UpdOpc == Hexagon::A2_addp);
+
+ if (isAdd) {
+ // If the register operand to the add/sub is the PHI we are looking
+ // at, this meets the induction pattern.
+ unsigned IndReg = DI->getOperand(1).getReg();
+ MachineOperand &Opnd2 = DI->getOperand(2);
+ int64_t V;
+ if (MRI->getVRegDef(IndReg) == Phi && checkForImmediate(Opnd2, V)) {
+ unsigned UpdReg = DI->getOperand(0).getReg();
+ IndRegs.insert(std::make_pair(UpdReg, std::make_pair(IndReg, V)));