OLD | NEW |
1 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===// | 1 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 // | 9 // |
10 // This file implements the CfgNode class, including the complexities | 10 // This file implements the CfgNode class, including the complexities |
11 // of instruction insertion and in-edge calculation. | 11 // of instruction insertion and in-edge calculation. |
12 // | 12 // |
13 //===----------------------------------------------------------------------===// | 13 //===----------------------------------------------------------------------===// |
14 | 14 |
15 #include "assembler.h" | 15 #include "assembler.h" |
16 #include "IceCfg.h" | 16 #include "IceCfg.h" |
17 #include "IceCfgNode.h" | 17 #include "IceCfgNode.h" |
18 #include "IceInst.h" | 18 #include "IceInst.h" |
19 #include "IceLiveness.h" | 19 #include "IceLiveness.h" |
20 #include "IceOperand.h" | 20 #include "IceOperand.h" |
21 #include "IceTargetLowering.h" | 21 #include "IceTargetLowering.h" |
22 | 22 |
23 namespace Ice { | 23 namespace Ice { |
24 | 24 |
25 CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name) | 25 CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name) |
26 : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false), | 26 : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false), |
27 InstCountEstimate(0) {} | 27 NeedsPlacement(false), InstCountEstimate(0) {} |
28 | 28 |
29 // Returns the name the node was created with. If no name was given, | 29 // Returns the name the node was created with. If no name was given, |
30 // it synthesizes a (hopefully) unique name. | 30 // it synthesizes a (hopefully) unique name. |
31 IceString CfgNode::getName() const { | 31 IceString CfgNode::getName() const { |
32 if (!Name.empty()) | 32 if (!Name.empty()) |
33 return Name; | 33 return Name; |
34 return "__" + std::to_string(getIndex()); | 34 return "__" + std::to_string(getIndex()); |
35 } | 35 } |
36 | 36 |
37 // Adds an instruction to either the Phi list or the regular | 37 // Adds an instruction to either the Phi list or the regular |
(...skipping 159 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
197 } | 197 } |
198 } | 198 } |
199 } | 199 } |
200 | 200 |
201 // Deletes the phi instructions after the loads and stores are placed. | 201 // Deletes the phi instructions after the loads and stores are placed. |
202 void CfgNode::deletePhis() { | 202 void CfgNode::deletePhis() { |
203 for (InstPhi *I : Phis) | 203 for (InstPhi *I : Phis) |
204 I->setDeleted(); | 204 I->setDeleted(); |
205 } | 205 } |
206 | 206 |
| 207 // Splits the edge from Pred to this node by creating a new node and |
| 208 // hooking up the in and out edges appropriately. (The EdgeIndex |
| 209 // parameter is only used to make the new node's name unique when |
| 210 // there are multiple edges between the same pair of nodes.) The new |
| 211 // node's instruction list is initialized to the empty list, with no |
| 212 // terminator instruction. If there are multiple edges from Pred to |
| 213 // this node, only one edge is split, and the particular choice of |
| 214 // edge is undefined. This could happen with a switch instruction, or |
| 215 // a conditional branch that weirdly has both branches to the same |
| 216 // place. TODO(stichnot,kschimpf): Figure out whether this is legal |
| 217 // in the LLVM IR or the PNaCl bitcode, and if so, we need to |
| 218 // establish a strong relationship among the ordering of Pred's |
| 219 // out-edge list, this node's in-edge list, and the Phi instruction's |
| 220 // operand list. |
| 221 CfgNode *CfgNode::splitIncomingEdge(CfgNode *Pred, SizeT EdgeIndex) { |
| 222 CfgNode *NewNode = |
| 223 Func->makeNode("split_" + Pred->getName() + "_" + getName() + "_" + |
| 224 std::to_string(EdgeIndex)); |
| 225 // The new node is added to the end of the node list, and will later |
| 226 // need to be sorted into a reasonable topological order. |
| 227 NewNode->setNeedsPlacement(true); |
| 228 // Repoint Pred's out-edge. |
| 229 bool Found = false; |
| 230 for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end(); |
| 231 !Found && I != E; ++I) { |
| 232 if (*I == this) { |
| 233 *I = NewNode; |
| 234 NewNode->InEdges.push_back(Pred); |
| 235 Found = true; |
| 236 } |
| 237 } |
| 238 assert(Found); |
| 239 // Repoint this node's in-edge. |
| 240 Found = false; |
| 241 for (auto I = InEdges.begin(), E = InEdges.end(); !Found && I != E; ++I) { |
| 242 if (*I == Pred) { |
| 243 *I = NewNode; |
| 244 NewNode->OutEdges.push_back(this); |
| 245 Found = true; |
| 246 } |
| 247 } |
| 248 assert(Found); |
| 249 // Repoint a suitable branch instruction's target. |
| 250 Found = false; |
| 251 for (auto I = Pred->getInsts().rbegin(), E = Pred->getInsts().rend(); |
| 252 !Found && I != E; ++I) { |
| 253 if (!(*I)->isDeleted()) { |
| 254 Found = (*I)->repointEdge(this, NewNode); |
| 255 } |
| 256 } |
| 257 assert(Found); |
| 258 return NewNode; |
| 259 } |
| 260 |
| 261 namespace { |
| 262 |
| 263 // Helper function used by advancedPhiLowering(). |
| 264 bool sameVarOrReg(const Variable *Var, const Operand *Opnd) { |
| 265 if (Var == Opnd) |
| 266 return true; |
| 267 if (const auto Var2 = llvm::dyn_cast<Variable>(Opnd)) { |
| 268 if (Var->hasReg() && Var->getRegNum() == Var2->getRegNum()) |
| 269 return true; |
| 270 } |
| 271 return false; |
| 272 } |
| 273 |
| 274 } // end of anonymous namespace |
| 275 |
| 276 // This the "advanced" version of Phi lowering for a basic block, in |
| 277 // contrast to the simple version that lowers through assignments |
| 278 // involving temporaries. |
| 279 // |
| 280 // All Phi instructions in a basic block are conceptually executed in |
| 281 // parallel. However, if we lower Phis early and commit to a |
| 282 // sequential ordering, we may end up creating unnecessary |
| 283 // interferences which lead to worse register allocation. Delaying |
| 284 // Phi scheduling until after register allocation can help unless |
| 285 // there are no free registers for shuffling registers or stack slots |
| 286 // and spilling becomes necessary. |
| 287 // |
| 288 // The advanced Phi lowering starts by finding a topological sort of |
| 289 // the Phi instructions, where "A=B" comes before "B=C" due to the |
| 290 // anti-dependence on B. If a topological sort is not possible due to |
| 291 // a cycle, the cycle is broken by introducing a non-parallel |
| 292 // temporary. For example, a cycle arising from a permutation like |
| 293 // "A=B;B=C;C=A" can become "T=A;A=B;B=C;C=T". All else being equal, |
| 294 // prefer to schedule assignments with register-allocated Src operands |
| 295 // earlier, in case that register becomes free afterwards, and prefer |
| 296 // to schedule assignments with register-allocated Dest variables |
| 297 // later, to keep that register free for longer. |
| 298 // |
| 299 // Once the ordering is determined, the Cfg edge is split and the |
| 300 // assignment list is lowered by the target lowering layer. The |
| 301 // specific placement of the new node within the Cfg node list is |
| 302 // deferred until later, including after empty node contraction. |
| 303 void CfgNode::advancedPhiLowering() { |
| 304 if (getPhis().empty()) |
| 305 return; |
| 306 |
| 307 // Count the number of non-deleted Phi instructions. |
| 308 struct { |
| 309 InstPhi *Phi; |
| 310 Variable *Dest; |
| 311 Operand *Src; |
| 312 bool Processed; |
| 313 size_t NumPred; // number of entries whose Src is this Dest |
| 314 int32_t Weight; // preference for topological order |
| 315 } Desc[getPhis().size()]; |
| 316 |
| 317 size_t NumPhis = 0; |
| 318 for (InstPhi *Inst : getPhis()) { |
| 319 if (!Inst->isDeleted()) { |
| 320 Desc[NumPhis].Phi = Inst; |
| 321 Desc[NumPhis].Dest = Inst->getDest(); |
| 322 ++NumPhis; |
| 323 } |
| 324 } |
| 325 if (NumPhis == 0) |
| 326 return; |
| 327 |
| 328 SizeT InEdgeIndex = 0; |
| 329 for (CfgNode *Pred : InEdges) { |
| 330 CfgNode *Split = splitIncomingEdge(Pred, InEdgeIndex++); |
| 331 AssignList Assignments; |
| 332 SizeT Remaining = NumPhis; |
| 333 |
| 334 // First pass computes Src and initializes NumPred. |
| 335 for (size_t I = 0; I < NumPhis; ++I) { |
| 336 Variable *Dest = Desc[I].Dest; |
| 337 Operand *Src = Desc[I].Phi->getOperandForTarget(Pred); |
| 338 Desc[I].Src = Src; |
| 339 Desc[I].Processed = false; |
| 340 Desc[I].NumPred = 0; |
| 341 // Cherry-pick any trivial assignments, so that they don't |
| 342 // contribute to the running complexity of the topological sort. |
| 343 if (sameVarOrReg(Dest, Src)) { |
| 344 Desc[I].Processed = true; |
| 345 --Remaining; |
| 346 if (Dest != Src) |
| 347 // If Dest and Src are syntactically the same, don't bother |
| 348 // adding the assignment, because in all respects it would |
| 349 // be redundant, and if Dest/Src are on the stack, the |
| 350 // target lowering may naively decide to lower it using a |
| 351 // temporary register. |
| 352 Assignments.push_back(InstAssign::create(Func, Dest, Src)); |
| 353 } |
| 354 } |
| 355 // Second pass computes NumPred by comparing every pair of Phi |
| 356 // instructions. |
| 357 for (size_t I = 0; I < NumPhis; ++I) { |
| 358 if (Desc[I].Processed) |
| 359 continue; |
| 360 const Variable *Dest = Desc[I].Dest; |
| 361 for (size_t J = 0; J < NumPhis; ++J) { |
| 362 if (Desc[J].Processed) |
| 363 continue; |
| 364 if (I != J) { |
| 365 // There shouldn't be two Phis with the same Dest variable |
| 366 // or register. |
| 367 assert(!sameVarOrReg(Dest, Desc[J].Dest)); |
| 368 } |
| 369 const Operand *Src = Desc[J].Src; |
| 370 if (sameVarOrReg(Dest, Src)) |
| 371 ++Desc[I].NumPred; |
| 372 } |
| 373 } |
| 374 |
| 375 // Another pass to compute initial Weight values. |
| 376 |
| 377 // Always pick NumPred=0 over NumPred>0. |
| 378 const int32_t WeightNoPreds = 4; |
| 379 // Prefer Src as a register because the register might free up. |
| 380 const int32_t WeightSrcIsReg = 2; |
| 381 // Prefer Dest not as a register because the register stays free |
| 382 // longer. |
| 383 const int32_t WeightDestNotReg = 1; |
| 384 |
| 385 for (size_t I = 0; I < NumPhis; ++I) { |
| 386 if (Desc[I].Processed) |
| 387 continue; |
| 388 int32_t Weight = 0; |
| 389 if (Desc[I].NumPred == 0) |
| 390 Weight += WeightNoPreds; |
| 391 if (auto Var = llvm::dyn_cast<Variable>(Desc[I].Src)) |
| 392 if (Var->hasReg()) |
| 393 Weight += WeightSrcIsReg; |
| 394 if (!Desc[I].Dest->hasReg()) |
| 395 Weight += WeightDestNotReg; |
| 396 Desc[I].Weight = Weight; |
| 397 } |
| 398 |
| 399 // Repeatedly choose and process the best candidate in the |
| 400 // topological sort, until no candidates remain. This |
| 401 // implementation is O(N^2) where N is the number of Phi |
| 402 // instructions, but with a small constant factor compared to a |
| 403 // likely implementation of O(N) topological sort. |
| 404 for (; Remaining; --Remaining) { |
| 405 size_t BestIndex = 0; |
| 406 int32_t BestWeight = -1; |
| 407 // Find the best candidate. |
| 408 for (size_t I = 0; I < NumPhis; ++I) { |
| 409 if (Desc[I].Processed) |
| 410 continue; |
| 411 int32_t Weight = 0; |
| 412 Weight = Desc[I].Weight; |
| 413 if (Weight > BestWeight) { |
| 414 BestIndex = I; |
| 415 BestWeight = Weight; |
| 416 } |
| 417 } |
| 418 assert(BestWeight >= 0); |
| 419 assert(Desc[BestIndex].NumPred <= 1); |
| 420 Variable *Dest = Desc[BestIndex].Dest; |
| 421 Operand *Src = Desc[BestIndex].Src; |
| 422 assert(!sameVarOrReg(Dest, Src)); |
| 423 // Break a cycle by introducing a temporary. |
| 424 if (Desc[BestIndex].NumPred) { |
| 425 bool Found = false; |
| 426 // If the target instruction "A=B" is part of a cycle, find |
| 427 // the "X=A" assignment in the cycle because it will have to |
| 428 // be rewritten as "X=tmp". |
| 429 for (size_t J = 0; !Found && J < NumPhis; ++J) { |
| 430 if (Desc[J].Processed) |
| 431 continue; |
| 432 Operand *OtherSrc = Desc[J].Src; |
| 433 if (Desc[J].NumPred && sameVarOrReg(Dest, OtherSrc)) { |
| 434 SizeT VarNum = Func->getNumVariables(); |
| 435 Variable *Tmp = Func->makeVariable( |
| 436 OtherSrc->getType(), "__split_" + std::to_string(VarNum)); |
| 437 Tmp->setNeedsStackSlot(); |
| 438 Assignments.push_back(InstAssign::create(Func, Tmp, OtherSrc)); |
| 439 Desc[J].Src = Tmp; |
| 440 Found = true; |
| 441 } |
| 442 } |
| 443 assert(Found); |
| 444 } |
| 445 // Now that a cycle (if any) has been broken, create the actual |
| 446 // assignment. |
| 447 Assignments.push_back(InstAssign::create(Func, Dest, Src)); |
| 448 // Update NumPred for all Phi assignments using this Phi's Src |
| 449 // as their Dest variable. Also update Weight if NumPred |
| 450 // dropped from 1 to 0. |
| 451 if (auto Var = llvm::dyn_cast<Variable>(Src)) { |
| 452 for (size_t I = 0; I < NumPhis; ++I) { |
| 453 if (Desc[I].Processed) |
| 454 continue; |
| 455 if (sameVarOrReg(Var, Desc[I].Dest)) { |
| 456 if (--Desc[I].NumPred == 0) |
| 457 Desc[I].Weight += WeightNoPreds; |
| 458 } |
| 459 } |
| 460 } |
| 461 Desc[BestIndex].Processed = true; |
| 462 } |
| 463 |
| 464 Func->getTarget()->lowerPhiAssignments(Split, Assignments); |
| 465 |
| 466 // Renumber the instructions to be monotonically increasing so |
| 467 // that addNode() doesn't assert when multi-definitions are added |
| 468 // out of order. |
| 469 Split->renumberInstructions(); |
| 470 Func->getVMetadata()->addNode(Split); |
| 471 } |
| 472 |
| 473 for (InstPhi *Inst : getPhis()) |
| 474 Inst->setDeleted(); |
| 475 } |
| 476 |
207 // Does address mode optimization. Pass each instruction to the | 477 // Does address mode optimization. Pass each instruction to the |
208 // TargetLowering object. If it returns a new instruction | 478 // TargetLowering object. If it returns a new instruction |
209 // (representing the optimized address mode), then insert the new | 479 // (representing the optimized address mode), then insert the new |
210 // instruction and delete the old. | 480 // instruction and delete the old. |
211 void CfgNode::doAddressOpt() { | 481 void CfgNode::doAddressOpt() { |
212 TargetLowering *Target = Func->getTarget(); | 482 TargetLowering *Target = Func->getTarget(); |
213 LoweringContext &Context = Target->getContext(); | 483 LoweringContext &Context = Target->getContext(); |
214 Context.init(this); | 484 Context.init(this); |
215 while (!Context.atEnd()) { | 485 while (!Context.atEnd()) { |
216 Target->doAddressOpt(); | 486 Target->doAddressOpt(); |
(...skipping 16 matching lines...) Expand all Loading... |
233 Context.advanceNext(); | 503 Context.advanceNext(); |
234 Context.advanceCur(); | 504 Context.advanceCur(); |
235 Target->doNopInsertion(); | 505 Target->doNopInsertion(); |
236 } | 506 } |
237 | 507 |
238 // Drives the target lowering. Passes the current instruction and the | 508 // Drives the target lowering. Passes the current instruction and the |
239 // next non-deleted instruction for target lowering. | 509 // next non-deleted instruction for target lowering. |
240 void CfgNode::genCode() { | 510 void CfgNode::genCode() { |
241 TargetLowering *Target = Func->getTarget(); | 511 TargetLowering *Target = Func->getTarget(); |
242 LoweringContext &Context = Target->getContext(); | 512 LoweringContext &Context = Target->getContext(); |
243 // Lower only the regular instructions. Defer the Phi instructions. | 513 // Lower the regular instructions. |
244 Context.init(this); | 514 Context.init(this); |
245 while (!Context.atEnd()) { | 515 while (!Context.atEnd()) { |
246 InstList::iterator Orig = Context.getCur(); | 516 InstList::iterator Orig = Context.getCur(); |
247 if (llvm::isa<InstRet>(*Orig)) | 517 if (llvm::isa<InstRet>(*Orig)) |
248 setHasReturn(); | 518 setHasReturn(); |
249 Target->lower(); | 519 Target->lower(); |
250 // Ensure target lowering actually moved the cursor. | 520 // Ensure target lowering actually moved the cursor. |
251 assert(Context.getCur() != Orig); | 521 assert(Context.getCur() != Orig); |
252 } | 522 } |
| 523 // Do preliminary lowering of the Phi instructions. |
| 524 Target->prelowerPhis(); |
253 } | 525 } |
254 | 526 |
255 void CfgNode::livenessLightweight() { | 527 void CfgNode::livenessLightweight() { |
256 SizeT NumVars = Func->getNumVariables(); | 528 SizeT NumVars = Func->getNumVariables(); |
257 LivenessBV Live(NumVars); | 529 LivenessBV Live(NumVars); |
258 // Process regular instructions in reverse order. | 530 // Process regular instructions in reverse order. |
259 // TODO(stichnot): Use llvm::make_range with LLVM 3.5. | 531 // TODO(stichnot): Use llvm::make_range with LLVM 3.5. |
260 for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) { | 532 for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) { |
261 if ((*I)->isDeleted()) | 533 if ((*I)->isDeleted()) |
262 continue; | 534 continue; |
(...skipping 30 matching lines...) Expand all Loading... |
293 // Initialize Live to be the union of all successors' LiveIn. | 565 // Initialize Live to be the union of all successors' LiveIn. |
294 for (CfgNode *Succ : OutEdges) { | 566 for (CfgNode *Succ : OutEdges) { |
295 Live |= Liveness->getLiveIn(Succ); | 567 Live |= Liveness->getLiveIn(Succ); |
296 // Mark corresponding argument of phis in successor as live. | 568 // Mark corresponding argument of phis in successor as live. |
297 for (InstPhi *I : Succ->Phis) | 569 for (InstPhi *I : Succ->Phis) |
298 I->livenessPhiOperand(Live, this, Liveness); | 570 I->livenessPhiOperand(Live, this, Liveness); |
299 } | 571 } |
300 Liveness->getLiveOut(this) = Live; | 572 Liveness->getLiveOut(this) = Live; |
301 | 573 |
302 // Process regular instructions in reverse order. | 574 // Process regular instructions in reverse order. |
303 // TODO(stichnot): Use llvm::make_range with LLVM 3.5. | |
304 for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) { | 575 for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) { |
305 if ((*I)->isDeleted()) | 576 if ((*I)->isDeleted()) |
306 continue; | 577 continue; |
307 (*I)->liveness((*I)->getNumber(), Live, Liveness, LiveBegin, LiveEnd); | 578 (*I)->liveness((*I)->getNumber(), Live, Liveness, LiveBegin, LiveEnd); |
308 } | 579 } |
309 // Process phis in forward order so that we can override the | 580 // Process phis in forward order so that we can override the |
310 // instruction number to be that of the earliest phi instruction in | 581 // instruction number to be that of the earliest phi instruction in |
311 // the block. | 582 // the block. |
| 583 SizeT NumNonDeadPhis = 0; |
312 InstNumberT FirstPhiNumber = Inst::NumberSentinel; | 584 InstNumberT FirstPhiNumber = Inst::NumberSentinel; |
313 for (InstPhi *I : Phis) { | 585 for (InstPhi *I : Phis) { |
314 if (I->isDeleted()) | 586 if (I->isDeleted()) |
315 continue; | 587 continue; |
316 if (FirstPhiNumber == Inst::NumberSentinel) | 588 if (FirstPhiNumber == Inst::NumberSentinel) |
317 FirstPhiNumber = I->getNumber(); | 589 FirstPhiNumber = I->getNumber(); |
318 I->liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd); | 590 if (I->liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd)) |
| 591 ++NumNonDeadPhis; |
319 } | 592 } |
320 | 593 |
321 // When using the sparse representation, after traversing the | 594 // When using the sparse representation, after traversing the |
322 // instructions in the block, the Live bitvector should only contain | 595 // instructions in the block, the Live bitvector should only contain |
323 // set bits for global variables upon block entry. We validate this | 596 // set bits for global variables upon block entry. We validate this |
324 // by shrinking the Live vector and then testing it against the | 597 // by shrinking the Live vector and then testing it against the |
325 // pre-shrunk version. (The shrinking is required, but the | 598 // pre-shrunk version. (The shrinking is required, but the |
326 // validation is not.) | 599 // validation is not.) |
327 LivenessBV LiveOrig = Live; | 600 LivenessBV LiveOrig = Live; |
328 Live.resize(Liveness->getNumGlobalVars()); | 601 Live.resize(Liveness->getNumGlobalVars()); |
(...skipping 14 matching lines...) Expand all Loading... |
343 } | 616 } |
344 Str << "\n"; | 617 Str << "\n"; |
345 llvm_unreachable("Fatal inconsistency in liveness analysis"); | 618 llvm_unreachable("Fatal inconsistency in liveness analysis"); |
346 } | 619 } |
347 | 620 |
348 bool Changed = false; | 621 bool Changed = false; |
349 LivenessBV &LiveIn = Liveness->getLiveIn(this); | 622 LivenessBV &LiveIn = Liveness->getLiveIn(this); |
350 // Add in current LiveIn | 623 // Add in current LiveIn |
351 Live |= LiveIn; | 624 Live |= LiveIn; |
352 // Check result, set LiveIn=Live | 625 // Check result, set LiveIn=Live |
353 Changed = (Live != LiveIn); | 626 SizeT &PrevNumNonDeadPhis = Liveness->getNumNonDeadPhis(this); |
354 if (Changed) | 627 bool LiveInChanged = (Live != LiveIn); |
| 628 Changed = (NumNonDeadPhis != PrevNumNonDeadPhis || LiveInChanged); |
| 629 if (LiveInChanged) |
355 LiveIn = Live; | 630 LiveIn = Live; |
| 631 PrevNumNonDeadPhis = NumNonDeadPhis; |
356 return Changed; | 632 return Changed; |
357 } | 633 } |
358 | 634 |
359 // Now that basic liveness is complete, remove dead instructions that | 635 // Now that basic liveness is complete, remove dead instructions that |
360 // were tentatively marked as dead, and compute actual live ranges. | 636 // were tentatively marked as dead, and compute actual live ranges. |
361 // It is assumed that within a single basic block, a live range begins | 637 // It is assumed that within a single basic block, a live range begins |
362 // at most once and ends at most once. This is certainly true for | 638 // at most once and ends at most once. This is certainly true for |
363 // pure SSA form. It is also true once phis are lowered, since each | 639 // pure SSA form. It is also true once phis are lowered, since each |
364 // assignment to the phi-based temporary is in a different basic | 640 // assignment to the phi-based temporary is in a different basic |
365 // block, and there is a single read that ends the live in the basic | 641 // block, and there is a single read that ends the live in the basic |
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
465 ++IEB; | 741 ++IEB; |
466 } | 742 } |
467 // Process the variables that are live across the entire block. | 743 // Process the variables that are live across the entire block. |
468 for (int i = LiveInAndOut.find_first(); i != -1; | 744 for (int i = LiveInAndOut.find_first(); i != -1; |
469 i = LiveInAndOut.find_next(i)) { | 745 i = LiveInAndOut.find_next(i)) { |
470 Variable *Var = Liveness->getVariable(i, this); | 746 Variable *Var = Liveness->getVariable(i, this); |
471 Var->addLiveRange(FirstInstNum, LastInstNum + 1, 1); | 747 Var->addLiveRange(FirstInstNum, LastInstNum + 1, 1); |
472 } | 748 } |
473 } | 749 } |
474 | 750 |
| 751 // If this node contains only deleted instructions, and ends in an |
| 752 // unconditional branch, contract the node by repointing all its |
| 753 // in-edges to its successor. |
| 754 void CfgNode::contractIfEmpty() { |
| 755 if (InEdges.size() == 0) |
| 756 return; |
| 757 Inst *Branch = NULL; |
| 758 for (Inst *I : Insts) { |
| 759 if (!I->isDeleted() && !I->isUnconditionalBranch()) |
| 760 return; |
| 761 Branch = I; |
| 762 } |
| 763 Branch->setDeleted(); |
| 764 assert(OutEdges.size() == 1); |
| 765 // Repoint all this node's in-edges to this node's successor. |
| 766 for (CfgNode *Pred : InEdges) { |
| 767 for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end(); I != E; |
| 768 ++I) { |
| 769 if (*I == this) { |
| 770 *I = OutEdges[0]; |
| 771 OutEdges[0]->InEdges.push_back(Pred); |
| 772 } |
| 773 } |
| 774 for (Inst *I : Pred->getInsts()) { |
| 775 if (!I->isDeleted()) |
| 776 I->repointEdge(this, OutEdges[0]); |
| 777 } |
| 778 } |
| 779 InEdges.clear(); |
| 780 // Don't bother removing the single out-edge, which would also |
| 781 // require finding the corresponding in-edge in the successor and |
| 782 // removing it. |
| 783 } |
| 784 |
475 void CfgNode::doBranchOpt(const CfgNode *NextNode) { | 785 void CfgNode::doBranchOpt(const CfgNode *NextNode) { |
476 TargetLowering *Target = Func->getTarget(); | 786 TargetLowering *Target = Func->getTarget(); |
477 // Check every instruction for a branch optimization opportunity. | 787 // Check every instruction for a branch optimization opportunity. |
478 // It may be more efficient to iterate in reverse and stop after the | 788 // It may be more efficient to iterate in reverse and stop after the |
479 // first opportunity, unless there is some target lowering where we | 789 // first opportunity, unless there is some target lowering where we |
480 // have the possibility of multiple such optimizations per block | 790 // have the possibility of multiple such optimizations per block |
481 // (currently not the case for x86 lowering). | 791 // (currently not the case for x86 lowering). |
482 for (Inst *I : Insts) | 792 for (Inst *I : Insts) { |
483 Target->doBranchOpt(I, NextNode); | 793 if (!I->isDeleted()) { |
| 794 Target->doBranchOpt(I, NextNode); |
| 795 } |
| 796 } |
484 } | 797 } |
485 | 798 |
486 // ======================== Dump routines ======================== // | 799 // ======================== Dump routines ======================== // |
487 | 800 |
488 void CfgNode::emit(Cfg *Func) const { | 801 void CfgNode::emit(Cfg *Func) const { |
489 Func->setCurrentNode(this); | 802 Func->setCurrentNode(this); |
490 Ostream &Str = Func->getContext()->getStrEmit(); | 803 Ostream &Str = Func->getContext()->getStrEmit(); |
491 if (Func->getEntryNode() == this) { | 804 if (Func->getEntryNode() == this) { |
492 Str << Func->getContext()->mangleName(Func->getFunctionName()) << ":\n"; | 805 Str << Func->getContext()->mangleName(Func->getFunctionName()) << ":\n"; |
493 } | 806 } |
(...skipping 106 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
600 if (!First) | 913 if (!First) |
601 Str << ", "; | 914 Str << ", "; |
602 First = false; | 915 First = false; |
603 Str << "%" << I->getName(); | 916 Str << "%" << I->getName(); |
604 } | 917 } |
605 Str << "\n"; | 918 Str << "\n"; |
606 } | 919 } |
607 } | 920 } |
608 | 921 |
609 } // end of namespace Ice | 922 } // end of namespace Ice |
OLD | NEW |