RewriteStatepointsForGC.cpp 114 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914
  1. //===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  8. //===----------------------------------------------------------------------===//
  9. //
  10. // Rewrite an existing set of gc.statepoints such that they make potential
  11. // relocations performed by the garbage collector explicit in the IR.
  12. //
  13. //===----------------------------------------------------------------------===//
  14. #include "llvm/Pass.h"
  15. #include "llvm/Analysis/CFG.h"
  16. #include "llvm/Analysis/InstructionSimplify.h"
  17. #include "llvm/Analysis/TargetTransformInfo.h"
  18. #include "llvm/ADT/SetOperations.h"
  19. #include "llvm/ADT/Statistic.h"
  20. #include "llvm/ADT/DenseSet.h"
  21. #include "llvm/ADT/SetVector.h"
  22. #include "llvm/ADT/StringRef.h"
  23. #include "llvm/ADT/MapVector.h"
  24. #include "llvm/IR/BasicBlock.h"
  25. #include "llvm/IR/CallSite.h"
  26. #include "llvm/IR/Dominators.h"
  27. #include "llvm/IR/Function.h"
  28. #include "llvm/IR/IRBuilder.h"
  29. #include "llvm/IR/InstIterator.h"
  30. #include "llvm/IR/Instructions.h"
  31. #include "llvm/IR/Intrinsics.h"
  32. #include "llvm/IR/IntrinsicInst.h"
  33. #include "llvm/IR/Module.h"
  34. #include "llvm/IR/MDBuilder.h"
  35. #include "llvm/IR/Statepoint.h"
  36. #include "llvm/IR/Value.h"
  37. #include "llvm/IR/Verifier.h"
  38. #include "llvm/Support/Debug.h"
  39. #include "llvm/Support/CommandLine.h"
  40. #include "llvm/Transforms/Scalar.h"
  41. #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  42. #include "llvm/Transforms/Utils/Cloning.h"
  43. #include "llvm/Transforms/Utils/Local.h"
  44. #include "llvm/Transforms/Utils/PromoteMemToReg.h"
  45. #define DEBUG_TYPE "rewrite-statepoints-for-gc"
  46. using namespace llvm;
  47. // Print the liveset found at the insert location
  48. static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden,
  49. cl::init(false));
  50. static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden,
  51. cl::init(false));
  52. // Print out the base pointers for debugging
  53. static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden,
  54. cl::init(false));
  55. // Cost threshold measuring when it is profitable to rematerialize value instead
  56. // of relocating it
  57. static cl::opt<unsigned>
  58. RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden,
  59. cl::init(6));
  60. #ifdef XDEBUG
  61. static bool ClobberNonLive = true;
  62. #else
  63. static bool ClobberNonLive = false;
  64. #endif
  65. static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",
  66. cl::location(ClobberNonLive),
  67. cl::Hidden);
  68. static cl::opt<bool> UseDeoptBundles("rs4gc-use-deopt-bundles", cl::Hidden,
  69. cl::init(false));
  70. static cl::opt<bool>
  71. AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",
  72. cl::Hidden, cl::init(true));
  73. /// Should we split vectors of pointers into their individual elements? This
  74. /// is known to be buggy, but the alternate implementation isn't yet ready.
  75. /// This is purely to provide a debugging and dianostic hook until the vector
  76. /// split is replaced with vector relocations.
  77. static cl::opt<bool> UseVectorSplit("rs4gc-split-vector-values", cl::Hidden,
  78. cl::init(false));
  79. namespace {
  80. struct RewriteStatepointsForGC : public ModulePass {
  81. static char ID; // Pass identification, replacement for typeid
  82. RewriteStatepointsForGC() : ModulePass(ID) {
  83. initializeRewriteStatepointsForGCPass(*PassRegistry::getPassRegistry());
  84. }
  85. bool runOnFunction(Function &F);
  86. bool runOnModule(Module &M) override {
  87. bool Changed = false;
  88. for (Function &F : M)
  89. Changed |= runOnFunction(F);
  90. if (Changed) {
  91. // stripNonValidAttributes asserts that shouldRewriteStatepointsIn
  92. // returns true for at least one function in the module. Since at least
  93. // one function changed, we know that the precondition is satisfied.
  94. stripNonValidAttributes(M);
  95. }
  96. return Changed;
  97. }
  98. void getAnalysisUsage(AnalysisUsage &AU) const override {
  99. // We add and rewrite a bunch of instructions, but don't really do much
  100. // else. We could in theory preserve a lot more analyses here.
  101. AU.addRequired<DominatorTreeWrapperPass>();
  102. AU.addRequired<TargetTransformInfoWrapperPass>();
  103. }
  104. /// The IR fed into RewriteStatepointsForGC may have had attributes implying
  105. /// dereferenceability that are no longer valid/correct after
  106. /// RewriteStatepointsForGC has run. This is because semantically, after
  107. /// RewriteStatepointsForGC runs, all calls to gc.statepoint "free" the entire
  108. /// heap. stripNonValidAttributes (conservatively) restores correctness
  109. /// by erasing all attributes in the module that externally imply
  110. /// dereferenceability.
  111. /// Similar reasoning also applies to the noalias attributes. gc.statepoint
  112. /// can touch the entire heap including noalias objects.
  113. void stripNonValidAttributes(Module &M);
  114. // Helpers for stripNonValidAttributes
  115. void stripNonValidAttributesFromBody(Function &F);
  116. void stripNonValidAttributesFromPrototype(Function &F);
  117. };
  118. } // namespace
  119. char RewriteStatepointsForGC::ID = 0;
  120. ModulePass *llvm::createRewriteStatepointsForGCPass() {
  121. return new RewriteStatepointsForGC();
  122. }
  123. INITIALIZE_PASS_BEGIN(RewriteStatepointsForGC, "rewrite-statepoints-for-gc",
  124. "Make relocations explicit at statepoints", false, false)
  125. INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  126. INITIALIZE_PASS_END(RewriteStatepointsForGC, "rewrite-statepoints-for-gc",
  127. "Make relocations explicit at statepoints", false, false)
  128. namespace {
  129. struct GCPtrLivenessData {
  130. /// Values defined in this block.
  131. DenseMap<BasicBlock *, DenseSet<Value *>> KillSet;
  132. /// Values used in this block (and thus live); does not included values
  133. /// killed within this block.
  134. DenseMap<BasicBlock *, DenseSet<Value *>> LiveSet;
  135. /// Values live into this basic block (i.e. used by any
  136. /// instruction in this basic block or ones reachable from here)
  137. DenseMap<BasicBlock *, DenseSet<Value *>> LiveIn;
  138. /// Values live out of this basic block (i.e. live into
  139. /// any successor block)
  140. DenseMap<BasicBlock *, DenseSet<Value *>> LiveOut;
  141. };
  142. // The type of the internal cache used inside the findBasePointers family
  143. // of functions. From the callers perspective, this is an opaque type and
  144. // should not be inspected.
  145. //
  146. // In the actual implementation this caches two relations:
  147. // - The base relation itself (i.e. this pointer is based on that one)
  148. // - The base defining value relation (i.e. before base_phi insertion)
  149. // Generally, after the execution of a full findBasePointer call, only the
  150. // base relation will remain. Internally, we add a mixture of the two
  151. // types, then update all the second type to the first type
  152. typedef DenseMap<Value *, Value *> DefiningValueMapTy;
  153. typedef DenseSet<Value *> StatepointLiveSetTy;
  154. typedef DenseMap<AssertingVH<Instruction>, AssertingVH<Value>>
  155. RematerializedValueMapTy;
  156. struct PartiallyConstructedSafepointRecord {
  157. /// The set of values known to be live across this safepoint
  158. StatepointLiveSetTy LiveSet;
  159. /// Mapping from live pointers to a base-defining-value
  160. DenseMap<Value *, Value *> PointerToBase;
  161. /// The *new* gc.statepoint instruction itself. This produces the token
  162. /// that normal path gc.relocates and the gc.result are tied to.
  163. Instruction *StatepointToken;
  164. /// Instruction to which exceptional gc relocates are attached
  165. /// Makes it easier to iterate through them during relocationViaAlloca.
  166. Instruction *UnwindToken;
  167. /// Record live values we are rematerialized instead of relocating.
  168. /// They are not included into 'LiveSet' field.
  169. /// Maps rematerialized copy to it's original value.
  170. RematerializedValueMapTy RematerializedValues;
  171. };
  172. }
  173. static ArrayRef<Use> GetDeoptBundleOperands(ImmutableCallSite CS) {
  174. assert(UseDeoptBundles && "Should not be called otherwise!");
  175. Optional<OperandBundleUse> DeoptBundle = CS.getOperandBundle("deopt");
  176. if (!DeoptBundle.hasValue()) {
  177. assert(AllowStatepointWithNoDeoptInfo &&
  178. "Found non-leaf call without deopt info!");
  179. return None;
  180. }
  181. return DeoptBundle.getValue().Inputs;
  182. }
  183. /// Compute the live-in set for every basic block in the function
  184. static void computeLiveInValues(DominatorTree &DT, Function &F,
  185. GCPtrLivenessData &Data);
  186. /// Given results from the dataflow liveness computation, find the set of live
  187. /// Values at a particular instruction.
  188. static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,
  189. StatepointLiveSetTy &out);
  190. // TODO: Once we can get to the GCStrategy, this becomes
  191. // Optional<bool> isGCManagedPointer(const Type *Ty) const override {
  192. static bool isGCPointerType(Type *T) {
  193. if (auto *PT = dyn_cast<PointerType>(T))
  194. // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
  195. // GC managed heap. We know that a pointer into this heap needs to be
  196. // updated and that no other pointer does.
  197. return (1 == PT->getAddressSpace());
  198. return false;
  199. }
  200. // Return true if this type is one which a) is a gc pointer or contains a GC
  201. // pointer and b) is of a type this code expects to encounter as a live value.
  202. // (The insertion code will assert that a type which matches (a) and not (b)
  203. // is not encountered.)
  204. static bool isHandledGCPointerType(Type *T) {
  205. // We fully support gc pointers
  206. if (isGCPointerType(T))
  207. return true;
  208. // We partially support vectors of gc pointers. The code will assert if it
  209. // can't handle something.
  210. if (auto VT = dyn_cast<VectorType>(T))
  211. if (isGCPointerType(VT->getElementType()))
  212. return true;
  213. return false;
  214. }
  215. #ifndef NDEBUG
  216. /// Returns true if this type contains a gc pointer whether we know how to
  217. /// handle that type or not.
  218. static bool containsGCPtrType(Type *Ty) {
  219. if (isGCPointerType(Ty))
  220. return true;
  221. if (VectorType *VT = dyn_cast<VectorType>(Ty))
  222. return isGCPointerType(VT->getScalarType());
  223. if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
  224. return containsGCPtrType(AT->getElementType());
  225. if (StructType *ST = dyn_cast<StructType>(Ty))
  226. return std::any_of(ST->subtypes().begin(), ST->subtypes().end(),
  227. containsGCPtrType);
  228. return false;
  229. }
  230. // Returns true if this is a type which a) is a gc pointer or contains a GC
  231. // pointer and b) is of a type which the code doesn't expect (i.e. first class
  232. // aggregates). Used to trip assertions.
  233. static bool isUnhandledGCPointerType(Type *Ty) {
  234. return containsGCPtrType(Ty) && !isHandledGCPointerType(Ty);
  235. }
  236. #endif
  237. static bool order_by_name(Value *a, Value *b) {
  238. if (a->hasName() && b->hasName()) {
  239. return -1 == a->getName().compare(b->getName());
  240. } else if (a->hasName() && !b->hasName()) {
  241. return true;
  242. } else if (!a->hasName() && b->hasName()) {
  243. return false;
  244. } else {
  245. // Better than nothing, but not stable
  246. return a < b;
  247. }
  248. }
  249. // Return the name of the value suffixed with the provided value, or if the
  250. // value didn't have a name, the default value specified.
  251. static std::string suffixed_name_or(Value *V, StringRef Suffix,
  252. StringRef DefaultName) {
  253. return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str();
  254. }
  255. // Conservatively identifies any definitions which might be live at the
  256. // given instruction. The analysis is performed immediately before the
  257. // given instruction. Values defined by that instruction are not considered
  258. // live. Values used by that instruction are considered live.
  259. static void analyzeParsePointLiveness(
  260. DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData,
  261. const CallSite &CS, PartiallyConstructedSafepointRecord &result) {
  262. Instruction *inst = CS.getInstruction();
  263. StatepointLiveSetTy LiveSet;
  264. findLiveSetAtInst(inst, OriginalLivenessData, LiveSet);
  265. if (PrintLiveSet) {
  266. // Note: This output is used by several of the test cases
  267. // The order of elements in a set is not stable, put them in a vec and sort
  268. // by name
  269. SmallVector<Value *, 64> Temp;
  270. Temp.insert(Temp.end(), LiveSet.begin(), LiveSet.end());
  271. std::sort(Temp.begin(), Temp.end(), order_by_name);
  272. errs() << "Live Variables:\n";
  273. for (Value *V : Temp)
  274. dbgs() << " " << V->getName() << " " << *V << "\n";
  275. }
  276. if (PrintLiveSetSize) {
  277. errs() << "Safepoint For: " << CS.getCalledValue()->getName() << "\n";
  278. errs() << "Number live values: " << LiveSet.size() << "\n";
  279. }
  280. result.LiveSet = LiveSet;
  281. }
  282. static bool isKnownBaseResult(Value *V);
  283. namespace {
  284. /// A single base defining value - An immediate base defining value for an
  285. /// instruction 'Def' is an input to 'Def' whose base is also a base of 'Def'.
  286. /// For instructions which have multiple pointer [vector] inputs or that
  287. /// transition between vector and scalar types, there is no immediate base
  288. /// defining value. The 'base defining value' for 'Def' is the transitive
  289. /// closure of this relation stopping at the first instruction which has no
  290. /// immediate base defining value. The b.d.v. might itself be a base pointer,
  291. /// but it can also be an arbitrary derived pointer.
  292. struct BaseDefiningValueResult {
  293. /// Contains the value which is the base defining value.
  294. Value * const BDV;
  295. /// True if the base defining value is also known to be an actual base
  296. /// pointer.
  297. const bool IsKnownBase;
  298. BaseDefiningValueResult(Value *BDV, bool IsKnownBase)
  299. : BDV(BDV), IsKnownBase(IsKnownBase) {
  300. #ifndef NDEBUG
  301. // Check consistency between new and old means of checking whether a BDV is
  302. // a base.
  303. bool MustBeBase = isKnownBaseResult(BDV);
  304. assert(!MustBeBase || MustBeBase == IsKnownBase);
  305. #endif
  306. }
  307. };
  308. }
  309. static BaseDefiningValueResult findBaseDefiningValue(Value *I);
  310. /// Return a base defining value for the 'Index' element of the given vector
  311. /// instruction 'I'. If Index is null, returns a BDV for the entire vector
  312. /// 'I'. As an optimization, this method will try to determine when the
  313. /// element is known to already be a base pointer. If this can be established,
  314. /// the second value in the returned pair will be true. Note that either a
  315. /// vector or a pointer typed value can be returned. For the former, the
  316. /// vector returned is a BDV (and possibly a base) of the entire vector 'I'.
  317. /// If the later, the return pointer is a BDV (or possibly a base) for the
  318. /// particular element in 'I'.
  319. static BaseDefiningValueResult
  320. findBaseDefiningValueOfVector(Value *I) {
  321. // Each case parallels findBaseDefiningValue below, see that code for
  322. // detailed motivation.
  323. if (isa<Argument>(I))
  324. // An incoming argument to the function is a base pointer
  325. return BaseDefiningValueResult(I, true);
  326. if (isa<Constant>(I))
  327. // Constant vectors consist only of constant pointers.
  328. return BaseDefiningValueResult(I, true);
  329. if (isa<LoadInst>(I))
  330. return BaseDefiningValueResult(I, true);
  331. if (isa<InsertElementInst>(I))
  332. // We don't know whether this vector contains entirely base pointers or
  333. // not. To be conservatively correct, we treat it as a BDV and will
  334. // duplicate code as needed to construct a parallel vector of bases.
  335. return BaseDefiningValueResult(I, false);
  336. if (isa<ShuffleVectorInst>(I))
  337. // We don't know whether this vector contains entirely base pointers or
  338. // not. To be conservatively correct, we treat it as a BDV and will
  339. // duplicate code as needed to construct a parallel vector of bases.
  340. // TODO: There a number of local optimizations which could be applied here
  341. // for particular sufflevector patterns.
  342. return BaseDefiningValueResult(I, false);
  343. // A PHI or Select is a base defining value. The outer findBasePointer
  344. // algorithm is responsible for constructing a base value for this BDV.
  345. assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
  346. "unknown vector instruction - no base found for vector element");
  347. return BaseDefiningValueResult(I, false);
  348. }
  349. /// Helper function for findBasePointer - Will return a value which either a)
  350. /// defines the base pointer for the input, b) blocks the simple search
  351. /// (i.e. a PHI or Select of two derived pointers), or c) involves a change
  352. /// from pointer to vector type or back.
  353. static BaseDefiningValueResult findBaseDefiningValue(Value *I) {
  354. assert(I->getType()->isPtrOrPtrVectorTy() &&
  355. "Illegal to ask for the base pointer of a non-pointer type");
  356. if (I->getType()->isVectorTy())
  357. return findBaseDefiningValueOfVector(I);
  358. if (isa<Argument>(I))
  359. // An incoming argument to the function is a base pointer
  360. // We should have never reached here if this argument isn't an gc value
  361. return BaseDefiningValueResult(I, true);
  362. if (isa<Constant>(I))
  363. // We assume that objects with a constant base (e.g. a global) can't move
  364. // and don't need to be reported to the collector because they are always
  365. // live. All constants have constant bases. Besides global references, all
  366. // kinds of constants (e.g. undef, constant expressions, null pointers) can
  367. // be introduced by the inliner or the optimizer, especially on dynamically
  368. // dead paths. See e.g. test4 in constants.ll.
  369. return BaseDefiningValueResult(I, true);
  370. if (CastInst *CI = dyn_cast<CastInst>(I)) {
  371. Value *Def = CI->stripPointerCasts();
  372. // If stripping pointer casts changes the address space there is an
  373. // addrspacecast in between.
  374. assert(cast<PointerType>(Def->getType())->getAddressSpace() ==
  375. cast<PointerType>(CI->getType())->getAddressSpace() &&
  376. "unsupported addrspacecast");
  377. // If we find a cast instruction here, it means we've found a cast which is
  378. // not simply a pointer cast (i.e. an inttoptr). We don't know how to
  379. // handle int->ptr conversion.
  380. assert(!isa<CastInst>(Def) && "shouldn't find another cast here");
  381. return findBaseDefiningValue(Def);
  382. }
  383. if (isa<LoadInst>(I))
  384. // The value loaded is an gc base itself
  385. return BaseDefiningValueResult(I, true);
  386. if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I))
  387. // The base of this GEP is the base
  388. return findBaseDefiningValue(GEP->getPointerOperand());
  389. if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
  390. switch (II->getIntrinsicID()) {
  391. default:
  392. // fall through to general call handling
  393. break;
  394. case Intrinsic::experimental_gc_statepoint:
  395. llvm_unreachable("statepoints don't produce pointers");
  396. case Intrinsic::experimental_gc_relocate: {
  397. // Rerunning safepoint insertion after safepoints are already
  398. // inserted is not supported. It could probably be made to work,
  399. // but why are you doing this? There's no good reason.
  400. llvm_unreachable("repeat safepoint insertion is not supported");
  401. }
  402. case Intrinsic::gcroot:
  403. // Currently, this mechanism hasn't been extended to work with gcroot.
  404. // There's no reason it couldn't be, but I haven't thought about the
  405. // implications much.
  406. llvm_unreachable(
  407. "interaction with the gcroot mechanism is not supported");
  408. }
  409. }
  410. // We assume that functions in the source language only return base
  411. // pointers. This should probably be generalized via attributes to support
  412. // both source language and internal functions.
  413. if (isa<CallInst>(I) || isa<InvokeInst>(I))
  414. return BaseDefiningValueResult(I, true);
  415. // I have absolutely no idea how to implement this part yet. It's not
  416. // necessarily hard, I just haven't really looked at it yet.
  417. assert(!isa<LandingPadInst>(I) && "Landing Pad is unimplemented");
  418. if (isa<AtomicCmpXchgInst>(I))
  419. // A CAS is effectively a atomic store and load combined under a
  420. // predicate. From the perspective of base pointers, we just treat it
  421. // like a load.
  422. return BaseDefiningValueResult(I, true);
  423. assert(!isa<AtomicRMWInst>(I) && "Xchg handled above, all others are "
  424. "binary ops which don't apply to pointers");
  425. // The aggregate ops. Aggregates can either be in the heap or on the
  426. // stack, but in either case, this is simply a field load. As a result,
  427. // this is a defining definition of the base just like a load is.
  428. if (isa<ExtractValueInst>(I))
  429. return BaseDefiningValueResult(I, true);
  430. // We should never see an insert vector since that would require we be
  431. // tracing back a struct value not a pointer value.
  432. assert(!isa<InsertValueInst>(I) &&
  433. "Base pointer for a struct is meaningless");
  434. // An extractelement produces a base result exactly when it's input does.
  435. // We may need to insert a parallel instruction to extract the appropriate
  436. // element out of the base vector corresponding to the input. Given this,
  437. // it's analogous to the phi and select case even though it's not a merge.
  438. if (isa<ExtractElementInst>(I))
  439. // Note: There a lot of obvious peephole cases here. This are deliberately
  440. // handled after the main base pointer inference algorithm to make writing
  441. // test cases to exercise that code easier.
  442. return BaseDefiningValueResult(I, false);
  443. // The last two cases here don't return a base pointer. Instead, they
  444. // return a value which dynamically selects from among several base
  445. // derived pointers (each with it's own base potentially). It's the job of
  446. // the caller to resolve these.
  447. assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
  448. "missing instruction case in findBaseDefiningValing");
  449. return BaseDefiningValueResult(I, false);
  450. }
  451. /// Returns the base defining value for this value.
  452. static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache) {
  453. Value *&Cached = Cache[I];
  454. if (!Cached) {
  455. Cached = findBaseDefiningValue(I).BDV;
  456. DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> "
  457. << Cached->getName() << "\n");
  458. }
  459. assert(Cache[I] != nullptr);
  460. return Cached;
  461. }
  462. /// Return a base pointer for this value if known. Otherwise, return it's
  463. /// base defining value.
  464. static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache) {
  465. Value *Def = findBaseDefiningValueCached(I, Cache);
  466. auto Found = Cache.find(Def);
  467. if (Found != Cache.end()) {
  468. // Either a base-of relation, or a self reference. Caller must check.
  469. return Found->second;
  470. }
  471. // Only a BDV available
  472. return Def;
  473. }
  474. /// Given the result of a call to findBaseDefiningValue, or findBaseOrBDV,
  475. /// is it known to be a base pointer? Or do we need to continue searching.
  476. static bool isKnownBaseResult(Value *V) {
  477. if (!isa<PHINode>(V) && !isa<SelectInst>(V) &&
  478. !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&
  479. !isa<ShuffleVectorInst>(V)) {
  480. // no recursion possible
  481. return true;
  482. }
  483. if (isa<Instruction>(V) &&
  484. cast<Instruction>(V)->getMetadata("is_base_value")) {
  485. // This is a previously inserted base phi or select. We know
  486. // that this is a base value.
  487. return true;
  488. }
  489. // We need to keep searching
  490. return false;
  491. }
  492. namespace {
  493. /// Models the state of a single base defining value in the findBasePointer
  494. /// algorithm for determining where a new instruction is needed to propagate
  495. /// the base of this BDV.
  496. class BDVState {
  497. public:
  498. enum Status { Unknown, Base, Conflict };
  499. BDVState(Status s, Value *b = nullptr) : status(s), base(b) {
  500. assert(status != Base || b);
  501. }
  502. explicit BDVState(Value *b) : status(Base), base(b) {}
  503. BDVState() : status(Unknown), base(nullptr) {}
  504. Status getStatus() const { return status; }
  505. Value *getBase() const { return base; }
  506. bool isBase() const { return getStatus() == Base; }
  507. bool isUnknown() const { return getStatus() == Unknown; }
  508. bool isConflict() const { return getStatus() == Conflict; }
  509. bool operator==(const BDVState &other) const {
  510. return base == other.base && status == other.status;
  511. }
  512. bool operator!=(const BDVState &other) const { return !(*this == other); }
  513. LLVM_DUMP_METHOD
  514. void dump() const { print(dbgs()); dbgs() << '\n'; }
  515. void print(raw_ostream &OS) const {
  516. switch (status) {
  517. case Unknown:
  518. OS << "U";
  519. break;
  520. case Base:
  521. OS << "B";
  522. break;
  523. case Conflict:
  524. OS << "C";
  525. break;
  526. };
  527. OS << " (" << base << " - "
  528. << (base ? base->getName() : "nullptr") << "): ";
  529. }
  530. private:
  531. Status status;
  532. AssertingVH<Value> base; // non null only if status == base
  533. };
  534. }
  535. #ifndef NDEBUG
  536. static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) {
  537. State.print(OS);
  538. return OS;
  539. }
  540. #endif
  541. namespace {
  542. // Values of type BDVState form a lattice, and this is a helper
  543. // class that implementes the meet operation. The meat of the meet
  544. // operation is implemented in MeetBDVStates::pureMeet
  545. class MeetBDVStates {
  546. public:
  547. /// Initializes the currentResult to the TOP state so that if can be met with
  548. /// any other state to produce that state.
  549. MeetBDVStates() {}
  550. // Destructively meet the current result with the given BDVState
  551. void meetWith(BDVState otherState) {
  552. currentResult = meet(otherState, currentResult);
  553. }
  554. BDVState getResult() const { return currentResult; }
  555. private:
  556. BDVState currentResult;
  557. /// Perform a meet operation on two elements of the BDVState lattice.
  558. static BDVState meet(BDVState LHS, BDVState RHS) {
  559. assert((pureMeet(LHS, RHS) == pureMeet(RHS, LHS)) &&
  560. "math is wrong: meet does not commute!");
  561. BDVState Result = pureMeet(LHS, RHS);
  562. DEBUG(dbgs() << "meet of " << LHS << " with " << RHS
  563. << " produced " << Result << "\n");
  564. return Result;
  565. }
  566. static BDVState pureMeet(const BDVState &stateA, const BDVState &stateB) {
  567. switch (stateA.getStatus()) {
  568. case BDVState::Unknown:
  569. return stateB;
  570. case BDVState::Base:
  571. assert(stateA.getBase() && "can't be null");
  572. if (stateB.isUnknown())
  573. return stateA;
  574. if (stateB.isBase()) {
  575. if (stateA.getBase() == stateB.getBase()) {
  576. assert(stateA == stateB && "equality broken!");
  577. return stateA;
  578. }
  579. return BDVState(BDVState::Conflict);
  580. }
  581. assert(stateB.isConflict() && "only three states!");
  582. return BDVState(BDVState::Conflict);
  583. case BDVState::Conflict:
  584. return stateA;
  585. }
  586. llvm_unreachable("only three states!");
  587. }
  588. };
  589. }
  590. /// For a given value or instruction, figure out what base ptr it's derived
  591. /// from. For gc objects, this is simply itself. On success, returns a value
  592. /// which is the base pointer. (This is reliable and can be used for
  593. /// relocation.) On failure, returns nullptr.
  594. static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) {
  595. Value *def = findBaseOrBDV(I, cache);
  596. if (isKnownBaseResult(def)) {
  597. return def;
  598. }
  599. // Here's the rough algorithm:
  600. // - For every SSA value, construct a mapping to either an actual base
  601. // pointer or a PHI which obscures the base pointer.
  602. // - Construct a mapping from PHI to unknown TOP state. Use an
  603. // optimistic algorithm to propagate base pointer information. Lattice
  604. // looks like:
  605. // UNKNOWN
  606. // b1 b2 b3 b4
  607. // CONFLICT
  608. // When algorithm terminates, all PHIs will either have a single concrete
  609. // base or be in a conflict state.
  610. // - For every conflict, insert a dummy PHI node without arguments. Add
  611. // these to the base[Instruction] = BasePtr mapping. For every
  612. // non-conflict, add the actual base.
  613. // - For every conflict, add arguments for the base[a] of each input
  614. // arguments.
  615. //
  616. // Note: A simpler form of this would be to add the conflict form of all
  617. // PHIs without running the optimistic algorithm. This would be
  618. // analogous to pessimistic data flow and would likely lead to an
  619. // overall worse solution.
  620. #ifndef NDEBUG
  621. auto isExpectedBDVType = [](Value *BDV) {
  622. return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||
  623. isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV);
  624. };
  625. #endif
  626. // Once populated, will contain a mapping from each potentially non-base BDV
  627. // to a lattice value (described above) which corresponds to that BDV.
  628. // We use the order of insertion (DFS over the def/use graph) to provide a
  629. // stable deterministic ordering for visiting DenseMaps (which are unordered)
  630. // below. This is important for deterministic compilation.
  631. MapVector<Value *, BDVState> States;
  632. // Recursively fill in all base defining values reachable from the initial
  633. // one for which we don't already know a definite base value for
  634. /* scope */ {
  635. SmallVector<Value*, 16> Worklist;
  636. Worklist.push_back(def);
  637. States.insert(std::make_pair(def, BDVState()));
  638. while (!Worklist.empty()) {
  639. Value *Current = Worklist.pop_back_val();
  640. assert(!isKnownBaseResult(Current) && "why did it get added?");
  641. auto visitIncomingValue = [&](Value *InVal) {
  642. Value *Base = findBaseOrBDV(InVal, cache);
  643. if (isKnownBaseResult(Base))
  644. // Known bases won't need new instructions introduced and can be
  645. // ignored safely
  646. return;
  647. assert(isExpectedBDVType(Base) && "the only non-base values "
  648. "we see should be base defining values");
  649. if (States.insert(std::make_pair(Base, BDVState())).second)
  650. Worklist.push_back(Base);
  651. };
  652. if (PHINode *Phi = dyn_cast<PHINode>(Current)) {
  653. for (Value *InVal : Phi->incoming_values())
  654. visitIncomingValue(InVal);
  655. } else if (SelectInst *Sel = dyn_cast<SelectInst>(Current)) {
  656. visitIncomingValue(Sel->getTrueValue());
  657. visitIncomingValue(Sel->getFalseValue());
  658. } else if (auto *EE = dyn_cast<ExtractElementInst>(Current)) {
  659. visitIncomingValue(EE->getVectorOperand());
  660. } else if (auto *IE = dyn_cast<InsertElementInst>(Current)) {
  661. visitIncomingValue(IE->getOperand(0)); // vector operand
  662. visitIncomingValue(IE->getOperand(1)); // scalar operand
  663. } else {
  664. // There is one known class of instructions we know we don't handle.
  665. assert(isa<ShuffleVectorInst>(Current));
  666. llvm_unreachable("unimplemented instruction case");
  667. }
  668. }
  669. }
  670. #ifndef NDEBUG
  671. DEBUG(dbgs() << "States after initialization:\n");
  672. for (auto Pair : States) {
  673. DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
  674. }
  675. #endif
  676. // Return a phi state for a base defining value. We'll generate a new
  677. // base state for known bases and expect to find a cached state otherwise.
  678. auto getStateForBDV = [&](Value *baseValue) {
  679. if (isKnownBaseResult(baseValue))
  680. return BDVState(baseValue);
  681. auto I = States.find(baseValue);
  682. assert(I != States.end() && "lookup failed!");
  683. return I->second;
  684. };
  685. bool progress = true;
  686. while (progress) {
  687. #ifndef NDEBUG
  688. const size_t oldSize = States.size();
  689. #endif
  690. progress = false;
  691. // We're only changing values in this loop, thus safe to keep iterators.
  692. // Since this is computing a fixed point, the order of visit does not
  693. // effect the result. TODO: We could use a worklist here and make this run
  694. // much faster.
  695. for (auto Pair : States) {
  696. Value *BDV = Pair.first;
  697. assert(!isKnownBaseResult(BDV) && "why did it get added?");
  698. // Given an input value for the current instruction, return a BDVState
  699. // instance which represents the BDV of that value.
  700. auto getStateForInput = [&](Value *V) mutable {
  701. Value *BDV = findBaseOrBDV(V, cache);
  702. return getStateForBDV(BDV);
  703. };
  704. MeetBDVStates calculateMeet;
  705. if (SelectInst *select = dyn_cast<SelectInst>(BDV)) {
  706. calculateMeet.meetWith(getStateForInput(select->getTrueValue()));
  707. calculateMeet.meetWith(getStateForInput(select->getFalseValue()));
  708. } else if (PHINode *Phi = dyn_cast<PHINode>(BDV)) {
  709. for (Value *Val : Phi->incoming_values())
  710. calculateMeet.meetWith(getStateForInput(Val));
  711. } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) {
  712. // The 'meet' for an extractelement is slightly trivial, but it's still
  713. // useful in that it drives us to conflict if our input is.
  714. calculateMeet.meetWith(getStateForInput(EE->getVectorOperand()));
  715. } else {
  716. // Given there's a inherent type mismatch between the operands, will
  717. // *always* produce Conflict.
  718. auto *IE = cast<InsertElementInst>(BDV);
  719. calculateMeet.meetWith(getStateForInput(IE->getOperand(0)));
  720. calculateMeet.meetWith(getStateForInput(IE->getOperand(1)));
  721. }
  722. BDVState oldState = States[BDV];
  723. BDVState newState = calculateMeet.getResult();
  724. if (oldState != newState) {
  725. progress = true;
  726. States[BDV] = newState;
  727. }
  728. }
  729. assert(oldSize == States.size() &&
  730. "fixed point shouldn't be adding any new nodes to state");
  731. }
  732. #ifndef NDEBUG
  733. DEBUG(dbgs() << "States after meet iteration:\n");
  734. for (auto Pair : States) {
  735. DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
  736. }
  737. #endif
  738. // Insert Phis for all conflicts
  739. // TODO: adjust naming patterns to avoid this order of iteration dependency
  740. for (auto Pair : States) {
  741. Instruction *I = cast<Instruction>(Pair.first);
  742. BDVState State = Pair.second;
  743. assert(!isKnownBaseResult(I) && "why did it get added?");
  744. assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
  745. // extractelement instructions are a bit special in that we may need to
  746. // insert an extract even when we know an exact base for the instruction.
  747. // The problem is that we need to convert from a vector base to a scalar
  748. // base for the particular indice we're interested in.
  749. if (State.isBase() && isa<ExtractElementInst>(I) &&
  750. isa<VectorType>(State.getBase()->getType())) {
  751. auto *EE = cast<ExtractElementInst>(I);
  752. // TODO: In many cases, the new instruction is just EE itself. We should
  753. // exploit this, but can't do it here since it would break the invariant
  754. // about the BDV not being known to be a base.
  755. auto *BaseInst = ExtractElementInst::Create(State.getBase(),
  756. EE->getIndexOperand(),
  757. "base_ee", EE);
  758. BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
  759. States[I] = BDVState(BDVState::Base, BaseInst);
  760. }
  761. // Since we're joining a vector and scalar base, they can never be the
  762. // same. As a result, we should always see insert element having reached
  763. // the conflict state.
  764. if (isa<InsertElementInst>(I)) {
  765. assert(State.isConflict());
  766. }
  767. if (!State.isConflict())
  768. continue;
  769. /// Create and insert a new instruction which will represent the base of
  770. /// the given instruction 'I'.
  771. auto MakeBaseInstPlaceholder = [](Instruction *I) -> Instruction* {
  772. if (isa<PHINode>(I)) {
  773. BasicBlock *BB = I->getParent();
  774. int NumPreds = std::distance(pred_begin(BB), pred_end(BB));
  775. assert(NumPreds > 0 && "how did we reach here");
  776. std::string Name = suffixed_name_or(I, ".base", "base_phi");
  777. return PHINode::Create(I->getType(), NumPreds, Name, I);
  778. } else if (SelectInst *Sel = dyn_cast<SelectInst>(I)) {
  779. // The undef will be replaced later
  780. UndefValue *Undef = UndefValue::get(Sel->getType());
  781. std::string Name = suffixed_name_or(I, ".base", "base_select");
  782. return SelectInst::Create(Sel->getCondition(), Undef,
  783. Undef, Name, Sel);
  784. } else if (auto *EE = dyn_cast<ExtractElementInst>(I)) {
  785. UndefValue *Undef = UndefValue::get(EE->getVectorOperand()->getType());
  786. std::string Name = suffixed_name_or(I, ".base", "base_ee");
  787. return ExtractElementInst::Create(Undef, EE->getIndexOperand(), Name,
  788. EE);
  789. } else {
  790. auto *IE = cast<InsertElementInst>(I);
  791. UndefValue *VecUndef = UndefValue::get(IE->getOperand(0)->getType());
  792. UndefValue *ScalarUndef = UndefValue::get(IE->getOperand(1)->getType());
  793. std::string Name = suffixed_name_or(I, ".base", "base_ie");
  794. return InsertElementInst::Create(VecUndef, ScalarUndef,
  795. IE->getOperand(2), Name, IE);
  796. }
  797. };
  798. Instruction *BaseInst = MakeBaseInstPlaceholder(I);
  799. // Add metadata marking this as a base value
  800. BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
  801. States[I] = BDVState(BDVState::Conflict, BaseInst);
  802. }
  803. // Returns a instruction which produces the base pointer for a given
  804. // instruction. The instruction is assumed to be an input to one of the BDVs
  805. // seen in the inference algorithm above. As such, we must either already
  806. // know it's base defining value is a base, or have inserted a new
  807. // instruction to propagate the base of it's BDV and have entered that newly
  808. // introduced instruction into the state table. In either case, we are
  809. // assured to be able to determine an instruction which produces it's base
  810. // pointer.
  811. auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) {
  812. Value *BDV = findBaseOrBDV(Input, cache);
  813. Value *Base = nullptr;
  814. if (isKnownBaseResult(BDV)) {
  815. Base = BDV;
  816. } else {
  817. // Either conflict or base.
  818. assert(States.count(BDV));
  819. Base = States[BDV].getBase();
  820. }
  821. assert(Base && "can't be null");
  822. // The cast is needed since base traversal may strip away bitcasts
  823. if (Base->getType() != Input->getType() &&
  824. InsertPt) {
  825. Base = new BitCastInst(Base, Input->getType(), "cast",
  826. InsertPt);
  827. }
  828. return Base;
  829. };
  830. // Fixup all the inputs of the new PHIs. Visit order needs to be
  831. // deterministic and predictable because we're naming newly created
  832. // instructions.
  833. for (auto Pair : States) {
  834. Instruction *BDV = cast<Instruction>(Pair.first);
  835. BDVState State = Pair.second;
  836. assert(!isKnownBaseResult(BDV) && "why did it get added?");
  837. assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
  838. if (!State.isConflict())
  839. continue;
  840. if (PHINode *basephi = dyn_cast<PHINode>(State.getBase())) {
  841. PHINode *phi = cast<PHINode>(BDV);
  842. unsigned NumPHIValues = phi->getNumIncomingValues();
  843. for (unsigned i = 0; i < NumPHIValues; i++) {
  844. Value *InVal = phi->getIncomingValue(i);
  845. BasicBlock *InBB = phi->getIncomingBlock(i);
  846. // If we've already seen InBB, add the same incoming value
  847. // we added for it earlier. The IR verifier requires phi
  848. // nodes with multiple entries from the same basic block
  849. // to have the same incoming value for each of those
  850. // entries. If we don't do this check here and basephi
  851. // has a different type than base, we'll end up adding two
  852. // bitcasts (and hence two distinct values) as incoming
  853. // values for the same basic block.
  854. int blockIndex = basephi->getBasicBlockIndex(InBB);
  855. if (blockIndex != -1) {
  856. Value *oldBase = basephi->getIncomingValue(blockIndex);
  857. basephi->addIncoming(oldBase, InBB);
  858. #ifndef NDEBUG
  859. Value *Base = getBaseForInput(InVal, nullptr);
  860. // In essence this assert states: the only way two
  861. // values incoming from the same basic block may be
  862. // different is by being different bitcasts of the same
  863. // value. A cleanup that remains TODO is changing
  864. // findBaseOrBDV to return an llvm::Value of the correct
  865. // type (and still remain pure). This will remove the
  866. // need to add bitcasts.
  867. assert(Base->stripPointerCasts() == oldBase->stripPointerCasts() &&
  868. "sanity -- findBaseOrBDV should be pure!");
  869. #endif
  870. continue;
  871. }
  872. // Find the instruction which produces the base for each input. We may
  873. // need to insert a bitcast in the incoming block.
  874. // TODO: Need to split critical edges if insertion is needed
  875. Value *Base = getBaseForInput(InVal, InBB->getTerminator());
  876. basephi->addIncoming(Base, InBB);
  877. }
  878. assert(basephi->getNumIncomingValues() == NumPHIValues);
  879. } else if (SelectInst *BaseSel = dyn_cast<SelectInst>(State.getBase())) {
  880. SelectInst *Sel = cast<SelectInst>(BDV);
  881. // Operand 1 & 2 are true, false path respectively. TODO: refactor to
  882. // something more safe and less hacky.
  883. for (int i = 1; i <= 2; i++) {
  884. Value *InVal = Sel->getOperand(i);
  885. // Find the instruction which produces the base for each input. We may
  886. // need to insert a bitcast.
  887. Value *Base = getBaseForInput(InVal, BaseSel);
  888. BaseSel->setOperand(i, Base);
  889. }
  890. } else if (auto *BaseEE = dyn_cast<ExtractElementInst>(State.getBase())) {
  891. Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();
  892. // Find the instruction which produces the base for each input. We may
  893. // need to insert a bitcast.
  894. Value *Base = getBaseForInput(InVal, BaseEE);
  895. BaseEE->setOperand(0, Base);
  896. } else {
  897. auto *BaseIE = cast<InsertElementInst>(State.getBase());
  898. auto *BdvIE = cast<InsertElementInst>(BDV);
  899. auto UpdateOperand = [&](int OperandIdx) {
  900. Value *InVal = BdvIE->getOperand(OperandIdx);
  901. Value *Base = getBaseForInput(InVal, BaseIE);
  902. BaseIE->setOperand(OperandIdx, Base);
  903. };
  904. UpdateOperand(0); // vector operand
  905. UpdateOperand(1); // scalar operand
  906. }
  907. }
  908. // Now that we're done with the algorithm, see if we can optimize the
  909. // results slightly by reducing the number of new instructions needed.
  910. // Arguably, this should be integrated into the algorithm above, but
  911. // doing as a post process step is easier to reason about for the moment.
  912. DenseMap<Value *, Value *> ReverseMap;
  913. SmallPtrSet<Instruction *, 16> NewInsts;
  914. SmallSetVector<AssertingVH<Instruction>, 16> Worklist;
  915. // Note: We need to visit the states in a deterministic order. We uses the
  916. // Keys we sorted above for this purpose. Note that we are papering over a
  917. // bigger problem with the algorithm above - it's visit order is not
  918. // deterministic. A larger change is needed to fix this.
  919. for (auto Pair : States) {
  920. auto *BDV = Pair.first;
  921. auto State = Pair.second;
  922. Value *Base = State.getBase();
  923. assert(BDV && Base);
  924. assert(!isKnownBaseResult(BDV) && "why did it get added?");
  925. assert(isKnownBaseResult(Base) &&
  926. "must be something we 'know' is a base pointer");
  927. if (!State.isConflict())
  928. continue;
  929. ReverseMap[Base] = BDV;
  930. if (auto *BaseI = dyn_cast<Instruction>(Base)) {
  931. NewInsts.insert(BaseI);
  932. Worklist.insert(BaseI);
  933. }
  934. }
  935. auto ReplaceBaseInstWith = [&](Value *BDV, Instruction *BaseI,
  936. Value *Replacement) {
  937. // Add users which are new instructions (excluding self references)
  938. for (User *U : BaseI->users())
  939. if (auto *UI = dyn_cast<Instruction>(U))
  940. if (NewInsts.count(UI) && UI != BaseI)
  941. Worklist.insert(UI);
  942. // Then do the actual replacement
  943. NewInsts.erase(BaseI);
  944. ReverseMap.erase(BaseI);
  945. BaseI->replaceAllUsesWith(Replacement);
  946. assert(States.count(BDV));
  947. assert(States[BDV].isConflict() && States[BDV].getBase() == BaseI);
  948. States[BDV] = BDVState(BDVState::Conflict, Replacement);
  949. BaseI->eraseFromParent();
  950. };
  951. const DataLayout &DL = cast<Instruction>(def)->getModule()->getDataLayout();
  952. while (!Worklist.empty()) {
  953. Instruction *BaseI = Worklist.pop_back_val();
  954. assert(NewInsts.count(BaseI));
  955. Value *Bdv = ReverseMap[BaseI];
  956. if (auto *BdvI = dyn_cast<Instruction>(Bdv))
  957. if (BaseI->isIdenticalTo(BdvI)) {
  958. DEBUG(dbgs() << "Identical Base: " << *BaseI << "\n");
  959. ReplaceBaseInstWith(Bdv, BaseI, Bdv);
  960. continue;
  961. }
  962. if (Value *V = SimplifyInstruction(BaseI, DL)) {
  963. DEBUG(dbgs() << "Base " << *BaseI << " simplified to " << *V << "\n");
  964. ReplaceBaseInstWith(Bdv, BaseI, V);
  965. continue;
  966. }
  967. }
  968. // Cache all of our results so we can cheaply reuse them
  969. // NOTE: This is actually two caches: one of the base defining value
  970. // relation and one of the base pointer relation! FIXME
  971. for (auto Pair : States) {
  972. auto *BDV = Pair.first;
  973. Value *base = Pair.second.getBase();
  974. assert(BDV && base);
  975. std::string fromstr = cache.count(BDV) ? cache[BDV]->getName() : "none";
  976. DEBUG(dbgs() << "Updating base value cache"
  977. << " for: " << BDV->getName()
  978. << " from: " << fromstr
  979. << " to: " << base->getName() << "\n");
  980. if (cache.count(BDV)) {
  981. // Once we transition from the BDV relation being store in the cache to
  982. // the base relation being stored, it must be stable
  983. assert((!isKnownBaseResult(cache[BDV]) || cache[BDV] == base) &&
  984. "base relation should be stable");
  985. }
  986. cache[BDV] = base;
  987. }
  988. assert(cache.count(def));
  989. return cache[def];
  990. }
  991. // For a set of live pointers (base and/or derived), identify the base
  992. // pointer of the object which they are derived from. This routine will
  993. // mutate the IR graph as needed to make the 'base' pointer live at the
  994. // definition site of 'derived'. This ensures that any use of 'derived' can
  995. // also use 'base'. This may involve the insertion of a number of
  996. // additional PHI nodes.
  997. //
  998. // preconditions: live is a set of pointer type Values
  999. //
  1000. // side effects: may insert PHI nodes into the existing CFG, will preserve
  1001. // CFG, will not remove or mutate any existing nodes
  1002. //
  1003. // post condition: PointerToBase contains one (derived, base) pair for every
  1004. // pointer in live. Note that derived can be equal to base if the original
  1005. // pointer was a base pointer.
  1006. static void
  1007. findBasePointers(const StatepointLiveSetTy &live,
  1008. DenseMap<Value *, Value *> &PointerToBase,
  1009. DominatorTree *DT, DefiningValueMapTy &DVCache) {
  1010. // For the naming of values inserted to be deterministic - which makes for
  1011. // much cleaner and more stable tests - we need to assign an order to the
  1012. // live values. DenseSets do not provide a deterministic order across runs.
  1013. SmallVector<Value *, 64> Temp;
  1014. Temp.insert(Temp.end(), live.begin(), live.end());
  1015. std::sort(Temp.begin(), Temp.end(), order_by_name);
  1016. for (Value *ptr : Temp) {
  1017. Value *base = findBasePointer(ptr, DVCache);
  1018. assert(base && "failed to find base pointer");
  1019. PointerToBase[ptr] = base;
  1020. assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||
  1021. DT->dominates(cast<Instruction>(base)->getParent(),
  1022. cast<Instruction>(ptr)->getParent())) &&
  1023. "The base we found better dominate the derived pointer");
  1024. // If you see this trip and like to live really dangerously, the code should
  1025. // be correct, just with idioms the verifier can't handle. You can try
  1026. // disabling the verifier at your own substantial risk.
  1027. assert(!isa<ConstantPointerNull>(base) &&
  1028. "the relocation code needs adjustment to handle the relocation of "
  1029. "a null pointer constant without causing false positives in the "
  1030. "safepoint ir verifier.");
  1031. }
  1032. }
  1033. /// Find the required based pointers (and adjust the live set) for the given
  1034. /// parse point.
  1035. static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache,
  1036. const CallSite &CS,
  1037. PartiallyConstructedSafepointRecord &result) {
  1038. DenseMap<Value *, Value *> PointerToBase;
  1039. findBasePointers(result.LiveSet, PointerToBase, &DT, DVCache);
  1040. if (PrintBasePointers) {
  1041. // Note: Need to print these in a stable order since this is checked in
  1042. // some tests.
  1043. errs() << "Base Pairs (w/o Relocation):\n";
  1044. SmallVector<Value *, 64> Temp;
  1045. Temp.reserve(PointerToBase.size());
  1046. for (auto Pair : PointerToBase) {
  1047. Temp.push_back(Pair.first);
  1048. }
  1049. std::sort(Temp.begin(), Temp.end(), order_by_name);
  1050. for (Value *Ptr : Temp) {
  1051. Value *Base = PointerToBase[Ptr];
  1052. errs() << " derived ";
  1053. Ptr->printAsOperand(errs(), false);
  1054. errs() << " base ";
  1055. Base->printAsOperand(errs(), false);
  1056. errs() << "\n";;
  1057. }
  1058. }
  1059. result.PointerToBase = PointerToBase;
  1060. }
  1061. /// Given an updated version of the dataflow liveness results, update the
  1062. /// liveset and base pointer maps for the call site CS.
  1063. static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
  1064. const CallSite &CS,
  1065. PartiallyConstructedSafepointRecord &result);
  1066. static void recomputeLiveInValues(
  1067. Function &F, DominatorTree &DT, ArrayRef<CallSite> toUpdate,
  1068. MutableArrayRef<struct PartiallyConstructedSafepointRecord> records) {
  1069. // TODO-PERF: reuse the original liveness, then simply run the dataflow
  1070. // again. The old values are still live and will help it stabilize quickly.
  1071. GCPtrLivenessData RevisedLivenessData;
  1072. computeLiveInValues(DT, F, RevisedLivenessData);
  1073. for (size_t i = 0; i < records.size(); i++) {
  1074. struct PartiallyConstructedSafepointRecord &info = records[i];
  1075. const CallSite &CS = toUpdate[i];
  1076. recomputeLiveInValues(RevisedLivenessData, CS, info);
  1077. }
  1078. }
  1079. // When inserting gc.relocate and gc.result calls, we need to ensure there are
  1080. // no uses of the original value / return value between the gc.statepoint and
  1081. // the gc.relocate / gc.result call. One case which can arise is a phi node
  1082. // starting one of the successor blocks. We also need to be able to insert the
  1083. // gc.relocates only on the path which goes through the statepoint. We might
  1084. // need to split an edge to make this possible.
  1085. static BasicBlock *
  1086. normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent,
  1087. DominatorTree &DT) {
  1088. BasicBlock *Ret = BB;
  1089. if (!BB->getUniquePredecessor())
  1090. Ret = SplitBlockPredecessors(BB, InvokeParent, "", &DT);
  1091. // Now that 'Ret' has unique predecessor we can safely remove all phi nodes
  1092. // from it
  1093. FoldSingleEntryPHINodes(Ret);
  1094. assert(!isa<PHINode>(Ret->begin()) &&
  1095. "All PHI nodes should have been removed!");
  1096. // At this point, we can safely insert a gc.relocate or gc.result as the first
  1097. // instruction in Ret if needed.
  1098. return Ret;
  1099. }
  1100. // Create new attribute set containing only attributes which can be transferred
  1101. // from original call to the safepoint.
  1102. static AttributeSet legalizeCallAttributes(AttributeSet AS) {
  1103. AttributeSet Ret;
  1104. for (unsigned Slot = 0; Slot < AS.getNumSlots(); Slot++) {
  1105. unsigned Index = AS.getSlotIndex(Slot);
  1106. if (Index == AttributeSet::ReturnIndex ||
  1107. Index == AttributeSet::FunctionIndex) {
  1108. for (Attribute Attr : make_range(AS.begin(Slot), AS.end(Slot))) {
  1109. // Do not allow certain attributes - just skip them
  1110. // Safepoint can not be read only or read none.
  1111. if (Attr.hasAttribute(Attribute::ReadNone) ||
  1112. Attr.hasAttribute(Attribute::ReadOnly))
  1113. continue;
  1114. // These attributes control the generation of the gc.statepoint call /
  1115. // invoke itself; and once the gc.statepoint is in place, they're of no
  1116. // use.
  1117. if (Attr.hasAttribute("statepoint-num-patch-bytes") ||
  1118. Attr.hasAttribute("statepoint-id"))
  1119. continue;
  1120. Ret = Ret.addAttributes(
  1121. AS.getContext(), Index,
  1122. AttributeSet::get(AS.getContext(), Index, AttrBuilder(Attr)));
  1123. }
  1124. }
  1125. // Just skip parameter attributes for now
  1126. }
  1127. return Ret;
  1128. }
  1129. /// Helper function to place all gc relocates necessary for the given
  1130. /// statepoint.
  1131. /// Inputs:
  1132. /// liveVariables - list of variables to be relocated.
  1133. /// liveStart - index of the first live variable.
  1134. /// basePtrs - base pointers.
  1135. /// statepointToken - statepoint instruction to which relocates should be
  1136. /// bound.
  1137. /// Builder - Llvm IR builder to be used to construct new calls.
  1138. static void CreateGCRelocates(ArrayRef<Value *> LiveVariables,
  1139. const int LiveStart,
  1140. ArrayRef<Value *> BasePtrs,
  1141. Instruction *StatepointToken,
  1142. IRBuilder<> Builder) {
  1143. if (LiveVariables.empty())
  1144. return;
  1145. auto FindIndex = [](ArrayRef<Value *> LiveVec, Value *Val) {
  1146. auto ValIt = std::find(LiveVec.begin(), LiveVec.end(), Val);
  1147. assert(ValIt != LiveVec.end() && "Val not found in LiveVec!");
  1148. size_t Index = std::distance(LiveVec.begin(), ValIt);
  1149. assert(Index < LiveVec.size() && "Bug in std::find?");
  1150. return Index;
  1151. };
  1152. Module *M = StatepointToken->getModule();
  1153. // All gc_relocate are generated as i8 addrspace(1)* (or a vector type whose
  1154. // element type is i8 addrspace(1)*). We originally generated unique
  1155. // declarations for each pointer type, but this proved problematic because
  1156. // the intrinsic mangling code is incomplete and fragile. Since we're moving
  1157. // towards a single unified pointer type anyways, we can just cast everything
  1158. // to an i8* of the right address space. A bitcast is added later to convert
  1159. // gc_relocate to the actual value's type.
  1160. auto getGCRelocateDecl = [&] (Type *Ty) {
  1161. assert(isHandledGCPointerType(Ty));
  1162. auto AS = Ty->getScalarType()->getPointerAddressSpace();
  1163. Type *NewTy = Type::getInt8PtrTy(M->getContext(), AS);
  1164. if (auto *VT = dyn_cast<VectorType>(Ty))
  1165. NewTy = VectorType::get(NewTy, VT->getNumElements());
  1166. return Intrinsic::getDeclaration(M, Intrinsic::experimental_gc_relocate,
  1167. {NewTy});
  1168. };
  1169. // Lazily populated map from input types to the canonicalized form mentioned
  1170. // in the comment above. This should probably be cached somewhere more
  1171. // broadly.
  1172. DenseMap<Type*, Value*> TypeToDeclMap;
  1173. for (unsigned i = 0; i < LiveVariables.size(); i++) {
  1174. // Generate the gc.relocate call and save the result
  1175. Value *BaseIdx =
  1176. Builder.getInt32(LiveStart + FindIndex(LiveVariables, BasePtrs[i]));
  1177. Value *LiveIdx = Builder.getInt32(LiveStart + i);
  1178. Type *Ty = LiveVariables[i]->getType();
  1179. if (!TypeToDeclMap.count(Ty))
  1180. TypeToDeclMap[Ty] = getGCRelocateDecl(Ty);
  1181. Value *GCRelocateDecl = TypeToDeclMap[Ty];
  1182. // only specify a debug name if we can give a useful one
  1183. CallInst *Reloc = Builder.CreateCall(
  1184. GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
  1185. suffixed_name_or(LiveVariables[i], ".relocated", ""));
  1186. // Trick CodeGen into thinking there are lots of free registers at this
  1187. // fake call.
  1188. Reloc->setCallingConv(CallingConv::Cold);
  1189. }
  1190. }
  1191. namespace {
  1192. /// This struct is used to defer RAUWs and `eraseFromParent` s. Using this
  1193. /// avoids having to worry about keeping around dangling pointers to Values.
  1194. class DeferredReplacement {
  1195. AssertingVH<Instruction> Old;
  1196. AssertingVH<Instruction> New;
  1197. public:
  1198. explicit DeferredReplacement(Instruction *Old, Instruction *New) :
  1199. Old(Old), New(New) {
  1200. assert(Old != New && "Not allowed!");
  1201. }
  1202. /// Does the task represented by this instance.
  1203. void doReplacement() {
  1204. Instruction *OldI = Old;
  1205. Instruction *NewI = New;
  1206. assert(OldI != NewI && "Disallowed at construction?!");
  1207. Old = nullptr;
  1208. New = nullptr;
  1209. if (NewI)
  1210. OldI->replaceAllUsesWith(NewI);
  1211. OldI->eraseFromParent();
  1212. }
  1213. };
  1214. }
  1215. static void
  1216. makeStatepointExplicitImpl(const CallSite CS, /* to replace */
  1217. const SmallVectorImpl<Value *> &BasePtrs,
  1218. const SmallVectorImpl<Value *> &LiveVariables,
  1219. PartiallyConstructedSafepointRecord &Result,
  1220. std::vector<DeferredReplacement> &Replacements) {
  1221. assert(BasePtrs.size() == LiveVariables.size());
  1222. assert((UseDeoptBundles || isStatepoint(CS)) &&
  1223. "This method expects to be rewriting a statepoint");
  1224. // Then go ahead and use the builder do actually do the inserts. We insert
  1225. // immediately before the previous instruction under the assumption that all
  1226. // arguments will be available here. We can't insert afterwards since we may
  1227. // be replacing a terminator.
  1228. Instruction *InsertBefore = CS.getInstruction();
  1229. IRBuilder<> Builder(InsertBefore);
  1230. ArrayRef<Value *> GCArgs(LiveVariables);
  1231. uint64_t StatepointID = 0xABCDEF00;
  1232. uint32_t NumPatchBytes = 0;
  1233. uint32_t Flags = uint32_t(StatepointFlags::None);
  1234. ArrayRef<Use> CallArgs;
  1235. ArrayRef<Use> DeoptArgs;
  1236. ArrayRef<Use> TransitionArgs;
  1237. Value *CallTarget = nullptr;
  1238. if (UseDeoptBundles) {
  1239. CallArgs = {CS.arg_begin(), CS.arg_end()};
  1240. DeoptArgs = GetDeoptBundleOperands(CS);
  1241. // TODO: we don't fill in TransitionArgs or Flags in this branch, but we
  1242. // could have an operand bundle for that too.
  1243. AttributeSet OriginalAttrs = CS.getAttributes();
  1244. Attribute AttrID = OriginalAttrs.getAttribute(AttributeSet::FunctionIndex,
  1245. "statepoint-id");
  1246. if (AttrID.isStringAttribute())
  1247. AttrID.getValueAsString().getAsInteger(10, StatepointID);
  1248. Attribute AttrNumPatchBytes = OriginalAttrs.getAttribute(
  1249. AttributeSet::FunctionIndex, "statepoint-num-patch-bytes");
  1250. if (AttrNumPatchBytes.isStringAttribute())
  1251. AttrNumPatchBytes.getValueAsString().getAsInteger(10, NumPatchBytes);
  1252. CallTarget = CS.getCalledValue();
  1253. } else {
  1254. // This branch will be gone soon, and we will soon only support the
  1255. // UseDeoptBundles == true configuration.
  1256. Statepoint OldSP(CS);
  1257. StatepointID = OldSP.getID();
  1258. NumPatchBytes = OldSP.getNumPatchBytes();
  1259. Flags = OldSP.getFlags();
  1260. CallArgs = {OldSP.arg_begin(), OldSP.arg_end()};
  1261. DeoptArgs = {OldSP.vm_state_begin(), OldSP.vm_state_end()};
  1262. TransitionArgs = {OldSP.gc_transition_args_begin(),
  1263. OldSP.gc_transition_args_end()};
  1264. CallTarget = OldSP.getCalledValue();
  1265. }
  1266. // Create the statepoint given all the arguments
  1267. Instruction *Token = nullptr;
  1268. AttributeSet ReturnAttrs;
  1269. if (CS.isCall()) {
  1270. CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
  1271. CallInst *Call = Builder.CreateGCStatepointCall(
  1272. StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
  1273. TransitionArgs, DeoptArgs, GCArgs, "safepoint_token");
  1274. Call->setTailCall(ToReplace->isTailCall());
  1275. Call->setCallingConv(ToReplace->getCallingConv());
  1276. // Currently we will fail on parameter attributes and on certain
  1277. // function attributes.
  1278. AttributeSet NewAttrs = legalizeCallAttributes(ToReplace->getAttributes());
  1279. // In case if we can handle this set of attributes - set up function attrs
  1280. // directly on statepoint and return attrs later for gc_result intrinsic.
  1281. Call->setAttributes(NewAttrs.getFnAttributes());
  1282. ReturnAttrs = NewAttrs.getRetAttributes();
  1283. Token = Call;
  1284. // Put the following gc_result and gc_relocate calls immediately after the
  1285. // the old call (which we're about to delete)
  1286. assert(ToReplace->getNextNode() && "Not a terminator, must have next!");
  1287. Builder.SetInsertPoint(ToReplace->getNextNode());
  1288. Builder.SetCurrentDebugLocation(ToReplace->getNextNode()->getDebugLoc());
  1289. } else {
  1290. InvokeInst *ToReplace = cast<InvokeInst>(CS.getInstruction());
  1291. // Insert the new invoke into the old block. We'll remove the old one in a
  1292. // moment at which point this will become the new terminator for the
  1293. // original block.
  1294. InvokeInst *Invoke = Builder.CreateGCStatepointInvoke(
  1295. StatepointID, NumPatchBytes, CallTarget, ToReplace->getNormalDest(),
  1296. ToReplace->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs,
  1297. GCArgs, "statepoint_token");
  1298. Invoke->setCallingConv(ToReplace->getCallingConv());
  1299. // Currently we will fail on parameter attributes and on certain
  1300. // function attributes.
  1301. AttributeSet NewAttrs = legalizeCallAttributes(ToReplace->getAttributes());
  1302. // In case if we can handle this set of attributes - set up function attrs
  1303. // directly on statepoint and return attrs later for gc_result intrinsic.
  1304. Invoke->setAttributes(NewAttrs.getFnAttributes());
  1305. ReturnAttrs = NewAttrs.getRetAttributes();
  1306. Token = Invoke;
  1307. // Generate gc relocates in exceptional path
  1308. BasicBlock *UnwindBlock = ToReplace->getUnwindDest();
  1309. assert(!isa<PHINode>(UnwindBlock->begin()) &&
  1310. UnwindBlock->getUniquePredecessor() &&
  1311. "can't safely insert in this block!");
  1312. Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
  1313. Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
  1314. // Attach exceptional gc relocates to the landingpad.
  1315. Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
  1316. Result.UnwindToken = ExceptionalToken;
  1317. const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx();
  1318. CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, ExceptionalToken,
  1319. Builder);
  1320. // Generate gc relocates and returns for normal block
  1321. BasicBlock *NormalDest = ToReplace->getNormalDest();
  1322. assert(!isa<PHINode>(NormalDest->begin()) &&
  1323. NormalDest->getUniquePredecessor() &&
  1324. "can't safely insert in this block!");
  1325. Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt());
  1326. // gc relocates will be generated later as if it were regular call
  1327. // statepoint
  1328. }
  1329. assert(Token && "Should be set in one of the above branches!");
  1330. if (UseDeoptBundles) {
  1331. Token->setName("statepoint_token");
  1332. if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
  1333. StringRef Name =
  1334. CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "";
  1335. CallInst *GCResult = Builder.CreateGCResult(Token, CS.getType(), Name);
  1336. GCResult->setAttributes(CS.getAttributes().getRetAttributes());
  1337. // We cannot RAUW or delete CS.getInstruction() because it could be in the
  1338. // live set of some other safepoint, in which case that safepoint's
  1339. // PartiallyConstructedSafepointRecord will hold a raw pointer to this
  1340. // llvm::Instruction. Instead, we defer the replacement and deletion to
  1341. // after the live sets have been made explicit in the IR, and we no longer
  1342. // have raw pointers to worry about.
  1343. Replacements.emplace_back(CS.getInstruction(), GCResult);
  1344. } else {
  1345. Replacements.emplace_back(CS.getInstruction(), nullptr);
  1346. }
  1347. } else {
  1348. assert(!CS.getInstruction()->hasNUsesOrMore(2) &&
  1349. "only valid use before rewrite is gc.result");
  1350. assert(!CS.getInstruction()->hasOneUse() ||
  1351. isGCResult(cast<Instruction>(*CS.getInstruction()->user_begin())));
  1352. // Take the name of the original statepoint token if there was one.
  1353. Token->takeName(CS.getInstruction());
  1354. // Update the gc.result of the original statepoint (if any) to use the newly
  1355. // inserted statepoint. This is safe to do here since the token can't be
  1356. // considered a live reference.
  1357. CS.getInstruction()->replaceAllUsesWith(Token);
  1358. CS.getInstruction()->eraseFromParent();
  1359. }
  1360. Result.StatepointToken = Token;
  1361. // Second, create a gc.relocate for every live variable
  1362. const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx();
  1363. CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder);
  1364. }
  1365. namespace {
  1366. struct NameOrdering {
  1367. Value *Base;
  1368. Value *Derived;
  1369. bool operator()(NameOrdering const &a, NameOrdering const &b) {
  1370. return -1 == a.Derived->getName().compare(b.Derived->getName());
  1371. }
  1372. };
  1373. }
  1374. static void StabilizeOrder(SmallVectorImpl<Value *> &BaseVec,
  1375. SmallVectorImpl<Value *> &LiveVec) {
  1376. assert(BaseVec.size() == LiveVec.size());
  1377. SmallVector<NameOrdering, 64> Temp;
  1378. for (size_t i = 0; i < BaseVec.size(); i++) {
  1379. NameOrdering v;
  1380. v.Base = BaseVec[i];
  1381. v.Derived = LiveVec[i];
  1382. Temp.push_back(v);
  1383. }
  1384. std::sort(Temp.begin(), Temp.end(), NameOrdering());
  1385. for (size_t i = 0; i < BaseVec.size(); i++) {
  1386. BaseVec[i] = Temp[i].Base;
  1387. LiveVec[i] = Temp[i].Derived;
  1388. }
  1389. }
  1390. // Replace an existing gc.statepoint with a new one and a set of gc.relocates
  1391. // which make the relocations happening at this safepoint explicit.
  1392. //
  1393. // WARNING: Does not do any fixup to adjust users of the original live
  1394. // values. That's the callers responsibility.
  1395. static void
  1396. makeStatepointExplicit(DominatorTree &DT, const CallSite &CS,
  1397. PartiallyConstructedSafepointRecord &Result,
  1398. std::vector<DeferredReplacement> &Replacements) {
  1399. const auto &LiveSet = Result.LiveSet;
  1400. const auto &PointerToBase = Result.PointerToBase;
  1401. // Convert to vector for efficient cross referencing.
  1402. SmallVector<Value *, 64> BaseVec, LiveVec;
  1403. LiveVec.reserve(LiveSet.size());
  1404. BaseVec.reserve(LiveSet.size());
  1405. for (Value *L : LiveSet) {
  1406. LiveVec.push_back(L);
  1407. assert(PointerToBase.count(L));
  1408. Value *Base = PointerToBase.find(L)->second;
  1409. BaseVec.push_back(Base);
  1410. }
  1411. assert(LiveVec.size() == BaseVec.size());
  1412. // To make the output IR slightly more stable (for use in diffs), ensure a
  1413. // fixed order of the values in the safepoint (by sorting the value name).
  1414. // The order is otherwise meaningless.
  1415. StabilizeOrder(BaseVec, LiveVec);
  1416. // Do the actual rewriting and delete the old statepoint
  1417. makeStatepointExplicitImpl(CS, BaseVec, LiveVec, Result, Replacements);
  1418. }
  1419. // Helper function for the relocationViaAlloca.
  1420. //
  1421. // It receives iterator to the statepoint gc relocates and emits a store to the
  1422. // assigned location (via allocaMap) for the each one of them. It adds the
  1423. // visited values into the visitedLiveValues set, which we will later use them
  1424. // for sanity checking.
  1425. static void
  1426. insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs,
  1427. DenseMap<Value *, Value *> &AllocaMap,
  1428. DenseSet<Value *> &VisitedLiveValues) {
  1429. for (User *U : GCRelocs) {
  1430. GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U);
  1431. if (!Relocate)
  1432. continue;
  1433. Value *OriginalValue = const_cast<Value *>(Relocate->getDerivedPtr());
  1434. assert(AllocaMap.count(OriginalValue));
  1435. Value *Alloca = AllocaMap[OriginalValue];
  1436. // Emit store into the related alloca
  1437. // All gc_relocates are i8 addrspace(1)* typed, and it must be bitcasted to
  1438. // the correct type according to alloca.
  1439. assert(Relocate->getNextNode() &&
  1440. "Should always have one since it's not a terminator");
  1441. IRBuilder<> Builder(Relocate->getNextNode());
  1442. Value *CastedRelocatedValue =
  1443. Builder.CreateBitCast(Relocate,
  1444. cast<AllocaInst>(Alloca)->getAllocatedType(),
  1445. suffixed_name_or(Relocate, ".casted", ""));
  1446. StoreInst *Store = new StoreInst(CastedRelocatedValue, Alloca);
  1447. Store->insertAfter(cast<Instruction>(CastedRelocatedValue));
  1448. #ifndef NDEBUG
  1449. VisitedLiveValues.insert(OriginalValue);
  1450. #endif
  1451. }
  1452. }
  1453. // Helper function for the "relocationViaAlloca". Similar to the
  1454. // "insertRelocationStores" but works for rematerialized values.
  1455. static void
  1456. insertRematerializationStores(
  1457. RematerializedValueMapTy RematerializedValues,
  1458. DenseMap<Value *, Value *> &AllocaMap,
  1459. DenseSet<Value *> &VisitedLiveValues) {
  1460. for (auto RematerializedValuePair: RematerializedValues) {
  1461. Instruction *RematerializedValue = RematerializedValuePair.first;
  1462. Value *OriginalValue = RematerializedValuePair.second;
  1463. assert(AllocaMap.count(OriginalValue) &&
  1464. "Can not find alloca for rematerialized value");
  1465. Value *Alloca = AllocaMap[OriginalValue];
  1466. StoreInst *Store = new StoreInst(RematerializedValue, Alloca);
  1467. Store->insertAfter(RematerializedValue);
  1468. #ifndef NDEBUG
  1469. VisitedLiveValues.insert(OriginalValue);
  1470. #endif
  1471. }
  1472. }
  1473. /// Do all the relocation update via allocas and mem2reg
  1474. static void relocationViaAlloca(
  1475. Function &F, DominatorTree &DT, ArrayRef<Value *> Live,
  1476. ArrayRef<PartiallyConstructedSafepointRecord> Records) {
  1477. #ifndef NDEBUG
  1478. // record initial number of (static) allocas; we'll check we have the same
  1479. // number when we get done.
  1480. int InitialAllocaNum = 0;
  1481. for (auto I = F.getEntryBlock().begin(), E = F.getEntryBlock().end(); I != E;
  1482. I++)
  1483. if (isa<AllocaInst>(*I))
  1484. InitialAllocaNum++;
  1485. #endif
  1486. // TODO-PERF: change data structures, reserve
  1487. DenseMap<Value *, Value *> AllocaMap;
  1488. SmallVector<AllocaInst *, 200> PromotableAllocas;
  1489. // Used later to chack that we have enough allocas to store all values
  1490. std::size_t NumRematerializedValues = 0;
  1491. PromotableAllocas.reserve(Live.size());
  1492. // Emit alloca for "LiveValue" and record it in "allocaMap" and
  1493. // "PromotableAllocas"
  1494. auto emitAllocaFor = [&](Value *LiveValue) {
  1495. AllocaInst *Alloca = new AllocaInst(LiveValue->getType(), "",
  1496. F.getEntryBlock().getFirstNonPHI());
  1497. AllocaMap[LiveValue] = Alloca;
  1498. PromotableAllocas.push_back(Alloca);
  1499. };
  1500. // Emit alloca for each live gc pointer
  1501. for (Value *V : Live)
  1502. emitAllocaFor(V);
  1503. // Emit allocas for rematerialized values
  1504. for (const auto &Info : Records)
  1505. for (auto RematerializedValuePair : Info.RematerializedValues) {
  1506. Value *OriginalValue = RematerializedValuePair.second;
  1507. if (AllocaMap.count(OriginalValue) != 0)
  1508. continue;
  1509. emitAllocaFor(OriginalValue);
  1510. ++NumRematerializedValues;
  1511. }
  1512. // The next two loops are part of the same conceptual operation. We need to
  1513. // insert a store to the alloca after the original def and at each
  1514. // redefinition. We need to insert a load before each use. These are split
  1515. // into distinct loops for performance reasons.
  1516. // Update gc pointer after each statepoint: either store a relocated value or
  1517. // null (if no relocated value was found for this gc pointer and it is not a
  1518. // gc_result). This must happen before we update the statepoint with load of
  1519. // alloca otherwise we lose the link between statepoint and old def.
  1520. for (const auto &Info : Records) {
  1521. Value *Statepoint = Info.StatepointToken;
  1522. // This will be used for consistency check
  1523. DenseSet<Value *> VisitedLiveValues;
  1524. // Insert stores for normal statepoint gc relocates
  1525. insertRelocationStores(Statepoint->users(), AllocaMap, VisitedLiveValues);
  1526. // In case if it was invoke statepoint
  1527. // we will insert stores for exceptional path gc relocates.
  1528. if (isa<InvokeInst>(Statepoint)) {
  1529. insertRelocationStores(Info.UnwindToken->users(), AllocaMap,
  1530. VisitedLiveValues);
  1531. }
  1532. // Do similar thing with rematerialized values
  1533. insertRematerializationStores(Info.RematerializedValues, AllocaMap,
  1534. VisitedLiveValues);
  1535. if (ClobberNonLive) {
  1536. // As a debugging aid, pretend that an unrelocated pointer becomes null at
  1537. // the gc.statepoint. This will turn some subtle GC problems into
  1538. // slightly easier to debug SEGVs. Note that on large IR files with
  1539. // lots of gc.statepoints this is extremely costly both memory and time
  1540. // wise.
  1541. SmallVector<AllocaInst *, 64> ToClobber;
  1542. for (auto Pair : AllocaMap) {
  1543. Value *Def = Pair.first;
  1544. AllocaInst *Alloca = cast<AllocaInst>(Pair.second);
  1545. // This value was relocated
  1546. if (VisitedLiveValues.count(Def)) {
  1547. continue;
  1548. }
  1549. ToClobber.push_back(Alloca);
  1550. }
  1551. auto InsertClobbersAt = [&](Instruction *IP) {
  1552. for (auto *AI : ToClobber) {
  1553. auto PT = cast<PointerType>(AI->getAllocatedType());
  1554. Constant *CPN = ConstantPointerNull::get(PT);
  1555. StoreInst *Store = new StoreInst(CPN, AI);
  1556. Store->insertBefore(IP);
  1557. }
  1558. };
  1559. // Insert the clobbering stores. These may get intermixed with the
  1560. // gc.results and gc.relocates, but that's fine.
  1561. if (auto II = dyn_cast<InvokeInst>(Statepoint)) {
  1562. InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt());
  1563. InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt());
  1564. } else {
  1565. InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode());
  1566. }
  1567. }
  1568. }
  1569. // Update use with load allocas and add store for gc_relocated.
  1570. for (auto Pair : AllocaMap) {
  1571. Value *Def = Pair.first;
  1572. Value *Alloca = Pair.second;
  1573. // We pre-record the uses of allocas so that we dont have to worry about
  1574. // later update that changes the user information..
  1575. SmallVector<Instruction *, 20> Uses;
  1576. // PERF: trade a linear scan for repeated reallocation
  1577. Uses.reserve(std::distance(Def->user_begin(), Def->user_end()));
  1578. for (User *U : Def->users()) {
  1579. if (!isa<ConstantExpr>(U)) {
  1580. // If the def has a ConstantExpr use, then the def is either a
  1581. // ConstantExpr use itself or null. In either case
  1582. // (recursively in the first, directly in the second), the oop
  1583. // it is ultimately dependent on is null and this particular
  1584. // use does not need to be fixed up.
  1585. Uses.push_back(cast<Instruction>(U));
  1586. }
  1587. }
  1588. std::sort(Uses.begin(), Uses.end());
  1589. auto Last = std::unique(Uses.begin(), Uses.end());
  1590. Uses.erase(Last, Uses.end());
  1591. for (Instruction *Use : Uses) {
  1592. if (isa<PHINode>(Use)) {
  1593. PHINode *Phi = cast<PHINode>(Use);
  1594. for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {
  1595. if (Def == Phi->getIncomingValue(i)) {
  1596. LoadInst *Load = new LoadInst(
  1597. Alloca, "", Phi->getIncomingBlock(i)->getTerminator());
  1598. Phi->setIncomingValue(i, Load);
  1599. }
  1600. }
  1601. } else {
  1602. LoadInst *Load = new LoadInst(Alloca, "", Use);
  1603. Use->replaceUsesOfWith(Def, Load);
  1604. }
  1605. }
  1606. // Emit store for the initial gc value. Store must be inserted after load,
  1607. // otherwise store will be in alloca's use list and an extra load will be
  1608. // inserted before it.
  1609. StoreInst *Store = new StoreInst(Def, Alloca);
  1610. if (Instruction *Inst = dyn_cast<Instruction>(Def)) {
  1611. if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {
  1612. // InvokeInst is a TerminatorInst so the store need to be inserted
  1613. // into its normal destination block.
  1614. BasicBlock *NormalDest = Invoke->getNormalDest();
  1615. Store->insertBefore(NormalDest->getFirstNonPHI());
  1616. } else {
  1617. assert(!Inst->isTerminator() &&
  1618. "The only TerminatorInst that can produce a value is "
  1619. "InvokeInst which is handled above.");
  1620. Store->insertAfter(Inst);
  1621. }
  1622. } else {
  1623. assert(isa<Argument>(Def));
  1624. Store->insertAfter(cast<Instruction>(Alloca));
  1625. }
  1626. }
  1627. assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&
  1628. "we must have the same allocas with lives");
  1629. if (!PromotableAllocas.empty()) {
  1630. // Apply mem2reg to promote alloca to SSA
  1631. PromoteMemToReg(PromotableAllocas, DT);
  1632. }
  1633. #ifndef NDEBUG
  1634. for (auto &I : F.getEntryBlock())
  1635. if (isa<AllocaInst>(I))
  1636. InitialAllocaNum--;
  1637. assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas");
  1638. #endif
  1639. }
  1640. /// Implement a unique function which doesn't require we sort the input
  1641. /// vector. Doing so has the effect of changing the output of a couple of
  1642. /// tests in ways which make them less useful in testing fused safepoints.
  1643. template <typename T> static void unique_unsorted(SmallVectorImpl<T> &Vec) {
  1644. SmallSet<T, 8> Seen;
  1645. Vec.erase(std::remove_if(Vec.begin(), Vec.end(), [&](const T &V) {
  1646. return !Seen.insert(V).second;
  1647. }), Vec.end());
  1648. }
  1649. /// Insert holders so that each Value is obviously live through the entire
  1650. /// lifetime of the call.
  1651. static void insertUseHolderAfter(CallSite &CS, const ArrayRef<Value *> Values,
  1652. SmallVectorImpl<CallInst *> &Holders) {
  1653. if (Values.empty())
  1654. // No values to hold live, might as well not insert the empty holder
  1655. return;
  1656. Module *M = CS.getInstruction()->getModule();
  1657. // Use a dummy vararg function to actually hold the values live
  1658. Function *Func = cast<Function>(M->getOrInsertFunction(
  1659. "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true)));
  1660. if (CS.isCall()) {
  1661. // For call safepoints insert dummy calls right after safepoint
  1662. Holders.push_back(CallInst::Create(Func, Values, "",
  1663. &*++CS.getInstruction()->getIterator()));
  1664. return;
  1665. }
  1666. // For invoke safepooints insert dummy calls both in normal and
  1667. // exceptional destination blocks
  1668. auto *II = cast<InvokeInst>(CS.getInstruction());
  1669. Holders.push_back(CallInst::Create(
  1670. Func, Values, "", &*II->getNormalDest()->getFirstInsertionPt()));
  1671. Holders.push_back(CallInst::Create(
  1672. Func, Values, "", &*II->getUnwindDest()->getFirstInsertionPt()));
  1673. }
  1674. static void findLiveReferences(
  1675. Function &F, DominatorTree &DT, ArrayRef<CallSite> toUpdate,
  1676. MutableArrayRef<struct PartiallyConstructedSafepointRecord> records) {
  1677. GCPtrLivenessData OriginalLivenessData;
  1678. computeLiveInValues(DT, F, OriginalLivenessData);
  1679. for (size_t i = 0; i < records.size(); i++) {
  1680. struct PartiallyConstructedSafepointRecord &info = records[i];
  1681. const CallSite &CS = toUpdate[i];
  1682. analyzeParsePointLiveness(DT, OriginalLivenessData, CS, info);
  1683. }
  1684. }
  1685. /// Remove any vector of pointers from the live set by scalarizing them over the
  1686. /// statepoint instruction. Adds the scalarized pieces to the live set. It
  1687. /// would be preferable to include the vector in the statepoint itself, but
  1688. /// the lowering code currently does not handle that. Extending it would be
  1689. /// slightly non-trivial since it requires a format change. Given how rare
  1690. /// such cases are (for the moment?) scalarizing is an acceptable compromise.
  1691. static void splitVectorValues(Instruction *StatepointInst,
  1692. StatepointLiveSetTy &LiveSet,
  1693. DenseMap<Value *, Value *>& PointerToBase,
  1694. DominatorTree &DT) {
  1695. SmallVector<Value *, 16> ToSplit;
  1696. for (Value *V : LiveSet)
  1697. if (isa<VectorType>(V->getType()))
  1698. ToSplit.push_back(V);
  1699. if (ToSplit.empty())
  1700. return;
  1701. DenseMap<Value *, SmallVector<Value *, 16>> ElementMapping;
  1702. Function &F = *(StatepointInst->getParent()->getParent());
  1703. DenseMap<Value *, AllocaInst *> AllocaMap;
  1704. // First is normal return, second is exceptional return (invoke only)
  1705. DenseMap<Value *, std::pair<Value *, Value *>> Replacements;
  1706. for (Value *V : ToSplit) {
  1707. AllocaInst *Alloca =
  1708. new AllocaInst(V->getType(), "", F.getEntryBlock().getFirstNonPHI());
  1709. AllocaMap[V] = Alloca;
  1710. VectorType *VT = cast<VectorType>(V->getType());
  1711. IRBuilder<> Builder(StatepointInst);
  1712. SmallVector<Value *, 16> Elements;
  1713. for (unsigned i = 0; i < VT->getNumElements(); i++)
  1714. Elements.push_back(Builder.CreateExtractElement(V, Builder.getInt32(i)));
  1715. ElementMapping[V] = Elements;
  1716. auto InsertVectorReform = [&](Instruction *IP) {
  1717. Builder.SetInsertPoint(IP);
  1718. Builder.SetCurrentDebugLocation(IP->getDebugLoc());
  1719. Value *ResultVec = UndefValue::get(VT);
  1720. for (unsigned i = 0; i < VT->getNumElements(); i++)
  1721. ResultVec = Builder.CreateInsertElement(ResultVec, Elements[i],
  1722. Builder.getInt32(i));
  1723. return ResultVec;
  1724. };
  1725. if (isa<CallInst>(StatepointInst)) {
  1726. BasicBlock::iterator Next(StatepointInst);
  1727. Next++;
  1728. Instruction *IP = &*(Next);
  1729. Replacements[V].first = InsertVectorReform(IP);
  1730. Replacements[V].second = nullptr;
  1731. } else {
  1732. InvokeInst *Invoke = cast<InvokeInst>(StatepointInst);
  1733. // We've already normalized - check that we don't have shared destination
  1734. // blocks
  1735. BasicBlock *NormalDest = Invoke->getNormalDest();
  1736. assert(!isa<PHINode>(NormalDest->begin()));
  1737. BasicBlock *UnwindDest = Invoke->getUnwindDest();
  1738. assert(!isa<PHINode>(UnwindDest->begin()));
  1739. // Insert insert element sequences in both successors
  1740. Instruction *IP = &*(NormalDest->getFirstInsertionPt());
  1741. Replacements[V].first = InsertVectorReform(IP);
  1742. IP = &*(UnwindDest->getFirstInsertionPt());
  1743. Replacements[V].second = InsertVectorReform(IP);
  1744. }
  1745. }
  1746. for (Value *V : ToSplit) {
  1747. AllocaInst *Alloca = AllocaMap[V];
  1748. // Capture all users before we start mutating use lists
  1749. SmallVector<Instruction *, 16> Users;
  1750. for (User *U : V->users())
  1751. Users.push_back(cast<Instruction>(U));
  1752. for (Instruction *I : Users) {
  1753. if (auto Phi = dyn_cast<PHINode>(I)) {
  1754. for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++)
  1755. if (V == Phi->getIncomingValue(i)) {
  1756. LoadInst *Load = new LoadInst(
  1757. Alloca, "", Phi->getIncomingBlock(i)->getTerminator());
  1758. Phi->setIncomingValue(i, Load);
  1759. }
  1760. } else {
  1761. LoadInst *Load = new LoadInst(Alloca, "", I);
  1762. I->replaceUsesOfWith(V, Load);
  1763. }
  1764. }
  1765. // Store the original value and the replacement value into the alloca
  1766. StoreInst *Store = new StoreInst(V, Alloca);
  1767. if (auto I = dyn_cast<Instruction>(V))
  1768. Store->insertAfter(I);
  1769. else
  1770. Store->insertAfter(Alloca);
  1771. // Normal return for invoke, or call return
  1772. Instruction *Replacement = cast<Instruction>(Replacements[V].first);
  1773. (new StoreInst(Replacement, Alloca))->insertAfter(Replacement);
  1774. // Unwind return for invoke only
  1775. Replacement = cast_or_null<Instruction>(Replacements[V].second);
  1776. if (Replacement)
  1777. (new StoreInst(Replacement, Alloca))->insertAfter(Replacement);
  1778. }
  1779. // apply mem2reg to promote alloca to SSA
  1780. SmallVector<AllocaInst *, 16> Allocas;
  1781. for (Value *V : ToSplit)
  1782. Allocas.push_back(AllocaMap[V]);
  1783. PromoteMemToReg(Allocas, DT);
  1784. // Update our tracking of live pointers and base mappings to account for the
  1785. // changes we just made.
  1786. for (Value *V : ToSplit) {
  1787. auto &Elements = ElementMapping[V];
  1788. LiveSet.erase(V);
  1789. LiveSet.insert(Elements.begin(), Elements.end());
  1790. // We need to update the base mapping as well.
  1791. assert(PointerToBase.count(V));
  1792. Value *OldBase = PointerToBase[V];
  1793. auto &BaseElements = ElementMapping[OldBase];
  1794. PointerToBase.erase(V);
  1795. assert(Elements.size() == BaseElements.size());
  1796. for (unsigned i = 0; i < Elements.size(); i++) {
  1797. Value *Elem = Elements[i];
  1798. PointerToBase[Elem] = BaseElements[i];
  1799. }
  1800. }
  1801. }
  1802. // Helper function for the "rematerializeLiveValues". It walks use chain
  1803. // starting from the "CurrentValue" until it meets "BaseValue". Only "simple"
  1804. // values are visited (currently it is GEP's and casts). Returns true if it
  1805. // successfully reached "BaseValue" and false otherwise.
  1806. // Fills "ChainToBase" array with all visited values. "BaseValue" is not
  1807. // recorded.
  1808. static bool findRematerializableChainToBasePointer(
  1809. SmallVectorImpl<Instruction*> &ChainToBase,
  1810. Value *CurrentValue, Value *BaseValue) {
  1811. // We have found a base value
  1812. if (CurrentValue == BaseValue) {
  1813. return true;
  1814. }
  1815. if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {
  1816. ChainToBase.push_back(GEP);
  1817. return findRematerializableChainToBasePointer(ChainToBase,
  1818. GEP->getPointerOperand(),
  1819. BaseValue);
  1820. }
  1821. if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
  1822. if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
  1823. return false;
  1824. ChainToBase.push_back(CI);
  1825. return findRematerializableChainToBasePointer(ChainToBase,
  1826. CI->getOperand(0), BaseValue);
  1827. }
  1828. // Not supported instruction in the chain
  1829. return false;
  1830. }
  1831. // Helper function for the "rematerializeLiveValues". Compute cost of the use
  1832. // chain we are going to rematerialize.
  1833. static unsigned
  1834. chainToBasePointerCost(SmallVectorImpl<Instruction*> &Chain,
  1835. TargetTransformInfo &TTI) {
  1836. unsigned Cost = 0;
  1837. for (Instruction *Instr : Chain) {
  1838. if (CastInst *CI = dyn_cast<CastInst>(Instr)) {
  1839. assert(CI->isNoopCast(CI->getModule()->getDataLayout()) &&
  1840. "non noop cast is found during rematerialization");
  1841. Type *SrcTy = CI->getOperand(0)->getType();
  1842. Cost += TTI.getCastInstrCost(CI->getOpcode(), CI->getType(), SrcTy);
  1843. } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) {
  1844. // Cost of the address calculation
  1845. Type *ValTy = GEP->getSourceElementType();
  1846. Cost += TTI.getAddressComputationCost(ValTy);
  1847. // And cost of the GEP itself
  1848. // TODO: Use TTI->getGEPCost here (it exists, but appears to be not
  1849. // allowed for the external usage)
  1850. if (!GEP->hasAllConstantIndices())
  1851. Cost += 2;
  1852. } else {
  1853. llvm_unreachable("unsupported instruciton type during rematerialization");
  1854. }
  1855. }
  1856. return Cost;
  1857. }
  1858. // From the statepoint live set pick values that are cheaper to recompute then
  1859. // to relocate. Remove this values from the live set, rematerialize them after
  1860. // statepoint and record them in "Info" structure. Note that similar to
  1861. // relocated values we don't do any user adjustments here.
  1862. static void rematerializeLiveValues(CallSite CS,
  1863. PartiallyConstructedSafepointRecord &Info,
  1864. TargetTransformInfo &TTI) {
  1865. const unsigned int ChainLengthThreshold = 10;
  1866. // Record values we are going to delete from this statepoint live set.
  1867. // We can not di this in following loop due to iterator invalidation.
  1868. SmallVector<Value *, 32> LiveValuesToBeDeleted;
  1869. for (Value *LiveValue: Info.LiveSet) {
  1870. // For each live pointer find it's defining chain
  1871. SmallVector<Instruction *, 3> ChainToBase;
  1872. assert(Info.PointerToBase.count(LiveValue));
  1873. bool FoundChain =
  1874. findRematerializableChainToBasePointer(ChainToBase,
  1875. LiveValue,
  1876. Info.PointerToBase[LiveValue]);
  1877. // Nothing to do, or chain is too long
  1878. if (!FoundChain ||
  1879. ChainToBase.size() == 0 ||
  1880. ChainToBase.size() > ChainLengthThreshold)
  1881. continue;
  1882. // Compute cost of this chain
  1883. unsigned Cost = chainToBasePointerCost(ChainToBase, TTI);
  1884. // TODO: We can also account for cases when we will be able to remove some
  1885. // of the rematerialized values by later optimization passes. I.e if
  1886. // we rematerialized several intersecting chains. Or if original values
  1887. // don't have any uses besides this statepoint.
  1888. // For invokes we need to rematerialize each chain twice - for normal and
  1889. // for unwind basic blocks. Model this by multiplying cost by two.
  1890. if (CS.isInvoke()) {
  1891. Cost *= 2;
  1892. }
  1893. // If it's too expensive - skip it
  1894. if (Cost >= RematerializationThreshold)
  1895. continue;
  1896. // Remove value from the live set
  1897. LiveValuesToBeDeleted.push_back(LiveValue);
  1898. // Clone instructions and record them inside "Info" structure
  1899. // Walk backwards to visit top-most instructions first
  1900. std::reverse(ChainToBase.begin(), ChainToBase.end());
  1901. // Utility function which clones all instructions from "ChainToBase"
  1902. // and inserts them before "InsertBefore". Returns rematerialized value
  1903. // which should be used after statepoint.
  1904. auto rematerializeChain = [&ChainToBase](Instruction *InsertBefore) {
  1905. Instruction *LastClonedValue = nullptr;
  1906. Instruction *LastValue = nullptr;
  1907. for (Instruction *Instr: ChainToBase) {
  1908. // Only GEP's and casts are suported as we need to be careful to not
  1909. // introduce any new uses of pointers not in the liveset.
  1910. // Note that it's fine to introduce new uses of pointers which were
  1911. // otherwise not used after this statepoint.
  1912. assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
  1913. Instruction *ClonedValue = Instr->clone();
  1914. ClonedValue->insertBefore(InsertBefore);
  1915. ClonedValue->setName(Instr->getName() + ".remat");
  1916. // If it is not first instruction in the chain then it uses previously
  1917. // cloned value. We should update it to use cloned value.
  1918. if (LastClonedValue) {
  1919. assert(LastValue);
  1920. ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue);
  1921. #ifndef NDEBUG
  1922. // Assert that cloned instruction does not use any instructions from
  1923. // this chain other than LastClonedValue
  1924. for (auto OpValue : ClonedValue->operand_values()) {
  1925. assert(std::find(ChainToBase.begin(), ChainToBase.end(), OpValue) ==
  1926. ChainToBase.end() &&
  1927. "incorrect use in rematerialization chain");
  1928. }
  1929. #endif
  1930. }
  1931. LastClonedValue = ClonedValue;
  1932. LastValue = Instr;
  1933. }
  1934. assert(LastClonedValue);
  1935. return LastClonedValue;
  1936. };
  1937. // Different cases for calls and invokes. For invokes we need to clone
  1938. // instructions both on normal and unwind path.
  1939. if (CS.isCall()) {
  1940. Instruction *InsertBefore = CS.getInstruction()->getNextNode();
  1941. assert(InsertBefore);
  1942. Instruction *RematerializedValue = rematerializeChain(InsertBefore);
  1943. Info.RematerializedValues[RematerializedValue] = LiveValue;
  1944. } else {
  1945. InvokeInst *Invoke = cast<InvokeInst>(CS.getInstruction());
  1946. Instruction *NormalInsertBefore =
  1947. &*Invoke->getNormalDest()->getFirstInsertionPt();
  1948. Instruction *UnwindInsertBefore =
  1949. &*Invoke->getUnwindDest()->getFirstInsertionPt();
  1950. Instruction *NormalRematerializedValue =
  1951. rematerializeChain(NormalInsertBefore);
  1952. Instruction *UnwindRematerializedValue =
  1953. rematerializeChain(UnwindInsertBefore);
  1954. Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
  1955. Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
  1956. }
  1957. }
  1958. // Remove rematerializaed values from the live set
  1959. for (auto LiveValue: LiveValuesToBeDeleted) {
  1960. Info.LiveSet.erase(LiveValue);
  1961. }
  1962. }
  1963. static bool insertParsePoints(Function &F, DominatorTree &DT,
  1964. TargetTransformInfo &TTI,
  1965. SmallVectorImpl<CallSite> &ToUpdate) {
  1966. #ifndef NDEBUG
  1967. // sanity check the input
  1968. std::set<CallSite> Uniqued;
  1969. Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
  1970. assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
  1971. for (CallSite CS : ToUpdate) {
  1972. assert(CS.getInstruction()->getParent()->getParent() == &F);
  1973. assert((UseDeoptBundles || isStatepoint(CS)) &&
  1974. "expected to already be a deopt statepoint");
  1975. }
  1976. #endif
  1977. // When inserting gc.relocates for invokes, we need to be able to insert at
  1978. // the top of the successor blocks. See the comment on
  1979. // normalForInvokeSafepoint on exactly what is needed. Note that this step
  1980. // may restructure the CFG.
  1981. for (CallSite CS : ToUpdate) {
  1982. if (!CS.isInvoke())
  1983. continue;
  1984. auto *II = cast<InvokeInst>(CS.getInstruction());
  1985. normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);
  1986. normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);
  1987. }
  1988. // A list of dummy calls added to the IR to keep various values obviously
  1989. // live in the IR. We'll remove all of these when done.
  1990. SmallVector<CallInst *, 64> Holders;
  1991. // Insert a dummy call with all of the arguments to the vm_state we'll need
  1992. // for the actual safepoint insertion. This ensures reference arguments in
  1993. // the deopt argument list are considered live through the safepoint (and
  1994. // thus makes sure they get relocated.)
  1995. for (CallSite CS : ToUpdate) {
  1996. SmallVector<Value *, 64> DeoptValues;
  1997. iterator_range<const Use *> DeoptStateRange =
  1998. UseDeoptBundles
  1999. ? iterator_range<const Use *>(GetDeoptBundleOperands(CS))
  2000. : iterator_range<const Use *>(Statepoint(CS).vm_state_args());
  2001. for (Value *Arg : DeoptStateRange) {
  2002. assert(!isUnhandledGCPointerType(Arg->getType()) &&
  2003. "support for FCA unimplemented");
  2004. if (isHandledGCPointerType(Arg->getType()))
  2005. DeoptValues.push_back(Arg);
  2006. }
  2007. insertUseHolderAfter(CS, DeoptValues, Holders);
  2008. }
  2009. SmallVector<PartiallyConstructedSafepointRecord, 64> Records(ToUpdate.size());
  2010. // A) Identify all gc pointers which are statically live at the given call
  2011. // site.
  2012. findLiveReferences(F, DT, ToUpdate, Records);
  2013. // B) Find the base pointers for each live pointer
  2014. /* scope for caching */ {
  2015. // Cache the 'defining value' relation used in the computation and
  2016. // insertion of base phis and selects. This ensures that we don't insert
  2017. // large numbers of duplicate base_phis.
  2018. DefiningValueMapTy DVCache;
  2019. for (size_t i = 0; i < Records.size(); i++) {
  2020. PartiallyConstructedSafepointRecord &info = Records[i];
  2021. findBasePointers(DT, DVCache, ToUpdate[i], info);
  2022. }
  2023. } // end of cache scope
  2024. // The base phi insertion logic (for any safepoint) may have inserted new
  2025. // instructions which are now live at some safepoint. The simplest such
  2026. // example is:
  2027. // loop:
  2028. // phi a <-- will be a new base_phi here
  2029. // safepoint 1 <-- that needs to be live here
  2030. // gep a + 1
  2031. // safepoint 2
  2032. // br loop
  2033. // We insert some dummy calls after each safepoint to definitely hold live
  2034. // the base pointers which were identified for that safepoint. We'll then
  2035. // ask liveness for _every_ base inserted to see what is now live. Then we
  2036. // remove the dummy calls.
  2037. Holders.reserve(Holders.size() + Records.size());
  2038. for (size_t i = 0; i < Records.size(); i++) {
  2039. PartiallyConstructedSafepointRecord &Info = Records[i];
  2040. SmallVector<Value *, 128> Bases;
  2041. for (auto Pair : Info.PointerToBase)
  2042. Bases.push_back(Pair.second);
  2043. insertUseHolderAfter(ToUpdate[i], Bases, Holders);
  2044. }
  2045. // By selecting base pointers, we've effectively inserted new uses. Thus, we
  2046. // need to rerun liveness. We may *also* have inserted new defs, but that's
  2047. // not the key issue.
  2048. recomputeLiveInValues(F, DT, ToUpdate, Records);
  2049. if (PrintBasePointers) {
  2050. for (auto &Info : Records) {
  2051. errs() << "Base Pairs: (w/Relocation)\n";
  2052. for (auto Pair : Info.PointerToBase) {
  2053. errs() << " derived ";
  2054. Pair.first->printAsOperand(errs(), false);
  2055. errs() << " base ";
  2056. Pair.second->printAsOperand(errs(), false);
  2057. errs() << "\n";
  2058. }
  2059. }
  2060. }
  2061. // It is possible that non-constant live variables have a constant base. For
  2062. // example, a GEP with a variable offset from a global. In this case we can
  2063. // remove it from the liveset. We already don't add constants to the liveset
  2064. // because we assume they won't move at runtime and the GC doesn't need to be
  2065. // informed about them. The same reasoning applies if the base is constant.
  2066. // Note that the relocation placement code relies on this filtering for
  2067. // correctness as it expects the base to be in the liveset, which isn't true
  2068. // if the base is constant.
  2069. for (auto &Info : Records)
  2070. for (auto &BasePair : Info.PointerToBase)
  2071. if (isa<Constant>(BasePair.second))
  2072. Info.LiveSet.erase(BasePair.first);
  2073. for (CallInst *CI : Holders)
  2074. CI->eraseFromParent();
  2075. Holders.clear();
  2076. // Do a limited scalarization of any live at safepoint vector values which
  2077. // contain pointers. This enables this pass to run after vectorization at
  2078. // the cost of some possible performance loss. Note: This is known to not
  2079. // handle updating of the side tables correctly which can lead to relocation
  2080. // bugs when the same vector is live at multiple statepoints. We're in the
  2081. // process of implementing the alternate lowering - relocating the
  2082. // vector-of-pointers as first class item and updating the backend to
  2083. // understand that - but that's not yet complete.
  2084. if (UseVectorSplit)
  2085. for (size_t i = 0; i < Records.size(); i++) {
  2086. PartiallyConstructedSafepointRecord &Info = Records[i];
  2087. Instruction *Statepoint = ToUpdate[i].getInstruction();
  2088. splitVectorValues(cast<Instruction>(Statepoint), Info.LiveSet,
  2089. Info.PointerToBase, DT);
  2090. }
  2091. // In order to reduce live set of statepoint we might choose to rematerialize
  2092. // some values instead of relocating them. This is purely an optimization and
  2093. // does not influence correctness.
  2094. for (size_t i = 0; i < Records.size(); i++)
  2095. rematerializeLiveValues(ToUpdate[i], Records[i], TTI);
  2096. // We need this to safely RAUW and delete call or invoke return values that
  2097. // may themselves be live over a statepoint. For details, please see usage in
  2098. // makeStatepointExplicitImpl.
  2099. std::vector<DeferredReplacement> Replacements;
  2100. // Now run through and replace the existing statepoints with new ones with
  2101. // the live variables listed. We do not yet update uses of the values being
  2102. // relocated. We have references to live variables that need to
  2103. // survive to the last iteration of this loop. (By construction, the
  2104. // previous statepoint can not be a live variable, thus we can and remove
  2105. // the old statepoint calls as we go.)
  2106. for (size_t i = 0; i < Records.size(); i++)
  2107. makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements);
  2108. ToUpdate.clear(); // prevent accident use of invalid CallSites
  2109. for (auto &PR : Replacements)
  2110. PR.doReplacement();
  2111. Replacements.clear();
  2112. for (auto &Info : Records) {
  2113. // These live sets may contain state Value pointers, since we replaced calls
  2114. // with operand bundles with calls wrapped in gc.statepoint, and some of
  2115. // those calls may have been def'ing live gc pointers. Clear these out to
  2116. // avoid accidentally using them.
  2117. //
  2118. // TODO: We should create a separate data structure that does not contain
  2119. // these live sets, and migrate to using that data structure from this point
  2120. // onward.
  2121. Info.LiveSet.clear();
  2122. Info.PointerToBase.clear();
  2123. }
  2124. // Do all the fixups of the original live variables to their relocated selves
  2125. SmallVector<Value *, 128> Live;
  2126. for (size_t i = 0; i < Records.size(); i++) {
  2127. PartiallyConstructedSafepointRecord &Info = Records[i];
  2128. // We can't simply save the live set from the original insertion. One of
  2129. // the live values might be the result of a call which needs a safepoint.
  2130. // That Value* no longer exists and we need to use the new gc_result.
  2131. // Thankfully, the live set is embedded in the statepoint (and updated), so
  2132. // we just grab that.
  2133. Statepoint Statepoint(Info.StatepointToken);
  2134. Live.insert(Live.end(), Statepoint.gc_args_begin(),
  2135. Statepoint.gc_args_end());
  2136. #ifndef NDEBUG
  2137. // Do some basic sanity checks on our liveness results before performing
  2138. // relocation. Relocation can and will turn mistakes in liveness results
  2139. // into non-sensical code which is must harder to debug.
  2140. // TODO: It would be nice to test consistency as well
  2141. assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) &&
  2142. "statepoint must be reachable or liveness is meaningless");
  2143. for (Value *V : Statepoint.gc_args()) {
  2144. if (!isa<Instruction>(V))
  2145. // Non-instruction values trivial dominate all possible uses
  2146. continue;
  2147. auto *LiveInst = cast<Instruction>(V);
  2148. assert(DT.isReachableFromEntry(LiveInst->getParent()) &&
  2149. "unreachable values should never be live");
  2150. assert(DT.dominates(LiveInst, Info.StatepointToken) &&
  2151. "basic SSA liveness expectation violated by liveness analysis");
  2152. }
  2153. #endif
  2154. }
  2155. unique_unsorted(Live);
  2156. #ifndef NDEBUG
  2157. // sanity check
  2158. for (auto *Ptr : Live)
  2159. assert(isHandledGCPointerType(Ptr->getType()) &&
  2160. "must be a gc pointer type");
  2161. #endif
  2162. relocationViaAlloca(F, DT, Live, Records);
  2163. return !Records.empty();
  2164. }
  2165. // Handles both return values and arguments for Functions and CallSites.
  2166. template <typename AttrHolder>
  2167. static void RemoveNonValidAttrAtIndex(LLVMContext &Ctx, AttrHolder &AH,
  2168. unsigned Index) {
  2169. AttrBuilder R;
  2170. if (AH.getDereferenceableBytes(Index))
  2171. R.addAttribute(Attribute::get(Ctx, Attribute::Dereferenceable,
  2172. AH.getDereferenceableBytes(Index)));
  2173. if (AH.getDereferenceableOrNullBytes(Index))
  2174. R.addAttribute(Attribute::get(Ctx, Attribute::DereferenceableOrNull,
  2175. AH.getDereferenceableOrNullBytes(Index)));
  2176. if (AH.doesNotAlias(Index))
  2177. R.addAttribute(Attribute::NoAlias);
  2178. if (!R.empty())
  2179. AH.setAttributes(AH.getAttributes().removeAttributes(
  2180. Ctx, Index, AttributeSet::get(Ctx, Index, R)));
  2181. }
  2182. void
  2183. RewriteStatepointsForGC::stripNonValidAttributesFromPrototype(Function &F) {
  2184. LLVMContext &Ctx = F.getContext();
  2185. for (Argument &A : F.args())
  2186. if (isa<PointerType>(A.getType()))
  2187. RemoveNonValidAttrAtIndex(Ctx, F, A.getArgNo() + 1);
  2188. if (isa<PointerType>(F.getReturnType()))
  2189. RemoveNonValidAttrAtIndex(Ctx, F, AttributeSet::ReturnIndex);
  2190. }
  2191. void RewriteStatepointsForGC::stripNonValidAttributesFromBody(Function &F) {
  2192. if (F.empty())
  2193. return;
  2194. LLVMContext &Ctx = F.getContext();
  2195. MDBuilder Builder(Ctx);
  2196. for (Instruction &I : instructions(F)) {
  2197. if (const MDNode *MD = I.getMetadata(LLVMContext::MD_tbaa)) {
  2198. assert(MD->getNumOperands() < 5 && "unrecognized metadata shape!");
  2199. bool IsImmutableTBAA =
  2200. MD->getNumOperands() == 4 &&
  2201. mdconst::extract<ConstantInt>(MD->getOperand(3))->getValue() == 1;
  2202. if (!IsImmutableTBAA)
  2203. continue; // no work to do, MD_tbaa is already marked mutable
  2204. MDNode *Base = cast<MDNode>(MD->getOperand(0));
  2205. MDNode *Access = cast<MDNode>(MD->getOperand(1));
  2206. uint64_t Offset =
  2207. mdconst::extract<ConstantInt>(MD->getOperand(2))->getZExtValue();
  2208. MDNode *MutableTBAA =
  2209. Builder.createTBAAStructTagNode(Base, Access, Offset);
  2210. I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
  2211. }
  2212. if (CallSite CS = CallSite(&I)) {
  2213. for (int i = 0, e = CS.arg_size(); i != e; i++)
  2214. if (isa<PointerType>(CS.getArgument(i)->getType()))
  2215. RemoveNonValidAttrAtIndex(Ctx, CS, i + 1);
  2216. if (isa<PointerType>(CS.getType()))
  2217. RemoveNonValidAttrAtIndex(Ctx, CS, AttributeSet::ReturnIndex);
  2218. }
  2219. }
  2220. }
  2221. /// Returns true if this function should be rewritten by this pass. The main
  2222. /// point of this function is as an extension point for custom logic.
  2223. static bool shouldRewriteStatepointsIn(Function &F) {
  2224. // TODO: This should check the GCStrategy
  2225. if (F.hasGC()) {
  2226. const auto &FunctionGCName = F.getGC();
  2227. const StringRef StatepointExampleName("statepoint-example");
  2228. const StringRef CoreCLRName("coreclr");
  2229. return (StatepointExampleName == FunctionGCName) ||
  2230. (CoreCLRName == FunctionGCName);
  2231. } else
  2232. return false;
  2233. }
  2234. void RewriteStatepointsForGC::stripNonValidAttributes(Module &M) {
  2235. #ifndef NDEBUG
  2236. assert(std::any_of(M.begin(), M.end(), shouldRewriteStatepointsIn) &&
  2237. "precondition!");
  2238. #endif
  2239. for (Function &F : M)
  2240. stripNonValidAttributesFromPrototype(F);
  2241. for (Function &F : M)
  2242. stripNonValidAttributesFromBody(F);
  2243. }
  2244. bool RewriteStatepointsForGC::runOnFunction(Function &F) {
  2245. // Nothing to do for declarations.
  2246. if (F.isDeclaration() || F.empty())
  2247. return false;
  2248. // Policy choice says not to rewrite - the most common reason is that we're
  2249. // compiling code without a GCStrategy.
  2250. if (!shouldRewriteStatepointsIn(F))
  2251. return false;
  2252. DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
  2253. TargetTransformInfo &TTI =
  2254. getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
  2255. auto NeedsRewrite = [](Instruction &I) {
  2256. if (UseDeoptBundles) {
  2257. if (ImmutableCallSite CS = ImmutableCallSite(&I))
  2258. return !callsGCLeafFunction(CS);
  2259. return false;
  2260. }
  2261. return isStatepoint(I);
  2262. };
  2263. // Gather all the statepoints which need rewritten. Be careful to only
  2264. // consider those in reachable code since we need to ask dominance queries
  2265. // when rewriting. We'll delete the unreachable ones in a moment.
  2266. SmallVector<CallSite, 64> ParsePointNeeded;
  2267. bool HasUnreachableStatepoint = false;
  2268. for (Instruction &I : instructions(F)) {
  2269. // TODO: only the ones with the flag set!
  2270. if (NeedsRewrite(I)) {
  2271. if (DT.isReachableFromEntry(I.getParent()))
  2272. ParsePointNeeded.push_back(CallSite(&I));
  2273. else
  2274. HasUnreachableStatepoint = true;
  2275. }
  2276. }
  2277. bool MadeChange = false;
  2278. // Delete any unreachable statepoints so that we don't have unrewritten
  2279. // statepoints surviving this pass. This makes testing easier and the
  2280. // resulting IR less confusing to human readers. Rather than be fancy, we
  2281. // just reuse a utility function which removes the unreachable blocks.
  2282. if (HasUnreachableStatepoint)
  2283. MadeChange |= removeUnreachableBlocks(F);
  2284. // Return early if no work to do.
  2285. if (ParsePointNeeded.empty())
  2286. return MadeChange;
  2287. // As a prepass, go ahead and aggressively destroy single entry phi nodes.
  2288. // These are created by LCSSA. They have the effect of increasing the size
  2289. // of liveness sets for no good reason. It may be harder to do this post
  2290. // insertion since relocations and base phis can confuse things.
  2291. for (BasicBlock &BB : F)
  2292. if (BB.getUniquePredecessor()) {
  2293. MadeChange = true;
  2294. FoldSingleEntryPHINodes(&BB);
  2295. }
  2296. // Before we start introducing relocations, we want to tweak the IR a bit to
  2297. // avoid unfortunate code generation effects. The main example is that we
  2298. // want to try to make sure the comparison feeding a branch is after any
  2299. // safepoints. Otherwise, we end up with a comparison of pre-relocation
  2300. // values feeding a branch after relocation. This is semantically correct,
  2301. // but results in extra register pressure since both the pre-relocation and
  2302. // post-relocation copies must be available in registers. For code without
  2303. // relocations this is handled elsewhere, but teaching the scheduler to
  2304. // reverse the transform we're about to do would be slightly complex.
  2305. // Note: This may extend the live range of the inputs to the icmp and thus
  2306. // increase the liveset of any statepoint we move over. This is profitable
  2307. // as long as all statepoints are in rare blocks. If we had in-register
  2308. // lowering for live values this would be a much safer transform.
  2309. auto getConditionInst = [](TerminatorInst *TI) -> Instruction* {
  2310. if (auto *BI = dyn_cast<BranchInst>(TI))
  2311. if (BI->isConditional())
  2312. return dyn_cast<Instruction>(BI->getCondition());
  2313. // TODO: Extend this to handle switches
  2314. return nullptr;
  2315. };
  2316. for (BasicBlock &BB : F) {
  2317. TerminatorInst *TI = BB.getTerminator();
  2318. if (auto *Cond = getConditionInst(TI))
  2319. // TODO: Handle more than just ICmps here. We should be able to move
  2320. // most instructions without side effects or memory access.
  2321. if (isa<ICmpInst>(Cond) && Cond->hasOneUse()) {
  2322. MadeChange = true;
  2323. Cond->moveBefore(TI);
  2324. }
  2325. }
  2326. MadeChange |= insertParsePoints(F, DT, TTI, ParsePointNeeded);
  2327. return MadeChange;
  2328. }
  2329. // liveness computation via standard dataflow
  2330. // -------------------------------------------------------------------
  2331. // TODO: Consider using bitvectors for liveness, the set of potentially
  2332. // interesting values should be small and easy to pre-compute.
  2333. /// Compute the live-in set for the location rbegin starting from
  2334. /// the live-out set of the basic block
  2335. static void computeLiveInValues(BasicBlock::reverse_iterator rbegin,
  2336. BasicBlock::reverse_iterator rend,
  2337. DenseSet<Value *> &LiveTmp) {
  2338. for (BasicBlock::reverse_iterator ritr = rbegin; ritr != rend; ritr++) {
  2339. Instruction *I = &*ritr;
  2340. // KILL/Def - Remove this definition from LiveIn
  2341. LiveTmp.erase(I);
  2342. // Don't consider *uses* in PHI nodes, we handle their contribution to
  2343. // predecessor blocks when we seed the LiveOut sets
  2344. if (isa<PHINode>(I))
  2345. continue;
  2346. // USE - Add to the LiveIn set for this instruction
  2347. for (Value *V : I->operands()) {
  2348. assert(!isUnhandledGCPointerType(V->getType()) &&
  2349. "support for FCA unimplemented");
  2350. if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
  2351. // The choice to exclude all things constant here is slightly subtle.
  2352. // There are two independent reasons:
  2353. // - We assume that things which are constant (from LLVM's definition)
  2354. // do not move at runtime. For example, the address of a global
  2355. // variable is fixed, even though it's contents may not be.
  2356. // - Second, we can't disallow arbitrary inttoptr constants even
  2357. // if the language frontend does. Optimization passes are free to
  2358. // locally exploit facts without respect to global reachability. This
  2359. // can create sections of code which are dynamically unreachable and
  2360. // contain just about anything. (see constants.ll in tests)
  2361. LiveTmp.insert(V);
  2362. }
  2363. }
  2364. }
  2365. }
  2366. static void computeLiveOutSeed(BasicBlock *BB, DenseSet<Value *> &LiveTmp) {
  2367. for (BasicBlock *Succ : successors(BB)) {
  2368. const BasicBlock::iterator E(Succ->getFirstNonPHI());
  2369. for (BasicBlock::iterator I = Succ->begin(); I != E; I++) {
  2370. PHINode *Phi = cast<PHINode>(&*I);
  2371. Value *V = Phi->getIncomingValueForBlock(BB);
  2372. assert(!isUnhandledGCPointerType(V->getType()) &&
  2373. "support for FCA unimplemented");
  2374. if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
  2375. LiveTmp.insert(V);
  2376. }
  2377. }
  2378. }
  2379. }
  2380. static DenseSet<Value *> computeKillSet(BasicBlock *BB) {
  2381. DenseSet<Value *> KillSet;
  2382. for (Instruction &I : *BB)
  2383. if (isHandledGCPointerType(I.getType()))
  2384. KillSet.insert(&I);
  2385. return KillSet;
  2386. }
  2387. #ifndef NDEBUG
  2388. /// Check that the items in 'Live' dominate 'TI'. This is used as a basic
  2389. /// sanity check for the liveness computation.
  2390. static void checkBasicSSA(DominatorTree &DT, DenseSet<Value *> &Live,
  2391. TerminatorInst *TI, bool TermOkay = false) {
  2392. for (Value *V : Live) {
  2393. if (auto *I = dyn_cast<Instruction>(V)) {
  2394. // The terminator can be a member of the LiveOut set. LLVM's definition
  2395. // of instruction dominance states that V does not dominate itself. As
  2396. // such, we need to special case this to allow it.
  2397. if (TermOkay && TI == I)
  2398. continue;
  2399. assert(DT.dominates(I, TI) &&
  2400. "basic SSA liveness expectation violated by liveness analysis");
  2401. }
  2402. }
  2403. }
  2404. /// Check that all the liveness sets used during the computation of liveness
  2405. /// obey basic SSA properties. This is useful for finding cases where we miss
  2406. /// a def.
  2407. static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,
  2408. BasicBlock &BB) {
  2409. checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator());
  2410. checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);
  2411. checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());
  2412. }
  2413. #endif
  2414. static void computeLiveInValues(DominatorTree &DT, Function &F,
  2415. GCPtrLivenessData &Data) {
  2416. SmallSetVector<BasicBlock *, 200> Worklist;
  2417. auto AddPredsToWorklist = [&](BasicBlock *BB) {
  2418. // We use a SetVector so that we don't have duplicates in the worklist.
  2419. Worklist.insert(pred_begin(BB), pred_end(BB));
  2420. };
  2421. auto NextItem = [&]() {
  2422. BasicBlock *BB = Worklist.back();
  2423. Worklist.pop_back();
  2424. return BB;
  2425. };
  2426. // Seed the liveness for each individual block
  2427. for (BasicBlock &BB : F) {
  2428. Data.KillSet[&BB] = computeKillSet(&BB);
  2429. Data.LiveSet[&BB].clear();
  2430. computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB]);
  2431. #ifndef NDEBUG
  2432. for (Value *Kill : Data.KillSet[&BB])
  2433. assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");
  2434. #endif
  2435. Data.LiveOut[&BB] = DenseSet<Value *>();
  2436. computeLiveOutSeed(&BB, Data.LiveOut[&BB]);
  2437. Data.LiveIn[&BB] = Data.LiveSet[&BB];
  2438. set_union(Data.LiveIn[&BB], Data.LiveOut[&BB]);
  2439. set_subtract(Data.LiveIn[&BB], Data.KillSet[&BB]);
  2440. if (!Data.LiveIn[&BB].empty())
  2441. AddPredsToWorklist(&BB);
  2442. }
  2443. // Propagate that liveness until stable
  2444. while (!Worklist.empty()) {
  2445. BasicBlock *BB = NextItem();
  2446. // Compute our new liveout set, then exit early if it hasn't changed
  2447. // despite the contribution of our successor.
  2448. DenseSet<Value *> LiveOut = Data.LiveOut[BB];
  2449. const auto OldLiveOutSize = LiveOut.size();
  2450. for (BasicBlock *Succ : successors(BB)) {
  2451. assert(Data.LiveIn.count(Succ));
  2452. set_union(LiveOut, Data.LiveIn[Succ]);
  2453. }
  2454. // assert OutLiveOut is a subset of LiveOut
  2455. if (OldLiveOutSize == LiveOut.size()) {
  2456. // If the sets are the same size, then we didn't actually add anything
  2457. // when unioning our successors LiveIn Thus, the LiveIn of this block
  2458. // hasn't changed.
  2459. continue;
  2460. }
  2461. Data.LiveOut[BB] = LiveOut;
  2462. // Apply the effects of this basic block
  2463. DenseSet<Value *> LiveTmp = LiveOut;
  2464. set_union(LiveTmp, Data.LiveSet[BB]);
  2465. set_subtract(LiveTmp, Data.KillSet[BB]);
  2466. assert(Data.LiveIn.count(BB));
  2467. const DenseSet<Value *> &OldLiveIn = Data.LiveIn[BB];
  2468. // assert: OldLiveIn is a subset of LiveTmp
  2469. if (OldLiveIn.size() != LiveTmp.size()) {
  2470. Data.LiveIn[BB] = LiveTmp;
  2471. AddPredsToWorklist(BB);
  2472. }
  2473. } // while( !worklist.empty() )
  2474. #ifndef NDEBUG
  2475. // Sanity check our output against SSA properties. This helps catch any
  2476. // missing kills during the above iteration.
  2477. for (BasicBlock &BB : F) {
  2478. checkBasicSSA(DT, Data, BB);
  2479. }
  2480. #endif
  2481. }
  2482. static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,
  2483. StatepointLiveSetTy &Out) {
  2484. BasicBlock *BB = Inst->getParent();
  2485. // Note: The copy is intentional and required
  2486. assert(Data.LiveOut.count(BB));
  2487. DenseSet<Value *> LiveOut = Data.LiveOut[BB];
  2488. // We want to handle the statepoint itself oddly. It's
  2489. // call result is not live (normal), nor are it's arguments
  2490. // (unless they're used again later). This adjustment is
  2491. // specifically what we need to relocate
  2492. BasicBlock::reverse_iterator rend(Inst->getIterator());
  2493. computeLiveInValues(BB->rbegin(), rend, LiveOut);
  2494. LiveOut.erase(Inst);
  2495. Out.insert(LiveOut.begin(), LiveOut.end());
  2496. }
  2497. static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
  2498. const CallSite &CS,
  2499. PartiallyConstructedSafepointRecord &Info) {
  2500. Instruction *Inst = CS.getInstruction();
  2501. StatepointLiveSetTy Updated;
  2502. findLiveSetAtInst(Inst, RevisedLivenessData, Updated);
  2503. #ifndef NDEBUG
  2504. DenseSet<Value *> Bases;
  2505. for (auto KVPair : Info.PointerToBase) {
  2506. Bases.insert(KVPair.second);
  2507. }
  2508. #endif
  2509. // We may have base pointers which are now live that weren't before. We need
  2510. // to update the PointerToBase structure to reflect this.
  2511. for (auto V : Updated)
  2512. if (!Info.PointerToBase.count(V)) {
  2513. assert(Bases.count(V) && "can't find base for unexpected live value");
  2514. Info.PointerToBase[V] = V;
  2515. continue;
  2516. }
  2517. #ifndef NDEBUG
  2518. for (auto V : Updated) {
  2519. assert(Info.PointerToBase.count(V) &&
  2520. "must be able to find base for live value");
  2521. }
  2522. #endif
  2523. // Remove any stale base mappings - this can happen since our liveness is
  2524. // more precise then the one inherent in the base pointer analysis
  2525. DenseSet<Value *> ToErase;
  2526. for (auto KVPair : Info.PointerToBase)
  2527. if (!Updated.count(KVPair.first))
  2528. ToErase.insert(KVPair.first);
  2529. for (auto V : ToErase)
  2530. Info.PointerToBase.erase(V);
  2531. #ifndef NDEBUG
  2532. for (auto KVPair : Info.PointerToBase)
  2533. assert(Updated.count(KVPair.first) && "record for non-live value");
  2534. #endif
  2535. Info.LiveSet = Updated;
  2536. }