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