Lines Matching full:select
1 //===--- SelectOptimize.cpp - Convert select to branches if profitable ---===//
47 #define DEBUG_TYPE "select-optimize"
50 "Number of select groups considered for conversion to branch");
52 "Number of select groups converted due to expensive cold operand");
54 "Number of select groups converted due to high-predictability");
56 "Number of select groups not converted due to unpredictability");
58 "Number of select groups not converted due to cold basic block");
60 "Number of select groups converted due to loop-level analysis");
75 GainGradientThreshold("select-opti-loop-gradient-gain-threshold",
80 GainCycleThreshold("select-opti-loop-cycle-gain-threshold",
85 "select-opti-loop-relative-gain-threshold",
129 /// select(icmp, X|1, X).
133 /// The select (/or) instruction.
135 /// Whether this select is inverted, "not(cond), FalseVal, TrueVal", as
140 /// Match a select or select-like instruction, returning a SelectLike.
142 // Select instruction are what we are usually looking for.
146 // An Or(zext(i1 X), Y) can also be treated like a select, with condition
160 /// Invert the select by inverting the condition and switching the operands.
193 /// condition of a select or c in `or(zext(c), x)`
221 /// getFalseValue of a select or `x` in `or(zext(c), x)` (which is
222 /// `select(c, x|1, x)`)
243 /// InstCostMap. This may need to be generated for select-like instructions.
268 /// InstCostMap. This may need to be generated for select-like instructions.
288 // Select groups consist of consecutive select instructions with the same
293 // Converts select instructions of a function to conditional jumps when deemed
294 // profitable. Returns true if at least one select was converted.
297 // Heuristics for determining which select instructions can be profitably
304 // Converts to branches the select groups that were deemed
308 // Splits selects of a given basic block into select groups.
311 // Determines for which select groups it is profitable converting to branches
318 // Determines if a select group should be converted to a branch (base
333 // Returns true if the condition of the select is highly predictable.
346 // Returns a set of all the select instructions in the given select groups.
353 // Returns the misprediction cost of a given select when converted to branch.
360 // Returns true if the target architecture supports lowering a given select.
416 // If none of the select types are supported then skip this pass.
450 // If none of the select types are supported then skip this pass.
477 // Determine for which select groups it is profitable converting to branches.
484 // Convert to branches the select groups that were deemed
488 // Code modified if at least one select group was converted.
494 // Collect all the select groups.
504 // Determine for which select groups it is profitable converting to branches.
530 /// select instructions in \p Selects, look through the defining select
554 assert(V && "Failed to get select true/false value");
571 // %sel = select i1 %cmp, i32 %c, i32 %d
577 // br i1 %cmp.frozen, label %select.true, label %select.false
578 // select.true:
579 // br label %select.end
580 // select.false:
581 // br label %select.end
582 // select.end:
583 // %sel = phi i32 [ %c, %select.true ], [ %d, %select.false ]
590 // first branch will point directly to select.end, and the corresponding PHI
595 // operands of the select instructions in the group and can be sunk without
602 // For each select, compute the sinkable dependence chains of the true and
619 // In the case of multiple select instructions in the same group, the order
647 // We split the block containing the select(s) into two blocks.
658 BasicBlock *EndBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
664 // select group to the newly-created end block.
690 // middle" of the select group.
700 TrueBlock = BasicBlock::Create(EndBlock->getContext(), "select.true.sink",
709 BasicBlock::Create(EndBlock->getContext(), "select.false.sink",
720 "Unexpected basic block transform while optimizing select");
722 FalseBlock = BasicBlock::Create(StartBlock->getContext(), "select.false",
754 // Use reverse iterator because later select may use the value of the
755 // earlier select, and we need to propagate value through earlier select
759 // The select itself is replaced with a PHI Node.
772 // Remove the old select instructions, now that they are not longer used.
792 // formation of a select group.
798 // Skip not(select(..)), if the not is part of the same select group
804 // We only allow selects in the same group, not other select-like
821 // If the select type is not supported, no point optimizing it.
827 dbgs() << "New Select group with\n";
855 // For each select group in an inner-most loop,
856 // a branch is more preferable than a select/conditional-move if:
857 // i) conversion to branches for all the select groups of the loop satisfies
860 // ii) the total cost of the select group is cheaper with a branch compared
862 // of a select group is the cost of its most expensive select instruction
892 ORmiss << "Select is more profitable (loop analysis). BranchCost="
903 LLVM_DEBUG(dbgs() << "Analyzing select group containing " << *SI.getI()
925 // predictable select is inexpensive in the target architecture.
971 "select instruction. ";
997 // The colder the cold value operand of the select is the more expensive
1013 // modifying memory in-between the load and the select instruction.
1053 // Avoid sinking other select instructions (should be handled separetely).
1107 ORmissL << "No select conversion in the loop due to no reduction of loop's "
1122 ORmissL << "No select conversion in the loop due to small reduction of "
1139 ORmissL << "No select conversion in the loop due to small gradient gain. "
1149 << "No select conversion in the loop due to negative gradient gain. ";
1207 // For a select that can be converted to branch,
1269 // If the select condition is obviously predictable, then the misprediction