Index: lib/CodeGen/MIRParser/MIParser.cpp =================================================================== --- lib/CodeGen/MIRParser/MIParser.cpp +++ lib/CodeGen/MIRParser/MIParser.cpp @@ -12,6 +12,8 @@ //===----------------------------------------------------------------------===// #include "MIParser.h" + +#include "../MIRPrinter.h" #include "MILexer.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringSwitch.h" @@ -134,7 +136,8 @@ bool parseBasicBlockDefinition(DenseMap &MBBSlots); - bool parseBasicBlock(MachineBasicBlock &MBB); + bool parseBasicBlock(MachineBasicBlock &MBB, + MachineBasicBlock *&AddFalthroughFrom); bool parseBasicBlockLiveins(MachineBasicBlock &MBB); bool parseBasicBlockSuccessors(MachineBasicBlock &MBB); @@ -518,7 +521,8 @@ return false; } -bool MIParser::parseBasicBlock(MachineBasicBlock &MBB) { +bool MIParser::parseBasicBlock(MachineBasicBlock &MBB, + MachineBasicBlock *&AddFalthroughFrom) { // Skip the definition. assert(Token.is(MIToken::MachineBasicBlockLabel)); lex(); @@ -538,10 +542,12 @@ // // is equivalent to // liveins: %edi, %esi + bool ExplicitSuccesors = false; while (true) { if (Token.is(MIToken::kw_successors)) { if (parseBasicBlockSuccessors(MBB)) return true; + ExplicitSuccesors = true; } else if (Token.is(MIToken::kw_liveins)) { if (parseBasicBlockLiveins(MBB)) return true; @@ -557,10 +563,9 @@ // Parse the instructions. bool IsInBundle = false; MachineInstr *PrevMI = nullptr; - while (true) { - if (Token.is(MIToken::MachineBasicBlockLabel) || Token.is(MIToken::Eof)) - return false; - else if (consumeIfPresent(MIToken::Newline)) + while (!Token.is(MIToken::MachineBasicBlockLabel) && + !Token.is(MIToken::Eof)) { + if (consumeIfPresent(MIToken::Newline)) continue; if (consumeIfPresent(MIToken::rbrace)) { // The first parsing pass should verify that all closing '}' have an @@ -592,6 +597,22 @@ assert(Token.isNewlineOrEOF() && "MI is not fully parsed"); lex(); } + + // Construct successor list by searching for basic block machine operands. + if (!ExplicitSuccesors) { + SmallVector Successors; + bool IsFallthrough; + guessSuccessors(MBB, Successors, IsFallthrough); + for (MachineBasicBlock *Succ : Successors) + MBB.addSuccessor(Succ); + + if (IsFallthrough) { + AddFalthroughFrom = &MBB; + } else { + MBB.normalizeSuccProbs(); + } + } + return false; } @@ -605,11 +626,17 @@ // The first parsing pass should have verified that this token is a MBB label // in the 'parseBasicBlockDefinitions' method. assert(Token.is(MIToken::MachineBasicBlockLabel)); + MachineBasicBlock *AddFalthroughFrom = nullptr; do { MachineBasicBlock *MBB = nullptr; if (parseMBBReference(MBB)) return true; - if (parseBasicBlock(*MBB)) + if (AddFalthroughFrom) { + AddFalthroughFrom->addSuccessor(MBB); + AddFalthroughFrom->normalizeSuccProbs(); + AddFalthroughFrom = nullptr; + } + if (parseBasicBlock(*MBB, AddFalthroughFrom)) return true; // The method 'parseBasicBlock' should parse the whole block until the next // block or the end of file. Index: lib/CodeGen/MIRPrinter.h =================================================================== --- lib/CodeGen/MIRPrinter.h +++ lib/CodeGen/MIRPrinter.h @@ -17,9 +17,11 @@ namespace llvm { +class MachineBasicBlock; class MachineFunction; class Module; class raw_ostream; +template class SmallVectorImpl; /// Print LLVM IR using the MIR serialization format to the given output stream. void printMIR(raw_ostream &OS, const Module &M); @@ -28,6 +30,17 @@ /// output stream. void printMIR(raw_ostream &OS, const MachineFunction &MF); +/// Determine a possible list of successors of a basic block based on the +/// basic block machine operand being used inside the block. This should give +/// you the correct list of successor blocks in most cases except for things +/// like jump tables where the basic block references can't easily be found. +/// The MIRPRinter will skip printing successors if they match the result of +/// this funciton and the parser will use this function to construct a list if +/// it is missing. +void guessSuccessors(const MachineBasicBlock &MBB, + SmallVectorImpl &Successors, + bool &IsFallthrough); + } // end namespace llvm #endif Index: lib/CodeGen/MIRPrinter.cpp =================================================================== --- lib/CodeGen/MIRPrinter.cpp +++ lib/CodeGen/MIRPrinter.cpp @@ -105,6 +105,9 @@ const DenseMap &RegisterMaskIds; const DenseMap &StackObjectOperandMapping; + bool canPredictBranchProbabilities(const MachineBasicBlock &MBB) const; + bool canPredictSuccessors(const MachineBasicBlock &MBB) const; + public: MIPrinter(raw_ostream &OS, ModuleSlotTracker &MST, const DenseMap &RegisterMaskIds, @@ -453,6 +456,61 @@ RegisterMaskIds.insert(std::make_pair(Mask, I++)); } +void llvm::guessSuccessors(const MachineBasicBlock &MBB, + SmallVectorImpl &Result, + bool &IsFallthrough) { + SmallPtrSet Seen; + + for (const MachineInstr &MI : MBB) { + for (const MachineOperand &MO : MI.operands()) { + if (!MO.isMBB()) + continue; + MachineBasicBlock *Succ = MO.getMBB(); + auto RP = Seen.insert(Succ); + if (RP.second) + Result.push_back(Succ); + } + } + MachineBasicBlock::const_iterator I = MBB.getLastNonDebugInstr(); + IsFallthrough = I == MBB.end() || !I->isBarrier(); +} + +bool +MIPrinter::canPredictBranchProbabilities(const MachineBasicBlock &MBB) const { + if (MBB.succ_size() <= 1) + return true; + if (!MBB.hasSuccessorProbabilities()) + return true; + + SmallVector Normalized(MBB.Probs.begin(), + MBB.Probs.end()); + BranchProbability::normalizeProbabilities(Normalized.begin(), + Normalized.end()); + SmallVector Equal(Normalized.size()); + BranchProbability::normalizeProbabilities(Equal.begin(), Equal.end()); + + return std::equal(Normalized.begin(), Normalized.end(), Equal.begin()); +} + +bool MIPrinter::canPredictSuccessors(const MachineBasicBlock &MBB) const { + SmallVector GuessedSuccs; + bool GuessedFallthrough; + guessSuccessors(MBB, GuessedSuccs, GuessedFallthrough); + if (GuessedFallthrough) { + const MachineFunction &MF = *MBB.getParent(); + MachineFunction::const_iterator NextI = std::next(MBB.getIterator()); + if (NextI != MF.end()) { + MachineBasicBlock *Next = const_cast(&*NextI); + if (!is_contained(GuessedSuccs, Next)) + GuessedSuccs.push_back(Next); + } + } + if (GuessedSuccs.size() != MBB.succ_size()) + return false; + return std::equal(MBB.succ_begin(), MBB.succ_end(), GuessedSuccs.begin()); +} + + void MIPrinter::print(const MachineBasicBlock &MBB) { assert(MBB.getNumber() >= 0 && "Invalid MBB number"); OS << "bb." << MBB.getNumber(); @@ -491,13 +549,14 @@ bool HasLineAttributes = false; // Print the successors - if (!MBB.succ_empty()) { + bool canPredictProbs = canPredictBranchProbabilities(MBB); + if (!canPredictProbs || !canPredictSuccessors(MBB)) { OS.indent(2) << "successors: "; for (auto I = MBB.succ_begin(), E = MBB.succ_end(); I != E; ++I) { if (I != MBB.succ_begin()) OS << ", "; printMBBReference(**I); - if (MBB.hasSuccessorProbabilities()) + if (!canPredictProbs) OS << '(' << format("0x%08" PRIx32, MBB.getSuccProbability(I).getNumerator()) << ')'; Index: test/CodeGen/MIR/X86/auto-successor.mir =================================================================== --- /dev/null +++ test/CodeGen/MIR/X86/auto-successor.mir @@ -0,0 +1,58 @@ +# RUN: llc -o - %s -run-pass=none -verify-machineinstrs | FileCheck %s +--- +# We shouldn't need any explicit successor lists in these examples +# CHECK-LABEL: name: func0 +# CHECK: bb.0: +# CHECK-NOT: successors +# CHECK: JE_1 %bb.1, implicit undef %eflags +# CHECK: JMP_1 %bb.3 +# CHECK: bb.1: +# CHECK-NOT: successors +# CHECK: bb.2: +# CHECK-NOT: successors +# CHECK: JE_1 %bb.1, implicit undef %eflags +# CHECK: bb.3: +# CHECK: RETQ undef %eax +name: func0 +body: | + bb.0: + JE_1 %bb.1, implicit undef %eflags + JMP_1 %bb.3 + + bb.1: + + bb.2: + JE_1 %bb.1, implicit undef %eflags + + bb.3: + RETQ undef %eax +... +--- +# Some cases that need explicit successors: +# CHECK-LABEL: name: func1 +name: func1 +body: | + bb.0: + ; CHECK: bb.0: + ; CHECK: successors: %bb.3, %bb.1 + successors: %bb.3, %bb.1 ; different order than operands + JE_1 %bb.1, implicit undef %eflags + JMP_1 %bb.3 + + bb.1: + ; CHECK: bb.1: + ; CHECK: successors: %bb.2, %bb.1 + successors: %bb.2, %bb.1 ; different order (fallthrough variant) + JE_1 %bb.1, implicit undef %eflags + + bb.2: + ; CHECK: bb.2: + ; CHECK: successors: %bb.1(0x60000000), %bb.3(0x20000000) + successors: %bb.1(3), %bb.3(1) ; branch probabilities not normalized + JE_1 %bb.1, implicit undef %eflags + + bb.3: + ; CHECK: bb.3: + ; CHECK: RETQ undef %eax + RETQ undef %eax +... Index: test/CodeGen/MIR/X86/newline-handling.mir =================================================================== --- test/CodeGen/MIR/X86/newline-handling.mir +++ test/CodeGen/MIR/X86/newline-handling.mir @@ -35,7 +35,7 @@ # CHECK-LABEL: name: foo # CHECK: body: | # CHECK-NEXT: bb.0.entry: -# CHECK-NEXT: successors: %bb.1.less(0x40000000), %bb.2.exit(0x40000000) +# CHECK-NEXT: successors: %bb.1.less, %bb.2.exit # CHECK-NEXT: liveins: %edi # CHECK: CMP32ri8 %edi, 10, implicit-def %eflags # CHECK-NEXT: JG_1 %bb.2.exit, implicit killed %eflags @@ -79,7 +79,7 @@ # CHECK-LABEL: name: bar # CHECK: body: | # CHECK-NEXT: bb.0.entry: -# CHECK-NEXT: successors: %bb.1.less(0x40000000), %bb.2.exit(0x40000000) +# CHECK-NEXT: successors: %bb.1.less, %bb.2.exit # CHECK-NEXT: liveins: %edi # CHECK: CMP32ri8 %edi, 10, implicit-def %eflags # CHECK-NEXT: JG_1 %bb.2.exit, implicit killed %eflags Index: test/CodeGen/MIR/X86/successor-basic-blocks.mir =================================================================== --- test/CodeGen/MIR/X86/successor-basic-blocks.mir +++ test/CodeGen/MIR/X86/successor-basic-blocks.mir @@ -32,7 +32,6 @@ name: foo body: | ; CHECK-LABEL: bb.0.entry: - ; CHECK: successors: %bb.1.less(0x40000000), %bb.2.exit(0x40000000) ; CHECK-LABEL: bb.1.less: bb.0.entry: successors: %bb.1.less, %bb.2.exit