polly/lib/CodeGen/Utils.cpp

//===--- Utils.cpp - Utility functions for the code generation --*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains utility functions for the code generation.
//
//===----------------------------------------------------------------------===//

#include "polly/CodeGen/Utils.h"
#include "polly/CodeGen/IRBuilder.h"
#include "polly/ScopInfo.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"

using namespace llvm;

// Alternative to llvm::SplitCriticalEdge.
//
// Creates a new block which branches to Succ. The edge to split is redirected
// to the new block.
//
// The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is
// not critical.
// The issue with llvm::SplitEdge is that it does not always create the middle
// block, but reuses Prev/Succ if it can. We always want a new middle block.
static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ,
                             const char *Suffix, DominatorTree *DT,
                             LoopInfo *LI, RegionInfo *RI) {
  assert(Prev && Succ);

  // Before:
  //   \    /     /   //
  //    Prev     /    //
  //     |  \___/     //
  //     |   ___      //
  //     |  /   \     //
  //    Succ     \    //
  //   /    \     \   //

  // The algorithm to update DominatorTree and LoopInfo of
  // llvm::SplitCriticalEdge is more efficient than
  // llvm::SplitBlockPredecessors, which is more general. In the future we might
  // either modify llvm::SplitCriticalEdge to allow skipping the critical edge
  // check; or Copy&Pase it here.
  BasicBlock *MiddleBlock = SplitBlockPredecessors(
      Succ, ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI);

  if (RI) {
    Region *PrevRegion = RI->getRegionFor(Prev);
    Region *SuccRegion = RI->getRegionFor(Succ);
    if (PrevRegion->contains(MiddleBlock)) {
      RI->setRegionFor(MiddleBlock, PrevRegion);
    } else {
      RI->setRegionFor(MiddleBlock, SuccRegion);
    }
  }

  // After:
  //   \    /     /   //
  //    Prev     /    //
  //     |  \___/     //
  //     |            //
  // MiddleBlock      //
  //     |   ___      //
  //     |  /   \     //
  //    Succ     \    //
  //   /    \     \   //

  return MiddleBlock;
}

std::pair<polly::BBPair, BranchInst *>
polly::executeScopConditionally(Scop &S, Value *RTC, DominatorTree &DT,
                                RegionInfo &RI, LoopInfo &LI) {
  Region &R = S.getRegion();
  PollyIRBuilder Builder(S.getEntry());

  // Before:
  //
  //      \   /      //
  //    EnteringBB   //
  //   _____|_____   //
  //  /  EntryBB  \  //
  //  |  (region) |  //
  //  \_ExitingBB_/  //
  //        |        //
  //      ExitBB     //
  //      /    \     //

  // Create a fork block.
  BasicBlock *EnteringBB = S.getEnteringBlock();
  BasicBlock *EntryBB = S.getEntry();
  assert(EnteringBB && "Must be a simple region");
  BasicBlock *SplitBlock =
      splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI);
  SplitBlock->setName("polly.split_new_and_old");

  // If EntryBB is the exit block of the region that includes Prev, exclude
  // SplitBlock from that region by making it itself the exit block. This is
  // trivially possible because there is just one edge to EnteringBB.
  // This is necessary because we will add an outgoing edge from SplitBlock,
  // which would violate the single exit block requirement of PrevRegion.
  Region *PrevRegion = RI.getRegionFor(EnteringBB);
  while (PrevRegion->getExit() == EntryBB) {
    PrevRegion->replaceExit(SplitBlock);
    PrevRegion = PrevRegion->getParent();
  }
  RI.setRegionFor(SplitBlock, PrevRegion);

  // Create a join block
  BasicBlock *ExitingBB = S.getExitingBlock();
  BasicBlock *ExitBB = S.getExit();
  assert(ExitingBB && "Must be a simple region");
  BasicBlock *MergeBlock =
      splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI);
  MergeBlock->setName("polly.merge_new_and_old");

  // Exclude the join block from the region.
  R.replaceExitRecursive(MergeBlock);
  RI.setRegionFor(MergeBlock, R.getParent());

  //      \   /      //
  //    EnteringBB   //
  //        |        //
  //    SplitBlock   //
  //   _____|_____   //
  //  /  EntryBB  \  //
  //  |  (region) |  //
  //  \_ExitingBB_/  //
  //        |        //
  //    MergeBlock   //
  //        |        //
  //      ExitBB     //
  //      /    \     //

  // Create the start and exiting block.
  Function *F = SplitBlock->getParent();
  BasicBlock *StartBlock =
      BasicBlock::Create(F->getContext(), "polly.start", F);
  BasicBlock *ExitingBlock =
      BasicBlock::Create(F->getContext(), "polly.exiting", F);
  SplitBlock->getTerminator()->eraseFromParent();
  Builder.SetInsertPoint(SplitBlock);
  BranchInst *CondBr = Builder.CreateCondBr(RTC, StartBlock, S.getEntry());

  if (Loop *L = LI.getLoopFor(SplitBlock)) {
    L->addBasicBlockToLoop(StartBlock, LI);
    L->addBasicBlockToLoop(ExitingBlock, LI);
  }
  DT.addNewBlock(StartBlock, SplitBlock);
  DT.addNewBlock(ExitingBlock, StartBlock);
  RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock));
  RI.setRegionFor(ExitingBlock, RI.getRegionFor(SplitBlock));

  //      \   /                    //
  //    EnteringBB                 //
  //        |                      //
  //    SplitBlock---------\       //
  //   _____|_____         |       //
  //  /  EntryBB  \    StartBlock  //
  //  |  (region) |        |       //
  //  \_ExitingBB_/   ExitingBlock //
  //        |                      //
  //    MergeBlock                 //
  //        |                      //
  //      ExitBB                   //
  //      /    \                   //

  // Connect start block to exiting block.
  Builder.SetInsertPoint(StartBlock);
  Builder.CreateBr(ExitingBlock);
  DT.changeImmediateDominator(ExitingBlock, StartBlock);

  // Connect exiting block to join block.
  Builder.SetInsertPoint(ExitingBlock);
  Builder.CreateBr(MergeBlock);
  DT.changeImmediateDominator(MergeBlock, SplitBlock);

  //      \   /                    //
  //    EnteringBB                 //
  //        |                      //
  //    SplitBlock---------\       //
  //   _____|_____         |       //
  //  /  EntryBB  \    StartBlock  //
  //  |  (region) |        |       //
  //  \_ExitingBB_/   ExitingBlock //
  //        |              |       //
  //    MergeBlock---------/       //
  //        |                      //
  //      ExitBB                   //
  //      /    \                   //
  //

  // Split the edge between SplitBlock and EntryBB, to avoid a critical edge.
  splitEdge(SplitBlock, EntryBB, ".pre_entry_bb", &DT, &LI, &RI);

  //      \   /                    //
  //    EnteringBB                 //
  //        |                      //
  //    SplitBlock---------\       //
  //        |              |       //
  //    PreEntryBB         |       //
  //   _____|_____         |       //
  //  /  EntryBB  \    StartBlock  //
  //  |  (region) |        |       //
  //  \_ExitingBB_/   ExitingBlock //
  //        |              |       //
  //    MergeBlock---------/       //
  //        |                      //
  //      ExitBB                   //
  //      /    \                   //

  return std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr);
}