From 96cb1128528a512f1ef9c28ae5e1b78a98dcc505 Mon Sep 17 00:00:00 2001 From: Bill Wendling Date: Thu, 19 Jul 2012 00:04:14 +0000 Subject: Remove tabs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160475 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 0719e2b044..ecc1e951fa 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -673,7 +673,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { // Inherit live-ins from the successor for (MachineBasicBlock::livein_iterator I = Succ->livein_begin(), - E = Succ->livein_end(); I != E; ++I) + E = Succ->livein_end(); I != E; ++I) NMBB->addLiveIn(*I); // Update LiveVariables. -- cgit v1.2.3-18-g5258 From f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 30 Jul 2012 17:36:47 +0000 Subject: Add MachineBasicBlock::isPredecessor(). A->isPredecessor(B) is the same as B->isSuccessor(A), but it can tolerate a B that is null or dangling. This shouldn't happen normally, but it it useful for verification code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160968 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index ecc1e951fa..f361d1ac29 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -540,9 +540,12 @@ MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB) { } } +bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const { + return std::find(pred_begin(), pred_end(), MBB) != pred_end(); +} + bool MachineBasicBlock::isSuccessor(const MachineBasicBlock *MBB) const { - const_succ_iterator I = std::find(Successors.begin(), Successors.end(), MBB); - return I != Successors.end(); + return std::find(succ_begin(), succ_end(), MBB) != succ_end(); } bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { -- cgit v1.2.3-18-g5258 From 5e63d43e48f6d0b597d21b83a1eed9eaf2febc93 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 8 Aug 2012 00:20:37 +0000 Subject: Fix a quadratic algorithm in MachineBranchProbabilityInfo. The getSumForBlock function was quadratic in the number of successors because getSuccWeight would perform a linear search for an already known iterator. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161460 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index f361d1ac29..2ba414dc6d 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -912,12 +912,11 @@ MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { /// getSuccWeight - Return weight of the edge from this block to MBB. /// -uint32_t MachineBasicBlock::getSuccWeight(const MachineBasicBlock *succ) const { +uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { if (Weights.empty()) return 0; - const_succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); - return *getWeightIterator(I); + return *getWeightIterator(Succ); } /// getWeightIterator - Return wight iterator corresonding to the I successor -- cgit v1.2.3-18-g5258 From 913ff09a9acf563ae9719ff223bc117dd66ad6b0 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 8 Aug 2012 01:10:31 +0000 Subject: Revert "Fix a quadratic algorithm in MachineBranchProbabilityInfo." It caused an assertion failure when compiling consumer-typeset. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161463 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 2ba414dc6d..f361d1ac29 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -912,11 +912,12 @@ MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { /// getSuccWeight - Return weight of the edge from this block to MBB. /// -uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { +uint32_t MachineBasicBlock::getSuccWeight(const MachineBasicBlock *succ) const { if (Weights.empty()) return 0; - return *getWeightIterator(Succ); + const_succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); + return *getWeightIterator(I); } /// getWeightIterator - Return wight iterator corresonding to the I successor -- cgit v1.2.3-18-g5258 From ff2b99afc8cbc6cfa73181072888e0f9f07deb7e Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Thu, 9 Aug 2012 22:49:37 +0000 Subject: Move use list management into MachineRegisterInfo. Register MachineOperands are kept in linked lists accessible via MRI's reg_iterator interfaces. The linked list management was handled partly by MachineOperand methods, partly by MRI methods. Move all of the list management into MRI, delete MO::AddRegOperandToRegInfo() and MO::RemoveRegOperandFromRegInfo(). Be more explicit about handling the cases where an MRI pointer isn't available. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161632 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index f361d1ac29..151b402168 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -109,7 +109,8 @@ void ilist_traits::removeNodeFromList(MachineInstr *N) { assert(N->getParent() != 0 && "machine instruction not in a basic block"); // Remove from the use/def lists. - N->RemoveRegOperandsFromUseLists(); + if (MachineFunction *MF = N->getParent()->getParent()) + N->RemoveRegOperandsFromUseLists(MF->getRegInfo()); N->setParent(0); -- cgit v1.2.3-18-g5258 From 15121ca0d18e6a0f6a16f8a696f4efc3782dc965 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 10 Aug 2012 03:23:27 +0000 Subject: Update edge weights correctly in replaceSuccessor(). When replacing Old with New, it can happen that New is already a successor. Add the old and new edge weights instead of creating a duplicate edge. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161653 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 42 ++++++++++++++++++++++++++++++--------- 1 file changed, 33 insertions(+), 9 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 151b402168..fd4cb5fab0 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -478,18 +478,42 @@ MachineBasicBlock::removeSuccessor(succ_iterator I) { void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New) { - uint32_t weight = 0; - succ_iterator SI = std::find(Successors.begin(), Successors.end(), Old); + if (Old == New) + return; - // If Weight list is empty it means we don't use it (disabled optimization). - if (!Weights.empty()) { - weight_iterator WI = getWeightIterator(SI); - weight = *WI; + succ_iterator E = succ_end(); + succ_iterator NewI = E; + succ_iterator OldI = E; + for (succ_iterator I = succ_begin(); I != E; ++I) { + if (*I == Old) { + OldI = I; + if (NewI != E) + break; + } + if (*I == New) { + NewI = I; + if (OldI != E) + break; + } } + assert(OldI != E && "Old is not a successor of this block"); + Old->removePredecessor(this); - // Update the successor information. - removeSuccessor(SI); - addSuccessor(New, weight); + // If New isn't already a successor, let it take Old's place. + if (NewI == E) { + New->addPredecessor(this); + *OldI = New; + return; + } + + // New is already a successor. + // Update its weight instead of adding a duplicate edge. + if (!Weights.empty()) { + weight_iterator OldWI = getWeightIterator(OldI); + *getWeightIterator(NewI) += *OldWI; + Weights.erase(OldWI); + } + Successors.erase(OldI); } void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { -- cgit v1.2.3-18-g5258 From cb6889b23d7bdac292e0203bcca19e82b2e17875 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 13 Aug 2012 23:13:23 +0000 Subject: Print out MachineBasicBlock successor weights when available. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161804 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index fd4cb5fab0..8bf0cc9656 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -311,8 +311,11 @@ void MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { if (!succ_empty()) { if (Indexes) OS << '\t'; OS << " Successors according to CFG:"; - for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) + for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) { OS << " BB#" << (*SI)->getNumber(); + if (!Weights.empty()) + OS << '(' << *getWeightIterator(SI) << ')'; + } OS << '\n'; } } -- cgit v1.2.3-18-g5258 From 03e593efc65807dad7ca8807554584fcb89f40f1 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 13 Aug 2012 23:13:25 +0000 Subject: Transfer weights in transferSuccessorsAndUpdatePHIs(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161805 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 8bf0cc9656..fa6b4502c4 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -535,14 +535,13 @@ void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) { while (!fromMBB->succ_empty()) { MachineBasicBlock *Succ = *fromMBB->succ_begin(); - uint32_t weight = 0; - + uint32_t Weight = 0; // If Weight list is empty it means we don't use it (disabled optimization). if (!fromMBB->Weights.empty()) - weight = *fromMBB->Weights.begin(); + Weight = *fromMBB->Weights.begin(); - addSuccessor(Succ, weight); + addSuccessor(Succ, Weight); fromMBB->removeSuccessor(Succ); } } @@ -554,7 +553,10 @@ MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB) { while (!fromMBB->succ_empty()) { MachineBasicBlock *Succ = *fromMBB->succ_begin(); - addSuccessor(Succ); + uint32_t Weight = 0; + if (!fromMBB->Weights.empty()) + Weight = *fromMBB->Weights.begin(); + addSuccessor(Succ, Weight); fromMBB->removeSuccessor(Succ); // Fix up any PHI nodes in the successor. -- cgit v1.2.3-18-g5258 From 990ca5517fd6666d4049b6b8281d9df99da11637 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 20 Aug 2012 22:01:38 +0000 Subject: Fix a quadratic algorithm in MachineBranchProbabilityInfo. The getSumForBlock function was quadratic in the number of successors because getSuccWeight would perform a linear search for an already known iterator. This patch was originally committed as r161460, but reverted again because of assertion failures. Now that duplicate Machine CFG edges have been eliminated, this works properly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162233 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBasicBlock.cpp | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'lib/CodeGen/MachineBasicBlock.cpp') diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index fa6b4502c4..cf13dbdab6 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -942,12 +942,11 @@ MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { /// getSuccWeight - Return weight of the edge from this block to MBB. /// -uint32_t MachineBasicBlock::getSuccWeight(const MachineBasicBlock *succ) const { +uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { if (Weights.empty()) return 0; - const_succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); - return *getWeightIterator(I); + return *getWeightIterator(Succ); } /// getWeightIterator - Return wight iterator corresonding to the I successor -- cgit v1.2.3-18-g5258