llvm/llvm/lib/Transforms/Utils/FixIrreducible.cpp

//===- FixIrreducible.cpp - Convert irreducible control-flow into loops ---===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// INPUT CFG: The blocks H and B form an irreducible cycle with two headers.
//
//                        Entry
//                       /     \
//                      v       v
//                      H ----> B
//                      ^      /|
//                       `----' |
//                              v
//                             Exit
//
// OUTPUT CFG: Converted to a natural loop with a new header N.
//
//                        Entry
//                          |
//                          v
//                          N <---.
//                         / \     \
//                        /   \     |
//                       v     v    /
//                       H --> B --'
//                             |
//                             v
//                            Exit
//
// To convert an irreducible cycle C to a natural loop L:
//
// 1. Add a new node N to C.
// 2. Redirect all external incoming edges through N.
// 3. Redirect all edges incident on header H through N.
//
// This is sufficient to ensure that:
//
// a. Every closed path in C also exists in L, with the modification that any
//    path passing through H now passes through N before reaching H.
// b. Every external path incident on any entry of C is now incident on N and
//    then redirected to the entry.
//
// Thus, L is a strongly connected component dominated by N, and hence L is a
// natural loop with header N.
//
// When an irreducible cycle C with header H is transformed into a loop, the
// following invariants hold:
//
// 1. No new subcycles are "discovered" in the set (C-H). The only internal
//    edges that are redirected by the transform are incident on H. Any subcycle
//    S in (C-H), already existed prior to this transform, and is already in the
//    list of children for this cycle C.
//
// 2. Subcycles of C are not modified by the transform. For some subcycle S of
//    C, edges incident on the entries of S are either internal to C, or they
//    are now redirected through N, which is outside of S. So the list of
//    entries to S does not change. Since the transform only adds a block
//    outside S, and redirects edges that are not internal to S, the list of
//    blocks in S does not change.
//
// 3. Similarly, any natural loop L included in C is not affected, with one
//    exception: L is "destroyed" by the transform iff its header is H. The
//    backedges of such a loop are now redirected to N instead, and hence the
//    body of this loop gets merged into the new loop with header N.
//
// The actual transformation is handled by the ControlFlowHub, which redirects
// specified control flow edges through a set of guard blocks. This also moves
// every PHINode in an outgoing block to the hub. Since the hub dominates all
// the outgoing blocks, each such PHINode continues to dominate its uses. Since
// every header in an SCC has at least two predecessors, every value used in the
// header (or later) but defined in a predecessor (or earlier) is represented by
// a PHINode in a header. Hence the above handling of PHINodes is sufficient and
// no further processing is required to restore SSA.
//
// Limitation: The pass cannot handle switch statements and indirect
//             branches. Both must be lowered to plain branches first.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/FixIrreducible.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/Analysis/CycleAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/ControlFlowUtils.h"

#define DEBUG_TYPE …

usingnamespacellvm;

namespace {
struct FixIrreducible : public FunctionPass { … };
} // namespace

char FixIrreducible::ID = …;

FunctionPass *llvm::createFixIrreduciblePass() { … }

INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
                      "Convert irreducible control-flow into natural loops",
                      false /* Only looks at CFG */, false /* Analysis Pass */)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible",
                    "Convert irreducible control-flow into natural loops",
                    false /* Only looks at CFG */, false /* Analysis Pass */)

// When a new loop is created, existing children of the parent loop may now be
// fully inside the new loop. Reconnect these as children of the new loop.
static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
                                BasicBlock *OldHeader) { … }

static void updateLoopInfo(LoopInfo &LI, Cycle &C,
                           ArrayRef<BasicBlock *> GuardBlocks) { … }

// Given a set of blocks and headers in an irreducible SCC, convert it into a
// natural loop. Also insert this new loop at its appropriate place in the
// hierarchy of loops.
static bool fixIrreducible(Cycle &C, CycleInfo &CI, DominatorTree &DT,
                           LoopInfo *LI) { … }

static bool FixIrreducibleImpl(Function &F, CycleInfo &CI, DominatorTree &DT,
                               LoopInfo *LI) { … }

bool FixIrreducible::runOnFunction(Function &F) { … }

PreservedAnalyses FixIrreduciblePass::run(Function &F,
                                          FunctionAnalysisManager &AM) { … }