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.  in match()
146       // An Or(zext(i1 X), Y) can also be treated like a select, with condition  in match()
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.  in run()
450   // If none of the select types are supported then skip this pass.  in runOnFunction()
477   // Determine for which select groups it is profitable converting to branches.  in optimizeSelects()
484   // Convert to branches the select groups that were deemed  in optimizeSelects()
488   // Code modified if at least one select group was converted.  in optimizeSelects()
494   // Collect all the select groups.  in optimizeSelectsBase()
504   // Determine for which select groups it is profitable converting to branches.  in optimizeSelectsBase()
530 /// select instructions in \p Selects, look through the defining select
554   assert(V && "Failed to get select true/false value");  in getTrueOrFalseValue()
571     //       %sel = select i1 %cmp, i32 %c, i32 %d  in convertProfitableSIGroups()
577     //       br i1 %cmp.frozen, label %select.true, label %select.false  in convertProfitableSIGroups()
578     //    select.true:  in convertProfitableSIGroups()
579     //       br label %select.end  in convertProfitableSIGroups()
580     //    select.false:  in convertProfitableSIGroups()
581     //       br label %select.end  in convertProfitableSIGroups()
582     //    select.end:  in convertProfitableSIGroups()
583     //       %sel = phi i32 [ %c, %select.true ], [ %d, %select.false ]  in convertProfitableSIGroups()
590     // first branch will point directly to select.end, and the corresponding PHI  in convertProfitableSIGroups()
595     // operands of the select instructions in the group and can be sunk without  in convertProfitableSIGroups()
602       // For each select, compute the sinkable dependence chains of the true and  in convertProfitableSIGroups()
619     // In the case of multiple select instructions in the same group, the order  in convertProfitableSIGroups()
647     // We split the block containing the select(s) into two blocks.  in convertProfitableSIGroups()
658     BasicBlock *EndBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");  in convertProfitableSIGroups()
664     // select group to the newly-created end block.  in convertProfitableSIGroups()
690     // middle" of the select group.  in convertProfitableSIGroups()
700       TrueBlock = BasicBlock::Create(EndBlock->getContext(), "select.true.sink",  in convertProfitableSIGroups()
709           BasicBlock::Create(EndBlock->getContext(), "select.false.sink",  in convertProfitableSIGroups()
720              "Unexpected basic block transform while optimizing select");  in convertProfitableSIGroups()
722       FalseBlock = BasicBlock::Create(StartBlock->getContext(), "select.false",  in convertProfitableSIGroups()
754     // Use reverse iterator because later select may use the value of the  in convertProfitableSIGroups()
755     // earlier select, and we need to propagate value through earlier select  in convertProfitableSIGroups()
759       // The select itself is replaced with a PHI Node.  in convertProfitableSIGroups()
772     // Remove the old select instructions, now that they are not longer used.  in convertProfitableSIGroups()
792         // formation of a select group.  in collectSelectGroups()
798         // Skip not(select(..)), if the not is part of the same select group  in collectSelectGroups()
804         // We only allow selects in the same group, not other select-like  in collectSelectGroups()
821       // If the select type is not supported, no point optimizing it.  in collectSelectGroups()
827         dbgs() << "New Select group with\n";  in collectSelectGroups()
855   // For each select group in an inner-most loop,  in findProfitableSIGroupsInnerLoops()
856   // a branch is more preferable than a select/conditional-move if:  in findProfitableSIGroupsInnerLoops()
857   // i) conversion to branches for all the select groups of the loop satisfies  in findProfitableSIGroupsInnerLoops()
860   // ii) the total cost of the select group is cheaper with a branch compared  in findProfitableSIGroupsInnerLoops()
862   //     of a select group is the cost of its most expensive select instruction  in findProfitableSIGroupsInnerLoops()
892       ORmiss << "Select is more profitable (loop analysis). BranchCost="  in findProfitableSIGroupsInnerLoops()
903   LLVM_DEBUG(dbgs() << "Analyzing select group containing " << *SI.getI()  in isConvertToBranchProfitableBase()
925   // predictable select is inexpensive in the target architecture.  in isConvertToBranchProfitableBase()
971               "select instruction. ";  in hasExpensiveColdOperand()
997       // The colder the cold value operand of the select is the more expensive  in hasExpensiveColdOperand()
1013 // modifying memory in-between the load and the select instruction.
1053     // Avoid sinking other select instructions (should be handled separetely).  in getExclBackwardsSlice()
1107     ORmissL << "No select conversion in the loop due to no reduction of loop's "  in checkLoopHeuristics()
1122     ORmissL << "No select conversion in the loop due to small reduction of "  in checkLoopHeuristics()
1139       ORmissL << "No select conversion in the loop due to small gradient gain. "  in checkLoopHeuristics()
1149         << "No select conversion in the loop due to negative gradient gain. ";  in checkLoopHeuristics()
1207         // For a select that can be converted to branch,  in computeLoopCosts()
1269   // If the select condition is obviously predictable, then the misprediction  in getMispredictionCost()