PPCBranchCoalescing.cpp | Explore in Territory

//===-- CoalesceBranches.cpp - Coalesce blocks with the same condition ---===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Coalesce basic blocks guarded by the same branch condition into a single
/// basic block.
///
//===----------------------------------------------------------------------===//

#include "PPC.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachinePostDominators.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumBlocksCoalesced, "Number of blocks coalesced");
STATISTIC(NumPHINotMoved, "Number of PHI Nodes that cannot be merged");
STATISTIC(NumBlocksNotCoalesced, "Number of blocks not coalesced");

//===----------------------------------------------------------------------===//
//                               PPCBranchCoalescing
//===----------------------------------------------------------------------===//
///
/// Improve scheduling by coalescing branches that depend on the same condition.
/// This pass looks for blocks that are guarded by the same branch condition
/// and attempts to merge the blocks together. Such opportunities arise from
/// the expansion of select statements in the IR.
///
/// This pass does not handle implicit operands on branch statements. In order
/// to run on targets that use implicit operands, changes need to be made in the
/// canCoalesceBranch and canMerge methods.
///
/// Example: the following LLVM IR
///
///     %test = icmp eq i32 %x 0
///     %tmp1 = select i1 %test, double %a, double 2.000000e-03
///     %tmp2 = select i1 %test, double %b, double 5.000000e-03
///
/// expands to the following machine code:
///
/// %bb.0: derived from LLVM BB %entry
///    liveins: %f1 %f3 %x6
///        <SNIP1>
///        %0 = COPY %f1; F8RC:%0
///        %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4
///        %8 = LXSDX %zero8, killed %7, implicit %rm;
///                    mem:LD8[ConstantPool] F8RC:%8 G8RC:%7
///        BCC 76, %5, <%bb.2>; CRRC:%5
///    Successors according to CFG: %bb.1(?%) %bb.2(?%)
///
/// %bb.1: derived from LLVM BB %entry
///    Predecessors according to CFG: %bb.0
///    Successors according to CFG: %bb.2(?%)
///
/// %bb.2: derived from LLVM BB %entry
///    Predecessors according to CFG: %bb.0 %bb.1
///        %9 = PHI %8, <%bb.1>, %0, <%bb.0>;
///                    F8RC:%9,%8,%0
///        <SNIP2>
///        BCC 76, %5, <%bb.4>; CRRC:%5
///    Successors according to CFG: %bb.3(?%) %bb.4(?%)
///
/// %bb.3: derived from LLVM BB %entry
///    Predecessors according to CFG: %bb.2
///    Successors according to CFG: %bb.4(?%)
///
/// %bb.4: derived from LLVM BB %entry
///    Predecessors according to CFG: %bb.2 %bb.3
///        %13 = PHI %12, <%bb.3>, %2, <%bb.2>;
///                     F8RC:%13,%12,%2
///        <SNIP3>
///        BLR8 implicit %lr8, implicit %rm, implicit %f1
///
/// When this pattern is detected, branch coalescing will try to collapse
/// it by moving code in %bb.2 to %bb.0 and/or %bb.4 and removing %bb.3.
///
/// If all conditions are meet, IR should collapse to:
///
/// %bb.0: derived from LLVM BB %entry
///    liveins: %f1 %f3 %x6
///        <SNIP1>
///        %0 = COPY %f1; F8RC:%0
///        %5 = CMPLWI killed %4, 0; CRRC:%5 GPRC:%4
///        %8 = LXSDX %zero8, killed %7, implicit %rm;
///                     mem:LD8[ConstantPool] F8RC:%8 G8RC:%7
///        <SNIP2>
///        BCC 76, %5, <%bb.4>; CRRC:%5
///    Successors according to CFG: %bb.1(0x2aaaaaaa / 0x80000000 = 33.33%)
///      %bb.4(0x55555554 / 0x80000000 = 66.67%)
///
/// %bb.1: derived from LLVM BB %entry
///    Predecessors according to CFG: %bb.0
///    Successors according to CFG: %bb.4(0x40000000 / 0x80000000 = 50.00%)
///
/// %bb.4: derived from LLVM BB %entry
///    Predecessors according to CFG: %bb.0 %bb.1
///        %9 = PHI %8, <%bb.1>, %0, <%bb.0>;
///                    F8RC:%9,%8,%0
///        %13 = PHI %12, <%bb.1>, %2, <%bb.0>;
///                     F8RC:%13,%12,%2
///        <SNIP3>
///        BLR8 implicit %lr8, implicit %rm, implicit %f1
///
/// Branch Coalescing does not split blocks, it moves everything in the same
/// direction ensuring it does not break use/definition semantics.
///
/// PHI nodes and its corresponding use instructions are moved to its successor
/// block if there are no uses within the successor block PHI nodes.  PHI
/// node ordering cannot be assumed.
///
/// Non-PHI can be moved up to the predecessor basic block or down to the
/// successor basic block following any PHI instructions. Whether it moves
/// up or down depends on whether the register(s) defined in the instructions
/// are used in current block or in any PHI instructions at the beginning of
/// the successor block.

