BasicBlockMatchingAndInference.cpp Source File (original) (raw)

27#include <unordered_map>

29using namespace llvm;

33 cl::desc("Threshold for infer stale profile"),

38public:

40 void init(const std::vector<MachineBasicBlock *> &Blocks,

41 const std::vector &Hashes) {

42 assert(Blocks.size() == Hashes.size() &&

43 "incorrect matcher initialization");

44 for (size_t I = 0; I < Blocks.size(); I++) {

46 uint16_t OpHash = Hashes[I].getOpcodeHash();

47 OpHashToBlocks[OpHash].push_back(std::make_pair(Hashes[I], Block));

48 }

49 }

53 auto BlockIt = OpHashToBlocks.find(BlendedHash.getOpcodeHash());

54 if (BlockIt == OpHashToBlocks.end()) {

55 return nullptr;

56 }

58 uint64_t BestDist = std::numeric_limits<uint64_t>::max();

59 for (auto It : BlockIt->second) {

63 if (BestBlock == nullptr || Dist < BestDist) {

64 BestDist = Dist;

65 BestBlock = Block;

66 }

67 }

68 return BestBlock;

69 }

71private:

72 using HashBlockPairType = std::pair<BlendedBlockHash, MachineBasicBlock *>;

73 std::unordered_map<uint16_t, std::vector> OpHashToBlocks;

74};

77 "machine-block-match-infer",

78 "Machine Block Matching and Inference Analysis", true,

79 true)

83 "Machine Block Matching and Inference Analysis", true, true)

100std::optionalBasicBlockMatchingAndInference::WeightInfo

102 auto It = ProgramWeightInfo.find(FuncName);

103 if (It == ProgramWeightInfo.end()) {

104 return std::nullopt;

105 }

106 return It->second;

107}

108

109BasicBlockMatchingAndInference::WeightInfo

110BasicBlockMatchingAndInference::initWeightInfoByMatching(MachineFunction &MF) {

111 std::vector<MachineBasicBlock *> Blocks;

112 std::vector Hashes;

115 for (auto &Block : MF) {

116 Blocks.push_back(&Block);

118 }

120 Matcher.init(Blocks, Hashes);

121 BasicBlockMatchingAndInference::WeightInfo MatchWeight;

122 auto [IsValid, PathAndClusterInfo] =

123 BSPR->getFunctionPathAndClusterInfo(MF.getName());

124 if (!IsValid)

125 return MatchWeight;

126 for (auto &BlockCount : PathAndClusterInfo.NodeCounts) {

127 if (PathAndClusterInfo.BBHashes.count(BlockCount.first.BaseID)) {

128 auto Hash = PathAndClusterInfo.BBHashes[BlockCount.first.BaseID];

130

131 if (Block != nullptr)

132 MatchWeight.BlockWeights[Block] += BlockCount.second;

133 }

134 }

135 for (auto &PredItem : PathAndClusterInfo.EdgeCounts) {

136 auto PredID = PredItem.first.BaseID;

137 if (!PathAndClusterInfo.BBHashes.count(PredID))

138 continue;

139 auto PredHash = PathAndClusterInfo.BBHashes[PredID];

140 MachineBasicBlock *PredBlock =

141 Matcher.matchBlock(BlendedBlockHash(PredHash));

142 if (PredBlock == nullptr)

143 continue;

144 for (auto &SuccItem : PredItem.second) {

145 auto SuccID = SuccItem.first.BaseID;

146 auto EdgeWeight = SuccItem.second;

147 if (PathAndClusterInfo.BBHashes.count(SuccID)) {

148 auto SuccHash = PathAndClusterInfo.BBHashes[SuccID];

149 MachineBasicBlock *SuccBlock =

150 Matcher.matchBlock(BlendedBlockHash(SuccHash));

151

152 if (SuccBlock != nullptr)

153 MatchWeight.EdgeWeights[std::make_pair(PredBlock, SuccBlock)] +=

154 EdgeWeight;

155 }

156 }

157 }

158 return MatchWeight;

159}

160

161void BasicBlockMatchingAndInference::generateWeightInfoByInference(

163 BasicBlockMatchingAndInference::WeightInfo &MatchWeight) {

164 BlockEdgeMap Successors;

165 for (auto &Block : MF) {

166 for (auto *Succ : Block.successors())

167 Successors[&Block].push_back(Succ);

168 }

169 SampleProfileInference SPI(

170 MF, Successors, MatchWeight.BlockWeights, MatchWeight.EdgeWeights);

171 BlockWeightMap BlockWeights;

172 EdgeWeightMap EdgeWeights;

173 SPI.apply(BlockWeights, EdgeWeights);

174 ProgramWeightInfo.try_emplace(

175 MF.getName(), BasicBlockMatchingAndInference::WeightInfo{

176 std::move(BlockWeights), std::move(EdgeWeights)});

177}

178

181 return false;

182 auto MatchWeight = initWeightInfoByMatching(MF);

183

184

185

186 if (static_cast<float>(MatchWeight.BlockWeights.size()) / MF.size() <

188 return false;

189 }

190 generateWeightInfoByInference(MF, MatchWeight);

191 return false;

192}

193

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static cl::opt< float > PropellerInferThreshold("propeller-infer-threshold", cl::desc("Threshold for infer stale profile"), cl::init(0.6), cl::Optional)

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

The object is used to identify and match basic blocks given their hashes.

Definition BasicBlockMatchingAndInference.cpp:37

void init(const std::vector< MachineBasicBlock * > &Blocks, const std::vector< BlendedBlockHash > &Hashes)

Initialize stale matcher.

Definition BasicBlockMatchingAndInference.cpp:40

MachineBasicBlock * matchBlock(BlendedBlockHash BlendedHash) const

Find the most similar block for a given hash.

Definition BasicBlockMatchingAndInference.cpp:52

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

void setPreservesAll()

Set by analyses that do not transform their input at all.

std::optional< WeightInfo > getWeightInfo(StringRef FuncName) const

Definition BasicBlockMatchingAndInference.cpp:101

bool runOnMachineFunction(MachineFunction &F) override

runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...

Definition BasicBlockMatchingAndInference.cpp:179

BasicBlockMatchingAndInference()

Definition BasicBlockMatchingAndInference.cpp:87

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

Definition BasicBlockMatchingAndInference.cpp:93

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

MachineFunctionPass(char &ID)

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

StringRef - Represent a constant reference to a string, i.e.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI void initializeBasicBlockMatchingAndInferencePass(PassRegistry &)

LLVM_ABI MachineFunctionPass * createBasicBlockMatchingAndInferencePass()

createBasicBlockMatchingAndInferencePass - This pass enables matching and inference when using propel...

Definition BasicBlockMatchingAndInference.cpp:194

An object wrapping several components of a basic block hash.

uint16_t getOpcodeHash() const

uint64_t distance(const BlendedBlockHash &BBH) const

Compute a distance between two given blended hashes.