237 lines · cpp
1//===- HexagonCFGOptimizer.cpp - CFG optimizations ------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "Hexagon.h"10#include "MCTargetDesc/HexagonMCTargetDesc.h"11#include "llvm/CodeGen/MachineBasicBlock.h"12#include "llvm/CodeGen/MachineFunction.h"13#include "llvm/CodeGen/MachineFunctionPass.h"14#include "llvm/CodeGen/MachineInstr.h"15#include "llvm/CodeGen/MachineOperand.h"16#include "llvm/CodeGen/TargetInstrInfo.h"17#include "llvm/CodeGen/TargetSubtargetInfo.h"18#include "llvm/Pass.h"19#include "llvm/Support/ErrorHandling.h"20#include <cassert>21#include <vector>22 23using namespace llvm;24 25#define DEBUG_TYPE "hexagon_cfg"26 27namespace {28 29class HexagonCFGOptimizer : public MachineFunctionPass {30private:31 void InvertAndChangeJumpTarget(MachineInstr &, MachineBasicBlock *);32 bool isOnFallThroughPath(MachineBasicBlock *MBB);33 34public:35 static char ID;36 37 HexagonCFGOptimizer() : MachineFunctionPass(ID) {}38 39 StringRef getPassName() const override { return "Hexagon CFG Optimizer"; }40 bool runOnMachineFunction(MachineFunction &Fn) override;41 42 MachineFunctionProperties getRequiredProperties() const override {43 return MachineFunctionProperties().setNoVRegs();44 }45};46 47} // end anonymous namespace48 49char HexagonCFGOptimizer::ID = 0;50 51static bool IsConditionalBranch(int Opc) {52 switch (Opc) {53 case Hexagon::J2_jumpt:54 case Hexagon::J2_jumptpt:55 case Hexagon::J2_jumpf:56 case Hexagon::J2_jumpfpt:57 case Hexagon::J2_jumptnew:58 case Hexagon::J2_jumpfnew:59 case Hexagon::J2_jumptnewpt:60 case Hexagon::J2_jumpfnewpt:61 return true;62 }63 return false;64}65 66static bool IsUnconditionalJump(int Opc) {67 return (Opc == Hexagon::J2_jump);68}69 70void HexagonCFGOptimizer::InvertAndChangeJumpTarget(71 MachineInstr &MI, MachineBasicBlock *NewTarget) {72 const TargetInstrInfo *TII =73 MI.getParent()->getParent()->getSubtarget().getInstrInfo();74 int NewOpcode = 0;75 switch (MI.getOpcode()) {76 case Hexagon::J2_jumpt:77 NewOpcode = Hexagon::J2_jumpf;78 break;79 case Hexagon::J2_jumpf:80 NewOpcode = Hexagon::J2_jumpt;81 break;82 case Hexagon::J2_jumptnewpt:83 NewOpcode = Hexagon::J2_jumpfnewpt;84 break;85 case Hexagon::J2_jumpfnewpt:86 NewOpcode = Hexagon::J2_jumptnewpt;87 break;88 default:89 llvm_unreachable("Cannot handle this case");90 }91 92 MI.setDesc(TII->get(NewOpcode));93 MI.getOperand(1).setMBB(NewTarget);94}95 96bool HexagonCFGOptimizer::isOnFallThroughPath(MachineBasicBlock *MBB) {97 if (MBB->canFallThrough())98 return true;99 for (MachineBasicBlock *PB : MBB->predecessors())100 if (PB->isLayoutSuccessor(MBB) && PB->canFallThrough())101 return true;102 return false;103}104 105bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {106 if (skipFunction(Fn.getFunction()))107 return false;108 109 // Loop over all of the basic blocks.110 for (MachineBasicBlock &MBB : Fn) {111 // Traverse the basic block.112 MachineBasicBlock::iterator MII = MBB.getFirstTerminator();113 if (MII != MBB.end()) {114 MachineInstr &MI = *MII;115 int Opc = MI.getOpcode();116 if (IsConditionalBranch(Opc)) {117 // (Case 1) Transform the code if the following condition occurs:118 // BB1: if (p0) jump BB3119 // ...falls-through to BB2 ...120 // BB2: jump BB4121 // ...next block in layout is BB3...122 // BB3: ...123 //124 // Transform this to:125 // BB1: if (!p0) jump BB4126 // Remove BB2127 // BB3: ...128 //129 // (Case 2) A variation occurs when BB3 contains a JMP to BB4:130 // BB1: if (p0) jump BB3131 // ...falls-through to BB2 ...132 // BB2: jump BB4133 // ...other basic blocks ...134 // BB4:135 // ...not a fall-thru136 // BB3: ...137 // jump BB4138 //139 // Transform this to:140 // BB1: if (!p0) jump BB4141 // Remove BB2142 // BB3: ...143 // BB4: ...144 unsigned NumSuccs = MBB.succ_size();145 MachineBasicBlock::succ_iterator SI = MBB.succ_begin();146 MachineBasicBlock* FirstSucc = *SI;147 MachineBasicBlock* SecondSucc = *(++SI);148 MachineBasicBlock* LayoutSucc = nullptr;149 MachineBasicBlock* JumpAroundTarget = nullptr;150 151 if (MBB.isLayoutSuccessor(FirstSucc)) {152 LayoutSucc = FirstSucc;153 JumpAroundTarget = SecondSucc;154 } else if (MBB.isLayoutSuccessor(SecondSucc)) {155 LayoutSucc = SecondSucc;156 JumpAroundTarget = FirstSucc;157 } else {158 // Odd case...cannot handle.159 }160 161 // The target of the unconditional branch must be JumpAroundTarget.162 // TODO: If not, we should not invert the unconditional branch.163 MachineBasicBlock* CondBranchTarget = nullptr;164 if (MI.getOpcode() == Hexagon::J2_jumpt ||165 MI.getOpcode() == Hexagon::J2_jumpf) {166 CondBranchTarget = MI.getOperand(1).getMBB();167 }168 169 if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) {170 continue;171 }172 173 if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) {174 // Ensure that BB2 has one instruction -- an unconditional jump.175 if ((LayoutSucc->size() == 1) &&176 IsUnconditionalJump(LayoutSucc->front().getOpcode())) {177 assert(JumpAroundTarget && "jump target is needed to process second basic block");178 MachineBasicBlock* UncondTarget =179 LayoutSucc->front().getOperand(0).getMBB();180 // Check if the layout successor of BB2 is BB3.181 bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget);182 bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) &&183 !JumpAroundTarget->empty() &&184 IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) &&185 JumpAroundTarget->pred_size() == 1 &&186 JumpAroundTarget->succ_size() == 1;187 188 if (case1 || case2) {189 InvertAndChangeJumpTarget(MI, UncondTarget);190 MBB.replaceSuccessor(JumpAroundTarget, UncondTarget);191 192 // Remove the unconditional branch in LayoutSucc.193 LayoutSucc->erase(LayoutSucc->begin());194 LayoutSucc->replaceSuccessor(UncondTarget, JumpAroundTarget);195 196 // This code performs the conversion for case 2, which moves197 // 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. otherwise201 // the CFG will be incorrect.202 if (!isOnFallThroughPath(UncondTarget))203 UncondTarget->moveAfter(JumpAroundTarget);204 }205 206 // Correct live-in information. Is used by post-RA scheduler207 // The live-in to LayoutSucc is now all values live-in to208 // JumpAroundTarget.209 std::vector<MachineBasicBlock::RegisterMaskPair> OrigLiveIn(210 LayoutSucc->livein_begin(), LayoutSucc->livein_end());211 std::vector<MachineBasicBlock::RegisterMaskPair> NewLiveIn(212 JumpAroundTarget->livein_begin(),213 JumpAroundTarget->livein_end());214 for (const auto &OrigLI : OrigLiveIn)215 LayoutSucc->removeLiveIn(OrigLI.PhysReg);216 for (const auto &NewLI : NewLiveIn)217 LayoutSucc->addLiveIn(NewLI);218 }219 }220 }221 }222 }223 }224 return true;225}226 227//===----------------------------------------------------------------------===//228// Public Constructor Functions229//===----------------------------------------------------------------------===//230 231INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer",232 false, false)233 234FunctionPass *llvm::createHexagonCFGOptimizer() {235 return new HexagonCFGOptimizer();236}237