HexagonCFGOptimizer.cpp revision 249423
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" 10249423Sdim#include "Hexagon.h" 11249423Sdim#include "HexagonMachineFunctionInfo.h" 12249423Sdim#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" 23249423Sdim#include "llvm/Target/TargetInstrInfo.h" 24249423Sdim#include "llvm/Target/TargetMachine.h" 25249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 26234285Sdim 27234285Sdimusing namespace llvm; 28234285Sdim 29234285Sdimnamespace { 30234285Sdim 31234285Sdimclass HexagonCFGOptimizer : public MachineFunctionPass { 32234285Sdim 33234285Sdimprivate: 34234285Sdim HexagonTargetMachine& QTM; 35234285Sdim const HexagonSubtarget &QST; 36234285Sdim 37234285Sdim void InvertAndChangeJumpTarget(MachineInstr*, MachineBasicBlock*); 38234285Sdim 39234285Sdim public: 40234285Sdim static char ID; 41234285Sdim HexagonCFGOptimizer(HexagonTargetMachine& TM) : MachineFunctionPass(ID), 42234285Sdim QTM(TM), 43234285Sdim QST(*TM.getSubtargetImpl()) {} 44234285Sdim 45234285Sdim const char *getPassName() const { 46234285Sdim return "Hexagon CFG Optimizer"; 47234285Sdim } 48234285Sdim bool runOnMachineFunction(MachineFunction &Fn); 49234285Sdim}; 50234285Sdim 51234285Sdim 52234285Sdimchar HexagonCFGOptimizer::ID = 0; 53234285Sdim 54234285Sdimstatic bool IsConditionalBranch(int Opc) { 55234285Sdim return (Opc == Hexagon::JMP_c) || (Opc == Hexagon::JMP_cNot) 56234285Sdim || (Opc == Hexagon::JMP_cdnPt) || (Opc == Hexagon::JMP_cdnNotPt); 57234285Sdim} 58234285Sdim 59234285Sdim 60234285Sdimstatic bool IsUnconditionalJump(int Opc) { 61234285Sdim return (Opc == Hexagon::JMP); 62234285Sdim} 63234285Sdim 64234285Sdim 65234285Sdimvoid 66234285SdimHexagonCFGOptimizer::InvertAndChangeJumpTarget(MachineInstr* MI, 67234285Sdim MachineBasicBlock* NewTarget) { 68234285Sdim const HexagonInstrInfo *QII = QTM.getInstrInfo(); 69234285Sdim int NewOpcode = 0; 70234285Sdim switch(MI->getOpcode()) { 71234285Sdim case Hexagon::JMP_c: 72234285Sdim NewOpcode = Hexagon::JMP_cNot; 73234285Sdim break; 74234285Sdim 75234285Sdim case Hexagon::JMP_cNot: 76234285Sdim NewOpcode = Hexagon::JMP_c; 77234285Sdim break; 78234285Sdim 79234285Sdim case Hexagon::JMP_cdnPt: 80234285Sdim NewOpcode = Hexagon::JMP_cdnNotPt; 81234285Sdim break; 82234285Sdim 83234285Sdim case Hexagon::JMP_cdnNotPt: 84234285Sdim NewOpcode = Hexagon::JMP_cdnPt; 85234285Sdim break; 86234285Sdim 87234285Sdim default: 88234285Sdim llvm_unreachable("Cannot handle this case"); 89234285Sdim } 90234285Sdim 91234285Sdim MI->setDesc(QII->get(NewOpcode)); 92234285Sdim MI->getOperand(1).setMBB(NewTarget); 93234285Sdim} 94234285Sdim 95234285Sdim 96234285Sdimbool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) { 97234285Sdim 98234285Sdim // Loop over all of the basic blocks. 99234285Sdim for (MachineFunction::iterator MBBb = Fn.begin(), MBBe = Fn.end(); 100234285Sdim MBBb != MBBe; ++MBBb) { 101234285Sdim MachineBasicBlock* MBB = MBBb; 102234285Sdim 103234285Sdim // Traverse the basic block. 104234285Sdim MachineBasicBlock::iterator MII = MBB->getFirstTerminator(); 105234285Sdim if (MII != MBB->end()) { 106234285Sdim MachineInstr *MI = MII; 107234285Sdim int Opc = MI->getOpcode(); 108234285Sdim if (IsConditionalBranch(Opc)) { 109234285Sdim 110234285Sdim // 111234285Sdim // (Case 1) Transform the code if the following condition occurs: 112234285Sdim // BB1: if (p0) jump BB3 113234285Sdim // ...falls-through to BB2 ... 114234285Sdim // BB2: jump BB4 115234285Sdim // ...next block in layout is BB3... 116234285Sdim // BB3: ... 117234285Sdim // 118234285Sdim // Transform this to: 119234285Sdim // BB1: if (!p0) jump BB4 120234285Sdim // Remove BB2 121234285Sdim // BB3: ... 122234285Sdim // 123234285Sdim // (Case 2) A variation occurs when BB3 contains a JMP to BB4: 124234285Sdim // BB1: if (p0) jump BB3 125234285Sdim // ...falls-through to BB2 ... 126234285Sdim // BB2: jump BB4 127234285Sdim // ...other basic blocks ... 128234285Sdim // BB4: 129234285Sdim // ...not a fall-thru 130234285Sdim // BB3: ... 131234285Sdim // jump BB4 132234285Sdim // 133234285Sdim // Transform this to: 134234285Sdim // BB1: if (!p0) jump BB4 135234285Sdim // Remove BB2 136234285Sdim // BB3: ... 137234285Sdim // BB4: ... 138234285Sdim // 139234285Sdim unsigned NumSuccs = MBB->succ_size(); 140234285Sdim MachineBasicBlock::succ_iterator SI = MBB->succ_begin(); 141234285Sdim MachineBasicBlock* FirstSucc = *SI; 142234285Sdim MachineBasicBlock* SecondSucc = *(++SI); 143234285Sdim MachineBasicBlock* LayoutSucc = NULL; 144234285Sdim MachineBasicBlock* JumpAroundTarget = NULL; 145234285Sdim 146234285Sdim if (MBB->isLayoutSuccessor(FirstSucc)) { 147234285Sdim LayoutSucc = FirstSucc; 148234285Sdim JumpAroundTarget = SecondSucc; 149234285Sdim } else if (MBB->isLayoutSuccessor(SecondSucc)) { 150234285Sdim LayoutSucc = SecondSucc; 151234285Sdim JumpAroundTarget = FirstSucc; 152234285Sdim } else { 153234285Sdim // Odd case...cannot handle. 154234285Sdim } 155234285Sdim 156234285Sdim // The target of the unconditional branch must be JumpAroundTarget. 157234285Sdim // TODO: If not, we should not invert the unconditional branch. 158234285Sdim MachineBasicBlock* CondBranchTarget = NULL; 159234285Sdim if ((MI->getOpcode() == Hexagon::JMP_c) || 160234285Sdim (MI->getOpcode() == Hexagon::JMP_cNot)) { 161234285Sdim CondBranchTarget = MI->getOperand(1).getMBB(); 162234285Sdim } 163234285Sdim 164234285Sdim if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) { 165234285Sdim continue; 166234285Sdim } 167234285Sdim 168234285Sdim if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) { 169234285Sdim 170234285Sdim // Ensure that BB2 has one instruction -- an unconditional jump. 171234285Sdim if ((LayoutSucc->size() == 1) && 172234285Sdim IsUnconditionalJump(LayoutSucc->front().getOpcode())) { 173234285Sdim MachineBasicBlock* UncondTarget = 174234285Sdim LayoutSucc->front().getOperand(0).getMBB(); 175234285Sdim // Check if the layout successor of BB2 is BB3. 176234285Sdim bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget); 177234285Sdim bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) && 178234285Sdim JumpAroundTarget->size() >= 1 && 179234285Sdim IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) && 180234285Sdim JumpAroundTarget->pred_size() == 1 && 181234285Sdim JumpAroundTarget->succ_size() == 1; 182234285Sdim 183234285Sdim if (case1 || case2) { 184234285Sdim InvertAndChangeJumpTarget(MI, UncondTarget); 185234285Sdim MBB->removeSuccessor(JumpAroundTarget); 186234285Sdim MBB->addSuccessor(UncondTarget); 187234285Sdim 188234285Sdim // Remove the unconditional branch in LayoutSucc. 189234285Sdim LayoutSucc->erase(LayoutSucc->begin()); 190234285Sdim LayoutSucc->removeSuccessor(UncondTarget); 191234285Sdim LayoutSucc->addSuccessor(JumpAroundTarget); 192234285Sdim 193234285Sdim // This code performs the conversion for case 2, which moves 194234285Sdim // the block to the fall-thru case (BB3 in the code above). 195234285Sdim if (case2 && !case1) { 196234285Sdim JumpAroundTarget->moveAfter(LayoutSucc); 197234285Sdim // only move a block if it doesn't have a fall-thru. otherwise 198234285Sdim // the CFG will be incorrect. 199234285Sdim if (!UncondTarget->canFallThrough()) { 200234285Sdim UncondTarget->moveAfter(JumpAroundTarget); 201234285Sdim } 202234285Sdim } 203234285Sdim 204234285Sdim // 205234285Sdim // Correct live-in information. Is used by post-RA scheduler 206234285Sdim // The live-in to LayoutSucc is now all values live-in to 207234285Sdim // JumpAroundTarget. 208234285Sdim // 209234285Sdim std::vector<unsigned> OrigLiveIn(LayoutSucc->livein_begin(), 210234285Sdim LayoutSucc->livein_end()); 211234285Sdim std::vector<unsigned> NewLiveIn(JumpAroundTarget->livein_begin(), 212234285Sdim JumpAroundTarget->livein_end()); 213234285Sdim for (unsigned i = 0; i < OrigLiveIn.size(); ++i) { 214234285Sdim LayoutSucc->removeLiveIn(OrigLiveIn[i]); 215234285Sdim } 216234285Sdim for (unsigned i = 0; i < NewLiveIn.size(); ++i) { 217234285Sdim LayoutSucc->addLiveIn(NewLiveIn[i]); 218234285Sdim } 219234285Sdim } 220234285Sdim } 221234285Sdim } 222234285Sdim } 223234285Sdim } 224234285Sdim } 225234285Sdim return true; 226234285Sdim} 227234285Sdim} 228234285Sdim 229234285Sdim 230234285Sdim//===----------------------------------------------------------------------===// 231234285Sdim// Public Constructor Functions 232234285Sdim//===----------------------------------------------------------------------===// 233234285Sdim 234234285SdimFunctionPass *llvm::createHexagonCFGOptimizer(HexagonTargetMachine &TM) { 235234285Sdim return new HexagonCFGOptimizer(TM); 236234285Sdim} 237