From 71d5a2540a98c81f5bcaeb48805e0e2881f530ef Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Sun, 16 Apr 2017 16:01:22 +0000 Subject: Vendor import of llvm trunk r300422: https://llvm.org/svn/llvm-project/llvm/trunk@300422 --- include/llvm/ADT/APFloat.h | 370 ++++--- include/llvm/ADT/APInt.h | 668 +++++------ include/llvm/ADT/APSInt.h | 3 - include/llvm/ADT/ArrayRef.h | 12 + include/llvm/ADT/BitVector.h | 43 +- include/llvm/ADT/BreadthFirstIterator.h | 164 +++ include/llvm/ADT/DenseMap.h | 13 +- include/llvm/ADT/DenseMapInfo.h | 18 + include/llvm/ADT/DenseSet.h | 27 +- include/llvm/ADT/DepthFirstIterator.h | 2 +- include/llvm/ADT/GraphTraits.h | 29 + include/llvm/ADT/None.h | 5 +- include/llvm/ADT/PointerUnion.h | 8 +- include/llvm/ADT/PostOrderIterator.h | 4 + include/llvm/ADT/STLExtras.h | 236 +++- include/llvm/ADT/ScopedHashTable.h | 4 +- include/llvm/ADT/SetVector.h | 8 +- include/llvm/ADT/SmallBitVector.h | 29 + include/llvm/ADT/SmallPtrSet.h | 57 +- include/llvm/ADT/SparseBitVector.h | 19 + include/llvm/ADT/StringExtras.h | 7 + include/llvm/ADT/StringMap.h | 110 +- include/llvm/ADT/StringRef.h | 10 +- include/llvm/ADT/Triple.h | 23 +- include/llvm/ADT/iterator.h | 34 +- include/llvm/Analysis/AliasAnalysis.h | 14 +- include/llvm/Analysis/AliasSetTracker.h | 7 +- include/llvm/Analysis/AssumptionCache.h | 21 +- include/llvm/Analysis/BasicAliasAnalysis.h | 18 + include/llvm/Analysis/BlockFrequencyInfo.h | 10 + include/llvm/Analysis/BlockFrequencyInfoImpl.h | 7 +- include/llvm/Analysis/BranchProbabilityInfo.h | 2 + include/llvm/Analysis/CFGPrinter.h | 3 +- include/llvm/Analysis/CGSCCPassManager.h | 1 + include/llvm/Analysis/CallGraph.h | 2 +- include/llvm/Analysis/ConstantFolding.h | 6 + include/llvm/Analysis/DominanceFrontier.h | 4 + include/llvm/Analysis/IndirectCallSiteVisitor.h | 12 +- include/llvm/Analysis/InlineCost.h | 6 + include/llvm/Analysis/InstructionSimplify.h | 12 +- include/llvm/Analysis/LazyBlockFrequencyInfo.h | 104 +- include/llvm/Analysis/LazyBranchProbabilityInfo.h | 12 + include/llvm/Analysis/LazyCallGraph.h | 493 +++++---- include/llvm/Analysis/LazyValueInfo.h | 15 +- include/llvm/Analysis/Loads.h | 31 +- include/llvm/Analysis/LoopAccessAnalysis.h | 37 +- include/llvm/Analysis/LoopInfo.h | 30 +- include/llvm/Analysis/LoopInfoImpl.h | 150 ++- include/llvm/Analysis/MemoryBuiltins.h | 43 +- include/llvm/Analysis/MemorySSA.h | 1155 ++++++++++++++++++++ include/llvm/Analysis/MemorySSAUpdater.h | 153 +++ include/llvm/Analysis/ObjectUtils.h | 42 + include/llvm/Analysis/OptimizationDiagnosticInfo.h | 150 +-- include/llvm/Analysis/PostDominators.h | 4 + include/llvm/Analysis/ProfileSummaryInfo.h | 16 +- include/llvm/Analysis/PtrUseVisitor.h | 5 +- include/llvm/Analysis/RegionInfo.h | 4 + include/llvm/Analysis/ScalarEvolution.h | 71 +- include/llvm/Analysis/ScalarEvolutionExpressions.h | 66 +- .../llvm/Analysis/ScalarEvolutionNormalization.h | 45 +- include/llvm/Analysis/TargetLibraryInfo.def | 2 +- include/llvm/Analysis/TargetLibraryInfo.h | 78 +- include/llvm/Analysis/TargetTransformInfo.h | 161 ++- include/llvm/Analysis/TargetTransformInfoImpl.h | 33 +- include/llvm/Analysis/TypeMetadataUtils.h | 5 +- include/llvm/Analysis/ValueTracking.h | 32 +- include/llvm/Analysis/VectorUtils.h | 59 +- include/llvm/Bitcode/BitcodeWriter.h | 19 +- include/llvm/Bitcode/LLVMBitCodes.h | 25 +- include/llvm/CMakeLists.txt | 1 + include/llvm/CodeGen/Analysis.h | 7 - include/llvm/CodeGen/AsmPrinter.h | 91 +- include/llvm/CodeGen/BasicTTIImpl.h | 175 ++- include/llvm/CodeGen/CallingConvLower.h | 10 - include/llvm/CodeGen/CommandFlags.h | 33 +- include/llvm/CodeGen/ExecutionDepsFix.h | 220 ++++ include/llvm/CodeGen/FastISel.h | 87 +- include/llvm/CodeGen/FaultMaps.h | 43 +- include/llvm/CodeGen/GCStrategy.h | 46 +- include/llvm/CodeGen/GlobalISel/CallLowering.h | 51 +- include/llvm/CodeGen/GlobalISel/IRTranslator.h | 96 +- .../llvm/CodeGen/GlobalISel/InstructionSelector.h | 13 + include/llvm/CodeGen/GlobalISel/Legalizer.h | 3 + include/llvm/CodeGen/GlobalISel/LegalizerHelper.h | 12 +- include/llvm/CodeGen/GlobalISel/LegalizerInfo.h | 8 +- include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h | 150 ++- include/llvm/CodeGen/GlobalISel/RegBankSelect.h | 4 + include/llvm/CodeGen/GlobalISel/RegisterBank.h | 2 +- include/llvm/CodeGen/GlobalISel/RegisterBankInfo.h | 20 +- include/llvm/CodeGen/GlobalISel/Utils.h | 21 + include/llvm/CodeGen/ISDOpcodes.h | 25 +- .../llvm/CodeGen/LazyMachineBlockFrequencyInfo.h | 76 ++ include/llvm/CodeGen/LexicalScopes.h | 38 +- include/llvm/CodeGen/LiveInterval.h | 28 +- include/llvm/CodeGen/LiveIntervalAnalysis.h | 140 +-- include/llvm/CodeGen/LiveIntervalUnion.h | 117 +- include/llvm/CodeGen/LiveRegMatrix.h | 21 +- include/llvm/CodeGen/LiveRegUnits.h | 128 +++ include/llvm/CodeGen/LowLevelType.h | 190 +--- include/llvm/CodeGen/MIRYamlMapping.h | 4 +- include/llvm/CodeGen/MachineBasicBlock.h | 23 +- include/llvm/CodeGen/MachineBlockFrequencyInfo.h | 8 +- include/llvm/CodeGen/MachineDominators.h | 22 +- include/llvm/CodeGen/MachineFrameInfo.h | 10 +- include/llvm/CodeGen/MachineFunction.h | 5 +- include/llvm/CodeGen/MachineFunctionInitializer.h | 2 +- include/llvm/CodeGen/MachineInstr.h | 29 +- include/llvm/CodeGen/MachineInstrBuilder.h | 35 +- include/llvm/CodeGen/MachineLoopInfo.h | 7 + include/llvm/CodeGen/MachineModuleInfoImpls.h | 29 + include/llvm/CodeGen/MachineOperand.h | 30 +- .../CodeGen/MachineOptimizationRemarkEmitter.h | 203 ++++ include/llvm/CodeGen/MachineRegisterInfo.h | 92 +- include/llvm/CodeGen/MachineScheduler.h | 100 +- include/llvm/CodeGen/MachineTraceMetrics.h | 66 +- include/llvm/CodeGen/MachineValueType.h | 81 +- include/llvm/CodeGen/PBQP/Solution.h | 21 +- include/llvm/CodeGen/Passes.h | 28 +- include/llvm/CodeGen/RegAllocPBQP.h | 82 +- include/llvm/CodeGen/RegisterClassInfo.h | 43 +- include/llvm/CodeGen/RegisterPressure.h | 72 +- include/llvm/CodeGen/RegisterScavenging.h | 42 +- include/llvm/CodeGen/ScheduleDAG.h | 509 +++++---- include/llvm/CodeGen/ScheduleDAGInstrs.h | 139 +-- include/llvm/CodeGen/ScheduleDAGMutation.h | 25 +- include/llvm/CodeGen/ScheduleDFS.h | 26 +- include/llvm/CodeGen/ScheduleHazardRecognizer.h | 8 +- include/llvm/CodeGen/ScoreboardHazardRecognizer.h | 22 +- include/llvm/CodeGen/SelectionDAG.h | 44 +- include/llvm/CodeGen/SelectionDAGISel.h | 23 +- include/llvm/CodeGen/SelectionDAGNodes.h | 162 +-- include/llvm/CodeGen/SlotIndexes.h | 22 +- include/llvm/CodeGen/StackMaps.h | 51 +- include/llvm/CodeGen/StackProtector.h | 18 +- .../llvm/CodeGen/TargetLoweringObjectFileImpl.h | 60 +- include/llvm/CodeGen/TargetPassConfig.h | 13 + include/llvm/CodeGen/TargetSchedule.h | 28 +- include/llvm/CodeGen/ValueTypes.h | 131 ++- include/llvm/Config/abi-breaking.h.cmake | 5 +- include/llvm/Config/config.h.cmake | 8 +- include/llvm/Config/llvm-config.h.cmake | 3 - include/llvm/DebugInfo/CodeView/CVRecord.h | 12 +- include/llvm/DebugInfo/CodeView/CVTypeDumper.h | 7 +- include/llvm/DebugInfo/CodeView/CVTypeVisitor.h | 10 +- include/llvm/DebugInfo/CodeView/CodeView.h | 6 + include/llvm/DebugInfo/CodeView/CodeViewError.h | 1 + include/llvm/DebugInfo/CodeView/CodeViewRecordIO.h | 12 +- include/llvm/DebugInfo/CodeView/Formatters.h | 40 + include/llvm/DebugInfo/CodeView/ModuleSubstream.h | 18 +- .../DebugInfo/CodeView/ModuleSubstreamVisitor.h | 54 +- .../llvm/DebugInfo/CodeView/RecordSerialization.h | 44 +- .../llvm/DebugInfo/CodeView/SymbolDeserializer.h | 11 +- include/llvm/DebugInfo/CodeView/SymbolRecord.h | 8 +- .../llvm/DebugInfo/CodeView/SymbolRecordMapping.h | 10 +- include/llvm/DebugInfo/CodeView/SymbolSerializer.h | 47 +- .../DebugInfo/CodeView/SymbolVisitorDelegate.h | 6 +- include/llvm/DebugInfo/CodeView/TypeDatabase.h | 4 +- include/llvm/DebugInfo/CodeView/TypeDeserializer.h | 17 +- include/llvm/DebugInfo/CodeView/TypeDumpVisitor.h | 14 + include/llvm/DebugInfo/CodeView/TypeRecord.h | 157 +-- .../llvm/DebugInfo/CodeView/TypeRecordMapping.h | 11 +- include/llvm/DebugInfo/CodeView/TypeRecords.def | 6 +- include/llvm/DebugInfo/CodeView/TypeSerializer.h | 8 +- .../llvm/DebugInfo/CodeView/TypeServerHandler.h | 36 + include/llvm/DebugInfo/CodeView/TypeStreamMerger.h | 7 +- include/llvm/DebugInfo/CodeView/TypeTableBuilder.h | 6 + include/llvm/DebugInfo/DIContext.h | 30 +- .../DebugInfo/DWARF/DWARFAbbreviationDeclaration.h | 49 +- .../llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h | 17 +- include/llvm/DebugInfo/DWARF/DWARFAttribute.h | 56 + include/llvm/DebugInfo/DWARF/DWARFCompileUnit.h | 18 +- include/llvm/DebugInfo/DWARF/DWARFContext.h | 25 +- include/llvm/DebugInfo/DWARF/DWARFDebugAbbrev.h | 12 +- include/llvm/DebugInfo/DWARF/DWARFDebugArangeSet.h | 13 +- include/llvm/DebugInfo/DWARF/DWARFDebugAranges.h | 14 +- include/llvm/DebugInfo/DWARF/DWARFDebugFrame.h | 14 +- include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h | 35 +- include/llvm/DebugInfo/DWARF/DWARFDebugLine.h | 33 +- include/llvm/DebugInfo/DWARF/DWARFDebugLoc.h | 14 +- include/llvm/DebugInfo/DWARF/DWARFDebugMacro.h | 3 +- include/llvm/DebugInfo/DWARF/DWARFDebugPubTable.h | 18 +- include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h | 16 +- include/llvm/DebugInfo/DWARF/DWARFDie.h | 163 +-- include/llvm/DebugInfo/DWARF/DWARFFormValue.h | 178 ++- include/llvm/DebugInfo/DWARF/DWARFGdbIndex.h | 20 +- include/llvm/DebugInfo/DWARF/DWARFRelocMap.h | 15 +- include/llvm/DebugInfo/DWARF/DWARFSection.h | 12 +- include/llvm/DebugInfo/DWARF/DWARFTypeUnit.h | 23 +- include/llvm/DebugInfo/DWARF/DWARFUnit.h | 59 +- include/llvm/DebugInfo/DWARF/DWARFUnitIndex.h | 25 +- include/llvm/DebugInfo/MSF/ByteStream.h | 169 --- include/llvm/DebugInfo/MSF/MappedBlockStream.h | 65 +- include/llvm/DebugInfo/MSF/SequencedItemStream.h | 93 -- include/llvm/DebugInfo/MSF/StreamArray.h | 304 ------ include/llvm/DebugInfo/MSF/StreamInterface.h | 53 - include/llvm/DebugInfo/MSF/StreamReader.h | 121 -- include/llvm/DebugInfo/MSF/StreamRef.h | 135 --- include/llvm/DebugInfo/MSF/StreamWriter.h | 92 -- .../llvm/DebugInfo/PDB/ConcreteSymbolEnumerator.h | 10 +- include/llvm/DebugInfo/PDB/DIA/DIARawSymbol.h | 1 + include/llvm/DebugInfo/PDB/IPDBRawSymbol.h | 5 + include/llvm/DebugInfo/PDB/IPDBSession.h | 11 +- include/llvm/DebugInfo/PDB/Native/DbiStream.h | 124 +++ .../llvm/DebugInfo/PDB/Native/DbiStreamBuilder.h | 120 ++ include/llvm/DebugInfo/PDB/Native/EnumTables.h | 22 + include/llvm/DebugInfo/PDB/Native/Formatters.h | 52 + include/llvm/DebugInfo/PDB/Native/GlobalsStream.h | 45 + include/llvm/DebugInfo/PDB/Native/Hash.h | 25 + include/llvm/DebugInfo/PDB/Native/HashTable.h | 106 ++ .../DebugInfo/PDB/Native/ISectionContribVisitor.h | 30 + include/llvm/DebugInfo/PDB/Native/InfoStream.h | 83 ++ .../llvm/DebugInfo/PDB/Native/InfoStreamBuilder.h | 64 ++ include/llvm/DebugInfo/PDB/Native/ModInfo.h | 78 ++ include/llvm/DebugInfo/PDB/Native/ModInfoBuilder.h | 74 ++ include/llvm/DebugInfo/PDB/Native/ModStream.h | 62 ++ include/llvm/DebugInfo/PDB/Native/NamedStreamMap.h | 55 + .../DebugInfo/PDB/Native/NativeCompilandSymbol.h | 35 + .../llvm/DebugInfo/PDB/Native/NativeEnumModules.h | 41 + .../llvm/DebugInfo/PDB/Native/NativeExeSymbol.h | 39 + .../llvm/DebugInfo/PDB/Native/NativeRawSymbol.h | 208 ++++ include/llvm/DebugInfo/PDB/Native/NativeSession.h | 78 ++ include/llvm/DebugInfo/PDB/Native/PDBFile.h | 139 +++ include/llvm/DebugInfo/PDB/Native/PDBFileBuilder.h | 71 ++ .../DebugInfo/PDB/Native/PDBTypeServerHandler.h | 48 + include/llvm/DebugInfo/PDB/Native/PublicsStream.h | 73 ++ include/llvm/DebugInfo/PDB/Native/RawConstants.h | 114 ++ include/llvm/DebugInfo/PDB/Native/RawError.h | 53 + include/llvm/DebugInfo/PDB/Native/RawTypes.h | 321 ++++++ include/llvm/DebugInfo/PDB/Native/StringTable.h | 56 + .../llvm/DebugInfo/PDB/Native/StringTableBuilder.h | 44 + include/llvm/DebugInfo/PDB/Native/SymbolStream.h | 42 + include/llvm/DebugInfo/PDB/Native/TpiHashing.h | 95 ++ include/llvm/DebugInfo/PDB/Native/TpiStream.h | 75 ++ .../llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h | 88 ++ include/llvm/DebugInfo/PDB/PDBExtras.h | 2 +- include/llvm/DebugInfo/PDB/PDBSymDumper.h | 16 + include/llvm/DebugInfo/PDB/PDBSymbol.h | 37 +- include/llvm/DebugInfo/PDB/PDBSymbolBlock.h | 2 +- include/llvm/DebugInfo/PDB/PDBSymbolCompiland.h | 2 +- .../llvm/DebugInfo/PDB/PDBSymbolCompilandDetails.h | 2 +- include/llvm/DebugInfo/PDB/PDBSymbolCompilandEnv.h | 2 +- include/llvm/DebugInfo/PDB/PDBSymbolData.h | 8 +- include/llvm/DebugInfo/PDB/PDBSymbolExe.h | 2 + include/llvm/DebugInfo/PDB/PDBSymbolFunc.h | 12 +- include/llvm/DebugInfo/PDB/PDBSymbolFuncDebugEnd.h | 2 +- .../llvm/DebugInfo/PDB/PDBSymbolFuncDebugStart.h | 2 +- include/llvm/DebugInfo/PDB/PDBSymbolLabel.h | 2 +- include/llvm/DebugInfo/PDB/PDBSymbolPublicSymbol.h | 2 +- include/llvm/DebugInfo/PDB/PDBSymbolThunk.h | 6 +- include/llvm/DebugInfo/PDB/PDBSymbolTypeArray.h | 9 +- .../llvm/DebugInfo/PDB/PDBSymbolTypeBaseClass.h | 11 +- include/llvm/DebugInfo/PDB/PDBSymbolTypeBuiltin.h | 2 +- include/llvm/DebugInfo/PDB/PDBSymbolTypeEnum.h | 12 +- include/llvm/DebugInfo/PDB/PDBSymbolTypeFriend.h | 4 +- .../llvm/DebugInfo/PDB/PDBSymbolTypeFunctionArg.h | 6 +- .../llvm/DebugInfo/PDB/PDBSymbolTypeFunctionSig.h | 11 +- include/llvm/DebugInfo/PDB/PDBSymbolTypePointer.h | 7 +- include/llvm/DebugInfo/PDB/PDBSymbolTypeTypedef.h | 8 +- include/llvm/DebugInfo/PDB/PDBSymbolTypeUDT.h | 16 +- include/llvm/DebugInfo/PDB/PDBSymbolTypeVTable.h | 7 +- .../llvm/DebugInfo/PDB/PDBSymbolTypeVTableShape.h | 2 +- .../llvm/DebugInfo/PDB/PDBSymbolUsingNamespace.h | 2 +- include/llvm/DebugInfo/PDB/PDBTypes.h | 6 +- include/llvm/DebugInfo/PDB/Raw/DbiStream.h | 122 --- include/llvm/DebugInfo/PDB/Raw/DbiStreamBuilder.h | 126 --- include/llvm/DebugInfo/PDB/Raw/EnumTables.h | 22 - include/llvm/DebugInfo/PDB/Raw/GlobalsStream.h | 45 - include/llvm/DebugInfo/PDB/Raw/Hash.h | 25 - .../DebugInfo/PDB/Raw/ISectionContribVisitor.h | 30 - include/llvm/DebugInfo/PDB/Raw/InfoStream.h | 69 -- include/llvm/DebugInfo/PDB/Raw/InfoStreamBuilder.h | 62 -- include/llvm/DebugInfo/PDB/Raw/ModInfo.h | 82 -- include/llvm/DebugInfo/PDB/Raw/ModStream.h | 62 -- include/llvm/DebugInfo/PDB/Raw/NameHashTable.h | 54 - include/llvm/DebugInfo/PDB/Raw/NameMap.h | 44 - include/llvm/DebugInfo/PDB/Raw/NameMapBuilder.h | 45 - include/llvm/DebugInfo/PDB/Raw/PDBFile.h | 133 --- include/llvm/DebugInfo/PDB/Raw/PDBFileBuilder.h | 64 -- include/llvm/DebugInfo/PDB/Raw/PublicsStream.h | 74 -- include/llvm/DebugInfo/PDB/Raw/RawConstants.h | 98 -- include/llvm/DebugInfo/PDB/Raw/RawError.h | 52 - include/llvm/DebugInfo/PDB/Raw/RawSession.h | 78 -- include/llvm/DebugInfo/PDB/Raw/RawTypes.h | 308 ------ include/llvm/DebugInfo/PDB/Raw/SymbolStream.h | 42 - include/llvm/DebugInfo/PDB/Raw/TpiHashing.h | 95 -- include/llvm/DebugInfo/PDB/Raw/TpiStream.h | 74 -- include/llvm/DebugInfo/PDB/Raw/TpiStreamBuilder.h | 82 -- include/llvm/DebugInfo/PDB/UDTLayout.h | 180 +++ include/llvm/DebugInfo/Symbolize/DIPrinter.h | 7 +- .../ExecutionEngine/Orc/CompileOnDemandLayer.h | 12 +- .../llvm/ExecutionEngine/Orc/ObjectLinkingLayer.h | 362 ------ include/llvm/ExecutionEngine/Orc/OrcError.h | 6 +- .../ExecutionEngine/Orc/OrcRemoteTargetClient.h | 1 + .../ExecutionEngine/Orc/OrcRemoteTargetServer.h | 23 +- .../llvm/ExecutionEngine/Orc/RPCSerialization.h | 243 +++- include/llvm/ExecutionEngine/Orc/RPCUtils.h | 787 ++++++++----- .../ExecutionEngine/Orc/RTDyldObjectLinkingLayer.h | 362 ++++++ include/llvm/ExecutionEngine/Orc/RawByteChannel.h | 34 +- include/llvm/IR/Argument.h | 99 +- include/llvm/IR/Attributes.h | 294 +++-- include/llvm/IR/BasicBlock.h | 87 +- include/llvm/IR/CallSite.h | 177 +-- include/llvm/IR/Comdat.h | 6 +- include/llvm/IR/Constant.h | 7 +- include/llvm/IR/ConstantRange.h | 11 +- include/llvm/IR/Constants.h | 2 +- include/llvm/IR/DIBuilder.h | 28 +- include/llvm/IR/DataLayout.h | 42 +- include/llvm/IR/DebugInfoFlags.def | 3 +- include/llvm/IR/DebugInfoMetadata.h | 209 +++- include/llvm/IR/DiagnosticInfo.h | 591 ++++++---- include/llvm/IR/Dominators.h | 45 +- include/llvm/IR/Function.h | 101 +- include/llvm/IR/GlobalIndirectSymbol.h | 18 +- include/llvm/IR/GlobalObject.h | 13 +- include/llvm/IR/GlobalValue.h | 14 +- include/llvm/IR/IRBuilder.h | 104 +- include/llvm/IR/InlineAsm.h | 24 +- include/llvm/IR/InstVisitor.h | 3 + include/llvm/IR/InstrTypes.h | 4 +- include/llvm/IR/Instruction.h | 51 +- include/llvm/IR/Instructions.h | 348 +++--- include/llvm/IR/IntrinsicInst.h | 65 ++ include/llvm/IR/Intrinsics.h | 4 +- include/llvm/IR/Intrinsics.td | 82 +- include/llvm/IR/IntrinsicsAMDGPU.td | 109 +- include/llvm/IR/IntrinsicsARM.td | 2 +- include/llvm/IR/IntrinsicsHexagon.td | 870 ++++++++++++++- include/llvm/IR/IntrinsicsNVVM.td | 84 +- include/llvm/IR/IntrinsicsPowerPC.td | 32 +- include/llvm/IR/IntrinsicsWebAssembly.td | 2 +- include/llvm/IR/IntrinsicsX86.td | 156 +-- include/llvm/IR/LLVMContext.h | 1 + include/llvm/IR/MDBuilder.h | 9 +- include/llvm/IR/Mangler.h | 4 + include/llvm/IR/Metadata.h | 15 +- include/llvm/IR/Module.h | 66 +- include/llvm/IR/ModuleSummaryIndex.h | 222 +++- include/llvm/IR/ModuleSummaryIndexYAML.h | 135 ++- include/llvm/IR/Operator.h | 24 +- include/llvm/IR/OptBisect.h | 18 - include/llvm/IR/PassManager.h | 70 +- include/llvm/IR/PassManagerInternal.h | 2 +- include/llvm/IR/PatternMatch.h | 56 + include/llvm/IR/PredIteratorCache.h | 14 +- include/llvm/IR/Statepoint.h | 2 +- include/llvm/IR/SymbolTableListTraits.h | 28 +- include/llvm/IR/TrackingMDRef.h | 17 +- include/llvm/IR/Type.h | 8 +- include/llvm/IR/TypeFinder.h | 14 +- include/llvm/IR/Use.h | 4 +- include/llvm/IR/UseListOrder.h | 7 +- include/llvm/IR/User.h | 14 +- include/llvm/IR/Value.h | 57 +- include/llvm/IR/ValueHandle.h | 136 ++- include/llvm/IR/ValueSymbolTable.h | 45 +- include/llvm/InitializePasses.h | 125 ++- include/llvm/LTO/Caching.h | 15 +- include/llvm/LTO/Config.h | 8 + include/llvm/LTO/LTO.h | 197 +--- include/llvm/LTO/LTOBackend.h | 7 +- include/llvm/LTO/legacy/LTOCodeGenerator.h | 7 +- include/llvm/LTO/legacy/ThinLTOCodeGenerator.h | 19 +- include/llvm/LinkAllPasses.h | 3 + include/llvm/Linker/IRMover.h | 6 +- include/llvm/Linker/Linker.h | 19 +- include/llvm/MC/ConstantPools.h | 10 +- include/llvm/MC/MCAsmBackend.h | 26 +- include/llvm/MC/MCAsmInfo.h | 140 ++- include/llvm/MC/MCAsmInfoCOFF.h | 42 +- include/llvm/MC/MCAsmInfoDarwin.h | 16 +- include/llvm/MC/MCAsmInfoELF.h | 10 +- include/llvm/MC/MCAsmInfoWasm.h | 24 + include/llvm/MC/MCAssembler.h | 59 +- include/llvm/MC/MCCodeEmitter.h | 15 +- include/llvm/MC/MCContext.h | 186 +++- include/llvm/MC/MCDisassembler/MCDisassembler.h | 17 +- include/llvm/MC/MCDisassembler/MCRelocationInfo.h | 18 +- include/llvm/MC/MCDisassembler/MCSymbolizer.h | 16 +- include/llvm/MC/MCDwarf.h | 48 +- include/llvm/MC/MCELFObjectWriter.h | 25 +- include/llvm/MC/MCELFStreamer.h | 26 +- include/llvm/MC/MCExpr.h | 85 +- include/llvm/MC/MCFragment.h | 32 +- include/llvm/MC/MCInst.h | 30 +- include/llvm/MC/MCInstPrinter.h | 16 +- include/llvm/MC/MCInstrAnalysis.h | 11 +- include/llvm/MC/MCInstrItineraries.h | 28 +- include/llvm/MC/MCLabel.h | 12 +- include/llvm/MC/MCLinkerOptimizationHint.h | 11 +- include/llvm/MC/MCMachObjectWriter.h | 15 +- include/llvm/MC/MCObjectFileInfo.h | 5 +- include/llvm/MC/MCObjectStreamer.h | 7 +- include/llvm/MC/MCObjectWriter.h | 24 +- include/llvm/MC/MCParser/AsmCond.h | 10 +- include/llvm/MC/MCParser/AsmLexer.h | 19 +- include/llvm/MC/MCParser/MCAsmLexer.h | 30 +- include/llvm/MC/MCParser/MCAsmParser.h | 41 +- include/llvm/MC/MCParser/MCAsmParserExtension.h | 26 +- include/llvm/MC/MCParser/MCAsmParserUtils.h | 5 +- include/llvm/MC/MCParser/MCParsedAsmOperand.h | 14 +- include/llvm/MC/MCParser/MCTargetAsmParser.h | 34 +- include/llvm/MC/MCRegisterInfo.h | 58 +- include/llvm/MC/MCSection.h | 33 +- include/llvm/MC/MCSectionCOFF.h | 8 +- include/llvm/MC/MCSectionELF.h | 23 +- include/llvm/MC/MCSectionMachO.h | 3 +- include/llvm/MC/MCSectionWasm.h | 86 ++ include/llvm/MC/MCStreamer.h | 41 +- include/llvm/MC/MCSubtargetInfo.h | 34 +- include/llvm/MC/MCSymbol.h | 29 +- include/llvm/MC/MCSymbolCOFF.h | 13 +- include/llvm/MC/MCSymbolWasm.h | 57 + include/llvm/MC/MCTargetOptions.h | 40 +- include/llvm/MC/MCWasmObjectWriter.h | 85 ++ include/llvm/MC/MCWasmStreamer.h | 83 ++ include/llvm/MC/MCWinCOFFObjectWriter.h | 11 +- include/llvm/MC/MCWinCOFFStreamer.h | 11 +- include/llvm/MC/MachineLocation.h | 30 +- include/llvm/MC/StringTableBuilder.h | 11 +- include/llvm/MC/SubtargetFeature.h | 96 +- include/llvm/Object/Archive.h | 1 + include/llvm/Object/Binary.h | 11 + include/llvm/Object/ELF.h | 2 +- include/llvm/Object/ELFObjectFile.h | 31 + include/llvm/Object/IRSymtab.h | 302 +++++ include/llvm/Object/MachO.h | 197 +++- include/llvm/Object/ModuleSummaryIndexObjectFile.h | 7 +- include/llvm/Object/ModuleSymbolTable.h | 3 +- include/llvm/Object/ObjectFile.h | 8 + include/llvm/Object/RelocVisitor.h | 7 + include/llvm/Object/SymbolicFile.h | 4 +- include/llvm/Object/Wasm.h | 112 +- include/llvm/ObjectYAML/DWARFEmitter.h | 48 + include/llvm/ObjectYAML/DWARFYAML.h | 52 +- include/llvm/ObjectYAML/MachOYAML.h | 8 +- include/llvm/ObjectYAML/ObjectYAML.h | 6 +- include/llvm/ObjectYAML/WasmYAML.h | 339 ++++++ include/llvm/Option/ArgList.h | 214 ++-- include/llvm/PassSupport.h | 10 +- include/llvm/Passes/PassBuilder.h | 13 +- .../llvm/ProfileData/Coverage/CoverageMapping.h | 79 +- .../ProfileData/Coverage/CoverageMappingReader.h | 46 +- .../ProfileData/Coverage/CoverageMappingWriter.h | 15 +- include/llvm/ProfileData/InstrProf.h | 171 +-- include/llvm/ProfileData/InstrProfData.inc | 84 +- include/llvm/ProfileData/InstrProfReader.h | 88 +- include/llvm/ProfileData/InstrProfWriter.h | 20 +- include/llvm/ProfileData/ProfileCommon.h | 54 +- include/llvm/ProfileData/SampleProf.h | 124 ++- include/llvm/ProfileData/SampleProfReader.h | 29 +- include/llvm/ProfileData/SampleProfWriter.h | 20 +- include/llvm/Support/AArch64TargetParser.def | 13 +- include/llvm/Support/ARMAttributeParser.h | 140 +++ include/llvm/Support/ARMBuildAttributes.h | 14 +- include/llvm/Support/ARMTargetParser.def | 6 + include/llvm/Support/Allocator.h | 50 +- include/llvm/Support/Atomic.h | 5 + include/llvm/Support/BinaryByteStream.h | 192 ++++ include/llvm/Support/BinaryItemStream.h | 95 ++ include/llvm/Support/BinaryStream.h | 78 ++ include/llvm/Support/BinaryStreamArray.h | 320 ++++++ include/llvm/Support/BinaryStreamError.h | 48 + include/llvm/Support/BinaryStreamReader.h | 234 ++++ include/llvm/Support/BinaryStreamRef.h | 174 +++ include/llvm/Support/BinaryStreamWriter.h | 166 +++ include/llvm/Support/CMakeLists.txt | 54 + include/llvm/Support/CachePruning.h | 79 +- include/llvm/Support/Casting.h | 70 ++ include/llvm/Support/Chrono.h | 95 ++ include/llvm/Support/CommandLine.h | 8 +- include/llvm/Support/Compiler.h | 7 +- include/llvm/Support/Compression.h | 24 +- include/llvm/Support/Debug.h | 28 +- include/llvm/Support/DebugCounter.h | 165 +++ include/llvm/Support/Dwarf.def | 87 +- include/llvm/Support/Dwarf.h | 13 +- include/llvm/Support/DynamicLibrary.h | 9 + include/llvm/Support/ELF.h | 36 +- include/llvm/Support/Endian.h | 89 +- include/llvm/Support/Error.h | 102 +- include/llvm/Support/FileSystem.h | 274 +++-- include/llvm/Support/FormatAdapters.h | 3 - include/llvm/Support/FormatProviders.h | 22 +- include/llvm/Support/FormatVariadic.h | 2 +- include/llvm/Support/GCOV.h | 67 +- include/llvm/Support/GenericDomTree.h | 76 +- include/llvm/Support/GenericDomTreeConstruction.h | 142 ++- include/llvm/Support/Host.h | 12 +- include/llvm/Support/LEB128.h | 72 +- include/llvm/Support/LowLevelTypeImpl.h | 202 ++++ include/llvm/Support/MD5.h | 59 +- include/llvm/Support/MachO.def | 4 + include/llvm/Support/MachO.h | 102 ++ include/llvm/Support/MathExtras.h | 4 +- include/llvm/Support/MemoryBuffer.h | 20 +- include/llvm/Support/Path.h | 80 +- include/llvm/Support/PointerLikeTypeTraits.h | 14 + include/llvm/Support/RWMutex.h | 25 +- include/llvm/Support/SMLoc.h | 4 +- include/llvm/Support/SourceMgr.h | 57 +- include/llvm/Support/TargetParser.h | 2 +- include/llvm/Support/TargetRegistry.h | 71 +- include/llvm/Support/ThreadPool.h | 15 - include/llvm/Support/Threading.h | 104 +- include/llvm/Support/Timer.h | 4 +- include/llvm/Support/TrailingObjects.h | 7 + include/llvm/Support/UniqueLock.h | 18 +- include/llvm/Support/Wasm.h | 145 ++- include/llvm/Support/WasmRelocs/WebAssembly.def | 13 + include/llvm/Support/YAMLTraits.h | 15 +- include/llvm/Support/thread.h | 14 - include/llvm/Support/type_traits.h | 9 + include/llvm/TableGen/Record.h | 4 + include/llvm/TableGen/StringMatcher.h | 2 +- include/llvm/TableGen/StringToOffsetTable.h | 8 +- include/llvm/Target/GenericOpcodes.td | 121 +- include/llvm/Target/GlobalISel/RegisterBank.td | 16 + .../llvm/Target/GlobalISel/SelectionDAGCompat.td | 53 + include/llvm/Target/GlobalISel/Target.td | 56 + include/llvm/Target/Target.td | 33 +- include/llvm/Target/TargetCallingConv.h | 202 ++-- include/llvm/Target/TargetGlobalISel.td | 29 - include/llvm/Target/TargetInstrInfo.h | 140 ++- include/llvm/Target/TargetLowering.h | 154 ++- include/llvm/Target/TargetLoweringObjectFile.h | 50 +- include/llvm/Target/TargetMachine.h | 12 +- include/llvm/Target/TargetOpcodes.def | 55 +- include/llvm/Target/TargetOptions.h | 89 +- include/llvm/Target/TargetRegisterInfo.h | 12 +- include/llvm/Target/TargetSchedule.td | 5 +- include/llvm/Target/TargetSelectionDAG.td | 22 +- include/llvm/Target/TargetSubtargetInfo.h | 8 + include/llvm/Transforms/IPO.h | 45 +- include/llvm/Transforms/IPO/ArgumentPromotion.h | 31 + include/llvm/Transforms/IPO/FunctionAttrs.h | 15 +- include/llvm/Transforms/IPO/FunctionImport.h | 6 +- include/llvm/Transforms/IPO/GlobalDCE.h | 21 +- include/llvm/Transforms/IPO/LowerTypeTests.h | 10 +- include/llvm/Transforms/IPO/PassManagerBuilder.h | 20 + include/llvm/Transforms/InstrProfiling.h | 40 +- include/llvm/Transforms/Instrumentation.h | 84 +- include/llvm/Transforms/PGOInstrumentation.h | 15 +- include/llvm/Transforms/Scalar.h | 30 +- include/llvm/Transforms/Scalar/GVNExpression.h | 313 +++--- include/llvm/Transforms/Scalar/JumpThreading.h | 10 +- include/llvm/Transforms/Scalar/LoopDataPrefetch.h | 8 +- include/llvm/Transforms/Scalar/LoopDeletion.h | 17 +- .../llvm/Transforms/Scalar/LoopLoadElimination.h | 30 + include/llvm/Transforms/Scalar/LoopPassManager.h | 36 +- include/llvm/Transforms/Scalar/LoopPredication.h | 32 + include/llvm/Transforms/Scalar/LoopSink.h | 40 + include/llvm/Transforms/Scalar/LoopUnrollPass.h | 30 +- include/llvm/Transforms/Scalar/MemCpyOptimizer.h | 11 +- include/llvm/Transforms/Scalar/SROA.h | 18 +- include/llvm/Transforms/Scalar/SimplifyCFG.h | 9 +- include/llvm/Transforms/Utils/BasicBlockUtils.h | 9 +- include/llvm/Transforms/Utils/BuildLibCalls.h | 4 +- include/llvm/Transforms/Utils/Cloning.h | 54 +- include/llvm/Transforms/Utils/FunctionComparator.h | 2 +- .../llvm/Transforms/Utils/FunctionImportUtils.h | 11 +- include/llvm/Transforms/Utils/GlobalStatus.h | 31 +- include/llvm/Transforms/Utils/Local.h | 23 +- include/llvm/Transforms/Utils/LoopUtils.h | 57 +- include/llvm/Transforms/Utils/LowerMemIntrinsics.h | 44 + include/llvm/Transforms/Utils/MemorySSA.h | 1014 ----------------- include/llvm/Transforms/Utils/ModuleUtils.h | 3 + include/llvm/Transforms/Utils/NameAnonGlobals.h | 8 +- include/llvm/Transforms/Utils/PredicateInfo.h | 295 +++++ include/llvm/Transforms/Utils/PromoteMemToReg.h | 3 - include/llvm/Transforms/Utils/SSAUpdater.h | 38 +- include/llvm/Transforms/Utils/SimplifyIndVar.h | 11 +- include/llvm/Transforms/Utils/SimplifyLibCalls.h | 5 +- include/llvm/Transforms/Utils/SymbolRewriter.h | 23 +- .../llvm/Transforms/Utils/UnifyFunctionExitNodes.h | 12 +- include/llvm/Transforms/Utils/UnrollLoop.h | 5 +- include/llvm/Transforms/Utils/VNCoercion.h | 108 ++ include/llvm/Transforms/Utils/ValueMapper.h | 20 +- include/llvm/Transforms/Vectorize/SLPVectorizer.h | 6 + include/llvm/XRay/Graph.h | 494 +++++++++ include/llvm/XRay/InstrumentationMap.h | 129 +++ include/llvm/XRay/XRayRecord.h | 9 +- include/llvm/XRay/YAMLXRayRecord.h | 2 +- include/llvm/module.modulemap | 11 +- 584 files changed, 23906 insertions(+), 11972 deletions(-) create mode 100644 include/llvm/ADT/BreadthFirstIterator.h create mode 100644 include/llvm/Analysis/MemorySSA.h create mode 100644 include/llvm/Analysis/MemorySSAUpdater.h create mode 100644 include/llvm/Analysis/ObjectUtils.h create mode 100644 include/llvm/CodeGen/ExecutionDepsFix.h create mode 100644 include/llvm/CodeGen/LazyMachineBlockFrequencyInfo.h create mode 100644 include/llvm/CodeGen/LiveRegUnits.h create mode 100644 include/llvm/CodeGen/MachineOptimizationRemarkEmitter.h create mode 100644 include/llvm/DebugInfo/CodeView/Formatters.h create mode 100644 include/llvm/DebugInfo/CodeView/TypeServerHandler.h create mode 100644 include/llvm/DebugInfo/DWARF/DWARFAttribute.h delete mode 100644 include/llvm/DebugInfo/MSF/ByteStream.h delete mode 100644 include/llvm/DebugInfo/MSF/SequencedItemStream.h delete mode 100644 include/llvm/DebugInfo/MSF/StreamArray.h delete mode 100644 include/llvm/DebugInfo/MSF/StreamInterface.h delete mode 100644 include/llvm/DebugInfo/MSF/StreamReader.h delete mode 100644 include/llvm/DebugInfo/MSF/StreamRef.h delete mode 100644 include/llvm/DebugInfo/MSF/StreamWriter.h create mode 100644 include/llvm/DebugInfo/PDB/Native/DbiStream.h create mode 100644 include/llvm/DebugInfo/PDB/Native/DbiStreamBuilder.h create mode 100644 include/llvm/DebugInfo/PDB/Native/EnumTables.h create mode 100644 include/llvm/DebugInfo/PDB/Native/Formatters.h create mode 100644 include/llvm/DebugInfo/PDB/Native/GlobalsStream.h create mode 100644 include/llvm/DebugInfo/PDB/Native/Hash.h create mode 100644 include/llvm/DebugInfo/PDB/Native/HashTable.h create mode 100644 include/llvm/DebugInfo/PDB/Native/ISectionContribVisitor.h create mode 100644 include/llvm/DebugInfo/PDB/Native/InfoStream.h create mode 100644 include/llvm/DebugInfo/PDB/Native/InfoStreamBuilder.h create mode 100644 include/llvm/DebugInfo/PDB/Native/ModInfo.h create mode 100644 include/llvm/DebugInfo/PDB/Native/ModInfoBuilder.h create mode 100644 include/llvm/DebugInfo/PDB/Native/ModStream.h create mode 100644 include/llvm/DebugInfo/PDB/Native/NamedStreamMap.h create mode 100644 include/llvm/DebugInfo/PDB/Native/NativeCompilandSymbol.h create mode 100644 include/llvm/DebugInfo/PDB/Native/NativeEnumModules.h create mode 100644 include/llvm/DebugInfo/PDB/Native/NativeExeSymbol.h create mode 100644 include/llvm/DebugInfo/PDB/Native/NativeRawSymbol.h create mode 100644 include/llvm/DebugInfo/PDB/Native/NativeSession.h create mode 100644 include/llvm/DebugInfo/PDB/Native/PDBFile.h create mode 100644 include/llvm/DebugInfo/PDB/Native/PDBFileBuilder.h create mode 100644 include/llvm/DebugInfo/PDB/Native/PDBTypeServerHandler.h create mode 100644 include/llvm/DebugInfo/PDB/Native/PublicsStream.h create mode 100644 include/llvm/DebugInfo/PDB/Native/RawConstants.h create mode 100644 include/llvm/DebugInfo/PDB/Native/RawError.h create mode 100644 include/llvm/DebugInfo/PDB/Native/RawTypes.h create mode 100644 include/llvm/DebugInfo/PDB/Native/StringTable.h create mode 100644 include/llvm/DebugInfo/PDB/Native/StringTableBuilder.h create mode 100644 include/llvm/DebugInfo/PDB/Native/SymbolStream.h create mode 100644 include/llvm/DebugInfo/PDB/Native/TpiHashing.h create mode 100644 include/llvm/DebugInfo/PDB/Native/TpiStream.h create mode 100644 include/llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/DbiStream.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/DbiStreamBuilder.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/EnumTables.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/GlobalsStream.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/Hash.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/ISectionContribVisitor.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/InfoStream.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/InfoStreamBuilder.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/ModInfo.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/ModStream.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/NameHashTable.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/NameMap.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/NameMapBuilder.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/PDBFile.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/PDBFileBuilder.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/PublicsStream.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/RawConstants.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/RawError.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/RawSession.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/RawTypes.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/SymbolStream.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/TpiHashing.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/TpiStream.h delete mode 100644 include/llvm/DebugInfo/PDB/Raw/TpiStreamBuilder.h create mode 100644 include/llvm/DebugInfo/PDB/UDTLayout.h delete mode 100644 include/llvm/ExecutionEngine/Orc/ObjectLinkingLayer.h create mode 100644 include/llvm/ExecutionEngine/Orc/RTDyldObjectLinkingLayer.h create mode 100644 include/llvm/MC/MCAsmInfoWasm.h create mode 100644 include/llvm/MC/MCSectionWasm.h create mode 100644 include/llvm/MC/MCSymbolWasm.h create mode 100644 include/llvm/MC/MCWasmObjectWriter.h create mode 100644 include/llvm/MC/MCWasmStreamer.h create mode 100644 include/llvm/Object/IRSymtab.h create mode 100644 include/llvm/ObjectYAML/DWARFEmitter.h create mode 100644 include/llvm/ObjectYAML/WasmYAML.h create mode 100644 include/llvm/Support/ARMAttributeParser.h create mode 100644 include/llvm/Support/BinaryByteStream.h create mode 100644 include/llvm/Support/BinaryItemStream.h create mode 100644 include/llvm/Support/BinaryStream.h create mode 100644 include/llvm/Support/BinaryStreamArray.h create mode 100644 include/llvm/Support/BinaryStreamError.h create mode 100644 include/llvm/Support/BinaryStreamReader.h create mode 100644 include/llvm/Support/BinaryStreamRef.h create mode 100644 include/llvm/Support/BinaryStreamWriter.h create mode 100644 include/llvm/Support/CMakeLists.txt create mode 100644 include/llvm/Support/DebugCounter.h create mode 100644 include/llvm/Support/LowLevelTypeImpl.h create mode 100644 include/llvm/Support/WasmRelocs/WebAssembly.def create mode 100644 include/llvm/Target/GlobalISel/RegisterBank.td create mode 100644 include/llvm/Target/GlobalISel/SelectionDAGCompat.td create mode 100644 include/llvm/Target/GlobalISel/Target.td delete mode 100644 include/llvm/Target/TargetGlobalISel.td create mode 100644 include/llvm/Transforms/IPO/ArgumentPromotion.h create mode 100644 include/llvm/Transforms/Scalar/LoopLoadElimination.h create mode 100644 include/llvm/Transforms/Scalar/LoopPredication.h create mode 100644 include/llvm/Transforms/Scalar/LoopSink.h create mode 100644 include/llvm/Transforms/Utils/LowerMemIntrinsics.h delete mode 100644 include/llvm/Transforms/Utils/MemorySSA.h create mode 100644 include/llvm/Transforms/Utils/PredicateInfo.h create mode 100644 include/llvm/Transforms/Utils/VNCoercion.h create mode 100644 include/llvm/XRay/Graph.h create mode 100644 include/llvm/XRay/InstrumentationMap.h (limited to 'include/llvm') diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 00304230a991..e7e5036e6930 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -18,9 +18,19 @@ #define LLVM_ADT_APFLOAT_H #include "llvm/ADT/APInt.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/Support/ErrorHandling.h" #include +#define APFLOAT_DISPATCH_ON_SEMANTICS(METHOD_CALL) \ + do { \ + if (usesLayout(getSemantics())) \ + return U.IEEE.METHOD_CALL; \ + if (usesLayout(getSemantics())) \ + return U.Double.METHOD_CALL; \ + llvm_unreachable("Unexpected semantics"); \ + } while (false) + namespace llvm { struct fltSemantics; @@ -42,7 +52,7 @@ enum lostFraction { // Example of truncated bits: lfMoreThanHalf // 1xxxxx x's not all zero }; -/// \brief A self-contained host- and target-independent arbitrary-precision +/// A self-contained host- and target-independent arbitrary-precision /// floating-point software implementation. /// /// APFloat uses bignum integer arithmetic as provided by static functions in @@ -130,22 +140,25 @@ enum lostFraction { // Example of truncated bits: // implementation classes. This struct should not define any non-static data // members. struct APFloatBase { + // TODO remove this and use APInt typedef directly. + typedef APInt::WordType integerPart; + /// A signed type to represent a floating point numbers unbiased exponent. typedef signed short ExponentType; /// \name Floating Point Semantics. /// @{ - static const fltSemantics &IEEEhalf(); - static const fltSemantics &IEEEsingle(); - static const fltSemantics &IEEEdouble(); - static const fltSemantics &IEEEquad(); - static const fltSemantics &PPCDoubleDouble(); - static const fltSemantics &x87DoubleExtended(); + static const fltSemantics &IEEEhalf() LLVM_READNONE; + static const fltSemantics &IEEEsingle() LLVM_READNONE; + static const fltSemantics &IEEEdouble() LLVM_READNONE; + static const fltSemantics &IEEEquad() LLVM_READNONE; + static const fltSemantics &PPCDoubleDouble() LLVM_READNONE; + static const fltSemantics &x87DoubleExtended() LLVM_READNONE; /// A Pseudo fltsemantic used to construct APFloats that cannot conflict with /// anything real. - static const fltSemantics &Bogus(); + static const fltSemantics &Bogus() LLVM_READNONE; /// @} @@ -191,7 +204,7 @@ struct APFloatBase { uninitialized }; - /// \brief Enumeration of \c ilogb error results. + /// Enumeration of \c ilogb error results. enum IlogbErrorKinds { IEK_Zero = INT_MIN + 1, IEK_NaN = INT_MIN, @@ -227,7 +240,7 @@ public: /// @} - /// \brief Returns whether this instance allocated memory. + /// Returns whether this instance allocated memory. bool needsCleanup() const { return partCount() > 1; } /// \name Convenience "constructors" @@ -235,10 +248,6 @@ public: /// @} - /// Used to insert APFloat objects, or objects that contain APFloat objects, - /// into FoldingSets. - void Profile(FoldingSetNodeID &NID) const; - /// \name Arithmetic /// @{ @@ -255,53 +264,12 @@ public: /// IEEE-754R 5.3.1: nextUp/nextDown. opStatus next(bool nextDown); - /// \brief Operator+ overload which provides the default - /// \c nmNearestTiesToEven rounding mode and *no* error checking. - IEEEFloat operator+(const IEEEFloat &RHS) const { - IEEEFloat Result = *this; - Result.add(RHS, rmNearestTiesToEven); - return Result; - } - - /// \brief Operator- overload which provides the default - /// \c nmNearestTiesToEven rounding mode and *no* error checking. - IEEEFloat operator-(const IEEEFloat &RHS) const { - IEEEFloat Result = *this; - Result.subtract(RHS, rmNearestTiesToEven); - return Result; - } - - /// \brief Operator* overload which provides the default - /// \c nmNearestTiesToEven rounding mode and *no* error checking. - IEEEFloat operator*(const IEEEFloat &RHS) const { - IEEEFloat Result = *this; - Result.multiply(RHS, rmNearestTiesToEven); - return Result; - } - - /// \brief Operator/ overload which provides the default - /// \c nmNearestTiesToEven rounding mode and *no* error checking. - IEEEFloat operator/(const IEEEFloat &RHS) const { - IEEEFloat Result = *this; - Result.divide(RHS, rmNearestTiesToEven); - return Result; - } - /// @} /// \name Sign operations. /// @{ void changeSign(); - void clearSign(); - void copySign(const IEEEFloat &); - - /// \brief A static helper to produce a copy of an APFloat value with its sign - /// copied from some other APFloat. - static IEEEFloat copySign(IEEEFloat Value, const IEEEFloat &Sign) { - Value.copySign(Sign); - return Value; - } /// @} @@ -309,9 +277,8 @@ public: /// @{ opStatus convert(const fltSemantics &, roundingMode, bool *); - opStatus convertToInteger(integerPart *, unsigned int, bool, roundingMode, - bool *) const; - opStatus convertToInteger(APSInt &, roundingMode, bool *) const; + opStatus convertToInteger(MutableArrayRef, unsigned int, bool, + roundingMode, bool *) const; opStatus convertFromAPInt(const APInt &, bool, roundingMode); opStatus convertFromSignExtendedInteger(const integerPart *, unsigned int, bool, roundingMode); @@ -398,7 +365,7 @@ public: /// Returns true if and only if the number has the largest possible finite /// magnitude in the current semantics. bool isLargest() const; - + /// Returns true if and only if the number is an exact integer. bool isInteger() const; @@ -407,7 +374,7 @@ public: IEEEFloat &operator=(const IEEEFloat &); IEEEFloat &operator=(IEEEFloat &&); - /// \brief Overload to compute a hash code for an APFloat value. + /// Overload to compute a hash code for an APFloat value. /// /// Note that the use of hash codes for floating point values is in general /// frought with peril. Equality is hard to define for these values. For @@ -443,9 +410,9 @@ public: /// If this value has an exact multiplicative inverse, store it in inv and /// return true. - bool getExactInverse(IEEEFloat *inv) const; + bool getExactInverse(APFloat *inv) const; - /// \brief Returns the exponent of the internal representation of the APFloat. + /// Returns the exponent of the internal representation of the APFloat. /// /// Because the radix of APFloat is 2, this is equivalent to floor(log2(x)). /// For special APFloat values, this returns special error codes: @@ -456,7 +423,7 @@ public: /// friend int ilogb(const IEEEFloat &Arg); - /// \brief Returns: X * 2^Exp for integral exponents. + /// Returns: X * 2^Exp for integral exponents. friend IEEEFloat scalbn(IEEEFloat X, int Exp, roundingMode); friend IEEEFloat frexp(const IEEEFloat &X, int &Exp, roundingMode); @@ -532,8 +499,9 @@ private: opStatus addOrSubtract(const IEEEFloat &, roundingMode, bool subtract); opStatus handleOverflow(roundingMode); bool roundAwayFromZero(roundingMode, lostFraction, unsigned int) const; - opStatus convertToSignExtendedInteger(integerPart *, unsigned int, bool, - roundingMode, bool *) const; + opStatus convertToSignExtendedInteger(MutableArrayRef, + unsigned int, bool, roundingMode, + bool *) const; opStatus convertFromUnsignedParts(const integerPart *, unsigned int, roundingMode); opStatus convertFromHexadecimalString(StringRef, roundingMode); @@ -636,6 +604,13 @@ public: opStatus add(const DoubleAPFloat &RHS, roundingMode RM); opStatus subtract(const DoubleAPFloat &RHS, roundingMode RM); + opStatus multiply(const DoubleAPFloat &RHS, roundingMode RM); + opStatus divide(const DoubleAPFloat &RHS, roundingMode RM); + opStatus remainder(const DoubleAPFloat &RHS); + opStatus mod(const DoubleAPFloat &RHS); + opStatus fusedMultiplyAdd(const DoubleAPFloat &Multiplicand, + const DoubleAPFloat &Addend, roundingMode RM); + opStatus roundToIntegral(roundingMode RM); void changeSign(); cmpResult compareAbsoluteValue(const DoubleAPFloat &RHS) const; @@ -643,9 +618,49 @@ public: bool isNegative() const; void makeInf(bool Neg); + void makeZero(bool Neg); + void makeLargest(bool Neg); + void makeSmallest(bool Neg); + void makeSmallestNormalized(bool Neg); void makeNaN(bool SNaN, bool Neg, const APInt *fill); + + cmpResult compare(const DoubleAPFloat &RHS) const; + bool bitwiseIsEqual(const DoubleAPFloat &RHS) const; + APInt bitcastToAPInt() const; + opStatus convertFromString(StringRef, roundingMode); + opStatus next(bool nextDown); + + opStatus convertToInteger(MutableArrayRef Input, + unsigned int Width, bool IsSigned, roundingMode RM, + bool *IsExact) const; + opStatus convertFromAPInt(const APInt &Input, bool IsSigned, roundingMode RM); + opStatus convertFromSignExtendedInteger(const integerPart *Input, + unsigned int InputSize, bool IsSigned, + roundingMode RM); + opStatus convertFromZeroExtendedInteger(const integerPart *Input, + unsigned int InputSize, bool IsSigned, + roundingMode RM); + unsigned int convertToHexString(char *DST, unsigned int HexDigits, + bool UpperCase, roundingMode RM) const; + + bool isDenormal() const; + bool isSmallest() const; + bool isLargest() const; + bool isInteger() const; + + void toString(SmallVectorImpl &Str, unsigned FormatPrecision, + unsigned FormatMaxPadding) const; + + bool getExactInverse(APFloat *inv) const; + + friend int ilogb(const DoubleAPFloat &Arg); + friend DoubleAPFloat scalbn(DoubleAPFloat X, int Exp, roundingMode); + friend DoubleAPFloat frexp(const DoubleAPFloat &X, int &Exp, roundingMode); + friend hash_code hash_value(const DoubleAPFloat &Arg); }; +hash_code hash_value(const DoubleAPFloat &Arg); + } // End detail namespace // This is a interface class that is currently forwarding functionalities from @@ -770,26 +785,24 @@ class APFloat : public APFloatBase { llvm_unreachable("Unexpected semantics"); } - void makeZero(bool Neg) { getIEEE().makeZero(Neg); } + void makeZero(bool Neg) { APFLOAT_DISPATCH_ON_SEMANTICS(makeZero(Neg)); } - void makeInf(bool Neg) { - if (usesLayout(*U.semantics)) - return U.IEEE.makeInf(Neg); - if (usesLayout(*U.semantics)) - return U.Double.makeInf(Neg); - llvm_unreachable("Unexpected semantics"); - } + void makeInf(bool Neg) { APFLOAT_DISPATCH_ON_SEMANTICS(makeInf(Neg)); } void makeNaN(bool SNaN, bool Neg, const APInt *fill) { - getIEEE().makeNaN(SNaN, Neg, fill); + APFLOAT_DISPATCH_ON_SEMANTICS(makeNaN(SNaN, Neg, fill)); } - void makeLargest(bool Neg) { getIEEE().makeLargest(Neg); } + void makeLargest(bool Neg) { + APFLOAT_DISPATCH_ON_SEMANTICS(makeLargest(Neg)); + } - void makeSmallest(bool Neg) { getIEEE().makeSmallest(Neg); } + void makeSmallest(bool Neg) { + APFLOAT_DISPATCH_ON_SEMANTICS(makeSmallest(Neg)); + } void makeSmallestNormalized(bool Neg) { - getIEEE().makeSmallestNormalized(Neg); + APFLOAT_DISPATCH_ON_SEMANTICS(makeSmallestNormalized(Neg)); } // FIXME: This is due to clang 3.3 (or older version) always checks for the @@ -804,7 +817,8 @@ class APFloat : public APFloatBase { : U(std::move(F), S) {} cmpResult compareAbsoluteValue(const APFloat &RHS) const { - assert(&getSemantics() == &RHS.getSemantics()); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only compare APFloats with the same semantics"); if (usesLayout(getSemantics())) return U.IEEE.compareAbsoluteValue(RHS.U.IEEE); if (usesLayout(getSemantics())) @@ -827,13 +841,7 @@ public: ~APFloat() = default; - bool needsCleanup() const { - if (usesLayout(getSemantics())) - return U.IEEE.needsCleanup(); - if (usesLayout(getSemantics())) - return U.Double.needsCleanup(); - llvm_unreachable("Unexpected semantics"); - } + bool needsCleanup() const { APFLOAT_DISPATCH_ON_SEMANTICS(needsCleanup()); } /// Factory for Positive and Negative Zero. /// @@ -920,9 +928,13 @@ public: /// \param isIEEE - If 128 bit number, select between PPC and IEEE static APFloat getAllOnesValue(unsigned BitWidth, bool isIEEE = false); - void Profile(FoldingSetNodeID &NID) const { getIEEE().Profile(NID); } + /// Used to insert APFloat objects, or objects that contain APFloat objects, + /// into FoldingSets. + void Profile(FoldingSetNodeID &NID) const; opStatus add(const APFloat &RHS, roundingMode RM) { + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); if (usesLayout(getSemantics())) return U.IEEE.add(RHS.U.IEEE, RM); if (usesLayout(getSemantics())) @@ -930,6 +942,8 @@ public: llvm_unreachable("Unexpected semantics"); } opStatus subtract(const APFloat &RHS, roundingMode RM) { + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); if (usesLayout(getSemantics())) return U.IEEE.subtract(RHS.U.IEEE, RM); if (usesLayout(getSemantics())) @@ -937,95 +951,172 @@ public: llvm_unreachable("Unexpected semantics"); } opStatus multiply(const APFloat &RHS, roundingMode RM) { - return getIEEE().multiply(RHS.getIEEE(), RM); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); + if (usesLayout(getSemantics())) + return U.IEEE.multiply(RHS.U.IEEE, RM); + if (usesLayout(getSemantics())) + return U.Double.multiply(RHS.U.Double, RM); + llvm_unreachable("Unexpected semantics"); } opStatus divide(const APFloat &RHS, roundingMode RM) { - return getIEEE().divide(RHS.getIEEE(), RM); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); + if (usesLayout(getSemantics())) + return U.IEEE.divide(RHS.U.IEEE, RM); + if (usesLayout(getSemantics())) + return U.Double.divide(RHS.U.Double, RM); + llvm_unreachable("Unexpected semantics"); } opStatus remainder(const APFloat &RHS) { - return getIEEE().remainder(RHS.getIEEE()); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); + if (usesLayout(getSemantics())) + return U.IEEE.remainder(RHS.U.IEEE); + if (usesLayout(getSemantics())) + return U.Double.remainder(RHS.U.Double); + llvm_unreachable("Unexpected semantics"); + } + opStatus mod(const APFloat &RHS) { + assert(&getSemantics() == &RHS.getSemantics() && + "Should only call on two APFloats with the same semantics"); + if (usesLayout(getSemantics())) + return U.IEEE.mod(RHS.U.IEEE); + if (usesLayout(getSemantics())) + return U.Double.mod(RHS.U.Double); + llvm_unreachable("Unexpected semantics"); } - opStatus mod(const APFloat &RHS) { return getIEEE().mod(RHS.getIEEE()); } opStatus fusedMultiplyAdd(const APFloat &Multiplicand, const APFloat &Addend, roundingMode RM) { - return getIEEE().fusedMultiplyAdd(Multiplicand.getIEEE(), Addend.getIEEE(), - RM); + assert(&getSemantics() == &Multiplicand.getSemantics() && + "Should only call on APFloats with the same semantics"); + assert(&getSemantics() == &Addend.getSemantics() && + "Should only call on APFloats with the same semantics"); + if (usesLayout(getSemantics())) + return U.IEEE.fusedMultiplyAdd(Multiplicand.U.IEEE, Addend.U.IEEE, RM); + if (usesLayout(getSemantics())) + return U.Double.fusedMultiplyAdd(Multiplicand.U.Double, Addend.U.Double, + RM); + llvm_unreachable("Unexpected semantics"); } opStatus roundToIntegral(roundingMode RM) { - return getIEEE().roundToIntegral(RM); + APFLOAT_DISPATCH_ON_SEMANTICS(roundToIntegral(RM)); + } + + // TODO: bool parameters are not readable and a source of bugs. + // Do something. + opStatus next(bool nextDown) { + APFLOAT_DISPATCH_ON_SEMANTICS(next(nextDown)); } - opStatus next(bool nextDown) { return getIEEE().next(nextDown); } + /// Add two APFloats, rounding ties to the nearest even. + /// No error checking. APFloat operator+(const APFloat &RHS) const { - return APFloat(getIEEE() + RHS.getIEEE(), getSemantics()); + APFloat Result(*this); + (void)Result.add(RHS, rmNearestTiesToEven); + return Result; } + /// Subtract two APFloats, rounding ties to the nearest even. + /// No error checking. APFloat operator-(const APFloat &RHS) const { - return APFloat(getIEEE() - RHS.getIEEE(), getSemantics()); + APFloat Result(*this); + (void)Result.subtract(RHS, rmNearestTiesToEven); + return Result; } + /// Multiply two APFloats, rounding ties to the nearest even. + /// No error checking. APFloat operator*(const APFloat &RHS) const { - return APFloat(getIEEE() * RHS.getIEEE(), getSemantics()); + APFloat Result(*this); + (void)Result.multiply(RHS, rmNearestTiesToEven); + return Result; } + /// Divide the first APFloat by the second, rounding ties to the nearest even. + /// No error checking. APFloat operator/(const APFloat &RHS) const { - return APFloat(getIEEE() / RHS.getIEEE(), getSemantics()); + APFloat Result(*this); + (void)Result.divide(RHS, rmNearestTiesToEven); + return Result; } - void changeSign() { getIEEE().changeSign(); } - void clearSign() { getIEEE().clearSign(); } - void copySign(const APFloat &RHS) { getIEEE().copySign(RHS.getIEEE()); } + void changeSign() { APFLOAT_DISPATCH_ON_SEMANTICS(changeSign()); } + void clearSign() { + if (isNegative()) + changeSign(); + } + void copySign(const APFloat &RHS) { + if (isNegative() != RHS.isNegative()) + changeSign(); + } + /// A static helper to produce a copy of an APFloat value with its sign + /// copied from some other APFloat. static APFloat copySign(APFloat Value, const APFloat &Sign) { - return APFloat(IEEEFloat::copySign(Value.getIEEE(), Sign.getIEEE()), - Value.getSemantics()); + Value.copySign(Sign); + return Value; } opStatus convert(const fltSemantics &ToSemantics, roundingMode RM, bool *losesInfo); - opStatus convertToInteger(integerPart *Input, unsigned int Width, - bool IsSigned, roundingMode RM, + opStatus convertToInteger(MutableArrayRef Input, + unsigned int Width, bool IsSigned, roundingMode RM, bool *IsExact) const { - return getIEEE().convertToInteger(Input, Width, IsSigned, RM, IsExact); + APFLOAT_DISPATCH_ON_SEMANTICS( + convertToInteger(Input, Width, IsSigned, RM, IsExact)); } opStatus convertToInteger(APSInt &Result, roundingMode RM, - bool *IsExact) const { - return getIEEE().convertToInteger(Result, RM, IsExact); - } + bool *IsExact) const; opStatus convertFromAPInt(const APInt &Input, bool IsSigned, roundingMode RM) { - return getIEEE().convertFromAPInt(Input, IsSigned, RM); + APFLOAT_DISPATCH_ON_SEMANTICS(convertFromAPInt(Input, IsSigned, RM)); } opStatus convertFromSignExtendedInteger(const integerPart *Input, unsigned int InputSize, bool IsSigned, roundingMode RM) { - return getIEEE().convertFromSignExtendedInteger(Input, InputSize, IsSigned, - RM); + APFLOAT_DISPATCH_ON_SEMANTICS( + convertFromSignExtendedInteger(Input, InputSize, IsSigned, RM)); } opStatus convertFromZeroExtendedInteger(const integerPart *Input, unsigned int InputSize, bool IsSigned, roundingMode RM) { - return getIEEE().convertFromZeroExtendedInteger(Input, InputSize, IsSigned, - RM); + APFLOAT_DISPATCH_ON_SEMANTICS( + convertFromZeroExtendedInteger(Input, InputSize, IsSigned, RM)); } opStatus convertFromString(StringRef, roundingMode); - APInt bitcastToAPInt() const { return getIEEE().bitcastToAPInt(); } + APInt bitcastToAPInt() const { + APFLOAT_DISPATCH_ON_SEMANTICS(bitcastToAPInt()); + } double convertToDouble() const { return getIEEE().convertToDouble(); } float convertToFloat() const { return getIEEE().convertToFloat(); } bool operator==(const APFloat &) const = delete; cmpResult compare(const APFloat &RHS) const { - return getIEEE().compare(RHS.getIEEE()); + assert(&getSemantics() == &RHS.getSemantics() && + "Should only compare APFloats with the same semantics"); + if (usesLayout(getSemantics())) + return U.IEEE.compare(RHS.U.IEEE); + if (usesLayout(getSemantics())) + return U.Double.compare(RHS.U.Double); + llvm_unreachable("Unexpected semantics"); } bool bitwiseIsEqual(const APFloat &RHS) const { - return getIEEE().bitwiseIsEqual(RHS.getIEEE()); + if (&getSemantics() != &RHS.getSemantics()) + return false; + if (usesLayout(getSemantics())) + return U.IEEE.bitwiseIsEqual(RHS.U.IEEE); + if (usesLayout(getSemantics())) + return U.Double.bitwiseIsEqual(RHS.U.Double); + llvm_unreachable("Unexpected semantics"); } unsigned int convertToHexString(char *DST, unsigned int HexDigits, bool UpperCase, roundingMode RM) const { - return getIEEE().convertToHexString(DST, HexDigits, UpperCase, RM); + APFLOAT_DISPATCH_ON_SEMANTICS( + convertToHexString(DST, HexDigits, UpperCase, RM)); } bool isZero() const { return getCategory() == fcZero; } @@ -1033,7 +1124,7 @@ public: bool isNaN() const { return getCategory() == fcNaN; } bool isNegative() const { return getIEEE().isNegative(); } - bool isDenormal() const { return getIEEE().isDenormal(); } + bool isDenormal() const { APFLOAT_DISPATCH_ON_SEMANTICS(isDenormal()); } bool isSignaling() const { return getIEEE().isSignaling(); } bool isNormal() const { return !isDenormal() && isFiniteNonZero(); } @@ -1045,30 +1136,24 @@ public: bool isFiniteNonZero() const { return isFinite() && !isZero(); } bool isPosZero() const { return isZero() && !isNegative(); } bool isNegZero() const { return isZero() && isNegative(); } - bool isSmallest() const { return getIEEE().isSmallest(); } - bool isLargest() const { return getIEEE().isLargest(); } - bool isInteger() const { return getIEEE().isInteger(); } + bool isSmallest() const { APFLOAT_DISPATCH_ON_SEMANTICS(isSmallest()); } + bool isLargest() const { APFLOAT_DISPATCH_ON_SEMANTICS(isLargest()); } + bool isInteger() const { APFLOAT_DISPATCH_ON_SEMANTICS(isInteger()); } APFloat &operator=(const APFloat &RHS) = default; APFloat &operator=(APFloat &&RHS) = default; void toString(SmallVectorImpl &Str, unsigned FormatPrecision = 0, unsigned FormatMaxPadding = 3) const { - return getIEEE().toString(Str, FormatPrecision, FormatMaxPadding); + APFLOAT_DISPATCH_ON_SEMANTICS( + toString(Str, FormatPrecision, FormatMaxPadding)); } void print(raw_ostream &) const; void dump() const; bool getExactInverse(APFloat *inv) const { - return getIEEE().getExactInverse(inv ? &inv->getIEEE() : nullptr); - } - - // This is for internal test only. - // TODO: Remove it after the PPCDoubleDouble transition. - const APFloat &getSecondFloat() const { - assert(&getSemantics() == &PPCDoubleDouble()); - return U.Double.getSecond(); + APFLOAT_DISPATCH_ON_SEMANTICS(getExactInverse(inv)); } friend hash_code hash_value(const APFloat &Arg); @@ -1085,22 +1170,36 @@ public: /// xlC compiler. hash_code hash_value(const APFloat &Arg); inline APFloat scalbn(APFloat X, int Exp, APFloat::roundingMode RM) { - return APFloat(scalbn(X.getIEEE(), Exp, RM), X.getSemantics()); + if (APFloat::usesLayout(X.getSemantics())) + return APFloat(scalbn(X.U.IEEE, Exp, RM), X.getSemantics()); + if (APFloat::usesLayout(X.getSemantics())) + return APFloat(scalbn(X.U.Double, Exp, RM), X.getSemantics()); + llvm_unreachable("Unexpected semantics"); } -/// \brief Equivalent of C standard library function. +/// Equivalent of C standard library function. /// /// While the C standard says Exp is an unspecified value for infinity and nan, /// this returns INT_MAX for infinities, and INT_MIN for NaNs. inline APFloat frexp(const APFloat &X, int &Exp, APFloat::roundingMode RM) { - return APFloat(frexp(X.getIEEE(), Exp, RM), X.getSemantics()); + if (APFloat::usesLayout(X.getSemantics())) + return APFloat(frexp(X.U.IEEE, Exp, RM), X.getSemantics()); + if (APFloat::usesLayout(X.getSemantics())) + return APFloat(frexp(X.U.Double, Exp, RM), X.getSemantics()); + llvm_unreachable("Unexpected semantics"); } -/// \brief Returns the absolute value of the argument. +/// Returns the absolute value of the argument. inline APFloat abs(APFloat X) { X.clearSign(); return X; } +/// \brief Returns the negated value of the argument. +inline APFloat neg(APFloat X) { + X.changeSign(); + return X; +} + /// Implements IEEE minNum semantics. Returns the smaller of the 2 arguments if /// both are not NaN. If either argument is a NaN, returns the other argument. LLVM_READONLY @@ -1125,4 +1224,5 @@ inline APFloat maxnum(const APFloat &A, const APFloat &B) { } // namespace llvm +#undef APFLOAT_DISPATCH_ON_SEMANTICS #endif // LLVM_ADT_APFLOAT_H diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 2c0713da256c..ab23130b137d 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -32,14 +32,6 @@ class raw_ostream; template class SmallVectorImpl; template class ArrayRef; -// An unsigned host type used as a single part of a multi-part -// bignum. -typedef uint64_t integerPart; - -const unsigned int host_char_bit = 8; -const unsigned int integerPartWidth = - host_char_bit * static_cast(sizeof(integerPart)); - class APInt; inline APInt operator-(APInt); @@ -75,8 +67,18 @@ inline APInt operator-(APInt); /// uses in its IR. This simplifies its use for LLVM. /// class LLVM_NODISCARD APInt { - unsigned BitWidth; ///< The number of bits in this APInt. +public: + typedef uint64_t WordType; + /// This enum is used to hold the constants we needed for APInt. + enum : unsigned { + /// Byte size of a word. + APINT_WORD_SIZE = sizeof(WordType), + /// Bits in a word. + APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT + }; + +private: /// This union is used to store the integer value. When the /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal. union { @@ -84,14 +86,7 @@ class LLVM_NODISCARD APInt { uint64_t *pVal; ///< Used to store the >64 bits integer value. }; - /// This enum is used to hold the constants we needed for APInt. - enum { - /// Bits in a word - APINT_BITS_PER_WORD = - static_cast(sizeof(uint64_t)) * CHAR_BIT, - /// Byte size of a word - APINT_WORD_SIZE = static_cast(sizeof(uint64_t)) - }; + unsigned BitWidth; ///< The number of bits in this APInt. friend struct DenseMapAPIntKeyInfo; @@ -99,7 +94,7 @@ class LLVM_NODISCARD APInt { /// /// This constructor is used only internally for speed of construction of /// temporaries. It is unsafe for general use so it is not public. - APInt(uint64_t *val, unsigned bits) : BitWidth(bits), pVal(val) {} + APInt(uint64_t *val, unsigned bits) : pVal(val), BitWidth(bits) {} /// \brief Determine if this APInt just has one word to store value. /// @@ -147,7 +142,7 @@ class LLVM_NODISCARD APInt { return *this; // Mask out the high bits. - uint64_t mask = ~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - wordBits); + uint64_t mask = UINT64_MAX >> (APINT_BITS_PER_WORD - wordBits); if (isSingleWord()) VAL &= mask; else @@ -196,32 +191,38 @@ class LLVM_NODISCARD APInt { /// out-of-line slow case for shl APInt shlSlowCase(unsigned shiftAmt) const; - /// out-of-line slow case for operator& - APInt AndSlowCase(const APInt &RHS) const; - - /// out-of-line slow case for operator| - APInt OrSlowCase(const APInt &RHS) const; - - /// out-of-line slow case for operator^ - APInt XorSlowCase(const APInt &RHS) const; - /// out-of-line slow case for operator= APInt &AssignSlowCase(const APInt &RHS); /// out-of-line slow case for operator== - bool EqualSlowCase(const APInt &RHS) const; + bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY; /// out-of-line slow case for operator== - bool EqualSlowCase(uint64_t Val) const; + bool EqualSlowCase(uint64_t Val) const LLVM_READONLY; /// out-of-line slow case for countLeadingZeros - unsigned countLeadingZerosSlowCase() const; + unsigned countLeadingZerosSlowCase() const LLVM_READONLY; /// out-of-line slow case for countTrailingOnes - unsigned countTrailingOnesSlowCase() const; + unsigned countTrailingOnesSlowCase() const LLVM_READONLY; /// out-of-line slow case for countPopulation - unsigned countPopulationSlowCase() const; + unsigned countPopulationSlowCase() const LLVM_READONLY; + + /// out-of-line slow case for setBits. + void setBitsSlowCase(unsigned loBit, unsigned hiBit); + + /// out-of-line slow case for flipAllBits. + void flipAllBitsSlowCase(); + + /// out-of-line slow case for operator&=. + APInt& AndAssignSlowCase(const APInt& RHS); + + /// out-of-line slow case for operator|=. + APInt& OrAssignSlowCase(const APInt& RHS); + + /// out-of-line slow case for operator^=. + APInt& XorAssignSlowCase(const APInt& RHS); public: /// \name Constructors @@ -238,13 +239,14 @@ public: /// \param val the initial value of the APInt /// \param isSigned how to treat signedness of val APInt(unsigned numBits, uint64_t val, bool isSigned = false) - : BitWidth(numBits), VAL(0) { + : BitWidth(numBits) { assert(BitWidth && "bitwidth too small"); - if (isSingleWord()) + if (isSingleWord()) { VAL = val; - else + clearUnusedBits(); + } else { initSlowCase(val, isSigned); - clearUnusedBits(); + } } /// \brief Construct an APInt of numBits width, initialized as bigVal[]. @@ -280,7 +282,7 @@ public: /// Simply makes *this a copy of that. /// @brief Copy Constructor. - APInt(const APInt &that) : BitWidth(that.BitWidth), VAL(0) { + APInt(const APInt &that) : BitWidth(that.BitWidth) { if (isSingleWord()) VAL = that.VAL; else @@ -288,7 +290,7 @@ public: } /// \brief Move Constructor. - APInt(APInt &&that) : BitWidth(that.BitWidth), VAL(that.VAL) { + APInt(APInt &&that) : VAL(that.VAL), BitWidth(that.BitWidth) { that.BitWidth = 0; } @@ -303,7 +305,7 @@ public: /// /// This is useful for object deserialization (pair this with the static /// method Read). - explicit APInt() : BitWidth(1), VAL(0) {} + explicit APInt() : VAL(0), BitWidth(1) {} /// \brief Returns whether this instance allocated memory. bool needsCleanup() const { return !isSingleWord(); } @@ -341,7 +343,7 @@ public: /// This checks to see if the value has all bits of the APInt are set or not. bool isAllOnesValue() const { if (isSingleWord()) - return VAL == ~integerPart(0) >> (APINT_BITS_PER_WORD - BitWidth); + return VAL == UINT64_MAX >> (APINT_BITS_PER_WORD - BitWidth); return countPopulationSlowCase() == BitWidth; } @@ -406,7 +408,7 @@ public: /// If this value is smaller than the specified limit, return it, otherwise /// return the limit value. This causes the value to saturate to the limit. - uint64_t getLimitedValue(uint64_t Limit = ~0ULL) const { + uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) const { return (getActiveBits() > 64 || getZExtValue() > Limit) ? Limit : getZExtValue(); } @@ -418,6 +420,36 @@ public: /// width without remainder. bool isSplat(unsigned SplatSizeInBits) const; + /// \returns true if this APInt value is a sequence of \param numBits ones + /// starting at the least significant bit with the remainder zero. + bool isMask(unsigned numBits) const { + assert(numBits != 0 && "numBits must be non-zero"); + assert(numBits <= BitWidth && "numBits out of range"); + if (isSingleWord()) + return VAL == (UINT64_MAX >> (APINT_BITS_PER_WORD - numBits)); + unsigned Ones = countTrailingOnes(); + return (numBits == Ones) && ((Ones + countLeadingZeros()) == BitWidth); + } + + /// \returns true if this APInt is a non-empty sequence of ones starting at + /// the least significant bit with the remainder zero. + /// Ex. isMask(0x0000FFFFU) == true. + bool isMask() const { + if (isSingleWord()) + return isMask_64(VAL); + unsigned Ones = countTrailingOnes(); + return (Ones > 0) && ((Ones + countLeadingZeros()) == BitWidth); + } + + /// \brief Return true if this APInt value contains a sequence of ones with + /// the remainder zero. + bool isShiftedMask() const { + if (isSingleWord()) + return isShiftedMask_64(VAL); + unsigned Ones = countPopulation(); + return (Ones + countTrailingZeros() + countLeadingZeros()) == BitWidth; + } + /// @} /// \name Value Generators /// @{ @@ -501,12 +533,26 @@ public: /// /// \returns An APInt value with the requested bits set. static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { - assert(hiBit <= numBits && "hiBit out of range"); - assert(loBit < numBits && "loBit out of range"); - if (hiBit < loBit) - return getLowBitsSet(numBits, hiBit) | - getHighBitsSet(numBits, numBits - loBit); - return getLowBitsSet(numBits, hiBit - loBit).shl(loBit); + APInt Res(numBits, 0); + Res.setBits(loBit, hiBit); + return Res; + } + + /// \brief Get a value with upper bits starting at loBit set. + /// + /// Constructs an APInt value that has a contiguous range of bits set. The + /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other + /// bits will be zero. For example, with parameters(32, 12) you would get + /// 0xFFFFF000. + /// + /// \param numBits the intended bit width of the result + /// \param loBit the index of the lowest bit to set. + /// + /// \returns An APInt value with the requested bits set. + static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) { + APInt Res(numBits, 0); + Res.setBitsFrom(loBit); + return Res; } /// \brief Get a value with high bits set @@ -516,15 +562,9 @@ public: /// \param numBits the bitwidth of the result /// \param hiBitsSet the number of high-order bits set in the result. static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { - assert(hiBitsSet <= numBits && "Too many bits to set!"); - // Handle a degenerate case, to avoid shifting by word size - if (hiBitsSet == 0) - return APInt(numBits, 0); - unsigned shiftAmt = numBits - hiBitsSet; - // For small values, return quickly - if (numBits <= APINT_BITS_PER_WORD) - return APInt(numBits, ~0ULL << shiftAmt); - return getAllOnesValue(numBits).shl(shiftAmt); + APInt Res(numBits, 0); + Res.setHighBits(hiBitsSet); + return Res; } /// \brief Get a value with low bits set @@ -534,16 +574,9 @@ public: /// \param numBits the bitwidth of the result /// \param loBitsSet the number of low-order bits set in the result. static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { - assert(loBitsSet <= numBits && "Too many bits to set!"); - // Handle a degenerate case, to avoid shifting by word size - if (loBitsSet == 0) - return APInt(numBits, 0); - if (loBitsSet == APINT_BITS_PER_WORD) - return APInt(numBits, UINT64_MAX); - // For small values, return quickly. - if (loBitsSet <= APINT_BITS_PER_WORD) - return APInt(numBits, UINT64_MAX >> (APINT_BITS_PER_WORD - loBitsSet)); - return getAllOnesValue(numBits).lshr(numBits - loBitsSet); + APInt Res(numBits, 0); + Res.setLowBits(loBitsSet); + return Res; } /// \brief Return a value containing V broadcasted over NewLen bits. @@ -587,7 +620,9 @@ public: /// \brief Postfix increment operator. /// - /// \returns a new APInt value representing *this incremented by one + /// Increments *this by 1. + /// + /// \returns a new APInt value representing the original value of *this. const APInt operator++(int) { APInt API(*this); ++(*this); @@ -601,7 +636,9 @@ public: /// \brief Postfix decrement operator. /// - /// \returns a new APInt representing *this decremented by one. + /// Decrements *this by 1. + /// + /// \returns a new APInt value representing the original value of *this. const APInt operator--(int) { APInt API(*this); --(*this); @@ -613,30 +650,13 @@ public: /// \returns *this decremented by one. APInt &operator--(); - /// \brief Unary bitwise complement operator. - /// - /// Performs a bitwise complement operation on this APInt. - /// - /// \returns an APInt that is the bitwise complement of *this - APInt operator~() const { - APInt Result(*this); - Result.flipAllBits(); - return Result; - } - /// \brief Logical negation operator. /// /// Performs logical negation operation on this APInt. /// /// \returns true if *this is zero, false otherwise. bool operator!() const { - if (isSingleWord()) - return !VAL; - - for (unsigned i = 0; i != getNumWords(); ++i) - if (pVal[i]) - return false; - return true; + return *this == 0; } /// @} @@ -688,7 +708,16 @@ public: /// than 64, the value is zero filled in the unspecified high order bits. /// /// \returns *this after assignment of RHS value. - APInt &operator=(uint64_t RHS); + APInt &operator=(uint64_t RHS) { + if (isSingleWord()) { + VAL = RHS; + clearUnusedBits(); + } else { + pVal[0] = RHS; + memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); + } + return *this; + } /// \brief Bitwise AND assignment operator. /// @@ -696,7 +725,29 @@ public: /// assigned to *this. /// /// \returns *this after ANDing with RHS. - APInt &operator&=(const APInt &RHS); + APInt &operator&=(const APInt &RHS) { + assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); + if (isSingleWord()) { + VAL &= RHS.VAL; + return *this; + } + return AndAssignSlowCase(RHS); + } + + /// \brief Bitwise AND assignment operator. + /// + /// Performs a bitwise AND operation on this APInt and RHS. RHS is + /// logically zero-extended or truncated to match the bit-width of + /// the LHS. + APInt &operator&=(uint64_t RHS) { + if (isSingleWord()) { + VAL &= RHS; + return *this; + } + pVal[0] &= RHS; + memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); + return *this; + } /// \brief Bitwise OR assignment operator. /// @@ -704,7 +755,14 @@ public: /// assigned *this; /// /// \returns *this after ORing with RHS. - APInt &operator|=(const APInt &RHS); + APInt &operator|=(const APInt &RHS) { + assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); + if (isSingleWord()) { + VAL |= RHS.VAL; + return *this; + } + return OrAssignSlowCase(RHS); + } /// \brief Bitwise OR assignment operator. /// @@ -727,7 +785,29 @@ public: /// assigned to *this. /// /// \returns *this after XORing with RHS. - APInt &operator^=(const APInt &RHS); + APInt &operator^=(const APInt &RHS) { + assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); + if (isSingleWord()) { + VAL ^= RHS.VAL; + return *this; + } + return XorAssignSlowCase(RHS); + } + + /// \brief Bitwise XOR assignment operator. + /// + /// Performs a bitwise XOR operation on this APInt and RHS. RHS is + /// logically zero-extended or truncated to match the bit-width of + /// the LHS. + APInt &operator^=(uint64_t RHS) { + if (isSingleWord()) { + VAL ^= RHS; + clearUnusedBits(); + } else { + pVal[0] ^= RHS; + } + return *this; + } /// \brief Multiplication assignment operator. /// @@ -766,59 +846,6 @@ public: /// \name Binary Operators /// @{ - /// \brief Bitwise AND operator. - /// - /// Performs a bitwise AND operation on *this and RHS. - /// - /// \returns An APInt value representing the bitwise AND of *this and RHS. - APInt operator&(const APInt &RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(getBitWidth(), VAL & RHS.VAL); - return AndSlowCase(RHS); - } - APInt And(const APInt &RHS) const { return this->operator&(RHS); } - - /// \brief Bitwise OR operator. - /// - /// Performs a bitwise OR operation on *this and RHS. - /// - /// \returns An APInt value representing the bitwise OR of *this and RHS. - APInt operator|(const APInt &RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(getBitWidth(), VAL | RHS.VAL); - return OrSlowCase(RHS); - } - - /// \brief Bitwise OR function. - /// - /// Performs a bitwise or on *this and RHS. This is implemented by simply - /// calling operator|. - /// - /// \returns An APInt value representing the bitwise OR of *this and RHS. - APInt Or(const APInt &RHS) const { return this->operator|(RHS); } - - /// \brief Bitwise XOR operator. - /// - /// Performs a bitwise XOR operation on *this and RHS. - /// - /// \returns An APInt value representing the bitwise XOR of *this and RHS. - APInt operator^(const APInt &RHS) const { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); - if (isSingleWord()) - return APInt(BitWidth, VAL ^ RHS.VAL); - return XorSlowCase(RHS); - } - - /// \brief Bitwise XOR function. - /// - /// Performs a bitwise XOR operation on *this and RHS. This is implemented - /// through the usage of operator^. - /// - /// \returns An APInt value representing the bitwise XOR of *this and RHS. - APInt Xor(const APInt &RHS) const { return this->operator^(RHS); } - /// \brief Multiplication operator. /// /// Multiplies this APInt by RHS and returns the result. @@ -842,7 +869,14 @@ public: /// \brief Logical right-shift function. /// /// Logical right-shift this APInt by shiftAmt. - APInt lshr(unsigned shiftAmt) const; + APInt lshr(unsigned shiftAmt) const { + APInt R(*this); + R.lshrInPlace(shiftAmt); + return R; + } + + /// Logical right-shift this APInt by shiftAmt in place. + void lshrInPlace(unsigned shiftAmt); /// \brief Left-shift function. /// @@ -1012,7 +1046,7 @@ public: /// the validity of the less-than relationship. /// /// \returns true if *this < RHS when both are considered unsigned. - bool ult(const APInt &RHS) const; + bool ult(const APInt &RHS) const LLVM_READONLY; /// \brief Unsigned less than comparison /// @@ -1030,7 +1064,7 @@ public: /// validity of the less-than relationship. /// /// \returns true if *this < RHS when both are considered signed. - bool slt(const APInt &RHS) const; + bool slt(const APInt &RHS) const LLVM_READONLY; /// \brief Signed less than comparison /// @@ -1144,7 +1178,11 @@ public: /// This operation tests if there are any pairs of corresponding bits /// between this APInt and RHS that are both set. - bool intersects(const APInt &RHS) const { return (*this & RHS) != 0; } + bool intersects(const APInt &RHS) const { + APInt temp(*this); + temp &= RHS; + return temp != 0; + } /// @} /// \name Resizing Operators @@ -1203,11 +1241,9 @@ public: void setAllBits() { if (isSingleWord()) VAL = UINT64_MAX; - else { + else // Set all the bits in all the words. - for (unsigned i = 0; i < getNumWords(); ++i) - pVal[i] = UINT64_MAX; - } + memset(pVal, -1, getNumWords() * APINT_WORD_SIZE); // Clear the unused ones clearUnusedBits(); } @@ -1217,6 +1253,49 @@ public: /// Set the given bit to 1 whose position is given as "bitPosition". void setBit(unsigned bitPosition); + /// Set the sign bit to 1. + void setSignBit() { + setBit(BitWidth - 1); + } + + /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. + void setBits(unsigned loBit, unsigned hiBit) { + assert(hiBit <= BitWidth && "hiBit out of range"); + assert(loBit <= BitWidth && "loBit out of range"); + if (loBit == hiBit) + return; + if (loBit > hiBit) { + setLowBits(hiBit); + setHighBits(BitWidth - loBit); + return; + } + if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) { + uint64_t mask = UINT64_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit)); + mask <<= loBit; + if (isSingleWord()) + VAL |= mask; + else + pVal[0] |= mask; + } else { + setBitsSlowCase(loBit, hiBit); + } + } + + /// Set the top bits starting from loBit. + void setBitsFrom(unsigned loBit) { + return setBits(loBit, BitWidth); + } + + /// Set the bottom loBits bits. + void setLowBits(unsigned loBits) { + return setBits(0, loBits); + } + + /// Set the top hiBits bits. + void setHighBits(unsigned hiBits) { + return setBits(BitWidth - hiBits, BitWidth); + } + /// \brief Set every bit to 0. void clearAllBits() { if (isSingleWord()) @@ -1232,13 +1311,12 @@ public: /// \brief Toggle every bit to its opposite value. void flipAllBits() { - if (isSingleWord()) + if (isSingleWord()) { VAL ^= UINT64_MAX; - else { - for (unsigned i = 0; i < getNumWords(); ++i) - pVal[i] ^= UINT64_MAX; + clearUnusedBits(); + } else { + flipAllBitsSlowCase(); } - clearUnusedBits(); } /// \brief Toggles a given bit to its opposite value. @@ -1247,6 +1325,12 @@ public: /// as "bitPosition". void flipBit(unsigned bitPosition); + /// Insert the bits from a smaller APInt starting at bitPosition. + void insertBits(const APInt &SubBits, unsigned bitPosition); + + /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits). + APInt extractBits(unsigned numBits, unsigned bitPosition) const; + /// @} /// \name Value Characterization Functions /// @{ @@ -1356,7 +1440,7 @@ public: /// /// \returns 0 if the high order bit is not set, otherwise returns the number /// of 1 bits from the most significant to the least - unsigned countLeadingOnes() const; + unsigned countLeadingOnes() const LLVM_READONLY; /// Computes the number of leading bits of this APInt that are equal to its /// sign bit. @@ -1372,7 +1456,7 @@ public: /// /// \returns BitWidth if the value is zero, otherwise returns the number of /// zeros from the least significant bit to the first one bit. - unsigned countTrailingZeros() const; + unsigned countTrailingZeros() const LLVM_READONLY; /// \brief Count the number of trailing one bits. /// @@ -1589,46 +1673,50 @@ public: /// Sets the least significant part of a bignum to the input value, and zeroes /// out higher parts. - static void tcSet(integerPart *, integerPart, unsigned int); + static void tcSet(WordType *, WordType, unsigned); /// Assign one bignum to another. - static void tcAssign(integerPart *, const integerPart *, unsigned int); + static void tcAssign(WordType *, const WordType *, unsigned); /// Returns true if a bignum is zero, false otherwise. - static bool tcIsZero(const integerPart *, unsigned int); + static bool tcIsZero(const WordType *, unsigned); /// Extract the given bit of a bignum; returns 0 or 1. Zero-based. - static int tcExtractBit(const integerPart *, unsigned int bit); + static int tcExtractBit(const WordType *, unsigned bit); /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least /// significant bit of DST. All high bits above srcBITS in DST are /// zero-filled. - static void tcExtract(integerPart *, unsigned int dstCount, - const integerPart *, unsigned int srcBits, - unsigned int srcLSB); + static void tcExtract(WordType *, unsigned dstCount, + const WordType *, unsigned srcBits, + unsigned srcLSB); /// Set the given bit of a bignum. Zero-based. - static void tcSetBit(integerPart *, unsigned int bit); + static void tcSetBit(WordType *, unsigned bit); /// Clear the given bit of a bignum. Zero-based. - static void tcClearBit(integerPart *, unsigned int bit); + static void tcClearBit(WordType *, unsigned bit); /// Returns the bit number of the least or most significant set bit of a /// number. If the input number has no bits set -1U is returned. - static unsigned int tcLSB(const integerPart *, unsigned int); - static unsigned int tcMSB(const integerPart *parts, unsigned int n); + static unsigned tcLSB(const WordType *, unsigned n); + static unsigned tcMSB(const WordType *parts, unsigned n); /// Negate a bignum in-place. - static void tcNegate(integerPart *, unsigned int); + static void tcNegate(WordType *, unsigned); /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag. - static integerPart tcAdd(integerPart *, const integerPart *, - integerPart carry, unsigned); + static WordType tcAdd(WordType *, const WordType *, + WordType carry, unsigned); + /// DST += RHS. Returns the carry flag. + static WordType tcAddPart(WordType *, WordType, unsigned); /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag. - static integerPart tcSubtract(integerPart *, const integerPart *, - integerPart carry, unsigned); + static WordType tcSubtract(WordType *, const WordType *, + WordType carry, unsigned); + /// DST -= RHS. Returns the carry flag. + static WordType tcSubtractPart(WordType *, WordType, unsigned); /// DST += SRC * MULTIPLIER + PART if add is true /// DST = SRC * MULTIPLIER + PART if add is false @@ -1640,23 +1728,23 @@ public: /// Otherwise DST is filled with the least significant DSTPARTS parts of the /// result, and if all of the omitted higher parts were zero return zero, /// otherwise overflow occurred and return one. - static int tcMultiplyPart(integerPart *dst, const integerPart *src, - integerPart multiplier, integerPart carry, - unsigned int srcParts, unsigned int dstParts, + static int tcMultiplyPart(WordType *dst, const WordType *src, + WordType multiplier, WordType carry, + unsigned srcParts, unsigned dstParts, bool add); /// DST = LHS * RHS, where DST has the same width as the operands and is /// filled with the least significant parts of the result. Returns one if /// overflow occurred, otherwise zero. DST must be disjoint from both /// operands. - static int tcMultiply(integerPart *, const integerPart *, const integerPart *, + static int tcMultiply(WordType *, const WordType *, const WordType *, unsigned); /// DST = LHS * RHS, where DST has width the sum of the widths of the /// operands. No overflow occurs. DST must be disjoint from both /// operands. Returns the number of parts required to hold the result. - static unsigned int tcFullMultiply(integerPart *, const integerPart *, - const integerPart *, unsigned, unsigned); + static unsigned tcFullMultiply(WordType *, const WordType *, + const WordType *, unsigned, unsigned); /// If RHS is zero LHS and REMAINDER are left unchanged, return one. /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set @@ -1667,38 +1755,39 @@ public: /// SCRATCH is a bignum of the same size as the operands and result for use by /// the routine; its contents need not be initialized and are destroyed. LHS, /// REMAINDER and SCRATCH must be distinct. - static int tcDivide(integerPart *lhs, const integerPart *rhs, - integerPart *remainder, integerPart *scratch, - unsigned int parts); + static int tcDivide(WordType *lhs, const WordType *rhs, + WordType *remainder, WordType *scratch, + unsigned parts); /// Shift a bignum left COUNT bits. Shifted in bits are zero. There are no /// restrictions on COUNT. - static void tcShiftLeft(integerPart *, unsigned int parts, - unsigned int count); + static void tcShiftLeft(WordType *, unsigned parts, unsigned count); /// Shift a bignum right COUNT bits. Shifted in bits are zero. There are no /// restrictions on COUNT. - static void tcShiftRight(integerPart *, unsigned int parts, - unsigned int count); + static void tcShiftRight(WordType *, unsigned parts, unsigned count); /// The obvious AND, OR and XOR and complement operations. - static void tcAnd(integerPart *, const integerPart *, unsigned int); - static void tcOr(integerPart *, const integerPart *, unsigned int); - static void tcXor(integerPart *, const integerPart *, unsigned int); - static void tcComplement(integerPart *, unsigned int); + static void tcAnd(WordType *, const WordType *, unsigned); + static void tcOr(WordType *, const WordType *, unsigned); + static void tcXor(WordType *, const WordType *, unsigned); + static void tcComplement(WordType *, unsigned); /// Comparison (unsigned) of two bignums. - static int tcCompare(const integerPart *, const integerPart *, unsigned int); + static int tcCompare(const WordType *, const WordType *, unsigned); /// Increment a bignum in-place. Return the carry flag. - static integerPart tcIncrement(integerPart *, unsigned int); + static WordType tcIncrement(WordType *dst, unsigned parts) { + return tcAddPart(dst, 1, parts); + } /// Decrement a bignum in-place. Return the borrow flag. - static integerPart tcDecrement(integerPart *, unsigned int); + static WordType tcDecrement(WordType *dst, unsigned parts) { + return tcSubtractPart(dst, 1, parts); + } /// Set the least significant BITS and clear the rest. - static void tcSetLeastSignificantBits(integerPart *, unsigned int, - unsigned int bits); + static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits); /// \brief debug method void dump() const; @@ -1723,6 +1812,74 @@ inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } +/// \brief Unary bitwise complement operator. +/// +/// \returns an APInt that is the bitwise complement of \p v. +inline APInt operator~(APInt v) { + v.flipAllBits(); + return v; +} + +inline APInt operator&(APInt a, const APInt &b) { + a &= b; + return a; +} + +inline APInt operator&(const APInt &a, APInt &&b) { + b &= a; + return std::move(b); +} + +inline APInt operator&(APInt a, uint64_t RHS) { + a &= RHS; + return a; +} + +inline APInt operator&(uint64_t LHS, APInt b) { + b &= LHS; + return b; +} + +inline APInt operator|(APInt a, const APInt &b) { + a |= b; + return a; +} + +inline APInt operator|(const APInt &a, APInt &&b) { + b |= a; + return std::move(b); +} + +inline APInt operator|(APInt a, uint64_t RHS) { + a |= RHS; + return a; +} + +inline APInt operator|(uint64_t LHS, APInt b) { + b |= LHS; + return b; +} + +inline APInt operator^(APInt a, const APInt &b) { + a ^= b; + return a; +} + +inline APInt operator^(const APInt &a, APInt &&b) { + b ^= a; + return std::move(b); +} + +inline APInt operator^(APInt a, uint64_t RHS) { + a ^= RHS; + return a; +} + +inline APInt operator^(uint64_t LHS, APInt b) { + b ^= LHS; + return b; +} + inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { I.print(OS, true); return OS; @@ -1799,47 +1956,13 @@ inline const APInt &umax(const APInt &A, const APInt &B) { return A.ugt(B) ? A : B; } -/// \brief Check if the specified APInt has a N-bits unsigned integer value. -inline bool isIntN(unsigned N, const APInt &APIVal) { return APIVal.isIntN(N); } - -/// \brief Check if the specified APInt has a N-bits signed integer value. -inline bool isSignedIntN(unsigned N, const APInt &APIVal) { - return APIVal.isSignedIntN(N); -} - -/// \returns true if the argument APInt value is a sequence of ones starting at -/// the least significant bit with the remainder zero. -inline bool isMask(unsigned numBits, const APInt &APIVal) { - return numBits <= APIVal.getBitWidth() && - APIVal == APInt::getLowBitsSet(APIVal.getBitWidth(), numBits); -} - -/// \returns true if the argument is a non-empty sequence of ones starting at -/// the least significant bit with the remainder zero (32 bit version). -/// Ex. isMask(0x0000FFFFU) == true. -inline bool isMask(const APInt &Value) { - return (Value != 0) && ((Value + 1) & Value) == 0; -} - -/// \brief Return true if the argument APInt value contains a sequence of ones -/// with the remainder zero. -inline bool isShiftedMask(unsigned numBits, const APInt &APIVal) { - return isMask(numBits, (APIVal - APInt(numBits, 1)) | APIVal); -} - -/// \brief Returns a byte-swapped representation of the specified APInt Value. -inline APInt byteSwap(const APInt &APIVal) { return APIVal.byteSwap(); } - -/// \brief Returns the floor log base 2 of the specified APInt value. -inline unsigned logBase2(const APInt &APIVal) { return APIVal.logBase2(); } - -/// \brief Compute GCD of two APInt values. +/// \brief Compute GCD of two unsigned APInt values. /// /// This function returns the greatest common divisor of the two APInt values /// using Euclid's algorithm. /// -/// \returns the greatest common divisor of Val1 and Val2 -APInt GreatestCommonDivisor(const APInt &Val1, const APInt &Val2); +/// \returns the greatest common divisor of A and B. +APInt GreatestCommonDivisor(APInt A, APInt B); /// \brief Converts the given APInt to a double value. /// @@ -1879,83 +2002,6 @@ inline APInt RoundFloatToAPInt(float Float, unsigned width) { return RoundDoubleToAPInt(double(Float), width); } -/// \brief Arithmetic right-shift function. -/// -/// Arithmetic right-shift the APInt by shiftAmt. -inline APInt ashr(const APInt &LHS, unsigned shiftAmt) { - return LHS.ashr(shiftAmt); -} - -/// \brief Logical right-shift function. -/// -/// Logical right-shift the APInt by shiftAmt. -inline APInt lshr(const APInt &LHS, unsigned shiftAmt) { - return LHS.lshr(shiftAmt); -} - -/// \brief Left-shift function. -/// -/// Left-shift the APInt by shiftAmt. -inline APInt shl(const APInt &LHS, unsigned shiftAmt) { - return LHS.shl(shiftAmt); -} - -/// \brief Signed division function for APInt. -/// -/// Signed divide APInt LHS by APInt RHS. -inline APInt sdiv(const APInt &LHS, const APInt &RHS) { return LHS.sdiv(RHS); } - -/// \brief Unsigned division function for APInt. -/// -/// Unsigned divide APInt LHS by APInt RHS. -inline APInt udiv(const APInt &LHS, const APInt &RHS) { return LHS.udiv(RHS); } - -/// \brief Function for signed remainder operation. -/// -/// Signed remainder operation on APInt. -inline APInt srem(const APInt &LHS, const APInt &RHS) { return LHS.srem(RHS); } - -/// \brief Function for unsigned remainder operation. -/// -/// Unsigned remainder operation on APInt. -inline APInt urem(const APInt &LHS, const APInt &RHS) { return LHS.urem(RHS); } - -/// \brief Function for multiplication operation. -/// -/// Performs multiplication on APInt values. -inline APInt mul(const APInt &LHS, const APInt &RHS) { return LHS * RHS; } - -/// \brief Function for addition operation. -/// -/// Performs addition on APInt values. -inline APInt add(const APInt &LHS, const APInt &RHS) { return LHS + RHS; } - -/// \brief Function for subtraction operation. -/// -/// Performs subtraction on APInt values. -inline APInt sub(const APInt &LHS, const APInt &RHS) { return LHS - RHS; } - -/// \brief Bitwise AND function for APInt. -/// -/// Performs bitwise AND operation on APInt LHS and -/// APInt RHS. -inline APInt And(const APInt &LHS, const APInt &RHS) { return LHS & RHS; } - -/// \brief Bitwise OR function for APInt. -/// -/// Performs bitwise OR operation on APInt LHS and APInt RHS. -inline APInt Or(const APInt &LHS, const APInt &RHS) { return LHS | RHS; } - -/// \brief Bitwise XOR function for APInt. -/// -/// Performs bitwise XOR operation on APInt. -inline APInt Xor(const APInt &LHS, const APInt &RHS) { return LHS ^ RHS; } - -/// \brief Bitwise complement function. -/// -/// Performs a bitwise complement operation on APInt. -inline APInt Not(const APInt &APIVal) { return ~APIVal; } - } // End of APIntOps namespace // See friend declaration above. This additional declaration is required in diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h index 813b3686d6b1..5b6dfa4a4b64 100644 --- a/include/llvm/ADT/APSInt.h +++ b/include/llvm/ADT/APSInt.h @@ -235,19 +235,16 @@ public: assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); return APSInt(static_cast(*this) & RHS, IsUnsigned); } - APSInt And(const APSInt &RHS) const { return this->operator&(RHS); } APSInt operator|(const APSInt& RHS) const { assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); return APSInt(static_cast(*this) | RHS, IsUnsigned); } - APSInt Or(const APSInt &RHS) const { return this->operator|(RHS); } APSInt operator^(const APSInt &RHS) const { assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); return APSInt(static_cast(*this) ^ RHS, IsUnsigned); } - APSInt Xor(const APSInt &RHS) const { return this->operator^(RHS); } APSInt operator*(const APSInt& RHS) const { assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index b3fe31f4a806..6b35d0aec8b2 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -487,6 +487,18 @@ namespace llvm { return ArrayRef(Arr); } + /// Construct a MutableArrayRef from a single element. + template + MutableArrayRef makeMutableArrayRef(T &OneElt) { + return OneElt; + } + + /// Construct a MutableArrayRef from a pointer and length. + template + MutableArrayRef makeMutableArrayRef(T *data, size_t length) { + return MutableArrayRef(data, length); + } + /// @} /// @name ArrayRef Comparison Operators /// @{ diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index cf3756d0d9c1..8240d01ae977 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -161,6 +161,17 @@ public: return -1; } + /// find_first_unset - Returns the index of the first unset bit, -1 if all + /// of the bits are set. + int find_first_unset() const { + for (unsigned i = 0; i < NumBitWords(size()); ++i) + if (Bits[i] != ~0UL) { + unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Bits[i]); + return Result < size() ? Result : -1; + } + return -1; + } + /// find_next - Returns the index of the next set bit following the /// "Prev" bit. Returns -1 if the next set bit is not found. int find_next(unsigned Prev) const { @@ -184,6 +195,30 @@ public: return -1; } + /// find_next_unset - Returns the index of the next usnet bit following the + /// "Prev" bit. Returns -1 if all remaining bits are set. + int find_next_unset(unsigned Prev) const { + ++Prev; + if (Prev >= Size) + return -1; + + unsigned WordPos = Prev / BITWORD_SIZE; + unsigned BitPos = Prev % BITWORD_SIZE; + BitWord Copy = Bits[WordPos]; + // Mask in previous bits. + BitWord Mask = (1 << BitPos) - 1; + Copy |= Mask; + + if (Copy != ~0UL) + return next_unset_in_word(WordPos, Copy); + + // Check subsequent words. + for (unsigned i = WordPos + 1; i < NumBitWords(size()); ++i) + if (Bits[i] != ~0UL) + return next_unset_in_word(i, Bits[i]); + return -1; + } + /// clear - Clear all bits. void clear() { Size = 0; @@ -503,6 +538,11 @@ public: } private: + int next_unset_in_word(int WordIndex, BitWord Word) const { + unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word); + return Result < size() ? Result : -1; + } + unsigned NumBitWords(unsigned S) const { return (S + BITWORD_SIZE-1) / BITWORD_SIZE; } @@ -539,7 +579,8 @@ private: } void init_words(BitWord *B, unsigned NumWords, bool t) { - memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); + if (NumWords > 0) + memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); } template diff --git a/include/llvm/ADT/BreadthFirstIterator.h b/include/llvm/ADT/BreadthFirstIterator.h new file mode 100644 index 000000000000..eaeecb6e057f --- /dev/null +++ b/include/llvm/ADT/BreadthFirstIterator.h @@ -0,0 +1,164 @@ +//===- llvm/ADT/BreadthFirstIterator.h - Breadth First iterator -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file builds on the ADT/GraphTraits.h file to build a generic breadth +// first graph iterator. This file exposes the following functions/types: +// +// bf_begin/bf_end/bf_iterator +// * Normal breadth-first iteration - visit a graph level-by-level. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_BREADTHFIRSTITERATOR_H +#define LLVM_ADT_BREADTHFIRSTITERATOR_H + +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/iterator_range.h" +#include +#include +#include +#include + +namespace llvm { + +// bf_iterator_storage - A private class which is used to figure out where to +// store the visited set. We only provide a non-external variant for now. +template class bf_iterator_storage { +public: + SetType Visited; +}; + +// The visited state for the iteration is a simple set. +template +using bf_iterator_default_set = SmallPtrSet; + +// Generic Breadth first search iterator. +template ::NodeRef>, + class GT = GraphTraits> +class bf_iterator + : public std::iterator, + public bf_iterator_storage { + typedef std::iterator super; + + typedef typename GT::NodeRef NodeRef; + typedef typename GT::ChildIteratorType ChildItTy; + + // First element is the node reference, second is the next child to visit. + typedef std::pair> QueueElement; + + // Visit queue - used to maintain BFS ordering. + // Optional<> because we need markers for levels. + std::queue> VisitQueue; + + // Current level. + unsigned Level; + +private: + inline bf_iterator(NodeRef Node) { + this->Visited.insert(Node); + Level = 0; + + // Also, insert a dummy node as marker. + VisitQueue.push(QueueElement(Node, None)); + VisitQueue.push(None); + } + + inline bf_iterator() = default; + + inline void toNext() { + Optional Head = VisitQueue.front(); + QueueElement H = Head.getValue(); + NodeRef Node = H.first; + Optional &ChildIt = H.second; + + if (!ChildIt) + ChildIt.emplace(GT::child_begin(Node)); + while (*ChildIt != GT::child_end(Node)) { + NodeRef Next = *(*ChildIt)++; + + // Already visited? + if (this->Visited.insert(Next).second) + VisitQueue.push(QueueElement(Next, None)); + } + VisitQueue.pop(); + + // Go to the next element skipping markers if needed. + if (!VisitQueue.empty()) { + Head = VisitQueue.front(); + if (Head != None) + return; + Level += 1; + VisitQueue.pop(); + + // Don't push another marker if this is the last + // element. + if (!VisitQueue.empty()) + VisitQueue.push(None); + } + } + +public: + typedef typename super::pointer pointer; + + // Provide static begin and end methods as our public "constructors" + static bf_iterator begin(const GraphT &G) { + return bf_iterator(GT::getEntryNode(G)); + } + + static bf_iterator end(const GraphT &G) { return bf_iterator(); } + + bool operator==(const bf_iterator &RHS) const { + return VisitQueue == RHS.VisitQueue; + } + + bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); } + + const NodeRef &operator*() const { return VisitQueue.front()->first; } + + // This is a nonstandard operator-> that dereferenfces the pointer an extra + // time so that you can actually call methods on the node, because the + // contained type is a pointer. + NodeRef operator->() const { return **this; } + + bf_iterator &operator++() { // Pre-increment + toNext(); + return *this; + } + + bf_iterator operator++(int) { // Post-increment + bf_iterator ItCopy = *this; + ++*this; + return ItCopy; + } + + unsigned getLevel() const { return Level; } +}; + +// Provide global constructors that automatically figure out correct types. +template bf_iterator bf_begin(const T &G) { + return bf_iterator::begin(G); +} + +template bf_iterator bf_end(const T &G) { + return bf_iterator::end(G); +} + +// Provide an accessor method to use them in range-based patterns. +template iterator_range> breadth_first(const T &G) { + return make_range(bf_begin(G), bf_end(G)); +} + +} // end namespace llvm + +#endif // LLVM_ADT_BREADTHFIRSTITERATOR_H diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 0b4b09d4b733..fd8d3bf368a8 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -53,6 +53,9 @@ class DenseMapIterator; template class DenseMapBase : public DebugEpochBase { + template + using const_arg_type_t = typename const_pointer_or_const_ref::type; + public: typedef unsigned size_type; typedef KeyT key_type; @@ -119,18 +122,18 @@ public: } /// Return 1 if the specified key is in the map, 0 otherwise. - size_type count(const KeyT &Val) const { + size_type count(const_arg_type_t Val) const { const BucketT *TheBucket; return LookupBucketFor(Val, TheBucket) ? 1 : 0; } - iterator find(const KeyT &Val) { + iterator find(const_arg_type_t Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) return iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } - const_iterator find(const KeyT &Val) const { + const_iterator find(const_arg_type_t Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) return const_iterator(TheBucket, getBucketsEnd(), *this, true); @@ -159,7 +162,7 @@ public: /// lookup - Return the entry for the specified key, or a default /// constructed value if no such entry exists. - ValueT lookup(const KeyT &Val) const { + ValueT lookup(const_arg_type_t Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) return TheBucket->getSecond(); @@ -389,6 +392,8 @@ protected: return KeyInfoT::getHashValue(Val); } static const KeyT getEmptyKey() { + static_assert(std::is_base_of::value, + "Must pass the derived type to this template!"); return KeyInfoT::getEmptyKey(); } static const KeyT getTombstoneKey() { diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h index a844ebcccf5b..bb973ac65063 100644 --- a/include/llvm/ADT/DenseMapInfo.h +++ b/include/llvm/ADT/DenseMapInfo.h @@ -60,6 +60,16 @@ template<> struct DenseMapInfo { } }; +// Provide DenseMapInfo for unsigned shorts. +template <> struct DenseMapInfo { + static inline unsigned short getEmptyKey() { return 0xFFFF; } + static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; } + static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; } + static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) { + return LHS == RHS; + } +}; + // Provide DenseMapInfo for unsigned ints. template<> struct DenseMapInfo { static inline unsigned getEmptyKey() { return ~0U; } @@ -95,6 +105,14 @@ template<> struct DenseMapInfo { } }; +// Provide DenseMapInfo for shorts. +template <> struct DenseMapInfo { + static inline short getEmptyKey() { return 0x7FFF; } + static inline short getTombstoneKey() { return -0x7FFF - 1; } + static unsigned getHashValue(const short &Val) { return Val * 37U; } + static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; } +}; + // Provide DenseMapInfo for ints. template<> struct DenseMapInfo { static inline int getEmptyKey() { return 0x7fffffff; } diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h index b25d3b7cba6f..fcf304c3ecc4 100644 --- a/include/llvm/ADT/DenseSet.h +++ b/include/llvm/ADT/DenseSet.h @@ -48,6 +48,8 @@ class DenseSetImpl { static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT), "DenseMap buckets unexpectedly large!"); MapTy TheMap; + template + using const_arg_type_t = typename const_pointer_or_const_ref::type; public: typedef ValueT key_type; @@ -78,7 +80,7 @@ public: } /// Return 1 if the specified key is in the set, 0 otherwise. - size_type count(const ValueT &V) const { + size_type count(const_arg_type_t V) const { return TheMap.count(V); } @@ -90,9 +92,12 @@ public: // Iterators. + class ConstIterator; + class Iterator { typename MapTy::iterator I; friend class DenseSetImpl; + friend class ConstIterator; public: typedef typename MapTy::iterator::difference_type difference_type; @@ -101,20 +106,24 @@ public: typedef value_type &reference; typedef std::forward_iterator_tag iterator_category; + Iterator() = default; Iterator(const typename MapTy::iterator &i) : I(i) {} ValueT &operator*() { return I->getFirst(); } + const ValueT &operator*() const { return I->getFirst(); } ValueT *operator->() { return &I->getFirst(); } + const ValueT *operator->() const { return &I->getFirst(); } Iterator& operator++() { ++I; return *this; } Iterator operator++(int) { auto T = *this; ++I; return T; } - bool operator==(const Iterator& X) const { return I == X.I; } - bool operator!=(const Iterator& X) const { return I != X.I; } + bool operator==(const ConstIterator& X) const { return I == X.I; } + bool operator!=(const ConstIterator& X) const { return I != X.I; } }; class ConstIterator { typename MapTy::const_iterator I; friend class DenseSet; + friend class Iterator; public: typedef typename MapTy::const_iterator::difference_type difference_type; @@ -123,10 +132,14 @@ public: typedef value_type &reference; typedef std::forward_iterator_tag iterator_category; + ConstIterator(const Iterator &B) : I(B.I) {} + + ConstIterator() = default; + ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} - const ValueT &operator*() { return I->getFirst(); } - const ValueT *operator->() { return &I->getFirst(); } + const ValueT &operator*() const { return I->getFirst(); } + const ValueT *operator->() const { return &I->getFirst(); } ConstIterator& operator++() { ++I; return *this; } ConstIterator operator++(int) { auto T = *this; ++I; return T; } @@ -143,8 +156,8 @@ public: const_iterator begin() const { return ConstIterator(TheMap.begin()); } const_iterator end() const { return ConstIterator(TheMap.end()); } - iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); } - const_iterator find(const ValueT &V) const { + iterator find(const_arg_type_t V) { return Iterator(TheMap.find(V)); } + const_iterator find(const_arg_type_t V) const { return ConstIterator(TheMap.find(V)); } diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h index c54573204588..b020d48cb3f0 100644 --- a/include/llvm/ADT/DepthFirstIterator.h +++ b/include/llvm/ADT/DepthFirstIterator.h @@ -135,7 +135,7 @@ private: } } this->Visited.completed(Node); - + // Oops, ran out of successors... go up a level on the stack. VisitStack.pop_back(); } while (!VisitStack.empty()); diff --git a/include/llvm/ADT/GraphTraits.h b/include/llvm/ADT/GraphTraits.h index 29bbcb010eee..2c88c4271b48 100644 --- a/include/llvm/ADT/GraphTraits.h +++ b/include/llvm/ADT/GraphTraits.h @@ -18,6 +18,8 @@ #ifndef LLVM_ADT_GRAPHTRAITS_H #define LLVM_ADT_GRAPHTRAITS_H +#include "llvm/ADT/iterator_range.h" + namespace llvm { // GraphTraits - This class should be specialized by different graph types... @@ -86,6 +88,33 @@ struct Inverse { // inverse falls back to the original graph. template struct GraphTraits>> : GraphTraits {}; +// Provide iterator ranges for the graph traits nodes and children +template +iterator_range::nodes_iterator> +nodes(const GraphType &G) { + return make_range(GraphTraits::nodes_begin(G), + GraphTraits::nodes_end(G)); +} +template +iterator_range>::nodes_iterator> +inverse_nodes(const GraphType &G) { + return make_range(GraphTraits>::nodes_begin(G), + GraphTraits>::nodes_end(G)); +} + +template +iterator_range::ChildIteratorType> +children(const typename GraphTraits::NodeRef &G) { + return make_range(GraphTraits::child_begin(G), + GraphTraits::child_end(G)); +} + +template +iterator_range>::ChildIteratorType> +inverse_children(const typename GraphTraits::NodeRef &G) { + return make_range(GraphTraits>::child_begin(G), + GraphTraits>::child_end(G)); +} } // End llvm namespace #endif diff --git a/include/llvm/ADT/None.h b/include/llvm/ADT/None.h index d69ec17c15f9..c7a99c61994e 100644 --- a/include/llvm/ADT/None.h +++ b/include/llvm/ADT/None.h @@ -19,8 +19,9 @@ namespace llvm { /// \brief A simple null object to allow implicit construction of Optional /// and similar types without having to spell out the specialization's name. -enum class NoneType { None }; -const NoneType None = None; +// (constant value 1 in an attempt to workaround MSVC build issue... ) +enum class NoneType { None = 1 }; +const NoneType None = NoneType::None; } #endif diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index a8ac18645f3a..9eb15524c0f3 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -31,7 +31,7 @@ template struct PointerUnionTypeSelectorReturn { /// Get a type based on whether two types are the same or not. /// /// For: -/// +/// /// \code /// typedef typename PointerUnionTypeSelector::Return Ret; /// \endcode @@ -190,17 +190,17 @@ public: }; template -static bool operator==(PointerUnion lhs, PointerUnion rhs) { +bool operator==(PointerUnion lhs, PointerUnion rhs) { return lhs.getOpaqueValue() == rhs.getOpaqueValue(); } template -static bool operator!=(PointerUnion lhs, PointerUnion rhs) { +bool operator!=(PointerUnion lhs, PointerUnion rhs) { return lhs.getOpaqueValue() != rhs.getOpaqueValue(); } template -static bool operator<(PointerUnion lhs, PointerUnion rhs) { +bool operator<(PointerUnion lhs, PointerUnion rhs) { return lhs.getOpaqueValue() < rhs.getOpaqueValue(); } diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index e519b5c07964..8fc08eb252eb 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -268,6 +268,10 @@ inverse_post_order_ext(const T &G, SetType &S) { // with a postorder iterator to build the data structures). The moral of this // story is: Don't create more ReversePostOrderTraversal classes than necessary. // +// Because it does the traversal in its constructor, it won't invalidate when +// BasicBlocks are removed, *but* it may contain erased blocks. Some places +// rely on this behavior (i.e. GVN). +// // This class should be used like this: // { // ReversePostOrderTraversal RPOT(FuncPtr); // Expensive to create diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index ec121e0d55cd..15945adbe589 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -23,11 +23,13 @@ #include // for qsort #include #include +#include #include #include #include // for std::pair #include "llvm/ADT/Optional.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/Compiler.h" @@ -44,6 +46,10 @@ namespace detail { template using IterOfRange = decltype(std::begin(std::declval())); +template +using ValueOfRange = typename std::remove_reference()))>::type; + } // End detail namespace //===----------------------------------------------------------------------===// @@ -123,7 +129,7 @@ inline void deleter(T *Ptr) { //===----------------------------------------------------------------------===// // mapped_iterator - This is a simple iterator adapter that causes a function to -// be dereferenced whenever operator* is invoked on the iterator. +// be applied whenever operator* is invoked on the iterator. // template class mapped_iterator { @@ -134,9 +140,8 @@ public: iterator_category; typedef typename std::iterator_traits::difference_type difference_type; - typedef typename std::result_of< - UnaryFunc(decltype(*std::declval()))> - ::type value_type; + typedef decltype(std::declval()(*std::declval())) + value_type; typedef void pointer; //typedef typename UnaryFunc::result_type *pointer; @@ -356,65 +361,126 @@ template struct index_sequence; template struct index_sequence_for; namespace detail { -template class zip_first { -public: - typedef std::input_iterator_tag iterator_category; - typedef std::tuple())...> value_type; +using std::declval; + +// We have to alias this since inlining the actual type at the usage site +// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017. +template struct ZipTupleType { + typedef std::tuple())...> type; +}; + +template +using zip_traits = iterator_facade_base< + ZipType, typename std::common_type::iterator_category...>::type, + // ^ TODO: Implement random access methods. + typename ZipTupleType::type, + typename std::iterator_traits>::type>::difference_type, + // ^ FIXME: This follows boost::make_zip_iterator's assumption that all + // inner iterators have the same difference_type. It would fail if, for + // instance, the second field's difference_type were non-numeric while the + // first is. + typename ZipTupleType::type *, + typename ZipTupleType::type>; + +template +struct zip_common : public zip_traits { + using Base = zip_traits; + using value_type = typename Base::value_type; + std::tuple iterators; -private: - template value_type deres(index_sequence) { +protected: + template value_type deref(index_sequence) const { return value_type(*std::get(iterators)...); } - template decltype(iterators) tup_inc(index_sequence) { + template + decltype(iterators) tup_inc(index_sequence) const { return std::tuple(std::next(std::get(iterators))...); } + template + decltype(iterators) tup_dec(index_sequence) const { + return std::tuple(std::prev(std::get(iterators))...); + } + public: - value_type operator*() { return deres(index_sequence_for{}); } + zip_common(Iters &&... ts) : iterators(std::forward(ts)...) {} + + value_type operator*() { return deref(index_sequence_for{}); } - void operator++() { iterators = tup_inc(index_sequence_for{}); } + const value_type operator*() const { + return deref(index_sequence_for{}); + } - bool operator!=(const zip_first &other) const { - return std::get<0>(iterators) != std::get<0>(other.iterators); + ZipType &operator++() { + iterators = tup_inc(index_sequence_for{}); + return *reinterpret_cast(this); } - zip_first(Iters &&... ts) : iterators(std::forward(ts)...) {} + + ZipType &operator--() { + static_assert(Base::IsBidirectional, + "All inner iterators must be at least bidirectional."); + iterators = tup_dec(index_sequence_for{}); + return *reinterpret_cast(this); + } +}; + +template +struct zip_first : public zip_common, Iters...> { + using Base = zip_common, Iters...>; + + bool operator==(const zip_first &other) const { + return std::get<0>(this->iterators) == std::get<0>(other.iterators); + } + + zip_first(Iters &&... ts) : Base(std::forward(ts)...) {} }; -template class zip_shortest : public zip_first { +template +class zip_shortest : public zip_common, Iters...> { template - bool test(const zip_first &other, index_sequence) const { + bool test(const zip_shortest &other, index_sequence) const { return all_of(std::initializer_list{std::get(this->iterators) != std::get(other.iterators)...}, identity{}); } public: - bool operator!=(const zip_first &other) const { - return test(other, index_sequence_for{}); + using Base = zip_common, Iters...>; + + bool operator==(const zip_shortest &other) const { + return !test(other, index_sequence_for{}); } - zip_shortest(Iters &&... ts) - : zip_first(std::forward(ts)...) {} + + zip_shortest(Iters &&... ts) : Base(std::forward(ts)...) {} }; template