aboutsummaryrefslogtreecommitdiff
path: root/src/relooper
diff options
context:
space:
mode:
Diffstat (limited to 'src/relooper')
-rw-r--r--src/relooper/Relooper.cpp74
-rw-r--r--src/relooper/Relooper.h2
2 files changed, 33 insertions, 43 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));
}
}
}
diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h
index fe56a133..e54b578c 100644
--- a/src/relooper/Relooper.h
+++ b/src/relooper/Relooper.h
@@ -59,8 +59,6 @@ struct Block {
Shape *Parent; // The shape we are directly inside
int Id; // A unique identifier
const char *Code; // The string representation of the code in this block. Owning pointer (we copy the input)
- Block *DefaultTarget; // The block we branch to without checking the condition, if none of the other conditions held.
- // Since each block *must* branch somewhere, this must be set
bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching us requires setting the label variable
Block(const char *CodeInit);
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-22 01:02:21 +0000