1 /*
2 * Copyright (c) 2023 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "aarch64_fixshortbranch.h"
17
18 namespace maplebe {
CalculateAlignRange(const BB & bb,uint32 addr) const19 uint32 AArch64FixShortBranch::CalculateAlignRange(const BB &bb, uint32 addr) const
20 {
21 if (addr == 0) {
22 return addr;
23 }
24 uint32 alignPower = bb.GetAlignPower();
25 /*
26 * The algorithm can avoid the problem that alignment causes conditional branch out of range in two stages.
27 * 1. asm: .mpl -> .s
28 * The pseudo-instruction [.p2align 5] is 12B.
29 * kAlignPseudoSize = 12 / 4 = 3
30 * 2. link: .s -> .o
31 * The pseudo-instruction will be expanded to nop.
32 * eg. .p2align 5
33 * alignPower = 5, alignValue = 2^5 = 32
34 * range = (32 - ((addr - 1) * 4) % 32) / 4 - 1
35 *
36 * =======> max[range, kAlignPseudoSize]
37 */
38 uint32 range = ((1U << alignPower) - (((addr - 1) * kInsnSize) & ((1U << alignPower) - 1))) / kInsnSize - 1;
39 return range > kAlignPseudoSize ? range : kAlignPseudoSize;
40 }
41
SetInsnId() const42 void AArch64FixShortBranch::SetInsnId() const
43 {
44 uint32 i = 0;
45 AArch64CGFunc *aarch64CGFunc = static_cast<AArch64CGFunc *>(cgFunc);
46 FOR_ALL_BB(bb, aarch64CGFunc)
47 {
48 FOR_BB_INSNS(insn, bb)
49 {
50 if (!insn->IsMachineInstruction()) {
51 continue;
52 }
53 i += insn->GetAtomicNum();
54 insn->SetId(i);
55 if (insn->GetMachineOpcode() == MOP_adrp_ldr && CGOptions::IsLazyBinding() &&
56 !cgFunc->GetCG()->IsLibcore()) {
57 /* For 1 additional EmitLazyBindingRoutine in lazybinding
58 * see function AArch64Insn::Emit in file aarch64_insn.cpp
59 */
60 ++i;
61 }
62 }
63 }
64 }
65
CalculateIfBBNum() const66 uint32 AArch64FixShortBranch::CalculateIfBBNum() const
67 {
68 uint32 ifBBCount = 0;
69 FOR_ALL_BB(bb, cgFunc)
70 {
71 if (bb->GetKind() != BB::kBBIf) {
72 ifBBCount++;
73 }
74 }
75 return ifBBCount;
76 }
77
PatchLongBranch()78 void AArch64FixShortBranch::PatchLongBranch()
79 {
80 AArch64CGFunc *aarch64CGFunc = static_cast<AArch64CGFunc *>(cgFunc);
81 uint32 ifBBCount = CalculateIfBBNum();
82 for (BB *bb = aarch64CGFunc->GetFirstBB(); bb != nullptr; bb = bb->GetNext()) {
83 if (bb->GetKind() != BB::kBBIf) {
84 continue;
85 }
86 Insn *insn = bb->GetLastMachineInsn();
87 while (insn != nullptr && insn->IsImmaterialInsn()) {
88 insn = insn->GetPrev();
89 }
90 if (insn == nullptr || !insn->IsCondBranch()) {
91 continue;
92 }
93 LabelIdx tbbLabelIdx = aarch64CGFunc->GetLabelInInsn(*insn);
94 // when we change condbr to condbr and b, we will have more insns
95 // in case the insn num will cause distance check not calculating right
96 // we assume that each if bb will be changed(which is the worst case).
97 if (ifBBCount <= AArch64Abi::kMaxInstrForCondBr &&
98 aarch64CGFunc->DistanceCheck(*bb, tbbLabelIdx, insn->GetId(), AArch64Abi::kMaxInstrForCondBr - ifBBCount)) {
99 continue;
100 }
101 aarch64CGFunc->InsertJumpPad(insn);
102 }
103 }
104 /*
105 * TBZ/TBNZ instruction is generated under -O2, these branch instructions only have a range of +/-32KB.
106 * If the branch target is not reachable, we split tbz/tbnz into combination of ubfx and cbz/cbnz, which
107 * will clobber one extra register. With LSRA under -O2, we can use one of the reserved registers R16 for
108 * that purpose. To save compile time, we do this change when there are more than 32KB / 4 instructions
109 * in the function.
110 */
FixShortBranches() const111 void AArch64FixShortBranch::FixShortBranches() const
112 {
113 AArch64CGFunc *aarch64CGFunc = static_cast<AArch64CGFunc *>(cgFunc);
114 bool change = false;
115 do {
116 change = false;
117 SetInsnId();
118 for (auto *bb = aarch64CGFunc->GetFirstBB(); bb != nullptr && !change; bb = bb->GetNext()) {
119 /* Do a backward scan searching for short branches */
120 for (auto *insn = bb->GetLastInsn(); insn != nullptr && !change; insn = insn->GetPrev()) {
121 if (!insn->IsMachineInstruction()) {
122 continue;
123 }
124 MOperator thisMop = insn->GetMachineOpcode();
125 if (thisMop != MOP_wtbz && thisMop != MOP_wtbnz && thisMop != MOP_xtbz && thisMop != MOP_xtbnz) {
126 continue;
127 }
128 LabelOperand &label = static_cast<LabelOperand &>(insn->GetOperand(kInsnThirdOpnd));
129 /* should not be commented out after bug fix */
130 if (aarch64CGFunc->DistanceCheck(*bb, label.GetLabelIndex(), insn->GetId(),
131 AArch64Abi::kMaxInstrForTbnz)) {
132 continue;
133 }
134 auto ® = static_cast<RegOperand &>(insn->GetOperand(kInsnFirstOpnd));
135 ImmOperand &bitSize = aarch64CGFunc->CreateImmOperand(1, k8BitSize, false);
136 auto &bitPos = static_cast<ImmOperand &>(insn->GetOperand(kInsnSecondOpnd));
137 MOperator ubfxOp = MOP_undef;
138 MOperator cbOp = MOP_undef;
139 switch (thisMop) {
140 case MOP_wtbz:
141 ubfxOp = MOP_wubfxrri5i5;
142 cbOp = MOP_wcbz;
143 break;
144 case MOP_wtbnz:
145 ubfxOp = MOP_wubfxrri5i5;
146 cbOp = MOP_wcbnz;
147 break;
148 case MOP_xtbz:
149 ubfxOp = MOP_xubfxrri6i6;
150 cbOp = MOP_xcbz;
151 break;
152 case MOP_xtbnz:
153 ubfxOp = MOP_xubfxrri6i6;
154 cbOp = MOP_xcbnz;
155 break;
156 default:
157 CHECK_FATAL_FALSE("must be");
158 break;
159 }
160 RegOperand &tmp = aarch64CGFunc->GetOrCreatePhysicalRegisterOperand(
161 R16, (ubfxOp == MOP_wubfxrri5i5) ? k32BitSize : k64BitSize, kRegTyInt);
162 (void)bb->InsertInsnAfter(*insn, cgFunc->GetInsnBuilder()->BuildInsn(cbOp, tmp, label));
163 (void)bb->InsertInsnAfter(*insn,
164 cgFunc->GetInsnBuilder()->BuildInsn(ubfxOp, tmp, reg, bitPos, bitSize));
165 bb->RemoveInsn(*insn);
166 change = true;
167 }
168 }
169 } while (change);
170 }
171
CheckFunctionSize(uint32 maxSize) const172 bool AArch64FixShortBranch::CheckFunctionSize(uint32 maxSize) const
173 {
174 uint32 firstInsnId = 0;
175 uint32 lastInsnId = UINT32_MAX;
176 bool findLast = false;
177 bool findFirst = false;
178
179 for (auto *bb = cgFunc->GetLastBB(); bb != nullptr && !findLast; bb = bb->GetPrev()) {
180 for (auto *insn = bb->GetLastInsn(); insn != nullptr && !findLast; insn = insn->GetPrev()) {
181 if (!insn->IsMachineInstruction() || insn->IsImmaterialInsn()) {
182 continue;
183 }
184 findLast = true;
185 lastInsnId = insn->GetId();
186 break;
187 }
188 }
189
190 for (auto *bb = cgFunc->GetFirstBB(); bb != nullptr && !findFirst; bb = bb->GetNext()) {
191 for (auto *insn = bb->GetFirstInsn(); insn != nullptr && !findFirst; insn = insn->GetNext()) {
192 if (!insn->IsMachineInstruction() || insn->IsImmaterialInsn()) {
193 continue;
194 }
195 findFirst = true;
196 firstInsnId = insn->GetId();
197 break;
198 }
199 }
200 return (lastInsnId - firstInsnId + 1) <= maxSize;
201 }
202
203 // when func size >= kMaxInstrForLdr
204 // ldr R1, .L.4__5
205 // .L_x: ...
206 // =>
207 // adrp x1, .L.4__5
208 // add x1, x1, :lo12:.L.4__5
209 // ldr x1, [x1]
FixLdr()210 void AArch64FixShortBranch::FixLdr()
211 {
212 AArch64CGFunc *aarch64CGFunc = static_cast<AArch64CGFunc *>(cgFunc);
213 SetInsnId();
214 if (CheckFunctionSize(AArch64Abi::kMaxInstrForLdr)) {
215 return;
216 }
217 FOR_ALL_BB(bb, cgFunc)
218 {
219 FOR_BB_INSNS(insn, bb)
220 {
221 if (!insn->IsMachineInstruction()) {
222 continue;
223 }
224 if (insn->GetMachineOpcode() == MOP_xldli && insn->GetOperand(kInsnSecondOpnd).IsLabelOpnd()) {
225 // ldr -> adrp + add
226 auto ®Opnd = static_cast<RegOperand &>(insn->GetOperand(kInsnFirstOpnd));
227 auto &labelOpnd = static_cast<LabelOperand &>(insn->GetOperand(kInsnSecondOpnd));
228 Operand &immOpnd = aarch64CGFunc->CreateImmOperand(labelOpnd.GetLabelIndex(), k64BitSize, false);
229 insn->SetOperand(kInsnSecondOpnd, immOpnd);
230 insn->SetMOP(AArch64CG::kMd[MOP_adrp_label]);
231 // ldr x1, [x1]
232 MemOperand *newDest = aarch64CGFunc->CreateMemOperand(
233 k64BitSize, regOpnd, aarch64CGFunc->CreateImmOperand(0, k32BitSize, false), false);
234 auto *newRegOpnd = static_cast<RegOperand *>(regOpnd.Clone(*aarch64CGFunc->GetMemoryPool()));
235 Insn &ldrInsn = aarch64CGFunc->GetInsnBuilder()->BuildInsn(MOP_xldr, *newRegOpnd, *newDest);
236 (void)bb->InsertInsnAfter(*insn, ldrInsn);
237 }
238 }
239 }
240 }
241
PhaseRun(maplebe::CGFunc & f)242 bool CgFixShortBranch::PhaseRun(maplebe::CGFunc &f)
243 {
244 auto *fixShortBranch = GetPhaseAllocator()->New<AArch64FixShortBranch>(&f);
245 CHECK_FATAL(fixShortBranch != nullptr, "AArch64FixShortBranch instance create failure");
246 fixShortBranch->FixShortBranches();
247
248 // fix ldr would cause insn num increasing, do ldr fix first.
249 fixShortBranch->PatchLongBranch();
250 return false;
251 }
252 MAPLE_TRANSFORM_PHASE_REGISTER(CgFixShortBranch, fixshortbranch)
253 } /* namespace maplebe */
254