1320957Sdim//===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===// 2320957Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6320957Sdim// 7320957Sdim//===----------------------------------------------------------------------===// 8320957Sdim// 9320957Sdim// Run a sanity check on the IR to ensure that Safepoints - if they've been 10320957Sdim// inserted - were inserted correctly. In particular, look for use of 11320957Sdim// non-relocated values after a safepoint. It's primary use is to check the 12320957Sdim// correctness of safepoint insertion immediately after insertion, but it can 13320957Sdim// also be used to verify that later transforms have not found a way to break 14320957Sdim// safepoint semenatics. 15320957Sdim// 16320957Sdim// In its current form, this verify checks a property which is sufficient, but 17320957Sdim// not neccessary for correctness. There are some cases where an unrelocated 18320957Sdim// pointer can be used after the safepoint. Consider this example: 19320957Sdim// 20320957Sdim// a = ... 21320957Sdim// b = ... 22320957Sdim// (a',b') = safepoint(a,b) 23320957Sdim// c = cmp eq a b 24320957Sdim// br c, ..., .... 25320957Sdim// 26320957Sdim// Because it is valid to reorder 'c' above the safepoint, this is legal. In 27320957Sdim// practice, this is a somewhat uncommon transform, but CodeGenPrep does create 28320957Sdim// idioms like this. The verifier knows about these cases and avoids reporting 29320957Sdim// false positives. 30320957Sdim// 31320957Sdim//===----------------------------------------------------------------------===// 32320957Sdim 33360784Sdim#include "llvm/IR/SafepointIRVerifier.h" 34320957Sdim#include "llvm/ADT/DenseSet.h" 35327952Sdim#include "llvm/ADT/PostOrderIterator.h" 36320957Sdim#include "llvm/ADT/SetOperations.h" 37320957Sdim#include "llvm/ADT/SetVector.h" 38320957Sdim#include "llvm/IR/BasicBlock.h" 39320957Sdim#include "llvm/IR/Dominators.h" 40320957Sdim#include "llvm/IR/Function.h" 41320957Sdim#include "llvm/IR/Instructions.h" 42360784Sdim#include "llvm/IR/IntrinsicInst.h" 43320957Sdim#include "llvm/IR/Intrinsics.h" 44320957Sdim#include "llvm/IR/Module.h" 45360784Sdim#include "llvm/IR/Statepoint.h" 46320957Sdim#include "llvm/IR/Value.h" 47360784Sdim#include "llvm/InitializePasses.h" 48360784Sdim#include "llvm/Support/CommandLine.h" 49320957Sdim#include "llvm/Support/Debug.h" 50320957Sdim#include "llvm/Support/raw_ostream.h" 51320957Sdim 52320957Sdim#define DEBUG_TYPE "safepoint-ir-verifier" 53320957Sdim 54320957Sdimusing namespace llvm; 55320957Sdim 56320957Sdim/// This option is used for writing test cases. Instead of crashing the program 57320957Sdim/// when verification fails, report a message to the console (for FileCheck 58320957Sdim/// usage) and continue execution as if nothing happened. 59320957Sdimstatic cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only", 60320957Sdim cl::init(false)); 61320957Sdim 62341825Sdimnamespace { 63320957Sdim 64341825Sdim/// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set 65341825Sdim/// of blocks unreachable from entry then propagates deadness using foldable 66341825Sdim/// conditional branches without modifying CFG. So GVN does but it changes CFG 67341825Sdim/// by splitting critical edges. In most cases passes rely on SimplifyCFG to 68341825Sdim/// clean up dead blocks, but in some cases, like verification or loop passes 69341825Sdim/// it's not possible. 70341825Sdimclass CFGDeadness { 71341825Sdim const DominatorTree *DT = nullptr; 72341825Sdim SetVector<const BasicBlock *> DeadBlocks; 73341825Sdim SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks. 74341825Sdim 75341825Sdimpublic: 76341825Sdim /// Return the edge that coresponds to the predecessor. 77341825Sdim static const Use& getEdge(const_pred_iterator &PredIt) { 78341825Sdim auto &PU = PredIt.getUse(); 79341825Sdim return PU.getUser()->getOperandUse(PU.getOperandNo()); 80341825Sdim } 81341825Sdim 82341825Sdim /// Return true if there is at least one live edge that corresponds to the 83341825Sdim /// basic block InBB listed in the phi node. 84341825Sdim bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const { 85341825Sdim assert(!isDeadBlock(InBB) && "block must be live"); 86341825Sdim const BasicBlock* BB = PN->getParent(); 87341825Sdim bool Listed = false; 88341825Sdim for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { 89341825Sdim if (InBB == *PredIt) { 90341825Sdim if (!isDeadEdge(&getEdge(PredIt))) 91341825Sdim return true; 92341825Sdim Listed = true; 93341825Sdim } 94341825Sdim } 95344779Sdim (void)Listed; 96341825Sdim assert(Listed && "basic block is not found among incoming blocks"); 97341825Sdim return false; 98341825Sdim } 99341825Sdim 100341825Sdim 101341825Sdim bool isDeadBlock(const BasicBlock *BB) const { 102341825Sdim return DeadBlocks.count(BB); 103341825Sdim } 104341825Sdim 105341825Sdim bool isDeadEdge(const Use *U) const { 106360784Sdim assert(cast<Instruction>(U->getUser())->isTerminator() && 107341825Sdim "edge must be operand of terminator"); 108341825Sdim assert(cast_or_null<BasicBlock>(U->get()) && 109341825Sdim "edge must refer to basic block"); 110360784Sdim assert(!isDeadBlock(cast<Instruction>(U->getUser())->getParent()) && 111341825Sdim "isDeadEdge() must be applied to edge from live block"); 112341825Sdim return DeadEdges.count(U); 113341825Sdim } 114341825Sdim 115341825Sdim bool hasLiveIncomingEdges(const BasicBlock *BB) const { 116341825Sdim // Check if all incoming edges are dead. 117341825Sdim for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { 118341825Sdim auto &PU = PredIt.getUse(); 119341825Sdim const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo()); 120341825Sdim if (!isDeadBlock(*PredIt) && !isDeadEdge(&U)) 121341825Sdim return true; // Found a live edge. 122341825Sdim } 123341825Sdim return false; 124341825Sdim } 125341825Sdim 126341825Sdim void processFunction(const Function &F, const DominatorTree &DT) { 127341825Sdim this->DT = &DT; 128341825Sdim 129341825Sdim // Start with all blocks unreachable from entry. 130341825Sdim for (const BasicBlock &BB : F) 131341825Sdim if (!DT.isReachableFromEntry(&BB)) 132341825Sdim DeadBlocks.insert(&BB); 133341825Sdim 134341825Sdim // Top-down walk of the dominator tree 135341825Sdim ReversePostOrderTraversal<const Function *> RPOT(&F); 136341825Sdim for (const BasicBlock *BB : RPOT) { 137344779Sdim const Instruction *TI = BB->getTerminator(); 138341825Sdim assert(TI && "blocks must be well formed"); 139341825Sdim 140341825Sdim // For conditional branches, we can perform simple conditional propagation on 141341825Sdim // the condition value itself. 142341825Sdim const BranchInst *BI = dyn_cast<BranchInst>(TI); 143341825Sdim if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition())) 144341825Sdim continue; 145341825Sdim 146341825Sdim // If a branch has two identical successors, we cannot declare either dead. 147341825Sdim if (BI->getSuccessor(0) == BI->getSuccessor(1)) 148341825Sdim continue; 149341825Sdim 150341825Sdim ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition()); 151341825Sdim if (!Cond) 152341825Sdim continue; 153341825Sdim 154341825Sdim addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2)); 155341825Sdim } 156341825Sdim } 157341825Sdim 158341825Sdimprotected: 159341825Sdim void addDeadBlock(const BasicBlock *BB) { 160341825Sdim SmallVector<const BasicBlock *, 4> NewDead; 161341825Sdim SmallSetVector<const BasicBlock *, 4> DF; 162341825Sdim 163341825Sdim NewDead.push_back(BB); 164341825Sdim while (!NewDead.empty()) { 165341825Sdim const BasicBlock *D = NewDead.pop_back_val(); 166341825Sdim if (isDeadBlock(D)) 167341825Sdim continue; 168341825Sdim 169341825Sdim // All blocks dominated by D are dead. 170341825Sdim SmallVector<BasicBlock *, 8> Dom; 171341825Sdim DT->getDescendants(const_cast<BasicBlock*>(D), Dom); 172341825Sdim // Do not need to mark all in and out edges dead 173341825Sdim // because BB is marked dead and this is enough 174341825Sdim // to run further. 175341825Sdim DeadBlocks.insert(Dom.begin(), Dom.end()); 176341825Sdim 177341825Sdim // Figure out the dominance-frontier(D). 178341825Sdim for (BasicBlock *B : Dom) 179341825Sdim for (BasicBlock *S : successors(B)) 180341825Sdim if (!isDeadBlock(S) && !hasLiveIncomingEdges(S)) 181341825Sdim NewDead.push_back(S); 182341825Sdim } 183341825Sdim } 184341825Sdim 185341825Sdim void addDeadEdge(const Use &DeadEdge) { 186341825Sdim if (!DeadEdges.insert(&DeadEdge)) 187341825Sdim return; 188341825Sdim 189341825Sdim BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get()); 190341825Sdim if (hasLiveIncomingEdges(BB)) 191341825Sdim return; 192341825Sdim 193341825Sdim addDeadBlock(BB); 194341825Sdim } 195341825Sdim}; 196341825Sdim} // namespace 197341825Sdim 198341825Sdimstatic void Verify(const Function &F, const DominatorTree &DT, 199341825Sdim const CFGDeadness &CD); 200341825Sdim 201353358Sdimnamespace llvm { 202353358SdimPreservedAnalyses SafepointIRVerifierPass::run(Function &F, 203353358Sdim FunctionAnalysisManager &AM) { 204353358Sdim const auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 205353358Sdim CFGDeadness CD; 206353358Sdim CD.processFunction(F, DT); 207353358Sdim Verify(F, DT, CD); 208353358Sdim return PreservedAnalyses::all(); 209353358Sdim} 210353358Sdim} 211353358Sdim 212327952Sdimnamespace { 213341825Sdim 214320957Sdimstruct SafepointIRVerifier : public FunctionPass { 215320957Sdim static char ID; // Pass identification, replacement for typeid 216320957Sdim SafepointIRVerifier() : FunctionPass(ID) { 217320957Sdim initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry()); 218320957Sdim } 219320957Sdim 220320957Sdim bool runOnFunction(Function &F) override { 221341825Sdim auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 222341825Sdim CFGDeadness CD; 223341825Sdim CD.processFunction(F, DT); 224341825Sdim Verify(F, DT, CD); 225320957Sdim return false; // no modifications 226320957Sdim } 227320957Sdim 228320957Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 229341825Sdim AU.addRequiredID(DominatorTreeWrapperPass::ID); 230320957Sdim AU.setPreservesAll(); 231320957Sdim } 232320957Sdim 233320957Sdim StringRef getPassName() const override { return "safepoint verifier"; } 234320957Sdim}; 235327952Sdim} // namespace 236320957Sdim 237320957Sdimvoid llvm::verifySafepointIR(Function &F) { 238320957Sdim SafepointIRVerifier pass; 239320957Sdim pass.runOnFunction(F); 240320957Sdim} 241320957Sdim 242320957Sdimchar SafepointIRVerifier::ID = 0; 243320957Sdim 244320957SdimFunctionPass *llvm::createSafepointIRVerifierPass() { 245320957Sdim return new SafepointIRVerifier(); 246320957Sdim} 247320957Sdim 248320957SdimINITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir", 249341825Sdim "Safepoint IR Verifier", false, false) 250341825SdimINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 251320957SdimINITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir", 252341825Sdim "Safepoint IR Verifier", false, false) 253320957Sdim 254320957Sdimstatic bool isGCPointerType(Type *T) { 255320957Sdim if (auto *PT = dyn_cast<PointerType>(T)) 256320957Sdim // For the sake of this example GC, we arbitrarily pick addrspace(1) as our 257320957Sdim // GC managed heap. We know that a pointer into this heap needs to be 258320957Sdim // updated and that no other pointer does. 259320957Sdim return (1 == PT->getAddressSpace()); 260320957Sdim return false; 261320957Sdim} 262320957Sdim 263320957Sdimstatic bool containsGCPtrType(Type *Ty) { 264320957Sdim if (isGCPointerType(Ty)) 265320957Sdim return true; 266320957Sdim if (VectorType *VT = dyn_cast<VectorType>(Ty)) 267320957Sdim return isGCPointerType(VT->getScalarType()); 268320957Sdim if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) 269320957Sdim return containsGCPtrType(AT->getElementType()); 270320957Sdim if (StructType *ST = dyn_cast<StructType>(Ty)) 271344779Sdim return llvm::any_of(ST->elements(), containsGCPtrType); 272320957Sdim return false; 273320957Sdim} 274320957Sdim 275320957Sdim// Debugging aid -- prints a [Begin, End) range of values. 276320957Sdimtemplate<typename IteratorTy> 277320957Sdimstatic void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) { 278320957Sdim OS << "[ "; 279320957Sdim while (Begin != End) { 280320957Sdim OS << **Begin << " "; 281320957Sdim ++Begin; 282320957Sdim } 283320957Sdim OS << "]"; 284320957Sdim} 285320957Sdim 286320957Sdim/// The verifier algorithm is phrased in terms of availability. The set of 287320957Sdim/// values "available" at a given point in the control flow graph is the set of 288320957Sdim/// correctly relocated value at that point, and is a subset of the set of 289320957Sdim/// definitions dominating that point. 290320957Sdim 291327952Sdimusing AvailableValueSet = DenseSet<const Value *>; 292327952Sdim 293320957Sdim/// State we compute and track per basic block. 294320957Sdimstruct BasicBlockState { 295320957Sdim // Set of values available coming in, before the phi nodes 296327952Sdim AvailableValueSet AvailableIn; 297320957Sdim 298320957Sdim // Set of values available going out 299327952Sdim AvailableValueSet AvailableOut; 300320957Sdim 301320957Sdim // AvailableOut minus AvailableIn. 302320957Sdim // All elements are Instructions 303327952Sdim AvailableValueSet Contribution; 304320957Sdim 305320957Sdim // True if this block contains a safepoint and thus AvailableIn does not 306320957Sdim // contribute to AvailableOut. 307320957Sdim bool Cleared = false; 308320957Sdim}; 309320957Sdim 310320957Sdim/// A given derived pointer can have multiple base pointers through phi/selects. 311320957Sdim/// This type indicates when the base pointer is exclusively constant 312320957Sdim/// (ExclusivelySomeConstant), and if that constant is proven to be exclusively 313320957Sdim/// null, we record that as ExclusivelyNull. In all other cases, the BaseType is 314320957Sdim/// NonConstant. 315320957Sdimenum BaseType { 316320957Sdim NonConstant = 1, // Base pointers is not exclusively constant. 317320957Sdim ExclusivelyNull, 318320957Sdim ExclusivelySomeConstant // Base pointers for a given derived pointer is from a 319320957Sdim // set of constants, but they are not exclusively 320320957Sdim // null. 321320957Sdim}; 322320957Sdim 323320957Sdim/// Return the baseType for Val which states whether Val is exclusively 324320957Sdim/// derived from constant/null, or not exclusively derived from constant. 325320957Sdim/// Val is exclusively derived off a constant base when all operands of phi and 326320957Sdim/// selects are derived off a constant base. 327320957Sdimstatic enum BaseType getBaseType(const Value *Val) { 328320957Sdim 329320957Sdim SmallVector<const Value *, 32> Worklist; 330320957Sdim DenseSet<const Value *> Visited; 331320957Sdim bool isExclusivelyDerivedFromNull = true; 332320957Sdim Worklist.push_back(Val); 333320957Sdim // Strip through all the bitcasts and geps to get base pointer. Also check for 334320957Sdim // the exclusive value when there can be multiple base pointers (through phis 335320957Sdim // or selects). 336320957Sdim while(!Worklist.empty()) { 337320957Sdim const Value *V = Worklist.pop_back_val(); 338320957Sdim if (!Visited.insert(V).second) 339320957Sdim continue; 340320957Sdim 341320957Sdim if (const auto *CI = dyn_cast<CastInst>(V)) { 342320957Sdim Worklist.push_back(CI->stripPointerCasts()); 343320957Sdim continue; 344320957Sdim } 345320957Sdim if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) { 346320957Sdim Worklist.push_back(GEP->getPointerOperand()); 347320957Sdim continue; 348320957Sdim } 349320957Sdim // Push all the incoming values of phi node into the worklist for 350320957Sdim // processing. 351320957Sdim if (const auto *PN = dyn_cast<PHINode>(V)) { 352320957Sdim for (Value *InV: PN->incoming_values()) 353320957Sdim Worklist.push_back(InV); 354320957Sdim continue; 355320957Sdim } 356320957Sdim if (const auto *SI = dyn_cast<SelectInst>(V)) { 357320957Sdim // Push in the true and false values 358320957Sdim Worklist.push_back(SI->getTrueValue()); 359320957Sdim Worklist.push_back(SI->getFalseValue()); 360320957Sdim continue; 361320957Sdim } 362320957Sdim if (isa<Constant>(V)) { 363320957Sdim // We found at least one base pointer which is non-null, so this derived 364320957Sdim // pointer is not exclusively derived from null. 365320957Sdim if (V != Constant::getNullValue(V->getType())) 366320957Sdim isExclusivelyDerivedFromNull = false; 367320957Sdim // Continue processing the remaining values to make sure it's exclusively 368320957Sdim // constant. 369320957Sdim continue; 370320957Sdim } 371320957Sdim // At this point, we know that the base pointer is not exclusively 372320957Sdim // constant. 373320957Sdim return BaseType::NonConstant; 374320957Sdim } 375320957Sdim // Now, we know that the base pointer is exclusively constant, but we need to 376320957Sdim // differentiate between exclusive null constant and non-null constant. 377320957Sdim return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull 378320957Sdim : BaseType::ExclusivelySomeConstant; 379320957Sdim} 380320957Sdim 381327952Sdimstatic bool isNotExclusivelyConstantDerived(const Value *V) { 382327952Sdim return getBaseType(V) == BaseType::NonConstant; 383327952Sdim} 384327952Sdim 385327952Sdimnamespace { 386327952Sdimclass InstructionVerifier; 387327952Sdim 388327952Sdim/// Builds BasicBlockState for each BB of the function. 389327952Sdim/// It can traverse function for verification and provides all required 390327952Sdim/// information. 391327952Sdim/// 392327952Sdim/// GC pointer may be in one of three states: relocated, unrelocated and 393327952Sdim/// poisoned. 394327952Sdim/// Relocated pointer may be used without any restrictions. 395327952Sdim/// Unrelocated pointer cannot be dereferenced, passed as argument to any call 396327952Sdim/// or returned. Unrelocated pointer may be safely compared against another 397327952Sdim/// unrelocated pointer or against a pointer exclusively derived from null. 398327952Sdim/// Poisoned pointers are produced when we somehow derive pointer from relocated 399327952Sdim/// and unrelocated pointers (e.g. phi, select). This pointers may be safely 400327952Sdim/// used in a very limited number of situations. Currently the only way to use 401327952Sdim/// it is comparison against constant exclusively derived from null. All 402327952Sdim/// limitations arise due to their undefined state: this pointers should be 403327952Sdim/// treated as relocated and unrelocated simultaneously. 404327952Sdim/// Rules of deriving: 405327952Sdim/// R + U = P - that's where the poisoned pointers come from 406327952Sdim/// P + X = P 407327952Sdim/// U + U = U 408327952Sdim/// R + R = R 409327952Sdim/// X + C = X 410327952Sdim/// Where "+" - any operation that somehow derive pointer, U - unrelocated, 411327952Sdim/// R - relocated and P - poisoned, C - constant, X - U or R or P or C or 412327952Sdim/// nothing (in case when "+" is unary operation). 413327952Sdim/// Deriving of pointers by itself is always safe. 414327952Sdim/// NOTE: when we are making decision on the status of instruction's result: 415327952Sdim/// a) for phi we need to check status of each input *at the end of 416327952Sdim/// corresponding predecessor BB*. 417327952Sdim/// b) for other instructions we need to check status of each input *at the 418327952Sdim/// current point*. 419327952Sdim/// 420327952Sdim/// FIXME: This works fairly well except one case 421327952Sdim/// bb1: 422327952Sdim/// p = *some GC-ptr def* 423327952Sdim/// p1 = gep p, offset 424327952Sdim/// / | 425327952Sdim/// / | 426327952Sdim/// bb2: | 427327952Sdim/// safepoint | 428327952Sdim/// \ | 429327952Sdim/// \ | 430327952Sdim/// bb3: 431327952Sdim/// p2 = phi [p, bb2] [p1, bb1] 432327952Sdim/// p3 = phi [p, bb2] [p, bb1] 433327952Sdim/// here p and p1 is unrelocated 434327952Sdim/// p2 and p3 is poisoned (though they shouldn't be) 435327952Sdim/// 436327952Sdim/// This leads to some weird results: 437327952Sdim/// cmp eq p, p2 - illegal instruction (false-positive) 438327952Sdim/// cmp eq p1, p2 - illegal instruction (false-positive) 439327952Sdim/// cmp eq p, p3 - illegal instruction (false-positive) 440327952Sdim/// cmp eq p, p1 - ok 441327952Sdim/// To fix this we need to introduce conception of generations and be able to 442327952Sdim/// check if two values belong to one generation or not. This way p2 will be 443327952Sdim/// considered to be unrelocated and no false alarm will happen. 444327952Sdimclass GCPtrTracker { 445327952Sdim const Function &F; 446341825Sdim const CFGDeadness &CD; 447320957Sdim SpecificBumpPtrAllocator<BasicBlockState> BSAllocator; 448320957Sdim DenseMap<const BasicBlock *, BasicBlockState *> BlockMap; 449327952Sdim // This set contains defs of unrelocated pointers that are proved to be legal 450327952Sdim // and don't need verification. 451327952Sdim DenseSet<const Instruction *> ValidUnrelocatedDefs; 452327952Sdim // This set contains poisoned defs. They can be safely ignored during 453327952Sdim // verification too. 454327952Sdim DenseSet<const Value *> PoisonedDefs; 455320957Sdim 456327952Sdimpublic: 457341825Sdim GCPtrTracker(const Function &F, const DominatorTree &DT, 458341825Sdim const CFGDeadness &CD); 459320957Sdim 460341825Sdim bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const { 461341825Sdim return CD.hasLiveIncomingEdge(PN, InBB); 462341825Sdim } 463341825Sdim 464327952Sdim BasicBlockState *getBasicBlockState(const BasicBlock *BB); 465327952Sdim const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const; 466327952Sdim 467327952Sdim bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); } 468327952Sdim 469327952Sdim /// Traverse each BB of the function and call 470327952Sdim /// InstructionVerifier::verifyInstruction for each possibly invalid 471327952Sdim /// instruction. 472327952Sdim /// It destructively modifies GCPtrTracker so it's passed via rvalue reference 473327952Sdim /// in order to prohibit further usages of GCPtrTracker as it'll be in 474327952Sdim /// inconsistent state. 475327952Sdim static void verifyFunction(GCPtrTracker &&Tracker, 476327952Sdim InstructionVerifier &Verifier); 477327952Sdim 478341825Sdim /// Returns true for reachable and live blocks. 479341825Sdim bool isMapped(const BasicBlock *BB) const { 480341825Sdim return BlockMap.find(BB) != BlockMap.end(); 481341825Sdim } 482341825Sdim 483327952Sdimprivate: 484327952Sdim /// Returns true if the instruction may be safely skipped during verification. 485327952Sdim bool instructionMayBeSkipped(const Instruction *I) const; 486327952Sdim 487327952Sdim /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for 488327952Sdim /// each of them until it converges. 489327952Sdim void recalculateBBsStates(); 490327952Sdim 491327952Sdim /// Remove from Contribution all defs that legally produce unrelocated 492327952Sdim /// pointers and saves them to ValidUnrelocatedDefs. 493327952Sdim /// Though Contribution should belong to BBS it is passed separately with 494327952Sdim /// different const-modifier in order to emphasize (and guarantee) that only 495327952Sdim /// Contribution will be changed. 496327952Sdim /// Returns true if Contribution was changed otherwise false. 497327952Sdim bool removeValidUnrelocatedDefs(const BasicBlock *BB, 498327952Sdim const BasicBlockState *BBS, 499327952Sdim AvailableValueSet &Contribution); 500327952Sdim 501327952Sdim /// Gather all the definitions dominating the start of BB into Result. This is 502327952Sdim /// simply the defs introduced by every dominating basic block and the 503327952Sdim /// function arguments. 504327952Sdim void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result, 505327952Sdim const DominatorTree &DT); 506327952Sdim 507327952Sdim /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS, 508327952Sdim /// which is the BasicBlockState for BB. 509327952Sdim /// ContributionChanged is set when the verifier runs for the first time 510327952Sdim /// (in this case Contribution was changed from 'empty' to its initial state) 511327952Sdim /// or when Contribution of this BB was changed since last computation. 512327952Sdim static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS, 513327952Sdim bool ContributionChanged); 514327952Sdim 515327952Sdim /// Model the effect of an instruction on the set of available values. 516327952Sdim static void transferInstruction(const Instruction &I, bool &Cleared, 517327952Sdim AvailableValueSet &Available); 518327952Sdim}; 519327952Sdim 520327952Sdim/// It is a visitor for GCPtrTracker::verifyFunction. It decides if the 521327952Sdim/// instruction (which uses heap reference) is legal or not, given our safepoint 522327952Sdim/// semantics. 523327952Sdimclass InstructionVerifier { 524327952Sdim bool AnyInvalidUses = false; 525327952Sdim 526327952Sdimpublic: 527327952Sdim void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I, 528327952Sdim const AvailableValueSet &AvailableSet); 529327952Sdim 530327952Sdim bool hasAnyInvalidUses() const { return AnyInvalidUses; } 531327952Sdim 532327952Sdimprivate: 533327952Sdim void reportInvalidUse(const Value &V, const Instruction &I); 534327952Sdim}; 535327952Sdim} // end anonymous namespace 536327952Sdim 537341825SdimGCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT, 538341825Sdim const CFGDeadness &CD) : F(F), CD(CD) { 539341825Sdim // Calculate Contribution of each live BB. 540341825Sdim // Allocate BB states for live blocks. 541341825Sdim for (const BasicBlock &BB : F) 542341825Sdim if (!CD.isDeadBlock(&BB)) { 543341825Sdim BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState; 544341825Sdim for (const auto &I : BB) 545341825Sdim transferInstruction(I, BBS->Cleared, BBS->Contribution); 546341825Sdim BlockMap[&BB] = BBS; 547341825Sdim } 548320957Sdim 549327952Sdim // Initialize AvailableIn/Out sets of each BB using only information about 550327952Sdim // dominating BBs. 551320957Sdim for (auto &BBI : BlockMap) { 552327952Sdim gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT); 553327952Sdim transferBlock(BBI.first, *BBI.second, true); 554320957Sdim } 555320957Sdim 556327952Sdim // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out 557327952Sdim // sets of each BB until it converges. If any def is proved to be an 558327952Sdim // unrelocated pointer, it will be removed from all BBSs. 559327952Sdim recalculateBBsStates(); 560327952Sdim} 561327952Sdim 562327952SdimBasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) { 563327952Sdim auto it = BlockMap.find(BB); 564341825Sdim return it != BlockMap.end() ? it->second : nullptr; 565327952Sdim} 566327952Sdim 567327952Sdimconst BasicBlockState *GCPtrTracker::getBasicBlockState( 568327952Sdim const BasicBlock *BB) const { 569327952Sdim return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB); 570327952Sdim} 571327952Sdim 572327952Sdimbool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const { 573327952Sdim // Poisoned defs are skipped since they are always safe by itself by 574327952Sdim // definition (for details see comment to this class). 575327952Sdim return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I); 576327952Sdim} 577327952Sdim 578327952Sdimvoid GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker, 579327952Sdim InstructionVerifier &Verifier) { 580327952Sdim // We need RPO here to a) report always the first error b) report errors in 581327952Sdim // same order from run to run. 582327952Sdim ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F); 583327952Sdim for (const BasicBlock *BB : RPOT) { 584327952Sdim BasicBlockState *BBS = Tracker.getBasicBlockState(BB); 585341825Sdim if (!BBS) 586341825Sdim continue; 587341825Sdim 588327952Sdim // We destructively modify AvailableIn as we traverse the block instruction 589327952Sdim // by instruction. 590327952Sdim AvailableValueSet &AvailableSet = BBS->AvailableIn; 591327952Sdim for (const Instruction &I : *BB) { 592327952Sdim if (Tracker.instructionMayBeSkipped(&I)) 593327952Sdim continue; // This instruction shouldn't be added to AvailableSet. 594327952Sdim 595327952Sdim Verifier.verifyInstruction(&Tracker, I, AvailableSet); 596327952Sdim 597327952Sdim // Model the effect of current instruction on AvailableSet to keep the set 598327952Sdim // relevant at each point of BB. 599327952Sdim bool Cleared = false; 600327952Sdim transferInstruction(I, Cleared, AvailableSet); 601327952Sdim (void)Cleared; 602327952Sdim } 603327952Sdim } 604327952Sdim} 605327952Sdim 606327952Sdimvoid GCPtrTracker::recalculateBBsStates() { 607320957Sdim SetVector<const BasicBlock *> Worklist; 608327952Sdim // TODO: This order is suboptimal, it's better to replace it with priority 609327952Sdim // queue where priority is RPO number of BB. 610320957Sdim for (auto &BBI : BlockMap) 611320957Sdim Worklist.insert(BBI.first); 612320957Sdim 613327952Sdim // This loop iterates the AvailableIn/Out sets until it converges. 614320957Sdim // The AvailableIn and AvailableOut sets decrease as we iterate. 615320957Sdim while (!Worklist.empty()) { 616320957Sdim const BasicBlock *BB = Worklist.pop_back_val(); 617341825Sdim BasicBlockState *BBS = getBasicBlockState(BB); 618341825Sdim if (!BBS) 619341825Sdim continue; // Ignore dead successors. 620320957Sdim 621320957Sdim size_t OldInCount = BBS->AvailableIn.size(); 622341825Sdim for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { 623341825Sdim const BasicBlock *PBB = *PredIt; 624341825Sdim BasicBlockState *PBBS = getBasicBlockState(PBB); 625341825Sdim if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt))) 626341825Sdim set_intersect(BBS->AvailableIn, PBBS->AvailableOut); 627341825Sdim } 628320957Sdim 629327952Sdim assert(OldInCount >= BBS->AvailableIn.size() && "invariant!"); 630327952Sdim 631327952Sdim bool InputsChanged = OldInCount != BBS->AvailableIn.size(); 632327952Sdim bool ContributionChanged = 633327952Sdim removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution); 634327952Sdim if (!InputsChanged && !ContributionChanged) 635320957Sdim continue; 636320957Sdim 637320957Sdim size_t OldOutCount = BBS->AvailableOut.size(); 638327952Sdim transferBlock(BB, *BBS, ContributionChanged); 639320957Sdim if (OldOutCount != BBS->AvailableOut.size()) { 640320957Sdim assert(OldOutCount > BBS->AvailableOut.size() && "invariant!"); 641320957Sdim Worklist.insert(succ_begin(BB), succ_end(BB)); 642320957Sdim } 643320957Sdim } 644327952Sdim} 645320957Sdim 646327952Sdimbool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB, 647327952Sdim const BasicBlockState *BBS, 648327952Sdim AvailableValueSet &Contribution) { 649327952Sdim assert(&BBS->Contribution == &Contribution && 650327952Sdim "Passed Contribution should be from the passed BasicBlockState!"); 651327952Sdim AvailableValueSet AvailableSet = BBS->AvailableIn; 652327952Sdim bool ContributionChanged = false; 653327952Sdim // For explanation why instructions are processed this way see 654327952Sdim // "Rules of deriving" in the comment to this class. 655327952Sdim for (const Instruction &I : *BB) { 656327952Sdim bool ValidUnrelocatedPointerDef = false; 657327952Sdim bool PoisonedPointerDef = false; 658327952Sdim // TODO: `select` instructions should be handled here too. 659327952Sdim if (const PHINode *PN = dyn_cast<PHINode>(&I)) { 660327952Sdim if (containsGCPtrType(PN->getType())) { 661327952Sdim // If both is true, output is poisoned. 662327952Sdim bool HasRelocatedInputs = false; 663327952Sdim bool HasUnrelocatedInputs = false; 664327952Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 665327952Sdim const BasicBlock *InBB = PN->getIncomingBlock(i); 666341825Sdim if (!isMapped(InBB) || 667341825Sdim !CD.hasLiveIncomingEdge(PN, InBB)) 668341825Sdim continue; // Skip dead block or dead edge. 669341825Sdim 670327952Sdim const Value *InValue = PN->getIncomingValue(i); 671320957Sdim 672327952Sdim if (isNotExclusivelyConstantDerived(InValue)) { 673327952Sdim if (isValuePoisoned(InValue)) { 674327952Sdim // If any of inputs is poisoned, output is always poisoned too. 675327952Sdim HasRelocatedInputs = true; 676327952Sdim HasUnrelocatedInputs = true; 677327952Sdim break; 678327952Sdim } 679327952Sdim if (BlockMap[InBB]->AvailableOut.count(InValue)) 680327952Sdim HasRelocatedInputs = true; 681327952Sdim else 682327952Sdim HasUnrelocatedInputs = true; 683327952Sdim } 684327952Sdim } 685327952Sdim if (HasUnrelocatedInputs) { 686327952Sdim if (HasRelocatedInputs) 687327952Sdim PoisonedPointerDef = true; 688327952Sdim else 689327952Sdim ValidUnrelocatedPointerDef = true; 690327952Sdim } 691327952Sdim } 692327952Sdim } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) && 693327952Sdim containsGCPtrType(I.getType())) { 694327952Sdim // GEP/bitcast of unrelocated pointer is legal by itself but this def 695327952Sdim // shouldn't appear in any AvailableSet. 696327952Sdim for (const Value *V : I.operands()) 697327952Sdim if (containsGCPtrType(V->getType()) && 698327952Sdim isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) { 699327952Sdim if (isValuePoisoned(V)) 700327952Sdim PoisonedPointerDef = true; 701327952Sdim else 702327952Sdim ValidUnrelocatedPointerDef = true; 703327952Sdim break; 704327952Sdim } 705327952Sdim } 706327952Sdim assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) && 707327952Sdim "Value cannot be both unrelocated and poisoned!"); 708327952Sdim if (ValidUnrelocatedPointerDef) { 709327952Sdim // Remove def of unrelocated pointer from Contribution of this BB and 710327952Sdim // trigger update of all its successors. 711327952Sdim Contribution.erase(&I); 712327952Sdim PoisonedDefs.erase(&I); 713327952Sdim ValidUnrelocatedDefs.insert(&I); 714341825Sdim LLVM_DEBUG(dbgs() << "Removing urelocated " << I 715341825Sdim << " from Contribution of " << BB->getName() << "\n"); 716327952Sdim ContributionChanged = true; 717327952Sdim } else if (PoisonedPointerDef) { 718327952Sdim // Mark pointer as poisoned, remove its def from Contribution and trigger 719327952Sdim // update of all successors. 720327952Sdim Contribution.erase(&I); 721327952Sdim PoisonedDefs.insert(&I); 722341825Sdim LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of " 723341825Sdim << BB->getName() << "\n"); 724327952Sdim ContributionChanged = true; 725327952Sdim } else { 726327952Sdim bool Cleared = false; 727327952Sdim transferInstruction(I, Cleared, AvailableSet); 728327952Sdim (void)Cleared; 729327952Sdim } 730327952Sdim } 731327952Sdim return ContributionChanged; 732327952Sdim} 733320957Sdim 734327952Sdimvoid GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB, 735327952Sdim AvailableValueSet &Result, 736327952Sdim const DominatorTree &DT) { 737327952Sdim DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)]; 738320957Sdim 739341825Sdim assert(DTN && "Unreachable blocks are ignored"); 740327952Sdim while (DTN->getIDom()) { 741327952Sdim DTN = DTN->getIDom(); 742341825Sdim auto BBS = getBasicBlockState(DTN->getBlock()); 743341825Sdim assert(BBS && "immediate dominator cannot be dead for a live block"); 744341825Sdim const auto &Defs = BBS->Contribution; 745327952Sdim Result.insert(Defs.begin(), Defs.end()); 746327952Sdim // If this block is 'Cleared', then nothing LiveIn to this block can be 747327952Sdim // available after this block completes. Note: This turns out to be 748327952Sdim // really important for reducing memory consuption of the initial available 749327952Sdim // sets and thus peak memory usage by this verifier. 750341825Sdim if (BBS->Cleared) 751327952Sdim return; 752327952Sdim } 753320957Sdim 754327952Sdim for (const Argument &A : BB->getParent()->args()) 755327952Sdim if (containsGCPtrType(A.getType())) 756327952Sdim Result.insert(&A); 757327952Sdim} 758320957Sdim 759327952Sdimvoid GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS, 760327952Sdim bool ContributionChanged) { 761327952Sdim const AvailableValueSet &AvailableIn = BBS.AvailableIn; 762327952Sdim AvailableValueSet &AvailableOut = BBS.AvailableOut; 763320957Sdim 764327952Sdim if (BBS.Cleared) { 765327952Sdim // AvailableOut will change only when Contribution changed. 766327952Sdim if (ContributionChanged) 767327952Sdim AvailableOut = BBS.Contribution; 768327952Sdim } else { 769327952Sdim // Otherwise, we need to reduce the AvailableOut set by things which are no 770327952Sdim // longer in our AvailableIn 771327952Sdim AvailableValueSet Temp = BBS.Contribution; 772327952Sdim set_union(Temp, AvailableIn); 773327952Sdim AvailableOut = std::move(Temp); 774327952Sdim } 775327952Sdim 776341825Sdim LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from "; 777341825Sdim PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end()); 778341825Sdim dbgs() << " to "; 779341825Sdim PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end()); 780341825Sdim dbgs() << "\n";); 781327952Sdim} 782327952Sdim 783327952Sdimvoid GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared, 784327952Sdim AvailableValueSet &Available) { 785327952Sdim if (isStatepoint(I)) { 786327952Sdim Cleared = true; 787327952Sdim Available.clear(); 788327952Sdim } else if (containsGCPtrType(I.getType())) 789327952Sdim Available.insert(&I); 790327952Sdim} 791327952Sdim 792327952Sdimvoid InstructionVerifier::verifyInstruction( 793327952Sdim const GCPtrTracker *Tracker, const Instruction &I, 794327952Sdim const AvailableValueSet &AvailableSet) { 795327952Sdim if (const PHINode *PN = dyn_cast<PHINode>(&I)) { 796327952Sdim if (containsGCPtrType(PN->getType())) 797327952Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 798327952Sdim const BasicBlock *InBB = PN->getIncomingBlock(i); 799341825Sdim const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB); 800341825Sdim if (!InBBS || 801341825Sdim !Tracker->hasLiveIncomingEdge(PN, InBB)) 802341825Sdim continue; // Skip dead block or dead edge. 803341825Sdim 804327952Sdim const Value *InValue = PN->getIncomingValue(i); 805327952Sdim 806327952Sdim if (isNotExclusivelyConstantDerived(InValue) && 807341825Sdim !InBBS->AvailableOut.count(InValue)) 808327952Sdim reportInvalidUse(*InValue, *PN); 809320957Sdim } 810327952Sdim } else if (isa<CmpInst>(I) && 811327952Sdim containsGCPtrType(I.getOperand(0)->getType())) { 812327952Sdim Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 813327952Sdim enum BaseType baseTyLHS = getBaseType(LHS), 814327952Sdim baseTyRHS = getBaseType(RHS); 815320957Sdim 816327952Sdim // Returns true if LHS and RHS are unrelocated pointers and they are 817327952Sdim // valid unrelocated uses. 818327952Sdim auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS, 819327952Sdim &LHS, &RHS] () { 820327952Sdim // A cmp instruction has valid unrelocated pointer operands only if 821327952Sdim // both operands are unrelocated pointers. 822327952Sdim // In the comparison between two pointers, if one is an unrelocated 823327952Sdim // use, the other *should be* an unrelocated use, for this 824327952Sdim // instruction to contain valid unrelocated uses. This unrelocated 825327952Sdim // use can be a null constant as well, or another unrelocated 826327952Sdim // pointer. 827327952Sdim if (AvailableSet.count(LHS) || AvailableSet.count(RHS)) 828327952Sdim return false; 829327952Sdim // Constant pointers (that are not exclusively null) may have 830327952Sdim // meaning in different VMs, so we cannot reorder the compare 831327952Sdim // against constant pointers before the safepoint. In other words, 832327952Sdim // comparison of an unrelocated use against a non-null constant 833327952Sdim // maybe invalid. 834327952Sdim if ((baseTyLHS == BaseType::ExclusivelySomeConstant && 835327952Sdim baseTyRHS == BaseType::NonConstant) || 836327952Sdim (baseTyLHS == BaseType::NonConstant && 837327952Sdim baseTyRHS == BaseType::ExclusivelySomeConstant)) 838327952Sdim return false; 839327952Sdim 840327952Sdim // If one of pointers is poisoned and other is not exclusively derived 841327952Sdim // from null it is an invalid expression: it produces poisoned result 842327952Sdim // and unless we want to track all defs (not only gc pointers) the only 843327952Sdim // option is to prohibit such instructions. 844327952Sdim if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) || 845327952Sdim (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull)) 846327952Sdim return false; 847327952Sdim 848327952Sdim // All other cases are valid cases enumerated below: 849327952Sdim // 1. Comparison between an exclusively derived null pointer and a 850327952Sdim // constant base pointer. 851327952Sdim // 2. Comparison between an exclusively derived null pointer and a 852327952Sdim // non-constant unrelocated base pointer. 853327952Sdim // 3. Comparison between 2 unrelocated pointers. 854327952Sdim // 4. Comparison between a pointer exclusively derived from null and a 855327952Sdim // non-constant poisoned pointer. 856327952Sdim return true; 857327952Sdim }; 858327952Sdim if (!hasValidUnrelocatedUse()) { 859327952Sdim // Print out all non-constant derived pointers that are unrelocated 860327952Sdim // uses, which are invalid. 861327952Sdim if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS)) 862327952Sdim reportInvalidUse(*LHS, I); 863327952Sdim if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS)) 864327952Sdim reportInvalidUse(*RHS, I); 865320957Sdim } 866327952Sdim } else { 867327952Sdim for (const Value *V : I.operands()) 868327952Sdim if (containsGCPtrType(V->getType()) && 869327952Sdim isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) 870327952Sdim reportInvalidUse(*V, I); 871320957Sdim } 872327952Sdim} 873320957Sdim 874327952Sdimvoid InstructionVerifier::reportInvalidUse(const Value &V, 875327952Sdim const Instruction &I) { 876327952Sdim errs() << "Illegal use of unrelocated value found!\n"; 877327952Sdim errs() << "Def: " << V << "\n"; 878327952Sdim errs() << "Use: " << I << "\n"; 879327952Sdim if (!PrintOnly) 880327952Sdim abort(); 881327952Sdim AnyInvalidUses = true; 882327952Sdim} 883327952Sdim 884341825Sdimstatic void Verify(const Function &F, const DominatorTree &DT, 885341825Sdim const CFGDeadness &CD) { 886341825Sdim LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() 887341825Sdim << "\n"); 888327952Sdim if (PrintOnly) 889327952Sdim dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n"; 890327952Sdim 891341825Sdim GCPtrTracker Tracker(F, DT, CD); 892327952Sdim 893327952Sdim // We now have all the information we need to decide if the use of a heap 894327952Sdim // reference is legal or not, given our safepoint semantics. 895327952Sdim 896327952Sdim InstructionVerifier Verifier; 897327952Sdim GCPtrTracker::verifyFunction(std::move(Tracker), Verifier); 898327952Sdim 899327952Sdim if (PrintOnly && !Verifier.hasAnyInvalidUses()) { 900320957Sdim dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName() 901320957Sdim << "\n"; 902320957Sdim } 903320957Sdim} 904