1234285Sdim//===-- HexagonCFGOptimizer.cpp - CFG optimizations -----------------------===// 2234285Sdim// The LLVM Compiler Infrastructure 3234285Sdim// 4234285Sdim// This file is distributed under the University of Illinois Open Source 5234285Sdim// License. See LICENSE.TXT for details. 6234285Sdim// 7234285Sdim//===----------------------------------------------------------------------===// 8234285Sdim 9234285Sdim#define DEBUG_TYPE "hexagon_cfg" 10252723Sdim#include "Hexagon.h" 11252723Sdim#include "HexagonMachineFunctionInfo.h" 12252723Sdim#include "HexagonSubtarget.h" 13234285Sdim#include "HexagonTargetMachine.h" 14234285Sdim#include "llvm/CodeGen/MachineDominators.h" 15234285Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 16234285Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 17234285Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 18234285Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 19234285Sdim#include "llvm/CodeGen/Passes.h" 20234285Sdim#include "llvm/Support/Compiler.h" 21234285Sdim#include "llvm/Support/Debug.h" 22234285Sdim#include "llvm/Support/MathExtras.h" 23252723Sdim#include "llvm/Target/TargetInstrInfo.h" 24252723Sdim#include "llvm/Target/TargetMachine.h" 25252723Sdim#include "llvm/Target/TargetRegisterInfo.h" 26234285Sdim 27234285Sdimusing namespace llvm; 28234285Sdim 29252723Sdimnamespace llvm { 30252723Sdim void initializeHexagonCFGOptimizerPass(PassRegistry&); 31252723Sdim} 32252723Sdim 33252723Sdim 34234285Sdimnamespace { 35234285Sdim 36234285Sdimclass HexagonCFGOptimizer : public MachineFunctionPass { 37234285Sdim 38234285Sdimprivate: 39252723Sdim const HexagonTargetMachine& QTM; 40234285Sdim const HexagonSubtarget &QST; 41234285Sdim 42234285Sdim void InvertAndChangeJumpTarget(MachineInstr*, MachineBasicBlock*); 43234285Sdim 44234285Sdim public: 45234285Sdim static char ID; 46252723Sdim HexagonCFGOptimizer(const HexagonTargetMachine& TM) 47252723Sdim : MachineFunctionPass(ID), QTM(TM), QST(*TM.getSubtargetImpl()) { 48252723Sdim initializeHexagonCFGOptimizerPass(*PassRegistry::getPassRegistry()); 49252723Sdim } 50234285Sdim 51234285Sdim const char *getPassName() const { 52234285Sdim return "Hexagon CFG Optimizer"; 53234285Sdim } 54234285Sdim bool runOnMachineFunction(MachineFunction &Fn); 55234285Sdim}; 56234285Sdim 57234285Sdim 58234285Sdimchar HexagonCFGOptimizer::ID = 0; 59234285Sdim 60234285Sdimstatic bool IsConditionalBranch(int Opc) { 61252723Sdim return (Opc == Hexagon::JMP_t) || (Opc == Hexagon::JMP_f) 62252723Sdim || (Opc == Hexagon::JMP_tnew_t) || (Opc == Hexagon::JMP_fnew_t); 63234285Sdim} 64234285Sdim 65234285Sdim 66234285Sdimstatic bool IsUnconditionalJump(int Opc) { 67234285Sdim return (Opc == Hexagon::JMP); 68234285Sdim} 69234285Sdim 70234285Sdim 71234285Sdimvoid 72234285SdimHexagonCFGOptimizer::InvertAndChangeJumpTarget(MachineInstr* MI, 73234285Sdim MachineBasicBlock* NewTarget) { 74234285Sdim const HexagonInstrInfo *QII = QTM.getInstrInfo(); 75234285Sdim int NewOpcode = 0; 76234285Sdim switch(MI->getOpcode()) { 77252723Sdim case Hexagon::JMP_t: 78252723Sdim NewOpcode = Hexagon::JMP_f; 79234285Sdim break; 80234285Sdim 81252723Sdim case Hexagon::JMP_f: 82252723Sdim NewOpcode = Hexagon::JMP_t; 83234285Sdim break; 84234285Sdim 85252723Sdim case Hexagon::JMP_tnew_t: 86252723Sdim NewOpcode = Hexagon::JMP_fnew_t; 87234285Sdim break; 88234285Sdim 89252723Sdim case Hexagon::JMP_fnew_t: 90252723Sdim NewOpcode = Hexagon::JMP_tnew_t; 91234285Sdim break; 92234285Sdim 93234285Sdim default: 94234285Sdim llvm_unreachable("Cannot handle this case"); 95234285Sdim } 96234285Sdim 97234285Sdim MI->setDesc(QII->get(NewOpcode)); 98234285Sdim MI->getOperand(1).setMBB(NewTarget); 99234285Sdim} 100234285Sdim 101234285Sdim 102234285Sdimbool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) { 103234285Sdim 104234285Sdim // Loop over all of the basic blocks. 105234285Sdim for (MachineFunction::iterator MBBb = Fn.begin(), MBBe = Fn.end(); 106234285Sdim MBBb != MBBe; ++MBBb) { 107234285Sdim MachineBasicBlock* MBB = MBBb; 108234285Sdim 109234285Sdim // Traverse the basic block. 110234285Sdim MachineBasicBlock::iterator MII = MBB->getFirstTerminator(); 111234285Sdim if (MII != MBB->end()) { 112234285Sdim MachineInstr *MI = MII; 113234285Sdim int Opc = MI->getOpcode(); 114234285Sdim if (IsConditionalBranch(Opc)) { 115234285Sdim 116234285Sdim // 117234285Sdim // (Case 1) Transform the code if the following condition occurs: 118234285Sdim // BB1: if (p0) jump BB3 119234285Sdim // ...falls-through to BB2 ... 120234285Sdim // BB2: jump BB4 121234285Sdim // ...next block in layout is BB3... 122234285Sdim // BB3: ... 123234285Sdim // 124234285Sdim // Transform this to: 125234285Sdim // BB1: if (!p0) jump BB4 126234285Sdim // Remove BB2 127234285Sdim // BB3: ... 128234285Sdim // 129234285Sdim // (Case 2) A variation occurs when BB3 contains a JMP to BB4: 130234285Sdim // BB1: if (p0) jump BB3 131234285Sdim // ...falls-through to BB2 ... 132234285Sdim // BB2: jump BB4 133234285Sdim // ...other basic blocks ... 134234285Sdim // BB4: 135234285Sdim // ...not a fall-thru 136234285Sdim // BB3: ... 137234285Sdim // jump BB4 138234285Sdim // 139234285Sdim // Transform this to: 140234285Sdim // BB1: if (!p0) jump BB4 141234285Sdim // Remove BB2 142234285Sdim // BB3: ... 143234285Sdim // BB4: ... 144234285Sdim // 145234285Sdim unsigned NumSuccs = MBB->succ_size(); 146234285Sdim MachineBasicBlock::succ_iterator SI = MBB->succ_begin(); 147234285Sdim MachineBasicBlock* FirstSucc = *SI; 148234285Sdim MachineBasicBlock* SecondSucc = *(++SI); 149234285Sdim MachineBasicBlock* LayoutSucc = NULL; 150234285Sdim MachineBasicBlock* JumpAroundTarget = NULL; 151234285Sdim 152234285Sdim if (MBB->isLayoutSuccessor(FirstSucc)) { 153234285Sdim LayoutSucc = FirstSucc; 154234285Sdim JumpAroundTarget = SecondSucc; 155234285Sdim } else if (MBB->isLayoutSuccessor(SecondSucc)) { 156234285Sdim LayoutSucc = SecondSucc; 157234285Sdim JumpAroundTarget = FirstSucc; 158234285Sdim } else { 159234285Sdim // Odd case...cannot handle. 160234285Sdim } 161234285Sdim 162234285Sdim // The target of the unconditional branch must be JumpAroundTarget. 163234285Sdim // TODO: If not, we should not invert the unconditional branch. 164234285Sdim MachineBasicBlock* CondBranchTarget = NULL; 165252723Sdim if ((MI->getOpcode() == Hexagon::JMP_t) || 166252723Sdim (MI->getOpcode() == Hexagon::JMP_f)) { 167234285Sdim CondBranchTarget = MI->getOperand(1).getMBB(); 168234285Sdim } 169234285Sdim 170234285Sdim if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) { 171234285Sdim continue; 172234285Sdim } 173234285Sdim 174234285Sdim if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) { 175234285Sdim 176234285Sdim // Ensure that BB2 has one instruction -- an unconditional jump. 177234285Sdim if ((LayoutSucc->size() == 1) && 178234285Sdim IsUnconditionalJump(LayoutSucc->front().getOpcode())) { 179234285Sdim MachineBasicBlock* UncondTarget = 180234285Sdim LayoutSucc->front().getOperand(0).getMBB(); 181234285Sdim // Check if the layout successor of BB2 is BB3. 182234285Sdim bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget); 183234285Sdim bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) && 184234285Sdim JumpAroundTarget->size() >= 1 && 185234285Sdim IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) && 186234285Sdim JumpAroundTarget->pred_size() == 1 && 187234285Sdim JumpAroundTarget->succ_size() == 1; 188234285Sdim 189234285Sdim if (case1 || case2) { 190234285Sdim InvertAndChangeJumpTarget(MI, UncondTarget); 191234285Sdim MBB->removeSuccessor(JumpAroundTarget); 192234285Sdim MBB->addSuccessor(UncondTarget); 193234285Sdim 194234285Sdim // Remove the unconditional branch in LayoutSucc. 195234285Sdim LayoutSucc->erase(LayoutSucc->begin()); 196234285Sdim LayoutSucc->removeSuccessor(UncondTarget); 197234285Sdim LayoutSucc->addSuccessor(JumpAroundTarget); 198234285Sdim 199234285Sdim // This code performs the conversion for case 2, which moves 200234285Sdim // the block to the fall-thru case (BB3 in the code above). 201234285Sdim if (case2 && !case1) { 202234285Sdim JumpAroundTarget->moveAfter(LayoutSucc); 203234285Sdim // only move a block if it doesn't have a fall-thru. otherwise 204234285Sdim // the CFG will be incorrect. 205234285Sdim if (!UncondTarget->canFallThrough()) { 206234285Sdim UncondTarget->moveAfter(JumpAroundTarget); 207234285Sdim } 208234285Sdim } 209234285Sdim 210234285Sdim // 211234285Sdim // Correct live-in information. Is used by post-RA scheduler 212234285Sdim // The live-in to LayoutSucc is now all values live-in to 213234285Sdim // JumpAroundTarget. 214234285Sdim // 215234285Sdim std::vector<unsigned> OrigLiveIn(LayoutSucc->livein_begin(), 216234285Sdim LayoutSucc->livein_end()); 217234285Sdim std::vector<unsigned> NewLiveIn(JumpAroundTarget->livein_begin(), 218234285Sdim JumpAroundTarget->livein_end()); 219234285Sdim for (unsigned i = 0; i < OrigLiveIn.size(); ++i) { 220234285Sdim LayoutSucc->removeLiveIn(OrigLiveIn[i]); 221234285Sdim } 222234285Sdim for (unsigned i = 0; i < NewLiveIn.size(); ++i) { 223234285Sdim LayoutSucc->addLiveIn(NewLiveIn[i]); 224234285Sdim } 225234285Sdim } 226234285Sdim } 227234285Sdim } 228234285Sdim } 229234285Sdim } 230234285Sdim } 231234285Sdim return true; 232234285Sdim} 233234285Sdim} 234234285Sdim 235234285Sdim 236234285Sdim//===----------------------------------------------------------------------===// 237234285Sdim// Public Constructor Functions 238234285Sdim//===----------------------------------------------------------------------===// 239234285Sdim 240252723Sdimstatic void initializePassOnce(PassRegistry &Registry) { 241252723Sdim PassInfo *PI = new PassInfo("Hexagon CFG Optimizer", "hexagon-cfg", 242252723Sdim &HexagonCFGOptimizer::ID, 0, false, false); 243252723Sdim Registry.registerPass(*PI, true); 244252723Sdim} 245252723Sdim 246252723Sdimvoid llvm::initializeHexagonCFGOptimizerPass(PassRegistry &Registry) { 247252723Sdim CALL_ONCE_INITIALIZATION(initializePassOnce) 248252723Sdim} 249252723Sdim 250252723SdimFunctionPass *llvm::createHexagonCFGOptimizer(const HexagonTargetMachine &TM) { 251234285Sdim return new HexagonCFGOptimizer(TM); 252234285Sdim} 253