Movatterモバイル変換

Go to the documentation of this file.

1//==- llvm/CodeGen/SelectionDAGAddressAnalysis.cpp - DAG Address Analysis --==//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

9#include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"

10#include "llvm/Analysis/MemoryLocation.h"

11#include "llvm/CodeGen/ISDOpcodes.h"

12#include "llvm/CodeGen/MachineFrameInfo.h"

13#include "llvm/CodeGen/MachineFunction.h"

14#include "llvm/CodeGen/SelectionDAG.h"

15#include "llvm/CodeGen/SelectionDAGNodes.h"

16#include "llvm/CodeGen/TargetLowering.h"

17#include "llvm/IR/GlobalAlias.h"

18#include "llvm/Support/Casting.h"

19#include "llvm/Support/Debug.h"

20#include <cstdint>

22using namespacellvm;

24boolBaseIndexOffset::equalBaseIndex(constBaseIndexOffset &Other,

25constSelectionDAG &DAG,

26 int64_t &Off) const{

27// Conservatively fail if we a match failed..

28if (!Base.getNode() || !Other.Base.getNode())

29returnfalse;

30if (!hasValidOffset() || !Other.hasValidOffset())

31returnfalse;

32// Initial Offset difference.

33 Off = *Other.Offset - *Offset;

35if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) {

36// Trivial match.

37if (Other.Base ==Base)

38returntrue;

40// Match GlobalAddresses

41if (auto *A = dyn_cast<GlobalAddressSDNode>(Base)) {

42if (auto *B = dyn_cast<GlobalAddressSDNode>(Other.Base))

43if (A->getGlobal() ==B->getGlobal()) {

44 Off +=B->getOffset() -A->getOffset();

45returntrue;

46 }

48returnfalse;

49 }

51// Match Constants

52if (auto *A = dyn_cast<ConstantPoolSDNode>(Base)) {

53if (auto *B = dyn_cast<ConstantPoolSDNode>(Other.Base)) {

54bool IsMatch =

55A->isMachineConstantPoolEntry() ==B->isMachineConstantPoolEntry();

56if (IsMatch) {

57if (A->isMachineConstantPoolEntry())

58 IsMatch =A->getMachineCPVal() ==B->getMachineCPVal();

59else

60 IsMatch =A->getConstVal() ==B->getConstVal();

61 }

62if (IsMatch) {

63 Off +=B->getOffset() -A->getOffset();

64returntrue;

65 }

66 }

68returnfalse;

69 }

71// Match FrameIndexes.

72if (auto *A = dyn_cast<FrameIndexSDNode>(Base))

73if (auto *B = dyn_cast<FrameIndexSDNode>(Other.Base)) {

74// Equal FrameIndexes - offsets are directly comparable.

75if (A->getIndex() ==B->getIndex())

76returntrue;

77// Non-equal FrameIndexes - If both frame indices are fixed

78// we know their relative offsets and can compare them. Otherwise

79// we must be conservative.

80constMachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();

81if (MFI.isFixedObjectIndex(A->getIndex()) &&

82 MFI.isFixedObjectIndex(B->getIndex())) {

83 Off += MFI.getObjectOffset(B->getIndex()) -

84 MFI.getObjectOffset(A->getIndex());

85returntrue;

86 }

87 }

88 }

90returnfalse;

91}

