1//===--- Utils.cpp - Utility functions for the code generation --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains utility functions for the code generation.
10//
11//===----------------------------------------------------------------------===//
12
13#include "polly/CodeGen/Utils.h"
14#include "polly/CodeGen/IRBuilder.h"
15#include "polly/ScopInfo.h"
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/Analysis/RegionInfo.h"
18#include "llvm/Transforms/Utils/BasicBlockUtils.h"
19
20using namespace llvm;
21
22// Alternative to llvm::SplitCriticalEdge.
23//
24// Creates a new block which branches to Succ. The edge to split is redirected
25// to the new block.
26//
27// The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is
28// not critical.
29// The issue with llvm::SplitEdge is that it does not always create the middle
30// block, but reuses Prev/Succ if it can. We always want a new middle block.
31static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ,
32 const char *Suffix, DominatorTree *DT,
33 LoopInfo *LI, RegionInfo *RI) {
34 assert(Prev && Succ);
35
36 // Before:
37 // \ / / //
38 // Prev / //
39 // | \___/ //
40 // | ___ //
41 // | / \ //
42 // Succ \ //
43 // / \ \ //
44
45 // The algorithm to update DominatorTree and LoopInfo of
46 // llvm::SplitCriticalEdge is more efficient than
47 // llvm::SplitBlockPredecessors, which is more general. In the future we might
48 // either modify llvm::SplitCriticalEdge to allow skipping the critical edge
49 // check; or Copy&Paste it here.
50 BasicBlock *MiddleBlock = SplitBlockPredecessors(
51 BB: Succ, Preds: ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI);
52
53 if (RI) {
54 Region *PrevRegion = RI->getRegionFor(BB: Prev);
55 Region *SuccRegion = RI->getRegionFor(BB: Succ);
56 if (PrevRegion->contains(BB: MiddleBlock)) {
57 RI->setRegionFor(BB: MiddleBlock, R: PrevRegion);
58 } else {
59 RI->setRegionFor(BB: MiddleBlock, R: SuccRegion);
60 }
61 }
62
63 // After:
64 // \ / / //
65 // Prev / //
66 // | \___/ //
67 // | //
68 // MiddleBlock //
69 // | ___ //
70 // | / \ //
71 // Succ \ //
72 // / \ \ //
73
74 return MiddleBlock;
75}
76
77std::pair<polly::BBPair, BranchInst *>
78polly::executeScopConditionally(Scop &S, Value *RTC, DominatorTree &DT,
79 RegionInfo &RI, LoopInfo &LI) {
80 Region &R = S.getRegion();
81 PollyIRBuilder Builder(S.getEntry());
82
83 // Before:
84 //
85 // \ / //
86 // EnteringBB //
87 // _____|_____ //
88 // / EntryBB \ //
89 // | (region) | //
90 // \_ExitingBB_/ //
91 // | //
92 // ExitBB //
93 // / \ //
94
95 // Create a fork block.
96 BasicBlock *EnteringBB = S.getEnteringBlock();
97 BasicBlock *EntryBB = S.getEntry();
98 assert(EnteringBB && "Must be a simple region");
99 BasicBlock *SplitBlock =
100 splitEdge(Prev: EnteringBB, Succ: EntryBB, Suffix: ".split_new_and_old", DT: &DT, LI: &LI, RI: &RI);
101 SplitBlock->setName("polly.split_new_and_old");
102
103 // If EntryBB is the exit block of the region that includes Prev, exclude
104 // SplitBlock from that region by making it itself the exit block. This is
105 // trivially possible because there is just one edge to EnteringBB.
106 // This is necessary because we will add an outgoing edge from SplitBlock,
107 // which would violate the single exit block requirement of PrevRegion.
108 Region *PrevRegion = RI.getRegionFor(BB: EnteringBB);
109 while (PrevRegion->getExit() == EntryBB) {
110 PrevRegion->replaceExit(BB: SplitBlock);
111 PrevRegion = PrevRegion->getParent();
112 }
113 RI.setRegionFor(BB: SplitBlock, R: PrevRegion);
114
115 // Create a join block
116 BasicBlock *ExitingBB = S.getExitingBlock();
117 BasicBlock *ExitBB = S.getExit();
118 assert(ExitingBB && "Must be a simple region");
119 BasicBlock *MergeBlock =
120 splitEdge(Prev: ExitingBB, Succ: ExitBB, Suffix: ".merge_new_and_old", DT: &DT, LI: &LI, RI: &RI);
121 MergeBlock->setName("polly.merge_new_and_old");
122
123 // Exclude the join block from the region.
124 R.replaceExitRecursive(NewExit: MergeBlock);
125 RI.setRegionFor(BB: MergeBlock, R: R.getParent());
126
127 // \ / //
128 // EnteringBB //
129 // | //
130 // SplitBlock //
131 // _____|_____ //
132 // / EntryBB \ //
133 // | (region) | //
134 // \_ExitingBB_/ //
135 // | //
136 // MergeBlock //
137 // | //
138 // ExitBB //
139 // / \ //
140
141 // Create the start and exiting block.
142 Function *F = SplitBlock->getParent();
143 BasicBlock *StartBlock =
144 BasicBlock::Create(Context&: F->getContext(), Name: "polly.start", Parent: F);
145 BasicBlock *ExitingBlock =
146 BasicBlock::Create(Context&: F->getContext(), Name: "polly.exiting", Parent: F);
147 SplitBlock->getTerminator()->eraseFromParent();
148 Builder.SetInsertPoint(SplitBlock);
149 BranchInst *CondBr = Builder.CreateCondBr(Cond: RTC, True: StartBlock, False: S.getEntry());
150
151 if (Loop *L = LI.getLoopFor(BB: SplitBlock)) {
152 L->addBasicBlockToLoop(NewBB: StartBlock, LI);
153 L->addBasicBlockToLoop(NewBB: ExitingBlock, LI);
154 }
155 DT.addNewBlock(BB: StartBlock, DomBB: SplitBlock);
156 DT.addNewBlock(BB: ExitingBlock, DomBB: StartBlock);
157 RI.setRegionFor(BB: StartBlock, R: RI.getRegionFor(BB: SplitBlock));
158 RI.setRegionFor(BB: ExitingBlock, R: RI.getRegionFor(BB: SplitBlock));
159
160 // \ / //
161 // EnteringBB //
162 // | //
163 // SplitBlock---------\ //
164 // _____|_____ | //
165 // / EntryBB \ StartBlock //
166 // | (region) | | //
167 // \_ExitingBB_/ ExitingBlock //
168 // | //
169 // MergeBlock //
170 // | //
171 // ExitBB //
172 // / \ //
173
174 // Connect start block to exiting block.
175 Builder.SetInsertPoint(StartBlock);
176 Builder.CreateBr(Dest: ExitingBlock);
177 DT.changeImmediateDominator(BB: ExitingBlock, NewBB: StartBlock);
178
179 // Connect exiting block to join block.
180 Builder.SetInsertPoint(ExitingBlock);
181 Builder.CreateBr(Dest: MergeBlock);
182 DT.changeImmediateDominator(BB: MergeBlock, NewBB: SplitBlock);
183
184 // \ / //
185 // EnteringBB //
186 // | //
187 // SplitBlock---------\ //
188 // _____|_____ | //
189 // / EntryBB \ StartBlock //
190 // | (region) | | //
191 // \_ExitingBB_/ ExitingBlock //
192 // | | //
193 // MergeBlock---------/ //
194 // | //
195 // ExitBB //
196 // / \ //
197 //
198
199 // Split the edge between SplitBlock and EntryBB, to avoid a critical edge.
200 splitEdge(Prev: SplitBlock, Succ: EntryBB, Suffix: ".pre_entry_bb", DT: &DT, LI: &LI, RI: &RI);
201
202 // \ / //
203 // EnteringBB //
204 // | //
205 // SplitBlock---------\ //
206 // | | //
207 // PreEntryBB | //
208 // _____|_____ | //
209 // / EntryBB \ StartBlock //
210 // | (region) | | //
211 // \_ExitingBB_/ ExitingBlock //
212 // | | //
213 // MergeBlock---------/ //
214 // | //
215 // ExitBB //
216 // / \ //
217
218 return std::make_pair(x: std::make_pair(x&: StartBlock, y&: ExitingBlock), y&: CondBr);
219}
220

source code of polly/lib/CodeGen/Utils.cpp