42using namespace PatternMatch;
44#define DEBUG_TYPE "lazy-value-info"
55 "Lazy Value Information Analysis",
false,
true)
105 if (
A.isOverdefined())
107 if (
B.isOverdefined())
117 if (!
A.isConstantRange() || !
B.isConstantRange()) {
124 A.getConstantRange().intersectWith(
B.getConstantRange());
128 std::move(Range),
A.isConstantRangeIncludingUndef() ||
129 B.isConstantRangeIncludingUndef());
138 class LazyValueInfoCache;
139 struct LVIValueHandle final :
public CallbackVH {
140 LazyValueInfoCache *Parent;
142 LVIValueHandle(
Value *V, LazyValueInfoCache *
P =
nullptr)
145 void deleted()
override;
146 void allUsesReplacedWith(
Value *V)
override {
157 class LazyValueInfoCache {
162 struct BlockCacheEntry {
167 std::optional<NonNullPointerSet> NonNullPointers;
176 const BlockCacheEntry *getBlockEntry(
BasicBlock *BB)
const {
177 auto It = BlockCache.
find_as(BB);
178 if (It == BlockCache.
end())
180 return It->second.get();
183 BlockCacheEntry *getOrCreateBlockEntry(
BasicBlock *BB) {
184 auto It = BlockCache.
find_as(BB);
185 if (It == BlockCache.
end())
186 It = BlockCache.
insert({ BB, std::make_unique<BlockCacheEntry>() })
189 return It->second.get();
192 void addValueHandle(
Value *Val) {
193 auto HandleIt = ValueHandles.
find_as(Val);
194 if (HandleIt == ValueHandles.
end())
195 ValueHandles.
insert({ Val,
this });
201 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
205 if (
Result.isOverdefined())
206 Entry->OverDefined.insert(Val);
208 Entry->LatticeElements.insert({ Val,
Result });
213 std::optional<ValueLatticeElement>
215 const BlockCacheEntry *Entry = getBlockEntry(BB);
219 if (Entry->OverDefined.count(V))
222 auto LatticeIt = Entry->LatticeElements.find_as(V);
223 if (LatticeIt == Entry->LatticeElements.end())
226 return LatticeIt->second;
229 bool isNonNullAtEndOfBlock(
232 BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
233 if (!Entry->NonNullPointers) {
234 Entry->NonNullPointers = InitFn(BB);
235 for (
Value *V : *Entry->NonNullPointers)
239 return Entry->NonNullPointers->count(V);
245 ValueHandles.
clear();
249 void eraseValue(
Value *V);
262void LazyValueInfoCache::eraseValue(
Value *V) {
263 for (
auto &Pair : BlockCache) {
264 Pair.second->LatticeElements.erase(V);
265 Pair.second->OverDefined.erase(V);
266 if (Pair.second->NonNullPointers)
267 Pair.second->NonNullPointers->erase(V);
270 auto HandleIt = ValueHandles.
find_as(V);
271 if (HandleIt != ValueHandles.
end())
272 ValueHandles.
erase(HandleIt);
275void LVIValueHandle::deleted() {
278 Parent->eraseValue(*
this);
281void LazyValueInfoCache::eraseBlock(
BasicBlock *BB) {
282 BlockCache.erase(BB);
285void LazyValueInfoCache::threadEdgeImpl(
BasicBlock *OldSucc,
297 std::vector<BasicBlock*> worklist;
298 worklist.push_back(OldSucc);
300 const BlockCacheEntry *Entry = getBlockEntry(OldSucc);
301 if (!Entry || Entry->OverDefined.empty())
304 Entry->OverDefined.end());
310 while (!worklist.empty()) {
315 if (ToUpdate == NewSucc)
continue;
318 auto OI = BlockCache.find_as(ToUpdate);
319 if (OI == BlockCache.end() || OI->second->OverDefined.empty())
321 auto &ValueSet = OI->second->OverDefined;
323 bool changed =
false;
324 for (
Value *V : ValsToClear) {
325 if (!ValueSet.erase(V))
333 if (!changed)
continue;
343class LazyValueInfoImpl;
345 LazyValueInfoImpl *LVIImpl;
351 LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L,
DominatorTree &DTree)
352 : LVIImpl(L), DT(DTree) {}
354 void emitBasicBlockStartAnnot(
const BasicBlock *BB,
365class LazyValueInfoImpl {
368 LazyValueInfoCache TheCache;
380 bool pushBlockValue(
const std::pair<BasicBlock *, Value *> &BV) {
381 if (!BlockValueSet.
insert(BV).second)
385 << BV.first->getName() <<
"\n");
397 std::optional<ValueLatticeElement> getBlockValue(
Value *Val,
BasicBlock *BB,
407 std::optional<ValueLatticeElement> solveBlockValueImpl(
Value *Val,
409 std::optional<ValueLatticeElement> solveBlockValueNonLocal(
Value *Val,
411 std::optional<ValueLatticeElement> solveBlockValuePHINode(
PHINode *PN,
413 std::optional<ValueLatticeElement> solveBlockValueSelect(
SelectInst *S,
417 std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
421 std::optional<ValueLatticeElement>
423 std::optional<ValueLatticeElement> solveBlockValueCast(
CastInst *CI,
425 std::optional<ValueLatticeElement>
427 std::optional<ValueLatticeElement> solveBlockValueIntrinsic(
IntrinsicInst *II,
429 std::optional<ValueLatticeElement>
432 void intersectAssumeOrGuardBlockValueConstantRange(
Value *Val,
464 LazyValueInfoAnnotatedWriter Writer(
this, DTree);
465 F.print(OS, &Writer);
471 TheCache.eraseBlock(BB);
480 : AC(AC),
DL(
DL), GuardDecl(GuardDecl) {}
485void LazyValueInfoImpl::solve() {
487 BlockValueStack.
begin(), BlockValueStack.
end());
489 unsigned processedCount = 0;
490 while (!BlockValueStack.
empty()) {
502 dbgs() <<
"Giving up on stack because we are getting too deep\n");
504 while (!StartingStack.empty()) {
505 std::pair<BasicBlock *, Value *> &
e = StartingStack.back();
506 TheCache.insertResult(
e.second,
e.first,
508 StartingStack.pop_back();
510 BlockValueSet.
clear();
511 BlockValueStack.
clear();
514 std::pair<BasicBlock *, Value *>
e = BlockValueStack.
back();
515 assert(BlockValueSet.
count(e) &&
"Stack value should be in BlockValueSet!");
517 if (solveBlockValue(
e.second,
e.first)) {
519 assert(BlockValueStack.
back() == e &&
"Nothing should have been pushed!");
521 std::optional<ValueLatticeElement> BBLV =
522 TheCache.getCachedValueInfo(
e.second,
e.first);
523 assert(BBLV &&
"Result should be in cache!");
525 dbgs() <<
"POP " << *
e.second <<
" in " <<
e.first->getName() <<
" = "
530 BlockValueSet.
erase(e);
533 assert(BlockValueStack.
back() != e &&
"Stack should have been pushed!");
538std::optional<ValueLatticeElement>
542 if (
Constant *VC = dyn_cast<Constant>(Val))
545 if (std::optional<ValueLatticeElement> OptLatticeVal =
546 TheCache.getCachedValueInfo(Val, BB)) {
547 intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);
548 return OptLatticeVal;
552 if (!pushBlockValue({ BB, Val }))
562 case Instruction::Load:
563 case Instruction::Call:
564 case Instruction::Invoke:
566 if (isa<IntegerType>(BBI->
getType())) {
577 assert(!isa<Constant>(Val) &&
"Value should not be constant");
578 assert(!TheCache.getCachedValueInfo(Val, BB) &&
579 "Value should not be in cache");
583 std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
588 TheCache.insertResult(Val, BB, *Res);
592std::optional<ValueLatticeElement>
596 return solveBlockValueNonLocal(Val, BB);
598 if (
PHINode *PN = dyn_cast<PHINode>(BBI))
599 return solveBlockValuePHINode(PN, BB);
601 if (
auto *SI = dyn_cast<SelectInst>(BBI))
602 return solveBlockValueSelect(SI, BB);
618 if (
auto *CI = dyn_cast<CastInst>(BBI))
619 return solveBlockValueCast(CI, BB);
622 return solveBlockValueBinaryOp(BO, BB);
624 if (
auto *EVI = dyn_cast<ExtractValueInst>(BBI))
625 return solveBlockValueExtractValue(EVI, BB);
627 if (
auto *II = dyn_cast<IntrinsicInst>(BBI))
628 return solveBlockValueIntrinsic(II, BB);
632 <<
"' - unknown inst def found.\n");
638 if (
Ptr->getType()->getPointerAddressSpace() == 0)
644 if (
LoadInst *L = dyn_cast<LoadInst>(
I)) {
646 }
else if (
StoreInst *S = dyn_cast<StoreInst>(
I)) {
649 if (
MI->isVolatile())
return;
653 if (!Len || Len->isZero())
return;
661bool LazyValueInfoImpl::isNonNullAtEndOfBlock(
Value *Val,
BasicBlock *BB) {
667 return TheCache.isNonNullAtEndOfBlock(Val, BB, [](
BasicBlock *BB) {
668 NonNullPointerSet NonNullPointers;
671 return NonNullPointers;
675std::optional<ValueLatticeElement>
676LazyValueInfoImpl::solveBlockValueNonLocal(
Value *Val,
BasicBlock *BB) {
682 assert(isa<Argument>(Val) &&
"Unknown live-in to the entry block");
696 std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB);
701 Result.mergeIn(*EdgeResult);
705 if (
Result.isOverdefined()) {
707 <<
"' - overdefined because of pred '"
708 << Pred->getName() <<
"' (non local).\n");
718std::optional<ValueLatticeElement>
731 std::optional<ValueLatticeElement> EdgeResult =
732 getEdgeValue(PhiVal, PhiBB, BB, PN);
737 Result.mergeIn(*EdgeResult);
741 if (
Result.isOverdefined()) {
743 <<
"' - overdefined because of pred (local).\n");
750 assert(!
Result.isOverdefined() &&
"Possible PHI in entry block?");
755 bool isTrueDest =
true);
759void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
761 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
773 auto *
I = cast<CallInst>(AssumeVH);
781 if (GuardDecl && !GuardDecl->
use_empty() &&
796 isNonNullAtEndOfBlock(Val, BB))
805 return ConstantRange::getFull(
DL.getTypeSizeInBits(Ty));
808std::optional<ValueLatticeElement>
811 std::optional<ValueLatticeElement> OptTrueVal =
812 getBlockValue(
SI->getTrueValue(), BB, SI);
817 std::optional<ValueLatticeElement> OptFalseVal =
818 getBlockValue(
SI->getFalseValue(), BB, SI);
834 ((LHS ==
SI->getTrueValue() && RHS ==
SI->getFalseValue()) ||
835 (RHS ==
SI->getTrueValue() && LHS ==
SI->getFalseValue()))) {
841 return TrueCR.
smin(FalseCR);
843 return TrueCR.
umin(FalseCR);
845 return TrueCR.
smax(FalseCR);
847 return TrueCR.
umax(FalseCR);
851 ResultCR,
TrueVal.isConstantRangeIncludingUndef() ||
852 FalseVal.isConstantRangeIncludingUndef());
856 if (LHS ==
SI->getTrueValue())
858 TrueCR.
abs(),
TrueVal.isConstantRangeIncludingUndef());
859 if (LHS ==
SI->getFalseValue())
861 FalseCR.
abs(),
FalseVal.isConstantRangeIncludingUndef());
866 if (LHS ==
SI->getTrueValue())
869 if (LHS ==
SI->getFalseValue())
889std::optional<ConstantRange>
891 std::optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI);
897std::optional<ValueLatticeElement>
908 case Instruction::Trunc:
909 case Instruction::SExt:
910 case Instruction::ZExt:
911 case Instruction::BitCast:
916 <<
"' - overdefined (unknown cast).\n");
923 std::optional<ConstantRange> LHSRes = getRangeFor(CI->
getOperand(0), CI, BB);
938std::optional<ValueLatticeElement>
939LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
947 std::optional<ConstantRange> LHSRes = getRangeFor(
I->getOperand(0),
I, BB);
948 std::optional<ConstantRange> RHSRes = getRangeFor(
I->getOperand(1),
I, BB);
949 if (!LHSRes || !RHSRes)
958std::optional<ValueLatticeElement>
961 "all operands to binary operators are sized");
962 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
963 unsigned NoWrapKind = 0;
964 if (OBO->hasNoUnsignedWrap())
966 if (OBO->hasNoSignedWrap())
969 return solveBlockValueBinaryOpImpl(
976 return solveBlockValueBinaryOpImpl(
982std::optional<ValueLatticeElement>
985 return solveBlockValueBinaryOpImpl(
991std::optional<ValueLatticeElement>
996 <<
"' - unknown intrinsic.\n");
1002 std::optional<ConstantRange>
Range = getRangeFor(Op, II, BB);
1004 return std::nullopt;
1013std::optional<ValueLatticeElement>
1018 return solveBlockValueOverflowIntrinsic(WO, BB);
1025 return getBlockValue(V, BB, EVI);
1028 <<
"' - overdefined (unknown extractvalue).\n");
1073 if (
auto *Ranges =
I->getMetadata(LLVMContext::MD_range))
1090 if (isa<Constant>(
RHS)) {
1094 else if (!isa<UndefValue>(
RHS))
1119 Known.
Zero = ~*
C & *Mask;
1120 Known.
One = *
C & *Mask;
1180 bool isTrueDest = CondVal.
getInt();
1185 if (
auto *EVI = dyn_cast<ExtractValueInst>(
Cond))
1194 auto NV = Visited.
find(NKey);
1195 if (NV == Visited.
end()) {
1197 return std::nullopt;
1218 if ((isTrueDest ^ IsAnd) && (LV != Visited.
end())) {
1222 if (RV != Visited.
end()) {
1228 if (LV == Visited.
end() || RV == Visited.
end()) {
1230 if (LV == Visited.
end())
1232 if (RV == Visited.
end())
1234 return std::nullopt;
1237 return intersect(LV->second, RV->second);
1257 bool isRevisit = !Iter.second;
1259 Val, CurrentCond, isRevisit, Visited, Worklist);
1261 Visited[CurrentCond] = *Result;
1264 }
while (!Worklist.
empty());
1266 auto Result = Visited.
find(CondKey);
1268 return Result->second;
1281 return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
1289 const APInt &OpConstVal,
1294 if (
auto *CI = dyn_cast<CastInst>(Usr)) {
1296 if (
auto *
C = dyn_cast_or_null<ConstantInt>(
1301 }
else if (
auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1304 assert((Op0Match || Op1Match) &&
1305 "Operand 0 nor Operand 1 isn't a match");
1308 if (
auto *
C = dyn_cast_or_null<ConstantInt>(
1312 }
else if (isa<FreezeInst>(Usr)) {
1313 assert(cast<FreezeInst>(Usr)->getOperand(0) == Op &&
"Operand 0 isn't Op");
1330 if (BI->isConditional() &&
1331 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1332 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1333 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1334 "BBTo isn't a successor of BBFrom");
1335 Value *Condition = BI->getCondition();
1339 if (Condition == Val)
1347 if (!Result.isOverdefined())
1350 if (
User *Usr = dyn_cast<User>(Val)) {
1351 assert(Result.isOverdefined() &&
"Result isn't overdefined");
1365 APInt ConditionVal(1, isTrueDest ? 1 : 0);
1375 for (
unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1376 Value *Op = Usr->getOperand(i);
1379 if (std::optional<APInt> OpConst =
1388 if (!Result.isOverdefined())
1396 Value *Condition =
SI->getCondition();
1397 if (!isa<IntegerType>(Val->
getType()))
1398 return std::nullopt;
1399 bool ValUsesConditionAndMayBeFoldable =
false;
1400 if (Condition != Val) {
1402 if (
User *Usr = dyn_cast<User>(Val))
1405 if (!ValUsesConditionAndMayBeFoldable)
1406 return std::nullopt;
1408 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1409 "Condition != Val nor Val doesn't use Condition");
1411 bool DefaultCase =
SI->getDefaultDest() == BBTo;
1415 for (
auto Case :
SI->cases()) {
1416 APInt CaseValue = Case.getCaseValue()->getValue();
1418 if (ValUsesConditionAndMayBeFoldable) {
1419 User *Usr = cast<User>(Val);
1424 return std::nullopt;
1434 if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1436 }
else if (Case.getCaseSuccessor() == BBTo)
1437 EdgesVals = EdgesVals.
unionWith(EdgeVal);
1441 return std::nullopt;
1446std::optional<ValueLatticeElement>
1450 if (
Constant *VC = dyn_cast<Constant>(Val))
1460 std::optional<ValueLatticeElement> OptInBlock =
1463 return std::nullopt;
1474 intersectAssumeOrGuardBlockValueConstantRange(Val,
InBlock, CxtI);
1481 LLVM_DEBUG(
dbgs() <<
"LVI Getting block end value " << *V <<
" at '"
1485 std::optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI);
1488 OptResult = getBlockValue(V, BB, CxtI);
1489 assert(OptResult &&
"Value not available after solving");
1501 if (
auto *
C = dyn_cast<Constant>(V))
1505 if (
auto *
I = dyn_cast<Instruction>(V))
1507 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1516 LLVM_DEBUG(
dbgs() <<
"LVI Getting edge value " << *V <<
" from '"
1520 std::optional<ValueLatticeElement>
Result =
1521 getEdgeValue(V, FromBB, ToBB, CxtI);
1524 Result = getEdgeValue(V, FromBB, ToBB, CxtI);
1525 assert(Result &&
"More work to do after problem solved?");
1534 TheCache.threadEdgeImpl(OldSucc, NewSucc);
1545 assert(M &&
"getCache() called with a null Module");
1547 Function *GuardDecl = M->getFunction(
1549 PImpl =
new LazyValueInfoImpl(AC,
DL, GuardDecl);
1551 return *
static_cast<LazyValueInfoImpl*
>(PImpl);
1555 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1556 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1559 getImpl(Info.PImpl, Info.AC,
F.getParent()).clear();
1578 delete &
getImpl(PImpl, AC,
nullptr);
1601 return LazyValueInfo(&AC, &
F.getParent()->getDataLayout(), &TLI);
1613 if (isa<AllocaInst>(V))
1627 if (Result.isConstant())
1628 return Result.getConstant();
1629 if (Result.isConstantRange()) {
1638 bool UndefAllowed) {
1644 if (Result.isUnknown())
1645 return ConstantRange::getEmpty(Width);
1646 if (Result.isConstantRange(UndefAllowed))
1647 return Result.getConstantRange(UndefAllowed);
1650 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1651 "ConstantInt value must be represented as constantrange");
1652 return ConstantRange::getFull(Width);
1656 bool UndefAllowed) {
1663 const Use *CurrU = &U;
1665 const unsigned MaxUsesToInspect = 3;
1666 for (
unsigned I = 0;
I < MaxUsesToInspect; ++
I) {
1667 std::optional<ValueLatticeElement> CondVal;
1668 auto *CurrI = cast<Instruction>(CurrU->getUser());
1669 if (
auto *
SI = dyn_cast<SelectInst>(CurrI)) {
1670 if (CurrU->getOperandNo() == 1)
1672 else if (CurrU->getOperandNo() == 2)
1674 }
else if (
auto *
PHI = dyn_cast<PHINode>(CurrI)) {
1684 if (CondVal && CondVal->isConstantRange())
1690 if (!CurrI->hasOneUse())
1704 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1706 if (Result.isConstant())
1707 return Result.getConstant();
1708 if (Result.isConstantRange()) {
1723 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1725 if (Result.isUnknown())
1726 return ConstantRange::getEmpty(Width);
1727 if (Result.isConstantRange())
1728 return Result.getConstantRange();
1731 assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1732 "ConstantInt value must be represented as constantrange");
1733 return ConstantRange::getFull(Width);
1743 if (
ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1809 getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI);
1833 :
getImpl(PImpl, AC, M).getValueAt(V, CxtI);
1872 if (
auto *
PHI = dyn_cast<PHINode>(V))
1873 if (
PHI->getParent() == BB) {
1875 for (
unsigned i = 0, e =
PHI->getNumIncomingValues(); i < e; i++) {
1876 Value *Incoming =
PHI->getIncomingValue(i);
1884 Baseline = (i == 0) ? Result
1885 : (Baseline == Result ? Baseline
1897 if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) {
1904 while (++PI != PE) {
1906 if (Ret != Baseline)
1922 bool UseBlockValue) {
1925 if (
auto *
C = dyn_cast<Constant>(
RHS))
1927 if (
auto *
C = dyn_cast<Constant>(
LHS))
1934 if (UseBlockValue) {
1945 M->getDataLayout())) {
1946 if (Res->isNullValue())
1948 if (Res->isOneValue())
1959 .threadEdge(PredBB, OldSucc, NewSucc);
1971 getImpl(PImpl, AC, M).clear();
1977 getImpl(PImpl, AC,
F.getParent()).printLVI(
F, DTree, OS);
1982void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1986 for (
const auto &
Arg :
F->args()) {
1989 if (Result.isUnknown())
1991 OS <<
"; LatticeVal for: '" <<
Arg <<
"' is: " << Result <<
"\n";
1999void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
2002 auto *ParentBB =
I->getParent();
2009 auto printResult = [&](
const BasicBlock *BB) {
2010 if (!BlocksContainingLVI.
insert(BB).second)
2014 OS <<
"; LatticeVal for: '" << *
I <<
"' in BB: '";
2016 OS <<
"' is: " <<
Result <<
"\n";
2019 printResult(ParentBB);
2022 for (
const auto *BBSucc :
successors(ParentBB))
2023 if (DT.dominates(ParentBB, BBSucc))
2024 printResult(BBSucc);
2027 for (
const auto *U :
I->users())
2028 if (
auto *UseI = dyn_cast<Instruction>(U))
2029 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
2030 printResult(UseI->getParent());
2052 dbgs() <<
"LVI for function '" <<
F.getName() <<
"':\n";
2053 auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
2054 auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2055 LVI.printLVI(
F, DTree,
dbgs());
2061char LazyValueInfoPrinter::ID = 0;
2063 "Lazy Value Info Printer Pass",
false,
false)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
SmallVector< MachineOperand, 4 > Cond
block Block Frequency Analysis
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void clear(coro::Shape &Shape)
Given that RA is a live value
This file defines the DenseSet and SmallDenseSet classes.
static bool runOnFunction(Function &F, bool PostInlining)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool isOperationFoldable(User *Usr)
static ValueLatticeElement getValueFromSimpleICmpCondition(CmpInst::Predicate Pred, Value *RHS, const APInt &Offset)
Get value range for a "(Val + Offset) Pred RHS" condition.
static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest=true)
static std::optional< ValueLatticeElement > getValueFromConditionImpl(Value *Val, CondValue CondVal, bool isRevisit, SmallDenseMap< CondValue, ValueLatticeElement > &Visited, SmallVectorImpl< CondValue > &Worklist)
static void AddNonNullPointersByInstruction(Instruction *I, NonNullPointerSet &PtrSet)
static bool hasSingleValue(const ValueLatticeElement &Val)
Returns true if this lattice value represents at most one possible value.
static const unsigned MaxProcessedPerValue
static LazyValueInfoImpl & getImpl(void *&PImpl, AssumptionCache *AC, const Module *M)
This lazily constructs the LazyValueInfoImpl.
static std::optional< ValueLatticeElement > getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo)
Compute the value of Val on the edge BBFrom -> BBTo.
static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest)
static bool usesOperand(User *Usr, Value *Op)
static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, const APInt &OpConstVal, const DataLayout &DL)
static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet)
static ValueLatticeElement getFromRangeMetadata(Instruction *BBI)
static ValueLatticeElement intersect(const ValueLatticeElement &A, const ValueLatticeElement &B)
Combine two sets of facts about the same value into a single set of facts.
static ConstantRange getConstantRangeOrFull(const ValueLatticeElement &Val, Type *Ty, const DataLayout &DL)
static ValueLatticeElement getValueFromOverflowCondition(Value *Val, WithOverflowInst *WO, bool IsTrueDest)
static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val, const DataLayout &DL, TargetLibraryInfo *TLI)
static bool isKnownNonConstant(Value *V)
Returns true if we can statically tell that this value will never be a "useful" constant.
PointerIntPair< Value *, 1, bool > CondValue
static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, ICmpInst::Predicate Pred)
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool InBlock(const Value *V, const BasicBlock *BB)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
This class represents an incoming formal argument to a Function.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
const Instruction & back() const
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
Conditional or Unconditional Branch instruction.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Value handle with callbacks on RAUW and destruction.
This is the base class for all instructions that perform data casts.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Type * getDestTy() const
Return the destination type, as a convenience.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
This is the shared class of boolean and integer constants.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
const APInt & getValue() const
Return the constant as an APInt value reference.
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This class represents a range of values.
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
bool isEmptySet() const
Return true if this set contains no members.
ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind) const
Return a new range representing the possible values resulting from an application of the specified ov...
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
ConstantRange smin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed minimum of a value in thi...
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
static Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Analysis to compute lazy value information.
Result run(Function &F, FunctionAnalysisManager &FAM)
Wrapper around LazyValueInfo.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
LazyValueInfoWrapperPass()
This pass computes, caches, and vends lazy value constraint information.
ConstantRange getConstantRangeAtUse(const Use &U, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the value at a specific use-site.
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)
Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...
Tristate
This is used to return true/false/dunno results.
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
void clear(const Module *M)
Complete flush all previously computed values.
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS)
Print the \LazyValueInfo Analysis.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed=true)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
An instruction for reading from memory.
This is the common base class for memset/memcpy/memmove.
This class wraps the llvm.memcpy/memmove intrinsics.
A Module instance is used to store all the information related to an LLVM module.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
PointerIntPair - This class implements a pair of a pointer and small integer.
PointerTy getPointer() const
A set of analyses that are preserved following a run of a transformation pass.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
Value * getOperand(unsigned i) const
This class represents lattice values for constants.
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
bool isOverdefined() const
Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
static ValueLatticeElement getNot(Constant *C)
bool isNotConstant() const
std::optional< APInt > asConstantInteger() const
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
static ValueLatticeElement get(Constant *C)
Constant * getNotConstant() const
Constant * getConstant() const
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
static ValueLatticeElement getOverdefined()
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
LLVMContext & getContext() const
All values hold a context through their type.
StringRef getName() const
Return a constant reference to the value's name.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive,...
bool erase(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
An efficient, type-erasing, non-owning reference to a callable.
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Solution solve(PBQPRAGraph &G)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
This is an optimization pass for GlobalISel generic memory operations.
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
void initializeLazyValueInfoPrinterPass(PassRegistry &)
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
FunctionPass * createLazyValueInfoPass()
createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass.
Interval::pred_iterator pred_end(Interval *I)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
@ SPF_ABS
Floating point maxnum.
@ SPF_NABS
Absolute value.
@ SPF_UMIN
Signed minimum.
@ SPF_UMAX
Signed maximum.
@ SPF_SMAX
Unsigned minimum.
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Value * simplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an ExtractValueInst, fold the result or return null.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
void initializeLazyValueInfoWrapperPassPass(PassRegistry &)
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
A special type used by analysis passes to provide an address that identifies that particular analysis...
SelectPatternFlavor Flavor
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?