93boolBaseIndexOffset::computeAliasing(constSDNode *Op0,

94constLocationSize NumBytes0,

95constSDNode *Op1,

96constLocationSize NumBytes1,

97constSelectionDAG &DAG,bool &IsAlias) {

98BaseIndexOffset BasePtr0 =match(Op0, DAG);

99if (!BasePtr0.getBase().getNode())

100returnfalse;

101

102BaseIndexOffset BasePtr1 =match(Op1, DAG);

103if (!BasePtr1.getBase().getNode())

104returnfalse;

105

106 int64_t PtrDiff;

107if (BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff)) {

108// If the size of memory access is unknown, do not use it to analysis.

109// BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the

110// following situations arise:

111if (PtrDiff >= 0 && NumBytes0.hasValue() && !NumBytes0.isScalable()) {

112// [----BasePtr0----]

113// [---BasePtr1--]

114// ========PtrDiff========>

115 IsAlias = !(static_cast<int64_t>(NumBytes0.getValue().getFixedValue()) <=

116 PtrDiff);

117returntrue;

118 }

119if (PtrDiff < 0 && NumBytes1.hasValue() && !NumBytes1.isScalable()) {

120// [----BasePtr0----]

121// [---BasePtr1--]

122// =====(-PtrDiff)====>

123 IsAlias = !((PtrDiff +static_cast<int64_t>(

124 NumBytes1.getValue().getFixedValue())) <= 0);

125returntrue;

126 }

127returnfalse;

128 }

129// If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be

130// able to calculate their relative offset if at least one arises

131// from an alloca. However, these allocas cannot overlap and we

132// can infer there is no alias.

133if (auto *A = dyn_cast<FrameIndexSDNode>(BasePtr0.getBase()))

134if (auto *B = dyn_cast<FrameIndexSDNode>(BasePtr1.getBase())) {

135MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();

136// If the base are the same frame index but the we couldn't find a

137// constant offset, (indices are different) be conservative.

138if (A->getIndex() !=B->getIndex() && (!MFI.isFixedObjectIndex(A->getIndex()) ||

139 !MFI.isFixedObjectIndex(B->getIndex()))) {

140 IsAlias =false;

141returntrue;

142 }

143 }

144

145bool IsFI0 = isa<FrameIndexSDNode>(BasePtr0.getBase());

146bool IsFI1 = isa<FrameIndexSDNode>(BasePtr1.getBase());

147bool IsGV0 = isa<GlobalAddressSDNode>(BasePtr0.getBase());

148bool IsGV1 = isa<GlobalAddressSDNode>(BasePtr1.getBase());

149bool IsCV0 = isa<ConstantPoolSDNode>(BasePtr0.getBase());

150bool IsCV1 = isa<ConstantPoolSDNode>(BasePtr1.getBase());

151

152if ((IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) {

153// We can derive NoAlias In case of mismatched base types.

154if (IsFI0 != IsFI1 || IsGV0 != IsGV1 || IsCV0 != IsCV1) {

155 IsAlias =false;

156returntrue;

157 }

158if (IsGV0 && IsGV1) {

159auto *GV0 = cast<GlobalAddressSDNode>(BasePtr0.getBase())->getGlobal();

160auto *GV1 = cast<GlobalAddressSDNode>(BasePtr1.getBase())->getGlobal();

161// It doesn't make sense to access one global value using another globals

162// values address, so we can assume that there is no aliasing in case of

163// two different globals (unless we have symbols that may indirectly point

164// to each other).

165// FIXME: This is perhaps a bit too defensive. We could try to follow the

166// chain with aliasee information for GlobalAlias variables to find out if

167// we indirect symbols may alias or not.

168if (GV0 != GV1 && !isa<GlobalAlias>(GV0) && !isa<GlobalAlias>(GV1)) {

169 IsAlias =false;

170returntrue;

171 }

172 }

173 }

174returnfalse;// Cannot determine whether the pointers alias.

175}

176

177boolBaseIndexOffset::contains(constSelectionDAG &DAG, int64_t BitSize,

178constBaseIndexOffset &Other,

179 int64_t OtherBitSize, int64_t &BitOffset) const{

180 int64_t Offset;

181if (!equalBaseIndex(Other, DAG, Offset))

182returnfalse;

183if (Offset >= 0) {

184// Other is after *this:

185// [-------*this---------]

186// [---Other--]

187// ==Offset==>

188 BitOffset = 8 * Offset;

189return BitOffset + OtherBitSize <= BitSize;

190 }

191// Other starts strictly before *this, it cannot be fully contained.

192// [-------*this---------]

193// [--Other--]

194returnfalse;

195}

