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