ForLoopV2.cpp 2.79 KB
Newer Older
guruhegde's avatar
guruhegde committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
#include "ForLoopV2.h"
#include "Util.h"

#include <llvm/IR/IRBuilder.h>

using namespace llvm;

namespace tas {

void IRLoop::extractLoopSkeleton(Loop * L) {
  Header = L->getHeader();
  Latch = L->getLoopLatch();
  IdxAlloca = getLoopIndexVar(L);
  PreHeader = L->getLoopPreheader();
}

void IRLoop::analyze(Loop * L) {
  extractLoopSkeleton(L);
  
  // Copy loop body
  for (auto & BB : L->getBlocks()) {
    Blocks.push_back(BB);
  }
}

guruhegde's avatar
guruhegde committed
26
void IRLoop::constructEmptyLoop(AllocaInst * TripCount, BasicBlock * ExitBlock) {
guruhegde's avatar
guruhegde committed
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
  auto & Ctx = ExitBlock->getContext();
  const auto & F = ExitBlock->getParent();

  Latch = BasicBlock::Create(Ctx, "latch", F);
  Header = BasicBlock::Create(Ctx, "header", F, Latch);
  PreHeader = BasicBlock::Create(Ctx, "preheader", F, Header);
  EmptyBody = BasicBlock::Create(Ctx, "emptyblock", F, Latch);

  // Create Loop Index Variable.
  IRBuilder<> Builder(Ctx);
  Builder.SetInsertPoint(&F->getEntryBlock().front());
  IdxAlloca = Builder.CreateAlloca(Builder.getInt32Ty());

  // Set Index variable to 0 in preheader block.
  Builder.SetInsertPoint(PreHeader);
  Builder.CreateStore(Builder.getInt32(0), IdxAlloca);
  Builder.CreateBr(Header);

  // Populate latch block
  Builder.SetInsertPoint(Latch);
  auto BackEdge = Builder.CreateBr(Header);
  addIncrementIndexOp(IdxAlloca, BackEdge);

  // Branch Empty block to latch
  Builder.SetInsertPoint(EmptyBody);
  Builder.CreateBr(Latch);

  // Populate header block
  Builder.SetInsertPoint(Header);
  auto IdxVal = Builder.CreateLoad(IdxAlloca);
guruhegde's avatar
guruhegde committed
57 58
  auto TC = Builder.CreateLoad(TripCount);
  auto * Icmp = Builder.CreateICmpSLT(IdxVal, TC, "loop-predicate");
guruhegde's avatar
guruhegde committed
59 60 61
  Builder.CreateCondBr(Icmp, EmptyBody, ExitBlock);
}

guruhegde's avatar
guruhegde committed
62 63
void IRLoop::setLoopBlocks(std::vector<BasicBlock *> & BlockList) {
  for_each(BlockList, [&] (auto & BB) { Blocks.push_back(BB); });
guruhegde's avatar
guruhegde committed
64 65 66 67 68 69
  assert (!Blocks.empty() && "Blocks can't be empty");
  setSuccessor(Header, Blocks.front()); // True Path
  assert (Latch && "Latch is NULL");
  setSuccessor(Blocks.back(), Latch);
}

guruhegde's avatar
guruhegde committed
70
void LoopBodyTraverser::traverse(std::vector<BasicBlock *> & Blocks,
guruhegde's avatar
guruhegde committed
71
                                 BasicBlock * Start, BasicBlock * End) {
guruhegde's avatar
guruhegde committed
72
  if (std::find(Blocks.begin(), Blocks.end(), Start) != Blocks.end()) return;
guruhegde's avatar
guruhegde committed
73 74 75 76
  if (Start == End) return;
  Blocks.push_back(Start);
  for (auto * BB : successors(Start)){
    // Don't travel out of loop
guruhegde's avatar
guruhegde committed
77 78 79 80 81 82 83 84 85 86 87
    if (std::find(ExitBlocks.begin(), ExitBlocks.end(), BB) != ExitBlocks.end()) continue;
    traverse(Blocks, BB, End);
  }
}

void LoopBodyTraverser::traverseReverse(std::vector<BasicBlock *> & Blocks,
                                 BasicBlock * Start, BasicBlock * End) {
  if (std::find(Blocks.begin(), Blocks.end(), Start) != Blocks.end()) return;
  if (Start == End) return;
  Blocks.push_back(Start);
  for (auto * BB : predecessors(Start)){
guruhegde's avatar
guruhegde committed
88 89 90 91 92
    traverse(Blocks, BB, End);
  }
}

}