aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils/SimplifyCFG.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Utils/SimplifyCFG.cpp')
-rw-r--r--lib/Transforms/Utils/SimplifyCFG.cpp80
1 files changed, 52 insertions, 28 deletions
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 9823433e86..3cae77227c 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -13,6 +13,14 @@
#define DEBUG_TYPE "simplifycfg"
#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Constants.h"
#include "llvm/DataLayout.h"
#include "llvm/DerivedTypes.h"
@@ -25,15 +33,6 @@
#include "llvm/Metadata.h"
#include "llvm/Module.h"
#include "llvm/Operator.h"
-#include "llvm/Type.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/InstructionSimplify.h"
-#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ConstantRange.h"
@@ -42,9 +41,10 @@
#include "llvm/Support/raw_ostream.h"
#include "llvm/TargetTransformInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Type.h"
#include <algorithm>
-#include <set>
#include <map>
+#include <set>
using namespace llvm;
static cl::opt<unsigned>
@@ -858,7 +858,7 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
if (PredHasWeights) {
GetBranchWeights(PTI, Weights);
- // branch-weight metadata is inconsistant here.
+ // branch-weight metadata is inconsistent here.
if (Weights.size() != 1 + PredCases.size())
PredHasWeights = SuccHasWeights = false;
} else if (SuccHasWeights)
@@ -870,7 +870,7 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
SmallVector<uint64_t, 8> SuccWeights;
if (SuccHasWeights) {
GetBranchWeights(TI, SuccWeights);
- // branch-weight metadata is inconsistant here.
+ // branch-weight metadata is inconsistent here.
if (SuccWeights.size() != 1 + BBCases.size())
PredHasWeights = SuccHasWeights = false;
} else if (PredHasWeights)
@@ -967,8 +967,8 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I =
PTIHandled.begin(),
E = PTIHandled.end(); I != E; ++I) {
- if (PredHasWeights || SuccHasWeights)
- Weights.push_back(WeightsForHandled[*I]);
+ if (PredHasWeights || SuccHasWeights)
+ Weights.push_back(WeightsForHandled[*I]);
PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault));
NewSuccessors.push_back(BBDefault);
}
@@ -1193,7 +1193,7 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) {
I != E; ++I) {
if (PHINode *PN = dyn_cast<PHINode>(I)) {
Value *BB1V = PN->getIncomingValueForBlock(BB1);
- Value *BB2V = PN->getIncomingValueForBlock(BB2);
+ Value *BB2V = PN->getIncomingValueForBlock(BB2);
MapValueFromBB1ToBB2[BB1V] = std::make_pair(BB2V, PN);
} else {
FirstNonPhiInBBEnd = &*I;
@@ -1202,7 +1202,7 @@ static bool SinkThenElseCodeToEnd(BranchInst *BI1) {
}
if (!FirstNonPhiInBBEnd)
return false;
-
+
// This does very trivial matching, with limited scanning, to find identical
// instructions in the two blocks. We scan backward for obviously identical
@@ -1415,7 +1415,7 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
if (BB1V == BIParentV)
continue;
- // Check for saftey.
+ // Check for safety.
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BB1V)) {
// An unfolded ConstantExpr could end up getting expanded into
// Instructions. Don't speculate this and another instruction at
@@ -3511,22 +3511,44 @@ bool SwitchLookupTable::WouldFitInRegister(const DataLayout *TD,
static bool ShouldBuildLookupTable(SwitchInst *SI,
uint64_t TableSize,
const DataLayout *TD,
+ const TargetTransformInfo *TTI,
const SmallDenseMap<PHINode*, Type*>& ResultTypes) {
- // The table density should be at least 40%. This is the same criterion as for
- // jump tables, see SelectionDAGBuilder::handleJTSwitchCase.
- // FIXME: Find the best cut-off.
if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10)
return false; // TableSize overflowed, or mul below might overflow.
- if (SI->getNumCases() * 10 >= TableSize * 4)
- return true;
- // If each table would fit in a register, we should build it anyway.
+ bool AllTablesFitInRegister = true;
+ bool HasIllegalType = false;
for (SmallDenseMap<PHINode*, Type*>::const_iterator I = ResultTypes.begin(),
E = ResultTypes.end(); I != E; ++I) {
- if (!SwitchLookupTable::WouldFitInRegister(TD, TableSize, I->second))
- return false;
+ Type *Ty = I->second;
+
+ // Saturate this flag to true.
+ HasIllegalType = HasIllegalType ||
+ !TTI->getScalarTargetTransformInfo()->isTypeLegal(Ty);
+
+ // Saturate this flag to false.
+ AllTablesFitInRegister = AllTablesFitInRegister &&
+ SwitchLookupTable::WouldFitInRegister(TD, TableSize, Ty);
+
+ // If both flags saturate, we're done. NOTE: This *only* works with
+ // saturating flags, and all flags have to saturate first due to the
+ // non-deterministic behavior of iterating over a dense map.
+ if (HasIllegalType && !AllTablesFitInRegister)
+ break;
}
- return true;
+
+ // If each table would fit in a register, we should build it anyway.
+ if (AllTablesFitInRegister)
+ return true;
+
+ // Don't build a table that doesn't fit in-register if it has illegal types.
+ if (HasIllegalType)
+ return false;
+
+ // The table density should be at least 40%. This is the same criterion as for
+ // jump tables, see SelectionDAGBuilder::handleJTSwitchCase.
+ // FIXME: Find the best cut-off.
+ return SI->getNumCases() * 10 >= TableSize * 4;
}
/// SwitchToLookupTable - If the switch is only used to initialize one or more
@@ -3538,7 +3560,9 @@ static bool SwitchToLookupTable(SwitchInst *SI,
const TargetTransformInfo *TTI) {
assert(SI->getNumCases() > 1 && "Degenerate switch?");
- if (TTI && !TTI->getScalarTargetTransformInfo()->shouldBuildLookupTables())
+ // Only build lookup table when we have a target that supports it.
+ if (!TTI || !TTI->getScalarTargetTransformInfo() ||
+ !TTI->getScalarTargetTransformInfo()->shouldBuildLookupTables())
return false;
// FIXME: If the switch is too sparse for a lookup table, perhaps we could
@@ -3605,7 +3629,7 @@ static bool SwitchToLookupTable(SwitchInst *SI,
APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue();
uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
- if (!ShouldBuildLookupTable(SI, TableSize, TD, ResultTypes))
+ if (!ShouldBuildLookupTable(SI, TableSize, TD, TTI, ResultTypes))
return false;
// Create the BB that does the lookups.
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-03 11:58:13 +0000