1 //===-- PolymorphicOpConversion.cpp ---------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "flang/Lower/BuiltinModules.h" 10 #include "flang/Optimizer/Builder/Todo.h" 11 #include "flang/Optimizer/Dialect/FIRDialect.h" 12 #include "flang/Optimizer/Dialect/FIROps.h" 13 #include "flang/Optimizer/Dialect/FIROpsSupport.h" 14 #include "flang/Optimizer/Dialect/FIRType.h" 15 #include "flang/Optimizer/Dialect/Support/FIRContext.h" 16 #include "flang/Optimizer/Dialect/Support/KindMapping.h" 17 #include "flang/Optimizer/Support/InternalNames.h" 18 #include "flang/Optimizer/Support/TypeCode.h" 19 #include "flang/Optimizer/Support/Utils.h" 20 #include "flang/Optimizer/Transforms/Passes.h" 21 #include "flang/Runtime/derived-api.h" 22 #include "flang/Semantics/runtime-type-info.h" 23 #include "mlir/Dialect/Affine/IR/AffineOps.h" 24 #include "mlir/Dialect/Arith/IR/Arith.h" 25 #include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h" 26 #include "mlir/Dialect/Func/IR/FuncOps.h" 27 #include "mlir/IR/BuiltinOps.h" 28 #include "mlir/Pass/Pass.h" 29 #include "mlir/Transforms/DialectConversion.h" 30 #include "llvm/ADT/SmallSet.h" 31 #include "llvm/Support/CommandLine.h" 32 33 namespace fir { 34 #define GEN_PASS_DEF_POLYMORPHICOPCONVERSION 35 #include "flang/Optimizer/Transforms/Passes.h.inc" 36 } // namespace fir 37 38 using namespace fir; 39 using namespace mlir; 40 41 namespace { 42 43 /// SelectTypeOp converted to an if-then-else chain 44 /// 45 /// This lowers the test conditions to calls into the runtime. 46 class SelectTypeConv : public OpConversionPattern<fir::SelectTypeOp> { 47 public: 48 using OpConversionPattern<fir::SelectTypeOp>::OpConversionPattern; 49 50 SelectTypeConv(mlir::MLIRContext *ctx) 51 : mlir::OpConversionPattern<fir::SelectTypeOp>(ctx) {} 52 53 llvm::LogicalResult 54 matchAndRewrite(fir::SelectTypeOp selectType, OpAdaptor adaptor, 55 mlir::ConversionPatternRewriter &rewriter) const override; 56 57 private: 58 // Generate comparison of type descriptor addresses. 59 mlir::Value genTypeDescCompare(mlir::Location loc, mlir::Value selector, 60 mlir::Type ty, mlir::ModuleOp mod, 61 mlir::PatternRewriter &rewriter) const; 62 63 llvm::LogicalResult genTypeLadderStep(mlir::Location loc, 64 mlir::Value selector, 65 mlir::Attribute attr, mlir::Block *dest, 66 std::optional<mlir::ValueRange> destOps, 67 mlir::ModuleOp mod, 68 mlir::PatternRewriter &rewriter, 69 fir::KindMapping &kindMap) const; 70 71 llvm::SmallSet<llvm::StringRef, 4> collectAncestors(fir::TypeInfoOp dt, 72 mlir::ModuleOp mod) const; 73 }; 74 75 /// Lower `fir.dispatch` operation. A virtual call to a method in a dispatch 76 /// table. 77 struct DispatchOpConv : public OpConversionPattern<fir::DispatchOp> { 78 using OpConversionPattern<fir::DispatchOp>::OpConversionPattern; 79 80 DispatchOpConv(mlir::MLIRContext *ctx, const BindingTables &bindingTables) 81 : mlir::OpConversionPattern<fir::DispatchOp>(ctx), 82 bindingTables(bindingTables) {} 83 84 llvm::LogicalResult 85 matchAndRewrite(fir::DispatchOp dispatch, OpAdaptor adaptor, 86 mlir::ConversionPatternRewriter &rewriter) const override { 87 mlir::Location loc = dispatch.getLoc(); 88 89 if (bindingTables.empty()) 90 return emitError(loc) << "no binding tables found"; 91 92 // Get derived type information. 93 mlir::Type declaredType = 94 fir::getDerivedType(dispatch.getObject().getType().getEleTy()); 95 assert(mlir::isa<fir::RecordType>(declaredType) && "expecting fir.type"); 96 auto recordType = mlir::dyn_cast<fir::RecordType>(declaredType); 97 98 // Lookup for the binding table. 99 auto bindingsIter = bindingTables.find(recordType.getName()); 100 if (bindingsIter == bindingTables.end()) 101 return emitError(loc) 102 << "cannot find binding table for " << recordType.getName(); 103 104 // Lookup for the binding. 105 const BindingTable &bindingTable = bindingsIter->second; 106 auto bindingIter = bindingTable.find(dispatch.getMethod()); 107 if (bindingIter == bindingTable.end()) 108 return emitError(loc) 109 << "cannot find binding for " << dispatch.getMethod(); 110 unsigned bindingIdx = bindingIter->second; 111 112 mlir::Value passedObject = dispatch.getObject(); 113 114 auto module = dispatch.getOperation()->getParentOfType<mlir::ModuleOp>(); 115 Type typeDescTy; 116 std::string typeDescName = 117 NameUniquer::getTypeDescriptorName(recordType.getName()); 118 if (auto global = module.lookupSymbol<fir::GlobalOp>(typeDescName)) { 119 typeDescTy = global.getType(); 120 } 121 122 // clang-format off 123 // Before: 124 // fir.dispatch "proc1"(%11 : 125 // !fir.class<!fir.heap<!fir.type<_QMpolyTp1{a:i32,b:i32}>>>) 126 127 // After: 128 // %12 = fir.box_tdesc %11 : (!fir.class<!fir.heap<!fir.type<_QMpolyTp1{a:i32,b:i32}>>>) -> !fir.tdesc<none> 129 // %13 = fir.convert %12 : (!fir.tdesc<none>) -> !fir.ref<!fir.type<_QM__fortran_type_infoTderivedtype>> 130 // %14 = fir.field_index binding, !fir.type<_QM__fortran_type_infoTderivedtype> 131 // %15 = fir.coordinate_of %13, %14 : (!fir.ref<!fir.type<_QM__fortran_type_infoTderivedtype>>, !fir.field) -> !fir.ref<!fir.box<!fir.ptr<!fir.array<?x!fir.type<_QM__fortran_type_infoTbinding>>>>> 132 // %bindings = fir.load %15 : !fir.ref<!fir.box<!fir.ptr<!fir.array<?x!fir.type<_QM__fortran_type_infoTbinding>>>>> 133 // %16 = fir.box_addr %bindings : (!fir.box<!fir.ptr<!fir.array<?x!fir.type<_QM__fortran_type_infoTbinding>>>>) -> !fir.ptr<!fir.array<?x!fir.type<_QM__fortran_type_infoTbinding>>> 134 // %17 = fir.coordinate_of %16, %c0 : (!fir.ptr<!fir.array<?x!fir.type<_QM__fortran_type_infoTbinding>>>, index) -> !fir.ref<!fir.type<_QM__fortran_type_infoTbinding>> 135 // %18 = fir.field_index proc, !fir.type<_QM__fortran_type_infoTbinding> 136 // %19 = fir.coordinate_of %17, %18 : (!fir.ref<!fir.type<_QM__fortran_type_infoTbinding>>, !fir.field) -> !fir.ref<!fir.type<_QM__fortran_builtinsT__builtin_c_funptr>> 137 // %20 = fir.field_index __address, !fir.type<_QM__fortran_builtinsT__builtin_c_funptr> 138 // %21 = fir.coordinate_of %19, %20 : (!fir.ref<!fir.type<_QM__fortran_builtinsT__builtin_c_funptr>>, !fir.field) -> !fir.ref<i64> 139 // %22 = fir.load %21 : !fir.ref<i64> 140 // %23 = fir.convert %22 : (i64) -> (() -> ()) 141 // fir.call %23() : () -> () 142 // clang-format on 143 144 // Load the descriptor. 145 mlir::Type fieldTy = fir::FieldType::get(rewriter.getContext()); 146 mlir::Type tdescType = 147 fir::TypeDescType::get(mlir::NoneType::get(rewriter.getContext())); 148 mlir::Value boxDesc = 149 rewriter.create<fir::BoxTypeDescOp>(loc, tdescType, passedObject); 150 boxDesc = rewriter.create<fir::ConvertOp>( 151 loc, fir::ReferenceType::get(typeDescTy), boxDesc); 152 153 // Load the bindings descriptor. 154 auto bindingsCompName = Fortran::semantics::bindingDescCompName; 155 fir::RecordType typeDescRecTy = mlir::cast<fir::RecordType>(typeDescTy); 156 mlir::Value field = rewriter.create<fir::FieldIndexOp>( 157 loc, fieldTy, bindingsCompName, typeDescRecTy, mlir::ValueRange{}); 158 mlir::Type coorTy = 159 fir::ReferenceType::get(typeDescRecTy.getType(bindingsCompName)); 160 mlir::Value bindingBoxAddr = 161 rewriter.create<fir::CoordinateOp>(loc, coorTy, boxDesc, field); 162 mlir::Value bindingBox = rewriter.create<fir::LoadOp>(loc, bindingBoxAddr); 163 164 // Load the correct binding. 165 mlir::Value bindings = rewriter.create<fir::BoxAddrOp>(loc, bindingBox); 166 fir::RecordType bindingTy = fir::unwrapIfDerived( 167 mlir::cast<fir::BaseBoxType>(bindingBox.getType())); 168 mlir::Type bindingAddrTy = fir::ReferenceType::get(bindingTy); 169 mlir::Value bindingIdxVal = rewriter.create<mlir::arith::ConstantOp>( 170 loc, rewriter.getIndexType(), rewriter.getIndexAttr(bindingIdx)); 171 mlir::Value bindingAddr = rewriter.create<fir::CoordinateOp>( 172 loc, bindingAddrTy, bindings, bindingIdxVal); 173 174 // Get the function pointer. 175 auto procCompName = Fortran::semantics::procCompName; 176 mlir::Value procField = rewriter.create<fir::FieldIndexOp>( 177 loc, fieldTy, procCompName, bindingTy, mlir::ValueRange{}); 178 fir::RecordType procTy = 179 mlir::cast<fir::RecordType>(bindingTy.getType(procCompName)); 180 mlir::Type procRefTy = fir::ReferenceType::get(procTy); 181 mlir::Value procRef = rewriter.create<fir::CoordinateOp>( 182 loc, procRefTy, bindingAddr, procField); 183 184 auto addressFieldName = Fortran::lower::builtin::cptrFieldName; 185 mlir::Value addressField = rewriter.create<fir::FieldIndexOp>( 186 loc, fieldTy, addressFieldName, procTy, mlir::ValueRange{}); 187 mlir::Type addressTy = procTy.getType(addressFieldName); 188 mlir::Type addressRefTy = fir::ReferenceType::get(addressTy); 189 mlir::Value addressRef = rewriter.create<fir::CoordinateOp>( 190 loc, addressRefTy, procRef, addressField); 191 mlir::Value address = rewriter.create<fir::LoadOp>(loc, addressRef); 192 193 // Get the function type. 194 llvm::SmallVector<mlir::Type> argTypes; 195 for (mlir::Value operand : dispatch.getArgs()) 196 argTypes.push_back(operand.getType()); 197 llvm::SmallVector<mlir::Type> resTypes; 198 if (!dispatch.getResults().empty()) 199 resTypes.push_back(dispatch.getResults()[0].getType()); 200 201 mlir::Type funTy = 202 mlir::FunctionType::get(rewriter.getContext(), argTypes, resTypes); 203 mlir::Value funcPtr = rewriter.create<fir::ConvertOp>(loc, funTy, address); 204 205 // Make the call. 206 llvm::SmallVector<mlir::Value> args{funcPtr}; 207 args.append(dispatch.getArgs().begin(), dispatch.getArgs().end()); 208 rewriter.replaceOpWithNewOp<fir::CallOp>(dispatch, resTypes, nullptr, args, 209 dispatch.getProcedureAttrsAttr()); 210 return mlir::success(); 211 } 212 213 private: 214 BindingTables bindingTables; 215 }; 216 217 /// Convert FIR structured control flow ops to CFG ops. 218 class PolymorphicOpConversion 219 : public fir::impl::PolymorphicOpConversionBase<PolymorphicOpConversion> { 220 public: 221 llvm::LogicalResult initialize(mlir::MLIRContext *ctx) override { 222 return mlir::success(); 223 } 224 225 void runOnOperation() override { 226 auto *context = &getContext(); 227 mlir::ModuleOp mod = getOperation(); 228 mlir::RewritePatternSet patterns(context); 229 230 BindingTables bindingTables; 231 buildBindingTables(bindingTables, mod); 232 233 patterns.insert<SelectTypeConv>(context); 234 patterns.insert<DispatchOpConv>(context, bindingTables); 235 mlir::ConversionTarget target(*context); 236 target.addLegalDialect<mlir::affine::AffineDialect, 237 mlir::cf::ControlFlowDialect, FIROpsDialect, 238 mlir::func::FuncDialect>(); 239 240 // apply the patterns 241 target.addIllegalOp<SelectTypeOp>(); 242 target.addIllegalOp<DispatchOp>(); 243 target.markUnknownOpDynamicallyLegal([](Operation *) { return true; }); 244 if (mlir::failed(mlir::applyPartialConversion(getOperation(), target, 245 std::move(patterns)))) { 246 mlir::emitError(mlir::UnknownLoc::get(context), 247 "error in converting to CFG\n"); 248 signalPassFailure(); 249 } 250 } 251 }; 252 } // namespace 253 254 llvm::LogicalResult SelectTypeConv::matchAndRewrite( 255 fir::SelectTypeOp selectType, OpAdaptor adaptor, 256 mlir::ConversionPatternRewriter &rewriter) const { 257 auto operands = adaptor.getOperands(); 258 auto typeGuards = selectType.getCases(); 259 unsigned typeGuardNum = typeGuards.size(); 260 auto selector = selectType.getSelector(); 261 auto loc = selectType.getLoc(); 262 auto mod = selectType.getOperation()->getParentOfType<mlir::ModuleOp>(); 263 fir::KindMapping kindMap = fir::getKindMapping(mod); 264 265 // Order type guards so the condition and branches are done to respect the 266 // Execution of SELECT TYPE construct as described in the Fortran 2018 267 // standard 11.1.11.2 point 4. 268 // 1. If a TYPE IS type guard statement matches the selector, the block 269 // following that statement is executed. 270 // 2. Otherwise, if exactly one CLASS IS type guard statement matches the 271 // selector, the block following that statement is executed. 272 // 3. Otherwise, if several CLASS IS type guard statements match the 273 // selector, one of these statements will inevitably specify a type that 274 // is an extension of all the types specified in the others; the block 275 // following that statement is executed. 276 // 4. Otherwise, if there is a CLASS DEFAULT type guard statement, the block 277 // following that statement is executed. 278 // 5. Otherwise, no block is executed. 279 280 llvm::SmallVector<unsigned> orderedTypeGuards; 281 llvm::SmallVector<unsigned> orderedClassIsGuards; 282 unsigned defaultGuard = typeGuardNum - 1; 283 284 // The following loop go through the type guards in the fir.select_type 285 // operation and sort them into two lists. 286 // - All the TYPE IS type guard are added in order to the orderedTypeGuards 287 // list. This list is used at the end to generate the if-then-else ladder. 288 // - CLASS IS type guard are added in a separate list. If a CLASS IS type 289 // guard type extends a type already present, the type guard is inserted 290 // before in the list to respect point 3. above. Otherwise it is just 291 // added in order at the end. 292 for (unsigned t = 0; t < typeGuardNum; ++t) { 293 if (auto a = mlir::dyn_cast<fir::ExactTypeAttr>(typeGuards[t])) { 294 orderedTypeGuards.push_back(t); 295 continue; 296 } 297 298 if (auto a = mlir::dyn_cast<fir::SubclassAttr>(typeGuards[t])) { 299 if (auto recTy = mlir::dyn_cast<fir::RecordType>(a.getType())) { 300 auto dt = mod.lookupSymbol<fir::TypeInfoOp>(recTy.getName()); 301 assert(dt && "dispatch table not found"); 302 llvm::SmallSet<llvm::StringRef, 4> ancestors = 303 collectAncestors(dt, mod); 304 if (!ancestors.empty()) { 305 auto it = orderedClassIsGuards.begin(); 306 while (it != orderedClassIsGuards.end()) { 307 fir::SubclassAttr sAttr = 308 mlir::dyn_cast<fir::SubclassAttr>(typeGuards[*it]); 309 if (auto ty = mlir::dyn_cast<fir::RecordType>(sAttr.getType())) { 310 if (ancestors.contains(ty.getName())) 311 break; 312 } 313 ++it; 314 } 315 if (it != orderedClassIsGuards.end()) { 316 // Parent type is present so place it before. 317 orderedClassIsGuards.insert(it, t); 318 continue; 319 } 320 } 321 } 322 orderedClassIsGuards.push_back(t); 323 } 324 } 325 orderedTypeGuards.append(orderedClassIsGuards); 326 orderedTypeGuards.push_back(defaultGuard); 327 assert(orderedTypeGuards.size() == typeGuardNum && 328 "ordered type guard size doesn't match number of type guards"); 329 330 for (unsigned idx : orderedTypeGuards) { 331 auto *dest = selectType.getSuccessor(idx); 332 std::optional<mlir::ValueRange> destOps = 333 selectType.getSuccessorOperands(operands, idx); 334 if (mlir::dyn_cast<mlir::UnitAttr>(typeGuards[idx])) 335 rewriter.replaceOpWithNewOp<mlir::cf::BranchOp>( 336 selectType, dest, destOps.value_or(mlir::ValueRange{})); 337 else if (mlir::failed(genTypeLadderStep(loc, selector, typeGuards[idx], 338 dest, destOps, mod, rewriter, 339 kindMap))) 340 return mlir::failure(); 341 } 342 return mlir::success(); 343 } 344 345 llvm::LogicalResult SelectTypeConv::genTypeLadderStep( 346 mlir::Location loc, mlir::Value selector, mlir::Attribute attr, 347 mlir::Block *dest, std::optional<mlir::ValueRange> destOps, 348 mlir::ModuleOp mod, mlir::PatternRewriter &rewriter, 349 fir::KindMapping &kindMap) const { 350 mlir::Value cmp; 351 // TYPE IS type guard comparison are all done inlined. 352 if (auto a = mlir::dyn_cast<fir::ExactTypeAttr>(attr)) { 353 if (fir::isa_trivial(a.getType()) || 354 mlir::isa<fir::CharacterType>(a.getType())) { 355 // For type guard statement with Intrinsic type spec the type code of 356 // the descriptor is compared. 357 int code = fir::getTypeCode(a.getType(), kindMap); 358 if (code == 0) 359 return mlir::emitError(loc) 360 << "type code unavailable for " << a.getType(); 361 mlir::Value typeCode = rewriter.create<mlir::arith::ConstantOp>( 362 loc, rewriter.getI8IntegerAttr(code)); 363 mlir::Value selectorTypeCode = rewriter.create<fir::BoxTypeCodeOp>( 364 loc, rewriter.getI8Type(), selector); 365 cmp = rewriter.create<mlir::arith::CmpIOp>( 366 loc, mlir::arith::CmpIPredicate::eq, selectorTypeCode, typeCode); 367 } else { 368 // Flang inline the kind parameter in the type descriptor so we can 369 // directly check if the type descriptor addresses are identical for 370 // the TYPE IS type guard statement. 371 mlir::Value res = 372 genTypeDescCompare(loc, selector, a.getType(), mod, rewriter); 373 if (!res) 374 return mlir::failure(); 375 cmp = res; 376 } 377 // CLASS IS type guard statement is done with a runtime call. 378 } else if (auto a = mlir::dyn_cast<fir::SubclassAttr>(attr)) { 379 // Retrieve the type descriptor from the type guard statement record type. 380 assert(mlir::isa<fir::RecordType>(a.getType()) && "expect fir.record type"); 381 fir::RecordType recTy = mlir::dyn_cast<fir::RecordType>(a.getType()); 382 std::string typeDescName = 383 fir::NameUniquer::getTypeDescriptorName(recTy.getName()); 384 auto typeDescGlobal = mod.lookupSymbol<fir::GlobalOp>(typeDescName); 385 auto typeDescAddr = rewriter.create<fir::AddrOfOp>( 386 loc, fir::ReferenceType::get(typeDescGlobal.getType()), 387 typeDescGlobal.getSymbol()); 388 mlir::Type typeDescTy = ReferenceType::get(rewriter.getNoneType()); 389 mlir::Value typeDesc = 390 rewriter.create<ConvertOp>(loc, typeDescTy, typeDescAddr); 391 392 // Prepare the selector descriptor for the runtime call. 393 mlir::Type descNoneTy = fir::BoxType::get(rewriter.getNoneType()); 394 mlir::Value descSelector = 395 rewriter.create<ConvertOp>(loc, descNoneTy, selector); 396 397 // Generate runtime call. 398 llvm::StringRef fctName = RTNAME_STRING(ClassIs); 399 mlir::func::FuncOp callee; 400 { 401 // Since conversion is done in parallel for each fir.select_type 402 // operation, the runtime function insertion must be threadsafe. 403 callee = 404 fir::createFuncOp(rewriter.getUnknownLoc(), mod, fctName, 405 rewriter.getFunctionType({descNoneTy, typeDescTy}, 406 rewriter.getI1Type())); 407 } 408 cmp = rewriter 409 .create<fir::CallOp>(loc, callee, 410 mlir::ValueRange{descSelector, typeDesc}) 411 .getResult(0); 412 } 413 414 auto *thisBlock = rewriter.getInsertionBlock(); 415 auto *newBlock = 416 rewriter.createBlock(dest->getParent(), mlir::Region::iterator(dest)); 417 rewriter.setInsertionPointToEnd(thisBlock); 418 if (destOps.has_value()) 419 rewriter.create<mlir::cf::CondBranchOp>(loc, cmp, dest, destOps.value(), 420 newBlock, std::nullopt); 421 else 422 rewriter.create<mlir::cf::CondBranchOp>(loc, cmp, dest, newBlock); 423 rewriter.setInsertionPointToEnd(newBlock); 424 return mlir::success(); 425 } 426 427 // Generate comparison of type descriptor addresses. 428 mlir::Value 429 SelectTypeConv::genTypeDescCompare(mlir::Location loc, mlir::Value selector, 430 mlir::Type ty, mlir::ModuleOp mod, 431 mlir::PatternRewriter &rewriter) const { 432 assert(mlir::isa<fir::RecordType>(ty) && "expect fir.record type"); 433 fir::RecordType recTy = mlir::dyn_cast<fir::RecordType>(ty); 434 std::string typeDescName = 435 fir::NameUniquer::getTypeDescriptorName(recTy.getName()); 436 auto typeDescGlobal = mod.lookupSymbol<fir::GlobalOp>(typeDescName); 437 if (!typeDescGlobal) 438 return {}; 439 auto typeDescAddr = rewriter.create<fir::AddrOfOp>( 440 loc, fir::ReferenceType::get(typeDescGlobal.getType()), 441 typeDescGlobal.getSymbol()); 442 auto intPtrTy = rewriter.getIndexType(); 443 mlir::Type tdescType = 444 fir::TypeDescType::get(mlir::NoneType::get(rewriter.getContext())); 445 mlir::Value selectorTdescAddr = 446 rewriter.create<fir::BoxTypeDescOp>(loc, tdescType, selector); 447 auto typeDescInt = 448 rewriter.create<fir::ConvertOp>(loc, intPtrTy, typeDescAddr); 449 auto selectorTdescInt = 450 rewriter.create<fir::ConvertOp>(loc, intPtrTy, selectorTdescAddr); 451 return rewriter.create<mlir::arith::CmpIOp>( 452 loc, mlir::arith::CmpIPredicate::eq, typeDescInt, selectorTdescInt); 453 } 454 455 llvm::SmallSet<llvm::StringRef, 4> 456 SelectTypeConv::collectAncestors(fir::TypeInfoOp dt, mlir::ModuleOp mod) const { 457 llvm::SmallSet<llvm::StringRef, 4> ancestors; 458 while (auto parentName = dt.getIfParentName()) { 459 ancestors.insert(*parentName); 460 dt = mod.lookupSymbol<fir::TypeInfoOp>(*parentName); 461 assert(dt && "parent type info not generated"); 462 } 463 return ancestors; 464 } 465