[Xtensa] Implement branch analysis

[arsenm]

Missing tests

[arsenm]

Needs tests

llvm/lib/Target/Xtensa/XtensaInstrInfo.h

public:
   // Get the load and store opcodes for a given register class and offset.
   void getLoadStoreOpcodes(const TargetRegisterClass *RC, unsigned &LoadOpcode,
                            unsigned &StoreOpcode, int64_t offset) const;
 
   // Emit code before MBBI in MI to move immediate value Value into
   // physical register Reg.
   void loadImmediate(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                      unsigned *Reg, int64_t Value) const;
+  bool
+  reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
+  bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
+                     MachineBasicBlock *&FBB,
+                     SmallVectorImpl<MachineOperand> &Cond,
+                     bool AllowModify) const override;
+  unsigned removeBranch(MachineBasicBlock &MBB,
+                        int *BytesRemoved = nullptr) const override;
+  unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
+                        MachineBasicBlock *FBB, ArrayRef<MachineOperand> Cond,
+                        const DebugLoc &DL,
+                        int *BytesAdded = nullptr) const override;
+
+  unsigned InsertBranchAtInst(MachineBasicBlock &MBB,
+                              MachineBasicBlock::iterator I,
+                              MachineBasicBlock *TBB,
+                              ArrayRef<MachineOperand> 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<MachineOperand> &Cond,
+                const MachineOperand *&Target) const;
 };
 } // end namespace llvm
 
 #endif /* LLVM_LIB_TARGET_XTENSA_XTENSAINSTRINFO_H */

llvm/lib/Target/Xtensa/XtensaInstrInfo.cpp

if (Value >= -2048 && Value <= 2047) {
     //  MCSymbol MSym
     BuildMI(MBB, MBBI, DL, get(Xtensa::L32R), *Reg).addConstantPoolIndex(Idx);
   } else {
     // use L32R to let assembler load immediate best
     // TODO replace to L32R
     llvm_unreachable("Unsupported load immediate value");
   }
 }
+
+bool XtensaInstrInfo::reverseBranchCondition(
+    SmallVectorImpl<MachineOperand> &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<MachineOperand> &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<MachineOperand, 4> 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<MachineOperand, 4> 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<MachineOperand> 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<MachineOperand> 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<MachineOperand> &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;
+  }
+}