1 //===-- HexagonCFGOptimizer.cpp - CFG optimizations -----------------------===// 2 // The LLVM Compiler Infrastructure 3 // 4 // This file is distributed under the University of Illinois Open Source 5 // License. See LICENSE.TXT for details. 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "Hexagon.h" 10 #include "HexagonMachineFunctionInfo.h" 11 #include "HexagonSubtarget.h" 12 #include "HexagonTargetMachine.h" 13 #include "llvm/CodeGen/MachineDominators.h" 14 #include "llvm/CodeGen/MachineFunctionPass.h" 15 #include "llvm/CodeGen/MachineInstrBuilder.h" 16 #include "llvm/CodeGen/MachineLoopInfo.h" 17 #include "llvm/CodeGen/MachineRegisterInfo.h" 18 #include "llvm/CodeGen/Passes.h" 19 #include "llvm/Support/Compiler.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Support/MathExtras.h" 22 #include "llvm/Target/TargetInstrInfo.h" 23 #include "llvm/Target/TargetMachine.h" 24 #include "llvm/Target/TargetRegisterInfo.h" 25 26 using namespace llvm; 27 28 #define DEBUG_TYPE "hexagon_cfg" 29 30 namespace llvm { 31 void initializeHexagonCFGOptimizerPass(PassRegistry&); 32 } 33 34 35 namespace { 36 37 class HexagonCFGOptimizer : public MachineFunctionPass { 38 39 private: 40 const HexagonTargetMachine& QTM; 41 const HexagonSubtarget &QST; 42 43 void InvertAndChangeJumpTarget(MachineInstr*, MachineBasicBlock*); 44 45 public: 46 static char ID; 47 HexagonCFGOptimizer(const HexagonTargetMachine& TM) 48 : MachineFunctionPass(ID), QTM(TM), QST(*TM.getSubtargetImpl()) { 49 initializeHexagonCFGOptimizerPass(*PassRegistry::getPassRegistry()); 50 } 51 52 const char *getPassName() const override { 53 return "Hexagon CFG Optimizer"; 54 } 55 bool runOnMachineFunction(MachineFunction &Fn) override; 56 }; 57 58 59 char HexagonCFGOptimizer::ID = 0; 60 61 static bool IsConditionalBranch(int Opc) { 62 return (Opc == Hexagon::JMP_t) || (Opc == Hexagon::JMP_f) 63 || (Opc == Hexagon::JMP_tnew_t) || (Opc == Hexagon::JMP_fnew_t); 64 } 65 66 67 static bool IsUnconditionalJump(int Opc) { 68 return (Opc == Hexagon::JMP); 69 } 70 71 72 void 73 HexagonCFGOptimizer::InvertAndChangeJumpTarget(MachineInstr* MI, 74 MachineBasicBlock* NewTarget) { 75 const HexagonInstrInfo *QII = QTM.getInstrInfo(); 76 int NewOpcode = 0; 77 switch(MI->getOpcode()) { 78 case Hexagon::JMP_t: 79 NewOpcode = Hexagon::JMP_f; 80 break; 81 82 case Hexagon::JMP_f: 83 NewOpcode = Hexagon::JMP_t; 84 break; 85 86 case Hexagon::JMP_tnew_t: 87 NewOpcode = Hexagon::JMP_fnew_t; 88 break; 89 90 case Hexagon::JMP_fnew_t: 91 NewOpcode = Hexagon::JMP_tnew_t; 92 break; 93 94 default: 95 llvm_unreachable("Cannot handle this case"); 96 } 97 98 MI->setDesc(QII->get(NewOpcode)); 99 MI->getOperand(1).setMBB(NewTarget); 100 } 101 102 103 bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) { 104 105 // Loop over all of the basic blocks. 106 for (MachineFunction::iterator MBBb = Fn.begin(), MBBe = Fn.end(); 107 MBBb != MBBe; ++MBBb) { 108 MachineBasicBlock* MBB = MBBb; 109 110 // Traverse the basic block. 111 MachineBasicBlock::iterator MII = MBB->getFirstTerminator(); 112 if (MII != MBB->end()) { 113 MachineInstr *MI = MII; 114 int Opc = MI->getOpcode(); 115 if (IsConditionalBranch(Opc)) { 116 117 // 118 // (Case 1) Transform the code if the following condition occurs: 119 // BB1: if (p0) jump BB3 120 // ...falls-through to BB2 ... 121 // BB2: jump BB4 122 // ...next block in layout is BB3... 123 // BB3: ... 124 // 125 // Transform this to: 126 // BB1: if (!p0) jump BB4 127 // Remove BB2 128 // BB3: ... 129 // 130 // (Case 2) A variation occurs when BB3 contains a JMP to BB4: 131 // BB1: if (p0) jump BB3 132 // ...falls-through to BB2 ... 133 // BB2: jump BB4 134 // ...other basic blocks ... 135 // BB4: 136 // ...not a fall-thru 137 // BB3: ... 138 // jump BB4 139 // 140 // Transform this to: 141 // BB1: if (!p0) jump BB4 142 // Remove BB2 143 // BB3: ... 144 // BB4: ... 145 // 146 unsigned NumSuccs = MBB->succ_size(); 147 MachineBasicBlock::succ_iterator SI = MBB->succ_begin(); 148 MachineBasicBlock* FirstSucc = *SI; 149 MachineBasicBlock* SecondSucc = *(++SI); 150 MachineBasicBlock* LayoutSucc = nullptr; 151 MachineBasicBlock* JumpAroundTarget = nullptr; 152 153 if (MBB->isLayoutSuccessor(FirstSucc)) { 154 LayoutSucc = FirstSucc; 155 JumpAroundTarget = SecondSucc; 156 } else if (MBB->isLayoutSuccessor(SecondSucc)) { 157 LayoutSucc = SecondSucc; 158 JumpAroundTarget = FirstSucc; 159 } else { 160 // Odd case...cannot handle. 161 } 162 163 // The target of the unconditional branch must be JumpAroundTarget. 164 // TODO: If not, we should not invert the unconditional branch. 165 MachineBasicBlock* CondBranchTarget = nullptr; 166 if ((MI->getOpcode() == Hexagon::JMP_t) || 167 (MI->getOpcode() == Hexagon::JMP_f)) { 168 CondBranchTarget = MI->getOperand(1).getMBB(); 169 } 170 171 if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) { 172 continue; 173 } 174 175 if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) { 176 177 // Ensure that BB2 has one instruction -- an unconditional jump. 178 if ((LayoutSucc->size() == 1) && 179 IsUnconditionalJump(LayoutSucc->front().getOpcode())) { 180 MachineBasicBlock* UncondTarget = 181 LayoutSucc->front().getOperand(0).getMBB(); 182 // Check if the layout successor of BB2 is BB3. 183 bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget); 184 bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) && 185 JumpAroundTarget->size() >= 1 && 186 IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) && 187 JumpAroundTarget->pred_size() == 1 && 188 JumpAroundTarget->succ_size() == 1; 189 190 if (case1 || case2) { 191 InvertAndChangeJumpTarget(MI, UncondTarget); 192 MBB->removeSuccessor(JumpAroundTarget); 193 MBB->addSuccessor(UncondTarget); 194 195 // Remove the unconditional branch in LayoutSucc. 196 LayoutSucc->erase(LayoutSucc->begin()); 197 LayoutSucc->removeSuccessor(UncondTarget); 198 LayoutSucc->addSuccessor(JumpAroundTarget); 199 200 // This code performs the conversion for case 2, which moves 201 // the block to the fall-thru case (BB3 in the code above). 202 if (case2 && !case1) { 203 JumpAroundTarget->moveAfter(LayoutSucc); 204 // only move a block if it doesn't have a fall-thru. otherwise 205 // the CFG will be incorrect. 206 if (!UncondTarget->canFallThrough()) { 207 UncondTarget->moveAfter(JumpAroundTarget); 208 } 209 } 210 211 // 212 // Correct live-in information. Is used by post-RA scheduler 213 // The live-in to LayoutSucc is now all values live-in to 214 // JumpAroundTarget. 215 // 216 std::vector<unsigned> OrigLiveIn(LayoutSucc->livein_begin(), 217 LayoutSucc->livein_end()); 218 std::vector<unsigned> NewLiveIn(JumpAroundTarget->livein_begin(), 219 JumpAroundTarget->livein_end()); 220 for (unsigned i = 0; i < OrigLiveIn.size(); ++i) { 221 LayoutSucc->removeLiveIn(OrigLiveIn[i]); 222 } 223 for (unsigned i = 0; i < NewLiveIn.size(); ++i) { 224 LayoutSucc->addLiveIn(NewLiveIn[i]); 225 } 226 } 227 } 228 } 229 } 230 } 231 } 232 return true; 233 } 234 } 235 236 237 //===----------------------------------------------------------------------===// 238 // Public Constructor Functions 239 //===----------------------------------------------------------------------===// 240 241 static void initializePassOnce(PassRegistry &Registry) { 242 PassInfo *PI = new PassInfo("Hexagon CFG Optimizer", "hexagon-cfg", 243 &HexagonCFGOptimizer::ID, nullptr, false, false); 244 Registry.registerPass(*PI, true); 245 } 246 247 void llvm::initializeHexagonCFGOptimizerPass(PassRegistry &Registry) { 248 CALL_ONCE_INITIALIZATION(initializePassOnce) 249 } 250 251 FunctionPass *llvm::createHexagonCFGOptimizer(const HexagonTargetMachine &TM) { 252 return new HexagonCFGOptimizer(TM); 253 } 254
