diff options
Diffstat (limited to 'src/relooper/Relooper.cpp')
| -rw-r--r-- | src/relooper/Relooper.cpp | 74 |
1 files changed, 33 insertions, 41 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index aa7e71a1..ca9c6ab1 100644 --- a/src/relooper/Relooper.cpp +++ b/src/relooper/Relooper.cpp @@ -10,6 +10,10 @@ // TODO: move all set to unorderedset +template <class T, class U> bool contains(const T& container, const U& contained) { + return container.find(contained) != container.end(); +} + #if DEBUG static void PrintDebug(const char *Format, ...); #define DebugDump(x, ...) Debugging::Dump(x, __VA_ARGS__) @@ -100,7 +104,7 @@ void Branch::Render(Block *Target, bool SetLabel) { int Block::IdCounter = 1; // 0 is reserved for clearings -Block::Block(const char *CodeInit) : Parent(NULL), Id(Block::IdCounter++), DefaultTarget(NULL), IsCheckedMultipleEntry(false) { +Block::Block(const char *CodeInit) : Parent(NULL), Id(Block::IdCounter++), IsCheckedMultipleEntry(false) { Code = strdup(CodeInit); } @@ -113,7 +117,7 @@ Block::~Block() { } void Block::AddBranchTo(Block *Target, const char *Condition, const char *Code) { - assert(BranchesOut.find(Target) == BranchesOut.end()); // cannot add more than one branch to the same target + assert(!contains(BranchesOut, Target)); // cannot add more than one branch to the same target BranchesOut[Target] = new Branch(Condition, Code); } @@ -174,6 +178,8 @@ void Block::Render(bool InLoop) { } } + Block *DefaultTarget(NULL); // The block we branch to without checking the condition, if none of the other conditions held. + // We must do this here, because blocks can be split and even comparing their Ids is not enough. We must check the conditions. for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin(); iter != ProcessedBranchesOut.end(); iter++) { if (!iter->second->Condition) { @@ -181,7 +187,7 @@ void Block::Render(bool InLoop) { DefaultTarget = iter->first; } } - assert(DefaultTarget); // Must be a default + assert(DefaultTarget); // Since each block *must* branch somewhere, this must be set ministring RemainingConditions; bool First = true; @@ -198,7 +204,7 @@ void Block::Render(bool InLoop) { Details = ProcessedBranchesOut[DefaultTarget]; } bool SetCurrLabel = SetLabel && Target->IsCheckedMultipleEntry; - bool HasFusedContent = Fused && Fused->InnerMap.find(Target) != Fused->InnerMap.end(); + bool HasFusedContent = Fused && contains(Fused->InnerMap, Target); bool HasContent = SetCurrLabel || Details->Type != Branch::Direct || HasFusedContent || Details->Code; if (iter != ProcessedBranchesOut.end()) { // If there is nothing to show in this branch, omit the condition @@ -356,7 +362,7 @@ void Relooper::Calculate(Block *Entry) { while (ToInvestigate.size() > 0) { Block *Curr = ToInvestigate.front(); ToInvestigate.pop_front(); - if (Live.find(Curr) != Live.end()) continue; + if (contains(Live, Curr)) continue; Live.insert(Curr); for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { ToInvestigate.push_back(iter->first); @@ -380,7 +386,7 @@ void Relooper::Calculate(Block *Entry) { for (BlockSet::iterator iter = Live.begin(); iter != Live.end(); iter++) { Block *Original = *iter; if (Original->BranchesIn.size() <= 1 || Original->BranchesOut.size() > 0) continue; // only dead ends, for now - if (Original->BranchesOut.find(Original) != Original->BranchesOut.end()) continue; // cannot split a looping node + if (contains(Original->BranchesOut, Original)) continue; // cannot split a looping node if (strlen(Original->Code)*(Original->BranchesIn.size()-1) > TotalCodeSize/5) continue; // if splitting increases raw code size by a significant amount, abort // Split the node (for simplicity, we replace all the blocks, even though we could have reused the original) PrintDebug("Splitting block %d\n", Original->Id); @@ -423,7 +429,7 @@ void Relooper::Calculate(Block *Entry) { // Add incoming branches from live blocks, ignoring dead code for (int i = 0; i < Blocks.size(); i++) { Block *Curr = Blocks[i]; - if (Pre.Live.find(Curr) == Pre.Live.end()) continue; + if (!contains(Pre.Live, Curr)) continue; for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { iter->first->BranchesIn.insert(Curr); } @@ -445,7 +451,7 @@ void Relooper::Calculate(Block *Entry) { // will appear void GetBlocksOut(Block *Source, BlockSet& Entries, BlockSet *LimitTo=NULL) { for (BlockBranchMap::iterator iter = Source->BranchesOut.begin(); iter != Source->BranchesOut.end(); iter++) { - if (!LimitTo || LimitTo->find(iter->first) != LimitTo->end()) { + if (!LimitTo || contains(*LimitTo, iter->first)) { Entries.insert(iter->first); } } @@ -457,7 +463,7 @@ void Relooper::Calculate(Block *Entry) { DebugDump(From, " relevant to solipsize: "); for (BlockSet::iterator iter = Target->BranchesIn.begin(); iter != Target->BranchesIn.end();) { Block *Prior = *iter; - if (From.find(Prior) == From.end()) { + if (!contains(From, Prior)) { iter++; continue; } @@ -502,7 +508,7 @@ void Relooper::Calculate(Block *Entry) { while (Queue.size() > 0) { Block *Curr = *(Queue.begin()); Queue.erase(Queue.begin()); - if (InnerBlocks.find(Curr) == InnerBlocks.end()) { + if (!contains(InnerBlocks, Curr)) { // This element is new, mark it as inner and remove from outer InnerBlocks.insert(Curr); Blocks.erase(Curr); @@ -518,7 +524,7 @@ void Relooper::Calculate(Block *Entry) { Block *Curr = *iter; for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { Block *Possible = iter->first; - if (InnerBlocks.find(Possible) == InnerBlocks.end()) { + if (!contains(InnerBlocks, Possible)) { NextEntries.insert(Possible); } } @@ -615,7 +621,7 @@ void Relooper::Calculate(Block *Entry) { Block *Invalidatee = ToInvalidate.front(); ToInvalidate.pop_front(); Block *Owner = Ownership[Invalidatee]; - if (IndependentGroups.find(Owner) != IndependentGroups.end()) { // Owner may have been invalidated, do not add to IndependentGroups! + if (contains(IndependentGroups, Owner)) { // Owner may have been invalidated, do not add to IndependentGroups! IndependentGroups[Owner].erase(Invalidatee); } if (Ownership[Invalidatee]) { // may have been seen before and invalidated already @@ -688,7 +694,7 @@ void Relooper::Calculate(Block *Entry) { Block *Child = *iter; for (BlockSet::iterator iter = Child->BranchesIn.begin(); iter != Child->BranchesIn.end(); iter++) { Block *Parent = *iter; - if (Ignore && Ignore->find(Parent) != Ignore->end()) continue; + if (Ignore && contains(*Ignore, Parent)) continue; if (Helper.Ownership[Parent] != Helper.Ownership[Child]) { ToInvalidate.push_back(Child); } @@ -739,7 +745,7 @@ void Relooper::Calculate(Block *Entry) { Block *CurrTarget = iter->first; BlockBranchMap::iterator Next = iter; Next++; - if (CurrBlocks.find(CurrTarget) == CurrBlocks.end()) { + if (!contains(CurrBlocks, CurrTarget)) { NextEntries.insert(CurrTarget); Solipsize(CurrTarget, Branch::Break, Multiple, CurrBlocks); } @@ -756,7 +762,7 @@ void Relooper::Calculate(Block *Entry) { // Add entries not handled as next entries, they are deferred for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); iter++) { Block *Entry = *iter; - if (IndependentGroups.find(Entry) == IndependentGroups.end()) { + if (!contains(IndependentGroups, Entry)) { NextEntries.insert(Entry); } } @@ -820,7 +826,7 @@ void Relooper::Calculate(Block *Entry) { BlockBlockSetMap::iterator curr = iter++; // iterate carefully, we may delete for (BlockSet::iterator iterBranch = Entry->BranchesIn.begin(); iterBranch != Entry->BranchesIn.end(); iterBranch++) { Block *Origin = *iterBranch; - if (Group.find(Origin) == Group.end()) { + if (!contains(Group, Origin)) { // Reached from outside the group, so we cannot handle this PrintDebug("Cannot handle group with entry %d because of incoming branch from %d\n", Entry->Id, Origin->Id); IndependentGroups.erase(curr); @@ -858,7 +864,7 @@ void Relooper::Calculate(Block *Entry) { Block *Curr = *iter; for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { Block *Target = iter->first; - if (SmallGroup.find(Target) == SmallGroup.end()) { + if (!contains(SmallGroup, Target)) { DeadEnd = false; break; } @@ -909,13 +915,13 @@ void Relooper::Calculate(Block *Entry) { PostOptimizer(Relooper *ParentInit) : Parent(ParentInit), Closure(NULL) {} - #define RECURSE_MULTIPLE_MANUAL(func, manual) \ - for (BlockShapeMap::iterator iter = manual->InnerMap.begin(); iter != manual->InnerMap.end(); iter++) { \ + #define RECURSE_Multiple(shape, func) \ + for (BlockShapeMap::iterator iter = shape->InnerMap.begin(); iter != shape->InnerMap.end(); iter++) { \ func(iter->second); \ } - #define RECURSE_MULTIPLE(func) RECURSE_MULTIPLE_MANUAL(func, Multiple); - #define RECURSE_LOOP(func) \ - func(Loop->Inner); + #define RECURSE_Loop(shape, func) \ + func(shape->Inner); + #define RECURSE(shape, func) RECURSE_##shape(shape, func); #define SHAPE_SWITCH(var, simple, multiple, loop) \ if (SimpleShape *Simple = Shape::IsSimple(var)) { \ @@ -926,20 +932,6 @@ void Relooper::Calculate(Block *Entry) { loop; \ } - #define SHAPE_SWITCH_AUTO(var, simple, multiple, loop, func) \ - if (SimpleShape *Simple = Shape::IsSimple(var)) { \ - simple; \ - func(Simple->Next); \ - } else if (MultipleShape *Multiple = Shape::IsMultiple(var)) { \ - multiple; \ - RECURSE_MULTIPLE(func) \ - func(Multiple->Next); \ - } else if (LoopShape *Loop = Shape::IsLoop(var)) { \ - loop; \ - RECURSE_LOOP(func); \ - func(Loop->Next); \ - } - // Find the blocks that natural control flow can get us directly to, or through a multiple that we ignore void FollowNaturalFlow(Shape *S, BlockSet &Out) { SHAPE_SWITCH(S, { @@ -992,7 +984,7 @@ void Relooper::Calculate(Block *Entry) { for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) { Block *Target = iter->first; Branch *Details = iter->second; - if (Details->Type != Branch::Direct && NaturalBlocks.find(Target) != NaturalBlocks.end()) { // note: cannot handle split blocks + if (Details->Type != Branch::Direct && contains(NaturalBlocks, Target)) { // note: cannot handle split blocks Details->Type = Branch::Direct; if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) { Multiple->NeedLoop--; @@ -1036,7 +1028,7 @@ void Relooper::Calculate(Block *Entry) { // If we are fusing a Multiple with a loop into this Simple, then visit it now if (Fused && Fused->NeedLoop) { LoopStack.push(Fused); - RECURSE_MULTIPLE_MANUAL(FindLabeledLoops, Fused); + RECURSE_Multiple(Fused, FindLabeledLoops); } for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) { Block *Target = iter->first; @@ -1062,14 +1054,14 @@ void Relooper::Calculate(Block *Entry) { if (Multiple->NeedLoop) { LoopStack.push(Multiple); } - RECURSE_MULTIPLE(FindLabeledLoops); + RECURSE(Multiple, FindLabeledLoops); if (Multiple->NeedLoop) { LoopStack.pop(); } Next = Root->Next; }, { LoopStack.push(Loop); - RECURSE_LOOP(FindLabeledLoops); + RECURSE(Loop, FindLabeledLoops); LoopStack.pop(); Next = Root->Next; }); @@ -1123,7 +1115,7 @@ void Debugging::Dump(BlockSet &Blocks, const char *prefix) { for (BlockBranchMap::iterator iter2 = Curr->BranchesOut.begin(); iter2 != Curr->BranchesOut.end(); iter2++) { Block *Other = iter2->first; printf(" -> %d\n", Other->Id); - assert(Other->BranchesIn.find(Curr) != Other->BranchesIn.end()); + assert(contains(Other->BranchesIn, Curr)); } } } |