Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1 | //===- 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 Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 9 | /// |
| 10 | /// \file |
| 11 | /// This file implements the Cfg class, including constant pool |
| 12 | /// management. |
| 13 | /// |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #include "IceCfg.h" |
John Porto | 67f8de9 | 2015-06-25 10:14:17 -0700 | [diff] [blame] | 17 | |
| 18 | #include "IceAssembler.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 19 | #include "IceCfgNode.h" |
Jim Stichnoth | 989a703 | 2014-08-08 10:13:44 -0700 | [diff] [blame] | 20 | #include "IceClFlags.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 21 | #include "IceDefs.h" |
Jan Voung | ec27073 | 2015-01-12 17:00:22 -0800 | [diff] [blame] | 22 | #include "IceELFObjectWriter.h" |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 23 | #include "IceGlobalInits.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 24 | #include "IceInst.h" |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 25 | #include "IceLiveness.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 26 | #include "IceOperand.h" |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 27 | #include "IceTargetLowering.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 28 | |
| 29 | namespace Ice { |
| 30 | |
Jim Stichnoth | a5fe17a | 2015-01-26 11:10:03 -0800 | [diff] [blame] | 31 | ICE_TLS_DEFINE_FIELD(const Cfg *, Cfg, CurrentCfg); |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 32 | |
Jan Voung | 1d62cf0 | 2015-01-09 14:57:32 -0800 | [diff] [blame] | 33 | ArenaAllocator<> *getCurrentCfgAllocator() { |
Jim Stichnoth | 31c9559 | 2014-12-19 12:51:35 -0800 | [diff] [blame] | 34 | return Cfg::getCurrentCfgAllocator(); |
| 35 | } |
| 36 | |
Jim Stichnoth | bbca754 | 2015-02-11 16:08:31 -0800 | [diff] [blame] | 37 | Cfg::Cfg(GlobalContext *Ctx, uint32_t SequenceNumber) |
Jan Voung | 1f47ad0 | 2015-03-20 15:01:26 -0700 | [diff] [blame] | 38 | : Ctx(Ctx), SequenceNumber(SequenceNumber), |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 39 | VMask(Ctx->getFlags().getVerbose()), NextInstNumber(Inst::NumberInitial), |
| 40 | Allocator(new ArenaAllocator<>()), Live(nullptr), |
| 41 | Target(TargetLowering::createLowering(Ctx->getFlags().getTargetArch(), |
| 42 | this)), |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 43 | VMetadata(new VariablesMetadata(this)), |
Jan Voung | 1f47ad0 | 2015-03-20 15:01:26 -0700 | [diff] [blame] | 44 | TargetAssembler(TargetLowering::createAssembler( |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 45 | Ctx->getFlags().getTargetArch(), this)) { |
Karl Schimpf | 6fcbddd | 2014-11-06 09:49:24 -0800 | [diff] [blame] | 46 | assert(!Ctx->isIRGenerationDisabled() && |
| 47 | "Attempt to build cfg when IR generation disabled"); |
| 48 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 49 | |
Jim Stichnoth | 8e92838 | 2015-02-02 17:03:08 -0800 | [diff] [blame] | 50 | Cfg::~Cfg() { assert(ICE_TLS_GET_FIELD(CurrentCfg) == nullptr); } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 51 | |
| 52 | void Cfg::setError(const IceString &Message) { |
| 53 | HasError = true; |
| 54 | ErrorMessage = Message; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 55 | } |
| 56 | |
Jim Stichnoth | 668a7a3 | 2014-12-10 15:32:25 -0800 | [diff] [blame] | 57 | CfgNode *Cfg::makeNode() { |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 58 | SizeT LabelIndex = Nodes.size(); |
Jim Stichnoth | 668a7a3 | 2014-12-10 15:32:25 -0800 | [diff] [blame] | 59 | CfgNode *Node = CfgNode::create(this, LabelIndex); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 60 | Nodes.push_back(Node); |
| 61 | return Node; |
| 62 | } |
| 63 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 64 | void Cfg::addArg(Variable *Arg) { |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 65 | Arg->setIsArg(); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 66 | Args.push_back(Arg); |
| 67 | } |
| 68 | |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 69 | void Cfg::addImplicitArg(Variable *Arg) { |
| 70 | Arg->setIsImplicitArg(); |
| 71 | ImplicitArgs.push_back(Arg); |
| 72 | } |
| 73 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 74 | // Returns whether the stack frame layout has been computed yet. This |
| 75 | // is used for dumping the stack frame location of Variables. |
| 76 | bool Cfg::hasComputedFrame() const { return getTarget()->hasComputedFrame(); } |
| 77 | |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 78 | namespace { |
| 79 | constexpr char BlockNameGlobalPrefix[] = ".L$profiler$block_name$"; |
| 80 | constexpr char BlockStatsGlobalPrefix[] = ".L$profiler$block_info$"; |
| 81 | |
John Porto | 1bec8bc | 2015-06-22 10:51:13 -0700 | [diff] [blame] | 82 | VariableDeclaration *nodeNameDeclaration(GlobalContext *Ctx, |
| 83 | const IceString &NodeAsmName) { |
| 84 | VariableDeclaration *Var = VariableDeclaration::create(Ctx); |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 85 | Var->setName(BlockNameGlobalPrefix + NodeAsmName); |
| 86 | Var->setIsConstant(true); |
John Porto | 1bec8bc | 2015-06-22 10:51:13 -0700 | [diff] [blame] | 87 | Var->addInitializer(VariableDeclaration::DataInitializer::create( |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 88 | 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 | |
| 94 | VariableDeclaration * |
John Porto | 1bec8bc | 2015-06-22 10:51:13 -0700 | [diff] [blame] | 95 | blockProfilingInfoDeclaration(GlobalContext *Ctx, const IceString &NodeAsmName, |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 96 | VariableDeclaration *NodeNameDeclaration) { |
John Porto | 1bec8bc | 2015-06-22 10:51:13 -0700 | [diff] [blame] | 97 | VariableDeclaration *Var = VariableDeclaration::create(Ctx); |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 98 | Var->setName(BlockStatsGlobalPrefix + NodeAsmName); |
| 99 | const SizeT Int64ByteSize = typeWidthInBytes(IceType_i64); |
John Porto | 1bec8bc | 2015-06-22 10:51:13 -0700 | [diff] [blame] | 100 | Var->addInitializer( |
| 101 | VariableDeclaration::ZeroInitializer::create(Int64ByteSize)); |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 102 | |
| 103 | const RelocOffsetT NodeNameDeclarationOffset = 0; |
John Porto | 1bec8bc | 2015-06-22 10:51:13 -0700 | [diff] [blame] | 104 | Var->addInitializer(VariableDeclaration::RelocInitializer::create( |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 105 | NodeNameDeclaration, NodeNameDeclarationOffset)); |
| 106 | Var->setAlignment(Int64ByteSize); |
| 107 | return Var; |
| 108 | } |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 109 | } // end of anonymous namespace |
| 110 | |
| 111 | void Cfg::profileBlocks() { |
| 112 | if (GlobalInits == nullptr) |
| 113 | GlobalInits.reset(new VariableDeclarationList()); |
| 114 | |
| 115 | for (CfgNode *Node : Nodes) { |
| 116 | IceString NodeAsmName = Node->getAsmName(); |
John Porto | 1bec8bc | 2015-06-22 10:51:13 -0700 | [diff] [blame] | 117 | GlobalInits->push_back(nodeNameDeclaration(Ctx, NodeAsmName)); |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 118 | GlobalInits->push_back( |
John Porto | 1bec8bc | 2015-06-22 10:51:13 -0700 | [diff] [blame] | 119 | blockProfilingInfoDeclaration(Ctx, NodeAsmName, GlobalInits->back())); |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 120 | Node->profileExecutionCount(GlobalInits->back()); |
| 121 | } |
| 122 | } |
| 123 | |
| 124 | bool Cfg::isProfileGlobal(const VariableDeclaration &Var) { |
| 125 | return Var.getName().find(BlockStatsGlobalPrefix) == 0; |
| 126 | } |
| 127 | |
| 128 | void 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 Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 142 | void Cfg::translate() { |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 143 | if (hasError()) |
| 144 | return; |
Jim Stichnoth | 380d7b9 | 2015-01-30 13:10:39 -0800 | [diff] [blame] | 145 | // FunctionTimer conditionally pushes/pops a TimerMarker if |
| 146 | // TimeEachFunction is enabled. |
| 147 | std::unique_ptr<TimerMarker> FunctionTimer; |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 148 | if (BuildDefs::dump()) { |
Karl Schimpf | df80eb8 | 2015-02-09 14:20:22 -0800 | [diff] [blame] | 149 | const IceString &TimingFocusOn = |
| 150 | getContext()->getFlags().getTimingFocusOn(); |
Jim Stichnoth | 380d7b9 | 2015-01-30 13:10:39 -0800 | [diff] [blame] | 151 | const IceString &Name = getFunctionName(); |
| 152 | if (TimingFocusOn == "*" || TimingFocusOn == Name) { |
Jim Stichnoth | 1c44d81 | 2014-12-08 14:57:52 -0800 | [diff] [blame] | 153 | setFocusedTiming(); |
| 154 | getContext()->resetTimer(GlobalContext::TSK_Default); |
Jim Stichnoth | 380d7b9 | 2015-01-30 13:10:39 -0800 | [diff] [blame] | 155 | getContext()->setTimerName(GlobalContext::TSK_Default, Name); |
Jim Stichnoth | 1c44d81 | 2014-12-08 14:57:52 -0800 | [diff] [blame] | 156 | } |
Karl Schimpf | df80eb8 | 2015-02-09 14:20:22 -0800 | [diff] [blame] | 157 | if (getContext()->getFlags().getTimeEachFunction()) |
Jim Stichnoth | 380d7b9 | 2015-01-30 13:10:39 -0800 | [diff] [blame] | 158 | FunctionTimer.reset(new TimerMarker( |
| 159 | getContext()->getTimerID(GlobalContext::TSK_Funcs, Name), |
| 160 | getContext(), GlobalContext::TSK_Funcs)); |
Jim Stichnoth | d14b1a0 | 2014-10-08 08:28:36 -0700 | [diff] [blame] | 161 | } |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 162 | TimerMarker T(TimerStack::TT_translate, this); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 163 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 164 | dump("Initial CFG"); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 165 | |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 166 | 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 Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 176 | // The set of translation passes and their order are determined by |
| 177 | // the target. |
| 178 | getTarget()->translate(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 179 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 180 | dump("Final output"); |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 181 | if (getFocusedTiming()) |
| 182 | getContext()->dumpTimers(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 183 | } |
| 184 | |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 185 | void Cfg::computeInOutEdges() { |
| 186 | // Compute the out-edges. |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 187 | for (CfgNode *Node : Nodes) |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 188 | 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 Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 220 | } |
| 221 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 222 | void Cfg::renumberInstructions() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 223 | TimerMarker T(TimerStack::TT_renumberInstructions, this); |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 224 | NextInstNumber = Inst::NumberInitial; |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 225 | for (CfgNode *Node : Nodes) |
| 226 | Node->renumberInstructions(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 227 | } |
| 228 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 229 | // placePhiLoads() must be called before placePhiStores(). |
| 230 | void Cfg::placePhiLoads() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 231 | TimerMarker T(TimerStack::TT_placePhiLoads, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 232 | for (CfgNode *Node : Nodes) |
| 233 | Node->placePhiLoads(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | // placePhiStores() must be called after placePhiLoads(). |
| 237 | void Cfg::placePhiStores() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 238 | TimerMarker T(TimerStack::TT_placePhiStores, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 239 | for (CfgNode *Node : Nodes) |
| 240 | Node->placePhiStores(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 241 | } |
| 242 | |
| 243 | void Cfg::deletePhis() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 244 | TimerMarker T(TimerStack::TT_deletePhis, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 245 | for (CfgNode *Node : Nodes) |
| 246 | Node->deletePhis(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 247 | } |
| 248 | |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 249 | void Cfg::advancedPhiLowering() { |
| 250 | TimerMarker T(TimerStack::TT_advancedPhiLowering, this); |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 251 | // 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 Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 257 | // 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 Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 260 | SizeT NumVars = getNumVariables(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 261 | for (SizeT I = 0; I < NumNodes; ++I) |
| 262 | Nodes[I]->advancedPhiLowering(); |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 263 | |
| 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 Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 295 | } |
| 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. |
| 300 | void Cfg::reorderNodes() { |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 301 | // TODO(ascull): it would be nice if the switch tests were always followed |
| 302 | // by the default case to allow for fall through. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 303 | 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 Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 315 | 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 Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 323 | 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 Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 330 | // 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 Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 339 | CfgNode *Succ = Node->getOutEdges().front(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 340 | 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 Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 348 | CfgNode *Pred = Node->getInEdges().front(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 349 | 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 Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 364 | SizeT OldSize = Nodes.size(); |
| 365 | (void)OldSize; |
| 366 | Nodes.clear(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 367 | for (CfgNode *Node : Placed) |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 368 | Nodes.push_back(Node); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 369 | for (CfgNode *Node : Unreachable) |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 370 | Nodes.push_back(Node); |
| 371 | assert(Nodes.size() == OldSize); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 372 | } |
| 373 | |
Matt Wala | 45a0623 | 2014-07-09 16:33:22 -0700 | [diff] [blame] | 374 | void Cfg::doArgLowering() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 375 | TimerMarker T(TimerStack::TT_doArgLowering, this); |
Matt Wala | 45a0623 | 2014-07-09 16:33:22 -0700 | [diff] [blame] | 376 | getTarget()->lowerArguments(); |
| 377 | } |
| 378 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 379 | void Cfg::doAddressOpt() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 380 | TimerMarker T(TimerStack::TT_doAddressOpt, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 381 | for (CfgNode *Node : Nodes) |
| 382 | Node->doAddressOpt(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 383 | } |
| 384 | |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 385 | void Cfg::doNopInsertion() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 386 | TimerMarker T(TimerStack::TT_doNopInsertion, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 387 | for (CfgNode *Node : Nodes) |
| 388 | Node->doNopInsertion(); |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 389 | } |
| 390 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 391 | void Cfg::genCode() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 392 | TimerMarker T(TimerStack::TT_genCode, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 393 | for (CfgNode *Node : Nodes) |
| 394 | Node->genCode(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 395 | } |
| 396 | |
| 397 | // Compute the stack frame layout. |
| 398 | void Cfg::genFrame() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 399 | TimerMarker T(TimerStack::TT_genFrame, this); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 400 | getTarget()->addProlog(Entry); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 401 | for (CfgNode *Node : Nodes) |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 402 | if (Node->getHasReturn()) |
| 403 | getTarget()->addEpilog(Node); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 404 | } |
| 405 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 406 | // 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. |
| 410 | void Cfg::livenessLightweight() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 411 | TimerMarker T(TimerStack::TT_livenessLightweight, this); |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 412 | getVMetadata()->init(VMK_Uses); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 413 | for (CfgNode *Node : Nodes) |
| 414 | Node->livenessLightweight(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 415 | } |
| 416 | |
| 417 | void Cfg::liveness(LivenessMode Mode) { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 418 | TimerMarker T(TimerStack::TT_liveness, this); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 419 | Live.reset(new Liveness(this, Mode)); |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 420 | getVMetadata()->init(VMK_Uses); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 421 | 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 Stichnoth | 7e57136 | 2015-01-09 11:43:26 -0800 | [diff] [blame] | 426 | for (CfgNode *Node : reverse_range(Nodes)) { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 427 | 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 Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 433 | for (CfgNode *Pred : Node->getInEdges()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 434 | NeedToProcess[Pred->getIndex()] = true; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 435 | } |
| 436 | } |
| 437 | } |
| 438 | } |
| 439 | if (Mode == Liveness_Intervals) { |
| 440 | // Reset each variable's live range. |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 441 | for (Variable *Var : Variables) |
| 442 | Var->resetLiveRange(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 443 | } |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 444 | // 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 Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 450 | for (Inst &I : Node->getPhis()) { |
| 451 | I.deleteIfDead(); |
| 452 | if (Mode == Liveness_Intervals && !I.isDeleted()) { |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 453 | if (FirstInstNum == Inst::NumberSentinel) |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 454 | FirstInstNum = I.getNumber(); |
| 455 | assert(I.getNumber() > LastInstNum); |
| 456 | LastInstNum = I.getNumber(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 457 | } |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 458 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 459 | for (Inst &I : Node->getInsts()) { |
| 460 | I.deleteIfDead(); |
| 461 | if (Mode == Liveness_Intervals && !I.isDeleted()) { |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 462 | if (FirstInstNum == Inst::NumberSentinel) |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 463 | FirstInstNum = I.getNumber(); |
| 464 | assert(I.getNumber() > LastInstNum); |
| 465 | LastInstNum = I.getNumber(); |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 466 | } |
| 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 Stichnoth | e4f65d8 | 2015-06-17 22:16:02 -0700 | [diff] [blame] | 478 | 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 Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 482 | FirstInstNum = Inst::NumberExtended; |
Jim Stichnoth | e4f65d8 | 2015-06-17 22:16:02 -0700 | [diff] [blame] | 483 | } |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 484 | Node->livenessAddIntervals(getLiveness(), FirstInstNum, LastInstNum); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 485 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 486 | } |
| 487 | } |
| 488 | |
| 489 | // Traverse every Variable of every Inst and verify that it |
| 490 | // appears within the Variable's computed live range. |
| 491 | bool Cfg::validateLiveness() const { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 492 | TimerMarker T(TimerStack::TT_validateLiveness, this); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 493 | bool Valid = true; |
Jim Stichnoth | e4a8f40 | 2015-01-20 12:52:51 -0800 | [diff] [blame] | 494 | OstreamLocker L(Ctx); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 495 | Ostream &Str = Ctx->getStrDump(); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 496 | for (CfgNode *Node : Nodes) { |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 497 | Inst *FirstInst = nullptr; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 498 | for (Inst &Inst : Node->getInsts()) { |
| 499 | if (Inst.isDeleted()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 500 | continue; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 501 | if (FirstInst == nullptr) |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 502 | FirstInst = &Inst; |
| 503 | InstNumberT InstNumber = Inst.getNumber(); |
| 504 | if (Variable *Dest = Inst.getDest()) { |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 505 | 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 Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 517 | if (static_cast<class Inst *>(&Inst) != FirstInst && |
| 518 | !Inst.isDestNonKillable() && |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 519 | Dest->getLiveRange().containsValue(InstNumber - 1, IsDest)) |
| 520 | Invalid = true; |
| 521 | if (Invalid) { |
| 522 | Valid = false; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 523 | Str << "Liveness error: inst " << Inst.getNumber() << " dest "; |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 524 | Dest->dump(this); |
| 525 | Str << " live range " << Dest->getLiveRange() << "\n"; |
| 526 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 527 | } |
| 528 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 529 | for (SizeT I = 0; I < Inst.getSrcSize(); ++I) { |
| 530 | Operand *Src = Inst.getSrc(I); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 531 | SizeT NumVars = Src->getNumVars(); |
| 532 | for (SizeT J = 0; J < NumVars; ++J) { |
| 533 | const Variable *Var = Src->getVar(J); |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 534 | const bool IsDest = false; |
| 535 | if (!Var->getIgnoreLiveness() && |
| 536 | !Var->getLiveRange().containsValue(InstNumber, IsDest)) { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 537 | Valid = false; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 538 | Str << "Liveness error: inst " << Inst.getNumber() << " var "; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 539 | Var->dump(this); |
| 540 | Str << " live range " << Var->getLiveRange() << "\n"; |
| 541 | } |
| 542 | } |
| 543 | } |
| 544 | } |
| 545 | } |
| 546 | return Valid; |
| 547 | } |
| 548 | |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 549 | void Cfg::contractEmptyNodes() { |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 550 | // 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 Schimpf | df80eb8 | 2015-02-09 14:20:22 -0800 | [diff] [blame] | 556 | if (Ctx->getFlags().getDecorateAsm()) |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 557 | return; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 558 | for (CfgNode *Node : Nodes) { |
| 559 | Node->contractIfEmpty(); |
| 560 | } |
| 561 | } |
| 562 | |
Jim Stichnoth | ff9c706 | 2014-09-18 04:50:49 -0700 | [diff] [blame] | 563 | void Cfg::doBranchOpt() { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 564 | TimerMarker T(TimerStack::TT_doBranchOpt, this); |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 565 | for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) { |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 566 | auto NextNode = I + 1; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 567 | (*I)->doBranchOpt(NextNode == E ? nullptr : *NextNode); |
Jim Stichnoth | ff9c706 | 2014-09-18 04:50:49 -0700 | [diff] [blame] | 568 | } |
| 569 | } |
| 570 | |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame^] | 571 | void 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 Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 577 | // ======================== Dump routines ======================== // |
| 578 | |
Jim Stichnoth | bbca754 | 2015-02-11 16:08:31 -0800 | [diff] [blame] | 579 | // 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. |
| 582 | void Cfg::emitTextHeader(const IceString &MangledName, GlobalContext *Ctx, |
| 583 | const Assembler *Asm) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 584 | if (!BuildDefs::dump()) |
Jim Stichnoth | 729dbd0 | 2015-02-25 14:48:43 -0800 | [diff] [blame] | 585 | return; |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 586 | Ostream &Str = Ctx->getStrEmit(); |
| 587 | Str << "\t.text\n"; |
Karl Schimpf | df80eb8 | 2015-02-09 14:20:22 -0800 | [diff] [blame] | 588 | if (Ctx->getFlags().getFunctionSections()) |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 589 | Str << "\t.section\t.text." << MangledName << ",\"ax\",@progbits\n"; |
Jim Stichnoth | bbca754 | 2015-02-11 16:08:31 -0800 | [diff] [blame] | 590 | if (!Asm->getInternal() || Ctx->getFlags().getDisableInternal()) { |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 591 | Str << "\t.globl\t" << MangledName << "\n"; |
Jan Voung | b2d5084 | 2015-05-12 09:53:50 -0700 | [diff] [blame] | 592 | Str << "\t.type\t" << MangledName << ",%function\n"; |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 593 | } |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame^] | 594 | Str << "\t" << Asm->getAlignDirective() << " " |
Jan Voung | b2d5084 | 2015-05-12 09:53:50 -0700 | [diff] [blame] | 595 | << Asm->getBundleAlignLog2Bytes() << ",0x"; |
Jan Voung | 08c3bcd | 2014-12-01 17:55:16 -0800 | [diff] [blame] | 596 | for (uint8_t I : Asm->getNonExecBundlePadding()) |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 597 | Str.write_hex(I); |
| 598 | Str << "\n"; |
| 599 | Str << MangledName << ":\n"; |
| 600 | } |
| 601 | |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame^] | 602 | void Cfg::deleteJumpTableInsts() { |
| 603 | for (InstJumpTable *JumpTable : JumpTables) |
| 604 | JumpTable->setDeleted(); |
| 605 | } |
| 606 | |
| 607 | void 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 Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 636 | void Cfg::emit() { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 637 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 638 | return; |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 639 | TimerMarker T(TimerStack::TT_emit, this); |
Karl Schimpf | df80eb8 | 2015-02-09 14:20:22 -0800 | [diff] [blame] | 640 | if (Ctx->getFlags().getDecorateAsm()) { |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 641 | renumberInstructions(); |
| 642 | getVMetadata()->init(VMK_Uses); |
| 643 | liveness(Liveness_Basic); |
| 644 | dump("After recomputing liveness for -decorate-asm"); |
| 645 | } |
Jim Stichnoth | e4a8f40 | 2015-01-20 12:52:51 -0800 | [diff] [blame] | 646 | OstreamLocker L(Ctx); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 647 | Ostream &Str = Ctx->getStrEmit(); |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame^] | 648 | 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 Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 659 | Node->emit(this); |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame^] | 660 | } |
| 661 | emitJumpTables(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 662 | Str << "\n"; |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 663 | } |
| 664 | |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 665 | void Cfg::emitIAS() { |
| 666 | TimerMarker T(TimerStack::TT_emit, this); |
Jim Stichnoth | e4a8f40 | 2015-01-20 12:52:51 -0800 | [diff] [blame] | 667 | // The emitIAS() routines emit into the internal assembler buffer, |
Jim Stichnoth | bbca754 | 2015-02-11 16:08:31 -0800 | [diff] [blame] | 668 | // so there's no need to lock the streams. |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame^] | 669 | deleteJumpTableInsts(); |
| 670 | const bool NeedSandboxing = Ctx->getFlags().getUseSandboxing(); |
| 671 | for (CfgNode *Node : Nodes) { |
| 672 | if (NeedSandboxing && Node->needsAlignment()) |
| 673 | getAssembler()->alignCfgNode(); |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 674 | Node->emitIAS(this); |
Andrew Scull | 86df4e9 | 2015-07-30 13:54:44 -0700 | [diff] [blame^] | 675 | } |
| 676 | emitJumpTables(); |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 677 | } |
| 678 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 679 | // Dumps the IR with an optional introductory message. |
| 680 | void Cfg::dump(const IceString &Message) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 681 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 682 | return; |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 683 | if (!isVerbose()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 684 | return; |
Jim Stichnoth | e4a8f40 | 2015-01-20 12:52:51 -0800 | [diff] [blame] | 685 | OstreamLocker L(Ctx); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 686 | Ostream &Str = Ctx->getStrDump(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 687 | if (!Message.empty()) |
| 688 | Str << "================ " << Message << " ================\n"; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 689 | setCurrentNode(getEntryNode()); |
| 690 | // Print function name+args |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 691 | if (isVerbose(IceV_Instructions)) { |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 692 | Str << "define "; |
Karl Schimpf | df80eb8 | 2015-02-09 14:20:22 -0800 | [diff] [blame] | 693 | if (getInternal() && !Ctx->getFlags().getDisableInternal()) |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 694 | Str << "internal "; |
Karl Schimpf | df6f9d1 | 2014-10-20 14:09:00 -0700 | [diff] [blame] | 695 | Str << ReturnType << " @" << Ctx->mangleName(getFunctionName()) << "("; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 696 | 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 Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 704 | resetCurrentNode(); |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 705 | if (isVerbose(IceV_Liveness)) { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 706 | // Print summary info about variables |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 707 | for (Variable *Var : Variables) { |
Jim Stichnoth | 144cdce | 2014-09-22 16:02:59 -0700 | [diff] [blame] | 708 | Str << "// multiblock="; |
| 709 | if (getVMetadata()->isTracked(Var)) |
| 710 | Str << getVMetadata()->isMultiBlock(Var); |
| 711 | else |
| 712 | Str << "?"; |
| 713 | Str << " weight=" << Var->getWeight() << " "; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 714 | Var->dump(this); |
| 715 | Str << " LIVE=" << Var->getLiveRange() << "\n"; |
| 716 | } |
| 717 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 718 | // Print each basic block |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 719 | for (CfgNode *Node : Nodes) |
| 720 | Node->dump(this); |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 721 | if (isVerbose(IceV_Instructions)) |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 722 | Str << "}\n"; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 723 | } |
| 724 | |
| 725 | } // end of namespace Ice |