1 //===- ARCBranchFinalize.cpp - ARC conditional branches ---------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass takes existing conditional branches and expands them into longer
10 // range conditional branches.
11 //===----------------------------------------------------------------------===//
12 
13 #define DEBUG_TYPE "arc-branch-finalize"
14 
15 #include "ARCInstrInfo.h"
16 #include "ARCTargetMachine.h"
17 #include "MCTargetDesc/ARCInfo.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/CodeGen/TargetInstrInfo.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Support/Debug.h"
25 #include <vector>
26 
27 using namespace llvm;
28 
29 namespace llvm {
30 
31 void initializeARCBranchFinalizePass(PassRegistry &Registry);
32 FunctionPass *createARCBranchFinalizePass();
33 
34 } // end namespace llvm
35 
36 namespace {
37 
38 class ARCBranchFinalize : public MachineFunctionPass {
39 public:
40   static char ID;
41 
42   ARCBranchFinalize() : MachineFunctionPass(ID) {
43     initializeARCBranchFinalizePass(*PassRegistry::getPassRegistry());
44   }
45 
46   StringRef getPassName() const override {
47     return "ARC Branch Finalization Pass";
48   }
49 
50   bool runOnMachineFunction(MachineFunction &MF) override;
51   void replaceWithBRcc(MachineInstr *MI) const;
52   void replaceWithCmpBcc(MachineInstr *MI) const;
53 
54 private:
55   const ARCInstrInfo *TII{nullptr};
56 };
57 
58 char ARCBranchFinalize::ID = 0;
59 
60 } // end anonymous namespace
61 
62 INITIALIZE_PASS_BEGIN(ARCBranchFinalize, "arc-branch-finalize",
63                       "ARC finalize branches", false, false)
64 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
65 INITIALIZE_PASS_END(ARCBranchFinalize, "arc-branch-finalize",
66                     "ARC finalize branches", false, false)
67 
68 // BRcc has 6 supported condition codes, which differ from the 16
69 // condition codes supported in the predicated instructions:
70 // EQ -- 000
71 // NE -- 001
72 // LT -- 010
73 // GE -- 011
74 // LO -- 100
75 // HS -- 101
76 static unsigned getCCForBRcc(unsigned CC) {
77   switch (CC) {
78   case ARCCC::EQ:
79     return 0;
80   case ARCCC::NE:
81     return 1;
82   case ARCCC::LT:
83     return 2;
84   case ARCCC::GE:
85     return 3;
86   case ARCCC::LO:
87     return 4;
88   case ARCCC::HS:
89     return 5;
90   default:
91     return -1U;
92   }
93 }
94 
95 static bool isBRccPseudo(MachineInstr *MI) {
96   return !(MI->getOpcode() != ARC::BRcc_rr_p &&
97            MI->getOpcode() != ARC::BRcc_ru6_p);
98 }
99 
100 static unsigned getBRccForPseudo(MachineInstr *MI) {
101   assert(isBRccPseudo(MI) && "Can't get BRcc for wrong instruction.");
102   if (MI->getOpcode() == ARC::BRcc_rr_p)
103     return ARC::BRcc_rr;
104   return ARC::BRcc_ru6;
105 }
106 
107 static unsigned getCmpForPseudo(MachineInstr *MI) {
108   assert(isBRccPseudo(MI) && "Can't get BRcc for wrong instruction.");
109   if (MI->getOpcode() == ARC::BRcc_rr_p)
110     return ARC::CMP_rr;
111   return ARC::CMP_ru6;
112 }
113 
114 void ARCBranchFinalize::replaceWithBRcc(MachineInstr *MI) const {
115   LLVM_DEBUG(dbgs() << "Replacing pseudo branch with BRcc\n");
116   unsigned CC = getCCForBRcc(MI->getOperand(3).getImm());
117   if (CC != -1U) {
118     BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
119             TII->get(getBRccForPseudo(MI)))
120         .addMBB(MI->getOperand(0).getMBB())
121         .addReg(MI->getOperand(1).getReg())
122         .add(MI->getOperand(2))
123         .addImm(getCCForBRcc(MI->getOperand(3).getImm()));
124     MI->eraseFromParent();
125   } else {
126     replaceWithCmpBcc(MI);
127   }
128 }
129 
130 void ARCBranchFinalize::replaceWithCmpBcc(MachineInstr *MI) const {
131   LLVM_DEBUG(dbgs() << "Branch: " << *MI << "\n");
132   LLVM_DEBUG(dbgs() << "Replacing pseudo branch with Cmp + Bcc\n");
133   BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
134           TII->get(getCmpForPseudo(MI)))
135       .addReg(MI->getOperand(1).getReg())
136       .add(MI->getOperand(2));
137   BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), TII->get(ARC::Bcc))
138       .addMBB(MI->getOperand(0).getMBB())
139       .addImm(MI->getOperand(3).getImm());
140   MI->eraseFromParent();
141 }
142 
143 bool ARCBranchFinalize::runOnMachineFunction(MachineFunction &MF) {
144   LLVM_DEBUG(dbgs() << "Running ARC Branch Finalize on " << MF.getName()
145                     << "\n");
146   std::vector<MachineInstr *> Branches;
147   bool Changed = false;
148   unsigned MaxSize = 0;
149   TII = MF.getSubtarget<ARCSubtarget>().getInstrInfo();
150   std::map<MachineBasicBlock *, unsigned> BlockToPCMap;
151   std::vector<std::pair<MachineInstr *, unsigned>> BranchToPCList;
152   unsigned PC = 0;
153 
154   for (auto &MBB : MF) {
155     BlockToPCMap.insert(std::make_pair(&MBB, PC));
156     for (auto &MI : MBB) {
157       unsigned Size = TII->getInstSizeInBytes(MI);
158       if (Size > 8 || Size == 0) {
159         LLVM_DEBUG(dbgs() << "Unknown (or size 0) size for: " << MI << "\n");
160       } else {
161         MaxSize += Size;
162       }
163       if (MI.isBranch()) {
164         Branches.push_back(&MI);
165         BranchToPCList.emplace_back(&MI, PC);
166       }
167       PC += Size;
168     }
169   }
170   for (auto P : BranchToPCList) {
171     if (isBRccPseudo(P.first))
172       isInt<9>(MaxSize) ? replaceWithBRcc(P.first) : replaceWithCmpBcc(P.first);
173   }
174 
175   LLVM_DEBUG(dbgs() << "Estimated function size for " << MF.getName() << ": "
176                     << MaxSize << "\n");
177 
178   return Changed;
179 }
180 
181 FunctionPass *llvm::createARCBranchFinalizePass() {
182   return new ARCBranchFinalize();
183 }
184