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