2375 lines · cpp
1//===- IfConversion.cpp - Machine code if conversion pass -----------------===//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// This file implements the machine instruction level if-conversion pass, which10// tries to convert conditional branches into predicated instructions.11//12//===----------------------------------------------------------------------===//13 14#include "BranchFolding.h"15#include "llvm/ADT/STLExtras.h"16#include "llvm/ADT/ScopeExit.h"17#include "llvm/ADT/SmallSet.h"18#include "llvm/ADT/SmallVector.h"19#include "llvm/ADT/SparseSet.h"20#include "llvm/ADT/Statistic.h"21#include "llvm/ADT/iterator_range.h"22#include "llvm/Analysis/ProfileSummaryInfo.h"23#include "llvm/CodeGen/LivePhysRegs.h"24#include "llvm/CodeGen/MBFIWrapper.h"25#include "llvm/CodeGen/MachineBasicBlock.h"26#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"27#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"28#include "llvm/CodeGen/MachineFunction.h"29#include "llvm/CodeGen/MachineFunctionPass.h"30#include "llvm/CodeGen/MachineInstr.h"31#include "llvm/CodeGen/MachineInstrBuilder.h"32#include "llvm/CodeGen/MachineOperand.h"33#include "llvm/CodeGen/MachineRegisterInfo.h"34#include "llvm/CodeGen/TargetInstrInfo.h"35#include "llvm/CodeGen/TargetLowering.h"36#include "llvm/CodeGen/TargetRegisterInfo.h"37#include "llvm/CodeGen/TargetSchedule.h"38#include "llvm/CodeGen/TargetSubtargetInfo.h"39#include "llvm/IR/DebugLoc.h"40#include "llvm/InitializePasses.h"41#include "llvm/Pass.h"42#include "llvm/Support/BranchProbability.h"43#include "llvm/Support/CommandLine.h"44#include "llvm/Support/Debug.h"45#include "llvm/Support/ErrorHandling.h"46#include "llvm/Support/raw_ostream.h"47#include <algorithm>48#include <cassert>49#include <functional>50#include <iterator>51#include <memory>52#include <utility>53#include <vector>54 55using namespace llvm;56 57#define DEBUG_TYPE "if-converter"58 59// Hidden options for help debugging.60static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);61static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);62static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);63static cl::opt<bool> DisableSimple("disable-ifcvt-simple",64 cl::init(false), cl::Hidden);65static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",66 cl::init(false), cl::Hidden);67static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",68 cl::init(false), cl::Hidden);69static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",70 cl::init(false), cl::Hidden);71static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",72 cl::init(false), cl::Hidden);73static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",74 cl::init(false), cl::Hidden);75static cl::opt<bool> DisableForkedDiamond("disable-ifcvt-forked-diamond",76 cl::init(false), cl::Hidden);77static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold",78 cl::init(true), cl::Hidden);79 80STATISTIC(NumSimple, "Number of simple if-conversions performed");81STATISTIC(NumSimpleFalse, "Number of simple (F) if-conversions performed");82STATISTIC(NumTriangle, "Number of triangle if-conversions performed");83STATISTIC(NumTriangleRev, "Number of triangle (R) if-conversions performed");84STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");85STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");86STATISTIC(NumDiamonds, "Number of diamond if-conversions performed");87STATISTIC(NumForkedDiamonds, "Number of forked-diamond if-conversions performed");88STATISTIC(NumIfConvBBs, "Number of if-converted blocks");89STATISTIC(NumDupBBs, "Number of duplicated blocks");90STATISTIC(NumUnpred, "Number of true blocks of diamonds unpredicated");91 92namespace {93 94 class IfConverter : public MachineFunctionPass {95 enum IfcvtKind {96 ICNotClassfied, // BB data valid, but not classified.97 ICSimpleFalse, // Same as ICSimple, but on the false path.98 ICSimple, // BB is entry of an one split, no rejoin sub-CFG.99 ICTriangleFRev, // Same as ICTriangleFalse, but false path rev condition.100 ICTriangleRev, // Same as ICTriangle, but true path rev condition.101 ICTriangleFalse, // Same as ICTriangle, but on the false path.102 ICTriangle, // BB is entry of a triangle sub-CFG.103 ICDiamond, // BB is entry of a diamond sub-CFG.104 ICForkedDiamond // BB is entry of an almost diamond sub-CFG, with a105 // common tail that can be shared.106 };107 108 /// One per MachineBasicBlock, this is used to cache the result109 /// if-conversion feasibility analysis. This includes results from110 /// TargetInstrInfo::analyzeBranch() (i.e. TBB, FBB, and Cond), and its111 /// classification, and common tail block of its successors (if it's a112 /// diamond shape), its size, whether it's predicable, and whether any113 /// instruction can clobber the 'would-be' predicate.114 ///115 /// IsDone - True if BB is not to be considered for ifcvt.116 /// IsBeingAnalyzed - True if BB is currently being analyzed.117 /// IsAnalyzed - True if BB has been analyzed (info is still valid).118 /// IsEnqueued - True if BB has been enqueued to be ifcvt'ed.119 /// IsBrAnalyzable - True if analyzeBranch() returns false.120 /// HasFallThrough - True if BB has fallthrough to the following BB.121 /// Note that BB may have a fallthrough if both122 /// !HasFallThrough and !IsBrAnalyzable is true. Also note123 /// that blockNeverFallThrough() can be used to prove that124 /// there is no fall through.125 /// IsUnpredicable - True if BB is known to be unpredicable.126 /// ClobbersPred - True if BB could modify predicates (e.g. has127 /// cmp, call, etc.)128 /// NonPredSize - Number of non-predicated instructions.129 /// ExtraCost - Extra cost for multi-cycle instructions.130 /// ExtraCost2 - Some instructions are slower when predicated131 /// BB - Corresponding MachineBasicBlock.132 /// TrueBB / FalseBB- See analyzeBranch(), but note that FalseBB can be set133 /// by AnalyzeBranches even if there is a fallthrough. So134 /// it doesn't correspond exactly to the result from135 /// TTI::analyzeBranch.136 /// BrCond - Conditions for end of block conditional branches.137 /// Predicate - Predicate used in the BB.138 struct BBInfo {139 bool IsDone : 1;140 bool IsBeingAnalyzed : 1;141 bool IsAnalyzed : 1;142 bool IsEnqueued : 1;143 bool IsBrAnalyzable : 1;144 bool IsBrReversible : 1;145 bool HasFallThrough : 1;146 bool IsUnpredicable : 1;147 bool CannotBeCopied : 1;148 bool ClobbersPred : 1;149 unsigned NonPredSize = 0;150 unsigned ExtraCost = 0;151 unsigned ExtraCost2 = 0;152 MachineBasicBlock *BB = nullptr;153 MachineBasicBlock *TrueBB = nullptr;154 MachineBasicBlock *FalseBB = nullptr;155 SmallVector<MachineOperand, 4> BrCond;156 SmallVector<MachineOperand, 4> Predicate;157 158 BBInfo() : IsDone(false), IsBeingAnalyzed(false),159 IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),160 IsBrReversible(false), HasFallThrough(false),161 IsUnpredicable(false), CannotBeCopied(false),162 ClobbersPred(false) {}163 };164 165 /// Record information about pending if-conversions to attempt:166 /// BBI - Corresponding BBInfo.167 /// Kind - Type of block. See IfcvtKind.168 /// NeedSubsumption - True if the to-be-predicated BB has already been169 /// predicated.170 /// NumDups - Number of instructions that would be duplicated due171 /// to this if-conversion. (For diamonds, the number of172 /// identical instructions at the beginnings of both173 /// paths).174 /// NumDups2 - For diamonds, the number of identical instructions175 /// at the ends of both paths.176 struct IfcvtToken {177 BBInfo &BBI;178 IfcvtKind Kind;179 unsigned NumDups;180 unsigned NumDups2;181 bool NeedSubsumption : 1;182 bool TClobbersPred : 1;183 bool FClobbersPred : 1;184 185 IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0,186 bool tc = false, bool fc = false)187 : BBI(b), Kind(k), NumDups(d), NumDups2(d2), NeedSubsumption(s),188 TClobbersPred(tc), FClobbersPred(fc) {}189 };190 191 /// Results of if-conversion feasibility analysis indexed by basic block192 /// number.193 std::vector<BBInfo> BBAnalysis;194 TargetSchedModel SchedModel;195 196 const TargetLoweringBase *TLI = nullptr;197 const TargetInstrInfo *TII = nullptr;198 const TargetRegisterInfo *TRI = nullptr;199 const MachineBranchProbabilityInfo *MBPI = nullptr;200 MachineRegisterInfo *MRI = nullptr;201 202 LivePhysRegs Redefs;203 204 bool PreRegAlloc = true;205 bool MadeChange = false;206 int FnNum = -1;207 std::function<bool(const MachineFunction &)> PredicateFtor;208 209 public:210 static char ID;211 212 IfConverter(std::function<bool(const MachineFunction &)> Ftor = nullptr)213 : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) {214 initializeIfConverterPass(*PassRegistry::getPassRegistry());215 }216 217 void getAnalysisUsage(AnalysisUsage &AU) const override {218 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();219 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();220 AU.addRequired<ProfileSummaryInfoWrapperPass>();221 MachineFunctionPass::getAnalysisUsage(AU);222 }223 224 bool runOnMachineFunction(MachineFunction &MF) override;225 226 MachineFunctionProperties getRequiredProperties() const override {227 return MachineFunctionProperties().setNoVRegs();228 }229 230 private:231 bool reverseBranchCondition(BBInfo &BBI) const;232 bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups,233 BranchProbability Prediction) const;234 bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,235 bool FalseBranch, unsigned &Dups,236 BranchProbability Prediction) const;237 bool CountDuplicatedInstructions(238 MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,239 MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,240 unsigned &Dups1, unsigned &Dups2,241 MachineBasicBlock &TBB, MachineBasicBlock &FBB,242 bool SkipUnconditionalBranches) const;243 bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,244 unsigned &Dups1, unsigned &Dups2,245 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;246 bool ValidForkedDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,247 unsigned &Dups1, unsigned &Dups2,248 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const;249 void AnalyzeBranches(BBInfo &BBI);250 void ScanInstructions(BBInfo &BBI,251 MachineBasicBlock::iterator &Begin,252 MachineBasicBlock::iterator &End,253 bool BranchUnpredicable = false) const;254 bool RescanInstructions(255 MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,256 MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,257 BBInfo &TrueBBI, BBInfo &FalseBBI) const;258 void AnalyzeBlock(MachineBasicBlock &MBB,259 std::vector<std::unique_ptr<IfcvtToken>> &Tokens);260 bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Pred,261 bool isTriangle = false, bool RevBranch = false,262 bool hasCommonTail = false);263 void AnalyzeBlocks(MachineFunction &MF,264 std::vector<std::unique_ptr<IfcvtToken>> &Tokens);265 void InvalidatePreds(MachineBasicBlock &MBB);266 bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);267 bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);268 bool IfConvertDiamondCommon(BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,269 unsigned NumDups1, unsigned NumDups2,270 bool TClobbersPred, bool FClobbersPred,271 bool RemoveBranch, bool MergeAddEdges);272 bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,273 unsigned NumDups1, unsigned NumDups2,274 bool TClobbers, bool FClobbers);275 bool IfConvertForkedDiamond(BBInfo &BBI, IfcvtKind Kind,276 unsigned NumDups1, unsigned NumDups2,277 bool TClobbers, bool FClobbers);278 void PredicateBlock(BBInfo &BBI, MachineBasicBlock::iterator E,279 SmallVectorImpl<MachineOperand> &Cond,280 SmallSet<MCRegister, 4> *LaterRedefs = nullptr);281 void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,282 SmallVectorImpl<MachineOperand> &Cond,283 bool IgnoreBr = false);284 void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges = true);285 286 bool MeetIfcvtSizeLimit(MachineBasicBlock &BB,287 unsigned Cycle, unsigned Extra,288 BranchProbability Prediction) const {289 return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra,290 Prediction);291 }292 293 bool MeetIfcvtSizeLimit(BBInfo &TBBInfo, BBInfo &FBBInfo,294 MachineBasicBlock &CommBB, unsigned Dups,295 BranchProbability Prediction, bool Forked) const {296 const MachineFunction &MF = *TBBInfo.BB->getParent();297 if (MF.getFunction().hasMinSize()) {298 MachineBasicBlock::iterator TIB = TBBInfo.BB->begin();299 MachineBasicBlock::iterator FIB = FBBInfo.BB->begin();300 MachineBasicBlock::iterator TIE = TBBInfo.BB->end();301 MachineBasicBlock::iterator FIE = FBBInfo.BB->end();302 303 unsigned Dups1 = 0, Dups2 = 0;304 if (!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,305 *TBBInfo.BB, *FBBInfo.BB,306 /*SkipUnconditionalBranches*/ true))307 llvm_unreachable("should already have been checked by ValidDiamond");308 309 unsigned BranchBytes = 0;310 unsigned CommonBytes = 0;311 312 // Count common instructions at the start of the true and false blocks.313 for (auto &I : make_range(TBBInfo.BB->begin(), TIB)) {314 LLVM_DEBUG(dbgs() << "Common inst: " << I);315 CommonBytes += TII->getInstSizeInBytes(I);316 }317 for (auto &I : make_range(FBBInfo.BB->begin(), FIB)) {318 LLVM_DEBUG(dbgs() << "Common inst: " << I);319 CommonBytes += TII->getInstSizeInBytes(I);320 }321 322 // Count instructions at the end of the true and false blocks, after323 // the ones we plan to predicate. Analyzable branches will be removed324 // (unless this is a forked diamond), and all other instructions are325 // common between the two blocks.326 for (auto &I : make_range(TIE, TBBInfo.BB->end())) {327 if (I.isBranch() && TBBInfo.IsBrAnalyzable && !Forked) {328 LLVM_DEBUG(dbgs() << "Saving branch: " << I);329 BranchBytes += TII->predictBranchSizeForIfCvt(I);330 } else {331 LLVM_DEBUG(dbgs() << "Common inst: " << I);332 CommonBytes += TII->getInstSizeInBytes(I);333 }334 }335 for (auto &I : make_range(FIE, FBBInfo.BB->end())) {336 if (I.isBranch() && FBBInfo.IsBrAnalyzable && !Forked) {337 LLVM_DEBUG(dbgs() << "Saving branch: " << I);338 BranchBytes += TII->predictBranchSizeForIfCvt(I);339 } else {340 LLVM_DEBUG(dbgs() << "Common inst: " << I);341 CommonBytes += TII->getInstSizeInBytes(I);342 }343 }344 for (auto &I : CommBB.terminators()) {345 if (I.isBranch()) {346 LLVM_DEBUG(dbgs() << "Saving branch: " << I);347 BranchBytes += TII->predictBranchSizeForIfCvt(I);348 }349 }350 351 // The common instructions in one branch will be eliminated, halving352 // their code size.353 CommonBytes /= 2;354 355 // Count the instructions which we need to predicate.356 unsigned NumPredicatedInstructions = 0;357 for (auto &I : make_range(TIB, TIE)) {358 if (!I.isDebugInstr()) {359 LLVM_DEBUG(dbgs() << "Predicating: " << I);360 NumPredicatedInstructions++;361 }362 }363 for (auto &I : make_range(FIB, FIE)) {364 if (!I.isDebugInstr()) {365 LLVM_DEBUG(dbgs() << "Predicating: " << I);366 NumPredicatedInstructions++;367 }368 }369 370 // Even though we're optimising for size at the expense of performance,371 // avoid creating really long predicated blocks.372 if (NumPredicatedInstructions > 15)373 return false;374 375 // Some targets (e.g. Thumb2) need to insert extra instructions to376 // start predicated blocks.377 unsigned ExtraPredicateBytes = TII->extraSizeToPredicateInstructions(378 MF, NumPredicatedInstructions);379 380 LLVM_DEBUG(dbgs() << "MeetIfcvtSizeLimit(BranchBytes=" << BranchBytes381 << ", CommonBytes=" << CommonBytes382 << ", NumPredicatedInstructions="383 << NumPredicatedInstructions384 << ", ExtraPredicateBytes=" << ExtraPredicateBytes385 << ")\n");386 return (BranchBytes + CommonBytes) > ExtraPredicateBytes;387 } else {388 unsigned TCycle = TBBInfo.NonPredSize + TBBInfo.ExtraCost - Dups;389 unsigned FCycle = FBBInfo.NonPredSize + FBBInfo.ExtraCost - Dups;390 bool Res = TCycle > 0 && FCycle > 0 &&391 TII->isProfitableToIfCvt(392 *TBBInfo.BB, TCycle, TBBInfo.ExtraCost2, *FBBInfo.BB,393 FCycle, FBBInfo.ExtraCost2, Prediction);394 LLVM_DEBUG(dbgs() << "MeetIfcvtSizeLimit(TCycle=" << TCycle395 << ", FCycle=" << FCycle396 << ", TExtra=" << TBBInfo.ExtraCost2 << ", FExtra="397 << FBBInfo.ExtraCost2 << ") = " << Res << "\n");398 return Res;399 }400 }401 402 /// Returns true if Block ends without a terminator.403 bool blockAlwaysFallThrough(BBInfo &BBI) const {404 return BBI.IsBrAnalyzable && BBI.TrueBB == nullptr;405 }406 407 /// Returns true if Block is known not to fallthrough to the following BB.408 bool blockNeverFallThrough(BBInfo &BBI) const {409 // Trust "HasFallThrough" if we could analyze branches.410 if (BBI.IsBrAnalyzable)411 return !BBI.HasFallThrough;412 // If this is the last MBB in the function, or if the textual successor413 // isn't in the successor list, then there is no fallthrough.414 MachineFunction::iterator PI = BBI.BB->getIterator();415 MachineFunction::iterator I = std::next(PI);416 if (I == BBI.BB->getParent()->end() || !PI->isSuccessor(&*I))417 return true;418 // Could not prove that there is no fallthrough.419 return false;420 }421 422 /// Used to sort if-conversion candidates.423 static bool IfcvtTokenCmp(const std::unique_ptr<IfcvtToken> &C1,424 const std::unique_ptr<IfcvtToken> &C2) {425 int Incr1 = (C1->Kind == ICDiamond)426 ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups;427 int Incr2 = (C2->Kind == ICDiamond)428 ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups;429 if (Incr1 > Incr2)430 return true;431 else if (Incr1 == Incr2) {432 // Favors subsumption.433 if (!C1->NeedSubsumption && C2->NeedSubsumption)434 return true;435 else if (C1->NeedSubsumption == C2->NeedSubsumption) {436 // Favors diamond over triangle, etc.437 if ((unsigned)C1->Kind < (unsigned)C2->Kind)438 return true;439 else if (C1->Kind == C2->Kind)440 return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();441 }442 }443 return false;444 }445 };446 447} // end anonymous namespace448 449char IfConverter::ID = 0;450 451char &llvm::IfConverterID = IfConverter::ID;452 453INITIALIZE_PASS_BEGIN(IfConverter, DEBUG_TYPE, "If Converter", false, false)454INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)455INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)456INITIALIZE_PASS_END(IfConverter, DEBUG_TYPE, "If Converter", false, false)457 458bool IfConverter::runOnMachineFunction(MachineFunction &MF) {459 if (skipFunction(MF.getFunction()) || (PredicateFtor && !PredicateFtor(MF)))460 return false;461 462 const TargetSubtargetInfo &ST = MF.getSubtarget();463 TLI = ST.getTargetLowering();464 TII = ST.getInstrInfo();465 TRI = ST.getRegisterInfo();466 MBFIWrapper MBFI(467 getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI());468 MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();469 ProfileSummaryInfo *PSI =470 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();471 MRI = &MF.getRegInfo();472 SchedModel.init(&ST);473 474 if (!TII) return false;475 476 PreRegAlloc = MRI->isSSA();477 478 bool BFChange = false;479 if (!PreRegAlloc) {480 // Tail merge tend to expose more if-conversion opportunities.481 BranchFolder BF(true, false, MBFI, *MBPI, PSI);482 BFChange = BF.OptimizeFunction(MF, TII, ST.getRegisterInfo());483 }484 485 LLVM_DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'"486 << MF.getName() << "\'");487 488 if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {489 LLVM_DEBUG(dbgs() << " skipped\n");490 return false;491 }492 LLVM_DEBUG(dbgs() << "\n");493 494 MF.RenumberBlocks();495 BBAnalysis.resize(MF.getNumBlockIDs());496 497 std::vector<std::unique_ptr<IfcvtToken>> Tokens;498 MadeChange = false;499 unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +500 NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;501 while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {502 // Do an initial analysis for each basic block and find all the potential503 // candidates to perform if-conversion.504 bool Change = false;505 AnalyzeBlocks(MF, Tokens);506 while (!Tokens.empty()) {507 std::unique_ptr<IfcvtToken> Token = std::move(Tokens.back());508 Tokens.pop_back();509 BBInfo &BBI = Token->BBI;510 IfcvtKind Kind = Token->Kind;511 unsigned NumDups = Token->NumDups;512 unsigned NumDups2 = Token->NumDups2;513 514 // If the block has been evicted out of the queue or it has already been515 // marked dead (due to it being predicated), then skip it.516 if (BBI.IsDone)517 BBI.IsEnqueued = false;518 if (!BBI.IsEnqueued)519 continue;520 521 BBI.IsEnqueued = false;522 523 bool RetVal = false;524 switch (Kind) {525 default: llvm_unreachable("Unexpected!");526 case ICSimple:527 case ICSimpleFalse: {528 bool isFalse = Kind == ICSimpleFalse;529 if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;530 LLVM_DEBUG(dbgs() << "Ifcvt (Simple"531 << (Kind == ICSimpleFalse ? " false" : "")532 << "): " << printMBBReference(*BBI.BB) << " ("533 << ((Kind == ICSimpleFalse) ? BBI.FalseBB->getNumber()534 : BBI.TrueBB->getNumber())535 << ") ");536 RetVal = IfConvertSimple(BBI, Kind);537 LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");538 if (RetVal) {539 if (isFalse) ++NumSimpleFalse;540 else ++NumSimple;541 }542 break;543 }544 case ICTriangle:545 case ICTriangleRev:546 case ICTriangleFalse:547 case ICTriangleFRev: {548 bool isFalse = Kind == ICTriangleFalse;549 bool isRev = (Kind == ICTriangleRev || Kind == ICTriangleFRev);550 if (DisableTriangle && !isFalse && !isRev) break;551 if (DisableTriangleR && !isFalse && isRev) break;552 if (DisableTriangleF && isFalse && !isRev) break;553 LLVM_DEBUG(dbgs() << "Ifcvt (Triangle");554 if (isFalse)555 LLVM_DEBUG(dbgs() << " false");556 if (isRev)557 LLVM_DEBUG(dbgs() << " rev");558 LLVM_DEBUG(dbgs() << "): " << printMBBReference(*BBI.BB)559 << " (T:" << BBI.TrueBB->getNumber()560 << ",F:" << BBI.FalseBB->getNumber() << ") ");561 RetVal = IfConvertTriangle(BBI, Kind);562 LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");563 if (RetVal) {564 if (isFalse)565 ++NumTriangleFalse;566 else if (isRev)567 ++NumTriangleRev;568 else569 ++NumTriangle;570 }571 break;572 }573 case ICDiamond:574 if (DisableDiamond) break;575 LLVM_DEBUG(dbgs() << "Ifcvt (Diamond): " << printMBBReference(*BBI.BB)576 << " (T:" << BBI.TrueBB->getNumber()577 << ",F:" << BBI.FalseBB->getNumber() << ") ");578 RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2,579 Token->TClobbersPred,580 Token->FClobbersPred);581 LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");582 if (RetVal) ++NumDiamonds;583 break;584 case ICForkedDiamond:585 if (DisableForkedDiamond) break;586 LLVM_DEBUG(dbgs() << "Ifcvt (Forked Diamond): "587 << printMBBReference(*BBI.BB)588 << " (T:" << BBI.TrueBB->getNumber()589 << ",F:" << BBI.FalseBB->getNumber() << ") ");590 RetVal = IfConvertForkedDiamond(BBI, Kind, NumDups, NumDups2,591 Token->TClobbersPred,592 Token->FClobbersPred);593 LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");594 if (RetVal) ++NumForkedDiamonds;595 break;596 }597 598 if (RetVal && MRI->tracksLiveness())599 recomputeLivenessFlags(*BBI.BB);600 601 Change |= RetVal;602 603 NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +604 NumTriangleFalse + NumTriangleFRev + NumDiamonds;605 if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)606 break;607 }608 609 if (!Change)610 break;611 MadeChange |= Change;612 }613 614 Tokens.clear();615 BBAnalysis.clear();616 617 if (MadeChange && IfCvtBranchFold) {618 BranchFolder BF(false, false, MBFI, *MBPI, PSI);619 BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo());620 }621 622 MadeChange |= BFChange;623 return MadeChange;624}625 626/// BB has a fallthrough. Find its 'false' successor given its 'true' successor.627static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,628 MachineBasicBlock *TrueBB) {629 for (MachineBasicBlock *SuccBB : BB->successors()) {630 if (SuccBB != TrueBB)631 return SuccBB;632 }633 return nullptr;634}635 636/// Reverse the condition of the end of the block branch. Swap block's 'true'637/// and 'false' successors.638bool IfConverter::reverseBranchCondition(BBInfo &BBI) const {639 DebugLoc dl; // FIXME: this is nowhere640 if (!TII->reverseBranchCondition(BBI.BrCond)) {641 TII->removeBranch(*BBI.BB);642 TII->insertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl);643 std::swap(BBI.TrueBB, BBI.FalseBB);644 return true;645 }646 return false;647}648 649/// Returns the next block in the function blocks ordering. If it is the end,650/// returns NULL.651static inline MachineBasicBlock *getNextBlock(MachineBasicBlock &MBB) {652 MachineFunction::iterator I = MBB.getIterator();653 MachineFunction::iterator E = MBB.getParent()->end();654 if (++I == E)655 return nullptr;656 return &*I;657}658 659/// Returns true if the 'true' block (along with its predecessor) forms a valid660/// simple shape for ifcvt. It also returns the number of instructions that the661/// ifcvt would need to duplicate if performed in Dups.662bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups,663 BranchProbability Prediction) const {664 Dups = 0;665 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)666 return false;667 668 if (TrueBBI.IsBrAnalyzable)669 return false;670 671 if (TrueBBI.BB->pred_size() > 1) {672 if (TrueBBI.CannotBeCopied ||673 !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize,674 Prediction))675 return false;676 Dups = TrueBBI.NonPredSize;677 }678 679 return true;680}681 682/// Returns true if the 'true' and 'false' blocks (along with their common683/// predecessor) forms a valid triangle shape for ifcvt. If 'FalseBranch' is684/// true, it checks if 'true' block's false branch branches to the 'false' block685/// rather than the other way around. It also returns the number of instructions686/// that the ifcvt would need to duplicate if performed in 'Dups'.687bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,688 bool FalseBranch, unsigned &Dups,689 BranchProbability Prediction) const {690 Dups = 0;691 if (TrueBBI.BB == FalseBBI.BB)692 return false;693 694 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)695 return false;696 697 if (TrueBBI.BB->pred_size() > 1) {698 if (TrueBBI.CannotBeCopied)699 return false;700 701 unsigned Size = TrueBBI.NonPredSize;702 if (TrueBBI.IsBrAnalyzable) {703 if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())704 // Ends with an unconditional branch. It will be removed.705 --Size;706 else {707 MachineBasicBlock *FExit = FalseBranch708 ? TrueBBI.TrueBB : TrueBBI.FalseBB;709 if (FExit)710 // Require a conditional branch711 ++Size;712 }713 }714 if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size, Prediction))715 return false;716 Dups = Size;717 }718 719 MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;720 if (!TExit && blockAlwaysFallThrough(TrueBBI)) {721 MachineFunction::iterator I = TrueBBI.BB->getIterator();722 if (++I == TrueBBI.BB->getParent()->end())723 return false;724 TExit = &*I;725 }726 return TExit && TExit == FalseBBI.BB;727}728 729/// Count duplicated instructions and move the iterators to show where they730/// are.731/// @param TIB True Iterator Begin732/// @param FIB False Iterator Begin733/// These two iterators initially point to the first instruction of the two734/// blocks, and finally point to the first non-shared instruction.735/// @param TIE True Iterator End736/// @param FIE False Iterator End737/// These two iterators initially point to End() for the two blocks() and738/// finally point to the first shared instruction in the tail.739/// Upon return [TIB, TIE), and [FIB, FIE) mark the un-duplicated portions of740/// two blocks.741/// @param Dups1 count of duplicated instructions at the beginning of the 2742/// blocks.743/// @param Dups2 count of duplicated instructions at the end of the 2 blocks.744/// @param SkipUnconditionalBranches if true, Don't make sure that745/// unconditional branches at the end of the blocks are the same. True is746/// passed when the blocks are analyzable to allow for fallthrough to be747/// handled.748/// @return false if the shared portion prevents if conversion.749bool IfConverter::CountDuplicatedInstructions(750 MachineBasicBlock::iterator &TIB,751 MachineBasicBlock::iterator &FIB,752 MachineBasicBlock::iterator &TIE,753 MachineBasicBlock::iterator &FIE,754 unsigned &Dups1, unsigned &Dups2,755 MachineBasicBlock &TBB, MachineBasicBlock &FBB,756 bool SkipUnconditionalBranches) const {757 while (TIB != TIE && FIB != FIE) {758 // Skip dbg_value instructions. These do not count.759 TIB = skipDebugInstructionsForward(TIB, TIE, false);760 FIB = skipDebugInstructionsForward(FIB, FIE, false);761 if (TIB == TIE || FIB == FIE)762 break;763 if (!TIB->isIdenticalTo(*FIB))764 break;765 // A pred-clobbering instruction in the shared portion prevents766 // if-conversion.767 std::vector<MachineOperand> PredDefs;768 if (TII->ClobbersPredicate(*TIB, PredDefs, false))769 return false;770 // If we get all the way to the branch instructions, don't count them.771 if (!TIB->isBranch())772 ++Dups1;773 ++TIB;774 ++FIB;775 }776 777 // Check for already containing all of the block.778 if (TIB == TIE || FIB == FIE)779 return true;780 // Now, in preparation for counting duplicate instructions at the ends of the781 // blocks, switch to reverse_iterators. Note that getReverse() returns an782 // iterator that points to the same instruction, unlike std::reverse_iterator.783 // We have to do our own shifting so that we get the same range.784 MachineBasicBlock::reverse_iterator RTIE = std::next(TIE.getReverse());785 MachineBasicBlock::reverse_iterator RFIE = std::next(FIE.getReverse());786 const MachineBasicBlock::reverse_iterator RTIB = std::next(TIB.getReverse());787 const MachineBasicBlock::reverse_iterator RFIB = std::next(FIB.getReverse());788 789 if (!TBB.succ_empty() || !FBB.succ_empty()) {790 if (SkipUnconditionalBranches) {791 while (RTIE != RTIB && RTIE->isUnconditionalBranch())792 ++RTIE;793 while (RFIE != RFIB && RFIE->isUnconditionalBranch())794 ++RFIE;795 }796 }797 798 // Count duplicate instructions at the ends of the blocks.799 while (RTIE != RTIB && RFIE != RFIB) {800 // Skip dbg_value instructions. These do not count.801 // Note that these are reverse iterators going forward.802 RTIE = skipDebugInstructionsForward(RTIE, RTIB, false);803 RFIE = skipDebugInstructionsForward(RFIE, RFIB, false);804 if (RTIE == RTIB || RFIE == RFIB)805 break;806 if (!RTIE->isIdenticalTo(*RFIE))807 break;808 // We have to verify that any branch instructions are the same, and then we809 // don't count them toward the # of duplicate instructions.810 if (!RTIE->isBranch())811 ++Dups2;812 ++RTIE;813 ++RFIE;814 }815 TIE = std::next(RTIE.getReverse());816 FIE = std::next(RFIE.getReverse());817 return true;818}819 820/// RescanInstructions - Run ScanInstructions on a pair of blocks.821/// @param TIB - True Iterator Begin, points to first non-shared instruction822/// @param FIB - False Iterator Begin, points to first non-shared instruction823/// @param TIE - True Iterator End, points past last non-shared instruction824/// @param FIE - False Iterator End, points past last non-shared instruction825/// @param TrueBBI - BBInfo to update for the true block.826/// @param FalseBBI - BBInfo to update for the false block.827/// @returns - false if either block cannot be predicated or if both blocks end828/// with a predicate-clobbering instruction.829bool IfConverter::RescanInstructions(830 MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,831 MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,832 BBInfo &TrueBBI, BBInfo &FalseBBI) const {833 bool BranchUnpredicable = true;834 TrueBBI.IsUnpredicable = FalseBBI.IsUnpredicable = false;835 ScanInstructions(TrueBBI, TIB, TIE, BranchUnpredicable);836 if (TrueBBI.IsUnpredicable)837 return false;838 ScanInstructions(FalseBBI, FIB, FIE, BranchUnpredicable);839 if (FalseBBI.IsUnpredicable)840 return false;841 if (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)842 return false;843 return true;844}845 846#ifndef NDEBUG847static void verifySameBranchInstructions(848 MachineBasicBlock *MBB1,849 MachineBasicBlock *MBB2) {850 const MachineBasicBlock::reverse_iterator B1 = MBB1->rend();851 const MachineBasicBlock::reverse_iterator B2 = MBB2->rend();852 MachineBasicBlock::reverse_iterator E1 = MBB1->rbegin();853 MachineBasicBlock::reverse_iterator E2 = MBB2->rbegin();854 while (E1 != B1 && E2 != B2) {855 skipDebugInstructionsForward(E1, B1, false);856 skipDebugInstructionsForward(E2, B2, false);857 if (E1 == B1 && E2 == B2)858 break;859 860 if (E1 == B1) {861 assert(!E2->isBranch() && "Branch mis-match, one block is empty.");862 break;863 }864 if (E2 == B2) {865 assert(!E1->isBranch() && "Branch mis-match, one block is empty.");866 break;867 }868 869 if (E1->isBranch() || E2->isBranch())870 assert(E1->isIdenticalTo(*E2) &&871 "Branch mis-match, branch instructions don't match.");872 else873 break;874 ++E1;875 ++E2;876 }877}878#endif879 880/// ValidForkedDiamond - Returns true if the 'true' and 'false' blocks (along881/// with their common predecessor) form a diamond if a common tail block is882/// extracted.883/// While not strictly a diamond, this pattern would form a diamond if884/// tail-merging had merged the shared tails.885/// EBB886/// _/ \_887/// | |888/// TBB FBB889/// / \ / \890/// FalseBB TrueBB FalseBB891/// Currently only handles analyzable branches.892/// Specifically excludes actual diamonds to avoid overlap.893bool IfConverter::ValidForkedDiamond(894 BBInfo &TrueBBI, BBInfo &FalseBBI,895 unsigned &Dups1, unsigned &Dups2,896 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {897 Dups1 = Dups2 = 0;898 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||899 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)900 return false;901 902 if (!TrueBBI.IsBrAnalyzable || !FalseBBI.IsBrAnalyzable)903 return false;904 // Don't IfConvert blocks that can't be folded into their predecessor.905 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)906 return false;907 908 // This function is specifically looking for conditional tails, as909 // unconditional tails are already handled by the standard diamond case.910 if (TrueBBI.BrCond.size() == 0 ||911 FalseBBI.BrCond.size() == 0)912 return false;913 914 MachineBasicBlock *TT = TrueBBI.TrueBB;915 MachineBasicBlock *TF = TrueBBI.FalseBB;916 MachineBasicBlock *FT = FalseBBI.TrueBB;917 MachineBasicBlock *FF = FalseBBI.FalseBB;918 919 if (!TT)920 TT = getNextBlock(*TrueBBI.BB);921 if (!TF)922 TF = getNextBlock(*TrueBBI.BB);923 if (!FT)924 FT = getNextBlock(*FalseBBI.BB);925 if (!FF)926 FF = getNextBlock(*FalseBBI.BB);927 928 if (!TT || !TF)929 return false;930 931 // Check successors. If they don't match, bail.932 if (!((TT == FT && TF == FF) || (TF == FT && TT == FF)))933 return false;934 935 bool FalseReversed = false;936 if (TF == FT && TT == FF) {937 // If the branches are opposing, but we can't reverse, don't do it.938 if (!FalseBBI.IsBrReversible)939 return false;940 FalseReversed = true;941 reverseBranchCondition(FalseBBI);942 }943 auto UnReverseOnExit = make_scope_exit([&]() {944 if (FalseReversed)945 reverseBranchCondition(FalseBBI);946 });947 948 // Count duplicate instructions at the beginning of the true and false blocks.949 MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();950 MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();951 MachineBasicBlock::iterator TIE = TrueBBI.BB->end();952 MachineBasicBlock::iterator FIE = FalseBBI.BB->end();953 if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,954 *TrueBBI.BB, *FalseBBI.BB,955 /* SkipUnconditionalBranches */ true))956 return false;957 958 TrueBBICalc.BB = TrueBBI.BB;959 FalseBBICalc.BB = FalseBBI.BB;960 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;961 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;962 if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))963 return false;964 965 // The size is used to decide whether to if-convert, and the shared portions966 // are subtracted off. Because of the subtraction, we just use the size that967 // was calculated by the original ScanInstructions, as it is correct.968 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;969 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;970 return true;971}972 973/// ValidDiamond - Returns true if the 'true' and 'false' blocks (along974/// with their common predecessor) forms a valid diamond shape for ifcvt.975bool IfConverter::ValidDiamond(976 BBInfo &TrueBBI, BBInfo &FalseBBI,977 unsigned &Dups1, unsigned &Dups2,978 BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const {979 Dups1 = Dups2 = 0;980 if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||981 FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)982 return false;983 984 // If the True and False BBs are equal we're dealing with a degenerate case985 // that we don't treat as a diamond.986 if (TrueBBI.BB == FalseBBI.BB)987 return false;988 989 MachineBasicBlock *TT = TrueBBI.TrueBB;990 MachineBasicBlock *FT = FalseBBI.TrueBB;991 992 if (!TT && blockAlwaysFallThrough(TrueBBI))993 TT = getNextBlock(*TrueBBI.BB);994 if (!FT && blockAlwaysFallThrough(FalseBBI))995 FT = getNextBlock(*FalseBBI.BB);996 if (TT != FT)997 return false;998 if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))999 return false;1000 if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)1001 return false;1002 1003 // FIXME: Allow true block to have an early exit?1004 if (TrueBBI.FalseBB || FalseBBI.FalseBB)1005 return false;1006 1007 // Count duplicate instructions at the beginning and end of the true and1008 // false blocks.1009 // Skip unconditional branches only if we are considering an analyzable1010 // diamond. Otherwise the branches must be the same.1011 bool SkipUnconditionalBranches =1012 TrueBBI.IsBrAnalyzable && FalseBBI.IsBrAnalyzable;1013 MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();1014 MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();1015 MachineBasicBlock::iterator TIE = TrueBBI.BB->end();1016 MachineBasicBlock::iterator FIE = FalseBBI.BB->end();1017 if(!CountDuplicatedInstructions(TIB, FIB, TIE, FIE, Dups1, Dups2,1018 *TrueBBI.BB, *FalseBBI.BB,1019 SkipUnconditionalBranches))1020 return false;1021 1022 TrueBBICalc.BB = TrueBBI.BB;1023 FalseBBICalc.BB = FalseBBI.BB;1024 TrueBBICalc.IsBrAnalyzable = TrueBBI.IsBrAnalyzable;1025 FalseBBICalc.IsBrAnalyzable = FalseBBI.IsBrAnalyzable;1026 if (!RescanInstructions(TIB, FIB, TIE, FIE, TrueBBICalc, FalseBBICalc))1027 return false;1028 // The size is used to decide whether to if-convert, and the shared portions1029 // are subtracted off. Because of the subtraction, we just use the size that1030 // was calculated by the original ScanInstructions, as it is correct.1031 TrueBBICalc.NonPredSize = TrueBBI.NonPredSize;1032 FalseBBICalc.NonPredSize = FalseBBI.NonPredSize;1033 return true;1034}1035 1036/// AnalyzeBranches - Look at the branches at the end of a block to determine if1037/// the block is predicable.1038void IfConverter::AnalyzeBranches(BBInfo &BBI) {1039 if (BBI.IsDone)1040 return;1041 1042 BBI.TrueBB = BBI.FalseBB = nullptr;1043 BBI.BrCond.clear();1044 BBI.IsBrAnalyzable =1045 !TII->analyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);1046 if (!BBI.IsBrAnalyzable) {1047 BBI.TrueBB = nullptr;1048 BBI.FalseBB = nullptr;1049 BBI.BrCond.clear();1050 }1051 1052 SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());1053 BBI.IsBrReversible = (RevCond.size() == 0) ||1054 !TII->reverseBranchCondition(RevCond);1055 BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == nullptr;1056 1057 if (BBI.BrCond.size()) {1058 // No false branch. This BB must end with a conditional branch and a1059 // fallthrough.1060 if (!BBI.FalseBB)1061 BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);1062 if (!BBI.FalseBB) {1063 // Malformed bcc? True and false blocks are the same?1064 BBI.IsUnpredicable = true;1065 }1066 }1067}1068 1069/// ScanInstructions - Scan all the instructions in the block to determine if1070/// the block is predicable. In most cases, that means all the instructions1071/// in the block are isPredicable(). Also checks if the block contains any1072/// instruction which can clobber a predicate (e.g. condition code register).1073/// If so, the block is not predicable unless it's the last instruction.1074void IfConverter::ScanInstructions(BBInfo &BBI,1075 MachineBasicBlock::iterator &Begin,1076 MachineBasicBlock::iterator &End,1077 bool BranchUnpredicable) const {1078 if (BBI.IsDone || BBI.IsUnpredicable)1079 return;1080 1081 bool AlreadyPredicated = !BBI.Predicate.empty();1082 1083 BBI.NonPredSize = 0;1084 BBI.ExtraCost = 0;1085 BBI.ExtraCost2 = 0;1086 BBI.ClobbersPred = false;1087 for (MachineInstr &MI : make_range(Begin, End)) {1088 if (MI.isDebugInstr())1089 continue;1090 1091 // It's unsafe to duplicate convergent instructions in this context, so set1092 // BBI.CannotBeCopied to true if MI is convergent. To see why, consider the1093 // following CFG, which is subject to our "simple" transformation.1094 //1095 // BB0 // if (c1) goto BB1; else goto BB2;1096 // / \1097 // BB1 |1098 // | BB2 // if (c2) goto TBB; else goto FBB;1099 // | / |1100 // | / |1101 // TBB |1102 // | |1103 // | FBB1104 // |1105 // exit1106 //1107 // Suppose we want to move TBB's contents up into BB1 and BB2 (in BB1 they'd1108 // be unconditional, and in BB2, they'd be predicated upon c2), and suppose1109 // TBB contains a convergent instruction. This is safe iff doing so does1110 // not add a control-flow dependency to the convergent instruction -- i.e.,1111 // it's safe iff the set of control flows that leads us to the convergent1112 // instruction does not get smaller after the transformation.1113 //1114 // Originally we executed TBB if c1 || c2. After the transformation, there1115 // are two copies of TBB's instructions. We get to the first if c1, and we1116 // get to the second if !c1 && c2.1117 //1118 // There are clearly fewer ways to satisfy the condition "c1" than1119 // "c1 || c2". Since we've shrunk the set of control flows which lead to1120 // our convergent instruction, the transformation is unsafe.1121 if (MI.isNotDuplicable() || MI.isConvergent())1122 BBI.CannotBeCopied = true;1123 1124 bool isPredicated = TII->isPredicated(MI);1125 bool isCondBr = BBI.IsBrAnalyzable && MI.isConditionalBranch();1126 1127 if (BranchUnpredicable && MI.isBranch()) {1128 BBI.IsUnpredicable = true;1129 return;1130 }1131 1132 // A conditional branch is not predicable, but it may be eliminated.1133 if (isCondBr)1134 continue;1135 1136 if (!isPredicated) {1137 BBI.NonPredSize++;1138 unsigned ExtraPredCost = TII->getPredicationCost(MI);1139 unsigned NumCycles = SchedModel.computeInstrLatency(&MI, false);1140 if (NumCycles > 1)1141 BBI.ExtraCost += NumCycles-1;1142 BBI.ExtraCost2 += ExtraPredCost;1143 } else if (!AlreadyPredicated) {1144 // FIXME: This instruction is already predicated before the1145 // if-conversion pass. It's probably something like a conditional move.1146 // Mark this block unpredicable for now.1147 BBI.IsUnpredicable = true;1148 return;1149 }1150 1151 if (BBI.ClobbersPred && !isPredicated) {1152 // Predicate modification instruction should end the block (except for1153 // already predicated instructions and end of block branches).1154 // Predicate may have been modified, the subsequent (currently)1155 // unpredicated instructions cannot be correctly predicated.1156 BBI.IsUnpredicable = true;1157 return;1158 }1159 1160 // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are1161 // still potentially predicable.1162 std::vector<MachineOperand> PredDefs;1163 if (TII->ClobbersPredicate(MI, PredDefs, true))1164 BBI.ClobbersPred = true;1165 1166 if (!TII->isPredicable(MI)) {1167 BBI.IsUnpredicable = true;1168 return;1169 }1170 }1171}1172 1173/// Determine if the block is a suitable candidate to be predicated by the1174/// specified predicate.1175/// @param BBI BBInfo for the block to check1176/// @param Pred Predicate array for the branch that leads to BBI1177/// @param isTriangle true if the Analysis is for a triangle1178/// @param RevBranch true if Reverse(Pred) leads to BBI (e.g. BBI is the false1179/// case1180/// @param hasCommonTail true if BBI shares a tail with a sibling block that1181/// contains any instruction that would make the block unpredicable.1182bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,1183 SmallVectorImpl<MachineOperand> &Pred,1184 bool isTriangle, bool RevBranch,1185 bool hasCommonTail) {1186 // If the block is dead or unpredicable, then it cannot be predicated.1187 // Two blocks may share a common unpredicable tail, but this doesn't prevent1188 // them from being if-converted. The non-shared portion is assumed to have1189 // been checked1190 if (BBI.IsDone || (BBI.IsUnpredicable && !hasCommonTail))1191 return false;1192 1193 // If it is already predicated but we couldn't analyze its terminator, the1194 // latter might fallthrough, but we can't determine where to.1195 // Conservatively avoid if-converting again.1196 if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)1197 return false;1198 1199 // If it is already predicated, check if the new predicate subsumes1200 // its predicate.1201 if (BBI.Predicate.size() && !TII->SubsumesPredicate(Pred, BBI.Predicate))1202 return false;1203 1204 if (!hasCommonTail && BBI.BrCond.size()) {1205 if (!isTriangle)1206 return false;1207 1208 // Test predicate subsumption.1209 SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());1210 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());1211 if (RevBranch) {1212 if (TII->reverseBranchCondition(Cond))1213 return false;1214 }1215 if (TII->reverseBranchCondition(RevPred) ||1216 !TII->SubsumesPredicate(Cond, RevPred))1217 return false;1218 }1219 1220 return true;1221}1222 1223/// Analyze the structure of the sub-CFG starting from the specified block.1224/// Record its successors and whether it looks like an if-conversion candidate.1225void IfConverter::AnalyzeBlock(1226 MachineBasicBlock &MBB, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {1227 struct BBState {1228 BBState(MachineBasicBlock &MBB) : MBB(&MBB) {}1229 MachineBasicBlock *MBB;1230 1231 /// This flag is true if MBB's successors have been analyzed.1232 bool SuccsAnalyzed = false;1233 };1234 1235 // Push MBB to the stack.1236 SmallVector<BBState, 16> BBStack(1, MBB);1237 1238 while (!BBStack.empty()) {1239 BBState &State = BBStack.back();1240 MachineBasicBlock *BB = State.MBB;1241 BBInfo &BBI = BBAnalysis[BB->getNumber()];1242 1243 if (!State.SuccsAnalyzed) {1244 if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) {1245 BBStack.pop_back();1246 continue;1247 }1248 1249 BBI.BB = BB;1250 BBI.IsBeingAnalyzed = true;1251 1252 AnalyzeBranches(BBI);1253 MachineBasicBlock::iterator Begin = BBI.BB->begin();1254 MachineBasicBlock::iterator End = BBI.BB->end();1255 ScanInstructions(BBI, Begin, End);1256 1257 // Unanalyzable or ends with fallthrough or unconditional branch, or if is1258 // not considered for ifcvt anymore.1259 if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {1260 BBI.IsBeingAnalyzed = false;1261 BBI.IsAnalyzed = true;1262 BBStack.pop_back();1263 continue;1264 }1265 1266 // Do not ifcvt if either path is a back edge to the entry block.1267 if (BBI.TrueBB == BB || BBI.FalseBB == BB) {1268 BBI.IsBeingAnalyzed = false;1269 BBI.IsAnalyzed = true;1270 BBStack.pop_back();1271 continue;1272 }1273 1274 // Do not ifcvt if true and false fallthrough blocks are the same.1275 if (!BBI.FalseBB) {1276 BBI.IsBeingAnalyzed = false;1277 BBI.IsAnalyzed = true;1278 BBStack.pop_back();1279 continue;1280 }1281 1282 // Push the False and True blocks to the stack.1283 State.SuccsAnalyzed = true;1284 BBStack.push_back(*BBI.FalseBB);1285 BBStack.push_back(*BBI.TrueBB);1286 continue;1287 }1288 1289 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];1290 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];1291 1292 if (TrueBBI.IsDone && FalseBBI.IsDone) {1293 BBI.IsBeingAnalyzed = false;1294 BBI.IsAnalyzed = true;1295 BBStack.pop_back();1296 continue;1297 }1298 1299 SmallVector<MachineOperand, 4>1300 RevCond(BBI.BrCond.begin(), BBI.BrCond.end());1301 bool CanRevCond = !TII->reverseBranchCondition(RevCond);1302 1303 unsigned Dups = 0;1304 unsigned Dups2 = 0;1305 bool TNeedSub = !TrueBBI.Predicate.empty();1306 bool FNeedSub = !FalseBBI.Predicate.empty();1307 bool Enqueued = false;1308 1309 BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);1310 1311 if (CanRevCond) {1312 BBInfo TrueBBICalc, FalseBBICalc;1313 auto feasibleDiamond = [&](bool Forked) {1314 bool MeetsSize = MeetIfcvtSizeLimit(TrueBBICalc, FalseBBICalc, *BB,1315 Dups + Dups2, Prediction, Forked);1316 bool TrueFeasible = FeasibilityAnalysis(TrueBBI, BBI.BrCond,1317 /* IsTriangle */ false, /* RevCond */ false,1318 /* hasCommonTail */ true);1319 bool FalseFeasible = FeasibilityAnalysis(FalseBBI, RevCond,1320 /* IsTriangle */ false, /* RevCond */ false,1321 /* hasCommonTail */ true);1322 return MeetsSize && TrueFeasible && FalseFeasible;1323 };1324 1325 if (ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2,1326 TrueBBICalc, FalseBBICalc)) {1327 if (feasibleDiamond(false)) {1328 // Diamond:1329 // EBB1330 // / \_1331 // | |1332 // TBB FBB1333 // \ /1334 // TailBB1335 // Note TailBB can be empty.1336 Tokens.push_back(std::make_unique<IfcvtToken>(1337 BBI, ICDiamond, TNeedSub | FNeedSub, Dups, Dups2,1338 (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));1339 Enqueued = true;1340 }1341 } else if (ValidForkedDiamond(TrueBBI, FalseBBI, Dups, Dups2,1342 TrueBBICalc, FalseBBICalc)) {1343 if (feasibleDiamond(true)) {1344 // ForkedDiamond:1345 // if TBB and FBB have a common tail that includes their conditional1346 // branch instructions, then we can If Convert this pattern.1347 // EBB1348 // _/ \_1349 // | |1350 // TBB FBB1351 // / \ / \1352 // FalseBB TrueBB FalseBB1353 //1354 Tokens.push_back(std::make_unique<IfcvtToken>(1355 BBI, ICForkedDiamond, TNeedSub | FNeedSub, Dups, Dups2,1356 (bool) TrueBBICalc.ClobbersPred, (bool) FalseBBICalc.ClobbersPred));1357 Enqueued = true;1358 }1359 }1360 }1361 1362 if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&1363 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,1364 TrueBBI.ExtraCost2, Prediction) &&1365 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {1366 // Triangle:1367 // EBB1368 // | \_1369 // | |1370 // | TBB1371 // | /1372 // FBB1373 Tokens.push_back(1374 std::make_unique<IfcvtToken>(BBI, ICTriangle, TNeedSub, Dups));1375 Enqueued = true;1376 }1377 1378 if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&1379 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,1380 TrueBBI.ExtraCost2, Prediction) &&1381 FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {1382 Tokens.push_back(1383 std::make_unique<IfcvtToken>(BBI, ICTriangleRev, TNeedSub, Dups));1384 Enqueued = true;1385 }1386 1387 if (ValidSimple(TrueBBI, Dups, Prediction) &&1388 MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,1389 TrueBBI.ExtraCost2, Prediction) &&1390 FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {1391 // Simple (split, no rejoin):1392 // EBB1393 // | \_1394 // | |1395 // | TBB---> exit1396 // |1397 // FBB1398 Tokens.push_back(1399 std::make_unique<IfcvtToken>(BBI, ICSimple, TNeedSub, Dups));1400 Enqueued = true;1401 }1402 1403 if (CanRevCond) {1404 // Try the other path...1405 if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,1406 Prediction.getCompl()) &&1407 MeetIfcvtSizeLimit(*FalseBBI.BB,1408 FalseBBI.NonPredSize + FalseBBI.ExtraCost,1409 FalseBBI.ExtraCost2, Prediction.getCompl()) &&1410 FeasibilityAnalysis(FalseBBI, RevCond, true)) {1411 Tokens.push_back(std::make_unique<IfcvtToken>(BBI, ICTriangleFalse,1412 FNeedSub, Dups));1413 Enqueued = true;1414 }1415 1416 if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,1417 Prediction.getCompl()) &&1418 MeetIfcvtSizeLimit(*FalseBBI.BB,1419 FalseBBI.NonPredSize + FalseBBI.ExtraCost,1420 FalseBBI.ExtraCost2, Prediction.getCompl()) &&1421 FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {1422 Tokens.push_back(1423 std::make_unique<IfcvtToken>(BBI, ICTriangleFRev, FNeedSub, Dups));1424 Enqueued = true;1425 }1426 1427 if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&1428 MeetIfcvtSizeLimit(*FalseBBI.BB,1429 FalseBBI.NonPredSize + FalseBBI.ExtraCost,1430 FalseBBI.ExtraCost2, Prediction.getCompl()) &&1431 FeasibilityAnalysis(FalseBBI, RevCond)) {1432 Tokens.push_back(1433 std::make_unique<IfcvtToken>(BBI, ICSimpleFalse, FNeedSub, Dups));1434 Enqueued = true;1435 }1436 }1437 1438 BBI.IsEnqueued = Enqueued;1439 BBI.IsBeingAnalyzed = false;1440 BBI.IsAnalyzed = true;1441 BBStack.pop_back();1442 }1443}1444 1445/// Analyze all blocks and find entries for all if-conversion candidates.1446void IfConverter::AnalyzeBlocks(1447 MachineFunction &MF, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) {1448 for (MachineBasicBlock &MBB : MF)1449 AnalyzeBlock(MBB, Tokens);1450 1451 // Sort to favor more complex ifcvt scheme.1452 llvm::stable_sort(Tokens, IfcvtTokenCmp);1453}1454 1455/// Returns true either if ToMBB is the next block after MBB or that all the1456/// intervening blocks are empty (given MBB can fall through to its next block).1457static bool canFallThroughTo(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB) {1458 MachineFunction::iterator PI = MBB.getIterator();1459 MachineFunction::iterator I = std::next(PI);1460 MachineFunction::iterator TI = ToMBB.getIterator();1461 MachineFunction::iterator E = MBB.getParent()->end();1462 while (I != TI) {1463 // Check isSuccessor to avoid case where the next block is empty, but1464 // it's not a successor.1465 if (I == E || !I->empty() || !PI->isSuccessor(&*I))1466 return false;1467 PI = I++;1468 }1469 // Finally see if the last I is indeed a successor to PI.1470 return PI->isSuccessor(&*I);1471}1472 1473/// Invalidate predecessor BB info so it would be re-analyzed to determine if it1474/// can be if-converted. If predecessor is already enqueued, dequeue it!1475void IfConverter::InvalidatePreds(MachineBasicBlock &MBB) {1476 for (const MachineBasicBlock *Predecessor : MBB.predecessors()) {1477 BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()];1478 if (PBBI.IsDone || PBBI.BB == &MBB)1479 continue;1480 PBBI.IsAnalyzed = false;1481 PBBI.IsEnqueued = false;1482 }1483}1484 1485/// Inserts an unconditional branch from \p MBB to \p ToMBB.1486static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB,1487 const TargetInstrInfo *TII) {1488 DebugLoc dl; // FIXME: this is nowhere1489 SmallVector<MachineOperand, 0> NoCond;1490 TII->insertBranch(MBB, &ToMBB, nullptr, NoCond, dl);1491}1492 1493/// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all1494/// values defined in MI which are also live/used by MI.1495static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs) {1496 const TargetRegisterInfo *TRI = MI.getMF()->getSubtarget().getRegisterInfo();1497 1498 // Before stepping forward past MI, remember which regs were live1499 // before MI. This is needed to set the Undef flag only when reg is1500 // dead.1501 SparseSet<MCPhysReg, MCPhysReg> LiveBeforeMI;1502 LiveBeforeMI.setUniverse(TRI->getNumRegs());1503 for (unsigned Reg : Redefs)1504 LiveBeforeMI.insert(Reg);1505 1506 SmallVector<std::pair<MCPhysReg, const MachineOperand*>, 4> Clobbers;1507 Redefs.stepForward(MI, Clobbers);1508 1509 // Now add the implicit uses for each of the clobbered values.1510 for (auto Clobber : Clobbers) {1511 // FIXME: Const cast here is nasty, but better than making StepForward1512 // take a mutable instruction instead of const.1513 unsigned Reg = Clobber.first;1514 MachineOperand &Op = const_cast<MachineOperand&>(*Clobber.second);1515 MachineInstr *OpMI = Op.getParent();1516 MachineInstrBuilder MIB(*OpMI->getMF(), OpMI);1517 if (Op.isRegMask()) {1518 // First handle regmasks. They clobber any entries in the mask which1519 // means that we need a def for those registers.1520 if (LiveBeforeMI.count(Reg))1521 MIB.addReg(Reg, RegState::Implicit);1522 1523 // We also need to add an implicit def of this register for the later1524 // use to read from.1525 // For the register allocator to have allocated a register clobbered1526 // by the call which is used later, it must be the case that1527 // the call doesn't return.1528 MIB.addReg(Reg, RegState::Implicit | RegState::Define);1529 continue;1530 }1531 if (any_of(TRI->subregs_inclusive(Reg),1532 [&](MCPhysReg S) { return LiveBeforeMI.count(S); }))1533 MIB.addReg(Reg, RegState::Implicit);1534 }1535}1536 1537/// If convert a simple (split, no rejoin) sub-CFG.1538bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {1539 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];1540 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];1541 BBInfo *CvtBBI = &TrueBBI;1542 BBInfo *NextBBI = &FalseBBI;1543 1544 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());1545 if (Kind == ICSimpleFalse)1546 std::swap(CvtBBI, NextBBI);1547 1548 MachineBasicBlock &CvtMBB = *CvtBBI->BB;1549 MachineBasicBlock &NextMBB = *NextBBI->BB;1550 if (CvtBBI->IsDone ||1551 (CvtBBI->CannotBeCopied && CvtMBB.pred_size() > 1)) {1552 // Something has changed. It's no longer safe to predicate this block.1553 BBI.IsAnalyzed = false;1554 CvtBBI->IsAnalyzed = false;1555 return false;1556 }1557 1558 if (CvtMBB.hasAddressTaken())1559 // Conservatively abort if-conversion if BB's address is taken.1560 return false;1561 1562 if (Kind == ICSimpleFalse)1563 if (TII->reverseBranchCondition(Cond))1564 llvm_unreachable("Unable to reverse branch condition!");1565 1566 Redefs.init(*TRI);1567 1568 if (MRI->tracksLiveness()) {1569 // Initialize liveins to the first BB. These are potentially redefined by1570 // predicated instructions.1571 Redefs.addLiveInsNoPristines(CvtMBB);1572 Redefs.addLiveInsNoPristines(NextMBB);1573 }1574 1575 // Remove the branches from the entry so we can add the contents of the true1576 // block to it.1577 BBI.NonPredSize -= TII->removeBranch(*BBI.BB);1578 1579 if (CvtMBB.pred_size() > 1) {1580 // Copy instructions in the true block, predicate them, and add them to1581 // the entry block.1582 CopyAndPredicateBlock(BBI, *CvtBBI, Cond);1583 1584 // Keep the CFG updated.1585 BBI.BB->removeSuccessor(&CvtMBB, true);1586 } else {1587 // Predicate the instructions in the true block.1588 PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);1589 1590 // Merge converted block into entry block. The BB to Cvt edge is removed1591 // by MergeBlocks.1592 MergeBlocks(BBI, *CvtBBI);1593 }1594 1595 bool IterIfcvt = true;1596 if (!canFallThroughTo(*BBI.BB, NextMBB)) {1597 InsertUncondBranch(*BBI.BB, NextMBB, TII);1598 BBI.HasFallThrough = false;1599 // Now ifcvt'd block will look like this:1600 // BB:1601 // ...1602 // t, f = cmp1603 // if t op1604 // b BBf1605 //1606 // We cannot further ifcvt this block because the unconditional branch1607 // will have to be predicated on the new condition, that will not be1608 // available if cmp executes.1609 IterIfcvt = false;1610 }1611 1612 // Update block info. BB can be iteratively if-converted.1613 if (!IterIfcvt)1614 BBI.IsDone = true;1615 InvalidatePreds(*BBI.BB);1616 CvtBBI->IsDone = true;1617 1618 // FIXME: Must maintain LiveIns.1619 return true;1620}1621 1622/// If convert a triangle sub-CFG.1623bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {1624 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];1625 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];1626 BBInfo *CvtBBI = &TrueBBI;1627 BBInfo *NextBBI = &FalseBBI;1628 DebugLoc dl; // FIXME: this is nowhere1629 1630 SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());1631 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)1632 std::swap(CvtBBI, NextBBI);1633 1634 MachineBasicBlock &CvtMBB = *CvtBBI->BB;1635 MachineBasicBlock &NextMBB = *NextBBI->BB;1636 if (CvtBBI->IsDone ||1637 (CvtBBI->CannotBeCopied && CvtMBB.pred_size() > 1)) {1638 // Something has changed. It's no longer safe to predicate this block.1639 BBI.IsAnalyzed = false;1640 CvtBBI->IsAnalyzed = false;1641 return false;1642 }1643 1644 if (CvtMBB.hasAddressTaken())1645 // Conservatively abort if-conversion if BB's address is taken.1646 return false;1647 1648 if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)1649 if (TII->reverseBranchCondition(Cond))1650 llvm_unreachable("Unable to reverse branch condition!");1651 1652 if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {1653 if (reverseBranchCondition(*CvtBBI)) {1654 // BB has been changed, modify its predecessors (except for this1655 // one) so they don't get ifcvt'ed based on bad intel.1656 for (MachineBasicBlock *PBB : CvtMBB.predecessors()) {1657 if (PBB == BBI.BB)1658 continue;1659 BBInfo &PBBI = BBAnalysis[PBB->getNumber()];1660 if (PBBI.IsEnqueued) {1661 PBBI.IsAnalyzed = false;1662 PBBI.IsEnqueued = false;1663 }1664 }1665 }1666 }1667 1668 // Initialize liveins to the first BB. These are potentially redefined by1669 // predicated instructions.1670 Redefs.init(*TRI);1671 if (MRI->tracksLiveness()) {1672 Redefs.addLiveInsNoPristines(CvtMBB);1673 Redefs.addLiveInsNoPristines(NextMBB);1674 }1675 1676 bool HasEarlyExit = CvtBBI->FalseBB != nullptr;1677 BranchProbability CvtNext, CvtFalse, BBNext, BBCvt;1678 1679 if (HasEarlyExit) {1680 // Get probabilities before modifying CvtMBB and BBI.BB.1681 CvtNext = MBPI->getEdgeProbability(&CvtMBB, &NextMBB);1682 CvtFalse = MBPI->getEdgeProbability(&CvtMBB, CvtBBI->FalseBB);1683 BBNext = MBPI->getEdgeProbability(BBI.BB, &NextMBB);1684 BBCvt = MBPI->getEdgeProbability(BBI.BB, &CvtMBB);1685 }1686 1687 // Remove the branches from the entry so we can add the contents of the true1688 // block to it.1689 BBI.NonPredSize -= TII->removeBranch(*BBI.BB);1690 1691 if (CvtMBB.pred_size() > 1) {1692 // Copy instructions in the true block, predicate them, and add them to1693 // the entry block.1694 CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);1695 } else {1696 // Predicate the 'true' block after removing its branch.1697 CvtBBI->NonPredSize -= TII->removeBranch(CvtMBB);1698 PredicateBlock(*CvtBBI, CvtMBB.end(), Cond);1699 1700 // Now merge the entry of the triangle with the true block.1701 MergeBlocks(BBI, *CvtBBI, false);1702 }1703 1704 // Keep the CFG updated.1705 BBI.BB->removeSuccessor(&CvtMBB, true);1706 1707 // If 'true' block has a 'false' successor, add an exit branch to it.1708 if (HasEarlyExit) {1709 SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),1710 CvtBBI->BrCond.end());1711 if (TII->reverseBranchCondition(RevCond))1712 llvm_unreachable("Unable to reverse branch condition!");1713 1714 // Update the edge probability for both CvtBBI->FalseBB and NextBBI.1715 // NewNext = New_Prob(BBI.BB, NextMBB) =1716 // Prob(BBI.BB, NextMBB) +1717 // Prob(BBI.BB, CvtMBB) * Prob(CvtMBB, NextMBB)1718 // NewFalse = New_Prob(BBI.BB, CvtBBI->FalseBB) =1719 // Prob(BBI.BB, CvtMBB) * Prob(CvtMBB, CvtBBI->FalseBB)1720 auto NewTrueBB = getNextBlock(*BBI.BB);1721 auto NewNext = BBNext + BBCvt * CvtNext;1722 auto NewTrueBBIter = find(BBI.BB->successors(), NewTrueBB);1723 if (NewTrueBBIter != BBI.BB->succ_end())1724 BBI.BB->setSuccProbability(NewTrueBBIter, NewNext);1725 1726 auto NewFalse = BBCvt * CvtFalse;1727 TII->insertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl);1728 BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);1729 }1730 1731 // Merge in the 'false' block if the 'false' block has no other1732 // predecessors. Otherwise, add an unconditional branch to 'false'.1733 bool FalseBBDead = false;1734 bool IterIfcvt = true;1735 bool isFallThrough = canFallThroughTo(*BBI.BB, NextMBB);1736 if (!isFallThrough) {1737 // Only merge them if the true block does not fallthrough to the false1738 // block. By not merging them, we make it possible to iteratively1739 // ifcvt the blocks.1740 if (!HasEarlyExit && NextMBB.pred_size() == 1 &&1741 blockNeverFallThrough(*NextBBI) && !NextMBB.hasAddressTaken()) {1742 MergeBlocks(BBI, *NextBBI);1743 FalseBBDead = true;1744 } else {1745 InsertUncondBranch(*BBI.BB, NextMBB, TII);1746 BBI.HasFallThrough = false;1747 }1748 // Mixed predicated and unpredicated code. This cannot be iteratively1749 // predicated.1750 IterIfcvt = false;1751 }1752 1753 // Update block info. BB can be iteratively if-converted.1754 if (!IterIfcvt)1755 BBI.IsDone = true;1756 InvalidatePreds(*BBI.BB);1757 CvtBBI->IsDone = true;1758 if (FalseBBDead)1759 NextBBI->IsDone = true;1760 1761 // FIXME: Must maintain LiveIns.1762 return true;1763}1764 1765/// Common code shared between diamond conversions.1766/// \p BBI, \p TrueBBI, and \p FalseBBI form the diamond shape.1767/// \p NumDups1 - number of shared instructions at the beginning of \p TrueBBI1768/// and FalseBBI1769/// \p NumDups2 - number of shared instructions at the end of \p TrueBBI1770/// and \p FalseBBI1771/// \p RemoveBranch - Remove the common branch of the two blocks before1772/// predicating. Only false for unanalyzable fallthrough1773/// cases. The caller will replace the branch if necessary.1774/// \p MergeAddEdges - Add successor edges when merging blocks. Only false for1775/// unanalyzable fallthrough1776bool IfConverter::IfConvertDiamondCommon(1777 BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,1778 unsigned NumDups1, unsigned NumDups2,1779 bool TClobbersPred, bool FClobbersPred,1780 bool RemoveBranch, bool MergeAddEdges) {1781 1782 if (TrueBBI.IsDone || FalseBBI.IsDone ||1783 TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1) {1784 // Something has changed. It's no longer safe to predicate these blocks.1785 BBI.IsAnalyzed = false;1786 TrueBBI.IsAnalyzed = false;1787 FalseBBI.IsAnalyzed = false;1788 return false;1789 }1790 1791 if (TrueBBI.BB->hasAddressTaken() || FalseBBI.BB->hasAddressTaken())1792 // Conservatively abort if-conversion if either BB has its address taken.1793 return false;1794 1795 // Put the predicated instructions from the 'true' block before the1796 // instructions from the 'false' block, unless the true block would clobber1797 // the predicate, in which case, do the opposite.1798 BBInfo *BBI1 = &TrueBBI;1799 BBInfo *BBI2 = &FalseBBI;1800 SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());1801 if (TII->reverseBranchCondition(RevCond))1802 llvm_unreachable("Unable to reverse branch condition!");1803 SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;1804 SmallVector<MachineOperand, 4> *Cond2 = &RevCond;1805 1806 // Figure out the more profitable ordering.1807 bool DoSwap = false;1808 if (TClobbersPred && !FClobbersPred)1809 DoSwap = true;1810 else if (!TClobbersPred && !FClobbersPred) {1811 if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)1812 DoSwap = true;1813 } else if (TClobbersPred && FClobbersPred)1814 llvm_unreachable("Predicate info cannot be clobbered by both sides.");1815 if (DoSwap) {1816 std::swap(BBI1, BBI2);1817 std::swap(Cond1, Cond2);1818 }1819 1820 // Remove the conditional branch from entry to the blocks.1821 BBI.NonPredSize -= TII->removeBranch(*BBI.BB);1822 1823 MachineBasicBlock &MBB1 = *BBI1->BB;1824 MachineBasicBlock &MBB2 = *BBI2->BB;1825 1826 // Initialize the Redefs:1827 // - BB2 live-in regs need implicit uses before being redefined by BB11828 // instructions.1829 // - BB1 live-out regs need implicit uses before being redefined by BB21830 // instructions. We start with BB1 live-ins so we have the live-out regs1831 // after tracking the BB1 instructions.1832 Redefs.init(*TRI);1833 if (MRI->tracksLiveness()) {1834 Redefs.addLiveInsNoPristines(MBB1);1835 Redefs.addLiveInsNoPristines(MBB2);1836 }1837 1838 // Remove the duplicated instructions at the beginnings of both paths.1839 // Skip dbg_value instructions.1840 MachineBasicBlock::iterator DI1 = MBB1.getFirstNonDebugInstr(false);1841 MachineBasicBlock::iterator DI2 = MBB2.getFirstNonDebugInstr(false);1842 BBI1->NonPredSize -= NumDups1;1843 BBI2->NonPredSize -= NumDups1;1844 1845 // Skip past the dups on each side separately since there may be1846 // differing dbg_value entries. NumDups1 can include a "return"1847 // instruction, if it's not marked as "branch".1848 for (unsigned i = 0; i < NumDups1; ++DI1) {1849 if (DI1 == MBB1.end())1850 break;1851 if (!DI1->isDebugInstr())1852 ++i;1853 }1854 while (NumDups1 != 0) {1855 // Since this instruction is going to be deleted, update call1856 // info state if the instruction is call instruction.1857 if (DI2->shouldUpdateAdditionalCallInfo())1858 MBB2.getParent()->eraseAdditionalCallInfo(&*DI2);1859 1860 ++DI2;1861 if (DI2 == MBB2.end())1862 break;1863 if (!DI2->isDebugInstr())1864 --NumDups1;1865 }1866 1867 if (MRI->tracksLiveness()) {1868 for (const MachineInstr &MI : make_range(MBB1.begin(), DI1)) {1869 SmallVector<std::pair<MCPhysReg, const MachineOperand*>, 4> Dummy;1870 Redefs.stepForward(MI, Dummy);1871 }1872 }1873 1874 BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.begin(), DI1);1875 MBB2.erase(MBB2.begin(), DI2);1876 1877 // The branches have been checked to match, so it is safe to remove the1878 // branch in BB1 and rely on the copy in BB2. The complication is that1879 // the blocks may end with a return instruction, which may or may not1880 // be marked as "branch". If it's not, then it could be included in1881 // "dups1", leaving the blocks potentially empty after moving the common1882 // duplicates.1883#ifndef NDEBUG1884 // Unanalyzable branches must match exactly. Check that now.1885 if (!BBI1->IsBrAnalyzable)1886 verifySameBranchInstructions(&MBB1, &MBB2);1887#endif1888 // Remove duplicated instructions from the tail of MBB1: any branch1889 // instructions, and the common instructions counted by NumDups2.1890 DI1 = MBB1.end();1891 while (DI1 != MBB1.begin()) {1892 MachineBasicBlock::iterator Prev = std::prev(DI1);1893 if (!Prev->isBranch() && !Prev->isDebugInstr())1894 break;1895 DI1 = Prev;1896 }1897 for (unsigned i = 0; i != NumDups2; ) {1898 // NumDups2 only counted non-dbg_value instructions, so this won't1899 // run off the head of the list.1900 assert(DI1 != MBB1.begin());1901 1902 --DI1;1903 1904 // Since this instruction is going to be deleted, update call1905 // info state if the instruction is call instruction.1906 if (DI1->shouldUpdateAdditionalCallInfo())1907 MBB1.getParent()->eraseAdditionalCallInfo(&*DI1);1908 1909 // skip dbg_value instructions1910 if (!DI1->isDebugInstr())1911 ++i;1912 }1913 MBB1.erase(DI1, MBB1.end());1914 1915 DI2 = BBI2->BB->end();1916 // The branches have been checked to match. Skip over the branch in the false1917 // block so that we don't try to predicate it.1918 if (RemoveBranch)1919 BBI2->NonPredSize -= TII->removeBranch(*BBI2->BB);1920 else {1921 // Make DI2 point to the end of the range where the common "tail"1922 // instructions could be found.1923 while (DI2 != MBB2.begin()) {1924 MachineBasicBlock::iterator Prev = std::prev(DI2);1925 if (!Prev->isBranch() && !Prev->isDebugInstr())1926 break;1927 DI2 = Prev;1928 }1929 }1930 while (NumDups2 != 0) {1931 // NumDups2 only counted non-dbg_value instructions, so this won't1932 // run off the head of the list.1933 assert(DI2 != MBB2.begin());1934 --DI2;1935 // skip dbg_value instructions1936 if (!DI2->isDebugInstr())1937 --NumDups2;1938 }1939 1940 // Remember which registers would later be defined by the false block.1941 // This allows us not to predicate instructions in the true block that would1942 // later be re-defined. That is, rather than1943 // subeq r0, r1, #11944 // addne r0, r1, #11945 // generate:1946 // sub r0, r1, #11947 // addne r0, r1, #11948 SmallSet<MCRegister, 4> RedefsByFalse;1949 SmallSet<MCRegister, 4> ExtUses;1950 if (TII->isProfitableToUnpredicate(MBB1, MBB2)) {1951 for (const MachineInstr &FI : make_range(MBB2.begin(), DI2)) {1952 if (FI.isDebugInstr())1953 continue;1954 SmallVector<MCRegister, 4> Defs;1955 for (const MachineOperand &MO : FI.operands()) {1956 if (!MO.isReg())1957 continue;1958 Register Reg = MO.getReg();1959 if (!Reg)1960 continue;1961 if (MO.isDef()) {1962 Defs.push_back(Reg);1963 } else if (!RedefsByFalse.count(Reg)) {1964 // These are defined before ctrl flow reach the 'false' instructions.1965 // They cannot be modified by the 'true' instructions.1966 ExtUses.insert_range(TRI->subregs_inclusive(Reg));1967 }1968 }1969 1970 for (MCRegister Reg : Defs) {1971 if (!ExtUses.contains(Reg))1972 RedefsByFalse.insert_range(TRI->subregs_inclusive(Reg));1973 }1974 }1975 }1976 1977 // Predicate the 'true' block.1978 PredicateBlock(*BBI1, MBB1.end(), *Cond1, &RedefsByFalse);1979 1980 // After predicating BBI1, if there is a predicated terminator in BBI1 and1981 // a non-predicated in BBI2, then we don't want to predicate the one from1982 // BBI2. The reason is that if we merged these blocks, we would end up with1983 // two predicated terminators in the same block.1984 // Also, if the branches in MBB1 and MBB2 were non-analyzable, then don't1985 // predicate them either. They were checked to be identical, and so the1986 // same branch would happen regardless of which path was taken.1987 if (!MBB2.empty() && (DI2 == MBB2.end())) {1988 MachineBasicBlock::iterator BBI1T = MBB1.getFirstTerminator();1989 MachineBasicBlock::iterator BBI2T = MBB2.getFirstTerminator();1990 bool BB1Predicated = BBI1T != MBB1.end() && TII->isPredicated(*BBI1T);1991 bool BB2NonPredicated = BBI2T != MBB2.end() && !TII->isPredicated(*BBI2T);1992 if (BB2NonPredicated && (BB1Predicated || !BBI2->IsBrAnalyzable))1993 --DI2;1994 }1995 1996 // Predicate the 'false' block.1997 PredicateBlock(*BBI2, DI2, *Cond2);1998 1999 // Merge the true block into the entry of the diamond.2000 MergeBlocks(BBI, *BBI1, MergeAddEdges);2001 MergeBlocks(BBI, *BBI2, MergeAddEdges);2002 return true;2003}2004 2005/// If convert an almost-diamond sub-CFG where the true2006/// and false blocks share a common tail.2007bool IfConverter::IfConvertForkedDiamond(2008 BBInfo &BBI, IfcvtKind Kind,2009 unsigned NumDups1, unsigned NumDups2,2010 bool TClobbersPred, bool FClobbersPred) {2011 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];2012 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];2013 2014 // Save the debug location for later.2015 DebugLoc dl;2016 MachineBasicBlock::iterator TIE = TrueBBI.BB->getFirstTerminator();2017 if (TIE != TrueBBI.BB->end())2018 dl = TIE->getDebugLoc();2019 // Removing branches from both blocks is safe, because we have already2020 // determined that both blocks have the same branch instructions. The branch2021 // will be added back at the end, unpredicated.2022 if (!IfConvertDiamondCommon(2023 BBI, TrueBBI, FalseBBI,2024 NumDups1, NumDups2,2025 TClobbersPred, FClobbersPred,2026 /* RemoveBranch */ true, /* MergeAddEdges */ true))2027 return false;2028 2029 // Add back the branch.2030 // Debug location saved above when removing the branch from BBI22031 TII->insertBranch(*BBI.BB, TrueBBI.TrueBB, TrueBBI.FalseBB,2032 TrueBBI.BrCond, dl);2033 2034 // Update block info.2035 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;2036 InvalidatePreds(*BBI.BB);2037 2038 // FIXME: Must maintain LiveIns.2039 return true;2040}2041 2042/// If convert a diamond sub-CFG.2043bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,2044 unsigned NumDups1, unsigned NumDups2,2045 bool TClobbersPred, bool FClobbersPred) {2046 BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];2047 BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];2048 MachineBasicBlock *TailBB = TrueBBI.TrueBB;2049 2050 // True block must fall through or end with an unanalyzable terminator.2051 if (!TailBB) {2052 if (blockAlwaysFallThrough(TrueBBI))2053 TailBB = FalseBBI.TrueBB;2054 assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");2055 }2056 2057 if (!IfConvertDiamondCommon(2058 BBI, TrueBBI, FalseBBI,2059 NumDups1, NumDups2,2060 TClobbersPred, FClobbersPred,2061 /* RemoveBranch */ TrueBBI.IsBrAnalyzable,2062 /* MergeAddEdges */ TailBB == nullptr))2063 return false;2064 2065 // If the if-converted block falls through or unconditionally branches into2066 // the tail block, and the tail block does not have other predecessors, then2067 // fold the tail block in as well. Otherwise, unless it falls through to the2068 // tail, add a unconditional branch to it.2069 if (TailBB) {2070 // We need to remove the edges to the true and false blocks manually since2071 // we didn't let IfConvertDiamondCommon update the CFG.2072 BBI.BB->removeSuccessor(TrueBBI.BB);2073 BBI.BB->removeSuccessor(FalseBBI.BB, true);2074 2075 BBInfo &TailBBI = BBAnalysis[TailBB->getNumber()];2076 bool CanMergeTail =2077 blockNeverFallThrough(TailBBI) && !TailBBI.BB->hasAddressTaken();2078 // The if-converted block can still have a predicated terminator2079 // (e.g. a predicated return). If that is the case, we cannot merge2080 // it with the tail block.2081 MachineBasicBlock::const_iterator TI = BBI.BB->getFirstTerminator();2082 if (TI != BBI.BB->end() && TII->isPredicated(*TI))2083 CanMergeTail = false;2084 // There may still be a fall-through edge from BBI1 or BBI2 to TailBB;2085 // check if there are any other predecessors besides those.2086 unsigned NumPreds = TailBB->pred_size();2087 if (NumPreds > 1)2088 CanMergeTail = false;2089 else if (NumPreds == 1 && CanMergeTail) {2090 MachineBasicBlock::pred_iterator PI = TailBB->pred_begin();2091 if (*PI != TrueBBI.BB && *PI != FalseBBI.BB)2092 CanMergeTail = false;2093 }2094 if (CanMergeTail) {2095 MergeBlocks(BBI, TailBBI);2096 TailBBI.IsDone = true;2097 } else {2098 BBI.BB->addSuccessor(TailBB, BranchProbability::getOne());2099 InsertUncondBranch(*BBI.BB, *TailBB, TII);2100 BBI.HasFallThrough = false;2101 }2102 }2103 2104 // Update block info.2105 BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;2106 InvalidatePreds(*BBI.BB);2107 2108 // FIXME: Must maintain LiveIns.2109 return true;2110}2111 2112static bool MaySpeculate(const MachineInstr &MI,2113 SmallSet<MCRegister, 4> &LaterRedefs) {2114 bool SawStore = true;2115 if (!MI.isSafeToMove(SawStore))2116 return false;2117 2118 for (const MachineOperand &MO : MI.operands()) {2119 if (!MO.isReg())2120 continue;2121 Register Reg = MO.getReg();2122 if (!Reg)2123 continue;2124 if (MO.isDef() && !LaterRedefs.count(Reg))2125 return false;2126 }2127 2128 return true;2129}2130 2131/// Predicate instructions from the start of the block to the specified end with2132/// the specified condition.2133void IfConverter::PredicateBlock(BBInfo &BBI, MachineBasicBlock::iterator E,2134 SmallVectorImpl<MachineOperand> &Cond,2135 SmallSet<MCRegister, 4> *LaterRedefs) {2136 bool AnyUnpred = false;2137 bool MaySpec = LaterRedefs != nullptr;2138 for (MachineInstr &I : make_range(BBI.BB->begin(), E)) {2139 if (I.isDebugInstr() || TII->isPredicated(I))2140 continue;2141 // It may be possible not to predicate an instruction if it's the 'true'2142 // side of a diamond and the 'false' side may re-define the instruction's2143 // defs.2144 if (MaySpec && MaySpeculate(I, *LaterRedefs)) {2145 AnyUnpred = true;2146 continue;2147 }2148 // If any instruction is predicated, then every instruction after it must2149 // be predicated.2150 MaySpec = false;2151 if (!TII->PredicateInstruction(I, Cond)) {2152#ifndef NDEBUG2153 dbgs() << "Unable to predicate " << I << "!\n";2154#endif2155 llvm_unreachable(nullptr);2156 }2157 2158 // If the predicated instruction now redefines a register as the result of2159 // if-conversion, add an implicit kill.2160 UpdatePredRedefs(I, Redefs);2161 }2162 2163 BBI.Predicate.append(Cond.begin(), Cond.end());2164 2165 BBI.IsAnalyzed = false;2166 BBI.NonPredSize = 0;2167 2168 ++NumIfConvBBs;2169 if (AnyUnpred)2170 ++NumUnpred;2171}2172 2173/// Copy and predicate instructions from source BB to the destination block.2174/// Skip end of block branches if IgnoreBr is true.2175void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,2176 SmallVectorImpl<MachineOperand> &Cond,2177 bool IgnoreBr) {2178 MachineFunction &MF = *ToBBI.BB->getParent();2179 2180 MachineBasicBlock &FromMBB = *FromBBI.BB;2181 for (MachineInstr &I : FromMBB) {2182 // Do not copy the end of the block branches.2183 if (IgnoreBr && I.isBranch())2184 break;2185 2186 MachineInstr *MI = MF.CloneMachineInstr(&I);2187 // Make a copy of the call info.2188 if (I.isCandidateForAdditionalCallInfo())2189 MF.copyAdditionalCallInfo(&I, MI);2190 2191 ToBBI.BB->insert(ToBBI.BB->end(), MI);2192 ToBBI.NonPredSize++;2193 unsigned ExtraPredCost = TII->getPredicationCost(I);2194 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);2195 if (NumCycles > 1)2196 ToBBI.ExtraCost += NumCycles-1;2197 ToBBI.ExtraCost2 += ExtraPredCost;2198 2199 if (!TII->isPredicated(I) && !MI->isDebugInstr()) {2200 if (!TII->PredicateInstruction(*MI, Cond)) {2201#ifndef NDEBUG2202 dbgs() << "Unable to predicate " << I << "!\n";2203#endif2204 llvm_unreachable(nullptr);2205 }2206 }2207 2208 // If the predicated instruction now redefines a register as the result of2209 // if-conversion, add an implicit kill.2210 UpdatePredRedefs(*MI, Redefs);2211 }2212 2213 if (!IgnoreBr) {2214 std::vector<MachineBasicBlock *> Succs(FromMBB.succ_begin(),2215 FromMBB.succ_end());2216 MachineBasicBlock *NBB = getNextBlock(FromMBB);2217 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;2218 2219 for (MachineBasicBlock *Succ : Succs) {2220 // Fallthrough edge can't be transferred.2221 if (Succ == FallThrough)2222 continue;2223 ToBBI.BB->addSuccessor(Succ);2224 }2225 }2226 2227 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());2228 ToBBI.Predicate.append(Cond.begin(), Cond.end());2229 2230 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;2231 ToBBI.IsAnalyzed = false;2232 2233 ++NumDupBBs;2234}2235 2236/// Move all instructions from FromBB to the end of ToBB. This will leave2237/// FromBB as an empty block, so remove all of its successor edges and move it2238/// to the end of the function. If AddEdges is true, i.e., when FromBBI's2239/// branch is being moved, add those successor edges to ToBBI and remove the old2240/// edge from ToBBI to FromBBI.2241void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {2242 MachineBasicBlock &FromMBB = *FromBBI.BB;2243 assert(!FromMBB.hasAddressTaken() &&2244 "Removing a BB whose address is taken!");2245 2246 // If we're about to splice an INLINEASM_BR from FromBBI, we need to update2247 // ToBBI's successor list accordingly.2248 if (FromMBB.mayHaveInlineAsmBr())2249 for (MachineInstr &MI : FromMBB)2250 if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)2251 for (MachineOperand &MO : MI.operands())2252 if (MO.isMBB() && !ToBBI.BB->isSuccessor(MO.getMBB()))2253 ToBBI.BB->addSuccessor(MO.getMBB(), BranchProbability::getZero());2254 2255 // In case FromMBB contains terminators (e.g. return instruction),2256 // first move the non-terminator instructions, then the terminators.2257 MachineBasicBlock::iterator FromTI = FromMBB.getFirstTerminator();2258 MachineBasicBlock::iterator ToTI = ToBBI.BB->getFirstTerminator();2259 ToBBI.BB->splice(ToTI, &FromMBB, FromMBB.begin(), FromTI);2260 2261 // If FromBB has non-predicated terminator we should copy it at the end.2262 if (FromTI != FromMBB.end() && !TII->isPredicated(*FromTI))2263 ToTI = ToBBI.BB->end();2264 ToBBI.BB->splice(ToTI, &FromMBB, FromTI, FromMBB.end());2265 2266 // Force normalizing the successors' probabilities of ToBBI.BB to convert all2267 // unknown probabilities into known ones.2268 // FIXME: This usage is too tricky and in the future we would like to2269 // eliminate all unknown probabilities in MBB.2270 if (ToBBI.IsBrAnalyzable)2271 ToBBI.BB->normalizeSuccProbs();2272 2273 SmallVector<MachineBasicBlock *, 4> FromSuccs(FromMBB.successors());2274 MachineBasicBlock *NBB = getNextBlock(FromMBB);2275 MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;2276 // The edge probability from ToBBI.BB to FromMBB, which is only needed when2277 // AddEdges is true and FromMBB is a successor of ToBBI.BB.2278 auto To2FromProb = BranchProbability::getZero();2279 if (AddEdges && ToBBI.BB->isSuccessor(&FromMBB)) {2280 // Remove the old edge but remember the edge probability so we can calculate2281 // the correct weights on the new edges being added further down.2282 To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, &FromMBB);2283 ToBBI.BB->removeSuccessor(&FromMBB);2284 }2285 2286 for (MachineBasicBlock *Succ : FromSuccs) {2287 // Fallthrough edge can't be transferred.2288 if (Succ == FallThrough) {2289 FromMBB.removeSuccessor(Succ);2290 continue;2291 }2292 2293 auto NewProb = BranchProbability::getZero();2294 if (AddEdges) {2295 // Calculate the edge probability for the edge from ToBBI.BB to Succ,2296 // which is a portion of the edge probability from FromMBB to Succ. The2297 // portion ratio is the edge probability from ToBBI.BB to FromMBB (if2298 // FromBBI is a successor of ToBBI.BB. See comment below for exception).2299 NewProb = MBPI->getEdgeProbability(&FromMBB, Succ);2300 2301 // To2FromProb is 0 when FromMBB is not a successor of ToBBI.BB. This2302 // only happens when if-converting a diamond CFG and FromMBB is the2303 // tail BB. In this case FromMBB post-dominates ToBBI.BB and hence we2304 // could just use the probabilities on FromMBB's out-edges when adding2305 // new successors.2306 if (!To2FromProb.isZero())2307 NewProb *= To2FromProb;2308 }2309 2310 FromMBB.removeSuccessor(Succ);2311 2312 if (AddEdges) {2313 // If the edge from ToBBI.BB to Succ already exists, update the2314 // probability of this edge by adding NewProb to it. An example is shown2315 // below, in which A is ToBBI.BB and B is FromMBB. In this case we2316 // don't have to set C as A's successor as it already is. We only need to2317 // update the edge probability on A->C. Note that B will not be2318 // immediately removed from A's successors. It is possible that B->D is2319 // not removed either if D is a fallthrough of B. Later the edge A->D2320 // (generated here) and B->D will be combined into one edge. To maintain2321 // correct edge probability of this combined edge, we need to set the edge2322 // probability of A->B to zero, which is already done above. The edge2323 // probability on A->D is calculated by scaling the original probability2324 // on A->B by the probability of B->D.2325 //2326 // Before ifcvt: After ifcvt (assume B->D is kept):2327 //2328 // A A2329 // /| /|\2330 // / B / B|2331 // | /| | ||2332 // |/ | | |/2333 // C D C D2334 //2335 if (ToBBI.BB->isSuccessor(Succ))2336 ToBBI.BB->setSuccProbability(2337 find(ToBBI.BB->successors(), Succ),2338 MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb);2339 else2340 ToBBI.BB->addSuccessor(Succ, NewProb);2341 }2342 }2343 2344 // Move the now empty FromMBB out of the way to the end of the function so2345 // it doesn't interfere with fallthrough checks done by canFallThroughTo().2346 MachineBasicBlock *Last = &*FromMBB.getParent()->rbegin();2347 if (Last != &FromMBB)2348 FromMBB.moveAfter(Last);2349 2350 // Normalize the probabilities of ToBBI.BB's successors with all adjustment2351 // we've done above.2352 if (ToBBI.IsBrAnalyzable && FromBBI.IsBrAnalyzable)2353 ToBBI.BB->normalizeSuccProbs();2354 2355 ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());2356 FromBBI.Predicate.clear();2357 2358 ToBBI.NonPredSize += FromBBI.NonPredSize;2359 ToBBI.ExtraCost += FromBBI.ExtraCost;2360 ToBBI.ExtraCost2 += FromBBI.ExtraCost2;2361 FromBBI.NonPredSize = 0;2362 FromBBI.ExtraCost = 0;2363 FromBBI.ExtraCost2 = 0;2364 2365 ToBBI.ClobbersPred |= FromBBI.ClobbersPred;2366 ToBBI.HasFallThrough = FromBBI.HasFallThrough;2367 ToBBI.IsAnalyzed = false;2368 FromBBI.IsAnalyzed = false;2369}2370 2371FunctionPass *2372llvm::createIfConverter(std::function<bool(const MachineFunction &)> Ftor) {2373 return new IfConverter(std::move(Ftor));2374}2375