196

197/// Parses tree in Ptr for base, index, offset addresses.

198staticBaseIndexOffset matchLSNode(constLSBaseSDNode *N,

199constSelectionDAG &DAG) {

200SDValue Ptr =N->getBasePtr();

201

202// (((B + I*M) + c)) + c ...

203SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(Ptr);

204SDValue Index =SDValue();

205 int64_tOffset = 0;

206bool IsIndexSignExt =false;

207

208// pre-inc/pre-dec ops are components of EA.

209if (N->getAddressingMode() ==ISD::PRE_INC) {

210if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))

211Offset +=C->getSExtValue();

212else// If unknown, give up now.

213returnBaseIndexOffset(SDValue(),SDValue(), 0,false);

214 }elseif (N->getAddressingMode() ==ISD::PRE_DEC) {

215if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))

216Offset -=C->getSExtValue();

217else// If unknown, give up now.

218returnBaseIndexOffset(SDValue(),SDValue(), 0,false);

219 }

220

221// Consume constant adds & ors with appropriate masking.

222while (true) {

223switch (Base->getOpcode()) {

224caseISD::OR:

225// Only consider ORs which act as adds.

226if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1)))

227if (DAG.MaskedValueIsZero(Base->getOperand(0),C->getAPIntValue())) {

228Offset +=C->getSExtValue();

229Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0));

230continue;

231 }

232break;

233caseISD::ADD:

234if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {

235Offset +=C->getSExtValue();

236Base = DAG.getTargetLoweringInfo().unwrapAddress(Base->getOperand(0));

237continue;

238 }

239break;

240caseISD::LOAD:

241caseISD::STORE: {

242auto *LSBase = cast<LSBaseSDNode>(Base.getNode());

243unsignedint IndexResNo = (Base->getOpcode() ==ISD::LOAD) ? 1 : 0;

244if (LSBase->isIndexed() &&Base.getResNo() == IndexResNo)

245if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) {

246auto Off =C->getSExtValue();

247if (LSBase->getAddressingMode() ==ISD::PRE_DEC ||

248 LSBase->getAddressingMode() ==ISD::POST_DEC)

249Offset -= Off;

250else

251Offset += Off;

252Base = DAG.getTargetLoweringInfo().unwrapAddress(LSBase->getBasePtr());

253continue;

254 }

255break;

256 }

257 }

258// If we get here break out of the loop.

259break;

260 }

261

262if (Base->getOpcode() ==ISD::ADD) {

263// TODO: The following code appears to be needless as it just

264// bails on some Ptrs early, reducing the cases where we

265// find equivalence. We should be able to remove this.

266// Inside a loop the current BASE pointer is calculated using an ADD and a

267// MUL instruction. In this case Base is the actual BASE pointer.

268// (i64 add (i64 %array_ptr)

269// (i64 mul (i64 %induction_var)

270// (i64 %element_size)))

271if (Base->getOperand(1)->getOpcode() ==ISD::MUL)

272returnBaseIndexOffset(Base, Index,Offset, IsIndexSignExt);

273

274// Look at Base + Index + Offset cases.

275 Index =Base->getOperand(1);

276SDValue PotentialBase =Base->getOperand(0);

277

278// Skip signextends.

279if (Index->getOpcode() ==ISD::SIGN_EXTEND) {

280 Index = Index->getOperand(0);

281 IsIndexSignExt =true;

282 }

283

284// Check if Index Offset pattern

285if (Index->getOpcode() !=ISD::ADD ||

286 !isa<ConstantSDNode>(Index->getOperand(1)))

287returnBaseIndexOffset(PotentialBase, Index,Offset, IsIndexSignExt);

288

289Offset += cast<ConstantSDNode>(Index->getOperand(1))->getSExtValue();

290 Index = Index->getOperand(0);

291if (Index->getOpcode() ==ISD::SIGN_EXTEND) {

292 Index = Index->getOperand(0);

293 IsIndexSignExt =true;

294 }else

295 IsIndexSignExt =false;

296Base = PotentialBase;

297 }

