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/CodeGen/IRBuilder.h"
16 #include "polly/ScopInfo.h"
17 
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/RegionInfo.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
22 
23 using namespace llvm;
24 
25 BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) {
26   BasicBlock *StartBlock, *SplitBlock, *NewBlock;
27   Region &R = S.getRegion();
28   PollyIRBuilder Builder(R.getEntry());
29   DominatorTree &DT = P->getAnalysis<DominatorTreeWrapperPass>().getDomTree();
30   RegionInfo &RI = P->getAnalysis<RegionInfoPass>().getRegionInfo();
31   LoopInfo &LI = P->getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
32 
33   // Split the entry edge of the region and generate a new basic block on this
34   // edge. This function also updates ScopInfo and RegionInfo.
35   NewBlock = SplitEdge(R.getEnteringBlock(), R.getEntry(), &DT, &LI);
36   if (DT.dominates(R.getEntry(), NewBlock)) {
37     BasicBlock *OldBlock = R.getEntry();
38     std::string OldName = OldBlock->getName();
39 
40     // Update ScopInfo.
41     for (ScopStmt *Stmt : S)
42       if (Stmt->getBasicBlock() == OldBlock) {
43         Stmt->setBasicBlock(NewBlock);
44         break;
45       }
46 
47     // Update RegionInfo.
48     SplitBlock = OldBlock;
49     OldBlock->setName("polly.split");
50     NewBlock->setName(OldName);
51     R.replaceEntryRecursive(NewBlock);
52     RI.setRegionFor(NewBlock, &R);
53   } else {
54     RI.setRegionFor(NewBlock, R.getParent());
55     SplitBlock = NewBlock;
56   }
57 
58   SplitBlock->setName("polly.split_new_and_old");
59   Function *F = SplitBlock->getParent();
60   StartBlock = BasicBlock::Create(F->getContext(), "polly.start", F);
61   SplitBlock->getTerminator()->eraseFromParent();
62   Builder.SetInsertPoint(SplitBlock);
63   Builder.CreateCondBr(RTC, StartBlock, R.getEntry());
64   if (Loop *L = LI.getLoopFor(SplitBlock))
65     L->addBasicBlockToLoop(StartBlock, LI);
66   DT.addNewBlock(StartBlock, SplitBlock);
67   Builder.SetInsertPoint(StartBlock);
68 
69   BasicBlock *MergeBlock;
70 
71   if (R.getExit()->getSinglePredecessor())
72     // No splitEdge required.  A block with a single predecessor cannot have
73     // PHI nodes that would complicate life.
74     MergeBlock = R.getExit();
75   else {
76     MergeBlock = SplitEdge(R.getExitingBlock(), R.getExit(), &DT, &LI);
77     // SplitEdge will never split R.getExit(), as R.getExit() has more than
78     // one predecessor. Hence, mergeBlock is always a newly generated block.
79     R.replaceExitRecursive(MergeBlock);
80     RI.setRegionFor(MergeBlock, &R);
81   }
82 
83   Builder.CreateBr(MergeBlock);
84   MergeBlock->setName("polly.merge_new_and_old");
85 
86   if (DT.dominates(SplitBlock, MergeBlock))
87     DT.changeImmediateDominator(MergeBlock, SplitBlock);
88   return StartBlock;
89 }
90