101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard//===- FlattenCFGPass.cpp - CFG Flatten Pass ----------------------===// 201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// 301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// The LLVM Compiler Infrastructure 401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// 501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// This file is distributed under the University of Illinois Open Source 601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// License. See LICENSE.TXT for details. 701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// 801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard//===----------------------------------------------------------------------===// 901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// 1001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// This file implements flattening of CFG. 1101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// 1201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard//===----------------------------------------------------------------------===// 1301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 1401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard#include "llvm/Transforms/Scalar.h" 1501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard#include "llvm/Analysis/AliasAnalysis.h" 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 1701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard#include "llvm/Pass.h" 1801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard#include "llvm/Transforms/Utils/Local.h" 1901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellardusing namespace llvm; 2001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "flattencfg" 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 2301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellardnamespace { 2401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellardstruct FlattenCFGPass : public FunctionPass { 2501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard static char ID; // Pass identification, replacement for typeid 2601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellardpublic: 2701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard FlattenCFGPass() : FunctionPass(ID) { 2801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard initializeFlattenCFGPassPass(*PassRegistry::getPassRegistry()); 2901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 3101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 3301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard AU.addRequired<AliasAnalysis>(); 3401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 3501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 3601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellardprivate: 3701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard AliasAnalysis *AA; 3801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard}; 3901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard} 4001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 4101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellardchar FlattenCFGPass::ID = 0; 4201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom StellardINITIALIZE_PASS_BEGIN(FlattenCFGPass, "flattencfg", "Flatten the CFG", false, 4301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard false) 4401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom StellardINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 4501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom StellardINITIALIZE_PASS_END(FlattenCFGPass, "flattencfg", "Flatten the CFG", false, 4601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard false) 4701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 4801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// Public interface to the FlattenCFG pass 4901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom StellardFunctionPass *llvm::createFlattenCFGPass() { return new FlattenCFGPass(); } 5001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 5101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// iterativelyFlattenCFG - Call FlattenCFG on all the blocks in the function, 5201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// iterating until no more changes are made. 5301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellardstatic bool iterativelyFlattenCFG(Function &F, AliasAnalysis *AA) { 5401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard bool Changed = false; 5501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard bool LocalChange = true; 5601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard while (LocalChange) { 5701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard LocalChange = false; 5801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 5901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // Loop over all of the basic blocks and remove them if they are unneeded... 6001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // 6101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard for (Function::iterator BBIt = F.begin(); BBIt != F.end();) { 6201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard if (FlattenCFG(BBIt++, AA)) { 6301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard LocalChange = true; 6401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 6501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 6601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard Changed |= LocalChange; 6701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 6801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard return Changed; 6901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard} 7001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 7101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellardbool FlattenCFGPass::runOnFunction(Function &F) { 7201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard AA = &getAnalysis<AliasAnalysis>(); 7301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard bool EverChanged = false; 7401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard // iterativelyFlattenCFG can make some blocks dead. 7501d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard while (iterativelyFlattenCFG(F, AA)) { 7601d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard removeUnreachableBlocks(F); 7701d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard EverChanged = true; 7801d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard } 7901d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard return EverChanged; 8001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard} 81