298returnBaseIndexOffset(Base, Index,Offset, IsIndexSignExt);

299}

300

301BaseIndexOffset BaseIndexOffset::match(constSDNode *N,

302constSelectionDAG &DAG) {

303if (constauto *LS0 = dyn_cast<LSBaseSDNode>(N))

304returnmatchLSNode(LS0, DAG);

305if (constauto *LN = dyn_cast<LifetimeSDNode>(N)) {

306if (LN->hasOffset())

307returnBaseIndexOffset(LN->getOperand(1),SDValue(), LN->getOffset(),

308false);

309returnBaseIndexOffset(LN->getOperand(1),SDValue(),false);

310 }

311returnBaseIndexOffset();

312}

313

314#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

315

316LLVM_DUMP_METHODvoidBaseIndexOffset::dump() const{

317print(dbgs());

318}

319

320voidBaseIndexOffset::print(raw_ostream&OS) const{

321OS <<"BaseIndexOffset base=[";

322Base->print(OS);

323OS <<"] index=[";

324if (Index)

325 Index->print(OS);

326OS <<"] offset=" << Offset;

327}

328

329#endif

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

Casting.h

LLVM_DUMP_METHOD

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

Definition:Compiler.h:622

Debug.h

Other

std::optional< std::vector< StOtherPiece > > Other

Definition:ELFYAML.cpp:1315

This file provides utility analysis objects describing memory locations.

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

matchLSNode

static BaseIndexOffset matchLSNode(const LSBaseSDNode *N, const SelectionDAG &DAG)

Parses tree in Ptr for base, index, offset addresses.

Definition:SelectionDAGAddressAnalysis.cpp:198

SelectionDAGAddressAnalysis.h

SelectionDAGNodes.h

SelectionDAG.h

Ptr

@ Ptr

Definition:TargetLibraryInfo.cpp:77

TargetLowering.h

This file describes how to lower LLVM code to machine code.

llvm::BaseIndexOffset::contains

bool contains(const SelectionDAG &DAG, int64_t BitSize, const BaseIndexOffset &Other, int64_t OtherBitSize, int64_t &BitOffset) const

Definition:SelectionDAGAddressAnalysis.cpp:177

llvm::BaseIndexOffset::print

void print(raw_ostream &OS) const

Definition:SelectionDAGAddressAnalysis.cpp:320

llvm::BaseIndexOffset::match

static BaseIndexOffset match(const SDNode *N, const SelectionDAG &DAG)

Parses tree in N for base, index, offset addresses.

Definition:SelectionDAGAddressAnalysis.cpp:301

llvm::BaseIndexOffset::computeAliasing

static bool computeAliasing(const SDNode *Op0, const LocationSize NumBytes0, const SDNode *Op1, const LocationSize NumBytes1, const SelectionDAG &DAG, bool &IsAlias)

Definition:SelectionDAGAddressAnalysis.cpp:93

llvm::BaseIndexOffset::dump

void dump() const

Definition:SelectionDAGAddressAnalysis.cpp:316

llvm::BaseIndexOffset::equalBaseIndex

bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG, int64_t &Off) const

Definition:SelectionDAGAddressAnalysis.cpp:24

llvm::GISelAddressing::BaseIndexOffset

Helper struct to store a base, index and offset that forms an address.

Definition:LoadStoreOpt.h:38

llvm::GISelAddressing::BaseIndexOffset::BaseIndexOffset

BaseIndexOffset()=default

llvm::GISelAddressing::BaseIndexOffset::hasValidOffset

bool hasValidOffset() const

Definition:LoadStoreOpt.h:53

llvm::GISelAddressing::BaseIndexOffset::getBase

Definition:LoadStoreOpt.h:46

