blob: 9e5df996161e650feb98756426c9a52da4500109 [file] [log] [blame]
Jim Stichnothf7c9a142014-04-29 10:52:43 -07001//===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
2//
3// The Subzero Code Generator
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
Andrew Scull9612d322015-07-06 14:53:25 -07009///
10/// \file
11/// This file implements the Cfg class, including constant pool
12/// management.
13///
Jim Stichnothf7c9a142014-04-29 10:52:43 -070014//===----------------------------------------------------------------------===//
15
16#include "IceCfg.h"
John Porto67f8de92015-06-25 10:14:17 -070017
18#include "IceAssembler.h"
Jim Stichnothf7c9a142014-04-29 10:52:43 -070019#include "IceCfgNode.h"
Jim Stichnoth989a7032014-08-08 10:13:44 -070020#include "IceClFlags.h"
Jim Stichnothf7c9a142014-04-29 10:52:43 -070021#include "IceDefs.h"
Jan Voungec270732015-01-12 17:00:22 -080022#include "IceELFObjectWriter.h"
John Portof8b4cc82015-06-09 18:06:19 -070023#include "IceGlobalInits.h"
Jim Stichnothf7c9a142014-04-29 10:52:43 -070024#include "IceInst.h"
Jim Stichnothd97c7df2014-06-04 11:57:08 -070025#include "IceLiveness.h"
Jim Stichnothf7c9a142014-04-29 10:52:43 -070026#include "IceOperand.h"
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -070027#include "IceTargetLowering.h"
Jim Stichnothf7c9a142014-04-29 10:52:43 -070028
29namespace Ice {
30
Jim Stichnotha5fe17a2015-01-26 11:10:03 -080031ICE_TLS_DEFINE_FIELD(const Cfg *, Cfg, CurrentCfg);
Jim Stichnoth31c95592014-12-19 12:51:35 -080032
Jan Voung1d62cf02015-01-09 14:57:32 -080033ArenaAllocator<> *getCurrentCfgAllocator() {
Jim Stichnoth31c95592014-12-19 12:51:35 -080034 return Cfg::getCurrentCfgAllocator();
35}
36
Jim Stichnothbbca7542015-02-11 16:08:31 -080037Cfg::Cfg(GlobalContext *Ctx, uint32_t SequenceNumber)
Jan Voung1f47ad02015-03-20 15:01:26 -070038 : Ctx(Ctx), SequenceNumber(SequenceNumber),
Jim Stichnotheafb56c2015-06-22 10:35:22 -070039 VMask(Ctx->getFlags().getVerbose()), NextInstNumber(Inst::NumberInitial),
40 Allocator(new ArenaAllocator<>()), Live(nullptr),
41 Target(TargetLowering::createLowering(Ctx->getFlags().getTargetArch(),
42 this)),
Jan Voung8acded02014-09-22 18:02:25 -070043 VMetadata(new VariablesMetadata(this)),
Jan Voung1f47ad02015-03-20 15:01:26 -070044 TargetAssembler(TargetLowering::createAssembler(
Jim Stichnotheafb56c2015-06-22 10:35:22 -070045 Ctx->getFlags().getTargetArch(), this)) {
Karl Schimpf6fcbddd2014-11-06 09:49:24 -080046 assert(!Ctx->isIRGenerationDisabled() &&
47 "Attempt to build cfg when IR generation disabled");
48}
Jim Stichnothf7c9a142014-04-29 10:52:43 -070049
Jim Stichnoth8e928382015-02-02 17:03:08 -080050Cfg::~Cfg() { assert(ICE_TLS_GET_FIELD(CurrentCfg) == nullptr); }
Jim Stichnothf7c9a142014-04-29 10:52:43 -070051
52void Cfg::setError(const IceString &Message) {
53 HasError = true;
54 ErrorMessage = Message;
Jim Stichnothf7c9a142014-04-29 10:52:43 -070055}
56
Jim Stichnoth668a7a32014-12-10 15:32:25 -080057CfgNode *Cfg::makeNode() {
Jim Stichnothf7c9a142014-04-29 10:52:43 -070058 SizeT LabelIndex = Nodes.size();
Jim Stichnoth668a7a32014-12-10 15:32:25 -080059 CfgNode *Node = CfgNode::create(this, LabelIndex);
Jim Stichnothf7c9a142014-04-29 10:52:43 -070060 Nodes.push_back(Node);
61 return Node;
62}
63
Jim Stichnothf7c9a142014-04-29 10:52:43 -070064void Cfg::addArg(Variable *Arg) {
Jim Stichnoth144cdce2014-09-22 16:02:59 -070065 Arg->setIsArg();
Jim Stichnothf7c9a142014-04-29 10:52:43 -070066 Args.push_back(Arg);
67}
68
Jim Stichnoth144cdce2014-09-22 16:02:59 -070069void Cfg::addImplicitArg(Variable *Arg) {
70 Arg->setIsImplicitArg();
71 ImplicitArgs.push_back(Arg);
72}
73
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -070074// Returns whether the stack frame layout has been computed yet. This
75// is used for dumping the stack frame location of Variables.
76bool Cfg::hasComputedFrame() const { return getTarget()->hasComputedFrame(); }
77
John Portof8b4cc82015-06-09 18:06:19 -070078namespace {
79constexpr char BlockNameGlobalPrefix[] = ".L$profiler$block_name$";
80constexpr char BlockStatsGlobalPrefix[] = ".L$profiler$block_info$";
81
John Porto1bec8bc2015-06-22 10:51:13 -070082VariableDeclaration *nodeNameDeclaration(GlobalContext *Ctx,
83 const IceString &NodeAsmName) {
84 VariableDeclaration *Var = VariableDeclaration::create(Ctx);
John Portof8b4cc82015-06-09 18:06:19 -070085 Var->setName(BlockNameGlobalPrefix + NodeAsmName);
86 Var->setIsConstant(true);
John Porto1bec8bc2015-06-22 10:51:13 -070087 Var->addInitializer(VariableDeclaration::DataInitializer::create(
John Portof8b4cc82015-06-09 18:06:19 -070088 NodeAsmName.data(), NodeAsmName.size() + 1));
89 const SizeT Int64ByteSize = typeWidthInBytes(IceType_i64);
90 Var->setAlignment(Int64ByteSize); // Wasteful, 32-bit could use 4 bytes.
91 return Var;
92}
93
94VariableDeclaration *
John Porto1bec8bc2015-06-22 10:51:13 -070095blockProfilingInfoDeclaration(GlobalContext *Ctx, const IceString &NodeAsmName,
John Portof8b4cc82015-06-09 18:06:19 -070096 VariableDeclaration *NodeNameDeclaration) {
John Porto1bec8bc2015-06-22 10:51:13 -070097 VariableDeclaration *Var = VariableDeclaration::create(Ctx);
John Portof8b4cc82015-06-09 18:06:19 -070098 Var->setName(BlockStatsGlobalPrefix + NodeAsmName);
99 const SizeT Int64ByteSize = typeWidthInBytes(IceType_i64);
John Porto1bec8bc2015-06-22 10:51:13 -0700100 Var->addInitializer(
101 VariableDeclaration::ZeroInitializer::create(Int64ByteSize));
John Portof8b4cc82015-06-09 18:06:19 -0700102
103 const RelocOffsetT NodeNameDeclarationOffset = 0;
John Porto1bec8bc2015-06-22 10:51:13 -0700104 Var->addInitializer(VariableDeclaration::RelocInitializer::create(
John Portof8b4cc82015-06-09 18:06:19 -0700105 NodeNameDeclaration, NodeNameDeclarationOffset));
106 Var->setAlignment(Int64ByteSize);
107 return Var;
108}
John Portof8b4cc82015-06-09 18:06:19 -0700109} // end of anonymous namespace
110
111void Cfg::profileBlocks() {
112 if (GlobalInits == nullptr)
113 GlobalInits.reset(new VariableDeclarationList());
114
115 for (CfgNode *Node : Nodes) {
116 IceString NodeAsmName = Node->getAsmName();
John Porto1bec8bc2015-06-22 10:51:13 -0700117 GlobalInits->push_back(nodeNameDeclaration(Ctx, NodeAsmName));
John Portof8b4cc82015-06-09 18:06:19 -0700118 GlobalInits->push_back(
John Porto1bec8bc2015-06-22 10:51:13 -0700119 blockProfilingInfoDeclaration(Ctx, NodeAsmName, GlobalInits->back()));
John Portof8b4cc82015-06-09 18:06:19 -0700120 Node->profileExecutionCount(GlobalInits->back());
121 }
122}
123
124bool Cfg::isProfileGlobal(const VariableDeclaration &Var) {
125 return Var.getName().find(BlockStatsGlobalPrefix) == 0;
126}
127
128void Cfg::addCallToProfileSummary() {
129 // The call(s) to __Sz_profile_summary are added by the profiler in functions
130 // that cause the program to exit. This function is defined in
131 // runtime/szrt_profiler.c.
132 Constant *ProfileSummarySym =
133 Ctx->getConstantExternSym("__Sz_profile_summary");
134 constexpr SizeT NumArgs = 0;
135 constexpr Variable *Void = nullptr;
136 constexpr bool HasTailCall = false;
137 auto *Call =
138 InstCall::create(this, NumArgs, Void, ProfileSummarySym, HasTailCall);
139 getEntryNode()->getInsts().push_front(Call);
140}
141
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700142void Cfg::translate() {
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700143 if (hasError())
144 return;
Jim Stichnoth380d7b92015-01-30 13:10:39 -0800145 // FunctionTimer conditionally pushes/pops a TimerMarker if
146 // TimeEachFunction is enabled.
147 std::unique_ptr<TimerMarker> FunctionTimer;
Jim Stichnoth20b71f52015-06-24 15:52:24 -0700148 if (BuildDefs::dump()) {
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800149 const IceString &TimingFocusOn =
150 getContext()->getFlags().getTimingFocusOn();
Jim Stichnoth380d7b92015-01-30 13:10:39 -0800151 const IceString &Name = getFunctionName();
152 if (TimingFocusOn == "*" || TimingFocusOn == Name) {
Jim Stichnoth1c44d812014-12-08 14:57:52 -0800153 setFocusedTiming();
154 getContext()->resetTimer(GlobalContext::TSK_Default);
Jim Stichnoth380d7b92015-01-30 13:10:39 -0800155 getContext()->setTimerName(GlobalContext::TSK_Default, Name);
Jim Stichnoth1c44d812014-12-08 14:57:52 -0800156 }
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800157 if (getContext()->getFlags().getTimeEachFunction())
Jim Stichnoth380d7b92015-01-30 13:10:39 -0800158 FunctionTimer.reset(new TimerMarker(
159 getContext()->getTimerID(GlobalContext::TSK_Funcs, Name),
160 getContext(), GlobalContext::TSK_Funcs));
Jim Stichnothd14b1a02014-10-08 08:28:36 -0700161 }
Jim Stichnoth8363a062014-10-07 10:02:38 -0700162 TimerMarker T(TimerStack::TT_translate, this);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700163
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700164 dump("Initial CFG");
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700165
John Portof8b4cc82015-06-09 18:06:19 -0700166 if (getContext()->getFlags().getEnableBlockProfile()) {
167 profileBlocks();
168 // TODO(jpp): this is fragile, at best. Figure out a better way of detecting
169 // exit functions.
170 if (GlobalContext::matchSymbolName(getFunctionName(), "exit")) {
171 addCallToProfileSummary();
172 }
173 dump("Profiled CFG");
174 }
175
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700176 // The set of translation passes and their order are determined by
177 // the target.
178 getTarget()->translate();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700179
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700180 dump("Final output");
Jim Stichnoth8363a062014-10-07 10:02:38 -0700181 if (getFocusedTiming())
182 getContext()->dumpTimers();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700183}
184
Jim Stichnoth69d3f9c2015-03-23 10:33:38 -0700185void Cfg::computeInOutEdges() {
186 // Compute the out-edges.
Jim Stichnothf44f3712014-10-01 14:05:51 -0700187 for (CfgNode *Node : Nodes)
Jim Stichnoth69d3f9c2015-03-23 10:33:38 -0700188 Node->computeSuccessors();
189
190 // Prune any unreachable nodes before computing in-edges.
191 SizeT NumNodes = getNumNodes();
192 llvm::BitVector Reachable(NumNodes);
193 llvm::BitVector Pending(NumNodes);
194 Pending.set(getEntryNode()->getIndex());
195 while (true) {
196 int Index = Pending.find_first();
197 if (Index == -1)
198 break;
199 Pending.reset(Index);
200 Reachable.set(Index);
201 CfgNode *Node = Nodes[Index];
202 assert(Node->getIndex() == (SizeT)Index);
203 for (CfgNode *Succ : Node->getOutEdges()) {
204 SizeT SuccIndex = Succ->getIndex();
205 if (!Reachable.test(SuccIndex))
206 Pending.set(SuccIndex);
207 }
208 }
209 SizeT Dest = 0;
210 for (SizeT Source = 0; Source < NumNodes; ++Source) {
211 if (Reachable.test(Source)) {
212 Nodes[Dest] = Nodes[Source];
213 Nodes[Dest]->resetIndex(Dest);
214 // Compute the in-edges.
215 Nodes[Dest]->computePredecessors();
216 ++Dest;
217 }
218 }
219 Nodes.resize(Dest);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700220}
221
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700222void Cfg::renumberInstructions() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700223 TimerMarker T(TimerStack::TT_renumberInstructions, this);
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800224 NextInstNumber = Inst::NumberInitial;
Jim Stichnothf44f3712014-10-01 14:05:51 -0700225 for (CfgNode *Node : Nodes)
226 Node->renumberInstructions();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700227}
228
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700229// placePhiLoads() must be called before placePhiStores().
230void Cfg::placePhiLoads() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700231 TimerMarker T(TimerStack::TT_placePhiLoads, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700232 for (CfgNode *Node : Nodes)
233 Node->placePhiLoads();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700234}
235
236// placePhiStores() must be called after placePhiLoads().
237void Cfg::placePhiStores() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700238 TimerMarker T(TimerStack::TT_placePhiStores, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700239 for (CfgNode *Node : Nodes)
240 Node->placePhiStores();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700241}
242
243void Cfg::deletePhis() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700244 TimerMarker T(TimerStack::TT_deletePhis, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700245 for (CfgNode *Node : Nodes)
246 Node->deletePhis();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700247}
248
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700249void Cfg::advancedPhiLowering() {
250 TimerMarker T(TimerStack::TT_advancedPhiLowering, this);
Jim Stichnotha3f57b92015-07-30 12:46:04 -0700251 // Clear all previously computed live ranges (but not live-in/live-out bit
252 // vectors or last-use markers), because the follow-on register allocation is
253 // only concerned with live ranges across the newly created blocks.
254 for (Variable *Var : Variables) {
255 Var->getLiveRange().reset();
256 }
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700257 // This splits edges and appends new nodes to the end of the node
258 // list. This can invalidate iterators, so don't use an iterator.
259 SizeT NumNodes = getNumNodes();
Jim Stichnotha3f57b92015-07-30 12:46:04 -0700260 SizeT NumVars = getNumVariables();
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700261 for (SizeT I = 0; I < NumNodes; ++I)
262 Nodes[I]->advancedPhiLowering();
Jim Stichnotha3f57b92015-07-30 12:46:04 -0700263
264 TimerMarker TT(TimerStack::TT_lowerPhiAssignments, this);
265 if (true) {
266 // The following code does an in-place update of liveness and live ranges as
267 // a result of adding the new phi edge split nodes.
268 getLiveness()->initPhiEdgeSplits(Nodes.begin() + NumNodes,
269 Variables.begin() + NumVars);
270 TimerMarker TTT(TimerStack::TT_liveness, this);
271 // Iterate over the newly added nodes to add their liveness info.
272 for (auto I = Nodes.begin() + NumNodes, E = Nodes.end(); I != E; ++I) {
273 InstNumberT FirstInstNum = getNextInstNumber();
274 (*I)->renumberInstructions();
275 InstNumberT LastInstNum = getNextInstNumber() - 1;
276 // TODO(stichnot): May be able to speed up liveness and live range
277 // calculation by having it consider only pre-colored or infinite-weight
278 // variables. Could also simplify LinearScan::initForInfOnly() that way.
279 (*I)->liveness(getLiveness());
280 (*I)->livenessAddIntervals(getLiveness(), FirstInstNum, LastInstNum);
281 }
282 } else {
283 // The following code does a brute-force recalculation of live ranges as a
284 // result of adding the new phi edge split nodes. The liveness calculation
285 // is particularly expensive because the new nodes are not yet in a proper
286 // topological order and so convergence is slower.
287 //
288 // This code is kept here for reference and can be temporarily enabled in
289 // case the incremental code is under suspicion.
290 renumberInstructions();
291 liveness(Liveness_Intervals);
292 getVMetadata()->init(VMK_All);
293 }
294 Target->regAlloc(RAK_Phi);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700295}
296
297// Find a reasonable placement for nodes that have not yet been
298// placed, while maintaining the same relative ordering among already
299// placed nodes.
300void Cfg::reorderNodes() {
Andrew Scull713278a2015-07-22 17:17:02 -0700301 // TODO(ascull): it would be nice if the switch tests were always followed
302 // by the default case to allow for fall through.
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700303 typedef std::list<CfgNode *> PlacedList;
304 PlacedList Placed; // Nodes with relative placement locked down
305 PlacedList Unreachable; // Unreachable nodes
306 PlacedList::iterator NoPlace = Placed.end();
307 // Keep track of where each node has been tentatively placed so that
308 // we can manage insertions into the middle.
309 std::vector<PlacedList::iterator> PlaceIndex(Nodes.size(), NoPlace);
310 for (CfgNode *Node : Nodes) {
311 // The "do ... while(0);" construct is to factor out the
312 // --PlaceIndex and assert() statements before moving to the next
313 // node.
314 do {
Andrew Scull713278a2015-07-22 17:17:02 -0700315 if (Node != getEntryNode() && Node->getInEdges().empty()) {
316 // The node has essentially been deleted since it is not a
317 // successor of any other node.
318 Unreachable.push_back(Node);
319 PlaceIndex[Node->getIndex()] = Unreachable.end();
320 Node->setNeedsPlacement(false);
321 continue;
322 }
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700323 if (!Node->needsPlacement()) {
324 // Add to the end of the Placed list.
325 Placed.push_back(Node);
326 PlaceIndex[Node->getIndex()] = Placed.end();
327 continue;
328 }
329 Node->setNeedsPlacement(false);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700330 // Assume for now that the unplaced node is from edge-splitting
331 // and therefore has 1 in-edge and 1 out-edge (actually, possibly
332 // more than 1 in-edge if the predecessor node was contracted).
333 // If this changes in the future, rethink the strategy.
334 assert(Node->getInEdges().size() >= 1);
335 assert(Node->getOutEdges().size() == 1);
336
337 // If it's a (non-critical) edge where the successor has a single
338 // in-edge, then place it before the successor.
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800339 CfgNode *Succ = Node->getOutEdges().front();
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700340 if (Succ->getInEdges().size() == 1 &&
341 PlaceIndex[Succ->getIndex()] != NoPlace) {
342 Placed.insert(PlaceIndex[Succ->getIndex()], Node);
343 PlaceIndex[Node->getIndex()] = PlaceIndex[Succ->getIndex()];
344 continue;
345 }
346
347 // Otherwise, place it after the (first) predecessor.
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800348 CfgNode *Pred = Node->getInEdges().front();
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700349 auto PredPosition = PlaceIndex[Pred->getIndex()];
350 // It shouldn't be the case that PredPosition==NoPlace, but if
351 // that somehow turns out to be true, we just insert Node before
352 // PredPosition=NoPlace=Placed.end() .
353 if (PredPosition != NoPlace)
354 ++PredPosition;
355 Placed.insert(PredPosition, Node);
356 PlaceIndex[Node->getIndex()] = PredPosition;
357 } while (0);
358
359 --PlaceIndex[Node->getIndex()];
360 assert(*PlaceIndex[Node->getIndex()] == Node);
361 }
362
363 // Reorder Nodes according to the built-up lists.
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800364 SizeT OldSize = Nodes.size();
365 (void)OldSize;
366 Nodes.clear();
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700367 for (CfgNode *Node : Placed)
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800368 Nodes.push_back(Node);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700369 for (CfgNode *Node : Unreachable)
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800370 Nodes.push_back(Node);
371 assert(Nodes.size() == OldSize);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700372}
373
Matt Wala45a06232014-07-09 16:33:22 -0700374void Cfg::doArgLowering() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700375 TimerMarker T(TimerStack::TT_doArgLowering, this);
Matt Wala45a06232014-07-09 16:33:22 -0700376 getTarget()->lowerArguments();
377}
378
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700379void Cfg::doAddressOpt() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700380 TimerMarker T(TimerStack::TT_doAddressOpt, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700381 for (CfgNode *Node : Nodes)
382 Node->doAddressOpt();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700383}
384
Matt Walac3302742014-08-15 16:21:56 -0700385void Cfg::doNopInsertion() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700386 TimerMarker T(TimerStack::TT_doNopInsertion, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700387 for (CfgNode *Node : Nodes)
388 Node->doNopInsertion();
Matt Walac3302742014-08-15 16:21:56 -0700389}
390
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700391void Cfg::genCode() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700392 TimerMarker T(TimerStack::TT_genCode, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700393 for (CfgNode *Node : Nodes)
394 Node->genCode();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700395}
396
397// Compute the stack frame layout.
398void Cfg::genFrame() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700399 TimerMarker T(TimerStack::TT_genFrame, this);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700400 getTarget()->addProlog(Entry);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700401 for (CfgNode *Node : Nodes)
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700402 if (Node->getHasReturn())
403 getTarget()->addEpilog(Node);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700404}
405
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700406// This is a lightweight version of live-range-end calculation. Marks
407// the last use of only those variables whose definition and uses are
408// completely with a single block. It is a quick single pass and
409// doesn't need to iterate until convergence.
410void Cfg::livenessLightweight() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700411 TimerMarker T(TimerStack::TT_livenessLightweight, this);
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700412 getVMetadata()->init(VMK_Uses);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700413 for (CfgNode *Node : Nodes)
414 Node->livenessLightweight();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700415}
416
417void Cfg::liveness(LivenessMode Mode) {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700418 TimerMarker T(TimerStack::TT_liveness, this);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700419 Live.reset(new Liveness(this, Mode));
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700420 getVMetadata()->init(VMK_Uses);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700421 Live->init();
422 // Initialize with all nodes needing to be processed.
423 llvm::BitVector NeedToProcess(Nodes.size(), true);
424 while (NeedToProcess.any()) {
425 // Iterate in reverse topological order to speed up convergence.
Jim Stichnoth7e571362015-01-09 11:43:26 -0800426 for (CfgNode *Node : reverse_range(Nodes)) {
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700427 if (NeedToProcess[Node->getIndex()]) {
428 NeedToProcess[Node->getIndex()] = false;
429 bool Changed = Node->liveness(getLiveness());
430 if (Changed) {
431 // If the beginning-of-block liveness changed since the last
432 // iteration, mark all in-edges as needing to be processed.
Jim Stichnothf44f3712014-10-01 14:05:51 -0700433 for (CfgNode *Pred : Node->getInEdges())
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700434 NeedToProcess[Pred->getIndex()] = true;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700435 }
436 }
437 }
438 }
439 if (Mode == Liveness_Intervals) {
440 // Reset each variable's live range.
Jim Stichnothf44f3712014-10-01 14:05:51 -0700441 for (Variable *Var : Variables)
442 Var->resetLiveRange();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700443 }
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800444 // Make a final pass over each node to delete dead instructions,
445 // collect the first and last instruction numbers, and add live
446 // range segments for that node.
447 for (CfgNode *Node : Nodes) {
448 InstNumberT FirstInstNum = Inst::NumberSentinel;
449 InstNumberT LastInstNum = Inst::NumberSentinel;
Jim Stichnoth29841e82014-12-23 12:26:24 -0800450 for (Inst &I : Node->getPhis()) {
451 I.deleteIfDead();
452 if (Mode == Liveness_Intervals && !I.isDeleted()) {
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800453 if (FirstInstNum == Inst::NumberSentinel)
Jim Stichnoth29841e82014-12-23 12:26:24 -0800454 FirstInstNum = I.getNumber();
455 assert(I.getNumber() > LastInstNum);
456 LastInstNum = I.getNumber();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700457 }
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800458 }
Jim Stichnoth29841e82014-12-23 12:26:24 -0800459 for (Inst &I : Node->getInsts()) {
460 I.deleteIfDead();
461 if (Mode == Liveness_Intervals && !I.isDeleted()) {
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800462 if (FirstInstNum == Inst::NumberSentinel)
Jim Stichnoth29841e82014-12-23 12:26:24 -0800463 FirstInstNum = I.getNumber();
464 assert(I.getNumber() > LastInstNum);
465 LastInstNum = I.getNumber();
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800466 }
467 }
468 if (Mode == Liveness_Intervals) {
469 // Special treatment for live in-args. Their liveness needs to
470 // extend beyond the beginning of the function, otherwise an arg
471 // whose only use is in the first instruction will end up having
472 // the trivial live range [2,2) and will *not* interfere with
473 // other arguments. So if the first instruction of the method
474 // is "r=arg1+arg2", both args may be assigned the same
475 // register. This is accomplished by extending the entry
476 // block's instruction range from [2,n) to [1,n) which will
477 // transform the problematic [2,2) live ranges into [1,2).
Jim Stichnothe4f65d82015-06-17 22:16:02 -0700478 if (Node == getEntryNode()) {
479 // TODO(stichnot): Make it a strict requirement that the entry
480 // node gets the lowest instruction numbers, so that extending
481 // the live range for in-args is guaranteed to work.
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800482 FirstInstNum = Inst::NumberExtended;
Jim Stichnothe4f65d82015-06-17 22:16:02 -0700483 }
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800484 Node->livenessAddIntervals(getLiveness(), FirstInstNum, LastInstNum);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700485 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700486 }
487}
488
489// Traverse every Variable of every Inst and verify that it
490// appears within the Variable's computed live range.
491bool Cfg::validateLiveness() const {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700492 TimerMarker T(TimerStack::TT_validateLiveness, this);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700493 bool Valid = true;
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800494 OstreamLocker L(Ctx);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700495 Ostream &Str = Ctx->getStrDump();
Jim Stichnothf44f3712014-10-01 14:05:51 -0700496 for (CfgNode *Node : Nodes) {
Jim Stichnothae953202014-12-20 06:17:49 -0800497 Inst *FirstInst = nullptr;
Jim Stichnoth29841e82014-12-23 12:26:24 -0800498 for (Inst &Inst : Node->getInsts()) {
499 if (Inst.isDeleted())
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700500 continue;
Jim Stichnothae953202014-12-20 06:17:49 -0800501 if (FirstInst == nullptr)
Jim Stichnoth29841e82014-12-23 12:26:24 -0800502 FirstInst = &Inst;
503 InstNumberT InstNumber = Inst.getNumber();
504 if (Variable *Dest = Inst.getDest()) {
Jim Stichnoth47752552014-10-13 17:15:08 -0700505 if (!Dest->getIgnoreLiveness()) {
506 bool Invalid = false;
507 const bool IsDest = true;
508 if (!Dest->getLiveRange().containsValue(InstNumber, IsDest))
509 Invalid = true;
510 // Check that this instruction actually *begins* Dest's live
511 // range, by checking that Dest is not live in the previous
512 // instruction. As a special exception, we don't check this
513 // for the first instruction of the block, because a Phi
514 // temporary may be live at the end of the previous block,
515 // and if it is also assigned in the first instruction of
516 // this block, the adjacent live ranges get merged.
Jim Stichnoth29841e82014-12-23 12:26:24 -0800517 if (static_cast<class Inst *>(&Inst) != FirstInst &&
518 !Inst.isDestNonKillable() &&
Jim Stichnoth47752552014-10-13 17:15:08 -0700519 Dest->getLiveRange().containsValue(InstNumber - 1, IsDest))
520 Invalid = true;
521 if (Invalid) {
522 Valid = false;
Jim Stichnoth29841e82014-12-23 12:26:24 -0800523 Str << "Liveness error: inst " << Inst.getNumber() << " dest ";
Jim Stichnoth47752552014-10-13 17:15:08 -0700524 Dest->dump(this);
525 Str << " live range " << Dest->getLiveRange() << "\n";
526 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700527 }
528 }
Jim Stichnoth29841e82014-12-23 12:26:24 -0800529 for (SizeT I = 0; I < Inst.getSrcSize(); ++I) {
530 Operand *Src = Inst.getSrc(I);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700531 SizeT NumVars = Src->getNumVars();
532 for (SizeT J = 0; J < NumVars; ++J) {
533 const Variable *Var = Src->getVar(J);
Jim Stichnoth47752552014-10-13 17:15:08 -0700534 const bool IsDest = false;
535 if (!Var->getIgnoreLiveness() &&
536 !Var->getLiveRange().containsValue(InstNumber, IsDest)) {
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700537 Valid = false;
Jim Stichnoth29841e82014-12-23 12:26:24 -0800538 Str << "Liveness error: inst " << Inst.getNumber() << " var ";
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700539 Var->dump(this);
540 Str << " live range " << Var->getLiveRange() << "\n";
541 }
542 }
543 }
544 }
545 }
546 return Valid;
547}
548
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700549void Cfg::contractEmptyNodes() {
Jim Stichnoth3d44fe82014-11-01 10:10:18 -0700550 // If we're decorating the asm output with register liveness info,
551 // this information may become corrupted or incorrect after
552 // contracting nodes that contain only redundant assignments. As
553 // such, we disable this pass when DecorateAsm is specified. This
554 // may make the resulting code look more branchy, but it should have
555 // no effect on the register assignments.
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800556 if (Ctx->getFlags().getDecorateAsm())
Jim Stichnoth3d44fe82014-11-01 10:10:18 -0700557 return;
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700558 for (CfgNode *Node : Nodes) {
559 Node->contractIfEmpty();
560 }
561}
562
Jim Stichnothff9c7062014-09-18 04:50:49 -0700563void Cfg::doBranchOpt() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700564 TimerMarker T(TimerStack::TT_doBranchOpt, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700565 for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
Andrew Scull713278a2015-07-22 17:17:02 -0700566 auto NextNode = I + 1;
Jim Stichnothae953202014-12-20 06:17:49 -0800567 (*I)->doBranchOpt(NextNode == E ? nullptr : *NextNode);
Jim Stichnothff9c7062014-09-18 04:50:49 -0700568 }
569}
570
Andrew Scull86df4e92015-07-30 13:54:44 -0700571void Cfg::markNodesForSandboxing() {
572 for (const InstJumpTable *JT : JumpTables)
573 for (SizeT I = 0; I < JT->getNumTargets(); ++I)
574 JT->getTarget(I)->setNeedsAlignment();
575}
576
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700577// ======================== Dump routines ======================== //
578
Jim Stichnothbbca7542015-02-11 16:08:31 -0800579// emitTextHeader() is not target-specific (apart from what is
580// abstracted by the Assembler), so it is defined here rather than in
581// the target lowering class.
582void Cfg::emitTextHeader(const IceString &MangledName, GlobalContext *Ctx,
583 const Assembler *Asm) {
Jim Stichnoth20b71f52015-06-24 15:52:24 -0700584 if (!BuildDefs::dump())
Jim Stichnoth729dbd02015-02-25 14:48:43 -0800585 return;
Jan Voung0faec4c2014-11-05 17:29:56 -0800586 Ostream &Str = Ctx->getStrEmit();
587 Str << "\t.text\n";
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800588 if (Ctx->getFlags().getFunctionSections())
Jan Voung0faec4c2014-11-05 17:29:56 -0800589 Str << "\t.section\t.text." << MangledName << ",\"ax\",@progbits\n";
Jim Stichnothbbca7542015-02-11 16:08:31 -0800590 if (!Asm->getInternal() || Ctx->getFlags().getDisableInternal()) {
Jan Voung0faec4c2014-11-05 17:29:56 -0800591 Str << "\t.globl\t" << MangledName << "\n";
Jan Voungb2d50842015-05-12 09:53:50 -0700592 Str << "\t.type\t" << MangledName << ",%function\n";
Jan Voung0faec4c2014-11-05 17:29:56 -0800593 }
Andrew Scull86df4e92015-07-30 13:54:44 -0700594 Str << "\t" << Asm->getAlignDirective() << " "
Jan Voungb2d50842015-05-12 09:53:50 -0700595 << Asm->getBundleAlignLog2Bytes() << ",0x";
Jan Voung08c3bcd2014-12-01 17:55:16 -0800596 for (uint8_t I : Asm->getNonExecBundlePadding())
Jan Voung0faec4c2014-11-05 17:29:56 -0800597 Str.write_hex(I);
598 Str << "\n";
599 Str << MangledName << ":\n";
600}
601
Andrew Scull86df4e92015-07-30 13:54:44 -0700602void Cfg::deleteJumpTableInsts() {
603 for (InstJumpTable *JumpTable : JumpTables)
604 JumpTable->setDeleted();
605}
606
607void Cfg::emitJumpTables() {
608 switch (Ctx->getFlags().getOutFileType()) {
609 case FT_Elf:
610 case FT_Iasm: {
611 // The emission needs to be delayed until the after the text section so save
612 // the offsets in the global context.
613 IceString MangledName = Ctx->mangleName(getFunctionName());
614 for (const InstJumpTable *JumpTable : JumpTables) {
615 SizeT NumTargets = JumpTable->getNumTargets();
616 JumpTableData &JT =
617 Ctx->addJumpTable(MangledName, JumpTable->getId(), NumTargets);
618 for (SizeT I = 0; I < NumTargets; ++I) {
619 SizeT Index = JumpTable->getTarget(I)->getIndex();
620 JT.pushTarget(
621 getAssembler()->getOrCreateCfgNodeLabel(Index)->getPosition());
622 }
623 }
624 } break;
625 case FT_Asm: {
626 // Emit the assembly directly so we don't need to hang on to all the names
627 for (const InstJumpTable *JumpTable : JumpTables)
628 getTarget()->emitJumpTable(this, JumpTable);
629 } break;
630 default:
631 llvm::report_fatal_error("Invalid out file type.");
632 break;
633 }
634}
635
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700636void Cfg::emit() {
Jim Stichnoth20b71f52015-06-24 15:52:24 -0700637 if (!BuildDefs::dump())
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800638 return;
Jim Stichnoth8363a062014-10-07 10:02:38 -0700639 TimerMarker T(TimerStack::TT_emit, this);
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800640 if (Ctx->getFlags().getDecorateAsm()) {
Jim Stichnoth3d44fe82014-11-01 10:10:18 -0700641 renumberInstructions();
642 getVMetadata()->init(VMK_Uses);
643 liveness(Liveness_Basic);
644 dump("After recomputing liveness for -decorate-asm");
645 }
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800646 OstreamLocker L(Ctx);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700647 Ostream &Str = Ctx->getStrEmit();
Andrew Scull86df4e92015-07-30 13:54:44 -0700648 IceString MangledName = Ctx->mangleName(getFunctionName());
649 const Assembler *Asm = getAssembler<>();
650 const bool NeedSandboxing = Ctx->getFlags().getUseSandboxing();
651
652 emitTextHeader(MangledName, Ctx, Asm);
653 deleteJumpTableInsts();
654 for (CfgNode *Node : Nodes) {
655 if (NeedSandboxing && Node->needsAlignment()) {
656 Str << "\t" << Asm->getAlignDirective() << " "
657 << Asm->getBundleAlignLog2Bytes() << "\n";
658 }
Jim Stichnothf44f3712014-10-01 14:05:51 -0700659 Node->emit(this);
Andrew Scull86df4e92015-07-30 13:54:44 -0700660 }
661 emitJumpTables();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700662 Str << "\n";
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700663}
664
Jan Voung0faec4c2014-11-05 17:29:56 -0800665void Cfg::emitIAS() {
666 TimerMarker T(TimerStack::TT_emit, this);
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800667 // The emitIAS() routines emit into the internal assembler buffer,
Jim Stichnothbbca7542015-02-11 16:08:31 -0800668 // so there's no need to lock the streams.
Andrew Scull86df4e92015-07-30 13:54:44 -0700669 deleteJumpTableInsts();
670 const bool NeedSandboxing = Ctx->getFlags().getUseSandboxing();
671 for (CfgNode *Node : Nodes) {
672 if (NeedSandboxing && Node->needsAlignment())
673 getAssembler()->alignCfgNode();
Jan Voung0faec4c2014-11-05 17:29:56 -0800674 Node->emitIAS(this);
Andrew Scull86df4e92015-07-30 13:54:44 -0700675 }
676 emitJumpTables();
Jan Voung0faec4c2014-11-05 17:29:56 -0800677}
678
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700679// Dumps the IR with an optional introductory message.
680void Cfg::dump(const IceString &Message) {
Jim Stichnoth20b71f52015-06-24 15:52:24 -0700681 if (!BuildDefs::dump())
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800682 return;
Jim Stichnothfa4efea2015-01-27 05:06:03 -0800683 if (!isVerbose())
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700684 return;
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800685 OstreamLocker L(Ctx);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700686 Ostream &Str = Ctx->getStrDump();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700687 if (!Message.empty())
688 Str << "================ " << Message << " ================\n";
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700689 setCurrentNode(getEntryNode());
690 // Print function name+args
Jim Stichnothfa4efea2015-01-27 05:06:03 -0800691 if (isVerbose(IceV_Instructions)) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700692 Str << "define ";
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800693 if (getInternal() && !Ctx->getFlags().getDisableInternal())
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700694 Str << "internal ";
Karl Schimpfdf6f9d12014-10-20 14:09:00 -0700695 Str << ReturnType << " @" << Ctx->mangleName(getFunctionName()) << "(";
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700696 for (SizeT i = 0; i < Args.size(); ++i) {
697 if (i > 0)
698 Str << ", ";
699 Str << Args[i]->getType() << " ";
700 Args[i]->dump(this);
701 }
702 Str << ") {\n";
703 }
Jim Stichnoth800dab22014-09-20 12:25:02 -0700704 resetCurrentNode();
Jim Stichnothfa4efea2015-01-27 05:06:03 -0800705 if (isVerbose(IceV_Liveness)) {
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700706 // Print summary info about variables
Jim Stichnothf44f3712014-10-01 14:05:51 -0700707 for (Variable *Var : Variables) {
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700708 Str << "// multiblock=";
709 if (getVMetadata()->isTracked(Var))
710 Str << getVMetadata()->isMultiBlock(Var);
711 else
712 Str << "?";
713 Str << " weight=" << Var->getWeight() << " ";
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700714 Var->dump(this);
715 Str << " LIVE=" << Var->getLiveRange() << "\n";
716 }
717 }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700718 // Print each basic block
Jim Stichnothf44f3712014-10-01 14:05:51 -0700719 for (CfgNode *Node : Nodes)
720 Node->dump(this);
Jim Stichnothfa4efea2015-01-27 05:06:03 -0800721 if (isVerbose(IceV_Instructions))
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700722 Str << "}\n";
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700723}
724
725} // end of namespace Ice