diff --git a/llvm/lib/Target/Xtensa/XtensaInstrInfo.h b/llvm/lib/Target/Xtensa/XtensaInstrInfo.h --- a/llvm/lib/Target/Xtensa/XtensaInstrInfo.h +++ b/llvm/lib/Target/Xtensa/XtensaInstrInfo.h @@ -64,6 +64,33 @@ // physical register Reg. void loadImmediate(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, unsigned *Reg, int64_t Value) const; + bool + reverseBranchCondition(SmallVectorImpl &Cond) const override; + bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, + MachineBasicBlock *&FBB, + SmallVectorImpl &Cond, + bool AllowModify) const override; + unsigned removeBranch(MachineBasicBlock &MBB, + int *BytesRemoved = nullptr) const override; + unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, + MachineBasicBlock *FBB, ArrayRef Cond, + const DebugLoc &DL, + int *BytesAdded = nullptr) const override; + + unsigned InsertBranchAtInst(MachineBasicBlock &MBB, + MachineBasicBlock::iterator I, + MachineBasicBlock *TBB, + ArrayRef Cond, const DebugLoc &DL, + int *BytesAdded) const; + + // Return true if MI is a conditional or unconditional branch. + // When returning true, set Cond to the mask of condition-code + // values on which the instruction will branch, and set Target + // to the operand that contains the branch target. This target + // can be a register or a basic block. + bool isBranch(const MachineBasicBlock::iterator &MI, + SmallVectorImpl &Cond, + const MachineOperand *&Target) const; }; } // end namespace llvm diff --git a/llvm/lib/Target/Xtensa/XtensaInstrInfo.cpp b/llvm/lib/Target/Xtensa/XtensaInstrInfo.cpp --- a/llvm/lib/Target/Xtensa/XtensaInstrInfo.cpp +++ b/llvm/lib/Target/Xtensa/XtensaInstrInfo.cpp @@ -159,3 +159,301 @@ llvm_unreachable("Unsupported load immediate value"); } } + +bool XtensaInstrInfo::reverseBranchCondition( + SmallVectorImpl &Cond) const { + assert(Cond.size() <= 4 && "Invalid branch condition!"); + + switch (Cond[0].getImm()) { + case Xtensa::BEQ: + Cond[0].setImm(Xtensa::BNE); + return false; + case Xtensa::BNE: + Cond[0].setImm(Xtensa::BEQ); + return false; + case Xtensa::BLT: + Cond[0].setImm(Xtensa::BGE); + return false; + case Xtensa::BGE: + Cond[0].setImm(Xtensa::BLT); + return false; + case Xtensa::BLTU: + Cond[0].setImm(Xtensa::BGEU); + return false; + case Xtensa::BGEU: + Cond[0].setImm(Xtensa::BLTU); + return false; + + case Xtensa::BEQI: + Cond[0].setImm(Xtensa::BNEI); + return false; + case Xtensa::BNEI: + Cond[0].setImm(Xtensa::BEQI); + return false; + case Xtensa::BGEI: + Cond[0].setImm(Xtensa::BLTI); + return false; + case Xtensa::BLTI: + Cond[0].setImm(Xtensa::BGEI); + return false; + case Xtensa::BGEUI: + Cond[0].setImm(Xtensa::BLTUI); + return false; + case Xtensa::BLTUI: + Cond[0].setImm(Xtensa::BGEUI); + return false; + + case Xtensa::BEQZ: + Cond[0].setImm(Xtensa::BNEZ); + return false; + case Xtensa::BNEZ: + Cond[0].setImm(Xtensa::BEQZ); + return false; + case Xtensa::BLTZ: + Cond[0].setImm(Xtensa::BGEZ); + return false; + case Xtensa::BGEZ: + Cond[0].setImm(Xtensa::BLTZ); + return false; + + default: + llvm_unreachable("Invalid branch condition!"); + } +} + +bool XtensaInstrInfo::analyzeBranch(MachineBasicBlock &MBB, + MachineBasicBlock *&TBB, + MachineBasicBlock *&FBB, + SmallVectorImpl &Cond, + bool AllowModify = false) const { + // Most of the code and comments here are boilerplate. + + // Start from the bottom of the block and work up, examining the + // terminator instructions. + MachineBasicBlock::iterator I = MBB.end(); + while (I != MBB.begin()) { + --I; + if (I->isDebugValue()) + continue; + + // Working from the bottom, when we see a non-terminator instruction, we're + // done. + if (!isUnpredicatedTerminator(*I)) + break; + + // A terminator that isn't a branch can't easily be handled by this + // analysis. + SmallVector ThisCond; + ThisCond.push_back(MachineOperand::CreateImm(0)); + const MachineOperand *ThisTarget; + if (!isBranch(I, ThisCond, ThisTarget)) + return true; + + // Can't handle indirect branches. + if (!ThisTarget->isMBB()) + return true; + + if (ThisCond[0].getImm() == Xtensa::J) { + // Handle unconditional branches. + if (!AllowModify) { + TBB = ThisTarget->getMBB(); + continue; + } + + // If the block has any instructions after a JMP, delete them. + while (std::next(I) != MBB.end()) + std::next(I)->eraseFromParent(); + + Cond.clear(); + FBB = 0; + + // TBB is used to indicate the unconditinal destination. + TBB = ThisTarget->getMBB(); + continue; + } + + // Working from the bottom, handle the first conditional branch. + if (Cond.empty()) { + // FIXME: add X86-style branch swap + FBB = TBB; + TBB = ThisTarget->getMBB(); + Cond.push_back(MachineOperand::CreateImm(ThisCond[0].getImm())); + + // push remaining operands + for (unsigned int i = 0; i < (I->getNumExplicitOperands() - 1); i++) + Cond.push_back(I->getOperand(i)); + + continue; + } + + // Handle subsequent conditional branches. + assert(Cond.size() <= 4); + assert(TBB); + + // Only handle the case where all conditional branches branch to the same + // destination. + if (TBB != ThisTarget->getMBB()) + return true; + + // If the conditions are the same, we can leave them alone. + unsigned OldCond = Cond[0].getImm(); + if (OldCond == ThisCond[0].getImm()) + continue; + } + + return false; +} + +unsigned XtensaInstrInfo::removeBranch(MachineBasicBlock &MBB, + int *BytesRemoved) const { + // Most of the code and comments here are boilerplate. + MachineBasicBlock::iterator I = MBB.end(); + unsigned Count = 0; + if (BytesRemoved) + *BytesRemoved = 0; + + while (I != MBB.begin()) { + --I; + SmallVector Cond; + Cond.push_back(MachineOperand::CreateImm(0)); + const MachineOperand *Target; + if (!isBranch(I, Cond, Target)) + break; + if (!Target->isMBB()) + break; + // Remove the branch. + if (BytesRemoved) + *BytesRemoved += getInstSizeInBytes(*I); + I->eraseFromParent(); + I = MBB.end(); + ++Count; + } + return Count; +} + +unsigned XtensaInstrInfo::insertBranch( + MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, + ArrayRef Cond, const DebugLoc &DL, int *BytesAdded) const { + unsigned Count = 0; + if (BytesAdded) + *BytesAdded = 0; + if (FBB) { + // Need to build two branches then + // one to branch to TBB on Cond + // and a second one immediately after to unconditionally jump to FBB + Count = InsertBranchAtInst(MBB, MBB.end(), TBB, Cond, DL, BytesAdded); + auto &MI = *BuildMI(&MBB, DL, get(Xtensa::J)).addMBB(FBB); + Count++; + if (BytesAdded) + *BytesAdded += getInstSizeInBytes(MI); + return Count; + } + // This function inserts the branch at the end of the MBB + Count += InsertBranchAtInst(MBB, MBB.end(), TBB, Cond, DL, BytesAdded); + return Count; +} + +unsigned XtensaInstrInfo::InsertBranchAtInst(MachineBasicBlock &MBB, + MachineBasicBlock::iterator I, + MachineBasicBlock *TBB, + ArrayRef Cond, + const DebugLoc &DL, + int *BytesAdded) const { + // Shouldn't be a fall through. + assert(TBB && "InsertBranch must not be told to insert a fallthrough"); + assert(Cond.size() <= 4 && + "Xtensa branch conditions have less than four components!"); + + if (Cond.empty() || (Cond[0].getImm() == Xtensa::J)) { + // Unconditional branch + MachineInstr *MI = BuildMI(MBB, I, DL, get(Xtensa::J)).addMBB(TBB); + if (BytesAdded && MI) + *BytesAdded += getInstSizeInBytes(*MI); + return 1; + } + + unsigned Count = 0; + unsigned BR_C = Cond[0].getImm(); + MachineInstr *MI = nullptr; + switch (BR_C) { + case Xtensa::BEQ: + case Xtensa::BNE: + case Xtensa::BLT: + case Xtensa::BLTU: + case Xtensa::BGE: + case Xtensa::BGEU: + MI = BuildMI(MBB, I, DL, get(BR_C)) + .addReg(Cond[1].getReg()) + .addReg(Cond[2].getReg()) + .addMBB(TBB); + break; + case Xtensa::BEQI: + case Xtensa::BNEI: + case Xtensa::BLTI: + case Xtensa::BLTUI: + case Xtensa::BGEI: + case Xtensa::BGEUI: + MI = BuildMI(MBB, I, DL, get(BR_C)) + .addReg(Cond[1].getReg()) + .addImm(Cond[2].getImm()) + .addMBB(TBB); + break; + case Xtensa::BEQZ: + case Xtensa::BNEZ: + case Xtensa::BLTZ: + case Xtensa::BGEZ: + MI = BuildMI(MBB, I, DL, get(BR_C)).addReg(Cond[1].getReg()).addMBB(TBB); + break; + default: + llvm_unreachable("Invalid branch type!"); + } + if (BytesAdded && MI) + *BytesAdded += getInstSizeInBytes(*MI); + ++Count; + return Count; +} + +bool XtensaInstrInfo::isBranch(const MachineBasicBlock::iterator &MI, + SmallVectorImpl &Cond, + const MachineOperand *&Target) const { + unsigned OpCode = MI->getOpcode(); + switch (OpCode) { + case Xtensa::J: + case Xtensa::JX: + case Xtensa::BR_JT: + Cond[0].setImm(OpCode); + Target = &MI->getOperand(0); + return true; + case Xtensa::BEQ: + case Xtensa::BNE: + case Xtensa::BLT: + case Xtensa::BLTU: + case Xtensa::BGE: + case Xtensa::BGEU: + Cond[0].setImm(OpCode); + Target = &MI->getOperand(2); + return true; + + case Xtensa::BEQI: + case Xtensa::BNEI: + case Xtensa::BLTI: + case Xtensa::BLTUI: + case Xtensa::BGEI: + case Xtensa::BGEUI: + Cond[0].setImm(OpCode); + Target = &MI->getOperand(2); + return true; + + case Xtensa::BEQZ: + case Xtensa::BNEZ: + case Xtensa::BLTZ: + case Xtensa::BGEZ: + Cond[0].setImm(OpCode); + Target = &MI->getOperand(1); + return true; + + default: + assert(!MI->getDesc().isBranch() && "Unknown branch opcode"); + return false; + } +}