llvm::LSBaseSDNode

Base class for LoadSDNode and StoreSDNode.

Definition:SelectionDAGNodes.h:2431

llvm::LocationSize

Definition:MemoryLocation.h:68

llvm::LocationSize::hasValue

bool hasValue() const

Definition:MemoryLocation.h:165

llvm::LocationSize::isScalable

bool isScalable() const

Definition:MemoryLocation.h:168

llvm::LocationSize::getValue

TypeSize getValue() const

Definition:MemoryLocation.h:170

llvm::MachineFrameInfo

The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.

Definition:MachineFrameInfo.h:106

llvm::MachineFrameInfo::getObjectOffset

int64_t getObjectOffset(int ObjectIdx) const

Return the assigned stack offset of the specified object from the incoming stack pointer.

Definition:MachineFrameInfo.h:528

llvm::MachineFrameInfo::isFixedObjectIndex

bool isFixedObjectIndex(int ObjectIdx) const

Returns true if the specified index corresponds to a fixed stack object.

Definition:MachineFrameInfo.h:700

llvm::MachineFunction::getFrameInfo

MachineFrameInfo & getFrameInfo()

getFrameInfo - Return the frame info object for the current function.

Definition:MachineFunction.h:749

llvm::SDNode

Represents one node in the SelectionDAG.

Definition:SelectionDAGNodes.h:496

llvm::SDValue

Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.

Definition:SelectionDAGNodes.h:145

llvm::SelectionDAG

This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...

Definition:SelectionDAG.h:228

llvm::SelectionDAG::getTargetLoweringInfo

const TargetLowering & getTargetLoweringInfo() const

Definition:SelectionDAG.h:503

llvm::SelectionDAG::getMachineFunction

MachineFunction & getMachineFunction() const

Definition:SelectionDAG.h:492

llvm::SelectionDAG::MaskedValueIsZero

bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth=0) const

Return true if 'Op & Mask' is known to be zero.

Definition:SelectionDAG.cpp:2977

llvm::TargetLowering::unwrapAddress

virtual SDValue unwrapAddress(SDValue N) const

Definition:TargetLowering.h:4273

llvm::details::FixedOrScalableQuantity::getFixedValue

constexpr ScalarTy getFixedValue() const

Definition:TypeSize.h:202

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition:raw_ostream.h:52

llvm::CallingConv::C

@ C

The default llvm calling convention, compatible with C.

Definition:CallingConv.h:34

llvm::ISD::STORE

@ STORE

Definition:ISDOpcodes.h:1103

llvm::ISD::ADD

@ ADD

Simple integer binary arithmetic operators.

Definition:ISDOpcodes.h:246

llvm::ISD::LOAD

@ LOAD

LOAD and STORE have token chains as their first operand, then the same operands as an LLVM load/store...

Definition:ISDOpcodes.h:1102

llvm::ISD::SIGN_EXTEND

@ SIGN_EXTEND

Conversion operators.

Definition:ISDOpcodes.h:805

llvm::ISD::OR

@ OR

Definition:ISDOpcodes.h:710

llvm::ISD::MUL

@ MUL

Definition:ISDOpcodes.h:248

llvm::ISD::POST_DEC

@ POST_DEC

Definition:ISDOpcodes.h:1559

llvm::ISD::PRE_DEC

@ PRE_DEC

Definition:ISDOpcodes.h:1559

llvm::ISD::PRE_INC

@ PRE_INC

Definition:ISDOpcodes.h:1559

llvm::PatternMatch::match

bool match(Val *V, const Pattern &P)

Definition:PatternMatch.h:49

llvm::sampleprof::Base

@ Base

Definition:Discriminator.h:58

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::Offset

@ Offset

Definition:DWP.cpp:480

llvm::print

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)

Definition:GCNRegPressure.cpp:227

llvm::dbgs

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

Definition:Debug.cpp:163

llvm::IRMemLocation::Other

@ Other

Any other memory.

#define N