-
Notifications
You must be signed in to change notification settings - Fork 10.8k
/
RewriteStatepointsForGC.cpp
2507 lines (2198 loc) · 96 KB
/
RewriteStatepointsForGC.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Rewrite an existing set of gc.statepoints such that they make potential
// relocations performed by the garbage collector explicit in the IR.
//
//===----------------------------------------------------------------------===//
#include "llvm/Pass.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#define DEBUG_TYPE "rewrite-statepoints-for-gc"
using namespace llvm;
// Print tracing output
static cl::opt<bool> TraceLSP("trace-rewrite-statepoints", cl::Hidden,
cl::init(false));
// Print the liveset found at the insert location
static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden,
cl::init(false));
static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden,
cl::init(false));
// Print out the base pointers for debugging
static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden,
cl::init(false));
// Cost threshold measuring when it is profitable to rematerialize value instead
// of relocating it
static cl::opt<unsigned>
RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden,
cl::init(6));
#ifdef XDEBUG
static bool ClobberNonLive = true;
#else
static bool ClobberNonLive = false;
#endif
static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",
cl::location(ClobberNonLive),
cl::Hidden);
namespace {
struct RewriteStatepointsForGC : public FunctionPass {
static char ID; // Pass identification, replacement for typeid
RewriteStatepointsForGC() : FunctionPass(ID) {
initializeRewriteStatepointsForGCPass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &F) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
// We add and rewrite a bunch of instructions, but don't really do much
// else. We could in theory preserve a lot more analyses here.
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<TargetTransformInfoWrapperPass>();
}
};
} // namespace
char RewriteStatepointsForGC::ID = 0;
FunctionPass *llvm::createRewriteStatepointsForGCPass() {
return new RewriteStatepointsForGC();
}
INITIALIZE_PASS_BEGIN(RewriteStatepointsForGC, "rewrite-statepoints-for-gc",
"Make relocations explicit at statepoints", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_END(RewriteStatepointsForGC, "rewrite-statepoints-for-gc",
"Make relocations explicit at statepoints", false, false)
namespace {
struct GCPtrLivenessData {
/// Values defined in this block.
DenseMap<BasicBlock *, DenseSet<Value *>> KillSet;
/// Values used in this block (and thus live); does not included values
/// killed within this block.
DenseMap<BasicBlock *, DenseSet<Value *>> LiveSet;
/// Values live into this basic block (i.e. used by any
/// instruction in this basic block or ones reachable from here)
DenseMap<BasicBlock *, DenseSet<Value *>> LiveIn;
/// Values live out of this basic block (i.e. live into
/// any successor block)
DenseMap<BasicBlock *, DenseSet<Value *>> LiveOut;
};
// The type of the internal cache used inside the findBasePointers family
// of functions. From the callers perspective, this is an opaque type and
// should not be inspected.
//
// In the actual implementation this caches two relations:
// - The base relation itself (i.e. this pointer is based on that one)
// - The base defining value relation (i.e. before base_phi insertion)
// Generally, after the execution of a full findBasePointer call, only the
// base relation will remain. Internally, we add a mixture of the two
// types, then update all the second type to the first type
typedef DenseMap<Value *, Value *> DefiningValueMapTy;
typedef DenseSet<llvm::Value *> StatepointLiveSetTy;
typedef DenseMap<Instruction *, Value *> RematerializedValueMapTy;
struct PartiallyConstructedSafepointRecord {
/// The set of values known to be live accross this safepoint
StatepointLiveSetTy liveset;
/// Mapping from live pointers to a base-defining-value
DenseMap<llvm::Value *, llvm::Value *> PointerToBase;
/// The *new* gc.statepoint instruction itself. This produces the token
/// that normal path gc.relocates and the gc.result are tied to.
Instruction *StatepointToken;
/// Instruction to which exceptional gc relocates are attached
/// Makes it easier to iterate through them during relocationViaAlloca.
Instruction *UnwindToken;
/// Record live values we are rematerialized instead of relocating.
/// They are not included into 'liveset' field.
/// Maps rematerialized copy to it's original value.
RematerializedValueMapTy RematerializedValues;
};
}
/// Compute the live-in set for every basic block in the function
static void computeLiveInValues(DominatorTree &DT, Function &F,
GCPtrLivenessData &Data);
/// Given results from the dataflow liveness computation, find the set of live
/// Values at a particular instruction.
static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,
StatepointLiveSetTy &out);
// TODO: Once we can get to the GCStrategy, this becomes
// Optional<bool> isGCManagedPointer(const Value *V) const override {
static bool isGCPointerType(const Type *T) {
if (const PointerType *PT = dyn_cast<PointerType>(T))
// For the sake of this example GC, we arbitrarily pick addrspace(1) as our
// GC managed heap. We know that a pointer into this heap needs to be
// updated and that no other pointer does.
return (1 == PT->getAddressSpace());
return false;
}
// Return true if this type is one which a) is a gc pointer or contains a GC
// pointer and b) is of a type this code expects to encounter as a live value.
// (The insertion code will assert that a type which matches (a) and not (b)
// is not encountered.)
static bool isHandledGCPointerType(Type *T) {
// We fully support gc pointers
if (isGCPointerType(T))
return true;
// We partially support vectors of gc pointers. The code will assert if it
// can't handle something.
if (auto VT = dyn_cast<VectorType>(T))
if (isGCPointerType(VT->getElementType()))
return true;
return false;
}
#ifndef NDEBUG
/// Returns true if this type contains a gc pointer whether we know how to
/// handle that type or not.
static bool containsGCPtrType(Type *Ty) {
if (isGCPointerType(Ty))
return true;
if (VectorType *VT = dyn_cast<VectorType>(Ty))
return isGCPointerType(VT->getScalarType());
if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
return containsGCPtrType(AT->getElementType());
if (StructType *ST = dyn_cast<StructType>(Ty))
return std::any_of(
ST->subtypes().begin(), ST->subtypes().end(),
[](Type *SubType) { return containsGCPtrType(SubType); });
return false;
}
// Returns true if this is a type which a) is a gc pointer or contains a GC
// pointer and b) is of a type which the code doesn't expect (i.e. first class
// aggregates). Used to trip assertions.
static bool isUnhandledGCPointerType(Type *Ty) {
return containsGCPtrType(Ty) && !isHandledGCPointerType(Ty);
}
#endif
static bool order_by_name(llvm::Value *a, llvm::Value *b) {
if (a->hasName() && b->hasName()) {
return -1 == a->getName().compare(b->getName());
} else if (a->hasName() && !b->hasName()) {
return true;
} else if (!a->hasName() && b->hasName()) {
return false;
} else {
// Better than nothing, but not stable
return a < b;
}
}
// Conservatively identifies any definitions which might be live at the
// given instruction. The analysis is performed immediately before the
// given instruction. Values defined by that instruction are not considered
// live. Values used by that instruction are considered live.
static void analyzeParsePointLiveness(
DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData,
const CallSite &CS, PartiallyConstructedSafepointRecord &result) {
Instruction *inst = CS.getInstruction();
StatepointLiveSetTy liveset;
findLiveSetAtInst(inst, OriginalLivenessData, liveset);
if (PrintLiveSet) {
// Note: This output is used by several of the test cases
// The order of elemtns in a set is not stable, put them in a vec and sort
// by name
SmallVector<Value *, 64> temp;
temp.insert(temp.end(), liveset.begin(), liveset.end());
std::sort(temp.begin(), temp.end(), order_by_name);
errs() << "Live Variables:\n";
for (Value *V : temp) {
errs() << " " << V->getName(); // no newline
V->dump();
}
}
if (PrintLiveSetSize) {
errs() << "Safepoint For: " << CS.getCalledValue()->getName() << "\n";
errs() << "Number live values: " << liveset.size() << "\n";
}
result.liveset = liveset;
}
static Value *findBaseDefiningValue(Value *I);
/// If we can trivially determine that the index specified in the given vector
/// is a base pointer, return it. In cases where the entire vector is known to
/// consist of base pointers, the entire vector will be returned. This
/// indicates that the relevant extractelement is a valid base pointer and
/// should be used directly.
static Value *findBaseOfVector(Value *I, Value *Index) {
assert(I->getType()->isVectorTy() &&
cast<VectorType>(I->getType())->getElementType()->isPointerTy() &&
"Illegal to ask for the base pointer of a non-pointer type");
// Each case parallels findBaseDefiningValue below, see that code for
// detailed motivation.
if (isa<Argument>(I))
// An incoming argument to the function is a base pointer
return I;
// We shouldn't see the address of a global as a vector value?
assert(!isa<GlobalVariable>(I) &&
"unexpected global variable found in base of vector");
// inlining could possibly introduce phi node that contains
// undef if callee has multiple returns
if (isa<UndefValue>(I))
// utterly meaningless, but useful for dealing with partially optimized
// code.
return I;
// Due to inheritance, this must be _after_ the global variable and undef
// checks
if (Constant *Con = dyn_cast<Constant>(I)) {
assert(!isa<GlobalVariable>(I) && !isa<UndefValue>(I) &&
"order of checks wrong!");
assert(Con->isNullValue() && "null is the only case which makes sense");
return Con;
}
if (isa<LoadInst>(I))
return I;
// For an insert element, we might be able to look through it if we know
// something about the indexes, but if the indices are arbitrary values, we
// can't without much more extensive scalarization.
if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(I)) {
Value *InsertIndex = IEI->getOperand(2);
// This index is inserting the value, look for it's base
if (InsertIndex == Index)
return findBaseDefiningValue(IEI->getOperand(1));
// Both constant, and can't be equal per above. This insert is definitely
// not relevant, look back at the rest of the vector and keep trying.
if (isa<ConstantInt>(Index) && isa<ConstantInt>(InsertIndex))
return findBaseOfVector(IEI->getOperand(0), Index);
}
// Note: This code is currently rather incomplete. We are essentially only
// handling cases where the vector element is trivially a base pointer. We
// need to update the entire base pointer construction algorithm to know how
// to track vector elements and potentially scalarize, but the case which
// would motivate the work hasn't shown up in real workloads yet.
llvm_unreachable("no base found for vector element");
}
/// Helper function for findBasePointer - Will return a value which either a)
/// defines the base pointer for the input or b) blocks the simple search
/// (i.e. a PHI or Select of two derived pointers)
static Value *findBaseDefiningValue(Value *I) {
assert(I->getType()->isPointerTy() &&
"Illegal to ask for the base pointer of a non-pointer type");
// This case is a bit of a hack - it only handles extracts from vectors which
// trivially contain only base pointers or cases where we can directly match
// the index of the original extract element to an insertion into the vector.
// See note inside the function for how to improve this.
if (auto *EEI = dyn_cast<ExtractElementInst>(I)) {
Value *VectorOperand = EEI->getVectorOperand();
Value *Index = EEI->getIndexOperand();
Value *VectorBase = findBaseOfVector(VectorOperand, Index);
// If the result returned is a vector, we know the entire vector must
// contain base pointers. In that case, the extractelement is a valid base
// for this value.
if (VectorBase->getType()->isVectorTy())
return EEI;
// Otherwise, we needed to look through the vector to find the base for
// this particular element.
assert(VectorBase->getType()->isPointerTy());
return VectorBase;
}
if (isa<Argument>(I))
// An incoming argument to the function is a base pointer
// We should have never reached here if this argument isn't an gc value
return I;
if (isa<GlobalVariable>(I))
// base case
return I;
// inlining could possibly introduce phi node that contains
// undef if callee has multiple returns
if (isa<UndefValue>(I))
// utterly meaningless, but useful for dealing with
// partially optimized code.
return I;
// Due to inheritance, this must be _after_ the global variable and undef
// checks
if (Constant *Con = dyn_cast<Constant>(I)) {
assert(!isa<GlobalVariable>(I) && !isa<UndefValue>(I) &&
"order of checks wrong!");
// Note: Finding a constant base for something marked for relocation
// doesn't really make sense. The most likely case is either a) some
// screwed up the address space usage or b) your validating against
// compiled C++ code w/o the proper separation. The only real exception
// is a null pointer. You could have generic code written to index of
// off a potentially null value and have proven it null. We also use
// null pointers in dead paths of relocation phis (which we might later
// want to find a base pointer for).
assert(isa<ConstantPointerNull>(Con) &&
"null is the only case which makes sense");
return Con;
}
if (CastInst *CI = dyn_cast<CastInst>(I)) {
Value *Def = CI->stripPointerCasts();
// If we find a cast instruction here, it means we've found a cast which is
// not simply a pointer cast (i.e. an inttoptr). We don't know how to
// handle int->ptr conversion.
assert(!isa<CastInst>(Def) && "shouldn't find another cast here");
return findBaseDefiningValue(Def);
}
if (isa<LoadInst>(I))
return I; // The value loaded is an gc base itself
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I))
// The base of this GEP is the base
return findBaseDefiningValue(GEP->getPointerOperand());
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
switch (II->getIntrinsicID()) {
case Intrinsic::experimental_gc_result_ptr:
default:
// fall through to general call handling
break;
case Intrinsic::experimental_gc_statepoint:
case Intrinsic::experimental_gc_result_float:
case Intrinsic::experimental_gc_result_int:
llvm_unreachable("these don't produce pointers");
case Intrinsic::experimental_gc_relocate: {
// Rerunning safepoint insertion after safepoints are already
// inserted is not supported. It could probably be made to work,
// but why are you doing this? There's no good reason.
llvm_unreachable("repeat safepoint insertion is not supported");
}
case Intrinsic::gcroot:
// Currently, this mechanism hasn't been extended to work with gcroot.
// There's no reason it couldn't be, but I haven't thought about the
// implications much.
llvm_unreachable(
"interaction with the gcroot mechanism is not supported");
}
}
// We assume that functions in the source language only return base
// pointers. This should probably be generalized via attributes to support
// both source language and internal functions.
if (isa<CallInst>(I) || isa<InvokeInst>(I))
return I;
// I have absolutely no idea how to implement this part yet. It's not
// neccessarily hard, I just haven't really looked at it yet.
assert(!isa<LandingPadInst>(I) && "Landing Pad is unimplemented");
if (isa<AtomicCmpXchgInst>(I))
// A CAS is effectively a atomic store and load combined under a
// predicate. From the perspective of base pointers, we just treat it
// like a load.
return I;
assert(!isa<AtomicRMWInst>(I) && "Xchg handled above, all others are "
"binary ops which don't apply to pointers");
// The aggregate ops. Aggregates can either be in the heap or on the
// stack, but in either case, this is simply a field load. As a result,
// this is a defining definition of the base just like a load is.
if (isa<ExtractValueInst>(I))
return I;
// We should never see an insert vector since that would require we be
// tracing back a struct value not a pointer value.
assert(!isa<InsertValueInst>(I) &&
"Base pointer for a struct is meaningless");
// The last two cases here don't return a base pointer. Instead, they
// return a value which dynamically selects from amoung several base
// derived pointers (each with it's own base potentially). It's the job of
// the caller to resolve these.
assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
"missing instruction case in findBaseDefiningValing");
return I;
}
/// Returns the base defining value for this value.
static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache) {
Value *&Cached = Cache[I];
if (!Cached) {
Cached = findBaseDefiningValue(I);
}
assert(Cache[I] != nullptr);
if (TraceLSP) {
dbgs() << "fBDV-cached: " << I->getName() << " -> " << Cached->getName()
<< "\n";
}
return Cached;
}
/// Return a base pointer for this value if known. Otherwise, return it's
/// base defining value.
static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache) {
Value *Def = findBaseDefiningValueCached(I, Cache);
auto Found = Cache.find(Def);
if (Found != Cache.end()) {
// Either a base-of relation, or a self reference. Caller must check.
return Found->second;
}
// Only a BDV available
return Def;
}
/// Given the result of a call to findBaseDefiningValue, or findBaseOrBDV,
/// is it known to be a base pointer? Or do we need to continue searching.
static bool isKnownBaseResult(Value *V) {
if (!isa<PHINode>(V) && !isa<SelectInst>(V)) {
// no recursion possible
return true;
}
if (isa<Instruction>(V) &&
cast<Instruction>(V)->getMetadata("is_base_value")) {
// This is a previously inserted base phi or select. We know
// that this is a base value.
return true;
}
// We need to keep searching
return false;
}
// TODO: find a better name for this
namespace {
class PhiState {
public:
enum Status { Unknown, Base, Conflict };
PhiState(Status s, Value *b = nullptr) : status(s), base(b) {
assert(status != Base || b);
}
PhiState(Value *b) : status(Base), base(b) {}
PhiState() : status(Unknown), base(nullptr) {}
Status getStatus() const { return status; }
Value *getBase() const { return base; }
bool isBase() const { return getStatus() == Base; }
bool isUnknown() const { return getStatus() == Unknown; }
bool isConflict() const { return getStatus() == Conflict; }
bool operator==(const PhiState &other) const {
return base == other.base && status == other.status;
}
bool operator!=(const PhiState &other) const { return !(*this == other); }
void dump() {
errs() << status << " (" << base << " - "
<< (base ? base->getName() : "nullptr") << "): ";
}
private:
Status status;
Value *base; // non null only if status == base
};
typedef DenseMap<Value *, PhiState> ConflictStateMapTy;
// Values of type PhiState form a lattice, and this is a helper
// class that implementes the meet operation. The meat of the meet
// operation is implemented in MeetPhiStates::pureMeet
class MeetPhiStates {
public:
// phiStates is a mapping from PHINodes and SelectInst's to PhiStates.
explicit MeetPhiStates(const ConflictStateMapTy &phiStates)
: phiStates(phiStates) {}
// Destructively meet the current result with the base V. V can
// either be a merge instruction (SelectInst / PHINode), in which
// case its status is looked up in the phiStates map; or a regular
// SSA value, in which case it is assumed to be a base.
void meetWith(Value *V) {
PhiState otherState = getStateForBDV(V);
assert((MeetPhiStates::pureMeet(otherState, currentResult) ==
MeetPhiStates::pureMeet(currentResult, otherState)) &&
"math is wrong: meet does not commute!");
currentResult = MeetPhiStates::pureMeet(otherState, currentResult);
}
PhiState getResult() const { return currentResult; }
private:
const ConflictStateMapTy &phiStates;
PhiState currentResult;
/// Return a phi state for a base defining value. We'll generate a new
/// base state for known bases and expect to find a cached state otherwise
PhiState getStateForBDV(Value *baseValue) {
if (isKnownBaseResult(baseValue)) {
return PhiState(baseValue);
} else {
return lookupFromMap(baseValue);
}
}
PhiState lookupFromMap(Value *V) {
auto I = phiStates.find(V);
assert(I != phiStates.end() && "lookup failed!");
return I->second;
}
static PhiState pureMeet(const PhiState &stateA, const PhiState &stateB) {
switch (stateA.getStatus()) {
case PhiState::Unknown:
return stateB;
case PhiState::Base:
assert(stateA.getBase() && "can't be null");
if (stateB.isUnknown())
return stateA;
if (stateB.isBase()) {
if (stateA.getBase() == stateB.getBase()) {
assert(stateA == stateB && "equality broken!");
return stateA;
}
return PhiState(PhiState::Conflict);
}
assert(stateB.isConflict() && "only three states!");
return PhiState(PhiState::Conflict);
case PhiState::Conflict:
return stateA;
}
llvm_unreachable("only three states!");
}
};
}
/// For a given value or instruction, figure out what base ptr it's derived
/// from. For gc objects, this is simply itself. On success, returns a value
/// which is the base pointer. (This is reliable and can be used for
/// relocation.) On failure, returns nullptr.
static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) {
Value *def = findBaseOrBDV(I, cache);
if (isKnownBaseResult(def)) {
return def;
}
// Here's the rough algorithm:
// - For every SSA value, construct a mapping to either an actual base
// pointer or a PHI which obscures the base pointer.
// - Construct a mapping from PHI to unknown TOP state. Use an
// optimistic algorithm to propagate base pointer information. Lattice
// looks like:
// UNKNOWN
// b1 b2 b3 b4
// CONFLICT
// When algorithm terminates, all PHIs will either have a single concrete
// base or be in a conflict state.
// - For every conflict, insert a dummy PHI node without arguments. Add
// these to the base[Instruction] = BasePtr mapping. For every
// non-conflict, add the actual base.
// - For every conflict, add arguments for the base[a] of each input
// arguments.
//
// Note: A simpler form of this would be to add the conflict form of all
// PHIs without running the optimistic algorithm. This would be
// analougous to pessimistic data flow and would likely lead to an
// overall worse solution.
ConflictStateMapTy states;
states[def] = PhiState();
// Recursively fill in all phis & selects reachable from the initial one
// for which we don't already know a definite base value for
// TODO: This should be rewritten with a worklist
bool done = false;
while (!done) {
done = true;
// Since we're adding elements to 'states' as we run, we can't keep
// iterators into the set.
SmallVector<Value *, 16> Keys;
Keys.reserve(states.size());
for (auto Pair : states) {
Value *V = Pair.first;
Keys.push_back(V);
}
for (Value *v : Keys) {
assert(!isKnownBaseResult(v) && "why did it get added?");
if (PHINode *phi = dyn_cast<PHINode>(v)) {
assert(phi->getNumIncomingValues() > 0 &&
"zero input phis are illegal");
for (Value *InVal : phi->incoming_values()) {
Value *local = findBaseOrBDV(InVal, cache);
if (!isKnownBaseResult(local) && states.find(local) == states.end()) {
states[local] = PhiState();
done = false;
}
}
} else if (SelectInst *sel = dyn_cast<SelectInst>(v)) {
Value *local = findBaseOrBDV(sel->getTrueValue(), cache);
if (!isKnownBaseResult(local) && states.find(local) == states.end()) {
states[local] = PhiState();
done = false;
}
local = findBaseOrBDV(sel->getFalseValue(), cache);
if (!isKnownBaseResult(local) && states.find(local) == states.end()) {
states[local] = PhiState();
done = false;
}
}
}
}
if (TraceLSP) {
errs() << "States after initialization:\n";
for (auto Pair : states) {
Instruction *v = cast<Instruction>(Pair.first);
PhiState state = Pair.second;
state.dump();
v->dump();
}
}
// TODO: come back and revisit the state transitions around inputs which
// have reached conflict state. The current version seems too conservative.
bool progress = true;
while (progress) {
#ifndef NDEBUG
size_t oldSize = states.size();
#endif
progress = false;
// We're only changing keys in this loop, thus safe to keep iterators
for (auto Pair : states) {
MeetPhiStates calculateMeet(states);
Value *v = Pair.first;
assert(!isKnownBaseResult(v) && "why did it get added?");
if (SelectInst *select = dyn_cast<SelectInst>(v)) {
calculateMeet.meetWith(findBaseOrBDV(select->getTrueValue(), cache));
calculateMeet.meetWith(findBaseOrBDV(select->getFalseValue(), cache));
} else
for (Value *Val : cast<PHINode>(v)->incoming_values())
calculateMeet.meetWith(findBaseOrBDV(Val, cache));
PhiState oldState = states[v];
PhiState newState = calculateMeet.getResult();
if (oldState != newState) {
progress = true;
states[v] = newState;
}
}
assert(oldSize <= states.size());
assert(oldSize == states.size() || progress);
}
if (TraceLSP) {
errs() << "States after meet iteration:\n";
for (auto Pair : states) {
Instruction *v = cast<Instruction>(Pair.first);
PhiState state = Pair.second;
state.dump();
v->dump();
}
}
// Insert Phis for all conflicts
// We want to keep naming deterministic in the loop that follows, so
// sort the keys before iteration. This is useful in allowing us to
// write stable tests. Note that there is no invalidation issue here.
SmallVector<Value *, 16> Keys;
Keys.reserve(states.size());
for (auto Pair : states) {
Value *V = Pair.first;
Keys.push_back(V);
}
std::sort(Keys.begin(), Keys.end(), order_by_name);
// TODO: adjust naming patterns to avoid this order of iteration dependency
for (Value *V : Keys) {
Instruction *v = cast<Instruction>(V);
PhiState state = states[V];
assert(!isKnownBaseResult(v) && "why did it get added?");
assert(!state.isUnknown() && "Optimistic algorithm didn't complete!");
if (!state.isConflict())
continue;
if (isa<PHINode>(v)) {
int num_preds =
std::distance(pred_begin(v->getParent()), pred_end(v->getParent()));
assert(num_preds > 0 && "how did we reach here");
PHINode *phi = PHINode::Create(v->getType(), num_preds, "base_phi", v);
// Add metadata marking this as a base value
auto *const_1 = ConstantInt::get(
Type::getInt32Ty(
v->getParent()->getParent()->getParent()->getContext()),
1);
auto MDConst = ConstantAsMetadata::get(const_1);
MDNode *md = MDNode::get(
v->getParent()->getParent()->getParent()->getContext(), MDConst);
phi->setMetadata("is_base_value", md);
states[v] = PhiState(PhiState::Conflict, phi);
} else {
SelectInst *sel = cast<SelectInst>(v);
// The undef will be replaced later
UndefValue *undef = UndefValue::get(sel->getType());
SelectInst *basesel = SelectInst::Create(sel->getCondition(), undef,
undef, "base_select", sel);
// Add metadata marking this as a base value
auto *const_1 = ConstantInt::get(
Type::getInt32Ty(
v->getParent()->getParent()->getParent()->getContext()),
1);
auto MDConst = ConstantAsMetadata::get(const_1);
MDNode *md = MDNode::get(
v->getParent()->getParent()->getParent()->getContext(), MDConst);
basesel->setMetadata("is_base_value", md);
states[v] = PhiState(PhiState::Conflict, basesel);
}
}
// Fixup all the inputs of the new PHIs
for (auto Pair : states) {
Instruction *v = cast<Instruction>(Pair.first);
PhiState state = Pair.second;
assert(!isKnownBaseResult(v) && "why did it get added?");
assert(!state.isUnknown() && "Optimistic algorithm didn't complete!");
if (!state.isConflict())
continue;
if (PHINode *basephi = dyn_cast<PHINode>(state.getBase())) {
PHINode *phi = cast<PHINode>(v);
unsigned NumPHIValues = phi->getNumIncomingValues();
for (unsigned i = 0; i < NumPHIValues; i++) {
Value *InVal = phi->getIncomingValue(i);
BasicBlock *InBB = phi->getIncomingBlock(i);
// If we've already seen InBB, add the same incoming value
// we added for it earlier. The IR verifier requires phi
// nodes with multiple entries from the same basic block
// to have the same incoming value for each of those
// entries. If we don't do this check here and basephi
// has a different type than base, we'll end up adding two
// bitcasts (and hence two distinct values) as incoming
// values for the same basic block.
int blockIndex = basephi->getBasicBlockIndex(InBB);
if (blockIndex != -1) {
Value *oldBase = basephi->getIncomingValue(blockIndex);
basephi->addIncoming(oldBase, InBB);
#ifndef NDEBUG
Value *base = findBaseOrBDV(InVal, cache);
if (!isKnownBaseResult(base)) {
// Either conflict or base.
assert(states.count(base));
base = states[base].getBase();
assert(base != nullptr && "unknown PhiState!");
}
// In essense this assert states: the only way two
// values incoming from the same basic block may be
// different is by being different bitcasts of the same
// value. A cleanup that remains TODO is changing
// findBaseOrBDV to return an llvm::Value of the correct
// type (and still remain pure). This will remove the
// need to add bitcasts.
assert(base->stripPointerCasts() == oldBase->stripPointerCasts() &&
"sanity -- findBaseOrBDV should be pure!");
#endif
continue;
}
// Find either the defining value for the PHI or the normal base for
// a non-phi node
Value *base = findBaseOrBDV(InVal, cache);
if (!isKnownBaseResult(base)) {
// Either conflict or base.
assert(states.count(base));
base = states[base].getBase();
assert(base != nullptr && "unknown PhiState!");
}
assert(base && "can't be null");
// Must use original input BB since base may not be Instruction
// The cast is needed since base traversal may strip away bitcasts
if (base->getType() != basephi->getType()) {
base = new BitCastInst(base, basephi->getType(), "cast",
InBB->getTerminator());
}
basephi->addIncoming(base, InBB);
}
assert(basephi->getNumIncomingValues() == NumPHIValues);
} else {
SelectInst *basesel = cast<SelectInst>(state.getBase());
SelectInst *sel = cast<SelectInst>(v);
// Operand 1 & 2 are true, false path respectively. TODO: refactor to
// something more safe and less hacky.
for (int i = 1; i <= 2; i++) {
Value *InVal = sel->getOperand(i);
// Find either the defining value for the PHI or the normal base for
// a non-phi node
Value *base = findBaseOrBDV(InVal, cache);
if (!isKnownBaseResult(base)) {
// Either conflict or base.
assert(states.count(base));
base = states[base].getBase();
assert(base != nullptr && "unknown PhiState!");
}
assert(base && "can't be null");
// Must use original input BB since base may not be Instruction
// The cast is needed since base traversal may strip away bitcasts
if (base->getType() != basesel->getType()) {
base = new BitCastInst(base, basesel->getType(), "cast", basesel);
}
basesel->setOperand(i, base);
}
}
}
// Cache all of our results so we can cheaply reuse them
// NOTE: This is actually two caches: one of the base defining value
// relation and one of the base pointer relation! FIXME
for (auto item : states) {
Value *v = item.first;
Value *base = item.second.getBase();
assert(v && base);
assert(!isKnownBaseResult(v) && "why did it get added?");
if (TraceLSP) {
std::string fromstr =
cache.count(v) ? (cache[v]->hasName() ? cache[v]->getName() : "")
: "none";
errs() << "Updating base value cache"
<< " for: " << (v->hasName() ? v->getName() : "")
<< " from: " << fromstr
<< " to: " << (base->hasName() ? base->getName() : "") << "\n";
}
assert(isKnownBaseResult(base) &&
"must be something we 'know' is a base pointer");
if (cache.count(v)) {
// Once we transition from the BDV relation being store in the cache to
// the base relation being stored, it must be stable
assert((!isKnownBaseResult(cache[v]) || cache[v] == base) &&
"base relation should be stable");
}
cache[v] = base;
}
assert(cache.find(def) != cache.end());
return cache[def];
}
// For a set of live pointers (base and/or derived), identify the base
// pointer of the object which they are derived from. This routine will
// mutate the IR graph as needed to make the 'base' pointer live at the
// definition site of 'derived'. This ensures that any use of 'derived' can
// also use 'base'. This may involve the insertion of a number of
// additional PHI nodes.
//
// preconditions: live is a set of pointer type Values
//
// side effects: may insert PHI nodes into the existing CFG, will preserve
// CFG, will not remove or mutate any existing nodes
//
// post condition: PointerToBase contains one (derived, base) pair for every
// pointer in live. Note that derived can be equal to base if the original
// pointer was a base pointer.
static void
findBasePointers(const StatepointLiveSetTy &live,
DenseMap<llvm::Value *, llvm::Value *> &PointerToBase,
DominatorTree *DT, DefiningValueMapTy &DVCache) {
// For the naming of values inserted to be deterministic - which makes for
// much cleaner and more stable tests - we need to assign an order to the
// live values. DenseSets do not provide a deterministic order across runs.
SmallVector<Value *, 64> Temp;
Temp.insert(Temp.end(), live.begin(), live.end());
std::sort(Temp.begin(), Temp.end(), order_by_name);
for (Value *ptr : Temp) {
Value *base = findBasePointer(ptr, DVCache);
assert(base && "failed to find base pointer");
PointerToBase[ptr] = base;
assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||
DT->dominates(cast<Instruction>(base)->getParent(),
cast<Instruction>(ptr)->getParent())) &&
"The base we found better dominate the derived pointer");
// If you see this trip and like to live really dangerously, the code should
// be correct, just with idioms the verifier can't handle. You can try
// disabling the verifier at your own substaintial risk.
assert(!isa<ConstantPointerNull>(base) &&
"the relocation code needs adjustment to handle the relocation of "
"a null pointer constant without causing false positives in the "
"safepoint ir verifier.");
}
}
/// Find the required based pointers (and adjust the live set) for the given
/// parse point.
static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache,
const CallSite &CS,
PartiallyConstructedSafepointRecord &result) {
DenseMap<llvm::Value *, llvm::Value *> PointerToBase;
findBasePointers(result.liveset, PointerToBase, &DT, DVCache);
if (PrintBasePointers) {
// Note: Need to print these in a stable order since this is checked in
// some tests.
errs() << "Base Pairs (w/o Relocation):\n";
SmallVector<Value *, 64> Temp;
Temp.reserve(PointerToBase.size());
for (auto Pair : PointerToBase) {
Temp.push_back(Pair.first);
}
std::sort(Temp.begin(), Temp.end(), order_by_name);
for (Value *Ptr : Temp) {
Value *Base = PointerToBase[Ptr];
errs() << " derived %" << Ptr->getName() << " base %" << Base->getName()
<< "\n";