1630 lines · cpp
1//===- R600MachineCFGStructurizer.cpp - CFG Structurizer ------------------===//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 "MCTargetDesc/R600MCTargetDesc.h"10#include "R600.h"11#include "R600RegisterInfo.h"12#include "R600Subtarget.h"13#include "llvm/ADT/DepthFirstIterator.h"14#include "llvm/ADT/SCCIterator.h"15#include "llvm/ADT/Statistic.h"16#include "llvm/CodeGen/MachineFunction.h"17#include "llvm/CodeGen/MachineFunctionPass.h"18#include "llvm/CodeGen/MachineJumpTableInfo.h"19#include "llvm/CodeGen/MachineLoopInfo.h"20#include "llvm/CodeGen/MachinePostDominators.h"21#include "llvm/InitializePasses.h"22 23using namespace llvm;24 25#define DEBUG_TYPE "structcfg"26 27enum { DEFAULT_VEC_SLOTS = 8 };28 29// TODO: move-begin.30 31//===----------------------------------------------------------------------===//32//33// Statistics for CFGStructurizer.34//35//===----------------------------------------------------------------------===//36 37STATISTIC(numSerialPatternMatch, "CFGStructurizer number of serial pattern "38 "matched");39STATISTIC(numIfPatternMatch, "CFGStructurizer number of if pattern "40 "matched");41STATISTIC(numClonedBlock, "CFGStructurizer cloned blocks");42STATISTIC(numClonedInstr, "CFGStructurizer cloned instructions");43 44namespace {45 46//===----------------------------------------------------------------------===//47//48// Miscellaneous utility for CFGStructurizer.49//50//===----------------------------------------------------------------------===//51 52#define SHOWNEWINSTR(i) LLVM_DEBUG(dbgs() << "New instr: " << *i << "\n");53 54#define SHOWNEWBLK(b, msg) \55 LLVM_DEBUG(dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \56 dbgs() << "\n";);57 58#define SHOWBLK_DETAIL(b, msg) \59 LLVM_DEBUG(if (b) { \60 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \61 b->print(dbgs()); \62 dbgs() << "\n"; \63 });64 65#define INVALIDSCCNUM -166 67//===----------------------------------------------------------------------===//68//69// supporting data structure for CFGStructurizer70//71//===----------------------------------------------------------------------===//72 73class BlockInformation {74public:75 bool IsRetired = false;76 int SccNum = INVALIDSCCNUM;77 78 BlockInformation() = default;79};80 81//===----------------------------------------------------------------------===//82//83// CFGStructurizer84//85//===----------------------------------------------------------------------===//86 87class R600MachineCFGStructurizer : public MachineFunctionPass {88public:89 using MBBVector = SmallVector<MachineBasicBlock *, 32>;90 using MBBInfoMap = std::map<MachineBasicBlock *, BlockInformation *>;91 using LoopLandInfoMap = std::map<MachineLoop *, MachineBasicBlock *>;92 93 enum PathToKind {94 Not_SinglePath = 0,95 SinglePath_InPath = 1,96 SinglePath_NotInPath = 297 };98 99 static char ID;100 101 R600MachineCFGStructurizer() : MachineFunctionPass(ID) {}102 103 StringRef getPassName() const override {104 return "AMDGPU Control Flow Graph structurizer Pass";105 }106 107 void getAnalysisUsage(AnalysisUsage &AU) const override {108 AU.addRequired<MachineDominatorTreeWrapperPass>();109 AU.addRequired<MachinePostDominatorTreeWrapperPass>();110 AU.addRequired<MachineLoopInfoWrapperPass>();111 MachineFunctionPass::getAnalysisUsage(AU);112 }113 114 /// Perform the CFG structurization115 bool run();116 117 /// Perform the CFG preparation118 /// This step will remove every unconditionnal/dead jump instructions and make119 /// sure all loops have an exit block120 bool prepare();121 122 bool runOnMachineFunction(MachineFunction &MF) override {123 // FIXME: This pass causes verification failures.124 MF.getProperties().setFailsVerification();125 126 TII = MF.getSubtarget<R600Subtarget>().getInstrInfo();127 TRI = &TII->getRegisterInfo();128 LLVM_DEBUG(MF.dump(););129 OrderedBlks.clear();130 Visited.clear();131 FuncRep = &MF;132 MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();133 LLVM_DEBUG(dbgs() << "LoopInfo:\n"; PrintLoopinfo(*MLI););134 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();135 LLVM_DEBUG(MDT->print(dbgs()););136 PDT = &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();137 LLVM_DEBUG(PDT->print(dbgs()););138 prepare();139 run();140 LLVM_DEBUG(MF.dump(););141 return true;142 }143 144protected:145 MachineDominatorTree *MDT;146 MachinePostDominatorTree *PDT;147 MachineLoopInfo *MLI;148 const R600InstrInfo *TII = nullptr;149 const R600RegisterInfo *TRI = nullptr;150 151 // PRINT FUNCTIONS152 /// Print the ordered Blocks.153 void printOrderedBlocks() const {154 size_t i = 0;155 for (MBBVector::const_iterator iterBlk = OrderedBlks.begin(),156 iterBlkEnd = OrderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) {157 dbgs() << "BB" << (*iterBlk)->getNumber();158 dbgs() << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")";159 if (i != 0 && i % 10 == 0) {160 dbgs() << "\n";161 } else {162 dbgs() << " ";163 }164 }165 }166 167 static void PrintLoopinfo(const MachineLoopInfo &LoopInfo) {168 for (const MachineLoop *L : LoopInfo)169 L->print(dbgs());170 }171 172 // UTILITY FUNCTIONS173 int getSCCNum(MachineBasicBlock *MBB) const;174 MachineBasicBlock *getLoopLandInfo(MachineLoop *LoopRep) const;175 bool hasBackEdge(MachineBasicBlock *MBB) const;176 bool isRetiredBlock(MachineBasicBlock *MBB) const;177 bool isActiveLoophead(MachineBasicBlock *MBB) const;178 PathToKind singlePathTo(MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,179 bool AllowSideEntry = true) const;180 int countActiveBlock(MBBVector::const_iterator It,181 MBBVector::const_iterator E) const;182 bool needMigrateBlock(MachineBasicBlock *MBB) const;183 184 // Utility Functions185 void reversePredicateSetter(MachineBasicBlock::iterator I,186 MachineBasicBlock &MBB);187 /// Compute the reversed DFS post order of Blocks188 void orderBlocks(MachineFunction *MF);189 190 // Function originally from CFGStructTraits191 void insertInstrEnd(MachineBasicBlock *MBB, int NewOpcode,192 const DebugLoc &DL = DebugLoc());193 MachineInstr *insertInstrBefore(MachineBasicBlock *MBB, int NewOpcode,194 const DebugLoc &DL = DebugLoc());195 MachineInstr *insertInstrBefore(MachineBasicBlock::iterator I, int NewOpcode);196 void insertCondBranchBefore(MachineBasicBlock::iterator I, int NewOpcode,197 const DebugLoc &DL);198 void insertCondBranchBefore(MachineBasicBlock *MBB,199 MachineBasicBlock::iterator I, int NewOpcode,200 int RegNum, const DebugLoc &DL);201 202 static int getBranchNzeroOpcode(int OldOpcode);203 static int getBranchZeroOpcode(int OldOpcode);204 static int getContinueNzeroOpcode(int OldOpcode);205 static int getContinueZeroOpcode(int OldOpcode);206 static MachineBasicBlock *getTrueBranch(MachineInstr *MI);207 static void setTrueBranch(MachineInstr *MI, MachineBasicBlock *MBB);208 static MachineBasicBlock *getFalseBranch(MachineBasicBlock *MBB,209 MachineInstr *MI);210 static bool isCondBranch(MachineInstr *MI);211 static bool isUncondBranch(MachineInstr *MI);212 static DebugLoc getLastDebugLocInBB(MachineBasicBlock *MBB);213 static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *MBB);214 215 /// The correct naming for this is getPossibleLoopendBlockBranchInstr.216 ///217 /// BB with backward-edge could have move instructions after the branch218 /// instruction. Such move instruction "belong to" the loop backward-edge.219 MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *MBB);220 221 static MachineInstr *getReturnInstr(MachineBasicBlock *MBB);222 static bool isReturnBlock(MachineBasicBlock *MBB);223 static void cloneSuccessorList(MachineBasicBlock *DstMBB,224 MachineBasicBlock *SrcMBB);225 static MachineBasicBlock *clone(MachineBasicBlock *MBB);226 227 /// MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose228 /// because the AMDGPU instruction is not recognized as terminator fix this229 /// and retire this routine230 void replaceInstrUseOfBlockWith(MachineBasicBlock *SrcMBB,231 MachineBasicBlock *OldMBB, MachineBasicBlock *NewBlk);232 233 static void wrapup(MachineBasicBlock *MBB);234 235 int patternMatch(MachineBasicBlock *MBB);236 int patternMatchGroup(MachineBasicBlock *MBB);237 int serialPatternMatch(MachineBasicBlock *MBB);238 int ifPatternMatch(MachineBasicBlock *MBB);239 int loopendPatternMatch();240 int mergeLoop(MachineLoop *LoopRep);241 242 /// return true iff src1Blk->succ_empty() && src1Blk and src2Blk are in243 /// the same loop with LoopLandInfo without explicitly keeping track of244 /// loopContBlks and loopBreakBlks, this is a method to get the information.245 bool isSameloopDetachedContbreak(MachineBasicBlock *Src1MBB,246 MachineBasicBlock *Src2MBB);247 int handleJumpintoIf(MachineBasicBlock *HeadMBB,248 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);249 int handleJumpintoIfImp(MachineBasicBlock *HeadMBB,250 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);251 int improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,252 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,253 MachineBasicBlock **LandMBBPtr);254 void showImproveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,255 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,256 MachineBasicBlock *LandMBB, bool Detail = false);257 int cloneOnSideEntryTo(MachineBasicBlock *PreMBB,258 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB);259 void mergeSerialBlock(MachineBasicBlock *DstMBB,260 MachineBasicBlock *SrcMBB);261 262 void mergeIfthenelseBlock(MachineInstr *BranchMI,263 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,264 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB);265 void mergeLooplandBlock(MachineBasicBlock *DstMBB,266 MachineBasicBlock *LandMBB);267 void mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,268 MachineBasicBlock *LandMBB);269 void settleLoopcontBlock(MachineBasicBlock *ContingMBB,270 MachineBasicBlock *ContMBB);271 272 /// normalizeInfiniteLoopExit change273 /// B1:274 /// uncond_br LoopHeader275 ///276 /// to277 /// B1:278 /// cond_br 1 LoopHeader dummyExit279 /// and return the newly added dummy exit block280 MachineBasicBlock *normalizeInfiniteLoopExit(MachineLoop *LoopRep);281 void removeUnconditionalBranch(MachineBasicBlock *MBB);282 283 /// Remove duplicate branches instructions in a block.284 /// For instance285 /// B0:286 /// cond_br X B1 B2287 /// cond_br X B1 B2288 /// is transformed to289 /// B0:290 /// cond_br X B1 B2291 void removeRedundantConditionalBranch(MachineBasicBlock *MBB);292 293 void addDummyExitBlock(SmallVectorImpl<MachineBasicBlock *> &RetMBB);294 void removeSuccessor(MachineBasicBlock *MBB);295 MachineBasicBlock *cloneBlockForPredecessor(MachineBasicBlock *MBB,296 MachineBasicBlock *PredMBB);297 void migrateInstruction(MachineBasicBlock *SrcMBB,298 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I);299 void recordSccnum(MachineBasicBlock *MBB, int SCCNum);300 void retireBlock(MachineBasicBlock *MBB);301 302private:303 MBBInfoMap BlockInfoMap;304 LoopLandInfoMap LLInfoMap;305 std::map<MachineLoop *, bool> Visited;306 MachineFunction *FuncRep;307 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> OrderedBlks;308};309 310} // end anonymous namespace311 312char R600MachineCFGStructurizer::ID = 0;313 314int R600MachineCFGStructurizer::getSCCNum(MachineBasicBlock *MBB) const {315 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);316 if (It == BlockInfoMap.end())317 return INVALIDSCCNUM;318 return (*It).second->SccNum;319}320 321MachineBasicBlock *R600MachineCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep)322 const {323 LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep);324 if (It == LLInfoMap.end())325 return nullptr;326 return (*It).second;327}328 329bool R600MachineCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const {330 MachineLoop *LoopRep = MLI->getLoopFor(MBB);331 if (!LoopRep)332 return false;333 MachineBasicBlock *LoopHeader = LoopRep->getHeader();334 return MBB->isSuccessor(LoopHeader);335}336 337bool R600MachineCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const {338 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);339 if (It == BlockInfoMap.end())340 return false;341 return (*It).second->IsRetired;342}343 344bool R600MachineCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const {345 MachineLoop *LoopRep = MLI->getLoopFor(MBB);346 while (LoopRep && LoopRep->getHeader() == MBB) {347 MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep);348 if(!LoopLand)349 return true;350 if (!isRetiredBlock(LoopLand))351 return true;352 LoopRep = LoopRep->getParentLoop();353 }354 return false;355}356 357R600MachineCFGStructurizer::PathToKind R600MachineCFGStructurizer::singlePathTo(358 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,359 bool AllowSideEntry) const {360 assert(DstMBB);361 if (SrcMBB == DstMBB)362 return SinglePath_InPath;363 while (SrcMBB && SrcMBB->succ_size() == 1) {364 SrcMBB = *SrcMBB->succ_begin();365 if (SrcMBB == DstMBB)366 return SinglePath_InPath;367 if (!AllowSideEntry && SrcMBB->pred_size() > 1)368 return Not_SinglePath;369 }370 if (SrcMBB && SrcMBB->succ_size()==0)371 return SinglePath_NotInPath;372 return Not_SinglePath;373}374 375int R600MachineCFGStructurizer::countActiveBlock(MBBVector::const_iterator It,376 MBBVector::const_iterator E) const {377 int Count = 0;378 while (It != E) {379 if (!isRetiredBlock(*It))380 ++Count;381 ++It;382 }383 return Count;384}385 386bool R600MachineCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const {387 unsigned BlockSizeThreshold = 30;388 unsigned CloneInstrThreshold = 100;389 bool MultiplePreds = MBB && (MBB->pred_size() > 1);390 391 if(!MultiplePreds)392 return false;393 unsigned BlkSize = MBB->size();394 return ((BlkSize > BlockSizeThreshold) &&395 (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold));396}397 398void R600MachineCFGStructurizer::reversePredicateSetter(399 MachineBasicBlock::iterator I, MachineBasicBlock &MBB) {400 assert(I.isValid() && "Expected valid iterator");401 for (;; --I) {402 if (I == MBB.end())403 continue;404 if (I->getOpcode() == R600::PRED_X) {405 switch (I->getOperand(2).getImm()) {406 case R600::PRED_SETE_INT:407 I->getOperand(2).setImm(R600::PRED_SETNE_INT);408 return;409 case R600::PRED_SETNE_INT:410 I->getOperand(2).setImm(R600::PRED_SETE_INT);411 return;412 case R600::PRED_SETE:413 I->getOperand(2).setImm(R600::PRED_SETNE);414 return;415 case R600::PRED_SETNE:416 I->getOperand(2).setImm(R600::PRED_SETE);417 return;418 default:419 llvm_unreachable("PRED_X Opcode invalid!");420 }421 }422 }423}424 425void R600MachineCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB,426 int NewOpcode, const DebugLoc &DL) {427 MachineInstr *MI =428 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL);429 MBB->push_back(MI);430 //assume the instruction doesn't take any reg operand ...431 SHOWNEWINSTR(MI);432}433 434MachineInstr *R600MachineCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB,435 int NewOpcode,436 const DebugLoc &DL) {437 MachineInstr *MI =438 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL);439 if (!MBB->empty())440 MBB->insert(MBB->begin(), MI);441 else442 MBB->push_back(MI);443 SHOWNEWINSTR(MI);444 return MI;445}446 447MachineInstr *R600MachineCFGStructurizer::insertInstrBefore(448 MachineBasicBlock::iterator I, int NewOpcode) {449 MachineInstr *OldMI = &(*I);450 MachineBasicBlock *MBB = OldMI->getParent();451 MachineInstr *NewMBB =452 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DebugLoc());453 MBB->insert(I, NewMBB);454 //assume the instruction doesn't take any reg operand ...455 SHOWNEWINSTR(NewMBB);456 return NewMBB;457}458 459void R600MachineCFGStructurizer::insertCondBranchBefore(460 MachineBasicBlock::iterator I, int NewOpcode, const DebugLoc &DL) {461 MachineInstr *OldMI = &(*I);462 MachineBasicBlock *MBB = OldMI->getParent();463 MachineFunction *MF = MBB->getParent();464 MachineInstr *NewMI = MF->CreateMachineInstr(TII->get(NewOpcode), DL);465 MBB->insert(I, NewMI);466 MachineInstrBuilder MIB(*MF, NewMI);467 MIB.addReg(OldMI->getOperand(1).getReg(), false);468 SHOWNEWINSTR(NewMI);469 //erase later oldInstr->eraseFromParent();470}471 472void R600MachineCFGStructurizer::insertCondBranchBefore(473 MachineBasicBlock *blk, MachineBasicBlock::iterator I, int NewOpcode,474 int RegNum, const DebugLoc &DL) {475 MachineFunction *MF = blk->getParent();476 MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL);477 //insert before478 blk->insert(I, NewInstr);479 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);480 SHOWNEWINSTR(NewInstr);481}482 483int R600MachineCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) {484 switch(OldOpcode) {485 case R600::JUMP_COND:486 case R600::JUMP: return R600::IF_PREDICATE_SET;487 case R600::BRANCH_COND_i32:488 case R600::BRANCH_COND_f32: return R600::IF_LOGICALNZ_f32;489 default: llvm_unreachable("internal error");490 }491 return -1;492}493 494int R600MachineCFGStructurizer::getBranchZeroOpcode(int OldOpcode) {495 switch(OldOpcode) {496 case R600::JUMP_COND:497 case R600::JUMP: return R600::IF_PREDICATE_SET;498 case R600::BRANCH_COND_i32:499 case R600::BRANCH_COND_f32: return R600::IF_LOGICALZ_f32;500 default: llvm_unreachable("internal error");501 }502 return -1;503}504 505int R600MachineCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) {506 switch(OldOpcode) {507 case R600::JUMP_COND:508 case R600::JUMP: return R600::CONTINUE_LOGICALNZ_i32;509 default: llvm_unreachable("internal error");510 }511 return -1;512}513 514int R600MachineCFGStructurizer::getContinueZeroOpcode(int OldOpcode) {515 switch(OldOpcode) {516 case R600::JUMP_COND:517 case R600::JUMP: return R600::CONTINUE_LOGICALZ_i32;518 default: llvm_unreachable("internal error");519 }520 return -1;521}522 523MachineBasicBlock *R600MachineCFGStructurizer::getTrueBranch(MachineInstr *MI) {524 return MI->getOperand(0).getMBB();525}526 527void R600MachineCFGStructurizer::setTrueBranch(MachineInstr *MI,528 MachineBasicBlock *MBB) {529 MI->getOperand(0).setMBB(MBB);530}531 532MachineBasicBlock *533R600MachineCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB,534 MachineInstr *MI) {535 assert(MBB->succ_size() == 2);536 MachineBasicBlock *TrueBranch = getTrueBranch(MI);537 MachineBasicBlock::succ_iterator It = MBB->succ_begin();538 MachineBasicBlock::succ_iterator Next = It;539 ++Next;540 return (*It == TrueBranch) ? *Next : *It;541}542 543bool R600MachineCFGStructurizer::isCondBranch(MachineInstr *MI) {544 switch (MI->getOpcode()) {545 case R600::JUMP_COND:546 case R600::BRANCH_COND_i32:547 case R600::BRANCH_COND_f32: return true;548 default:549 return false;550 }551 return false;552}553 554bool R600MachineCFGStructurizer::isUncondBranch(MachineInstr *MI) {555 switch (MI->getOpcode()) {556 case R600::JUMP:557 case R600::BRANCH:558 return true;559 default:560 return false;561 }562 return false;563}564 565DebugLoc R600MachineCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) {566 //get DebugLoc from the first MachineBasicBlock instruction with debug info567 DebugLoc DL;568 for (MachineInstr &MI : *MBB)569 if (MI.getDebugLoc())570 DL = MI.getDebugLoc();571 return DL;572}573 574MachineInstr *R600MachineCFGStructurizer::getNormalBlockBranchInstr(575 MachineBasicBlock *MBB) {576 MachineBasicBlock::reverse_iterator It = MBB->rbegin();577 MachineInstr *MI = &*It;578 if (MI && (isCondBranch(MI) || isUncondBranch(MI)))579 return MI;580 return nullptr;581}582 583MachineInstr *R600MachineCFGStructurizer::getLoopendBlockBranchInstr(584 MachineBasicBlock *MBB) {585 for (MachineBasicBlock::reverse_iterator It = MBB->rbegin(), E = MBB->rend();586 It != E; ++It) {587 // FIXME: Simplify588 MachineInstr *MI = &*It;589 if (MI) {590 if (isCondBranch(MI) || isUncondBranch(MI))591 return MI;592 if (!TII->isMov(MI->getOpcode()))593 break;594 }595 }596 return nullptr;597}598 599MachineInstr *R600MachineCFGStructurizer::getReturnInstr(MachineBasicBlock *MBB) {600 MachineBasicBlock::reverse_iterator It = MBB->rbegin();601 if (It != MBB->rend()) {602 MachineInstr *instr = &(*It);603 if (instr->getOpcode() == R600::RETURN)604 return instr;605 }606 return nullptr;607}608 609bool R600MachineCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) {610 MachineInstr *MI = getReturnInstr(MBB);611 bool IsReturn = MBB->succ_empty();612 if (MI)613 assert(IsReturn);614 else if (IsReturn)615 LLVM_DEBUG(dbgs() << "BB" << MBB->getNumber()616 << " is return block without RETURN instr\n";);617 return IsReturn;618}619 620void R600MachineCFGStructurizer::cloneSuccessorList(MachineBasicBlock *DstMBB,621 MachineBasicBlock *SrcMBB) {622 for (MachineBasicBlock *Succ : SrcMBB->successors())623 DstMBB->addSuccessor(Succ); // *iter's predecessor is also taken care of624}625 626MachineBasicBlock *R600MachineCFGStructurizer::clone(MachineBasicBlock *MBB) {627 MachineFunction *Func = MBB->getParent();628 MachineBasicBlock *NewMBB = Func->CreateMachineBasicBlock();629 Func->push_back(NewMBB); //insert to function630 for (const MachineInstr &It : *MBB)631 NewMBB->push_back(Func->CloneMachineInstr(&It));632 return NewMBB;633}634 635void R600MachineCFGStructurizer::replaceInstrUseOfBlockWith(636 MachineBasicBlock *SrcMBB, MachineBasicBlock *OldMBB,637 MachineBasicBlock *NewBlk) {638 MachineInstr *BranchMI = getLoopendBlockBranchInstr(SrcMBB);639 if (BranchMI && isCondBranch(BranchMI) &&640 getTrueBranch(BranchMI) == OldMBB)641 setTrueBranch(BranchMI, NewBlk);642}643 644void R600MachineCFGStructurizer::wrapup(MachineBasicBlock *MBB) {645 assert((!MBB->getParent()->getJumpTableInfo()646 || MBB->getParent()->getJumpTableInfo()->isEmpty())647 && "found a jump table");648 649 //collect continue right before endloop650 SmallVector<MachineInstr *, DEFAULT_VEC_SLOTS> ContInstr;651 MachineBasicBlock::iterator Pre = MBB->begin();652 MachineBasicBlock::iterator E = MBB->end();653 MachineBasicBlock::iterator It = Pre;654 while (It != E) {655 if (Pre->getOpcode() == R600::CONTINUE656 && It->getOpcode() == R600::ENDLOOP)657 ContInstr.push_back(&*Pre);658 Pre = It;659 ++It;660 }661 662 //delete continue right before endloop663 for (auto *MI : ContInstr)664 MI->eraseFromParent();665 666 // TODO to fix up jump table so later phase won't be confused. if667 // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but668 // there isn't such an interface yet. alternatively, replace all the other669 // blocks in the jump table with the entryBlk //}670}671 672bool R600MachineCFGStructurizer::prepare() {673 bool Changed = false;674 675 //FIXME: if not reducible flow graph, make it so ???676 677 LLVM_DEBUG(dbgs() << "R600MachineCFGStructurizer::prepare\n";);678 679 orderBlocks(FuncRep);680 681 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> RetBlks;682 683 // Add an ExitBlk to loop that don't have one684 for (MachineLoop *LoopRep : *MLI) {685 MBBVector ExitingMBBs;686 LoopRep->getExitingBlocks(ExitingMBBs);687 688 if (ExitingMBBs.size() == 0) {689 MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep);690 if (DummyExitBlk)691 RetBlks.push_back(DummyExitBlk);692 }693 }694 695 // Remove unconditional branch instr.696 // Add dummy exit block iff there are multiple returns.697 for (MachineBasicBlock *MBB : OrderedBlks) {698 removeUnconditionalBranch(MBB);699 removeRedundantConditionalBranch(MBB);700 if (isReturnBlock(MBB)) {701 RetBlks.push_back(MBB);702 }703 assert(MBB->succ_size() <= 2);704 }705 706 if (RetBlks.size() >= 2) {707 addDummyExitBlock(RetBlks);708 Changed = true;709 }710 711 return Changed;712}713 714bool R600MachineCFGStructurizer::run() {715 //Assume reducible CFG...716 LLVM_DEBUG(dbgs() << "R600MachineCFGStructurizer::run\n");717 718#ifdef STRESSTEST719 //Use the worse block ordering to test the algorithm.720 ReverseVector(orderedBlks);721#endif722 723 LLVM_DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks(););724 int NumIter = 0;725 bool Finish = false;726 MachineBasicBlock *MBB;727 bool MakeProgress = false;728 int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(),729 OrderedBlks.end());730 731 do {732 ++NumIter;733 LLVM_DEBUG(dbgs() << "numIter = " << NumIter734 << ", numRemaintedBlk = " << NumRemainedBlk << "\n";);735 (void)NumIter;736 737 SmallVectorImpl<MachineBasicBlock *>::const_iterator It =738 OrderedBlks.begin();739 SmallVectorImpl<MachineBasicBlock *>::const_iterator E =740 OrderedBlks.end();741 742 SmallVectorImpl<MachineBasicBlock *>::const_iterator SccBeginIter =743 It;744 MachineBasicBlock *SccBeginMBB = nullptr;745 int SccNumBlk = 0; // The number of active blocks, init to a746 // maximum possible number.747 int SccNumIter; // Number of iteration in this SCC.748 749 while (It != E) {750 MBB = *It;751 752 if (!SccBeginMBB) {753 SccBeginIter = It;754 SccBeginMBB = MBB;755 SccNumIter = 0;756 SccNumBlk = NumRemainedBlk; // Init to maximum possible number.757 LLVM_DEBUG(dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB);758 dbgs() << "\n";);759 }760 761 if (!isRetiredBlock(MBB))762 patternMatch(MBB);763 764 ++It;765 766 bool ContNextScc = true;767 if (It == E768 || getSCCNum(SccBeginMBB) != getSCCNum(*It)) {769 // Just finish one scc.770 ++SccNumIter;771 int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It);772 if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) {773 LLVM_DEBUG(dbgs() << "Can't reduce SCC " << getSCCNum(MBB)774 << ", sccNumIter = " << SccNumIter;775 dbgs() << "doesn't make any progress\n";);776 (void)SccNumIter;777 ContNextScc = true;778 } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) {779 SccNumBlk = sccRemainedNumBlk;780 It = SccBeginIter;781 ContNextScc = false;782 LLVM_DEBUG(dbgs() << "repeat processing SCC" << getSCCNum(MBB)783 << "sccNumIter = " << SccNumIter << '\n';);784 } else {785 // Finish the current scc.786 ContNextScc = true;787 }788 } else {789 // Continue on next component in the current scc.790 ContNextScc = false;791 }792 793 if (ContNextScc)794 SccBeginMBB = nullptr;795 } //while, "one iteration" over the function.796 797 MachineBasicBlock *EntryMBB =798 *GraphTraits<MachineFunction *>::nodes_begin(FuncRep);799 if (EntryMBB->succ_empty()) {800 Finish = true;801 LLVM_DEBUG(dbgs() << "Reduce to one block\n";);802 } else {803 int NewnumRemainedBlk804 = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end());805 // consider cloned blocks ??806 if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) {807 MakeProgress = true;808 NumRemainedBlk = NewnumRemainedBlk;809 } else {810 MakeProgress = false;811 LLVM_DEBUG(dbgs() << "No progress\n";);812 }813 }814 } while (!Finish && MakeProgress);815 816 // Misc wrap up to maintain the consistency of the Function representation.817 wrapup(*GraphTraits<MachineFunction *>::nodes_begin(FuncRep));818 819 // Detach retired Block, release memory.820 for (auto &It : BlockInfoMap) {821 if (It.second && It.second->IsRetired) {822 assert((It.first)->getNumber() != -1);823 LLVM_DEBUG(dbgs() << "Erase BB" << (It.first)->getNumber() << "\n";);824 It.first->eraseFromParent(); // Remove from the parent Function.825 }826 delete It.second;827 }828 BlockInfoMap.clear();829 LLInfoMap.clear();830 831 if (!Finish) {832 LLVM_DEBUG(FuncRep->viewCFG());833 report_fatal_error("IRREDUCIBLE_CFG");834 }835 836 return true;837}838 839void R600MachineCFGStructurizer::orderBlocks(MachineFunction *MF) {840 int SccNum = 0;841 for (scc_iterator<MachineFunction *> It = scc_begin(MF); !It.isAtEnd();842 ++It, ++SccNum) {843 const std::vector<MachineBasicBlock *> &SccNext = *It;844 for (MachineBasicBlock *MBB : SccNext) {845 OrderedBlks.push_back(MBB);846 recordSccnum(MBB, SccNum);847 }848 }849 850 // walk through all the block in func to check for unreachable851 for (auto *MBB : nodes(MF)) {852 SccNum = getSCCNum(MBB);853 if (SccNum == INVALIDSCCNUM)854 dbgs() << "unreachable block BB" << MBB->getNumber() << "\n";855 }856}857 858int R600MachineCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {859 int NumMatch = 0;860 int CurMatch;861 862 LLVM_DEBUG(dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";);863 864 while ((CurMatch = patternMatchGroup(MBB)) > 0)865 NumMatch += CurMatch;866 867 LLVM_DEBUG(dbgs() << "End patternMatch BB" << MBB->getNumber()868 << ", numMatch = " << NumMatch << "\n";);869 870 return NumMatch;871}872 873int R600MachineCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) {874 int NumMatch = 0;875 NumMatch += loopendPatternMatch();876 NumMatch += serialPatternMatch(MBB);877 NumMatch += ifPatternMatch(MBB);878 return NumMatch;879}880 881int R600MachineCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) {882 if (MBB->succ_size() != 1)883 return 0;884 885 MachineBasicBlock *childBlk = *MBB->succ_begin();886 if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk))887 return 0;888 889 mergeSerialBlock(MBB, childBlk);890 ++numSerialPatternMatch;891 return 1;892}893 894int R600MachineCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) {895 //two edges896 if (MBB->succ_size() != 2)897 return 0;898 if (hasBackEdge(MBB))899 return 0;900 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);901 if (!BranchMI)902 return 0;903 904 assert(isCondBranch(BranchMI));905 int NumMatch = 0;906 907 MachineBasicBlock *TrueMBB = getTrueBranch(BranchMI);908 NumMatch += serialPatternMatch(TrueMBB);909 NumMatch += ifPatternMatch(TrueMBB);910 MachineBasicBlock *FalseMBB = getFalseBranch(MBB, BranchMI);911 NumMatch += serialPatternMatch(FalseMBB);912 NumMatch += ifPatternMatch(FalseMBB);913 MachineBasicBlock *LandBlk;914 int Cloned = 0;915 916 assert (!TrueMBB->succ_empty() || !FalseMBB->succ_empty());917 // TODO: Simplify918 if (TrueMBB->succ_size() == 1 && FalseMBB->succ_size() == 1919 && *TrueMBB->succ_begin() == *FalseMBB->succ_begin()) {920 // Diamond pattern921 LandBlk = *TrueMBB->succ_begin();922 } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) {923 // Triangle pattern, false is empty924 LandBlk = FalseMBB;925 FalseMBB = nullptr;926 } else if (FalseMBB->succ_size() == 1927 && *FalseMBB->succ_begin() == TrueMBB) {928 // Triangle pattern, true is empty929 // We reverse the predicate to make a triangle, empty false pattern;930 std::swap(TrueMBB, FalseMBB);931 reversePredicateSetter(MBB->end(), *MBB);932 LandBlk = FalseMBB;933 FalseMBB = nullptr;934 } else if (FalseMBB->succ_size() == 1935 && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) {936 LandBlk = *FalseMBB->succ_begin();937 } else if (TrueMBB->succ_size() == 1938 && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) {939 LandBlk = *TrueMBB->succ_begin();940 } else {941 return NumMatch + handleJumpintoIf(MBB, TrueMBB, FalseMBB);942 }943 944 // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the945 // new BB created for landBlk==NULL may introduce new challenge to the946 // reduction process.947 if (LandBlk &&948 ((TrueMBB && TrueMBB->pred_size() > 1)949 || (FalseMBB && FalseMBB->pred_size() > 1))) {950 Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk);951 }952 953 if (TrueMBB && TrueMBB->pred_size() > 1) {954 TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB);955 ++Cloned;956 }957 958 if (FalseMBB && FalseMBB->pred_size() > 1) {959 FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB);960 ++Cloned;961 }962 963 mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk);964 965 ++numIfPatternMatch;966 967 numClonedBlock += Cloned;968 969 return 1 + Cloned + NumMatch;970}971 972int R600MachineCFGStructurizer::loopendPatternMatch() {973 std::deque<MachineLoop *> NestedLoops;974 for (auto &It: *MLI)975 for (MachineLoop *ML : depth_first(It))976 NestedLoops.push_front(ML);977 978 if (NestedLoops.empty())979 return 0;980 981 // Process nested loop outside->inside (we did push_front),982 // so "continue" to a outside loop won't be mistaken as "break"983 // of the current loop.984 int Num = 0;985 for (MachineLoop *ExaminedLoop : NestedLoops) {986 if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop])987 continue;988 LLVM_DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump(););989 int NumBreak = mergeLoop(ExaminedLoop);990 if (NumBreak == -1)991 break;992 Num += NumBreak;993 }994 return Num;995}996 997int R600MachineCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {998 MachineBasicBlock *LoopHeader = LoopRep->getHeader();999 MBBVector ExitingMBBs;1000 LoopRep->getExitingBlocks(ExitingMBBs);1001 assert(!ExitingMBBs.empty() && "Infinite Loop not supported");1002 LLVM_DEBUG(dbgs() << "Loop has " << ExitingMBBs.size()1003 << " exiting blocks\n";);1004 // We assume a single ExitBlk1005 MBBVector ExitBlks;1006 LoopRep->getExitBlocks(ExitBlks);1007 SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet(llvm::from_range, ExitBlks);1008 assert(ExitBlkSet.size() == 1);1009 MachineBasicBlock *ExitBlk = *ExitBlks.begin();1010 assert(ExitBlk && "Loop has several exit block");1011 MBBVector LatchBlks;1012 for (auto *LB : inverse_children<MachineBasicBlock*>(LoopHeader))1013 if (LoopRep->contains(LB))1014 LatchBlks.push_back(LB);1015 1016 for (MachineBasicBlock *MBB : ExitingMBBs)1017 mergeLoopbreakBlock(MBB, ExitBlk);1018 for (MachineBasicBlock *MBB : LatchBlks)1019 settleLoopcontBlock(MBB, LoopHeader);1020 int Match = 0;1021 do {1022 Match = 0;1023 Match += serialPatternMatch(LoopHeader);1024 Match += ifPatternMatch(LoopHeader);1025 } while (Match > 0);1026 mergeLooplandBlock(LoopHeader, ExitBlk);1027 MachineLoop *ParentLoop = LoopRep->getParentLoop();1028 if (ParentLoop)1029 MLI->changeLoopFor(LoopHeader, ParentLoop);1030 else1031 MLI->removeBlock(LoopHeader);1032 Visited[LoopRep] = true;1033 return 1;1034}1035 1036bool R600MachineCFGStructurizer::isSameloopDetachedContbreak(1037 MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) {1038 if (Src1MBB->succ_empty()) {1039 MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB);1040 if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) {1041 MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep];1042 if (TheEntry) {1043 LLVM_DEBUG(dbgs() << "isLoopContBreakBlock yes src1 = BB"1044 << Src1MBB->getNumber() << " src2 = BB"1045 << Src2MBB->getNumber() << "\n";);1046 return true;1047 }1048 }1049 }1050 return false;1051}1052 1053int R600MachineCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB,1054 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {1055 int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB);1056 if (Num == 0) {1057 LLVM_DEBUG(dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk"1058 << "\n";);1059 Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB);1060 }1061 return Num;1062}1063 1064int R600MachineCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB,1065 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {1066 int Num = 0;1067 MachineBasicBlock *DownBlk;1068 1069 //trueBlk could be the common post dominator1070 DownBlk = TrueMBB;1071 1072 LLVM_DEBUG(dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber()1073 << " true = BB" << TrueMBB->getNumber()1074 << ", numSucc=" << TrueMBB->succ_size() << " false = BB"1075 << FalseMBB->getNumber() << "\n";);1076 1077 while (DownBlk) {1078 LLVM_DEBUG(dbgs() << "check down = BB" << DownBlk->getNumber(););1079 1080 if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) {1081 LLVM_DEBUG(dbgs() << " working\n";);1082 1083 Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk);1084 Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk);1085 1086 numClonedBlock += Num;1087 Num += serialPatternMatch(*HeadMBB->succ_begin());1088 Num += serialPatternMatch(*std::next(HeadMBB->succ_begin()));1089 Num += ifPatternMatch(HeadMBB);1090 assert(Num > 0);1091 1092 break;1093 }1094 LLVM_DEBUG(dbgs() << " not working\n";);1095 DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : nullptr;1096 } // walk down the postDomTree1097 1098 return Num;1099}1100 1101#ifndef NDEBUG1102void R600MachineCFGStructurizer::showImproveSimpleJumpintoIf(1103 MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB,1104 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) {1105 dbgs() << "head = BB" << HeadMBB->getNumber()1106 << " size = " << HeadMBB->size();1107 if (Detail) {1108 dbgs() << "\n";1109 HeadMBB->print(dbgs());1110 dbgs() << "\n";1111 }1112 1113 if (TrueMBB) {1114 dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = "1115 << TrueMBB->size() << " numPred = " << TrueMBB->pred_size();1116 if (Detail) {1117 dbgs() << "\n";1118 TrueMBB->print(dbgs());1119 dbgs() << "\n";1120 }1121 }1122 if (FalseMBB) {1123 dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = "1124 << FalseMBB->size() << " numPred = " << FalseMBB->pred_size();1125 if (Detail) {1126 dbgs() << "\n";1127 FalseMBB->print(dbgs());1128 dbgs() << "\n";1129 }1130 }1131 if (LandMBB) {1132 dbgs() << ", land = BB" << LandMBB->getNumber() << " size = "1133 << LandMBB->size() << " numPred = " << LandMBB->pred_size();1134 if (Detail) {1135 dbgs() << "\n";1136 LandMBB->print(dbgs());1137 dbgs() << "\n";1138 }1139 }1140 1141 dbgs() << "\n";1142}1143#endif1144 1145int R600MachineCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,1146 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,1147 MachineBasicBlock **LandMBBPtr) {1148 bool MigrateTrue = false;1149 bool MigrateFalse = false;1150 1151 MachineBasicBlock *LandBlk = *LandMBBPtr;1152 1153 assert((!TrueMBB || TrueMBB->succ_size() <= 1)1154 && (!FalseMBB || FalseMBB->succ_size() <= 1));1155 1156 if (TrueMBB == FalseMBB)1157 return 0;1158 1159 MigrateTrue = needMigrateBlock(TrueMBB);1160 MigrateFalse = needMigrateBlock(FalseMBB);1161 1162 if (!MigrateTrue && !MigrateFalse)1163 return 0;1164 1165 // If we need to migrate either trueBlk and falseBlk, migrate the rest that1166 // have more than one predecessors. without doing this, its predecessor1167 // rather than headBlk will have undefined value in initReg.1168 if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1)1169 MigrateTrue = true;1170 if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1)1171 MigrateFalse = true;1172 1173 LLVM_DEBUG(1174 dbgs() << "before improveSimpleJumpintoIf: ";1175 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0););1176 1177 // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk1178 //1179 // new: headBlk => if () {initReg = 1; org trueBlk branch} else1180 // {initReg = 0; org falseBlk branch }1181 // => landBlk => if (initReg) {org trueBlk} else {org falseBlk}1182 // => org landBlk1183 // if landBlk->pred_size() > 2, put the about if-else inside1184 // if (initReg !=2) {...}1185 //1186 // add initReg = initVal to headBlk1187 1188 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);1189 if (!MigrateTrue || !MigrateFalse) {1190 // XXX: We have an opportunity here to optimize the "branch into if" case1191 // here. Branch into if looks like this:1192 // entry1193 // / |1194 // diamond_head branch_from1195 // / \ |1196 // diamond_false diamond_true1197 // \ /1198 // done1199 //1200 // The diamond_head block begins the "if" and the diamond_true block1201 // is the block being "branched into".1202 //1203 // If MigrateTrue is true, then TrueBB is the block being "branched into"1204 // and if MigrateFalse is true, then FalseBB is the block being1205 // "branched into"1206 //1207 // Here is the pseudo code for how I think the optimization should work:1208 // 1. Insert MOV GPR0, 0 before the branch instruction in diamond_head.1209 // 2. Insert MOV GPR0, 1 before the branch instruction in branch_from.1210 // 3. Move the branch instruction from diamond_head into its own basic1211 // block (new_block).1212 // 4. Add an unconditional branch from diamond_head to new_block1213 // 5. Replace the branch instruction in branch_from with an unconditional1214 // branch to new_block. If branch_from has multiple predecessors, then1215 // we need to replace the True/False block in the branch1216 // instruction instead of replacing it.1217 // 6. Change the condition of the branch instruction in new_block from1218 // COND to (COND || GPR0)1219 //1220 // In order insert these MOV instruction, we will need to use the1221 // RegisterScavenger. Usually liveness stops being tracked during1222 // the late machine optimization passes, however if we implement1223 // bool TargetRegisterInfo::requiresRegisterScavenging(1224 // const MachineFunction &MF)1225 // and have it return true, liveness will be tracked correctly1226 // by generic optimization passes. We will also need to make sure that1227 // all of our target-specific passes that run after regalloc and before1228 // the CFGStructurizer track liveness and we will need to modify this pass1229 // to correctly track liveness.1230 //1231 // After the above changes, the new CFG should look like this:1232 // entry1233 // / |1234 // diamond_head branch_from1235 // \ /1236 // new_block1237 // / |1238 // diamond_false diamond_true1239 // \ /1240 // done1241 //1242 // Without this optimization, we are forced to duplicate the diamond_true1243 // block and we will end up with a CFG like this:1244 //1245 // entry1246 // / |1247 // diamond_head branch_from1248 // / \ |1249 // diamond_false diamond_true diamond_true (duplicate)1250 // \ / |1251 // done --------------------|1252 //1253 // Duplicating diamond_true can be very costly especially if it has a1254 // lot of instructions.1255 return 0;1256 }1257 1258 int NumNewBlk = 0;1259 1260 bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2);1261 1262 //insert R600::ENDIF to avoid special case "input landBlk == NULL"1263 MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, R600::ENDIF);1264 1265 if (LandBlkHasOtherPred) {1266 report_fatal_error("Extra register needed to handle CFG");1267 Register CmpResReg =1268 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);1269 report_fatal_error("Extra compare instruction needed to handle CFG");1270 insertCondBranchBefore(LandBlk, I, R600::IF_PREDICATE_SET,1271 CmpResReg, DebugLoc());1272 }1273 1274 // XXX: We are running this after RA, so creating virtual registers will1275 // cause an assertion failure in the PostRA scheduling pass.1276 Register InitReg =1277 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);1278 insertCondBranchBefore(LandBlk, I, R600::IF_PREDICATE_SET, InitReg,1279 DebugLoc());1280 1281 if (MigrateTrue) {1282 migrateInstruction(TrueMBB, LandBlk, I);1283 // need to uncondionally insert the assignment to ensure a path from its1284 // predecessor rather than headBlk has valid value in initReg if1285 // (initVal != 1).1286 report_fatal_error("Extra register needed to handle CFG");1287 }1288 insertInstrBefore(I, R600::ELSE);1289 1290 if (MigrateFalse) {1291 migrateInstruction(FalseMBB, LandBlk, I);1292 // need to uncondionally insert the assignment to ensure a path from its1293 // predecessor rather than headBlk has valid value in initReg if1294 // (initVal != 0)1295 report_fatal_error("Extra register needed to handle CFG");1296 }1297 1298 if (LandBlkHasOtherPred) {1299 // add endif1300 insertInstrBefore(I, R600::ENDIF);1301 1302 // put initReg = 2 to other predecessors of landBlk1303 for (MachineBasicBlock *MBB : LandBlk->predecessors())1304 if (MBB != TrueMBB && MBB != FalseMBB)1305 report_fatal_error("Extra register needed to handle CFG");1306 }1307 LLVM_DEBUG(1308 dbgs() << "result from improveSimpleJumpintoIf: ";1309 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0););1310 1311 // update landBlk1312 *LandMBBPtr = LandBlk;1313 1314 return NumNewBlk;1315}1316 1317void R600MachineCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,1318 MachineBasicBlock *SrcMBB) {1319 LLVM_DEBUG(dbgs() << "serialPattern BB" << DstMBB->getNumber() << " <= BB"1320 << SrcMBB->getNumber() << "\n";);1321 DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());1322 1323 DstMBB->removeSuccessor(SrcMBB, true);1324 cloneSuccessorList(DstMBB, SrcMBB);1325 1326 removeSuccessor(SrcMBB);1327 MLI->removeBlock(SrcMBB);1328 retireBlock(SrcMBB);1329}1330 1331void R600MachineCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,1332 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,1333 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) {1334 assert (TrueMBB);1335 LLVM_DEBUG(dbgs() << "ifPattern BB" << MBB->getNumber(); dbgs() << "{ ";1336 if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs()1337 << " } else ";1338 dbgs() << "{ "; if (FalseMBB) {1339 dbgs() << "BB" << FalseMBB->getNumber();1340 } dbgs() << " }\n ";1341 dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else {1342 dbgs() << "BB" << LandMBB->getNumber();1343 } dbgs() << "\n";);1344 1345 int OldOpcode = BranchMI->getOpcode();1346 DebugLoc BranchDL = BranchMI->getDebugLoc();1347 1348// transform to1349// if cond1350// trueBlk1351// else1352// falseBlk1353// endif1354// landBlk1355 1356 MachineBasicBlock::iterator I = BranchMI;1357 insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode),1358 BranchDL);1359 1360 if (TrueMBB) {1361 MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());1362 MBB->removeSuccessor(TrueMBB, true);1363 if (LandMBB && TrueMBB->succ_size()!=0)1364 TrueMBB->removeSuccessor(LandMBB, true);1365 retireBlock(TrueMBB);1366 MLI->removeBlock(TrueMBB);1367 }1368 1369 if (FalseMBB) {1370 insertInstrBefore(I, R600::ELSE);1371 MBB->splice(I, FalseMBB, FalseMBB->begin(),1372 FalseMBB->end());1373 MBB->removeSuccessor(FalseMBB, true);1374 if (LandMBB && !FalseMBB->succ_empty())1375 FalseMBB->removeSuccessor(LandMBB, true);1376 retireBlock(FalseMBB);1377 MLI->removeBlock(FalseMBB);1378 }1379 insertInstrBefore(I, R600::ENDIF);1380 1381 BranchMI->eraseFromParent();1382 1383 if (LandMBB && TrueMBB && FalseMBB)1384 MBB->addSuccessor(LandMBB);1385}1386 1387void R600MachineCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk,1388 MachineBasicBlock *LandMBB) {1389 LLVM_DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber()1390 << " land = BB" << LandMBB->getNumber() << "\n";);1391 1392 insertInstrBefore(DstBlk, R600::WHILELOOP, DebugLoc());1393 insertInstrEnd(DstBlk, R600::ENDLOOP, DebugLoc());1394 DstBlk->replaceSuccessor(DstBlk, LandMBB);1395}1396 1397void R600MachineCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,1398 MachineBasicBlock *LandMBB) {1399 LLVM_DEBUG(dbgs() << "loopbreakPattern exiting = BB"1400 << ExitingMBB->getNumber() << " land = BB"1401 << LandMBB->getNumber() << "\n";);1402 MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB);1403 assert(BranchMI && isCondBranch(BranchMI));1404 DebugLoc DL = BranchMI->getDebugLoc();1405 MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI);1406 MachineBasicBlock::iterator I = BranchMI;1407 if (TrueBranch != LandMBB)1408 reversePredicateSetter(I, *I->getParent());1409 insertCondBranchBefore(ExitingMBB, I, R600::IF_PREDICATE_SET, R600::PREDICATE_BIT, DL);1410 insertInstrBefore(I, R600::BREAK);1411 insertInstrBefore(I, R600::ENDIF);1412 //now branchInst can be erase safely1413 BranchMI->eraseFromParent();1414 //now take care of successors, retire blocks1415 ExitingMBB->removeSuccessor(LandMBB, true);1416}1417 1418void R600MachineCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,1419 MachineBasicBlock *ContMBB) {1420 LLVM_DEBUG(dbgs() << "settleLoopcontBlock conting = BB"1421 << ContingMBB->getNumber() << ", cont = BB"1422 << ContMBB->getNumber() << "\n";);1423 1424 MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB);1425 if (MI) {1426 assert(isCondBranch(MI));1427 MachineBasicBlock::iterator I = MI;1428 MachineBasicBlock *TrueBranch = getTrueBranch(MI);1429 int OldOpcode = MI->getOpcode();1430 DebugLoc DL = MI->getDebugLoc();1431 1432 bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI);1433 1434 if (!UseContinueLogical) {1435 int BranchOpcode =1436 TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) :1437 getBranchZeroOpcode(OldOpcode);1438 insertCondBranchBefore(I, BranchOpcode, DL);1439 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.1440 insertInstrEnd(ContingMBB, R600::CONTINUE, DL);1441 insertInstrEnd(ContingMBB, R600::ENDIF, DL);1442 } else {1443 int BranchOpcode =1444 TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) :1445 getContinueZeroOpcode(OldOpcode);1446 insertCondBranchBefore(I, BranchOpcode, DL);1447 }1448 1449 MI->eraseFromParent();1450 } else {1451 // if we've arrived here then we've already erased the branch instruction1452 // travel back up the basic block to see the last reference of our debug1453 // location we've just inserted that reference here so it should be1454 // representative insertEnd to ensure phi-moves, if exist, go before the1455 // continue-instr.1456 insertInstrEnd(ContingMBB, R600::CONTINUE,1457 getLastDebugLocInBB(ContingMBB));1458 }1459}1460 1461int R600MachineCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB,1462 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) {1463 int Cloned = 0;1464 assert(PreMBB->isSuccessor(SrcMBB));1465 while (SrcMBB && SrcMBB != DstMBB) {1466 assert(SrcMBB->succ_size() == 1);1467 if (SrcMBB->pred_size() > 1) {1468 SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB);1469 ++Cloned;1470 }1471 1472 PreMBB = SrcMBB;1473 SrcMBB = *SrcMBB->succ_begin();1474 }1475 1476 return Cloned;1477}1478 1479MachineBasicBlock *1480R600MachineCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB,1481 MachineBasicBlock *PredMBB) {1482 assert(PredMBB->isSuccessor(MBB) && "succBlk is not a predecessor of curBlk");1483 1484 MachineBasicBlock *CloneMBB = clone(MBB); //clone instructions1485 replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB);1486 //srcBlk, oldBlk, newBlk1487 1488 PredMBB->replaceSuccessor(MBB, CloneMBB);1489 1490 // add all successor to cloneBlk1491 cloneSuccessorList(CloneMBB, MBB);1492 1493 numClonedInstr += MBB->size();1494 1495 LLVM_DEBUG(dbgs() << "Cloned block: "1496 << "BB" << MBB->getNumber() << "size " << MBB->size()1497 << "\n";);1498 1499 SHOWNEWBLK(CloneMBB, "result of Cloned block: ");1500 1501 return CloneMBB;1502}1503 1504void R600MachineCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB,1505 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I) {1506 MachineBasicBlock::iterator SpliceEnd;1507 //look for the input branchinstr, not the AMDGPU branchinstr1508 MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB);1509 if (!BranchMI) {1510 LLVM_DEBUG(dbgs() << "migrateInstruction don't see branch instr\n";);1511 SpliceEnd = SrcMBB->end();1512 } else {1513 LLVM_DEBUG(dbgs() << "migrateInstruction see branch instr: " << *BranchMI);1514 SpliceEnd = BranchMI;1515 }1516 LLVM_DEBUG(dbgs() << "migrateInstruction before splice dstSize = "1517 << DstMBB->size() << "srcSize = " << SrcMBB->size()1518 << "\n";);1519 1520 //splice insert before insertPos1521 DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd);1522 1523 LLVM_DEBUG(dbgs() << "migrateInstruction after splice dstSize = "1524 << DstMBB->size() << "srcSize = " << SrcMBB->size()1525 << '\n';);1526}1527 1528MachineBasicBlock *1529R600MachineCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) {1530 MachineBasicBlock *LoopHeader = LoopRep->getHeader();1531 MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch();1532 1533 if (!LoopHeader || !LoopLatch)1534 return nullptr;1535 MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch);1536 // Is LoopRep an infinite loop ?1537 if (!BranchMI || !isUncondBranch(BranchMI))1538 return nullptr;1539 1540 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();1541 FuncRep->push_back(DummyExitBlk); //insert to function1542 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");1543 LLVM_DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";);1544 LLVMContext &Ctx = LoopHeader->getParent()->getFunction().getContext();1545 Ctx.emitError("Extra register needed to handle CFG");1546 return nullptr;1547}1548 1549void R600MachineCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) {1550 MachineInstr *BranchMI;1551 1552 // I saw two unconditional branch in one basic block in example1553 // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.1554 while ((BranchMI = getLoopendBlockBranchInstr(MBB))1555 && isUncondBranch(BranchMI)) {1556 LLVM_DEBUG(dbgs() << "Removing uncond branch instr: " << *BranchMI);1557 BranchMI->eraseFromParent();1558 }1559}1560 1561void R600MachineCFGStructurizer::removeRedundantConditionalBranch(1562 MachineBasicBlock *MBB) {1563 if (MBB->succ_size() != 2)1564 return;1565 MachineBasicBlock *MBB1 = *MBB->succ_begin();1566 MachineBasicBlock *MBB2 = *std::next(MBB->succ_begin());1567 if (MBB1 != MBB2)1568 return;1569 1570 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);1571 assert(BranchMI && isCondBranch(BranchMI));1572 LLVM_DEBUG(dbgs() << "Removing unneeded cond branch instr: " << *BranchMI);1573 BranchMI->eraseFromParent();1574 SHOWNEWBLK(MBB1, "Removing redundant successor");1575 MBB->removeSuccessor(MBB1, true);1576}1577 1578void R600MachineCFGStructurizer::addDummyExitBlock(1579 SmallVectorImpl<MachineBasicBlock*> &RetMBB) {1580 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();1581 FuncRep->push_back(DummyExitBlk); //insert to function1582 insertInstrEnd(DummyExitBlk, R600::RETURN);1583 1584 for (MachineBasicBlock *MBB : RetMBB) {1585 if (MachineInstr *MI = getReturnInstr(MBB))1586 MI->eraseFromParent();1587 MBB->addSuccessor(DummyExitBlk);1588 LLVM_DEBUG(dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber()1589 << " successors\n";);1590 }1591 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ");1592}1593 1594void R600MachineCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) {1595 while (MBB->succ_size())1596 MBB->removeSuccessor(*MBB->succ_begin());1597}1598 1599void R600MachineCFGStructurizer::recordSccnum(MachineBasicBlock *MBB,1600 int SccNum) {1601 BlockInformation *&srcBlkInfo = BlockInfoMap[MBB];1602 if (!srcBlkInfo)1603 srcBlkInfo = new BlockInformation();1604 srcBlkInfo->SccNum = SccNum;1605}1606 1607void R600MachineCFGStructurizer::retireBlock(MachineBasicBlock *MBB) {1608 LLVM_DEBUG(dbgs() << "Retiring BB" << MBB->getNumber() << "\n";);1609 1610 BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB];1611 1612 if (!SrcBlkInfo)1613 SrcBlkInfo = new BlockInformation();1614 1615 SrcBlkInfo->IsRetired = true;1616 assert(MBB->succ_empty() && MBB->pred_empty() && "can't retire block yet");1617}1618 1619INITIALIZE_PASS_BEGIN(R600MachineCFGStructurizer, "amdgpustructurizer",1620 "AMDGPU CFG Structurizer", false, false)1621INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)1622INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)1623INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)1624INITIALIZE_PASS_END(R600MachineCFGStructurizer, "amdgpustructurizer",1625 "AMDGPU CFG Structurizer", false, false)1626 1627FunctionPass *llvm::createR600MachineCFGStructurizerPass() {1628 return new R600MachineCFGStructurizer();1629}1630