merge_conditional_branches.go

     1  // Copyright 2025 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ssa
     6  
     7  import (
     8  	"cmd/compile/internal/types"
     9  )
    10  
    11  const (
    12  	InvalidIndex            = -1 + iota
    13  	TrueConditionSuccIndex  // Index for true condition successor in block's successor list
    14  	FalseConditionSuccIndex // Index for false condition successor in block's successor list
    15  )
    16  
    17  // mergeConditionalBranches performs if-conversion optimization on ARM64 by
    18  // transforming nested conditional branches into conditional comparison instructions.
    19  //
    20  // The optimization detects patterns where two consecutive conditional branches
    21  // implement logical AND/OR operations and replaces them with CCMP/CCMN instructions
    22  // that execute the second conditionally based on the first comparison result.
    23  //
    24  // Transformation Pattern:
    25  //
    26  // Original CFG:
    27  //
    28  //	  if1 (outer condition)
    29  //	  /  \
    30  //	 /    \
    31  //	/      if2 (inner condition)
    32  //	|     /   \
    33  //	|    /     \
    34  //	|   /       \
    35  //	b1 (common)  b2 (target)
    36  //
    37  // Transformed CFG:
    38  //
    39  //	 new_if (conditional comparison)
    40  //	  /   \
    41  //	 /     \
    42  //	/        p (empty plain block)
    43  //	|         \
    44  //	|          \
    45  //	|           \
    46  //	b1 (common)  b2 (target)
    47  //
    48  // Transformation Conditions:
    49  // - Both if1 and if2 must be ARM64 conditional blocks
    50  // - if2 must have exactly one predecessor from if1
    51  // - if2 must not contain memory operations or side effects
    52  // - The transformation must preserve phi node consistency in successor blocks
    53  //
    54  // This optimization eliminates branch mispredictions and improves instruction-level
    55  // parallelism by leveraging ARM64's conditional execution capabilities.
    56  // The resulting code uses conditional comparison instructions that test the second
    57  // condition only if the first condition evaluates to a specific value.
    58  func mergeConditionalBranches(f *Func) {
    59  	if f.Config.arch != "arm64" {
    60  		return
    61  	}
    62  
    63  	// We iterate in postorder to ensure we process inner conditional blocks before
    64  	// their outer counterparts. This is crucial because:
    65  	// 1. Transformations create new conditional comparisons that combine inner and outer conditions
    66  	// 2. Processing inner blocks first ensures we don't miss nested patterns
    67  	// 3. It maintains the integrity of the CFG during transformations
    68  	// Reverse order (from leaves to root) allows safe modification without affecting
    69  	// yet-to-be-processed outer structures.
    70  	blocks := f.postorder()
    71  
    72  	for _, block := range blocks {
    73  		// outerSuccIndex: index of the outedge from if1 to if2
    74  		// innerSuccIndex: index of the outedge from if2 to b2
    75  		outerSuccIndex, innerSuccIndex := detectNestedIfPattern(block)
    76  
    77  		if outerSuccIndex != InvalidIndex && innerSuccIndex != InvalidIndex {
    78  			transformNestedIfPattern(block, outerSuccIndex, innerSuccIndex)
    79  		}
    80  	}
    81  }
    82  
    83  // findFirstNonEmptyPlainBlock finds the first non-empty block in a chain of empty plain blocks
    84  // starting from the specified child index of the parent block. It skips over empty blocks
    85  // that serve only as pass-through nodes in the control flow graph.
    86  func findFirstNonEmptyPlainBlock(parentBlock *Block, childIndex int) *Block {
    87  	childBlock := parentBlock.Succs[childIndex].Block()
    88  	for isEmptyPlainBlock(childBlock) {
    89  		childBlock = childBlock.Succs[0].Block()
    90  	}
    91  	return childBlock
    92  }
    93  
    94  // isEmptyPlainBlock checks if a block is empty (contains no values), has exactly one
    95  // predecessor and is of kind BlockPlain. Such blocks are typically
    96  // artifacts of previous optimizations and can be safely removed or bypassed.
    97  func isEmptyPlainBlock(block *Block) bool {
    98  	return block.Kind == BlockPlain &&
    99  		len(block.Values) == 0 &&
   100  		len(block.Preds) == 1
   101  }
   102  
   103  // removeEmptyPlainBlockChain removes a chain of empty plain blocks starting from
   104  // the specified child index of the parent block. It traverses through consecutive
   105  // empty blocks and deletes them from the control flow graph, connecting the parent
   106  // directly to the first non-empty block in the chain.
   107  func removeEmptyPlainBlockChain(parentBlock *Block, childIndex int) *Block {
   108  	childBlock := parentBlock.Succs[childIndex].Block()
   109  	for isEmptyPlainBlock(childBlock) {
   110  		nextBlock := childBlock.Succs[0].Block()
   111  		removeEmptyPlainBlock(childBlock)
   112  		childBlock = nextBlock
   113  	}
   114  	return childBlock
   115  }
   116  
   117  // removeEmptyPlainBlock removes a single empty plain block from the control flow graph.
   118  // It connects the block's predecessor directly to its successor, effectively bypassing
   119  // the empty block, and then marks the block as invalid for future cleanup.
   120  func removeEmptyPlainBlock(block *Block) {
   121  	prevEdge := block.Preds[0]
   122  	nextEdge := block.Succs[0]
   123  
   124  	prevEdge.b.Succs[prevEdge.i] = nextEdge
   125  	nextEdge.b.Preds[nextEdge.i] = prevEdge
   126  
   127  	block.removePred(0)
   128  	block.removeSucc(0)
   129  	block.Reset(BlockInvalid)
   130  }
   131  
   132  // detectNestedIfPattern detects nested if patterns that can be transformed to conditional comparisons.
   133  // It examines the outer block to see if it contains a nested conditional structure that matches
   134  // the pattern for if-conversion. Returns the outer successor index (which branch contains the
   135  // nested condition) and internal successor index (which branch of the nested condition leads to
   136  // the common merge point), or InvalidIndex if no pattern is detected.
   137  func detectNestedIfPattern(outerBlock *Block) (int, int) {
   138  	if !isIfBlock(outerBlock) {
   139  		// outerBlock doesn't contain comparison
   140  		return InvalidIndex, InvalidIndex
   141  	}
   142  
   143  	// Skip empty blocks to find actual conditional targets
   144  	// Empty plain blocks are often inserted by previous optimizations
   145  	thenBlock := findFirstNonEmptyPlainBlock(outerBlock, TrueConditionSuccIndex)
   146  	elseBlock := findFirstNonEmptyPlainBlock(outerBlock, FalseConditionSuccIndex)
   147  	if thenBlock == elseBlock {
   148  		// Both branches lead to the same block, cannot transform
   149  		return InvalidIndex, InvalidIndex
   150  	}
   151  
   152  	// Check for cyclic patterns where a condition refers back to the original block
   153  	if thenBlock == outerBlock {
   154  		// True branch forms a cycle back to outerBlock
   155  		return detectCyclePattern(outerBlock, FalseConditionSuccIndex)
   156  	} else if elseBlock == outerBlock {
   157  		// False branch forms a cycle back to outerBlock
   158  		return detectCyclePattern(outerBlock, TrueConditionSuccIndex)
   159  	}
   160  
   161  	outerSuccIndex := InvalidIndex
   162  
   163  	// Check if the true branch contains a nested conditional that can be moved
   164  	if len(thenBlock.Preds) == 1 &&
   165  		isIfBlock(thenBlock) &&
   166  		canValuesBeMoved(thenBlock) {
   167  		// True branch contains a valid nested condition
   168  		outerSuccIndex = TrueConditionSuccIndex
   169  	} else if len(elseBlock.Preds) == 1 &&
   170  		isIfBlock(elseBlock) &&
   171  		canValuesBeMoved(elseBlock) {
   172  		// False branch contains a valid nested condition
   173  		outerSuccIndex = FalseConditionSuccIndex
   174  	} else {
   175  		// This chain of blocks is not in pattern.
   176  		return InvalidIndex, InvalidIndex
   177  	}
   178  
   179  	// Tree structure:
   180  	//
   181  	//                outerBlock
   182  	//                 /      \
   183  	//                /        \
   184  	//     commonBothBlock   innerBlock
   185  	//                        /     \
   186  	//                       /       \
   187  	//                 thenBlock    elseBlock
   188  	//
   189  	// outerBlock: The outer conditional block being examined
   190  	// innerBlock: The inner conditional block (nested condition)
   191  	// commonBothBlock: The block reached when the outer condition is not met
   192  	// thenBlock/elseBlock: Successors of the inner conditional block
   193  	innerBlock := findFirstNonEmptyPlainBlock(outerBlock, outerSuccIndex)
   194  	commonBothBlock := findFirstNonEmptyPlainBlock(outerBlock, outerSuccIndex^1)
   195  	thenBlock = findFirstNonEmptyPlainBlock(innerBlock, TrueConditionSuccIndex)
   196  	elseBlock = findFirstNonEmptyPlainBlock(innerBlock, FalseConditionSuccIndex)
   197  
   198  	// Determine which inner branch leads to the common merge point
   199  	// This identifies the index to NOT common merge point
   200  	var innerSuccIndex = InvalidIndex
   201  	switch commonBothBlock {
   202  	case elseBlock:
   203  		// Pattern: (if1 && if2) or (!if1 && if2)
   204  		// False branch of if2 leads to commonBothBlock,
   205  		// that means True branch leads to b2 (target)
   206  		innerSuccIndex = TrueConditionSuccIndex
   207  	case thenBlock:
   208  		// Pattern: (if1 && !if2) or (!if1 && !if2)
   209  		// True branch of if2 leads to commonBothBlock,
   210  		// that means False branch leads to b2 (target)
   211  		innerSuccIndex = FalseConditionSuccIndex
   212  	default:
   213  		// No pattern are matched
   214  		return InvalidIndex, InvalidIndex
   215  	}
   216  
   217  	// Critical check: ensure phi nodes in merge blocks have consistent values
   218  	// This guarantees semantic preservation after transformation
   219  	outToCommonIndex := outerSuccIndex ^ 1 // index of the outedge from outerBlock to commonBothBlock
   220  	inToCommonIndex := innerSuccIndex ^ 1  // index of the outedge from innerBlock to commonBothBlock
   221  	if !checkSameValuesInPhiNodes(outerBlock, innerBlock, outToCommonIndex, inToCommonIndex) {
   222  		return InvalidIndex, InvalidIndex
   223  	}
   224  
   225  	return outerSuccIndex, innerSuccIndex
   226  }
   227  
   228  // detectCyclePattern detects cyclic patterns where a conditional block's successor
   229  // refers back to the original block. This handles special cases where the control
   230  // flow forms a loop-like structure that can still be optimized with conditional comparisons.
   231  func detectCyclePattern(outerBlock *Block, outSuccIndex int) (int, int) {
   232  	secondCondBlock := findFirstNonEmptyPlainBlock(outerBlock, outSuccIndex)
   233  
   234  	if len(secondCondBlock.Preds) != 1 ||
   235  		len(secondCondBlock.Succs) != 2 ||
   236  		!isIfBlock(secondCondBlock) ||
   237  		!canValuesBeMoved(secondCondBlock) {
   238  		return InvalidIndex, InvalidIndex
   239  	}
   240  
   241  	thenBlock := findFirstNonEmptyPlainBlock(secondCondBlock, TrueConditionSuccIndex)
   242  	elseBlock := findFirstNonEmptyPlainBlock(secondCondBlock, FalseConditionSuccIndex)
   243  
   244  	if thenBlock == elseBlock {
   245  		// Both branches pointing to same block indicates degenerate case
   246  		return InvalidIndex, InvalidIndex
   247  	}
   248  
   249  	// Check if the cycle connects back to the original block and verify phi consistency
   250  	switch outerBlock {
   251  	case thenBlock:
   252  		// True branch of inner condition leads back to outerBlock
   253  		if !checkSameValuesInPhiNodes(outerBlock, thenBlock, outSuccIndex^1, TrueConditionSuccIndex) {
   254  			return InvalidIndex, InvalidIndex
   255  		}
   256  		return outSuccIndex, FalseConditionSuccIndex
   257  	case elseBlock:
   258  		// False branch of inner condition leads back to outerBlock
   259  		if !checkSameValuesInPhiNodes(outerBlock, elseBlock, outSuccIndex^1, FalseConditionSuccIndex) {
   260  			return InvalidIndex, InvalidIndex
   261  		}
   262  		return outSuccIndex, TrueConditionSuccIndex
   263  	default:
   264  		// Pattern was not found
   265  		return InvalidIndex, InvalidIndex
   266  	}
   267  }
   268  
   269  // checkSameValuesInPhiNodes checks if phi nodes in merge blocks have the same values
   270  // for the given successor indices. This ensures that after transformation, phi nodes
   271  // will receive the correct values from both paths. Returns true if all phi nodes
   272  // have consistent arguments for the specified paths.
   273  func checkSameValuesInPhiNodes(outerBlock, innerBlock *Block, outToCommonIndex, inToCommonIndex int) bool {
   274  	// Skip empty blocks to find actual phi-containing merge blocks
   275  	// Empty blocks don't affect phi nodes but complicate path tracking
   276  	for isEmptyPlainBlock(outerBlock.Succs[outToCommonIndex].Block()) {
   277  		outerBlock = outerBlock.Succs[outToCommonIndex].Block()
   278  		outToCommonIndex = 0 // After empty block, only one path exists
   279  	}
   280  
   281  	for isEmptyPlainBlock(innerBlock.Succs[inToCommonIndex].Block()) {
   282  		innerBlock = innerBlock.Succs[inToCommonIndex].Block()
   283  		inToCommonIndex = 0 // After empty block, only one path exists
   284  	}
   285  
   286  	// Both paths must lead to the same merge block for transformation to be valid
   287  	if outerBlock.Succs[outToCommonIndex].Block() != innerBlock.Succs[inToCommonIndex].Block() {
   288  		panic("checkSameValuesInPhiNodes: paths do not lead to the same merge block - invalid CFG pattern for if-conversion")
   289  	}
   290  
   291  	argIndex1 := outerBlock.Succs[outToCommonIndex].Index()
   292  	argIndex2 := innerBlock.Succs[inToCommonIndex].Index()
   293  
   294  	resultBlock := outerBlock.Succs[outToCommonIndex].Block()
   295  	for _, v := range resultBlock.Values {
   296  		if v.Op != OpPhi {
   297  			continue
   298  		}
   299  
   300  		// If phi arguments from different paths don't match,
   301  		// merging the conditions would produce wrong values
   302  		if v.Args[argIndex1] != v.Args[argIndex2] {
   303  			return false
   304  		}
   305  	}
   306  
   307  	return true
   308  }
   309  
   310  // canValuesBeMoved checks if all values in a block can be safely moved to another block.
   311  // This is necessary because during transformation, values from the inner conditional
   312  // block are moved to the outer block. Values with side effects, memory operations,
   313  // or phi nodes cannot be moved.
   314  func canValuesBeMoved(b *Block) bool {
   315  	for _, v := range b.Values {
   316  		if !canValueBeMoved(v) {
   317  			return false
   318  		}
   319  	}
   320  	return true
   321  }
   322  
   323  // canValueBeMoved checks if a single value can be safely moved to another block.
   324  // Returns false for values that have side effects, are memory operations, phi nodes,
   325  // or nil checks, as moving these could change program semantics.
   326  func canValueBeMoved(v *Value) bool {
   327  	if v.Op == OpPhi {
   328  		return false
   329  	}
   330  	if v.Type.IsMemory() {
   331  		return false
   332  	}
   333  	if v.Op.HasSideEffects() {
   334  		return false
   335  	}
   336  	if opcodeTable[v.Op].nilCheck {
   337  		return false
   338  	}
   339  	if v.MemoryArg() != nil {
   340  		return false
   341  	}
   342  	return true
   343  }
   344  
   345  // isIfBlock checks if a block is a conditional block that can participate in
   346  // if-conversion. This includes all ARM64 conditional block kinds (EQ, NE, LT, etc.)
   347  // and zero/non-zero test blocks (Z, NZ, ZW, NZW).
   348  func isIfBlock(b *Block) bool {
   349  	switch b.Kind {
   350  	case BlockARM64EQ,
   351  		BlockARM64NE,
   352  		BlockARM64LT,
   353  		BlockARM64LE,
   354  		BlockARM64GT,
   355  		BlockARM64GE,
   356  		BlockARM64ULT,
   357  		BlockARM64ULE,
   358  		BlockARM64UGT,
   359  		BlockARM64UGE:
   360  		return isComparisonOperation(b.Controls[0])
   361  	case BlockARM64Z,
   362  		BlockARM64NZ,
   363  		BlockARM64ZW,
   364  		BlockARM64NZW:
   365  		return true
   366  	default:
   367  		return false
   368  	}
   369  }
   370  
   371  // isComparisonOperation checks if a value represents a comparison operation
   372  // that can be used in conditional execution. Also ensures the value has only
   373  // one use to prevent unexpected side effects from transformation.
   374  func isComparisonOperation(value *Value) bool {
   375  	if value.Uses != 1 {
   376  		// This value can be transformed to another value.
   377  		// New value can get another results, not which are expected.
   378  		// That why we need to check this case.
   379  		return false
   380  	}
   381  
   382  	switch value.Op {
   383  	case OpARM64CMP,
   384  		OpARM64CMPconst,
   385  		OpARM64CMN,
   386  		OpARM64CMNconst,
   387  		OpARM64CMPW,
   388  		OpARM64CMPWconst,
   389  		OpARM64CMNW,
   390  		OpARM64CMNWconst:
   391  		return true
   392  	default:
   393  		return false
   394  	}
   395  }
   396  
   397  // transformNestedIfPattern transforms a detected nested if pattern into a
   398  // conditional comparison. This is the main transformation function that
   399  // coordinates all the steps needed to convert the nested conditionals into
   400  // a single conditional comparison instruction.
   401  func transformNestedIfPattern(outerBlock *Block, outSuccIndex, inSuccIndex int) {
   402  	clearPatternFromEmptyPlainBlocks(outerBlock, outSuccIndex)
   403  	innerBlock := outerBlock.Succs[outSuccIndex].Block()
   404  
   405  	// Transform the control flow step by step:
   406  	// 1. Transform primary comparison to standard form if needed
   407  	// 2. Transform dependent comparison to work with conditional execution
   408  	// 3. Convert to conditional comparison operation (CCMP/CCMN)
   409  	// 4. Fix comparisons with constants to use constant forms when possible
   410  	// 5. Set the new control value for the transformed block
   411  	// 6. Move all values from inner block to outer block
   412  	// 7. Eliminate the now-redundant nested block
   413  	transformPrimaryComparisonValue(outerBlock)
   414  	transformDependentComparisonValue(innerBlock)
   415  	transformToConditionalComparisonValue(outerBlock, outSuccIndex, inSuccIndex)
   416  	fixComparisonWithConstant(innerBlock, outSuccIndex)
   417  	setNewControlValue(outerBlock, innerBlock, outSuccIndex, inSuccIndex)
   418  	moveAllValues(outerBlock, innerBlock)
   419  	elimNestedBlock(innerBlock, inSuccIndex)
   420  }
   421  
   422  // clearPatternFromEmptyPlainBlocks removes all empty plain blocks from the
   423  // detected pattern to simplify the control flow graph before transformation.
   424  func clearPatternFromEmptyPlainBlocks(outerBlock *Block, outSuccIndex int) {
   425  	innerBlock := removeEmptyPlainBlockChain(outerBlock, outSuccIndex)
   426  	removeEmptyPlainBlockChain(outerBlock, outSuccIndex^1)
   427  
   428  	removeEmptyPlainBlockChain(innerBlock, TrueConditionSuccIndex)
   429  	removeEmptyPlainBlockChain(innerBlock, FalseConditionSuccIndex)
   430  }
   431  
   432  // moveAllValues moves all values from the source block to the destination block.
   433  // This is used to consolidate the computations from the inner conditional block
   434  // into the outer block as part of the if-conversion process.
   435  func moveAllValues(dest, src *Block) {
   436  	for _, value := range src.Values {
   437  		value.Block = dest
   438  		dest.Values = append(dest.Values, value)
   439  	}
   440  	src.truncateValues(0)
   441  }
   442  
   443  // elimNestedBlock eliminates a nested block that has been incorporated into
   444  // the outer block through if-conversion. It removes the specified successor
   445  // edge and updates phi nodes in the target block to remove the corresponding argument.
   446  func elimNestedBlock(b *Block, index int) {
   447  	removedEdge := b.Succs[index^1]
   448  
   449  	notBothMetBlock := removedEdge.Block()
   450  	i := removedEdge.Index()
   451  
   452  	b.removeSucc(index ^ 1)
   453  	notBothMetBlock.removePred(i)
   454  	for _, v := range notBothMetBlock.Values {
   455  		if v.Op != OpPhi {
   456  			continue
   457  		}
   458  		notBothMetBlock.removePhiArg(v, i)
   459  	}
   460  
   461  	b.Func.invalidateCFG()
   462  	b.Reset(BlockPlain)
   463  	b.Likely = BranchUnknown
   464  }
   465  
   466  // setNewControlValue sets the new control value for the transformed block
   467  // based on the inner block's control value. It also updates the branch
   468  // likelihood based on the original block's branch prediction.
   469  func setNewControlValue(outerBlock, innerBlock *Block, outSuccIndex, inSuccIndex int) {
   470  	outerBlock.resetWithControl(innerBlock.Kind, innerBlock.Controls[0])
   471  	if !isBranchLikelyConsistentWithIndex(outerBlock, outSuccIndex) ||
   472  		!isBranchLikelyConsistentWithIndex(innerBlock, inSuccIndex) {
   473  		outerBlock.Likely = BranchUnknown
   474  	}
   475  }
   476  
   477  // isBranchLikelyConsistentWithIndex checks if the branch likelihood matches the expected
   478  // index. Returns true if the likelihood is consistent with the branch direction.
   479  func isBranchLikelyConsistentWithIndex(b *Block, index int) bool {
   480  	if index == TrueConditionSuccIndex && b.Likely == BranchLikely {
   481  		return true
   482  	} else if index == FalseConditionSuccIndex && b.Likely == BranchUnlikely {
   483  		return true
   484  	}
   485  	return false
   486  }
   487  
   488  // transformPrimaryComparisonValue transforms special block kinds (Z, NZ, ZW, NZW)
   489  // into standard comparison operations. These block kinds test for zero/non-zero
   490  // and need to be converted to explicit comparisons with zero for conditional execution.
   491  func transformPrimaryComparisonValue(block *Block) {
   492  	switch block.Kind {
   493  	case BlockARM64Z:
   494  		arg0 := block.Controls[0]
   495  		controlValue := block.NewValue1I(arg0.Pos, OpARM64CMPconst, types.TypeFlags, 0, arg0)
   496  		block.resetWithControl(BlockARM64EQ, controlValue)
   497  	case BlockARM64NZ:
   498  		arg0 := block.Controls[0]
   499  		controlValue := block.NewValue1I(arg0.Pos, OpARM64CMPconst, types.TypeFlags, 0, arg0)
   500  		block.resetWithControl(BlockARM64NE, controlValue)
   501  	case BlockARM64ZW:
   502  		arg0 := block.Controls[0]
   503  		controlValue := block.NewValue1I(arg0.Pos, OpARM64CMPWconst, types.TypeFlags, 0, arg0)
   504  		block.resetWithControl(BlockARM64EQ, controlValue)
   505  	case BlockARM64NZW:
   506  		arg0 := block.Controls[0]
   507  		controlValue := block.NewValue1I(arg0.Pos, OpARM64CMPWconst, types.TypeFlags, 0, arg0)
   508  		block.resetWithControl(BlockARM64NE, controlValue)
   509  	default:
   510  		return
   511  	}
   512  }
   513  
   514  // transformDependentComparisonValue transforms the comparison in the dependent
   515  // (inner) block to prepare it for conditional execution. This involves converting
   516  // constant comparisons to register comparisons and handling special block kinds.
   517  func transformDependentComparisonValue(block *Block) {
   518  	typ := &block.Func.Config.Types
   519  
   520  	switch block.Kind {
   521  	case BlockARM64EQ,
   522  		BlockARM64NE,
   523  		BlockARM64LT,
   524  		BlockARM64LE,
   525  		BlockARM64GT,
   526  		BlockARM64GE,
   527  		BlockARM64ULT,
   528  		BlockARM64ULE,
   529  		BlockARM64UGT,
   530  		BlockARM64UGE:
   531  		value := block.Controls[0]
   532  
   533  		switch value.Op {
   534  		case OpARM64CMPconst:
   535  			arg0 := value.Args[0]
   536  			auxConstant := auxIntToInt64(value.AuxInt)
   537  			value.reset(OpARM64CMP)
   538  			constantValue := block.Func.constVal(OpARM64MOVDconst, typ.UInt64, auxConstant, true)
   539  			value.AddArg2(arg0, constantValue)
   540  		case OpARM64CMNconst:
   541  			arg0 := value.Args[0]
   542  			auxConstant := auxIntToInt64(value.AuxInt)
   543  			value.reset(OpARM64CMN)
   544  			constantValue := block.Func.constVal(OpARM64MOVDconst, typ.UInt64, auxConstant, true)
   545  			value.AddArg2(arg0, constantValue)
   546  		case OpARM64CMPWconst:
   547  			arg0 := value.Args[0]
   548  			auxConstant := auxIntToInt32(value.AuxInt)
   549  			value.reset(OpARM64CMPW)
   550  			constantValue := block.Func.constVal(OpARM64MOVDconst, typ.UInt64, int64(auxConstant), true)
   551  			value.AddArg2(arg0, constantValue)
   552  		case OpARM64CMNWconst:
   553  			arg0 := value.Args[0]
   554  			auxConstant := auxIntToInt32(value.AuxInt)
   555  			value.reset(OpARM64CMNW)
   556  			constantValue := block.Func.constVal(OpARM64MOVDconst, typ.UInt64, int64(auxConstant), true)
   557  			value.AddArg2(arg0, constantValue)
   558  		default:
   559  			return
   560  		}
   561  	case BlockARM64Z:
   562  		arg0 := block.Controls[0]
   563  		arg1 := block.Func.constVal(OpARM64MOVDconst, typ.UInt64, 0, true)
   564  		comparisonValue := block.NewValue2(arg0.Pos, OpARM64CMP, types.TypeFlags, arg0, arg1)
   565  		block.resetWithControl(BlockARM64EQ, comparisonValue)
   566  	case BlockARM64NZ:
   567  		arg0 := block.Controls[0]
   568  		arg1 := block.Func.constVal(OpARM64MOVDconst, typ.UInt64, 0, true)
   569  		comparisonValue := block.NewValue2(arg0.Pos, OpARM64CMP, types.TypeFlags, arg0, arg1)
   570  		block.resetWithControl(BlockARM64NE, comparisonValue)
   571  	case BlockARM64ZW:
   572  		arg0 := block.Controls[0]
   573  		arg1 := block.Func.constVal(OpARM64MOVDconst, typ.UInt64, 0, true)
   574  		comparisonValue := block.NewValue2(arg0.Pos, OpARM64CMPW, types.TypeFlags, arg0, arg1)
   575  		block.resetWithControl(BlockARM64EQ, comparisonValue)
   576  	case BlockARM64NZW:
   577  		arg0 := block.Controls[0]
   578  		arg1 := block.Func.constVal(OpARM64MOVDconst, typ.UInt64, 0, true)
   579  		comparisonValue := block.NewValue2(arg0.Pos, OpARM64CMPW, types.TypeFlags, arg0, arg1)
   580  		block.resetWithControl(BlockARM64NE, comparisonValue)
   581  	default:
   582  		panic("Wrong block kind")
   583  	}
   584  }
   585  
   586  // fixComparisonWithConstant optimizes conditional comparisons by converting
   587  // them to constant forms when one operand is a small constant. This generates
   588  // more efficient CCMPconst/CCMNconst instructions.
   589  func fixComparisonWithConstant(block *Block, index int) {
   590  	// Helper function to extract 5-bit immediate from int64 constant (0-31 range)
   591  	getImm64 := func(auxInt int64) (uint8, bool) {
   592  		imm := auxIntToInt64(auxInt)
   593  		if imm&^0x1f == 0 {
   594  			return uint8(imm), true
   595  		}
   596  		return 0, false
   597  	}
   598  
   599  	// Helper function to extract 5-bit immediate from int32 constant (0-31 range)
   600  	getImm32 := func(auxInt int64) (uint8, bool) {
   601  		imm := auxIntToInt32(auxInt)
   602  		if imm&^0x1f == 0 {
   603  			return uint8(imm), true
   604  		}
   605  		return 0, false
   606  	}
   607  
   608  	// Helper function to convert conditional comparison to constant form if possible
   609  	// Algorithm: Check if either operand is a small 5-bit constant (0-31). If found:
   610  	// 1. Convert operation to constant form (CCMP -> CCMPconst, etc.)
   611  	// 2. Set the 'ind' flag for immediate mode
   612  	// 3. When constant is first operand (arg0), swap operands and invert condition
   613  	tryConvertToConstForm := func(value *Value, newOp Op, getImm func(int64) (uint8, bool)) {
   614  		params := value.AuxArm64ConditionalParams()
   615  		arg0 := value.Args[0]
   616  		arg1 := value.Args[1]
   617  		arg2 := value.Args[2]
   618  		// Check second operand for small constant
   619  		if arg1.Op == OpARM64MOVDconst {
   620  			if imm, ok := getImm(arg1.AuxInt); ok {
   621  				value.reset(newOp)
   622  				params.constValue = imm
   623  				params.ind = true
   624  				value.AuxInt = arm64ConditionalParamsToAuxInt(params)
   625  				value.AddArg2(arg0, arg2)
   626  				return
   627  			}
   628  		}
   629  
   630  		// Check first operand for small constant
   631  		if arg0.Op == OpARM64MOVDconst {
   632  			if imm, ok := getImm(arg0.AuxInt); ok {
   633  				value.reset(newOp)
   634  				invertConditionsInBlock(block, &params, index)
   635  				params.constValue = imm
   636  				params.ind = true
   637  				value.AuxInt = arm64ConditionalParamsToAuxInt(params)
   638  				value.AddArg2(arg1, arg2)
   639  				return
   640  			}
   641  		}
   642  	}
   643  
   644  	// try to convert control value of block to constant form
   645  	controlValue := block.Controls[0]
   646  	switch controlValue.Op {
   647  	case OpARM64CCMP:
   648  		tryConvertToConstForm(controlValue, OpARM64CCMPconst, getImm64)
   649  	case OpARM64CCMN:
   650  		tryConvertToConstForm(controlValue, OpARM64CCMNconst, getImm64)
   651  	case OpARM64CCMPW:
   652  		tryConvertToConstForm(controlValue, OpARM64CCMPWconst, getImm32)
   653  	case OpARM64CCMNW:
   654  		tryConvertToConstForm(controlValue, OpARM64CCMNWconst, getImm32)
   655  	default:
   656  		return
   657  	}
   658  }
   659  
   660  // invertConditionsInBlock inverts the condition in a block and returns updated
   661  // conditional parameters. This is used when swapping operands in constant
   662  // optimizations to maintain correct semantics.
   663  func invertConditionsInBlock(block *Block, params *arm64ConditionalParams, index int) {
   664  	invertKind := invertBlockKind(block.Kind)
   665  	block.Kind = invertKind
   666  	if index == FalseConditionSuccIndex {
   667  		invertKind = negateBlockKind(invertKind)
   668  	}
   669  	params.nzcv = nzcvByBlockKind(invertKind)
   670  }
   671  
   672  // transformToConditionalComparisonValue transforms the comparison operations
   673  // to conditional comparison operations (CCMP/CCMN). This is the core transformation
   674  // that creates the conditional execution pattern by combining the outer and inner
   675  // conditions into a single conditional comparison instruction.
   676  func transformToConditionalComparisonValue(outerBlock *Block, outSuccIndex, inSuccIndex int) {
   677  	innerBlock := outerBlock.Succs[outSuccIndex].Block()
   678  
   679  	// Adjust block kinds and successors if needed to match expected pattern
   680  	if outSuccIndex != inSuccIndex {
   681  		outerBlock.Kind = negateBlockKind(outerBlock.Kind)
   682  		outerBlock.swapSuccessors()
   683  		outSuccIndex ^= 1
   684  	}
   685  
   686  	outerControl := outerBlock.Controls[0]
   687  	outerKind := outerBlock.Kind
   688  
   689  	innerControl := innerBlock.Controls[0]
   690  	innerKind := innerBlock.Kind
   691  
   692  	// Adjust conditions based on successor index
   693  	if outSuccIndex == FalseConditionSuccIndex {
   694  		outerKind = negateBlockKind(outerKind)
   695  		innerKind = negateBlockKind(innerKind)
   696  	}
   697  
   698  	// Get conditional parameters and transform the operation
   699  	params := createConditionalParamsByBlockKind(outerKind, innerKind)
   700  
   701  	innerControl.AddArg(outerControl)
   702  	innerControl.Op = transformOpToConditionalComparisonOperation(innerControl.Op)
   703  	innerControl.AuxInt = arm64ConditionalParamsToAuxInt(params)
   704  }
   705  
   706  // transformOpToConditionalComparisonOperation maps standard comparison operations
   707  // to their conditional comparison counterparts (e.g., CMP -> CCMP, CMN -> CCMN).
   708  func transformOpToConditionalComparisonOperation(op Op) Op {
   709  	switch op {
   710  	case OpARM64CMP:
   711  		return OpARM64CCMP
   712  	case OpARM64CMN:
   713  		return OpARM64CCMN
   714  	case OpARM64CMPconst:
   715  		return OpARM64CCMPconst
   716  	case OpARM64CMNconst:
   717  		return OpARM64CCMNconst
   718  	case OpARM64CMPW:
   719  		return OpARM64CCMPW
   720  	case OpARM64CMNW:
   721  		return OpARM64CCMNW
   722  	case OpARM64CMPWconst:
   723  		return OpARM64CCMPWconst
   724  	case OpARM64CMNWconst:
   725  		return OpARM64CCMNWconst
   726  	default:
   727  		panic("Incorrect operation")
   728  	}
   729  }
   730  
   731  // createConditionalParamsByBlockKind constructs conditional parameters for ARM64 conditional instructions.
   732  // It combines two block kinds:
   733  // - outerKind specifies the main condition (e.g., LT, GT) to be evaluated.
   734  // - innerKind determines the NZCV flag pattern to be used when the main condition is FALSE.
   735  // The resulting parameters are typically used by conditional comparison operations (CCMP, CCMN).
   736  func createConditionalParamsByBlockKind(outerKind, innerKind BlockKind) arm64ConditionalParams {
   737  	cond := condByBlockKind(outerKind) // the condition code for the primary comparison
   738  	nzcv := nzcvByBlockKind(innerKind) // NZCV flags to apply when the condition is false
   739  	return arm64ConditionalParamsAuxInt(cond, nzcv)
   740  }
   741  
   742  // condByBlockKind maps block kinds to their corresponding condition codes
   743  // for ARM64 conditional execution.
   744  func condByBlockKind(kind BlockKind) Op {
   745  	switch kind {
   746  	case BlockARM64EQ:
   747  		return OpARM64Equal
   748  	case BlockARM64NE:
   749  		return OpARM64NotEqual
   750  	case BlockARM64LT:
   751  		return OpARM64LessThan
   752  	case BlockARM64LE:
   753  		return OpARM64LessEqual
   754  	case BlockARM64GT:
   755  		return OpARM64GreaterThan
   756  	case BlockARM64GE:
   757  		return OpARM64GreaterEqual
   758  	case BlockARM64ULT:
   759  		return OpARM64LessThanU
   760  	case BlockARM64ULE:
   761  		return OpARM64LessEqualU
   762  	case BlockARM64UGT:
   763  		return OpARM64GreaterThanU
   764  	case BlockARM64UGE:
   765  		return OpARM64GreaterEqualU
   766  	default:
   767  		panic("Incorrect kind of Block")
   768  	}
   769  }
   770  
   771  // nzcvByBlockKind returns NZCV flags encoding the *logical opposite* of the specified block condition.
   772  // The returned flags represent the processor state to be used when the primary comparison condition
   773  // evaluates to false.
   774  //
   775  // Each case constructs the flag pattern for the inverse condition:
   776  //
   777  //	EQ -> NE, LT -> GE, GT -> LE, etc.
   778  func nzcvByBlockKind(kind BlockKind) uint8 {
   779  	switch kind {
   780  	case BlockARM64EQ:
   781  		// Encode NE : Z == 0
   782  		return packNZCV(false, false, false, false) // N=0,Z=0,C=0,V=0
   783  	case BlockARM64NE:
   784  		// Encode EQ : Z == 1
   785  		return packNZCV(false, true, false, false) // N=0,Z=1,C=0,V=0
   786  	case BlockARM64LT:
   787  		// Encode GE : N == V
   788  		return packNZCV(false, false, false, false) // N=0,Z=0,C=0,V=0
   789  	case BlockARM64LE:
   790  		// Encode GT : (Z == 0) && (N == V)
   791  		return packNZCV(false, false, false, false) // N=0,Z=0,C=0,V=0
   792  	case BlockARM64GT:
   793  		// Encode LE : (Z == 1) || (N != V)
   794  		return packNZCV(false, true, false, false) // N=0,Z=1,C=0,V=0
   795  	case BlockARM64GE:
   796  		// Encode LT : N != V
   797  		return packNZCV(false, false, false, true) // N=0,Z=0,C=0,V=1
   798  	case BlockARM64ULT:
   799  		// Encode UGE : C == 1
   800  		return packNZCV(false, false, true, false) // N=0,Z=0,C=1,V=0
   801  	case BlockARM64ULE:
   802  		// Encode UGT : (C == 1) && (Z == 0)
   803  		return packNZCV(false, false, true, false) // N=0,Z=0,C=1,V=0
   804  	case BlockARM64UGT:
   805  		// Encode ULE : (C == 0) || (Z == 1)
   806  		return packNZCV(false, false, false, false) // N=0,Z=0,C=0,V=0
   807  	case BlockARM64UGE:
   808  		// Encode ULT : C == 0
   809  		return packNZCV(false, false, false, false) // N=0,Z=0,C=0,V=0
   810  	default:
   811  		panic("Incorrect kind of Block")
   812  	}
   813  }
   814  
   815  // packNZCV packs boolean condition flags into a single byte representing
   816  // the ARM64 NZCV condition flags: Negative, Zero, Carry, Overflow.
   817  func packNZCV(N, Z, C, V bool) uint8 {
   818  	var NZCVFlags uint8 = 0
   819  	if N {
   820  		NZCVFlags |= 1 << 3
   821  	}
   822  	if Z {
   823  		NZCVFlags |= 1 << 2
   824  	}
   825  	if C {
   826  		NZCVFlags |= 1 << 1
   827  	}
   828  	if V {
   829  		NZCVFlags |= 1
   830  	}
   831  	return NZCVFlags
   832  }
   833  
   834  // negateBlockKind returns the logical negation of a block kind
   835  // (e.g., EQ becomes NE, LT becomes GE).
   836  func negateBlockKind(kind BlockKind) BlockKind {
   837  	switch kind {
   838  	case BlockARM64EQ:
   839  		return BlockARM64NE
   840  	case BlockARM64NE:
   841  		return BlockARM64EQ
   842  	case BlockARM64LT:
   843  		return BlockARM64GE
   844  	case BlockARM64LE:
   845  		return BlockARM64GT
   846  	case BlockARM64GT:
   847  		return BlockARM64LE
   848  	case BlockARM64GE:
   849  		return BlockARM64LT
   850  	case BlockARM64ULT:
   851  		return BlockARM64UGE
   852  	case BlockARM64ULE:
   853  		return BlockARM64UGT
   854  	case BlockARM64UGT:
   855  		return BlockARM64ULE
   856  	case BlockARM64UGE:
   857  		return BlockARM64ULT
   858  	default:
   859  		panic("Incorrect kind of Block")
   860  	}
   861  }
   862  
   863  // invertBlockKind inverts the operands of a comparison block kind
   864  // (e.g., LT becomes GT, LE becomes GE).
   865  func invertBlockKind(kind BlockKind) BlockKind {
   866  	switch kind {
   867  	case BlockARM64EQ:
   868  		return BlockARM64EQ
   869  	case BlockARM64NE:
   870  		return BlockARM64NE
   871  	case BlockARM64LT:
   872  		return BlockARM64GT
   873  	case BlockARM64LE:
   874  		return BlockARM64GE
   875  	case BlockARM64GT:
   876  		return BlockARM64LT
   877  	case BlockARM64GE:
   878  		return BlockARM64LE
   879  	case BlockARM64ULT:
   880  		return BlockARM64UGT
   881  	case BlockARM64ULE:
   882  		return BlockARM64UGE
   883  	case BlockARM64UGT:
   884  		return BlockARM64ULT
   885  	case BlockARM64UGE:
   886  		return BlockARM64ULE
   887  	default:
   888  		panic("Incorrect kind of Block")
   889  	}
   890  }
   891
View as plain text