namespace {

class PPCBranchCoalescing : public MachineFunctionPass { … };
} // End anonymous namespace.

char PPCBranchCoalescing::ID = …;
/// createPPCBranchCoalescingPass - returns an instance of the Branch Coalescing
/// Pass
FunctionPass *llvm::createPPCBranchCoalescingPass() { … }

INITIALIZE_PASS_BEGIN(PPCBranchCoalescing, DEBUG_TYPE,
                      "Branch Coalescing", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
INITIALIZE_PASS_END(PPCBranchCoalescing, DEBUG_TYPE, "Branch Coalescing",
                    false, false)

PPCBranchCoalescing::CoalescingCandidateInfo::CoalescingCandidateInfo()
    : … { … }

void PPCBranchCoalescing::CoalescingCandidateInfo::clear() { … }

void PPCBranchCoalescing::initialize(MachineFunction &MF) { … }

///
/// Analyze the branch statement to determine if it can be coalesced. This
/// method analyses the branch statement for the given candidate to determine
/// if it can be coalesced. If the branch can be coalesced, then the
/// BranchTargetBlock and the FallThroughBlock are recorded in the specified
/// Candidate.
///
///\param[in,out] Cand The coalescing candidate to analyze
///\return true if and only if the branch can be coalesced, false otherwise
///
bool PPCBranchCoalescing::canCoalesceBranch(CoalescingCandidateInfo &Cand) { … }

///
/// Determine if the two operand lists are identical
///
/// \param[in] OpList1 operand list
/// \param[in] OpList2 operand list
/// \return true if and only if the operands lists are identical
///
bool PPCBranchCoalescing::identicalOperands(
    ArrayRef<MachineOperand> OpList1, ArrayRef<MachineOperand> OpList2) const { … }

///
/// Moves ALL PHI instructions in SourceMBB to beginning of TargetMBB
/// and update them to refer to the new block.  PHI node ordering
/// cannot be assumed so it does not matter where the PHI instructions
/// are moved to in TargetMBB.
///
/// \param[in] SourceMBB block to move PHI instructions from
/// \param[in] TargetMBB block to move PHI instructions to
///
void PPCBranchCoalescing::moveAndUpdatePHIs(MachineBasicBlock *SourceMBB,
                                         MachineBasicBlock *TargetMBB) { … }

///
/// This function checks if MI can be moved to the beginning of the TargetMBB
/// following PHI instructions. A MI instruction can be moved to beginning of
/// the TargetMBB if there are no uses of it within the TargetMBB PHI nodes.
///
/// \param[in] MI the machine instruction to move.
/// \param[in] TargetMBB the machine basic block to move to
/// \return true if it is safe to move MI to beginning of TargetMBB,
///         false otherwise.
///
bool PPCBranchCoalescing::canMoveToBeginning(const MachineInstr &MI,
                                          const MachineBasicBlock &TargetMBB
                                          ) const { … }

///
/// This function checks if MI can be moved to the end of the TargetMBB,
/// immediately before the first terminator.  A MI instruction can be moved
/// to then end of the TargetMBB if no PHI node defines what MI uses within
/// it's own MBB.
///
/// \param[in] MI the machine instruction to move.
/// \param[in] TargetMBB the machine basic block to move to
/// \return true if it is safe to move MI to end of TargetMBB,
///         false otherwise.
///
bool PPCBranchCoalescing::canMoveToEnd(const MachineInstr &MI,
                                    const MachineBasicBlock &TargetMBB
                                    ) const { … }

///
/// This method checks to ensure the two coalescing candidates follows the
/// expected pattern required for coalescing.
///
/// \param[in] SourceRegion The candidate to move statements from
/// \param[in] TargetRegion The candidate to move statements to
/// \return true if all instructions in SourceRegion.BranchBlock can be merged
/// into a block in TargetRegion; false otherwise.
///
bool PPCBranchCoalescing::validateCandidates(
    CoalescingCandidateInfo &SourceRegion,
    CoalescingCandidateInfo &TargetRegion) const { … }

///
/// This method determines whether the two coalescing candidates can be merged.
/// In order to be merged, all instructions must be able to
///   1. Move to the beginning of the SourceRegion.BranchTargetBlock;
///   2. Move to the end of the TargetRegion.BranchBlock.
/// Merging involves moving the instructions in the
/// TargetRegion.BranchTargetBlock (also SourceRegion.BranchBlock).
///
/// This function first try to move instructions from the
/// TargetRegion.BranchTargetBlock down, to the beginning of the
/// SourceRegion.BranchTargetBlock. This is not possible if any register defined
/// in TargetRegion.BranchTargetBlock is used in a PHI node in the
/// SourceRegion.BranchTargetBlock. In this case, check whether the statement
/// can be moved up, to the end of the TargetRegion.BranchBlock (immediately
/// before the branch statement). If it cannot move, then these blocks cannot
/// be merged.
///
/// Note that there is no analysis for moving instructions past the fall-through
/// blocks because they are confirmed to be empty. An assert is thrown if they
/// are not.
///
/// \param[in] SourceRegion The candidate to move statements from
/// \param[in] TargetRegion The candidate to move statements to
/// \return true if all instructions in SourceRegion.BranchBlock can be merged
///         into a block in TargetRegion, false otherwise.
///
bool PPCBranchCoalescing::canMerge(CoalescingCandidateInfo &SourceRegion,
                                CoalescingCandidateInfo &TargetRegion) const { … }

/// Merge the instructions from SourceRegion.BranchBlock,
/// SourceRegion.BranchTargetBlock, and SourceRegion.FallThroughBlock into
/// TargetRegion.BranchBlock, TargetRegion.BranchTargetBlock and
/// TargetRegion.FallThroughBlock respectively.
///
/// The successors for blocks in TargetRegion will be updated to use the
/// successors from blocks in SourceRegion. Finally, the blocks in SourceRegion
/// will be removed from the function.
///
/// A region consists of a BranchBlock, a FallThroughBlock, and a
/// BranchTargetBlock. Branch coalesce works on patterns where the
/// TargetRegion's BranchTargetBlock must also be the SourceRegions's
/// BranchBlock.
///
///  Before mergeCandidates:
///
///  +---------------------------+
///  |  TargetRegion.BranchBlock |
///  +---------------------------+
///     /        |
///    /   +--------------------------------+
///   |    |  TargetRegion.FallThroughBlock |
///    \   +--------------------------------+
///     \        |
///  +----------------------------------+
///  |  TargetRegion.BranchTargetBlock  |
///  |  SourceRegion.BranchBlock        |
///  +----------------------------------+
///     /        |
///    /   +--------------------------------+
///   |    |  SourceRegion.FallThroughBlock |
///    \   +--------------------------------+
///     \        |
///  +----------------------------------+
///  |  SourceRegion.BranchTargetBlock  |
///  +----------------------------------+
///
///  After mergeCandidates:
///
///  +-----------------------------+
///  |  TargetRegion.BranchBlock   |
///  |  SourceRegion.BranchBlock   |
///  +-----------------------------+
///     /        |
///    /   +---------------------------------+
///   |    |  TargetRegion.FallThroughBlock  |
///   |    |  SourceRegion.FallThroughBlock  |
///    \   +---------------------------------+
///     \        |
///  +----------------------------------+
///  |  SourceRegion.BranchTargetBlock  |
///  +----------------------------------+
///
/// \param[in] SourceRegion The candidate to move blocks from
/// \param[in] TargetRegion The candidate to move blocks to
///
bool PPCBranchCoalescing::mergeCandidates(CoalescingCandidateInfo &SourceRegion,
                                       CoalescingCandidateInfo &TargetRegion) { … }

bool PPCBranchCoalescing::runOnMachineFunction(MachineFunction &MF) { … }
llvm/llvm/lib/Target/PowerPC/PPCBranchCoalescing.cpp
