BranchFolding.cpp revision 7d33b4c59b56afb96feea71073c1d9e70c457e28
1//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass forwards branches to unconditional branches to make them branch 11// directly to the target block. This pass often results in dead MBB's, which 12// it then removes. 13// 14// Note that this pass must be run after register allocation, it cannot handle 15// SSA form. 16// 17//===----------------------------------------------------------------------===// 18 19#define DEBUG_TYPE "branchfolding" 20#include "llvm/CodeGen/Passes.h" 21#include "llvm/CodeGen/MachineModuleInfo.h" 22#include "llvm/CodeGen/MachineFunctionPass.h" 23#include "llvm/CodeGen/MachineJumpTableInfo.h" 24#include "llvm/CodeGen/RegisterScavenging.h" 25#include "llvm/Target/TargetInstrInfo.h" 26#include "llvm/Target/TargetMachine.h" 27#include "llvm/Target/MRegisterInfo.h" 28#include "llvm/Support/CommandLine.h" 29#include "llvm/Support/Debug.h" 30#include "llvm/ADT/Statistic.h" 31#include "llvm/ADT/STLExtras.h" 32#include <algorithm> 33using namespace llvm; 34 35STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 36STATISTIC(NumBranchOpts, "Number of branches optimized"); 37STATISTIC(NumTailMerge , "Number of block tails merged"); 38static cl::opt<bool> EnableTailMerge("enable-tail-merge", cl::Hidden); 39 40namespace { 41 struct BranchFolder : public MachineFunctionPass { 42 static char ID; 43 BranchFolder() : MachineFunctionPass((intptr_t)&ID) {} 44 45 virtual bool runOnMachineFunction(MachineFunction &MF); 46 virtual const char *getPassName() const { return "Control Flow Optimizer"; } 47 const TargetInstrInfo *TII; 48 MachineModuleInfo *MMI; 49 bool MadeChange; 50 private: 51 // Tail Merging. 52 bool TailMergeBlocks(MachineFunction &MF); 53 bool TryMergeBlocks(MachineBasicBlock* SuccBB, 54 MachineBasicBlock* PredBB); 55 void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 56 MachineBasicBlock *NewDest); 57 MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 58 MachineBasicBlock::iterator BBI1); 59 60 std::vector<std::pair<unsigned,MachineBasicBlock*> > MergePotentials; 61 const MRegisterInfo *RegInfo; 62 RegScavenger *RS; 63 // Branch optzn. 64 bool OptimizeBranches(MachineFunction &MF); 65 void OptimizeBlock(MachineBasicBlock *MBB); 66 void RemoveDeadBlock(MachineBasicBlock *MBB); 67 68 bool CanFallThrough(MachineBasicBlock *CurBB); 69 bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable, 70 MachineBasicBlock *TBB, MachineBasicBlock *FBB, 71 const std::vector<MachineOperand> &Cond); 72 }; 73 char BranchFolder::ID = 0; 74} 75 76FunctionPass *llvm::createBranchFoldingPass() { return new BranchFolder(); } 77 78/// RemoveDeadBlock - Remove the specified dead machine basic block from the 79/// function, updating the CFG. 80void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { 81 assert(MBB->pred_empty() && "MBB must be dead!"); 82 DOUT << "\nRemoving MBB: " << *MBB; 83 84 MachineFunction *MF = MBB->getParent(); 85 // drop all successors. 86 while (!MBB->succ_empty()) 87 MBB->removeSuccessor(MBB->succ_end()-1); 88 89 // If there is DWARF info to active, check to see if there are any LABEL 90 // records in the basic block. If so, unregister them from MachineModuleInfo. 91 if (MMI && !MBB->empty()) { 92 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 93 I != E; ++I) { 94 if ((unsigned)I->getOpcode() == TargetInstrInfo::LABEL) { 95 // The label ID # is always operand #0, an immediate. 96 MMI->InvalidateLabel(I->getOperand(0).getImm()); 97 } 98 } 99 } 100 101 // Remove the block. 102 MF->getBasicBlockList().erase(MBB); 103} 104 105bool BranchFolder::runOnMachineFunction(MachineFunction &MF) { 106 TII = MF.getTarget().getInstrInfo(); 107 if (!TII) return false; 108 109 RegInfo = MF.getTarget().getRegisterInfo(); 110 RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL; 111 112 MMI = getAnalysisToUpdate<MachineModuleInfo>(); 113 114 bool EverMadeChange = false; 115 bool MadeChangeThisIteration = true; 116 while (MadeChangeThisIteration) { 117 MadeChangeThisIteration = false; 118 MadeChangeThisIteration |= TailMergeBlocks(MF); 119 MadeChangeThisIteration |= OptimizeBranches(MF); 120 EverMadeChange |= MadeChangeThisIteration; 121 } 122 123 // See if any jump tables have become mergable or dead as the code generator 124 // did its thing. 125 MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); 126 const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables(); 127 if (!JTs.empty()) { 128 // Figure out how these jump tables should be merged. 129 std::vector<unsigned> JTMapping; 130 JTMapping.reserve(JTs.size()); 131 132 // We always keep the 0th jump table. 133 JTMapping.push_back(0); 134 135 // Scan the jump tables, seeing if there are any duplicates. Note that this 136 // is N^2, which should be fixed someday. 137 for (unsigned i = 1, e = JTs.size(); i != e; ++i) 138 JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs)); 139 140 // If a jump table was merge with another one, walk the function rewriting 141 // references to jump tables to reference the new JT ID's. Keep track of 142 // whether we see a jump table idx, if not, we can delete the JT. 143 std::vector<bool> JTIsLive; 144 JTIsLive.resize(JTs.size()); 145 for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); 146 BB != E; ++BB) { 147 for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end(); 148 I != E; ++I) 149 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 150 MachineOperand &Op = I->getOperand(op); 151 if (!Op.isJumpTableIndex()) continue; 152 unsigned NewIdx = JTMapping[Op.getJumpTableIndex()]; 153 Op.setJumpTableIndex(NewIdx); 154 155 // Remember that this JT is live. 156 JTIsLive[NewIdx] = true; 157 } 158 } 159 160 // Finally, remove dead jump tables. This happens either because the 161 // indirect jump was unreachable (and thus deleted) or because the jump 162 // table was merged with some other one. 163 for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i) 164 if (!JTIsLive[i]) { 165 JTI->RemoveJumpTable(i); 166 EverMadeChange = true; 167 } 168 } 169 170 delete RS; 171 return EverMadeChange; 172} 173 174//===----------------------------------------------------------------------===// 175// Tail Merging of Blocks 176//===----------------------------------------------------------------------===// 177 178/// HashMachineInstr - Compute a hash value for MI and its operands. 179static unsigned HashMachineInstr(const MachineInstr *MI) { 180 unsigned Hash = MI->getOpcode(); 181 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 182 const MachineOperand &Op = MI->getOperand(i); 183 184 // Merge in bits from the operand if easy. 185 unsigned OperandHash = 0; 186 switch (Op.getType()) { 187 case MachineOperand::MO_Register: OperandHash = Op.getReg(); break; 188 case MachineOperand::MO_Immediate: OperandHash = Op.getImm(); break; 189 case MachineOperand::MO_MachineBasicBlock: 190 OperandHash = Op.getMachineBasicBlock()->getNumber(); 191 break; 192 case MachineOperand::MO_FrameIndex: OperandHash = Op.getFrameIndex(); break; 193 case MachineOperand::MO_ConstantPoolIndex: 194 OperandHash = Op.getConstantPoolIndex(); 195 break; 196 case MachineOperand::MO_JumpTableIndex: 197 OperandHash = Op.getJumpTableIndex(); 198 break; 199 case MachineOperand::MO_GlobalAddress: 200 case MachineOperand::MO_ExternalSymbol: 201 // Global address / external symbol are too hard, don't bother, but do 202 // pull in the offset. 203 OperandHash = Op.getOffset(); 204 break; 205 default: break; 206 } 207 208 Hash += ((OperandHash << 3) | Op.getType()) << (i&31); 209 } 210 return Hash; 211} 212 213/// HashEndOfMBB - Hash the last two instructions in the MBB. We hash two 214/// instructions, because cross-jumping only saves code when at least two 215/// instructions are removed (since a branch must be inserted). 216static unsigned HashEndOfMBB(const MachineBasicBlock *MBB) { 217 MachineBasicBlock::const_iterator I = MBB->end(); 218 if (I == MBB->begin()) 219 return 0; // Empty MBB. 220 221 --I; 222 unsigned Hash = HashMachineInstr(I); 223 224 if (I == MBB->begin()) 225 return Hash; // Single instr MBB. 226 227 --I; 228 // Hash in the second-to-last instruction. 229 Hash ^= HashMachineInstr(I) << 2; 230 return Hash; 231} 232 233/// ComputeCommonTailLength - Given two machine basic blocks, compute the number 234/// of instructions they actually have in common together at their end. Return 235/// iterators for the first shared instruction in each block. 236static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, 237 MachineBasicBlock *MBB2, 238 MachineBasicBlock::iterator &I1, 239 MachineBasicBlock::iterator &I2) { 240 I1 = MBB1->end(); 241 I2 = MBB2->end(); 242 243 unsigned TailLen = 0; 244 while (I1 != MBB1->begin() && I2 != MBB2->begin()) { 245 --I1; --I2; 246 if (!I1->isIdenticalTo(I2)) { 247 ++I1; ++I2; 248 break; 249 } 250 ++TailLen; 251 } 252 return TailLen; 253} 254 255/// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything 256/// after it, replacing it with an unconditional branch to NewDest. This 257/// returns true if OldInst's block is modified, false if NewDest is modified. 258void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 259 MachineBasicBlock *NewDest) { 260 MachineBasicBlock *OldBB = OldInst->getParent(); 261 262 // Remove all the old successors of OldBB from the CFG. 263 while (!OldBB->succ_empty()) 264 OldBB->removeSuccessor(OldBB->succ_begin()); 265 266 // Remove all the dead instructions from the end of OldBB. 267 OldBB->erase(OldInst, OldBB->end()); 268 269 // If OldBB isn't immediately before OldBB, insert a branch to it. 270 if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest)) 271 TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>()); 272 OldBB->addSuccessor(NewDest); 273 ++NumTailMerge; 274} 275 276/// SplitMBBAt - Given a machine basic block and an iterator into it, split the 277/// MBB so that the part before the iterator falls into the part starting at the 278/// iterator. This returns the new MBB. 279MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB, 280 MachineBasicBlock::iterator BBI1) { 281 // Create the fall-through block. 282 MachineFunction::iterator MBBI = &CurMBB; 283 MachineBasicBlock *NewMBB = new MachineBasicBlock(CurMBB.getBasicBlock()); 284 CurMBB.getParent()->getBasicBlockList().insert(++MBBI, NewMBB); 285 286 // Move all the successors of this block to the specified block. 287 while (!CurMBB.succ_empty()) { 288 MachineBasicBlock *S = *(CurMBB.succ_end()-1); 289 NewMBB->addSuccessor(S); 290 CurMBB.removeSuccessor(S); 291 } 292 293 // Add an edge from CurMBB to NewMBB for the fall-through. 294 CurMBB.addSuccessor(NewMBB); 295 296 // Splice the code over. 297 NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end()); 298 299 // For targets that use the register scavenger, we must maintain LiveIns. 300 if (RS) { 301 RS->enterBasicBlock(&CurMBB); 302 if (!CurMBB.empty()) 303 RS->forward(prior(CurMBB.end())); 304 BitVector RegsLiveAtExit(RegInfo->getNumRegs()); 305 RS->getRegsUsed(RegsLiveAtExit, false); 306 for (unsigned int i=0, e=RegInfo->getNumRegs(); i!=e; i++) 307 if (RegsLiveAtExit[i]) 308 NewMBB->addLiveIn(i); 309 } 310 311 return NewMBB; 312} 313 314/// EstimateRuntime - Make a rough estimate for how long it will take to run 315/// the specified code. 316static unsigned EstimateRuntime(MachineBasicBlock::iterator I, 317 MachineBasicBlock::iterator E, 318 const TargetInstrInfo *TII) { 319 unsigned Time = 0; 320 for (; I != E; ++I) { 321 const TargetInstrDescriptor &TID = TII->get(I->getOpcode()); 322 if (TID.Flags & M_CALL_FLAG) 323 Time += 10; 324 else if (TID.Flags & (M_LOAD_FLAG|M_STORE_FLAG)) 325 Time += 2; 326 else 327 ++Time; 328 } 329 return Time; 330} 331 332/// ShouldSplitFirstBlock - We need to either split MBB1 at MBB1I or MBB2 at 333/// MBB2I and then insert an unconditional branch in the other block. Determine 334/// which is the best to split 335static bool ShouldSplitFirstBlock(MachineBasicBlock *MBB1, 336 MachineBasicBlock::iterator MBB1I, 337 MachineBasicBlock *MBB2, 338 MachineBasicBlock::iterator MBB2I, 339 const TargetInstrInfo *TII) { 340 // TODO: if we had some notion of which block was hotter, we could split 341 // the hot block, so it is the fall-through. Since we don't have profile info 342 // make a decision based on which will hurt most to split. 343 unsigned MBB1Time = EstimateRuntime(MBB1->begin(), MBB1I, TII); 344 unsigned MBB2Time = EstimateRuntime(MBB2->begin(), MBB2I, TII); 345 346 // If the MBB1 prefix takes "less time" to run than the MBB2 prefix, split the 347 // MBB1 block so it falls through. This will penalize the MBB2 path, but will 348 // have a lower overall impact on the program execution. 349 return MBB1Time < MBB2Time; 350} 351 352// See if any of the blocks in MergePotentials (which all have a common single 353// successor, or all have no successor) can be tail-merged. If there is a 354// successor, any blocks in MergePotentials that are not tail-merged and 355// are not immediately before Succ must have an unconditional branch to 356// Succ added (but the predecessor/successor lists need no adjustment). 357// The lone predecessor of Succ that falls through into Succ, 358// if any, is given in PredBB. 359 360bool BranchFolder::TryMergeBlocks(MachineBasicBlock *SuccBB, 361 MachineBasicBlock* PredBB) { 362 MadeChange = false; 363 364 // Sort by hash value so that blocks with identical end sequences sort 365 // together. 366 std::stable_sort(MergePotentials.begin(), MergePotentials.end()); 367 368 // Walk through equivalence sets looking for actual exact matches. 369 while (MergePotentials.size() > 1) { 370 unsigned CurHash = (MergePotentials.end()-1)->first; 371 unsigned PrevHash = (MergePotentials.end()-2)->first; 372 MachineBasicBlock *CurMBB = (MergePotentials.end()-1)->second; 373 374 // If there is nothing that matches the hash of the current basic block, 375 // give up. 376 if (CurHash != PrevHash) { 377 if (SuccBB && CurMBB != PredBB) 378 TII->InsertBranch(*CurMBB, SuccBB, NULL, std::vector<MachineOperand>()); 379 MergePotentials.pop_back(); 380 continue; 381 } 382 383 // Determine the actual length of the shared tail between these two basic 384 // blocks. Because the hash can have collisions, it's possible that this is 385 // less than 2. 386 MachineBasicBlock::iterator BBI1, BBI2; 387 unsigned CommonTailLen = 388 ComputeCommonTailLength(CurMBB, (MergePotentials.end()-2)->second, 389 BBI1, BBI2); 390 391 // If the tails don't have at least two instructions in common, see if there 392 // is anything else in the equivalence class that does match. 393 if (CommonTailLen < 2) { 394 unsigned FoundMatch = ~0U; 395 for (int i = MergePotentials.size()-2; 396 i != -1 && MergePotentials[i].first == CurHash; --i) { 397 CommonTailLen = ComputeCommonTailLength(CurMBB, 398 MergePotentials[i].second, 399 BBI1, BBI2); 400 if (CommonTailLen >= 2) { 401 FoundMatch = i; 402 break; 403 } 404 } 405 406 // If we didn't find anything that has at least two instructions matching 407 // this one, bail out. 408 if (FoundMatch == ~0U) { 409 // Put the unconditional branch back, if we need one. 410 if (SuccBB && CurMBB != PredBB) 411 TII->InsertBranch(*CurMBB, SuccBB, NULL, std::vector<MachineOperand>()); 412 MergePotentials.pop_back(); 413 continue; 414 } 415 416 // Otherwise, move the matching block to the right position. 417 std::swap(MergePotentials[FoundMatch], *(MergePotentials.end()-2)); 418 } 419 420 MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second; 421 422 // If neither block is the entire common tail, split the tail of one block 423 // to make it redundant with the other tail. 424 if (CurMBB->begin() != BBI1 && MBB2->begin() != BBI2) { 425 if (0) { // Enable this to disable partial tail merges. 426 MergePotentials.pop_back(); 427 continue; 428 } 429 430 // Decide whether we want to split CurMBB or MBB2. 431 if (ShouldSplitFirstBlock(CurMBB, BBI1, MBB2, BBI2, TII)) { 432 CurMBB = SplitMBBAt(*CurMBB, BBI1); 433 BBI1 = CurMBB->begin(); 434 MergePotentials.back().second = CurMBB; 435 } else { 436 MBB2 = SplitMBBAt(*MBB2, BBI2); 437 BBI2 = MBB2->begin(); 438 (MergePotentials.end()-2)->second = MBB2; 439 } 440 } 441 442 if (MBB2->begin() == BBI2) { 443 // Hack the end off CurMBB, making it jump to MBBI@ instead. 444 ReplaceTailWithBranchTo(BBI1, MBB2); 445 // This modifies CurMBB, so remove it from the worklist. 446 MergePotentials.pop_back(); 447 } else { 448 assert(CurMBB->begin() == BBI1 && "Didn't split block correctly?"); 449 // Hack the end off MBB2, making it jump to CurMBB instead. 450 ReplaceTailWithBranchTo(BBI2, CurMBB); 451 // This modifies MBB2, so remove it from the worklist. 452 MergePotentials.erase(MergePotentials.end()-2); 453 } 454 MadeChange = true; 455 } 456 return MadeChange; 457} 458 459bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { 460 MadeChange = false; 461 462 if (!EnableTailMerge) return false; 463 464 // First find blocks with no successors. 465 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 466 if (I->succ_empty()) 467 MergePotentials.push_back(std::make_pair(HashEndOfMBB(I), I)); 468 } 469 // See if we can do any crossjumping on those. 470 MadeChange |= TryMergeBlocks(NULL, NULL); 471 472 MergePotentials.clear(); 473 // Look at blocks with two predecessors, where each predecessor has either: 474 // - a single successor, or 475 // - two successors, where successor I is reached either by ubr or fallthrough. 476 // The two-successor case where successor I is reached by cbr 477 // from both blocks is handled by the preceding case (when we consider the 478 // other, fallthough block). 479 // FIXME: The two-successor case where I is reached by cbr 480 // from one block, and by fallthrough/ubr from the other, is not handled yet. 481 // Beware that sometimes blocks are in the predecessor list, but can't really 482 // jump to the "successor" we're looking at. Tolerate this. 483 484 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 485 if (!I->succ_empty() && I->pred_size() >= 2) { 486 MachineBasicBlock *IBB = I; 487 MachineBasicBlock *PredBB = prior(I); 488 for (MachineBasicBlock::pred_iterator P = I->pred_begin(), E2 = I->pred_end(); 489 P != E2; ++P) { 490 MachineBasicBlock* PBB = *P; 491 MachineBasicBlock *TBB = 0, *FBB = 0; 492 std::vector<MachineOperand> Cond; 493 // Remove the unconditional branch at the end, if any. 494 if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond) && 495 ((!FBB && Cond.size()==0) || // single successor 496 (!FBB && TBB!=IBB) || // cbr elsewhere, fallthrough to I 497 (FBB && FBB==IBB))) { // cbr then branch to I 498 if (TBB) { 499 TII->RemoveBranch(*PBB); 500 if (TBB!=IBB) 501 // reinsert conditional branch only, for now 502 TII->InsertBranch(*PBB, TBB, 0, Cond); 503 } 504 MergePotentials.push_back(std::make_pair(HashEndOfMBB(PBB), *P)); 505 } 506 } 507 if (MergePotentials.size() >= 2) 508 MadeChange |= TryMergeBlocks(I, PredBB); 509 // Reinsert an unconditional branch if needed. 510 // The 1 below can be either an original single predecessor, or a result 511 // of removing blocks in TryMergeBlocks. 512 if (MergePotentials.size()==1 && 513 (MergePotentials.begin())->second != PredBB) 514 TII->InsertBranch(*((MergePotentials.begin())->second), I, NULL, 515 std::vector<MachineOperand>()); 516 MergePotentials.clear(); 517 } 518 } 519 520 return MadeChange; 521} 522 523//===----------------------------------------------------------------------===// 524// Branch Optimization 525//===----------------------------------------------------------------------===// 526 527bool BranchFolder::OptimizeBranches(MachineFunction &MF) { 528 MadeChange = false; 529 530 // Make sure blocks are numbered in order 531 MF.RenumberBlocks(); 532 533 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 534 MachineBasicBlock *MBB = I++; 535 OptimizeBlock(MBB); 536 537 // If it is dead, remove it. 538 if (MBB->pred_empty()) { 539 RemoveDeadBlock(MBB); 540 MadeChange = true; 541 ++NumDeadBlocks; 542 } 543 } 544 return MadeChange; 545} 546 547 548/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the 549/// CFG to be inserted. If we have proven that MBB can only branch to DestA and 550/// DestB, remove any other MBB successors from the CFG. DestA and DestB can 551/// be null. 552static bool CorrectExtraCFGEdges(MachineBasicBlock &MBB, 553 MachineBasicBlock *DestA, 554 MachineBasicBlock *DestB, 555 bool isCond, 556 MachineFunction::iterator FallThru) { 557 bool MadeChange = false; 558 bool AddedFallThrough = false; 559 560 // If this block ends with a conditional branch that falls through to its 561 // successor, set DestB as the successor. 562 if (isCond) { 563 if (DestB == 0 && FallThru != MBB.getParent()->end()) { 564 DestB = FallThru; 565 AddedFallThrough = true; 566 } 567 } else { 568 // If this is an unconditional branch with no explicit dest, it must just be 569 // a fallthrough into DestB. 570 if (DestA == 0 && FallThru != MBB.getParent()->end()) { 571 DestA = FallThru; 572 AddedFallThrough = true; 573 } 574 } 575 576 MachineBasicBlock::pred_iterator SI = MBB.succ_begin(); 577 while (SI != MBB.succ_end()) { 578 if (*SI == DestA) { 579 DestA = 0; 580 ++SI; 581 } else if (*SI == DestB) { 582 DestB = 0; 583 ++SI; 584 } else if ((*SI)->isLandingPad()) { 585 ++SI; 586 } else { 587 // Otherwise, this is a superfluous edge, remove it. 588 MBB.removeSuccessor(SI); 589 MadeChange = true; 590 } 591 } 592 if (!AddedFallThrough) { 593 assert(DestA == 0 && DestB == 0 && 594 "MachineCFG is missing edges!"); 595 } else if (isCond) { 596 assert(DestA == 0 && "MachineCFG is missing edges!"); 597 } 598 return MadeChange; 599} 600 601 602/// ReplaceUsesOfBlockWith - Given a machine basic block 'BB' that branched to 603/// 'Old', change the code and CFG so that it branches to 'New' instead. 604static void ReplaceUsesOfBlockWith(MachineBasicBlock *BB, 605 MachineBasicBlock *Old, 606 MachineBasicBlock *New, 607 const TargetInstrInfo *TII) { 608 assert(Old != New && "Cannot replace self with self!"); 609 610 MachineBasicBlock::iterator I = BB->end(); 611 while (I != BB->begin()) { 612 --I; 613 if (!TII->isTerminatorInstr(I->getOpcode())) break; 614 615 // Scan the operands of this machine instruction, replacing any uses of Old 616 // with New. 617 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 618 if (I->getOperand(i).isMachineBasicBlock() && 619 I->getOperand(i).getMachineBasicBlock() == Old) 620 I->getOperand(i).setMachineBasicBlock(New); 621 } 622 623 // Update the successor information. 624 std::vector<MachineBasicBlock*> Succs(BB->succ_begin(), BB->succ_end()); 625 for (int i = Succs.size()-1; i >= 0; --i) 626 if (Succs[i] == Old) { 627 BB->removeSuccessor(Old); 628 BB->addSuccessor(New); 629 } 630} 631 632/// CanFallThrough - Return true if the specified block (with the specified 633/// branch condition) can implicitly transfer control to the block after it by 634/// falling off the end of it. This should return false if it can reach the 635/// block after it, but it uses an explicit branch to do so (e.g. a table jump). 636/// 637/// True is a conservative answer. 638/// 639bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB, 640 bool BranchUnAnalyzable, 641 MachineBasicBlock *TBB, MachineBasicBlock *FBB, 642 const std::vector<MachineOperand> &Cond) { 643 MachineFunction::iterator Fallthrough = CurBB; 644 ++Fallthrough; 645 // If FallthroughBlock is off the end of the function, it can't fall through. 646 if (Fallthrough == CurBB->getParent()->end()) 647 return false; 648 649 // If FallthroughBlock isn't a successor of CurBB, no fallthrough is possible. 650 if (!CurBB->isSuccessor(Fallthrough)) 651 return false; 652 653 // If we couldn't analyze the branch, assume it could fall through. 654 if (BranchUnAnalyzable) return true; 655 656 // If there is no branch, control always falls through. 657 if (TBB == 0) return true; 658 659 // If there is some explicit branch to the fallthrough block, it can obviously 660 // reach, even though the branch should get folded to fall through implicitly. 661 if (MachineFunction::iterator(TBB) == Fallthrough || 662 MachineFunction::iterator(FBB) == Fallthrough) 663 return true; 664 665 // If it's an unconditional branch to some block not the fall through, it 666 // doesn't fall through. 667 if (Cond.empty()) return false; 668 669 // Otherwise, if it is conditional and has no explicit false block, it falls 670 // through. 671 return FBB == 0; 672} 673 674/// CanFallThrough - Return true if the specified can implicitly transfer 675/// control to the block after it by falling off the end of it. This should 676/// return false if it can reach the block after it, but it uses an explicit 677/// branch to do so (e.g. a table jump). 678/// 679/// True is a conservative answer. 680/// 681bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) { 682 MachineBasicBlock *TBB = 0, *FBB = 0; 683 std::vector<MachineOperand> Cond; 684 bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond); 685 return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond); 686} 687 688/// IsBetterFallthrough - Return true if it would be clearly better to 689/// fall-through to MBB1 than to fall through into MBB2. This has to return 690/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will 691/// result in infinite loops. 692static bool IsBetterFallthrough(MachineBasicBlock *MBB1, 693 MachineBasicBlock *MBB2, 694 const TargetInstrInfo &TII) { 695 // Right now, we use a simple heuristic. If MBB2 ends with a call, and 696 // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to 697 // optimize branches that branch to either a return block or an assert block 698 // into a fallthrough to the return. 699 if (MBB1->empty() || MBB2->empty()) return false; 700 701 MachineInstr *MBB1I = --MBB1->end(); 702 MachineInstr *MBB2I = --MBB2->end(); 703 return TII.isCall(MBB2I->getOpcode()) && !TII.isCall(MBB1I->getOpcode()); 704} 705 706/// OptimizeBlock - Analyze and optimize control flow related to the specified 707/// block. This is never called on the entry block. 708void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { 709 MachineFunction::iterator FallThrough = MBB; 710 ++FallThrough; 711 712 // If this block is empty, make everyone use its fall-through, not the block 713 // explicitly. 714 if (MBB->empty()) { 715 // Dead block? Leave for cleanup later. 716 if (MBB->pred_empty()) return; 717 718 if (FallThrough == MBB->getParent()->end()) { 719 // TODO: Simplify preds to not branch here if possible! 720 } else { 721 // Rewrite all predecessors of the old block to go to the fallthrough 722 // instead. 723 while (!MBB->pred_empty()) { 724 MachineBasicBlock *Pred = *(MBB->pred_end()-1); 725 ReplaceUsesOfBlockWith(Pred, MBB, FallThrough, TII); 726 } 727 728 // If MBB was the target of a jump table, update jump tables to go to the 729 // fallthrough instead. 730 MBB->getParent()->getJumpTableInfo()-> 731 ReplaceMBBInJumpTables(MBB, FallThrough); 732 MadeChange = true; 733 } 734 return; 735 } 736 737 // Check to see if we can simplify the terminator of the block before this 738 // one. 739 MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB)); 740 741 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 742 std::vector<MachineOperand> PriorCond; 743 bool PriorUnAnalyzable = 744 TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); 745 if (!PriorUnAnalyzable) { 746 // If the CFG for the prior block has extra edges, remove them. 747 MadeChange |= CorrectExtraCFGEdges(PrevBB, PriorTBB, PriorFBB, 748 !PriorCond.empty(), MBB); 749 750 // If the previous branch is conditional and both conditions go to the same 751 // destination, remove the branch, replacing it with an unconditional one or 752 // a fall-through. 753 if (PriorTBB && PriorTBB == PriorFBB) { 754 TII->RemoveBranch(PrevBB); 755 PriorCond.clear(); 756 if (PriorTBB != MBB) 757 TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 758 MadeChange = true; 759 ++NumBranchOpts; 760 return OptimizeBlock(MBB); 761 } 762 763 // If the previous branch *only* branches to *this* block (conditional or 764 // not) remove the branch. 765 if (PriorTBB == MBB && PriorFBB == 0) { 766 TII->RemoveBranch(PrevBB); 767 MadeChange = true; 768 ++NumBranchOpts; 769 return OptimizeBlock(MBB); 770 } 771 772 // If the prior block branches somewhere else on the condition and here if 773 // the condition is false, remove the uncond second branch. 774 if (PriorFBB == MBB) { 775 TII->RemoveBranch(PrevBB); 776 TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond); 777 MadeChange = true; 778 ++NumBranchOpts; 779 return OptimizeBlock(MBB); 780 } 781 782 // If the prior block branches here on true and somewhere else on false, and 783 // if the branch condition is reversible, reverse the branch to create a 784 // fall-through. 785 if (PriorTBB == MBB) { 786 std::vector<MachineOperand> NewPriorCond(PriorCond); 787 if (!TII->ReverseBranchCondition(NewPriorCond)) { 788 TII->RemoveBranch(PrevBB); 789 TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond); 790 MadeChange = true; 791 ++NumBranchOpts; 792 return OptimizeBlock(MBB); 793 } 794 } 795 796 // If this block doesn't fall through (e.g. it ends with an uncond branch or 797 // has no successors) and if the pred falls through into this block, and if 798 // it would otherwise fall through into the block after this, move this 799 // block to the end of the function. 800 // 801 // We consider it more likely that execution will stay in the function (e.g. 802 // due to loops) than it is to exit it. This asserts in loops etc, moving 803 // the assert condition out of the loop body. 804 if (!PriorCond.empty() && PriorFBB == 0 && 805 MachineFunction::iterator(PriorTBB) == FallThrough && 806 !CanFallThrough(MBB)) { 807 bool DoTransform = true; 808 809 // We have to be careful that the succs of PredBB aren't both no-successor 810 // blocks. If neither have successors and if PredBB is the second from 811 // last block in the function, we'd just keep swapping the two blocks for 812 // last. Only do the swap if one is clearly better to fall through than 813 // the other. 814 if (FallThrough == --MBB->getParent()->end() && 815 !IsBetterFallthrough(PriorTBB, MBB, *TII)) 816 DoTransform = false; 817 818 // We don't want to do this transformation if we have control flow like: 819 // br cond BB2 820 // BB1: 821 // .. 822 // jmp BBX 823 // BB2: 824 // .. 825 // ret 826 // 827 // In this case, we could actually be moving the return block *into* a 828 // loop! 829 if (DoTransform && !MBB->succ_empty() && 830 (!CanFallThrough(PriorTBB) || PriorTBB->empty())) 831 DoTransform = false; 832 833 834 if (DoTransform) { 835 // Reverse the branch so we will fall through on the previous true cond. 836 std::vector<MachineOperand> NewPriorCond(PriorCond); 837 if (!TII->ReverseBranchCondition(NewPriorCond)) { 838 DOUT << "\nMoving MBB: " << *MBB; 839 DOUT << "To make fallthrough to: " << *PriorTBB << "\n"; 840 841 TII->RemoveBranch(PrevBB); 842 TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond); 843 844 // Move this block to the end of the function. 845 MBB->moveAfter(--MBB->getParent()->end()); 846 MadeChange = true; 847 ++NumBranchOpts; 848 return; 849 } 850 } 851 } 852 } 853 854 // Analyze the branch in the current block. 855 MachineBasicBlock *CurTBB = 0, *CurFBB = 0; 856 std::vector<MachineOperand> CurCond; 857 bool CurUnAnalyzable = TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond); 858 if (!CurUnAnalyzable) { 859 // If the CFG for the prior block has extra edges, remove them. 860 MadeChange |= CorrectExtraCFGEdges(*MBB, CurTBB, CurFBB, 861 !CurCond.empty(), 862 ++MachineFunction::iterator(MBB)); 863 864 // If this is a two-way branch, and the FBB branches to this block, reverse 865 // the condition so the single-basic-block loop is faster. Instead of: 866 // Loop: xxx; jcc Out; jmp Loop 867 // we want: 868 // Loop: xxx; jncc Loop; jmp Out 869 if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) { 870 std::vector<MachineOperand> NewCond(CurCond); 871 if (!TII->ReverseBranchCondition(NewCond)) { 872 TII->RemoveBranch(*MBB); 873 TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond); 874 MadeChange = true; 875 ++NumBranchOpts; 876 return OptimizeBlock(MBB); 877 } 878 } 879 880 881 // If this branch is the only thing in its block, see if we can forward 882 // other blocks across it. 883 if (CurTBB && CurCond.empty() && CurFBB == 0 && 884 TII->isBranch(MBB->begin()->getOpcode()) && CurTBB != MBB) { 885 // This block may contain just an unconditional branch. Because there can 886 // be 'non-branch terminators' in the block, try removing the branch and 887 // then seeing if the block is empty. 888 TII->RemoveBranch(*MBB); 889 890 // If this block is just an unconditional branch to CurTBB, we can 891 // usually completely eliminate the block. The only case we cannot 892 // completely eliminate the block is when the block before this one 893 // falls through into MBB and we can't understand the prior block's branch 894 // condition. 895 if (MBB->empty()) { 896 bool PredHasNoFallThrough = TII->BlockHasNoFallThrough(PrevBB); 897 if (PredHasNoFallThrough || !PriorUnAnalyzable || 898 !PrevBB.isSuccessor(MBB)) { 899 // If the prior block falls through into us, turn it into an 900 // explicit branch to us to make updates simpler. 901 if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) && 902 PriorTBB != MBB && PriorFBB != MBB) { 903 if (PriorTBB == 0) { 904 assert(PriorCond.empty() && PriorFBB == 0 && 905 "Bad branch analysis"); 906 PriorTBB = MBB; 907 } else { 908 assert(PriorFBB == 0 && "Machine CFG out of date!"); 909 PriorFBB = MBB; 910 } 911 TII->RemoveBranch(PrevBB); 912 TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond); 913 } 914 915 // Iterate through all the predecessors, revectoring each in-turn. 916 MachineBasicBlock::pred_iterator PI = MBB->pred_begin(); 917 bool DidChange = false; 918 bool HasBranchToSelf = false; 919 while (PI != MBB->pred_end()) { 920 if (*PI == MBB) { 921 // If this block has an uncond branch to itself, leave it. 922 ++PI; 923 HasBranchToSelf = true; 924 } else { 925 DidChange = true; 926 ReplaceUsesOfBlockWith(*PI, MBB, CurTBB, TII); 927 } 928 } 929 930 // Change any jumptables to go to the new MBB. 931 MBB->getParent()->getJumpTableInfo()-> 932 ReplaceMBBInJumpTables(MBB, CurTBB); 933 if (DidChange) { 934 ++NumBranchOpts; 935 MadeChange = true; 936 if (!HasBranchToSelf) return; 937 } 938 } 939 } 940 941 // Add the branch back if the block is more than just an uncond branch. 942 TII->InsertBranch(*MBB, CurTBB, 0, CurCond); 943 } 944 } 945 946 // If the prior block doesn't fall through into this block, and if this 947 // block doesn't fall through into some other block, see if we can find a 948 // place to move this block where a fall-through will happen. 949 if (!CanFallThrough(&PrevBB, PriorUnAnalyzable, 950 PriorTBB, PriorFBB, PriorCond)) { 951 // Now we know that there was no fall-through into this block, check to 952 // see if it has a fall-through into its successor. 953 bool CurFallsThru = CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, 954 CurCond); 955 956 if (!MBB->isLandingPad()) { 957 // Check all the predecessors of this block. If one of them has no fall 958 // throughs, move this block right after it. 959 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 960 E = MBB->pred_end(); PI != E; ++PI) { 961 // Analyze the branch at the end of the pred. 962 MachineBasicBlock *PredBB = *PI; 963 MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough; 964 if (PredBB != MBB && !CanFallThrough(PredBB) 965 && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) { 966 // If the current block doesn't fall through, just move it. 967 // If the current block can fall through and does not end with a 968 // conditional branch, we need to append an unconditional jump to 969 // the (current) next block. To avoid a possible compile-time 970 // infinite loop, move blocks only backward in this case. 971 if (CurFallsThru) { 972 MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB)); 973 CurCond.clear(); 974 TII->InsertBranch(*MBB, NextBB, 0, CurCond); 975 } 976 MBB->moveAfter(PredBB); 977 MadeChange = true; 978 return OptimizeBlock(MBB); 979 } 980 } 981 } 982 983 if (!CurFallsThru) { 984 // Check all successors to see if we can move this block before it. 985 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 986 E = MBB->succ_end(); SI != E; ++SI) { 987 // Analyze the branch at the end of the block before the succ. 988 MachineBasicBlock *SuccBB = *SI; 989 MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev; 990 std::vector<MachineOperand> SuccPrevCond; 991 992 // If this block doesn't already fall-through to that successor, and if 993 // the succ doesn't already have a block that can fall through into it, 994 // and if the successor isn't an EH destination, we can arrange for the 995 // fallthrough to happen. 996 if (SuccBB != MBB && !CanFallThrough(SuccPrev) && 997 !SuccBB->isLandingPad()) { 998 MBB->moveBefore(SuccBB); 999 MadeChange = true; 1000 return OptimizeBlock(MBB); 1001 } 1002 } 1003 1004 // Okay, there is no really great place to put this block. If, however, 1005 // the block before this one would be a fall-through if this block were 1006 // removed, move this block to the end of the function. 1007 if (FallThrough != MBB->getParent()->end() && 1008 PrevBB.isSuccessor(FallThrough)) { 1009 MBB->moveAfter(--MBB->getParent()->end()); 1010 MadeChange = true; 1011 return; 1012 } 1013 } 1014 } 1015} 1016