aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/SelectOptimize.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/SelectOptimize.cpp')
-rw-r--r--llvm/lib/CodeGen/SelectOptimize.cpp481
1 files changed, 220 insertions, 261 deletions
diff --git a/llvm/lib/CodeGen/SelectOptimize.cpp b/llvm/lib/CodeGen/SelectOptimize.cpp
index 6b6d590..81796fc 100644
--- a/llvm/lib/CodeGen/SelectOptimize.cpp
+++ b/llvm/lib/CodeGen/SelectOptimize.cpp
@@ -127,26 +127,77 @@ public:
/// act like selects. For example Or(Zext(icmp), X) can be treated like
/// select(icmp, X|1, X).
class SelectLike {
+ SelectLike(Instruction *I) : I(I) {}
+
/// The select (/or) instruction.
Instruction *I;
/// Whether this select is inverted, "not(cond), FalseVal, TrueVal", as
/// opposed to the original condition.
bool Inverted = false;
- /// The index of the operand that depends on condition. Only for select-like
- /// instruction such as Or/Add.
- unsigned CondIdx;
-
public:
- SelectLike(Instruction *I, bool Inverted = false, unsigned CondIdx = 0)
- : I(I), Inverted(Inverted), CondIdx(CondIdx) {}
+ /// Match a select or select-like instruction, returning a SelectLike.
+ static SelectLike match(Instruction *I) {
+ // Select instruction are what we are usually looking for.
+ if (isa<SelectInst>(I))
+ return SelectLike(I);
+
+ // An Or(zext(i1 X), Y) can also be treated like a select, with condition
+ // C and values Y|1 and Y.
+ Value *X;
+ if (PatternMatch::match(
+ I, m_c_Or(m_OneUse(m_ZExt(m_Value(X))), m_Value())) &&
+ X->getType()->isIntegerTy(1))
+ return SelectLike(I);
+
+ return SelectLike(nullptr);
+ }
+
+ bool isValid() { return I; }
+ operator bool() { return isValid(); }
+
+ /// Invert the select by inverting the condition and switching the operands.
+ void setInverted() {
+ assert(!Inverted && "Trying to invert an inverted SelectLike");
+ assert(isa<Instruction>(getCondition()) &&
+ cast<Instruction>(getCondition())->getOpcode() ==
+ Instruction::Xor);
+ Inverted = true;
+ }
+ bool isInverted() const { return Inverted; }
Instruction *getI() { return I; }
const Instruction *getI() const { return I; }
Type *getType() const { return I->getType(); }
- unsigned getConditionOpIndex() { return CondIdx; };
+ Value *getNonInvertedCondition() const {
+ if (auto *Sel = dyn_cast<SelectInst>(I))
+ return Sel->getCondition();
+ // Or(zext) case
+ if (auto *BO = dyn_cast<BinaryOperator>(I)) {
+ Value *X;
+ if (PatternMatch::match(BO->getOperand(0),
+ m_OneUse(m_ZExt(m_Value(X)))))
+ return X;
+ if (PatternMatch::match(BO->getOperand(1),
+ m_OneUse(m_ZExt(m_Value(X)))))
+ return X;
+ }
+
+ llvm_unreachable("Unhandled case in getCondition");
+ }
+
+ /// Return the condition for the SelectLike instruction. For example the
+ /// condition of a select or c in `or(zext(c), x)`
+ Value *getCondition() const {
+ Value *CC = getNonInvertedCondition();
+ // For inverted conditions the CC is checked when created to be a not
+ // (xor) instruction.
+ if (Inverted)
+ return cast<Instruction>(CC)->getOperand(0);
+ return CC;
+ }
/// Return the true value for the SelectLike instruction. Note this may not
/// exist for all SelectLike instructions. For example, for `or(zext(c), x)`
@@ -173,56 +224,74 @@ public:
return getTrueValue(/*HonorInverts=*/false);
if (auto *Sel = dyn_cast<SelectInst>(I))
return Sel->getFalseValue();
- // We are on the branch where the condition is zero, which means BinOp
- // does not perform any computation, and we can simply return the operand
- // that is not related to the condition
- if (auto *BO = dyn_cast<BinaryOperator>(I))
- return BO->getOperand(1 - CondIdx);
+ // Or(zext) case - return the operand which is not the zext.
+ if (auto *BO = dyn_cast<BinaryOperator>(I)) {
+ Value *X;
+ if (PatternMatch::match(BO->getOperand(0),
+ m_OneUse(m_ZExt(m_Value(X)))))
+ return BO->getOperand(1);
+ if (PatternMatch::match(BO->getOperand(1),
+ m_OneUse(m_ZExt(m_Value(X)))))
+ return BO->getOperand(0);
+ }
llvm_unreachable("Unhandled case in getFalseValue");
}
- /// Return the NonPredCost cost of the op on \p isTrue branch, given the
- /// costs in \p InstCostMap. This may need to be generated for select-like
- /// instructions.
- Scaled64 getOpCostOnBranch(
- bool IsTrue, const DenseMap<const Instruction *, CostInfo> &InstCostMap,
- const TargetTransformInfo *TTI) {
- auto *V = IsTrue ? getTrueValue() : getFalseValue();
- if (V) {
- if (auto *IV = dyn_cast<Instruction>(V)) {
- auto It = InstCostMap.find(IV);
+ /// Return the NonPredCost cost of the true op, given the costs in
+ /// InstCostMap. This may need to be generated for select-like instructions.
+ Scaled64 getTrueOpCost(DenseMap<const Instruction *, CostInfo> &InstCostMap,
+ const TargetTransformInfo *TTI) {
+ if (isa<SelectInst>(I))
+ if (auto *I = dyn_cast<Instruction>(getTrueValue())) {
+ auto It = InstCostMap.find(I);
return It != InstCostMap.end() ? It->second.NonPredCost
: Scaled64::getZero();
}
- return Scaled64::getZero();
- }
- // If getTrue(False)Value() return nullptr, it means we are dealing with
- // select-like instructions on the branch where the actual computation is
- // happening. In that case the cost is equal to the cost of computation +
- // cost of non-dependant on condition operand
- InstructionCost Cost = TTI->getArithmeticInstrCost(
- getI()->getOpcode(), I->getType(), TargetTransformInfo::TCK_Latency,
- {TargetTransformInfo::OK_AnyValue, TargetTransformInfo::OP_None},
- {TTI::OK_UniformConstantValue, TTI::OP_PowerOf2});
- auto TotalCost = Scaled64::get(*Cost.getValue());
- if (auto *OpI = dyn_cast<Instruction>(I->getOperand(1 - CondIdx))) {
- auto It = InstCostMap.find(OpI);
- if (It != InstCostMap.end())
- TotalCost += It->second.NonPredCost;
- }
- return TotalCost;
+
+ // Or case - add the cost of an extra Or to the cost of the False case.
+ if (isa<BinaryOperator>(I))
+ if (auto I = dyn_cast<Instruction>(getFalseValue())) {
+ auto It = InstCostMap.find(I);
+ if (It != InstCostMap.end()) {
+ InstructionCost OrCost = TTI->getArithmeticInstrCost(
+ Instruction::Or, I->getType(), TargetTransformInfo::TCK_Latency,
+ {TargetTransformInfo::OK_AnyValue,
+ TargetTransformInfo::OP_None},
+ {TTI::OK_UniformConstantValue, TTI::OP_PowerOf2});
+ return It->second.NonPredCost + Scaled64::get(*OrCost.getValue());
+ }
+ }
+
+ return Scaled64::getZero();
+ }
+
+ /// Return the NonPredCost cost of the false op, given the costs in
+ /// InstCostMap. This may need to be generated for select-like instructions.
+ Scaled64
+ getFalseOpCost(DenseMap<const Instruction *, CostInfo> &InstCostMap,
+ const TargetTransformInfo *TTI) {
+ if (isa<SelectInst>(I))
+ if (auto *I = dyn_cast<Instruction>(getFalseValue())) {
+ auto It = InstCostMap.find(I);
+ return It != InstCostMap.end() ? It->second.NonPredCost
+ : Scaled64::getZero();
+ }
+
+ // Or case - return the cost of the false case
+ if (isa<BinaryOperator>(I))
+ if (auto I = dyn_cast<Instruction>(getFalseValue()))
+ if (auto It = InstCostMap.find(I); It != InstCostMap.end())
+ return It->second.NonPredCost;
+
+ return Scaled64::getZero();
}
};
private:
- // Select groups consist of consecutive select-like instructions with the same
- // condition. Between select-likes could be any number of auxiliary
- // instructions related to the condition like not, zext
- struct SelectGroup {
- Value *Condition;
- SmallVector<SelectLike, 2> Selects;
- };
+ // Select groups consist of consecutive select instructions with the same
+ // condition.
+ using SelectGroup = SmallVector<SelectLike, 2>;
using SelectGroups = SmallVector<SelectGroup, 2>;
// Converts select instructions of a function to conditional jumps when deemed
@@ -282,11 +351,6 @@ private:
SmallDenseMap<const Instruction *, SelectLike, 2>
getSImap(const SelectGroups &SIGroups);
- // Returns a map from select-like instructions to the corresponding select
- // group.
- SmallDenseMap<const Instruction *, const SelectGroup *, 2>
- getSGmap(const SelectGroups &SIGroups);
-
// Returns the latency cost of a given instruction.
std::optional<uint64_t> computeInstCost(const Instruction *I);
@@ -465,45 +529,34 @@ void SelectOptimizeImpl::optimizeSelectsInnerLoops(Function &F,
}
}
-/// Returns optimised value on \p IsTrue branch. For SelectInst that would be
-/// either True or False value. For (BinaryOperator) instructions, where the
-/// condition may be skipped, the operation will use a non-conditional operand.
-/// For example, for `or(V,zext(cond))` this function would return V.
-/// However, if the conditional operand on \p IsTrue branch matters, we create a
-/// clone of instruction at the end of that branch \p B and replace the
-/// condition operand with a constant.
-///
-/// Also /p OptSelects contains previously optimised select-like instructions.
-/// If the current value uses one of the optimised values, we can optimise it
-/// further by replacing it with the corresponding value on the given branch
-static Value *getTrueOrFalseValue(
- SelectOptimizeImpl::SelectLike &SI, bool isTrue,
- SmallDenseMap<Instruction *, std::pair<Value *, Value *>, 2> &OptSelects,
- BasicBlock *B) {
- Value *V = isTrue ? SI.getTrueValue() : SI.getFalseValue();
- if (V) {
- auto *IV = dyn_cast<Instruction>(V);
- if (IV && OptSelects.count(IV))
- return isTrue ? OptSelects[IV].first : OptSelects[IV].second;
- return V;
+/// If \p isTrue is true, return the true value of \p SI, otherwise return
+/// false value of \p SI. If the true/false value of \p SI is defined by any
+/// select instructions in \p Selects, look through the defining select
+/// instruction until the true/false value is not defined in \p Selects.
+static Value *
+getTrueOrFalseValue(SelectOptimizeImpl::SelectLike SI, bool isTrue,
+ const SmallPtrSet<const Instruction *, 2> &Selects,
+ IRBuilder<> &IB) {
+ Value *V = nullptr;
+ for (SelectInst *DefSI = dyn_cast<SelectInst>(SI.getI());
+ DefSI != nullptr && Selects.count(DefSI);
+ DefSI = dyn_cast<SelectInst>(V)) {
+ if (DefSI->getCondition() == SI.getCondition())
+ V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
+ else // Handle inverted SI
+ V = (!isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
}
- auto *BO = cast<BinaryOperator>(SI.getI());
- assert(BO->getOpcode() == Instruction::Or &&
- "Only currently handling Or instructions.");
-
- auto *CBO = BO->clone();
- auto CondIdx = SI.getConditionOpIndex();
- CBO->setOperand(CondIdx, ConstantInt::get(CBO->getType(), 1));
-
- unsigned OtherIdx = 1 - CondIdx;
- if (auto *IV = dyn_cast<Instruction>(CBO->getOperand(OtherIdx))) {
- if (OptSelects.count(IV))
- CBO->setOperand(OtherIdx,
- isTrue ? OptSelects[IV].first : OptSelects[IV].second);
+ if (isa<BinaryOperator>(SI.getI())) {
+ assert(SI.getI()->getOpcode() == Instruction::Or &&
+ "Only currently handling Or instructions.");
+ V = SI.getFalseValue();
+ if (isTrue)
+ V = IB.CreateOr(V, ConstantInt::get(V->getType(), 1));
}
- CBO->insertBefore(B->getTerminator());
- return CBO;
+
+ assert(V && "Failed to get select true/false value");
+ return V;
}
void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
@@ -549,9 +602,7 @@ void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
SmallVector<std::stack<Instruction *>, 2> TrueSlices, FalseSlices;
typedef std::stack<Instruction *>::size_type StackSizeType;
StackSizeType maxTrueSliceLen = 0, maxFalseSliceLen = 0;
- for (SelectLike &SI : ASI.Selects) {
- if (!isa<SelectInst>(SI.getI()))
- continue;
+ for (SelectLike SI : ASI) {
// For each select, compute the sinkable dependence chains of the true and
// false operands.
if (auto *TI = dyn_cast_or_null<Instruction>(SI.getTrueValue())) {
@@ -598,8 +649,8 @@ void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
}
// We split the block containing the select(s) into two blocks.
- SelectLike &SI = ASI.Selects.front();
- SelectLike &LastSI = ASI.Selects.back();
+ SelectLike SI = ASI.front();
+ SelectLike LastSI = ASI.back();
BasicBlock *StartBlock = SI.getI()->getParent();
BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(LastSI.getI()));
// With RemoveDIs turned off, SplitPt can be a dbg.* intrinsic. With
@@ -613,21 +664,19 @@ void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
// Delete the unconditional branch that was just created by the split.
StartBlock->getTerminator()->eraseFromParent();
- // Move any debug/pseudo and auxiliary instructions that were in-between the
+ // Move any debug/pseudo instructions and not's that were in-between the
// select group to the newly-created end block.
SmallVector<Instruction *, 2> SinkInstrs;
auto DIt = SI.getI()->getIterator();
- auto NIt = ASI.Selects.begin();
while (&*DIt != LastSI.getI()) {
- if (NIt != ASI.Selects.end() && &*DIt == NIt->getI())
- ++NIt;
- else
+ if (DIt->isDebugOrPseudoInst())
+ SinkInstrs.push_back(&*DIt);
+ if (match(&*DIt, m_Not(m_Specific(SI.getCondition()))))
SinkInstrs.push_back(&*DIt);
DIt++;
}
- auto InsertionPoint = EndBlock->getFirstInsertionPt();
for (auto *DI : SinkInstrs)
- DI->moveBeforePreserving(&*InsertionPoint);
+ DI->moveBeforePreserving(&*EndBlock->getFirstInsertionPt());
// Duplicate implementation for DbgRecords, the non-instruction debug-info
// format. Helper lambda for moving DbgRecords to the end block.
@@ -651,15 +700,7 @@ void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
// At least one will become an actual new basic block.
BasicBlock *TrueBlock = nullptr, *FalseBlock = nullptr;
BranchInst *TrueBranch = nullptr, *FalseBranch = nullptr;
- // Checks if select-like instruction would materialise on the given branch
- auto HasSelectLike = [](SelectGroup &SG, bool IsTrue) {
- for (auto &SL : SG.Selects) {
- if ((IsTrue ? SL.getTrueValue() : SL.getFalseValue()) == nullptr)
- return true;
- }
- return false;
- };
- if (!TrueSlicesInterleaved.empty() || HasSelectLike(ASI, true)) {
+ if (!TrueSlicesInterleaved.empty()) {
TrueBlock = BasicBlock::Create(EndBlock->getContext(), "select.true.sink",
EndBlock->getParent(), EndBlock);
TrueBranch = BranchInst::Create(EndBlock, TrueBlock);
@@ -667,7 +708,7 @@ void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
for (Instruction *TrueInst : TrueSlicesInterleaved)
TrueInst->moveBefore(TrueBranch);
}
- if (!FalseSlicesInterleaved.empty() || HasSelectLike(ASI, false)) {
+ if (!FalseSlicesInterleaved.empty()) {
FalseBlock =
BasicBlock::Create(EndBlock->getContext(), "select.false.sink",
EndBlock->getParent(), EndBlock);
@@ -707,166 +748,93 @@ void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
FT = FalseBlock;
}
IRBuilder<> IB(SI.getI());
- auto *CondFr =
- IB.CreateFreeze(ASI.Condition, ASI.Condition->getName() + ".frozen");
+ auto *CondFr = IB.CreateFreeze(SI.getCondition(),
+ SI.getCondition()->getName() + ".frozen");
- SmallDenseMap<Instruction *, std::pair<Value *, Value *>, 2> INS;
+ SmallPtrSet<const Instruction *, 2> INS;
+ for (auto SI : ASI)
+ INS.insert(SI.getI());
// Use reverse iterator because later select may use the value of the
// earlier select, and we need to propagate value through earlier select
// to get the PHI operand.
- InsertionPoint = EndBlock->begin();
- for (SelectLike &SI : ASI.Selects) {
+ for (auto It = ASI.rbegin(); It != ASI.rend(); ++It) {
+ SelectLike SI = *It;
// The select itself is replaced with a PHI Node.
PHINode *PN = PHINode::Create(SI.getType(), 2, "");
- PN->insertBefore(InsertionPoint);
+ PN->insertBefore(EndBlock->begin());
PN->takeName(SI.getI());
- // Current instruction might be a condition of some other group, so we
- // need to replace it there to avoid dangling pointer
- if (PN->getType()->isIntegerTy(1)) {
- for (auto &SG : ProfSIGroups) {
- if (SG.Condition == SI.getI())
- SG.Condition = PN;
- }
- }
- SI.getI()->replaceAllUsesWith(PN);
- auto *TV = getTrueOrFalseValue(SI, true, INS, TrueBlock);
- auto *FV = getTrueOrFalseValue(SI, false, INS, FalseBlock);
- INS[PN] = {TV, FV};
- PN->addIncoming(TV, TrueBlock);
- PN->addIncoming(FV, FalseBlock);
+ PN->addIncoming(getTrueOrFalseValue(SI, true, INS, IB), TrueBlock);
+ PN->addIncoming(getTrueOrFalseValue(SI, false, INS, IB), FalseBlock);
PN->setDebugLoc(SI.getI()->getDebugLoc());
+ SI.getI()->replaceAllUsesWith(PN);
+ INS.erase(SI.getI());
++NumSelectsConverted;
}
IB.CreateCondBr(CondFr, TT, FT, SI.getI());
// Remove the old select instructions, now that they are not longer used.
- for (SelectLike &SI : ASI.Selects)
+ for (auto SI : ASI)
SI.getI()->eraseFromParent();
}
}
void SelectOptimizeImpl::collectSelectGroups(BasicBlock &BB,
SelectGroups &SIGroups) {
- // Represents something that can be considered as select instruction.
- // Auxiliary instruction are instructions that depends on a condition and have
- // zero or some constant value on True/False branch, such as:
- // * ZExt(1bit)
- // * Not(1bit)
- struct SelectLikeInfo {
- Value *Cond;
- bool IsAuxiliary;
- bool IsInverted;
- unsigned ConditionIdx;
- };
-
- std::map<Value *, SelectLikeInfo> SelectInfo;
-
- // Check if the instruction is SelectLike or might be part of SelectLike
- // expression, put information into SelectInfo and return the iterator to the
- // inserted position.
- auto ProcessSelectInfo = [&SelectInfo](Instruction *I) {
- Value *Cond;
- if (match(I, m_OneUse(m_ZExt(m_Value(Cond)))) &&
- Cond->getType()->isIntegerTy(1)) {
- bool Inverted = match(Cond, m_Not(m_Value(Cond)));
- return SelectInfo.insert({I, {Cond, true, Inverted, 0}}).first;
- }
-
- if (match(I, m_Not(m_Value(Cond)))) {
- return SelectInfo.insert({I, {Cond, true, true, 0}}).first;
- }
-
- // Select instruction are what we are usually looking for.
- if (match(I, m_Select(m_Value(Cond), m_Value(), m_Value()))) {
- bool Inverted = match(Cond, m_Not(m_Value(Cond)));
- return SelectInfo.insert({I, {Cond, false, Inverted, 0}}).first;
- }
-
- // An Or(zext(i1 X), Y) can also be treated like a select, with condition X
- // and values Y|1 and Y.
- if (auto *BO = dyn_cast<BinaryOperator>(I)) {
- if (BO->getType()->isIntegerTy(1) || BO->getOpcode() != Instruction::Or)
- return SelectInfo.end();
-
- for (unsigned Idx = 0; Idx < 2; Idx++) {
- auto *Op = BO->getOperand(Idx);
- auto It = SelectInfo.find(Op);
- if (It != SelectInfo.end() && It->second.IsAuxiliary)
- return SelectInfo
- .insert({I, {It->second.Cond, false, It->second.IsInverted, Idx}})
- .first;
- }
- }
- return SelectInfo.end();
- };
-
- bool AlreadyProcessed = false;
BasicBlock::iterator BBIt = BB.begin();
- std::map<Value *, SelectLikeInfo>::iterator It;
while (BBIt != BB.end()) {
Instruction *I = &*BBIt++;
- if (I->isDebugOrPseudoInst())
- continue;
-
- if (!AlreadyProcessed)
- It = ProcessSelectInfo(I);
- else
- AlreadyProcessed = false;
-
- if (It == SelectInfo.end() || It->second.IsAuxiliary)
- continue;
-
- if (!TTI->shouldTreatInstructionLikeSelect(I))
- continue;
-
- Value *Cond = It->second.Cond;
- // Vector conditions are not supported.
- if (!Cond->getType()->isIntegerTy(1))
- continue;
+ if (SelectLike SI = SelectLike::match(I)) {
+ if (!TTI->shouldTreatInstructionLikeSelect(I))
+ continue;
- SelectGroup SIGroup{Cond};
- SIGroup.Selects.emplace_back(I, It->second.IsInverted,
- It->second.ConditionIdx);
+ SelectGroup SIGroup;
+ SIGroup.push_back(SI);
+ while (BBIt != BB.end()) {
+ Instruction *NI = &*BBIt;
+ // Debug/pseudo instructions should be skipped and not prevent the
+ // formation of a select group.
+ if (NI->isDebugOrPseudoInst()) {
+ ++BBIt;
+ continue;
+ }
- // If the select type is not supported, no point optimizing it.
- // Instruction selection will take care of it.
- if (!isSelectKindSupported(SIGroup.Selects.front()))
- continue;
+ // Skip not(select(..)), if the not is part of the same select group
+ if (match(NI, m_Not(m_Specific(SI.getCondition())))) {
+ ++BBIt;
+ continue;
+ }
- while (BBIt != BB.end()) {
- Instruction *NI = &*BBIt;
- // Debug/pseudo instructions should be skipped and not prevent the
- // formation of a select group.
- if (NI->isDebugOrPseudoInst()) {
+ // We only allow selects in the same group, not other select-like
+ // instructions.
+ if (!isa<SelectInst>(NI))
+ break;
+
+ SelectLike NSI = SelectLike::match(NI);
+ if (NSI && SI.getCondition() == NSI.getCondition()) {
+ SIGroup.push_back(NSI);
+ } else if (NSI && match(NSI.getCondition(),
+ m_Not(m_Specific(SI.getCondition())))) {
+ NSI.setInverted();
+ SIGroup.push_back(NSI);
+ } else
+ break;
++BBIt;
- continue;
}
- It = ProcessSelectInfo(NI);
- if (It == SelectInfo.end()) {
- AlreadyProcessed = true;
- break;
- }
+ // If the select type is not supported, no point optimizing it.
+ // Instruction selection will take care of it.
+ if (!isSelectKindSupported(SI))
+ continue;
- // Auxiliary with same condition
- auto [CurrCond, IsAux, IsRev, CondIdx] = It->second;
- if (Cond != CurrCond) {
- AlreadyProcessed = true;
- break;
- }
+ LLVM_DEBUG({
+ dbgs() << "New Select group with\n";
+ for (auto SI : SIGroup)
+ dbgs() << " " << *SI.getI() << "\n";
+ });
- if (!IsAux)
- SIGroup.Selects.emplace_back(NI, IsRev, CondIdx);
- ++BBIt;
+ SIGroups.push_back(SIGroup);
}
- LLVM_DEBUG({
- dbgs() << "New Select group (" << SIGroup.Selects.size() << ") with\n";
- for (auto &SI : SIGroup.Selects)
- dbgs() << " " << *SI.getI() << "\n";
- });
-
- SIGroups.push_back(SIGroup);
}
}
@@ -910,13 +878,12 @@ void SelectOptimizeImpl::findProfitableSIGroupsInnerLoops(
// Assuming infinite resources, the cost of a group of instructions is the
// cost of the most expensive instruction of the group.
Scaled64 SelectCost = Scaled64::getZero(), BranchCost = Scaled64::getZero();
- for (SelectLike &SI : ASI.Selects) {
+ for (SelectLike SI : ASI) {
SelectCost = std::max(SelectCost, InstCostMap[SI.getI()].PredCost);
BranchCost = std::max(BranchCost, InstCostMap[SI.getI()].NonPredCost);
}
if (BranchCost < SelectCost) {
- OptimizationRemark OR(DEBUG_TYPE, "SelectOpti",
- ASI.Selects.front().getI());
+ OptimizationRemark OR(DEBUG_TYPE, "SelectOpti", ASI.front().getI());
OR << "Profitable to convert to branch (loop analysis). BranchCost="
<< BranchCost.toString() << ", SelectCost=" << SelectCost.toString()
<< ". ";
@@ -925,7 +892,7 @@ void SelectOptimizeImpl::findProfitableSIGroupsInnerLoops(
ProfSIGroups.push_back(ASI);
} else {
OptimizationRemarkMissed ORmiss(DEBUG_TYPE, "SelectOpti",
- ASI.Selects.front().getI());
+ ASI.front().getI());
ORmiss << "Select is more profitable (loop analysis). BranchCost="
<< BranchCost.toString()
<< ", SelectCost=" << SelectCost.toString() << ". ";
@@ -936,7 +903,7 @@ void SelectOptimizeImpl::findProfitableSIGroupsInnerLoops(
bool SelectOptimizeImpl::isConvertToBranchProfitableBase(
const SelectGroup &ASI) {
- const SelectLike &SI = ASI.Selects.front();
+ SelectLike SI = ASI.front();
LLVM_DEBUG(dbgs() << "Analyzing select group containing " << *SI.getI()
<< "\n");
OptimizationRemark OR(DEBUG_TYPE, "SelectOpti", SI.getI());
@@ -996,14 +963,14 @@ static bool extractBranchWeights(const SelectOptimizeImpl::SelectLike SI,
bool SelectOptimizeImpl::hasExpensiveColdOperand(const SelectGroup &ASI) {
bool ColdOperand = false;
uint64_t TrueWeight, FalseWeight, TotalWeight;
- if (extractBranchWeights(ASI.Selects.front(), TrueWeight, FalseWeight)) {
+ if (extractBranchWeights(ASI.front(), TrueWeight, FalseWeight)) {
uint64_t MinWeight = std::min(TrueWeight, FalseWeight);
TotalWeight = TrueWeight + FalseWeight;
// Is there a path with frequency <ColdOperandThreshold% (default:20%) ?
ColdOperand = TotalWeight * ColdOperandThreshold > 100 * MinWeight;
} else if (PSI->hasProfileSummary()) {
OptimizationRemarkMissed ORmiss(DEBUG_TYPE, "SelectOpti",
- ASI.Selects.front().getI());
+ ASI.front().getI());
ORmiss << "Profile data available but missing branch-weights metadata for "
"select instruction. ";
EmitAndPrintRemark(ORE, ORmiss);
@@ -1012,7 +979,7 @@ bool SelectOptimizeImpl::hasExpensiveColdOperand(const SelectGroup &ASI) {
return false;
// Check if the cold path's dependence slice is expensive for any of the
// selects of the group.
- for (SelectLike SI : ASI.Selects) {
+ for (SelectLike SI : ASI) {
Instruction *ColdI = nullptr;
uint64_t HotWeight;
if (TrueWeight < FalseWeight) {
@@ -1202,8 +1169,7 @@ bool SelectOptimizeImpl::computeLoopCosts(
DenseMap<const Instruction *, CostInfo> &InstCostMap, CostInfo *LoopCost) {
LLVM_DEBUG(dbgs() << "Calculating Latency / IPredCost / INonPredCost of loop "
<< L->getHeader()->getName() << "\n");
- const auto SImap = getSImap(SIGroups);
- const auto SGmap = getSGmap(SIGroups);
+ const auto &SImap = getSImap(SIGroups);
// Compute instruction and loop-critical-path costs across two iterations for
// both predicated and non-predicated version.
const unsigned Iterations = 2;
@@ -1250,14 +1216,13 @@ bool SelectOptimizeImpl::computeLoopCosts(
// MispredictCost = max(MispredictPenalty, CondCost) * MispredictRate
if (SImap.contains(&I)) {
auto SI = SImap.at(&I);
- const auto *SG = SGmap.at(&I);
- Scaled64 TrueOpCost = SI.getOpCostOnBranch(true, InstCostMap, TTI);
- Scaled64 FalseOpCost = SI.getOpCostOnBranch(false, InstCostMap, TTI);
+ Scaled64 TrueOpCost = SI.getTrueOpCost(InstCostMap, TTI);
+ Scaled64 FalseOpCost = SI.getFalseOpCost(InstCostMap, TTI);
Scaled64 PredictedPathCost =
getPredictedPathCost(TrueOpCost, FalseOpCost, SI);
Scaled64 CondCost = Scaled64::getZero();
- if (auto *CI = dyn_cast<Instruction>(SG->Condition))
+ if (auto *CI = dyn_cast<Instruction>(SI.getCondition()))
if (InstCostMap.count(CI))
CondCost = InstCostMap[CI].NonPredCost;
Scaled64 MispredictCost = getMispredictionCost(SI, CondCost);
@@ -1283,20 +1248,11 @@ SmallDenseMap<const Instruction *, SelectOptimizeImpl::SelectLike, 2>
SelectOptimizeImpl::getSImap(const SelectGroups &SIGroups) {
SmallDenseMap<const Instruction *, SelectLike, 2> SImap;
for (const SelectGroup &ASI : SIGroups)
- for (const SelectLike &SI : ASI.Selects)
+ for (SelectLike SI : ASI)
SImap.try_emplace(SI.getI(), SI);
return SImap;
}
-SmallDenseMap<const Instruction *, const SelectOptimizeImpl::SelectGroup *, 2>
-SelectOptimizeImpl::getSGmap(const SelectGroups &SIGroups) {
- SmallDenseMap<const Instruction *, const SelectGroup *, 2> SImap;
- for (const SelectGroup &ASI : SIGroups)
- for (const SelectLike &SI : ASI.Selects)
- SImap.try_emplace(SI.getI(), &ASI);
- return SImap;
-}
-
std::optional<uint64_t>
SelectOptimizeImpl::computeInstCost(const Instruction *I) {
InstructionCost ICost =
@@ -1355,6 +1311,9 @@ SelectOptimizeImpl::getPredictedPathCost(Scaled64 TrueCost, Scaled64 FalseCost,
}
bool SelectOptimizeImpl::isSelectKindSupported(const SelectLike SI) {
+ bool VectorCond = !SI.getCondition()->getType()->isIntegerTy(1);
+ if (VectorCond)
+ return false;
TargetLowering::SelectSupportKind SelectKind;
if (SI.getType()->isVectorTy())
SelectKind = TargetLowering::ScalarCondVectorVal;
generated by cgit v1.1 at 2025-07-20 07:42:50 +0000