1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
6XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
7XX XX
8XX AssertionProp XX
9XX XX
10XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
11XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
12*/
13
14#include "jitpch.h"
15#ifdef _MSC_VER
16#pragma hdrstop
17#endif
18
19/*****************************************************************************
20 *
21 * Helper passed to Compiler::fgWalkTreePre() to find the Asgn node for optAddCopies()
22 */
23
24/* static */
25Compiler::fgWalkResult Compiler::optAddCopiesCallback(GenTree** pTree, fgWalkData* data)
26{
27 GenTree* tree = *pTree;
28
29 if (tree->OperIs(GT_ASG))
30 {
31 GenTree* op1 = tree->gtOp.gtOp1;
32 Compiler* comp = data->compiler;
33
34 if ((op1->gtOper == GT_LCL_VAR) && (op1->gtLclVarCommon.gtLclNum == comp->optAddCopyLclNum))
35 {
36 comp->optAddCopyAsgnNode = tree;
37 return WALK_ABORT;
38 }
39 }
40 return WALK_CONTINUE;
41}
42
43/*****************************************************************************
44 *
45 * Add new copies before Assertion Prop.
46 */
47
48void Compiler::optAddCopies()
49{
50 unsigned lclNum;
51 LclVarDsc* varDsc;
52
53#ifdef DEBUG
54 if (verbose)
55 {
56 printf("\n*************** In optAddCopies()\n\n");
57 }
58 if (verboseTrees)
59 {
60 printf("Blocks/Trees at start of phase\n");
61 fgDispBasicBlocks(true);
62 }
63#endif
64
65 // Don't add any copies if we have reached the tracking limit.
66 if (lvaHaveManyLocals())
67 {
68 return;
69 }
70
71 for (lclNum = 0, varDsc = lvaTable; lclNum < lvaCount; lclNum++, varDsc++)
72 {
73 var_types typ = varDsc->TypeGet();
74
75 // We only add copies for non temp local variables
76 // that have a single def and that can possibly be enregistered
77
78 if (varDsc->lvIsTemp || !varDsc->lvSingleDef || !varTypeCanReg(typ))
79 {
80 continue;
81 }
82
83 /* For lvNormalizeOnLoad(), we need to add a cast to the copy-assignment
84 like "copyLclNum = int(varDsc)" and optAssertionGen() only
85 tracks simple assignments. The same goes for lvNormalizedOnStore as
86 the cast is generated in fgMorphSmpOpAsg. This boils down to not having
87 a copy until optAssertionGen handles this*/
88 if (varDsc->lvNormalizeOnLoad() || varDsc->lvNormalizeOnStore() || typ == TYP_BOOL)
89 {
90 continue;
91 }
92
93 if (varTypeIsSmall(varDsc->TypeGet()) || typ == TYP_BOOL)
94 {
95 continue;
96 }
97
98 // If locals must be initialized to zero, that initialization counts as a second definition.
99 // VB in particular allows usage of variables not explicitly initialized.
100 // Note that this effectively disables this optimization for all local variables
101 // as C# sets InitLocals all the time starting in Whidbey.
102
103 if (!varDsc->lvIsParam && info.compInitMem)
104 {
105 continue;
106 }
107
108 // On x86 we may want to add a copy for an incoming double parameter
109 // because we can ensure that the copy we make is double aligned
110 // where as we can never ensure the alignment of an incoming double parameter
111 //
112 // On all other platforms we will never need to make a copy
113 // for an incoming double parameter
114
115 bool isFloatParam = false;
116
117#ifdef _TARGET_X86_
118 isFloatParam = varDsc->lvIsParam && varTypeIsFloating(typ);
119#endif
120
121 if (!isFloatParam && !varDsc->lvVolatileHint)
122 {
123 continue;
124 }
125
126 // We don't want to add a copy for a variable that is part of a struct
127 if (varDsc->lvIsStructField)
128 {
129 continue;
130 }
131
132 // We require that the weighted ref count be significant.
133 if (varDsc->lvRefCntWtd() <= (BB_LOOP_WEIGHT * BB_UNITY_WEIGHT / 2))
134 {
135 continue;
136 }
137
138 // For parameters, we only want to add a copy for the heavier-than-average
139 // uses instead of adding a copy to cover every single use.
140 // 'paramImportantUseDom' is the set of blocks that dominate the
141 // heavier-than-average uses of a parameter.
142 // Initial value is all blocks.
143
144 BlockSet paramImportantUseDom(BlockSetOps::MakeFull(this));
145
146 // This will be threshold for determining heavier-than-average uses
147 unsigned paramAvgWtdRefDiv2 = (varDsc->lvRefCntWtd() + varDsc->lvRefCnt() / 2) / (varDsc->lvRefCnt() * 2);
148
149 bool paramFoundImportantUse = false;
150
151#ifdef DEBUG
152 if (verbose)
153 {
154 printf("Trying to add a copy for V%02u %s, avg_wtd = %s\n", lclNum,
155 varDsc->lvIsParam ? "an arg" : "a local", refCntWtd2str(paramAvgWtdRefDiv2));
156 }
157#endif
158
159 //
160 // We must have a ref in a block that is dominated only by the entry block
161 //
162
163 if (BlockSetOps::MayBeUninit(varDsc->lvRefBlks))
164 {
165 // No references
166 continue;
167 }
168
169 bool isDominatedByFirstBB = false;
170
171 BlockSetOps::Iter iter(this, varDsc->lvRefBlks);
172 unsigned bbNum = 0;
173 while (iter.NextElem(&bbNum))
174 {
175 /* Find the block 'bbNum' */
176 BasicBlock* block = fgFirstBB;
177 while (block && (block->bbNum != bbNum))
178 {
179 block = block->bbNext;
180 }
181 noway_assert(block && (block->bbNum == bbNum));
182
183 bool importantUseInBlock = (varDsc->lvIsParam) && (block->getBBWeight(this) > paramAvgWtdRefDiv2);
184 bool isPreHeaderBlock = ((block->bbFlags & BBF_LOOP_PREHEADER) != 0);
185 BlockSet blockDom(BlockSetOps::UninitVal());
186 BlockSet blockDomSub0(BlockSetOps::UninitVal());
187
188 if (block->bbIDom == nullptr && isPreHeaderBlock)
189 {
190 // Loop Preheader blocks that we insert will have a bbDom set that is nullptr
191 // but we can instead use the bNext successor block's dominator information
192 noway_assert(block->bbNext != nullptr);
193 BlockSetOps::AssignNoCopy(this, blockDom, fgGetDominatorSet(block->bbNext));
194 }
195 else
196 {
197 BlockSetOps::AssignNoCopy(this, blockDom, fgGetDominatorSet(block));
198 }
199
200 if (!BlockSetOps::IsEmpty(this, blockDom))
201 {
202 BlockSetOps::Assign(this, blockDomSub0, blockDom);
203 if (isPreHeaderBlock)
204 {
205 // We must clear bbNext block number from the dominator set
206 BlockSetOps::RemoveElemD(this, blockDomSub0, block->bbNext->bbNum);
207 }
208 /* Is this block dominated by fgFirstBB? */
209 if (BlockSetOps::IsMember(this, blockDomSub0, fgFirstBB->bbNum))
210 {
211 isDominatedByFirstBB = true;
212 }
213 }
214
215#ifdef DEBUG
216 if (verbose)
217 {
218 printf(" Referenced in " FMT_BB ", bbWeight is %s", bbNum,
219 refCntWtd2str(block->getBBWeight(this)));
220
221 if (isDominatedByFirstBB)
222 {
223 printf(", which is dominated by BB01");
224 }
225
226 if (importantUseInBlock)
227 {
228 printf(", ImportantUse");
229 }
230
231 printf("\n");
232 }
233#endif
234
235 /* If this is a heavier-than-average block, then track which
236 blocks dominate this use of the parameter. */
237 if (importantUseInBlock)
238 {
239 paramFoundImportantUse = true;
240 BlockSetOps::IntersectionD(this, paramImportantUseDom,
241 blockDomSub0); // Clear blocks that do not dominate
242 }
243 }
244
245 // We should have found at least one heavier-than-averageDiv2 block.
246 if (varDsc->lvIsParam)
247 {
248 if (!paramFoundImportantUse)
249 {
250 continue;
251 }
252 }
253
254 // For us to add a new copy:
255 // we require that we have a floating point parameter
256 // or a lvVolatile variable that is always reached from the first BB
257 // and we have at least one block available in paramImportantUseDom
258 //
259 bool doCopy = (isFloatParam || (isDominatedByFirstBB && varDsc->lvVolatileHint)) &&
260 !BlockSetOps::IsEmpty(this, paramImportantUseDom);
261
262 // Under stress mode we expand the number of candidates
263 // to include parameters of any type
264 // or any variable that is always reached from the first BB
265 //
266 if (compStressCompile(STRESS_GENERIC_VARN, 30))
267 {
268 // Ensure that we preserve the invariants required by the subsequent code.
269 if (varDsc->lvIsParam || isDominatedByFirstBB)
270 {
271 doCopy = true;
272 }
273 }
274
275 if (!doCopy)
276 {
277 continue;
278 }
279
280 GenTree* stmt;
281 unsigned copyLclNum = lvaGrabTemp(false DEBUGARG("optAddCopies"));
282
283 // Because lvaGrabTemp may have reallocated the lvaTable, ensure varDsc
284 // is still in sync with lvaTable[lclNum];
285 varDsc = &lvaTable[lclNum];
286
287 // Set lvType on the new Temp Lcl Var
288 lvaTable[copyLclNum].lvType = typ;
289
290#ifdef DEBUG
291 if (verbose)
292 {
293 printf("\n Finding the best place to insert the assignment V%02i=V%02i\n", copyLclNum, lclNum);
294 }
295#endif
296
297 if (varDsc->lvIsParam)
298 {
299 noway_assert(varDsc->lvDefStmt == nullptr || varDsc->lvIsStructField);
300
301 // Create a new copy assignment tree
302 GenTree* copyAsgn = gtNewTempAssign(copyLclNum, gtNewLclvNode(lclNum, typ));
303
304 /* Find the best block to insert the new assignment */
305 /* We will choose the lowest weighted block, and within */
306 /* those block, the highest numbered block which */
307 /* dominates all the uses of the local variable */
308
309 /* Our default is to use the first block */
310 BasicBlock* bestBlock = fgFirstBB;
311 unsigned bestWeight = bestBlock->getBBWeight(this);
312 BasicBlock* block = bestBlock;
313
314#ifdef DEBUG
315 if (verbose)
316 {
317 printf(" Starting at " FMT_BB ", bbWeight is %s", block->bbNum,
318 refCntWtd2str(block->getBBWeight(this)));
319
320 printf(", bestWeight is %s\n", refCntWtd2str(bestWeight));
321 }
322#endif
323
324 /* We have already calculated paramImportantUseDom above. */
325 BlockSetOps::Iter iter(this, paramImportantUseDom);
326 unsigned bbNum = 0;
327 while (iter.NextElem(&bbNum))
328 {
329 /* Advance block to point to 'bbNum' */
330 /* This assumes that the iterator returns block number is increasing lexical order. */
331 while (block && (block->bbNum != bbNum))
332 {
333 block = block->bbNext;
334 }
335 noway_assert(block && (block->bbNum == bbNum));
336
337#ifdef DEBUG
338 if (verbose)
339 {
340 printf(" Considering " FMT_BB ", bbWeight is %s", block->bbNum,
341 refCntWtd2str(block->getBBWeight(this)));
342
343 printf(", bestWeight is %s\n", refCntWtd2str(bestWeight));
344 }
345#endif
346
347 // Does this block have a smaller bbWeight value?
348 if (block->getBBWeight(this) > bestWeight)
349 {
350#ifdef DEBUG
351 if (verbose)
352 {
353 printf("bbWeight too high\n");
354 }
355#endif
356 continue;
357 }
358
359 // Don't use blocks that are exception handlers because
360 // inserting a new first statement will interface with
361 // the CATCHARG
362
363 if (handlerGetsXcptnObj(block->bbCatchTyp))
364 {
365#ifdef DEBUG
366 if (verbose)
367 {
368 printf("Catch block\n");
369 }
370#endif
371 continue;
372 }
373
374 // Don't use the BBJ_ALWAYS block marked with BBF_KEEP_BBJ_ALWAYS. These
375 // are used by EH code. The JIT can not generate code for such a block.
376
377 if (block->bbFlags & BBF_KEEP_BBJ_ALWAYS)
378 {
379#if FEATURE_EH_FUNCLETS
380 // With funclets, this is only used for BBJ_CALLFINALLY/BBJ_ALWAYS pairs. For x86, it is also used
381 // as the "final step" block for leaving finallys.
382 assert((block->bbPrev != nullptr) && block->bbPrev->isBBCallAlwaysPair());
383#endif // FEATURE_EH_FUNCLETS
384#ifdef DEBUG
385 if (verbose)
386 {
387 printf("Internal EH BBJ_ALWAYS block\n");
388 }
389#endif
390 continue;
391 }
392
393 // This block will be the new candidate for the insert point
394 // for the new assignment
395 CLANG_FORMAT_COMMENT_ANCHOR;
396
397#ifdef DEBUG
398 if (verbose)
399 {
400 printf("new bestBlock\n");
401 }
402#endif
403
404 bestBlock = block;
405 bestWeight = block->getBBWeight(this);
406 }
407
408 // If there is a use of the variable in this block
409 // then we insert the assignment at the beginning
410 // otherwise we insert the statement at the end
411 CLANG_FORMAT_COMMENT_ANCHOR;
412
413#ifdef DEBUG
414 if (verbose)
415 {
416 printf(" Insert copy at the %s of " FMT_BB "\n",
417 (BlockSetOps::IsEmpty(this, paramImportantUseDom) ||
418 BlockSetOps::IsMember(this, varDsc->lvRefBlks, bestBlock->bbNum))
419 ? "start"
420 : "end",
421 bestBlock->bbNum);
422 }
423#endif
424
425 if (BlockSetOps::IsEmpty(this, paramImportantUseDom) ||
426 BlockSetOps::IsMember(this, varDsc->lvRefBlks, bestBlock->bbNum))
427 {
428 stmt = fgInsertStmtAtBeg(bestBlock, copyAsgn);
429 }
430 else
431 {
432 stmt = fgInsertStmtNearEnd(bestBlock, copyAsgn);
433 }
434 }
435 else
436 {
437 noway_assert(varDsc->lvDefStmt != nullptr);
438
439 /* Locate the assignment to varDsc in the lvDefStmt */
440 stmt = varDsc->lvDefStmt;
441 noway_assert(stmt->gtOper == GT_STMT);
442
443 optAddCopyLclNum = lclNum; // in
444 optAddCopyAsgnNode = nullptr; // out
445
446 fgWalkTreePre(&stmt->gtStmt.gtStmtExpr, Compiler::optAddCopiesCallback, (void*)this, false);
447
448 noway_assert(optAddCopyAsgnNode);
449
450 GenTree* tree = optAddCopyAsgnNode;
451 GenTree* op1 = tree->gtOp.gtOp1;
452
453 noway_assert(tree && op1 && tree->OperIs(GT_ASG) && (op1->gtOper == GT_LCL_VAR) &&
454 (op1->gtLclVarCommon.gtLclNum == lclNum));
455
456 /* TODO-Review: BB_UNITY_WEIGHT is not the correct block weight */
457 unsigned blockWeight = BB_UNITY_WEIGHT;
458
459 /* Assign the old expression into the new temp */
460
461 GenTree* newAsgn = gtNewTempAssign(copyLclNum, tree->gtOp.gtOp2);
462
463 /* Copy the new temp to op1 */
464
465 GenTree* copyAsgn = gtNewAssignNode(op1, gtNewLclvNode(copyLclNum, typ));
466
467 /* Change the tree to a GT_COMMA with the two assignments as child nodes */
468
469 tree->gtBashToNOP();
470 tree->ChangeOper(GT_COMMA);
471
472 tree->gtOp.gtOp1 = newAsgn;
473 tree->gtOp.gtOp2 = copyAsgn;
474
475 tree->gtFlags |= (newAsgn->gtFlags & GTF_ALL_EFFECT);
476 tree->gtFlags |= (copyAsgn->gtFlags & GTF_ALL_EFFECT);
477 }
478
479#ifdef DEBUG
480 if (verbose)
481 {
482 printf("\nIntroducing a new copy for V%02u\n", lclNum);
483 gtDispTree(stmt->gtStmt.gtStmtExpr);
484 printf("\n");
485 }
486#endif
487 }
488}
489
490//------------------------------------------------------------------------------
491// GetAssertionDep: Retrieve the assertions on this local variable
492//
493// Arguments:
494// lclNum - The local var id.
495//
496// Return Value:
497// The dependent assertions (assertions using the value of the local var)
498// of the local var.
499//
500
501ASSERT_TP& Compiler::GetAssertionDep(unsigned lclNum)
502{
503 JitExpandArray<ASSERT_TP>& dep = *optAssertionDep;
504 if (dep[lclNum] == nullptr)
505 {
506 dep[lclNum] = BitVecOps::MakeEmpty(apTraits);
507 }
508 return dep[lclNum];
509}
510
511/*****************************************************************************
512 *
513 * Initialize the assertion prop bitset traits and the default bitsets.
514 */
515
516void Compiler::optAssertionTraitsInit(AssertionIndex assertionCount)
517{
518 apTraits = new (this, CMK_AssertionProp) BitVecTraits(assertionCount, this);
519 apFull = BitVecOps::MakeFull(apTraits);
520}
521
522/*****************************************************************************
523 *
524 * Initialize the assertion prop tracking logic.
525 */
526
527void Compiler::optAssertionInit(bool isLocalProp)
528{
529 // Use a function countFunc to determine a proper maximum assertion count for the
530 // method being compiled. The function is linear to the IL size for small and
531 // moderate methods. For large methods, considering throughput impact, we track no
532 // more than 64 assertions.
533 // Note this tracks at most only 256 assertions.
534 static const AssertionIndex countFunc[] = {64, 128, 256, 64};
535 static const unsigned lowerBound = 0;
536 static const unsigned upperBound = _countof(countFunc) - 1;
537 const unsigned codeSize = info.compILCodeSize / 512;
538 optMaxAssertionCount = countFunc[isLocalProp ? lowerBound : min(upperBound, codeSize)];
539
540 optLocalAssertionProp = isLocalProp;
541 optAssertionTabPrivate = new (this, CMK_AssertionProp) AssertionDsc[optMaxAssertionCount];
542 optComplementaryAssertionMap =
543 new (this, CMK_AssertionProp) AssertionIndex[optMaxAssertionCount + 1](); // zero-inited (NO_ASSERTION_INDEX)
544 assert(NO_ASSERTION_INDEX == 0);
545
546 if (!isLocalProp)
547 {
548 optValueNumToAsserts = new (getAllocator()) ValueNumToAssertsMap(getAllocator());
549 }
550
551 if (optAssertionDep == nullptr)
552 {
553 optAssertionDep = new (this, CMK_AssertionProp) JitExpandArray<ASSERT_TP>(getAllocator(), max(1, lvaCount));
554 }
555
556 optAssertionTraitsInit(optMaxAssertionCount);
557 optAssertionCount = 0;
558 optAssertionPropagated = false;
559 bbJtrueAssertionOut = nullptr;
560}
561
562#ifdef DEBUG
563void Compiler::optPrintAssertion(AssertionDsc* curAssertion, AssertionIndex assertionIndex /* =0 */)
564{
565 if (curAssertion->op1.kind == O1K_EXACT_TYPE)
566 {
567 printf("Type ");
568 }
569 else if (curAssertion->op1.kind == O1K_ARR_BND)
570 {
571 printf("ArrBnds ");
572 }
573 else if (curAssertion->op1.kind == O1K_SUBTYPE)
574 {
575 printf("Subtype ");
576 }
577 else if (curAssertion->op2.kind == O2K_LCLVAR_COPY)
578 {
579 printf("Copy ");
580 }
581 else if ((curAssertion->op2.kind == O2K_CONST_INT) || (curAssertion->op2.kind == O2K_CONST_LONG) ||
582 (curAssertion->op2.kind == O2K_CONST_DOUBLE))
583 {
584 printf("Constant ");
585 }
586 else if (curAssertion->op2.kind == O2K_SUBRANGE)
587 {
588 printf("Subrange ");
589 }
590 else
591 {
592 printf("?assertion classification? ");
593 }
594 printf("Assertion: ");
595 if (!optLocalAssertionProp)
596 {
597 printf("(%d, %d) ", curAssertion->op1.vn, curAssertion->op2.vn);
598 }
599
600 if (!optLocalAssertionProp)
601 {
602 printf("(" FMT_VN "," FMT_VN ") ", curAssertion->op1.vn, curAssertion->op2.vn);
603 }
604
605 if ((curAssertion->op1.kind == O1K_LCLVAR) || (curAssertion->op1.kind == O1K_EXACT_TYPE) ||
606 (curAssertion->op1.kind == O1K_SUBTYPE))
607 {
608 printf("V%02u", curAssertion->op1.lcl.lclNum);
609 if (curAssertion->op1.lcl.ssaNum != SsaConfig::RESERVED_SSA_NUM)
610 {
611 printf(".%02u", curAssertion->op1.lcl.ssaNum);
612 }
613 }
614 else if (curAssertion->op1.kind == O1K_ARR_BND)
615 {
616 printf("[idx:");
617 vnStore->vnDump(this, curAssertion->op1.bnd.vnIdx);
618 printf(";len:");
619 vnStore->vnDump(this, curAssertion->op1.bnd.vnLen);
620 printf("]");
621 }
622 else if (curAssertion->op1.kind == O1K_BOUND_OPER_BND)
623 {
624 printf("Oper_Bnd");
625 vnStore->vnDump(this, curAssertion->op1.vn);
626 }
627 else if (curAssertion->op1.kind == O1K_BOUND_LOOP_BND)
628 {
629 printf("Loop_Bnd");
630 vnStore->vnDump(this, curAssertion->op1.vn);
631 }
632 else if (curAssertion->op1.kind == O1K_CONSTANT_LOOP_BND)
633 {
634 printf("Const_Loop_Bnd");
635 vnStore->vnDump(this, curAssertion->op1.vn);
636 }
637 else if (curAssertion->op1.kind == O1K_VALUE_NUMBER)
638 {
639 printf("Value_Number");
640 vnStore->vnDump(this, curAssertion->op1.vn);
641 }
642 else
643 {
644 printf("?op1.kind?");
645 }
646
647 if (curAssertion->assertionKind == OAK_SUBRANGE)
648 {
649 printf(" in ");
650 }
651 else if (curAssertion->assertionKind == OAK_EQUAL)
652 {
653 if (curAssertion->op1.kind == O1K_LCLVAR)
654 {
655 printf(" == ");
656 }
657 else
658 {
659 printf(" is ");
660 }
661 }
662 else if (curAssertion->assertionKind == OAK_NO_THROW)
663 {
664 printf(" in range ");
665 }
666 else if (curAssertion->assertionKind == OAK_NOT_EQUAL)
667 {
668 if (curAssertion->op1.kind == O1K_LCLVAR)
669 {
670 printf(" != ");
671 }
672 else
673 {
674 printf(" is not ");
675 }
676 }
677 else
678 {
679 printf(" ?assertionKind? ");
680 }
681
682 if (curAssertion->op1.kind != O1K_ARR_BND)
683 {
684 switch (curAssertion->op2.kind)
685 {
686 case O2K_LCLVAR_COPY:
687 printf("V%02u", curAssertion->op2.lcl.lclNum);
688 if (curAssertion->op1.lcl.ssaNum != SsaConfig::RESERVED_SSA_NUM)
689 {
690 printf(".%02u", curAssertion->op1.lcl.ssaNum);
691 }
692 break;
693
694 case O2K_CONST_INT:
695 case O2K_IND_CNS_INT:
696 if (curAssertion->op1.kind == O1K_EXACT_TYPE)
697 {
698 printf("Exact Type MT(%08X)", dspPtr(curAssertion->op2.u1.iconVal));
699 assert(curAssertion->op2.u1.iconFlags != 0);
700 }
701 else if (curAssertion->op1.kind == O1K_SUBTYPE)
702 {
703 printf("MT(%08X)", dspPtr(curAssertion->op2.u1.iconVal));
704 assert(curAssertion->op2.u1.iconFlags != 0);
705 }
706 else if (curAssertion->op1.kind == O1K_BOUND_OPER_BND)
707 {
708 assert(!optLocalAssertionProp);
709 vnStore->vnDump(this, curAssertion->op2.vn);
710 }
711 else if (curAssertion->op1.kind == O1K_BOUND_LOOP_BND)
712 {
713 assert(!optLocalAssertionProp);
714 vnStore->vnDump(this, curAssertion->op2.vn);
715 }
716 else if (curAssertion->op1.kind == O1K_CONSTANT_LOOP_BND)
717 {
718 assert(!optLocalAssertionProp);
719 vnStore->vnDump(this, curAssertion->op2.vn);
720 }
721 else
722 {
723 var_types op1Type;
724
725 if (curAssertion->op1.kind == O1K_VALUE_NUMBER)
726 {
727 op1Type = vnStore->TypeOfVN(curAssertion->op1.vn);
728 }
729 else
730 {
731 unsigned lclNum = curAssertion->op1.lcl.lclNum;
732 assert(lclNum < lvaCount);
733 LclVarDsc* varDsc = lvaTable + lclNum;
734 op1Type = varDsc->lvType;
735 }
736
737 if (op1Type == TYP_REF)
738 {
739 assert(curAssertion->op2.u1.iconVal == 0);
740 printf("null");
741 }
742 else
743 {
744 if ((curAssertion->op2.u1.iconFlags & GTF_ICON_HDL_MASK) != 0)
745 {
746 printf("[%08p]", dspPtr(curAssertion->op2.u1.iconVal));
747 }
748 else
749 {
750 printf("%d", curAssertion->op2.u1.iconVal);
751 }
752 }
753 }
754 break;
755
756 case O2K_CONST_LONG:
757 printf("0x%016llx", curAssertion->op2.lconVal);
758 break;
759
760 case O2K_CONST_DOUBLE:
761 if (*((__int64*)&curAssertion->op2.dconVal) == (__int64)I64(0x8000000000000000))
762 {
763 printf("-0.00000");
764 }
765 else
766 {
767 printf("%#lg", curAssertion->op2.dconVal);
768 }
769 break;
770
771 case O2K_SUBRANGE:
772 printf("[%d..%d]", curAssertion->op2.u2.loBound, curAssertion->op2.u2.hiBound);
773 break;
774
775 default:
776 printf("?op2.kind?");
777 break;
778 }
779 }
780
781 if (assertionIndex > 0)
782 {
783 printf(" index=#%02u, mask=", assertionIndex);
784 printf("%s", BitVecOps::ToString(apTraits, BitVecOps::MakeSingleton(apTraits, assertionIndex - 1)));
785 }
786 printf("\n");
787}
788#endif // DEBUG
789
790/******************************************************************************
791 *
792 * Helper to retrieve the "assertIndex" assertion. Note that assertIndex 0
793 * is NO_ASSERTION_INDEX and "optAssertionCount" is the last valid index.
794 *
795 */
796Compiler::AssertionDsc* Compiler::optGetAssertion(AssertionIndex assertIndex)
797{
798 assert(NO_ASSERTION_INDEX == 0);
799 assert(assertIndex != NO_ASSERTION_INDEX);
800 assert(assertIndex <= optAssertionCount);
801 AssertionDsc* assertion = &optAssertionTabPrivate[assertIndex - 1];
802#ifdef DEBUG
803 optDebugCheckAssertion(assertion);
804#endif
805
806 return assertion;
807}
808
809/*****************************************************************************
810 *
811 * A simple helper routine so not all callers need to supply a AssertionDsc*
812 * if they don't care about it. Refer overloaded method optCreateAssertion.
813 *
814 */
815AssertionIndex Compiler::optCreateAssertion(GenTree* op1, GenTree* op2, optAssertionKind assertionKind)
816{
817 AssertionDsc assertionDsc;
818 return optCreateAssertion(op1, op2, assertionKind, &assertionDsc);
819}
820
821/*****************************************************************************
822 *
823 * We attempt to create the following assertion:
824 *
825 * op1 assertionKind op2
826 *
827 * If we can create the assertion then update 'assertion' if we are
828 * unsuccessful assertion->assertionKind will be OAK_INVALID. If we are
829 * successful in creating the assertion we call optAddAssertion which adds
830 * the assertion to our assertion table.
831 *
832 * If we are able to create the assertion the return value is the
833 * assertionIndex for this assertion otherwise the return value is
834 * NO_ASSERTION_INDEX and we could not create the assertion.
835 *
836 */
837AssertionIndex Compiler::optCreateAssertion(GenTree* op1,
838 GenTree* op2,
839 optAssertionKind assertionKind,
840 AssertionDsc* assertion)
841{
842 memset(assertion, 0, sizeof(AssertionDsc));
843 //
844 // If we cannot create an assertion using op1 and op2 then the assertionKind
845 // must be OAK_INVALID, so we initialize it to OAK_INVALID and only change it
846 // to a valid assertion when everything is good.
847 //
848 assertion->assertionKind = OAK_INVALID;
849 bool haveArgs = false;
850 var_types toType;
851
852 if (op1->gtOper == GT_ARR_BOUNDS_CHECK)
853 {
854 if (assertionKind == OAK_NO_THROW)
855 {
856 GenTreeBoundsChk* arrBndsChk = op1->AsBoundsChk();
857 assertion->assertionKind = assertionKind;
858 assertion->op1.kind = O1K_ARR_BND;
859 assertion->op1.bnd.vnIdx = vnStore->VNConservativeNormalValue(arrBndsChk->gtIndex->gtVNPair);
860 assertion->op1.bnd.vnLen = vnStore->VNConservativeNormalValue(arrBndsChk->gtArrLen->gtVNPair);
861 goto DONE_ASSERTION;
862 }
863 }
864
865 //
866 // Did we receive Helper call args?
867 //
868 if (op1->gtOper == GT_LIST)
869 {
870 if (op2->gtOper != GT_LIST)
871 {
872 goto DONE_ASSERTION; // Don't make an assertion
873 }
874 op1 = op1->gtOp.gtOp1;
875 op2 = op2->gtOp.gtOp1;
876 haveArgs = true;
877 }
878
879 //
880 // Are we trying to make a non-null assertion?
881 //
882 if (op2 == nullptr)
883 {
884 assert(haveArgs == false);
885 //
886 // Must an OAK_NOT_EQUAL assertion
887 //
888 noway_assert(assertionKind == OAK_NOT_EQUAL);
889
890 //
891 // Set op1 to the instance pointer of the indirection
892 //
893
894 ssize_t offset = 0;
895 while ((op1->gtOper == GT_ADD) && (op1->gtType == TYP_BYREF))
896 {
897 if (op1->gtGetOp2()->IsCnsIntOrI())
898 {
899 offset += op1->gtGetOp2()->gtIntCon.gtIconVal;
900 op1 = op1->gtGetOp1();
901 }
902 else if (op1->gtGetOp1()->IsCnsIntOrI())
903 {
904 offset += op1->gtGetOp1()->gtIntCon.gtIconVal;
905 op1 = op1->gtGetOp2();
906 }
907 else
908 {
909 break;
910 }
911 }
912
913 if (fgIsBigOffset(offset) || op1->gtOper != GT_LCL_VAR)
914 {
915 goto DONE_ASSERTION; // Don't make an assertion
916 }
917
918 unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
919 noway_assert(lclNum < lvaCount);
920 LclVarDsc* lclVar = &lvaTable[lclNum];
921
922 ValueNum vn;
923
924 //
925 // We only perform null-checks on GC refs
926 // so only make non-null assertions about GC refs
927 //
928 if (lclVar->TypeGet() != TYP_REF)
929 {
930 if (optLocalAssertionProp || (lclVar->TypeGet() != TYP_BYREF))
931 {
932 goto DONE_ASSERTION; // Don't make an assertion
933 }
934
935 vn = vnStore->VNConservativeNormalValue(op1->gtVNPair);
936 VNFuncApp funcAttr;
937
938 // Try to get value number corresponding to the GC ref of the indirection
939 while (vnStore->GetVNFunc(vn, &funcAttr) && (funcAttr.m_func == (VNFunc)GT_ADD) &&
940 (vnStore->TypeOfVN(vn) == TYP_BYREF))
941 {
942 if (vnStore->IsVNConstant(funcAttr.m_args[1]) &&
943 varTypeIsIntegral(vnStore->TypeOfVN(funcAttr.m_args[1])))
944 {
945 offset += vnStore->CoercedConstantValue<ssize_t>(funcAttr.m_args[1]);
946 vn = funcAttr.m_args[0];
947 }
948 else if (vnStore->IsVNConstant(funcAttr.m_args[0]) &&
949 varTypeIsIntegral(vnStore->TypeOfVN(funcAttr.m_args[0])))
950 {
951 offset += vnStore->CoercedConstantValue<ssize_t>(funcAttr.m_args[0]);
952 vn = funcAttr.m_args[1];
953 }
954 else
955 {
956 break;
957 }
958 }
959
960 if (fgIsBigOffset(offset) || (vnStore->TypeOfVN(vn) != TYP_REF))
961 {
962 goto DONE_ASSERTION; // Don't make an assertion
963 }
964
965 assertion->op1.kind = O1K_VALUE_NUMBER;
966 }
967 else
968 {
969 // If the local variable has its address exposed then bail
970 if (lclVar->lvAddrExposed)
971 {
972 goto DONE_ASSERTION; // Don't make an assertion
973 }
974
975 assertion->op1.kind = O1K_LCLVAR;
976 assertion->op1.lcl.lclNum = lclNum;
977 assertion->op1.lcl.ssaNum = op1->AsLclVarCommon()->GetSsaNum();
978 vn = vnStore->VNConservativeNormalValue(op1->gtVNPair);
979 }
980
981 assertion->op1.vn = vn;
982 assertion->assertionKind = assertionKind;
983 assertion->op2.kind = O2K_CONST_INT;
984 assertion->op2.vn = ValueNumStore::VNForNull();
985 assertion->op2.u1.iconVal = 0;
986 assertion->op2.u1.iconFlags = 0;
987#ifdef _TARGET_64BIT_
988 assertion->op2.u1.iconFlags |= 1; // Signify that this is really TYP_LONG
989#endif // _TARGET_64BIT_
990 }
991 //
992 // Are we making an assertion about a local variable?
993 //
994 else if (op1->gtOper == GT_LCL_VAR)
995 {
996 unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
997 noway_assert(lclNum < lvaCount);
998 LclVarDsc* lclVar = &lvaTable[lclNum];
999
1000 // If the local variable has its address exposed then bail
1001 if (lclVar->lvAddrExposed)
1002 {
1003 goto DONE_ASSERTION; // Don't make an assertion
1004 }
1005
1006 if (haveArgs)
1007 {
1008 //
1009 // Must either be an OAK_EQUAL or an OAK_NOT_EQUAL assertion
1010 //
1011 if ((assertionKind != OAK_EQUAL) && (assertionKind != OAK_NOT_EQUAL))
1012 {
1013 goto DONE_ASSERTION; // Don't make an assertion
1014 }
1015
1016 if (op2->gtOper == GT_IND)
1017 {
1018 op2 = op2->gtOp.gtOp1;
1019 assertion->op2.kind = O2K_IND_CNS_INT;
1020 }
1021 else
1022 {
1023 assertion->op2.kind = O2K_CONST_INT;
1024 }
1025
1026 if (op2->gtOper != GT_CNS_INT)
1027 {
1028 goto DONE_ASSERTION; // Don't make an assertion
1029 }
1030
1031 //
1032 // TODO-CQ: Check for Sealed class and change kind to O1K_EXACT_TYPE
1033 // And consider the special cases, like CORINFO_FLG_SHAREDINST or CORINFO_FLG_VARIANCE
1034 // where a class can be sealed, but they don't behave as exact types because casts to
1035 // non-base types sometimes still succeed.
1036 //
1037 assertion->op1.kind = O1K_SUBTYPE;
1038 assertion->op1.lcl.lclNum = lclNum;
1039 assertion->op1.vn = vnStore->VNConservativeNormalValue(op1->gtVNPair);
1040 assertion->op1.lcl.ssaNum = op1->AsLclVarCommon()->GetSsaNum();
1041 assertion->op2.u1.iconVal = op2->gtIntCon.gtIconVal;
1042 assertion->op2.vn = vnStore->VNConservativeNormalValue(op2->gtVNPair);
1043 assertion->op2.u1.iconFlags = op2->GetIconHandleFlag();
1044
1045 //
1046 // Ok everything has been set and the assertion looks good
1047 //
1048 assertion->assertionKind = assertionKind;
1049 }
1050 else // !haveArgs
1051 {
1052 /* Skip over a GT_COMMA node(s), if necessary */
1053 while (op2->gtOper == GT_COMMA)
1054 {
1055 op2 = op2->gtOp.gtOp2;
1056 }
1057
1058 assertion->op1.kind = O1K_LCLVAR;
1059 assertion->op1.lcl.lclNum = lclNum;
1060 assertion->op1.vn = vnStore->VNConservativeNormalValue(op1->gtVNPair);
1061 assertion->op1.lcl.ssaNum = op1->AsLclVarCommon()->GetSsaNum();
1062
1063 switch (op2->gtOper)
1064 {
1065 optOp2Kind op2Kind;
1066 //
1067 // No Assertion
1068 //
1069 default:
1070 goto DONE_ASSERTION; // Don't make an assertion
1071
1072 //
1073 // Constant Assertions
1074 //
1075 case GT_CNS_INT:
1076 op2Kind = O2K_CONST_INT;
1077 goto CNS_COMMON;
1078
1079 case GT_CNS_LNG:
1080 op2Kind = O2K_CONST_LONG;
1081 goto CNS_COMMON;
1082
1083 case GT_CNS_DBL:
1084 op2Kind = O2K_CONST_DOUBLE;
1085 goto CNS_COMMON;
1086
1087 CNS_COMMON:
1088 {
1089 //
1090 // Must either be an OAK_EQUAL or an OAK_NOT_EQUAL assertion
1091 //
1092 if ((assertionKind != OAK_EQUAL) && (assertionKind != OAK_NOT_EQUAL))
1093 {
1094 goto DONE_ASSERTION; // Don't make an assertion
1095 }
1096
1097 // If the LclVar is a TYP_LONG then we only make
1098 // assertions where op2 is also TYP_LONG
1099 //
1100 if ((lclVar->TypeGet() == TYP_LONG) && (op2->TypeGet() != TYP_LONG))
1101 {
1102 goto DONE_ASSERTION; // Don't make an assertion
1103 }
1104
1105 assertion->op2.kind = op2Kind;
1106 assertion->op2.lconVal = 0;
1107 assertion->op2.vn = vnStore->VNConservativeNormalValue(op2->gtVNPair);
1108
1109 if (op2->gtOper == GT_CNS_INT)
1110 {
1111#ifdef _TARGET_ARM_
1112 // Do not Constant-Prop immediate values that require relocation
1113 if (op2->gtIntCon.ImmedValNeedsReloc(this))
1114 {
1115 goto DONE_ASSERTION;
1116 }
1117 // Do not Constant-Prop large constants for ARM
1118 // TODO-CrossBitness: we wouldn't need the cast below if GenTreeIntCon::gtIconVal had
1119 // target_ssize_t type.
1120 if (!codeGen->validImmForMov((target_ssize_t)op2->gtIntCon.gtIconVal))
1121 {
1122 goto DONE_ASSERTION; // Don't make an assertion
1123 }
1124#endif // _TARGET_ARM_
1125 assertion->op2.u1.iconVal = op2->gtIntCon.gtIconVal;
1126 assertion->op2.u1.iconFlags = op2->GetIconHandleFlag();
1127#ifdef _TARGET_64BIT_
1128 if (op2->TypeGet() == TYP_LONG || op2->TypeGet() == TYP_BYREF)
1129 {
1130 assertion->op2.u1.iconFlags |= 1; // Signify that this is really TYP_LONG
1131 }
1132#endif // _TARGET_64BIT_
1133 }
1134 else if (op2->gtOper == GT_CNS_LNG)
1135 {
1136 assertion->op2.lconVal = op2->gtLngCon.gtLconVal;
1137 }
1138 else
1139 {
1140 noway_assert(op2->gtOper == GT_CNS_DBL);
1141 /* If we have an NaN value then don't record it */
1142 if (_isnan(op2->gtDblCon.gtDconVal))
1143 {
1144 goto DONE_ASSERTION; // Don't make an assertion
1145 }
1146 assertion->op2.dconVal = op2->gtDblCon.gtDconVal;
1147 }
1148
1149 //
1150 // Ok everything has been set and the assertion looks good
1151 //
1152 assertion->assertionKind = assertionKind;
1153 }
1154 break;
1155
1156 //
1157 // Copy Assertions
1158 //
1159 case GT_LCL_VAR:
1160 {
1161 //
1162 // Must either be an OAK_EQUAL or an OAK_NOT_EQUAL assertion
1163 //
1164 if ((assertionKind != OAK_EQUAL) && (assertionKind != OAK_NOT_EQUAL))
1165 {
1166 goto DONE_ASSERTION; // Don't make an assertion
1167 }
1168
1169 unsigned lclNum2 = op2->gtLclVarCommon.gtLclNum;
1170 noway_assert(lclNum2 < lvaCount);
1171 LclVarDsc* lclVar2 = &lvaTable[lclNum2];
1172
1173 // If the two locals are the same then bail
1174 if (lclNum == lclNum2)
1175 {
1176 goto DONE_ASSERTION; // Don't make an assertion
1177 }
1178
1179 // If the types are different then bail */
1180 if (lclVar->lvType != lclVar2->lvType)
1181 {
1182 goto DONE_ASSERTION; // Don't make an assertion
1183 }
1184
1185 // If we're making a copy of a "normalize on load" lclvar then the destination
1186 // has to be "normalize on load" as well, otherwise we risk skipping normalization.
1187 if (lclVar2->lvNormalizeOnLoad() && !lclVar->lvNormalizeOnLoad())
1188 {
1189 goto DONE_ASSERTION; // Don't make an assertion
1190 }
1191
1192 // If the local variable has its address exposed then bail
1193 if (lclVar2->lvAddrExposed)
1194 {
1195 goto DONE_ASSERTION; // Don't make an assertion
1196 }
1197
1198 assertion->op2.kind = O2K_LCLVAR_COPY;
1199 assertion->op2.lcl.lclNum = lclNum2;
1200 assertion->op2.vn = vnStore->VNConservativeNormalValue(op2->gtVNPair);
1201 assertion->op2.lcl.ssaNum = op2->AsLclVarCommon()->GetSsaNum();
1202
1203 //
1204 // Ok everything has been set and the assertion looks good
1205 //
1206 assertion->assertionKind = assertionKind;
1207 }
1208 break;
1209
1210 // Subrange Assertions
1211 case GT_EQ:
1212 case GT_NE:
1213 case GT_LT:
1214 case GT_LE:
1215 case GT_GT:
1216 case GT_GE:
1217
1218 /* Assigning the result of a RELOP, we can add a boolean subrange assertion */
1219
1220 toType = TYP_BOOL;
1221 goto SUBRANGE_COMMON;
1222
1223 case GT_CLS_VAR:
1224
1225 /* Assigning the result of an indirection into a LCL_VAR, see if we can add a subrange assertion */
1226
1227 toType = op2->gtType;
1228 goto SUBRANGE_COMMON;
1229
1230 case GT_ARR_ELEM:
1231
1232 /* Assigning the result of an indirection into a LCL_VAR, see if we can add a subrange assertion */
1233
1234 toType = op2->gtType;
1235 goto SUBRANGE_COMMON;
1236
1237 case GT_LCL_FLD:
1238
1239 /* Assigning the result of an indirection into a LCL_VAR, see if we can add a subrange assertion */
1240
1241 toType = op2->gtType;
1242 goto SUBRANGE_COMMON;
1243
1244 case GT_IND:
1245
1246 /* Assigning the result of an indirection into a LCL_VAR, see if we can add a subrange assertion */
1247
1248 toType = op2->gtType;
1249 goto SUBRANGE_COMMON;
1250
1251 case GT_CAST:
1252 {
1253 if (lvaTable[lclNum].lvIsStructField && lvaTable[lclNum].lvNormalizeOnLoad())
1254 {
1255 // Keep the cast on small struct fields.
1256 goto DONE_ASSERTION; // Don't make an assertion
1257 }
1258
1259 toType = op2->CastToType();
1260 SUBRANGE_COMMON:
1261 if ((assertionKind != OAK_SUBRANGE) && (assertionKind != OAK_EQUAL))
1262 {
1263 goto DONE_ASSERTION; // Don't make an assertion
1264 }
1265
1266 if (varTypeIsFloating(op1->TypeGet()))
1267 {
1268 // We don't make assertions on a cast from floating point
1269 goto DONE_ASSERTION;
1270 }
1271
1272 switch (toType)
1273 {
1274 case TYP_BOOL:
1275 case TYP_BYTE:
1276 case TYP_UBYTE:
1277 case TYP_SHORT:
1278 case TYP_USHORT:
1279#ifdef _TARGET_64BIT_
1280 case TYP_UINT:
1281 case TYP_INT:
1282#endif // _TARGET_64BIT_
1283 assertion->op2.u2.loBound = AssertionDsc::GetLowerBoundForIntegralType(toType);
1284 assertion->op2.u2.hiBound = AssertionDsc::GetUpperBoundForIntegralType(toType);
1285 break;
1286
1287 default:
1288 goto DONE_ASSERTION; // Don't make an assertion
1289 }
1290 assertion->op2.kind = O2K_SUBRANGE;
1291 assertion->assertionKind = OAK_SUBRANGE;
1292 }
1293 break;
1294 }
1295 } // else // !haveArgs
1296 } // if (op1->gtOper == GT_LCL_VAR)
1297
1298 //
1299 // Are we making an IsType assertion?
1300 //
1301 else if (op1->gtOper == GT_IND)
1302 {
1303 op1 = op1->gtOp.gtOp1;
1304 //
1305 // Is this an indirection of a local variable?
1306 //
1307 if (op1->gtOper == GT_LCL_VAR)
1308 {
1309 unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
1310 noway_assert(lclNum < lvaCount);
1311 LclVarDsc* lclVar = &lvaTable[lclNum];
1312
1313 // If the local variable is not in SSA then bail
1314 if (!lvaInSsa(lclNum))
1315 {
1316 goto DONE_ASSERTION;
1317 }
1318
1319 // If we have an typeHnd indirection then op1 must be a TYP_REF
1320 // and the indirection must produce a TYP_I
1321 //
1322 if (op1->gtType != TYP_REF)
1323 {
1324 goto DONE_ASSERTION; // Don't make an assertion
1325 }
1326
1327 assertion->op1.kind = O1K_EXACT_TYPE;
1328 assertion->op1.lcl.lclNum = lclNum;
1329 assertion->op1.vn = vnStore->VNConservativeNormalValue(op1->gtVNPair);
1330 assertion->op1.lcl.ssaNum = op1->AsLclVarCommon()->GetSsaNum();
1331
1332 assert(assertion->op1.lcl.ssaNum == SsaConfig::RESERVED_SSA_NUM ||
1333 assertion->op1.vn ==
1334 vnStore->VNConservativeNormalValue(
1335 lvaTable[lclNum].GetPerSsaData(assertion->op1.lcl.ssaNum)->m_vnPair));
1336
1337 ssize_t cnsValue = 0;
1338 unsigned iconFlags = 0;
1339 // Ngen case
1340 if (op2->gtOper == GT_IND)
1341 {
1342 if (!optIsTreeKnownIntValue(!optLocalAssertionProp, op2->gtOp.gtOp1, &cnsValue, &iconFlags))
1343 {
1344 goto DONE_ASSERTION; // Don't make an assertion
1345 }
1346
1347 assertion->assertionKind = assertionKind;
1348 assertion->op2.kind = O2K_IND_CNS_INT;
1349 assertion->op2.u1.iconVal = cnsValue;
1350 assertion->op2.vn = vnStore->VNConservativeNormalValue(op2->gtOp.gtOp1->gtVNPair);
1351
1352 /* iconFlags should only contain bits in GTF_ICON_HDL_MASK */
1353 assert((iconFlags & ~GTF_ICON_HDL_MASK) == 0);
1354 assertion->op2.u1.iconFlags = iconFlags;
1355#ifdef _TARGET_64BIT_
1356 if (op2->gtOp.gtOp1->TypeGet() == TYP_LONG)
1357 {
1358 assertion->op2.u1.iconFlags |= 1; // Signify that this is really TYP_LONG
1359 }
1360#endif // _TARGET_64BIT_
1361 }
1362 // JIT case
1363 else if (optIsTreeKnownIntValue(!optLocalAssertionProp, op2, &cnsValue, &iconFlags))
1364 {
1365 assertion->assertionKind = assertionKind;
1366 assertion->op2.kind = O2K_IND_CNS_INT;
1367 assertion->op2.u1.iconVal = cnsValue;
1368 assertion->op2.vn = vnStore->VNConservativeNormalValue(op2->gtVNPair);
1369
1370 /* iconFlags should only contain bits in GTF_ICON_HDL_MASK */
1371 assert((iconFlags & ~GTF_ICON_HDL_MASK) == 0);
1372 assertion->op2.u1.iconFlags = iconFlags;
1373#ifdef _TARGET_64BIT_
1374 if (op2->TypeGet() == TYP_LONG)
1375 {
1376 assertion->op2.u1.iconFlags |= 1; // Signify that this is really TYP_LONG
1377 }
1378#endif // _TARGET_64BIT_
1379 }
1380 else
1381 {
1382 goto DONE_ASSERTION; // Don't make an assertion
1383 }
1384 }
1385 }
1386
1387DONE_ASSERTION:
1388 if (assertion->assertionKind == OAK_INVALID)
1389 {
1390 return NO_ASSERTION_INDEX;
1391 }
1392
1393 if (!optLocalAssertionProp)
1394 {
1395 if ((assertion->op1.vn == ValueNumStore::NoVN) || (assertion->op2.vn == ValueNumStore::NoVN) ||
1396 (assertion->op1.vn == ValueNumStore::VNForVoid()) || (assertion->op2.vn == ValueNumStore::VNForVoid()))
1397 {
1398 return NO_ASSERTION_INDEX;
1399 }
1400
1401 // TODO: only copy assertions rely on valid SSA number so we could generate more assertions here
1402 if ((assertion->op1.kind != O1K_VALUE_NUMBER) && (assertion->op1.lcl.ssaNum == SsaConfig::RESERVED_SSA_NUM))
1403 {
1404 return NO_ASSERTION_INDEX;
1405 }
1406 }
1407
1408 // Now add the assertion to our assertion table
1409 noway_assert(assertion->op1.kind != O1K_INVALID);
1410 noway_assert(assertion->op1.kind == O1K_ARR_BND || assertion->op2.kind != O2K_INVALID);
1411 return optAddAssertion(assertion);
1412}
1413
1414/*****************************************************************************
1415 *
1416 * If tree is a constant node holding an integral value, retrieve the value in
1417 * pConstant. If the method returns true, pConstant holds the appropriate
1418 * constant. Set "vnBased" to true to indicate local or global assertion prop.
1419 * "pFlags" indicates if the constant is a handle marked by GTF_ICON_HDL_MASK.
1420 */
1421bool Compiler::optIsTreeKnownIntValue(bool vnBased, GenTree* tree, ssize_t* pConstant, unsigned* pFlags)
1422{
1423 // Is Local assertion prop?
1424 if (!vnBased)
1425 {
1426 if (tree->OperGet() == GT_CNS_INT)
1427 {
1428 *pConstant = tree->gtIntCon.IconValue();
1429 *pFlags = tree->GetIconHandleFlag();
1430 return true;
1431 }
1432#ifdef _TARGET_64BIT_
1433 // Just to be clear, get it from gtLconVal rather than
1434 // overlapping gtIconVal.
1435 else if (tree->OperGet() == GT_CNS_LNG)
1436 {
1437 *pConstant = tree->gtLngCon.gtLconVal;
1438 *pFlags = tree->GetIconHandleFlag();
1439 return true;
1440 }
1441#endif
1442 return false;
1443 }
1444
1445 // Global assertion prop
1446 ValueNum vn = vnStore->VNConservativeNormalValue(tree->gtVNPair);
1447 if (!vnStore->IsVNConstant(vn))
1448 {
1449 return false;
1450 }
1451
1452 // ValueNumber 'vn' indicates that this node evaluates to a constant
1453
1454 var_types vnType = vnStore->TypeOfVN(vn);
1455 if (vnType == TYP_INT)
1456 {
1457 *pConstant = vnStore->ConstantValue<int>(vn);
1458 *pFlags = vnStore->IsVNHandle(vn) ? vnStore->GetHandleFlags(vn) : 0;
1459 return true;
1460 }
1461#ifdef _TARGET_64BIT_
1462 else if (vnType == TYP_LONG)
1463 {
1464 *pConstant = vnStore->ConstantValue<INT64>(vn);
1465 *pFlags = vnStore->IsVNHandle(vn) ? vnStore->GetHandleFlags(vn) : 0;
1466 return true;
1467 }
1468#endif
1469 return false;
1470}
1471
1472#ifdef DEBUG
1473/*****************************************************************************
1474 *
1475 * Print the assertions related to a VN for all VNs.
1476 *
1477 */
1478void Compiler::optPrintVnAssertionMapping()
1479{
1480 printf("\nVN Assertion Mapping\n");
1481 printf("---------------------\n");
1482 for (ValueNumToAssertsMap::KeyIterator ki = optValueNumToAsserts->Begin(); !ki.Equal(optValueNumToAsserts->End());
1483 ++ki)
1484 {
1485 printf("(%d => ", ki.Get());
1486 printf("%s)\n", BitVecOps::ToString(apTraits, ki.GetValue()));
1487 }
1488}
1489#endif
1490
1491/*****************************************************************************
1492 *
1493 * Maintain a map "optValueNumToAsserts" i.e., vn -> to set of assertions
1494 * about that VN. Given "assertions" about a "vn" add it to the previously
1495 * mapped assertions about that "vn."
1496 */
1497void Compiler::optAddVnAssertionMapping(ValueNum vn, AssertionIndex index)
1498{
1499 ASSERT_TP* cur = optValueNumToAsserts->LookupPointer(vn);
1500 if (cur == nullptr)
1501 {
1502 optValueNumToAsserts->Set(vn, BitVecOps::MakeSingleton(apTraits, index - 1));
1503 }
1504 else
1505 {
1506 BitVecOps::AddElemD(apTraits, *cur, index - 1);
1507 }
1508}
1509
1510/*****************************************************************************
1511 * Statically if we know that this assertion's VN involves a NaN don't bother
1512 * wasting an assertion table slot.
1513 */
1514bool Compiler::optAssertionVnInvolvesNan(AssertionDsc* assertion)
1515{
1516 if (optLocalAssertionProp)
1517 {
1518 return false;
1519 }
1520
1521 static const int SZ = 2;
1522 ValueNum vns[SZ] = {assertion->op1.vn, assertion->op2.vn};
1523 for (int i = 0; i < SZ; ++i)
1524 {
1525 if (vnStore->IsVNConstant(vns[i]))
1526 {
1527 var_types type = vnStore->TypeOfVN(vns[i]);
1528 if ((type == TYP_FLOAT && _isnan(vnStore->ConstantValue<float>(vns[i])) != 0) ||
1529 (type == TYP_DOUBLE && _isnan(vnStore->ConstantValue<double>(vns[i])) != 0))
1530 {
1531 return true;
1532 }
1533 }
1534 }
1535 return false;
1536}
1537
1538/*****************************************************************************
1539 *
1540 * Given an assertion add it to the assertion table
1541 *
1542 * If it is already in the assertion table return the assertionIndex that
1543 * we use to refer to this element.
1544 * Otherwise add it to the assertion table ad return the assertionIndex that
1545 * we use to refer to this element.
1546 * If we need to add to the table and the table is full return the value zero
1547 */
1548AssertionIndex Compiler::optAddAssertion(AssertionDsc* newAssertion)
1549{
1550 noway_assert(newAssertion->assertionKind != OAK_INVALID);
1551
1552 // Even though the propagation step takes care of NaN, just a check
1553 // to make sure there is no slot involving a NaN.
1554 if (optAssertionVnInvolvesNan(newAssertion))
1555 {
1556 JITDUMP("Assertion involved Nan not adding\n");
1557 return NO_ASSERTION_INDEX;
1558 }
1559
1560 // Check if exists already, so we can skip adding new one. Search backwards.
1561 for (AssertionIndex index = optAssertionCount; index >= 1; index--)
1562 {
1563 AssertionDsc* curAssertion = optGetAssertion(index);
1564 if (curAssertion->Equals(newAssertion, !optLocalAssertionProp))
1565 {
1566 return index;
1567 }
1568 }
1569
1570 // Check if we are within max count.
1571 if (optAssertionCount >= optMaxAssertionCount)
1572 {
1573 return NO_ASSERTION_INDEX;
1574 }
1575
1576 optAssertionTabPrivate[optAssertionCount] = *newAssertion;
1577 optAssertionCount++;
1578
1579#ifdef DEBUG
1580 if (verbose)
1581 {
1582 printf("GenTreeNode creates assertion:\n");
1583 gtDispTree(optAssertionPropCurrentTree, nullptr, nullptr, true);
1584 printf(optLocalAssertionProp ? "In " FMT_BB " New Local " : "In " FMT_BB " New Global ", compCurBB->bbNum);
1585 optPrintAssertion(newAssertion, optAssertionCount);
1586 }
1587#endif // DEBUG
1588
1589 // Assertion mask bits are [index + 1].
1590 if (optLocalAssertionProp)
1591 {
1592 assert(newAssertion->op1.kind == O1K_LCLVAR);
1593
1594 // Mark the variables this index depends on
1595 unsigned lclNum = newAssertion->op1.lcl.lclNum;
1596 BitVecOps::AddElemD(apTraits, GetAssertionDep(lclNum), optAssertionCount - 1);
1597 if (newAssertion->op2.kind == O2K_LCLVAR_COPY)
1598 {
1599 lclNum = newAssertion->op2.lcl.lclNum;
1600 BitVecOps::AddElemD(apTraits, GetAssertionDep(lclNum), optAssertionCount - 1);
1601 }
1602 }
1603 else
1604 // If global assertion prop, then add it to the dependents map.
1605 {
1606 optAddVnAssertionMapping(newAssertion->op1.vn, optAssertionCount);
1607 if (newAssertion->op2.kind == O2K_LCLVAR_COPY)
1608 {
1609 optAddVnAssertionMapping(newAssertion->op2.vn, optAssertionCount);
1610 }
1611 }
1612
1613#ifdef DEBUG
1614 optDebugCheckAssertions(optAssertionCount);
1615#endif
1616 return optAssertionCount;
1617}
1618
1619#ifdef DEBUG
1620void Compiler::optDebugCheckAssertion(AssertionDsc* assertion)
1621{
1622 assert(assertion->assertionKind < OAK_COUNT);
1623 assert(assertion->op1.kind < O1K_COUNT);
1624 assert(assertion->op2.kind < O2K_COUNT);
1625 // It would be good to check that op1.vn and op2.vn are valid value numbers.
1626
1627 switch (assertion->op1.kind)
1628 {
1629 case O1K_LCLVAR:
1630 case O1K_EXACT_TYPE:
1631 case O1K_SUBTYPE:
1632 assert(assertion->op1.lcl.lclNum < lvaCount);
1633 assert(optLocalAssertionProp ||
1634 lvaTable[assertion->op1.lcl.lclNum].lvPerSsaData.IsValidSsaNum(assertion->op1.lcl.ssaNum));
1635 break;
1636 case O1K_ARR_BND:
1637 // It would be good to check that bnd.vnIdx and bnd.vnLen are valid value numbers.
1638 break;
1639 case O1K_BOUND_OPER_BND:
1640 case O1K_BOUND_LOOP_BND:
1641 case O1K_CONSTANT_LOOP_BND:
1642 case O1K_VALUE_NUMBER:
1643 assert(!optLocalAssertionProp);
1644 break;
1645 default:
1646 break;
1647 }
1648 switch (assertion->op2.kind)
1649 {
1650 case O2K_IND_CNS_INT:
1651 case O2K_CONST_INT:
1652 {
1653 // The only flags that can be set are those in the GTF_ICON_HDL_MASK, or bit 0, which is
1654 // used to indicate a long constant.
1655 assert((assertion->op2.u1.iconFlags & ~(GTF_ICON_HDL_MASK | 1)) == 0);
1656 switch (assertion->op1.kind)
1657 {
1658 case O1K_EXACT_TYPE:
1659 case O1K_SUBTYPE:
1660 assert(assertion->op2.u1.iconFlags != 0);
1661 break;
1662 case O1K_LCLVAR:
1663 case O1K_ARR_BND:
1664 assert((lvaTable[assertion->op1.lcl.lclNum].lvType != TYP_REF) || (assertion->op2.u1.iconVal == 0));
1665 break;
1666 case O1K_VALUE_NUMBER:
1667 assert((vnStore->TypeOfVN(assertion->op1.vn) != TYP_REF) || (assertion->op2.u1.iconVal == 0));
1668 break;
1669 default:
1670 break;
1671 }
1672 }
1673 break;
1674
1675 default:
1676 // for all other 'assertion->op2.kind' values we don't check anything
1677 break;
1678 }
1679}
1680
1681/*****************************************************************************
1682 *
1683 * Verify that assertion prop related assumptions are valid. If "index"
1684 * is 0 (i.e., NO_ASSERTION_INDEX) then verify all assertions in the table.
1685 * If "index" is between 1 and optAssertionCount, then verify the assertion
1686 * desc corresponding to "index."
1687 */
1688void Compiler::optDebugCheckAssertions(AssertionIndex index)
1689{
1690 AssertionIndex start = (index == NO_ASSERTION_INDEX) ? 1 : index;
1691 AssertionIndex end = (index == NO_ASSERTION_INDEX) ? optAssertionCount : index;
1692 for (AssertionIndex ind = start; ind <= end; ++ind)
1693 {
1694 AssertionDsc* assertion = optGetAssertion(ind);
1695 optDebugCheckAssertion(assertion);
1696 }
1697}
1698#endif
1699
1700/*****************************************************************************
1701 *
1702 * Given a "candidateAssertion", and the assertion operands op1 and op2,
1703 * create a complementary assertion and add it to the assertion table,
1704 * which can be retrieved using optFindComplementary(index)
1705 *
1706 */
1707
1708void Compiler::optCreateComplementaryAssertion(AssertionIndex assertionIndex, GenTree* op1, GenTree* op2)
1709{
1710 if (assertionIndex == NO_ASSERTION_INDEX)
1711 {
1712 return;
1713 }
1714
1715 AssertionDsc& candidateAssertion = *optGetAssertion(assertionIndex);
1716 if (candidateAssertion.op1.kind == O1K_BOUND_OPER_BND || candidateAssertion.op1.kind == O1K_BOUND_LOOP_BND ||
1717 candidateAssertion.op1.kind == O1K_CONSTANT_LOOP_BND)
1718 {
1719 AssertionDsc dsc = candidateAssertion;
1720 dsc.assertionKind = dsc.assertionKind == OAK_EQUAL ? OAK_NOT_EQUAL : OAK_EQUAL;
1721 optAddAssertion(&dsc);
1722 return;
1723 }
1724
1725 if (candidateAssertion.assertionKind == OAK_EQUAL)
1726 {
1727 AssertionIndex index = optCreateAssertion(op1, op2, OAK_NOT_EQUAL);
1728 optMapComplementary(index, assertionIndex);
1729 }
1730 else if (candidateAssertion.assertionKind == OAK_NOT_EQUAL)
1731 {
1732 AssertionIndex index = optCreateAssertion(op1, op2, OAK_EQUAL);
1733 optMapComplementary(index, assertionIndex);
1734 }
1735
1736 // Are we making a subtype or exact type assertion?
1737 if ((candidateAssertion.op1.kind == O1K_SUBTYPE) || (candidateAssertion.op1.kind == O1K_EXACT_TYPE))
1738 {
1739 // Did we recieve helper call args?
1740 if (op1->gtOper == GT_LIST)
1741 {
1742 op1 = op1->gtOp.gtOp1;
1743 }
1744 optCreateAssertion(op1, nullptr, OAK_NOT_EQUAL);
1745 }
1746}
1747
1748/*****************************************************************************
1749 *
1750 * Create assertions for jtrue operands. Given operands "op1" and "op2" that
1751 * are used in a conditional evaluation of a jtrue stmt, create assertions
1752 * for the operands.
1753 */
1754
1755AssertionIndex Compiler::optCreateJtrueAssertions(GenTree* op1, GenTree* op2, Compiler::optAssertionKind assertionKind)
1756{
1757 AssertionDsc candidateAssertion;
1758 AssertionIndex assertionIndex = optCreateAssertion(op1, op2, assertionKind, &candidateAssertion);
1759 // Don't bother if we don't have an assertion on the JTrue False path. Current implementation
1760 // allows for a complementary only if there is an assertion on the False path (tree->HasAssertion()).
1761 if (assertionIndex != NO_ASSERTION_INDEX)
1762 {
1763 optCreateComplementaryAssertion(assertionIndex, op1, op2);
1764 }
1765 return assertionIndex;
1766}
1767
1768AssertionInfo Compiler::optCreateJTrueBoundsAssertion(GenTree* tree)
1769{
1770 GenTree* relop = tree->gtGetOp1();
1771 if ((relop->OperKind() & GTK_RELOP) == 0)
1772 {
1773 return NO_ASSERTION_INDEX;
1774 }
1775 GenTree* op1 = relop->gtGetOp1();
1776 GenTree* op2 = relop->gtGetOp2();
1777
1778 ValueNum op1VN = vnStore->VNConservativeNormalValue(op1->gtVNPair);
1779 ValueNum op2VN = vnStore->VNConservativeNormalValue(op2->gtVNPair);
1780 ValueNum relopVN = vnStore->VNConservativeNormalValue(relop->gtVNPair);
1781
1782 bool hasTestAgainstZero =
1783 (relop->gtOper == GT_EQ || relop->gtOper == GT_NE) && (op2VN == vnStore->VNZeroForType(op2->TypeGet()));
1784
1785 ValueNumStore::UnsignedCompareCheckedBoundInfo unsignedCompareBnd;
1786 // Cases where op1 holds the upper bound arithmetic and op2 is 0.
1787 // Loop condition like: "i < bnd +/-k == 0"
1788 // Assertion: "i < bnd +/- k == 0"
1789 if (hasTestAgainstZero && vnStore->IsVNCompareCheckedBoundArith(op1VN))
1790 {
1791 AssertionDsc dsc;
1792 dsc.assertionKind = relop->gtOper == GT_EQ ? OAK_EQUAL : OAK_NOT_EQUAL;
1793 dsc.op1.kind = O1K_BOUND_OPER_BND;
1794 dsc.op1.vn = op1VN;
1795 dsc.op2.kind = O2K_CONST_INT;
1796 dsc.op2.vn = vnStore->VNZeroForType(op2->TypeGet());
1797 dsc.op2.u1.iconVal = 0;
1798 dsc.op2.u1.iconFlags = 0;
1799 AssertionIndex index = optAddAssertion(&dsc);
1800 optCreateComplementaryAssertion(index, nullptr, nullptr);
1801 return index;
1802 }
1803 // Cases where op1 holds the upper bound and op2 is 0.
1804 // Loop condition like: "i < bnd == 0"
1805 // Assertion: "i < bnd == false"
1806 else if (hasTestAgainstZero && vnStore->IsVNCompareCheckedBound(op1VN))
1807 {
1808 AssertionDsc dsc;
1809 dsc.assertionKind = relop->gtOper == GT_EQ ? OAK_EQUAL : OAK_NOT_EQUAL;
1810 dsc.op1.kind = O1K_BOUND_LOOP_BND;
1811 dsc.op1.vn = op1VN;
1812 dsc.op2.kind = O2K_CONST_INT;
1813 dsc.op2.vn = vnStore->VNZeroForType(op2->TypeGet());
1814 dsc.op2.u1.iconVal = 0;
1815 dsc.op2.u1.iconFlags = 0;
1816 AssertionIndex index = optAddAssertion(&dsc);
1817 optCreateComplementaryAssertion(index, nullptr, nullptr);
1818 return index;
1819 }
1820 // Cases where op1 holds the lhs of the condition op2 holds the bound.
1821 // Loop condition like "i < bnd"
1822 // Assertion: "i < bnd != 0"
1823 else if (vnStore->IsVNCompareCheckedBound(relopVN))
1824 {
1825 AssertionDsc dsc;
1826 dsc.assertionKind = OAK_NOT_EQUAL;
1827 dsc.op1.kind = O1K_BOUND_LOOP_BND;
1828 dsc.op1.vn = relopVN;
1829 dsc.op2.kind = O2K_CONST_INT;
1830 dsc.op2.vn = vnStore->VNZeroForType(TYP_INT);
1831 dsc.op2.u1.iconVal = 0;
1832 dsc.op2.u1.iconFlags = 0;
1833 AssertionIndex index = optAddAssertion(&dsc);
1834 optCreateComplementaryAssertion(index, nullptr, nullptr);
1835 return index;
1836 }
1837 // Loop condition like "(uint)i < (uint)bnd" or equivalent
1838 // Assertion: "no throw" since this condition guarantees that i is both >= 0 and < bnd (on the appropiate edge)
1839 else if (vnStore->IsVNUnsignedCompareCheckedBound(relopVN, &unsignedCompareBnd))
1840 {
1841 assert(unsignedCompareBnd.vnIdx != ValueNumStore::NoVN);
1842 assert((unsignedCompareBnd.cmpOper == VNF_LT_UN) || (unsignedCompareBnd.cmpOper == VNF_GE_UN));
1843 assert(vnStore->IsVNCheckedBound(unsignedCompareBnd.vnBound));
1844
1845 AssertionDsc dsc;
1846 dsc.assertionKind = OAK_NO_THROW;
1847 dsc.op1.kind = O1K_ARR_BND;
1848 dsc.op1.vn = relopVN;
1849 dsc.op1.bnd.vnIdx = unsignedCompareBnd.vnIdx;
1850 dsc.op1.bnd.vnLen = vnStore->VNNormalValue(unsignedCompareBnd.vnBound);
1851 dsc.op2.kind = O2K_INVALID;
1852 dsc.op2.vn = ValueNumStore::NoVN;
1853
1854 AssertionIndex index = optAddAssertion(&dsc);
1855 if (unsignedCompareBnd.cmpOper == VNF_GE_UN)
1856 {
1857 // By default JTRUE generated assertions hold on the "jump" edge. We have i >= bnd but we're really
1858 // after i < bnd so we need to change the assertion edge to "next".
1859 return AssertionInfo::ForNextEdge(index);
1860 }
1861 return index;
1862 }
1863 // Cases where op1 holds the condition bound check and op2 is 0.
1864 // Loop condition like: "i < 100 == 0"
1865 // Assertion: "i < 100 == false"
1866 else if (hasTestAgainstZero && vnStore->IsVNConstantBound(op1VN))
1867 {
1868 AssertionDsc dsc;
1869 dsc.assertionKind = relop->gtOper == GT_EQ ? OAK_EQUAL : OAK_NOT_EQUAL;
1870 dsc.op1.kind = O1K_CONSTANT_LOOP_BND;
1871 dsc.op1.vn = op1VN;
1872 dsc.op2.kind = O2K_CONST_INT;
1873 dsc.op2.vn = vnStore->VNZeroForType(op2->TypeGet());
1874 dsc.op2.u1.iconVal = 0;
1875 dsc.op2.u1.iconFlags = 0;
1876 AssertionIndex index = optAddAssertion(&dsc);
1877 optCreateComplementaryAssertion(index, nullptr, nullptr);
1878 return index;
1879 }
1880 // Cases where op1 holds the lhs of the condition op2 holds rhs.
1881 // Loop condition like "i < 100"
1882 // Assertion: "i < 100 != 0"
1883 else if (vnStore->IsVNConstantBound(relopVN))
1884 {
1885 AssertionDsc dsc;
1886 dsc.assertionKind = OAK_NOT_EQUAL;
1887 dsc.op1.kind = O1K_CONSTANT_LOOP_BND;
1888 dsc.op1.vn = relopVN;
1889 dsc.op2.kind = O2K_CONST_INT;
1890 dsc.op2.vn = vnStore->VNZeroForType(TYP_INT);
1891 dsc.op2.u1.iconVal = 0;
1892 dsc.op2.u1.iconFlags = 0;
1893 AssertionIndex index = optAddAssertion(&dsc);
1894 optCreateComplementaryAssertion(index, nullptr, nullptr);
1895 return index;
1896 }
1897
1898 return NO_ASSERTION_INDEX;
1899}
1900
1901/*****************************************************************************
1902 *
1903 * Compute assertions for the JTrue node.
1904 */
1905AssertionInfo Compiler::optAssertionGenJtrue(GenTree* tree)
1906{
1907 // Only create assertions for JTRUE when we are in the global phase
1908 if (optLocalAssertionProp)
1909 {
1910 return NO_ASSERTION_INDEX;
1911 }
1912
1913 GenTree* relop = tree->gtOp.gtOp1;
1914 if ((relop->OperKind() & GTK_RELOP) == 0)
1915 {
1916 return NO_ASSERTION_INDEX;
1917 }
1918
1919 Compiler::optAssertionKind assertionKind = OAK_INVALID;
1920
1921 GenTree* op1 = relop->gtOp.gtOp1;
1922 GenTree* op2 = relop->gtOp.gtOp2;
1923
1924 AssertionInfo info = optCreateJTrueBoundsAssertion(tree);
1925 if (info.HasAssertion())
1926 {
1927 return info;
1928 }
1929
1930 // Find assertion kind.
1931 switch (relop->gtOper)
1932 {
1933 case GT_EQ:
1934 assertionKind = OAK_EQUAL;
1935 break;
1936 case GT_NE:
1937 assertionKind = OAK_NOT_EQUAL;
1938 break;
1939 default:
1940 // TODO-CQ: add other relop operands. Disabled for now to measure perf
1941 // and not occupy assertion table slots. We'll add them when used.
1942 return NO_ASSERTION_INDEX;
1943 }
1944
1945 // Check for op1 or op2 to be lcl var and if so, keep it in op1.
1946 if ((op1->gtOper != GT_LCL_VAR) && (op2->gtOper == GT_LCL_VAR))
1947 {
1948 jitstd::swap(op1, op2);
1949 }
1950 // If op1 is lcl and op2 is const or lcl, create assertion.
1951 if ((op1->gtOper == GT_LCL_VAR) &&
1952 ((op2->OperKind() & GTK_CONST) || (op2->gtOper == GT_LCL_VAR))) // Fix for Dev10 851483
1953 {
1954 return optCreateJtrueAssertions(op1, op2, assertionKind);
1955 }
1956
1957 // Check op1 and op2 for an indirection of a GT_LCL_VAR and keep it in op1.
1958 if (((op1->gtOper != GT_IND) || (op1->gtOp.gtOp1->gtOper != GT_LCL_VAR)) &&
1959 ((op2->gtOper == GT_IND) && (op2->gtOp.gtOp1->gtOper == GT_LCL_VAR)))
1960 {
1961 jitstd::swap(op1, op2);
1962 }
1963 // If op1 is ind, then extract op1's oper.
1964 if ((op1->gtOper == GT_IND) && (op1->gtOp.gtOp1->gtOper == GT_LCL_VAR))
1965 {
1966 return optCreateJtrueAssertions(op1, op2, assertionKind);
1967 }
1968
1969 // Look for a call to an IsInstanceOf helper compared to a nullptr
1970 if ((op2->gtOper != GT_CNS_INT) && (op1->gtOper == GT_CNS_INT))
1971 {
1972 jitstd::swap(op1, op2);
1973 }
1974 // Validate op1 and op2
1975 if ((op1->gtOper != GT_CALL) || (op1->gtCall.gtCallType != CT_HELPER) || (op1->TypeGet() != TYP_REF) || // op1
1976 (op2->gtOper != GT_CNS_INT) || (op2->gtIntCon.gtIconVal != 0)) // op2
1977 {
1978 return NO_ASSERTION_INDEX;
1979 }
1980 if (op1->gtCall.gtCallMethHnd != eeFindHelper(CORINFO_HELP_ISINSTANCEOFINTERFACE) &&
1981 op1->gtCall.gtCallMethHnd != eeFindHelper(CORINFO_HELP_ISINSTANCEOFARRAY) &&
1982 op1->gtCall.gtCallMethHnd != eeFindHelper(CORINFO_HELP_ISINSTANCEOFCLASS) &&
1983 op1->gtCall.gtCallMethHnd != eeFindHelper(CORINFO_HELP_ISINSTANCEOFANY))
1984 {
1985 return NO_ASSERTION_INDEX;
1986 }
1987
1988 op2 = op1->gtCall.gtCallLateArgs->gtOp.gtOp2;
1989 op1 = op1->gtCall.gtCallLateArgs;
1990
1991 // Reverse the assertion
1992 assert(assertionKind == OAK_EQUAL || assertionKind == OAK_NOT_EQUAL);
1993 assertionKind = (assertionKind == OAK_EQUAL) ? OAK_NOT_EQUAL : OAK_EQUAL;
1994
1995 if (op1->gtOp.gtOp1->gtOper == GT_LCL_VAR)
1996 {
1997 return optCreateJtrueAssertions(op1, op2, assertionKind);
1998 }
1999
2000 return NO_ASSERTION_INDEX;
2001}
2002
2003/*****************************************************************************
2004 *
2005 * Create an assertion on the phi node if some information can be gleaned
2006 * from all of the constituent phi operands.
2007 *
2008 */
2009AssertionIndex Compiler::optAssertionGenPhiDefn(GenTree* tree)
2010{
2011 if (!tree->IsPhiDefn())
2012 {
2013 return NO_ASSERTION_INDEX;
2014 }
2015
2016 GenTree* phi = tree->gtOp.gtOp2;
2017
2018 // Try to find if all phi arguments are known to be non-null.
2019 bool isNonNull = true;
2020 for (GenTreeArgList* args = phi->gtOp.gtOp1->AsArgList(); args != nullptr; args = args->Rest())
2021 {
2022 if (!vnStore->IsKnownNonNull(args->Current()->gtVNPair.GetConservative()))
2023 {
2024 isNonNull = false;
2025 break;
2026 }
2027 }
2028
2029 // All phi arguments are non-null implies phi rhs is non-null.
2030 if (isNonNull)
2031 {
2032 return optCreateAssertion(tree->gtOp.gtOp1, nullptr, OAK_NOT_EQUAL);
2033 }
2034 return NO_ASSERTION_INDEX;
2035}
2036
2037/*****************************************************************************
2038 *
2039 * If this statement creates a value assignment or assertion
2040 * then assign an index to the given value assignment by adding
2041 * it to the lookup table, if necessary.
2042 */
2043void Compiler::optAssertionGen(GenTree* tree)
2044{
2045 tree->ClearAssertion();
2046
2047 if (tree->gtFlags & GTF_COLON_COND)
2048 {
2049 return;
2050 }
2051
2052#ifdef DEBUG
2053 optAssertionPropCurrentTree = tree;
2054#endif
2055
2056 // For most of the assertions that we create below
2057 // the assertion is true after the tree is processed
2058 bool assertionProven = true;
2059 AssertionInfo assertionInfo;
2060 switch (tree->gtOper)
2061 {
2062 case GT_ASG:
2063 // VN takes care of non local assertions for assignments and data flow.
2064 if (optLocalAssertionProp)
2065 {
2066 assertionInfo = optCreateAssertion(tree->gtOp.gtOp1, tree->gtOp.gtOp2, OAK_EQUAL);
2067 }
2068 else
2069 {
2070 assertionInfo = optAssertionGenPhiDefn(tree);
2071 }
2072 break;
2073
2074 case GT_OBJ:
2075 case GT_BLK:
2076 case GT_DYN_BLK:
2077 case GT_IND:
2078 case GT_NULLCHECK:
2079 // All indirections create non-null assertions
2080 assertionInfo = optCreateAssertion(tree->AsIndir()->Addr(), nullptr, OAK_NOT_EQUAL);
2081 break;
2082
2083 case GT_ARR_LENGTH:
2084 // An array length is an indirection (but doesn't derive from GenTreeIndir).
2085 assertionInfo = optCreateAssertion(tree->AsArrLen()->ArrRef(), nullptr, OAK_NOT_EQUAL);
2086 break;
2087
2088 case GT_ARR_BOUNDS_CHECK:
2089 if (!optLocalAssertionProp)
2090 {
2091 assertionInfo = optCreateAssertion(tree, nullptr, OAK_NO_THROW);
2092 }
2093 break;
2094
2095 case GT_ARR_ELEM:
2096 // An array element reference can create a non-null assertion
2097 assertionInfo = optCreateAssertion(tree->gtArrElem.gtArrObj, nullptr, OAK_NOT_EQUAL);
2098 break;
2099
2100 case GT_CALL:
2101 // A virtual call can create a non-null assertion. We transform some virtual calls into non-virtual calls
2102 // with a GTF_CALL_NULLCHECK flag set.
2103 if ((tree->gtFlags & GTF_CALL_NULLCHECK) || tree->AsCall()->IsVirtual())
2104 {
2105 // Retrieve the 'this' arg
2106 GenTree* thisArg = gtGetThisArg(tree->AsCall());
2107#if defined(_TARGET_X86_) || defined(_TARGET_AMD64_) || defined(_TARGET_ARM_)
2108 if (thisArg == nullptr)
2109 {
2110 // For tail calls we lose the this pointer in the argument list but that's OK because a null check
2111 // was made explicit, so we get the assertion when we walk the GT_IND in the argument list.
2112 noway_assert(tree->gtCall.IsTailCall());
2113 break;
2114 }
2115#endif // _TARGET_X86_ || _TARGET_AMD64_ || _TARGET_ARM_
2116 noway_assert(thisArg != nullptr);
2117 assertionInfo = optCreateAssertion(thisArg, nullptr, OAK_NOT_EQUAL);
2118 }
2119 break;
2120
2121 case GT_CAST:
2122 // We only create this assertion for global assertion prop
2123 if (!optLocalAssertionProp)
2124 {
2125 // This represets an assertion that we would like to prove to be true. It is not actually a true
2126 // assertion.
2127 // If we can prove this assertion true then we can eliminate this cast.
2128 assertionInfo = optCreateAssertion(tree->gtOp.gtOp1, tree, OAK_SUBRANGE);
2129 assertionProven = false;
2130 }
2131 break;
2132
2133 case GT_JTRUE:
2134 assertionInfo = optAssertionGenJtrue(tree);
2135 break;
2136
2137 default:
2138 // All other gtOper node kinds, leave 'assertionIndex' = NO_ASSERTION_INDEX
2139 break;
2140 }
2141
2142 // For global assertion prop we must store the assertion number in the tree node
2143 if (assertionInfo.HasAssertion() && assertionProven && !optLocalAssertionProp)
2144 {
2145 tree->SetAssertionInfo(assertionInfo);
2146 }
2147}
2148
2149/*****************************************************************************
2150 *
2151 * Maps a complementary assertion to its original assertion so it can be
2152 * retrieved faster.
2153 */
2154void Compiler::optMapComplementary(AssertionIndex assertionIndex, AssertionIndex index)
2155{
2156 if (assertionIndex == NO_ASSERTION_INDEX || index == NO_ASSERTION_INDEX)
2157 {
2158 return;
2159 }
2160
2161 assert(assertionIndex <= optMaxAssertionCount);
2162 assert(index <= optMaxAssertionCount);
2163
2164 optComplementaryAssertionMap[assertionIndex] = index;
2165 optComplementaryAssertionMap[index] = assertionIndex;
2166}
2167
2168/*****************************************************************************
2169 *
2170 * Given an assertion index, return the assertion index of the complementary
2171 * assertion or 0 if one does not exist.
2172 */
2173AssertionIndex Compiler::optFindComplementary(AssertionIndex assertIndex)
2174{
2175 if (assertIndex == NO_ASSERTION_INDEX)
2176 {
2177 return NO_ASSERTION_INDEX;
2178 }
2179 AssertionDsc* inputAssertion = optGetAssertion(assertIndex);
2180
2181 // Must be an equal or not equal assertion.
2182 if (inputAssertion->assertionKind != OAK_EQUAL && inputAssertion->assertionKind != OAK_NOT_EQUAL)
2183 {
2184 return NO_ASSERTION_INDEX;
2185 }
2186
2187 AssertionIndex index = optComplementaryAssertionMap[assertIndex];
2188 if (index != NO_ASSERTION_INDEX && index <= optAssertionCount)
2189 {
2190 return index;
2191 }
2192
2193 optAssertionKind complementaryAssertionKind =
2194 (inputAssertion->assertionKind == OAK_EQUAL) ? OAK_NOT_EQUAL : OAK_EQUAL;
2195 for (AssertionIndex index = 1; index <= optAssertionCount; ++index)
2196 {
2197 // Make sure assertion kinds are complementary and op1, op2 kinds match.
2198 AssertionDsc* curAssertion = optGetAssertion(index);
2199 if (curAssertion->Complementary(inputAssertion, !optLocalAssertionProp))
2200 {
2201 optMapComplementary(assertIndex, index);
2202 return index;
2203 }
2204 }
2205 return NO_ASSERTION_INDEX;
2206}
2207
2208/*****************************************************************************
2209 *
2210 * Given a lclNum and a toType, return assertion index of the assertion that
2211 * claims that a variable's value is always a valid subrange of toType.
2212 * Thus we can discard or omit a cast to toType. Returns NO_ASSERTION_INDEX
2213 * if one such assertion could not be found in "assertions."
2214 */
2215
2216AssertionIndex Compiler::optAssertionIsSubrange(GenTree* tree, var_types toType, ASSERT_VALARG_TP assertions)
2217{
2218 if (!optLocalAssertionProp && BitVecOps::IsEmpty(apTraits, assertions))
2219 {
2220 return NO_ASSERTION_INDEX;
2221 }
2222
2223 for (AssertionIndex index = 1; index <= optAssertionCount; index++)
2224 {
2225 AssertionDsc* curAssertion = optGetAssertion(index);
2226 if ((optLocalAssertionProp ||
2227 BitVecOps::IsMember(apTraits, assertions, index - 1)) && // either local prop or use propagated assertions
2228 (curAssertion->assertionKind == OAK_SUBRANGE) &&
2229 (curAssertion->op1.kind == O1K_LCLVAR))
2230 {
2231 // For local assertion prop use comparison on locals, and use comparison on vns for global prop.
2232 bool isEqual = optLocalAssertionProp
2233 ? (curAssertion->op1.lcl.lclNum == tree->AsLclVarCommon()->GetLclNum())
2234 : (curAssertion->op1.vn == vnStore->VNConservativeNormalValue(tree->gtVNPair));
2235 if (!isEqual)
2236 {
2237 continue;
2238 }
2239
2240 // Make sure the toType is within current assertion's bounds.
2241 switch (toType)
2242 {
2243 case TYP_BYTE:
2244 case TYP_UBYTE:
2245 case TYP_SHORT:
2246 case TYP_USHORT:
2247 if ((curAssertion->op2.u2.loBound < AssertionDsc::GetLowerBoundForIntegralType(toType)) ||
2248 (curAssertion->op2.u2.hiBound > AssertionDsc::GetUpperBoundForIntegralType(toType)))
2249 {
2250 continue;
2251 }
2252 break;
2253
2254 case TYP_UINT:
2255 if (curAssertion->op2.u2.loBound < AssertionDsc::GetLowerBoundForIntegralType(toType))
2256 {
2257 continue;
2258 }
2259 break;
2260
2261 case TYP_INT:
2262 break;
2263
2264 default:
2265 continue;
2266 }
2267 return index;
2268 }
2269 }
2270 return NO_ASSERTION_INDEX;
2271}
2272
2273/**********************************************************************************
2274 *
2275 * Given a "tree" that is usually arg1 of a isinst/cast kind of GT_CALL (a class
2276 * handle), and "methodTableArg" which is a const int (a class handle), then search
2277 * if there is an assertion in "assertions", that asserts the equality of the two
2278 * class handles and then returns the index of the assertion. If one such assertion
2279 * could not be found, then it returns NO_ASSERTION_INDEX.
2280 *
2281 */
2282AssertionIndex Compiler::optAssertionIsSubtype(GenTree* tree, GenTree* methodTableArg, ASSERT_VALARG_TP assertions)
2283{
2284 if (!optLocalAssertionProp && BitVecOps::IsEmpty(apTraits, assertions))
2285 {
2286 return NO_ASSERTION_INDEX;
2287 }
2288 for (AssertionIndex index = 1; index <= optAssertionCount; index++)
2289 {
2290 if (!optLocalAssertionProp && !BitVecOps::IsMember(apTraits, assertions, index - 1))
2291 {
2292 continue;
2293 }
2294
2295 AssertionDsc* curAssertion = optGetAssertion(index);
2296 if (curAssertion->assertionKind != OAK_EQUAL ||
2297 (curAssertion->op1.kind != O1K_SUBTYPE && curAssertion->op1.kind != O1K_EXACT_TYPE))
2298 {
2299 continue;
2300 }
2301
2302 // If local assertion prop use "lcl" based comparison, if global assertion prop use vn based comparison.
2303 if ((optLocalAssertionProp) ? (curAssertion->op1.lcl.lclNum != tree->AsLclVarCommon()->GetLclNum())
2304 : (curAssertion->op1.vn != vnStore->VNConservativeNormalValue(tree->gtVNPair)))
2305 {
2306 continue;
2307 }
2308
2309 if (curAssertion->op2.kind == O2K_IND_CNS_INT)
2310 {
2311 if (methodTableArg->gtOper != GT_IND)
2312 {
2313 continue;
2314 }
2315 methodTableArg = methodTableArg->gtOp.gtOp1;
2316 }
2317 else if (curAssertion->op2.kind != O2K_CONST_INT)
2318 {
2319 continue;
2320 }
2321
2322 ssize_t methodTableVal = 0;
2323 unsigned iconFlags = 0;
2324 if (!optIsTreeKnownIntValue(!optLocalAssertionProp, methodTableArg, &methodTableVal, &iconFlags))
2325 {
2326 continue;
2327 }
2328
2329 if (curAssertion->op2.u1.iconVal == methodTableVal)
2330 {
2331 return index;
2332 }
2333 }
2334 return NO_ASSERTION_INDEX;
2335}
2336
2337//------------------------------------------------------------------------------
2338// optVNConstantPropOnTree: Substitutes tree with an evaluated constant while
2339// managing ref-counts and side-effects.
2340//
2341// Arguments:
2342// block - The block containing the tree.
2343// stmt - The statement in the block containing the tree.
2344// tree - The tree node whose value is known at compile time.
2345// The tree should have a constant value number.
2346//
2347// Return Value:
2348// Returns a potentially new or a transformed tree node.
2349// Returns nullptr when no transformation is possible.
2350//
2351// Description:
2352// Transforms a tree node if its result evaluates to a constant. The
2353// transformation can be a "ChangeOper" to a constant or a new constant node
2354// with extracted side-effects.
2355//
2356// Before replacing or substituting the "tree" with a constant, extracts any
2357// side effects from the "tree" and creates a comma separated side effect list
2358// and then appends the transformed node at the end of the list.
2359// This comma separated list is then returned.
2360//
2361// For JTrue nodes, side effects are not put into a comma separated list. If
2362// the relop will evaluate to "true" or "false" statically, then the side-effects
2363// will be put into new statements, presuming the JTrue will be folded away.
2364//
2365// The ref-counts of any variables in the tree being replaced, will be
2366// appropriately decremented. The ref-counts of variables in the side-effect
2367// nodes will be retained.
2368//
2369GenTree* Compiler::optVNConstantPropOnTree(BasicBlock* block, GenTree* stmt, GenTree* tree)
2370{
2371 if (tree->OperGet() == GT_JTRUE)
2372 {
2373 // Treat JTRUE separately to extract side effects into respective statements rather
2374 // than using a COMMA separated op1.
2375 return optVNConstantPropOnJTrue(block, stmt, tree);
2376 }
2377 // If relop is part of JTRUE, this should be optimized as part of the parent JTRUE.
2378 // Or if relop is part of QMARK or anything else, we simply bail here.
2379 else if (tree->OperIsCompare() && (tree->gtFlags & GTF_RELOP_JMP_USED))
2380 {
2381 return nullptr;
2382 }
2383
2384 // We want to use the Normal ValueNumber when checking for constants.
2385 ValueNum vnCns = vnStore->VNConservativeNormalValue(tree->gtVNPair);
2386 ValueNum vnLib = vnStore->VNLiberalNormalValue(tree->gtVNPair);
2387
2388 // Check if node evaluates to a constant.
2389 if (!vnStore->IsVNConstant(vnCns))
2390 {
2391 return nullptr;
2392 }
2393
2394 GenTree* newTree = tree;
2395 GenTree* sideEffList = nullptr;
2396 switch (vnStore->TypeOfVN(vnCns))
2397 {
2398 case TYP_FLOAT:
2399 {
2400 float value = vnStore->ConstantValue<float>(vnCns);
2401
2402 if (tree->TypeGet() == TYP_INT)
2403 {
2404 // Same sized reinterpretation of bits to integer
2405 newTree = optPrepareTreeForReplacement(tree, tree);
2406 tree->ChangeOperConst(GT_CNS_INT);
2407 tree->gtIntCon.gtIconVal = *(reinterpret_cast<int*>(&value));
2408 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2409 }
2410 else
2411 {
2412 // Implicit assignment conversion to float or double
2413 assert(varTypeIsFloating(tree->TypeGet()));
2414
2415 newTree = optPrepareTreeForReplacement(tree, tree);
2416 tree->ChangeOperConst(GT_CNS_DBL);
2417 tree->gtDblCon.gtDconVal = value;
2418 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2419 }
2420 break;
2421 }
2422
2423 case TYP_DOUBLE:
2424 {
2425 double value = vnStore->ConstantValue<double>(vnCns);
2426
2427 if (tree->TypeGet() == TYP_LONG)
2428 {
2429 // Same sized reinterpretation of bits to long
2430 newTree = optPrepareTreeForReplacement(tree, tree);
2431 tree->ChangeOperConst(GT_CNS_NATIVELONG);
2432 tree->gtIntConCommon.SetLngValue(*(reinterpret_cast<INT64*>(&value)));
2433 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2434 }
2435 else
2436 {
2437 // Implicit assignment conversion to float or double
2438 assert(varTypeIsFloating(tree->TypeGet()));
2439
2440 newTree = optPrepareTreeForReplacement(tree, tree);
2441 tree->ChangeOperConst(GT_CNS_DBL);
2442 tree->gtDblCon.gtDconVal = value;
2443 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2444 }
2445 break;
2446 }
2447
2448 case TYP_LONG:
2449 {
2450 INT64 value = vnStore->ConstantValue<INT64>(vnCns);
2451#ifdef _TARGET_64BIT_
2452 if (vnStore->IsVNHandle(vnCns))
2453 {
2454 // Don't perform constant folding that involves a handle that needs
2455 // to be recorded as a relocation with the VM.
2456 if (!opts.compReloc)
2457 {
2458 newTree = gtNewIconHandleNode(value, vnStore->GetHandleFlags(vnCns));
2459 newTree->gtVNPair = ValueNumPair(vnLib, vnCns);
2460 newTree = optPrepareTreeForReplacement(tree, newTree);
2461 }
2462 }
2463 else
2464#endif
2465 {
2466 switch (tree->TypeGet())
2467 {
2468 case TYP_INT:
2469 // Implicit assignment conversion to smaller integer
2470 newTree = optPrepareTreeForReplacement(tree, tree);
2471 tree->ChangeOperConst(GT_CNS_INT);
2472 tree->gtIntCon.gtIconVal = (int)value;
2473 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2474 break;
2475
2476 case TYP_LONG:
2477 // Same type no conversion required
2478 newTree = optPrepareTreeForReplacement(tree, tree);
2479 tree->ChangeOperConst(GT_CNS_NATIVELONG);
2480 tree->gtIntConCommon.SetLngValue(value);
2481 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2482 break;
2483
2484 case TYP_FLOAT:
2485 // No implicit conversions from long to float and value numbering will
2486 // not propagate through memory reinterpretations of different size.
2487 unreached();
2488 break;
2489
2490 case TYP_DOUBLE:
2491 // Same sized reinterpretation of bits to double
2492 newTree = optPrepareTreeForReplacement(tree, tree);
2493 tree->ChangeOperConst(GT_CNS_DBL);
2494 tree->gtDblCon.gtDconVal = *(reinterpret_cast<double*>(&value));
2495 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2496 break;
2497
2498 default:
2499 return nullptr;
2500 }
2501 }
2502 }
2503 break;
2504
2505 case TYP_REF:
2506 if (tree->TypeGet() != TYP_REF)
2507 {
2508 return nullptr;
2509 }
2510
2511 assert(vnStore->ConstantValue<size_t>(vnCns) == 0);
2512 newTree = optPrepareTreeForReplacement(tree, tree);
2513 tree->ChangeOperConst(GT_CNS_INT);
2514 tree->gtIntCon.gtIconVal = 0;
2515 tree->ClearIconHandleMask();
2516 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2517 break;
2518
2519 case TYP_INT:
2520 {
2521 int value = vnStore->ConstantValue<int>(vnCns);
2522#ifndef _TARGET_64BIT_
2523 if (vnStore->IsVNHandle(vnCns))
2524 {
2525 // Don't perform constant folding that involves a handle that needs
2526 // to be recorded as a relocation with the VM.
2527 if (!opts.compReloc)
2528 {
2529 newTree = gtNewIconHandleNode(value, vnStore->GetHandleFlags(vnCns));
2530 newTree->gtVNPair = ValueNumPair(vnLib, vnCns);
2531 newTree = optPrepareTreeForReplacement(tree, newTree);
2532 }
2533 }
2534 else
2535#endif
2536 {
2537 switch (tree->TypeGet())
2538 {
2539 case TYP_REF:
2540 case TYP_INT:
2541 // Same type no conversion required
2542 newTree = optPrepareTreeForReplacement(tree, tree);
2543 tree->ChangeOperConst(GT_CNS_INT);
2544 tree->gtIntCon.gtIconVal = value;
2545 tree->ClearIconHandleMask();
2546 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2547 break;
2548
2549 case TYP_LONG:
2550 // Implicit assignment conversion to larger integer
2551 newTree = optPrepareTreeForReplacement(tree, tree);
2552 tree->ChangeOperConst(GT_CNS_NATIVELONG);
2553 tree->gtIntConCommon.SetLngValue(value);
2554 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2555 break;
2556
2557 case TYP_FLOAT:
2558 // Same sized reinterpretation of bits to float
2559 newTree = optPrepareTreeForReplacement(tree, tree);
2560 tree->ChangeOperConst(GT_CNS_DBL);
2561 tree->gtDblCon.gtDconVal = *(reinterpret_cast<float*>(&value));
2562 tree->gtVNPair = ValueNumPair(vnLib, vnCns);
2563 break;
2564
2565 case TYP_DOUBLE:
2566 // No implicit conversions from int to double and value numbering will
2567 // not propagate through memory reinterpretations of different size.
2568 unreached();
2569 break;
2570
2571 default:
2572 return nullptr;
2573 }
2574 }
2575 }
2576 break;
2577
2578 default:
2579 return nullptr;
2580 }
2581 return newTree;
2582}
2583
2584/*******************************************************************************************************
2585 *
2586 * Perform constant propagation on a tree given the "curAssertion" is true at the point of the "tree."
2587 *
2588 */
2589GenTree* Compiler::optConstantAssertionProp(AssertionDsc* curAssertion,
2590 GenTree* tree,
2591 GenTree* stmt DEBUGARG(AssertionIndex index))
2592{
2593 unsigned lclNum = tree->gtLclVarCommon.gtLclNum;
2594
2595 if (lclNumIsCSE(lclNum))
2596 {
2597 return nullptr;
2598 }
2599
2600 GenTree* newTree = tree;
2601
2602 // Update 'newTree' with the new value from our table
2603 // Typically newTree == tree and we are updating the node in place
2604 switch (curAssertion->op2.kind)
2605 {
2606 case O2K_CONST_DOUBLE:
2607 // There could be a positive zero and a negative zero, so don't propagate zeroes.
2608 if (curAssertion->op2.dconVal == 0.0)
2609 {
2610 return nullptr;
2611 }
2612 newTree->ChangeOperConst(GT_CNS_DBL);
2613 newTree->gtDblCon.gtDconVal = curAssertion->op2.dconVal;
2614 break;
2615
2616 case O2K_CONST_LONG:
2617 if (newTree->gtType == TYP_LONG)
2618 {
2619 newTree->ChangeOperConst(GT_CNS_NATIVELONG);
2620 newTree->gtIntConCommon.SetLngValue(curAssertion->op2.lconVal);
2621 }
2622 else
2623 {
2624 newTree->ChangeOperConst(GT_CNS_INT);
2625 newTree->gtIntCon.gtIconVal = (int)curAssertion->op2.lconVal;
2626 newTree->gtType = TYP_INT;
2627 }
2628 break;
2629
2630 case O2K_CONST_INT:
2631 if (curAssertion->op2.u1.iconFlags & GTF_ICON_HDL_MASK)
2632 {
2633 // Here we have to allocate a new 'large' node to replace the old one
2634 newTree = gtNewIconHandleNode(curAssertion->op2.u1.iconVal,
2635 curAssertion->op2.u1.iconFlags & GTF_ICON_HDL_MASK);
2636 }
2637 else
2638 {
2639 bool isArrIndex = ((tree->gtFlags & GTF_VAR_ARR_INDEX) != 0);
2640 // If we have done constant propagation of a struct type, it is only valid for zero-init,
2641 // and we have to ensure that we have the right zero for the type.
2642 if (varTypeIsStruct(tree))
2643 {
2644 assert(curAssertion->op2.u1.iconVal == 0);
2645 }
2646#ifdef FEATURE_SIMD
2647 if (varTypeIsSIMD(tree))
2648 {
2649 LclVarDsc* varDsc = lvaGetDesc(lclNum);
2650 var_types simdType = tree->TypeGet();
2651 assert(varDsc->TypeGet() == simdType);
2652 var_types baseType = varDsc->lvBaseType;
2653 newTree = gtGetSIMDZero(simdType, baseType, varDsc->lvVerTypeInfo.GetClassHandle());
2654 if (newTree == nullptr)
2655 {
2656 return nullptr;
2657 }
2658 }
2659 else
2660#endif // FEATURE_SIMD
2661 {
2662 newTree->ChangeOperConst(GT_CNS_INT);
2663 newTree->gtIntCon.gtIconVal = curAssertion->op2.u1.iconVal;
2664 newTree->ClearIconHandleMask();
2665 }
2666 // If we're doing an array index address, assume any constant propagated contributes to the index.
2667 if (isArrIndex)
2668 {
2669 newTree->gtIntCon.gtFieldSeq =
2670 GetFieldSeqStore()->CreateSingleton(FieldSeqStore::ConstantIndexPseudoField);
2671 }
2672 newTree->gtFlags &= ~GTF_VAR_ARR_INDEX;
2673 }
2674
2675 // Constant ints are of type TYP_INT, not any of the short forms.
2676 if (varTypeIsIntegral(newTree->TypeGet()))
2677 {
2678#ifdef _TARGET_64BIT_
2679 var_types newType = (var_types)((curAssertion->op2.u1.iconFlags & 1) ? TYP_LONG : TYP_INT);
2680 if (newTree->TypeGet() != newType)
2681 {
2682 noway_assert(newTree->gtType != TYP_REF);
2683 newTree->gtType = newType;
2684 }
2685#else
2686 if (newTree->TypeGet() != TYP_INT)
2687 {
2688 noway_assert(newTree->gtType != TYP_REF && newTree->gtType != TYP_LONG);
2689 newTree->gtType = TYP_INT;
2690 }
2691#endif
2692 }
2693 break;
2694
2695 default:
2696 return nullptr;
2697 }
2698
2699 if (!optLocalAssertionProp)
2700 {
2701 assert(newTree->OperIsConst()); // We should have a simple Constant node for newTree
2702 assert(vnStore->IsVNConstant(curAssertion->op2.vn)); // The value number stored for op2 should be a valid
2703 // VN representing the constant
2704 newTree->gtVNPair.SetBoth(curAssertion->op2.vn); // Set the ValueNumPair to the constant VN from op2
2705 // of the assertion
2706 }
2707
2708#ifdef DEBUG
2709 if (verbose)
2710 {
2711 printf("\nAssertion prop in " FMT_BB ":\n", compCurBB->bbNum);
2712 optPrintAssertion(curAssertion, index);
2713 gtDispTree(newTree, nullptr, nullptr, true);
2714 }
2715#endif
2716
2717 return optAssertionProp_Update(newTree, tree, stmt);
2718}
2719
2720/*******************************************************************************************************
2721 *
2722 * Called in the context of an existing copy assertion which makes an "==" assertion on "lclVar" and
2723 * "copyVar." Before substituting "copyVar" for "lclVar", we make sure using "copy" doesn't widen access.
2724 *
2725 */
2726bool Compiler::optAssertionProp_LclVarTypeCheck(GenTree* tree, LclVarDsc* lclVarDsc, LclVarDsc* copyVarDsc)
2727{
2728 /*
2729 Small struct field locals are stored using the exact width and loaded widened
2730 (i.e. lvNormalizeOnStore==false lvNormalizeOnLoad==true),
2731 because the field locals might end up embedded in the parent struct local with the exact width.
2732
2733 In other words, a store to a short field local should always done using an exact width store
2734
2735 [00254538] 0x0009 ------------ const int 0x1234
2736 [002545B8] 0x000B -A--G--NR--- = short
2737 [00254570] 0x000A D------N---- lclVar short V43 tmp40
2738
2739 mov word ptr [L_043], 0x1234
2740
2741 Now, if we copy prop, say a short field local V43, to another short local V34
2742 for the following tree:
2743
2744 [04E18650] 0x0001 ------------ lclVar int V34 tmp31
2745 [04E19714] 0x0002 -A---------- = int
2746 [04E196DC] 0x0001 D------N---- lclVar int V36 tmp33
2747
2748 We will end with this tree:
2749
2750 [04E18650] 0x0001 ------------ lclVar int V43 tmp40
2751 [04E19714] 0x0002 -A-----NR--- = int
2752 [04E196DC] 0x0001 D------N---- lclVar int V36 tmp33 EAX
2753
2754 And eventually causing a fetch of 4-byte out from [L_043] :(
2755 mov EAX, dword ptr [L_043]
2756
2757 The following check is to make sure we only perform the copy prop
2758 when we don't retrieve the wider value.
2759 */
2760
2761 if (copyVarDsc->lvIsStructField)
2762 {
2763 var_types varType = (var_types)copyVarDsc->lvType;
2764 // Make sure we don't retrieve the wider value.
2765 return !varTypeIsSmall(varType) || (varType == tree->TypeGet());
2766 }
2767 // Called in the context of a single copy assertion, so the types should have been
2768 // taken care by the assertion gen logic for other cases. Just return true.
2769 return true;
2770}
2771
2772/**********************************************************************************
2773 *
2774 * Perform copy assertion propagation when the lclNum and ssaNum of the "tree" match
2775 * the "curAssertion."
2776 *
2777 */
2778GenTree* Compiler::optCopyAssertionProp(AssertionDsc* curAssertion,
2779 GenTree* tree,
2780 GenTree* stmt DEBUGARG(AssertionIndex index))
2781{
2782 const AssertionDsc::AssertionDscOp1& op1 = curAssertion->op1;
2783 const AssertionDsc::AssertionDscOp2& op2 = curAssertion->op2;
2784
2785 noway_assert(op1.lcl.lclNum != op2.lcl.lclNum);
2786
2787 unsigned lclNum = tree->gtLclVarCommon.GetLclNum();
2788
2789 // Make sure one of the lclNum of the assertion matches with that of the tree.
2790 if (op1.lcl.lclNum != lclNum && op2.lcl.lclNum != lclNum)
2791 {
2792 return nullptr;
2793 }
2794
2795 // Extract the matching lclNum and ssaNum.
2796 unsigned copyLclNum = (op1.lcl.lclNum == lclNum) ? op2.lcl.lclNum : op1.lcl.lclNum;
2797 unsigned copySsaNum = BAD_VAR_NUM;
2798 if (!optLocalAssertionProp)
2799 {
2800 // Extract the ssaNum of the matching lclNum.
2801 unsigned ssaNum = (op1.lcl.lclNum == lclNum) ? op1.lcl.ssaNum : op2.lcl.ssaNum;
2802 copySsaNum = (op1.lcl.lclNum == lclNum) ? op2.lcl.ssaNum : op1.lcl.ssaNum;
2803
2804 if (ssaNum != tree->AsLclVarCommon()->GetSsaNum())
2805 {
2806 return nullptr;
2807 }
2808 }
2809
2810 LclVarDsc* copyVarDsc = &lvaTable[copyLclNum];
2811 LclVarDsc* lclVarDsc = &lvaTable[lclNum];
2812
2813 // Make sure the types are compatible.
2814 if (!optAssertionProp_LclVarTypeCheck(tree, lclVarDsc, copyVarDsc))
2815 {
2816 return nullptr;
2817 }
2818
2819 // Make sure we can perform this copy prop.
2820 if (optCopyProp_LclVarScore(lclVarDsc, copyVarDsc, curAssertion->op1.lcl.lclNum == lclNum) <= 0)
2821 {
2822 return nullptr;
2823 }
2824
2825 tree->gtLclVarCommon.SetSsaNum(copySsaNum);
2826 tree->gtLclVarCommon.SetLclNum(copyLclNum);
2827
2828#ifdef DEBUG
2829 if (verbose)
2830 {
2831 printf("\nAssertion prop in " FMT_BB ":\n", compCurBB->bbNum);
2832 optPrintAssertion(curAssertion, index);
2833 gtDispTree(tree, nullptr, nullptr, true);
2834 }
2835#endif
2836
2837 // Update and morph the tree.
2838 return optAssertionProp_Update(tree, tree, stmt);
2839}
2840
2841/*****************************************************************************
2842 *
2843 * Given a tree consisting of a just a LclVar and a set of available assertions
2844 * we try to propagate an assertion and modify the LclVar tree if we can.
2845 * We pass in the root of the tree via 'stmt', for local copy prop 'stmt' will
2846 * be nullptr. Returns the modified tree, or nullptr if no assertion prop took place.
2847 */
2848
2849GenTree* Compiler::optAssertionProp_LclVar(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
2850{
2851 assert(tree->gtOper == GT_LCL_VAR);
2852 // If we have a var definition then bail or
2853 // If this is the address of the var then it will have the GTF_DONT_CSE
2854 // flag set and we don't want to to assertion prop on it.
2855 if (tree->gtFlags & (GTF_VAR_DEF | GTF_DONT_CSE))
2856 {
2857 return nullptr;
2858 }
2859
2860 BitVecOps::Iter iter(apTraits, assertions);
2861 unsigned index = 0;
2862 while (iter.NextElem(&index))
2863 {
2864 AssertionIndex assertionIndex = GetAssertionIndex(index);
2865 if (assertionIndex > optAssertionCount)
2866 {
2867 break;
2868 }
2869 // See if the variable is equal to a constant or another variable.
2870 AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
2871 if (curAssertion->assertionKind != OAK_EQUAL || curAssertion->op1.kind != O1K_LCLVAR)
2872 {
2873 continue;
2874 }
2875
2876 // Copy prop.
2877 if (curAssertion->op2.kind == O2K_LCLVAR_COPY)
2878 {
2879 // Cannot do copy prop during global assertion prop because of no knowledge
2880 // of kill sets. We will still make a == b copy assertions during the global phase to allow
2881 // for any implied assertions that can be retrieved. Because implied assertions look for
2882 // matching SSA numbers (i.e., if a0 == b1 and b1 == c0 then a0 == c0) they don't need kill sets.
2883 if (optLocalAssertionProp)
2884 {
2885 // Perform copy assertion prop.
2886 GenTree* newTree = optCopyAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
2887 if (newTree == nullptr)
2888 {
2889 // Skip and try next assertion.
2890 continue;
2891 }
2892 return newTree;
2893 }
2894 }
2895 // Constant prop (for local assertion prop.)
2896 // The case where the tree type could be different than the LclVar type is caused by
2897 // gtFoldExpr, specifically the case of a cast, where the fold operation changes the type of the LclVar
2898 // node. In such a case is not safe to perform the substitution since later on the JIT will assert mismatching
2899 // types between trees.
2900 else if (curAssertion->op1.lcl.lclNum == tree->gtLclVarCommon.GetLclNum() &&
2901 tree->gtType == lvaTable[tree->gtLclVarCommon.GetLclNum()].lvType)
2902 {
2903 // If local assertion prop just, perform constant prop.
2904 if (optLocalAssertionProp)
2905 {
2906 return optConstantAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
2907 }
2908 // If global assertion, perform constant propagation only if the VN's match and the lcl is non-CSE.
2909 else if (curAssertion->op1.vn == vnStore->VNConservativeNormalValue(tree->gtVNPair))
2910 {
2911#if FEATURE_ANYCSE
2912 // Don't perform constant prop for CSE LclVars
2913 if (!lclNumIsCSE(tree->AsLclVarCommon()->GetLclNum()))
2914#endif
2915 {
2916 return optConstantAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
2917 }
2918 }
2919 }
2920 }
2921 return nullptr;
2922}
2923
2924/*****************************************************************************
2925 *
2926 * Given a set of "assertions" to search, find an assertion that matches
2927 * op1Kind and lclNum, op2Kind and the constant value and is either equal or
2928 * not equal assertion.
2929 */
2930AssertionIndex Compiler::optLocalAssertionIsEqualOrNotEqual(
2931 optOp1Kind op1Kind, unsigned lclNum, optOp2Kind op2Kind, ssize_t cnsVal, ASSERT_VALARG_TP assertions)
2932{
2933 noway_assert((op1Kind == O1K_LCLVAR) || (op1Kind == O1K_EXACT_TYPE) || (op1Kind == O1K_SUBTYPE));
2934 noway_assert((op2Kind == O2K_CONST_INT) || (op2Kind == O2K_IND_CNS_INT));
2935 if (!optLocalAssertionProp && BitVecOps::IsEmpty(apTraits, assertions))
2936 {
2937 return NO_ASSERTION_INDEX;
2938 }
2939
2940 for (AssertionIndex index = 1; index <= optAssertionCount; ++index)
2941 {
2942 AssertionDsc* curAssertion = optGetAssertion(index);
2943 if (optLocalAssertionProp || BitVecOps::IsMember(apTraits, assertions, index - 1))
2944 {
2945 if ((curAssertion->assertionKind != OAK_EQUAL) && (curAssertion->assertionKind != OAK_NOT_EQUAL))
2946 {
2947 continue;
2948 }
2949
2950 if ((curAssertion->op1.kind == op1Kind) && (curAssertion->op1.lcl.lclNum == lclNum) &&
2951 (curAssertion->op2.kind == op2Kind))
2952 {
2953 bool constantIsEqual = (curAssertion->op2.u1.iconVal == cnsVal);
2954 bool assertionIsEqual = (curAssertion->assertionKind == OAK_EQUAL);
2955
2956 if (constantIsEqual || assertionIsEqual)
2957 {
2958 return index;
2959 }
2960 }
2961 }
2962 }
2963 return NO_ASSERTION_INDEX;
2964}
2965
2966/*****************************************************************************
2967 *
2968 * Given a set of "assertions" to search for, find an assertion that is either
2969 * "op1" == "op2" or "op1" != "op2." Does a value number based comparison.
2970 *
2971 */
2972AssertionIndex Compiler::optGlobalAssertionIsEqualOrNotEqual(ASSERT_VALARG_TP assertions, GenTree* op1, GenTree* op2)
2973{
2974 if (BitVecOps::IsEmpty(apTraits, assertions))
2975 {
2976 return NO_ASSERTION_INDEX;
2977 }
2978 BitVecOps::Iter iter(apTraits, assertions);
2979 unsigned index = 0;
2980 while (iter.NextElem(&index))
2981 {
2982 AssertionIndex assertionIndex = GetAssertionIndex(index);
2983 if (assertionIndex > optAssertionCount)
2984 {
2985 break;
2986 }
2987 AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
2988 if ((curAssertion->assertionKind != OAK_EQUAL && curAssertion->assertionKind != OAK_NOT_EQUAL))
2989 {
2990 continue;
2991 }
2992
2993 if ((curAssertion->op1.vn == vnStore->VNConservativeNormalValue(op1->gtVNPair)) &&
2994 (curAssertion->op2.vn == vnStore->VNConservativeNormalValue(op2->gtVNPair)))
2995 {
2996 return assertionIndex;
2997 }
2998 }
2999 return NO_ASSERTION_INDEX;
3000}
3001
3002/*****************************************************************************
3003 *
3004 * Given a set of "assertions" to search for, find an assertion that is either
3005 * op == 0 or op != 0
3006 *
3007 */
3008AssertionIndex Compiler::optGlobalAssertionIsEqualOrNotEqualZero(ASSERT_VALARG_TP assertions, GenTree* op1)
3009{
3010 if (BitVecOps::IsEmpty(apTraits, assertions))
3011 {
3012 return NO_ASSERTION_INDEX;
3013 }
3014 BitVecOps::Iter iter(apTraits, assertions);
3015 unsigned index = 0;
3016 while (iter.NextElem(&index))
3017 {
3018 AssertionIndex assertionIndex = GetAssertionIndex(index);
3019 if (assertionIndex > optAssertionCount)
3020 {
3021 break;
3022 }
3023 AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
3024 if ((curAssertion->assertionKind != OAK_EQUAL && curAssertion->assertionKind != OAK_NOT_EQUAL))
3025 {
3026 continue;
3027 }
3028
3029 if ((curAssertion->op1.vn == vnStore->VNConservativeNormalValue(op1->gtVNPair)) &&
3030 (curAssertion->op2.vn == vnStore->VNZeroForType(op1->TypeGet())))
3031 {
3032 return assertionIndex;
3033 }
3034 }
3035 return NO_ASSERTION_INDEX;
3036}
3037
3038/*****************************************************************************
3039 *
3040 * Given a tree consisting of a RelOp and a set of available assertions
3041 * we try to propagate an assertion and modify the RelOp tree if we can.
3042 * We pass in the root of the tree via 'stmt', for local copy prop 'stmt' will be nullptr
3043 * Returns the modified tree, or nullptr if no assertion prop took place
3044 */
3045
3046GenTree* Compiler::optAssertionProp_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3047{
3048 assert(tree->OperKind() & GTK_RELOP);
3049
3050 if (!optLocalAssertionProp)
3051 {
3052 // If global assertion prop then use value numbering.
3053 return optAssertionPropGlobal_RelOp(assertions, tree, stmt);
3054 }
3055
3056 //
3057 // Currently only GT_EQ or GT_NE are supported Relops for local AssertionProp
3058 //
3059
3060 if ((tree->gtOper != GT_EQ) && (tree->gtOper != GT_NE))
3061 {
3062 return nullptr;
3063 }
3064
3065 // If local assertion prop then use variable based prop.
3066 return optAssertionPropLocal_RelOp(assertions, tree, stmt);
3067}
3068
3069/*************************************************************************************
3070 *
3071 * Given the set of "assertions" to look up a relop assertion about the relop "tree",
3072 * perform Value numbering based relop assertion propagation on the tree.
3073 *
3074 */
3075GenTree* Compiler::optAssertionPropGlobal_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3076{
3077 GenTree* newTree = tree;
3078 GenTree* op1 = tree->gtOp.gtOp1;
3079 GenTree* op2 = tree->gtOp.gtOp2;
3080
3081 // Look for assertions of the form (tree EQ/NE 0)
3082 AssertionIndex index = optGlobalAssertionIsEqualOrNotEqualZero(assertions, tree);
3083
3084 if (index != NO_ASSERTION_INDEX)
3085 {
3086 // We know that this relop is either 0 or != 0 (1)
3087 AssertionDsc* curAssertion = optGetAssertion(index);
3088
3089#ifdef DEBUG
3090 if (verbose)
3091 {
3092 printf("\nVN relop based constant assertion prop in " FMT_BB ":\n", compCurBB->bbNum);
3093 printf("Assertion index=#%02u: ", index);
3094 printTreeID(tree);
3095 printf(" %s 0\n", (curAssertion->assertionKind == OAK_EQUAL) ? "==" : "!=");
3096 }
3097#endif
3098
3099 // Bail out if tree is not side effect free.
3100 if ((tree->gtFlags & GTF_SIDE_EFFECT) != 0)
3101 {
3102 JITDUMP("sorry, blocked by side effects\n");
3103 return nullptr;
3104 }
3105
3106 if (curAssertion->assertionKind == OAK_EQUAL)
3107 {
3108 tree->ChangeOperConst(GT_CNS_INT);
3109 tree->gtIntCon.gtIconVal = 0;
3110 }
3111 else
3112 {
3113 tree->ChangeOperConst(GT_CNS_INT);
3114 tree->gtIntCon.gtIconVal = 1;
3115 }
3116
3117 newTree = fgMorphTree(tree);
3118 DISPTREE(newTree);
3119 return optAssertionProp_Update(newTree, tree, stmt);
3120 }
3121
3122 // Else check if we have an equality check involving a local
3123 if (!tree->OperIs(GT_EQ, GT_NE))
3124 {
3125 return nullptr;
3126 }
3127
3128 if (op1->gtOper != GT_LCL_VAR)
3129 {
3130 return nullptr;
3131 }
3132
3133 // Find an equal or not equal assertion involving "op1" and "op2".
3134 index = optGlobalAssertionIsEqualOrNotEqual(assertions, op1, op2);
3135
3136 if (index == NO_ASSERTION_INDEX)
3137 {
3138 return nullptr;
3139 }
3140
3141 AssertionDsc* curAssertion = optGetAssertion(index);
3142
3143 // Allow or not to reverse condition for OAK_NOT_EQUAL assertions.
3144 bool allowReverse = true;
3145
3146 // If the assertion involves "op2" and it is a constant, then check if "op1" also has a constant value.
3147 ValueNum vnCns = vnStore->VNConservativeNormalValue(op2->gtVNPair);
3148 if (vnStore->IsVNConstant(vnCns))
3149 {
3150#ifdef DEBUG
3151 if (verbose)
3152 {
3153 printf("\nVN relop based constant assertion prop in " FMT_BB ":\n", compCurBB->bbNum);
3154 printf("Assertion index=#%02u: ", index);
3155 printTreeID(op1);
3156 printf(" %s ", (curAssertion->assertionKind == OAK_EQUAL) ? "==" : "!=");
3157 if (genActualType(op1->TypeGet()) == TYP_INT)
3158 {
3159 printf("%d\n", vnStore->ConstantValue<int>(vnCns));
3160 }
3161 else if (op1->TypeGet() == TYP_LONG)
3162 {
3163 printf("%I64d\n", vnStore->ConstantValue<INT64>(vnCns));
3164 }
3165 else if (op1->TypeGet() == TYP_DOUBLE)
3166 {
3167 printf("%f\n", vnStore->ConstantValue<double>(vnCns));
3168 }
3169 else if (op1->TypeGet() == TYP_FLOAT)
3170 {
3171 printf("%f\n", vnStore->ConstantValue<float>(vnCns));
3172 }
3173 else if (op1->TypeGet() == TYP_REF)
3174 {
3175 // The only constant of TYP_REF that ValueNumbering supports is 'null'
3176 assert(vnStore->ConstantValue<size_t>(vnCns) == 0);
3177 printf("null\n");
3178 }
3179 else
3180 {
3181 printf("??unknown\n");
3182 }
3183 gtDispTree(tree, nullptr, nullptr, true);
3184 }
3185#endif
3186 // Change the oper to const.
3187 if (genActualType(op1->TypeGet()) == TYP_INT)
3188 {
3189 op1->ChangeOperConst(GT_CNS_INT);
3190 op1->gtIntCon.gtIconVal = vnStore->ConstantValue<int>(vnCns);
3191 }
3192 else if (op1->TypeGet() == TYP_LONG)
3193 {
3194 op1->ChangeOperConst(GT_CNS_NATIVELONG);
3195 op1->gtIntConCommon.SetLngValue(vnStore->ConstantValue<INT64>(vnCns));
3196 }
3197 else if (op1->TypeGet() == TYP_DOUBLE)
3198 {
3199 double constant = vnStore->ConstantValue<double>(vnCns);
3200 op1->ChangeOperConst(GT_CNS_DBL);
3201 op1->gtDblCon.gtDconVal = constant;
3202
3203 // Nothing can be equal to NaN. So if IL had "op1 == NaN", then we already made op1 NaN,
3204 // which will yield a false correctly. Instead if IL had "op1 != NaN", then we already
3205 // made op1 NaN which will yield a true correctly. Note that this is irrespective of the
3206 // assertion we have made.
3207 allowReverse = (_isnan(constant) == 0);
3208 }
3209 else if (op1->TypeGet() == TYP_FLOAT)
3210 {
3211 float constant = vnStore->ConstantValue<float>(vnCns);
3212 op1->ChangeOperConst(GT_CNS_DBL);
3213 op1->gtDblCon.gtDconVal = constant;
3214 // See comments for TYP_DOUBLE.
3215 allowReverse = (_isnan(constant) == 0);
3216 }
3217 else if (op1->TypeGet() == TYP_REF)
3218 {
3219 op1->ChangeOperConst(GT_CNS_INT);
3220 // The only constant of TYP_REF that ValueNumbering supports is 'null'
3221 noway_assert(vnStore->ConstantValue<size_t>(vnCns) == 0);
3222 op1->gtIntCon.gtIconVal = 0;
3223 }
3224 else
3225 {
3226 noway_assert(!"unknown type in Global_RelOp");
3227 }
3228
3229 op1->gtVNPair.SetBoth(vnCns); // Preserve the ValueNumPair, as ChangeOperConst/SetOper will clear it.
3230 }
3231 // If the assertion involves "op2" and "op1" is also a local var, then just morph the tree.
3232 else if (op2->gtOper == GT_LCL_VAR)
3233 {
3234#ifdef DEBUG
3235 if (verbose)
3236 {
3237 printf("\nVN relop based copy assertion prop in " FMT_BB ":\n", compCurBB->bbNum);
3238 printf("Assertion index=#%02u: V%02d.%02d %s V%02d.%02d\n", index, op1->gtLclVar.gtLclNum,
3239 op1->gtLclVar.gtSsaNum, (curAssertion->assertionKind == OAK_EQUAL) ? "==" : "!=",
3240 op2->gtLclVar.gtLclNum, op2->gtLclVar.gtSsaNum);
3241 gtDispTree(tree, nullptr, nullptr, true);
3242 }
3243#endif
3244 // If floating point, don't just substitute op1 with op2, this won't work if
3245 // op2 is NaN. Just turn it into a "true" or "false" yielding expression.
3246 if (op1->TypeGet() == TYP_DOUBLE || op1->TypeGet() == TYP_FLOAT)
3247 {
3248 // Note we can't trust the OAK_EQUAL as the value could end up being a NaN
3249 // violating the assertion. However, we create OAK_EQUAL assertions for floating
3250 // point only on JTrue nodes, so if the condition held earlier, it will hold
3251 // now. We don't create OAK_EQUAL assertion on floating point from GT_ASG
3252 // because we depend on value num which would constant prop the NaN.
3253 op1->ChangeOperConst(GT_CNS_DBL);
3254 op1->gtDblCon.gtDconVal = 0;
3255 op2->ChangeOperConst(GT_CNS_DBL);
3256 op2->gtDblCon.gtDconVal = 0;
3257 }
3258 // Change the op1 LclVar to the op2 LclVar
3259 else
3260 {
3261 noway_assert(varTypeIsIntegralOrI(op1->TypeGet()));
3262 op1->AsLclVarCommon()->SetLclNum(op2->AsLclVarCommon()->GetLclNum());
3263 op1->AsLclVarCommon()->SetSsaNum(op2->AsLclVarCommon()->GetSsaNum());
3264 }
3265 }
3266 else
3267 {
3268 return nullptr;
3269 }
3270
3271 // Finally reverse the condition, if we have a not equal assertion.
3272 if (allowReverse && curAssertion->assertionKind == OAK_NOT_EQUAL)
3273 {
3274 gtReverseCond(tree);
3275 }
3276
3277 newTree = fgMorphTree(tree);
3278
3279#ifdef DEBUG
3280 if (verbose)
3281 {
3282 gtDispTree(newTree, nullptr, nullptr, true);
3283 }
3284#endif
3285
3286 return optAssertionProp_Update(newTree, tree, stmt);
3287}
3288
3289/*************************************************************************************
3290 *
3291 * Given the set of "assertions" to look up a relop assertion about the relop "tree",
3292 * perform local variable name based relop assertion propagation on the tree.
3293 *
3294 */
3295GenTree* Compiler::optAssertionPropLocal_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3296{
3297 assert(tree->OperGet() == GT_EQ || tree->OperGet() == GT_NE);
3298
3299 GenTree* op1 = tree->gtOp.gtOp1;
3300 GenTree* op2 = tree->gtOp.gtOp2;
3301
3302 // For Local AssertionProp we only can fold when op1 is a GT_LCL_VAR
3303 if (op1->gtOper != GT_LCL_VAR)
3304 {
3305 return nullptr;
3306 }
3307
3308 // For Local AssertionProp we only can fold when op2 is a GT_CNS_INT
3309 if (op2->gtOper != GT_CNS_INT)
3310 {
3311 return nullptr;
3312 }
3313
3314 optOp1Kind op1Kind = O1K_LCLVAR;
3315 optOp2Kind op2Kind = O2K_CONST_INT;
3316 ssize_t cnsVal = op2->gtIntCon.gtIconVal;
3317 var_types cmpType = op1->TypeGet();
3318
3319 // Don't try to fold/optimize Floating Compares; there are multiple zero values.
3320 if (varTypeIsFloating(cmpType))
3321 {
3322 return nullptr;
3323 }
3324
3325 // Find an equal or not equal assertion about op1 var.
3326 unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
3327 noway_assert(lclNum < lvaCount);
3328 AssertionIndex index = optLocalAssertionIsEqualOrNotEqual(op1Kind, lclNum, op2Kind, cnsVal, assertions);
3329
3330 if (index == NO_ASSERTION_INDEX)
3331 {
3332 return nullptr;
3333 }
3334
3335 AssertionDsc* curAssertion = optGetAssertion(index);
3336
3337 bool assertionKindIsEqual = (curAssertion->assertionKind == OAK_EQUAL);
3338 bool constantIsEqual = false;
3339
3340 if (genTypeSize(cmpType) == TARGET_POINTER_SIZE)
3341 {
3342 constantIsEqual = (curAssertion->op2.u1.iconVal == cnsVal);
3343 }
3344#ifdef _TARGET_64BIT_
3345 else if (genTypeSize(cmpType) == sizeof(INT32))
3346 {
3347 // Compare the low 32-bits only
3348 constantIsEqual = (((INT32)curAssertion->op2.u1.iconVal) == ((INT32)cnsVal));
3349 }
3350#endif
3351 else
3352 {
3353 // We currently don't fold/optimize when the GT_LCL_VAR has been cast to a small type
3354 return nullptr;
3355 }
3356
3357 noway_assert(constantIsEqual || assertionKindIsEqual);
3358
3359#ifdef DEBUG
3360 if (verbose)
3361 {
3362 printf("\nAssertion prop for index #%02u in " FMT_BB ":\n", index, compCurBB->bbNum);
3363 gtDispTree(tree, nullptr, nullptr, true);
3364 }
3365#endif
3366
3367 // Return either CNS_INT 0 or CNS_INT 1.
3368 bool foldResult = (constantIsEqual == assertionKindIsEqual);
3369 if (tree->gtOper == GT_NE)
3370 {
3371 foldResult = !foldResult;
3372 }
3373
3374 op2->gtIntCon.gtIconVal = foldResult;
3375 op2->gtType = TYP_INT;
3376
3377 return optAssertionProp_Update(op2, tree, stmt);
3378}
3379
3380/*****************************************************************************
3381 *
3382 * Given a tree consisting of a Cast and a set of available assertions
3383 * we try to propagate an assertion and modify the Cast tree if we can.
3384 * We pass in the root of the tree via 'stmt', for local copy prop 'stmt'
3385 * will be nullptr.
3386 *
3387 * Returns the modified tree, or nullptr if no assertion prop took place.
3388 */
3389GenTree* Compiler::optAssertionProp_Cast(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3390{
3391 assert(tree->gtOper == GT_CAST);
3392
3393 var_types toType = tree->gtCast.gtCastType;
3394 GenTree* op1 = tree->gtCast.CastOp();
3395
3396 // If we have a cast involving floating point types, then bail.
3397 if (varTypeIsFloating(toType) || varTypeIsFloating(op1->TypeGet()))
3398 {
3399 return nullptr;
3400 }
3401
3402 // Skip over a GT_COMMA node(s), if necessary to get to the lcl.
3403 GenTree* lcl = op1;
3404 while (lcl->gtOper == GT_COMMA)
3405 {
3406 lcl = lcl->gtOp.gtOp2;
3407 }
3408
3409 // If we don't have a cast of a LCL_VAR then bail.
3410 if (lcl->gtOper != GT_LCL_VAR)
3411 {
3412 return nullptr;
3413 }
3414
3415 AssertionIndex index = optAssertionIsSubrange(lcl, toType, assertions);
3416 if (index != NO_ASSERTION_INDEX)
3417 {
3418 LclVarDsc* varDsc = &lvaTable[lcl->gtLclVarCommon.gtLclNum];
3419 if (varDsc->lvNormalizeOnLoad() || varTypeIsLong(varDsc->TypeGet()))
3420 {
3421 // For normalize on load variables it must be a narrowing cast to remove
3422 if (genTypeSize(toType) > genTypeSize(varDsc->TypeGet()))
3423 {
3424 // Can we just remove the GTF_OVERFLOW flag?
3425 if ((tree->gtFlags & GTF_OVERFLOW) == 0)
3426 {
3427 return nullptr;
3428 }
3429 else
3430 {
3431
3432#ifdef DEBUG
3433 if (verbose)
3434 {
3435 printf("\nSubrange prop for index #%02u in " FMT_BB ":\n", index, compCurBB->bbNum);
3436 gtDispTree(tree, nullptr, nullptr, true);
3437 }
3438#endif
3439 tree->gtFlags &= ~GTF_OVERFLOW; // This cast cannot overflow
3440 return optAssertionProp_Update(tree, tree, stmt);
3441 }
3442 }
3443
3444 // GT_CAST long -> uint -> int
3445 // |
3446 // GT_LCL_VAR long
3447 //
3448 // Where the lclvar is known to be in the range of [0..MAX_UINT]
3449 //
3450 // A load of a 32-bit unsigned int is the same as a load of a 32-bit signed int
3451 //
3452 if (toType == TYP_UINT)
3453 {
3454 toType = TYP_INT;
3455 }
3456
3457 // Change the "lcl" type to match what the cast wanted, by propagating the type
3458 // change down the comma nodes leading to the "lcl", if we skipped them earlier.
3459 GenTree* tmp = op1;
3460 while (tmp->gtOper == GT_COMMA)
3461 {
3462 tmp->gtType = toType;
3463 tmp = tmp->gtOp.gtOp2;
3464 }
3465 noway_assert(tmp == lcl);
3466 tmp->gtType = toType;
3467 }
3468
3469#ifdef DEBUG
3470 if (verbose)
3471 {
3472 printf("\nSubrange prop for index #%02u in " FMT_BB ":\n", index, compCurBB->bbNum);
3473 gtDispTree(tree, nullptr, nullptr, true);
3474 }
3475#endif
3476 return optAssertionProp_Update(op1, tree, stmt);
3477 }
3478 return nullptr;
3479}
3480
3481/*****************************************************************************
3482 *
3483 * Given a tree with an array bounds check node, eliminate it because it was
3484 * checked already in the program.
3485 */
3486GenTree* Compiler::optAssertionProp_Comma(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3487{
3488 // Remove the bounds check as part of the GT_COMMA node since we need parent pointer to remove nodes.
3489 // When processing visits the bounds check, it sets the throw kind to None if the check is redundant.
3490 if ((tree->gtGetOp1()->OperGet() == GT_ARR_BOUNDS_CHECK) &&
3491 ((tree->gtGetOp1()->gtFlags & GTF_ARR_BOUND_INBND) != 0))
3492 {
3493 optRemoveRangeCheck(tree, stmt);
3494 return optAssertionProp_Update(tree, tree, stmt);
3495 }
3496 return nullptr;
3497}
3498
3499/*****************************************************************************
3500 *
3501 * Given a tree consisting of a Ind and a set of available assertions, we try
3502 * to propagate an assertion and modify the Ind tree if we can. We pass in the
3503 * root of the tree via 'stmt', for local copy prop 'stmt' will be nullptr.
3504 *
3505 * Returns the modified tree, or nullptr if no assertion prop took place.
3506 *
3507 */
3508
3509GenTree* Compiler::optAssertionProp_Ind(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3510{
3511 assert(tree->OperIsIndir());
3512
3513 if (!(tree->gtFlags & GTF_EXCEPT))
3514 {
3515 return nullptr;
3516 }
3517
3518 // Check for add of a constant.
3519 GenTree* op1 = tree->AsIndir()->Addr();
3520 if ((op1->gtOper == GT_ADD) && (op1->gtOp.gtOp2->gtOper == GT_CNS_INT))
3521 {
3522 op1 = op1->gtOp.gtOp1;
3523 }
3524
3525 if (op1->gtOper != GT_LCL_VAR)
3526 {
3527 return nullptr;
3528 }
3529
3530 unsigned lclNum = op1->gtLclVarCommon.gtLclNum;
3531
3532#ifdef DEBUG
3533 bool vnBased = false;
3534 AssertionIndex index = NO_ASSERTION_INDEX;
3535#endif
3536 if (optAssertionIsNonNull(op1, assertions DEBUGARG(&vnBased) DEBUGARG(&index)))
3537 {
3538#ifdef DEBUG
3539 if (verbose)
3540 {
3541 (vnBased) ? printf("\nVN based non-null prop in " FMT_BB ":\n", compCurBB->bbNum)
3542 : printf("\nNon-null prop for index #%02u in " FMT_BB ":\n", index, compCurBB->bbNum);
3543 gtDispTree(tree, nullptr, nullptr, true);
3544 }
3545#endif
3546 tree->gtFlags &= ~GTF_EXCEPT;
3547 tree->gtFlags |= GTF_IND_NONFAULTING;
3548
3549 // Set this flag to prevent reordering
3550 tree->gtFlags |= GTF_ORDER_SIDEEFF;
3551
3552 return optAssertionProp_Update(tree, tree, stmt);
3553 }
3554
3555 return nullptr;
3556}
3557
3558/*****************************************************************************
3559 * Check if a non-null assertion can be made about the input operand "op"
3560 * from the set of "assertions," or implicitly from the value number on "op."
3561 *
3562 * Sets "pVnBased" if the assertion is value number based. If no matching
3563 * assertions are found from the table, then returns "NO_ASSERTION_INDEX."
3564 *
3565 * Note: If both VN and assertion table yield a matching assertion, "pVnBased"
3566 * is only set and the return value is "NO_ASSERTION_INDEX."
3567 */
3568bool Compiler::optAssertionIsNonNull(GenTree* op,
3569 ASSERT_VALARG_TP assertions DEBUGARG(bool* pVnBased)
3570 DEBUGARG(AssertionIndex* pIndex))
3571{
3572 bool vnBased = (!optLocalAssertionProp && vnStore->IsKnownNonNull(op->gtVNPair.GetConservative()));
3573#ifdef DEBUG
3574 *pVnBased = vnBased;
3575#endif
3576
3577 if (vnBased)
3578 {
3579#ifdef DEBUG
3580 *pIndex = NO_ASSERTION_INDEX;
3581#endif
3582 return true;
3583 }
3584
3585 AssertionIndex index = optAssertionIsNonNullInternal(op, assertions);
3586#ifdef DEBUG
3587 *pIndex = index;
3588#endif
3589 return index != NO_ASSERTION_INDEX;
3590}
3591
3592/*****************************************************************************
3593 * Check if a non-null assertion can be made about the input operand "op"
3594 * from the set of "assertions."
3595 *
3596 */
3597AssertionIndex Compiler::optAssertionIsNonNullInternal(GenTree* op, ASSERT_VALARG_TP assertions)
3598{
3599 // If local assertion prop use lcl comparison, else use VN comparison.
3600 if (!optLocalAssertionProp)
3601 {
3602 if (BitVecOps::MayBeUninit(assertions) || BitVecOps::IsEmpty(apTraits, assertions))
3603 {
3604 return NO_ASSERTION_INDEX;
3605 }
3606
3607 ValueNum vn = op->gtVNPair.GetConservative();
3608
3609 // Check each assertion to find if we have a vn == or != null assertion.
3610 BitVecOps::Iter iter(apTraits, assertions);
3611 unsigned index = 0;
3612 while (iter.NextElem(&index))
3613 {
3614 AssertionIndex assertionIndex = GetAssertionIndex(index);
3615 if (assertionIndex > optAssertionCount)
3616 {
3617 break;
3618 }
3619 AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
3620 if (curAssertion->assertionKind != OAK_NOT_EQUAL)
3621 {
3622 continue;
3623 }
3624 if (curAssertion->op1.vn != vn || curAssertion->op2.vn != ValueNumStore::VNForNull())
3625 {
3626 continue;
3627 }
3628 return assertionIndex;
3629 }
3630 }
3631 else
3632 {
3633 unsigned lclNum = op->AsLclVarCommon()->GetLclNum();
3634 // Check each assertion to find if we have a variable == or != null assertion.
3635 for (AssertionIndex index = 1; index <= optAssertionCount; index++)
3636 {
3637 AssertionDsc* curAssertion = optGetAssertion(index);
3638 if ((curAssertion->assertionKind == OAK_NOT_EQUAL) && // kind
3639 (curAssertion->op1.kind == O1K_LCLVAR) && // op1
3640 (curAssertion->op2.kind == O2K_CONST_INT) && // op2
3641 (curAssertion->op1.lcl.lclNum == lclNum) && (curAssertion->op2.u1.iconVal == 0))
3642 {
3643 return index;
3644 }
3645 }
3646 }
3647 return NO_ASSERTION_INDEX;
3648}
3649/*****************************************************************************
3650 *
3651 * Given a tree consisting of a call and a set of available assertions, we
3652 * try to propagate a non-null assertion and modify the Call tree if we can.
3653 * Returns the modified tree, or nullptr if no assertion prop took place.
3654 *
3655 */
3656GenTree* Compiler::optNonNullAssertionProp_Call(ASSERT_VALARG_TP assertions, GenTreeCall* call, GenTree* stmt)
3657{
3658 if ((call->gtFlags & GTF_CALL_NULLCHECK) == 0)
3659 {
3660 return nullptr;
3661 }
3662 GenTree* op1 = gtGetThisArg(call);
3663 noway_assert(op1 != nullptr);
3664 if (op1->gtOper != GT_LCL_VAR)
3665 {
3666 return nullptr;
3667 }
3668
3669#ifdef DEBUG
3670 bool vnBased = false;
3671 AssertionIndex index = NO_ASSERTION_INDEX;
3672#endif
3673 if (optAssertionIsNonNull(op1, assertions DEBUGARG(&vnBased) DEBUGARG(&index)))
3674 {
3675#ifdef DEBUG
3676 if (verbose)
3677 {
3678 (vnBased) ? printf("\nVN based non-null prop in " FMT_BB ":\n", compCurBB->bbNum)
3679 : printf("\nNon-null prop for index #%02u in " FMT_BB ":\n", index, compCurBB->bbNum);
3680 gtDispTree(call, nullptr, nullptr, true);
3681 }
3682#endif
3683 call->gtFlags &= ~GTF_CALL_NULLCHECK;
3684 call->gtFlags &= ~GTF_EXCEPT;
3685 noway_assert(call->gtFlags & GTF_SIDE_EFFECT);
3686 return call;
3687 }
3688 return nullptr;
3689}
3690
3691/*****************************************************************************
3692 *
3693 * Given a tree consisting of a call and a set of available assertions, we
3694 * try to propagate an assertion and modify the Call tree if we can. Our
3695 * current modifications are limited to removing the nullptrCHECK flag from
3696 * the call.
3697 * We pass in the root of the tree via 'stmt', for local copy prop 'stmt'
3698 * will be nullptr. Returns the modified tree, or nullptr if no assertion prop
3699 * took place.
3700 *
3701 */
3702
3703GenTree* Compiler::optAssertionProp_Call(ASSERT_VALARG_TP assertions, GenTreeCall* call, GenTree* stmt)
3704{
3705 if (optNonNullAssertionProp_Call(assertions, call, stmt))
3706 {
3707 return optAssertionProp_Update(call, call, stmt);
3708 }
3709 else if (!optLocalAssertionProp && (call->gtCallType == CT_HELPER))
3710 {
3711 if (call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_ISINSTANCEOFINTERFACE) ||
3712 call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_ISINSTANCEOFARRAY) ||
3713 call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_ISINSTANCEOFCLASS) ||
3714 call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_ISINSTANCEOFANY) ||
3715 call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTINTERFACE) ||
3716 call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTARRAY) ||
3717 call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTCLASS) ||
3718 call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTANY) ||
3719 call->gtCallMethHnd == eeFindHelper(CORINFO_HELP_CHKCASTCLASS_SPECIAL))
3720 {
3721 GenTree* arg1 = gtArgEntryByArgNum(call, 1)->node;
3722 if (arg1->gtOper != GT_LCL_VAR)
3723 {
3724 return nullptr;
3725 }
3726
3727 GenTree* arg2 = gtArgEntryByArgNum(call, 0)->node;
3728
3729 unsigned index = optAssertionIsSubtype(arg1, arg2, assertions);
3730 if (index != NO_ASSERTION_INDEX)
3731 {
3732#ifdef DEBUG
3733 if (verbose)
3734 {
3735 printf("\nDid VN based subtype prop for index #%02u in " FMT_BB ":\n", index, compCurBB->bbNum);
3736 gtDispTree(call, nullptr, nullptr, true);
3737 }
3738#endif
3739 GenTree* list = nullptr;
3740 gtExtractSideEffList(call, &list, GTF_SIDE_EFFECT, true);
3741 if (list != nullptr)
3742 {
3743 arg1 = gtNewOperNode(GT_COMMA, call->TypeGet(), list, arg1);
3744 fgSetTreeSeq(arg1);
3745 }
3746
3747 return optAssertionProp_Update(arg1, call, stmt);
3748 }
3749 }
3750 }
3751
3752 return nullptr;
3753}
3754
3755/*****************************************************************************
3756 *
3757 * Given a tree consisting of a comma node with a bounds check, remove any
3758 * redundant bounds check that has already been checked in the program flow.
3759 */
3760GenTree* Compiler::optAssertionProp_BndsChk(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3761{
3762 if (optLocalAssertionProp)
3763 {
3764 return nullptr;
3765 }
3766
3767 assert(tree->gtOper == GT_ARR_BOUNDS_CHECK);
3768
3769#ifdef FEATURE_ENABLE_NO_RANGE_CHECKS
3770 if (JitConfig.JitNoRangeChks())
3771 {
3772#ifdef DEBUG
3773 if (verbose)
3774 {
3775 printf("\nFlagging check redundant due to JitNoRangeChks in " FMT_BB ":\n", compCurBB->bbNum);
3776 gtDispTree(tree, nullptr, nullptr, true);
3777 }
3778#endif // DEBUG
3779 tree->gtFlags |= GTF_ARR_BOUND_INBND;
3780 return nullptr;
3781 }
3782#endif // FEATURE_ENABLE_NO_RANGE_CHECKS
3783
3784 BitVecOps::Iter iter(apTraits, assertions);
3785 unsigned index = 0;
3786 while (iter.NextElem(&index))
3787 {
3788 AssertionIndex assertionIndex = GetAssertionIndex(index);
3789 if (assertionIndex > optAssertionCount)
3790 {
3791 break;
3792 }
3793 // If it is not a nothrow assertion, skip.
3794 AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
3795 if (!curAssertion->IsBoundsCheckNoThrow())
3796 {
3797 continue;
3798 }
3799
3800 GenTreeBoundsChk* arrBndsChk = tree->AsBoundsChk();
3801
3802 // Set 'isRedundant' to true if we can determine that 'arrBndsChk' can be
3803 // classified as a redundant bounds check using 'curAssertion'
3804 bool isRedundant = false;
3805#ifdef DEBUG
3806 const char* dbgMsg = "Not Set";
3807#endif
3808
3809 // Do we have a previous range check involving the same 'vnLen' upper bound?
3810 if (curAssertion->op1.bnd.vnLen == vnStore->VNConservativeNormalValue(arrBndsChk->gtArrLen->gtVNPair))
3811 {
3812 ValueNum vnCurIdx = vnStore->VNConservativeNormalValue(arrBndsChk->gtIndex->gtVNPair);
3813
3814 // Do we have the exact same lower bound 'vnIdx'?
3815 // a[i] followed by a[i]
3816 if (curAssertion->op1.bnd.vnIdx == vnCurIdx)
3817 {
3818 isRedundant = true;
3819#ifdef DEBUG
3820 dbgMsg = "a[i] followed by a[i]";
3821#endif
3822 }
3823 // Are we using zero as the index?
3824 // It can always be considered as redundant with any previous value
3825 // a[*] followed by a[0]
3826 else if (vnCurIdx == vnStore->VNZeroForType(arrBndsChk->gtIndex->TypeGet()))
3827 {
3828 isRedundant = true;
3829#ifdef DEBUG
3830 dbgMsg = "a[*] followed by a[0]";
3831#endif
3832 }
3833 // Do we have two constant indexes?
3834 else if (vnStore->IsVNConstant(curAssertion->op1.bnd.vnIdx) && vnStore->IsVNConstant(vnCurIdx))
3835 {
3836 // Make sure the types match.
3837 var_types type1 = vnStore->TypeOfVN(curAssertion->op1.bnd.vnIdx);
3838 var_types type2 = vnStore->TypeOfVN(vnCurIdx);
3839
3840 if (type1 == type2 && type1 == TYP_INT)
3841 {
3842 int index1 = vnStore->ConstantValue<int>(curAssertion->op1.bnd.vnIdx);
3843 int index2 = vnStore->ConstantValue<int>(vnCurIdx);
3844
3845 // the case where index1 == index2 should have been handled above
3846 assert(index1 != index2);
3847
3848 // It can always be considered as redundant with any previous higher constant value
3849 // a[K1] followed by a[K2], with K2 >= 0 and K1 >= K2
3850 if (index2 >= 0 && index1 >= index2)
3851 {
3852 isRedundant = true;
3853#ifdef DEBUG
3854 dbgMsg = "a[K1] followed by a[K2], with K2 >= 0 and K1 >= K2";
3855#endif
3856 }
3857 }
3858 }
3859 // Extend this to remove additional redundant bounds checks:
3860 // i.e. a[i+1] followed by a[i] by using the VN(i+1) >= VN(i)
3861 // a[i] followed by a[j] when j is known to be >= i
3862 // a[i] followed by a[5] when i is known to be >= 5
3863 }
3864
3865 if (!isRedundant)
3866 {
3867 continue;
3868 }
3869
3870#ifdef DEBUG
3871 if (verbose)
3872 {
3873 printf("\nVN based redundant (%s) bounds check assertion prop for index #%02u in " FMT_BB ":\n", dbgMsg,
3874 assertionIndex, compCurBB->bbNum);
3875 gtDispTree(tree, nullptr, nullptr, true);
3876 }
3877#endif
3878
3879 // Defer actually removing the tree until processing reaches its parent comma, since
3880 // optRemoveRangeCheck needs to rewrite the whole comma tree.
3881 arrBndsChk->gtFlags |= GTF_ARR_BOUND_INBND;
3882 return nullptr;
3883 }
3884 return nullptr;
3885}
3886
3887/*****************************************************************************
3888 *
3889 * Called when we have a successfully performed an assertion prop. We have
3890 * the newTree in hand. This method will replace the existing tree in the
3891 * stmt with the newTree.
3892 *
3893 */
3894
3895GenTree* Compiler::optAssertionProp_Update(GenTree* newTree, GenTree* tree, GenTree* stmt)
3896{
3897 noway_assert(newTree != nullptr);
3898
3899 if (stmt == nullptr)
3900 {
3901 noway_assert(optLocalAssertionProp);
3902 }
3903 else
3904 {
3905 noway_assert(!optLocalAssertionProp);
3906
3907 // If newTree == tree then we modified the tree in-place otherwise we have to
3908 // locate our parent node and update it so that it points to newTree
3909 if (newTree != tree)
3910 {
3911 GenTree** link = gtFindLink(stmt, tree);
3912#ifdef DEBUG
3913 if (link == nullptr)
3914 {
3915 noway_assert(!"gtFindLink failed!");
3916 printf("\nCould not find parent of:\n");
3917 gtDispTree(tree);
3918 printf("\nIn this stmt:\n");
3919 gtDispTree(stmt);
3920 }
3921#endif
3922 noway_assert(link != nullptr);
3923 noway_assert(tree != nullptr);
3924 if (link != nullptr)
3925 {
3926 // Replace the old operand with the newTree
3927 *link = newTree;
3928
3929 // We only need to ensure that the gtNext field is set as it is used to traverse
3930 // to the next node in the tree. We will re-morph this entire statement in
3931 // optAssertionPropMain(). It will reset the gtPrev and gtNext links for all nodes.
3932
3933 newTree->gtNext = tree->gtNext;
3934 }
3935 }
3936 }
3937
3938 // Record that we propagated the assertion.
3939 optAssertionPropagated = true;
3940 optAssertionPropagatedCurrentStmt = true;
3941
3942 return newTree;
3943}
3944
3945/*****************************************************************************
3946 *
3947 * Given a tree and a set of available assertions we try to propagate an
3948 * assertion and modify 'tree' if we can. We pass in the root of the tree
3949 * via 'stmt', for local copy prop 'stmt' will be nullptr.
3950 *
3951 * Returns the modified tree, or nullptr if no assertion prop took place.
3952 */
3953
3954GenTree* Compiler::optAssertionProp(ASSERT_VALARG_TP assertions, GenTree* tree, GenTree* stmt)
3955{
3956 switch (tree->gtOper)
3957 {
3958 case GT_LCL_VAR:
3959 return optAssertionProp_LclVar(assertions, tree, stmt);
3960
3961 case GT_OBJ:
3962 case GT_BLK:
3963 case GT_DYN_BLK:
3964 case GT_IND:
3965 case GT_NULLCHECK:
3966 return optAssertionProp_Ind(assertions, tree, stmt);
3967
3968 case GT_ARR_BOUNDS_CHECK:
3969 return optAssertionProp_BndsChk(assertions, tree, stmt);
3970
3971 case GT_COMMA:
3972 return optAssertionProp_Comma(assertions, tree, stmt);
3973
3974 case GT_CAST:
3975 return optAssertionProp_Cast(assertions, tree, stmt);
3976
3977 case GT_CALL:
3978 return optAssertionProp_Call(assertions, tree->AsCall(), stmt);
3979
3980 case GT_EQ:
3981 case GT_NE:
3982 case GT_LT:
3983 case GT_LE:
3984 case GT_GT:
3985 case GT_GE:
3986
3987 return optAssertionProp_RelOp(assertions, tree, stmt);
3988
3989 default:
3990 return nullptr;
3991 }
3992}
3993
3994//------------------------------------------------------------------------
3995// optImpliedAssertions: Given a tree node that makes an assertion this
3996// method computes the set of implied assertions
3997// that are also true. The updated assertions are
3998// maintained on the Compiler object.
3999//
4000// Arguments:
4001// assertionIndex : The id of the assertion.
4002// activeAssertions : The assertions that are already true at this point.
4003
4004void Compiler::optImpliedAssertions(AssertionIndex assertionIndex, ASSERT_TP& activeAssertions)
4005{
4006 noway_assert(!optLocalAssertionProp);
4007 noway_assert(assertionIndex != 0);
4008 noway_assert(assertionIndex <= optAssertionCount);
4009
4010 AssertionDsc* curAssertion = optGetAssertion(assertionIndex);
4011 if (!BitVecOps::IsEmpty(apTraits, activeAssertions))
4012 {
4013 const ASSERT_TP mappedAssertions = optGetVnMappedAssertions(curAssertion->op1.vn);
4014 if (mappedAssertions == nullptr)
4015 {
4016 return;
4017 }
4018
4019 ASSERT_TP chkAssertions = BitVecOps::MakeCopy(apTraits, mappedAssertions);
4020
4021 if (curAssertion->op2.kind == O2K_LCLVAR_COPY)
4022 {
4023 const ASSERT_TP op2Assertions = optGetVnMappedAssertions(curAssertion->op2.vn);
4024 if (op2Assertions != nullptr)
4025 {
4026 BitVecOps::UnionD(apTraits, chkAssertions, op2Assertions);
4027 }
4028 }
4029 BitVecOps::IntersectionD(apTraits, chkAssertions, activeAssertions);
4030
4031 if (BitVecOps::IsEmpty(apTraits, chkAssertions))
4032 {
4033 return;
4034 }
4035
4036 // Check each assertion in chkAssertions to see if it can be applied to curAssertion
4037 BitVecOps::Iter chkIter(apTraits, chkAssertions);
4038 unsigned chkIndex = 0;
4039 while (chkIter.NextElem(&chkIndex))
4040 {
4041 AssertionIndex chkAssertionIndex = GetAssertionIndex(chkIndex);
4042 if (chkAssertionIndex > optAssertionCount)
4043 {
4044 break;
4045 }
4046 if (chkAssertionIndex == assertionIndex)
4047 {
4048 continue;
4049 }
4050
4051 // Determine which one is a copy assertion and use the other to check for implied assertions.
4052 AssertionDsc* iterAssertion = optGetAssertion(chkAssertionIndex);
4053 if (curAssertion->IsCopyAssertion())
4054 {
4055 optImpliedByCopyAssertion(curAssertion, iterAssertion, activeAssertions);
4056 }
4057 else if (iterAssertion->IsCopyAssertion())
4058 {
4059 optImpliedByCopyAssertion(iterAssertion, curAssertion, activeAssertions);
4060 }
4061 }
4062 }
4063 // Is curAssertion a constant assignment of a 32-bit integer?
4064 // (i.e GT_LVL_VAR X == GT_CNS_INT)
4065 else if ((curAssertion->assertionKind == OAK_EQUAL) && (curAssertion->op1.kind == O1K_LCLVAR) &&
4066 (curAssertion->op2.kind == O2K_CONST_INT))
4067 {
4068 optImpliedByConstAssertion(curAssertion, activeAssertions);
4069 }
4070}
4071
4072/*****************************************************************************
4073 *
4074 * Given a set of active assertions this method computes the set
4075 * of non-Null implied assertions that are also true
4076 */
4077
4078void Compiler::optImpliedByTypeOfAssertions(ASSERT_TP& activeAssertions)
4079{
4080 if (BitVecOps::IsEmpty(apTraits, activeAssertions))
4081 {
4082 return;
4083 }
4084
4085 // Check each assertion in activeAssertions to see if it can be applied to constAssertion
4086 BitVecOps::Iter chkIter(apTraits, activeAssertions);
4087 unsigned chkIndex = 0;
4088 while (chkIter.NextElem(&chkIndex))
4089 {
4090 AssertionIndex chkAssertionIndex = GetAssertionIndex(chkIndex);
4091 if (chkAssertionIndex > optAssertionCount)
4092 {
4093 break;
4094 }
4095 // chkAssertion must be Type/Subtype is equal assertion
4096 AssertionDsc* chkAssertion = optGetAssertion(chkAssertionIndex);
4097 if ((chkAssertion->op1.kind != O1K_SUBTYPE && chkAssertion->op1.kind != O1K_EXACT_TYPE) ||
4098 (chkAssertion->assertionKind != OAK_EQUAL))
4099 {
4100 continue;
4101 }
4102
4103 // Search the assertion table for a non-null assertion on op1 that matches chkAssertion
4104 for (AssertionIndex impIndex = 1; impIndex <= optAssertionCount; impIndex++)
4105 {
4106 AssertionDsc* impAssertion = optGetAssertion(impIndex);
4107
4108 // The impAssertion must be different from the chkAssertion
4109 if (impIndex == chkAssertionIndex)
4110 {
4111 continue;
4112 }
4113
4114 // impAssertion must be a Non Null assertion on lclNum
4115 if ((impAssertion->assertionKind != OAK_NOT_EQUAL) ||
4116 ((impAssertion->op1.kind != O1K_LCLVAR) && (impAssertion->op1.kind != O1K_VALUE_NUMBER)) ||
4117 (impAssertion->op2.kind != O2K_CONST_INT) || (impAssertion->op1.vn != chkAssertion->op1.vn))
4118 {
4119 continue;
4120 }
4121
4122 // The bit may already be in the result set
4123 if (!BitVecOps::IsMember(apTraits, activeAssertions, impIndex - 1))
4124 {
4125 BitVecOps::AddElemD(apTraits, activeAssertions, impIndex - 1);
4126#ifdef DEBUG
4127 if (verbose)
4128 {
4129 printf("\nCompiler::optImpliedByTypeOfAssertions: %s Assertion #%02d, implies assertion #%02d",
4130 (chkAssertion->op1.kind == O1K_SUBTYPE) ? "Subtype" : "Exact-type", chkAssertionIndex,
4131 impIndex);
4132 }
4133#endif
4134 }
4135
4136 // There is at most one non-null assertion that is implied by the current chkIndex assertion
4137 break;
4138 }
4139 }
4140}
4141
4142//------------------------------------------------------------------------
4143// optGetVnMappedAssertions: Given a value number, get the assertions
4144// we have about the value number.
4145//
4146// Arguments:
4147// vn - The given value number.
4148//
4149// Return Value:
4150// The assertions we have about the value number.
4151//
4152
4153ASSERT_VALRET_TP Compiler::optGetVnMappedAssertions(ValueNum vn)
4154{
4155 ASSERT_TP set = BitVecOps::UninitVal();
4156 if (optValueNumToAsserts->Lookup(vn, &set))
4157 {
4158 return set;
4159 }
4160 return BitVecOps::UninitVal();
4161}
4162
4163/*****************************************************************************
4164 *
4165 * Given a const assertion this method computes the set of implied assertions
4166 * that are also true
4167 */
4168
4169void Compiler::optImpliedByConstAssertion(AssertionDsc* constAssertion, ASSERT_TP& result)
4170{
4171 noway_assert(constAssertion->assertionKind == OAK_EQUAL);
4172 noway_assert(constAssertion->op1.kind == O1K_LCLVAR);
4173 noway_assert(constAssertion->op2.kind == O2K_CONST_INT);
4174
4175 ssize_t iconVal = constAssertion->op2.u1.iconVal;
4176
4177 const ASSERT_TP chkAssertions = optGetVnMappedAssertions(constAssertion->op1.vn);
4178 if (chkAssertions == nullptr || BitVecOps::IsEmpty(apTraits, chkAssertions))
4179 {
4180 return;
4181 }
4182
4183 // Check each assertion in chkAssertions to see if it can be applied to constAssertion
4184 BitVecOps::Iter chkIter(apTraits, chkAssertions);
4185 unsigned chkIndex = 0;
4186 while (chkIter.NextElem(&chkIndex))
4187 {
4188 AssertionIndex chkAssertionIndex = GetAssertionIndex(chkIndex);
4189 if (chkAssertionIndex > optAssertionCount)
4190 {
4191 break;
4192 }
4193 // The impAssertion must be different from the const assertion.
4194 AssertionDsc* impAssertion = optGetAssertion(chkAssertionIndex);
4195 if (impAssertion == constAssertion)
4196 {
4197 continue;
4198 }
4199
4200 // The impAssertion must be an assertion about the same local var.
4201 if (impAssertion->op1.vn != constAssertion->op1.vn)
4202 {
4203 continue;
4204 }
4205
4206 bool usable = false;
4207 switch (impAssertion->op2.kind)
4208 {
4209 case O2K_SUBRANGE:
4210 // Is the const assertion's constant, within implied assertion's bounds?
4211 usable = ((iconVal >= impAssertion->op2.u2.loBound) && (iconVal <= impAssertion->op2.u2.hiBound));
4212 break;
4213
4214 case O2K_CONST_INT:
4215 // Is the const assertion's constant equal/not equal to the implied assertion?
4216 usable = ((impAssertion->assertionKind == OAK_EQUAL) && (impAssertion->op2.u1.iconVal == iconVal)) ||
4217 ((impAssertion->assertionKind == OAK_NOT_EQUAL) && (impAssertion->op2.u1.iconVal != iconVal));
4218 break;
4219
4220 default:
4221 // leave 'usable' = false;
4222 break;
4223 }
4224
4225 if (usable)
4226 {
4227 BitVecOps::AddElemD(apTraits, result, chkIndex);
4228#ifdef DEBUG
4229 if (verbose)
4230 {
4231 AssertionDsc* firstAssertion = optGetAssertion(1);
4232 printf("\nCompiler::optImpliedByConstAssertion: constAssertion #%02d , implies assertion #%02d",
4233 (constAssertion - firstAssertion) + 1, (impAssertion - firstAssertion) + 1);
4234 }
4235#endif
4236 }
4237 }
4238}
4239
4240/*****************************************************************************
4241 *
4242 * Given a copy assertion and a dependent assertion this method computes the
4243 * set of implied assertions that are also true.
4244 * For copy assertions, exact SSA num and LCL nums should match, because
4245 * we don't have kill sets and we depend on their value num for dataflow.
4246 */
4247
4248void Compiler::optImpliedByCopyAssertion(AssertionDsc* copyAssertion, AssertionDsc* depAssertion, ASSERT_TP& result)
4249{
4250 noway_assert(copyAssertion->IsCopyAssertion());
4251
4252 // Get the copyAssert's lcl/ssa nums.
4253 unsigned copyAssertLclNum = BAD_VAR_NUM;
4254 unsigned copyAssertSsaNum = SsaConfig::RESERVED_SSA_NUM;
4255
4256 // Check if copyAssertion's op1 or op2 matches the depAssertion's op1.
4257 if (depAssertion->op1.lcl.lclNum == copyAssertion->op1.lcl.lclNum)
4258 {
4259 copyAssertLclNum = copyAssertion->op2.lcl.lclNum;
4260 copyAssertSsaNum = copyAssertion->op2.lcl.ssaNum;
4261 }
4262 else if (depAssertion->op1.lcl.lclNum == copyAssertion->op2.lcl.lclNum)
4263 {
4264 copyAssertLclNum = copyAssertion->op1.lcl.lclNum;
4265 copyAssertSsaNum = copyAssertion->op1.lcl.ssaNum;
4266 }
4267 // Check if copyAssertion's op1 or op2 matches the depAssertion's op2.
4268 else if (depAssertion->op2.kind == O2K_LCLVAR_COPY)
4269 {
4270 if (depAssertion->op2.lcl.lclNum == copyAssertion->op1.lcl.lclNum)
4271 {
4272 copyAssertLclNum = copyAssertion->op2.lcl.lclNum;
4273 copyAssertSsaNum = copyAssertion->op2.lcl.ssaNum;
4274 }
4275 else if (depAssertion->op2.lcl.lclNum == copyAssertion->op2.lcl.lclNum)
4276 {
4277 copyAssertLclNum = copyAssertion->op1.lcl.lclNum;
4278 copyAssertSsaNum = copyAssertion->op1.lcl.ssaNum;
4279 }
4280 }
4281
4282 if (copyAssertLclNum == BAD_VAR_NUM || copyAssertSsaNum == SsaConfig::RESERVED_SSA_NUM)
4283 {
4284 return;
4285 }
4286
4287 // Get the depAssert's lcl/ssa nums.
4288 unsigned depAssertLclNum = BAD_VAR_NUM;
4289 unsigned depAssertSsaNum = SsaConfig::RESERVED_SSA_NUM;
4290 if ((depAssertion->op1.kind == O1K_LCLVAR) && (depAssertion->op2.kind == O2K_LCLVAR_COPY))
4291 {
4292 if ((depAssertion->op1.lcl.lclNum == copyAssertion->op1.lcl.lclNum) ||
4293 (depAssertion->op1.lcl.lclNum == copyAssertion->op2.lcl.lclNum))
4294 {
4295 depAssertLclNum = depAssertion->op2.lcl.lclNum;
4296 depAssertSsaNum = depAssertion->op2.lcl.ssaNum;
4297 }
4298 else if ((depAssertion->op2.lcl.lclNum == copyAssertion->op1.lcl.lclNum) ||
4299 (depAssertion->op2.lcl.lclNum == copyAssertion->op2.lcl.lclNum))
4300 {
4301 depAssertLclNum = depAssertion->op1.lcl.lclNum;
4302 depAssertSsaNum = depAssertion->op1.lcl.ssaNum;
4303 }
4304 }
4305
4306 if (depAssertLclNum == BAD_VAR_NUM || depAssertSsaNum == SsaConfig::RESERVED_SSA_NUM)
4307 {
4308 return;
4309 }
4310
4311 // Is depAssertion a constant assignment of a 32-bit integer?
4312 // (i.e GT_LVL_VAR X == GT_CNS_INT)
4313 bool depIsConstAssertion = ((depAssertion->assertionKind == OAK_EQUAL) && (depAssertion->op1.kind == O1K_LCLVAR) &&
4314 (depAssertion->op2.kind == O2K_CONST_INT));
4315
4316 // Search the assertion table for an assertion on op1 that matches depAssertion
4317 // The matching assertion is the implied assertion.
4318 for (AssertionIndex impIndex = 1; impIndex <= optAssertionCount; impIndex++)
4319 {
4320 AssertionDsc* impAssertion = optGetAssertion(impIndex);
4321
4322 // The impAssertion must be different from the copy and dependent assertions
4323 if (impAssertion == copyAssertion || impAssertion == depAssertion)
4324 {
4325 continue;
4326 }
4327
4328 if (!AssertionDsc::SameKind(depAssertion, impAssertion))
4329 {
4330 continue;
4331 }
4332
4333 bool op1MatchesCopy =
4334 (copyAssertLclNum == impAssertion->op1.lcl.lclNum) && (copyAssertSsaNum == impAssertion->op1.lcl.ssaNum);
4335
4336 bool usable = false;
4337 switch (impAssertion->op2.kind)
4338 {
4339 case O2K_SUBRANGE:
4340 usable = op1MatchesCopy && ((impAssertion->op2.u2.loBound <= depAssertion->op2.u2.loBound) &&
4341 (impAssertion->op2.u2.hiBound >= depAssertion->op2.u2.hiBound));
4342 break;
4343
4344 case O2K_CONST_LONG:
4345 usable = op1MatchesCopy && (impAssertion->op2.lconVal == depAssertion->op2.lconVal);
4346 break;
4347
4348 case O2K_CONST_DOUBLE:
4349 // Exact memory match because of positive and negative zero
4350 usable = op1MatchesCopy &&
4351 (memcmp(&impAssertion->op2.dconVal, &depAssertion->op2.dconVal, sizeof(double)) == 0);
4352 break;
4353
4354 case O2K_IND_CNS_INT:
4355 // This is the ngen case where we have an indirection of an address.
4356 noway_assert((impAssertion->op1.kind == O1K_EXACT_TYPE) || (impAssertion->op1.kind == O1K_SUBTYPE));
4357
4358 __fallthrough;
4359
4360 case O2K_CONST_INT:
4361 usable = op1MatchesCopy && (impAssertion->op2.u1.iconVal == depAssertion->op2.u1.iconVal);
4362 break;
4363
4364 case O2K_LCLVAR_COPY:
4365 // Check if op1 of impAssertion matches copyAssertion and also op2 of impAssertion matches depAssertion.
4366 if (op1MatchesCopy && (depAssertLclNum == impAssertion->op2.lcl.lclNum &&
4367 depAssertSsaNum == impAssertion->op2.lcl.ssaNum))
4368 {
4369 usable = true;
4370 }
4371 else
4372 {
4373 // Otherwise, op2 of impAssertion should match copyAssertion and also op1 of impAssertion matches
4374 // depAssertion.
4375 usable = ((copyAssertLclNum == impAssertion->op2.lcl.lclNum &&
4376 copyAssertSsaNum == impAssertion->op2.lcl.ssaNum) &&
4377 (depAssertLclNum == impAssertion->op1.lcl.lclNum &&
4378 depAssertSsaNum == impAssertion->op1.lcl.ssaNum));
4379 }
4380 break;
4381
4382 default:
4383 // leave 'usable' = false;
4384 break;
4385 }
4386
4387 if (usable)
4388 {
4389 BitVecOps::AddElemD(apTraits, result, impIndex - 1);
4390
4391#ifdef DEBUG
4392 if (verbose)
4393 {
4394 AssertionDsc* firstAssertion = optGetAssertion(1);
4395 printf("\nCompiler::optImpliedByCopyAssertion: copyAssertion #%02d and depAssertion #%02d, implies "
4396 "assertion #%02d",
4397 (copyAssertion - firstAssertion) + 1, (depAssertion - firstAssertion) + 1,
4398 (impAssertion - firstAssertion) + 1);
4399 }
4400#endif
4401 // If the depAssertion is a const assertion then any other assertions that it implies could also imply a
4402 // subrange assertion.
4403 if (depIsConstAssertion)
4404 {
4405 optImpliedByConstAssertion(impAssertion, result);
4406 }
4407 }
4408 }
4409}
4410
4411#include "dataflow.h"
4412
4413/*****************************************************************************
4414 *
4415 * Dataflow visitor like callback so that all dataflow is in a single place
4416 *
4417 */
4418class AssertionPropFlowCallback
4419{
4420private:
4421 ASSERT_TP preMergeOut;
4422 ASSERT_TP preMergeJumpDestOut;
4423
4424 ASSERT_TP* mJumpDestOut;
4425 ASSERT_TP* mJumpDestGen;
4426
4427 Compiler* m_pCompiler;
4428 BitVecTraits* apTraits;
4429
4430public:
4431 AssertionPropFlowCallback(Compiler* pCompiler, ASSERT_TP* jumpDestOut, ASSERT_TP* jumpDestGen)
4432 : preMergeOut(BitVecOps::UninitVal())
4433 , preMergeJumpDestOut(BitVecOps::UninitVal())
4434 , mJumpDestOut(jumpDestOut)
4435 , mJumpDestGen(jumpDestGen)
4436 , m_pCompiler(pCompiler)
4437 , apTraits(pCompiler->apTraits)
4438 {
4439 }
4440
4441 // At the start of the merge function of the dataflow equations, initialize premerge state (to detect change.)
4442 void StartMerge(BasicBlock* block)
4443 {
4444 JITDUMP("AssertionPropCallback::StartMerge: " FMT_BB " in -> %s\n", block->bbNum,
4445 BitVecOps::ToString(apTraits, block->bbAssertionIn));
4446 BitVecOps::Assign(apTraits, preMergeOut, block->bbAssertionOut);
4447 BitVecOps::Assign(apTraits, preMergeJumpDestOut, mJumpDestOut[block->bbNum]);
4448 }
4449
4450 // During merge, perform the actual merging of the predecessor's (since this is a forward analysis) dataflow flags.
4451 void Merge(BasicBlock* block, BasicBlock* predBlock, flowList* preds)
4452 {
4453 ASSERT_TP pAssertionOut = ((predBlock->bbJumpKind == BBJ_COND) && (predBlock->bbJumpDest == block))
4454 ? mJumpDestOut[predBlock->bbNum]
4455 : predBlock->bbAssertionOut;
4456 JITDUMP("AssertionPropCallback::Merge : " FMT_BB " in -> %s, predBlock " FMT_BB " out -> %s\n",
4457 block->bbNum, BitVecOps::ToString(apTraits, block->bbAssertionIn), predBlock->bbNum,
4458 BitVecOps::ToString(apTraits, predBlock->bbAssertionOut));
4459 BitVecOps::IntersectionD(apTraits, block->bbAssertionIn, pAssertionOut);
4460 }
4461
4462 // At the end of the merge store results of the dataflow equations, in a postmerge state.
4463 bool EndMerge(BasicBlock* block)
4464 {
4465 JITDUMP("AssertionPropCallback::EndMerge : " FMT_BB " in -> %s\n\n", block->bbNum,
4466 BitVecOps::ToString(apTraits, block->bbAssertionIn));
4467
4468 BitVecOps::DataFlowD(apTraits, block->bbAssertionOut, block->bbAssertionGen, block->bbAssertionIn);
4469 BitVecOps::DataFlowD(apTraits, mJumpDestOut[block->bbNum], mJumpDestGen[block->bbNum], block->bbAssertionIn);
4470
4471 bool changed = (!BitVecOps::Equal(apTraits, preMergeOut, block->bbAssertionOut) ||
4472 !BitVecOps::Equal(apTraits, preMergeJumpDestOut, mJumpDestOut[block->bbNum]));
4473
4474 if (changed)
4475 {
4476 JITDUMP("AssertionPropCallback::Changed : " FMT_BB " before out -> %s; after out -> %s;\n"
4477 "\t\tjumpDest before out -> %s; jumpDest after out -> %s;\n\n",
4478 block->bbNum, BitVecOps::ToString(apTraits, preMergeOut),
4479 BitVecOps::ToString(apTraits, block->bbAssertionOut),
4480 BitVecOps::ToString(apTraits, preMergeJumpDestOut),
4481 BitVecOps::ToString(apTraits, mJumpDestOut[block->bbNum]));
4482 }
4483 else
4484 {
4485 JITDUMP("AssertionPropCallback::Unchanged : " FMT_BB " out -> %s; \t\tjumpDest out -> %s\n\n",
4486 block->bbNum, BitVecOps::ToString(apTraits, block->bbAssertionOut),
4487 BitVecOps::ToString(apTraits, mJumpDestOut[block->bbNum]));
4488 }
4489
4490 return changed;
4491 }
4492};
4493
4494/*****************************************************************************
4495 *
4496 * Compute the assertions generated by each block.
4497 */
4498ASSERT_TP* Compiler::optComputeAssertionGen()
4499{
4500 ASSERT_TP* jumpDestGen = fgAllocateTypeForEachBlk<ASSERT_TP>();
4501
4502 for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
4503 {
4504 ASSERT_TP valueGen = BitVecOps::MakeEmpty(apTraits);
4505 GenTree* jtrue = nullptr;
4506
4507 // Walk the statement trees in this basic block.
4508 for (GenTree* stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
4509 {
4510 noway_assert(stmt->gtOper == GT_STMT);
4511
4512 for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
4513 {
4514 if (tree->gtOper == GT_JTRUE)
4515 {
4516 // A GT_TRUE is always the last node in a tree, so we can break here
4517 assert((tree->gtNext == nullptr) && (stmt->gtNext == nullptr));
4518 jtrue = tree;
4519 break;
4520 }
4521
4522 if (tree->GeneratesAssertion())
4523 {
4524 AssertionInfo info = tree->GetAssertionInfo();
4525 optImpliedAssertions(info.GetAssertionIndex(), valueGen);
4526 BitVecOps::AddElemD(apTraits, valueGen, info.GetAssertionIndex() - 1);
4527 }
4528 }
4529 }
4530
4531 if (jtrue != nullptr)
4532 {
4533 // Copy whatever we have accumulated into jumpDest edge's valueGen.
4534 ASSERT_TP jumpDestValueGen = BitVecOps::MakeCopy(apTraits, valueGen);
4535
4536 if (jtrue->GeneratesAssertion())
4537 {
4538 AssertionInfo info = jtrue->GetAssertionInfo();
4539 AssertionIndex valueAssertionIndex;
4540 AssertionIndex jumpDestAssertionIndex;
4541
4542 if (info.IsNextEdgeAssertion())
4543 {
4544 valueAssertionIndex = info.GetAssertionIndex();
4545 jumpDestAssertionIndex = optFindComplementary(info.GetAssertionIndex());
4546 }
4547 else // is jump edge assertion
4548 {
4549 valueAssertionIndex = optFindComplementary(info.GetAssertionIndex());
4550 jumpDestAssertionIndex = info.GetAssertionIndex();
4551 }
4552
4553 if (valueAssertionIndex != NO_ASSERTION_INDEX)
4554 {
4555 // Update valueGen if we have an assertion for the bbNext edge
4556 optImpliedAssertions(valueAssertionIndex, valueGen);
4557 BitVecOps::AddElemD(apTraits, valueGen, valueAssertionIndex - 1);
4558 }
4559
4560 if (jumpDestAssertionIndex != NO_ASSERTION_INDEX)
4561 {
4562 // Update jumpDestValueGen if we have an assertion for the bbJumpDest edge
4563 optImpliedAssertions(jumpDestAssertionIndex, jumpDestValueGen);
4564 BitVecOps::AddElemD(apTraits, jumpDestValueGen, jumpDestAssertionIndex - 1);
4565 }
4566 }
4567
4568 jumpDestGen[block->bbNum] = jumpDestValueGen;
4569 }
4570 else
4571 {
4572 jumpDestGen[block->bbNum] = BitVecOps::MakeEmpty(apTraits);
4573 }
4574
4575 block->bbAssertionGen = valueGen;
4576
4577#ifdef DEBUG
4578 if (verbose)
4579 {
4580 printf("\n" FMT_BB " valueGen = %s", block->bbNum, BitVecOps::ToString(apTraits, block->bbAssertionGen));
4581 if (block->bbJumpKind == BBJ_COND)
4582 {
4583 printf(" => " FMT_BB " valueGen = %s,", block->bbJumpDest->bbNum,
4584 BitVecOps::ToString(apTraits, jumpDestGen[block->bbNum]));
4585 }
4586 }
4587#endif
4588 }
4589 return jumpDestGen;
4590}
4591
4592/*****************************************************************************
4593 *
4594 * Initialize the assertion data flow flags that will be propagated.
4595 */
4596
4597ASSERT_TP* Compiler::optInitAssertionDataflowFlags()
4598{
4599 ASSERT_TP* jumpDestOut = fgAllocateTypeForEachBlk<ASSERT_TP>();
4600
4601 // The local assertion gen phase may have created unreachable blocks.
4602 // They will never be visited in the dataflow propagation phase, so they need to
4603 // be initialized correctly. This means that instead of setting their sets to
4604 // apFull (i.e. all possible bits set), we need to set the bits only for valid
4605 // assertions (note that at this point we are not creating any new assertions).
4606 // Also note that assertion indices start from 1.
4607 ASSERT_TP apValidFull = BitVecOps::MakeEmpty(apTraits);
4608 for (int i = 1; i <= optAssertionCount; i++)
4609 {
4610 BitVecOps::AddElemD(apTraits, apValidFull, i - 1);
4611 }
4612
4613 // Initially estimate the OUT sets to everything except killed expressions
4614 // Also set the IN sets to 1, so that we can perform the intersection.
4615 // Also, zero-out the flags for handler blocks, as we could be in the
4616 // handler due to an exception bypassing the regular program flow which
4617 // actually generates assertions along the bbAssertionOut/jumpDestOut
4618 // edges.
4619 for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
4620 {
4621 if (bbIsHandlerBeg(block))
4622 {
4623 block->bbAssertionIn = BitVecOps::MakeEmpty(apTraits);
4624 }
4625 else
4626 {
4627 block->bbAssertionIn = BitVecOps::MakeCopy(apTraits, apValidFull);
4628 }
4629 block->bbAssertionGen = BitVecOps::MakeEmpty(apTraits);
4630 block->bbAssertionOut = BitVecOps::MakeCopy(apTraits, apValidFull);
4631 jumpDestOut[block->bbNum] = BitVecOps::MakeCopy(apTraits, apValidFull);
4632 }
4633 // Compute the data flow values for all tracked expressions
4634 // IN and OUT never change for the initial basic block B1
4635 BitVecOps::ClearD(apTraits, fgFirstBB->bbAssertionIn);
4636 return jumpDestOut;
4637}
4638
4639// Callback data for the VN based constant prop visitor.
4640struct VNAssertionPropVisitorInfo
4641{
4642 Compiler* pThis;
4643 GenTree* stmt;
4644 BasicBlock* block;
4645 VNAssertionPropVisitorInfo(Compiler* pThis, BasicBlock* block, GenTree* stmt)
4646 : pThis(pThis), stmt(stmt), block(block)
4647 {
4648 }
4649};
4650
4651//------------------------------------------------------------------------------
4652// optPrepareTreeForReplacement
4653// Updates ref counts and extracts side effects from a tree so it can be
4654// replaced with a comma separated list of side effects + a new tree.
4655//
4656// Note:
4657// The old and new trees may be the same. In this case, the tree will be
4658// appended to the side-effect list (if present) and returned.
4659//
4660// Arguments:
4661// oldTree - The tree node to be dropped from the stmt expr.
4662// newTree - The tree node to append to the side effect list from "oldTree".
4663//
4664// Return Value:
4665// Returns a comma separated list of side-effects present in the "oldTree".
4666// When "newTree" is non-null:
4667// 1. When side-effects are present in oldTree, newTree will be appended to the
4668// comma separated list.
4669// 2. When no side effects are present, then returns the "newTree" without
4670// any list.
4671// When "newTree" is null:
4672// 1. Returns the extracted side-effects from "oldTree"
4673// 2. When no side-effects are present, returns null.
4674//
4675// Description:
4676// Decrements ref counts for the "oldTree" that is going to be replaced. If there
4677// are side effects in the tree, then ref counts for variables in the side effects
4678// are incremented because they need to be kept in the stmt expr.
4679//
4680// Either the "newTree" is returned when no side effects are present or a comma
4681// separated side effect list with "newTree" is returned.
4682//
4683GenTree* Compiler::optPrepareTreeForReplacement(GenTree* oldTree, GenTree* newTree)
4684{
4685 // If we have side effects, extract them and append newTree to the list.
4686 GenTree* sideEffList = nullptr;
4687 if ((oldTree->gtFlags & GTF_SIDE_EFFECT) != 0)
4688 {
4689 bool ignoreRoot = false;
4690
4691 if (oldTree == newTree)
4692 {
4693 // If the caller passed the same tree as both old and new then it means
4694 // that it expects that the root of the tree has no side effects and it
4695 // won't be extracted. Otherwise the resulting comma tree would be invalid,
4696 // having both op1 and op2 point to the same tree.
4697 //
4698 // Do a sanity check to ensure persistent side effects aren't discarded and
4699 // tell gtExtractSideEffList to ignore the root of the tree.
4700 assert(!gtNodeHasSideEffects(oldTree, GTF_PERSISTENT_SIDE_EFFECTS));
4701 //
4702 // Exception side effects may be ignored if the root is known to be a constant
4703 // (e.g. VN may evaluate a DIV/MOD node to a constant and the node may still
4704 // have GTF_EXCEPT set, even if it does not actually throw any exceptions).
4705 assert(!gtNodeHasSideEffects(oldTree, GTF_EXCEPT) ||
4706 vnStore->IsVNConstant(vnStore->VNConservativeNormalValue(oldTree->gtVNPair)));
4707
4708 ignoreRoot = true;
4709 }
4710
4711 gtExtractSideEffList(oldTree, &sideEffList, GTF_SIDE_EFFECT, ignoreRoot);
4712 }
4713
4714 if (sideEffList != nullptr)
4715 {
4716 noway_assert((sideEffList->gtFlags & GTF_SIDE_EFFECT) != 0);
4717
4718 if (newTree != nullptr)
4719 {
4720 newTree = gtNewOperNode(GT_COMMA, newTree->TypeGet(), sideEffList, newTree);
4721 }
4722 else
4723 {
4724 newTree = sideEffList;
4725 }
4726 }
4727
4728 return newTree;
4729}
4730
4731//------------------------------------------------------------------------------
4732// optVNConstantPropOnJTrue
4733// Constant propagate on the JTrue node by extracting side effects and moving
4734// them into their own statements. The relop node is then modified to yield
4735// true or false, so the branch can be folded.
4736//
4737// Arguments:
4738// block - The block that contains the JTrue.
4739// stmt - The JTrue stmt which can be evaluated to a constant.
4740// tree - The JTrue node whose relop evaluates to 0 or non-zero value.
4741//
4742// Return Value:
4743// The jmpTrue tree node that has relop of the form "0 =/!= 0".
4744// If "tree" evaluates to "true" relop is "0 == 0". Else relop is "0 != 0".
4745//
4746// Description:
4747// Special treatment for JTRUE nodes' constant propagation. This is because
4748// for JTRUE(1) or JTRUE(0), if there are side effects they need to be put
4749// in separate statements. This is to prevent relop's constant
4750// propagation from doing a simple minded conversion from
4751// (1) STMT(JTRUE(RELOP(COMMA(sideEffect, OP1), OP2)), S.T. op1 =/!= op2 to
4752// (2) STMT(JTRUE(COMMA(sideEffect, 1/0)).
4753//
4754// fgFoldConditional doesn't fold (2), a side-effecting JTRUE's op1. So, let us,
4755// here, convert (1) as two statements: STMT(sideEffect), STMT(JTRUE(1/0)),
4756// so that the JTRUE will get folded by fgFoldConditional.
4757//
4758// Note: fgFoldConditional is called from other places as well, which may be
4759// sensitive to adding new statements. Hence the change is not made directly
4760// into fgFoldConditional.
4761//
4762GenTree* Compiler::optVNConstantPropOnJTrue(BasicBlock* block, GenTree* stmt, GenTree* test)
4763{
4764 GenTree* relop = test->gtGetOp1();
4765
4766 // VN based assertion non-null on this relop has been performed.
4767 if (!relop->OperIsCompare())
4768 {
4769 return nullptr;
4770 }
4771
4772 //
4773 // Make sure GTF_RELOP_JMP_USED flag is set so that we can later skip constant
4774 // prop'ing a JTRUE's relop child node for a second time in the pre-order
4775 // tree walk.
4776 //
4777 assert((relop->gtFlags & GTF_RELOP_JMP_USED) != 0);
4778
4779 ValueNum vnCns = relop->gtVNPair.GetConservative();
4780 ValueNum vnLib = relop->gtVNPair.GetLiberal();
4781 if (!vnStore->IsVNConstant(vnCns))
4782 {
4783 return nullptr;
4784 }
4785
4786 // Prepare the tree for replacement so any side effects can be extracted.
4787 GenTree* sideEffList = optPrepareTreeForReplacement(test, nullptr);
4788
4789 // Transform the relop's operands to be both zeroes.
4790 ValueNum vnZero = vnStore->VNZeroForType(TYP_INT);
4791 relop->gtOp.gtOp1 = gtNewIconNode(0);
4792 relop->gtOp.gtOp1->gtVNPair = ValueNumPair(vnZero, vnZero);
4793 relop->gtOp.gtOp2 = gtNewIconNode(0);
4794 relop->gtOp.gtOp2->gtVNPair = ValueNumPair(vnZero, vnZero);
4795
4796 // Update the oper and restore the value numbers.
4797 bool evalsToTrue = (vnStore->CoercedConstantValue<INT64>(vnCns) != 0);
4798 relop->SetOper(evalsToTrue ? GT_EQ : GT_NE);
4799 relop->gtVNPair = ValueNumPair(vnLib, vnCns);
4800
4801 // Insert side effects back after they were removed from the JTrue stmt.
4802 // It is important not to allow duplicates exist in the IR, that why we delete
4803 // these side effects from the JTrue stmt before insert them back here.
4804 while (sideEffList != nullptr)
4805 {
4806 GenTree* newStmt;
4807 if (sideEffList->OperGet() == GT_COMMA)
4808 {
4809 newStmt = fgInsertStmtNearEnd(block, sideEffList->gtGetOp1());
4810 sideEffList = sideEffList->gtGetOp2();
4811 }
4812 else
4813 {
4814 newStmt = fgInsertStmtNearEnd(block, sideEffList);
4815 sideEffList = nullptr;
4816 }
4817 // fgMorphBlockStmt could potentially affect stmts after the current one,
4818 // for example when it decides to fgRemoveRestOfBlock.
4819 fgMorphBlockStmt(block, newStmt->AsStmt() DEBUGARG(__FUNCTION__));
4820 }
4821
4822 return test;
4823}
4824
4825//------------------------------------------------------------------------------
4826// optVNConstantPropCurStmt
4827// Performs constant prop on the current statement's tree nodes.
4828//
4829// Assumption:
4830// This function is called as part of a pre-order tree walk.
4831//
4832// Arguments:
4833// tree - The currently visited tree node.
4834// stmt - The statement node in which the "tree" is present.
4835// block - The block that contains the statement that contains the tree.
4836//
4837// Return Value:
4838// Returns the standard visitor walk result.
4839//
4840// Description:
4841// Checks if a node is an R-value and evaluates to a constant. If the node
4842// evaluates to constant, then the tree is replaced by its side effects and
4843// the constant node.
4844//
4845Compiler::fgWalkResult Compiler::optVNConstantPropCurStmt(BasicBlock* block, GenTree* stmt, GenTree* tree)
4846{
4847 // Don't propagate floating-point constants into a TYP_STRUCT LclVar
4848 // This can occur for HFA return values (see hfa_sf3E_r.exe)
4849 if (tree->TypeGet() == TYP_STRUCT)
4850 {
4851 return WALK_CONTINUE;
4852 }
4853
4854 switch (tree->OperGet())
4855 {
4856 // Make sure we have an R-value.
4857 case GT_ADD:
4858 case GT_SUB:
4859 case GT_DIV:
4860 case GT_MOD:
4861 case GT_UDIV:
4862 case GT_UMOD:
4863 case GT_EQ:
4864 case GT_NE:
4865 case GT_LT:
4866 case GT_LE:
4867 case GT_GE:
4868 case GT_GT:
4869 case GT_OR:
4870 case GT_XOR:
4871 case GT_AND:
4872 case GT_LSH:
4873 case GT_RSH:
4874 case GT_RSZ:
4875 case GT_NEG:
4876 case GT_CAST:
4877 case GT_INTRINSIC:
4878 break;
4879
4880 case GT_MULHI:
4881 assert(false && "Unexpected GT_MULHI node encountered before lowering");
4882 break;
4883
4884 case GT_JTRUE:
4885 break;
4886
4887 case GT_MUL:
4888 // Don't transform long multiplies.
4889 if (tree->gtFlags & GTF_MUL_64RSLT)
4890 {
4891 return WALK_SKIP_SUBTREES;
4892 }
4893 break;
4894
4895 case GT_LCL_VAR:
4896 // Make sure the local variable is an R-value.
4897 if ((tree->gtFlags & (GTF_VAR_DEF | GTF_DONT_CSE)))
4898 {
4899 return WALK_CONTINUE;
4900 }
4901#if FEATURE_ANYCSE
4902 // Let's not conflict with CSE (to save the movw/movt).
4903 if (lclNumIsCSE(tree->AsLclVarCommon()->GetLclNum()))
4904 {
4905 return WALK_CONTINUE;
4906 }
4907#endif
4908 break;
4909
4910 default:
4911 // Unknown node, continue to walk.
4912 return WALK_CONTINUE;
4913 }
4914
4915 // Perform the constant propagation
4916 GenTree* newTree = optVNConstantPropOnTree(block, stmt, tree);
4917 if (newTree == nullptr)
4918 {
4919 // Not propagated, keep going.
4920 return WALK_CONTINUE;
4921 }
4922
4923 // Successful propagation, mark as assertion propagated and skip
4924 // sub-tree (with side-effects) visits.
4925 // TODO #18291: at that moment stmt could be already removed from the stmt list.
4926
4927 optAssertionProp_Update(newTree, tree, stmt);
4928
4929 JITDUMP("After constant propagation on [%06u]:\n", tree->gtTreeID);
4930 DBEXEC(VERBOSE, gtDispTree(stmt));
4931
4932 return WALK_SKIP_SUBTREES;
4933}
4934
4935//------------------------------------------------------------------------------
4936// optVnNonNullPropCurStmt
4937// Performs VN based non-null propagation on the tree node.
4938//
4939// Assumption:
4940// This function is called as part of a pre-order tree walk.
4941//
4942// Arguments:
4943// block - The block that contains the statement that contains the tree.
4944// stmt - The statement node in which the "tree" is present.
4945// tree - The currently visited tree node.
4946//
4947// Return Value:
4948// None.
4949//
4950// Description:
4951// Performs value number based non-null propagation on GT_CALL and
4952// indirections. This is different from flow based assertions and helps
4953// unify VN based constant prop and non-null prop in a single pre-order walk.
4954//
4955void Compiler::optVnNonNullPropCurStmt(BasicBlock* block, GenTree* stmt, GenTree* tree)
4956{
4957 ASSERT_TP empty = BitVecOps::UninitVal();
4958 GenTree* newTree = nullptr;
4959 if (tree->OperGet() == GT_CALL)
4960 {
4961 newTree = optNonNullAssertionProp_Call(empty, tree->AsCall(), stmt);
4962 }
4963 else if (tree->OperIsIndir())
4964 {
4965 newTree = optAssertionProp_Ind(empty, tree, stmt);
4966 }
4967 if (newTree)
4968 {
4969 assert(newTree == tree);
4970 optAssertionProp_Update(newTree, tree, stmt);
4971 }
4972}
4973
4974//------------------------------------------------------------------------------
4975// optVNAssertionPropCurStmtVisitor
4976// Unified Value Numbering based assertion propagation visitor.
4977//
4978// Assumption:
4979// This function is called as part of a pre-order tree walk.
4980//
4981// Return Value:
4982// WALK_RESULTs.
4983//
4984// Description:
4985// An unified value numbering based assertion prop visitor that
4986// performs non-null and constant assertion propagation based on
4987// value numbers.
4988//
4989/* static */
4990Compiler::fgWalkResult Compiler::optVNAssertionPropCurStmtVisitor(GenTree** ppTree, fgWalkData* data)
4991{
4992 VNAssertionPropVisitorInfo* pData = (VNAssertionPropVisitorInfo*)data->pCallbackData;
4993 Compiler* pThis = pData->pThis;
4994
4995 pThis->optVnNonNullPropCurStmt(pData->block, pData->stmt, *ppTree);
4996
4997 return pThis->optVNConstantPropCurStmt(pData->block, pData->stmt, *ppTree);
4998}
4999
5000/*****************************************************************************
5001 *
5002 * Perform VN based i.e., data flow based assertion prop first because
5003 * even if we don't gen new control flow assertions, we still propagate
5004 * these first.
5005 *
5006 * Returns the skipped next stmt if the current statement or next few
5007 * statements got removed, else just returns the incoming stmt.
5008 */
5009GenTree* Compiler::optVNAssertionPropCurStmt(BasicBlock* block, GenTree* stmt)
5010{
5011 // TODO-Review: EH successor/predecessor iteration seems broken.
5012 // See: SELF_HOST_TESTS_ARM\jit\Directed\ExcepFilters\fault\fault.exe
5013 if (block->bbCatchTyp == BBCT_FAULT)
5014 {
5015 return stmt;
5016 }
5017
5018 // Preserve the prev link before the propagation and morph.
5019 GenTree* prev = (stmt == block->firstStmt()) ? nullptr : stmt->gtPrev;
5020
5021 // Perform VN based assertion prop first, in case we don't find
5022 // anything in assertion gen.
5023 optAssertionPropagatedCurrentStmt = false;
5024
5025 VNAssertionPropVisitorInfo data(this, block, stmt);
5026 fgWalkTreePre(&stmt->gtStmt.gtStmtExpr, Compiler::optVNAssertionPropCurStmtVisitor, &data);
5027
5028 if (optAssertionPropagatedCurrentStmt)
5029 {
5030 fgMorphBlockStmt(block, stmt->AsStmt() DEBUGARG("optVNAssertionPropCurStmt"));
5031 }
5032
5033 // Check if propagation removed statements starting from current stmt.
5034 // If so, advance to the next good statement.
5035 GenTree* nextStmt = (prev == nullptr) ? block->firstStmt() : prev->gtNext;
5036 return nextStmt;
5037}
5038
5039/*****************************************************************************
5040 *
5041 * The entry point for assertion propagation
5042 */
5043
5044void Compiler::optAssertionPropMain()
5045{
5046 if (fgSsaPassesCompleted == 0)
5047 {
5048 return;
5049 }
5050#ifdef DEBUG
5051 if (verbose)
5052 {
5053 printf("*************** In optAssertionPropMain()\n");
5054 printf("Blocks/Trees at start of phase\n");
5055 fgDispBasicBlocks(true);
5056 }
5057#endif
5058
5059 optAssertionInit(false);
5060
5061 noway_assert(optAssertionCount == 0);
5062
5063 // First discover all value assignments and record them in the table.
5064 for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
5065 {
5066 compCurBB = block;
5067
5068 fgRemoveRestOfBlock = false;
5069
5070 GenTree* stmt = block->bbTreeList;
5071 while (stmt)
5072 {
5073 // We need to remove the rest of the block.
5074 if (fgRemoveRestOfBlock)
5075 {
5076 fgRemoveStmt(block, stmt);
5077 stmt = stmt->gtNext;
5078 continue;
5079 }
5080 else
5081 {
5082 // Perform VN based assertion prop before assertion gen.
5083 GenTree* nextStmt = optVNAssertionPropCurStmt(block, stmt);
5084
5085 // Propagation resulted in removal of the remaining stmts, perform it.
5086 if (fgRemoveRestOfBlock)
5087 {
5088 stmt = stmt->gtNext;
5089 continue;
5090 }
5091
5092 // Propagation removed the current stmt or next few stmts, so skip them.
5093 if (stmt != nextStmt)
5094 {
5095 stmt = nextStmt;
5096 continue;
5097 }
5098 }
5099
5100 // Perform assertion gen for control flow based assertions.
5101 for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
5102 {
5103 optAssertionGen(tree);
5104 }
5105
5106 // Advance the iterator
5107 stmt = stmt->gtNext;
5108 }
5109 }
5110
5111 if (!optAssertionCount)
5112 {
5113 return;
5114 }
5115
5116#ifdef DEBUG
5117 fgDebugCheckLinks();
5118#endif
5119
5120 // Allocate the bits for the predicate sensitive dataflow analysis
5121 bbJtrueAssertionOut = optInitAssertionDataflowFlags();
5122 ASSERT_TP* jumpDestGen = optComputeAssertionGen();
5123
5124 // Modified dataflow algorithm for available expressions.
5125 DataFlow flow(this);
5126 AssertionPropFlowCallback ap(this, bbJtrueAssertionOut, jumpDestGen);
5127 flow.ForwardAnalysis(ap);
5128
5129 for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
5130 {
5131 // Compute any implied non-Null assertions for block->bbAssertionIn
5132 optImpliedByTypeOfAssertions(block->bbAssertionIn);
5133 }
5134
5135#ifdef DEBUG
5136 if (verbose)
5137 {
5138 printf("\n");
5139 for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
5140 {
5141 printf("\n" FMT_BB, block->bbNum);
5142 printf(" valueIn = %s", BitVecOps::ToString(apTraits, block->bbAssertionIn));
5143 printf(" valueOut = %s", BitVecOps::ToString(apTraits, block->bbAssertionOut));
5144 if (block->bbJumpKind == BBJ_COND)
5145 {
5146 printf(" => " FMT_BB, block->bbJumpDest->bbNum);
5147 printf(" valueOut= %s", BitVecOps::ToString(apTraits, bbJtrueAssertionOut[block->bbNum]));
5148 }
5149 }
5150 printf("\n");
5151 }
5152#endif // DEBUG
5153
5154 ASSERT_TP assertions = BitVecOps::MakeEmpty(apTraits);
5155
5156 // Perform assertion propagation (and constant folding)
5157 for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
5158 {
5159 BitVecOps::Assign(apTraits, assertions, block->bbAssertionIn);
5160
5161 // TODO-Review: EH successor/predecessor iteration seems broken.
5162 // SELF_HOST_TESTS_ARM\jit\Directed\ExcepFilters\fault\fault.exe
5163 if (block->bbCatchTyp == BBCT_FAULT)
5164 {
5165 continue;
5166 }
5167
5168 // Make the current basic block address available globally.
5169 compCurBB = block;
5170 fgRemoveRestOfBlock = false;
5171
5172 // Walk the statement trees in this basic block
5173 GenTree* stmt = block->FirstNonPhiDef();
5174 while (stmt)
5175 {
5176 noway_assert(stmt->gtOper == GT_STMT);
5177
5178 // Propagation tells us to remove the rest of the block. Remove it.
5179 if (fgRemoveRestOfBlock)
5180 {
5181 fgRemoveStmt(block, stmt);
5182 stmt = stmt->gtNext;
5183 continue;
5184 }
5185
5186 // Preserve the prev link before the propagation and morph, to check if propagation
5187 // removes the current stmt.
5188 GenTree* prev = (stmt == block->firstStmt()) ? nullptr : stmt->gtPrev;
5189
5190 optAssertionPropagatedCurrentStmt = false; // set to true if a assertion propagation took place
5191 // and thus we must morph, set order, re-link
5192 for (GenTree* tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
5193 {
5194 if (tree->OperIs(GT_JTRUE))
5195 {
5196 // A GT_TRUE is always the last node in a tree, so we can break here
5197 assert((tree->gtNext == nullptr) && (stmt->gtNext == nullptr));
5198 break;
5199 }
5200
5201 JITDUMP("Propagating %s assertions for " FMT_BB ", stmt [%06d], tree [%06d], tree -> %d\n",
5202 BitVecOps::ToString(apTraits, assertions), block->bbNum, dspTreeID(stmt), dspTreeID(tree),
5203 tree->GetAssertionInfo().GetAssertionIndex());
5204
5205 GenTree* newTree = optAssertionProp(assertions, tree, stmt);
5206 if (newTree)
5207 {
5208 assert(optAssertionPropagatedCurrentStmt == true);
5209 tree = newTree;
5210 }
5211
5212 // If this tree makes an assertion - make it available.
5213 if (tree->GeneratesAssertion())
5214 {
5215 AssertionInfo info = tree->GetAssertionInfo();
5216 optImpliedAssertions(info.GetAssertionIndex(), assertions);
5217 BitVecOps::AddElemD(apTraits, assertions, info.GetAssertionIndex() - 1);
5218 }
5219 }
5220
5221 if (optAssertionPropagatedCurrentStmt)
5222 {
5223#ifdef DEBUG
5224 if (verbose)
5225 {
5226 printf("Re-morphing this stmt:\n");
5227 gtDispTree(stmt);
5228 printf("\n");
5229 }
5230#endif
5231 // Re-morph the statement.
5232 fgMorphBlockStmt(block, stmt->AsStmt() DEBUGARG("optAssertionPropMain"));
5233 }
5234
5235 // Check if propagation removed statements starting from current stmt.
5236 // If so, advance to the next good statement.
5237 GenTree* nextStmt = (prev == nullptr) ? block->firstStmt() : prev->gtNext;
5238 stmt = (stmt == nextStmt) ? stmt->gtNext : nextStmt;
5239 }
5240 optAssertionPropagatedCurrentStmt = false; // clear it back as we are done with stmts.
5241 }
5242
5243#ifdef DEBUG
5244 fgDebugCheckBBlist();
5245 fgDebugCheckLinks();
5246#endif
5247}
5248