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