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 |
(...skipping 339 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
350 LivenessBV &LiveIn = Liveness->getLiveIn(this); | 350 LivenessBV &LiveIn = Liveness->getLiveIn(this); |
351 // Add in current LiveIn | 351 // Add in current LiveIn |
352 Live |= LiveIn; | 352 Live |= LiveIn; |
353 // Check result, set LiveIn=Live | 353 // Check result, set LiveIn=Live |
354 Changed = (Live != LiveIn); | 354 Changed = (Live != LiveIn); |
355 if (Changed) | 355 if (Changed) |
356 LiveIn = Live; | 356 LiveIn = Live; |
357 return Changed; | 357 return Changed; |
358 } | 358 } |
359 | 359 |
360 #ifndef NDEBUG | |
361 namespace { | |
362 | |
363 bool comparePair(const LiveBeginEndMapEntry &A, const LiveBeginEndMapEntry &B) { | |
364 return A.first == B.first; | |
365 } | |
366 | |
367 } // end of anonymous namespace | |
368 #endif // NDEBUG | |
369 | |
370 // Now that basic liveness is complete, remove dead instructions that | 360 // Now that basic liveness is complete, remove dead instructions that |
371 // were tentatively marked as dead, and compute actual live ranges. | 361 // were tentatively marked as dead, and compute actual live ranges. |
372 // It is assumed that within a single basic block, a live range begins | 362 // It is assumed that within a single basic block, a live range begins |
373 // at most once and ends at most once. This is certainly true for | 363 // at most once and ends at most once. This is certainly true for |
374 // pure SSA form. It is also true once phis are lowered, since each | 364 // pure SSA form. It is also true once phis are lowered, since each |
375 // assignment to the phi-based temporary is in a different basic | 365 // assignment to the phi-based temporary is in a different basic |
376 // block, and there is a single read that ends the live in the basic | 366 // block, and there is a single read that ends the live in the basic |
377 // block that contained the actual phi instruction. | 367 // block that contained the actual phi instruction. |
378 void CfgNode::livenessPostprocess(LivenessMode Mode, Liveness *Liveness) { | 368 void CfgNode::livenessPostprocess(LivenessMode Mode, Liveness *Liveness) { |
379 InstNumberT FirstInstNum = Inst::NumberSentinel; | 369 InstNumberT FirstInstNum = Inst::NumberSentinel; |
(...skipping 19 matching lines...) Expand all Loading... |
399 LastInstNum = I->getNumber(); | 389 LastInstNum = I->getNumber(); |
400 // Create fake live ranges for a Kill instruction, but only if the | 390 // Create fake live ranges for a Kill instruction, but only if the |
401 // linked instruction is still alive. | 391 // linked instruction is still alive. |
402 if (Mode == Liveness_Intervals) { | 392 if (Mode == Liveness_Intervals) { |
403 if (InstFakeKill *Kill = llvm::dyn_cast<InstFakeKill>(I)) { | 393 if (InstFakeKill *Kill = llvm::dyn_cast<InstFakeKill>(I)) { |
404 if (!Kill->getLinked()->isDeleted()) { | 394 if (!Kill->getLinked()->isDeleted()) { |
405 SizeT NumSrcs = I->getSrcSize(); | 395 SizeT NumSrcs = I->getSrcSize(); |
406 for (SizeT Src = 0; Src < NumSrcs; ++Src) { | 396 for (SizeT Src = 0; Src < NumSrcs; ++Src) { |
407 Variable *Var = llvm::cast<Variable>(I->getSrc(Src)); | 397 Variable *Var = llvm::cast<Variable>(I->getSrc(Src)); |
408 InstNumberT InstNumber = I->getNumber(); | 398 InstNumberT InstNumber = I->getNumber(); |
409 Liveness->addLiveRange(Var, InstNumber, InstNumber, 1); | 399 Var->addLiveRange(InstNumber, InstNumber, 1); |
410 } | 400 } |
411 } | 401 } |
412 } | 402 } |
413 } | 403 } |
414 } | 404 } |
415 if (Mode != Liveness_Intervals) | 405 if (Mode != Liveness_Intervals) |
416 return; | 406 return; |
417 TimerMarker T1(TimerStack::TT_liveRangeCtor, Func); | 407 TimerMarker T1(TimerStack::TT_liveRangeCtor, Func); |
418 | 408 |
419 SizeT NumVars = Liveness->getNumVarsInNode(this); | 409 SizeT NumVars = Liveness->getNumVarsInNode(this); |
420 LivenessBV &LiveIn = Liveness->getLiveIn(this); | 410 LivenessBV &LiveIn = Liveness->getLiveIn(this); |
421 LivenessBV &LiveOut = Liveness->getLiveOut(this); | 411 LivenessBV &LiveOut = Liveness->getLiveOut(this); |
422 LiveBeginEndMap &MapBegin = *Liveness->getLiveBegin(this); | 412 LiveBeginEndMap &MapBegin = *Liveness->getLiveBegin(this); |
423 LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this); | 413 LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this); |
424 std::sort(MapBegin.begin(), MapBegin.end()); | 414 std::sort(MapBegin.begin(), MapBegin.end()); |
425 std::sort(MapEnd.begin(), MapEnd.end()); | 415 std::sort(MapEnd.begin(), MapEnd.end()); |
426 // Verify there are no duplicates. | 416 // Verify there are no duplicates. |
427 assert(std::adjacent_find(MapBegin.begin(), MapBegin.end(), comparePair) == | 417 struct ComparePair { |
| 418 bool operator()(const LiveBeginEndMapEntry &A, |
| 419 const LiveBeginEndMapEntry &B) { |
| 420 return A.first == B.first; |
| 421 } |
| 422 }; |
| 423 assert(std::adjacent_find(MapBegin.begin(), MapBegin.end(), ComparePair()) == |
428 MapBegin.end()); | 424 MapBegin.end()); |
429 assert(std::adjacent_find(MapEnd.begin(), MapEnd.end(), comparePair) == | 425 assert(std::adjacent_find(MapEnd.begin(), MapEnd.end(), ComparePair()) == |
430 MapEnd.end()); | 426 MapEnd.end()); |
431 | 427 |
432 LivenessBV LiveInAndOut = LiveIn; | 428 LivenessBV LiveInAndOut = LiveIn; |
433 LiveInAndOut &= LiveOut; | 429 LiveInAndOut &= LiveOut; |
434 | 430 |
435 // Iterate in parallel across the sorted MapBegin[] and MapEnd[]. | 431 // Iterate in parallel across the sorted MapBegin[] and MapEnd[]. |
436 auto IBB = MapBegin.begin(), IEB = MapEnd.begin(); | 432 auto IBB = MapBegin.begin(), IEB = MapEnd.begin(); |
437 auto IBE = MapBegin.end(), IEE = MapEnd.end(); | 433 auto IBE = MapBegin.end(), IEE = MapEnd.end(); |
438 while (IBB != IBE || IEB != IEE) { | 434 while (IBB != IBE || IEB != IEE) { |
439 SizeT i1 = IBB == IBE ? NumVars : IBB->first; | 435 SizeT i1 = IBB == IBE ? NumVars : IBB->first; |
440 SizeT i2 = IEB == IEE ? NumVars : IEB->first; | 436 SizeT i2 = IEB == IEE ? NumVars : IEB->first; |
441 SizeT i = std::min(i1, i2); | 437 SizeT i = std::min(i1, i2); |
442 // i1 is the Variable number of the next MapBegin entry, and i2 is | 438 // i1 is the Variable number of the next MapBegin entry, and i2 is |
443 // the Variable number of the next MapEnd entry. If i1==i2, then | 439 // the Variable number of the next MapEnd entry. If i1==i2, then |
444 // the Variable's live range begins and ends in this block. If | 440 // the Variable's live range begins and ends in this block. If |
445 // i1<i2, then i1's live range begins at instruction IBB->second | 441 // i1<i2, then i1's live range begins at instruction IBB->second |
446 // and extends through the end of the block. If i1>i2, then i2's | 442 // and extends through the end of the block. If i1>i2, then i2's |
447 // live range begins at the first instruction of the block and | 443 // live range begins at the first instruction of the block and |
448 // ends at IEB->second. In any case, we choose the lesser of i1 | 444 // ends at IEB->second. In any case, we choose the lesser of i1 |
449 // and i2 and proceed accordingly. | 445 // and i2 and proceed accordingly. |
450 InstNumberT LB = i == i1 ? IBB->second : FirstInstNum; | 446 InstNumberT LB = i == i1 ? IBB->second : FirstInstNum; |
451 InstNumberT LE = i == i2 ? IEB->second : LastInstNum + 1; | 447 InstNumberT LE = i == i2 ? IEB->second : LastInstNum + 1; |
452 | 448 |
453 Variable *Var = Liveness->getVariable(i, this); | 449 Variable *Var = Liveness->getVariable(i, this); |
454 if (!Var->getIgnoreLiveness()) { | 450 if (!Var->getIgnoreLiveness()) { |
455 if (LB > LE) { | 451 if (LB > LE) { |
456 Liveness->addLiveRange(Var, FirstInstNum, LE, 1); | 452 Var->addLiveRange(FirstInstNum, LE, 1); |
457 Liveness->addLiveRange(Var, LB, LastInstNum + 1, 1); | 453 Var->addLiveRange(LB, LastInstNum + 1, 1); |
458 // Assert that Var is a global variable by checking that its | 454 // Assert that Var is a global variable by checking that its |
459 // liveness index is less than the number of globals. This | 455 // liveness index is less than the number of globals. This |
460 // ensures that the LiveInAndOut[] access is valid. | 456 // ensures that the LiveInAndOut[] access is valid. |
461 assert(i < Liveness->getNumGlobalVars()); | 457 assert(i < Liveness->getNumGlobalVars()); |
462 LiveInAndOut[i] = false; | 458 LiveInAndOut[i] = false; |
463 } else { | 459 } else { |
464 Liveness->addLiveRange(Var, LB, LE, 1); | 460 Var->addLiveRange(LB, LE, 1); |
465 } | 461 } |
466 } | 462 } |
467 if (i == i1) | 463 if (i == i1) |
468 ++IBB; | 464 ++IBB; |
469 if (i == i2) | 465 if (i == i2) |
470 ++IEB; | 466 ++IEB; |
471 } | 467 } |
472 // Process the variables that are live across the entire block. | 468 // Process the variables that are live across the entire block. |
473 for (int i = LiveInAndOut.find_first(); i != -1; | 469 for (int i = LiveInAndOut.find_first(); i != -1; |
474 i = LiveInAndOut.find_next(i)) { | 470 i = LiveInAndOut.find_next(i)) { |
475 Variable *Var = Liveness->getVariable(i, this); | 471 Variable *Var = Liveness->getVariable(i, this); |
476 Liveness->addLiveRange(Var, FirstInstNum, LastInstNum + 1, 1); | 472 Var->addLiveRange(FirstInstNum, LastInstNum + 1, 1); |
477 } | 473 } |
478 } | 474 } |
479 | 475 |
480 void CfgNode::doBranchOpt(const CfgNode *NextNode) { | 476 void CfgNode::doBranchOpt(const CfgNode *NextNode) { |
481 TargetLowering *Target = Func->getTarget(); | 477 TargetLowering *Target = Func->getTarget(); |
482 // Check every instruction for a branch optimization opportunity. | 478 // Check every instruction for a branch optimization opportunity. |
483 // It may be more efficient to iterate in reverse and stop after the | 479 // It may be more efficient to iterate in reverse and stop after the |
484 // first opportunity, unless there is some target lowering where we | 480 // first opportunity, unless there is some target lowering where we |
485 // have the possibility of multiple such optimizations per block | 481 // have the possibility of multiple such optimizations per block |
486 // (currently not the case for x86 lowering). | 482 // (currently not the case for x86 lowering). |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
594 if (!First) | 590 if (!First) |
595 Str << ", "; | 591 Str << ", "; |
596 First = false; | 592 First = false; |
597 Str << "%" << I->getName(); | 593 Str << "%" << I->getName(); |
598 } | 594 } |
599 Str << "\n"; | 595 Str << "\n"; |
600 } | 596 } |
601 } | 597 } |
602 | 598 |
603 } // end of namespace Ice | 599 } // end of namespace Ice |
OLD | NEW |