blob: 58d795757bc506066fe6a1a3d4e3dd945cacc7be [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;
Jim Stichnotha3f57b92015-07-30 12:46:04 -0700276 (*I)->liveness(getLiveness());
277 (*I)->livenessAddIntervals(getLiveness(), FirstInstNum, LastInstNum);
278 }
279 } else {
280 // The following code does a brute-force recalculation of live ranges as a
281 // result of adding the new phi edge split nodes. The liveness calculation
282 // is particularly expensive because the new nodes are not yet in a proper
283 // topological order and so convergence is slower.
284 //
285 // This code is kept here for reference and can be temporarily enabled in
286 // case the incremental code is under suspicion.
287 renumberInstructions();
288 liveness(Liveness_Intervals);
289 getVMetadata()->init(VMK_All);
290 }
291 Target->regAlloc(RAK_Phi);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700292}
293
294// Find a reasonable placement for nodes that have not yet been
295// placed, while maintaining the same relative ordering among already
296// placed nodes.
297void Cfg::reorderNodes() {
Andrew Scull713278a2015-07-22 17:17:02 -0700298 // TODO(ascull): it would be nice if the switch tests were always followed
299 // by the default case to allow for fall through.
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700300 typedef std::list<CfgNode *> PlacedList;
301 PlacedList Placed; // Nodes with relative placement locked down
302 PlacedList Unreachable; // Unreachable nodes
303 PlacedList::iterator NoPlace = Placed.end();
304 // Keep track of where each node has been tentatively placed so that
305 // we can manage insertions into the middle.
306 std::vector<PlacedList::iterator> PlaceIndex(Nodes.size(), NoPlace);
307 for (CfgNode *Node : Nodes) {
308 // The "do ... while(0);" construct is to factor out the
309 // --PlaceIndex and assert() statements before moving to the next
310 // node.
311 do {
Andrew Scull713278a2015-07-22 17:17:02 -0700312 if (Node != getEntryNode() && Node->getInEdges().empty()) {
313 // The node has essentially been deleted since it is not a
314 // successor of any other node.
315 Unreachable.push_back(Node);
316 PlaceIndex[Node->getIndex()] = Unreachable.end();
317 Node->setNeedsPlacement(false);
318 continue;
319 }
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700320 if (!Node->needsPlacement()) {
321 // Add to the end of the Placed list.
322 Placed.push_back(Node);
323 PlaceIndex[Node->getIndex()] = Placed.end();
324 continue;
325 }
326 Node->setNeedsPlacement(false);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700327 // Assume for now that the unplaced node is from edge-splitting
328 // and therefore has 1 in-edge and 1 out-edge (actually, possibly
329 // more than 1 in-edge if the predecessor node was contracted).
330 // If this changes in the future, rethink the strategy.
331 assert(Node->getInEdges().size() >= 1);
332 assert(Node->getOutEdges().size() == 1);
333
334 // If it's a (non-critical) edge where the successor has a single
335 // in-edge, then place it before the successor.
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800336 CfgNode *Succ = Node->getOutEdges().front();
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700337 if (Succ->getInEdges().size() == 1 &&
338 PlaceIndex[Succ->getIndex()] != NoPlace) {
339 Placed.insert(PlaceIndex[Succ->getIndex()], Node);
340 PlaceIndex[Node->getIndex()] = PlaceIndex[Succ->getIndex()];
341 continue;
342 }
343
344 // Otherwise, place it after the (first) predecessor.
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800345 CfgNode *Pred = Node->getInEdges().front();
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700346 auto PredPosition = PlaceIndex[Pred->getIndex()];
347 // It shouldn't be the case that PredPosition==NoPlace, but if
348 // that somehow turns out to be true, we just insert Node before
349 // PredPosition=NoPlace=Placed.end() .
350 if (PredPosition != NoPlace)
351 ++PredPosition;
352 Placed.insert(PredPosition, Node);
353 PlaceIndex[Node->getIndex()] = PredPosition;
354 } while (0);
355
356 --PlaceIndex[Node->getIndex()];
357 assert(*PlaceIndex[Node->getIndex()] == Node);
358 }
359
360 // Reorder Nodes according to the built-up lists.
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800361 SizeT OldSize = Nodes.size();
362 (void)OldSize;
363 Nodes.clear();
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700364 for (CfgNode *Node : Placed)
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800365 Nodes.push_back(Node);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700366 for (CfgNode *Node : Unreachable)
Jim Stichnothbfb410d2014-11-05 16:04:05 -0800367 Nodes.push_back(Node);
368 assert(Nodes.size() == OldSize);
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700369}
370
Qining Lu969f6a32015-07-31 09:58:34 -0700371namespace {
372void getRandomPostOrder(CfgNode *Node, llvm::BitVector &ToVisit,
373 Ice::NodeList &PostOrder,
374 Ice::RandomNumberGenerator *RNG) {
375 assert(ToVisit[Node->getIndex()]);
376 ToVisit[Node->getIndex()] = false;
377 NodeList Outs = Node->getOutEdges();
378 Ice::RandomShuffle(Outs.begin(), Outs.end(),
379 [RNG](int N) { return RNG->next(N); });
380 for (CfgNode *Next : Outs) {
381 if (ToVisit[Next->getIndex()])
382 getRandomPostOrder(Next, ToVisit, PostOrder, RNG);
383 }
384 PostOrder.push_back(Node);
385}
386} // end of anonymous namespace
387
388void Cfg::shuffleNodes() {
389 if (!Ctx->getFlags().shouldReorderBasicBlocks())
390 return;
391
392 NodeList ReversedReachable;
393 NodeList Unreachable;
394 llvm::BitVector ToVisit(Nodes.size(), true);
395 // Traverse from entry node.
396 getRandomPostOrder(getEntryNode(), ToVisit, ReversedReachable,
397 &Ctx->getRNG());
398 // Collect the unreachable nodes.
399 for (CfgNode *Node : Nodes)
400 if (ToVisit[Node->getIndex()])
401 Unreachable.push_back(Node);
402 // Copy the layout list to the Nodes.
403 SizeT OldSize = Nodes.size();
404 (void)OldSize;
405 Nodes.clear();
406 for (CfgNode *Node : reverse_range(ReversedReachable))
407 Nodes.emplace_back(Node);
408 for (CfgNode *Node : Unreachable) {
409 Nodes.emplace_back(Node);
410 }
411 assert(Nodes.size() == OldSize);
412
413 dump("After basic block shuffling");
414}
415
Matt Wala45a06232014-07-09 16:33:22 -0700416void Cfg::doArgLowering() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700417 TimerMarker T(TimerStack::TT_doArgLowering, this);
Matt Wala45a06232014-07-09 16:33:22 -0700418 getTarget()->lowerArguments();
419}
420
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700421void Cfg::doAddressOpt() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700422 TimerMarker T(TimerStack::TT_doAddressOpt, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700423 for (CfgNode *Node : Nodes)
424 Node->doAddressOpt();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700425}
426
Matt Walac3302742014-08-15 16:21:56 -0700427void Cfg::doNopInsertion() {
Qining Lu969f6a32015-07-31 09:58:34 -0700428 if (!Ctx->getFlags().shouldDoNopInsertion())
429 return;
Jim Stichnoth8363a062014-10-07 10:02:38 -0700430 TimerMarker T(TimerStack::TT_doNopInsertion, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700431 for (CfgNode *Node : Nodes)
432 Node->doNopInsertion();
Matt Walac3302742014-08-15 16:21:56 -0700433}
434
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700435void Cfg::genCode() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700436 TimerMarker T(TimerStack::TT_genCode, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700437 for (CfgNode *Node : Nodes)
438 Node->genCode();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700439}
440
441// Compute the stack frame layout.
442void Cfg::genFrame() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700443 TimerMarker T(TimerStack::TT_genFrame, this);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700444 getTarget()->addProlog(Entry);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700445 for (CfgNode *Node : Nodes)
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700446 if (Node->getHasReturn())
447 getTarget()->addEpilog(Node);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700448}
449
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700450// This is a lightweight version of live-range-end calculation. Marks
451// the last use of only those variables whose definition and uses are
452// completely with a single block. It is a quick single pass and
453// doesn't need to iterate until convergence.
454void Cfg::livenessLightweight() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700455 TimerMarker T(TimerStack::TT_livenessLightweight, this);
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700456 getVMetadata()->init(VMK_Uses);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700457 for (CfgNode *Node : Nodes)
458 Node->livenessLightweight();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700459}
460
461void Cfg::liveness(LivenessMode Mode) {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700462 TimerMarker T(TimerStack::TT_liveness, this);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700463 Live.reset(new Liveness(this, Mode));
Jim Stichnoth877b04e2014-10-15 15:13:06 -0700464 getVMetadata()->init(VMK_Uses);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700465 Live->init();
466 // Initialize with all nodes needing to be processed.
467 llvm::BitVector NeedToProcess(Nodes.size(), true);
468 while (NeedToProcess.any()) {
469 // Iterate in reverse topological order to speed up convergence.
Jim Stichnoth7e571362015-01-09 11:43:26 -0800470 for (CfgNode *Node : reverse_range(Nodes)) {
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700471 if (NeedToProcess[Node->getIndex()]) {
472 NeedToProcess[Node->getIndex()] = false;
473 bool Changed = Node->liveness(getLiveness());
474 if (Changed) {
475 // If the beginning-of-block liveness changed since the last
476 // iteration, mark all in-edges as needing to be processed.
Jim Stichnothf44f3712014-10-01 14:05:51 -0700477 for (CfgNode *Pred : Node->getInEdges())
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700478 NeedToProcess[Pred->getIndex()] = true;
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700479 }
480 }
481 }
482 }
483 if (Mode == Liveness_Intervals) {
484 // Reset each variable's live range.
Jim Stichnothf44f3712014-10-01 14:05:51 -0700485 for (Variable *Var : Variables)
486 Var->resetLiveRange();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700487 }
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800488 // Make a final pass over each node to delete dead instructions,
489 // collect the first and last instruction numbers, and add live
490 // range segments for that node.
491 for (CfgNode *Node : Nodes) {
492 InstNumberT FirstInstNum = Inst::NumberSentinel;
493 InstNumberT LastInstNum = Inst::NumberSentinel;
Jim Stichnoth29841e82014-12-23 12:26:24 -0800494 for (Inst &I : Node->getPhis()) {
495 I.deleteIfDead();
496 if (Mode == Liveness_Intervals && !I.isDeleted()) {
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800497 if (FirstInstNum == Inst::NumberSentinel)
Jim Stichnoth29841e82014-12-23 12:26:24 -0800498 FirstInstNum = I.getNumber();
499 assert(I.getNumber() > LastInstNum);
500 LastInstNum = I.getNumber();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700501 }
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800502 }
Jim Stichnoth29841e82014-12-23 12:26:24 -0800503 for (Inst &I : Node->getInsts()) {
504 I.deleteIfDead();
505 if (Mode == Liveness_Intervals && !I.isDeleted()) {
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800506 if (FirstInstNum == Inst::NumberSentinel)
Jim Stichnoth29841e82014-12-23 12:26:24 -0800507 FirstInstNum = I.getNumber();
508 assert(I.getNumber() > LastInstNum);
509 LastInstNum = I.getNumber();
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800510 }
511 }
512 if (Mode == Liveness_Intervals) {
513 // Special treatment for live in-args. Their liveness needs to
514 // extend beyond the beginning of the function, otherwise an arg
515 // whose only use is in the first instruction will end up having
516 // the trivial live range [2,2) and will *not* interfere with
517 // other arguments. So if the first instruction of the method
518 // is "r=arg1+arg2", both args may be assigned the same
519 // register. This is accomplished by extending the entry
520 // block's instruction range from [2,n) to [1,n) which will
521 // transform the problematic [2,2) live ranges into [1,2).
Jim Stichnothe4f65d82015-06-17 22:16:02 -0700522 if (Node == getEntryNode()) {
523 // TODO(stichnot): Make it a strict requirement that the entry
524 // node gets the lowest instruction numbers, so that extending
525 // the live range for in-args is guaranteed to work.
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800526 FirstInstNum = Inst::NumberExtended;
Jim Stichnothe4f65d82015-06-17 22:16:02 -0700527 }
Jim Stichnothe5b73e62014-12-15 09:58:51 -0800528 Node->livenessAddIntervals(getLiveness(), FirstInstNum, LastInstNum);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700529 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700530 }
531}
532
533// Traverse every Variable of every Inst and verify that it
534// appears within the Variable's computed live range.
535bool Cfg::validateLiveness() const {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700536 TimerMarker T(TimerStack::TT_validateLiveness, this);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700537 bool Valid = true;
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800538 OstreamLocker L(Ctx);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700539 Ostream &Str = Ctx->getStrDump();
Jim Stichnothf44f3712014-10-01 14:05:51 -0700540 for (CfgNode *Node : Nodes) {
Jim Stichnothae953202014-12-20 06:17:49 -0800541 Inst *FirstInst = nullptr;
Jim Stichnoth29841e82014-12-23 12:26:24 -0800542 for (Inst &Inst : Node->getInsts()) {
543 if (Inst.isDeleted())
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700544 continue;
Jim Stichnothae953202014-12-20 06:17:49 -0800545 if (FirstInst == nullptr)
Jim Stichnoth29841e82014-12-23 12:26:24 -0800546 FirstInst = &Inst;
547 InstNumberT InstNumber = Inst.getNumber();
548 if (Variable *Dest = Inst.getDest()) {
Jim Stichnoth47752552014-10-13 17:15:08 -0700549 if (!Dest->getIgnoreLiveness()) {
550 bool Invalid = false;
551 const bool IsDest = true;
552 if (!Dest->getLiveRange().containsValue(InstNumber, IsDest))
553 Invalid = true;
554 // Check that this instruction actually *begins* Dest's live
555 // range, by checking that Dest is not live in the previous
556 // instruction. As a special exception, we don't check this
557 // for the first instruction of the block, because a Phi
558 // temporary may be live at the end of the previous block,
559 // and if it is also assigned in the first instruction of
560 // this block, the adjacent live ranges get merged.
Jim Stichnoth29841e82014-12-23 12:26:24 -0800561 if (static_cast<class Inst *>(&Inst) != FirstInst &&
562 !Inst.isDestNonKillable() &&
Jim Stichnoth47752552014-10-13 17:15:08 -0700563 Dest->getLiveRange().containsValue(InstNumber - 1, IsDest))
564 Invalid = true;
565 if (Invalid) {
566 Valid = false;
Jim Stichnoth29841e82014-12-23 12:26:24 -0800567 Str << "Liveness error: inst " << Inst.getNumber() << " dest ";
Jim Stichnoth47752552014-10-13 17:15:08 -0700568 Dest->dump(this);
569 Str << " live range " << Dest->getLiveRange() << "\n";
570 }
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700571 }
572 }
Jim Stichnoth29841e82014-12-23 12:26:24 -0800573 for (SizeT I = 0; I < Inst.getSrcSize(); ++I) {
574 Operand *Src = Inst.getSrc(I);
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700575 SizeT NumVars = Src->getNumVars();
576 for (SizeT J = 0; J < NumVars; ++J) {
577 const Variable *Var = Src->getVar(J);
Jim Stichnoth47752552014-10-13 17:15:08 -0700578 const bool IsDest = false;
579 if (!Var->getIgnoreLiveness() &&
580 !Var->getLiveRange().containsValue(InstNumber, IsDest)) {
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700581 Valid = false;
Jim Stichnoth29841e82014-12-23 12:26:24 -0800582 Str << "Liveness error: inst " << Inst.getNumber() << " var ";
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700583 Var->dump(this);
584 Str << " live range " << Var->getLiveRange() << "\n";
585 }
586 }
587 }
588 }
589 }
590 return Valid;
591}
592
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700593void Cfg::contractEmptyNodes() {
Jim Stichnoth3d44fe82014-11-01 10:10:18 -0700594 // If we're decorating the asm output with register liveness info,
595 // this information may become corrupted or incorrect after
596 // contracting nodes that contain only redundant assignments. As
597 // such, we disable this pass when DecorateAsm is specified. This
598 // may make the resulting code look more branchy, but it should have
599 // no effect on the register assignments.
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800600 if (Ctx->getFlags().getDecorateAsm())
Jim Stichnoth3d44fe82014-11-01 10:10:18 -0700601 return;
Jim Stichnoth336f6c42014-10-30 15:01:31 -0700602 for (CfgNode *Node : Nodes) {
603 Node->contractIfEmpty();
604 }
605}
606
Jim Stichnothff9c7062014-09-18 04:50:49 -0700607void Cfg::doBranchOpt() {
Jim Stichnoth8363a062014-10-07 10:02:38 -0700608 TimerMarker T(TimerStack::TT_doBranchOpt, this);
Jim Stichnothf44f3712014-10-01 14:05:51 -0700609 for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
Andrew Scull713278a2015-07-22 17:17:02 -0700610 auto NextNode = I + 1;
Jim Stichnothae953202014-12-20 06:17:49 -0800611 (*I)->doBranchOpt(NextNode == E ? nullptr : *NextNode);
Jim Stichnothff9c7062014-09-18 04:50:49 -0700612 }
613}
614
Andrew Scull86df4e92015-07-30 13:54:44 -0700615void Cfg::markNodesForSandboxing() {
616 for (const InstJumpTable *JT : JumpTables)
617 for (SizeT I = 0; I < JT->getNumTargets(); ++I)
618 JT->getTarget(I)->setNeedsAlignment();
619}
620
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700621// ======================== Dump routines ======================== //
622
Jim Stichnothbbca7542015-02-11 16:08:31 -0800623// emitTextHeader() is not target-specific (apart from what is
624// abstracted by the Assembler), so it is defined here rather than in
625// the target lowering class.
626void Cfg::emitTextHeader(const IceString &MangledName, GlobalContext *Ctx,
627 const Assembler *Asm) {
Jim Stichnoth20b71f52015-06-24 15:52:24 -0700628 if (!BuildDefs::dump())
Jim Stichnoth729dbd02015-02-25 14:48:43 -0800629 return;
Jan Voung0faec4c2014-11-05 17:29:56 -0800630 Ostream &Str = Ctx->getStrEmit();
631 Str << "\t.text\n";
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800632 if (Ctx->getFlags().getFunctionSections())
Jan Voung0faec4c2014-11-05 17:29:56 -0800633 Str << "\t.section\t.text." << MangledName << ",\"ax\",@progbits\n";
Jim Stichnothbbca7542015-02-11 16:08:31 -0800634 if (!Asm->getInternal() || Ctx->getFlags().getDisableInternal()) {
Jan Voung0faec4c2014-11-05 17:29:56 -0800635 Str << "\t.globl\t" << MangledName << "\n";
Jan Voungb2d50842015-05-12 09:53:50 -0700636 Str << "\t.type\t" << MangledName << ",%function\n";
Jan Voung0faec4c2014-11-05 17:29:56 -0800637 }
Andrew Scull86df4e92015-07-30 13:54:44 -0700638 Str << "\t" << Asm->getAlignDirective() << " "
Jan Voungb2d50842015-05-12 09:53:50 -0700639 << Asm->getBundleAlignLog2Bytes() << ",0x";
Jan Voung08c3bcd2014-12-01 17:55:16 -0800640 for (uint8_t I : Asm->getNonExecBundlePadding())
Jan Voung0faec4c2014-11-05 17:29:56 -0800641 Str.write_hex(I);
642 Str << "\n";
643 Str << MangledName << ":\n";
644}
645
Andrew Scull86df4e92015-07-30 13:54:44 -0700646void Cfg::deleteJumpTableInsts() {
647 for (InstJumpTable *JumpTable : JumpTables)
648 JumpTable->setDeleted();
649}
650
651void Cfg::emitJumpTables() {
652 switch (Ctx->getFlags().getOutFileType()) {
653 case FT_Elf:
654 case FT_Iasm: {
655 // The emission needs to be delayed until the after the text section so save
656 // the offsets in the global context.
657 IceString MangledName = Ctx->mangleName(getFunctionName());
658 for (const InstJumpTable *JumpTable : JumpTables) {
659 SizeT NumTargets = JumpTable->getNumTargets();
660 JumpTableData &JT =
661 Ctx->addJumpTable(MangledName, JumpTable->getId(), NumTargets);
662 for (SizeT I = 0; I < NumTargets; ++I) {
663 SizeT Index = JumpTable->getTarget(I)->getIndex();
Jan Voungc2ec5812015-08-05 09:35:18 -0700664 JT.pushTarget(getAssembler()->getCfgNodeLabel(Index)->getPosition());
Andrew Scull86df4e92015-07-30 13:54:44 -0700665 }
666 }
667 } break;
668 case FT_Asm: {
669 // Emit the assembly directly so we don't need to hang on to all the names
670 for (const InstJumpTable *JumpTable : JumpTables)
671 getTarget()->emitJumpTable(this, JumpTable);
672 } break;
Andrew Scull86df4e92015-07-30 13:54:44 -0700673 }
674}
675
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700676void Cfg::emit() {
Jim Stichnoth20b71f52015-06-24 15:52:24 -0700677 if (!BuildDefs::dump())
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800678 return;
Jim Stichnoth8363a062014-10-07 10:02:38 -0700679 TimerMarker T(TimerStack::TT_emit, this);
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800680 if (Ctx->getFlags().getDecorateAsm()) {
Jim Stichnoth3d44fe82014-11-01 10:10:18 -0700681 renumberInstructions();
682 getVMetadata()->init(VMK_Uses);
683 liveness(Liveness_Basic);
684 dump("After recomputing liveness for -decorate-asm");
685 }
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800686 OstreamLocker L(Ctx);
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700687 Ostream &Str = Ctx->getStrEmit();
Andrew Scull86df4e92015-07-30 13:54:44 -0700688 IceString MangledName = Ctx->mangleName(getFunctionName());
689 const Assembler *Asm = getAssembler<>();
690 const bool NeedSandboxing = Ctx->getFlags().getUseSandboxing();
691
692 emitTextHeader(MangledName, Ctx, Asm);
693 deleteJumpTableInsts();
694 for (CfgNode *Node : Nodes) {
695 if (NeedSandboxing && Node->needsAlignment()) {
696 Str << "\t" << Asm->getAlignDirective() << " "
697 << Asm->getBundleAlignLog2Bytes() << "\n";
698 }
Jim Stichnothf44f3712014-10-01 14:05:51 -0700699 Node->emit(this);
Andrew Scull86df4e92015-07-30 13:54:44 -0700700 }
701 emitJumpTables();
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700702 Str << "\n";
Jim Stichnoth5bc2b1d2014-05-22 13:38:48 -0700703}
704
Jan Voung0faec4c2014-11-05 17:29:56 -0800705void Cfg::emitIAS() {
706 TimerMarker T(TimerStack::TT_emit, this);
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800707 // The emitIAS() routines emit into the internal assembler buffer,
Jim Stichnothbbca7542015-02-11 16:08:31 -0800708 // so there's no need to lock the streams.
Andrew Scull86df4e92015-07-30 13:54:44 -0700709 deleteJumpTableInsts();
710 const bool NeedSandboxing = Ctx->getFlags().getUseSandboxing();
711 for (CfgNode *Node : Nodes) {
712 if (NeedSandboxing && Node->needsAlignment())
713 getAssembler()->alignCfgNode();
Jan Voung0faec4c2014-11-05 17:29:56 -0800714 Node->emitIAS(this);
Andrew Scull86df4e92015-07-30 13:54:44 -0700715 }
716 emitJumpTables();
Jan Voung0faec4c2014-11-05 17:29:56 -0800717}
718
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700719// Dumps the IR with an optional introductory message.
720void Cfg::dump(const IceString &Message) {
Jim Stichnoth20b71f52015-06-24 15:52:24 -0700721 if (!BuildDefs::dump())
Karl Schimpfb6c96af2014-11-17 10:58:39 -0800722 return;
Jim Stichnothfa4efea2015-01-27 05:06:03 -0800723 if (!isVerbose())
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700724 return;
Jim Stichnothe4a8f402015-01-20 12:52:51 -0800725 OstreamLocker L(Ctx);
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700726 Ostream &Str = Ctx->getStrDump();
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700727 if (!Message.empty())
728 Str << "================ " << Message << " ================\n";
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700729 setCurrentNode(getEntryNode());
730 // Print function name+args
Jim Stichnothfa4efea2015-01-27 05:06:03 -0800731 if (isVerbose(IceV_Instructions)) {
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700732 Str << "define ";
Karl Schimpfdf80eb82015-02-09 14:20:22 -0800733 if (getInternal() && !Ctx->getFlags().getDisableInternal())
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700734 Str << "internal ";
Karl Schimpfdf6f9d12014-10-20 14:09:00 -0700735 Str << ReturnType << " @" << Ctx->mangleName(getFunctionName()) << "(";
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700736 for (SizeT i = 0; i < Args.size(); ++i) {
737 if (i > 0)
738 Str << ", ";
739 Str << Args[i]->getType() << " ";
740 Args[i]->dump(this);
741 }
742 Str << ") {\n";
743 }
Jim Stichnoth800dab22014-09-20 12:25:02 -0700744 resetCurrentNode();
Jim Stichnothfa4efea2015-01-27 05:06:03 -0800745 if (isVerbose(IceV_Liveness)) {
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700746 // Print summary info about variables
Jim Stichnothf44f3712014-10-01 14:05:51 -0700747 for (Variable *Var : Variables) {
Jim Stichnoth144cdce2014-09-22 16:02:59 -0700748 Str << "// multiblock=";
749 if (getVMetadata()->isTracked(Var))
750 Str << getVMetadata()->isMultiBlock(Var);
751 else
752 Str << "?";
753 Str << " weight=" << Var->getWeight() << " ";
Jim Stichnothd97c7df2014-06-04 11:57:08 -0700754 Var->dump(this);
755 Str << " LIVE=" << Var->getLiveRange() << "\n";
756 }
757 }
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700758 // Print each basic block
Jim Stichnothf44f3712014-10-01 14:05:51 -0700759 for (CfgNode *Node : Nodes)
760 Node->dump(this);
Jim Stichnothfa4efea2015-01-27 05:06:03 -0800761 if (isVerbose(IceV_Instructions))
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700762 Str << "}\n";
Jim Stichnothf7c9a142014-04-29 10:52:43 -0700763}
764
765} // end of namespace Ice