1 //===--- Utils.cpp - Utility functions for the code generation --*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains utility functions for the code generation.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "polly/CodeGen/Utils.h"
15 #include "polly/ScopInfo.h"
16 #include "llvm/IR/IRBuilder.h"
17 #include "llvm/Support/Debug.h"
18 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
19 
20 using namespace llvm;
21 
22 BasicBlock *polly::executeScopConditionally(Scop &S, Pass *PassInfo) {
23   BasicBlock *StartBlock, *SplitBlock, *NewBlock;
24   Region &R = S.getRegion();
25   IRBuilder<> Builder(R.getEntry());
26   DominatorTree &DT =
27       PassInfo->getAnalysis<DominatorTreeWrapperPass>().getDomTree();
28   RegionInfo &RI = PassInfo->getAnalysis<RegionInfo>();
29 
30   // Split the entry edge of the region and generate a new basic block on this
31   // edge. This function also updates ScopInfo and RegionInfo.
32   NewBlock = SplitEdge(R.getEnteringBlock(), R.getEntry(), PassInfo);
33   if (DT.dominates(R.getEntry(), NewBlock)) {
34     BasicBlock *OldBlock = R.getEntry();
35     std::string OldName = OldBlock->getName();
36 
37     // Update ScopInfo.
38     for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI)
39       if ((*SI)->getBasicBlock() == OldBlock) {
40         (*SI)->setBasicBlock(NewBlock);
41         break;
42       }
43 
44     // Update RegionInfo.
45     SplitBlock = OldBlock;
46     OldBlock->setName("polly.split");
47     NewBlock->setName(OldName);
48     R.replaceEntryRecursive(NewBlock);
49     RI.setRegionFor(NewBlock, &R);
50   } else {
51     RI.setRegionFor(NewBlock, R.getParent());
52     SplitBlock = NewBlock;
53   }
54 
55   SplitBlock->setName("polly.split_new_and_old");
56   Function *F = SplitBlock->getParent();
57   StartBlock = BasicBlock::Create(F->getContext(), "polly.start", F);
58   SplitBlock->getTerminator()->eraseFromParent();
59   Builder.SetInsertPoint(SplitBlock);
60   Builder.CreateCondBr(Builder.getTrue(), StartBlock, R.getEntry());
61   DT.addNewBlock(StartBlock, SplitBlock);
62   Builder.SetInsertPoint(StartBlock);
63 
64   BasicBlock *MergeBlock;
65 
66   if (R.getExit()->getSinglePredecessor())
67     // No splitEdge required.  A block with a single predecessor cannot have
68     // PHI nodes that would complicate life.
69     MergeBlock = R.getExit();
70   else {
71     MergeBlock = SplitEdge(R.getExitingBlock(), R.getExit(), PassInfo);
72     // SplitEdge will never split R.getExit(), as R.getExit() has more than
73     // one predecessor. Hence, mergeBlock is always a newly generated block.
74     R.replaceExitRecursive(MergeBlock);
75     RI.setRegionFor(MergeBlock, &R);
76   }
77 
78   Builder.CreateBr(MergeBlock);
79   MergeBlock->setName("polly.merge_new_and_old");
80 
81   if (DT.dominates(SplitBlock, MergeBlock))
82     DT.changeImmediateDominator(MergeBlock, SplitBlock);
83   return StartBlock;
84 }
85