1 //===- FlattenCFGPass.cpp - CFG Flatten 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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements flattening of CFG.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/Analysis/AliasAnalysis.h"
14 #include "llvm/IR/CFG.h"
15 #include "llvm/IR/InstrTypes.h"
16 #include "llvm/IR/ValueHandle.h"
17 #include "llvm/InitializePasses.h"
18 #include "llvm/Pass.h"
19 #include "llvm/Transforms/Scalar.h"
20 #include "llvm/Transforms/Utils/Local.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "flattencfg"
25 
26 namespace {
27 struct FlattenCFGPass : public FunctionPass {
28   static char ID; // Pass identification, replacement for typeid
29 public:
30   FlattenCFGPass() : FunctionPass(ID) {
31     initializeFlattenCFGPassPass(*PassRegistry::getPassRegistry());
32   }
33   bool runOnFunction(Function &F) override;
34 
35   void getAnalysisUsage(AnalysisUsage &AU) const override {
36     AU.addRequired<AAResultsWrapperPass>();
37   }
38 
39 private:
40   AliasAnalysis *AA;
41 };
42 }
43 
44 char FlattenCFGPass::ID = 0;
45 INITIALIZE_PASS_BEGIN(FlattenCFGPass, "flattencfg", "Flatten the CFG", false,
46                       false)
47 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
48 INITIALIZE_PASS_END(FlattenCFGPass, "flattencfg", "Flatten the CFG", false,
49                     false)
50 
51 // Public interface to the FlattenCFG pass
52 FunctionPass *llvm::createFlattenCFGPass() { return new FlattenCFGPass(); }
53 
54 /// iterativelyFlattenCFG - Call FlattenCFG on all the blocks in the function,
55 /// iterating until no more changes are made.
56 static bool iterativelyFlattenCFG(Function &F, AliasAnalysis *AA) {
57   bool Changed = false;
58   bool LocalChange = true;
59 
60   // Use block handles instead of iterating over function blocks directly
61   // to avoid using iterators invalidated by erasing blocks.
62   std::vector<WeakVH> Blocks;
63   Blocks.reserve(F.size());
64   for (auto &BB : F)
65     Blocks.push_back(&BB);
66 
67   while (LocalChange) {
68     LocalChange = false;
69 
70     // Loop over all of the basic blocks and try to flatten them.
71     for (WeakVH &BlockHandle : Blocks) {
72       // Skip blocks erased by FlattenCFG.
73       if (auto *BB = cast_or_null<BasicBlock>(BlockHandle))
74         if (FlattenCFG(BB, AA))
75           LocalChange = true;
76     }
77     Changed |= LocalChange;
78   }
79   return Changed;
80 }
81 
82 bool FlattenCFGPass::runOnFunction(Function &F) {
83   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
84   bool EverChanged = false;
85   // iterativelyFlattenCFG can make some blocks dead.
86   while (iterativelyFlattenCFG(F, AA)) {
87     removeUnreachableBlocks(F);
88     EverChanged = true;
89   }
90   return EverChanged;
91 }
92