This repository has been archived by the owner on Jan 23, 2023. It is now read-only.
/
lower.cpp
5662 lines (4909 loc) · 212 KB
/
lower.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX XX
XX Lower XX
XX XX
XX Preconditions: XX
XX XX
XX Postconditions (for the nodes currently handled): XX
XX - All operands requiring a register are explicit in the graph XX
XX XX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
*/
#include "jitpch.h"
#ifdef _MSC_VER
#pragma hdrstop
#endif
#ifndef LEGACY_BACKEND // This file is ONLY used for the RyuJIT backend that uses the linear scan register allocator
#include "lower.h"
#if !defined(_TARGET_64BIT_)
#include "decomposelongs.h"
#endif // !defined(_TARGET_64BIT_)
//------------------------------------------------------------------------
// MakeSrcContained: Make "childNode" a contained node
//
// Arguments:
// parentNode - is a non-leaf node that can contain its 'childNode'
// childNode - is an op that will now be contained by its parent.
//
// Notes:
// If 'childNode' it has any existing sources, they will now be sources for the parent.
//
void Lowering::MakeSrcContained(GenTreePtr parentNode, GenTreePtr childNode)
{
assert(!parentNode->OperIsLeaf());
assert(childNode->canBeContained());
childNode->SetContained();
}
//------------------------------------------------------------------------
// CheckImmedAndMakeContained: Checks if the 'childNode' is a containable immediate
// and, if so, makes it contained.
//
// Arguments:
// parentNode - is any non-leaf node
// childNode - is an child op of 'parentNode'
//
// Return value:
// true if we are able to make childNode a contained immediate
//
bool Lowering::CheckImmedAndMakeContained(GenTree* parentNode, GenTree* childNode)
{
assert(!parentNode->OperIsLeaf());
// If childNode is a containable immediate
if (IsContainableImmed(parentNode, childNode))
{
// then make it contained within the parentNode
MakeSrcContained(parentNode, childNode);
return true;
}
return false;
}
//------------------------------------------------------------------------
// IsSafeToContainMem: Checks for conflicts between childNode and parentNode,
// and returns 'true' iff memory operand childNode can be contained in parentNode.
//
// Arguments:
// parentNode - any non-leaf node
// childNode - some node that is an input to `parentNode`
//
// Return value:
// true if it is safe to make childNode a contained memory operand.
//
bool Lowering::IsSafeToContainMem(GenTree* parentNode, GenTree* childNode)
{
m_scratchSideEffects.Clear();
m_scratchSideEffects.AddNode(comp, childNode);
for (GenTree* node = childNode->gtNext; node != parentNode; node = node->gtNext)
{
if (m_scratchSideEffects.InterferesWith(comp, node, false))
{
return false;
}
}
return true;
}
//------------------------------------------------------------------------
// This is the main entry point for Lowering.
GenTree* Lowering::LowerNode(GenTree* node)
{
assert(node != nullptr);
switch (node->gtOper)
{
case GT_IND:
TryCreateAddrMode(LIR::Use(BlockRange(), &node->gtOp.gtOp1, node), true);
ContainCheckIndir(node->AsIndir());
break;
case GT_STOREIND:
TryCreateAddrMode(LIR::Use(BlockRange(), &node->gtOp.gtOp1, node), true);
if (!comp->codeGen->gcInfo.gcIsWriteBarrierAsgNode(node))
{
LowerStoreIndir(node->AsIndir());
}
break;
case GT_ADD:
{
GenTree* afterTransform = LowerAdd(node);
if (afterTransform != nullptr)
{
return afterTransform;
}
__fallthrough;
}
#if !defined(_TARGET_64BIT_)
case GT_ADD_LO:
case GT_ADD_HI:
case GT_SUB_LO:
case GT_SUB_HI:
#endif
case GT_SUB:
case GT_AND:
case GT_OR:
case GT_XOR:
ContainCheckBinary(node->AsOp());
break;
#ifdef _TARGET_XARCH_
case GT_NEG:
// Codegen of this tree node sets ZF and SF flags.
if (!varTypeIsFloating(node))
{
node->gtFlags |= GTF_ZSF_SET;
}
break;
#endif // _TARGET_XARCH_
case GT_MUL:
case GT_MULHI:
#if defined(_TARGET_X86_) && !defined(LEGACY_BACKEND)
case GT_MUL_LONG:
#endif
ContainCheckMul(node->AsOp());
break;
case GT_UDIV:
case GT_UMOD:
if (!LowerUnsignedDivOrMod(node->AsOp()))
{
ContainCheckDivOrMod(node->AsOp());
}
break;
case GT_DIV:
case GT_MOD:
return LowerSignedDivOrMod(node);
case GT_SWITCH:
return LowerSwitch(node);
case GT_CALL:
LowerCall(node);
break;
#ifdef _TARGET_XARCH_
case GT_BT:
case GT_BTC:
case GT_BTR:
case GT_BTS:
ContainCheckBTx(node->AsOp());
break;
#endif
case GT_LT:
case GT_LE:
case GT_GT:
case GT_GE:
case GT_EQ:
case GT_NE:
case GT_TEST_EQ:
case GT_TEST_NE:
case GT_CMP:
LowerCompare(node);
break;
case GT_JTRUE:
ContainCheckJTrue(node->AsOp());
break;
case GT_JMP:
LowerJmpMethod(node);
break;
case GT_RETURN:
LowerRet(node);
break;
case GT_RETURNTRAP:
ContainCheckReturnTrap(node->AsOp());
break;
case GT_CAST:
LowerCast(node);
break;
#ifdef _TARGET_XARCH_
case GT_ARR_BOUNDS_CHECK:
#ifdef FEATURE_SIMD
case GT_SIMD_CHK:
#endif // FEATURE_SIMD
ContainCheckBoundsChk(node->AsBoundsChk());
break;
#endif // _TARGET_XARCH_
case GT_ARR_ELEM:
return LowerArrElem(node);
case GT_ARR_OFFSET:
ContainCheckArrOffset(node->AsArrOffs());
break;
case GT_ROL:
case GT_ROR:
LowerRotate(node);
break;
#ifndef _TARGET_64BIT_
case GT_LSH_HI:
case GT_RSH_LO:
ContainCheckShiftRotate(node->AsOp());
break;
#endif // !_TARGET_64BIT_
case GT_LSH:
case GT_RSH:
case GT_RSZ:
#ifdef _TARGET_XARCH_
LowerShift(node->AsOp());
#else
ContainCheckShiftRotate(node->AsOp());
#endif
break;
case GT_STORE_BLK:
case GT_STORE_OBJ:
case GT_STORE_DYN_BLK:
{
GenTreeBlk* blkNode = node->AsBlk();
TryCreateAddrMode(LIR::Use(BlockRange(), &blkNode->Addr(), blkNode), false);
LowerBlockStore(blkNode);
}
break;
case GT_LCLHEAP:
ContainCheckLclHeap(node->AsOp());
break;
#ifdef _TARGET_XARCH_
case GT_INTRINSIC:
ContainCheckIntrinsic(node->AsOp());
break;
#endif // _TARGET_XARCH_
#ifdef FEATURE_SIMD
case GT_SIMD:
LowerSIMD(node->AsSIMD());
break;
#endif //
case GT_LCL_VAR:
WidenSIMD12IfNecessary(node->AsLclVarCommon());
break;
case GT_STORE_LCL_VAR:
#if defined(_TARGET_AMD64_) && defined(FEATURE_SIMD)
{
GenTreeLclVarCommon* const store = node->AsLclVarCommon();
if ((store->TypeGet() == TYP_SIMD8) != (store->gtOp1->TypeGet() == TYP_SIMD8))
{
GenTreeUnOp* bitcast =
new (comp, GT_BITCAST) GenTreeOp(GT_BITCAST, store->TypeGet(), store->gtOp1, nullptr);
store->gtOp1 = bitcast;
BlockRange().InsertBefore(store, bitcast);
}
}
#endif // _TARGET_AMD64_
WidenSIMD12IfNecessary(node->AsLclVarCommon());
__fallthrough;
case GT_STORE_LCL_FLD:
// TODO-1stClassStructs: Once we remove the requirement that all struct stores
// are block stores (GT_STORE_BLK or GT_STORE_OBJ), here is where we would put the local
// store under a block store if codegen will require it.
if ((node->TypeGet() == TYP_STRUCT) && (node->gtGetOp1()->OperGet() != GT_PHI))
{
#if FEATURE_MULTIREG_RET
GenTree* src = node->gtGetOp1();
assert((src->OperGet() == GT_CALL) && src->AsCall()->HasMultiRegRetVal());
#else // !FEATURE_MULTIREG_RET
assert(!"Unexpected struct local store in Lowering");
#endif // !FEATURE_MULTIREG_RET
}
LowerStoreLoc(node->AsLclVarCommon());
break;
case GT_LOCKADD:
CheckImmedAndMakeContained(node, node->gtOp.gtOp2);
break;
default:
break;
}
return node->gtNext;
}
/** -- Switch Lowering --
* The main idea of switch lowering is to keep transparency of the register requirements of this node
* downstream in LSRA. Given that the switch instruction is inherently a control statement which in the JIT
* is represented as a simple tree node, at the time we actually generate code for it we end up
* generating instructions that actually modify the flow of execution that imposes complicated
* register requirement and lifetimes.
*
* So, for the purpose of LSRA, we want to have a more detailed specification of what a switch node actually
* means and more importantly, which and when do we need a register for each instruction we want to issue
* to correctly allocate them downstream.
*
* For this purpose, this procedure performs switch lowering in two different ways:
*
* a) Represent the switch statement as a zero-index jump table construct. This means that for every destination
* of the switch, we will store this destination in an array of addresses and the code generator will issue
* a data section where this array will live and will emit code that based on the switch index, will indirect and
* jump to the destination specified in the jump table.
*
* For this transformation we introduce a new GT node called GT_SWITCH_TABLE that is a specialization of the switch
* node for jump table based switches.
* The overall structure of a GT_SWITCH_TABLE is:
*
* GT_SWITCH_TABLE
* |_________ localVar (a temporary local that holds the switch index)
* |_________ jumpTable (this is a special node that holds the address of the jump table array)
*
* Now, the way we morph a GT_SWITCH node into this lowered switch table node form is the following:
*
* Input: GT_SWITCH (inside a basic block whose Branch Type is BBJ_SWITCH)
* |_____ expr (an arbitrarily complex GT_NODE that represents the switch index)
*
* This gets transformed into the following statements inside a BBJ_COND basic block (the target would be
* the default case of the switch in case the conditional is evaluated to true).
*
* ----- original block, transformed
* GT_ASG
* |_____ tempLocal (a new temporary local variable used to store the switch index)
* |_____ expr (the index expression)
*
* GT_JTRUE
* |_____ GT_COND
* |_____ GT_GE
* |___ Int_Constant (This constant is the index of the default case
* that happens to be the highest index in the jump table).
* |___ tempLocal (The local variable were we stored the index expression).
*
* ----- new basic block
* GT_SWITCH_TABLE
* |_____ tempLocal
* |_____ jumpTable (a new jump table node that now LSRA can allocate registers for explicitly
* and LinearCodeGen will be responsible to generate downstream).
*
* This way there are no implicit temporaries.
*
* b) For small-sized switches, we will actually morph them into a series of conditionals of the form
* if (case falls into the default){ goto jumpTable[size]; // last entry in the jump table is the default case }
* (For the default case conditional, we'll be constructing the exact same code as the jump table case one).
* else if (case == firstCase){ goto jumpTable[1]; }
* else if (case == secondCase) { goto jumptable[2]; } and so on.
*
* This transformation is of course made in JIT-IR, not downstream to CodeGen level, so this way we no longer
* require internal temporaries to maintain the index we're evaluating plus we're using existing code from
* LinearCodeGen to implement this instead of implement all the control flow constructs using InstrDscs and
* InstrGroups downstream.
*/
GenTree* Lowering::LowerSwitch(GenTree* node)
{
unsigned jumpCnt;
unsigned targetCnt;
BasicBlock** jumpTab;
assert(node->gtOper == GT_SWITCH);
// The first step is to build the default case conditional construct that is
// shared between both kinds of expansion of the switch node.
// To avoid confusion, we'll alias m_block to originalSwitchBB
// that represents the node we're morphing.
BasicBlock* originalSwitchBB = m_block;
LIR::Range& switchBBRange = LIR::AsRange(originalSwitchBB);
// jumpCnt is the number of elements in the jump table array.
// jumpTab is the actual pointer to the jump table array.
// targetCnt is the number of unique targets in the jump table array.
jumpCnt = originalSwitchBB->bbJumpSwt->bbsCount;
jumpTab = originalSwitchBB->bbJumpSwt->bbsDstTab;
targetCnt = originalSwitchBB->NumSucc(comp);
// GT_SWITCH must be a top-level node with no use.
#ifdef DEBUG
{
LIR::Use use;
assert(!switchBBRange.TryGetUse(node, &use));
}
#endif
JITDUMP("Lowering switch BB%02u, %d cases\n", originalSwitchBB->bbNum, jumpCnt);
// Handle a degenerate case: if the switch has only a default case, just convert it
// to an unconditional branch. This should only happen in minopts or with debuggable
// code.
if (targetCnt == 1)
{
JITDUMP("Lowering switch BB%02u: single target; converting to BBJ_ALWAYS\n", originalSwitchBB->bbNum);
noway_assert(comp->opts.MinOpts() || comp->opts.compDbgCode);
if (originalSwitchBB->bbNext == jumpTab[0])
{
originalSwitchBB->bbJumpKind = BBJ_NONE;
originalSwitchBB->bbJumpDest = nullptr;
}
else
{
originalSwitchBB->bbJumpKind = BBJ_ALWAYS;
originalSwitchBB->bbJumpDest = jumpTab[0];
}
// Remove extra predecessor links if there was more than one case.
for (unsigned i = 1; i < jumpCnt; ++i)
{
(void)comp->fgRemoveRefPred(jumpTab[i], originalSwitchBB);
}
// We have to get rid of the GT_SWITCH node but a child might have side effects so just assign
// the result of the child subtree to a temp.
GenTree* rhs = node->gtOp.gtOp1;
unsigned lclNum = comp->lvaGrabTemp(true DEBUGARG("Lowering is creating a new local variable"));
comp->lvaSortAgain = true;
comp->lvaTable[lclNum].lvType = rhs->TypeGet();
comp->lvaTable[lclNum].lvRefCnt = 1;
GenTreeLclVar* store =
new (comp, GT_STORE_LCL_VAR) GenTreeLclVar(GT_STORE_LCL_VAR, rhs->TypeGet(), lclNum, BAD_IL_OFFSET);
store->gtOp1 = rhs;
store->gtFlags = (rhs->gtFlags & GTF_COMMON_MASK);
store->gtFlags |= GTF_VAR_DEF;
switchBBRange.InsertAfter(node, store);
switchBBRange.Remove(node);
return store;
}
noway_assert(jumpCnt >= 2);
// Spill the argument to the switch node into a local so that it can be used later.
unsigned blockWeight = originalSwitchBB->getBBWeight(comp);
LIR::Use use(switchBBRange, &(node->gtOp.gtOp1), node);
ReplaceWithLclVar(use);
// GT_SWITCH(indexExpression) is now two statements:
// 1. a statement containing 'asg' (for temp = indexExpression)
// 2. and a statement with GT_SWITCH(temp)
assert(node->gtOper == GT_SWITCH);
GenTreePtr temp = node->gtOp.gtOp1;
assert(temp->gtOper == GT_LCL_VAR);
unsigned tempLclNum = temp->gtLclVarCommon.gtLclNum;
LclVarDsc* tempVarDsc = comp->lvaTable + tempLclNum;
var_types tempLclType = temp->TypeGet();
BasicBlock* defaultBB = jumpTab[jumpCnt - 1];
BasicBlock* followingBB = originalSwitchBB->bbNext;
/* Is the number of cases right for a test and jump switch? */
const bool fFirstCaseFollows = (followingBB == jumpTab[0]);
const bool fDefaultFollows = (followingBB == defaultBB);
unsigned minSwitchTabJumpCnt = 2; // table is better than just 2 cmp/jcc
// This means really just a single cmp/jcc (aka a simple if/else)
if (fFirstCaseFollows || fDefaultFollows)
{
minSwitchTabJumpCnt++;
}
#if defined(_TARGET_ARM_)
// On ARM for small switch tables we will
// generate a sequence of compare and branch instructions
// because the code to load the base of the switch
// table is huge and hideous due to the relocation... :(
minSwitchTabJumpCnt += 2;
#endif // _TARGET_ARM_
// Once we have the temporary variable, we construct the conditional branch for
// the default case. As stated above, this conditional is being shared between
// both GT_SWITCH lowering code paths.
// This condition is of the form: if (temp > jumpTableLength - 2){ goto jumpTable[jumpTableLength - 1]; }
GenTreePtr gtDefaultCaseCond = comp->gtNewOperNode(GT_GT, TYP_INT, comp->gtNewLclvNode(tempLclNum, tempLclType),
comp->gtNewIconNode(jumpCnt - 2, genActualType(tempLclType)));
// Make sure we perform an unsigned comparison, just in case the switch index in 'temp'
// is now less than zero 0 (that would also hit the default case).
gtDefaultCaseCond->gtFlags |= GTF_UNSIGNED;
/* Increment the lvRefCnt and lvRefCntWtd for temp */
tempVarDsc->incRefCnts(blockWeight, comp);
GenTreePtr gtDefaultCaseJump = comp->gtNewOperNode(GT_JTRUE, TYP_VOID, gtDefaultCaseCond);
gtDefaultCaseJump->gtFlags = node->gtFlags;
LIR::Range condRange = LIR::SeqTree(comp, gtDefaultCaseJump);
switchBBRange.InsertAtEnd(std::move(condRange));
BasicBlock* afterDefaultCondBlock = comp->fgSplitBlockAfterNode(originalSwitchBB, condRange.LastNode());
// afterDefaultCondBlock is now the switch, and all the switch targets have it as a predecessor.
// originalSwitchBB is now a BBJ_NONE, and there is a predecessor edge in afterDefaultCondBlock
// representing the fall-through flow from originalSwitchBB.
assert(originalSwitchBB->bbJumpKind == BBJ_NONE);
assert(originalSwitchBB->bbNext == afterDefaultCondBlock);
assert(afterDefaultCondBlock->bbJumpKind == BBJ_SWITCH);
assert(afterDefaultCondBlock->bbJumpSwt->bbsHasDefault);
assert(afterDefaultCondBlock->isEmpty()); // Nothing here yet.
// The GT_SWITCH code is still in originalSwitchBB (it will be removed later).
// Turn originalSwitchBB into a BBJ_COND.
originalSwitchBB->bbJumpKind = BBJ_COND;
originalSwitchBB->bbJumpDest = jumpTab[jumpCnt - 1];
// Fix the pred for the default case: the default block target still has originalSwitchBB
// as a predecessor, but the fgSplitBlockAfterStatement() moved all predecessors to point
// to afterDefaultCondBlock.
flowList* oldEdge = comp->fgRemoveRefPred(jumpTab[jumpCnt - 1], afterDefaultCondBlock);
comp->fgAddRefPred(jumpTab[jumpCnt - 1], originalSwitchBB, oldEdge);
// If we originally had 2 unique successors, check to see whether there is a unique
// non-default case, in which case we can eliminate the switch altogether.
// Note that the single unique successor case is handled above.
BasicBlock* uniqueSucc = nullptr;
if (targetCnt == 2)
{
uniqueSucc = jumpTab[0];
noway_assert(jumpCnt >= 2);
for (unsigned i = 1; i < jumpCnt - 1; i++)
{
if (jumpTab[i] != uniqueSucc)
{
uniqueSucc = nullptr;
break;
}
}
}
if (uniqueSucc != nullptr)
{
// If the unique successor immediately follows this block, we have nothing to do -
// it will simply fall-through after we remove the switch, below.
// Otherwise, make this a BBJ_ALWAYS.
// Now, fixup the predecessor links to uniqueSucc. In the original jumpTab:
// jumpTab[i-1] was the default target, which we handled above,
// jumpTab[0] is the first target, and we'll leave that predecessor link.
// Remove any additional predecessor links to uniqueSucc.
for (unsigned i = 1; i < jumpCnt - 1; ++i)
{
assert(jumpTab[i] == uniqueSucc);
(void)comp->fgRemoveRefPred(uniqueSucc, afterDefaultCondBlock);
}
if (afterDefaultCondBlock->bbNext == uniqueSucc)
{
afterDefaultCondBlock->bbJumpKind = BBJ_NONE;
afterDefaultCondBlock->bbJumpDest = nullptr;
}
else
{
afterDefaultCondBlock->bbJumpKind = BBJ_ALWAYS;
afterDefaultCondBlock->bbJumpDest = uniqueSucc;
}
}
// If the number of possible destinations is small enough, we proceed to expand the switch
// into a series of conditional branches, otherwise we follow the jump table based switch
// transformation.
else if ((jumpCnt < minSwitchTabJumpCnt) || comp->compStressCompile(Compiler::STRESS_SWITCH_CMP_BR_EXPANSION, 50))
{
// Lower the switch into a series of compare and branch IR trees.
//
// In this case we will morph the node in the following way:
// 1. Generate a JTRUE statement to evaluate the default case. (This happens above.)
// 2. Start splitting the switch basic block into subsequent basic blocks, each of which will contain
// a statement that is responsible for performing a comparison of the table index and conditional
// branch if equal.
JITDUMP("Lowering switch BB%02u: using compare/branch expansion\n", originalSwitchBB->bbNum);
// We'll use 'afterDefaultCondBlock' for the first conditional. After that, we'll add new
// blocks. If we end up not needing it at all (say, if all the non-default cases just fall through),
// we'll delete it.
bool fUsedAfterDefaultCondBlock = false;
BasicBlock* currentBlock = afterDefaultCondBlock;
LIR::Range* currentBBRange = &LIR::AsRange(currentBlock);
// Walk to entries 0 to jumpCnt - 1. If a case target follows, ignore it and let it fall through.
// If no case target follows, the last one doesn't need to be a compare/branch: it can be an
// unconditional branch.
bool fAnyTargetFollows = false;
for (unsigned i = 0; i < jumpCnt - 1; ++i)
{
assert(currentBlock != nullptr);
// Remove the switch from the predecessor list of this case target's block.
// We'll add the proper new predecessor edge later.
flowList* oldEdge = comp->fgRemoveRefPred(jumpTab[i], afterDefaultCondBlock);
if (jumpTab[i] == followingBB)
{
// This case label follows the switch; let it fall through.
fAnyTargetFollows = true;
continue;
}
// We need a block to put in the new compare and/or branch.
// If we haven't used the afterDefaultCondBlock yet, then use that.
if (fUsedAfterDefaultCondBlock)
{
BasicBlock* newBlock = comp->fgNewBBafter(BBJ_NONE, currentBlock, true);
comp->fgAddRefPred(newBlock, currentBlock); // The fall-through predecessor.
currentBlock = newBlock;
currentBBRange = &LIR::AsRange(currentBlock);
}
else
{
assert(currentBlock == afterDefaultCondBlock);
fUsedAfterDefaultCondBlock = true;
}
// We're going to have a branch, either a conditional or unconditional,
// to the target. Set the target.
currentBlock->bbJumpDest = jumpTab[i];
// Wire up the predecessor list for the "branch" case.
comp->fgAddRefPred(jumpTab[i], currentBlock, oldEdge);
if (!fAnyTargetFollows && (i == jumpCnt - 2))
{
// We're processing the last one, and there is no fall through from any case
// to the following block, so we can use an unconditional branch to the final
// case: there is no need to compare against the case index, since it's
// guaranteed to be taken (since the default case was handled first, above).
currentBlock->bbJumpKind = BBJ_ALWAYS;
}
else
{
// Otherwise, it's a conditional branch. Set the branch kind, then add the
// condition statement.
currentBlock->bbJumpKind = BBJ_COND;
// Now, build the conditional statement for the current case that is
// being evaluated:
// GT_JTRUE
// |__ GT_COND
// |____GT_EQ
// |____ (switchIndex) (The temp variable)
// |____ (ICon) (The actual case constant)
GenTreePtr gtCaseCond =
comp->gtNewOperNode(GT_EQ, TYP_INT, comp->gtNewLclvNode(tempLclNum, tempLclType),
comp->gtNewIconNode(i, TYP_INT));
/* Increment the lvRefCnt and lvRefCntWtd for temp */
tempVarDsc->incRefCnts(blockWeight, comp);
GenTreePtr gtCaseBranch = comp->gtNewOperNode(GT_JTRUE, TYP_VOID, gtCaseCond);
LIR::Range caseRange = LIR::SeqTree(comp, gtCaseBranch);
currentBBRange->InsertAtEnd(std::move(caseRange));
}
}
if (fAnyTargetFollows)
{
// There is a fall-through to the following block. In the loop
// above, we deleted all the predecessor edges from the switch.
// In this case, we need to add one back.
comp->fgAddRefPred(currentBlock->bbNext, currentBlock);
}
if (!fUsedAfterDefaultCondBlock)
{
// All the cases were fall-through! We don't need this block.
// Convert it from BBJ_SWITCH to BBJ_NONE and unset the BBF_DONT_REMOVE flag
// so fgRemoveBlock() doesn't complain.
JITDUMP("Lowering switch BB%02u: all switch cases were fall-through\n", originalSwitchBB->bbNum);
assert(currentBlock == afterDefaultCondBlock);
assert(currentBlock->bbJumpKind == BBJ_SWITCH);
currentBlock->bbJumpKind = BBJ_NONE;
currentBlock->bbFlags &= ~BBF_DONT_REMOVE;
comp->fgRemoveBlock(currentBlock, /* unreachable */ false); // It's an empty block.
}
}
else
{
// Lower the switch into an indirect branch using a jump table:
//
// 1. Create the constant for the default case
// 2. Generate a GT_GE condition to compare to the default case
// 3. Generate a GT_JTRUE to jump.
// 4. Load the jump table address into a local (presumably the just
// created constant for GT_SWITCH).
// 5. Create a new node for the lowered switch, this will both generate
// the branch table and also will be responsible for the indirect
// branch.
JITDUMP("Lowering switch BB%02u: using jump table expansion\n", originalSwitchBB->bbNum);
GenTree* switchValue = comp->gtNewLclvNode(tempLclNum, tempLclType);
#ifdef _TARGET_64BIT_
if (tempLclType != TYP_I_IMPL)
{
// Note that the switch value is unsigned so the cast should be unsigned as well.
switchValue = comp->gtNewCastNode(TYP_I_IMPL, switchValue, TYP_U_IMPL);
switchValue->gtFlags |= GTF_UNSIGNED;
}
#endif
GenTreePtr gtTableSwitch =
comp->gtNewOperNode(GT_SWITCH_TABLE, TYP_VOID, switchValue, comp->gtNewJmpTableNode());
/* Increment the lvRefCnt and lvRefCntWtd for temp */
tempVarDsc->incRefCnts(blockWeight, comp);
// this block no longer branches to the default block
afterDefaultCondBlock->bbJumpSwt->removeDefault();
comp->fgInvalidateSwitchDescMapEntry(afterDefaultCondBlock);
LIR::Range& afterDefaultCondBBRange = LIR::AsRange(afterDefaultCondBlock);
afterDefaultCondBBRange.InsertAtEnd(LIR::SeqTree(comp, gtTableSwitch));
}
GenTree* next = node->gtNext;
// Get rid of the GT_SWITCH(temp).
switchBBRange.Remove(node->gtOp.gtOp1);
switchBBRange.Remove(node);
return next;
}
// NOTE: this method deliberately does not update the call arg table. It must only
// be used by NewPutArg and LowerArg; these functions are responsible for updating
// the call arg table as necessary.
void Lowering::ReplaceArgWithPutArgOrCopy(GenTree** argSlot, GenTree* putArgOrCopy)
{
assert(argSlot != nullptr);
assert(*argSlot != nullptr);
assert(putArgOrCopy->OperIsPutArg() || putArgOrCopy->OperIs(GT_COPY));
GenTree* arg = *argSlot;
// Replace the argument with the putarg/copy
*argSlot = putArgOrCopy;
putArgOrCopy->gtOp.gtOp1 = arg;
// Insert the putarg/copy into the block
BlockRange().InsertAfter(arg, putArgOrCopy);
}
//------------------------------------------------------------------------
// NewPutArg: rewrites the tree to put an arg in a register or on the stack.
//
// Arguments:
// call - the call whose arg is being rewritten.
// arg - the arg being rewritten.
// info - the fgArgTabEntry information for the argument.
// type - the type of the argument.
//
// Return Value:
// The new tree that was created to put the arg in the right place
// or the incoming arg if the arg tree was not rewritten.
//
// Assumptions:
// call, arg, and info must be non-null.
//
// Notes:
// For System V systems with native struct passing (i.e. FEATURE_UNIX_AMD64_STRUCT_PASSING defined)
// this method allocates a single GT_PUTARG_REG for 1 eightbyte structs and a GT_FIELD_LIST of two GT_PUTARG_REGs
// for two eightbyte structs.
//
// For STK passed structs the method generates GT_PUTARG_STK tree. For System V systems with native struct passing
// (i.e. FEATURE_UNIX_AMD64_STRUCT_PASSING defined) this method also sets the GC pointers count and the pointers
// layout object, so the codegen of the GT_PUTARG_STK could use this for optimizing copying to the stack by value.
// (using block copy primitives for non GC pointers and a single TARGET_POINTER_SIZE copy with recording GC info.)
//
GenTreePtr Lowering::NewPutArg(GenTreeCall* call, GenTreePtr arg, fgArgTabEntryPtr info, var_types type)
{
assert(call != nullptr);
assert(arg != nullptr);
assert(info != nullptr);
GenTreePtr putArg = nullptr;
bool updateArgTable = true;
bool isOnStack = true;
#ifdef FEATURE_UNIX_AMD64_STRUCT_PASSING
if (varTypeIsStruct(type))
{
isOnStack = !info->structDesc.passedInRegisters;
}
else
{
isOnStack = info->regNum == REG_STK;
}
#else // !FEATURE_UNIX_AMD64_STRUCT_PASSING
isOnStack = info->regNum == REG_STK;
#endif // !FEATURE_UNIX_AMD64_STRUCT_PASSING
#ifdef _TARGET_ARMARCH_
// Mark contained when we pass struct
// GT_FIELD_LIST is always marked conatained when it is generated
if (varTypeIsStruct(type))
{
arg->SetContained();
if ((arg->OperGet() == GT_OBJ) && (arg->AsObj()->Addr()->OperGet() == GT_LCL_VAR_ADDR))
{
MakeSrcContained(arg, arg->AsObj()->Addr());
}
}
#endif
#ifdef _TARGET_ARM_
// Struct can be split into register(s) and stack on ARM
if (info->isSplit)
{
assert(arg->OperGet() == GT_OBJ || arg->OperGet() == GT_FIELD_LIST);
// TODO: Need to check correctness for FastTailCall
if (call->IsFastTailCall())
{
NYI_ARM("lower: struct argument by fast tail call");
}
putArg = new (comp, GT_PUTARG_SPLIT)
GenTreePutArgSplit(arg, info->slotNum PUT_STRUCT_ARG_STK_ONLY_ARG(info->numSlots), info->numRegs,
call->IsFastTailCall(), call);
putArg->gtRegNum = info->regNum;
// If struct argument is morphed to GT_FIELD_LIST node(s),
// we can know GC info by type of each GT_FIELD_LIST node.
// So we skip setting GC Pointer info.
//
GenTreePutArgSplit* argSplit = putArg->AsPutArgSplit();
if (arg->OperGet() == GT_OBJ)
{
BYTE* gcLayout = nullptr;
unsigned numRefs = 0;
GenTreeObj* argObj = arg->AsObj();
if (argObj->IsGCInfoInitialized())
{
gcLayout = argObj->gtGcPtrs;
numRefs = argObj->GetGcPtrCount();
}
else
{
// Set GC Pointer info
gcLayout = new (comp, CMK_Codegen) BYTE[info->numSlots + info->numRegs];
numRefs = comp->info.compCompHnd->getClassGClayout(arg->gtObj.gtClass, gcLayout);
argSplit->setGcPointers(numRefs, gcLayout);
}
// Set type of registers
for (unsigned index = 0; index < info->numRegs; index++)
{
var_types regType = comp->getJitGCType(gcLayout[index]);
argSplit->m_regType[index] = regType;
}
}
else
{
GenTreeFieldList* fieldListPtr = arg->AsFieldList();
for (unsigned index = 0; index < info->numRegs; fieldListPtr = fieldListPtr->Rest(), index++)
{
var_types regType = fieldListPtr->gtGetOp1()->TypeGet();
argSplit->m_regType[index] = regType;
// Clear the register assignments on the fieldList nodes, as these are contained.
fieldListPtr->gtRegNum = REG_NA;
}
}
}
else
#endif // _TARGET_ARM_
{
if (!isOnStack)
{
#if defined(FEATURE_UNIX_AMD64_STRUCT_PASSING)
if (info->isStruct)
{
// The following code makes sure a register passed struct arg is moved to
// the register before the call is made.
// There are two cases (comments added in the code below.)
// 1. The struct is of size one eightbyte:
// In this case a new tree is created that is GT_PUTARG_REG
// with a op1 the original argument.
// 2. The struct is contained in 2 eightbytes:
// in this case the arg comes as a GT_FIELD_LIST of two GT_LCL_FLDs
// - the two eightbytes of the struct.
// The code creates a GT_PUTARG_REG node for each GT_LCL_FLD in the GT_FIELD_LIST
// and splices it in the list with the corresponding original GT_LCL_FLD tree as op1.
assert(info->structDesc.eightByteCount != 0);
if (info->structDesc.eightByteCount == 1)
{
// clang-format off
// Case 1 above: Create a GT_PUTARG_REG node with op1 of the original tree.
//
// Here the IR for this operation:
// lowering call :
// N001(3, 2)[000017] ------ - N---- / --* &lclVar byref V00 loc0
// N003(6, 5)[000052] * --XG------ - / --* indir int
// N004(3, 2)[000046] ------ - N---- + --* &lclVar byref V02 tmp0
// (13, 11)[000070] -- - XG-- - R-- - arg0 in out + 00 / --* storeIndir int
// N009(3, 4)[000054] ------ - N----arg0 in rdi + --* lclFld int V02 tmp0[+0](last use)
// N011(33, 21)[000018] --CXG------ - *call void Test.Foo.test1
//
// args :
// lowering arg : (13, 11)[000070] -- - XG-- - R-- - *storeIndir int
//
// late :
// lowering arg : N009(3, 4)[000054] ------ - N---- * lclFld int V02 tmp0[+0](last use)
// new node is : (3, 4)[000071] ------------ * putarg_reg int RV
//
// after :
// N001(3, 2)[000017] ------ - N---- / --* &lclVar byref V00 loc0
// N003(6, 5)[000052] * --XG------ - / --* indir int
// N004(3, 2)[000046] ------ - N---- + --* &lclVar byref V02 tmp0
// (13, 11)[000070] -- - XG-- - R-- - arg0 in out + 00 / --* storeIndir int
// N009(3, 4)[000054] ------ - N---- | / --* lclFld int V02 tmp0[+0](last use)
// (3, 4)[000071] ------------arg0 in rdi + --* putarg_reg int RV
// N011(33, 21)[000018] --CXG------ - *call void Test.Foo.test1
//
// clang-format on
putArg = comp->gtNewPutArgReg(type, arg, info->regNum);
}
else if (info->structDesc.eightByteCount == 2)
{
// clang-format off
// Case 2 above: Convert the LCL_FLDs to PUTARG_REG
//
// lowering call :
// N001(3, 2) [000025] ------ - N----Source / --* &lclVar byref V01 loc1
// N003(3, 2) [000056] ------ - N----Destination + --* &lclVar byref V03 tmp1
// N006(1, 1) [000058] ------------ + --* const int 16
// N007(12, 12)[000059] - A--G---- - L - arg0 SETUP / --* copyBlk void
// N009(3, 4) [000061] ------ - N----arg0 in rdi + --* lclFld long V03 tmp1[+0]
// N010(3, 4) [000063] ------------arg0 in rsi + --* lclFld long V03 tmp1[+8](last use)
// N014(40, 31)[000026] --CXG------ - *call void Test.Foo.test2
//
// args :
// lowering arg : N007(12, 12)[000059] - A--G---- - L - *copyBlk void
//
// late :
// lowering arg : N012(11, 13)[000065] ------------ * <list> struct
//
// after :
// N001(3, 2)[000025] ------ - N----Source / --* &lclVar byref V01 loc1
// N003(3, 2)[000056] ------ - N----Destination + --* &lclVar byref V03 tmp1
// N006(1, 1)[000058] ------------ + --* const int 16
// N007(12, 12)[000059] - A--G---- - L - arg0 SETUP / --* copyBlk void
// N009(3, 4)[000061] ------ - N---- | / --* lclFld long V03 tmp1[+0]
// (3, 4)[000072] ------------arg0 in rdi + --* putarg_reg long
// N010(3, 4)[000063] ------------ | / --* lclFld long V03 tmp1[+8](last use)
// (3, 4)[000073] ------------arg0 in rsi + --* putarg_reg long
// N014(40, 31)[000026] --CXG------ - *call void Test.Foo.test2
//
// clang-format on
assert(arg->OperGet() == GT_FIELD_LIST);
GenTreeFieldList* fieldListPtr = arg->AsFieldList();
assert(fieldListPtr->IsFieldListHead());