//===--- HexagonGenPredicate.cpp ------------------------------------------===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "gen-pred" #include "llvm/ADT/SetVector.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" #include "HexagonTargetMachine.h" #include <functional> #include <queue> #include <set> #include <vector> using namespace llvm; namespace llvm { void initializeHexagonGenPredicatePass(PassRegistry& Registry); FunctionPass *createHexagonGenPredicate(); } namespace { struct Register { unsigned R, S; Register(unsigned r = 0, unsigned s = 0) : R(r), S(s) {} Register(const MachineOperand &MO) : R(MO.getReg()), S(MO.getSubReg()) {} bool operator== (const Register &Reg) const { return R == Reg.R && S == Reg.S; } bool operator< (const Register &Reg) const { return R < Reg.R || (R == Reg.R && S < Reg.S); } }; struct PrintRegister { PrintRegister(Register R, const TargetRegisterInfo &I) : Reg(R), TRI(I) {} friend raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR); private: Register Reg; const TargetRegisterInfo &TRI; }; raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR) LLVM_ATTRIBUTE_UNUSED; raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR) { return OS << PrintReg(PR.Reg.R, &PR.TRI, PR.Reg.S); } class HexagonGenPredicate : public MachineFunctionPass { public: static char ID; HexagonGenPredicate() : MachineFunctionPass(ID), TII(0), TRI(0), MRI(0) { initializeHexagonGenPredicatePass(*PassRegistry::getPassRegistry()); } virtual const char *getPassName() const { return "Hexagon generate predicate operations"; } virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired<MachineDominatorTree>(); AU.addPreserved<MachineDominatorTree>(); MachineFunctionPass::getAnalysisUsage(AU); } virtual bool runOnMachineFunction(MachineFunction &MF); private: typedef SetVector<MachineInstr*> VectOfInst; typedef std::set<Register> SetOfReg; typedef std::map<Register,Register> RegToRegMap; const HexagonInstrInfo *TII; const HexagonRegisterInfo *TRI; MachineRegisterInfo *MRI; SetOfReg PredGPRs; VectOfInst PUsers; RegToRegMap G2P; bool isPredReg(unsigned R); void collectPredicateGPR(MachineFunction &MF); void processPredicateGPR(const Register &Reg); unsigned getPredForm(unsigned Opc); bool isConvertibleToPredForm(const MachineInstr *MI); bool isScalarCmp(unsigned Opc); bool isScalarPred(Register PredReg); Register getPredRegFor(const Register &Reg); bool convertToPredForm(MachineInstr *MI); bool eliminatePredCopies(MachineFunction &MF); }; char HexagonGenPredicate::ID = 0; } INITIALIZE_PASS_BEGIN(HexagonGenPredicate, "hexagon-gen-pred", "Hexagon generate predicate operations", false, false) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) INITIALIZE_PASS_END(HexagonGenPredicate, "hexagon-gen-pred", "Hexagon generate predicate operations", false, false) bool HexagonGenPredicate::isPredReg(unsigned R) { if (!TargetRegisterInfo::isVirtualRegister(R)) return false; const TargetRegisterClass *RC = MRI->getRegClass(R); return RC == &Hexagon::PredRegsRegClass; } unsigned HexagonGenPredicate::getPredForm(unsigned Opc) { using namespace Hexagon; switch (Opc) { case A2_and: case A2_andp: return C2_and; case A4_andn: case A4_andnp: return C2_andn; case M4_and_and: return C4_and_and; case M4_and_andn: return C4_and_andn; case M4_and_or: return C4_and_or; case A2_or: case A2_orp: return C2_or; case A4_orn: case A4_ornp: return C2_orn; case M4_or_and: return C4_or_and; case M4_or_andn: return C4_or_andn; case M4_or_or: return C4_or_or; case A2_xor: case A2_xorp: return C2_xor; case C2_tfrrp: return COPY; } // The opcode corresponding to 0 is TargetOpcode::PHI. We can use 0 here // to denote "none", but we need to make sure that none of the valid opcodes // that we return will ever be 0. assert(PHI == 0 && "Use different value for <none>"); return 0; } bool HexagonGenPredicate::isConvertibleToPredForm(const MachineInstr *MI) { unsigned Opc = MI->getOpcode(); if (getPredForm(Opc) != 0) return true; // Comparisons against 0 are also convertible. This does not apply to // A4_rcmpeqi or A4_rcmpneqi, since they produce values 0 or 1, which // may not match the value that the predicate register would have if // it was converted to a predicate form. switch (Opc) { case Hexagon::C2_cmpeqi: case Hexagon::C4_cmpneqi: if (MI->getOperand(2).isImm() && MI->getOperand(2).getImm() == 0) return true; break; } return false; } void HexagonGenPredicate::collectPredicateGPR(MachineFunction &MF) { for (MachineFunction::iterator A = MF.begin(), Z = MF.end(); A != Z; ++A) { MachineBasicBlock &B = *A; for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) { MachineInstr *MI = &*I; unsigned Opc = MI->getOpcode(); switch (Opc) { case Hexagon::C2_tfrpr: case TargetOpcode::COPY: if (isPredReg(MI->getOperand(1).getReg())) { Register RD = MI->getOperand(0); if (TargetRegisterInfo::isVirtualRegister(RD.R)) PredGPRs.insert(RD); } break; } } } } void HexagonGenPredicate::processPredicateGPR(const Register &Reg) { DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": " << PrintReg(Reg.R, TRI, Reg.S) << "\n"); typedef MachineRegisterInfo::use_iterator use_iterator; use_iterator I = MRI->use_begin(Reg.R), E = MRI->use_end(); if (I == E) { DEBUG(dbgs() << "Dead reg: " << PrintReg(Reg.R, TRI, Reg.S) << '\n'); MachineInstr *DefI = MRI->getVRegDef(Reg.R); DefI->eraseFromParent(); return; } for (; I != E; ++I) { MachineInstr *UseI = I->getParent(); if (isConvertibleToPredForm(UseI)) PUsers.insert(UseI); } } Register HexagonGenPredicate::getPredRegFor(const Register &Reg) { // Create a predicate register for a given Reg. The newly created register // will have its value copied from Reg, so that it can be later used as // an operand in other instructions. assert(TargetRegisterInfo::isVirtualRegister(Reg.R)); RegToRegMap::iterator F = G2P.find(Reg); if (F != G2P.end()) return F->second; DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": " << PrintRegister(Reg, *TRI)); MachineInstr *DefI = MRI->getVRegDef(Reg.R); assert(DefI); unsigned Opc = DefI->getOpcode(); if (Opc == Hexagon::C2_tfrpr || Opc == TargetOpcode::COPY) { assert(DefI->getOperand(0).isDef() && DefI->getOperand(1).isUse()); Register PR = DefI->getOperand(1); G2P.insert(std::make_pair(Reg, PR)); DEBUG(dbgs() << " -> " << PrintRegister(PR, *TRI) << '\n'); return PR; } MachineBasicBlock &B = *DefI->getParent(); DebugLoc DL = DefI->getDebugLoc(); const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; unsigned NewPR = MRI->createVirtualRegister(PredRC); // For convertible instructions, do not modify them, so that they can // be converted later. Generate a copy from Reg to NewPR. if (isConvertibleToPredForm(DefI)) { MachineBasicBlock::iterator DefIt = DefI; BuildMI(B, std::next(DefIt), DL, TII->get(TargetOpcode::COPY), NewPR) .addReg(Reg.R, 0, Reg.S); G2P.insert(std::make_pair(Reg, Register(NewPR))); DEBUG(dbgs() << " -> !" << PrintRegister(Register(NewPR), *TRI) << '\n'); return Register(NewPR); } llvm_unreachable("Invalid argument"); } bool HexagonGenPredicate::isScalarCmp(unsigned Opc) { switch (Opc) { case Hexagon::C2_cmpeq: case Hexagon::C2_cmpgt: case Hexagon::C2_cmpgtu: case Hexagon::C2_cmpeqp: case Hexagon::C2_cmpgtp: case Hexagon::C2_cmpgtup: case Hexagon::C2_cmpeqi: case Hexagon::C2_cmpgti: case Hexagon::C2_cmpgtui: case Hexagon::C2_cmpgei: case Hexagon::C2_cmpgeui: case Hexagon::C4_cmpneqi: case Hexagon::C4_cmpltei: case Hexagon::C4_cmplteui: case Hexagon::C4_cmpneq: case Hexagon::C4_cmplte: case Hexagon::C4_cmplteu: case Hexagon::A4_cmpbeq: case Hexagon::A4_cmpbeqi: case Hexagon::A4_cmpbgtu: case Hexagon::A4_cmpbgtui: case Hexagon::A4_cmpbgt: case Hexagon::A4_cmpbgti: case Hexagon::A4_cmpheq: case Hexagon::A4_cmphgt: case Hexagon::A4_cmphgtu: case Hexagon::A4_cmpheqi: case Hexagon::A4_cmphgti: case Hexagon::A4_cmphgtui: return true; } return false; } bool HexagonGenPredicate::isScalarPred(Register PredReg) { std::queue<Register> WorkQ; WorkQ.push(PredReg); while (!WorkQ.empty()) { Register PR = WorkQ.front(); WorkQ.pop(); const MachineInstr *DefI = MRI->getVRegDef(PR.R); if (!DefI) return false; unsigned DefOpc = DefI->getOpcode(); switch (DefOpc) { case TargetOpcode::COPY: { const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; if (MRI->getRegClass(PR.R) != PredRC) return false; // If it is a copy between two predicate registers, fall through. } case Hexagon::C2_and: case Hexagon::C2_andn: case Hexagon::C4_and_and: case Hexagon::C4_and_andn: case Hexagon::C4_and_or: case Hexagon::C2_or: case Hexagon::C2_orn: case Hexagon::C4_or_and: case Hexagon::C4_or_andn: case Hexagon::C4_or_or: case Hexagon::C4_or_orn: case Hexagon::C2_xor: // Add operands to the queue. for (ConstMIOperands Mo(DefI); Mo.isValid(); ++Mo) if (Mo->isReg() && Mo->isUse()) WorkQ.push(Register(Mo->getReg())); break; // All non-vector compares are ok, everything else is bad. default: return isScalarCmp(DefOpc); } } return true; } bool HexagonGenPredicate::convertToPredForm(MachineInstr *MI) { DEBUG(dbgs() << LLVM_FUNCTION_NAME << ": " << MI << " " << *MI); unsigned Opc = MI->getOpcode(); assert(isConvertibleToPredForm(MI)); unsigned NumOps = MI->getNumOperands(); for (unsigned i = 0; i < NumOps; ++i) { MachineOperand &MO = MI->getOperand(i); if (!MO.isReg() || !MO.isUse()) continue; Register Reg(MO); if (Reg.S && Reg.S != Hexagon::subreg_loreg) return false; if (!PredGPRs.count(Reg)) return false; } MachineBasicBlock &B = *MI->getParent(); DebugLoc DL = MI->getDebugLoc(); unsigned NewOpc = getPredForm(Opc); // Special case for comparisons against 0. if (NewOpc == 0) { switch (Opc) { case Hexagon::C2_cmpeqi: NewOpc = Hexagon::C2_not; break; case Hexagon::C4_cmpneqi: NewOpc = TargetOpcode::COPY; break; default: return false; } // If it's a scalar predicate register, then all bits in it are // the same. Otherwise, to determine whether all bits are 0 or not // we would need to use any8. Register PR = getPredRegFor(MI->getOperand(1)); if (!isScalarPred(PR)) return false; // This will skip the immediate argument when creating the predicate // version instruction. NumOps = 2; } // Some sanity: check that def is in operand #0. MachineOperand &Op0 = MI->getOperand(0); assert(Op0.isDef()); Register OutR(Op0); // Don't use getPredRegFor, since it will create an association between // the argument and a created predicate register (i.e. it will insert a // copy if a new predicate register is created). const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; Register NewPR = MRI->createVirtualRegister(PredRC); MachineInstrBuilder MIB = BuildMI(B, MI, DL, TII->get(NewOpc), NewPR.R); // Add predicate counterparts of the GPRs. for (unsigned i = 1; i < NumOps; ++i) { Register GPR = MI->getOperand(i); Register Pred = getPredRegFor(GPR); MIB.addReg(Pred.R, 0, Pred.S); } DEBUG(dbgs() << "generated: " << *MIB); // Generate a copy-out: NewGPR = NewPR, and replace all uses of OutR // with NewGPR. const TargetRegisterClass *RC = MRI->getRegClass(OutR.R); unsigned NewOutR = MRI->createVirtualRegister(RC); BuildMI(B, MI, DL, TII->get(TargetOpcode::COPY), NewOutR) .addReg(NewPR.R, 0, NewPR.S); MRI->replaceRegWith(OutR.R, NewOutR); MI->eraseFromParent(); // If the processed instruction was C2_tfrrp (i.e. Rn = Pm; Pk = Rn), // then the output will be a predicate register. Do not visit the // users of it. if (!isPredReg(NewOutR)) { Register R(NewOutR); PredGPRs.insert(R); processPredicateGPR(R); } return true; } bool HexagonGenPredicate::eliminatePredCopies(MachineFunction &MF) { DEBUG(dbgs() << LLVM_FUNCTION_NAME << "\n"); const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass; bool Changed = false; VectOfInst Erase; // First, replace copies // IntR = PredR1 // PredR2 = IntR // with // PredR2 = PredR1 // Such sequences can be generated when a copy-into-pred is generated from // a gpr register holding a result of a convertible instruction. After // the convertible instruction is converted, its predicate result will be // copied back into the original gpr. for (MachineFunction::iterator A = MF.begin(), Z = MF.end(); A != Z; ++A) { MachineBasicBlock &B = *A; for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) { if (I->getOpcode() != TargetOpcode::COPY) continue; Register DR = I->getOperand(0); Register SR = I->getOperand(1); if (!TargetRegisterInfo::isVirtualRegister(DR.R)) continue; if (!TargetRegisterInfo::isVirtualRegister(SR.R)) continue; if (MRI->getRegClass(DR.R) != PredRC) continue; if (MRI->getRegClass(SR.R) != PredRC) continue; assert(!DR.S && !SR.S && "Unexpected subregister"); MRI->replaceRegWith(DR.R, SR.R); Erase.insert(I); Changed = true; } } for (VectOfInst::iterator I = Erase.begin(), E = Erase.end(); I != E; ++I) (*I)->eraseFromParent(); return Changed; } bool HexagonGenPredicate::runOnMachineFunction(MachineFunction &MF) { TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo(); TRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo(); MRI = &MF.getRegInfo(); PredGPRs.clear(); PUsers.clear(); G2P.clear(); bool Changed = false; collectPredicateGPR(MF); for (SetOfReg::iterator I = PredGPRs.begin(), E = PredGPRs.end(); I != E; ++I) processPredicateGPR(*I); bool Again; do { Again = false; VectOfInst Processed, Copy; typedef VectOfInst::iterator iterator; Copy = PUsers; for (iterator I = Copy.begin(), E = Copy.end(); I != E; ++I) { MachineInstr *MI = *I; bool Done = convertToPredForm(MI); if (Done) { Processed.insert(MI); Again = true; } } Changed |= Again; auto Done = [Processed] (MachineInstr *MI) -> bool { return Processed.count(MI); }; PUsers.remove_if(Done); } while (Again); Changed |= eliminatePredCopies(MF); return Changed; } FunctionPass *llvm::createHexagonGenPredicate() { return new HexagonGenPredicate(); }